nedoPC.org

Electronics hobbyists community established in 2002
Atom Feed | View unanswered posts | View active topics It is currently 28 Mar 2024 12:27



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

Joined: 08 Jan 2003 23:22
Posts: 22412
Location: Silicon Valley
Reply with quote
UPDATE: Самые последние исходники под MIT-лицензией всегда можно найти тут: https://gitlab.com/shaos/graphin
Приаттачиваю архив с исходниками и досовским EXE-шником Walsh Explorer v1.0.5 от 7 декабря 2023 года прямо сюда:
Attachment:
GRAPHIN.ZIP [480.83 KiB]
Downloaded 285 times

-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

На основе моей дипломной работы 1996 года хочу зарелизить опенсорсную программу "Walsh Explorer" (для начала под DOS), которая поможет создать простой алгоритм сжатия изображений с потерями, способный заменить JPEG на ретрокомпах (т.к. JPEG для них тяжеловат). В этом простом алгоритме вместо DCT будет использоваться преобразование Уолша (Walsh-Hadamard Transform) и далее кодирование по Хаффману (Huffman coding). Предварительные эксперименты тут показали, что пободаться с JPEG нам вполне по силам :idea:

Отпочковано отсюда: http://www.nedopc.org/forum/viewtopic.php?f=46&t=22127&start=30

Shaos wrote:
А так-то я обработкой изображений очень давно занимаюсь - вот скрины из моей дипломной работы 1996 года:

Image

там например можно было поиграться со спектром преобразования Уолша:

Image

и даже получить обратно картинку из урезанного спектра:

Image

программа работала с BWS форматом изрбражений (это мой собственный формат представления картинок в градациях серого без потерь с 6 битами на точку):

Image

интерфейс пользователя был самописный ( я его создал в 1995 году и назвал GRAPHIN : ) т.к. всё работало на голом досе в 320x200:

Image

как можно видеть я там реализовал несколько простых фильтров и ещё в этой программе можно было поиграться с экспериментальными алгоритмами фрактального сжатия и самодельной "аппроксимации сферами" (тоже моё изобретение):

Image

Вот полное меню для преобразования Уолша:

Attachment:
demo_006.png
demo_006.png [ 6.78 KiB | Viewed 19094 times ]

Откуда можно зайти в "Обработку спектра":

Attachment:
demo_007.png
demo_007.png [ 6.11 KiB | Viewed 19094 times ]

И выбрать "Просмотр строк спектра" где двигаясь вверх-вниз можно поглядеть глазами как оно выглядит "сбоку":

Attachment:
demo_008.png
demo_008.png [ 6.44 KiB | Viewed 19094 times ]

А вот подменю "Квантование спектра":

Attachment:
demo_009.png
demo_009.png [ 3.48 KiB | Viewed 19094 times ]

Где можно огрубить отсчёты скажем до 7 бит и получить восстановленное изображение:

Attachment:
demo_010.png
demo_010.png [ 8.41 KiB | Viewed 19094 times ]

Надо все эти возможности повторить в нашем новом графическом редакторе :mrgreen:

P.S. IC1 это был мой экспериментальный формат сжатия картинок на основе преобразования Уолша - там тоже надо было квантовать отсчёты, но я там в те времена накосячил с памятью и оно падало при попытке прочитать сохранённый файл (починил 30 октября 2023). Ещё в этой программе был формат IC2 (фрактальное сжатие - для него даже отдельный просмотрщик был) и формат IC3 (моё самодельное сжатие сферами) - ни то, ни другое в настоящее время интереса не вызывает. Ещё судя по архиву наработок я пытался Фурье осилить, но видать не осилил :roll:

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

Attachment:
demo_011.png
demo_011.png [ 6.27 KiB | Viewed 18918 times ]

Это я пытался повторить вот этот эксперимент со спектром Фурье (картинка из твиттера):

Attachment:
Fourier.png
Fourier.png [ 103.15 KiB | Viewed 18918 times ]

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


26 Oct 2023 09:21
Profile WWW
Admin
User avatar

Joined: 08 Jan 2003 23:22
Posts: 22412
Location: Silicon Valley
Reply with quote
Мой формат (слева) до Хаффмана по качеству превосходит пережатый JPEG, но по размерам не догоняет - нужен Хаффман:

Image

Плюс существующий формат надо несколько обработать напильником:

Shaos wrote:
В своей дипломной работе 1996 года (см. тут) я сжимал изображения с использованием двумерного спектра Уолша (64x64 для картинок в градациях серого 64х64 где каждый пиксел принимал значения от 0 до 63):



