Canny-Algorithmus

Der Canny-Algorithmus, benannt nach John 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.

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.

Mehrdimensionale Normalverteilung

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 könnte sein:

$\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.

Ausgangsbild für den Algorithmus

Anschließend werden die partiellen Ableitungen 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 die partiellen Ableitung in X-Richtung g_x und die partielle Ableitung in Y-Richtung g_y benötigt werden, ergeben sich also nach Anwendung des Sobeloperators 2 neue Bilder.

$\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

Ergebnis des Sobeloperators in X-Richtung

Ergebnis des Sobeloperators in Y-Richtung

Mithilfe der beiden so ermittelten partiellen Ableitungen lässt sich der Anstieg einer potentiellen Kante durch einen Pixel leicht errechnen. Es gilt:

$\mbox{Anstieg} = \begin{cases} \arctan(\frac {g_y}{g_x}), & \mbox{falls }g_x\ne 0 \\ 0^\circ, & \mbox{falls }g_x=0, g_y=0\\ 90^\circ, & \mbox{falls }g_x=0, g_y\ne 0 \end{cases}$.

Da ein Pixel jedoch nur 8 Nachbarn hat, ergeben sich lokal lediglich 4 mögliche Kantenrichtungen: 0°, 45°, 90° und 135°. Die soeben errechneten Anstiege werden also auf einen dieser Werte gerundet.

Errechneter Anstieg potentieller Kanten im jeweiligen Punkt

Errechneter Anstieg potentieller Kanten im jeweiligen Punkt mit Darstellung der Kantenstärke (s.u.)

Als drittes muss noch ein Bild der absoluten Kantenstärken berechnet werden. 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 Steigerung der Effizienz oftmals eine Approximation verwendet:

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

Um sicherzustellen, dass eine Kante nicht mehr als einen 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 jeden Pixel die Werte G(x,y) mit denjenigen seiner 8 Nachbarn verglichen. Keiner der benachbarten Pixel darf einen höheren Wert aufweisen, es sei denn, der betreffende Nachbarspixel liegt entlang der berechneten Kantenrichtung. Ist dies nicht gegeben, wird der Grauwert auf Null gesetzt. Diese Technik wird "non-maximum suppression" (NMS) genannt.

Errechneter Anstieg (gerundet)

Errechneter Anstieg (gerundet) mit Darstellung der Kantenstärke

Verbleibende Pixel (lokale Maxima)

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 T₁ < T₂. Man scannt das Bild durch, bis ein Pixel gefunden wird, dessen Stärke größer T₂ ist. Dieser Kante folgt man dann beidseitig. Alle Pixel entlang dieser Kante mit Stärke größer T₁ 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.

Ergebnis der Kantenextraktion

Diese Menge von Punkten 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).

Einzelnachweise

1. ↑ [1] John Canny: A Computational Approach to Edge Detection, 1986 PAMI