ターゲットに関する雲状３ｄデータ点群の複数のフレームを記録する方法

专利摘要:
n個のフレームにおける雲状に分布した3Dデータ点群（雲状3Dデータ点群）を記録する方法が開示される。n個のフレームの中からフレームペア（200i，200j）が選択され、各フレーム内の部分空間（702）が規定される。雲状3Dデータ点群が塊状の形状を含んでいる条件を満たす部分空間が特定される。塊状の対象物各々に関する質量中心の位置も決定される。異なるフレームの対応する部分空間における質量中心の位置を利用して、フレームペア同士の間の対応点が決定される。その後、対応点を利用して、各フレームにおける全ての点を記録するために、グローバル並進及び回転ベクトルを全てのnフレームについて計算する。nフレーム中のデータ点は、グローバル並進及び回転ベクトルを用いて変換され、一群のn個の粗く調整されたフレームが得られる。
公开号:JP2011513882A
申请号:JP2010550750
申请日:2009-03-02
公开日:2011-04-28
发明作者:グルヴナ，カティー；ジー ブラスク，スティーヴン；マイネアー，キャサリーン
申请人:ハリス コーポレイションＨａｒｒｉｓ Ｃｏｒｐｏｒａｔｉｏｎ；
IPC主号:G06T15-08

专利说明:

[0001] 本発明は、雲状に分布するデータ点群（point cloud data）を記録又は登録することに関連し、特に、野外においてかなりの障害物の下にある（open and under significant occlusion）ターゲットの雲状に分布するデータ点群を記録又は登録することに関連する。]
背景技術

[0002] 画像処理システムにおいてしばしば生じる問題の1つは、ターゲットが他の対象物によって部分的に不鮮明になることであり、他の対象物はセンサがターゲットに適切に照射することや画像処理を妨げてしまう。例えば、光学系の画像処理システムの場合、木の葉やカモフラージュ用の網（camouflage netting）によってターゲットが遮られ、システムがターゲットを適切に画像処理する機能が制限されてしまう。さらに、ターゲットを遮る対象物はしばしば穴だらけのもの（porous）である。木の葉やカモフラージュ用の網は、そのような穴だらけの障害物の典型例であり、なぜならそれらはしばしば光を通す穴を含んでいるからである。]
[0003] 穴だらけのものの背後に隠れた対象物は、適切な技術を使用することにより検出及び認識できることが、知られている。遮るものを介したターゲットの瞬間観察（instantaneous view）は、ターゲットの表面の一部分しか含んでいないことが認められる。その部分的な領域は、遮るものの穴の領域を通して見えるターゲットの断片をなす。そのような穴の領域を通して見えるターゲットの断片は、画像処理センサの具体的な位置に依存して異なる。しかしながら、いくつもの様々な位置のセンサからのデータを収集することで、データ群を取得することができる。多くの場合、データの集合が分析され、ターゲットについての認識可能な画像が再構築される。通常、これは記録手順又は登録手順（registration process）を含み、その記録手順によって、様々な場所のセンサにより取得された特定のターゲットについての一連の画像フレームが収集され、そのシーケンスから1つの複合画像が構築される。]
[0004] 遮られている対象物の画像を再構築する場合において、3次元（3D）型のセンサシステムを利用することが知られている。3D型センサシステムの一例は、光検出レンジング（Light Detection And Ranging：LIDAR）システムである。LIDAR型3Dセンサシステムは、レーザ光による1つのパルスからの複数のレンジエコー（range echoes）を記録することで、画像フレームを生成する。したがって、LIDARデータの画像フレーム各々は、3次元における座標点の集まり（3D座標点群）を形成し、その3D座標点群は、センサ開口内の複数のレンジエコーに対応する。これらの点はしばしばボクセル（voxel）と言及され、3次元座標空間における格子の値を表す。3D画像処理に使用されるボクセルは、2D画像処理装置において使用されるピクセル（画素）に類似するものである。これらのフレームは、上述したようにターゲットの画像を再構築するように処理される。この場合において、3D座標点群に属する点の各々は、3D的なその状況における実際の表面を表す個々のx、y及びzの値を有することが理解されるべきである。]
発明が解決しようとする課題

[0005] 複数の視点やフレームにより部分的に見えるターゲットに関するLIDAR3Dデータ点群の集まりは、ターゲット判別、状況分析及び変化の検出等の目的に有用である。しかしながら、複数の視点やフレームを、全てのデータを合成した複合画像に組み立てるために、記録プロセスが必要になることが理解されるであろう。記録プロセスは、複数の場面（フレーム）の中から3D座標点群を並べ、3D座標点群により表現されるターゲットの観測可能な断片が、有用な画像とともに合成されるようにする。LIDARデータを用いて、遮られたターゲットの記録及び可視化に関する方法例は、特許文献1に記載されている。しかしながら、その文献で説明されている方法は、時間的に互いに近接したデータフレームを必要とし、したがって、LIDARを使用して非常に長い期間にわたって生じるターゲットの変化を検出するような場合には有用でない。]
課題を解決するための手段

[0006] 一実施例による方法は、
関心のあるターゲットに関する雲状に分布した3次元（3D）データ点群（雲状3Dデータ点群）の複数のフレームを記録する方法であって、
あるシーンに関する雲状3Dデータ点群を含むn個の前記複数のフレームの中から複数のフレームペアを選択し、
前記複数のフレーム中の各フレームの中で複数の部分空間を規定し、
前記複数の部分空間の内、雲状3Dデータ点群が所定の塊状の対象物を含む条件を満たす部分空間（条件充足部分空間）を特定し、
前記塊状の対象物の質量中心の位置を判定し、
異なるフレーム同士における対応する部分空間内の前記質量中心の位置を利用して、フレームペアの間における質量中心対応点を判定し、
前記質量中心対応点を利用して、各フレームの粗い記録のためのグローバル値RjTjを、n個のフレーム全てについて同時に計算するステップ
を有し、前記Rjは、フレームjの各々における全ての点をフレームiに整合させるために必要な回転ベクトルであり、前記Tjは、フレームjにおける全ての点をフレームiに整合させるために必要な並進ベクトルである、方法である。]
図面の簡単な説明

