PackMan - Lossless Video Codec
© Riba 2018

1. Идея.

Идея создать свой Lossless видео-кодек родилась у меня не на пустом месте. Для своего Нано-плеера (nanoPlayer@STM32F407) нужно было написать программу для воспроизведения видео без потерь, потому что с “квадратами” и “муарами”, которые дают MJPEG и H264, я уже наигрался! Сильное сжатие – это конечно хорошо, но иногда хочется смотреть видео в хорошем качестве. Тогда на помощь приходят Lossless видео-кодеки. Что значит Lossless? Это слово означает, что кодер сжимает видео-поток таким образом, чтобы декодер при разжатии выдавал его без изменений. Проще говоря - разжатый поток одинаков с исходным.

Правда, тут некоторые создатели кодеков и обычные пользователи допускают ошибку, неправильно трактуя слово “Lossless”. Дело в том, что можно получить на выходе декодера изображение без потерь, но выходной поток не будет совпадать с входным. Например, увеличение градации цветовой компоненты на единицу Вы вряд ли заметите :) (особенно при числе бит на точку от 6:6:6 и выше).

Между прочим, многие так называемые “Lossless”-кодеки дают именно такой поток, особенно когда используется преобразование цветовых пространств (к примеру, RGB в YUV4:2:0 и обратно). Тогда имеет место ввести ещё один термин – BitExact – бит-экзактность, который означает равенство с точностью ДО 1 БИТА! Другими словами, если в результате сравнения все байты исходного и декодированного потоков будут одинаковы, то кодек считается битэкзактным. Если кодек битэкзактный, то он Lossless. Обратно может быть неверно, пример дал выше.

Из Lossless-кодеков видео известны:

- HuffYUV – самый древний кодек, уже устарел. Плюс – быстрый. Минус – плохо жмёт.

- Dirac – малоизвестный кодек. Плюс – жмёт лучше предыдущего. Минус – медленный.

- Lagarith – современный кодек. Плюс – жмёт лучше предыдущего. Минусы не нашёл.

- MSU – самый лучший кодек по сжатию на сегодняшний день! Минусы – чудовищно большое время для кодирования, очень медленное декодирование сильно сжатого потока. Закрытый (исходники недоступны)

- MJPEG2000 Lossless – малоизвестный кодек. Жмет лучше HuffYUV, но хуже Dirac.

Можно было портировать один из этих кодеков на STM32F407, особенно Lagarith, но мне захотелось создать свой видео-кодек, который имел бы шанс превзойти по степени сжатия вышеперечисленные, НО при этом сохранить возможность декодирования на микроконтроллере STM32F407@168 MHz. И мне удалось! Правда, не сразу. Путём проведения многочисленных экспериментов, была найдена оптимальная последовательность этапов кодирования-декодирования.



2. Архитектура кодека.

Сразу скажу, что решающим этапом в становлении архитектуры кодека были технические характеристики элементов nanoPlayer: процессор STM32F407@168 МГц и OLED дисплей с разрешением 160x128 пикселей RGB 6:6:6. А также выбор числа FPS равный 12, как оптимальный для просмотров мультфильмов. Число FPS накладывает лишь ограничение на скорость декодирования на STM32F407, на архитектуру кодека он не влияет.

Переход к числу бит от 8 к 6, уже даёт уменьшение объёма исходных данных на 25%. При сравнении степеней сжатия разных кодеков (об этом рассказано дальше), это учтено, перед сжатием исходный поток видео предварительно обрабатывается – младшие 2 бита обнуляются (чтобы сравнение кодеков было на равных условиях). Мало того, 6-битное представление цветовых компонент сыграло в пользу при реализации конвейеров кодирования-декодирования: двух свободных бит хватило, чтобы не выйти за пределы значений одного байта при обработке данных, а это делает сжатие более эффективным.

Разработанный видео-кодек при кодировании убирает три избыточности в исходном потоке:

- цветовая избыточность: убирается с помощью преобразования цветового пространства RGB в пространство YCbCr
- пространственная избыточность: убирается с помощью 3- уровневого 2- мерного WaveLet-преобразования
- межкадровая избыточность: убирается с помощью вычисления межкадровой разницы

Все этапы преобразований в конвейере обратимы. Декодированный поток битэкзактен по отношению к исходному потоку (с обнулёнными 2 битами в младших разрядах).
Структура конвейера кодера показана на рисунке ниже:



Конвейер декодера – тот же, но в обратном порядке. Рассмотрим каждый этап преобразования в конвейере подробнее.

1) Каждый пиксель во фрейме в формате RGB 6:6:6 преобразуется в формат YCbCr. Это даёт возможность избавиться от цветовой избыточности в кадрах. Используется полностью обратимое преобразование – Reversible Color Transform:

