Hörndetektering

Utdata från en typisk hörndetekteringsalgoritm

Hörndetektering är ett tillvägagångssätt som används inom datorseende system för att extrahera vissa typer av funktioner och härleda innehållet i en bild. Hörndetektering används ofta inom rörelsedetektering , bildregistrering , videospårning , bildmosaik , panoramasömmar , 3D-rekonstruktion och objektigenkänning . Hörndetektering överlappar ämnet för detektering av intressepunkter .

Formalisering

Ett hörn kan definieras som skärningspunkten mellan två kanter. Ett hörn kan också definieras som en punkt för vilken det finns två dominerande och olika kantriktningar i en lokal grannskap av punkten.

En intressepunkt är en punkt i en bild som har en väldefinierad position och som kan detekteras robust. Det betyder att en intressepunkt kan vara ett hörn men det kan också vara till exempel en isolerad punkt med lokalt intensitetsmaximum eller minimum, linjeslut eller en punkt på en kurva där krökningen är lokalt maximal.

I praktiken detekterar de flesta så kallade hörndetekteringsmetoder intressepunkter i allmänhet, och i själva verket används termerna "hörn" och "intressepunkt" mer eller mindre omväxlande genom litteraturen. Som en konsekvens, om endast hörn ska detekteras, är det nödvändigt att göra en lokal analys av detekterade intressepunkter för att bestämma vilka av dessa som är verkliga hörn. Exempel på kantdetektering som kan användas med efterbearbetning för att detektera hörn är Kirsch-operatören och Frei-Chen maskeringsset.

"Hörn", "intressepunkt" och "funktion" används omväxlande i litteraturen, vilket förvirrar frågan. Specifikt finns det flera klumpdetektorer som kan kallas "intressepunktsoperatörer", men som ibland felaktigt kallas "hörndetektorer". Dessutom finns det en idé om åsdetektering för att fånga närvaron av långsträckta föremål.

Hörndetektorer är vanligtvis inte särskilt robusta och kräver ofta införda stora redundanser för att förhindra att effekten av individuella fel dominerar igenkänningsuppgiften.

En bestämning av kvaliteten på en hörndetektor är dess förmåga att detektera samma hörn i flera liknande bilder, under förhållanden med olika ljus, translation, rotation och andra transformationer.

Ett enkelt tillvägagångssätt för hörndetektering i bilder är att använda korrelation , men detta blir mycket beräkningsmässigt dyrt och suboptimalt. Ett alternativt tillvägagångssätt som används ofta är baserat på en metod som föreslås av Harris och Stephens (nedan), som i sin tur är en förbättring av en metod av Moravec.

Moravec hörndetekteringsalgoritm

Detta är en av de tidigaste hörndetekteringsalgoritmerna och definierar ett hörn som en punkt med låg självlikhet. Algoritmen testar varje pixel i bilden för att se om ett hörn finns, genom att överväga hur lik en lapp centrerad på pixeln är till närliggande, till stor del överlappande lappar. Likheten mäts genom att ta summan av kvadratskillnader (SSD) mellan motsvarande pixlar i två patchar. En lägre siffra indikerar mer likhet.

Om pixeln är i ett område med enhetlig intensitet, kommer de närliggande lapparna att se likadana ut. Om pixeln är på en kant kommer närliggande fläckar i en riktning vinkelrät mot kanten att se helt annorlunda ut, men närliggande fläckar i en riktning parallell med kanten kommer bara att resultera i en liten förändring. Om pixeln är på en funktion med variation i alla riktningar, kommer ingen av de närliggande lapparna att se likadana ut.

Hörnstyrkan definieras som den minsta SSD mellan patchen och dess grannar (horisontell, vertikal och på de två diagonalerna). Anledningen är att om detta nummer är högt så är variationen längs alla skift antingen lika med den eller större än den, så att alla närliggande lappar ser annorlunda ut.

Om talet för hörnstyrkan beräknas för alla platser, indikerar att det är lokalt maximalt för en plats att en funktion av intresse finns i den.

Som påpekats av Moravec är ett av huvudproblemen med den här operatören att den inte är isotrop : om det finns en kant som inte är i riktning mot grannarna (horisontell, vertikal eller diagonal), så kommer den minsta SSD:n att vara stor och kanten blir felaktigt vald som intressepunkt.

Harris & Stephens / Shi-Tomasis hörndetekteringsalgoritmer

Ytterligare information: Harris Corner Detector

Harris och Stephens förbättrade Moravecs hörndetektor genom att överväga skillnaden mellan hörnpoängen med avseende på riktning direkt, istället för att använda skiftade lappar. (Denna hörnpoäng kallas ofta för autokorrelation , eftersom termen används i det papper där denna detektor beskrivs. Men matematiken i uppsatsen indikerar tydligt att summan av kvadratskillnader används.)

Utan förlust av allmänhet kommer vi att anta att en gråskala 2-dimensionell bild används. Låt denna bild ges av $I$ . Överväg att ta en bildlapp över området $(u,v)$ och flytta den med $(x,y)$ . Den viktade summan av kvadratskillnader (SSD) mellan dessa två patchar, betecknade $S$ , ges av:

$S(x,y)=\summa _ {u}\summa _{v}w(u,v)\,\left(I(u+x,v+y)-I(u,v)\right)^{2}$

$I(u+x,v+y)$ kan approximeras med en Taylor-expansion . Låt $I_{x}$ och $I_{y}$ vara partiella derivator av $I$ , så att

$I(u+x,v+y)\approx I(u,v)+I_{x}(u,v)x+I_{y}(u,v)y$

Detta ger uppskattningen

$S(x,y)\approx \ summa _{u}\summa _{v}w(u,v)\,\left(I_{x}(u,v)x+I_{y}(u,v)y\right)^{2} ,$

som kan skrivas i matrisform:

