JP2016031764A - 画像解析方法 - Google Patents

Abstract

【課題】三次元点群を解析する方法であって、最低レベルに複数の葉ノードを含む、
【解決手段】階層的な探索木に点を配置することを含む。各葉ノードは三次元点群の点に対応し、探索木は各々にノードを伴う複数の階層レベルを備え、ノードは枝によって階層を通り抜けて互いに垂直的に接続され、子孫ノードの特性の少なくとも１つのモーメントが各ノードに保存される。方法は、領域の中に入る点が最小数のノードによって表されるように、子孫の葉ノードの全てが領域内に含まれる最高レベルのノードを識別し、領域内に完全に含まれるサブツリーのない点に対して葉ノードを選択し、領域内の点を表すノードに統計的演算（識別されたノード内に保存される特性のモーメントから判定される）を行うことによって、領域内に位置する点の幾何学的情報を判定することを含む。
【選択図】図３

Description

ここに記述される本発明の実施形態は、一般に画像解析方法およびシステムに関する。

多くのコンピュータ・ビジョンおよび画像処理アプリケーションは、三次元点群からの一群の点の統計的尺度を計算する必要がある。一例は、三次元点群の特徴の検出である。

特徴は、三次元点群によって表わされるシーンの内容のコンパクトな表現を提供する。それらは、シーンのローカル部分だけについて記述し、故に、クラッタ、オクルージョンおよびクラス内変動に対するロバスト性を与える。そのような特性のため、特徴は、オブジェクト認識および位置合わせ、シーン理解、カメラ校正ならびに姿勢推定などの問題に対してよい選択である。特徴の数は点（ポイント）の数よりもはるかに少ないので、データが大きい（つまり、大規模な再構成方法あるいはレーザー・スキャナーからキャプチャーされた）場合には、特徴ベースのアプローチは効率においてポイントベースのアプローチを上回る長所を持つ。

３Ｄコンピュータ・ビジョン用の特徴ベースのアプローチの応用はユビキタスである。これらは、次のものを含んでいるが次のものに制限されない。オブジェクト認識および位置合わせ、移動ロボット、ナビゲーションおよびマッピング、拡張現実、自動車の自動運転、シーン理解およびモデル化。

３Ｄオブジェクト認識の目標の一つはシーン内のオブジェクトのリアルタイム検出である。この技術は、３ＤデータからＣＡＤモデルを構築するための基本的な技術のうちの１つである。他の応用例は、ナビゲーション、移動ロボット工学、拡張現実および自動生産である。シーンの一部分だけが観測されるので、カメラから得られた三次元点群からの検出は困難なタスクである。人間は、ほとんど労せずしてオブジェクトを認識する。しかしながら、特に制限のある時間的制約がある場合には、これは依然としてコンピュータ・ビジョンにおける難題である。

３Ｄオブジェクト認識において１つの重要なステップは、特徴（すなわち、オブジェクトの位置および方向を推定するために使用することのできるシーン内の目立つ領域）を見つけ出して抽出することである。特徴抽出は、他のタスク（例えば、三次元点群位置合わせおよびオブジェクト追跡）にも有用である。

（関連出願の相互参照）
この出願は、２０１４年７月２５日に提出された英国特許出願第１４１３２４５．０号に基づいていて、かつ、この優先権の利益を主張するものであって、その全内容が参照によってここに組み込まれる。

図１は、本発明の実施形態に従う方法を行うのに適したコンピュータ・ビジョンシステムの概略図である。 図２は、特徴の表現である。 図３は、実施形態に従う特徴検出方法を図示するフロー図である。 図４（ａ）は、ツリーノードおよび葉ノードとオーバーラップするクエリを示す図である。図４（ｂ）は、探索木の概略図である。 図５は、探索領域の半径に対して１０，０００回の半径探索を行うのにかかった時間のプロットである。 図６は、ＣＰＵおよびＧＰＵの両方で実行される本発明に従う方法を用いて探索領域の半径に対して１００，０００回の半径探索を行うのにかかった時間のプロットである。 図７は、実施形態に従う特徴記述子を生成する方法を図示するフロー図である。 図８は、実施形態に従う特徴を抽出して特徴記述子を生成する方法を図示するフロー図である。 図９は、実施形態に従う三次元点群フィルタリング方法を図示するフロー図である。 図１０は、実施形態に従う三次元点群サブサンプリング方法を図示するフロー図である。 図１１は、実施形態に従う三次元点群の密度推定を図示するフロー図である。 図１２は、実施形態に従う、三次元点群から垂線を推定する方法を図示するフロー図である。 図１３は、実施形態に従う、三次元点群の面方向を推定する方法を図示するフロー図である。

実施形態によれば、三次元点群を解析する方法が提供される。この方法は、複数の点（ポイント）を含む三次元点群を受け取ることを含む。各点は、画像内の空間的な点を表す。この方法は、最低レベルに複数の葉ノードを含む、階層的な探索木に点を配置することを含む。各葉ノードは三次元点群の点に対応し、探索木は複数の階層レベルを備え、階層レベルの各々にノードを伴い、ノードは枝によって階層間で互いに接続され、子孫ノードの特性の少なくとも１つのモーメントが各ノードに保存される。この方法は、領域の中に入る点が最小数のノードによって表されるように、子孫の葉ノードの全てが領域内に含まれる最高レベルのノードを特定し、領域内に完全に含まれるサブツリーのない点に対して葉ノードを選択し、領域内の点を表すノードに統計的演算を行うことによって、領域内にある点の幾何学的情報を決定することを含む。統計的演算は、識別されたノード内に保存される特性のモーメントから判定される。

上記方法は、点の集合をノードの集合として表し、ツリーは三次元点群から構築される。領域は３Ｄの球状領域であってよく、この実施形態において、この方法は、球領域の内部に位置する点群の全ての点の集合を発見し、当該集合をノードの集合として返す。この方法によって発見された点の集合は、正確または近似であり得る。

例えば、位置の平均を計算するために、領域に入る全ての点の平均を計算する必要がある。上記方法において、位置の平均を計算することが望まれるならば、探索木の構築時に、ツリーノードの全ての子孫ノードの位置の平均が各ノードに保存される。位置の平均は位置の一次モーメントであって、この場合に位置が特性である。幾何学的情報が計算される際に、可能な場合には、幾何学的情報はノードに保存された平均の値を用いて計算される。故に、この方法は、毎回点の各々について平均を計算するとは限らない。葉ノードそれ自身からの値は、その子孫ノードの全てが領域内に存在するノードが識別できない場合に使用されるに過ぎない。点のグループは、点が下る最高レベルのノードによって記述される。ノードから下る点の一部が領域外にあるならば、当該ノードは使用することができず、より低いレベルのノードが捜し求められる。

特性は、位置、法線ベクトル、カラー、曲率、強度または透明度から選択される少なくとも１つであってよい。

