![](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 16:51
|
It is currently 31 Aug 2024 16:51
|
Создаём подобие JPEG для ретрокомпов (Walsh+Huffman)
Author |
Message |
Shaos
Admin
Joined: 08 Jan 2003 23:22 Posts: 23199 Location: Silicon Valley
|
UPDATE: Самые последние исходники под MIT-лицензией всегда можно найти тут: https://gitlab.com/shaos/graphin Приаттачиваю архив с исходниками и досовским EXE-шником Walsh Explorer v1.0.5 от 7 декабря 2023 года прямо сюда:
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- На основе моей дипломной работы 1996 года хочу зарелизить опенсорсную программу "Walsh Explorer" (для начала под DOS), которая поможет создать простой алгоритм сжатия изображений с потерями, способный заменить JPEG на ретрокомпах (т.к. JPEG для них тяжеловат). В этом простом алгоритме вместо DCT будет использоваться преобразование Уолша (Walsh-Hadamard Transform) и далее кодирование по Хаффману (Huffman coding). Предварительные эксперименты тут показали, что пободаться с JPEG нам вполне по силам Отпочковано отсюда: http://www.nedopc.org/forum/viewtopic.php?f=46&t=22127&start=30Вот полное меню для преобразования Уолша: Откуда можно зайти в "Обработку спектра": И выбрать "Просмотр строк спектра" где двигаясь вверх-вниз можно поглядеть глазами как оно выглядит "сбоку": А вот подменю "Квантование спектра": Где можно огрубить отсчёты скажем до 7 бит и получить восстановленное изображение: Надо все эти возможности повторить в нашем новом графическом редакторе ![mrgreen :mrgreen:](./images/smilies/icon_mrgreen.gif) P.S. IC1 это был мой экспериментальный формат сжатия картинок на основе преобразования Уолша - там тоже надо было квантовать отсчёты, но я там в те времена накосячил с памятью и оно падало при попытке прочитать сохранённый файл (починил 30 октября 2023). Ещё в этой программе был формат IC2 (фрактальное сжатие - для него даже отдельный просмотрщик был) и формат IC3 (моё самодельное сжатие сферами) - ни то, ни другое в настоящее время интереса не вызывает. Ещё судя по архиву наработок я пытался Фурье осилить, но видать не осилил ![:roll:](./images/smilies/icon_rolleyes.gif) P.P.S. Между прочим не всегда спектр Уолша выглядит как непонятное облако - вот например интересный вариант: Это я пытался повторить вот этот эксперимент со спектром Фурье (картинка из твиттера):
You do not have the required permissions to view the files attached to this post.
|
26 Oct 2023 09:21 |
|
![](./styles/getaway/theme/images/spacer.gif) |
Shaos
Admin
Joined: 08 Jan 2003 23:22 Posts: 23199 Location: Silicon Valley
|
Мой формат (слева) до Хаффмана по качеству превосходит пережатый JPEG, но по размерам не догоняет - нужен Хаффман: ![Image](http://www.nedopc.org/forum/download/file.php?id=13189) Плюс существующий формат надо несколько обработать напильником: а именно: - Сделать возможным сохранять несколько произвольных отсчётов-выскочек в количестве от 1 до скажем 8 с указанием координат вместо теперешних трёх захардкоденных;
- Сохранять параметры квантования с большей точностью, а не как сейчас с точностью до десятых долей;
- Разрешить несколько способов обхода спектра - по горизонтали, по вертикали и по диагонали;
- Отбрасывать нулевые отсчёты в хвосте спектра для уменьшения размеров получающегося файла;
- Добавить адаптивное сжатие, когда параметры будут выбираться автоматически исходя из указанного показателя качества (от 0 до 100 по аналогии с JPEG) и если Хаффман не помогает уменьшить блок (если таблица получилась слишком большая), то оставлять RLE (как сейчас).
Ну и в дальнейшем хотелось бы перейти от картинок 64х64 к картинкам произвольного размера (скажем до 2048x2048 кодируя всё те же блоки 64х64 быстрым преобразованием Уолша) - расширение такого файла будет скажем .whi (Walsh+Huffman Image), а если оно таки полетит как надо (под DOS и на ретрокомпах типа Спринтера), то вот тогда уже можно перейти к разработке формата TONIC...
|
31 Oct 2023 23:38 |
|
![](./styles/getaway/theme/images/spacer.gif) |
shiny
Maniac
Joined: 14 Oct 2023 06:59 Posts: 232
|
А маркер комментариев поддерживается, или он чуждый классу пользователей?
_________________ uselessretro.blogspot.com
|
02 Nov 2023 06:34 |
|
![](./styles/getaway/theme/images/spacer.gif) |
Shaos
Admin
Joined: 08 Jan 2003 23:22 Posts: 23199 Location: Silicon Valley
|
Кто такой есть маркер комментариев? В смысле как в JPEG? https://habr.com/en/articles/102521/Не - комментарии лишние ![mrgreen :mrgreen:](./images/smilies/icon_mrgreen.gif)
|
02 Nov 2023 06:37 |
|
![](./styles/getaway/theme/images/spacer.gif) |
imsushka
Senior
Joined: 01 Jan 2022 04:34 Posts: 190 Location: USSR, Tashkent
|
а как же хеш, говорящий что это не генерированная ИИ картинка ?
|
02 Nov 2023 07:20 |
|
![](./styles/getaway/theme/images/spacer.gif) |
Shaos
Admin
Joined: 08 Jan 2003 23:22 Posts: 23199 Location: Silicon Valley
|
ну про то чем сгенерирована сжимаемая картинка кодировщик точно знать не знает
|
02 Nov 2023 09:06 |
|
![](./styles/getaway/theme/images/spacer.gif) |
shiny
Maniac
Joined: 14 Oct 2023 06:59 Posts: 232
|
да, это он - COM (FF FE) вообще, если взглянуть на состав картинки, то обнаружится немало мусора ![8)](./images/smilies/icon_cool.gif)
_________________ uselessretro.blogspot.com
|
02 Nov 2023 20:43 |
|
![](./styles/getaway/theme/images/spacer.gif) |
Shaos
Admin
Joined: 08 Jan 2003 23:22 Posts: 23199 Location: Silicon Valley
|
Американизированный вариант программы практически готов ![mrgreen :mrgreen:](./images/smilies/icon_mrgreen.gif) Сама программа будет под GPL или MIT (позже решил, что MIT), а используемые библиотечные классы я скорее всего выкачу как PUBLIC DOMAIN: - BWS.CPP - Black-and-White Screen format (картинки в градациях серого размером до 65535x65535 пикселов с уровнями яркости от 0 до 63);
- BITIO.CPP - BIT Input/Output (побитное чтение и сохранение файлов);
- UNIHUFF.CPP - Huffman coding (чтение и сохранение файлов с кодированием по Хаффману);
- GRAPHIN.CPP - GRAPHical INterface for DOS (пользовательский интерфейс для досовских программ с кнопками и менюшками) - позже решил графина таки оставить копирайтнутым под MIT-лицензией
( они все созданы мной в 1995-1996 годах, даже Хаффман, которого я тогда так никуда и не прикрутил ибо застрял на отладке : ) P.S. Кстати GRAPHIN умеет поддерживать разрешения до 1024x768 Пример под спойлером: 1024x768Правда поддерживает он все эти SVGA режимы через бинарную либу SVGA256.OBJ, которую я где-то оттопырил в 1995 году: О - есть новая версия опенсорц (MIT 2020), которая ещё и разрешение 1280х1024 поддерживает https://github.com/jharg93/SvgaBGI/blob/main/SVGA256.HНадо что ли перевести денег человеку, раз уж я аж на протяжении 28 лет его труды использую ![:roll:](./images/smilies/icon_rolleyes.gif) P.P.S. У нас на форуме GRAPHIN упоминался ещё в 2012 году (11 лет назад) в контексте самодельных пользовательских интерфейсов: http://www.nedopc.org/forum/viewtopic.php?p=97574#p97574Решил его выкатить под MIT-лицензией и потом потихоньку развивать до полноценного GUI ![:roll:](./images/smilies/icon_rolleyes.gif) Например очень сильно не мешало бы прикрутить к нему мышь - наработки по мыше для борланда у меня были...
You do not have the required permissions to view the files attached to this post.
|
04 Nov 2023 12:30 |
|
![](./styles/getaway/theme/images/spacer.gif) |
Shaos
Admin
Joined: 08 Jan 2003 23:22 Posts: 23199 Location: Silicon Valley
|
Читаю тут про то как люди меряют качество восстановленной картинки по сравнению с оригиналом: https://en.wikipedia.org/wiki/Peak_signal-to-noise_ratioВот как я в 1996 году считал ошибку, называя её СКО (средне-квадратичное отклонение), коим оно НЕ является: ![](images/spacer.gif) | ![](images/spacer.gif) | ![](images/spacer.gif) | ![](images/spacer.gif) | Code: double operator|(BWS &b1,BWS &b2) { double e,d,d2,n,s; e=0.0;s=0.0; int i,j,c,r; c=b1.GetCol(); r=b1.GetRow(); if((c==b2.GetCol())&&(r==b2.GetRow())) { for(i=0;i<c;i++){ for(j=0;j<r;j++){ d2=b1.GetPixelScr(i,j); d=d2-b2.GetPixelScr(i,j); e+=d*d; s+=d2*d2; }} e=sqrt(e/s); } else e=99999; return e; }
| ![](images/spacer.gif) | ![](images/spacer.gif) | ![](images/spacer.gif) | ![](images/spacer.gif) |
и показывая её в процентах (т.е. умножал на 100). Это не совсем MSE (Median-Squared Error) т.к. в этом случае мне было бы достаточно сложить возведённые в квадрат разницы и разделить на кол-во пикселов, а я делю на сумму яркостей пикселов первой картинки (т.е. уже своего рода нормализованная ошибка) да ещё и беру квадратный корень - получается у совсем различных изображений ошибка будет приближаться к 100%, а у одинаковых - к нулю (наверное по научному это NRMSE - Normalized Root Mean Square Error), однако я заметил что в визуально похожих картинках, где много чёрных пикселов у меня насчитывется большая ошибка - надо разобраться: P.S. Да - это NRMSE, которое ещё называют коэффициентом вариации или относительным стандартным отклонением если оно измеряется в процентах (как у меня): https://en.wikipedia.org/wiki/Coefficient_of_variationP.P.S. Так то оно вполне терпимо меряет - вот примеры похожих и непохожих изображений:
You do not have the required permissions to view the files attached to this post.
|
04 Nov 2023 13:29 |
|
![](./styles/getaway/theme/images/spacer.gif) |
Shaos
Admin
Joined: 08 Jan 2003 23:22 Posts: 23199 Location: Silicon Valley
|
Поправил раскрашивание спектра при выводе - теперь зелёные цвета это положительные отсчёты, а красные - отрицательные. И убрал умножение на 2 из-за которого при отрисовке выпячивались маленькие отсчёты, а большие уходили в разноцветную мешанину, т.к. убегали за пределы своих цветовых диапазонов (сейчас зашкал больше +63 даёт белый, а меньше -64 даёт ярко синий):
You do not have the required permissions to view the files attached to this post.
|
05 Nov 2023 13:13 |
|
![](./styles/getaway/theme/images/spacer.gif) |
Shaos
Admin
Joined: 08 Jan 2003 23:22 Posts: 23199 Location: Silicon Valley
|
Предварительные результаты с Хаффманом - мы его сделали я щитаю (JPEG в смысле) ![:lol:](./images/smilies/icon_lol.gif) Можно ещё над более оптимальным представлением таблицы Хаффмана поработать, но результат уже вполне себе...
You do not have the required permissions to view the files attached to this post.
|
06 Nov 2023 01:18 |
|
![](./styles/getaway/theme/images/spacer.gif) |
Shaos
Admin
Joined: 08 Jan 2003 23:22 Posts: 23199 Location: Silicon Valley
|
А вот так будет выглядеть слегка пережатый Уолш в цвете (слева - оригинал, справа - результат восстановления): Это я в GIMP совместил как RGB три картинки в градациях серого, поджатые Уолшем-Хаффманом почти в 3 раза! И я не планирую прореживать цвета, как это делает JPEG и другие форматы сжатия цветных изображений...
You do not have the required permissions to view the files attached to this post.
|
06 Nov 2023 02:05 |
|
![](./styles/getaway/theme/images/spacer.gif) |
Shaos
Admin
Joined: 08 Jan 2003 23:22 Posts: 23199 Location: Silicon Valley
|
Реализовал всё, кроме последнего пункта - адаптивный алгоритм будет позже. По поводу обхода - пока получается, что диагональный обход убирает больше всего хвостовых нулей подряд, чем горизонтальный или вертикальный способы обхода - когда буду делать адаптивный алгоритм надо будет ещё проверять если сжатие может быть лучше при каких-то других обходах, но пока диагональный даёт лучший результат...
|
06 Nov 2023 09:25 |
|
![](./styles/getaway/theme/images/spacer.gif) |
Shaos
Admin
Joined: 08 Jan 2003 23:22 Posts: 23199 Location: Silicon Valley
|
Переделываю сохранение таблицы Хаффмана в соответствии с новой информациейПо ходу можно прикинуть разницу в размерах таблицы в случае 3 разных вариантов сохранения, скажем можно взять таблицу из ELAINE сжатой до 2 бит на сэмпл (ELAINE02.WHI): (таблица Хаффмана в WHI смешивает в месте квантованные отсчёты и метки последовательностей нулей разной длины, представляя их как разные литералы) Если оставить как есть сейчас, то она будет занимать (3+8)*27+2*2+1*3+2*4+2*5+4*6+7*16=458 бит (58 байт) Если сделать как SHAFF2 (когда размер символа указывается не для каждого символа, а для целого блока, которых тут 6), но в побитовом сохранении, то уже 8*27+(2+3)*6+2*2+1*3+2*4+2*5+4*6+7*16=407 бит (51 байт) Если же таблицу упорядочить в соответствии с кодами, то можно сохранить её в виде дерева: получив 269 бит (34 байта) - под спойлером раскладка в дерево: дерево![](images/spacer.gif) | ![](images/spacer.gif) | ![](images/spacer.gif) | ![](images/spacer.gif) | Code: >>>halfhuf 0..27 (5)- split offset 5 - 0..1,2..26 there is 0 branch - process >>>halfhuf 2..26 (6)- split offset 6 - 2..11,12..26 there is 0 branch - process >>>halfhuf 12..26 (7)- split offset 7 - 12..12,13..26 there is 0 branch - process >>>halfhuf 13..26 (8)- split offset 8 - 13..19,20..26 there is 0 branch - process >>>halfhuf 20..26 (9)- split offset 9 - 20..23,24..26 there is 0 branch - process >>>halfhuf 24..26 (10)- split offset 10 - 24..25,26..26 single 0 branch - literal 26 0xB3 ( ) 000000|0 there is 1 branch - process >>>halfhuf 24..25 (11)- split offset 11 - 24..24,25..25 single 0 branch - literal 25 0xF6 ( ) 0000010|0 single 1 branch - literal 24 0xDF ( ) 0000011|1 <<<halfhuf 19 <<<halfhuf 29 there is 1 branch - process >>>halfhuf 20..23 (10)- split offset 10 - 20..21,22..23 there is 0 branch - process >>>halfhuf 22..23 (11)- split offset 11 - 22..22,23..23 single 0 branch - literal 23 0xDD ( ) 0000100|0 single 1 branch - literal 22 0xD1 ( ) 0000101|1 <<<halfhuf 19 there is 1 branch - process >>>halfhuf 20..21 (11)- split offset 11 - 20..20,21..21 single 0 branch - literal 21 0xCC ( ) 0000110|0 single 1 branch - literal 20 0xC5 ( ) 0000111|1 <<<halfhuf 19 <<<halfhuf 39 <<<halfhuf 69 there is 1 branch - process >>>halfhuf 13..19 (9)- split offset 9 - 13..15,16..19 there is 0 branch - process >>>halfhuf 16..19 (10)- split offset 10 - 16..17,18..19 there is 0 branch - process >>>halfhuf 18..19 (11)- split offset 11 - 18..18,19..19 single 0 branch - literal 19 0xBF ( ) 0001000|0 single 1 branch - literal 18 0xBD ( ) 0001001|1 <<<halfhuf 19 there is 1 branch - process >>>halfhuf 16..17 (11)- split offset 11 - 16..16,17..17 single 0 branch - literal 17 0xBC ( ) 0001010|0 single 1 branch - literal 16 0xBA ( ) 0001011|1 <<<halfhuf 19 <<<halfhuf 39 there is 1 branch - process >>>halfhuf 13..15 (10)- split offset 10 - 13..13,14..15 there is 0 branch - process >>>halfhuf 14..15 (11)- split offset 11 - 14..14,15..15 single 0 branch - literal 15 0xB8 ( ) 0001100|0 single 1 branch - literal 14 0x57 (W) 0001101|1 <<<halfhuf 19 single 1 branch - literal 13 0xBB ( ) 000111|1 <<<halfhuf 29 <<<halfhuf 69 <<<halfhuf 139 single 1 branch - literal 12 0xAF ( ) 001|1 <<<halfhuf 149 there is 1 branch - process >>>halfhuf 2..11 (7)- split offset 7 - 2..8,9..11 there is 0 branch - process >>>halfhuf 9..11 (8)- split offset 8 - 9..10,11..11 single 0 branch - literal 11 0xB1 ( ) 0100|0 there is 1 branch - process >>>halfhuf 9..10 (9)- split offset 9 - 9..9,10..10 single 0 branch - literal 10 0xB2 ( ) 01010|0 single 1 branch - literal 9 0xB4 ( ) 01011|1 <<<halfhuf 19 <<<halfhuf 29 there is 1 branch - process >>>halfhuf 2..8 (8)- split offset 8 - 2..2,3..8 there is 0 branch - process >>>halfhuf 3..8 (9)- split offset 9 - 3..6,7..8 there is 0 branch - process >>>halfhuf 7..8 (10)- split offset 10 - 7..7,8..8 single 0 branch - literal 8 0xB7 ( ) 011000|0 single 1 branch - literal 7 0xB9 ( ) 011001|1 <<<halfhuf 19 there is 1 branch - process >>>halfhuf 3..6 (10)- split offset 10 - 3..4,5..6 there is 0 branch - process >>>halfhuf 5..6 (11)- split offset 11 - 5..5,6..6 single 0 branch - literal 6 0xD6 ( ) 0110100|0 single 1 branch - literal 5 0xBE ( ) 0110101|1 <<<halfhuf 19 there is 1 branch - process >>>halfhuf 3..4 (11)- split offset 11 - 3..3,4..4 single 0 branch - literal 4 0xB6 ( ) 0110110|0 single 1 branch - literal 3 0xB5 ( ) 0110111|1 <<<halfhuf 19 <<<halfhuf 39 <<<halfhuf 59 single 1 branch - literal 2 0xB0 ( ) 0111|1 <<<halfhuf 69 <<<halfhuf 99 <<<halfhuf 249 there is 1 branch - process >>>halfhuf 0..1 (6)- split offset 6 - 0..0,1..1 single 0 branch - literal 1 0x58 (X) 10|0 single 1 branch - literal 0 0x56 (V) 11|1 <<<halfhuf 19 <<<halfhuf 269
| ![](images/spacer.gif) | ![](images/spacer.gif) | ![](images/spacer.gif) | ![](images/spacer.gif) |
что на 24 байта короче - выходит ELAINE02.WHI будет не 175 байт длиной, а уже 151, что даёт сжатие в 20.4 раза вместо озвученных выше 17.7 ![:o](./images/smilies/icon_eek.gif)
|
07 Nov 2023 21:32 |
|
![](./styles/getaway/theme/images/spacer.gif) |
Shaos
Admin
Joined: 08 Jan 2003 23:22 Posts: 23199 Location: Silicon Valley
|
Прикинул тут 2 варанта (ELAINE02 и ELAINE04) с RLE и без RLE и чото получается, что просто кодирование символов по частоте (голый Хаффман) даёт результаты лучше, чем Хаффман поверх RLE (когда нули собраны с спец.символы по количеству подряд идущих и замешаны с сэмплами в общем алфавите как в примерах выше) - наверное надо добавить как опцию возможность делать и так, и эдак (и потом в адаптивном алгоритме реализовать всё с выбором лучшего): (последний вариант это голые квантованные данные чисто чтобы было) Но отбрасывание хвостовых нулей я оставлю для всех вариантов т.к. их наличие уж точно ничего не даёт, а просто расходует попусту пространство (хотя с другой стороны, в случае отбрасывания нулей приходится заводить отдельный символ, означающий конец последовательности). P.S. А пока выложил GRAPHIN на GitLab под MIT-лицензией вместе с одним примером и дополнительными классами BWS и BITIO (эти я выдаю как PUBLIC DOMAIN): https://gitlab.com/shaos/graphin
|
07 Nov 2023 22:34 |
|
Who is online |
Users browsing this forum: Claude AI [Bot] and 5 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
|
|