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

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

Это подсказывает возможный путь для отбрасывания части информации. Можно требовать хорошего совпадения для медленно перемещающихся объектов, и приблизительного совпадения для тех, что перемещаются быстро. В итоге получаем алгоритм, который оценивает для каждого блока В все ближайшие к нему блоки-кандидаты, а для более удаленных блоков он рассматривает все меньшую часть блоков. Такой метод мог бы работать для параметров максимального смещения dx = dy — 6. Общее число оцениваемых блоков сокращается с (2dx + 1)(2dy + 1) = 13 х 13 = 169 до всего 65, то есть, до 39%!

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

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

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

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

На первом проходе сканируются черные блоки (четверть всех блоков на рисунке). Векторы перемещения для этих блоков вычисляются некоторым другим методом. На втором проходе оцениваются серые блоки (их тоже 25% от общего числа), с помощью векторов перемещения их угловых соседей. Наконец, белые блоки (их 50%) изучаются на третьем проходе. Для вычисления их векторов перемещения используются четыре соседа, прилегающие к их сторонам. Если векторы перемещений соседних блоков сильно различаются, то их не стоит использовать, а вектор перемещения блока В придется вычислять другим методом.