nedoPC.org

Electronics hobbyists community established in 2002
Atom Feed | View unanswered posts | View active topics It is currently 13 Apr 2024 16:39



Reply to topic  [ 65 posts ]  Go to page Previous  1, 2, 3, 4, 5
Создаём подобие JPEG для ретрокомпов (Walsh+Huffman) 
Author Message
Admin
User avatar

Joined: 08 Jan 2003 23:22
Posts: 22498
Location: Silicon Valley
Reply with quote
Shaos wrote:
А по яркости-тёмности картинки можно сделать вывод поглядев на отсчёт спектра [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:
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 бита плюс знак
Ну или даже можно нулевой отсчёт записать в "выскочки" и тогда фиксированной битности вообще не будет использоваться нигде...

_________________
:dj: https://mastodon.social/@Shaos


06 Dec 2023 04:44
Profile WWW
Admin
User avatar

Joined: 08 Jan 2003 23:22
Posts: 22498
Location: Silicon Valley
Reply with quote
Shaos wrote:
shiny wrote:
Shaos wrote:
shiny wrote:
А маркер комментариев поддерживается, или он чуждый классу пользователей?
Кто такой есть маркер комментариев?

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

Не - комментарии лишние :mrgreen:
да, это он - 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 вместо расстановки квадратов в строчку...

_________________
:dj: https://mastodon.social/@Shaos


06 Dec 2023 19:29
Profile WWW
Admin
User avatar

Joined: 08 Jan 2003 23:22
Posts: 22498
Location: Silicon Valley
Reply with quote
Shaos wrote:
Shaos wrote:
Ладно - будет по верхней планке. И поиск можно делать не тупым перебором, а бинарный т.к. коэффициенты сжатия K всегда идут по возрастанию снизу-вверх, а детерминированное качество Q всегда идёт по убыванию снизу-вверх (а вот ошибка нет - она скачет ибо "по нижней планке" ошибка всегда ниже, чем у предыдущей "верхней планки", хотя в пределах одного и того же значения Q ошибка тоже всегда увеличивается снизу-вверх - её придётся подсчитывать на месте уже после выбора точки по которой мы будем работать).

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

FEMALER.BWS Q=80
Code:
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)

Attachment:
FemaleR-Q80-x3.png
FemaleR-Q80-x3.png [ 21.46 KiB | Viewed 16464 times ]


FEMALER.BWS Q=50
Code:
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)

Attachment:
FemaleR-Q50-x3.png
FemaleR-Q50-x3.png [ 21.79 KiB | Viewed 16464 times ]


FEMAILER.BWS Q=25
Code:
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)

Attachment:
FemaleR-Q25-x3.png
FemaleR-Q25-x3.png [ 22.18 KiB | Viewed 16463 times ]


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

_________________
:dj: https://mastodon.social/@Shaos


07 Dec 2023 01:05
Profile WWW
Admin
User avatar

Joined: 08 Jan 2003 23:22
Posts: 22498
Location: Silicon Valley
Reply with quote
Выложил Walsh Explorer v1.0.5 на гитлаб: https://gitlab.com/shaos/graphin/-/tree/main/WALSHEXP
Также приаттачил новый ZIP-архив в первое сообщение этого топика
Основная фича версии 1.0.5 это адаптивный алгоритм создания WHI-файлов:

Attachment:
walshexp_1_0_5_adaptive_x3.png
walshexp_1_0_5_adaptive_x3.png [ 16.04 KiB | Viewed 16310 times ]

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

Attachment:
walshexp_1_0_5_adaptive2_x3.png
walshexp_1_0_5_adaptive2_x3.png [ 22.69 KiB | Viewed 16310 times ]

и имя файла:

Attachment:
walshexp_1_0_5_adaptive3_x3.png
walshexp_1_0_5_adaptive3_x3.png [ 21.44 KiB | Viewed 16310 times ]

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

Attachment:
walshexp_1_0_5_adaptive4_x3.png
walshexp_1_0_5_adaptive4_x3.png [ 22.46 KiB | Viewed 16310 times ]


Новая оценка трудозатрат:
Code:
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 :mrgreen:

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

_________________
:dj: https://mastodon.social/@Shaos


08 Dec 2023 00:22
Profile WWW
Admin
User avatar

Joined: 08 Jan 2003 23:22
Posts: 22498
Location: Silicon Valley
Reply with quote
Ещё раз сравниваю ELAINE сжатую адаптивным WHI-алгоритмом с JPEG (беру близкие по размеру файлы WHI и пишу с каким Q они были сделаны):

Attachment:
WHIvsJPEG.jpg
WHIvsJPEG.jpg [ 526.22 KiB | Viewed 16100 times ]

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

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


Attachments:
WHIvsJPEG.zip [32.62 KiB]
Downloaded 177 times

_________________
:dj: https://mastodon.social/@Shaos
09 Dec 2023 01:14
Profile WWW
Display posts from previous:  Sort by  
Reply to topic   [ 65 posts ]  Go to page Previous  1, 2, 3, 4, 5

Who is online

Users browsing this forum: No registered users and 1 guest


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
Jump to:  
cron
Powered by phpBB® Forum Software © phpBB Group
Designed by ST Software.