Программирование

[parallelno]

Буду сюда выкладывать сравнения.
Для сравнения я взял картинку, адаптировал под размер и палитру Вектора, затем индексы цвета двух соседних вертикальных пикселей объеденил в один байт. Добавил палитру, все упаковал UPKR упаковщиком.
Вторая картинка это та же картинка только прогоненая через vector quantization, затем декодированная обратно, востановлена палитра (местами неточно). Потом индексы цвета двух соседних вертикальных пикселей объеденил в один байт, упаковано UPKR упаковщиком.

То есть подход по сути не упаковщик, а упрошатель картинок.
Я сделал свой формат на тайлах, но он начинает сильно жирнеть когда тайлов больше 256, поэтому отказался в пользу просто востановленной картинки после квантизации и упакованой как та с которой идет сравнение.

и так lossless vs lossy:

contrast_dither_adaptive
original image to upkr: 8886 // lossless, 8886 байт
vector quantization to upkr:
3608, rate: 0.41, tile_size: 4, n_clusters: 256 // lossy, 3608 байт. rate это во сколько он меньше чем lossless
4473, rate: 0.50, tile_size: 4, n_clusters: 1536
6605, rate: 0.74, tile_size: 2, n_clusters: 1536



- - - Добавлено - - -

original image to upkr: 8886
vector quantization to upkr:
3554, rate: 0.40, tile_size: 4, n_clusters: 256
4428, rate: 0.50, tile_size: 8, n_clusters: 256
5531, rate: 0.62, tile_size: 2, n_clusters: 1536




- - - Добавлено - - -

image_intro2
original image to upkr: 8049
vector quantization to upkr:
3651, rate: 0.45, tile_size: 8, n_clusters: 256
4386, rate: 0.54, tile_size: 4, n_clusters: 1024
5273, rate: 0.66, tile_size: 2, n_clusters: 1536



- - - Добавлено - - -

img06
original image to upkr: 10230
vector quantization to upkr:
4333, rate: 0.42, tile_size: 8, n_clusters: 256
4873, rate: 0.48, tile_size: 8, n_clusters: 512
5322, rate: 0.52, tile_size: 2, n_clusters: 1536




- - - Добавлено - - -

img14
original image to upkr: 3818
vector quantization to upkr:
2828, rate: 0.74, tile_size: 4, n_clusters: 512
3295, rate: 0.86, tile_size: 2, n_clusters: 512
3604, rate: 0.94, tile_size: 2, n_clusters: 1536



- - - Добавлено - - -

img17
original image to upkr: 3008
vector quantization to upkr:
2751, rate: 0.91, tile_size: 2, n_clusters: 96
2877, rate: 0.96, tile_size: 2, n_clusters: 1536



- - - Добавлено - - -

svofski, а какие размеры получились у писателей? у тебя сохранились оригиналы, хочется прогнать через VQ алгоритм.

[svofski]

svofski, а какие размеры получились у писателей? у тебя сохранились оригиналы, хочется прогнать через VQ алгоритм.

Пушкин был 1394 байта + 373 байта рисовалка, спасибо ivagor-у. Но это нельзя сравнивать. В моем алгоритме псевдослучайно блуждающая кисточка малюет картинку и фактически он пригоден только для очень крупных планов и высоко узнавабельных оригиналов. Скорость отображения очень низкая, это годится только как демо-эффект, но для этого надо сначала все разогнать раз в 10. Наверняка можно улучшить, но все равно на алгоритм для общего применения он никогда не потянет.

Оригинала картинок у меня не сохранилось, но если просто сравнить, тут ничего сложного. Берешь первый попавшийся портрет (не обязательно Пушкина на самом деле), обрезаешь его примерно вот так как у меня, и запускаешь.

- - - Добавлено - - -

Картинку типа img06 по-моему можно векторизовать и рисовать полигонами. Но это тоже вряд ли получится сделать очень быстро.

[parallelno]

Хочется услышать ваши мысли по поводу результатов. Все ли понятно из статистики? Какие вы видите плюсы и минусы. Может быть у вас есть идеи для улучшения?

[ivagor]

Абстрактные оценки в вакууме мало что дадут. Сколько свободной памяти и сколько картинок нужно разместить?