Y=floor((R+(2*G)+B)/4); Cb=B-G; Cr=R-G,

где floor() – операция округления до наибольшего целого, которое меньше или равно аргументу. Не путать с int() !!! Обратное преобразование:

G=Y-floor((Cb+Cr)/4); R=Cr+G; B=Cb+G;

Практическая реализация кодека делает ещё пару вещей перед этим преобразованием:
обнуляет 2 младших бита каждой цветовой компоненты RGB 8:8:8 – просто сдвигает вправо на 2 разряда: 8:8:8 => 6:6:6
меняет местами цветовые компоненты R и B, потому что принято хранить R в младшем байте, B – в старшем, но видеопамять устроена совсем наоборот! :)

2) Три уровня вейвлет-преобразования по двум измерениям (2D). Тип вейвлета: Lifting based 5/3 LeGall, успешно использующийся в Lossless JPEG2000. Число уровней оптимально: меньше – понижает эффективность сжатия, а больше – увеличивает нагрузку на процессор (принципиально только для микроконтроллеров). Данный тип вейвлета хорош тем, что коэффициенты, которые он выдаёт, не превышают пределов значения одного байта (при условии, что входные данные 6 бит, 2 бита свободно). Это преобразование удаляет пространственную избыточность в кадре.

3) Для устранения межкадровой избыточности используется разность между текущим и предыдущим кадрами. Из вейвлета текущего кадра арифметически вычитается вейвлет предыдущего. Переполнение байтов (заворачивание значений через ноль), которое тут может произойти, не портит данные, так как при декодировании такое переполнение ликвидируется обратным сложением с вейвлетом предыдущего кадра!

Для потенциальной реализации функции перемотки добавлена вставка ключевого фрейма. Это несколько ухудшает сжатие, но не настолько, чтобы полностью отказываться от ключевых фреймов. В данной реализации кодека каждый 12-й фрейм – ключевой, что обеспечивает точность перемотки 1 секунду при 12 FPS. Очевидно, что первый фрейм – всегда ключевой.

4) Далее преобразованные данные поступают на энтропийный кодер Хаффмана, который призван закодировать данные компактным образом. Суть его предельно проста: наиболее повторяющиеся байты кодируются более короткими битовыми цепочками – чем выше частота повторения байта, тем короче будет его битовый код. Тут следует отметить, что при обработке одного фрейма, кодирование Хаффмана делается отдельно по цветовым компонентам в следующей последовательности: dY, dCb, dCr. Буква “d” означает разницу между вейвлетами, полученную на предыдущем этапе. Отдельно, потому что есть ограничения на размер оперативной памяти в STM32F407, но на степень сжатия это не влияет.

5) Далее кодер выполняет сжатие RLE. Используется такой тип RLE: старший бит первого байта хранит тип цепочки: повтор или нет, остальные 7 бит – число символов (повторяющихся или нет), затем сами символы (разные или символ повтора). Остальные типы RLE оказались менее эффективными.
Затем кодер сравнивает размер сжатых данных по Хаффману и дополнительно с RLE. Если есть выигрыш от RLE, то в выходной поток пойдёт фрейм с двойным сжатием. Если нет, то на выход пойдёт фрейм со сжатием Хаффмана. Экспериментально были рассмотренные следующие комбинации сжатия:

- только RLE
- только Хаффман
- RLE, затем Хаффман
- Хаффман, затем RLE

При обработке видео 25-минутной длительности была собрана статистика по комбинациям. Оказалось, что только RLE сжатие выгодно было в 1% случае, RLE+Huffman был выгоден в 5% случаев. Остальные комбинации были выгодны чаще всего и примерно в одинаковом процентном соотношении! Поэтому было решено использовать только две комбинации:

- только Хаффман
- Хаффман, затем RLE

Естественно, при декодировании надо знать, как пожат фрейм и его размер. Для этого было принято решение – ввести 2 байта перед началом каждой трети фрейма. Трети фрейма – это отдельно пожатые компоненты Y, Cb, Cr отдельно взятого фрейма. Одна треть несжатого фрейма занимает ровно 20 кБ = 160x128 (разрешение OLED дисплея nanoPlayer, 1 байт на цветовую компоненту). Тогда при допуске, что размер одной пожатой трети фрейма не превысит 80% от размера исходной, достаточно 14 бит для представления размера сжатого фрейма: от 1 до 16384 байт! Оставшиеся старшие 2 бита несут в себе следующую информацию:

- бит 15: =0 – одиночное сжатие (Хаффман), =1 – двойное сжатие (Хаффман+RLE)
- бит 14: =0 – разностный фрейм, =1 – ключевой фрейм

Пояснительные рисунки:





Порядок следования байтов – Little Endian. В самом начале файла – сигнатура 8 байт “Packman\0”.