[0007] 異なるセンサによるからのフレーム（又は同じセンサが異なる場所／回転により取得したフレーム）が何故記録を必要とするかについての説明図。
記録プロセスの対称となる雲状3Dデータ点群を含むフレーム群の一例を示す図。
記録プロセスの対称となる雲状3Dデータ点群を含むフレーム群の一例を示す図。
記録プロセスの対称となる雲状3Dデータ点群を含むフレーム群の一例を示す図。
記録プロセスの対称となる雲状3Dデータ点群を含むフレーム群の一例を示す図。
記録プロセスの対称となる雲状3Dデータ点群を含むフレーム群の一例を示す図。
記録プロセスの対称となる雲状3Dデータ点群を含むフレーム群の一例を示す図。
本発明による記録プロセスのフローチャート。
図3の記録プロセスにおける粗い記録ステップの詳細を示すフローチャート。
図3の記録プロセスにおける細かい記録ステップの詳細を示すフローチャート。
選択された構造を特定するための固有値メトリックを示す図。
部分空間の説明図。
ボクセルの説明図。]
[0008] 本発明は、関心のあるターゲットに関する雲状に分布した3次元（3D）データ点群（雲状3Dデータ点群）の複数のフレームを記録又は登録するプロセスに関する。本プロセスは、n個の複数のフレームを取得することから始まり、n個のフレームの各々は、選択された地理的な場所について収集された雲状3Dデータ点群を含んでいる。フレームの組（フレームペア）の数は、n個の複数のフレームの中から決定される。フレームペアは、一連のフレームの中の隣接するフレームのペア及び隣接していないフレームのペアの双方を含む。その後、各フレームの中で部分空間（sub−volume）が規定される。これらの部分空間は、雲状3Dデータ点群の水平スライスにより重複せずに又は排他的に（exclusively）規定される。]
[0009] 本プロセスは、雲状3Dデータ点群が塊状の構造（分布の形状）（blob−like structure）を有する条件を満たす部分空間を特定するステップに続く。条件を満たす部分空間（qualifying sub−volume）を特定するステップにおいて、固有値分析を利用して、特定の部分空間が塊状の構造を有するか否かを判定してもよい。その特定するステップは、有利なことに、部分空間が少なくとも所定の数のデータ点を含んでいるか否かを判定する。]
[0010] その後に、塊状の対象物（オブジェクト）の各々に関する質量中心（重心）の位置が判定される。様々なフレームの対応する部分空間の質量中心の位置を使用して、フレームペア同士の間の質量中心対応点（centroid correspondence point）を決定する。質量中心対応点は、フレームペアの内の第1のフレームの「条件を満たす部分空間」における第1の質量中心の位置を特定することで決定され、第1の質量中心の位置は、フレームペアの内の第2のフレームの「条件を満たす部分空間」における第2の質量中心の位置に最も合致するものである。本発明の一形態によれば、質量中心対応点は、従来のK−Dツリーサーチ法（K−D tree search process）を用いて特定される。]
[0011] その後、質量中心対応点は、nフレーム全てについて、各フレームの粗い記録のためのグローバル値RjTjを同時に計算するのに使用され、Rjは、フレームjの各々における全ての点をフレームiに整合させる（登録する又は記録する）ために必要な回転ベクトルであり、Tjは、フレームjにおける全ての点をフレームiに整合させる（登録する又は記録する）ために必要な並進ベクトルである。本プロセスは、回転及び並進ベクトルを使用して、グローバル値RjTjによりnフレームにおける全てのデータ点を変換し、n個の粗く調整されたフレーム群を提供する。]
[0012] 本発明は、粗く調整されたフレームの全てを別の記録ステップにおいて処理するステップをさらに含み、全てのフレームにおける雲状3Dデータ点群について、より高精度な記録を行う。このステップは、フレームペア各々を構成するフレームの間で対応点（correspondence points）を特定することを含む。対応点は、フレームペアの第1のフレームの「条件を満たす部分空間」におけるデータ点を特定することで見出され、そのデータ点は、フレームペアの第2のフレームの「条件を満たす部分空間」における第2のデータ点の位置に最も合致するものである。例えば、対応点は、従来のK−Dツリーサーチプロセスを用いて特定される。]
[0013] 対応点が見出されると、その対応点を利用して、nフレーム全てについて、各フレームの細かい記録のためのグローバル値RjTjを同時に計算する。再び、Rjは、フレームjの各々における全ての点をフレームiに整合させる（登録する又は記録する）ために必要な回転ベクトルであり、Tjは、フレームjにおける全ての点をフレームiに整合させる（登録する又は記録する）ために必要な並進ベクトルである。その後、nフレームの全てのデータ点が、グローバル値RjTjを用いて変換され、n個の細かく調整されたフレーム群を提供する。対応点を特定し、各フレームの細かい記録のためにグローバル値RjTjを同時に計算し、データ点を変換するステップを、少なくとも1つの最適化パラメータが満たされるまで反復することを、本方法はさらに含む。]
[0014] 雲状に分布する3次元データ点の複数のフレームを記録する発明方法を理解するために、先ず、そのようなデータの性質及び従来の取得方法を考察することが有用である。図1は、物理的な地域108の上空に或る距離を隔てて位置する2つの異なるセンサ102−i、102−jを示す。センサ102−i、102−jは、同じタイプであるが物理的には異なるセンサでもよいし、あるいは2つの異なる時間における1つの同じセンサを表現していてもよい。センサ102−i、102−jの各々は、物理的な領域108を表す雲状に分布した3次元データ点群による少なくとも1つのフレームを取得する。概して、「雲状に分布したデータ点群（point cloud data）」は、3次元空間における対象物を特定するディジタル化されたデータを示す。]
[0015] 本発明の説明の便宜上、物理的な場所108は、地表面上の地理的な場所として説明する。しかしながら、本願において説明される方法は、何らかの画像処理システムにおいて画像処理される任意のオブジェクト（対象）を表現する複数のフレームを含むシーケンスから、データを記録する場合にも適用可能であることが、当業者に理解されるであろう。例えば、そのような画像処理システムは、ロボット製造プロセス及び宇宙開発システムを含む。]
[0016] 雲状に分布する3Dデータ点群（雲状3Dデータ点群）を生成するのに使用可能な多種多様なセンサ、測定装置及び画像処理システムが存在することを、当業者は認めるであろう。本発明は、これらの様々な画像処理システムの内の何れかから取得された雲状3Dデータ点群を記録するために使用可能である。]
[0017] 雲状3Dデータ点群の1つ以上のフレームを生成する3D画像処理システムの一例は、従来のLIDAR画像処理システムである。概して、そのようなLIDARシステムは、高エネルギレーザ、光検出器（光ディテクタ）及びタイミング回路を使用して、ターゲットまでの距離を判定している。従来のLIDARシステムの場合、1つ以上のレーザパルスを使用して、シーン（場所）に照射する。各々のパルスは、ディテクタアレイとともに動作するタイミング回路にトリガを与える。概して、このシステムは、レーザからターゲットに至り、その後にディテクタアレイに戻って来る往復経路（ラウンドトリップ経路）を伝搬するパルスの画素各々について時間を測定する。ターゲットからの反射光がディテクタアレイにより検出され、そのラウンドトリップ時間が測定され、ターゲットの位置までの距離を判定する。計算される範囲ないし距離の情報は、ターゲットを構成する複数の点について得られるので、雲状に分布した3Dデータ点群を形成する。雲状に分布した3Dデータ点群は、対象物の3D形状を得るために使用される。]
[0018] 図1において、センサ102−i、102−jにより画像処理される物理的な空間108は、例えば車両のような1つ以上の対象物、目標物、オブジェクト又はターゲットを含む。しかしながら、センサ102−i、102−jとターゲットとの間の見通し線は、障害物（occluding materials）により部分的に遮られてしまうかもしれない。障害物は、関心のあるターゲットの雲状3Dデータ点群をセンサが取得することを遮る任意の種類のものを含む。LIDARシステムの場合、障害物は、樹木の葉のような自然界に存在するものや、カモフラージュ用の網のような人工のものを含む。]
[0019] 多くの場合、障害物106は、その性質上、穴が多い何らかのもの（porous）であることが認められる。したがって、センサ102−i、102−jは、障害物の穴の領域から見える（visible）ターゲットの断片を検出することができる。そのような穴の領域を通して見えるターゲットの断片は、センサ102−i、102−jの具体的な場所に依存して異なる。しかしながら、いくつもの異なるセンサの位置からのデータを収集することで、データの集まりを得ることができる。多くの場合、そのデータの集まりは分析され、認識可能なターゲットの画像を再構築する。]
[0020] 図2Aは、雲状に分布する3Dデータ点群200−iを含むフレームの一例を示し、これは図1のセンサ102−iにより取得されたものである。同様に、図2Bは、雲状に分布する3Dデータ点群200−jを含むフレームの一例を示し、これは図1のセンサ102−jにより取得されたものである。簡明化のため、図2A及び2Bにおける雲状3Dデータ点群のフレームは、それぞれ「フレームi」及び「フレームj」として言及される。雲状3Dデータ点群200−i、200−jの各々は、ある空間（体積）を占めるデータ点群の場所を規定し、それらの各々は、x、y、z軸における座標により3次元空間内で規定されることが、図2A及び2Bから分かる。センサ102−i、102−jが実行する測定により、データ点各々のx、y、z座標が規定される。]
[0021] 図1において、センサ102−i、102−jはそれぞれ異なる配置及び向きを有することがわかる。センサ102−i、102−jの配置及び向きは、センサの姿勢又はポーズとしてしばしば言及されることを、当業者は認めるであろう。例えば、センサ102−iは、「フレームiを構成する雲状3Dデータ点群200−iが取得された時点のポーズパラメータによって規定される姿勢を有する」、と言うことができる。]
[0022] 上記の説明により、フレームi、jにそれぞれ含まれる雲状3Dデータ点群200−i、200−jは、中心が異なるセンサの座標系に基づいていることが分かる。したがって、センサ102−i、102−jにより生成されるフレームi、jの雲状3Dデータ点群200は、異なる座標系に関して規定されている。これらの異なる座標系は、必要に応じて、空間的に回転及び並進（平行移動）させる必要があり、その後に、2つ以上のフレームからの雲状3Dデータ点群が共通する座標系において適切に表現されることを、当業者は認めるであろう。この場合において、本願により説明される記録プロセスの目的の1つは、2つ以上のフレームからの雲状3Dデータ点群を利用して、一連のフレーム中の各フレームについて必要なデータ点の相対的な回転及び並進を判定することであることが、理解されるべきである。]
[0023] フレームi及びフレームjにおける雲状3Dデータ点群の少なくとも一部が、共通の対象物（すなわち、同じ物理的な又は地理的な領域）に関して取得された場合にのみ、一連の雲状3Dデータ点群が記録又は登録されることにも留意を要する。したがって、フレームi及びjの少なくとも一部分は、一般に、共通する地理的領域（場所）からのデータを含む。例えば、各フレームの少なくとも約1／3の共通部分が、共通する地理的領域のデータを含んでいることが一般的に好ましい。さらに、フレームi及びjに含まれているデータは、時間的に互いに短時間の内に取得されたものであることを要しないことが、理解されるべきである。本願により説明される記録プロセスは、何週間も、何ヶ月もあるいは何年にもわたって取得されたフレームｉ及びjに含まれる雲状3Dデータ点群についても使用可能である。]
[0024] 図3を参照しながら、雲状3Dデータ点群の複数のフレームi、jを記録又は登録するプロセスの概要を説明する。本プロセスはステップ302から始まる。ステップ302において、n個のフレーム群をなす雲状3Dデータ点群200−i，．．．200−nを取得する。このステップは、図1及び図2を参照しながら説明した方法を用いて実行される。n個のフレーム各々の雲状3Dデータ点群を取得するのに使用される具体的な方法が何であるかは重要でない。必要なことは、結果のフレームが、空間内の複数の点各々の場所を規定するデータを含んでいること、及び各々の点は、x、y、z軸に関する座標の組によって規定されることである。通常、センサは、収集期間（収集インターバル）の間に、3D測定値を含む連続的な25ないし40個のフレームを収集する。これら全てのフレームからのデータは、図3に示されるプロセスを用いて整合させられる、記録又は登録される。]
[0025] 本プロセスはステップ304に続き、多数のフレームペアが選択される。この場合において、本願において使用される「ペア又は組」という用語は、フレーム1及びフレーム2のように隣接しているフレームに言及するとは限らない。むしろ、ペアは、隣接するフレーム及び隣接していないフレーム1，2；1，3；1，4；2，3；2，4；2，5等を含んでもよい。フレームペアの数は、記録プロセスにおいて、個々のフレーム各々に対して、どの程度の数のフレームペアが分析されるかを決定する。例えば、フレームペアの数が2に選ばれた場合、フレームペアは、1，2；1，3； 2，3；2，4； 3，4；3，5等となる。フレームペアの数が3に選ばれた場合、フレームペアは、1，2；1，3；1，4； 2，3；2，4；2，5； 3，4；3，5；3，6等となる。]
[0026] 特定の地理的領域を調査する特定の指令に関して、連続的に生成される一群のフレームは、関心のあるターゲットが相当に遮られているような場合に特に有用である。なぜなら、連続的に収集された雲状3Dデータ点群のフレームは、フレーム毎にかなりの量の有意義な内容（common sense content）を含む傾向があるからである。一般に、これは、雲状3Dデータ点群のフレームが速やかに収集されかつフレーム同士の間に遅延が僅かしかない場合である。フレーム同士の間でかなりの重複を含めるのに必要な正確なフレーム収集速度は、測定が行われるプラットフォームの速度に依存する。しかしながら、本願において説明される方法は、雲状3Dデータ点群の複数のフレームが連続的には取得されていない場合にも使用可能であることが、理解されるべきである。その場合、2つのフレームの間でかなりの量の有意義な内容を含むフレームペアを選択することで、記録用の雲状3Dデータ点群のフレームペアが選択される。例えば、第1のフレームのシーン（場面）の内容の少なくとも約25％が第2のフレームと共通していた場合、第1のフレームと第2のフレームはフレームペアとして選択することができる。]
[0027] 本プロセスはステップ306に続き、ノイズフィルタリングが実行され、雲状3Dデータ点群のn個のフレーム各々に含まれているノイズを削減する。この場合において、適切な如何なるノイズフィルタが使用されてもよい。例えば、一実施例において、データ点に関して非常にまばらにしか存在していないボクセルに含まれているデータを削除するノイズフィルタが使用されてもよい。そのようなノイズフィルタの具体例は、特許文献2に記載されている。しかしながら、本発明はそのような例に限定されない。]
[0028] 本方法はステップ308に続き、フレームの各々について、そこに含まれているデータの水平スライスを選択する。この様子は図2C、2Dに示されており、フレームi、jにおける水平スライス203を形成する平面201、202が示されている。有利なことに、関心のあるターゲットを含んでいると考えられ、かつ関心のない無関係なデータを含まない空間として、水平スライス203が選択される。本発明の一実施例において、フレーム1ないしnの各々の水平スライス203は、ある場所を含むように選択され、その場所は、地表面より僅かに上にあり、地面から所定の高度又は高さに及んでいるものである。例えば、地面からz＝0．5メートルないし地面からz＝6．5メートルの範囲内のデータを含む水平スライス203は、地上のほとんどの種類の車両その他の対象物を包含するのに通常適している。しかしながら、本発明はこのような場合に限定されないことが理解されるべきである。別の状況において、地面に対して高い場所から始まる水平スライスを選択し、シーン内の高い対象物（例えば木の幹）のみに基づいて、記録が実行されるようにすることが望ましい場合もある。木々の影により遮られている対象物の場合、地面から、低い木の枝（tree limbs）より若干低いところに伸びる水平スライス203を選択することが望ましい。]
[0029] ステップ310において、各フレームの水平スライス203は、複数の部分空間（sub−volume）702に分割される。このステップは図7を参照することで良く理解できる。部分空間702は、雲状3Dデータ点群の各フレームにより表現される空間全体と比較して、かなり小さい体積を占めるように、個々の部分空間702が選択される。例えば、一実施例において、各々のフレームを形成する空間は、16個の部分空間に分割される。各々の部分空間702の具体的なサイズ（大きさ）は、シーン（場面）に登場するオブジェクト（対象物）について予想されるサイズに基づいて選択される。しかしながら、部分空間の各々は、フレームに含まれていると予想される塊状のオブジェクトを含む程度に十分に大きなサイズを有することが望ましい。塊状のオブジェクトの概念については、後述される。ただし、本発明は何らかのサイズの部分空間に限定されるものではない。図8を参照するに、部分空間702の各々が、さらにボクセルに分割されていることが分かる。ボクセルはシーンデータの立方体（単位立方体）である。例えば、1つのボクセルは、（0．2m）3のサイズを有する。]
[0030] 図3を再び参照するに、本プロセスはステップ312に続く。ステップ312において、部分空間の各々が評価され、校正プロセスに使用するのに最も相応しいものを特定する。この評価プロセスは2つのテスト（検査、試験）を含む。第1のテストは、特定の部分空間が十分に多くのデータ点を含んでいるか否かについての検査を含む。所定数のデータ点を含む任意の部分空間は、このテストに合格する。例えば、特定の部分空間内に存在する実際のデータ点の数が、部分空間内に存在することが可能な総データ点数の少なくとも1／10であるか否かの確認を、このテストは含んでもよいが、本発明はそのような場合に限定ではない。このプロセスは、データ点を非常にまばらにしか含んでいないデータ点が、以後の記録ステップに使用されないようにすることを保証する。]
[0031] ステップ312において行われる第2のテストは、特定の部分空間が塊状の雲状データ点の構造又は形状を含んでいるか否かの判別である。概して、ボクセルが十分に多い数のデータ点を含む条件を満たし、かつ塊状の構造を含んでいた場合、その特定の部分空間は、「条件を満たす部分空間（qualifying sub−volume）」であり、以後の記録ステップに使用される。]
[0032] 以後のステップを説明する前に、塊又は塊状（blob−like）の意味を詳細に説明する。塊状にかつ雲状に分布するデータ点は、3次元のボール（球）又は一定の形状を有しない塊として理解できる。したがって、本願において言及される塊状の雲状データ点群は、直線、曲線又は平面をなす雲状データ点群を含むものではない。雲状データ点群が塊状の構造（形状）を有するか否かを判別する際に、適切な如何なる方法が使用されてもよい。しかしながら、本願の場合、雲状データ点群に対して固有値解析（Eigen analysis）を行うことが好ましい。]
[0033] 固有値解析は、対称的なマトリクス(行列)により表現されるデータ構造のサマリ（概要、特徴）をもたらすことは、当該技術分野において既知である。この場合において、一群の固有値各々を計算するのに使用される対称的なマトリクスは、部分空間各々に含まれる雲状に分布するデータ点群（雲状データ点群）であるように選択される。部分空間各々における雲状データ点の各々は、x、y、zの値により指定される。したがって、データのまわりに楕円（楕円体）を描くことができ、その楕円は、3つの値（すなわち、λ1、λ2、λ3）により規定することができる。第1の固有値は常に最大であり、第3の固有値は常に最小であるとする。固有値λ1、λ2、λ3の各々は、0及び1．0の間の値をとる。固有値を計算する方法及び方式自体は当該技術分野において既知である。したがって、それらを詳細には説明しない。]
[0034] 本発明において、固有値λ1、λ2、λ3は、一連のメトリックを計算するのに使用され、それらのメトリックは、部分空間内の雲状3Dデータ点群により形成される形状の指標を与える際に有用である。特に、メトリックM1、M2、M3が固有値λ1、λ2、λ3を用いて次のように計算される：



