Canny-Algorithmus
aus Wikipedia, der freien Enzyklopädie
Der Canny-Algorithmus, benannt nach John Canny, ist ein in der digitalen Bildverarbeitung weit verbreiteter, robuster Algorithmus zur Kantendetektion. Er gliedert sich in verschiedene Faltungsoperationen und liefert ein Bild, welches idealerweise nur noch die Kanten des Ausgangsbildes enthält.
Da der Algorithmus nur auf Graubildern arbeiten kann, ist eine vorherige Überführung von farbigen Bildern in Graubilder erforderlich. In diesen Grauwertbildern sind Kanten durch große Helligkeitsschwankungen zwischen zwei benachbarten Pixeln charakterisiert. Sie können somit als eine Unstetigkeit der Grauwertfunktion g(x,y) des Ausgangsbildes aufgefasst werden. Da derartige Unstetigkeiten auch ohne das Vorhandensein von Kanten einfach durch Bildrauschen auftreten können, verwendet der Algorithmus die Gaußsche Normalverteilung zur Glättung des Bildes.
Dabei wird das Originalbild mit Hilfe einer Maske gefaltet, die die Gaußsche Normalverteilung annähert. Der neue Grauwert eines Pixels gn(x,y) ergibt sich dabei aus den gewichteten Werten der ihn umgebenden Pixel. Ein Beispiel für eine solche Maske könnte sein:
Je größer hierbei die Maske gewählt wird, desto robuster wird der Algorithmus gegenüber Rauschen.
Anschließend werden die Gradienten der einzelnen Pixel ermittelt, indem das Bild mit Hilfe des Sobeloperators gefaltet wird. Dieser arbeitet entweder in X-Richtung oder in Y-Richtung und betont somit entweder horizontale oder vertikale Kanten. Auch beim Sobeloperator ergibt sich der neue Wert eines Pixels aus den gewichteten Werten der ihn umgebenden Pixel. Da für den Canny-Algorithmus der Gradient in X-Richtung gx und der Gradient in Y-Richtung gy benötigt werden, ergeben sich also nach Anwendung des Sobeloperators 2 neue Bilder.
Sobeloperator in X-Richtung
Sobeloperator in Y-Richtung
Mithilfe der beiden so ermittelten Gradienten lässt sich der Anstieg einer potentiellen Kante durch einen Pixel leicht errechnen. Es gilt:
.
Da ein Pixel jedoch nur 8 Nachbarn hat, ergeben sich insgesamt lediglich 4 mögliche Kantenanstiege: 0°, 45°, 90° und 135°. Die soeben errechneten Anstiege werden also auf einen dieser Werte gerundet.
Die Kantenstärke eines einzelnen Pixels wird als Summe aus dem Betrag der beiden Gradienten gebildet.
Um sicherzustellen, dass eine Kante nicht mehr als einen Pixel breit ist, werden im folgenden Schritt lokale Maxima gesucht. Dabei wird für jeden Pixel überprüft, ob einer seiner 8 Nachbarn eine höhere Kantenstärke als der Pixel selbst hat. Ist dies der Fall, und führt der errechnete Kantenanstieg von diesem Pixel mit höherer Kantenstärke nicht auf den zu betrachtenden Pixel, wird dessen Kantenstärke auf 0 gesetzt. Man kann also annehmen das dieser Pixel nicht zu einer Kante gehört.
Abschließend muss natürlich noch festgestellt werden, ab welcher Kantenstärke ein Pixel zu einer Kante zu zählen ist. Um das Aufbrechen einer Kante durch Schwankungen in der errechneten Kantenstärke zu vermeiden wird ein Hysterese genanntes Verfahren angewendet. Bei diesem Verfahren verwendet man zwei Schwellwerte. Alle Pixel, deren Kantenstärke über dem ersten Schwellwert liegen, werden als Kantenelemente (Edgels, von engl. edgeelements) aufgefasst. Alle, deren Kantenstärke unter dem zweiten Schwellwert liegen, werden nicht weiter als Edgels in Betracht gezogen. Für Pixel, deren Kantenstärke zwischen den beiden Schwellwerten liegen, gilt: Sie sind ein Edgel wenn einer ihrer Nachbarn ein Edgel ist und dessen Kantenanstieg zu ihnen selbst führt. Nach diesem letzten Schritt ist der Algorithmus beendet und liefert eine Menge von Punkten, die bei korrekter Wahl der Schwellwerte die im Ausgangsbild vorhandenen Kanten aufzeigen.
Diese Menge von Punkten kann auf viele verschieden Arten verwendet werden, um weitere Informationen aus dem Bild zu extrahieren (z.B. Hough-Transformation zur Erkennung einfacher geometrischer Objekte oder Waltz-Algorithmus zur Erkennung von dreidimensionalen Objekten im Bild).
