автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.11, диссертация на тему:Алгоритмы и программные средства поиска векторов похожести для сжатия видеоданных

На правах рукописи

ООЗДЬЫ^-ч^ г

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

АЛГОРИТМЫ И ПРОГРАММНЫЕ СРЕДСТВА ПОИСКА ВЕКТОРОВ ПОХОЖЕСТИ ДЛЯ СЖАТИЯ ВИДЕОДАННЫХ

Специальность 05.13.11 - Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей

Автореферат диссертации на соискание учёной степени кандидата технических наук

2 2 Л Е Н 2008

Томск-2008

003458244

Работа выполнена на кафедре Автоматизированных систем управления ГОУ ВПО «Томский государственный университет систем управления и радиоэлектроники».

Научный руководитель:

Заслуженный деятель науки РФ, доктор технических наук, профессор Кориков Анатолий Михайлович

Официальные оппоненты:

Доктор технических наук, профессор Погребной Владимир Кириллович

Кандидат технических наук, доцент Поляков Алексей Юрьевич

Ведущая организация: Новосибирский государственный

технический университет

Защита состоится « 29 » декабря 2008 г. в 1430 на заседании совета по защите докторских и кандидатских диссертаций Д 212.269.06 при Томском политехническом университете по адресу: 634034, г. Томск, ул. Советская, 84, институт «Кибернетический центр» ТПУ.

С диссертацией можно ознакомиться в библиотеке Томского политехнического университета по адресу: 634034, г. Томск, ул. Белинского, 55.

Автореферат разослан « 28 » ноября 2008 г.

Ученый секретарь

Совета

к.т.н., доцент

М.А. Сонькин

Общая характеристика работы

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

Основополагающие результаты в области теории информации принадлежат ведущим отечественным (В.А. Котельников, А.Я. Хинчин, А.Н. Колмогоров, A.A. Харкевич, JI.M. Финк) и зарубежным (К. Шеннон, С. Голдман, Д. Хоффман, P.M. Грей) ученым.

В настоящее время огромное внимание уделяется разработке алгоритмов сжатия видеоданных, использующих компенсацию движения. Начиная с 1980 года, организации ITU и MPEG последовательно выпускают ряд стандартов сжатия, использующих блочную компенсацию движения: #.261, MPEG-1, MPEG-2/H.262, Н.263, MPEG-4, Я.264 (MPEG-A part-Щ. Использование алгоритмов компенсации движения при сжатии видеоданных позволяет существенно увеличить степень компрессии при том же соотношении сигнал/шум результирующего видео. Параллельно с разработкой новых стандартов сжатия происходит совершенствование алгоритмов поиска векторов похожести. Алгоритм поиска векторов похожести выполняет важнейшую роль в системах сжатия видеоданных, использующих компенсацию движения. От выбора алгоритма поиска векторов похожести напрямую зависит степень компрессии и вычислительная сложность компрессора. Поиск векторов похожести является одним из самых ресурсоемких этапов компрессии видеоданных. Однако сам алгоритм поиска векторов похожести обычно не фиксируется в стандарте сжатия. Таким образом, модуль поиска векторов похожести можно свободно подвергать алгоритмической оптимизации в рамках стандарта сжатия. Использование более эффективного алгоритма поиска векторов похожести даёт значительное конкурентное преимущество над другими компрессорами, реализующими тот же стандарт сжатия. По этой причине разработка алгоритмов поиска векторов похожести является актуальной задачей.

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

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

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

- выполнить анализ существующих алгоритмов поиска векторов похожести;

- разработать программные средства сравнения алгоритмов поиска векторов похожести;

- реализовать и сравнить существующие алгоритмы поиска векторов похожести;

- разработать новую оценочную функцию;

- разработать и реализовать более эффективный по сравнению с аналогами алгоритм поиска векторов похожести.

Объектом исследования является компрессия цифровых видеоданных. Предметом исследования являются алгоритмы поиска векторов похожести, используемые при сжатии видеоданных.

Методы исследования: Результаты диссертации получены с помощью методов математического и имитационного моделирования, методов оптимизации и вычислительной математики. В процессе программной реализации теоретических результатов использовались методы теории алгоритмов, теории структур данных и объектно-ориентированного программирования.

Научная новизна:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Программная система «МЕРгателногЫ используется компанией ООО «МэйнКонцепт-Дивикс» для проведения внутренних испытаний алгоритмов поиска векторов похожести.

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

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

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

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

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

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

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

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

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

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

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

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

Компрессия - это процесс сжатия данных с целью представления

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

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

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

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

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

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

2. Оценочные функции, основанные на минимизации энергии невязки текущего и предсказанного блоков. Для блока размером NxN, имеющего координаты (х,у) оценочные функции вычисляются следующим образом:

SAD(VX ,Vy) = Y£\ll{x + m,y + n)-I„(x + Vx+m,y + V,+ n)|.

п-0 m=0

SSE(VX, V, ) = £ £ (/, (x + m, y + n) - (x + Vx +m,y + Vy + n)} ,

1=0 m=0

где (Vv Vy) - значения вектора похожести, It, /(1 - значения яркости пикселей текущего и предыдущего кадров соответственно.

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

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

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

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

На вход «MEFrameworb> подаются несжатые видеоданные. «MEFramework» производит сжатие входных видеоданных согласно стандарту MPEG-2. Компенсация движения производится с использованием выбранного алгоритма поиска векторов похожести и оценочной функции (блок МС (motion compensation) на рис. 1). Далее видеоданные подвергаются дискретному косинусному преобразованию (блок DCT- discrete cosine transform), квантованию (блок Q - quantization) с постоянным значе-

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

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

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

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

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

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

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

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

- «MEFramework» позволяет производить поиск векторов похожести с точностью до половины пикселя. Данная точность выбрана исходя из ограничений стандарта MPEG-2.

Во второй главе также приведены описания тестовых видеопоследовательностей. Для сравнения алгоритмов поиска векторов похожести были использованы десять видеопоследовательностей, рекомендованных организацией ITU для проверки цифровых кодеков.

С использованием разработанной программной системы был произведён сравнительный анализ оценочных функций М, SAD и SSE. При проведении сравнения в качестве алгоритма поиска векторов похожести использовался алгоритм полного перебора. Размеры сжатых с использованием сравниваемых оценочных функций для пяти видеопоследовательностей представлены на рис. 2.

12 3 4 5

Видеопоследовательность

Рис. 2. Значения меры 5 для сравниваемых оценочных функций

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

1. Использование оценочной функции М позволило достичь наибольшей степени компрессии. Однако оценочная функция М обладает высокой вычислительной сложностью и редко используется на практике при поиске векторов похожести.

2. Использование оценочных функций SAD и SSE позволило достичь схожей степени компрессии. Вычислительная сложность меры SSE

выше, чем у меры SAD, так как при вычислении SSE используются операция умножения, а при вычислении SAD - нет. В связи с этим был сделан вывод о том, что использование меры SAD более эффективно.

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

1) поиск начального приближения вектора похожести;

