JPEG-предиктор, PNG-корректор и концевой узел древовидного Undo
Продолжаю разрабатывать систему контроля версий для изображений - она будет лежать в основе ScanCombine, но ей может найтись и множество других применений. Чрезвычайно важно обеспечить малый размер хранимых таким образом изображений - хранить тупо изображение целиком после каждого действия совершенно недопустимо. Один из лучших способов - предиктор-корректор: каждая команда после выполнения сразу пытается отменить действие, насколько это возможно, имея на руках только итоговое изображение - это и есть предиктор. Затем, мы вычитаем из "предсказанного" изображения исходное - и эту разность и сохраняем в древовидном Undo, в файле DLRN. Когда мы захотим отменить операцию, мы снова запустим предиктор, а потом к результатам его работы прибавим разность, по определению получив ровно то, что и должны.
Сейчас опробовал такую ситуацию: мы работаем с изображением, храня его в формате сжатия без потерь (PNG, TIFF, PSD и пр.), и вот вроде все сделали - пора представить его широкой общественности, сохранив в JPEG. Как правило, в такой ситуации мы оставляем изображение, сжатое без потерь - для себя - и его же, с потерями - для размещения на сайте, в торренты и пр.
А что, если сохранение в формат с потерями тоже счесть командой, которую можно отменить? Это очень хорошо ложится в концепцию предиктора-корректора. Предиктор здесь тривиальный: он считает, что сжатие в JPEG не сильно изменило картинку и в целом передает исходное изображение. Тогда корректор записывает разность между исходным изображением и сжатым, и сжимает её без потерь.
(Верхний график - если храним обе версии, с потерями и без потерь. Чуть ниже - то, что я сейчас реализовал - храним JPEG и дельту, т.е разностное, сжатое в PNG. Еще ниже - если только исходное без потерь, ну и два нижних - сколько весит отдельно JPEG и дельта)
В целом, затея весьма удачна - при сжатии полноцветного изображения в JPEG с качеством 80 и сохранением разностного изображения в PNG мы получаем суммарный размер двух этих картинок лишь на 2% выше, чем занимал исходный файл в PNG. Я, правда, вообще надеялся, что иногда JPEG помог бы ужать исходное изображение посильнее, взяв на себя все низкочастотные корреляции между пикселями, которые сам PNG найти неспособен, но увы.
И еще одно приятное дополнение: в древовидном Undo теперь можно объявить команду как концевую. Это значит, что мы не можем выполнить после нее другую команду, а должны вместо этого вернуться на шаг назад и применить новую команду уже там! Это ровно то, что нужно для "сохранить в JPEG" - при попытке продолжить работать с картинкой он "отменяет" сохранение в JPEG, чтобы по невнимательности мы не потеряли качества.
Под катом - как выглядят разностные изображения, осторожно, режет глаза! В качестве подопытного брался полноцветный скан обложки сольфеджио.
Качество JPEG: 60.
Качество 70
Качество 80
Качество 90
Качество 100
Не надо удивляться пестроте - разность "в минус" берется по модулю, т.е -2 запишется как 254, оттого так всё рябит - в основном здесь и встречаются значения 0,1,2, 253,254,255, остальные гораздо реже. Мало того, зелёный передается очень точно, ошибки обычно в красном и синем канале, и это вполне ожидаемо - человек наиболее чувствителен именно к зеленому, и поэтому его JPEG почти не трогает, чтобы никто не догадался.
Еще можно заметить, что чем выше качество JPEG, тем мелкозернистее разностная картинка, всё ближе и ближе к белому шуму.
Я попробовал посчитать энтропию разностного изображения по Шеннону, с точностью до 3 знаков она совпала с размером результирующего PNG, так что сильно улучшить сжатие вряд ли удастся. Было бы интересно использовать корреляцию внутри пиксела (считав красную компоненту, мы можем лучше угадать, какой будет зеленая и синяя, либо, вместо хранения непосредственно их, мы должны использовать их линейные комбинации, которые станут независимыми, и которые можно будет сжать уже по Хаффману), в конце концов, я не обязан в своём древовидном Undo использовать именно PNG для хранения разностей, или я могу использовать своё собственное дополнение формата PNG, например, новый тип фильтра-предиктора, в дополнение к имеющимся 5 (none, Sub, Up, Ave, Paeth).
Сейчас опробовал такую ситуацию: мы работаем с изображением, храня его в формате сжатия без потерь (PNG, TIFF, PSD и пр.), и вот вроде все сделали - пора представить его широкой общественности, сохранив в JPEG. Как правило, в такой ситуации мы оставляем изображение, сжатое без потерь - для себя - и его же, с потерями - для размещения на сайте, в торренты и пр.
А что, если сохранение в формат с потерями тоже счесть командой, которую можно отменить? Это очень хорошо ложится в концепцию предиктора-корректора. Предиктор здесь тривиальный: он считает, что сжатие в JPEG не сильно изменило картинку и в целом передает исходное изображение. Тогда корректор записывает разность между исходным изображением и сжатым, и сжимает её без потерь.
(Верхний график - если храним обе версии, с потерями и без потерь. Чуть ниже - то, что я сейчас реализовал - храним JPEG и дельту, т.е разностное, сжатое в PNG. Еще ниже - если только исходное без потерь, ну и два нижних - сколько весит отдельно JPEG и дельта)
В целом, затея весьма удачна - при сжатии полноцветного изображения в JPEG с качеством 80 и сохранением разностного изображения в PNG мы получаем суммарный размер двух этих картинок лишь на 2% выше, чем занимал исходный файл в PNG. Я, правда, вообще надеялся, что иногда JPEG помог бы ужать исходное изображение посильнее, взяв на себя все низкочастотные корреляции между пикселями, которые сам PNG найти неспособен, но увы.
И еще одно приятное дополнение: в древовидном Undo теперь можно объявить команду как концевую. Это значит, что мы не можем выполнить после нее другую команду, а должны вместо этого вернуться на шаг назад и применить новую команду уже там! Это ровно то, что нужно для "сохранить в JPEG" - при попытке продолжить работать с картинкой он "отменяет" сохранение в JPEG, чтобы по невнимательности мы не потеряли качества.
Под катом - как выглядят разностные изображения, осторожно, режет глаза! В качестве подопытного брался полноцветный скан обложки сольфеджио.
Качество JPEG: 60.
Качество 70
Качество 80
Качество 90
Качество 100
Не надо удивляться пестроте - разность "в минус" берется по модулю, т.е -2 запишется как 254, оттого так всё рябит - в основном здесь и встречаются значения 0,1,2, 253,254,255, остальные гораздо реже. Мало того, зелёный передается очень точно, ошибки обычно в красном и синем канале, и это вполне ожидаемо - человек наиболее чувствителен именно к зеленому, и поэтому его JPEG почти не трогает, чтобы никто не догадался.
Еще можно заметить, что чем выше качество JPEG, тем мелкозернистее разностная картинка, всё ближе и ближе к белому шуму.
Я попробовал посчитать энтропию разностного изображения по Шеннону, с точностью до 3 знаков она совпала с размером результирующего PNG, так что сильно улучшить сжатие вряд ли удастся. Было бы интересно использовать корреляцию внутри пиксела (считав красную компоненту, мы можем лучше угадать, какой будет зеленая и синяя, либо, вместо хранения непосредственно их, мы должны использовать их линейные комбинации, которые станут независимыми, и которые можно будет сжать уже по Хаффману), в конце концов, я не обязан в своём древовидном Undo использовать именно PNG для хранения разностей, или я могу использовать своё собственное дополнение формата PNG, например, новый тип фильтра-предиктора, в дополнение к имеющимся 5 (none, Sub, Up, Ave, Paeth).