Алгоритм сопоставления блоков

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

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

Область поиска для хорошего соответствия макроблока определяется «параметром поиска» p, где p — количество пикселей на всех четырех сторонах соответствующего макроблока в предыдущем кадре. Параметр поиска — это мера движения. Чем больше значение p, тем больше потенциальное движение и вероятность найти хорошее совпадение. Однако полный поиск всех потенциальных блоков является вычислительно дорогостоящей задачей. Типичные входные данные — это макроблок размером 16 пикселей и область поиска p = 7 пикселей.

Сопоставление блоков и 3D-фильтрация используют этот подход для решения различных восстановления изображений, обратных задач таких как уменьшение шума. ^[1] и устранение размытия ^[2] как в неподвижных изображениях, так и в цифровом видео .

Мотивация

Оценка движения — это процесс определения векторов движения , которые описывают преобразование одного 2D-изображения в другое; обычно из соседних кадров видеопоследовательности. Векторы движения могут относиться ко всему изображению (глобальная оценка движения) или к конкретным частям, таким как прямоугольные блоки, участки произвольной формы или даже к каждому пикселю. Векторы движения могут быть представлены поступательной моделью или многими другими моделями, которые могут аппроксимировать движение реальной видеокамеры, например вращение и перемещение во всех трех измерениях и масштабирование.

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

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

Метрики оценки

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

Средняя разница или средняя абсолютная разница (MAD) = ${\frac {1}{N^{2}}}\sum _{i=0}^{n-1}\sum _{j=0}^{n-1}|C_{ij}-R_{ij}|$

Среднеквадратическая ошибка (MSE) = ${\frac {1}{N^{2}}}\sum _{i=0}^{n-1}\sum _{j=0}^{n-1}(C_{ij}-R_{ij})^{2}$

где N — размер макроблока, а $C_{ij}$ и $R_{ij}$ – это пиксели, сравниваемые в текущем макроблоке и эталонном макроблоке соответственно.

Изображение с компенсацией движения, созданное с использованием векторов движения и макроблоков из опорного кадра, характеризуется пиковым отношением сигнал/шум (PSNR),

${\text{PSNR}}=10\log _{10}{\frac {({\text{peak to peak value of original data}})^{2}}{\text{MSE}}}$

Алгоритмы

Алгоритмы сопоставления блоков исследуются с середины 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.
Найдите местоположение точки с функцией наименьшей стоимости.
Если точка, отличная от центра, является наилучшей точкой соответствия,
1. Выберите эту точку в качестве нового центра
Если лучшая точка совпадения находится в центре, установите S = S/2.
Повторите шаги 2–3.
всех 8 местоположений вокруг центра на расстоянии S. Если S = 1, выполняется поиск
Установите вектор движения как точку с наименьшей функцией стоимости.

Новый трехэтапный поиск

TSS использует единый шаблон проверки и склонен пропускать небольшие движения. НТСС ^[4] является улучшением по сравнению с TSS, поскольку он обеспечивает схему поиска со смещением по центру и имеет возможность остановки на полпути для снижения вычислительных затрат. Это был один из первых широко распространенных быстрых алгоритмов, который часто использовался для реализации более ранних стандартов, таких как MPEG 1 и H.261.

Алгоритм работает следующим образом:

Начните с поиска местоположения в центре
Найдите 8 локаций +/- S пикселей с S = 4 и 8 локаций +/- S пикселей с S = 1 вокруг локации (0,0)
Выберите среди 16 найденных местоположений то, у которого есть функция минимальной стоимости.
Если функция минимальной стоимости встречается в начале координат, остановите поиск и установите вектор движения на (0,0).
Если функция минимальной стоимости встречается в одном из 8 мест при S = 1, установите новое начало поиска в это место.
1. Проверьте соседние веса для этого местоположения. В зависимости от местоположения можно проверить либо 3, либо 5 точек.
Тот, который дает наименьший вес, является наиболее близким, установите вектор движения в это место.
Если наименьший вес после первого шага был в одном из 8 мест при S = 4, следует обычная процедура TSS.
1. Выберите среди 9 найденных местоположений то, у которого есть функция минимальной стоимости.
2. Установите новый источник поиска в выбранное выше место.
3. Установите новый размер шага как S = S/2.
4. Повторяйте процедуру поиска до тех пор, пока S = 1.

