Introduction
In this page, I describe a brief explanation on the Mean Shift analysis1,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
- Mean Shift Analysis and Applications, D. Comaniciu and P. Meer, 1999 (pdf)
- Mean Shift: A Robust Approach Toward Feature Space Analysis, D. Comaniciu and P. Meer, 2002 (pdf)
- コンピュータビジョン2 最先端ガイド 第2章, アドコム・メディア株式会社 (in Japanese)
0 件のコメント:
コメントを投稿