Canny-randzoeker

Uit Wikipedia, de vrije encyclopedie
Ga naar: navigatie, zoeken

De Canny-randzoeker operator is ontwikkeld door John F. Canny in 1986 en maakt gebruik van een multi-stage algoritme voor het opsporen van een breed scala van randen in beelden. Canny ontwikkelde ook een computationele theorie van de randdetectie om uit te leggen waarom de techniek werkt.

De Canny-randzoeker toegepast op een kleurenfoto van een stoommachine. (Zie de oorspronkelijke afbeelding hier)

Ontwikkeling van het Canny algoritme[bewerken]

Canny's doel was om de optimale randdetectie-algoritme te vinden. Onder een "optimale" randdetector wordt verstaan:

  • goede detectie - het algoritme moet zo veel mogelijk echte randen in het beeld markeren.
  • goede lokalisatie - gemarkeerde randen moet zo dicht mogelijk liggen bij de rand in het beeld.
  • minimale reactie - een rand met de afbeelding dient eenmaal te worden gemarkeerd, en waar mogelijk mag beeldruis geen valse randen geven.

Om aan deze eisen te voldoen maakte Canny gebruik van de analyse van de verschillen - een techniek die de functie vindt die een bepaald functionaal optimaliseert. De optimale functie in de Canny zoeker wordt beschreven door de som van vier exponentiële termen, maar kan worden benaderd door de eerste afgeleide van een Gaussiaan.

Stadia van het Canny algoritme[bewerken]

Ruisonderdrukking[bewerken]

Het beeld nadat een 5x5 Gaussian masker is doorgegeven over elke pixel

Omdat de Canny randdetector gebruikmaakt van een filter op basis van de eerste afgeleide van een Gaussiaan, is deze gevoelig voor ruis op ruwe onbewerkte beeldgegevens, dus om te beginnen moet het ruwe beeld convolveren met een Gaussiaans filter. Het resultaat is een beetje wazige versie van het origineel die niet in belangrijke mate wordt beïnvloed door een enkele luidruchtige pixel.

Hier is een voorbeeld van een 5x5 Gaussfilter gebruikt voor het maken van de afbeelding aan de rechterkant, met \sigma = 1.4:


\mathbf{B} = \frac{1}{159} \begin{bmatrix} 
2 & 4 & 5 & 4 & 2 \\
4 & 9 & 12 & 9 & 4 \\
5 & 12 & 15 & 12 & 5 \\
4 & 9 & 12 & 9 & 4 \\
2 & 4 & 5 & 4 & 2
\end{bmatrix} * \mathbf{A}

Het vinden van de intensiteit van de gradiënt van het beeld[bewerken]

Een binaire rand kaart, afgeleid van de Sobel operator, met een drempelwaarde van 80. De randen zijn gekleurd om de richting van de rand aan te geven: geel voor nul graden, 45 graden voor groen, blauw voor 90 graden en rood voor 135 graden.

Een rand in een afbeelding kan in elke richting lopen. Daarom maakt het Canny algoritme gebruik van vier filters voor de detectie van horizontale, verticale en diagonale randen in het beeld. De rand detector (Roberts, Prewitt, Sobel bijvoorbeeld) geeft een waarde voor de eerste afgeleide in de horizontale richting (Gy) en de verticale richting (Gx). Hieruit kunnen de gradiënt en de richting worden bepaald:

\mathbf{G} = \sqrt{ {\mathbf{G}_x}^2 + {\mathbf{G}_y}^2 }

\mathbf{\Theta} = \operatorname{arctan}\left({ \mathbf{G}_y \over \mathbf{G}_x }\right)

De hoek van de randrichting wordt afgerond naar een van de vier hoeken die de verticale, horizontale en de twee diagonale richtingen vertegenwoordigen (0, 45, 90 en 135 graden, bijvoorbeeld).

Niet maximale suppressie[bewerken]

Dezelfde binaire kaart getoond aan de linkerzijde na niet-maxima onderdrukking. De randen zijn nog gekleurd om aan te geven richting.

Aangezien de ramingen van het beeld hellingen, een zoekopdracht wordt vervolgens uitgevoerd om te bepalen of de helling, de omvang ervan uitgegaan een lokale maximale helling in de richting. Dus, bijvoorbeeld,

  • indien de afgeronde hoek is nul graden het punt zal worden beschouwd als aan de rand als de intensiteit groter is dan de intensiteit in het noorden en zuiden richtingen,
  • indien de afgeronde hoek is 90 graden het punt zal worden beschouwd als aan de rand als de intensiteit groter is dan de intensiteit in het westen en oosten richtingen,
  • indien de afgeronde hoek is 135 graden het punt zal worden beschouwd als aan de rand als de intensiteit groter is dan de intensiteit in het noordoosten en zuidwesten richtingen,
  • indien de afgeronde hoek is 45 graden het punt zal worden beschouwd als aan de rand als de intensiteit groter is dan de intensiteit in het noordwesten en zuidoosten richtingen.

