Kantenerkennung In Bildern

Leopold-Franzens-Universit¨ at Innsbruck Institut f¨ ur Informatik Gruppe Infmath Imaging

Bakkalaureatsarbeit

Kantenerkennung in Bildern Thomas Zangerl Betreuer: Dr. Andreas Obereder

Pfons, den 3. Juni 2007

Zusammenfassung Kantenerkennung ist einer der wichtigsten Schritte im menschlichen und automatisierten Erkennen von Bildinhalten. Es existiert eine dementsprechend fast u altigend große Anzahl an Herangehensweisen und Al¨berw¨ gorithmen. Die meisten dieser Ann¨ aherungen an das Thema fußen auf der ersten und/oder zweiten Ableitung der Bildintensit¨ atswerte, kombiniert mit allgemein anerkannten Schritten zur Verbesserung der Ergebnisse, wie Nonmaxima-Unterdr¨ uckung oder Hysterese. Diese Arbeit versucht einen Querschnitt durch einen Großteil k¨ urzlich vorgestellter und allgemein bekannter Verfahren zu geben und konzentriert sich ferner auf alternative Zug¨ ange, wie sie von Haralick in [1] und Smith und Brady in [2] vorgestellt wurden. Abstract Edge detection is one of the most important steps in human and machine-driven low level image processing. Accordingly, there is an amazing number of algorithms and problem solution proposals. Most of these approaches deal with the first and/or second derivative of the image pixel intensity values, combined with steps like non-maximal suppression or hysteresis, which are generally considered useful in improving the results. This paper gives a synopsis over both methods introduced lately and generally known, while furtherly concentrating on alternative approaches, as introduced by Haralick in [1] and Smith and Brady in [2].

1

Inhaltsverzeichnis ¨ 1 Uberblick u ¨ ber aktuelle Kantenerkennungsverfahren 1.1

1.2

1.3

1.4

1.5

4

Klassische gradientenbasierte Kantendetektoren . . . . . . . . . .

4

1.1.1

Sobel-Operator . . . . . . . . . . . . . . . . . . . . . . . .

4

1.1.2

Prewitt-Operator . . . . . . . . . . . . . . . . . . . . . . .

5

1.1.3

Roberts-Operator . . . . . . . . . . . . . . . . . . . . . . .

5

1.1.4

Kompass-Operatoren . . . . . . . . . . . . . . . . . . . . .

5

Detektoren auf Basis der zweiten Ableitung . . . . . . . . . . . .

6

1.2.1

Laplacian of Gaussian (LoG) . . . . . . . . . . . . . . . .

6

1.2.2

Difference of Gaussians (DoG) . . . . . . . . . . . . . . .

9

Kantenerkennung nach dem Canny-Muster . . . . . . . . . . . .

10

1.3.1

Canny-Filter . . . . . . . . . . . . . . . . . . . . . . . . .

10

1.3.2

Rothwell . . . . . . . . . . . . . . . . . . . . . . . . . . . .

11

1.3.3

Edison . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

12

1.3.4

Iverson-Zucker . . . . . . . . . . . . . . . . . . . . . . . .

14

Kantenerkennung mithilfe neuronaler Netze . . . . . . . . . . . .

16

1.4.1

. . . . . . . . . . . . . . . . . . . . . . . . . . . .

16

Kantenerkennung mittels anisotroper Diffusion . . . . . . . . . .

17

1.5.1

17

Bezdek

Black . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2 Kantenerkennung abseits des Mainstreams“ 20 ” 2.1 Parametrische Kantenmodelle . . . . . . . . . . . . . . . . . . . . 20

2.2

2.1.1

Sloped Facet Models . . . . . . . . . . . . . . . . . . . . .

20

2.1.2

Integrierter Gradientendetektor . . . . . . . . . . . . . . .

21

2.1.3

Nulldurchg¨ ange der 2. Ableitung mit Cubic Facet Models

24

Kantenerkennung ohne Ableitung . . . . . . . . . . . . . . . . . .

25

2.2.1

25

SUSAN . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3 Zusammenfassung und Ausblick

28

A Qualitativer und quantitativer Vergleich von Kantendetektoren 30

2

A.1 Pratt-Metrik . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

30

A.2 Rosenfeld-Metrik . . . . . . . . . . . . . . . . . . . . . . . . . . .

30

B Methoden zur Konturaufbesserung

31

B.1 Nonmaxima-Unterdr¨ uckung . . . . . . . . . . . . . . . . . . . . .

31

B.2 Hysterese . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

32

B.3 Thinning-Verfahren . . . . . . . . . . . . . . . . . . . . . . . . . .

32

C Interpolation durch Polynome

33

3

¨ Uberblick u ¨ ber aktuelle Kantenerkennungsverfahren

1

1.1 1.1.1

Klassische gradientenbasierte Kantendetektoren Sobel-Operator

Der Sobel-Operator geh¨ ort gemeinsam mit dem Prewitt-Operator, dem RobertsCross-Operator und den Kompass-Operatoren zu den einfachsten, ¨altesten und wohl auch, gemessen an den meisten Metriken, qualitativ schw¨achsten Algorithmen. Dennoch wird er in der Realit¨at h¨aufig eingesetzt, was aber auch mit seiner Implementierungseinfachheit zu tun haben d¨ urfte. Prinzipiell bildet das Verfahren nur die Richtungsableitungen in x und y Richtung mit Hilfe einer Faltungsmatrix und errechnet sich so eine gesch¨atzte Kantenst¨arke. Die Faltungsmatrizen, die Ann¨ aherungen an die jeweiligen Richtungsableitungen darstellen, sehen dann so aus: 

−1 HxS =  −2 −1

0 0 0

  1 −1 2  HyS =  0 1 1

 −2 −1 0 0  2 1

Die Kantenst¨ arke kann durch die L2 -Norm der Faltungen berechnet werden: q E (u, v ) = (Dx (u, v))2 + (Dy (u, v))2 wobei D(u, v) den Wert des Pixels mit Index uv nach der Faltung mit den oben vorgestellten Matrizen darstellt. Oft beschr¨ankt man sich darauf, nur die Summe der Betr¨ age der Ableitungen als Ann¨aherung an die Kantenst¨arke zu betrachten. Oftmals erweist es sich als n¨ utzlich, wenn man Informationen u ¨ber die gesch¨ atzte Kantenrichtung in einem Kantenpixelkandidaten gewinnen kann, so zum Beispiel in Schritten die zur Konturaufbesserung verwendet werden (siehe B.1). Ein Vorteil des Sobel-Verfahrens ist, dass diese leicht mit folgender Formel zu gewinnen sind:   Dy (u, v) −1 φ(u, v ) = tan Dx (u, v) Der Sobel Operator ist zwar recht einfach zu implementieren und relativ schnell, hat aber einige Nachteile: • Schmale Kanten werden durch die Gl¨attung oft verbreitert. • Der Algorithmus ist relativ rauschanf¨allig, da er vor allem hochfrequente Anteile verst¨ arkt. • Kanten, deren Kontrast¨anderungen u ¨ber einen zu großen Bereich verlaufen ¨ ( feine“ Uberg¨ ange), um in einer 3 x 3 Umgebung ersichtlich zu sein, ” 4

werden von dem Filter nicht erkannt. Allerdings kann dieser Vorwurf jedem Filter, das mit kleinen Masken arbeitet, gemacht werden und ist somit eher Teil eines allgemeinen Kompromisses zwischen Maskengr¨oße und Erkennungsleistung. Auch wird man leicht argumentieren k¨onnen, dass prozentuell gesehen ein eher geringer Anteil der Kanten solche Eigenschaften aufweist. • Der Operator ist eigentlich obsolet und nur aufgrund seiner Einfachheit beliebt. Will man auf ein gut dokumentiertes Standardverfahren zur¨ uckgreifen, so w¨ are der Canny-Algorithmus auf jeden Fall zu bevorzugen.

1.1.2

Prewitt-Operator

Der Prewitt-Operator verwendet exakt die gleiche Technik, wie der SobelOperator, der einzige Unterschied sind die Masken, die als Ann¨aherung an die Berechung des Gradienten der Bildfunktion verwendet werden. Diese legen weniger Wert auf die zentrale Zeile bzw. Spalte und stellen, separiert dargestellt, eine einfache Gl¨ attung u ¨ber drei Zeilen mit anschließender Gradientenberechnung dar. Da der Prewitt-Operator gleich funktioniert, wie der Sobel-Operator, aber schlechtere Ergebnisse liefert, wird er in der Praxis praktisch nicht mehr eingesetzt. Hier sei er nur der Vollst¨ andigkeit halber erw¨ahnt.

1.1.3

Roberts-Operator

Dieser Operator gilt als einer der ¨altesten Kantenoperatoren u ¨berhaupt und verwendet lediglich 2x2 Filter, was angesichts heutiger Kantenerkennungsmasken als durchaus exotisch betrachtet werden darf. Die Filter sch¨ atzen den Gradienten in Richtung der Diagonalen - die Erkennungsleistung des Operators h¨alt dem Vergleich mit neueren und neuesten Techniken allerdings bei weitem nicht stand.

1.1.4

Kompass-Operatoren

Die Idee, die hinter der Schaffung von Kompass-Operatoren stand, war, dass viele Filter in ihrer Erkennungsleistung oft stark richtungsabh¨angig sind. Daher lag der Versuch, einen Satz engerer“ Filter zu verwenden, die daf¨ ur f¨ ur mehrere ” Richtungen ausgelegt sind, recht nahe. Die Faltungsmatrizen, die man verwenden soll, sind nicht vorgeschrieben; prinzipiell k¨ onnen beliebige zur Kantenerkennung geeignete Matrizen verwendet werden, die jeweils in 45◦ Winkeln gedreht werden. Ein Beispiel mit dem Sobel-Operator w¨ urde folgendermaßen aussehen: 

H0K

−1 =  −2 −1

0 0 0

  −2 1 2  H1K =  −1 1 0 5

 −1 0 0 1  1 2



H2K

−1 = 0 1

  −2 −1 0 0 0  H3K =  1 2 1 2

 −1 −2 0 −1  1 0

Eine angenehme Eigenschaft ist, dass die Filtermasken H4 bis H7 −H0 bis H3 entsprechen, denn so muss aufgrund der Linearit¨at der Faltung auch das gefilterte Bild zur Errechnung von D4 bis D7 nur mit -1 multipliziert werden. Bezeichnen D0 . . . D7 die einzelnen Filterergebnisse, dann ist die eigentliche Kantenst¨ arke E K definiert als die L8 -Norm der Faltungen: E K (u, v) = max(|D0 (u, v)|, |D1 (u, v)|, D2 (u, v)|, |D3 (u, v)|), Auch bei diesem Verfahren kann man sich die Kantenrichtung einfach errechnen; dargestellt durch das am st¨ arksten ansprechende Filter: π j 4 wobei j dem Di mit dem jeweils gr¨oßten Wert entspricht. Eine Eigenschaft, die sich bei Kompassoperatoren erstmals bemerken l¨asst, sich aber wie ein roter Faden durch zahlreiche Vorschl¨age, die zur Kantenerkennung gemacht werden, zieht, ist, dass sich ein theoretisch formulierbares Verbesserungspotenzial nicht unbedingt auf die Praxis auswirken muss. (Am st¨arksten uber all seinen sichtbar wird dies in [3], wo sich der Canny-Operator gegen¨ Weiterentwicklungen mit der besten Erkennungsleistung behauptet). So verf¨ ugen auch die Kompassoperatoren u uber ¨ber wenig reelle Vorteile gegen¨ dem Sobel-Operator: φK (u, v) =

