[Перевод] QOI: как сжимать изображения в 20 раз быстрее STBI и без потерь

У представленного месяц назад формата сжатия изображений QOI уже есть реализации на различных языках, плагины для GIMP, Xn View MP и Paint.NET, а также dll для отображения эскизов в Проводнике Windows. Можно скачать изображение и сразу посмотреть на него здесь. Подробности о qoi от автора формата читайте под катом.


Представляем QOI — Quite OK Image Format. Он без потерь сжимает RGB- и RGBA-изображения до размера PNG, обеспечивая при этом ускорение в 20–50 раз при сжатии и ускорение в 3–4 раза при распаковке. Всё однопоточно, без SIMD. И до глупости просто.

В начале я хочу сказать, что не имею ни малейшего представления о том, что делаю. Я не любитель компрессии и едва понимаю, как работает кодирование Хаффмана и DCT. К счастью, QOI не использует ни то, ни другое. Я просто прорабатывал некоторые идеи, которые, как я подумал, могли бы помочь сжимать изображения. Результат меня весьма удивил.

Ради чего? Краткая тирада

Форматы файлов ужасны. Я совершенно не люблю PNG, JPEG или, ещё хуже, MPEG, MOV, MP4. Они от сложности рвутся по швам. Абсолютно каждая мелочь в них кричит: «Дизайн консорциума!».

Некоторое время назад я немного побаловался с MPEG. Основные идеи сжатия видео в MPEG гениальны, а ещё более гениальны они для 1993 года, но получившийся формат файла — мерзость.

Я представляю себе заседание группы экспертов по движущимся изображениям, где какой-то случайный иск потребовал, чтобы у формата был способ указать, что видеопоток защищён авторским правом. И битовый флаг copyright вошёл в стандарт и успешно остановил пиратство в кино ещё до его начала.

Промышленный стандарт MPEG задуман тридцать лет назад, все патенты давно истекли, а профессиональный интерес — потерян. Но священная спецификация, названная ISO/IEC 11172-2, — это хорошо охраняемый секрет, раскрываемый только тем, кто выложит 200 долларов, чтобы спонсировать ISO.

Есть альтернативные, открытые видеокодеки, но они опять же кошмарно сложные. Они конкурируют с последними технологиями, требуют огромных библиотек, требовательных к вычислениям и сложных в работе. Альтернативы PNG конкурируют между собой по степени сжатия, при этом сложность их постоянно возрастает.

Безусловно, есть рынок кодеков для видео, аудио и изображений, которые разменяли степень сжатия на скорость и простоту, но никто не служит ему. Эти ребята могли бы, но там всё запатентовано.

Да, stb_image избавил всех нас от мучений с libpng и поэтому используется в бесчисленных играх и приложениях. Какое-то время назад я пытался сделать то же самое для видео с помощью pl_mpeg и добился некоторого успеха.

Но со всем тем, чему я научился, почему бы не отойти на шаг назад и не реализовать простую схему сжатия, способную конкурировать с PNG, но без сотрясений? Или почему бы не реализовать простую схему сжатия видео, похожую на MPEG, но в нормальном формате?

И я возился со всем этим, хотел взять элементы MPEG-1 и упростить парсинг, ускорить его на графическом процессоре, но наткнулся на решение в смысле формата изображения без потерь, иногда способного конкурировать с PNG. Степень сжатия немного хуже, но формат проще.

Технические детали

Cпецификация формата файла QOI обновлена. Пожалуйста, ознакомьтесь с ней на qoiformat.org. QOI кодирует и декодирует изображения за один проход, при этом он проходит через каждый пиксель только один раз. Пиксель кодируется разными способами.

Результирующие значения упаковываются в блоки, которые начинаются с 2–4-битного тега (указывающего один из этих четырёх методов), за которым следует ряд битов данных. Все эти блоки (биты тегов и данных) выровнены по байтам, поэтому между блоками не нужно выкручиваться с битами.

Вот четыре метода сжатия:

1. Пробег по пикселям

Если текущий пиксель точно такой же, как и предыдущий, длина пробега увеличивается на 1. При обнаружении пикселя, который отличается от предыдущего, длина пробега сохраняется в закодированных данных, а текущий пиксель упаковывается одним из трёх других методов. Фрагмент длины пробега имеет два варианта, вариант зависит от количества необходимых битов:

QOI_RUN_8 { u8 tag : 3; // b010 u8 run : 5; // 5-bit run-length repeating the previous pixel: 1..32
}
QOI_RUN_16 {
u8 tag : 3; // b011
u16 run : 13; // 13-bit run-length repeating the previous pixel: 33..8224
}

2. Индекс в ранее увиденном пикселе

Энкодер сохраняет массив пробега из 64 пикселей, с которыми сталкивался ранее. Обнаружив, что текущий пиксель присутствует в этом массиве, программа сохраняет индекс в этом массиве в поток. Чтобы кодирование занимало время O(n), в этом массиве выполняется только один поиск.

