(57)【要約】【課題】入力画像中のマーカ認識において以下の（イ）〜（ハ）の問題を解決する。  （イ）既存のトポロジー情報によるマーカ認識手法において同一トポロジー構造だが別図像のマーカ間の区別ができない  （ロ）既存のトポロジー情報によるマーカ認識手法において６自由度の姿勢推定ができない  （ハ）ＧＥＯＭＥＴＲＩＣ  ＨＡＳＨＩＮＧ法において、試行すべき基底の数が多いとメモリ使用量や計算量が増大する【解決手段】  既存のトポロジーによる方法では出来なかった同一トポロジー構造だが別図像のマーカ間の区別と、３次元空間内での姿勢推定を、トポロジー情報とマーカ各領域の重心を使用しＧＥＯＭＥＴＲＩＣ  ＨＡＳＨＩＮＧ法を適用して可能にする。また、ＧＥＯＭＥＴＲＩＣ  ＨＡＳＨＩＮＧ法の際にトポロジー情報を併用し基底を選択することで、メモリ使用量や計算量を減少させる。【選択図】図４
2011170829.tif 000002
【特許請求の範囲】
【請求項１】
コンピュータへの入力画像からのマーカ認識方法のうち、入力画像中からマーカ認識をおこなう際に、入力画像から得られるマーカ各領域間の包括関係および隣接関係をあらわすトポロジー情報を利用する認識方法において、トポロジー情報とあわせて、図像の各領域の重心を使用してＧｅｏｍｅｔｒｉｃ  Ｈａｓｈｉｎｇ法に基づく投票を行うことにより、同一トポロジー構造を持つ別図像間の識別を可能にするとともに、６自由度の姿勢推定を可能にする方法。
【請求項２】
請求項１において、Ｇｅｏｍｅｔｒｉｃ  Ｈａｓｈｉｎｇ法を適用する際に試行すべき座標変換のために使用するありうる基底の候補が多いとメモリ使用量や計算量が大幅に増加するが、基底の取得に必要なテンプレート側でのあらかじめ決定しておくべき複数の点を選定する際に、トポロジー情報をあわせて考慮することにより、試行すべき基底の数を減らしメモリ使用量や計算量を減少させる方法。
【請求項３】
Ｇｅｏｍｅｔｒｉｃ  Ｈａｓｈｉｎｇ法を適用する際に試行すべき座標変換のために使用するありうる基底の候補が多いとメモリ使用量や計算量が大幅に増加するが、基底の取得に必要なテンプレート側でのあらかじめ決定しておくべき複数の点を選定する際に、トポロジー情報をあわせて考慮することにより、試行すべき基底の数を減らしメモリ使用量や計算量を減少させる方法。
【発明の詳細な説明】
【技術分野】
【０００１】  本発明は、コンピュータ画像認識によるマーカ画像の認識に関する。
【背景技術】
【０００２】コンピュータを利用する入力画像からのマーカ認識において、白黒に二値化した領域のトポロジー的な隣接情報・領域間の包括関係の情報を利用してマーカ認識を行う方法がある（非特許文献１、非特許文献２、非特許文献３）。【０００３】  これらの方法は二値化された画像のトポロジカルな隣接情報・包括関係を木構造として表現し、その木構造の判別によってマーカの特定をするものである。トポロジカルな情報を使用するので、マーカのデザインがトポロジカルな隣接情報・包括関係を保つ限り、マーカの検出が可能である。【０００４】  またｌｅｆｔ  ｈｅａｖｙ  ｄｅｐｔｈ  ｓｅｑｕｅｎｃｅを使用した木構造のソート方法は、このトポロジーにもとづくマーカ認識方法の一部において使用されており、既に広く知られているものである。（非特許文献４、非特許文献３）【０００５】  さらに画像内から得られた点と、登録済みパターンの点を基底によって不変特徴に変換し、複数のテンプレートとのマッチングをハッシュ・テーブル上で行うＧｅｏｍｅｔｒｉｃ  Ｈａｓｈｉｎｇ法もよく知られている。（非特許文献５）
【先行技術文献】
【０００６】
【非特許文献１】  Ｃｏｓｔａｎｚａ，Ｅ．ａｎｄ  Ｈｕａｎｇ，Ｊ．２００９．Ｄｅｓｉｇｎａｂｌｅ  ｖｉｓｕａｌ  ｍａｒｋｅｒｓ．Ｉｎ  Ｐｒｏｃｅｅｄｉｎｇｓ  ｏｆ  ｔｈｅ  ２７ｔｈ  ｉｎｔｅｒｎａｔｉｏｎａｌ  Ｃｏｎｆｅｒｅｎｃｅ  ｏｎ  Ｈｕｍａｎ  Ｆａｃｔｏｒｓ  ｉｎ  Ｃｏｍｐｕｔｉｎｇ  Ｓｙｓｔｅｍｓ（Ｂｏｓｔｏｎ，ＭＡ，ＵＳＡ，Ａｐｒｉｌ  ０４−０９，２００９）．ＣＨＩ’０９．ＡＣＭ，Ｎｅｗ  Ｙｏｒｋ，ＮＹ，１８７９−１８８８．ＤＯＩ＝ｈｔｔｐ：／／ｄｏｉ．ａｃｍ．ｏｒｇ／１０．１１４５／１５１８７０１．１５１８９９０
【０００７】
【非特許文献２】  Ｃｏｓｔａｎｚａ，Ｅ．ａｎｄ  Ｍｉｒｊａ，Ｌ．Ｔｅｌｌｉｎｇ  ａ  ｓｔｏｒｙ  ｏｎ  ａ  ｔａｇ：Ｔｈｅ  ｉｍｐｏｒｔａｎｃｅ  ｏｆ  ｍａｒｋｅｒｓ’ｖｉｓｕａｌ  ｄｅｓｉｇｎ  ｆｏｒ  ｒｅａｌ  ｗｏｒｌｄ  ａｐｐｌｉｃａｔｉｏｎｓ（ｐａｐｅｒ  ｐｒｅｓｅｎｔａｔｉｏｎ）．Ｉｎ  Ｐｒｏｃｅｅｄｉｎｇｓ  ｏｆ  ｔｈｅ  Ｍｏｂｉｌｅ  Ｉｎｔｅｒａｃｔｉｏｎ  ｗｉｔｈ  ｔｈｅ  Ｒｅａｌ  Ｗｏｒｌｄ  Ｗｏｒｋｓｈｏｐ  ａｔ  Ｍｏｂｉｌｅ  ＨＣＩ２００６，Ｅｓｐｏｏ，Ｆｉｎｌａｎｄ，ｓｅｐ  ２００６．
【０００８】
【非特許文献３】  Ｂｅｎｃｉｎａ，Ｒ．，Ｋａｌｔｅｎｂｒｕｎｎｅｒ，Ｍ．，ａｎｄ  Ｊｏｒｄａ，Ｓ．２００５．Ｉｍｐｒｏｖｅｄ  Ｔｏｐｏｌｏｇｉｃａｌ  Ｆｉｄｕｃｉａｌ  Ｔｒａｃｋｉｎｇ  ｉｎ  ｔｈｅ  ｒｅａｃＴＩＶｉｓｉｏｎ  Ｓｙｓｔｅｍ．Ｉｎ  Ｐｒｏｃｅｅｄｉｎｇｓ  ｏｆ  ｔｈｅ  ２００５  ＩＥＥＥ  Ｃｏｍｐｕｔｅｒ  Ｓｏｃｉｅｔｙ  Ｃｏｎｆｅｒｅｎｃｅ  ｏｎ  Ｃｏｍｐｕｔｅｒ  Ｖｉｓｉｏｎ  ａｎｄ  Ｐａｔｔｅｒｎ  Ｒｅｃｏｇｎｉｔｉｏｎ（Ｃｖｐｒ’０５）−Ｗｏｒｋｓｈｏｐｓ−Ｖｏｌｕｍｅ  ０３（Ｊｕｎｅ２０−２６，２００５）．ＣＶＰＲ．ＩＥＥＥ  Ｃｏｍｐｕｔｅｒ  Ｓｏｃｉｅｔｙ，Ｗａｓｈｉｎｇｔｏｎ，ＤＣ，９９．ＤＯＩ＝ｈｔｔｐ：／／ｄｘ．ｄｏｉ．ｏｒｇ／１０．１１０９／ＣＶＰＲ．２００５．４７５
【０００９】
【非特許文献４】Ｓ．Ｎａｋａｎｏ  ａｎｄ  Ｔ．Ｕｎｏ，“Ｅｆｆｉｃｉｅｎｔ  ｇｅｎｅｒａｔｉｏｎ  ｏｆ  ｒｏｏｔｅｄ  ｔｒｅｅｓ，”Ｎａｔｉｏｎａｌ  Ｉｎｓｔｉｔｕｔｅ  ｆｏｒ  Ｉｎｆｏｒｍａｔｉｃｓ（Ｊａｐａｎ），Ｔｅｃｈ．Ｒｅｐ．ＮＩＩ−２００３−００５Ｅ，２００３．
【００１０】
【非特許文献５】Ｗｏｌｆｓｏｎ，Ｈ．Ｊ．＆  Ｒｉｇｏｕｔｓｏｓ，Ｉ（１９９７）．“Ｇｅｏｍｅｔｒｉｃ  Ｈａｓｈｉｎｇ：Ａｎ  Ｏｖｅｒｖｉｅｗ”，ＩＥＥＥ  Ｃｏｍｐｕｔａｔｉｏｎａｌ  Ｓｃｉｅｎｃｅ  ａｎｄ  Ｅｎｇｉｎｅｅｒｉｎｇ．４（４），１０−２１
【発明の開示】
【発明が解決しようとする課題】
【００１１】  二値化されたマーカ図像内の白黒領域のトポロジカルな隣接情報・包括関係を木構造として解釈し、その木構造の判別によってマーカの特定をする既存のトポロジー情報のみに基づくマーカ認識方法では、トポロジー情報を使用するため、ある図像を持つ入力画像中でのマーカ領域が傾いていたり回転していたりしても、同じトポロジー的な隣接情報・包括関係を保つ限りにおいて同一マーカとして判別が可能であり、人間の目にみても意味のある図像をマーカとして使用できるが、その反面、マーカの図像・形状が全く違っている二つの別のマーカ図像でもトポロジー情報が全く同じであれば、図像的・形状的には全く違うマーカでも同じマーカとして認識されてしまう。【００１２】  しかし、おなじトポロジー構造をもつマーカ図像は、容易に複数作成されうる。このためトポロジー情報のみに基づく方法ではマーカ間の区別が十分でないことが多い。このようにマーカ認識の一意性が十分でないという問題が、既存のトポロジー情報のみを用いた方法に存在する。【００１３】  また、上記のような既存のトポロジー情報のみを用いるマーカ認識方法においては、トポロジー情報のみを使用するため、マーカ形状やマーカ図像が他の方法にくらべて比較的自由にデザインできるというメリットがあるものの、画像からのマーカ領域の推定やマーカの２次元平面および３次元空間内での向きや位置の推定に必要な座標の情報が、形状を考慮しない性質をもつトポロジー情報には含まれないため、トポロジー情報のみでは６自由度（３次元空間内の位置とＸＹＺ各軸での回転角度）の姿勢推定が行えないという欠点がある。【００１４】  また、Ｇｅｏｍｅｔｒｉｃ  Ｈａｓｈｉｎｇ法では、ハッシュ・テーブル上に登録された基底とテンプレートのペア（もしくはテンプレート）にたいして投票を行うが、そのためには座標変換を行う必要がある。このとき、座標変換に必要な基底の取得に関連する点の数が多くなると、調べるべき基底の候補が増え、メモリ使用量や計算量が大幅に増加する。【００１５】    また、Ｇｅｏｍｅｔｒｉｃ  Ｈａｓｈｉｎｇ法では、ハッシュ・テーブルに投票に使用する点の候補が増えると、実際とは違うテンプレートにも投票が有効になる確率が増え、検出の精度が低下する場合がある。
【課題を解決するための手段】
【００１６】    本発明は、以上のような課題を解決するため、以下の手段を採用する。【００１７】    本発明で言うトポロジー情報とは、二値化された画像を用いる既存のトポロジカルなマーカ内各領域の隣接関係のみに基づくマーカ認識方法と同様、マーカ内各領域の形状や大きさにかかわらず、単に隣接関係と各領域の色（二値化後の黒及び白）のみをあらわす情報および、そのような情報から派生して得られる関連情報をさす。【００１８】    このようなトポロジー情報は、領域間の包括関係の木構造としてあらわすことができ、マーカ図像をこのような木構造で表したとき、その木構造と一致するものを、入力画像を同様にトポロジー情報として表した情報から検索することにより、入力画像からマーカらしき領域の検出を行う。【００１９】  本発明では、トポロジー情報のみによるマーカ認識方法に加えて、Ｇｅｏｍｅｔｒｉｃ  Ｈａｓｈｉｎｇ法を併用して適用する。【００２０】  本発明では、同一トポロジー構造をもつ別図像のマーカ間の識別を、Ｇｅｏｍｅｔｒｉｃ  Ｈａｓｈｉｎｇを適用した投票によって行う。【００２１】  Ｇｅｏｍｅｔｒｉｃ  Ｈａｓｈｉｎｇ法では、入力画像中の投票に使用する各点を、一般には複数以上ある、可能な基底によって座標変換し、ハッシュ・テーブルに登録して有る、（複数登録されていても良い）マーカのテンプレートと基底のペア（もしくは基底の試行をひとつずつあとで行う場合はマーカのテンプレート）にたいして投票し、投票の成否の結果を利用して、もっとも結果の良いものを正しい基底と検出マーカの組み合わせとして判定する。【００２２】上のようにＧｅｏｍｅｔｒｉｃ  Ｈａｓｈｉｎｇ法を適用する際は、ありうる有効な基底を複数利用して座標変換を行い、投票をおこなうことが必要であるが、ありうる基底の数があまりに多いと、メモリ使用量や計算量の増大が問題となる。【００２３】  本発明では、あらかじめテンプレート側から得る、座標変換に少なくとも４点必要な基底の取得に使用する点に関して、トポロジー情報をこの点の選択の際に使用して、基底の選択のさいに考慮することにより、可能な基底の候補数を減らし、メモリ使用量や計算量を減らす。【００２４】  本発明では、Ｇｅｏｍｅｔｒｉｃ  Ｈａｓｈｉｎｇ法で投票を行うハッシュ・テーブルを、同一のトポロジー構造ごと、あるいは、同一のトポロジー構造と可能な基底やテンプレートの組み合わせごとに用意することにより、あらかじめトポロジー的に該当しないマーカ候補をふるい落とし、投票の精度を上げる。【００２５】  本発明では、Ｇｅｏｍｅｔｒｉｃ  Ｈａｓｈｉｎｇ法で投票を行うさいに、テンプレートと投票されるハッシュ・テーブル上のエントリの間で、トポロジー情報を考慮してトポロジー的に一致する可能性がない投票であれば無効な投票としてあつかい、投票の精度をあげる。【００２６】  本発明では、Ｇｅｏｍｅｔｒｉｃ  Ｈａｓｈｉｎｇ法で投票を行ったのち、マーカが確定されるが、このとき得られた基底が正しいと考えられるので、その基底の取得に使用したマーカのテンプレート上の点と入力画像の点の対応が６自由度の姿勢推定に必要な分はとれていることになる。これを使用して６自由度の姿勢推定を行う。
【発明の効果】
【００２７】  本発明によれば、トポロジー情報と幾何的な情報を用いるＧｅｏｍｅｔｒｉｃ  Ｈａｓｈｉｎｇ法の併用により、既存のトポロジー情報のみを利用するマーカ認識方法の欠点である、別図像でも同一のトポロジー的な構造を持っていると区別ができず、マーカの認識時の一意性が少ないという問題を解決できる。【００２８】  同時に、既存のトポロジー情報のみを利用するマーカ認識方法の欠点である入力画像からの６自由度の姿勢推定を行うことができる。【００２９】  本発明によれば、Ｇｅｏｍｅｔｒｉｃ  Ｈａｓｈｉｎｇ法を適用する際に問題となるメモリ使用量や計算量の問題を、Ｇｅｏｍｅｔｒｉｃ  Ｈａｓｈｉｎｇ法適用時に座標変換のための基底の絞り込みのさい、トポロジー情報を考慮することにより、メモリ使用量や計算量を大幅に減らすことができる。【００３０】  本発明によれば、Ｇｅｏｍｅｔｒｉｃ  Ｈａｓｈｉｎｇ法による投票時にもトポロジー情報を考慮することにより、投票の精度を上げることができる。
【図面の簡単な説明】
【００３１】
【図１】本発明に関する手法の基本的な利用形態を表す図である。
【図２】本発明に関する手法の基本的な利用形態での処理の基本的な流れを表すフローチャートである。
【図３】本発明に関する手法の基本的な利用形態における、Ｇｅｏｍｅｔｒｉｃ  Ｈａｓｈｉｎｇ法を適用する際に、３次元空間内で様々な角度や距離で撮影された入力画像を、ハッシュ・テーブルへの投票のまえに行われる座標変換の説明を「発明を実施するための形態」の項目で行うために用意された、座標変換の様子を視覚的にわかりやすくした図である。
【図４】本発明でのトポロジー情報とＧｅｏｍｅｔｒｉｃ  Ｈａｓｈｉｎｇ法を併用したマーカ認識を行うために、あらかじめマーカ図像からトポロジー情報を抽出し、トポロジー情報をあらわす木構造をて、またその木構造のうち、リーフ・ノードとなる領域の重心座標をハッシュ・テーブル上のエントリに登録する際の様子をあらわす概念図である。
【図５】トポロジー情報を木構造であらわし、またｌｅｆｔ  ｈｅａｖｙ  ｄｅｐｔｈ  ｓｅｑｕｅｎｃｅにしたがってソートした状態をあらわす図で有る。また、図１０および図１１で図示されたマーカ図像例のトポロジー構造を表したものである。
【図６】図５において示された木構造において、ルートから符号（７）のグループによって表されているリーフ・ノードにたどり着くために通過する道順を、通過する各ノードをルートとする部分木として順に抜きだして並べることにより表現した図である。
【図７】図５において示された木構造において、ルートから符号（９）のグループによって表されているリーフ・ノードにたどり着くために通過する道順を、通過する各ノードをルートとする部分木として順に抜きだして並べることにより表現した図である。
【図８】図５において示された木構造において、ルートから符号（１１）のグループによってとして表されているリーフ・ノードにたどり着くために通過する道順を、通過する各ノードをルートとする部分木として順に抜きだして並べることにより表現した図である。
【図９】図５において示された木構造において、ルートから符号（１０）のグループによって表されているリーフ・ノードにたどり着くために通過する道順を、通過する各ノードをルートとする部分木として順に抜きだして並べることにより表現した図である。
【図１０】本発明の実施例で使用するマーカ図像の一例である。図１１のマーカ図像と同じトポロジー構造を持つ。
【図１１】本発明の実施例で使用するマーカ図像の一例である。図１０のマーカ図像と同じトポロジー構造を持つ。
【発明を実施するための形態】
【００３２】  まず本発明に関する手法の基本的な利用形態について、図１から図２を参照して説明する。
【００３３】  図１において、本発明の基本的な利用形態を示す。図１のように、利用者はカメラ等により周囲の映像を取得し、コンピュータへと入力する。もしくはすでに撮影済みの映像をコンピュータへと入力する。このように映像入力機器およびコンピュータにより本マーカ認識方法を利用することができる。
【００３４】  このように入力された映像をコンピュータにより分析し、検出結果を何らかの利用手段を介してユーザに提示する。この検出結果利用手段は、ディスプレイなどの映像出力機器や検出データの処理プログラムなどを含む。
【００３５】  入力された映像からマーカ領域を検出し、検出結果をユーザに返す方法について、本発明での利用形態での処理の流れを、図２を用いて具体的に説明する。この方法は、おもに図２に示すように、画像入力ステップ（ＳＴ０１）と、分析前画像処理ステップ（ＳＴ０２）と、トポロジー情報および各領域の情報抽出ステップ（ＳＴ０３）と、検出対象マーカ絞り込みステップ（ＳＴ０４）と、Ｇｅｏｍｅｔｒｉｃ  Ｈａｓｈｉｎｇ法適用ステップ（ＳＴ０５）と、マーカ情報抽出ステップ（ＳＴ０６）と、検出結果利用ステップ（ＳＴ０７）からなる。
【００３６】本発明では、図２に示すように、まずコンピュータに対して外部記憶装置やカメラなどからマーカ検出対象となる画像の入力を行う（ＳＴ０１）。その後、入力された画像に対してマーカ検出処理を行うために必要な分析前処理を行う（ＳＴ０２）。この分析前処理には画像のグレイスケール変換や二値化、スムージングなど一般的によく知られている画像処理アルゴリズムが用いられる。
【００３７】分析前画像処理ステップ（ＳＴ０２）によって行われた画像処理の結果から、トポロジー情報及び各領域の情報抽出ステップ（ＳＴ０３）において、画像内のトポロジー情報を取得する。このとき、各領域の入力画像中での面積や最小包括矩形、重心位置の情報も同時に取得し、後のステップで利用する。
【００３８】  検出対象マーカ絞り込みステップ（ＳＴ０４）では取得した画像内のトポロジー情報内を検索し、システムに登録されているマーカから、入力画像中にマーカとして存在しうる候補のみへの絞り込みを行う。もし、取得した画像に対応する候補が存在しなければ、マーカが存在しないと判定して以後の処理は行わない。
【００３９】  Ｇｅｏｍｅｔｒｉｃ  Ｈａｓｈｉｎｇ法適用ステップ（ＳＴ０５）においてはトポロジー情報及び各領域の情報抽出ステップ（ＳＴ０３）から得られた各領域の情報うち、トポロジー情報を木構造として表した際に、末端の（リーフとなる）ノードとなる領域の重心を得て、これをＧｅｏｍｅｔｒｉｃ  Ｈａｓｈｉｎｇ法に使用する。
【００４０】  まず、ハッシュ・テーブル上に登録された、マーカのテンプレートと基底の組（もしくはマーカのテンプレート）に対する投票を行うために、座標変換を行う必要がある。図３にこの様子を示す。図３の「入力画像中で３次元空間内で傾いて配置されたマーカ図像の例（１）」は入力画像中で傾いて撮影されたマーカである。マーカ情報が登録されたハッシュ・テーブルに対して投票をおこなうためには、座標変換を行い図３の「基底を使用して２次元平面に投影しなおしたマーカ図像の例（２）」のように正規化した形に変換する必要がある。実際のＧｅｏｍｅｔｒｉｃ  Ｈａｓｈｉｎｇ法適用時には、このように図像全体を変換するのではなく、Ｇｅｏｍｅｔｒｉｃ  Ｈａｓｈｉｎｇ法の投票に必要な入力画像中の点の座標のみを座標変換する。
また、基底とマーカのテンプレートのペア（もしくはマーカのテンプレート）を登録する際に、多くの場合正規化して登録するため、かならずしも図３のように単純に正面から見た形になるわけではない。（図３は説明の簡略化のために、一例として正面からみたように座標変換しただけである。）
【００４１】  一般にはテンプレート側と入力画像側の間で４点の対応があれば、このような座標変換のための基底が取得できる。
【００４２】  組み合わせ分の数の基底を得て、Ｇｅｏｍｅｔｒｉｃ  Ｈａｓｈｉｎｇ時に試される基底の候補とする。この候補のなかから、のちの投票によって正しい基底が選び出される。
【００４３】  また、ハッシュ・テーブルにはあらかじめ、基底とマーカのテンプレートのペア（もしくはマーカのテンプレート）が登録されている。このハッシュ・テーブルに登録されるテンプレートは、後の投票で使用したい点をマーカの図像から選んで登録する。本発明では、領域の重心位置のうちからふさわしいものを選んで登録する。また、このとき、使用した基底とテンプレートの組み合わせをハッシュ・テーブルに登録する。（もしくはテンプレートのみ登録し、基底はのちにひとつずつ試すこともできる。）
【００４４】  図４に登録の様子を表す概念図を示す。図４の「マーカ図像の例（３）」にマーカ図像の１例をしめす。また図４の「（３）のマーカ図像のトポロジー的な構造がｌｅｆｔ  ｈｅａｖｙ  ｄｅｐｔｈ  ｓｅｑｕｅｎｃｅにソートされて得られた木構造（４）」には、そのトポロジー構造をあらわす木構造を示す。
【００４５】  本発明では、トポロジーの木構造のうち、リーフ・ノードとして表現される領域の重心位置を得て、投票にふさわしいものを、マーカのテンプレートとしてあらかじめハッシュ・テーブルのエントリに登録しておく。図４の「（４）の木構造のリーフ・ノードのうち、投票に使用したい点を抜き出し、ハッシュ・テーブル上にテンプレートとして登録した様子（５）」にこの様子を示す。このとき、後述するように、トポロジー情報も同時に登録することにより投票の精度を上げる。同様に他に使用するマーカ図像もハッシュ・テーブル上にテンプレートとして登録しておき、投票の対象となるようにする。
【００４６】  基底とテンプレートの組をあわせてハッシュ・テーブル上に登録してある場合は、入力画像中の点から任意の点を選び基底として座標変換し、ハッシュ・テーブル上の基底とテンプレートの組み合わせに投票する。あらかじめハッシュ・テーブルに基底とテンプレートのペアが登録しているエントリ位置に投票がおこなわれれば、有効な投票となり、投票したエントリ位置にテンプレートからの点の登録がなければ無効な投票となる。
【００４７】  もしくは、基底をひとつだけ選んで、ハッシュ・テーブル上にテンプレートを登録してある場合は、このハッシュ・テーブルに投票を行う際には、前述のように傾いて撮影されたマーカから投票に使用する領域の重心位置を選び、ありうる基底それぞれにたいして座標変換を適用していく。投票に使用する点（重心位置）をハッシュ・テーブルに投票し、あらかじめハッシュ・テーブルにテンプレートが登録しているエントリ位置に投票がおこなわれれば、有効な投票となり、投票したエントリ位置にテンプレートからの点の登録がなければ無効な投票となる。
【００４８】  投票はテンプレートにたいして行われ、投票を受けたテンプレートは受け付けた投票数が投票数分ふえる。また、ミスとなった投票数も数える。
【００４９】  Ｇｅｏｍｅｔｒｉｃ  Ｈａｓｈｉｎｇ法によって試すべき基底をすべて座標変換と投票に使用した後、ハッシュ・テーブルに登録されたテンプレートのうち、投票の結果の評価が良いテンプレートと基底の組み合わせが正解として、それぞれ検出されたマーカと正しい基底として扱われる。
【００５０】  投票の結果の評価には正しい投票数だけでなく、無効となった投票数の数も考慮する。
【００５１】  また、Ｇｅｏｍｅｔｒｉｃ  Ｈａｓｈｉｎｇ法では、様々なテンプレート間でハッシュ・テーブルを共有する際は、単純にすべて正面からみたように座標変換するのではなく、様々なテンプレートでハッシュ・テーブルを共有できるように、各テンプレートを正規化することがある。
【００５２】  ここで、テンプレート側の基底の取得に必要な複数の点はすでに決定してあるので、入力画像側にある点から複数の点のそれぞれに対応する点を選び出し、可能な組み合わせを得て基底の取得に使用するということは、入力画像側の候補の点から、そのテンプレート上で決定された各点に対応するものを順列組み合わせで選び出すことになり、その順列組み合わせの総数がＧｅｏｍｅｔｒｉｃ  Ｈａｓｈｉｎｇ法を適用する際に使用される基底の総数となる。
【００５３】  Ｇｅｏｍｅｔｒｉｃ  Ｈａｓｈｉｎｇ法の適用時にあらかじめ基底とテンプレートの組み合わせを登録しておく方法では、使用可能な基底の数が多い場合には、メモリ使用量が容易に大幅に増加する。あるいは、特定の点をテンプレート側で基底に使用すると決めておき、Ｇｅｏｍｅｔｒｉｃ  Ｈａｓｈｉｎｇ法を適用する際に、もっとも単純な方法は、すべての得られた点に対して総当たりで可能な基底を全て取得し、座標変換をためすことであるが、これは点の数が多い場合には、計算量が容易に大幅に増加する。
【００５４】  本発明では、この基底を得るための点を、先程の得たトポロジー情報の木構造のなかの末端のリーフ・ノードに該当する領域の重心位置を利用して使用する。
【００５５】  Ｇｅｏｍｅｔｒｉｃ  Ｈａｓｈｉｎｇの際、基底を得るための点の組み合わせの数は、メモリ使用量や計算量に大きく影響するため、トポロジー情報を併用することにより、組み合わせの数を減らし、メモリ使用量や計算量を減らす。
【００５６】  トポロジー情報を併用すれば、入力画像中のマーカ領域から得たリーフに該当する領域のうち、基底を得るために使用するテンプレート上の点に対応しうるものを絞り込むことができる。
【００５７】  これには、ルート・ノードから該当リーフ・ノードにたどり着くために通過する各ノードをルートとして部分木を切り出して、通過する道順を表現する。図５に示した木構造は、トポロジー情報を表す木構造をｌｅｆｔ  ｈｅａｖｙ  ｄｅｐｔｈ  ｓｅｑｕｅｎｃｅという木構造を正規化して表現する順序にしたがってソートされている。ｌｅｆｔ  ｈｅａｖｙ  ｄｅｐｔｈ  ｓｅｑｕｅｎｃｅによるソートは必ずしも必須ではないが、前述のような通過する道順を表現する際に、木構造が同じであることを判別するのにｌｅｆｔ  ｈｅａｖｙ  ｄｅｐｔｈ  ｓｅｑｕｅｎｃｅを使用すると処理が簡単にできる。
【００５８】  その部分木により表現された道順の違いにより、リーフ・ノードをグループ化することができる。これにより、トポロジー情報を表す木構造の中のリーフ・ノードをいくつかのグループに細分化して分けることができる。
【００５９】  このグループ分けには、ルートからそのリーフ・ノードにたどり着くために通過する各ノードをルートとする部分木を切り出して、通過順にならべて道順を表現するときに、通過順の部分木の並びによってあらわされる道順が同じであれば、おなじグループに属するとしてあつかう。
【００６０】  このトポロジー情報をもとにしたグループ分け情報を、Ｇｅｏｍｅｔｒｉｃ  Ｈａｓｈｉｎｇ法の適用時に基底を使用するときに考慮することにより、ありうる基底の数を大幅に絞り込むことができる
【００６１】  この基底を得るために使用するテンプレート上の点に対応しうるものを絞り込みの一例を、図３を用いて具体的に説明する。
【００６２】  図５は、図１０のマーカ図像例のトポロジー情報を木構造によって表したものである。このとき、「ルートからリーフ・ノードへとたどる際に得られる部分木による道順が同じ表現であらわされるグループＡ（６）」（以下グループＡと呼ぶ）から「ルートからリーフ・ノードへとたどる際に得られる部分木による道順が同じ表現であらわされるグループＦ（１１）」（以下グループＦと呼ぶ）の各リーフ・ノードのグループ内のあるリーフ・ノードは、他のグループ内にある別のリーフ・ノードとはトポロジー情報のみで区別がつくが、同じグループ内では区別がつかない。
【００６３】  なぜなら、あるグループと別のグループに属するリーフ・ノードにルートから達するために通過するノードを、それぞれルートとするあらたな部分木を抜き出して道順を表現すると、その道順が同じグループ内では同じものとなるが、別グループに属するノードとは別のものになるからである。
【００６４】  図６に図５「ルートからリーフ・ノードへとたどる際に得られる部分木による道順が同じ表現であらわされるグループＢ（７）」（以下グループＢと呼ぶ）のグループのリーフ・ノードにルートから達するための道順を、そのとき通過するノードをそれぞれルートとするあらたな部分木を抜き出して並べてあらわした道順をしめす。また、図７に例として同様に図５「ルートからリーフ・ノードへとたどる際に得られる部分木による道順が同じ表現であらわされるグループＤ（９）」（以下グループＤと呼ぶ）のグループのリーフ・ノードにルートから行き着くために道順を示す。
【００６５】  このようなリーフ・ノードに行き着くための道順を、基底の選択の際の考慮にいれると、テンプレート側であらかじめ基底の選択のために決定されている点と対応する入力画像中の点を道順によって絞り込むことができる。結果としてＧｅｏｍｅｔｒｉｃ  Ｈａｓｈｉｎｇ法を適用する際に問題となる基底の選択の組み合わせを減らせ、メモリ使用量や計算量を減らすことができる。
【００６６】  入力画像中にあるマーカの中のある点を、Ｇｅｏｍｅｔｒｉｃ  Ｈａｓｈｉｎｇ法でつかうテンプレートへ投票できるように座標変換を行う基底を得るには、テンプレート側と入力画像側の間で少なくとも４点の対応が必要である。そのため、以下に具体的な例として４点の対応を使用する形で説明する。
【００６７】  例えば、図５の例では、単純にすべてのリーフ・ノードから基底を得るために必要な４つの点（リーフ・ノードの重心位置）を選ぶとすると、全部で２３個リーフ・ノードが有るため、Ｇｅｏｍｅｔｒｉｃ  Ｈａｓｈｉｎｇで使用することになる基底の数は、すべて合わせると２３ｘ２２ｘ２１ｘ２０＝２１２，５２０となる。この中から、正しい基底を得るためには、これらすべての基底にたいして座標変換を行い、テンプレートとの対応度をチェックすることになる。
【００６８】  しかし、トポロジー情報を考慮して、ルートから行き着くために関連する部分木の構造をリーフ・ノードの選択に使用すると、計算量を減らすことができる。図５において、「ルートからリーフ・ノードへとたどる際に得られる部分木による道順が同じ表現であらわされるグループＢ（７）」（以下グループＢと呼ぶ）の二つのリーフ・ノードから４点の最初の２つ、「ルートからリーフ・ノードへとたどる際に得られる部分木による道順が同じ表現であらわされるグループＥ（１０）」（グループＥと呼ぶ）の１つのリーフ・ノードから３点目の一つ、「ルートからリーフ・ノードへとたどる際に得られる部分木による道順が同じ表現であらわされるグループＦ（１１）」（グループＦと呼ぶ）に属する１１のリーフ・ノードのなかから特定の一つを最後の４点目の一つとして選んだものが、正しい基底となるようにテンプレート側であらかじめ決定しておく。
【００６９】  本発明でＧｅｏｍｅｔｒｉｃ  Ｈａｓｈｉｎｇ法が適用されるステップに進んだときには、既にトポロジー情報を使ってマーカ候補を絞り込んでいるため、トポロジー情報は入力画像中のマーカらしき領域とマーカ候補テンプレートの間では一致している。つまり図５に表現されたトポロジー情報を表した木構造は、入力画像中のマーカらしき領域と、絞り込まれたマーカ候補テンプレートで同じである。
【００７０】  ここでグループＥは、所属ノードがひとつしかなく、ルートからグループＥへの前述の部分木を利用して表した道順をみると、他のグループの道順とはすべて違っている。よって、トポロジー情報からえた道順のみでグループＥを特定できる。この道順を図９に示す。
【００７１】  そのためグループＥは、あらかじめ選んで有る基底に使用する４点のうちの１つ（テンプレート側で選んだグループＥからの１点）と、トポロジー情報からえた道順のみで対応させることができる。
【００７２】  つぎに、グループＦに属する１１のリーフ・ノードの中から１つを座標変換に使用する基底の算出に必要な４点の１つに使用するようにする。グループＦにあるリーフ・ノードにたどり着くための道順を、部分木をつかった前述の方法で表すと、図８のようになる。グループＦに属するリーフ・ノードはみな同じ道順で表されるため、グループ内では互いに区別がつかない。
【００７３】  グループＦには複数のリーフ・ノードがあり、トポロジー情報による道順だけではグループＦの中では互いに区別がつかない。そのため、あらかじめテンプレート側で選んだ、基底に使用する４点のうちのグループＦからの１点に対して、入力画像側のグループＦに属する１１点のリーフ・ノードとの組み合わせ計１１通りが、Ｇｅｏｍｅｔｒｉｃ  Ｈａｓｈｉｎｇ法の際の座標変換のための基底の取得のために試される対象となる。
【００７４】  グループＢに有るリーフ・ノードにたどり着くためのトポロジー情報から得られる道順を図６に示す。
【００７５】  グループＢには２つのリーフ・ノードが属し、この二つのノードはトポロジー情報から得た道順では区別がつかない。最初の基底の算出に必要な４点のうち２点がグループＢからえらばれているため、それらと入力画像側のマーカらしき領域のリーフ・ノードのうちグループＢに属するものとの対応の組み合わせは２ｘ１の計２通りとなる。
【００７６】  最後に、各グループのすべての組み合わせを座標変換のための基底としてＧｅｏｍｅｔｒｉｃ  Ｈａｓｈｉｎｇ時に試すので、（グループＢの２通り）ｘ（グループＥの１通り）ｘ（グループＦの１１通り）＝計２２通りが、Ｇｅｏｍｅｔｒｉｃ  Ｈａｓｈｉｎｇ法適用時に試すための基底の総数となる。
【００７７】  このように図５に示したトポロジー構造から、グループＢから２つ、グループＥから１つ、グループＦから１つを選択したものを基底の取得に利用する点としてあらかじめテンプレート側で設定しておくと、トポロジー情報を考慮しない場合の２１２，５２０通りであった試すべき基底の候補が、このようにトポロジー情報を併用したＧｅｏｍｅｔｒｉｃ  Ｈａｓｈｉｎｇ法の場合２２通りと大幅に削減でき、２２÷２１２，５２０＝９６６０分の１にメモリ使用量や計算量の増大を抑えることができる。
【００７８】  以上のように、基底を得るためのテンプレート側での基準となる点をトポロジー情報考慮して決めておき、Ｇｅｏｍｅｔｒｉｃ  Ｈａｓｈｉｎｇ法を用いてマーカを判別するときにトポロジー情報を併用すると、大幅にメモリ使用量や計算量を削減することができる。
【００７９】  Ｇｅｏｍｅｔｒｉｃ  Ｈａｓｈｉｎｇ法適用ステップ（ＳＴ０５）においては、以上のような方法でトポロジー情報を併用する形でメモリ使用量や計算量を大幅に削減したのち、Ｇｅｏｍｅｔｒｉｃ  Ｈａｓｈｉｎｇを行い、ハッシュ・テーブルに登録されたマーカ候補のテンプレートへの投票に利用し、もっとも一致度が高いと投票されたものを検出マーカとして確定する。
【００８０】  この投票の際にも、トポロジー構造をあらわした木構造から得られた道順の情報をもちい、トポロジー情報をもちいなければ有効である投票でも、この道順よりあきらかに違ったものであるとわかるものは、無効な投票とする。
【００８１】  つまりあるハッシュ・テーブル上のエントリに投票が行われても、そこにテンプレートが登録してある点に至るためのテンプレート上での道順が、現在投票を行っている点の道順と一致していなければ、無効な投票である。
【００８２】  本発明では、このように投票時にトポロジー情報から得られた道順を考慮に入れることにより、投票の精度をより上げることができる。
【００８３】  もし充分な一致度をもつ基底とテンプレートの組み合わせがＧｅｏｍｅｔｒｉｃ  Ｈａｓｈｉｎｇ法を適用しても見つからなかった場合、該当するマーカがなかったものと判定し、以後の処理は行わない。
【００８４】  マーカ情報抽出ステップ（ＳＴ０６）では、ここまでの処理でマーカが確定されたことによりえられる情報を抽出する。
【００８５】  マーカ情報抽出ステップ（ＳＴ０６）で得られる情報には、６自由度（３次元空間内の位置とＸＹＺ軸の回転角度）の姿勢推定がある。まずＧｅｏｍｅｔｒｉｃ  Ｈａｓｈｉｎｇ法を適用し、正しい基底とモデルが得られたため、その基底を得るのに利用した入力画像点とマーカのモデル上（マーカ座標上）の点の対応が４点以上取れている。これにより、姿勢推定に必要な４点がえられていることになり、６自由度の姿勢推定の情報が得られる。
【００８６】  また、６自由度の姿勢推定の情報が得られたことにより、マーカ平面上のどの点が入力画像中のマーカのどの点と対応しているかもわかるようになり、マーカ平面のある領域の色や形状を得るのに、対応する入力画像中のマーカ領域の情報を使用することができる。
【００８７】  検出結果利用ステップ（ＳＴ０７）では、ここまでの処理で得られた情報に基づき、任意の処理を行う。
【実施例】
【００８８】  図１０および図１１は、本発明の実施例１において利用されるマーカの例で有る。【００８９】  図１０および図１１のマーカは、図像は違うが、トポロジー的な構造の観点からは同じ構造をもち、その情報は図５の木構造によって表される。【００９０】  図１０において、一番外側の黒い領域は、図５の木構造のルートとして表される。【００９１】  図１０において、「ＴＯＰＯＬＯ！！」と描かれた領域のトポロジー情報は、その内側に、７つの黒い領域を含み、図５において、「図１０のマーカ図像例のうち、「ＴＯＰＯＬＯ！！」と書かれた領域のトポロジー情報を現す部分木のルート（１２）」のノードから始まる部分木に対応する。また、その領域のうち「！！」以外に対応する領域は、それぞれ、さらに内側に白い領域を含んでいる。【００９２】  同様に、図１０のマーカ図像の人形の領域のうち、顔にあたる領域は、内側に３つの黒い領域を包括し、そのトポロジー構造は「図１０のマーカ図像例のうち、人形形の部分の頭にあたる領域のトポロジー情報を現す部分木のルート（１３）」と書かれたノードから始まる部分木に対応する。【００９３】  同様に、図１０のマーカ図像の人形の領域のうち、胴体部分の領域は、内側に１つの黒い領域を包括し、そのトポロジー構造は「図１０のマーカ図像例のうち、人形形の部分の胴体にあたる領域のトポロジー情報を現す部分木のルート（１４）」とかかれたノードから始まる部分木に対応する。【００９４】  図１０のマーカ図像中の残りの領域は、一番外の黒い領域の下に直接ある、白い領域であり、図５では「ルートからリーフ・ノードへとたどる際に得られる部分木による道順が同じ表現であらわされるグループＦ（１１）」とかかれたグループにあたる。【００９５】  同様に図１１の図像を解釈すると、この図像は図１０と全くおなじトポロジー構造をもち、したがって、その情報は図１０のマーカ図像とは同じ木構造であらわされることになる、よって図５で図示される木構造を持つ。【００９６】  ここで、のちのＧｅｏｍｅｔｒｉｃ  Ｈａｓｈｉｎｇ法で使用するために、あらかじめ図１０、図１１のマーカをハッシュ・テーブルに登録する。具体的には、トポロジー情報の木構造のうち、のちのＧｅｏｍｅｔｒｉｃ  Ｈａｓｈｉｎｇ法適用時に投票に使用するために使用したい木構造末端のリーフ・ノードに対応する領域の重心位置を使用してハッシュ・テーブル上のエントリに登録しておく。【００９７】  図４に、図１０のマーカをハッシュ・テーブルに登録する様子を示す。【００９８】  また、図１０のマーカ図像は図４において再度、「マーカ図像の例（３）」として示されているが、よって図４の「マーカ図像の例（３）」は図５のトポロジーの木構造をもち、その木構造は図１０の図像と同じものとなる。図４においてこの木構造は「（３）のマーカ図像のトポロジー的な構造がｌｅｆｔ  ｈｅａｖｙ  ｄｅｐｔｈ  ｓｅｑｕｅｎｃｅによってソートされて得られた木構造（４）」として図示されている。そのリーフ・ノードに対応する領域の重心位置のうち、投票に使用するものを図４の「（４）の木構造のリーフ・ノードのうち、投票に使用したい点を抜き出し、ハッシュ・テーブル上にテンプレートとして登録し���様子（５）」のようにハッシュ・テーブル上のエントリに登録する。【００９９】  投票に使用する領域は、角度や方向を変えてマーカが撮影された入力画像でもマーカ平面上での実際の重心の位置と、入力画像の２次元平面上での同領域の重心位置の誤差がそれほど変わらないものを選ぶ。すべてのリーフ・ノードを登録する必要はない。【０１００】  この登録時に、同時にその点に木構造のルートからたどり着くために通過する部分木の情報を道順としてあわせて登録する。この情報をＧｅｏｍｅｔｒｉｃ  Ｈａｓｈｉｎｇ法を適用の際に併用して、投票の精度をあげる。【０１０１】  同様のハッシュ・テーブルへの登録処理を図１１のマーカにたいしても行う。【０１０２】  このハッシュ・テーブルへの登録の際に、テンプレート側で基底の変換の取得に使用するあらかじめ決められた複数の点が、全て同一のトポロジー情報を利用した道順であらわすことが可能なテンプレートの間では、正規化を行えばハッシュ・テーブルを共有することが可能である。【０１０３】  よって複数の同じトポロジー構造を持つマーカ間でハッシュ・テーブルを共有することにより、同一トポロジー構造の別図像マーカ間での投票を同時に行うことができる。このようなＧｅｏｍｅｔｒｉｃ  Ｈａｓｈｉｎｇ法が一般的にもつ利点はトポロジー情報を併用しても同じである。【０１０４】  次に、入力画像からこれらマーカを検出するさい、まず入力画像は２値化される。これは、図２では分析前画像処理ステップ（ＳＴ０２）に該当する。【０１０５】  ついで入力画像全体の各白黒領域の隣接関係を得る。このような白黒領域間の隣接関係は、白と黒の２色の領域しか存在しないため、実際には単なる包括関係の木構造として表現できることになる。また同時に各領域の情報（重心位置や最小包括矩形、面積）を得る。これは図２ではトポロジー情報及び各領域の情報抽出ステップ（ＳＴ０３）に該当する。【０１０６】  入力画像中から、登録マーカのうちどれかと合致するものを探す際に、本発明では、まず、登録マーカのうちどれかのトポロジーの木構造と一致するものを、入力画像中から探しだす。これは図２では、検出対象マーカ絞り込みステップ（ＳＴ０４）に該当する。【０１０７】    このような木構造の探索は、既存のトポロジー情報のみを用いるマーカ認識方法でも容易に実現されているものである。しかし、既存のトポロジー情報のみを用いるマーカ認識方法では、このようなトポロジーの木構造の一致のみでマーカの検出を行うので、同一のトポロジー構造を持っているが別図像のマーカに関しては判別ができない。【０１０８】  本発明では、同一のトポロジー構造をもつ別図像のマーカの間の判別をＧｅｏｍｅｔｒｉｃ  Ｈａｓｈｉｎｇ法を利用して行い判別が可能である。【０１０９】  例として、図５に示した木構造と一致するものが入力画像中から発見された場合、それは図１０と図１１に示した２つのマーカのどちらかに該当する可能性がある領域である。【０１１０】  しかし、これだけではマーカの確定と姿勢推定のためには不十分であるので、次にまずＧｅｏｍｅｔｒｉｃ  Ｈａｓｈｉｎｇ法を適用してマーカの確定を行う。これは図２ではＧｅｏｍｅｔｒｉｃ  Ｈａｓｈｉｎｇ法適用ステップ（���Ｔ０５）に該当する。【０１１１】  本実施例での、Ｇｅｏｍｅｔｒｉｃ  Ｈａｓｈｉｎｇ法の具体的な適用例を示す。本発明では従来のＧｅｏｍｅｔｒｉｃ  Ｈａｓｈｉｎｇ法とはちがい、トポロジー情報を併用することによりメモリ使用量や計算量を大幅に削減したのちを大幅に減らすことが可能である。【０１１２】  本実施例では、まず、入力画像中からトポロジー構造がマーカ候補のどれかと一致しているものを選び出しているので、選び出した入力画像中のマーカらしき領域に関しては、トポロジー情報をあらわず木構造は既に得られている。【０１１３】  Ｇｅｏｍｅｔｒｉｃ  Ｈａｓｈｉｎｇ法をこの領域の情報を用いて、マーカ候補からえられたテンプレートが登録されているハッシュ・テーブルへの投票に使用する。【０１１４】  入力画像中のマーカらしき領域のうちトポロジー情報をあらわす木構造のリーフ・ノードにあるものをハッシュ・テーブルへの投票に使用する。このとき、入力画像中の該当領域は３次元空間内に配置されたマーカであるので、傾いていたり回転していたりするため、そのままでは投票できない。そのため、ハッシュ・テーブルに投票できる座標変換を行うための基底を得る必要がある。【０１１５】  このような座標変換の基底を得るためには入力画像中のすくなくとも４点と、ハッシュ・テーブルに登録されているテンプレート４点の対応があればよい。【０１１６】  だが、現在入力画像中からえられているトポロジー情報のみではこの対応は取れないため、まず可能な基底の組み合わせをためし、それを仮定として座標変換を行い、その仮定にもとづいて投票を行う。もしくは可能な基底の組み合わせとテンプレートの組をハッシュ・テーブル上にペアとして登録しておくことにより、どの任意の基底でも投票をうけつけてもっともらしい基底とテンプレートのペアをまとめて判別し、よりもっともらしいものを検出結果としてすることもできる。【０１１７】  仮定が正しければ、他の間違った仮定よりも多くのハッシュ・テーブルへの投票が有効になるはずなので、もっとも多くの投票を得た基底とマーカのテンプレートのペアを正しい答えであるものとして、検出マーカとする。【０１１８】  このとき、トポロジーの木構造ではリーフ・ノードに該当する領域の重心位置を入力画像から得て、座標変換の基底を求めるが、前述のようにリーフ・ノードから４点を選び、ハッシュ・テーブル上のテンプレートの４点と仮に対応させる必要がある。【０１１９】  図５では全部で２３のリーフ・ノードがあるので、これから順列組み合わせでそれぞれ対応する４点を選ぶと、全部で２３ｘ２２ｘ２１ｘ２０＝２１２，５００となってしまう。【０１２０】  しかし、トポロジー情報を併用すると、あらかじめマーカ側の対応する４点を、メモリ使用量や計算量が減らせるように選んでおくと、組み合わせの数を大幅に減らすことができる。【０１２１】  図５において、トポロジー情報を木構造であらわし、ルートからリーフ・ノードにたどり着くために通過するノードを新たにルートとして切り出し、それを並べて道順として表現したものによりグループ化すると、図５の「ルートからリーフ・ノードへとたどる際に得られる部分木による道順が同じ表現であらわされるグループＡ（６）」（以下グループＡ）から「ルートからリーフ・ノードへとたどる際に得られる部分木による道順が同じ表現であらわされるグループＦ（１１）」（以下グループＦ）までの６つのグループに分けることができる。【０１２２】  本実施例では、基底を得るときに使用するマーカ側の４点を、図５の「ルートからリーフ・ノードへとたどる際に得られる部分木による道順が同じ表現であらわされるグループＢ（７）」（以下グループＢと呼ぶ）のノードから２点、「ルートからリーフ・ノードへとたどる際に得られる部分木による道順が同じ表現であらわされるグループＥ（１０）」（以下グループＥと呼ぶ）のノードから１つ、「ルートからリーフ・ノードへとたどる際に得られる部分木による道順が同じ表現であらわされるグループＦ（１１）」（以下グループＦと呼ぶ）のノードから１つ選ぶようにしたものとする。【０１２３】  このとき、入力画像中のマーカらしき領域も同じトポロジー構造をもっているので、グループＢに属するノードの数は２つである。そのため、マーカ側で決めたグループＢから２つ選んで有る点と、入力画像中のマーカらしき領域内のグループＢとの対応は、グループＢには２つしかノードが無いため、おのずと２ｘ１の２通りとなる。【０１２４】  同様にグループＥには１しかノードがないため、対応は１つである【０１２５】  グループＦには１１のノードがあるため、マーカ画像側のグループＦから１つえらんであったとき、１１通りの対応がある。【０１２６】  本実施例では、以上を考慮すると、トポロジー情報を併用した場合、試すべき基底の数は全部で２ｘ１ｘ１１＝２２通りですむ。【０１２７】  以上の２２通りの基底を使いＧｅｏｍｅｔｒｉｃ  Ｈａｓｈｉｎｇを行う。２２通りの基底にそれぞれから得られた座標変換を、入力画像中のマーカらしき領域からトポロジーの木構造の中でリーフ・ノードにあたる領域の入力画像中の重心位置にたいして行い、得られた変換後の座標を使用して、ハッシュ・テーブルに投票する。【０１２８】  この投票時にも道順を考慮し、ハッシュ・テーブル上のエントリに内にテンプレートの点が登録してあり、そこにたいして投票が行われても、投票されたテンプレート上の点の道順と、投票している点の道順が違えば、無効な投票としてあつかう。【０１２９】  これにより、トポロジー情報を考慮して投票の精度をあげることができる。【０１３０】  この組み合わせのうち、有効な投票および無効な投票の数を考慮して評価をおこなったとき、最も多く友好度の高かった基底とテンプレートの組み合わせが、正しい基底と検出されたマーカ種別の組み合わせとして扱われる。【０１３１】  このようにＧｅｏｍｅｔｒｉｃ  Ｈａｓｈｉｎｇ法をトポロジー情報による候補検出の後で併用して行うので、ハッシュ・テーブル上に図１０と図１１を登録されているとき、この二つのマーカ図像のトポロジー情報が同じだとしても、入力画像中の実際のマーカが図１０のマーカだった場合、図１１のマーカのＧｅｏｍｅｔｒｉｃ  Ｈａｓｈｉｎｇ時の投票での評価が、図１０より低くなるため、マーカは図１０であるとして検出される。【０１３２】  また、充分な評価を得たテンプレートと基底の組み合わせがなかった場合は、��ーカが検出されなかったと判定し以下は処理を行わない。【０１３３】  このようにトポロジー情報で、まず、マーカ候補を絞り込み、その後Ｇｅｏｍｅｔｒｉｃ  Ｈａｓｈｉｎｇ法をトポロジー情報を併用して適用することにより同一トポロジー構造で別図像のマーカ間の区別をつけることができる。【０１３４】  またトポロジー情報の併用をおこなうとＧｅｏｍｅｔｒｉｃ  Ｈａｓｈｉｎｇ法適用時に試すべき基底の数が大幅に減るので、メモリ使用量や計算量も少なくてすむ。【０１３５】  ここまでの処理で、検出されたマーカは確定して基底に使用した４点が正しいものであるということになり、入力画像中のマーカらしき領域は、撮影されたマーカであるとして扱うことができる。よって、マーカから様々な情報を抽出することができる。これは図２で言うマーカ情報抽出ステップ（ＳＴ０６）に該当する。【０１３６】  既にマーカの図像上の４点の座標と入力画像中のマーカ領域の４点の対応は基底に使用した４点が正しいとされるので、対応が取れていることになる。このため、この４点を使用して、入力画像中のマーカの３次元空間での位置とＸＹＺ各軸に対する回転をとることができ、６自由度の姿勢推定が行える。【０１３７】  また同様マーカの図像上の４点の座標と入力画像中のマーカ領域の４点の対応は基底に使用した４点が正しいとされていることから、マーカ図像中の任意の点と入力画像中のマーカ領域の任意の点の対応が取れる。【０１３８】  以上のようなマーカ情報抽出ステップ（ＳＴ０６）で得られた情報を利用して任意の処理を行うことができる。これは図２で言う検出結果処理ステップ（ＳＴ０７）にあたる。【０１３９】  たとえば、６自由度の姿勢推定の情報を利用して、入力画像中のマーカ領域の上に３次元のモデルを位置や距離、傾きなどをあわせたうえで合成することができる。【０１４０】  なお、本発明の技術範囲は上記の基本的な利用形態、本実施例に限定されるものではなく、本発明の趣旨を逸脱しない範囲において種々の変更を加えることが可能である。【０１４１】  本発明のトポロジー情報をＧｅｏｍｅｔｒｉｃ  Ｈａｓｈｉｎｇ法適用時に考慮することにより、メモリ使用量や計算量を削減する方法は、トポロジー情報を利用したマーカ認識を行う場合以外にも、メモリ使用量や計算量の削減のために使用可能である。
【符号の説明】
【０１４２】１  入力画像中で３次元空間内で傾いて配置されたマーカ図像の例
２  基底を使用して２次元平面に投影しなおしたマーカ図像の例
３  マーカ図像の例
４  ３のマーカ図像のトポロジー的な構造がｌｅｆｔ  ｈｅａｖｙ  ｄｅｐｔｈ  ｓｅｑｕｅｎｃｅにソートされて得られた木構造
５  ４の木構造のリーフ・ノードのうち、投票に使用したい点を抜き出し、ハッシュ・テーブル上にテンプレートとして登録した様子
６  ルートからリーフ・ノードへとたどる際に得られる部分木による道順が同じ表現であらわされるグループＡ
７  ルートからリーフ・ノードへとたどる際に得られる部分木による道順が同じ表現であらわされるグループＢ
８  ルートからリーフ・ノードへとたどる際に得られる部分木による道順が同じ表現であらわされるグループＣ
９  ルートからリーフ・ノードへとたどる際に得られる部分木による道順が同じ表現であらわされるグループＤ
１０  ルートからリーフ・ノードへとたどる際に得られる部分木による道順が同じ表現であらわされるグループＥ
１１  ルートからリーフ・ノードへとたどる際に得られる部分木による道順が同じ表現であらわされるグループＦ
１２  図１０のマーカ図像例のうち、「ＴＯＰＯＬＯ！！」と書かれた領域のトポロジー情報を現す部分木のルート
１３  図１０のマーカ図像例のうち、人形の部分の頭にあたる領域のトポロジー情報を現す部分木のルート
１４  図１０のマーカ図像例のうち、人形の部分の胴体にあたる領域のトポロジー情報を現す部分木のルート
【図１】
2011170829.tif 000003
【図２】
2011170829.tif 000004
【図３】
2011170829.tif 000005
【図４】
2011170829.tif 000006
【図５】
2011170829.tif 000007
【図６】
2011170829.tif 000008
【図７】
2011170829.tif 000009
【図８】
2011170829.tif 000010
【図９】
2011170829.tif 000011
【図１０】
2011170829.tif 000012
【図１１】
2011170829.tif 000013