Usuari:Fco.javier.garcia.polo/Scale-invariant feature transform

Scale-invariant feature transform (SIFT) és un algorisme de visió per ordinador per detectar i descriure les característiques locals de les imatges. L'algorisme va ser publicat per David Lowe el 1999.

Les aplicacions inclouen el reconeixement d'objectes, la cartografia i la navegació robòtica, costura de la imatge, modelat 3D, reconeixement de gestos, de seguiment de vídeo, i moviment. L'algorisme està patentat als Estats Units d'Amèrica, i pertany a la Universitat de la Colúmbia Britànica.

Resum

Per a qualsevol objecte en una imatge, els punts d'interès en l'objecte poden ser extrets per proporcionar una descripció de les característiques de l'objecte. Aquesta descripció, extreta d'una imatge d'entrenament, es pot utilitzar per identificar l'objecte quan es tracta de localitzar l'objecte en una imatge de prova que conté molts altres objectes. Per dur a terme un reconeixement fiable, és important que les característiques extretes de la imatge d'entrenament siguin detectables fins i tot en els canvis d'escala de la imatge, del soroll i de la il·luminació. Aquests punts es troben en general en regions d'alt contrast de la imatge, com ara les vores de l'objecte.

Una altra característica important d'aquestes característiques fos que les posicions relatives entre aquests punts a l'escena original no poden canviar d'una imatge a una altra. Per exemple, si només les quatre cantonades d'una porta van ser utilitzats com a característiques, aquestes haurien de funcionar independentment de la posició de la porta, però si alguns punts del quadre també s'utilitzessin, el reconeixement donaria error si la porta estigués oberta o tancada. De la mateixa manera, les característiques ubicades en objectes articulats o flexibles no solen treballar si no existeix cap canvi en la seva geometria interna entre dues imatges de les que seran processades. No obstant això, en la pràctica SIFT detecta i utilitza un nombre molt gran de característiques de les imatges, el que redueix l'aparició d'errors causats per aquestes variacions.

Existeix el mètode patentat de Lowe amb què es pot identificar els objectes, fins i tot entre distints objectes desordenats, com l'oclusió parcial de l'objecte, ja que el seu descriptor de característiques SIFT és invariant en escala uniforme, orientació i distorsió, i parcialment invariant a canvis d'il·luminació.

Mètode de David Lowe

Els punts clau SIFT dels objectes primer s'extreuen d'un conjunt d'imatges referència i s'emmagatzema en una base de dades. Un objecte es reconeix en una nova imatge de forma individual comparant cada característica de la nova imatge amb aquesta base de dades i cercant un candidat que coincideixi basat en la distància euclidiana dels vectors de característiques. De tot el conjunt de coincidències, els subconjunts de punts claus amb d'acord amb l'objecte, i la seva ubicació, escala i l'orientació de la nova imatge és identificada per filtrar les coincidències correctes.

La determinació dels grups consistents es realitza ràpidament mitjançant la implementació d'una taula hash eficient de la transformada general de Hough. Cada grup de 3 o més característiques han d'estar d'acord sobre un objecte i el seu proposat se sotmet a una verificació més detallada i, posteriorment, es descarten els valors atípics. Finalment, la probabilitat d'un conjunt particular de característiques indica la presència d'un objecte que és processat, tenint en compte la precisió d'ajust i el nombre de probables falses correctes. L'objecte coincident que passi tots els tests pot ser identificat com a correcte amb un al grau de confiança.

Problema	Tècnica	Avantatge
Localització clau / Escala / Rotació	DoG / Escala-espai piramidal / Assignació d'orientació	Precisió, estabilitat, escala i invariància rotacional
Distorsió geomètrica	Confusió / Mostreig de l'orientació de la imatge	Invariància afí
Indexació i coincidència	Veí més proper / Best Bin First search	Eficiència / velocitat
Identificació de cluster	Transformada Hough	Plantejament de models
Model de verificació / Detecció de contorns	Lineal de mínims quadrats	Millor tolerància a errors en coincidències menors
Acceptació de hipòtesi	Anàlisi de probabilitat Bayesiana	Fiabilitat

Etapes

Detecció d'escala invariant característica

El mètode Lowe per a la generació d'una imatge característica transforma una imatge en una gran col·lecció de vectors de característics, cadascun d'ells és invariant a la traducció de la imatge, l'escala i la rotació, en part invariant a canvis d'il·luminació i robust a la distorsió geomètrica local. Aquestes característiques comparteixen propietats similars amb les neurones a l'escorça temporal inferior que s'utilitzen per al reconeixement d'objectes en la visió dels primats. [6] Els llocs clau es defineixen com els màxims i mínims del resultat de la diferència de la funció gaussiana aplicada en l'escala de l'espai a una sèrie d'imatges allisades i mostrejades. Orientacions dominants són assignades per localitzar punts clau. Aquests passos asseguren que els punts clau són més estables per a la comparació i el reconeixement. Als descriptors SIFT la distorsió afí local s'obté considerant un radi de píxels al voltant de la ubicació clau, distorsió i remostratge de la imatge local d'orientació.

Relació de característiques i indexació

