Знаю тема крайне избитая, но готового алгоритма так нигде найти и не удалось.

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

Если есть люди разбирающиеся, подскажите все ли я правильно понял:
1. Для нахождения фрагмента на картинке считаем корреляционную функцию K=f(ax, ay), где ax и ay - смещения фрагмента относительно левого верхнего угла картинки. Максимум этой функции будет соответствовать положению фрагмента на картинке.
2. В случае использования преобразований Фурье корреляционная функция считается так:

где S1 и S2 - двумерные спектры картинки и фрагмента соответственно, * - комплексное сопряжение (т.е. у каждого значения в S2 знак мнимой части меняем на противоположный), F-1 - обратное преобразование Фурье, S1(wx, wy)S2*(wx, wy) - поэлементное перемножение S1 на S2*.
3. S1 и S2 получаем прямым преобразованием Фурье картинки и фрагмента соответственно.

В чем я не уверен, это следующее:
Правильно ли записана формуля для корреляционной функции? Я ее взял по аналогии с одномерным случаем (K(ax) = F-1{S1(wx) S2*(wx)}).
Правильно ли я понял на счет комплексного сопряжения? Т.е., если S2 - массив комплексных чисел, то надо просто у каждого элемента этого массива знак мнимой части поменять на противоположный.
Правильно ли, что G() = S1()S2*() - это поэлементное умножение, т.е. G[i] = S1[i] * S2*[i]? И тутже еще один вопрос: длина S2 меньше длины S1 (т.к. размеры фрагмента меньше размеров картинки), как их перемножать друг на друга?
И последнее: действительно ли S1 и S2 получаем прямым преобразованием Фурье исходных картинок?

Если же все правильно подскажите как потестить правильность преобразований Фурье. Просто есть еще подозрение, что неправильно работают преобразования.

P.S. Имеется ввиду конечно двумерные преобразования Фурье.

есть простой способ локализовать ошибку: посчитать корреляцию по-простому и сравнить с результатом подсчёта с помощью Фурье, тогда станет ясно, снаружи или внутри ошибка

кроме того, можно взять очень маленькие изображения (например, 1x1 и 2x1) и попробовать на них - тогда можно много чего вручную проверить

Это сообщение отредактировал(а) maxim1000 - 15.9.2009, 08:02

Я знаком только с одномерным ПФ, поэтому могу сказать только по поводу следующего:

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

Собственно так я и сделал. Результаты само собой разные (были бы одинаковые не писал бы).



Так то оно так, но хотелось бы во-первых сначала понять правильный ли вообще подход, и во-вторых понимать из какой картинки какой спектр должен получиться и наоборот. Тогда и тестить преобразования.



Тут не сравнение двух картинок, а поиск подкартинки в картинке. Т.е. пусть у нас есть картинка размером, например, 64x64; мы из нее вырезаем фрагмент с координатами, например, x = 5, y = 10, width = 8, height = 12 и пытаемся его найти на исходной картинке. Результатом действия алгоритма должны быть две координаты: x = 5, y = 10. Как-то так.

в описании ничего неправильного я не заметил, однако вполне возможно, что где-то закралась какая-нибудь чисто техническая ошибка

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