Punktmustererkennung

Bei zwei unterschiedlichen Punktmengen (zweidimensional zur Vereinfachung), die auf zwei unterschiedliche Quadrate verteilt sind, stellt sich die Frage:

1- Wie kann man ein Vorkommen des Kleinen durch das Große finden?
2- Haben Sie eine Idee, wie Sie die Vorkommen wie in der folgenden Abbildung gezeigt einstufen können?

Hier ist eine einfache Demonstration der Frage und eine gewünschte Lösung:

Update 1:
Die folgende Abbildung zeigt eine etwas realistischere Ansicht des untersuchten Problems.

Zu den Kommentaren gelten folgende Eigenschaften:

• Die genaue Position der Punkte ist verfügbar
• genaue größe der punkte sind vorhanden
  • Größe kann Null sein (~ 1) = nur ein Punkt
• Alle Punkte sind schwarz auf weißem Hintergrund
• Es gibt keinen Graustufen- / Anti-Aliasing-Effekt

Hier ist meine Implementierung der vorgestellten Methode endolithmit einigen kleinen Änderungen (ich habe das Ziel anstelle der Quelle gedreht, da es kleiner und schneller gedreht wird). Ich akzeptierte die Antwort des Endolithen, weil ich vorher darüber nachgedacht hatte. Über RANSAC habe ich bisher keine Erfahrung. Darüber hinaus erfordert die Implementierung von RANSAC viel Code.

Dies ist nicht die beste Lösung, aber es ist eine Lösung. Ich möchte von besseren Techniken lernen:

Wenn sie nicht gedreht oder skaliert würden, könnten Sie eine einfache Kreuzkorrelation der Bilder verwenden. Überall dort, wo das kleine Bild im großen Bild auftritt, wird es einen hellen Peak geben.

• Registrieren eines Bildes mit normalisierter Kreuzkorrelation
• Template-basiertes Matching und Convolution

Sie können die Kreuzkorrelation mit einer FFT-Methode beschleunigen. Wenn Sie jedoch nur ein kleines Quellbild mit einem großen Zielbild abgleichen, ist die Brute-Force-Multiplikations- und Additionsmethode manchmal (normalerweise) schneller.

Quelle:

Ziel:

Kreuzkorrelation:

Die beiden hellen Punkte sind die Orte, die übereinstimmen.

Sie haben jedoch einen Rotationsparameter in Ihrem Beispielbild, sodass dies für sich allein nicht funktioniert. Wenn nur eine Drehung und keine Skalierung zulässig ist, kann die Kreuzkorrelation weiterhin verwendet werden. Sie müssen jedoch die Quelle kreuzkorrelieren, drehen, mit dem gesamten Zielbild kreuzkorrelieren, erneut drehen usw. für alle Umdrehungen.

Beachten Sie, dass das Bild dadurch nicht unbedingt gefunden wird. Handelt es sich bei dem Quellbild um zufälliges Bildrauschen und bei dem Ziel um zufälliges Bildrauschen, werden Sie es nur finden, wenn Sie genau im richtigen Winkel suchen. Unter normalen Umständen wird es wahrscheinlich gefunden, aber es hängt von den Bildeigenschaften und den Winkeln ab, in denen Sie suchen.

Diese Seite zeigt ein Beispiel, wie es gemacht wird, gibt aber keinen Algorithmus an.

Jeder Offset, bei dem die Summe über einem bestimmten Schwellenwert liegt, ist eine Übereinstimmung. Sie können die Güte der Übereinstimmung berechnen, indem Sie das Quellbild mit sich selbst korrelieren und alle Ihre Summen durch diese Zahl dividieren. Eine perfekte Übereinstimmung wird 1.0 sein.

Dies ist jedoch sehr rechenintensiv, und es gibt wahrscheinlich bessere Methoden zum Abgleichen von Punktmustern (über die ich gerne etwas wissen würde).

Schnelles Python-Beispiel mit Graustufen- und FFT-Methode:

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-Farben-Bitmaps

Bei 1-Farben-Bitmaps wäre dies jedoch viel schneller. Kreuzkorrelation wird:

• Platzieren Sie das Quellbild über dem Zielbild
  • bitweises UND aller überlappenden Pixel (viel schneller als Multiplikation)
  • summiere alle 1s im überlappenden Bereich
• Quellbild um 1 Pixel verschieben
  • bitweise UND alle überlappenden Pixel
  • summiere alle 1s
• ...

Wenn Sie ein Graustufenbild auf Binärwert beschränken, ist dies möglicherweise ausreichend.

Punktwolke

Wenn die Quelle und das Ziel beide Punktmuster sind, besteht eine schnellere Methode darin, die Mitten jedes Punkts zu finden (einmal mit einem bekannten Punkt kreuzkorrelieren und dann die Peaks suchen) und sie als Satz von Punkten zu speichern und dann mit der Quelle abzugleichen zum Zielen drehen, verschieben und den Fehler der kleinsten Quadrate zwischen den nächstgelegenen Punkten in den beiden Mengen finden.

