nabbla (nabbla1) wrote,
nabbla
nabbla1

Categories:

Про lossless JPEG rotation

Возращаешься из отпуска, нужно с фотографиями разобраться, ну хотя бы повернуть правильно.

Если картинка у нас в JPEG, то повернуть её можно тремя разными способами:
1. поменять флажок где-то в EXIF'е - операция простейшая, очевидно никаких потерь не вносящая, но далеко не все на этот флажок реагируют, а некоторые реагируют неадекватно
2. декодировать JPEG, повернуть изображение и закодировать в JPEG обратно, скорее всего внеся дополнительные потери.
3. декодировать JPEG лишь отчасти - до блоков с DCT-коэффициентами, после чего расположить эти блоки в другом порядке (транспонировать и зеркально отразить), и внутри каждого блока коэффициенты повернуть (тоже транспонировать и зеркально отразить), после чего заново применить этап энтропийного кодирования, который, как известно, потерь не вносит. Чтобы такой вариант сработал, ширина и высота картинки должна быть кратна 8, а зачастую и 16 (если используется chroma subsampling, т.е понижение разрешения цветоразностных компонент), но именно так чаще всего и бывает, разрешение матрицы принято делать круглым (в двоичной системе) числом.

Интереснее всего повернуть картинку третьим методом - тогда уж точно на любом устройстве, в любой программе она откроется правильно, да и качества не "расплескаем". Когда-то я загуглил это выражение - "lossless JPEG rotation" и нашёл, что да, штука хорошая, и библиотека написана, и программки есть, это дело реализующие, да и родной просмотрщик картинок в Windows этой фичей обзавёлся в какой-то момент, так что можно вертеть смело, и будет всё по высшему разряду.

Захотелось мне проверить, так ли это. Взял исходное изображение, скопировал, открыл просмотрщиком, нажал "повернуть", закрыл просмотрщик, после чего открыл оба файла в фотошопе. Исходный там повернул на 90 градусов, создал в нём новый слой с режимом Subtract, вставил в него картинку из второго файла, избавился от слоёв (flatten image) ну и посмотрел уровни. Кроме огромного пика на 0 был небольшой хвостик, и после растягивания его во весь диапазон получилось вот что:
dif.jpg

Один и тот же результат получился и в WinXP, и в Windows 7. Хм, всё-таки с потерями получается? Странно, я на скриншот натыкался:

такое сообщение возникает, когда ширина или высота не кратны 8, и тогда придётся "честно" распаковать, повернуть и запаковать обратно. Наличие такого сообщения намекает, что в противном случае потери информации не происходит.

Наконец, решил скачать специализированную программу для поворота JPEG без потерь, скачал, повернул, проверил - картина та же самая, файлы не совпадают, хоть тресни!

Пришлось закопаться в тему чуть поглубже...


Эксперимент немножко изменил: теперь осуществляется не один поворот на 90°, а два поворота, сначала по часовой, потом против часовой, но обязательно с сохранением промежуточного варианта в файле. Т.е один раз открыли, повернули по часовой, закрыли, убедились, что файл перезаписан, снова открыли, повернули против часовой, закрыли. Сравнение и исходным файлом показывает: изображения идентичны, не различаясь ни на пиксель. Это верно как для Windows picture viewer, так и для JPEG Lossless Rotator.

Итак, поворот действительно происходит без потерь в том плане, что является полностью обратимым. Но каким-то непостижимым образом от порядка выполнения операций - "сначала поворачиваем коэффициенты DCT, потом делаем IDCT, потом преобразуем YCbCr в RGB" или "делаем IDCT, преобразуем YCbCr в RGB, поворачиваем картинку" - получаются разные результаты.

Такое поведение свойственно не только фотошопу - я пробовал провести сравнение с помощью Paint.net и тоже не получил совпадения.