図6のテーブル（表）は、計算される3つのメトリックM1、M2、M3を示し、それらをどのように利用して直線、平面、曲線及び塊状のオブジェクトを判別するかを示す。上述したように、塊状の雲状3Dデータ点群は、3次元的な球形（ボール）又は不定形状の塊であると理解される。そのような塊状の雲状3Dデータ点群は、木の幹、岩又は他の大きな静止物に関連付けられることがしばしばある。したがって、本願において塊状の雲状3Dデータ点群は、直線、曲線又は平面をなすにすぎない雲状3Dデータ点群を含まない。]
[0035] M1、M2、M3の値が全て1．0に近似的に等しい場合、これは、その部分空間が、平面や直線状のデータ点群ではなく、塊状のデータ点群を含んでいることを示す。例えば、特定の部分空間についてのM1、M2、M3の値が全て0．7より大きかった場合、その部分空間は塊状のデータ点群の構造を有すると結論づけることができる。さらに、本発明は、塊状の特徴を有する雲状3Dデータ点群を規定する際に、M1、M2、M3の何らかの値に限定されるものではないことを、当業者は認めるであろう。さらに、本発明は説明した特定のメトリックに限定されないことも、当業者は直ちに認めるであろう。むしろそうではなく、適切な任意のメトリックが使用可能である。ただし、それらのメトリックは、塊状のデータ点群が、直線、曲線、平面を規定するデータ点群と区別できるものとする。]
[0036] 図3を再び参照するに、図6における固有値メトリックをステップ312において使用し、細かい記録プロセスに最も有用であるフレームi．．．nの「条件を満たす部分空間」を特定する。本願において使用されているように、「条件を満たす部分空間（qualifying
sub−volume）」は、所定数のデータ点を含み（まばらにしかデータが存在していない部分空間を避けるためである）、かつ塊状の雲状3Dデータ点群を含むものである。本プロセスは複数のフレームペアについてステップ312において行われ、その複数のフレームペアは、一群のフレームにより表現される隣接するフレームペア及び隣接していないフレームペアの双方を含む。例えば、フレームペアは、フレーム1，2；1，3；1，4；2，3；2，4；2，5等を含むが、この場合において、連続的な番号のフレームは収集された一連のフレームの中で隣接したものであり、連続的でない（不連続な）番号のフレームは収集された一連のフレームの中で隣接していないものである。]
[0037] ステップ312における「条件を満たす部分空間」を特定することに続いて、本プロセスはステップ400に進む。ステップ400は粗い記録ステップ（coarse registration step）であり、ある方法を全てのフレームに同時に使用することで、フレーム1．．．nのデータについての粗い記録（登録）が行われる。より具体的には、ステップ400は、雲状3Dデータ点群のnフレーム全てについて、グローバル値RjTjを同時に計算することを含み、Rjは、フレームjの各々における全ての点をフレームiに整合させる（登録する又は記録する）ために必要な回転ベクトルであり、Tjは、フレームjにおける全ての点をフレームiに整合させる（登録する又は記録する）ために必要な並進ベクトルである。]
[0038] その後、プロセスはステップ500に続き、ある方法を全てのフレームに同時に使用することで、フレーム1．．．nのデータについての細かい記録（登録）が行われる。より具体的には、ステップ500は、雲状3Dデータ点群のnフレーム全てについて、グローバル値RjTjを同時に計算することを含み、Rjは、フレームjの各々における全ての点をフレームiに整合させる（登録する又は記録する）ために必要な回転ベクトルであり、Tjは、フレームjにおける全ての点をフレームiに整合させる（登録する又は記録する）ために必要な並進ベクトルである。]
[0039] 重要なことに、ステップ400における粗い記録ステップは、フレームペアにおける塊状のオブジェクトに関する質量中心のペアを含む比較的粗い調整法に基づいている。本願において使用されているように、質量中心（centroid）という用語は、塊状のオブジェクト（対象物）の近似的な質量中心をも含む概念である。これに対して、ステップ500における細かい記録ステップは、より高精度な方法であり、フレームペアにおける実際のデータ点の滞欧するペアを特定することに基づいている。]
[0040] ステップ400及び500において計算された各フレームのRj及びTjの計算値は、雲状3Dデータ点群を、各フレームから共通の座標系へ変換するのに使用される。例えば、共通の座標系は、特定の基準フレームの座標系でもよい。この段階において、一連のシーケンスに含まれる全てのフレームについての記録プロセスが完了する。その後、本プロセスはステップ600において終了し、一連のシーケンスから集約されたデータが表示可能になる。粗い記録ステップ及び細かい記録ステップの各々について、以下、詳細に説明する。
＜粗い記録＞
粗い記録ステップ400は、図4のフローチャートにより詳細に示されている。図4に示されているように、プロセスはステップ401に続き、条件を満たす部分空間の各々に含まれている塊状のオブジェクト各々の質量中心が特定される。ステップ312において特定した部分空間各々における塊状のオブジェクトの質量中心は、ステップ304において選択されたフレーム同士の間の対応点（correspondence points）を決定するために使用される。]
[0041] 本願において使用されているように、「対応点」という用語は、フレームiの部分空間内で表現される現実世界における特定の物理的な場所であり、フレームjの部分空間内で表現される同じ物理的な場所に近似的に等しい。本発明の場合、このプロセスは、（1）フレームiにおける特定の部分空間に含まれている塊状構造の質量中心の位置（質量中心位置）を見出すこと及び（2）フレームiにおける塊状構造の質量中心位置に最も合致するフレームjの対応する部分空間における塊状構造の質量中心位置を判定することにより実行される。言い換えれば、あるフレーム（例えば、フレームj）の「条件を満たす部分空間」における質量中心位置は、別のフレーム（例えば、フレームi）の「条件を満たす部分空間」における質量中心位置に最も近接して位置している。「条件を満たす部分空間」の質量中心位置を利用して、フレームペア同士の間の対応点を見出す。フレームペア同士の間の質量中心位置の対応関係は、K−Dツリーサーチ法を用いて見出すことができる。当該技術分野において既知であるこの方法は、最近接サーチ法（nearest neighbor search method）として言及されることもある。]
[0042] 重要なことに、対応点を特定する先行するプロセスにおいて、対応する部分空間が対応する塊状オブジェクトを実際に含んでいることを仮定している。この場合において、雲状3Dデータ点群の各フレームを収集するプロセスは、一般に、そのような雲状3Dデータ点群を収集するのに使用されたセンサの位置及び高度に関する情報も収集することを含むことが、理解されるべきである。この位置及び高度の情報は、有利なことに、フレームペアを構成する2つの別個のフレームにおける対応する部分空間同士が、同じシーンの内容を実質的に含むように、粗く合わせられていることを保証するために使用される。言い換えれば、これは、フレームペアを構成する2つのフレームにおける対応する部分空間は、地上の同じ物理的な場所を含むシーンの内容を含んでいることを意味する。対応する部分空間同士が対応する塊状オブジェクトを実際に含んでいることをさらに保証するため、有利なことに、選択的に制御される回転可能なレンズ（selectively controlled pivoting lens）を有するセンサを利用して、雲状3Dデータ点群を収集することが好ましい。センサが搭載されている車両の位置が、シーンに接近したり離れたりしたとしても、特定の物理的な場所に向かう方向を維持するように、回転可能なレンズは自動的に制御されるようにすることができる。]
[0043] 塊状オブジェクトの質量中心に基づいて、説明した対応点が各フレームペアについて決定されると、本プロセスはステップ404に続く。ステップ404において、同時に使用される方法により、全てのフレームについてグローバル変換（RiTi）の値が計算される。ステップ400は、雲状3Dデータ点群のnフレーム全てについて、RjTjのグローバル値を同時に計算することを含む。Rjは、フレームjの各々における全ての点をフレームiに整合させる（登録する又は記録する）ために必要な回転ベクトルであり、Tjは、フレームjにおける全ての点をフレームiに整合させる（登録する又は記録する）ために必要な並進ベクトルである。]
[0044] 上述したグローバル変換プロセスを実行するのに使用可能な様々な従来の方法が存在することを、当業者は認めるであろう。この場合において、そのような任意の方法が本発明に使用可能であることが、理解されるべきである。そのような方法は、各フレーム対における質量中心の位置同士の間の位置関係を最も良く記述（説明）するx、y、z軸方向の並進法（変換法）を見出すことを含む。そのような方法自体は当該技術分野において既知である。好適実施例の場合、全てのフレームのグローバル変換を同時に発見するために使用可能な数学的方法の1つは、非特許文献1に記載されており、その開示内容は本願のリファレンスに組み入れられる。重要なことに、この方法は、申し分のない結果を直接的にもたらし、さらなる最適化や反復を要しないことが判明した。最後に、ステップ406において、ステップ404において計算したようなRiTiの値を利用して、全てのフレームに含まれる全てのデータ点が変換される。その後、本プロセスはステップ500に関して説明された細かい記録ステップに続く。]
[0045] ＜細かい記録＞
雲状3Dデータ点群の各フレームについてステップ400において行われた粗い調整は、各々のフレームの対応する部分空間が、シーンに含まれている対応する構造又はオブジェクトに関するデータ点を含むことを予想（期待）するには十分である。本願において使用されているように、対応する部分空間は、2つの異なるフレームに関し、共通する相対的な位置を有するものである。ステップ400に関して上述した粗い記録プロセスと同様に、ステップ500における細かい記録プロセスは、一度に全てのフレームについて記録する同時の方法を使用する。ステップ500における細かい記録プロセスについては、図5のフローチャートにより詳細に説明する。]
[0046] より具体的には、ステップ500において、ステップ400の粗い記録ステップからの粗く調整されたフレームペア全てが同時に処理され、より細かい記録が行われる。ステップ500は、雲状3Dデータ点群のnフレーム全てについて、グローバル値RjTjを同時に計算することを含み、Rjは、フレームjの各々における全ての点をフレームiに整合させる（登録する又は記録する）ために必要な回転ベクトルであり、Tjは、フレームjにおける全ての点をフレームiに整合させる（登録する又は記録する）ために必要な並進ベクトルである。ステップ500における細かい記録プロセスは、フレームペアにおける実際のデータ点の体うするペアに基づいている。これはステップ400の粗い記録ステップの場合と異なり、ステップ400の場合、フレームペアにおける塊状オブジェクトの質量中心の対応するペアを含む高精度ではない方法に基づいている。]
[0047] 特に、上記の粗い記録ステップが完了した後に、雲状3Dデータ点群のフレームペアについて細かい記録プロセスを実行するのに使用可能な様々な従来の方法が存在することを、当業者は認めるであろう。例えば、グローバル最適化ルーチンを含む簡易な反復法が使用されてもよい。そのような方法は、粗い記録ステップが完了した後に、フレームi及びフレームjにより形成されるフレームペアにおけるデータ点同士の間の位置関係を最良に記述（説明）するx、y、z軸方向の変換を見出すことを含む。この場合において、フレームペアにおける点同士の対応関係を記述（説明）するデータ点同士の様々な位置変換を見出すこと、及び位置変換の特定の反復において最も近い点を見出すことを、最適化ルーチンにおいて反復してもよい。]
[0048] 細かい記録プロセス500において、上記の粗い記録ステップにおいて使用するために選択したものと同じ「条件を満たす部分空間」が使用される。ステップ502において、データセット内のフレームペア各々について、「条件を満たす部分空間」の内の対応するものの中に含まれているデータ点の対応ペアを特定するステップに、本プロセスは続く。このステップは、あるフレーム（例えば、フレームj）の「条件を満たす部分空間」におけるデータ点を見出すことで行われ、そのデータ点は、別のフレーム（例えば、フレームi）の「条件を満たす部分空間」におけるデータ点の位置又は配置に最も合致するものである。。「条件を満たす部分空間」における未処理データ点を利用して、フレームペア同士の間の対応関係を見出す。フレームペア同士の間の点の対応関係は、K−Dツリーサーチ法（K−D tree search method）を用いて見出すことができる。当該技術分野において既知のこの方法は、最近接探索法（nearest neighbor search method）と言及されることもある。]
[0049] ステップ504、506において、最適化ルーチンは、全てのフレームに関連する雲状3Dデータ点群について同時に実行される。最適化ルーチンは、ステップ504において、データセット中の全ての点及び全てのフレームに適用可能なグローバルローテーション、スケール及び変換マトリクス（回転、スケーリング及び変換のパラメータ）を決定することから始まる。この決定は、非特許文献1に記載の方法を用いて実行することができる。したがって、ローカルなフレーム毎の変換ではなく、グローバルな変換が実行される。]
[0050] 最適化ルーチンは、ステップ506において、1つ以上の最適化のテスト（検査、試験）を実行する。本発明の一実施例によれば、ステップ506において、3つのテストが実行され、それらは、（1）エラーによる変化が、ある所定値未満であるか否か、（2）実際のエラーが、ある所定値未満であるか否か、及び（3）図5の最適化プロセスが、少なくともN回反復されたか否かである。これらのテストに対する答えが「No」（いいえ）であった場合、本プロセスはステップ508に続く。ステップ508では、全てのフレームの全ての点が、ステップ504において計算されたRiTiの値により変換される。その後、本プロセスはさらに反復するためにステップ502に戻る。]
[0051] あるいは、ステップ506における何れかのテストに対する答えが「Yes」（はい）であった場合、本プロセスはステップ510に続き、全てのフレームがステップ504において計算されたRiTiの値により変換される。この段階において、全てのフレームからのデータについて、目視用ディスプレイにアップロードする準備が整う。その後、本プロセスはステップ600において終了する。]
[0052] 図5における最適化ルーチンは、各フレームjについての回転及び並進ベクトルRiTiを見出すために使用され、そのRiTiは、ステップ502において特定されたデータ点の対応するペア全てについて、エラーを同時に最小にするものである。回転及び並進ベクトルは、各フレームjの全ての点について使用され、フレームiとともに合成され、複合画像を形成する。このような目的に使用可能な当該技術分野で既知の様々な最適化ルーチンは幾つも存在する。例えば、最適化ルーチンは、同時摂動確率近似（simultaneous perturbation stochastic approximation：SPSA）を含んでもよい。使用可能な他の最適化方法は、ネルダーメッドシンプレックス法（Nelder Mead Simplex method）、最小二乗適合法（Least Squares Fit method）及び準ニュートン法（Quasi Newton method）を含む。さらに、SPSA法は、上記の最適化を実行するのに好ましい。これらの最適化法の各々は、当該技術分野において既知であり、したがって詳細には説明しない。]
[0053] 本発明はデータ処理システム又はコンピュータプログラム（又はプログラム製品）として実現されてもよいことを、当業者はさらに認めるであろう。したがって、本発明は、完全にハードウェアとして実現されてもよいし、完全にソフトウェアとして実現されてもよし、あるいはソフトウェア及びハードウェアの組み合わせとして実現されてもよい。本発明は、コンピュータ読取可能案プログラムコードが記憶されているコンピュータ読取可能な記憶媒体におけるコンピュータプログラム又はプログラム製品の形態をとってもよい。適切な如何なるコンピュータ読取可能な媒体が使用されてもよく、例えば、RAM、ディスクドライバ、CD−ROM、ハードディスク、磁気ストレージ装置でもよいし、及び／又は他の任意の形式のプログラムバルクストレージでもよい。]
[0054] 本発明を担うプログラムコードは、ジャバ（Java）（登録商標）、C＋＋又は他のオブジェクト指向プログラミング言語により書かれたものでもよい。しかしながら、コンピュータプログラムコードは、従来の処理プログラム言語（例えば、Cプログラミング言語）により書かれたものでもよい。コンピュータプログラムコードは、目視指向（visually oriented）プログラミング言語（例えば、VisualBasic）により書かれたものでもよい。]
実施例

