Mean shift

Questo articolo affronterà l'importanza di Mean shift nella società odierna. Mean shift ha acquisito rilevanza in diversi ambiti, dalla moda alla tecnologia, passando per la cultura e la politica. La sua influenza si è diffusa in modo significativo negli ultimi anni, generando un profondo impatto sul modo in cui le persone interagiscono e si relazionano tra loro. Ecco perché è essenziale analizzare in modo approfondito il ruolo svolto attualmente da Mean shift e le sue possibili implicazioni a breve e lungo termine. A tal fine verranno esaminate diverse prospettive e casi di studio per comprendere meglio l’importanza e la portata di Mean shift nella società contemporanea.

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

Mean shift è un algoritmo iterativo per determinare il massimo locale di una funzione di densità di probabilità a partire da un dataset di campioni.[1] Data una funzione kernel e una stima iniziale della moda , ad ogni iterazione viene calcolata la media pesata della stima kernel di densità

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

e il procedimento viene iterato fino a convergenza, quando lo shift diventa irrilevante.

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

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

  1. ^ a b Yizong Cheng, Mean Shift, Mode Seeking, and Clustering, in IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 17, n. 8, agosto 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, gennaio 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, maggio 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, maggio 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.