(57)【要約】      （修正有）【課題】点群データ同士のマッチング関係を確定するための方法及び装置を提供する。【解決手段】点群データ同士のマッチング関係を確定するための方法は、同じ対象物をオブジェクトとして収集された点群データである、第１の点群データに関連する第１の特徴及び同様に第２の点群データに関連する第２の特徴を抽出するステップと、第１の特徴及び第２の特徴に対して特徴マッチングを行うステップと、特徴マッチングに基づいて、第１の点群データと第２の点群データ間のマッチング関係を確定するステップと、を含む。【選択図】図２
2019133646.tif 000002
【特許請求の範囲】
【請求項１】
点群データ同士のマッチング関係を確定するための方法であって、
第１の点群データに関連する第１の特徴及び第２の点群データに関連する第２の特徴を抽出するステップであって、前記第１の点群データ及び前記第２の点群データは、同じ対象物をオブジェクトとして収集されたものである、ステップと、
前記第１の特徴及び前記第２の特徴に対して特徴マッチングを行うステップと、
前記特徴マッチングに基づいて、前記第１の点群データと前記第２の点群データ間のマッチング関係を確定するステップと、を含む点群データ同士のマッチング関係を確定するための方法。
【請求項２】
請求項１において、
前記第１の特徴及び前記第２の特徴のそれぞれは、少なくとも特徴点と前記特徴点に対応する法線ベクトルとを含むことを特徴とする点群データ同士のマッチング関係を確定するための方法。
【請求項３】
請求項１において、
前記第１の特徴及び前記第２の特徴を抽出するステップは、
前記第１の点群データから第１の地面点群データを確定し、前記第１の地面点群データの中心点及び対応する法線ベクトルを前記第１の特徴の特徴点及び対応する法線ベクトルと確定するステップと、
前記第２の点群のデータから第２の地面点群データを確定し、前記第２の地面点群データの中心点及び対応する法線ベクトルを前記第２の特徴の特徴点及び対応する法線ベクトルと確定するステップとを含むことを特徴とする点群データ同士のマッチング関係を確定するための方法。
【請求項４】
請求項１において、
前記第１の特徴及び前記第２の特徴を抽出するステップは、
前記第１の点群データから第１の候補平面点群データを確定し、前記第１の候補平面点群データに基づいて、前記第１の特徴を確定するステップと、
前記第２の点群のデータから第２の候補平面点群データを確定し、前記第２の候補平面点群データに基づいて、前記第２の特徴を確定するステップとを含むことを特徴とする点群データ同士のマッチング関係を確定するための方法。
【請求項５】
第４項において、
前記第１の候補平面点群データに基づいて、前記第１の特徴を確定するステップは、
前記第１の候補平面点群データにおけるスレッド（Ｔｈｒｅａｄ）の中断ポイントを確定するステップと、
前記中断ポイントに基づいて、前記スレッドに対して分割を行うステップと、
分割された前記スレッドに対してクラスタリングを行うステップと、
前記第１の候補平面点群データに平面点群データが含まれていることを示すクラスタリング結果に応答して、前記平面点群データの中心点及び対応する法線ベクトルを前記第１の特徴の特徴点及び対応する法線ベクトルと確定するステップとを含むことを特徴とする点群データ同士のマッチング関係を確定するための方法。
【請求項６】
請求項３又は請求項５において、
前記第１の特徴及び前記第２の特徴に対して特徴マッチングを行うステップは、
前記第１の特徴及び前記第２の特徴を同じ座標系に変換するステップと、
前記第１の特徴の特徴点と前記第２の特徴の特徴点との間の距離を確定するステップと、
前記距離が距離閾値よりも小さいことに応答して、前記第１の特徴の法線ベクトルと前記第２の特徴の法線ベクトルとの間の差を確定するステップと、
前記差が差閾値よりも小さいことに応答して、前記第１の特徴と前記第２の特徴がマッチングされると確定するステップとを含むことを特徴とする点群データ同士のマッチング関係を確定するための方法。
【請求項７】
請求項１において、
前記第１の特徴及び前記第２の特徴を抽出するステップは、
前記第１の点群データから第１の候補柱体点群データを確定し、前記第１の候補柱体点群データに基づいて、前記第１の特徴を確定するステップと、
前記第２の点群のデータから第２の候補柱体点群データを確定し、前記第２の候補柱体点群データに基づいて、前記第２の特徴を確定するステップとを含むことを特徴とする点群データ同士のマッチング関係を確定するための方法。
【請求項８】
請求項７において、
前記第１の候補柱体点群データに基づいて、前記第１の特徴を確定するステップは、
前記第１の候補柱体点群データにおける、主な方向と法線ベクトルとの間の夾角が夾角閾値よりも小さい点群データに対してクラスタリングを行うステップと、
前記第１の候補柱体点群データに柱体点群データが含まれていることを示すクラスタリング結果に応答して、前記柱体点群データの中心点、法線ベクトル及び半径を、前記第１の特徴の特徴点、法線ベクトル及び半径と確定するステップとを含むことを特徴とする点群データ同士のマッチング関係を確定するための方法。
【請求項９】
請求項８において、
前記第１の特徴及び前記第２の特徴に対して特徴マッチングを行うステップは、
前記第１の特徴及び前記第２の特徴を同じ座標系に変換するステップと、
前記第１の特徴の特徴点と前記第２の特徴の特徴点との距離を確定するステップと、
前記距離が距離閾値よりも小さいことに応答して、前記第１の特徴の法線ベクトル及び半径と、前記第２の特徴の法線ベクトル及び半径との間の差を確定するステップと、
前記差が差閾値よりも小さいことに応答して、前記第１の特徴と前記第２の特徴がマッチングされると確定するステップとを含むことを特徴とする点群データ同士のマッチング関係を確定するための方法。
【請求項１０】
請求項１において、
前記第１の点群データと前記第２の点群データ間のマッチング関係を確定するステップは、
前記第１の特徴と前記第２の特徴がマッチングされたことに応答して、前記第１の点群データと前記第２の点群データ間のマッチング関係を確定するステップを含むことを特徴とする点群データ同士のマッチング関係を確定するための方法。
【請求項１１】
点群データとの間のマッチング関係を確定するための装置であって、
第１の点群データに関連する第１の特徴及び第２の点群データに関連する第２の特徴を抽出するように構築される抽出モジュールであって、前記第１の点群データ及び前記第２の点群データは、同じ対象物をオブジェクトとして収集されたものである、抽出モジュールと、
前記第１の特徴及び前記第２の特徴に対して特徴マッチングを行うように構築されるマッチングモジュールと、
前記特徴マッチングに基づいて、前記第１の点群データと前記第２の点群データ間のマッチング関係を確定するように構築される確定モジュールとを含む点群データとの間のマッチング関係を確定するための装置。
【請求項１２】
請求項１１において、
前記第１の特徴及び前記第２の特徴のそれぞれは、少なくとも特徴点と前記特徴点に対応する法線ベクトルとを含むことを特徴とする点群データ同士のマッチング関係を確定する装置。
【請求項１３】
請求項１１において、
前記抽出モジュールは、
前記第１の点群データから第１の地面点群データを確定し、前記第１の地面点群データの中心点及び対応する法線ベクトルを前記第１の特徴の特徴点及び対応する法線ベクトルと確定し、
前記第２の点群のデータから第２の地面点群データを確定し、前記第２の地面点群データの中心点及び対応する法線ベクトルを前記第２の特徴の特徴点及び対応する法線ベクトルと確定するように、さらに構築されることを特徴とする点群データ同士のマッチング関係を確定する装置。
【請求項１４】
請求項１１において、
前記抽出モジュールは、
前記第１の点群データから第１の候補平面点群データを確定し、前記第１の候補平面点群データに基づいて、前記第１の特徴を確定し、
前記第２の点群のデータから第２の候補平面点群データを確定し、前記第２の候補平面点群データに基づいて、前記第２の特徴を確定するように、さらに構築されることを特徴とする点群データ同士のマッチング関係を確定する装置。
【請求項１５】
請求項１４において、
前記抽出モジュールは、
前記第１の候補平面点群データにおけるスレッド（Ｔｈｒｅａｄ）の中断ポイントを確定し、
前記中断ポイントに基づいて、前記スレッドに対して分割を行い、
分割された前記スレッドに対してクラスタリングを行い、
前記第１の候補平面点群データに平面点群データが含まれていることを示すクラスタリング結果に応答して、前記平面点群データの中心点及び対応する法線ベクトルを前記第１の特徴の特徴点及び対応する法線ベクトルと確定するステップとを含むことを特徴とする点群データ同士のマッチング関係を確定するように、さらに構築されることを特徴とする点群データ同士のマッチング関係を確定する装置。
【請求項１６】
請求項１３項又は請求項１５において、
前記マッチングモジュールは、
前記第１の特徴及び前記第２の特徴を同じ座標系に変換し、
前記第１の特徴の特徴点と前記第２の特徴の特徴点との間の距離を確定し、
前記距離が距離閾値よりも小さいことに応答して、前記第１の特徴の法線ベクトルと前記第２の特徴の法線ベクトルとの間の差を確定し、
前記差が差閾値よりも小さいことに応答して、前記第１の特徴と前記第２の特徴がマッチングされると確定するように、さらに構築されることを特徴とする点群データ同士のマッチング関係を確定する装置。
【請求項１７】
請求項１１において、
前記抽出モジュールは、
前記第１の点群データから第１の候補柱体点群データを確定し、前記第１の候補柱体点群データに基づいて、前記第１の特徴を確定し、
前記第２の点群のデータから第２の候補柱体点群データを確定し、前記第２の候補柱体点群データに基づいて、前記第２の特徴を確定するように、さらに構築されることを特徴とする点群データとの間のマッチング関係を確定するための装置。
【請求項１８】
請求項１７において、
前記抽出モジュールは、
前記第１の候補柱体点群データにおける、主な方向と法線ベクトルとの間の夾角が夾角閾値よりも小さい点群データに対してクラスタリングを行い、
前記第１の候補柱体点群データに柱体点群データが含まれていることを示すクラスタリング結果に応答して、前記柱体点群データの中心点、法線ベクトル及び半径を、前記第１の特徴の特徴点、法線ベクトル及び半径と確定するように、さらに構築されることを特徴とする点群データ同士のマッチング関係を確定する装置。
【請求項１９】
請求項１８において、
前記マッチングモジュールは、
前記第１の特徴及び前記第２の特徴を同じ座標系に変換し、
前記第１の特徴の特徴点と前記第２の特徴の特徴点との距離を確定し、
前記距離が距離閾値よりも小さいことに応答して、前記第１の特徴の法線ベクトル及び半径と、前記第２の特徴の法線ベクトル及び半径との間の差を確定し、
前記差が差閾値よりも小さいことに応答して、前記第１の特徴と前記第２の特徴がマッチングされると確定するように、さらに構築されることを特徴とする点群データ同士のマッチング関係を確定する装置。
【請求項２０】
請求項１１において、
前記確定モジュールは、
前記第１の特徴と前記第２の特徴がマッチングされたことに応答して、前記第１の点群データと前記第２の点群データ間のマッチング関係を確定するように、さらに構築されることを特徴とする点群データ同士のマッチング関係を確定する装置。
【請求項２１】
１つまたは複数のプロセッサと、
１つまたは複数のプログラムを記憶するための記憶装置とを含み、
前記１つまたは複数のプログラムが前記１つまたは複数のプロセッサによって実行される場合、請求項１から請求項１０のうちいずれか１項の方法を実現する機器。
【請求項２２】
コンピュータプログラムが記憶されているコンピュータ読み取り可能な記憶媒体であって、
前記コンピュータプログラムがプロセッサによって実行される場合、請求項１から請求項１０項のうちいずれか１項の方法を実現するコンピュータ読み取り可能な記憶媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本願の実施形態は、一般的に点群データ処理技術分野に関するものであり、より具体的に、点群データ同士のマッチング関係を確定するための方法及び装置に関するものである。
【背景技術】
【０００２】
高精度地図マッピングは、３次元地図の環境を正確に認識する必要がある。同時に、広い意味では、自律走行車もシミュレーションを目的とし、３次元動的目標を認識する必要がある。また、部品の製造、品質検査、多様化ビュー、漫画創作、３次元マッピングとマスコミュニケーション手段などの分野にも各種の３次元対象物を認識し比較する必要がある。現在、前記のような分野では、３次元対象物の認識は、一般的に点群データを収集して分析を行うことによって実現されることができる。
【０００３】
点群は、一般的に、大量のポイントのセットを指す。高精度地図マッピングと自律走行車などの分野では、点群は、一般的に、道路や周辺環境に存在する表面特性を備える大量のポイントのセットを指し、これにより道路、ガードレール、看板などの物体の表面形状を表示することができる。点群データは、点群のデータを表示するためのものであり、点群データには点群の中の各ポイントが備える、例えば３次元座標およびその他のプロパティ（例えば、光の強さ、ＲＧＢカラー、系の措置、奥行きなど）が記録される。点群データは、例えば、３次元スキャン装置を使用して点群収集環境をスキャンして取得することができ、これらの３次元スキャン装置は、レーザーレーダー、ステレオカメラ、飛行時間（ｔｉｍｅ−ｏｆ−ｆｌｉｇｈｔ）カメラなどを含むことができる。これらのデバイスは、ジャンドンファ方法で物体表面の大量のポイントの情報を測定し、次いで、任意のデータファイル形式の形式で点群データを出力することができる。
【０００４】
取得した点群データを利用して次の操作を行う場合、特に動的にまたは何度も取得した点群をオブジェクトとして総合的に使用する場合、動的目標点群シャドウ除去は、一つの技術ポイントであると考えられる。点群データは、点群を表示するのに使用されるので、点群の間のマッチング関係の確定と点群データ同士のマッチング関係の確定は互いに関連している。点群データ同士のマッチング関係を確定するための繰り返し最近点（ＩＣＰ）アルゴリズムのような従来の方法は、ほぼすべての点群データ（つまり、点群の中のほぼすべてのポイントの関連データ）を利用して、異なる点群データの間のマッチング関係を確定する。上述した従来の方法において、点群データ同士のマッチング関係を確定するために、同じ対象物を対象にする点群データから点群の中の特定の特徴を備える点を人為的に抽出する。しかしながら、人為的な抽出は、点群データの要求が非常に厳しく、点群の中のポイントのデータが十分に大きく、収集の精度が十分に高い場合にのみ、例えば点群の中の対応するコーナーなどの一部の詳細を見つけることができ、これは大量の人力コストを必要とする。
【０００５】
同時に、点群の中のポイントは、通常に量が非常に膨大なので、異なる点群データの間のマッチング関係を確定するとき、上述した従来の方法は、大量のコンピューティングを稠密的に進める必要があり、これにより、大量の時間とメモリ空間を消費することになる。
【０００６】
また、例えば車両搭載型レーザーレーダーを用いて車両搭載型レーザー点群を取得する場合、取得した車両搭載型レーザー点群は、非剛性変形の特徴を備える。しかしながら、繰り返し最近点アルゴリズムなどの上述した従来の方法は、一般的にただ剛性変形の特徴を備える点群にのみ適用される。したがって、大規模な車両搭載型レーザー点群データの間のマッチング関係を確定するに当たり、上述した従来の方法を利用することにより、良好な精度を備えるように確保することができない。これにより、点群データ同士のマッチング関係を確定する時の非剛性変換の要求を満足することもできなくなる。
【０００７】
また、点群データ同士のマッチング関係を確定するに当たり、上述した従来の方法は、すべて同時に６つの自由度をオブジェクトとしてマッチング関係を確定し、これは相対的に高い演算速度と相対的に大きなメモリ空間を必要とする。
【発明の概要】
【発明が解決しようとする課題】
【０００８】
本願の実施形態は、点群データ同士のマッチング関係を確定するための方法及び装置を提供する。
【課題を解決するための手段】
【０００９】
第一の局面として、点群データ同士のマッチング関係を確定するための方法であって、第１の点群データに関連する第１の特徴及び第２の点群データに関連する第２の特徴を抽出するステップであって、前記第１の点群データ及び前記第２の点群データは、同じ対象物をオブジェクトとして収集されたものである、ステップと、前記第１の特徴及び前記第２の特徴に対して特徴マッチングを行うステップと、前記特徴マッチングの結果に基づいて、前記第１の点群データと前記第２の点群データ間のマッチング関係を確定するステップと、を含む。
【００１０】
第二の局面として、点群データとの間のマッチング関係を確定するための装置であって、第１の点群データに関連する第１の特徴及び第２の点群データに関連する第２の特徴を抽出するように構築される抽出モジュールであって、前記第１の点群データ及び前記第２の点群データは、同じ対象物をオブジェクトとして収集されたものである、抽出モジュールと、前記第１の特徴及び前記第２の特徴に対して特徴マッチングを行うように構築されるマッチングモジュールと、前記特徴マッチングの結果に基づいて、前記第１の点群データと前記第２の点群データ間のマッチング関係を確定するように構築される確定モジュールとを含む。
【００１１】
第三の局面として、機器であって、１つまたは複数のプロセッサと、１つまたは複数のプログラムを記憶するための記憶装置とを含み、前記１つまたは複数のプログラムが前記１つまたは複数のプロセッサによって実行される場合、第一の局面の方法を実現する。
【００１２】
第四の局面として、コンピュータプログラムが記憶されているコンピュータ読み取り可能な記憶媒体であって、前記コンピュータプログラムがプロセッサによって実行される場合、第一の局面の方法を実現する。
【００１３】
発明の内容の部分で説明した内容は、本願の実施形態のポイントまたは重要な特徴を限定しようとするものではなく、本願の範囲を限定するためのものではないことを理解されたい。本願の他の特徴は、下の説明を介して容易に理解できるだろう。
【図面の簡単な説明】
【００１４】
以下の図面による非限定的な実施形態についての詳細な説明を読み、参照することにより、本願の他の特徴、目的及び利点がより明らかになる。
【図１】図１は、本願の複数の実施形態を実現可能な例示的な環境の概略図１００を示す。
【図２】図２は、本願の実施形態による点群データ同士のマッチング関係を確定するための方法２００のフローチャートを示す。
【図３】図３は、本願の実施形態による点群データ同士のマッチング関係を確定する装置３００のブロック図を示す。
【図４】図４は、本願の実施形態を実施可能な例示的機器４００のブロック概略図を示す。各図面において、同一または対応する符号は、同一または対応する部分を表示する。
【発明を実施するための形態】
【００１５】
以下、説明の詳細を参照しながら本願の様々な実施形態及び態様を説明し、図面には、上記様々な実施形態が示される。以下の説明及び図面は、本願を例示するためのものであり、限定するものとして解釈されるべきではない。本願の様々な実施形態を全面的に理解するために、多くの特定の詳細を説明する。ところが、いくつかの場合には、本願の実施形態に対する簡単な説明を提供するために、周知又は従来技術の詳細について説明していない。
【００１６】
本願の実施形態を説明することにおいて、用語「含む」及び似ている用語は、開放的な「含む」に理解すべきである。つまり、「．．．を含むが、これらに限定されない」と理解すべきである。用語「に基づいて」は、「少なくとも部分的に．．．に基づいて」と理解すべきである。用語「一実施形態」または「当該実施形態」は、「少なくとも一つの実施形態」として理解すべきである。用語「第１」、「第２」などは、異なるか、同じ対象物を示す可能性もある。以下、他の明確な定義と暗黙的定義を含める可能性もある。
【００１７】
前述した背景技術に記載されたように、従来の技術において、異なる点群データ同士のマッチング関係を確定する場合、大量のコンピューティングを稠密的に進めなければならず、これにより、大量の時間とメモリ空間を消費する。同時に、非剛性変形特性を備える、例えば車両搭載型レーザー点群データをオブジェクトとしてマッチング関係を確定する場合、従来の方法を使用すると、大規模な車両搭載型レーザー点群データの間のマッチング関係を確定する時、良好な精度を有するように確保することができなくなる。上述した問題は、点群が各種の分野での応用と発展に重大な影響を与える。
【００１８】
例えば上述した問題と１つまたは複数の他の潜在的な問題を少なくとも部分的に解決するために、本願の実施形態は、点群データ同士のマッチング関係を確定するための方法及び装置を提出する。本願の実施形態によれば、自動的に迅速で、かつ精度を高く実現することができる点群データ同士のマッチング関係を確定するための方法を提供する。
【００１９】
この方法において、点群に含まれる異なるポイントの特定の属性に応じて、点群の中のポイントを、例えば地面ポイント、平面ポイントと柱体ポイントを含む複数のタイプに分類する。地面ポイントは、測定を行う環境中の地面の位置に位置するポイントを示す。平面ポイントは、測定を行う環境中の地面の位置と垂直したり、他の特定の角度をなす平面上に位置するポイントを示し、これらの平面は、例えば建築物の外表面と看板などを含むことができる。柱体ポイントは、測定を行う環境中の地面の位置と垂直したり、他の特定の角度をなす柱体の表面に位置するポイントを示し、これらの柱体は、例えば電柱、木、ゴミ箱などを含むことができる。点群の中のポイントの前記タイプは、ただ地面ポイント、平面ポイントと柱体ポイントだけを含むのではなく、例えば球体ポイント、地面のコーナーポイント、高反射率ポイントなどの他のタイプのものも含むことができることを理解されたい。点群の収集環境に存在する、比較を行うことができる異なる形状であれば、すべて点群の中のポイントのタイプとして使用することができる。
【００２０】
点群に含む異なるポイントを複数のタイプに分類した後、異なるタイプのポイントが備える特有の属性を利用して、異なるタイプのポイントから新しい特徴を生成することができる。続いて、異なる点群の中の相応のタイプのポイントから生成された特徴を比較することにより、異なる点群がマッチングするかどうかを確定することができ、さらに異なる点群の間のマッチング関係を確定することができる。本願の実施形態において、用語「特徴」は、特徴点、特徴点に対応する法線ベクトルと他のサブの属性を含むことができる。これらのサブの属性は、例えば柱体の半径、高さ、特徴点を対象とする小さなブロック面の辺の長さなどを含む。
【００２１】
本願において、前記異なる特徴は、生成された複数の抽象的な特徴点と特徴点に対応する法線ベクトルを含むことができる。本願において、異なる点群間のマッチング関係は、異なる点群との間の空間変換関係を含み、例えば、一つの点群がどのように回転、水平移動、角度の変化などのような操作を介して他の一つの点群に変換されるか、つまり、他の一つの点群の中の各ポイントの位置と大体に重ねるかを含む。同時に、異なる点群間のマッチング関係を確定する過程は、点群の間の整合と呼ばれることもできる。
【００２２】
前記方法は、単に点群中のポイントから生成された異なる特徴について整合を行うと結構であり、点群中のすべてのポイントに対して整合を行う必要がないので、整合を行うのに必要な計算量を大幅に減少させることができる。同時に、点群中のポイントを異なるタイプに分類し、異なる種類のポイントは、異なる自由度に対応されるので、整合するに当たり、毎回部分的な自由度の整合を行うだけで、同時に６つの自由度の整合を行う必要がないので、計算リソースと記憶リソースを節約することができ、演算速度を向上させることができる。
【００２３】
以下、添付された図面を参照して、本願の実施形態について具体的に説明をする。
【００２４】
図１は、本願の複数の実施形態が実現可能な例示的な環境の概略図１００を示す。概略図１００は、主に、本願中の関連点群とこれに対応する点群データの収集環境を示す。
【００２５】
図１には収集オブジェクト１１０が図示されるが、収集オブジェクト１１０は、収集環境をオブジェクトにして点群を収集し、対応する点群データ１２０を生成し、点群データ１２０を計算装置１３０に送信する。図１において、収集オブジェクト１１０は、収集車の形式で示される。本願において、点群データ１２０を収集するための収集オブジェクト１１０は、収集車に限定されず、点群収集能力を備える任意のオブジェクト、例えば、各種の交通手段であることを理解されたい。さらに、収集オブジェクト１１０は、点群収集能力を備える装置が集積または搭載された各種のオブジェクトであってもよい。収集オブジェクト１１０に収集された点群データ１２０は、計算装置１３０で後続の処理を行う。収集オブジェクト１１０は、有線または無線データ転送などの任意のデータ転送形式を使用して、点群データ１２０を計算装置１３０に転送することができることを理解されたい。これらの転送は、必ずしもリアルタイム転送である必要がない。どのような視覚的または任意の形式で点群データ１２０を計算装置１３０に送信する場合でも、点群データ１２０に対する計算装置１３０の後続の処理に影響を与えない。
【００２６】
本願の実施形態において、点群データは、収集オブジェクト１１０によりレーザーレーダーを使用して収集環境の３６０度スキャンを行って取得された収集環境中の各対象物の外表面のポイントのデータである。スキャンされた垂直解像度に応じて一つのｎ×ｍのデータを取得することができ、ここで、ｎは、垂直方向の走査線の数であり、スレッド数でも呼ばれ、ｍは一つのスキャンラインが水平方向に沿って３６０度スキャンを行って取得したデータである。垂直解像度について、垂直解像度を２．５度に設定すると、１０÷２．５＝４つのスレッドがスキャンされる。収集オブジェクト１１０が所定の高さを備えるので、点群スキャンを行う場合、地面の水平面をオブジェクトにするスキャンデータを取得するように、通常、水平面に対する角度が負の角（例えば、−２．５度）である一つの角度から開始してスキャンを行うことを理解されたい。前記数の選択は、単に例示的な目的のために行われるだけで、任意の方法で、本出願の保護範囲に限定を進行しようとするものではないことを理解されたい。
【００２７】
図１は、道路１４０、広告板１５０−１、１５０−２、１５０−３（広告板１５０と通称される）、ゴミ箱１６０−１、１６０−２（ゴミ箱１６０と通称される）、電柱１７０−１、１７０−２（電柱１７０と通称される）と木１８０−１、１８０−２（木１８０と通称される）を含む収集環境中の各種の対象物をさらに示す。前記対象物において、道路１４０の表面上で収集した点群のデータは、地面点群データを構成し、道路１４０と基本的に垂直され、小さな平面をなす広告板１５０の表面上で収集した点群のデータは、平面点群データを構成し、異なる長さと直径を備える柱体形状であるゴミ箱１６０、電柱１７０と木１８０の表面上で収集した点群のデータは、柱体点群データを構成する。
【００２８】
点群の収集により取得されたデータは、ポイントを収集した位置及び関連するいくつかの属性なので、ただ収集した点群中のポイントのみから、各ポイントが属する分類を直接確定することができず、その後の操作を介して点群データ１２０から相応の地面点群のデータ、平面点群データと柱体点群データなどの異なる分類の点群データを確定する必要があることを理解されたい。図１に示された内容は、点群の収集を行う例示的場面に理解することもでき、ここで、点群の収集を行った後、収集された点群が道路１４０、広告板１５０、ゴミ箱１６０、電柱１７０、または木１８０から由来されたかを直接確定することができず、図２を参照して、説明した以下の方法のフローチャートに沿って後続の処理を介して、点群データ１２０から異なる分類の点群データ１２０を確定する必要がある。
【００２９】
図２は、本願の実施形態による点群データ同士のマッチング関係を確定する方法２００のフローチャートを示す。方法２００は、例えば、図１の計算装置１１０で実行されることができる。方法２００を介して、収集オブジェクト１１０から取得した異なる点群データ１２０をオブジェクトにして、点群データ１２０同士のマッチング関係を確定することができる。
【００３０】
本願の実施形態において、主に同一または本質的に同じ位置で収集オブジェクト１１０により異なる時間に収集された点群データ１２０をオブジェクトにして、点群データ１２０同士のマッチング関係を確定する。収集オブジェクト１１０自体の位置、角度などの内在的原因、及び気象の影響などなような収集環境に存在する可能性がある外在的原因により、収集オブジェクト１１０により同じ位置で異なる時間に収集された点群データが完全に同じではないので、その後の操作を行うように、異なる回次に収集したこれらの点群データ１２０同士のマッチング関係を確定する必要がある。以下、収集オブジェクト１１０により同じ位置で異なる時間に収集した第１の点群データ１２０−１と第２の点群データ１２０−２を例に挙げて説明する。
【００３１】
本願の技術的方案は、基本的に同じ位置で異なる収集オブジェクト１１０により収集された点群データ１２０同士の整合に適用されることもできることを理解されたい。方法２００は、図示されていない追加のステップをさらに含むことができ、および／または、図示されたステップを省略することもでき、本願の範囲は、これらの方面に限定されないことを理解されたい。
【００３２】
方法２００は、ブロック２０２から始まる。ブロック２０２において、計算装置１３０は、第１の点群データ１２０−１に関連する特徴（下に「第１の特徴」と呼ばれる）及び第２の点群データ１２０−２に関連する特徴（下に「第２の特徴」と呼ばれる）を抽出する。上述したように、収集オブジェクト１１０は、同じ位置で異なる回次に第１の点群データ１２０−１と第２の点群データ１２０−２を収集するので、第１の点群データ１２０−１と第２の点群データ１２０−２は同じ対象物（つまり、同じ収集環境）をオブジェクトにして収集されたとみなすことができる。
【００３３】
本願の実施形態において、前述した内容を組み合わせて、前記第１の特徴及び前記第２の特徴は、それぞれ第１の点群データ１２０−１と第２の点群データ１２０−２に基づいて確定した特徴点、特徴点に対応する法線ベクトル及び他の付加的な属性を含めることができ、ここで、付加的な属性は、例えば柱体の半径、高さ、特徴点に対応する小さなブロック面の辺の長さなどを含む。点群中のポイントの分類上の違いに応じて、第１の特徴及び第２の特徴を抽出する過程のステップは、同じではなく、抽出された第１の特徴及び第２の特徴に含くまれる、例えば特徴点と法線ベクトルの特徴の数は同じでなく、抽出された第１の特徴及び第２の特徴に含まれる特徴の内容も同一でない。
【００３４】
以下、それぞれの点群データに含まれる地面点群のデータ、平面点群データと柱体点群データをオブジェクトにして、点群データ１２０から特徴を抽出する過程を説明する。第１の点群データ１２０−１に関連する第１の特徴を抽出するステップと、第２の点群データ１２０−２に関連する第２の特徴を抽出するステップは同じなので、以下、第１の点群データ１２０−１に関連する第１の特徴を抽出するステップのみに対して説明する。
【００３５】
［地面点群データの特徴抽出過程］
地面点群は、通常の範囲が相対的に大きく、分布が相対的に一致するので、第１の点群データ１２０−１から第１の点群データ１２０−１の中の第１の地面点群データを確定することは相対的に容易である。したがって、本願の実施形態において、まず第１の点群データ１２０−１から第１の地面点群データを確定する。第１の点群データ１２０−１に関連する第１の特徴を抽出することにおいて、必ず先に第１の地面点群データを確定することを要求するのではなく、まず第１の平面点群データ又は第１の柱体点群データを確定することもでき、ここで、異なる分類の点群データを確定するステップは、本願の実施形態の効果を実現しない原因にならないことを理解されたい。
【００３６】
地面点群データの特徴抽出処理において、まず第１の点群データ１２０−１から、第１の点群中の地面のポイントを表示する第１の地面点群データを確定する。本願の実施形態において、累積的な合計（ＣＵＳＵＭ）アルゴリズムを利用して、地面点群中の地面の端部の高さのトリップポイントを検出する。続いて、地面点群内で成長アルゴリズムを使用する。前記プロセスを介して、第１の地面点群データを取得することができる。
【００３７】
第１の地面点群データを取得した後、取得された地面点群を所定の面積の小さなブロックに分割する。本願の実施形態において、地面点群は、辺の長さがａである小正方形に分割されるが、ａは、例えば、０．５メートルまたは点群の収集要求および／または収集オブジェクト１１０の収集能力に適した任意の長さであってもよい。前記小さなブロックの形状と尺度の数は、単に例示であるだけで、本願の実施形態を限定するためのものではないことを理解されたい。各小さなブロックは、地面点群中の複数のポイントが含まれることができ、含まれるポイントの数は、分割された小さなブロックのサイズに関連されることを理解されたい。
【００３８】
分割された小正方形（小さなブロック）を取得した後、各小正方形をオブジェクトにして、その小正方形の中心点及び対応する法線ベクトルを計算し、取得した各小正方形の中心点及び対応する法線ベクトルの集合は、第１の地面点群データを表示可能な特徴（即ち、第１の特徴）である。前記ステップを経過した後に、数が少ない特徴で第１の地面点群データを表示することができるので、前記ステップは、点群データのダウンサンプリングに呼ばれることもできる。
【００３９】
選択可能に、前記分割された小正方形に、例えば、植物またはガードレールなどの他の対象物が含まれる可能性があるので、各小正方形をオブジェクトにして、計算した中心点及び対応する法線ベクトルの正確性に影響を与える可能性がある。したがって、マッチングされていない場合を減らすように、小さな正方形に分割した後、各小四角に含む点群中のポイントをオブジェクトにして、例えば高さの違い、高さの平均値、反射率の平均値などの高さ関連情報を計算したり、高さ分布情報を確立して、その後の点群の整合を行うにおいて、前記情報に対して更に比較を行い、点群整合をより正確に実現することができる。これらのステップは、必要不可欠なものではなく、前記情報を比較する前の任意の時間に実行されることができ、本願の実施形態の効果を実現しない原因にならないことを理解されたい。同時に、これらのステップは、平面点群データの特徴抽出処理と柱体点群データの特徴抽出処理に適用されることもできる。
【００４０】
［平面点群データの特徴抽出過程］
平面点群データの特徴抽出過程において、まず第１の点群データ１２０−１から、第１の点群中の平面のポイントを表示する第１の平面点群データを確定する。前述した平面点群データの特徴抽出処理を行うとき、第１の地面点群データを確定するステップが既に完了した場合、第１の点群データ１２０−１から第１の地面点群データを削除することにより、演算量を明確に減少させることができる。第１の点群データ１２０−１から第１の地面点群データを削除した後、取得した点群データは、第１の候補平面点群データと呼ばれる。
【００４１】
平面点群データの特徴抽出処理において、異なるスレッド（つまり、垂直方向で異なるスキャンライン）をオブジェクトにして処理を行う。異なるスレッドをオブジェクトにする処理は、並行に進行されることができ、これにより演算の速度を加速させることができることを理解されたい。各スレッドに、点群中の複数のポイントが含まれることができ、そのうちのポイントの数は、データスキャンを行うときの水平解像度によって決定される。例えば、各スレッドの水平方向の総角度が３６０度なので、水平方向の各解像度が０．１度である場合、各スレッドには、点群中の３６０÷０．１＝３６００個のポイントが含まれる。前記数の選択は、単に例示的な目的のために行われるだけで、任意の方法で、本出願の保護範囲に限定を進行しようとするものではないことを理解されたい。
【００４２】
各スレッドをオブジェクトにして処理を行う場合、スレッド中の各ポイントとその前のポイント間の距離差を計算し、当該距離差とそのポイントの距離の比率が特定の所定閾値を超えた場合、そのポイントをスレッド中の中断ポイントとみなす。これらのステップは、第１の候補平面点群データの異なる小さな平面に属するポイントを区別するのに使用されることを理解されたい。したがって、ポイントとポイントの間の距離差とそのポイントの距離の比率を利用する上述した比較方式は単に例示であるだけで、本願の限定を行うものではない。本願の実施形態において、第１の候補平面点群データのうちの異なる小さな平面に属するポイントを区別することができる任意の適切な計算の方法を利用することができる。一つのスレッドで複数の中断ポイントを捜すことにより、これらのスレッドを異なるセグメントに分割することができる。
【００４３】
中断ポイントを利用して各スレッドを異なるセグメントに分割した後、すべてのスレッド範囲内のセグメントの集合を取得することができる。続いて、例えば主成分分析（ＰＣＡ）アルゴリズムのような方法を利用して、各セグメントに含まれる点群中のポイントの特徴ルート（ｃｈａｒａｃｔｅｒｉｓｔｉｃ  ｒｏｏｔ）と特徴ベクトルのような特徴値を計算することにより、分析を通じて、そのセグメントの形状属性（即ち、当該セグメントが直線か、曲線かまたは区分できないか）を取得することができる。
【００４４】
セグメントの集合中の各セグメントの形状属性を取得した後、平面属性を備える第１の平面点群データを確定する必要があるので、直線属性を備えるセグメントだけを保留するが、これらのセグメントは、直線セグメントと呼ばれることもできる。そして、そのセグメントを表示するように、各直線セグメントに含まれる点群中のポイントの中心点と主な方向を計算する。
【００４５】
次に、前記ステップで保留された直線セグメント対してオイラー条件クラスタリングを行うが、ここで、クラスタリングの標準は、セグメントの中心点が近接（例えば、中心点間の距離が所定の距離閾値内に位置する）だけでではなく、主要な方向も近接（例えば、主要な方向との間の角度差が所定の閾値角度内に位置する）することである。これにより、前記ステップで保留された直線セグメントは、複数の直線セグメントセットにクラスタリングされるが、各直線セグメントセットに含まれる点群中のポイントは、異なる平面に属する。
【００４６】
クラスタリングにより複数の直線セグメントセットを取得した後に、再び主成分分析アルゴリズムのような方法を用いて、各直線セグメントセットに含まれる点群中のポイントの特徴ルートと特徴ベクトルのような特徴値を計算することにより、分析を介して、その直線のセグメントセットの形状属性（つまり、当該セグメントが、平面であるか、平面ではないか、または確定することができないか）を取得することができる。
【００４７】
各直線セグメントセットの形状属性を取得した後、平面属性を備える第１の平面点群データを確定する必要があるので、単に平面属性を備える直線セグメントセットだけを保留し、これらの直線セグメントセットは平面直線セグメントのセットと呼ばれ、各平面直線セグメントセットに含まれる点群中のポイントの法線ベクトルを計算し、その平面直線セグメントセットに含まれる点群中のポイントの中心ポイントを計算して取得する。続いて、地面点群データの特徴抽出処理に関連して説明した前記点群データのダウンサンプリングと同じ方法に基づいて、各平面直線セグメントセットに含まれる点群中のポイントを小さなブロックに分割し、各小正方形をオブジェクトにして、小正方形の中心点及び対応する法線ベクトルを計算し、取得した各小正方形の中心点及び対応する法線ベクトルの集合は、第１の平面点群データを表示することができる特徴（即ち、第１の特徴）である。
【００４８】
［柱体点群データの特徴抽出過程］
柱体点群データの特徴抽出過程において、まず第１の点群データ１２０−１から、第１の点群中の柱体のポインタを表示する第１の柱体点群データを確定する。柱体点群データの特徴抽出処理を行うとき、第１の地面点群データを確定するステップと、第１の平面点群データを確定するステップが既に完了した場合、第１の地面点群データ及び第１の平面点群データを削除することにより、演算量を低減させることができる。第１の点群データ１２０−１から第１の地面点群データ及び第１の平面点群データを削除後、取得した点群データは第１の候補柱体点群データと呼ばれる。
【００４９】
第１の候補柱体点群データを取得した後、点群中の、例えば各２メートルの近接領域内のポイントをオブジェクトにして主成分分析アルゴリズムのような方法を実行して、各ポイントの法線ベクトルとの主要な方向を計算し、これらの点に対して、例えばオイラー条件クラスタリングを行い、クラスタリングの標準は、ポイントの主な方向との法線ベクトルの夾角が例えば５度の夾角閾値内に位置することであってもよい。これにより、前記ステップで保留された点群中のポイントは、複数のポイントセットにクラスタリングされるが、各ポイントセットに含まれる点群中のポイントは、一つの柱体に属する。
【００５０】
続いて、当該ポイントのセットが属する柱体の中心として、各ポイントセットの中心ポイントを計算して、当該柱体の法線ベクトル及び半径を記録し、取得した各柱体の中心点、法線ベクトル及び半径のセットは、第１の柱体点群データを表示することができる特徴（即ち、第１の特徴）である。
【００５１】
続いて、方法２００に戻り、ブロック２０４において、前記方法を使用して抽出した第１の点群データ１２０−１に関連する第１の特徴と第２の点群データ１２０−２に関連する第２の特徴をオブジェクトにして特徴マッチングを行う。特徴マッチングの進行は、２つの特徴が対応するかどうかを判断することを目的として、この過程は、その後の点群整合を行う基礎である。同様に、点群中のポイントの分類上の違いに応じて、抽出された第１の特徴及び第２の特徴に対して特徴マッチングを行う過程のステップは同一でない。以下、抽出された第１の特徴と抽出された第２の特徴が、それぞれ地面点群データの特徴、平面点群データの特徴と柱体点群データの特徴であることを前提として、抽出された第１の特徴及び第２の特徴に対して特徴マッチングを行うプロセスを説明する。
【００５２】
［地面点群データの特徴マッチング過程］
地面点群データの特徴マッチング過程において、マトリックスの回転を介して、地面点群データの特徴の形式である第１の特徴及び第２の特徴を同じ座標系に変換する。
【００５３】
第１の特徴及び第２の特徴を同じ座標系に変換した後、第１の特徴中の特徴点（即ち、地面点群データにおける小さなブロックの中心点）と第２の特徴中の対応する特徴点との間の距離を確定して、当該距離が所定の距離閾値よりも小さい場合に、その特徴点の法線ベクトルとその対応する特徴点の法線ベクトルとの間の差を確定し、その差が所定の差閾値よりも小さい場合に、これらの２つの特徴点がマッチングされると確定することができる。選択的に、これらのステップは、第１の特徴の一つの特徴点をオブジェクトにして、第２の特徴において、第１の特徴中の該当特徴点との距離差と法線ベクトル差がすべて対応した所定の閾値よりも小さい特徴点を検出することで実現されることもできる。具体的に、このような２つの特徴点間のマッチング関係に応じて点群を調整した後、第１の特徴及び第２の特徴の閾値の割合（例えば、７０％−１００％のうちの任意の割合）を満足する対応する特徴点間の距離差と法線ベクトル差がすべて対応した所定の閾値（ここの所定の閾値は、必ず前記所定の閾値と同じでなければならないのではなく、今回の行う判断がさらに厳しくするように、数値がより小さいこともできる）内に位置すると、このような場合、これらの２つの特徴点がマッチングすると確定することができる。第１の特徴及び第２の特徴からそれぞれ由来した２つの特徴点がマッチングすると確定された後に、これらの２つの特徴点のマッチングを、これらの２つの特徴点が属する第１の点群データ１２０−１と第２の点群データ１２０−２に記録する。これらのマッチング過程において、第１の特徴及び第２の特徴のすべて、またはほとんどの特徴点をオブジェクトにしてマッチングするかどうかを確定する必要があり、これにより第１の点群データ１２０−１と第２の点群データ１２０−２のマッチング結果を取得することができる。ここで、異なる特徴点をオブジェクトにしてマッチングするかどうかを確定することは並列に行われることができる。
【００５４】
［平面点群データの特徴マッチング過程］
平面点群データの特徴マッチング過程において、マトリックスの回転を介して、平面点群データの特徴の形式である第１の特徴及び第２の特徴を同じ座標系に変換する。
【００５５】
第１の特徴及び第２の特徴を同じ座標系に変換し後、第１の特徴中の特徴点（即ち、平面点群データにおける小さなブロックの中心点）と第２の特徴中の対応する特徴点との間の距離を確定して、当該距離が所定の距離閾値よりも小さい場合に、その特徴点の法線ベクトルとその対応する特徴点の法線ベクトルとの間の差を確定し、その差が所定の差閾値よりも小さい場合に、これらの２つの特徴点がマッチングされると確定することができる。選択的に、これらのステップは、第１の特徴の一つの特徴点をオブジェクトにして、第２の特徴において、第１の特徴中の該当特徴点との距離差と法線ベクトル差がすべて対応した所定の閾値よりも小さい特徴点を検出することで実現されることもできる。具体的に、このような２つの特徴点間のマッチング関係に応じて点群を調整した後、第１の特徴及び第２の特徴の閾値の割合（例えば、７０％−１００％のうちの任意の割合）を満足する対応する特徴点間の距離差と法線ベクトル差がすべて対応した所定の閾値（ここでの所定の閾値は、必ず前記所定の閾値と同じでなければならないのではなく、今回の行う判断がさらに厳しくするように、数値がより小さいこともできる）内に位置すると、このような場合、これらの２つの特徴点がマッチングすると確定することができる。第１の特徴及び第２の特徴からそれぞれ由来した２つの特徴点がマッチングすると確定された後に、これらの２つの特徴点のマッチングを、これらの２つの特徴点が属する第１の点群データ１２０−１と第２の点群データ１２０−２に記録する。これらのマッチング過程において、第１の特徴及び第２の特徴のすべて、またはほとんどの特徴点をオブジェクトにしてマッチングするかどうかを確定する必要があり、これにより第１の点群データ１２０−１と第２の点群データ１２０−２のマッチング結果を取得することができる。ここで、異なる特徴点をオブジェクトにしてマッチングするかどうかを確定することは並列に行われることができる。
【００５６】
［柱体点群データの特徴マッチング過程］
柱体点群データの特徴マッチング過程において、マトリックスの回転を介して、柱体点群データの特徴の形式である第１の特徴及び第２の特徴を同じ座標系に変換する。
【００５７】
第１の特徴及び第２の特徴を同じ座標系に変換した後、第１の特徴中の特徴点（即ち、柱体の中心点）と第２の特徴中の対応する特徴点との間の距離を確定し、当該距離が所定の距離閾値よりも小さい場合に、その特徴点の法線ベクトル及び半径とその対応する特徴点の法線ベクトル及び半径との間の差を確定し、その差が所定の差閾値よりも小さい場合に、これらの２つの特徴点がマッチングされると確定することができる。選択的に、これらのステップは、第１の特徴の一つの特徴点の周囲の所定の範囲内の、第２の特徴から由来した他の特徴点を検出することで実現されることもできる。具体的に、第１の特徴中の該当特徴点と、第２の特徴から由来した任意の特徴点の法線ベクトル及び半径の差が所定の差閾値よりも小さく、第２の特徴のうち該当の範囲内の他の特徴点の法線ベクトル及び半径との差よりも小さい場合に、これらの２つの特徴点がマッチングされると確定することができる。第１の特徴及び第２の特徴からそれぞれ由来した２つの特徴点がマッチングすると確定された後に、これらの２つの特徴点のマッチングを、これらの２つの特徴点が属する第１の点群データ１２０−１と第２の点群データ１２０−２に記録する。これらのマッチング過程において、第１の特徴及び第２の特徴のすべて、またはほとんどの特徴点をオブジェクトにしてマッチングするかどうかを確定する必要があり、これにより第１の点群データ１２０−１と第２の点群データ１２０−２のマッチング結果を取得することができる。ここで、異なる特徴点をオブジェクトにしてマッチングするかどうかを確定することは並列に行われることができる。
【００５８】
続いて、ブロック２０６において、ブロック２０４で説明したステップを使用して取得した第１の特徴及び第２の特徴の特徴マッチングの結果に基づいて、第１の点群データ１２０−１と第２の点群データ１２０−２同士のマッチング関係を確定する。上述したように、異なる点群間のマッチング関係は、１つの点群がどのように、例えば回転、水平移動、角度の変化などの操作を介して他の一つの点群に変換かどうかとのような、異なる点群との間の空間変換関係を含む。第１の点群データ１２０−１と第２の点群データ１２０−２同士のマッチング関係を確定することにおいて、第１の点群データ１２０−１と第２の点群データ１２０−２が地面点群のデータ、平面点群データ、または柱体点群データを含むかに関わらず、行うプロセスはすべて同じである。
【００５９】
第１の点群データ１２０−１と第２の点群データ１２０−２がマッチングされることを確定した後に、対応する点群データ（即ち、すべて地面点群のデータ、平面点群データや柱体点群データである）をオブジェクトにして、ランダムサンプリングの一貫性（ＲＡＮＳＡＣ）アルゴリズムのような方法を用いて、第１の点群データ１２０−１と第２の点群データ１２０−２との間の以下のようなマッチング関係を確定することにより、第１の点群データ１２０−１の第１の特徴と第２の点群データ１２０−２の第２の特徴のうちの少なくとも大部分の特徴が、これらのマッチング関係を満足するようにする。本願の実施形態によれば、ランダムサンプリングの一貫性アルゴリズムと同じ方法を用いて、第１の点群データ１２０−１と第２の点群データ１２０−２同士のマッチング関係を確定する場合に、マッチングされた各特徴点をオブジェクトにして、繰り返し循環を進めてマッチング関係を見つけることができる。しかしながら、マッチングされた複数の特徴点をオブジェクトにして、例えば、中間値をとるような方式を利用して、複数の特徴点をオブジェクトにして、同時にマッチング関係を見つけることもでき、これにより、計算量を相応に低減させることができる。
【００６０】
点群データを地面点群のデータ、平面点群データと柱体点群データとの３つのタイプに分類するので、異なる種類の点群データをオブジェクトにして、異なる自由度のマッチング関係を見つけることができ、６つの自由度をオブジェクトにして、同時に第１の点群データ１２０−１と第２の点群データ１２０−２同士のマッチング関係を見つける必要がない。例えば、地面点群データは、高さ誤差（ｚ）と回転誤差を調整するのに使用することができ、薄型の点群データや柱体点群データは、平面誤差（ｘ、ｙ）との角度誤差を調整するのに使用することができる。
【００６１】
以上、図２を参照して、計算装置１３０の視点から点群データ同士のマッチング関係を確定する方法２００のプローを説明した。計算装置１３０の視点から行われた説明は、本願に記載された内容をよりよく示すためのものであり、任意の方法で限定するためのものではないことを理解されたい。
【００６２】
図１及び図２を参照して進行した説明からわかるように、本願の実施形態に係る技術的方案は、従来の技術に比べて、様々な利点を備える。前記技術的方案は、単に点群中のポイントから生成された異なる特徴をオブジェクトにして整合を行い、点群中のすべてのポイントをオブジェクトにして整合を行う必要がないので、整合を行うのに必要な計算量を大幅に減少させることができる。同時に、点群中のポイントを異なるタイプに分類し、異なる種類のポイントは、異なる自由度に対応されるので、整合を行う場合、毎回に部分的自由度しかオブジェクトにすることができ、同時に６つの自由度をオブジェクトにして整合を進める必要がないので、計算リソースとストレージリソースを節約することができる。そして、演算速度を向上させ、個々のマッチングミスにより全体的なマッチングに誤りをもたらすことを避けることができる。また、同じ対象物をオブジェクトにする特定の特徴を備える点を人為的に抽出して、点群データ同士のマッチング関係を確定することと比較して、前記技術的方案は、収集オブジェクト１１０により収集された点群の密度要求が高くなく、元データの誤差要求も大きくない。
【００６３】
図３は、本願の実施形態に係る装置３００のブロック図を示す。例えば、図２に示すような点群データ同士のマッチング関係を確定する方法２００は、装置３００により実現されることができる。図３に示すように、装置３００は、第１の点群データに関連する第１の特徴と第２の点群データに関連する第２の特徴を抽出するように構築された抽出モジュール３１０であって、第１の点群データと第２の点群データは、同じ対象物をオブジェクトにして収集されたものである、抽出モジュール３１０を含むことができる。装置３００は、第１の特徴及び第２の特徴に対して特徴マッチングを行うよう構築されたマッチングモジュール３２０をさらに含むことができる。装置３００は、特徴マッチングの結果に基づいて、第１の点群データと第２の点群データ間のマッチング関係を確定するように構築された確定モジュール３３０をさらに含むことができる。
【００６４】
簡潔を目的として、図３には、装置３００の一部を選択可能なモジュールが示されていない。しかしながら、先に図１〜図２を参照して説明した各特徴は、装置３００にも適用されることを理解されたい。また、装置３００の各モジュールは、ハードウェアモジュールであっても、ソフトウェアモジュールであってもよい。例えば、いくつかの実施形態において、装置３００は、ソフトウェアおよび／またはファームウェアを利用して、部分的または全体的に実現されることができ、例えば、コンピュータ読み取り可能な媒体上に格納され、コンピュータプログラム製品として実現されることができる。必要に応じて、または加えて、装置３００は、ハードウェアにより部分的または全体的に実現されることができ、例えば、集積回路（ＩＣ）、特定用途向け集積回路（ＡＳＩＣ）、システム・オン・チップ（ＳＯＣ）、フィールドプログラマブルゲートアレイ（ＦＰＧＡ）などで実現されることができる。本願の範囲は、これらの方面に限定されない。
【００６５】
図４は、本願の実施形態を実施可能な例示的機器４００のブロック図を示す。機器４００は、図２の群データ同士のマッチング関係を確定するための方法２００を実現するのに使用することができる。図示されたように、機器４００は、中央処理ユニット４０１（ＣＰＵ）を含み、ＣＰＵ４０１は、読み取り専用メモリ４０２（ＲＯＭ）に記憶されたコンピュータプログラム指令、または記憶ユニット４０８からランダムアクセスメモリ４０３（ＲＡＭ）にロードされたコンピュータプログラム指令に基づいて、各種の適切な動作と処理を実行することができる。ＲＡＭ４０３には、機器４００の動作に必要な各種のプログラムやデータが記憶されることができる。ＣＰＵ４０１、ＲＯＭ４０２とＲＡＭ４０３、バス４０４を介して互いに接続される。入力／出力（Ｉ／Ｏ）インターフェース４０５もバス４０４に接続される。
【００６６】
機器４００中のＩ／Ｏインターフェース４０５に接続されている複数の部品として、キーボード、マウスなどの入力ユニット４０６と、様々なタイプの表示装置、スピーカーなどの出力ユニット４０７と、磁気ディスク、コンパクトディスクなどの記憶ユニット４０８と、ＬＡＮカード、モデム、無線通信トランシーバなどの通信ユニット４０９が含まれる。通信ユニット４０９は、機器４００がインターネットなどのコンピュータネットワークおよび／または各種の電気通信網を介して他の機器と情報／データを交換することを可能にする。
【００６７】
中央処理ユニット４０１は、前述した各方法と処理、例えば、方法２００を実行する。例えば、いくつかのの実施形態において、方法２００は、コンピュータソフトウェアプログラムとして実現されることができ、これは機械可読媒体（例えば、記憶ユニット４０８）に含まれている。一部の実施形態において、コンピュータプログラムの一部または全部は、ＲＯＭ４０２、および／または通信ユニット４０９を経由して機器４００上にロードおよび／またはインストールすることができる。コンピュータプログラムは、ＲＡＭ４０３にロードされてＣＰＵ４０１により実行される場合、前述した方法２００の１つまたは複数のステップを実行することができる。
【００６８】
本願は、方法、装置、システム、および／またはコンピュータプログラム製品であることができる。コンピュータプログラム製品は、コンピュータ読み取り可能な記憶媒体であることができ、コンピュータ読み取り可能な記憶媒体上に、本願の各方面を実行するためのコンピュータ読み取り可能なプログラムコマンドが搭載される。
【００６９】
コンピュータ読み取り可能な記憶媒体は、コマンド実行装置によって使用されるコマンドを保持するか、記憶することができるタイプの装置であることができる。コンピュータ読み取り可能な記憶媒体は、例えば、電気ストレージ装置、磁気ストレージ装置、光ストレージ装置、電磁記憶装置、半導体記憶装置、またはこれらの任意の適切な組み合わせであることができるが、これに限定されない。コンピュータ読み取り可能な記憶媒体のより具体的な例は、ポータブルコンピュータディスク、ハードディスク、ランダムアクセスメモリ（ＲＡＭ）、読み取り専用メモリ（ＲＯＭ）、消去およびプログラム可能な読み取り専用メモリ（ＥＰＲＯＭまたはフラッシュメモリ）、スタティックランダムアクセスメモリ（ＳＲＡＭ）、携帯コンパクトディスク読み取り専用メモリ（ＣＤ−ＲＯＭ）、デジタル多用途ディスク（ＤＶＤ）、メモリスティック、フロッピーディスク、機械コーディング装置、例えば、コマンドが格納されてパンチカードまたは溝内突起構造、およびこれらの任意の適切な組み合わせを含むが、これに限定されない。本明細書に使用されるコンピュータ読み取り可能な記憶媒体は、電波や自由伝播される他の電磁波、導波管又はその他の伝送媒体を介して伝播される電磁波（例えば、光ファイバケーブルを介して光パルス）または電線を介して送信される電気信号のような瞬間の信号として解釈されない。
【００７０】
本明細書に説明されたコンピュータ読み取り可能なプログラムコマンドは、コンピュータ読み取り可能な記憶媒体から各計算／処理装置にダウンロードされるか、またはインターネット、ＬＡＮ、広域ネットワーク、および／または無線ネットワークなどのネットワークを介して外部のコンピュータまたは外部記憶装置にダウンロードことができる。ネットワークは、銅伝送ケーブル、光ファイバ伝送、無線伝送、ルータ、ファイアウォール、交換、ゲートウェイコンピュータおよび／またはエッジサーバーが含むことができる。各計算／処理装置中のＬＡＮカードまたはネットワークインタフェースは、ネットワークからコンピュータ読み取り可能なプログラムコマンドを受信し、コンピュータ読み取り可能なプログラムコマンドは、各計算／処理装置中のコンピュータで読み取り可能な記憶媒体に記憶されるように、コンピュータ読み取り可能なプログラムコマンドを中継する。
【００７１】
本願の操作を実行するためのコンピュータプログラムコマンドは、アセンブリコマンド、コマンドセットアーキテクチャ（ＩＳＡ）コマンド、機械コマンド、機械関連コマンド、マイクロコード、ファームウェアコマンド、状態設定データや１つまたは複数のプログラミング言語の任意の組み合わせで書かれたソースコードまたはオブジェクトコードであることができる。前記プログラミング言語は、Ｓｍａｌｌｔａｌｋ、Ｃ＋＋、などの、対象物をオブジェクトにするプログラミング言語、「Ｃ」言語のような従来の手続き型プログラミング言語または類似のプログラミング言語を含む。コンピュータ読み取り可能なプログラムコマンドは、完全にユーザーのコンピュータ上で実行されるか、部分的にユーザーのコンピュータ上で実行されるか、独立した一つのソフトウェアパケットとして実行されるか、部分的にユーザーのコンピュータ上で実行されて、部分的に遠距離コンピュータ上で実行されたり、または完全にリモートコンピュータまたはサーバー上で実行されることができる。遠距離コンピュータに関する場面において、遠距離コンピュータは、ローカルエリアネットワーク（ＬＡＮ）またはワイドエリアネットワーク（ＷＡＮ）を含む任意のタイプのネットワークを介してユーザーのコンピュータに接続することができ、または（例えば、インターネットサービスプロバイダを利用して、インターネット接続を介して）外部コンピュータに接続することができる。一部の実施形態において、コンピュータ読み取り可能なプログラムコマンドの状態情報を利用して、オンデマンド電子回路（例えば、プログラマブルロジック回路、フィールドプログラマブルゲートアレイ（ＦＰＧＡ）またはプログラマブルロジックアレイ（ＰＬＡ））を個性化させ、その電子回路は、本願の各方面を実現するために、コンピュータ読み取り可能なプログラムコマンドを実行する。
【００７２】
ここで、本願の各方面は、本願の実施形態による方法、装置（システム）及びコンピュータプログラム製品のフローチャートおよび／またはブロック図を参照して説明された。フローチャートおよび／またはブロック図の各ブロックとフローチャート、および／またはブロック図中の各ブロックの組み合わせは、すべてのコンピュータ読み取り可能なプログラムコマンドとして実現されることができることを理解されたい。
【００７３】
これらのコンピュータ読み取り可能なプログラムコマンドは、汎用コンピュータ、専用コンピュータ又はその他のプログラマブルよりデータ処理装置の処理ユニットに提供されて、一装置が生産されることができる。これにより、これらのコマンドは、コンピュータまたはその他のプログラマブルデータ処理装置の処理ユニットで実行される場合、フローチャート、および／またはブロック図中の１つまたは複数のブロックに規定された機能／動作を実現する装置が生成される。これらのコンピュータ読み取り可能なプログラムコマンドは、コンピュータ読み取り可能な記憶媒体に記憶されることもできる。これらのコマンドは、コンピュータ、プログラマブルデータ処理装置、および／またはその他の装置が特定の方法で操作されるようにし、このような場合、コマンドが格納されるコンピュータ読み取り可能な媒体は、フローチャートおよび／またはブロック図中の１つまたは複数のブロックに規定された機能／動作の各方面を実現するためのコマンドが含む製品を含む。
【００７４】
コンピュータ読み取り可能なプログラムコマンドは、コンピュータ、その他のプログラマブルデータ処理装置または他の装置にロードされることもでき、これにより、コンピュータ実現のプロセスを生成するように、コンピュータ、その他のプログラマブルデータ処理装置または他の装置上で一連の操作手順を実行して、コンピュータ、その他のプログラマブルデータ処理装置または他の装置上で実行されるコマンドがフローチャートおよび／またはブロック図中の１つまたは複数のブロックに規定された機能／動作を実現するようにする。
【００７５】
添付された図面中のフローチャートとブロック図は、本願の複数の実施形態に係るシステム、方法、およびコンピュータプログラム製品の実現可能なシステムの構造、機能、および処理を示す。これらの方面において、フローチャートまたはブロック図中の各ブロックは、一つのモジュール、プログラムのセグメントまたはコマンドの一部を代表することができ、前記モジュールは、プログラムのセグメントまたはコマンドの一部、規定されたロジック機能を実現するための１つまたは複数の実行可能なコマンドを含む。一部の代替可能な実現において、ブロックに記載さ機能は、図面に記載さ順序とは異なる順序で発生することもできる。たとえば、連続される２つのブロックは、実際の上、基本的に並行されるように実行されることができ、関連する機能に応じて、時には逆の順序で実行されることもできる。ブロック図および／またはフローチャート中の各ブロックとブロック図および／またはフローチャート中のブロックの組み合わせは、規定された機能または動作を実行するためのハードウェアベースの専門のシステムに実現されることができ、または専門のハードウェアとコンピュータコマンドの組み合わせで実現されることがあることに注意しなければならない。
【００７６】
以上、本願の各実施形態を説明したが、前述した説明は、例示的なものに過ぎず、限定的なものではなく、開示された各実施形態に限定されるものでもない。説明された各実施形態の範囲と思想を逸脱しなければ多くの修正及び変更を行うことができることを、その技術分野における通常の知識を有する技術者は自明である。本明細書で使用される用語の選択は、各実施形態の原理、実際の応用または市販の技術のための技術の改善を最良に解釈したり、または当該技術分野で通常の知識を有する他の技術者が、本明細書に開示された各実施形態を理解できる。
【図１】
2019133646.tif 000003
【図２】
2019133646.tif 000004
【図３】
2019133646.tif 000005
【図４】
2019133646.tif 000006
【手続補正書】
【提出日】平成31年4月9日(2019.4.9)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
点群データ同士のマッチング関係を確定するための方法であって、
第１の点群データに関連する第１の特徴及び第２の点群データに関連する第２の特徴を抽出するステップであって、前記第１の点群データ及び前記第２の点群データは、同じ対象物をオブジェクトとして収集されたものである、ステップと、
前記第１の特徴及び前記第２の特徴に対して特徴マッチングを行うステップと、
前記特徴マッチングの結果に基づいて、前記第１の点群データと前記第２の点群データ間のマッチング関係を確定するステップと、を含む点群データ同士のマッチング関係を確定するための方法。
【請求項２】
請求項１において、
前記第１の特徴及び前記第２の特徴のそれぞれは、少なくとも特徴点と前記特徴点に対応する法線ベクトルとを含むことを特徴とする点群データ同士のマッチング関係を確定するための方法。
【請求項３】
請求項１において、
前記第１の特徴及び前記第２の特徴を抽出するステップは、
前記第１の点群データから第１の地面点群データを確定し、前記第１の地面点群データの中心点及び対応する法線ベクトルを前記第１の特徴の特徴点及び対応する法線ベクトルと確定するステップと、
前記第２の点群のデータから第２の地面点群データを確定し、前記第２の地面点群データの中心点及び対応する法線ベクトルを前記第２の特徴の特徴点及び対応する法線ベクトルと確定するステップとを含むことを特徴とする点群データ同士のマッチング関係を確定するための方法。
【請求項４】
請求項１において、
前記第１の特徴及び前記第２の特徴を抽出するステップは、
前記第１の点群データから第１の候補平面点群データを確定し、前記第１の候補平面点群データに基づいて、前記第１の特徴を確定するステップと、
前記第２の点群のデータから第２の候補平面点群データを確定し、前記第２の候補平面点群データに基づいて、前記第２の特徴を確定するステップとを含むことを特徴とする点群データ同士のマッチング関係を確定するための方法。
【請求項５】
第４項において、
前記第１の候補平面点群データに基づいて、前記第１の特徴を確定するステップは、
前記第１の候補平面点群データにおけるスレッド（Ｔｈｒｅａｄ）の中断ポイントを確定するステップと、
前記中断ポイントに基づいて、前記スレッドに対して分割を行うステップと、
分割された前記スレッドに対してクラスタリングを行うステップと、
クラスタリング結果に応答して、前記平面点群データの中心点及び対応する法線ベクトルを前記第１の特徴の特徴点及び対応する法線ベクトルと確定するステップとを含むことを特徴とする点群データ同士のマッチング関係を確定するための方法。
【請求項６】
請求項３又は請求項５において、
前記第１の特徴及び前記第２の特徴に対して特徴マッチングを行うステップは、
前記第１の特徴及び前記第２の特徴を同じ座標系に変換するステップと、
前記第１の特徴の特徴点と前記第２の特徴の特徴点との間の距離を確定するステップと、
前記距離が距離閾値よりも小さいことに応答して、前記第１の特徴の法線ベクトルと前記第２の特徴の法線ベクトルとの間の差を確定するステップと、
前記差が差閾値よりも小さいことに応答して、前記第１の特徴と前記第２の特徴がマッチングされると確定するステップとを含むことを特徴とする点群データ同士のマッチング関係を確定するための方法。
【請求項７】
請求項１において、
前記第１の特徴及び前記第２の特徴を抽出するステップは、
前記第１の点群データから第１の候補柱体点群データを確定し、前記第１の候補柱体点群データに基づいて、前記第１の特徴を確定するステップと、
前記第２の点群のデータから第２の候補柱体点群データを確定し、前記第２の候補柱体点群データに基づいて、前記第２の特徴を確定するステップとを含むことを特徴とする点群データ同士のマッチング関係を確定するための方法。
【請求項８】
請求項７において、
前記第１の候補柱体点群データに基づいて、前記第１の特徴を確定するステップは、
前記第１の候補柱体点群データにおける、主な方向と法線ベクトルとの間の夾角が夾角閾値よりも小さい点群データに対してクラスタリングを行うステップと、
クラスタリング結果に応答して、前記柱体点群データの中心点、法線ベクトル及び半径を、前記第１の特徴の特徴点、法線ベクトル及び半径と確定するステップとを含むことを特徴とする点群データ同士のマッチング関係を確定するための方法。
【請求項９】
請求項８において、
前記第１の特徴及び前記第２の特徴に対して特徴マッチングを行うステップは、
前記第１の特徴及び前記第２の特徴を同じ座標系に変換するステップと、
前記第１の特徴の特徴点と前記第２の特徴の特徴点との距離を確定するステップと、
前記距離が距離閾値よりも小さいことに応答して、前記第１の特徴の法線ベクトル及び半径と、前記第２の特徴の法線ベクトル及び半径との間の差を確定するステップと、
前記差が差閾値よりも小さいことに応答して、前記第１の特徴と前記第２の特徴がマッチングされると確定するステップとを含むことを特徴とする点群データ同士のマッチング関係を確定するための方法。
【請求項１０】
請求項１において、
前記第１の点群データと前記第２の点群データ間のマッチング関係を確定するステップは、
前記第１の特徴と前記第２の特徴がマッチングされたことに応答して、前記第１の点群データと前記第２の点群データ間のマッチング関係を確定するステップを含むことを特徴とする点群データ同士のマッチング関係を確定するための方法。
【請求項１１】
点群データとの間のマッチング関係を確定するための装置であって、
第１の点群データに関連する第１の特徴及び第２の点群データに関連する第２の特徴を抽出するように構築される抽出モジュールであって、前記第１の点群データ及び前記第２の点群データは、同じ対象物をオブジェクトとして収集されたものである、抽出モジュールと、
前記第１の特徴及び前記第２の特徴に対して特徴マッチングを行うように構築されるマッチングモジュールと、
前記特徴マッチングの結果に基づいて、前記第１の点群データと前記第２の点群データ間のマッチング関係を確定するように構築される確定モジュールとを含む点群データとの間のマッチング関係を確定するための装置。
【請求項１２】
請求項１１において、
前記第１の特徴及び前記第２の特徴のそれぞれは、少なくとも特徴点と前記特徴点に対応する法線ベクトルとを含むことを特徴とする点群データ同士のマッチング関係を確定する装置。
【請求項１３】
請求項１１において、
前記抽出モジュールは、
前記第１の点群データから第１の地面点群データを確定し、前記第１の地面点群データの中心点及び対応する法線ベクトルを前記第１の特徴の特徴点及び対応する法線ベクトルと確定し、
前記第２の点群のデータから第２の地面点群データを確定し、前記第２の地面点群データの中心点及び対応する法線ベクトルを前記第２の特徴の特徴点及び対応する法線ベクトルと確定するように、さらに構築されることを特徴とする点群データ同士のマッチング関係を確定する装置。
【請求項１４】
請求項１１において、
前記抽出モジュールは、
前記第１の点群データから第１の候補平面点群データを確定し、前記第１の候補平面点群データに基づいて、前記第１の特徴を確定し、
前記第２の点群のデータから第２の候補平面点群データを確定し、前記第２の候補平面点群データに基づいて、前記第２の特徴を確定するように、さらに構築されることを特徴とする点群データ同士のマッチング関係を確定する装置。
【請求項１５】
請求項１４において、
前記抽出モジュールは、
前記第１の候補平面点群データにおけるスレッド（Ｔｈｒｅａｄ）の中断ポイントを確定し、
前記中断ポイントに基づいて、前記スレッドに対して分割を行い、
分割された前記スレッドに対してクラスタリングを行い、
クラスタリング結果に応答して、前記平面点群データの中心点及び対応する法線ベクトルを前記第１の特徴の特徴点及び対応する法線ベクトルと確定するステップとを含むことを特徴とする点群データ同士のマッチング関係を確定するように、さらに構築されることを特徴とする点群データ同士のマッチング関係を確定する装置。
【請求項１６】
請求項１３項又は請求項１５において、
前記マッチングモジュールは、
前記第１の特徴及び前記第２の特徴を同じ座標系に変換し、
前記第１の特徴の特徴点と前記第２の特徴の特徴点との間の距離を確定し、
前記距離が距離閾値よりも小さいことに応答して、前記第１の特徴の法線ベクトルと前記第２の特徴の法線ベクトルとの間の差を確定し、
前記差が差閾値よりも小さいことに応答して、前記第１の特徴と前記第２の特徴がマッチングされると確定するように、さらに構築されることを特徴とする点群データ同士のマッチング関係を確定する装置。
【請求項１７】
請求項１１において、
前記抽出モジュールは、
前記第１の点群データから第１の候補柱体点群データを確定し、前記第１の候補柱体点群データに基づいて、前記第１の特徴を確定し、
前記第２の点群のデータから第２の候補柱体点群データを確定し、前記第２の候補柱体点群データに基づいて、前記第２の特徴を確定するように、さらに構築されることを特徴とする点群データとの間のマッチング関係を確定するための装置。
【請求項１８】
請求項１７において、
前記抽出モジュールは、
前記第１の候補柱体点群データにおける、主な方向と法線ベクトルとの間の夾角が夾角閾値よりも小さい点群データに対してクラスタリングを行い、
クラスタリング結果に応答して、前記柱体点群データの中心点、法線ベクトル及び半径を、前記第１の特徴の特徴点、法線ベクトル及び半径と確定するように、さらに構築されることを特徴とする点群データ同士のマッチング関係を確定する装置。
【請求項１９】
請求項１８において、
前記マッチングモジュールは、
前記第１の特徴及び前記第２の特徴を同じ座標系に変換し、
前記第１の特徴の特徴点と前記第２の特徴の特徴点との距離を確定し、
前記距離が距離閾値よりも小さいことに応答して、前記第１の特徴の法線ベクトル及び半径と、前記第２の特徴の法線ベクトル及び半径との間の差を確定し、
前記差が差閾値よりも小さいことに応答して、前記第１の特徴と前記第２の特徴がマッチングされると確定するように、さらに構築されることを特徴とする点群データ同士のマッチング関係を確定する装置。
【請求項２０】
請求項１１において、
前記確定モジュールは、
前記第１の特徴と前記第２の特徴がマッチングされたことに応答して、前記第１の点群データと前記第２の点群データ間のマッチング関係を確定するように、さらに構築されることを特徴とする点群データ同士のマッチング関係を確定する装置。
【請求項２１】
１つまたは複数のプロセッサと、
１つまたは複数のプログラムを記憶するための記憶装置とを含み、
前記１つまたは複数のプログラムが前記１つまたは複数のプロセッサによって実行される場合、請求項１から請求項１０のうちいずれか１項の方法を実現する機器。
【請求項２２】
コンピュータプログラムが記憶されているコンピュータ読み取り可能な記憶媒体であって、
前記コンピュータプログラムがプロセッサによって実行される場合、請求項１から請求項１０項のうちいずれか１項の方法を実現するコンピュータ読み取り可能な記憶媒体。
【請求項２３】
コンピュータプログラムであって、
前記コンピュータプログラムがプロセッサにより実行されると、請求項１から請求項１０項のうちいずれか１項の方法を実現するコンピュータプログラム。
【外国語明細書】
2019133646000001.pdf