プロ生ちゃん Hidden Object ゲームを作ろう…の途中

プロ生ちゃん Advent Calendar 2014 – Qiita
http://qiita.com/advent-calendar/2014/pronama-chan

の8日目の記事です。Xamarin+F# とダブってしまったので、ゲーム自体ができていません…という訳ではなくて、マスコットアプリ文化祭 2014 もかねて作る予定だったのですが、なんかあれこれと体調が悪くて、できあがりそうにないので、構想と途中経過だけでもつらつらと。

マスコットアプリ文化祭 2014 (Mascot Character Apps Contest)
http://pronama.github.io/mascot-apps-contest/2014/

Hidden Object Game とは？

Online Hidden Object Games | Big Fish
http://www.bigfishgames.com/online-games/genres/15/hidden-object.html

単純に絵に隠されたモノを探すゲームです。ブラウザでもPCネイティブでもあるのですが、リアルっぽい絵の中に、リアルっぽいコインやら壺やら剣やらが隠されているので、探して見つけ出します。リストにある（英語なんだけど）名前のものを探してクリックする単純なゲームなんですが、なぜかブラウザゲームの１ジャンルを占めています。たぶん、探すとそれなりに時間がかかるので暇つぶしにいいのと、ゲームのお試し時間（１時間など）に挟み込んで、お試し時間を食いつぶすのにちょうどいいんですよね。このゲーム方式。
Hidden Object Game を解くアルゴリズム…を考えるのも面白そうなのですが、今回は、Hidden Object を作るほうのアルゴリズムを考えてみます。

たぶん、公開されているゲームは、背景の絵に人の手でちまちまと隠れそうな場所を選んでおいていると思うのですが、それを自動化します…自動化して何かいいことがあるのか？汎用性はあるのか？ってのもあるけど、まあ自動化する方法を考えてみましょう。その経緯で得られるものは多いですからね。

隠れるとはどういうことか？

最初に「隠れる」とはどういうことかを考えておきましょう。Hidden Object では、モノを隠すときに単純に絵に重ねています。半透明になって判別しづらい状態になっています。ちょうど背景の形に沿っていたり、背景の色に揃っていたりします。絵本などのローリーを探せのような探しものは、（人の意志で）あらかじ絵に埋め込まれていますが、Hidden Object の場合は、あらかじめ背景があるところに（人の意志で）見つけにくくなるように重ね合わせをします。
同時に、完全に重ね合わせて隠れてしまってはいけません。きちんと、見つかるように微妙な違いは残しておく必要があります。そうしないと、見つからないかくれんぼになってしまうので、いつになっても終わりになりません。

これが、無造作に渋谷の街並みにプロ生ちゃんを半透明に隠した状態です。半透明にしているだけだから、隠れているといえば隠れているし、無造作に置いているだけなので、隠れていないといえば隠れていません。すぐ見つけられます。

特徴量をみてみよう

この「隠れる」という定義を考えなおしてみましょう。（いきなしですが）コンピュータビジョン的なところでいえば、物がわかる（物体を認識する）という方法、主に「特徴量」というものを使います。モノの写真の角とか辺とかをかき集めて、モノの特徴を拾い出すんですね。コンピューターの目で「特徴量」を拾い出してモノを認識するのであれば、逆に「特徴量」がわからないようにすれば、コンピューターの目にとって、うまく隠れることができるのではないか？ってのが、特徴量を使う発想の元です。既に、手段が目的に代わってしまっていますが（苦笑）、なんか思いついたので試してみたかったのです。

これが背景となる渋谷の画像の特徴量です。いっぱいマルがついていますが、このマルのあるところが、写真の中の特徴的な部分というわけです。約２万点あります。コンピューターの目は（すでに人間の目ではない）、この特徴点を頼りにして、そこに何があるかを調べます。物体の特徴点と比較するわけです。

