(57)【要約】      （修正有）【課題】コンピュータ入力画像中のマーカ認識において、既存のトポロジー情報を用いるマーカ認識手法、および既存のパターン・マッチング手法や画像の特徴点を用いる手法を用いるマーカ認識手法を併用し、同じトポロジー情報を持つマーカ間の区別、３次元空間内での位置推定、マーカ検出にかかる計算コストの低減を行う。【解決手段】トポロジー情報によるマーカ候補領域検出ステップＳＴ０１、トポロジー情報によるマーカ候補絞り込みステップＳＴ０２、トポロジー情報によるマーカ検出ステップＳＴ０３、幾何的な情報によるマーカ検出ステップＳＴ０４、パターン・マッチングによるマーカ検出ステップＳＴ０５，特徴点によるマーカ検出ステップＳＴ０６、マーカの情報抽出ステップＳＴ０７を実行する。【選択図】図２０
2011030168.tif 000002
【特許請求の範囲】
【請求項１】
コンピュータへの入力画像からのマーカ認識手法のうち、入力画像中からマーカ認識をおこなう際に、入力画像から得られるマーカ各領域間の包括関係および隣接関係をあらわすトポロジー情報を利用する認識手法において、トポロジー情報とあわせて、マーカ全体やマーカの各部分の中心、重心、ベクトル、形状の幾何的な情報も併用しマーカの認識を行う手法。
【請求項２】
コンピュータへの入力画像からのマーカ認識手法のうち、入力画像中からマーカ認識をおこなう際に、入力画像から得られるマーカ各領域間の包括関係および隣接関係をあらわすトポロジー情報を利用する認識手法において、トポロジー情報とあわせて、マーカ全体やマーカの各部分の中心、重心、ベクトル、形状の幾何的な情報を利用し、位置推定を行う手法。
【請求項３】
コンピュータへの入力画像からのマーカ認識手法のうち、入力画像中からマーカ認識をおこなう際に、入力画像から得られるマーカ各領域間の包括関係および隣接関係をあらわすトポロジー情報を利用する認識手法において、トポロジー情報とあわせて、マーカ全体やマーカの各部分の中心、重心、ベクトルの幾何的な情報を利用し、直接マーカ図像内に情報を埋め込む手法。
【請求項４】
コンピュータへの入力画像からのマーカ認識手法において、入力画像中からマーカ認識をおこなう際に、入力画像から得られるマーカ各領域間の包括関係および隣接関係をあらわすトポロジー情報を利用する認識手法において、トポロジー情報により検出すべきマーカ候補の絞り込みを行った後に、画像の特徴点の情報を用いる手法やパターン・マッチング手法を併用する手法
【発明の詳細な説明】
【技術分野】
【０００１】  本発明は、コンピュータ画像認識によるマーカ画像の認識に関する。
【背景技術】
【０００２】  コンピュータを利用する入力画像からのマーカ認識において、白黒に二値化した領域のトポロジカルな隣接情報・領域関の包括関係の情報を利用してマーカ認識を行う手法がある（非特許文献１、非特許文献２、非特許文献３）。【０００３】  これらの手法は二値化された画像のトポロジカルな隣接情報・包括関係を木構造として表現し、その木構造の判別によってマーカの特定をするものである。トポロジカルな情報を使用するので、マーカのデザインがトポロジカルな隣接情報・包括関係を保つ限り、マーカの判別が可能である。【０００４】  また、既存の他の入力画像内のマーカ認識や物体追跡を行う手法として、トポロジー情報を利用せず、パターン・マッチングなどの手法を用いるもの（非特許文献４）や画像の特徴点の情報を用いるもの（非特許文献５）も、手法として広く知られている。
【先行技術文献】
【０００５】
【非特許文献１】Ｃｏｓｔａｎｚａ，Ｅ．ａｎｄ  Ｈｕａｎｇ，Ｊ．２００９．Ｄｅｓｉｇｎａｂｌｅ  ｖｉｓｕａｌ  ｍａｒｋｅｒｓ．Ｉｎ  Ｐｒｏｃｅｅｄｉｎｇｓ  ｏｆ  ｔｈｅ  ２７ｔｈ  ｉｎｔｅｒｎａｔｉｏｎａｌ  Ｃｏｎｆｅｒｅｎｃｅ  ｏｎ  Ｈｕｍａｎ  Ｆａｃｔｏｒｓ  ｉｎ  Ｃｏｍｐｕｔｉｎｇ  Ｓｙｓｔｅｍｓ（Ｂｏｓｔｏｎ，ＭＡ，ＵＳＡ，Ａｐｒｉｌ  ０４−０９，２００９）．ＣＨＩ’０９．ＡＣＭ，Ｎｅｗ  Ｙｏｒｋ，ＮＹ，１８７９−１８８８．ＤＯＩ＝ｈｔｔｐ：／／ｄｏｉ．ａｃｍ．ｏｒｇ／１０．１１４５／１５１８７０１．１５１８９９０
【０００６】
【非特許文献２】Ｃｏｓｔａｎｚａ，Ｅ．ａｎｄ  Ｍｉｒｊａ，Ｌ．Ｔｅｌｌｉｎｇ  ａ  ｓｔｏｒｙ  ｏｎ  ａ  ｔａｇ：Ｔｈｅ  ｉｍｐｏｒｔａｎｃｅ  ｏｆ  ｍａｒｋｅｒｓ’ｖｉｓｕａｌ  ｄｅｓｉｇｎ  ｆｏｒ  ｒｅａｌ  ｗｏｒｌｄ  ａｐｐｌｉｃａｔｉｏｎｓ（ｐａｐｅｒ  ｐｒｅｓｅｎｔａｔｉｏｎ）．Ｉｎ  Ｐｒｏｃｅｅｄｉｎｇｓ  ｏｆ  ｔｈｅ  Ｍｏｂｉｌｅ  Ｉｎｔｅｒａｃｔｉｏｎ  ｗｉｔｈ  ｔｈｅ  Ｒｅａｌ  Ｗｏｒｌｄ  Ｗｏｒｋｓｈｏｐ  ａｔ  Ｍｏｂｉｌｅ  ＨＣＩ２００６，Ｅｓｐｏｏ，Ｆｉｎｌａｎｄ，ｓｅｐ  ２００６
【０００７】
【非特許文献３】Ｂｅｎｃｉｎａ，Ｒ．，Ｋａｌｔｅｎｂｒｕｎｎｅｒ，Ｍ．，ａｎｄ  Ｊｏｒｄａ，Ｓ．２００５．Ｉｍｐｒｏｖｅｄ  Ｔｏｐｏｌｏｇｉｃａｌ  Ｆｉｄｕｃｉａｌ  Ｔｒａｃｋｉｎｇ  ｉｎ  ｔｈｅ  ｒｅａｃＴＩＶｉｓｉｏｎ  Ｓｙｓｔｅｍ．Ｉｎ  Ｐｒｏｃｅｅｄｉｎｇｓ  ｏｆ  ｔｈｅ  ２００５  ＩＥＥＥ  Ｃｏｍｐｕｔｅｒ  Ｓｏｃｉｅｔｙ  Ｃｏｎｆｅｒｅｎｃｅ  ｏｎ  Ｃｏｍｐｕｔｅｒ  Ｖｉｓｉｏｎ  ａｎｄ  Ｐａｔｔｅｒｎ  Ｒｅｃｏｇｎｉｔｉｏｎ  （Ｃｖｐｒ’０５）−Ｗｏｒｋｓｈｏｐｓ−Ｖｏｌｕｍｅ  ０３（Ｊｕｎｅ  ２０−２６，２００５）．ＣＶＰＲ．ＩＥＥＥ  Ｃｏｍｐｕｔｅｒ  Ｓｏｃｉｅｔｙ，Ｗａｓｈｉｎｇｔｏｎ，ＤＣ，９９．ＤＯＩ＝ｈｔｔｐ：／／ｄｘ．ｄｏｉ．ｏｒｇ／１０．１１０９／ＣＶＰＲ．２００５．４７５
【０００８】
【非特許文献４】Ｋａｔｏ，Ｈ．ａｎｄ  Ｂｉｌｌｉｎｇｈｕｒｓｔ，Ｍ．１９９９．Ｍａｒｋｅｒ  Ｔｒａｃｋｉｎｇ  ａｎｄ  ＨＭＤ  Ｃａｌｉｂｒａｔｉｏｎ  ｆｏｒ  ａ  Ｖｉｄｅｏ−Ｂａｓｅｄ  Ａｕｇｍｅｎｔｅｄ  Ｒｅａｌｉｔｙ  Ｃｏｎｆｅｒｅｎｃｉｎｇ  Ｓｙｓｔｅｍ．Ｉｎ  Ｐｒｏｃｅｅｄｉｎｇｓ  ｏｆ  ｔｈｅ  ２ｎｄ  ＩＥＥＥ  ａｎｄ  ＡＣＭ  ｉｎｔｅｒｎａｔｉｏｎａｌ  Ｗｏｒｋｓｈｏｐ  ｏｎ  Ａｕｇｍｅｎｔｅｄ  Ｒｅａｌｉｔｙ（Ｏｃｔｏｂｅｒ  ２０−２１，１９９９）．ＩＷＡＲ．ＩＥＥＥ  Ｃｏｍｐｕｔｅｒ  Ｓｏｃｉｅｔｙ，Ｗａｓｈｉｎｇｔｏｎ，ＤＣ，８５．
【０００９】
【非特許文献５】情報処理学会研究報告．ＣＶＩＭ（コンピュータビジョンとイメージメディア），ＩＰＳＪ  ＳＩＧ  Ｎｏｔｅｓ．ＣＶＩＭ  ２００７（１）ｐｐ．１０１−１０８  ２００７０１１１  社団法人情報処理学会
【発明の開示】
【発明が解決しようとする課題】
【００１０】  マーカ図像内の白黒領域のトポロジカルな隣接情報・包括関係を木構造として解釈し、その木構造の判別によってマーカの特定をする既存の手法では、トポロジー情報を使用するため、ある図像を持つ入力画像中でのマーカ領域が傾いていたり回転していたりしても、同じトポロジカルな隣接情報・包括関係を保つ限りにおいて同一マーカとして判別が可能であるが、その反面、マーカの図像・形状が全く違っている、二つの別のマーカ図像でもトポロジー情報が全く同じであれば、図像的・形状的には全く違うマーカでも同じマーカとして認識されてしまう。【００１１】  しかし、おなじトポロジー構造をもつマーカ図像群は、多くの場合数多く存在し、このためトポロジー情報のみに基づく手法ではマーカ間の区別が十分でないことが多い。このようにマーカ認識の一意性が十分でないという問題が、既存のトポロジー情報のみを用いた手法に存在する。【００１２】  また、上記のような既存のトポロジー手法においては、トポロジー情報のみを使用するため、マーカ形状やマーカ図像が他手法にくらべて比較的自由にデザインできるというメリットがあるものの、画像からのマーカ領域の推定やマーカの２次元平面および３次元空間内での向きや位置の推定に必要な座漂の情報が、形状を考慮しない性質をもつトポロジー情報には含まれないため、トポロジー情報のみでは位置推定が行えないという欠点がある。【００１３】  またトポロジー手法だけでなく、既存のパターン・マッチング手法や、画像の特徴点を利用する方法を使用するマーカ認識手法の多くにおいても、多くの種別のマーカを多数処理する際には、画像から検索すべき登録マーカの検出をする段階において、必要なマーカ数や種別に応じて処理時間や計算量が、大幅に増加してしまうという問題がある。
【課題を解決するための手段】
【００１４】  本発明は、以上のような課題を解決するため、以下の手段を採用する。【００１５】  トポロジー情報だけでは不十分なマーカ認識の一意性を、マーカ全体やマーカの各部分の中心・重心・ベクトル・形状の幾何的な情報を併用することにより解決する。また、そのような幾何的情報では不十分とされる場合には、さらに絞り込みされたマーカ候補群に対して、既存のマーカ領域内での特徴点の情報やパターン・マッチング手法を併用するという手段によって解決する。【００１６】  また同様にトポロジー情報と併用して、マーカ全体やマーカの各部分の中心・重心・ベクトルの幾何的な情報を利用することにより、直接マーカ内に情報を埋め込む手段も用いる。【００１７】  本発明で言うトポロジー情報とは、二値化された画像を用いる既存のトポロジカルなマーカ内各領域の隣接関係に基づくマーカ認識手法と同様、マーカ内各領域の形状や大きさにかかわらず、単に隣接関係と各領域の色のみをあらわす情報をさす。【００１８】  例えば図１７の左側にあるマーカ例（１７）に示されたマーカ図像のトポロジー情報を、それぞれ黒い領域を黒丸、白い領域を白丸とし、隣接関係を矢印によってあらわすとすると、図１７の右側に示されたグラフ（１８）のようになる。【００１９】  ここで白黒に二値化された画像では、ある領域はかならず別の領域に含まれることになるか、もしくは一番外側の領域となるため、ある領域が別の領域に隣接しているということは、その領域との包括関係にあるということと同じことになる。【００２０】  たとえば、既存の隣接関係および包活関係をあらわすトポロジー情報のみに基づく手法においては、図１８のマーカ図像例（１９）と図１９のマーカ図像例（２１）を認識する際、図１８のトポロジー情報のグラフ（２０）および図１９のトポロジー情報のグラフ（２２）に示されたように、両マーカとも同じトポロジー構造をもつため、両マーカの区別がトポロジー情報のみではできない。【００２１】  本発明の手法では、このように複数マーカ間での区別がトポロジー情報のみでは行えない場合、トポロジー情報にくわえて、図像から得ることのできる各領域における中心・重心・ベクトル・形状の幾何的な情報をまず使用し、両マーカの区別を試みる。【００２２】  たとえば、図１８のマーカ図像例（１９）と図１９のマーカ図像例（２１）間では、トポロジー情報は同じだが、各領域の中心・重心・形状や各領域間のベクトルといった情報は互いに違っているので、このような幾何的な情報を利用して判別ができる。【００２３】  このように本発明の手法では、トポロジー情報が同じマーカが発見され、区別できない場合に、幾何的な情報を併用する手段を用いる。【００２４】  しかし、このような幾何的な情報ではマーカの区別に関して十分な情報がまだ得られない場合においては、画像の特徴点の抽出およびパターン・マッチングの手法を利用して、さらにマーカ認識を試みる。【００２５】  たとえば、図１８のマーカ図像例（１９）と図１９のマーカ図像例（２１）図像間では、図像はかなり違っているためパターン・マッチングや画像の特徴点の情報を併用すれば、判別がより正確に行える。【００２６】  画像の特徴点を用いるマーカ認識手法���パターン・マッチングに基づくマーカ認識手法は、広くもちいられているものである。しかし、既存の特徴点のみをもちいた手法やパターン・マッチングのみに基づく手法と違い、本発明では、このような特徴点を用いる手法やパターン・マッチングに基づく手法を適用する前段階の処理において、トポロジー情報に基づいて検出対象となるマーカ候補の絞り込みを行っており、検出対象となるマーカ候補の絞り込みを行う手段を用いている。【００２７】このようなトポロジー情報による絞り込みにより、検出すべきマーカの対象となるマーカ候補の数を絞り込めば、計算コストの削減が行え、多量の検出マーカ候補がある際に計算上のメリットがある。【００２８】  また既存のトポロジー情報にもとづくマーカ認識手法は、トポロジー情報を利用して、登録済みの検索対象マーカとトポロジカルな構造が一致するものを検出するというものであるが、本発明の応用として、登録済みの検索対象マーカとの一致により情報を得るのではなく、幾何情報を併用する手法によりマーカ内に直接データを埋め込み、マーカから直接データを得る手法も用いる。【００２９】  たとえば、本手法では図３の例のマーカのように、マーカ内のデータエンコード部にデータが埋め込みを行える。既存のトポロジーのみに基づく手法では、各領域の幾何的な情報をデータのエンコードには利用していないので、形状や位置を考慮しないトポロジー情報のみでは、データエンコード部に埋め込まれたビット情報の並び順を適切な方法で抽出できないが、本手法ではベクトルや角度という幾何的情報を利用してビット情報の並び順を復号でき、既存のトポロジー情報のみに基づく手法とちがい、検索対象マーカとの一致の検出を行うことなく、マーカに直接的に情報を埋め込み、また直接的に抽出する。【００３０】  このように直接的にデータをマーカにエンコードする場合、本手法はトポロジー情報と幾何的情報を併用しており、かつマーカのトポロジカルな特徴をデータエンコード法により制限しているため、そのような制限されたトポロジカルな特徴を、入力画像中からの検索のさいに利用し、マーカ領域の検索速度を向上することができる。【００３１】  本手法では既存のトポロジー情報のみに基づく手法単体では、包括関係以外の情報を考慮しないため不可能であった、空間での位置推定を、本手法では上記の幾何的な情報、特徴点の情報を使用するため、それらの情報を使用して容易に行うことができる。
【発明の効果】
【００３２】  本発明によれば、トポロジー情報と幾何的な情報およびパターン・マッチングおよび画像の特徴点情報の併用により、既存のトポロジー情報を利用するマーカ認識手法の欠点である、マーカの認識時の一意性が少ないという問題を解決できる。【００３３】  同時に、既存のトポロジー情報を利用するマーカ認識手法の欠点である入力画像からの位置推定を容易にかつ正確性をまして行うことができる。【００３４】  また、マーカのデザインおよびデータのエンコーディング方法によっては、それらのトポロジカルな性質を用いて、マーカ検索をすばやく行うことができる。【００３５】  既存の特徴点やパターン・マッチングを利用してマーカ認識を行う手法においても、本手法のように、特徴点やパターン・マッチングを行う前段階でトポロジー情報を用いて、検出対象マーカ候補を絞り込むことにより、計算コストを削減できる。
【図面の簡単な説明】
【００３６】
【図１】本発明に関する手法の基本的な利用形態を表す図である。
【図２】本発明に関する手法の基本的な利用形態での処理の基本的な流れを表すフローチャートである。
【図３】本発明の実施例１で説明されている、幾何情報とトポロジー情報を利用した基準部とデータエンコード部を持つマーカの例である。
【図４】本発明の実施例１で説明されている、図３に示されたマーカ例のトポロジー情報をあらわす図である。
【図５】本発明の実施例１で説明されているマーカ認識の処理の基本的な流れを表すフローチャートである。
【図６】本発明の実施例２で説明されている、幾何情報とトポロジー情報を利用した複数のデータエンコード部をもつマーカの例である。
【図７】本発明の実施例２で説明されているマーカ認識の処理の基本的な流れを表すフローチャートである。
【図８】本発明の実施例３で説明されている、幾何情報とトポロジー情報を利用したデータエンコード部のみを持つマーカの例である。
【図９】本発明の実施例３で説明されているマーカ認識の処理の基本的な流れを表すフローチャートである。
【図１０】本発明の実施例４で説明されている、実施例１、実施例２、実施例３の各種別のマーカを、それぞれカードの上下に配置した例である。
【図１１】本発明の実施例５で説明されている、幾何情報とトポロジー情報を利用した、中心に基準ベクトル取得部と周辺部にデータエンコード部をもつマーカの例である。
【図１２】図１２は図１１に示されたマーカの各部位の説明である。
【図１３】本発明の実施例５で説明されているマーカ認識の処理の基本的な流れを表すフローチャートである。
【図１４】本発明の実施例６で説明されている、幾何情報とトポロジー情報を利用した、中心に図像を持ち、周辺部に基準ベクトル取得部とデータエンコード部の両方をもつマーカの例である。
【図１５】図１５は図１４に示されたマーカの各部位の説明である。
【図１６】本発明の実施例６で説明されているマーカ認識の処理の基本的な流れを表すフローチャートである。
【図１７】本発明の実施例７で説明されている、トポロジー情報を使用してマーカ候補を絞り込みし、幾何情報およびパターン・マッチング・特徴点情報と併用してマーカ認識を行うマーカ例その１と、そのマーカのトポロジー情報を表した図である。
【図１８】本発明の実施例７で説明されている、トポロジー情報を使用してマーカ候補を絞り込みし、幾何情報およびパターン・マッチング・特徴点情報と併用してマーカ認識を行うマーカ例その２と、そのマーカのトポロジー情報を表した図である。
【図１９】本発明の実施例７で説明されている、トポロジー情報を使用してマーカ候補を絞り込みし、幾何情報およびパターン・マッチング・特徴点情報と併用してマーカ認識を行うマーカ例その３と、そのマーカのトポロジー情報を表した図である。
【図２０】本発明の実施例７で説明されているマーカ認識の処理の基本的な流れを表すフローチャートである
【発明を実施するための形態】
【００３７】  まず本発明に関する手法の基本的な利用形態について、図１から図２を参照して説明する。
【００３８】  図１において、本発明の基本的な利用形態を示す。図１のように、利用者はカメラ等により周囲の映像を取得し、コンピュータへと入力する。もしくはすでに撮影済みの映像をコンピュータへと入力する。このように映像入力機器およびコンピュータにより本手法を利用することができる。
【００３９】  このように入力された映像をコンピュータにより分析し、検出結果を何らかの利用手段をかいしてユーザに提示する。この検出結果利用手段は、ディスプレイなどの映像出力機器や検出データの処理プログラムなどを含む。
【００４０】  入力された映像からマーカ領域を検出し、検出結果をユーザに返す方法について、本発明での利用形態での処理の流れを、図２を用いて具体的に説明する。この方法は、おもに図２に示すように、画像入力ステップ（ＳＴ０１）と、分析前画像処理ステップ（ＳＴ０２）と、トポロジー情報および各領域の情報抽出ステップ（ＳＴ０３）と、画像内特徴点および幾何情報抽出ステップ（ＳＴ０４）と、検出対象マーカ候補絞り込みステップ（ＳＴ０５）と、マーカ検出ステップ（ＳＴ０６）と、マーカ情報抽出ステップ（ＳＴ０７）と、検出結果利用ステップ（ＳＴ０８）からなる。
【００４１】  本発明では、図２に示すように、まずコンピュータに対して外部記憶装置やカメラなどからマーカ検出対象となる画像の入力を行う（ＳＴ０１）。その後、入力された画像に対してマーカ検出処理を行うために必要な分析前処理を行う（ＳＴ０２）。この分析前処理には画像のグレイスケール変換や二値化、スムージングなど一般的によく知られている画像処理アルゴリズムが用いられる。
【００４２】  分析前処理（ＳＴ０２）によって行われた画像処理の結果から、画像内のトポロジー情報を取得する（ＳＴ０３）。得られたトポロジー情報は後の検出対象マーカ候補絞り込みステップ（ＳＴ０５）やマーカ検出ステップ（ＳＴ０６）およびマーカ情報抽出ステップ（ＳＴ０７）などで利用される。
【００４３】  同様に、画像の特徴量やその他のトポロジー情報検出ステップ内では得られない幾何的な情報を、後の検出対象マーカ候補絞り込みステップ（ＳＴ０５）やマーカ検出ステップ（ＳＴ０６）およびマーカ位置計算ステップ（ＳＴ０７）で併用する場合、分析前処理（ＳＴ０２）によって行われた画像処理の結果から、必要な画像特徴量や幾何的な情報の取得を、画像内特徴点および幾何情報抽出ステップ（ＳＴ０４）において行う。もし画像内特徴点および幾何情報抽出ステップ（ＳＴ０４）が、後のステップでは使用されない場合、画像内特徴点および幾何情報抽出ステップ（ＳＴ０４）は省略することができる。
【００４４】  検出対象マーカ候補絞り込みステップ（ＳＴ０５）において、これまでのステップで得られた、画像のトポロジー情報、特徴点情報、幾何情報などを利用し、検出すべきマーカ候補の絞り込みを行い、検索対象マーカ数を削減する。本手法の応用として利用されるマーカの種別によっては、この検出対象マーカ候補絞り込みステップ（ＳＴ０５）が必要ない場合がある。
【００４５】  マーカ検出ステップ（ＳＴ０６）において、絞り込みを行われた検索対象マーカと一致するマーカが入力画像内に存在するかどうか検出を行う。この検出の際には、再度以前のステップで得られたトポロジー情報、特徴点情報、幾何情報を併用する。マーカが検出されたさいは、マーカ情報抽出ステップ（ＳＴ０７）にすすむ。
【００４６】  マーカ情報抽出ステップ（ＳＴ０７）では、以前までのステップで得られた情報と検出されたマーカに関する情報を抽出し、またマーカの２次元および３次元空間内での座標や大きさなどの位置情報を推定する。
【００４７】  検出結果利用ステップ（ＳＴ０８）では、得られた検出結果を利用する。
【００４８】  既存の、トポロジー情報のみに基づくマーカ認識手法では、マーカのデザインがトポロジカルな隣接情報・包括関係を保つ限りマーカの判別が可能であるが、反面、マーカの図像、形状が全く違っていてもトポロジカルな隣接情報・包括関係が全く同じであれば、図像的・形状的には、全く違うマーカでも同じマーカとして認識されるという問題があった。これを、マーカ全体やマーカの各部分の中心・重心・ベクトル・形状の幾何的な情報や、画像の特徴点の情報、パターン・マッチング手法を、トポロジー手法と併用して実現した。
【００４９】  またトポロジー情報を利用したマーカ認識手法において、検出候補マーカとのトポロジー情報の一致によりマーカ検出を行うのではなく、同様に幾何的な情報を併用することにより、直接マーカ内にデータを埋め込むことを実現した。
【００５０】  トポロジー情報を検出マーカ候補の絞り込みに使用することにより、既存の広く知られた画像の特徴点を利用するマーカ認識手法やパターン・マッチング手法に基づく手法においても、マーカ認識の計算コストを削減することを可能とした。
【実施例１】
【００５１】  図３は、本発明の実施例１において利用されるマーカの一例である。このタイプのマーカの各部分は、図３に示されているように、基準部（１）とデータエンコード部（２）とに分かれる。この図３の例においては、１１ビットのデータをエンコードしているが、エンコードされるデータのビット数は、自由に増減可能である。【００５２】  本実施例１ではデータエンコード部においては、内部にほかの領域を含まない、黒と白の四角形の領域が配置されている。これらの領域は、その色に応じて０か１情報を各１ビットずつエンコードしている。以下では、このような領域を以後ではビット情報領域と呼ぶものとする。図３の例では、データエンコード部（２）には、左から黒のビット情報領域が４つ、白のビット情報領域が３つ、黒のビット情報領域が３つ、白のビット情報領域が１つの順で並んでいる。黒のビット情報領域が０、白のビット情報領域が１をあらわすとすると、このデータエンコード部（２）は００００１１１０００１の二進数の１１ビットを荒らすことになる。【００５３】  まず、本マーカを入力画像内から検出する際、このマーカのトポロジカルな構造を利用する。【００５４】  図３のマーカのトポロジカルな構造を図４に示す。図４における白丸は図３における白い領域を、黒丸は図３における黒い領域を、矢印はそれぞれ領域間の隣接関係をしめすものとする。基準部（１）とデータエンコード部（２）は、違ったトポロジー情報を持っているので容易に判別できる。【００５５】  図３の例では、基準部（１）は黒領域の中に一つの白領域が入っており、それと対応する領域のトポロジー情報は、図４では、「実施例１図３のマーカ例における基準部のトポロジー情報を表す部位（点線内）（３）」として注釈されている。【００５６】  図３のデータエンコード部（２）においては、エンコード方法から明らかなように、黒いビット情報領域白いビット情報領域の数の総数はデータエンコード部（２）内にエンコードされたビット数と一致する。これと対応するトポロジー情報はそれぞれ、図４において「実施例１図３のマーカ例におけるデータエンコード部のうち黒いビット情報領域のトポロジー情報を表す部位（点線内）（４）」「実施例１図３のマーカ例におけるデータエンコード部のうち白いビット情報領域のトポロジー情報を表す部位（点線内）（５）」として注釈されている。【００５７】  このようなトポロジー情報を持つ領域を、入力画像中から探し出せば、それがマーカ候補となる。【００５８】  この実施例１のマーカの例では、データエンコード部（２）内の白および黒のビット情報領域から得られたビット列は、隣接および包括関係のみを表すことしかできないトポロジー情報だけでは、ビットの並び順序は決定できないが、基準部（１）からのベクトルの長さによってソートされることにより、１１ビットのデータの順序を決定してエンコードすることができる。【００５９】  このようにマーカの検索においてトポロジー情報を利用し、データのエンコードとデコードにおいて幾何的な情報を併用する。【００６０】  検出されたマーカから各領域の中心や重心、形状など、システムにたいしては既知の幾何的な情報を併用し、マーカの位置推定などを���うことができる。【００６１】  たとえば、基準部（１）および各ビット領域の入力画像内での座標や面積、マーカの輪郭線を利用して、２次元平面上および３次元空間上でのマーカ位置の推定を行うことができる。【００６２】  さらに、本発明ではデータエンコード部（２）においては、ビット情報領域の総数はデータエンコード部（２）のビット数と一致しなければならないという性質を利用して、マーカ領域の検索をすばやく行うことができる。【００６３】  たとえば実施例１のサンプルにおいては、図４におけるデータエンコード部（２）の白いビット領域のトポロジー情報（領域隣接情報）とデータエンコード部の黒いビット情報領域のトポロジー情報（領域隣接情報）に属するようなノード数が、データエンコード部（２）のビット数と一致する。【００６４】  白と黒のビット情報領域を２進数として解釈することにより、データエンコード部（２）には、かならずビット数の半分以上の個数の白もしくは黒のビット情報領域が内部に存在することになる。ある桁数の２進数における０の総数は、全体の桁数から１の総数を引いたものと必ず一致するので、かならず０の個数が全体の桁数の半分を超えるか、もしくはちょうど半分となるか、そうでなければ、１の個数が全体の桁数の半分を超えるか、もしくはちょうど半分となっていることになる。【００６５】  一般に入力画像において、トポロジー的に内部に包括された領域がより多い領域は、入力画像では、より稀になる傾向があるため、データエンコード部（２）のビット数が十分大きく、入力画像中に含まれるデータエンコード部（２）の白および黒のビット情報領域の総数が十分大きい場合、本手法では、このような特徴を利用してマーカ検索を行うことにより、マーカ検索の速度を向上させることができる。【００６６】  また、ベクトルの向きを利用して、認識されたマーカが有効なマーカであるかどうかを調べる。例えば、基準部（１）から各ビット情報領域に対する向きが一致していない場合、それは有効なマーカではないとして検出対象からはずされる。【００６７】  本種別のマーカにおいては、上記のようなベクトルを利用したデータエンコード方法が正常に保たれる限り、おもにトポロジー情報を用いているという性質により、マーカ図像や形状は自由に設定できる。【００６８】  たとえばビット情報領域の形は上記のような認識法では使用されていないため四角でなく他の形状でもよい。また同様に、マーカ全体の形が長方形ではなく、上記の認識法に合致する限り、楕円や他の形状でもよい。【００６９】  本実施例１で述べられた本発明の応用の実施例における処理の具体例を図５に示す。
本実施例１の具体例は、主に、トポロジー情報によるマーカ候補領域検出ステップ（ＳＴ０１）、基準部からの距離によるデータエンコード部ソートステップ（ＳＴ０２）、マーカ有効性判断ステップ（ＳＴ０３）、マーカ情報抽出ステップ（ＳＴ０４）の四つのステップからなる。【００７０】  マーカ候補領域検出ステップ（ＳＴ０１）では、既に以前の段階で入力画像から分析されて得られたトポロジー情報から、マーカ候補領域を一つ検出する。この際には、マーカ領域のトポロジー情報を利用して、合致するものを候補領域として検出する。【００７１】  基準部からの距離によるデータエンコード部ソートステップ（ＳＴ０２）では、マーカ候補領域検出ステップ（ＳＴ０１）で得られたマーカ候補領域における基準部からのベクトルの長さを利用して、データエンコード領域の各ビット情報領域から得られた各ビット情報をソートし、ビット情報の順序を決定してデータのデコードをする。このように、本手法ではトポロジー情報とベクトル情報が併用される。【００７２】  マーカ有効性判断ステップ（ＳＴ０３）においては、さらにマーカ候補領域の基準部から、各ビット情報領域へのベクトルの長さや角度も利用して、有効なマーカであるかどうかを判断する。異常なベクトルの長さや角度が検出された場合、無効なマーカであるとして拒否する。【００７３】  マーカ有効性判断ステップ（ＳＴ０３）において、有効であると判断されたマーカ候補は正しいマーカであるとして、マーカ情報抽出ステップ（ＳＴ０４）にすすみ、マーカから得られる情報を抽出する。その後は、必要であればマーカ候補領域検出ステップ（ＳＴ０１）に再度進み、次のマーカ候補をチェックすることができる。【００７４】  マーカ有効性判断ステップ（ＳＴ０３）において、無効であると判断されたマーカ候補は、無効マーカ候補として無視される、その後は、必要であればマーカ候補領域検出ステップ（ＳＴ０１）に再度進み、次のマーカ候補をチェックすることができる。【００７５】  必要なすべてのマーカ候補領域がチェックし終わったら、マーカ検出は終了し、位置計算や検出結果の利用などの別処理へと移行する。
【実施例２】
【００７６】  実施例２として、図６に、実施例１と同様のベクトル情報をトポロジー情報と併用したマーカの一例をしめす。ただし、実施例１と違い、図６のマーカは基準点をもたず、データエンコード部を複数の違ったトポロジー的な性質をもつ領域にわけ、それにより各領域を区別することができる。たとえば図６のマーカの例では、「実施例２におけるマーカ例のデータエンコード部▲１▼（６）」と「実施例２におけるマーカ例のデータエンコード部▲２▼（７）」として図示された、二つのデータエンコード部を持ち、そのなかに０か１の１ビットをそれぞれにエンコードする、ビット情報領域が配置されている。【００７７】  隣接および包括関係のみを表すことしかできないトポロジー情報だけでは、ビットの並び順序は決定できないため、データをデコードする際に実施例２でもベクトル情報を使用する。データをデコードするために、実施例１のように基準部からのベクトルを使用する代わりに、実施例２の図６のマーカの例では、別のデータエンコード部や、別のデータエンコード部内の任意のビット情報領域からのベクトルの長さを使用して、ビット情報領域の色から得られるビット列をソートしてビットの並ぶ順序を確定しデータのデコードを行う。【００７８】  例えば図６の例では、データエンコード部▲２▼（７）の任意のビット情報領域からの距離を利用して、データエンコード部▲１▼（６）内での各ビット情報領域によってあらわされるビット列のソートをおこなうことができる。【００７９】  このように実施例２においてもマーカの検索においてトポロジー情報を利用し、データのエンコードとデコードにおいては幾何的な情報を併用する。【００８０】  実施例２においても、実施例１のようにマーカの検出を画像内により稀なトポロジー情報を利用することにより、マーカ検出を効率的に行うことができる。【００８１】  検出されたマーカから各領域の位置や大きさや重心や形状といった、システムにたいしては既知の幾何的な情報を併用し、マーカの位置推定などを行うことができる。【００８２】  本種別のマーカにおいても、上記のようなベクトルを利用したデータエンコード方法が正常に保たれる限り、おもにトポロジー情報を用いているという性質により、マーカ図像や形状は自由に設定できる。【００８３】  本実施例２で述べられた本発明の応用の実施例における処理の具体例を図７に示す。本実施例２の具体例は、主に、トポロジー情報によるマーカ候補領域検出ステップ（ＳＴ０１）、他のデータエンコード部からの距離によるソートステップ（ＳＴ０２）、マーカ有効性判断ステップ（ＳＴ０３）、マーカ情報抽出ステップ（ＳＴ０４）の四つのステップからなる【００８４】  マーカ候補領域検出ステップ（ＳＴ０１）では、既に以前の段階で入力画像から分析されて得られたトポロジー情報から、マーカ候補領域を一つ検出する。この際には、先に述べたように、マーカ領域のトポロジー的な特徴を利用して候補領域を検出する。【００８５】  他のデータエンコード部からの距離によるソートステップ（ＳＴ０２）では、マーカ候補領域検出ステップ（ＳＴ０１）で得られたマーカ候補領域の複数のデータエンコード部を利用して、他のデータエンコード部も���くは他のデータエンコード部内のビット情報領域からの距離に応じて、もう一方のデータエンコード部内のビット情報領域から得られるビット列を、互いにソートしあう。このように、トポロジー情報とベクトル情報が併用される。【００８６】  マーカ有効性判断ステップ（ＳＴ０３）においては、さらに、あるデータエンコード部のビット情報領域のからの、他のビット情報領域へのベクトルの長さや角度も利用して、有効なマーカであるかどうかを判断する。異常なベクトルの長さや角度が検出された場合、無効なマーカであるとして拒否する。【００８７】  マーカ有効性判断ステップ（ＳＴ０３）において、有効であると判断されたマーカ候補は正しいマーカであるとして、マーカ情報抽出ステップ（ＳＴ０４）にすすみ、マーカから得られる情報を抽出する。そののち、マーカ候補領域検出ステップ（ＳＴ０１）に再度進み、次のマーカ候補をチェックする。【００８８】  マーカ有効性判断ステップ（ＳＴ０３）において、無効であると判断されたマーカ候補は、無効マーカ候補として無視され、のちにマーカ候補領域検出ステップ（ＳＴ０１）に再度進み、次のマーカ候補をチェックする。【００８９】  すべてのマーカ候補領域がチェックし終わったら、マーカ検出は終了し、位置計算や検出結果の利用などの別処理へと移行する。
【実施例３】
【００９０】実施例３として、図８に、実施例１と実施例２と同様にベクトル情報とトポロジー情報と併用したマーカの一例をしめす。ただし、実施例１と違い、図８のマーカは基準点をもたない。また、実施例２と違ってデータエンコード領域は一つであり、図８においては「実施例３におけるマーカ例のデータエンコード部（８）」として示されている。【００９１】  隣接および包括関係のみを表すことしかできないトポロジー情報だけでは、ビットの並び順序は決定できない。そこでデータをデコードするために、データエンコード部内部において、ビット情報領域から得られるビット列をソートしなければならないが、本実施例３の例では、各ビット情報領域の間のベクトルを利用することによりソートを行う。【００９２】  また、一般的にこのようなマーカが入力画像内にある場合、端にあるビット領域は、入力画像中の座標においても当然、端にあるので、それを利用して検出する手助けにできる。また、任意のビット情報領域から最も遠い距離にあるビット情報領域も、一般的に端となる。【００９３】  またデータエンコード部の端にある領域においては必ず全ての他のビット情報領域へのベクトルが同じ向きになり、端にない領域では必ず他のビット情報へのベクトルのうち反対の向きを指すベクトルが検出できる。【００９４】  上記のような方法のどれかにより端にある２点のマーカを取得でき、どちらかの端点の距離を使用してデコードされるデータのビット順をソートできるが、これだけではソート時にどちらの端が先頭ビットになり、どちらの端が終端ビットになるべきか決定できない。このような場合、以下の二つの方法をとってデータをエンコードすることにより解決できる。【００９５】  まず、データ自体に先頭ビットと終端ビットをあらわす情報を埋め込む。たとえば先頭ビットは必ず１、終端ビットは必ず０があらわれるものとし、複合された情報の先頭が０ならば、ビットの順序を反転する。これにより、ビットのソート順を正しく行う。【００９６】  もしくは、エンコードするデータを中心のビットを境に対象に配置する。たとえば１１０１という４ビットのデータをエンコードする際に８ビットを使用し、１１０１１０１１とするか７ビットを使用し１１０１０１１とエンコードする。これにより、どちらの方向からデータを読み込んでも同じデータを復号できる。また、このように対象に配置された対応するビット同士をチェックすることにより、より堅牢なデータの抽出が可能になる。【００９７】  また実施例３においても、実施例１および実施例２のようにマーカの検出を画像内により稀なトポロジー情報を利用することにより、マーカ検出を効率的に行うことができる。【００９８】  このように実施例３においてもマーカの検索においてトポロジー情報を利用し、データのエンコードとデコードにおいては幾何的な情報を併用する。【００９９】  本実施例３で述べられた本発明の応用の実施例における処理の具体例を図５に示す。本実施例１の具体例は、主に、トポロジー情報によるマーカ候補領域検出ステップ（ＳＴ０１）、ベクトル情報によるデータエンコード部ソートステップ（ＳＴ０２）、マーカ有効性判断ステップ（ＳＴ０３）、マーカ情報抽出ステップ（ＳＴ０４）の四つのステップからなる。【０１００】  マーカ候補領域検出ステップ（ＳＴ０１）では、既に以前の段階で入力画像から分析されて得られたトポロジー情報から、マーカ候補領域を一つ検出する。この際には、先に述べたような、マーカ領域のトポロジー的な特徴を利用して、候補領域を検出する。【０１０１】  ベクトル情報によるデータエンコード部ソートステップ（ＳＴ０２）では、各ビット情報領域間のベクトルを計算し、すべての他ビット情報領域へのベクトルの向きが同じであるものを、端にあるビット情報領域とする。２つの端点が検出されることになるので、ビット情報に向きデータを埋め込む場合は、先頭ビットを表す領域がビット情報領域の色から決定できる。その先頭ビットを表す領域から順に距離が近い順にビットをソートする。対象にビット情報を配置している場合は、向きを気にせずに任意の端からの距離に合わせてビットをソートする。このように各データエンコード部のビット情報を表す領域をソートする。このステップにおいては、トポロジー情報とベクトル情報が併用される。【０１０２】  マーカ有効性判断ステップ（ＳＴ０３）においては、さらに各ビット情報領域間のベクトルの長さや角度も利用して、有効なマーカであるかどうかを判断する。異常なベクトルの長さや角度が検出された場合、無効なマーカであるとして拒否する。【０１０３】  マーカ有効性判断ステップ（ＳＴ０３）において、有効であると判断されたマーカ候補は正しいマーカであるとして、マーカ情報抽出ステップ（ＳＴ０４）にすすみ、マーカから得られる情報を抽出する。そののち、マーカ候補領域検出ステップ（ＳＴ０１）に再度進み、次のマーカ候補をチェックする。【０１０４】  マーカ有効性判断ステップ（ＳＴ０３）において、無効であると判断されたマーカ候補は、無効マーカ候補として無視され、のちにマーカ候補領域検出ステップ（ＳＴ０１）に再度進み、次のマーカ候補をチェックする。【０１０５】  すべてのマーカ候補領域がチェックし終わったら、マーカ検出は終了し、位置計算や検出結果の利用などの別処理へと移行する。
【実施例４】
【０１０６】  実施例４として、図１０に、マーカを複数カードの上下にペアとして配置し、そのペアを利用してより効率的、正確に位置推定をできるようにした実施例を「実施例１の種別のマーカをカードの上下に配置した例（９）」、「実施例２の種別のマーカをカードの上下に配置した例（１０）」、「実施例３の種別のマーカをカードの上下に配置した例（１１）」として示す。これは、カードの上下あるマーカの位置情報を利用して、カードの３次元空間内での位置推定をより正確に行うのに役立つ。【０１０７】  図１０のうち、実施例２の種別のマーカをカードの上下に配置した例（１０）では、上下に配置されたマーカのトポロジカルな構造の違いを、配置位置を示す情報としても利用できる。【０１０８】  また、図１０において、上下に配置されたマーカの間の領域は使用されていないので、必要に応じて任意の図像を配置することができる。また、マーカ情報と併用して、その任意の図像における画像特徴点や図像とのパターン・マッチング結果を利用することによりマーカの一意性の向上やマーカ認識の堅牢性を向上させるために使用することができる。
【実施例５】
【０１０９】  実施例５として、ベクトルの角度情報をデータエンコード部のビット情報領域のソートに使用する例を示す。図１１は、この種別のマーカの一例を示し、図１２はその各部位の説明である。【０１１０】  図１１の四角形のマーカにおいては、図１２に示すように外部のデータエンコード部に配置された黒い四角形および白い四角形にそれぞれ０と１の１ビットがエンコードされる。隣接および包括関係のみを表すことしかできないトポロジー情報だけでは、ビットの並び順序は決定できないので、マーカ中心部から各データエンコード部への角度を各ビットのソートに利用し、データの埋め込みを行う。【０１１１】  図１２において、「実施例５におけるマーカ例の基準ベクトル取得部（点線内、中心部）（１２）」として図示されている、内部の中心部に配置された白い四角形を含む黒い正方形の領域は、基準ベクトル取得部として使用される。また図１２において「実施例５におけるマーカ例のデータエンコード部（点線外、周辺部）（１３）」は、それぞれの色に応じて０か１のビット情報を埋め込まれた、白もしくは黒い四角形であるビット情報領域を含む。【０１１２】  このマーカの中心部から、基準ベクトル取得部（１２）内部の黒い四角形の中心へのベクトルの角度を基準ベクトルとして取得する。その後、ビット情報領域から得られるビット列を、中心部から各ビット情報領域へのベクトルの角度と基準ベクトルからの角度の差を使用してソートする。ことによって、それぞれのビット情報領域に埋め込まれたビットの並び順を決定しデータをマーカから抽出する。【０１１３】  検出されたマーカから各領域の位置や大きさや重心や形状など、システムにたいしては既知の幾何的な情報を併用し、マーカの位置推定などを行うことができる。【０１１４】  このように実施例５においてもマーカの検索においてトポロジー情報を利用し、データのエンコードとデコードにおいて幾何的な情報を併用する。【０１１５】  実施例５においても、実施例１のようにマーカの検出を画像内により稀なトポロジー情報を利用することにより、マーカ検出を効率的に行うことができる。【０１１６】  実施例５の図１１の種別のマーカにおいても、上記のようなベクトルを利用したデータエンコード方法が正常に保たれる限り、おもにトポロジー情報を用いているという性質により、マーカ図像や形状は自由に設定できる。【０１１７】  本実施例５で述べられた、本発明の応用の実施例における処理の具体例を図１３に示す。実施例５の具体例は、主に、トポロジー情報によるマーカ候補領域検出ステップ（ＳＴ０１）、基準ベクトルからの角度を利用したソートステップ（ＳＴ０２）、マーカ有効性判断ステップ（ＳＴ０３）、マーカ情報抽出ステップ（ＳＴ０４）の四つのステップからな【０１１８】  マーカ候補領域検出ステップ（ＳＴ０１）では、既に以前の段階で入力画像から分析されて得られたトポロジー情報から、マーカ候補領域を一つ検出する。この際には、先に述べたような、マーカ領域のトポロジー的な特徴を利用して、候補領域を検出する。【０１１９】  基準ベクトルからの角度を利用したソートステップ（ＳＴ０２）では、マーカ候補領域検出ステップ（ＳＴ０１）で得られたマ��カ候補領域のうち、まず、基準ベクトル取得部マーカ中心部から内部の白い領域へのベクトルを基準ベクトルとして取得する。次にマーカ中心部から各データエンコード部内のビット情報領域へのベクトルをそれぞれ取得し、基準ベクトルとの角度を利用してソートする。これにより、データエンコード部にエンコードされたビット情報が順序づけられ、マーカ内にエンコードされたデータを抽出できる。このように、トポロジー情報と幾何的な情報が併用される。【０１２０】  マーカ有効性判断ステップ（ＳＴ０３）においては、さらにすでに取得されているベクトルの長さや角度などが、マーカの特徴と一致するかを判断して、有効であるかどうかを判断する。異常なベクトルの長さや角度が検出された場合、無効なマーカであるとして拒否する。【０１２１】  マーカ有効性判断ステップ（ＳＴ０３）において、有効であると判断されたマーカ候補は正しいマーカであるとして、マーカ情報抽出ステップ（ＳＴ０４）にすすみ、マーカから得られる情報を抽出する。そののち、マーカ候補領域検出ステップ（ＳＴ０１）に再度進み、次のマーカ候補をチェックする。【０１２２】  マーカ有効性判断ステップ（ＳＴ０３）において、無効であると判断されたマーカ候補は、無効マーカ候補として無視され、のちにマーカ候補領域検出ステップ（ＳＴ０１）に再度進み、次のマーカ候補をチェックする。【０１２３】  すべてのマーカ候補領域がチェックし終わったら、マーカ検出は終了し、位置計算や検出結果の利用などの別処理へと移行する。
【実施例６】
【０１２４】  実施例６として、ベクトルの角度情報をデータエンコード部のビット情報領域から得られるビット列のソートに使用する別の例を図１４に示す。図１４は、この種別のマーカの一例を示す。この図１３の種別のマーカでは内部に図像を配置することができる。図１５において、図１４のマーカの各部の説明を示す。【０１２５】  図１４の種別のマーカでは、図１５の「実施例６におけるマーカ例の基準ベクトル取得部（右上の白領域中の黒い四角形）（１４）」として示すように、基準ベクトルを取得するための領域は周辺部に埋め込まれている。またデータエンコード部も同様に「実施例６におけるマーカ例のデータエンコード部（周辺部）（１６）」に示すように、周辺部に埋め込まれている。【０１２６】  また、図１５「実施例６におけるマーカ例のデータエンコードを阻害しない性質をもつ任意の図像（中心部）（１５）」に示すように、本実施例６のデータエンコード手法を阻害しないような、基準ベクトル取得部ともデータエンコード部とも違ったトポロジー的な性質をもつものであれば、任意の図像を中心部に配置することができる。【０１２７】  図１５において、実施例６におけるマーカ例の基準ベクトル取得部（右上の白領域中の黒い四角形）（１４）のトポロジー的な特徴は、実施例６におけるマーカ例のデータエンコード部（周辺部）（１６）に埋め込まれた、白と黒の四角形の領域であるビット情報領域とは違っているため、トポロジー情報のみで容易に判別できる。【０１２８】  マーカ中心から基準ベクトル取得部（１４）へのベクトルを取得し基準ベクトルとする。【０１２９】  隣接および包括関係のみを表すことしかできないトポロジー情報だけでは、ビットの並び順序は決定できないので、ベクトル情報を利用して、ビット順序を決定する。基準ベクトルとの角度差をもとに、マーカ中心部からデータエンコード部内の、各ビット情報領域へのベクトルの角度をソートして、得られるビット列の順序を確定しマーカに埋め込まれたデータを抽出する。【０１３０】  検出されたマーカから各領域の位置や大きさや重心や形状など、システムにたいしては既知の幾何的な情報を併用し、マーカの位置推定などを行うことができる。【０１３１】  このように実施例６においてもマーカの検索においてトポロジー情報を利用し、データのエンコードとデコードにおいて幾何的な情報を併用する。【０１３２】  実施例６においても、実施例１のようにマーカの検出を画像内により稀なトポロジー情報を利用することにより、マーカ検出を効率的に行うことができる。【０１３３】  本発明の手法では、おもにトポロジー情報を用いてマーカ認識を行っているという性質により、実施例６の図１４の種別のマーカにおいても、上記のようなベクトルを利用したデータのエンコード方法が正常に保たれる限り、マーカ図像や形状は自由に設定できる。【０１３４】本実施例６で述べられた、本発明の応用の実施例における処理の具体例を図１６に示す。実施例６の具体例は、主に、トポロジー情報によるマーカ候補領域検出ステップ（ＳＴ０１）、基準ベクトルからの角度を利用したソートステップ（ＳＴ０２）、マーカ有効性判断ステップ（ＳＴ０３）、マーカ情報抽出ステップ（ＳＴ���４）の四つのステップからなる。【０１３５】  マーカ候補領域検出ステップ（ＳＴ０１）では、既に以前の段階で入力画像から分析されて得られたトポロジー情報から、マーカ候補領域を一つ検出する。この際には、先に述べたような、マーカ領域のトポロジー的な特徴を利用して、候補領域を検出する。【０１３６】  基準ベクトルからの角度を利用したソートステップ（ＳＴ０２）では、マーカ候補領域のうち、まずマーカ中心部から基準ベクトル取得部である「内部に黒い四角形を一つ含む白い四角形」へのベクトルを、基準ベクトルとして取得する。またマーカ中心部からビット情報を埋め込まれた「内部に黒い四角形を一つ含む白い四角形」であるビット情報領域への各ベクトルも同様に取得する。前者の基準ベクトルの角度を基準に、後者のビット情報領域へのベクトルの角度をソートして、各ビット情報の配置順を取得し、マーカに埋め込まれた情報を抽出する。このようにトポロジー情報と幾何的な情報が併用される。【０１３７】  マーカ有効性判断ステップ（ＳＴ０３）においては、さらにすでに取得されているベクトルの長さや角度などが、マーカの特徴と一致するかを判断して、有効であるかどうかを判断する。異常なベクトルの長さや角度が検出された場合、無効なマーカであるとして拒否する。【０１３８】  マーカ有効性判断ステップ（ＳＴ０３）において、有効であると判断されたマーカ候補は正しいマーカであるとして、マーカ情報抽出ステップ（ＳＴ０４）にすすみ、マーカから得られる情報を抽出する。そののち、マーカ候補領域検出ステップ（ＳＴ０１）に再度進み、次のマーカ候補をチェックする。【０１３９】  マーカ有効性判断ステップ（ＳＴ０３）において、無効であると判断されたマーカ候補は、無効マーカ候補として無視され、のちにマーカ候補領域検出ステップ（ＳＴ０１）に再度進み、次のマーカ候補をチェックする。【０１４０】  すべてのマーカ候補領域がチェックし終わったら、マーカ検出は終了し、位置計算や検出結果の利用などの別処理へと移行する。
【実施例７】
【０１４１】  実施例７では、マーカ図像の認識を、トポロジー情報に基づく手法と、画像の特徴点および幾何的な情報およびパターン・マッチング手法の併用により行う実施例を示す。トポロジー情報は、マーカ候補の絞り込みに主に使用され、その後、トポロジー情報とあわせて、マーカ全体やマーカの各部分の中心・重心・ベクトル・形状の幾何的な情報を利用してマーカの検出を試みる。それだけで十分マーカ候補の絞り込みが行われない場合には、画像の特徴点やパターン・マッチングの手法をさらに適用する。【０１４２】  図１７から図１９において、白黒に二値化されたマーカ図像の例として、図１７・実施例７におけるマーカ例その１（１７）、図１８・実施例７におけるマーカ例その２（１９）、図１９・実施例７におけるマーカ例その３（２１）の３つを示す。それぞれの図像に対応するマーカのトポロジカルな包括関係および隣接関係の情報を図としてあらわしたものを、図１７の実施例７におけるマーカ例その１のトポロジー情報をあらわしたグラフ（１８）、図１８の実施例７におけるマーカ例その２のトポロジー情報をあらわしたグラフ（２０）、図１９の実施例７におけるマーカ例その３のトポロジー情報をあらわしたグラフ（２２）として示す。これらを本実施例での検出候補マーカの例とする。【０１４３】  本実施例７では、まず、入力画像から得られたトポロジー情報を利用してマーカ候補を検索する。このとき、登録されているマーカのトポロジー情報のどれかと一致するものをマーカ候補として扱う。一致するマーカ候補が一つである場合、それを検出したマーカとしてあつかう。【０１４４】  しかし、例えば図１８・実施例７におけるマーカ例その２（１９）が画像内に存在し、マーカ候補として検出されたとする。このとき、そのトポロジー情報は、図１８の実施例７におけるマーカ例その２のトポロジー情報をあらわしたグラフ（２０）として示される。よって、このトポロジー情報が、図１７の実施例７におけるマーカ例その１のトポロジー情報をあらわしたグラフ（１８）とは異なっているため、実施例７におけるマーカ例その１（１７）は、マーカ候補から外れる。しかし、まだ図１９の実施例７におけるマーカ例その３のトポロジー情報をあらわしたグラフ（２２）とトポロジー情報が同じであるので、既存のトポロジー情報のみに基づく手法では区別がつかず、検出マーカがひとつに確定できない。【０１４５】  このような場合、本発明で用いる手法では、マーカ全体やマーカの各部分の中心・重心・ベクトル・形状の幾何的な情報も使用するとともに、同時に画像の特徴点の情報を用いる手法やパターン・マッチング手法を併用して、同じトポロジー情報を持つマーカ間でも区別を行う。【０１４６】  まず、マーカ全体やマーカの各部分の領域における、中心・重心・ベクトル・形状の幾何的な情報で、先ほど得られた同じトポロジー情報を持つマーカ間でのさらに絞り込みを行う。このような画像内のある領域に関する幾何的な情報の取得方法はすでに一般に広く知られているものを用いる。【０１４７】  本手法では、そのように取得された、マーカ候補領域からそれぞれの部分及び全体の中心・重心・ベクトル・形状の幾何的な情報のうち全て、もしくは必���なものとその組み合わせを利用して、検出すべきマーカ集合内のマーカと、それぞれと個別に、また組み合わせて相関度を比較して、一致度の高いもののみを絞り込む。【０１４８】  たとえば、四角形の輪郭をしたマーカがあり、その輪郭がシステムに対して既知である場合、輪郭を取得したのち、入力画像内のマーカ輪郭の各頂点の位置を利用して、入力画像のマーカ輪郭から３次元空間上のマーカ座標を推定し、正面からマーカをみたような２次元平面への変換行列を取得することができる。これにより傾いたマーカの画像でも取得した変換行列により透視変換が可能である。このような既知の形状や座標の情報を利用して、傾いて撮影されているマーカを２次元平面上で真正面から見ている形に透視変換する手法は、既に既存のマーカ認識手法で広くつかわれているものである。【０１４９】  一般に正方形などの形状にマーカの形状を限定している手法では、正方形の四頂点などを使用して、このような２次元平面への変換行列を得ている。本手法でもこの手法は適用できる。【０１５０】  また、本手法では、まずトポロジー情報によりマーカ候補を絞っているため、マーカ候補に残っているマーカ群のそれぞれの形状は既知となり、このようなマーカを二次元平面に配置し真正面から見た形へと、入力画像中のマーカ画像を透視変換するための行列は既存の手法を利用して容易に得られる。これによって、全てのマーカ形状を正方形に限定せずに、単に形状に関係なく得られるトポロジー情報から、該当するトポロジー情報を持つマーカ候補群を選ぶことができ、それらマーカ候補群のもつマーカ形状はそれぞれシステムに対して既知となるので、その形状を使用して２次元平面への変換行列を得てもよい。当然この場合は、その形状は、変換行列が得られるように設計されているものでなある必要がある。たとえば、簡単な例では、長方形や五角形などでもかまわない。【０１５１】  各領域の占める領域間の重心から得られるベクトルを利用することにより、ある程度のマーカの入力画像内での回転角度が取得できる。この角度を利用して、マーカ中心から全領域へのベクトルを足すことによって得られるベクトルを、マーカの向きの基準として扱う。これを変換行列を得るときに、追加的な情報として、マーカの入力画像内での向きの推定に役立て、２次元平面への変換行列の取得に役立てる。【０１５２】  本手法では、上のようにマーカ図像を２次元に透視変換するための変換行列を取得したのち、さらに検出したいマーカ候補群の中心・重心・ベクトル・形状の幾何的な情報を２次元平面に直した形で復元できる。【０１５３】  そのように変換された各領域の重心の位置を比較し、一致度がより高いものを検出したいマーカ候補群のなかから、検出するマーカ候補として残し、明らかに重心の位置が違うものなどは候補としてあつかわないことにより、絞り込みを行える。これには、互いに最近傍にある重心をペアとして各距離の誤差を得ることができ、この誤差が明らかに大きすぎるものは候補からはずす手法を使用する。また全体の誤差がすくなくても、異常な誤差をもつ重心のペアがある場合は、そのマーカも候補からはずす。【０１５４】  この時点でまだ絞込みがたりなければ、さらに他の幾何��な情報を用いて、マーカ候補を絞り込んで、検出マーカを確定を試みる。【０１５５】  このとき、ベクトルの向きとマーカ候補領域のうち任意の領域を、現在残っているマーカ候補と向きの基準を合わせ、該当領域の形状を比較することにより、あまりに形状が違っているものは、候補からはずすことができる。【０１５６】  このように、本手法では、トポロジー情報にくわえて中心・重心・ベクトル・形状の幾何的な情報を併用する。【０１５７】  また、それだけでなく各幾何的な情報の組み合わせを使用してマーカの絞り込みを行う。そのさい、各幾何的な情報の重みづけは、実際に使用される環境や、マーカの図像によって変えることができる。たとえば、各領域の輪郭は大きく違っているが重心はほぼ同じようなマーカが複数あり、これらの間でマーカを区別する必要がある際は、形状の相関の度合いを大きく重みづけて一致度を評価する。【０１５８】  この段階で一つの検出マーカ候補に絞れたときは、そのマーカが検出されたとする。まだ複数のマーカが候補に残っている場合、別手法をさらに併用しての候補の絞り込みに進む。【０１５９】  幾何的な情報のみで絞り込みが十分でなかった場合、画像の特徴点もしくはパターン・マッチングを行い、候補をさらに絞り込む。これにより、よりもっともマーカ候補と一致度が高いマーカを、検出マーカとしてあつかう。【０１６０】  上記の手法で見つかった検出マーカがマーカとしての有効度が十分でない場合、検出マーカとしては扱わず、十分有効であるもののみを検出マーカとしてあつかう。【０１６１】  検出マーカに関して今まで得られている情報や入力画像のマーカ領域から得られる情報を利用して、マーカの２次元平面や３次元空間内での位置推定などを行うことができる。【０１６２】  本実施例７で述べられた、本発明の応用の実施例における処理の具体例を図２０に示す。実施例７の具体例は、主に、トポロジー情報によるマーカ候補領域検出ステップ（ＳＴ０１）、トポロジー情報によるマーカ候補絞り込みステップ（ＳＴ０２）、トポロジー情報によるマーカ検出ステップ（ＳＴ０３）、幾何的な情報によるマーカ検出ステップ（ＳＴ０４）、パターン・マッチングによるマーカ検出ステップ（ＳＴ０５），特徴点によるマーカ検出ステップ（ＳＴ０６）、マーカの情報抽出ステップ（ＳＴ０７）の７つのステップからなる。【０１６３】マーカ候補領域検出ステップ（ＳＴ０１）では、既に以前の段階で入力画像から分析されて得られたトポロジー情報から、マーカ候補領域を一つ検出する。この際には、先に述べたような、マーカ領域のトポロジー的な特徴を利用して、候補領域を検出する。【０１６４】  トポロジー情報によるマーカ候補絞り込みステップ（ＳＴ０２）では、マーカ候補領域検出ステップ（ＳＴ０１）で得られた候補領域と、システムには既知の検出すべきマーカ候補のトポロジー情報を比較し、関係のないマーカ候補を検出対象除外し、トポロジー情報が一致するものだけを絞り込んで検出対象マーカとして残す。【０１６５】  トポロジー情報によるマーカ検出ステップ（ＳＴ０３）では、絞り込まれた検出対象マーカとトポロジー情報が一致するマーカがある場合、すでに一つに候補が絞られ検出されたマーカが確定したのなら、マーカの情報抽出ステップ（ＳＴ０７）とすすむ。候補が未確定の状態であれば、次に幾何的な情報によるマーカ検出ステップ（ＳＴ０４）にすすむ。【０１６６】  幾何的な情報によるマーカ検出ステップ（ＳＴ０４）では、マーカ全体やマーカの各部分の中心・重心・ベクトル・形状を含む幾何的な情報を使用して、現在のマーカ候補の中に、十分一致するものがあるかを調べる。この段階で幾何的な特徴が十分一致したマーカ候補がある場合には、それを検出マーカとして確定し、マーカの情報抽出ステップ（ＳＴ０７）とすすむ。そうでない場合には、一致度が低く、明らかに対象でないマーカを候補の集合から除外し、パターン・マッチングによるマーカ検出ステップ（ＳＴ０５）へと進む。【０１６７】  パターン・マッチングによるマーカ検出ステップ（ＳＴ０５）では、検出されたマーカ候補領域と、パターン・マッチング手法をもちい、絞り込み済みのマーカ候補集合との比較を行い、マーカ確定を試みる。この段階で十分一致したマーカ候補がある場合には、それを検出マーカとして確定し、マーカの情報抽出ステップ（ＳＴ０７）とすすむ。そうでない場合には、一致度が低く、明らかに対象でないマーカを候補の集合から除外し、特徴点によるマーカ検出ステップ（ＳＴ０６）へと進む。【０１６８】  特徴点によるマーカ検出ステップ（ＳＴ０６）は、マーカ候補領域内の画像特徴点とマーカ候補集合のそれぞれの特徴点を比較し、マーカ確定を試みる。この段階で十分一致したマーカ候補がある場合には、それを検出マーカとして確定し、マーカの情報抽出ステップ（ＳＴ０７）とすすむ。そうでない場合は、次のマーカ候補領域のチェックへと進む。【０１６９】  マーカ情報抽出ステップ（ＳＴ０７）においては、現在までに得られているマーカに関する情報から後の利用手段で必要な情報を抽出する。これには位置推定のための情報、マーカ種別、一致度など現在までに得られた情報がすべて含まれる。【０１７０】  すべてのマーカ候補領域がチェックし終わったら、マーカ検出は終了し、位置計算や検出結果の利用などの別処理へと移行する。【０１７１】  なお、本発明の技術範囲は上記の基本的な利用形態、実施例１から実施例７までに限定されるものではなく、本発明の趣旨を逸脱しない範囲において種々の変更を加えることが可能である。
【符号の説明】
【０１７２】１  実施例１におけるマーカ例の基準部
２  実施例１におけるマーカ例のデータエンコード部
３  実施例１図３のマーカ例における基準部のトポロジー情報を表す部位（点線内）
４  実施例１図３のマーカ例におけるデータエンコード部のうち黒いビット情報領域のトポロジー情報を表す部位（点線内）
５  実施例１図３のマーカ例におけるデータエンコード部のうち白いビット情報領域のトポロジー情報を表す部位（点線内）
６  実施例２におけるマーカ例のデータエンコード部▲１▼
７  実施例２におけるマーカ例のデータエンコード部▲２▼
８  実施例３におけるマーカ例のデータエンコード部
９  実施例１の種別のマーカをカードの上下に配置した例
１０  実施例２の種別のマーカをカードの上下に配置した例
１１  実施例３の種別のマーカをカードの上下に配置した例
１２  実施例５におけるマーカ例の基準ベクトル取得部（点線内、中心部）
１３  実施例５におけるマーカ例のデータエンコード部（点線外、周辺部）
１４  実施例６におけるマーカ例の基準ベクトル取得用領域（右上の白領域中の黒い四角形）
１５  実施例６におけるマーカ例のデータエンコードを阻害しない性質をもつ任意の図像（中心部）
１６  実施例６におけるマーカ例のデータエンコード部（周辺部）
１７  実施例７におけるマーカ例その１
１８  図１７の実施例７におけるマーカ例その１のトポロジー情報をあらわしたグラフ
１９  実施例７におけるマーカ例その２
２０  図１８の実施例７におけるマーカ例その２のトポロジー情報を表したグラフ
２１  実施例７におけるマーカ例その３
２２  図１９の実施例７におけるマーカ例その３のトポロジー情報を表したグラフ
【図１】
2011030168.tif 000003
【図２】
2011030168.tif 000004
【図３】
2011030168.tif 000005
【図４】
2011030168.tif 000006
【図５】
2011030168.tif 000007
【図６】
2011030168.tif 000008
【図７】
2011030168.tif 000009
【図８】
2011030168.tif 000010
【図９】
2011030168.tif 000011
【図１０】
2011030168.tif 000012
【図１１】
2011030168.tif 000013
【図１２】
2011030168.tif 000014
【図１３】
2011030168.tif 000015
【図１４】
2011030168.tif 000016
【図１５】
2011030168.tif 000017
【図１６】
2011030168.tif 000018
【図１７】
2011030168.tif 000019
【図１８】
2011030168.tif 000020
【図１９】
2011030168.tif 000021
【図２０】
2011030168.tif 000022