おぺんcv

画像処理エンジニアのブログ

Mean-shift Trackingを実装してみた

OpenCV 画像処理

勉強のためにMean-shift Trackingを実装してみました

ソースコード

以下に公開してあります
github.com

参考

実装の際に参考にしたのはOpenCVのCamShiftのサンプルコードと
こちらのintelの論文です
http://opencv.jp/opencv-1.0.0_org/docs/papers/camshift.pdf
URLから分かるようにCamShiftのオリジナルっぽいですね

アルゴリズム

アルゴリズムを簡単に紹介します

追跡の開始

最初に追跡対象の色ヒストグラムを計算します

  1. 追跡ウィンドウの位置とサイズを設定
  2. ウィンドウ内の色ヒストグラムを計算
追跡ウィンドウの更新

枚フレーム以下の処理を行います

  1. 追跡対象の2次元確率分布を計算
  2. 追跡ウィンドウ内の確率分布の重心を求める
  3. ウィンドウの中心が重心の位置に来るようウィンドウを更新
  4. 収束するまで2、3を繰り返す

2次元確率分布は要するに「追跡対象らしさマップ」みたいなものです
最初に計算したヒストグラムを2次元に逆投影(back projection)することで求められます
2、3がMean-shiftの本処理です
確率分布のピークに向かってウインドウを移動させます
さらにウィンドウのサイズや傾きを計算する処理が加わると
CamShiftと呼ばれる手法になります

あとはこことかも参考になりました
OpenCV: Meanshift and Camshift

ソースの解説

MeanShiftTrackerクラス

start()で追跡の開始、update()で追跡ウィンドウの更新を行います
勉強用ということでメンバは公開にしました

class MeanShiftTracker
{
public:
	MeanShiftTracker();
	void start(const cv::Mat& img, const cv::Rect& window);
	int update(const cv::Mat& img, cv::Rect& window);
	int vmin_, vmax_, smin_;
	cv::Mat hist_, backProject_;
};
追跡の開始

ウィンドウ内の色ヒストグラムを計算します
純粋に色だけに着目したい(輝度や彩度の影響を無視したい)ので
RGBをHSVに変換しそのHue成分だけを使用します
また輝度や彩度が低い画素では色の表現力も弱くなるので
そのような画素もマスクによって計算から除外します

void MeanShiftTracker::start(const cv::Mat& img, const cv::Rect& window)
{
	CV_Assert(img.type() == CV_8UC3);

	// ROIの設定
	cv::Mat roi = img(window);

	// HSVに変換
	cv::Mat hsv;
	cv::cvtColor(roi, hsv, cv::COLOR_BGR2HSV);

	// マスクの作成
	cv::Mat mask;
	cv::inRange(hsv, cv::Scalar(0, smin_, vmin_), cv::Scalar(180, 256, vmax_), mask);

	// Hue成分の抽出
	cv::Mat hue(hsv.size(), hsv.depth());
	int fromTo[2] = { 0, 0 };
	cv::mixChannels({ hsv }, { hue }, fromTo, 1);

	// ヒストグラムの計算
	int histSize = 64;
	float range[] = { 0, 180 };
	calcHist(hue, mask, hist_, histSize, range);
}

ヒストグラムの計算では値がrangeの範囲内にある画素を
0≦x<1となるよう正規化し、histSizeをかけることでビンを算出しています

void calcHist(const cv::Mat& img, const cv::Mat& mask, cv::Mat& hist, int histSize, const float *range)
{
	CV_Assert(img.type() == CV_8U);
	CV_Assert(mask.type() == CV_8U);
	CV_Assert(mask.size() == img.size());

	hist.create(cv::Size(1, histSize), CV_32F);
	hist = cv::Scalar::all(0);

	float minv = range[0];
	float maxv = range[1];

	for (int i = 0; i < img.rows; ++i)
	{
		for (int j = 0; j < img.cols; ++j)
		{
			float v = img.at<uchar>(i, j);
			if (v < minv || v >= maxv)
				continue;

			float nv = (v - minv) / (maxv - minv);
			int bin = static_cast<int>(histSize * nv);
			CV_Assert(bin < histSize);
			if (mask.at<uchar>(i, j))
				hist.at<float>(bin) += 1.0f;
		}
	}
}
追跡ウィンドウの更新

全体の流れはこんな感じ
前半部分は開始処理とほとんど同じですね

