Siterem

Создание сайтов под ключ

Пн-Вс: 12:00-22:00 (MSK)
Заказать звонок

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

Источник: habr.com

Обратный звонок

Оставьте свой телефон и мы свяжемся с Вами

Заявка принята, спасибо!
Мы вскоре свяжемся с Вами ;)