nedoPC.org

Electronics hobbyists community established in 2002
Atom Feed | View unanswered posts | View active topics It is currently 27 Feb 2024 02:13



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

Joined: 08 Jan 2003 23:22
Posts: 22231
Location: Silicon Valley
Reply with quote
Shaos wrote:
Shaos wrote:
(таблица Хаффмана в WHI смешивает в месте квантованные отсчёты и метки последовательностей нулей разной длины, представляя их как разные литералы)
Прикинул тут 2 варанта (ELAINE02 и ELAINE04) с RLE и без RLE и чото получается, что просто кодирование символов по частоте (голый Хаффман) даёт результаты лучше, чем Хаффман поверх RLE (когда нули собраны с спец.символы по количеству подряд идущих и замешаны с сэмплами в общем алфавите как в примерах выше) - наверное надо добавить как опцию возможность делать и так, и эдак (и потом в адаптивном алгоритме реализовать всё с выбором лучшего):
Code:
11 - Huffman after RLE
10 - Huffman only
01 - RLE only
00 - Raw data
(последний вариант это голые квантованные данные чисто чтобы было)

Но отбрасывание хвостовых нулей я оставлю для всех вариантов т.к. их наличие уж точно ничего не даёт, а просто расходует попусту пространство (хотя с другой стороны, в случае отбрасывания нулей приходится заводить отдельный символ, означающий конец последовательности).
При квантовании одно из значений будет отводится под маркер конца цепочки сэмплов - например при указании 2 бит на сэмпл у нас получаются 4 разных значения:
Code:
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-мя (либо ближайшим к ним смещённым значением)...

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


08 Nov 2023 01:38
Profile WWW
Admin
User avatar

Joined: 08 Jan 2003 23:22
Posts: 22231
Location: Silicon Valley
Reply with quote
Shaos wrote:
выходит ELAINE02.WHI будет не 175 байт длиной, а уже 151, что даёт сжатие в 20.4 раза вместо озвученных выше 17.7 :o
Даже меньше получилось - 146 байт, что даёт сжатие в 21.2 раза :lol:

Attachment:
WHIvsJPEG.jpg
WHIvsJPEG.jpg [ 385 KiB | Viewed 6305 times ]

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

Attachment:
walshexp_031.png
walshexp_031.png [ 9.11 KiB | Viewed 6305 times ]


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

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


10 Nov 2023 04:39
Profile WWW
Admin
User avatar

Joined: 08 Jan 2003 23:22
Posts: 22231
Location: Silicon Valley
Reply with quote
А теперь поговорим о квантовании - с 1996 года у меня реализован следующий алгоритм: из указанного количества битов убирается один бит, который отводится под знак, оставшиеся биты (N) используются для вычисления коэффициента, на который будут умножаться квантованные отсчёты для получения восстановленного отсчёта для дальнейшего пропускания его через обратное преобразование Уолша для восстановления ( и кстати обратное преобразование Уолша абсолютно идентично прямому : ) - коэффициент получался путём деления асболютного максимума (без знака) на 2^N (деление производится с плавающей точкой двойной точности), при этом диапазон от -AbsMax до +AbsMax делится на зоны следующий образом (показано для случае 3-битного квантования, когда 1 бит уходит на знак и оставшиеся N=2 используются для кодирования абсолютной величины отсчёта) - описанный вариант соответствует левой картинке:

Attachment:
Quantization.jpg
Quantization.jpg [ 81.63 KiB | Viewed 6245 times ]

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

Attachment:
WHIvsJPEG.jpg
WHIvsJPEG.jpg [ 379.41 KiB | Viewed 6245 times ]

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

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


10 Nov 2023 19:22
Profile WWW
Admin
User avatar

Joined: 08 Jan 2003 23:22
Posts: 22231
Location: Silicon Valley
Reply with quote