Таким образом, этот алгоритм проверяет 17 точек для каждого макроблока, а в худшем случае проверяется 33 местоположения, что все равно намного быстрее, чем TSS.

Простой и эффективный поиск

Идея TSS заключается в том, что поверхность ошибок из-за движения в каждом макроблоке является унимодальной . Унимодальная поверхность — это поверхность в форме чаши, у которой веса, генерируемые функцией стоимости, монотонно увеличиваются от глобального минимума. Однако унимодальная поверхность не может иметь два минимума в противоположных направлениях, и, следовательно, 8-точечный поиск по фиксированному шаблону TSS можно дополнительно модифицировать, чтобы включить это и сэкономить вычисления. СЭС ^[5] является расширением TSS, включающим это предположение.

Алгоритм SES совершенствует алгоритм TSS, поскольку каждый шаг поиска в SES разделен на две фазы:

• Первый этап:

     • Divide the area of search in four quadrants
     • Start search with three locations, one at center (A) and others (B and C), S=4 locations away from A in orthogonal directions
     • Find points in search quadrant for second phase using the weight distribution for A, B, C:
            • If (MAD(A)>=MAD(B) and MAD(A)>=MAD(C)), select points in second phase quadrant IV
            • If (MAD(A)>=MAD(B) and MAD(A)<=MAD(C)), select points in second phase quadrant I
            • If (MAD(A)<MAD(B) and MAD(A)<MAD(C)), select points in second phase quadrant II
            • If (MAD(A)<MAD(B) and MAD(A)>=MAD(C)), select points in second phase quadrant III

• Второй этап:

     • Find the location with lowest weight
     • Set the new search origin as the point found above

• Установите новый размер шага как S = S/2.

• Повторяйте процедуру поиска SES до тех пор, пока S=1.

• Выберите место с наименьшим весом в качестве вектора движения. SES в вычислительном отношении очень эффективен по сравнению с TSS. Однако достигаемое пиковое отношение сигнал/шум ниже по сравнению с TSS, поскольку поверхности ошибок в действительности не являются строго унимодальными.

Четырехшаговый поиск

Четырехшаговый поиск — это улучшение по сравнению с TSS с точки зрения меньших вычислительных затрат и лучшего пикового соотношения сигнал/шум. Похоже на: НТСС, ФСС ^[6] также используется поиск со смещением по центру и предусмотрена остановка на полпути.

Алгоритм работает следующим образом:

Начните с поиска местоположения в центре
Установить размер шага S = 2 (независимо от параметра поиска p)
Поиск 8 локаций +/- S пикселей вокруг локации (0,0)
Выберите среди 9 найденных местоположений то, у которого есть функция минимальной стоимости.
Если минимальный вес находится в центре окна поиска:
1. Установите новый размер шага как S = S/2 (то есть S = 1).
2. Повторите процедуру поиска с пунктов 3 по 4.
3. Выберите местоположение с наименьшим весом в качестве вектора движения.
Если минимальный вес обнаружен в одном из 8 мест, кроме центра:
1. Установите новое начало координат в этом месте
2. Зафиксируйте размер шага как S = 2.
3. Повторите процедуру поиска с шагов 3 по 4. В зависимости от местоположения нового источника выполните поиск по 5 или 3 местоположениям.
4. Выберите место с наименьшим весом
5. Если место с наименьшим весом находится в центре нового окна, перейдите к шагу 5, в противном случае перейдите к шагу 6.

Поиск алмазов

Поиск алмазов (DS) ^[7] Алгоритм использует ромбовидный шаблон поиска точек и работает точно так же, как и 4SS. Однако количество шагов, которые может выполнить алгоритм, не ограничено.

Для поиска используются два разных типа фиксированных шаблонов:

Шаблон поиска большого ромба (LDSP)
Схема поиска «маленький ромб» (SDSP)

Алгоритм работает следующим образом:

ЛДСП:

1. Начните с поиска местоположения в центре
2. Установить размер шага S = 2
3. Найдите 8 пикселей местоположения (X,Y) так, что (|X|+|Y|=S) вокруг местоположения (0,0), используя ромбовидный шаблон поиска точек.
4. Выберите среди 9 найденных местоположений то, у которого есть функция минимальной стоимости.
5. Если минимальный вес найден в центре окна поиска, перейдите к шагу SDSP.
6. Если минимальный вес обнаружен в одном из 8 мест, кроме центра, установите новое начало координат в этом месте.
7. Повтор ЛДСП

СДСП:

1. Установите новый источник поиска
2. Установите новый размер шага как S = S/2 (то есть S = 1).
3. Повторите процедуру поиска, чтобы найти местоположение с наименьшим весом.
4. Выберите местоположение с наименьшим весом в качестве вектора движения.

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

Адаптивный поиск по образцу дороги

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

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

Начните с местоположения поиска в центре (исходное место).
Найдите прогнозируемый вектор движения для блока
Установите размер шага S = max (|X|,|Y|), где (X,Y) — координата прогнозируемого вектора движения.
Поиск точек, распределенных вокруг начала координат с шагом S.
Установите точку с наименьшим весом в качестве начала координат.
Поиск с использованием схемы поиска «маленький ромб» (SDSP) вокруг нового источника.
Повторяйте поиск SDSP до тех пор, пока наименее взвешенная точка не окажется в центре SDSP.

Поиск по шаблону Рода непосредственно помещает поиск в область, где существует высокая вероятность найти хороший совпадающий блок. Основное преимущество ARPS перед DS заключается в том, что если прогнозируемый вектор движения равен (0, 0), он не тратит вычислительное время на выполнение LDSP, а сразу начинает использовать SDSP. Более того, если прогнозируемый вектор движения находится далеко от центра, ARPS снова экономит на вычислениях, напрямую переходя к этой окрестности и используя SDSP, тогда как DS не торопится с выполнением LDSP.

Ссылки

^ Дабов, Костадин; Фой, Алессандро; Катковник Владимир; Егиазарян, Карен (16 июля 2007 г.). «Подавление шума изображения с помощью разреженной совместной фильтрации трехмерной области преобразования». Транзакции IEEE при обработке изображений . 16 (8): 2080–2095. Бибкод : 2007ITIP...16.2080D . CiteSeerX 10.1.1.219.5398 . дои : 10.1109/TIP.2007.901238 . ПМИД 17688213 . S2CID 1475121 .
^ Даниелян, Арам; Катковник Владимир; Егиазарян, Карен (30 июня 2011 г.). «Кадры BM3D и вариационное устранение размытия изображений». Транзакции IEEE при обработке изображений . 21 (4): 1715–28. arXiv : 1106.6180 . Бибкод : 2012ITIP...21.1715D . дои : 10.1109/TIP.2011.2176954 . ПМИД 22128008 . S2CID 11204616 .
^ Дже, Чансу; Пак, Хён Мин (2013). «Оптимизированное иерархическое сопоставление блоков для быстрой и точной регистрации изображений». Обработка сигналов: передача изображений . 28 (7): 779–791. дои : 10.1016/j.image.2013.04.002 .
^ Ли, Жэньсян; Цзэн, Бинг; Лю, Мин (август 1994 г.). «Новый трехэтапный алгоритм поиска для оценки движения блоков». Транзакции IEEE по схемам и системам видеотехнологий . 4 (4): 438–442. дои : 10.1109/76.313138 .
^ Лу, Цзяньхуа; Лю, Мин (апрель 1997 г.). «Простой и эффективный алгоритм поиска для оценки движения с сопоставлением блоков». Транзакции IEEE по схемам и системам видеотехнологий . 7 (2): 429–433. дои : 10.1109/76.564122 .
^ По, Лай-Ман; Ма, Вин-Чунг (июнь 1996 г.). «Новый четырехшаговый алгоритм поиска для быстрой оценки движения блоков». Транзакции IEEE по схемам и системам видеотехнологий . 6 (3): 313–317. дои : 10.1109/76.499840 .
^ Чжу, Шан; Ма, Кай-Куанг (февраль 2000 г.). «Новый алгоритм поиска алмазов для быстрой оценки движения с сопоставлением блоков». Транзакции IEEE при обработке изображений . 9 (12): 287–290. Бибкод : 2000ITIP....9..287Z . дои : 10.1109/83.821744 . ПМИД 18255398 .
^ Не, Яо; Ма, Кай-Куанг (декабрь 2002 г.). «Адаптивный поиск по шаблону Руда для быстрой оценки движения с сопоставлением блоков» (PDF) . Транзакции IEEE при обработке изображений . 11 (12): 1442–1448. Бибкод : 2002ITIP...11.1442N . дои : 10.1109/TIP.2002.806251 . ПМИД 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

