Распознавание точечных паттернов

Имея два разных размера наборов точек (2D для простоты), распределенных по двум разным размерам квадратов, возникает вопрос:

1- как найти любое появление маленького через большое?
2- Есть идеи о том, как ранжировать события, как показано на следующем рисунке?

Вот простая демонстрация вопроса и желаемого решения:

Обновление 1: на
следующем рисунке показан более реалистичный взгляд на исследуемую проблему.

Что касается комментариев, применяются следующие свойства:

• точное местоположение точек доступны
• точный размер очков доступны
  • размер может быть нулевым (~ 1) = только точка
• все точки черные на белом фоне
• отсутствует эффект серой шкалы / сглаживания

Вот моя реализация метода, представленная endolithнекоторыми небольшими изменениями (я повернул цель вместо источника, так как он меньше и быстрее вращается). Я принял ответ Эндолита, потому что думал об этом раньше. О RANSAC у меня пока нет опыта. Кроме того, реализация RANSAC требует много кода.

Это не лучшее решение, но это решение. Я хотел бы узнать о лучших методах:

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

• Регистрация изображения с использованием нормализованной взаимной корреляции
• Сопоставление и свертка на основе шаблонов

Вы можете ускорить взаимную корреляцию, используя метод БПФ, но если вы просто сопоставляете небольшое исходное изображение с большим целевым изображением, метод умножения-и-сложения методом грубой силы иногда (не обычно) быстрее.

Источник:

Цель:

Кросс-корреляция:

Два ярких пятна - это места, которые совпадают.

Но вы делаете , имеют параметр вращения в вашем примере изображения, так что не будет работать сам по себе. Если разрешено только вращение, но не масштабирование, тогда все еще возможно использовать взаимную корреляцию, но вам необходимо взаимно коррелировать, вращать источник, взаимно коррелировать его со всем целевым изображением, вращать его снова и т. Д. Для все вращения.

Обратите внимание, что это не обязательно когда-либо найти изображение. Если исходное изображение является случайным шумом, а цель - случайным шумом, вы не найдете его, если не будете искать точно под прямым углом. В нормальных ситуациях он, вероятно, найдет его, но это зависит от свойств изображения и углов, в которых вы ведете поиск.

Эта страница показывает пример того, как это будет сделано, но не дает алгоритм.

Любое смещение, где сумма выше некоторого порога, является совпадением. Вы можете рассчитать качество совпадения, сопоставив исходное изображение с самим собой и разделив все свои суммы на это число. Идеальное совпадение будет 1,0.

Это будет очень сложным в вычислительном отношении, хотя, и, вероятно, есть лучшие методы для сопоставления шаблонов точек (о которых я хотел бы знать).

Пример быстрого Python с использованием градаций серого и метода FFT:

from __future__ import division
from pylab import *
import Image
import ImageOps

source_file = 'dots source.png'
target_file = 'dots target.png'

# Load file as grayscale with white dots
target = asarray(ImageOps.invert(Image.open(target_file).convert('L')))

close('all')
figure()
imshow(target)
gray()
show()

source_Image = ImageOps.invert(Image.open(source_file).convert('L'))

for angle in (0, 180):
    source = asarray(source_Image.rotate(angle, expand = True))
    best_match = max(fftconvolve(source[::-1,::-1], source).flat)

    # Cross-correlation using FFT
    d = fftconvolve(source[::-1,::-1], target, mode='same')

    figure()
    imshow(source)


    # This only finds a single peak.  Use something that finds multiple peaks instead:
    peak_x, peak_y = unravel_index(argmax(d),shape(d))

    figure()    
    plot(peak_y, peak_x,'ro')
    imshow(d)

    # Keep track of all these matches:
    print angle, peak_x, peak_y, d[peak_x,peak_y] / best_match

1-цветные растровые изображения

Для одноцветных растровых изображений это будет намного быстрее. Кросс-корреляция становится:

• Поместите исходное изображение поверх целевого изображения
  • побитовое И все перекрывающиеся пиксели (намного быстрее, чем умножение)
  • суммировать все 1 в перекрытой области
• Переместить исходное изображение на 1 пиксель
  • побитовое И все перекрывающиеся пиксели
  • суммировать все 1
• ...

Пороговое преобразование изображения в градациях серого в двоичный файл и последующее выполнение этого может быть достаточно хорошим.

Облако точек

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

С точки зрения компьютерного зрения: основной проблемой является оценка гомографии между вашим целевым набором точек и подмножеством точек в большом наборе. В вашем случае, только с ротацией, это будет аффинная гомография. Вы должны посмотреть на метод RANSAC . Он предназначен для поиска совпадения в наборе со многими выбросами. Итак, вы вооружены двумя важными ключевыми словами: омография и RANSAC .

OpenCV предлагает инструменты для вычисления этих решений, но вы также можете использовать MATLAB. Вот пример RANSAC с использованием OpenCV . И еще одна полная реализация .

Типичным приложением может быть нахождение обложки книги на картинке. У вас есть фотография обложки книги и фотография книги на столе. Подход заключается не в сопоставлении шаблонов, а в нахождении заметных углов в каждом изображении и сравнении этих наборов точек. Ваша проблема выглядит как вторая половина этого процесса - поиск точки, установленной в большом облаке. RANSAC был разработан, чтобы сделать это надежно.

Я предполагаю, что методы взаимной корреляции могут также работать для Вас, так как данные настолько чисты. Проблема в том, что вы добавляете еще одну степень свободы с вращением, и метод становится очень медленным.

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

PS Идея в том, что вместо работы с изображением вы можете работать с координатами ненулевых пикселей. Общий поиск ближайшего соседа. Вы должны выполнить исчерпывающий поиск всего пространства поиска, как поступательного, так и вращательного, используя некоторую сетку, то есть некоторый шаг по координате и углу поворота. Для каждой координаты / угла вы берете подмножество пикселей в окне с центром, координата которого повернута на этот угол, берете их координаты (относительно центра) и сравниваете их с координатами пикселя искомого шаблона. Вы должны убедиться, что в обоих наборах баллы отсортированы одинаково. Вы найдете координаты с минимальной разностью (максимальная ковариация). После этого грубого совпадения вы можете найти точное совпадение с помощью некоторого метода оптимизации. Извините, я не могу передать это более просто, чем это.

Я очень удивлен, почему никто не упомянул методы семейства обобщенных преобразований Хафа . Они напрямую решают эту конкретную проблему.

Вот что я предлагаю:

1. Возьмите шаблон и создайте R-таблицу , индексируя края шаблона. Края, которые я выбрал, следующие:

2. Используйте стандартную реализацию OpenCV обобщенного преобразования Хафа для получения:

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

Более того, обработка поворотов очень естественна для схем Хафа. Фактически, для двумерного случая это просто добавленное измерение в аккумуляторе. На случай, если вы захотите подробно рассказать о том, как сделать его действительно эффективным, М. Ульрих объясняет множество хитростей в своей статье .

Это хорошее приложение для геометрического хеширования. страница википедии с геометрическим хешированием