Mean shift

Da Wikipedia, l'enciclopedia libera.
Jump to navigation Jump to search

Mean shift è un metodo non parametrico per la ricerca delle mode di una funzione di densità di probabilità.[1] Introdotto nel 1975 da Fukunanga e Hostetler,[2] è equivalente all'applicazione della discesa del gradiente alla stima kernel di densità della distribuzione.[3] L'algoritmo non richiede assunzioni sulla forma dei cluster e ha un singolo parametro, l'ampiezza di banda, la cui determinazione è tuttavia non banale in generale. Mean shift ha applicazioni in analisi dei cluster, elaborazione digitale delle immagini e visione artificiale.[4]

Descrizione[modifica | modifica wikitesto]

Mean shift è un algoritmo iterativo per determinare i massimi locali di una funzione di densità di probabilità a partire da un dataset di campioni.[1] Data una funzione kernel , ad ogni iterazione viene calcolata per ogni punto la media pesata della stima kernel di densità

dove è l'insieme di campioni per i quali . Il vettore è detto mean shift. Ogni punto viene aggiornato con uno spostamento verso la media, nella direzione indicata dal vettore mean shift

e il procedimento viene iterato fino a convergenza.

La funzione kernel è solitamente una funzione radiale di base. Alcune funzioni comuni sono la palla

la gaussiana

e la funzione kernel di Epanechnikov

dove denota il volume della sfera unitaria in dimensioni.[5]

Nonostante il diffuso utilizzo dell'algoritmo, non è nota una dimostrazione di convergenza nel caso generale.[5] È dimostrata la convergenza nel caso unidimensionale, se la funzione kernel è differenziabile, convessa e strettamente decrescente,[6] e nel caso multidimensionale se la funzione di densità ha un numero finito di punti stazionari isolati.[5][7]

Applicazioni[modifica | modifica wikitesto]

Mean shift è usato come algoritmo di clustering, assegnando ogni punto del dataset alla moda della distribuzione di densità più vicina lungo la direzione determinata dal gradiente.[2] L'algoritmo ha applicazioni nel tracking, e l'idea di base è quella di costruire per un frame una mappa di confidenza basata sull'istogramma dell'oggetto tracciato nel frame precedente, e applicare mean shift per determinare il massimo della distribuzione di confidenza nella regione prossima alla posizione precedente dell'oggetto.[8][9][10][11] Un numero limitato di iterazioni di mean shift può essere usato come metodo di riduzione del rumore.[2]

Note[modifica | modifica wikitesto]

  1. ^ a b Yizong Cheng, Mean Shift, Mode Seeking, and Clustering, in IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 17, nº 8, August 1995, pp. 790–799, DOI:10.1109/34.400568.
  2. ^ a b c Keinosuke Fukunaga e Larry D. Hostetler, The Estimation of the Gradient of a Density Function, with Applications in Pattern Recognition, in IEEE Transactions on Information Theory, vol. 21, nº 1, January 1975, pp. 32–40, DOI:10.1109/TIT.1975.1055330.
  3. ^ Richard Szeliski, Computer Vision, Algorithms and Applications, Springer, 2011
  4. ^ Dorin Comaniciu e Peter Meer, Mean Shift: A Robust Approach Toward Feature Space Analysis, in IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 24, nº 5, May 2002, pp. 603–619, DOI:10.1109/34.1000236.
  5. ^ a b c Youness Aliyari Ghassabeh, A sufficient condition for the convergence of the mean shift algorithm with Gaussian kernel, in Journal of Multivariate Analysis, vol. 135, 1º marzo 2015, pp. 1–10, DOI:10.1016/j.jmva.2014.11.009.
  6. ^ Youness Aliyari Ghassabeh, On the convergence of the mean shift algorithm in the one-dimensional space, in Pattern Recognition Letters, vol. 34, nº 12, 1º settembre 2013, pp. 1423–1427, DOI:10.1016/j.patrec.2013.05.004, arXiv:1407.2961.
  7. ^ Xiangru Li, Zhanyi Hu e Fuchao Wu, A note on the convergence of the mean shift, in Pattern Recognition, vol. 40, nº 6, 1º giugno 2007, pp. 1756–1762, DOI:10.1016/j.patcog.2006.10.016.
  8. ^ Dorin Comaniciu, Visvanathan Ramesh e Peter Meer, Kernel-based Object Tracking, in IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 25, nº 5, May 2003, pp. 564–575, DOI:10.1109/tpami.2003.1195991.
  9. ^ Shai Avidan, Ensemble Tracking, in 2005 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR'05), vol. 2, San Diego, California, IEEE, 2005, pp. 494–501, DOI:10.1109/CVPR.2005.144, ISBN 978-0-7695-2372-9.
  10. ^ Gary Bradski (1998) Computer Vision Face Tracking For Use in a Perceptual User Interface Archiviato il 17 aprile 2012 in Internet Archive., Intel Technology Journal, No. Q2.
  11. ^ Ebrahim Emami, Online failure detection and correction for CAMShift tracking algorithm, in 2013 Iranian Conference on Machine Vision and Image Processing (MVIP), vol. 2, IEEE, 2013, pp. 180–183, DOI:10.1109/IranianMVIP.2013.6779974, ISBN 978-1-4673-6184-2.