(57)【要約】【課題】モデル画像から選択された特徴点のセットとクエリ画像から選択された特徴点のセットとのセット同士のマッチングを迅速に行うことができるようにする。【解決手段】クエリ画像から、ベース点と、単数あるいは複数のサポート点とからなる特徴点セットが複数決定され、位置関係を表す幾何情報が生成される。また、クエリ特徴点とモデル特徴点とのセット同士のマッチングがLSHにより行われる。マッチングの前、特徴量に基づくクラスタリングが行われ、それぞれのクエリ特徴点と同じクラスタに属するモデル特徴点がクエリ特徴点の最近傍候補とされる。サポート点の最近傍候補の位置を基準として、幾何情報により特定される、ベース点の最近傍候補があるとされる位置にベース点候補がない場合、その位置にベース点候補のモデル特徴点が追加される。本発明は、局所特徴量を用いた物体認識を行う装置に適用することができる。【選択図】図５
2011221688.tif 000002
【特許請求の範囲】
【請求項１】
特徴量に基づいてクラスタリングすることによって決定された、モデルデータの特徴点であるモデル特徴点が属するクラスタの情報と、前記モデル特徴点の特徴量の情報を記憶する記憶手段と、
クエリとして入力されたデータの特徴点であるクエリ特徴点の特徴量を抽出する抽出手段と、
基準となる１つの前記クエリ特徴点である基準点と、前記基準点に従属する１つまたは複数の前記クエリ特徴点である従属点とから構成される前記クエリ特徴点の第１のセットを決定し、前記第１のセット毎に、前記基準点の位置を基準とする、それぞれの前記従属点の位置を表す情報である幾何情報を生成する生成手段と、
前記クエリ特徴点を、前記モデル特徴点のクラスタリングと同じ手法でクラスタリングするクラスタリング手段と、
前記基準点と同じクラスタに属する前記モデル特徴点を前記基準点の最近傍候補とするとともに、前記従属点と同じクラスタに属する前記モデル特徴点を前記従属点の最近傍候補とし、それぞれの前記従属点の最近傍候補の位置を基準として、前記幾何情報により特定される前記基準点があるとされる位置に、前記基準点の最近傍候補があるか否かを判定し、判定結果に応じて、前記基準点の最近傍候補となる前記モデル特徴点を補正する補正手段と、
前記第１のセットと、補正後の前記基準点の最近傍候補と前記従属点の最近傍候補から構成される第２のセットとの類似度を各特徴点の特徴量に基づいて算出し、前記第１のセットの最近傍となる前記第２のセットを決定する類似度算出手段と
を備える認識装置。
【請求項２】
前記補正手段は、前記幾何情報により特定される前記基準点の最近傍候補があるとされる位置に前記基準点の最近傍候補がないと判定した場合、その位置に、前記基準点の最近傍候補となる前記モデル特徴点を追加する
請求項１に記載の認識装置。
【請求項３】
前記補正手段は、前記幾何情報により特定される前記基準点の最近傍候補があるとされる位置に前記基準点の最近傍候補がないと判定した場合であって、その位置の前記モデル特徴点に従属する前記従属点の最近傍候補の数が所定の数より多いとき、前記基準点の最近傍候補となる前記モデル特徴点を追加する
請求項２に記載の認識装置。
【請求項４】
前記補正手段は、さらに、前記幾何情報により特定される前記基準点があるとされる位置に前記基準点の最近傍候補があると判定した場合であって、その位置の前記モデル特徴点に従属する前記従属点の最近傍候補の数が所定の数より少ないとき、前記基準点の最近傍候補を削除する
請求項３に記載の認識装置。
【請求項５】
前記クエリ特徴点の特徴量を表すクエリ特徴量ベクトルと、前記クエリ特徴量ベクトルと次元数が同じベクトルであるLSHのハッシュ関数ベクトルとの内積値が閾値以上であるか否かに応じて、前記クエリ特徴量ベクトルを１と０の二値のうちの一方の値に量子化する量子化手段をさらに備え、
前記クラスタリング手段は、
前記クエリ特徴点を、それぞれの前記ハッシュ関数ベクトルを用いて得られた前記クエリ特徴量ベクトルの量子化後の値の組み合わせにより識別されるクラスタに属する特徴点としてクラスタリングする
請求項１に記載の認識装置。
【請求項６】
特徴量に基づいてクラスタリングすることによって決定された、モデルデータの特徴点であるモデル特徴点が属するクラスタの情報と、前記モデル特徴点の特徴量の情報を記憶し、
クエリとして入力されたデータの特徴点であるクエリ特徴点の特徴量を抽出し、
基準となる１つの前記クエリ特徴点である基準点と、前記基準点に従属する１つまたは複数の前記クエリ特徴点である従属点とから構成される前記クエリ特徴点の第１のセットを決定し、前記第１のセット毎に、前記基準点の位置を基準とする、それぞれの前記従属点の位置を表す情報である幾何情報を生成し、
前記クエリ特徴点を、前記モデル特徴点のクラスタリングと同じ手法でクラスタリングし、
前記基準点と同じクラスタに属する前記モデル特徴点を前記基準点の最近傍候補とするとともに、前記従属点と同じクラスタに属する前記モデル特徴点を前記従属点の最近傍候補とし、それぞれの前記従属点の最近傍候補の位置を基準として、前記幾何情報により特定される前記基準点があるとされる位置に、前記基準点の最近傍候補があるか否かを判定し、判定結果に応じて、前記基準点の最近傍候補となる前記モデル特徴点を補正し、
前記第１のセットと、補正後の前記基準点の最近傍候補と前記従属点の最近傍候補から構成される第２のセットとの類似度を各特徴点の特徴量に基づいて算出し、前記第１のセットの最近傍となる前記第２のセットを決定する
ステップを含む認識方法。
【請求項７】
特徴量に基づいてクラスタリングすることによって決定された、モデルデータの特徴点であるモデル特徴点が属するクラスタの情報と、前記モデル特徴点の特徴量の情報を記憶し、
クエリとして入力されたデータの特徴点であるクエリ特徴点の特徴量を抽出し、
基準となる１つの前記クエリ特徴点である基準点と、前記基準点に従属する１つまたは複数の前記クエリ特徴点である従属点とから構成される前記クエリ特徴点の第１のセットを決定し、前記第１のセット毎に、前記基準点の位置を基準とする、それぞれの前記従属点の位置を表す情報である幾何情報を生成し、
前記クエリ特徴点を、前記モデル特徴点のクラスタリングと同じ手法でクラスタリングし、
前記基準点と同じクラスタに属する前記モデル特徴点を前記基準点の最近傍候補とするとともに、前記従属点と同じクラスタに属する前記モデル特徴点を前記従属点の最近傍候補とし、それぞれの前記従属点の最近傍候補の位置を基準として、前記幾何情報により特定される前記基準点があるとされる位置に、前記基準点の最近傍候補があるか否かを判定し、判定結果に応じて、前記基準点の最近傍候補となる前記モデル特徴点を補正し、
前記第１のセットと、補正後の前記基準点の最近傍候補と前記従属点の最近傍候補から構成される第２のセットとの類似度を各特徴点の特徴量に基づいて算出し、前記第１のセットの最近傍となる前記第２のセットを決定する
ステップを含む処理をコンピュータに実行させるプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、認識装置、認識方法、およびプログラムに関し、特に、モデル画像から選択された特徴点のセットとクエリ画像から選択された特徴点のセットとのセット同士のマッチングを迅速に行うことができるようにした認識装置、認識方法、およびプログラムに関する。
【背景技術】
【０００２】
局所特徴量を用いた一般物体認識の手法として、特許文献１には、モデル画像とクエリ画像から、ベース点と、単数あるいは複数のサポート点とからなる特徴点セットを複数抽出し、特徴点セット同士のマッチングを行う手法が開示されている。
【０００３】
例えばモデル画像のベース点は、モデル画像上に設定された特徴点のうちの基準となる特徴点であり、サポート点は、ベース点以外の特徴点であって、ベース点に従属して決定される特徴点である。モデル化時、各特徴点の特徴量を表す情報とともに、ベース点の位置を基準として、各サポート点の位置を表す情報である幾何情報が保存されるようになされている。
【０００４】
特許文献１に開示されている手法（以下、従来手法という）によれば、テクスチャの少ない物体の識別をロバストに行うことや、背景の影響を抑えて識別を行うことができるようになっている。
【０００５】
従来手法の実用化には計算の高速化が望ましい。例えば、局所特徴量を用いた物体認識を高速化させる方法として、非特許文献１に記載されるLSH(Locality Sensitive Hashing)に代表されるような、データベース検索を行う方法がある。
【０００６】
LSHは、クエリ画像のある特徴点が入力された場合に、その特徴点が属する部分集合であるモデル特徴点のクラスタを特定し、同じクラスタに含まれるモデル特徴点のみを対象にして類似度を計算するものである。類似度計算の回数を減らすことによって全ての特徴点間の類似度を計算する最近傍探索と較べて計算量を抑え、物体認識を高速に行うことができるようになっている。
【０００７】
非特許文献２には、ハイパーグラフを用いることによって、特徴点のセット単位でのマッチングを実現する手法が開示されている。
【先行技術文献】
【特許文献】
【０００８】
【特許文献１】特開２００８−７７６２５号公報
【非特許文献】
【０００９】
【非特許文献１】’Locality−sensitive hashing scheme based on p-stable distributions’, Mayur Datar, Piotr Indyk, Proceedings of the twentieth annual symposium on Computational geometry, pp. 253-262, 2004
【非特許文献２】A Tensor-Based Algorithm for High-Order Graph Matching’, Olivier Duchenne, Francis Bach, Inso Kweon, Jean Ponce, Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, 2009
【発明の概要】
【発明が解決しようとする課題】
【００１０】
従来手法にLSHを適用した場合、特徴点セットには複数の特徴点が含まれるため、LSHによって単純に各特徴点の最近傍が求まっても、セットとしての最近傍ではない可能性が高い。
【００１１】
また、ここで、従来手法に非特許文献２に開示されているハイパーグラフを用いる手法を適用することを考える。このハイパーグラフを用いる手法は、特徴点セットを構成する特徴点の数、およびその相対位置が一定であることが要求される。従って、この手法は、特徴点セットを構成する特徴点の数が可変であり、かつ、選択された特徴点の位置により柔軟に相対位置を規定する幾何情報を持つ従来手法の特徴点セットのマッチングには適用することができない。
【００１２】
すなわち、特徴点のセットを用いて物体を記述し、かつ物体の形状変化に対応するために特徴点セットを構成する特徴点の数を可変にするといったアルゴリズムの特性が、LSHや、ハイパーグラフを用いる手法を従来手法に適用することを困難なものにしている。
【００１３】
本発明はこのような状況に鑑みてなされたものであり、モデル画像から選択された特徴点のセットとクエリ画像から選択された特徴点のセットとのセット同士のマッチングを迅速に行うことができるようにするものである。
【課題を解決するための手段】
【００１４】
本発明の一側面の認識装置は、特徴量に基づいてクラスタリングすることによって決定された、モデルデータの特徴点であるモデル特徴点が属するクラスタの情報と、前記モデル特徴点の特徴量の情報を記憶する記憶手段と、クエリとして入力されたデータの特徴点であるクエリ特徴点の特徴量を抽出する抽出手段と、基準となる１つの前記クエリ特徴点である基準点と、前記基準点に従属する１つまたは複数の前記クエリ特徴点である従属点とから構成される前記クエリ特徴点の第１のセットを決定し、前記第１のセット毎に、前記基準点の位置を基準とする、それぞれの前記従属点の位置を表す情報である幾何情報を生成する生成手段と、前記クエリ特徴点を、前記モデル特徴点のクラスタリングと同じ手法でクラスタリングするクラスタリング手段と、前記基準点と同じクラスタに属する前記モデル特徴点を前記基準点の最近傍候補とするとともに、前記従属点と同じクラスタに属する前記モデル特徴点を前記従属点の最近傍候補とし、それぞれの前記従属点の最近傍候補の位置を基準として、前記幾何情報により特定される前記基準点があるとされる位置に、前記基準点の最近傍候補があるか否かを判定し、判定結果に応じて、前記基準点の最近傍候補となる前記モデル特徴点を補正する補正手段と、前記第１のセットと、補正後の前記基準点の最近傍候補と前記従属点の最近傍候補から構成される第２のセットとの類似度を各特徴点の特徴量に基づいて算出し、前記第１のセットの最近傍となる前記第２のセットを決定する類似度算出手段とを備える。
【００１５】
前記補正手段には、前記幾何情報により特定される前記基準点の最近傍候補があるとされる位置に前記基準点の最近傍候補がないと判定した場合、その位置に、前記基準点の最近傍候補となる前記モデル特徴点を追加させることができる。
【００１６】
前記補正手段には、前記幾何情報により特定される前記基準点の最近傍候補があるとされる位置に前記基準点の最近傍候補がないと判定した場合であって、その位置の前記モデル特徴点に従属する前記従属点の最近傍候補の数が所定の数より多いとき、前記基準点の最近傍候補となる前記モデル特徴点を追加させることができる。
【００１７】
前記補正手段には、さらに、前記幾何情報により特定される前記基準点があるとされる位置に前記基準点の最近傍候補があると判定した場合であって、その位置の前記モデル特徴点に従属する前記従属点の最近傍候補の数が所定の数より少ないとき、前記基準点の最近傍候補を削除させることができる。
【００１８】
前記クエリ特徴点の特徴量を表すクエリ特徴量ベクトルと、前記クエリ特徴量ベクトルと次元数が同じベクトルであるLSHのハッシュ関数ベクトルとの内積値が閾値以上であるか否かに応じて、前記クエリ特徴量ベクトルを１と０の二値のうちの一方の値に量子化する量子化手段をさらに設けることができる。この場合、前記クラスタリング手段には、前記クエリ特徴点を、それぞれの前記ハッシュ関数ベクトルを用いて得られた前記クエリ特徴量ベクトルの量子化後の値の組み合わせにより識別されるクラスタに属する特徴点としてクラスタリングさせることができる。
【００１９】
本発明の一側面の認識方法は、特徴量に基づいてクラスタリングすることによって決定された、モデルデータの特徴点であるモデル特徴点が属するクラスタの情報と、前記モデル特徴点の特徴量の情報を記憶し、クエリとして入力されたデータの特徴点であるクエリ特徴点の特徴量を抽出し、基準となる１つの前記クエリ特徴点である基準点と、前記基準点に従属する１つまたは複数の前記クエリ特徴点である従属点とから構成される前記クエリ特徴点の第１のセットを決定し、前記第１のセット毎に、前記基準点の位置を基準とする、それぞれの前記従属点の位置を表す情報である幾何情報を生成し、前記クエリ特徴点を、前記モデル特徴点のクラスタリングと同じ手法でクラスタリングし、前記基準点と同じクラスタに属する前記モデル特徴点を前記基準点の最近傍候補とするとともに、前記従属点と同じクラスタに属する前記モデル特徴点を前記従属点の最近傍候補とし、それぞれの前記従属点の最近傍候補の位置を基準として、前記幾何情報により特定される前記基準点があるとされる位置に、前記基準点の最近傍候補があるか否かを判定し、判定結果に応じて、前記基準点の最近傍候補となる前記モデル特徴点を補正し、前記第１のセットと、補正後の前記基準点の最近傍候補と前記従属点の最近傍候補から構成される第２のセットとの類似度を各特徴点の特徴量に基づいて算出し、前記第１のセットの最近傍となる前記第２のセットを決定するステップを含む。
【００２０】
本発明の一側面のプログラムは、特徴量に基づいてクラスタリングすることによって決定された、モデルデータの特徴点であるモデル特徴点が属するクラスタの情報と、前記モデル特徴点の特徴量の情報を記憶し、クエリとして入力されたデータの特徴点であるクエリ特徴点の特徴量を抽出し、基準となる１つの前記クエリ特徴点である基準点と、前記基準点に従属する１つまたは複数の前記クエリ特徴点である従属点とから構成される前記クエリ特徴点の第１のセットを決定し、前記第１のセット毎に、前記基準点の位置を基準とする、それぞれの前記従属点の位置を表す情報である幾何情報を生成し、前記クエリ特徴点を、前記モデル特徴点のクラスタリングと同じ手法でクラスタリングし、前記基準点と同じクラスタに属する前記モデル特徴点を前記基準点の最近傍候補とするとともに、前記従属点と同じクラスタに属する前記モデル特徴点を前記従属点の最近傍候補とし、それぞれの前記従属点の最近傍候補の位置を基準として、前記幾何情報により特定される前記基準点があるとされる位置に、前記基準点の最近傍候補があるか否かを判定し、判定結果に応じて、前記基準点の最近傍候補となる前記モデル特徴点を補正し、前記第１のセットと、補正後の前記基準点の最近傍候補と前記従属点の最近傍候補から構成される第２のセットとの類似度を各特徴点の特徴量に基づいて算出し、前記第１のセットの最近傍となる前記第２のセットを決定するステップを含む処理をコンピュータに実行させる。
【００２１】
本発明の一側面においては、特徴量に基づいてクラスタリングすることによって決定された、モデルデータの特徴点であるモデル特徴点が属するクラスタの情報と、前記モデル特徴点の特徴量の情報が記憶され、クエリとして入力されたデータの特徴点であるクエリ特徴点の特徴量が抽出される。また、基準となる１つの前記クエリ特徴点である基準点と、前記基準点に従属する１つまたは複数の前記クエリ特徴点である従属点とから構成される前記クエリ特徴点の第１のセットが決定され、前記第１のセット毎に、前記基準点の位置を基準とする、それぞれの前記従属点の位置を表す情報である幾何情報が生成され、前記クエリ特徴点が、前記モデル特徴点のクラスタリングと同じ手法でクラスタリングされる。さらに、前記基準点と同じクラスタに属する前記モデル特徴点を前記基準点の最近傍候補とするとともに、前記従属点と同じクラスタに属する前記モデル特徴点を前記従属点の最近傍候補とし、それぞれの前記従属点の最近傍候補の位置を基準として、前記幾何情報により特定される前記基準点があるとされる位置に、前記基準点の最近傍候補があるか否かが判定され、判定結果に応じて、前記基準点の最近傍候補となる前記モデル特徴点が補正される。前記第１のセットと、補正後の前記基準点の最近傍候補と前記従属点の最近傍候補から構成される第２のセットとの類似度が各特徴点の特徴量に基づいて算出され、前記第１のセットの最近傍となる前記第２のセットが決定される。
【発明の効果】
【００２２】
本発明によれば、モデル画像から選択された特徴点のセットとクエリ画像から選択された特徴点のセットとのセット同士のマッチングを迅速に行うことができる。
【図面の簡単な説明】
【００２３】
【図１】本発明の一実施形態に係る学習装置の構成例を示すブロック図である。
【図２】図１のインデックス作成部の構成例を示すブロック図である。
【図３】モデル特徴量ベクトルの量子化の例を示す図である。
【図４】量子化値の例を示す図である。
【図５】本発明の一実施形態に係る認識装置の構成例を示すブロック図である。
【図６】図５の認識部の構成例を示すブロック図である。
【図７】特徴点の決定の例を示す図である。
【図８】特徴点間の位置関係を示す図である。
【図９】特徴点の例を示す図である。
【図１０】特徴点の補正について説明する図である。
【図１１】特徴点の補正について説明する図１０に続く図である。
【図１２】特徴点の他の補正について説明する図である。
【図１３】特徴点の他の補正について説明する図１２に続く図である。
【図１４】学習装置の学習処理について説明するフローチャートである。
【図１５】図１４のステップＳ４において行われるインデックス作成処理について説明するフローチャートである。
【図１６】認識装置の認識処理について説明するフローチャートである。
【図１７】図１６のステップＳ２５において行われる最近傍候補選択処理について説明するフローチャートである。
【図１８】図１６のステップＳ２６において行われる最近傍候補補正処理について説明するフローチャートである。
【図１９】コンピュータの構成例を示すブロック図である。
【発明を実施するための形態】
【００２４】
［学習装置の構成例］
図１は、本発明の一実施形態に係る学習装置の構成例を示すブロック図である。
【００２５】
KNNマッチングなどの最近傍探索をLSHによって行う処理は、オフラインフェーズとしての学習処理と、オンラインフェーズとしての認識処理とからなる。図１の学習装置１は学習処理を行う装置である。
【００２６】
学習装置１はコンピュータにより構成される。図１に示す機能部のうちの少なくとも一部は、学習装置１を構成するコンピュータのCPUにより所定のプログラムが実行されることによって実現される。
【００２７】
図１に示すように、学習装置１は、画像処理部１１、特徴量抽出部１２、インデックス作成部１３、ハッシュ関数記憶部１４、およびモデル辞書記憶部１５から構成される。画像処理部１１に対しては、認識させようとする物体の画像であるモデル画像が入力される。
【００２８】
画像処理部１１は、モデル画像をグレースケールの画像に変換する処理、グレースケールのモデル画像に基づいてエッジ画像を生成する処理、多重解像度処理などの初期処理を行う。画像処理部１１は、初期処理によって得られたモデル画像のデータを特徴量抽出部１２に出力する。
【００２９】
特徴量抽出部１２は、モデル画像のエッジ上の各点を特徴点として決定する。例えば、特徴量抽出部１２は、多重解像度処理によって得られた解像度の異なる各画像に含まれる、特徴点に対応する位置の画素の情報を特徴量（局所特徴量）として抽出する。
【００３０】
特徴量抽出部１２は、抽出した特徴量を表す特徴量ベクトルの情報をモデル辞書記憶部１５に記憶させるとともに、インデックス作成部１３に出力する。
【００３１】
以下、適宜、モデル画像の特徴点をモデル特徴点といい、モデル特徴点の特徴量を表す特徴量ベクトルをモデル特徴量ベクトルという。
【００３２】
インデックス作成部１３は、ハッシュ関数記憶部１４に記憶されているLSHのハッシュ関数を読み出し、読み出したハッシュ関数を用いてモデル特徴量ベクトルを量子化する。１つのハッシュ関数を用いることによって、１つの特徴量ベクトルは０と１のうちのいずれかの値に量子化される。
【００３３】
また、インデックス作成部１３は、モデル特徴点を、モデル特徴量ベクトルに複数のハッシュ関数を適用してそれぞれ求められた量子化値の組み合わせをキーとするクラスタに属する特徴点としてクラスタリングする。
【００３４】
インデックス作成部１３は、それぞれのモデル特徴点と、モデル特徴点が属するクラスタの識別情報であるキーを対応付けた情報であるインデックス情報を作成し、モデル辞書記憶部１５に記憶させる。インデックス作成部１３によるモデル特徴量ベクトルの量子化とクラスタリングについては後述する。
【００３５】
ハッシュ関数記憶部１４は、予め生成された、複数のLSHのハッシュ関数を記憶する。LSHのハッシュ関数の生成については例えば非特許文献１に記載されている。
【００３６】
モデル辞書記憶部１５は、特徴量抽出部１２により抽出されたモデル特徴量ベクトルの情報と、インデックス作成部１３により作成されたインデックス情報を含むモデル辞書を記憶する。モデル辞書記憶部１５に記憶されたモデル辞書は、物体認識を実際に行う認識装置に提供される。学習装置１から認識装置に対するモデル辞書の提供は、有線または無線による通信によって、または記録媒体を介して行われる。
【００３７】
図２は、図１のインデックス作成部１３の構成例を示すブロック図である。
【００３８】
図２に示すように、インデックス作成部１３は、量子化部２１とクラスタリング部２２から構成される。
【００３９】
量子化部２１は、ハッシュ関数記憶部１４に記憶されているハッシュ関数を、特徴量抽出部１２から供給されたモデル特徴量ベクトルに適用してハッシュ値を算出する。
【００４０】
ハッシュ関数記憶部１４に記憶されているハッシュ関数は、モデル特徴量ベクトルと次元数が同じベクトル（ハッシュ関数ベクトル）として表される。量子化部２１により算出されるハッシュ値は実数のベクトルとなり、ベクトルの各項はモデル特徴量ベクトルとハッシュ関数ベクトルの内積である。
【００４１】
量子化部２１は、ハッシュ値として算出した内積値と閾値を比較し、モデル特徴量ベクトルを１と０の二値のうちのいずれかの値に量子化する。例えば、量子化部２１は、モデル特徴量ベクトルとハッシュ関数ベクトルの内積値が閾値としての０以上の場合、モデル特徴量ベクトルを値１に量子化し、０未満の場合、モデル特徴量ベクトルを値０に量子化する。
【００４２】
図３は、モデル特徴量ベクトルの量子化の例を示す図である。
【００４３】
図３の特徴量ベクトルＡとＢはモデル特徴量ベクトルである。ハッシュ関数ベクトルｆは、複数用意されているもののうちの１つのハッシュ関数を表すベクトルである。ハッシュ関数ベクトルｆに対しては、ハッシュ関数ベクトルｆと直交する超平面が、特徴量空間を二分する閾値として設定されている。
【００４４】
例えば、特徴量ベクトルＡとハッシュ関数ベクトルｆの内積値が閾値である０以上の値として求められた場合、特徴量ベクトルＡは値１に量子化される。
【００４５】
また、特徴量ベクトルＢとハッシュ関数ベクトルｆの内積値が０未満の値として求められた場合、特徴量ベクトルＢは値０に量子化される。
【００４６】
量子化部２１は、以上のようなモデル特徴量ベクトルの量子化を、ハッシュ関数記憶部１４に記憶されているそれぞれのハッシュ関数ベクトルを用いて行う。量子化部２１により得られた量子化値はクラスタリング部２２に供給される。
【００４７】
クラスタリング部２２は、量子化部２１により得られた量子化値に基づいて、それぞれのモデル特徴点をクラスタリングする。
【００４８】
図４は、モデル特徴量ベクトルの量子化値の例を示す図である。
【００４９】
図４は、ハッシュ関数ベクトルｆ１乃至ｆ３をそれぞれ用いて得られた、モデル特徴量ベクトルである特徴量ベクトルＡとＢの量子化値の例を示している。
【００５０】
図４の例においては、ハッシュ関数ベクトルｆ１を用いた場合、特徴量ベクトルＡは値０に量子化されている。また、ハッシュ関数ベクトルｆ２を用いた場合、特徴量ベクトルＡは値１に量子化されている。ハッシュ関数ベクトルｆ３を用いた場合、特徴量ベクトルＡは値１に量子化されている。
【００５１】
同様に、ハッシュ関数ベクトルｆ１を用いた場合、特徴量ベクトルＢは値０に量子化されている。ハッシュ関数ベクトルｆ２を用いた場合、特徴量ベクトルＢは値０に量子化されている。ハッシュ関数ベクトルｆ３を用いた場合、特徴量ベクトルＢは値１に量子化されている。
【００５２】
この場合、クラスタリング部２２は、特徴量ベクトルＡにより特徴量が表されるモデル特徴点を、それぞれのハッシュ関数ベクトルを用いて算出された量子化値の組み合わせである［０，１，１］をキーとするクラスタに属する特徴点としてクラスタリングする。
【００５３】
また、クラスタリング部２２は、特徴量ベクトルＢにより特徴量が表されるモデル特徴点を、それぞれのハッシュ関数ベクトルを用いて算出された量子化値の組み合わせである［０，０，１］をキーとするクラスタに属する特徴点としてクラスタリングする。
【００５４】
クラスタリング部２２は、特徴量ベクトルＡにより特徴量が表されるモデル特徴点のIDと、［０，１，１］を対応付けたインデックス情報を作成する。また、クラスタリング部２２は、特徴量ベクトルＢにより特徴量が表されるモデル特徴点のIDと、［０，０，１］を対応付けたインデックス情報を作成する。
【００５５】
このように、インデックス作成部１３においては、各モデル特徴量ベクトルを対象として、モデル特徴量ベクトルとハッシュ関数ベクトルの内積値が算出され、閾値と比較することによって１と０の二値のうちの一方の値にモデル特徴量ベクトルが量子化される。また、量子化値に基づいてモデル特徴点がクラスタリングされる。
【００５６】
以上のようにして学習装置１により生成されたモデル辞書は認識装置に提供され、局所特徴量を用いた物体認識が行われる。
【００５７】
［認識装置の構成例］
図５は、本発明の一実施形態に係る認識装置の構成例を示すブロック図である。
【００５８】
図５の認識装置２は、局所特徴量を用いた物体認識をLSHによって行う装置である。
【００５９】
認識装置２もコンピュータにより構成される。図５に示す機能部のうちの少なくとも一部は、認識装置２を構成するコンピュータのCPUにより所定のプログラムが実行されることによって実現される。学習装置１と認識装置２が同じコンピュータにより実現されるようにしてもよいし、それぞれ異なるコンピュータにより実現されるようにしてもよい。
【００６０】
図５に示すように、認識装置２は、画像処理部３１、特徴量抽出部３２、認識部３３、ハッシュ関数記憶部３４、およびモデル辞書記憶部３５から構成される。画像処理部１１に対してはクエリ画像が入力される。
【００６１】
画像処理部３１は、図１の画像処理部１１と同様の処理を行う。すなわち、画像処理部３１は、クエリ画像に基づいて初期処理を行う。画像処理部３１は、初期処理を行うことによって得られたクエリ画像のデータを特徴量抽出部３２と認識部３３に出力する。
【００６２】
特徴量抽出部３２は、図１の特徴量抽出部１２と同様にして、クエリ画像の特徴点を決定し、それぞれの特徴点の特徴量を抽出する。
【００６３】
以下、適宜、クエリ画像の特徴点をクエリ特徴点といい、クエリ特徴点の特徴量を表す特徴量ベクトルをクエリ特徴量ベクトルという。
【００６４】
認識部３３は、画像処理部３１から供給されたクエリ画像から、ベース点と、単数あるいは複数のサポート点とからなる特徴点セットを複数決定し、特徴点セット同士のマッチングをLSHによって行う。
【００６５】
ベース点は、クエリ画像上に設定された特徴点のうちの基準となる特徴点であり、サポート点は、ベース点以外の特徴点であって、ベース点に従属して決定される特徴点である。認識部３３においては、ベース点の位置を基準として、各サポート点の位置を表す情報である幾何情報も生成される。
【００６６】
認識部３３は、特徴点セット同士のマッチングの結果に基づいて、例えばクエリ画像に含まれる物体がどのモデル画像に含まれる物体であるのかを認識し、認識結果を出力する。例えば、クエリ特徴点のセットとマッチした最近傍のモデル特徴点のセットの数などに基づいて物体が認識される。
【００６７】
ハッシュ関数記憶部３４は、学習装置１のハッシュ関数記憶部１４に記憶されているものと同じ複数のLSHのハッシュ関数を記憶する。
【００６８】
モデル辞書記憶部３５は、学習装置１から提供されたモデル辞書を記憶する。
【００６９】
図６は、図５の認識部３３の構成例を示すブロック図である。
【００７０】
図６に示すように、認識部３３は、特徴点セット決定部５１、量子化部５２、クラスタリング部５３、最近傍候補補正部５４、類似度算出部５５、および出力部５６から構成される。画像処理部３１から出力されたクエリ画像に初期処理を施して得られたデータは特徴点セット決定部５１に入力される。
【００７１】
特徴点セット決定部５１は、画像処理部３１から供給されたクエリ画像のデータに基づいて、ベース点と、単数あるいは複数のサポート点とからなる特徴点セットを複数決定する。
【００７２】
図７は、特徴点セットの例を示す図である。
【００７３】
例えば図７に示すように、特徴点セット決定部５１は、参照円Ｒを決定し、参照円Ｒと交差するエッジ画像Ｅ上の点を、ベース点ｂ、サポート点ｓ１，ｓ２，ｓ３とする。図７のエッジ画像Ｅは、クエリ画像に基づいて画像処理部３１により生成された画像である。特徴点セット決定部５１は、参照円Ｒの大きさと位置を変えて、ベース点とサポート点から構成されるクエリ特徴点のセットである特徴点セットを複数決定する。特徴点セットを構成するクエリ特徴点の数、およびそれらの位置関係は、参照円Ｒの位置と大きさが変わることに応じてセット毎に異なるものになる。
【００７４】
また、特徴点セット決定部５１は、特徴点セット毎に、ベース点の位置を基準とした、各サポート点の位置を表す情報である幾何情報を生成する。
【００７５】
図８は、幾何情報に含まれる情報の例を示す図である。
【００７６】
図８に示すように、サポート点ｓ１乃至ｓ３のベース点ｂからの相対的な位置（距離および角度）は、相対距離ｒ１，ｒ２，ｒ３、および、基準軸Ｉからの相対角度θ１，θ２，θ３で表される。幾何情報には、相対距離ｒ１，ｒ２，ｒ３、および、基準軸Ｉからの相対角度θ１，θ２，θ３を表す情報が含まれる。
【００７７】
特徴点セット決定部５１は、特徴点セットを構成するクエリ特徴点の情報を量子化部５２に出力する。また、特徴点セット決定部５１は、特徴点セットを構成するクエリ特徴点の情報と幾何情報を最近傍候補補正部５４に出力する。なお、以上のような特徴点セットの決定方法については、例えば、特開２００８−７７６２５号公報や特開２００８−２４３１７５号公報に記載されている。
【００７８】
量子化部５２は、特徴点セットを構成するクエリ特徴点を特徴点セット決定部５１から供給された情報に基づいて特定し、特定したクエリ特徴点の特徴を表すクエリ特徴量ベクトルを図２の量子化部２１と同様にして量子化する。特徴量抽出部３２から出力されたクエリ特徴量ベクトルの情報は量子化部５２に入力されている。
【００７９】
すなわち、量子化部５２は、ハッシュ関数記憶部３４に記憶されているハッシュ関数をクエリ特徴量ベクトルに適用してハッシュ値を算出する。
【００８０】
量子化部５２は、ハッシュ値として算出した内積値と閾値を比較し、クエリ特徴量ベクトルを１と０の二値のうちのいずれかの値に量子化する。例えば、量子化部５２は、クエリ特徴量ベクトルとハッシュ関数ベクトルの内積値が閾値としての０以上の場合、クエリ特徴量ベクトルを値１に量子化し、０未満の場合、クエリ特徴量ベクトルを値０に量子化する。
【００８１】
量子化部５２は、クエリ特徴量ベクトルの量子化を、ハッシュ関数記憶部３４に記憶されているそれぞれのハッシュ関数ベクトルを用いて行う。量子化部５２は、それぞれのハッシュ関数ベクトルを用いて得られた量子化値をクラスタリング部５３に出力する。
【００８２】
クラスタリング部５３は、図２のクラスタリング部２２と同様に、量子化部５２により得られた量子化値に基づいて、それぞれのクエリ特徴点をクラスタリングする。
【００８３】
例えばクエリ特徴量ベクトルがそれぞれ値０，１，１に量子化された場合、クラスタリング部５３は、そのクエリ特徴量ベクトルにより特徴量が表されるクエリ特徴点を、［０，１，１］をキーとするクラスタに属する特徴点としてクラスタリングする。
【００８４】
また、クエリ特徴量ベクトルがそれぞれ値０，０，１に量子化された場合、クラスタリング部５３は、そのクエリ特徴量ベクトルにより特徴量が表されるクエリ特徴点を、［０，０，１］をキーとするクラスタに属する特徴点としてクラスタリングする。
【００８５】
クラスタリング部５３は、クエリ特徴点が属するクラスタのキーの情報を最近傍候補補正部５４に出力する。
【００８６】
最近傍候補補正部５４は、クラスタリング部５３によるクラスタリングの結果に基づいて、特徴点セットを構成するクエリ特徴点が属するクラスタを特定する。また、最近傍候補補正部５４は、クエリ特徴点と同じクラスタに属するモデル特徴点を最近傍候補の特徴点とし、最近傍候補のモデル特徴点の補正を行う。モデル特徴点の補正については後述する。
【００８７】
最近傍候補補正部５４は、特徴量抽出部３２から供給された、それぞれの特徴点セットを構成するクエリ特徴点の特徴量ベクトルの情報を類似度算出部５５に出力する。
【００８８】
また、最近傍候補補正部５４は、最近傍候補のモデル特徴点の特徴量ベクトルの情報をモデル辞書記憶部３５から読み出し、類似度算出部５５に出力する。最近傍候補補正部５４から出力される情報には、補正によって追加された最近傍候補のモデル特徴点の特徴量ベクトルの情報も含まれる。
【００８９】
類似度算出部５５は、特徴点セット毎に、特徴点セットを構成するクエリ特徴点と、最近傍候補補正部５４により特定された最近傍候補のモデル特徴点との特徴量ベクトルの類似度に基づいて、特徴点のセット同士の類似度を算出する。
【００９０】
すなわち、類似度算出部５５においては、特徴点セットを構成するベース点と、ベース点の最近傍候補となるモデル特徴点との特徴量ベクトルの類似度、および、特徴点セットを構成するサポート点と、サポート点の最近傍候補となるモデル特徴点との特徴量ベクトルの類似度に基づいて、クエリ特徴点からなる特徴点セットと、それぞれのクエリ特徴点の最近傍候補からなるモデル特徴点のセットとの類似度が算出される。例えば、特徴点同士の特徴量ベクトルの類似度を足し合わせた値が、クエリ特徴点からなる特徴点セットと、最近傍候補からなるモデル特徴点のセットとの類似度として算出される。
【００９１】
類似度算出部５５は、類似度が高い順に所定の数の最近傍候補のモデル特徴点のセットを選択し、一般化ハフ変換やoutlier除去処理などの処理を行うことによって、最近傍のモデル特徴点のセットを選択する。類似度算出部５５は、最近傍のモデル特徴点のセットの情報を出力部５６に出力する。
【００９２】
出力部５６は、最近傍のモデル特徴点のセットの数などに基づいて、クエリ画像に含まれる物体がどのモデル画像に含まれる物体であるのかを認識し、認識結果を出力する。
【００９３】
［モデル特徴点の補正について］
図９乃至図１３を参照して、最近傍候補補正部５４により行われる最近傍候補のモデル特徴点の補正について説明する。最近傍候補のモデル特徴点の補正は、それぞれの特徴点セットを対象にして行われる。
【００９４】
図９は、特徴点セットを構成するクエリ特徴点と、それぞれのクエリ特徴点の最近傍候補となるモデル特徴点の例を示す図である。
【００９５】
図９の左側は、クエリ画像の特徴点であるクエリ特徴点の例を示し、右側は、モデル画像の特徴点であるモデル特徴点の例を示す。図９の左側に示す、ベース点ｂ、サポート点ｓ１およびｓ２から構成される特徴点セットを対象にして処理を行う場合について説明する。
【００９６】
ベース点ｂ、サポート点ｓ１およびｓ２は特徴点セット決定部５１により決定される。特徴点セット決定部５１から供給される幾何情報には、ベース点ｂの位置を基準とした、サポート点ｓ１の位置を表す情報と、サポート点ｓ２の位置を表す情報が含まれている。ベース点ｂ、サポート点ｓ１およびｓ２のそれぞれのクエリ特徴点が、どのクラスタに属する特徴点であるのかはクラスタリング部５３により決定されている。
【００９７】
この場合、最近傍候補補正部５４は、ベース点ｂと同じクラスタに属するモデル特徴点をモデル辞書記憶部３５に記憶されているインデックス情報に基づいて特定し、特定したモデル特徴点を、ベース点ｂの最近傍候補とする。
【００９８】
また、最近傍候補補正部５４は、サポート点ｓ１とｓ２のそれぞれのクエリ特徴点と同じクラスタに属するモデル特徴点をインデックス情報に基づいて特定し、特定したモデル特徴点を、サポート点ｓ１とｓ２のそれぞれの最近傍候補とする。
【００９９】
図９の右側に示すモデル特徴点ｂ１とｂ２はベース点ｂの最近傍候補である。また、モデル特徴点ｓ１−１，ｓ１−２，ｓ１−３は、それぞれ、サポート点ｓ１の最近傍候補である。モデル特徴点ｓ２−１，ｓ２−２，ｓ２−３は、それぞれ、サポート点ｓ２の最近傍候補である。
【０１００】
以下、適宜、ベース点の最近傍候補のモデル特徴点をベース点候補といい、サポート点の最近傍候補のモデル特徴点をサポート点候補という。
【０１０１】
最近傍候補補正部５４は、それぞれのサポート点候補に注目し、サポート点候補の位置を基準として、幾何情報により特定されるベース点があるとされる位置に、ベース点候補があるか否かを判定する。
【０１０２】
図１０は、図９の右側のベース点候補、サポート点候補を示す図である。
【０１０３】
はじめに、最近傍候補補正部５４は、例えばサポート点候補ｓ１−１に注目する。最近傍候補補正部５４は、サポート点候補ｓ１−１の位置を基準として、ベース点ｂの最近傍候補があるとされる矢印＃１の先の位置に、ベース点候補があるか否かを判定する。
【０１０４】
図１０の例においては、その位置にはベース点候補ｂ２があるものとして判定される。矢印＃１の先の位置は、幾何情報により表される、ベース点ｂとサポート点ｓ１の位置関係に基づいて特定される。この時点で、ベース点候補ｂ２の位置の得票数は１になる。
【０１０５】
また、最近傍候補補正部５４は、サポート点候補ｓ２−１に注目する。最近傍候補補正部５４は、サポート点候補ｓ２−１の位置を基準として、ベース点ｂの最近傍候補があるとされる矢印＃２の先の位置に、ベース点候補があるか否かを判定する。
【０１０６】
図１０の例においては、その位置にはベース点候補ｂ２があるものとして判定される。矢印＃２の先の位置は、幾何情報により表される、ベース点ｂとサポート点ｓ２の位置関係に基づいて特定される。この時点で、ベース点候補ｂ２の位置の得票数は２になる。
【０１０７】
同様に、最近傍候補補正部５４は、サポート点候補ｓ１−２に注目する。最近傍候補補正部５４は、サポート点候補ｓ１−２の位置を基準として、ベース点ｂの最近傍候補があるとされる矢印＃３の先の位置に、ベース点候補があるか否かを判定する。
【０１０８】
図１０の例においては、その位置にはベース点候補ｂ１があるものとして判定される。矢印＃３の先の位置は、幾何情報により表される、ベース点ｂとサポート点ｓ１の位置関係に基づいて特定される。この時点で、ベース点候補ｂ１の位置の得票数は１になる。
【０１０９】
また、最近傍候補補正部５４は、サポート点候補ｓ２−２に注目する。最近傍候補補正部５４は、サポート点候補ｓ２−２の位置を基準として、ベース点ｂの最近傍候補があるとされる矢印＃４の先の位置に、ベース点候補があるか否かを判定する。
【０１１０】
図１０の例においては、その位置にはベース点候補ｂ１があるものとして判定される。矢印＃４の先の位置は、幾何情報により表される、ベース点ｂとサポート点ｓ２の位置関係に基づいて特定される。この時点で、ベース点候補ｂ１の位置の得票数は２になる。
【０１１１】
最近傍候補補正部５４は、サポート点候補ｓ１−３に注目する。最近傍候補補正部５４は、サポート点候補ｓ１−３の位置を基準として、ベース点ｂの最近傍候補があるとされる矢印＃５の先の位置ｐ１に、ベース点候補があるか否かを判定する。
【０１１２】
図１０の例においては、位置ｐ１にはベース点候補がないものとして判定される。破線の丸印はモデル特徴点がないことを表す。矢印＃５の先の位置ｐ１は、幾何情報により表される、ベース点ｂとサポート点ｓ１の位置関係に基づいて特定される。この時点で、位置ｐ１の得票数は１になる。
【０１１３】
また、最近傍候補補正部５４は、サポート点候補ｓ２−３に注目する。最近傍候補補正部５４は、サポート点候補ｓ２−３の位置を基準として、ベース点ｂの最近傍候補があるとされる矢印＃６の先の位置ｐ１に、ベース点候補があるか否かを判定する。
【０１１４】
図１０の例においては、位置ｐ１にはベース点候補がないものとして判定される。矢印＃６の先の位置ｐ１は、幾何情報により表される、ベース点ｂとサポート点ｓ２の位置関係に基づいて特定される。この時点で、位置ｐ１の得票数は２になる。
【０１１５】
この場合、最近傍候補補正部５４は、図１１に示すように、サポート点候補ｓ１−３の位置を基準としてベース点の最近傍候補があるとされる位置であり、かつ、サポート点候補ｓ２−３の位置を基準としてベース点の最近傍候補があるとされる位置である位置ｐ１に、ベース点ｂの最近傍候補であるベース点候補ｂ３を追加する。
【０１１６】
すなわち、最近傍候補補正部５４は、幾何情報により特定される、ベース点候補があるとされる位置にベース点候補が実際にない場合、その位置に、ベース点候補となるモデル特徴点を追加する。得票数が所定の数以上ある場合（同じ位置にベース点候補があるとするサポート点候補が所定の数以上ある場合）に、ベース点候補となるモデル特徴点が追加されるようにしてもよい。
【０１１７】
最近傍候補補正部５４は、モデル辞書記憶部３５に記憶されているインデックス情報を更新し、新たに追加したベース点候補ｂ３を、ベース点ｂ、ベース点候補ｂ１，ｂ２と同じクラスタに属するモデル特徴点として追加登録する。
【０１１８】
また、最近傍候補補正部５４は、ベース点候補ｂ３のモデル特徴量ベクトルの情報をモデル辞書記憶部３５に記憶させる。ベース点候補ｂ３の特徴量を表すモデル特徴量ベクトルの情報は、例えば、他のベース点候補のモデル特徴量ベクトルの情報に基づく予測によって求められる。
【０１１９】
図１２は、ベース点候補、サポート点候補の他の例を示す図である。
【０１２０】
図１２の例においては、ベース点ｂの最近傍候補としてベース点候補ｂ１，ｂ２，ｂ３があり、サポート点ｓ１の最近傍候補としてサポート点候補ｓ１−１，ｓ１−２，ｓ１−３があるものとされている。
【０１２１】
また、サポート点ｓ２の最近傍候補としてサポート点候補ｓ２−２とｓ２−３があるものとされている。図１２の例においては、サポート点候補ｓ２の最近傍候補として、破線で示す位置に図１０のサポート点候補ｓ２−１がない。
【０１２２】
このような状態で最近傍候補を補正する場合について説明する。
【０１２３】
最近傍候補補正部５４は、例えばサポート点候補ｓ１−１に注目する。最近傍候補補正部５４は、サポート点候補ｓ１−１の位置を基準として、ベース点ｂの最近傍候補があるとされる矢印＃１の先の位置ｐ２に、ベース点候補があるか否かを判定する。
【０１２４】
図１２の例においては、位置ｐ２にはベース点候補ｂ２があるものとして判定される。この時点で、ベース点候補ｂ２の位置ｐ２の得票数は１になる。
【０１２５】
また、最近傍候補補正部５４は、サポート点候補ｓ１−２に注目する。最近傍候補補正部５４は、サポート点候補ｓ１−２の位置を基準として、ベース点ｂの最近傍候補があるとされる矢印＃３の先の位置に、ベース点候補があるか否かを判定する。
【０１２６】
図１２の例においては、その位置にはベース点候補ｂ１があるものとして判定される。この時点で、ベース点候補ｂ１の位置の得票数は１になる。
【０１２７】
また、最近傍候補補正部５４は、サポート点候補ｓ２−２に注目する。最近傍候補補正部５４は、サポート点候補ｓ２−２の位置を基準として、ベース点ｂの最近傍候補があるとされる矢印＃４の先の位置に、ベース点候補があるか否かを判定する。
【０１２８】
図１２の例においては、その位置にはベース点候補ｂ１があるものとして判定される。この時点で、ベース点候補ｂ１の位置の得票数は２になる。
【０１２９】
最近傍候補補正部５４は、サポート点候補ｓ１−３に注目する。最近傍候補補正部５４は、サポート点候補ｓ１−３の位置を基準として、ベース点ｂの最近傍候補があるとされる矢印＃５の先の位置に、ベース点候補があるか否かを判定する。
【０１３０】
図１２の例においては、その位置にはベース点候補ｂ３があるものとして判定される。この時点で、ベース点候補ｂ３の位置の得票数は１になる。
【０１３１】
また、最近傍候補補正部５４は、サポート点候補ｓ２−３に注目する。最近傍候補補正部５４は、サポート点候補ｓ２−３の位置を基準として、ベース点ｂの最近傍候補があるとされる矢印＃６の先の位置に、ベース点候補があるか否かを判定する。
【０１３２】
図１２の例においては、その位置にはベース点候補ｂ３があるものとして判定される。この時点で、ベース点候補ｂ３の位置の得票数は２になる。
【０１３３】
この場合、最近傍候補補正部５４は、図１３に示すように、サポート点候補ｓ１−１の位置を基準としてベース点の最近傍候補があるとされる位置ではあるが、他のサポート点候補の位置を基準としてベース点の最近傍候補があるとはされていない位置である位置ｐ２にあるベース点候補ｂ２を削除する。
【０１３４】
すなわち、最近傍候補補正部５４は、幾何情報により特定される、ベース点候補があるとされる位置にベース点候補が実際にあるが、その位置にベース点候補があるとするサポート点候補の数が所定の数より少ない場合（得票数が少ない場合）、そのベース点候補を削除する。
【０１３５】
最近傍候補補正部５４は、モデル辞書記憶部３５に記憶されているインデックス情報を更新し、ベース点候補ｂ２を、ベース点ｂ、ベース点候補ｂ１，ｂ３と同じクラスタから削除する。
【０１３６】
LSHによって各特徴点をクラスタリングする場合、特徴量ベクトルの量子化誤差などにより、ベース点の最近傍であるモデル特徴点が、ベース点のクエリ特徴点と同じクラスタに含まれていない場合がある。ベース点候補のモデル特徴点を以上のようにして追加することによって、そのように、ベース点のクエリ特徴点と同じクラスタから脱落したモデル特徴点をベース点候補として含ませることが可能になる。
【０１３７】
また、特徴量ベクトルの量子化誤差などにより、ベース点の最近傍ではないモデル特徴点が、ベース点のクエリ特徴点と同じクラスタに含まれている場合がある。ベース点候補のモデル特徴点を以上のようにして削除することによって、そのように、ベース点のクエリ特徴点と同じクラスタに誤って含まれたモデル特徴点を、ベース点候補から削除することが可能になる。
【０１３８】
これにより、LSHを採用した場合であっても、全ての特徴点間の類似度を実際に算出する完全な最近傍探索と較べてマッチングの精度を維持することができる。
【０１３９】
［装置の動作］
ここで、図１４のフローチャートを参照して、学習装置１の学習処理について説明する。
【０１４０】
図１４の処理は、モデル画像が学習装置１に入力されたときに開始される。
【０１４１】
ステップＳ１において、画像処理部１１は初期処理を行う。
【０１４２】
ステップＳ２において、特徴量抽出部１２は、初期処理によって得られたエッジ画像の各点をモデル特徴点として決定する。
【０１４３】
ステップＳ３において、特徴量抽出部１２は、それぞれのモデル特徴点の特徴量を抽出し、抽出した特徴量を表すモデル特徴量ベクトルの情報をモデル辞書記憶部１５に記憶させる。
【０１４４】
ステップＳ４において、インデックス作成部１３によりインデックス作成処理が行われる。インデックス作成処理においては、モデル特徴量ベクトルが量子化され、量子化値に基づいてモデル特徴点がクラスタリングされる。インデックス作成処理が終了した後、処理は終了される。
【０１４５】
次に、図１５のフローチャートを参照して、図１４のステップＳ４において行われるインデックス作成処理について説明する。
【０１４６】
図１５の処理は、１つのモデル特徴点の特徴量を表すモデル特徴量ベクトルの情報が特徴量抽出部１２から供給される毎に行われる。
【０１４７】
ステップＳ１１において、量子化部２１は、ハッシュ関数記憶部１４に記憶されているハッシュ関数を１つ選択する。
【０１４８】
ステップＳ１２において、量子化部２１は、モデル特徴量ベクトルと、選択したハッシュ関数ベクトルとの内積値を算出する。
【０１４９】
ステップＳ１３において、量子化部２１は、算出した内積値が閾値としての０以上である場合、モデル特徴量ベクトルを値１に量子化し、０未満の場合、モデル特徴量ベクトルを値０に量子化する。
【０１５０】
ステップＳ１４において、量子化部２１は、ハッシュ関数記憶部１４に記憶されている全てのハッシュ関数を選択したか否かを判定する。量子化部２１は、まだ選択していないハッシュ関数があるとステップＳ１４において判定した場合、ステップＳ１１に戻り、違うハッシュ関数を選択して以上の処理を繰り返す。
【０１５１】
一方、全てのハッシュ関数を選択したとステップＳ１４において判定された場合、ステップＳ１５において、クラスタリング部２２は、モデル特徴点を、量子化値の組み合わせをキーとするクラスタに属する特徴点としてクラスタリングする。また、クラスタリング部２２は、モデル特徴点のIDと、キーを対応付けたインデックス情報を作成し、記憶させる。
【０１５２】
以上の処理が、特徴量抽出部１２により抽出された全てのモデル特徴点を対象として行われる。その後、図１４のステップＳ４に戻り、それ以降の処理が行われる。
【０１５３】
次に、図１６のフローチャートを参照して、認識装置２の認識処理について説明する。
【０１５４】
図１６の処理は、クエリ画像が認識装置２に入力されたときに開始される。
【０１５５】
ステップＳ２１において、画像処理部３１は初期処理を行う。
【０１５６】
ステップＳ２２において、特徴量抽出部３２は、初期処理によって得られたエッジ画像の各点をクエリ特徴点として決定する。
【０１５７】
ステップＳ２３において、特徴量抽出部３２は、それぞれのクエリ特徴点の特徴量を抽出し、抽出した特徴量を表すクエリ特徴量ベクトルの情報を出力する。
【０１５８】
ステップＳ２４において、認識部３３の特徴点セット決定部５１は、図７を参照して説明したようにして、ベース点と、単数あるいは複数のサポート点とからなる特徴点セットを複数決定する。また、特徴点セット決定部５１は、特徴点セット毎に、ベース点の位置を基準とした、各サポート点の位置を表す情報である幾何情報を生成する。
【０１５９】
ステップＳ２５において、量子化部５２およびクラスタリング部５３により最近傍候補選択処理が行われる。最近傍候補選択処理においては、クエリ特徴量ベクトルが量子化され、クエリ特徴点がクラスタリングされる。
【０１６０】
ステップＳ２６において、最近傍候補補正部５４により最近傍候補補正処理が行われる。最近傍候補補正処理により、最近傍候補となるモデル特徴点の追加や削除が行われる。
【０１６１】
ステップＳ２７において、類似度算出部５５は、特徴点セット毎に、特徴点セットを構成するクエリ特徴点と、最近傍候補のモデル特徴点との特徴量ベクトルの類似度に基づいて、特徴点のセット同士の類似度を算出する。
【０１６２】
ステップＳ２８において、類似度算出部５５は、類似度が高い順に所定の数の最近傍候補のモデル特徴点のセットを選択し、その中から、最近傍のモデル特徴点のセットを選択する。類似度の最も高い特徴点のセットが、最近傍のモデル特徴点のセットとして選択されるようにしてもよい。
【０１６３】
ステップＳ２９において、出力部５６は、最近傍のモデル特徴点のセットの数などに基づいて、クエリ画像に含まれる物体がどのモデル画像に含まれる物体であるのかを認識し、認識結果を出力する。その後、処理は終了される。
【０１６４】
次に、図１７のフローチャートを参照して、図１６のステップＳ２５において行われる最近傍候補選択処理について説明する。
【０１６５】
図１７の処理は、１つのクエリ特徴点の特徴量を表すクエリ特徴量ベクトルの情報が特徴量抽出部３２から供給される毎に行われる。
【０１６６】
ステップＳ４１において、認識部３３の量子化部５２は、ハッシュ関数記憶部３４に記憶されているハッシュ関数を１つ選択する。
【０１６７】
ステップＳ４２において、量子化部５２は、クエリ特徴量ベクトルと、選択したハッシュ関数ベクトルとの内積値を算出する。
【０１６８】
ステップＳ４３において、量子化部５２は、算出した内積値が閾値としての０以上である場合、クエリ特徴量ベクトルを値１に量子化し、０未満の場合、クエリ特徴量ベクトルを値０に量子化する。
【０１６９】
ステップＳ４４において、量子化部５２は、ハッシュ関数記憶部３４に記憶されている全てのハッシュ関数を選択したか否かを判定する。量子化部５２は、まだ選択していないハッシュ関数があるとステップＳ４４において判定した場合、ステップＳ４１に戻り、違うハッシュ関数を選択して以上の処理を繰り返す。
【０１７０】
一方、全てのハッシュ関数を選択したとステップＳ４４において判定された場合、ステップＳ４５において、クラスタリング部５３は、クエリ特徴点を、量子化値の組み合わせをキーとするクラスタに属する特徴点としてクラスタリングする。
【０１７１】
以上の処理が、特徴量抽出部３２により抽出された全てのクエリ特徴点を対象として行われる。図１６のステップＳ２５に戻り、それ以降の処理が行われる。
【０１７２】
次に、図１８のフローチャートを参照して、図１６のステップＳ２６において行われる最近傍候補補正処理について説明する。
【０１７３】
図１８の処理は、特徴点セット決定部５１により決定されたそれぞれの特徴点セットを対象として行われる。
【０１７４】
ステップＳ６１において、最近傍候補補正部５４は、処理対象の特徴点セットを構成するサポート点の最近傍候補であるサポート点候補のうちの１つのサポート点候補に注目する。
【０１７５】
ステップＳ６２において、最近傍候補補正部５４は、注目するサポート点候補の位置を基準として、幾何情報により特定されるベース点があるとされる位置に、ベース点候補があるか否かを確認する。最近傍候補補正部５４は、確認した位置にベース点候補がある場合、その位置の得票数を１だけ加算する。
【０１７６】
ステップＳ６３において、最近傍候補補正部５４は、全てのサポート点候補に注目したか否かを判定する。
【０１７７】
全てのサポート点候補に注目していないとステップＳ６３において判定した場合、ステップＳ６１に戻り、他のサポート点候補に注目して以上の処理が繰り返される。
【０１７８】
一方、全てのサポート点候補に注目したとステップＳ６３において判定した場合、ステップＳ６４において、最近傍候補補正部５４は、確認した位置に、ベース点候補が実際にあるか否かを判定する。
【０１７９】
ベース点候補が実際にあるとステップＳ６４において判定した場合、ステップＳ６５において、最近傍候補補正部５４は、得票数が所定の数より多いか否かを判定する。
【０１８０】
得票数が所定の数より少ないとステップＳ６５において判定した場合、ステップＳ６６において、最近傍候補補正部５４は、確認した位置にあるベース点候補を削除する。ベース点候補のモデル特徴点が削除された場合、または、ステップＳ６５において得票数が所定の数より多いと判定された場合、図１６のステップＳ２６に戻り、それ以降の処理が行われる。
【０１８１】
一方、確認した位置にベース点候補がないとステップＳ６４において判定した場合、ステップＳ６７において、最近傍候補補正部５４は、得票数が所定の数より多いか否かを判定する。
【０１８２】
得票数が所定の数より多いとステップＳ６７において判定した場合、ステップＳ６８において、最近傍候補補正部５４は、確認した位置にベース点候補となるモデル特徴点を追加する。ベース点候補となるモデル特徴点が追加された場合、または、ステップＳ６７において得票数が所定の数より少ないと判定された場合、図１６のステップＳ２６に戻り、それ以降の処理が行われる。
【０１８３】
以上の一連の処理により、物体認識をLSHによって行うことで計算量を減らし、マッチングの高速化が可能になる。また、マッチングの精度を維持することが可能になる。
【０１８４】
［コンピュータの構成例］
上述した一連の処理は、ハードウェアにより実行することもできるし、ソフトウェアにより実行することもできる。一連の処理をソフトウェアにより実行する場合には、そのソフトウェアを構成するプログラムが、専用のハードウェアに組み込まれているコンピュータ、または汎用のパーソナルコンピュータなどに、プログラム記録媒体からインストールされる。
【０１８５】
図１９は、上述した一連の処理をプログラムにより実行するコンピュータのハードウェアの構成例を示すブロック図である。
【０１８６】
CPU(Central Processing Unit)１０１、ROM(Read Only Memory)１０２、RAM(Random Access Memory)１０３は、バス１０４により相互に接続されている。
【０１８７】
バス１０４には、さらに、入出力インタフェース１０５が接続されている。入出力インタフェース１０５には、キーボード、マウスなどよりなる入力部１０６、ディスプレイ、スピーカなどよりなる出力部１０７が接続される。また、入出力インタフェース１０５には、ハードディスクや不揮発性のメモリなどよりなる記憶部１０８、ネットワークインタフェースなどよりなる通信部１０９、リムーバブルメディア１１１を駆動するドライブ１１０が接続される。
【０１８８】
以上のように構成されるコンピュータでは、CPU１０１が、例えば、記憶部１０８に記憶されているプログラムを入出力インタフェース１０５及びバス１０４を介してRAM１０３にロードして実行することにより、上述した一連の処理が行われる。
【０１８９】
CPU１０１が実行するプログラムは、例えばリムーバブルメディア１１１に記録して、あるいは、ローカルエリアネットワーク、インターネット、デジタル放送といった、有線または無線の伝送媒体を介して提供され、記憶部１０８にインストールされる。
【０１９０】
なお、コンピュータが実行するプログラムは、本明細書で説明する順序に沿って時系列に処理が行われるプログラムであっても良いし、並列に、あるいは呼び出しが行われたとき等の必要なタイミングで処理が行われるプログラムであっても良い。
【０１９１】
本発明の実施の形態は、上述した実施の形態に限定されるものではなく、本発明の要旨を逸脱しない範囲において種々の変更が可能である。
【符号の説明】
【０１９２】
１  学習装置，  ２  認識装置，  １１  画像処理部，  １２  特徴量抽出部，  １３  インデックス作成部，  １４  ハッシュ関数記憶部，  １５  モデル辞書記憶部，  ２１  量子化部，  ２２  クラスタリング部，  ３１  画像処理部，  ３２  特徴量抽出部，  ３３  認識部，  ３４  ハッシュ関数記憶部，  ３５  モデル辞書記憶部，  ５１  特徴点セット決定部，  ５２  量子化部，  ５３  クラスタリング部，  ５４  最近傍候補補正部，  ５５  類似度算出部，  ５６  出力部
【図１】
2011221688.tif 000003
【図２】
2011221688.tif 000004
【図３】
2011221688.tif 000005
【図４】
2011221688.tif 000006
【図５】
2011221688.tif 000007
【図６】
2011221688.tif 000008
【図７】
2011221688.tif 000009
【図８】
2011221688.tif 000010
【図９】
2011221688.tif 000011
【図１０】
2011221688.tif 000012
【図１１】
2011221688.tif 000013
【図１２】
2011221688.tif 000014
【図１３】
2011221688.tif 000015
【図１４】
2011221688.tif 000016
【図１５】
2011221688.tif 000017
【図１６】
2011221688.tif 000018
【図１７】
2011221688.tif 000019
【図１８】
2011221688.tif 000020
【図１９】
2011221688.tif 000021