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 modifica

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

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

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)={\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}}

e la funzione kernel di Epanechnikov

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}$ denota il volume della sfera unitaria in $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 modifica

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

^ ^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.
^ ^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.
^ Richard Szeliski, Computer Vision, Algorithms and Applications, Springer, 2011
^ 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.
^ ^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.
^ 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.
^ 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.
^ 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.
^ 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.
^ 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.
^ 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

[PAMI95-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.

[Fukunaga-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.

[note3-3] Richard Szeliski, Computer Vision, Algorithms and Applications, Springer, 2011

[PAMI02-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.

[:0-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.

[note1-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.

[note2-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.

[PAMI03-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.

[avidan2001-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.

[note4-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.

[Emami2001-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.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]