2) уточняющий поиск;

3) завершающая обработка найденных векторов похожести.

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

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

МВ< МВз МВ3

С. •■'" •<"•'• С* • • -'А . i „ MB, Текущий блок

Рис. 3. Блоки, используемые для вычисления медианного вектора

Алгоритм нахождения вектора начального приближения: Шаг 1. Векторы соседних блоков МВ\, МВ2,МВг (рис. 3) используются для определения так называемого медианного вектора. Вычисляем значение оценочной функции для медианного вектора. Сравниваем это значение с пороговой величиной Ть если полученное значение меньше чем Г, переходим к уточняющему поиску, в противном случае переходим к шагу 2. Пороговая величина Т\ вычисляется исходя из значений оценочных функций соседних блоков по формуле:

7, = ak min(SADl,SAD2,SAD3,SAD,) + bk, где SADi, SAD2, SAD} SADa - меры SAD, рассчитанные для блоков MB], МВг.МВъ соответственно.

Шаг 2. Составляем список векторов-кандидатов. В этот список добавляем найденные векторы соседних блоков в текущем и предыдущем кадрах. Так же в список добавляются интерполированные векторы: если в предыдущем кадре вектор похожести какого либо из блоков указывал в текущий блок, то этот вектор так же добавляется в список.

Шаг 3. Из списка векторов-кандидатов удаляются близкие векторы. Для всех векторов попарно рассчитывается величина d(y\v2) = \v*-v?\ + \v}-vf\. Если d(V,Vm)<T1, то вектор Vm исключается из списка векторов-кандидатов. Экспериментально было получено оптимальное значение параметра Т2, равное 4.

Шаг 4. Вычисление оценочной функции производится для всех оставшихся векторов-кандидатов. Вектор-кандидат с наименьшим значением оценочной функции принимается за вектор начального приближения.

Шаг 5. Если значение оценочной функции в точке начального приближения больше чем Ту=2Т\, то принимаем решение о том, что точка начального приближения найдена неудачно и производим её адаптивный поиск методом сканирования в зависимости от размеров поискового окна и разрешения изображения.

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

Для выбора метода локальной оптимизации при помощи программной системы «MEFramework» был проведён сравнительный анализ следующих методов: симплексный метод, Гаусса-Зейделя (покоординатного спуска), Хука-Дживса, градиентный метод и метод поиска по алмазу. По результатам сравнительного анализа был сделан вывод о том, что сравниваемые методы локальной оптимизации позволяют достичь близкой степени компрессии. Однако градиентный метод требует меньшего количества вызовов оценочной функции.

Градиентный метод сводится к следующему итерационному процессу:

Шаг 1. В точке Vk вычисляется градиент оценочной функции. Вычисление градиента оценочной функции в зависимости от ситуации производится методом прямой (упреждающей), либо обратной (отстающей) конечной разности по формулам:

mx,y) = {f(x + \,y)-f(x,y),f(x,y + \)-f(x,y)}, m*,y) = {Дх, у) - fix - У), fix,у) - fix,у -1)}.

Шаг 2. Принимаем yk+l ~ ук -Я ) , вычисляем ДУЫ).

¡У/(Ук)Ц

Шаг 3. Если f(Vk+') < f(Vk), принимаем Vм за текущую точку и

переходим к шагу 1, иначе уменьшаем À на единицу и переходим к шагу 4.

Шаг 4. Если параметр X > 1, переходим к шагу 2, иначе заканчиваем поиск, результатом поиска является вектор похожести Vk.

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

Для проведения сравнительного анализа с помощью программной системы «MEFramework"» автором были реализованы следующие алгоритмы поиска векторов похожести: NTTS, СБА, ADZS, PMVFAST, EPZS. По совокупности критериев алгоритм EPZS оказался наиболее эффективным алгоритмом поиска векторов похожести. Использование этого алгоритма позволяет достичь высокой степени компрессии при низком количестве вычислений оценочной функции.

Произведено сравнение предложенного алгоритма с алгоритмом EPZS. Результаты сравнения, алгоритмов представлены на рис. 4, 5.

Видеопоследовательность

Рис. 4. Значения меры S для тестируемых алгоритмов, Мбайт

Видеопоследовательность

Рис. 5. Значения меры К для тестируемых алгоритмов, млн. вызовов

По результатам сравнения алгоритмов сделаны следующие выводы: использование предложенного алгоритма поиска векторов похожести позволяет достичь увеличения степени компрессии по сравнению с алгоритмом EPZS на 1-2%. При этом, предложенный алгоритм требует на 1525% меньшего количества вычислений оценочной функции чем алгоритм EPZS. Таким образом, предложенный алгоритм поиска векторов похожести имеет меньшую вычислительную сложность и его использование позволит увеличить производительность компрессора при сохранении степени сжатия.

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

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

cost{vi,v;) = sad(v;,v;)+k,i\vlx -f;-1 |+\v; -v;-'|),

где (V^,Vy) ~ вектор похожести текущего блока, , V'y~]) -вектор похожести предыдущего блока, к коэффициент для учёта степени

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

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

Y.SADU

k -М_>

2Х>

■-I

где М- количество блоков в кадре, - количество бит, потребовавшееся для кодирования j-го блока в (<-1)-м кадре, SAD'tl - значения

меры SAD, рассчитанной для ¿-го блока в (г-1)-м кадре.

Произведено сравнение предложенной оценочной функции Cost с оценочной функцией SAD на тестовых видеопоследовательностях. В эксперименте использовались различные значения коэффициентов квантования. Результаты сравнения для пяти тестовых видеопоследовательностей представлены в табл. 1.

Таблица 1. Размер видеопоследовательностей, сжатых с применением сравниваемых оценочных функций, Мбайт_

№ Оценочная функция Коэффициент квантования

3 10 20 30

1 Cost 23,379 7,364 3,7 2,698

SAD 23,616 7,671 4,025 3,066

2 Cost 27,204 9,924 4,479 2,798

SAD 27,445 10,338 4,863 3,144

3 Cost 132,24 40,814 16,904 10,942

SAD 132,248 41,974 17,689 11,413

4 Cost 70,01 19,779 8,477 5,958

SAD 70,602 20,708 9,323 6,76

5 Cost 28,079 7,105 3,603 2,839

SAD 28,383 7,612 3,982 3,204

Анализ данных из табл. 1 позволяет сделать вывод о том, что в сравнении с функцией SAD использование предложенной оценочной функции увеличивает степень компрессии на 3-5% для коэффициента квантования 10, на 5-9% для параметра коэффициента 20 и на 5-12% для коэффициента квантования 30.

Разработанный алгоритм поиска векторов похожести и новая оценочная функция были встроены в реальное приложение сжатия видеоданных, компрессор «MainConcept MPEG-2 Video Encoder». Для проведения сравнительного анализа была реализована версия компрессора, использующего алгоритм EPZS. В качестве оценочной функции для алгоритма EPZS использовалась функция SAD. При проведении сравнения эффективности алгоритмов поиска векторов похожести тестовые видеопоследовательности сжимались с постоянным битрейтом. Для оценки качества найденных векторов использовалась общепризнанная мера оценки качества сжатых видеоданных PSNR, рассчитанная для декодированного и оригинального кадров. Для оценки вычислительной сложности алгоритмов сравнивалось время, требуемое для сжатия видеопоследовательно-

Рис. 6. Значения меры для сравниваемых алгоритмов поиска векторов похожести, дБ

В результате анализа данных, представленных на рис. 10, рис. 11 сделаны следующие выводы:

1) использование предложенного алгоритма поиска векторов похожести и новой оценочной функции при сжатии видеоданных позволяет увеличить значение меры качества Р&\7? по сравнению со значениями, достигаемыми при использовании алгоритма EPZS■,