сохраняя его в файл побитно следующим образом:
  • Пользователь спрашивался сколько бит на отсчёт надо использовать для кодирования - выбиралось значение от 4 до 12 (это с учётом бита знака);
  • Отсчёты [0][0], [0][1] и [1][0] сохранялись отдельно в заголовке как целые 14-битные числа (т.к. они обычно сильно больше остальных отсчётов);
  • Параметры квантования (количество битов и шаг с точностью до десятых долей) также сохранялись в заголовке;
  • Остальные отсчёты квантовались от нуля до абсолютного максимума в пределах этого спектра (без учёта вышеупомянутых трёх отсчётов) и сохранялись в указанном количестве битов (с битом знака идущим первым), однако код 100...00 (минус ноль) использовался как маркер последовательности квантованных нулей - если такой маркер встречался в последовательности, то за ним шло 6-битное количество нулей которые надо вставить при вычитке этой строки спектра (таким способом я кодировал 3 и больше нулей идущих подряд).

а именно:

  • Сделать возможным сохранять несколько произвольных отсчётов-выскочек в количестве от 1 до скажем 8 с указанием координат вместо теперешних трёх захардкоденных;
  • Сохранять параметры квантования с большей точностью, а не как сейчас с точностью до десятых долей;
  • Разрешить несколько способов обхода спектра - по горизонтали, по вертикали и по диагонали;
  • Отбрасывать нулевые отсчёты в хвосте спектра для уменьшения размеров получающегося файла;
  • Добавить адаптивное сжатие, когда параметры будут выбираться автоматически исходя из указанного показателя качества (от 0 до 100 по аналогии с JPEG) и если Хаффман не помогает уменьшить блок (если таблица получилась слишком большая), то оставлять RLE (как сейчас).

Ну и в дальнейшем хотелось бы перейти от картинок 64х64 к картинкам произвольного размера (скажем до 2048x2048 кодируя всё те же блоки 64х64 быстрым преобразованием Уолша) - расширение такого файла будет скажем .whi (Walsh+Huffman Image), а если оно таки полетит как надо (под DOS и на ретрокомпах типа Спринтера), то вот тогда уже можно перейти к разработке формата TONIC...

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


31 Oct 2023 23:38
Profile WWW
Senior
User avatar

Joined: 14 Oct 2023 06:59
Posts: 104
Reply with quote
А маркер комментариев поддерживается, или он чуждый классу пользователей?


02 Nov 2023 06:34
Profile
Admin
User avatar

Joined: 08 Jan 2003 23:22
Posts: 22412
Location: Silicon Valley
Reply with quote
shiny wrote:
А маркер комментариев поддерживается, или он чуждый классу пользователей?
Кто такой есть маркер комментариев?

В смысле как в JPEG? https://habr.com/en/articles/102521/

Не - комментарии лишние :mrgreen:

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


02 Nov 2023 06:37
Profile WWW
Senior

Joined: 01 Jan 2022 04:34
Posts: 162
Location: USSR, Tashkent
Reply with quote
Shaos wrote:
Кто такой есть маркер комментариев?

В смысле как в JPEG? https://habr.com/en/articles/102521/

Не - комментарии лишние :mrgreen:


а как же хеш, говорящий что это не генерированная ИИ картинка ?


02 Nov 2023 07:20
Profile
Admin
User avatar

Joined: 08 Jan 2003 23:22
Posts: 22412
Location: Silicon Valley
Reply with quote
imsushka wrote:
а как же хеш, говорящий что это не генерированная ИИ картинка ?

ну про то чем сгенерирована сжимаемая картинка кодировщик точно знать не знает

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


02 Nov 2023 09:06
Profile WWW
Senior
User avatar

Joined: 14 Oct 2023 06:59
Posts: 104
Reply with quote
Shaos wrote:
Кто такой есть маркер комментариев?

В смысле как в JPEG? https://habr.com/en/articles/102521/

Не - комментарии лишние :mrgreen:


да, это он - COM (FF FE)
вообще, если взглянуть на состав картинки, то обнаружится немало мусора 8)


02 Nov 2023 20:43
Profile
Admin
User avatar

Joined: 08 Jan 2003 23:22
Posts: 22412
Location: Silicon Valley
Reply with quote
Американизированный вариант программы практически готов :mrgreen:

Attachment:
walshexp.gif
walshexp.gif [ 141.88 KiB | Viewed 18481 times ]

