Создаём подобие JPEG для ретрокомпов (Walsh+Huffman)

[Shaos]

Выложил версию 1.0.2, в которой добавил ещё 2 способа обхода спектра:

walshexp_traverse3new.png

Причём формат WHI файла расширился так, что старые файлы всё ещё читаются (ранее написано как я это сделал)

https://gitlab.com/shaos/graphin/-/tree/main/WALSHEXP

P.S. Обновил приаттаченную к первому сообщению версию - теперь там тоже 1.0.2

[Shaos]

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

Кто такой есть маркер комментариев?

В смысле как в JPEG? https://habr.com/en/articles/102521/

Не - комментарии лишние

да, это он - COM (FF FE)

Таки будет у меня комментарий

Но только когда WHI файлы первой версии (сигнатура W1), которые кодируют один квадрат, будут склеиваться вместе (можно через COPY /B это делать) и комментарий, идущий после сигнатуры W0, будет нужен для указания что с этими квадратами делать, например текст "320x200" будет означать что далее идущую цепочку квадратов надо выложить как чёрно-белую картинку в экран 320x200 слева-направо сверху-вниз, а скажем "RGB320x200" будет говорить о том, что далее идут квадратики по каналам: R,G,B,R,G,B и т.д. которые также будут заполнять экран 320x200. Анимацию даже можно аналогичным образом задавать указав комментарий "MOVIE"

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

[shiny]

Довольно прозрачно описано. у jpg кроме маркера добавлено слово - длина текстового комментария.
Заодно формат кодировки ANSI, что придаст свою головную боль.

[Shaos]

У меня будет просто строка заканчивающаяся нулём

[Shaos]

Пока выложил свои эксперименты с отрисовкой RGB картинок используя 256-цветную палитру:

https://gitlab.com/shaos/graphin/-/blob/main/EXAMPLES/RGB_VIEW.CPP

[shiny]

как говаривал мой приятель - очень даже сексуально выглядит.

[Shaos]

Пока выложил свои эксперименты с отрисовкой RGB картинок используя 256-цветную палитру

Заодно выложил обновлённую версию Walsh Explorer v1.0.3 (в первом сообщении этого топика архив также обновлён):

https://gitlab.com/shaos/graphin/-/blob/main/WALSHEXP/

В версии 1.0.3 заточка под нового графина и меню обхода матрицы отсчётов спектра слегка переставил:

[Shaos]

Думаю какую-то автоматизацию в Walsh Explorer прикрутить, чтобы разные опции пробовать при сохранении WHI-файла не вручную, а программно (через внешний файл команд, который будет генерироваться другой программой). Потом пользуясь полученными результатами приделаю в Walsh Explorer адаптивный алгоритм (сохранение файла в самом компактном виде по заданному качеству Q). Потом поддержку цветных картинок прикручу (пользуясь наработками, что изложены выше) и только потом создам отдельную либу кодера-декодера для включения в сторонние программы (в том числе в наш будущий графический редактор nedopixels).

P.S. Сделал автоматизацию по быстрому на уровне графина (но пока не выкладываю). Команды в ней задаются в текстовом "скрипте" имя которого даётся как аргумент при вызове WALSHEXP.EXE и который выглядит вот так:

Code: Select all

Load BWS image=1
PANEL10=FEMALEB.BWS
Walsh transform >>>=1
Walsh transform=10
# Comments
PANEL12=97
12 bits per sample=64
Traversal strategy=1
Compression method=3
FB6-134
Walsh transform=0
Walsh transform >>>=0

Этот скрипт открывает файл FEMALEB.BWS, выбирает сохранение WHI устанавливая нужные опции (менюшки идентифицируются первой строчкой меню, которая обычно обозначает заголовок, а панельки - количеством видимых элементов) и задавая имя сохраняемого файла FB6-134 после чего программа закрывается (т.к. последней командой идёт выбрать Exit в главном меню)...

[Shaos]

Выложил версию 1.0.4 с автоматизацией

