Kantmarkering

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 26 juni 2016; kontroller kräver 14 redigeringar .

Kantdetektering ( kantdetektion ) - en term i teorin om bildbehandling och datorseende , delvis från området objektsökning och objektval, bygger på algoritmer som väljer punkter i en digital bild där ljusstyrkan ändras kraftigt eller det finns andra typer av inhomogeniteter.

Utnämning

Huvudsyftet med att upptäcka skarpa förändringar i bildens ljusstyrka är att fånga viktiga händelser och förändringar i världen. De kan återspegla olika antaganden om bildmodellen, förändringar i bildens ljusstyrka kan indikera:

djupförändringar;
förändringar av ytorientering;
förändringar i materialegenskaper;
skillnad i scenbelysning.

Helst är resultatet av gränsval en uppsättning relaterade kurvor som representerar gränserna för objekt, ansikten och intryck på en yta, såväl som kurvor som representerar förändringar i ytornas position. Således kan applicering av ett kantdetekteringsfilter på en bild avsevärt minska mängden data som bearbetas på grund av det faktum att den filtrerade delen av bilden anses vara mindre signifikant, och de viktigaste strukturella egenskaperna hos bilden bevaras. Det är dock inte alltid möjligt att särskilja gränserna i bilder av den verkliga världen av medium komplexitet. De gränser som extraheras från sådana bilder har ofta sådana brister som fragmentering (gränsernas kurvor är inte kopplade till varandra), frånvaron av gränser eller förekomsten av falska gränser som inte motsvarar det föremål som studeras.

Kantegenskaper

Gränserna som markeras i en 2D-bild av en 3D-scen kan delas in i synvinkelberoende eller synvinkeloberoende. Synvinkeloberoende gränser återspeglar vanligtvis egenskaper som ärvts från objekt i en 3D-scen, såsom ytfärgning och form. Synpunktsberoende gränser kan ändras med synpunkten och reflektera scenens geometri, till exempel överlappande objekt.

En normal kant kan till exempel vara en kant mellan röda och gula block. Å andra sidan kan en linje vara en uppsättning pixlar av en annan färg på en konstant bakgrund. Därför kan en linje ha en kant på varje sida av den.

Kanter är ganska viktiga i många bildbehandlingstillämpningar, särskilt i maskinseendesystem som analyserar scener av konstgjorda föremål under fasta ljusförhållanden. Under de senaste åren har det dock gjorts konsekventa (och framgångsrika) studier av datorseendemetoder som inte förlitar sig på kantdetektering som ett förbearbetningssteg.

En enkel gränsmodell

Även om en del litteratur överväger valet av idealiska kanter, är kanterna i en naturlig bild vanligtvis inte det. De påverkas vanligtvis av en eller flera av följande effekter:

Fokusoskärpa på grund av ändligt skärpedjup,
Suddig penumbra från icke-punkt ljuskällor,
Skuggning av släta föremål,

och därför använder många forskare den stegade kanten som utjämnas av en Gaussisk funktion (felfunktion) som den enklaste approximationen av den ideala kantmodellen för att modellera suddiga gränser i tillämpade problem. Således kan en endimensionell bild som har exakt en kant vid en punkt modelleras som: $f$ $x=0$

$f(x)={\frac {I_{r}-I_{l}}{2}}\left(\operatörsnamn {erf} \left({\frac {x}{{\sqrt {2} }\sigma }}\right)+1\right)+I_{l}.$

Här

\operatorname {erf} \,\left(u\right)={\frac {2}{\sqrt {\pi }}}\int \limits _{0}^{u}e^{-t ^{2}}\,dt

Till vänster om gränsen finns ljusstyrka , till höger - . Parametern kallas storleken på kantskärpa. $I_{l}=\lim _{x\rightarrow -\infty }f(x)$ $I_{r}=\lim _{x\rightarrow \infty }f(x)$ $\sigma$

Varför gränsval inte är en trivial uppgift

För att illustrera varför kantdetektering är ett icke-trivialt problem, överväg problemet med kantdetektering på följande endimensionella signal. Här kan vi direkt intuitivt säga att gränsen ska ligga mellan den 4:e och 5:e pixeln.

5	7	6	fyra	152	148	149

