Добро пожаловать, гость
:: алгоритмы  и методы :: :: олимпиадные задачи :: :: связь :: :: о сайте :: :: форум ::

Форум работает в режиме архива, только для чтения и поиска.
Архив 2004 Архив 2007 Архив 2013

 
 
Опции темы Поиск в этой теме Опции просмотра
  #1  
Старый 15.09.2009, 08:52
Новичок

Отправить личное сообщение для Rodya Посмотреть профиль Найти все сообщения от Rodya
 
Регистрация: 15.09.2009
Сообщений: 3

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

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

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

где 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. Имеется ввиду конечно двумерные преобразования Фурье.
  #2  
Старый 15.09.2009, 09:57
MBo MBo вне форума
Местный

Отправить личное сообщение для MBo Посмотреть профиль Найти все сообщения от MBo
 
Регистрация: 21.09.2006
Адрес: Новосибирск
Сообщений: 1,374

>Правильно ли записана формуля для корреляционной функции?
>Правильно ли я понял на счет комплексного сопряжения?
да. да.


>длина S2 меньше длины S1 (т.к. размеры фрагмента меньше размеров картинки), как их перемножать друг на друга?
дополнять нулями

>как потестить правильность преобразований Фурье
если на глазок - посмотреть картинки преобразования для известных функций - синусы, прямоугольник

Двумерное Фурье и одномерные конволюция и корреляция с использованием FFT есть в книге Numerical Recipes (12 и 13 главы)

Кроме того, можно выполнить корреляцию медленную, без Фурье, по определению, и сравнить результаты.
P.S. При выполнении корреляции может понадобиться смещать сигналы, если они однополярные (для изображений это как раз так), чтобы светлые поля не зашкаливали.
  #3  
Старый 15.09.2009, 21:06
^ ^

 
Сообщений: n/a

Hi!

Вы на чем это все программируете? Совет: "переходите на наливки" (c) -- то бишь на Matlab. По крайней мере, Вы автоматически получите разделение школярских (уже давно решенных) проблем типа двумерного преобразования Фурье и действительно творческих (phase correlation image registration или motion estimation).

Много примеров готового кода можно почерпнуть на китайском сайте http://en.pudn.com/
Например
http://en.pudn.com/downloads105/sour...434579_en.html
кория:
http://www.mediafire.com/?sharekey=5...75f6 e8ebb871

Ищите: 'phase correlation' 'motion estimation' 'image registration' и т.п.

Удачи!
  #4  
Старый 25.09.2009, 14:16
Новичок

Отправить личное сообщение для Rodya Посмотреть профиль Найти все сообщения от Rodya
 
Регистрация: 15.09.2009
Сообщений: 3

Сообщение от MBo Посмотреть сообщение
P.S. При выполнении корреляции может понадобиться смещать сигналы, если они однополярные (для изображений это как раз так), чтобы светлые поля не зашкаливали.
А можно поподробнее? как раз дошел до этой проблеммы.
Т.е. если на картинке есть какие-то более яркие чем все остальное области, то максимум корреляции будет именно там.
Что означает смещать сигналы? Я попробовал так: у 8-битных картинок из яркости каждого пиксела вычел 128. Стало лучше, но все равно часто сваливается в яркую область.
  #5  
Старый 28.09.2009, 15:47
Новичок

Отправить личное сообщение для Rodya Посмотреть профиль Найти все сообщения от 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 - это про быстрые преобразования Фурье.
А так же из книжки товарищей Р. Гонсалеса и Р. Вудса "Цифровая обработка изображений".
 


Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск
Опции просмотра


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Таблица умножения дробей с использованием класса Alexander_ua Задачи 9 19.02.2010 02:20
Автоматизированное составление расписаний с использованием генетических алгоритмов. GreatWizard Математические алгоритмы 1 28.04.2008 14:41
максимальный поток в графе с использованием параллельных вычислений kernel1987 Графы 0 19.04.2008 21:22
проблема с использованием русского алфавита в с++ elle Реализация, исходники, языки 9 17.03.2008 21:19