幾何学的情報は、点の数、位置の平均、カラーの平均、法線ベクトルの平均、強度の平均、位置の共分散、法線ベクトルの共分散、カラーの共分散、曲率の分散および強度の分散から選択される１つ以上であってよい。

モーメントは、零次、一次、二次または任意のより高次のモーメントから選択されてよい。

実施形態において、方法は、三次元点群内の全ての点の位置を隣接する点の平均に置き換えることにより三次元点群をフィルタリングするように構成され、隣接する点は領域によって定義される距離の内に入り、幾何学的情報は隣接する点の平均である。

一実施形態において、方法は、三次元点群をフィルタリングするために使用され、ここで点の位置の零次および一次モーメントがノードに保存され、方法は、三次元点群内の全ての点の位置を隣接する点の平均に置き換えることにより三次元点群をフィルタリングするように構成され、隣接する点は領域によって定義される距離の内に入り、幾何学的情報は、零次および一次モーメントから計算された、隣接する点の平均である。

さらなる実施形態において、幾何学的情報は、領域内の点の数であり、方法は、領域のサイズによって除算される領域内の点の数を用いて三次元点群の密度を推定することをさらに含む。

さらなる実施形態において、方法は、領域内の点の数を判定するために使用される。ここで、点の位置の零次モーメントがノードに保存され、幾何学的情報は領域内の点の数であり、方法は、領域のサイズによって除算される、保存された零次モーメントからの領域内の点の数を用いて三次元点群の密度を推定することをさらに含む。

方法は、点または点における面に対する法線を判定する際にも使用されてよく、ここで、点の位置の零次、一次および二次モーメントがノードに保存されてよく、幾何学的情報は三次元点群上で選択された点の法線ベクトルであり、法線ベクトルは、ノード内に保存されたモーメントから、選択された点の周囲の領域内の点の共分散行列を計算することによって判定され、方法は、共分散行列の第３の固有ベクトルから法線を判定することをさらに含む。

点または点のサブセットにおける面の方向が、点の位置の零次、一次および二次モーメントをノードに保存することによって判定されてもよく、幾何学的情報は選択された点における三次元点群の面の法線であり、方向は、ノード内に保存されたモーメントから、選択された点の周囲の領域内の点の共分散行列を計算し、共分散行列の３つの固有ベクトルから方向を導出することによって、判定される。

実施形態において、上記方法は特徴検出に使用される。特徴検出では、領域内の多数の点から幾何学的情報を計算する必要がある。多くのタイプの特徴検出器は、位置または面法線のどちらかの共分散を使用する。共分散は、零次、一次および二次モーメントから計算され、これらのモーメントはツリーの構築時にノードに保存することができる。これら保存されたモーメントは、共分散の判定時に子孫ノードの各々を用いてモーメント計算する必要性を回避するために、特徴検出中にノードから検索することができる。

共分散行列を計算する能力は、特徴位置および特徴記述子の判定において多くの用途がある。ここで、点の位置の零次、一次および二次モーメントがノードに保存され、幾何学的情報は三次元点群内の特徴の位置であり、方法は、選択された点の周囲に定義される領域内の点についてのノード内に保存されたモーメントから共分散行列を計算することと、共分散行列の固有値からスコアを判定することとをさらに含み、特徴は、当該特徴のスコアを基準として、選択された点に位置するとみなされる。

実施形態において、共分散行列は３つの固有値を持ち、最小の固有値がスコアとして割り当てられる。さらなる実施形態において、領域は、第１の半径を持つ第１の球であり、選択された点は、当該点の周囲に第１の球と第２の半径を持つ第２の球とを構築することによって解析され、第２の半径は第１の半径よりも大きく、選択された点についての第２の球の中の三次元点群内の点の各々は、これらの点の周囲に第１の球を構築し、各点についてスコアを計算することによって解析される。ここで、特徴の位置は、第１の球について計算された最大のスコアを伴う点にあると判定される。

上記において、記述子は、特徴が位置する点について判定された第１の球および当該第１の球についての３Ｄ方向である。

しかしながら、共分散行列は技術分野において知られている他の記述子を判定するためにも用いられてよく、これらは上記解析方法からの共分散を用いて計算することができる。

これは、オブジェクトの認識／位置合わせに使用することができ、ここでは未知のシーンから抽出された特徴が、既知の、過去に解析されたオブジェクトからの特徴のデータベースと比較される。

上記技法は、特徴および記述子を効率的に抽出するために使用することができるが、他の用法もある。例えば、三次元点群サブサンプリングであって、ここでは上記のフィルタリングされた三次元点群がサンプリングされる。これは、三次元点群の圧縮および可視化のために使用することができる。

さらなる実施形態では、三次元点群を解析するように構成されたシステムが提供され、システムは、複数の点を含む三次元点群を受け取るのに適合した三次元点群受信ユニットを含み、各点は、画像内の空間的な点を表し、システムは、最低レベルに複数の葉ノードを含む、階層的な探索木に点を配置するのに適合したプロセッサを含み、各葉ノードは三次元点群の点に対応し、探索木は複数の階層レベルを備え、当該階層レベルの各々にノードを伴い、ノードは枝によって階層を通り抜けて互いに垂直的に接続され、子孫ノードの特性の少なくとも１つのモーメントが各ノードに保存され、プロセッサは、領域の中に入る点が最小数のノードによって表されるように、子孫の葉ノードの全てが領域内に含まれる最高レベルのノードを識別し、領域内に完全に含まれるサブツリーのない点に対して葉ノードを選択し、領域内の点を表すノードに統計的演算を行うことによって、領域内に位置する点の幾何学的情報を判定および出力するようにさらに適合され、統計的手段は、識別されたノード内に保存される特性のモーメントから判定される。

実施形態において、プロセッサは、ＧＰＵ（Ｇｒａｐｈｉｃｓ Ｐｒｏｃｅｓｓｉｎｇ Ｕｎｉｔ）である。

さらなる実施形態において、方法は、携帯電話機、タブレットなどのモバイルデバイス上で実装される。方法は、拡張現実アプリケーションなどでの使用のためにオブジェクト認識および位置合わせを提供するために使用することができる。特徴検出、記述、フィルタリング、三次元点群サブサンプリング、方向決定の実施形態および他の実施形態は全て、モバイルデバイス内で実装することができる。

本発明の実施形態はソフトウェアで実装可能なので、本発明の２５の実施形態は汎用コンピュータ、モバイル処理デバイスなど（実施形態ではＧＰＵを備える）に、任意の適した伝送媒体で提供されるコンピュータコードを包含する。伝送媒体は、フロッピー（登録商標）ディスク、ＣＤ ＲＯＭ、磁気デバイス若しくはプログラム可能なメモリデバイスなどの任意の記録媒体、または、例えば電気、光学若しくはマイクロ波信号などの任意の信号などの任意の一時的な媒体を備えることができる。