Indexació consisteix en l'emmagatzematge de claus SIFT i la identificació de les claus que coincideixen de la nova imatge. Lowe utilitza una modificació de l'algorisme d'arbre k-d que s'anomena el mètode Best-bin-first search [7] aquest pot identificar els veïns més propers amb alta probabilitat d'utilitzar una quantitat limitada de computació. L'algorisme de BBF utilitza una cerca de comanda modificada a l'algorisme d'arbre k-d a fi que els contenidors en les característiques d'espais se cerquin en l'ordre de la seva distància més propera a la ubicació de la consulta. Aquest ordre de recerca requereix l'ús d'una cua de prioritat basat en heap per a la determinació eficient de l'ordre de recerca.

El millor punt de coincidència per a cada punt clau es troba mitjançant la identificació del seu veí més proper a la base de dades de punts clau a partir d'imatges d'entrenament. Els veïns més propers es defineixen com els punts clau amb la distància mínima euclidiana del vector descriptor donat. La probabilitat que una comparació sigui correcta potser determinada tenint en compte la relació de distància del veí més proper a la distància del segon més proper.

Lowe [5] va rebutjar totes les coincidències en què la relació de distància és més gran que 0,8, el que elimina el 90% de les comparacions falses mentre es descarten menys del 5% de les coincidències correctes. Per millorar encara més l'eficiència de l'algorisme de recerca de best-bin-fist es va tallar després de comprovar els primers 200 candidats veïns més propers. Per a una base de dades de 100.000 punts clau,proporciona una acceleració en la recerca del veí més proper per al voltant de 2 ordres de magnitud, per als resultats en menys d'un 5% de reducció en el nombre d'aparellaments correctes.

Cúmul d'identificació per " Hough transform voting"

La transformada de Hough es fa servir per a les hipòtesis de dispersió fiables per buscar les claus i estar d'acord amb un model particular posat. Aquesta transformada identifica grups de característiques amb una interpretació coherent mitjançant l'ús de cada característica per votar per tots els objectes que són consistents amb aquesta característica. Quan els grups de característiques es troben a votar al mateix posat d'un objecte, la probabilitat d'interpretació que sigui correcta és molt més gran que per a qualsevol característica individual. Una entrada en una taula hash es crea amb la predicció de la ubicació del model, l'orientació i l'escala. La taula hash es busca per identificar a tots els grups d'almenys 3 entrades en un contenidor, i als contenidors es classifiquen en ordre decreixent de grandària.

Cada un dels punts clau SIFT especifica la ubicació en 2D, l'escala i orientació, i cada punt clau coincident en la base de dades té un registre dels seus paràmetres relatius a la imatge d'entrenament en què es va trobar. La transformada de similitud implícita en aquests quatre paràmetres es busca per només per fer una aproximació als de 6 graus de llibertat posats a l'espai per un objecte 3D i també no té en compte les deformacions no rígides. Per tant, Lowe[5] utilitzen mides generals bin de 30 graus per a l'orientació, un factor de 2 per escala, i 0,25 vegades la màxima dimensió de la imatge projectada d'entrenament (utilitzant l'escala de valor de referència) per a la ubicació. Les mostres clau SIFT generat en l'escala més gran es donen dues vegades el pes dels de menor escala. Això significa que gran l'escala es busca per l'efecte capaç de filtrar els veïns més probables per a la comprovació de l'escala més petita. Això també millora el rendiment del reconeixement per part de donar més pes a l'escala menys sorollosa. Per evitar el problema dels efectes dels límits en l'assignació de contenidor, cada un dels vots de punts clau coincidents per als dos contenidors més propers en cada dimensió, es dóna un total de 16 entrades per a cada hipòtesi.

Model de verificació per "linear least squares"

Cada cluster indentificat es fa servir com a subjecte pel procés de verificació en el qual la solució linear least squares és formada amb els paràmetres de la transformació afí en relació amb el model de la imatge. La transformació afí d'un punt al model [x y]^T a un punt a la imatge [u v]^T pot ser escrita de la següent manera:

${\begin{bmatrix}u\\v\end{bmatrix}}={\begin{bmatrix}m1&m2\\m3&m4\end{bmatrix}}{\begin{bmatrix}x\\y\end{bmatrix}}+{\begin{bmatrix}tx\\ty\end{bmatrix}}$

On el model de traducció és [tx ty]^T i la rotació afí, l'escala, i l'extensió és representada pels paràmetres m1, m2, m3 and m4. Per resoldre els paràmetres de transformació de l'equació anterior pot ser reescrit per recollir les incògnites en un vector columna.

${\begin{bmatrix}x&y&0&0&1&0\\0&0&x&y&0&1\\....\\....\end{bmatrix}}{\begin{bmatrix}m1\\m2\\m3\\m4\\tx\\ty\end{bmatrix}}={\begin{bmatrix}u\\v\\.\\.\end{bmatrix}}$

Aquesta equació mostra una sola coincidència, però de qualsevol nombre de coincidències poden ser afegides, amb cada coincidència contribuint dues files per la primera i l'última matriu. Si més no tres coincidències són necessàries per a proporcionar una solució. Podem escriure aquest sistema lineal com:

$A{\hat {\mathbf {x} }}\approx \mathbf {b} ,$

On A és una matriu coneguda m-by-n (usually with m > n), x és un vector paràmetre no conegut de dimensions n, i b és un vector de mesures conegut de dimensions m.

Per tant el vector minimitzat ${\hat {\mathbf {x} }}$ és la solució de l'equació

$A^{T}\!A{\hat {\mathbf {x} }}=A^{T}\mathbf {b} .$

