Detecció de cantonades

Sortida d'un algorisme típic de detecció de cantonades

La detecció de cantonades és un enfocament utilitzat en els sistemes de visió per ordinador per extreure determinats tipus de característiques i inferir el contingut d'una imatge. La detecció de cantonades s'utilitza amb freqüència en detecció de moviment, registre d'imatges, seguiment de vídeo, mosaic d'imatges, costura panoràmica, reconstrucció 3D i reconeixement d'objectes. La detecció de cantonades se solapa amb el tema de detecció de punts d'interès.

Estimació de l'emoció mitjançant la detecció de cantonades

Formalització

Una cantonada es pot definir com la intersecció de dues arestes. Una cantonada també es pot definir com un punt per al qual hi ha dues direccions de vora dominants i diferents en un veïnat local del punt.

Un punt d'interès és un punt d'una imatge que té una posició ben definida i que es pot detectar de manera robusta. Això vol dir que un punt d'interès pot ser una cantonada però també pot ser, per exemple, un punt aïllat d'intensitat local màxima o mínima, finals de línia o un punt d'una corba on la curvatura és localment màxima.

A la pràctica, la majoria dels anomenats mètodes de detecció de cantonades detecten punts d'interès en general i, de fet, els termes "cantó" i "punt d'interès" s'utilitzen de manera més o menys intercanviable a través de la literatura. Com a conseqüència, si només es volen detectar cantons, cal fer una anàlisi local dels punts d'interès detectats per determinar quins d'aquests són racons reals. Exemples de detecció de vores que es poden utilitzar amb el postprocessament per detectar cantonades són l'operador Kirsch i el conjunt d'emmascarament Frei-Chen.

"Racó", "punt d'interès" i "funció" s'utilitzen indistintament a la literatura, confonent el tema. Concretament, hi ha diversos detectors de taques que es poden denominar "operadors de punts d'interès", però que de vegades s'anomenen erròniament "detectors de cantonada". A més, existeix una noció de detecció de crestes per capturar la presència d'objectes allargats.

Els detectors de cantonada no solen ser molt robusts i sovint requereixen grans redundàncies introduïdes per evitar que l'efecte d'errors individuals domini la tasca de reconeixement.

Una determinació de la qualitat d'un detector de cantonada és la seva capacitat per detectar el mateix racó en múltiples imatges similars, en condicions d'il·luminació, translació, rotació i altres transformacions diferents.

Un enfocament senzill per a la detecció de cantonades a les imatges és utilitzar la correlació, però això es fa molt car computacionalment i subòptim. Un enfocament alternatiu utilitzat amb freqüència es basa en un mètode proposat per Harris i Stephens (a continuació), que al seu torn és una millora d'un mètode de Moravec.

Algorisme de detecció de cantonades Moravec

Aquest és un dels primers algorismes de detecció de cantonada i defineix una cantonada com un punt amb poca autosemblança. L'algoritme prova cada píxel de la imatge per veure si hi ha una cantonada, tenint en compte la semblança d'un pegat centrat al píxel amb els pegats propers, en gran part superposats. La similitud es mesura prenent la suma de diferències al quadrat (SSD) entre els píxels corresponents de dos pegats. Un nombre més baix indica més semblança.

Si el píxel es troba en una regió d'intensitat uniforme, els pegats propers tindran un aspecte similar. Si el píxel està a una vora, els pegats propers en una direcció perpendicular a la vora tindran un aspecte molt diferent, però els pegats propers en una direcció paral·lela a la vora només produiran un petit canvi. Si el píxel es troba en una funció amb variació en totes direccions, cap dels pegats propers es veurà semblant.

La força de la cantonada es defineix com el SSD més petit entre el pegat i els seus veïns (horitzontal, vertical i a les dues diagonals). El motiu és que si aquest nombre és alt, aleshores la variació al llarg de tots els torns és igual o més gran que ell, de manera que la captura de tots els pegats propers sembla diferent.

Si el nombre de força de cantonada es calcula per a totes les ubicacions, que sigui màxim localment per a una ubicació indica que hi ha una característica d'interès.

Tal com ha assenyalat Moravec, un dels principals problemes d'aquest operador és que no és isòtrop: si hi ha una vora que no es troba en la direcció dels veïns (horitzontal, vertical o diagonal), aleshores la SSD més petita serà gran i la vora serà escollida incorrectament com a punt d'interès.

Els algorismes de detecció de cantonades de Harris & Stephens / Shi–Tomasi

