Mean shift

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 K {\displaystyle K} e una stima iniziale della moda x {\displaystyle x} , ad ogni iterazione viene calcolata la media pesata della stima kernel di densità

m ( x ) = ∑ x i ∈ N ( x ) K ( x i − x ) x i ∑ x i ∈ N ( x ) K ( x i − x ) {\displaystyle m(x)={\frac {\sum _{x_{i}\in N(x)}K(x_{i}-x)x_{i}}{\sum _{x_{i}\in N(x)}K(x_{i}-x)}}}

dove N ( x ) {\displaystyle N(x)} è l'insieme di campioni x i {\displaystyle x_{i}} per i quali K ( x i ) ≠ 0 {\displaystyle K(x_{i})\neq 0} . Il vettore m ( x ) − x {\displaystyle m(x)-x} è detto mean shift. Il punto x {\displaystyle x} viene aggiornato con uno spostamento verso la media, nella direzione indicata dal vettore mean shift

x ← m ( x ) {\displaystyle x\leftarrow m(x)}

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

K ( x ) = { 1 if   ‖ x ‖ ≤ λ 0 if   ‖ x ‖ > λ {\displaystyle K(x)={\begin{cases}1&{\text{if}}\ \|x\|\leq \lambda \\0&{\text{if}}\ \|x\|>\lambda \\\end{cases}}}

la gaussiana

K ( x i − x ) = e − c | | x i − x | | 2 {\displaystyle K(x_{i}-x)=e^{-c||x_{i}-x||^{2}}}

e la funzione kernel di Epanechnikov

K ( x ) = { D + 2 2 V D ( 1 − | | x | | 2 ) if   ‖ x ‖ ≤ 1 0 if   ‖ x ‖ > λ {\displaystyle K(x)={\begin{cases}{\frac {D+2}{2V_{D}}}\left(1-||x||^{2}\right)&{\text{if}}\ \|x\|\leq 1\\0&{\text{if}}\ \|x\|>\lambda \\\end{cases}}}

dove V D {\displaystyle V_{D}} denota il volume della sfera unitaria in D {\displaystyle D} 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.
  Portale Informatica
  Portale Matematica
  Portale Statistica