Mean Shiftの理論

in English

はじめに

　Mean Shiftの理論をまとめます。次回、OpenCVによる実践をまとめます。

理論

　$d$ 次元空間内に観測点 $\{\vec{x}_{i}|i=1,\cdots,n\}$ が与えられたとき、観測点の分布が作り出す密度分布関数 $f(\vec{x})$ を考えることができる。点が集中している場所では $f(\vec{x})$ の値は大きく、点がまばらな場所では小さい値を取る。

いま任意の観測点 $\vec{x}$ を中心とする半径 $h$ の球（超球）を考える。球内に存在する観測点の重心 $\vec{x}_{\rm c}$ は、$\vec{x}$ よりも密度の高い場所に存在する。

$\vec{x}_{c}$ を $\vec{x}$ に置き換え同じ計算を繰り返せば、最初に指定した観測点は $f(\vec{x})$ の極大値へ向かって収束していくことが分る。 この振る舞いは文献^1,2において厳密に証明されている。このように重心（平均値）への移動を繰り返すことにより、密度分布関数の極大値を検出する手法をMean Shiftと呼ぶ。

　点 $\vec{x}$ を中心とする球内の重心 $\vec{m}(\vec{x})$ は、次式で定義される。 $$\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}$$ ここで、$S_{h}(\vec{x})$ は点 $\vec{x}$ を中心とする半径 $h$ の球内に存在する観測点の集合を表す。$|S_{h}(\vec{x})|$ は要素の数である。議論を一般化するため、上式を以下のように書き直す。 $$\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}$$ ここで、和は全ての観測点についてとることに注意する。$K(\vec{x}_i;\;\vec{x},h)$ は次式で定義される量である。 $$\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}$$ このとき、密度分布関数 $f(\vec{x})$ は次式で定義される。 $$\begin{equation} f(\vec{x})=\frac{1}{n\;V_{d}}\;\sum_{i=1}^{n}\;K(\vec{x}_i;\;\vec{x},h) \end{equation}$$ ここで、$V_{d}$ は半径 $h$ の $d$ 次元球の体積である。したがって次式が成り立つ。 $$\begin{equation} \int\;d\vec{x}\;f(\vec{x}) = 1 \end{equation}$$ $K(\vec{x}_i;\;\vec{x},h)$ はカーネルと呼ばれる関数である。カーネルは式($\ref{kernel}$)以外の関数に拡張することができる。

　いま球対称なカーネル関数を考える。 $$\begin{equation} K(\vec{x}_i;\;\vec{x},h) = k\left(\left\|\frac{\vec{x}-\vec{x}_i}{h} \right\|^2\right) \end{equation}$$ $k(x)$ をプロファイルと呼ぶ。このカーネルで定義される密度分布関数を $f_{K}(\vec{x})$ と書くことにすれば $$\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}$$ を得る。ここで、$k^{\prime}(x)=dk(x)/dx$とした。$g(x)=-k^{\prime}(x)$を導入すると $$\begin{equation} \vec{\nabla}\;f_K(\vec{x})=\frac{2}{h^2}f_G(\vec{x})\;\vec{s}_G(\vec{x}) \end{equation}$$ を得る。 ここで、 $$\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}$$ である。 $\vec{s}_G(\vec{x})$ は、任意の点 $\vec{x}$ から重心 $\vec{m}_G(\vec{x})$ へ向かうベクトルである。すなわち、注目している密度分布関数 $f_K(\vec{x})$ の勾配は、カーネル $G$ を用いて計算される重心移動の方向に一致する。

　さて、関数 $k(x)$ が次式で与えれるとき $$\begin{eqnarray} k(x)=\left\{ \begin{array}{} 1-x\;\; &{\rm if}&\;\;x\leq 1\\ 0\;\; &{\rm if}&\;\;x \gt 1 \end{array} \right. \end{eqnarray}$$ $g(x)$ は以下のようになる。 $$\begin{eqnarray} g(x)=\left\{ \begin{array}{} 1\;\; &{\rm if}&\;\;x\leq 1\\ 0\;\; &{\rm if}&\;\;x \gt 1 \end{array} \right. \end{eqnarray}$$ すなわち、$g$ から構成されるカーネル $G(\vec{x}_i;\;\vec{x},h)$ は式($\ref{kernel}$)に等しい。 ここで定義されたカーネル $K(\vec{x}_i;\;\vec{x},h)$ をEpanechnikovカーネル、$G(\vec{x}_i;\;\vec{x},h)$ を福永カーネルと呼ぶ。福永カーネルによる重心移動の方向は、Epanechnikovカーネルにより定義される密度分布関数の勾配方向と一致する。

参考文献

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章, アドコム・メディア株式会社