La solució del sistema lineal d'equacions ve donada en termes de la matriu $(A^{T}A)^{-1}A^{T}$, anomenada pseudoinverse de A, per

${\hat {\mathbf {x} }}=(A^{T}\!A)^{-1}A^{T}\mathbf {b} .$

El qual minimitza la suma dels quadrats, de les distàncies dels llocs model de projecció als llocs d'imatge corresponent.

Detecció de valors extrems

Els valors extrems poden ser eliminats mitjançant la comprovació d’acords entre cada imatge característica i la model, donada la solució dels paràmetres.

Tenint en compte la solució de mínims quadrats lineals, cada partit està obligat a acceptar la meitat del rang d'error que es va utilitzar per als paràmetres en els contenidors de la transformada de Hough.

Com a valors atípics es descarten, la solució de mínims quadrats lineals es torna a resoldre amb punts restants, i el procés es reitera. Si hi ha menys de 3 punts restants després de descartar els valors extrems, llavors el partit es rebutja.

A més, un joc amb fase de dalt a baix es fa servir per afegir més partits que estan d'acord amb la posició del model de projeccions, que podrien haver estat omesos de la paperera de la transformada de Hough, a causa de la similitud de transformar l'aproximació o altres errors.

La decisió final d'acceptar o rebutjar un model d’hipòtesi es basa en un model probabilístic detallat. Aquest mètode calcula primer el nombre esperat de falsos partits que el model posa, donada la mida projectada del model, el nombre de característiques dins de la regió, i la precisió de l'ajust. Una anàlisi de probabilitat bayesiana dóna la probabilitat que l'objecte estigui present basat en el nombre actual de característiques coincidents trobades. Un model serà acceptat si la probabilitat final per a una correcta interpretació és més gran que 0,98. El reconeixement d'objectes basat en Lowe SIFT dóna excel·lents resultats, excepte en l'ample de les variacions de la il·luminació i, en transformacions no-rígides.

Mètodes que competeixen pel reconeixement a escala objecte invariant per mitjà d'oclusions parcial/desordenades

RIFT: és una generalització de rotació-invariant de SIFT. El descriptor RIFT es construeix amb pegats circulars normalitzat dividit en anells concèntrics d'igual amplada i dins de cada anell es computa un histograma d'orientació dels gradients. Per mantenir la invariància de la rotació, l'orientació es mesura en cada punt respecte a la direcció que apunta cap a fora des del centre.

G-RIF (Generalized Robust Invariant Feature): és un descriptor de context general que codifica l'orientació de la vora, la densitat de la vora i la informació de tonalitat d'una manera unificada combinant la informació perceptual amb la codificació espacial. El sistema de reconeixement d'objectes utilitza veïns de votació basat en context per estimar els models d'objectes.

SURF (Speeded Up Robust Features ): és una escala d'alt rendiment i un detector de rotació invariant de punts d'interès / descriptor reclama l'aproximació o fins i tot superar esquemes proposats anteriorment pel que fa a la repetibilitat, el caràcter distintiu, i la robustesa. SURF es basa en imatges integrals per imatges convolucionades per reduir el temps de càlcul, es basa en les fortaleses dels detectors de líders existents i dels descriptors. Descriu la distribució de Haar wavelet respostes dels punt d'interès veïns. Les imatges integrals s'utilitzen per la velocitat i només 64 dimensions són utilitzades per reduir el temps de càlcul de característiques i de partit. El pas d'indexació es basa en el signe de la Laplace, que augmenta la velocitat de joc i la solidesa dels descriptors.

PCA-SIFT and GLOH són variants de SIFT. El descriptor PCA-SIFT és un vector d'imatges gradients en direcció x i y calculada dins de la regió de suport. La regió de gradient es mostreja en 39x39 posicions, per tant, el vector té una dimensió de 3042. La dimensió es redueix. La dimensió es redueix a 36, amb l'anàlisi del component principal (PCA). L'histograma del factor de proximitat - orientació (GLOH) és una extensió del descriptor SIFT dissenyat per augmentar la seva solidesa i caràcter distintiu. El descriptor SIFT es calcula per una ubicació de la xarxa log-polar amb tres contenidors en direcció radial (els ràdis s'estableixen pels valors 6, 11 i 15) i 8 en direcció angular, el que es tradueix en 17 contenidors d'ubicació. El contenidor central no està dividit en direccions angulars. Les orientacions dels gradients es quantifiquen en 16 contenidors que resulta en histograma de 272 contenidors. La mida d'aquest descriptor es redueix amb l'anàlisi del component principal (PCA). La matriu de covariància de PCA es calcula sobre els pegats de la imatge recollida a partir de diverses imatges. Les 128 més grans vectors s'utilitzen per a la descripció.

Wagner et al. ha desenvolupat dos algorismes de reconeixement d'objectes dissenyats, tenint en compte, especialment amb les limitacions dels actuals telèfons mòbils. En contrast amb l'enfocament clàssic de SIFT Wagner et al. utilitzar el FASTdetector d'angle per a la detecció de característiques. L'algorisme també fa una distinció entre la fase de preparació fora de línia on es creen funcions en diferents nivells d'escala i la fase on-line on les característiques només es creen en el nivell de l'escala actual de la imatge fixa de la càmera del telèfon. A més, les característiques són creades a partir d'un pegat fix de píxels 15x15 i de formar un descriptor SIFT amb només 36 dimensions. L'enfocament s'ha ampliat mitjançant la integració d'un arbre de Vocabulari Escalable a la "pipeline" de reconeixement. Això permet el reconeixement eficaç d'un major nombre d'objectes en els telèfons mòbils. L'enfocament és principalment limitat per la quantitat d'espai disponible en RAM.