https://gitlab.com/shaos/graphin

Архив в первом сообщении топика тоже обновил

P.S. Также в меню задания битности для квантования сделал стартовое значение 12 вместо 13, т.к. 13 это слишком много - мой Хаффман не справляется с таким количеством литералов...

[Shaos]

Вот с помощью GIMP слепил вместе сжатые независимо друг от друга каналы RGB с разной битностью, примерным показателем качества Q и коэффициентом сжатия K:

FemaleRGB-9bit-Q99-x3.png

FemaleRGB-7bit-Q91-x3.png

FemaleRGB-6bit-Q62-x3.png

FemaleRGB-5bit-Q27-x3.png

FemaleRGB-4bit-Q12-x3.png

Такое ощущение, что качество надо задавать не от 0 до 99, а 1,2,3,4,5,6,7,8,9 ибо скачки большие (качество я тут считал как процент оставшихся ненулевых квантованных отсчётов по отношению к количеству ненулевых неквантованных отсчётов коих было порядка 86% в данном конкретном изображении) либо вообще программно прогнать все значения битностей от 12 до 3 и показать пользователю все варианты, чтобы он выбирал сам...

[Shaos]

Сохранил оригинальную цветную картинку как JPEG с качеством от 0 до 100 с шагом от 1 до 5:

Code: Select all

-rw-r--r-- 1 shaos shaos  409 Nov 21 00:36 Female64x64-Q00.jpg
-rw-r--r-- 1 shaos shaos  409 Nov 21 00:36 Female64x64-Q01.jpg
-rw-r--r-- 1 shaos shaos  485 Nov 21 00:35 Female64x64-Q05.jpg
-rw-r--r-- 1 shaos shaos  599 Nov 21 00:35 Female64x64-Q10.jpg
-rw-r--r-- 1 shaos shaos  710 Nov 21 00:35 Female64x64-Q15.jpg
-rw-r--r-- 1 shaos shaos  795 Nov 21 00:35 Female64x64-Q20.jpg
-rw-r--r-- 1 shaos shaos  889 Nov 21 00:34 Female64x64-Q25.jpg
-rw-r--r-- 1 shaos shaos  976 Nov 21 00:34 Female64x64-Q30.jpg
-rw-r--r-- 1 shaos shaos 1044 Nov 21 00:34 Female64x64-Q35.jpg
-rw-r--r-- 1 shaos shaos 1102 Nov 21 00:34 Female64x64-Q40.jpg
-rw-r--r-- 1 shaos shaos 1162 Nov 21 00:34 Female64x64-Q45.jpg
-rw-r--r-- 1 shaos shaos 1215 Nov 21 00:33 Female64x64-Q50.jpg
-rw-r--r-- 1 shaos shaos 1275 Nov 21 00:33 Female64x64-Q55.jpg
-rw-r--r-- 1 shaos shaos 1337 Nov 21 00:33 Female64x64-Q60.jpg
-rw-r--r-- 1 shaos shaos 1436 Nov 21 00:33 Female64x64-Q65.jpg
-rw-r--r-- 1 shaos shaos 1541 Nov 21 00:32 Female64x64-Q70.jpg
-rw-r--r-- 1 shaos shaos 1666 Nov 21 00:32 Female64x64-Q75.jpg
-rw-r--r-- 1 shaos shaos 1854 Nov 21 00:32 Female64x64-Q80.jpg
-rw-r--r-- 1 shaos shaos 2123 Nov 21 00:31 Female64x64-Q85.jpg
-rw-r--r-- 1 shaos shaos 2196 Nov 21 00:47 Female64x64-Q86.jpg
-rw-r--r-- 1 shaos shaos 2267 Nov 21 00:47 Female64x64-Q87.jpg
-rw-r--r-- 1 shaos shaos 2376 Nov 21 00:47 Female64x64-Q88.jpg
-rw-r--r-- 1 shaos shaos 2459 Nov 21 00:47 Female64x64-Q89.jpg
-rw-r--r-- 1 shaos shaos 2588 Nov 21 00:31 Female64x64-Q90.jpg
-rw-r--r-- 1 shaos shaos 2692 Nov 21 00:45 Female64x64-Q91.jpg
-rw-r--r-- 1 shaos shaos 2818 Nov 21 00:45 Female64x64-Q92.jpg
-rw-r--r-- 1 shaos shaos 2999 Nov 21 00:44 Female64x64-Q93.jpg
-rw-r--r-- 1 shaos shaos 3239 Nov 21 00:44 Female64x64-Q94.jpg
-rw-r--r-- 1 shaos shaos 3525 Nov 21 00:30 Female64x64-Q95.jpg
-rw-r--r-- 1 shaos shaos 4004 Nov 21 00:44 Female64x64-Q96.jpg
-rw-r--r-- 1 shaos shaos 4562 Nov 21 00:44 Female64x64-Q97.jpg
-rw-r--r-- 1 shaos shaos 5395 Nov 21 00:44 Female64x64-Q98.jpg
-rw-r--r-- 1 shaos shaos 6654 Nov 21 00:31 Female64x64-Q99.jpg
-rw-r--r-- 1 shaos shaos 7476 Nov 21 00:29 Female64x64-Q100.jpg

