Canny-Algorithmus

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche
Dieser Artikel oder nachfolgende Abschnitt ist nicht hinreichend mit Belegen (beispielsweise Einzelnachweisen) ausgestattet. Die fraglichen Angaben werden daher möglicherweise demnächst entfernt. Bitte hilf der Wikipedia, indem du die Angaben recherchierst und gute Belege einfügst. Näheres ist eventuell auf der Diskussionsseite oder in der Versionsgeschichte angegeben. Bitte entferne zuletzt diese Warnmarkierung.
Dieser Artikel oder Abschnitt bedarf einer Überarbeitung. Näheres ist auf der Diskussionsseite angegeben. Hilf mit, ihn zu verbessern, und entferne anschließend diese Markierung.

Der Canny-Algorithmus (auch: Canny edge detector), benannt nach John Francis Canny[1], 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.

Vorprozessierung[Bearbeiten]

Ausgangsbild für den Algorithmus

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 Normalverteilung zur Glättung des Bildes.

Dabei wird das Originalbild mit Hilfe einer Maske gefaltet, die die Normalverteilung annähert. Der neue Grauwert eines Pixels g_n(x,y) ergibt sich dabei aus den gewichteten Werten der ihn umgebenden Pixel. Ein Beispiel für eine solche Maske ist

\begin{pmatrix} 1 & 2 & 1 \\ 2 & 4 & 2 \\ 1 & 2 & 1 \end{pmatrix}.

Je größer hierbei die Maske gewählt wird, desto robuster wird der Algorithmus gegenüber Rauschen, jedoch können durch zu starke Glättung feine Kanten verloren gehen.

Kantendetektion[Bearbeiten]

Partielle Ableitungen[Bearbeiten]

Ergebnis des Sobeloperators in X-Richtung
Ergebnis des Sobeloperators in Y-Richtung

Für den Canny-Algorithmus werden die partiellen Ableitungen der einzelnen Pixel in X-Richtung und in Y-Richtung benötigt. Die partiellen Ableitungen g_x bzw. g_y werden ermittelt, indem das vorprozessierte Bild mit Hilfe des Sobeloperators jeweils in X- bzw. Y-Richtung gefaltet wird. Somit werden vertikale bzw. horizontale Kanten betont. Auch beim Sobeloperator ergibt sich der neue Wert eines Pixels aus den gewichteten Werten der ihn umgebenden Pixel:

\begin{pmatrix} 1 & 0 & -1 \\ 2 & 0 & -2 \\ 1 & 0 & -1 \end{pmatrix} Sobeloperator in X-Richtung,
\begin{pmatrix} 1 & 2 & 1 \\ 0 & 0 & 0 \\ -1 & -2 & -1 \end{pmatrix} Sobeloperator in Y-Richtung.

Nach jeweiliger Anwendung der beiden Sobeloperatoren auf das vorprozessierte Bild ergeben sich zwei neue Bilder, die partiellen Ableitungen.

Kantenrichtung[Bearbeiten]

Errechneter Anstieg potentieller Kanten im jeweiligen Punkt

Mithilfe der beiden ermittelten partiellen Ableitungen lässt sich die Richtung \theta einer potentiellen Kante durch ein Pixel mittels

\theta = \operatorname{atan2}(g_y,g_x)

errechnen, wobei atan2 hier der sog. „Arkustangens mit zwei Argumenten“ ist.

Da ein Pixel jedoch nur 8 Nachbarn hat, werden die Kantenrichtungen gerundet auf 0°, 45°, 90° und 135°.

Absolute Kantenstärke[Bearbeiten]

Im dritten Schritt wird ein Bild der absoluten Kantenstärken berechnet. Dabei wird der Wert eines einzelnen Pixels aus dem euklidischen Betrag der beiden partiellen Ableitungen gebildet.

G(x,y) = \sqrt{g_x(x,y)^2 + g_y(x,y)^2}

In der Praxis wird zur Effizienzsteigerung oftmals eine Approximation verwendet:

G(x,y) = \left| g_x(x,y) \right|  + \left| g_y(x,y) \right|

Non-maximum suppression[Bearbeiten]

Verbleibende Pixel (lokale Maxima)

Um sicherzustellen, dass eine Kante nicht mehr als ein Pixel breit ist, sollen im folgenden Schritt einzig die Maxima entlang einer Kante erhalten bleiben. Dafür wird vom Bild mit den absoluten Kantenstärken ausgegangen und für jedes Pixel die Werte G(x,y) mit den beiden Pixeln rechts und links neben der Kante (oder entlang des Gradienten) verglichen. Ist einer der Werte größer, wird der Grauwert auf Null gesetzt. Diese Technik wird non-maximum suppression (NMS) genannt.

Hysterese[Bearbeiten]

Ergebnis der Kantenextraktion

Abschließend wird noch festgestellt, 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 T_1 < T_2. Man scannt das Bild durch, bis ein Pixel gefunden wird, dessen Stärke größer T_2 ist. Dieser Kante folgt man dann beidseitig. Alle Pixel entlang dieser Kante mit Stärke größer T_1 werden als Kantenelement markiert.

Nach diesem letzten Schritt ist der Algorithmus beendet und liefert eine Menge von Punkten, die bei geeigneter Wahl der Schwellwerte die im Ausgangsbild vorhandenen Kanten aufzeigen.

Verwendung[Bearbeiten]

Die durch den Algorithmus erhaltene Menge von Kantenpunkten kann auf viele verschiedene 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).

Literatur[Bearbeiten]

  • An improved CANNY edge detection algorithm von Bing Wang, Department of Electric and Information Engineering Changsha University of Science and Technology Changsha, Hunan, China, 2009
  • DOW-Canny: An Improvised Version Of Canny Edge Detector, von Ravi Kumar Dalal, Rahul Gupta, Pulkit Wadhwa und Anand Gupta, Neta Subhas Institute of Technology, Neu Delhi, Indien, 2011

Weblinks[Bearbeiten]

 Commons: Edge detection – Sammlung von Bildern, Videos und Audiodateien

Einzelnachweise[Bearbeiten]

  1. [1] (PDF; 7,3 MB) John Canny: A Computational Approach to Edge Detection, 1986 PAMI