[1] Дабов, Костадин; Фой, Алессандро; Катковник Владимир; Егиазарян, Карен (16 июля 2007 г.). «Подавление шума изображения с помощью разреженной совместной фильтрации трехмерной области преобразования». Транзакции IEEE при обработке изображений . 16 (8): 2080–2095. Бибкод : 2007ITIP...16.2080D . CiteSeerX 10.1.1.219.5398 . дои : 10.1109/TIP.2007.901238 . ПМИД 17688213 . S2CID 1475121 .

[2] Даниелян, Арам; Катковник Владимир; Егиазарян, Карен (30 июня 2011 г.). «Кадры BM3D и вариационное устранение размытия изображений». Транзакции IEEE при обработке изображений . 21 (4): 1715–28. arXiv : 1106.6180 . Бибкод : 2012ITIP...21.1715D . дои : 10.1109/TIP.2011.2176954 . ПМИД 22128008 . S2CID 11204616 .

[Je_spic13_ohbm-3] Дже, Чансу; Пак, Хён Мин (2013). «Оптимизированное иерархическое сопоставление блоков для быстрой и точной регистрации изображений». Обработка сигналов: передача изображений . 28 (7): 779–791. дои : 10.1016/j.image.2013.04.002 .

[tss-4] Ли, Жэньсян; Цзэн, Бинг; Лю, Мин (август 1994 г.). «Новый трехэтапный алгоритм поиска для оценки движения блоков». Транзакции IEEE по схемам и системам видеотехнологий . 4 (4): 438–442. дои : 10.1109/76.313138 .

[5] Лу, Цзяньхуа; Лю, Мин (апрель 1997 г.). «Простой и эффективный алгоритм поиска для оценки движения с сопоставлением блоков». Транзакции IEEE по схемам и системам видеотехнологий . 7 (2): 429–433. дои : 10.1109/76.564122 .

[6] По, Лай-Ман; Ма, Вин-Чунг (июнь 1996 г.). «Новый четырехшаговый алгоритм поиска для быстрой оценки движения блоков». Транзакции IEEE по схемам и системам видеотехнологий . 6 (3): 313–317. дои : 10.1109/76.499840 .

[7] Чжу, Шан; Ма, Кай-Куанг (февраль 2000 г.). «Новый алгоритм поиска алмазов для быстрой оценки движения с сопоставлением блоков». Транзакции IEEE при обработке изображений . 9 (12): 287–290. Бибкод : 2000ITIP....9..287Z . дои : 10.1109/83.821744 . ПМИД 18255398 .

[8] Не, Яо; Ма, Кай-Куанг (декабрь 2002 г.). «Адаптивный поиск по шаблону Руда для быстрой оценки движения с сопоставлением блоков» (PDF) . Транзакции IEEE при обработке изображений . 11 (12): 1442–1448. Бибкод : 2002ITIP...11.1442N . дои : 10.1109/TIP.2002.806251 . ПМИД 18249712 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]