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

46

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

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

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


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

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

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

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

разработчик
источник
1
Вы ищете решение для сопоставления таких точек или для более сложных изображений? Сколько точек может быть на картинках?
Да, это очень важно. Если это просто точки известного размера, вы можете оптимизировать для этого. Если у вас есть фидуциарные маркеры, вы можете оптимизировать их. Будьте более конкретны о том, что вы используете это для
Эндолит
Для задачи, над которой я работаю, есть наборы точек (каждая из нескольких сотен точек), в которых ищется другой набор точек меньшего размера (скажем, <100). Приведенная выше демонстрация настолько проста и понятна, однако реальная проблема выглядит сложной. Существует также интерес к поиску совпадений, ранжированных на основе нежелательных баллов, которые существуют среди них.
Разработчик
1
Будут ли черно-белые точки? Вы получаете их с камеры / сканера / что-то еще? Двоичные значения могут сделать вычисления намного быстрее.
Эндолит
У вас есть проблемы с нахождением центров точек или просто с обнаружением миниатюры на большой картине, зная положение точек?

Ответы:

17

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

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

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

Источник:

введите описание изображения здесь

Цель:

введите описание изображения здесь

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

введите описание изображения здесь

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

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

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

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

Любое смещение, где сумма выше некоторого порога, является совпадением. Вы можете рассчитать качество совпадения, сопоставив исходное изображение с самим собой и разделив все свои суммы на это число. Идеальное совпадение будет 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
Это верно, для исследуемой проблемы нет масштабирования, но может произойти вращение. Спасибо за ссылку и ответ.
Разработчик
@ Разработчик: Ну, тогда это будет работать, но, возможно, есть лучший способ. Если это просто двоичное изображение, кросс-корреляция будет намного быстрее, хотя. (Есть ли такая вещь, как БПФ для двоичного сигнала?) Поворот произвольный? Вам придется поэкспериментировать с набором значений поворота, которые дают хорошие результаты, например, увеличение на 1 градус или 5 градусов и т. Д.
эндолит
1
Да, это бинарная проблема. Я также помню откуда-то, что был такой метод, чтобы найти более короткий сигнал, модулированный по более длинному сигналу с разными амплитудами. Я помню, независимо от сложности, он работал очень хорошо, показывая точки выбора в качестве начальных точек событий. Поскольку проблема в 2D, мне не ясно, как использовать подобную концепцию. Это также сложно из-за вращения, которое применяется в 2D.
Разработчик
1
Да, это становится невозможным при добавлении свободы вращения. Вот почему такие методы, как RANSAC, были разработаны. Я думаю, что это помогает думать вне коробки DSP на этом.
Мэтт М.
@ MattM: это работает, это просто медленно. :)
эндолит
22

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

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

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

введите описание изображения здесь

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

Мэтт М.
источник
Я добавил немного больше деталей в вопрос. Я глубоко проверю ваши ссылки, однако быстрое впечатление, что это разные концепции!
Разработчик
1
Похоже, это действительно проблема RANSAC / гомографии :)
Мэтт М.
Что ж. Это была новая концепция для меня. Я попробую это как можно скорее. Если я столкнусь с трудностями, я поделюсь с вами, замечательными и поддерживающими членами сообщества.
Разработчик
Простой вопрос: возможно ли / возможно ли применить метод RANSAC / гомографии к трехмерному облаку точек?
Разработчик
Это не правильное решение. К сожалению, этот вопрос не содержит информации об интенсивности, и поэтому простые схемы дескрипторов не будут работать. Проблема скорее геометрическая, чем эта.
Толга
3

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

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

mirror2image
источник
1
Не могли бы вы привести пример с более подробным объяснением вашей идеи? Текущая версия вашего ответа сбивает меня с толку.
Разработчик
3

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

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

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

введите описание изображения здесь

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

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

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

Толга Бердал
источник