Znajdź obraz w obrazku

Question

Szukam najlepszego sposobu na wykrycie obrazu w innym obrazie. Mam mały obrazek i chciałbym znaleźć lokalizację, w której się pojawi w ramach większego obrazu - który faktycznie będzie przechwytywany na ekranie. Koncepcyjnie to jest jak "Gdzie jest Waldo?" sortowanie wyszukiwania na większym obrazie.

Czy istnieją skuteczne/szybkie sposoby osiągnięcia tego? Szybkość jest ważniejsza niż pamięć.

Edit:

do „wewnętrzny” obraz może nie zawsze mają taką samą skalę, ale mają ten sam obrót.

Nie można bezpiecznie założyć, że obraz będzie idealnie zawarty w drugim, piksel na piksel.

Answer 1

Wikipedia ma artykuł o Template Matching, z przykładowym kodem.

(Mimo, że strona nie obsługuje zmienione wagi, posiada linki do innych stylów dopasowania, na przykład Scale invariant feature transform)

Answer 2

Można traktować to jako problem z podciąganiu, w którym znaki w alfabecie są pikselami, a ciąg znaków jest obrazem. Będziesz także potrzebował użyć znaku specjalnego w podobnym duchu do łamania linii, aby wskazać granicę obrazu.

Algorytm chcesz to na wikipedii: http://en.wikipedia.org/wiki/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm

Aktualizacja: Jeśli nie można przyjąć, że obraz jest doskonale zawarte w drugiej, piksel na piksel, to podejście nie będzie działać.

Istnieją inne, bardziej skomplikowane algorytmy oparte na tej samej koncepcji programowania dynamicznego co powyższe, ale nie będę do nich wchodzić, chyba że będzie to konieczne.

Answer 3

Jeśli rotacja również musiał być pokrywane, w Generalised Hough Transform mogą być użyte.