Canny-Algorithmus

aus Wikipedia, der freien Enzyklopädie
Zur Navigation springen Zur Suche springen
Dieser Artikel oder nachfolgende Abschnitt ist nicht hinreichend mit Belegen (beispielsweise Einzelnachweisen) ausgestattet. Angaben ohne ausreichenden Beleg könnten daher möglicherweise demnächst entfernt werden. Bitte hilf Wikipedia, indem du die Angaben recherchierst und gute Belege einfügst.
Dieser Artikel oder Abschnitt bedarf einer Überarbeitung. Näheres sollte auf der Diskussionsseite angegeben sein. Bitte 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.

Vorverarbeitung (Bildglättung)[Bearbeiten | Quelltext bearbeiten]

Ausgangsbild für den Algorithmus

Der Canny-Algorithmus arbeitet auf zweidimensionalen Intensitätswerten. Er kann also auf Grauwertbildern oder einzelnen Farbkanälen Kanten detektieren, enthält aber keine Vorschrift, wie mehrere monochrome Kanäle zusammengeführt würden. In der Regel werden Farbbilder vor einer Kantenerkennung in ein gemeinsames Grauwertbild überführt.

In Grauwertbildern sind Kanten durch große Helligkeitsschwankungen zwischen zwei benachbarten Pixeln charakterisiert. Sie können somit für ein Ausgangsbild als eine Unstetigkeit der Grauwertfunktion (nicht ableitbar) bzw. – in der üblichen diskretisierten Variante – als Sprungfunktion (ableitbar) aufgefasst werden. Canny ging beim Kantendetektorentwurf von einem Nutzsignal (Bild) aus, das mit weißem Rauschen überlagert ist.[1] Diese Annahme ist durchaus zweckdienlich, da thermisches Rauschen in Elektronikbausteinen, die bei der Bildaufnahme Verwendung finden, eine vergleichbare Verteilung aufweist. Es ist folglich nicht einwandfrei feststellbar, ob eine Kante aus dem eigentlichen Signal stammt oder durch das überlagernde Rauschen verursacht ist. Dem gaußverteilten weißen Rauschen setzt der Canny-Algorithmus daher eine auf der Glockenkurve basierende Glättungsfunktion entgegen, bspw. in Form einer Faltung mit einem Binomialfilter. In der Vorverarbeitung wird das Bild damit tiefgepasst, sodass das vornehmlich im hohen Frequenzbereich vorkommende weiße Rauschen gedämpft oder eliminiert wird, bevor Kanten gefunden werden. Ein neuer Grauwert eines Pixels ergibt sich dabei als Faltungsantwort aus den gewichteten Werten des eigenen und der ihn umgebenden Pixel. Ein Beispiel für eine solche Faltungsmatrix ist

.

Das heißt, die Faltungsmatrix ist separierbar. Die Vektoren, die dyadisch zur Matrix verknüpft werden, entsprechen hierbei der n-ten Zeile eines pascalschen Dreiecks.

Eine größere Faltungsmatrix verstärkt den Tiefpasseffekt und dadurch die Robustheit gegenüber Rauschen. Zugleich verschwinden jedoch feine Kanten.

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 vorverarbeitete 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 vorverarbeitete Bild ergeben sich zwei neue Bilder, die partiellen Ableitungen.

Es kann auch statt des Sobel-Operators und der Vorverarbeitung 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).

Software[Bearbeiten | Quelltext bearbeiten]

Der Algorithmus ist in den freien Bildverarbeitungsbibliotheken Scikit-image[2] und OpenCV[3] implementiert.

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. a b [1] (PDF; 7,3 MB) John Canny: A Computational Approach to Edge Detection, 1986 PAMI
  2. Canny edge detector — skimage docs. Abgerufen am 13. September 2018 (englisch).
  3. OpenCV: Canny Edge Detector. Abgerufen am 16. September 2018 (englisch).