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