Корреляция с использованием БПФ
Rodya
Новичок
Регистрация: 15.09.2009
Сообщений: 3
Всем огромное спасибо! Все заработало!!!
Если кому интересно, то конечный алгоритм получился такой:
Предположим, что есть картинка разрешением A x B и фрагмент разрешением C x D. Надо найти положение фрагмента на картинке.
Пользуемся следующей формулой (корреляционная функция):
K(ax, ay) = F-1{Sк(wx, wy) X Sф*(wx, wy)} = F-1{G(wx, wy)}
Другими словами хотим получить функцию K(ax, ay), координаты максимума которой соответствуют положению фрагмента на картинке.
Здесь F-1 - символ обратного преобразования Фурье; Sк и Sф - двумерные спектры картинки и фрагмента соответственно; S* - комплексное сопряжение; Sк X Sф* - поэлементное умножение.
Для простоты предположим, что оба изображения заданы двумерными double массивами, каждый элемент которых соответствует яркости соответствующего пикселя.
Теперь по порядку.
1. Сначала надо сместить сигнал фрагмента. Это значит посчитать среднее по всем элементам массива фрагмента, а затем вычесть его из каждого из этих элементов. Этим мы добьемся того, что сумма всех элементов будет равна нулю. Если этого не сделать, то максимум корреляционной функции будет указывать не на положение фрагменты на картинке, а на наиболее яркие области на ней.
2. Затем необходимо создать два новых массива размерностью A + C - 1 на B + D - 1 (см. размеры исходных картинок). В них мы начиная с левого верхнего пикселя копируем значения из картинки и из фрагмента (картинку в первый массив, а фрагмент во второй). Все остальные элементы делаем равными нулю. Другими словами у нас должно получиться два изображения, в левых верхних углах которых будут картинка (на первом изображении) и фрагмент (на втором), все остальное на них будет черным. Дальше работать будем только с этими массивами.
3. Затем ищем спектры. Их получаем прямыми преобразованиями Фурье от имеющихся у нас функций (или массивов). после этого шага будем иметь два двумерных массива комплексных чисел размерностью A + C - 1 на B + D - 1.
4. Теперь берем спектр фрагмента и каждому элементу присваиваем его же комплексно сопряженное. Т.е. у каждого из элементов меняем знак мнимой части на противоположный.
5. Дальше считаем взаимный спектр, который получаем поэлементным перемножением двух, уже имеющихся у нас, спектров. Т.е. считаем новый массив по формуле G(i, j) = Sк(i, j) * Sф*(i, j).
6. Теперь очталось сделать обратное преобразование Фурье от полученного взаимного спектра и найти максимум получившейся функции. Его координаты и будут соответствовать положению фрагмента на картинке.
Можно еще смещать сигнал не только фрагмента, но и самой картики, но у меня и так нормально работает.
Куча информации взял отсюда:
http://psi-logic.shadanakar.org/fft/fft.htm - это про быстрые преобразования Фурье.
А так же из книжки товарищей Р. Гонсалеса и Р. Вудса "Цифровая обработка изображений".
Идентификация изображений - алгоритм
Jan 6 2011, 05:50
Смотря в каком отображении производить свертку... 
