Object recognition: differenze tra le versioni

Versione delle 06:28, 1 apr 2012

Versione delle 16:44, 4 giu 2012

Riga 3:

L''''Object recognition''' nella [[computer vision]] è la capacità di trovare un determinato oggetto in una sequenza di immagini o video. L'uomo riconosce una moltitudine di oggetti in immagini con poco sforzo, nonostante il fatto che l'immagine degli oggetti possa variare un po' in diversi punti di vista, in diversi formati/scala o rotazione. Inoltre gli oggetti possono essere riconosciuti anche quando sono parzialmente esclusi dalla vista. Questo compito è ancora una sfida per la [[computer vision]] in generale. [[David Lowe (computer scientist)|David Lowe]] ha sperimentato la [[computer vision]] per l'estrazione e l'utilizzo della scala invariante [[Scale-invariant feature transform|SIFT]] in modo da rendere il riconoscimento più affidabile.

Per ogni oggetto in un'immagine, ci sono molte 'features', che sono caratteristiche interessanti dell'oggetto, le quali possono essere estratte in modo da fornire una descrizione "caratteristica" dell'oggetto. Questa descrizione estratta da una immagine campione può poi essere utilizzata per identificare l'oggetto durante il tentativo di individuare l'oggetto in una immagine di test contenente più oggetti. È importante che l'insieme di caratteristiche estratte dall'immagine campione sia insensibile a variazioni di scala delle immagini, i disturbi, l'illuminazione e distorsioni geometriche, in modo da rendere affidabile il riconoscimento. Il metodo brevettato di Lowe <ref>{{US patent|6,711,293}}, "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</ref> può riconoscere gli oggetti in maniera affidabile, anche tra il disordine e con occlusione parziale perché il metodo [[Scale-invariant feature transform|SIFT]] è indipendente dalla scala, orientamento, distorsione e parzialmente dai cambiamenti d'illuminazione <ref name="lowe">Lowe, D. G., “Object recognition from local scale-invariant features”, International Conference on Computer Vision, Corfu, Greece, September 1999.</ref>. Questo articolo presenta il metodo di Lowe e cita alcuni concorrenti tecniche disponibili per l'object recognition in presenza di disordine e occlusione parziale.

== Metodo di David Lowe ==

Riga 40:

== Fasi principali ==

=== Funzione di rilevamento a scala invariante ===

