Содержание к диссертации
Введение
1 Анализ состояния проблемы 13
1.1 История видео компрессии 13
1.2 Основы видео компрессии, компенсация движения как метод устранения временной избыточности 21
1.3 Классификация методов компенсации движения 24
1.3.1 Классификация по типу сущностей, в терминах которых производится компенсация движения 24
1.3.2 Классификация по точности векторов движения 25
1.3.3 Классификация по мере оценки стоимости вектора движения 28
1.4 Обзор алгоритмов поиска движения, применяемых при сжатии видеоданных 31
1.4.1 Алгоритм полного перебора 31
1.4.2 Алгоритм поиска NTTS 33
1.4.3 Алгоритм поиска по алмазу 36
1.4.4 Алгоритм поиска РМКРЖГ 38
1.4.5 Алгоритм поиска СВА 40
1.4.6 Алгоритм поиска ADZS 42
1.4.7 Алгоритм поиска EPZS 48
2 Программная система сравнения алгоритмов поиска движения. реализация и сравнение современных алгоритмов поиска векторов похожести 56
2.1 Обоснование необходимости разработки программной системы сравнения алгоритмов поиска движения 57
2.2 Обзор аналогов программной системы MEFramework 57
2.2.1 VirtualDub MSUMotion Estimation Filter 57
2.2.2 Программа ME Analyzer 63
2.3 Обоснование выбора критериев оценки алгоритмов поиска движения 66
2.4 DirectShow как средство для работы с мультимедиа данными 68
2.4.1 История развития DirectShow 68
2.4.2 DirectShow фильтры 71
2.5 Описание реализации программной системы 74
2.6 Тестирование современных алгоритмов поиска движения и их сравнительный анализ на основе выбранных критериев 79
2.6.1 Описание тестовых видеопоследовательностей 79
2.6.2 Сравнительный анализ оценочных функций 86
2.5.1 Тестирование и сравнительный анализ алгоритмов поиска векторов похожести 89
3 Разработка и реализация оригинального алгоритма поиска движения. сравнение с аналогами 97
3.1 Обоснование необходимости разработки нового алгоритма 97
3.2 Требования к разрабатываемому алгоритму 97
3.3 Разработка метода нахождения первого приближения 100
3.4 Выбор метода локальной оптимизации 101
3.4.1 Симплексный метод 101
3.4.2 Метод Нельдера-Мида (деформируемых многогранников) . 103
3.4.3 Метод Гаусса-Зейделя (покоординатного спуска) і04
3.4.4 Метод Хука-Дживса 105
3.4.5 Градиентные методы. Метод наискорейшего спуска 108
3.4.6 Сравнение эффективности и выбор метода локальной оптимизации для алгоритма поиска движения 109
3.5 Описание предложенного алгоритма 113
3.6 Оценка эффективности разработанного алгоритма и
сравнение с аналогами 116
3.7. Разработка новой оценочной функции 120
3.9. Использование предложенного алгоритма в реальной системе компрессии видеоданных 125
Заключение 132
Литература 135
Приложение
- Основы видео компрессии, компенсация движения как метод устранения временной избыточности
- Обзор аналогов программной системы MEFramework
- Требования к разрабатываемому алгоритму
- Описание предложенного алгоритма
Введение к работе
Актуальность темы.
Пропускная способность компьютерных сетей продолжает расти, высокоскоростное соединение с домашним компьютером стало обычным явлением. Вместительность жёстких дисков, флэш-памяти и оптических устройств хранения данных стала больше чем когда-либо. Стоимость передачи и хранения информации становится всё меньше и меньше, однако проблема сжатия видеоданных не теряет своей актуальности. Алгоритмы сжатия видеоданных постоянно совершенствуются, создаются новые стандарты видеокомпрессии. Сжатие видеоданных предоставляет нам два важных преимущества. Во-первых, сжатие позволяет использовать цифровые видеоданные в таких средах хранения и передачи информации, в которых невозможно использовать видеоданные без компрессии. Во-вторых, сжатие видеоданных позволяет более эффективно использовать ресурсы среды передачи или хранения информации.
В настоящее время огромное внимание уделяется разработке алгоритмов сжатия видеоданных, использующих компенсацию движения. Начиная с 1980 года, организации ITU и MPEG последовательно выпускают ряд стандартов сжатия, использующих блочную компенсацию движения: Н.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].
Сложность разработки алгоритмов поиска векторов похожести обусловлена тем, что алгоритм должен отвечать сразу нескольким требованиям, подчас взаимоисключающим и требующим нахождения компромисса: найденные векторы похожести должны обеспечивать наибольшую степень сжатия блока; в связи с тем, что в битовую последовательность кодируется не сам вектор похожести, а его невязка с вектором предыдущего блока, желательно, что бы векторы похожести соседних блоков имели близкое значение; алгоритм поиска векторов похожести должен иметь низкую вычислительную сложность, вычисление оценочной функции должно производиться минимальное количество раз.
Актуальным также является исследование оценочных функций, об ладающих низкой вычислительной сложностью, но позволяющих с высо кой точностью оценить качество найденного вектора движения с точки зрения компрессии текущего блока. 'S
Цель состоит в разработке алгоритмического и программного обеспечения поиска векторов похожести, позволяющего улучшить производительность компрессоров и повысить степень компрессии видеоданных.
Для достижения поставленной цели необходимо решить следующие задачи: выполнить анализ существующих алгоритмов поиска векторов похожести; разработать программные средства сравнения алгоритмов поиска векторов похожести; реализовать и сравнить существующие алгоритмы поиска векторов похожести; разработать новую оценочную функцию; разработать и реализовать более эффективный по сравнению с аналогами алгоритм поиска векторов похожести.
Объектом исследования является компрессия цифровых видеоданных. Предметом исследования являются алгоритмы поиска векторов похожести, используемые при сжатии видеоданных.
Методы исследования. Результаты диссертации получены с помощью методов математического и имитационного моделирования, методов оптимизации и вычислительной математики. В процессе программной реализации теоретических результатов использовались методы теории алгоритмов, теории структур данных и объектно-ориентированного программирования.
Достоверность полученных в диссертационной работе результатов подтверждается: - результатами компьютерного (имитационного) моделирования; - совпадением с теоретическими оценками. Научная новизна работы состоит в следующем. . 1. Разработана программная система «MEFramework», позволяющая оценивать вычислительную сложность и эффективность алгоритмов поиска векторов похожести. Отличительными особенностями данной программной системы является возможность сравнивать степень компрессии и количество вызовов оценочной функции при сжатии с использованием различных алгоритмов поиска векторов похожести, а также возможность раздельно задавать оценочную функцию и алгоритм поиска.
Предложен оригинальный алгоритм поиска векторов похожести, отличающийся от известных использованием метода градиентного спуска для локального поиска, применением обратного прохода для уточнения найденных векторов похожести и использованием метода сканирования для векторов с плохим начальным приближением.
Предложена новая оценочная функция, используемая при поиске векторов похожести. В отличие от известных, предложенная оценочная функция позволяет учитывать не только сложность компрессии невязки блоков, но и сложность кодирования векторов похожести.
Практическая ценность.
Реализована программная система «MEFramework» в виде фильтра DirectShow. Программная система «MEFramework» позволяет оценивать вычислительную сложность и эффективность алгоритмов поиска векторов похожести. Отличительной особенностью данной программной системы является возможность раздельно задавать оценочную функцию и алгоритм поиска векторов похожести. Это позволяет оценивать эффективность алгоритмов поиска векторов похожести при использовании различных оценочных функций.
В качестве модулей системы «MEFramework» программно реализованы алгоритмы локального поиска, а также наиболее эффективные из известных алгоритмов поиска векторов похожести.
Программно реализован предложенный алгоритм поиска векторов похожести. Для предложенного алгоритма реализована новая оценочная функция. При помощи программной системы «MEFramework» произведено сравнение с современными аналогами. Экспериментальные результаты продемонстрировали преимущество разработанного алгоритма над аналогами.
4. Разработанный алгоритм поиска векторов похожести был внедрен компанией ООО «МэйнКонцепт-Дивикс» в составе коммерческого продукта «Mainconcept MPEG-2 Video Encoder»
Основные положения, выносимые на защиту
Разработанная программная система «MEFramework» позволяет количественно оценивать вычислительную сложность и степень компрессии, достигаемую при использовании различных алгоритмов поиска векторов похожести.
Использование оригинального алгоритма поиска векторов похожести, использующего метод градиентного спуска для локальной оптимизации, позволяет уменьшить количество вычислений оценочной функции и увеличить степень компрессии, достигаемую при сжатии видеоданных.
Использование новой оценочной функции, учитывающей сложность кодирования векторов, позволяет увеличить степень компрессии, достигаемую при сжатии видеоданных.
Внедрение результатов:
Алгоритм поиска векторов похожести, разработанный в рамках данной диссертационной работы, внедрен в коммерческий продукт компании ООО «МэйнКонцепт-Дивикс», Mainconcept MPEG-2 Video Encoder. Программная система «MEFramework» используется компанией ООО «МэйнКонцепт-Дивикс» для проведения внутренних испытаний алгоритмов поиска векторов похожести. Акт о внедрении приложен к диссертации.
Апробация работы Основные положения работы докладывались на следующих семинарах и конференциях:
1. XLIII международная научная студенческая конференция «Студент и научно-технический прогресс» - Новосибирск, 2005. Доклад отмечен дипломом третьей степени.
2. XI Всероссийская научная конференция студентов-физиков и молодых учёных - Екатеринбург, 2005.
Всероссийская научно-техническая конференция студентов, аспирантов и молодых учёных «Научная сессия ТУСУР-2005» - Томск, 2005. Доклад отмечен почётной грамотой «за лучший доклад».
Всероссийская научно-техническая конференция студентов, аспирантов и молодых ученых «Научная сессия ТУСУР - 2007» - Томск, 2007.
Научно-практическая конференция «Электронные средства и системы управления: итоги реализации программы развития электроники и ІТ-технологий в Томской области» - Томск, 2008. Доклад отмечен дипломом первой степени.
Научно-технические семинары кафедры автоматизированных систем управления, ТУСУР.
Публикации
По теме диссертации автором опубликованы 10 работ, в том числе 4 статьи в научных периодических журналах, из них 1 в журнале из перечня ВАК [9], 5 докладов опубликовано в материалах научных конференций и семинаров, зарегистрирована программа в Отраслевом фонде алгоритмов и программ (ОФАП).
1. Потапов П.В. Оптимизация распределения ресурсов при кодировании видеоданных // Информационные системы. - Томск: ТУСУР, 2004. С. 123 - 129.
Потапов П.В. Оптимальное распределение ресурсов при сжатии видеоданных с использованием двухпроходных алгоритмов // Материалы всероссийской научной конференции студентов-физиков. - Екатеринбург: АСФ, 2005. С. 251-254.
Потапов П.В. Оптимальное распределение ресурсов при сжатии видеоданных с использованием двухпроходного алгоритма // Материалы XLIII международной научной студенческой конференции «студент и научно-технический прогресс». - Новосибирск: НГУ, 2005. С. 45- 46.
4. Потапов П.В. Применение двухпроходного алгоритма для распределения ресурсов при сжатии видеоданных // Материалы всероссийской научно-технической конференции. — Томск: ТУСУР, 2005. С. 65-68.
Потапов П.В. Двухпроходный режим компрессии видеоданных // Доклады Томского государственного университета систем управления и радиоэлектроники. - Томск, 2005. - № 3 (11). С. 77-81.
Потапов П.В. Двухпроходные алгоритмы распределения ресурсов при сжатии видеоданных. Информационные системы: тр. постоянно действующего научно-технического семинара // Том. гос. ун-т систем упр. и радиоэлектроники, отд. проблем информатизации Том. Науч. Центра СО РАН. -Томск: ТУСУР, 2006. -№. 4. С. 10-18.
Кориков A.M., Потапов П.В. Программная среда для разработки и исследования алгоритмов оценки движения при сжатии видеоданных. // Вычислительные технологии, Институт вычислительных технологий СО РАН. - Томск, 2007. - Т. 12. - Спец. выпуск 1. С. 42-50.
Потапов П.В. Разработка программной среды для сравнения алгоритмов поиска видеоданных. // Материалы докладов Всероссийской Науч-но-Технической конференции студентов, аспирантов и молодых ученых «Научная сессия ТУСУР-2007». - Томск, 2007. С. 189-192.
Потапов П.В. Использование методов локальной оптимизации для поиска векторов похожести при сжатии видеоданных // Сб. науч. докл. Международной науч.-практ. конф. «Электронные системы и средства управления». — Томск, 2008. - С. 43 - 47.
Потапов П.В. Программная система моделирования поиска векторов похожести при сжатии видеоданных «MEFramework» II Отраслевой фонд алгоритмов и программ. Свидетельство об отраслевой регистрации разработки № 11657. Номер государственной регистрации: 50200802145. -2008.
Личный вклад
Основные результаты и положения, выносимые на защиту, выполнены автором лично. Автором лично была реализована программная система MEFramework. В качестве модулей к этой системы реализован ряд современных алгоритмов поиска векторов похожести, методов локальной оптимизации, а так же ряд оценочных функций, произведен сравнительный анализ. Новая оценочная функция разработана автором лично. Предлагаемый алгоритм поиска векторов похожести и экспериментальные данные разработаны и получены автором лично. Научный руководитель принимал участие в постановке целей и задач исследований, обсуждении полученных результатов.
Благодарности
Автор выражает глубокую благодарность научному руководителю Корикову A.M. за помощь в работе над диссертацией, статьями, решении организационных вопросов, и научный опыт, переданный в процессе совместной деятельности.
Также автор очень признателен коллегам из компаний ООО «Мэйн-Концепт-ДивИкс» Сергееву С.Н., Иванову В., Цурпал С, Милякову А. за ценные практические советы по общим вопросам сжатия видеоданных и критическое обсуждение промежуточных результатов в ходе работы над диссертацией.
Основы видео компрессии, компенсация движения как метод устранения временной избыточности
Компрессия это процесс сжатия данных с целью представления этих данных меньшим количеством бит. Сжатие предполагает наличие пары систем: компрессор и декомпрессор (енкодер, декодер). Компрессор преобразует исходные данные в сжатую форму (занимающую меньшее количество бит) перед передачей или сохранением данных. Декомпрессор преобразует данные из сжатой формы обратно к первоначальному виду [16 — 21].
Информация может быть сжата путём устранения из неё избыточности: - устранение пространственной избыточности - основано на том, что значения пикселей одного кадра обычно коррелированны и могут быть описаны более компактно. Так же используется подавление мелких деталей сцены, несущественных для её восприятия человеком (этот метод применяется при сжатии с потерями); - устранение избыточности математического представления основано на повышении информационной плотности результирующего цифрового потока путём выбора оптимального математического кода для его описания (например, использование более коротких кодовых слов для наиболее часто повторяемых значений); - устранение временной избыточности учитывает тот факт, что в пределах коротких интервалов времени (промежутков между кадрами) ви деоизображение обычно изменяется незначительно, например, происходит плавное смещение небольшого объекта на фоне фиксированного заднего плана. Статическую часть кадра можно кодировать как разницу с преды дущим кадром, а движущуюся часть описать при помощи вектора движе ния (вектора похожести). Устранение временной избыточности, и в част ности компенсация движения, позволяет существенно увеличить степень сжатия видеоданных [5]. В системах сжатия без потерь статистическая избыточность удаляется из сигнала таким образом, что сигнал может быть полностью восстановлен получателем без потерь. К сожалению, в настоящее время методы сжатия без потерь достигают небольшой степени компрессии видео и ау дио данных. Наиболее часто на практике применяются алгоритмы сжатия видеоданных, основанные на сжатии с потерями. Использование таких алгоритмов позволяет достичь большей степени сжатия, однако недостатком является то, что декодированные данные не являются полностью идентичными исходным. Целью алгоритма сжатия видеоданных является достижение высокой степени компрессии при минимальных искажениях, вносимых в процессе сжатия [7].
Большинство видеопоследовательностей содержат высокую временную избыточность, т.е. соседние кадры в последовательности обычно сильно коррелированны между собой (имеют много схожих частей). Разница между соседними кадрами часто соответствует движению в кадре объекта, либо движению камеры. Это движение может быть аппроксимировано как линейное движение объекта в кадре либо всего кадра. Таким образом, количество информации, которая должна быть передана, может быть уменьшено, в случае если передается только разница между текущим кадром и уже переданным. Такая методика сжатия видеоданных называется разностным предсказанием. Дальнейшее сжатие может быть достигнуто при использовании предсказания движения. Каждый блок в текущем кадре сопоставляется с блоком в предыдущем кадре, с которым имеется наибольшее сходство. Смещение между координатами двух блоков называется вектором похожести или вектором движения {Motion Vector). Невязка между текущим блоком и предсказанным блоком кодируется и передаётся вместе с вектором движения блока. На принимающей стороне оригинальный блок может быть восстановлен путём декодирования невязки значений пикселов блока и добавления её к значениям блока из предыдущего восстановленного кадра со смещением, соответствующим вектору движения. Процесс устранения временной избыточности с использованием векторов движения называется компенсацией движения {Motion Compensation) [11, 83].
Обзор аналогов программной системы MEFramework
Авторы программы: Дмитрий Ватолин, Карен Симонян, Сергей Гришин. Данное программное средство реализовано в качестве фильтра к утилите VirtualDub. Фильтр производит оценку и компенсацию движения из одного или нескольких кадров в видео потоке. Он позволяет отображать разбиение макроблоков, векторы похожести и точность векторов похожести [6]. Диалоговое окно основных настроек фильтра представлено на рис. 2.1.
Параметры программного средства, отображенные на главном диалоговом окне настроек фильтра: 1. Motion estimation preset - вид компенсации движения. В качестве видов компенсации движения можно выбрать настройки, соответствующие алгоритмам компенсации движения, использующимися в стандартах MPEG-2, MPEG-4, Н.264. 2. Motion estimation algorithm — алгоритм поиска векторов похожести из предыдущего кадра. 3. Block sizes - Размеры блоков, используемые при компенсации движения: Maximum block size — наибольший размер блока; Minimum block size - наименьший размер блока; 4. Precision - точность поиска вектора движения: Horizontal precision - точность поиска вектора движения по горизонтали. Pixel - пиксельная точность, Half pixel - полупиксельная точность, Quarter pixel — четверть-пиксельная точность. Vertical precision - точность поиска вектора движения по вертикали. Pixel — пиксельная точность, Half pixel — полу-пиксельная точность, Quarter pixel - четверть-пиксельная точность. 4. Halfpel interpolation algorithm - алгоритм полу-пиксельной интерполяции. 5. Number of reference frames — число опорных кадров. Может принимать значения от 1 до 10. Если указан 1 опорный кадр, то производится компенсация только из предыдущего кадра. 6. Search radius — радиус окна поиска вектора движения Horizontal - максимальная длина горизонтальной проекции вектора движения. Может принимать значения от 1 до 100. Vertical - максимальная длина вертикальной проекции вектора движения. Может принимать значения от 1 до 100. 7. Output - выходные данные фильтра: Compensated frame - выводить скомпенсированный кадр. Residual after motion compensation - выводить межкадровую разницу после компенсации движения. Residual without motion compensation - выводить межкадровую разницу без компенсации движения. 8. Borders allowed - разрешить компенсацию из блоков, выходящих за границы кадра.
Требования к разрабатываемому алгоритму
Сложность разработки алгоритмов поиска векторов похожести обусловлена тем, что алгоритм должен отвечать сразу нескольким требованиям, подчас взаимоисключающим и требующим нахождения компромисса: - найденные векторы похожести должны обеспечивать наибольшую степень сжатия блока; - желательно, чтобы найденные векторы похожести соседних блоков имели одинаковое направление, так как в битовую последовательность кодируется не сам вектор похожести, а его невязка с вектором предыдущего блока; - алгоритм поиска векторов похожести должен иметь низкую вычислительную сложность, вычисление оценочной функции должно производиться минимальное количество раз.
График поверхности оценочной функции SAD, вычисляемой по формуле (1.4), построенный для одного из блоков тестовой последовательности, представлен на рис. 3.1.
По виду поверхности оценочной функции можно сделать вывод о том, что функция не является выпуклой, имеет множество локальных минимумов и оврагов. Таким образом, использование методов локальной оп тимизации не будет эффективным, если в качестве начальной точки поиска использовать точку, соответствующую нулевому вектору (0, 0). В связи с этим алгоритм поиска векторов похожести решено разбить на следующие этапы:
1. Алгоритм нахождения первого приближения. Поверхность оценочной функции не является гладкой. Имеется множество локальных минимумов и оврагов, потому так важно найти точку первого приближения, прежде чем приступать к уточняющему поиску. Алгоритм нахождения первого приближения должен учитывать векторы похожести соседних блоков, а также векторы похожести предыдущего кадра. Это увеличит точность нахождения точки первого приближения, а значит, может сократить количество итераций и качество работы уточняющего алгоритма. Количество вычислений оценочной функции при нахождении точки первого приближения должно быть наименьшим, исходя из требования низкой вычислительной сложности алгоритма поиска векторов похожести.
2. Алгоритм уточняющего (локального) поиска. Алгоритм локального поиска используется для уточнения вектора похожести, полученного на первом этапе поиска. Количество итераций локального поиска, а так же количество вычислений оценочной функции должно быть минимально исходя из требования низкой вычислительной сложности алгоритма поиска векторов похожести. Уточняющий поиск должен находить векторы похожести с точностью до одного пиксела.
3. Завершающая обработка найденных векторов. В завершающей стадии поиска, когда найдены векторы для всех блоков кадра, можно про вести анализ полученных векторов и скорректировать векторы некоторых блоков в соответствии с направлением векторов похожести соседних блоков.
При разработке метода нахождения первого приближения было решено использовать модификацию метода проверки векторов-кандидатов, использованного в алгоритмах PMVFAST и EPZS. В отличии от EPZS, векторы-кандидаты берутся не только из соседних блоков данного кадра, но так же и из соседних блоков предыдущего кадра [27]. Так же используется схема интерполяции векторов из предыдущего кадра.
Алгоритм метода нахождения первого приближения: 1) находится медианный предиктор, вычисляется значение оценочной функции, соответствующее этому вектору. Если полученное значение меньше чем пороговое значение Т1у то останавливаем выполнение алгоритма. В качестве вектора начального приближения принимаем медианный предиктор; 2) формируются список векторов кандидатов. В этот список заносятся векторы соседних блоков данного в данном кадре и в предыдущем кадре. Также в список заносятся интерполированные векторы из предыдущего кадра; 3) сформированный список векторов кандидатов подвергается прореживанию - вектор похожести отбрасывается, если расстояние от него до другого вектора-кандидата меньше или равно шагу поиска уточняющего алгоритма; 4) производится вычисление значений оценочной функции в точках, соответствующих оставшимся векторам-кандидатам. Выбирается лучший вектор-кандидат; 5) в случае если значение оценочной функции для выбранного вектора-кандидата меньше порогового значения Т2, либо количество векторов-кандидатов равно нулю, производится дополнительный поиск сканированием в окрестности точки (0,0).
Описание предложенного алгоритма
Для определения точки начального приближения мы можем использовать найденные векторы похожести соседних блоков в текущем кадре, а так же векторы похожести из предыдущего кадра. Использование этой априорной информации и есть основная идея метода поиска начального приближения вектора похожести. Изложим алгоритм реализации этой идеи с помощью рис. 3.5, на котором представлены блоки, векторы которых используются для нахождения векторы начального приближения: Л) векторы соседних блоков MBj, MB 2, MB з (рис. 3.5) используются для определения так называемого медианного (среднего) вектора [4]. Вычисляем значение оценочной функции для медианного вектора. Сравниваем это значение с пороговой величиной 77, если полученное значение меньше чем 77 переходим к уточняющему поиску, в противном случае переходим к следующему шагу 2. Пороговая величина 77 вычисляется исходя из значений оценочных функций соседних блоков по формуле: 71 = ак min(&4 Д, SAD2, SAD , SAD4 ) + bk; 2) составляем список векторов-кандидатов. В этот список добавляем найденные векторы соседних блоков в текущем и предыдущем кадрах. Так же в список добавляются интерполированные векторы: если в предыдущем кадре вектор похожести какого либо из блоков указывал в текущий блок, то этот вектор так же добавляется в список; 3) из списка векторов-кандидатов удаляются близкие векторы. Для всех векторов попарно рассчитывается величина из списка векторов-кандидатов. Исходя из шага поиска алгоритма локальной оптимизации, было принято решение использовать значение параметра Т2, равное 4; 4) вычисление оценочной функции производится для всех оставшихся векторов-кандидатов. Вектор-кандидат с наименьшим значением оценочной функции принимается за вектор начального приближения; 5) если значение оценочной функции в точке начального приближения больше чем 73 = 2П, то принимаем решение о том, что точка начального приближения найдена неудачно и производим её адаптивный поиск 115методом сканирования в зависимости от размеров поискового окна и разрешения изображения. В результате работы данного алгоритма мы получаем точку начального приближения. На следующем этапе происходит уточнение найденного вектора похожести. Для проведения уточняющего поиска выбран градиентный метод локальной оптимизации. Градиентный метод сводится к следующему итерационном процессу: 1) в точке Vk вычисляется градиент оценочной функции. Вычисле ние градиента оценочной функции в зависимости от ситуации производит ся методом прямой (упреждающей), либо обратной (отстающей) конечной разности по формулам: Для определения оптимального значения параметра Л был проведён следующий эксперимент: тестовые видеопоследовательности сжимались с применением разработанного алгоритма с параметрами Л, равными 1, 2, 3, 4, 5, 6, 7, 8. Наименьшее количество вызовов оценочной функции при наименьшем размере сжатой видеопоследовательности было получено для значения Я = 4. Экспериментально найдено, что метод поиска с использованием градиента требует меньше вычислений оценочной функции для нахождения локального минимума, чем методы нулевого порядка, такие как метод Га усса-Зейделя, метод Хука-Дживса, симплексный метод. Так же метод локальной оптимизации с использованием градиента требует меньше вычислений оценочной функции по сравнению с методами поиска по шаблону, применяемыми в алгоритмах Diamond, PMl FAST, EPZS. После нахождения векторов похожести для всех блоков кадра производится уточняющий обратный проход. На этом этапе проходим все блоки кадра в обратном порядке. По сравнению с первым проходом появляется информация о векторах похожести блоков расположенных ниже и правее текущего блока. Если значение оценочной функции, полученное для текущего блока меньше значений оценочных функций соседних блоков, то проверяем значения оценочных функций для векторов этих векторов. Если значение оценочной функции меньше чем для найденного на первом проходе вектора похожести, проводим уточняющий поиск для вектора с наименьшим значением оценочной функции [22].
