Canny-randzoeker

De Canny-randzoeker is een methode, ontwikkeld door John F. Canny in 1986, die gebruikmaakt van een multi-stage algoritme voor het opsporen van een breed scala van randen in beelden. Canny ontwikkelde ook een computational theory of edge detection voor de verklaring van de techniek.

Ontwikkeling van het Canny-algoritme bewerken

Canny's doel was het 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 - een punt van een gemarkeerde rand moet zo goed mogelijk liggen in het midden van de rand in het beeld.
minimale reactie - een bepaalde rand in de afbeelding dient slechts eenmaal te worden gemarkeerd, en waar mogelijk mag beeldruis geen valse randen geven.

Om aan deze eisen te voldoen maakte Canny gebruik van variatierekening, een techniek voor het bepalen van de functie die een gegeven 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. Daarom wordt om te beginnen het ruwe beeld geconvolueerd met een Gaussisch filter. Het resultaat is een enigszins wazige versie van het origineel die niet in belangrijke mate wordt beïnvloed door een enkele dominante 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 randkaart, 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 randdetector (Roberts, Prewitt, Sobel bijvoorbeeld) geeft een waarde voor de eerste afgeleide in de horizontale richting (Gx) en de verticale richting (Gy). 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).

Differentiële meetkundige formulering van de 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

Canny, J., A Computational Approach to Edge Detection, IEEE Trans. Pattern Analysis and Machine Intelligence, 8:679-714, 1986.
R. Deriche, gebruik van Canny de criteria voor de afleiding van een optimale rand detector recursief geïmplementeerd, Int. J. Computer Vision, Vol. 1, pp. 167-187, april 1987.
Lindeberg, Tony "Edge detectie en kam detectie met automatische schaal selectie", International Journal of Computer Vision, 30, 2, pp 117 - 154, 1998. (Inclusief het verschil in benadering van de niet-maximale suppressie.)

Zie ook bewerken

Digitale beeldverwerking