Всем привет! В этой статье я опишу алгоритм работы формата сжатия изображений без потерь. Сжатие использует известные методики, которые и дали ему название. Проект начинался с простых экспериментов, которые вышли из под контроля. Не смотря на то, что формат чаще сжимает лучше чем png, никакого практического применения этот формат не имеет, оставаясь чисто академическим.

Внимание! В статье много картинок.

Предисловие

Все началось в конце 2021 года. На хабре вышла статья про формат сжатия QOI . Этот формат делает упор на скорость кодирования и декодирования, а не на размер. Автор формата пишет, что он обычный программист и несильно разбирается в сложных алгоритмах.

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

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

Ссылка на проект. В проекте есть бины.

Проект написан на C#. Особо не оптимизировал и не причесывал. Только добавил многопоточное кодирование алгоритмами.

Исходные тестовые изображения

Для тестов использовал знаменитое изображение Lenna. У этого изображения есть сайт, где отсканировано это же изображение в более высоком качестве. Обрезал нижнюю часть (там ню) и принялся за работу.

Другие изображения для тестирования я взял на wikimedia, выбрав случайный год и месяц. Переконвертировал их в png Gimp-ом с максимальным сжатием. В комментариях порекомендовали проверить и оптимизатор PNGOUT.

Дельта-кодирование

Дельта-кодирование - это когда мы вместо абсолютных значений данных записываем их изменение. И если изменение небольшие, то их дельта стремится к нулю.

Например, значения:

128

129

130

130

129

128

127

128

Превращаются в:

0

1

1

0

-1

-1

-1

1

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

Так как наше изображение имеет много мест с плавными переходами (градиенты), то дельта кодирование должно очень сильно уменьшить значения данных. Вот один из увеличенных кусков изображения:

Ну что ж, давайте применим дельта кодирование и посмотрим, что у нас выйдет. Сначала сделаем горизонтальное кодирование, после этого сделаем вертикальное кодирование, так как у нас градиенты могут быть по всем осям.

Наша текстура превращается в следующую:

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

Вот такой график был в изначальном изображении для зеленого канала:

Вот такой график получился после горизонтального и вертикального дельта кодирования:

Там где цвет не менялся, получился 0, там где он возрастал на 1, получился 1, там где он уменьшался на 1, получился -1, но байты у нас без знака, поэтому он стал 255. т.е у нас все значения стремятся к 0 и к 255.

Внимание! Далее для удобства статьи и для наглядности, я циклически сдвину все значения на 128 (половина байта от 0 до 255). В гистограмме пик значений окажется в центре. Само изображение станет серым, и смещения будут градациями серого, не будет резких перепадов белого и черного. В самом кодировании ничего не сдвигается!

Вот такое мы получаем изображение, если сдвинем все значения на 128:

И вот такая гистограмма для зеленого канала:

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

Что еще можно обнаружить, посмотрев на изображение, что у нас получилось? В нем практически исчезла информация о цвете! Так как, условно, все цвета уходили в тень с похожими дельтами. А если у нас нет цвета, то мы можем взять за основу один канал, например, зеленый, а в другие каналы записать разницу (дельту) от этого канала. Похожим образом кодировалось аналоговое телевидение: передавалось чб изображение и две разности канала от него, а третий канал, получался вычетом двух получившихся каналов из чб.

Изображение с дельтами от каналов:

Разница не очень заметна там, где было яркое светлое, теперь преобладает зеленое. Но на изображение без сдвигов на 128 - более заметно. Зеленый заметно преобладает, точнее наоборот: красный и синий стал заметно меньше:

Сравните с изображением, что было, когда мы применили дельту по горизонтали и вертикали, но еще не сдвинули на 128.

А теперь посмотрим что получилось у нас в дельтах каналов, например, в красном:

Огромное количество нулей, 1 и -1 (255). Все остальное рассыпалось. А значит и сжиматься этот канал будет заметно сильнее.

Код Хаффмана

Код Хаффмана алгоритм кодирования, который кодирует часто встречающиеся данные более коротким кодом, а редко встречающиеся - более длинным, и чем больше разница в частоте символов, тем более сильнее получается сжатие. Коды генерируются таким образом, что любой код не является началом любого другого, что позволяет достоверно определить код при декодировании. Статей в интернете, и на хабре в частности, очень много. Я просто взял описание с википедии и реализовал так, как там написано.

Создал массив с нодами, в которых указано значение и частота вхождений.

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

Теперь можно написать первый тест и посмотреть - насколько наше кодирование лучше, чем png. Для удобства алгоритм сокращенно буду называть drh (от названия delta rle huffman).

Повторю наш алгоритм:

  • Дельта кодирование пикселей по вертикали и горизонтали

  • Дельта каналов относительно зеленого

  • Кодирование кодом Хаффмана, построчно, каждого канала по отдельности