Заимплементил запись всех четырёх алгритмов (но чтение пока только для 2 - допиливаю остальное) - вот ELAINE с 5-битным квантованием (файлы расположены по убыванию размера):
Code:
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%) - разница только в размерах...

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


11 Nov 2023 02:47
Profile WWW
Admin
User avatar

Joined: 08 Jan 2003 23:22
Posts: 22231
Location: Silicon Valley
Reply with quote
Всё - сделал чтение и выложил как часть репозитория GRAPHIN :lol:

https://gitlab.com/shaos/graphin

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

Attachment:
ElaineComparison.jpg
ElaineComparison.jpg [ 41.97 KiB | Viewed 6161 times ]

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

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


11 Nov 2023 04:49
Profile WWW
Admin
User avatar

Joined: 08 Jan 2003 23:22
Posts: 22231
Location: Silicon Valley
Reply with quote
Посчитал строки кода:
Code:
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 денег :mrgreen:

P.S. Кстати в те времена когда писался этот код, я использовал очень компактный способ написания C++ программ :)
Code:
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х ;)

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


11 Nov 2023 14:37
Profile WWW
Admin
User avatar

Joined: 08 Jan 2003 23:22
Posts: 22231
Location: Silicon Valley
Reply with quote
Shaos wrote:
Shaos wrote:
Между прочим не всегда спектр Уолша выглядит как непонятное облако - вот например интересный вариант:

Image

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

Image

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

Attachment:
walshexp_049.png
walshexp_049.png [ 7.75 KiB | Viewed 6150 times ]


Attachment:
walshexp_048.png
walshexp_048.png [ 2.93 KiB | Viewed 6150 times ]


Attachment:
walshexp_047.png
walshexp_047.png [ 3.14 KiB | Viewed 6150 times ]


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

Image

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


11 Nov 2023 22:13
Profile WWW
Admin
User avatar

Joined: 08 Jan 2003 23:22
Posts: 22231
Location: Silicon Valley
Reply with quote
А теперь порешаем интересный вопрос - если мы вводим произвольный размер картинок, то надо быть готовым к тому, что наши квадратики будут обрезаться где не попадя - а именно справа или снизу (т.к. слева и сверху они очевидно будут выровнены по левому и верхнему краям) и надо понять что делать с закрытыми краями, чтобы сжатие занимало как можно меньше места. Очевидные варианты, который приходят в голову:
0. закрашиваем край чёрным
1. закрашиваем край белым
2. копируем туда копию того что остаётся видимым
3. копируем туда зеркальную копию того что остаётся видимым
Соответственно вот такие спектры Уолша у нас получаются для вышеописанных вариантов - для обрезания справа:
Attachment:
half0v.png
half0v.png [ 5.6 KiB | Viewed 6147 times ]

Attachment:
half1v.png
half1v.png [ 5.69 KiB | Viewed 6147 times ]

Attachment:
half2v.png
half2v.png [ 7.88 KiB | Viewed 6147 times ]

Attachment:
half3v.png
half3v.png [ 8.02 KiB | Viewed 6147 times ]

И для обрезания снизу:
Attachment:
half0h.png
half0h.png [ 6.1 KiB | Viewed 6147 times ]

Attachment:
half1h.png
half1h.png [ 6.17 KiB | Viewed 6147 times ]

Attachment:
half2h.png
half2h.png [ 6.94 KiB | Viewed 6147 times ]

Attachment:
half3h.png
half3h.png [ 7.23 KiB | Viewed 6147 times ]

А теперь выясним, какие из этих вариантов лучше всего сжимаются в WHI, если выбирать 6-битное квантование и разные варианты обхода (в названиях файлов они отражаются так - диагональный без дополнительного суффикса, горизонтальный - дополнительный суффикс H, вертикальный - дополнительный суффикс V):
Code:
-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, то заливка одним уровнем отрезаемого ПОМОГАЕТ - по размеру выходит как повторяющиеся половинки:
Attachment:
walshexp_058.png
walshexp_058.png [ 3.82 KiB | Viewed 6115 times ]
(наверное копирование одного и того же куска 4 раза поможет ещё больше)

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




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


