Открыть список
Как стать автором
Обновить

Комментарии 135

это прекрасно! очень давно искал подобную статью, кратко и понятно.
Спасибо! Значит я не зря старался :)
Только недавно пытался въехать в спецификацию, со скрипом — и вот тебе готовое, разжёванное решение =) (ну, не совсем, конечно, но с ним намного проще).
Автор — молодец!
НЛО прилетело и опубликовало эту надпись здесь
«Обратное дискретно-косинусное преобразование»
Такое в школе вроде не изучают…
Ну не в 7 классе, чуть позже. Но все таки стоит!
НЛО прилетело и опубликовало эту надпись здесь
Далеко не факт, скорее будет куча глупых вопросов.
Не меньше ) если нет базы, то все эти ценнейшие знания пройдут мимо.
А базу, как показывает практика, нарабатывают только те, кто сам задается целью изучить устройство компа и программирование. А для остальных все это будет мусором, увы )
не буду утверждать, что так во всех школах, но, приходилось сидеть на уроке информатики в 5 классе, в школе. Детей спрашивают, что такое монитор, они отвечают контакт. Детей спрашивают, что такое интернет — дети отвечают контакт и Мой мир@mail.ru. Детям пытаются объяснить базовые принципы устройства компьютера, то же устройство байта, etc., дети ничего не слушают, им бы быстрее «вконтактик»…
Сейчас образование не на самом высшем уровне, и информатика — не исключение.
ровно так же 10 лет назад школьники не понимали, как работает микроволновка, а 20 лет назад — телевизор.

это нормально, компьютеры должны упрощаться. Если у меня в руках iPad — какой нафиг «монитор» и «системный блок»? Если у меня машина с АКПП — так ли мне необходимо знать, как работает планетарная передача?

не вижу смысла преподавать информатику в том виде, в каком ее, судя по всему, преподают.
Да, и математику нафиг, у меня же калькулятор.
в каком-то смысле — да.

для нематематиков есть калькулятор.

я вот не уверен, что мы с Вами (очевидно, оба имеющие отношение к IT-области) что-то можем сейчас рассказать о валентности или пестиках-тычинках; представляю, кстати, как смеются над нами химики на своем химическом хабрахабре… и о наших представлениях о том, как размножаются бабочки.

да что говорить. я вот даже специально shift зажму.

УСТНЫЙ СЧЕТ ДАВНО СТАЛ РЕДКОСТЬЮ!

Кто утверждает обратное — не знает жизни. Ведь мало кто умеет перемножить в уме двузначные числа (тот, кто быстро складывает — уже пользуется уважением). Включая — ха-ха — айтишников.

Вы думаете, я про новое поколение? да нет, про тридцатилетних тоже. Кто из них помнит правило «умножения на 11», например?

нет, я уверен, в Вашем окружении — все помнят, но если взять чуть более общую картину?
Да ладно вам умножение, расплачиваетесь — проверяйте сдачу. И тренировка, и простые алгоритмы будете в голове держать.

Это как отжиматься — вроде само по себе оно не нужно, а не такой развалиной себя чувствуешь.
На пластике надо проверять особенно :-)
Я-то считать в ума с детства люблю и считаю естественным. Но, как показала жизнь, таких меньшинство.
С другой стороны это даже здорово. Конкуренцию легче составлять, так сказать…
честно говоря большинство моих преподов арифметические ошибки ошибками не считали, и ничего против калькуляторов не имели.
Какое упущение с их стороны ) арифметика и ее закономерности — одна из самых интересных областей математики в начальной школе.
Интересно — понятия слишком субъективное, чтобы судить по нему об опрометчивости преподавателей.
Да и вообще, как по мне, в школе инетесно все, что понятно. А понятно становится когда тебе понятно объясняют. Так что: не могут заинтересовать, пусть хоть не насилуют.
арифметику.
Как же вы узнаете что именно нажимать на калькуляторе? :)
Тоже предпочитаю считатт в уме. Кстати, картинка по теме:

Никто не знает, где про такую методику подробнее можно почитать?
Хм, не прикрепилось что-то изображение в предыдущем комментарии.
image
Вы хотите сказать, что сейчас школьники понимают, как работает телевизор или микроволновка, и что эти устройства упростились? Если не объяснять основы, как «устройство байта» и прочее, то такая «информатика» даром не нужна.
нет, и сейчас не понимают. да, конечно, устройства упростились до «нажми кнопку и оно будет работать». да, я считаю, что знать принцип работы холодильника не обязательно для счастья в жизни (господи, да кто из Ваших знакомых сможет его объяснить?).

другое дело, что многие вещи в школе преподаются для того, чтобы ребенок мог понадкусывать побольше яблок (как в анекдоте) и понять, что ему интересно.

возвращаясь к комментарию, на который я отвечал: видите ли, если «Детей спрашивают, что такое монитор, они отвечают контакт» — это означают, что их ничему не смогли научить. Значит, либо учили не тому, либо не так.
Нет, почему же ) Например, бизнес-аналитику вовсе не обязательно понимать устройство байта. И отсутствие такого знания вовсе не мешает ему анализировать систему.
И еще — а действительно ли школьнику необходимо знать устройство телевизора? Физику-электронщику надо, программисту, пожалуй, тоже имеет смысл, а вот школьнику… не факт )
ну почему же. в случае с ЭЛТ-шками телевизоры являлись хорошим примером применения ряда физических законов на практике.
Меня один 9 класник доставал этим вопросом. Дам пусть грызет.
Респект автору. И забавное совпадение — с момента вопроса школьника прошло меньше недели.
Доставал именно структурой jpeg?
Да! BMP он освоил :) Кстати, хотел писать свой архиватор… Дам ему дискретку, пусть пишет.
Бредовый школьник — толи изобретатель очередной болгенос, то ли гений необструганный. Все начинает, все бросает на пол дороги. Писал игру на паскале — бросил, за 3 урока освоил Блендер отрубил мартышке ухо нарисованным мечем — забросил. Скачал игровой движок — строит свой CS.

Это АД для учителя… Я за ним не успеваю. Программа ему не интересна.
Если получится вывезу его осенью на конференцию в Москву, может чуть мозга прибавит. А то быть самым умным на деревне — черевато манией величия.
Плоховато вы к ученикам относитесь. Быть самым умным на деревне, при наличии хорошего стимула и поддержки, означает быть самым успешным в жизни.
1. Я к нему плохо не отношусь. Иначе бы им не занимался, а гнал бы программу.
2. Я плохо отношусь к его привычке — снимать сливки и не лезь в глубь. Что-то нужно освоить, а не только по верхам бегать.
3. Его последняя фраза — «я за 3 дня освоил HTML». Я ее уже где то слышал. Поэтому поручил ему сделать поиск в Интернет по фразе Болгенос и сформулировать мнение.
Как то так.
начните с более простых вещей, вроде BMP — там RLE обычный, если мне не изменяет память… затем GIF — тут уже LZW, пусть научится писать простой архиватор (это увлекательно же, я тоже в школе писал). А потом JPEG…
В BMP «по дефолту» нет сжатия вообще, легко проверяется по размеру — размер BMP точно равен (ширина*высота*BPP картинки)+заголовок. Поддержка RLE есть, но не знаю, насколько это актуально для простых графических редакторов. Возможно в более новых вариантах BMP есть что-то более продвинутое, чем RLE.
да есть там RLE, и все всегда его умели, не спорьте :)

ну фиг с ним, с BMP

возьмите TIFF
или древний PCX (Paintbrush for DOS!)

по-моему, я с RLE/картинками как раз в PCX познакомился.

в общем, это было для примера — как демонстрировать прогресс в области алгоритмов компрессии (RLE — ведь действительно первое, что приходит в голову)
>да есть там RLE, и все всегда его умели, не спорьте :)
Может и умели, достоверно всего не знаю. По стандарту он есть, так что спорить не буду, естессна :)
У TIFF тоже куча вариантов сжатия, да ещё и слои и прочая лабуда, слишком он навороченный. А вот PCX — это да, штука подходящая.
У первых спецификаций TIFF было только LZW (во времена Aldus, от которой все досталось Adobe), а так же тег NewSubfileType давал делать только «страницы» внутри TIFF, хранение слоев приделала уже Adobe, им проще — они владельцы спецификации, могут расширять теги как угодно.