теперь сравним WHI-картинки с сопоставимыми по размеру JPG-ами:

Code: Select all

9bit - 7202 (Q~99) ~ Female64x64-Q100.jpg
7bit - 5568 (Q~91) ~ Female64x64-Q98.jpg
6bit - 4089 (Q-62) ~ Female64x64-Q96.jpg
5bit - 2200 (Q~27) ~ Female64x64-Q86.jpg
4bit - 1110 (Q~12) ~ Female64x64-Q40.jpg

и выглядит так, что JPEG цветную картинку сжимает лучше (точнее упаковывает в тот же размер лучшее качество - потому что subsampling?):

FemaleRGB-JPEG-Q98-vs-WHI-7bit.png

FemaleRGB-JPEG-Q96-vs-WHI-6bit.png

FemaleRGB-JPEG-Q86-vs-WHI-5bit.png

FemaleRGB-JPEG-Q40-vs-WHI-4bit.png

[Shaos]

Такое ощущение, что качество надо задавать не от 0 до 99, а 1,2,3,4,5,6,7,8,9 ибо скачки большие (качество я тут считал как процент оставшихся ненулевых квантованных отсчётов по отношению к количеству ненулевых неквантованных отсчётов коих было порядка 86% в данном конкретном изображении)...

Я придумал как поддержать Q с мелким шагом от 1 до 99

Просто начинаем отбрасывать отсчёты (стартуя с правого-нижнего угла спектра) -1 и +1 пока не доберёмся до нужного процента
Если выкинув все -1 и +1 не добрались до нужного процента, то начинаем выкидывать -2 и +2 и т.д.
По сути квантование это и делает, только очень грубо - сразу помногу, а так мы как бы добавляем мелкую корректировку, чтобы подкрутить процент до желаемого

P.S. Обдумывая будущий адаптивный алгоритм сохранения в формат WHI посохранял красную составляющую вышеразмноженной картинки (FEMALER.BWS) с разными параметрами (ниже K означает коэффициент сжатия, а Q - качество как процент отквантованных ненулевых отсчётов к количеству неквантованных ненулевых отсчётов в непожатом спектре):

Code: Select all

