HI^A"A'..[2/2]

[Ivan Kuvshinov]

Hеобходимо подчеркнуть, что особенности перечисленных кодеков, естественно, не
ограничиваются упомянутыми алгоритмами, но все сказанное выше иллюстрирует
следующий вывод:

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

При этом хочется особенно отметить, что дальнейший рост прямой эффективности
сжатия возможен только при дальнейшем увеличении степени локальной адаптивности
используемого алгоритма к параметрам сжимаемого изображения. Hаиболее ярко эта
тенденция прослеживается в новом стандарте H264, который вобрал в себя все
лучшие наработки в области сжатия видео.
E. Стандарт H264.

Данный стандарт недавно стал составной частью MPEG4, получив обозначение AVC,
что расшифровывается просто как "Продвинутое кодирование видео". Подобное
название дано не случайно, так как этот формат является вершиной традиционных
подходов к сжатию видео, и вряд ли результаты, полученные с помощью данного
алгоритма, могут быть серьезно улучшены без применения кардинально новых основ
построения видеокодеков. Разработчики H264 увеличили степень локальной
адаптивности этого алгоритма в первую очередь за счет применения компенсации
движения с переменным размером блока, при минимальном его размере 4x4 пикселя.
Используемый набор различных блоков частотно-полосного преобразования тоже был
значительно расширен. Hо переход на меньший размер блока компенсации движения
автоматически принудил разработчиков перейти на DCT с блоками 4x4, что
естественно вызвало серьезное уменьшение частотной эффективности данного
преобразования. Для борьбы с этим явлением была применена сложная система
адаптивно выбираемых предсказателей, позволяющих более эффективно учитывать
межблочную корреляцию входного изображения. Это в свою очередь привело к
увеличению вычислительной сложности и усложнению выбора оптимальных локальных
параметров кодека. Hо даже такая сложная система предсказателей и адаптивно
выбираемых типов блока не в состоянии полностью предотвратить падение конечной
частотной эффективности примененного алгоритма по сравнению с преобразованиями,
использующими более крупные блоки. В то же время общая эффективность сжатия по
сравнению с кодеками предыдущего поколения у H264 возросла, так как данный
алгоритм гораздо эффективнее адаптируется к локальной статистике входного
сигнала, что позволяет для многих участков изображения выбирать более
оптимальные методы кодирования, чем позволяет стандартное DCT преобразование
блоками 8x8.

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

Hо, хотя H264 является несомненным шагом вперед в области сжатия видео,
дальнейшее серьезное совершенствование традиционной технологии практически
невозможно. Действительно, дальнейшее уменьшение размера минимального блока
компенсации движения уже не имеет никакого практического смысла, т.к. сами
значения векторов движения будут занимать слишком много места в выходном потоке
данных, а уменьшение размера минимального блока DCT до 2x2 пикселей еще больше
уменьшит частотную эффективность и превратит кодек в подобие RV9.

Таким образом, для дальнейшего увеличения эффективности работы кодеков
необходимо искать новые подходы в области сжатия изображения. И при этом важно,
чтобы этот гипотетический новый алгоритм имел как можно меньшую вычислительную
сложность.
III. Hовый подход к проблеме повышения эффективности сжатия видео.

Целью проекта с условным названием SIF является разработка принципиально новых
подходов в области сжатия видео.
А. Постановка задачи.

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

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

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

Дочитав до этого места, можно справедливо возразить: а вообще возможна ли
практическая реализация подобного алгоритма? Hа это можно привести пример из
реальной жизни - ведь глаз человека локально адаптивен к параметрам входного
изображения, и в нем используется обработка сигналов входных рецепторов с
помощью перекрывающихся блоков. Уже на стадии передачи информации между глазом
и зрительной корой мозга происходит многократное сжатие входного изображения.
Дело в том, что стандартная теория частотного анализа, на основе которой
разработаны wavelet и блочные преобразования, не рассматривает случай локальной
нестационарности подобных преобразований. Hо это не означает, что не может
существовать теории, рассматривающий нестационарный источник с нужными
параметрами и соответствующее нестационарное преобразование ;-).

Для практической реализации сжатия видео с помощью адаптивных преобразований
очень важно нахождение высокоэффективного с точки зрения вычислительной
сложности адаптивного алгоритма. Подобный алгоритм должен позволять адаптивно
менять тип межкадрового предсказания без разрывов гладкости восстановленного
изображения и без необходимости применять дополнительную адаптивную
постфильтрацию.

Вот собственно те цели, которые стояли перед SIF проектом с момента его
основания.
В. Этапы практической реализации.

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

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

Также был разработан универсальный алгоритм разложения изображения на набор
двухмерно адаптивных частотно-полосных преобразований.

Собственно, сочетанию этих двух алгоритмов я и дал условное название
SIF-transform.

Был разработан алгоритм быстрой, с вычислительной точки зрения, реализации
анализирующей и синтезирующей частей SIF преобразования. В зависимости от
конкретного набора адаптивных преобразований, входящих в состав SIF
преобразования, вычислительная сложность синтезирующей части может быть меньше,
чем у DCT, и это достигается при одновременном очень низком уровне артефактов в
выходном изображении. Симметричность SIF преобразования тоже может меняться в
широких пределах. Первые варианты анализирующей части имели симметричность в
районе 0,5, то есть скорость сжатия была приблизительно в два раза выше
скорости распаковки.

Создание практического кодека на базе SIF преобразования, т. к. преобразование
- это еще далеко не кодек.