2) для видеопоследовательностей с низким разрешением (1, 2, 3) время, затраченное на сжатие с применением предложенного алгоритма и алгоритма EPZS практически одинаковое. Это объясняется тем, что эти

видеопоследовательности не содержат длинных векторов похожести, и

ритмов, с

3) для видеопоследовательностей 4-10 использование предложенного алгоритма поиска векторов похожести позволяет уменьшить общее время компрессии на 5-15%, что является ощутимым достижением оптимизации компрессора видеоданных.

В заключении перечислены основные результаты, полученные в диссертационной работе.

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

2. Произведён анализ оценочных функций SAD, SSD, Ml. Степень компрессии с использованием функции М1 оказалась самой высокой, однако вычислительная сложность данной функции не позволяет использовать её в реальных приложениях сжатия видеоданных. Функции SAD и SSD позволили достичь схожей степени компрессии, однако в силу того, что функция SSD является вычислительно более сложной, в дальнейших исследованиях было решено использовать функцию SAD.

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

4. Проведён сравнительный анализ пяти алгоритмов поиска экстремума: симплексный метод, Гаусса-Зейделя, Хука-Дживса, градиентный метод, метод поиска по алмазу. Лучшим среди тестируемых методов оказался градиентный метод.

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

6. Произведено сравнение разработанного алгоритма поиска векторов похожести с алгоритмом EPZS. Использование предложенного алгоритма при сжатии видеоданных позволяет уменьшить количество вычислений оценочной функции по сравнению с алгоритмом EPZS на 15-25% при той же степени компрессии.

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

8. Произведено сравнение разработанного алгоритма поиска векторов похожести, использующего новую оценочную функцию с алгоритмом EPZS в реальном приложении сжатия видеоданных. Использование предложенного алгоритма поиска векторов похожести позволяет уменьшить общее время компрессии по сравнению с результатами алгоритма EPZS, на 5-15%, при незначительном улучшении качества.

9. Алгоритм поиска векторов похожести, разработанный в рамках данной диссертационной работы, внедрен в коммерческий продукт компании Mainoncept AG, Mainconcept MPEG-2 Video Encoder, что подтверждается актом о внедрении.

10. Программная система «MEFrameworb> зарегистрирована в Отраслевом фонде алгоритмов и программ (ОФАП) и используется компанией ООО «МэйнКонцепт-Дивикс» для проведения внутренних испытаний алгоритмов поиска векторов похожести.

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

Публикации по основным результатам диссертации:

1. Потапов П.В. Оптимизация распределения ресурсов при кодировании видеоданных // Информационные системы. - Томск: ТУСУР, 2004. -№ 3. - С. 129 - 134.

2. Потапов П.В. Оптимальное распределение ресурсов при сжатии видеоданных с использованием двухпроходных алгоритмов // Материалы всероссийской научной конференции студентов-физиков. - Екатеринбург: АСФ, 2005.-С. 251-254.

3. Потапов П.В. Оптимальное распределение ресурсов при сжатии видеоданных с использованием двухпроходного алгоритма // Материалы XLIII международной научной студенческой конференции «студент и научно-технический прогресс». - Новосибирск: НГУ, 2005. - С. 45 - 46.

4. Потапов П.В. Применение двухпроходного алгоритма для распределения ресурсов при сжатии видеоданных // Материалы всероссийской научно-технической конференции студентов и молодых ученых «Научная сессия ТУСУР - 2005». - Томск: ТУСУР, 2005. - С. 65 -68.

5. Потапов П.В. Двухпроходный режим компрессии видеоданных // Доклады Томского государственного университета систем управления и радиоэлектроники. - Томск, 2005.-Т. 11.-№3.-С. 77- 81.

6. Потапов П.В. Двухпроходные алгоритмы распределения ресурсов при сжатии видеоданных // Информационные системы. - Томск: ТУСУР, 2006.-№4.-С. 10-18.

7. Кориков A.M., Потапов П.В. Программная среда для разработки и исследования алгоритмов оценки движения при сжатии видеоданных // Вычислительные технологии, - Томск, 2007.- Т. 12.- Спец выпуск 1.-С. 42-50.

8. Потапов П.В. Разработка программной среды для сравнения алгоритмов поиска видеоданных. // Материалы докладов Всероссийской Научно-Технической конференции студентов, аспирантов и молодых ученых «Научная сессия ТУСУР-2007». - Томск, 2007. - С. 189 - 192.

9. Потапов П.В. Использование методов локальной оптимизации для поиска векторов похожести при сжатии видеоданных // Сб. науч. докл. Международной науч.-практ. конф. «Электронные системы и средства управления». - Томск, 2008. - С. 43 - 47.