Если несколько больших (полноэкранных?) картинок, то использование upkr мне кажется жестоким по отношению к пользователю. Понимаю в деме предельных параметров распаковать 1-2 картинки, человек посмотрит ее один раз и успокоится. А если запускать игру несколько раз и там каждый раз upkr распаковывает картинки по 32 Кб, то терпение быстро иссякнет. Еще момент с местом под распаковку - при использовании "безбуферных" (выдающих полный результат) распаковщиков в сочетании с пикселями нужно дополнительно 32 Кб. Вместо этого можно использовать менее эффективные упаковщики, но с буферными (удобно на 256 байт) распаковщиками и потратить те 32 Кб на компенсацию меньшей степени сжатия. На мой взгляд приемлемыми компромиссами по скорости и степени сжатия являются rip и exomizer, плюс они умеют ограничивать длину и дальность ссылок, т.е. можно распаковывать в кольцевой буфер ограниченного размера.

Никогда всерьез не занимался сжатием палитровых картинок, но насколько я понял из прочитанного, сейчас самый модный вариант - предсказатели+оптимизация палитры для согласования+сжимаем арифметическим кодером. Но тут еще надо найти эти экспериментальные упаковщики, сделать для них распаковщик для вектора и получить скорость скорее всего хуже upkr.
Для полутоновых или нечто jpeg-подобное (с ДКП) или вейвлеты. Но тут сразу много вопросов - насколько приемлемы полутоновые картинки, устроит ли 8 оттенков желтого/зеленого/красного, распаковщик сложный и медленный. 16 отенков серого на ЧБ мониторе более интересны, но это специфическое решение. Кстати, для полутоновых векторное кодирование должно давать более приемлемые результаты, чем для палитровых. Еще можно вспомнить экзотику типа фрактальных, но это опять надо искать упаковщики и делать распаковщик.

Возвращаясь на землю, я бы скорее всего ориентировался на rip. Если сжимать байты, то распаковываем на экран. Если сжимаем пиксели, то распаковываем в кольцевой буфер. Пиксели сжимаются лучше, но ограничение длины и дальности ссылок ухудшает сжатие, поэтому надо смотреть конкретные примеры. Также использование буфера позволяет распаковывать картинки произвольного размера, а не на полный экран.

[parallelno]

ivagor, напиши пожалуйста что ты думаешь про упрощатель картинок. Напиши если можешь свои мысли по поводу соотношения качества изображения и размера. Вместо upkr может быть любой упаковщик.

[ivagor]

Про упрощатель у меня есть не особо оригинальная мысль:
1) делим картинку на квадратные или прямоугольные блоки
2) в рамках блока оставляем 2 или 4 цвета из 16
Тут несколько степеней свободы или точек приложения сил для экспериментов
1) какие размеры блоков выбрать
2) сколько цветов в рамках блока
3) как выбирать цвета (понятно, что тут с потерями) когда выбор неоднозначен
Из упаковщиков я бы, по крайней мере для начала, ориентировался на salvador. Он умеет сжимать под кольцевой буфер заданного размера и для буфера 256 байт есть готовый распаковщик zx0.
Для примера: пусть блоки 8x8, в блоках 4 цвета из 16. Картинка 256x256: 16 Кб пиксели, 2 Кб цвета блоков. Т.е. в примере из 32 Кб сократили до 18 и это еще без сжатия "обычным" упаковщиком. Другое дело, как будет выглядеть такая упрощенная картинка, возможно, что совершенно неприемлемо.
Вариант с блоками можно развить до иерархического, опять же надо пробовать, возможно это дурацкая идея, а может где-то хорошо подойдет.

[parallelno]

А что ты думаешь про результаты упрощателя которые я представил выше?

[ivagor]

Если сравнивать с беспотерьным вариантом, то результаты интересные. Но, как я ранее написал, считаю, что надо сравнивать с целевыми значениями (сколько места и сколько картинок требуется) и с использованием чего-то менее сурового, чем upkr.

[Improver]

Про упрощатель у меня есть не особо оригинальная мысль:
1) делим картинку на квадратные или прямоугольные блоки
2) в рамках блока оставляем 2 или 4 цвета из 16

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

[ivagor]

В принципе одноцветные блоки должен дожимать упаковщик. Но есть другой вариант - если цветов на блок 4, то всего комбинаций 65536, а для картинки 256x256 будут востребованы максимум 1024. Часть комбинаций можно задействовать для индикации неких специфичных блоков, например одноцветных. Для палитровых картинок разбиение на плоскости в общем случае вряд ли много что даст, разве что в связке с оптимизацией палитры (перестановками).