$S(x,y)\approx {\begin{bmatrix}x&y\end{bmatrix}}A{\begin{bmatrix}x\ \y\end{bmatrix}},$

där A är strukturtensorn ,

$A=\summa _{u}\summa _{v} w(u,v){\begin{bmatrix}I_{x}(u,v)^{2}&I_{x}(u,v)I_{y}(u,v)\\I_{x}( u,v)I_{y}(u,v)&I_{y}(u,v)^{2}\end{bmatrix}}={\begin{bmatrix}\langle I_{x}^{2}\ rangle &\langle I_{x}I_{y}\rangle \\\langle I_{x}I_{y}\rangle &\langle I_{y}^{2}\rangle \end{bmatrix}}$

I ord finner vi kovariansen för den partiella derivatan av bildintensiteten $I$ med avseende på $x$ och $y$ -axlarna.

Vinkelparenteser anger medelvärdesberäkning (dvs summering över $(u,v)$ ). $w(u,v)$ anger typen av fönster som glider över bilden. Om ett boxfilter används kommer svaret att vara anisotropt , men om ett Gaussiskt används kommer svaret att vara isotropt .

Ett hörn (eller i allmänhet en intressepunkt) kännetecknas av en stor variation av $S$ i alla riktningar av vektorn ${\begin{bmatrix}x&y\end{bmatrix}}$ . Genom att analysera egenvärdena för $A$ kan denna karakterisering uttryckas på följande sätt: $A$ bör ha två "stora" egenvärden för en intressepunkt. Baserat på storleken på egenvärdena kan följande slutsatser göras baserat på detta argument:

1. Om $\lambda _{1}\approx 0$ och $\lambda _{2}\approx 0$ så är denna pixel $(x,y)$ har inga funktioner av intresse.
2. Om $\lambda _{1}\approx 0$ och $\lambda _{2}$ har något stort positivt värde, så hittas en kant.
3. Om $\lambda _{1}$ och $\lambda _{2}$ har stora positiva värden, så hittas ett hörn.

Harris och Stephens noterar att exakt beräkning av egenvärdena är beräkningsmässigt dyr, eftersom den kräver beräkning av en kvadratrot , och föreslår istället följande funktion ${\displaystyle M_{c}} ,$ där $\kappa$ är en inställbar känslighetsparameter:

$M_{c}=\lambda _{1}\lambda _{2} -\kappa \left(\lambda _{1}+\lambda _{2}\right)^{2}=\det(A)-\kappa \operatörsnamn {spår} ^{2}(A)$

Därför behöver algoritmen inte faktiskt beräkna egenvärdesuppdelningen av matrisen $A$ och istället är det tillräckligt att utvärdera determinanten och spåret av $A$ för att hitta hörn, eller snarare intressepunkter i allmänhet .

Shi–Tomasis hörndetektor beräknar direkt $\min(\lambda _{1},\lambda _{2})$ eftersom hörnen under vissa antaganden är mer stabila för spårning. Observera att denna metod ibland också kallas Kanade–Tomasis hörndetektor.

Värdet på $\kappa$ måste bestämmas empiriskt, och i litteraturen har värden i intervallet 0,04–0,15 rapporterats som möjliga.

Man kan undvika att sätta parametern $\kappa$ genom att använda Nobles hörnmått $M_{c}'$ som motsvarar det harmoniska medelvärdet av egenvärdena:

$M_{c}'=2{\frac {\det(A)}{\operatörsnamn {trace} (A)+\epsilon } },$

$\epsilon$ är en liten positiv konstant.

Om $A$ kan tolkas som precisionsmatrisen för hörnpositionen är kovariansmatrisen för hörnpositionen ${\displaystyle A^{-1}} ,$ dvs.

${\frac {1}{\langle I_{x}^{2}\rangle \langle I_{y}^{2}\rangle -\langle I_{x}I_{y}\rangle ^{2 }}}{\begin{bmatrix}\langle I_{y}^{2}\rangle &-\langle I_{x}I_{y}\rangle \\-\langle I_{x}I_{y}\rangle &\langle I_{x}^{2}\rangle \end{bmatrix}}.$

Summan av egenvärdena för ${\displaystyle A^{-1}} ,$ som i så fall kan tolkas som en generaliserad varians (eller en "total osäkerhet") av hörnpositionen, är relaterad till Nobles hörnmått $M_{c}'$ med följande ekvation:

$\lambda _{1}(A^{-1})+\lambda _{2}(A^{-1})={\frac {\operatörsnamn {spår} (A)}{\det( A)}}\approx {\frac {2}{M_{c}'}}.$

Förstner hörndetektor

Hörndetektering med Förstner-algoritmen

I vissa fall kan man vilja beräkna platsen för ett hörn med subpixelnoggrannhet. För att uppnå en ungefärlig lösning löser Förstner-algoritmen den punkt som ligger närmast hörnets alla tangentlinjer i ett givet fönster och är en minsta kvadratisk lösning. Algoritmen förlitar sig på det faktum att för ett idealiskt hörn korsar tangentlinjer i en enda punkt.

Ekvationen för en tangentlinje $T_{\mathbf {x} '}(\mathbf {x} )$ vid pixel $\mathbf {x} '$ ges av:

$T_{\mathbf {x'} }(\mathbf {x} )=\nabla I(\mathbf {x' } )^{\top }(\mathbf {x} -\mathbf {x'} )=0$

där $\nabla I(\mathbf {x'} )={\begin{bmatrix}I_{\mathbf {x} }&I_{\mathbf {y } }\end{bmatrix}}^{\top }$ är gradientvektorn för bilden $I$ vid $\mathbf {x'}$ .

Punkten $\mathbf {x} _{0}$ närmast alla tangentlinjer i fönstret $N$ är:

$\mathbf {x} _{0}={\underset {\mathbf {x} \in \mathbb {R} ^{2\times 1}}{\operatörsnamn {argmin} }}\int _{\mathbf {x'} \in N}T_{\mathbf {x'} }(\mathbf {x} )^ {2}d\mathbf {x'}$

Avståndet från $\mathbf {x} _{0}$ till tangentlinjerna $T_{\mathbf {x'} }$ viktas av gradientens storlek, vilket ger tangenterna större vikt passerar genom pixlar med starka gradienter.

Lösa för $\mathbf {x} _{0}$ :

$\begin{aligned}\mathbf {x} _{0}&={\underset {\mathbf {x} \in \mathbb {R} ^{2\times 1}}{\operatorname {argmin} }}\int _{\mathbf {x'} \in N}\left(\nabla I\left(\mathbf {x'} \right)^{\top }\left(\mathbf {x} -\mathbf {x'} \right)\right)^{2}d\mathbf {x'} \\&={\underset {\mathbf {x} \in \mathbb {R} ^{2\times 1}}{\operatörsnamn {argmin } }}\int _{\mathbf {x'} \in N}(\mathbf {x} -\mathbf {x'} )^{\top }\nabla I(\mathbf {x'} )\nabla I (\mathbf {x'} )^{\top }(\mathbf {x} -\mathbf {x'} )d\mathbf {x'} \\&={\underset {\mathbf {x} \in \ mathbb {R} ^{2\ gånger 1}}{\operatörsnamn {argmin} }}\left(\mathbf {x} ^{\top }A\mathbf {x} -2\mathbf {x} ^{\top }\mathbf {b} +c\right)\end{aligned}}$

$A\in \mathbb {R} ^{2\times 2},{\textbf {b}}\in \mathbb {R} ^{2\times 1},c\in \mathbb {R}$ definieras som:

${\begin{aligned}A&=\int \nabla I(\mathbf {x'} )\nabla I(\mathbf {x'} )^ {\top }d\mathbf {x'} \\\mathbf {b} &=\int \nabla I(\mathbf {x'} )\nabla I(\mathbf {x'} )^{\top }\ mathbf {x'} d\mathbf {x'} \\c&=\int \mathbf {x'} ^{\top }\nabla I(\mathbf {x'} )\nabla I(\mathbf {x'} )^{\top }\mathbf {x'} d\mathbf {x'} \\\end{aligned}}$

Att minimera denna ekvation kan göras genom att differentiera med avseende på $x$ och sätta den lika med 0:

$2A\mathbf {x} -2\mathbf {b} =0\Högerpil A\mathbf {x} =\mathbf {b}$

Observera att $A\in \mathbb {R} ^{2\times 2}$ är strukturens tensor . För att ekvationen ska ha en lösning $A$ vara inverterbar, vilket innebär att $A$ måste vara full rang (rank 2). Alltså lösningen

$x_{0}=A^{-1}\mathbf {b}$

existerar bara där ett faktiskt hörn finns i fönstret $N$ .

En metod för att utföra automatiskt skalval för denna hörnlokaliseringsmetod har presenterats av Lindeberg genom att minimera den normaliserade residual

${\tilde {d}}_{\min }={\frac {cb^{T}A^{-1}b}{\ operatörsnamn {trace} A}}$

över vågar. Därigenom har metoden förmågan att automatiskt anpassa skalnivåerna för beräkning av bildgradienterna till brusnivån i bilddatan, genom att välja grövre skalnivåer för brusig bilddata och finare skalnivåer för nära idealiska hörnliknande strukturer.

Anmärkningar:

• $c$ kan ses som en residual i beräkningen av den minsta kvadratiska lösningen: om $c=0$ så var det inget fel.
• denna algoritm kan modifieras för att beräkna centrum för cirkulära egenskaper genom att ändra tangentlinjer till normala linjer.

Harris-operatören i flera skala

Beräkningen av den andra momentmatrisen (ibland även kallad strukturtensor ) A $\displaystyle A}$ i Harris-operatorn kräver beräkning av bildderivator $I_{x},I_{y }$ i bilddomänen samt summeringen av icke-linjära kombinationer av dessa derivator över lokala grannskap. Eftersom beräkningen av derivator vanligtvis involverar ett steg av skalrumsutjämning, kräver en operationell definition av Harris-operatorn två skalparametrar: (i) en lokal skala för utjämning före beräkningen av bildderivator , och (ii) en integrationsskala för att ackumulera de icke-linjära operationerna på derivatoperatorer till en integrerad bilddeskriptor.

Med $I$ som betecknar den ursprungliga bildintensiteten, låt $L$ beteckna skalrumsrepresentationen av $I$ som erhålls genom faltning med en gaussisk kärna

$g(x,y,t)={\frac {1}{2{\pi }t }}e^{-\left(x^{2}+y^{2}\right)/2t}$

med lokal skala parameter $t$ :

$L(x,y,t)\ =g(x,y,t)*I(x, y)$

och låt $L_{x}=\partial _{x}L$ och $L_{y}=\partial _{y}L$ beteckna den partiella derivator av $L$ . Introducera dessutom en Gaussisk fönsterfunktion $g(x,y,s)$ med integrationsskalparameter $s$ . Sedan kan den flerskaliga andra ögonblicksmatrisen definieras som

$\mu (x,y;t,s)=\int _{\xi =-\infty }^{\infty }\int _{\eta =-\infty }^{\infty }{\begin {bmatrix}L_{x}^{2}(x-\xi ,y-\eta ;t)&L_{x}(x-\xi ,y-\eta ;t)\,L_{y}(x- \xi ,y-\eta ;t)\\L_{x}(x-\xi ,y-\eta ;t)\,L_{y}(x-\xi ,y-\eta ;t)&L_{ y}^{2}(x-\xi ,y-\eta ;t)\end{bmatrix}}g(\xi ,\eta ;s)\,d\xi \,d\eta .$

Sedan kan vi beräkna egenvärden för $\mu$ på ett liknande sätt som egenvärdena för $A$ och definiera det flerskaliga Harris hörnmåttet som

$M_{c}(x,y;t,s)=\det(\mu (x,y;t,s))-\kappa \,\operatörsnamn {spår} ^{2}(\mu ( x,y;t,s)).$

När det gäller valet av den lokala skalparametern $t$ och integrationsskalparametern $s$ , är dessa skalparametrar vanligtvis kopplade av en relativ integrationsskalparameter $\gamma$ så att $s=\gamma ^{2}t$ , där $\gamma$ vanligtvis väljs i intervallet $[1,2]$ . Således kan vi beräkna Harris-hörnmåttet $M_{c}(x,y;t,\gamma ^{2}t)$ när som helst skala $t$ i skalutrymme för att erhålla en flerskalig hörndetektor, som reagerar på hörnstrukturer av varierande storlek i bilddomänen.

I praktiken kompletteras denna flerskaliga hörndetektor ofta med ett skalvalssteg , där den skalnormaliserade Laplacian-operatorn

$\nabla _{\mathrm {norm} }^{2}L(x,y;t)\ =t\nabla ^{2}L(x,y,t)=t(L_{xx} (x,y,t)+L_{yy}(x,y,t))$

beräknas på varje skala i skalrum och skalanpassade hörnpunkter med automatiskt skalval ( "Harris-Laplace-operatören") beräknas från de punkter som samtidigt är:

• spatiala maxima för flerskaligt hörnmått $M_{c}(x,y;t,\gamma ^{2}t)$

  $({\hat {x}},{\hat {y}};t)=\operatörsnamn {argmaxlocal} _{(x,y)}M_{c}\left(x,y;t,\gamma ^{2}t\right)$

• lokala maxima eller minima över skalor för den skalnormaliserade Laplacian-operatorn $\nabla _{\mathrm {norm} }^{2}(x,y,t)$ :

  ${\hat {t}}=\operatörsnamn {argmaxminlocal} _{t}\nabla _{\mathrm {norm} }^{2}L({\hat {x}},{\hat {y}};t)$

Den nivåkurva kurvatur tillvägagångssätt

Ett tidigare tillvägagångssätt för hörndetektering är att detektera punkter där kurvaturen för nivåkurvor och gradientstorleken samtidigt är höga. Ett differentiellt sätt att upptäcka sådana punkter är genom att beräkna den omskalade nivåkurvans krökning (produkten av nivåkurvans krökning och gradientstorleken upphöjd till tre potens)

${\tilde {\kappa }}(x,y;t) =L_{x}^{2}L_{yy}+L_{y}^{2}L_{xx}-2L_{x}L_{y}L_{xy}$

och att detektera positiva maxima och negativa minima för detta differentialuttryck i någon skala $t$ i skalrumsrepresentationen $L$ för originalbilden. Ett huvudproblem vid beräkning av den omskalade nivåkurvans krökningsenhet på en enda skala är dock att den kan vara känslig för brus och för valet av skalnivå. En bättre metod är att beräkna den $\gamma$ -normaliserade omskalade nivåkurvan

${\tilde {\kappa }}_{\mathrm {norm} }(x,y;t)=t^{2\gamma }(L_{x}^{2}L_{yy}+L_{y}^{2}L_{xx }-2L_{x}L_{y}L_{xy})$

med $\gamma =7/8$ och för att detektera teckenskala-space extrema av detta uttryck, som är punkter och skalor som är positiva maxima och negativa minima med avseende på både rymden och skalan

$({\hat {x}},{\hat {y }};{\hat {t}})=\operatörsnamn {argminmaxlocal} _{(x,y;t)}{\tilde {\kappa}}_{\mathrm {norm} }(x,y;t)$

i kombination med ett komplementärt lokaliseringssteg för att hantera ökningen av lokaliseringsfel vid grövre skalor. På detta sätt kommer större skalvärden att associeras med rundade hörn med stor rumslig utsträckning medan mindre skalvärden kommer att associeras med skarpa hörn med liten rumslig utsträckning. Detta tillvägagångssätt är den första hörndetektorn med automatiskt skalval (före "Harris-Laplace-operatören" ovan) och har använts för att spåra hörn under storskaliga variationer i bilddomänen och för att matcha hörnsvar mot kanter för att beräkna strukturella bildegenskaper för geonbaserad objektigenkänning.

Laplacian av Gaussian, skillnader mellan Gaussians och bestämningsfaktorer för de hessiska skalan-rymden intressepunkter

LoG är en akronym som står för Laplacian av Gaussian , DoG är en akronym som står för different of Gaussians (DoG är en approximation av LoG), och DoH är en akronym som står för determinant of the Hessian . Dessa skalinvarianta intressepunkter extraheras alla genom att detektera skalrumsextrema för skalnormaliserade differentialuttryck, dvs punkter i skalrymd där motsvarande skalnormaliserade differentialuttryck antar lokala extrema med avseende på både rymd och skala

$({\hat {x}},{\hat {y}};{\hat {t}})=\operatörsnamn {argminmaxlocal} _{(x,y;t)}(D_{\mathrm {norm} }L)(x,y;t)$

där $D_{norm}L$ betecknar lämplig skalnormaliserad differentialenhet (definierad nedan).

Dessa detektorer beskrivs mer fullständigt i blobdetektion . Den skalnormaliserade laplacianen för Gaussiska och Gaussiska särdrag (Lindeberg 1994, 1998; Lowe 2004)

${\begin{aligned}\nabla _{\mathrm {norm} }^{2}L(x,y;t)&=t\,(L_{xx}+L_{yy})\\ &\approx {\frac {t\left(L(x,y;t+\Delta t)-L(x,y;t)\right)}{\Delta t}}\end{aligned}}$

gör inte nödvändigtvis mycket selektiva funktioner, eftersom dessa operatörer också kan leda till svar nära kanterna. För att förbättra hörndetekteringsförmågan hos skillnaderna hos Gaussiska detektorer använder funktionsdetektorn som används i SIFT -systemet därför ett ytterligare efterbearbetningssteg, där egenvärdena för bildens hessian vid detekteringsskalan undersöks på liknande sätt som i Harris-operatören. Om förhållandet mellan egenvärdena är för högt betraktas den lokala bilden som för kantliknande, så särdraget avvisas. Även Lindebergs Laplacian of the Gaussian funktionsdetektor kan definieras till att innefatta komplementär tröskelvärde på en komplementär differentiell invariant för att undertrycka svar nära kanter.

Den skalnormaliserade determinanten för den hessiska operatorn (Lindeberg 1994, 1998)

$\det H_{\mathrm {norm} }L=t^{2}(L_{xx}L_{ åå}-L_{xy}^{2})$

är å andra sidan mycket selektiv för väl lokaliserade bildegenskaper och reagerar endast när det finns signifikanta grånivåvariationer i två bildriktningar och är i detta och andra avseenden en bättre intressepunktsdetektor än Gaussans Laplacian. Determinanten för hessian är ett affint kovariant differentiellt uttryck och har bättre skalvalsegenskaper under affina bildtransformationer än den laplaciska operatorn (Lindeberg 2013, 2015). Experimentellt innebär detta att determinant av de hessiska intressepunkterna har bättre repeterbarhetsegenskaper under lokal bilddeformation än Laplacian intressepunkter, vilket i sin tur leder till bättre prestanda för bildbaserad matchning i termer av högre effektivitetspoäng och lägre 1− precisionspoäng .

Skalvalsegenskaperna, affina transformationsegenskaper och experimentella egenskaper hos dessa och andra skalrumsintressepunktdetektorer analyseras i detalj i (Lindeberg 2013, 2015).

Skala-rymds intressepunkter baserade på Lindeberg Hessian-funktionens styrka

Inspirerad av de strukturellt likartade egenskaperna hos den hessiska matrisen $Hf$ för en funktion $f$ och andra-momentmatrisen (strukturtensor) $\mu$ , vilket t.ex. kan manifesteras i vad gäller deras liknande transformationsegenskaper under affina bilddeformationer

$(Hf')=A^{-T}\,(Hf)\,A^{-1}$ ,

$\mu '=A^{-T}\,\mu \,A^{-1}$ ,

Lindeberg (2013, 2015) föreslog att fyra särdragsstyrkemått från den hessiska matrisen skulle definieras på relaterade sätt eftersom Harris- och Shi-och-Tomasi-operatorerna definieras från strukturtensorn (andra momentsmatrisen). Specifikt definierade han följande osignerade och signerade hessiska särdragsstyrkemått:

• det osignerade hessiska särdragets styrka I:

  $D_{ 1,\mathrm {norm} }L={\begin{cases}t^{2}\,(\det HL-k\,\operatörsnamn {trace} ^{2}HL)&{\mbox{if}} \,\det HL-k\,\operatörsnamn {spår} ^{2}HL>0\\0&{\mbox{annars}}\end{cases}}$

• det signerade hessiska dragets styrka I:

  ${\tilde {D}}_{1,\mathrm {norm} }L={\begin{cases} t^{2}\,(\det HL-k\,\operatörsnamn {spår} ^{2}HL)&{\mbox{if}}\,\det HL-k\,\operatörsnamn {spår} ^{ 2}HL>0\\t^{2}\,(\det HL+k\,\operatörsnamn {spår} ^{2}HL)&{\mbox{if}}\,\det HL+k\, \operatörsnamn {spåra} ^{2}HL<0\\0&{\mbox{annars}}\end{cases}}$

• den osignerade hessiska egenskapens styrka mått II:

  $D_{2,\mathrm {norm} }L=t\,\min(|\lambda _{1}(HL)|,|\lambda _{2}(HL)|)$

• det undertecknade hessiska kännetecknet styrkemått II:

  ${\tilde {D}}_{2,\mathrm {norm} }L={\begin{cases}t\, \lambda _{1}(HL)&{\mbox{if}}\,|\lambda _{1}(HL)|<|\lambda _{2}(HL)|\\t\,\lambda _ {2}(HL)&{\mbox{if}}\,|\lambda _{2}(HL)|<|\lambda _{1}(HL)|\\t\,(\lambda _{1 }(HL)+\lambda _{2}(HL))/2&{\mbox{annat}}\end{cases}}$

där $\operatorname {trace} HL=L_{xx}+L_{yy}$ och ${ \displaystyle \det HL=L_{xx}L_{yy}-L_{xy}^{2}}$ betecknar spåret och determinanten för den hessiska matrisen $HL$ för skalrumsrepresentationen ${\ displaystyle L}$ i valfri skala $t$ , medan

$\lambda _{1}(HL )=L_{pp}={\frac {1}{2}}\left(L_{xx}+L_{yy}-{\sqrt {(L_{xx}-L_{yy})^{2}+ 4L_{xy}^{2}}}\höger)$

$\lambda _{2}(HL)=L_{qq}={\frac {1}{2}}\left(L_{xx}+L_{yy}+{\sqrt {(L_) {xx}-L_{yy})^{2}+4L_{xy}^{2}}}\höger)$

beteckna egenvärdena för den hessiska matrisen.

Det osignerade hessiska dragstyrkamåttet $D_{1,\mathrm {norm} }L$ reagerar på lokala extrema värden med positiva värden och är inte känsligt för sadelpunkter, medan den signerade hessiska dragstyrkan mät ${\tilde {D}}_{1,\mathrm {norm} }L$ svarar dessutom på sadelpunkter med negativa värden. Det osignerade hessiska särdragets styrka $D_{2,\mathrm {norm} }L$ är okänsligt för den lokala polariteten hos signalen, medan det signerade hessiska särdragets styrka ${\tilde {D}}_{2,\mathrm {norm} }L$ svarar på signalens lokala polaritet med tecknet för dess utsignal.

I Lindeberg (2015) kombinerades dessa fyra differentialenheter med lokalt skalval baserat på endera skala-rymdextrema-detektion

$({\hat {x}},{\hat {y}};{\hat {t}})=\operatörsnamn {argminmaxlocal} _{(x,y;t)}(D_{\mathrm {norm} }L)(x,y;t)$

eller skala länkning. Vidare mäter den signerade och osignerade hessiska egenskapens styrka $D_{2,\mathrm {norm} }L$ och ${\tilde { D}}_{2,\mathrm {norm} }L$ kombinerades med komplementär tröskelvärde på $D_{1,\mathrm {norm} }L>0$ .

Genom experiment med bildmatchning under skalningstransformationer på en affischdatauppsättning med 12 affischer med multi-view-matchning över skalningstransformationer upp till en skalningsfaktor på 6 och visningsriktningsvariationer upp till en lutningsvinkel på 45 grader med lokala bilddeskriptorer definierade från omformuleringar av de rena bilddeskriptorerna i SIFT- och SURF- operatorerna till bildmätningar i termer av Gaussiska derivatoperatorer (Gauss-SIFT och Gauss-SURF) istället för original SIFT som definierats från en bildpyramid eller original SURF som definierats från Haar-vågor, det visades att detektering av skala-mellanrumsintressepunkter baserat på det osignerade hessiska särdragets styrka $D_{1,\mathrm {norm} }L$ möjliggjorde bästa prestanda och bättre prestanda än skalutrymme intressepunkter erhållna från determinanten av hessiska $\det H_{\mathrm {norm} }L=t^{ 2}\left(L_{xx}L_{yy}-L_{xy}^{2}\right)$ . Både det osignerade hessiska dragstyrkemåttet $D_{1,\mathrm {norm} }L$ , det signerade hessiska dragstyrkemåttet ${ \tilde {D}}_{1,norm}L$ och bestämningsfaktorn för hessisk $\det H_{norm}L$ möjliggjorde bättre prestanda än laplacian för gaussisk $\nabla _{\mathrm {norm} }^{2}L=t\,(L_{xx}+L_{yy})$ . I kombination med skallänkning och komplementär tröskelvärde på $D_{1,\mathrm {norm} }L>0$ , det signerade hessiska särdragets styrka ${\tilde {D}}_{2,\mathrm {norm} }L$ möjliggjorde dessutom bättre prestanda än Gaussans Laplacian $\nabla _{\ mathrm {norm} }^{2}L$ .

Dessutom visades det att alla dessa detektorer för differentialskala och rymdintresse definierade från den hessiska matrisen möjliggör detektering av ett större antal intressepunkter och bättre matchningsprestanda jämfört med Harris- och Shi-och-Tomasi-operatorerna definierade från strukturen tensor (andra ögonblicksmatris).

En teoretisk analys av skalvalsegenskaperna för dessa fyra hessiska särdragsstyrkemått och andra differentiella enheter för att detektera skal-rymdsintressepunkter, inklusive Gaussans Laplacian och Hessians bestämningsfaktor, ges i Lindeberg (2013) och en analys av deras affina transformationsegenskaper såväl som experimentella egenskaper i Lindeberg (2015).

Affinanpassade intressepunktsoperatörer

De intressepunkter som erhålls från Harris-operatorn med flera skalor med automatiskt skalval är oföränderliga för translationer, rotationer och enhetliga omskalningar i den rumsliga domänen. De bilder som utgör input till ett datorseendesystem är dock också föremål för perspektivförvrängningar. För att erhålla en intressepunktsoperator som är mer robust för perspektivtransformationer är ett naturligt tillvägagångssätt att utforma en funktionsdetektor som är oföränderlig för affintransformationer . I praktiken kan affina invarianta intressepunkter erhållas genom att tillämpa affin formanpassning där formen på utjämningskärnan iterativt förvrängs för att matcha den lokala bildstrukturen runt intressepunkten eller motsvarande en lokal bildlapp iterativt förvrängs medan formen på utjämningen kärnan förblir rotationssymmetrisk (Lindeberg 1993, 2008; Lindeberg och Garding 1997; Mikolajzcyk och Schmid 2004). Förutom den ofta använda Harris-operatorn i flera skalor, kan affin formanpassning tillämpas på andra hörndetektorer som listas i denna artikel, såväl som på differentialblobdetektorer såsom Laplacian/skillnaden hos Gaussian-operatorn, determinanten för Hessian och operatören Hessian–Laplace.

Wang och Brady hörndetekteringsalgoritm

Wang och Brady-detektorn betraktar bilden som en yta och letar efter platser där det finns stor krökning längs en bildkant. Algoritmen letar med andra ord efter platser där kanten snabbt ändrar riktning. Hörnpoängen, $C$ , ges av:

$C=\left({\frac {\delta ^{2}I}{\delta \mathbf {t} ^{2}}}\right)^{2}-c|\nabla I| ^{2},$

där ${\bf {t}}$ är enhetsvektorn vinkelrät mot gradienten, och $c$ bestämmer hur kantfobisk detektorn är. Författarna noterar också att utjämning (Gaussisk föreslås) krävs för att minska brus.

Utjämning orsakar också förskjutning av hörn, så författarna härleder ett uttryck för förskjutningen av ett 90 graders hörn, och tillämpar detta som en korrektionsfaktor på de detekterade hörnen.

SUSAN hörndetektor

SUSAN är en akronym som står för minsta univalue segment assimilating nucleus . Denna metod är föremål för ett brittiskt patent från 1994 som inte längre är i kraft.

För funktionsdetektering placerar SUSAN en cirkulär mask över pixeln som ska testas (kärnan). Området för masken är $M$ , och en pixel i denna mask representeras av ${\vec {m}}\in M$ . Kärnan är vid ${\vec {m}}_{0}$ . Varje pixel jämförs med kärnan med hjälp av jämförelsefunktionen:

$c({\vec {m}})=e^{-\left({\frac {I( {\vec {m}})-I({\vec {m}}_{0})}{t}}\right)^{6}}$

där $t$ är ljusstyrkeskillnaden, $I$ är pixelns ljusstyrka och exponentens styrka har bestämts empiriskt. Denna funktion ser ut som en utjämnad topphatt eller rektangulär funktion . Arean för SUSAN ges av:

$n(M)=\summa _{{\vec {m}}\in M}c({\vec {m}})$

Om $c$ är den rektangulära funktionen, så är $n$ antalet pixlar i masken som är inom $t$ från kärnan. Svaret från SUSAN-operatören ges av:

$R(M)={\begin{cases}gn(M)&{\mbox{if}}\ n( M)<g\\0&{\mbox{annars,}}\end{cases}}$

där $g$ kallas 'geometrisk tröskel'. Med andra ord har SUSAN-operatören bara ett positivt betyg om området är tillräckligt litet. Den minsta SUSAN lokalt kan hittas med icke-maximal undertryckning, och detta är den kompletta SUSAN-operatören.

Värdet $t$ bestämmer hur lika punkter som måste vara kärnan innan de anses vara en del av envärdessegmentet. Värdet på $g$ bestämmer minimistorleken på envärdessegmentet. Om $g$ är tillräckligt stor, blir detta en kantdetektor .

För hörndetektering används ytterligare två steg. För det första tyngdpunkten för SUSAN. Ett riktigt hörn kommer att ha tyngdpunkten långt från kärnan. Det andra steget insisterar på att alla punkter på linjen från kärnan genom tyngdpunkten ut till kanten av masken är i SUSAN.

Trajkovic och Hedley hörndetektor

På ett sätt som liknar SUSAN, testar den här detektorn direkt om en patch under en pixel är sig själv lik genom att undersöka närliggande pixlar. ${\vec {c}}$ är pixeln som ska beaktas, och ${\vec {p}}\i P$ är punkten på en cirkel $P$ centrerad kring ${\vec {c}}$ . Punkten ${\vec {p}}'$ är punkten mitt emot ${\vec {p}}$ längs diametern.

Svarsfunktionen definieras som:

$r({\ vec {c}})=\min _{{\vec {p}}\in P}\left(\left(I({\vec {p}})-I({\vec {c}})\ höger)^{2}+\left(I({\vec {p}}')-I({\vec {c}})\right)^{2}\right)$

Detta kommer att vara stort när det inte finns någon riktning i vilken mittpixeln liknar två närliggande pixlar längs en diameter. $P$ är en diskretiserad cirkel (en Bresenham-cirkel ), så interpolering används för mellanliggande diametrar för att ge ett mer isotropt svar. Eftersom alla beräkningar ger en övre gräns för $\min$ kontrolleras de horisontella och vertikala riktningarna först för att se om det är värt att fortsätta med den fullständiga beräkningen av $c$ .

AST-baserade funktionsdetektorer

AST är en akronym som står för accelererad segmenttest . Detta test är en avslappnad version av SUSAN corner-kriteriet. Istället för att utvärdera den cirkulära skivan, beaktas endast pixlarna i en Bresenham-cirkel med radien $r$ runt kandidatpunkten. Om $n$ sammanhängande pixlar alla är ljusare än kärnan med minst $t$ eller alla mörkare än kärnan med $t$ , så anses pixeln under kärnan vara en egenskap . Detta test rapporteras ge mycket stabila funktioner. Valet av i vilken ordning pixlarna testas är ett så kallat Twenty Questions-problem . Att bygga korta beslutsträd för detta problem resulterar i de mest beräkningseffektiva funktionsdetektorerna som finns tillgängliga.

Den första hörndetekteringsalgoritmen baserad på AST är FAST ( funktioner från accelererat segmenttest) . Även om $r$ i princip kan ta vilket värde som helst, använder FAST endast ett värde på 3 (motsvarande en cirkel med 16 pixlars omkrets), och tester visar att de bästa resultaten uppnås med $n$ som är 9 Detta värde på $n$ är det lägsta vid vilket kanter inte detekteras. Ordningen i vilken pixlar testas bestäms av ID3-algoritmen från en träningsuppsättning bilder. Förvirrande nog är namnet på detektorn något likt namnet på tidningen som beskriver Trajkovic och Hedleys detektor.

Automatisk syntes av detektorer

Trujillo och Olague introducerade en metod genom vilken genetisk programmering används för att automatiskt syntetisera bildoperatorer som kan upptäcka intressepunkter. Terminalen och funktionsuppsättningarna innehåller primitiva operationer som är vanliga i många tidigare föreslagna konstgjorda konstruktioner. Fitness mäter stabiliteten för varje operatör genom repeterbarhetshastigheten och främjar en enhetlig spridning av detekterade punkter över bildplanet. Prestandan hos de utvecklade operatörerna har bekräftats experimentellt med hjälp av tränings- och testsekvenser av progressivt transformerade bilder. Därför anses den föreslagna GP-algoritmen vara människokonkurrens för problemet med detektering av intressepunkter.

Spatio-temporal intressepunktsdetektorer

Harris-operatören har utökats till rum-tid av Laptev och Lindeberg. Låt $\mu$ beteckna den rumsliga-temporala andra ögonblicksmatrisen definierad av

$A=\summa _{u}\summa _{v}\summa _{w}h(u,v,w){\begin{bmatrix}L_{x }(u,v,w)^{2}&L_{x}(u,v,w)L_{y}(u,v,w)&L_{x}(u,v,w)L_{t}( u,v,w)\\L_{x}(u,v,w)L_{y}(u,v,w)&L_{y}(u,v,w)^{2}&L_{y}( u,v,w)L_{t}(u,v,w)\\L_{x}(u,v,w)L_{t}(u,v,w)&L_{y}(u,v, w)L_{t}(u,v,w)&L_{t}(u,v,w)^{2}\\\end{bmatrix}}={\begin{bmatrix}\langle L_{x}^ {2}\rangle &\langle L_{x}L_{y}\rangle &\langle L_{x}L_{t}\rangle \\\langle L_{x}L_{y}\rangle &\langle L_{ y}^{2}\rangle &\langle L_{y}L_{t}\rangle \\\langle L_{x}L_{t}\rangle &\langle L_{y}L_{t}\rangle &\ langle L_{t}^{2}\rangle \\\end{bmatrix}}$

Sedan, för ett lämpligt val av $k<1/27$ , detekteras spatio-temporala intressepunkter från spatio-temporala extrema av följande spatio-temporala Harris-mått:

$H=\det(\mu )-\kappa \,\operatörsnamn {spår} ^{2}(\mu).$

Determinanten för den hessiska operatorn har utökats till gemensam rumtid av Willems et al och Lindeberg, vilket leder till följande skalnormaliserade differentialuttryck:

$\det(H_{(x,y,t),\mathrm {norm} }L)=\,s^{2\gamma _{s}}\tau ^{\gamma _{\tau }} \left(L_{xx}L_{yy}L_{tt}+2L_{xy}L_{xt}L_{yt}-L_{xx}L_{yt}^{2}-L_{yy}L_{xt} ^{2}-L_{tt}L_{xy}^{2}\höger).$

I arbetet av Willems et al användes ett enklare uttryck motsvarande $\gamma _{s}=1$ och ${\displaystyle \gamma _{\tau }=1} .$ I Lindeberg visades att $\gamma _{s}=5/4$$displaystyle \gamma _{\tau }=5/4}$ τ innebär bättre skalvalsegenskaper i den meningen att de valda skalnivåerna erhålls från en rumslig gaussisk blob med rumslig utsträckning $s=s_{0}$ och tidsmässig utsträckning $\tau =\tau _{0}$ kommer perfekt att matcha den rumsliga omfattningen och den tidsmässiga varaktigheten av blobben, med skalval som utförs genom att detektera rums-temporala skala-rymdsextrema för differentialuttrycket.

Den lappiska operatorn har utökats till spatio-temporal videodata av Lindeberg, vilket leder till följande två spatio-temporala operatorer, som också utgör modeller av mottagliga fält av icke-laggade vs lagged neuroner i LGN :

$\partial _{ t,\mathrm {norm} }(\nabla _{(x,y),\mathrm {norm} }^{2}L)=s^{\gamma _{s}}\tau ^{\gamma _{ \tau }/2}(L_{xxt}+L_{yyt}),$

$\partial _{tt,\mathrm {norm} }(\nabla _{(x,y),\mathrm {norm} }^{2}L)=s^{\gamma _{s}}\ tau ^{\gamma _{\tau }}(L_{xxtt}+L_{yytt}).$

För den första operatorn kräver skalvalsegenskaper att man använder $\gamma _{\tau }=1/2$$s}=1}$ och , om vi vill att denna operator ska anta sitt maximala värde över rumsliga-temporala skalor på en spatio-temporal skalanivå som återspeglar den rumsliga utsträckningen och den tidsmässiga varaktigheten av en Gaussisk blob som börjar. För den $\gamma _{\tau }=3/4$ operatorn kräver skalvalsegenskaper att man använder $\displaystyle \gamma _{s}=1}$ och , om vi vill att denna operator ska anta sitt maximala värde över rumsliga-temporala skalor på en spatio-temporal skalanivå som återspeglar den rumsliga utsträckningen och den tidsmässiga varaktigheten av en blinkande Gaussisk blob.

Färgförlängningar av spatio-temporala intressepunktsdetektorer har undersökts av Everts et al.

Referensimplementeringar

Det här avsnittet tillhandahåller externa länkar till referensimplementeringar av några av detektorerna som beskrivs ovan. Dessa referensimplementeringar tillhandahålls av författarna till artikeln där detektorn först beskrivs. Dessa kan innehålla detaljer som inte finns eller är explicita i tidningarna som beskriver funktionerna.

• DoG-detektering (som en del av SIFT -systemet), Windows och x86 Linux körbara filer
• Harris-Laplace , statiska körbara Linux- filer. Innehåller även DoG- och LoG-detektorer samt affin anpassning för alla inkluderade detektorer.
• FAST detektor , C, C++, MATLAB källkod och körbara filer för olika operativsystem och arkitekturer.
• lip-vireo , [LoG, DoG, Harris-Laplacian, Hessian och Hessian-Laplacian], [SIFT, flip invariant SIFT, PCA-SIFT, PSIFT, Styrbara filter, SPIN][Linux, Windows och SunOS] körbara filer.
• SUSAN Low Level Image Processing , C-källkod.
• Onlineimplementering av Harris Corner Detector - IPOL

Se även

• klumpdetektering
• affin formanpassning
• skala utrymme
• åsdetektering
• intressepunktsdetektering
• funktionsdetektering (datorseende)
• Bildderivat

externa länkar

• Lindeberg, Tony (2001) [1994], "Hörndetektering" , Encyclopedia of Mathematics , EMS Press
• Brostow, "Hörndetektering -- UCL Computer Science"