DisCollection.ru

Авторефераты и темы диссертаций

Поступления 20.10.2008

Материалы

загрузка...

Алгоритмы и программные средства поиска векторов похожести для сжатия видеоданных

Потапов Павел Вячеславович, 20.10.2008

 

Практическая ценность:

– Реализована программная система «MEFramework» в виде фильтра DirectShow. Программная система «MEFramework» позволяет оценивать вычислительную сложность и эффективность алгоритмов поиска векторов похожести. Отличительной особенностью данной программной системы является возможность раздельно задавать оценочную функцию и алгоритм поиска векторов похожести. Это позволяет оценивать эффективность алгоритмов поиска векторов похожести при использовании различных оценочных функций.

– В качестве модулей системы «MEFramework» программно реализованы алгоритмы локального поиска, а также наиболее эффективные из известных алгоритмов поиска векторов похожести.

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

– Разработанный алгоритм поиска векторов похожести был внедрен компанией ООО «МэйнКонцепт-Дивикс» в составе коммерческого продукта «Mainconcept MPEG-2 Video Encoder».

Основные положения, выносимые на защиту:

1. Разработанная программная система «MEFramework» позволяет количественно оценивать вычислительную сложность и степень компрессии, достигаемую при использовании различных алгоритмов поиска векторов похожести.

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

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

Внедрение результатов:

Алгоритм поиска векторов похожести, разработанный в рамках данной диссертационной работы, внедрен в коммерческий продукт компании ООО «МэйнКонцепт-Дивикс», Mainconcept MPEG-2 Video Encoder. Программная система «MEFramework» используется компанией ООО «МэйнКонцепт-Дивикс» для проведения внутренних испытаний алгоритмов поиска векторов похожести.

Апробация работы. Основные положения работы докладывались на следующих семинарах и конференциях:

1. XLIII международная научная студенческая конференция «Студент и научно-технический прогресс» - Новосибирск, 2005. Доклад отмечен дипломом третьей степени.

2. XI Всероссийская научная конференция студентов-физиков и молодых учёных - Екатеринбург, 2005.

3. Всероссийская научно-техническая конференция студентов, аспирантов и молодых ученых «Научная сессия ТУСУР-2005» - Томск, 2005. Доклад отмечен почётной грамотой «за лучший доклад».

4. Всероссийская научно-техническая конференция студентов, аспирантов и молодых ученых «Научная сессия ТУСУР – 2007» - Томск, 2007.

5. Научно-практическая конференция «Электронные средства и системы управления: итоги реализации программы развития электроники и IT-технологий в Томской области» - Томск, 2008. Доклад отмечен дипломом первой степени.

6. Научно-технические семинары кафедры автоматизированных систем управления, ТУСУР.

Публикации. По теме диссертации автором опубликованы 10 работ, в том числе 4 статьи в научных периодических журналах, из них 1 в журналах из перечня ВАК [7], 5 докладов опубликовано в материалах научных конференций и семинаров, зарегистрирована программа в Отраслевом фонде алгоритмов и программ (ОФАП) [10].

Структура и объем диссертации: Диссертационная работа состоит из введения, трех глав и трех приложений. Содержит 142 страницы, 11 таблиц, 48 рисунков и 3 приложения. Список цитируемой литературы содержит 98 наименований.

Содержание работы

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

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

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

При сжатии видеопоследовательности кадры могут быть сжаты как отдельные изображения, путём устранения пространственной избыточности, подавления мелких деталей, представления в виде оптимального математического кода и.т.д. Степень компрессии можно существенно увеличить, если учесть тот факт, что в пределах коротких интервалов времени (промежутков между кадрами) видеоизображение обычно изменяется незначительно. Неподвижную часть кадра можно кодировать как разницу с предыдущим кадром, а движущуюся часть описать при помощи векторов похожести. Вектором похожести (motion vector) называют смещение между координатами блока, используемого для предсказания, и координатами текущего блока. Процесс устранения временной избыточности с использованием векторов похожести называется компенсацией движения (motion compensation). При сжатии с применением метода компенсации движения для нахождения векторов похожести используются алгоритмы поиска векторов похожести, обеспечивающие поиск векторов, позволяющих достичь наибольшей степени компрессии.

