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 (Bildglättung)[Bearbeiten | Quelltext 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 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 ergibt sich dabei aus den gewichteten Werten der ihn umgebenden Pixel. Ein Beispiel für eine solche Maske ist

.

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 | Quelltext bearbeiten]

Partielle Ableitungen[Bearbeiten | Quelltext bearbeiten]

Ergebnis des Sobeloperators in -Richtung
Ergebnis des Sobeloperators in -Richtung

Für den Canny-Algorithmus werden die partiellen Ableitungen der einzelnen Pixel in -Richtung und in -Richtung benötigt. Die partiellen Ableitungen bzw. werden ermittelt, indem das vorprozessierte Bild mit Hilfe des Sobeloperators jeweils in - bzw. -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:

Sobeloperator in -Richtung,
Sobeloperator in -Richtung.

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

Es kann auch statt dem Sobel-Operator und Vorprozess direkt mit den 1. Ableitungen (In x- und y-Richtung) des Gauß-Kerns gefiltert werden. Dies folgt aus der Assoziativität von linearen Filtern und daraus, dass die Ableitung sich als Filter darstellen lässt. So wird quasi geglättet und abgeleitet in einem Durchlauf. Canny hat gezeigt, dass dieser Ansatz die Signal to Noise Ratio optimiert.

Kantenrichtung[Bearbeiten | Quelltext bearbeiten]

Errechneter Anstieg bzw. Winkel potentieller Kanten im jeweiligen Punkt

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

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 | Quelltext 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.

In der Praxis wird zur Effizienzsteigerung oftmals eine Approximation verwendet:

Non-maximum suppression[Bearbeiten | Quelltext 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 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. Man kann sich das so vorstellen, dass der Algorithmus auf dem „Grat“ eines „Bergrückens“ entlangwandert und alle Bildpunkte zu Null setzt, die nicht zum Grat gehören. Diese Technik wird non-maximum suppression (NMS) genannt.

Hysterese[Bearbeiten | Quelltext 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 . Man scannt das Bild durch, bis ein Pixel gefunden wird, dessen Stärke größer ist. Dieser Kante folgt man dann beidseitig. Alle Pixel entlang dieser Kante mit Stärke größer 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 | Quelltext 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 | Quelltext 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
  • DGW-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 | Quelltext bearbeiten]

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

Einzelnachweise[Bearbeiten | Quelltext bearbeiten]

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