Всем привет! В этой статье я опишу алгоритм работы формата сжатия изображений без потерь. Сжатие использует известные методики, которые и дали ему название. Проект начинался с простых экспериментов, которые вышли из под контроля. Не смотря на то, что формат чаще сжимает лучше чем 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%) |
Всем спасибо за внимание! Еще раз Ссылка на проект
Комментарии (16)
Dmitri-D
20.05.2024 22:46надо выписывать на С или Rust и сравнивать скорость с какой скоростью такой формат можно будет выводить, если интегрировать в браузеры или любые другие UI.
Разница в величине компрессии, пожалуй, играет роль если она в районе 30% и выше (очень субъективное суждение).
pvvv
20.05.2024 22:46+7Теперь осталось взять арифметическое кодирование (которое позволяет приблизится к теоретическому n*log(n) и иметь дробное количество битов/символ, в отличии от Хаффмана, где меньше 1 бита/символ не бывает). А вместо простого дельта кодирования брать сумму/разность двух пикселей, потом сумму/разность от "суммарных" пикселей с предыдущего шага и так N раз пока не пиксели не закончатся ну или пока не надоест. В результате получится почти jpeg2000.
sci_nov
20.05.2024 22:46Да, но только какой нибудь rANS, например, или FSE. Range Encoder (арифметический кодер) медленный. Для изображений имеет смысл применить несколько заранее подготовленных линейных фильтров (4 например) и выбирать наилучший. Соответственно, индексы фильтров группировать отдельно и также кодировать FSE.
Zara6502
20.05.2024 22:46Для решения этой проблемы используют кодирование числа переменной длины
Дельта-код Элиаса не хотите попробовать?
Slav2
Попробуйте pngout сжать и сравните размер с вашим
mynameco Автор
Спасибо! Добавил в таблицы и pngout для сравнения.
jpegqs
Сравните с lossless режимом WebP2 и JPEG XL, тогда и поговорим. PNG ни о чём, только ленивый его не обойдёт. С PNG вообще сравнивать странно, он плохо подходит для сжатия фото. Иначе, для не знакомых с темой людей, всё выглядит будто вы сделали что-то многообещающее, раз PNG обошли.
Zara6502
В массе своей выбирается PNG не потому что он лучший для фото, а потому что почти все инструменты если и умеют во что-то сжимать без потерь, то это и есть PNG, то есть на самом деле им пользуются не потому что он жмёт хорошо, а потому что нет альтернативы. А так как PNG сжимает без потерь, то и сравнивать нужно с PNG.
pvvv
с абсолютно тем же успехом можно raw/bmp просто пожать zipом, что можно сказать, внутри png и происходит. Для схем/чертежей с кучей одинаковых сгруппированых пикселей вполне работает, как и QOI впрочем, а для реальных фотографий - не особо.
mynameco Автор
Ох и отхвачу я минусов. Я проверил. WebP жмет лучше. Даже почитал как он устроен. Еще рассказал друзьям, они сказали, так вот что это за хрень, которую сохраняет гугл хром, и никто не открывает эту картинку. Если почитать историю png, они взяли доступный алгоритм без лицензий. Мне кажется за webp будущее. Если будет поддерживаться аппаратно кодек VP8 где он кодирует ключевые кадры, то во всех машинах мира, он будет лучшим. Но как я понимаю, если он до сих пор не популярен, хотя его двигает Google, значит есть какие то интеллектуальные, лицензионные проблемы. С Уважением.
Zara6502
ко мне часто попадают картинки HEIC и WEBP, приходится специально запускать FAR, лезть в папку и запускать скрипт который прогоняет CONVERT в JPG и только потом начинать работать с этими изображениеми. Проблема не в форматах или степенях сжатия, а в том - насколько широко эти форматы поддерживаются софтом.
Вот мало кто помнит, но еще в 2007 году никто не обменивался PDF, слали или JPG или TIFF. И только когда все утюги мира стали сканировать в PDF - формат стал практически стандартом для многостраничных сканов.
orekh
И зря, уж лучше бы cbz занял место pdf. Простой формат, в отличии от невероятной хтони внутренностей проприетащины адобе.
Zara6502
Мы не обсуждаем PDF.
Zara6502
и как много программ умеет открывать на редактирование raw пожатый zipом? Или вы мне предлагаете вместо оперативной работы с изображением гонять туда-сюда файлики?
orekh
Мне кажется, что это изначальная проблема проводника файлов операционной системы или файловой системы. Было бы во многом удобно, если бы файлы-контейнеры подключались как папки и работать с ними можно было бы бесшовно.
Zara6502
вы перекладываете проблемы ковбоев на шерифа, так нельзя, я точно не хочу чтобы MS определяла мою работу с файлами.