(57)【特許請求の範囲】
【請求項１】
認識対象物体を表す３次元点群と、認識対象物体が存在する環境を表す３次元点群とを用いて、前記環境を表す３次元点群に含まれる認識対象物体を認識する物体認識装置であって、
前記認識対象物体の３次元点群内の各点に対して法線ベクトルを計算する法線ベクトル計算部と、
前記認識対象物体の３次元点群内の各点に対して点周辺の情報を表現する局所特徴量を計算する局所特徴量計算部と、
あらかじめ前記環境を表す３次元点群から作成された局所特徴量のクラスタ中心に対して、前記局所特徴量計算部によって認識対象物体を表す３次元点群から計算された局所特徴量を割り当てる局所特徴量割当部と、
前記局所特徴量割当部によって局所特徴量を割り当てた結果から各クラスタに割り当てられた局所特徴量の数を計算し、認識対象物体を表現するヒストグラムを計算するヒストグラム作成部と、
前記認識対象物体を表す３次元点群から当該３次元点群の大きさを表現するボックスを計算するボックスサイズ決定部と、
前記環境を表す３次元点群内に、前記ボックスサイズ決定部によって計算されたボックスを配置する各配置パターンに対して、前記配置パターンにおけるボックスを表現するヒストグラムを計算するボックスヒストグラム計算部と、
前記ボックスヒストグラム計算部によって各配置パターンに対して計算された前記ヒストグラムと、前記ヒストグラム作成部によって計算されたヒストグラムの比較を行い、各配置パターンに対してスコアを計算するヒストグラム比較部と、
前記ヒストグラム比較部によって計算されたボックスの各配置パターンに対するスコアから、ボックス内に前記認識対象物体が含まれるようなボックスの配置パターンを決定する物体認識処理部と、
前記物体認識処理部によって得られた配置パターンから認識対象物体が存在する三次元座標を復元する座標復元部と、
を含む物体認識装置。
【請求項２】
前記環境を表す点群が存在する３次元空間を予め定められた大きさのボクセルによって離散化し、あらかじめ前記環境を表す３次元点群内の各点に対して計算された局所特徴量と、前記局所特徴量に割り当てられたクラスタ中心とに基づいて、前記３次元空間内の離散化された前記ボクセルの各々に対して、前記ボクセルを含む所定の範囲に含まれる局所特徴量から計算されるヒストグラムを格納した３次元積分画像を計算する３次元積分画像作成部を更に含み、
前記ボックスヒストグラム計算部は、ボックスの各配置パターンに対して、前記３次元積分画像の各ボクセルに保存されたヒストグラムを用いて高々８回の和または差の計算によって、前記配置パターンのボックスを表現するヒストグラムを計算する請求項１に記載の物体認識装置。
【請求項３】
前記局所特徴量計算部は、前記法線ベクトル計算部によって各点に対して計算された法線ベクトルを利用してＳＨＯＴ（Signature of Histograms of Orientations）を計算する請求項１又は２に記載の物体認識装置。
【請求項４】
認識対象物体の３次元点群内の各点に対して法線ベクトルを計算する法線ベクトル計算部と、
前記認識対象物体の３次元点群内の各点に対して点周辺の情報を表現する局所特徴量を計算する局所特徴量計算部と、
あらかじめ認識対象物体が存在する環境を表す３次元点群から作成された局所特徴量のクラスタ中心に対して、前記局所特徴量計算部によって認識対象物体を表す３次元点群から計算された局所特徴量を割り当てる局所特徴量割当部と、
前記局所特徴量割当部によって局所特徴量を割り当てた結果から各クラスタに割り当てられた局所特徴量の数を計算し、認識対象物体を表現するヒストグラムを計算するヒストグラム作成部と、
前記認識対象物体を表す３次元点群から当該３次元点群の大きさを表現するボックスを計算するボックスサイズ決定部と、
前記環境を表す３次元点群内に、前記ボックスサイズ決定部によって計算されたボックスを配置する各配置パターンに対して、前記配置パターンにおけるボックスを表現するヒストグラムを計算するボックスヒストグラム計算部と、
を含む３次元点群モデル化装置。
【請求項５】
法線ベクトル計算部、局所特徴量計算部、局所特徴量割当部、ヒストグラム作成部、ボックスサイズ決定部、ボックスヒストグラム計算部、ヒストグラム比較部、物体認識処理部、及び座標復元部を含み、認識対象物体を表す点群と、認識対象物体が存在する環境を表す点群とを用いて、環境を表す点群に含まれる認識対象物体を認識する物体認識方法であって、
前記法線ベクトル計算部が、前記認識対象物体の３次元点群内の各点に対して法線ベクトルを計算するステップと、
前記局所特徴量計算部が、前記認識対象物体の３次元点群内の各点に対して点周辺の情報を表現する局所特徴量を計算するステップと、
前記局所特徴量割当部が、あらかじめ前記環境を表す３次元点群から作成された局所特徴量のクラスタ中心に対して、前記局所特徴量計算部によって認識対象物体を表す３次元点群から計算された局所特徴量を割り当てるステップと、
前記ヒストグラム作成部が、前記局所特徴量割当部によって局所特徴量を割り当てた結果から各クラスタに割り当てられた局所特徴量の数を計算し、認識対象物体を表現するヒストグラムを計算するステップと、
前記ボックスサイズ決定部が、前記認識対象物体を表す３次元点群から当該３次元点群の大きさを表現するボックスを計算するステップと、
前記ボックスヒストグラム計算部が、前記環境を表す３次元点群内に、前記ボックスサイズ決定部によって計算されたボックスを配置する各配置パターンに対して、前記配置パターンにおけるボックスを表現するヒストグラムを計算するステップと、
前記ヒストグラム比較部が、前記ボックスヒストグラム計算部によって各配置パターンに対して計算された前記ヒストグラムと、前記ヒストグラム作成部によって計算されたヒストグラムの比較を行い、各配置パターンに対してスコアを計算するステップと、
前記物体認識処理部が、前記ヒストグラム比較部によって計算されたボックスの各配置パターンに対するスコアから、ボックス内に前記認識対象物体が含まれるようなボックスの配置パターンを決定するステップと、
前記座標復元部が、前記物体認識処理部によって得られた配置パターンから認識対象物体が存在する三次元座標を復元するステップと、
を含む物体認識方法。
【請求項６】
３次元積分画像作成部が、前記環境を表す点群が存在する３次元空間を予め定められた大きさのボクセルによって離散化し、あらかじめ前記環境を表す３次元点群内の各点に対して計算された局所特徴量と、前記局所特徴量に割り当てられたクラスタ中心とに基づいて、前記３次元空間内の離散化された前記ボクセルの各々に対して、前記ボクセルを含む所定の範囲に含まれる局所特徴量から計算されるヒストグラムを格納した３次元積分画像を計算するステップを更に含み、
前記ボックスヒストグラム計算部が計算するステップは、ボックスの各配置パターンに対して、前記３次元積分画像の各ボクセルに保存されたヒストグラムを用いて高々８回の和または差の計算によって、前記配置パターンのボックスを表現するヒストグラムを計算する請求項５に記載の物体認識方法。
【請求項７】
コンピュータを、請求項１〜３のいずれか１項に記載の物体認識装置を構成する各部として機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、物体認識装置、３次元点群モデル化装置、方法、及びプログラムに係り、特に、環境を表す３次元点群に含まれる認識対象物を認識するための物体認識装置、３次元点群モデル化装置、方法、及びプログラムに関する。
【背景技術】
【０００２】
レーザーレンジファインダで計測した計測結果である３次元点群から物体を認識するとき、表面の反射率や面の向きによって３次元の計測結果に大きなノイズが生じることが多い。このように計測された３次元点群のデータで物体を認識する場合、ノイズに強いアルゴリズムが必要となる。
【０００３】
２次元の画像における物体検出のアルゴリズムのなかで、ノイズに強い特徴表現としては、Bag of Visual Words（以下、ＢｏＶＷと記載する）がある（非特許文献１参照）。
【０００４】
一般的には、認識対象の物体の多数の２次元画像からＢｏＶＷ形式のベクトルを抽出して記憶部に記憶しておき、入力画像から抽出されたＢｏＶＷ形式のベクトルを記憶部のベクトルと比較することで、物体を認識する。
【先行技術文献】
【非特許文献】
【０００５】
【非特許文献１】J. Sivic et al.: "Video Google: A Text Retrieval Approach to Object Matching in Videos", in Proc. ICCV, 2003.
【非特許文献２】F. Tombari, S. Salti, and L. Di Stefano,"SHOT: Unique signatures of histograms for surface and texture description",in 11th European Conference on Computer Vision (ECCV)
【発明の概要】
【発明が解決しようとする課題】
【０００６】
上記の２次元画像における物体認識の方法はロバストではあるが、そのままでは３次元点群による物体認識には用いることができない。
【０００７】
本発明は、上記問題点を解決するために成されたものであり、精度よく、３次元点群から物体を認識することができる物体認識装置、３次元点群モデル化装置、方法、及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【０００８】
上記目的を達成するために、第１の発明に係る物体認識装置は、認識対象物体を表す３次元点群と、認識対象物体が存在する環境を表す３次元点群とを用いて、前記環境を表す３次元点群に含まれる認識対象物体を認識する物体認識装置であって、前記認識対象物体の３次元点群内の各点に対して法線ベクトルを計算する法線ベクトル計算部と、前記認識対象物体の３次元点群内の各点に対して点周辺の情報を表現する局所特徴量を計算する局所特徴量計算部と、あらかじめ前記環境を表す３次元点群から作成された局所特徴量のクラスタ中心に対して、前記局所特徴量計算部によって認識対象物体を表す３次元点群から計算された局所特徴量を割り当てる局所特徴量割当部と、前記局所特徴量割当部によって局所特徴量を割り当てた結果から各クラスタに割り当てられた局所特徴量の数を計算し、認識対象物体を表現するヒストグラムを計算するヒストグラム作成部と、前記認識対象物体を表す３次元点群から当該３次元点群の大きさを表現するボックスを計算するボックスサイズ決定部と、前記環境を表す３次元点群内に、前記ボックスサイズ決定部によって計算されたボックスを配置する各配置パターンに対して、前記配置パターンにおけるボックスを表現するヒストグラムを計算するボックスヒストグラム計算部と、前記ボックスヒストグラム計算部によって各配置パターンに対して計算された前記ヒストグラムと、前記ヒストグラム作成部によって計算されたヒストグラムの比較を行い、各配置パターンに対してスコアを計算するヒストグラム比較部と、前記ヒストグラム比較部によって計算されたボックスの各配置パターンに対するスコアから、ボックス内に前記認識対象物体が含まれるようなボックスの配置パターンを決定する物体認識処理部と、前記物体認識処理部によって得られた配置パターンから認識対象物体が存在する三次元座標を復元する座標復元部と、を含んで構成されている。
【０００９】
また、第１の発明に係る物体認識装置において、前記環境を表す点群が存在する３次元空間を予め定められた大きさのボクセルによって離散化し、あらかじめ前記環境を表す３次元点群内の各点に対して計算された局所特徴量と、前記局所特徴量に割り当てられたクラスタ中心とに基づいて、前記３次元空間内の離散化された前記ボクセルの各々に対して、前記ボクセルを含む所定の範囲に含まれる局所特徴量から計算されるヒストグラムを格納した３次元積分画像を計算する３次元積分画像作成部を更に含み、前記ボックスヒストグラム計算部は、ボックスの各配置パターンに対して、前記３次元積分画像の各ボクセルに保存されたヒストグラムを用いて高々８回の和または差の計算によって、前記配置パターンのボックスを表現するヒストグラムを計算するようにしてもよい。
【００１０】
また、第１の発明に係る物体認識装置において、前記局所特徴量計算部は、前記法線ベクトル計算部によって各点に対して計算された法線ベクトルを利用してＳＨＯＴ（Signature of Histograms of Orientations）を計算するようにしてもよい。
【００１１】
第２の発明に係る３次元点群モデル化装置は、認識対象物体の３次元点群内の各点に対して法線ベクトルを計算する法線ベクトル計算部と、前記認識対象物体の３次元点群内の各点に対して点周辺の情報を表現する局所特徴量を計算する局所特徴量計算部と、あらかじめ認識対象物体が存在する環境を表す３次元点群から作成された局所特徴量のクラスタ中心に対して、前記局所特徴量計算部によって認識対象物体を表す３次元点群から計算された局所特徴量を割り当てる局所特徴量割当部と、前記局所特徴量割当部によって局所特徴量を割り当てた結果から各クラスタに割り当てられた局所特徴量の数を計算し、認識対象物体を表現するヒストグラムを計算するヒストグラム作成部と、前記認識対象物体を表す３次元点群から当該３次元点群の大きさを表現するボックスを計算するボックスサイズ決定部と、前記環境を表す３次元点群内に、前記ボックスサイズ決定部によって計算されたボックスを配置する各配置パターンに対して、前記配置パターンにおけるボックスを表現するヒストグラムを計算するボックスヒストグラム計算部と、を含んで構成されている。
【００１２】
第３の発明に係る物体認識方法は、法線ベクトル計算部、局所特徴量計算部、局所特徴量割当部、ヒストグラム作成部、ボックスサイズ決定部、ボックスヒストグラム計算部、ヒストグラム比較部、物体認識処理部、及び座標復元部を含み、認識対象物体を表す点群と、認識対象物体が存在する環境を表す点群とを用いて、環境を表す点群に含まれる認識対象物体を認識する物体認識方法であって、前記法線ベクトル計算部が、前記認識対象物体の３次元点群内の各点に対して法線ベクトルを計算するステップと、前記局所特徴量計算部が、前記認識対象物体の３次元点群内の各点に対して点周辺の情報を表現する局所特徴量を計算するステップと、前記局所特徴量割当部が、あらかじめ前記環境を表す３次元点群から作成された局所特徴量のクラスタ中心に対して、前記局所特徴量計算部によって認識対象物体を表す３次元点群から計算された局所特徴量を割り当てるステップと、前記ヒストグラム作成部が、前記局所特徴量割当部によって局所特徴量を割り当てた結果から各クラスタに割り当てられた局所特徴量の数を計算し、認識対象物体を表現するヒストグラムを計算するステップと、前記ボックスサイズ決定部が、前記認識対象物体を表す３次元点群から当該３次元点群の大きさを表現するボックスを計算するステップと、前記ボックスヒストグラム計算部が、前記環境を表す３次元点群内に、前記ボックスサイズ決定部によって計算されたボックスを配置する各配置パターンに対して、前記配置パターンにおけるボックスを表現するヒストグラムを計算するステップと、前記ヒストグラム比較部が、前記ボックスヒストグラム計算部によって各配置パターンに対して計算された前記ヒストグラムと、前記ヒストグラム作成部によって計算されたヒストグラムの比較を行い、各配置パターンに対してスコアを計算するステップと、前記物体認識処理部が、前記ヒストグラム比較部によって計算されたボックスの各配置パターンに対するスコアから、ボックス内に前記認識対象物体が含まれるようなボックスの配置パターンを決定するステップと、前記座標復元部が、前記物体認識処理部によって得られた配置パターンから認識対象物体が存在する三次元座標を復元するステップと、を含んで実行することを特徴とする。
【００１３】
また、第３の発明に係る物体認識方法において、３次元積分画像作成部が、前記環境を表す点群が存在する３次元空間を予め定められた大きさのボクセルによって離散化し、あらかじめ前記環境を表す３次元点群内の各点に対して計算された局所特徴量と、前記局所特徴量に割り当てられたクラスタ中心とに基づいて、前記３次元空間内の離散化された前記ボクセルの各々に対して、前記ボクセルを含む所定の範囲に含まれる局所特徴量から計算されるヒストグラムを格納した３次元積分画像を計算するステップを更に含み、前記ボックスヒストグラム計算部が計算するステップは、ボックスの各配置パターンに対して、前記３次元積分画像の各ボクセルに保存されたヒストグラムを用いて高々８回の和または差の計算によって、前記配置パターンのボックスを表現するヒストグラムを計算するようにしてもよい。
【００１４】
第４の発明に係るプログラムは、コンピュータを、上記第１の発明に係る物体認識装置を構成する各部として機能させるためのプログラムである。
【発明の効果】
【００１５】
本発明の物体認識装置、３次元点群モデル化装置、方法、及びプログラムによれば、精度よく、３次元点群から物体を認識することができる、という効果が得られる。
【図面の簡単な説明】
【００１６】
【図１】本発明の実施の形態に係る物体認識装置の構成を示すブロック図である。
【図２】基礎データ記憶部２１の一例を示す図である。
【図３】法線ベクトル記憶部３０の一例を示す図である。
【図４】局所特徴量記憶部３２の一例を示す図である。
【図５】クラスタ記憶部３４の一例を示す図である。
【図６】積分画像記憶部３６の一例を示す図である。
【図７】認識結果記憶部３８の一例を示す図である。
【図８】本発明の実施の形態に係る物体認識装置における前処理ルーチンを示すフローチャートである。
【図９】本発明の実施の形態に係る物体認識装置における物体認識処理ルーチンを示すフローチャートである。
【発明を実施するための形態】
【００１７】
以下、図面を参照して本発明の実施の形態を詳細に説明する。
【００１８】
＜本発明の実施の形態に係る概要＞
【００１９】
本実施の形態では、特徴量として、３次元点群でも利用可能な記述力の高い「ＳＨＯＴ（Signature of Histograms of Orientations）」を用いることで、多様な形状をカバーして物体を認識する。また、ＢｏＶＷを用いて物体を表現することで、計測誤差などのノイズの影響による形状の微小な変化に対して影響を受けやすいＳＨＯＴの不安定な面をカバーすることができる。
【００２０】
＜本発明の実施の形態に係る物体認識装置の構成＞
【００２１】
まず、本発明の実施の形態に係る物体認識装置の構成について説明する。図１に示すように、本発明の実施の形態に係る物体認識装置１００は、ＣＰＵと、ＲＡＭと、後述する物体認識処理ルーチンを実行するためのプログラムや各種データを記憶したＲＯＭと、を含むコンピュータで構成することが出来る。この物体認識装置１００は、機能的には図１に示すように入力部１０と、演算部２０と、出力部６０とを備えている。
【００２２】
入力部１０は、物体が存在する環境における複数の３次元点からなる３次元点群を受け付ける。３次元点群は、物体の表面上の位置を計測した計測結果である複数の位置を表す３次元点群であり、レーザーレンジファインダや、赤外線センサ、または超音波センサなどの、３次元点群を計測する装置によって得られたものである。
【００２３】
また、入力部１０は、認識対象物体を表す３次元点群を受け付ける。受け付けた３次元点群は基礎データ記憶部２１に格納するものとする。
【００２４】
演算部２０は、前処理部２２と、基礎データ記憶部２１と、法線ベクトル記憶部３０と、局所特徴量記憶部３２と、クラスタ記憶部３４と、積分画像記憶部３６と、認識結果記憶部３８と、法線ベクトル計算部４０と、局所特徴量計算部４２と、局所特徴量割当部４４と、ヒストグラム作成部４６と、ボックスサイズ決定部４８と、ボックスヒストグラム計算部５０と、ヒストグラム比較部５２と、物体認識処理部５４と、座標復元部５６とを含んで構成されている。
【００２５】
前処理部２２は、以下に説明する各部の処理によって、物体が存在する環境における複数の３次元点群を受け付け、物体の認識に必要な法線ベクトル、局所特徴量、クラスタ、及び３次元積分画像を学習する。
【００２６】
前処理部２２は、法線ベクトル計算部２３と、局所特徴量計算部２４と、クラスタリング部２５と、３次元積分画像作成部２６とを含んで構成されている。
【００２７】
基礎データ記憶部２１には、入力部１０で受け付けた、前処理に用いる、物体が存在する環境における３次元点群が格納されている。また、入力部１０で受け付けた、認識対象物体を表す３次元点群が格納されている。なお、基礎データ記憶部２１を設けずに、外部のレーザーレンジファインダから入力部１０を介してリアルタイムで受け取るようにしてもよい。基礎データ記憶部２１の一例を図２に示す。
【００２８】
法線ベクトル計算部２３は、基礎データ記憶部２１に格納された物体が存在する環境における３次元点群の各点について、当該点の周辺の３次元点を用いて、Ｘ，Ｙ，Ｚ座標における単位ベクトルとして、法線ベクトルを計算し、法線ベクトル記憶部３０に記憶する。法線ベクトルの計算には、非特許文献３に記載の手法を用いる。
【００２９】
［非特許文献３］：K. Klasing, D. Althoff, D. Wollherr, M. Buss,"Comparison of Surface Normal Estimation Methods for Range Sensing Applications", Robotics and Automation, 2009.
【００３０】
法線ベクトル記憶部３０には、法線ベクトル計算部２３により物体が存在する環境における点群について計算されたＮ個の法線ベクトルが格納されている。また、法線ベクトル計算部４０により認識対象物体について計算されたＮ個の法線ベクトルが格納される。法線ベクトル記憶部３０に一例を図３に示す。
【００３１】
局所特徴量計算部２４は、物体が存在する環境における３次元点群の各点について、法線ベクトル記憶部３０に記憶された法線ベクトルに基づいて、当該点の局所特徴量を計算し、局所特徴量記憶部３２に格納する。ここでは、局所特徴量用に予め定めたサイズのＭ個のボクセルの各々について、当該ボクセルの中心位置に近い所定の個数の３次元点に対して計算された法線ベクトルを利用してＳＨＯＴという特徴量を算出する（上記非特許文献２参照）。なお、３次元点群からサンプリングしたＭ個の点の各々について、局所特徴量を計算してもよい。
【００３２】
局所特徴量記憶部３２には、局所特徴量計算部２４によって計算されたＭ個の局所特徴量が格納されている。また、局所特徴量には、後述するクラスタリング部２５によって割り当てられたクラスタ中心のクラスタ番号が付与される。局所特徴量はＤ次元のベクトルで表現される。また、局所特徴量に対応付けて、ｘ、ｙ、ｚの座標値（局所特徴量用のボクセルの中心の座標値）も記憶しておく。局所特徴量記憶部３２の一例を図４に示す。
【００３３】
クラスタリング部２５は、局所特徴量計算部２４によって計算されたＭ個の局所特徴量に基づいて、非特許文献１に記載のコードブック学習の手法を用いて、Ｋ個のクラスタについて、クラスタ中心を計算し、各クラスタに、Ｍ個の局所特徴量の各々を割り当てる。計算したクラスタ中心はクラスタ記憶部３４に格納する。また、各クラスタに各局所特徴量を割り当てた結果として、各局所特徴量に対するクラスタ番号を局所特徴量記憶部３２に格納する。クラスタ数Ｋはあらかじめ設定により定めておく。ここでは、大量の３次元点群のデータを用いてクラスタリングすることによって、有意なクラスタ中心を得ることができる。
【００３４】
クラスタ記憶部３４には、クラスタリング部２５によって計算されたＫ個のクラスタのクラスタ中心が格納されている。クラスタ記憶部３４の一例を図５に示す。
【００３５】
３次元積分画像作成部２６は、物体が存在する環境を表す３次元点群を含む３次元空間を、３次元積分画像用に予め定められた大きさのボクセルによって離散化する。離散化されたｘ、ｙ、ｚの座標値で、点群が含まれる最大の座標値をそれぞれＸｍａｘ、Ｙｍａｘ、Ｚｍａｘとする。次に、局所特徴量計算部２４によって計算されたＭ個の局所特徴量と、クラスタリング部２５によってＭ個の局所特徴量に割り当てられたクラスタとに基づいて、３次元空間内の離散化されたボクセルの各々に対して、当該ボクセルと３次元空間の原点とで規定される直方体の範囲に含まれる局所特徴量から計算される、各クラスタの頻度を表すヒストグラムを格納した３次元積分画像を計算する。２次元の積分画像の考えを３次元に拡張して、計算対象のボックス周辺のボクセルについて格納されたヒストグラムの和及び差を用いて、計算対象のボックスの中の各クラスタの頻度がわかるようにする。なお、積分する単位は設定によりあらかじめ定めておく。また、局所特徴量のボクセルのサイズとは独立して指定するようにしてよい。
【００３６】
積分画像記憶部３６には、３次元積分画像作成部２６によって計算された３次元積分画像が格納されている。具体的には、図６に示すように、各ボクセルについて、ボクセルのインデックス番号と、各クラスタの頻度とが格納されている。
【００３７】
法線ベクトル計算部４０は、基礎データ記憶部２１に格納された認識対象物体の３次元点群内の各点に対して、法線ベクトル計算部２３と同様に、法線ベクトルを計算し、法線ベクトル記憶部３０に格納する。
【００３８】
局所特徴量計算部４２は、基礎データ記憶部２１に格納された認識対象物体の３次元点群に基づいて、認識対象物体の３次元点群からサンプリングされた各点について、局所特徴量を計算し、局所特徴量記憶部３２に格納する。ここでは、局所特徴量計算部２４と同様に、各点に対して計算された法線ベクトルを利用してＳＨＯＴという特徴量を算出する（上記非特許文献２参照）。
【００３９】
局所特徴量割当部４４は、クラスタ記憶部３４に格納された各クラスタのクラスタ中心と、局所特徴量計算部４２によって認識対象物体を表す３次元点群の各点について計算された局所特徴量とに基づいて、各クラスタに、認識対象物体を表す３次元点群の各点について計算された局所特徴量の各々を割り当てる。
【００４０】
ヒストグラム作成部４６は、局所特徴量割当部４４によって各点についての局所特徴量
を各クラスタに割り当てた結果から、各クラスタに割り当てられた局所特徴量の数を計算し、認識対象物体を表現する、各クラスタの出現頻度を表すヒストグラムを計算する。
【００４１】
ボックスサイズ決定部４８は、認識対象物体を表す３次元点群から当該３次元点群の大きさを表現するボックスのサイズを計算する。ｘ方向の大きさは、３次元点群のｘ方向の計測データを用いて、以下の（１）式により計算できる。
【００４２】
【数１】
0006499599.tif 000002
【００４３】
最大値、最小値は、３次元点群のｘ方向の最大値、最小値である。ｒは、３次元積分画像用のボクセルの一辺の長さとし、ボックスがボクセル何個分となるかのサイズが決定される。上記はｘ方向の場合と同様に、ｙ、ｚについても同様に計算できる。
【００４４】
また、ボックスサイズ決定部４８は、基礎データ記憶部２１に格納された環境を表す３次元点群を含む３次元空間であって、かつ、ボクセルによって離散化された３次元空間をスキャニングするように、計算したサイズのボックスを配置し、各配置パターンを決定する。なお、ボックスの大きさを変えたものを３次元空間に配置した配置パターンを更に決定するようにしてもよい。
【００４５】
ボックスヒストグラム計算部５０は、積分画像記憶部３６に記憶された３次元積分画像を用いて、ボックスサイズ決定部４８によって決定されたボックスを配置する各配置パターンに対して、当該配置パターンにおけるボックスを表現するヒストグラムを計算する。計算されるヒストグラムは、ボックス内に存在する局所特徴量に割り当てられた各クラスタの出現頻度を表す。当該配置パターンにおけるボックスを表現するヒストグラムは、３次元積分画像の各ボクセルに保存されたヒストグラムを用いて高々８回の和または差の計算によって計算される。
【００４６】
ヒストグラム比較部５２は、ボックスヒストグラム計算部５０によって各配置パターンに対して計算されたヒストグラムと、ヒストグラム作成部４６によって計算されたヒストグラムの比較を行い、各配置パターンに対してスコアを計算する。例えば、ヒストグラムを表すベクトルのベクトル類似度を、スコアとして計算する。
【００４７】
認識結果記憶部３８には、ヒストグラム比較部５２によって各配置パターンに対して計算されたスコアが格納されている。認識結果記憶部３８の一例を図７に示す。配置パターンに対応するインデックスとスコアとが格納されている。
【００４８】
物体認識処理部５４は、ヒストグラム比較部５２によって計算されたボックスの各配置パターンに対するスコアから、ボックス内に認識対象物体が含まれるようなボックスの配置パターンを決定する。ここでは、スコアの値が閾値以上であり、かつ、周囲の配置パターンのインデックスに対するスコアと比較して、着目する配置パターンのインデックスのスコアが極大（最も高いスコア）になっていれば、そのインデックスに対応する位置に、物体が存在すると認識する。そして、物体が存在すると認識されたインデックスに対して、認識結果を認識結果記憶部３８に追加する。
【００４９】
座標復元部５６は、物体認識処理部５４によって得られた配置パターンのインデックスとボックスサイズ決定部４８によって得られたボックスサイズから、上記（１）式とは逆の計算を行って、離散化された座標値から認識対象物体が存在する三次元座標を復元し、出力部６０に出力する。
【００５０】
＜本発明の実施の形態に係る物体認識装置の作用＞
【００５１】
次に、本発明の実施の形態に係る物体認識装置１００の作用について説明する。入力部１０において物体が存在する環境における３次元点群を受け付けて基礎データ記憶部２１に格納すると、物体認識装置１００は、図８に示す前処理ルーチンを実行する。
【００５２】
まず、ステップＳ１００では、基礎データ記憶部２１に格納された物体が存在する環境における３次元点群の各点について、Ｘ，Ｙ，Ｚ座標における単位ベクトルとして、法線ベクトルを計算し、法線ベクトル記憶部３０に記憶する。
【００５３】
次に、ステップＳ１０２では、基礎データ記憶部２１に格納された物体が存在する環境における３次元点群と、法線ベクトル記憶部３０に記憶された各点の法線ベクトルとに基づいて、局所特徴量用に予め定めたサイズのＭ個のボクセルの各々について、局所特徴量を計算し、局所特徴量記憶部３２に格納する。
【００５４】
ステップＳ１０４では、局所特徴量計算部２４によって計算されたＭ個の局所特徴量に基づいて、非特許文献１に記載のコードブック学習の手法を用いて、Ｋ個のクラスタについて、クラスタ中心を計算し、各クラスタにＭ個の局所特徴量の各々を割り当て、Ｍ個の局所特徴量の各々に対するクラスタ番号を局所特徴量記憶部３２に格納し、各クラスタのクラスタ中心をクラスタ記憶部３４に格納する。
【００５５】
ステップＳ１０６では、基礎データ記憶部２１に格納された環境を表す３次元点群を含む３次元空間を、予め定められた大きさのボクセルによって離散化する。
【００５６】
ステップＳ１０８では、ステップＳ１０４で計算されたＭ個の局所特徴量と、ステップＳ１０４でＭ個の局所特徴量に割り当てられたクラスタとに基づいて、３次元空間内の離散化されたボクセルの各々に対して、当該ボクセルと３次元空間の原点とで規定される直方体の範囲に含まれる局所特徴量から計算されるヒストグラムを格納した３次元積分画像を計算して、積分画像記憶部３６に格納する。
【００５７】
次に、物体認識処理ルーチンについて説明する。入力部１０において認識対象物体を表す３次元点群を受け付けて基礎データ記憶部２１に格納すると、物体認識装置１００は、図９に示す物体認識処理ルーチンを実行する。
【００５８】
ステップＳ２００では、基礎データ記憶部２１に格納された認識対象物体の３次元点群内の各点に対して、法線ベクトルを計算し、法線ベクトル記憶部３０に格納する。
【００５９】
ステップＳ２０２では、基礎データ記憶部２１に格納された認識対象物体の３次元点群に基づいて、３次元点群からサンプリングされた各点について、局所特徴量を計算し、局所特徴量記憶部３２に格納する。
【００６０】
ステップＳ２０４では、クラスタ記憶部３４に格納された各クラスタのクラスタ中心に基づいて、ステップＳ２０２で認識対象物体を表す３次元点群の各点について計算された局所特徴量を、各クラスタに割り当てる。
【００６１】
ステップＳ２０６では、ステップＳ２０４で局所特徴量をクラスタに割り当てた結果から、各クラスタに割り当てられた局所特徴量の数を計算し、認識対象物体を表現するヒストグラムを計算する。
【００６２】
ステップＳ２０８では、認識対象物体を表す３次元点群から当該３次元点群の大きさを表現するボックスのサイズを上記（１）式により計算する。
【００６３】
ステップＳ２１０では、基礎データ記憶部２１に格納された環境を表す３次元点群を含む３次元空間であって、ボクセルによって離散化された３次元空間に、ステップＳ２０８でサイズが計算されたボックスを配置し、ボックスの各配置パターンを決定する。
【００６４】
ステップＳ２１１では、積分画像記憶部３６に記憶された３次元積分画像を用いて、上記ステップＳ２１０で決定されたボックスを配置する各配置パターンに対して、当該配置パターンにおけるボックスを表現するヒストグラムを計算する。当該配置パターンにおけるボックスを表現するヒストグラムは、３次元積分画像の各ボクセルに保存されたヒストグラムを用いて高々８回の和または差の計算によって計算される。
【００６５】
ステップＳ２１２では、ステップＳ２１０で各配置パターンに対して計算されたヒストグラムと、ステップＳ２０６で計算されたヒストグラムの比較を行い、各配置パターンに対してスコアを計算する。
【００６６】
ステップＳ２１４では、ステップＳ２１２によって計算されたボックスの各配置パターンに対するスコアから、スコアが最も高い配置パターンを、ボックス内に認識対象物体が含まれるようなボックスの配置パターンとして決定する。
【００６７】
ステップＳ２１６では、物体認識処理部５４によって得られた配置パターンから認識対象物体が存在する三次元座標を復元し、出力部６０に出力し処理を終了する。
【００６８】
以上説明したように、本発明の実施の形態に係る物体認識装置によれば、認識対象物体を表現するヒストグラムを計算し、認識対象物体を表す３次元点群から当該３次元点群の大きさを表現するボックスを計算し、認識対象物体が存在する環境を表す３次元点群を含む３次元空間にボックスを配置した配置パターンを決定し、配置パターンにおけるボックスを表現するヒストグラムを計算し、各配置パターンに対して計算されたヒストグラムと、認識対象物体を表現するヒストグラムの比較を行い、各配置パターンに対してスコアを計算し、ボックスの各配置パターンに対するスコアから、配置パターンを決定し、配置パターンから認識対象物体が存在する三次元座標を復元することにより、精度よく、３次元点群から物体を認識することができる。
【００６９】
なお、本発明は、上述した実施の形態に限定されるものではなく、この発明の要旨を逸脱しない範囲内で様々な変形や応用が可能である。
【００７０】
例えば、上述した実施の形態では物体認識装置１００について説明したがこの装置及び構成に限定されるものではない。例えば、認識対象物体をモデル化するために、基礎データ記憶部２１と、法線ベクトル記憶部３０と、局所特徴量記憶部３２と、クラスタ記憶部３４と、積分画像記憶部３６と、法線ベクトル計算部４０と、局所特徴量計算部４２と、局所特徴量割当部４４と、ヒストグラム作成部４６と、ボックスサイズ決定部４８と、ボックスヒストグラム計算部５０と、を含む３次元点群モデル化装置として構成するようにしてもよい。
【符号の説明】
【００７１】
１０   入力部
２０   演算部
２２   前処理部
２１   基礎データ記憶部
２３   法線ベクトル計算部
２４   局所特徴量計算部
２５   クラスタリング部
２６   ３次元積分画像作成部
３０   法線ベクトル記憶部
３２   局所特徴量記憶部
３４   クラスタ記憶部
３６   積分画像記憶部
３８   認識結果記憶部
４０   法線ベクトル計算部
４２   局所特徴量計算部
４４   局所特徴量割当部
４６   ヒストグラム作成部
４８   ボックスサイズ決定部
５０   ボックスヒストグラム計算部
５２   ヒストグラム比較部
５４   物体認識処理部
５６   座標復元部
６０   出力部
１００ 物体認識装置
【図１】
0006499599.tif 000003
【図２】
0006499599.tif 000004
【図３】
0006499599.tif 000005
【図４】
0006499599.tif 000006
【図５】
0006499599.tif 000007
【図６】
0006499599.tif 000008
【図７】
0006499599.tif 000009
【図８】
0006499599.tif 000010
【図９】
0006499599.tif 000011