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

[Shaos]

А по яркости-тёмности картинки можно сделать вывод поглядев на отсчёт спектра [0][0] - у средне-серых картинок он около 2000. У высветленных картинок он может достигать 3900, а у затемнённых уходить ниже 1000 - я видел значения 789 и даже 245. И как я писал на предыдущей странице, тот алгоритм ошибки, что я использую, занижает ошибку у высветленных изображений и завышает у затемнённых, поэтому полагаться чисто на ошибку наверное не стоит.

Можно теоретически прикинуть значение [0][0] у картинки полностью залитой средней яркостью (32) в квадрате 64х64 - сначала складываем 64 яркости 32 и затем делим на 8 (корень из 64), что даёт 256, затем проходимся в перпендикулярном направлении - в этом случае складываем 64 отсчёта по 256 и снова делим на 8, что даёт 2048 - вот это и есть теоретическая величина отсчёта спектра [0][0] для средне-серого изображения (что вполне соотносится с наблюдениями изложенными выше). Для ярко-белой заливки (63 это максимум) таким же способом получается 4032, а для совсем чёрного (0) очевидно получится 0.

Если мы считаем двухмерного Уолша не в 64х64, а в 16х16, то там цифры будут 512 для средне-серого изображения (в 4 раза меньше, чем в 64х64) и 1008 для ярко-белой заливки (опять же в 4 раза меньше, чем для 64х64) - соответственно если мы будем делать "прогрессивное" восстановление картинки, двигаясь от низких разрешений к высоким, пропуская нечётные степени двойки, то надо будет корректировать отсчёты от предыдущего разрешения умножая их на 4.

P.S. Так как в текущем формате WHT под сохранение отсчёта [0][0] отведено 16 бит, то теоретический предел по размерам получается 1024x1024, которое даст 64512 в [0][0] для ярко-белой картинки. По-идее, если картинка тёмная, то можно и 2048х2048 попробовать сохранять (так то оно хранит log2N в 4 битах, т.е. вплоть до 15, но со стороной 2^15 у нас не полетит 100%).

В версии 2 формата WHI (первые 2 байта таких файлов будут содержать W2) надо будет поднять битность нулевого отсчёта до 18, чтобы сохранять размеры до 4096x4096, плюс знак, чтобы можно было сохранять цветоразностные поля (там будут отрицательные значения наряду с положительными). Ну или сразу 20 со знаком (что даст 8192x8192 для 6-битных изображений или 2048x2048 для 8-битных), причём битность "выскочек" надо будет тоже поднять т.к. сейчас оно кодируется 4 битами, т.е. от 0 до 15, можно конечно использовать 0 заместо 16, но в версии 2 наверное надо использовать сдвинутые значения - скажем сдвинутые на 8:

Code: Select all

0000 -> 8 битов плюс знак
0001 -> 9 битов плюс знак
0010 -> 10 битов плюс знак
0011 -> 11 битов плюс знак
0100 -> 12 битов плюс знак
0101 -> 13 битов плюс знак
0110 -> 14 битов плюс знак
0111 -> 15 битов плюс знак
1000 -> 16 битов плюс знак
1001 -> 17 битов плюс знак
1010 -> 18 битов плюс знак
1011 -> 19 битов плюс знак
1100 -> 20 битов плюс знак
1101 -> 21 бит плюс знак
1110 -> 22 бита плюс знак
1111 -> 23 бита плюс знак

Ну или даже можно нулевой отсчёт записать в "выскочки" и тогда фиксированной битности вообще не будет использоваться нигде...