• Ein nennenswerter Vorteil ist, dass ein Kompass-Operator aufgrund der besseren Abdeckung verschiedener Richtungen auf Kanten, die f¨ ur den reinen Sobel-Operator ung¨ unstig gelegen sind, besser reagiert. • Jedoch m¨ ussen hier vier Faltungsoperationen auf jeden Pixel angewandt werden, w¨ ahrend der z.B. der Sobel Operator mit zwei auskommt. • Kompass-Operatoren sind ebenfalls stark rauschanf¨allig. • Es ergeben sich oft nur f¨ ur klare, starke Linien eindeutige Muster. • Die Qualit¨ at des Ergebnisses des Operators ist oft abh¨angig von der Gr¨oße des Objekts bzw. der Abruptheit der Kante.

1.2 1.2.1

Detektoren auf Basis der zweiten Ableitung Laplacian of Gaussian (LoG)

Geschichtlich betrachtet sind Kantendetektoren auf Basis der zweiten Ableitung sozusagen die n¨ achste Evolutionsstufe nach den einfachen Gradientenfil6

tern und haben sich vor Cannys viel beachteter Arbeit sehr großer Popularit¨at erfreut. In [5] entwickeln Marr und Hildreth einen Operator, den sie auf die Sehvorg¨ ange des Menschen zur¨ uckf¨ uhren (es wurde allerdings gezeigt, dass die Technik nur ein Teil menschlicher Bilderkennung ist). Dieser Operator, der die zweite Ableitung einer Gauß-Funktion darstellt, wird meistens unter der aussagekr¨ aftigen Bezeichnung Laplacian of Gaussian angef¨ uhrt (allerdings sind manchmal auch die Bezeichnungen Marr-Hildreth-Operator und Mexican-Hat“ anzutreffen). ” Der Grundgedanke ist, dass die zweite Ableitung die lokale Kr¨ ummung einer Funktion misst und man deshalb die Nulldurchg¨ange der zweiten Ableitung als Kantenkriterium betrachten kann. Allerdings ist die zweite Ableitung stark anf¨ allig gegen¨ uber Bildrauschen, weshalb eine Gl¨attung des Bildes mit dem Gauß-Filter zur Rauschunterdr¨ uckung vorangehen sollte. Der Laplace-Operator, im folgenden L(x, y) genannt, ist als Kantendetektor isotrop (d.h. er arbeitet in allen Richtungen gleich gut) und stellt die zweite Richtungsableitung nach x und y eines Bildes I(x, y) dar: ∂2I ∂2I + 2 2 ∂x ∂y

L(x, y) =

Die Funktion ist prinzipiell als Faltungsmatrix approximierbar; es sollte aber vorher noch eine Gl¨ attung mit einer (gl¨ ucklicherweise ebenfalls isotropen) Gaußschen Normalverteilung erfolgen. Von diesem Zeitpunkt an G(x) genannt, errechnet sich deren Dichtefunktion folgendermaßen: G(x) = √

x2 1 e− 2σ2 2πσ

wobei σ die Standardabweichung darstellt und sich auf die Streuung der Gaußschen Glockenkurve auswirkt, und der Erwartungswert µ, der die Position gr¨oßter Dichte kennzeichnet, hier 0 ist. F¨ ur eine Gl¨ attung unseres Bildes ben¨otigen wir die Normalverteilung in zwei Dimensionen, deren Dichtefunktion G(x, y) sich als G(x, y) = √

x2 +y 2 1 e− 2σ2 2πσ 2

definiert. Die Idee ist (und hier unterst¨ utzt uns die Assoziativit¨at der Faltung), nur einen Operator zu verwenden, der Laplace-Operator und Gauß-Gl¨attung in sich vereint. Es reicht also, die zweite Ableitung in beiden Richtungen der 2DGaußfunktion zu verwenden. Dieser Operator sei hier f¨ ur eine Standardabweichung σ = 1, 4 veranschaulicht:

7

(a) Die 2D-Gaußfunktion mit σ = 1.4 und (b) Der Laplaceoperator auf die Gaußµ=0 funktion angewandt

Abbildung 1: Der Gaußoperator und dessen zweite Ableitung Wir wollen nun die Gaußsche Normalverteilung als Faltung auf die Pixel eines Bildes anwenden. Da die Normalverteilung zwar nie 0 ist, aber bereits drei Schritte vom Mittelpunkt entfernt nahe 0 ist, kann man die Funktion mit einer 5 × 5 Filtermaske approximieren, die einen gewichteten“ Durchschnitt eines ” Pixels mit seinen Nachbarpixeln bildet, wobei des gr¨oßte Gewicht nat¨ urlich auf dem zentralen Pixel liegt. Beschleunigen l¨ asst sich dieser Vorgang durch das Aufspalten der zweidimensionalen Gl¨ attung auf zwei 1D-Filtermasken. Als weiterer Vorteil erweist sich, dass die Frequenzkurve von Bildern selbst einer (halbierten) 1D-GaußschenNormalverteilung entspricht und man deshalb gute Kontrolle u ¨ber die verbleibenden Frequenzen hat. Aufgrund der bereits angesprochenen Assoziativit¨at der Faltung k¨onnen wir nun das Gauß-Filter mit dem Laplace-Filter falten und uns so Rechenzeit ersparen, da wir diesen Vorgang nur einmal durchf¨ uhren m¨ ussen und das Bild fortan mit dem vereinten“ Operator falten k¨onnen. ” Nach der Faltung bleibt uns folgende Funktion:   x2 + y 2 − x2 +y2 2 1 1 − e 2σ πσ 4 2σ 2 Diese Funktion kann z.B. durch folgende Filtermaske approximiert werden (Beispiel mit σ = 1.4): LoG(x, y) = −

             

0 0 3 2 2 2 3 0 0

0 2 3 5 5 5 3 2 0

3 3 5 3 0 0 5 3 3

2 2 2 3 5 5 5 3 3 0 3 5 −12 −23 −12 3 −23 −40 −23 0 −12 −23 −12 0 3 0 3 5 5 5 5 3 2 2 2 3 8

0 2 3 5 5 5 3 2 0

0 2 3 2 2 2 3 2 0

             

Eventuell sollte man auf das Ergebnis noch einen Schwellwertoperator anwenden, da sonst beliebig kleine Nulldurchg¨ange in die Bewertung miteinfließen und das Filter auch auf eventuell unerw¨ unscht schwache Kanten anspricht. Eine Bewertung von Laplacian of Gaussian: • Das Verfahren ist isotrop - es ist daher nur eine Maske notwendig... • ... die entsprechend groß sein muss, um die Funktion nicht abzuschneiden. • Es lassen sich eben wegen der Isotropie keine Informationen u ¨ber Kantenrichtung extrahieren. • Die Position der Kanten muss aufgrund der vorangehenden Gl¨attung mit dem Gauß-Filter nicht immer exakt sein. • Es bleiben False-Positives im Bild. • LoG erzeugt immer geschlossene Konturen - was nicht realistisch ist. • Das Verfahren wurde und wird immer noch vielfach implementiert, generell ist aber eine Tendenz zu anderen, neueren Verfahren, die insbesonders auf Canny basieren, zu beobachten. • F¨ ur alle Verfahren, die auf der zweiten Ableitung basieren, gilt, dass das erzeugte Kantenst¨ arkebild sehr d¨ unne Kanten aufweist. Somit gelten sie als pr¨ adestiniert f¨ ur Linienextraktion, wie sie in etwa in der Schrifterkennung eingesetzt wird.

1.2.2

Difference of Gaussians (DoG)

Das Laplacian of Gaussian Filter l¨asst sich recht einfach approximieren, indem man die Differenz zweier verschieden großer Gauß-Filter berechnet. Experimentell wurde herausgefunden, dass eine gute Approximation auftritt, wenn das σ der gr¨ oßeren Maske circa das 1,6-fache des σ der kleineren Maske ist. In der Praxis wird die Difference-of-Gaussians-Methode allerdings selten eingesetzt; beliebt ist sie jedoch unter anderem zur Anwendung in schnellen StereobildVergleichsalgorithmen.

9

1.3 1.3.1

Kantenerkennung nach dem Canny-Muster Canny-Filter

Bis hierher wurden Kantenerkennungsalgorithmen behandelt, die sich der grundlegenden Prinzipien der Kantenerkennung bedienen; eine recht gute Zusammenfassung dieser Verfahren findet sich in [4]. Der Canny Algorithmus wird im Gegensatz dazu h¨aufig zu den optimalen“ ” Kantenerkennungsverfahren gerechnet, da er selbst heute noch - immerhin 20 Jahre nach seiner Erfindung - konkurrenzf¨ahige Ergebnisse liefert. Auch bauen die meisten weitergehenden Vorschl¨age unmittelbar auf Cannys Technik auf. Canny versuchte den Operator von einer formal spezifizierten objektiven Funkur die er drei Hauptziele formulierte: tion ausgehend zu minimieren, f¨ • Minimierung der Anzahl falscher Kantenmarkierungen • M¨ oglichst gute Lokalisierung von Kanten • Erzeugung von nur einer Markierung pro Kante Canny errechnete sich auf Basis dieser Kriterien eine Funktion, die als Summe von vier Exponentialtermen dargestellt wurde. Allerdings ¨ahnelte diese Funktion sehr stark der ersten Ableitung einer Gaußschen Normalverteilung, weshalb im Endeffekt diese eingesetzt wurde. Zur Berechnung der Ableitungen kann man auf beliebige Standardprozeduren zur¨ uckgreifen, wie in etwa den Sobeloperator. Also faltet man die GaußscheGl¨ attungsfunktion mit der Ableitungsmaske und wendet den dabei entstehenden Operator auf das Bild an. Dies sollte in vier Richtungen erfolgen, wobei die Richtung, die am st¨ arksten anspricht, hervorgehoben wird. Zusammenfassend wir folgendermaßen vorgegangen: • 1. Schritt: Gl¨ attung der Bilddaten mit Hilfe einer Gauß Faltungsmatrix. • 2. Schritt: Anwendung eines einfachen Ableitungsfilters in 2D, Hervorhebung von Regionen mit Nullstellen in der 2. Ableitung (in Richtung des Gradienten - um Kanten mit Subpixelgenauigkeit zu finden). • 3. Schritt: Es entstehen Grate im Gradientst¨arkebild. Der Algorithmus setzt nun alle Pixel, die sich nicht direkt auf dem Grat befinden auf 0 (Nonmaxima-Unterdr¨ uckung, siehe B.1). • 4. Schritt: Wende auf die verbleibenden Kantenpixelkandidaten noch ein Hystereverfahren an, um unwichtige“ Kanten zu unterdr¨ ucken (f¨ ur eine ” Erkl¨ arung der Vorgangsweise, siehe B.2) Durch Variation von σ bei der Gl¨attung kann die Granularit¨at der Kantensuche beeinflusst werden, wobei h¨ohere σ Werte zwar weniger Details im Bild ur aber die Rauschempfindlichkeit abschw¨achen. lassen, daf¨ Somit werden die Filterergebnisse von σ und den Schwellwerten der Hysterese, 10

