Scale-invariant feature transfrom

De Viquipèdia
Dreceres ràpides: navegació, cerca

Scale-invariant feature transfrom (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.[1]

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.[2]

Resum[modifica | modifica el codi]

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[3] 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ó.[4]


Mètode de David Lowe[modifica | modifica el codi]

Els punts clau SIFT dels objectes primer s'extreuen d'un conjunt d'imatges referència[4] 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.[5]

Problema Tècnica Avantatge
Localització clau / Escala / Rotació DoG / Escala-espai piramidal / Assignació d'orientació Precisió, estabilitat, escala & invariància rotacional
Distorsió geomètrica Confusió / Mostreig de la 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[modifica | modifica el codi]

Detecció d'escala invariant característica[modifica | modifica el codi]

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ó[modifica | modifica el codi]

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"[modifica | modifica el codi]

La transformada de Hough s'utilitza 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"[modifica | modifica el codi]

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^TA)^{-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[modifica | modifica el codi]

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 s'utilitza 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.[6] 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 de 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[modifica | modifica el codi]

RIFT:[7] é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[8] (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[9] (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[10] and GLOH[11] són variants de SIFT. El descriptor PCA-SIFT és un vector de 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.[12] En contrast amb l'enfocament clàssic de SIFT Wagner et al. utilitzar el FAST detector 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.[13] 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[modifica | modifica el codi]

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[modifica | modifica el codi]

Escala espai-extrems de detecció[modifica | modifica el codi]

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 de 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,[14] 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ó[modifica | modifica el codi]

Després que els extrems de 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 el rati 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[modifica | modifica el codi]

En primer lloc, per a cada punt clau candidat, la interpolació de dades properes s'utilitza 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.[1] El nou enfocament calcula la interpolació de la ubicació de l'extrem, la qual cosa millora substancialment el joc i l'estabilitat.[5] 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ó de 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[15]

Descart de punts claus de baix contrast[modifica | modifica el codi]

Per descartar els punts clau amb baix contrast, el valor de l'expansió de Taylor de segon ordreD(\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[modifica | modifica el codi]

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 els 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 lloc 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.[5] 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ó[modifica | modifica el codi]

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 de 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[modifica | modifica el codi]

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 l’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. Donat 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 degut a 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 son 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[modifica | modifica el codi]

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 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 el augment progressiu del desenfocament. Això és degut a 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 te 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 del histograma del contenidor, i és relatiu al coeficient de correlació de Spearman.

Aplicacions[modifica | modifica el codi]

Reconeixement d'objectes utilitzant característiques SIFT[modifica | modifica el codi]

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ó, aquestos 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.[16] 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ó de 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 que 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[modifica | modifica el codi]

En aquesta aplicació,[17] un sistema estèreo trinocular s'utilitza 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[modifica | modifica el codi]

El descriptor SIFT pot ser utilitzat en la costura de 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.[18]

Modelatge escena 3D, reconeixement i seguiment[modifica | modifica el codi]

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 desde 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ó s'utilitza per reduir la fluctuació en la projecció virtual.[19]

Descriptors SIFT 3D per reconeixement d'accions humanes[modifica | modifica el codi]

Extensions del descriptor SIFT per a dimensions 2 +1 espai-temporals de dades en el context del reconeixement de l'acció humana en les seqüències de vídeo han estat estudiats en aquest apartat.[20][21][22][23] 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 espai-temporal. 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 espai-temporal o en llocs determinats a l'atzar, temps i escales. Les regions espai-temporals 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 espai-temporal. 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.[24]

Anàlisi del cervell humà amb Imatges de Ressonància Magnètica en 3D[modifica | modifica el codi]

La técnica de morfometria basada en funcions (FBM)[25] utilitza els extrems en una diferència d'escala espaial 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 espai-temporal, 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 de 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 de AD en el cervell i la classificació d'Alzheimer lleu en noves imatges amb una taxa de 80%.[25]

Vegeu també[modifica | modifica el codi]

Referències[modifica | modifica el codi]

  1. 1,0 1,1 Lowe, David G. (1999). "Object recognition from local scale-invariant features". Proceedings of the International Conference on Computer Vision 2: 1150–1157. DOI:10.1109/ICCV.1999.790410.  
  2. , US 6711293
  3. Scale-invariant feature transfrom a l'USPTO (anglès), "Method and apparatus for identifying scale invariant features in an image and use of same for locating an object in an image", David Lowe's patent for the SIFT algorithm, March 23, 2004
  4. 4,0 4,1 Lowe, D. G., “Object recognition from local scale-invariant features”, International Conference on Computer Vision, Corfu, Greece, September 1999.
  5. 5,0 5,1 5,2 Lowe, D. G., “Distinctive Image Features from Scale-Invariant Keypoints”, International Journal of Computer Vision, 60, 2, pp. 91-110, 2004.
  6. Lowe, D.G., Local feature view clustering for 3D object recognition. IEEE Conference on Computer Vision and Pattern Recognition,Kauai, Hawaii, 2001, pp. 682-688.
  7. Lazebnik, S., Schmid, C., and Ponce, J., "Semi-Local Affine Parts for Object Recognition", Proceedings of the British Machine Vision Conference, 2004.
  8. Sungho Kim, Kuk-Jin Yoon, In So Kweon, "Object Recognition Using a Generalized Robust Invariant Feature and Gestalt’s Law of Proximity and Similarity", Conference on Computer Vision and Pattern Recognition Workshop (CVPRW'06), 2006
  9. Bay, H., Tuytelaars, T., Gool, L.V., "SURF: Speeded Up Robust Features", Proceedings of the ninth European Conference on Computer Vision, May 2006.
  10. Ke, Y., and Sukthankar, R., "PCA-SIFT: A More Distinctive Representation for Local Image Descriptors", Computer Vision and Pattern Recognition, 2004.
  11. 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.
  12. D. Wagner, G. Reitmayr, A. Mulloni, T. Drummond, and D. Schmalstieg, "Pose tracking from natural features on mobile phones" Proceedings of the International Symposium on Mixed and Augmented Reality, 2008.
  13. N. Henze, T. Schinke, and S. Boll, "What is That? Object Recognition from Natural Features on a Mobile Phone" Proceedings of the Workshop on Mobile Interaction with the Real World, 2009.
  14. Lindeberg, Tony. «Feature detection with automatic scale selection». International Journal of Computer Vision, vol. 30, 2, 1998, pàg. 79–116. DOI: 10.1023/A:1008045108935.
  15. Lindeberg, Tony and Bretzner, Lars. «Real-time scale selection in hybrid multi-scale representations». Proc. Scale-Space'03, Springer Lecture Notes in Computer Science, vol. 2695, 2003, pàg. 148–163. DOI: 10.1007/3-540-44935-3_11.
  16. Beis, J.; Lowe, David G. (1997). "Shape indexing using approximate nearest-neighbour search in high-dimensional spaces". Conference on Computer Vision and Pattern Recognition, Puerto Rico: sn: 1000–1006. DOI:10.1109/CVPR.1997.609451.  
  17. Se, S.; Lowe, David G.; Little, J. (2001). "Vision-based mobile robot localization and mapping using scale-invariant features". Proceedings of the IEEE International Conference on Robotics and Automation (ICRA) 2: 2051. DOI:10.1109/ROBOT.2001.932909.  
  18. Brown, M.; Lowe, David G. (2003). "Recognising Panoramas". Proceedings of the ninth IEEE International Conference on Computer Vision 2: 1218–1225. DOI:10.1109/ICCV.2003.1238630.  
  19. Iryna Gordon and David G. Lowe, "What and where: 3D object recognition with accurate pose," in Toward Category-Level Object Recognition, (Springer-Verlag, 2006), pp. 67-82
  20. Laptev, Ivan and Lindeberg, Tony (2004). "Local descriptors for spatio-temporal recognition". ECCV'04 Workshop on Spatial Coherence for Visual Motion Analysis, Springer Lecture Notes in Computer Science, Volume 3667: 91–103. DOI:10.1007/11676959_8.  
  21. Ivan Laptev, Barbara Caputo, Christian Schuldt and Tony Lindeberg. «Local velocity-adapted motion events for spatio-temporal recognition». Computer Vision and Image Understanding, vol. 108, 3, 2007, pàg. 207–229. DOI: 10.1016/j.cviu.2006.11.023.
  22. Scovanner, Paul; Ali, S; Shah, M (2007). "A 3-dimensional sift descriptor and its application to action recognition". Proceedings of the 15th International Conference on Multimedia: 357–360. DOI:10.1145/1291233.1291311.  
  23. Flitton, G.; Breckon, T. (2010). "Object Recognition using 3D SIFT in Complex CT Volumes". Proceedings of the British Machine Vision Conference: 11.1-12. DOI:10.5244/C.24.11.  
  24. Niebles, J. C. Wang, H. and Li, Fei-Fei (2006). "Unsupervised Learning of Human Action Categories Using Spatial-Temporal Words". Proceedings of the British Machine Vision Conference (BMVC). Data de consulta {Plantilla:Accessdate].  
  25. 25,0 25,1 Matthew Toews, William M. Wells III, D. Louis Collins, Tal Arbel. «Feature-based Morphometry: Discovering Group-related Anatomical Patterns». NeuroImage, vol. 49, 3, 2010, pàg. 2318–2327. DOI: 10.1016/j.neuroimage.2009.10.032. PMID: 19853047.

Enllaços externs[modifica | modifica el codi]