Кросс корреляция + FFT для изображений
1) Быстрое преобразование Фурье(FFT), насколько я понял, должно применятся к изображениям ,но непонятно каким образом. Т. е. на входе имеем изображение а вот что получаем на выходе не понятно.
2) Как считается кросс корреляция. Я нашел формулу на википедии но не знаю какие обозначения за что отвечают.
Не могли бы вы объяснить на пальцах суть метода или посоветовать какой нибудь русскоязычный ресурс с доступным описанием этих алгоритмов?
1) Быстрое преобразование Фурье(FFT), насколько я понял, должно применятся к изображениям ,но непонятно каким образом. Т. е. на входе имеем изображение а вот что получаем на выходе не понятно.
Быстрое преобразование Фурье (БПФ) - это алгоритм, с помощью которого быстро вычисляется дискретное преобразование фурье.
Обычное преобразование фурье применяется для непрерывных функций, но в компьютере обрабатывать непрерывные функции затруднительно. Дискретное преобразование фурье - модификация преобразования для функций, заданных только в некоторых точках.
Чтобы понять, что такое преобразование Фурье, полезно сначала посмотреть (например в википедии) про ряды Фурье.
Изображение рассматривается как двумерная функция, заданная в точках прямоугольной сетки. В целях упрощения будем рассматривать только градации серого. Это значит, что значение в каждой ячейке сетки - одно число.
После двумерного преобразования Фурье эта функция будет представлена как сумма двумерных синусоид с некоторыми коэффициентами.
Каждая синусоида характеризуется периодом по Х и периодом по У. Образом Фурье будет опять двумерная функция, значения в которой - коэффициенты для соответствующих синусоид. Ее удобно тоже показывать как изображение.
В общем это не так просто. Чтобы хорошо все понять нужно будет долго читать учебники по матану.
2) Как считается кросс корреляция. Я нашел формулу на википедии но не знаю какие обозначения за что отвечают.
Я не знаю, что такое кросс корреляция. Искать формулу мне лениво. Но просто использовать формулу, не понимая, что она означает, лучше даже не пытаться.
Подозреваю, что там нужно будет освоить еще некоторое количество материала. Например, почти наверняка нужно будет знать, что такое свертка.
Может не стоит вообще браться за такое дело?
Не если взялся надо разобрать.
Я в принципе понимаю кросс корреляцию она показывает выраженность одного сигнала в другом.
Дискретной кросс-корреляций функций f(t) и g(t), определенных на множестве целых чисел Z, называется следующая операция:
corr(f,g)[n]=sum(m=-inf,+inf)f*[m]g[n+m];
Кросс-корреляция чаще всего применяется в обработке сигналов, при этом f считается образцом, а g – сигналом, содержащим образец. Результат – это вектор чисел, показывающих, насколько сильно образец выражен в сигнале.
Описание взято отсюда:http://alglib.sources.ru/fasttransforms/crosscorrelation.php
Не понятно что в случае изображения является сигналом(яркость каждого пиксела?) и в каких пределах изменяются m и n. На входе я так понял должна получится некоторая последовательность, в которой мы ищем глобальный экстремум(возможно максимум, но могу ошибаться) в этом месте и будет максимально совпадение с образцом.
Не понятно что в случае изображения является сигналом(яркость каждого пиксела?) и в каких пределах изменяются m и n. На входе я так понял должна получится некоторая последовательность, в которой мы ищем глобальный экстремум(возможно максимум, но могу ошибаться) в этом месте и будет максимально совпадение с образцом.
Сигалом является изображение. Да, яркость каждого пиксела.
Сигнал является двумерным. Это значит, что все формулы должны быть взяты для двумерного случая. Появится дополнительное суммирование по второй координате.
Кросс-корреляция по сути является обычной сверткой для дискретного случая.
Теперь про то, причем тут преобразование Фурье.
Пусть f и g - некие функции. Есть теорема:
Фурье( свертка(f, g) ) = Фурье(f) * Фурье(g)
Это значит, что для вычисления свертки требуется:
1) посчитать образы Фурье от f и g
2) перемножить их (поточечно)
3) провести обратное преобразование Фурье.
То, что в результате получится, и будет сверткой (кросс-корреляцией).
Случай двумерный, так что ее тоже можно показать как изображение.
f - это исходное изображение, g - фильтр.
Если в качестве g взять, например, функцию Гаусса (естественно, двумерную), то на выходе получится то же изображение, но слегка размазанное (как раз это, кстати, называется "Гауссово размытие").
Если в качестве g использовать фильтр Габора (http://ru.wikipedia.org/wiki/%D0%A4%D0%B0%D0%B9%D0%BB:Gabor_filter.png), то получим изображение, в котором яркими являются те точки, в которых исходное изображение имеет ту же степень полосатости в том же направлении. Это, в некотором роде, и есть поиск паттернов.
Я бы посоветовал не гуглить отдельно каждый непонятный алгоритм, а пойти издалека и найти какой-нибудь хороший учебник, где будет написано про преобразование Фурье и свертки.
P.S Если таки будете что-то кодить, то для преобразование Фурье мне больше всего нравится библиотека fftw.
Требуется: посчитать произведение 128 * 32
1) считаем "образы" чисел: log(128)=7 и log(32)=5
2) складываем: 7 + 5 = 12 - операция умножения заменилась на более простую операцию сложения
3) обратное преобразование: 2^12 = 4096
Ответ: 128 * 32 = 4096
В принципе, да. Только нужно учитывать, что для масштабирования и поворота этот метод (по крайней мере в таком виде) работать не будет.
Небольшая демонстрация фильтров габора - из картинки вычленяются куски с запрошенной полосатостью:
http://190vision.blogspot.com/2009/02/orientation-and-gabor-filter.html
Если вам интересно то вот:http://www.liralab.it/teaching/sina/slides-current/fourier-mellin-paper.pdf правда на английском
и вот на русском общие сведения по методам связанными с преобразованиями изображений в том числе и с Фурье:http://www.sati.archaeology.nsc.ru/gr/texts/image_process/index.html#simple_methods_xy_rotatemax