Nibnib: формат изображений со сверхбыстрой распаковкой для RP2350

В репозитории на GitHub описан Nibnib, экспериментальный формат изображений, настроенный на предельную скорость распаковки. Он возник как опыт: какое качество картинки и какую скорость можно получить при выводе по DVI на микроконтроллере RP2350. На устройствах такого класса обычно используют изображения с малой глубиной цвета и поиск цвета по палитре. Бюджет составляет примерно 6 тактов на пиксель: этого хватает на чтение пикселя, обращение к палитре и запись в строковый буфер, но запаса почти не остаётся.

В основе Nibnib тоже лежит палитра, но в ней хранится не абсолютный цвет, а разность (дельта). По утверждению README, это заметно повышает качество на плавных участках по сравнению с обычными палитровыми изображениями. Скорость достигается тем, что из одного входного байта декодируются сразу два пикселя, что даёт сжатие 4 бита на пиксель (4bpp).

Декодирование работает парами пикселей. Последний декодированный пиксель удваивается, затем из потока читается байт, по нему берётся 32-битное значение из палитры и прибавляется к удвоенному предыдущему пикселю. Получаются два 16-битных пикселя в формате RGB 565; младшие 16 бит, левый пиксель. Внутренний цикл на Rust состоит из чтения байта, одного сложения с обращением к палитре и двух записей. Реализация декодера «на лету» для RP2350 входит в демонстрацию изображений в репозитории vic-2350.

Формат определяется именно процессом декодирования, а кодирование, это поиск в пространстве возможных закодированных изображений такого, которое распакуется в максимально похожую копию оригинала. Здесь поиск сильно асимметричен: нынешний кодировщик на порядки медленнее декодера. Для сравнения в README указано, что в JPEG на базовом уровне кодирование и декодирование занимают примерно одинаковое время.

Поиск ведётся по двум направлениям: выбор палитры и выбор кодовых слов. В первой версии палитра состоит из «куба» малых значений дельты и блока случайных значений, выбранных по взвешенным гауссианам. Куб нужен, чтобы можно было достичь значений около нуля и полной шкалы без переполнения; без него появляются заметные артефакты. Случайную часть настраивали вручную, исходя из предположений о разумных значениях: малая разность между двумя пикселями делает картинку глаже, но ухудшает передачу резких границ. Палитра пока не подбирается под конкретное изображение, автор называет это явной возможностью улучшить качество.

Основной цикл кодирования концептуально прост: перебираются все 256 записей палитры, выбирается запись с минимальной ошибкой, а затем эта ошибка распределяется по весам Флойда, Стейнберга, так что следующие пиксели подгоняются под исходное значение плюс накопленные взвешенные ошибки. Это похоже на популярную диффузию ошибки с квантованной палитрой, но там обычно обрабатывают один пиксель за раз, а здесь выбирается запись, минимизирующая ошибку сразу двух пикселей, причём сумма весит чуть больше разности: зрение человека чувствительнее к низким пространственным частотам.

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

Сам формат устроен предельно просто: по 2 байта на ширину и высоту, затем 256 32-битных записей палитры, затем строки по порядку. Каждая строка начинается с двух пикселей RGB 565, за которыми идут (ширина − 2) / 2 байт индексов палитры; шаг строки округляется до кратного 4 байтам. Другой метаданных нет. Формат не предназначен для архивного хранения и скорее пригоден там, где он тесно встроен в декодер. Код распространяется на выбор по лицензии Apache 2.0 или MIT.

Ключевые факты

Nibnib, экспериментальный формат изображений для вывода по DVI на микроконтроллере RP2350; бюджет, примерно 6 тактов на пиксель.
Из одного байта декодируются два пикселя RGB 565 через палитру из 256 32-битных записей, в которой хранится дельта, а не абсолютный цвет; итоговое сжатие, 4bpp.
Кодировщик асимметричен: он перебирает все 256 записей палитры с диффузией ошибки Флойда, Стейнберга и на порядки медленнее декодера.
Палитра пока не адаптируется к изображению, а артефакты тянутся вправо от резких границ из-за жадного поиска; улучшения возможны без смены декодера.
Формат не предназначен для архива; код доступен по лицензии Apache 2.0 или MIT на выбор.

Почему это важно

Проект показывает, как выжимать качество из жёстко ограниченного бюджета в несколько тактов на пиксель: вся сложность переносится в кодировщик, а декодер сводится к одному сложению и обращению к палитре. Идея хранить в палитре дельту вместо абсолютного цвета, простой приём, который, по словам README, заметно улучшает плавные области по сравнению с обычной палитровой графикой. Это нишевая, но наглядная иллюстрация асимметричных схем сжатия.

Кому это важно

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

Как это применить

Реализация декодера для RP2350 включена в демонстрацию изображений в репозитории vic-2350; кодировщик и описание формата лежат в репозитории Nibnib. Лицензия на выбор: Apache 2.0 или MIT. Формат задуман для тесной интеграции с декодером, а не как универсальный контейнер, так что брать его стоит под конкретную задачу вывода кадра на ограниченном устройстве.

Можно ли доверять

Все утверждения о качестве и скорости взяты из README самого репозитория и подаются автором как описание базовой рабочей версии. Конкретных замеров нет: ни скорости декодирования, ни тактов, измеренных на RP2350, ни метрик качества (вроде PSNR или SSIM), ни сравнения с JPEG или другими палитровыми форматами по числам. Сравнение с JPEG в тексте качественное. Заявление о лучшем качестве, чем у палитровых изображений, пока не подкреплено цифрами.

Риски и подводные камни

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