Поделиться
Программист, не имеющий представления о сжатии данных, создал суперзамену формату 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.
Эксперименты с замером производительности алгоритмов сжатия и распаковки разработчик производил над набором из 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.
Предложенный алгоритм имеет линейную сложность, поэтому его производительность не зависит от объема входных данных, то есть в данном случае – размера изображения.
Короткая ссылка
