23. Методы подоптимального поиска векторов движения

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

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

На сегодняшний день известно множество алгоритмов подоптимального поиска векторов движения. Рассмотрим наиболее известные среди них.

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

Поиск с разбавленным расстоянием: Из опыта известно, что быстро перемещающиеся объекты выглядят смазанными при воспроизведении на экране, даже если имеют четкие очертания в каждом кадре. В результате можно построить такой алгоритм поиска векторов. Для близких блоков от блока В берутся все ближайшие блоки-кандидаты, а при увеличении расстояния, блоки берутся с большим шагом, а значит и их число будет меньше (рис. 3).

Рис. 3.

Локализованный поиск: Этот метод основан на гипотезе, что если хорошее совпадение найдено, что еще лучшее, скорее всего, находится где-то рядом. Тогда алгоритм поиска получается следующий. Сначала по разреженному расстоянию находится лучший блок, а затем, относительно него, с более точным расстоянием находится еще более подходящий.

Двумерный логарифмический поиск: Допустим имеется квадратная область (2d+1)(2d+1). В этой области берется пять точек с шагом  с координатами (a,b) (a-s,b) (a+s,b) (a,b-s) (a,b+s), т.е. в форме знака +. Затем выбирается наилучший блок из этих 5 и если лучший в точке (a,b), то s делится на 2 и поиск продолжается. В противном случае алгоритм перемещается в новую точку с тем же шагом. На последнем шаге работы этого алгоритма s=1 и тогда берутся все 9 точек и для них находится лучший блок.

Поиск за 3 шага: Данный алгоритм похож на предыдущий, но в отличие от него берет не 5, а 9 точек с определенным шагом s. Затем поиск переходит в новую точку (или остается в прежней, если этот блок лучший) и повторяет поиск при шаге s=s/2. И так пока s не дойдет до 1 – это будет последний шаг. Если изначально s=4, то алгоритм завершит свою работу за 3 шага.

Ортогональный поиск: Идея заключается в последовательном поиске лучшего блока сначала по горизонтали из 3-х возможных (центральный и два с боков). Затем берется самый подходящий из них и после этого просматриваются блоки по вертикали (также 3: один выбранный и по одному сверху и снизу). Лучший блок становится центром для последующего поиска.

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

Перекрестный поиск: Сначала находятся лучшие блоки расположенные с разными шагами в форме знака х, а на последнем этапе, при s=1, форма поиска +.

Методы иерархического поиска: Иерархический поиск начинает поиск векторов движения с больших блоков. После этого большой блок разбивается на более мелкие, обычно на 4 или 9 и для этих меньших блоков векторы движения уточняются. Данный метод дает более лучшие результаты, чем рассмотренные выше, но обладает и большей вычислительной сложностью. На практике объем вычислений обычно сокращают следующими подходами:

1. Пока блок большой выбирать не лучшее приближение, а более-менее подходящее. Все равно этот вектор движения потом будет уточняться.

2. При исследовании больших блоков можно пропустить некоторые пикселы, например, оставить только четверть.