int MeanShiftTracker::update(const cv::Mat& img, cv::Rect& window)
{
	// HSVに変換
	cv::Mat hsv;
	cv::cvtColor(img, hsv, cv::COLOR_BGR2HSV);

	// マスクの作成
	cv::Mat mask;
	cv::inRange(hsv, cv::Scalar(0, smin_, vmin_), cv::Scalar(180, 256, vmax_), mask);

	// Hue成分の抽出
	cv::Mat hue(hsv.size(), hsv.depth());
	int fromTo[2] = { 0, 0 };
	cv::mixChannels({ hsv }, { hue }, fromTo, 1);

	// ヒストグラムの逆投影
	float range[] = { 0, 180 };
	calcBackProject(hue, hist_, backProject_, range);

	// 逆投影画像のマスキング
	cv::bitwise_and(backProject_, mask, backProject_);

	// ウィンドウの更新
	return meanShift(backProject_, window);
}

追跡対象の2次元確率分布を求めるため、ヒストグラムの逆投影を行います
各画素に対しヒストグラムを計算した時と同じ方法でビンを計算し
ビンに対応するヒストグラムの値(度数)を逆投影画像に格納します
追跡対象に近い色を持つならば、大きな値になるはずです
見やすいように値を0～255に正規化してあります

void calcBackProject(const cv::Mat& img, const cv::Mat& hist, cv::Mat& backProject, const float *range)
{
	CV_Assert(img.type() == CV_8U);
	CV_Assert(hist.type() == CV_32F);

	backProject.create(img.size(), CV_8U);
	backProject = cv::Scalar::all(0);

	cv::Mat _hist = hist;
	cv::normalize(_hist, _hist, 0, 255, cv::NORM_MINMAX);

	int histSize = hist.rows;
	float minv = range[0];
	float maxv = range[1];

	for (int i = 0; i < img.rows; ++i)
	{
		for (int j = 0; j < img.cols; ++j)
		{
			float v = img.at<uchar>(i, j);
			if (v < minv || v >= maxv)
				continue;

			float nv = (v - minv) / (maxv - minv);
			int bin = static_cast<int>(histSize * nv);
			CV_Assert(bin < histSize);
			backProject.at<uchar>(i, j) = cv::saturate_cast<uchar>(_hist.at<float>(bin));
		}
	}
}

追跡ウィンドウ内の確率分布の重心を求めます
分布の0次モーメントを
M_{00} = \sum_{x}\sum_{y}I(x,y)
1次モーメントを
M_{10} = \sum_{x}\sum_{y}xI(x,y); \ \ M_{01} = \sum_{x}\sum_{y}yI(x,y)
とすると、重心は以下のように求まります
x_c = \frac{M_{10}}{M_{00}}; \ \ y_c = \frac{M_{01}}{M_{00}}
ウィンドウの中心が重心の位置に来るようウィンドウ位置を更新します
反復が既定回数に達するか、ウィンドウの移動量が小さくなるまで繰り返します

int meanShift(const cv::Mat& probImage, cv::Rect& window)
{
	CV_Assert(probImage.type() == CV_8U);

	int maxiter = 20;
	for (int iter = 0; iter < maxiter; ++iter)
	{
		// 重心の計算
		unsigned int mz = 0, mx = 0, my = 0;
		for (int i = 0; i < window.height; ++i)
		{
			for (int j = 0; j < window.width; ++j)
			{
				int y = i + window.y;
				int x = j + window.x;

				mz += probImage.at<uchar>(y, x);
				mx += x * probImage.at<uchar>(y, x);
				my += y * probImage.at<uchar>(y, x);
			}
		}

		if (mz == 0)
			return 0;

		int cx = mx / mz;
		int cy = my / mz;

		// ウィンドウの位置を更新
		int winx = cx - window.width/2;
		int winy = cy - window.height/2;

		winx = std::min(probImage.cols - 1 - window.width, std::max(0, winx));
		winy = std::min(probImage.rows - 1 - window.height, std::max(0, winy));

		// 移動量が小さい場合は終了
		if (abs(winx - window.x) < 1 && abs(winy - window.y) < 1)
			break;

		window.x = winx;
		window.y = winy;
	}

	return 1;
}

サンプル

入力データはこちらを利用させていただきました
David Ross - Incremental Visual Tracking

OpenCVのCamShiftのデモと同様に
マウスのドラッグで追跡対象を指定できるようになってます
キーボードの'b'を押すと逆投影画像に表示が切り替わります

MeanShiftTracker Demo
最初は追跡に成功していますが
途中でウィンドウが背景の方に外れてしまいました

おわりに

以前の記事ではOpenCVのサンプルの紹介で終わってしまったので
今回は理解のために自分で中身を実装してみました