Такой же формат (за исключением хидера и в точном соответствии с первоначальными спецификациями и без сжатия) используется в формате Scitex CT
Википедия говорит, что есть как минимум JPEG и PNG(Deflate), по крайней мере у biCompression есть значения для этих алгоритмов.
Значения есть, но Windows такие файлы не поддерживает, я проверял.
Может быть, их какой-то редкий особый софт поддерживает.
НЛО прилетело и опубликовало эту надпись здесь
Вселенная не терпит вопросов вообще ) Она просто дает ответы на те из них, на которые сочтет нужным ответить )
Классная статья (я кстати, дочитал «до этого места», где мой пирожок). Правда непонятно зачем это все — для jpeg'а есть уже миллиард разных библиотек разной степени велосипедности. :-)
Как зачем? Интересно же самому поковыряться :)
Не поймите неправильно, но все-таки интересно — неужели чисто и только академический интерес? Без практического применения и/или использования в качестве работы в университет или подобного.

Просто работа действительно не шуточная, особенно если в конце концов получился работающий декодер, и добиться не просто понимания как оно работает, а имплементации…

Кроме уважения к проделанной работе у меня все-таки просыпается легкое недоумение (и кажется не только у меня).
Потому что это базовые знания.
Кто хочет развиваться — ищет то, чего не знает. А кто не хочет — сидит в болоте, расчитывая на чужие знания.
Реально раздражают люди, которые спрашивают — «а зачем ты это сделал», да «за тебя это уже сделали» и т.п.
Лучше сидеть вКонтакте и пересмотреть все тупые сериалы когда-либо созданные человечеством.

В средние века людей сжигали за тягу к знаниям, а теперь сжигают глупыми насмешками и глупыми вопросами.
Простите, но я спрашивал не почему автор разобрался как оно работает, а есть ли этот труд где-то в применении (читай можно ли посмотреть готовую работу и где она применяется).
Конкретной цели не было, применения нет. Но раз уж сделал, была мысль сделать сделать свой просмотрщик, однако понимаю, что это довольно тяжело.
Спасибо.

А как Вы смотрите на реализацию многопоточного пакетного конвертора? Дело в том, что я заметил, что большество готовых конверторов совершенно не утилизируют 2+ ядерные системы (тот же FastStone когда я ему скормил 1к фотографий мрачно взял 80% одного ядра на моем квадре, и отрабатывал довольно долго).

Задача, насколько я понимаю, довольно хорошо паралелится — и не только работу с матрицами (что уже очень не плохо), но можно реализовать в виде нескольких этапов, которые ставятся в очередь исполнения. Если взять 4 ядра и несколько сотен фотографий большого резолюшена, то пока происходит просчет матрицы квантования на одном jpeg, другие worker-ы могут выполнить другие операции от других jpeg-ов (то же построение дерева). Или паралельный поиск оптимального алгоритма сжатия с анализом потерь — этому ваабще цены небыло бы :)

На стандартных декодерах такое сложно сделать, разве что паралельно загружать картинки, но разбить загрузку на этапы… не уверен.

В общем, вот такая идейка, куда реально можно было бы применить полученный результат.
Параллелится отлично, но действительно, это редко используется. Кодирование посложнее. Подумаю, спасибо за совет :)
Параллельно можно обрабатывать и 1 картинку.
В случае декодирования, по сути, всё упирается в скорость последовательного участка — разборки huffman-а. DCT/color-transform можно разложить на любое число тредов.

Huffman можно декодировать simd-ом, но это несколько геморно в случае jpeg-а (в mpeg фиксированные таблицы huffman-а и имеются simd реализации) но реализуемо.
Если изображение большое, то можно и поспекулировать — декодировать битовый поток с нескольких мест файла — нужно только найти начало кода. Т.е. по-идее тупо декодируем с произвольного бита и если не декодировалось, возвращаемся к изначальной точке и смещаемся на 1 бит.