Característiques

La detecció i descripció de les característiques de la imatge local pot ajudar en el reconeixement d'objectes. Les característiques SIFT són locals i es basa en l'aparença de l'objecte en els punts d'interès particular, i són invariants a imatge a escala i rotacions. També són robustos als canvis en la il·luminació, el soroll i canvis menors en el punt de vista. A més d'aquestes propietats, que són molt distintius, relativament fàcil d'extreure, permeten la identificació d'objectes correcta amb baixa probabilitat de desajustament i són fàcils de combinar una base de dades (grans) de les característiques locals. La descripció d'un objecte pel conjunt de característiques SIFT és robusta a l'oclusió parcial, tan sols 3 característiques SIFT d'un objecte són suficients per calcular la seva ubicació i el seu posat. El reconeixement es pot realitzar en primer prop a temps real, almenys per a petites bases de dades i en maquinari moderna.

Algorismes

Escala espai-extrems de detecció

Aquesta és l'etapa on els punts d'interès, que es diuen punts clau en el marc de SIFT, es detecten. Per això, la imatge és convolucionada amb filtres gaussians a diferents escales, i després la diferència d'imatges borroses de Gauss successives es prenen. Després es prenen els punts clau com màxims / mínims de la diferència gaussiana (DOG) que es produeixen en múltiples escales. En concret, un DoG de la imatge $D\left(x,y,\sigma \right)$ està donat per

$D\left(x,y,\sigma \right)=L\left(x,y,k_{i}\sigma \right)-L\left(x,y,k_{j}\sigma \right)$,

on $L\left(x,y,k\sigma \right)$ és la convolució de la imatge original $I\left(x,y\right)$ amb el desenfocament gaussià $G\left(x,y,k\sigma \right)$ a escala $k\sigma$, és a dir,

$L\left(x,y,k\sigma \right)=G\left(x,y,k\sigma \right)*I\left(x,y\right)$

Per tant, una imatge DoG entre escales $k_{i}\sigma$ i $k_{j}\sigma$ és només la diferència de les imatges borroses de Gauss en les escales $k_{i}\sigma$ and $k_{j}\sigma$. Per escala espai de detecció d'extrems en l'algorisme SIFT, la imatge és la primera convolucionada amb imatges borroses de Gauss en diferents escales. Les imatges convolucionades estan agrupades en octaves (1 / 8 correspon a duplicar el valor de $\sigma$), i el valor de $k_{i}$ es seleccionat de manera que obtenim un nombre fix d'imatges convolucionada per octava. A continuació, les imatges de diferència de Gauss es prenen del costat de les imatges borroses de Gauss per vuitena.

Una vegada que les imatges DoG s'han obtinguts, els punts clau són identificats com els mínims / màxims locals de les imatges DoG a través d'escales. Això es fa mitjançant la comparació de cada píxel de la imatge DoG amd els seus vuit veïns en la mateixa escala i nou píxels corresponents a pixels veïns en cadascuna de les escales veïnes. Si el valor del píxel és el màxim o mínim entre tots els píxels comparats, aquest és seleccionat com acandidat a ser un punt clau. Aquest pas de detecció de punt clau és una variació d'un dels detecció blob mètodes desenvolupats per Lindeberg mitjançant la detecció de l'escala-espai extrems de l'escala normalitzada, Laplaciana, que detecta els punts que són extrems locals en relació amb l'espai i escala, en el cas discret per les comparacions amb aproximadament 26 veïns en un espai discretitzat de volum escala - espai. La diferència d'operadors Gaussians pot ser vist com una aproximació a la laplaciana, s'expressa aquí en una piràmide del menú.

Punts claus de localització

Després que els extrems d'espai i escala es detecten (la seva ubicació es mostra a la imatge superior), l'algorisme SIFT descarta punts clau de baix contrast (els punts restants es mostren en la imatge del mig) i després es filtra aquells ubicats en les vores. El resultat conjunt de punts clau es mostra a l'última imatge.

La detecció d'extrems d'escala-espai produeix massa candidats a punt clau, algunes de les quals són inestables. El següent pas en l'algorisme és realitzar un ajust detallat de les dades properes a la ubicació exacta, l'escala, i la ràtio de curvatures principals. Aquesta informació permet rebutjar punts amb un contrast baix (i per tant són sensibles al soroll) o no estan ben localitzats al llarg d'una vora.

Interpolació de dades properes per una posició exacta

En primer lloc, per a cada punt clau candidat, la interpolació de dades properes es fa servir per determinar amb exactitud la seva posició. El plantejament inicial era localitzar cada punt clau just en el lloc i l'escala del punt clau candidat. El nou enfocament calcula la interpolació de la ubicació de l'extrem, la qual cosa millora substancialment el joc i l'estabilitat. La interpolació es realitza mitjançant l'equació quadràtica de Taylor de la funció de la diferència d'escala i espai de Gauss, $D\left(x,y,\sigma \right)$ amb el punt clau candidat com l'origen. Aquesta expansió de Taylor ve donada per:

$D({\textbf {x}})=D+{\frac {\partial D^{T}}{\partial {\textbf {x}}}}{\textbf {x}}+{\frac {1}{2}}{\textbf {x}}^{T}{\frac {\partial ^{2}D}{\partial {\textbf {x}}^{2}}}{\textbf {x}}$

on D i els seus derivats són avaluats en el punt clau candidat i ${\textbf {x}}=\left(x,y,\sigma \right)$ és el desplaçament des d'aquest punt. La ubicació de l'extrem, ${\hat {\textbf {x}}}$, es determina prenent la derivada d'aquesta funció respecte a ${\textbf {x}}$ i s’estableix a zero. Si el desplaçament ${\hat {\textbf {x}}}$ és més gran que $0.5$ en qualsevol direcció, llavors això és una indicació que l'extrem està més a prop d'un altre punt clau candidat. En aquest cas, el punt clau candidat es canvia i es realitza la interpolació en comptes d'aquest punt. En cas contrari el desplaçament s'afegeix al seu punt clau candidat per obtenir l'estimació interpolada per a la ubicació de la extrem. Una determinació similar de subpixel de les ubicacions d'escala-espai es realitza en una implementació a temps real basada en piràmides híbrides desenvolupades per Lindeberg i els seus companys de treball

Descart de punts claus de baix contrast

Per descartar els punts clau amb baix contrast, el valor de l'expansió de Taylor de segon ordre$D({\textbf {x}})$ es calcula en el desplaçament ${\hat {\textbf {x}}}$ Si el valor és menor a $0.03$, el candidat a punt és descartat. En cas contrari, es manté, amb destinació final ${\textbf {y}}+{\hat {\textbf {x}}}$ and scale $\sigma$, where ${\textbf {y}}$ és la ubicació original del punt clau a escala $\sigma$.

Eliminació de respostes de vora

La funció DoG tindrà respostes contundents al llarg de les vores, encara que el punt clau candidat no és sòlid a petites quantitats de soroll. Per tant, per tal d'augmentar l'estabilitat, hem d'eliminar els punts clau que han poc determinants però que tenen poques respostes d'alt avantatge. Per als pics poc definits en la funció DoG, la curvatura principal a través de la vora seria molt més gran que la curvatura principals al llarg d'ella. Trobar aquestes quantitats de curvatures principals a resoldre per als valors propis de segon ordre de la matriu de Hesse, H:

${\textbf {H}}={\begin{bmatrix}D_{xx}&D_{xy}\\D_{xy}&D_{yy}\end{bmatrix}}$

Els valors propis de laHsón proporcionals a les curvatures principals de D. Resulta que la proporció dels dos valors propis, per exemple $\alpha$ és el més gran, i$\beta$ el més petit, amb una relació $r=\alpha /\beta$, és suficient a efectes de SIFT. El rastre deH, és a dir, $D_{xx}+D_{yy}$, ens dóna la suma dels dos valors propis, mentre que el seu determinant, és a dir,$D_{xx}D_{yy}-D_{xy}^{2}$, rendiments del producte. la relació ${\text{R}}=\operatorname {Tr} \left({\textbf {H}}\right)^{2}/\operatorname {Det} \left({\textbf {H}}\right)$ es pot demostrar que és igual a $\left(r+1\right)^{2}/r$, que només depèn de la relació dels valors propis en comptes dels seus valors individuals. R és mínima quan els valors propis són iguals entre si. Per tant, com més gran és la diferència absoluta entre els dos valors propis, el que equival a una diferència superior absoluta entre les dues curvatures principals de D, major serà el valor de R. D'això es desprèn que, per a alguns llindars de valor propi $r_{\text{th}}$, si R d'un punt clau candidat és més gran que $\left(r_{\text{th}}+1\right)^{2}/r_{\text{th}}$, es determina que el punt clau que no està ben localitzat i per tant, es rebutja. El nou enfocament utilitza $r_{\text{th}}=10$. Aquest pas del procés per a la supressió de les respostes a les vores é una transferència d'un enfocament corresponent a l'operador de Harris detecció de la cantonades. La diferència és que la mesura del llindar es calcula a partir de la matriu hessiana en lloc d'una matriu de segon moment.

Orientació de l'assignació

En aquest pas, cada punt clau se li assigna una o més orientacions sobre la base de les direccions locals de la imatge gradient. Aquest és el pas clau en l'assoliment d'invariància rotacional com el punt clau descriptor es pot representar en relació amb aquesta orientació i, per tant, aconseguir invariància a la rotació de la imatge. En primer lloc, la imatge de suavitzada de Gauss $L\left(x,y,\sigma \right)$ en el punt clau de l'escala $\sigma$ es pren perquè tots els càlculs es realitzin de manera invariant en escala. Per a una mostra de la imatge $L\left(x,y\right)$ a escala $\sigma$, la magnitud del gradient, $m\left(x,y\right)$, i l'orientació, $\theta \left(x,y\right)$, es calcula prèviament mitjançant les diferències de píxels:

$m\left(x,y\right)={\sqrt {\left(L\left(x+1,y\right)-L\left(x-1,y\right)\right)^{2}+\left(L\left(x,y+1\right)-L\left(x,y-1\right)\right)^{2}}}$

$\theta \left(x,y\right)=\tan ^{-1}\left({\frac {L\left(x,y+1\right)-L\left(x,y-1\right)}{L\left(x+1,y\right)-L\left(x-1,y\right)}}\right)$