図１は、三次元点群の形式で３Ｄデータをキャプチャーするために用いることのできる適切なシステムを示す。システムは、基本的に、カメラ３５と、解析ユニット２１と、ことによるとディスプレイ（図示されない）とを備える。

実施形態において、カメラ３５は、標準的なビデオカメラであって、ユーザによって移動可能である。動作中に、カメラ３５は、画像化されるオブジェクトの周囲を自由に動かされる。カメラは単にハンドヘルドであってもよい。しかしながら、さらなる実施形態にでは、カメラは三脚または他の機械的な支持器具上に取り付けられる。それから、三次元点群は、様々なカメラ姿勢で収集された２Ｄ画像を用いて構築されてもよい。他の実施形態において、３Ｄカメラまたは他のデプスセンサ（例えば、隔たって据えられた複数の開口を備えるステレオカメラ、オブジェクトにパターンを投影することのできるカメラ、ＬＩＤＡＲセンサおよびＴＯＦ（Ｔｉｍｅ Ｏｆ Ｆｌｉｇｈｔ）センサ）が使用されてもよい。ＣＡＴスキャナおよびＭＲＩスキャナなどの医療スキャナがデータを提供するために使用されてもよい。これらのタイプのカメラおよびスキャナから三次元点群を生成する方法は、既知であってここではこれ以上論じられない。

解析ユニット２１は、カメラ３５からカメラデータを受信するセクションを備える。解析ユニット２１は、プログラム２５を実行するプロセッサ２３を備える。解析ユニット２１は、ストレージ２７をさらに備える。ストレージ２７は、カメラ３５から受信されたデータを解析するためにプログラム２５によって使用されるデータを保存する。解析ユニット２１は、入力モジュール３１および出力モジュール３３をさらに備える。入力モジュール３１は、カメラ３５に接続される。入力モジュール３１は単にカメラ３５から直接的にデータを受信するかもしれないし、或いは、入力モジュール３１は外部記録媒体またはネットワークからカメラデータを受信してもよい。

使用時に、解析ユニット２１は、入力モジュール３１を通じてカメラデータを受信する。プロセッサ２３で実行されるプログラム２５は、ストレージ２７に保存されたデータを用いてカメラデータを解析し、３Ｄデータを生成してオブジェクトおよびそれらの姿勢を認識する。ディスプレイ（図示されない）またはローカルの若しくはネットワーク化された他の出力デバイスに接続され得る出力モジュールを介して、データは出力される。

図１は全くの概略であって、システムは、携帯電話機、タブレットなどのカメラ（例えば、カメラは３Ｄデータを得るために方々動かされ得る）が内蔵カメラであるモバイルデバイス内で提供され得る。或いは、データはモバイルデバイスに送信され得る。さらなる実施形態において、システムは、腕時計、および／または、ヘッドウェア、バイザーなどのウェアラブルテクノロジにおいて提供され得る。

解析ユニットは、多くのタスクを扱うように構成され得る。画像内の特徴を検出するタスクが図２乃至３を参照して記述される。特徴は、オブジェクトの関心領域であって通常はオブジェクトのプロファイルに変化がある所である。特徴を検出することは、オブジェクト認識および位置合わせ、ナビゲーションおよびマッピング、シーン理解およびモデリングなどの多くの３Ｄアプリケーションにおいて重要なステップである。図２は、特徴として識別されたオブジェクトのコーナーの概要を示す。

三次元点群のために多くの特徴検出器が存在する。これらの検出器の一部は、シーン内で観察される点の近辺に位置する点または面法線のいくついかの統計量の抽出に依存する。

実施形態において、解析に適した点を識別するために、クエリが球領域として提供される。解析用の点を識別するために、探索木構造が構築され点にインデックスが付けられる。図２のフロー図では、ステップＳ１０１において、三次元点群が図１を参照して記述されたタイプの装置から受信される。

ステップＳ１０３において、三次元点群の点にインデックスを付けるために探索木が構築される。多くの様々な方法論が、例えばＯｃｔｒｅｅまたはＫＤＴｒｅｅなどの探索木を構築するために使用可能である。いくつかの実施形態では、ノード毎に、当該ノードで生じる２つのグループの値同士の距離が最大となるように選択された、２つの枝にツリーが分割される。

この実施形態において、ステップＳ１０５では、値が探索木のノードに保存される。値の正確な性質は、アプリケーションに依存し、後により詳細に説明される。しかしながら、各ノードにおいて、ノードから下る三次元点群の全ての点に関連した特性のモーメントがノード内に保存される。例えば、探索木の構築時に、行われる解析が、例えば、面法線、カラーなどの点の特性の共分散を必要とするならば、全ての子孫ノードについて計算された特性の共分散がノードに保存される。各ノードは、それ自身のサブツリーのためのルートノードを当該サブツリーが全ての子孫の点（子孫ポイント）を備える所に形成する。

ステップＳ１０７では、クエリの球領域（クエリボール領域）Ｒが設定される。一実施形態では、球のサイズは固定される。他の実施形態では、球のサイズは変化する。この特定の例では、簡単にするために、単一の球サイズが仮定される。

次に、実施形態において、分枝限定法が、球内に位置する端点（エンドポイント）までツリー内を探索するために用いられる。この実施形態において、子孫の葉ノードが全て領域内に含まれる場合に、最高レベルのサブツリーが識別されるように、領域Ｒの中に完全に入るサブツリーが特定される。

サブツリーが領域内に完全には含まれないためサブツリーを特定することができない場合には、点を表す葉ノードが選択される。従って、領域の中に入る点は、最小数のノードで表現される。

領域Ｒ内のノードの判定は、ステップＳ１０９で行われる。これは、図４を参照してより詳細に説明される。図４（ｂ）では、探索木が、最高レベルに２枝に分かれるルートノードＣ１を備えて示される。２つの枝の各々は、ノードＣ２およびＣ３でそれぞれ終わる。ノードＣ２は、さらに再分割され、子孫の葉ノードＣ４およびＣ５を持つ。ノードＣ３は、さらに再分割され３つの葉ノードＣ６、Ｃ７およびＣ８で終わる。

図４（ａ）は、Ｃ１乃至Ｃ８とマーク付けされた葉ノードおよびツリーノードと共にサーチクエリＱの概略を示す。点Ｃ４はＱの外にあるので、ルートノードＣ１からの木全体が完全にはサーチクエリＱの中に含まれていないことが分かる。しかしながら、ノードＣ３からのサブツリーは、サーチクエリＱの中に完全に含まれている。故に、ノードＣ３は、３つの子孫ノードＣ６、Ｃ７およびＣ８を表現するために使用可能である。

葉ノードＣ５は、サーチクエリＱの中に完全に含まれているサブツリーに属さない。故に、この点は、葉ノードＣ５によってのみ表現することができる。

上に説明されたように、ノードは、それらの子孫の葉ノードのモーメントを保存する。

