カラーコードについて
BOW cARdでは、ARToolKitで使われるマーカー画像と違い、5×5のカラーコードを使っています。これについて説明します。
ARToolKitでは、ARアプリケーション製作者が用意したマーカー画像をアプリケーションが保持し、実行時に得られたスクエアのそれぞれについて、保持しているマーカーと一致しているか照らし合わせる仕組みになっています。
好きな画像をマーカーとして使える手軽さがありますが、マーカーの種類が多くなると照らし合わせの負荷が大きくなるほか、各マーカーを事前に知っておく必要があるという制約があるため、マーカーを2次元コードにすることでこれらを解決しました。
コードの設計にあたって、最初に以下のようなことを考えました。
- 色 - QRコードやバーコードと同様の白黒コードにするか、カラーコードにするか。何色を使うか。
- グリッドの分割数 - 4×4 か 5×5 か それ以上か。
- 方向識別 - 認識されたスクエアの回転をどう検出するか。
- 誤り対応 - 誤り検出 または 誤り訂正。その方法。
まず色ですが、白黒にすると検出が楽である反面、セルあたり1bitのデータしか持てません。対して4色のカラーコードを使えばセルあたり2bitを持つことができますが、カメラや照明の差による影響を受けやすくなります。
そこでグリッドの分割数を考えてみました。分割数が小さいほどセルを大きくできるので、マーカーがカメラから離れた際の精度を保つことができます。カメラからの入力画像は320×240と低解像度なので、セルは可能な限り大きくしたいところです。そこで、4色のカラーコードを使う代わりに分割数を減らすことにしました。
色をCMYKにした理由ですが、ユーザが自分のコードを印刷できるというシチュエーションを考えた場合に、家庭用プリンタでも明確にコントラストが出るようにしたかったからです。実際、他の色の組み合わせ（RGBなど）を古いプリンタで試したところ、インクが混ざった汚い感じになってしまい識別に難がありました。
次は方向の識別です。コードはセルの並びですが、どの順で並べるか分からないとコードが読み取れないため、最初に方向を取り出せる必要があります。カラーコードの中に方向識別用のセルを作ってしまうと、任意のデータを埋められるセルが減ってしまうので、外側の黒枠や白枠に工夫することも考えましたが、シンプルにするために左上のセルをシアンに固定することにしました。他の3隅のセルにシアンが出てしまうと困るので、これらにシアンが入らないよう黒とイエローのみにしています。
（マゼンタを入れても良いのですが、分かりやすくするために3隅は1bit、それ以外は2bitとしたので黒/イエローです）
最後に誤り対応です。誤り検出にしろ誤り訂正にしろ、あまり冗長ビットを増やしてしまうとセルが小さくなってしまい逆効果なので、3ビット程度の誤りしか面倒を見れません。その程度の誤りがどのぐらい発生するのか、試しに誤り対応をせずカラーコード読み取りを行ってみると、1セルの認識を失敗するケースが時折ありました。ユーザがエラーを正そうと好意的にカメラを動かしてくれる場合は良いのですが、そうでないとエラーが続けて発生してしまい、誤り訂正が必要だと判断しました。
誤り訂正符号にはいくつもの種類がありますが、高速に処理できる点でハミング符号を選んでいます。実装も容易で、非常に単純なクラスで書き表せました。コードはこちら。
これまでの要素を使ってカラーコードを作るとどのぐらいのデータが入り、どのぐらいのマーカーが作れるでしょうか。
分割数が4×4だった場合、ビット数は4×4x2=32bit。左上の2bitと残りの3隅の1bitずつは使えないので27bitを符号に使えます。これを4ブロックに分割してそれぞれに(7,4)ハミング符号を持たせると15bitの情報ビットを保持でき、32,768種類のマーカーが作れる計算になります。これだとWeb上で自由にマーカーを作らせるのをためらってしまう量ですね。
分割数が5×5だった場合、ビット数は5×5x2=50bit。符号に使えるのは45bitなので3ブロックに分割してそれぞれに(15,11)ハミング符号を持たせると33bitの情報ビットを保持できます。33bitだと扱いにくいので、現在はそのうち32bitを使っています。残りの1bitはいつか困ったときに使えそうです。これで4,294,967,296種類のマーカーが作れる計算になり、安心してWebで使えます。
というわけで、現在の5×5のカラーコードができました。
次回は読み取りの際に行っている工夫について書きたいと思います。