Canny kantdetektor

Canny-kantdetektorn appliceras på ett färgfotografi av en ångmaskin.

Originalbilden.

Canny kantdetektorn är en kantdetekteringsoperatör som använder en flerstegsalgoritm för att detektera ett brett spektrum av kanter i bilder . Den utvecklades av John F. Canny 1986. Canny producerade också en beräkningsteori för kantdetektering som förklarar varför tekniken fungerar.

Utveckling

Canny edge-detektion är en teknik för att extrahera användbar strukturell information från olika visionobjekt och dramatiskt minska mängden data som ska bearbetas. Det har använts i stor utsträckning i olika datorseendesystem . Canny har funnit att kraven för tillämpning av kantdetektering på olika synsystem är relativt lika. Således kan en kantdetekteringslösning för att möta dessa krav implementeras i ett brett spektrum av situationer. De allmänna kriterierna för kantdetektering inkluderar:

Detektering av kant med låg felfrekvens, vilket innebär att detekteringen korrekt ska fånga upp så många kanter som visas i bilden som möjligt
Kantpunkten som detekteras från operatören bör lokaliseras exakt till mitten av kanten.
En given kant i bilden ska bara markeras en gång och där det är möjligt ska bildbrus inte skapa falska kanter.

För att uppfylla dessa krav använde Canny variationskalkylen – en teknik som hittar den funktion som optimerar en given funktion . Den optimala funktionen i Cannys detektor beskrivs av summan av fyra exponentialtermer , men den kan approximeras av förstaderivatan av en Gauss .

Bland de kantdetekteringsmetoder som hittills utvecklats är Canny edge detektionsalgoritm en av de mest strikt definierade metoderna som ger bra och tillförlitlig detektering. På grund av dess optimalitet för att uppfylla de tre kriterierna för kantdetektering och enkelheten i processen för implementering, blev den en av de mest populära algoritmerna för kantdetektering.

Bearbeta

Processen för Canny edge-detektionsalgoritm kan delas upp i fem olika steg:

Använd gaussiskt filter för att jämna ut bilden för att ta bort bruset
Hitta bildens intensitetsgradienter
Tillämpa tröskelvärde för gradientstorlek eller undertryckning av nedre gränsgräns för att bli av med falsk respons på kantdetektering
Använd dubbel tröskel för att bestämma potentiella kanter
Spårkant genom hysteres : Slutför detekteringen av kanter genom att undertrycka alla andra kanter som är svaga och inte anslutna till starka kanter.

Gaussiskt filter

Bilden efter en 5×5 Gaussisk mask har passerats över varje pixel.

Eftersom alla resultat av kantdetektering lätt påverkas av bruset i bilden, är det viktigt att filtrera bort bruset för att förhindra falsk detektering som orsakas av det. För att jämna ut bilden viks en gaussisk filterkärna ihop med bilden. Detta steg kommer att jämna ut bilden något för att minska effekterna av uppenbart brus på kantdetektorn. Ekvationen för en gaussisk filterkärna med storlek (2 k +1)×(2 k +1) ges av:

$H_{ij}={\frac {1}{2\pi \sigma ^{2}}}\exp \left(-{\frac {(i -(k+1))^{2}+(j-(k+1))^{2}}{2\sigma ^{2}}}\right);1\leq i,j\leq (2k +1)$

Här är ett exempel på ett 5×5 Gaussiskt filter, som används för att skapa den intilliggande bilden, med $\sigma$ = 1. (Asterisken anger en faltningsoperation .)

