Kantenbasierte Segmentation
Kanten vollständig detektieren
Problem: Bei der normalen Kantendetektion haben wir das Problem, daß die Kanten sehr "dick" werden und "verwaschen".
Idee:
Suche eine Kantendetektion, die die Kanten möglichst genau
trifft.
Lösung:
Non-Maximum-Supression
In Halcon:
nonmax_suppression , teilweise auch: nms
Im Vergleich sieht man, daß die Kanten dünner sind als zuvor.
Bei der Non-Maximum-Suppression werden die nicht maximalen Punkte (bezogen auf ihren Grauwert) des Amplitudenbildes (eines Kantenfilters) in die Ausgaberegion nicht mit übernommen (unterdrückt).
Man unterscheidet hier zwei wesentliche Vorgehensweisen:
Problem: Die normale Schewellwertoperation (die das Rauschen herausfiltern soll) liefert bei relativ hohem Schwellwertnicht notwendigerweise zusammenhängende Kanten, bei relativ niedrigem Schwellwert aber zu viel Rauschen.
Idee:
Suche "intelligenten" Operator, der die Kanten
"komplett" erkennt und gleichzeitig das Rauschen
herausfiltert.
Lösung: Schwellwertoperation mit Hysterese
In Halcon: hysteresis_threshold:
Dieser Schwellwertoperation werden zwei Schwellwerte übergeben:
Ein oberer und ein unterer Schwellwert.
Hierbei bezeichnet Hysterese das Verhalten, das die sicheren
Punkte auf ihre Nachbarpixel (Sicherheit) abstrahlen.
In Halcon sind die
Non-Maximum-Supression der Hystere-Schwellwert und eine
Kantenfilter in einem Operator zusammengefaßt:
edges_image
Umrechnung von Kanten
in Konturen (Segmentierung)
Um Konturen aus einem Kantenbild zu berechnen muß dieses in skelletierter Form vorliegen, d.h. die Kanten dürfen nur noch ein Pixel breit sein.
- Endpunkte sind diejenigen Punkte, die in 8-Nachbarschaft nur einen Nachbarn haben
- Kreuzungspunkte sind diejenigen Punkte, die in 8-Nachbarschaft mehr als 3 Nachbarn haben
(Alle Punkte, die genau 2 Nachbarn haben sind "normale" Kantenpunkte mit Vorgänger und Nachfolger.)
Konturen haben gegenüber Kanten zwei Vorteile:
In Halcon gibt es die Operatoren:
junction_skeleton
- dieser erkennt lediglich End- und Kreuzungspunkte und
gen_contours_skeleton_xld: -
dieser berechnet die Konturen
Ziel: Eine
mathematische Funktion (sog. Polygon), die die Kontur
möglichst genau beschreibt, da diese Datenstruktur wesentlich
einfacher in der Handhabung ist als Pixeldastellung der Kontur.
Außerdem lassen sich beispielsweise Parallelitäten leichter mit
dieser Datenstruktur "erkennen".
Hierfür gibt es drei verschiedene Verfahren:
1.) Polygonapproximation mit dem Verfahren von Ramer:
Das Verfahren von Ramer zur Kurvennapproximation ermöglicht
es mit Hilfe einer iterativen Methode Polygone mit einer kleinen
Anzahl von Stützstellen zu erzeugen.
Der Parameter "a " bestimmt
hierbei die Genauigkeit der Approximation, die bestimmt wird
durch den Abstand des Polygons zur Originalkurve.
Der Algorithmus beginnt, indem er den Anfangs- und den Endpunkt
der zu approximierenden Kurve als sog. Stützstellen markiert und
verbindet - dies ist die erste Approximation.
Als nächstes sucht dieser jeweils den Punkt mit maximalen
Abstand zur Originalkurve und approximiert diese erneut, indem er
diesen Punkt als weitere Stützstelle einfügt. Dieser Schritt
wird mit den zwei Hälften (links und rechts der neuen
Stützstelle) wiederholt bis der Abstand zur Originalkurve
jeweils kleiner oder gleich dem Parameterwert ist.
Das iterative Vorgehen läßt sich mit der folgenden Grafik
verdeutlichen:
Anmerkung:
Dieser Algorithmus braucht nur sehr wenige Stützstellen,
allerdings kann man die Komplexität des Polygons nicht direkt
beeinflussen.
2.) Das Verfahren von Ray:
Der Algorithmus der dieses Verfahren beschreibt versucht ein
möglichst langes Kurvenstück der Originalkurve mit einem
Geradenstück zu approximieren, wobei der Fehler bezüglich des
jeweiligen Segments minimal sein soll (d.h. unter einer
vordefinierten Grenze).
Anmerkung:
Auch hier ist es nicht möglich die Komplexität Komplexität
des Polygons direkt zu beeinflussen.
3.) Das Verfahren von Sato:
Diesem Algorithmus wird die Anzahl der Stützstellen
übergeben (und somit die Komplexität der Approximation
bestimmt). Dann berechnet dieser dasjenige Polygon, das die
Originalkurve am bestem approximiert (unter Berücksichtigung der
max. zu verwendenden Stützstellen).
Der Algorithmus versucht durch Ausgleichsgeraden zwischen den
Stützstellen den Approximationsfehler durch
"geschickte" Wahl zu minimieren.
Anmerkung:
Die Komplexität des Polygons ist festgelegt, allerdings geht
dies u.U. auf Kosten der Genauigkeit.
- Das "richtige" Verfahren auszuwählen hängt
stark von den verwendeten Eingabedaten und der weiteren
Verarbeitung ab.