nedoPC.org

При квантовании одно из значений будет отводится под маркер конца цепочки сэмплов - например при указании 2 бит на сэмпл у нас получаются 4 разных значения:

Спецсимвол с идущими следом 6 битами может использоваться для кодирования последовательности нулей (RLE) как в старом формате .IC1, а также для обозначения конца цепочки:
10 xxxxxx где
xxxxxx=000000 кодирует 64 нуля
xxxxxx=000001 кодирует маркер конца
xxxxxx=000010 кодирует 2 нуля (если оно короче, чем 2 нуля по отдельности)
xxxxxx=000011 кодирует 3 нуля
...
xxxxxx=111111 кодирует 63 нуля

В случае голого Хаффмана спецсимвол будет использоваться сам по себе как маркер конца

В случае Хаффмана после RLE весь диапазон будет сдвигаться, чтобы включить в себя разные последовательности нулей как отдельные символы - для этого будет использоваться максимальное значение при кодировании без учёта знака - для 2 битов это 1, для 3 битов это 3, для 4 битов - 7 и т.д. Вот так раскидываем для "2 битов":
00..00 - сдвинутое значение -1
00..01 - маркер конца (т.к. ноль сам по себе не может попасться)
00..10 - сдвинутое значение +1
00..11 - отсюда и далее идут последовательности нулей от 1 до N (битность символов выбирается исходя из максимального значения N)
...
11..11 - теоретический предел
N можно также ограничить сверху, чтобы битность символов в таблице не уходило сильно в сторону - скажем теми же 64-мя (либо ближайшим к ним смещённым значением)...

Даже меньше получилось - 146 байт, что даёт сжатие в 21.2 раза


и это "Huffman after RLE" - если сделать голимого Хаффмана, то может быть станет ещё меньше



P.S. По качеству получается примерно так:
JPEG качество 90 примерно соответствует ошибке 3%
JPEG качество 80 примерно соответствует ошибке 5%
JPEG качество 60 примерно соответствует ошибке 8%
JPEG качество 40 примерно соответствует ошибке 13%
JPEG качество 20 примерно соответствует ошибке 19%
т.е. примерно Q=100-E*4 - это мне нужно для адаптивного алгоритма, когда оно само все параметры подберёт по требуемому качеству (но с этой моей ошибкой, как я писал раньше, есть проблемы - слишком светлые картинки занижают ошибку, а слишком тёмные - завышают).

P.P.S. Ну или от пользователя принимать не качество от 0 до 99, а во сколько раз надо сжать входное изображение - с этим было бы проще...

А теперь поговорим о квантовании - с 1996 года у меня реализован следующий алгоритм: из указанного количества битов убирается один бит, который отводится под знак, оставшиеся биты (N) используются для вычисления коэффициента, на который будут умножаться квантованные отсчёты для получения восстановленного отсчёта для дальнейшего пропускания его через обратное преобразование Уолша для восстановления ( и кстати обратное преобразование Уолша абсолютно идентично прямому : ) - коэффициент получался путём деления асболютного максимума (без знака) на 2^N (деление производится с плавающей точкой двойной точности), при этом диапазон от -AbsMax до +AbsMax делится на зоны следующий образом (показано для случае 3-битного квантования, когда 1 бит уходит на знак и оставшиеся N=2 используются для кодирования абсолютной величины отсчёта) - описанный вариант соответствует левой картинке:


При большой битности наверное не играет особой роли как мы делим этот отрезок, однако в случае малой битности начинаются проблемы - как можно видеть зоны у максимумов непропорционально много кодируются кодом 11, что может привести к искажениям. Вчера я попробовал вариант, что нарисован по середине, когда абсолютный максимум делится не на 2^N, а на 2^N-1 - в этом случае наоборот в районе максимумов код 11 захватывает непропорционально мало отсчётов и т.к. зона 00 стала шире оно привело к выкидыванию большего количества отсчётов со значениями близкими к нулю, что привело к большим квадратам и визуально более худшему восстановлению картинки при той же битности. Теперь я решил попробовать вариант с разделением на 2^N-1/2 (картинка справа), который выглядит пропорционально и по-моему получилось лучше


Тут формула качества уже примерно такая: Q=100-E*4.5

Заимплементил запись всех четырёх алгритмов (но чтение пока только для 2 - допиливаю остальное) - вот ELAINE с 5-битным квантованием (файлы расположены по убыванию размера):
Визуально они идентичны (58% ненулевых отсчётов, ошибка 5%) - разница только в размерах...

Всё - сделал чтение и выложил как часть репозитория GRAPHIN

https://gitlab.com/shaos/graphin

Вот такие размеры получаются для ELAINE при разных методах сжатия и разной битности:


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

Посчитал строки кода:
sloccount оценил мою работу в 7 с лишним человеко-месяцев и $83K денег

P.S. Кстати в те времена когда писался этот код, я использовал очень компактный способ написания C++ программ
И сейчас когда начал добавлять и исправлять невольно продолжил этот "coding standard" от Шаоса образца середины 90х

Вот остальные спектры из этой же серии:







Напомню, что это я про вот это:

А теперь порешаем интересный вопрос - если мы вводим произвольный размер картинок, то надо быть готовым к тому, что наши квадратики будут обрезаться где не попадя - а именно справа или снизу (т.к. слева и сверху они очевидно будут выровнены по левому и верхнему краям) и надо понять что делать с закрытыми краями, чтобы сжатие занимало как можно меньше места. Очевидные варианты, который приходят в голову:
0. закрашиваем край чёрным
1. закрашиваем край белым
2. копируем туда копию того что остаётся видимым
3. копируем туда зеркальную копию того что остаётся видимым
Соответственно вот такие спектры Уолша у нас получаются для вышеописанных вариантов - для обрезания справа:




И для обрезания снизу:




А теперь выясним, какие из этих вариантов лучше всего сжимаются в WHI, если выбирать 6-битное квантование и разные варианты обхода (в названиях файлов они отражаются так - диагональный без дополнительного суффикса, горизонтальный - дополнительный суффикс H, вертикальный - дополнительный суффикс V):
Как можно видеть краевая картинка справа (вертикальный отрез) лучше сжимается, если в скрытой части сидит копия видимой части и обход идёт вертикально (HALF2VV.WHI), и краевая картинка снизу (горизонтальный отрез) лучше сжимается, если в скрытой части сидит копия видимой части, но обход идёт уже горизонтально (HALF2HH.WHI). Зеркальные варианты отстают только на 12 байтов (HALF3VV.WHI и HALF3HH.WHI), а варианты с чёрными или белыми половинами судя по всему сжимаются плохо (причём когда обход идёт "перпендикулярно" отрезу, то сжатие несколько лучше).

P.S. Серую полосу тоже попробовал - результат тот же, что и для белой и чёрной. А вот если режем не ровно по середине, а скажем по четверти, то там при копировании кусков картинки в отрезаемую часть экономии по сжатию не происходит. Если же кусать 3/4, то заливка одним уровнем отрезаемого ПОМОГАЕТ - по размеру выходит как повторяющиеся половинки:
(наверное копирование одного и того же куска 4 раза поможет ещё больше)

P.P.S. Заодно выкатил Walsh Explorer v1.0.1 пофиксив багу, когда WHI ломался, если в спектре появляется 2й отсчёт у которого тоже самое значение, что и у [0][0] - это например случается если половина картинки - чёрная (обратите внимание на два числа 1157 и два числа 1052 на картинках внизу)

и точно:

Размер WHI-файла с такими же параметрами сжатия всего 534 байта

Вобщем тогда алгоритм такой - если режем половину, тогда повторяем картинку в мёртвой половине из живой половины, а если четверть (откусывая 3/4) то повторяем живой кусочек 4 раза (и т.д. в случае выживших 1/8, 1/16 и т.д.). Если же с краю отрезается меньше половины, то тут ничего не поможет - просто заливаем мёртвый кусочек чем-то одинаковым (например белым).

P.S. Для тех, кто не дружит с GitLab (точнее для тех, с кем GitLab не дружит) приаттачиваю архив с Walsh Explorer v1.0.1 и исходниками к первому сообщению этого топика

Я что-то упустил или нет - артефакты jpg будут?

Нет

Тут заместо артефактов - цифровой шум:





P.S. Размеры файлов для последнего случая (отсортированы по убыванию):


P.P.S. Вот для сравнения 2-битный Huffman after RLE с горизонтальным обходом той же самой картинки (размер файла получился всего 168 байт):

Вот тут можно пронаблюдать интересный эффект:



Если в картинке всё нарисовано квадратами 2х2, то спектр занимает только левый-верхний квадрант

Получается, что можно таким образом иметь сжатое изображение низкого разрешения, а потом "слоями" добавлять высокое просто докидывая в спектр дополнительные квадранты и есть возможность остановиться в любой момент, когда достигли нужного разрешения!

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

P.S. Наверное что-то такое надо будет делать не раньше версии 3, а в следующей версии 2 надо просто поддержать прямоугольные изображения произвольных размеров, составленные из квадратов в трёх каналах RGB и плюс добавить ещё один вариант обхода - Squared-Progressive (или как его правильно назвать?):


P.P.S. По идее Square-Progressive можно добавить прямо сейчас т.к. в существующем формате есть четвёртая неиспользуемая комбинация для кодирования метода обхода - 00 (сейчас 01 это диагональный обход, 10 - горизонтальный и 11 - вертикальный). Хотя наверное следует потом ещё добавить Horizontally-Progressive и Vertically-Progressive т.к. существуют изображения, которые сжимаются лучше при горизонтальном или вертикальном обходе спектра.

P.P.P.S. Мне в мастодонте дали наводку на статью, где такой способ обхода называется "in shells” или "gnomons":
https://hbfs.wordpress.com/2018/08/07/moeud-deux/

Мне тут в мастодонте советуют ещё Morton-order попробовать (Z-order):

https://en.wikipedia.org/wiki/Z-order_curve

Наверное 00 можно как префикс закодировать, расширив пространство значений до 8 (типа как Хаффман), добавив всё сразу:


P.S. 22 ноября 2023 года (начиная с v1.0.5) остановился на таком наборе вариантов обхода (в порядке отображения в меню):

01 - Diagonal (usually best)
0000 - Z-order (Morton)
0001 - Boustrophedon Shells
0010 - Boustrophedon Diagonal
10 - Horizontal (raw-major)
11 - Vertical (column-major)
0011.. - заглушка на будущее (в меню отсутствует)

Можно не каждую степень двойки брать начиная с 0, а только те, которые дают целочисленные коэффициенты в знаменателе у преобразования Уолша, а именно:

• 2^2=4 (коэффициент 1/2),
• 2^4=16 (коэффициент 1/4),
• 2^6=64 (коэффициент 1/8),
• 2^8=256 (коэффициент 1/16),
• 2^10=1024 (коэффициент 1/32)
• и даже наверное 2^12=4096 (коэффициент 1/64)

P.S. На самом деле в двухмерном преобразовании Уолша умножение на коэффициент происходит дважды и соответственно два корня превращаются в само число т.е. все коэффициенты в результате будут целочисленными в знаменателе...

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

А по яркости-тёмности картинки можно сделать вывод поглядев на отсчёт спектра [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%).