Finden Sie die Ecken eines Polygons, das durch eine Regionsmaske dargestellt wird
BW = poly2mask(x, y, m, n)berechnet a binäre Region of Interest (ROI) -Maske, BW, aus einem ROI-Polygon, dargestellt durch die Vektoren x und y. Die Größe von BW ist m-mal-n.
poly2masksetzt Pixel im BW das sind innerhalb des Polygons (X, Y) bis 1 und setzt Pixel außerhalb des Polygons auf 0.
Problem:
Mit einer solchen binären Maske BW eines konvexen Vierecks, was wäre der effizienteste Weg, um die vier Ecken zu bestimmen?
z. B.
Beste Lösung bisher:
Verwenden Sie edge , um die Begrenzungslinien zu finden, die Hough-Transformation, um die 4 Linien im Kantenbild zu finden, und suchen Sie dann die Schnittpunkte dieser 4 Linien oder verwenden Sie einen Eckendetektor am Kantenbild. Scheint kompliziert, und ich kann mir nicht helfen zu fühlen, dass es eine einfachere Lösung gibt.
Btw, convhull gibt nicht immer 4 Punkte zurück (vielleicht kann jemand qhull -Optionen vorschlagen, um das zu verhindern): es gibt auch ein paar Punkte entlang der Kanten zurück.
BEARBEITEN:
Amros Antwort wirkt sehr elegant und effizient. Aber es könnte mehrere "Ecken" an jeder echten Ecke geben, da die Spitzen nicht eindeutig sind. Ich könnte sie basierend auf θ gruppieren und die "Ecken" um eine echte Ecke herum berechnen, aber das Hauptproblem ist die Verwendung von order(1:10) .
Ist 10 genug, um alle Ecken zu berücksichtigen oder schließt dies eine "Ecke" an einer echten Ecke aus?
5 Antworten
Dies ist etwas ähnlich zu dem, was @AndyL vorgeschlagen wurde. Allerdings verwende ich die Grenzsignatur in Polarkoordinaten anstelle der Tangente.
Beachten Sie, dass ich anfange, indem ich die Kanten extrahiere, die Grenze erhalte und sie dann in die Signatur umwandle. Schließlich finden wir die Punkte auf der Grenze, die vom Schwerpunkt am weitesten entfernt sind, diese Punkte bilden die gefundenen Ecken. (Alternativ können wir auch Spitzen in der Signatur für Ecken erkennen.)
Das Folgende ist eine vollständige Implementierung:
%Vor% 
BEARBEITEN: Als Antwort auf Jacobs Kommentar sollte ich erklären, dass ich zuerst versucht habe, die Spitzen in der Signatur mit ersten / zweiten Ableitungen zu finden, aber am Ende die weitesten N-Punkte genommen habe. 10 war nur ein Ad-hoc-Wert und wäre schwierig zu verallgemeinern (Ich habe versucht, 4 wie die Anzahl der Ecken zu nehmen, aber es hat nicht alle abgedeckt). Ich denke, die Idee, sie zu gruppieren, um Duplikate zu entfernen, ist eine Betrachtung wert.
Soweit ich das sehe, bestand das Problem beim ersten Ansatz darin, dass Sie, wenn Sie rho darstellen, ohne θ zu berücksichtigen, eine andere Form (nicht die gleichen Peaks) erhalten, da die Geschwindigkeit durch die wir die Grenze verfolgen, ist unterschiedlich und hängt von der Krümmung ab. Wenn wir herausfinden könnten, wie dieser Effekt normalisiert wird, können wir mit Derivaten genauere Ergebnisse erzielen.
Wenn Sie die Bildverarbeitungs-Toolbox haben, gibt es eine Funktion namens cornermetric , die einen Harris-Eckendetektor oder die minimale Eigenwertmethode von Shi und Tomasi implementieren können. Diese Funktion ist seit Version 6.2 der Image Processing Toolbox (MATLAB-Version R2008b) verfügbar.
Mit dieser Funktion hatte ich einen etwas anderen Ansatz als die anderen Antworten. Die folgende Lösung basiert auf der Idee, dass ein kreisförmiger Bereich, der an jedem "wahren" Eckpunkt zentriert ist, das Polygon um einen kleineren Betrag überlappt als ein kreisförmiger Bereich, der über einem fehlerhaften Eckpunkt zentriert ist, der sich tatsächlich an der Kante befindet. Diese Lösung kann auch Fälle behandeln, in denen mehrere Punkte an derselben Ecke erkannt werden ...
Der erste Schritt besteht darin, die Daten zu laden:
%Vor% Berechnen Sie als Nächstes die Eckmetrik mithilfe von cornermetric . Beachten Sie, dass ich die Eckmetrik durch das ursprüngliche Polygon maskiere, so dass wir nach Eckpunkten suchen, die innerhalb des Polygons sind (d. H. Versuchen, die Eckpixel des Polygons zu finden). imregionalmax wird dann verwendet, um die lokalen Maxima zu finden. Da Sie Cluster mit mehr als 1 Pixel mit der gleichen Eckmetrik haben können, addiere ich dann Rauschen zu den Maxima und rechne es neu, so dass ich nur 1 Pixel in jeder maximalen Region erhalte. Jede maximale Region wird dann mit bwlabel gekennzeichnet:
Die markierten Regionen werden dann (mit imdilate ) mit einem scheibenförmigen erweitert strukturierendes Element (erstellt mit strel ):
Nachdem die markierten Eckbereiche erweitert wurden, überlappen sie das ursprüngliche Polygon teilweise. Regionen an einer Kante des Polygons haben etwa 50% Überlappung, während Regionen an einer Ecke eine Überlappung von etwa 25% aufweisen. Die Funktion regionprops kann verwendet werden, um die Überlappungsbereiche für jede markierte Region zu finden die 4 Regionen, die die geringste Überlappung aufweisen, können daher als die wahren Ecken betrachtet werden:
Und jetzt können wir die Pixelkoordinaten der Ecken mit find und ismember :
Und hier ist ein Test mit einer rautenförmigen Region:
Ich möchte dieses Problem lösen, indem ich mit einer Grenze arbeite, weil es das von einem 2D-Problem auf ein 1D-Problem reduziert.
Verwenden Sie bwtraceboundary() aus dem Bildverarbeitungs-Toolkit, um eine Liste von Punkten auf der Grenze zu extrahieren. Dann wandle die Grenze in eine Reihe von Tangentenvektoren um (es gibt eine Anzahl von Möglichkeiten, dies zu tun, eine Art wäre, die
i th Punkt entlang der Grenze vom Punkt i+delta .) Sobald Sie eine Liste von Vektoren haben, nehmen Sie das Skalarprodukt benachbarter Vektoren. Die vier Punkte mit den kleinsten Punktprodukten sind deine Ecken!
Wenn Ihr Algorithmus an Polygonen mit einer beliebigen Anzahl von Knoten arbeiten soll, dann suchen Sie einfach nach Punktprodukten, die eine bestimmte Anzahl von Standardabweichungen unter dem mittleren Punktprodukt haben.
Ich entschied mich für einen Harris Corner Detektor (hier ist ein weitere formelle Beschreibung ), um die Ecken zu erhalten. Dies kann wie folgt implementiert werden:
%Vor% Hier das Problem mit mehreren Ecken dank der Gaußschen Fensterfunktion, die die Intensitätsänderung glättet. Im Folgenden sehen Sie eine vergrößerte Version einer Ecke mit der hot colormap.
Hier ist ein Beispiel mit Ruby und HornetsEye . Grundsätzlich erstellt das Programm ein Histogramm der quantisierten Sobel-Gradientenorientierung, um dominante Orientierungen zu finden. Wenn vier dominante Orientierungen gefunden werden, werden Linien angepasst und die Schnittpunkte zwischen benachbarten Linien werden als die Ecken des projizierten Rechtecks angenommen.
%Vor% 
Tags und Links matlab computer-vision geometry polygon corner-detection