(57)【特許請求の範囲】
【請求項１】
複数の走査線のなかの距離データから少なくとも１つの対象物を検出する方法において、
スキャナにより複数の走査線のなかの距離データを取得する過程と、
プロセッサにより距離データの点のすべての対の間の線区分を定めるべく各走査線を処理する過程と、
異なる走査線のなかの線区分を結合することにより面を形成する過程と、
もし第１の面しきい値以内の併合面誤差が得られるならば、各走査線のなかの各線区分を最良適合面に併合する過程と、
もし第２の面しきい値以内の結合面誤差が得られるならば、結合面を生ぜしめるべく面の対を併合する過程と、
面に併合され得ない走査線のなかのすべての線区分は、以前の走査線からの併合されていない線区分と比較され、もし併合の結果として得られる面がしきい値以内の誤差を有するならば、新しい面を形成するべく最良可能な併合を行う過程と、を備え
前記の面の併合が完了される時、プロセッサを経て、仮説発生と、前記結合面から形成される少なくとも１つの対象物の検証とを行うことを特徴とする対象物の検出方法。
【請求項２】
さらに、各線区分を最良適合面に併合する以前に、もし線しきい値以内の併合線区分誤差が各線区分に対して得られるならば、各走査線のなかの線区分の対を併合する過程を含んでいることを特徴とする請求項１記載の方法。
【請求項３】
前記の線区分の対の併合が、線区分の対の最良適合のために、最良適合の併合線区分誤差が線しきい値を越えるまで、繰り返して行われることを特徴とする請求項２記載の方法。
【請求項４】
前記の面の対の併合が、
面の各々に対する法線を計算し、
面の識別子を、面の各々に対する法線の成分に基づいて二次元の配列のなかに、
各面を配列のただ１つのセルに対応させて記憶し、
第２の面しきい値以内の結合面誤差を見い出すべく１つのセルおよびそれに隣接するセルのなかの各面とすべての他の面との結合に対する結合面誤差を計算する過程を含んでいることを特徴とする請求項２記載の方法。
【請求項５】
前記の面の対の併合がさらに、第１の面しきい値以内のすべての走査線のなかの線区分および隣接するセルのなかの面の対のすべての可能な併合の後に、もし各々の結合面誤差が第３の面しきい値以内であれば、追加的な結合面を形成するべく、予め定められた距離内の面の対を併合する過程を含んでいることを特徴とする請求項４記載の方法。
【請求項６】
さらに、線区分の１つを最良適合面に併合することにより生ぜしめられる併合面誤差が第１のしきい値よりも大きい時、もし最低可能な併合面誤差が第４の面しきい値以内であれば、この線区分の１つを最低可能な併合面誤差を生ぜしめるべく以前の走査線のなかの他の線区分と併合することを特徴とする請求項５記載の方法。
【請求項７】
さらに、各線区分が通過するすべてのセルを識別するべく関心のある空間をセルに分割する過程を含んでおり、
前記面との前記線区分の併合が、各線区分を線区分が通過するセルを通過する面のみと比較することにより最良適合面を決定することを特徴とする請求項６記載の方法。
【請求項８】
前記面との前記線区分の併合が、各面が通過するセルを、面を形成するべく併合される線が通過するセルとして識別することを特徴とする請求項７記載の方法。
【請求項９】
最初に面を形成するべく行われる線区分の前記併合が、他の走査線に対する距離データを取得しながら、１つの走査線のなかの距離データに対して実行されることを特徴とする請求項８記載の方法。
【請求項１０】
面との線区分の前記併合が、他の走査線に対する距離データを取得しながら、１つの走査線のなかの距離データに対して実行されることを特徴とする請求項８記載の方法。
【請求項１１】
ロボットのロボット視覚装置において、
複数の走査線のなかの距離データを取得するスキャナ‐サブシステムと、
距離データおよび距離データを解析するための計算機プログラムを記憶し、距離データを解析するための作業領域を用意するべく、前記スキャナ‐サブシステムに接続されている少なくとも１つの記憶ユニットと、
各走査線のなかの距離データの点の隣接する対の間の線区分を定めるべく前記記憶ユニットのなかに記憶されている計算機プログラムを実行することにより距離データを解析するため、それぞれ第１の面しきい値以内の第１の面誤差を有する面を形成するべく線区分を結合するため、それぞれ第２の面しきい値以内の第２の面誤差を有する結合された面を形成するべく面の対を併合するため、および対象物情報を生ずるため、前記記憶ユニットおよび前記スキャナ‐サブシステムに接続されているプロセッサと、
距離データの解析の結果としての対象物情報をロボットに与えるべく前記プロセッサ、前記記憶ユニットおよびロボットに接続されている入力／出力インタフェースとを含んでいることを特徴とするロボット視覚装置。
【請求項１２】
前記プロセッサが、面を形成するべく線区分を結合しようと試みる以前に、もし併合線誤差が線しきい値以内であれば、それぞれ併合線誤差を有する併合された線区分を形成するべく各走査線のなかの線区分の対を併合することを特徴とする請求項１１記載のロボット視覚装置。
【請求項１３】
前記プロセッサが、線区分の対の併合により新しい面を形成する以前に、もし併合された面が第３の面しきい値以内の第３の面誤差を有するならば、併合された面を形成するべく、併合されていない線区分の各々および各走査線のなかの併合された線区分を以前の走査線の処理中に形成された最良適合面と併合することを特徴とする請求項１２記載のロボット視覚装置。
【請求項１４】
併合されていない線区分の１つおよび現在の走査線のなかの併合された線区分を最良適合面に併合することにより発生される第３の面誤差が、第３の面しきい値よりも大きい時、前記プロセッサが、もし最小の併合面誤差が第１の面しきい値以内であれば、線区分のすべてのなかで最小の併合面誤差を生ぜしめるべく、併合されていない線区分の１つおよび現在の走査線のなかの併合された線区分を以前の走査線のなかの線区分の１つと併合することを特徴とする請求項１３記載のロボット視覚装置。
【請求項１５】
前記プロセッサが、面の各々に対する法線を計算し、面の識別子を面の各々に対する法線の成分に基づいて前記記憶ユニットの作業領域のなかの二次元の配列のなかに、各面を配列のただ１つのセルに対応させて記憶し、１つのセルおよびそれに隣接するセルのなかのすべての他の面との各面の各結合に対する第２の面誤差を計算し、結合された面の１つとして第２の面しきい値以内の最小の第２の面誤差を有する面の結合を記憶することを特徴とする請求項１４記載のロボット視覚装置。
【請求項１６】
第３の面しきい値以内の第３の面誤差を生ぜしめる最良適合面への、併合されていない線区分および併合された線区分のすべての可能な併合が行われ、第１の面しきい値以内の第１の面誤差を有する新しい面を形成するべく線区分のすべての可能な併合が行われ、かつ第２の面しきい値以内の第２の面誤差を生ぜしめる隣接するセルのなかの面の結合がすべて行われた後に、もし各々の追加的な結合された面が第４の面しきい値以内の第４の面誤差を有するならば、前記プロセッサが追加的な結合された面を形成するべく予め定められた距離内の面の対を併合することを特徴とする請求項１５記載のロボット視覚装置。
【請求項１７】
車両に対する対象物識別システムにおいて、関心のある領域の複数の走査線のなかの距離データを取得するべく車両に取付けられているスキャナと、前記スキャナに接続されており、各走査線のなかの距離データの隣接する点のすべての対の間の線区分を定め、それぞれ第１の面しきい値以内の第１の面誤差を有する面を形成するべく線区分を結合し、それぞれ第２の面しきい値以内の第２の面誤差を有する結合された面を形成するべく面の対を併合し、また結合された面から関心のある領域のなかの対象物を識別するデータ処理システムとを含んでいることを特徴とする車両に対する対象物識別システム。
【請求項１８】
前記データ処理システムが、もし最小の併合線誤差が線しきい値以内であれば、それぞれ対のなかの線区分の少なくとも１つに対して最小の併合線誤差を有する併合された線区分を形成するべく、各走査線のなかの線区分の対を併合し、次いで、もし併合された面が第３の面しきい値以内の第３の面誤差を有するならば、併合された面を形成するべく、併合されていない線区分の各々および各走査線のなかの併合された線区分を以前の走査線の処理中に形成された最良適合面に併合することを特徴とする請求項１７記載の車両に対する対象物識別システム。
【請求項１９】
前記データ処理システムが、面の各々に対する法線を計算し、面の識別子を面の各々に対する法線の成分に基づいて二次元の配列のなかに記憶し、１つのセルおよびそれに隣接するセルのなかのすべての他の面との各面の各結合に対する第２の面誤差を計算し、また結合された面の１つとして第２の面しきい値以内の最小の第２の面誤差を有する面の結合を記憶することを特徴とする請求項１８記載の車両に対する対象物識別システム。
【請求項２０】
線区分と線しきい値以内の併合線誤差を生ぜしめる併合された線区分とのすべての可能な併合が行われ、第１の面しきい値以内の第１の面誤差を生ぜしめる最良適合面への併合されていない線区分および併合された線区分のすべての可能な併合が行われ、第２の面しきい値以内の第２の面誤差を生ぜしめる隣接するセルのなかの面の結合がすべて行われた後に、もし各々の追加的な結合された面が第４の面しきい値以内の第４の面誤差を有するならば、前記プロセッサが追加的な結合された面を形成するべく予め定められた距離内の面の対を併合することを特徴とする請求項１９記載の車両に対する対象物識別システム。
【請求項２１】
関心のある空間内の像を認識するべく計算機システムを作動させる方法において、
スキャナから複数の走査線のなかの距離データを受信する過程と、
前記距離データを分析するための少なくとも１つの記憶ユニット内に前記距離データ及びコンピュータプログラムを蓄積する過程と、
各走査線のなかの距離データの点の隣接する対の間の線区分を定めるため、それぞれ第１の面しきい値以内の第１の面誤差を有する面を形成するべく線区分を結合するため、それぞれ第２の面しきい値以内の第２の面誤差を有する結合された面を形成するべく面の対を併合するため、面に併合され得ない走査線のなかのすべての線区分は、以前の走査線からの併合されていない線区分と比較され、もし併合の結果として得られる面がしきい値以内の誤差を有するならば、新しい面を形成するべく最良可能な併合を行うため、及び、結合された面から関心のある空間内の対象物を認識するため、プロセッサにより距離データを処理する過程と、
前記プロセッサ内の関心のある空間内の認識された対象物を表すデータを出力インタフェースを経て出力する過程とを含んでいることを特徴とする方法。
【請求項２２】
さらに、スキャナから受信された距離データを記憶する過程と、関心のある空間に対応し、また関心のある空間の対応する部分を通過する各線区分に対する線区分データと面データとを、面データにより表される面を形成するべく併合された線区分に対する線区分データを以前に記憶する二次元のセルのなかに記憶する二次元のセルに分けられた記憶領域を定める過程と、
前記処理過程がさらに、もし第３の面しきい値以内の併合面誤差が得られるならば、各線区分を線区分が通過するセルの少なくとも１つを通過する最良適合面に併合する過程を含んでいることを特徴とする請求項２１記載の方法。
【請求項２３】
結合された面を形成するべく面の対を併合する前記処理過程が、
面の識別子を面の各々に対する法線の成分に基づいて二次元の配列のなかに記憶し、
１つのセルのなかの各面および１つのセルおよびそれに隣接するセルのなかのすべての他の面に対する第２の面誤差を計算し、
結合された面の１つとして、第２の面しきい値以内の最小の第２の面誤差を有する面の結合を記憶し、
もし各々の追加的な結合された面が第４の面しきい値以内の結合面誤差を有するならば、追加的な結合された面を形成するべく、予め定められた距離内の面の対を併合する過程を含んでいることを特徴とする請求項２２記載の方法。
【請求項２４】
スキャナにより与えられる距離データから関心のある空間内の対象物を認識するための計算機システムにおいて、
スキャナから複数の走査線のなかの距離データを受信するための手段と、
各走査線のなかの距離データの点の隣接する対の間の線区分を定めるため、それぞれ第１の面しきい値以内の第１の面誤差を有する面を形成するべく線区分を結合するため、それぞれ第２の面しきい値以内の第２の面誤差を有する結合された面を形成するべく面の対を併合するため、結合された面から関心のある空間内の像を認識するため、距離データを処理する手段と、
関心のある空間内の認識された対象物を表すデータを出力する手段とを含んでいることを特徴とする計算機システム。
【請求項２５】
さらに、スキャナから受信された距離データを記憶するため、および、関心のある空間に対応し、関心のある空間の対応する部分を通過する各線区分に対する線区分データと面データとを、面データにより表される面を形成するべく併合された線区分に対する線区分データを以前に記憶する二次元のセルのなかに記憶する二次元のセルに分けられた記憶領域を定めるための手段を含んでおり、
処理のための前記手段が、もし第３の面しきい値以内の併合面誤差が得られるならば、各線区分を線区分が通過するセルの少なくとも１つを通過する最良適合面に併合するための手段を含んでいることを特徴とする請求項２４記載の計算機システム。
【請求項２６】
処理のための前記手段が、結合された面を形成するべく面の対を併合するための手段を含んでおり、この手段が、
面の識別子を面の各々に対する法線の成分に基づいて二次元の配列のなかに記憶するための手段と、
１つのセルのなかの各面および１つのセルおよびそれに隣接するセルのなかのすべての他の面に対する第２の面誤差を計算するための手段と、
結合された面の１つとして、第２の面しきい値以内の最小の第２の面誤差を有する面の結合を記憶するための手段と、
もし各々の追加的な結合された面が第４の面しきい値以内の結合面誤差を有するならば、追加的な結合された面を形成するべく、予め定められた距離内の面の対を併合するための手段とを含んでいることを特徴とする請求項２５記載の計算機システム。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明はロボット視覚システムに関し、また、一層詳細には、走査される一次元の距離センサを使用して得られるデータのなかの面の検出に関する。
【０００２】
【従来の技術】
視覚データまたは環境に関する同等の情報が得られるようにロボットを設計するさまざまな方策が知られている。テレビジョンカメラ、レーダー、ソナー、およびレーザー撮像システムがすべて使用されている。多くの異なる形式のセンサおよび像認識技術が使用されてきた。たいていの技術は膨大な計算を必要とするので、処理に時間がかかり、対象物に関して迅速に得られる情報は通常わずかである。これらの欠点は、センサが自動車車両のような可動のプラットホームの上に取付けられる時、不都合さを増す。
【０００３】
しばしば、センサが可動のプラットホームの上に取付けられる用途では、多くのレーダーシステムの場合のように、センサデータが検出される各対象物に対して単一の点に減ぜられる。一層詳細な情報が望まれる時、対象物に関する情報が検出される間、プラットホームは可能なかぎり固定に保たれ得る。一例として１９９４年３月３日付けのヨーロッパ特許出願第 617,296号明細書に記載されている検出システムでは、検出される点はほぼヘッドライトの高さの車両の床にほぼ平行な単一の面に制限されている。このようなシステムは障害物回避のような用途には適しているが、センサの目的が他の車両のような対象物の三次元測定を行うことである時には不十分である。建設機械に取付けられるセンサのような多くの実世界の用途では、測定実施中にプラットホームを安定に保つことは実際的でない。
【０００４】
【発明が解決しようとする課題】
本発明の課題は、三次元の像データから迅速に平面的特徴を取り出す方法を提供することである。
【０００５】
本発明の他の課題は、データ取得中に運動するプラットホームのようなノイズのある環境のなかの三次元の像データから平面的特徴を取り出すことである。
【０００６】
本発明の別の課題は、多重の走査線から得られた距離データを、走査線間の結合なしに、走査線が張る面のなかに結合することである。
【０００７】
【課題を解決するための手段】
上記の課題は、走査線からの距離データを解析するための計算機‐読取り可能な媒体上で実行される計算機プログラムにおいて、もし第１の面しきい値以内の併合面誤差が得られるならば、最良適合面と各走査線のなかの各線区分を併合する線区分併合コードと、もし第２の面しきい値以内の結合面誤差が得られるならば、面の対を併合する面併合コードとを含んでいることを特徴とする計算機‐読取り可能な媒体上で実行される計算機プログラムにより解決される。計算機プログラムは掘削機または他の建設機械のような可動の機械に取付けられているスキャナに接続されている計算機システム上で実行され得る。スキャナは関心のあるフィールドのなかの三次元の点を得るべく関心のある空間内の複数の走査線を発生するレーダーまたはレーザー装置であり得る。
【０００８】
最良適合面に併合する線区分を得るべく、各走査線のなかでスキャナにより検出される隣接する点が線区分を形成するべく結合される。もし併合の結果として得られる線区分がしきい値以内の誤差を有するならば、各走査線のなかの線区分は併合される。誤差は最小二乗法または他の回帰法を使用して計算され得る。このプロセスは、すべての線区分が、しきい値の超過なしに、他の線区分に併合され終わるまで継続する。
【０００９】
いったん面が形成され終わると、その後の走査線のなかの各線区分は、もししきい値が併合された面により超過されないならば、最良適合面に併合される。面に併合され得ない走査線のなかのすべての線区分は、以前の走査線からの併合されていない線区分と比較され、もし併合の結果として得られる面がしきい値以内の誤差を有するならば、新しい面を形成するべく最良可能な併合が行われる。
【００１０】
法線が面の各々に対して計算される。類似の法線を有する面の可能な併合は、走査線のすべてが処理され終わった後に計算される。もし結合された面がしきい値以内の誤差を有するならば、類似の法線を有するこれらの面との各面に対する最良可能な併合が行われる。上記のすべての可能な併合が完了された後、その結果としての面が、たとえば仮説発生および検証を行うべく、伝統的な対象物認識ソフトウェアに与えられる。
【００１１】
【実施例】
これらの課題は、後で明らかになる他の課題および利点と一緒に、以下の添付図面による詳細な説明および特許請求の範囲から明らかになる構造および作動の詳細に帰する。図面を通じて同じ部分には同じ参照符号が付されている。
【００１２】
図１に示されているように、本発明による方法は、走査線のなかの距離データを取得する過程１０で開始する。本発明による方法を実施するのに使用され得るシステムの簡単化されたブロック図が、図２に示されている。走査線はミシガン州、ファーミントンヒルの「ＰＥＲＣＥＰＴＲＯＮ」の部品番号０００９‐００６４の５０００ＬＡＳＡＲのようなスキャナ１２から取得され得る。本方法は、ウィスコンシン州、マジソンのＨＥＵＲＩＫＯＮまたはＳＩＬＩＣＯＮ  ＧＲＡＰＨＩＣＳ  ＩＮＤＩＧＯまたはＳＵＮ  ＵＬＴＲＡＳＰＡＲＣのＢＡＪＡ４７００のなかのＶＭＥボード上のＭＩＰＳ  Ｒ４７００、または特定の形式のロボットに対する他の適当なデータ処理装置のようなプロセッサ１４を有する計算機システム上で実行され得る。
【００１３】
たとえば、たいていの任意の種類のマイクロプロセッサシステムはフルサイズの掘削機に搭載することができるが、より小さい可動プラットホームにおいては、電池駆動のシステム、またはスキャナ１２から離れた計算機システムの使用を別途必要とすることもある。このような点により、計算機システム内の構成要素は図２中に示されているようなバス１６により、または無線、赤外線、有線などのような代替的な伝送システムにより接続することができる。プロセッサ１４には、作業領域データ記憶のためのＲＡＭおよびハードディスクまたは他のバブルメモリのような不揮発性メモリのような１つまたはそれ以上の記憶ユニット１８も接続される。最後に、入力／出力インタフェース２０が、本発明による処理の結果を、対象物認識を行うための他のプロセッサのような構成要素に与える。代替的に、同一のプロセッサ１４が本発明による距離データを処理するのに、および伝統的な技術を使用して行われ得る対象物認識を行うのに使用され得る。
【００１４】
距離データがスキャナ１２から受信されるにつれて、過程２２で線区分が距離データのなかの隣接する点から形成される。線区分は次いで過程２４でより長い線区分および面の最初の組に併合される。より長い線区分を形成するべく走査線のなかの線区分を結合するための擬似コードの一例は下に示されている。
0004046835.tif 000002
【００１５】
上の擬似コードのなかに示されているように、走査線のなかのデータ点は、それらが受信されるにつれて、データ点を接続する線区分のリストを定めるのに使用される。線区分の各隣接対の直線性が計算され、もし誤差がしきい値よりも小さいならば、可能な併合が優先キューのなかに入れられる。最初の線区分のすべての可能な併合が計算され終わった後に、優先キューのなかの最良併合が実行され、併合された線区分が線のリストから削除され、新しい線が追加される。優先キューのなかの最良併合を実行するプロセスは、優先キューが空になるまで実行される。
【００１６】
線のリストＬのなかに残留する線区分は面に併合される。最初に、面は極めて近接している線区分から形成される。続いて、下記のように、線区分は最良適合面と併合される。好ましい実施例では、線区分および面の近接性は、対象物の検出のために関心のある空間をセルに分け、また残留する線区分の各々が通過するセルを識別することにより決定される。処理を簡単化するべく、擬似コードにあげられている実施例では、三次元の距離データの２つの次元のみが使用される。たとえば、水平面の座標がセルの所属関係を決定するのに使用され得る。この目的の擬似コードは下に示されている。
線のグリッドセル所属関係に対する擬似コード
0004046835.tif 000003
【００１７】
最も新たに処理された走査線のなかの各線区分に対して上に示されているように、残留する線区分の開始および終了点が、それらが同一のセルのなかに置かれているかどうかを見るべくチェックされる。もしそうであれば、線区分はセルに加えられ、最も新たに処理された走査線のなかの残留する線区分のすべてが処理され終わるまで、次の線区分に関して処理が継続される。もし線区分の開始および終了点が同一のセルのなかに位置しないならば、線区分の中心点が見い出され、
所属関係を計算するプロセスが線区分の各半分に対して実行される。線区分は、含まれている線区分の部分が単一のセルのなかに置かれるまで、ますます小さい断片に分けられる。セルの各々のなかの線区分に対して使用される識別子は線区分のすべての部分に対して同一である。さらに、各線区分に対するデータ構造は線区分が通過するセルを表す。
【００１８】
セルのサイズは、アルゴリズムの速度を最適化するべく、関心のある空間のサイズ、認識されるべき対象物のサイズ、走査装置の分解能などのような多数の因子に基づいて選ばれる。たとえば、７メートル幅および１４メートル深さの空間に対しては水平面内に１０×１０のセルの配列が使用され得よう。
【００１９】
本発明の最後の目的は面を生成することである。最初に、同一のセルのなかの線が、いくつの線区分がしきい値以内の誤差を有する面を形成するべく併合され得るかを見るべく検査される。それらの線区分は異なる走査線からのものでなければならず、またたとえば１５Ｅ以下の角度を成して近似的に平行であり、またかなり密である。好ましい実施例では、線区分の質量中心の間のベクトルが各線区分の法線の上に投影され、投影の少なくとも１つの長さが１．５メートル以内である時、線区分は併合するのに十分に密であるとみなされる。
【００２０】
面が形成されるにつれて、線区分の位置を識別するセルの配列が、面を形成するべく併合された線区分がそれを通して置かれた同一のセルのなかに置かれつつある面を識別するべく更新される。面に対する誤差の計算は、たとえセルの所属関係がただ２つの時限に基づいて決定されるとしても、各線のすべての３つの時限を使用する。
【００２１】
最初の面の形成後に処理される走査線に対しては、線区分の併合と残留する線区分が通過するセルの識別との完了時に、各線区分が過程２６で、もし誤差がしきい値よりも小さいならば、最小の誤差を有する近くの面と併合される。このような併合を実行するための擬似コードは下に示されている。
面区分化のための擬似コード
for each scanline s
for each line segment l in s
C = cells through which l passes
P = planes passing through C
M = empty list of merges
compute merges of l and each plane in P
if there are any merges then
perform the best merge
try to merge each plane in P with the new plane
else
L = lines passing through C
if best merge of l and l' in L has low error then
merge l and l'
else
place l into table of objects
endif
endif
endfor
endfor
T = empty n x n table of plane lists
for each plane p in world
add p to cell of T based on x and y components of normal
endfor
【００２２】
上に示されているように、走査線のなかの各線区分に対して、その線区分と、その線区分が通過する同一のセルを通過する面の各々とに対して、併合が計算される。もし誤差がしきい値よりも小さいならば、最良可能な併合が実行される。もし新しい面が線区分との（また場合によっては他の面との）併合により作られるならば、その新しい面が対象物の表（テ−ブル）のなかに置かれ、またその線区分および古い面が除去される。もしその線区分とその線区分と同一のセルを通過する面との間の最良併合がしきい値よりも大きい誤差を有するならば、過程３２で、その線区分を同一のセルを通過する他の線区分と併合する試みがなされる。
面への線区分の最良可能な併合は、もし新しい面がしきい値以内の誤差を有するならば、実行される。その新しい面が対象物の表のなかに置かれ、また既存の線区分は対象物の表から除去される。さもなければ、どの面または既存の線区分とも併合され得なかった走査線のなかの線区分は、対象物の表のなかに置かれる。
【００２３】
もし過程３４で、さらに多くの走査線が処理されるべきことが示されるならば、処理が上記のように継続する。走査線のすべてが処理され終わった後、過程３６で、もし結合された面がしきい値よりも小さい誤差を有するならば、類似の法線を有する面を併合する試みがなされる。類似の面を併合するための擬似コードは下に示されている。
類似の面を併合するための擬似コード
function mergeSimilarPlanes
/* ntab は２次元の配列である。配列中の各セルは特定の値に近い法線 を有する面のリストを含む（各セルに対して異なる）。この値はテ−ブル 中のセルの位置に関係する。*/
ntab = nx by ny array of lists
/* まず，面のすべてをntabに置く */
for each plane p in world
n = normal of p
/* iおよびj，pが置かれるべきntab中の位置を計算 */
i = abs(x component of n) * (nx - 1)
j = abs(y component of n) * (ny - 1)
add p to list of planes in ntab[j][i]
endfor
/* すべての面にわたってル−プし、現在の面と類似する方向性を有する 他の面を見つけるためにntabを使用する。低い併合誤差を有すると わかった面の対を併合する。 */
for each plane p in world
/* iおよびj，pが置かれるべきntab中の位置を計算 */
i = abs(x component of n) * (nx - 1)
j = abs(y component of n) * (ny - 1)
/* セル[i][j]に隣接するテ−ブル内のすべてのセルを見る。すなわち p'の法線に近い法線を有するすべての面を見る。 */
for jj = j-1 to j+1
for ii = i-1 to i+1
planeList = all planes in ntab[jj][ii]
for each plane p' in planeList
newp = p merged with p'
if newp has small error
/* テ−ブルを更新 */
remove p from list of planes in world
remove p' from list of planes in world
remove p from ntab
remove p' from ntab
add newp to list of planes in world
add newp to ntab
skip to next plane p in world
endif
endfor
endfor
endfor
endfor
end function
【００２４】
上に示されているように、類似の面を併合するための擬似コードは線および面を併合するための擬似コードに似ている。二次元の配列は、併合のための候補でありそうな面を識別するプロセスを簡単化するべく、面で満たされている。二次元の配列は記憶ユニット１８により用意される作業領域のなかで定められる。配列のなかのセルの数は、面のどのような類似が可能な併合のために検査されるべきかに関係する。これは順番に、誤差に対して使用されているしきい、面の数、距離データのなかのノイズの大きさ、速度に対する最適化などに関係する。本質的に二次元の配列は、面の各々に対する法線と、線区分および面が通過するセルを識別するのに使用される水平面のような参照面のなかの軸線とにより作られる角度を表す。たとえば、セルは法線のＸおよびＹ成分の絶対値に０．１の変動を表し得る。
【００２５】
配列が満たされた後、セルは一度に一つ通り抜けられ、またセルのなかの各面に対してそのセルおよび隣のセルのなかの他の面との可能な併合が計算される。上の擬似コード中に示されているように、９つのセルの全体がチェックされる。なぜならば、もし他の面と比較されているその面の法線が距離の境の１つに近いならば、それは同一のセルのなかの面のどれよりも隣のセルのなかの面の法線に近いことがあり得る。
【００２６】
好ましい実施例では、最良可能な併合を行う試みはなされない。いったんしきい値よりも小さい誤差を有する結合された面が見い出されると、その２つの併合された面が面のリストから、また法線の配列から削除され、またその結合された面がそのリストに追加され、またその結合された面のその法線が法線の配列に追加される。次いで、面のリストのなかの次の面が処理される。新しい面がリストの端に追加されるので、リストの端が到達される時、（新しい面を含めて）面のすべては処理され終わっている。面の可能な併合がもはや存在しないことを確かめるべく、最後の過程で、下の擬似コードのなかに示されているように、近くの面を併合しようと試みる。この処理は、密に近接しており、また測定誤差に起因して十分に異なる法線を有し、使用される離散化のレベルに起因して隣のセルのなかにはないが、結果としての併合された面が受容可能なしきい値よりも小さい誤差を有する面、特に小さい面を検出する。
0004046835.tif 000004
0004046835.tif 000005
【００２７】
線を面に併合するために使用されるセルの配列は、類似の法線を有する面が併合され終わった後に近くの面を併合するのに再び使用される。上に示されているように、近くの面を併合するプロセスは類似の法線を有する面を併合するプロセスに似ている。相違点は、隣のセルが、法線の成分の代わりに、線および面を併合するのに使用される同一の地理的セルを表すことである。プロセスは、もはや併合が生起しなくなるまで、継続する。
【００２８】
一例は、距離データから得られたデータ点の組とトラックの床の抽象的表現５８とを示す図３に与えられている。大きいほうの点は、上記の擬似コードから発生される計算機コードを実行することにより面に併合されるデータ点を表す。データ点６０および６２の群により形成される面の部分は、トラック運転台の頂後縁および左後縁に相当し、従ってまたトラックの識別に有用であり得る面に相当する。しかし、群６４のなかのデータ点は大地の部分であり、好ましくは他の面の部分として結合されるべきではない。
【００２９】
ダンプトラックの距離スキャンが図４に示されている。上記の擬似コードから発生される計算機コードは示されているような面を発生する。これらの面は、認識されるべき対象物が似て見えるべきモデルを有する伝統的なソフトウェアであり得る対象物認識ソフトウェア３８に与えられる。従来通常のように、このような対象物認識ソフトウェアは、面または面の部分が何を表すかの仮説を発生し、また検証手順が仮説を検証するべく実行される。このプロセスは、対象物が認識されるまで、またはその面がそのソフトウェアが認識可能などの対象物とも合致しないことが決定されるまで、繰り返される。
【００３０】
本発明の多くの特徴および利点が詳細な説明から明らかであり、またこうして本発明の一般的な原理およびスコ−プに属するシステムおよび方法のすべてのこのような特徴および利点は、特許請求の範囲によりカバーされている。さらに、さまざまな変更が本発明の開示を参考にして当業者により行われ得るので、以上に図示かつ説明した厳密な構造および動作に本発明の範囲を限定することは望まれない。他の適当な変更および均等なものは本発明の趣旨に属するものとして主張され得る。
【図面の簡単な説明】
【図１】本発明による方法のフロ−チャート。
【図２】本発明による方法を実施するのに使用され得るシステムのブロック図。
【図３】誤った面の検出に終わり得る距離データの一例。
【図４】上からとられたダンプトラックの距離スキャンの一例。
【符号の説明】
５８    トラックの床の抽象的表現
６０、６２    データ点
６４    データ点の群
【図１】
0004046835.tif 000006
【図２】
0004046835.tif 000007
【図３】
0004046835.tif 000008
【図４】
0004046835.tif 000009