Всем привет! В этой статье я опишу алгоритм работы формата сжатия изображений без потерь. Сжатие использует известные методики, которые и дали ему название. Проект начинался с простых экспериментов, которые вышли из под контроля. Не смотря на то, что формат чаще сжимает лучше чем 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 байт |
Выше - статистика вхождений для алгоритма Хаффмана собиралась по предыдущей строке. Если собирать по всем предыдущим строкам, то получается еще меньше:
|
Размер 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 байт |
Статистика по алгоритмам:
|
Delta H count : 71 |
Статистика тестовых изображений с 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%) |
Всем спасибо за внимание! Еще раз Ссылка на проект
Автор: Альберт
