Kantendetektion

Kantenfindung

Originalbild

Mithilfe eines Sobel-Operators erstelltes Kantenbild

Die Kantendetektion oder Kantenextraktion ist Teil einer Segmentierung von Elementen in der Bildverarbeitung. Sie versucht, flächige Bereiche in einem digitalen Bild voneinander zu trennen, wenn sie sich entlang gerader oder gekrümmter Linien ausreichend in Farb- oder Grauwert, Helligkeit oder Textur unterscheiden. Spezielle Kantenoperatoren sollen die Übergänge zwischen diesen Bereichen erkennen und als Kanten markieren. Zugleich soll aber ein einzelner, homogener Bereich als solcher erkannt werden und von einem guten Kantendetektor nicht durch eine Kante in zwei Flächen geteilt werden.

Eine Hauptschwierigkeit der Kantendetektion, insbesondere bei dreidimensionalen Objekten, ist die Unterscheidung von Reflexionskanten, die auf Eigenschaften des Objektes beruhen, und Beleuchtungskanten, die auf Eigenschaften der Beleuchtung beruhen (z. B. Schatten, Lichtkegel).

Die Kantendetektion wird u. a. im Computer Vision, in der Photogrammetrie und der Kartografie eingesetzt, um z. B. aus Luftbildern genaue Objekt- oder Geländekanten zu detektieren.

Definition Kante

Unter einer Kante versteht man eine Kurve ${\vec {g}}(t)$, entlang derer der Gradient des Bildes $f$ immer in Normalenrichtung zeigt (das heißt eine Isolinie):

$f({\vec {g}}(t))\implies {\frac {df({\vec {g}}(t))}{dt}}=\nabla f|_{{\vec {g}}(t)}\cdot {\frac {\partial {\vec {g}}}{\partial t}}=0$

Probleme mit dieser Definition

Bei der der obigen Definition der Kante mit Hilfe des Gradienten ${\vec {g}}(t)$ von der Helligkeit $f$ treten folgende Probleme auf:

1. Wenn zwei benachbarte Teilmengen eines Bildes unterschiedliche Farben, aber die gleiche Helligkeit haben, dann ist der Gradient der Helligkeit gleich Null, und es wird keine Kante entdeckt.
2. Die Kantendetektion wird am Computer mittels Bildverarbeitung gemacht. Das Bild im Computer ist ein zwei-dimensionales Feld mit ganzzahligen Elementen jedoch keine stetige Funktion, weswegen man keine Ableitungen berechnen kann. Daher muss der Gradient durch zwei partielle Differenzen (jeweils in $x$- und $y$-Richtung) ersetzt werden. Dies gilt zunächst einmal nur für einen Farbkanal (sogenanntes Grauwertbild). In einem Farbbild gibt es jedoch mehrere Gradienten, jeweils einen für die Farbkanäle Rot, Grün und Blau.
3. Bei einer ein Pixel breiten farbigen Linie auf einem Hintergrund von einer anderen Farbe sollen zwei Kanten auf beiden Seiten der Linie entdeckt werden können. Zur Unterscheidung beider Seiten sollen die Differenzen gegenüber liegender Seiten unterschiedliche Vorzeichen haben. Hingegen soll bei einer drei Pixel breiten Rampe nur eine Kante entdeckt werden, d. h., die Differenzen sollen gleiche Vorzeichen haben. Dieses Vorzeichen kann nicht das Vorzeichen der Differenz der Helligkeiten sein, weil bei zwei benachbarten Teilmengen mit unterschiedlichen Farben und gleichen Helligkeiten die Differenz der Helligkeiten gleich Null ist und kein Vorzeichen hat.
4. In der Literatur werden teilweise auch Gratlinien als Kanten bezeichnet, wo obige Definition nicht greifen würde.

Definition nach Kovalevsky

