Автокорреляция

Что за 3 вариации?

См. http://en.wikipedia.org/wiki/Autocorrelation#Efficient_computation . А быстрое Фурье преобразование умеют вычислять многие (например, fftw3, GSL и др.).

Что за 3 вариации?

Сдвиги по 2 осям и поворот.

См. http://en.wikipedia.org/wiki/Autocorrelation#Efficient_computation . А быстрое Фурье преобразование умеют вычислять многие (например, fftw3, GSL и др.).

Это для одномерного случая. Не думаю, что так уж просто будет приспособить это для двумерного.

См. http://en.wikipedia.org/wiki/Autocorrelation#Efficient_computation . А быстрое Фурье преобразование умеют вычислять многие (например, fftw3, GSL и др.).

Это для одномерного случая. Не думаю, что так уж просто будет приспособить это для двумерного.

А в чем сложность? Сдвиги по каждой из осей независимы. Можете сразу двумерную корреляцию считать. Двумерное (и многомерное) Фурье — стандартная опция всех мат. пакетов/библиотек.

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

А в чем сложность?

Например, я не уверен, как будет выглядеть теорема Винера-Хинчина в этом случае.

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

Ну и это тоже. Хотя можно взять любой готовый алгоритм поворота изображения со сглаживанием. Всё равно делов навалом. Может быть я так и поступлю, но хотелось бы готовую библиотеку.

Для двумерной автокорреляции подойдёт двумерный фильтр, их быстрое вычисление основано на двумерном быстром преобразовании Фурье. В качестве ядра (импульсной функции) фильтра надо взять то же самое изображение, только с обратным порядком пикселей (то есть отражённое слева направо и сверху вниз).

Поворот (для третьего параметра) придётся приделывать самостоятельно, но библиотечные функции есть.

Интересует библиотека, способная быстро вычислять функцию автокорреляции двумерных массивов

Image Processing Toolbox: xcorr2 - вычисление коэффициентов корреляции между двумя матрицами,

fftn - n–мерное БПФ,
convn - свертка N–мерных сигналов,
radon - преобразование Радона (для инвариантности к повороту, ещё иногда применяют преобразование Фурье-Меллина).

быстро вычислять

Digital Signal Processors + FFT Acceleration.

А можно поинтересоваться, какую характеристику позволяет узнать АКФ по повороту? Спектральной мощности по x и y недостаточно?

Грубо говоря, мне нужно отслеживать перемещения объектов. Если на изображеии есть объект, который сместился на X, Y и повернулся вокруг какой-либо оси на \alpha, функция автокорелляции будет иметь локальный максимум в точке (X, Y, \alpha).

Для этого лучше смотри преобразования, инвариантные к повороту.

И автокорреляция тут ни при чём, кстати, это уже взаимная корреляция.

Можно глянуть, как реализовано в gwyddion.

Неспешно пишу такую штуку. Без математики, чисто придуманные мной алгоритмы. Правда там еще учитывается увеличение-уменьшение объекта.

Вспомнилась OpenCV — оно не может?