Mean-Shift

Mean Shift és un potent i versàtil algorisme no paramètric iteratiu que es pot utilitzar per a molts propòsits com trobar modes, clustering, etc. Mean Shift va ser introduït per Fukunaga i Hostetler el 1975, però no va ser usat àmpliament fins a l'auge tecnològic. Actualment, s'ha estès en aplicació en altres camps com la visió per computador.

Idea intuïtiva

Mean Shift considera un espai de característiques com una funció de densitat de probabilitat. Si l'entrada és un conjunt de punts, Mean Shift els considera com una mostra de la funció de densitat de probabilitat corresponent. Si hi ha les regions denses (o conglomerats), llavors, aquestes es corresponen amb un mode (o màxim local) de la funció de densitat de probabilitat. També podem identificar clústers associats a un màxim donat utilitzant Mean Shift. Per a cada punt de dades, l'algorisme fa desplaçar la finestra fins al pic més proper de la PDF del conjunt de dades. Per a cada punt de dades, el canvi de medi defineix una finestra al voltant d'ella i calcula la mitjana del punt de dades. Després es desplaça el centre de la finestra per a la mitjana i es repeteix l'algorisme fins que convergeix. Després de cada iteració, es pot considerar que la finestra es desplaça a una regió més densa del conjunt de dades. A alt nivell, podem especificar Mean Shift de la següent manera:

1. Fixar una finestra al voltant de cada punt de dades.
2. Càlcul de la mitjana de les dades dins de la finestra.
3. Posar la finestra a la mitjana i repetir fins a la convergència.

Elements

Kernel

Es pot dir que el kernel és una mesura que diu com s'assemblen dos punts d'informació.

És una funció que satisfà els següents requeriments:

• $\int _{Rd}\phi (x)=1$

• $\phi (x)\geq 0$

• Simètrica.

Tipus de kernels

• Rectangular : $f(x)={\begin{cases}1&a\leq x<b\\\ 0&eqac\\\end{cases}}$

• Gaussià: $\phi (x)=e^{\frac {-x^{2}}{2\sigma ^{2}}}$

• Epanechnikov :$f(x)={\begin{cases}{\frac {3}{4}}(1-x^{2})&|{x}|\leq 1\\\ 0&eqac\\\end{cases}}$

 

Densitat d'estimació

La densitat d'estimació del kernel és una manera no paramètrica d'estimar la funció de densitat d'una variable aleatòria. Normalment anomenat com la tècnica de la finestra Parzen. Donat un kernel k, i el paràmetre d'amplada de banda h, i el nombre de punts del vector n, la densitat d'estimació del kernel per un conjunt de d-dimensional és:

${\hat {f}}(x)={\frac {1}{nh^{d}}}\sum _{i=1}^{n}{\frac {(x-x_{i})}{h}}$

Amplada de banda o mida de finestra

L'amplada de banda "h", controla el seu radi d'influència:

• "h" massa petita: Hi ha sobreajust. Es trobaran molts màxims.
• "h" massa gran: Suavitza els detalls de la data. Es pot arribar a només obtenir un mode o màxim on n'hi havia més.

Per tant, s'haurà d'escollir l'amplada de banda segons aquest conveni.

L'element Gradient

Com s'ha dit anteriorment, el Mean Shift, tracta els punts de l'espai de característiques com una Funció de densitat de probabilitat. Regions denses en un espai de característiques corresponen a màxims o modes locals. Així que per a cada punt de dades, realitzem l'ascens del gradient en la funció de densitat estimada fins a la convergència. Els punts estacionaris obtinguts a través de gradient d'ascens representen els modes o màxims de la funció de densitat. Tots els punts associats amb el mateix punt estacionari pertanyen al mateix grup.

Avaluació

Punts Forts

• Eina independent d'aplicacions.
• Adequat per a l'anàlisi de dades reals.
• No assumeix qualsevol forma prèvia (per exemple, el·líptica) en agrupacions de dades.
• Pot manipular espais característics múltiples: unidimensionals, multidimensionals.
• h (mida de la finestra) té un significat físic, a diferència de K -means.