3. Реализация кодека.

Кодек реализован в виде отдельных программ: кодера и декодера. Исходные тексты программ написаны на языках C/C++, Assembler. Поддерживаемые платформы и операционные системы:

- ПК: кодер и декодер. Не оптимизированы по скорости. DOS, Win32
- nanoPlayer: только декодер. Оптимизирован по скорости. STM32F407 BareMetal

Реализация для nanoPlayer использует SIMD-инструкции, DMA и ассемблерные вставки. Декодер входит в состав всего проекта “nanoPlay_PackMan” , а это:

- FLAC audio-player (оптимизированный по скорости декодер от RockBox)
- PackMan video-player (декодер рассматриваемого кодека)
- FatFS & SDIO (поддержка файловой системы на картах SD micro)



4. Ограничения кодека.

1) Частота следования фреймов не должна превышать 12 FPS. Данное ограничение продиктовано для сохранения оставшегося ресурса скорости процессора на декодирование FLAC.

2) Размер кадра 160x128. Глубина цвета 18 бит на точку 6:6:6. Ограничение продиктовано использованием OLED-дисплея UG-6028 в nanoPlayer.

3) Карта памяти SD micro должна иметь класс скорости не ниже 4. На картах без обозначения класса скорости воспроизведение звука FLAC идёт иногда с заиканиями – в этом случае частота смены кадров меньше 12 FPS.

4) Размер одной сжатой трети фрейма по любой цветовой компоненте не должен превышать 16 кБ, тоесть максимально худший коэффициент сжатия не должен быть хуже 1.25. На практике коэффициент сжатия выходит всегда больше (если же конечно не жать видео с белым шумом :) ).

5) Кодек гарантирует битэкзактность старших 6 бит каждой цветовой компоненты (если исходные данные представлены в формате RGB 8:8:8). Младшие 2 бита отбрасываются и не обрабатываются. Ограничение продиктовано использованием OLED-дисплея.



5. Результаты.

Как всегда неоднозначны! Разные видео показывают разные результаты. Хорошо жмутся видео с большой длительностью. Ниже приведены примеры сжатия разными кодеками (для всех кодеков в качестве исходного потока брался RGB 6:6:6):

1) Мультфильм:

- исходный размер: 1.01 ГБ, что при пересчёте из 8:8:8 бит в 6:6:6 бит даст 775.68 МБ
- Lagarith: 282 МБ
- MSU: 207 МБ
- PackMan: 254 МБ

2) Фильм:

- исходный размер: 877 МБ, что эквивалентно 657.75 МБ при пересчете на 6 бит
- Lagarith: 241 МБ
- MSU: 246 МБ
- PackMan: 225 МБ

Остальные кодеки (HuffYUV, Dirac, Lossless MJPEG2000) были ещё хуже.

Есть ещё версия кодека с арифметическим кодером вместо кодера Хаффмана+RLE, сжатие в этом случае ещё более эффективно, для примера:

- Кодеры Huffman + RLE: 225 МБ
- Арифметический кодер: 206 МБ

Но ресурсов процессора STM32F407@168 MHz не хватает для нормального воспроизведения FLAC звука одновременно с видео. Поэтому версия этой конфигурации кодека не зарелижена. Опытным путём установил, что арифметический кодер (реализация Q-кодера) в 2 раза медленнее кодера Хаффмана.



6. Исходный материал.

Весь код написан мной за исключением следующих библиотек:

- RLE (декодер пришлось переписывать, содержал ошибку)
- Huffman
- Le Gall 5/3 Lifting scheme (взят алгоритм)

Источники: интернет, github.com, pudn.com .



7. Поставка кодека.

Для ПК кодек Packman поставляется в следующих видах:

- Исполняемые файлы для ОС DOS (DPMI), Win9x, WinXP : папка DOS
- Исполняемые файлы для ОС Win32, Win64 : папка Win32
- Исходные тексты программ : папка _SRC_
- bat-скрипт для облегчения запуска и образец видео: папка Test
- readme.txt

Под DOS доступен ещё плеер, воспроизводящий видео во время декодирования.

Дополнительные утилиты (ffmpeg, ffplay) не входят в эту поставку, поскольку они громоздки и легко находятся в интернете.

Утилиты “контроль битэкзактности” и “конвертер 8:8:8 в 6:6:6” доступны для скачивания в другом архиве.

Для STM32F407 – в составе ПО для плеера nanoPlayer и только декодер, который оптимизирован по скорости. Файлы декодера:

- PackMan.inc (главный файл декодера)
- файлы в папке Huffman
- файлы в папке RLE



8. Использование ffmpeg и ffplay.

Программа ffmpeg используется для получения сырого потока видео из любого другого формата:

ffmpeg.exe -i 0.mp4 -s 160x128 -r 12 -c:v rawvideo -pix_fmt rgb24 -qscale:v 0 -an 888.rgb

-i 0.mp4 – исходный файл видео (может быть любого формата)
-s 160x128 – размер кадра
-r 12 – частота следования фреймов
-c:v rawvideo – сырой видеопоток
-pix_fmt rgb24 – формат данных RGB 8:8:8
-qscale:v 0 – самое лучшее качество, которое только обеспечивает ffmpeg
-an – не использовать дорожку со звуком
888.rgb – выходной файл, сожержит сырые кадры в формате RGB 8:8:8

Далее файл 888.rgb уже можно жать кодером PackMan. Для проверки битэкзактности (если это нужно в целях контроля) файл 888.rgb конвертируется в 666.rgb специальной утилитой (её упомянул выше). Декодированный поток сравнивать на битэкзактность именно с 666.rgb, а не с 888.rgb!

Цепочка с проверкой на бит-экзактность:

(mp4, avi, mpeg, …) => ffmpeg.exe => 888.rgb => 888to666.exe => 666.rgb => encoder.exe => 666.pak => decoder.exe => 666.dec => ffplay.exe

Если проверка на бит-экзактность не нужна, цепочка короче:

(mp4, avi, mpeg, …) => ffmpeg.exe => 888.rgb => encoder.exe => 666.pak => decoder.exe => 666.dec => ffplay.exe

Для nanoPlayer на STM32F407:

(mp4, avi, mpeg, …) => ffmpeg.exe => 888.rgb => encoder.exe => 666.pak => nanoPlayer


Команда ffplay для проигрывания декодированного видео на ПК:

ffplay.exe -f rawvideo -video_size 160x128 -pixel_format rgb24 -framerate 12 666.dec



9. Перспективы.

Получился отличный Lossless Bitexact видео-кодек, заточенный под железо nanoPlayer, который соперничает с Lagarith и MSU по степени сжатия и скорости декодирования. Даёт сильный выигрыш в сжатии на длинных видео, на коротких видео уступает Lagarith и MSU.

Способен декодировать видео 160x128, RGB 6:6:6, 12FPS и совместно работать с FLAC-декодером аудио 24 kHz, 16 bit, 1 channel, 2000 byte blocksize – на микроконтроллере STM32F407@168 Mhz.

По сути – первая версия (нулевая). Для лучших результатов – отказаться от кодера Хаффмана и применить Арифметический кодер (нужно оптимизировать под STM32F407). Возможно, провести ревизию алгоритма.

Кодек не претендует на звание “мега-супер-пупер быстрый кодек с офигенным сжатием”, и создавался в целях “разминки мозгов” и личных интересов.

Проект может быть полезен для всех тех, кто не равнодушен к теме ЦОС жаждет написать что-то своё для микроконтроллеров.

Предложения и эксперименты по улучшению скорости декодера и увеличению степени сжатия кодера приветствуются! :)



Программы кодера, декодера, исходные тексты программ, тестовый образец, bat-скрипт - для ПК (DOS, Win9x, WinXP, Win32, Win64): ТУТ

Оптимизированная программа декодера для STM32F407 - для nanoPlayer: ТУТ ( + параллельно декодирование FLAC)

Статья про nanoPlayer и его программное обеспечение: http://vrtp.ru/index.php?act=categories&CO...le&article=3712

Обсуждение, новые прошивки, исходники, алгоритмы, схемотехника: http://vrtp.ru/index.php?showtopic=29688&st=90


Обновление 02.08.2018:

Адаптация кодека PackMan rev.2 на STM32H743 :PackMan320.
Подробнее тут: http://vrtp.ru/index.php?showtopic=29688&v...ndpost&p=784391


Исходники кодера и декодера PackMan320 для ПК (Win32) + скомпилированные бинарники:
http://vrtp.ru/index.php?act=Attach&type=post&id=784392


Исходники декодера PackMan320 + декодера FLAC + FatFs + SDIO + LCD для STM32H743 (отладка Nucleo-H743).
http://vrtp.ru/index.php?act=Attach&type=post&id=784393

Рабочий плеер Video+Audio. Файлы кидать на SD карту парами (0.fla , 0.pak, 1.fla, 1.pak, ...)
Карта подключена к SDIO1.
Тестовые файлы FLAC + PackMan там же.


Немножко конвертеров + краткий гайд как конвертить:
http://vrtp.ru/index.php?act=Attach&type=post&id=784394

Видео декодеров PackMan320 + FLAC в действии на игровой консоли на Nucleo-H743:






Таблица соединений:
http://www.vrtp.ru/index.php?act=Attach&type=post&id=784400

© Riba 22.03.2018