10. Потапов П.В. Программная система моделирования поиска векторов похожести при сжатии видеоданных «MEFramework» // Отраслевой фонд алгоритмов и программ. Свидетельство об отраслевой регистрации разработки № 11657. Номер государственной регистрации: 50200802145.-2008.

Тираж 100. Заказ №1107. Томский государственный университет систем управления и радиоэлектроники 634050, г. Томск, пр. Ленина, 40

ВВЕДЕНИЕ.

1 АНАЛИЗ СОСТОЯНИЯ ПРОБЛЕМЫ.

1.1 История видео компрессии.

1.2 Основы видео компрессии, компенсация движения как метод устранения временной избыточности.

1.3 Классификация методов компенсации движения.

1.3.1 Классификация по типу сущностей, в терминах которых производится компенсация движения.

1.3.2 Классификация по точности векторов движения.

1.3.3 Классификация по мере оценки стоимости вектора движения.

1.4 Обзор алгоритмов поиска движения, применяемых при сжатии видеоданных.

1.4.1 Алгоритм полного перебора.

1.4.2 Алгоритм поиска NTTS.

1.4.3 Алгоритм поиска по алмазу.

1.4.4 Алгоритм поиска PMVFAST.

1.4.5 Алгоритм поиска СБА.

1.4.6 Алгоритм поиска ADZS.

1.4.7 Алгоритм поиска EPZS.

Выводы по главе 1.

2 ПРОГРАММНАЯ СИСТЕМА СРАВНЕНИЯ АЛГОРИТМОВ ПОИСКА ДВИЖЕНИЯ. РЕАЛИЗАЦИЯ И СРАВНЕНИЕ СОВРЕМЕННЫХ АЛГОРИТМОВ ПОИСКА ВЕКТОРОВ

ПОХОЖЕСТИ.

2.1 Обоснование необходимости разработки программной системы сравнения алгоритмов поиска движения.

2.2 Обзор аналогов программной системы MEFramework.

2.2.1 VirtualDub MSUMotion Estimation Filter.

2.2.2 Программа ME Analyzer.

2.3 Обоснование выбора критериев оценки алгоритмов поиска движения.

2.4 DirectShow как средство для работы с мультимедиа данными

2.4.1 История развития DirectShow.

2.4.2 DirectShow фильтры.

2.5 Описание реализации программной системы.

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

2.6.1 Описание тестовых видеопоследовательностей.

2.6.2 Сравнительный анализ оценочных функций.

2.5.3 Тестирование и сравнительный анализ алгоритмов поиска векторов похожести.

Выводы по главе 2.

3 РАЗРАБОТКА И РЕАЛИЗАЦИЯ ОРИГИНАЛЬНОГО АЛГОРИТМА ПОИСКА ДВИЖЕНИЯ. СРАВНЕНИЕ С

АНАЛОГАМИ.

3.1 Обоснование необходимости разработки нового алгоритма

3.2 Требования к разрабатываемому алгоритму.

3.3 Разработка метода нахождения первого приближения.

3.4 Выбор метода локальной оптимизации.

3.4.1 Симплексный метод.

3.4.2 Метод Нельдера-Мида (деформируемых многогранников)

3.4.3 Метод Гаусса-Зейделя (покоординатного спуска).J

3.4.4 Метод Хука-Дживса.

3.4.5 Градиентные методы. Метод наискорейшего спуска.

3.4.6 Сравнение эффективности и выбор метода локальной оптимизации для алгоритма поиска движения.

3.5 Описание предложенного алгоритма.

3.6 Оценка эффективности разработанного алгоритма и сравнение с аналогами.

3.7. Разработка новой оценочной функции.

3.9. Использование предложенного алгоритма в реальной системе компрессии видеоданных.

Выводы по главе 3.

Актуальность темы.

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

В настоящее время огромное внимание уделяется разработке алгоритмов сжатия видеоданных, использующих компенсацию движения. Начиная с 1980 года, организации ITU и MPEG последовательно выпускают ряд стандартов сжатия, использующих блочную компенсацию движения: 11.261, MPEG-1, MPEG-2/H.262, Н.263, MPEG-4, Н.264 (MPEG-4 part-10) [89 - 94, 96, 97]. Использование алгоритмов компенсации движения при сжатии видеоданных позволяет существенно увеличить степень компрессии при том же соотношении сигнал/шум результирующего видео. Параллельно с разработкой новых стандартов сжатия происходит совершенствование алгоритмов'поиска векторов похожести. Алгоритм поиска векторов похожести выполняет важнейшую роль в системах сжатия видеоданных, использующих компенсацию движения. От выбора алгоритма поиска векторов похожести напрямую зависит степень компрессии и вычислительная сложность компрессора. Поиск векторов похожести является одним из самых ресурсоемких этапов компрессии видеоданных. Однако, сам алгоритм поиска векторов похожести обычно не фиксируется в стандарте сжатия. Таким образом, модуль поиска векторов похожести является одной из немногих частей видеокомпрессора, которую можно свободно подвергать алгоритмической оптимизации. Использование эффективного алгоритма поиска векторов похожести даёт значительное конкурентное преимущество над другими компрессорами, реализующими тот же стандарт сжатия. Вот почему в этой области продолжаются интенсивные исследования, несмотря на то, что уже разработано множество алгоритмов поиска векторов похожести для различных задач [27, 32, 34 - 37,46 - 51, 56, 66 - 70, 72 — 80, 88].

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

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

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

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

Объектом исследования является компрессия цифровых видеоданных. Предметом исследования являются алгоритмы поиска векторов похожести, используемые при сжатии видеоданных.

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

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

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

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

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

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

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

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

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

4. Разработанный алгоритм поиска векторов похожести был внедрен компанией ООО «МэйнКонцепт-Дивикс» в составе коммерческого продукта «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 в журнале из перечня ВАК [9], 5 докладов опубликовано в материалах научных конференций и семинаров, зарегистрирована программа в Отраслевом фонде алгоритмов и программ (ОФАП).

1. Потапов П.В. Оптимизация распределения ресурсов при кодировании видеоданных // Информационные системы. — Томск: ТУСУР, 2004. С. 123 - 129.

2. Потапов П.В. Оптимальное распределение ресурсов при сжатии видеоданных с использованием двухпроходных алгоритмов // Материалы всероссийской научной конференции студентов-физиков. - Екатеринбург: АСФ, 2005. С. 251-254.