図３の実施形態は、キーポイント検出器に関する。ハリス（Ｈａｒｒｉｓ）法は、コーナーおよびエッジをベースとする方法であって、このタイプの方法は水平および垂直方向におけるそれらの激しい強度変化によって特徴付けられる。３Ｄに適応させる場合に、画像勾配は面法線によって置き換えられる。共分散行列Ｃ（ｘ）は、定義済みの半径ｒと共に、三次元点群の各点ｘ∈Ｒを中心に置く球領域に位置する点の面法線から計算される。それから、キーポイント応答は次のように定義される。

ここで、ｋは正の実数値のパラメータである。このパラメータは、弱いエッジの大きさと強いエッジの大きさとの比率の下限としておよそ役立つ。さらに、ハリス３Ｄキーポイント検出器の２つの他の変形がある。ロウ（Ｌｏｗｅ）法は、以下の応答を用いる。

ノーブル（Ｎｏｂｌｅ）法は、以下の応答を用いる。

ＫＬＴ（Ｋａｎａｄｅ−Ｌｕｃａｓ−Ｔｏｍａｓｉ）検出器では、３Ｄに適応させるために、面法線の代わりに入力３Ｄ位置から直接的に共分散行列が計算される。キーポイント応答のために、共分散行列の第１の固有値が用いられる。

いわゆるＳＩＦＴキーポイント検出器は、キーポイントを選択するためにヘッシアンの３Ｄバージョンを用いる。確率密度関数ｆ（ｘ）は、空間内でデータを規則的にサンプリングすることで近似される。確率密度関数上にスケール空間が構築され、ヘッセの行列式の極大値を求めて探索がなされる。入力三次元点群は、スケールの増加と共に多数のガウシアンフィルタを用いて畳み込まれる。少数のＤｏＧ（Ｄｉｆｆｅｒｅｎｃｅ−ｏｆ−Ｇａｕｓｓｉａｎ）クラウドをもたらすために、隣接する平滑化されたボリュームが差し引かれる。キーポイントは、スケール中のＤｏＧクラウドの極小値／極大値として識別される。

ＩＳＳ（Ｉｎｔｒｉｎｓｉｃ Ｓｈａｐｅ Ｓｉｇｎａｔｕｒｅｓ）は、領域状の（ｒｅｇｉｏｎ−ｗｉｓｅ）品質尺度に依存する。この方法は、最小の固有値の大きさ（クエリの球領域内に位置し、それぞれの主要な方向に沿って大きな変動を備える点のみを含めるために）および２つの連続した固有値同士の比率（主要な方向に沿って同様の広がりを持つ点を除外するために）を用いる。上記方法のように、所与の球領域内部に位置する点を探索するアルゴリズムが必要となる。

上記のものは、キーポイントまたは特徴の検出方法の例である。それらの各々は、領域Ｒの中に入る点の共分散行列の計算を必要とする。ステップＳ１０９では、領域Ｒの中に入るノードが識別される。

第１に、半径探索として所与のクエリボール領域内部の点を見つけ出すアルゴリズムを考慮する。このアルゴリズムは、３Ｄの点ｐおよび半径ｒ＞０を入力として取り、三次元点群の点のリストＸ＝｛ｘ_１，．．．，ｘ_ｎ｝（ここでｎは返される点の数である）を出力として返す。

ステップＳ１０９に関して論じられた方法では、根源的な木の各ノードは三次元点群の部分集合を定義し、これは所与のノードの子孫である葉ノードの点全ての集合である。

ｃ_１，．．．，ｃ_ｍがノード（いくつかのｍについてｍ＜ｎ）表し、ノードｃの葉ノードの点の集合をＰ（ｃ）によって示すとする。部分集合Ｘは、ノードのいくつかの集合Ｃ＝｛ｃ_ｉ１，．．．，ｃ_ｉｋ｝についての和集合Ｐ（ｃ_ｉ１）∪．．．∪Ｐ（ｃ_ｉｋ）として同等に表現することができる。実際には、Ｃの要素数（すなわちｋ）は、Ｘの要素数（すなわちｎ）よりも相当に少ないので、半径探索アルゴリズムがＸの代わりにＣを返し、かつ、Ｘの代わりにＣに基づく統計量が計算されるならば、効率は改善される。

Ｃに基づく統計量の計算は可能であるが、さらなるステップが必要となる。説明の容易さのために、目標は、点（すなわちＸ）の統計量を計算することであると仮定される。一旦この例が説明されて、この思想の他の種類の幾何学的情報（例えば、面法線）への拡張が説明される。

点の数、点の平均、および、Ｘの点の共分散行列は、それぞれｎ、ｕ、Ｃでそれぞれ示される。以下の量を定義する。

平均および共分散は、以下の数式を介して間接的に計算することができる。

故に、残りはＣからｍ（Ｘ）およびＭ（Ｘ）を計算することである。これら２つの量はいくつかの点の量の和であって、和は結合演算子であるから、それらは以下の式によって計算することができる。

故に、量ｍ（Ｐ（ｃ））およびＭ（Ｐ（ｃ））がノードｃ毎に計算されるならば、これらの量を合計することでクエリ毎にＣからＸの点統計量を計算することができる。

次のアルゴリズムによって以下のものが実装可能である。

各サーチクエリは木構造を変更しないので多数のクエリを並列的に取り扱うことができる点に注目すべきである。これは、ＧＰＵにタスクをロードすることによって、タスクがさらに加速されることを可能にする。

上記例は、ノードに保存される点の統計量を使用した。しかしながら、上述のように、点の任意の幾何学的特性が、同じやり方、ならびに、このノードに保存される特性の必要なモーメントで、上で説明されたように計算を削減するために使用可能である。例えば、零次モーメント（すなわち点の数）が計算されノードに保存されてよく、任意の特性の一次モーメントが例えば平均値を計算するためにノードに保存されてよい。さらなる実施形態では、二次モーメントが共分散などを計算するために保存されてよい。さらなる次数のモーメントが計算されてノードに予め保存されてもよい。

図３のフローチャートは特徴検出に関し、ステップＳ１１１において特徴検出に必要な統計量が計算される。使用される正確な統計量は、使用される実際の方法に依存し、適切な例が上に与えられた。例えば、ＩＳＳ法が用いられるならば、共分散行列が構築される。これは、上述のようにノードの点または面法線の位置の二次モーメントを予め計算することによって達成される。

１つの領域について、一旦これがなされると、画像全体が解析されたかどうかが判定されるステップＳ１１３へと方法は進む。さらなる領域があるならば、新たな領域Ｒが設定され、評価されるノードが決定される所から手続きが再び仕上げられる。実施形態において、各領域は、所与の半径を持ち、三次元点群／画像の点を中心に置く球体として定義される。全ての点および全ての半径が解析された時に、画像全体が解析されたと判定される。

