(57)【要約】【課題】局所特徴量を用いた物体認識をLSHによって行う場合の認識精度を向上させることができるようにする。【解決手段】モデル画像から抽出されたモデル特徴点の特徴量を表すモデル特徴量ベクトルに対してハッシュ関数が適用され、モデル特徴量ベクトルが量子化される。量子化は、モデル特徴量ベクトルとハッシュ関数ベクトルの内積値が閾値と比較され、１と０の二値のうちの一方の値に量子化するようにして行われる。また、特徴量空間上でハッシュ関数ベクトルに設定されている量子化誤差マージンの範囲内にある場合、二値のうちの他方の値も量子化値として設定される。そのモデル特徴量ベクトルを有するモデル特徴点は、モデル特徴量ベクトルの量子化値に基づいて、複数のクラスタに属するようにクラスタリングされる。本発明は、局所特徴量を用いた物体認識を行う装置に適用することができる。【選択図】図３
2011221689.tif 000002
【特許請求の範囲】
【請求項１】
入力されたモデルデータの特徴点であるモデル特徴点を決定し、前記モデル特徴点の特徴量を抽出する抽出手段と、
前記モデル特徴点の特徴量を表すモデル特徴量ベクトルと、前記モデル特徴量ベクトルと次元数が同じベクトルであるLSHのハッシュ関数ベクトルとの内積値が閾値以上であるか否かに応じて、前記モデル特徴量ベクトルを１と０の二値のうちの一方の値に量子化し、前記モデル特徴量ベクトルが、特徴量空間において前記ハッシュ関数ベクトルに設定されたマージンの範囲内にある場合、１と０の二値のうちの他方の値を、前記モデル特徴量ベクトルの量子化後の値として設定する量子化手段と、
前記モデル特徴点を、それぞれの前記ハッシュ関数ベクトルを用いて得られた前記モデル特徴量ベクトルの量子化後の値の組み合わせにより識別されるクラスタに属する特徴点としてクラスタリングするクラスタリング手段と
を備える学習装置。
【請求項２】
前記モデル特徴量ベクトルの情報と、前記モデル特徴点が属するクラスタの情報とを対応付けて記憶する記憶手段をさらに備える
請求項１に記載の学習装置。
【請求項３】
前記マージンは、前記ハッシュ関数ベクトルと直交する超平面の近傍を含むように前記ハッシュ関数ベクトルに設定される
請求項１に記載の学習装置。
【請求項４】
入力されたモデルデータの特徴点であるモデル特徴点を決定し、
前記モデル特徴点の特徴量を抽出し、
前記モデル特徴点の特徴量を表すモデル特徴量ベクトルと、前記モデル特徴量ベクトルと次元数が同じベクトルであるLSHのハッシュ関数ベクトルとの内積値が閾値以上であるか否かに応じて、前記モデル特徴量ベクトルを１と０の二値のうちの一方の値に量子化し、
前記モデル特徴量ベクトルが、特徴量空間において前記ハッシュ関数ベクトルに設定されたマージンの範囲内にある場合、１と０の二値のうちの他方の値を、前記モデル特徴量ベクトルの量子化後の値として設定し、
前記モデル特徴点を、それぞれの前記ハッシュ関数ベクトルを用いて得られた前記モデル特徴量ベクトルの量子化後の値の組み合わせにより識別されるクラスタに属する特徴点としてクラスタリングする
ステップを含む学習方法。
【請求項５】
入力されたモデルデータの特徴点であるモデル特徴点を決定し、
前記モデル特徴点の特徴量を抽出し、
前記モデル特徴点の特徴量を表すモデル特徴量ベクトルと、前記モデル特徴量ベクトルと次元数が同じベクトルであるLSHのハッシュ関数ベクトルとの内積値が閾値以上であるか否かに応じて、前記モデル特徴量ベクトルを１と０の二値のうちの一方の値に量子化し、
前記モデル特徴量ベクトルが、特徴量空間において前記ハッシュ関数ベクトルに設定されたマージンの範囲内にある場合、１と０の二値のうちの他方の値を、前記モデル特徴量ベクトルの量子化後の値として設定し、
前記モデル特徴点を、それぞれの前記ハッシュ関数ベクトルを用いて得られた前記モデル特徴量ベクトルの量子化後の値の組み合わせにより識別されるクラスタに属する特徴点としてクラスタリングする
ステップを含む処理をコンピュータに実行させるプログラム。
【請求項６】
入力されたモデルデータの特徴点であるモデル特徴点を決定し、
前記モデル特徴点の特徴量を抽出し、
前記モデル特徴点の特徴量を表すモデル特徴量ベクトルと、前記モデル特徴量ベクトルと次元数が同じベクトルであるLSHのハッシュ関数ベクトルとの内積値が閾値以上であるか否かに応じて、前記モデル特徴量ベクトルを１と０の二値のうちの一方の値に量子化し、
前記モデル特徴量ベクトルが、特徴量空間において前記ハッシュ関数ベクトルに設定されたマージンの範囲内にある場合、１と０の二値のうちの他方の値を、前記モデル特徴量ベクトルの量子化後の値として設定し、
前記モデル特徴点を、それぞれの前記ハッシュ関数ベクトルを用いて得られた前記モデル特徴量ベクトルの量子化後の値の組み合わせにより識別されるクラスタに属する特徴点としてクラスタリングする
学習装置により生成された情報に基づいて処理を行う認識装置において、
クエリとして入力されたデータの特徴点であるクエリ特徴点を決定し、前記クエリ特徴点の特徴量を抽出する抽出手段と、
前記クエリ特徴点の特徴量を表すクエリ特徴量ベクトルと、前記ハッシュ関数ベクトルとの内積値が閾値以上であるか否かに応じて、前記クエリ特徴量ベクトルを１と０の二値のうちの一方の値に量子化する量子化手段と、
前記クエリ特徴点を、それぞれの前記ハッシュ関数ベクトルを用いて得られた前記クエリ特徴量ベクトルの量子化後の値の組み合わせにより識別されるクラスタに属する特徴点としてクラスタリングするクラスタリング手段と、
前記クエリ特徴点と、前記クエリ特徴点と同じクラスタに属するそれぞれの前記モデル特徴点との類似度を算出し、算出した類似度に基づいて、前記クエリ特徴点の最近傍となる前記モデル特徴点を決定する認識手段と
を備える認識装置。
【請求項７】
前記学習装置により生成された前記モデル特徴量ベクトルの情報と、前記モデル特徴点が属するクラスタの情報とを対応付けて記憶する記憶手段をさらに備える
請求項６に記載の認識装置。
【請求項８】
入力されたモデルデータの特徴点であるモデル特徴点を決定し、
前記モデル特徴点の特徴量を抽出し、
前記モデル特徴点の特徴量を表すモデル特徴量ベクトルと、前記モデル特徴量ベクトルと次元数が同じベクトルであるLSHのハッシュ関数ベクトルとの内積値が閾値以上であるか否かに応じて、前記モデル特徴量ベクトルを１と０の二値のうちの一方の値に量子化し、
前記モデル特徴量ベクトルが、特徴量空間において前記ハッシュ関数ベクトルに設定されたマージンの範囲内にある場合、１と０の二値のうちの他方の値を、前記モデル特徴量ベクトルの量子化後の値として設定し、
前記モデル特徴点を、それぞれの前記ハッシュ関数ベクトルを用いて得られた前記モデル特徴量ベクトルの量子化後の値の組み合わせにより識別されるクラスタに属する特徴点としてクラスタリングする
学習装置により生成された情報に基づいて行う認識方法において、
クエリとして入力されたデータの特徴点であるクエリ特徴点を決定し、
前記クエリ特徴点の特徴量を抽出し、
前記クエリ特徴点の特徴量を表すクエリ特徴量ベクトルと、前記ハッシュ関数ベクトルとの内積値が閾値以上であるか否かに応じて、前記クエリ特徴量ベクトルを１と０の二値のうちの一方の値に量子化し、
前記クエリ特徴点を、それぞれの前記ハッシュ関数ベクトルを用いて得られた前記クエリ特徴量ベクトルの量子化後の値の組み合わせにより識別されるクラスタに属する特徴点としてクラスタリングし、
前記クエリ特徴点と、前記クエリ特徴点と同じクラスタに属するそれぞれの前記モデル特徴点との類似度を算出し、算出した類似度に基づいて、前記クエリ特徴点の最近傍となる前記モデル特徴点を決定する
ステップを含む認識方法。
【請求項９】
入力されたモデルデータの特徴点であるモデル特徴点を決定し、
前記モデル特徴点の特徴量を抽出し、
前記モデル特徴点の特徴量を表すモデル特徴量ベクトルと、前記モデル特徴量ベクトルと次元数が同じベクトルであるLSHのハッシュ関数ベクトルとの内積値が閾値以上であるか否かに応じて、前記モデル特徴量ベクトルを１と０の二値のうちの一方の値に量子化し、
前記モデル特徴量ベクトルが、特徴量空間において前記ハッシュ関数ベクトルに設定されたマージンの範囲内にある場合、１と０の二値のうちの他方の値を、前記モデル特徴量ベクトルの量子化後の値として設定し、
前記モデル特徴点を、それぞれの前記ハッシュ関数ベクトルを用いて得られた前記モデル特徴量ベクトルの量子化後の値の組み合わせにより識別されるクラスタに属する特徴点としてクラスタリングする
学習装置により生成された情報に基づく処理をコンピュータに実行させるプログラムにおいて、
クエリとして入力されたデータの特徴点であるクエリ特徴点を決定し、
前記クエリ特徴点の特徴量を抽出し、
前記クエリ特徴点の特徴量を表すクエリ特徴量ベクトルと、前記ハッシュ関数ベクトルとの内積値が閾値以上であるか否かに応じて、前記クエリ特徴量ベクトルを１と０の二値のうちの一方の値に量子化し、
前記クエリ特徴点を、それぞれの前記ハッシュ関数ベクトルを用いて得られた前記クエリ特徴量ベクトルの量子化後の値の組み合わせにより識別されるクラスタに属する特徴点としてクラスタリングし、
前記クエリ特徴点と、前記クエリ特徴点と同じクラスタに属するそれぞれの前記モデル特徴点との類似度を算出し、算出した類似度に基づいて、前記クエリ特徴点の最近傍となる前記モデル特徴点を決定する
ステップを含む処理をコンピュータに実行させるプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、学習装置、学習方法、認識装置、認識方法、およびプログラムに関し、特に、局所特徴量を用いた認識をLSHによって行う場合の認識精度を向上させることができるようにした学習装置、学習方法、認識装置、認識方法、およびプログラムに関する。
【背景技術】
【０００２】
画像内に写る物体を認識する物体認識の方法として、物体を局所的な特徴量で記述し、局所特徴量同士のマッチングを行う方法がある。局所特徴量を用いた物体認識によれば、視点変化や画像内の物体の部分的な隠れがある場合などに対してもロバスト性を確保することが可能になる。
【０００３】
局所特徴量を用いた物体認識においては、多数のクエリ特徴点とモデル特徴点のマッチング（最近傍探索）が行われるため、全ての特徴量間の類似度を求めるための膨大な計算量が問題になる。ここで、クエリ特徴点は、物体認識時にクエリとして入力された画像であるクエリ画像から抽出された特徴点であり、モデル特徴点は、物体認識の前に行われる学習時に用いられる画像であるモデル画像から抽出された特徴点である。
【０００４】
そこで、局所特徴量を用いた物体認識を高速化させる方法として、近年、LSH(Locality Sensitive Hashing)などの方法が用いられている。
【０００５】
LSHを用いた場合、学習時、モデル特徴点の特徴量を表すモデル特徴量ベクトルにハッシュ関数を適用してハッシュ値が計算され、閾値処理によってモデル特徴量ベクトルの量子化が行われる。また、量子化後の値に応じて各モデル特徴点がクラスタリングされる。
【０００６】
図１は、特徴量ベクトルの量子化の例を示す図である。
【０００７】
図１の例においては、ハッシュ関数ベクトルｆ１乃至ｆ３が予め用意されている。ハッシュ関数は、それが適用される特徴量ベクトルと次元数が同じベクトルとして表される。
【０００８】
例えば、図１に示すように、モデル特徴量ベクトルとして特徴量ベクトルＡが抽出された場合、特徴量ベクトルＡと、ハッシュ関数ベクトルｆ１乃至ｆ３のそれぞれとの内積がハッシュ値として算出される。算出された内積値が閾値以上であるか否かに応じて、特徴量ベクトルが１と０のうちのいずれかの値に量子化される。
【０００９】
図１の例においては、ハッシュ関数ベクトルｆ１を用いることによって特徴量ベクトルＡが値０に量子化されている。また、ハッシュ関数ベクトルｆ２とｆ３を用いることによって、それぞれ、特徴量ベクトルＡが値１に量子化されている。
【００１０】
この場合、特徴量ベクトルＡにより特徴量が表されるモデル特徴点は、［０，１，１］をキーとするクラスタ（［０，１，１］によって識別されるクラスタ）に属する特徴点としてクラスタリングされる。
【００１１】
同様に、モデル特徴量ベクトルとして特徴量ベクトルＢが抽出された場合、特徴量ベクトルＢと、ハッシュ関数ベクトルｆ１乃至ｆ３のそれぞれとの内積が計算される。
【００１２】
図１の例においては、ハッシュ関数ベクトルｆ１を用いることによって特徴量ベクトルＢが値０に量子化されている。また、ハッシュ関数ベクトルｆ２とｆ３を用いることによって、それぞれ、特徴量ベクトルＢが値０と値１に量子化されている。
【００１３】
この場合、特徴量ベクトルＢにより特徴量が表されるモデル特徴点は、［０，０，１］をキーとするクラスタに属する特徴点としてクラスタリングされる。
【００１４】
学習時においては、全てのモデル特徴量ベクトルがこのようにして量子化され、量子化結果に基づいてモデル特徴点がクラスタリングされる。
【００１５】
一方、認識時、図１を参照して説明した処理と同様の処理によって、クエリ特徴点の特徴量を表すクエリ特徴量ベクトルにハッシュ関数を適用してハッシュ値が計算され、閾値処理によってクエリ特徴量ベクトルの量子化が行われる。
【００１６】
また、量子化後の値に応じて各クエリ特徴点がクラスタリングされ、同じクラスタに属するモデル特徴点との間で、特徴量ベクトルの類似度が計算され、最近傍のモデル特徴点が決定される。
【００１７】
クラスタリングが行われるため、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
【非特許文献２】Object Recognition Using Locality-Sensitive Hashing of Shape Contexts’, Andrea Frome, Jitendra Malik, Nearest-Neighbor Methods in Learning and Vision, Eds. G. Shakhnarovich, T. Darrell, P. Indyk, 2005
【発明の概要】
【発明が解決しようとする課題】
【００１９】
ハッシュ関数を適用して求められたハッシュ値が閾値以上であるか否かに応じて１と０の二値のうちのいずれかの値に特徴量ベクトルを量子化する方法では、量子化誤差が発生しやすく、それがもとで、近似最近傍探索を正しく行うことができないことがある。
【００２０】
図２は、特徴量ベクトルの量子化誤差について説明する図である。
【００２１】
例えば、図２の特徴量ベクトルＡとＢは、学習時にモデル画像から抽出されたモデル特徴点の特徴量を表す特徴量ベクトルである。ハッシュ関数ベクトルｆには、ハッシュ関数ベクトルｆと直交する超平面（特徴量空間が２次元で表される場合、直交する直線）が閾値として設定されている。
【００２２】
図２の例においては、特徴量ベクトルＡとハッシュ関数ベクトルｆの内積値は閾値としての０以上であり、特徴量ベクトルＡは値１に量子化されている。また、特徴量ベクトルＢとハッシュ関数ベクトルｆの内積値は閾値としての０未満であり、特徴量ベクトルＢは値０に量子化されている。
【００２３】
特徴量ベクトルＡとＢは特徴量空間上では接近しているにも関わらず、異なる値に量子化されている。これにより、特徴量ベクトルＡにより特徴量が表されるモデル特徴点と、特徴量ベクトルＢにより特徴量が表されるモデル特徴点がそれぞれ異なるクラスタに属する特徴点としてクラスタリングされてしまう。
【００２４】
閾値処理の対象になるハッシュ値はハッシュ関数ベクトルと特徴量ベクトルとの内積値であるため、以上のような量子化は、ハッシュ関数ベクトルと直交する超平面で特徴量空間を二分して、１と０の二値のうちのいずれかの値を設定する処理に相当する。
【００２５】
従って、切断面の両側の、切断面近辺に特徴量ベクトルがある場合（内積が０に近い場合）、たとえ接近していてもそれぞれの特徴量ベクトルが異なる値に量子化されてしまう。その結果、特徴量空間においては接近している特徴量ベクトルを有する特徴点同士が異なるクラスタに属する特徴点としてクラスタリングされてしまい、全ての特徴点間の類似度を求める完全な最近傍探索と比較してマッチング性能が低下する。
【００２６】
本発明はこのような状況に鑑みてなされたものであり、局所特徴量を用いた物体認識をLSHによって行う場合の認識精度を向上させることができるようにするものである。
【課題を解決するための手段】
【００２７】
本発明の一側面の学習装置は、入力されたモデルデータの特徴点であるモデル特徴点を決定し、前記モデル特徴点の特徴量を抽出する抽出手段と、前記モデル特徴点の特徴量を表すモデル特徴量ベクトルと、前記モデル特徴量ベクトルと次元数が同じベクトルであるLSHのハッシュ関数ベクトルとの内積値が閾値以上であるか否かに応じて、前記モデル特徴量ベクトルを１と０の二値のうちの一方の値に量子化し、前記モデル特徴量ベクトルが、特徴量空間において前記ハッシュ関数ベクトルに設定されたマージンの範囲内にある場合、１と０の二値のうちの他方の値を、前記モデル特徴量ベクトルの量子化後の値として設定する量子化手段と、前記モデル特徴点を、それぞれの前記ハッシュ関数ベクトルを用いて得られた前記モデル特徴量ベクトルの量子化後の値の組み合わせにより識別されるクラスタに属する特徴点としてクラスタリングするクラスタリング手段とを備える。
【００２８】
前記モデル特徴量ベクトルの情報と、前記モデル特徴点が属するクラスタの情報とを対応付けて記憶する記憶手段をさらに設けることができる。
【００２９】
前記マージンは、前記ハッシュ関数ベクトルと直交する超平面の近傍を含むように前記ハッシュ関数ベクトルに設定されるようにすることができる。
【００３０】
本発明の一側面の学習方法は、入力されたモデルデータの特徴点であるモデル特徴点を決定し、前記モデル特徴点の特徴量を抽出し、前記モデル特徴点の特徴量を表すモデル特徴量ベクトルと、前記モデル特徴量ベクトルと次元数が同じベクトルであるLSHのハッシュ関数ベクトルとの内積値が閾値以上であるか否かに応じて、前記モデル特徴量ベクトルを１と０の二値のうちの一方の値に量子化し、前記モデル特徴量ベクトルが、特徴量空間において前記ハッシュ関数ベクトルに設定されたマージンの範囲内にある場合、１と０の二値のうちの他方の値を、前記モデル特徴量ベクトルの量子化後の値として設定し、前記モデル特徴点を、それぞれの前記ハッシュ関数ベクトルを用いて得られた前記モデル特徴量ベクトルの量子化後の値の組み合わせにより識別されるクラスタに属する特徴点としてクラスタリングするステップを含む。
【００３１】
本発明の一側面のプログラムは、入力されたモデルデータの特徴点であるモデル特徴点を決定し、前記モデル特徴点の特徴量を抽出し、前記モデル特徴点の特徴量を表すモデル特徴量ベクトルと、前記モデル特徴量ベクトルと次元数が同じベクトルであるLSHのハッシュ関数ベクトルとの内積値が閾値以上であるか否かに応じて、前記モデル特徴量ベクトルを１と０の二値のうちの一方の値に量子化し、前記モデル特徴量ベクトルが、特徴量空間において前記ハッシュ関数ベクトルに設定されたマージンの範囲内にある場合、１と０の二値のうちの他方の値を、前記モデル特徴量ベクトルの量子化後の値として設定し、前記モデル特徴点を、それぞれの前記ハッシュ関数ベクトルを用いて得られた前記モデル特徴量ベクトルの量子化後の値の組み合わせにより識別されるクラスタに属する特徴点としてクラスタリングするステップを含む処理をコンピュータに実行させる。
【００３２】
本発明の他の側面の認識装置は、クエリとして入力されたデータの特徴点であるクエリ特徴点を決定し、前記クエリ特徴点の特徴量を抽出する抽出手段と、前記クエリ特徴点の特徴量を表すクエリ特徴量ベクトルと、ハッシュ関数ベクトルとの内積値が閾値以上であるか否かに応じて、前記クエリ特徴量ベクトルを１と０の二値のうちの一方の値に量子化する量子化手段と、前記クエリ特徴点を、それぞれの前記ハッシュ関数ベクトルを用いて得られた前記クエリ特徴量ベクトルの量子化後の値の組み合わせにより識別されるクラスタに属する特徴点としてクラスタリングするクラスタリング手段と、前記クエリ特徴点と、前記クエリ特徴点と同じクラスタに属するそれぞれの前記モデル特徴点との類似度を算出し、算出した類似度に基づいて、前記クエリ特徴点の最近傍となる前記モデル特徴点を決定する認識手段とを備える。
【００３３】
学習装置により生成されたモデル特徴量ベクトルの情報と、前記モデル特徴点が属するクラスタの情報とを対応付けて記憶する記憶手段をさらに設けることができる。
【００３４】
本発明の他の側面の認識方法は、クエリとして入力されたデータの特徴点であるクエリ特徴点を決定し、前記クエリ特徴点の特徴量を抽出し、前記クエリ特徴点の特徴量を表すクエリ特徴量ベクトルと、ハッシュ関数ベクトルとの内積値が閾値以上であるか否かに応じて、前記クエリ特徴量ベクトルを１と０の二値のうちの一方の値に量子化し、前記クエリ特徴点を、それぞれの前記ハッシュ関数ベクトルを用いて得られた前記クエリ特徴量ベクトルの量子化後の値の組み合わせにより識別されるクラスタに属する特徴点としてクラスタリングし、前記クエリ特徴点と、前記クエリ特徴点と同じクラスタに属するそれぞれの前記モデル特徴点との類似度を算出し、算出した類似度に基づいて、前記クエリ特徴点の最近傍となる前記モデル特徴点を決定するステップを含む。
【００３５】
本発明の他の側面のプログラムは、クエリとして入力されたデータの特徴点であるクエリ特徴点を決定し、前記クエリ特徴点の特徴量を抽出し、前記クエリ特徴点の特徴量を表すクエリ特徴量ベクトルと、ハッシュ関数ベクトルとの内積値が閾値以上であるか否かに応じて、前記クエリ特徴量ベクトルを１と０の二値のうちの一方の値に量子化し、前記クエリ特徴点を、それぞれの前記ハッシュ関数ベクトルを用いて得られた前記クエリ特徴量ベクトルの量子化後の値の組み合わせにより識別されるクラスタに属する特徴点としてクラスタリングし、前記クエリ特徴点と、前記クエリ特徴点と同じクラスタに属するそれぞれの前記モデル特徴点との類似度を算出し、算出した類似度に基づいて、前記クエリ特徴点の最近傍となる前記モデル特徴点を決定するステップを含む処理をコンピュータに実行させる。
【００３６】
本発明の一側面においては、入力されたモデルデータの特徴点であるモデル特徴点が決定され、前記モデル特徴点の特徴量が抽出され、前記モデル特徴点の特徴量を表すモデル特徴量ベクトルと、前記モデル特徴量ベクトルと次元数が同じベクトルであるLSHのハッシュ関数ベクトルとの内積値が閾値以上であるか否かに応じて、前記モデル特徴量ベクトルが１と０の二値のうちの一方の値に量子化される。また、前記モデル特徴量ベクトルが、特徴量空間において前記ハッシュ関数ベクトルに設定されたマージンの範囲内にある場合、１と０の二値のうちの他方の値が、前記モデル特徴量ベクトルの量子化後の値として設定され、前記モデル特徴点が、それぞれの前記ハッシュ関数ベクトルを用いて得られた前記モデル特徴量ベクトルの量子化後の値の組み合わせにより識別されるクラスタに属する特徴点としてクラスタリングされる。
【００３７】
本発明の他の側面においては、クエリとして入力されたデータの特徴点であるクエリ特徴点が決定され、前記クエリ特徴点の特徴量が抽出され、前記クエリ特徴点の特徴量を表すクエリ特徴量ベクトルと、ハッシュ関数ベクトルとの内積値が閾値以上であるか否かに応じて、前記クエリ特徴量ベクトルが１と０の二値のうちの一方の値に量子化される。また、前記クエリ特徴点が、それぞれの前記ハッシュ関数ベクトルを用いて得られた前記クエリ特徴量ベクトルの量子化後の値の組み合わせにより識別されるクラスタに属する特徴点としてクラスタリングされ、前記クエリ特徴点と、前記クエリ特徴点と同じクラスタに属するそれぞれの前記モデル特徴点との類似度が算出され、算出された類似度に基づいて、前記クエリ特徴点の最近傍となる前記モデル特徴点が決定される。
【発明の効果】
【００３８】
本発明によれば、局所特徴量を用いた物体認識をLSHによって行う場合の認識精度を向上させることができる。
【図面の簡単な説明】
【００３９】
【図１】特徴量ベクトルの量子化の例を示す図である。
【図２】量子化誤差について説明する図である。
【図３】本発明の一実施形態に係る学習装置の構成例を示すブロック図である。
【図４】図３のインデックス作成部の構成例を示すブロック図である。
【図５】量子化誤差の補正の例を示す図である。
【図６】量子化値の例を示す図である。
【図７】本発明の一実施形態に係る認識装置の構成例を示すブロック図である。
【図８】図７の認識部の構成例を示すブロック図である。
【図９】学習装置の学習処理について説明するフローチャートである。
【図１０】図９のステップＳ４において行われるインデックス作成処理について説明するフローチャートである。
【図１１】認識装置の認識処理について説明するフローチャートである。
【図１２】図１１のステップＳ３４において行われる最近傍候補選択処理について説明するフローチャートである。
【図１３】物体認識装置の構成例を示すブロック図である。
【図１４】特徴点の決定の例を示す図である。
【図１５】特徴点間の位置関係を示す図である。
【図１６】特徴点のマッチングについて説明する図である。
【図１７】コンピュータの構成例を示すブロック図である。
【発明を実施するための形態】
【００４０】
［学習装置の構成例］
図３は、本発明の一実施形態に係る学習装置の構成例を示すブロック図である。
【００４１】
KNNマッチングなどの最近傍探索をLSHによって行う処理は、オフラインフェーズとしての学習処理と、オンラインフェーズとしての認識処理とからなる。図３の学習装置１は学習処理を行う装置である。
【００４２】
学習装置１はコンピュータにより構成される。図３に示す機能部のうちの少なくとも一部は、学習装置１を構成するコンピュータのCPUにより所定のプログラムが実行されることによって実現される。
【００４３】
図３に示すように、学習装置１は、画像処理部１１、特徴量抽出部１２、インデックス作成部１３、ハッシュ関数記憶部１４、およびモデル辞書記憶部１５から構成される。画像処理部１１に対しては、認識させようとする物体の画像であるモデル画像が入力される。
【００４４】
画像処理部１１は、モデル画像をグレースケールの画像に変換する処理、グレースケールのモデル画像に基づいてエッジ画像を生成する処理、多重解像度処理などの初期処理を行う。画像処理部１１は、初期処理によって得られたモデル画像のデータを特徴量抽出部１２に出力する。
【００４５】
特徴量抽出部１２は、モデル画像のエッジ上の各点を特徴点として決定する。例えば、特徴量抽出部１２は、多重解像度処理によって得られた解像度の異なる各画像に含まれる、特徴点に対応する位置の画素の情報を特徴量（局所特徴量）として抽出する。
【００４６】
特徴量抽出部１２は、抽出した特徴量を表す特徴量ベクトルの情報をモデル辞書記憶部１５に記憶させるとともに、インデックス作成部１３に出力する。
【００４７】
以下、適宜、モデル画像の特徴点をモデル特徴点といい、モデル特徴点の特徴量を表す特徴量ベクトルをモデル特徴量ベクトルという。
【００４８】
インデックス作成部１３は、ハッシュ関数記憶部１４に記憶されているLSHのハッシュ関数を読み出し、読み出したハッシュ関数を用いてモデル特徴量ベクトルを量子化する。
【００４９】
また、インデックス作成部１３は、モデル特徴点を、モデル特徴量ベクトルに複数のハッシュ関数を適用してそれぞれ求められた量子化値の組み合わせをキーとするクラスタに属する特徴点としてクラスタリングする。
【００５０】
インデックス作成部１３は、それぞれのモデル特徴点と、モデル特徴点が属するクラスタの識別情報であるキーを対応付けた情報であるインデックス情報を作成し、モデル辞書記憶部１５に記憶させる。インデックス作成部１３によるモデル特徴量ベクトルの量子化とクラスタリングについては後述する。
【００５１】
ハッシュ関数記憶部１４は、予め生成された、複数のLSHのハッシュ関数を記憶する。LSHのハッシュ関数の生成については例えば非特許文献１に記載されている。
【００５２】
ハッシュ関数記憶部１４に記憶されているそれぞれのハッシュ関数には、モデル特徴量ベクトルの量子化誤差を軽減するためのマージンである量子化誤差マージンが設定されている。ハッシュ関数記憶部１４は、量子化誤差マージンに関する情報をハッシュ関数に対応付けて記憶する。
【００５３】
モデル辞書記憶部１５は、特徴量抽出部１２により抽出されたモデル特徴量ベクトルの情報と、インデックス作成部１３により作成されたインデックス情報を含むモデル辞書を記憶する。モデル辞書記憶部１５に記憶されたモデル辞書は、物体認識を実際に行う認識装置に提供される。学習装置１から認識装置に対するモデル辞書の提供は、有線または無線による通信によって、または記録媒体を介して行われる。
【００５４】
図４は、図３のインデックス作成部１３の構成例を示すブロック図である。
【００５５】
図４に示すように、インデックス作成部１３は、量子化部２１とクラスタリング部２２から構成される。
【００５６】
量子化部２１は、ハッシュ関数記憶部１４に記憶されているハッシュ関数を、特徴量抽出部１２から供給されたモデル特徴量ベクトルに適用してハッシュ値を算出する。
【００５７】
ハッシュ関数記憶部１４に記憶されているハッシュ関数は、モデル特徴量ベクトルと次元数が同じベクトル（ハッシュ関数ベクトル）として表される。量子化部２１により算出されるハッシュ値は実数のベクトルとなり、ベクトルの各項はモデル特徴量ベクトルとハッシュ関数ベクトルの内積である。
【００５８】
量子化部２１は、ハッシュ値として算出した内積値と閾値を比較し、モデル特徴量ベクトルを１と０の二値のうちのいずれか一方の値に量子化する。例えば、量子化部２１は、モデル特徴量ベクトルとハッシュ関数ベクトルの内積値が閾値としての０以上の場合、モデル特徴量ベクトルを値１に量子化し、０未満の場合、モデル特徴量ベクトルを値０に量子化する。
【００５９】
また、量子化部２１は、特徴量空間上で、モデル特徴量ベクトルがハッシュ関数ベクトルに設定されている量子化誤差マージンの範囲内にある場合、そのモデル特徴量ベクトルを値１に量子化している場合には値０を、値０に量子化している場合には１を、それぞれ量子化値として設定する。
【００６０】
図５は、量子化誤差の補正の例を示す図である。
【００６１】
図５の特徴量ベクトルＡとＢはモデル特徴量ベクトルである。ハッシュ関数ベクトルｆは、複数用意されているもののうちの１つのハッシュ関数を表すベクトルである。ハッシュ関数ベクトルｆに対しては、ハッシュ関数ベクトルｆと直交する超平面が、特徴量空間を二分する閾値として設定されている。
【００６２】
また、閾値を表す超平面とハッシュ関数ベクトルｆとの交点を基準として、閾値を表す超平面の一方の面側の近傍と、他方の面側の近傍を内側に含むように境界Ａと境界Ｂが設定されている。境界Ａと境界Ｂの内側の範囲が、ハッシュ関数ベクトルｆの量子化誤差マージンとなる。
【００６３】
例えば、特徴量ベクトルＡとハッシュ関数ベクトルｆの内積値が０以上の値として求められた場合、上述したようにして特徴量ベクトルＡは値１に量子化される。また、特徴量ベクトルＡは、特徴量空間上で、ハッシュ関数ベクトルｆの量子化マージンの範囲に含まれるから、値０も特徴量ベクトルＡの量子化値として設定される。
【００６４】
ハッシュ関数ベクトルｆを用いた場合、特徴量ベクトルＡは、０と１の両方の値に量子化されることになる。
【００６５】
同様に、特徴量ベクトルＢとハッシュ関数ベクトルｆの内積値が０未満の値として求められた場合、特徴量ベクトルＢは値０に量子化される。また、特徴量ベクトルＢは、特徴量空間上で、ハッシュ関数ベクトルｆの量子化マージンの範囲に含まれるから、値１も特徴量ベクトルＢの量子化値として設定される。
【００６６】
ハッシュ関数ベクトルｆを用いた場合、特徴量ベクトルＢは、０と１の両方の値に量子化されることになる。
【００６７】
量子化部２１は、以上のようなモデル特徴量ベクトルの量子化を、ハッシュ関数記憶部１４に記憶されているそれぞれのハッシュ関数ベクトルを用いて行う。量子化部２１により得られた量子化値はクラスタリング部２２に供給される。
【００６８】
クラスタリング部２２は、量子化部２１により得られた量子化値に基づいて、それぞれのモデル特徴点をクラスタリングする。
【００６９】
図６は、モデル特徴量ベクトルの量子化値の例を示す図である。
【００７０】
図６は、ハッシュ関数ベクトルｆ１乃至ｆ３をそれぞれ用いて得られた、モデル特徴量ベクトルである特徴量ベクトルＡとＢの量子化値の例を示している。
【００７１】
図６に示すように、ハッシュ関数ベクトルｆ１を用いた場合、特徴量ベクトルＡは値０に量子化される。
【００７２】
また、ハッシュ関数ベクトルｆ２を用いた場合、特徴量ベクトルＡは値１に量子化される。ここで、特徴量ベクトルＡは、特徴量空間上で、ハッシュ関数ベクトルｆ２に設定された量子化マージンの範囲に含まれる特徴量ベクトルであるため、値０も、特徴量ベクトルＡの量子化値として設定される。
【００７３】
ハッシュ関数ベクトルｆ３を用いた場合、特徴量ベクトルＡは値１に量子化される。
【００７４】
同様に、ハッシュ関数ベクトルｆ１を用いた場合、特徴量ベクトルＢは値０に量子化される。
【００７５】
また、ハッシュ関数ベクトルｆ２を用いた場合、特徴量ベクトルＢは値０に量子化される。特徴量ベクトルＢは、特徴量空間上で、ハッシュ関数ベクトルｆ２に設定された量子化マージンの範囲に含まれる特徴量ベクトルであるため、値１も、特徴量ベクトルＢの量子化値として設定される。
【００７６】
ハッシュ関数ベクトルｆ３を用いた場合、特徴量ベクトルＢは値１に量子化される。
【００７７】
この場合、クラスタリング部２２は、特徴量ベクトルＡにより特徴量が表されるモデル特徴点を、それぞれのハッシュ関数ベクトルを用いて算出された量子化値の組み合わせである［０，１，１］をキーとするクラスタと、［０，０，１］をキーとするクラスタの２つのクラスタに属する特徴点としてクラスタリングする。
【００７８】
また、クラスタリング部２２は、特徴量ベクトルＢにより特徴量が表されるモデル特徴点を、それぞれのハッシュ関数ベクトルを用いて算出された量子化値の組み合わせである［０，０，１］をキーとするクラスタと、［０，１，１］をキーとするクラスタの２つのクラスタに属する特徴点としてクラスタリングする。
【００７９】
クラスタリング部２２は、特徴量ベクトルＡにより特徴量が表されるモデル特徴点のIDと、［０，１，１］および［０，０，１］を対応付けたインデックス情報を作成する。また、クラスタリング部２２は、特徴量ベクトルＢにより特徴量が表されるモデル特徴点のIDと、［０，０，１］および［０，１，１］を対応付けたインデックス情報を作成する。
【００８０】
このように、インデックス作成部１３においては、各モデル特徴量ベクトルを対象として、モデル特徴量ベクトルとハッシュ関数ベクトルの内積値が算出され、閾値と比較することによって１と０の二値のうちの一方の値にモデル特徴量ベクトルが量子化される。
【００８１】
また、ハッシュ関数ベクトルに設定された量子化誤差マージンの範囲にモデル特徴量ベクトルが含まれる場合、１と０の二値のうちの他方の値も量子化値として設定され、量子化値に基づいてモデル特徴点がクラスタリングされる。
【００８２】
これにより、ハッシュ関数ベクトルの閾値となる超平面の近傍にあるモデル特徴量ベクトルにより特徴量が表されるモデル特徴点を、値１をキーに含むクラスタと値０をキーに含むクラスタの両方のクラスタにクラスタリングすることができる。
【００８３】
すなわち、いずれかのハッシュ関数ベクトルの閾値となる超平面の近傍にあるモデル特徴量ベクトルを有するモデル特徴点については、冗長性を持った形でクラスタリングすることが可能になる。
【００８４】
以上のようにして学習装置１により生成されたモデル辞書は認識装置に提供され、局所特徴量を用いた物体認識が行われる。
【００８５】
［認識装置の構成例］
図７は、本発明の一実施形態に係る認識装置の構成例を示すブロック図である。
【００８６】
図７の認識装置２は、局所特徴量を用いた物体認識をLSHによって行う装置である。
【００８７】
認識装置２もコンピュータにより構成される。図７に示す機能部のうちの少なくとも一部は、認識装置２を構成するコンピュータのCPUにより所定のプログラムが実行されることによって実現される。学習装置１と認識装置２が同じコンピュータにより実現されるようにしてもよいし、それぞれ異なるコンピュータにより実現されるようにしてもよい。
【００８８】
図７に示すように、認識装置２は、画像処理部３１、特徴量抽出部３２、認識部３３、ハッシュ関数記憶部３４、およびモデル辞書記憶部３５から構成される。画像処理部３１に対してはクエリ画像が入力される。
【００８９】
画像処理部３１は、図３の画像処理部１１と同様の処理を行う。すなわち、画像処理部３１は、クエリ画像に基づいて初期処理を行う。画像処理部３１は、初期処理を行うことによって得られたクエリ画像のデータを特徴量抽出部３２に出力する。
【００９０】
特徴量抽出部３２は、図３の特徴量抽出部１２と同様に、クエリ画像の特徴点を決定し、それぞれの特徴点の特徴量を抽出する。
【００９１】
以下、適宜、クエリ画像の特徴点をクエリ特徴点といい、クエリ特徴点の特徴量を表す特徴量ベクトルをクエリ特徴量ベクトルという。
【００９２】
認識部３３は、ハッシュ関数記憶部３４に記憶されているLSHのハッシュ関数に基づいてクエリ特徴量ベクトルを量子化し、クエリ特徴点をクラスタリングする。また、認識部３３は、モデル辞書記憶部３５に記憶されているインデックス情報に基づいて、クエリ特徴点と同じクラスタに属するモデル特徴点を最近傍候補として選択し、クエリ特徴点と最近傍候補のモデル特徴点との特徴量ベクトルの類似度を算出する。
【００９３】
認識部３３は、特徴量ベクトルの類似度が高い順に所定の数のモデル特徴点を選択し、その中から、最近傍のモデル特徴点を選択する。
【００９４】
認識部３３は、クエリ特徴点とマッチした最近傍のモデル特徴点の数などに基づいて、クエリ画像に含まれる物体がどのモデル画像に含まれる物体であるのかを認識し、認識結果を出力する。
【００９５】
ハッシュ関数記憶部３４は、学習装置１のハッシュ関数記憶部１４に記憶されているものと同じ複数のLSHのハッシュ関数を記憶する。ハッシュ関数記憶部３４に記憶されているハッシュ関数には量子化誤差マージンは設定されていない。
【００９６】
モデル辞書記憶部３５は、学習装置１から提供されたモデル辞書を記憶する。
【００９７】
図８は、図７の認識部３３の構成例を示すブロック図である。
【００９８】
図８に示すように、認識部３３は、量子化部４１、クラスタリング部４２、類似度算出部４３、および出力部４４から構成される。
【００９９】
量子化部４１は、ハッシュ関数記憶部３４に記憶されているハッシュ関数をクエリ特徴量ベクトルに適用してハッシュ値を算出する。
【０１００】
量子化部４１は、ハッシュ値として算出した内積値と閾値を比較し、クエリ特徴量ベクトルを１と０の二値のうちのいずれか一方の値に量子化する。例えば、量子化部４１は、クエリ特徴量ベクトルとハッシュ関数ベクトルの内積値が閾値としての０以上の場合、クエリ特徴量ベクトルを値１に量子化し、０未満の場合、クエリ特徴量ベクトルを値０に量子化する。
【０１０１】
量子化部４１は、クエリ特徴量ベクトルの量子化を、ハッシュ関数記憶部３４に記憶されているそれぞれのハッシュ関数ベクトルを用いて行う。
【０１０２】
例えば、図６を参照して説明したように、ハッシュ関数ベクトルｆ１乃至ｆ３を用いることによって、クエリ特徴量ベクトルである特徴量ベクトルＡがそれぞれ値０，１，１に量子化される。量子化部４１がクエリ特徴量ベクトルの量子化に用いるハッシュ関数には量子化誤差マージンが設定されていないから、クエリ特徴量ベクトルの量子化値として求められる値は、１つのハッシュ関数ベクトルにつき０または１の１つの値である。
【０１０３】
また、ハッシュ関数ベクトルｆ１乃至ｆ３を用いることによって、クエリ特徴量ベクトルである特徴量ベクトルＢがそれぞれ値０，０，１に量子化される。
【０１０４】
量子化部４１は、量子化値をクラスタリング部４２に出力する。学習装置１により生成されたインデックス情報がすでに冗長性を持つため、また、実行速度を重視するため、量子化部４１による量子化においては、上述したような量子化誤差の補正は行われない。
【０１０５】
クラスタリング部４２は、図４のクラスタリング部２２と同様に、量子化部４１により得られた量子化値に基づいて、それぞれのクエリ特徴点をクラスタリングする。
【０１０６】
例えばクエリ特徴量ベクトルがそれぞれ値０，１，１に量子化された場合、クラスタリング部４２は、そのクエリ特徴量ベクトルにより特徴量が表されるクエリ特徴点を、［０，１，１］をキーとするクラスタに属する特徴点としてクラスタリングする。
【０１０７】
また、クエリ特徴量ベクトルがそれぞれ値０，０，１に量子化された場合、クラスタリング部４２は、そのクエリ特徴量ベクトルにより特徴量が表されるクエリ特徴点を、［０，０，１］をキーとするクラスタに属する特徴点としてクラスタリングする。
【０１０８】
クラスタリング部４２は、クエリ特徴点が属するクラスタのキーの情報を類似度算出部４３に出力する。
【０１０９】
類似度算出部４３は、モデル辞書記憶部３５に記憶されているモデル辞書に含まれるインデックス情報に基づいて、クエリ特徴点が属するクラスタと同じクラスタに属するモデル特徴点を最近傍候補の特徴点として特定する。
【０１１０】
類似度算出部４３は、最近傍候補のモデル特徴量ベクトルの情報をモデル辞書記憶部３５から読み出し、クエリ特徴点と、最近傍候補のモデル特徴点との特徴量ベクトルの類似度を算出する。クエリ特徴点の特徴量ベクトルの情報は、特徴量抽出部３２から供給されている。
【０１１１】
類似度算出部４３は、類似度が高い順に所定の数のモデル特徴点を選択し、一般化ハフ変換やoutlier除去処理などの処理を行うことによって、最近傍のモデル特徴点を選択する。類似度の最も高いモデル特徴点が、最近傍のモデル特徴点として選択されるようにしてもよい。類似度算出部４３は、最近傍のモデル特徴点の情報を出力部４４に出力する。
【０１１２】
出力部４４は、クエリ特徴点とマッチした最近傍のモデル特徴点の数などに基づいて、クエリ画像に含まれる物体がどのモデル画像に含まれる物体であるのかを認識し、認識結果を出力する。
【０１１３】
学習時にモデル特徴点が冗長性を持った形でクラスタリングされているため、クエリ特徴点が、最近傍のモデル特徴点と異なるクラスタに属する特徴点としてクラスタリングされてしまう可能性を低減することが可能になる。
【０１１４】
従って、クエリ特徴点との特徴量ベクトルの類似度を実際に算出する対象として、最近傍のモデル特徴点が含まれる可能性が高くなり、マッチングの精度を高めることが可能になる。また、最終的な認識結果の精度をも高めることが可能になる。
【０１１５】
［装置の動作］
ここで、図９のフローチャートを参照して、学習装置１の学習処理について説明する。
【０１１６】
図９の処理は、モデル画像が学習装置１に入力されたときに開始される。
【０１１７】
ステップＳ１において、画像処理部１１は初期処理を行う。
【０１１８】
ステップＳ２において、特徴量抽出部１２は、初期処理によって得られたエッジ画像の各点をモデル特徴点として決定する。
【０１１９】
ステップＳ３において、特徴量抽出部１２は、それぞれのモデル特徴点の特徴量を抽出し、抽出した特徴量を表すモデル特徴量ベクトルの情報をモデル辞書記憶部１５に記憶させる。
【０１２０】
ステップＳ４において、インデックス作成部１３によりインデックス作成処理が行われる。インデックス作成処理においては、モデル特徴量ベクトルが量子化され、量子化値に基づいてモデル特徴点がクラスタリングされる。インデックス作成処理が終了した後、処理は終了される。
【０１２１】
次に、図１０のフローチャートを参照して、図９のステップＳ４において行われるインデックス作成処理について説明する。
【０１２２】
図１０の処理は、１つのモデル特徴点の特徴量を表すモデル特徴量ベクトルの情報が特徴量抽出部１２から供給される毎に行われる。
【０１２３】
ステップＳ１１において、インデックス作成部１３の量子化部２１は、ハッシュ関数記憶部１４に記憶されているハッシュ関数を１つ選択する。
【０１２４】
ステップＳ１２において、量子化部２１は、モデル特徴量ベクトルと、選択したハッシュ関数ベクトルとの内積値を算出する。
【０１２５】
ステップＳ１３において、量子化部２１は、算出した内積値が閾値としての０以上である場合、モデル特徴量ベクトルを値１に量子化し、０未満の場合、モデル特徴量ベクトルを値０に量子化する。
【０１２６】
ステップＳ１４において、量子化部２１は、特徴量空間上で、モデル特徴量ベクトルがハッシュ関数ベクトルに設定されている量子化誤差マージンの範囲内にあるか否かを判定する。
【０１２７】
モデル特徴量ベクトルが量子化誤差マージンの範囲内にあるとステップＳ１４において判定した場合、ステップＳ１５において、量子化部２１は、モデル特徴量ベクトルの量子化誤差を補正する。
【０１２８】
すなわち、量子化部２１は、モデル特徴量ベクトルを１と０の二値のうちの一方の値である値１にステップＳ１３において量子化している場合には、他方の値である値０を設定する。また、量子化部２１は、モデル特徴量ベクトルを１と０の二値のうちの一方の値である値０にステップＳ１３において量子化している場合には、他方の値である値１を設定する。
【０１２９】
モデル特徴量ベクトルが量子化誤差マージンの範囲内にないとステップＳ１４において判定された場合、ステップＳ１５の処理はスキップされる。
【０１３０】
ステップＳ１６において、量子化部２１は、ハッシュ関数記憶部１４に記憶されている全てのハッシュ関数を選択したか否かを判定する。量子化部２１は、まだ選択していないハッシュ関数があるとステップＳ１６において判定した場合、ステップＳ１１に戻り、違うハッシュ関数を選択して以上の処理を繰り返す。
【０１３１】
一方、全てのハッシュ関数を選択したとステップＳ１６において判定された場合、ステップＳ１７において、クラスタリング部２２は、モデル特徴点を、量子化値の組み合わせをキーとするクラスタに属する特徴点としてクラスタリングする。また、クラスタリング部２２は、モデル特徴点のIDと、キーを対応付けたインデックス情報を作成し、記憶させる。
【０１３２】
以上の処理が、特徴量抽出部１２により抽出された全てのモデル特徴点を対象として行われる。その後、図９のステップＳ４に戻り、それ以降の処理が行われる。
【０１３３】
以上の処理により、いずれかのハッシュ関数ベクトルの閾値となる超平面の近傍にあるモデル特徴量ベクトルを有するモデル特徴点については、冗長性を持った形でクラスタリングすることが可能になる。
【０１３４】
次に、図１１のフローチャートを参照して、認識装置２の認識処理について説明する。
【０１３５】
図１１の処理は、クエリ画像が認識装置２に入力されたときに開始される。
【０１３６】
ステップＳ３１において、画像処理部３１は初期処理を行う。
【０１３７】
ステップＳ３２において、特徴量抽出部３２は、初期処理によって得られたエッジ画像の各点をクエリ特徴点として決定する。
【０１３８】
ステップＳ３３において、特徴量抽出部３２は、それぞれのクエリ特徴点の特徴量を抽出し、抽出した特徴量を表すクエリ特徴量ベクトルの情報を出力する。
【０１３９】
ステップＳ３４において、認識部３３により最近傍候補選択処理が行われる。最近傍候補選択処理においては、クエリ特徴量ベクトルが量子化され、クエリ特徴点がクラスタリングされる。また、クエリ特徴点と、同じクラスタに属するそれぞれのモデル特徴点との特徴量ベクトルの類似度が算出される。
【０１４０】
ステップＳ３５において、認識部３３は、一般化ハフ変換やoutlier除去処理などの処理を行うことによって、ステップＳ３４の処理によって選択された最近傍候補の中から、最近傍のモデル特徴点を決定する。
【０１４１】
ステップＳ３６において、認識部３３は、全てのクエリ特徴点を対象として以上の処理が行われた後、クエリ画像に含まれる物体がどのモデル画像に含まれる物体であるのかを認識する。その後、処理は終了される。
【０１４２】
次に、図１２のフローチャートを参照して、図１１のステップＳ３４において行われる最近傍候補選択処理について説明する。
【０１４３】
図１２の処理は、１つのクエリ特徴点の特徴量を表すクエリ特徴量ベクトルの情報が特徴量抽出部３２から供給される毎に行われる。
【０１４４】
ステップＳ５１において、認識部３３の量子化部４１は、ハッシュ関数記憶部３４に記憶されているハッシュ関数を１つ選択する。
【０１４５】
ステップＳ５２において、量子化部４１は、クエリ特徴量ベクトルと、選択したハッシュ関数ベクトルとの内積値を算出する。
【０１４６】
ステップＳ５３において、量子化部４１は、算出した内積値が閾値としての０以上である場合、クエリ特徴量ベクトルを値１に量子化し、０未満の場合、クエリ特徴量ベクトルを値０に量子化する。
【０１４７】
ステップＳ５４において、量子化部４１は、ハッシュ関数記憶部３４に記憶されている全てのハッシュ関数を選択したか否かを判定する。量子化部４１は、まだ選択していないハッシュ関数があるとステップＳ５４において判定した場合、ステップＳ５１に戻り、違うハッシュ関数を選択して以上の処理を繰り返す。
【０１４８】
一方、全てのハッシュ関数を選択したとステップＳ５４において判定された場合、ステップＳ５５において、クラスタリング部４２は、クエリ特徴点を、量子化値の組み合わせをキーとするクラスタに属する特徴点としてクラスタリングする。
【０１４９】
ステップＳ５６において、類似度算出部４３は、インデックス情報に基づいて、クエリ特徴点と同じクラスタに属するモデル特徴点を最近傍候補として選択する。また、類似度算出部４３は、クエリ特徴点と、最近傍候補のモデル特徴点との特徴量ベクトルの類似度を算出する。
【０１５０】
ステップＳ５７において、類似度算出部４３は、特徴量ベクトルの類似度が高い順に所定の数のモデル特徴点を選択する。
【０１５１】
以上の処理が、特徴量抽出部３２により抽出された全てのクエリ特徴点を対象として行われる。その後、図１１のステップＳ３４に戻り、それ以降の処理が行われる。
【０１５２】
以上の処理により、クエリ特徴点が、最近傍のモデル特徴点と異なるクラスタに属する特徴点としてクラスタリングされてしまう可能性を低減することができ、マッチングの精度と、最終的な認識結果の精度を高めることが可能になる。
【０１５３】
［変形例］
以上においては、特徴量ベクトルの量子化誤差の補正が学習時にのみ行われるものとしたが、認識時にも行われるようにしてもよい。また、学習時ではなく、認識時にのみ行われるようにしてもよい。
【０１５４】
また、以上においては、画像から抽出した局所特徴量のマッチングをLSHによって行う場合について説明したが、マッチングの対象になる情報は、画像から抽出された特徴量に限られない。例えば、音声データから抽出された特徴量のマッチングなどに適用することも可能である。
【０１５５】
［適用例］
局所特徴量を用いた物体認識を以上のようにしてLSHによって行うことは、例えば、特開２００８−７７６２５号公報や特開２００８−２４３１７５号公報に記載されている物体認識に適用可能である。
【０１５６】
図１３は、物体認識装置の構成例を示すブロック図である。
【０１５７】
図１３に示す物体認識装置１１１の構成は、特開２００８−２４３１７５号公報に記載されている物体認識装置の構成と基本的に同様である。
【０１５８】
図１３に示すように、物体認識装置１１１は、モデル特徴量登録部１３１とクエリ（ターゲット）画像認識部１３２から構成される。
【０１５９】
モデル特徴量登録部１３１は、カメラ部１５１、フレームメモリ１５２、エッジ強度画像生成部１５３、エッジ画像生成部１５４、モデル特徴量抽出部１５５、およびモデル辞書記憶部１５６から構成される。
【０１６０】
カメラ部１５１は、被写体の像を撮像し、撮像して得られた画像をモデル画像としてフレームメモリ１５２に供給する。
【０１６１】
フレームメモリ１５２は、カメラ部１５１から供給されたモデル画像を蓄積する。
【０１６２】
エッジ強度画像生成部１５３は、フレームメモリ１５２に蓄積されているモデル画像を基にエッジ強度画像を生成する。エッジ強度画像は、モデル画像の所定の領域における位置の変化に対する画素値の変化の大きさの度合いを示すエッジ強度からなる。エッジ強度画像において、画素値の変化が急峻かつ大きいほど、エッジ強度は強くなり、画素値の変化が緩やかかつ小さいほどエッジ強度は弱くなる。
【０１６３】
すなわち、エッジ強度画像生成部１５３は、モデル画像内の注目画素を含む近傍の領域における画素値の変化の大きさの度合いを示すエッジ強度からなるエッジ強度画像を生成する。エッジ強度画像生成部１５３は、生成したエッジ強度画像をモデル特徴量抽出部１５５に供給する。
【０１６４】
エッジ画像生成部１５４は、フレームメモリ１５２に蓄積されているモデル画像を基にエッジ画像を生成する。エッジ画像は、モデル画像の画素の画素値の大小の境界を示す画像である。
【０１６５】
例えば、エッジ画像生成部１５４は、モデル画像内の注目画素の画素値の大きさが予め定められた閾値以上であれば１とし、それ以外を０とした画像をエッジ画像として生成する。エッジ画像生成部１５４は、生成したエッジ画像をモデル特徴量抽出部１５５に供給する。
【０１６６】
モデル特徴量抽出部１５５は、エッジ画像生成部１５４から供給されたエッジ画像上にモデル特徴点を決定する。
【０１６７】
また、モデル特徴量抽出部１５５は、モデル特徴点のうちの基準の点となるベース点と、ベース点以外のモデル特徴点であってベース点に従属して決定される点であるサポート点との幾何学的位置関係を決定する。
【０１６８】
ここで、幾何学的位置関係は、注目される２点のうちの１点を基準とした場合、他の１点の位置を基準の点からの距離および角度で表す関係とされる。すなわち、モデル特徴量抽出部１５５は、ベース点に対するサポート点の相対位置を決定する。
【０１６９】
モデル特徴点は、エッジ画像上の局所領域に設定される参照円と、エッジ画像とが交差する点であるエッジ点とされる。ベース点は、その参照円上のエッジ点の１つであり、その他の点はサポート点とされる。
【０１７０】
具体的には、モデル特徴量抽出部１５５は、図１４に示すように、エッジ画像Ｅの局所領域としての参照円Ｒを決定し、参照円Ｒと交差するエッジ画像Ｅ上のエッジ点を、ベース点ｂ、サポート点ｓ１，ｓ２，ｓ３とする。
【０１７１】
図１５に示すように、サポート点ｓ１乃至ｓ３のベース点ｂからの相対的な位置（距離および角度）は、相対距離ｒ１，ｒ２，ｒ３、および、基準軸Ｉからの相対角度θ１，θ２，θ３で表される。
【０１７２】
モデル特徴量抽出部１５５においては、参照円Ｒの大きさと位置を変えて、ベース点とサポート点のセットが複数選択される。
【０１７３】
モデル特徴量抽出部１５５は、エッジ強度画像生成部１５３から供給されたエッジ強度画像を基に、モデル特徴点（ベース点とサポート点）のエッジ強度をモデル特徴量として抽出する。モデル特徴量は、所定の次元数の特徴量ベクトルであるモデル特徴量ベクトルとして表される。
【０１７４】
また、モデル特徴量抽出部１５５は、図３の特徴量抽出部１２と同様にして、予め与えられているLSHのハッシュ関数を用いてモデル特徴量ベクトルを量子化する。モデル特徴量抽出部１５５においても、上述したような、量子化誤差を補正する処理が行われる。
【０１７５】
モデル特徴量抽出部１５５は、モデル特徴点を、モデル特徴量ベクトルに複数のハッシュ関数を適用してそれぞれ求められた量子化値の組み合わせをキーとするクラスタに属する特徴点としてクラスタリングする。
【０１７６】
モデル特徴量抽出部１５５は、それぞれのモデル特徴点と、モデル特徴点が属するクラスタの識別情報であるキーを対応付けた情報であるインデックス情報を作成し、モデル辞書記憶部１５６に記憶させる。
【０１７７】
また、モデル特徴量抽出部１５５は、ベース点とサポート点との幾何学的位置関係とモデル特徴量ベクトルの情報を、モデル画像毎にモデル辞書記憶部１５６に記憶させる。
【０１７８】
モデル辞書記憶部１５６は、例えばハードディスクドライブなどの記憶装置から構成される。
【０１７９】
一方、図１３のクエリ画像認識部１３２は、カメラ部１６１、フレームメモリ１６２、エッジ強度画像生成部１６３、エッジ画像生成部１６４、クエリ特徴量抽出部１６５、マッチング部１６６、および物体同定部１６７から構成される。
【０１８０】
カメラ部１６１、フレームメモリ１６２、エッジ強度画像生成部１６３、エッジ画像生成部１６４は、それぞれ、モデル特徴量登録部１３１のカメラ部１５１、フレームメモリ１５２、エッジ強度画像生成部１５３、エッジ画像生成部１５４と同様である。
【０１８１】
すなわち、カメラ部１６１は、被写体の像を撮像し、撮像して得られた画像をクエリ画像としてフレームメモリ１６２に供給する。
【０１８２】
フレームメモリ１６２は、カメラ部１６１から供給されたクエリ画像を蓄積する。
【０１８３】
エッジ強度画像生成部１６３は、フレームメモリ１６２に蓄積されているクエリ画像を基にエッジ強度画像を生成する。
【０１８４】
エッジ画像生成部１６４は、フレームメモリ１６２に蓄積されているクエリ画像を基にエッジ画像を生成する。
【０１８５】
クエリ特徴量抽出部１６５は、クエリ画像のエッジ画像およびエッジ強度画像を基に、モデル画像のモデル特徴点に対応するクエリ画像のエッジ点におけるエッジ強度を、クエリ画像の特徴量であるクエリ特徴量として抽出する。クエリ特徴量は、所定の次元数の特徴量ベクトルであるクエリ特徴量ベクトルとして表される。
【０１８６】
クエリ特徴量抽出部１６５は、クエリ特徴量ベクトルの情報を、クラスタの識別情報であるキーの情報とともにマッチング部１６６に供給する。
【０１８７】
マッチング部１６６は、図７の認識部３３と同様にして、予め与えられているLSHのハッシュ関数を用いてクエリ特徴量ベクトルを量子化する。
【０１８８】
マッチング部１６６は、クエリ特徴点（ベース点およびサポート点）を、クエリ特徴量ベクトルに複数のハッシュ関数を適用してそれぞれ求められた量子化値の組み合わせをキーとするクラスタに属する特徴点としてクラスタリングする。
【０１８９】
マッチング部１６６は、モデル辞書記憶部１５６に記憶されているインデックス情報に基づいて、クエリ特徴点と同じクラスタに属するモデル特徴点を最近傍候補として選択する。例えば、クエリ画像のベース点およびサポート点のセットを構成するそれぞれのクエリ特徴点について、同じクラスタに属するモデル特徴点が検出される。
【０１９０】
マッチング部１６６は、検出したモデル特徴点のモデル特徴量ベクトルの情報をモデル辞書記憶部１５６から読み出し、クエリ特徴点と、最近傍候補のモデル特徴点との特徴量ベクトルの類似度を算出する。マッチング部１６６は、算出した類似度に基づいて、クエリ特徴点の最近傍となるモデル特徴点を決定する。
【０１９１】
物体同定部１６７は、最近傍のモデル特徴点の数を基に、クエリ画像に含まれている物体を同定する。
【０１９２】
マッチング部１６６によるマッチングについて説明する。
【０１９３】
例えば、モデル画像が持つＰ個の特徴点であるエッジ点と、クエリ画像におけるＰ個の特徴点に対応する点とについて、特徴量同士のコストが算出され、コストの値が十分高い点がマッチングペアとして取得される。
【０１９４】
図１６Ａは、モデル画像（モデル画像のエッジ画像Ｅ）のベース点ｂ１と、クエリ画像（クエリ画像のエッジ画像Ｅ’）の点ｐ'とのマッチングを説明する図である。
【０１９５】
まず、クエリ画像の点ｐ'の基準軸にあわせ、モデル画像のサポート点ｓの位置補正が行われる。具体的には、モデル画像のベース点ｂ1が持つ基準軸方向ｎθ、クエリ画像の点ｐ'が持つ基準軸方向ｎ'θを用いて、図１６Ｂに示すようにして位置補正が行われる。つまり、モデル画像のベース点ｂ１が持つ基準軸方向ｎθを、クエリ画像の点ｐ’が持つ基準軸方向ｎ’θとの差ｄθ分だけ矢印方向に傾ける。
【０１９６】
続いて、ベースｂ1を点ｐ'の位置にあわせ、ｂ1-ｐ'間の特徴量コストｄ(ｂ1，ｐ')を算出し、各サポート点については、図１６Ｃに示す探索領域内で特徴量コストｄ(ｓ1j，ｐ'k)が最小となる点を探索する。
【０１９７】
モデル特徴点をｍ、クエリ特徴点をｔとすると、局所特徴量間の距離を表すｄ(m，t)は下式（１）で表される。
【数１】
2011221689.tif 000003
【０１９８】
式（１）のhm(k)はモデル特徴点の特徴量を表し、ht(k)はクエリ特徴点の特徴量を表す。
【０１９９】
また、ベース点、及びサポート点をあわせたTotalのマッチングコストは下式（２）で表される。
【数２】
2011221689.tif 000004
【０２００】
式（２）のα1j、β1jは、それぞれ、角度、距離のペナルティコストであり、下式（３）で表される。
【数３】
2011221689.tif 000005
【０２０１】
また、θｐ'k、ｒｐ'kは各サポート点に最もマッチする点ｐ’kのベース点ｂiからの角度、及び距離である。
【０２０２】
以上の計算を全てのクエリ特徴点について行い、最大コストを持つ点をモデルのベース点ｂ１の対応点ｂ’１とする。
【０２０３】
このように、図３の学習装置１において行われる学習処理、図７の認識装置２において行われる認識処理は、特開２００８−７７６２５号公報や特開２００８−２４３１７５号公報に記載されている物体認識に適用可能である。
【０２０４】
［コンピュータの構成例］
上述した一連の処理は、ハードウェアにより実行することもできるし、ソフトウェアにより実行することもできる。一連の処理をソフトウェアにより実行する場合には、そのソフトウェアを構成するプログラムが、専用のハードウェアに組み込まれているコンピュータ、または汎用のパーソナルコンピュータなどに、プログラム記録媒体からインストールされる。
【０２０５】
図１７は、上述した一連の処理をプログラムにより実行するコンピュータのハードウェアの構成例を示すブロック図である。
【０２０６】
CPU(Central Processing Unit)２０１、ROM(Read Only Memory)２０２、RAM(Random Access Memory)２０３は、バス２０４により相互に接続されている。
【０２０７】
バス２０４には、さらに、入出力インタフェース２０５が接続されている。入出力インタフェース２０５には、キーボード、マウスなどよりなる入力部２０６、ディスプレイ、スピーカなどよりなる出力部２０７が接続される。また、入出力インタフェース２０５には、ハードディスクや不揮発性のメモリなどよりなる記憶部２０８、ネットワークインタフェースなどよりなる通信部２０９、リムーバブルメディア２１１を駆動するドライブ２１０が接続される。
【０２０８】
以上のように構成されるコンピュータでは、CPU２０１が、例えば、記憶部２０８に記憶されているプログラムを入出力インタフェース２０５及びバス２０４を介してRAM２０３にロードして実行することにより、上述した一連の処理が行われる。
【０２０９】
CPU２０１が実行するプログラムは、例えばリムーバブルメディア２１１に記録して、あるいは、ローカルエリアネットワーク、インターネット、デジタル放送といった、有線または無線の伝送媒体を介して提供され、記憶部２０８にインストールされる。
【０２１０】
なお、コンピュータが実行するプログラムは、本明細書で説明する順序に沿って時系列に処理が行われるプログラムであっても良いし、並列に、あるいは呼び出しが行われたとき等の必要なタイミングで処理が行われるプログラムであっても良い。
【０２１１】
本発明の実施の形態は、上述した実施の形態に限定されるものではなく、本発明の要旨を逸脱しない範囲において種々の変更が可能である。
【符号の説明】
【０２１２】
１  学習装置，  ２  認識装置，  １１  画像処理部，  １２  特徴量抽出部，  １３  インデックス作成部，  １４  ハッシュ関数記憶部，  １５  モデル辞書記憶部，  ２１  量子化部，  ２２  クラスタリング部，  ３１  画像処理部，  ３２  特徴量抽出部，  ３３  認識部，  ３４  ハッシュ関数記憶部，  ３５  モデル辞書記憶部，  ４１  量子化部，  ４２  クラスタリング部，  ４３  類似度算出部，  ４４  出力部
【図１】
2011221689.tif 000006
【図２】
2011221689.tif 000007
【図３】
2011221689.tif 000008
【図４】
2011221689.tif 000009
【図５】
2011221689.tif 000010
【図６】
2011221689.tif 000011
【図７】
2011221689.tif 000012
【図８】
2011221689.tif 000013
【図９】
2011221689.tif 000014
【図１０】
2011221689.tif 000015
【図１１】
2011221689.tif 000016
【図１２】
2011221689.tif 000017
【図１３】
2011221689.tif 000018
【図１４】
2011221689.tif 000019
【図１５】
2011221689.tif 000020
【図１６】
2011221689.tif 000021
【図１７】
2011221689.tif 000022