(57)【特許請求の範囲】
【請求項１】
物体の位置及び姿勢を認識する物体認識方法であって、
新たな計測位置から計測して得られた三次元形状上の座標値をコンピュータに入力するデータ入力ステップと、
前記三次元形状の存在する空間領域を、境界表面が互いに直交する直方体からなる複数のボクセルに分割し、各ボクセル位置を記憶する環境モデルを構築するモデル構築ステップと、
前記座標値に対応するボクセルの内部に代表点とその誤差分布を設定し記憶する第１マッチングステップとを実施し、
先の計測位置から計測して得られた前記三次元形状のデータが存在しない場合には、新たな計測位置を自己位置と同定し、
先の計測位置から計測して得られた前記三次元形状のデータが存在する場合には、
先の計測位置に対する環境モデルに対し、
新たな計測データおよび誤差分布を回転及び並進させ、または
新たな計測位置に対する環境モデルを回転及び並進させ、
近接する誤差分布間の距離に関する評価値が最小になるように位置合わせする精密合わせステップと、
前記精密合わせステップにおける回転量及び並進量から自己位置を同定する自己位置同定ステップとを実施し、
更に複数の計測位置から計測された複数の計測データおよび複数の誤差分布を統合する統合ステップと、
統合して得られた計測データおよび誤差分布に対し、モデルデータによって表される被計測物を回転および並進させ、前記統合して得られた計測データと前記モデルデータを構成する要素との距離に関する評価値が最小になるようにする位置合わせをする第２マッチングステップとを実施する、ことを特徴とする物体認識方法。
【請求項２】
前記第２マッチングステップにおいて、計測データとモデルデータを構成する要素との距離を用いて、計測データとモデルデータの差異を判断することにより、物体の検査を可能とする、ことを特徴とする請求項１に記載の物体認識方法。
【請求項３】
前記第１マッチングステップにおいて、ボクセルの内部に代表点とその誤差分布に加え、ボクセル内に物体の存在確率を表す確率値を設定し、記憶する、ことを特徴とする請求項１に記載の物体認識方法。
【請求項４】
前記精密合わせステップの前に、先の計測位置に対する環境モデルに対し、
新たな計測データおよび誤差分布を回転及び並進させ、計測データおよび誤差分布と近接する代表点を有するボクセル間との距離の総和が最小になるように、または
新たな計測位置に対する環境モデルを回転及び並進させ、代表点を有するボクセル間の距離の総和が最小になるように、
位置合わせする粗合わせステップを有する、ことを特徴とする請求項１に記載の物体認識方法。
【請求項５】
前記精密合わせステップの前に、先の計測位置に対する環境モデルに対し、
新たな計測データおよび誤差分布を回転及び並進させ、計測データおよび誤差分布と近接する代表点を有するボクセルの確率値の総和が最大になるように、または
新たな計測位置に対する環境モデルを回転及び並進させ、近接するボクセルが持つ確率値の差の総和が最小になるように、
位置合わせする粗合わせステップを有する、ことを特徴とする請求項１に記載の物体認識方法。
【請求項６】
前記データ入力ステップの後に、
現在の計測位置を過去の計測位置の変化から推定し、または
現在の計測位置を取得可能なセンサにより取得し、または
計測データの距離値だけでなく反射強度値を利用し、
照合する範囲を限定する探索範囲限定ステップを有する、ことを特徴とする請求項１に記載の物体認識方法。
【請求項７】
前記自己位置同定ステップにおいて、先の計測位置における位置及び姿勢から新たな計測位置の６自由度位置を同定する、ことを特徴とする請求項１に記載の物体認識方法。
【請求項８】
前記精密合わせステップにおいて、誤差分布が交差する場合を同一計測点とし、その場合の距離値に分布の一致度から求めた重みを掛け合わせて誤差分布間の距離を算出する、ことを特徴とする請求項１に記載の物体認識方法。
【請求項９】
前記モデル構築ステップにおいて、最大のボクセルを必要最小限の分解能に相当する大きさに設定し、かつ単一のボクセル内に複数の被計測点が存在する場合に、単一のボクセル内に単一の被計測点のみが存在するように、該ボクセルを更に分割して階層的に複数のボクセルに分割する、ことを特徴とする請求項１に記載の物体認識方法。
【請求項１０】
前記自己位置同定ステップの後に、前記環境モデルを更新するモデル更新ステップを有し、該モデル更新ステップにおいて、新たに入力された被計測点の座標値に対応するボクセルを探索し、
原点と被計測点の間に物体が存在しないものとして、その間に位置するボクセル内の代表点と誤差分布を再設定もしくは消去する、ことを特徴とする請求項１に記載の物体認識方法。
【請求項１１】
前記自己位置同定ステップの後に、前記環境モデルを更新するモデル更新ステップを有し、該モデル更新ステップにおいて、新たに入力された被計測点の座標値に対応するボクセルを探索し、
該ボクセル内に代表点がない場合に、前記座標値と誤差分布を代表点の座標値と誤差分布として設定する、ことを特徴とする請求項１に記載の物体認識方法。
【請求項１２】
前記自己位置同定ステップの後に、前記環境モデルを更新するモデル更新ステップを有し、該モデル更新ステップにおいて、新たに入力された被計測点の座標値に対応するボクセルを探索し、
前記ボクセル内に既に設定した代表点がある場合に、新たに取得した誤差分布と既に設定したボクセル内の誤差分布とを比較し、
誤差分布が互いに重複する場合に、両誤差分布から新たな誤差分布と新たな代表点を再設定し、
誤差分布が互いに重複しない場合に、単一のボクセル内に単一の代表点のみが存在するように、該ボクセルを更に分割して階層的に複数のボクセルに分割する、ことを特徴とする請求項１に記載の物体認識方法。
【請求項１３】
前記自己位置同定ステップにおいて、自己位置の同定とともに、自己位置の誤差分布を同定し、現在の自己位置と誤差分布および同定した自己位置と誤差分布とからカルマンフィルタによって、自己位置と誤差分布を補正する、ことを特徴とする請求項１に記載の物体認識方法。
【請求項１４】
前記自己位置同定ステップの後に、前記環境モデルを更新するモデル更新ステップを有し、該モデル更新ステップにおいて、前記新たに取得した誤差分布と前記既に設定したボクセル内の誤差分布とを比較し、誤差分布が互いに重複する場合に、両誤差分布から新たな誤差分布と新たな代表点を再設定した結果、新たな代表点が他のボクセル内へ移動したとき、
該他のボクセル内に代表点がない場合に、該新たな誤差分布と該新たな代表点を該他のボクセルの内部に設定し、
該他のボクセル内に既に設定した代表点がある場合に、該新たな誤差分布と既に設定した該他のボクセル内の誤差分布とを比較し、（Ａ）誤差分布が互いに重複する場合に、両誤差分布から、または、両誤差分布とボクセル内に既に設定した代表点と新たに入力された被計測点の座標値から、新たな誤差分布と新たな代表点を再設定し、（Ｂ）誤差分布が互いに重複しない場合に、単一のボクセル内に単一の代表点のみが存在するように、該ボクセルを更に分割して階層的に複数のボクセルに分割する、ことを特徴とする請求項１に記載の物体認識方法。
【請求項１５】
前記自己位置同定ステップの後に、前記環境モデルを更新するモデル更新ステップを有し、
該モデル更新ステップにおいて、新たに入力された被計測点の座標値およびその誤差分布と、既に設定したボクセル内の代表点およびその誤差分布とから、カルマンフィルタにより新たな代表点と誤差分布を取得して再設定する、ことを特徴とする請求項１に記載の物体認識方法。
【請求項１６】
前記精密合わせステップにおいて、前記近接する誤差分布間の距離に関する評価値が最小になるように位置合わせする代わりに、前記近接する誤差分布間に基づく最尤推定値によって定めた一致度に関する評価値が最大となるように、先の計測位置に対する環境モデルに対し、
新たな計測データおよび誤差分布を回転及び並進させ、または
新たな計測位置に対する環境モデルを回転及び並進させて位置合わせする、ことを特徴とする請求項１に記載の物体認識方法。
【請求項１７】
前記精密合わせステップにおける前記一致度に関する評価値の算出式が次の［数１］の式で表わされ、
【数１】
0005380792.tif 000016
この式において、計測点ｊと環境モデル上の代表点ｉとが対応付けられているとし、当該計測点ｊなる計測データが得られる確率をＥＭ（ｉ、ｊ）としており、ω（ｊ）は、環境モデルの中に計測点ｊと対応付けられる代表点が存在する場合は１、それ以外の場合は０としている、ことを特徴とする請求項１６に記載の物体認識方法。
【請求項１８】
前記統合ステップにおいて、新たに入力された被計測点の座標値に対応するボクセルを探索し、
前記ボクセル内に既に設定した代表点がある場合に、新たに取得した誤差分布と既に設定したボクセル内の誤差分布とを比較し、
誤差分布が互いに重複する場合に、両誤差分布から新たな誤差分布と新たな代表点を再設定し、
誤差分布が互いに重複しない場合に、単一のボクセル内に単一の代表点のみが存在するように、該ボクセルを更に分割して階層的に複数のボクセルに分割する、ことを特徴とする請求項１に記載の物体認識方法。
【請求項１９】
前記統合ステップにおいて、両誤差分布から新たな誤差分布と新たな代表点を再設定した結果、新たな代表点が他のボクセル内へ移動したとき、
該他のボクセル内に代表点がない場合に、該新たな誤差分布と該新たな代表点を該他のボクセルの内部に設定し、
該他のボクセル内に既に設定した代表点がある場合に、該新たな誤差分布と既に設定した該他のボクセル内の誤差分布とを比較し、（Ａ）誤差分布が互いに重複する場合に、両誤差分布から、または、両誤差分布とボクセル内に既に設定した代表点と新たに入力された被計測点の座標値から、新たな誤差分布と新たな代表点を再設定し、（Ｂ）誤差分布が互いに重複しない場合に、単一のボクセル内に単一の代表点のみが存在するように、該ボクセルを更に分割して階層的に複数のボクセルに分割する、ことを特徴とする請求項１８に記載の物体認識方法。
【請求項２０】
物体の位置及び姿勢を認識する物体認識装置であって、
新たな計測位置から計測して得られた三次元形状上の座標値をコンピュータに入力するデータ入力部と、
前記三次元形状の存在する空間領域を、境界表面が互いに直交する直方体からなる複数のボクセルに分割し、各ボクセル位置を記憶する環境モデルを構築するモデル構築部と、
前記座標値に対応するボクセルの内部に代表点とその誤差分布を設定し記憶する第１マッチング部と、
先の計測位置から計測して得られた前記三次元形状のデータが存在しない場合には、新たな計測位置を自己位置と同定し、
先の計測位置から計測して得られた前記三次元形状のデータが存在する場合には、
先の計測位置に対する環境モデルに対し、（Ａ）新たな計測データおよび誤差分布を回転及び並進させ、または（Ｂ）新たな計測位置に対する環境モデルを回転及び並進させ、近接する誤差分布間の距離に関する評価値が最小になるように位置合わせし、位置合わせに必要な回転量及び並進量から自己位置を同定する自己位置同定部と、
複数の計測位置から計測された複数の計測データおよび複数の誤差分布を統合する統合部と、
統合して得られた計測データおよび誤差分布に対し、モデルデータによって多面体として表される被計測物を回転および並進させ、前記統合して得られた計測データと前記多面体を構成する平面との距離に関する評価値が最小になるようにする位置合わせをする第２マッチング部とを具備する、ことを特徴とする物体認識装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、被計測物たる物体の形状、計測地点から計測して得られた被計測物の位置、姿勢を認識する方法と装置に関する。
【背景技術】
【０００２】
従来は、複数のビジョンセンサで撮影し、第１〜ｎ画像から物体の二次元特徴を抽出し、その対応付けで物体の二次元特徴の三次元情報を加え、物体の三次元位置・姿勢を推定している（例えば、特許文献１参照）。
ただし、位置・姿勢の信頼度評価値は、二次元画像処理のエッジ抽出精度に依存するため、高い精度は得られない。また、信頼性評価に使用する特徴量を事前に設定しておく必要がある。
【０００３】
また、距離センサによって得られた距離データから、物体の特徴的な部位（例えば、円柱、楕円）の大まかな位置を求め、これに従ってビジョンセンサを物体に正対させた後に、二次元処理により特徴部位を検出し、物体の精密な位置・姿勢を求めるものもある。
ただし、この場合は、距離データだけで物体の位置・姿勢を特定することはできず、二段構えであるためコストと時間がかかる。また、検出できる物体の形状的な制約が大きい。さらに、形状検査に適用するには精度が不十分である。
【０００４】
また、単眼ビジョンセンサで、事前に物体の見え方を十分教示しておくことで、現在の見え方から物体の位置・姿勢を推定するものもある。
ただし、物体が一部隠れているような場合に対応が困難である。また、ビジョンセンサを用いるため、照明条件に依存する。さらに、大量の画像を予め教示しておく必要がる。また、形状検査に適用するには精度が不十分である。
【特許文献１】特許第３５２５８９６号公報
【発明の開示】
【発明が解決しようとする課題】
【０００５】
ビジョンセンサを用いてワーク（被計測物）の位置・姿勢を認識する場合、ワークの背景情報や外光等の照明条件の変化に影響を受け易い。そこで、背景の単一化や照明条件の安定化により計測環境を整える必要があるが、これら環境の整備は必ずしも可能ではない。これに対して、レーザ光をワークに投影して距離データを取得するレーザスキャナ等は、背景の影響を受けず、照明条件の変化に対してロバストであり、環境の整備を行うことなく、ワークの形状を計測することができる。ただし、レーザスキャナを用いた場合の欠点として、レーザ光のワーク表面に対する入射角度が浅い場合や、レーザ光が直接反射するような場合等に、計測結果に欠損や誤差が発生する点が挙げられる。加えて、レーザスキャナは三角測量方式とＴＯＦ(Time of Flight)方式に大別できるが、三角測量方式のレーザスキャナは、計測可能な距離の範囲が狭いため、単一視点からの計測ではワークの一部しか計測できないという問題がある。また、ＴＯＦ方式のレーザスキャナは、一般に三角測量方式に比べて計測範囲は広いが距離計測精度が低いと言う問題を持つ。
【０００６】
三次元レーザレーダのような距離センサを用いる場合、計測される三次元形状上の被計測点は、横方向及び垂直方向に離散した点群となる。この点群の間隔は、計測点からの距離が例えば５０ｍの場合、被計測点の間隔は、例えば横方向で約３１５ｍｍ、垂直方向で約５２５ｍｍに達する。
【０００７】
また、複数の計測位置から静止している三次元形状を計測する場合、三次元レーザレーダのような距離センサでは、計測位置毎に、被計測点の位置は通常異なる。
さらに、このような距離センサは、一般に測定距離に例えば約２０ｃｍ前後の誤差を有する。
従って、三次元レーザレーダのような距離センサを用いる場合、以下の制約条件Ａ〜Ｃがある。
条件Ａ：計測データに点数が少ない（例えば、１フレーム＝１６６×５０点）
条件Ｂ：計測データに誤差を含む（例えば、測定距離に約２０ｃｍ前後）
条件Ｃ：計測データは同じ計測点を計るとは限らない。
すなわち、得られる距離データは横方向及び垂直方向に離散した点群であり、計測毎に位置が相違するため対応点がなく、測定距離に比較的大きな誤差を含んでいる。
【０００８】
このような距離データを「ＩＣＰ（Iterative Closest Point）アルゴリズム」で処理する場合、以下の問題点がある。
ＩＣＰアルゴリズムは、対応点が既知でない場合の位置合わせ手段の１つであり、先の計測データに対するその後の計測データの最も近傍の点を求め、回転・並進を行いながらその距離の総和が最小になる状態を一致状態となるように解を求めるものである。
（１）誤差の蓄積
ＩＣＰアルゴリズムは、２つの距離データの重ね合わせ手段であり、先のデータとその後のデータとの比較を繰り返し、その差分を積分しても、対応点がほとんどないため、誤差が蓄積してしまう。
（２）計算量が多い
ＩＣＰアルゴリズムは、繰り返し計算であるため、計算量が膨大となる。すなわち、ＩＣＰアルゴリズムは、計測データの各データ点に対応するモデルデータを探索する必要があるため、モデルデータ点数および計測データ点数が増加すると計算量が増大する。具体的には、モデルデータの点数をＭ、計測データの点数をＮとした場合、例えば全探索時の計算オーダは、Ｏ（Ｍ×Ｎ）となる。
（３）計測点が少ない場合を扱えない
ＩＣＰアルゴリズムは、密な距離データを対象としているため、離散した点群であり、空間的に疎である場合は、誤った結果に収束してしまう。
【０００９】
そのため、このような距離センサを用いた位置同定には、以下の要件を満たす必要がある。
（１）メモリ効率の良い周囲環境のためのデータ構造
逐次得られる計測データを全て保存する方法では無尽蔵にメモリを必要とする。よって、周囲環境を計測した結果を効率良く格納するデータ構造が必要である。
（２）計測データの点数不足および誤差に対する安定性
計測データの点数が少ない場合、および、誤差を含む場合であっても、できるだけ位置同定精度が低下しない必要がある。
（３）位置同定のための計算の効率化
周囲環境を計測して獲得した環境情報と計測データの比較により、自己位置同定を行うが、この比較処理に多くの計算を必要とする。
【課題を解決するための手段】
【００１０】
本発明は上述した問題点を解決するために創案されたものである。すなわち、位置・姿勢が未知のワークをレーザスキャナ等の距離センサにより複数の視点から計測し、計測結果の欠損部分を別視点のデータで充填しながら、なおかつ精度良く統合することができる物体認識の方法と装置を提供する。計測範囲が狭いという三角測量方式の欠点は、複数視点からのデータをつなぎ合わせながら統合することで解決する。また、距離計測が低精度というＴＯＦ方式の欠点も、複数回の計測を統計的手法により統合することで解決可能となる。
【００１１】
本発明の第１の特徴は、物体の位置及び姿勢を認識する物体認識方法であって、
（１）新たな計測位置から計測して得られた三次元形状上の座標値をコンピュータに入力するデータ入力ステップと、
（２）前記三次元形状の存在する空間領域を、境界表面が互いに直交する直方体からなる複数のボクセルに分割し、各ボクセル位置を記憶する環境モデルを構築するモデル構築ステップと、
（３）前記座標値に対応するボクセルの内部に代表点とその誤差分布を設定し記憶する第１マッチングステップとを実施し、
（４−１）先の計測位置から計測して得られた前記三次元形状のデータが存在しない場合には、新たな計測位置を自己位置と同定し、
（４−２）先の計測位置から計測して得られた前記三次元形状のデータが存在する場合には、
（４−２−１）先の計測位置に対する環境モデルに対し、（Ａ）新たな計測データおよび誤差分布を回転及び並進させ、または（Ｂ）新たな計測位置に対する環境モデルを回転及び並進させ、近接する誤差分布間の距離に関する評価値が最小になるように位置合わせする精密合わせステップと、
（４−２−２）前記精密合わせステップにおける回転量及び並進量から自己位置を同定する自己位置同定ステップとを実施し、
（５）更に複数の計測位置から計測された複数の計測データおよび複数の誤差分布を統合する統合ステップと、
（６）統合して得られた計測データおよび誤差分布に対し、モデルデータによって表される被計測物を回転および並進させ、前記統合して得られた計測データと前記モデルデータを構成する要素との距離に関する評価値が最小になるようにする位置合わせをする第２マッチングステップとを実施する、ことにある。
モデルデータの表現方法としては、例えば、多面体、自由曲面、ボクセルおよび代表点と誤差分布の集合などが挙げられる。
距離に関する評価値は、当該距離の総和、当該距離の平均値、当該距離の２乗の総和、または、当該距離の最大値であってもよく、他の適切な評価値であってもよい。
「座標値に対応するボクセル」とは、その座標値によって特定される点が内部に存在するボクセルという意味である。
「代表点」とは、統計処理の結果得られる、誤差分布の中心や最尤推定値等である。
「代表点とその誤差分布」を設定する方法、「誤差分布間の距離」を求める方法については後述する。
【００１２】
前記第２マッチングステップにおいて、計測データとモデルデータを構成する要素との距離を用いて、計測データとモデルデータの差異を判断することにより、物体の検査を可能とする、としても良い。
また、前記第１マッチングステップにおいて、ボクセルの内部に代表点とその誤差分布に加え、ボクセル内に物体の存在確率を表す確率値を設定し、記憶する、としても良い。
【００１３】
前記精密合わせステップの前に、先の計測位置に対する環境モデルに対し、
（１）新たな計測データおよび誤差分布を回転及び並進させ、計測データおよび誤差分布と近接する代表点を有するボクセル間との距離の総和が最小になるように、または
（２）新たな計測位置に対する環境モデルを回転及び並進させ、代表点を有するボクセル間の距離の総和が最小になるように、
位置合わせする粗合わせステップを有する、としても良い。
【００１４】
前記精密合わせステップの前に、先の計測位置に対する環境モデルに対し、
（１）新たな計測データおよび誤差分布を回転及び並進させ、計測データおよび誤差分布と近接する代表点を有するボクセルの確率値の総和が最大になるように、または
（２）新たな計測位置に対する環境モデルを回転及び並進させ、近接するボクセルが持つ確率値の差の総和が最小になるように、
位置合わせする粗合わせステップを有する、としても良い。
【００１５】
前記データ入力ステップの後に、
（１）現在の計測位置を過去の計測位置の変化から推定し、または
（２）現在の計測位置を取得可能なセンサにより取得し、または
（３）計測データの距離値だけでなく反射強度値を利用し、
照合する範囲を限定する探索範囲限定ステップを有する、としても良い。
【００１６】
前記自己位置同定ステップにおいて、先の計測位置における位置及び姿勢から新たな計測位置の６自由度位置を同定する、としても良い。
【００１７】
前記精密合わせステップにおいて、誤差分布が交差する場合を同一計測点とし、その場合の距離値に分布の一致度から求めた重みを掛け合わせて誤差分布間の距離を算出する、としても良い。
分布の一致度から重みを求める方法については、後述する。
【００１８】
前記モデル構築ステップにおいて、最大のボクセルを必要最小限の分解能に相当する大きさに設定し、かつ単一のボクセル内に複数の被計測点が存在する場合に、単一のボクセル内に単一の被計測点のみが存在するように、該ボクセルを更に分割して階層的に複数のボクセルに分割する、としても良い。
「必要最小限の分解能に相当する大きさ」とは、計測対象を包含することができる大きさである。
【００１９】
前記自己位置同定ステップの後に、前記環境モデルを更新するモデル更新ステップを有し、該モデル更新ステップにおいて、新たに入力された被計測点の座標値に対応するボクセルを探索し、
原点と被計測点の間に物体が存在しないものとして、その間に位置するボクセル内の代表点と誤差分布を再設定もしくは消去する、としても良い。
【００２０】
前記自己位置同定ステップの後に、前記環境モデルを更新するモデル更新ステップを有し、該モデル更新ステップにおいて、新たに入力された被計測点の座標値に対応するボクセルを探索し、
該ボクセル内に代表点がない場合に、前記座標値と誤差分布を代表点の座標値と誤差分布として設定する、としても良い。
【００２１】
前記自己位置同定ステップの後に、前記環境モデルを更新するモデル更新ステップを有し、該モデル更新ステップにおいて、新たに入力された被計測点の座標値に対応するボクセルを探索し、
前記ボクセル内に既に設定した代表点がある場合に、新たに取得した誤差分布と既に設定したボクセル内の誤差分布とを比較し、
誤差分布が互いに重複する場合に、両誤差分布から新たな誤差分布と新たな代表点を再設定し、
誤差分布が互いに重複しない場合に、単一のボクセル内に単一の代表点のみが存在するように、該ボクセルを更に分割して階層的に複数のボクセルに分割する、としても良い。
２つの誤差分布から新たな誤差分布と新たな代表点を再設定する方法については、後述する。
【００２２】
前記自己位置同定ステップにおいて、自己位置の同定とともに、自己位置の誤差分布を同定し、現在の自己位置と誤差分布および同定した自己位置と誤差分布とからカルマンフィルタによって、自己位置と誤差分布を補正する、としても良い。
自己位置の誤差分布を同定する方法については、後述する。
【００２３】
前記自己位置同定ステップの後に、前記環境モデルを更新するモデル更新ステップを有し、該モデル更新ステップにおいて、前記新たに取得した誤差分布と前記既に設定したボクセル内の誤差分布とを比較し、誤差分布が互いに重複する場合に、両誤差分布から新たな誤差分布と新たな代表点を再設定した結果、新たな代表点が他のボクセル内へ移動したとき、
該他のボクセル内に代表点がない場合に、該新たな誤差分布と該新たな代表点を該他のボクセルの内部に設定し、
該他のボクセル内に既に設定した代表点がある場合に、該新たな誤差分布と既に設定した該他のボクセル内の誤差分布とを比較し、（Ａ）誤差分布が互いに重複する場合に、両誤差分布から、または、両誤差分布とボクセル内に既に設定した代表点と新たに入力された被計測点の座標値から、新たな誤差分布と新たな代表点を再設定し、（Ｂ）誤差分布が互いに重複しない場合に、単一のボクセル内に単一の代表点のみが存在するように、該ボクセルを更に分割して階層的に複数のボクセルに分割する、としても良い。
【００２４】
前記自己位置同定ステップの後に、前記環境モデルを更新するモデル更新ステップを有し、
該モデル更新ステップにおいて、新たに入力された被計測点の座標値およびその誤差分布と、既に設定したボクセル内の代表点およびその誤差分布とから、カルマンフィルタにより新たな代表点と誤差分布を取得して再設定する、としても良い。
【００２５】
前記精密合わせステップにおいて、前記近接する誤差分布間の距離に関する評価値が最小になるように位置合わせする代わりに、前記近接する誤差分布間に基づく最尤推定値によって定めた一致度に関する評価値が最大となるように、先の計測位置に対する環境モデルに対し、
（１）新たな計測データおよび誤差分布を回転及び並進させ、または
（２）新たな計測位置に対する環境モデルを回転及び並進させて位置合わせする、としても良い。
【００２６】
前記一致度に関する評価値の算出式は前記［数１］の式で表わされる。
【００２７】
前記[数１]の式において、計測点ｊと環境モデル上の代表点ｉとが対応付けられているとし、当該計測点ｊなる計測データが得られる確率をＥＭ（ｉ、ｊ）としており、ω（ｊ）は、環境モデルの中に計測点ｊと対応付けられる代表点が存在する場合は１、それ以外の場合は０としている。
「計測点ｊと環境モデル上の代表点ｉとが対応付けられている」とは、計測点ｊに対応するボクセルにすでに代表点が存在する場合をいう。
【００２８】
前記統合ステップにおいて、新たに入力された被計測点の座標値に対応するボクセルを探索し、
前記ボクセル内に既に設定した代表点がある場合に、新たに取得した誤差分布と既に設定したボクセル内の誤差分布とを比較し、
（１）誤差分布が互いに重複する場合に、両誤差分布から新たな誤差分布と新たな代表点を再設定し、
（２）誤差分布が互いに重複しない場合に、単一のボクセル内に単一の代表点のみが存在するように、該ボクセルを更に分割して階層的に複数のボクセルに分割する、ことが好ましい。
【００２９】
前記統合ステップにおいて、両誤差分布から新たな誤差分布と新たな代表点を再設定した結果、新たな代表点が他のボクセル内へ移動したとき、
（１）該他のボクセル内に代表点がない場合に、該新たな誤差分布と該新たな代表点を該他のボクセルの内部に設定し、
（２）該他のボクセル内に既に設定した代表点がある場合に、該新たな誤差分布と既に設定した該他のボクセル内の誤差分布とを比較し、（Ａ）誤差分布が互いに重複する場合に、両誤差分布から、または、両誤差分布とボクセル内に既に設定した代表点と新たに入力された被計測点の座標値から、新たな誤差分布と新たな代表点を再設定し、（Ｂ）誤差分布が互いに重複しない場合に、単一のボクセル内に単一の代表点のみが存在するように、該ボクセルを更に分割して階層的に複数のボクセルに分割する、ことが好ましい。
【００３０】
前記評価値は、前記計測データと、前記計測データに近接する各平面との距離の総和である、ことが好ましい。
【発明の効果】
【００３１】
上記本発明の方法と装置によれば、三次元形状の存在する空間領域を、複数のボクセルに分割し、各ボクセル位置を記憶するので、計測対象物が大きい場合であっても、データ量をボクセル数に比例する小さいデータサイズに抑えることができる。
また、座標値に対応するボクセルの内部に代表点とその誤差分布を設定し記憶するので、ボクセルの分解能以上の情報を表現することができる。
従って、本発明のデータ構造により、複数視点の計測データを固定サイズに統合できる。
【００３２】
また、ボクセルの内部に物体の存在確率を表す確率値を設定し、保存することによって、誤差分布が代表点の属するボクセルよりも広がっている場合においても、各ボクセルにおける物体の存在有無を代表点が属するボクセルを見つけ、その誤差分布から再計算させることなく、当該ボクセルの確率値だけで容易に判断できるので、検索時間を抑えることができる。
また、現在の計測位置を過去の計測位置の変化から推定し、もしくは現在の計測位置を取得可能なセンサにより取得し、もしくは計測データの距離値だけでなく反射強度を利用し、照合する範囲を制限するので、検索時間を抑えることができる。
【００３３】
また、粗合わせステップにおいて、先の計測位置に対する環境モデルに対し、新たな計測データおよび誤差分布を回転及び並進させ、計測データおよび誤差分布と近接する代表点を有するボクセル間との距離に関する評価値（例えば、当該距離の総和）が最小になるように、もしくは新たな計測位置に対する環境モデルを回転及び並進させ、代表点を有するボクセル間の距離に関する評価値（例えば、当該距離の総和）が最小になるように、
もしくは新たな計測データおよび誤差分布を回転及び並進させ、計測データおよび誤差分布と近接する代表点を有するボクセルの確率値に関する評価値（例えば、当該確率値の総和）が最大になるように、もしくは新たな計測位置に対する環境モデルを回転及び並進させ、近接するボクセルが持つ確率値の差に関する評価値（例えば、当該確率値の差の総和）が最小になるように、位置合わせするので、誤差の蓄積を防ぎながら、短時間に代表点を有するボクセル同士の位置合わせができる。
【００３４】
また、先の計測位置に対する環境モデルに対し、新たな計測位置に対する環境モデルを回転及び並進させ、近接するボクセルが持つ確率値の差に関する評価値（例えば、当該確率値の差の総和）が最小になるように、位置合わせする場合には、物体が存在しない情報も加味して位置合わせするので、精度の向上が図れる。
【００３５】
次いで、精密合わせステップにおいて、先の計測位置に対する環境モデルに対し、新たな計測データおよび誤差分布を回転及び並進させ、もしくは新たな計測位置に対する環境モデルを回転及び並進させ、近接する誤差分布間の距離に関する評価値（例えば、当該距離の総和）が最小になるように位置合わせするので、誤差分布同士の精密な位置合わせを短時間にできる。
従って、本発明による複数視点からのデータの統合処理により、誤差の蓄積を防ぎながら、高精度な形状取得を可能にできる。
【００３６】
また、本発明のデータ構造は、ボクセル構造を拡張した構造をしているため、データサイズは点群に比べて小さく済ませることができる。すなわち、本発明で提案するデータ構造はボクセル内に１つの代表点を保存するため、計測点に対応するモデル点を探索する計算オーダを１とすることができるため、全体での計算オーダをＯ（Ｎ）に減少することができる。
従って、周囲環境と計測データの位置合わせ（ＩＣＰアルゴリズム）を行う際に探索対象となるデータ量が減少することから、計算を効率化できる。
【００３７】
さらに、従来のＩＣＰアルゴリズムは疎データに対して誤った結果を出力するが、本発明の環境モデルは、ボクセル内に代表点と誤差分布を持っているため、疎データに対応した位置合わせが可能である。
【００３８】
また、現在の自己位置と誤差分布および同定した自己位置と誤差分布とからカルマンフィルタによって、自己位置と誤差分布を補正することによって、より自己位置の精度を向上させることができる。
【００３９】
従って、本発明の方法と装置によれば、誤差を含むデータを正確な情報に補正する機能を有すると共に、長時間の計測に対して高精度に収束する。なおかつ、位置同定処理は、ボクセルの各ボクセルに対応する代表点とその誤差分布を計測点で更新する処理であるため計算量が小さく、演算は周囲ボクセルへの影響を与えずボクセル内で閉じている。よって、高速な処理が可能である。また、計測データはボクセルに逐次統合可能であり、その結果得られた周囲環境情報のメモリサイズは固定サイズを上回ることはない。
【００４０】
さらに、前記モデル更新ステップにおいて、新たに入力された被計測点の座標値およびその誤差分布と、既に設定したボクセル内の代表点およびその誤差分布とから、カルマンフィルタにより新たな代表点と誤差分布を取得して再設定するので、より真値に近い形状を得ることができる。
特に、カルマンフィルタを用いたモデル更新ステップを繰り返すことで、誤差を含むデータであってもカルマンフィルタの効果により真値に収束した高精度な形状が得られる。
【００４１】
また、前記精密合わせステップにおいて、前記近接する誤差分布間の距離に関する評価値（例えば、当該距離の総和）が最小になるように位置合わせする代わりに、前記近接する誤差分布間に基づく最尤推定値によって定めた一致度に関する評価値（例えば、当該一致度の総乗）が最大となるように、先の計測位置に対する環境モデルに対し、新たな計測データおよび誤差分布を回転及び並進させ、もしくは新たな計測位置に対する環境モデルを回転及び並進させて位置合わせすることで、環境モデル、計測データの双方の誤差を考慮して位置合わせすることができる。
【００４２】
また、前記出力ステップにおいて、前記ボクセルの代表点の位置を三次元形状の計測値として出力装置に出力する際に、該計測値の信頼性または精度を示す指標を、該ボクセルの内部の誤差分布の大きさ出力装置に出力するため、計測装置を使用する際に、信頼性の低い計測値をアプリケーションの内容に応じて使用者が取捨選択することができるようになる。
【００４３】
また、前記出力ステップにおいて、前記ボクセルの代表点の位置を三次元形状の計測値として出力装置に出力するときに、該ボクセルの内部の誤差分布の大きさが所定の基準値よりも大きい場合に、該計測値の信頼性または精度が所定の基準よりも低いとして、該ボクセルの前記計測値を出力装置に出力しないようにすることによって、計測装置を使用する際に、そもそも信頼性の高い計測値のみを扱うことができるようになるため、扱うデータ量を削減することや、信頼性の向上につながる。
【００４４】
また、前記データ入力ステップにおいて、距離センサを用いて、三次元形状上の座標値を任意の計測位置を原点とする距離データとして原点を移動しながら順次取得し、特に異なる方向から距離データを得ることによって、分布形状が異なる誤差分布の距離データを統合することが可能となり、精度を向上することができる。
【００４５】
また、前記マッチングステップの後に、前記環境モデルを更新するモデル更新ステップを有し、該モデル更新ステップにおいて、新たに入力された被計測点の座標値に対応するボクセルを探索し、前記ボクセル内の代表点および誤差分布の少なくともいずれかが新たに設定される、または再設定される、または該ボクセルを更に分割して階層的に複数のボクセルに分割される場合のみ、前記出力ステップにおいて、当該ボクセルの代表点の位置、誤差分布およびボクセルの位置の少なくともいずれかを三次元形状の計測値として出力装置に出力することによって、距離センサから新たに得られた被計測点によって影響を受けたボクセル内の代表点等の値が出力される。このため、使用者は従来と同様の運用を想定しながら、距離センサで得られる元々の計測値があたかもより精度の高い計測値に置き換わったように、利用することができるようになる。このように、より精度の高い三次元形状計測が可能になる。
【００４６】
また、前記出力ステップにおいて、距離センサの位置から距離センサが位置計測可能な範囲の環境モデル内のボクセルの代表点の位置を三次元形状の計測値として出力装置に出力することによって、従来の距離センサの計測値の分解能が粗い場合でも、あたかも精度良くかつ分解能が高い距離センサのように利用することが可能となる。このように、より精度の高い三次元形状計測が可能になる。  
本発明のその他の目的及び有利な特徴は、添付図面を参照した以下の説明から明らかになろう。
【発明を実施するための最良の形態】
【００４７】
以下本発明の好ましい実施形態について、図面を参照して説明する。なお、各図において、共通する部分には同一の符号を付し、重複した説明を省略する。
【００４８】
図１は、本発明の物体認識装置の全体構成図である。図１に示すように、本発明の物体認識装置４０は、計測対象物（ワーク）までの距離を計測する３Ｄセンサ４１、物体認識処理を実行する物体認識処理部４２、被計測対象物の三次元形状を表すデータ（例えば、ＣＡＤデータ）を記憶するモデルデータベース部４３を具備する。物体認識処理部４２において認識された物体の位置や姿勢を、ロボット制御部４５へ出力し、ロボット制御部４５からロボット４６へ制御信号を出力し、ハンド４７を動かして計測対象物を把持したりすることができる。
本発明において、自己位置とは、計測位置を意味し、例えば、３Ｄセンサ４１の外界における６自由度の位置と姿勢を意味する。
図示しないが、本発明において、距離センサ（３Ｄセンサ）以外のオドメータ、カメラ、ＧＰＳ、姿勢センサを、必要に応じてオプションとして用いても良い。以下、距離センサを用いた例を説明する。
【００４９】
図２は、距離センサの一例としての三次元レーザレーダの構成図である。この図に示すように、三次元レーザレーダ１０は、レーダヘッド１２と制御器２０から構成される。レーザダイオード１３から発振されたパルスレーザ光１は、投光レンズ１４で平行光２に整形され、ミラー１８ａ，１８ｂと回転・揺動するポリゴンミラー１５で二次元方向に走査され、測定対象物に照射される。測定対象物から反射されたパルスレーザ光３は、ポリゴンミラー１５を介して受光レンズ１６で集光され、光検出器１７で電気信号に変換される。
【００５０】
制御器２０内の時間間隔カウンタ２１は、レーザダイオード１３のパルス発振タイミングと同期したスタートパルス４と、光検出器１７から出力されたストップパルス５の時間間隔を計測する。信号処理ボード２２は、反射光が検出された時点の時間間隔ｔ、ポリゴンミラーの回転角度θ、揺動角度φを極座標データ（ｒ，θ，φ）として出力する。
ｒは計測位置（レーダヘッド設置位置）を原点とする距離であり、ｒ＝ｃ×ｔ／２  の式で求められる。ここでｃは光速である。
判定処理ユニット２３は、信号処理ボードからの極座標データを、レーダヘッド設置位置を原点とした三次元空間データ（ｘ，ｙ，ｚ）へ変換して、検出処理を行うようになっている。なおこの図で２４はドライブユニットである。
【００５１】
上述した三次元レーザレーダ１０の計測範囲は、例えば、水平画角６０°、垂直画角３０°、最大測定距離５０ｍである。また、位置検出精度は、例えば約２０ｃｍである。
また、計測データを各画素に対して奥行き方向の距離値を持った距離画像で表示する場合、１フレームの計測点数を、横方向１６６点、スキャン方向５０点とすると、１フレームに１６６×５０＝８３００点が表示される。この場合にフレームレートは、例えば約２フレーム／秒である。
【００５２】
この三次元レーザレーダ１０で計測される三次元形状上の被計測点は、横方向にΔθ×ｒ、垂直方向にΔφ×ｒ、互いに離散した点群となる。例えば、Δθ＝６０／１６６×π／１８０＝６．３×１０−３ラジアン、Δφ＝３０／５０×π／１８０＝１０．５×１０−３ラジアン、ｒ＝５０ｍの場合、最も近接する場合でも、被計測点の間隔は、横方向で約３１５ｍｍ、垂直方向で約５２５ｍｍとなる。
【００５３】
本発明では、距離センサとして、例えば、上述した三次元レーザレーダ１０を用いる。しかし、距離センサはこれに限定されず、視差を利用した距離センサ、その他の周知の距離センサを用いることができる。
【００５４】
図３，図４は、距離センサで計測された極座標データと誤差の関係を示す図である。
図３に示すように、任意の計測位置を原点とする極座標値（ｒ，θ，φ）を計測結果として計測する。距離センサによる計測結果には、図に示すような誤差分布が通常存在する。
この誤差分布は、誤差分布のｒｓ，θｓ，φｓでの存在確率をＰ（ｒｓ，θｓ，φｓ）とした場合、誤差分布は計測の軸ｒ，θ，φ方向に正規分布しているとし、例えば[数２]の式で表すことができる。ここで、ｒ，θ，φはセンサからの計測値、σｒ，σθ，σφは標準偏差、Ａは規格化定数である。
図４に示すように、誤差分布は、通常ｒ方向に長い切頭円錐形（左図）に内包される分布であるが、遠方においてａとｂの差は小さい。従って、この誤差分布を直方体に包含される楕円体として安全サイドに近似することができる。
【００５５】
【数２】
0005380792.tif 000002
【００５６】
図５は、物体認識処理部の構成の一例を示す。この図に示すように、物体認識処理部４２は、内部記憶装置３４、中央処理装置３５を備える。物体認識処理部４２は、データ入力装置３２および外部記憶装置３３からデータを受け取り、ロボット制御部４５へデータを送る。
【００５７】
データ入力装置３２は、上述した距離センサを有し、三次元形状上の座標値を物体認識処理部４２に入力する。また、例えばゴニオメータ、オドメータ等を併用して、距離センサの位置・姿勢や移動距離も入力するのがよい。なお、データ入力装置３２は、キーボード等の通常の入力手段も有するのがよい。
外部記憶装置３３は、ハードディスク、フロッピー（登録商標）ディスク、磁気テープ、コンパクトディスク等である。外部記憶装置３３は、環境モデルのサイズが大きく後述する内部記憶装置３４に入力された三次元形状上の座標値、ボクセル位置、及び代表点とその誤差分布の全体を保持できない場合には、環境モデルの一部範囲または全体範囲に対する、入力された三次元形状上の座標値、ボクセル位置、及び代表点とその誤差分布の一部または全体を記憶し、かつ本発明の方法を実行するためのプログラムを記憶する。また、外部記憶装置３３は、後述するＣＡＤモデルデータを記憶する。
内部記憶装置３４は、例えばＲＡＭ，ＲＯＭ等であり、環境モデルの一部範囲または全体範囲に対する、入力された三次元形状上の座標値、ボクセル位置、及び代表点とその誤差分布の一部または全体を保管し、かつ演算情報を保管する。
中央処理装置３５（ＣＰＵ）は、モデル構築装置、マッチング装置、粗合わせと精密合わせの位置合わせ装置、モデル更新装置として機能し、演算や入出力等を集中的に処理し、内部記憶装置３４と共に、プログラムを実行する。モデル構築装置は、後述のモデル構築ステップを行う装置であり、マッチング装置は、後述の環境モデルと点群とのマッチングステップおよび計測データとＣＡＤモデルデータとのマッチングステップを行う装置であり、位置合わせ装置は、後述の粗合わステップと精密合わせステップを行う装置であり、モデル更新装置は、後述のモデル更新ステップを行う装置である。
ロボット制御部４５は、物体認識処理部４２から受け取る被計測物の位置や姿勢に基づいてロボットのアームやハンドの動きを制御する。
【００５８】
上述した本発明の装置は、上述した距離センサと通常のＰＣ（コンピュータ）を組み合わせたものでもよく、或いは、全体を一体にした装置であってもよい。また、自走可能な装置内に一体的に組み込んでもよい。
【００５９】
図６は、本発明の方法を示すフローチャートである。図６に示すように、データ入力ステップＳ１、データ補正ステップＳ２、探索範囲限定ステップＳ３、モデル構築ステップＳ４、環境モデルと点群とのマッチングステップＳ５、自己位置同定ステップＳ７、Ｓ１０、粗合わせステップＳ８、精密合わせステップＳ９、モデル更新ステップＳ１１及び計測データとワークのモデルデータとのマッチングステップＳ１２を有する。
なお、Ｓ４は初めて計測データが得られたときにだけ実施し、それ以外のＳ１〜Ｓ３及びＳ５〜Ｓ１２は、計測データが得られる毎に実施する。
【００６０】
データ入力ステップＳ１では、新たな計測位置から距離センサを用いて計測した三次元形状上の座標値をコンピュータの記憶装置に入力する。また、例えばゴニオメータ、オドメータ等を併用して、距離センサの位置・姿勢や移動距離も入力するのがよい。
なお、このデータ入力ステップＳ１において、三次元レーザレーダ１０を用いて、三次元形状上の座標値を、任意の計測位置を原点とする距離データとして、原点を移動しながら順次取得するのがよい。
【００６１】
距離センサとして三次元レーザレーダ１０を用いた場合、三次元形状上の座標値は、任意の計測位置を原点とする距離データであり、極座標値（ｒ，θ，φ）で表される。また、各座標値の誤差分布は、極座標値（ｒ，θ，φ）から演算で求めるか、予め別の入力手段（例えばキーボード）で入力する。
【００６２】
データ補正ステップＳ２では、距離データの補正処理を行い、距離データの精度を向上させる。また、極座標データとオドメータのデータから、任意の固定位置を原点とした三次元空間データ（ｘ，ｙ，ｚ）へ変換してもよい。
距離データの補正処理では、孤立点の除去、統計的処理、等を行う。孤立点は、周囲の点から孤立して存在する点であり、計測データは複数の近接する点で構成されることから、孤立点は誤計測と仮定して除去することができる。統計的処理は、計測データが含む誤差分布を考慮して、複数回の計測を統計処理（例えば平均値等）することで、距離の補正を行う。
さらに、対象とする三次元形状が、直線近似又は平面近似できる場合にはこれらを行うのがよい。
【００６３】
探索範囲限定ステップＳ３では、距離センサの探索範囲を限定する。
探索範囲を限定せずに環境モデルに対する計測データのマッチング処理を行うと、複数の解（被計測点）が得られる可能性がある。そこで、（１）現在のセンサ位置を、過去のセンサ位置とその過去のセンサ位置からの変化量から推定し、センサ位置推定結果の近傍を探索する、（２）オドメータを用いてセンサ位置を推定し、探索範囲を限定する、（３）距離データのうち、距離値だけでなく、反射強度値も利用して探索結果を絞り込む、等を実施する。
【００６４】
図７は、ボクセルの分割に八分木を用いた場合のモデル構築ステップの模式図である。
モデル構築ステップＳ４では、この図に示すように、三次元形状の存在する空間領域を、境界表面が互いに直交する直方体からなる複数のボクセル６に分割し、各ボクセル位置を記憶する環境モデルを構築する。
ボクセル６の形状は、各辺の長さが等しい立方体でも、各辺の長さが異なる直方体でもよい。
また、ボクセル６の各辺の長さは、最大のボクセル６を必要最小限の分解能に相当する大きさに設定するのがよい。以下、最大のボクセル６をレベル１のボクセルと呼ぶ。
また、単一のボクセル内に複数の被計測点が存在する場合には、単一のボクセル内に単一の被計測点のみが存在するように、例えば八分木を選んだ場合は、ボクセルを更に八分割して階層的に複数のボクセルに分割する。以下、最大のボクセル６の八分割を１回実施した空間領域をレベル２のボクセル、ｋ回実施した空間領域をレベルｋ＋１のボクセルと呼ぶ。
【００６５】
図８は、構築された環境モデルの模式図である。
マッチングステップＳ５では、この図に示すように、三次元形状上の座標値に対応するボクセル６の内部に代表点７とその誤差分布８を設定し記憶する。末端のボクセルは計測値の代表点を１つだけ持つことができる。各ボクセルが計測値の代表点とその誤差分布を持つことで、物体の形状を表す。また、物体の存在確率を表す確率値をボクセルに持たせることもできる。
【００６６】
マッチングステップＳ５において、代表点の絶対位置は次の［数３］の式で与えられる。ここで、（ｘ，ｙ，ｚ）は代表点のボクセルでの相対座標、Ｓｘ，Ｓｙ，Ｓｚはレベル１でのボクセルの一辺の大きさ、ｎｘ（ｋ），ｎｙ（ｋ），ｎｚ（ｋ）はレベルｋでのボクセルの番地、Ｌは求める代表点が存在するレベルである。
【００６７】
【数３】
0005380792.tif 000003
【００６８】
図９，図１０は、本発明におけるボクセルデータのデータ構造を示す図である。
この図において、図９は、各ボクセルデータのメモリレイアウト例である。この図において、矢印はデータへのリンクを表し、値としてはデータへのポインタを保持する。
図１０は、レベル２（１，１，０）のボクセルが代表点を持つ場合の例を示している。なおこの図において、ｎｕｌｌは空集合を表す。
【００６９】
上述したデータ構造の環境モデルは、以下の特徴を有する。
（１）内容：空間を複数の小直方体（ボクセル）で分割して各ボクセルに計測点の代表点と誤差分布を保持する。
（２）精度：ボクセル毎に持つ計測点の代表値相当である。
（３）存在：物体の存在の有無を表現できる。
（４）データ量：ボクセルの個数に比例してメモリを必要とするが、サイズ固定である。
（５）点群からの変換：適しており、計算量は少ない。
（６）アクセス速度：シンプルな構造をしているため、要素へのアクセスが高速である。
【００７０】
またこの特徴から、上述した環境モデルは、以下の効果Ａ〜Ｃをすべて満たしている。
効果Ａ：誤差を考慮した表現が可能である。
効果Ｂ：必要なメモリ量と計算量が一定量以下である。
効果Ｃ：物体の存在だけでなく、物体が存在しないことを表せる。
【００７１】
図６のステップＳ６で、先の計測位置から計測した同一の三次元形状に関するデータの有無をチェックする。このチェックで、先の計測位置から計測した同一の三次元形状に関するデータが存在しない場合には、新たな計測位置を自己位置（センサ位置）と同定する。
この同定は、逐次移動する移動体の初期位置において、既知の６自由度位置（例えばグローバル座標系の原点）で実施することが好ましい。また、この同定において、新たな計測位置の位置（３自由度）と姿勢（３自由度）を含む６自由度位置を同定することが好ましい。
【００７２】
また、ステップＳ６のチェックで、先の計測位置から計測した同一の三次元形状に関するデータが存在する場合には、粗合わせステップＳ８と精密合わせステップＳ９を、マッチングステップＳ５の後に実施する。
図１１は、粗合わせステップＳ８と精密合わせステップＳ９のデータ処理フロー図であり、図１２は粗合わせステップＳ８の模式図、図１３は精密合わせステップＳ９の模式図である。
【００７３】
図１１の粗合わせステップＳ８では、図１２に示すように、先の計測位置に対する環境モデルに対し、
（１−１）新たな計測データおよび誤差分布を回転及び並進させ、計測データおよび誤差分布と近接する代表点を有するボクセルとの距離に関する評価値（例えば、当該距離の総和）が最小になるように、もしくは
（１−２）新たな計測位置に対する環境モデル（新たな計測データから作成したボクセル）を回転及び並進させ、近接する代表点を有するボクセル間の距離に関する評価値（例えば、当該距離の総和）が最小になるように、もしくは、
（２−１）新たな計測データおよび誤差分布を回転及び並進させ、計測データおよび誤差分布と近接する代表点を有するボクセルの確率値に関する評価値（例えば、当該確率値の総和）が最大になるように、もしくは
（２−２）新たな計測位置に対する環境モデル（新たな計測データから作成したボクセルであって各ボクセルは確率値を有する）を回転及び並進させ、近接するボクセルが持つ確率値の差に関する評価値（例えば、当該確率値の差の総和）が最小になるように、位置合わせする。
【００７４】
粗合わせステップＳ８における位置合わせは、環境モデルと計測データをボクセル空間上で表現すること、もしくは環境モデルはボクセル空間上で、計測データは代表点と誤差分布表現することで実施する。現在の計測データが位置（ｘ，ｙ，ｚ）、姿勢（θ，φ，ψ）での計測であったとして、計測データをワールド座標に変換して環境モデルとの一致度を算出する。
一致度の算出には、例えば最短距離法を用いることができる。最短距離法を用いた場合のボクセル間の距離は、２つのボクセル空間をｘ（１）、ｘ（２）、ボクセルの総数をＩ、ボクセルの値をｘｉ（ｎ）とすると、［数４］の式で定義できる。
計測データの最適な位置・姿勢は、位置（ｘ，ｙ，ｚ）、姿勢（θ，φ，ψ）を変化させることによってεを最小にする最小自乗法によって算出できる。
【００７５】
また、一致度として、例えば環境モデルと計測データの両ボクセルにおいて、近接する両ボクセルの持つ確率値の差に関する評価値（例えば、当該確率値の差の総和）を用いることができる。この場合は一致度を最小にするように、計測データの最適な位置・姿勢を変化させる。
また、環境モデルはボクセル空間上で、計測データは代表値と誤差分布表現した場合には、計測データの代表値、および誤差分布が近接する環境モデルのボクセルの確率値に関する評価値（例えば、当該確率値の総和）を用いることができる。この場合は一致度を最大にするように、計測データの最適な位置・姿勢を変化させる。
【００７６】
【数４】
0005380792.tif 000004
【００７７】
図１１の精密合わせステップＳ９では、図１３に示すように、先の計測位置に対する環境モデルに対し、
（１）新たな計測データおよび誤差分布を回転及び並進させ、もしくは
（２）新たな計測位置に対する環境モデルを回転及び並進させ、
近接する誤差分布間の距離に関する評価値（例えば、当該距離の総和）が最小になるように位置合わせする。
精密合わせステップＳ９における環境モデルと計測データの精密合わせ位置合わせには、点群と点群の位置合わせが可能なＩＣＰアルゴリズムに誤差分布を考慮した手法を利用する。位置合わせの初期値には、粗い位置合わせにより得られた位置・姿勢を利用する。
ＩＣＰアルゴリズムに利用する誤差分布間の距離の算出には、例えば誤差分布が交差する場合を同一計測点と考え、その場合の距離値に分布の一致度から求めた重みを掛け合わせて算出する。分布の一致には例えばマハラノビス距離のような距離尺度を利用できる。
この場合の環境モデルと計測データの距離は、環境モデルデータをｐＭｉ、環境モデルデータの誤差分布をΣＭｉ、計測データをＰＤｉ、計測データの誤差分布をΣＤｉ、誤差分布の合成関数をｗ、計測データに対応する環境モデルデータの個数をＮとすると、［数５］の式で定義できる。ここで、Ｔは転置を表す。誤差分布の合成関数ｗは、分布の一致度から求めた重みである。
計測データの最適な位置・姿勢は、計測データを計測した位置（ｘ，ｙ，ｚ）  、姿勢（θ，φ，ψ）を変化させてＰＤｉを移動することによりεを最小にする最小自乗法によって算出できる。
また、自己位置・姿勢の同定とともに、自己位置の誤差分布を同定し、現在の自己位置と誤差分布および同定した自己位置と誤差分布とからカルマンフィルタによって、自己位置と誤差分布を補正する。
【００７８】
【数５】
0005380792.tif 000005
【００７９】
さらに図６のモデル更新ステップＳ１１は、自己位置同定ステップＳ１０の後に実施し、モデル構築ステップＳ４で構築した環境モデルを更新する。
【００８０】
図１４は、モデル更新ステップＳ１１におけるデータ処理フロー図である。この図に示すように、ステップＳ２１で新たに入力された被計測点の座標値に対応するボクセルを探索し、ステップＳ２２で該当するボクセル内に代表点がない（ボクセルが空である）場合には、ステップＳ２３で新たに入力された被計測点の座標値と誤差分布を代表点の座標値と誤差分布として設定（新規に登録）する。
また、このステップＳ２３において、新しい計測位置（原点）と被計測点の間には、原理的に物体が存在しないはずである。従って新しい計測位置（原点）と被計測点の間に位置するボクセル内の代表点と誤差分布を再設定、もしくは消去する。
【００８１】
図１５は、該当するボクセル内に既に設定した代表点がある場合の模式図である。
図１４のステップＳ２２で該当するボクセル内に既に設定した代表点がある場合には、ステップＳ２４で新たに取得した誤差分布と既に設定したボクセル内の誤差分布とを比較する（すなわち異なる点か同一点かを判断する）。
この比較で、誤差分布が互いに重複する場合（図１５の（Ａ））には、ステップＳ２５で両誤差分布から、または、両誤差分布とボクセル内に既に設定した代表点と新たに入力された被計測点の座標値から、新たな誤差分布と新たな代表点を再設定する（すなわち誤差分布を合成する）。
またこの比較で、誤差分布が互いに重複しない場合（図１５の（Ｂ））には、ステップＳ２６、Ｓ２７で単一のボクセル内に単一の代表点のみが存在するように、該ボクセルを更に八分割して階層的に複数のボクセルに分割し新規に登録する。
分割と合成の基準は、例えば誤差分布の一致度から判断する。誤差分布の一致度には例えば、マハラノビス距離のような距離尺度を利用できる。また、２つの誤差分布に基づき、両者が同一点を表しているかを統計的検定によって判定してもよい。
【００８２】
ステップＳ２５で両誤差分布から新たな誤差分布と新たな誤差分布の中心を再設定した結果、新たな代表点が他のボクセル内へ移動したとき（即ち、ステップＳ２８で、Ｙｅｓ）、ステップＳ２２へ戻り、上述の処理を繰り返す。
なお、図１６は、ステップＳ２５で両誤差分布から、または、両誤差分布とボクセル内に既に設定した代表点と新たに入力された被計測点の座標値から、新たな誤差分布と新たな誤差分布の中心を再設定した結果、新たな代表点が他のボクセル内へ移動する場合を示している。
【００８３】
ボクセル内に物体の存在確率を表す確率値を設定する場合には、モデル更新ステップＳ１１において、ボクセル内の代表点と誤差分布の新規登録、もしくは再設定、もしくは消去、もしくは分割後に新規登録の処理に応じて、ボクセル内の確率値も統計処理によって、新規登録、もしくは再設定、もしくは消去、もしくは分割後に新規登録を行う。
【００８４】
図１７は、誤差分布が互いに重複する場合（図１５の（Ａ））の別の模式図である。ステップＳ２５において、２つの代表点と誤差分布を合成して新たな代表点を誤差分布を設定する手段として、カルマンフィルタを用いることができる。例えば、二次元の場合に、この図に示すように、２つの代表点をそれぞれｘ（１），ｘ’（２）、２つの誤差分布をΣ（１）、Σ’（２）とし、これを合成した代表点をｘ（２）、誤差分布をΣ（２）とすると、代表点ｘ（２）と誤差分布Σ（２）を算出する模式図は図１７のようになる。
【００８５】
図６のマッチングステップＳ１２では、計測データは、平均値m(i)、誤差共分散行列Sm(i)の正規分布に従うものとする。
図２２は、計測データとＣＡＤモデルとのマッチングを説明するための二次元模式図である。この図に示すように、被計測物（例えば、ワーク）のＣＡＤモデルは、例えば三角形パッチで表現し、その頂点をw(j)で表す。ＣＡＤモデルの位置をt、姿勢をR、とするとき、三角形パッチの頂点の座標はR・w(j)+tとなる。なお、tは３要素の並進ベクトル、Ｒは３×３の行列とする。
【００８６】
図２３は、計測データとＣＡＤモデルとの対応を説明するための図である。三角形パッチｗ（ｊ）の添え字ｊは、ｍ（ｉ）に対して全ての三角形パッチの頂点のうち最近傍となるものを選択した結果とする。
図２４は、計測データとＣＡＤモデルとの一致度を説明するための図である。計測データとＣＡＤモデルの一致度E（R,t）は、マハラノビス距離を用いて図２５に示す式によって定義できる。計測データから算出される被計測物の位置と姿勢は、E（R,t）を最小とするR,tにより与えられる。
【００８７】
算出された被計測物の位置ｔと姿勢Ｒに関するデータは、ロボット制御部４５などに出力される。ロボット制御部４５などに出力された被計測物の位置ｔと姿勢Ｒに関するデータは、ロボット４６が被計測物をつかむために使用される。
また、被計測物の位置ｔと姿勢Ｒが算出できると、計測データの各誤差分布とＣＡＤモデルデータとが一致しない部分の位置やそのずれ量が算出できる。ずれ量が大きい場合、被計測物の表面に欠損部があることなどが分かる。つまり、被計測物の表面形状の検査が可能となる。
【００８８】
モデル更新ステップＳ１１において、新たに入力された被計測点の座標値に対応するボクセルを探索し、前記ボクセル内の代表点および誤差分布の少なくともいずれかが新たに設定される、または再設定される、または該ボクセルを更に分割して階層的に複数のボクセルに分割される場合、マッチングステップＳ１２において、当該ボクセルの代表点の位置を三次元形状の計測値としても良い。
【００８９】
マッチングステップＳ１２において、距離センサの位置・姿勢が得られる場合は、その位置から見える範囲の環境モデル内のボクセルの代表点の位置を三次元形状の計測値としてもよい。距離センサの位置から見える範囲とは、距離センサの位置から距離センサが位置計測可能な範囲であり、距離センサの位置から距離センサが位置計測可能な角度範囲（視野）と、距離センサの位置から距離センサが位置計測可能な距離範囲とを含む。
【００９０】
図６に示した処理の手順は、新たな計測位置において、新しい計測データが得られる度に、処理を繰り返し行い、内部記憶装置３４および外部記憶装置３３の少なくともいずれかに結果を格納する。処理を高速化するためには、内部記憶装置３４に容量が許す限り結果を格納することが好ましい。
【００９１】
上述した本発明の方法と装置によれば、三次元形状の存在する空間領域を、複数のボクセル６に分割し、各ボクセル位置を記憶するので、計測対象物が大きい場合であっても、データ量をボクセル数に比例する小さいデータサイズに抑えることができる。
また、座標値に対応するボクセル６の内部に代表点７とその誤差分布８を設定し記憶するので、ボクセルの分解能以上の情報を表現することができる。
【００９２】
また、ボクセルの内部に物体の存在確率を表す確率値を設定し、保存することによって、誤差分布が代表点の属するボクセルよりも広がっている場合においても、各ボクセルにおける物体の存在有無を代表点が属するボクセルを見つけ、その誤差分布から再計算させることなく、当該ボクセルの確率値だけで容易に判断できるので、検索時間を抑えることができる。
また、現在の計測位置を、
（１）「過去の計測位置」と「過去の計測位置からの予定されている変化量」に基づいて推定し、
（２）現在の計測位置を取得可能なセンサにより取得し、または
（３）計測データの距離値だけでなく反射強度を利用し、照合する範囲を制限するので、検索時間を抑えることができる。
【００９３】
また、粗合わせステップＳ８において、先の計測位置に対する環境モデルに対し、
（１−１）新たな計測データおよび誤差分布を回転及び並進させ、計測データおよび誤差分布と近接する代表点を有するボクセル間との距離に関する評価値（例えば、当該距離の総和）が最小になるように、もしくは
（１−２）新たな計測位置に対する環境モデル（新たな計測データから作成したボクセル）を回転及び並進させ、近接する代表点を有するボクセル間の距離に関する評価値（例えば、当該距離の総和）が最小になるように、もしくは
（２−１）新たな計測データおよび誤差分布を回転及び並進させ、計測データおよび誤差分布と近接する代表点を有するボクセルの確率値に関する評価値（例えば、当該確率値の総和）が最大になるように、もしくは
（２−２）新たな計測位置に対する環境モデル（新たな計測データから作成したボクセルであって各ボクセルは確率値を有する）を回転及び並進させ、近接するボクセルが持つ確率値の差に関する評価値（例えば、当該確率値の差の総和）が最小になるように、位置合わせするので、誤差の蓄積を防ぎながら、短時間に代表点を有するボクセル同士の位置合わせができる。
【００９４】
また、先の計測位置に対する環境モデルに対し、新たな計測位置に対する環境モデルを回転及び並進させ、近接するボクセルが持つ確率値の差に関する評価値（例えば、当該確率値の差の総和）が最小になるように、位置合わせする場合には、物体が存在しない情報も加味して位置合わせするので、精度の向上が図れる。
【００９５】
次いで、精密合わせステップＳ７において、先の計測位置に対する環境モデルに対し、新たな計測データおよび誤差分布を回転及び並進させ、もしくは新たな計測位置に対する環境モデルを回転及び並進させ、近接する誤差分布間の距離に関する評価値（例えば、当該距離の総和）が最小になるように位置合わせするので、誤差分布同士の精密な位置合わせを短時間にできる。
従って、本発明による複数視点からのデータの統合処理により、誤差の蓄積を防ぎながら、高精度な形状取得を可能にできる。
【００９６】
また、本発明では、ボクセル構造を拡張した構造をしているため、データサイズは点群に比べて小さく済ませることができる。従って、周囲環境と計測データの位置合わせ（ＩＣＰアルゴリズム）を行う際に探索対象となるデータ量が減少することから、計算を効率化できる。
【００９７】
さらに、従来のＩＣＰアルゴリズムは疎データに対して誤った結果を出力するが、本発明の環境モデルは、ボクセル内に代表点と誤差分布を持っているため、疎データに対応した位置合わせが可能である。
【００９８】
また、モデル構築ステップＳ４において、最大のボクセル６を必要最小限の分解能に相当する大きさに設定し、かつ単一のボクセル６内に複数の被計測点が存在する場合に、単一のボクセル内に単一の被計測点のみが存在するように、該ボクセルを更に八分割して階層的に複数のボクセルに分割するので、データ量を小さいデータサイズに抑えると同時に、分割後のボクセルと代表点を用いて解像度を更に高めることができる。
【００９９】
特に、三次元形状上の同じ位置に関する複数の座標値を、複数の計測位置を原点とする距離データとして取得し、該距離データの座標値を、前記代表点の座標値とし、距離データの座標値の計測誤差を代表点の誤差分布とすることにより、正確な座標値と誤差分布を用いて複数回の計測を統計的に統合することができ、一層の精度向上が可能となる。
【０１００】
図１８は、複数の計測位置を原点とする距離データを統合することによって、代表点の誤差分布が縮小し、代表点の精度が向上する様子を示している。このように異なる計測位置（即ち、距離センサである三次元計測器の位置）を原点として得られた距離データは誤差分布の向きも異なるので、これらの距離データを環境モデルを介して逐次統合することによって、代表点の誤差分布が縮小し、代表点の位置精度が向上する。なお、図１８において、三次元計測後の図はコップの２次元断面を表わした模式図であり、三次元計測後の図の破線はコップの実際表面を表わしている。
【０１０１】
また、自己位置の同定とともに、自己位置の誤差分布を同定し、現在の自己位置と誤差分布および同定した自己位置と誤差分布とからカルマンフィルタによって、自己位置と誤差分布を補正することによって、一層の精度向上が可能となる。
【０１０２】
また、原点と被計測点の間に物体が存在しないものとして、その間に位置するボクセル内の代表点と誤差分布を再設定、もしくは消去することにより、誤った計測データの影響を除去することができる。
【０１０３】
また、新たに入力された被計測点の座標値に対応するボクセルを探索し、該ボクセル内に代表点がない場合に、前記座標値と誤差分布を代表点の座標値と誤差分布として設定することにより、代表点の座標値と誤差分布を容易に設定できる。
【０１０４】
更に、前記ボクセル内に既に設定した代表点がある場合に、新たに取得した誤差分布と既に設定したボクセル内の誤差分布とを比較し、
誤差分布が互いに重複する場合に、両誤差分布から、または、両誤差分布とボクセル内に既に設定した代表点と新たに入力された被計測点の座標値から、新たな誤差分布と新たな代表点を再設定し、
誤差分布が互いに重複しない場合に、単一のボクセル内に単一の代表点のみが存在するように、該ボクセルを更に八分割して階層的に複数のボクセルに分割する、ことにより、誤差の蓄積を回避しながら高精度な形状に収束させることができる。
【０１０５】
従って、本発明の方法と装置によれば、誤差を含むデータを正確な情報に補正する機能を有すると共に、複数回の計測に対して高精度に収束する。なおかつ、位置同定処理は、ボクセルの各ボクセルに対応する代表点とその誤差分布を計測点で更新する処理であるため計算量が小さく、演算は周囲ボクセルへの影響を与えずボクセル内で閉じている。よって、高速な処理が可能である。また、計測データはボクセルに逐次統合可能であり、その結果得られた周囲環境情報のメモリサイズは固定サイズを上回ることはない。具体的には、レベル１のボクセル個数をＮ、分割最大レベルをＬｍａｘとするとき、メモリサイズは、各ボクセルに必要とするメモリサイズに、高々、図２６に示す式を乗じた値となるため、これは固定サイズを上回ることはない。
【０１０６】
カルマンフィルタを用いたモデル更新ステップについて、詳しく説明する。
【０１０７】
カルマンフィルタを用いたモデル更新ステップの場合には、新たに入力された被計測点の座標値およびその誤差分布と、既に設定したボクセル内の代表点およびその誤差分布とから、カルマンフィルタにより新たな代表点と誤差分布を取得して再設定する。
【０１０８】
各モデル点群の位置m（ｉ）を状態量とし、距離センサの計測点の位置を基に、モデルを次の［数６］で表現する。なお、本実施例では、m（ｉ）は、ボクセル内部の代表点である（以下、同様）。
【０１０９】
【数６】
0005380792.tif 000006
【０１１０】
［数６］において、
Ｌ（ｊ）は、距離センサによる計測位置である。例えば、Ｌ（ｊ）は、距離センサのセンサ座標系において三次元ＬＲＦ（レーザレンジファインダ）の計測点ｊ（ｊ＝１，．．．，Ｎ）の位置Ｌ（ｊ）＝（ｘＬ（ｊ），ｙＬ（ｊ），ｚＬ（ｊ））ｔである。ここで、ｔは転置行列を示す（以下、同様）。
ｈｍ（Ｒｒ，ｔｒ，ｍ（ｉ））は、Ｌ（ｊ）に対する観測系モデルである。
Ｒｒは、距離センサを搭載した移動体（例えば移動ロボット）のワールド座標系に対する姿勢を表す回転行列Ｒｒ＝Ｒ（θｘ，θｙ，θｚ）である。なお、θｘ，θｙ，θｚは、それぞれｘ軸、ｙ軸、ｚ軸周りの回転角を示す（以下、同様）。
ｔｒは、上記移動体のワールド座標系に対する位置を表す並進ベクトルｔｒ＝（ｘ，ｙ，ｚ）である。
ｖＬ（ｉ）は、距離センサの計測値Ｌ（ｊ）に加わる観測ノイズである。
Ｒｓは、センサ座標系の移動体座標系に対する回転行列Ｒｓ＝Ｒ（θｘ，θｙ，θｚ）である。
ｔｓは、センサ座標系の移動体座標系に対する位置を表す併進ベクトルｔｓ＝（ｘ，ｙ，ｚ）である。
【０１１１】
距離センサによる計測点群と、環境モデル点群上の点ｉ（即ち、代表点）を対応づける。この対応付けが行われたモデル点群上の点iに対して[数７]の式により更新を行う。なお、距離センサによる計測点群と対応付けが行われたモデル点群上の代表点ｍ（i）に対してのみ次の［数７］の式により更新を行ってよい。
【０１１２】
【数７】
0005380792.tif 000007
【０１１３】
［数７］の式において、
添え字ｋは、離散時刻ｋでの値であることを表す。
ｍｋ（ｉ）について、ｍ’ｋ（ｉ）はｍｋ（ｉ）の更新値（事後推定値）を示し、ｍｋ，ｋ−１（ｉ）はｍ’ｋ−１（ｉ）に基づいたｍｋ（ｉ）の予測値（事前推定値）を示す。なお、環境（測定対象物）は静止しているので、ｍｋ，ｋ-１（ｉ）＝ｍ’ｋ-１（ｉ）である。
Σmk（ｉ）は、ボクセル内部の代表点ｍｋ（ｉ）の誤差共分散行列(即ち、上述の誤差分布)である。また、Σｍｋ（ｉ）について、  Σ’ｍｋ（ｉ）はΣｍｋ（ｉ）の更新値（事後推定値）を示し、Σｍｋ，ｋ−１（ｉ）はΣ’ｍｋ−１（ｉ）に基づいたΣｍｋ（ｉ）の予測値（事前推定値）を示す。センサ座標系において三次元LRFの計測点j（j=１,…,Ｎ）の位置をＬ（ｊ）で表し、その誤差共分散行列をΣＬ（ｊ）で表す。ここでＮは、三次元LRFで得られた計測点の総数である。三次元LRFの誤差モデルとして計測距離に関係ない一定の正規分布を仮定する。センサ座標系のｘ軸方向にレーザを照射する場合の誤差共分散行列をΣＳとする。レーザの照射方向に応じて誤差分布も姿勢を変える。ΣＬ（ｊ）は、基準の方向に対するレーザ照射方向を回転行列ＲＬ（ｊ）を用いてΣＬ（ｊ）＝ＲＬ（ｊ）ΣＳＲＬｔ（ｊ）と表される。計測点jのワールド座標系における位置ｚ（ｊ）、およびその誤差共分散行列Σｚ（ｊ）は、それぞれｚ（ｊ）＝Ｒｒ（ＲｓＬ（ｊ）＋ｔｓ）＋ｔｒ、Σｚ（ｊ）＝ＲｒＲｓΣＬ（ｊ）ＲｓｔＲｒｔと表すことができる。
Ｋｍｋ（ｉ） は、 ｍｋ（ｉ）に対するカルマンゲインである。
ｈｍｋ（Ｒｒｋ，ｔｒｋ，ｍｋ，ｋ−１（ｉ））は、Ｌｋ（ｊ）、ｉ＝ｐｋ（ｊ）に対する観測系モデルである。ｉ＝ｐｋ（ｊ）は、計測点ｊに対応付けられた環境地図（即ち、環境モデル）上の点である。
Ｈｍｋは、Ｌｋ（ｊ）、ｉ＝ｐｋ（ｊ）に対する観測系モデルのヤコビアン行列であり、次の［数８］の式で表わされる。
【０１１４】
【数８】
0005380792.tif 000008
【０１１５】
カルマンフィルタの更新過程によって、環境地図のモデル点群の各点（ボクセルの代表点）の位置と誤差共分散行列の更新値ｍ’ｋ（ｉ）、Σ’mk（ｉ）が得られた段階で、環境モデルの更新を以下の手順で行う。
（１）これら更新値ｍ’ｋ（ｉ）、Σ’mk（ｉ）を、新たな代表点、誤差分布として再設定する。
（２）上述（１）の結果、代表点の位置が別のボクセル内に移動した場合、移動先のボクセルが代表点を保持していないときは、移動後の代表点とその誤差共分散行列を移動先のボクセルに保持させ、移動元のボクセルからは代表点等を取り除く。移動先のボクセルが既に代表点を保持しているときには、2つの代表点において、これらの両誤差分布が重複するかを判断する（上述のＳ２４における判断と同様）。その後の処理は、図１４のＳ２４以降の処理と同じであってよい。
（３）モデル点群上の代表点ｍ（i）と対応付けが行われなかった距離センサによる計測点について、当該計測点が含まれるボクセルが代表点を持たない場合は、計測点とその誤差分布をそのボクセルの代表点と誤差分布として追加し保持する。もし、ボクセル内に既に代表点が存在する場合には、ボクセル内にある対応付けが行われなかった他の複数の計測点を含め、既存の代表点と各計測点とが全て異なるボクセルに含まれるように、ボクセルを分割した上で分割後のボクセルに代表点等を継承させる。
【０１１６】
上述のカルマンフィルタを用いたモデル更新ステップを繰り返すことで、序々にボクセル内の誤差共分散行列（即ち、誤差分布）の範囲が小さくなるとともに、ボクセルが分割され易くなる。ボクセルが分割されることによって、初期ボクセルのサイズ以下の変化も表現することが可能となる。
図１９は、カルマンフィルタを用いたモデル更新ステップにより得られた結果を示す。図２０は図１９の一部拡大図である。これら図において、初期のボクセルの1辺の長さを100cmとし、再分割数を6分割まで許している。対象が存在している領域では、ボクセルの再分割を繰り返した結果、計測対象を精度良く表現している。対象が存在しない領域ではボクセルの再分割は行われず、必要十分なデータ量で環境を表現できることがわかる。また、各ボクセル内の代表点の誤差分布も小さく、環境地図を高精度で表現できている。このように、誤差を含むデータであってもカルマンフィルタの効果により、真値に収束した結果が得られる。さらに、この方法では計測データ数を増加させることによって標準偏差が小さくなり、精度のさらなる向上が期待できる。
【０１１７】
また、測定対象物の位置・姿勢は固定しているため、更新を測定対象物の位置・姿勢と独立して行うことができる。なお、距離センサによる計測点群と対応付けが行われたモデル点群上の代表点ｍ（i）に対してのみ、上述のカルマンフィルタによる更新を行うことで、大幅な計算コストの削減が可能になる。
【０１１８】
前記精密合わせステップにおいて、前記近接する誤差分布間の距離の総和が最小になるように位置合わせする代わりに、前記近接する誤差分布間に基づく最尤推定値によって定めた一致度に関する評価値（例えば、当該一致度の総乗）が最大となるように、先の計測位置に対する環境モデルに対し、新たな計測データおよび誤差分布を回転及び並進させ、もしくは新たな計測位置に対する環境モデルを回転及び並進させて位置合わせしてもよい。
この場合について詳しく説明する。
【０１１９】
環境地図（環境モデル）であるモデル点群、およびセンサの計測点群双方に誤差モデルを考慮しているため、前記一致度に関する評価値（例えば、当該一致度の総乗）の算出式（以下、評価関数と言う）にも双方の誤差を取り入れることが可能である。本実施例の場合、単に最も近い点を対応付けするのではなく、尤度の概念を取り入れることによって、評価関数に環境地図上の誤差分布、および計測点の誤差分布を加味し、現時点での環境地図において、各計測点の出現確率が最大となる場合に評価関数も最大となるように定める。
具体的には、計測点jに対応付けられた環境地図上の点ｉ＝ｐ（ｊ）の位置が、平均値（代表点）ｍ（ｉ）、誤差共分散行列Σｍ（ｉ）の正規分布に従うと仮定した上で、三次元LRFで計測した結果、Ｌ（ｊ）なる計測データが得られる確率値Ｐｒ（Ｌ（ｊ）｜ｍ（ｉ），Σｍ（ｉ））を点iと点jとの評価関数ＥＭ（ｉ，ｊ）とし、その総乗が最大となるように次の［数９］の式で評価関数を定める。[数９]の式によって誤差分布間に基づく最尤推定値によって定めた一致度を算出することができる。
【０１２０】
【数９】
0005380792.tif 000009
【０１２１】
ただし、ω（ｊ）は、モデル点群の中に計測点ｊと対応付けられる点が存在する場合は１、それ以外の場合は０とする。
ここで、Ｐｒ（Ｌ（ｊ）｜ｑ）を環境地図の点がｑの位置にある場合にＬ（ｊ）なる計測データが得られる確率値を表すものとし、Ｐｒ（ｑ｜ｍ（ｉ），Σｍ（ｉ））を平均値ｍ（ｉ）、誤差共分散行列Σｍ（ｉ）の正規分布に従うと仮定した上で環境地図の点がｑの位置にある確率値を表すものとすると、［数１０］の式が成り立つ。
【０１２２】
【数１０】
0005380792.tif 000010
【０１２３】
Ｐｒ（ｑ｜ｍ（ｉ），Σｍ（ｉ））は正規分布を仮定すると、次の［数１１］の式となる。
【０１２４】
【数１１】
0005380792.tif 000011
【０１２５】
一方、Ｐｒ（Ｌ（ｊ）｜ｑ）は、Ｌ（ｊ）をｚ（ｊ）で置き換えて、次の［数１２］の式で近似することができる。
【数１２】
0005380792.tif 000012
【０１２６】
ここで、ｚｋ（ｊ）は、距離センサを搭載した移動体、例えば移動ロボットの位置ｔｒ、姿勢Ｒｒに依存している。実際は、三次元LRFのセンサ座標系の中心から見たｑの向きと計測点Ｌ（ｊ）の向きとは図２１に示すように異なるため、誤差共分散行列Σｚ（ｊ）もｑの向きに合わせて回転変換する必要があるが、対応付けられた環境地図上の点iから大きく離れたところにあるｑの存在確率は低いため、十分な精度で近似できると考えられる。よって、Ｐｒ（Ｌ（ｊ）｜ｍ（ｉ），Σｍ（ｉ））は、次の［数１３］の式で表すことができる。
【０１２７】
【数１３】
0005380792.tif 000013
【０１２８】
簡単な計算によって、次の［数１４］の式を得る。
【０１２９】
【数１４】
0005380792.tif 000014
【０１３０】
ただし、α（ｊ），β（ｊ）は次の［数１５］の式で表すことができる。
【０１３１】
【数１５】
0005380792.tif 000015
【０１３２】
従って、モデル点群の点iと計測点群の点jとの対応付けの一致度を表す評価関数ＥＭ（ｉ，ｊ）は、平均値ｍ（ｉ）、誤差共分散行列Σｍ（ｉ）＋Σｚ（ｊ）の正規分布において、ｚ（ｊ）が得られる確率値に近似できる。この評価関数を用いることによって、環境地図、計測データ双方の誤差を考慮した対応付けが可能となる。
【０１３３】
計測点と環境地図（即ち、環境モデル）との対応付けについて補足説明をする。上記実施例では、誤差分布を考慮した統計的な評価関数を用いるため、評価関数の値を求めなければ対応点を定めることができない。そこで、環境地図上のモデル点群の中で対応付けする候補を予め絞り込み、その候補の中から評価関数の値を基に対応点を求める。具体的には、以下のように定めることができる。
（１）対象とする計測点jの誤差共分散行列ΣＬ（ｊ）の範囲（例えば標準偏差の3倍の範囲）と交わる最上位のボクセルとそのボクセルに隣接している最上位のボクセルを求め、下層のボクセルも含めこれらのボクセル内に存在する代表点を対応点の候補とする。ボクセルが階層構造となっているため、この候補点の探索には計算コストはほとんどかからない。このとき、候補となる代表点がない場合には、対応点がないものとみなす。隣接するボクセルも候補に加える理由は、ボクセル内の代表点の位置によっては、誤差共分散行列の範囲が隣接するボクセルまではみ出すことがあるからである。
（２）候補となるボクセルの代表点iと誤差共分散行列を用いて、評価関数ＥＭ（ｉ，ｊ）の値を求める。
（３）評価関数ＥＭ（ｉ，ｊ）の値が最も大きい代表点iを対応点とする。ただし、最も大きい評価関数の値がある閾値未満の場合には、対応点がないものとみなす。
本実施例では、対応付けの評価関数ＥＭ（ｉ，ｊ）として、尤度に基づいた式を採用しており、対応点の有無に関して統計的に明確な判断尺度があるため、対応点が存在しないと考えられる場合においても無理に対応付けを行うようなことはない。なお、対応点がない場合には、対象となる計測点はこれまで未計測の部分に相当する点であると解釈し、環境地図に追加する。
【０１３４】
実施形態として、三次元形状の計測について説明したが、二次元形状を三次元形状の特別な場合として見ることにより、二次元形状も同様に計測できる。
【０１３５】
なお、本発明は、上述した実施形態に限定されず、本発明の要旨を逸脱しない範囲で種々に変更することができることは勿論である。
【図面の簡単な説明】
【０１３６】
【図１】本発明の物体認識装置の全体構成図である。
【図２】三次元レーザレーダの構成図である。
【図３】距離センサで計測された極座標データと誤差の関係を示す図である。
【図４】誤差分布を直方体に包含される楕円体として近似する場合を示している。
【図５】物体認識処理部の構成の一例を示す図である。
【図６】本発明の方法を示すフローチャートである。
【図７】モデル構築ステップの模式図である。
【図８】構築された環境モデルの模式図である。
【図９】本発明におけるボクセルデータのデータ構造を示す図であり、各ボクセルデータのメモリレイアウト例を示している。
【図１０】本発明におけるボクセルデータのデータ構造を示す図であり、レベル２（１，１，０）のボクセルが代表点を持つ場合の例を示している。
【図１１】粗合わせステップＳ６と精密合わせステップＳ７のデータ処理フロー図である。
【図１２】粗合わせステップＳ６の模式図である。
【図１３】精密合わせステップＳ７の模式図である。
【図１４】モデル更新ステップにおけるデータ処理フロー図である。
【図１５】該当するボクセル内に既に設定した代表点がある場合の模式図である。
【図１６】誤差分布が互いに重複する場合に、両誤差分布から新たな誤差分布と新たな誤差分布の中心を再設定した結果、新たな代表点が他のボクセル内へ移動する場合を示している。
【図１７】誤差分布が互いに重複する場合の模式図である。
【図１８】複数の計測位置を原点とする距離データを統合することによって、代表点の誤差分布が縮小し、代表点の精度が向上する様子を示す模式図である。
【図１９】カルマンフィルタを用いたモデル更新ステップにより得られた結果を示す。
【図２０】図１９の一部拡大図である。
【図２１】誤差を考慮した対応付けを示している。
【図２２】計測データとＣＡＤモデルとのマッチングを説明するための二次元模式図である。
【図２３】計測データとＣＡＤモデルとの対応を説明するための図である。
【図２４】計測データとＣＡＤモデルとの一致度を説明するための図である。
【図２５】計測データとＣＡＤモデルの一致度E（R,t）を、マハラノビス距離を用いて定義するための式である。
【図２６】レベル１のボクセル個数をＮ、分割最大レベルをＬｍａｘとするときのメモリサイズを説明するための図である。
【符号の説明】
【０１３７】
４０  物体認識装置
４１  ３Ｄセンサ
４２  物体認識処理部
４３  モデルデータベース部
４５  ロボット制御部
４６  ロボット
【図１】
0005380792.tif 000017
【図２】
0005380792.tif 000018
【図３】
0005380792.tif 000019
【図４】
0005380792.tif 000020
【図５】
0005380792.tif 000021
【図６】
0005380792.tif 000022
【図７】
0005380792.tif 000023
【図８】
0005380792.tif 000024
【図９】
0005380792.tif 000025
【図１０】
0005380792.tif 000026
【図１１】
0005380792.tif 000027
【図１２】
0005380792.tif 000028
【図１３】
0005380792.tif 000029
【図１４】
0005380792.tif 000030
【図１５】
0005380792.tif 000031
【図１６】
0005380792.tif 000032
【図１７】
0005380792.tif 000033
【図１８】
0005380792.tif 000034
【図１９】
0005380792.tif 000035
【図２０】
0005380792.tif 000036
【図２１】
0005380792.tif 000037
【図２２】
0005380792.tif 000038
【図２３】
0005380792.tif 000039
【図２４】
0005380792.tif 000040
【図２５】
0005380792.tif 000041
【図２６】
0005380792.tif 000042