Els càlculs de la magnitud i de la direcció del gradient es fan per a cada píxel en una regió veïna al voltant del punt clau en la imatge borrosa Gaussiana L. es forma un histograma d'orientació amb 36 contenidors, cada un dels contenidors cobreix 10 graus. Cada mostra de la finestra de veïns sumat a l'histograma de contenidor és ponderat per la magnitud gradient i per una finestra circular de Gauss ponderada amb un $\sigma$ que és 1,5 vegades més gran que la de l'escala del punt clau. Els pics en l'histograma corresponen a orientacions dominants. Una vegada que l'histograma està ple, les orientacions corresponents als pics més alts i els pics locals que estan dins del 80% dels pics més alts s'assignen al punt clau. En el cas que s'assignin múltiples orientacions, un punt clau addicional es crea amb la mateixa ubicació i escala que el punt clau original per a cada orientació addicional.

Descriptor de punts claus

S’ha vist en passos previs llocs on són els punts claus a escales particulars i les orientacions que se’ls assignen. Això va assegurar la invariància de la ubicació de la imatge, escala i rotació. Ara volem calcular un vector descriptor per cada punt clau de tal manera que el descriptor sigui fort y independent de les variacions restants, tals com la il·luminació, punt de vista en 3D, etc. Aquest pas es realitza en la imatge més propera de l'escala del punt clau. En primer lloc, una sèrie d’histogrames d’orientació creen conjunts de 4x4 píxels amb 8 contenidors cada un. Aquests histogrames es calculen a partir dels valors de la magnitud i l'orientació de les mostres en una regió de 16x16 en tot el punt clau de tal manera que cada histograma conté mostres de 4x4 subregions de la regió veïna original. Les magnituds són ponderades per una funció Gaussiana amb σ igual a la meitat de l'ample de la finestra del descriptor. El descriptor es converteix en un vector de tots els valors d’aquests histogrames. Atès que hi ha 4x4=16 histogrames cada un amb 8 compartiments del vector té 128 elements. Aquest vector es normalitza a la unitat de longitud amb la finalitat de millorar la invariància als canvis i la il·luminació. Per reduir aquests efectes d’il·luminació no lineal d’un umbral de 0,2 s’aplica i el vector es normalitza novament. Tot i la dimensió del descriptor (128) sembla alta, els descriptors de mida menor no funcionen tan bé en tota la llista de feines corresponents [5] i el cost computacional segueix sent més baix a causa de la BBF aproximada (vegeu més avall), mètode utilitzat per trobar el veí més proper. Es van seguir fent millors descriptors però contemplant el perill addicional de l'augment de la sensibilitat de la distorsió i l'oclusió. També està demostrat que la precisió característica de joc es superior al 50% per als canvis de punt de vista fins a 50 graus. Per tant, els descriptors SIFT són invariants a petits canvis d'afinació. Per provar el caràcter distintiu dels descriptors SIFT, la precisió corresponent es mesura també en contra dels diferents nombres de punts claus en la base de dades de prova, i es demostra que l'adequació de la precisió disminueix molt a poc a poc per a bases de dades molt grans, els que demostra que les característiques del SIFT són molt distintives.

Comparació de característiques SIFT amb altres característiques locals

Existeix un extens estudi realitzat sobre l'avaluació de l'acompliment dels diferents descriptors locals, inclosa la SIFT, utilitzant una àmplia gamma de detectors [18]Els principals resultats es resumeixen a continuació.:

• Les característiques de SIFT i SIFT -like GLOH exhibeixen els nivells més alts the afinitat per a una transformació afí de 50 graus. Després d'aquest límit de transformació, els resultats comencen a ser poc fiables.
• El distintiu dels descriptors es mesura amb la suma dels valors propis dels descriptors, que s'obté per l'anàlisi de components principals dels descriptors normalitzats per la seva variància. Això correspon a la quantitat de variància capturada pels diferents descriptors, per tant, el seu caràcter distintiu. Les característiques de PCA-SIFT (Anàlisi de Components Principals aplicada a descriptors SIFT ), GLOH SIFT són les que donen els valors més alts.
• SIFT basat en descriptors superaren altres descriptors locals en escenes tant de textura i estructura, amb la diferència de major rendiment en l'escena amb textura.
• Per als canvis d'escala en el rang 2-2,5 i rotacions d'imatge en el rang de 30 a 45 graus, SIFT i SIFT basat en descriptors de nou superaren a altres descriptors locals amb contingut de l'escena, tant en textura com en estructura.
• Rendiment per a tots els descriptors locals degradades en les imatges introduïdes amb una important quantitat de desenfocament, amb la descriptors que es basen en les vores, com a forma de context, realitzant cada vegada pitjor amb l'augment progressiu del desenfocament. Això és a causa de les vores desapareixen en la cas d'una falta de definició alta. Però GLOH, PCA-SIFT i SIFT encara treballen millor que les altres. Això també es pot dir en l'avaluació en el cas de canvis d'il·luminació.

Les avaluacions realitzades suggereixen fortament que SIFT basat en descriptors, la qual està basada en regions, és la més robusta i distintiva, per tant més adequat per a la coincidència de característiques. No obstant això, els descriptors més recents com el Surf no han estat avaluades en aquest estudi.

SURF s'ha demostrat que té un rendiment similar al de SIFT, mentre que al mateix temps, és molt més ràpid [19].