これが、プロ生ちゃんを置いたときの特徴量の表示です。背景となる部分は変わらなくて…ってことはなくて、FAST で計算したからなのかランダムが入って毎回ちょっと変わるんですよね。うーむ、それはさておき、先の背景だけの特徴量の抽出と、プロ生ちゃんを入れたときの特徴量の抽出を比較して、

• あまり差がなければ、うまく隠れている。
• 特徴量の差が大きければ、（コンピュータの目で）見つけやすい

という仮定ができます。

比較をしてみると、

ほら、プロ生ちゃんを置いたときと、置かないときに特徴量の差が、が、が、というストーリーだったのですが、これだと分かりづらいですね。つーか、わかりません…

前後の特徴点の比較は、プロ生ちゃんを置いた場所がわかっているので、その近傍（この場合は、100×100）だけ調べます。透過している背景部分はかわらないはずで、重なっているところの特徴点が違っている状態になる、と予想する訳です。で、その変わっている点が少ない方がうまく隠れている状態で、逆に特徴点がたくさん変わっていると見つかりやすい（隠れていない）と考えることができます。

隠す候補は、回転も含めて 100 点ぐらい用意しておいて、それぞれの特徴量の変化を計算して比較すればよいのです。特徴点のずれ自体は、相関関数を使って計算すればよいでしょう…ってところまでは考えたんですけどね、ちょっとまだ作成中です。

OpenCvSharp を使う

でもって、特徴量を計算したり WPFのImageを扱ったりするのに OpenCV を使っていますが、C# から使える opencvsharp という便利なライブラリがあります。NuGet で取得できるので手軽にプロジェクトに組み込めて便利です。

OpenCV | OpenCV
http://opencv.org/
shimat/opencvsharp
https://github.com/shimat/opencvsharp
NuGet Gallery | OpenCvSharp 2.4.10.20141111
https://www.nuget.org/packages/OpenCvSharp-AnyCPU/

ちなみに、先の特徴量の計算は以下な感じです。OpenCV の中身を弄らないのであれば、CV.Mat でそのまま受け渡しができるので、便利でしょう。実際、カメラキャプチャして画像処理をしているのですが、640×480 程度であれば CVEx.WriteableBitmapConverter.ToWriteableBitmap は 30fps 程度で動きます。

CV.Mat FeatureMatching(
	CV.Mat img1,
	string featureDetectorName,
	string descriptorExtractorName,
	string descriptorMatcherName)
{
	// 特徴点抽出
	var detector = new CV.FastFeatureDetector();
	var keypoint1 = detector.Detect(img1);
	var output = new CV.Mat();
	CV.Cv2.DrawKeypoints( img1, keypoint1, output );

	return output;
}

/// <summary>
/// プロ生ちゃん込みで特徴量を算出
/// </summary>
/// <param name="sender"></param>
/// <param name="e"></param>
private void OnClickProNama(object sender, RoutedEventArgs e)
{
	string featureDetectorName = "FAST";
	string descriptorExtractorName = "BRIEF";
	string descriptorMatcherName = "BruteForce";

	// プロ生込みで bitmap に保存
	var path = @"d:temppnpronama.png";
	SaveCanvas(this.cv, path);
	CV.Mat mat1 = new CV.Mat(path);
	var mat = FeatureMatching(mat1, featureDetectorName, descriptorExtractorName, descriptorMatcherName);
	this.img1.Source = CVEx.WriteableBitmapConverter.ToWriteableBitmap(mat);

	this.imgPN.Visibility = System.Windows.Visibility.Hidden;
	this.imgPN2.Visibility = System.Windows.Visibility.Hidden;

}

そんな訳で、非常に中途半端なのですが、ネタ的には（自分的に）面白いので引き続きやります。普通、特徴量の計算は特徴点の抽出は「目立つ」ところを見つけて、物体を検知するのですが、このパターンは逆に「隠れる」ために、特徴量が変わらないようにする、ってのがミソです。まあ、文中にもあるように、あくまで「コンピューターの目」から逃れる手段なので、「人間の目」から逃れられるかどうか疑問だし、たぶん隠れないだろうなーという予想はしているのですが。