Рисунок 1 Схема отбора блоков по алгоритму MPO
При этом в алгоритме MPO поиск вектора движения для каждого блока не зависит от результатов поиска на более ранних итерациях алгоритма, что делает разработанный алгоритм наиболее эффективным для сложных траекторий движения.
В целях сокращения передаваемой информации о движении, было выработано требование объединения блоков в соответствии с выбранным критерием принадлежности локальной области. При этом рассматриваются два случая, приводящих к снижению качества: потеря областей малого движения и небольшое количество пикселов для блоков малого размера. Для первого случая выбрано ограничение размеров блока до 64х64 пиксела, а для второго случая предложено разделение сравниваемых блоков по различным их типам.
аб
ашине»
Для сокращения передаваемой информации о движении, как комбинация блочного и объектного подхода, были проанализированы следующие алгоритмы разделения блоков:
разделение по направлению движения в соответствии с алгоритмом (VJ - Vectors Joint based), который выполняется в три этапа:
сортировка векторов движения по принципу увеличения параметров движения;
разделение векторов движения в соответствие с допустимым уровнем отклонения параметров движения на группы;
выравнивание поля векторов за счет значений векторов локальной окрестности.
разработанный алгоритм разделения в соответствии с маской классификации по мажоритарному признаку (PoI ? Points of Interest based). При этом маска формируется в соответствии с этапами, приведенными на рисунке 4.
Выбор алгоритма выделения опорных точек основан на исследовании следующих алгоритмов: алгоритм ADC (Absolute Difference Criteria), алгоритм Харриса, а также алгоритм SIFT (Scale Invariant Feature Transform). По результатам проведенного анализа алгоритм SIFT с размером ядра Гаусса 5x5 был выбран в качестве основы для расчета маски классификации.
Рисунок 4 Последовательность этапов алгоритма PoI
На рисунке 5 представлены зави- симости PSNR и вычислительных затрат Q, выражаемых количеством базовых операций на блок кадра, от размеров блока, выражаемых минималь-ным размером S и максимальным прираще-нием по каждой из сторон d, а также RD-характе-ристика.
VSBM для последовательности «Теннис»
Анализ результатов показал, что предложенный алгоритм способствует улучшению показателей сжатия воспроизведенной видеопоследовательности (если PSNR > 30дБ, то качество работы алгоритма оценки и компенсации движения считается хорошим). Алгоритм VSBM+PoI+MPO превзошел существующие алгоритмы VSBM и VSBM+VJ+MPO как с точки зрения качества восстановленной видеопоследовательности, так и с точки зрения коэффициента её сжатия при схожей вычислительной сложности. Необходимо также отметить, что при максимальном значении размера блока, равном 64Ч64, проявляется эффект мажоритарности.
Третий раздел посвящен исследованию алгоритмов кодирования преобразованием.
На основе данных, представленных в разделе 1, разработаны быстрые алгоритмы преобразования Хартли (с наилучшим качеством восстановленной видеопоследовательности) и косинусного преобразования (с наилучшим коэффициентом сжатия).
Для начала сформулируем принципы, на основе которых будут построены предлагаемые быстрые алгоритмы. Данные преобразования допускают разделение области расчета на подобласти. Используя корреляцию соседних областей, можно существенно сократить вычислительные затраты. Кроме того, присутствие симметричных и ассиметричных компонент дает дополнительную возможность декомпозиции сигнала.
Нисходящий алгоритм быстрого трехмерного преобразования Хартли (3D-БПХП) на основе неразделимого ядра преобразования для блоков целой размерности можно сформулировать следующим образом:
,
где u, v, t - размерность вычисляемого целого блока, r - номер частичной суммы,
,
N, M, P - размерность куба-кадра, , а abc - трехбитный двоичный код, определяющий номер формируемой суммы.
Блоки промежуточной размерности формируются иерархически при помощи более крупных блоков целой размерности на основе вычисляемых частичных сумм по формуле:
где u', v', t' - размерность вычисляемого промежуточного блока. Промежуточный блок может иметь размерность, уменьшаемую вдвое хотя бы по одной из координат.
Рисунок 6 Схема итерации алгоритма 3D-БПХП с соответствующими связями вычитания, сложения
Если размер блока уменьшается по одному или по трем аргументам для функции cas, то знак суммы считается отрицательным. При уменьшении размеров ни по одному или по двум аргументам для функции cas знак не изменяется.
Иерархический процесс продолжается, пока размерность целого блока не составит 2x2 пиксела. Схема одной итерации предложенного алгоритма представлена на рисунке 6.
Алгоритм быстрого трехмерного косинусного преобразования на основе вычисления текущего отсчета по набору предыдущих отсчетов (3D-БКПП) можно сформулировать следующим образом:
где ,
,
,
,
а abc- трехбитный троичный код, каждый разряд которого принадлежит множеству {-1, 0, 1}.
Необходимо отметить, что переменный размер матрицы преобразования формируется на основе блочных структур изображений, полученных на этапе оценки и компенсации движения, а временная компонента выбирается равной расстоянию между опорными кадрами.
В ходе исследования было выявлено, что трехмерные алгоритмы позволили вдвое увеличить коэффициент сжатия видеопоследовательности по сравнению с двумерными вариантами алгоритмов при незначительном ухудшении ее качества при восстановлении по сравнению с двухмерными вариантами алгоритмов. Это объясняется тем, что алгоритмы выполняют преобразование не только в пространстве, но и во времени, устраняя соответствующую избыточность.
В результате исследования для кадров последовательности «Теннис» получены зависимости, представленные на рисунках 7 и 8.
Рисунок 7 Вычислительная сложность алгоритмов кодирования преобразованием (Q1, Q2-количество умножений и сложений, V-размер стороны блока).
D-БКПП кодирования преобразованием.
Предложенный быстрый алгоритм 3D-БПХП позволил на 30 % сократить число операций сложения/умножения на пиксел кадра видеопоследовательности за счет иерархического расчета коэффициентов преобразования по сравнению с предложенным Джеонгом И. алгоритмом. Также он позволил повысить качество восстановленной видеопоследовательности на 2 % и коэффициент ее сжатия на 1,5 % по сравнению с алгоритмом на основе фиксированного размера ядра (3D-БПХФ).
Предложенный быстрый алгоритм 3D-БКПП позволил на 40 % сократить число операций умножения на пиксел кадра видеопоследовательности при незначительном увеличении числа сложений по сравнению с предложенным Алшибами Х. алгоритмом. Также он обеспечил повышение качества восстановленной видеопоследовательности и коэффициента ее сжатия на 3 % по сравнению с подходом на основе фиксированного размера ядра (3D-БКПФ).
Преимущество алгоритмов на основе переменного ядра преобразования объясняется использованием адаптивно выбираемого размера матрицы преобразования для областей с мелкими деталями и для областей фона соответственно.
В четвертом разделе исследуется алгоритм адаптивной интерполяции центрального отсчета, а также разработанный алгоритм интерполяции с адаптивным размером ядра.
В ходе исследования было выявлено, что адаптивный алгоритм центрального отсчета (рисунок 9) и разработанный алгоритм с адаптивным размером ядра (рисунок 10) позволяют в лучшей степени сократить блокинг - эффект, полученный в результате кодирования преобразованием на основе блоков.
Рисунок 9 Адаптивная интерполяция центрального отсчета
Рисунок 10 Интерполяция с адаптивным размером ядра: 1 - 2х2, 2 - 4х4, 3 - 8х8, 4 - 16х16, 5 - 32х32, о - опорные отсчеты, с - центральные отсчеты
Алгоритм интерполяции с адаптивным размером ядра является рекурсивным алгоритмом, в рамках которого центральный основной и побочные симметричные отсчеты вычисляются нисходящим образом в рамках адаптивного алгоритма центрального отсчета, причем направление предсказания определяется в целом для блока в соответствии с критерием минимизации суммарной ошибки интерполяции и передается кодовым словом длиной 2 бита на блок. Оставшиеся пикселы являются крайними и вычисляются по алгоритму «прямой крест», преимущества качественных характеристик которого показаны в разделе 1.
Необходимо отметить, что для блоков различного размера, полученного на этапе оценки и компенсации движения, применяются соответствующие ядра интерполяции, обеспечивающие совместимость при стыковке блоков различного размера.
При этом интерполяционный остаток (разностное изображение) предлагается формировать только для опорных кадров, а для ссылочных кадров предлагается полагать все коэффициенты, кроме опорных, равными нулю.
Сравнительные оценки алгоритмов интерполяции, представленные на рисунке 11, показали возможность увеличения коэффициента сжатия видеопоследовательности на 20% за счет алгоритмов интерполяции, и в среднем на 30% за счет предложенного алгоритма интерполяции.
В пятом разделе предлагается комплексный метод сжатия видеоданных, основанный на сочетании предложенных алгоритмов, а также описывается программная реализация предложенного метода.
На рисунке 12 представлена модель кодера. Пунктирной стрелкой обозначена связь по данным блоков временной и пространственной модели.
В рамках пространственной модели отсчеты сигнала поступают на вход анализатора кодирования, затем осуществляется интерполяция отсчетов сигнала по алгоритму, представленному в главе 4, его переупорядочивание зигзаг - сканированием и квантование алгоритмом кодового квантования, являющегося частным случаем сеточного квантования, который использует вектора надежности битовых плоскостей кадра.
Энтропийное кодирование осуществляется модифицированным кодом Хаффмана переменной длины.
Рисунок 12 Модель кодера
Блок анализатора кодирования (АК) представляет собой анализатор движения, описанный в разделе 3 с расширенным функционалом. На основании значений порога анализатора T1 и T2 , равных 4 и 14 соответственно, осуществляется выбор 2D/3D режима. Анализатор кодирования формируется в соответствии с условием:
где ,
,
при ,,
где с и с' значения яркостей пикселов текущего и предыдущего кадров.
Двухмерные алгоритмы кодирования преобразованием реализуются строчно-столбцовым методом.
В ходе исследования было выявлено, что лучшие значения RD - характеристики показали значения порогов анализатора T3 и T4 , равные 8 и 17.
Благодаря симметричности алгоритма, декодирование осуществляется аналогично в обратном направлении.
В ходе диссертационной работы были разработаны программные средства в среде разработки Visual C++. Блок-схема взаимодействия основных процедур разработанного приложения представлена на рисунке 13.
Программные средства позволяют:
Рисунок 13 Блок-схема взаимодействия
осуществлять выбор основных параметров кодирования;
отображать результаты оценки и компенсации движения в виде кадра, с обозначением блоков и векторов движения;
осуществлять оценку основ-ных показателей сжатия, а именно качества, коэффи-циента сжатия и битрейта;
осуществлять сжатие видеопоследовательности по заданному набору параметров, воспроизводить и сохранять результаты сжатия в формате mkv. Экспериментальные результаты, представленные на рисунке 14, показали, что качество работы предложен-ного видеокомпрессора не уступает видеокомпрессору на основе стандарта H.264.
Представленные зависимости приведены для двух крайних случаев для последовательностей наименьшей (min) и наибольшей (max) динамичности.
Применение предложенного метода сжатия видеоданных позволило повысить качество восстановленной видеопоследовательности на 5%, коэффициент ее сжатия на 30% по сравнению с методом VP8, а также сократить необходимый битрейт на 30% и вычислительные затраты на 20%.
В заключении представлены основные результаты работы.
Основные результаты работы
В результате исследования алгоритмов выбора блоков для сравнения предложен иерархический алгоритм выбора блоков для сравнения.
В ходе исследования алгоритмов оценки и компенсации движения разработан алгоритм классификации блоков кадра на основе маски, построение которой осуществляется в рамках предложенного алгоритма построения маски.
Предложен иерархический алгоритм быстрого преобразования Хартли на основе неразделимого ядра преобразования переменного размера.
Разработан алгоритм быстрого косинусного преобразования с переменным размером ядра преобразования, базирующийся на расчете коэффициентов преобразования по ряду предыдущих отсчетов.
Предложено использовать интерполяцию отсчетов сигнала для устранения блокинг - эффекта на выходе блока кодирования преобразованием, а также разработан алгоритм интерполяции на основе адаптивного выбора размера ядра.
Разработаны модель и метод сжатия видеоданных, основанные на сочетании предложенных алгоритмов.
Выполнена программная реализация предложенного метода сжатия и получены численные результаты компрессии видеопоследовательностей различной динамичности, согласно которым общий выигрыш от использования предлагаемого метода составляет порядка 25 %.
Список публикаций по теме диссертации