FEMALER | 7bits/sampl | 6bits/sampl | 5bits/sampl |
--------+-------------+-------------+-------------+
   1826 | <<< [0][0] always stored separately     |
    388 | K=3.15 Q=36 | K=4.84 Q=17 | K=8.96 Q=8  |
    346 | K=2.72 Q=49 | K=4.52 Q=22 | K=7.89 Q=8  |
    283 | K=2.55 Q=49 | K=4.03 Q=28 | K=6.78 Q=12 |
    244 | K=2.13 Q=69 | K=3.37 Q=36 | K=5.96 Q=15 |
    199 | K=2.00 Q=69 | K=3.17 Q=36 | K=4.90 Q=17 |
    157 | K=1.88 Q=69 | K=2.66 Q=49 | K=4.48 Q=22 |
    148 | K=1.83 Q=69 | K=2.62 Q=49 | K=4.10 Q=28 |
    145 | K=1.82 Q=69 | K=2.57 Q=49 | K=4.10 Q=28 |
    125 | K=1.61 Q=99 | K=2.15 Q=69 | K=3.97 Q=28 |
    124 | K=1.60 Q=99 | K=2.15 Q=69 | K=3.38 Q=35 |
    123 | K=1.60 Q=99 | K=2.15 Q=69 | K=3.37 Q=35 |
    119 | K=1.60 Q=99 | K=2.14 Q=69 | K=3.37 Q=35 |
    112 | K=1.59 Q=99 | K=2.11 Q=69 | K=3.29 Q=35 |
    109 | K=1.58 Q=99 | K=2.11 Q=69 | K=3.28 Q=35 |
     97 | K=1.52 Q=99 | K=2.00 Q=69 | K=3.17 Q=35 |
     92 | K=1.51 Q=99 | K=1.99 Q=69 | K=2.76 Q=48 |
     87 | K=1.49 Q=99 | K=1.96 Q=69 | K=2.75 Q=48 |
    ... |....... Q=99 |....... Q=69 |....... Q=48 |
     63 | K=1.29 Q=99 | K=1.61 Q=99 | K=2.52 Q=48 |
    ... |.............|.............|.............|

Левая колонка говорит нам о том, с какого значения начинается квантование (это самое большое квантованное значение - всё что амплитудой больше сохраняется отдельно как есть - я это делаю из-за того, что несколько больших отсчётов обычно "выскочки" по амплитуде и их из квантования лучше исключить, чтобы попусту не размазывали динамический диапазон). Качество Q=99 означает, что все ненулевые отсчёты остались нетронутыми (максимально возможное качество). Как можно видеть, одни и те же значения качества попадаются в разных битностях, но с разным началом квантования - при этом коэффициент сжатия тоже не сильно гуляет и примерно соответствует качеству. Получается, что можно нужное качество найти для разных битностей (подрезав слабые отсчёты как я писал чуть выше), а потом чисто по подсчитанной ошибке (и по итоговому коэффициенту сжатия) автоматически можно решить какие параметры сжатия в итоге выбираются для сохранения итоговой картинки.

P.P.S. Вот раскрасил в разноцветные заливки для пущей понятности:

FEMALER.png

Чтобы сохранить данное изображение вообще без квантования и без отдельного запоминания "выскочек" (за исключением отсчёта [0][0] который всегда положительный, всегда больше всех по амплитуде и всегда сохраняется отдельно), надо выбрать 10 бит/отсчёт т.к. в данном случае надо уметь сохранять -388 и +388, которые упаковываются в 2^9 плюс 1 бит знака, т.е. 10 бит на отсчёт - при 10bits/sample все показатели Q в колонке будут 99 (не пишу 100 т.к. отсчёты после Уолша на самом деле имеют дробную часть, которую я отбрасываю, ну т.е. уже не 100% восстановление, но близкое к тому)...

[Shaos]

К вопросу о том отличаются ли визуально восстановленные картинки скажем для Q=36 в случае 7 битов, 6 битов и 5 битов - да, отличаются:

FemaleR-7bit-Q36-x3.png

FemaleR-6bit-Q36-x3.png

FemaleR-5bit-Q36-x3.png

Именно поэтому нужно ещё ошибку учитывать, которая в данном случае принимает значения 5%, 6% и 7% соответственно (однако 7-битный вариант имеет коэффициент сжатия похуже):

Code: Select all

-rw-r--r-- 1 shaos shaos  945 Nov 22 22:18 FFF.WHI
-rw-r--r-- 1 shaos shaos  880 Nov 22 22:17 FF.WHI
-rw-r--r-- 1 shaos shaos  880 Nov 22 22:15 F.WHI