Сама программа будет под 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 :o
Code:
#define SVGA256_320x200 0
#define SVGA256_640x400 1
#define SVGA256_640x480 2
#define SVGA256_800x600 3
#define SVGA256_1024x768 4
Пример под спойлером:
 1024x768
Attachment:
graftst1_000.png
graftst1_000.png [ 2.88 KiB | Viewed 18458 times ]
Правда поддерживает он все эти SVGA режимы через бинарную либу SVGA256.OBJ, которую я где-то оттопырил в 1995 году:
Code:
SVGA 256 Colour BGI Device Driver (SVGA256) 2.31 - Dec 06, 1991
Copyright (c) 1991 Jordan Hargraphix
О - есть новая версия опенсорц (MIT 2020), которая ещё и разрешение 1280х1024 поддерживает :esurprised:
https://github.com/jharg93/SvgaBGI/blob/main/SVGA256.H
Quote:
REGISTRATION: I have decided to release these drivers free of charge, although donations would be greatly appreciated and certainly expedite the release of future versions. :-> The drivers have not been crippled in any way, though beta releases of new drivers may have some functions yet unimplemented.

Registration fees: ( Price includes both BGIv2.0 and BGIv3.0 drivers )
...
SuperVGA BGI 256 $30
...
Надо что ли перевести денег человеку, раз уж я аж на протяжении 28 лет его труды использую :roll:

P.P.S. У нас на форуме GRAPHIN упоминался ещё в 2012 году (11 лет назад) в контексте самодельных пользовательских интерфейсов:
http://www.nedopc.org/forum/viewtopic.php?p=97574#p97574
Решил его выкатить под MIT-лицензией и потом потихоньку развивать до полноценного GUI :roll:
Например очень сильно не мешало бы прикрутить к нему мышь - наработки по мыше для борланда у меня были...

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


04 Nov 2023 12:30
Profile WWW
Admin
User avatar

Joined: 08 Jan 2003 23:22
Posts: 22412
Location: Silicon Valley
Reply with quote
Читаю тут про то как люди меряют качество восстановленной картинки по сравнению с оригиналом:

https://en.wikipedia.org/wiki/Peak_signal-to-noise_ratio

Вот как я в 1996 году считал ошибку, называя её СКО (средне-квадратичное отклонение), коим оно НЕ является:
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;
}
и показывая её в процентах (т.е. умножал на 100). Это не совсем MSE (Median-Squared Error) т.к. в этом случае мне было бы достаточно сложить возведённые в квадрат разницы и разделить на кол-во пикселов, а я делю на сумму яркостей пикселов первой картинки (т.е. уже своего рода нормализованная ошибка) да ещё и беру квадратный корень - получается у совсем различных изображений ошибка будет приближаться к 100%, а у одинаковых - к нулю (наверное по научному это NRMSE - Normalized Root Mean Square Error), однако я заметил что в визуально похожих картинках, где много чёрных пикселов у меня насчитывется большая ошибка - надо разобраться:

Attachment:
walshexp_001.png
walshexp_001.png [ 5.45 KiB | Viewed 18476 times ]


P.S. Да - это NRMSE, которое ещё называют коэффициентом вариации или относительным стандартным отклонением если оно измеряется в процентах (как у меня):

https://en.wikipedia.org/wiki/Coefficient_of_variation

Quote:
Недостатки

1. Когда среднее значение близко к нулю, коэффициент вариации приближается к бесконечности и поэтому чувствителен к небольшим изменениям среднего...


P.P.S. Так то оно вполне терпимо меряет - вот примеры похожих и непохожих изображений:


Attachments:
walshexp_003.png
walshexp_003.png [ 6.54 KiB | Viewed 18471 times ]
walshexp_002.png
walshexp_002.png [ 6.68 KiB | Viewed 18471 times ]

_________________
:dj: https://mastodon.social/@Shaos
04 Nov 2023 13:29
Profile WWW
Admin
User avatar

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

Image

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


Attachments:
walshexp_005.png
walshexp_005.png [ 6.15 KiB | Viewed 18422 times ]

_________________
:dj: https://mastodon.social/@Shaos
05 Nov 2023 13:13
Profile WWW
Admin
User avatar

Joined: 08 Jan 2003 23:22
Posts: 22412
Location: Silicon Valley
Reply with quote
Предварительные результаты с Хаффманом - мы его сделали я щитаю (JPEG в смысле) :lol:

Attachment:
WHIvsJPEG.jpg
WHIvsJPEG.jpg [ 380.58 KiB | Viewed 18378 times ]

Можно ещё над более оптимальным представлением таблицы Хаффмана поработать, но результат уже вполне себе...

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


06 Nov 2023 01:18
Profile WWW
Admin
User avatar

Joined: 08 Jan 2003 23:22
Posts: 22412
Location: Silicon Valley
Reply with quote
А вот так будет выглядеть слегка пережатый Уолш в цвете (слева - оригинал, справа - результат восстановления):

Attachment:
TiffanyRGB.png
TiffanyRGB.png [ 23.66 KiB | Viewed 18371 times ]

Это я в GIMP совместил как RGB три картинки в градациях серого, поджатые Уолшем-Хаффманом почти в 3 раза!

И я не планирую прореживать цвета, как это делает JPEG и другие форматы сжатия цветных изображений...

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


06 Nov 2023 02:05
Profile WWW
Admin
User avatar

Joined: 08 Jan 2003 23:22
Posts: 22412
Location: Silicon Valley
Reply with quote
Shaos wrote:
  • Сделать возможным сохранять несколько произвольных отсчётов-выскочек в количестве от 1 до скажем 8 с указанием координат вместо теперешних трёх захардкоденных;
  • Сохранять параметры квантования с большей точностью, а не как сейчас с точностью до десятых долей;
  • Разрешить несколько способов обхода спектра - по горизонтали, по вертикали и по диагонали;
  • Отбрасывать нулевые отсчёты в хвосте спектра для уменьшения размеров получающегося файла;
  • Добавить адаптивное сжатие, когда параметры будут выбираться автоматически исходя из указанного показателя качества (от 0 до 100 по аналогии с JPEG) и если Хаффман не помогает уменьшить блок (если таблица получилась слишком большая), то оставлять RLE (как сейчас).
Реализовал всё, кроме последнего пункта - адаптивный алгоритм будет позже.

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

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


06 Nov 2023 09:25
Profile WWW
Admin
User avatar

Joined: 08 Jan 2003 23:22
Posts: 22412
Location: Silicon Valley
Reply with quote
Переделываю сохранение таблицы Хаффмана в соответствии с новой информацией

По ходу можно прикинуть разницу в размерах таблицы в случае 3 разных вариантов сохранения, скажем можно взять таблицу из ELAINE сжатой до 2 бит на сэмпл (ELAINE02.WHI):
Code:
72   088:10
72   086:11
18   175:001
17   176:0111
11   177:0100
7   180:01011
6   178:01010
4   185:011001
3   187:000111
3   183:011000
2   179:000000
2   214:0110100
2   190:0110101
2   182:0110110
2   181:0110111
1   246:0000010
1   223:0000011
1   221:0000100
1   209:0000101
1   204:0000110
1   197:0000111
1   191:0001000
1   189:0001001
1   188:0001010
1   186:0001011
1   184:0001100
1   087:0001101
(таблица Хаффмана в 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 байт)

Если же таблицу упорядочить в соответствии с кодами, то можно сохранить её в виде дерева:
Code:
72 086:11
72 088:10
17 176:0111
2  181:0110111
2  182:0110110
2  190:0110101
2  214:0110100
4  185:011001
3  183:011000
7  180:01011
6  178:01010
11 177:0100
18 175:001
3  187:000111
1  087:0001101
1  184:0001100
1  186:0001011
1  188:0001010
1  189:0001001
1  191:0001000
1  197:0000111
1  204:0000110
1  209:0000101
1  221:0000100
1  223:0000011
1  246:0000010
2  179:000000
получив 269 бит (34 байта) - под спойлером раскладка в дерево:
 дерево
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
что на 24 байта короче - выходит ELAINE02.WHI будет не 175 байт длиной, а уже 151, что даёт сжатие в 20.4 раза вместо озвученных выше 17.7 :o

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


07 Nov 2023 21:32
Profile WWW
Admin
User avatar

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

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

P.S. А пока выложил GRAPHIN на GitLab под MIT-лицензией вместе с одним примером и дополнительными классами BWS и BITIO (эти я выдаю как PUBLIC DOMAIN):

https://gitlab.com/shaos/graphin

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


07 Nov 2023 22:34
Profile WWW
Display posts from previous:  Sort by  
Reply to topic   [ 65 posts ]  Go to page 1, 2, 3, 4, 5  Next

Who is online

Users browsing this forum: Google [Bot] and 21 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.