• Die Kante ist eine zusammenhängende Folge von kurzen, zwischen zwei benachbarten Pixeln liegenden Strecken, die als Cracks bezeichnet werden.
• Die entsprechenden Differenzen sollen zu einem Wert $\bigtriangleup Farbe$ zusammengeführt werden, zum Beispiel für zwei horizontal benachbarte Pixel als Summe der Beträge der Differenzen:
• $\bigtriangleup Farbe=\left\vert \bigtriangleup Rot\right\vert +\left\vert \bigtriangleup Gruen\right\vert +\left\vert \bigtriangleup Blau\right\vert$.
• Die resultierende Differenz $\bigtriangleup Farbe$ soll größer als ein vorgegebener Schwellwert sein.
• Das Vorzeichen dieser Differenz im Fall eines Farbbildes ist gleich dem Vorzeichen der Differenz der Intensitäten der grünen Farbkanäle, falls diese Differenz ungleich Null ist. Sonst soll es die Differenz der Intensitäten der roten Farbkanäle sein, falls diese Differenz ungleich Null ist. Wenn beide Differenzen, die grüne und die rote gleich Null sind, dann soll es das Vorzeichen der blauen Differenz sein. Diese kann nicht gleich Null sein, weil die Summe der drei Differenzen größer als die Schwelle ist.
• Ein Crack $C$ gehört zur Kante, wenn der Betrag der Differenz $\bigtriangleup Farbe$ an diesem Crack größer als die Schwelle ist, und die Vorzeichen an N mit $C$ benachbarten parallelen Cracks gleich sind. Da eine Kante eine gerade Strecke ist, ist es von Vorteil, wenn man nur einen Crack bestimmt, welcher sich von den anderen Cracks hervorhebt. Dieser Crack repräsentiert dann die gesamte Kante. Um diesen zu identifizieren, vergleicht man alle N mit $C$ benachbarten parallelen Cracks und der Crack mit der größten Differenz ist der repräsentative Crack für diese Kante.

Beispiel:

Diese Bedingungen können zum Beispiel so sein:

Wenn N gleich 2 ist, die Vorzeichen dieser zwei Differenzen gleich dem Vorzeichen der Differenz von $C$ sind und der Betrag der Differenz von $C$ größer als die Beträge der beiden anderen Differenzen ist, dann gehört $C$ zur Kante.

Man kann ähnliche Bedingungen für den Fall N > 2 aufstellen. Diese Bedingungen werden so gewählt, dass unter den N mit $C$ benachbarten Cracks mit gleichen Vorzeichen der Differenzen nur ein Crack als Kante gewählt wird.

Funktionsweise

Ein Kantendetektor berechnet in der Regel den Farbwertgradienten an jedem einzelnen Pixel eines Bildes durch Untersuchung eines den Punkt umgebenden Bereiches. Dieser Vorgang erfolgt durch diskrete Faltung des Bildes mit einer Faltungsmatrix, dem Kantenoperator. Letzterer definiert dabei die Größe des zu untersuchenden Umfeldes und mit welcher Gewichtung dessen einzelne Pixel in die Berechnung eingehen. Der Kantenoperator ermittelt für das zentrale Pixel aus der Umgebung quasi einen mittleren Wert für den Gradienten. Führt man diese Operation für alle Pixel im Bild durch, so kann man aus der resultierenden Matrix der Gradienten ein neues Bild zusammensetzen, das Kantenbild genannt wird. Auf ihm heben sich die Kanten zwischen homogenen Bereichen ab, da an diesen Stellen ein vergleichsweise großer Gradient der Farbwerte vorliegt.

Wendet man den Kantenoperator auf das Ergebnisbild an, so kann man quasi die zweite Ableitung bilden, d. h., es werden die Änderungen des Helligkeits-Gradienten sichtbar. Die Kanten treten in der zweiten Ableitung meist am deutlichsten hervor. Feine Kanten können hierbei jedoch untergehen und bleiben unentdeckt.

Der größte Unterschied verschiedener Kantendetektoren besteht im Allgemeinen im verwendeten Kantenoperator.

