Введение
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
Приложение
