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

${\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 ${\displaystyle N(x)}$ è l'insieme di campioni ${\displaystyle x_{i}}$ per i quali ${\displaystyle K(x_{i})\neq 0}$. Il vettore ${\displaystyle m(x)-x}$ è detto mean shift. Il punto ${\displaystyle x}$ viene aggiornato con uno spostamento verso la media, nella direzione indicata dal vettore mean shift

${\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

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

la gaussiana

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

e la funzione kernel di Epanechnikov

${\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 ${\displaystyle V_{D}}$ denota il volume della sfera unitaria in ${\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. 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. 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. 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.