ARToolKitの解析 その② マーカーの認識
解析の２回目は、マーカーの認識についてです。
前回の変換行列の計算で、省略した部分を説明します。
---- < マーカー認識の概要 > ----
※注意
この動画で、画像の色分けでは、そのつど色が計算されるため、多くの色が点滅するような動画になっています。
また、画像の生成等の重い処理を行っているので、フレームレートは低くなっています。
光過敏性発作などがある方は、予めご注意ください。
BGM：エコテロニカ（sansuiさん）
なんだかムーンサイドみたいですね。
ちょっと誤字があるようですが、気にしないでください。
ARToolKitでは、変換行列を計算する前に、その基となるマーカーを知っていなければなりません。
カメラに映った画像から、どこにマーカーがあるのか判定するために、おおまかに以下のような処理を行います。
１．カメラからの画像を２値化して、画像の暗い部分を探す
２．暗い部分で、それぞれの閉じた領域に印を付ける
３．各閉領域で、一番端の点を最初の頂点（頂点１）とする
４．頂点１から、領域の輪郭を探す
５．輪郭が分かったら、２番目の頂点を探す
６．残りの頂点３，４を探す
７．４つの頂点をもつ領域を４角形と判断する
８．４角形内の画像を単純化する
９．単純化された画像に対して、パターンマッチングを行う
それぞれの処理を見てみます。
---- < １．カメラからの画像を２値化して、画像の暗い部分を探す > ----
カメラから得られたカラー画像を、２値化して白or黒のみの画像にします。
ARToolKitでは、黒枠のマーカーを認識するので、
ここでの画像は白黒を反転したようなものになっています。
---- < ２．暗い部分で、それぞれの閉じた領域に印を付ける > ----
画像を２値化すると、閉じた領域がたくさんできます。
それぞれの閉領域を区別するために、ラベリングと呼ばれる作業を行います。
これは、各領域を走査して、繋がっている部分に同じ番号を割り振っていく作業になります。
---- < ３．各閉領域で、一番端の点を最初の頂点（頂点１）とする > ----
２で閉領域が見つかったので、各閉領域の外接矩形を求めます。
そして、外接矩形の辺上にある点を探します。
これが、最初の頂点（頂点１）になります。
---- < ４．頂点１から、領域の輪郭を探す > ----
次に、輪郭を探します。
頂点１からスタートして、閉領域の輪郭を辿るように、点を見つけていきます。
最後に、頂点１に戻ってきます。
---- < ５．輪郭が分かったら、２番目の頂点を探す > ----
輪郭は点の集まりなので、その中で頂点１から最も離れたものを探します。
それを頂点２とします。
---- < ６．残りの頂点３，４を探す > ----
頂点１、２から頂点３，４を探します。
まず輪郭点を、"頂点１→２" と "頂点２→１" の２つに分けます。
２つの輪郭点で、頂点１・２の線分から、最も離れた点を探します。
これを再帰的に繰り返して、残りの頂点も見つけ出します。
---- < ７．４つの頂点をもつ領域を４角形と判断する > ----
上記の処理の途中で、領域が望みの４角形かどうかが、だいたい判定されます。
最初に、面積が非常に小さい、または大きい領域は除外されます。
他にも、４つの頂点がうまく見つからない領域も除外されます。
４つの頂点は、順番に並んでいるとは限らないので、
そのつど調整されます。
---- < ８．４角形内の画像を単純化する > ----
４角形が見つかったので、やっとパターンの判別に入ります。
判別のために、４角形内の画像は単純かされます。
マーカーが斜めに映っている場合も、内部の画像は修正され、真正面からのものになり、
解像度も非常に小さくなります。
---- < ９．単純化された画像に対して、パターンマッチングを行う > ----
この単純化された画像に対して、パターンマッチングを行います。
パターンマッチングでは、基となるパターンと単純化された４角形内の画像を比較し、誤差を計算します。
この誤差が、ある決まった値より小さい場合に、これが求めるマーカーであると判定されることになります。
（実際には、最も誤差が小さいパターンが、その４角形に割り当てられ、後の判断はプログラマに委ねられます。
---- < 最後に > ----
調べてみて分かりましたが、すばらしいアルゴリズムですね。
非常に勉強になりました。
やはり、所々怪しいところはありますので、間違い等はご指摘いただければありがたいです。
あまり関係ないですが、BGMを使用させてもらっているsansuiさんつながりで、「ゆめにっき」というフリーゲームを現在やっています。
RPGツクールで作られた、夢の中を探索するという戦闘のないゲームなんですが、「とても怖いゲーム」です。
まるで、マザー２のムーンサイドのような怖さで、今回作った動画もプログラムもそれっぽいと思ってしまいました。
前回の変換行列の計算で、省略した部分を説明します。
---- < マーカー認識の概要 > ----
※注意
この動画で、画像の色分けでは、そのつど色が計算されるため、多くの色が点滅するような動画になっています。
また、画像の生成等の重い処理を行っているので、フレームレートは低くなっています。
光過敏性発作などがある方は、予めご注意ください。
BGM：エコテロニカ（sansuiさん）
なんだかムーンサイドみたいですね。
ちょっと誤字があるようですが、気にしないでください。
ARToolKitでは、変換行列を計算する前に、その基となるマーカーを知っていなければなりません。
カメラに映った画像から、どこにマーカーがあるのか判定するために、おおまかに以下のような処理を行います。
１．カメラからの画像を２値化して、画像の暗い部分を探す
２．暗い部分で、それぞれの閉じた領域に印を付ける
３．各閉領域で、一番端の点を最初の頂点（頂点１）とする
４．頂点１から、領域の輪郭を探す
５．輪郭が分かったら、２番目の頂点を探す
６．残りの頂点３，４を探す
７．４つの頂点をもつ領域を４角形と判断する
８．４角形内の画像を単純化する
９．単純化された画像に対して、パターンマッチングを行う
それぞれの処理を見てみます。
---- < １．カメラからの画像を２値化して、画像の暗い部分を探す > ----
カメラから得られたカラー画像を、２値化して白or黒のみの画像にします。
ARToolKitでは、黒枠のマーカーを認識するので、
ここでの画像は白黒を反転したようなものになっています。
---- < ２．暗い部分で、それぞれの閉じた領域に印を付ける > ----
画像を２値化すると、閉じた領域がたくさんできます。
それぞれの閉領域を区別するために、ラベリングと呼ばれる作業を行います。
これは、各領域を走査して、繋がっている部分に同じ番号を割り振っていく作業になります。
---- < ３．各閉領域で、一番端の点を最初の頂点（頂点１）とする > ----
２で閉領域が見つかったので、各閉領域の外接矩形を求めます。
そして、外接矩形の辺上にある点を探します。
これが、最初の頂点（頂点１）になります。
---- < ４．頂点１から、領域の輪郭を探す > ----
次に、輪郭を探します。
頂点１からスタートして、閉領域の輪郭を辿るように、点を見つけていきます。
最後に、頂点１に戻ってきます。
---- < ５．輪郭が分かったら、２番目の頂点を探す > ----
輪郭は点の集まりなので、その中で頂点１から最も離れたものを探します。
それを頂点２とします。
---- < ６．残りの頂点３，４を探す > ----
頂点１、２から頂点３，４を探します。
まず輪郭点を、"頂点１→２" と "頂点２→１" の２つに分けます。
２つの輪郭点で、頂点１・２の線分から、最も離れた点を探します。
これを再帰的に繰り返して、残りの頂点も見つけ出します。
---- < ７．４つの頂点をもつ領域を４角形と判断する > ----
上記の処理の途中で、領域が望みの４角形かどうかが、だいたい判定されます。
最初に、面積が非常に小さい、または大きい領域は除外されます。
他にも、４つの頂点がうまく見つからない領域も除外されます。
４つの頂点は、順番に並んでいるとは限らないので、
そのつど調整されます。
---- < ８．４角形内の画像を単純化する > ----
４角形が見つかったので、やっとパターンの判別に入ります。
判別のために、４角形内の画像は単純かされます。
マーカーが斜めに映っている場合も、内部の画像は修正され、真正面からのものになり、
解像度も非常に小さくなります。
---- < ９．単純化された画像に対して、パターンマッチングを行う > ----
この単純化された画像に対して、パターンマッチングを行います。
パターンマッチングでは、基となるパターンと単純化された４角形内の画像を比較し、誤差を計算します。
この誤差が、ある決まった値より小さい場合に、これが求めるマーカーであると判定されることになります。
（実際には、最も誤差が小さいパターンが、その４角形に割り当てられ、後の判断はプログラマに委ねられます。
---- < 最後に > ----
調べてみて分かりましたが、すばらしいアルゴリズムですね。
非常に勉強になりました。
やはり、所々怪しいところはありますので、間違い等はご指摘いただければありがたいです。
あまり関係ないですが、BGMを使用させてもらっているsansuiさんつながりで、「ゆめにっき」というフリーゲームを現在やっています。
RPGツクールで作られた、夢の中を探索するという戦闘のないゲームなんですが、「とても怖いゲーム」です。
まるで、マザー２のムーンサイドのような怖さで、今回作った動画もプログラムもそれっぽいと思ってしまいました。