Harris i Stephens van millorar el detector de cantonades de Moravec considerant directament el diferencial de la puntuació de les cantonades respecte a la direcció, en comptes d'utilitzar pedaços desplaçats. (Aquesta puntuació de cantonada s'anomena sovint autocorrelació, ja que el terme s'utilitza en el document en què es descriu aquest detector. Tanmateix, les matemàtiques del document indiquen clarament que s'utilitza la suma de diferències al quadrat.)

Sense pèrdua de generalitat, suposarem que s'utilitza una imatge bidimensional en escala de grisos. Que aquesta imatge ve donada per $I$. Penseu en fer un pegat d'imatge sobre la zona $(u,v)$ i desplaçant-lo $(x,y)$. La suma ponderada de les diferències al quadrat (SSD) entre aquests dos pegats, indicada $S$, ve donada per:

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

El detector de cantonada Förstner

Detecció de cantonades mitjançant l'algoritme de Förstner

En alguns casos, és possible que vulgueu calcular la ubicació d'una cantonada amb una precisió de subpíxels. Per aconseguir una solució aproximada, l'algorisme de Förstner resol el punt més proper a totes les línies tangents de la cantonada en una finestra donada i és una solució de mínims quadrats. L'algorisme es basa en el fet que per a una cantonada ideal, les línies tangents es creuen en un sol punt.

L'equació d'una recta tangent $T_{{𝐱}^{\prime }}(𝐱)$ al píxel ${𝐱}^{\prime }$ ve donada per:

$T_{{𝐱}^{\prime }}(𝐱)=\mathrm{\nabla }I({𝐱}^{\prime }{)}^{\mathrm{\top }}(𝐱-{𝐱}^{\prime })=0$

on $\mathrm{\nabla }I({𝐱}^{\prime })={\left[\begin{array}{cc}{I}_{𝐱}& I_{𝐲}\end{array}\right]}^{\mathrm{\top }}$ és el vector de gradient de la imatge $I$ a ${𝐱}^{\prime }$.

El punt ${𝐱}_0$ més proper a totes les línies tangents de la finestra $N$ és:

${𝐱}_0=\underset{𝐱\in {ℝ}^{2\times 1}}{\mathrm{argmin}}\underset{{𝐱}^{\prime }\in N}{\int }{T}_{{𝐱}^{\prime }}(𝐱{)}^{2}d{𝐱}^{\prime }$

L'operador Harris multiescala

