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

[Shaos]

(таблица Хаффмана в WHI смешивает в месте квантованные отсчёты и метки последовательностей нулей разной длины, представляя их как разные литералы)

Прикинул тут 2 варанта (ELAINE02 и ELAINE04) с RLE и без RLE и чото получается, что просто кодирование символов по частоте (голый Хаффман) даёт результаты лучше, чем Хаффман поверх RLE (когда нули собраны с спец.символы по количеству подряд идущих и замешаны с сэмплами в общем алфавите как в примерах выше) - наверное надо добавить как опцию возможность делать и так, и эдак (и потом в адаптивном алгоритме реализовать всё с выбором лучшего):

Code: Select all

11 - Huffman after RLE
10 - Huffman only
01 - RLE only
00 - Raw data

(последний вариант это голые квантованные данные чисто чтобы было)

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

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

Code: Select all

00 кодирует 0
01 кодирует +1
10 кодирует спецсимвол
11 кодирует -1

Спецсимвол с идущими следом 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-мя (либо ближайшим к ним смещённым значением)...

[Shaos]

выходит ELAINE02.WHI будет не 175 байт длиной, а уже 151, что даёт сжатие в 20.4 раза вместо озвученных выше 17.7

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

WHIvsJPEG.jpg

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

walshexp_031.png

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, а во сколько раз надо сжать входное изображение - с этим было бы проще...

[Shaos]

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

Quantization.jpg

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

WHIvsJPEG.jpg

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

[Shaos]

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

Code: Select all

ELAINE.BWS   3076 - Original (6 bits/pixel)
ELAINE50.WHI 2581 - Raw data
ELAINE51.WHI 2278 - RLE only
ELAINE5.WHI  1333 - Huffman after RLE
ELAINE52.WHI 1308 - Huffman only

Визуально они идентичны (58% ненулевых отсчётов, ошибка 5%) - разница только в размерах...

[Shaos]

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

https://gitlab.com/shaos/graphin

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

ElaineComparison.jpg

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

[Shaos]

Посчитал строки кода:

Code: Select all

Total Physical Source Lines of Code (SLOC)                = 2,909
Development Effort Estimate, Person-Years (Person-Months) = 0.61 (7.36)
 (Basic COCOMO model, Person-Months = 2.4 * (KSLOC**1.05))
Schedule Estimate, Years (Months)                         = 0.44 (5.34)
 (Basic COCOMO model, Months = 2.5 * (person-months**0.38))
Estimated Average Number of Developers (Effort/Schedule)  = 1.38
Total Estimated Cost to Develop                           = $ 82,903
 (average salary = $56,286/year, overhead = 2.40).

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

P.S. Кстати в те времена когда писался этот код, я использовал очень компактный способ написания C++ программ

Code: Select all

int UniHuff::ReadTable(void) // Read table from BitFile
{if(mode!=HUFF_RD) return 0;
 if(subm) return 0;
 char addi[100];
 int i,i2,j;
 Bits b;
 int ver=hfile->Get(2).Ret();
 if(ver>1) return 0; // Wrong version (must be 00 or 01)
 slen=hfile->Get(4).Ret(); // 0..15
 numt=hfile->Get(12).Ret(); // 0..4097
 tabl=new UniHuffR[numt];
 if(tabl==NULL) return 0;
 code=new Bits[numt];
 if(code==NULL) return 0;
 if(ver==1) // read additional info
 { int sadd=hfile->Get(8).Ret();
   for(i=0;i<sadd;i++)
   { j=1;i2=0;
     while(j)
     { j=hfile->Get(7).Ret(); // 7-bit ASCII
       addi[i2++]=j;
       if(i2>=100) return 0; // Can't handle that
     }
     i2=hfile->Get(slen).Ret();
     if(!Add(i2,addi)) return 0;
   }
 }
 nums=0;
 if(!ReadTable(b)) return 0;
 subm=1;
 return nums;
}

И сейчас когда начал добавлять и исправлять невольно продолжил этот "coding standard" от Шаоса образца середины 90х

[Shaos]

Между прочим не всегда спектр Уолша выглядит как непонятное облако - вот например интересный вариант:

Поправил раскрашивание спектра при выводе - теперь зелёные цвета это положительные отсчёты, а красные - отрицательные. И убрал умножение на 2 из-за которого при отрисовке выпячивались маленькие отсчёты, а большие уходили в разноцветную мешанину, т.к. убегали за пределы своих цветовых диапазонов (сейчас зашкал больше +63 даёт белый, а меньше -64 даёт ярко синий):

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

walshexp_049.png

walshexp_048.png

walshexp_047.png

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

[Shaos]

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

half0v.png

half1v.png

half2v.png

half3v.png

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

half0h.png

half1h.png

half2h.png

half3h.png

А теперь выясним, какие из этих вариантов лучше всего сжимаются в WHI, если выбирать 6-битное квантование и разные варианты обхода (в названиях файлов они отражаются так - диагональный без дополнительного суффикса, горизонтальный - дополнительный суффикс H, вертикальный - дополнительный суффикс V):

Code: Select all