Самым подозрительным моментом в декодировании JPEG мне показалось восстановление исходного разрешения каналов цветности, т.е chroma upsampling, если таковое необходимо. Именно там может крыться "анизотропия", поскольку большинство таких алгоритмов работают в два прохода, сначала по строкам, потом по столбцам (может, и наоборот, но всегда в одном порядке!).

Я посмотрел на то, как был сжат мой файл (с фотика), там действительно использовалось chroma subsampling, т.е разрешение каналов цветности вдвое уменьшили. Попробовал пересохранить в JPEG без понижения разрешения, в случае фотошопа это качество JPEG, начиная с 7. Перепробовал чуть ли не все ступени: 12, 11, 10, 9 - в каждом случае поворачивал картинку в Windows picture viewer либо JPEG Lossless Rotator - и действительно картинки совпали, ни одного отклонения ни в одном пикселе.

На качестве же 6 снова началось. Похоже, виновник был найден.

Но хотелось всё-таки разобраться подробнее, что там такое происходит. На большой фотографии сложно чего-то найти, поэтому была сделана тестовая картинка 16х16 - две вертикальные красные полосы на белом фоне. Красные - потому что с точки зрения JPEG красным можно заметно пожертвовать в пользу зелёного, огрубив его насколько возможно.

(она растянута до 128х128 методом "ближайшего соседа" для наглядности, по щелчку откроется оригинал 16х16 сурово зажатый JPEG'ом)
2stripes.jpg

Его можно легко и непринуждённо проанализировать с помощью программы JPEG Snoop. Как мы и ожидали, внутри окажется 6 блоков 8х8 - четыре из них для канала яркости Y, ещё по одному - для цветоразностных каналов Cb, Cr.

У всех этих блоков ненулевой является лишь верхняя строка, ниже сплошные нули, что и понятно для изображения из вертикальных линий. Вот эти строки:
левый верхний и левый нижний блоки, канал Y:
832 -264 -255 -243 -198 -156 -102  -51

правый верхний и правый нижний, канал Y:
832 -198 -102   81  198  234  238  136

канал Cb:
 -34   0    0    0    0    0    0    0

канал Cr:
 136  51    0  136  120    0    0  102


Можно тут же осуществить разворот и посмотреть, как выглядит файл после него. Всё как ожидалось: коэффициенты все те же самые, только повёрнуты внутри каждого блока, да и сами блоки идут в другом порядке, действительно, полного перекодирования не происходило, вся информация сохранилась.

Попробуем "ручками" (скажем, в excel) произвести декодирование. Первым делом IDCT, здесь он по сути одномерный, правильную формулу (с масштабированием, принятым именно в JPEG) ищем здесь (это вообще могучий документ, по которому вполне можно написать JPEG-кодер и декодер с нуля, второе у меня получилось, по кр мере baseline), на стр. 27. После обратного преобразования нужно ещё прибавить 128, и получаем вот что.

Канал яркости (одна строка, слева направо):
60,13360867	257,7906832	260,6691047	256,4705544	255,1233352	254,0147911	254,525421	257,2725018	261,4402775	75,65536937	247,5907119	253,3391067	261,2770809	258,4502851	247,3036337	250,9435349

Канал Cb:
123,75	123,75	123,75	123,75	123,75	123,75	123,75	123,75
(не самый интересный)

Канал Cr:
192,3499813	122,7883068	126,4215419	130,7172862	189,2827138	133,5784581	137,2116932	127,6500187


Дальше возникает множество вопросов: нужно ли уже сейчас обрубать значения ниже 0 или выше 255, округлять до целых значений, или сначала преобразовать в RGB, а только потом так делать? Как именно из 8 отсчетов цветности получить необходимые 16?

Почему-то в спецификации JPEG этого тупо не оговорено, и разные декодеры ведут себя немножко по-разному.

Методом подгона я определил, как работает фотошоп. Он уже после IDCT обрубает результаты до 8 бит, а разрешение каналам цветности повышает методом "ближайшего соседа", т.е каждый отсчет канала цветности распространяется на квадратик 2х2 пикселя. Как же выходит, что поворот на 90 и декодирование JPEG "не коммутируют" - так до конца и не ясно. Можно видеть, что операции не вполне линейны и при выходе за диапазон [0;255] от порядка слагаемых может многое зависеть.

Что меня удивило даже больше - насколько различными могут быть результаты декодирования одной и той же картинки разными программами! Слева фотошоп, справа Paint.net
0: (150; 16; 53)    (150; 16; 53)
1: (255; 211; 248)  (255; 223; 248) !!!
2: (248; 255; 248)  (255; 248; 248) !!!
3: (248; 255; 248)  (249; 255; 248) !!!
4: (251; 255; 248)  (251; 255; 248)
5: (253; 255; 247)  (253; 255; 247)
6: (255; 255; 248)  (255; 255; 248)
7: (255; 252; 248)  (255; 244; 248) !!!
8: (255; 213; 248)  (255; 223; 248) !!!

и так далее - разница порою достигает 10, вполне заметно и невооруженным глазом!

Опять же, реверс-инжениринг показывает, что в Paint.net используеется линейная интерполяция для восстановления исходного разрешения каналов цветности. Наибольшая разница проявляется на резких краях, в фотошопе они более резкие (но угловатые), в Paint.net поплавнее.

Выводы такие:
- пользоваться поворотом изображений в стандартном виндовском просмотрщике можно с чистой совестью - он действительно осуществляет поворот без потерь, по кр. мере когда размеры изображения кратны 16. Если нет, то старый Windows picture & fax viewer (под win XP) выдаст предупреждение, новый (под Win 7) скушает с потерей качества и не подавится.

- в спецификации JPEG не прописан весь процесс декодирования целиком, выбрать способ chroma upsampling предлагается декодеру, и они реализованы по-разному, кроме того, ничего не говорится о переполнениях - насколько часто их нужно "обрубать" - держаться в пределах [0; 255] всю дорогу, или вообще считать в плавающей арифметике и лишь на последнем этапе вернуться к 8 битам. В местах резких границ, особенно при высокой степени сжатия это также приведет к различным результатам у разных декодеров

- большинство декодеров (если не все) не обладают симметрией к повороту на 90 градусов, т.е от порядка действий зависит результат. Именно поэтому я поначалу возвёл поклёп на все программы для поворота "без потерь", а дело-то было не в них!

- что я делаю со своей жизнью...
Tags: математика, поездки, программки
Subscribe

  • О вытягивании себя из болота по методу Мюнхгаузена

    Всё готовлюсь к встрече с представителями РКК Энергия, нужно убедить их в моём способе определения положения ВидеоИзмерителя Параметров Сближения на…

  • Ремонт лыжных мостиков

    Вернулся с сегодняшнего субботника. Очень продуктивно: отремонтировали все ТРИ мостика! Правда, для этого надо было разделиться, благо народу…

  • Гетто-байк

    В субботу во время Великой Октябрьской резни бензопилой умудрился петуха сломать в велосипеде. По счастью, уже на следующий день удалось купить…

  • Post a new comment

    Error

    Anonymous comments are disabled in this journal

    default userpic

    Your IP address will be recorded 

  • 23 comments

  • О вытягивании себя из болота по методу Мюнхгаузена

    Всё готовлюсь к встрече с представителями РКК Энергия, нужно убедить их в моём способе определения положения ВидеоИзмерителя Параметров Сближения на…

  • Ремонт лыжных мостиков

    Вернулся с сегодняшнего субботника. Очень продуктивно: отремонтировали все ТРИ мостика! Правда, для этого надо было разделиться, благо народу…

  • Гетто-байк

    В субботу во время Великой Октябрьской резни бензопилой умудрился петуха сломать в велосипеде. По счастью, уже на следующий день удалось купить…