(57)【要約】  多次元オブジェクトを表す多次元地理的データポイントをレジスタリングする方法は、ａ）多次元オブジェクトの表面の複数の重複したフレームを表す複数のポイントを受け付けるステップと、ｂ）第１フレームの各ポイントに対して、以降の複数のフレームのそれぞれの対応する最も近いポイントを検出するステップと、ｃ）対応する最も近いポイントが揃うように、各フレームに対する回転及び変換を決定するステップと、ｄ）各回転及び変換を実行するためのコストを決定するステップと、ｅ）最適な変換を提供するため、さらなるフレームに対してステップｂ）からｄ）を繰り返すステップとから構成される。
2008506136.tif 000002
【特許請求の範囲】
【請求項１】
多次元オブジェクトを表す多次元デジタル高度モデル地理的ポイントをレジスタリングするシステムであって、
第１フレームの各ポイントに対して、複数の以降のフレームのそれぞれの対応する最も近いポイントを検出するレジストレーションエンジンと、
前記複数の以降のフレームのそれぞれに対して、回転及び変換を決定し、各回転及び変換を実行するためのコストを決定するプロセッサと、
停止基準に到達するまで、さらなるフレームに対する前記回転及び変換並びにコストの決定を繰り返すロジックルーチンと、
から構成されるシステム。
【請求項２】
請求項１記載のシステムであって、さらに、
部分的に覆い隠された地表を表すデータポイントの複数のフレームを受け付け、前記地表のみを表すデータポイント群の複数のフレームを生成する地面検出装置を有するシステム。
【請求項３】
請求項１記載のシステムであって、さらに、
前記プロセッサによって決定されたコストを利用して、剛体変換を前記フレームに適用するロジックを有するシステム。
【請求項４】
請求項１記載のシステムであって、さらに、
前記第１フレームの各ポイントに最も近いポイントを前記以降のフレームにおいて検索するため、各フレームのポイントを表すｋ−Ｄツリーを有するシステム。
【請求項５】
請求項１記載のシステムであって、さらに、
前記多次元オブジェクトを表す統合された表面を提供するため、前記フレームを統合するフレーム統合装置を有するシステム。
【請求項６】
請求項１記載のシステムであって、さらに、
前記多次元オブジェクトを表示するディスプレイを有するシステム。
【発明の詳細な説明】
【発明の詳細な説明】
【０００１】
［発明の背景］
変化のある地理的地形などの多次元オブジェクトの完全なデジタルモデルを生成するのに、様々な視点からとられた複数の重複した範囲の画像（データポイントのボリューム又はフレームとしても知られる）を合成する必要がある。これらのフレームは、オブジェクトの多次元モデルを生成するため、レジストレーションとして知られる処理を利用して合成される。レジストレーション処理では、様々なフレームの要求される変換及び回転が決定される。当該処理は、Δｘ、Δｙ、Δｚ、Δω、Δκ及びΔΦの６つのパラメータを使用する。ここで、最初の３つのパラメータは、ｘ、ｙ及びｚの各座標の変換に関し、その後の３つのパラメータは、上記ｘ、ｙ及びｚの３つの軸のそれぞれに関する回転に関する。オブジェクトの様々なかつ重複した視点からの多数のデータポイントからなるフレームをレジスタリングする既知の方法は、計算量が多く、時間がかかるものである。しかしながら、レジストレーション技術の多くのアプリケーションは、フレームが取得される時間からの迅速なレスポンスを必要とする。従って、多次元データポイントをレジスタリングするためのより高速かつロウバストなシステムが必要とされる。
【０００２】
既知の地理的ポイントセットの方法には、イメージングＬＡＳＥＲ  ＲＡＤＡＲ（ＬＩＤＡＲ）及びＩＦＳＡＲ（Ｉｎｔｅｒｆｅｒｏｍｅｔｒｉｃ  Ｓｙｎｔｈｅｔｉｃ  Ａｐｅｒｔｕｒｅ  Ｒａｄａｒ）が含まれる。図１を参照するに、空中ＬＩＤＡＲシステム１００の一例が示される。システム１００は、航空機１０４の下部に搭載されたＬＩＤＡＲ装置１０２を有する。航空機の下に、空中から地面の視界を妨害する木や葉により構成される樹木によって部分的に覆い隠された地面を有するエリアがある。ＬＩＤＡＲ装置１０２は、地上に向けられた複数のレーザ光パルスを発射する。当該装置１０２は、パルスの反射／散乱を検出するセンサ１０３を有する。ＬＩＤＡＲ装置１０２は、単一の画像からの高度対位置情報を含むデータを提供する。しかしながら、様々な視点からの当該エリアの複数のフレーム又は部分が、画像を生成するのに利用されることに留意すべきである。地形を覆う樹木はまた、当該樹木の下のターゲット（戦車１０６など）を大きく覆い隠す。このため、地面及びターゲット１０６からの装置１０２のセンサ１０３によって受信されるポイントは、まばらなものとなる。このため、正確な３次元画像を生成するため、これらのポイントを処理するロウバストなシステムが求められる。さらに、最も戦術的かつ戦略的なものにするため、ターゲット１０６が認識可能な地上の画像が迅速かつ容易に利用可能とならなければならない。
【０００３】
［発明の概要］
本発明の実施例によると、多次元地理的データポイントをレジスタリングする方法は、地理的エリアの複数の重複したフレームを表す複数のデジタル高度モデルポイントを受け付けるステップと、第１フレームの複数のポイントのそれぞれに対して、以降の複数のフレームの対応する最も近いポイントを検出するステップと、各フレームに対する回転及び変換を決定するステップと、各回転及び変換を実行するためのコストを決定するステップと、フレームをレジスタリングするコストを最適化するため、ある回数又は停止基準に到達するまで、さらなるフレームに対して上記処理を繰り返すステップとから構成される。上述した方法はまた、特化した又はプログラム可能な情報処理システムによって、あるいはＣＤ−ＲＯＭやＤＶＤなどのコンピュータ可読媒体の命令セットとして実行することが可能である。
【０００４】
［詳細な説明］
図２を参照するに、本発明の実施例を用いた情報処理システム２００を示すハイレベルなブロック図が示される。システム２００は、地理的データポイントのソース２０２を有する。これらのポイントは、好ましくは、図１に関して説明されたようなＬＩＤＡＲ装置１０２により提供される複数の３次元（３Ｄ）地理的ポイントの値である。
【０００５】
ＬＩＤＡＲ装置２０２は、従来方法によりポイントの画像の複数のフレーム（又はボリューム）を生成する。各フレームは、航空機１０４がある地形の上を移動するとき、所与の期間にセンサ１０３により収集されたポイントを有する（エクスポージャ）。好適な実施例では、当該期間は１／３秒であり、現在の装置によると、このエクスポージャは、ＬＩＤＡＲセンサ１０３により数十万のポイント群が取得される。各ポイントは、３次元座標（ｘ，ｙ，ｚ）により規定される。
【０００６】
本システムが従来技術のパフォーマンスに対して向上される１つの方法は、少なくとも部分的に地表及びターゲット１０６（存在する場合には）を表し、地面から所定の閾値より大きな高さ（６フィートなど）にある障害物を表さないデータポイントのみを利用することによるものである。これらの地面ポイントのみを利用することは、ダウンリンク及び処理されるべきポイント数を大きく減少させ、これにより、当該地形のモデルを生成するのに必要となる時間を減少させることができる。
【０００７】
ＬＩＤＡＲ装置１０２によって提供されるデータは、リンギング（ｒｉｎｇｉｎｇ）として知られる効果（又はコロナ（ｃｏｒｏｎａ）効果）を有するかもしれない。リンギングは、誤ったリターンを生じさせるターゲットエリアにより生成される光の散乱によって生じる。リンギング除去フィルタ（回路又はプログラムロジック）２０４が、リンギングを除去するため受信した３Ｄ地理的ポイントをフィルタリングするのに利用される。必ずしもすべての地理的データが、リンギングを含んでいるとは限らない。従って、フィルタ２０４が常に要求されるとは限らない。リンギングは、選択された方位（ａｚｉｍｕｔｈ）設定を超えるすべてのデータを無視することにより除去され、これにより、誤った画像が解消される。方位の選択は、統計データにより規定され、又はヒューリスティックに決定される。システム２００のリンギング除去フィルタ２０４の使用により、フィルタ２０４の出力における信号対ノイズ比が増大する。リンギングフィルタの具体例の詳細は、整理番号ＧＣＳＤ−１５２６により同時に出願された特許出願に記載されている。
【０００８】
リンギングノイズ除去フィルタ２０４によって供給された出力は、地面検出装置２０６に受付される。地面検出装置２０６は、複数の処理されていない地理的ポイント（例えば、ＬＩＤＡＲ装置１０２などからの）とそれらの座標を用いて地表を検出し、地表とターゲット１０６のエリアを表す複数のフレームを表す複数の地面ポイントを提供するのに利用される。地面検出装置２０６は、それの入力から地面ポイントを抽出し、樹木のなどの地上の障害物ポイントをフィルタリングすることによって地面を検出する。予想されるように、樹木や他の葉などを介し地面に到達するＬＩＤＡＲパルスの個数は、ＬＩＤＡＲソース（又はエミッタ）により発射されるものよりかなり少なくなる。従って、ＬＩＤＡＲセンサにおいて検出される地面（地面ポイント）からの光のポイントは、航空機１０４の下方の地形全体から受け付けた合計より相応に少なくなる。
【０００９】
従って、地面検出装置２０６は、リンギング除去フィルタ２０４の出力において提供される地理的データから、地表シェル（３次元表面を規定するポイント群）を抽出する。地面検出装置２０６の出力は、ターゲット１０６を含む地表を表すデータ群を有する。地面ポイントは、樹木や他の葉などにより提供される地上の障害物からそれらを分離することによって決定される。
【００１０】
地面検出装置２０６はまた、地形の大きな変化がないように地面が連続的なものとなることを保証するよう動作する。これは、地表に対する２次元（２Ｄ）格子を生成し、各格子コンポーネントにおける地面の高さを決定することによって実現される。各格子コンポーネントは、好ましくは、各サイドに１メートルである地面の正方形部分を表す。このデータが格子全体に対して収集されると、地面検出装置２０６は、不十分なデータに基づく又は範囲外となるポイントを削除する。何れのポイントが削除されるべきかの決定は、地面検出装置２０６にプログラムされたアーチファクトに基づく。地面検出装置２０６は、さらに地表の地形を計算するとき、所定の高さ（６フィートなどの人の高さなど）より高い点を無視するようプログラムされる。この所定の高さは、ルールベース統計によって決定される。これは、地面の一部となる可能性のない任意の構造を削除するため実行される。従って、地面検出装置２０６の出力は、樹木の頂上のデータを用いたシステムより実際の地表のより忠実な表現を提供する。
【００１１】
地面検出装置２０６の出力は、コンペティティブフィルタ２０８に供給される。コンペティティブフィルタ２０８は、地面検出装置２０６によって提供される地表データ（地面ポイント）に対する処理に使用される。地面ポイントは、コンペティティブフィルタを利用して、デジタル高度モデル（ＤＥＭ）ポイントの３Ｄシェルを取得するためフィルタリングされる。コンペティティブフィルタ２０８は、ＬＩＤＡＲ装置２０２によって収集されるデータなど地理的座標に拘束されない地表データをフィルタリングする。フィルタ２０８は、ポイントの各フレームに対する所定のオーダーの多項式適合を実行することにより動作する。これは、何れの多項式がフレーム内のポイント群を最も良く表すか決定することにより行われる。１つの例は、１次多項式（タイル平面）であり、他の例は、数値平均（ゼロ次）である。好適な実施例では、平均及びタイル平面（それぞれ、ゼロ次及び１次多項式）が、何れか与えられたポイントフレームにおける最善の適合について競合する。他の実施例は、より高次の多項式を利用するかもしれない。多項式をフレームを適合させる方法は、参照することによりその開示のすべてがここに含まれる、米国特許出願第０９／８２７，３０５号に記載されている。
【００１２】
従って、すべてのポイントフレームに対して、フィルタ２０８は、当該フレームのポイントに適合したタイル平面を決定する。各フレームは、レジストレーションによって生成されるエリア全体の一部を構成するパッチ（ｐａｔｃｈ）をカバーするマイクロフレームである。コンペティティブフィルタ２０８の出力は、取得された各フレームに対して１つの平面となる複数の（３０個などの）平面からなる地形である。地表の最適な推定は、樹木や葉による障害物が部分的に覆い隠されたターゲットの画像を生成することを可能にする。各フレームがフィルタ２０８により処理されると、当該出力はレジスタリングされていないＤＥＭ表面群となる。本実施例では、各表面は地表となるが、本発明による方法及びシステムは、ターゲットオブジェクトの任意の表面について利用可能であるということが理解されるべきである。
【００１３】
コンペティティブフィルタ２０８により生成されるデータＤＥＭは、システム２００のユーザに有用な画像をレンダリングするには適していない。閲覧可能な画像を生成するため、まずレジストレーション処理を完了させる必要がある。好適な実施例では、レジストレーションはブロック２１０（レジストレーションエンジン）と２１２（剛体変換エンジン）によって実行される繰り返し処理により実行される。本実施例では、地表の３Ｄ表現を取得するため、複数のデータ（フレーム）群が、ターゲットエリア又は表面全体の画像を生成するため自動合成される。各データ（フレーム）群は、表面特徴の異なる視界を提供する異なる視点から取得される。レジストレーションは、センサ１０３が当該表面を移動するとき、この表面を表す各ポイントの相対位置を決定する。これにより、表面エリアの様々な視界が、隣接フレームに適合するように各フレームの変換及び回転を実行することによって、互いに揃えられる。
【００１４】
ブロック２１０は、隣接フレームのポイントを揃える。これは、第１フレームの複数のポイントのそれぞれに対して、最も近いポイントを第２フレームから検出することによって行われる。最も近いポイントが検出されると、フレームがレジスタリングされたモデル又は画像を表す良好な適合を生成するように揃えられる。これは、ペア単位処理として知られる。当該処理の各繰り返しは、より良好な適合を生成し、最適な配置が実現されるまで当該処理が続けられる。これは、他のフレームに適合するため、各フレームの各回転及び変換に係る計算コストを決定することによって実現される。各繰り返しにおいて収集された情報（隣接フレーム間のマッチ）を利用して、停止基準に到達するまで、以降の繰り返しが配置を訂正する。この基準は、ある回数の繰り返しの終了又は所定の目標の達成とすることができる。本実施例では、各繰り返しからの観察をマトリックスに入力し、その後、すべての変換が実質的に同時に実行されるように（すなわち、ｎ単位処理）、即座にマトリックスを解くことによって、他の複数のフレームにおける最も近いポイントを特定するため、第１フレームの各ポイントに対して最も近いポイントの検索を実行する。
【００１５】
ブロック２１２は、各繰り返し中にブロック２１０において生成されたポイントの配置に関する情報を受け付ける。ブロック２１のプロセッサロジックは、ブロック２１０により提供された情報を利用して、それらが共に適合されるとき、各フレームに対する変換（すなわち、角度と移動）を決定する。従って、ブロック２１２の出力は、合成対象となるフレームの角度と移動のセット（Δｘ、Δｙ、Δｚ、Δω、Δκ及びΔΦ）となる。
【００１６】
フレーム統合ブロック２１４は、剛体変換ブロック２１２の出力を受け付け、剛体変換情報に従って、コンペティティブフィルタ２０８により生成されたＤＥＭポイントのすべてを統合する。
【００１７】
好適な実施例では、フレームに対する最適な回転及び変換を決定するため、繰り返し処理が複数回（５回など）繰り返される。好ましくは、参照することによりその開示がここに含まれる、Ｊ．Ａ．Ｗｉｌｌｉａｍｓ及びＭ．Ｂｅｎｎａｍｏｕｎによる“Ｓｉｍｕｌｔａｎｅｏｕｓ  Ｒｅｇｉｓｔｒａｔｉｏｎ  ｏｆ  Ｍｕｌｔｉｐｌｅ  Ｐｏｉｎｔ  Ｓｔｓ  Ｕｓｉｎｇ  Ｏｒｔｈｏｎｏｒｍａｌ  Ｍａｔｒｉｃｅｓ”（Ｐｒｏｃ．ＩＥＥＥ  Ｉｎｔ．Ｃｏｎｆ．ｏｎ  Ａｃｏｕｓｔｉｃｓ，Ｓｐｅｅｃｈ  ａｎｄ  Ｓｉｇｎａｌ  Ｐｒｏｃｅｓｓｉｎｇ（ＩＣＡＳＳＰ  Ｊｕｎ．２０００，ｐｐ．２１９９−２２０２））に与えられるアルゴリズムを利用する。
【００１８】
上述した繰り返される変換は、ブロック２１２において実行される。各変換は、剛体変換である。変換が対応するポイント間の距離を維持する場合、当該変換は剛体であると言われる。
【００１９】
フレーム統合ブロック２１４において、ブロック２１２により生成されたレジスタリングされたボリュームの統合が実行され、その結果が提示するのに適切なサイズと形状にクロッピング（ｃｒｏｐ）され、その後、ターゲットの構造を表示するため、ブロック２１６において視覚的に利用される。この結果は、高速表示される３Ｄモデルである。ここに記載される実施例では、図１に示されるような樹木の頂上の下に隠れる戦車１０６などのターゲットが、戦車１０６の上方の樹木の覆い隠す効果なしに図示される。
【００２０】
上述したように、レジストレーション処理の速度は、戦闘環境の戦車１０６など隠れたターゲットの特定などの多くのアプリケーションにおいて重要である。当該処理をスピードアップする１つの方法は、フレームからフレームへの対応するポイントに対する検索スピードを向上させることである。これは、いくつかの周知のｋ−Ｄツリーアルゴリズムの何れかを利用して実現することが可能である。従って、各フレームからのデータポイントは、隣接フレームのポイント群の全体が、第１フレームの所与のポイントに対する最も近いポイントを検出するための検索が不要となるように、ツリー構造にマッピングされる。ｋ−Ｄツリーアルゴリズムの一例が、ｈｔｔｐ：／／ｗｗｗ．ｒｏｌｅｍａｋｅｒ．ｄｋ／ｎｏｎＲｏｌｅｍａｋｅｒ／ｕｎｉ／ａｌｇｏｇｅｍ／ｋｄｔｒｅｅ．ｈｔｍのウェブサイトに見つけることができる。
【００２１】
図３を参照するに、ＬＩＤＡＲポイントのフレームなどの１つのフレームに対する表面を表すポイント群が示される。各ステップにおいて、当該領域は、各領域がこれらのポイントの１／２を含む２つの領域に分割される。当該処理は、各ポイントが自らの領域に属するまで繰り返される。例えば、８つのポイントから開始し、あるポイントを検索している場合、何れの半分にそれがあるか問い合わせることによって、４つのポイントに分けられ、その後２つのポイントに、最後に１つのポイントに分けられる。これはたった３つのステップで行うことができ、８つすべてのポイントを問い合わせることより容易である。存在するポイントが多くなるほど、その差は特に大きくなる。２５６個のポイントが存在する場合、２５６回の代わりに８回の試行によりあるポイントを検出することが可能である。
【００２２】
レジストレーションエンジン２１０は、ラインＬ１〜Ｌ８を生成する。これらのラインは、ｋ−Ｄツリーを構築するのに利用され、図４に示される。ｋ−Ｄツリーは、ポイントＰ１〜Ｐ１０をｘ及びｙ方向に再帰的に分割することによって生成される。ｋ−Ｄツリーでは、図３の各ラインはノード（丸印）によって表され、各ポイント（矩形）がノードに接続される。当該ツリーは、何れか所与のポイントに最も近いポイントを検出するのに必要とされる検索時間を減少させるのに利用される。例えば、Ｐ１０に最も近いポイントを検索する場合、ノードＬ１からＬ３を、その後にＬ７を探索し、Ｐ１でなくＰ９のみを検討する。本例は２Ｄであるが、本出願は３Ｄポイントを利用することに留意されたい。
【００２３】
図５は、ユークリッド距離に対する統計的距離の効果を示す複数のポイントのグラフである。「Ｏ」として示されるポイントは、ＬＩＤＡＲにより生成されたフレームＡからのものであり、「Ｘ」として示されるポイントは、ＬＩＤＡＲにより生成されたフレームＢからのものである。これらのフレーム又はボリュームは重複していると仮定する。フレームＡのどのポイントがフレームＢのどのポイントと組み合わされるかについては当初はわかっていない。整列されるべき各ポイントペアの座標を比較することからスタートする。何れか所与のポイントペア間の距離は、丸印又は楕円として表される。丸印はユークリッド距離を表し、楕円はマハラノビス（Ｍａｈａｌａｎｏｂｉｓ）距離を表す。等式ｒ２＝（ｘ−ｍｘ）’Ｃｘ−１（ｘ−ｍｘ）における値ｒは、特徴ベクトル（ｆｅａｔｕｒｅ  ｖｅｃｔｏｒ）ｘから平均ベクトル（ｍｅａｎ  ｖｅｃｔｏｒ）ｍｘまでのマハラノビス距離と呼ばれる。ただし、Ｃｘはｘに対する共分散行列である。ｒが一定となる表面は、平均ｍｘを中心とする楕円となることは、証明することができる。マハラノビス距離は、ポイントを上下に（すなわち、ｚ軸に沿って）揃えるのに利用される。当該処理は、ポイントがそれの実際のものよりｚ方向に離れて現れるという観察された事実を認識している。他のフレームの対応するポイントを特定するために楕円エリアを利用してポイントを揃えることによって、丸印により表されるユークリッド距離を単に利用することより、より正確なモデルを実現することができる。
【図面の簡単な説明】
【００２４】
【図１】図１は、ターゲットを隠す樹木により覆われた地形の画像を処理するための空中ＬＩＤＡＲ装置を示す。
【図２】図２は、本発明の実施例による情報処理システムを示すハイレベルブロック図である。
【図３】図３は、ＬＩＤＡＲポイントのフレームなどの１つのフレームに対する表面を表す２次元ポイント群である。
【図４】図４は、最も近いポイントの検索に利用されるｋ−Ｄツリーを示す。
【図５】図５は、ユークリッド距離に対する統計的距離の効果を示す複数のポイントのグラフである。
【図１】
2008506136.tif 000003
【図２】
2008506136.tif 000004
【図３】
2008506136.tif 000005
【図４】
2008506136.tif 000006
【図５】
2008506136.tif 000007
【国際調査報告】
2008506136.tif 000008