[0055] 本願において開示及び権利請求される装置、方法及びアルゴリズムの全ては、本開示にに関し、過度の実験（undue experimentation）を要することなく作成及び実行可能である。本発明は好適実施例の観点から説明されてきたが、本発明による概念、精神及び範囲から逸脱することなく、装置、方法及び方法における一連のステップに対して変形が施されてもよいことは、当業者にとって明らかであろう。より具体的には、同一の又は同様な結果を得るために、何らかの構成要件が付加されてもよいし、組み合わされてもよいし、あるいは本願で説明した構成要件を置換してもよいことは、明らかであろう。当業者に明らかなそのような類似する置換及び変形は、特許請求の範囲によって規定される本発明の精神、範囲及び概念の範疇にある。]
[0056] 米国特許出願公開第2005／0243323号明細書
米国特許第7，304，645号明細書]
先行技術

[0057] J.Williams and M.Bennamoun eititled “Simultaneous Registration of Multiple Point Sets Using Orthonormal Matricies”Proc.,IEEE Int. Conf. on Acoustics, Speech and Signal Processing (ICASSP’00)]

权利要求:

請求項1
関心のあるターゲットに関する雲状に分布した3次元（3D）データ点群（雲状3Dデータ点群）の複数のフレームを記録する方法であって、あるシーンに関する雲状3Dデータ点群を含むn個の前記複数のフレームの中から複数のフレームペアを選択し、前記複数のフレーム中の各フレームの中で複数の部分空間を規定し、前記複数の部分空間の内、雲状3Dデータ点群が所定の塊状の対象物を含む条件を満たす部分空間（条件充足部分空間）を特定し、前記塊状の対象物の質量中心の位置を判定し、異なるフレーム同士における対応する部分空間内の前記質量中心の位置を利用して、フレームペアの間における質量中心対応点を判定し、前記質量中心対応点を利用して、各フレームの粗い記録のためのグローバル値RjTjを、n個のフレーム全てについて同時に計算するステップを有し、前記Rjは、フレームjの各々における全ての点をフレームiに整合させるために必要な回転ベクトルであり、前記Tjは、フレームjにおける全ての点をフレームiに整合させるために必要な並進ベクトルである、方法。
請求項2
前記グローバル値RjTjを用いて、前記n個のフレームにおける全てのデータ点を変換し、n個の粗く調整されたフレーム群を求めるステップをさらに有する、請求項1記載の方法。
請求項3
前記条件を満たす部分空間を特定する際に、部分空間各々について固有値分析を実行し、部分空間が前記所定の塊状の対象物を含んでいるか否かを判別する、請求項2記載の方法。
請求項4
前記質量中心対応点を判定する際に、フレームペアの第1のフレームの条件充足部分空間における第１の質量中心を特定し、該第1の質量中心は、フレームペアの第2のフレームの条件充足部分空間における第2の質量中心の位置に最も近いものである、請求項1記載の方法。
請求項5
粗く調整されたフレーム全てを別の記録ステップにおいて処理し、全てのフレームおける雲状3Dデータ点群をさらに細かく記録する、請求項1記載の方法。
請求項6
フレームペア各々を構成するフレーム同士の間における対応点を特定するステップをさらに有する、請求項5記載の方法。
請求項7
前記対応点を特定する前記ステップにおいて、フレームペアの第1のフレームの条件充足部分空間におけるデータ点を特定し、該データ点は、フレームペアの第2のフレームの条件充足部分空間における第2のデータ点の位置に最も近いものである、請求項6記載の方法。
請求項8
前記対応点を特定する前記ステップが、K−Dツリーサーチ法を用いて実行される、請求項7記載の方法。
請求項9
前記対応点を利用して、各フレームの細かい記録のためのグローバル値RjTjを、n個のフレーム全てについて同時に計算するステップをさらに有し、前記Rjは、フレームjの各々における全ての点をフレームiに整合させるために必要な回転ベクトルであり、前記Tjは、フレームjにおける全ての点をフレームiに整合させるために必要な並進ベクトルである、請求項7記載の方法。
請求項10
ノイズを除去するために前記n個のフレーム各々にノイズフィルタリングを施す、請求項1記載の方法。