いくつかの実施形態において、領域のサイズは固定される。他の実施形態において、領域Ｒの半径が最適化される。ここで、ステップＳ１０９以降の処理は、同一の点を中心に置くが異なる半径を持つ領域のために繰り返される。実施形態において、これは、スコア（例えば、領域内に位置する点の共分散行列の第３の固有値によって判定される当該領域の点の「コーナーらしさ（ｃｏｒｎｅｒｎｅｓｓ）」）を計算することによって達成される。特徴検出では、隣接する領域の全てよりも高く得点する領域が選択される。

実際には、以下の条件の双方が満足されるならば２つの球領域は互いに隣接するとみなされる。
− ２つの半径同士の比が１／αとαとの間である。ここで、αは大抵１．５に設定される。
− ２つの球の中心間距離が、大きい方の球の半径のβ倍未満である。βは、大抵０．８に設定される。

これは、同一の半径が全ての球領域について固定されるケース、および、半径が球領域毎に変化するケースの双方に適用される。両ケースにおいて、球領域は、そのスコアがその隣接する球領域の全てのスコアよりも高いならば、維持されるだけである。半径が変えられるケースにおいて、実施形態では点あたりの半径が最適化されない点に注意されたい。寧ろ、様々な半径および様々な点で全ての球領域が計算される。それから、隣接する球領域と比較して最高のスコアを持つ球領域が維持される。

上記方法が、ＧＬＳＬ（ＯｐｅｎＧＬ Ｓｈａｄｉｎｇ Ｌａｎｇｕａｇｅ）を使用し、ＣＰＵおよびＧＰＵを用いてテストされた。それぞれ異なるオブジェクトを表現する、テスト用の１０個の入力三次元点群が、東芝オブジェクト認識データセットから採用された。三次元点群あたりの点の数は、８００００個から１５００００個までに及ぶ。

三次元点群の点から均等にサンプリングされた中心および０から２５ｃｍまで変化する半径を備えるクエリの球領域がランダムに生成された。上記方法は、必要とされる処理時間が少ない。上記方法から得られる、クエリの球領域の半径に亘る平均処理時間のプロットが図５に図示される。興味深いことに、半径が増加するにつれて、ノードの数が実際には減少するので上記方法の速度は減少し始める。

極値では、半径が非常に大きいので全ての点がクエリの球領域に含まれ、上記方法は１つのノード（すなわち、ルートノード）のみを訪れ（ｖｉｓｉｔ）る。

上記方法のＣＰＵバージョンをＧＰＵバージョンと比較すると、図６に図示されるように、ＧＰＵバージョンは８−１３倍速度を改善することが示される。

それは統計的な特徴検出の高速な抽出方法を提供することが上記例から分かる。この方法は特徴検出の効率を改善し、これは大規模データに非常に有用である。

上記方法では、探索木が構築され、所与の球領域内の点がその位置を捜し当てられる。しかしながら、上記方法においてノード毎に、当該ノードの子孫の葉ノードに位置する全ての点がさらに識別される。次に、包含球（バウンディングボール；全ての点を内部に含んでいる球）と、ノード毎のこれらの点からのモーメント・セットとが予め計算される。所与の球領域から幾何学的情報を抽出する場合に、ノードの最小セットの点がクエリの球領域の内部に位置する同一の点集合（ポイントセット）であるように、包含球はノードの最小のセットを素早く識別するために使用される。幾何学的情報は、それから、クエリの球領域なの内部の点集合からではなく識別されたノードのモーメントから間接的に抽出される。

上記方法の処理速度は、クエリごとに発見された点の数には依存せず、発見されたノードの数に依存する。しかしながら、ノードの数は点の数に比べて実際にははるかに少なく、効率における相当な利得につながる。

三次元点群が大きくなるほど、上記方法に見られる速度の利得は大きくなる。例えば、クエリの球領域が三次元点群の全ての点を覆うほど大きいならば、上記方法は、クエリの球領域における全ての点に対立するものとして単一のノードを返す。このケースでの利得はＮ倍（ここで、Ｎは三次元点群の点数である）になり得る。

上記の記述は特徴検出に関するが、この方法は特徴記述子の構築に適用することもできる。

図７は、実施形態に従い、特徴記述子を生成し、および／または、特徴を抽出する、方法を図示するフロー図である。いかなる不要な反復も避けるために、類似の特徴を示すために類似の参照番号が使用される。

図３を参照して説明されたフロー図の場合のように、ステップＳ１０１では三次元点群が得られる。ステップＳ１０３では、三次元点群の点にインデックスを付けるために探索木が構築される。

ステップＳ２０５において、特性のモーメントが各ノードに保存され、特性のモーメントが保存されたノードから下る全てのノードに基づいてモーメントが計算される。この処理は図３のステップＳ１０５を参照してより詳細に説明される。この実施形態では、特徴記述子を判定するために、位置の零次、一次、および二次モーメントがノードに保存される。

ステップＳ２０７では、画像の領域Ｒが解析されるために設定される。記述子を構築する場合に、これは点ｘのあたりの設定サイズであるかもしれない。

ステップＳ２０９では、評価されるノードが決定される。この処理は図３のステップＳ１０９を参照して記述された処理と同じである。

実施形態では、ステップＳ２０５を参照して説明されたようなノードに保存されたモーメントを用いて、ステップＳ２１１において共分散行列を計算することによって記述子が決定されてもよい。記述子は、ステップＳ２１３において決定される。

ステップＳ２１５では、解析が完了したかどうかを調べるためにチェックが行われる。完了していなかったならば、ステップＳ２１７において新たな領域が選択され、ステップＳ２０９においてこの領域内のノードが評価され、処理を繰り返す。

例えば、特徴の位置が点ｘとして既に抽出されていたならば、処理は点ｘを順に踏むことができる。

図８は、特徴の抽出および検出の両方のための方法のフロー図である。いかなる不要な反復も避けるために、類似の特徴を示すために類似の参照番号が使用される。

図３を参照して説明されたフロー図の場合のように、ステップＳ１０１では三次元点群が得られる。ステップＳ１０３では、三次元点群の点にインデックスを付けるために探索木が構築される。

ステップＳ２５５では、特性のモーメントが各ノードに保存され、特性のモーメントが保存されたノードから下る全てのノードに基づいてモーメントが計算される。この処理は、図３のステップＳ１０５を参照してより詳細に説明される。この実施形態では、特徴抽出および記述子の生成のために、位置の零次、一次、および二次モーメントが保存される。

ステップＳ２５７では、点ｘが三次元点群から選択される。結局、三次元点群内の全ての点についてこの方法が行われる。

ステップＳ２５９において、点ｘについて、ｘを中心に置き固定の半径ｒ_１を持つ第１の球Ｂ_１（ｘ）と、同様にｘを中心に置き固定の半径ｒ_２を持つ第２の球Ｂ_２（ｘ）とが構築される。ステップＳ２６１では、球Ｂ_１（ｘ）毎に、３Ｄ方向Ｒ（ｘ）およびスコアｆ（ｘ）が計算される。

