Найти изображение в изображении

Question

Я ищу лучший способ обнаружить изображение в другом изображении. У меня есть маленькое изображение, и я хотел бы найти место, где оно появляется на большом изображении, которое фактически будет снимками экрана. Концептуально это похоже на «Где Уолдо?» вид поиска в увеличенном изображении.

Есть ли эффективные / быстрые способы сделать это? Скорость важнее памяти.

Редактировать:

«Внутреннее» изображение может не всегда иметь одинаковый масштаб, но будет иметь одинаковое вращение.

Небезопасно предполагать, что изображение будет идеально заключено в другое, пиксель за пикселем.

Answer 1

В Википедии есть статья Соответствие шаблону , с примером кода.

(Хотя эта страница не обрабатывает измененные масштабы, она имеет ссылки на другие стили соответствия, например Преобразование инвариантной функции масштаба )

Answer 2

Если вращение также необходимо учитывать, можно использовать Обобщенное преобразование Хафа .

Answer 3

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

Алгоритм, который вы хотите, находится в Википедии: http://en.wikipedia.org/wiki/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm

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

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