JPH10240944A - 可動ロボットに対する距離データの高速面区分化方法 - Google Patents
可動ロボットに対する距離データの高速面区分化方法Info
- Publication number
- JPH10240944A JPH10240944A JP10051241A JP5124198A JPH10240944A JP H10240944 A JPH10240944 A JP H10240944A JP 10051241 A JP10051241 A JP 10051241A JP 5124198 A JP5124198 A JP 5124198A JP H10240944 A JPH10240944 A JP H10240944A
- Authority
- JP
- Japan
- Prior art keywords
- line
- error
- merged
- merging
- threshold
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Granted
Links
Classifications
-
- G—PHYSICS
- G06—COMPUTING OR CALCULATING; COUNTING
- G06T—IMAGE DATA PROCESSING OR GENERATION, IN GENERAL
- G06T7/00—Image analysis
- G06T7/10—Segmentation; Edge detection
- G06T7/12—Edge-based segmentation
-
- G—PHYSICS
- G06—COMPUTING OR CALCULATING; COUNTING
- G06T—IMAGE DATA PROCESSING OR GENERATION, IN GENERAL
- G06T7/00—Image analysis
- G06T7/10—Segmentation; Edge detection
- G06T7/181—Segmentation; Edge detection involving edge growing; involving edge linking
-
- G—PHYSICS
- G06—COMPUTING OR CALCULATING; COUNTING
- G06V—IMAGE OR VIDEO RECOGNITION OR UNDERSTANDING
- G06V10/00—Arrangements for image or video recognition or understanding
- G06V10/20—Image preprocessing
- G06V10/26—Segmentation of patterns in the image field; Cutting or merging of image elements to establish the pattern region, e.g. clustering-based techniques; Detection of occlusion
- G06V10/267—Segmentation of patterns in the image field; Cutting or merging of image elements to establish the pattern region, e.g. clustering-based techniques; Detection of occlusion by performing operations on regions, e.g. growing, shrinking or watersheds
-
- G—PHYSICS
- G06—COMPUTING OR CALCULATING; COUNTING
- G06V—IMAGE OR VIDEO RECOGNITION OR UNDERSTANDING
- G06V20/00—Scenes; Scene-specific elements
- G06V20/10—Terrestrial scenes
-
- G—PHYSICS
- G06—COMPUTING OR CALCULATING; COUNTING
- G06V—IMAGE OR VIDEO RECOGNITION OR UNDERSTANDING
- G06V20/00—Scenes; Scene-specific elements
- G06V20/60—Type of objects
- G06V20/64—Three-dimensional [3D] objects
-
- G—PHYSICS
- G06—COMPUTING OR CALCULATING; COUNTING
- G06T—IMAGE DATA PROCESSING OR GENERATION, IN GENERAL
- G06T2207/00—Indexing scheme for image analysis or image enhancement
- G06T2207/10—Image acquisition modality
- G06T2207/10032—Satellite or aerial image; Remote sensing
- G06T2207/10044—Radar image
-
- G—PHYSICS
- G06—COMPUTING OR CALCULATING; COUNTING
- G06T—IMAGE DATA PROCESSING OR GENERATION, IN GENERAL
- G06T2207/00—Indexing scheme for image analysis or image enhancement
- G06T2207/30—Subject of image; Context of image processing
- G06T2207/30248—Vehicle exterior or interior
- G06T2207/30252—Vehicle exterior; Vicinity of vehicle
Landscapes
- Engineering & Computer Science (AREA)
- Physics & Mathematics (AREA)
- General Physics & Mathematics (AREA)
- Theoretical Computer Science (AREA)
- Multimedia (AREA)
- Computer Vision & Pattern Recognition (AREA)
- Image Analysis (AREA)
- Length Measuring Devices By Optical Means (AREA)
- Image Processing (AREA)
Abstract
(57)【要約】
【課題】 走査線からの距離データを解析するための計
算機‐読取り可能な媒体上で実行される計算機プログラ
ムにおいて、迅速に三次元の像データから平面的特徴を
取り出す方法を提供する。 【解決手段】 走査線からの距離データを解析するため
の計算機プログラムにおいて、もし第１の面しきい値以
内の被併合面誤差が得られるならば、最良適合面と各走
査線のなかの各線区分を併合する線区分併合コードと、
もし第２の面しきい値以内の被結合面誤差が得られるな
らば、面の対を併合する面併合コードとを含んでいる。
算機‐読取り可能な媒体上で実行される計算機プログラ
ムにおいて、迅速に三次元の像データから平面的特徴を
取り出す方法を提供する。 【解決手段】 走査線からの距離データを解析するため
の計算機プログラムにおいて、もし第１の面しきい値以
内の被併合面誤差が得られるならば、最良適合面と各走
査線のなかの各線区分を併合する線区分併合コードと、
もし第２の面しきい値以内の被結合面誤差が得られるな
らば、面の対を併合する面併合コードとを含んでいる。
Description
【０００１】
【発明の属する技術分野】本発明はロボット視覚システ
ムに関し、また、一層詳細には、走査される一次元の距
離センサを使用して得られるデータのなかの面の検出に
関する。
ムに関し、また、一層詳細には、走査される一次元の距
離センサを使用して得られるデータのなかの面の検出に
関する。
【０００２】
【従来の技術】視覚データまたは環境に関する同等の情
報が得られるようにロボットを設計するさまざまな方策
が知られている。テレビジョンカメラ、レーダー、ソナ
ー、およびレーザー撮像システムがすべて使用されてい
る。多くの異なる形式のセンサおよび像認識技術が使用
されてきた。たいていの技術は膨大な計算を必要とする
のて、処理に時間がかかり、対象物に関して迅速に得ら
れ情報は通常わずかである。これらの欠点は、センサが
自動車車両のような可動のプラットホームの上に取付け
られる時、不都合さを増す。
報が得られるようにロボットを設計するさまざまな方策
が知られている。テレビジョンカメラ、レーダー、ソナ
ー、およびレーザー撮像システムがすべて使用されてい
る。多くの異なる形式のセンサおよび像認識技術が使用
されてきた。たいていの技術は膨大な計算を必要とする
のて、処理に時間がかかり、対象物に関して迅速に得ら
れ情報は通常わずかである。これらの欠点は、センサが
自動車車両のような可動のプラットホームの上に取付け
られる時、不都合さを増す。
【０００３】しばしば、センサが可動のプラットホーム
の上に取付けられる用途では、多くのレーダーシステム
の場合のように、センサデータが検出される各対象物に
対して単一の点に減ぜられる。一層詳細な情報が望まれ
る時、対象物にに関する情報が検出される間、プラット
ホームは可能なかぎり固定に保たれ得る。一例として１
９９４年３月３日付けのヨーロッパ特許出願第 617,296
号明細書に記載されている検出システムでは、検出され
る点はほぼヘッドライトの高さの車両の床にほぼ平行な
単一の面に制限されている。このようなシステムは障害
物回避のような用途には適しているが、センサの目的が
他の車両のような対象物の三次元測定を行うことである
時には不十分である。建設機械に取付けられるセンサの
ような多くの実世界の用途では、測定実施中にプラット
ホームを安定に保つことは実際的でない。
の上に取付けられる用途では、多くのレーダーシステム
の場合のように、センサデータが検出される各対象物に
対して単一の点に減ぜられる。一層詳細な情報が望まれ
る時、対象物にに関する情報が検出される間、プラット
ホームは可能なかぎり固定に保たれ得る。一例として１
９９４年３月３日付けのヨーロッパ特許出願第 617,296
号明細書に記載されている検出システムでは、検出され
る点はほぼヘッドライトの高さの車両の床にほぼ平行な
単一の面に制限されている。このようなシステムは障害
物回避のような用途には適しているが、センサの目的が
他の車両のような対象物の三次元測定を行うことである
時には不十分である。建設機械に取付けられるセンサの
ような多くの実世界の用途では、測定実施中にプラット
ホームを安定に保つことは実際的でない。
【０００４】
【発明が解決しようとする課題】本発明の課題は、三次
元の像データから迅速に平面的特徴を取り出す方法を提
供することである。
元の像データから迅速に平面的特徴を取り出す方法を提
供することである。
【０００５】本発明の他の課題は、データ取得中に運動
するプラットホームのようなノイズのある環境のなかの
三次元の像データから平面的特徴を取り出すことであ
る。
するプラットホームのようなノイズのある環境のなかの
三次元の像データから平面的特徴を取り出すことであ
る。
【０００６】本発明の別の課題は、多重の走査線から得
られた距離データを、走査線間の結合なしに、走査線が
張る面のなかに結合することである。
られた距離データを、走査線間の結合なしに、走査線が
張る面のなかに結合することである。
【０００７】
【課題を解決するための手段】上記の課題は、走査線か
らの距離データを解析するための計算機‐読取り可能な
媒体上で実行される計算機プログラムにおいて、もし第
１の面しきい値以内の併合面誤差が得られるならば、最
良適合面と各走査線のなかの各線区分を併合する線区分
併合コードと、もし第２の面しきい値以内の結合面誤差
が得られるならば、面の対を併合する面併合コードとを
含んでいることを特徴とする計算機‐読取り可能な媒体
上で実行される計算機プログラムにより解決される。計
算機プログラムは掘削機または他の建設機械のような可
動の機械に取付けられているスキャナに接続されている
計算機システム上で実行され得る。スキャナは関心のあ
るフィールドのなかの三次元の点を得るべく関心のある
空間内の複数の走査線を発生するレーダーまたはレーザ
ー装置であり得る。
らの距離データを解析するための計算機‐読取り可能な
媒体上で実行される計算機プログラムにおいて、もし第
１の面しきい値以内の併合面誤差が得られるならば、最
良適合面と各走査線のなかの各線区分を併合する線区分
併合コードと、もし第２の面しきい値以内の結合面誤差
が得られるならば、面の対を併合する面併合コードとを
含んでいることを特徴とする計算機‐読取り可能な媒体
上で実行される計算機プログラムにより解決される。計
算機プログラムは掘削機または他の建設機械のような可
動の機械に取付けられているスキャナに接続されている
計算機システム上で実行され得る。スキャナは関心のあ
るフィールドのなかの三次元の点を得るべく関心のある
空間内の複数の走査線を発生するレーダーまたはレーザ
ー装置であり得る。
【０００８】最良適合面に併合する線区分を得るべく、
各走査線のなかでスキャナにより検出される隣接する点
が線区分を形成するべく結合される。もし併合の結果と
して得られる線区分がしきい値以内の誤差を有するなら
ば、各走査線のなかの線区分は併合される。誤差は最小
二乗法または他の回帰法を使用して計算され得る。この
プロセスは、すべての線区分が、しきい値の超過なし
に、他の線区分に併合され終わるまで継続する。
各走査線のなかでスキャナにより検出される隣接する点
が線区分を形成するべく結合される。もし併合の結果と
して得られる線区分がしきい値以内の誤差を有するなら
ば、各走査線のなかの線区分は併合される。誤差は最小
二乗法または他の回帰法を使用して計算され得る。この
プロセスは、すべての線区分が、しきい値の超過なし
に、他の線区分に併合され終わるまで継続する。
【０００９】いったん面が形成され終わると、その後の
走査線のなかの各線区分は、もししきい値が併合された
面により超過されないならば、最良適合面に併合され
る。面に併合され得ない走査線のなかのすべての線区分
は、以前の走査線からの併合されていない線区分と比較
され、もし併合の結果として得られる面がしきい値以内
の誤差を有するならば、新しい面を形成するべく最良可
能な併合が行われる。
走査線のなかの各線区分は、もししきい値が併合された
面により超過されないならば、最良適合面に併合され
る。面に併合され得ない走査線のなかのすべての線区分
は、以前の走査線からの併合されていない線区分と比較
され、もし併合の結果として得られる面がしきい値以内
の誤差を有するならば、新しい面を形成するべく最良可
能な併合が行われる。
【００１０】法線が面の各々に対して計算される。類似
の法線を有する面の可能な併合は、走査線のすべてが処
理され終わった後に計算される。もし結合された面がし
きい値以内の誤差を有するならば、類似の法線を有する
これらの面との各面に対する最良可能な併合が行われ
る。上記のすべての可能な併合が完了された後、その結
果としての面が、たとえば仮説発生および検証を行うべ
く、伝統的な対象物認識ソフトウェアに与えられる。
の法線を有する面の可能な併合は、走査線のすべてが処
理され終わった後に計算される。もし結合された面がし
きい値以内の誤差を有するならば、類似の法線を有する
これらの面との各面に対する最良可能な併合が行われ
る。上記のすべての可能な併合が完了された後、その結
果としての面が、たとえば仮説発生および検証を行うべ
く、伝統的な対象物認識ソフトウェアに与えられる。
【００１１】
【実施例】これらの課題は、後で明らかになる他の課題
および利点と一緒に、以下の添付図面による詳細な説明
および特許請求の範囲から明らかになる構造および作動
の詳細に帰する。図面を通じて同じ部分には同じ参照符
号が付されている。
および利点と一緒に、以下の添付図面による詳細な説明
および特許請求の範囲から明らかになる構造および作動
の詳細に帰する。図面を通じて同じ部分には同じ参照符
号が付されている。
【００１２】図１に示されているように、本発明による
方法は、走査線のなかの距離データを取得する過程１０
で開始する。本発明による方法を実施するのに使用され
得るシステムの簡単化されたブロック図が、図２に示さ
れている。走査線はミシガン州、ファーミントンヒルの
「ＰＥＲＣＥＰＴＲＯＮ」の部品番号０００９‐００６
４の５０００ＬＡＳＡＲのようなスキャナ１２から取得
され得る。本方法は、ウィスコンシン州、マジソンのＨ
ＥＵＲＩＫＯＮまたはＳＩＬＩＣＯＮ ＧＲＡＰＨＩＣ
Ｓ ＩＮＤＩＧＯまたはＳＵＮ ＵＬＴＲＡＳＰＡＲＣ
のＢＡＪＡ４７００のなかのＶＭＥボード上のＭＩＰＳ
Ｒ４７００、または特定の形式のロボットに対する他
の適当なデータ処理装置のようなプロセッサ１４を有す
る計算機システム上で実行され得る。
方法は、走査線のなかの距離データを取得する過程１０
で開始する。本発明による方法を実施するのに使用され
得るシステムの簡単化されたブロック図が、図２に示さ
れている。走査線はミシガン州、ファーミントンヒルの
「ＰＥＲＣＥＰＴＲＯＮ」の部品番号０００９‐００６
４の５０００ＬＡＳＡＲのようなスキャナ１２から取得
され得る。本方法は、ウィスコンシン州、マジソンのＨ
ＥＵＲＩＫＯＮまたはＳＩＬＩＣＯＮ ＧＲＡＰＨＩＣ
Ｓ ＩＮＤＩＧＯまたはＳＵＮ ＵＬＴＲＡＳＰＡＲＣ
のＢＡＪＡ４７００のなかのＶＭＥボード上のＭＩＰＳ
Ｒ４７００、または特定の形式のロボットに対する他
の適当なデータ処理装置のようなプロセッサ１４を有す
る計算機システム上で実行され得る。
【００１３】たとえば、たいていの任意の種類のマイク
ロプロセッサシステムがフルサイズの掘削機に取付けら
れ得ようが、より小さい可動プラットホームは、電池駆
動のシステムまたはスキャナ１２から離れた計算機シス
テムの使用を必要とすることもあろう。こうして、計算
機システム内の構成要素は図２中に示されているように
バス１６により、または無線、赤外線、有線などのよう
な代替的な伝送システムにより接続され得る。プロセッ
サ１４には、作業領域データ記憶のためのＲＡＭおよび
ハードディスクまたは他のバブルメモリのような不揮発
性メモリのような１つまたはそれ以上の記憶ユニット１
８も接続される。最後に、入力／出力インタフェース２
０が、本発明による処理の結果を、対象物認識を行うた
めの他のプロセッサのような構成要素に与える。代替的
に、同一のプロセッサ１４が本発明による距離データを
処理するのに、および伝統的な技術を使用して行われ得
る対象物認識を行うのに使用され得る。
ロプロセッサシステムがフルサイズの掘削機に取付けら
れ得ようが、より小さい可動プラットホームは、電池駆
動のシステムまたはスキャナ１２から離れた計算機シス
テムの使用を必要とすることもあろう。こうして、計算
機システム内の構成要素は図２中に示されているように
バス１６により、または無線、赤外線、有線などのよう
な代替的な伝送システムにより接続され得る。プロセッ
サ１４には、作業領域データ記憶のためのＲＡＭおよび
ハードディスクまたは他のバブルメモリのような不揮発
性メモリのような１つまたはそれ以上の記憶ユニット１
８も接続される。最後に、入力／出力インタフェース２
０が、本発明による処理の結果を、対象物認識を行うた
めの他のプロセッサのような構成要素に与える。代替的
に、同一のプロセッサ１４が本発明による距離データを
処理するのに、および伝統的な技術を使用して行われ得
る対象物認識を行うのに使用され得る。
【００１４】距離データがスキャナ１２から受信される
につれて、過程２２で線区分が距離データのなかの隣接
する点から形成される。線区分は次いで過程２４でより
長い線区分および面の最初の組に併合される。より長い
線区分を形成するべく走査線のなかの線区分を結合する
ための擬似コードの一例は下に示されている。直線区分化のための擬似コード for each point pi scanline add line between pi and pi+1 to list of lines L endfor q = empty priority queue for each line l in L compute the merges mL and mR of l with its neighbors if error(mL) < threshold then add mL to q endif if error(mR) < threshold then add mR to q endif end for while q is not empty m = best merge in q merge lines in m and add resulting line l to L compute merges for l and add to q endwhile
につれて、過程２２で線区分が距離データのなかの隣接
する点から形成される。線区分は次いで過程２４でより
長い線区分および面の最初の組に併合される。より長い
線区分を形成するべく走査線のなかの線区分を結合する
ための擬似コードの一例は下に示されている。直線区分化のための擬似コード for each point pi scanline add line between pi and pi+1 to list of lines L endfor q = empty priority queue for each line l in L compute the merges mL and mR of l with its neighbors if error(mL) < threshold then add mL to q endif if error(mR) < threshold then add mR to q endif end for while q is not empty m = best merge in q merge lines in m and add resulting line l to L compute merges for l and add to q endwhile
【００１５】上の擬似コードのなかに示されているよう
に、走査線のなかのデータ点は、それらが受信されるに
つれて、データ点を接続する線区分のリストを定めるの
に使用される。線区分の各隣接対の直線性が計算され、
もし誤差がしきい値よりも小さいならば、可能な併合が
優先キューのなかに入れられる。最初の線区分のすべて
の可能な併合が計算され終わった後に、優先キューのな
かの最良併合が実行され、併合された線区分が線のリス
トから削除され、新しい線が追加される。優先キューの
なかの最良併合を実行するプロセスは、優先キューが空
になるまで実行される。
に、走査線のなかのデータ点は、それらが受信されるに
つれて、データ点を接続する線区分のリストを定めるの
に使用される。線区分の各隣接対の直線性が計算され、
もし誤差がしきい値よりも小さいならば、可能な併合が
優先キューのなかに入れられる。最初の線区分のすべて
の可能な併合が計算され終わった後に、優先キューのな
かの最良併合が実行され、併合された線区分が線のリス
トから削除され、新しい線が追加される。優先キューの
なかの最良併合を実行するプロセスは、優先キューが空
になるまで実行される。
【００１６】線のリストＬのなかに残留する線区分は面
に併合される。最初に、面は極めて近接している線区分
から形成される。続いて、下記のように、線区分は最良
適合面と併合される。好ましい実施例では、線区分およ
び面の近接性は、対象物の検出のために関心のある空間
をセルに分け、また残留する線区分の各々が通過するセ
ルを識別することにより決定される。処理を簡単化する
べく、擬似コードにあげられている実施例では、三次元
の距離データの２つの時限のみが使用される。たとえ
ば、水平面の座標がセルの所属関係を決定するのに使用
され得る。この目的の擬似コードは下に示されている。線のグリッドセル所属関係に対する擬似コード
に併合される。最初に、面は極めて近接している線区分
から形成される。続いて、下記のように、線区分は最良
適合面と併合される。好ましい実施例では、線区分およ
び面の近接性は、対象物の検出のために関心のある空間
をセルに分け、また残留する線区分の各々が通過するセ
ルを識別することにより決定される。処理を簡単化する
べく、擬似コードにあげられている実施例では、三次元
の距離データの２つの時限のみが使用される。たとえ
ば、水平面の座標がセルの所属関係を決定するのに使用
され得る。この目的の擬似コードは下に示されている。線のグリッドセル所属関係に対する擬似コード
【００１７】最も新たに処理された走査線のなかの各線
区分に対して上に示されているように、残留する線区分
の開始および終了点が、それらが同一のセルのなかに置
かれているかどうかを見るべくチェックされる。もしそ
うであれば、線区分はセルに加えられ、最も新たに処理
された走査線のなかの残留する線区分のすべてが処理さ
れ終わるまで、次の線区分に関して処理が継続される。
もし線区分の開始および終了点が同一のセルのなかに位
置しないならば、線区分の中心点が見い出され、所属関
係を計算するプロセスが線区分の各半分に対して実行さ
れる。線区分は、含まれている線区分の部分が単一のセ
ルのなかに置かれるまで、ますます小さい断片に分けら
れる。セルの各々のなかの線区分に対して使用される識
別子は線区分のすべての部分に対して同一である。さら
に、各線区分に対するデータ構造は線区分が通過するセ
ルを表す。
区分に対して上に示されているように、残留する線区分
の開始および終了点が、それらが同一のセルのなかに置
かれているかどうかを見るべくチェックされる。もしそ
うであれば、線区分はセルに加えられ、最も新たに処理
された走査線のなかの残留する線区分のすべてが処理さ
れ終わるまで、次の線区分に関して処理が継続される。
もし線区分の開始および終了点が同一のセルのなかに位
置しないならば、線区分の中心点が見い出され、所属関
係を計算するプロセスが線区分の各半分に対して実行さ
れる。線区分は、含まれている線区分の部分が単一のセ
ルのなかに置かれるまで、ますます小さい断片に分けら
れる。セルの各々のなかの線区分に対して使用される識
別子は線区分のすべての部分に対して同一である。さら
に、各線区分に対するデータ構造は線区分が通過するセ
ルを表す。
【００１８】セルのサイズは、アルゴリズムの速度を最
適化するべく、関心のある空間のサイズ、認識されるべ
き対象物のサイズ、走査装置の分解能などのような多数
の因子に基づいて選ばれる。たとえば、７メートル幅お
よび１４メートル深さの空間に対しては水平面内に１０
×１０のセルの配列が使用され得よう。
適化するべく、関心のある空間のサイズ、認識されるべ
き対象物のサイズ、走査装置の分解能などのような多数
の因子に基づいて選ばれる。たとえば、７メートル幅お
よび１４メートル深さの空間に対しては水平面内に１０
×１０のセルの配列が使用され得よう。
【００１９】本発明の最後の目的は面を生成することで
ある。最初に、同一のセルのなかの線が、いくつの線区
分がしきい値以内の誤差を有する面を形成するべく併合
され得るかを見るべく検査される。それらの線区分は異
なる走査線からのものでなければならず、またたとえば
１５Ｅ以下の角度を成して近似的に平行であり、またか
なり密である。好ましい実施例では、線区分の質量中心
の間のベクトルが各線区分の法線の上に投影され、投影
の少なくとも１つの長さが１．５メートル以内である
時、線区分は併合するのに十分に密であるとみなされ
る。
ある。最初に、同一のセルのなかの線が、いくつの線区
分がしきい値以内の誤差を有する面を形成するべく併合
され得るかを見るべく検査される。それらの線区分は異
なる走査線からのものでなければならず、またたとえば
１５Ｅ以下の角度を成して近似的に平行であり、またか
なり密である。好ましい実施例では、線区分の質量中心
の間のベクトルが各線区分の法線の上に投影され、投影
の少なくとも１つの長さが１．５メートル以内である
時、線区分は併合するのに十分に密であるとみなされ
る。
【００２０】面が形成されるにつれて、線区分の位置を
識別するセルの配列が、面を形成するべく併合された線
区分がそれを通して置かれた同一のセルのなかに置かれ
つつある面を識別するべく更新される。面に対する誤差
の計算は、たとえセルの所属関係がただ２つの時限に基
づいて決定されるとしても、各線のすべての３つの時限
を使用する。
識別するセルの配列が、面を形成するべく併合された線
区分がそれを通して置かれた同一のセルのなかに置かれ
つつある面を識別するべく更新される。面に対する誤差
の計算は、たとえセルの所属関係がただ２つの時限に基
づいて決定されるとしても、各線のすべての３つの時限
を使用する。
【００２１】最初の面の形成後に処理される走査線に対
しては、線区分の併合と残留する線区分が通過するセル
の識別との完了時に、各線区分が過程２６で、もし誤差
がしきい値よりも小さいならば、最小の誤差を有する近
くの面と併合される。このような併合を実行するための
擬似コードは下に示されている。面区分化のための擬似コード 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 enffor 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
しては、線区分の併合と残留する線区分が通過するセル
の識別との完了時に、各線区分が過程２６で、もし誤差
がしきい値よりも小さいならば、最小の誤差を有する近
くの面と併合される。このような併合を実行するための
擬似コードは下に示されている。面区分化のための擬似コード 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 enffor 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 ennfor endfor endfor endfor end function
理されるべきことが示されるならば、処理が上記のよう
に継続する。走査線のすべてが処理され終わった後、過
程３６で、もし結合された面がしきい値よりも小さい誤
差を有するならば、類似の法線を有する面を併合する試
みがなされる。類似の面を併合するための擬似コードは
下に示されている。類似の面を併合するための擬似コード 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 ennfor endfor endfor endfor end function
【００２４】上に示されているように、類似の面を併合
するための擬似コードは線および面を併合するための擬
似コードに似ている。二次元の配列は、併合のための候
補でありそうな面を識別するプロセスを簡単化するべ
く、面で満たされている。二次元の配列は記憶ユニット
１８により用意される作業領域のなかで定められる。配
列のなかのセルの数は、面のどのような類似が可能な併
合のために検査されるべきかに関係する。これは順番
に、誤差に対して使用されているしきい、面の数、距離
データのなかのノイズの大きさ、速度に対する最適化な
どに関係する。本質的に二次元の配列は、面の各々に対
する法線と、線区分および面が通過するセルを識別する
のに使用される水平面のような参照面のなかの軸線とに
より作られる角度を表す。たとえば、セルは法線のＸお
よびＹ成分の絶対値に０．１の変動を表し得る。
するための擬似コードは線および面を併合するための擬
似コードに似ている。二次元の配列は、併合のための候
補でありそうな面を識別するプロセスを簡単化するべ
く、面で満たされている。二次元の配列は記憶ユニット
１８により用意される作業領域のなかで定められる。配
列のなかのセルの数は、面のどのような類似が可能な併
合のために検査されるべきかに関係する。これは順番
に、誤差に対して使用されているしきい、面の数、距離
データのなかのノイズの大きさ、速度に対する最適化な
どに関係する。本質的に二次元の配列は、面の各々に対
する法線と、線区分および面が通過するセルを識別する
のに使用される水平面のような参照面のなかの軸線とに
より作られる角度を表す。たとえば、セルは法線のＸお
よびＹ成分の絶対値に０．１の変動を表し得る。
【００２５】配列が満たされた後、セルは一度に一つ通
り抜けられ、またセルのなかの各面に対してそのセルお
よび隣のセルのなかの他の面との可能な併合が計算され
る。上の擬似コード中に示されているように、９つのセ
ルの全体がチェックされる。なぜならば、もし他の面と
比較されているその面の法線が距離の境の１つに近いな
らば、それは同一のセルのなかの面のどれよりも隣のセ
ルのなかの面の法線に近いことがあり得る。
り抜けられ、またセルのなかの各面に対してそのセルお
よび隣のセルのなかの他の面との可能な併合が計算され
る。上の擬似コード中に示されているように、９つのセ
ルの全体がチェックされる。なぜならば、もし他の面と
比較されているその面の法線が距離の境の１つに近いな
らば、それは同一のセルのなかの面のどれよりも隣のセ
ルのなかの面の法線に近いことがあり得る。
【００２６】好ましい実施例では、最良可能な併合を行
う試みはなされない。いったんしきい値よりも小さい誤
差を有する結合された面が見い出されると、その２つの
併合された面が面のリストから、また法線の配列から削
除され、またその結合された面がそのリストに追加さ
れ、またその結合された面のその法線が法線の配列に追
加される。次いで、面のリストのなかの次の面が処理さ
れる。新しい面がリストの端に追加されるので、リスト
の端が到達される時、（新しい面を含めて）面のすべて
は処理され終わっている。面の可能な併合がもはや存在
しないことを確かめるべく、最後の過程で、下の擬似コ
ードのなかに示されているように、近くの面を併合しよ
うと試みる。この処理は、密に近接しており、また測定
誤差に起因して十分に異なる法線を有し、使用される離
散化のレベルに起因して隣のセルのなかにはないが、結
果としての併合された面が受容可能なしきい値よりも小
さい誤差を有する面、特に小さい面を検出する。近くの面を併合するための擬似コード /* mergeNearbyPlanes - 互いに特に近いが異なる法線を有する面の併合を 試みる。小さな面に対しては法線はノイズを含み得るので、 mergeNearbyPlanes はそれらを併合しようとはしない。しかし２つの 小さな面が近ければ、ときにはそれらは小さな誤差を有する大きな面を 形成するために併合され得る。この関数は反復的に互いに近い面を併合 しようと試みる。それ以上併合が実行され得ないとき、関数は終了する。 この関数は、すべての走査線が処理された後、およびmergeSimilarPlanes の後で呼ばれる。 */ function mergeNearbyPlanes performedMerges = 1; /* objTableはセルの２次元配列である。各セルはセルを通る面および線 のリストを含む。objTableは初期区分化パスの間に計算される（線が 面を形成するために併合されるとき）。 */ objTable = 2D array of cells while performedMerges = C for each plane p /* pを通るすべてのセルにわたってル−プ。これらのセルは線が 面に併合される前に計算される。各セルは２Ｄ座標平面内のセル の中心を表すｘおよびｙ座標を有する。 */ for each cell c that p passes through for y = c.y-1 to c.y+1 for x = c.x-1 to c.x+1 c' = objTable[y][x] for each plane p' in c' newp = p merged with p' if newp has small error remove p from objTable remove p' from objTable add newp to objTable performedMerges = 1 endif endfor /* p' */ endfor /* x */ endfor /* y */ endfor /* c */ endfor /* p */ endwhile end function
う試みはなされない。いったんしきい値よりも小さい誤
差を有する結合された面が見い出されると、その２つの
併合された面が面のリストから、また法線の配列から削
除され、またその結合された面がそのリストに追加さ
れ、またその結合された面のその法線が法線の配列に追
加される。次いで、面のリストのなかの次の面が処理さ
れる。新しい面がリストの端に追加されるので、リスト
の端が到達される時、（新しい面を含めて）面のすべて
は処理され終わっている。面の可能な併合がもはや存在
しないことを確かめるべく、最後の過程で、下の擬似コ
ードのなかに示されているように、近くの面を併合しよ
うと試みる。この処理は、密に近接しており、また測定
誤差に起因して十分に異なる法線を有し、使用される離
散化のレベルに起因して隣のセルのなかにはないが、結
果としての併合された面が受容可能なしきい値よりも小
さい誤差を有する面、特に小さい面を検出する。近くの面を併合するための擬似コード /* mergeNearbyPlanes - 互いに特に近いが異なる法線を有する面の併合を 試みる。小さな面に対しては法線はノイズを含み得るので、 mergeNearbyPlanes はそれらを併合しようとはしない。しかし２つの 小さな面が近ければ、ときにはそれらは小さな誤差を有する大きな面を 形成するために併合され得る。この関数は反復的に互いに近い面を併合 しようと試みる。それ以上併合が実行され得ないとき、関数は終了する。 この関数は、すべての走査線が処理された後、およびmergeSimilarPlanes の後で呼ばれる。 */ function mergeNearbyPlanes performedMerges = 1; /* objTableはセルの２次元配列である。各セルはセルを通る面および線 のリストを含む。objTableは初期区分化パスの間に計算される（線が 面を形成するために併合されるとき）。 */ objTable = 2D array of cells while performedMerges = C for each plane p /* pを通るすべてのセルにわたってル−プ。これらのセルは線が 面に併合される前に計算される。各セルは２Ｄ座標平面内のセル の中心を表すｘおよびｙ座標を有する。 */ for each cell c that p passes through for y = c.y-1 to c.y+1 for x = c.x-1 to c.x+1 c' = objTable[y][x] for each plane p' in c' newp = p merged with p' if newp has small error remove p from objTable remove p' from objTable add newp to objTable performedMerges = 1 endif endfor /* p' */ endfor /* x */ endfor /* y */ endfor /* c */ endfor /* p */ endwhile end function
【００２７】線を面に併合するために使用されるセルの
配列は、類似の法線を有する面が併合され終わった後に
近くの面を併合するのに再び使用される。上に示されて
いるように、近くの面を併合するプロセスは類似の法線
を有する面を併合するプロセスに似ている。相違点は、
隣のセルが、法線の成分の代わりに、線および面を併合
するのに使用される同一の地理的セルを表すことであ
る。プロセスは、もはや併合が生起しなくなるまで、継
続する。
配列は、類似の法線を有する面が併合され終わった後に
近くの面を併合するのに再び使用される。上に示されて
いるように、近くの面を併合するプロセスは類似の法線
を有する面を併合するプロセスに似ている。相違点は、
隣のセルが、法線の成分の代わりに、線および面を併合
するのに使用される同一の地理的セルを表すことであ
る。プロセスは、もはや併合が生起しなくなるまで、継
続する。
【００２８】一例は、距離データから得られたデータ点
の組とトラックの床の抽象的表現５８とを示す図３に与
えられている。大きいほうの点は、上記の擬似コードか
ら発生される計算機コードを実行することにより面に併
合されるデータ点を表す。データ点６０および６２の群
により形成される面の部分は、トラック運転台の頂後縁
および左後縁に相当し、従ってまたトラックの識別に有
用であり得る面に相当する。しかし、群６４のなかのデ
ータ点は大地の部分であり、好ましくは他の面の部分と
して結合されるべきではない。
の組とトラックの床の抽象的表現５８とを示す図３に与
えられている。大きいほうの点は、上記の擬似コードか
ら発生される計算機コードを実行することにより面に併
合されるデータ点を表す。データ点６０および６２の群
により形成される面の部分は、トラック運転台の頂後縁
および左後縁に相当し、従ってまたトラックの識別に有
用であり得る面に相当する。しかし、群６４のなかのデ
ータ点は大地の部分であり、好ましくは他の面の部分と
して結合されるべきではない。
【００２９】ダンプトラックの距離スキャンが図４に示
されている。上記の擬似コードから発生される計算機コ
ードは示されているような面を発生する。これらの面
は、認識されるべき対象物が似て見えるべきモデルを有
する伝統的なソフトウェアであり得る対象物認識ソフト
ウェア３８に与えられる。従来通常のように、このよう
な対象物認識ソフトウェアは、面または面の部分が何を
表すかの仮説を発生し、また検証手順が仮説を検証する
べく実行される。このプロセスは、対象物が認識される
まで、またはその面がそのソフトウェアが認識可能など
の対象物とも合致しないことが決定されるまで、繰り返
される。
されている。上記の擬似コードから発生される計算機コ
ードは示されているような面を発生する。これらの面
は、認識されるべき対象物が似て見えるべきモデルを有
する伝統的なソフトウェアであり得る対象物認識ソフト
ウェア３８に与えられる。従来通常のように、このよう
な対象物認識ソフトウェアは、面または面の部分が何を
表すかの仮説を発生し、また検証手順が仮説を検証する
べく実行される。このプロセスは、対象物が認識される
まで、またはその面がそのソフトウェアが認識可能など
の対象物とも合致しないことが決定されるまで、繰り返
される。
【００３０】本発明の多くの特徴および利点が詳細な説
明から明らかであり、またこうして本発明の一般的な原
理およびスコ−プに属するシステムおよび方法のすべて
のこのような特徴および利点は、特許請求の範囲により
カバーされている。さらに、さまざまな変更が本発明の
開示を参考にして当業者により行われ得るので、以上に
図示かつ説明した厳密な構造および動作に本発明の範囲
を限定することは望まれない。他の適当な変更および均
等なものは本発明の趣旨に属するものとして主張され得
る。
明から明らかであり、またこうして本発明の一般的な原
理およびスコ−プに属するシステムおよび方法のすべて
のこのような特徴および利点は、特許請求の範囲により
カバーされている。さらに、さまざまな変更が本発明の
開示を参考にして当業者により行われ得るので、以上に
図示かつ説明した厳密な構造および動作に本発明の範囲
を限定することは望まれない。他の適当な変更および均
等なものは本発明の趣旨に属するものとして主張され得
る。
【図面の簡単な説明】
【図１】本発明による方法のフロ−チャート。
【図２】本発明による方法を実施するのに使用され得る
システムのブロック図。
システムのブロック図。
【図３】誤った面の検出に終わり得る距離データの一
例。
例。
【図４】上からとられたダンプトラックの距離スキャン
の一例。
の一例。
５８ トラックの床の抽象的表現 ６０、６２ データ点 ６４ データ点の群
Claims (36)
- 【請求項１】 走査線からの距離データを解析するため
の計算機‐読取り可能な媒体上で実行される計算機プロ
グラムにおいて、 もし第１の面しきい値以内の被併合面誤差が得られるな
らば、各走査線のなかの各線区分を最良適合面に併合す
る線区分併合コードと、 もし第２の面しきい値以内の被結合面誤差が得られるな
らば、面の対を併合する面併合コードとを含んでいるこ
とを特徴とする計算機‐読取り可能な媒体上で実行され
る計算機プログラム。 - 【請求項２】 線区分が単一の走査線のなかの距離デー
タにより定められる隣接点の各対の間に形成されてお
り、また前記線区分併合コードがさらに、各線区分を最
良適合面に併合するに先立って、もし線しきい値以内の
併合線区分誤差が得られるならば各走査線のなかの線区
分の対を併合する過程を含んでいることを特徴とする請
求項１記載の計算機‐読取り可能な媒体上で実行される
計算機プログラム。 - 【請求項３】 前記線区分併合コードが、他の走査線に
対する距離データを取得しながら、１つの走査線のなか
の距離データに対して実行されることを特徴とする請求
項２記載の計算機‐読取り可能な媒体上で実行される計
算機プログラム。 - 【請求項４】 前記面併合コードが、第２の面しきい値
以内の結合面誤差を有する結合面の１つを形成するべ
く、各面を、類似の法線を有する面および予め定められ
た距離のなかの面の少なくとも１つと対にすることを特
徴とする請求項１記載の計算機‐読取り可能な媒体上で
実行される計算機プログラム。 - 【請求項５】 前記面併合コードが、 面の各々に対する法線を計算し、 面の識別子を面の各々に対する法線の成分に基づいて二
次元の配列のなかに、各面を配列のただ１つのセルに対
応させて記憶し、 第２の面しきい値以内の結合面誤差を見い出すべく各面
および１つのセルおよびそれに隣接する他のセルのなか
のすべての他の面に対する結合面誤差を計算することに
より類似の法線を有する面を結合することを特徴とする
請求項４記載の計算機‐読取り可能な媒体上で実行され
る計算機プログラム。 - 【請求項６】 線区分の１つを最良適合面に併合するこ
とにより生ぜしめられる併合面誤差が第１の面しきいよ
りも大きい時、前記線区分併合コードがさらに、もしこ
の線区分の１つを以前の走査線のなかの他の線区分と併
合することにより生ぜしめられる最低可能な併合面誤差
が第１の面しきい値以内ならば、そのような以前の走査
線のなかの他の線区分と併合する過程を含んでいること
を特徴とする請求項１記載の計算機‐読取り可能な媒体
上で実行される計算機プログラム。 - 【請求項７】 線区分の各々に対する最良適合面の併合
が第１のしきいよりも大きい併合面誤差を生じ、２つの
線区分が第１の面しきい値以内の併合面誤差で併合され
得なくなるまで、前記線区分併合コードが実行され、 前記面併合コードが、各可能な併合の結合面誤差が第２
の面しきいよりも大きくなるまで実行されることを特徴
とする請求項１記載の計算機‐読取り可能な媒体上で実
行される計算機プログラム。 - 【請求項８】 さらに、各線区分が通過するすべてのセ
ルを識別するべく関心のある空間をセルに分割する空間
分割コードを含んでおり、 前記線区分併合コードが、各線区分を線区分が通過する
セルを通過する面のみと比較することにより最良適合面
を決定することを特徴とする請求項１記載の計算機‐読
取り可能な媒体上で実行される計算機プログラム。 - 【請求項９】 前記線区分併合コードが、各面が通過す
るセルを、面を形成するべく併合される線が通過するセ
ルとして識別することを特徴とする請求項８記載の計算
機‐読取り可能な媒体上で実行される計算機プログラ
ム。 - 【請求項１０】 さらに、仮説発生と、前記面併合コー
ドの完了された処理の結果として結合面から形成される
少なくとも１つの対象物の検証とを行う対象物認識コー
ドを含んでいることを特徴とする請求項１記載の計算機
‐読取り可能な媒体上で実行される計算機プログラム。 - 【請求項１１】 複数の走査線のなかの距離データから
少なくとも１つの対象物を検出する方法において、 複数の走査線のなかの距離データを取得する過程と、 距離データの点のすべての対の間の線区分を定めるべく
各走査線を処理する過程と、 異なる走査線のなかの線区分を結合することにより面を
形成する過程と、 もし第１の面しきい値以内の併合面誤差が得られるなら
ば、各走査線のなかの各線区分を最良適合面に併合する
過程と、 もし第２の面しきい値以内の結合面誤差が得られるなら
ば、結合面を生ぜしめるべく面の対を併合する過程と、 前記の面の併合が完了される時、仮説発生と、前記結合
面から形成される少なくとも１つの対象物の検証とを行
う過程とを含んでいることを特徴とする対象物の検出方
法。 - 【請求項１２】 さらに、各線区分を最良適合面に併合
する以前に、もし線しきい値以内の併合線区分誤差が各
線区分に対して得られるならば、各走査線のなかの線区
分の対を併合する過程を含んでいることを特徴とする請
求項１１記載の方法。 - 【請求項１３】 前記の線区分の対の併合が、線区分の
対の最良適合のために、最良適合の併合線区分誤差が線
しきい値を越えるまで、繰り返して行われることを特徴
とする請求項１２記載の方法。 - 【請求項１４】 前記の面の対の併合が、 面の各々に対する法線を計算し、 面の識別子を、面の各々に対する法線の成分に基づいて
二次元の配列のなかに、 各面を配列のただ１つのセルに対応させて記憶し、 第２の面しきい値以内の結合面誤差を見い出すべく１つ
のセルおよびそれに隣接するセルのなかの各面とすべて
の他の面との結合に対する結合面誤差を計算する過程を
含んでいることを特徴とする請求項１２記載の方法。 - 【請求項１５】 前記の面の対の併合がさらに、第１の
面しきい値以内のすべての走査線のなかの線区分および
隣接するセルのなかの面の対のすべての可能な併合の後
に、もし各々の結合面誤差が第３の面しきい値以内であ
れば、追加的な結合面を形成するべく、予め定められた
距離内の面の対を併合する過程を含んでいることを特徴
とする請求項１４記載の方法。 - 【請求項１６】 さらに、線区分の１つを最良適合面に
併合することにより生ぜしめられる併合面誤差が第１の
しきい値よりも大きい時、もし最低可能な併合面誤差が
第４の面しきい値以内であれば、この線区分の１つを最
低可能な併合面誤差を生ぜしめるべく以前の走査線のな
かの他の線区分と併合することを特徴とする請求項１５
記載の方法。 - 【請求項１７】 さらに、各線区分が通過するすべての
セルを識別するべく関心のある空間をセルに分割する過
程を含んでおり、 前記面との前記線区分の併合が、各線区分を線区分が通
過するセルを通過する面のみと比較することにより最良
適合面を決定することを特徴とする請求項１６記載の方
法。 - 【請求項１８】 前記面との前記線区分の併合が、各面
が通過するセルを、面を形成するべく併合される線が通
過するセルとして識別することを特徴とする請求項１７
記載の方法。 - 【請求項１９】 最初に面を形成するべく行われる線区
分の前記併合が、他の走査線に対する距離データを取得
しながら、１つの走査線のなかの距離データに対して実
行されることを特徴とする請求項１８記載の方法。 - 【請求項２０】 面との線区分の前記併合が、他の走査
線に対する距離データを取得しながら、１つの走査線の
なかの距離データに対して実行されることを特徴とする
請求項１８記載の方法。 - 【請求項２１】 ロボットのロボット視覚装置におい
て、 複数の走査線のなかの距離データを取得するスキャナ‐
サブシステムと、 距離データおよび距離データを解析するための計算機プ
ログラムを記憶し、距離データを解析するための作業領
域を用意するべく、前記スキャナ‐サブシステムに接続
されている少なくとも１つの記憶ユニットと、 各走査線のなかの距離データの点の隣接する対の間の線
区分を定めるべく前記記憶ユニットのなかに記憶されて
いる計算機プログラムを実行することにより距離データ
を解析するため、それぞれ第１の面しきい値以内の第１
の面誤差を有する面を形成するべく線区分を結合するた
め、それぞれ第２の面しきい値以内の第２の面誤差を有
する結合された面を形成するべく面の対を併合するた
め、および対象物情報を生ずるため、前記記憶ユニット
および前記スキャナ‐サブシステムに接続されているプ
ロセッサと、 距離データの解析の結果としての対象物情報をロボット
に与えるべく前記プロセッサ、前記記憶ユニットおよび
ロボットに接続されている入力／出力インタフェースと
を含んでいることを特徴とするロボット視覚装置。 - 【請求項２２】 前記プロセッサが、面を形成するべく
線区分を結合しようと試みる以前に、もし併合線誤差が
線しきい値以内であれば、それぞれ併合線誤差を有する
併合された線区分を形成するべく各走査線のなかの線区
分の対を併合することを特徴とする請求項２１記載のロ
ボット視覚装置。 - 【請求項２３】 前記プロセッサが、線区分の対の併合
により新しい面を形成する以前に、もし併合された面が
第３の面しきい値以内の第３の面誤差を有するならば、
併合された面を形成するべく、併合されていない線区分
の各々および各走査線のなかの併合された線区分を以前
の走査線の処理中に形成された最良適合面と併合するこ
とを特徴とする請求項２２記載のロボット視覚装置。 - 【請求項２４】 併合されていない線区分の１つおよび
現在の走査線のなかの併合された線区分を最良適合面に
併合することにより発生される第３の面誤差が、第３の
面しきい値よりも大きい時、前記プロセッサが、もし最
小の併合面誤差が第１の面しきい値以内であれば、線区
分のすべてのなかで最小の併合面誤差を生ぜしめるべ
く、併合されていない線区分の１つおよび現在の走査線
のなかの併合された線区分を以前の走査線のなかの線区
分の１つと併合することを特徴とする請求項２３記載の
ロボット視覚装置。 - 【請求項２５】 前記プロセッサが、面の各々に対する
法線を計算し、面の識別子を面の各々に対する法線の成
分に基づいて前記記憶ユニットの作業領域のなかの二次
元の配列のなかに、各面を配列のただ１つのセルに対応
させて記憶し、１つのセルおよびそれに隣接するセルの
なかのすべての他の面との各面の各結合に対する第２の
面誤差を計算し、結合された面の１つとして第２の面し
きい値以内の最小の第２の面誤差を有する面の結合を記
憶することを特徴とする請求項２４記載のロボット視覚
装置。 - 【請求項２６】 第３の面しきい値以内の第３の面誤差
を生ぜしめる最良適合面への、併合されていない線区分
および併合された線区分のすべての可能な併合が行わ
れ、第１の面しきい値以内の第１の面誤差を有する新し
い面を形成するべく線区分のすべての可能な併合が行わ
れ、かつ第２の面しきい値以内の第２の面誤差を生ぜし
める隣接するセルのなかの面の結合がすべて行われた後
に、もし各々の追加的な結合された面が第４の面しきい
値以内の第４の面誤差を有するならば、前記プロセッサ
が追加的な結合された面を形成するべく予め定められた
距離内の面の対を併合することを特徴とする請求項２５
記載のロボット視覚装置。 - 【請求項２７】 車両に対する対象物識別システムにお
いて、関心のある領域の複数の走査線のなかの距離デー
タを取得するべく車両に取付けられているスキャナと、 前記スキャナに接続されており、各走査線のなかの距離
データの隣接する点のすべての対の間の線区分を定め、
それぞれ第１の面しきい値以内の第１の面誤差を有する
面を形成するべく線区分を結合し、それぞれ第２の面し
きい値以内の第２の面誤差を有する結合された面を形成
するべく面の対を併合し、また結合された面から関心の
ある領域のなかの対象物を識別するデータ処理システム
とを含んでいることを特徴とする車両に対する対象物識
別システム。 - 【請求項２８】 前記データ処理システムが、もし最小
の併合線誤差が線しきい値以内であれば、それぞれ対の
なかの線区分の少なくとも１つに対して最小の併合線誤
差を有する併合された線区分を形成するべく、各走査線
のなかの線区分の対を併合し、次いで、もし併合された
面が第３の面しきい値以内の第３の面誤差を有するなら
ば、併合された面を形成するべく、併合されていない線
区分の各々および各走査線のなかの併合された線区分を
以前の走査線の処理中に形成された最良適合面に併合す
ることを特徴とする請求項２７記載の車両に対する対象
物識別システム。 - 【請求項２９】 前記データ処理システムが、面の各々
に対する法線を計算し、面の識別子を面の各々に対する
法線の成分に基づいて二次元の配列のなかに記憶し、１
つのセルおよびそれに隣接するセルのなかのすべての他
の面との各面の各結合に対する第２の面誤差を計算し、
また結合された面の１つとして第２の面しきい値以内の
最小の第２の面誤差を有する面の結合を記憶することを
特徴とする請求項２８記載の自立的車両に対する対象物
識別システム。 - 【請求項３０】 線区分と線しきい値以内の併合線誤差
を生ぜしめる併合された線区分とのすべての可能な併合
が行われ、第１の面しきい値以内の第１の面誤差を生ぜ
しめる最良適合面への併合されていない線区分および併
合された線区分のすべての可能な併合が行われ、第２の
面しきい値以内の第２の面誤差を生ぜしめる隣接するセ
ルのなかの面の結合がすべて行われた後に、もし各々の
追加的な結合された面が第４の面しきい値以内の第４の
面誤差を有するならば、前記プロセッサが追加的な結合
された面を形成するべく予め定められた距離内の面の対
を併合することを特徴とする請求項２９記載の車両に対
する対象物識別システム。 - 【請求項３１】 関心のある空間内の像を認識するべく
計算機システムを作動させる方法において、 スキャナから複数の走査線のなかの距離データを受信す
る過程と、 各走査線のなかの距離データの点の隣接する対の間の線
区分を定めるため、それぞれ第１の面しきい値以内の第
１の面誤差を有する面を形成するべく線区分を結合する
ため、それぞれ第２の面しきい値以内の第２の面誤差を
有する結合された面を形成するべく面の対を併合するた
め、結合された面から関心のある空間内の対象物を認識
するため、距離データを処理する過程と、 関心のある空間内の認識された対象物を表すデータを出
力する過程とを含んでいることを特徴とする方法。 - 【請求項３２】 さらに、スキャナから受信された距離
データを記憶する過程と、関心のある空間に対応し、ま
た関心のある空間の対応する部分を通過する各線区分に
対する線区分データと面データとを、面データにより表
される面を形成するべく併合された線区分に対する線区
分データを以前に記憶する二次元のセルのなかに記憶す
る二次元のセルに分けられた記憶領域を定める過程と、 前記処理過程がさらに、もし第３の面しきい値以内の併
合面誤差が得られるならば、各線区分を線区分が通過す
るセルの少なくとも１つを通過する最良適合面に併合す
る過程を含んでいることを特徴とする請求項３１記載の
方法。 - 【請求項３３】 結合された面を形成するべく面の対を
併合する前記処理過程が、 面の識別子を面の各々に対する法線の成分に基づいて二
次元の配列のなかに記憶し、 １つのセルのなかの各面および１つのセルおよびそれに
隣接するセルのなかのすべての他の面に対する第２の面
誤差を計算し、 結合された面の１つとして、第２の面しきい値以内の最
小の第２の面誤差を有する面の結合を記憶し、 もし各々の追加的な結合された面が第４の面しきい値以
内の結合面誤差を有するならば、追加的な結合された面
を形成するべく、予め定められた距離内の面の対を併合
する過程を含んでいることを特徴とする請求項３２記載
の方法。 - 【請求項３４】 スキャナにより与えられる距離データ
から関心のある空間内の対象物を認識するための計算機
システムにおいて、 スキャナから複数の走査線のなかの距離データを受信す
るための手段と、 各走査線のなかの距離データの点の隣接する対の間の線
区分を定めるため、それぞれ第１の面しきい値以内の第
１の面誤差を有する面を形成するべく線区分を結合する
ため、それぞれ第２の面しきい値以内の第２の面誤差を
有する結合された面を形成するべく面の対を併合するた
め、結合された面から関心のある空間内の像を認識する
ため、距離データを処理する手段と、 関心のある空間内の認識された対象物を表すデータを出
力する手段とを含んでいることを特徴とする計算機シス
テム。 - 【請求項３５】 さらに、スキャナから受信された距離
データを記憶するため、および、関心のある空間に対応
し、関心のある空間の対応する部分を通過する各線区分
に対する線区分データと面データとを、面データにより
表される面を形成するべく併合された線区分に対する線
区分データを以前に記憶する二次元のセルのなかに記憶
する二次元のセルに分けられた記憶領域を定めるための
手段を含んでおり、 処理のための前記手段が、もし第３の面しきい値以内の
併合面誤差が得られるならば、各線区分を線区分が通過
するセルの少なくとも１つを通過する最良適合面に併合
するための手段を含んでいることを特徴とする請求項３
４記載の計算機システム。 - 【請求項３６】 処理のための前記手段が、結合された
面を形成するべく面の対を併合するための手段を含んで
おり、この手段が、 面の識別子を面の各々に対する法線の成分に基づいて二
次元の配列のなかに記憶するための手段と、 １つのセルのなかの各面および１つのセルおよびそれに
隣接するセルのなかのすべての他の面に対する第２の面
誤差を計算するための手段と、 結合された面の１つとして、第２の面しきい値以内の最
小の第２の面誤差を有する面の結合を記憶するための手
段と、 もし各々の追加的な結合された面が第４の面しきい値以
内の結合面誤差を有するならば、追加的な結合された面
を形成するべく、予め定められた距離内の面の対を併合
するための手段とを含んでいることを特徴とする請求項
３５記載の計算機システム。
Applications Claiming Priority (2)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| US08/801974 | 1997-02-19 | ||
| US08/801,974 US5978504A (en) | 1997-02-19 | 1997-02-19 | Fast planar segmentation of range data for mobile robots |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| JPH10240944A true JPH10240944A (ja) | 1998-09-11 |
| JP4046835B2 JP4046835B2 (ja) | 2008-02-13 |
Family
ID=25182500
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP05124198A Expired - Fee Related JP4046835B2 (ja) | 1997-02-19 | 1998-02-18 | 可動ロボットに対する距離データの高速面区分化方法 |
Country Status (3)
| Country | Link |
|---|---|
| US (1) | US5978504A (ja) |
| JP (1) | JP4046835B2 (ja) |
| DE (1) | DE19805794A1 (ja) |
Cited By (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JP2011196860A (ja) * | 2010-03-19 | 2011-10-06 | Optex Co Ltd | 距離画像カメラを用いた物体寸法測定方法および物体寸法測定装置 |
Families Citing this family (28)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| DE10148060A1 (de) * | 2001-09-28 | 2003-04-10 | Ibeo Automobile Sensor Gmbh | Verfahren zur Erkennung und Verfolgung von Objekten |
| WO2005088244A1 (ja) * | 2004-03-17 | 2005-09-22 | Sony Corporation | 平面検出装置、平面検出方法、及び平面検出装置を搭載したロボット装置 |
| US6990390B2 (en) * | 2004-05-19 | 2006-01-24 | Caterpillar Inc. | Method and apparatus to detect change in work tool |
| EP1840507B1 (en) * | 2006-03-28 | 2013-07-17 | Riccardo Clarici | Method and integrated system for the digital survey of three-dimensional environments. |
| JP4645601B2 (ja) * | 2007-02-13 | 2011-03-09 | トヨタ自動車株式会社 | 環境地図の生成方法及び移動ロボット |
| DE102008020579B4 (de) * | 2008-04-24 | 2014-07-31 | Fraunhofer-Gesellschaft zur Förderung der angewandten Forschung e.V. | Verfahren zur automatischen Objektlageerkennung und Bewegung einer Vorrichtung relativ zu einem Objekt |
| DE102009009569B4 (de) * | 2009-02-19 | 2019-12-19 | Daimler Ag | Verfahren zum Ermitteln einer Teilfläche eines Bauteils |
| US8340400B2 (en) * | 2009-05-06 | 2012-12-25 | Honeywell International Inc. | Systems and methods for extracting planar features, matching the planar features, and estimating motion from the planar features |
| US20110232719A1 (en) * | 2010-02-17 | 2011-09-29 | Freda Robert M | Solar power system |
| US8199977B2 (en) | 2010-05-07 | 2012-06-12 | Honeywell International Inc. | System and method for extraction of features from a 3-D point cloud |
| US8660365B2 (en) | 2010-07-29 | 2014-02-25 | Honeywell International Inc. | Systems and methods for processing extracted plane features |
| CL2012000933A1 (es) | 2011-04-14 | 2014-07-25 | Harnischfeger Tech Inc | Un metodo y una pala de cable para la generacion de un trayecto ideal, comprende: un motor de oscilacion, un motor de izaje, un motor de avance, un cucharon para excavar y vaciar materiales y, posicionar la pala por medio de la operacion del motor de izaje, el motor de avance y el motor de oscilacion y; un controlador que incluye un modulo generador de un trayecto ideal. |
| US8620533B2 (en) | 2011-08-30 | 2013-12-31 | Harnischfeger Technologies, Inc. | Systems, methods, and devices for controlling a movement of a dipper |
| US8521418B2 (en) | 2011-09-26 | 2013-08-27 | Honeywell International Inc. | Generic surface feature extraction from a set of range data |
| KR101909544B1 (ko) * | 2012-01-19 | 2018-10-18 | 삼성전자주식회사 | 평면 검출 장치 및 방법 |
| US9206587B2 (en) | 2012-03-16 | 2015-12-08 | Harnischfeger Technologies, Inc. | Automated control of dipper swing for a shovel |
| US9153067B2 (en) | 2013-01-21 | 2015-10-06 | Honeywell International Inc. | Systems and methods for 3D data based navigation using descriptor vectors |
| US9123165B2 (en) | 2013-01-21 | 2015-09-01 | Honeywell International Inc. | Systems and methods for 3D data based navigation using a watershed method |
| US20140363073A1 (en) * | 2013-06-11 | 2014-12-11 | Microsoft Corporation | High-performance plane detection with depth camera data |
| US9406138B1 (en) | 2013-09-17 | 2016-08-02 | Bentley Systems, Incorporated | Semi-automatic polyline extraction from point cloud |
| US9412040B2 (en) * | 2013-12-04 | 2016-08-09 | Mitsubishi Electric Research Laboratories, Inc. | Method for extracting planes from 3D point cloud sensor data |
| US9233469B2 (en) | 2014-02-13 | 2016-01-12 | GM Global Technology Operations LLC | Robotic system with 3D box location functionality |
| CA2978389C (en) | 2016-09-08 | 2025-12-09 | Joy Global Surface Mining Inc | System and method for semi-autonomous control of an industrial machine |
| US10515319B2 (en) * | 2016-12-16 | 2019-12-24 | Fetch Robotics, Inc. | System and method for computing a probability that an object comprises a target |
| DE102017201169A1 (de) | 2017-01-25 | 2018-07-26 | Siemens Aktiengesellschaft | Rechnergestütztes Bildverarbeitungsverfahren |
| CN110930411B (zh) * | 2019-11-20 | 2023-04-28 | 浙江光珀智能科技有限公司 | 一种基于深度相机的人体分割方法及系统 |
| CN112171668A (zh) * | 2020-09-21 | 2021-01-05 | 河南颂达信息技术有限公司 | 一种基于人工智能的轨道式机器人防卡死检测方法及装置 |
| DE102021210903A1 (de) | 2021-09-29 | 2023-03-30 | Robert Bosch Gesellschaft mit beschränkter Haftung | Verfahren zum Aufnehmen eines Objekts mittels einer Robotervorrichtung |
Family Cites Families (6)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| FR617296A (fr) * | 1925-10-24 | 1927-02-16 | Instrument de musique producteur de sons continus | |
| US5093869A (en) * | 1990-12-26 | 1992-03-03 | Hughes Aircraft Company | Pattern recognition apparatus utilizing area linking and region growth techniques |
| US5302997A (en) * | 1992-12-28 | 1994-04-12 | Eastman Kodak Company | Composite photometric and range finding element array |
| JP3466661B2 (ja) * | 1993-06-29 | 2003-11-17 | キヤノン株式会社 | 画像処理装置及びその方法 |
| JP2501010B2 (ja) * | 1993-10-25 | 1996-05-29 | インターナショナル・ビジネス・マシーンズ・コーポレイション | 移動ロボットの誘導装置 |
| US5471541A (en) * | 1993-11-16 | 1995-11-28 | National Research Council Of Canada | System for determining the pose of an object which utilizes range profiles and synethic profiles derived from a model |
-
1997
- 1997-02-19 US US08/801,974 patent/US5978504A/en not_active Expired - Lifetime
-
1998
- 1998-02-12 DE DE19805794A patent/DE19805794A1/de not_active Ceased
- 1998-02-18 JP JP05124198A patent/JP4046835B2/ja not_active Expired - Fee Related
Cited By (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JP2011196860A (ja) * | 2010-03-19 | 2011-10-06 | Optex Co Ltd | 距離画像カメラを用いた物体寸法測定方法および物体寸法測定装置 |
Also Published As
| Publication number | Publication date |
|---|---|
| US5978504A (en) | 1999-11-02 |
| DE19805794A1 (de) | 1998-08-20 |
| JP4046835B2 (ja) | 2008-02-13 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| JPH10240944A (ja) | 可動ロボットに対する距離データの高速面区分化方法 | |
| EP2430588B1 (en) | Object recognition method, object recognition apparatus, and autonomous mobile robot | |
| US10859684B1 (en) | Method and system for camera-lidar calibration | |
| CN112432647B (zh) | 车厢的定位方法、装置、系统及计算机可读存储介质 | |
| JP5870273B2 (ja) | 物体検出装置、物体検出方法及びプログラム | |
| CN111612728B (zh) | 一种基于双目rgb图像的3d点云稠密化方法和装置 | |
| CN111142514B (zh) | 一种机器人及其避障方法和装置 | |
| JP2018124787A (ja) | 情報処理装置、データ管理装置、データ管理システム、方法、及びプログラム | |
| JP6021689B2 (ja) | 車両諸元計測処理装置、車両諸元計測方法及びプログラム | |
| CN113793413A (zh) | 三维重建方法、装置、电子设备及存储介质 | |
| CN113592976B (zh) | 地图数据的处理方法、装置、家用电器和可读存储介质 | |
| US11778156B2 (en) | Stereo depth estimation | |
| CN113768419A (zh) | 确定扫地机清扫方向的方法、装置及扫地机 | |
| JP2020173584A (ja) | 物体検出装置 | |
| JPH09212643A (ja) | 三次元物体認識方法及びその装置 | |
| CN114549764B (zh) | 基于无人车的障碍物识别方法、装置、设备及存储介质 | |
| CN119722949B (zh) | 用于三维重建的视点优化方法、装置、设备以及介质 | |
| CN117408935A (zh) | 障碍物检测方法、电子设备和存储介质 | |
| CN119169073A (zh) | 一种锚孔定位方法及系统 | |
| JP4106163B2 (ja) | 障害物検出装置及びその方法 | |
| CN115683109B (zh) | 基于cuda和三维栅格地图的视觉动态障碍物检测方法 | |
| JPH11259658A (ja) | 物体認識方法およびその方法を用いた物体認識装置，車輌認識方法，車輌認識装置 | |
| US20240233336A1 (en) | Machine learning device | |
| JP2004030453A (ja) | ステレオマッチング方法、ステレオマッチングプログラム及びステレオマッチングプログラムを記録したコンピュータ読み取り可能な記録媒体 | |
| JP2006525559A (ja) | ステレオカメラによるオブジェクトの分類のための方法 |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| A621 | Written request for application examination |
Free format text: JAPANESE INTERMEDIATE CODE: A621 Effective date: 20050217 |
|
| RD02 | Notification of acceptance of power of attorney |
Free format text: JAPANESE INTERMEDIATE CODE: A7422 Effective date: 20050217 |
|
| A521 | Request for written amendment filed |
Free format text: JAPANESE INTERMEDIATE CODE: A523 Effective date: 20050316 |
|
| A131 | Notification of reasons for refusal |
Free format text: JAPANESE INTERMEDIATE CODE: A131 Effective date: 20070322 |
|
| A601 | Written request for extension of time |
Free format text: JAPANESE INTERMEDIATE CODE: A601 Effective date: 20070620 |
|
| A602 | Written permission of extension of time |
Free format text: JAPANESE INTERMEDIATE CODE: A602 Effective date: 20070625 |
|
| A601 | Written request for extension of time |
Free format text: JAPANESE INTERMEDIATE CODE: A601 Effective date: 20070720 |
|
| A602 | Written permission of extension of time |
Free format text: JAPANESE INTERMEDIATE CODE: A602 Effective date: 20070725 |
|
| A601 | Written request for extension of time |
Free format text: JAPANESE INTERMEDIATE CODE: A601 Effective date: 20070821 |
|
| A602 | Written permission of extension of time |
Free format text: JAPANESE INTERMEDIATE CODE: A602 Effective date: 20070824 |
|
| A521 | Request for written amendment filed |
Free format text: JAPANESE INTERMEDIATE CODE: A523 Effective date: 20070921 |
|
| TRDD | Decision of grant or rejection written | ||
| A01 | Written decision to grant a patent or to grant a registration (utility model) |
Free format text: JAPANESE INTERMEDIATE CODE: A01 Effective date: 20071023 |
|
| A61 | First payment of annual fees (during grant procedure) |
Free format text: JAPANESE INTERMEDIATE CODE: A61 Effective date: 20071121 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20101130 Year of fee payment: 3 |
|
| R150 | Certificate of patent or registration of utility model |
Free format text: JAPANESE INTERMEDIATE CODE: R150 |
|
| LAPS | Cancellation because of no payment of annual fees |