[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"

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

По идее можно расширить идею - в последовательности квадратов может попадаться секция W0 с комментарием COPYn где n - это порядковый номер уже обработанного квадрата - таким способом уже можно поддержать тайлы (повторяющиеся квадраты по ходу картинки). А в случае MOVIE можно также иметь по ходу дела секции W0 с комментарием SKIP, что значит пропуск квадрата (т.е. на его месте будет просвечивать предыдущее изображение). Для отметки начала следующего кадра можно использовать комментарий FRAME, за которым может идти задержка в мс для отработки стоп-кадра. По сути и квадраты разного размера можно поддержать - например файл может начаться с квадрата 64x64, за которым будут идти 4 квадрата 32x32, что будет означать, что эти 4 меньших квадрата должны составить больший квадрат 64х64 вместо расстановки квадратов в строчку...

[Shaos]

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

Приступаю к реализации алгоритма "по верхней планке", чтобы покрыть факторы качества ниже 90 - для начала надо пройтись по самой первой строчке таблицы, чтобы узнать верхние Q для каждой колонки. Далее находим нижние значения, от которых надо начинать плясать вверх - они вычисляются элементарно - минимально разумная точка это число, которое можно представить указанным количеством бит без квантования (это я уже умею вычислять - см.выше) либо самое нижнее возможное (у меня количество отчётов "выскочек" ограничено 99, поэтому если там в 99-й позиции уже стоит число, которое невозможно представить без искажений данным количеством бит, то танцуем от этого самого числа вверх). Далее бинарным поиском находим точку "по верхней планке" для Q=99 в каждой колонке и далее скачем вверх (опять же бинарным поиском), чтобы найти следующее Q не равное 99 - в таблице для FEMALER приведённой выше за 99 идёт 69 потом 49 потом 36 потом 28 и т.д. По этим цепочкам чисел выбираем самое ближайшее сверху для задаваемого пользователем значения Q (например если пользователь указал Q=50, то выбираем Q=69) и считаем по уже отработанному алгоритму, отбрасывая лишние единички для подгонки Q и перебирая все способы сжатия и все способы обхода матрицы для каждой из колонок (заранее отбросив все колонки, в которых не попадается выбранное значение Q, чтобы не тратить на них вычислительное время), выбирая лучший вариант в колонке и далее выбираем самое лучшее сжатие среди лучших по колонкам...

Фуф - вроде накодил универсальный адаптивный алагоритм как хотел

FEMALER.BWS Q=80

Code: Select all

Q=80 COMPRESS\f80.WHI

Try [1] S=388 B=10 Q=80 (100)
>>> [1] S=388 B=10 Q=80 (100)
$10BIT.WHI S=388 B=10 Q=80 (80) K=1.334 Kmax=1.334 (10) RLE+HUF (11) B.Diag (0010)
Try [4] S=244 B=9 Q=80 (100)
>>> [1] S=388 B=9 Q=80 (100)
$09BIT.WHI S=388 B=9 Q=80 (80) K=1.635 Kmax=1.635 (9) RLE+HUF (11) Diag (01)
Try [9] S=125 B=8 Q=80 (100)
>>> [5] S=199 B=8 Q=80 (100)
>>> [3] S=283 B=8 Q=80 (68)
>>> [4] S=244 B=8 Q=80 (100)
$08BIT.WHI S=244 B=8 Q=80 (80) K=1.747 Kmax=1.747 (8) RLE+HUF (11) Diag (01)
Try [25] S=63 B=7 Q=80 (100)
>>> [13] S=119 B=7 Q=80 (100)
>>> [7] S=148 B=7 Q=80 (68)
>>> [10] S=124 B=7 Q=80 (100)
>>> [8] S=145 B=7 Q=80 (68)
>>> [9] S=125 B=7 Q=80 (100)
$07BIT.WHI S=125 B=7 Q=80 (80) K=1.760 Kmax=1.760 (7) RLE+HUF (11) Diag (01)
Try [82] S=31 B=6 Q=80 (100)
>>> [41] S=46 B=6 Q=80 (100)
>>> [21] S=80 B=6 Q=80 (68)
>>> [31] S=53 B=6 Q=80 (100)
>>> [26] S=62 B=6 Q=80 (100)
>>> [23] S=68 B=6 Q=80 (68)
>>> [24] S=64 B=6 Q=80 (68)
>>> [25] S=63 B=6 Q=80 (100)
$06BIT.WHI S=63 B=6 Q=80 (80) K=1.752 Kmax=1.760 (7) RLE+HUF (11) Diag (01)
Try [99] S=27 B=5 Q=80 (100)
>>> [50] S=42 B=5 Q=80 (68)
>>> [74] S=33 B=5 Q=80 (68)
>>> [86] S=30 B=5 Q=80 (100)
>>> [80] S=32 B=5 Q=80 (68)
>>> [83] S=31 B=5 Q=80 (100)
>>> [81] S=32 B=5 Q=80 (68)
>>> [82] S=31 B=5 Q=80 (100)
$05BIT.WHI S=31 B=5 Q=80 (80) K=1.698 Kmax=1.760 (7) RLE+HUF (11) Diag (01)

Chosen $07BIT.WHI for Q=80 S=125 B=7 K=1.760 (3.410 bpp) RLE+HUF (11) Diag (01)

FemaleR-Q80-x3.png

FEMALER.BWS Q=50

Code: Select all

Q=50 COMPRESS\f50.WHI

Try [1] S=388 B=10 Q=50 (100)
>>> [1] S=388 B=10 Q=50 (100)
$10BIT.WHI S=388 B=10 Q=50 (50) K=1.714 Kmax=1.714 (10) HUF (10) Diag (01)
Try [4] S=244 B=9 Q=50 (100)
>>> [1] S=388 B=9 Q=50 (100)
$09BIT.WHI S=388 B=9 Q=50 (50) K=1.901 Kmax=1.901 (9) HUF (10) Diag (01)
Try [9] S=125 B=8 Q=50 (100)
>>> [1] S=388 B=8 Q=50 (68)
$08BIT.WHI S=388 B=8 Q=50 (50) K=2.485 Kmax=2.485 (8) RLE+HUF (11) Diag (01)
Try [25] S=63 B=7 Q=50 (100)
>>> [13] S=119 B=7 Q=50 (100)
>>> [7] S=148 B=7 Q=50 (68)
>>> [4] S=244 B=7 Q=50 (68)
>>> [2] S=346 B=7 Q=50 (48)
>>> [3] S=283 B=7 Q=50 (48)
$07BIT.WHI S=244 B=7 Q=50 (50) K=2.812 Kmax=2.812 (7) RLE+HUF (11) B.Diag (0010)
Try [82] S=31 B=6 Q=50 (100)
>>> [41] S=46 B=6 Q=50 (100)
>>> [21] S=80 B=6 Q=50 (68)
>>> [11] S=123 B=6 Q=50 (68)
>>> [6] S=157 B=6 Q=50 (48)
>>> [8] S=145 B=6 Q=50 (48)
>>> [9] S=125 B=6 Q=50 (68)
$06BIT.WHI S=125 B=6 Q=50 (50) K=2.843 Kmax=2.843 (6) RLE+HUF (11) B.Diag (0010)
Try [99] S=27 B=5 Q=50 (100)
>>> [50] S=42 B=5 Q=50 (68)
>>> [25] S=63 B=5 Q=50 (48)
>>> [37] S=48 B=5 Q=50 (68)
>>> [31] S=53 B=5 Q=50 (68)
>>> [28] S=60 B=5 Q=50 (68)
>>> [26] S=62 B=5 Q=50 (68)
$05BIT.WHI S=62 B=5 Q=50 (50) K=2.819 Kmax=2.843 (6) RLE+HUF (11) B.Diag (0010)
Try [99] S=27 B=4 Q=50 (68)
>>> [50] S=42 B=4 Q=50 (48)
>>> [74] S=33 B=4 Q=50 (48)
>>> [86] S=30 B=4 Q=50 (68)
>>> [80] S=32 B=4 Q=50 (48)
>>> [83] S=31 B=4 Q=50 (48)
>>> [84] S=31 B=4 Q=50 (48)
>>> [85] S=31 B=4 Q=50 (48)
$04BIT.WHI S=30 B=4 Q=50 (50) K=2.609 Kmax=2.843 (6) RLE+HUF (11) Diag (01)

Chosen $06BIT.WHI for Q=50 S=125 B=6 K=2.843 (2.111 bpp) RLE+HUF (11) B.Diag (0010)

FemaleR-Q50-x3.png

FEMAILER.BWS Q=25

Code: Select all

Q=25 COMPRESS\f25.WHI

Try [1] S=388 B=10 Q=25 (100)
>>> [1] S=388 B=10 Q=25 (100)
$10BIT.WHI S=388 B=10 Q=25 (25) K=2.701 Kmax=2.701 (10) RLE+HUF (11) Morton (0000)
Try [4] S=244 B=9 Q=25 (100)
>>> [1] S=388 B=9 Q=25 (100)
$09BIT.WHI S=388 B=9 Q=25 (25) K=3.055 Kmax=3.055 (9) RLE+HUF (11) Morton (0000)
Try [9] S=125 B=8 Q=25 (100)
>>> [1] S=388 B=8 Q=25 (68)
$08BIT.WHI S=388 B=8 Q=25 (25) K=3.671 Kmax=3.671 (8) RLE+HUF (11) B.Diag (0010)
Try [25] S=63 B=7 Q=25 (100)
>>> [1] S=388 B=7 Q=25 (36)
$07BIT.WHI S=388 B=7 Q=25 (25) K=4.718 Kmax=4.718 (7) RLE+HUF (11) Morton (0000)
Try [82] S=31 B=6 Q=25 (100)
>>> [41] S=46 B=6 Q=25 (100)
>>> [21] S=80 B=6 Q=25 (68)
>>> [11] S=123 B=6 Q=25 (68)
>>> [6] S=157 B=6 Q=25 (48)
>>> [3] S=283 B=6 Q=25 (28)
>>> [2] S=346 B=6 Q=25 (22)
$06BIT.WHI S=283 B=6 Q=25 (25) K=5.144 Kmax=5.144 (6) HUF (10) Diag (01)
Try [99] S=27 B=5 Q=25 (100)
>>> [50] S=42 B=5 Q=25 (68)
>>> [25] S=63 B=5 Q=25 (48)
>>> [13] S=119 B=5 Q=25 (36)
>>> [7] S=148 B=5 Q=25 (28)
>>> [4] S=244 B=5 Q=25 (15)
>>> [5] S=199 B=5 Q=25 (18)
>>> [6] S=157 B=5 Q=25 (22)
$05BIT.WHI S=148 B=5 Q=25 (25) K=5.322 Kmax=5.322 (5) HUF (10) B.Diag (0010)
Try [99] S=27 B=4 Q=25 (68)
>>> [50] S=42 B=4 Q=25 (48)
>>> [25] S=63 B=4 Q=25 (28)
>>> [13] S=119 B=4 Q=25 (15)
>>> [19] S=85 B=4 Q=25 (22)
>>> [22] S=75 B=4 Q=25 (28)
>>> [20] S=84 B=4 Q=25 (22)
>>> [21] S=80 B=4 Q=25 (22)
$04BIT.WHI S=75 B=4 Q=25 (25) K=5.249 Kmax=5.322 (5) HUF (10) B.Diag (0010)
Try [99] S=27 B=3 Q=25 (36)
>>> [50] S=42 B=3 Q=25 (22)
>>> [74] S=33 B=3 Q=25 (28)
>>> [62] S=37 B=3 Q=25 (22)
>>> [68] S=34 B=3 Q=25 (28)
>>> [65] S=36 B=3 Q=25 (22)
>>> [66] S=35 B=3 Q=25 (28)
$03BIT.WHI S=35 B=3 Q=25 (25) K=4.682 Kmax=5.322 (5) HUF (10) B.Diag (0010)

Chosen $05BIT.WHI for Q=25 S=148 B=5 K=5.322 (1.127 bpp) HUF (10) B.Diag (0010)

FemaleR-Q25-x3.png

P.S. Алгоритм "по верхней планке" полностью игнорирует ошибку при сравнении результата и оригинала просто беря самое сильное сжатие с указанным количеством ненулевых отсчётов, что даёт не самую лучшую картинку на выходе - тут как бы надо выбирать, либо картинка получше, либо сжатие посильнее и пока я выбираю сжатие...

[Shaos]

Выложил Walsh Explorer v1.0.5 на гитлаб: https://gitlab.com/shaos/graphin/-/tree/main/WALSHEXP
Также приаттачил новый ZIP-архив в первое сообщение этого топика
Основная фича версии 1.0.5 это адаптивный алгоритм создания WHI-файлов:

walshexp_1_0_5_adaptive_x3.png

он просит задать качество от 1 до 99:

walshexp_1_0_5_adaptive2_x3.png

и имя файла:

walshexp_1_0_5_adaptive3_x3.png

после этого будет сгенерён оптимальный WHI-файл:

walshexp_1_0_5_adaptive4_x3.png

Новая оценка трудозатрат:

Code: Select all

Total Physical Source Lines of Code (SLOC)                = 4,146
Development Effort Estimate, Person-Years (Person-Months) = 0.89 (10.68)
 (Basic COCOMO model, Person-Months = 2.4 * (KSLOC**1.05))
Schedule Estimate, Years (Months)                         = 0.51 (6.15)
 (Basic COCOMO model, Months = 2.5 * (person-months**0.38))
Estimated Average Number of Developers (Effort/Schedule)  = 1.74
Total Estimated Cost to Develop                           = $ 120,269
 (average salary = $56,286/year, overhead = 2.40).
SLOCCount, Copyright (C) 2001-2004 David A. Wheeler
SLOCCount is Open Source Software/Free Software, licensed under the GNU GPL.
SLOCCount comes with ABSOLUTELY NO WARRANTY, and you are welcome to
redistribute it under certain conditions as specified by the GNU GPL license;
see the documentation for details.
Please credit this data as "generated using David A. Wheeler's 'SLOCCount'."

по сравнению с предыдущей оценкой от 11 ноября добавилось 3 с лишним человеко-месяца работы в итоге стоимость разработки возросла с $83K до $120K

P.S. По состоянию на 1996 год там было 3,187 строк, т.е. я тысячу строк примерно добавил за последний месяц...

[Shaos]

Ещё раз сравниваю ELAINE сжатую адаптивным WHI-алгоритмом с JPEG (беру близкие по размеру файлы WHI и пишу с каким Q они были сделаны):

WHIvsJPEG.jpg

Субъективно WHI для этой картинки в градациях серого выглядит немного лучше, чем JPEG с похожей степенью сжатия по-моему

P.S. Приаттачиваю архив с файлами картинок ELAINE в форматах PNG,BWS,WHI и JPG, если кто хочет сам проверить...