(57)【要約】【課題】埋め込み型メディアマーカ（ＥＭＭ）識別に基づいて画像を識別する方法、装置およびプログラムを提供する。【解決手段】第１の粗い比較３０１と、第２の細かな比較３０２とを含む、階層的比較が使用される。第１の粗い比較３０１では、ＥＭＭを有する画像を、データベース内の画像と、低い分解能において比較する。結果は、第１の粗い比較３０１より高い分解能において比較を行う、第２の細かな比較３０２に入力される。この階層的比較アプローチを利用することによって、より少ない誤検出で画像を識別することが可能になる。【選択図】図３
2012230676.tif 000002
【特許請求の範囲】
【請求項１】
受信手段により、インデックス標識を含む第１の画像を受信し、
第１の比較手段により、前記第１の画像と、インデックス付き候補画像との、第１の比較を行い、前記第１の比較を行うことは、前記第１の画像の第１の表現を構築することを含み、
前記第１の比較手段により、前記第１の比較に基づいて、前記インデックス付き候補画像の、第１のランク付けを行い、
前記第１の比較手段により、前記第１のランク付けに基づいて、前記インデックス付き候補画像から選択を行い、
第２の比較手段により、前記第１の画像と、前記選択されたインデックス付き候補画像との、第２の比較を行い、前記第２の比較を行うことは、前記第１の画像の前記第１の表現より高い分解能を有する、前記第１の画像の第２の表現を作成することを含み、
前記第２の比較手段により、前記第２の比較に基づいて、前記選択されたインデックス付き候補画像の、第２のランク付けを行い、
前記第２の比較手段により、前記第２のランク付けに基づいて、インデックス付き画像を識別すること
を含む、インデックス付き画像を識別する方法。
【請求項２】
前記第２の比較を行うことは、
前記インデックス標識から、埋め込み型メディアマーカ（ＥＭＭ）の特徴を抽出し、
前記ＥＭＭの配向に基づいて、前記第１の画像の優先配向を決定し、
前記インデックス付き候補画像のぞれぞれを、グリッドを使用して表現し、
前記ＥＭＭを含む前記画像の前記優先配向を、前記第２の表現を使用して表現し、
前記第２の表現と、前記インデックス付き候補画像のそれぞれの前記グリッドとの間で、マッチングする対応関係を識別すること
を含み、前記第２のランク付けは、前記識別されたマッチングする対応関係に基づいて、前記インデックス付き候補画像のうちの少なくとも１つのそれぞれにスコア付けすることを更に含む、請求項１に記載の方法。
【請求項３】
前記マッチングする対応関係を識別することは、
前記第２の表現に含まれる特徴を、前記取得された画像のそれぞれの前記グリッドに含まれる、対応する特徴と比較すること
を更に含み、前記対応する特徴は、前記優先配向に基づいて平行移動を行うことによって決定される、請求項２に記載の方法。
【請求項４】
前記第１の比較を行うことは、
前記インデックス付き候補画像のそれぞれを、グリッドを使用して表現し、
前記第１の表現のグリッド位置と、データベース画像のそれぞれの前記グリッドとの間で、マッチングする対応関係の数を識別すること
を含み、前記第１のランク付けは、マッチングする対応関係の前記数に基づく、請求項１に記載の方法。
【請求項５】
前記インデックス付き候補画像のそれぞれを、グリッドを使用して表現することは、
前記データベース画像のためのインデックスファイルを利用すること
を含み、前記インデックスファイル内のエントリは、前記データベース画像のそれぞれについて、前記グリッド内の各特徴の属性を対応付ける、請求項４に記載の方法。
【請求項６】
前記第１の比較を行うことは、
前記インデックスファイル内のエントリを、前記第１の表現と比較すること
を更に含む、請求項５に記載の方法。
【請求項７】
インデックス標識を含む第１の画像を受信するカメラと、
前記受信された第１の画像を第１の表現として表現する、第１の比較ユニットであって、前記第１の画像と、データベース画像との、第１の比較を行い、前記第１の比較に基づいて、インデックス付き候補画像をランク付けすることを含む第１のランク付けを行い、前記第１のランク付けに基づいて、前記インデックス付き候補画像から選択を行う、第１の比較ユニットと、
前記受信された第１の画像を、前記第１の表現より高い分解能を有する、前記第１の画像の第２の表現として表現する、第２の比較ユニットであって、前記第１の画像と、前記選択された画像のそれぞれとの、第２の比較を行い、前記第２の比較に基づいて、前記選択された画像をランク付けすることを含む第２のランク付けを行い、前記第２のランク付けに基づいて、前記第１の画像に対応する、インデックス付き画像を識別する、第２の比較ユニットと
を備える、装置。
【請求項８】
前記第２の比較を行うことは、
前記インデックス標識から、埋め込み型メディアマーカ（ＥＭＭ）の特徴を抽出し、
前記ＥＭＭの配向に基づいて、前記第１の画像の優先配向を決定し、
前記インデックス付き候補画像のぞれぞれを、グリッドを使用して表現し、
前記ＥＭＭを含む前記画像の前記優先配向を、前記第２の表現を使用して表現し、
前記第２の表現と、前記インデックス付き候補画像のそれぞれの前記グリッドとの間で、マッチングする対応関係を識別すること
を更に含み、前記第２のランク付けは、前記識別されたマッチングする対応関係に基づいて、前記インデックス付き候補画像のうちの少なくとも１つのそれぞれをスコア付けすることを更に含む、請求項７に記載の装置。
【請求項９】
前記マッチングする対応関係を識別することは、
前記第２の表現に含まれる特徴を、前記選択された画像のそれぞれの前記グリッドに含まれる、対応する特徴と比較すること
を更に含み、前記対応する特徴は、前記優先配向に基づいて平行移動を行うことによって決定される、請求項８に記載の装置。
【請求項１０】
前記第１の比較を行うことは、
前記候補となるインデックス付き画像のそれぞれを、グリッドを使用して表現し、
前記第１の表現のグリッド位置と、前記データベース画像のそれぞれの対応するグリッドとの間の、マッチング属性の数を識別すること
を含み、前記第１のランク付けは、マッチング属性の前記数に基づく、請求項７に記載の装置。
【請求項１１】
前記インデックス付き候補画像のそれぞれを、グリッドを使用して表現することは、
前記インデックス付き候補画像のためのインデックスファイルを利用すること
を含み、前記インデックスファイル内のエントリは、前記データベース画像のそれぞれについて、前記グリッド内の各特徴の属性を対応付ける、請求項１０に記載の装置。
【請求項１２】
前記第１の比較を行うことは、
前記インデックスファイル内のエントリを、前記第１の表現と比較すること
を更に含む、請求項１１に記載の装置。
【請求項１３】
コンピュータに、インデックス付き画像の識別のためのプロセスを実行させるプログラムであって、前記プロセスは、
インデックス標識を含む第１の画像を受信し、
前記第１の画像と、インデックス付き候補画像との、第１の比較を行い、前記第１の比較を行うことは、前記第１の画像の第１の表現を構築することを含み、
前記第１の比較に基づいて、前記インデックス付き候補画像の、第１のランク付けを行い、
前記第１のランク付けに基づいて、インデックス付き候補画像から選択を行い、
前記第１の画像と、前記選択したインデックス付き候補画像との、第２の比較を行い、前記第２の比較を行うことは、前記第１の画像の前記第１の表現より高い分解能を有する、前記第１の画像の第２の表現を作成することを含み、
前記第２の比較に基づいて、前記選択したインデックス付き候補画像の、第２のランク付けを行い、
前記第２のランク付けに基づいて、インデックス付き画像を識別すること
を含む、プログラム。
【請求項１４】
前記第２の比較を行うことは、
前記インデックス標識から、埋め込み型メディアマーカ（ＥＭＭ）の特徴を抽出し、
前記ＥＭＭの配向に基づいて、前記第１の画像の優先配向を決定し、
前記インデックス付き候補画像のぞれぞれを、グリッドを使用して表現し、
前記ＥＭＭを含む前記画像の前記優先配向を、前記第２の表現を使用して表現し、
前記第２の表現と、前記インデックス付き候補画像のそれぞれの前記グリッドとの間で、マッチングする対応関係を識別すること
を含み、前記第２のランク付けは、識別されたマッチングする対応関係に基づいて、前記インデックス付き候補画像のうちの少なくとも１つのそれぞれをスコア付けすることを更に含む、請求項１３に記載のプログラム。
【請求項１５】
前記マッチングする対応関係を識別することは、
前記第２の表現に含まれるピクセルを、前記インデックス付き候補画像のそれぞれの前記グリッドに含まれる、対応する特徴と比較すること
を更に含み、前記対応する特徴は、前記優先配向に基づいて平行移動を行うことによって決定される、請求項１４に記載のプログラム。
【請求項１６】
前記第１の比較を行うことは、
前記インデックス付き候補画像のそれぞれを、グリッドを使用して表現し、
前記第１の表現のグリッド位置と、データベース画像のそれぞれの前記グリッドとの間で、マッチングする対応関係の数を識別すること
を含み、前記第１のランク付けは、マッチングする対応関係の前記数に基づく、請求項１３に記載のプログラム。
【請求項１７】
前記インデックス付き候補画像のそれぞれを、グリッドを使用して表現することは、
前記データベース画像のためのインデックスファイルを利用すること
を含み、前記インデックスファイル内のエントリは、前記データベース画像のそれぞれの前記グリッド内の各ピクセルの属性をマッピングする、請求項１６に記載のプログラム。
【請求項１８】
前記第１の比較を行うことは、
前記インデックスファイル内のエントリを、前記第１の表現と比較すること
を更に含む、請求項１７に記載のプログラム。
【請求項１９】
前記プロセスは、前記インデックスファイル内の前記エントリとの比較のために、前記第１の表現のインデックス表現を作成することを更に含む、請求項１８に記載のプログラム。
【請求項２０】
前記特徴を比較することは、
前記インデックス付き候補画像のためのインデックスファイルを利用し、ここで、前記インデックスファイル内のエントリは、前記データベース画像のそれぞれの前記グリッド内の各特徴の属性をマッピングし、
前記第２の表現を、前記インデックスファイルとの比較のためのインデックス表現で表現し、
前記インデックスファイル内のエントリを、前記インデックス表現と比較すること
を含む、請求項１６に記載のプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、一般に、画像識別のための装置およびプログラムに関し、特に、埋め込み型メディアマーカ（Ｅｍｂｅｄｄｅｄ  Ｍｅｄｉａ  Ｍａｒｋｅｒ）（ＥＭＭ）を含む画像を識別するための装置およびプログラムに関する。
【背景技術】
【０００２】
カメラ付き携帯電話などの装置を介して、動的なメディアを静的な紙ドキュメントとリンクする技術は、マルチメディア・エンハンスト・ブック（ｍｕｌｔｉｍｅｉａ  ｅｎｈａｎｃｅｄ  ｂｏｏｋｓ）及びマルチメディア・アドバーティスメント・オン・ペーパー（ｍｕｌｔｉｍｅｄｉａ  ａｄｖｅｒｔｉｓｅｍｅｎｔ  ｏｎ  ｐａｐｅｒ）などの、多くの興味深い応用例に適用可能である。例えば、２次元バーコードが、そのような静的な紙ドキュメント上で使用可能であり、これは、最近のカメラ付き携帯電話によって容易に認識することが可能である。しかし、バーコードは、視覚的に邪魔になる傾向があり、特定のドキュメントコンテンツと関連付けられる場合、ドキュメントのレイアウトの妨げになりがちである。
【０００３】
他のシステムとして、識別処理がドキュメントコンテンツに依存するものがある。例えば、ドキュメント内の視覚的特徴を、ドキュメントを識別するために利用することが可能である。ドキュメントの語境界ボックス（静的な紙ドキュメントの１つ以上の語を囲むボックス）に基づいた特徴を利用することによって、メディアを、静的な紙ドキュメント上のテキストにリンクすることも可能である。しかし、これらの方法では、静的な紙ドキュメント内のどのコンテンツがメディア情報にリンクする可能性があるかについての指針を提供しなければ、良好な精度及びスケーラビリティを達成できない。具体的には、そのような指針をユーザに十分に提供していない場合、当てもなく撮影されたクエリ画像は識別精度の低下をもたらす様々なひずみを含み得る。そこで、従来のシステムでは、適切な識別のために、ドキュメントページの全体に対して特徴抽出およびインデックス付けを行う必要があり、それにより、データセットが大きい場合には大量の時間及びメモリコストが発生していた。
【０００４】
これらの問題に対処するために、埋め込み型メディアマーカ（ＥＭＭ）などの、インデックス標識（ｉｎｄｅｘ  ｉｎｄｉｃａｔｏｒｓ）が、識別の目的のために利用されてきた。ＥＭＭは、メディア情報とリンクされる位置において紙ドキュメント上に印刷されたほぼ透明のマーカである。ＥＭＭは、ハイパーリンクと類似しており、リンクの存在を示す。ユーザは、関連するデジタルメディアを閲覧すべく、ドキュメント上にオーバーレイされた、ＥＭＭ表示パッチ（ＥＭＭが配置された部位）を、例えばカメラ付き携帯電話を用いて撮影する。ＥＭＭ表示パッチがカメラ付き携帯電話によって撮影されたら、撮影された画像を、識別のために、ＥＭＭ又はインデックス標識のデータベースと比較して、これらのＥＭＭ又はインデックス標識を適切なデジタルメディアを取得するために利用してもよい。
【０００５】
図１は、図１（ａ）に示すように右上隅１０１にＥＭＭがオーバーレイされた例示的ドキュメント１００を用いた、ＥＭＭを使用する従来のプロセスのシーケンスを示す。ユーザは、図１（ｂ）に示すように、例示的ドキュメント上の、ＥＭＭ表示パッチのクローズアップ画像１０２を撮影する。ＥＭＭを使用することによって、ＥＭＭ表示パッチのみ、特徴抽出およびインデックス付けをすればよい。これにより、特徴抽出時間、及びメモリ使用量を大幅に削減することが出来、また、ノイズを多く含む、ＥＭＭの外側のコンテンツの特徴が除外されることによって、精度を向上させることが出来る。
【０００６】
続いて、識別段階において、ＥＭＭは、ＥＭＭ標示領域（ＥＭＭ表示パッチが配置された領域）を撮影するようユーザをガイドすることが可能であり、これにより、図１（ｃ）に示すような、ひずみが大幅に削減されたクエリ画像１０３がもたらされる。適切なクエリ画像が取得された後、ＥＭＭ識別の次の実行処理は、カメラ付き携帯電話で撮影されたクエリ画像を、データセット内でインデックス付けされた、オリジナルのＥＭＭ表示パッチの一つとして認識することであり、これにより、図１（ｄ）に示すように、関連するメディアが取得され、携帯電話１０４上で再生される。
【先行技術文献】
【非特許文献】
【０００７】
【非特許文献１】Ｚｈｏｎｇ  Ｗｕらによる、「大域部分的複製ウェブ画像検索のための特徴バンドリング（Ｂｕｎｄｌｉｎｇ  Ｆｅａｔｕｒｅｓ  ｆｏｒ  Ｌａｒｇｅ  Ｓｃａｌｅ  Ｐａｒｔｉａｌ−Ｄｕｐｌｉｃａｔｅ  Ｗｅｂ  Ｉｍａｇｅ  Ｓｅａｒｃｈ）」、ＣＶＰＲ’０９議事録、２００９年６月、８頁
【非特許文献２】Ｓｖｅｔｌａｎａ  Ｌａｚｅｂｎｉｋらによる、「特徴バッグを越えて：自然背景カテゴリ認識のための空間ピラミッドマッチング（Ｂｅｙｏｎｄ  Ｂａｇｓ  ｏｆ  Ｆｅａｔｕｒｅｓ：  Ｓｐａｔｉａｌ  Ｐｙｒａｍｉｄ  Ｍａｔｃｈｉｎｇ  ｆｏｒ  Ｒｅｃｏｇｎｉｚｉｎｇ  Ｎａｔｕｒａｌ  Ｓｃｅｎｅ  Ｃａｔｅｇｏｒｉｅｓ）」、ＣＶＰＲ’０６議事録、２００６年１０月９日、８頁
【非特許文献３】Ｏｎｄｒｅｊ  Ｃｈｕｍらによる、「幾何学的最小ハッシング：干し草の中の（太い）針を探す方法（Ｇｅｏｍｅｔｒｉｃ  ｍｉｎ−Ｈａｓｈｉｎｇ：  Ｆｉｎｄｉｎｇ  ａ  （Ｔｈｉｃｋ）  Ｎｅｅｄｌｅ  ｉｎａ  Ｈａｙｓｔａｃｋ）」、ＣＶＰＲ’０９議事録、２００９年５月５日、１〜８頁
【非特許文献４】Ｈｅｒｖｅ  Ｊｅｇｏｕらによる、「大域画像検索のためのハミング包含および弱幾何学的一貫性（Ｈａｍｍｉｎｇ  Ｅｍｂｅｄｄｉｎｇ  ａｎｄ  Ｗｅａｋ  Ｇｅｏｍｅｔｒｉｃ  Ｃｏｎｓｉｓｔｅｎｃｙ  ｆｏｒ  Ｌａｒｇｅ  Ｓｃａｌｅ  Ｉｍａｇｅ  Ｓｅａｒｃｈ）」、ＥＣＣＶ’０８議事録、２００８年１０月、１〜１５頁
【非特許文献５】Ｄａｖｉｄ  Ｇ．Ｌｏｗｅによる、「スケール不変的キーポイントからの特有な画像特徴（Ｄｉｓｔｉｎｃｔｉｖｅ  Ｉｍａｇｅ  Ｆｅａｔｕｒｅｓ  Ｆｒｏｍ  Ｓｃａｌｅ−Ｉｎｖａｒｉａｎｔ  Ｋｅｙｐｏｉｎｔｓ）」、２００４年１月５日、１〜２８頁、ＩＪＣＶ
【非特許文献６】Ｊａｍｅｓ  Ｐｈｉｌｂｉｎらによる、「大量語彙および高速空間マッチングによる対象検索（Ｏｂｊｅｃｔ  Ｒｅｔｒｉｅｖａｌ  ｗｉｔｈ  Ｌａｒｇｅ  Ｖｏｃａｂｕｌａｒｉｅｓ  ａｎｄ  Ｆａｓｔ  Ｓｐａｔｉａｌ  Ｍａｔｃｈｉｎｇ）」、ＣＶＰＲ’０７議事録、２００７年７月１６日
【非特許文献７】Ｑｉｏｎｇ  Ｌｉｕらによる、「埋め込み型メディアマーカ：マルチメディアと紙とを繋ぐ（Ｅｍｂｅｄｄｅｄ  Ｍｅｄｉａ  Ｍａｒｋｅｒ：  Ｌｉｎｋｉｎｇ  Ｍｕｌｔｉｍｅｄｉａ  ｔｏ  Ｐａｐｅｒ）」、ＡＣＭ  Ｍｕｌｔｉｍｅｄｉａ’１０議事録、２０１０年１０月、２頁
【非特許文献８】Ｑｉｏｎｇ  Ｌｉｕらによる、「埋め込み型メディアマーカ：関連付けられたメディアを指標する紙上のマーカ（Ｅｍｂｅｄｄｅｄ  Ｍｅｄｉａ  Ｍａｒｋｅｒｓ：  Ｍａｒｋｓ  ｏｎ  Ｐａｐｅｒ  ｔｈａｔ  Ｓｉｇｎｉｆｙ  Ａｓｓｏｃｉａｔｅｄ  Ｍｅｄｉａ）」、ＡＣＭ議事録、２００９年４月４日〜９日、１〜１０頁
【非特許文献９】Ｊｏｓｅｆ  Ｓｉｖｉｃらによる、「ビデオＧｏｏｇｌｅ：ビデオ対象マッチングに対する文章検索アプローチ（Ｖｉｄｅｏ  Ｇｏｏｇｌｅ：  Ａ  Ｔｅｘｔ  Ｒｅｔｒｉｅｖａｌ  Ａｐｐｒｏａｃｈ  ｔｏ  Ｏｂｊｅｃｔ  Ｍａｔｃｈｉｎｇ  ｉｎ  Ｖｉｄｅｏｓ）」、Ｉｎｔｅｒｎａｔｉｏｎａｌ  Ｃｏｎｆｅｒｅｎｃｅ  ｏｎ  Ｃｏｍｐｕｔｅｒ  Ｖｉｓｉｏｎ議事録、ＩＥＥＥ  Ｃｏｍｐｕｔｅｒ  Ｓｏｃｉｅｔｙ、２００３年、１〜８頁、２巻
【非特許文献１０】Ｂａｒｃｏｄｅ、Ｗｉｋｉｐｅｄｉａ、最新更新日：４月２日２０：３６、にＷｉｋｉｍｅｄｉａ  Ｆｏｕｎｄａｔｉｏｎ，Ｉｎｃ、アクセス日：２０１１年４月１２日、＜ｈｔｔｐ：／／ｅｎ．ｗｉｋｉｐｅｄｉａ．ｏｒｇ／ｗｉｋｉ／Ｂａｒｃｏｄｅ＞
【非特許文献１１】Ｂｅｒｎａ  Ｅｒｏｌらによる、「ＨＯＴＰＡＰＥＲ：携帯電話を用いて紙上マルチメディアインタラクションを行う方法（ＨＯＴＰＡＰＥＲ：  Ｍｕｌｔｉｍｅｄｉａ  Ｉｎｔｅｒａｃｔｉｏｎ  ｗｉｔｈ  Ｐａｐｅｒ  ｕｓｉｎｉｇ  Ｍｏｂｉｌｅ  Ｐｈｏｎｅｓ）」、Ｍｕｌｔｉｍｅｄｉａ’０８議事録、２００８年１０月２７日〜１１月１日、３９９〜４０８頁、バンクーバー、カナダ
【非特許文献１２】「ＳｎａｐＴｅｌｌ−視覚的製品検索（ＳｎａｐＴｅｌｌ−Ｖｉｓｕａｌ  Ｐｒｏｄｕｃｔ  Ｓｅａｒｃｈ）」、  Ｓｎａｐｔｅｌｌ、アクセス日：２０１１年４月１４日、ｈｔｔｐ：／／ｗｗｗ．ｓｎａｐｔｅｌｌ．ｃｏｍ／
【非特許文献１３】「Ｋｏｏａｂａ：スマート視覚標識の作成―ラップトップおよびデスクトップコンピュータのための画像認識製品（Ｋｏｏａｂａ：  Ｍａｋｅ  Ｓｍａｒｔ  Ｖｉｓｕａｌｓ−  ｉｍａｇｅ  ｒｅｃｏｇｎｉｔｉｏｎ  ｐｒｏｄｕｃｔｓ  ｆｏｒ  ｍｏｂｉｌｅ  ａｎｄ  ｄｅｓｋｔｏｐ）」、アクセス日：２０１１年４月１４日、ｈｔｔｐ：／／ｗｗｗ．ｋｏｏａｂａ．ｃｏｍ
【非特許文献１４】Ｋｒｉｓｔｅｎ  Ｌｏｒｒａｉｎｅ  Ｇｒａｕｍａｎによる、「効率的検索および認識のために特徴のセットをマッチングする方法（Ｍａｔｃｈｉｎｇ  Ｓｅｔｓ  ｏｆ  Ｆｅａｔｕｒｅｓ  ｆｏｒ  Ｅｆｆｉｃｉｅｎｔ  Ｒｅｔｒｉｅｖａｌ  ａｎｄ  Ｒｅｃｏｇｎｉｔｉｏｎ）」、２００６年８月１１日、１〜１５３頁、マサチューセッツ工科大学、ケンブリッジ、アメリカ合衆国
【非特許文献１５】Ｄａｖｉｄ  Ｎｉｓｔｅｒらによる、「語彙木によるスケーラブル認識法（Ｓｃａｌａｂｌｅ  Ｒｅｃｏｇｎｉｔｉｏｎ  ｗｉｔｈ  ａ  Ｖｏｃａｂｕｌａｒｙ  Ｔｒｅｅ）」、ＣＶＰＲ’０６議事録、２００６年１０月９日、８頁
【非特許文献１６】Ｍｉｃｈａｅｌ  Ｄｏｎｏｓｅｒらによる、「効率的な、最大安定性を有する極限領域（ＭＳＥＲ）トラッキング（Ｅｆｆｉｃｉｅｎｔ  Ｍａｘｉｍａｌｌｙ  Ｓｔａｂｌｅ  Ｅｘｔｒｅｍａｌ  Ｒｅｇｉｏｎ  （ＭＳＥＲ）  Ｔｒａｃｋｉｎｇ）」、ＣＶＰＲ’０６議事録、２００６年７月５日、８頁
【非特許文献１７】Ｊｏｎａｔｈｏｎ  Ｓ．  Ｈａｒｅらによる、「ＭａｐＳｎａｐｐｅｒ：携帯電話からの地図画像をマッチングする効率的なアルゴリズムの設計（ＭａｐＳｎａｐｐｅｒ：  Ｅｎｇｉｎｅｅｒｉｎｇ  ａｎ  Ｅｆｆｉｃｉｅｎｔ  Ａｌｇｏｒｉｔｈｍ  ｆｏｒ  Ｍａｔｃｈｉｎｇ  Ｉｍａｇｅｓ  ｏｆ  Ｍａｐｓ  ｆｒｏｍ  Ｍｏｂｉｌｅ  Ｐｈｏｎｅｓ）」、Ｍｕｌｔｉｍｅｄｉａ  Ｃｏｎｔｅｎｔ  Ａｃｃｅｓｓ議事録、Ａｌｇｏｒｉｔｈｍｓ  ａｎｄ  Ｓｙｓｔｅｍｓ  ＩＩ、２００８年１月２８日、１１頁
【非特許文献１８】Ｗｅｎｇａｎｇ  Ｚｈｏｕらによる、「大域部分的複製ウェブ画像検索のための空間コーディング（Ｓｐａｔｉａｌ  Ｃｏｄｉｎｇ  ｆｏｒ  Ｌａｒｇｅ  Ｓｃａｌｅ  Ｐａｒｔｉａｌ−Ｄｕｐｌｉｃａｔｅ  Ｗｅｂ  Ｉｍａｇｅ  Ｓｅａｒｃｈ）」、ＡＣＭ  Ｍｕｌｔｉｍｅｄｉａ’１０議事録、２０１０年１０月２５日〜２９日、５１１〜５２０頁、フィレンツェ、イタリア
【発明の概要】
【発明が解決しようとする課題】
【０００８】
ＥＭＭは、画像の撮影をガイドし、処理コストを制限するための、オリジナルの紙ドキュメント上にオーバーレイされた、意味を備えた標識（ｍｅａｎｉｎｇｆｕｌ−ａｗａｒｅｎｅｓｓ  ｍａｒｋｅｒｓ）として表現されてもよい。しかし、現在のＥＭＭ識別システムは、いかなる特定のマッチング制約も考慮することなしに、幾何的特徴の厳密な比較処理などの、一般的な局所特徴に基づくマッチングのアプローチに、依然として厳密に依存する。そのような、幾何的特徴の厳密な比較処理は、実際には、低い精度、及び高いメモリ／時間複雑性の問題を有する。
【０００９】
従って、高い精度と、低いメモリ及び時間複雑性とを提供する、識別手法が必要とされている。
【課題を解決するための手段】
【００１０】
本発明の第１の態様に係る、インデックス付き画像を識別する方法は、受信手段により、インデックス標識を含む第１の画像を受信し、第１の比較手段により、前記第１の画像と、インデックス付き候補画像との、第１の比較を行い、前記第１の比較を行うことは、前記第１の画像の第１の表現を構築することを含み、前記第１の比較手段により、前記第１の比較に基づいて、前記インデックス付き候補画像の、第１のランク付けを行い、前記第１の比較手段により、前記第１のランク付けに基づいて、前記インデックス付き候補画像から選択を行い、第２の比較手段により、前記第１の画像と、前記選択されたインデックス付き候補画像との、第２の比較を行い、前記第２の比較を行うことは、前記第１の画像の前記第１の表現より高い分解能を有する、前記第１の画像の第２の表現を作成することを含み、前記第２の比較手段により、前記第２の比較に基づいて、前記選択されたインデックス付き候補画像の、第２のランク付けを行い、前記第２の比較手段により、前記第２のランク付けに基づいて、インデックス付き画像を識別することを含む。
【００１１】
本発明の第２の態様に係る方法は、第１の態様において、前記第２の比較を行うことが、前記インデックス標識から、埋め込み型メディアマーカ（ＥＭＭ）の特徴を抽出し、前記ＥＭＭの配向に基づいて、前記第１の画像の優先配向を決定し、前記インデックス付き候補画像のぞれぞれを、グリッドを使用して表現し、前記ＥＭＭを含む前記画像の前記優先配向を、前記第２の表現を使用して表現し、前記第２の表現と、前記インデックス付き候補画像のそれぞれの前記グリッドとの間で、マッチングする対応関係を識別することを含んでもよく、前記第２のランク付けが、前記識別されたマッチングする対応関係に基づいて、前記インデックス付き候補画像のうちの少なくとも１つのそれぞれにスコア付けすることを更に含んでもよい。
【００１２】
本発明の第３の態様に係る方法は、第２の態様において、前記マッチングする対応関係を識別することが、前記第２の表現に含まれる特徴を、前記取得された画像のそれぞれの前記グリッドに含まれる、対応する特徴と比較することを更に含んでよく、前記対応する特徴が、前記優先配向に基づいて平行移動を行うことによって決定されてもよい。
【００１３】
本発明の第４の態様に係る方法は、第１の態様において、前記第１の比較を行うことが、前記インデックス付き候補画像のそれぞれを、グリッドを使用して表現し、前記第１の表現のグリッド位置と、データベース画像のそれぞれの前記グリッドとの間で、マッチングする対応関係の数を識別することを含んでもよく、前記第１のランク付けは、マッチングする対応関係の前記数に基づいてもよい。
【００１４】
本発明の第５の態様に係る方法は、第４の態様において、前記インデックス付き候補画像のそれぞれを、グリッドを使用して表現することが、前記データベース画像のためのインデックスファイルを利用することを含んでよく、前記インデックスファイル内のエントリが、前記データベース画像のそれぞれについて、前記グリッド内の各特徴の属性を対応付けてもよい。
【００１５】
本発明の第６の態様に係る方法は、第５の態様において、前記第１の比較を行うことが、前記インデックスファイル内のエントリを、前記第１の表現と比較することを更に含んでもよい。
【００１６】
本発明の第７の態様に係る装置は、インデックス標識を含む第１の画像を受信するカメラと、前記受信された第１の画像を第１の表現として表現する、第１の比較ユニットであって、前記第１の画像と、データベース画像との、第１の比較を行い、前記第１の比較に基づいて、インデックス付き候補画像をランク付けすることを含む第１のランク付けを行い、前記第１のランク付けに基づいて、前記インデックス付き候補画像から選択を行う、第１の比較ユニットと、前記受信された第１の画像を、前記第１の表現より高い分解能を有する、前記第１の画像の第２の表現として表現する、第２の比較ユニットであって、前記第１の画像と、前記選択された画像のそれぞれとの、第２の比較を行い、前記第２の比較に基づいて、前記選択された画像をランク付けすることを含む第２のランク付けを行い、前記第２のランク付けに基づいて、前記第１の画像に対応する、インデックス付き画像を識別する、第２の比較ユニットとを備える。
【００１７】
本発明の第８の態様に係る装置は、第７の態様において、前記第２の比較を行うことが、前記インデックス標識から、埋め込み型メディアマーカ（ＥＭＭ）の特徴を抽出し、前記ＥＭＭの配向に基づいて、前記第１の画像の優先配向を決定し、前記インデックス付き候補画像のぞれぞれを、グリッドを使用して表現し、前記ＥＭＭを含む前記画像の前記優先配向を、前記第２の表現を使用して表現し、前記第２の表現と、前記インデックス付き候補画像のそれぞれの前記グリッドとの間で、マッチングする対応関係を識別することを更に含んでよく、前記第２のランク付けは、前記識別されたマッチングする対応関係に基づいて、前記インデックス付き候補画像のうちの少なくとも１つのそれぞれをスコア付けすることを更に含んでもよい。
【００１８】
本発明の第９の態様に係る装置は、第８の態様において、前記マッチングする対応関係を識別することが、前記第２の表現に含まれる特徴を、前記選択された画像のそれぞれの前記グリッドに含まれる、対応する特徴と比較することを更に含んでよく、前記対応する特徴が、前記優先配向に基づいて平行移動を行うことによって決定されてもよい。
【００１９】
本発明の第１０の態様に係る装置は、第７の態様において、前記第１の比較を行うことが、前記候補となるインデックス付き画像のそれぞれを、グリッドを使用して表現し、前記第１の表現のグリッド位置と、前記データベース画像のそれぞれの対応するグリッドとの間の、マッチング属性の数を識別することを含んでよく、前記第１のランク付けが、マッチング属性の前記数に基づいてもよい。
【００２０】
本発明の第１１の態様に係る装置は、第１０の態様において、前記インデックス付き候補画像のそれぞれを、グリッドを使用して表現することが、前記インデックス付き候補画像のためのインデックスファイルを利用することを含んでよく、前記インデックスファイル内のエントリが、前記データベース画像のそれぞれについて、前記グリッド内の各特徴の属性を対応付けてもよい。
【００２１】
本発明の第１２の態様に係る装置は、第１１の態様において、前記第１の比較を行うことが、前記インデックスファイル内のエントリを、前記第１の表現と比較することを更に含んでもよい。
【００２２】
本発明の第１３の態様に係るプログラムは、コンピュータに、インデックス付き画像の識別のためのプロセスを実行させるプログラムであって、前記プロセスは、インデックス標識を含む第１の画像を受信し、前記第１の画像と、インデックス付き候補画像との、第１の比較を行い、前記第１の比較を行うことは、前記第１の画像の第１の表現を構築することを含み、前記第１の比較に基づいて、前記インデックス付き候補画像の、第１のランク付けを行い、前記第１のランク付けに基づいて、インデックス付き候補画像から選択を行い、前記第１の画像と、前記選択したインデックス付き候補画像との、第２の比較を行い、前記第２の比較を行うことは、前記第１の画像の前記第１の表現より高い分解能を有する、前記第１の画像の第２の表現を作成することを含み、前記第２の比較に基づいて、前記選択したインデックス付き候補画像の、第２のランク付けを行い、前記第２のランク付けに基づいて、インデックス付き画像を識別することを含む。
【００２３】
本発明の第１４の態様に係るプログラムは、第１３の態様において、前記第２の比較を行うことが、前記インデックス標識から、埋め込み型メディアマーカ（ＥＭＭ）の特徴を抽出し、前記ＥＭＭの配向に基づいて、前記第１の画像の優先配向を決定し、前記インデックス付き候補画像のぞれぞれを、グリッドを使用して表現し、前記ＥＭＭを含む前記画像の前記優先配向を、前記第２の表現を使用して表現し、前記第２の表現と、前記インデックス付き候補画像のそれぞれの前記グリッドとの間で、マッチングする対応関係を識別することを含んでよく、前記第２のランク付けが、識別されたマッチングする対応関係に基づいて、前記インデックス付き候補画像のうちの少なくとも１つのそれぞれをスコア付けすることを更に含んでもよい。
【００２４】
本発明の第１５の態様に係るプログラムは、第１４の態様において、前記マッチングする対応関係を識別することが、前記第２の表現に含まれるピクセルを、前記インデックス付き候補画像のそれぞれの前記グリッドに含まれる、対応する特徴と比較することを更に含んでよく、前記対応する特徴が、前記優先配向に基づいて平行移動を行うことによって決定されてもよい。
【００２５】
本発明の第１６の態様に係るプログラムは、第１５の態様において、前記第１の比較を行うことが、前記インデックス付き候補画像のそれぞれを、グリッドを使用して表現し、前記第１の表現のグリッド位置と、データベース画像のそれぞれの前記グリッドとの間で、マッチングする対応関係の数を識別することを含んでよく、前記第１のランク付けが、マッチングする対応関係の前記数に基づいてもよい。
【００２６】
本発明の第１７の態様に係るプログラムは、第１６の態様において、前記インデックス付き候補画像のそれぞれを、グリッドを使用して表現することが、前記データベース画像のためのインデックスファイルを利用することを含んでよく、前記インデックスファイル内のエントリが、前記データベース画像のそれぞれの前記グリッド内の各ピクセルの属性をマッピングしてもよい。
【００２７】
本発明の第１８の態様に係るプログラムは、第１７の態様において、前記第１の比較を行うことが、前記インデックスファイル内のエントリを、前記第１の表現と比較することを更に含んでもよい。
【００２８】
本発明の第１９の態様に係るプログラムは、第１８の態様において、前記プロセスが、前記インデックスファイル内の前記エントリとの比較のために、前記第１の表現のインデックス表現を作成することを更に含んでもよい。
【００２９】
本発明の第２０の態様に係るプログラムは、第１６の態様において、前記特徴を比較することが、前記インデックス付き候補画像のためのインデックスファイルを利用し、ここで、前記インデックスファイル内のエントリは、前記データベース画像のそれぞれの前記グリッド内の各特徴の属性をマッピングし、前記第２の表現を、前記インデックスファイルとの比較のためのインデックス表現で表現し、前記インデックスファイル内のエントリを、前記インデックス表現と比較することを含んでもよい。
【００３０】
本発明に関する追加の態様は、一部は、以下の説明において記載され、一部は、説明から明らかであり、又は本発明の実施によって知られ得る。本発明の態様は、以下の詳細な説明、及び添付の特許請求の範囲において特に指摘される、要素によって、並びに様々な要素及び態様の組み合わせによって、実現及び達成されてもよい。
【００３１】
前述の、及び以下の説明の両方は、例示的かつ説明的なものにすぎず、特許請求される本発明、又はその適用を、いかなる形においても限定することを意図するものではない、ということを理解されたい。
【００３２】
添付図面は、本明細書に組み込まれ、本明細書の一部を構成するものである。添付図面は、本発明の実施形態を例示し、説明と一緒に、本発明の技術の原理を説明及び例示するために役立つ。
【発明の効果】
【００３３】
本発明に係る態様によれば、階層的比較アプローチを利用することによって、より少ない誤検出で画像を識別することが可能になる。
【図面の簡単な説明】
【００３４】
【図１】従来の埋め込み型メディアマーカ（ＥＭＭ）識別プロセスを示すシーケンス図である。
【図２】本発明の実施形態による、画像の特徴に基づいた画像識別を示すシーケンス図である。
【図３】本発明の実施形態による方法を示すフローチャートである。
【図４】本発明の実施形態によるグリッド化処理（ｇｒｉｄｄｉｎｇ  ｐｒｏｃｅｓｓ）を示す図である。
【図５】本発明の実施形態による、インデックスファイル、及び画像の表現（ｒｅｐｒｅｓｅｎｔａｔｉｏｎ）を示す図である。
【図６】本発明の実施形態による比較方法を示すフローチャートである。
【図７】本発明の実施形態による、埋め込み型メディアマーカ（ＥＭＭ）の向き（ｄｏｍｉｎａｎｔ  ｏｒｉｅｎｔａｔｉｏｎ）に基づいた、受信された画像の平行移動を示す図である。
【図８】本発明の実施形態による装置の機能図である。
【図９】本発明のシステムが実施され得るコンピュータプラットフォームを例示する図である。
【発明を実施するための形態】
【００３５】
以下の詳細な説明では、添付図面を参照する。添付図面においては、同一の機能要素が同様の数字で表されている。前述の添付図面は、本発明の原理と一致する特定の実施形態及び実装を限定せず、例示するものである。それらの実装は、当業者が本発明を実施することを可能にするのに十分なだけ詳細に説明されるが、本発明の範囲及び精神を逸脱することなく、他の実装が利用されてもよく、様々な要素の構造的変更及び／又は置換が行われてもよい、ということを理解されたい。以下の詳細な説明は、従って、限定された意味で解釈されるべきではない。加えて、説明される本発明の様々な実施形態は、汎用コンピュータ上で実行されるソフトウェアの形態で、専用ハードウェアの形態で、又は、ソフトウェアとハードウェアとの組み合わせで実装されてもよい。
【００３６】
画像の特徴量同士を単純に比較していく以前のアプローチでは、ＥＭＭ識別に固有のマッチング制約を考慮することができない。従って、そのような以前のアプローチでは、ＥＭＭ識別の十分な精度を達成するために、より多くのメモリと時間とが不必要に費やされる。本発明の例示的実施形態では、ＥＭＭ識別の効率及び精度の両方を向上させるために、階層化された２つのマッチング制約を利用する。特に興味深いのは、ＥＭＭ識別に固有の、「単射（ｉｎｊｅｃｔｉｏｎ）」及び「近似的−大域幾何的一貫性（ａｐｐｒｏｘｉｍａｔｅ  ｇｌｏｂａｌ  ｇｅｏｍｅｔｒｉｃ  ｃｏｎｓｉｓｔｅｎｃｙ）」（略してＡＧＧＣ）であり、これらについて以下に更に説明する。
【００３７】
（単射制約）
単射制約は、ＥＭＭ識別においてクエリ画像を生成することを介して実施される。ここで、クエリ画像は、図２（ａ）に示すように、紙の上などに印刷されたＥＭＭを表示するパッチ２０２の、カメラ撮影されたバージョン２０１である。単射制約は、クエリ画像の、それぞれの検出された「顕著な」領域が、ターゲット画像(クエリ画像との同一性を判断する対象となる画像)の多くても１つの領域にマッピングされる、ということを意味している（すなわち、「単射写像（ｉｎｊｅｃｔｉｖｅ  ｍａｐｐｉｎｇ）」である）。しかし、そのような制約は、クエリ画像がオリジナル画像２０４の大幅なデジタル編集によって生成される、近似的−複製画像検出法／部分的−複製画像検出法（ｎｅａｒ−ｄｕｐｌｉｃａｔｅ／ｐａｒｔｉａｌ−ｄｕｐｌｉｃａｔｅ  ｉｍａｇｅ  ｄｅｔｅｃｔｉｏｎ）においては維持されない可能性がある。図２（ｂ）は、この制約を破る例示的ケースを示しており、この場合には部分的-複製画像検出の対象としなければならない。適切なオリジナル画像２０４を問題なく取得するためには、クエリ画像２０３の部分セクションを、データベース内の画像と対照して解析する必要がある。
【００３８】
（ＡＧＧＣ制約）
ＡＧＧＣ制約は、ＥＭＭによって実施され、これは、クエリ画像とそのターゲットとの間の幾何学的変化を、予測可能な小さな範囲内に限定するものであり、従って、クエリ画像の空間的レイアウトは、そのターゲット画像の空間的レイアウトと、高い忠実度で大域的に一致していなければならない。そのような制約は、他の類似した応用例においては、必ずしも維持されるとは限らない。図２（ｃ）は、同じオブジェクトを含むが、縮尺が大きく異なる２つの画像２０５及び２０６の例を示す。オブジェクト認識の応用においては、それらをマッチングさせることが必要とされるが、ＥＭＭ識別には、それらをマッチングさせることは期待されない。単射制約及びＡＧＧＣ制約を考慮に入れることによって、検索範囲を限定することは、更に精度を向上させ、メモリ及び時間複雑性を減少させるのに役立つ可能性がある。この例では、２つの画像２０５及び２０６の間のスケーリング問題を考慮に入れることによって、それらの画像のうちの１つがクエリとして使用される場合には、他方をターゲットの候補から外して、他の画像から適切な画像が取得される。
【００３９】
これらのマッチング制約を十分に利用して、複数分解能グリッド化情報（ｍｕｌｔｉ−ｒｅｓｏｌｕｔｉｏｎ  ｇｒｉｄｄｉｎｇ  ｉｎｆｏｒｍａｔｉｏｎ）に基づいた２つの制約から、比較対象の絞込みを行うアルゴリズムを設計した。これらは、「単射」及び「ＡＧＧＣ」対応関係を検出するものである。そして、これらを使用して画像の類似性を検出するのである。大きな平行移動量を有する、困難なケースに対処するために、空間的近隣検索アプローチ（ｓｐａｔｉａｌ  ｎｅｉｇｈｂｏｒｈｏｏｄ  ｓｅａｒｃｈ  ａｐｐｒｏａｃｈ）が更に提案される。メモリを縮小し、処理時間を制限するための、階層的戦略が、スケーラビリティを達成するために利用される。
【００４０】
（例示的マッチング手法のワークフロー）
図３は、本発明の例示的実施形態における、ＡＧＧＣ及び単射マッチング制約を階層的戦略に従って採用する、例示的マッチング手法のワークフローを示す。このアプローチは、「幾何学的制約に基づく対応性投票法（Ｇｅｏｍｅｔｒｉｃ  Ｃｏｎｓｔｒａｉｎｅｄ  Ｃｏｒｒｅｓｐｏｎｄｅｎｃｅｓ  Ｖｏｔｉｎｇ）」（略してＧＣＣＶ）と呼ばれてもよい。ＥＭＭを含む画像を受信したら（３００）、この戦略では、ＡＧＧＣ及び単射マッチング制約を、以下の階層構造で利用する。
【００４１】
（１）第１の粗い比較及びランク付けを行う（３０１）。この段階の間、本発明の例示的実施形態では、ＡＧＧＣ制約を利用して、データベース内の画像の、粗いレベルのランク付けを行う。初期の「ＡＧＧＣ」対応関係構築は、粗いレベルのグリッドを各画像上に配置し、同じ粗いレベルのグリッド内に存在するビジュアルワード（ｖｉｓｕａｌ ｗｏｒｄｓ）のみを相互にマッチングさせることによって動作する。全てのインデックス付き画像が、次に、前述の「ＡＧＧＣ」対応関係に基づいてランク付けされる。なお、ここにおける「ビジュアルワード」とは、検索に用いる画像の特徴(本実施例では局所特徴量)のことであり、文書検索における「キーワード」に対応させた用語である。
【００４２】
（２）第１の粗い比較によるランク付けに基づいて、第２の細かな（ｒｅｆｉｎｉｎｇ）比較及びランク付けを行う（３０２）。この段階の間、本発明の例示的実施形態では、上位ランクの画像を、より細かい分解能のグリッドに分割し、それらの初期対応関係を、細かい粒度における「単射」制約を使用して検証することによって動作する、対応関係の細分化（ｃｏｒｒｅｓｐｏｎｄｅｎｃｅ  ｒｅｆｉｎｅｍｅｎｔ）を利用する。大きな平行移動によってもたらされるエラーを更に減少させるために、「平行移動補償（ｔｒａｎｓｌａｔｉｏｎ  ｃｏｍｐｅｎｓａｔｉｏｎ）」アルゴリズムも、必要に応じて利用してもよい。平行移動補償アルゴリズムは、平行移動による変化（ｔｒａｎｓｌａｔｉｏｎ  ｃｈａｎｇｅｓ）を評価し、適格の対応関係(比較対象となっている2つの画像の局所的な対応関係のうちで、最終的に採用すると決定した対応関係)を見つける前に、画像を大まかにアライメントする。これは、ＥＭＭ画像の現在の向き(例えばSIFT特徴量において頻度が最も大きい方向)に基づいて、そのＥＭＭを含む画像の向きを決定し、この向きに従って、グリッド又はその他の表現を作成することによって行われる。
【００４３】
（３）ランク付けの結果、最上位となった画像（１つ又は複数）をユーザに返す（３０３）。適格の対応関係が、データベース画像をランク付けするために使用され、そして、ランク付けの結果としての上位画像（１つ又は複数）が、最終確認のために、ユーザに返されてもよい。あるいは、ユーザによる最終確認をなしで済ませ、最上位の画像を、デジタルメディアの取得のために利用してもよい。
【００４４】
（４）前のステップ３０３に基づいて、適切なデジタルメディアを取得する（３０４）。
【００４５】
加えて、階層的符号化／復号化戦略が、複数分解能グリッド情報を効率的に記憶及び利用するために採用される。以下の、比較の技術的説明において更に記載されるように、グリッドは、テーブルの形態で表現されてもよい。
【００４６】
ＡＧＧＣマッチング制約に基づいた、第１の粗い比較ランク付けの説明
「ＡＧＧＣ」制約は、クエリ画像の空間的レイアウトが、そのターゲット画像の空間的レイアウトと、高い忠実度で大域的に一致していなければならない、ということを意味している。従って、対応する特徴は、２つのそれぞれの画像間で、同様の位置に位置していなければならない。この仮定に基づいて、グリッド・バッグ・オブ・ワーズ（Ｇｒｉｄ−Ｂａｇ−ｏｆ−Ｗｏｒｄｓ）（Ｇ−ＢＯＷ）マッチングなどのマッチング手法が、「ＡＧＧＣ」制約を満たす初期対応関係を見つけるために使用されてもよい。Ｇ−ＢＯＷマッチングは、画像を、ｎ個の等しいサイズのグリッドに分割し、次に、クエリ画像の局所特徴ｆｑとインデックス付き画像の局所特徴ｆｉｄｘとを、量子化器ｑ（．）によって量子化する。この際に、同じビジュアルワードに量子化され、且つ同じｇｒｉｄ−ｉｄを有する(すなわち、ほぼ同じ位置にある)場合に、ｆｑがｆｉｄｘにマッチしていると判断する。すなわち、ｆｑとｆｉｄｘとがマッチしているか否かを表すＧ−ＢｏＷマッチング値は次の式によって表される。
【００４７】
【数１】
2012230676.tif 000003
【００４８】
次に、グリッドｉ内における全てのｆｑ(クエリ画像の局所特徴)についてのＧ−ＢｏＷマッチング値の合計を求め正規化する。これにより、クエリ画像とインデックス画像それぞれのグリッドｉ内における部分同士のマッチングスコア、すなわち類似度を取得する。
【００４９】
【数２】
2012230676.tif 000004
【００５０】
上式で、｜Ｉｑｉ｜及び｜Ｉｉｄｘｉ｜は、それぞれ、クエリ画像及びインデックス付けされた画像のグリッドｉ内の、ビジュアルワードの総数である。全ての別個のグリッドのマッチングスコアが合計されてもよく、これは、クエリ画像Ｉｑとインデックス画像Ｉｉｄｘとの間の最終的な類似度ｓｉｍ（ｉｑ，ｉｄｘ）をもたらす。
【００５１】
【数３】
2012230676.tif 000005
【００５２】
図４は、２×２グリッドを使用したＧ−ＢＯＷ方法の例示的実施を示す。画像４００は、２×２グリッド４０１内で表現され、各グリッドから対応関係が抽出されてもよく、そして、ホモグラフィ行列(射影変換行列)４０２が構築されてもよい。ホモグラフィ行列は、より容易な比較のために、各グリッドの対応関係を、ビット列、又はワードＩＤとして表現する。
【００５３】
グリッド化なしのアルゴリズムを愚直に適用した場合には、ＡＧＧＣ制約が破られることになるが、ここで提案したＧ−ＢＯＷ方法を適切なグリッド（例えば、２×２、４×４など）を用いて利用することによって、大概のマッチングについて、「ＡＧＧＣ」制約が満されることを確実にする。加えて、前述の平行移動補償アルゴリズムによって、又はその他の手段によって、ホモグラフィが正しく評価された場合、対応関係のホモグラフィ一致について更に検証することが可能であり、これにより、グリッド化なしの愚直な適用に比べ、誤検出がはるかに少なくて済む。
【００５４】
メモリ複雑性。実際には、Ｇ−ＢｏＷマッチングを効率的に実施するために、インデックス付けされた局所特徴のグリッドＩＤが、インデックスファイルのテーブル内に記録される。この解決法は、インデックスファイルのために、グリッド化なしの画像ファイルよりも、わずかに多くのメモリ空間を要するのみである。例えば、４×４グリッドのグリッドＩＤを記録するために、各局所特徴について、追加の４ビットのみが必要とされる。
【００５５】
図５は、図４の画像を表現する、可能なインデックスファイルの例である。インデックスファイルは、画像内の局所特徴量を示すワードＩＤと、その局所特徴量に対応するグリッドＩＤと、適切なファイル名とによって整列されていてもよい。
【００５６】
時間複雑性。マッチングに追加的に費やされる時間消費量は、次を含む。１）クエリ画像の特徴のための、オンライングリッドＩＤ計算、及び、２）メモリからの、インデックス付けされた特徴のグリッドＩＤの取り出し、及び、それらと、クエリ画像のグリッドＩＤとの比較。通常、そのようなマッチングは、時間消費量を増加させることが予想される。しかし、グリッドマッチングを含めることは、時間消費量を実際には増加させない。代わりに、それは、多くの不適格な特徴をマッチングさせることと、マッチングスコアを更新することの必要性をなくすことによって、時間をわずかに減少させる。
【００５７】
（単射マッチング制約に基づいた、第２の細かなランク付けの説明）
第１の粗い比較及びランク付けは、「ＡＧＧＣ」制約を満たす初期対応関係を提供する。しかし、そのような手法では、同じグリッド内に量子化されたクエリ画像のＭ個の特徴が、共通のグリッド内に量子化されたインデックス画像のＮ（Ｍ≠Ｎ）個の特徴とマッチする場合、「単射写像」条件を保証することができない。従って、分解能を増加させること（すなわち、グリッドの数を増加させること、又は、より厳しい空間的制約を実施すること）によって、不適格の対応関係を除外するようにしてもよい。しかし、これは、幾何学的変化に対するロバスト性を減少させて、適格の対応関係の欠如をもたらす可能性もある。この問題を解決するために、ホモグラフィ検証（ｈｏｍｏｇｒａｐｈｙ  ｖｅｒｉｆｉｃａｔｉｏｎ）（例えば、画像の向きを決定し、その向きを揃えて比較を行うこと）が、２つの画像間のパースペクティブ変化が小さい場合（そのような条件は、ＥＭＭ識別において満たされる可能性がある）に「単射」特性を維持するために、採用されてもよい。例示的手順では、仮定されたホモグラフィが、候補となる対応関係に基づいて、ピクセルレベルで、最初に評価され、各対応関係が、次に、ホモグラフィ一致を調べることによって検証される。最後に、ホモグラフィ一致を満たす対応関係の数に従って、マッチングスコアが更新される。
【００５８】
しかし、従来のホモグラフィ評価及び検証は、以下の理由により理想的ではない。１）ピクセルレベルの座標をハードディスクからロードすることは、時間がかかりすぎる。２）ピクセルレベルの空間情報を使用したホモグラフィ評価及び検証は、特徴点（ｋｅｙｐｏｉｎｔ）の小さな位置変化の影響を受けやすい。３）ＢｏＷマッチングから取得された一時的マッチングは、非常にノイズが多く、これは、行列を計算するための時間を大幅に増加させる可能性があり、かつ、評価された行列の精度を減少させる可能性もある。
【００５９】
これらの制限に対処するために、近似的−幾何学的検証法（Ａｐｐｒｏｘｉｍａｔｅ  Ｇｅｏｍｅｔｒｉｃ  Ｖｅｒｉｆｉｃａｔｉｏｎ）（ＡＧＶ）などの、グリッドレベルでのより効率的な検証手順が利用されてもよい。初期対応関係の、細かいレベルのグリッド情報が、ホモグラフィ行列を評価するために使用される。続いて、全ての一時的マッチングが、ホモグラフィ一致に基づいて検証される。
【００６０】
図６は、近似的−幾何学的検証法の例示的プロセスを示す。最上位の候補画像が与えられたら、Ｇ−ＢＯＷマッチングが、最初に、初期対応関係から行われる（６００）。ホモグラフィ評価が、次に、初期対応関係から行われて、適切なホモグラフィ行列が作成されてもよい（６０１）。ホモグラフィ行列に基づいて、クエリ画像が、候補画像と空間的にアライメントされてもよい（６０２）。一時的マッチングが、次に、バッグ・オブ・ワーズ・オーバーラッピング（ｂａｇ  ｏｆ  ｗｏｒｄｓ  ｏｖｅｒｌａｐｐｉｎｇ）から検証され、最終決定された適格のマッチングが、それにより、取得されてもよい（６０３）。マッチングスコアが、それにより、（例えば、式（２）及び（３）に従って）更新されてもよく、それに応じて、上位の候補画像が再ランク付けされる（６０４）。
【００６１】
「ＡＧＧＣ」対応関係を見つけるために粗い量子化を採用する場合、いくつかの適格のマッチングの損失をもたらす可能性がある。従って、損失を部分的に埋め合わせるために、全ての一時的マッチングが検証される。ＡＧＶのためにグリッドの数を選択する場合、識別能力と、空間複雑性との間のトレードオフが存在する。使用されるグリッドがより多ければ、対応関係の座標はより精密になるが、それにより、より多くのビットが、グリッディング情報を記憶するために必要とされる。いくつかのパラメータ（１６×１６、３２×３２、及び６４×６４）が利用されてもよく、３２×３２が、最良の結果をもたらす傾向がある。
【００６２】
ＡＧＶ対従来の幾何学的検証法。近似的−幾何学的検証法は、速度の観点から、２つの理由により、従来の幾何学的検証法より性能が優れている。第１に、量子化された位置情報は、メモリ内に記憶されるのに十分なほど小さく（例えば、３２×３２のグリッドＩＤは、特徴当たり１０ビットを要するのみである）、これは、細分化ステップの間にハードディスクにアクセスするための時間をなくすのに役立つ。第２に、Ｇ−ＢｏＷマッチングによって取得された対応関係は、ＢｏＷマッチングに基づく対応関係よりもはるかにノイズが少なく、従って、それらを使用することによって、評価時間が大幅に減少する可能性がある。実験でも、Ｇ−ＢｏＷマッチングに基づく対応関係を使用することによって、ＢｏＷに基づく対応関係を使用するよりもはるかに高い識別精度が達成されることが示されている。
【００６３】
（平行移動補償）
大きな幾何学的変化を有する困難なケースでは、粗い量子化によって、多くの適格の「ＡＧＧＣ」対応関係が不可避的に破棄され、結果として、ホモグラフィ評価の精度が劣化する可能性がある。又、更には、ターゲット画像が上位ランクの候補リスト内に配置されない場合、ターゲット画像を完全に逃してしまう可能性がある。例えば、ｉｍａｇｅ＿ｓｉｚｅ／ｎ１／２より大きな平行移動量（ｎは、「ＡＧＧＣ」対応関係の構築ステップにおけるグリッドの数）は、全てのグリッドの完全なミスアライメントをもたらす。これにより、ターゲット画像に対して「ＡＧＧＣ」対応関係を検出することができなくなる。従って、ミスアライメントによってもたらされるエラーを補償することは、良好な識別精度を達成するために非常に重要である。
【００６４】
平行移動問題を解決するための直接的な解決法は、空間的な複数割り当てを行うことである。言い換えると、ＥＭＭを有する画像の点を、データベース画像内の対応する1つの点と比較する代わりに、通常の方法で割り当てられるグリッドだけでなく、８つの隣接するグリッドにも点を割り当てて比較するのである。しかし、そのような単純な戦略は、過剰なノイズを誘発させる可能性があり、結果として、精度を低下させ、時間消費量を増加させる。多くの場合、９つの量子化された方向のうち、実際の平行移動による変化を最良に近似することが可能な方向は、１つのみである。従って、間違った方向に割り当てられた多くの点は、単にノイズになる。
【００６５】
この複数割り当ての制限を克服し、平行移動によってもたらされるエラーを減少させるための、より良い解決法は、比較を行う前に、ＥＭＭ画像の配向を決定することである。この配向が決定されたら、２つの画像間で、最良の平行移動の方向を評価することが可能であり、次に、全ての点を、この方向に割り当てることが可能である。従って、正しい隣接点又は平衡移動点を決定することが可能である。この着想を実施するためには、最良の平行移動方向に向かってシフトする場合に、大部分のグリッドにおいて、（式（２）で示される）最大となる類似性が取得されている、ということが仮定されてもよい。言い換えると、全てのグリッドについて、最も多くの最大マッチングスコアを有する方向が、最良の平行移動方向である。以下のアルゴリズムは、平行移動方向を評価するための例示的手順を記載する。
【００６６】
【数４】
2012230676.tif 000006
【００６７】
最良の平行移動方向を取得した後、「ＡＧＧＣ」対応関係を見つけるために、各点が、次に、この方向に割り当てられる。従って、現在のグリッドのワードと、最良の隣接グリッドのワードとの間の対応を含む、集合Ｍｂｅｓｔが取得されてもよい。平行移動変化によってもたらされるエラーを補償するために、マッチングスコアが計算され、集合Ｍｂｅｓｔを使用して、ホモグラフィが評価される。
【００６８】
図７は、受信された画像の向きに基づいた、ホモグラフィ評価の例を示す。受信された画像７００から、ＥＭＭの向き、ここでは局所特徴(ＳＩＦＴ)において、各キーポイントにおける画素値の勾配の方向のうちで最大頻度を有する勾配の方向をその「向き」として決定する。そして、その向きを合わせるように、平行移動を行い、これを評価する（７０１）。評価は、画像の形態を取ってもよく、又は、画像の特徴を表現する単純な行列又はグリッドであってもよく、又は、インデックスファイルと同じフォーマットであってもよい。
【００６９】
（階層的符号化／復号化）
複数分解能空間情報を記憶及び復号化するための効率的な戦略は、以下の３つの要件を満たさなければならない。１）できるだけ小さなメモリ空間を要するものでなければならない。２）粗いレベルのグリッドＩＤ、隣接するグリッドＩＤ、及び細かいレベルの座標を含む、所望の情報を高速に計算しなければならない。３）粗いレベルのグリッドの数などの、パラメータの調節が容易でなければならない。従って、本発明の実施形態は、これらの要件を最も良く満たす、階層的符号化及び復号化戦略を、必要に応じて利用してもよい。各画像は、２ｋ×２ｋのグリッドに階層的に量子化される。画像は、最初に、２×２のグリッドに分割され、次に、各グリッドが、２×２のグリッドに反復的に更に分割され、レベルｋにおいて２ｋ×２ｋのグリッドがもたらされる。図４は、ｋ＝１の場合の例を示す。次に、レベルｋにおける各グリッドには、固有のグリッドＩＤが与えられる（例えば、順次的な番号付け、又は、上位レベルのグリッド（ｘｉ−１，ｙｉ−１）内の４つの位置のうちの１つを一意に表す座標（ｘｉ，ｙｉ）、（１≦ｉ≦ｋ）、による符号化など）。最後に、全てのレベルにおける座標が、一緒に連結されて、ビット列を形成し、図５に示すように、それに応じてインデックス付けされてもよい。
【００７０】
メモリ複雑性。最も細かいレベルのグリッドの数が与えられたら、提案された手法では、全てのより粗いレベルの情報が、対応する最も細かいレベルのグリッドＩＤ内に埋め込まれることによって、メモリ空間の占有度が最も低くなる。加えて、そのような情報は、各局所特徴の画像ＩＤと共にまとめられて、高速アクセスのための転置ファイル内に記憶されてもよい。図５は、インデックスの例示的構成を示す。各ビジュアルワードは、画像（その中にそのビジュアルワードが現れる）のリストと、対応するグリッドＩＤとを含む、インデックス内のエントリを有する。
【００７１】
時間複雑性。階層的戦略は、いくつかのビット／加算／減算演算を使用して、全ての所望の情報を解析することが可能であり、これは、実際の使用において非常に高速である。
【００７２】
図８は、本発明の例示的実施形態による装置８００の機能図の一例を示す。ＥＭＭを含む画像８０１は、カメラ８０２によって受信され、カメラ８０２は、データベース８０５との第１の比較を行う第１の比較ユニット８０４に、画像を転送する。装置は、必要に応じて、画像を平行移動させる平行移動ユニット８０３に、及び、画像を必要に応じて符号化する符号化ユニット８０７に、画像を転送してもよい。第１の比較ユニットの結果は、第２の比較ユニット８０６に転送される。第２の比較ユニットによる結果は、ディスプレイ８０８に転送されてもよく、又は、適切なデジタルメディアがロードされて、表示されてもよい。符号化ユニット８０７は、データベース内の画像を表現するために使用されるインデックスファイル（１つ又は複数）のフォーマットで、受信された画像を表現するためにも使用されてもよい。
【００７３】
図９は、コンピュータ／サーバシステム９００（その上で、本発明の方法の実施形態が実施されてもよい）の一実施形態を示すブロック図である。システム９００は、当業者に公知であるような、命令を実行するために動作するプロセッサ９０２及びメモリ９０３を含む、コンピュータ／サーバプラットフォーム９０１を含む。本明細書で使用される用語「コンピュータ読み取り可能媒体（ｃｏｍｐｕｔｅｒ−ｒｅａｄａｂｌｅ  ｍｅｄｉｕｍ）」は、命令を実行するプロセッサ９０２にこれを提供することに関与する、任意の媒体を意味する。加えて、コンピュータプラットフォーム９０１は、キーボード、マウス、タッチ装置、又は口頭コマンドなどの、複数の入力装置９０４からの入力を受信する。コンピュータプラットフォーム９０１は、加えて、ポータブルハードドライブ、光媒体（ＣＤ又はＤＶＤ）、ディスク媒体などの、リムーバブル記憶装置９０５、又は、コンピュータによって実行可能コードが読み取られことが可能な、任意のその他の媒体に接続されてもよい。コンピュータプラットフォームは、更に、インターネットに、あるいは、その他の、ローカルのパブリック又はプライベートネットワークの構成要素に接続された、ネットワークリソース９０６に接続されてもよい。ネットワークリソース９０６は、ネットワーク９０７上の遠隔位置から、コンピュータプラットフォームに、命令及びデータを提供してもよい。ネットワークリソース９０６への接続は、８０２．１１標準、Ｂｌｕｅｔｏｏｔｈ（登録商標）、又はセルラプロトコルなどの、無線プロトコルを介してもよく、あるいは、ケーブル、又は光ファイバなどの、物理的伝送媒体を介してもよい。ネットワークリソースは、データ及び実行可能命令を、コンピュータプラットフォーム９０１から離れた位置において記憶するための、記憶装置を含んでもよい。コンピュータは、データ及びその他の情報をユーザに出力するために、並びに、ユーザからの追加の指示及び入力を要求するために、ディスプレイ９０８と相互作用する。ディスプレイ９０８は、従って、ユーザと相互作用するための入力装置９０４として更に働いてもよい。
【００７４】
更に、本明細書において開示された本発明の明細及び実施を考慮すれば、本発明の他の実施は当業者にとって明らかであろう。記載された実施形態の、様々な態様及び／又は構成要素は、単独で、又は任意の組み合わせで、画像識別システム内に使用されてもよい。明細及び例は、例示的なものとしてのみ考慮されることを意図するものであり、本発明の真の範囲及び精神は、特許請求の範囲によって示される。
【図１】
2012230676.tif 000007
【図２】
2012230676.tif 000008
【図３】
2012230676.tif 000009
【図４】
2012230676.tif 000010
【図５】
2012230676.tif 000011
【図６】
2012230676.tif 000012
【図７】
2012230676.tif 000013
【図８】
2012230676.tif 000014
【図９】
2012230676.tif 000015