実施形態において、特徴抽出方法は、相対的に同じサイズのオブジェクト（すなわち、それらの外観は既知の半径ｒ_０の３Ｄ球によって境界を定められ得る）を認識するために用いられる。ここで、ｒ_１はｒ_０のγ倍（ここでγは大抵０．３に設定される）に決定され、ｒ_２はｒ_１のβ倍（ここでβは大抵０．８に設定される）に決定される。γおよびβの値は必要に応じて変更することができる。

所与の点ｘについての３Ｄ方向Ｒ（ｘ）およびスコアｆ（ｘ）は、Ｂ_１（ｘ）内部に位置する点の数ｎ（ｘ）、Ｂ_１（ｘ）内部に位置する全ての点の位置の平均ｍ（ｘ）および共分散行列Ｃ（ｘ）を計算することによって、計算される。点数は、保存された零次モーメントから判定することができる。

共分散行列の３つの固有値ｖ_１（ｘ）、ｖ_２（ｘ）およびｖ_３（ｘ）は、それらの関連する固有ベクトルｅ_１（ｘ）、ｅ_２（ｘ）およびｅ_３（ｘ）と共に、計算されて降順にソートされる。固有ベクトルｅ_ｉ（ｘ）毎（ここでｉ＝１，．．．，３）に、ｅ_ｉ（ｘ）およびｍ（ｘ）−ｘのドット積が負値であるならばｅ_ｉ（ｘ）＝−ｅ_ｉ（ｘ）と設定することによりその方向が反転される。３つの固有ベクトルは、それから、３Ｄ方向：Ｒ（ｘ）＝（ｅ_１（ｘ），ｅ_２（ｘ），ｅ_３（ｘ））として割り当てられる。

次に、第３の固有値ｖ_３（ｘ）がスコアｆ（ｘ）として割り当てられる。直観的には、スコアｆ（ｘ）はＢ_１（ｘ）の点の面がどのくらい厚いかを示す。この方法によって検出される特徴は、大抵は、コーナー、エッジ、および、２つ以上のオブジェクトの交差する領域に対応する。

ステップＳ２６３において、Ｂ_２（ｘ）内部に位置する全ての隣接する点に比べてスコアｆ（ｘ）が大きい点ｘが選択される。ステップＳ２６５では、選択された特徴がロバストであるかどうかチェックされる。実施形態では、以下の要件を満足しない特徴は削除される。
・ｎ（ｘ）≦θ_１：（θ_１のデフォルト値は５である）Ｂ_１（ｘ）の点の数が少なすぎる。
・ｖ_２（ｘ）／ｖ_１（ｘ）≦θ_２：（θ_２のデフォルト値は０．９５である）ｖ_２（ｘ）がｖ_１（ｘ）に近すぎることはｅ_１（ｘ）およびｅ_２（ｘ）の計算を不安定にする。
・ｖ_３（ｘ）／ｖ_２（ｘ）≦θ_３：（θ_３のデフォルト値は０．９５である）ｖ_３（ｘ）がｖ_２（ｘ）に近すぎることはｅ_２（ｘ）およびｅ_３（ｘ）の計算を不安定にする。

ステップＳ２６７において、三次元点群の全ての点が解析されたかどうかを調べるためにチェックが行われる。否であるならば、新たな点ｘがステップＳ２７３において選択され、処理はステップＳ２５９にループバックする。

上記実施形態の方法は、非常に少ない処理時間を必要とする。それは、現在１５フレーム／秒で作動しており、リアルタイムアプリケーションに適している。別の利点は、カラー情報を必要としない点である。故に、それは、カラーが弁別的特徴でない状況（例えば、低テクスチャオブジェクトまたは光の不足した状況でキャプチャーされたオブジェクト）に適している。

図９は、実施形態に従う、三次元点群をフィルタリングする方法を図示するフロー図である。いかなる不要な反復も避けるために、類似の特徴を示すために類似の参照番号が使用される。

図３を参照して説明されたフロー図の場合のように、ステップＳ１０１では三次元点群が得られる。ステップＳ１０３では、三次元点群の点にインデックスを付けるために探索木が構築される。

ステップＳ３０５において、特性のモーメントが各ノードに保存され、特性のモーメントが保存されるノードから下る全てのノードに基づいてモーメントが計算される。この処理は、図３のステップＳ１０５を参照してより詳細に説明される。この実施形態において、フィルタリングのために、子孫のノードの位置の平均が保存されるように一次モーメントがノードに保存される。

このフィルタリング方法において、各点が選択され、点の位置が当該点の周囲の領域の平均と置き換えられる。ステップＳ３０７において、フィルタリングされる点が選択される。解析される三次元点群内の各点は、処理中にフィルタリングされる。故に、この実施形態において、フィルタリングされる点は順に選択される。

ステップＳ３０９では点の周りの領域が設定され、これは当該点あたりを中心に置く球である。この実施形態において、球は固定の半径を持つ。半径は、必要とされるフィルタリングレベルに依存して設定される。半径は、画像化される三次元点群全体について固定される。実施形態において、半径は以下のように決定される。まず、三次元点群の任意の２つの点間の最短の非零距離が、全ての点の組み合わせ（ポイントペア）に網羅的に目を通すことにより確定される。この最短距離をｄ_０とする。それから、半径はｄ_０のλ倍（ここでλは大抵は５に設定される）に設定される。

ステップＳ３１１では、評価されるノードが決定される。この処理は、図３のステップＳ１０９を参照して記述された処理と同じである。ステップＳ３１３では、ステップＳ３０５を参照して説明されたようなノードに保存された一次モーメントを用いて平均が計算される。ステップＳ３１５において、各点の位置の値は、計算された平均に置き換えられる。ステップＳ３１７では、処理が全ての点について完了したかどうかを調べるためにチェックがなされる。否であれば、ステップＳ３１９に新たな点がおいて選択され、ステップＳ３０９において当該点の周囲に領域が構築される。それから、処理は、全ての点について完了するまで繰り返される。

上記例では、特性は点の位置である。しかしながら、他の特性を同じ方法で取り扱うことが可能である。例えば、特性として保存されているカラーの一次モーメントを用いて、点のカラーを上述のようにフィルタリングすることが可能である。多数の特性の平均または他の統計的尺度が計算できるように多数の特性のモーメントがノードに保存されてよいことに注意されたい。

他のフィルタリング方法が使用されてもよく、例えば、平均は、ステップＳ３１３まで図Ｂを参照して記述されるように計算されてもよい。しかしながら、ステップＳ３１５では、点における特性の平均からの差分が計算されてよい。差分が所定の値よりも大きければ、点は破棄されるか平均値に置き換えられてよい。

図１０は、三次元点群サブサンプリングの方法を図示するフロー図である。この方法は、図９を参照して記述されたフィルタリング方法に基づいている。いかなる不要な反復も避けるために、類似の特徴を示すために類似の参照番号が使用される。フィルタリングされた三次元点群がステップＳ３２１において生成された後に、フィルタリングされた三次元点群から点がランダムにサンプリングされ、サブサンプリングされた三次元点群を生み出す。

