![](http://www.nedopc.org/nedopc/image/nedobanner3.gif) |
nedoPC.orgCommunity for electronics hobbyists, established in 2002 |
![](http://www.nedopc.org/nedopc/image/nedobanner4.gif) |
Last visit was: 31 Aug 2024 19:12
|
It is currently 31 Aug 2024 19:12
|
Создаём подобие JPEG для ретрокомпов (Walsh+Huffman)
Author |
Message |
Shaos
Admin
Joined: 08 Jan 2003 23:22 Posts: 23200 Location: Silicon Valley
|
При квантовании одно из значений будет отводится под маркер конца цепочки сэмплов - например при указании 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-мя (либо ближайшим к ним смещённым значением)...
|
08 Nov 2023 01:38 |
|
![](./styles/getaway/theme/images/spacer.gif) |
Shaos
Admin
Joined: 08 Jan 2003 23:22 Posts: 23200 Location: Silicon Valley
|
Даже меньше получилось - 146 байт, что даёт сжатие в 21.2 раза ![:lol:](./images/smilies/icon_lol.gif) и это "Huffman after RLE" - если сделать голимого Хаффмана, то может быть станет ещё меньше ![:idea:](./images/smilies/icon_yesicon.gif) 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, а во сколько раз надо сжать входное изображение - с этим было бы проще...
You do not have the required permissions to view the files attached to this post.
|
10 Nov 2023 04:39 |
|
![](./styles/getaway/theme/images/spacer.gif) |
Shaos
Admin
Joined: 08 Jan 2003 23:22 Posts: 23200 Location: Silicon Valley
|
А теперь поговорим о квантовании - с 1996 года у меня реализован следующий алгоритм: из указанного количества битов убирается один бит, который отводится под знак, оставшиеся биты (N) используются для вычисления коэффициента, на который будут умножаться квантованные отсчёты для получения восстановленного отсчёта для дальнейшего пропускания его через обратное преобразование Уолша для восстановления ( и кстати обратное преобразование Уолша абсолютно идентично прямому : ) - коэффициент получался путём деления асболютного максимума (без знака) на 2^N (деление производится с плавающей точкой двойной точности), при этом диапазон от -AbsMax до +AbsMax делится на зоны следующий образом (показано для случае 3-битного квантования, когда 1 бит уходит на знак и оставшиеся N=2 используются для кодирования абсолютной величины отсчёта) - описанный вариант соответствует левой картинке: При большой битности наверное не играет особой роли как мы делим этот отрезок, однако в случае малой битности начинаются проблемы - как можно видеть зоны у максимумов непропорционально много кодируются кодом 11, что может привести к искажениям. Вчера я попробовал вариант, что нарисован по середине, когда абсолютный максимум делится не на 2^N, а на 2^N-1 - в этом случае наоборот в районе максимумов код 11 захватывает непропорционально мало отсчётов и т.к. зона 00 стала шире оно привело к выкидыванию большего количества отсчётов со значениями близкими к нулю, что привело к большим квадратам и визуально более худшему восстановлению картинки при той же битности. Теперь я решил попробовать вариант с разделением на 2^N-1/2 (картинка справа), который выглядит пропорционально и по-моему получилось лучше ![:roll:](./images/smilies/icon_rolleyes.gif) Тут формула качества уже примерно такая: Q=100-E*4.5
You do not have the required permissions to view the files attached to this post.
|
10 Nov 2023 19:22 |
|
![](./styles/getaway/theme/images/spacer.gif) |
Shaos
Admin
Joined: 08 Jan 2003 23:22 Posts: 23200 Location: Silicon Valley
|
![](http://www.nedopc.org/forum/download/file.php?id=13219) Заимплементил запись всех четырёх алгритмов (но чтение пока только для 2 - допиливаю остальное) - вот ELAINE с 5-битным квантованием (файлы расположены по убыванию размера): Визуально они идентичны (58% ненулевых отсчётов, ошибка 5%) - разница только в размерах...
|
11 Nov 2023 02:47 |
|
![](./styles/getaway/theme/images/spacer.gif) |
Shaos
Admin
Joined: 08 Jan 2003 23:22 Posts: 23200 Location: Silicon Valley
|
Всё - сделал чтение и выложил как часть репозитория GRAPHIN https://gitlab.com/shaos/graphinВот такие размеры получаются для ELAINE при разных методах сжатия и разной битности: Как можно видеть при малой битности Хаффман после RLE выглядит лучше (и даже чисто RLE не плох), однако при большой битности чисто Хаффман показывает чуть лучшие результаты...
You do not have the required permissions to view the files attached to this post.
|
11 Nov 2023 04:49 |
|
![](./styles/getaway/theme/images/spacer.gif) |
Shaos
Admin
Joined: 08 Jan 2003 23:22 Posts: 23200 Location: Silicon Valley
|
Посчитал строки кода: sloccount оценил мою работу в 7 с лишним человеко-месяцев и $83K денег ![mrgreen :mrgreen:](./images/smilies/icon_mrgreen.gif) P.S. Кстати в те времена когда писался этот код, я использовал очень компактный способ написания C++ программ ![:)](./images/smilies/icon_smile.gif) И сейчас когда начал добавлять и исправлять невольно продолжил этот "coding standard" от Шаоса образца середины 90х ![;)](./images/smilies/icon_wink.gif)
|
11 Nov 2023 14:37 |
|
![](./styles/getaway/theme/images/spacer.gif) |
Shaos
Admin
Joined: 08 Jan 2003 23:22 Posts: 23200 Location: Silicon Valley
|
Вот остальные спектры из этой же серии: Напомню, что это я про вот это: ![Image](http://www.nedopc.org/forum/download/file.php?id=13178)
You do not have the required permissions to view the files attached to this post.
|
11 Nov 2023 22:13 |
|
![](./styles/getaway/theme/images/spacer.gif) |
Shaos
Admin
Joined: 08 Jan 2003 23:22 Posts: 23200 Location: Silicon Valley
|
А теперь порешаем интересный вопрос - если мы вводим произвольный размер картинок, то надо быть готовым к тому, что наши квадратики будут обрезаться где не попадя - а именно справа или снизу (т.к. слева и сверху они очевидно будут выровнены по левому и верхнему краям) и надо понять что делать с закрытыми краями, чтобы сжатие занимало как можно меньше места. Очевидные варианты, который приходят в голову: 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 на картинках внизу) ![:oops:](./images/smilies/icon_redface.gif) ![](http://www.nedopc.org/forum/download/file.php?id=13229) ![](http://www.nedopc.org/forum/download/file.php?id=13228)
You do not have the required permissions to view the files attached to this post.
|
11 Nov 2023 23:57 |
|
![](./styles/getaway/theme/images/spacer.gif) |
Shaos
Admin
Joined: 08 Jan 2003 23:22 Posts: 23200 Location: Silicon Valley
|
и точно: Размер WHI-файла с такими же параметрами сжатия всего 534 байта ![:o](./images/smilies/icon_eek.gif) Вобщем тогда алгоритм такой - если режем половину, тогда повторяем картинку в мёртвой половине из живой половины, а если четверть (откусывая 3/4) то повторяем живой кусочек 4 раза (и т.д. в случае выживших 1/8, 1/16 и т.д.). Если же с краю отрезается меньше половины, то тут ничего не поможет - просто заливаем мёртвый кусочек чем-то одинаковым (например белым). P.S. Для тех, кто не дружит с GitLab (точнее для тех, с кем GitLab не дружит) приаттачиваю архив с Walsh Explorer v1.0.1 и исходниками к первому сообщению этого топика ![:roll:](./images/smilies/icon_rolleyes.gif)
You do not have the required permissions to view the files attached to this post.
|
12 Nov 2023 02:47 |
|
![](./styles/getaway/theme/images/spacer.gif) |
shiny
Maniac
Joined: 14 Oct 2023 06:59 Posts: 232
|
Я что-то упустил или нет - артефакты jpg будут?
_________________ uselessretro.blogspot.com
|
12 Nov 2023 07:26 |
|
![](./styles/getaway/theme/images/spacer.gif) |
Shaos
Admin
Joined: 08 Jan 2003 23:22 Posts: 23200 Location: Silicon Valley
|
Нет Тут заместо артефактов - цифровой шум: P.S. Размеры файлов для последнего случая (отсортированы по убыванию): P.P.S. Вот для сравнения 2-битный Huffman after RLE с горизонтальным обходом той же самой картинки (размер файла получился всего 168 байт):
You do not have the required permissions to view the files attached to this post.
|
12 Nov 2023 12:43 |
|
![](./styles/getaway/theme/images/spacer.gif) |
Shaos
Admin
Joined: 08 Jan 2003 23:22 Posts: 23200 Location: Silicon Valley
|
Вот тут можно пронаблюдать интересный эффект: ![](http://www.nedopc.org/forum/download/file.php?id=13227) Если в картинке всё нарисовано квадратами 2х2, то спектр занимает только левый-верхний квадрант Получается, что можно таким образом иметь сжатое изображение низкого разрешения, а потом "слоями" добавлять высокое просто докидывая в спектр дополнительные квадранты и есть возможность остановиться в любой момент, когда достигли нужного разрешения! ![surprised :esurprised:](./images/smilies/icon_e_surprised.gif) И делать это надо для всех квадратов одновременно (в будущем ведь мы будем иметь несколько квадратов в пределах одного изображения, которое будет необязательно квадратным, причём для трёх разных каналов - 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/
You do not have the required permissions to view the files attached to this post.
|
12 Nov 2023 22:21 |
|
![](./styles/getaway/theme/images/spacer.gif) |
Shaos
Admin
Joined: 08 Jan 2003 23:22 Posts: 23200 Location: Silicon Valley
|
Мне тут в мастодонте советуют ещё 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.. - заглушка на будущее (в меню отсутствует)
|
13 Nov 2023 08:36 |
|
![](./styles/getaway/theme/images/spacer.gif) |
Shaos
Admin
Joined: 08 Jan 2003 23:22 Posts: 23200 Location: Silicon Valley
|
Можно не каждую степень двойки брать начиная с 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. На самом деле в двухмерном преобразовании Уолша умножение на коэффициент происходит дважды и соответственно два корня превращаются в само число т.е. все коэффициенты в результате будут целочисленными в знаменателе...
|
14 Nov 2023 03:29 |
|
![](./styles/getaway/theme/images/spacer.gif) |
Shaos
Admin
Joined: 08 Jan 2003 23:22 Posts: 23200 Location: Silicon Valley
|
Наверное на самом деле всё проще - качество восстанавливаемой картинки впрямую коррелирует с количеством ненулевых отсчётов в квантованном спектре - чем их меньше, тем качество картинки хуже и процент таковых примерно равен проценту качества 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%).
|
14 Nov 2023 21:09 |
|
Who is online |
Users browsing this forum: Claude AI [Bot] and 3 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
|
|