Brontekst bekijken van 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.

[[Bestand:Valve monochrome canny (6).PNG|thumb|300px|right|De Canny-randzoeker toegepast op een kleurenfoto van een stoommachine. (Zie de oorspronkelijke afbeelding [https://en.wikipedia.org/wiki/File:Valve_original_(1).PNG hier])]]

== Ontwikkeling van het Canny-algoritme ==
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 (wiskunde)|functie]] die een gegeven [[functionaal]] optimaliseert. De optimale functie in de Canny-zoeker wordt beschreven door de som van vier [[Exponentiële functie|exponentiële]] termen, maar kan worden benaderd door de eerste [[afgeleide]] van een [[Gaussische functie|Gaussiaan]].

== Stadia van het Canny-algoritme ==
=== [[Beeld ruisonderdrukking|Ruisonderdrukking]] ===
[[Bestand:Valve gaussian (2).PNG|thumb|200px|right|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 [[convolutie|geconvolueerd]] met een Gaussisch filter. Het resultaat is een enigszins [[Gaussian blur|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 <math>\sigma=1{,}4</math>:

:<math>
\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}
</math>

=== Het vinden van de intensiteit van de gradiënt van het beeld ===
[[Bestand:Valve sobel with angle colour (4).PNG|thumb|200px|left|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: 

<math>\mathbf{G} = \sqrt{ {\mathbf{G}_x}^2 + {\mathbf{G}_y}^2 }</math>

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

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).
<!-- Dit moet eerst verbeterd worden
=== Niet-maximale suppressie ===
[[Bestand:Valve canny with angle colour (7).PNG|thumb|200px|right| Dezelfde binaire kaart getoond aan de linkerzijde na niet-maxima onderdrukking. De randen zijn nog gekleurd om de richting aan te geven.]]

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 [[binaire image|binair beeld]] is verkregen. Deze worden soms aangeduid als "dunne randen".

=== Tracing randen door het beeld en hysterese drempelmethode ===
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 [[hysterese|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 randpixel of een niet-randpixel. 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 de Canny-randzoeker ===
Een meer verfijnde benadering te verkrijgen randen met sub-pixel nauwkeurigheid is door gebruik te maken van de aanpak van [[Edge detection#Differentiële rand detectie|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 [[Edge detection#Differentiële rand detectie|rand detectie]] voor een gedetailleerde beschrijving.

== Parameters ==
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 ==
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 [[IIR|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 [[Digitale signaalprocessor|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==
* 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.
*[https://www.nada.kth.se/cvap/abstracts/cvap191.html Lindeberg, Tony "Edge detectie en kam detectie met automatische schaal selectie", International Journal of Computer Vision, 30, 2, pp 117 - 154, 1998. ][https://www.nada.kth.se/cvap/abstracts/cvap191.html (Inclusief het verschil in benadering van de niet-maximale suppressie.)]

==Zie ook==
<!-- het Engelstalige artikel linkt naar een reeks andere Engelstalige artikelen waarvan nog geen vertaling in het Nederlands is 
*[[Rand detectie|Rand detectie]]
*[[Feature detectie (computer vision)|Feature detectie (computer vision)]]
*[[Feature extractie|Feature extractie]]
*[[Schaal ruimte|Schaal ruimte]]
*[[Ridge detectie|Ridge detectie]]
*[[Computer Vision|Computer Vision]]
-->
*[[Digitale beeldbewerking|Digitale beeldverwerking]]

==Externe links==
*[https://www.cs.berkeley.edu/~jfc/ John Canny's home page]
*[https://web.archive.org/web/20090615224334/http://matlabserver.cs.rug.nl/ online Canny-randzoeker]
*[https://web.archive.org/web/20110703043249/http://www.tomgibara.com/computer-vision/canny-edge-detector Gratis Java-implementatie van Canny-randzoeker]
*[http://www-sop.inria.fr/odyssee/team/Rachid.Deriche/Publications/RD.references.html Publicatie Lijst van Rachid Deriche]

[[Categorie:Digitale beeldverwerking]]
[[Categorie:Algoritme]]