У меня в PS3 SPU реализации Jpeg декодера около 70% уходило на huffman, но правда я не оптимизировал этот участок, а оптимизировать там есть что. В принципе декодер и так давал 40-50MPix/s с 1 SPU — так что я не особо загонялся по этому поводу.

>> Или паралельный поиск оптимального алгоритма сжатия с анализом потерь
У jpeg один алгоритм (не считая lossless)
Но можно играть таблицей квантизации и фильтровать блоки 8x8 чтобы они занимали меньше памяти после DCT.
Гм, я тоже распараллеливал. Но только ДКП, так как это жрало процентов 80. На двухядерном E8500 стало выдавать примерно такую же скорость. А разбор битового потока шел довольно быстро.
Например одна фирма сделала загадку при решении которой можно подать туда CV и я думаю будут получены некоторые бонусы. А загадка это битый jpeg файл который надо ручками в hex редакторе восстановиться, чтобы найти ссылку на следующую загадку. Вот пытаясь это дело решить я сюда и забрел.
лучше что-то знать и уметь чем не знать и не уметь

Пример — работа с очень большими изображениями ) почти все готовые либы работают с JPEG в памяти. А если памяти не хватает? Вот тут уже приходится и ручками покопаться, и алгоритмы понапридумывать )
Большое спасибо, очень качественная статья!
А если не секрет, зачем вы писали свой декодер? Довольно специфичная задача
Спасибо. Не знал что в фавиконке гугла столько «Яд»а :)
Он есть во всех jpg-файлах :)
НЛО прилетело и опубликовало эту надпись здесь
Помнится читал что в GIF изображения можно без труда поместить php код и большинство загрузчиков файлов пропустят такое изображения и код корректно выполнится на сервере. А что с jpg в этом случае?
Можно поместить что угодно(если какие-либо 2 байта не будут совпадать с маркером) после окончания любой из секций, у которой известна длина. Декодировщики, после чтения секции пропускают байты пока не встретят маркер. Как это применимо в плане помещения туда php-кода я не знаю.
Вы читали какую-то желтую прессу, простите )

Максимум, что могло быть — это какая-нибудь ошибка типа stack overflow в декодере чего-то вроде ImageMagick/GD. Вы заливаете туда файл, php-скрипт его пытается сконвертировать, из картинки вылезает код и с правами GD начинает творить чудеса. Что-то вроде этого
я читал вот это -> «Марсель Низамутдинов — Тактика защиты и нападения на Web-приложения»
Других книг на русском языке по безопасности я увы не нашёл…
скорее всего, там имелось в виду следующее:
* старые непропатченные версии ИЕ6/ИЕ7 могут выполнить js код спрятанный в картинке;
* если разработчик не сделал обработку картинки после ее загрузки на сервак и она тупо копируется в папку доступную из веб, то можно загрузить картинку в теле которой будет php-скрипт и попытаться выполнить его (например, при наличии уязвимости класса php-including);