Il metodo Lowe per la generazione di un'immagine caratteristica chiamata '''Scale Invariant Feature Transform''' ([[Scale-invariant feature transform|SIFT]]) trasforma l'immagine in una grande collezione di caratteristiche vettoriali, ognuna delle quali è invariante rispetto a traslazione, ridimensionamento, rotazione e, in parte rispetto all'illuminazione. Tale metodo è robusto rispetto a distorsioni geometriche. Queste caratteristiche hanno proprietà simili ai neuroni del [[lobo occipitale]], i quali vengono utilizzati per il riconoscimento di oggetti nei sistema di visione dei primati<ref>Serre, T., Kouh, M., Cadieu, C., Knoblich, U., Kreiman, G., Poggio, T., “A Theory of Object Recognition: Computations and Circuits in the Feedforward Path of the Ventral Stream in Primate Visual Cortex”, Computer Science and Artificial Intelligence Laboratory Technical Report, December 19, 2005 MIT-CSAIL-TR-2005-082.</ref>.Le posizioni dei punti chiave sono definite come massimi e minimi del risultato della [[differenza delle Gaussiane (vedi [[:en:Difference of Gaussians|Difference of Gaussiansgaussiane]]), di una serie di immagini ottenute col sistema [[:en:Scale-space|spazio-scala]]. Vengono scartati i punti a basso contrasto e i punti di bordo che si trovano lungo un bordo. Maggiore credibilità viene assegnata ai punti chiave localizzati. Queste fasi garantiscono che i punti chiave siano più stabili durante il riconoscimento.

La solidità del metodo [[Scale-invariant feature transform|SIFT]] rispetto alla distorsione è quindi ottenuta considerando i pixel nell'intorno del punto chiave e sfocando e ricampionando l'immagine locale.

=== Ricerca e indicizzazione ===

L'indicizzazione è il problema di immagazzinare i punti chiave [[Scale-invariant feature transform|SIFT]] e di individuarli in una nuova immagine. Lowe ha usato una modifica dell'algoritmo [[k-d tree]] chiamato metodo del '''Best-bin-first search''' <ref>Beis, J., and Lowe, D.G “Shape indexing using approximate nearest-neighbour search in high-dimensional spaces”, Conference on Computer Vision and Pattern Recognition,Puerto Rico, 1997, pp. 1000–1006.</ref> che può individuare il [[nearest neighbor]]s con elevata probabilità utilizzando solo limitate risorse di elaborazione. L'algoritmo BBF utilizza un ordinamento di ricerca modificato per il [[k-d tree]] in modo che i bins nella proprietà spazio siano ricercati in funzione della loro minima distanza dalla posizione richiesta. Questo ordine di ricerca richiede l'uso di una [[heap]] basata sulla [[coda di priorità]] per l'efficiente determinazione dell'ordine di ricerca. L'appaiamento al miglior candidato per ogni keypoint viene trovato identificando il suoi vicini più prossimi [[nearest neighbor]] nel database dei keypoints proveniente dalle immagini di addestramento. I [[nearest neighbor]] sono definiti come i the keypoints con la minima [[Euclidean distance]] da un dato vettore descrittivo. La probabilità che un appaiamento sia corretto può essere determinata tramite il rapporto delle distanze con i due vicini più prossimi.

Lowe<ref name="lowe04" /> rigetta tutti gli accoppiamenti in cui il rapporto di distanza è superiore a 0.8, il che elimina 90% dei falsi accoppiamenti pur compromettendo meno del 5% degli appaiamenti corretti. Per migliorare ulteriormente l'efficienza dell'algoritmo di ricerca best-bin-first viene effettuato un cutoff dopo i primi 200 candidati [[nearest neighbor]]. Per un database di 100,000 keypoints, tutto ciò porta ad una velocizzazione sulla ricerca del corretto [[nearest neighbor]] di circa due ordini di grandezza compromettendo meno del 5% sul numero dei corretti accoppiamenti.

Riga 55 ⟶ 54:

[[Hough Transform]] is used to cluster reliable model hypotheses to search for keys that agree upon a particular model [[pose]]. [[Hough transform]] identifies clusters of features with a consistent interpretation by using each feature to vote for all object [[pose]]s that are consistent with the feature. When clusters of features are found to vote for the same pose of an object, the probability of the interpretation being correct is much higher than for any single feature. An entry in a [[hash table]] is created predicting the model ___location, orientation, and scale from the match hypothesis.The [[hash table]] is searched to identify all clusters of at least 3 entries in a bin, and the bins are sorted into decreasing order of size.

Each of the [[Scale-invariant feature transform|SIFT]] keypoints specifies 2D ___location, scale, and orientation, and each matched keypoint in the database has a record of the keypoint’skeypoint's parameters relative to the training image in which it was found. The similarity transform implied by these 4 parameters is only an approximation to the full 6 degree-of-freedom pose space for a 3D object and also does not account for any non-rigid deformations. Therefore, Lowe<ref name="lowe04" /> used broad bin sizes of 30 degrees for orientation, a factor of 2 for scale, and 0.25 times the maximum projected training image dimension (using the predicted scale) for ___location. The [[Scale-invariant feature transform|SIFT]] key samples generated at the larger scale are given twice the weight of those at the smaller scale. This means that the larger scale is in effect able to filter the most likely neighbours for checking at the smaller scale. This also improves recognition performance by giving more weight to the least-noisy scale. To avoid the problem of boundary effects in bin assignment, each keypoint match votes for the 2 closest bins in each dimension, giving a total of 16 entries for each hypothesis and further broadening the pose range.

=== Model verification by linear least squares ===

Each identified cluster is then subject to a verification procedure in which a [[linear least squares]] solution is performed for the parameters of the [[affine transformation]] relating the model to the image. The [[affine transformation]] of a model point [x y]^T to an image point [u v]^T can be written as below

:<math>

\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}

</math>

where the model translation is [tx ty]^T and the affine rotation, scale, and stretch are represented by the parameters m1, m2, m3 and m4. To solve for the transformation parameters the equation above can be rewritten to gather the unknowns into a column vector.

Riga 85 ⟶ 82:

The solution of the system of linear equations is given in terms of the matrix <math>(A^TA)^{-1}A^T</math> , called the [[Moore-Penrose pseudoinverse|pseudoinverse]] of ''A'', by

:<math> \hat{\mathbf{x}} = (A^T\!A)^{-1} A^T \mathbf{b}. </math>

which minimizes the sum of the squares of the distances from the projected model locations to the corresponding image locations.

=== Outlier detection ===

Riga 104 ⟶ 100:

"[[SURF]]<ref>Bay, H., Tuytelaars, T., Gool, L.V., "SURF: Speeded Up Robust Features", Proceedings of the ninth European Conference on Computer Vision, May 2006.</ref> : Speeded Up Robust Features" is a high-performance scale and rotation-invariant interest point detector / descriptor claimed to approximate or even outperform previously proposed schemes with respect to repeatability, distinctiveness, and robustness. [[SURF]] relies on integral images for image convolutions to reduce computation time, builds on the strengths of the leading existing detectors and descriptors (using a fast [[Hessian matrix]]-based measure for the detector and a distribution-based descriptor). It describes a distribution of [[Haar wavelet]] responses within the interest point neighbourhood. Integral images are used for speed and only 64 dimensions are used reducing the time for feature computation and matching. The indexing step is based on the sign of the [[Laplacian]],which increases the matching speed and the robustness of the descriptor.

PCA-SIFT <ref>Ke, Y., and Sukthankar, R., PCA-SIFT: A More Distinctive Representation for Local Image DescriptorsComputer Vision and Pattern Recognition, 2004.</ref> and [[GLOH]] <ref>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.</ref> are variants of [[Scale-invariant feature transform|SIFT]]. PCA-SIFT descriptor is a vector of image gradients in x and y direction computed within the support region. The gradient region is sampled at 39x39 locations, therefore the vector is of dimension 3042. The dimension is reduced

to 36 with [[Analisi delle componenti principali|PCA]]. Gradient ___location-orientation histogram ([[GLOH]]) is an extension of the [[Scale-invariant feature transform|SIFT]] descriptor designed to increase its robustness and distinctiveness. The [[Scale-invariant feature transform|SIFT]] descriptor is computed for a log-polar ___location grid with three bins in radial direction (the radius set to 6, 11, and 15) and 8 in angular direction, which results in 17 ___location bins. The central bin is not divided in angular directions. The gradient orientations are quantized in 16 bins resulting in 272 bin histogram. The size of this descriptor is reduced with PCA. The [[covariance matrix]] for PCA is estimated on image patches collected from various images. The 128 largest [[eigenvector]]s are used for description.

Riga 118 ⟶ 114:

== Collegamenti esterni ==

* [http://citeseer.ist.psu.edu/lowe04distinctive.html Lowe, D. G., “Distinctive Image Features from Scale-Invariant Keypoints”, International Journal of Computer Vision, 60, 2, pp. 91-110, 2004.]

* [http://www.cs.ubc.ca/spider/lowe/pubs.html David Lowe's Publications]

* [http://www.cs.ubc.ca/~lowe/keypoints/ David Lowe's Demo Software : SIFT keypoint detector]

* [http://www.vision.ee.ethz.ch/~surf/index.html SURF: Speeded up robust features ]

Riga 125 ⟶ 121:

* [http://www-cvr.ai.uiuc.edu/ponce_grp/publication/paper/bmvc04.pdf Lazebnik, S., Schmid, C., and Ponce, J., Semi-Local Affine Parts for Object Recognition, BMVC, 2004. ]

* [http://user.cs.tu-berlin.de/~nowozin/libsift/ libsift: Scale Invariant Feature Transform implementation]

== Voci correlate ==