Om förändringen i ljusstyrka mellan den 4:e och 5:e pixeln var mindre, och förändringen i ljusstyrka mellan deras grannar var större, skulle det inte längre vara så lätt att säga att gränsen skulle vara på denna plats. Dessutom kan man hävda att det borde finnas mer än en gräns överhuvudtaget.

5	7	6	41	113	148	149

Att hårdfixa en viss tröskel för vad förändringen i ljusstyrka mellan två intilliggande pixlar ska vara, så att vi kan säga att det finns en gräns, är därför inte alltid en lätt uppgift. Detta är en av anledningarna till att kantdetektering inte är en trivial uppgift, om inte objekten i scenen är ganska enkla och ljusförhållandena är väl anpassade.

Tillvägagångssätt för gränsdetektering

Det finns många tillvägagångssätt för kantdetektering, men nästan allt kan delas in i två kategorier: metoder baserade på sökning efter maxima och metoder baserade på sökning efter nollor. Toppbaserade metoder framhäver kanter genom att beräkna "kantstyrkan", vanligtvis ett förstaderivatuttryck som gradientens storlek, och sedan leta efter lokala maxima för kantstyrkan med hjälp av kantens antagna riktning, vanligtvis vinkelrät mot gradienten vektor. Nollbaserade metoder letar efter skärningspunkter för abskissan för det andra derivatuttrycket, typiskt nollor för Laplacian eller nollor för ett icke-linjärt differentiellt uttryck, vilket kommer att beskrivas senare. Som ett förbearbetningssteg tillämpas bildutjämning nästan alltid på kantdetektering, vanligtvis med ett gaussiskt filter.

De publicerade kantdetekteringsmetoderna skiljer sig åt i de anbringade kantutjämningsfiltren och i hur kantstyrkan beräknas. Även om många kantdetekteringsmetoder förlitar sig på att beräkna gradienten för en bild, skiljer de sig åt i de typer av filter som används för att beräkna gradienterna i x- och y-riktningarna.

Markera Cannys gränser

John Cannystuderat det matematiska problemet att få fram ett filter som är optimalt vad gäller urval, lokalisering och minimering av flera svar på en kant. Han visade att det önskade filtret är summan av fyra exponentialer. Han visade också att detta filter kan approximeras väl av den första derivatan av Gauss. Canny introducerade konceptet Non-Maximum Suppression (undertryckning av icke-maximum), vilket innebär att kantpixlarna är deklarerade pixlar där det lokala maximumet för gradienten i gradientvektorns riktning nås.

Även om hans arbete gjordes i de tidiga dagarna av datorseende, är Canny kantdetektorn fortfarande en av de bästa detektorerna idag. Förutom i speciella fall är det svårt att hitta en detektor som presterar betydligt bättre än Canny-detektorn.

Canny-Deriché-detektorn härleddes från ett liknande matematiskt kriterium som Canny-detektorn, även om det från en annan synvinkel resulterade i en uppsättning rekursiva filter för bildutjämning istället för exponentiella och Gaussiska filter.

Andra första ordningens metoder

För att uppskatta storleken på en bildgradient eller dess utjämnade version kan olika gradientoperatorer användas. Det enklaste tillvägagångssättet är att använda centrala skillnader:

L_{x}(x,y)=-1/2\cdot L(x-1,y)+0\cdot L(x,y)+1/2\cdot L(x+1,y ).

L_{y}(x,y)=-1/2\cdot L(x,y-1)+0\cdot L(x,y)+1/2\cdot L(x,y+1 ).

motsvarande tillämpningen av följande filter på bilden:

L_{x}={\begin{bmatrix}-1/2&0&1/2\end{bmatrix}}*L\quad {\mbox{and}}\quad L_{y}={\begin{bmatrix} +1/2\\0\\-1/2\end{bmatrix}}*L

Den välkända Sobel-operatören är baserad på följande filter:

L_{x}={\begin{bmatrix}-1&0&+1\\-2&0&+2\\-1&0&+1\end{bmatrix}}*L\quad {\mbox{and}}\quad L_ {y}={\begin{bmatrix}+1&+2&+1\\0&0&0\\-1&-2&-1\end{bmatrix}}*L

Med dessa uppskattningar kan vi beräkna gradientens storlek enligt följande:

{\displaystyle |\nabla L|={\sqrt {L_{x}^{2}+L_{y}^{2))))

