Введение
Система, используемая в приложениях компьютерной графики. Алгоритм сопоставления блоков – это метод поиска соответствующих макроблоков в последовательности цифровых видеокадров для оценки движения. В основе оценки движения лежит предположение, что структуры, соответствующие объектам и фону в кадре видеопоследовательности, перемещаются внутри кадра, формируя соответствующие объекты в последующем кадре. Это позволяет выявить временную избыточность в видеопоследовательности, повышая эффективность межкадрового сжатия видео за счет определения содержимого макроблока относительно содержимого известного макроблока, который минимально отличается. Алгоритм сопоставления блоков предполагает разделение текущего кадра видео на макроблоки и сравнение каждого из них с соответствующим блоком и его соседними блоками в близлежащем кадре видео (часто только с предыдущим). Создается вектор, моделирующий перемещение макроблока из одной позиции в другую. Это перемещение, рассчитанное для всех макроблоков, составляющих кадр, и является оценкой движения в кадре. Область поиска подходящего макроблока определяется параметром поиска, p, где p – количество пикселей по всем четырем сторонам соответствующего макроблока в предыдущем кадре. Параметр поиска является мерой движения: чем больше значение p, тем больше потенциальное движение и вероятность найти хорошее соответствие. Однако полный поиск по всем возможным блокам – вычислительно затратная операция. Типичные входные данные – макроблок размером 16 пикселей и область поиска p = 7 пикселей. Сопоставление блоков и 3D-фильтрация используют этот подход для решения различных задач восстановления изображения, таких как подавление шума и устранение размытости как в статичных изображениях, так и в цифровом видео.
A Block Matching Algorithm is a way of locating matching macroblocks in a sequence of digital video frames for the purposes of motion estimation. The underlying supposition behind motion estimation is that the patterns corresponding to objects and background in a frame of video sequence move within the frame to form corresponding objects on the subsequent frame. This can be used to discover temporal redundancy in the video sequence, increasing the effectiveness of inter frame video compression by defining the contents of a macroblock by reference to the contents of a known macroblock which is minimally different. A block matching algorithm involves dividing the current frame of a video into macroblocks and comparing each of the macroblocks with a corresponding block and its adjacent neighbors in a nearby frame of the video (sometimes just the previous one). A vector is created that models the movement of a macroblock from one location to another. This movement, calculated for all the macroblocks comprising a frame, constitutes the motion estimated in a frame. The search area for a good macroblock match is decided by the ‘search parameter’, p, where p is the number of pixels on all four sides of the corresponding macro block in the previous frame. The search parameter is a measure of motion. The larger the value of p, larger is the potential motion and the possibility for finding a good match. A full search of all potential blocks however is a computationally expensive task. Typical inputs are a macroblock of size 16 pixels and a search area of p = 7 pixels. Block matching and 3D filtering makes use of this approach to solve various image restoration inverse problems such as noise reduction and deblurring in both still images and digital video.
Мотивация
Оценка движения — это процесс определения векторов движения, описывающих преобразование из одного 2D-изображения в другое, как правило, между соседними кадрами видеопоследовательности. Векторы движения могут относиться ко всему изображению (глобальная оценка движения) или к его отдельным частям, таким как прямоугольные блоки, области произвольной формы или даже к отдельным пикселям. Векторы движения могут быть представлены посредством трансляционной модели или множества других моделей, способных аппроксимировать движение реальной видеокамеры, включая вращение и перемещение во всех трех измерениях, а также масштабирование. Применение векторов движения к изображению для предсказания его преобразования в другое изображение, вызванного движением камеры или объекта в кадре, называется компенсацией движения. Комбинация оценки движения и компенсации движения является ключевым элементом сжатия видео, используемым в стандартах MPEG 1, 2 и 4, а также во многих других видеокодеках. Сжатие видео на основе оценки движения позволяет экономить биты за счет передачи закодированных изображений-разностей, которые обладают меньшей энтропией по сравнению с передачей полностью закодированного кадра. Однако оценка движения является наиболее вычислительно сложной и ресурсоемкой операцией во всем процессе сжатия. Поэтому для сжатия видео необходимы быстрые и вычислительно эффективные алгоритмы оценки движения.
Алгоритмы
Алгоритмы сопоставления блоков исследуются с середины 1980-х годов. Было разработано множество алгоритмов, но ниже описаны лишь некоторые из наиболее базовых или часто используемых.
Поиск
Этот алгоритм вычисляет функцию стоимости в каждой возможной позиции в окне поиска. Это обеспечивает наилучшее соответствие макроблока в опорном кадре с блоком в другом кадре. В результате, изображение с компенсацией движения имеет максимально возможное отношение сигнал/шум по сравнению с любым другим алгоритмом сопоставления блоков. Однако, это самый вычислительно сложный алгоритм сопоставления блоков из всех. Увеличение окна поиска требует большего числа вычислений.
Оптимизированное иерархическое сопоставление блоков (OHBM)
Оптимизированный алгоритм иерархического сопоставления блоков (OHBM) ускоряет полный поиск, основанный на оптимизированных пирамидах изображений.