T 1 und T 2, beeinflusst. Ein zu niedriges T1 bewirkt, dass zu viele unn¨otige Kanten im Bild verbleiben, ein zu hohes T2, dass verrauschte Kanten unterbrochen werden. Bewertung des Canny-Filters: • Das Filter erkennt Kanten selbst bei starkem Rauschen relativ zuverl¨assig. • Ein großes Problem, welches immer wieder erw¨ahnt wird, sind die Schwierigkeiten, die mit Y-f¨ ormigen Kanten auftreten - diese behalten nicht zu 100% ihre Form und k¨onnen L¨ocher“ bekommen. Dieses Problem ” kann allerdings gel¨ ost werden, indem man solche Verbindungen bei der Gratsuche ber¨ ucksichtigt (ein L¨osungsvorschlag, der die Bildtopologie mitber¨ ucksichtigt, wurde von Rothwell in [6] gemacht; siehe dazu 1.3.2). • Die Hysterese (Schritt 3 des Algorithmus) bremst das Verfahren stark ein. Im schlimmsten Fall (und das w¨are, wenn die Hysterese eine Kante erkennt, die durch das ganze Bild l¨auft), steigt die Komplexit¨at durch diesen Schritt auf O(n). • In [3] vergleichen die Autoren 8 durchwegs moderne“ Detektoren anhand ” geologischer Bilder eines Vulkans auf die Erkennungsleistung bez¨ uglich der Kanten der geotektonischen Oberfl¨ache. Als Vergleichsbasis ziehen die Autoren die Rosenfeld und Pratt Metrik heran (zur Erkl¨arung der Funktionsweise, siehe A.1 und A.2). ¨ Der Vergleich mag zwar nicht repr¨asentativ sein, erlaubt aber einen Uberblick und ist der einzige auffindbare seiner Art, der sich explizit mit sehr modernen Verfahren besch¨aftigt. Getestet werden Canny, Rothwell, Black, SUSAN, Edison, Iverson-Zucker, Bezdek und Fitton-Cox, wobei es sich bei letzterem lediglich um eine modifizierte HOUGH-Transformation handelt. Hinsichtlich der Kriterien des Vergleichs schneidet Canny am besten ab. 1.3.2

Rothwell

Der bei weitem am h¨ aufigsten anzutreffende Kritikpunkt am Canny-Filter ist dessen Versagen bei Y-f¨ ormigen Kantenstrukturen. Als einen der Gr¨ unde daf¨ ur f¨ uhrt Rothwell in [6] an, dass das Extrahieren der Normalen zur Kantenrichtung, uckung des Canny-Algorithmus stattfindet, das ja bei der Nonmaxima-Unterdr¨ sehr unzuverl¨ assig ist - vor allem bei Verbindungsst¨ ucken. Deswegen schl¨ agt er ein Verfahren vor, das dem von Canny zwar prinzipiell ahnlich ist, jedoch beim Hysterese-Schritt nur eine untere Schranke T 2 festlegt, ¨ bis zu der eine Kante verfolgt werden soll, um im Kantenst¨arkebild noch enthalten zu sein. Der obere Schwellwert T 1 wird dynamisch, abh¨angig vom Bild, festgelegt. Zu diesem Zweck gewinnt der Algorithmus Topologieinformationen aus dem Bild, indem er zuerst ein Thinning nach dem Tsao-Fu-Algorithmus durchf¨ uhrt und dann Ecken aus der verbleibenden Kantenmenge konstruiert. Dies geschieht, indem Ecken entweder auf Kantenpixel(kandidaten) platziert werden, die nur einen Nachbarn haben (und deswegen das Ende einer Kante sein m¨ ussen) oder auf Kantenpixel(kandidaten), die mehr als zwei Nachbarn haben (und deswegen eine Verbindungsstelle sein m¨ ussen). 11

Die Kanten befinden sich nun konsequenterweise zwischen den so platzierten Ecken; auf diese Weise verf¨ ugt man u ¨ber Topologieinformationen, die man nutzen kann, um eine Schwellwertebene“ T zu generieren. ” Diese Topologieinformationen haben sozusagen den doppelten Vorteil, dass man einerseits u ahnte Schwellwertebene verf¨ ugt und andererseits bessere ¨ber die erw¨ Grundlagen zur Bildung von lokalen Normalen zur Kantenrichtung verf¨ ugt, was der Verbesserung der Ergebnisse der Nonmaxima-Unterdr¨ uckung zutr¨aglich ist. Kantenpixelkandidaten werden nun zu Kantenpixeln, falls gilt: Nx,y ≥ αTx,y wobei Nx,y die Intensit¨ at des jeweiligen Pixel ist. Bewertung von Rothwells Verfahren: • Rothwell et al. bezeichnen das Verfahren als bottom-up Technik, da das Extrahieren von Topologieinformationen w¨ahrend der Kantenfindung erfolgt. • Zur weiteren Verarbeitung stehen schon sinnvolle Topologiedaten zur Verugung. f¨ • Die Erkennungsleistung an Verbindungsst¨ ucken (und zumindest gemessen anhand synthetischer Bilder auch allgemein) ist der des Canny Verfahrens u ¨berlegen. • Der Zeitaufwand ist aber sicherlich auch h¨oher; es ist nicht nur ein per se aufw¨ andiger Hysterese-Schritt erforderlich; sondern auch noch ein TsaoFu-Thinning und das Extrahieren von Topologieinformationen. • Die Topologieinformationen m¨ ussen auch nicht vollst¨andig sein und sollten deshalb von aufbauenden Anwendungen, die stark davon abh¨angig sind, durchaus u uft werden. ¨berpr¨ • Das Rothwell-Verfahren erreicht in [3] Platz 2, noch vor SUSAN, Edison und Iverson-Zucker.

1.3.3

Edison

In [7] betrachten Meer und Georgescu die klassischen drei Schritte, die in vielen Detektoren, so auch bei Canny, verwendet werden und verallgemeinern sie auf einen linearen Vektorraum. So erhoffen sie, mit wenig zus¨atzlichem Rechenaufwand (ganz ¨ahnlich wie bei Rothwell sozusagen bottom-up) Informationen u ¨ber die Zuverl¨assigkeit der gefundenen Kanten zu gewinnen. Am klassischen Vorgehen kritisieren sie unter anderem, dass die Gradientenst¨arke, die ja als Kantenkriterium gilt, eine mehrdeutige Information darstellt, da sie aus dem Einfluss des Kantenmusters und der Kantendicke zusammengesetzt ist.

12

Demonstrieren l¨ asst sich das verfolgte Konzept am besten anhand eines konkreten Faltungsbeispieles von Bilddaten. Multipliziert man z.B. ein n×n-Fenster von Bilddaten a mit einer Maske w, so erh¨alt man:

Ergebnis =

m m X X

wij aij

(1)

i=−m j=−m

Als inneres Matrizenprodukt wird (1) zu: Ergebnis = spur[W T A] = spur[W AT ] Wenn man die Spalten dieser Matrix nun untereinander in einer Spalte anschreibt, kann man das Ergebnis des Operators auch als inneres Vektorprodukt berechnen: Ergebnis = wT a = aT w Im n·n-dimensionalen Vektorraum ist w ein 1D-Unterraum, W sei das (n·n−1)dimensionale Komplement von w. Dann ergibt der Fensteroperator f¨ ur jedes beliebige b ∈ W 0; deshalb gilt Folgendes: Ergebnis = wT (a + b) = wT a So sieht man, dass eine große Zahl an Vektoren das gleiche Ergebnis liefert; in der Praxis wirkt sich das als false-positives in offensichtlich unstrukturierter Nachbarschaft des Fensters aus. Seien nun (o.E.d.A.) die Daten normalisiert, d.h. es gelte k a k= 1. In diesem Fall schlagen Meer und Georgescu die nachfolgende Vorgehensweise vor: A Den Gradienten stelle man sich als zwei Masken vor (eine f¨ ur jede Richtungsableitung), welche einen zweidimensionalen Unterraum bilden: E=

w2 wT w1 w1T + T 2 T w1 w1 w2 w2

Die Projektion Ea der Bilddaten a auf diese Ebene entspricht der geˆ atzten Gradientenrichtung θ. sch¨ B Konstruiere nun eine ideale Kantenschablone t mit der gleichen Gradientenrichtung - die sich zwangsl¨aufig außerhalb des durch E dargestellten Unterraums befindet (innerhalb < a, Ea >). C Berechne nun η = |tT a|

13

D Dann ist η der Cosinus des Winkels zwischen den Daten a und der idealen Kante t - und somit der Betrag des Korrelationskoeffizienten zwischen diesen beiden Vektoren. Bewertung von Edison: • η ist ein wirklich unabh¨ angiger Sch¨atzer f¨ ur das Vorhandensein der vermuteten Kanten, da es nur aus Vektoren außerhalb der Gradientenebene zusammengesetzt ist. • Dennoch gibt es Kanten, die sich nicht an das vorgestellte Modell halten - diese werden vom Verfahren diskriminiert. • Verfahren auf h¨ oherem Niveau, die von einer sehr detailgenauen Kantenerkennung abh¨ angig sind, sollten dem Zuverl¨assigkeitssch¨atzer daher auch nicht uneingeschr¨ ankt vertrauen. • In der Theorie ist der Algorithmus wirkungsvoller als das Verfahren von Canny. • Jedoch f¨ uhrt einen zus¨atzlichen Schritt ein, der das Verfahren noch rechenintensiver macht. • Eine Open-Source Implementierung findet sich unter: http://www.caip.rutgers.edu/riul/research/code/EDISON/. • In [3] erreicht der Algorithmus lediglich Platz 7.

1.3.4

Iverson-Zucker