Позиция поиска определяется «хешем» значения rgba (на самом деле просто r^g^b^a). Линейный поиск или бухгалтерия сложнее не слишком улучшит сжатие, но немного замедлит работу.

QOI_INDEX {
u8 tag : 2; // b00
u8 idx : 6; // 6-bit index into the color index array: 0..63
}

3. Разница с предыдущим пикселем

Когда текущий цвет пикселя не слишком далёк от предыдущего, разница с предыдущим пикселем сохраняется в потоке. Здесь есть три варианта, в зависимости от того, насколько велика разница. Основное внимание уделяется значению RGB; изменения альфа-канала обходятся дороже:

QOI_DIFF_8 {
u8 tag : 2; // b10
u8 dr : 2; // 2-bit red channel difference: -1..2
u8 dg : 2; // 2-bit green channel difference: -1..2
u8 db : 2; // 2-bit blue channel difference: -1..2
}
QOI_DIFF_16 {
u8 tag : 3; // b110
u8 dr : 5; // 5-bit red channel difference: -15..16
u8 dg : 4; // 4-bit green channel difference: -7.. 8
u8 db : 4; // 4-bit blue channel difference: -7.. 8
}
QOI_DIFF_24 {
u8 tag : 4; // b1110
u8 dr : 5; // 5-bit red channel difference: -15..16
u8 dg : 5; // 5-bit green channel difference: -15..16
u8 db : 5; // 5-bit blue channel difference: -15..16
u8 da : 5; // 5-bit alpha channel difference: -15..16
}

4. Полные значения rgba

Если все три предыдущих метода не подходят, значения r, g, b, a (но только те, которые отличаются от предыдущего пикселя) сохраняются в потоке в виде полных байтов:

QOI_COLOR {
u8 tag : 4; // b1111
u8 has_r: 1; // red byte follows
u8 has_g: 1; // green byte follows
u8 has_b: 1; // blue byte follows
u8 has_a: 1; // alpha byte follows
u8 r; // red value if has_r == 1: 0..255
u8 g; // green value if has_g == 1: 0..255
u8 b; // blue value if has_b == 1: 0..255
u8 a; // alpha value if has_a == 1: 0..255
}

Вот и всё. Если у вас есть минута, пожалуйста, прочитайте исходник qoi.h.

Что дальше?

Серьёзно, я ошеломлён. BMP и TIFF имеют кодировку длины пробега, GIF работает с LZW. Но что находится между ними? Ничего. Почему? Я обнаружил, что поле для работы между RLE и LZW достаточно велико, чтобы провести над ним не один день. Работа над QOI шла очень весело. Видеть, как каждое сделанное изменение повлияло на степень сжатия, — это захватывало.

Проработанный лучше, QOI может служить основой видеокодека без потерь для скринкастов и т.п. Ускорение SIMD для QOI также было бы круто, но (исходя из моих очень ограниченных знаний о некоторых инструкциях SIMD на ARM), формат, похоже, не очень хорошо подходит для этого. Может быть, кто-то с опытом больше может пролить на это свет?

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

На этом автор заканчивает свой пост. А научиться решать проблемы при помощи алгоритмов вы сможете на наших курсах:

Узнайте подробности акции.

Другие профессии и курсы

Data Science и Machine Learning

Python, веб-разработка

Мобильная разработка

Java и C#

От основ — в глубину

А также

Читайте так же:

  • Google Ads внедрил новые функции в интеллектуальное назначение ставокGoogle Ads внедрил новые функции в интеллектуальное назначение ставок Google Ads внедряет несколько новых функций. Чтобы рекламодателям было проще управлять стратегиями интеллектуального назначения ставок и повышать эффективность кампаний. Основные сигналы для «Целевой рентабельности инвестиций в рекламу» и «Максимальной ценности конверсии» Основные […]
  • [Перевод] Вся правда о Hi-Res: что скрывают аудиоформаты высокого разрешения[Перевод] Вся правда о Hi-Res: что скрывают аудиоформаты высокого разрешения Одно из самых интересных событий, которые произошли в мире аудио за последние годы — небывалый рост популярности форматов высокого разрешения (Hi-Res). Среди причин появления в своё время новых форматов — неудовлетворённость качеством звучания CD, ведь на заре эпохи компакт-дисков все […]
  • После расследования регулятора Virgin Galactic вновь разрешили летатьПосле расследования регулятора Virgin Galactic вновь разрешили летать Федеральное управление гражданской авиации США (FAA) провело расследование инцидента с отклонением от курса корабля Virgin Galactic во время спуска на Землю в июле и разрешило возобновить полеты компании. В будущем Virgin Galactic будет более тесно взаимодействовать с FAA.Расследование […]
  • Портативный ВЧ ваттметр Микран (отзыв)Портативный ВЧ ваттметр Микран (отзыв) Вместо введенияНедавно в моей домашней лаборатории появился USB сенсор мощности PLS6 российской фирмы Микран. Тут важно упомянуть, что домашняя лаба не равно для хобби, приборы мне необходимы для моей основной работы.Рис.1 мой экземпляр ваттметраОтмечу, что он был доступен в демо, то […]