\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\}A {\thmatrix .

Det är viktigt att förstå att valet av storleken på den Gaussiska kärnan kommer att påverka detektorns prestanda. Ju större storleken är, desto lägre är detektorns känslighet för brus. Dessutom kommer lokaliseringsfelet för att detektera kanten att öka något med ökningen av den gaussiska filterkärnan. En 5×5 är en bra storlek för de flesta fall, men det kommer också att variera beroende på specifika situationer.

Hitta bildens intensitetsgradient

En kant i en bild kan peka i en mängd olika riktningar, så Canny-algoritmen använder fyra filter för att upptäcka horisontella, vertikala och diagonala kanter i den suddiga bilden. Kantdetekteringsoperatorn (som Roberts , Prewitt eller Sobel ) returnerar ett värde för den första derivatan i horisontell riktning (G _x ) och vertikal riktning (G _y ). Från detta kan kantgradienten och riktningen bestämmas:

Gradientriktning

\mathbf {G} ={\sqrt {{\mathbf {G} _{x}}^{2}+{\mathbf {G} _{y}}^ {2}}}

\mathbf {\Theta } =\operatörsnamn {atan2} \left(\mathbf {G} _{y},\mathbf {G} _{x}\right)

,

där G kan beräknas med hypotfunktionen och atan2 är arctangensfunktionen med två argument. Kantriktningsvinkeln avrundas till en av fyra vinklar som representerar vertikal, horisontell och de två diagonalerna (0°, 45°, 90° och 135°). En kantriktning som faller i varje färgområde kommer att ställas in på ett specifikt vinkelvärde, till exempel θ i [0°, 22,5°] eller [157,5°, 180°] kartor till 0°.

Gradient magnitud tröskel eller nedre gräns cut-off undertryckning

Minsta cut-off-undertryckning av gradientstorlekar, eller nedre gränströskelvärde, är en kantförtunningsteknik .

Undertryckning av nedre gränsgräns tillämpas för att hitta platserna med den skarpaste förändringen av intensitetsvärdet. Algoritmen för varje pixel i gradientbilden är:

Jämför kantstyrkan för den aktuella pixeln med pixelns kantstyrka i positiva och negativa gradientriktningar.
Om kantstyrkan för den aktuella pixeln är störst jämfört med de andra pixlarna i masken med samma riktning (t.ex. en pixel som pekar i y-riktningen kommer att jämföras med pixeln ovanför och under den i den vertikala axeln ), kommer värdet att bevaras. Annars kommer värdet att undertryckas.

I vissa implementeringar kategoriserar algoritmen de kontinuerliga gradientriktningarna i en liten uppsättning diskreta riktningar och flyttar sedan ett 3x3 filter över resultatet från föregående steg (det vill säga kantstyrkan och gradientriktningarna). Vid varje pixel undertrycker den kantstyrkan hos mittpixeln (genom att sätta dess värde till 0) om dess storlek inte är större än storleken på de två grannarna i gradientriktningen. Till exempel,

om den rundade gradientvinkeln är 0° (dvs. kanten är i nord–sydlig riktning) kommer punkten att anses vara på kanten om dess gradientstorlek är större än storleken vid pixlar i öster och väster .
om den rundade gradientvinkeln är 90° (dvs. kanten är i öst–västlig riktning) kommer punkten att anses vara på kanten om dess gradientstorlek är större än storleken vid pixlar i nord- och sydriktningen ,
om den rundade gradientvinkeln är 135° (dvs kanten är i nordost–sydvästlig riktning) kommer punkten att anses vara på kanten om dess gradientstorlek är större än storleken vid pixlar i nordväst och sydost vägbeskrivningar,
om den rundade gradientvinkeln är 45° (dvs. kanten är i nordväst–sydöstlig riktning) kommer punkten att anses vara på kanten om dess gradientstorlek är större än storleken vid pixlar i nordost och sydväst vägbeskrivningar.

I mer exakta implementeringar används linjär interpolation mellan de två angränsande pixlarna som gränsar över gradientriktningen. Till exempel, om gradientvinkeln är mellan 89° och 180°, kommer interpolering mellan gradienter vid nord- och nordöstra pixlar att ge ett interpolerat värde, och interpolation mellan syd- och sydvästra pixlar ger det andra (med användning av konventionerna i sista stycket). Gradientstorleken vid den centrala pixeln måste vara större än båda dessa för att den ska markeras som en kant.

Observera att riktningens tecken är irrelevant, dvs nord–syd är detsamma som syd–nord och så vidare.

Dubbel tröskel

Efter applicering av icke-maximal undertryckning ger återstående kantpixlar en mer exakt representation av verkliga kanter i en bild. Det finns dock kvar några kantpixlar som orsakas av brus och färgvariationer. För att ta hänsyn till dessa falska svar är det viktigt att filtrera bort kantpixlar med ett svagt gradientvärde och bevara kantpixlar med ett högt gradientvärde. Detta uppnås genom att välja höga och låga tröskelvärden. Om en kantpixels gradientvärde är högre än det höga tröskelvärdet markeras den som en stark kantpixel. Om en kantpixels gradientvärde är mindre än det höga tröskelvärdet och större än det låga tröskelvärdet markeras det som en svag kantpixel. Om en kantpixels gradientvärde är mindre än det låga tröskelvärdet kommer det att undertryckas. De två tröskelvärdena är empiriskt bestämda och deras definition kommer att bero på innehållet i en given ingångsbild.

Kantspårning genom hysteres

Canny kantdetektering tillämpas på ett fotografi

De starka kantpixlarna bör verkligen vara involverade i den slutliga kantbilden; de anses komma från verkliga kanter i bilden. Det kommer dock att bli en del debatt om de svaga kantpixlarna. Vi vill avgöra om dessa pixlar kommer från en sann kant, eller brus/färgvariationer. Svag kantpixlar bör tas bort från övervägande om det är det senare. Denna algoritm använder tanken att svaga kantpixlar från sanna kanter (vanligtvis) kommer att kopplas till starka kantpixlar medan brusreaktioner inte är sammankopplade. För att spåra kantanslutningen blobanalys genom att titta på en svag kantpixel och dess 8-anslutna grannskapspixlar. Så länge det finns en stark kantpixel som är involverad i bloben, kan den svaga kantpunkten identifieras som en som bör bevaras. Dessa svaga kantpixlar blir starka kanter som sedan kan göra att deras närliggande svaga kantpixlar bevaras.

Genomgång av algoritmen

Det här avsnittet visar hur en bild fortskrider genom vart och ett av de fem stegen.

Originalbilden

Bilden har reducerats till gråskala och ett 5x5 Gaussiskt filter med σ=1,4 har tillämpats

Intensitetsgradienten för föregående bild. Bildens kanter har hanterats genom replikering.

Icke-maximal undertryckning tillämpas på föregående bild.

Dubbel tröskelvärde tillämpas på föregående bild. Svaga pixlar är de med ett gradientvärde mellan 0,1 och 0,3. Starka pixlar har ett gradientvärde som är större än 0,3

Hysteres tillämpas på föregående bild

Förbättringar

Medan traditionell Canny-kantdetektering tillhandahåller en relativt enkel men exakt metod för kantdetekteringsproblemet, med mer krävande krav på noggrannhet och robusthet på detekteringen, kan den traditionella algoritmen inte längre hantera den utmanande kantdetekteringsuppgiften. De huvudsakliga bristerna i den traditionella algoritmen kan sammanfattas enligt följande:

Ett Gaussiskt filter används för att jämna ut bruset, men det kommer också att jämna ut kanten, vilket anses vara högfrekvensfunktionen. Detta kommer att öka möjligheten att sakna svaga kanter, och uppkomsten av isolerade kanter i resultatet.
För beräkningen av gradientamplituden använder den gamla Canny-kantdetekteringsalgoritmen mitten i ett litet 2×2 grannskapsfönster för att beräkna medelvärdet för den finita skillnaden för att representera gradientamplituden. Denna metod är känslig för brus och kan lätt upptäcka falska kanter och tappa verkliga kanter.
I den traditionella Canny edge-detekteringsalgoritmen kommer det att finnas två fasta globala tröskelvärden för att filtrera bort de falska kanterna. Men eftersom bilden blir komplex kommer olika lokala områden att behöva mycket olika tröskelvärden för att exakt hitta de verkliga kanterna. Dessutom bestäms de globala tröskelvärdena manuellt genom experiment i den traditionella metoden, vilket leder till en komplexitet i beräkningen när ett stort antal olika bilder behöver hanteras.
Resultatet av den traditionella detekteringen kan inte nå en tillfredsställande hög noggrannhet av ett enda svar för varje kant - flerpunktssvar kommer att visas.

För att komma till rätta med dessa defekter presenteras en förbättring av canny edge-algoritmen i följande stycken.

Byt gaussiskt filter

Eftersom både kant och brus kommer att identifieras som en högfrekvent signal, kommer ett enkelt Gaussiskt filter att lägga till en jämn effekt på dem båda. För att uppnå hög noggrannhet för detektering av den verkliga kanten förväntas det emellertid att en jämnare effekt bör appliceras på brus och en mindre jämn effekt bör läggas till kanten. Bing Wang och Shaosheng Fan från Changsha University of Science and Technology utvecklade ett adaptivt filter, där filtret kommer att utvärdera diskontinuitet mellan gråskalevärden för varje pixel [ ^{citat behövs ]} . Ju högre diskontinuitet, desto lägre vikt ställs in för det jämna filtret vid den punkten. Ju lägre diskontinuitet mellan gråskalevärdena är, desto högre ställs viktvärdet på filtret. Processen för att implementera detta adaptiva filter kan sammanfattas i fem steg:

1. K = 1, ställ in iterationen n och koefficienten för amplituden för kanten h.

2. Beräkna gradientvärdet

G_{x}(x,y)

och

G_{y}(x,y)

3. Beräkna vikten enligt formlerna nedan:

$d(x,y)={\sqrt {G_{x}(x,y)^{2 }+G_{y}(x,y)^{2}}}$

$w(x,y)=\exp \left(-{\frac {\sqrt {d(x,y) }}{2h^{2}}}\höger)$

4. Definitionen av det adaptiva filtret är:

$f(x,y) ={\frac {1}{N}}\summa \limits _{i=-1}^{1}\summa \limits _{j=-1}^{1}f(x+i,y+j )w(x+i,y+j)$

för att jämna ut bilden, var

$N=\summa \limits _{i=-1}^{1}\summa \limits _{ j=-1}^{1}w(x+i,y+j)$

5. När K = n, stoppa iterationen, annars, k = k+1, fortsätt med det andra steget

Förbättring av gradientstorlek och riktningsberäkning

Gradientens storlek och riktning kan beräknas med en mängd olika kantdetekteringsoperatörer, och valet av operatör kan påverka kvaliteten på resultaten. Ett mycket vanligt valt är 3x3 Sobel- filtret. Däremot kan andra filter vara bättre, till exempel ett 5x5 Sobel-filter, som minskar brus, eller Scharr- filtret, som har bättre rotationssymmetri. Andra vanliga val är Prewitt (används av Zhou) och Roberts Cross .

Robust metod för att bestämma dubbeltröskelvärdet

För att lösa de utmaningar där det är svårt att bestämma dubbeltröskelvärdet empiriskt, kan Otsus metod användas på den icke-maximala undertryckta gradientstorleksbilden för att generera det höga tröskelvärdet. Den låga tröskeln är vanligtvis inställd på 1/2 av den höga tröskeln i detta fall. Eftersom gradientstorleksbilden är kontinuerligt värderad utan ett väldefinierat maximum, måste Otsus metod anpassas för att använda värde/räknepar istället för ett komplett histogram.

Kantens gallring

Medan den traditionella Canny-kantdetekteringen implementerar ett bra detekteringsresultat för att uppfylla de två första kriterierna, uppfyller den inte strikt det enda svaret per kant. En matematisk morfologiteknik för att tunna ut den detekterade kanten har utvecklats av Mallat S och Zhong.

Användning av kurvor

Kurveler har använts i stället för Gauss-filtret och gradientuppskattning för att beräkna ett vektorfält vars riktningar och magnituder approximerar riktningen och styrkan hos kanterna i bilden, på vilket steg 3 - 5 i Canny-algoritmen sedan tillämpas. Kurveler bryter ner signaler till separata komponenter av olika skalor, och att tappa komponenterna i finare skalor kan minska brus.

Differentiell geometrisk formulering

Ett mer förfinat tillvägagångssätt för att erhålla kanter med subpixelnoggrannhet är att använda metoden för differentiell kantdetektering, där kravet på icke-maximal undertryckning formuleras i termer av andra och tredje ordningens derivator beräknade från en skalrumsrepresentation (Lindeberg 1998) – se artikeln om kantdetektering för en detaljerad beskrivning.

Variationsformulering av Haralick-Canny kantdetektorn

En variationsförklaring för huvudingrediensen i Canny-kantdetektorn, det vill säga att hitta nollgenomgångarna för 2:a derivatan längs gradientriktningen, visade sig vara resultatet av att minimera en Kronrod-Minkowski-funktion och samtidigt maximera integralen över inriktningen av kanten med gradientfältet (Kimmel och Bruckstein 2003). Se artikeln om regulariserade Laplacian nollkorsningar och andra optimala kantintegratorer för en detaljerad beskrivning.

Parametrar

Canny-algoritmen innehåller ett antal justerbara parametrar, som kan påverka beräkningstiden och effektiviteten av algoritmen.

Storleken på Gauss-filtret: utjämningsfiltret som används i det första steget påverkar direkt resultaten av Canny-algoritmen. Mindre filter orsakar mindre suddighet och tillåter detektering av små, skarpa linjer. Ett större filter orsakar mer oskärpa, och smetar ut värdet på en given pixel över ett större område av bilden. Större suddighetsradier är mer användbara för att upptäcka större, jämnare kanter – till exempel kanten på en regnbåge.
Tröskelvärden: användningen av två tröskelvärden med hysteres ger mer flexibilitet än en enkeltröskelmetod, men generella problem med tröskelmetoder gäller fortfarande. En för hög tröskel kan missa viktig information. Å andra sidan kommer en för låg tröskel att felaktigt identifiera irrelevant information (som brus) som viktig. Det är svårt att ge en generisk tröskel som fungerar bra på alla bilder. Ingen beprövad metod för detta problem finns ännu.

Slutsats

Canny-algoritmen är anpassningsbar till olika miljöer. Dess parametrar gör att den kan skräddarsys för att känna igen kanter med olika egenskaper beroende på de särskilda kraven för en given implementering. I Cannys originalpapper ledde härledningen av det optimala filtret till ett Finite Impulse Response- filter, som kan vara långsamt att beräkna i den spatiala domänen om mängden utjämning som krävs är viktig (filtret kommer att ha ett stort rumsligt stöd i så fall) . Av denna anledning föreslås det ofta att man använder Rachid Deriches oändliga impulssvarsform av Cannys filter ( Canny–Deriche-detektorn ), som är rekursiv och som kan beräknas på en kort, fast tidsperiod för vilken önskad mängd utjämning som helst. . Den andra formen är lämplig för realtidsimplementationer i FPGA eller DSP , eller mycket snabba inbyggda datorer. I detta sammanhang ger dock den regelbundna rekursiva implementeringen av Canny-operatorn ingen bra approximation av rotationssymmetri och ger därför en bias mot horisontella och vertikala kanter.

Se även

Canny, J., A Computational Approach To Edge Detection , IEEE Transactions on Pattern Analysis and Machine Intelligence, 8(6):679–698, 1986.
R. Deriche, Använda Cannys kriterier för att härleda en rekursivt implementerad optimal kantdetektor , Int. J. Computer Vision, vol. 1, s. 167–187, april 1987.
Lindeberg, Tony "Edge detection and ridge detection with automatic scale selection", International Journal of Computer Vision, 30, 2, pp 117—154, 1998. (Inkluderar differential approach to non-maximum suppression.)
Kimmel, Ron och Bruckstein, Alfred M. "On regularized Laplacian zero crossings and other optimal edge integrators", International Journal of Computer Vision, 53(3):225–243, 2003. (Inkluderar den geometriska variationstolkningen för Haralick–Canny kantdetektor.)
Moeslund, T. (2009, 23 mars). Canny Edge Detection. Hämtad 3 december 2014
Thomas B. Moeslund. Bild- och videobehandling. augusti 2008
Green, B. (2002, 1 januari). Handledning för Canny Edge Detection. Hämtad 3 december 2014 ; arkiveras här

externa länkar