Iverson und Zucker glauben, dass, obwohl Kantendetektoren zu wenig globale Kriterien ber¨ ucksichtigen, diese immer noch Spielraum f¨ ur Verbesserungen im lokalen Teil lassen. Daher versuchen sie, den Prozess auf strikt formale Beine zu stellen; ihre Idee in [8] legt nahe, einen linearen Operator in einen Satz logischer Vorbedingungen zu zerlegen. Dazu teilt man diesen Operator in eine Menge Operatoren auf, deren Summe identisch zum urspr¨ unglichen Operator ist. Diese linearen Teiloperatoren stellen nun eine Messm¨oglichkeit f¨ ur die Erf¨ ullung der logischen Vorbedingungen dar. Allerdings muss die Konstruktion unter Ber¨ ucksichtigung folgender beiden Bedingungen erfolgen: • Der Operator soll nur dann reagieren, wenn die Vorbedinungen erf¨ ullt sind • Falls die Vorbedingungen erf¨ ullt sind, soll das Ergebnis exakt das Gleiche, wie das des urspr¨ unglichen Operators sein Damit soll die Zahl der false-positives, die laut Iverson und Zucker unter alschliches Erkennen von Kontrastlinien als Kanten, Erkennen anderem durch f¨ von Kanten auf die der Operator im Durchlauf gar nicht ausgerichtet ist, oder

14

Erkennen von Kantenpixeln, die nicht im Zentrum des Operators liegen entstehen, verringert werden. Bei dem linearen Operator, der verwendet wird, handelt es sich Richtungsoheren Grades des Gauß-Operators. Hat man sich auf den linearen ableitungen h¨ Operator festgelegt, bleibt noch die Zerlegung in logische Vorbedingungen. Zu diesem Zweck haben Iverson und Zucker Verkn¨ upfungen entwickelt, um numeupfungen rische Werte auf logische abzubilden. Analog zu den logischen Verkn¨ kann man diese als ∧+ und ∨+ bezeichnen. Dabei sei  x + y,    y, x ∧+ y =  x,    x + y,

falls falls falls falls

x>0∧y x>0∧y x≤0∧y x≤0∧y

>0 ≤ 0; > 0; ≤ 0;

Wieder analog zur Logik liefert ∨+ den positiven Wert, falls ein Wert von x oder y positiv ist. Mithilfe dieser Verkn¨ upfungen kann nun endlich der logisch/lineare Operator definiert werden: Ein logisch/linearer Operator auf dem Vektorraum X (x ∈ X) sei eine beliebige Funktion L : X → R in der Sprache L, die sich durch die folgende Grammatik definiert: L → ψ(x); L → ai L; L → L ∧+ L; L → L ∨+ L ankte, reelle, lineare Funktion ist und ai eine reelle wobei ψ(x) eine beschr¨ Konstante. Solche logisch-linearen Operatoren kann man nun punktweise auf das Bild anwenden. So wird z.B. aus dem (fiktiven) Operator F: ∀x ∈ X : F (I1 , I2 )(x) = I1 (x) ∧+ I2 (x), I1 , I2 : X → R uckkommend auf f¨ ur unsere Anwendungszwecke konkret n¨ utzliche FunktioZur¨ nen, sei nun Dx2 die zweite Richtungsableitung von diskreten Bilddaten. Dann l¨ asst sich eine Faltungsoperation die den Effekt des Laplace-Operators hat, folgendermaßen darstellen: φ(I) = (−Dx2 ∧+ −Dy2 ) ∗ I upfung der Operatoren mittels logischer Kombinatoren (und Mithilfe der Verkn¨ der Bedingung, dass bei positiver Entscheidung das Ergebnis des Operators das gleiche sein muss, wie ohne die Zerlegung) u ufen Iverson und Zucker die ¨berpr¨ Bedingungen die sie an eine Bildkurve stellen quasi w¨ahrend des Kantenfindungsprozesses. Den Begriff der Bildkurve definieren sie im Zuge der Formalisierung selbst und legen ihn folgendermaßen fest: Eine Bildkurve ist eine Abbildung α : S → I, so dass gilt:

(Tangentenbedingung) α sei stetig in S

15

(Normalenbedingung) N (βs ) gelte f¨ ur alle s ∈ S wobei S die Menge aller Punkte auf einer Kurve zwischen zwei Punkten ist und die Bedingung N (βs ) von der Art der Kurve abh¨angt. Von diesen Bildkurven legen sie drei verschiedene Typen fest, die sich durch ihre Normalenbedinung N (βs ) unterscheiden (die drei Typen bezeichnen sie als Kanten, positive Kontrastlinien und negative Kontrastlinien). Die Beschreibung auf [8] geht hiervon ausgehend noch weiter und beschreibt unter anderem die Anwendung des Prinzips auf das Canny-Verfahren. Da eine solch detaillierte Beschreibung den Rahmen dieser Arbeit sprengen w¨ urde, sei auf die angef¨ uhrte Original-Publikation verwiesen. Bewertung von Iverson-Zucker: • Das Verfahren legt klar und formal (in Form der Bildkurve) fest, was ein Kantenfindungsalgorithmus auffinden muss und was nicht. • Die Effizienz bei T-Verbindungsst¨ ucken und Fenstern mit mehr als einer Kante ist gr¨ oßer, da das Modell die M¨oglichkeit des Auftretens mehrerer Kanten ber¨ ucksichtigt. • Der Algorithmus findet Kontrastlinien, die er im Gegensatz zu den meisten anderen Algorithmen explizit behandelt, besser auf als dies z.B. der Canny-Algorithmus macht - die Entwerfer des Algorithmus geben zahlreiche Anwendungsbeispiele an, wo dies sinnvoll ist, so z.B. beim Erkennen von Fingerabdr¨ ucken. • Der zeitaufw¨ andige Hysterese Schritt entf¨allt, die Komplexit¨at (auf einer maximal parallelisierten Umgebung) ist O(1). • Mithilfe der Zerlegung in logische Bedingungen, sind die Ableitungen h¨oheren Grades nicht nur stabil sondern auch sehr effizient. • In [3] kann das Verfahren jedoch nur Platz 5 erreichen.

1.4 1.4.1

Kantenerkennung mithilfe neuronaler Netze Bezdek

Bezdek verwendet in [9] den Sobel-Operator als Ausgangslage, um ein neuronales Netz zur Kantenerkennung zu trainieren. Der Operator erzeugt Trai” ningsmengen“ aus allen m¨ oglichen bin¨aren Fenstermengen. F¨ ur ein 3 × 3 Fens9 ter existieren 2 solcher verschiedener Inhaltsmengen, deren Ausgabe mit dem Sobel-Verfahren auf Werte zwischen 0 und 1 skaliert werden. Diese Ausgabewerte werden nun durch eine fuzzy Zugeh¨origkeitsfunktion beschrieben, die den Grad der Zugeh¨origkeit des Pixels zur Kantenpixelmenge uckt. oder zur Menge der Pixel mit anderen Eigenschaften im Bild ausdr¨ Die Kantenheit“ eines Pixels kann, wendet man den Sobeloperator auf das ” Bin¨ arbild an, die Werte 0, 31 , 32 und 1 annehmen. Diese Kantenheit“ kann ” man als Maßzahl f¨ ur die unscharfe Zugeh¨origkeits-Funktion verwenden - das 16

neuronale Netzwerk muss nur mehr darauf trainiert werden, f¨ ur jedes Fenster den angemessenen Wert zur¨ uckzugeben. Analog zur Schwellwertanwendung beim originalen Sobel-Operator wird auch hier eine Entscheidung auf die Ausgabe angewandt, die festlegt, ob das bisschen ” Kante“ aus der unscharfen Zugeh¨origkeit nun ganz Kante oder gar nicht Kante ist. Bewertung von Bezdek: • Das Ergebnis ist f¨ ur Bin¨arbilder gleich, wie das des Sobel-Operators. • Bei niedrig-konstrastierten Graustufenbildern sind die Ergebnisse des BezdekOperators allerdings besser. • Eine starke Beschr¨ ankung des Verfahrens ist jedoch in der w¨ahlbaren Maskengr¨ oße zu sehen: W¨ahrend man das neuronale Netzwerk mit einem 3 × 3 Filter auf 29 verschiedener Inhaltsmengen trainieren muss, ben¨otigt ur eine 5 × 5 Faltungsmatrix bereits 225 Kombinationen. man f¨ • In [3] erreicht das Verfahren Platz 6 - den vorletzten Platz vor Edison.

1.5 1.5.1

Kantenerkennung mittels anisotroper Diffusion Black

Ganz im Gegensatz zu den vielen Verfahren, die Verbesserungen der Grundidee von Canny darstellen, beschreiben die Autoren in [10] ein M¨oglichkeit, anisotrope Diffusion zur Kantenfindung einzusetzen. Verwendet wird dabei eine Kantenstoppfunktion“ die nahe verwandt mit der Einflussfunktion und der ” Fehlernorm in der sogenannten robusten Sch¨atzung“ ist. ” Kanten zwischen st¨ uckweise konstanten Regionen werden dabei im robusten atzsystem als Ausreißer“ erkannt (wobei Ausreißer Stichprobenwerte sind, Sch¨ ” die sich außerhalb eines gewissen, realistischen Wertebereichs befinden bzw. deren Normalverteilungsdichte fast 0 ist). Die Autoren gehen von einem anisotropem Diffusionsfilter, konkret dem diskreten Perona-Malik-Filter aus: Ist+1 = Ist +

λ X g(∇Is,p )∇Is,p |ηs | p∈η

(2)

s

wobei λ ∈ R+ die Diffusionsrate festlegt, Is die diskreten Bildintensit¨atswerte, ηs die r¨ aumliche Nachbarschaft des Pixel s darstellt und |ηs | die Anzahl der Nachbarn von s ist. Nun wird versucht, ein statistisches Modell der Perona-Malik Funktion zu entwerfen, unter der Annahme, dass es sich bei Bildern um st¨ uckweise konstante Funktionen handelt, die durch Rauschen verf¨alscht wurden. In diesem statistischen Modell sollte die Differenz einer Bildintensit¨at und seiner Nachbarintensit¨ aten normalverteilt sein. Dies trifft jedoch nicht zu, wenn sich

17

in der Bildregion ein Kantenpixelkandidat befindet, da dieser in der konstanten Funktion eine Unstetigkeit darstellt. Zuerst versucht man nun ein st¨ uckweise konstantes Bild aus verrauschten Daten zu sch¨ atzen; dabei sollte folgendes Optimierungskriterium erf¨ ullt sein: min I

XX

ρ(Ip − Is , σ)

(3)

s∈I p∈ηs

