2013年5月31日金曜日

C++メモ

下記のコードにおいて、fun(int)fun(const int)は同じsignatureとみなされエラーになる。 値渡しの引数に対してはconstをつけないのがC++の作法である。 しかし、この引数に対し実装部ではconstを付けることができる。 これにより、この引数がread-onlyであることを意味的に強制することができる。 参照
const参照されたオブジェクトからconstをはずすキャストの振る舞いは未定義である。 参照
  1. デフォルトではunique_ptrを採用する。必要に応じてshared_ptrにmove-convertする。
  2. make_shared/make_uniqueはexception-safeである。通常はこれらを使う。
  3. 以下2つの場合、make_shared/make_uniqueを使うことができない。
    1. ユーザ定義のdeleterを使用する場合
    2. legacy codeからraw pointerを受け取った場合
  4. auto_ptrはdeprecatedである。
参照

2013年5月25日土曜日

C++メモ

C++11におけるconstmutableの意味。
physical const logical const
writable mutable
readable(thread-safe) const const
const は、read-only か safe to read concurrently を意味する。physical const かもしれないし、logical const かもしれない。一方、mutable は writable but logically const を意味する。

参照サイト

2013年5月21日火曜日

Mean Shift Filtering 〜Practice by OpenCV〜

in Japanese

Introduction

 In the previous page, I provided a brief explanation of the Mean Shift analysis. In this page, I describe the Mean Shift filtering proposed by D. Comaniciu and P. Meer in [1][2]. I also show the practice of the filtering by the OpenCV library.

Theory

 Suppose we have an $RGB$ image that consists of $n$ pixels each of which has three values $(r,g,b)$. Since the image is regarded as the distribution of the points in the 3-dimensional space, we can define a density function as shown in the previous discussion. We can detect local maximal points of the density by the Mean Shift analysis as illustrated below. In the figure, the blue circles indicate local maximal points.
Any point $\vec{x}$ in the 3-dimensional ($RGB$) space converges toward a local maximal point adjacent to $\vec{x}$. If we replace all points in the image by the corresponding local maximal points, we can accomplish the smoothing of the image. In the above figure, the green line shows the smoothing image.

 It should be noticed that an image has not only color information but also location one. Since the smoothing procedure explained above ignores location information, two distantly-positioned objects that happen to have similar color can be labeled by the same color. When we would like to assign the different labels to them, we cannot employ the procedure. D. Comaniciu and P. Meer expanded the vector $(r,g,b)$ that represents each pixel to the 5-dimensional vector $(x,y,r,g,b)$ which includes location information $(x,y)$1,2. In this case, the kernel used in the Mean Shift analysis is modified as \begin{equation} K(\vec{x}_i;\;\vec{x},h)=K_{\rm spatial}(\vec{x}_i^{\;s};\;\vec{x}^{\;s},h_s)\;K_{\rm range}(\vec{x}_i^{\;r};\;\vec{x}^{\;r},h_r) \end{equation} where $\vec{x}=(\vec{x}^{\;s},\vec{x}^{\;r})$, $\vec{x}^{\;s}=(x,y)$, $\vec{x}^{\;r}=(r,g,b)$, $h_s$ is the radius of the sphere in the spatial space , and $h_r$ is the the radius of the sphere in the color space. Using the kernel, the mean is calculated by the following expression: \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} Only when calculating the kernel, $\vec{x}^{\;s}$ and $\vec{x}^{\;r}$ are distinguished. Other calculation is the same as the previous page. Applying the Mean Shift analysis to all points $\{\vec{x}_{i}|i=1,\cdots,n\}$ in the image, we obtain a set of convergence points $\{\vec{z}_{i}|i=1,\cdots,n\}$. By replacing $\vec{x}_i^{\;r}$ (the color component of the original point) by $\vec{z}_i^{\;r}$ (the color component of the convergence point), we generate a new point $\vec{y}_i=(\vec{x}_i^{\;s},\vec{z}_i^{\;r})$. The image constructed from the set $\{\vec{y}_{i}|i=1,\cdots,n\}$ is the final result.

Practice by OpenCV

We can use cv::pyrMeanShiftFiltering. The sample code is as follows: The function cv::pyrMeanShiftFiltering is called in the 14th line. The first argument is an input image, and the second is an output image. The third and fourth arguments are $h_{s}$ and $h_{r}$, respectively. The sixth argument is the termination criteria for the algorithm. If we use pyramid images in the internal calculation, we have to set the level number of them to the fifth argument. Because this time we apply the Mean Shift analysis to the source image only once, we set it to 0. The resultant images are as follows:
Source Image:
$(h_s,h_r)=(16,32)$:
$(h_s,h_r)=(16,64)$:
The size of the input image is (256,256) pixels. We set params.max_iteration_count_=30 and params.epsilon_=0.01. Maybe cv::pyrMeanShiftFiltering employs the Fukunaga 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)

2013年5月19日日曜日

Mean Shift Analysis

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 \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)