-rw-r--r-- 1 shaos shaos 1018 Nov 11 22:28 HALF2VV.WHI
-rw-r--r-- 1 shaos shaos 1030 Nov 11 22:30 HALF3VV.WHI
-rw-r--r-- 1 shaos shaos 1064 Nov 11 22:27 HALF2HH.WHI
-rw-r--r-- 1 shaos shaos 1076 Nov 11 22:29 HALF3HH.WHI
-rw-r--r-- 1 shaos shaos 1249 Nov 11 22:28 HALF2VH.WHI
-rw-r--r-- 1 shaos shaos 1271 Nov 11 22:28 HALF2V.WHI
-rw-r--r-- 1 shaos shaos 1297 Nov 11 22:25 HALF1VH.WHI
-rw-r--r-- 1 shaos shaos 1298 Nov 11 23:09 HALF0VH.WHI
-rw-r--r-- 1 shaos shaos 1299 Nov 11 22:27 HALF2HV.WHI
-rw-r--r-- 1 shaos shaos 1324 Nov 11 22:26 HALF2H.WHI
-rw-r--r-- 1 shaos shaos 1367 Nov 11 23:08 HALF0HV.WHI
-rw-r--r-- 1 shaos shaos 1371 Nov 11 22:24 HALF1HV.WHI
-rw-r--r-- 1 shaos shaos 1380 Nov 11 22:30 HALF3VH.WHI
-rw-r--r-- 1 shaos shaos 1410 Nov 11 22:30 HALF3V.WHI
-rw-r--r-- 1 shaos shaos 1424 Nov 11 22:29 HALF3HV.WHI
-rw-r--r-- 1 shaos shaos 1451 Nov 11 22:29 HALF3H.WHI
-rw-r--r-- 1 shaos shaos 1544 Nov 11 22:25 HALF1VV.WHI
-rw-r--r-- 1 shaos shaos 1545 Nov 11 23:09 HALF0VV.WHI
-rw-r--r-- 1 shaos shaos 1547 Nov 11 22:24 HALF1V.WHI
-rw-r--r-- 1 shaos shaos 1548 Nov 11 23:09 HALF0V.WHI
-rw-r--r-- 1 shaos shaos 1589 Nov 11 22:23 HALF1H.WHI
-rw-r--r-- 1 shaos shaos 1589 Nov 11 23:07 HALF0H.WHI
-rw-r--r-- 1 shaos shaos 1592 Nov 11 22:23 HALF1HH.WHI
-rw-r--r-- 1 shaos shaos 1592 Nov 11 23:08 HALF0HH.WHI
-rw-r--r-- 1 shaos shaos 1791 Nov 11 12:32 ELAINE62.WHI <<< целая картинка сжатая методом "Huffman only"
-rw-r--r-- 1 shaos shaos 1827 Nov 11 12:32 ELAINE6H.WHI <<< целая картинка сжатая "Huffman after RLE" с горизонтальным обходом
-rw-r--r-- 1 shaos shaos 1827 Nov 11 12:32 ELAINE6V.WHI <<< целая картинка сжатая "Huffman after RLE" с вертикальным обходом
-rw-r--r-- 1 shaos shaos 1828 Nov 11 22:15 ELAINE6.WHI <<< целая картинка сжатая "Huffman after RLE" с диагональным обходом
-rw-r--r-- 1 shaos shaos 2966 Nov 11 12:32 ELAINE61.WHI <<< целая картинка сжатая "RLE only"
-rw-r--r-- 1 shaos shaos 3093 Nov 11 12:32 ELAINE60.WHI <<< целая картинка сжатая "Raw data"
-rw-r--r-- 1 shaos shaos 3076 Oct 29 00:34 ELAINE.BWS <<< целая картинка - оригинал

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

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

walshexp_058.png

(наверное копирование одного и того же куска 4 раза поможет ещё больше)

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

[Shaos]

Если же кусать 3/4, то заливка одним уровнем отрезаемого ПОМОГАЕТ - по размеру выходит как повторяющиеся половинки:



(наверное копирование одного и того же куска 4 раза поможет ещё больше)

и точно:

walshexp_059.png

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

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

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

[shiny]

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

[Shaos]

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

Нет

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

walshexp_buck3.png

walshexp_text3.png

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

Code: Select all

-rw-r--r-- 1 shaos shaos  614 Nov 12 13:16 TEXT3H.WHI <<< 3-bit "Huffman after RLE" с горизонтальным обходом
-rw-r--r-- 1 shaos shaos  647 Nov 12 13:16 TEXT3V.WHI <<< 3-bit "Huffman after RLE" с вертикальным обходом
-rw-r--r-- 1 shaos shaos  655 Nov 12 13:15 TEXT3.WHI <<< 3-bit "Huffman after RLE" с диагональным обходом
-rw-r--r-- 1 shaos shaos  708 Nov 12 13:24 TEXT3HHO.WHI <<< 3-bit "Huffman only" с горизонтальным обходом
-rw-r--r-- 1 shaos shaos  748 Nov 12 13:27 TEXT3RLE.WHI <<< 3-bit "RLE only" с горизонтальным обходом
-rw-r--r-- 1 shaos shaos 1543 Nov 12 13:28 TEXT3RAW.WHI <<< 3-bit "Raw data" с горизонтальным обходом
-rw-r--r-- 1 shaos shaos 3076 Nov  1 00:40 TEXT.BWS <<< 6-bit оригинал (на скриншоте слева)

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

walshexp_text2.png

[Shaos]

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

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

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

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

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

Square-Progressive.jpg

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/

Shells.png

[Shaos]

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

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

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

Code: Select all

01 - Diagonal (as right now)
10 - Horizontal (as right now)
11 - Vertical (as right now)
0000 - Z-order (Morton)
0001 - Square-Progressive
0010 - Horizontal-Progressive
0011 - Vertical-Progressive

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.. - заглушка на будущее (в меню отсутствует)

[Shaos]

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

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

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

Можно не каждую степень двойки брать начиная с 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. На самом деле в двухмерном преобразовании Уолша умножение на коэффициент происходит дважды и соответственно два корня превращаются в само число т.е. все коэффициенты в результате будут целочисленными в знаменателе...

[Shaos]

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

Наверное на самом деле всё проще - качество восстанавливаемой картинки впрямую коррелирует с количеством ненулевых отсчётов в квантованном спектре - чем их меньше, тем качество картинки хуже и процент таковых примерно равен проценту качества 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%).