Хабр Курсы для всех
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 140
это прекрасно! очень давно искал подобную статью, кратко и понятно.
«Обратное дискретно-косинусное преобразование»
Такое в школе вроде не изучают…
Такое в школе вроде не изучают…
Ну не в 7 классе, чуть позже. Но все таки стоит!
не буду утверждать, что так во всех школах, но, приходилось сидеть на уроке информатики в 5 классе, в школе. Детей спрашивают, что такое монитор, они отвечают контакт. Детей спрашивают, что такое интернет — дети отвечают контакт и Мой мир@mail.ru. Детям пытаются объяснить базовые принципы устройства компьютера, то же устройство байта, etc., дети ничего не слушают, им бы быстрее «вконтактик»…
Сейчас образование не на самом высшем уровне, и информатика — не исключение.
Сейчас образование не на самом высшем уровне, и информатика — не исключение.
Да, и математику нафиг, у меня же калькулятор.
честно говоря большинство моих преподов арифметические ошибки ошибками не считали, и ничего против калькуляторов не имели.
арифметику.
Как же вы узнаете что именно нажимать на калькуляторе? :)
Тоже предпочитаю считатт в уме. Кстати, картинка по теме:
Никто не знает, где про такую методику подробнее можно почитать?
Никто не знает, где про такую методику подробнее можно почитать?
Вы хотите сказать, что сейчас школьники понимают, как работает телевизор или микроволновка, и что эти устройства упростились? Если не объяснять основы, как «устройство байта» и прочее, то такая «информатика» даром не нужна.
Нет, почему же ) Например, бизнес-аналитику вовсе не обязательно понимать устройство байта. И отсутствие такого знания вовсе не мешает ему анализировать систему.
И еще — а действительно ли школьнику необходимо знать устройство телевизора? Физику-электронщику надо, программисту, пожалуй, тоже имеет смысл, а вот школьнику… не факт )
И еще — а действительно ли школьнику необходимо знать устройство телевизора? Физику-электронщику надо, программисту, пожалуй, тоже имеет смысл, а вот школьнику… не факт )
Меня один 9 класник доставал этим вопросом. Дам пусть грызет.
Респект автору. И забавное совпадение — с момента вопроса школьника прошло меньше недели.
Респект автору. И забавное совпадение — с момента вопроса школьника прошло меньше недели.
Доставал именно структурой jpeg?
Да! BMP он освоил :) Кстати, хотел писать свой архиватор… Дам ему дискретку, пусть пишет.
Бредовый школьник — толи изобретатель очередной болгенос, то ли гений необструганный. Все начинает, все бросает на пол дороги. Писал игру на паскале — бросил, за 3 урока освоил Блендер отрубил мартышке ухо нарисованным мечем — забросил. Скачал игровой движок — строит свой CS.
Это АД для учителя… Я за ним не успеваю. Программа ему не интересна.
Если получится вывезу его осенью на конференцию в Москву, может чуть мозга прибавит. А то быть самым умным на деревне — черевато манией величия.
Бредовый школьник — толи изобретатель очередной болгенос, то ли гений необструганный. Все начинает, все бросает на пол дороги. Писал игру на паскале — бросил, за 3 урока освоил Блендер отрубил мартышке ухо нарисованным мечем — забросил. Скачал игровой движок — строит свой CS.
Это АД для учителя… Я за ним не успеваю. Программа ему не интересна.
Если получится вывезу его осенью на конференцию в Москву, может чуть мозга прибавит. А то быть самым умным на деревне — черевато манией величия.
Плоховато вы к ученикам относитесь. Быть самым умным на деревне, при наличии хорошего стимула и поддержки, означает быть самым успешным в жизни.
1. Я к нему плохо не отношусь. Иначе бы им не занимался, а гнал бы программу.
2. Я плохо отношусь к его привычке — снимать сливки и не лезь в глубь. Что-то нужно освоить, а не только по верхам бегать.
3. Его последняя фраза — «я за 3 дня освоил HTML». Я ее уже где то слышал. Поэтому поручил ему сделать поиск в Интернет по фразе Болгенос и сформулировать мнение.
Как то так.
2. Я плохо отношусь к его привычке — снимать сливки и не лезь в глубь. Что-то нужно освоить, а не только по верхам бегать.
3. Его последняя фраза — «я за 3 дня освоил HTML». Я ее уже где то слышал. Поэтому поручил ему сделать поиск в Интернет по фразе Болгенос и сформулировать мнение.
Как то так.
В BMP «по дефолту» нет сжатия вообще, легко проверяется по размеру — размер BMP точно равен (ширина*высота*BPP картинки)+заголовок. Поддержка RLE есть, но не знаю, насколько это актуально для простых графических редакторов. Возможно в более новых вариантах BMP есть что-то более продвинутое, чем RLE.
>да есть там RLE, и все всегда его умели, не спорьте :)
Может и умели, достоверно всего не знаю. По стандарту он есть, так что спорить не буду, естессна :)
У TIFF тоже куча вариантов сжатия, да ещё и слои и прочая лабуда, слишком он навороченный. А вот PCX — это да, штука подходящая.
Может и умели, достоверно всего не знаю. По стандарту он есть, так что спорить не буду, естессна :)
У TIFF тоже куча вариантов сжатия, да ещё и слои и прочая лабуда, слишком он навороченный. А вот PCX — это да, штука подходящая.
У первых спецификаций TIFF было только LZW (во времена Aldus, от которой все досталось Adobe), а так же тег NewSubfileType давал делать только «страницы» внутри TIFF, хранение слоев приделала уже Adobe, им проще — они владельцы спецификации, могут расширять теги как угодно.
Такой же формат (за исключением хидера и в точном соответствии с первоначальными спецификациями и без сжатия) используется в формате Scitex CT
Такой же формат (за исключением хидера и в точном соответствии с первоначальными спецификациями и без сжатия) используется в формате Scitex CT
Хотите формат ещё интереснее - поглядите на древний эппловский PICT, который в одном контейнере содержал и вектор и растр и текстовые объекты и черт знает что ещё, причём как последовательность команд.
Википедия говорит, что есть как минимум JPEG и PNG(Deflate), по крайней мере у biCompression есть значения для этих алгоритмов.
Интересненько…
Классная статья (я кстати, дочитал «до этого места», где мой пирожок). Правда непонятно зачем это все — для jpeg'а есть уже миллиард разных библиотек разной степени велосипедности. :-)
Как зачем? Интересно же самому поковыряться :)
Не поймите неправильно, но все-таки интересно — неужели чисто и только академический интерес? Без практического применения и/или использования в качестве работы в университет или подобного.
Просто работа действительно не шуточная, особенно если в конце концов получился работающий декодер, и добиться не просто понимания как оно работает, а имплементации…
Кроме уважения к проделанной работе у меня все-таки просыпается легкое недоумение (и кажется не только у меня).
Просто работа действительно не шуточная, особенно если в конце концов получился работающий декодер, и добиться не просто понимания как оно работает, а имплементации…
Кроме уважения к проделанной работе у меня все-таки просыпается легкое недоумение (и кажется не только у меня).
Потому что это базовые знания.
Кто хочет развиваться — ищет то, чего не знает. А кто не хочет — сидит в болоте, расчитывая на чужие знания.
Реально раздражают люди, которые спрашивают — «а зачем ты это сделал», да «за тебя это уже сделали» и т.п.
Лучше сидеть вКонтакте и пересмотреть все тупые сериалы когда-либо созданные человечеством.
В средние века людей сжигали за тягу к знаниям, а теперь сжигают глупыми насмешками и глупыми вопросами.
Кто хочет развиваться — ищет то, чего не знает. А кто не хочет — сидит в болоте, расчитывая на чужие знания.
Реально раздражают люди, которые спрашивают — «а зачем ты это сделал», да «за тебя это уже сделали» и т.п.
Лучше сидеть вКонтакте и пересмотреть все тупые сериалы когда-либо созданные человечеством.
В средние века людей сжигали за тягу к знаниям, а теперь сжигают глупыми насмешками и глупыми вопросами.
Простите, но я спрашивал не почему автор разобрался как оно работает, а есть ли этот труд где-то в применении (читай можно ли посмотреть готовую работу и где она применяется).
Конкретной цели не было, применения нет. Но раз уж сделал, была мысль сделать сделать свой просмотрщик, однако понимаю, что это довольно тяжело.
Спасибо.
А как Вы смотрите на реализацию многопоточного пакетного конвертора? Дело в том, что я заметил, что большество готовых конверторов совершенно не утилизируют 2+ ядерные системы (тот же FastStone когда я ему скормил 1к фотографий мрачно взял 80% одного ядра на моем квадре, и отрабатывал довольно долго).
Задача, насколько я понимаю, довольно хорошо паралелится — и не только работу с матрицами (что уже очень не плохо), но можно реализовать в виде нескольких этапов, которые ставятся в очередь исполнения. Если взять 4 ядра и несколько сотен фотографий большого резолюшена, то пока происходит просчет матрицы квантования на одном jpeg, другие worker-ы могут выполнить другие операции от других 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.
В случае декодирования, по сути, всё упирается в скорость последовательного участка — разборки 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.
Например одна фирма сделала загадку при решении которой можно подать туда CV и я думаю будут получены некоторые бонусы. А загадка это битый jpeg файл который надо ручками в hex редакторе восстановиться, чтобы найти ссылку на следующую загадку. Вот пытаясь это дело решить я сюда и забрел.
лучше что-то знать и уметь чем не знать и не уметь
Пример — работа с очень большими изображениями ) почти все готовые либы работают с JPEG в памяти. А если памяти не хватает? Вот тут уже приходится и ручками покопаться, и алгоритмы понапридумывать )
Большое спасибо, очень качественная статья!
Блин, торт! Тортище!
А если не секрет, зачем вы писали свой декодер? Довольно специфичная задача
Спасибо. Не знал что в фавиконке гугла столько «Яд»а :)
Месье знает толк в извращениях!
Помнится читал что в GIF изображения можно без труда поместить php код и большинство загрузчиков файлов пропустят такое изображения и код корректно выполнится на сервере. А что с jpg в этом случае?
Можно поместить что угодно(если какие-либо 2 байта не будут совпадать с маркером) после окончания любой из секций, у которой известна длина. Декодировщики, после чтения секции пропускают байты пока не встретят маркер. Как это применимо в плане помещения туда php-кода я не знаю.
я читал вот это -> «Марсель Низамутдинов — Тактика защиты и нападения на Web-приложения»
Других книг на русском языке по безопасности я увы не нашёл…
Других книг на русском языке по безопасности я увы не нашёл…
скорее всего, там имелось в виду следующее:
* старые непропатченные версии ИЕ6/ИЕ7 могут выполнить js код спрятанный в картинке;
* если разработчик не сделал обработку картинки после ее загрузки на сервак и она тупо копируется в папку доступную из веб, то можно загрузить картинку в теле которой будет php-скрипт и попытаться выполнить его (например, при наличии уязвимости класса php-including);
www.dsec.ru/about/articles/web_xss/
* старые непропатченные версии ИЕ6/ИЕ7 могут выполнить js код спрятанный в картинке;
* если разработчик не сделал обработку картинки после ее загрузки на сервак и она тупо копируется в папку доступную из веб, то можно загрузить картинку в теле которой будет php-скрипт и попытаться выполнить его (например, при наличии уязвимости класса php-including);
www.dsec.ru/about/articles/web_xss/
никто не мешает дописать что угодно в конец файла :)
Сам по себе PHP из картинки, естественно, не выполнится просто так, как ни старайтесь. Для этого требуется убедить интерпретатор (часто путём добавления .php в середину или конец имени файла) выполнить файл, содержащий картинку и добавку в виде PHP кода.
Отсюда вывод: правоверный jpeg начинается с «яШяю» :)
[00 11] Длина: 16 байт.
17
17
оу, классно! Разжевано хорошо достаточно! спасибо.
Не совсем понял, это jpeg картинка, сделанная из ico?
Хорошо расписано, с картинками :)
В вузе на младших курсах развлекался, ковыряя все подряд в hex-редакторах, изучая форматы. После таких упражнений спецификации читались как худлит.
В вузе на младших курсах развлекался, ковыряя все подряд в hex-редакторах, изучая форматы. После таких упражнений спецификации читались как худлит.
Простите, а зачем надо с нуля писать? Реализаций навалом )
Я уже отвечал
«Вам когда-нибудь хотелось узнать как устроен jpg-файл? Сейчас разберемся!» — говорится в сааамом начале текста ;)
Офигенно, спасибо. Пока не успел прочитать, сижу работаю сверхурочно, но именно такую статью по структуре графических файлов в своё время искал. Может напишете серию про различные распространенные мультимедиа-форматы? Интересно, и адски полезно для многих.
Хотелось бы что бы после этой статьи число студентов, собственноручно написавших курсовой по структурам и алгоритмам, увеличилось хотя бы на толику :)
Вы как оптимизировали ДКП? насколько я помню, каконичный алгоритм оперирует произведением матриц. SSE накручивали?
Я думал насчет SSE. Но мне показалось компилятор сам, при определенных опциях, использует SSE-оптимизацию. Но не могу это утверждать.
Моя оптимизация простая — формулу свел к перемножению матриц, косинусы заменил массивом констант, и выделил некоторые частные случаи, когда в матрице преобладают нули.
Если интересно — могу рассказать о своих опытах расковыривания формата Fruity Loops Score (fsc).
Интересно, а на сколько реально «рисовать» jpeg в hex редакторе?
Выше таки написали что-то вроде =)
Статья хорошая, понравилась.
Ностальгия. Как то писал на Verilog, JPEG-encoder. Ну и соответственно пришлось постигать так же процесс построения самого JPEG файла.
Ностальгия. Как то писал на Verilog, JPEG-encoder. Ну и соответственно пришлось постигать так же процесс построения самого JPEG файла.
Класс! Спасибо огромное!
Очень приятно, что кратко и понятно.
Очень приятно, что кратко и понятно.
До сих пор помню, она занимала 7 секунд. Но это и неудивительно, если бездумно пользоваться приведенной формулой, то для вычисления одного канала одного пикселя потребуется нахождения 128 косинусов, 768 умножений, и сколько-то там сложений. Только вдумайтесь — почти тысяча непростых операций только на один канал одного пиксела! К счастью, тут есть простор для отимизации (после долгих экспериментов уменьшил время загрузки до предела точности таймера 15мс, и после этого сменил изображение на фотографию в 25 раз большей площадью. Возможно, напишу об этом отдельной статьей).
я только за
На самом деле, в качестве отправной точки оптимизации надо брать быстрое преобразование Фурье: en.wikipedia.org/wiki/Fast_Fourier_transform, en.wikipedia.org/wiki/Cooley%E2%80%93Tukey_FFT_algorithm
большое спасибо, как раз сам сидел разбирался.
вот бы еще про lossless jpeg так подробно расписали. эх.
вот бы еще про lossless jpeg так подробно расписали. эх.
Хм. А мне казалось что в jpeg'е обязательно должен быть JFIF
А, да, JPEGsnoop говорит, что это идентификатор. Он находится в секции с маркером FFE0. А все секции с маркерами FFEn отданы для приложений. В них же хранится и EXIF. Возможно есть договоренность по этому идентификатору JFIF, но спецификация этого не предусматривает. Поэтому я просто удалил эту секцию.
вагон респекта за столько труда!
Супер! То что я искал! Спасибо автору!!!
Я так когда-то при помощи бинарного просмотрщика (в Тотал Коммандере) и пэйнта без посторонней документации разобрал полноцветный bmp, написал генератор на php и рисовал прямые линии :-)
Пользы ноль, удовольствия — тонна.
Пользы ноль, удовольствия — тонна.
Полноцветный — вполне возможно )
А вот если бы 16-битный формат разобрал — я бы медаль дал ) таких гениев мало )
А вот если бы 16-битный формат разобрал — я бы медаль дал ) таких гениев мало )
А какие с ним сложности? Что два байта на три цвета?
Сам не разбирал, но не думаю, что это задача уровня гения.
А JPG не так подробно, но ковырял: надо было быстро получать из файла размеры картинки и EXIF (чтобы скриптом перелопатить под миллион картинок): так прочесть пару байт из файла оказалось куда быстрей, чем использовать готовые библиотеки, которые грузят картинку в память (может, есть такие, которые не грузят, но за полдня я таких не нашёл).
Сам не разбирал, но не думаю, что это задача уровня гения.
А JPG не так подробно, но ковырял: надо было быстро получать из файла размеры картинки и EXIF (чтобы скриптом перелопатить под миллион картинок): так прочесть пару байт из файла оказалось куда быстрей, чем использовать готовые библиотеки, которые грузят картинку в память (может, есть такие, которые не грузят, но за полдня я таких не нашёл).
Я бы засунул эту статью в перевод, т.к. текст очень похож на англоязычный вариант того, по которому я учился декодить JPEG примерно 8 лет назад. Писал программу на Си для конвертации картинок в ANSII графику…
Какой еще перевод! Я потратил все вечера недели на написание статьи. Сам взял пример, сам декодировал его, сам нарисовал схемы и деревья, сам получил эти таблицы, сам описал процесс. А процесс декодирования он один для всех, поэтому похож.
возможно в тот момент спецификация была не 180 страничная. Пороюсь в документах и попробую привести то что было. А за работу спасибо, прав я или нет, перевод это или нет, главное что работа проделана и проделана качественно и, думаю, поможет многим интересующимся и перспективным пиплам, коих с каждым годом не становиться больше :(
Спасибо, напомнили мне о студенчестве.
Неделю этот алгоритм в Борланд Паскале отлаживал :))
Неделю этот алгоритм в Борланд Паскале отлаживал :))
О души благодарю автора статьи. Впрочем — количество добавивших избранное показывает, что я не один :).
Супер!!! Будет что нибудь подобное для PNG?
Я бы добавил ссылку на Independent JPEG Group откуда можно скачать исходники на С. Там же можно посмотреть на используемые оптимизации, так, например, есть несколько реализаций ДКП и ОДКП. Следует правда отметить, что код написан очень мудрёно.
Также когда-то попадалась на глаза реализация от Intel.
Также когда-то попадалась на глаза реализация от Intel.
Из-за грёбанных патентов до сих пор в jpeg не применяется арифметическое сжатие.
А есть ведь ещё разработки типа типа PackJPG (и другие), обеспечивающие на 30% лучшее сжатие чем обычный jpeg при абсолютном байт-в-байт сходстве распакованной картинки, но тоже проблема — никаких плагинов для браузеров/просмотрщиков/редакторов.
А есть ведь ещё разработки типа типа PackJPG (и другие), обеспечивающие на 30% лучшее сжатие чем обычный jpeg при абсолютном байт-в-байт сходстве распакованной картинки, но тоже проблема — никаких плагинов для браузеров/просмотрщиков/редакторов.
В стандарте описан (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;
}
11 лет прошло, а оказалось очень актуально. @Fil,большое спасибо!
Спасибо.
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Декодирование JPEG для чайников