wobei ρ (· ) eine Fehlernorm und σ ein Skalierungsparameter ist. Die Ableitung einer beliebigen ρ-Funktion ist dabei proportional zur Einflussfunktion, welche den systematischen Fehler charakterisiert, den eine Messung auf das Ergebnis hat. So l¨ asst sich auch feststellen, dass z.B. eine quadratische ρ-Funktion Ausrei” ßern“ zuviel Einfluss gibt - daher sollte die ρ Funktion toleranter auf Ausreißer“ ” reagieren und diese gegebenenfalls verwerfen. Eine f¨ ur diese Zwecke gut geeignete ρ-Funktion ist die Lorentz-Fehlernorm:   1  x 2 ρ(x, σ) = log 1 + 2 σ Betrachtet man hier die Ableitung ρ0 , so sieht man, dass der Einfluss einer Gradientenst¨ arke die u ¨ber dem festgelegten Wert σ liegt, schw¨acher wird. Als n¨ achsten Schritt leiten Black et al. eine Beziehung zwischen Bildrekonstruktion u atzung“ und anisotrope Diffusion aus den kontinu¨ber robuste Sch¨ ” ierlichen Formen von (2) und (3) ab:   ∇I ∂I(x, y, t) 0 = div ρ (k ∇I k) ∂t k ∇I k wobei div die Divergenz bezeichnet und folgende Beziehung gilt: . ρ0 (x) g(x) = x Von hier ausgehend gilt nur noch, die Kantenstoppfunktion“ g(· ) und damit ρ ” zu optimieren - im folgenden l¨asst sich das vorgestellte Verfahren dazu nutzen, wirklich Kantenbilder zu gewinnen, indem man eine penalty Funktion einf¨ uhrt, ur Ausreißer“ (in einem zus¨atzlich eingef¨ uhrten, sogenannten line-process) die f¨ ” niedrige Werte liefert (siehe [10]). Bewertung des Black-Verfahrens: • Auch bei diesem Verfahren ist anschließend eine Nonmaxima-Unterdr¨ uckung und vor allem ein zeitaufw¨andiger Hysterese-Schritt notwendig. • In [3] erreicht das Verfahren Platz 3. • Es bestehen keine qualitativen Absicherungen, die in etwa bei Edison, Rothwell oder Iverson-Zucker im Verfahren zus¨atzlich mitermittelt werden.

18

• Es werden w¨ ahrend des Verfahrens keine der weiteren Verarbeitung zutr¨ aglichen Informationen ermittelt, wie in etwa bei Rothwell oder auch Edison. • Das Verfahren ist unabh¨angig von den sonst meist grundlagenbildenden Ideen von Canny.

19

2

Kantenerkennung abseits des Mainstreams“ ”

2.1

Parametrische Kantenmodelle

Vor allem Robert Haralick engagiert sich in dem ansonsten wenig beachteten Segment der Kantenerkennung ausgehend von parametrischen Kantenmodellen. Die zugrundeliegende Idee ist, dass es den Kantenfindungsprozess vereinfacht, wenn man u ugt. Da¨ber eine mathematisch-deterministische Beschreibung verf¨ bei wird angenommen, dass die diskreten Bildinformationen, die vorliegen, eine durch Rauschen verf¨ alschte Approximation an die darunter liegende Bildintensit¨ atsfunktion sind. Um diese Intensit¨ atsfunktion zu gewinnen, zerlegt man das Bild in kleine, rechteckige Bildausschnitte, die man Facets nennt und im Folgenden durch Polynome zu approximieren versucht. Abh¨ angig des Grades der Polynome gibt es auch verschiedene Methoden, Kanteninformationen zu gewinnen. Haralicks-Methode, die Polynome u ¨berhaupt zu bestimmen, widmet sich Abschnitt C. 2.1.1

Sloped Facet Models

Die Polynome, die hier verwendet werden, stellen geneigte Ebenen ( sloped ” facets“) dar, dabei wird folgendes Modell angenommen: g(r, c) = α · r + β · c + γ + θ(r, c) wobei

r: Zeilenindex (row) c: Spaltenindex (column) α: Steigung der Ebene in r-Richtung β: Steigung der Ebene in c-Richtung γ: H¨ ohe der Ebene im Ursprung θ(r, c): Rauschen (Zufallsvariable, normal verteilt)

Es wird angenommen, dass die Rauschvorg¨ange der einzelnen Pixel unabh¨angig voneinander sind. Darauf aufbauend wird der Bildauschnitt g(r, c) durch eine unverrauschte geneigte Ebene interpoliert: ˆ + γˆ p(r, c) = α ˆ r + βc Dabei w¨ ahlt man α ˆ , βˆ und γˆ so, dass der mittlere quadratische Fehler 2 minimiert wird, wobei: 2 =

XX

(p(r, c) − g(r, c))2

r∈R c∈C

Ableiten nach den Winkeln und Nullsetzen von 2 ergibt die Ergebnisse P α ˆ=

r∈R

P

rg(r, c) 2 c∈C r

c∈C

P

r∈R

20

P

βˆ =

P

r∈R

P

cg(r, c) 2 c∈C c

c∈C

P

r∈R

P

P P r∈R c∈C g(r, c) P P γˆ = r∈R c∈C 1 Durch Zerlegung von  in zwei Terme und geschicktes Einsetzen, erh¨alt man zwei Terme, die beide χ2 -verteilt sind. Insbesonders ist somit 2 /σ 2 χ2 -verteilt. Nun kann man die Nullhypothese H0 (α = β = 0) durch folgende F-Statistik u ufen: ¨berpr¨ PP 2 PP 2 αˆ2 r + βˆ2 c )/2 P P F = 2 /( 1 − 3) Es handelt sich dabei um die Neigung der gesch¨atzten Ebene normalisiert durch den mittleren quadratischen Fehler. Folgende Ereignisse f¨ uhren nun zum Verwerfen der Null-Hypothese: 1. Die gesch¨ atzte Neigung ist zu groß. Vermutlich ist eine Kante vorhanden. 2. Der mittlere quadratische Fehler ist zu klein. Bewertung des Sloped-Facet-Modells zur Kantenfindung: • Sloped-Facets werden kaum eingesetzt, meistens greift man auf die Nulldurchg¨ ange von kubischen Polynominterpolationen zur¨ uck. • Folglich existieren kaum Aussagen zur Komplexit¨at und Erkennungsleistung. • Das Verfahren hat unter anderem den Nachteil, das es verrauschte Facetten als flach betrachtet. 2.1.2

Integrierter Gradientendetektor

Der integrierte Gradientendetektor basiert nun nicht mehr auf Polynomen zweiten Grades, sondern auf solchen dritten Grades (auf die Interpolation solcher Polynome geht Abschnitt C genauer ein, die Masken die man dazu verwenden kann folgen sp¨ ater in diesem Abschnitt). Somit versteht es sich als Cubic Facet Model im Sinne von Haralicks Facet Models“. ” Die Zielsetzung des integrierten Gradientendetektors ist, die Operationen eines Gradientendetektors anzun¨ahern. Haralick verwendet dazu in [11] folgendes kubisches Polynom:

f (x, y) = k1 + k2 r + k3 c + k4 r2 + k5 rc + k6 c2 + k7 r3 + k8 cr2 + k9 c2 r + k10 c3 (4) 21

Ein Verfahren, um ein Gradientenfilter (dessen prinzipielle Funktionsweise schon ausf¨ uhrlich unter anderem in den Abschnitten 1.1.1 bzw. 1.3.1 vorgestellt wurde), mithilfe der parametrisierten Facets umzusetzen, entwickelten Haralick und Zuniga in [12]. Dazu berechnen sie die partiellen Ableitungen der ersten Zeile und Spalte des interpolierten Polynoms (4) mit Zentrum (0,0): ∂I(r, c) = k2 ∂r ∂I(r, c) = k3 ∂c Nun gilt f¨ ur die Richtungsableitung in eine beliebige Richtung φ, dass die Funktion Iφ0 (r, c), die diese Ableitung repr¨asentiert, folgendermaßen berechnet werden kann: ∂I(r, c) ∂I(r, c) Iφ0 (r, c) = sin φ + cos φ ∂r ∂c Integriert man diese Richtungsableitung, so erh¨alt man die integrierte Richtungsableitung Fφ (f¨ ur eine Fenstergr¨oße von N × N ):

Fφ =

1 4N 2

Z

L

−L

Z

W

Iφ0 (r, c)

−W

Das Verfahren erzielt mit Werten f¨ ur L und W , die wenig kleiner als die halbe Maskengr¨ oße sind, die besten Resultate (wobei L = W = 0 einer einfachen Gradientenfilterung des kubischen Polynoms entspricht). Das φ, das Fφ hier maximiert, entspricht der Sch¨atzung der Gradientenrichtung, d.h. der gesch¨ atzte integrierte Gradient ist G = Fφ max uφ max wobei uφ max der Einheitsvektor in Richtung des maximalen Gradienten ist. F¨ ur L = W ist das φ, das Fφ maximiert φ = tan−1

B A

und Fφ max errechnet sich dann durch Fφ max =

p A2 + B 2

wobei A = L2 k7 + 13 L2 k9 + k2 und B = L2 k10 + 13 L2 k8 + k3 . Die einzelnen ki erh¨ alt man, indem man die Bilddaten mit Linearkombinationen der Gewichtungskernel f¨ ur die diskreten orthogonalen Polynome faltet. autert dies genauer in [13]. Haralick erl¨ Berechnet man die einzelnen Faltungskernel auf Grundlage von TschebyscheffPolynomen, so erh¨ alt man folgende zehn Filtermasken, die als Ergebnis einer

22

Faltung mit den Bilddaten die einzelnen ki ergeben (wobei aufgrund der symmetrisch gew¨ ahlten St¨ utzstellen und der Zeilen- und Spaltenindizierung die Masken M3 , M6 , M9 bzw. M10 jeweils den transponierten Matrizen M2 , M4 , M8 bzw. M7 entsprechen):

     

1 M1 = 25

     

M2 =

−0, 0743 0, 0114 0, 0400 0, 0114 −0, 0743

0, 0114 0, 0971 0, 1257 0, 0971 0, 0114

0, 0400 0, 1257 0, 1543 0, 1257 0, 0400      

1 M4 = 70

2 −1 −2 −1 2      

1 M5 = 100

 M7 =

1 360

    

    

1 140

1 1 1 1 1

0, 0114 0, 0971 0, 1257 0, 0971 0, 0114

1 1 1 1 1



−0, 0743 0, 0114 0, 0400 0, 0114 −0, 0743



1 1 1 1 1

2 2 2 −1 −1 −1 −2 −2 −2 −1 −1 −1 2 2 2

1 1 1 1 1

2 −1 −2 −1 2

−4 2 4 2 −4

    

    

     

 2 0 −2 −4 1 0 −1 −2   0 0 0 0   −1 0 1 2  −2 0 2 4

−6 −6 −6 −6 −6 12 12 12 12 12 0 0 0 0 0 −12 −12 −12 −12 −12 6 6 6 6 6 

M8 =

4 2 0 −2 −4

1 1 1 1 1

     

 −2 0 2 4 1 0 −1 −2   2 0 −2 −4   1 0 −1 −2  −2 0 2 4

Bewertung des integrierten Gradientdetektors: • Als Gradientenverfahren verliert der Operator seinen exotischen Status und steht - trotz Parametermodell - in Konkurrenz mit dem Canny-Algorithmus 23