och gradientens riktning beräknas så här:

\theta =\operatörsnamn {atan2} (L_{y},L_{x})

Andra operatorer för att beräkna gradienten för en bild föreslogs av Judith Prewitt och Lawrence Roberts och är kända som Pruitt-operatorn respektive Roberts-korsoperatorn .

Tröskelvärde och poolning

När vi har hittat styrkan på gränsen (vanligtvis gradientens storlek), är nästa steg att tillämpa en tröskel för att avgöra om gränsen är vid en given punkt i bilden. Ju mindre tröskeln är, desto fler kanter blir det, men desto mer känsligt blir resultatet för brus, vilket framhäver onödig bilddata. Omvänt kan en hög tröskel missa svaga kanter eller få en kant i fragment.

Om tröskeln appliceras helt enkelt på bilden med gradientstorlek, kommer de resulterande gränserna att bli tjocka och viss efterbearbetning kommer att krävas för att göra kanten tunn och exakt. Om gränserna däremot väljs med hjälp av icke-maximal undertryckning, kommer gränserna att vara tunna per definition och kan sammanfogas till polygoner genom proceduren för kantfogning (gränsspårning). På ett diskret rutnät kan det icke-maximala undertryckningssteget implementeras genom att uppskatta gradientriktningen med hjälp av förstaderivator, avrunda riktningen med värden i 45-graderssteg och slutligen jämföra gradientvärdena i den resulterande gradientriktningen.

Den traditionella metoden för att lösa problemet med att hitta en lämplig tröskel är "sena" trösklar. Metoden använder flera trösklar. Vi använder den övre tröskeln för att hitta gränsens startpunkt. När vi väl har en startpunkt spårar vi kanten, punkt för punkt, tills kantstyrkan ligger över den nedre tröskeln. Denna algoritm antar att kanterna med största sannolikhet är kontinuerliga kurvor och tillåter oss att spåra de svaga områdena på kanterna utan antagandet att alla brusiga punkter i bilden kommer att märkas som kanter. Men det finns fortfarande problemet med att välja lämpliga tröskelvärden för denna metod, eftersom de optimala parametrarna kan variera från bild till bild.

Gränsförfining

Gränsförfining är en process som gör gränser tunna genom att ta bort oönskade falska punkter som visas på gränsen. Denna teknik tillämpas efter att bilden har utjämnats (med ett median- eller gaussiskt filter), en kantoperator (som den som beskrivs ovan) har tillämpats för att beräkna kantstyrkan och efter att kanterna har rensats med lämpliga trösklar. Den här metoden tar bort alla oönskade punkter och, när den tillämpas försiktigt, produceras kanter som är en pixel tjocka.

Fördelar:

skarpa och tunna kanter förbättrar effektiviteten i objektigenkänningen
När du använder Hough-transformen för att detektera linjer eller ellipser ger tunna kanter betydligt bättre resultat
om gränsen är gränsen till något område, låter tunna gränser dig beräkna parametrar som omkretsen utan någon komplicerad aritmetik

Det finns många populära metoder för att lösa detta problem. En av dem beskrivs nedan:

Välj anslutningstyp: 8, 6 eller 4
- 8-anslutning är att föredra, vilket tar hänsyn till alla pixlar som omedelbart omger den aktuella pixeln
Ta bort punkter ovanför, under, till vänster och höger om en punkt
- Detta bör göras i flera omgångar, det vill säga först ta bort punkter i en riktning, sedan ta bort punkter i den andra riktningen på den bearbetade bilden.
- Punkten tas bort i följande fall:
  1. Denna punkt har inga grannar ovanifrån (vid bearbetning av den "övre" riktningen, annars - i motsvarande riktning)
  2. Denna punkt är inte slutet på raden
  3. Att ta bort den här punkten kommer inte att påverka anslutningen för dess grannar på något sätt.
  4. ELLER är det en isolerad punkt
- Annars tas inte punkten bort.
Det föregående steget kan upprepas flera gånger, beroende på den önskade nivån av "prydlighet" av gränsen.

Andra ordningens tillvägagångssätt för gränsdetektering

Vissa kantvalsoperatorer använder andraderivator av bildens ljusstyrka istället för att arbeta med en gradient. Detta bestämmer naturligtvis styrkan på gradientförändringen. Således, i det ideala fallet, kommer att hitta nollorna för den andra derivatan att göra det möjligt att hitta de lokala maxima för gradienten.

