Разработчик представил Quite OK Image, алгоритм сжатия без потерь со сложностью O(n)

Разработчик Доминик Саблевски (Dominic Szablewski) представил алгоритм QOI (Quite OK Image), который позволяет без потерь сжимать RGB и RGBA изображения до размера файла, аналогичного для формата PNG, но в 20-50 раз быстрее. Автор отметил у себя в блоге, что алгоритм оказался «до глупости простым». Код проекта доступен на GitHub.

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

Особенность Quite OK Image в том, что кодирование и декодирование происходит за один проход по изображению — алгоритм касается каждого пикселя только один раз и при этом каждый пиксель кодируется одним из четырех различных способов.

Результирующие значения записываются в чанки, начиная с 2..4 tag-бита, который указывает на способ кодирования, а затем следует количество данных в битах. Все чанки побайтово выровнены. 

Как уже было сказано выше, алгоритм включает в себя 4 разных типа кодирования пикселей:

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

QOI_RUN_8 {     u8 tag  :  3;   // b010     u8 run  :  5;   // 5-битовый интервал повторения предыдущего пикселя: 1..32 }  QOI_RUN_16 {     u8 tag  :  3;   // b011     u16 run : 13;   // 13-битовый интервал повторения предыдущего пикселя: 33..8224 }

• индексирование ранее просмотренного пикселя: кодировщик хранит массив из 64 ранее просмотренных пикселей и если обнаруживает пиксель, до сих пор хранящийся в массиве, то сохраняет его индекс в поток.

  Для сохранения сложности O(n) в массиве используется только один вид поиска по хешам значения rgba (r^g^b^a). Линейный поиск или другие алгоритмы усложнили бы кодировщик и замедлили бы его.

QOI_INDEX {     u8 tag  :  2;   // b00     u8 idx  :  6;   // 6-битный индекс в массиве цветов: 0..63 }

• отличие от предыдущего пикселя: если цвет текущего пикселя не критично отличается от предыдущего, то разница между этими пикселями записывается в поток. Есть три вида записи, которые выбираются в зависимости от того, насколько велика разница. Примечательно, что обработка альфа-канала занимает больше времени, чем RGB.

QOI_DIFF_8 {     u8 tag  :  2;   // b10     u8 dr   :  2;   // 2-битная разница красного канала: -1..2     u8 dg   :  2;   // 2-битная разница зеленого канала: -1..2     u8 db   :  2;   // 2-битная разница синего канала: -1..2 }  QOI_DIFF_16 {     u8 tag  :  3;   // b110     u8 dr   :  5;   // 5-битная разница красного канала: -15..16     u8 dg   :  4;   // 4-битная разница зеленого канала:  -7.. 8     u8 db   :  4;   // 4-битная разница синего канала:  -7.. 8 }  QOI_DIFF_24 {     u8 tag  :  4;   // b1110     u8 dr   :  5;   // 5-битная разница красного канала: -15..16     u8 dg   :  5;   // 5-битная разница зеленого канала: -15..16     u8 db   :  5;   // 5-битная разница синего канала: -15..16     u8 da   :  5;   // 5-битная разница альфа-канала: -15..16 }

• целые значение RGBA: если три предыдущих способов не удается применить, то в поток сохраняются целые значения пикселя.

QOI_COLOR {     u8 tag  :  4;   // b1111     u8 has_r:  1;   // красный байт     u8 has_g:  1;   // зеленый байт     u8 has_b:  1;   // синий байт     u8 has_a:  1;   // альфа-байт     u8 r;           // значение красного байта, если has_r == 1: 0..255     u8 g;           // значение зеленого байта, если has_g == 1: 0..255     u8 b;           // значение синего байта, если has_b == 1: 0..255     u8 a;           // значение альфа-байта, если has_a == 1: 0..255 }

Автор сравнил работу своего алгоритма с libpng и stb_image. Тесты показали, что qoi обгоняет популярные библиотеки по скорости кодирования и декодирования в 20-50 раз, но при этом размер итогового файла получается таким же или незначительно меньше. Также разработчик заявил о том, что планирует применить полученный опыт для создания эффективного видеокодека.