3. Потапов П.В. Оптимальное распределение ресурсов при сжатии видеоданных с использованием двухпроходного алгоритма // Материалы XLIII международной научной студенческой конференции «студент и научно-технический прогресс». - Новосибирск: НГУ, 2005. С. 45- 46.

4. Потапов П.В. Применение двухпроходного алгоритма для распределения ресурсов при сжатии видеоданных // Материалы всероссийской научно-технической конференции. — Томск: ТУСУР, 2005. С. 65-68.

5. Потапов П.В. Двухпроходный режим компрессии видеоданных // Доклады Томского государственного университета систем управления и радиоэлектроники. - Томск, 2005. - № 3 (11). С. 77-81.

6. Потапов П.В. Двухпроходные алгоритмы распределения ресурсов при сжатии видеоданных. Информационные системы: тр. постоянно действующего научно-технического семинара // Том. гос. ун-т систем упр. и радиоэлектроники, отд. проблем информатизации Том. Науч. Центра СО РАН. - Томск: ТУСУР, 2006. - №. 4. С. 10-18.

7. Кориков A.M., Потапов П.В. Программная среда для разработки и исследования алгоритмов оценки движения при сжатии видеоданных. // Вычислительные технологии, Институт вычислительных технологий СО РАН. - Томск, 2007. - Т. 12. - Спец. выпуск 1. С. 42-50.

8. Потапов П.В. Разработка программной среды для сравнения алгоритмов поиска видеоданных. // Материалы докладов Всероссийской Научно-Технической конференции студентов, аспирантов и молодых ученых «Научная сессия ТУСУР-2007». - Томск, 2007. С. 189-192.

10. Потапов П.В. Использование методов локальной оптимизации для поиска векторов похожести при сжатии видеоданных // Сб. науч. докл. Международной науч.-практ. конф. «Электронные системы и средства управления». — Томск, 2008. - С. 43 - 47.

11. Потапов П.В. Программная система моделирования поиска векторов похожести при сжатии видеоданных «MEFrameworby II Отраслевой фонд алгоритмов и программ. Свидетельство об отраслевой регистрации разработки № 11657. Номер государственной регистрации: 50200802145. -2008.

Личный вклад

Основные результаты и положения, выносимые на защиту, выполнены автором лично. Автором лично была реализована программная система MEFramewoi'k. В качестве модулей к этой системы реализован ряд современных алгоритмов поиска векторов похожести, методов локальной оптимизации, а так же ряд оценочных функций, произведен сравнительный анализ. Новая оценочная функция разработана автором лично. Предлагаемый алгоритм поиска векторов похожести и экспериментальные данные разработаны и получены автором лично. Научный руководитель принимал участие в постановке целей и задач исследований, обсуждении полученных результатов.

Благодарности

Автор выражает глубокую благодарность научному руководителю Корикову A.M. за помощь в работе над диссертацией, статьями, решении организационных вопросов, и научный опыт, переданный в процессе совместной деятельности.

Также автор очень признателен коллегам из компаний ООО «Мэйн-Концепт-ДивИкс» Сергееву С.Н., Иванову В., Цурпал С., Милякову А. за ценные практические советы по общим вопросам сжатия видеоданных и критическое обсуждение промежуточных результатов в ходе работы над диссертацией.

Основные результаты диссертации состоят в следующем:

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

2. При помощи программной системы MEFramework проведён сравнительный анализ оценочных функций SAD, SSD, Ml. Степень компрессии с использованием функции Ml оказалась самой высокой, однако вычислительная сложность данной функции не позволяет использовать её для поиска векторов похожести в реальных приложениях сжатия видеоданных. Функции SAD и SSD позволили достичь схожей степени компрессии, однако в силу того, что функция SSD является вычислительно более сложной, в дальнейших исследованиях было решено использовать функцию SAD.

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

4. Для выбора метода локальной оптимизации был проведён сравнительный анализ и тестирование пяти алгоритмов поиска экстремума: симплексный метод, Гаусса-Зейделя, Хука-Дживса, градиентный метод, метод поиска по алмазу. По результатам сравнительного анализа лучшим среди тестируемых методов оказался модифицированный градиентный метод.

5. Разработан оригинальный алгоритм поиска векторов похожести при сжатии видеоданных. Алгоритм использует расширенный набор векторов-кандидатов, а так же метод сканирования при нахождении точки начального приближения. Для уточнения точки начального приближения используется градиентный метод локальной оптимизации. По окончании поиска векторов для всего кадра производится обратный проход по всем блокам с целью уточнения найденных векторов похожести с учетом новых векторов-кандидатов.

6. Произведено сравнение разработанного алгоритма поиска векторов похожести с алгоритмом EPZS. Использование предложенного алгоритма при сжатии видеоданных позволяет уменьшить количество вычислений оценочной функции по сравнению с алгоритмом EPZS на 15-25% при той же степени компрессии.

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

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

9. Алгоритм поиска векторов похожести, разработанный в рамках данной диссертационной работы, внедрен в коммерческий продукт компании Mainoncept AG, Mainconcept MPEG-2 Video Encoder, что подтверждается актом о внедрении.

10. Программная система MEFramework зарегистрирована в Отраслевом фонде алгоритмов и программ (ОФАП) и используется компанией ООО «МэйнКонцепт-Дивикс» для проведения внутренних испытаний алгоритмов поиска векторов похожести.

135

ЗАКЛЮЧЕНИЕ

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

1. Артюшенко В.М., Шелухин О.И., Афонин М.Ю. Цифровое сжатие видеоинформации и звука. — М.: Дашков и Ко, 2003. — 426 с.

2. Базара М., Шетти К. Нелинейное программирование. Теория и алгоритмы. -М.: Мир, 1982. 583 с.

3. Банди. Б. Методы оптимизации. М.: Радио и связь, 1988. - 127 с.

4. Васильев Ф. П. Численные методы решения экстремальных задач. -М.:Наука, 1981.-549 с.

5. Ватолин Д., Ратушняк А., Смирнов М., Юкин В. Методы сжатия данных. Устройство архиваторов, сжатие изображений и видео. — МгДиалог-МИФИ, 2002.-384 с.

6. Ватолин Д., Симонян К., Гришин С. VirtualDub MSU Motion Estimation Filter Электронный ресурс. — Режим доступа: http://www.compression.iTi/video/motionestimation/index.html. -01.11.2008.

