Блок соответствие Алгоритм представляет собой способ определения местоположения , соответствующие макроблоков в последовательности цифровых видео кадров для целей оценки движения . Основное предположение, лежащее в основе оценки движения, состоит в том, что шаблоны, соответствующие объектам и фону в кадре видеопоследовательности, перемещаются внутри кадра, чтобы сформировать соответствующие объекты в следующем кадре. Это можно использовать для обнаружения временной избыточности в видеопоследовательности, повышая эффективность межкадрового сжатия видео путем определения содержимого макроблока посредством ссылки на содержимое известного макроблока, которое минимально отличается.
Алгоритм сопоставления блоков включает разделение текущего кадра видео на макроблоки и сравнение каждого из макроблоков с соответствующим блоком и его соседними соседями в ближайшем кадре видео (иногда только с предыдущим). Создается вектор , моделирующий перемещение макроблока из одного места в другое. Это движение, вычисленное для всех макроблоков, составляющих кадр, составляет движение, оцениваемое в кадре.
Область поиска для хорошего совпадения макроблока определяется «параметром поиска» p, где p - количество пикселей на всех четырех сторонах соответствующего макроблока в предыдущем кадре. Параметр поиска - это мера движения. Чем больше значение p, тем больше потенциальное движение и возможность найти хорошее совпадение. Однако полный поиск всех потенциальных блоков - это дорогостоящая задача. Типичные входы - это макроблок размером 16 пикселей и область поиска p = 7 пикселей.
Блочное сопоставление и трехмерная фильтрация используют этот подход для решения различных обратных задач восстановления изображения, таких как уменьшение шума [1] и устранение размытости [2] как в неподвижных изображениях, так и в цифровом видео .
Мотивация
Оценка движения - это процесс определения векторов движения, которые описывают преобразование из одного 2D-изображения в другое; обычно из соседних кадров в видеопоследовательности. Векторы движения могут относиться ко всему изображению (оценка глобального движения) или конкретным частям, таким как прямоугольные блоки, участки произвольной формы или даже к каждому пикселю. Векторы движения могут быть представлены трансляционной моделью или многими другими моделями, которые могут аппроксимировать движение реальной видеокамеры, например вращение и перемещение во всех трех измерениях и масштабирование.
Применение векторов движения к изображению для прогнозирования преобразования в другое изображение из-за движущейся камеры или объекта на изображении называется компенсацией движения . Комбинация оценки движения и компенсации движения является ключевой частью сжатия видео, используемого MPEG 1, 2 и 4, а также многими другими видеокодеками .
Сжатие видео на основе оценки движения помогает экономить биты, отправляя закодированные разностные изображения, которые по своей природе имеют меньшую энтропию, чем отправка полностью кодированного кадра. Однако наиболее затратной с точки зрения вычислений и ресурсоемких операций во всем процессе сжатия является оценка движения. Следовательно, для сжатия видео необходимы быстрые и недорогие в вычислительном отношении алгоритмы оценки движения.
Метрики оценки
Метрика для сопоставления макроблока с другим блоком основана на функции стоимости. Самыми популярными с точки зрения вычислительных затрат являются:
Средняя разница или Средняя абсолютная разница (MAD) =
Среднеквадратичная ошибка (MSE) =
где N - размер макроблока, а а также - пиксели, сравниваемые в текущем макроблоке и опорном макроблоке, соответственно.
Изображение с компенсацией движения, которое создается с использованием векторов движения и макроблоков из опорного кадра, характеризуется пиковым отношением сигнал / шум (PSNR),
Алгоритмы
Алгоритмы блочного сопоставления исследуются с середины 1980-х годов. Было разработано множество алгоритмов, но ниже описаны лишь некоторые из самых основных или часто используемых.
Исчерпывающий поиск
Этот алгоритм вычисляет функцию стоимости в каждом возможном месте в окне поиска. Это приводит к наилучшему совпадению макроблока в опорном кадре с блоком в другом кадре. Получающееся в результате изображение с компенсацией движения имеет наивысшее пиковое отношение сигнал / шум по сравнению с любым другим алгоритмом сопоставления блоков. Однако это самый обширный алгоритм сопоставления блоков из всех. Окно поиска большего размера требует большего количества вычислений.
Оптимизированное иерархическое сопоставление блоков (OHBM)
Алгоритм оптимизированного иерархического сопоставления блоков (OHBM) ускоряет исчерпывающий поиск на основе оптимизированных пирамид изображений. [3]
Трехэтапный поиск
Это один из первых алгоритмов быстрого сопоставления блоков. Он работает следующим образом:
- Начните с поиска в центре
- Установите размер шага S = 4 и параметр поиска p = 7
- Поиск в 8 точках +/- S пикселей вокруг местоположения (0,0) и местоположения (0,0)
- Выберите среди 9 найденных местоположений одно с функцией минимальных затрат.
- Установите новую точку поиска в указанное выше место
- Установите новый размер шага как S = S / 2
- Повторяйте процедуру поиска до тех пор, пока S = 1.
Результирующее местоположение для S = 1 - это местоположение с функцией минимальной стоимости, и макроблок в этом местоположении является наилучшим соответствием.
В этом алгоритме сокращение вычислений в 9 раз. Для p = 7, в то время как ES оценивает стоимость для 225 макроблоков, TSS оценивает только для 25 макроблоков.
Двумерный логарифмический поиск
TDLS тесно связан с TSS, однако он более точен для оценки векторов движения для большого размера окна поиска. Алгоритм можно описать следующим образом:
- Начните с поиска в центре
- Выберите начальный размер шага, скажем, S = 8
- Найдите 4 точки на расстоянии S от центра по осям X и Y
- Найдите местоположение точки с функцией наименьших затрат
- Если точка, отличная от центра, является наилучшей точкой совпадения,
- Выберите эту точку как новый центр
- Повторите шаги с 2 по 3.
- Если лучшая точка совпадения находится в центре, установите S = S / 2.
- Если S = 1, ищутся все 8 точек вокруг центра на расстоянии S.
- Задайте вектор движения как точку с функцией наименьшей стоимости
Новый трехэтапный поиск
TSS использует равномерно распределенный шаблон проверки и склонен пропускать небольшие движения. NTSS [4] является усовершенствованием по сравнению с TSS, поскольку он обеспечивает схему поиска со смещением по центру и имеет условия для остановки на полпути для снижения вычислительных затрат. Это был один из первых широко распространенных быстрых алгоритмов, который часто использовался для реализации более ранних стандартов, таких как MPEG 1 и H.261.
Алгоритм работает следующим образом:
- Начните с поиска в центре
- Поиск 8 местоположений +/- S пикселей с S = 4 и 8 местоположений +/- S пикселей с S = 1 вокруг местоположения (0,0)
- Выберите среди 16 найденных местоположений одно с функцией минимальных затрат.
- Если функция минимальной стоимости встречается в начале координат, остановите поиск и установите вектор движения на (0,0)
- Если функция минимальной стоимости встречается в одном из 8 местоположений при S = 1, установите новый источник поиска для этого местоположения.
- Проверьте смежные веса для этого местоположения, в зависимости от местоположения он может проверять 3 или 5 баллов.
- Тот, который дает наименьший вес, является ближайшим соответствием, установите вектор движения в это место
- Если наименьший вес после первого шага был в одном из 8 местоположений при S = 4, обычная процедура TSS выполняется следующим образом.
- Выберите среди 9 найденных местоположений одно с функцией минимальных затрат.
- Установите новую точку поиска в указанное выше место
- Установите новый размер шага как S = S / 2
- Повторяйте процедуру поиска до тех пор, пока S = 1.
Таким образом, этот алгоритм проверяет 17 точек для каждого макроблока, и в наихудшем сценарии проверяется 33 местоположения, что по-прежнему намного быстрее, чем TSS.
Простой и эффективный поиск
Идея TSS заключается в том, что поверхность ошибки из-за движения в каждом макроблоке является одномодальной . Унимодальная поверхность - это поверхность в форме чаши, так что веса, генерируемые функцией стоимости, монотонно увеличиваются от глобального минимума. Однако унимодальная поверхность не может иметь два минимума в противоположных направлениях, и, следовательно, поиск фиксированного шаблона по 8 точкам TSS может быть дополнительно модифицирован, чтобы включить это и сохранить вычисления. SES [5] является расширением TSS, которое включает это предположение.
Алгоритм SES улучшает алгоритм TSS, поскольку каждый шаг поиска в SES делится на две фазы:
• Первая фаза :
• Разделите область поиска на четыре квадранта • Начните поиск с трех местоположений: одно в центре (A), а другие (B и C), S = 4 местоположения от точки A в ортогональных направлениях. А = 34,0444094, -1177977943; В = 34,043634, -117,7897651; С = 34,04453, -117,7977953 • Найдите точки в квадранте поиска для второй фазы, используя распределение весов для A, B, C: • Если (MAD (A)> = MAD (B) и MAD (A)> = MAD (C)), выберите точки во втором квадранте фазы IV • Если (MAD (A)> = MAD (B) и MAD (A) <= MAD (C)), выберите точки во втором квадранте фазы I. • Если (MAD (A)• Если (MAD (A) = MAD (C)), выберите точки во втором квадранте фазы III
• Вторая фаза:
• Найдите место с наименьшим весом • Установите новое начало поиска как точку, найденную выше.
• Установите новый размер шага как S = S / 2.
• Повторяйте процедуру поиска SES до тех пор, пока S = 1.
• Выберите место с наименьшим весом, так как вектор движения SES очень эффективен с вычислительной точки зрения по сравнению с TSS. Однако достигнутое пиковое отношение сигнал / шум оставляет желать лучшего по сравнению с TSS, поскольку в действительности поверхности ошибок не являются строго одномодальными. 34.0444094
Четырехэтапный поиск
Четырехэтапный поиск является улучшением по сравнению с TSS с точки зрения более низкой стоимости вычислений и лучшего отношения пикового сигнала к шуму. Подобно NTSS, FSS [6] также использует поиск со смещением по центру и имеет положение остановки на полпути.
Алгоритм работает следующим образом:
- Начните с поиска в центре
- Установите размер шага S = 2, (независимо от параметра поиска p)
- Искать в 8 точках +/- S пикселей вокруг местоположения (0,0) местоположения 1 = 34.0460965, -117.7955275;
2 = 34,0464443, -117,7990496; 3 = 34,0446975, -117,7999699; 4 = 34,0438915, -117,7952174
- Выберите среди 9 найденных местоположений одно с функцией минимальных затрат.
- Если минимальный вес находится в центре окна поиска:
- Установите новый размер шага как S = S / 2 (то есть S = 1)
- Повторите процедуру поиска с шагов 3 по 4.
- Выберите место с наименьшим весом в качестве вектора движения
- Если минимальный вес находится в одном из 8 мест, кроме центра:
- Установите новую точку отсчета в этом месте
- Зафиксируем размер шага как S = 2.
- Повторите процедуру поиска с шагов 3 по 4. В зависимости от местоположения нового источника выполните поиск в 5 или 3 местах.
- Выберите место с наименьшим весом 34.043634, -117.7897651
- Если место наименьшего веса находится в центре нового окна, переходите к шагу 5, иначе переходите к шагу 6
Алмазный поиск
Алгоритм Diamond Search (DS) [7] использует шаблон точки поиска в виде ромба, и алгоритм работает точно так же, как 4SS. Однако нет ограничений на количество шагов, которые может предпринять алгоритм.
Для поиска используются два разных типа фиксированных шаблонов,
- Большой ромбовидный поисковый образец (LDSP)
- Шаблон поиска малого ромба (SDSP)
Алгоритм работает следующим образом:
- ЛДСП:
- Начните с поиска в центре
- Установите размер шага S = 2
- Поиск в 8 пикселях местоположения (X, Y) таким образом, что (| X | + | Y | = S) вокруг местоположения (0,0) с использованием шаблона точки поиска в виде ромба
- Выберите среди 9 найденных местоположений одно с функцией минимальных затрат.
- Если минимальный вес находится в центре окна поиска, перейдите к шагу SDSP.
- Если минимальный вес находится в одном из 8 местоположений, кроме центра, установите новое начало координат в этом месте.
- Повторить ЛДСП
- SDSP:
- Установить новую точку поиска
- Установите новый размер шага как S = S / 2 (то есть S = 1)
- Повторите процедуру поиска, чтобы найти место с наименьшим весом.
- Выберите местоположение с наименьшим весом как расположение вектора движения вектора движения с наименьшим весом 34.0444094, -1177977943
Этот алгоритм очень точно находит глобальный минимум, поскольку шаблон поиска не слишком велик и не слишком мал. Алгоритм алмазного поиска имеет пиковое отношение сигнал / шум, близкое к таковому у исчерпывающего поиска, при значительно меньших вычислительных затратах.
Адаптивный поиск по шаблону руда
Алгоритм адаптивного поиска шаблона местоположения (ARPS) [8] использует тот факт, что общее движение в кадре обычно является когерентным , т.е. если макроблоки вокруг текущего макроблока перемещаются в определенном направлении, то существует высокая вероятность того, что текущий макроблок также будет иметь похожий вектор движения . Этот алгоритм использует вектор движения макроблока слева от него для прогнозирования собственного вектора движения.
Адаптивный поиск по шаблону руда выполняется следующим образом:
- Начните с поиска в центре (исходной точке)
- Найдите прогнозируемый вектор движения для блока
- Установите размер шага S = max (| X |, | Y |), где (X, Y) - координата прогнозируемого вектора движения.
- Поиск распределенных точек диаграммы направленности вокруг исходной точки с шагом S
- Установите точку с наименьшим весом в качестве исходной точки
- Поиск с использованием шаблона поиска в виде маленького ромба (SDSP) вокруг нового источника
- Повторяйте поиск SDSP, пока наименее взвешенная точка не окажется в центре SDSP.
Поиск по шаблону Rood напрямую помещает поиск в область, где есть высокая вероятность найти хороший совпадающий блок. Основное преимущество ARPS над DS заключается в том, что если прогнозируемый вектор движения равен (0, 0), он не тратит время вычислений на выполнение LDSP, но сразу начинает использовать SDSP. Кроме того, если прогнозируемый вектор движения находится далеко от центра, тогда ARPS снова экономит на вычислениях, напрямую перескакивая к этой окрестности и используя SDSP, тогда как DS не торопится, выполняя LDSP.
Рекомендации
- ^ Dabov, Kostadin; Фой, Алессандро; Катковник, Владимир; Егиазарян, Карен (16 июля 2007 г.). «Шумоподавление изображения с помощью разреженной совместной фильтрации в области трехмерного преобразования». IEEE Transactions по обработке изображений . 16 (8): 2080–2095. Bibcode : 2007ITIP ... 16.2080D . CiteSeerX 10.1.1.219.5398 . DOI : 10.1109 / TIP.2007.901238 . PMID 17688213 . S2CID 1475121 .
- ^ Даниелян, Арам; Катковник, Владимир; Егиазарян, Карен (30 июня 2011 г.). "Рамки BM3D и удаление размытых изображений". IEEE Transactions по обработке изображений . 21 (4): 1715–28. arXiv : 1106.6180 . Bibcode : 2012ITIP ... 21.1715D . DOI : 10.1109 / TIP.2011.2176954 . PMID 22128008 . S2CID 11204616 .
- ^ Дже, Чансу; Пак, Хён Мин (2013). «Оптимизированное иерархическое сопоставление блоков для быстрой и точной регистрации изображений». Обработка сигналов: передача изображений . 28 (7): 779–791. DOI : 10.1016 / j.image.2013.04.002 .
- ^ Ли, Жэньсян; Цзэн, Бинг; Лиу, Мин (август 1994). «Новый трехэтапный алгоритм поиска для оценки движения блока». IEEE Trans. Схемы и системы для видеотехники . 4 (4): 438–442. DOI : 10.1109 / 76.313138 .
- ^ Лу, Цзяньхуа; Лиу, Мин (апрель 1997 г.). «Простой и эффективный алгоритм поиска для оценки движения с сопоставлением блоков». IEEE Trans. Схемы и системы для видеотехники . 7 (2): 429–433. DOI : 10.1109 / 76.564122 .
- ^ По, Лай-Ман; Ма, Вин-Чунг (июнь 1996 г.). «Новый четырехэтапный алгоритм поиска для быстрой оценки движения блока». IEEE Trans. Схемы и системы для видеотехники . 6 (3): 313–317. DOI : 10.1109 / 76.499840 .
- ^ Чжу, Шань; Ма, Кай-Куанг (февраль 2000 г.). «Новый алгоритм алмазного поиска для оценки движения с быстрым согласованием блоков». EEE Trans. Обработка изображений . 9 (12): 287–290. DOI : 10.1109 / 83.821744 . PMID 18255398 .
- ^ Не, Яо; Ма, Кай-Куанг (декабрь 2002 г.). «Адаптивный поиск по образцу руда для оценки движения с быстрым согласованием блоков» (PDF) . IEEE Trans. Обработка изображений . 11 (12): 1442–1448. DOI : 10.1109 / TIP.2002.806251 . PMID 18249712 .
Внешние ссылки
1. http://www.mathworks.com/matlabcentral/fileexchange/8761-block-matching-algorithms-for-motion-estimation
2. https://www.ece.cmu.edu/~ee899/project/deepak_mid.htm