und seinen Derivaten. • Tendenziell erzeugt der integrierte Gradientendetektor weniger false-negatives als der Canny-Algorithmus... • ... daf¨ ur allerdings auch mehr false-positives. • Die Rauschanf¨ alligkeit kann in bestimmten Situationen weit niedriger sein, als die des Canny-Algorithmus. • Das Ergebnis des Algorithmus kann auch schon ohne aufw¨andige Nachbearbeitungsschritte, wie in etwa Hysterese oder Non-Maxima Unterdr¨ uckung in etwa mit dem des Canny-Filters konkurrieren. Verzichtet man auf die Kantenrichtungsinformationen kommt man aufgrund der Distributivit¨at der Faltung und der Tatsache, dass A und B Linerkombinationen von Koeffizienten sind, mit zwei Faltungen und einer L2 -Norm aus. 2.1.3

Nulldurchg¨ ange der 2. Ableitung mit Cubic Facet Models

Liegt die Polynomdarstellung der diskreten Bilddaten einmal vor (zur eigentlichen Interpolation, siehe C), ist es vergleichsweise einfach, die Nulldurchg¨ange der zweiten Ableitung zu untersuchen. Da das parametrische Kantenmodell bereits als Ann¨aherung an eine als verrauscht angenommene Oberfl¨ ache gilt, verwendet man hier statt des LoG nur den Laplace-Operator. Von der kubischen Interpolation, die in 4 dargestellt ist, ausgehend, ist die zweite Ableitung 2k4 + 2k6 Eine Kante tritt genau dann auf, wenn mit diesem cubic fit“ ein Nulldurchgang ” stattfindet. In der Prototypimplementierung hat es sich als praktikabel und effizient erweisen, hier einfach zu testen, ob k4 und k6 einen gewissen Wert u ¨bersteigen, was aufgrund des Kurvenverlaufs des Nullduchgangs, zum Ziel f¨ uhrt. Bewertung des Haralick-Kantendetektors: • Das Verfahren ist das bekannteste, das auf dem Facet Model basiert und wird deswegen wegen seines Erfinders oft auch Haralick-Kantendetektor genannt. • Die Eigenschaften sind weitgehend mit denen von LoG identisch; Unteruber einen Gauß-Filter schiede entstehen nur durch die Art der Gl¨attung (¨ bei LoG unter u ¨ber die Anpassung der Facets bei diesem Detektor). • Als Vorteil gegen¨ uber dem LoG-Verfahren wird angef¨ uhrt, dass die Varianz einer Faltungsoperation mit der Maske geringer ist ( Haralicks Kriteri” um“). Dies ist insofern ein Vorteil, als gr¨oßere Varianzen in der Faltungsoperation auch zu h¨ oheren false-positive- und false-negative-Raten f¨ uhren.

24

2.2 2.2.1

Kantenerkennung ohne Ableitung SUSAN

