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

0
62

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

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

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

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

Программист, не имеющий представления о сжатии данных, создал суперзамену формату 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

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

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

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

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

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

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

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

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

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