www.dsec.ru/about/articles/web_xss/
никто не мешает дописать что угодно в конец файла :)
Сам по себе PHP из картинки, естественно, не выполнится просто так, как ни старайтесь. Для этого требуется убедить интерпретатор (часто путём добавления .php в середину или конец имени файла) выполнить файл, содержащий картинку и добавку в виде PHP кода.
Отсюда вывод: правоверный jpeg начинается с «яШяю» :)
Не совсем :) Начинается всегда «яШ». Но порядок остальных маркеров(кроме SOS, конца файла, и еще некоторых) не регламентирован.
О, недоглядел, спасибо за внимательность!
оу, классно! Разжевано хорошо достаточно! спасибо.
Не совсем понял, это jpeg картинка, сделанная из ico?
Верно. От ico там ничего нет.
А пережал так сильно, чтобы уменьшить размер, и в особенности деревья Хаффмана.
Хорошо расписано, с картинками :)
В вузе на младших курсах развлекался, ковыряя все подряд в hex-редакторах, изучая форматы. После таких упражнений спецификации читались как худлит.
Простите, а зачем надо с нуля писать? Реализаций навалом )
Ясно… Круто, сам ковырял просто тоже :-)
«Вам когда-нибудь хотелось узнать как устроен jpg-файл? Сейчас разберемся!» — говорится в сааамом начале текста ;)
Офигенно, спасибо. Пока не успел прочитать, сижу работаю сверхурочно, но именно такую статью по структуре графических файлов в своё время искал. Может напишете серию про различные распространенные мультимедиа-форматы? Интересно, и адски полезно для многих.
Пожалуйста! Я подумаю. Это занимает много времени, но может на досуге еще что-нибудь расковыряю :)
Радует, что любознательность еще не все растеряли. Благодаря таким как вы, хабр ещё торт ;)
Если надумаете, может, на сайте своем выложите?
И людям искать удобно, и свой ресурс продвинете уникальным и ценным контентом.
Хотелось бы что бы после этой статьи число студентов, собственноручно написавших курсовой по структурам и алгоритмам, увеличилось хотя бы на толику :)
Главное, чтобы не старые алгоритмы заново реализовывали, а новые идеи находили ) Иначе большого смысла нет.
Вы как оптимизировали ДКП? насколько я помню, каконичный алгоритм оперирует произведением матриц. SSE накручивали?
Я думал насчет SSE. Но мне показалось компилятор сам, при определенных опциях, использует SSE-оптимизацию. Но не могу это утверждать.
Моя оптимизация простая — формулу свел к перемножению матриц, косинусы заменил массивом констант, и выделил некоторые частные случаи, когда в матрице преобладают нули.
ну тоже самое что и RES*IMG*DCTT

> Но мне показалось компилятор сам, при определенных опциях, использует SSE-оптимизацию.
некоторые преобразуют раскрытые циклы…
Я тоже читал статью на codenet :) Что-то они там намудрили. IMG — исходная матрица, RES — полученная матрица ДКП, но что тогда значит RES*IMG? Вероятно они имели в виду RES = DCT*RES*DCTT
Если интересно — могу рассказать о своих опытах расковыривания формата Fruity Loops Score (fsc).
Вот это было бы тоже интересно! Давайте
Интересно, а на сколько реально «рисовать» jpeg в hex редакторе?
В HEX-редакторе реально сделать всё что угодно. Вопрос только в навыке и наличии большого количества свободного времени :)
Насчет большого количества — это вы в самую точку )
Зато компенсируется самоудовлетворением )
НЛО прилетело и опубликовало эту надпись здесь
Перечитал все комментарии, удивляюсь, как это никто не всунулся и не написал:
Хабр ТОРТ!

Статья зачОт!
Чорт, мимо :)
Статья хорошая, понравилась.
Ностальгия. Как то писал на Verilog, JPEG-encoder. Ну и соответственно пришлось постигать так же процесс построения самого JPEG файла.
НЛО прилетело и опубликовало эту надпись здесь
Класс! Спасибо огромное!
Очень приятно, что кратко и понятно.
До сих пор помню, она занимала 7 секунд. Но это и неудивительно, если бездумно пользоваться приведенной формулой, то для вычисления одного канала одного пикселя потребуется нахождения 128 косинусов, 768 умножений, и сколько-то там сложений. Только вдумайтесь — почти тысяча непростых операций только на один канал одного пиксела! К счастью, тут есть простор для отимизации (после долгих экспериментов уменьшил время загрузки до предела точности таймера 15мс, и после этого сменил изображение на фотографию в 25 раз большей площадью. Возможно, напишу об этом отдельной статьей).