SUSAN ( Smallest Univalue Segment assimilating Nucleus“) ist ein isotropisch ” arbeitendes Filter, bei dem man eine Maske auf dem Bild platziert und die Helligkeit jedes Pixels in dieser Maske mit dem Nukleus (dem Wert in der Mitte der Maske) vergleicht. F¨ ur diesen Vergleich kann man nun eine Funktion definieren, die abh¨angig von einem Schwellwert t den Wert 0 oder 1 annimmt: ( → → 1 falls |I(− r ) − I(− r0 )| ≤ t → − → − c( r , r0 ) = → − → 0 falls |I( r ) − I(− r0 )| > t → → wobei − r0 die Position des Nukleus bezeichnet, − r die Position des gerade betrachteten Pixels und I sich auf die (diskrete) Intensit¨atsfunktion (die Helligkeit ahlten Pixels) bezieht. des gerade gew¨ Davon ausgehend kann man nun die Fl¨ache des USAN aus der Summe der Pixel, die verglichen mit dem Nukleus u ¨ber dem Schwellwert liegen, errechnen: → n(− r0 ) =

X

→ → c(− r ,− r0 )

→ − r

Als n¨ achsten Schritt wendet man einen geometrischen Schwellwert“ auf n an, ” der eigentlich nicht der Kantenfindung selbst, sondern der Rauschunterdr¨ uckung dient. Dieser Schwellwert g ist auf der Basis von Erfahrungswerten als 3nmax /4 festgelegt. Es kann gezeigt werden, dass so keine Kanten verloren gehen (insbesondere ist im Kantenfall das USAN immer kleiner als nmax /2) und optimale uckung erzielt wird. Rauschunterdr¨ Man wendet nun g auf die einzelnen USANs-Fl¨achen an: − R(→ r0 ) =

( → → g − n(− r0 ) falls n(− r0 ) < g 0 sonst

Darin spiegelt sich das SUSAN-Prinzip: Je kleiner das USAN, desto st¨arker die Kante. ur c kann hingegen noch verbessert werden, insbesonders um Die Gleichung f¨ stabilere Ergebnisse zu liefern: d 6 → → c(− r ,− r0 ) = e−( t )

→ → wobei d = |I(− r )| − |I(− r0 )| Dem typisches Problem isotroper Kantendetektoren entgeht man jedoch auch ur hier nicht: Man hat keine Informationen u ¨ber die Kantenrichtung. Z.B. f¨ Nonmaxima-Unterdr¨ uckung und Kantenerkennung auf Sub-Pixel-Genauigkeit ben¨ otigt man diese aber. Zumindest die Kantenrichtung kann man aus dem USAN rekonstruieren. Bei einer Stufenkante, die sich genau zwischen zwei Pixeln befindet, hier inter-pixel 25

→ edge genannt, ist der Vektor zwischen dem Gravitationszentrum − r des USAN → − und dem Nukleus genau senkrecht zur lokalen Kantenrichtung. r berechnet sich aus: P − → − → − → → − r c( r , r0 ) → − r = Pr → − → − → − r c( r , r0 ) Etwas schwieriger wird es bei Kanten, die sehr nahe dem Zentrum eines Pixels liegen. Das USAN ist nun eine Linie, auf der sich die Kante befindet, der Rest der Maske wird unterdr¨ uckt. Man kann die Kantenrichtung aber finden, indem man die l¨ angste Symmetrieachse berechnet: → (x − x0 )2 (− r0 ) =

X

→ (y − y0 )2 (− r0 ) =

X

→ → (x − x0 )2 c(− r ,− r0 )

→ − r

→ → (y − y0 )2 c(− r ,− r0 )

→ − r

und → (x − x0 )(y − y0 )(− r0 ) =

X

→ → (x − x0 )(y − y0 )c(− r ,− r0 )

→ − r

Das Verh¨ altnis zwischen (x − x0 )2 und (y − y0 )2 bestimmt die Ausrichtung der Kante, das Vorzeichen von (x − x0 )(y − y0 ), legt fest, ob eine Diagonalkante einen positiven oder negativen Gradienten hat. Zum Kategorisieren des Typs der Kante erweist sich ein heuristisches Vorgehen als n¨ utzlich: • Falls die USAN-Fl¨ ache kleiner als der Maskendurchmesser ist, handelt es sich wahrscheinlich um eine intra-pixel Kante. • Sonst handelt es sich um eine inter-pixel-Kante, außer das Gravitationszentrum ist weniger als einen Pixel vom Nukleus entfernt. Es bleibt aber auf jeden Fall individuell zu entscheiden, ob die Kantenrichtungsinformation den Aufwand rechtfertigt, was f¨ ur jedes Anwendungsgebiet agen sein wird. abzuw¨ Hat man die Richtungsinformationen extrahiert, k¨onnte nun noch eine NonmaximaUnterdr¨ uckung folgen. Bewertung von SUSAN: • Unsch¨ arfere Kanten werden mit einer geringeren USAN-Fl¨ache im Kantenzentrum bestraft. Das kann sich als Vorteil erweisen. • Im Gegensatz zu Canny braucht SUSAN keinen abschließenden (zeitaufw¨ andigen) Hysterese Schritt. Deswegen ist der Algorithmus um ein Vielfaches schneller. • Die Erkennungsleistung von SUSAN h¨angt nicht von der Maskengr¨oße ab (nat¨ urlich ab einer 3 × 3 Maske). 26

• Rauschunterdr¨ uckung ist durch den geometrischen Schwellwertschritt gut. • Auch Y-f¨ ormige Kanten werden, im Gegensatz zu Canny, gut verbunden. • SUSAN platziert sich hinsichtlich der quantitiven Kriterien von [3] souvean auf Platz 4. r¨

27

3

Zusammenfassung und Ausblick

¨ Im Rahmen dieser Arbeit wurde ein Uberblick u ¨ber die popul¨arsten sowie ausgew¨ ahlte neuere Kantendetektoren gegeben. Welche der vorgestellten Detektoren die besten“ Ergebnisse liefern, l¨asst sich ” allerdings, wenn u ¨berhaupt, nur tendenziell festlegen. Zwar war Cannys Detektor der erste, der merkbare Verbesserungen gegen¨ uber einfachen Richtungsableitungen brachte und wird auch heute noch sehr oft eingesetzt; jedoch darf trotzdem nicht davon ausgegangen werden, dass ein Verfahren unter allen Umst¨ anden optimales Verhalten liefert. Ganz abgesehen davon ist Cannys Verfahren aufgrund des zeitaufw¨ andigen Hystereseschrittes bei geschwindigkeitskritischen Anwendungen reinen Faltungsoperatoren unterlegen. Aus diesem Grund - und auch, weil es sich immer lohnt, Alternativen zu betrachten - wurden in dieser Arbeit auch weniger bekannte Verfahren, wie SUSAN, Haralicks integrierter Gradientendetektor und Weiterentwicklungen des Canny-Verfahrens betrachtet. Von SUSAN, Haralicks integriertem Gradientendetektor und dem Haralick-Kantendetektor wurden Prototypen in Matlab erstellt. Die nachfolgenden Kantenst¨ arkebilder wurden mit diesen Prototypen aus dem Originalbild errechnet, es fehlen jedoch eventuelle Nachbearbeitungsschritte; insbesonders findet kein Thinning statt (d.h. die gefunden Kanten sind fallweise breiter als einen Pixel).1

(a) Das Originalbild

(b) Nach Kantenfindung mit integriertem Gradientendetektor

1 Das

Copyright des Bildes liegt bei Playboy Enterprises, Inc.. Die Verwendung wird von Playboy mittlerweile toleriert (Quelle: http://www.cs.cmu.edu/˜chuck/lennapg/editor.html). Das Bild ist der de-facto Industriestandard zum Testen von Bildverarbeitungsalgorithmen.

28

(c) Nach Kantenfindung Haralick-Kantendetektor

mit

dem

(d) Nach Kantenfindung SUSAN-Kantendetektor

mit

dem

Abbildung 2: Ergebnisse der Prototypen In einer zweiten Arbeit wird nun daher die Umsetzung dieser Prototypen in einem eigenst¨ andigen Programm mit grafischer Oberfl¨ache als Ziel dienen. Dabei ist geplant, die Algorithmen in Form von C(++)-Dateien in die Oberfl¨ache, die utzt durch die QT-Bibliothek, gestaltet werden in der Sprache C++, unterst¨ wird, einzubinden, was sich gleichzeitig als Test f¨ ur die tats¨achliche Praxistauglichkeit der Algorithmen anbietet. Dabei kann als grobe Hilfestellung auf die w¨ahrend der Implementierung der Matlab-Prototypen gesammelte Erfahrung zur¨ uckgegriffen werden; ein Hauptaugenmerk muss bei der Umsetzung der Verfahren aber auf der effizienten Implementierung liegen, die sich in Matlab leicht mit Hilfe (effizienter) integrierter Routinen bewerkstelligen l¨ asst, in C(++) aber selbst erarbeitet werden muss.

29

A

Qualitativer und quantitativer Vergleich von Kantendetektoren

W¨ ahrend es eine Vielzahl an L¨osungsvorschl¨agen f¨ ur das Problem der Kantenerkennung in Bildern selbst gibt, existiert weit weniger Material u ¨ber den Vergleich bereits entwickelter Methoden. Die wohl naheliegendste M¨ oglichkeit, die Ergebnisse eines Kantenfindungsalgorithmus auszuwerten, ist der visuelle Vergleich von Bildern durch einen Betrachter. Es wird jedoch oft die mangelnde Objektivit¨at und die Abh¨angigkeit vom Empfinden des jeweiligen Betrachters an diesem Vorgehen kritisiert, weshalb f¨ ur den Vergleich von Kantenst¨ arkebildern Metriken geschaffen wurden. Repr¨ asentativ sollen hier zwei dieser Metriken vorgestellt werden:

A.1

Pratt-Metrik

Die Pratt-Matrik bezieht sich auf eine ideale Kantenabbildung, die man zu einem Bild zus¨ atzlich zu dem Ergebnis des Algorithmus vorliegen hat. Ob man hier die ideale Kantenabbildung selbst findet oder beispielsweise Ergebnisse des Canny-Algorithmus schrittweise durch Nachbearbeitung verbessert, wird offen gelassen. Die Referenzkanten in der idealen Kantenabbildung sollten jedoch m¨ oglichst einen Pixel breit sein. Dann ist das Bewertungskriterium f¨ ur den Algorithmus n

E1 =

d X 1 1 max{nd , nt } i=1 1 + ad2i

wobei nd die Anzahl der durch den Kantenfindungsalgorithmus gefundenen Kanten und nt die Anzahl der in der idealen Kantenabbildungen vorhandenen Kanten ist. Bei di handelt es sich um den Abstand einer durch den Algorithmus achsten (vom Pixel der erkannten Kante ausgehend) erkannten Kante zu der n¨ m¨ oglichen Kante. Durch max{nd , nt } werden false-positives und false-negatives bestraft, mithilfe des Skalierfaktors a kann man regeln, ob man zu dicke“ Kanten oder d¨ unne, ” aber falsche gelegene Kanten mehr bestrafen m¨ochte. Eine h¨ ohere Pratt-Metrik bedeutet demzufolge ein besseres Ergebnis, gemessen anhand des Abstandes der gefundenen zu den erwarteten Kanten und auch ausgehend von der Anzahl der false-positives und false-negatives. Eine ausf¨ uhrlichere Zusammenfassung des Messverfahrens findet sich in [14].

A.2

Rosenfeld-Metrik

W¨ ahrend die Pratt-Metrik haupts¨achlich lokale Kanteneigenschaften wie die Eigenschaft als false-positive oder das Fehlen der Kante an der zu erwartenden Stelle bzw. den Abstand der Kante zur tats¨achlich auftretenden untersucht, betrachtet die Rosenfeld-Metrik vornehmlich die Kantenkoh¨arenz. 30

Somit ist die Rosenfeld-Metrik kein ausreichendes aber zus¨atzlich zu einer anderen Metrik eventuell ein aussagekr¨aftiges Bewertungskriterium. Bevor man jedoch das eigentlich Prinzip der Rosenfeld-Metrik betrachten kann, muss man noch einige Vorbereitungen treffen: M¨ochte man wissen, wie gut sich ein Kantenpixel im Bild nach links fortsetzt, kann man daf¨ ur eine Funktion L(k) definieren:

( π a(d, dk )a( kπ 4 ,d + 2) L(k) = 0

falls Nachbar k ein Kantenpixel ist sonst

(5)

d kennzeichnet dabei die Kantenrichtung des getesteten Pixels, di die Richtung der Nachbarpixel vom rechten Pixel ausgehend im Gegenuhrzeigersinn. a ist eine Metrik f¨ ur den Winkelunterschied: π − |α − β| π Ersetzt man in (5) d + π2 durch d − π2 , so erh¨alt man eine analoge Funktion R(k) ur die Kantenstetigkeit nach rechts. f¨ a(α, β) =

Sei C nun der Durchschnitt des gr¨oßten Wertes von R(k) und des gr¨oßten Wertes von L(k). ur die D¨ unnheit Davon ausgehend kann man sich sehr einfach eine Kennzahl T f¨ der Kante errechnen; diese besteht aus den sechs u ¨brigen Pixeln innerhalb der betrachteten 3×3 Maske (alle Pixel außer dem Zentrum und den jeweils gr¨oßten L(k) und R(k)). So erh¨ alt man die Metrik aus den beiden gewonnenen Kenngr¨oßen: E2 = γC + (1 − γ)T wobei γ frei w¨ ahlbar ist, aber nat¨ urlich gr¨oßer 0 und kleiner 1 sein sollte.

B B.1

Methoden zur Konturaufbesserung Nonmaxima-Unterdru ¨ ckung

Zum Entfernen von durch den Kantenerkennungsalgorithmus gefundenen Fehlinformationen, die in etwa durch ein verrauschtes Ausgangsbild entstanden sind, erfreut sich die Nonmaxima-Unterdr¨ uckung aufgrund ihrer relativen Einfachheit als Nachbearbeitungsschritt großer Beliebtheit. Man vergleicht den Betrag der Kante mit quer zu Ihrer Richtung gelegenen Pixeln und geht dabei in etwa nach folgendem Algorithmus vor: (A) Ermittle zwei Nachbarn (aus den 8 umherliegenden Pixel) des aktuellen Pixels, so dass quer zur Kantenrichtung“ gilt. W¨ahle dazu aus den Rich” tungsmasken auf Basis der Gradientrichtung α des aktuellen Pixels. 31

¨ (B) Uberpr¨ ufe ob sich die Gradientenrichtung des Pixels und seiner beiden Nachbarn um weniger als einen Schwellwert unterscheidet. Ist der Unteroßer als, wahlweise ±15◦ , ±45◦ oder ±90◦ , nimm den n¨achsten schied gr¨ Pixel und beginne wieder bei (A). (C) Falls der Gradientenbetrag des aktuellen Pixels nicht gr¨oßer ist, als der beider Nachbarn, wird er auf 0 gesetzt. Beginne mit dem n¨ achsten Pixel wieder bei (A) (D) Eventuell kann man noch alle Pixel, die einen gewissen Schwellwert unterschreiten, auf 0 setzen. Dasselbe Verfahren kann auch mit 4 Nachbareintr¨agen durchgef¨ uhrt werden. Man w¨ ahlt, je nach lokal Kantenrichtung (in 45◦ Schritten) z.B. die links und links unten und rechts und rechts oben gelegenen Eintr¨age.

B.2

Hysterese

Das Hystereseverfahren wird durch zwei Schwellwerte T 1 und T 2 gesteuert. T1 legt den Schwellwert fest, der ben¨otigt wird, damit ein Grat als Kante im Bin¨ arbild bestehen bleibt und T2 denjenigen (quasi unteren) Schwellwert, bis zu dessem Erreichen der Algorithmus der Kante folgt. Die Schwellwerte sind entweder statisch vorgegeben und m¨ ussen bereits vor der Durchf¨ uhrung des Verfahrens als zumindest f¨ ur den Großteil der erwarteten Bilder sinnvolle Werte gew¨ ahlt werden oder werden wie bei 1.3.2 dynamisch aus im Bild vorhandenen Informationen gewonnen. Dies ist insbesonders deswegen sinnvoll, weil Bilder oft nicht u ugen. ¨ber das gleiche Helligkeits- oder Kontrastverh¨altnis verf¨ Als sehr großer Nachteil des Hystereseschritts wird immer dessen große Rechenintensit¨ at angef¨ uhrt, die sich im schlimmsten Fall im Bereich von O(n) bewegt. Das klingt zwar nach einer geringen Komplexit¨at, relativiert sich aber, wenn man bedenkt, dass die allermeisten Methoden der Kantenerkennung O(1) als Komplexit¨ atsmaß haben.

B.3

Thinning-Verfahren

Sehr viele Kantenfindungsalgorithmen besitzen die unangenehme Eigenschaft, dass sie im Kantenst¨ arkebild, das sie aus dem Originalbild erzeugen, viele Kanten k¨ unstlich verbreitern. Werden die Kanteninformationen dabei so stark beeintr¨achtigt, dass auf dem Prozess aufbauende Schritte diese nicht ohne Zwischenverarbeitungsschritt verwenden k¨ onnen oder ben¨ otigt man exakte Linieninformationen (etwa zur Schrifterkennung oder zum Verarbeiten von Fingerabdr¨ ucken), so ist man auf einen Thinning-Schritt in der Nachbearbeitung angewiesen. ¨ Ahnlich wie in der Kantenerkennung selbst, existiert auch hier eine erschlagende Vielfalt an Verfahren, die jedoch nicht immer dasselbe Ziel verfolgen, da nie exakt festgelegt wurde, welche Aufgabe ein Thinning-Algorithmus zu erf¨ ullen

32

hat. Davon unabh¨ angig bringen Thinning-Verfahren oft unerw¨ unschte St¨oreffekte in das Bild ein. Exemplarisch soll hier dennoch das bekannteste Verfahren, er¨ortert von Zhang und Suen in [15], vorgestellt werden. F¨ ur den Kantenpixelkandidaten P1 , u ¨ber dem die Maske zentriert ist, gilt dabei folgende Nachbarschaft: P9 P8 P7

P2 P1 P6

P3 P4 P5

Das Verfahren folgt zwei Iterationen. Im ersten Schritt wird P1 gel¨oscht (in einem Bin¨ arbild auf 0 gesetzt), falls folgende vier Bedingungen erf¨ ullt sind: 1) 2 ≤ B(P1 ) ≤ 6 2) A(P1 ) ≤ 1 3) P2 · P4 · P6 = 0 4) P4 · P6 · P8 = 0 ¨ wobei A(P1 ) die Anzahl der 01-Uberg¨ ange in der geordneten Menge P2 . . . P9 ist und B(P1 ) die Anzahl der Nachbarn von P1 , deren Intensit¨atswert nicht 0 ist. In der zweiten Iteration erfolgt genau dieselbe Prozedur, mit dem einzigen Unterschied, dass sich die L¨ oschbedingungen 3 und 4 ¨andern: 3’) P2 · P4 · P8 = 0 4’) P2 · P6 · P8 = 0 Die erste Iteration entfernt dabei s¨ ud¨ostliche Kantenbegrenzungen und nordwestliche Eckpunkte, w¨ ahrend die zweite Iteration nordwestliche Kantenbegrenud¨ ostliche Eckpunkte behandelt. zungen und s¨ Das Verfahren terminiert, wenn keine Punkte mehr entfernt werden k¨onnen; durch die Bedingungen 1 und 2 bleibt das Skelett erhalten. Man sieht, dass dieser Nachbearbeitungsprozess die besonders angenehme Eigenschaft hat, keinerlei Kantenrichtungsinformationen zu ben¨otigen.