7. Гласман К. Преобразование стандартов: методы оценки векторов движения // 625. М: Издательство 625, 2006. - №6.

8. Гилл Ф., Мюррей У., Райт М. Практическая оптимизация: Пер. с англ. -М: Мир, 1985.-509 с.

9. Кориков A.M., Потапов П.В. Программная среда для разработки и исследования алгоритмов оценки движения при сжатии видеоданных // Вычислительные технологии, Институт вычислительных технологий СО РАН. Томск, 2007. - Т. 12. - Спец. выпуск 1. - С. 42-50.

10. Кривошеев М. И. Основы телевизионных измерений. 3-е изд., доп. и перераб. М.: Радио и связь, 1989. 608 с.

11. Кубасов Д., Ватолин Д. Обзор методов компенсации движения. Интернет журнал «Графика и Мультимедиа» Электронный ресурс. — Режим доступа: http://cgm.graphicon.ru/content/view/76/64/. 05.06.2007.

12. Курицкий Б. Поиск оптимальных решений средствами Excel 7.0. Спб.: BHV, 1997.-384 с.

13. Мицель А. А., Шелестов А. А. Методы оптимизации. Томск: ТУ СУР, 2004. - 244 с.

14. Моисеев Н. Н., Иванилов Ю. П., Столярова Е. М. Методы оптимизации. -М.: Наука, 1975.-352 с.

15. Поляк Б. Т. Введение в оптимизацию. М.: Наука, 1983. - 384 с.

16. Потапов П.В. Оптимизация распределения ресурсов при кодировании видеоданных // Информационные системы. Томск: ТУ СУР, 2004. - С. 123 - 129.

17. Потапов П.В. Оптимальное распределение ресурсов при сжатии видеоданных с использованием двухпроходных алгоритмов // Материалы всероссийской научной конференции студентов-физиков. — Екатеринбург: АСФ, 2005. С. 251-254.

18. Потапов П.В. Применение двухпроходного алгоритма для распределения ресурсов при сжатии видеоданных // Материалы всероссийской научно-технической конференции. Томск: ТУСУР, 2005. - С. 65-68.

19. Потапов П.В. Двухпроходный режим компрессии видеоданных // Доклады Томского государственного университета систем управления и радиоэлектроники. Томск, 2005. - № 3 (11). - С. 77-81.

20. Потапов П.В. Разработка программной среды для сравнения алгоритмов поиска видеоданных. // Материалы докладов Всероссийской Научно

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

22. Потапов П.В., Кориков A.M. Алгоритм поиска векторов похожести при сжатии видеоданных // Известия Томского политехнического университета. Томск, 2008. — Т. 312. - № 5.

23. Потапов П.В. Использование методов локальной оптимизации для поиска векторов похожести при сжатии видеоданных // Сб. науч. докл. Международной науч.-практ. конф. «Электронные системы и средства управления». Томск, 2008. - С. 43 - 47.

24. Потапов П.В. Программная система моделирования поиска векторов похожести при сжатии видеоданных «MEFramework» // Отраслевой фонд алгоритмов и программ. Номер государственной регистрации:. — 2008.

25. Потапов П.В., Кориков A.M. Оценочная функция для поиска векторов похожести при сжатии видеоданных // Доклады ТУСУРа. — Томск, 2008.-№2(18), ч. 2.

26. Путилин С.Ю. Быстрый алгоритм нахождения движения в видеопоследовательностях Электронный ресурс. — Режим доступа: www.graphicon.ru. -12.12.2006.

27. Рыков А.С. Поисковая оптимизация. Методы деформируемых конфигураций. М.: Наука, 1993. - 214 с.

28. Телемультимедиа.ру Электронный ресурс. Режим доступа: www.telemultimedia.ru. - 19.07.2008.

29. Френке JI. Теория сигналов. М.: Сов. радио, 1974. 344 с.

30. Шипилов С.А. Методы безусловной многомерной оптимизации. — Новокузнецк: НФИ КемГУ, 2000. 31 с.

31. Benmoussat B.N., Belbachir M.F., Belbachir A.N. Fast diamond search algorithm for block based motion estimation // IEEE Transactions on Circuits and Systems for Video Technology. 1998. - V. 7. - № 3. - P. 424-428.

32. Bhaskaran V., Konstantinides К., Image and Video Compression Standards: Algorithms and Architectures. — Dordrecht: Kluwer, 1997. 454 p.

33. Brady N. MPEG-4 standardized methods for the compression of arbitrarily shaped video objects // IEEE Transactions on Circuits and Systems for Video Technology.-1999.-P. 1170-1189.

34. Chen W.H, Smith С. H., Fralick S. C. A fast computational algorithm for the discrete cosine transform // IEEE Trans. Commun. 1977. - V. 25. — №9.

35. Christopoulos V., Comelis J., A Center-Biased Adaptive Search Algorithm for Block Motion Estimation // IEEE Transactions on Circuits and Systems for Video Technology. 2000. - V. 10. - № 3. - P. 423-426.

36. Dzung Т.Н., Jeffrey S.V. Fast and Efficient Algorithms for Video Compression and Rate Control // IEEE Transactions on Circuits and Systems for Video Technology. 1998. - V. 7. - № 3. - P. 323-442.

37. Dzung Т.Н., Philip M.L., Jeffrey S.V. Efficient Cost Measures for Motion Estimation at Low Bit Rates // IEEE Transactions on Circuits and Systems for Video Technology. 1998. - V. 8. - № 4. - P. 488-500.

38. Flierl M., Wiegand Т., Girod B. Video codec incorporating block-based multihypothesis motioncompensated prediction // Proc. of SPIE, Visual Comm. and Image Proc. 2000 (VCIP 2000). Perth, 2000. - V. 4067. - № 1. -P. 238-249.

39. Furht В., "A Survey of Multimedia Compression Techniques and Standards. Part II: Video Compression" // Journal of Real-Time Imaging. 1995. - V. 1. -P. 319-338.

40. Jain J. R. Displacement measurement and its application in interframe image coding // IEEE Trans. Commun. 1981. - V.29. - P. 1799-1808.

41. Ghanbari M. Standard Codecs—Image Compression to Advanced Video Coding. London, UK: The Institution of Electrical Engineers, 2003. - 407 p.

42. Golomb S.W. Run-length encoding // IEEE Trans, on Inf. Theory. 1966. -V. 12.-P. 399-401.

43. Haskell В., Puri A., Netravali A. Digital Video: An Introduction to MPEG-2. -NY.: Chapman & Hall, 1997. 456 p.