Aus Sicht des Computers: Das Grundproblem besteht darin, eine Homographie zwischen Ihrer Zielpunktmenge und einer Teilmenge von Punkten in der großen Menge zu schätzen . In Ihrem Fall handelt es sich nur bei Rotation um eine affine Homographie. Sie sollten sich mit der RANSAC- Methode befassen . Es wurde entwickelt, um eine Übereinstimmung in einem Set mit vielen Ausreißern zu finden. Sie sind also mit zwei wichtigen Schlüsselwörtern ausgestattet: Homografie und RANSAC .

OpenCV bietet Tools zur Berechnung dieser Lösungen, Sie können aber auch MATLAB verwenden. Hier ist ein RANSAC-Beispiel mit OpenCV . Und noch eine vollständige Implementierung .

Eine typische Anwendung könnte darin bestehen, ein Buchcover in einem Bild zu finden. Sie haben ein Bild des Buchumschlags und ein Foto des Buches auf einem Tisch. Der Ansatz besteht nicht darin, einen Vorlagenabgleich durchzuführen, sondern in jedem Bild markante Ecken zu finden und diese Punktmengen zu vergleichen. Ihr Problem scheint die zweite Hälfte dieses Prozesses zu sein - den Punkt zu finden, der in einer großen Wolke festgelegt ist. RANSAC wurde entwickelt, um dies robust zu machen.

Ich denke, Kreuzkorrelationsmethoden können auch für Sie funktionieren, da die Daten so sauber sind. Das Problem ist, dass Sie mit der Drehung einen weiteren Freiheitsgrad hinzufügen und die Methode sehr langsam wird.

Wenn das Muster spärlich binär ist, können Sie einfache Kovarianz von Koordinatenvektoren anstelle von Bildern durchführen. Nehmen Sie Koordinaten von Punkten im Unterfenster, sortieren Sie sie links oben, erstellen Sie einen Vektor aus allen Koordinaten und berechnen Sie die Kovarianz mit einem Vektor, der aus Koordinaten von Punkten von Mustern besteht, die links oben sortiert sind. Sie können auch Gewichte verwenden. Danach suchen die nächsten Nachbarn mit Brute Force nach maximaler Kovarianz auf einem Gitter im großen Fenster (und auch in Rotationswinkeln). Nachdem Sie mit der Suche ungefähre Koordinaten gefunden haben, können Sie diese mit der Methode der kleinsten Quadrate neu gewichten.

PS Idea ist, anstatt mit Bildern zu arbeiten, können Sie auch mit Koordinaten von Pixeln ungleich Null arbeiten. Gemeinsame Suche nach dem nächsten Nachbarn. Sie sollten den gesamten Suchraum vollständig durchsuchen, sowohl translatorisch als auch rotatorisch. Verwenden Sie dazu ein Raster, dh einen Schritt in Bezug auf die Koordinaten und den Rotationswinkel. Für jede Koordinate / jeden Winkel nehmen Sie eine Teilmenge der Pixel im Fenster, deren Mittelpunkt auf diesen Winkel gedreht ist. Nehmen Sie deren Koordinaten (relativ zum Mittelpunkt) und vergleichen Sie sie mit den Koordinaten der Pixel des gesuchten Musters. Sie sollten sicherstellen, dass in beiden Sätzen die Punkte auf die gleiche Weise sortiert sind. Sie finden Koordinaten mit minimaler Differenz (maximale Kovarianz). Nach dieser groben Übereinstimmung können Sie eine genaue Übereinstimmung mit einer Optimierungsmethode finden. Entschuldigung, ich kann es nicht einfacher weitergeben.

Ich bin sehr überrascht, warum niemand Methoden der Generalized Hough Transform- Familie erwähnte . Sie lösen dieses spezielle Problem direkt.

Folgendes schlage ich vor:

1. Nehmen Sie die Vorlage, erstellen Sie die R-Tabelle und indizieren Sie die Kanten der Vorlage. Die Kanten, die ich auswähle, sind die folgenden:

2. Verwenden Sie die Standard- OpenCV-Implementierung der generalisierten Hough-Transformation , um Folgendes zu erhalten:

wo passende Orte markiert sind. Das gleiche Verfahren wäre auch dann noch funktionsfähig, wenn die Kanten auf einen einzigen Punkt reduziert würden, da für das Verfahren keine Bildintensitäten erforderlich sind.

Darüber hinaus ist die Handhabung von Rotationen bei Hough-Schemata sehr natürlich. Tatsächlich ist es für 2D-Fälle nur eine zusätzliche Dimension im Akkumulator. Für den Fall, dass Sie auf Details eingehen möchten, um es wirklich effizient zu machen, erklärt M. Ulrich eine Menge Tricks in seiner Arbeit .

Dies ist eine gute Anwendung für geometrisches Hashing. geometrische Hashing-Wikipedia-Seite