(57)【特許請求の範囲】
【請求項１】
複数の物体の画像を取得するステップと、
前記物体の画像の特徴量を抽出した特徴量テンプレートを生成し、該特徴量テンプレートをバイナリ化するステップと、
木構造データベースにハッシュテーブルを配置した探索空間を生成し、前記バイナリ化した特徴量テンプレートに基づいて、下記評価関数の評価値が最小となるように、該特徴量テンプレートにおけるビット位置を算出し、該算出したビット位置における前記特徴量テンプレートの値に基づいて前記ハッシュテーブルのハッシュ値を算出し、前記特徴量テンプレートのハッシュ値に基づいて、前記特徴量テンプレートを前記木構造データベースのハッシュテーブルに分配するステップと、
認識対象物の画像を取得するステップと、
前記認識対象物の画像の特徴量を抽出した特徴量テンプレートを生成し、該特徴量テンプレートをバイナリ化するステップと、
前記バイナリ化した特徴量テンプレートの前記ビット位置の値に基づいて、前記認識対象物の特徴量テンプレートのハッシュ値を算出するステップと、
前記算出したハッシュ値に対応する前記木構造データベースのハッシュテーブルを選択し、該選択したハッシュテーブルに属する特徴量テンプレートと、前記認識対象物の特徴量テンプレートとのマッチングを行うステップと、
を含むことを特徴とする物体認識方法。
【数７】
0006493102.tif 000008
但し、Ｎｉは前記探索空間のｉ番目（ｉ＝１〜ｎ：ｎは予め設定された木構造の階層数）のノードにおける前記特徴量テンプレートの数であり、｜ＳＢＬ(Ｎｉ)｜は、ｉ番目のノードから分岐し、左側に分配される前記特徴量テンプレートの数であり、｜ＳＢＲ(Ｎｉ)｜は、ｉ番目のノードから分岐し、右側に分配される前記特徴量テンプレートの数である。
【請求項２】
請求項１に記載の物体認識方法であって、
下記評価関数の評価値が最小となるように、前記特徴量テンプレートにおけるビット位置を算出する、ことを特徴とする物体認識方法。
【数８】
0006493102.tif 000009
但し、ｘ、ｙは同一物体の特徴量を示し、ｑｘ、ｑｙは、その姿勢を示すクォータニオンであり、τは、予め設定される閾値であり、上記関数Ｐ（Ｎ）は、同一の物体で姿勢が近い場合に、ペナルティとして１を出力する関数である。
【請求項３】
複数の物体の画像を取得する画像取得手段と、
前記画像取得手段により取得された物体の画像の特徴量を抽出した特徴量テンプレートを生成し、該特徴量テンプレートをバイナリ化する特徴量抽出手段と、
木構造データベースにハッシュテーブルを配置した探索空間を生成し、前記特徴量抽出手段により前記バイナリ化された特徴量テンプレートに基づいて、下記評価関数の評価値が最小となるように、該特徴量テンプレートにおけるビット位置を算出し、該算出したビット位置における前記特徴量テンプレートの値に基づいて前記ハッシュテーブルのハッシュ値を算出し、前記特徴量テンプレートのハッシュ値に基づいて、前記特徴量テンプレートを前記木構造データベースのハッシュテーブルに分配するテーブル分配手段と、
前記画像取得手段により認識対象物の画像を取得しており、前記特徴量抽出手段により該取得された認識画像の特徴量を抽出した特徴量テンプレートを生成し該特徴量テンプレートをバイナリ化しており、該バイナリ化した特徴量テンプレートの前記ビット位置の値に基づいて、前記認識対象物の特徴量テンプレートのハッシュ値を算出し、該算出したハッシュ値に対応する前記木構造データベースのハッシュテーブルを選択し、該選択したハッシュテーブルに属する特徴量テンプレートと、前記認識対象物の特徴量テンプレートとのマッチングを行うマッチング手段と、
を備える、ことを特徴とする物体認識装置。
【数９】
0006493102.tif 000010
但し、Ｎｉは前記探索空間のｉ番目（ｉ＝１〜ｎ：ｎは予め設定された木構造の階層数）のノードにおける前記特徴量テンプレートの数であり、｜ＳＢＬ(Ｎｉ)｜は、ｉ番目のノードから分岐し、左側に分配される前記特徴量テンプレートの数であり、｜ＳＢＲ(Ｎｉ)｜は、ｉ番目のノードから分岐し、右側に分配される前記特徴量テンプレートの数である。
【請求項４】
複数の物体の画像を取得する処理と、
前記物体の画像の特徴量を抽出した特徴量テンプレートを生成し、該特徴量テンプレートをバイナリ化する処理と、
木構造データベースにハッシュテーブルを配置した探索空間を生成し、前記バイナリ化した特徴量テンプレートに基づいて、下記評価関数の評価値が最小となるように、該特徴量テンプレートにおけるビット位置を算出し、該算出したビット位置における前記特徴量テンプレートの値に基づいて前記ハッシュテーブルのハッシュ値を算出し、前記特徴量テンプレートのハッシュ値に基づいて、前記特徴量テンプレートを前記木構造データベースのハッシュテーブルに分配する処理と、
認識対象物の画像を取得する処理と、
前記認識対象物の画像の特徴量を抽出した特徴量テンプレートを生成し、該特徴量テンプレートをバイナリ化する処理と、
前記バイナリ化した特徴量テンプレートの前記ビット位置の値に基づいて、前記認識対象物の特徴量テンプレートのハッシュ値を算出する処理と、
前記算出したハッシュ値に対応する前記木構造データベースのハッシュテーブルを選択し、該選択したハッシュテーブルに属する特徴量テンプレートと、前記認識対象物の特徴量テンプレートとのマッチングを行う処理と、
をコンピュータに実行させる、ことを特徴とするプログラム。
【数１０】
0006493102.tif 000011
但し、Ｎｉは前記探索空間のｉ番目（ｉ＝１〜ｎ：ｎは予め設定された木構造の階層数）のノードにおける前記特徴量テンプレートの数であり、｜ＳＢＬ(Ｎｉ)｜は、ｉ番目のノードから分岐し、左側に分配される前記特徴量テンプレートの数であり、｜ＳＢＲ(Ｎｉ)｜は、ｉ番目のノードから分岐し、右側に分配される前記特徴量テンプレートの数である。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、物体を認識する物体認識方法、物体認識装置及びプログラムに関するものである。
【背景技術】
【０００２】
木構造のデータベースの探索空間を生成し、木構造の各ノードで条件判定を行うことで探索を行って木構造のデータベースの各テーブルに到達し、マッチングを行う物体認識方法が知られている（例えば、非特許文献１参照）。
【先行技術文献】
【非特許文献】
【０００３】
【非特許文献１】秋山瑞樹、柳井啓司著、Ｗｅｂ上の大量画像を用いた特定物体認識手法による一般物体認識、情報処理学会報告、ＩＰＳＪ  ＳＩＧ  Technical Report
【発明の概要】
【発明が解決しようとする課題】
【０００４】
上記方法においては、木構造の各ノードで条件判定を行う必要があるため、探索時間がかかり、認識速度が低下する虞がある。
本発明は、このような問題点に鑑みてなされたものであり、認識精度を良好に維持しつつ、高速な物体認識が可能となる物体認識方法、物体認識装置及びプログラムを提供することを主たる目的とする。
【課題を解決するための手段】
【０００５】
上記目的を達成するための本発明の一態様は、複数の物体の画像を取得するステップと、前記物体の画像の特徴量を抽出した特徴量テンプレートを生成し、該特徴量テンプレートをバイナリ化するステップと、木構造データベースにハッシュテーブルを配置した探索空間を生成し、前記バイナリ化した特徴量テンプレートに基づいて、下記評価関数の評価値が最小となるように、該特徴量テンプレートにおけるビット位置を算出し、該算出したビット位置における前記特徴量テンプレートの値に基づいて前記ハッシュテーブルのハッシュ値を算出し、前記特徴量テンプレートのハッシュ値に基づいて、前記特徴量テンプレートを前記木構造データベースのハッシュテーブルに分配するステップと、認識対象物の画像を取得するステップと、前記認識対象物の画像の特徴量を抽出した特徴量テンプレートを生成し、該特徴量テンプレートをバイナリ化するステップと、前記バイナリ化した特徴量テンプレートの前記ビット位置の値に基づいて、前記認識対象物の特徴量テンプレートのハッシュ値を算出するステップと、前記算出したハッシュ値に対応する前記木構造データベースのハッシュテーブルを選択し、該選択したハッシュテーブルに属する特徴量テンプレートと、前記認識対象物の特徴量テンプレートとのマッチングを行うステップと、を含むことを特徴とする物体認識方法である。
【数１】
0006493102.tif 000002
但し、Ｎｉは前記探索空間のｉ番目（ｉ＝１〜ｎ：ｎは予め設定された木構造の階層数）のノードにおける前記特徴量テンプレートの数であり、｜ＳＢＬ(Ｎｉ)｜は、ｉ番目のノードから分岐し、左側に分配される前記特徴量テンプレートの数であり、｜ＳＢＲ(Ｎｉ)｜は、ｉ番目のノードから分岐し、右側に分配される前記特徴量テンプレートの数である。
この一態様において、下記評価関数の評価値が最小となるように、前記特徴量テンプレートにおけるビット位置を算出してもよい。
【数２】
0006493102.tif 000003
但し、ｘ、ｙは同一物体の特徴量を示し、ｑｘ、ｑｙは、その姿勢を示すクォータニオンであり、τは、予め設定される閾値であり、上記関数Ｐ（Ｎ）は、同一の物体で姿勢が近い場合に、ペナルティとして１を出力する関数である。
上記目的を達成するための本発明の一態様は、複数の物体の画像を取得する画像取得手段と、前記画像取得手段により取得された物体の画像の特徴量を抽出した特徴量テンプレートを生成し、該特徴量テンプレートをバイナリ化する特徴量抽出手段と、木構造データベースにハッシュテーブルを配置した探索空間を生成し、前記特徴量抽出手段により前記バイナリ化された特徴量テンプレートに基づいて、下記評価関数の評価値が最小となるように、該特徴量テンプレートにおけるビット位置を算出し、該算出したビット位置における前記特徴量テンプレートの値に基づいて前記ハッシュテーブルのハッシュ値を算出し、前記特徴量テンプレートのハッシュ値に基づいて、前記特徴量テンプレートを前記木構造データベースのハッシュテーブルに分配するテーブル分配手段と、前記画像取得手段により認識対象物の画像を取得しており、前記特徴量抽出手段により該取得された認識画像の特徴量を抽出した特徴量テンプレートを生成し該特徴量テンプレートをバイナリ化しており、該バイナリ化した特徴量テンプレートの前記ビット位置の値に基づいて、前記認識対象物の特徴量テンプレートのハッシュ値を算出し、該算出したハッシュ値に対応する前記木構造データベースのハッシュテーブルを選択し、該選択したハッシュテーブルに属する特徴量テンプレートと、前記認識対象物の特徴量テンプレートとのマッチングを行うマッチング手段と、を備える、ことを特徴とする物体認識装置であってもよい。
【数３】
0006493102.tif 000004
但し、Ｎｉは前記探索空間のｉ番目（ｉ＝１〜ｎ：ｎは予め設定された木構造の階層数）のノードにおける前記特徴量テンプレートの数であり、｜ＳＢＬ(Ｎｉ)｜は、ｉ番目のノードから分岐し、左側に分配される前記特徴量テンプレートの数であり、｜ＳＢＲ(Ｎｉ)｜は、ｉ番目のノードから分岐し、右側に分配される前記特徴量テンプレートの数である。
上記目的を達成するための本発明の一態様は、複数の物体の画像を取得する処理と、前記物体の画像の特徴量を抽出した特徴量テンプレートを生成し、該特徴量テンプレートをバイナリ化する処理と、木構造データベースにハッシュテーブルを配置した探索空間を生成し、前記バイナリ化した特徴量テンプレートに基づいて、下記評価関数の評価値が最小となるように、該特徴量テンプレートにおけるビット位置を算出し、該算出したビット位置における前記特徴量テンプレートの値に基づいて前記ハッシュテーブルのハッシュ値を算出し、前記特徴量テンプレートのハッシュ値に基づいて、前記特徴量テンプレートを前記木構造データベースのハッシュテーブルに分配する処理と、認識対象物の画像を取得する処理と、前記認識対象物の画像の特徴量を抽出した特徴量テンプレートを生成し、該特徴量テンプレートをバイナリ化する処理と、前記バイナリ化した特徴量テンプレートの前記ビット位置の値に基づいて、前記認識対象物の特徴量テンプレートのハッシュ値を算出する処理と、前記算出したハッシュ値に対応する前記木構造データベースのハッシュテーブルを選択し、該選択したハッシュテーブルに属する特徴量テンプレートと、前記認識対象物の特徴量テンプレートとのマッチングを行う処理と、をコンピュータに実行させる、ことを特徴とするプログラムであってもよい。
【数４】
0006493102.tif 000005
但し、Ｎｉは前記探索空間のｉ番目（ｉ＝１〜ｎ：ｎは予め設定された木構造の階層数）のノードにおける前記特徴量テンプレートの数であり、｜ＳＢＬ(Ｎｉ)｜は、ｉ番目のノードから分岐し、左側に分配される前記特徴量テンプレートの数であり、｜ＳＢＲ(Ｎｉ)｜は、ｉ番目のノードから分岐し、右側に分配される前記特徴量テンプレートの数である。
【発明の効果】
【０００６】
本発明は、このような問題点に鑑みてなされたものであり、認識精度を良好に維持しつつ、高速な物体認識が可能となる物体認識方法、物体認識装置及びプログラムを提供することができる。
【図面の簡単な説明】
【０００７】
【図１】本発明の実施形態１に係る物体認識装置の概略的なシステム構成を示すブロック図である。
【図２】物体認識装置のオフライン工程を説明するための図である。
【図３】バイナリ化した特徴量テンプレートの一例を示す図である。
【図４】木構造のデータベースの一例を示す図である。
【図５】物体認識装置のオンライン工程を説明するための図である。
【図６】本発明の実施形態１に係る物体認識方法の処理フローを示すフローチャートである。
【図７】ＲＢＳ、ＰＢＳ、ＴＢＳ、及びＴＢＶによる認識精度及び認識物体の数との関係を示す図である。
【図８】ＲＢＳ、ＰＢＳ、ＴＢＳ、及びＴＢＶによる認識精度及び認識物体の数との関係を示す図である。
【図９】ＲＢＳ、ＰＢＳ、ＴＢＳ、及びＴＢＶによる認識時間及び認識物体の数との関係を示す図である。
【図１０】ＲＢＳ、ＰＢＳ、ＴＢＳ、及びＴＢＶによる認識時間及び認識物体の数との関係を示す図である。
【図１１】特徴量テンプレートのサイズに応じてハッシュ関数を変更する構成を説明するための図である。
【発明を実施するための形態】
【０００８】
実施形態１
以下、図面を参照して本発明の実施形態について説明する。
本発明の実施形態１に係る物体認識装置は、２次元又は３次元の物体（アイテム及び姿勢）をテンプレートマッチングを行って認識するものである。
【０００９】
ここで、単に、全モデルの画像と、認識する物体の画像と、のマッチングを行った場合、その探索時間が大きくなり、リアルタイム性に欠ける。そこで、本実施形態１に係る物体認識装置は、高速化と高精度化を両立した木構造の探索空間を設計し、この探索空間でモデルの画像（以下、モデル画像）の特徴量テンプレートと認識する物体の画像（以下、認識物体画像）の特徴量テンプレートとのマッチングを行う。これにより、高速な物体認識が可能となる。
【００１０】
物体認識装置は、例えば、演算処理等を行うＣＰＵ（Central Processing Unit）、ＣＰＵによって実行される演算プログラム等が記憶されたＲＯＭ（Read Only Memory）やＲＡＭ（Random Access Memory）からなるメモリ、外部と信号の入出力を行うインターフェイス部（Ｉ／Ｆ）などからなるマイクロコンピュータを中心にして、ハードウェア構成されている。ＣＰＵ、メモリ及びインターフェイス部は、データバスなどを介して相互に接続されている。
【００１１】
本実施形態１に係る物体認識装置は、例えば、オフライン工程において、モデル画像から特徴量テンプレートを生成し、生成した特徴量テンプレートを木構造のデータベースのハッシュテーブルに分配し、対応付ける。そして、物体認識装置は、オンライン工程において、認識物体画像から特徴量テンプレートを生成し、この特徴量テンプレートと、木構造のデータベースのハッシュテーブルの特徴量テンプレートと、のマッチングを行い、その物体を認識する。
【００１２】
まず、上述したオンライン工程の処理について、説明する。
図１は、本実施形態１に係る物体認識装置の概略的なシステム構成を示すブロック図である。本実施形態１に係る物体認識装置１は、画像取得部２と、特徴量抽出部３と、テンプレート分配部４と、マッチング部５と、を備えている。
【００１３】
画像取得部２は、画像取得手段の一具体例である。画像取得部２は、図２に示す如く、カメラを用いて、モデルとなる複数種類の物体（アイテム）のモデル画像を取得する（ａ）。画像取得部２は、カメラを用いて、各モデルを複数の異なる方向から撮影した異なる姿勢のモデル画像を取得する。
【００１４】
特徴量抽出部３は、特徴量抽出手段の一具体例である。特徴量抽出部３は、画像取得部２により取得されたモデル画像から特徴量を抽出し、特徴量テンプレートを生成する（ｂ）。さらに、特徴量抽出部３は、生成した特徴量テンプレートをバイナリ化する。
【００１５】
特徴量抽出部３は、画像取得部２により取得されたモデル画像から、例えば、図３に示す如く、ＬＩＮＥＭＯＤ特徴量を抽出した特徴量テンプレートを生成し、その特徴量テンプレートをバイナリ化する。
【００１６】
なお、特徴量抽出部３は、一例として、ＬＩＮＥＭＯＤ特徴量を抽出しているが、これに限定されない。特徴量抽出部３は、例えば、ＨＯＧ（Histograms of Oriented Gradients）特徴量、ＳＩＦＴ特徴量（Scale-Invariant Feature Transform）、ＳＵＲＦ特徴量（Speeded Up Robust Features）を抽出してもよく、任意の特徴量を抽出してもよい。
【００１７】
テンプレート分配部４は、テンプレート分配手段の一具体例である。テンプレート分配部４は、木構造データベースにハッシュテーブルを配置した探索空間を生成する。テンプレート分配部４は、例えば、図２に示すような３階層の木構造データベースを生成する（ｃ）。なお、木構造のデータベースの階層数は、予めユーザによって設定される。例えば、階層数を増加させると後述の如く、ハッシュテーブル内の特徴量テンプレート数が絞り込まれ、マッチング数が減少するため認識速度が向上する。
【００１８】
テンプレート分配部４は、バイナリ化した特徴量テンプレートに基づいて、評価関数の評価値が最小となるように、該特徴量テンプレートにおけるビット位置（例えば、（あ）、（い））を算出する（ｂ）。
【００１９】
なお、算出されるビット位置の数は、設定される階層数によって決まる。例えば、物体の認識速度、認識物体画像の精度（入力ノイズ）、求められる物体認識精度、などを比較考量して、後述のマッチグを行う特徴量テンプレートの数（各ハッシュテーブルに分配、対応付ける特徴量テンプレートの数）を実験的に設定する。認識速度を高速化したい場合は、マッチングを行う特徴量テンプレートの数を減少させる。また、認識物体画像の精度が低い（ノイズが大きい）、あるいは、物体認識精度を上げたい場合は、マッチングを行う特徴量テンプレートの数を増加させる。そして、ハッシュテーブルにその設定された数の特徴量テンプレートが分配されるように、木構造の階層数を決定する。木構造の階層数が決定されれば、その階層数に応じて、ビット位置の数を決定する。決定された階層数から１を減じたものが、算出するビット位置の数となる。図２の（ｃ）の場合、３階層であるため、ビット位置の数は２となる。
【００２０】
テンプレート分配部４は、例えば、特徴量テンプレートの数が各ハッシュテーブルで均一に最も近くなるように、特徴量テンプレートの分配を行うための下記評価関数を用いて、特徴量テンプレートにおけるビット位置を算出する。
【数５】
0006493102.tif 000006
なお、上記式において、Ｎｉは探索空間のｉ番目（ｉ＝１〜ｎ：ｎは予め設定された木構造の階層数）のノードにおける特徴量テンプレートの数であり、｜ＳＢＬ(Ｎｉ)｜は、ｉ番目のノードから分岐し、左側に分配される特徴量の数であり、｜ＳＢＲ(Ｎｉ)｜は、ｉ番目のノードから分岐し、右側に分配される特徴量の数である。
【００２１】
上記評価関数の評価値を最小にするということは、各ノードから、左側に分配される特徴量テンプレートの数と右側に分配される特徴量テンプレートの数との差が最小（例えば、略０）にすることである。すなわち、上記評価関数の評価値を最小にすることで、特徴量テンプレートの数が各ハッシュテーブルで均一に最も近くなるように、特徴量テンプレートを分配できる。図２の（ｃ）に示す場合、１０００個の特徴量テンプレートを、第１階層のノードで、左側及び右側に５００個ずつの特徴量テンプレートに分配される。さらに、第２階層のノードで、左側及び右側に２５０個ずつの特徴量テンプレートに分配される。各ハッシュテーブルには、最終的に、２５０個ずつの特徴量テンプレートが均一に分配されていることになる。
【００２２】
次に、評価関数の評価値が最小となるように、特徴量テンプレートにおけるビット位置を算出する方法について説明する。
テンプレート分配部４は、図３に示す如く、バイナリ化した特徴量テンプレート（複数のセルで構成）のセルの列位置（ｒ）、セルの行位置（ｃ）、及び各セル内の位置（ｂ）（以下、これらｒ、ｃ、及びｂで特定した位置をビット位置と称す）について、評価関数の評価値を算出し、その評価値が最小となるビット位置の組合せを算出する。なお、組合せるビット位置の数は、上述の如く、木構造のデータベースの階層数によって予め設定されている。
テンプレート分配部は、ｒ、ｃ、及びｂを変えることで、特徴量テンプレート上のビット位置を探索し、評価関数の評価値が最小となるビット位置の組合せを算出する。
【００２３】
例えば、図４に示す如く、木構造のデータベースの階層数が、例えば４階層である場合、組合せるビット位置の数は、３ビットであり、３つのビット位置が算出される。第１階層のノードで１０００個の特徴量テンプレートがある場合、テンプレート分配部４は、評価関数を用いて、第１階層のノードで５００個ずつの特徴量テンプレートに分かれるビット位置を探索する。より具体的には、テンプレート分配部４は、そのビット位置の値が０となる（左側に分岐する）特徴量テンプレートの数が５００、かつ、そのビット位置の値が１となる（右側に分岐する）特徴量テンプレートの数が５００となり、均等となるビット位置を探索する。
【００２４】
以下、同様にして、テンプレート分配部４は、評価関数を用いて、第２階層の各ノードで２５０個ずつの特徴量テンプレートに分かれるビット位置を探索する。さらに、テンプレート分配部４は、評価関数を用いて、第３階層の各ノードで１２５個ずつの特徴量テンプレートに分かれるビット位置を探索する。
【００２５】
上記のように、木構造の各ノードでは、ビット位置の値（０又は１）によって、右側又は左側に分岐される。しがたって、１０００個の特徴量テンプレートは、最終的に１２５個ずつの特徴量テンプレートに分けられ、各ハッシュテーブルに分配され、対応付けられる。
【００２６】
テンプレート分配部４は、算出したビット位置における特徴量テンプレートの値に基づいてハッシュテーブルのハッシュ値を算出する。ハッシュ値は、例えば、特徴量テンプレートの各ビット位置の値を組み合わせたもの（順に並べたもの）とする。図４の一例では、左から４番目のハッシュテーブルのハッシュ値は、０１１となる。なお、テンプレート分配部４は、特徴量テンプレートの各ビット位置の値に基づいて、所定のハッシュ関数を用いてハッシュ値を算出してもよい。
【００２７】
テンプレート分配部４は、モデル画像の特徴量テンプレートのハッシュ値に基づいて、各特徴量テンプレートを木構造データベースのハッシュテーブルに分配する。テンプレート分配部４は、各モデル画像の特徴量テンプレートにおけるビット位置の値から、その特徴量テンプレートのハッシュ値を夫々算出する。そして、テンプレート分配部４は、算出したハッシュ値と一致する木構造データベースのハッシュテーブルに、各モデル画像の特徴量テンプレートを分配し、対応付ける。
【００２８】
上述したように、本実施形態１に係る物体認識装置１において、上記評価関数の評価値が最小となるように、特徴量テンプレートにおけるビット位置を算出し、算出したビット位置における特徴量テンプレートの値に基づいてハッシュテーブルのハッシュ値を算出し、特徴量テンプレートのハッシュ値に基づいて、特徴量テンプレートを木構造データベースのハッシュテーブルに分配する。これにより、モデル画像の特徴量テンプレートの数が各ハッシュテーブルで均一に最も近くなるように、各特徴量テンプレートを分配できる。すなわち、各ハッシュテーブルにおいて一様にモデル画像の特徴量テンプレートの探索範囲を狭めることができる。したがって、どのような姿勢の認識物体の特徴量テンプレートに対しても、数を均一に絞り込んだハッシュテーブルのモデル画像の特徴量テンプレートと、マッチングを行うことができる。このため、認識精度を良好に維持しつつ、高速な物体認識が可能となる。
【００２９】
続いて、上述したオフライン工程の処理について説明する。
画像取得部２は、カメラを用いて、認識物体画像を取得する。画像取得部２は、例えば、図５の（ａ）に示す如く、取得した認識物体画像のうち、物体を含む所定領域の画像を切り取り、その所定領域の認識物体画像を特徴量抽出部３に出力する。
【００３０】
特徴量抽出部３は、画像取得部２にから出力された認識物体画像から特徴量を抽出し、特徴量テンプレートを生成する。さらに、特徴量抽出部３は、生成した特徴量テンプレートをバイナリ化する（ｂ）。
【００３１】
マッチング部５は、マッチング手段の一具体例である。マッチング部５は、例えば、上記算出された特徴量テンプレートのビット位置（（ｃ）のマーク部分）の値（１０、００、１１、１１）を並べて、そのハッシュ値（１０００１１１１）を算出する（ｄ）。マッチング部５は、算出したハッシュ値に対応する木構造データベースのハッシュテーブルを選択する（ｅ）。
【００３２】
このように、マッチング部５は、認識物体画像の特徴量テンプレートのビット位置からハッシュ値を算出し、このハッシュ値を用いて、即座に、木構造のデータベースのハッシュテーブルを選択できる。従がって、木構造の各ノードの条件判定を行う必要がなく、探索時間の大幅な削減に繋がり、高速な物体認識が可能となる。
【００３３】
また、ハッシュテーブルに予めその数が絞り込まれた特徴量テンプレートが対応付けられている。このため、マッチング部５は、この絞り込まれた特徴量テンプレートに対してのみ、マッチングを行えばよい。したがって、大幅なマッチング時間の短縮に繋がり、さらに高速な物体認識が可能となる。例えば、８階層の木構造のデータベース（７ビットハッシュ）の場合、特徴量テンプレートの数を、５０００個から３０個までに絞り込み、各ハッシュテーブルに対応付けることができる。この場合、３０個の特徴量テンプレートのみに対してマッチングを行えばよいため、大幅なマッチング時間の短縮に繋がる。
【００３４】
マッチング部５は、選択したハッシュテーブルに属するモデル画像の特徴量テンプレートと、認識物体画像の特徴量テンプレートとのマッチングを行う（ｆ）。マッチング部５は、例えば、各モデル画像の特徴量テンプレートと、認識物体画像の特徴量テンプレートとの相関値を夫々算出する。そして、マッチング部５は、算出した相関値が最も高いモデル画像の特徴量テンプレートを認識物体として認識し、その物体及び姿勢を出力する。
【００３５】
なお、マッチング部５は、算出した相関値が所定値以下となり相関が低い（マッチングするものがない）場合、本認識処理を終了してもよい。あるいは、マッチング部５は、算出した相関値が所定値以下となり相関が低い場合、他のハッシュテーブルに属するモデル画像の特徴量テンプレートと、認識物体画像の特徴量テンプレートとのマッチングを再度行ってもよい。
【００３６】
次に、本実施形態１に係る物体認識方法について説明する。図６は、本実施形態に係る物体認識方法の処理フローを示すフローチャートである。
オフライン工程において、画像取得部２は、カメラを用いて、物体のモデル画像を取得する（ステップＳ１０１）。
【００３７】
特徴量抽出部３は、画像取得部２により取得されたモデル画像から、特徴量を抽出し、特徴量テンプレートを生成する（ステップＳ１０２）。特徴量抽出部３は、生成した特徴量テンプレートをバイナリ化する（ステップＳ１０３）。
【００３８】
テンプレート分配部４は、予め設定された階層の木構造データベースにハッシュテーブルを配置した探索空間を生成する（ステップＳ１０４）。
テンプレート分配部４は、特徴量抽出部３によりバイナリ化された特徴量テンプレートに基づいて、上記評価関数の評価値が最小となるように、該特徴量テンプレートにおけるビット位置を算出する（ステップＳ１０５）。
【００３９】
テンプレート分配部４は、各特徴量テンプレートのハッシュ値を算出し、算出したハッシュ値と一致する木構造データベースのハッシュテーブルに、各特徴量テンプレートを分配し対応付ける（ステップＳ１０６）。
【００４０】
オンライン工程において、画像取得部２は、カメラを用いて、認識物体画像を取得する。
特徴量抽出部３は、画像取得部２により取得された認識物体画像から特徴量を抽出し（ステップＳ１０７）、特徴量テンプレートを生成する（ステップＳ１０８）。さらに、特徴量抽出部３は、生成した特徴量テンプレートをバイナリ化する（ステップＳ１０９）。マッチング部５は、上記算出された特徴量テンプレートのビット位置の値を並べて、ハッシュ値を算出する（ステップＳ１１０）。マッチング部５は、算出したハッシュ値に対応する木構造データベースのハッシュテーブルを選択する（ステップＳ１１１）。
【００４１】
マッチング部５は、選択したハッシュテーブルに属するモデル画像の特徴量テンプレートと、認識物体画像の特徴量テンプレートとのマッチングを行う（ステップＳ１１２）。
マッチング部５は、認識物体画像の特徴量テンプレートとの相関値が最も高いモデル画像の特徴量テンプレートを認識物体として認識し、その物体及び姿勢を出力する（ステップＳ１１３）。
【００４２】
以上、本実施形態１において、木構造データベースにハッシュテーブルを配置した探索空間を生成し、バイナリ化したモデル画像の特徴量テンプレートに基づいて、上記評価関数の評価値が最小となるように、該特徴量テンプレートにおけるビット位置の組合せを算出し、該算出したビット位置の組合せにおける特徴量テンプレートの値に基づいてハッシュテーブルのハッシュ値を算出し、特徴量テンプレートのハッシュ値に基づいて、特徴量テンプレートを木構造データベースのハッシュテーブルに分配する。これにより、特徴量テンプレートの数が各ハッシュテーブルで均一に最も近くなり、各ハッシュテーブルのハッシュ値は、算出したビット位置の組合せにおける特徴量テンプレートの値に基づいて算出されたものとなる。さらに、バイナリ化した認識物体画像の特徴量テンプレートのビット位置の値に基づいて、認識対象物の特徴量テンプレートのハッシュ値を算出し、算出したハッシュ値に対応する木構造データベースのハッシュテーブルを選択し、該選択したハッシュテーブルに属する特徴量テンプレートと、認識対象物の特徴量テンプレートとのマッチングを行う。これにより、認識物体画像の特徴量テンプレートのビット位置からハッシュ値を算出し、このハッシュ値を用いて、即座に、木構造のデータベースのハッシュテーブルを選択できる。従がって、木構造の各ノードの条件判定を行う必要がなく、探索時間の削減に繋がり、高速な物体認識が可能となる。また、ハッシュテーブルに予めその数が絞り込まれた特徴量テンプレートが対応付けられている。このため、マッチング部は、この絞り込まれた特徴量テンプレートに対してのみ、マッチングを行えばよい。したがって、マッチング時間の短縮に繋がり、高速な物体認識が可能となる。
さらに、モデル画像の特徴量テンプレートの数が各ハッシュテーブルで均一に最も近くなるように、各特徴量テンプレートを分配できる。すなわち、各ハッシュテーブルにおいて一様にモデル画像の特徴量テンプレートの探索範囲を狭めることができる。したがって、どのような姿勢の認識物体の特徴量テンプレートに対しても、数を均一に絞り込んだハッシュテーブルのモデル画像の特徴量テンプレートと、マッチングを行うことができる。このため、認識精度を良好に維持しつつ、高速な物体認識が可能となる。
【００４３】
実施形態２
本発明の実施形態２において、  テンプレート分配部４は、例えば、特徴量テンプレートの数が各ハッシュテーブルで均一に最も近くなるように特徴量テンプレートが分配され、かつ、同一モデルで類似姿勢の特徴量テンプレートが同一のハッシュテーブルに分配されないような下記評価関数を用いて、特徴量テンプレートにおけるビット位置を算出する。
【数６】
0006493102.tif 000007
但し、ｘ、ｙは同一物体の特徴量を示し、ｑｘ、ｑｙは、その姿勢を示すクォータニオンである。τは、予め実験的に求め設定される閾値であり、例えば、０．３が設定されている。上記関数Ｐ（Ｎ）は、同一モデルで姿勢が類似している場合に、ペナルティとして１を出力する関数である。
【００４４】
上記評価関数において、前方の項は、上記実施形態１の評価関数と同一であり、特徴量テンプレートの数が各ハッシュテーブルで均一に最も近くなるように特徴量テンプレートを分配するための項である。また、後方の項（関数Ｐ（Ｎ）を含む項）は、ペナルティ項であり、同一モデルで類似姿勢の特徴量テンプレートが同一のハッシュテーブルに分配されないようにする（モデル種類を散けるようにする）ための項である。この項によって、同一モデルで類似姿勢の特徴量テンプレートは別々のハッシュテーブルに分配される。
【００４５】
例えば、同一モデルが同一のハッシュテーブルにある場合、ハッシュ値の算出で参照しているビット位置だけ見ると、同一モデルで姿勢が類似しているものが同一のハッシュテーブルに分配され易い。一方で、一般に類似したもの同志から局所探索するよりも、出来るだけ異なったもの同志からグローバル探索した方が、より良好な探索結果が得られる。本実施形態においては、最初、ハッシュ値の算出で参照しているビット位置のみを見て、該当するハッシュテーブルを選択し、その後、選択したハッシュテーブルに属する全特徴量テンプレートと認識対象物の特徴量テンプレートとのマッチングを行う。このため、同一モデルで類似姿勢の特徴量テンプレートが別々のハッシュテーブルに分配され、モデル種類を散けた方が、より良好な探索結果が得られ、物体の認識精度も高くなる。
【００４６】
以上、本実施形態２によれば、上記評価関数を用いることにより、モデル画像の特徴量テンプレートの数が各ハッシュテーブルで均一に最も近くなるように、かつ、同一モデルで類似姿勢の特徴量テンプレートが同一のハッシュテーブルとならないように、特徴量テンプレートを分配できる。
モデル画像の特徴量テンプレートの数が各ハッシュテーブルで均一に最も近くなるように、特徴量テンプレートを分配することで、上記実施形態１と同様に、高速な物体認識が可能となる。さらに、同一モデルで類似姿勢の特徴量テンプレートが同一のハッシュテーブルとならないように、特徴量テンプレートを分配することで、上記実施形態１に比して、より高精度に物体を認識できる。すなわち、物体の認識精度をより良好に維持しつつ、高速な物体認識が可能となる。
【００４７】
次に上述した本実施形態１及び２に係る物体認識装置を用いて物体を認識したシミュレーション結果について説明する。
図７及び図８は、ＲＢＳ、ＰＢＳ、ＴＢＳ、及びＴＢＶによる認識精度及び認識物体の数との関係を示す図である。図９及び図１０は、ＲＢＳ、ＰＢＳ、ＴＢＳ、及びＴＢＶによる認識時間及び認識物体の数との関係を示す図である。
【００４８】
なお、図７及び図８では、認識物体の一例としてサルの置物（ape）を用い、図９及び図１０では認識物体の一例としてランプの置物（lamp）を用いている。また、ＲＢＳ（Randomness-based selection）では、特徴量テンプレートのビット位置をランダムに設定している。また、ＰＢＳ（Probability-based selection）では、認識物体のエントロピーに基づいて特徴量テンプレートのビット位置を設定している。ＴＢＳ（Tree-based selection）では、上記実施形態１に係る評価関数（１）式を用いて特徴量テンプレートのビット位置を設定している。ＴＢＶ（Tree-based selection with view scattering）では、上記実施形態２に係る評価関数（２）式を用いて特徴量テンプレートのビット位置を設定している。本シミュレーションでは、ＲＢＳ、ＰＢＳ、ＴＢＳ、及びＴＢＶにおいて、上記のように特徴量テンプレートのビット位置を設定し、マッチングを行っている。
【００４９】
図７及び図８に示す如く、本実施形態に係るＴＢＳ（評価関数（１）式）及びＴＢＶ（評価関数（２）式）のいずれも、他のＰＢＳ及びＲＢＳに比して、良好な認識精度が得られていることが分かる。また、本実施形態２に係るＴＢＶ（評価関数（２）式）は、本実施形態１に係るＴＢＳ（評価関数（１）式）よりも高い認識精度が得られていることが分かる。
【００５０】
さらに、図９及び図１０に示す如く、本実施形態に係るＴＢＳ（評価関数（１）式）及びＴＢＶ（評価関数（２）式）のいずれも、他のＰＢＳ及びＲＢＳに比して、大幅に認識時間が短縮され、高速な物体認識が可能であることが分かる。特に、認識物体の数（種類）が増加すると、他のＰＢＳ及びＲＢＳでは、その数に比例して認識時間が増加しているが、本実施形態に係るＴＢＳ（評価関数（１）式）及びＴＢＶ（評価関数（２）式）では、認識物体の数が増加しても認識時間がほとんど変化しない点で優れている。
【００５１】
すなわち、図７乃至図１０に示すシミュレーション結果から、ＴＢＳ（評価関数（１）式）及びＴＢＶ（評価関数（２）式）を用いた本実施形態１及び２に係る物体認識装置１は、物体の認識精度を良好に維持しつつ、高速な物体認識が可能とであるということが分かる。
【００５２】
なお、本発明は上記実施の形態に限られたものではなく、趣旨を逸脱しない範囲で適宜変更することが可能である。
例えば、上記実施形態において、特徴量抽出部３は、画像取得部２により取得されたモデル画像から特徴量を抽出し、多段階的なサイズに変化させた特徴量テンプレートを生成してもよい。これにより、例えば、物体あるいはモデルを遠方あるいは近接して見るなどの撮影レンジを変化させた場合でも、その撮影レンジに対応して特徴量テンプレートのサイズを変化させることで、その検出精度を向上させることができる。
【００５３】
この場合、テンプレート分配部４は、特徴量テンプレートの各ビット位置の値に基づいて、その特徴量テンプレートのサイズに対応したハッシュ関数を用いてハッシュ値を算出する。例えば、図１１に示す如く、テンプレート分配部４は、特徴量テンプレートの各ビット位置の値に基づいて、その特徴量テンプレートのサイズ３２＊３２、４８＊４８、６４＊６４に対応したハッシュ関数Ａ、Ｂ、Ｃを用いてハッシュ値を夫々算出する。
【００５４】
また、本発明は、例えば、図６に示す処理を、ＣＰＵ又はＧＰＵ（Graphics Processing Unit）にコンピュータプログラムを実行させることにより実現することも可能である。
プログラムは、様々なタイプの非一時的なコンピュータ可読媒体（non-transitory computer readable medium）を用いて格納され、コンピュータに供給することができる。非一時的なコンピュータ可読媒体は、様々なタイプの実体のある記録媒体（tangible storage medium）を含む。非一時的なコンピュータ可読媒体の例は、磁気記録媒体（例えばフレキシブルディスク、磁気テープ、ハードディスクドライブ）、光磁気記録媒体（例えば光磁気ディスク）、ＣＤ−ＲＯＭ（Read Only Memory）、ＣＤ−Ｒ、ＣＤ−Ｒ／Ｗ、半導体メモリ（例えば、マスクＲＯＭ、ＰＲＯＭ（Programmable ROM）、ＥＰＲＯＭ（Erasable PROM）、フラッシュＲＯＭ、ＲＡＭ（random access memory））を含む。
【００５５】
また、プログラムは、様々なタイプの一時的なコンピュータ可読媒体（transitory computer readable medium）によってコンピュータに供給されてもよい。一時的なコンピュータ可読媒体の例は、電気信号、光信号、及び電磁波を含む。一時的なコンピュータ可読媒体は、電線及び光ファイバ等の有線通信路、又は無線通信路を介して、プログラムをコンピュータに供給できる。
【符号の説明】
【００５６】
１  物体認識装置、２  画像取得部、３  特徴量抽出部、４  テンプレート分配部、５  マッチング部
【図１】
0006493102.tif 000012
【図２】
0006493102.tif 000013
【図３】
0006493102.tif 000014
【図４】
0006493102.tif 000015
【図５】
0006493102.tif 000016
【図６】
0006493102.tif 000017
【図７】
0006493102.tif 000018
【図８】
0006493102.tif 000019
【図９】
0006493102.tif 000020
【図１０】
0006493102.tif 000021
【図１１】
0006493102.tif 000022