11 Nov 2023 23:57
Profile WWW
Admin
User avatar

Joined: 08 Jan 2003 23:22
Posts: 22231
Location: Silicon Valley
Reply with quote
Shaos wrote:
Если же кусать 3/4, то заливка одним уровнем отрезаемого ПОМОГАЕТ - по размеру выходит как повторяющиеся половинки:

Image

(наверное копирование одного и того же куска 4 раза поможет ещё больше)
и точно:
Attachment:
walshexp_059.png
walshexp_059.png [ 5.52 KiB | Viewed 6112 times ]

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

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

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

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


12 Nov 2023 02:47
Profile WWW
Online
Fanat

Joined: 14 Oct 2023 06:59
Posts: 77
Reply with quote
Я что-то упустил или нет - артефакты jpg будут?


12 Nov 2023 07:26
Profile
Admin
User avatar

Joined: 08 Jan 2003 23:22
Posts: 22231
Location: Silicon Valley
Reply with quote
shiny wrote:
Я что-то упустил или нет - артефакты jpg будут?
Нет

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

Attachment:
walshexp_buck3.png
walshexp_buck3.png [ 20.61 KiB | Viewed 6037 times ]


Attachment:
walshexp_text3.png
walshexp_text3.png [ 26.17 KiB | Viewed 6019 times ]


P.S. Размеры файлов для последнего случая (отсортированы по убыванию):
Code:
-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 байт):

Attachment:
walshexp_text2.png
walshexp_text2.png [ 24.84 KiB | Viewed 6019 times ]

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


12 Nov 2023 12:43
Profile WWW
Admin
User avatar

Joined: 08 Jan 2003 23:22
Posts: 22231
Location: Silicon Valley
Reply with quote
Вот тут можно пронаблюдать интересный эффект:



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

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

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

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

Attachment:
Square-Progressive.jpg
Square-Progressive.jpg [ 115.27 KiB | Viewed 5983 times ]

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/

Attachment:
Shells.png
Shells.png [ 55.03 KiB | Viewed 5868 times ]

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


12 Nov 2023 22:21
Profile WWW
Admin
User avatar

Joined: 08 Jan 2003 23:22
Posts: 22231
Location: Silicon Valley
Reply with quote
Мне тут в мастодонте советуют ещё Morton-order попробовать (Z-order):

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

Наверное 00 можно как префикс закодировать, расширив пространство значений до 8 (типа как Хаффман), добавив всё сразу:
Code:
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.. - заглушка на будущее (в меню отсутствует)

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


13 Nov 2023 08:36
Profile WWW
Admin
User avatar

Joined: 08 Jan 2003 23:22
Posts: 22231
Location: Silicon Valley
Reply with quote
Shaos wrote:
Если в картинке всё нарисовано квадратами 2х2, то спектр занимает только левый-верхний квадрант :roll:

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

И делать это надо для всех квадратов одновременно (в будущем ведь мы будем иметь несколько квадратов в пределах одного изображения, которое будет необязательно квадратным, причём для трёх разных каналов - 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) :o

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

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


14 Nov 2023 03:29
Profile WWW
Admin
User avatar

Joined: 08 Jan 2003 23:22
Posts: 22231
Location: Silicon Valley
Reply with quote
Shaos wrote:
Тут формула качества уже примерно такая: 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%).

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


14 Nov 2023 21:09
Profile WWW
Display posts from previous:  Sort by  
Reply to topic   [ 65 posts ]  Go to page Previous  1, 2, 3, 4, 5  Next

Who is online

Users browsing this forum: No registered users and 4 guests


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:  
Powered by phpBB® Forum Software © phpBB Group
Designed by ST Software.