El càlcul de la segona matriu de moments (de vegades també es coneix com a tensor d'estructura) $A$ en l'operador Harris, requereix el càlcul de les derivades d'imatge $I_x,I_y$ en el domini de la imatge, així com la suma de combinacions no lineals d'aquestes derivades sobre els barris locals. Atès que el càlcul de derivades normalment implica una etapa de suavització d'escala-espai, una definició operativa de l'operador Harris requereix dos paràmetres d'escala: (i) una escala local per suavitzar abans del càlcul de les derivades d'imatge, i (ii) una escala d'integració per acumular les operacions no lineals d'operadors derivats en un descriptor d'imatge integrat.

Amb $I$ que denota la intensitat de la imatge original, det $L$ denoten la representació de l'espai d'escala $I$ obtingut per convolució amb un nucli gaussià

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

Aproximació a la curvatura de la corba de nivell

Un enfocament anterior a la detecció de cantonades és detectar punts on la curvatura de les corbes de nivell i la magnitud del gradient són alhora altes. Una manera diferencial de detectar aquests punts és calculant la curvatura de la corba de nivell reescalada (el producte de la curvatura de la corba de nivell i la magnitud del gradient elevada a la potència de tres)

$\tilde{\kappa }(x,y;t)=L_x^2{L}_{yy}+L_y^2{L}_{xx}-2L_x{L}_y{L}_{xy}$

Laplacià de Gauss, diferències de Gaussians i determinant dels punts d'interès escala-espai Hessian

LoG és un acrònim que significa laplacià de gaussià, DoG és un acrònim que significa diferència de gaussians (DoG és una aproximació de LoG), i DoH és un acrònim que significa determinant de la hessiana. Tots aquests punts d'interès invariants d'escala s'extreuen mitjançant la detecció d'extrems d'escala-espai d'expressions diferencials normalitzades per escala, és a dir, punts en l'escala-espai on les corresponents expressions diferencials normalitzades a escala assumeixen extrems locals tant pel que fa a l'espai com a l'escala

$(\hat{x},\hat{y};\hat{t})={\mathrm{argminmaxlocal}}_{(x,y;t)}(D_{\mathrm{n}\mathrm{o}\mathrm{r}\mathrm{m}}L)(x,y;t)$

L'algorisme de detecció de cantonades de Wang i Brady

El detector Wang i Brady considera que la imatge és una superfície i busca llocs on hi hagi una gran curvatura al llarg d'una vora de la imatge. En altres paraules, l'algorisme busca llocs on la vora canvia de direcció ràpidament. El córner, $C$, ve donada per:

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

on $𝐭$ és el vector unitari perpendicular al gradient, i $c$ determina fins a quin punt el detector és de fòbic. Els autors també assenyalen que cal suavitzar (se suggereix gaussian) per reduir el soroll.

El detector de cantonada SUSAN

SUSAN és un acrònim que significa el nucli assimilador del segment univalu més petit. Aquest mètode és objecte d'una patent britànica de 1994 que ja no està en vigor.

Per a la detecció de característiques, SUSAN col·loca una màscara circular sobre el píxel que es vol provar (el nucli). La regió de la màscara és $M$, i un píxel d'aquesta màscara està representat per $\overrightarrow{m}\in M$. El nucli és a ${\overrightarrow{m}}_0$. Cada píxel es compara amb el nucli mitjançant la funció de comparació:

$c(\overrightarrow{m})=e^{-{\left(\frac{I(\overrightarrow{m})-I({\overrightarrow{m}}_0)}{t}\right)}^6}$

on $t$ és el llindar de diferència de brillantor, $I$ és la brillantor del píxel i la potència de l'exponent s'ha determinat empíricament. Aquesta funció té l'aspecte d'una funció rectangular o de barret de copa suavitzada.

El detector de cantonada Trajkovic i Hedley

De manera similar a SUSAN, aquest detector prova directament si un pegat sota un píxel és autosimilar examinant els píxels propers. $\overrightarrow{c}$ és el píxel a considerar, i $\overrightarrow{p}\in P$ és punt en un cercle $P$ centrat al voltant $\overrightarrow{c}$. El punt ${\overrightarrow{p}}^{\prime }$ és el punt contrari a $\overrightarrow{p}$ al llarg del diàmetre.

La funció de resposta es defineix com:

$r(\overrightarrow{c})=\underset{\overrightarrow{p}\in P}{\min }({(I(\overrightarrow{p})-I(\overrightarrow{c}))}^2+{(I({\overrightarrow{p}}^{\prime })-I(\overrightarrow{c}))}^2)$

Detectors de característiques basats en AST

AST és un acrònim que significa prova de segment accelerat. Aquesta prova és una versió relaxada del criteri de cantonada SUSAN. En lloc d'avaluar el disc circular, només els píxels d'un cercle de radi de Bresenham $r$ al voltant del punt candidat es consideren. Si $n$ els píxels contigus són almenys més brillants que el nucli $t$ o tot més fosc que el nucli per $t$, llavors el píxel sota el nucli es considera una característica. S'informa que aquesta prova produeix funcions molt estables. L'elecció de l'ordre en què es comencen a provar els píxels és l'anomenat problema de vint preguntes. La construcció d'arbres de decisió curts per a aquest problema dóna com a resultat els detectors de característiques computacionalment més eficients disponibles.

Síntesi automàtica de detectors

Trujillo i Olague van introduir un mètode pel qual s'utilitza la programació genètica per sintetitzar automàticament operadors d'imatge que poden detectar punts d'interès. Els conjunts de terminals i funcions contenen operacions primitives que són habituals en molts dissenys fets per l'home proposats anteriorment. Fitness mesura l'estabilitat de cada operador mitjançant la taxa de repetibilitat i promou una dispersió uniforme dels punts detectats a través del pla de la imatge. El rendiment dels operadors evolucionats s'ha confirmat experimentalment mitjançant seqüències d'entrenament i prova d'imatges transformades progressivament. Per tant, es considera que l'algorisme GP proposat és competitiu per als humans per al problema de la detecció de punts d'interès.

Detectors de punts d'interès espaciotemporal

L'operador Harris ha estat estès a l'espai-temps per Laptev i Lindeberg. Deixa $\mu$ denoteu la matriu de segon moment espaciotemporal definida per

$A=\sum _u\sum _v\sum _{w}h(u,v,w)\left[\begin{array}{ccc}{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{array}\right]=\left[\begin{array}{ccc}⟨L_x^2⟩& ⟨L_x{L}_y⟩& ⟨L_x{L}_t⟩\\ ⟨L_x{L}_y⟩& ⟨L_y^2⟩& ⟨L_y{L}_t⟩\\ ⟨L_x{L}_t⟩& ⟨L_y{L}_t⟩& ⟨L_t^2⟩\end{array}\right]$

Aleshores, per a una elecció adequada de $k<1/27$, es detecten punts d'interès espaciotemporal a partir dels extrems espaciotemporals de la següent mesura de Harris:

$H=\det (\mu )-\kappa {\mathrm{trace}}^2(\mu ).$