2013年5月13日月曜日

Mean Shift Filteringの理論と実践

in English

はじめに

 前回、Mean Shift の理論をまとめました。今回は、D. Comaniciu と P. Meer により提案された Mean Shift Filtering についてまとめます。

理論

 $n$ 個の画素から構成される $RGB$ 画像を考える。各画素は $(r,g,b)$ を持つ。3次元空間内の点の分布を考えれば、前回と同様に密度分布関数を定義することができる。点が疎らに存在する領域の密度は低く、点が密に存在する領域の密度は高い。いま、Mean Shiftを用いて密度分布関数の極大値を検出していくと図のようになるであろう(青丸で極大値を表した)。
$RGB$ 空間内の任意の3次元ベクトル $\vec{x}$ は、図に見るように、その近傍にある極大値に向かって収束していく。画像内の全ベクトル(全画素)を、それらが収束する極大値の色に置き換えれば、色の平滑化を行うことができる(平滑化後の密度分布関数を緑の線で示した)。

 画像は色だけでなく位置の情報も含む。上記の方法は位置を無視しているので、離れた場所にあるオブジェクト $A$ と $B$ が、たまたま類似色であったため、同じ色(同じラベル)に収束してしまうことがある。オブジェクト $A$ と $B$ に異なるラベルを割り振りたい場合、これでは都合が悪い。そこで、D. Comaniciu と P. Meer は、各画素を表現するベクトルを $(r,g,b)$ ではなく位置情報を含む5次元ベクトル $(x,y,r,g,b)$ に拡張することを考えた1,2。このとき、Mean Shiftで使用するカーネルは以下のように変更される。 \begin{equation} K(\vec{x}_i;\;\vec{x},h)=K_{\rm spatial}(\vec{x}_i^{\;s};\;\vec{x}^{\;s},h_s)\;K_{\rm range}(\vec{x}_i^{\;r};\;\vec{x}^{\;r},h_r) \end{equation} ここで、$\vec{x}=(\vec{x}^{\;s},\vec{x}^{\;r})$、$\vec{x}^{\;s}=(x,y)$、$\vec{x}^{\;r}=(r,g,b)$、$h_s$ は位置空間内の球の半径、$h_r$ は色空間内の球の半径である。このカーネルを使い、次式で重心を計算する。 \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} $\vec{x}^{\;s}$ と $\vec{x}^{\;r}$ の区別がなされるのはカーネル計算時のみである。あとの計算はこれまでと同じである。Mean Shiftの手順を画像内の全ての点 $\{\vec{x}_{i}|i=1,\cdots,n\}$ に適用すると、収束点の集合 $\{\vec{z}_{i}|i=1,\cdots,n\}$ を得る。元の点の色成分 $\vec{x}_i^{\;r}$ を、収束点の色成分 $\vec{z}_i^{\;r}$ に置き換えることにより、新たな点 $\vec{y}_i=(\vec{x}_i^{\;s},\vec{z}_i^{\;r})$ を作る。集合 $\{\vec{y}_{i}|i=1,\cdots,n\}$ から構成される画像が求める結果である。

OpenCVによる実践

cv::pyrMeanShiftFilteringを使えば良い。実装例は以下の通り。 14行目でcv::pyrMeanShiftFilteringを呼び出している。第1引数が入力画像、第2引数が出力画像である。第3引数と第4引数はそれぞれ、$h_{s}$と$h_{r}$に相当する。第6引数はアルゴリズムの停止条件である。ピラミッド画像を利用する場合は第5引数にその階層数を指定する。今回は現画像に一度だけ適用したいので0とした。結果は以下の通りである。
元画像:
$(h_s,h_r)=(16,32)$:
$(h_s,h_r)=(16,64)$:
両者ともparams.max_iteration_count_=30, params.epsilon_=0.01とした。ソースを見ていないのでcv::pyrMeanShiftFilteringの内部で使われているカーネルの具体的な形は分りません。たぶん福永カーネルかな?

参考文献

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

2013年5月11日土曜日

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

2013年5月4日土曜日

C++ メモ

main関数

以下のmain関数は、C++標準で「portableである」と認められている書き方である。開発環境依存ではない。 return 0はなくても良い。

std::move

2つのコンテナ間の要素のコピーはこう書くことができる。 もし、コピーのあと、コピー元のコンテナが用済みになるならばこう書くことができる。

std::future::wait

std::futureのテンプレート引数がvoidのとき、getwaitは等価である。

スレッドへの引数渡し

  1. by value:Safe, but make sure a deep copy is made
  2. by move:Safe, as long as strict(deep) adherence to move semantics
  3. by const reference:Safe, as long as object is guaranteed deep-immutable
  4. by non-const reference:Safe, as long as the object is a monitor

std::condition_variable

以下は等価である。

参考文献

  1. The C++ Standard Library, Second Edition, Addison-Wesley, 2012.
  2. C++11 Concurrency, Bartosz Milewski