Векторы похожести можно искать для различных по форме и размеру участков кадра. Поиск может осуществляться для целого кадра, для каждого пикселя отдельно, либо для участков произвольной формы. На практике чаще всего используют метод согласования блоков. Этот метод подразумевает разбиение кадра на большое число блоков (обычно прямоугольных). Каждый блок одного кадра (блок поиска) сравнивается с блоками предыдущего кадра, и оценивается вероятность того, что они являются фрагментами одного и того же участка изображения. Затем вычисляются компоненты смещения блока из исходного положения до положения, которое наилучшим образом согласуется с блоком поиска, что дает величину и направление вектора похожести. Точность оценки вектора находится на уровне одного элемента, поскольку обнаружение согласования блоков основано на сравнении значений элементов изображения. Размеры области поиска определяют максимальную величину вектора похожести, которая может быть измерена, поскольку этот параметр ограничивает максимальную скорость перемещения объекта, которую возможно зафиксировать.

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

1. M(Vx,Vy) – для определения значения этой функции производится сжатие блока с использованием текущего вектора похожести. Значением оценочной функции является размер сжатого блока в битах. При использовании данной оценочной функции производится непосредственная минимизация размеров сжатых блоков кадра.

оценочные функции вычисляются следующим образом:

- значения яркости пикселей текущего и предыдущего кадров соответственно.

В первой главе приведены описания следующих алгоритмов поиска векторов похожести: алгоритма полного перебора, алгоритма поиска по алмазу, NTTS, CBA, ADZS, PMVFAST, EPSZ.

Во второй главе обосновывается выбор критериев оценки эффективности алгоритмов поиска векторов похожести: размер S сжатой видеопоследовательности и количество вычислений K оценочной функции. Сжатие видеопоследовательности производится согласно стандарту MPEG-2. При сжатии используется постоянный коэффициент квантования для всех блоков видеопоследовательности. Это обеспечивает одинаковый уровень вносимых при компрессии искажений для сравниваемых алгоритмов.

Для выполнения сравнительного анализа алгоритмов поиска векторов похожести реализована программная система «MEFramework» в виде фильтра DirectShow. Состав программной системы представлен на рис. 1.

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

На вход «MEFramework» подаются несжатые видеоданные. «MEFramework» производит сжатие входных видеоданных согласно стандарту MPEG-2. Компенсация движения производится c использованием выбранного алгоритма поиска векторов похожести и оценочной функции (блок MC (motion compensation) на рис. 1). Далее видеоданные подвергаются дискретному косинусному преобразованию (блок DCT – discrete cosine transform), квантованию (блок Q – quantization) с постоянным значением коэффициента квантования и арифметическому кодированию при помощи кодов переменной длинны (блок VLC – variable length coding). Для получения восстановленного кадра, использующегося в качестве опорного при компрессии следующего кадра, производится декодирование текущего кадра. Для этих целей после операции квантования кадр подвергается деквантованию (в блоке Q-1 – dequantization, inverse quantization) и обратному дискретному косинусному преобразованию (в блоке IDCT – inverse discrete cosine transform). На выходе MEFramework имеем сжатый в соответствии со стандартом MPEG-2 видеопоток. Декодирование видеопотока может быть осуществлено любым MPEG-2 декодером.

Рис. 1. Состав разработанной программной системы

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

Преимущества разработанной программной системы состоят в следующем:

– выходом программной системы является сжатая с применением стандарта MPEG-2 и указанного алгоритма поиска векторов похожести входная видеопоследовательность. Компрессия производится с постоянным коэффициентом квантования, что позволяет оценивать качество найденных векторов похожести непосредственно по степени сжатия видеопоследовательности;

– оценка вычислительной сложности алгоритма поиска векторов похожести производится по количеству вызовов оценочной функции. Такой подход позволяет получить оценку вычислительной сложности алгоритма, не зависящую от производительности вычислительной системы, на которой производилось тестирование;