пытаюсь реализовать template matching через FFT 
формула 
position(x,y)= MAX(IFFT(FFT(Img)*FFT(template)))

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

http://en.wikipedia.org/wiki/Phase_correlation
вот тут формула отличается.тоже это самое что normalized cross corelation?

Если я правильно понял вас, то ваша задача - это поиск шаблона в изображении, т.е. поиск такой позиции, которая максимизирует скалярное произведение шаблона на изображение.

Таким образом, мы помещаем шаблон в (0;0), остальное добиваем нулями.

Теперь у нас есть два вектора, и нам надо найти скалярные произведения всех циклических сдвигов первого вектора на второй. Это решается следующим образом: к одному вектору припишем в конец его же, а другой вектор - поревёрсим (изменим порядок на противоположный) и добьём нулями до длины первого вектора, и посчитаем через FFT произведение их как многочленов. Вторая четверть получившихся коэффициентов (c n-го по 2n-1-ый - где n это размер изображения) и будет искомыми скалярными произведениями.

 да.
 
 не очень понял, что вы написали.
 у меня не вектор, а матрица(изображение).
 результат IFFT(FFT(Img)*FFT(template)) тоже матрица и на ней надо найти максимум это и будет положением темплейта.
 я не понимаю как выполнять операцию * при различных размерах матрицы и как производить эту операцию.
 пробовал добивать темплейт нулями и почленно перемножать элементы матрицы(т.е. res(i,j)=a(i,j)*b(i,j)), но получается неправильный ответ.
 возможно надо нормировать или я что то не понимаю.

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

Тогда, если мы сделаем сравнение двух полученных векторов, то это получится ответ, как если бы шаблон приложили в точку (0;0). Если мы сдвинем вектор шаблона на единицу, то это будет соответствовать положению шаблона (0;1), и т.д.

Т.е. разные сдвиги вектора шаблона соответствуют разным позициям шаблона в изображении. (Впрочем, надо не забыть отсеять среди них такие, при которых шаблон вылазит за пределы изображения.)

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

так все таки надо смотреть все возможные комбинации положения шаблона?

вот есть код, но непонятно какой операции соответсвует 
obtain the cross power spectrum
и зачем производится нормировка (возможно только лишь для того чтобы скопировать в изображение)



Добавлено @ 12:45
а понял все таки в блоке /* obtain the cross power spectrum */
считается как в википедии перемножение двух комплексных чисел второе из которых комплексно сопряженное.

Это сообщение отредактировал(а) mrgloom - 28.11.2011, 12:46

да и находит таким методом правильно только координаты почему то получаются
(width-maxloc.x,height-maxloc.y) , а не (maxloc.x,maxloc.y) .
+ еще смущает что 1D массивы не проссаживается ли производительность против 2D массива? (в плане считать фурье туда сюда)

Сказать честно, я не совсем понимаю, что есть DFT от матрицы. (Ведь DFT от массива имеет чёткую интерпретацию как значения многочлена с указанными коэффициентами в точках-комплексных корнях из единицы. Как это перенести на матрицы, я не понимаю.)

А решение со сведением к одномерному случаю кажется достаточно прямолинейным.



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



Повторюсь, я не понимаю, что такое DFT от двумерного массива. Но в моём решении фурье запускается один раз, никаких "туда-сюда" нет. И то, что мы перемножаем весь массив целиком, важно концептуально.

попытался сравнить код через старый opencv и код через FFTW+opencv
похоже что оба работают правильно, только постоянно какие то непонятные доп. смещения по краям(в коде они закомментированы прибавляются или вычитаются от конечной точки), т.е. я так понимаю в зависимости от того в какой квадрант попадает пик корреляции зависит какая будет формула расчета конечного результата, причем для 2-х методов формулы вроде бы будут разные.
эти коды я использую не для поиска темплейта, а для сшивки пары изображений.изображения одного размера.

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

использовал версию opencv 2.4.3 она работает на некоторых изображениях, а например на изображении где 20% перекрытия не всегда выдает не тот пик,
что то типа (w,h)-peak или -peak.
не пойму с чем это всё связано, какие то краевые проблемы или связанные с цикличностью?
когда изображения разного размера я добавляю нулями, но в зависимости от размера (см. в коде) получаются разные результаты.

вопрос можно ли дополнять нулями? есть ли разница сколько добавлять или куда помещать изображение? (я помещал в левый верхний угол, а остальное заполнял нулями).
+ еще в самом коде phaseCorrelate непонятный код по смещению.