Marr-Hildreth-operatorn är baserad på att beräkna rötterna för Laplace-operatorn som appliceras på en bild som utjämnas av ett Gaussiskt filter. Den här operatorn har dock visat sig markera falska kanter i homogena områden av bilden där gradienten har ett lokalt minimum. Dessutom lokaliserade denna operatör dåligt rundade kanter. Därför är denna operatör nu snarare av historiskt värde.

Differentiell kantdetektering

Ett mer avancerat sätt att detektera andra ordningens kanter, som också extraherar kanter med pixelprecision, är att använda följande differentialmetod för att detektera nollor av andraderivatan med avseende på gradientvektorns riktning.

Låt oss införa vid varje punkt i bilden ett lokalt koordinatsystem , där är riktningen parallell med gradienten. Om vi antar att bilden har jämnats ut med ett Gaussiskt filter och att skalrepresentationen på skalan har beräknats, kan vi kräva att ett gradientvärde för skalrepresentation som är lika med förstaderivatan i -riktningen har en förstaderivata i -riktningen lika med noll $(u,v)$ $v$ $L(x,y;t)$ $t$ $L_{v}$ $v$ $v$

\partial _{v}(L_{v})=0

medan andraderivatan i - riktningen från måste vara negativ, eftersom vi bara är intresserade av maxima, det vill säga: $v$ $L_{v}$

\partial _{vv}(L_{v})\leq 0

Skriven som ett explicit uttryck för lokala partiella derivator , … , kan denna kantdefinition uttryckas som nolllinjer i den differentiella invarianten ${\displaystyle L_{x))$ ${\displaystyle L_{y))$ ${\displaystyle L_{ååå))$

L_{v}^{2}L_{vv}=L_{x}^{2}\,L_{xx}+2\,L_{x}\,L_{y}\,L_{xy} +L_{y}^{2}\,L_{yy}=0,

som uppfyller följande villkor:

L_{v}^{3}L_{vvv}=L_{x}^{3}\,L_{xxx}+3\,L_{x}^{2}\,L_{y}\, L_{xxy}+3\,L_{x}\,L_{y}^{2}\,L_{xyy}+L_{y}^{3}\,L_{yyy}\leq 0

där , ... betecknar partiella derivator beräknade på skalrepresentationen som erhålls genom att filtrera originalbilden med ett Gaussiskt filter. ${\displaystyle L_{x))$ ${\displaystyle L_{y))$ ${\displaystyle L_{ååå))$ $L$

I det här fallet kommer kanterna automatiskt att vara kontinuerliga kurvor med pixelprecision. De resulterande kanterna kan dessutom appliceras på framhävning med fördröjd tröskelvärde.

I praktiken kan de första derivatorna beräknas som beskrivits tidigare, medan de andra derivatorna kan beräknas från skalningsrepresentationen enligt följande: $L$

L_{xx}(x,y)=L(x-1,y)-2L(x,y)+L(x+1,y).

L_{xy}(x,y)=(L(x-1,y-1)-L(x-1,y+1)-L(x+1,y-1)+L(x +1,y+1))/4,

L_{yy}(x,y)=L(x,y-1)-2L(x,y)+L(x,y+1).

motsvarande följande operatörer:

L_{xx}={\begin{bmatrix}1&-2&1\end{bmatrix}}*L\quad {\mbox{and}}\quad L_{xy}={\begin{bmatrix}-1/ 4&0&1/4\\0&0&0\\1/4&0&-1/4\end{bmatrix}}*L\quad {\mbox{and}}\quad L_{yy}={\begin{bmatrix}1\\-2 \\1\end{bmatrix}}*L

Derivat av högre ordning kan beräknas på liknande sätt.

Fasmatchning närmar sig

Den senaste utvecklingen inom kantdetekteringstekniker använder en frekvensmetod för kantdetektering. Fasmatchningsmetoder försöker hitta områden i bilden där alla sinusoider i frekvensrymden är i fas. Dessa områden kommer vanligtvis att motsvara områden av den upplevda kanten, oavsett hur stor förändringen i ljusstyrka är där. Den största fördelen med denna metod är att den starkt betonar " Mach-band " och undviker de typiska falska gränserna runt en grov kant.