Recentment, una lleugera variació del descriptor que empren una xarxa irregular de histograma s'ha proposat que millora significativament el seu rendiment. [20] En lloc d'utilitzar una quadrícula de 4x4 cubs de histograma, tots els contenidors s'estenen fins al centre de la funció. Això millora la robustesa del descriptor de canvis a gran escala.

La tècnica SIFT-Rank va ser demostrada per millorar el rendiment del descriptor SIFT per coincidència de característiques afí. [21] Un descriptor SIFT-Rank és generat a partir d'un descriptor SIFT estàndard, mitjançant l'establiment de cada histograma de contenidor al seu rang en un arranjament ordenat de contenidors. La distància Euclidiana entre els descriptors SIFT-Rang és invariant a canvis arbitraris monotons en els valors de l'histograma del contenidor, i és relatiu al coeficient de correlació de Spearman.

Aplicacions

Reconeixement d'objectes utilitzant característiques SIFT

Donada la capacitat de SIFT per trobar punts clau distintius que són invariants a la ubicació, escala i rotació, i robust a transformacions afins i canvis en la il·luminació, aquests es poden utilitzar per al reconeixement d'objectes. Els passos que s'indiquen a continuació.

• En primer lloc, les característiques SIFT s'obtenen de la imatge d'entrada mitjançant l'algorisme descrit més amunt.
• Aquestes característiques es fan coincidir amb la base de dades de característiques SIFT obtinguda a partir de les imatges d'entrenament. Aquesta comparació es fa a través de la distància Euclidiana basat en el veí més proper. Per augmentar la robustesa, les coparacions són rebutjades pels punts clau perquè la relació entre la distància del veí més proper a la distància al segon veí més proper sigui més gran que 0,8. Això descarta moltes de la identificacions errònies derivades del desordre de fons. Finalment, per evitar els elevats costos de cerca per trobar la distància euclidiana-basada en la distància del veí més proper, un algorisme aproximat anomenat el best-bin-first algorithm és utilitzat. Aquest és un mètode ràpid per al retorn dels veïns més propers amb alta probabilitat, i pot donar augment de velocitat en un factor de 1000, mentre que la recerca del veí més proper (d'interès) ocupa el 95% del temps.
• Encara que la prova de relació de distància s'ha descrit anteriorment descarta moltes de la identificacions errònies derivades de desordre de fons, encara tenim coincidències que pertanyen a diferents objectes. Per tant, per incrementar la robustesa de la identificació d'objectes, volem agrupar aquelles característiques que pertanyen a un mateix objecte i rebutgen les coincidències que sobren en el procés d'agrupació. Això es fa utilitzant la transformada de Hough. Això li permetrà identificar els grups de característiques per votar el mateix objecte posat. Quan els grups de característiques es troben a seleccionar per un mateix objecte posat, la probabilitat d'interpretació que sigui correcta és molt més gran que per a qualsevol característica individual. Cada selecció de punts clau per al conjunt d'objectes suposa que són consistents amb la ubicació dels punts clau, l'escala i l'orientació. Els contenidors en els quals s'acumulen almenys tres seleccions de punts clau s'identifiquen com a objecte candidat per comparar com a correcte.
• Per a cada grup de candidats, una solució de mínims quadrats pels millors paràmetres estimats de projecció afí en relació a la imatge d'entrenament de la imatge d'entrada obtinguda. Si la projecció d'un punt clau a través d'aquests paràmetres es troba dins de la meitat del rang d'error que es va utilitzar per als paràmetres en els contenidors de la transformada de Hough, el punt clau de coincidència es manté. Si hi ha menys de 3 punts després de descartar els valors extrems al contenidor, l'objecte per la compraració serà rebutjat. L'ajust de mínims quadrats es busca per repetir fins que no hi hagi rebutjos. Això funciona millor per reconeixement de superfície plana que al reconeixement d'objectes 3D des del model afí no hi ha una afinitat per objectes 3D.

Les característiques SIFT en essència es poden aplicar a qualsevol tasca que requereixi la identificació d'objectes en diferents imatges. S'ha treballat en aplicacions com ara el reconeixement de les categories d'objecte en particular en les imatges 2D, reconstrucció 3D, "motion tracking" i segmentació, localització robòtica, composició panoràmica de la imatge i calibratge epipolar.

Robot de localització i cartografia

En aquesta aplicació, un sistema estèreo trinocular es fa servir per determinar les estimacions 3D amb les ubicacions dels punts clau. Els punts clau s'utilitzen només quan apareixen a les 3 imatges amb diferències consistents. Com el moviment del robot, es localitza mitjançant coincidències amb noves característiques en els actuals mapes 3D, i després gradualment incorpora funcions al mapa, mentres actualitza les seves posicions en 3D usant un filtre de Kalman. Això proporciona una solució robusta i precisa al problema de la localització de robots en entorns desconeguts.

Panorama stitching