C

Interpolation durch Polynome

Vor allem zur Kantenfindung in den sogenannten Facet-Models w¨ urde man gerne Polynome aus den diskreten Bilddaten erzeugen, deren integrierten Gradienten oder zweite Ableitung man gerne betrachten w¨ urde, beziehungsweise die man gerne innerhalb eines statistischen Zusammenhanges, wie zum Beispiel bei urde. Haralicks Sloped Facets, betrachten w¨ Man versucht dazu die Bilder, die als diskrete Matrixeintr¨age vorliegen, durch folgendes Polynom zu interpolieren: 33

f (r, c) = k1 + k2 r + k3 c + k4 r2 + k5 rc + k6 c2 + k7 r3 + k8 r2 c + k9 rc2 + k10 c3 Da das Ausrechnen der Polynomkoeffizienten aus 10 Gleichungen viel zu aufw¨andig w¨ are, schl¨ agt Haralick vor, Masken zu verwenden, um diese zu berechnen. Es gilt Koeffizienten f¨ ur das Polynom k1 + k2 xi + k3 x2i = fi zu finden. Man kann sich nun der Eigenschaft bedienen, dass man die St¨ utzstellen f¨ ur die Interpolation frei w¨ ahlen darf. W¨ahlt man diese symmetrisch um die 0, so ergeben sich prinzipbedingt einige Vereinfachungen. L¨ost man nun n¨amlich ein Gleichungssystem mit i diskreten Funktionswerten nach den Koeffizienten auf, so entfallen einige Glieder der Gleichungen aus Symmetriegr¨ unden. Hat man diese vorbereitenden Maßnahmen getroffen, verwendet man nun, um die Koeffizienten zu interpolieren, ein Verfahren, das auf orthogonalen Polynomen fußt. Die hier gew¨ ahlten Polynome sind so beschaffen, dass gilt: Z

b

h2n 6= 0 falls m = n 0 sonst

 gm (x)gn (x)dx =

a

(6)

wobei hn die Norm der Funktion g ist. Es gilt also, f¨ ur f (x) = k0 +k1 g1 (x)+. . . eine Koeffizienteninterpolation durchzuf¨ uhren. Man kann nun beide Seiten mit gn (x) multiplizieren und integrieren und erh¨ alt: Z

b

b

Z f (x)gn (x) = k0

Z gn (x)dx + k1

a

a

b

g1 (x)gn (x)dx + . . .

(7)

a

Wegen (6) verschwinden aus (7) alle Glieder der rechten Seite, außer: Z

b

gn (x)gn (x)dx = kn h2n

a

Somit gilt nun

kn = (1/h2n )

Z

b

f (x)gn (x)dx

(8)

a

Es bleibt noch die Entscheidung, welche Polynome, die die oben angef¨ uhrte Orthogonalit¨ atseigenschaft erf¨ ullen, man w¨ahlen soll. Besonders g¨ unstig f¨ ur Interpolationsaufgaben sind unter den orthogonalen Polynomen die so genannten Tschebyscheff-Polynome, die charakterisiert sind durch w(x) = √

34

1 1 − x2

h2n

 =

f alls n 6= 0 sonst

π/2 π

Die Koeffizienten der Polynome bestimmen sich nun durch:

kn =

(1/h2n )

Z

1

−1

f (x) √ Tn (x)dx 1 − x2

Ein Vorteil, den uns solche orthogonalen Polynome bieten, ist, dass zur Verkleinerung des N¨ aherungsfehlers einfach eine gewisse Anzahl von Polynomen aufzuaddieren ausreicht. Haralick betrachtet (im eindimensionalen Fall) ein Polynom n-ten Grades f¨ ur Reihen (in der Bildintensit¨ atsmatrix) r und P (0) := 1 Pn (r) = rn + an−1 rn−1 + . . . + a1 r + a0 Das jeweils n¨ achste unbekannte Polynom bekommt man u ¨ber die bereits erw¨ ahnte Orthogonalit¨ atsbedingung. Zum Beispiel errechnet sich P1 (r) folgendermaßen: X

P0 (r)P1 (r) =

X

(r + a0 ) = 0

r∈R

r∈R

F¨ ur die Reihenindizierung greifen wir wieder auf den alten Trick des symmetrischen Koordinatensystems zur¨ uck und w¨ahlen zum Beispiel {-2,-1,0,1,2}. P Dann ist r = 0, folglich muss a0 = 0 sein. Also ist P1 (r) = r Analog kann man nun weitere Polynome bestimmen, indem man auf bereits bestimmte Polynome, die Orthogonalit¨atseigenschaft und die Vorteile, die sich durch die gew¨ ahlte Reihenindizierung ergeben, zur¨ uckgreift. So erh¨ alt man die Polynome P0 (r) = 1 P1 (r) = r P2 (r) = r2 − µ2 /µ0 P3 (r) = r3 − (µ4 /µ2 )r (µ µ −µ µ )r 2 +(µ µ −µ2 ) P4 (r) = r4 + 2 4 0µ06µ4 −µ2 2 6 4 2

wobei µk =

X

rk

r∈R

Die so gewonnenen Pi k¨ onnen nun als Koeffizienten f¨ ur Zeilen- und Spalteneintr¨ age genutzt werden (indem man Pi (r) und Pi (c) berechnet). Erinnern wir uns an (8). Die Koeffizienten f¨ ur eindimensionale Interpolation von Bildintensit¨ atsdaten w¨ aren nun:

35

km =

Pm (r) f (r) 2 s∈R Pm (s)

X

P r∈R

wobei f (r) den Grauwert des Pixels r darstellt. In der zweiten Dimension stellt sich der Term dar als: Pm (r, c) P 2 s∈R t∈C Pm (s, t)

Mm (r, c) = P

Daraus lassen sich Masken zur Polynom-Koeffizienten-Interpolation ableiten, die neun 3 × 3 Masken f¨ ur den quadratischen Fit finden sich (in einer gegen¨ uber des Originaltextes korrigierten Version) in [16], die zehn 5 × 5 Masken f¨ ur den kubischen Fit finden sich in Abschnitt 2.1.2. Jedoch ist die Faltung des Bildes mit einer 2D-Faltungsmatrix zur Koeffizienteninterpolation immer noch rechenintensiv. Deswegen schlagen Ji und Haralick in [13] vor, zwei 1D Faltungsmatrizen zu verwenden. Dabei greifen sie auf die Eigenschaft zur¨ uck, dass diskrete orthogonale Polynome auch als Tensorprodukte zweier 1D Polynome gebildet werden k¨onnen. Sei zum Beispiel (wieder in unserem symmetrischen Koordinatensystem) die 1D Gewichtungsmatrix w01 0-ten Grades 15 [1 1 1 1 1]0 und die 1D Gewichtungsmatrix 1 w11 1-ten Grades 10 [−2 − 1 0 1 2]0 so erh¨alt man w21 aus dem Tensorprodukt der beiden Vektoren und w31 aus deren Kreuzprodukt.

36

Literatur [1] Robert M. Haralick Edge and region analysis for digital image data Computer Graphics and Image Processing 12 (1980) 60-73 [2] S.M. Smith, J.M. Brady SUSAN - A new approach to low level image processing Technical Report TR95SMS1c, Oxford University, 1995 [3] D.P. Argialas, O.D. Mavrantza Comparison of Edge Detection and Hough Transform Techniques for the Extraction of Geologic Features International Society for Photgrammetry and Remote Sensing, Commission III, WG4, Istanbul 2004 [4] Wilhelm Burger, Mark J. Burge Digitale Bildverarbeitung Springer-Verlag-Berlin, 2005 [5] D. Marr, E. Hildreth Theory of Edge Detection Proceedings Royal Society of London, vol. B207, pp. 187-217, 1980 [6] C.A. Rothwell, J.L. Mundy, W.Hoffmann, V.D. Nguyen Driving Vision by Topology Proceedings IEEE Symposium on Computer Vision, pp. 395-400, 1995 [7] Peter Meer, Bogdan Georgescu Edge Detection with Embedded Confidence IEEE Transactions on Pattern Analysis and Machine Intelligence, Volume 23, pp. 1351 - 1365, 2001 [8] L. Iverson, S.W. Zucker Logical/Linear Operators for Image Curves IEEE Transactions on Pattern Analysis and Machine Intelligence, Volume 17, pp. 982 - 996, 1995 [9] J.C. Bezdek, M. Shirvaikar Edge detection using the fuzzy control paradigm Proc 2nd European Congress on Intelligent Techniques and Soft Computing, Verlag der Augustinus Buchhandlung, Aachen, 1994, Vol 1, pp 1-12. [10] M.J. Black et al Robust Anisotropic Diffusion IEEE Transactions on Image Processing, Volume 7/3, 1998 [11] Robert M. Haralick Digital step edges from zero crossings of second directional derivatives IEEE Transactions on Pattern analysis and machine intelligence, Volume 6, pp. 58-68, 1984

37

[12] O.A. Zuniga, Robert M. Haralick Integrated directional derivative gradient operator IEEE Transactions on Systems, Man and Cybernetics, pp. 508 - 517, 1987 [13] Qiang Ji, Robert M. Haralick. Efficient Facet Edge Detection and quantitative performance evaluation . The Journal Of The Pattern Recognition Society. 2002 (35), pp 689-700 ˙ Avcıba¸s, B. Sankur, K. Sayood [14] I. Statistical evaluation of image quality measures Journal of Electronic Imaging 11(2), pp. 206 - 223, 2002 [15] T.Y. Zang, C.Y. Suen A Fast Parallel Algorithm for Thinning Digital Patterns Communications of the ACM, Volume 27, pp. 236 - 239, 1984 [16] Henning B¨ assmann, Philipp W. Besslich Konturorientierte Verfahren in der digitalen Bildverarbeitung Springer-Verlag-Berlin, 1989

38