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

  • Лестница для самых жадных

    В эти выходные побывал на даче, после 3-недельной "самоизоляции". Забавно, как будто зима началась! Особенно грязные галоши остались на улице, в…

  • Возвращаемся к макету

    Очень давно макетом видеоизмерителя параметров сближения не занимался: сначала "громко думал" по поводу измерения его положения на аппарате, а потом…

  • Минутка живописи

    В процессе разгребания содержимого квартиры (после нескольких ремонтов) дошёл, наконец, и до картин. В кои-то веки их повесил. Куда их вешать -…

  • Post a new comment

    Error

    Anonymous comments are disabled in this journal

    default userpic

    Your IP address will be recorded 

  • 15 comments

  • Лестница для самых жадных

    В эти выходные побывал на даче, после 3-недельной "самоизоляции". Забавно, как будто зима началась! Особенно грязные галоши остались на улице, в…

  • Возвращаемся к макету

    Очень давно макетом видеоизмерителя параметров сближения не занимался: сначала "громко думал" по поводу измерения его положения на аппарате, а потом…

  • Минутка живописи

    В процессе разгребания содержимого квартиры (после нескольких ремонтов) дошёл, наконец, и до картин. В кои-то веки их повесил. Куда их вешать -…