Punts dèbils

• La mida de la finestra (selecció d'amplada de banda) no és trivial.
• Una mida de la finestra inadequada pot causar maneres diferents alhora de fusionar-se. S'ha d'adaptar la mida de la finestra.

Arguments mínims d'entrada per al MeanShift

• Una funció de distància per mesurar distàncies entre píxels. En general, la distància euclidiana, però també pot ser utilitzada qualsevol altra funció de distància com ara la distància Manhattan.
• Un radi. Tots els píxels dins d'aquest radi (mesurat per la distància per sobre) es comptabilitzaran per al càlcul.
• Diferència de valor. De tots els píxels dins de radi r, s'han de prendre només aquells els valors es troben dins d'aquesta diferència per al càlcul de la mitjana.

Aplicacions

Mean Shift és un algorisme versàtil que ha trobat una gran quantitat d'aplicacions pràctiques, com ara:

Clustering

L'aplicació més important és l'agrupament o clustering. El fet que Mean Shift no faci suposicions sobre el nombre de grups o la forma de l'agrupació el fa ideal per la manipulació de grups de forma i nombre arbitrari .

Fases de l'algoritme

• Es parteix del vector de característiques de l'espai provinent de la imatge.

• Iteracions Mean Shift: Es calcula la Mitjana de les mostres dins de cada finestra,

• Les finestres són desplaçades cap a on estan calculades les mitjanes.

• Se segueix iterant fins a la convergència. Les finestres es col·loquen als màxims de cada regió.

• La informació és agrupada segons on estan col·locades les finestres.

Seguiment d'objectes

El Seguiment_d'objectes està basat en una combinació del Mean shift i l'histograma de color de la mateixa imatge. CAMshift i EnsembleShift són alguns exemples de seguiment d'objectes.

Segmentació

La Segmentació és una tècnica d'homogeneïtzació local que és molt útil per a l'amortiment d'ombrejat o diferències de tonalitat en els objectes localitzats .

Implementacions

Nom	Llenguatge	Open Source	Descripció
[1] Arxivat 2014-12-05 a Wayback Machine.	C++	Si	Implementació amb aprenentatge Supervisat.
[2]	C++, C#	Si	Implementació per seguiment d'objectes.
[3]	C++	Si	Implementació per seguiment d'objectes.
[4] Arxivat 2015-02-12 a Wayback Machine.	Matlab	Si	Implementació per Segmentació.
[5]	-	Si	OpenCv
[6]	Varis	Si	Llibreries a Google Code.

Vegeu també

• SIFT
• SURF
• Clusterització de dades
• Reconeixement d'objectes
• Classificació
• Seguiment d'objectes
• K-means

Referències

• Cheng, Yizong (1995). Mean Shift, Mode Seeking, and Clustering. IEEE Transactions on Pattern Analysis and Machine Intelligence, 17, 790-799.

• Donoho, D.L. and Liu, R.C. (1991). Geometrizing rates of convergence, II. The Annals of Statistics, 633-667.

• Comaniciu, Dorin; Peter Meer (2002). Mean Shift: A Robust Approach Toward Feature Space Analysis. IEEE Transactions on Pattern Analysis and Machine Intelligence, 24, 603-619.

• Fukunaga, Keinosuke; Larry D. Hostetler (1975). The Estimation of the Gradient of a Density Function, with Applications in Pattern Recognition. IEEE Transactions on Information Theory, 21, 32-40.

• Klemel{ä}, J. (2005). Adaptive estimation of the mode of a multivariate density. Journal of Nonparametric Statistics, 17, 83-105.

• Lepski, O.V. (1992). On problems of adaptive estimation in white Gaussian noise. Topics in nonparametric estimation, 12, 87-106.

Enllaços externs

• Video Master Class UCF (anglès)
• Auto exemples (anglès)
• K-means vs Mean Shift Clustering (anglès)
• Demo Mean Shif Clustering(anglès)