El descriptor SIFT pot ser utilitzat en la costura d'imatges panoràmiques en reconstrucció automàtic per a imatges no panoràmiques. Les característiques extretes de les imatges d'entrada es comparen entre si per trobar k-veïns més propers per a cada característica. Aquestes correspondències s'utilitzen per trobar una imatge candidat m que coincideixi per a cada imatge. Les homografies entre parelles d'imatges són processades utilitzant RANSAC i un model probabilístic és utilitzat per la verificació. Perquè no hi ha cap restricció en la imatges d'entrada, una búsqueda gràfica s'aplica per trobar els components connectats de tal manera que coincideixi amb la imatge de cada component que correspondrà a un panorama. Finalment, per a cada paquet d'ajust Bundle adjustment es creat per resoldre els paràmetres de la càmera, i el panorama es realitza mitjançant multi-banda de fusió. A causa del reconeixement d'objectes SIFT enfocat a panorama, el sistema resultant es insensible a l'ordenació, orientació, escala i il·luminació de les imatges. Les imatges d'entrada poden contenir múltiples panorames i imatges de soroll (algunes de les quals ni tan sols poden ser part de la imatge composta), i seqüències panoràmiques són reorganitzades i representades com a sortida.

Modelatge escena 3D, reconeixement i seguiment

Aquesta aplicació utilitza les característiques SIFT de reconeixement d'objectes 3D i modelatge en 3D en el context de la realitat augmentada, on els objectes sintètics amb precisió es superposen a imatges reals. El SIFT matching es fa per una sèrie d'imatges 2D d'una escena o un objecte pres des de diferents angles. Es fa servir amb bundle adjustment per crear un model 3D de l'escassa escena vista i recuperar al mateix temps el pla de la càmera i els paràmetres de calibratge. A continuació, la posició, orientació i grandària dels objectes virtuals es defineixen en relació amb el sistema de coordenades del model de recuperació. Per moviments de comparació, les característiques SIFT de nou s'extreuen del quadre de vídeo actual i s'adapten a les característiques ja calculades, donant com a resultat un conjunt de correspondències de 2D a 3D. Aquestes correspondències s'utilitzen per calcular el pla de la càmera per a la projecció virtual i el renderitzat final. Una tècnica de regularització es fa servir per reduir la fluctuació en la projecció virtual.

Descriptors SIFT 3D per reconeixement d'accions humanes

Extensions del descriptor SIFT per a dimensions 2 +1 espaciotemporals de dades en el context del reconeixement de l'acció humana en les seqüències de vídeo han estat estudiats en aquest apartat. El càlcul de posicions locals que depenen de la posició d'histogrames en l'algorisme SIFT 2D són esteses de dues a tres dimensions per descriure les característiques SIFT en un domini espaciotemporal. Per a l'aplicació de reconeixement de l'acció humana en una seqüència de vídeo, presa de mostres dels vídeos d'entrenament es porta a terme ja sigui en els punts d'interès espaciotemporal o en llocs determinats a l'atzar, temps i escales. Les regions espaciotemporals al voltant d'aquests punts d'interès, es descriuen utilitzant el descriptor SIFT 3D. Aquests descriptors són llavors agrupats per formar un model Bag of words espaciotemporal. Els descriptors SIFT 3D extrets dels vídeos d'assaig es comparen amb aquestes paraules per a la classificació de l'acció humana. Els autors informen de molt millors resultats amb el seu enfocament de descriptor SIFT 3D que amb altres mètodes com a simples descriptors SIFT 2D i Gradient Magnitude.

Anàlisi del cervell humà amb Imatges de Ressonància Magnètica en 3D

La técnica de morfometria basada en funcions (FBM) utilitza els extrems en una diferència d'escala espacial de Gauss per analitzar i classificar les imatges en 3D de ressonància magnètica (MRIs) del cervell humà. Els models FBM de la imatge probabilística com un collage de pel·lícules independents, condicionada a la geometria de la imatge i les etiquetes de grup, per exemple, subjectes sans i pacients amb malaltia d'Alzheimer (AD). Les característiques primer s'extreuen de les imatges individuals d'una diferència 4D de l'escala de Gauss espaciotemporal, llavors el model quant a la seva aparença, la geometria i el grup d'ocurrències d'estadístiques a través d'un conjunt d'imatges. FBM va ser validat en l'anàlisi d'AD mitjançant un conjunt de 200 imatges de ressonància magnètica volumètrica del cervell humà i la identificació automàtica dels indicadors establerts d'AD en el cervell i la classificació d'Alzheimer lleu en noves imatges amb una taxa de 80%.

Vegeu també

• Visió artificial
• Detector Viola Jones

Enllaços externs

• Rob Hess's implementation of SIFT consultat el 20 Mar 2010
• The Invariant Relations of 3D to 2D Projection of Point Sets, Journal of Pattern Recognition Research(JPRR), Vol. 3, No 1, 2008.
• Lowe, D. G., “Distinctive Image Features from Scale-Invariant Keypoints”, International Journal of Computer Vision, 60, 2, pp. 91-110, 2004.
• Mikolajczyk, K., and Schmid, C., "A performance evaluation of local descriptors", IEEE Transactions on Pattern Analysis and Machine Intelligence, 10, 27, pp 1615--1630, 2005.
• PCA-SIFT: A More Distinctive Representation for Local Image Descriptors
• Lazebnik, S., Schmid, C., and Ponce, J., Semi-Local Affine Parts for Object Recognition, BMVC, 2004.
• ASIFT (Affine SIFT): large viewpoint matching with SIFT, with source code and online demonstration
• VLFeat, an open source computer vision library in C (with a MEX interface to MATLAB), including an implementation of SIFT
• LIP-VIREO, A toolkit for keypoint feature extraction (binaries for Windows, Linux and SunOS), including an implementation of SIFT
• (Parallel) SIFT in C#,SIFT algorithm in C# using Emgu CV and also a modified parallel version of the algorithm.