44. Нету M., Hengartner U., Steenkiste P., Gross T. MPEG system streams in best-effort networks // Proc. Packet Video. New York, 1999.

45. Hosur P.I., Ma K.K. Motion Vector Field Adaptive Fast Motion Estimation // Second International Conference on Information, Communications and Signal Processing (ICICS '99). Singapore, 1999. - P. 7-10.

46. Kim D.W., Choi J. S., Kim J. T. Adaptive motion estimation based on spatio-temporal correlation // Signal Processing: Image Commun. 1998. — V. 13. — P. 161-170.

47. Kim S.H., Park R.H. Fast Motion compensation Algorithm for Video Sequences with Local Brightness Variations // Proc. of SPIE, Visual Comm. and Image Proc. 2000 (VCIP 2000). Perth , 2000. -V. 4067. - № 3. - P. 1229-1238.

48. Koga Т., Iinuma K., Hirano A., Iijima Y., Ishiguro T. Motion compensated interframe coding for video conferencing // Proc. NTC. LA, 1981. - P. 7382.

49. Li R., Zeng В., Liou M.L. A new three-step search algorithm for block motion estimation // IEEE Trans, on Circuits and Systems for Video Technology. -1994.- V. 4.- № 4. P. 438-42.

50. Marpe D., Schwarz H., Wiegand T. Context-Based Adaptive Binary Arithmetic Coding in the H.264 / AVC Video Compression Standard // IEEE Transactions on Circuits and Systems for Video Technology. 2003. - P. 586-602.

51. Mattavelli M. PhD. Thesis: Motion Analysis and Estimation: From Ill-Posed Discrete Inverse Linear Problems to MPEG-2 coding. Ecole Polytechnique Federale de Lausanne: Lausanne, 1996.

52. Tekalp M.A. Digital Video Processing. New Jersey: Prentice Hall, 1995. -560 p.

53. Nasrabadi N., King R. Image coding using vector quantisation: a review // IEEE Trans. Commun. 1998. - V. 36.-№8.-P. 124-135.

54. Oh H. S., Lee H. K. Adaptive adjustment of the search window for block-matching algorithm with variable block size // IEEE Trans. Consumer Electron. 1998. - V. 44. - P. 659-666.

55. Oscal Т., Chen C. Motion estimation using a one-dimensional gradient descent search // IEEE Transactions on Circuits and Systems for Video Technology.-2000.-V. 10.-№4.-P. 608-616.

56. Pandzic I., Forchheimer R. MPEG-4 Facial Animation. NY: John Wiley & Sons, 2002. - 299 p.

57. Parhi К. K., Nishitani T. Digital Signal Processing for Multimedia Systems. -NY:Marcel Dekker, 1999. 884 p.

58. Pennebaker W. В., Mitchell J. L., Fogg C., LeGall D. MPEG Digital Video Compression Standard. NY: Chapman & Hall, 1997.

59. Puri A., Chen T. Multimedia Systems, Standards and Networks. NY: Marcel Dekker, 2000. - 664 p.

60. Rao K. R., Hwang J. J. Techniques and Standards for Image, Video and Audio Coding. — New Jersey: Prentice Hall, 1997. 563 p.

61. Richardson E.G. H.264 and MPEG-4 Video Compression. Aberdeen, UK: The Robert Gordon University, 2003.

62. Richardson E.G. Video codec design. Aberdeen, UK: The Robert Gordon University, 2002. - 303 p.

63. Riley M. J., Richardson E. G. Digital Video Communications. London: Artech House, 1997.

64. Sadka A., Compressed Video Communications. NY: John Wiley & Sons, 2002.-248 p.

65. Sappasitwong Т., Aramvith S., Jitapunkul S., Tamtrakarn A., Kitti-punyangam P., Kortrakulk H. Adaptive Asymmetric Diamond Search Algorithm for Block-Based Motion Estimation // in Proc. Of Inter. Symp. on

66. Video/Image Proc and Multimedia com. (VIPromCom). — Zadar, Croatia, 2002.

67. Sullivan G. Multi-Hypothesis Motion Compensation for Low Bit-Rate Video Coding // in Proc. of the IEEE Inter. Conf. on Acoustics, Speech, and Signal Proc. Minneapolis, 1993. - V. 5. - P.437-440.

68. Sullivan G., Wiegand T. Rate-distortion optimization for video compression // IEEE Signal Process. Mag. 1998. - P. 122-134.

69. Tang C.W., Au O.C. Unidirectional Motion Compensated Temporal Interpolation // Proc. of IEEE International Symposium on Circuits and Systems. 1997. - V. 2. - P. 1444-1447.

70. Tham J.Y., Ranganath S., Ranganath M., Kassim A.A. A Novel Unrestricted Center-Biased Diamond Search Algorithm for Block Motion Estimation // IEEE Transactions on Circuits and Systems for Video Technology. — 1998. -V. 8.-P. 369-377.

71. Teodosio L., Bender W. Salient Video Stills: Content and Context Reserved // Proc. of the ACM Inter. Conf. on Multimedia. Anaheim, 1993. - P. 39-46.

72. Tourapis A.M., Au O.C., Liou M.L. Predictive Motion vector Field Adaptive Search Technique (PMVFAST) Enhancing Block-Based Motion Estimation // Proc. Of visual Comm. and Image Proc. (VCIP-2001). - 2001. - V. 1. - P. 315-325.

73. Tourapis A.M., Au O.C., Liou M.L. New Results on Zonal Based Motion Estimation Algorithms — Advanced Predictive Diamond Zonal Search // Proc. of 2001 IEEE International Symposium on Circuits and Systems (ISCAS-2001).-Sydney, 2001.-V. 5.-P. 183-186.

74. Tourapis A.M. Enhanced predictive zonal search for single and multiple frame motion estimation // Proc. SPIE Conf. Visual Communications and Image Processing. 2002. - P 1069-1079.

75. Tourapis A.M., Au O.C., Liou M.L., Shen G. Status Report of Core Experiment on Fast Block-Matching Motion Estimation using Diamond Zonal

76. Search with Embedded Radar // ISO/IEC JTC1/SC29/WG11 MPEG99/m4917. Vancouver, 1999.

77. Tourapis A.M., Au O.C., Liou M.L. Fast Motion Estimation using Circular Zonal Search // Proc. of SPIE Sym. of Visual Comm. & Image Processing. VCIP'99. 1999. — V. 2.-P. 1496-1504.

