У представленного месяц назад формата сжатия изображений 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 имеют RLE, GIF работает с LZW. Но что находится между ними? Ничего. Почему? Я обнаружил, что поле для работы между RLE и LZW достаточно велико, чтобы провести над ним не один день. Работа над QOI шла очень весело. Видеть, как каждое сделанное изменение повлияло на степень сжатия, — это захватывало.

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

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

Бенчмарки.

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

• Курс «Алгоритмы и структуры данных»

• Профессия C++ разработчик

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