Идентификация изображений - алгоритм Опции

[ASZ]

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

[SKov]

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

Тут надо уточнить, что значит "произвольной ориентации". Если это "ориентация" в смысле вращения или сдвига на плоскости - это еще ничего. А если в пространстве - это другое. Но вообще посмотрите в сторону метода "характерных точек". Т.е. в образце и в рабочем снимке надо выделить особые ( в некотором смысле ) пикселы или небольшие группы пикселов. Например, резкие перепады яркости. И попытаться сначала рассмотреть варианты наведения соответствия между этими особыми точками в двух картинках, а затем и для остального изображения.
А вообще, картинка 30*30 уж очень маленькая, что там можно распознать - даже не знаю...

[fontp]

Тут надо уточнить, что значит "произвольной ориентации". Если это "ориентация" в смысле вращения или сдвига на плоскости - это еще ничего. А если в пространстве - это другое. Но вообще посмотрите в сторону метода "характерных точек". Т.е. в образце и в рабочем снимке надо выделить особые ( в некотором смысле ) пикселы или небольшие группы пикселов. Например, резкие перепады яркости. И попытаться сначала рассмотреть варианты наведения соответствия между этими особыми точками в двух картинках, а затем и для остального изображения.
А вообще, картинка 30*30 уж очень маленькая, что там можно распознать - даже не знаю...

Да всё зависит от характера преобразования. Признаки используемые для идентификации должны быть инвариантами по отношению к преобразованию.

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

[Lmx2315]

http://forum.algolist.ru/algorithm-image-g...vaniem-bpf.html

Корреляция с использованием БПФ


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