Mean Shift Analysis

in Japanese

Introduction

　In this page, I describe a brief explanation on the Mean Shift analysis^1,2. In the next page, I explain the practice by the OpenCV library.

Theory

　Suppose we have points $\{\vec{x}_{i}|i=1,\cdots,n\}$ in the $d$-dimensional space. We can consider a density function $f(\vec{x})$ that the distribution of them yields. The density has a large value in the area where there are a lot of points, and has a small one in the area where points sparsely exist.

Let us consider a sphere (hypersphere) centered on an arbitrary point $\vec{x}$ with a radius $h$. The centroid $\vec{x}_{\rm c}$ of the points within the sphere gives $f(\vec{x}_{\rm c}) > f(\vec{x})$.

Replacing $\vec{x}_{c}$ by $\vec{x}$ and repeating the same calculation, the initial point converges to a local maximal point of the density $f(\vec{x})$. The convergence is mathematically proved in [1][2]. The approach for detecting local maximal points on the density function $f(\vec{x})$ by repeating movement to the centroid (mean) is referred to as the Mean Shift analysis.

　The mean $\vec{m}(\vec{x})$ of points within the sphere centered on the point $\vec{x}$ is defined as \begin{equation} \vec{m}(\vec{x}) = \frac{1}{|S_{h}(\vec{x})|}\sum_{\vec{x}_i \in S_{h}(\vec{x})}\;\vec{x}_{i} \end{equation} where $S_{h}(\vec{x})$ indicates a set of points within the sphere centered on $\vec{x}$ with the radius $h$, and $|S_{h}(\vec{x})|$ is the number of points in $S_{h}(\vec{x})$. In order to generalize the discussion, we rewrite the above expression as \begin{equation} \vec{m}(\vec{x}) = \frac{\sum_{i=1}^{n}\;K(\vec{x}_i;\;\vec{x},h)\;\vec{x}_i}{\sum_{i=1}^{n}\;K(\vec{x}_i;\;\vec{x},h)} \end{equation} where the sum is taken over all points we are now considering. The function $K(\vec{x}_i;\;\vec{x},h)$ is defined as \begin{eqnarray} K(\vec{x}_i;\;\vec{x},h)=\left\{ \begin{array}{} 1\;\; {\rm if}\;\;\|\vec{x}-\vec{x}_i\|\leq h\\ 0\;\; {\rm if}\;\;\|\vec{x}-\vec{x}_i\|\gt h \end{array} \right. \label{kernel} \end{eqnarray} . Then, the density function $f(\vec{x})$ is defined by using $K(\vec{x}_i;\;\vec{x},h)$ as \begin{equation} f(\vec{x})=\frac{1}{n\;V_{d}}\;\sum_{i=1}^{n}\;K(\vec{x}_i;\;\vec{x},h) \end{equation} where $V_{d}$ denotes a volume of the $d$-dimensional hypersphere with the radius $h$. Therefore, the following expression is satisfied: \begin{equation} \int\;d\vec{x}\;f(\vec{x}) = 1. \end{equation} The function $K(\vec{x}_i;\;\vec{x},h)$ is called the kernel. The kernel can be extended to various forms other than (\ref{kernel}).

　Let us consider a spherically-symmetrical kernel as \begin{equation} K(\vec{x}_i;\;\vec{x},h) = k\left(\left\|\frac{\vec{x}-\vec{x}_i}{h} \right\|^2\right) \end{equation} where $k(x)$ is called the profile. When we write the density function constructed from the the profile as $f_{K}(\vec{x})$, the derivative of it with respect to $\vec{x}$ yields the following equation: \begin{equation} \vec{\nabla}\;f_K(\vec{x})=\frac{2}{n\;V_d\;h^2}\;\sum_{i=1}^{n}\;k^{\prime}\left(\left\|\frac{\vec{x}-\vec{x}_i}{h} \right\|^2\right)\;\left(\vec{x}-\vec{x}_i\right) \end{equation} where $k^{\prime}(x)=dk(x)/dx$. Introducing $g(x)=-k^{\prime}(x)$, we obtain \begin{equation} \vec{\nabla}\;f_K(\vec{x})=\frac{2}{h^2}f_G(\vec{x})\;\vec{s}_G(\vec{x}) \label{mean-shift-relation} \end{equation} where \begin{equation} f_G(\vec{x})=\frac{1}{n\;V_{d}}\;\sum_{i=1}^{n}\;G(\vec{x}_i;\;\vec{x},h) \end{equation} \begin{equation} \vec{s}_G(\vec{x})=\vec{m}_G(\vec{x})-\vec{x} \end{equation} \begin{equation} m_G(\vec{x}) = \frac{\sum_{i=1}^{n}\;G(\vec{x}_i;\;\vec{x},h)\;\vec{x}_i}{\sum_{i=1}^{n}\;G(\vec{x}_i;\;\vec{x},h)} \end{equation} \begin{equation} G(\vec{x}_i;\;\vec{x},h) = g\left(\left\|\frac{\vec{x}-\vec{x}_i}{h} \right\|^2\right). \end{equation} The mean shift vector $\vec{s}_G(\vec{x})$ is the vector from $\vec{x}$ to $\vec{m}_G(\vec{x})$. The eq.(\ref{mean-shift-relation}) means that the mean shift direction, which is calculated using the kernel $G$, coincides with the direction of the gradient of the density $f_K(\vec{x})$.

　If the function $k(x)$ is given as \begin{eqnarray} k(x)=\left\{ \begin{array}{} 1-x\;\; &{\rm if}&\;\;x\leq 1\\ 0\;\; &{\rm if}&\;\;x \gt 1 \end{array} \right., \label{epanechnikov} \end{eqnarray} we get the function $g(x)$ as \begin{eqnarray} g(x)=\left\{ \begin{array}{} 1\;\; &{\rm if}&\;\;x\leq 1\\ 0\;\; &{\rm if}&\;\;x \gt 1 \end{array} \right.. \label{fukunaga} \end{eqnarray} That is, the kernel $G(\vec{x}_i;\;\vec{x},h)$ constructed from the profile $g(x)$ equals to the eq.(\ref{kernel}). The kernel $K(\vec{x}_i;\;\vec{x},h)$ constructed from the eq.(\ref{epanechnikov}) is called the Epanechnikov kernel, and the kernel $G(\vec{x}_i;\;\vec{x},h)$ constructed from the eq.(\ref{fukunaga}) is called the Fukunaga kernel. The mean shift direction by the Fukunaga kernel equals to the direction of the gradient of the density defined by the Epanechnikov kernel.

References

1. Mean Shift Analysis and Applications, D. Comaniciu and P. Meer, 1999 (pdf)
2. Mean Shift: A Robust Approach Toward Feature Space Analysis, D. Comaniciu and P. Meer, 2002 (pdf)
3. コンピュータビジョン2 最先端ガイド　第2章, アドコム・メディア株式会社 (in Japanese)