in Japanese

## 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 $$\vec{m}(\vec{x}) = \frac{1}{|S_{h}(\vec{x})|}\sum_{\vec{x}_i \in S_{h}(\vec{x})}\;\vec{x}_{i}$$ 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 $$\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)}$$ 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 $$f(\vec{x})=\frac{1}{n\;V_{d}}\;\sum_{i=1}^{n}\;K(\vec{x}_i;\;\vec{x},h)$$ where $V_{d}$ denotes a volume of the $d$-dimensional hypersphere with the radius $h$. Therefore, the following expression is satisfied: $$\int\;d\vec{x}\;f(\vec{x}) = 1.$$ 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 $$K(\vec{x}_i;\;\vec{x},h) = k\left(\left\|\frac{\vec{x}-\vec{x}_i}{h} \right\|^2\right)$$ 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: $$\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)$$ where $k^{\prime}(x)=dk(x)/dx$. Introducing $g(x)=-k^{\prime}(x)$, we obtain $$\vec{\nabla}\;f_K(\vec{x})=\frac{2}{h^2}f_G(\vec{x})\;\vec{s}_G(\vec{x}) \label{mean-shift-relation}$$ where $$f_G(\vec{x})=\frac{1}{n\;V_{d}}\;\sum_{i=1}^{n}\;G(\vec{x}_i;\;\vec{x},h)$$ $$\vec{s}_G(\vec{x})=\vec{m}_G(\vec{x})-\vec{x}$$ $$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)}$$ $$G(\vec{x}_i;\;\vec{x},h) = g\left(\left\|\frac{\vec{x}-\vec{x}_i}{h} \right\|^2\right).$$ 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)