P.S. Коэффициент сжатия тут получились выше, чем в таблице в предыдущем сообщении, т.к. тут я пользовался методом "Huffman after RLE", а при составлении таблицы вчера я делал "Huffman only", который даёт результаты лучше только для высокой битности когда мало нулей.

P.P.S. Добавил ещё один алгоритм обхода "Boustrophedon Diagonal" - это когда диагональные линии не обрываются, переходя на начало, а идут сначала в одну сторону, потом в другую - оно должно дать чуть лучшую локальность для RLE чем просто Diagonal (хотя пока они выдают идентичные результаты по степени сжатия):

[Shaos]

Я хотел выбирать начало квантования по тому месту, в котором оно более-менее выравнивается - например 3 идущие друг за другом (упорядоченные) абсолютные величины отличаются не более чем на 7% (или 5 единиц? или 2 шага квантования?) - это замечательно работает для вышеприведённой картинки для 7 битов и 6 битов - достаточно ровный блок Q начинается на 125, однако в случае 5 битов почему-то ровный блок качеств начался не с 125, а с 124:




P.S. Если плясать от шагов квантования, то для 7 бит это 1/64 (без учёта знака), для 6 бит - 1/32 и для 5 бит 1/16.
125/64=1.95 (двойной шаг - 3.91) - и 123 отличается от 125 на 2 единицы (полтора шага квантования брать?)
125/32=3.91 (двойной шаг - 7.81 и полуторный - 5.86) - полтора тоже срабатывает
а вот для /16 первый раз оно сработает уже на 157-148-145:

Screenshot from 2023-11-22 23-31-07.png

P.P.S. Вообще надо квантование применять к диапазону -125...+125 - поэтому умножаем на 2...

[Shaos]

Вот раскрасил в разноцветные заливки для пущей понятности:


Чтобы сохранить данное изображение вообще без квантования и без отдельного запоминания "выскочек" (за исключением отсчёта [0][0] который всегда положительный, всегда больше всех по амплитуде и всегда сохраняется отдельно), надо выбрать 10 бит/отсчёт т.к. в данном случае надо уметь сохранять -388 и +388, которые упаковываются в 2^9 плюс 1 бит знака, т.е. 10 бит на отсчёт - при 10bits/sample все показатели Q в колонке будут 99 (не пишу 100 т.к. отсчёты после Уолша на самом деле имеют дробную часть, которую я отбрасываю, ну т.е. уже не 100% восстановление, но близкое к тому)...

Возможно как раз от Q=99 и надо плясать (наплевав на выбор старта исходя из шага квантования и т.д.) - выбираем самую высокую битность (в данном случае 10bits/sample) и там поиск начала квантования НЕ нужен - отсчёты кодируются все как есть (кроме [0][0] который всегда отдельно). Далее отбрасываем низкие по амплитуде отсчёты для достижения нужного Q (если Q=99 то останавливаемся прямо сразу). Далее идём в следующую битность - 9bits/sample и стартуем сначала квантования 255 (в этом случае опять же Q будет 99) и двигаемся вверх, ища самую первую строку, где Q больше либо равна желаемой и начинаем отбрасывать низкие по амплитуде отсчёты там пока не достигнем желаемой Q, далее двигаемся в 8bits/sample и стартуем с уровня 127 и т.д. (совсем до 2bits/sample доходить ненадо ибо количество "выскочек" в формате WHI волюнтаристски ограничено числом 100, включая [0][0], поэтому если 2^(N-1)-1 сидит глубже, чем 100 отсортированных по амплитуде абсолютных значений отсчётов, то стартуем с 99-го и если показатель Q для него уже меньше желаемого, то эту битность даже не рассматриваем). По ходу пьесы сохраняем (запоминаем) все параметры сжатия и выбираем самое сильное для желаемого Q (причём то, для которого показатель ERR не сильно страшный) - вобщем как-то так...