Я за вас уже все сделал - вот результат:

Размер в памяти : 1 873 152 байт
Размер gimp png : 981 891 (52%) байт
Размер pngout : 972 885 (51%) байт
Размер drh : 834 004 (44%) байт

Выше - статистика вхождений для алгоритма Хаффмана собиралась по предыдущей строке. Если собирать по всем предыдущим строкам, то получается еще меньше:

Размер drh : 803 047 (42%) байт (- 30 957 байт)

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

Rle (run-length encoding)

Rle (Кодирование длин серий) - это алгоритм, который заменяет последовательность одинаковых символов каким-то кодом, с указанием их количества. Так как в каналах красного и синего у нас разница между зеленым, то по идее, там должно быть много нулей. Чтобы визуально увидеть нули, я взял отдельные каналы, сдвинутые на 128 (серые) и заменил там 128 на 0, т.е. виртуальный ноль на реальный. Теперь 0 будет черного цвета и контрастировать на фоне серого изображения.

Вот зеленый канал:

А вот красный:

Очень заметно, что нулей там очень много, а значит rle нам поможет!

Для rle нужен отдельный код, поэтому я создал, как бы, виртуальный пиксель со значением 256, и собирал для него статистику так же, как и для обычных пикселей. Для расчета я брал размер кода нуля, размер кода rle и постфикса, в котором указывается число символов, и рассчитывал какое количество нулей можно минимально закодировать, чтобы итоговый размер rle кода с числом был меньше.

Результат с использованием rle:

Размер drh :  781 847 (41%) байт (- 21 200 байт)

Алгоритм без названия

Есть у меня еще одно преобразование потока. Оно больше подходит для зеленого канала, так как там оригинальное дельта кодирование потока. В остальных каналах структура рассыпается. Когда в изображении поток светлеет, то в дельта потоке идет волна положительных чисел, когда изображение темнеет, то в дельта потоке идет отрицательная волна.

Условно, можно представить это так:

2

2

1

1

0

0

0

-1

-1

-1

-2

-2

Амплитуда и продолжительность волн, конечно, хаотичная. Но если часто встречаются длинные волны, то мы можем использовать знак числа не как абсолютное значение, а как метку того, что знак в потоке поменялся. Это уменьшит количество отрицательных чисел и увеличит количество положительных чисел, что очень хорошо скажется на последующем кодировании алгоритмом Хаффмана.

Например, в нашем случае поток превратится в следующий:

2

2

2

2

1

1

1

0

0

0

-1

-1

Результат после этого алгоритма:

Размер drh :  777 219 (41%) байт (- 4 628 байт)

Сжатие чисел

Для rle после кода пишется число. Если мы зарезервируем, например, byte для него, то сам код с числом будет коротким, но мы будем ограничены последовательностью в 255. А если мы будем для числа резервировать больше места, то сам код с числом будет большего размера и не будет подходить для коротких последовательностей, а их статистически больше.

Для решения этой проблемы используют кодирование числа переменной длины. Например, кодировка символов UTF-8. В байте резервируется место, в котором записывается информация о длине символов.

Но я использовал более простой и компактный вариант: я выбрал количество бит для числа и после них ставлю один бит расширения (extension). Этот бит определяет - есть ли дальше еще такой же кусок . Например, для rle я выбрал 3 бита + бит расширения:

(000 E) (000 E)

Если число помещается в 3 бита, от 0 до 7, то размер итогового числа будет 4 бита, если помещается в 6 бит, от 0 до 63, то итоговое число будет 8 бит и т.д.

Для других чисел, например, размер изображения в хедере файла, я использовал кодировку 6 бит + бит расширения.

(000000 E) (000000 E)

Итоговая реализация

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

Раздельное дельта кодирование, одно на всю строку, варианты:

  • Только горизонтальное

  • Только вертикальное

  • Вертикальное и горизонтальное

Варианты алгоритмов на каждый канал:

  • (H) Алгоритм Хаффмана, статистика по предыдущей строке

  • (HA) Алгоритм Хаффмана, статистика по всем предыдущим строкам

  • (SH) Знак числа переключает знак в потоке, алгоритм Хаффмана, статистика по предыдущей строке

  • (SHA) Знак числа переключает знак в потоке, алгоритм Хаффмана, по всем предыдущим строкам

  • (RH) Алгоритм Хаффмана, rle, статистика по предыдущей строке

  • (RHA) Алгоритм Хаффмана, rle, статистика по всем предыдущим строкам

  • (RSH) Знак числа переключает знак в потоке, rle, алгоритм Хаффмана, статистика по предыдущей строке

  • (RSHA) Знак числа переключает знак в потоке, rle, алгоритм Хаффмана, по всем предыдущим строкам