Für eine korrekte Kantendetektion sind in der Regel vier Schritte notwendig:

1. Glätten: Unterdrücke so viel Rauschen wie möglich, ohne die echten Kanten zu zerstören.
2. Verbesserung: Wende einen Filter an, um die Qualität der Bildränder zu verbessern.
3. Erkennung: Bestimme, welche Pixel als Rauschen verworfen werden sollen und welche beibehalten werden sollte. Normalerweise liefert die Schwellenwertbildung das Kriterium, das für die Erkennung verwendet wird.
4. Lokalisierung: Bestimme die genaue Position einer Kante. Für einige Anwendungen kann es erforderlich sein, die Position einer Kante genauer als den Abstand zwischen den Pixeln zu bestimmen. Kantenverdünnung und Verknüpfung sind in der Regel in diesem Schritt erforderlich.

Berechnungen

Kantendetektion mit Ableitungen

Ein digitales Bild ist eine zweidimensionale Funktion. Daher werden Operatoren, die Kanten beschreiben, mit partiellen Ableitungen ausgedrückt. Punkte, die an einer Kante liegen, können erkannt werden durch:

• Erfassen lokaler Maxima oder Minima der ersten Ableitung
• Erfassen der Nullstellen der zweiten Ableitung

Weil ein digitales Bild keine kontinuierliche Funktion ist, sondern eine diskrete Funktion von neben einander liegenden Pixeln, kann man die partiellen Ableitungen nicht direkt bilden. Stattdessen muss man, um die Ableitungen von Farbwerten zu berechnen, sie mit endlichen Differenzen annähern:

1. Ableitung

$f'(x)=\lim _{h\to 0}{\frac {f(x+h)-f(x)}{h}}\approx f(x+1)-f(x)$

2. Ableitung

$f''(x)=\lim _{h\to 0}{\frac {f'(x+h)-f'(x)}{h}}\approx f'(x+1)-f'(x)\approx f(x+2)-2\cdot f(x+1)+f(x)$

Das kann man auf zwei Dimensionen verallgemeinern:

${\frac {\partial f}{\partial x}}=\lim _{h_{x}\to 0}{\frac {f(x+h_{x},y)-f(x,y)}{h_{x}}}\approx f(x+1,y)-f(x,y)$

${\frac {\partial f}{\partial y}}=\lim _{h_{y}\to 0}{\frac {f(x,y+h_{y})-f(x,y)}{h_{y}}}\approx f(x,y+1)-f(x,y)$

Operatoren

Die bekanntesten Kantenoperatoren (auch Kantenfilter) sind:

• Sobel-Operator
• Scharr-Operator
• Laplace-Filter (siehe auch Laplace-Operator)
• Prewitt-Operator
• Roberts-Operator
• Kirsch-Operator
• Canny-Algorithmus
• Marr-Hildreth-Operator (auch Laplacian of Gaussian (LoG) oder Sombrerofilter)
• Kontrastverstärker
• Aktive Kontur (Snake)
• Extremalspannenfilter
• Gabor-Filter

• 
  Ein Schwarzweißfoto
• 
  Normalisierte Gradientengröße des Sobel-Operators
• 
  Normalisierter x-Gradient des Sobel-Operators
• 
  Normalisierter y-Gradient des Sobel-Operators
• 
  Normalisierte Gradientengröße des Scharr-Operators
• 
  Normalisierte Gradientengröße des Roberts-Operators
• 
  Normalisierte Gradientengröße des Prewitt-Operators

Menschliches Auge

Für den Menschen ist Kantendetektion eine wesentliche Voraussetzung zur visuellen Objekterkennung. Sein Sehapparat leistet diese Aufgabe hauptsächlich mit der lateralen Hemmung. Dadurch werden sogar feinste Linienstrukturen aus größerer Distanz erkennbar, etwa dünne Drähte oder ferne Wegverläufe. Allerdings sind auch optische Täuschungen möglich, etwa teilweise bei den sog. Marskanälen oder den Machschen Streifen.