サブサンプリングされた三次元点群はステップＳ１０１において受け取られる三次元点群に比べてサンプル数が少ないので、図１０を参照して記述される上記方法は三次元点群圧縮方法でもある。

上記例は点のランダムサンプリングに言及したが、他のサンプリング方法が使用可能である。さらに、図Ｂを参照して記述されたフィルタリング方法は、例えば、点が平均から所定の距離を超えている場合に点の値を平均に置き換えるだけで変更することが可能であるし、平均から所定の距離より大きい点を破棄することもできる。

図１１は、三次元点群の密度推定を図示するフロー図である。いかなる不要な反復も避けるために、類似の特徴を示すために類似の参照番号が使用される。

図３を参照して説明されたフロー図の場合のように、ステップＳ１０１では三次元点群が得られる。ステップＳ１０３では、三次元点群の点にインデックスを付けるために探索木が構築される。

ステップＳ４０５において、特性のモーメントが各ノードに保存され、特性のモーメントが保存されるノードから下る全てのノードに基づいてモーメントが計算される。この処理は、図３のステップＳ１０５を参照してより詳細に説明される。この実施形態では、密度推定のために、一次モーメントがノードに保存され、故に、子孫ノードの数が各ノードに保存される。

ステップＳ４０７において、密度が推定される領域が選択される。ステップＳ４０９では、図３のステップＳ１０９を参照して記述されたのと同じやり方で、評価されるノードが決定される。それから、ステップＳ４１１において、ノードに保存された零次モーメントを用いて領域内の点の総数が計算される。密度を推定するために、ステップＳ４１３において領域の体積によって点の数が除算され、ステップＳ４１５において密度が出力される。

図１２は、三次元点群から法線を推定する方法を図示するフロー図である。いかなる不要な反復も避けるために、類似の特徴を示すために類似の参照番号が使用される。

図３を参照して説明されたフロー図の場合のように、ステップＳ１０１では三次元点群が得られる。ステップＳ１０３では、三次元点群の点にインデックスを付けるために探索木が構築される。

ステップＳ５０５において、特性のモーメントが各ノードに保存され、特性のモーメントが保存されるノードから下る全てのノードに基づいてモーメントが計算される。この処理は、図３のステップＳ１０５を参照してより詳細に説明される。この実施形態では、法線推定のために、子孫ノードの点の位置からの零次、一次および二次モーメントが各ノードに保存される。

ステップＳ５０７において、法線が計算される点が選択される。ステップＳ５０９では、点の周囲に領域が構築される。実施形態において、これは固定の半径を持つ球領域である。実施形態において、半径は以下のように決定される。まず、三次元点群の任意の２つの点間の最短の非零距離が、全ての点の組み合わせに網羅的に目を通すことにより確定される。この最短距離をｄ_０とする。それから、半径はｄ_０のλ倍（ここでλは大抵は５に設定される）に設定される。

ステップＳ５１１において、図３のステップＳ１０９を参照して記述されたのと同じ方法で、評価されるノードが決定される。ステップＳ５１３では、零次、一次および二次モーメントを用いて領域内の全ての点の共分散行列が計算される。ステップＳ５１５では、共分散行列の第３の固有ベクトルが法線として推定される。

ステップＳ５１７において、全ての点について処理が行われたかどうかを調べるためにチェックが行われる。否であれば、法線の推定が必要とされるさらなる点が存在し、新たな点がステップＳ５１９で選択され、新たな領域が構築されるステップＳ５０９へと処理はループバックする。ステップＳ５２１において、推定された法線が出力される。

さらなる実施形態において、法線の零次および一次モーメントをノードに保存することにより、法線ベクトルの平均が計算される。

図１３は、三次元点群の面の方向の推定方法を図示するフロー図である。いかなる不要な反復も避けるために、類似の特徴を示すために類似の参照番号が使用される。

図３を参照して説明されたフロー図の場合のように、ステップＳ１０１では三次元点群が得られる。ステップＳ１０３では、三次元点群の点にインデックスを付けるために探索木が構築される。

ステップＳ６０５において、特性のモーメントが各ノードに保存され、特性のモーメントが保存されるノードから下る全てのノードに基づいてモーメントが計算される。この処理は、図３のステップＳ１０５を参照してより詳細に説明される。この実施形態では、方向推定のために、子孫ノードの点位置からの零次、一次および二次モーメントが各ノードに保存される。

ステップＳ６０７では、方向が計算される点が選択される。ステップＳ６０９では、領域が点の周囲に構築される。実施形態において、これは固定の半径を持つ球領域である。実施形態において、各点における方向が必要とされる場合に、半径は以下のように決定される。まず、三次元点群の任意の２つの点間の最短の非零距離が、全ての点の組み合わせに網羅的に目を通すことにより確定される。この最短距離をｄ_０とする。それから、半径はｄ_０のλ倍（ここでλは大抵は５に設定される）に設定される。

特徴の方向を判定することが望まれる場合に、半径は、例えば図８を参照して記述されたタイプの特徴検出方法において決定された球領域から決定することができる。

ステップＳ６１１において、評価されるノードは、図３のステップＳ１０９を参照して記述されたのと同じやり方で決定される。ステップＳ６１３において、保存された零次、一次および二次モーメントを用いて、領域内の全てのポイントの共分散行列が計算される。ステップＳ６１５では、方向は、共分散行列の３つの固有ベクトルとして推定される。

ステップＳ６１７において、全ての点について処理が行われたかどうかを調べるためにチェックが行われる。否であれば、方向の推定が必要とされるさらなる点が存在し、新たな点がステップＳ６１９で選択され、新たな領域が構築されるステップＳ６０９へと処理はループバックする。ステップＳ６２１において、推定された方向が出力される。

実施形態において、図３乃至１３において教示された上記方法のいずれも、例えば携帯電話機、タブレット、ウェアラブルテクノロジなどのモバイルデバイスにおいて実装することができる。係る方法は、例えば拡張現実、ジェスチャ認識、オブジェクト認識、オブジェクト位置合わせ、オブジェクトまたはモバイルデバイスの姿勢推定、ナビゲーションおよび／またはゲームなどの他のアプリケーションの一部を形成できる。

いくつかの実施形態を説明したが、これらの実施形態は、例として提示したものであり、発明の範囲を限定することは意図していない。これら新規な方法およびシステムは、その他の様々な形態で実施されることが可能であり、発明の要旨を逸脱しない範囲で、種々の省略、置き換え、変更を行うことができる。これら実施形態やその変形は、発明の範囲や要旨に含まれるとともに、特許請求の範囲に記載された発明とその均等の範囲に含まれる。

Claims (20)