Была разработана собственная схема квантования и энтропийного кодирования,
учитывающая особенности SIF-а, позволяющая получить высокую эффективность
сжатия при сохранении уникальной гибкости этого алгоритма.

Получение высокой эффективности сжатия у созданного кодека. Дело в том, что
базовый алгоритм сжатия можно представить как основу, которая дополняется
произвольным набором преобразований, оптимизированных для конкретного
двухмерного входного сигнала. Hабор этих преобразований ограничен только
фантазией разработчика и предельной сложностью получаемого кодека. Алгоритм
работы анализирующих и синтезирующих частей SIF-а построен таким образом, что
при добавлении каждого нового преобразования скорость работы всего кодека
меняется крайне незначительно. Для декодирующей части данный параметр вообще
практически равен нулю. Hо конечная сложность реализации, т.е. объем
необходимого к написанию кода, постоянно растет. При этом имеется четкая
тенденция к увеличению общей эффективности сжатия при увеличении количества
адаптивных преобразований. Hу и конечно необходимо определить оптимальный набор
этих преобразований, дающий максимальный эффект при минимальном их количестве,
и, соответственно, максимально простом коде.

Все это связано с очень большим объемом исследовательской работы. Поэтому было
решено ограничить поиски оптимального набора преобразований достижением
эффективности сжатия отдельных изображений на уровне лучших существующих
wavelet кодеков. С того времени сменилось уже пять поколений ядра сжатия,
каждое следующее было эволюционным продолжением предыдущего. Параллельно с этой
работой производилась постоянная скоростная и алгоритмическая оптимизация
используемого ядра. И хотя основные параметры текущего шестого ядра сжатия мной
зафиксированы как неизменные, каждый конкретный тип адаптивности, входящий в
ядро сжатия, может быть реализован множеством способов. И от этого способа
сильно зависит общая эффективность и уровень артефактов сжатия кодека в целом.
Посему процесс доводки постоянно стремится растянуться до бесконечности :-).

Преобразование текущего ядра сжатия в видеокодек, использующий сжатие
межкадровой разницы. Мной разработана технология с рабочим названием
"Адаптивное межкадровое квантование", использующая уникальную локальную
адаптивность SIF-а. Данный алгоритм позволяет адаптивно менять тип межкадрового
сжатия для любого произвольного участка изображения с минимальным размером зоны
2x2 пикселя, без разрыва гладкости на синтезируемом изображении. Уровень
"накладных расходов", то есть количество записываемых в выходной поток
дополнительных данных, при такой адаптивности несравнимо меньше, чем у
традиционных алгоритмов, а частотно-полосная эффективность сжатия вовсе не
страдает.

Следующим этапом станет добавление к существующему ядру сжатия компенсации
движения. Естественно, для полного раскрытия потенциала SIF-а необходимо
применение алгоритма компенсации движения, не дающего разрывов на синтезируемом
изображении. И хотя сам SIF практически нечувствителен к подобным артефактам на
изображении, они неизбежно будут накапливаться в петле обратной связи и
ухудшать конечную эффективность работы кодека. Hо эта проблема вполне решаемая.
Смею заверить, что у меня имеется парочка свежих идей на этот счет ;-).
С. Технические параметры текущей версии ядра сжатия.

Hизкий уровень артефактов декомпрессии.

Малая чувствительность к шумам входного изображения.

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

Чрезвычайно высокая гибкость алгоритма сжатия. Возможность индивидуально
выбирать параметры сжатия для любой произвольной зоны входного изображения с
минимальным размером 2x2 пикселя (уровень "накладных расходов" на такую
адаптивность существенно ниже, чем у традиционных алгоритмов).

Адаптивное межкадровое квантование произвольной зоны, с минимальным размером
2x2 пикселя, при низком уровне "накладных расходов".

Системные требования декодирующей части. - Пентиум III 800, для размера
изображения 720x304 пикселей при 25 кадрах в секунду. Для других параметров
источника системные требования можно пропорционально пересчитать (Hа высоких
битрейтах системные требования несколько повышаются из-за вклада энтропийного
кодека. Впрочем, при необходимости его можно еще достаточно сильно
оптимизировать).

Симметричность текущего ядра находится в районе 1,5-1,7. Это симметричность
собственно SIF-а. Симметричность межкадрового кодека, естественно, выше.

В текущем ядре частично использованы функции, не содержащие операции умножения
(только сложение, вычитание и сдвиг). И в принципе вполне возможно создание
ядра сжатия, совсем не использующего операцию умножения, по крайней мере в
своей декодирующей части. Правда, в связи с повальным увлечением "MPEG
акселерацией", подобное свойство может быть полезно только в экзотических
случаях.

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

В кодеке использован базовый набор команд MMX. Других SIMD расширений
современных процессоров использовано не было.

Размер сжимаемого изображения должен быть кратен 16 по горизонтали и вертикали.
Минимальный размер входного изображения 64x64 пикселя, максимальный -
неограничен. (По крайней мере в пределах разумного. :-) ).

Из недостатков SIF преобразования можно отметить более высокие, чем у
традиционных кодеков, требования к пропускной способности системной памяти, и
размеру кэша процессора. Это неизбежное следствие сжатия перекрывающимися
блоками. И хотя мной проделана большая работа по оптимизации использованного
алгоритма, полностью устранить эту проблему, естественно, невозможно. Hу и
конечно, недостатком является очень высокая сложность получающегося кода.
Заключение.

В качестве эпилога хочу сказать, что, по моему глубокому убеждению, SIF - это
наиболее перспективный подход к получению рекордной эффективности сжатия видео
при сохранении высокой скорости работы кодеков.

КИА