78. Tourapis A.M., Au O.C., Liou M.L. A High Performance Algorithm for Fast Block Based Motion Estimation // Proc. of Picture Coding Symposium, PCS'99. — 1999. P. 121-124.

79. Tourapis A.M., Au O.C., Liou M.L. An Adaptive Center (Radar) Zonal based Algorithm for Motion Estimation // Proc. Of 6th IEEE Int. Conf. on Electronics, Circuits and Systems. ICECS'99. 1999.

80. Tourapis A. M., Au О. C., Liou M.L., Shen G., Ahmad I. Optimizing the Mpeg-4 Encoder Advanced Diamond Zonal Search // in Proc. of 2000 IEEE Inter. Symposium on Circuits and Systems (ISCAS-2000). - 2000, Geneva.

81. Tsai J. C., Hsieh С. H., Weng S. K., Lai M. F. Block-matching motion estimation using correlation search algorithm // Signal Processing: Image Commun.- 1998.-V. 13.-P. 119-133.

82. Walsh A., Bourges-S 'evenier M. MPEG-4 Jump Start. New Jersey: Prentice-Hall, 2002.

83. Wiegand Т., Sullivan G., Bjontegaard G., Luthra A. Overviewof the H.264 /AVCVideo Coding Standard // IEEE Transactions on Circuits and Systems for Video Technology. 2003. - P. 923-938.

84. Wiegand Т., Zhang X., Girod B. Long-Term Memoiy Motion-Compensated Prediction // IEEE Transactions on Circuits and Systems for Video Technology. 1999. - P.70-84.

85. Witten I., Neal R., Cleary J. Arithmetic coding for data compression // Communications of the ACM. 1987. - V. 30, № 6.

86. Wong C.K., Au O.C. Fast Motion Compensated Temporal Interpolation for Video // Proc. of SPIE Sym. of Visual Comm. and Image Proc. 1995. - V. 2. -P. 1108-1118.

87. Wong C.K., Au O.C., Tang C.W. Motion Compensated Temporal Interpolation with Overlapping I I Proc. of IEEE Int. Sym. on Circ. and Syst. -1996.-V. 2.-P. 608-611.

88. Yun Q. Shi, Huifang Sun. Image and video compression for multimedia engineering: fundamentals, algorithms and standarts. — NW: CRC Press LLC. 2000.-506 p.

89. Zhu S., Ma K.K. A new diamond search algorithm for fast block matching motion estimation //Proc. of Int. Conf. Information, Communications and Signal Processing. 1997. - V. 1. - P. 292-298.

90. ISO/IEC 11172-2: Information technology Coding of moving pictures and associated audio for digital storage media at up to about 1,5 Mbit/s - Part 2: Video.-1993.

91. ISO/IEC 13818-1: Information Technology Generic coding of moving pictures and associated audio information: System. — 1997.

92. ISO/IEC 13818-2: Information technology Generic coding of moving pictures and associated audio information: Video. - 2000.

93. ISO/IEC 14496-2: Information technology Coding of audio-visual objects -Part 2: Visual.-2001.

94. ISO/IEC 14496-10: Information technology Coding of audio-visual objects -- Part 10: Advanced Video Coding. - 2005.

95. ISO/IEC 15938, Information technology multimedia content description interface (MPEG-7). - 2002.

96. ITU-R Draft new Recommendation ITU-R BS. 10/20., Method for objective measurements of perceived audio quality. 1998.

97. ITU-T H.261. Video Codec for Audiovisual services at p x 64 kbits. 1990.

98. ITU-T H.263. Video coding for low bit rate communication. 2005.

99. ITU-T Recommendation J. 143. User requirements for objective perceptual video quality measurements in digital cable television. — 2000.

100. ITU-T ВТ. 801-1. Test signals for digitally encoded colour television signals conforming with Recommendations ITU-RBT.601 and ITU-R BT.656. -1995.

101. ITU-T ВТ. 802-1. Test pictures and sequences for subjective assessments of digital codecs conveying signals produced according to Recommendation ITU-RBT.601. 1994.f1

102. СПИСОК ИСПОЛЬЗУЕМЫХ ОБОЗНАЧЕНИЙ И СОКРАЩЕНИЙ

103. Biti-ate (битейт) применительно к компрессии видеоданных выражает степень сжатия потока, тем самым, определяя пропускную способность канала, требуемую для передачи потока в реальном времени.

104. САВАС (Context-adaptive binary arithmetic coding) — контекстнозависимое адаптивное бинарное арифметическое кодирование.

105. CAVLC (Context-adaptive variable-length coding) Контекстнозависимое адаптивное кодирование с переменной длиной кодового слова

106. CCITT {International Consultative Committee for Telegraphy and Telephony) подразделение ITU, разрабатывающее технические стандарты по всем международным аспектам цифровых и аналоговых коммуникаций.

107. DCT {Discrete Cosine Transform) — дискретное косинусное преобразование.

108. DPCM {differential pulse code modulation) — дифференциальная импульсно- кодовая модуляция.

109. DVD {digital versatile disc) — цифровой многоцелевой диск, носитель информации.

110. O {International Organization for Standardization) — международная организация, занимающаяся стандартизацией.

111. U {International Telecommunication Union) — Международный союз электросвязи.

112. U-T подразделение ITU, сектор стандартизации электросвязи, является преемником CCITT.

113. MB {macroblock) участок кадра, обычно имеющий размер 16x16 пикселей.

114. MSE {mean square error) — среднеквадратическая ошибка

115. MPEG {Motion Picture Experts Group) группа специалистов ISO, разрабатывающая стандартц сжатия цифрового видео и аудио.

116. MV (motion vector) — вектор движения, вектор похожести.

117. NTSC (от англ. National Television Standards Committee) — система аналогового цветного телевидения, принятая в качестве стандартной в США, Канаде, Японии и ряде стран Америки.

118. PAL (от англ. phase-alternating line) система аналогового цветного телевидения.

119. PCM {pulse code modulation) импульсно-кодовая модуляция.

120. PSNR (peak signal-to-noise ratio) — обозначает отношение между максимумом возможного значения сигнала и мощностью шума, искажающего значения сигнала.

121. SAD (sum of absolute differences) — сумма модулей ошибки.

122. SSE (sum of square errors) сумма квадратов ошибки.

123. VCR (от англ. video cassette recorder) устройства записи видеоданных для домашнего использования, использующие в качестве носителей магнитную пленку.