Dit is uitgewerkt door een 3x3 grid over de intensiteit kaart.

Vanaf dat moment aangeduid als niet-maximale suppressie, een set van rand punten, in de vorm van een binair beeld is verkregen. Deze worden soms aangeduid als "dunne randen".

Tracing randen door het beeld en hysterese drempelmethode[bewerken]

Intensiteit hellingen die groot meer kans te beantwoorden aan de randen dan wanneer ze klein zijn. Het is in de meeste gevallen onmogelijk om een drempel die op een bepaalde intensiteit kleurverloop schakelaars uit die overeenkomt met een rand in het niet te doen. Dus Canny gebruikt drempelmethode met hysteresis. Drempelmethode met hysteresis vereist twee drempels - hoog en laag. Het maken van de veronderstelling dat belangrijke randen moeten worden langs doorlopende bochten in de afbeelding kunnen we volgen een zwakke punt van een bepaalde lijn en te ontdoen van een paar drukke pixels die niet een lijn, maar hebben grote gradiënten. Daarom beginnen we door toepassing van een hoge drempel. Dit markeert de randen kunnen we vrij zeker van zijn echte. Uitgaande van deze, met behulp van de directionele informatie die eerder randen kan worden opgespoord door middel van het beeld. Terwijl de opsporing een rand, passen we de lagere drempel, zodat wij kunnen traceren zwakke delen van de randen, zolang we een uitgangspunt.

Zodra dit proces voltooid is hebben we een binaire beeld waar elke pixel wordt gemarkeerd als een rand pixel of een niet-rand pixel. Van aanvullende output van de rand tracingsystemen stap, de binaire rand kaart opgehaald op deze manier kan ook worden behandeld als een set van rand-curves, die na verdere bewerking kan worden gerepresenteerd als polygonen in het beeld domein.

Differentiële meetkundige formulering van het Canny-randzoeker[bewerken]

Een meer verfijnde benadering te verkrijgen randen met sub-pixel nauwkeurigheid is door gebruik te maken van de aanpak van differentiële rand detectie, waarbij de eis van niet-maximale suppressie wordt geformuleerd in termen van tweede-en derde-orde afgeleiden berekend uit een schaal-space vertegenwoordiging ( Lindeberg 1998) - zie het artikel over de rand detectie voor een gedetailleerde beschrijving.

Parameters[bewerken]

Het Canny-algoritme bevat een aantal instelbare parameters die van invloed kunnen zijn op de berekeningstijd en de effectiviteit van het algoritme.

  • De grootte van het Gaussiaanse filter: het afvlakfilter gebruikt in de eerste fase een rechtstreeks effect op de resultaten van het Canny-algoritme. Kleinere filters veroorzaken minder vervagingen, en detecteren kleine, scherpe lijnen. Een groter filter veroorzaakt meer vervagingen, en vegen de waarde van een pixel uit over een groter gebied van de afbeelding. Grotere vervagingsstralen zijn nuttig voor het opsporen van grotere, gladdere randen - bijvoorbeeld de rand van een regenboog.
  • Drempels: het gebruik van twee drempels met hysteresis laat meer flexibiliteit toe dan een enkele-drempelwaarde aanpak, maar de algemene problemen van drempelmethode-benaderingen nog steeds van toepassing. Een te hoge drempel kan belangrijke informatie missen. Aan de andere kant, een te lage drempel zal ten onrechte irrelevante informatie (zoals ruis) identificeren als belangrijk. Het is moeilijk om een algemene drempel in te stellen die goed werkt op alle afbeeldingen. Er is nog geen beproefde aanpak voor dit probleem.

Conclusie[bewerken]

Het Canny algoritme is aangepast aan de verschillende omgevingen. De parameters mogelijk te maken afgestemd op erkenning van de randen van de verschillende kenmerken, afhankelijk van de specifieke eisen van een bepaalde uitvoering. In Canny het oorspronkelijke papier, de afleiding van de optimale filter geleid tot een Finite Impulse Response filter, dat kan worden vertraagd om in het ruimtelijke domein als het bedrag van de egalisatie vereist is belangrijk (het filter zal een grote ruimtelijke ondersteuning in dat geval) . Om deze reden is het vaak voorgesteld gebruik te maken van Rachid Deriche 's Infinite Impulse Response vorm van Canny het filter (de Canny-Deriche detector), die is recursief, en die kan worden berekend in een korte, vaste hoeveelheid tijd voor elke gewenste bedrag van smoothing. De tweede vorm is geschikt voor realtime implementaties in FPGA s of DSP s, of zeer snel embedded pc's. In dit verband echter de reguliere uitvoering van de recursieve Canny exploitant geeft geen goede benadering van de rotatie-symmetrie en daarom geeft een vertekening naar horizontale en verticale randen.

Referenties[bewerken]

Zie ook[bewerken]

Externe links[bewerken]