Итоговое сжатие:

Размер в памяти : 1 873 152 байт
Размер gimp png : 981 891 (52%) байт
Размер pngout : 972 885 (51%) байт
Размер drh : 757 530 (40%) байт (- 19 689 байт от предыдущего)

Статистика по алгоритмам:

Delta H count : 71
Delta V count : 120
Delta HV count : 385
Rle count : 54251
HA : 82
SHA : 369
RHA : 111
RSHA : 1 111
H : 3
SH : 11
RH : 0
RSH : 41

Статистика тестовых изображений с wikimedia:

  • В комментариях порекомендовали сравнить с оптимизатором png - PNGOUT.

Если у Вас как и у меня странные размеры столбиков в таблице, то значит хабр их так рассчитывает (

Название

raw

gimp_png

pngout

drh

15th_Arrondissement

90 731 394

42 526 358 (46%)

39 565 296 (43%)

30 743 704 (33%)

035_Uganda_kobs

33 272 403

18 970 680 (57%)

18 970 680 (57%)

18 290 582 (54%)

Alligator_mississippiensis

11 520 000

3 424 666 (29%)

3 148 232 (27%)

2 335 555 (20%)

Australian_House_of

31 515 000

16 594 068 (52%)

16 594 068 (52%)

15 238 948 (48%)

Bloemknop_van_een

35 831 808

17 912 362 (49%)

17 423 097 (48%)

15 239 398 (42%)

Bonaparte_premier

18 251 850

8 414 208 (46%)

7 845 598 (42%)

5 802 686 (31%)

Cabo_Norte

117 366 306

54 923 608 (46%)

49 295 472 (42%)

36 171 071 (30%)

Cálice,_Patena

31 935 150

19 340 437 (60%)

19 340 437 (60%)

16 574 404 (51%)

Catedral_Metropolitana

27 505 860

13 207 395 (48%)

13 007 166 (47%)

11 649 748 (42%)

Diomedea_exulans

12 495 000

4 486 541 (35%)

4 305 531 (34%)

3 549 462 (28%)

Dörzbach_-_Hohebach

92 528 118

56 636 479 (61%)

55 365 884 (59%)

45 848 952 (49%)

Easter_breakfast

60 466 176

35 957 811 (59%)

35 741 021 (59%)

32 812 801 (54%)

Ely_Cathedral

93 230 784

62 155 688 (66% )

59 913 142 (64%)

46 258 288 (49%)

Evening_pray

47 988 750

26 623 627 (55%)

23 989 259 (49%)

17 652 471 (36%)

Everest,_Himalayas

32 514 048

18 136 205 (55%)

17 854 084 (54%)

15 209 519 (46%)

Gazania_krebsiana

132 029 952

48 426 335 (36%)

46 917 009 (35%)

46 045 089 (34%)

Guarda-corpo

32 108 091

16 681 516 (51%)

16 387 780 (51%)

13 468 008 (41%)

ISR-2013-Jerusalem

75 000 000

26 579 848 (35%)

26 579 848 (35%)

24 326 519 (32%)

Katharine_Hepburn

17 447 160

3 966 995 (22%)

3 013 214 (17%)

2 866 751 (16%)

Latarnia_morska

55 498 275

12 616 536 (22%)

11 461 134 (20%)

9 046 817 (16%)

Lukmanierpass,_Passo

46 575 726

33 067 593 (70%)

32 660 222 (70%)

27 714 865 (59%)

Münster,_LWL

62 374 455

33 802 173 (54%)

32 979 264 (52%)

26 141 307 (41%)

Muster_für

26 152 632

10 391 347 (39%)

10 290 979 (39%)

8 826 897 (33%)

Opernpassage

439 282 140

119 418 716 (27%)

114 075 630 (25%)

85 254 836 (19%)

Palacio_Belvedere

80 060 940

30 278 909 (37%)

29 090 411 (36%)

22 193 699 (27%)

Praia_do_Ribeiro

36 081 000

16 667 140 (46%)

15 666 141 (43%)

12 684 818 (35%)

Rottenburg_a.N.

124 109 667

61 475 039 (49%)

59 734 027 (48%)

49 365 240 (39%)

Town_hall_of_Leuven

28 974 267

18 025 068 (62%)

16 319 774 (56%)

12 438 602 (42%)

Traditional_worker

26 250 576

14 317 377 (54%)

13 757 986 (52%)

10 660 003 (40%)

Trier_Medaille

11 899 134

3 635 305 (30%)

3 405 656 (28%)

2 538 093 (21%)

Zoutelande

79 892 313

25 768 379 (32%)

24 911 972 (31%)

20 800 720 (26%)

Всем спасибо за внимание! Еще раз Ссылка на проект

Комментарии (16)


  1. Slav2
    20.05.2024 22:46
    +1

    Попробуйте pngout сжать и сравните размер с вашим


    1. mynameco Автор
      20.05.2024 22:46
      +2

      Спасибо! Добавил в таблицы и pngout для сравнения.


      1. jpegqs
        20.05.2024 22:46
        +1

        Сравните с lossless режимом WebP2 и JPEG XL, тогда и поговорим. PNG ни о чём, только ленивый его не обойдёт. С PNG вообще сравнивать странно, он плохо подходит для сжатия фото. Иначе, для не знакомых с темой людей, всё выглядит будто вы сделали что-то многообещающее, раз PNG обошли.


        1. Zara6502
          20.05.2024 22:46
          +5

          В массе своей выбирается PNG не потому что он лучший для фото, а потому что почти все инструменты если и умеют во что-то сжимать без потерь, то это и есть PNG, то есть на самом деле им пользуются не потому что он жмёт хорошо, а потому что нет альтернативы. А так как PNG сжимает без потерь, то и сравнивать нужно с PNG.


          1. pvvv
            20.05.2024 22:46
            +1

            с абсолютно тем же успехом можно raw/bmp просто пожать zipом, что можно сказать, внутри png и происходит. Для схем/чертежей с кучей одинаковых сгруппированых пикселей вполне работает, как и QOI впрочем, а для реальных фотографий - не особо.


            1. mynameco Автор
              20.05.2024 22:46
              +3

              Ох и отхвачу я минусов. Я проверил. WebP жмет лучше. Даже почитал как он устроен. Еще рассказал друзьям, они сказали, так вот что это за хрень, которую сохраняет гугл хром, и никто не открывает эту картинку. Если почитать историю png, они взяли доступный алгоритм без лицензий. Мне кажется за webp будущее. Если будет поддерживаться аппаратно кодек VP8 где он кодирует ключевые кадры, то во всех машинах мира, он будет лучшим. Но как я понимаю, если он до сих пор не популярен, хотя его двигает Google, значит есть какие то интеллектуальные, лицензионные проблемы. С Уважением.


              1. Zara6502
                20.05.2024 22:46

                ко мне часто попадают картинки HEIC и WEBP, приходится специально запускать FAR, лезть в папку и запускать скрипт который прогоняет CONVERT в JPG и только потом начинать работать с этими изображениеми. Проблема не в форматах или степенях сжатия, а в том - насколько широко эти форматы поддерживаются софтом.

                Вот мало кто помнит, но еще в 2007 году никто не обменивался PDF, слали или JPG или TIFF. И только когда все утюги мира стали сканировать в PDF - формат стал практически стандартом для многостраничных сканов.


                1. orekh
                  20.05.2024 22:46

                  И зря, уж лучше бы cbz занял место pdf. Простой формат, в отличии от невероятной хтони внутренностей проприетащины адобе.


                  1. Zara6502
                    20.05.2024 22:46

                    Мы не обсуждаем PDF.


            1. Zara6502
              20.05.2024 22:46

              и как много программ умеет открывать на редактирование raw пожатый zipом? Или вы мне предлагаете вместо оперативной работы с изображением гонять туда-сюда файлики?


              1. orekh
                20.05.2024 22:46

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


                1. Zara6502
                  20.05.2024 22:46

                  вы перекладываете проблемы ковбоев на шерифа, так нельзя, я точно не хочу чтобы MS определяла мою работу с файлами.


  1. Dmitri-D
    20.05.2024 22:46

    надо выписывать на С или Rust и сравнивать скорость с какой скоростью такой формат можно будет выводить, если интегрировать в браузеры или любые другие UI.
    Разница в величине компрессии, пожалуй, играет роль если она в районе 30% и выше (очень субъективное суждение).


  1. pvvv
    20.05.2024 22:46
    +7

    Теперь осталось взять арифметическое кодирование (которое позволяет приблизится к теоретическому n*log(n) и иметь дробное количество битов/символ, в отличии от Хаффмана, где меньше 1 бита/символ не бывает). А вместо простого дельта кодирования брать сумму/разность двух пикселей, потом сумму/разность от "суммарных" пикселей с предыдущего шага и так N раз пока не пиксели не закончатся ну или пока не надоест. В результате получится почти jpeg2000.


    1. sci_nov
      20.05.2024 22:46

      Да, но только какой нибудь rANS, например, или FSE. Range Encoder (арифметический кодер) медленный. Для изображений имеет смысл применить несколько заранее подготовленных линейных фильтров (4 например) и выбирать наилучший. Соответственно, индексы фильтров группировать отдельно и также кодировать FSE.


  1. Zara6502
    20.05.2024 22:46

    Для решения этой проблемы используют кодирование числа переменной длины

    Дельта-код Элиаса не хотите попробовать?