Теперь надо придумать...

[thesz]

...как вычислять максимальную корреляцию с субпиксельной точностью возде максимума корреляции, вычисленной с помощью DFT.

И надо прочитать про FFTW для уяснения работы алгоритма DFT не по основанию 2.

Comments

слегка не в тему

[monocalibro]

"...как вычислять максимальную корреляцию" сплайны Вам в руки.
Вы наверняка знаете, но тем не менее - в библиотеках Clean есть линейная алгебра на основе "функционализированного" BLAS. Не то чтобы вполне декларативно, но работает.
http://www.cs.ru.nl/~clean/Download/Download_Libraries/clas/clas.html

[monocalibro]

а Фортран 90 все равно лучше. И FFT там не проблема

[potan]

Перечитал описание fft. Даже на Haskell реализовал :-).
Но в что такое основание? Алгоритм требует что бы длинна списка была степенью двойки - это имеется ввиду?

[thesz]

Да.

Однако, такой же эффект может быть использован и для, например, 2^n*3^m*5^k... Тогда получается скорость работы O(n log n).

OpenCV это умеет. FFTW это умеет.

Однако, FFTW умеет работать с простым числом отсчетов (которое ни на что, кроме себя и 1, не делится) и все равно получать производительность O(n log n).

Очень интересно, как это у них получается. ;)

[potan]

Может они дополняют массив чем-нибудь до ближайшей степени?
Кстати, интересно для какого основания степени скорость будет максимальна?

[thesz]

Ты прав. Они пользуются Bluestein algorithm, а он использует свертку, вычисляемую с помощью FFT с основанием, допустим, 2^n и заполняет ненужное нулями.

Как все запущено! ;) Я думал, там хитрая теория чисел используется... ;)