я только за
Да, я на них тоже наткнулся, но так и не решился разбираться.
Согласен, во первых FFT. А во вторых косинусы не пересчитывать а держать константами. (ха, капитан очевидность)
большое спасибо, как раз сам сидел разбирался.
вот бы еще про lossless jpeg так подробно расписали. эх.
Хм. А мне казалось что в jpeg'е обязательно должен быть JFIF
А, да, JPEGsnoop говорит, что это идентификатор. Он находится в секции с маркером FFE0. А все секции с маркерами FFEn отданы для приложений. В них же хранится и EXIF. Возможно есть договоренность по этому идентификатору JFIF, но спецификация этого не предусматривает. Поэтому я просто удалил эту секцию.
вагон респекта за столько труда!
Супер! То что я искал! Спасибо автору!!!
Я так когда-то при помощи бинарного просмотрщика (в Тотал Коммандере) и пэйнта без посторонней документации разобрал полноцветный bmp, написал генератор на php и рисовал прямые линии :-)
Пользы ноль, удовольствия — тонна.
насколько «прямые линии»? алгоритм Брезенхейма? )
Да вы что, исключительно вертикальные и горизонтальные :-) Я в том юном возрасте даже фамилию такую прочитать не смог бы)
Хотя пробовал рисовать под углом — понял, что ничего не смогу, а про алгоритмы читать негде — интернета не было.
Полноцветный — вполне возможно )
А вот если бы 16-битный формат разобрал — я бы медаль дал ) таких гениев мало )
А какие с ним сложности? Что два байта на три цвета?
Сам не разбирал, но не думаю, что это задача уровня гения.

А JPG не так подробно, но ковырял: надо было быстро получать из файла размеры картинки и EXIF (чтобы скриптом перелопатить под миллион картинок): так прочесть пару байт из файла оказалось куда быстрей, чем использовать готовые библиотеки, которые грузят картинку в память (может, есть такие, которые не грузят, но за полдня я таких не нашёл).
Я бы засунул эту статью в перевод, т.к. текст очень похож на англоязычный вариант того, по которому я учился декодить JPEG примерно 8 лет назад. Писал программу на Си для конвертации картинок в ANSII графику…
Какой еще перевод! Я потратил все вечера недели на написание статьи. Сам взял пример, сам декодировал его, сам нарисовал схемы и деревья, сам получил эти таблицы, сам описал процесс. А процесс декодирования он один для всех, поэтому похож.
возможно в тот момент спецификация была не 180 страничная. Пороюсь в документах и попробую привести то что было. А за работу спасибо, прав я или нет, перевод это или нет, главное что работа проделана и проделана качественно и, думаю, поможет многим интересующимся и перспективным пиплам, коих с каждым годом не становиться больше :(
Спасибо, напомнили мне о студенчестве.
Неделю этот алгоритм в Борланд Паскале отлаживал :))
О души благодарю автора статьи. Впрочем — количество добавивших избранное показывает, что я не один :).
Рад, что понравилось! Я сам в шоке от количества :)
Супер!!! Будет что нибудь подобное для PNG?
Спасибо :) Возможно, но на это уходит куча времени.
Я бы добавил ссылку на Independent JPEG Group откуда можно скачать исходники на С. Там же можно посмотреть на используемые оптимизации, так, например, есть несколько реализаций ДКП и ОДКП. Следует правда отметить, что код написан очень мудрёно.

Также когда-то попадалась на глаза реализация от Intel.
Из-за грёбанных патентов до сих пор в jpeg не применяется арифметическое сжатие.
А есть ведь ещё разработки типа типа PackJPG (и другие), обеспечивающие на 30% лучшее сжатие чем обычный jpeg при абсолютном байт-в-байт сходстве распакованной картинки, но тоже проблема — никаких плагинов для браузеров/просмотрщиков/редакторов.
p.s. хотя патенты то уже несколько лет как кончились.
В стандарте описан (Figure C.2) очень простой способ генерировать коды хаффмана, вот псевдокод:
//code_counts - массив количеств кодов из 16 элементов.
code = 0
for(i in 0..16)
{
  for(j in 0..code_counts[i])
  {
    codes[(i + 1,  code)] = read_next_value(); //i + 1 — битовая длина кода, в младших битах (i + 1) code сам код
    ++code;
  }
  code <<= 1;
}
Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.