Canny-Algorithmus

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

Funktionsweise

Beim Canny-Algorithmus werden nur zwei Schwellenwerte für alle Bilder verwendet. Um eine bessere Kantenabbildung zu erhalten, wird der Kantendetektor auf jeden Block eines Bildes angewendet. Die Hauptkriterien für die Kantendetektion sind folgende:

• Niedrige Fehlerrate: Es ist wichtig, dass die im Bild auftretenden Kanten nicht übersehen werden und keine falschen Kanten erkannt werden. Dieses Kriterium wird mathematisch mit folgender Formel dargestellt:

${\frac {A\cdot \left|\int \limits _{-W}^{0}f(x)\ \mathrm {d} x\right|}{n_{0}\cdot \left|\int \limits _{-W}^{0}f^{2}(x)\ \mathrm {d} x\right|}}$

• Gute Lokalisierung: Der Abstand zwischen den vom Detektor gefundenen Pixeln und der tatsächlichen Kante muss minimal sein. Die Formel für dieses Kriterium lautet:

${\frac {A\cdot \left|f'(0)\right|}{n_{0}\cdot \left|\int \limits _{-W}^{0}f^{2}(x)\ \mathrm {d} x\right|}}$

• Einzelantwort: Jede Kante wird nur einmal erkannt. Die Formel für dieses Kriterium lautet:

$\pi \cdot \left({\frac {\int \limits _{-\infty }^{\infty }f'^{2}(x)\ \mathrm {d} x}{\int \limits _{-\infty }^{\infty }f''^{2}(x)\ \mathrm {d} x}}\right)^{\frac {1}{2}}$

Der Algorithmus besteht hauptsächlich aus fünf Schritten:

1. Der horizontale $\mathbf {G} _{x}$ und der vertikale $\mathbf {G} _{y}$ Gradient jedes Pixels werden berechnet.
2. Unter Verwendung von $\mathbf {G} _{x}$ und $\mathbf {G} _{y}$ werden die Größe und die Richtung jedes Pixels berechnet.
3. Alle Nichtmaxima werden als Null gezählt, d. h. die Nichtmaxima werden unterdrückt. Daher wird dieser Schritt als nicht-maximale Unterdrückung bezeichnet.
4. Die hohen und niedrigen Schwellenwerte werden unter Verwendung des Histogramms der Gradientengröße des Bildes gemessen.
5. Um die richtige Kantenabbildung zu erhalten, wird ein Hysterese-Schwellenwert verwendet, der die schwachen und starken Kanten verbindet. Die schwachen Kanten werden genau dann berücksichtigt, wenn sie mit einer der starken Kanten verbunden sind oder aus der Kantenabbildung entfernt werden. Die starke Kante ist diejenige, deren Pixel größer als die hohe Schwelle ist, und die schwache Kante ist eine, deren Pixelwert zwischen der hohen und der niedrigen Schwelle liegt.

Daraufhin wird dann die Pixelstärke und Ausrichtung dieses Gradienten berechnet. Im nächsten Schritt werden alle Maxima gefunden, die das Bild enthält. Anschließend werden sie beibehalten und die anderen Nicht-Maxima entfernt. Der Prozess wird als nicht maximale Unterdrückung bezeichnet. In Schritt 4 wird das Pixel abhängig von den eingestellten hohen und niedrigen Schwellenwerten entweder als Kante oder als Nichtkante dargestellt. Wenn der Pixelwert zwischen dem hohen und dem niedrigen Schwellenwert liegt, ist dies eine schwache Kante. Um Kanten im Bild zu erkennen, werden zwei Schwellenwerte als hoch und niedrig betrachtet. Dann wird schließlich die Hystereseschwelle angewendet, die eine Entscheidung über die zu berücksichtigende oder verbleibende erkannte schwache Kante treffen kann. Das Pixel wird mit den benachbarten Pixeln verglichen. Wenn die schwache Kante mit dieser starken Kante verbunden ist, wird sie als Kante betrachtet, andernfalls wird sie aus der Kantenabbildung entfernt. Der Schwellenwert ist für alle Bilder gleich. Aus diesem Grund gibt es einige Einschränkungen, wenn es auf die Blockebene des Bildes angewendet wird. Der Algorithmus erkennt einerseits falsche Kanten im glatten Bereich und übersieht anderseits einige signifikante Kanten. Um die obige Einschränkung zu überwinden, werden ein adaptiver Schwellenwertblock und die Blockklassifizierungsblöcke zusammen mit den obigen Blöcken hinzugefügt. Und der Schwellenwert wird, basierend auf dem Block, unterschiedlich eingestellt. Somit wird die Leistung des Canny-Algorithmus auf Blockebene verbessert.

Bildglättung

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 $g(x,y)$ (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. 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 auf Bild damit ein Tiefpassfilter angewendet, sodass das vornehmlich im hohen Frequenzbereich vorkommende, weiße Rauschen gedämpft oder eliminiert wird, bevor Kanten gefunden werden. Ein neuer Grauwert eines Pixels $g_{n}(x,y)$ ergibt sich dabei als Faltungsantwort aus den gewichteten Werten des eigenen und der ihn umgebenden Pixel. Ein Beispiel für eine solche Faltungsmatrix ist

$g_{n}(x,y)={\frac {1}{4}}{\begin{bmatrix}1\\2\\1\end{bmatrix}}\cdot {\frac {1}{4}}{\begin{bmatrix}1&2&1\end{bmatrix}}={\frac {1}{16}}{\begin{pmatrix}1&2&1\\2&4&2\\1&2&1\end{pmatrix}}$.

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

Partielle Ableitungen

Ergebnis des Sobel-Operators in $X$-Richtung

Ergebnis des Sobel-Operators 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 vorverarbeitete Bild mit Hilfe des Sobeloperators jeweils in $X$- bzw. $Y$-Richtung gefaltet wird. Somit werden vertikale bzw. horizontale Kanten betont. Auch beim Sobel-Operator 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 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 in einem einzigen Durchlauf geglättet und abgeleitet. Canny hat gezeigt, dass dieser Ansatz den Signal-Rauschabstand optimiert.

Kantenrichtung

Errechneter Anstieg bzw. Winkel potentieller Kanten im jeweiligen Punkt

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

$\theta (x,y)=\operatorname {arctan2} {\bigl (}g_{x}(x,y),g_{y}(x,y){\bigr )}$

errechnen, wobei arctan2 der sog. „Arcustangens mit zwei Argumenten“ ist.

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

Absolute Kantenstärke

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

• 
  Errechneter Anstieg potentieller Kanten im jeweiligen Punkt mit Darstellung der Kantenstärke
• 
  Errechneter Anstieg (gerundet)
• 
  Errechneter Anstieg (gerundet) mit Darstellung der Kantenstärke

Non-maximum suppression

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

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

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

Der Algorithmus ist in den freien Bildverarbeitungsbibliotheken Scikit-image und OpenCV implementiert.

Literatur

• 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

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