Разработчик представил 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 раз, но при этом размер итогового файла получается таким же или незначительно меньше. Также разработчик заявил о том, что планирует применить полученный опыт для создания эффективного видеокодека.
