Разделы

ПО Свободное ПО Интернет Интернет-ПО Техника

Программист, не имеющий представления о сжатии данных, создал суперзамену формату PNG

Представлен новый легковесный и очень простой формат компрессии картинок без потерь Quite OK Image (QOI). Он позволяет в десятки раз быстрее сжимать растровые изображения в цветовой модели RGBA по сравнению с популярным сегодня PNG при незначительно отличающемся итоговом размере файла. Автор QOI признается, что практически ничего не понимает в алгоритмах сжатия, а идея формата к нему пришла во время работы над проектом в смежной области.

Создан «убийца» PNG?

Создан новый формат сжатия растровых изображений, использующих цветовую модель RGB(A), без потери качества. Разработка получила название QOI (Quite OK Image, «вполне нормальное изображение»). Ее отличают простота и лаконичность реализации, а также высокая скорость компрессии/декомпрессии.

По заявлению автора формата и эталонной реализации, программиста Доминика Саблевски (Dominic Szablewski) из Германии, скорость кодирования изображения в формате QOI в 20-50 раз выше по сравнению с использованием распространенного в интернете PNG (Portable Network Graphics, «переносимая сетевая графика»). По быстроте декодирования QOI также превосходит PNG, однако не столь значительно – в три-четыре раза. При этом размер сжатого QOI-файла сопоставим с PNG-файлом, содержащим аналогичную картинку.

PNG – это растровый формат хранения графической информации, использующий сжатие без потерь по алгоритму Deflate. Формат был представлен в 1996 г. в качестве свободной альтернативы проприетарному GIF.

szablewski-600.png
Программист-игродел представил новый формат сжатия изображений QOI

Эксперименты с замером производительности алгоритмов сжатия и распаковки разработчик производил над набором из 185 изображений. Среди них разнообразные скриншоты, обои рабочего стола, фотографии людей и природы, комиксы и текстуры. Для кодирования/декодирования в формате PNG использовались открытые библиотеки libpng и stb_image.

Исходный код открыт для всех

Исходный код всех материалов, имеющих отношение к QOI опубликован на хостинге Github и доступен на условиях свободной лицензии MIT.

По состоянию на 29 ноября 2021 г. проект состоит всего из трех файлов: заголовочный qoi.h содержит реализацию функций кодирования/декодирования изображения; qoiconv.c – утилиту командной строки для преобразования файлов из формата PNG в QOI и обратно; qoibench.c – инструмент-обертка для сравнения скорости кодирования с использованием libpng, stb_image и qoi.h.

Объем кода эталонной однопоточной реализации составляет 492 строки, конвертера – еще 76 строк, без учета комментариев. Дополнительно сторонними разработчики подготовлены реализации кодировщиков и декодировщиков на языках Go, Zig и Rust.

Автор не может – сообщество поможет

Автор подчеркивает, что совершенно не разбирается в алгоритмах сжатия. «Я понятия не имею, что творю, – предупреждает Саблевски в своем сообщении, размещенном в его личном блоге. – Я едва понимаю принцип работы алгоритма кодирования Хаффмана и как выполняется дискретное косинусное преобразование».

Алгоритм Хаффмана был создан в 1952 г. аспирантом Массачусетского технологического института (MIT) Дэвидом Хаффманом (David Huffman). Этот метод кодирования информации и его модификации широко используются в различных программах сжатия, в частности, он задействован в методе Deflate, который применяется при упаковке данных в формате PNG.

Дискретное косинусное преобразование (Discrete Cosine Transform, DCT) – это математическое преобразование, например, применяемое в алгоритмах сжатия данных с потерями, в том числе MPEG (видео) и JPEG (статичные изображения).

Кроме того, изначально перед Саблевски не стояла задача создать «убийцу PNG». Специализирующийся на разработке игр программист, по собственному признанию, «возился с идеей создания простой схемы сжатия, похожей на MPEG, но с вменяемым форматом файла» и внезапно пришел к QOI.

Тем не менее, проект привлек внимание программистов-энтузиастов, которые моментально предложили целый ряд изменений, направленных на улучшение нового формата. Сам Саблевски в комментариях на Github признается, что не ожидал такого интереса к собственной разработке, которую он называет «до глупости простой» (stupidly simple): «Сказать, что я удивлен тем количеством внимания, которое этому уделяется, было бы преуменьшением».

Особенности метода сжатия

Как объясняет Саблевски в своем блоге, QOI кодирует и декодирует изображение в один проход, то есть каждый пиксель (минимальный элемент растрового изображения) обрабатывается алгоритмом единожды. Закодирован пиксель может быть четырьмя разными способами, в зависимости от параметров его «соседа».

Если анализируемый алгоритмом пиксель по цвету (записываются в формате RGB или RGBA) совпадает с предыдущим, то вместо записи его полной характеристики счетчик повторений увеличивается на единицу . Таким образом, данный алгоритм сжатия, известный как RLE (Run-length encoding, «кодирование повторов»), будет обеспечивать высокую степень сжатия при наличии множества точек одного цвета, расположенных в ряд по горизонтали.

Александр Осипов, МегаФон: Эффективность киберзащиты вырастет, если снизится рутинная нагрузка на специалистов
безопасность

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

Алгоритм предполагает формирование и поддержание в актуальном состоянии массива из 64 последних проанализированных пикселей. Если анализируемый пиксель совпадает с одним из «запомненных» кодировщиком, то сохраняется соответствующий ему индекс.

Когда оптимизировать входной поток данных не представляется возможным (три предыдущих способа не применимы), записывается полное значение цвета в формате RGBA.

Предложенный алгоритм имеет линейную сложность, поэтому его производительность не зависит от объема входных данных, то есть в данном случае – размера изображения.

Дмитрий Степанов