1. 三次元点群を解析する方法であって、
   前記方法は、複数の点を含む三次元点群を受け取ることを具備し、
   各点は、画像内の空間的な点を表し、
   前記方法は、最下位レベルに複数の葉ノードを含む、階層的な探索木に点を配置することを具備し、
   各葉ノードは前記三次元点群の点に対応し、探索木は複数の階層レベルを備え、当該階層レベルの各々にノードを伴い、ノードは枝によって階層レベル間で互いに接続され、子孫ノードの特性の少なくとも１つのモーメントが各ノードに保存され、
   前記方法は、領域の中に入る点が最小数のノードによって表されるように、子孫の葉ノードの全てが前記領域内に含まれる最上位レベルのノードを特定し、前記領域内に完全に含まれるサブツリーのない点に対しては葉ノードを選択し、前記領域内の点を表すノードに統計的演算を行うことによって、領域内に位置する点の幾何学的情報を判定することを具備し、
   前記統計的演算は、識別されたノード内に保存される特性のモーメントから判定される、
   方法。
2. 前記特性は、位置、法線ベクトル、カラー、曲率、強度または透明度から選択される少なくとも１つである、請求項１記載の方法。
3. 前記幾何学的情報は、点の数、位置の平均、カラーの平均、法線ベクトルの平均、強度の平均、位置の共分散、法線ベクトルの共分散、カラーの共分散、曲率の分散および強度の分散から選択される少なくとも１つである、請求項１記載の方法。
4. 前記モーメントは、零次、一次、二次または任意のより高次のモーメントから選択される、請求項１記載の方法。
5. 点の位置の零次および一次モーメントが前記ノードに保存され、
   前記方法は、三次元点群内の全ての点の位置を隣接する点の平均に置き換えることにより三次元点群をフィルタリングするように構成され、
   前記隣接する点は、前記領域によって定義される距離の内に入り、
   前記幾何学的情報は、保存された零次および一次モーメントから計算される、前記隣接する点の平均である、
   請求項１記載の方法。
6. 点の位置の零次モーメントが前記ノードに保存され、
   前記幾何学的情報は、領域内の点の数であり、
   前記方法は、前記領域のサイズによって除算される、保存された零次モーメントからの前記領域内の点の数を用いて三次元点群の密度を推定することをさらに具備する、
   請求項１記載の方法。
7. 点の位置の零次、一次および二次モーメントが前記ノードに保存され、
   前記幾何学的情報は、三次元点群上で選択された点の法線ベクトルであり、
   前記法線ベクトルは、ノード内に保存されたモーメントから、前記選択された点の周囲の領域内の点の共分散行列を計算することによって判定され、
   前記方法は、前記共分散行列の第３の固有ベクトルから法線を判定することをさらに具備する、
   請求項１記載の方法。
8. 点の位置の零次、一次および二次モーメントが前記ノードに保存され、
   前記幾何学的情報は、選択された点における三次元点群の面の方向であり、
   前記方向は、ノード内に保存されたモーメントから、前記選択された点の周囲の領域内の点の共分散行列を計算し、前記共分散行列の３つの固有ベクトルから前記方向を導出することによって、判定される、
   請求項１記載の方法。
9. 点の位置の零次、一次および二次モーメントが前記ノードに保存され、
   前記幾何学的情報は、三次元点群内の特徴の位置であり、
   前記方法は、選択された点の周囲に定義される領域内の点についてのノード内に保存されたモーメントから共分散行列を計算することと、前記共分散行列の固有値からスコアを決定することとをさらに具備し、
   特徴は、当該特徴のスコアを基準として、前記選択されたポイントに位置するとみなされる、
   請求項１記載の方法。
10. 前記共分散行列は、３つの固有値を持ち、
    最小の固有値が前記スコアとして割り当てられる、
    請求項９記載の方法。
11. 前記領域は、第１の半径を持つ第１の球であり、
    選択された点は、当該点の周囲に第１の球と第２の半径を持つ第２の球とを構築することによって解析され、
    前記第２の半径は前記第１の半径よりも大きく、
    選択された点についての第２の点の中の三次元点群内の点の各々は、これらの点の周囲に第１の球を構築し、各球について前記スコアを計算することによって解析される、
    請求項９記載の方法。
12. 特徴の位置は、前記第１の球について計算された最大のスコアを伴う点にあると判定される、請求項１１記載の方法。
13. 識別された特徴について記述子が導出され、
    前記記述子は、特徴が位置する点について判定された第１の球および当該第１の球についての３Ｄ方向である、
    請求項９記載の方法。
14. 点の位置の零次、一次および二次モーメントが前記ノードに保存され、
    前記幾何学的情報は、三次元点群内の特徴の記述子であり、
    前記方法は、
    選択された点の周囲に定義される領域内の点についてのノード内に保存されたモーメントから共分散行列を計算することと、
    前記共分散行列から記述子を判定することと
    をさらに具備する、
    請求項１記載の方法。
15. 前記方法は、点のマップを解析して領域についての特徴記述子を生み出すために構成され、
    前記特徴記述子は、前記幾何学的情報を含む、
    請求項１記載の方法。
16. フィルタリングされた三次元点群をサンプリングすることをさらに具備する、請求項５記載の方法。
17. オブジェクトの認識、および／または、位置合わせの方法であって、
    前記方法は、請求項１４の方法に従って三次元点群を解析することを具備し、
    前記方法は、特徴記述子を複数のオブジェクトについての特徴記述子のデータベースと比較することをさらに具備する、
    方法。
18. フィルタリングされた三次元点群をサンプリングすることを具備し、
    前記フィルタリングされた三次元点群は、請求項５の方法に従って判定される、
    三次元点群圧縮方法。
19. 三次元点群を解析するように構成されたシステムであって、
    前記システムは、複数の点を含む三次元点群を受け取るのに適合した三次元点群受信ユニットを具備し、
    各点は、画像内の空間的な点を表し、
    前記システムは、最低レベルに複数の葉ノードを含む、階層的な探索木に点を配置するのに適合したプロセッサを具備し、
    各葉ノードは前記三次元点群の点に対応し、探索木は複数の階層レベルを備え、当該階層レベルの各々にノードを伴い、ノードは枝によって階層を通り抜けて互いに垂直的に接続され、子孫ノードの特性の少なくとも１つのモーメントが各ノードに保存され、
    前記プロセッサは、領域の中に入る点が最小数のノードによって表されるように、子孫の葉ノードの全てが前記領域内に含まれる最高レベルのノードを識別し、前記領域内に完全に含まれるサブツリーのない点に対して葉ノードを選択し、前記領域内の点を表すノードに統計的演算を行うことによって、領域内に位置する点の幾何学的情報を判定および出力するようにさらに適合され、
    前記統計的演算は、識別されたノード内に保存される特性のモーメントから判定される、
    システム。
20. 請求項１の方法を行うようにコンピュータを制御するためのコンピュータ可読命令を搬送する記録媒体。