Быстрый алгоритм для поиска маленькой картинки в большой картине?

Какой лучший (самый быстрый) способ проверить, находится ли маленькая картинка внутри большой картинки?

(Увеличенное изображение:)

enter image description here Хотите найти: enter image description here

У меня есть решение, но оно очень медленное:

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

для этого метода требуется ~ 7 секунд, чтобы найти фотографию размером 50x50 на снимке 1600x1200.

Может быть, вы знаете лучший алгоритм? Я знаю программное обеспечение, которое может сделать это через секунду.

Ответы

Ответ 1

Математическая операция convolution (которая может быть эффективно реализована с помощью Fast Fourier Transform).

Ответ 2

в другом ответе описывается взаимная корреляция через свертку изображений (реализуется путем умножения ffts). но иногда вы хотите использовать нормированную кросс-корреляцию - см. http://scribblethink.org/Work/nvisionInterface/nip.html для полного обсуждения и подробностей быстрой реализации.

Ответ 3

Если вы знаете, что значения пикселей будут точными, это станет частным случаем проблемы с сопоставлением строк. Есть много быстрых алгоритмов сопоставления строк, я бы начал с Boyer-Moore или Кнут-Морриса-Пратта.

Ответ 4

У вас есть худший случай O(hA*wA*hB*wB), где hA, wA, hB, wB - высота и ширина большого изображения A и маленькое изображение B.

Этот альго должен иметь худший случай O((wA+wB)*hA*hB)

Он основан на сопоставлении строк, и вот как это работает:

  • Найдите каждую строку изображения B в каждой строке изображения A, используя каждый раз подряд.
    • Каждый раз, когда у вас есть соответствие, храните в массиве matched_row тройной (rA, cA, rB), где (rA, cA) представляет начальную точку в изображении A строки rB файла B.
  • Теперь вы сортируете matched_row сначала в соответствии с cA, затем до rA, а затем до rB.

  • Теперь вы перебираете массив, и если вы сопоставляете изображение B из 5 строк, у вас будет что-то вроде этого:

        (12, 5, 0), (13, 5, 1), (14, 5, 2), (15, 5, 3), (15, 5, 4)

Ответ 5

Что бы я хотел нарезать оба изображения в изображениях 10x10, вычислить "средний" цвет каждого маленького изображения и выполнить тот же алгоритм, что и вы.

Это должно масштабироваться с любым алгоритмом, поскольку оно влияет только на постоянный коэффициент.