Быстрый алгоритм вычисления двумерной корреляции для видеообработки

Авторы: Альтман Е. А., Захаренко Е. И.

Аннотация: Предложен быстрый алгоритм вычисления двумерной корреляции сигналов размерами N×N и (N + M – 1)×(N + M – 1), где N = 2 i , i и M – целые числа. Метод построен на принципе рекурсивного разбиения корреляции на более короткие длины и применении на каждом шаге разбиения наиболее эффективного алгоритма. Вычислительная эффективность различных методов корреляции выявлена в результате представленного в статье исследования. Также авторами разработан еще один быстрый алгоритм вычисления двумерной корреляции, разбивающий ее на 12. Этот метод эффективен при длине сигнала 4×4 и применяется на одном из шагов рекурсивного разбиения предложенного алгоритма. В результате исследования выявлено, что предложенный алгоритм рекурсивного разбиения двумерной корреляции эффективен для коротких сигналов (менее 32×32). Применение этого метода для решения задач видеообработки позволяет снизить вычислительную сложность блочной оценки движения полным перебором вдвое по сравнению с вычислением по прямой формуле для блока размером 8×8 точек и на 3% по сравнению с наиболее быстрыми из известных методов двумерной корреляции.

Ключевые слова: двумерная корреляция, оценка движения, видеокодирование, суммарная квадратичная разность

Библиография статьи: Альтман Е. А. Быстрый алгоритм вычисления двумерной корреляции для видеообработки / Е. А. Альтман, Е. И. Захаренко // Доклады ТУСУР. – 2015. – № 2(36). – С. 119–124.