(57)【要約】      （修正有）【課題】点群データから特徴点を高精度で抽出することができる抽出装置、方法及びプログラムを提供する。【解決手段】抽出装置１０は、取得部１１と、第１算出部１３と、第１抽出部１５と、出力部２１と、を備える。取得部１１は、対象物の表面上の３次元座標と、３次元座標において対象物の表面に垂直な法線ベクトルとを、含む点の集合である点群データを取得する。第１算出部１３は、点群データの各点が有する法線ベクトルを用いて、法線ベクトルを表現するパラメータを軸として張られる法線空間における点群データの点の密集度を表す法線空間点密度を算出する。第１抽出部１５は、点群データから、法線空間点密度の低さが所定条件を満たす１以上の点を抽出する。出力部２１は、抽出された１以上の点を出力する。【選択図】図１
2015184061.tif 000002
【特許請求の範囲】
【請求項１】
対象物の表面上の３次元座標と、当該３次元座標において前記対象物の表面に垂直な法線ベクトルとを、含む点の集合である点群データを取得する取得部と、
前記点群データの各点が有する前記法線ベクトルを用いて、前記法線ベクトルを表現するパラメータを軸として張られる法線空間における前記点群データの点の密集度を表す法線空間点密度を算出する第１算出部と、
前記点群データから、前記法線空間点密度の低さが所定条件を満たす１以上の点を抽出する第１抽出部と、
抽出された前記１以上の点を出力する出力部と、
を備える抽出装置。
【請求項２】
前記法線空間点密度は、前記法線空間を分割した法線空間分割領域に含まれる前記点群データの点の数である請求項１に記載の抽出装置。
【請求項３】
前記法線空間点密度は、前記法線空間における前記点群データの点毎に、前記点群データのうち当該点との距離が所定の範囲内である近傍点それぞれに対し、当該点と当該近傍点との距離が増えるほど減衰する関数の値を算出し、合計した値である請求項１に記載の抽出装置。
【請求項４】
前記第１抽出部は、前記点群データから、前記法線空間点密度が低い順に所定数の点を抽出する請求項１に記載の抽出装置。
【請求項５】
前記第１抽出部は、前記法線空間分割領域に含まれる前記点群データの点の数を、前記法線空間点密度の低い順に加算した加算値を算出し、当該加算値が所定数以下の前記法線空間分割領域に含まれる点を前記点群データから抽出する請求項２に記載の抽出装置。
【請求項６】
前記第１抽出部は、前記点群データから、前記法線空間点密度が閾値以下の点を抽出する請求項１に記載の抽出装置。
【請求項７】
前記第１算出部は、前記法線ベクトルの偏りが大きいほど前記法線空間点密度が減るように補正する請求項１に記載の抽出装置。
【請求項８】
前記１以上の点が有する前記３次元座標を用いて、前記３次元座標を表現するパラメータを軸として張られる位置空間における前記１以上の点の密集度を表す位置空間点密度を算出する第２算出部と、
前記１以上の点から、前記位置空間点密度が閾値を超える１以上の点を抽出する第２抽出部と、を更に備え、
前記出力部は、前記第２抽出部により抽出された前記１以上の点を出力する請求項１に記載の抽出装置。
【請求項９】
前記位置空間点密度は、前記位置空間を分割した位置空間分割領域に含まれる前記１以上の点の数である請求項８に記載の抽出装置。
【請求項１０】
前記位置空間点密度は、前記位置空間における前記１以上の点毎に、前記１以上の点のうち当該点との距離が所定の範囲内である近傍点それぞれに対し、当該点と当該近傍点との距離が増えるほど減衰する関数の値を算出し、合計した値である請求項８に記載の抽出装置。
【請求項１１】
前記出力部は、前記１以上の点を表示部に表示出力させる請求項１に記載の抽出装置。
【請求項１２】
対象物の表面上の３次元座標と、当該３次元座標において前記対象物の表面に垂直な法線ベクトルとを、含む点の集合である点群データを取得する取得ステップと、
前記点群データの各点が有する前記法線ベクトルを用いて、前記法線ベクトルを表現するパラメータを軸として張られる法線空間における前記点群データの点の密集度を表す法線空間点密度を算出する第１算出ステップと、
前記点群データから、前記法線空間点密度の低さが所定条件を満たす１以上の点を抽出する第１抽出ステップと、
抽出された前記１以上の点を出力する出力ステップと、
を含む抽出方法。
【請求項１３】
対象物の表面上の３次元座標と、当該３次元座標において前記対象物の表面に垂直な法線ベクトルとを、含む点の集合である点群データを取得する取得ステップと、
前記点群データの各点が有する前記法線ベクトルを用いて、前記法線ベクトルを表現するパラメータを軸として張られる法線空間における前記点群データの点の密集度を表す法線空間点密度を算出する第１算出ステップと、
前記点群データから、前記法線空間点密度の低さが所定条件を満たす１以上の点を抽出する第１抽出ステップと、
抽出された前記１以上の点を出力する出力ステップと、
をコンピュータに実行させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明の実施形態は、抽出装置、方法及びプログラムに関する。
【背景技術】
【０００２】
対象物の３次元形状を計測する場合、対象物の全てを１回で計測することは困難であるため、複数回に分けて計測することが一般的である。この場合、計測毎に得られる点群データはそれぞれ座標系が異なるため、点群データ同士で位置合わせを行うことで、全ての点群データの座標系を共通化し、全ての点群データを統合する。
【０００３】
一般的な位置合わせ手法では、まず、一方の点群データから複数の特徴点を抽出し、抽出した複数の特徴点それぞれに対応する対応点を他方の点群データから抽出し、抽出した複数の特徴点それぞれと抽出した複数の対応点それぞれとの対応関係から、点群データ同士の位置合わせを粗い精度で行う（以下、「第１段階の位置合わせ」と称する場合がある）。その後、一方の点群データの各点と他方の点群データの各点との位置合わせを高精度で行う（以下、「第２段階の位置合わせ」と称する場合がある）。なお、一方の点群データの各点は、一方の点群データの間引き処理後の各点であってもよいし、他方の点群データの各点は、他方の点群データの間引き処理後の各点であってもよい。
【０００４】
このように、点群データ同士の位置合わせは段階的に行われるため、第１段階の位置合わせにおいて点群データから特徴点を高精度で抽出することが、点群データ同士の位置合わせの高速化につながる。
【０００５】
ところで、第２段階の位置合わせを高速化するため、点群データから特徴点が多く残るように間引き処理を行う技術がある。この技術では、点群データの各点が有する法線ベクトルの角度を算出し、点群データから、この角度空間における分散がなるべく大きくなるような部分点群を残すように、間引き処理を行う。これにより、対象物の特徴的な形状である角（コーナー）上などには多くの点（特徴点）が残り、対象物の非特徴的な形状である平面上などにはほとんどの点（非特徴点）が残らないように、間引き処理が行われる。
【先行技術文献】
【非特許文献】
【０００６】
【非特許文献１】Ｓ．Ｒｕｓｉｎｋｉｅｗｉｃｚ  ａｎｄ  Ｍ．Ｌｅｖｏｙ，“Ｅｆｆｉｃｉｅｎｔ  Ｖａｒｉａｎｔｓ  ｏｆ  ｔｈｅ  ＩＣＰ  Ａｌｇｏｒｉｔｈｍ，”  Ｐｒｏｃｅｅｄｉｎｇｓ  ｏｆ  ３−Ｄ  Ｄｉｇｉｔａｌ  Ｉｍａｇｉｎｇ  ａｎｄ  Ｍｏｄｅｌｉｎｇ（３ＤＩＭ），２００１．
【発明の概要】
【発明が解決しようとする課題】
【０００７】
しかしながら、上述したような従来技術は、特徴点を抽出するのではなく、非特徴点を抽出して間引く技術であるため、点群データの間引き処理後の各点には、特徴点だけでなくわずかながら非特徴点も残存してしまう。このため、上述したような従来技術を第１段階の位置合わせに適用しても点群データから特徴点を高精度で抽出することができない。
【０００８】
本発明が解決しようとする課題は、点群データから特徴点を高精度で抽出することができる抽出装置、方法及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【０００９】
実施形態の抽出装置は、取得部と、第１算出部と、第１抽出部と、出力部と、を備える。取得部は、対象物の表面上の３次元座標と、当該３次元座標において前記対象物の表面に垂直な法線ベクトルとを、含む点の集合である点群データを取得する。第１算出部は、前記点群データの各点が有する前記法線ベクトルを用いて、前記法線ベクトルを表現するパラメータを軸として張られる法線空間における前記点群データの点の密集度を表す法線空間点密度を算出する。第１抽出部は、前記点群データから、前記法線空間点密度の低さが所定条件を満たす１以上の点を抽出する。出力部は、抽出された前記１以上の点を出力する。
【図面の簡単な説明】
【００１０】
【図１】第１実施形態の抽出装置の例を示す構成図。
【図２】第１実施形態の対象物の例を示す図。
【図３】第１実施形態の対象物の一部分での点群データの例を示す図。
【図４】第１実施形態の法線空間の例を示す図。
【図５】第１実施形態の法線空間分割領域の例を示す図。
【図６】第１実施形態の点群データからの点の抽出例を示す図。
【図７】第１実施形態の法線空間における点の抽出結果の例を示す図。
【図８】第１実施形態の対象物の一部分における点の抽出結果の例を示す図。
【図９】第１実施形態の全体処理例を示すフローチャート。
【図１０】第１実施形態において法線空間点密度が法線空間分割領域に含まれる点群データの点の数の場合の抽出処理例を示すフローチャート。
【図１１】第１実施形態の抽出装置を用いた位置合わせ処理例を示すフローチャート。
【図１２】第２実施形態の抽出装置の例を示す構成図。
【図１３】第２実施形態の第１抽出部により抽出された対象物の一部分での特徴点群データの例を示す図。
【図１４】第２実施形態の位置空間の例を示す図。
【図１５】第２実施形態の位置空間分割領域の例を示す図。
【図１６】第２実施形態の対象物の一部分における点の抽出結果の例を示す図。
【図１７】第２実施形態の全体処理例を示すフローチャート。
【図１８】第３実施形態の抽出装置の例を示す構成図。
【図１９】第３実施形態の全体処理例を示すフローチャート。
【図２０】各実施形態の抽出装置のハードウェア構成例を示すブロック図。
【発明を実施するための形態】
【００１１】
以下、添付図面を参照しながら、実施形態を詳細に説明する。
【００１２】
（第１実施形態）
図１は、第１実施形態の抽出装置１０の一例を示す構成図である。図１に示すように、抽出装置１０は、取得部１１と、第１算出部１３と、第１抽出部１５と、出力部２１とを、備える。取得部１１、第１算出部１３、第１抽出部１５、及び出力部２１は、例えば、ＣＰＵ（Central  Processing  Unit）などの処理装置にプログラムを実行させること、即ち、ソフトウェアにより実現してもよいし、ＩＣ（Integrated  Circuit）などのハードウェアにより実現してもよいし、ソフトウェア及びハードウェアを併用して実現してもよい。
【００１３】
取得部１１は、対象物の表面上の３次元座標と、当該３次元座標において対象物の表面に垂直な法線ベクトルとを、含む点の集合である点群データを取得する。
【００１４】
３次元座標は、３次元直交座標系に配置された３次元位置座標であることが好ましいが、これに限定されるものではない。３次元座標は、３次元直交座標系に変換可能な座標系に配置された３次元位置座標であってもよく、例えば、３次元極座標系や３次元円筒座標系に配置された３次元位置座標であってもよい。
【００１５】
法線ベクトルは、３次元直交座標系の各軸における法線方向成分を表す３要素からなるベクトルであることが好ましいが、これに限定されるものではない。法線ベクトルは、３次元直交座標系に変換可能な座標系に配置されたベクトルであってもよく、例えば、３次元極座標系や３次元円筒座標系に配置されたベクトルであってもよい。
【００１６】
図２は、第１実施形態の対象物３０の一例を示す図であり、図３は、第１実施形態の対象物３０の一部分での点群データ３１の一例を示す図である。図２及び図３に示す例の場合、取得部１１は、対象物３０の表面上の３次元座標と、当該３次元座標において対象物３０の表面に垂直な法線ベクトルとを、含む点の集合である点群データ３１を取得する。
【００１７】
なお、取得部１１が取得する点群データは、レーザセンサやステレオカメラなどを用いた３次元計測によって生成されたものであってもよいし、３Ｄ―ＣＡＤ（Ｃｏｍｐｕｔｅｒ  Ａｉｄｅｄ  Ｄｅｓｉｇｎ）などのソフトウェアで生成されたものであってもよい。
【００１８】
また、取得部１１が取得した点群データに含まれる各点は、３次元座標及び法線ベクトル以外の情報を含んでいてもよい。例えば、点群データがアクティブセンサを用いた３次元計測によって生成された場合、点群データは、各点の反射強度を更に含むことができる。また例えば、点群データが可視光カメラを用いた３次元計測によって生成された場合、点群データは、各点の輝度値を更に含むことができる。また例えば、点群データがカラーカメラを用いた３次元計測によって生成された場合、点群データは、各点の色情報を更に含むことができる。また例えば、点群データがレーザセンサやステレオカメラなどを用いた時系列の３次元計測によって生成された場合、点群データは、各点の信頼度を更に含むことができる。信頼度は、実際にその場所に点が存在することの信頼性を表す。また例えば、点群データが３Ｄ―ＣＡＤによって生成された場合、点群データは、各点の色情報や材質情報など３Ｄモデルが保有する情報を更に含むことができる。
【００１９】
第１算出部１３は、取得部１１により取得された点群データの各点が有する法線ベクトルを用いて、法線ベクトルを表現するパラメータを軸として張られる法線空間における点群データの点の密集度を表す法線空間点密度を算出する。
【００２０】
図４は、第１実施形態の法線空間の一例を示す図である。図４に示す例では、第１算出部１３は、点群データ３１の各点が有する法線ベクトルを用いて、法線空間に点群データ３１を配置している。具体的に説明すると、法線空間の軸であるｎｘ、ｎｙ、ｎｚは、法線方向成分を表す３要素であるため、第１算出部１３は、点群データ３１の各点が有する法線ベクトルを表現するパラメータに基づいて、法線空間に点群データ３１を配置する。
【００２１】
法線空間点密度は、例えば、法線空間を分割した法線空間分割領域に含まれる点群データの点の数とすることができる。図５は、第１実施形態の法線空間分割領域の一例を示す図である。図５に示す例では、法線空間分割領域は、３次元直交座標系で表される法線空間をグリッド状に等間隔に分割した領域としているが、これに限定されるものではない。第１算出部１３は、点群データ３１の各点を法線空間（法線空間分割領域）に投票（配置）した後に、法線空間分割領域それぞれに含まれる点群データの点の数を算出すればよい。また、第１算出部１３は、点群データの各点を該当する法線空間分割領域だけに投票するのではなく、当該点との距離が増えるほど減少する重みをかけた値を、近傍の法線空間分割領域に投票してもよい。
【００２２】
但し、法線空間点密度は、これに限定されるものではない。例えば、法線空間点密度は、法線空間における点群データの点毎に、点群データのうち当該点との距離が所定の範囲内である近傍点それぞれに対し、当該点と当該近傍点との距離が増えるほど減衰する関数の値を算出し、合計した値としてもよい。
【００２３】
距離が増えるほど減衰する関数は、例えば、正規分布の確率密度関数とすることができる。この場合、第１算出部１３は、数式（１）により法線空間点密度を算出できる。
【００２４】
【数１】
2015184061.tif 000003
【００２５】
ここで、ｚは、法線空間点密度算出対象の点（注目点）の法線ベクトルを示し、Ｐは、注目点に対する近傍点の集合を示し、Ｚｉは、ｉ番目の近傍点の法線ベクトルであり、σ２は、法線空間における点群データの分散を示すが、適当な定数としてもよい。
【００２６】
なお第１算出部１３は、法線ベクトルの偏りが大きいほど法線空間点密度が減るように補正してもよい。但し、法線ベクトルの偏りは、対象物において、より測定されやすい向きの法線ベクトルに対してより大きくなる値を表すこととする。
【００２７】
具体的に説明すると、法線ベクトルの偏りは、法線空間分割領域の分割方法や、点群データを測定するレーザセンサやステレオカメラなどの測定機器の特性に依って生じる。
【００２８】
例えば、図５に示すように、法線空間分割領域が、３次元直交座標系で表される法線空間をグリッド状に等間隔に分割した領域であるとする。この場合、法線ベクトルは、半径が１である球面上に位置する。このため、この球面と各法線空間分割領域との重複領域の大きさが大きいほど、この法線空間分割領域における法線ベクトルの偏りが大きくなる。
【００２９】
ｉ番目の法線空間分割領域の法線空間点密度をｄｉとし、この法線空間分割領域に含まれる半径１の球面の表面積をＳｉとすると、第１算出部１３は、例えば、数式（２）を用いて、法線空間点密度を補正する。
【００３０】
【数２】
2015184061.tif 000004
【００３１】
また、別の補正の例として、測定機器が二眼ステレオ視等によるものであり、視野角がある範囲に限定される場合を考える。
【００３２】
この場合、光軸の正方向（光学中心から対象物に向かう方向）とのなす角が鋭角となる法線ベクトルは観測されず、光軸の正方向とのなす角が大きい法線ベクトルほど多く観測される。即ち、法線ベクトルの偏りが大きい。このため、第１算出部１３は、光軸の正方向とのなす角が大きいほど、法線空間点密度が大きく減るような補正をしてもよい。
【００３３】
ｉ番目の点の法線空間点密度をｄｉとし、この点の持つ法線ベクトルと光軸の正方向とのなす角をＲｉとすると、第１算出部１３は、例えば、数式（３）を用いて、法線空間点密度を補正する。
【００３４】
【数３】
2015184061.tif 000005
【００３５】
なお、第１算出部１３は、複数の補正を組み合わせて法線空間点密度を補正してもよく、例えば、数式（２）及び数式（３）の両方を適用してもよい。
【００３６】
第１抽出部１５は、取得部１１により取得された点群データから、第１算出部１３により算出された法線空間点密度の低さが所定条件を満たす１以上の点を特徴点として抽出する。第１抽出部１５は、点群データから、法線空間点密度が低い順に所定数の点を抽出してもよいし、法線空間点密度が閾値以下の点を抽出してもよい。
【００３７】
なお、法線空間点密度が、法線空間分割領域に含まれる点群データの点の数の場合、第１抽出部１５は、法線空間分割領域に含まれる点群データの点の数を、法線空間点密度の低い順に加算した加算値を算出し、当該加算値が所定数以下の法線空間分割領域に含まれる点を点群データから抽出する。
【００３８】
例えば、第１抽出部１５は、図６に示すように、法線空間分割領域に含まれる点群データの点の数を、法線空間点密度の低い順に並べ、法線空間点密度の低い順に法線空間点密度（点の数）を加算した加算値を算出する。そして第１抽出部１５は、算出した加算値が閾値に達すると、加算値が所定数以下の法線空間分割領域に含まれる点を点群データから抽出する。例えば、図６に示す例では、所定数が２２であるため、第１抽出部１５は、算出した加算値が２２に達すると、加算値が２２以下の法線空間分割領域に含まれる点（法線空間分割領域に含まれる点の数が１〜４である法線空間分割領域に含まれる点）を点群データから抽出する。
【００３９】
また、図６に示す例において、閾値を４とし、第１抽出部１５は、法線空間分割領域に含まれる点群データの点の数が１〜４である法線空間分割領域に含まれる点を点群データから抽出してもよい。
【００４０】
なお、法線空間点密度が、数式（１）により算出された値の場合、点群データの各点が法線空間点密度を有するため、この値（法線空間点密度）が低い順に所定数の点を抽出してもよいし、この値（法線空間点密度）が閾値以下の点を抽出してもよい。
【００４１】
図７は、第１実施形態の法線空間における点の抽出結果の一例を示す図であり、図８は、第１実施形態の対象物３０の一部分における点の抽出結果の一例を示す図である。図７に示す例では、図５に示す例において、符号３５〜３８で示した点以外の点である１以上の点の集合（以下、「特徴点群データ４１」と称する場合がある）が抽出されている。この特徴点群データ４１に含まれる各点は、図８に示すように、対象物３０の特徴的な形状である角（コーナー）上などに存在する特徴点となっている。
【００４２】
出力部２１は、第１抽出部１５により抽出された１以上の点を出力する。
【００４３】
図９は、第１実施形態の抽出装置１０で行われる全体処理の手順の流れの一例を示すフローチャートである。
【００４４】
まず、取得部１１は、点群データを取得する（ステップＳ１０１）。
【００４５】
続いて、第１算出部１３は、取得部１１により取得された点群データの各点が有する法線ベクトルを用いて、法線空間における法線空間点密度を算出する（ステップＳ１０３）。
【００４６】
続いて、第１抽出部１５は、取得部１１により取得された点群データから、第１算出部１３により算出された法線空間点密度の低さが所定条件を満たす１以上の点を特徴点として抽出する（ステップＳ１０５）。
【００４７】
そして出力部２１は、第１抽出部１５により抽出された特徴点を出力する。
【００４８】
図１０は、第１実施形態において法線空間点密度が法線空間分割領域に含まれる点群データの点の数の場合の抽出処理の手順の流れの一例を示すフローチャートである。
【００４９】
まず、第１算出部１３は、法線空間をＭ個に分割し、Ｍ個の法線空間分割領域を生成する（ステップＳ２０１）。
【００５０】
続いて、第１算出部１３は、各法線空間分割領域の内包点数Ｎ（ｉ）を算出する（ステップＳ２０３）。なお、ｉ＝１〜Ｍである。
【００５１】
続いて、第１抽出部１５は、Ｎ（ｉ）を昇順にソートし、ソート後のインデックスｉの並びを｛ｊ１，ｊ２，…，ｊＭ｝とする（ステップＳ２０５）。
【００５２】
続いて、第１抽出部１５は、変数ｋ及び変数Ｓを０に初期化する（ステップＳ２０７）。
【００５３】
続いて、第１抽出部１５は、ｋをインクリメントし、変数Ｓ（初期値０）にＮ（ｊｋ）の値を加算する（ステップＳ２０９）。
【００５４】
続いて、第１抽出部１５は、Ｓの値が所定数以下であるか否かを確認する（ステップＳ２１１）。Ｓの値が所定数未満であれば（ステップＳ２１１でＹｅｓ）、ステップＳ２０９へ戻る。
【００５５】
一方、Ｓの値が所定数以上であれば（ステップＳ２１１でＮｏ）、第１抽出部１５は、｛ｊ１，ｊ２，…，ｊｋ｝番目の分割領域に含まれる各点を抽出する（ステップＳ２１３）。
【００５６】
以上のように第１実施形態では、法線ベクトルの方向が希少である点、即ち、法線空間点密度の低い点を特徴点として抽出するので、点群データから特徴点を高精度で抽出することができる。
【００５７】
一般的に、法線ベクトルの方向が希少である点は、周囲の点との区別が付きやすいため特徴点となるが、法線ベクトルの方向が夥多である点は、周囲の点との区別が付きにくいため非特徴点となる。なお、法線ベクトルの方向が希少である点は、直方体の角（コーナー）や凹凸のある表面形状上に存在し、法線ベクトルの方向が夥多である点は、平面上に多く存在する。このため、特徴点を高精度で抽出するためには、法線ベクトルの方向が夥多である点を除外して、法線ベクトルの方向が希少である点を抽出する必要がある。
【００５８】
第１実施形態では、法線ベクトルの方向が希少である点、即ち、法線空間点密度の低い点を特徴点として抽出するので、法線空間点密度の高い非特徴点を除外して特徴点を抽出でき、点群データから特徴点を高精度で抽出することができる。
【００５９】
図１１は、第１実施形態の抽出装置１０を用いた位置合わせ処理の一例を示すフローチャートである。ここでは、特徴点の抽出以外の処理も抽出装置１０が行う場合を例に取り説明するが、特徴点の抽出以外の処理は、抽出装置１０以外の装置が行ってもよい。
【００６０】
まず、抽出装置１０は、第１点群データ及び第２点群データを取得する（ステップＳ３０１）。ここで、第１点群データ及び第２点群データは、例えば、対象物を異なる位置から計測した点群データである。
【００６１】
続いて、抽出装置１０は、第１点群データから１以上の第１特徴点を抽出し、第２点群データから１以上の第２特徴点を抽出する（ステップＳ３０３）。なお、ここでは、１以上の第２特徴点それぞれは、１以上の第１特徴点それぞれに対応する対応点であるとする。つまり、上述した抽出装置１０による特徴点の抽出処理は、第１点群データから１以上の第１特徴点を抽出する際に行われる。
【００６２】
続いて、抽出装置１０は、１以上の第１特徴点それぞれと、１以上の第２特徴点それぞれとの第１段階の位置合わせ（精度の粗い位置合わせ）を行う（ステップＳ３０５）。
【００６３】
続いて、抽出装置１０は、第１点群データの１以上の第１点それぞれと、第２点群データの１以上の第２点それぞれとの第２段階の位置合わせ（高精度の位置合わせ）を行う（ステップＳ３０７）。
【００６４】
このように、位置合わせにおける特徴点の抽出に第１実施形態の抽出処理を適用することで、特徴点を高精度に抽出できるので、第１段階の位置合わせの精度が上がり、第２段階の位置合わせの高速化が可能となるため、点群データ同士の位置合わせ全体での高速化も可能となる。
【００６５】
（第２実施形態）
第２実施形態では、非特徴点がノイズとして含まれないように特徴点を抽出する例について説明する。以下では、第１実施形態との相違点の説明を主に行い、第１実施形態と同様の機能を有する構成要素については、第１実施形態と同様の名称・符号を付し、その説明を省略する。
【００６６】
図１２は、第２実施形態の抽出装置１１０の一例を示す構成図である。図１２に示すように、第２実施形態の抽出装置１１０では、第２算出部１１７及び第２抽出部１１９が第１実施形態と相違する。
【００６７】
図１３は、第２実施形態の第１抽出部１５により抽出された対象物３０の一部分での特徴点群データ１４１の一例を示す図である。図１３に示す例では、法線ベクトルのノイズ等の影響で、第１抽出部１５により抽出された特徴点候補群データ１４１に非特徴点１４５、１４６が含まれている。第２実施形態では、特徴点候補群データ１４１から非特徴点１４５、１４６を含まないように特徴点を抽出する。
【００６８】
第２算出部１１７は、第１抽出部１５により抽出された１以上の点（以下、「特徴点候補群データ」と称する場合がある）が有する３次元座標を用いて、３次元座標を表現するパラメータを軸として張られる位置空間における第１抽出部１５により抽出された１以上の点の密集度を表す位置空間点密度を算出する。
【００６９】
図１４は、第２実施形態の位置空間の一例を示す図である。図１４に示す例では、第２算出部１１７は、特徴点候補群データ１４１の各点が有する３次元座標を用いて、位置空間に特徴点候補群データ１４１を配置している。
【００７０】
位置空間点密度は、例えば、位置空間を分割した位置空間分割領域に含まれる特徴点候補群データの点の数とすることができる。図１５は、第２実施形態の位置空間分割領域の一例を示す図である。図１５に示す例では、位置空間分割領域は、３次元直交座標系で表される位置空間をグリッド状に等間隔に分割した領域としているが、これに限定されるものではない。第２算出部１１７は、特徴点候補群データ１４１の各点を位置空間（位置空間分割領域）に投票（配置）した後に、位置空間分割領域それぞれに含まれる特徴点候補群データの点の数を算出すればよい。また、第２算出部１１７は、特徴点候補群データの各点を該当する位置空間分割領域だけに投票するのではなく、当該点との距離が増えるほど減少する重みをかけた値を、近傍の位置空間分割領域に投票してもよい。
【００７１】
但し、位置空間点密度は、これに限定されるものではない。例えば、位置空間点密度は、位置空間における特徴点候補群データの点毎に、特徴点候補群データのうち当該点との距離が所定の範囲内である近傍点それぞれに対し、当該点と当該近傍点との距離が増えるほど減衰する関数の値を算出し、合計した値としてもよい。
【００７２】
距離が増えるほど減衰する関数は、例えば、正規分布の確率密度関数とすることができる。この場合、第２算出部１１７は、数式（４）により位置空間点密度を算出できる。
【００７３】
【数４】
2015184061.tif 000006
【００７４】
ここで、ｘは、位置空間点密度算出対象の点（注目点）の３次元座標を示し、Ｑは、注目点に対する近傍点の集合を示し、ｘｉは、ｉ番目の近傍点の３次元座標であり、σ’２は、位置空間における特徴点候補群データの分散を示すが、適当な定数としてもよい。
【００７５】
第２抽出部１１９は、第１抽出部１５により抽出された特徴点候補群データから、位置空間点密度が閾値を超える１以上の点を抽出する。
【００７６】
図１６は、第２実施形態の対象物３０の一部分における点の抽出結果の一例を示す図である。図１６に示す例では、図１３及び図１５に示す例における非特徴点１４５、１４６以外の点である１以上の点の集合（以下、「特徴点群データ１５１」と称する場合がある）が抽出されている。この特徴点群データ１５１に含まれる各点は、図１６に示すように、対象物３０の特徴的な形状である角（コーナー）上などに存在する特徴点となっている。
【００７７】
出力部２１は、第２抽出部１１９により抽出された１以上の点を出力する。
【００７８】
図１７は、第２実施形態の抽出装置１１０で行われる全体処理の手順の流れの一例を示すフローチャートである。
【００７９】
まず、取得部１１は、点群データを取得する（ステップＳ４０１）。
【００８０】
続いて、第１算出部１３は、取得部１１により取得された点群データの各点が有する法線ベクトルを用いて、法線空間における法線空間点密度を算出する（ステップＳ４０３）。
【００８１】
続いて、第１抽出部１５は、取得部１１により取得された点群データから、第１算出部１３により算出された法線空間点密度の低さが所定条件を満たす１以上の点を候補点として抽出する（ステップＳ４０５）。
【００８２】
続いて、第２算出部１１７は、第１抽出部１５により抽出された特徴点候補群データが有する３次元座標を用いて、位置空間における位置空間点密度を算出する（ステップＳ４０７）。
【００８３】
続いて、第２抽出部１１９は、第１抽出部１５により抽出された特徴点候補群データから、位置空間点密度が閾値を超える１以上の点を特徴点として抽出する（ステップＳ４０９）。
【００８４】
そして出力部２１は、第２抽出部１１９により抽出された特徴点を出力する。
【００８５】
一般的に、特徴的な形状上の特徴点は位置空間において互いに近傍に位置する傾向があるが、法線ベクトルのノイズ等の影響で発生した非特徴点は位置空間上ではまばらに存在するため、近接する確率が低い。
【００８６】
第２実施形態では、法線ベクトルの方向が希少である点、即ち、法線空間点密度の低い点を候補点として抽出した後に、位置空間点密度が閾値を超える点、即ち、位置空間内で孤立していない点を特徴点として抽出するので、法線ベクトルのノイズ等の影響で、点群データから、ノイズにより誤算出される非特徴点を含まない特徴点を高精度で抽出することができる。
【００８７】
（第３実施形態）
第３実施形態では、抽出した特徴点を表示出力する例について説明する。以下では、第１実施形態との相違点の説明を主に行い、第１実施形態と同様の機能を有する構成要素については、第１実施形態と同様の名称・符号を付し、その説明を省略する。
【００８８】
図１８は、第３実施形態の抽出装置２１０の一例を示す構成図である。図１８に示すように、第３実施形態の抽出装置２１０では、表示部２２３が第１実施形態と相違する。
【００８９】
表示部２２３は、例えば、液晶ディスプレイなどの表示装置により実現できる。
【００９０】
出力部２１は、第１抽出部１５により抽出された１以上の点（特徴点群データ）を表示部２２３に表示出力させる。表示部２２３の表示には、特徴点群データの各点を、その点の持つ三次元座標上に配置した３Ｄのグラフィックスによる画像ないし動画像を用いることができる。この際、表示部２２３は、特徴点群データの各点を取得部１１により取得された点群データの各点に重畳させて表示してもよいし、両点群を区別するために点の色や形状を変えて表示してもよい。また表示部２２３は、３Ｄのグラフィックスを用いず、特徴点群データをある視点から見た二次元の画像ないし動画像上に配置して表示してもよい。
【００９１】
図１９は、第３実施形態の抽出装置２１０で行われる全体処理の手順の流れの一例を示すフローチャートである。
【００９２】
まず、取得部１１は、点群データを取得する（ステップＳ５０１）。
【００９３】
続いて、第１算出部１３は、取得部１１により取得された点群データの各点が有する法線ベクトルを用いて、法線空間における法線空間点密度を算出する（ステップＳ５０３）。
【００９４】
続いて、第１抽出部１５は、取得部１１により取得された点群データから、第１算出部１３により算出された法線空間点密度の低さが所定条件を満たす１以上の点を特徴点として抽出する（ステップＳ５０５）。
【００９５】
続いて、出力部２１は、第１抽出部１５により抽出された特徴点を表示部２２３に表示出力させる（ステップＳ５０７）。
【００９６】
以上のように第３実施形態によれば、抽出された特徴点群データの各点が妥当であるかどうかをユーザが目視で確認することができる。これにより、インタラクティブに出力結果を調整できる特徴点の算出が可能となる。
【００９７】
（ハードウェア構成）
図２０は、上記各実施形態の抽出装置のハードウェア構成の一例を示すブロック図である。図２０に示すように、上記各実施形態の抽出装置は、ＣＰＵなどの制御装置９０１と、ＲＯＭやＲＡＭなどの記憶装置９０２と、ＨＤＤやＳＳＤなどの外部記憶装置９０３と、ディスプレイなどの表示装置９０４と、マウスやキーボードなどの入力装置９０５と、通信Ｉ／Ｆ９０６とを、備えており、通常のコンピュータを利用したハードウェア構成で実現できる。
【００９８】
上記各実施形態の抽出装置で実行されるプログラムを、インストール可能な形式又は実行可能な形式のファイルでＣＤ−ＲＯＭ、ＣＤ−Ｒ、メモリカード、ＤＶＤ、フレキシブルディスク（ＦＤ）等のコンピュータで読み取り可能な記憶媒体に記憶されて提供される。
【００９９】
上記各実施形態の抽出装置で実行されるプログラムは、ＲＯＭ等に予め組み込んで提供されるようにしてもよい。また、上記各実施形態の抽出装置で実行されるプログラムを、インターネット等のネットワークに接続されたコンピュータ上に格納し、ネットワーク経由でダウンロードさせることにより提供するようにしてもよい。また、上記各実施形態の抽出装置で実行されるプログラムを、インターネット等のネットワーク経由で提供または配布するようにしてもよい。
【０１００】
上記各実施形態の抽出装置で実行されるプログラムは、上述した各部をコンピュータ上で実現させるためのモジュール構成となっている。実際のハードウェアとしては、例えば、制御装置９０１が外部記憶装置９０３からプログラムを記憶装置９０２上に読み出して実行することにより、上記各部がコンピュータ上で実現されるようになっている。
【０１０１】
以上説明したとおり、上記各実施形態によれば、点群データから特徴点を高精度で抽出することができる。
【０１０２】
なお本発明は、上記各実施形態そのままに限定されるものではなく、実施段階ではその要旨を逸脱しない範囲で構成要素を変形して具体化することができる。また上記各実施形態に開示されている複数の構成要素の適宜な組み合わせにより、種々の発明を形成することができる。例えば、実施形態に示される全構成要素からいくつかの構成要素を削除してもよい。さらに、異なる実施形態にわたる構成要素を適宜組み合わせても良い。
【０１０３】
例えば、上記実施形態のフローチャートにおける各ステップを、その性質に反しない限り、実行順序を変更し、複数同時に実施し、あるいは実施毎に異なった順序で実施してもよい。
【符号の説明】
【０１０４】
１０、１１０、２１０  抽出装置
１１  取得部
１３  第１算出部
１５  第１抽出部
１１７  第２算出部
１１９  第２抽出部
２１  出力部
２２３  表示部
【図１】
2015184061.tif 000007
【図２】
2015184061.tif 000008
【図５】
2015184061.tif 000009
【図６】
2015184061.tif 000010
【図９】
2015184061.tif 000011
【図１０】
2015184061.tif 000012
【図１１】
2015184061.tif 000013
【図１２】
2015184061.tif 000014
【図１７】
2015184061.tif 000015
【図１８】
2015184061.tif 000016
【図１９】
2015184061.tif 000017
【図２０】
2015184061.tif 000018
【図３】
2015184061.tif 000019
【図４】
2015184061.tif 000020
【図７】
2015184061.tif 000021
【図８】
2015184061.tif 000022
【図１３】
2015184061.tif 000023
【図１４】
2015184061.tif 000024
【図１５】
2015184061.tif 000025
【図１６】
2015184061.tif 000026