By Rean Neil Luces
Template Matching ist ein wichtiges Thema im Bereich der Künstlichen Intelligenz (KI), da es einer der Ansätze für das Grundproblem der Bildverarbeitung ist, nämlich die Lokalisierung der Region von Interesse. Es findet heraus, wo sich ein bestimmtes Objekt in einem gegebenen Bild befindet. Es hat eine breite Palette von Anwendungen wie Objekterkennung, Verfolgung, Überwachung, medizinische Bildgebung und Bildstitching.
Template Matching besteht ebenfalls aus zwei Hauptkomponenten: dem Quellbild und dem Template-Bild oder dem Patch. Das Quellbild ist das Bild, von dem wir erwarten, dass es mit dem Vorlagenbild übereinstimmt, während das Vorlagenbild das Patch-Bild ist, das mit dem Teilbild des Quellbildes verglichen wird.
Die beiden allgemeinen Klassifizierungen des Vorlagen- oder Bildabgleichs sind vorlagenbasiert und merkmalsbasiert. Der schablonenbasierte Ansatz, der auch als flächenbasierter Ansatz bezeichnet wird, funktioniert sehr gut, wenn Schablonen keine starken Merkmale mit einem Bild aufweisen, da sie direkt mit den Pixelwerten arbeiten. Die Übereinstimmungen werden anhand der Intensitätswerte des Bildes und der Vorlage gemessen. Der merkmalsbasierte Ansatz hingegen wird verwendet, wenn sowohl das Ausgangsbild als auch die Vorlage eine größere Übereinstimmung in Bezug auf Merkmale und Kontrollpunkte aufweisen. In diesem Fall umfassen die Merkmale Punkte, Kurven oder ein Oberflächenmodell, um einen Vorlagenabgleich durchzuführen.
Vorlagenbasierter Ansatz
Der vorlagenbasierte Ansatz ist einfacher zu implementieren als der merkmalsbasierte. Beim einfachen Template-Matching wird das Template-Bild mit dem Quellbild verglichen, indem es verschoben wird. Das Schablonenbild wird jeweils um ein Pixel von links nach rechts oder von oben nach unten verschoben, um ein numerisches Maß für die Ähnlichkeit mit dem überlappenden Bereich zu berechnen. Beide Bilder werden in Binärbilder oder Schwarz-Weiß-Bilder umgewandelt, und dann werden Verfahren zum Abgleich von Vorlagen wie normalisierte Kreuzkorrelation, Kreuzkorrelation und Summe der quadratischen Differenz angewandt.
Eine der Herausforderungen des vorlagenbasierten Ansatzes ist die Skaleninvarianz. Änderungen in der Größe des Quellbildes oder des Vorlagenbildes wirken sich auf die Leistung des Algorithmus aus. Ein einfacher Trick zur Lösung des Problems besteht darin, die Größe des Vorlagenbildes in mehreren Maßstäben zu ändern und es dann mit dem Ausgangsbild zu vergleichen. Nachdem Sie alle Größen durchgespielt haben, nehmen Sie die Region mit dem größten Korrelationskoeffizienten und verwenden diese als „angepasste“ Region. Allerdings ist die Rotationsinvarianz mit diesem Ansatz schwer zu lösen. Daher entwickelte Kim, Hae & Araújo, Sidnei (2007) den Ciratefi-Algorithmus, um das Rotationsproblem durch Verbesserung des Brute-Force-Algorithmus zu lösen, bei dem das Vorlagenbild in jedem Winkel gedreht wird. Der Ciratefi-Algorithmus ist 400-mal schneller als der Brute-Force-Algorithmus und erzielt die gleichen Ergebnisse.
Merkmalbasierter Ansatz
Bildmerkmale, wie Kanten und interessante Punkte, liefern reichhaltige Informationen über den Bildinhalt. Lokale Merkmale und ihre Deskriptoren sind die Bausteine vieler Computer-Vision-Algorithmen. Zu ihren Anwendungen gehören Bildregistrierung, Objekterkennung und -klassifizierung, Verfolgung und Bewegungsabschätzung. Diese Merkmale sind exklusiv für jedes Bild und helfen daher bei der Identifizierung zwischen Bildern. Die Merkmale eines Bildes bleiben auch dann erhalten, wenn sich Größe und Ausrichtung ändern, so dass sich der Ansatz auch dann als nützlich erweisen kann, wenn die Übereinstimmung im Suchbild auf irgendeine Weise transformiert wird. Dieser Ansatz ist auch effizienter, wenn das Bild eine große Auflösung hat. Wenn Sie Ihr Vorlagenbild pixelweise in ein großes Ausgangsbild schieben und dies in verschiedenen Maßstäben wiederholen, ist dies sehr rechenintensiv.
Der merkmalsbasierte Vorlagenabgleich umfasst vier Hauptschritte. Die ersten beiden Schritte sind die Merkmalserkennung und die Merkmalsextraktion. SIFT (Scale Invariant Feature Transform) und SURF (Speeded Up Robust Feature) eignen sich am besten für die Erkennung und den Abgleich von Merkmalen, da sie nicht skaliert, gedreht, verschoben, beleuchtet und verwischt werden können. Nach der Merkmalserkennung und -extraktion ist der nächste Schritt der Merkmalsabgleich mit Fast Library for Approximate Nearest Neighbors (FLANN). Sie enthält eine Sammlung von Algorithmen, die für die schnelle Suche nach den nächsten Nachbarn in großen Datensätzen und hochdimensionalen Merkmalen optimiert sind. Aus den vom FLANN-Matcher gesammelten übereinstimmenden Merkmalen werden anhand des Lowe’s Ratio-Tests gute Übereinstimmungen ausgewählt. Nach der Filterung von Merkmalspunkten wird im nächsten Schritt die Homographie mit Hilfe des RANSAC-Algorithmus (RANdom SAmple Consensus) berechnet.
Dieser Ansatz kann jedoch nicht verwendet werden, wenn die Bilder weniger Merkmale aufweisen oder verschiedene Objekte die gleichen Merkmale haben, da der Algorithmus die Vorlage im Ausgangsbild nicht finden kann.