nabbla (nabbla1) wrote,
nabbla
nabbla1

Categories:

JPEG-предиктор, PNG-корректор и концевой узел древовидного Undo

Продолжаю разрабатывать систему контроля версий для изображений - она будет лежать в основе ScanCombine, но ей может найтись и множество других применений. Чрезвычайно важно обеспечить малый размер хранимых таким образом изображений - хранить тупо изображение целиком после каждого действия совершенно недопустимо. Один из лучших способов - предиктор-корректор: каждая команда после выполнения сразу пытается отменить действие, насколько это возможно, имея на руках только итоговое изображение - это и есть предиктор. Затем, мы вычитаем из "предсказанного" изображения исходное - и эту разность и сохраняем в древовидном Undo, в файле DLRN. Когда мы захотим отменить операцию, мы снова запустим предиктор, а потом к результатам его работы прибавим разность, по определению получив ровно то, что и должны.

Сейчас опробовал такую ситуацию: мы работаем с изображением, храня его в формате сжатия без потерь (PNG, TIFF, PSD и пр.), и вот вроде все сделали - пора представить его широкой общественности, сохранив в JPEG. Как правило, в такой ситуации мы оставляем изображение, сжатое без потерь - для себя - и его же, с потерями - для размещения на сайте, в торренты и пр.

А что, если сохранение в формат с потерями тоже счесть командой, которую можно отменить? Это очень хорошо ложится в концепцию предиктора-корректора. Предиктор здесь тривиальный: он считает, что сжатие в JPEG не сильно изменило картинку и в целом передает исходное изображение. Тогда корректор записывает разность между исходным изображением и сжатым, и сжимает её без потерь.

JPEG+PNG.png

(Верхний график - если храним обе версии, с потерями и без потерь. Чуть ниже - то, что я сейчас реализовал - храним JPEG и дельту, т.е разностное, сжатое в PNG. Еще ниже - если только исходное без потерь, ну и два нижних - сколько весит отдельно JPEG и дельта)

В целом, затея весьма удачна - при сжатии полноцветного изображения в JPEG с качеством 80 и сохранением разностного изображения в PNG мы получаем суммарный размер двух этих картинок лишь на 2% выше, чем занимал исходный файл в PNG. Я, правда, вообще надеялся, что иногда JPEG помог бы ужать исходное изображение посильнее, взяв на себя все низкочастотные корреляции между пикселями, которые сам PNG найти неспособен, но увы.

И еще одно приятное дополнение: в древовидном Undo теперь можно объявить команду как концевую. Это значит, что мы не можем выполнить после нее другую команду, а должны вместо этого вернуться на шаг назад и применить новую команду уже там! Это ровно то, что нужно для "сохранить в JPEG" - при попытке продолжить работать с картинкой он "отменяет" сохранение в JPEG, чтобы по невнимательности мы не потеряли качества.

Под катом - как выглядят разностные изображения, осторожно, режет глаза! В качестве подопытного брался полноцветный скан обложки сольфеджио.

Качество JPEG: 60.
last_page_jpeg60.png

Качество 70
last_page_jpeg70.png

Качество 80
last_page_jpeg80.png

Качество 90
last_page_jpeg90.png

Качество 100
last_page_dif.png

Не надо удивляться пестроте - разность "в минус" берется по модулю, т.е -2 запишется как 254, оттого так всё рябит - в основном здесь и встречаются значения 0,1,2, 253,254,255, остальные гораздо реже. Мало того, зелёный передается очень точно, ошибки обычно в красном и синем канале, и это вполне ожидаемо - человек наиболее чувствителен именно к зеленому, и поэтому его JPEG почти не трогает, чтобы никто не догадался.

Еще можно заметить, что чем выше качество JPEG, тем мелкозернистее разностная картинка, всё ближе и ближе к белому шуму.

Я попробовал посчитать энтропию разностного изображения по Шеннону, с точностью до 3 знаков она совпала с размером результирующего PNG, так что сильно улучшить сжатие вряд ли удастся. Было бы интересно использовать корреляцию внутри пиксела (считав красную компоненту, мы можем лучше угадать, какой будет зеленая и синяя, либо, вместо хранения непосредственно их, мы должны использовать их линейные комбинации, которые станут независимыми, и которые можно будет сжать уже по Хаффману), в конце концов, я не обязан в своём древовидном Undo использовать именно PNG для хранения разностей, или я могу использовать своё собственное дополнение формата PNG, например, новый тип фильтра-предиктора, в дополнение к имеющимся 5 (none, Sub, Up, Ave, Paeth).
Tags: scancombine, Программки
Subscribe

Recent Posts from This Journal

  • Нахождение двух самых отдалённых точек

    Пока компьютер долго и упорно мучал симуляцию, я пытался написать на ассемблере алгоритм захвата на ближней дистанции. А сейчас на этом коде можно…

  • Слишком общительный счётчик

    Вчера я чуть поторопился отсинтезировать проект,параметры не поменял: RomWidth = 8 вместо 7, RamWidth = 9 вместо 8, и ещё EnableByteAccess=1, чтобы…

  • Балансируем конвейер QuatCore

    В пятницу у нас всё замечательно сработало на симуляции, первые 16 миллисекунд полёт нормальный. А вот прошить весь проект на ПЛИС и попробовать "в…

  • Post a new comment

    Error

    Anonymous comments are disabled in this journal

    default userpic

    Your IP address will be recorded 

  • 15 comments

Recent Posts from This Journal

  • Нахождение двух самых отдалённых точек

    Пока компьютер долго и упорно мучал симуляцию, я пытался написать на ассемблере алгоритм захвата на ближней дистанции. А сейчас на этом коде можно…

  • Слишком общительный счётчик

    Вчера я чуть поторопился отсинтезировать проект,параметры не поменял: RomWidth = 8 вместо 7, RamWidth = 9 вместо 8, и ещё EnableByteAccess=1, чтобы…

  • Балансируем конвейер QuatCore

    В пятницу у нас всё замечательно сработало на симуляции, первые 16 миллисекунд полёт нормальный. А вот прошить весь проект на ПЛИС и попробовать "в…