Scale-invariant feature transform

Scale-invariant feature transform (o SIFT) è un algoritmo di visione computazionale che permette di rilevare e descrivere caratteristiche, o feature, locali in immagini. L'algoritmo è stato pubblicato da David Lowe nel 1999.

Applicazioni includono: object recognition, robotic mapping e navigation, image stitching, 3D modeling, gesture recognition, video tracking, e match moving.

L'algoritmo è brevettato negli Stati Uniti; il proprietario è la University of British Columbia.

Scale-invariant feature transform

Per ogni oggetto in un'immagine, punti interessanti possono essere estratti per fornire una descrizione delle caratteristiche dell'oggetto. Questa descrizione, ricavata da un'immagine selezionata per l'apprendimento, può essere poi usata per identificare l'oggetto quando si prova ad individuarlo in una immagine di test che contiene molti altri oggetti. Per un riconoscimento affidabile, è importante che le caratteristiche estratte dall'immagine di apprendimento siano rilevabili anche con cambiamenti di scala, rumore e illuminazione. Tali punti di solito sono posizionati in regioni ad alto contrasto dell'immagine, come contorni di oggetti.

Un'altra importante caratteristica di queste feature è che le loro posizioni relative nella scena originale non dovrebbero cambiare tra due immagini affini. Per esempio, se come feature vengono presi gli angoli di una porta, esse dovrebbero funzionale indipendentemente dalla posizione della porta; se però vengono presi in considerazione anche punti del contorno, il riconoscimento fallirebbe se la porta fosse chiusa o aperta. In modo simile, le feature situate in oggetti articolati o flessibili tipicamente non funzionano se avvenisse un qualsiasi cambiamento della loro geometria interna tra due immagini nell'insieme elaborato. In pratica, comunque, SIFT rileva e usa un numero molto più grande di feature dalle immagini, il che riduce il contributo degli errori causati da queste variazioni locali sull'errore medio di tutte le feature.

Il metodo di Lowe può identificare in modo robusto oggetti anche nella confusione o parzialmente nascosti, perché il descrittore di feature SIFT è invariante per scala, orientazione e distorsione affine e parzialmente invariante a cambi di illuminazione. Questa sezione riassume il metodo di object recognition di Lowe e introduce alcune tecniche alternative disponibili per il riconoscimenti di oggetti in condizioni di confusione o parziale occlusione.

Il metodo di Lowe

I keypoints (punti chiave) SIFT di oggetti vengono prima estratti da un insieme di immagini di riferimento e immagazzinati in un database. Un oggetto viene riconosciuto in una nuova immagine confrontando individualmente ogni feature della nuova immagine con il database precedentemente ottenuto e cercando feature basandosi sulla distanza euclidea dei loro vettori di feature. Dall'insieme completo di corrispondenze, nella nuova immagine vengono identificati sottoinsiemi di keypoints che concordano con l'oggetto e la sua posizione, scala, orientazione per filtrare le corrispondenze migliori. La determinazione di cluster consistenti viene effettuata in modo rapido usando un'implementazione con [hash table]] efficiente della [trasformata di Hough]] generalizzata. Ogni cluster di 3 o più feature concordanti su un oggetto e la sua posizione è soggetto ad un'ulteriore verifica dettagliata del modello e, di conseguenza, gli outliers vengono scartati. Infine viene calcolata la probabilità che un particolare insieme di features indichi la presenza di un oggetto, data l'accuratezza di fit e un numero di possibili false corrispondenze. Quelle che passano tutti questi test vengono identificate come corrette con alta confidenza.

<references>

See also

• 3D single object recognition
• autostitch
• Feature detection (computer vision)
• SURF (Speeded Up Robust Features)
• scale-space
• scale-space implementation

External links

• Rob Hess's implementation of SIFT accessed 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.