(57)【要約】【課題】点群データから高精度な三次元形状データを生成する。【解決手段】三次元座標を持つ複数の点群データから三次元形状を自動生成する三次元形状の自動生成装置において、前記点群データから三次元形状のエッジ及び面を抽出するためのセグメント化を行うセグメント手段と、前記セグメント手段により生成されたセグメント情報及び予め設定された関数に基づいて三次元形状を判定し自動生成する形状判定生成手段とを有することにより、上記課題を解決する。【選択図】        図１
2004272459.tif 000002
【特許請求の範囲】
【請求項１】
三次元座標を持つ複数の点群データから三次元形状を自動生成する三次元形状の自動生成装置において、
前記点群データから三次元形状のエッジ及び面を抽出するためのセグメント化を行うセグメント手段と、
前記セグメント手段により生成されたセグメント情報及び予め設定された関数に基づいて三次元形状を判定し自動生成する形状判定生成手段とを有することを特徴とする自動生成装置。
【請求項２】
前記セグメント手段は、
前記点群データに整列情報が含まれる場合は整列順に基づきセグメント化を行い、前記点群データに整列情報が含まれていない場合は、三角ポリゴンを生成してセグメント化を行うことを特徴とする請求項１に記載の自動生成装置。
【請求項３】
前記セグメント手段は、
前記セグメント化された点群データのセグメント形状情報から各形状間において、隣接する形状同士の連続性、法線方向、又は距離に基づきエッジ及び面を抽出することを特徴とする請求項１又は２に記載の自動生成装置。
【請求項４】
前記形状判定生成手段は、
セグメント化された各々のセグメントにおける点群データから最小二乗法を用いて前記所定の関数として設定された平面方程式又は曲面方程式に置き換え、その係数値により固有値及び固有ベクトルを生成することを特徴とする請求項１に記載の自動生成装置。
【請求項５】
前記形状判定生成手段は、
前記固有値に対する寄与率と、予め設定した閾値とに基づいて平面又は二次曲面の形状を判定することを特徴とする請求項４に記載の自動生成装置。
【請求項６】
前記形状判定生成手段は、
前記二次曲面形状から移動量ベクトルを生成することを特徴とする請求項５に記載の自動生成装置。
【請求項７】
前記形状判定生成手段は、
前記固有ベクトル及び前記移動ベクトルにより前記セグメントの点群データをオブジェクト座標に変換して曲面形状を生成することを特徴とする請求項４乃至６の何れか１項に記載の自動生成装置。
【請求項８】
三次元座標を持つ複数の点群データから三次元形状を自動生成する三次元形状の自動生成方法において、
前記点群データから三次元形状のエッジ及び面を抽出するためのセグメント化を行うセグメント段階と、
前記セグメント段階により生成されたセグメント情報及び予め設定された関数に基づいて三次元形状を判定し自動生成する形状判定生成段階とを有することを特徴とする自動生成方法。
【請求項９】
前記セグメント段階は、
前記点群データに整列情報が含まれる場合は整列順に基づきセグメント化を行い、前記点群データに整列情報が含まれていない場合は、三角ポリゴンを生成してセグメント化を行うことを特徴とする請求項８に記載の自動生成方法。
【請求項１０】
前記セグメント段階は、
前記セグメント化された点群データのセグメント形状情報から各形状間において、隣接する形状同士の連続性、法線方向、又は距離に基づきエッジ及び面を抽出することを特徴とする請求項８又は９に記載の自動生成方法。
【請求項１１】
前記形状判定生成段階は、
セグメント化された各々のセグメントにおける点群データから最小二乗法を用いて前記所定の関数として設定された平面方程式又は曲面方程式に置き換え、その係数値により固有値及び固有ベクトルを生成することを特徴とする請求項８に記載の自動生成方法。
【請求項１２】
前記形状判定生成段階は、
前記固有値に対する寄与率と、予め設定した閾値とに基づいて平面又は二次曲面の形状を判定することを特徴とする請求項１１に記載の自動生成方法。
【請求項１３】
前記形状判定生成段階は、
前記二次曲面形状から移動量ベクトルを生成することを特徴とする請求項１２に記載の自動生成方法。
【請求項１４】
前記形状判定生成段階は、
前記固有ベクトル及び前記移動ベクトルにより前記セグメントの点群データをオブジェクト座標に変換して曲面形状を生成することを特徴とする請求項１１乃至１３の何れか１項に記載の自動生成方法。
【請求項１５】
三次元座標を持つ複数の点群データから三次元形状を自動生成する三次元形状の自動生成をコンピュータに実行させるためのプログラムにおいて、
前記点群データから三次元形状のエッジ及び面を抽出するためのセグメント化を行うセグメントステップと、
前記セグメントステップにより生成されたセグメント情報及び予め設定された関数に基づいて三次元形状を判定し自動生成する形状判定生成ステップとをコンピュータに実行させるためのプログラム。
【請求項１６】
前記セグメントステップは、
前記点群データに整列情報が含まれる場合は整列順に基づきセグメント化を行い、前記点群データに整列情報が含まれていない場合は、三角ポリゴンを生成してセグメント化を行うことを特徴とする請求項１５に記載のプログラム。
【請求項１７】
前記セグメントステップは、
前記セグメント化された点群データのセグメント形状情報から各形状間において、隣接する形状同士の連続性、法線方向、又は距離に基づきエッジ及び面を抽出することを特徴とする請求項１５乃至１６に記載のプログラム。
【請求項１８】
前記形状判定生成ステップは、
セグメント化された各々のセグメントにおける点群データから最小二乗法を用いて前記所定の関数として設定された平面方程式又は曲面方程式に置き換え、その係数値により固有値及び固有ベクトルを生成することを特徴とする請求項１５に記載のプログラム。
【請求項１９】
前記形状判定生成ステップは、
前記固有値に対する寄与率と、予め設定した閾値とに基づいて平面又は二次曲面の形状を判定することを特徴とする請求項１８に記載のプログラム。
【請求項２０】
前記形状判定生成ステップは、
前記二次曲面形状から移動量ベクトルを生成することを特徴とする請求項１９に記載のプログラム。
【請求項２１】
前記形状判定生成ステップは、
前記固有ベクトル及び前記移動ベクトルにより前記セグメントの点群データをオブジェクト座標に変換して曲面形状を生成することを特徴とする請求項１８乃至２０の何れか１項に記載のプログラム。
【請求項２２】
請求項１５乃至２１何れか一項記載のプログラムを記録した記録媒体。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、三次元形状の自動生成装置、自動生成方法、そのプログラム、及びそのプログラムを記録した記録媒体に係り、特に三次元レーザースキャナー等で取得した点群データから高精度で均質な三次元形状データを自動生成する自動生成装置、自動生成方法、そのプログラム、及びそのプログラムを記録した記録媒体に関する。
【０００２】
【従来の技術】
近年の著しい情報技術（ＩＴ）の発展により、従来の紙ベースの二次元地図から二次元電子地図へ、更にはカーナビゲーションシステムやコンピュータを利用した地理検索システム等、広範な分野をターゲットに三次元電子地図の構築が進められている。
【０００３】
また、三次元の位置情報を持つ点群データを用いて三次元形状データを生成する点群データ処理ソフトウェアは、複数の点群データについて位置合わせ（アラインメント）、統合（マージング）、ポリゴン化等の機能を有し、三次元形状データの生成を実現している。なお、点群データは、実際の建物等の三次元形状を、距離計測器等を用いてレーザースキャニングすることにより取得している。
【０００４】
また、三次元物体における二次元図形情報を用いて、三次元基本形状モデルとの対応付けを行うことで三次元物体の三次元形状モデルを生成する技術が開示されている（例えば、特許文献１参照。）。
【０００５】
【特許文献１】
特開平４―２８９９７６号公報
【０００６】
【発明が解決しようとする課題】
しかしながら、レーザースキャニングで取得した点群データから三次元データを作成する従来のソフトウェアはその機能が未だ十分とは言えず、多くの手作業と熟練技術が必要になっている。
【０００７】
例えば、プラントや建築物等の三次元形状の場合、カーナビゲーションシステム等のコンテンツ制作や３Ｄ−ＣＡＤで利用するためには、明確にエッジと面で構成される三次元データを必要とするが、そのような三次元形状データを生成するには点群データの量が少なすぎるため、特に、レーザースキャニングによる点群データが取得されていない場合、三次元形状の不可視部分（オクルージョン部分）のエッジや面を精度よく生成することができず、多大な手作業の労力を要している。三次元形状が複数あれば、人手による作業が多分に発生し、更に作業者の技術、経験等によって抽出し生成した三次元形状の質にばらつきが生じてしまう。
【０００８】
なお、スキャニングの数を増やして点群の精度を上げた場合にもデータ量が多くなり計算処理時間が増大するという問題があり、三次元デジタル化業務等においては、レーザースキャニングによる点群データをアラインメント、マージング、ポリゴン化及びポリゴンリダクションによる三次元形状データ作成が主体であったが、プラントや建築物等の大規模な対象物においては全ての部分をスキャニングすることは困難であるため現実的な方法ではない。同様に特許文献１に示すようなカメラ画像等からなる二次元図形の取得も困難である。
【０００９】
本発明は、上述した問題点に鑑みなされたものであり、レーザースキャニングという技術を利用して、プラント、建築物・街並、文化財建造物等について高精度な三次元形状データを自動生成することにより手作業や熟練技術を大幅に軽減し、三次元データ作成の均質化、高精度化及び高効率化を実現するための三次元形状の自動生成装置、自動生成方法、そのプログラム、及びそのプログラムを記録した記録媒体を提供することを目的とする。
【００１０】
【課題を解決するための手段】
上記課題を解決するために、本件発明は、以下の特徴を有する課題を解決するための手段を採用している。
【００１１】
請求項１に記載された発明は、三次元座標を持つ複数の点群データから三次元形状を自動生成する三次元形状の自動生成装置において、前記点群データから三次元形状のエッジ及び面を抽出するためのセグメント化を行うセグメント手段と、前記セグメント手段により生成されたセグメント情報及び予め設定された関数に基づいて三次元形状を判定し自動生成する形状判定生成手段とを有することを特徴とする。
【００１２】
請求項１記載の発明によれば、点群データにないオクルージョン部分が、単純な幾何形状で構成されている場合が多いことを利用し、近傍の可視部分の形状、色、対象物の種類等の補足情報から類推してオクルージョン部分のエッジや面を正確に生成することで高精度な三次元形状データを生成する。また、作業者による手作業をなくすことで均質な三次元形状データを生成することができる。
【００１３】
請求項２に記載された発明は、前記セグメント手段は、前記点群データに整列情報が含まれる場合は整列順に基づきセグメント化を行い、前記点群データに整列情報が含まれていない場合は、三角ポリゴンを生成してセグメント化を行うことを特徴とする。
【００１４】
請求項２記載の発明によれば、点群データからセグメントを容易に生成することができる。また、点群データに整列情報が含まれていない場合でも点群データのセグメント化を可能にする。
【００１５】
請求項３に記載された発明は、前記セグメント手段は、前記セグメント化された点群データのセグメント形状情報から各形状間において、隣接する形状同士の連続性、法線方向、距離に基づきエッジ及び面を抽出することを特徴とする。
【００１６】
請求項３記載の発明によれば、セグメント形状同士の連続性、法線方向、距離からエッジ及び面に関する情報を容易に取得することができる。これにより、高精度な三次元形状を生成することができる。
【００１７】
請求項４に記載された発明は、前記形状判定生成手段は、セグメント化された各々のセグメントにおける点群データから最小二乗法を用いて前記所定の関数として設定された平面方程式又は曲面方程式に置き換え、その係数値により固有値及び固有ベクトルを生成することを特徴とする。
【００１８】
請求項４記載の発明によれば、点群データに含まれていない三次元形状のオクルージョン部分に対しても三次元形状を生成することができる。これにより、高精度で均質な三次元形状データを生成することができる。
【００１９】
請求項５に記載された発明は、前記形状判定生成手段は、前記固有値に対する寄与率と、予め設定した閾値とに基づいて平面又は二次曲面の形状を判定することを特徴とする。
【００２０】
請求項５記載の発明によれば、閾値条件に基づき、生成される三次元形状の精度を設定することができ、より詳細で高精度な三次元形状データを生成することができる。
【００２１】
請求項６に記載された発明は、前記形状判定生成手段は、前記二次曲面形状から移動量ベクトルを生成することを特徴とする。
【００２２】
請求項６記載の発明によれば、移動量ベクトルにより、生成する形状における軸の座標等、形状に関する情報を得ることができるため、高精度な三次元形状データを生成することができる。
【００２３】
請求項７に記載された発明は、前記形状判定生成手段は、前記固有ベクトル及び前記移動ベクトルにより前記セグメントの点群データをオブジェクト座標に変換して曲面形状を生成することを特徴とする。
【００２４】
請求項７記載の発明によれば、点群データに含まれていない三次元形状のオクルージョン部分に対しても三次元形状を生成することができる。これにより、高精度で均質な三次元形状データを生成することができる。
【００２５】
請求項８に記載された発明は、三次元座標を持つ複数の点群データから三次元形状を自動生成する三次元形状の自動生成方法において、前記点群データから三次元形状のエッジ及び面を抽出するためのセグメント化を行うセグメント段階と、前記セグメント段階により生成されたセグメント情報及び予め設定された関数に基づいて三次元形状を判定し自動生成する形状判定生成段階とを有することを特徴とする。
【００２６】
請求項８記載の発明によれば、点群データにないオクルージョン部分が、単純な幾何形状で構成されている場合が多いことを利用し、近傍の可視部分の形状、色、対象物の種類等の補足情報から類推してオクルージョン部分のエッジや面を正確に生成することで高精度な三次元形状データを生成する。また、作業者による手作業をなくすことで均質な三次元形状データを生成することができる。
【００２７】
請求項９に記載された発明は、前記セグメント段階は、前記点群データに整列情報が含まれる場合は整列順に基づきセグメント化を行い、前記点群データに整列情報が含まれていない場合は、三角ポリゴンを生成してセグメント化を行うことを特徴とする。
【００２８】
請求項９記載の発明によれば、点群データからセグメントを容易に生成することができる。また、点群データに整列情報が含まれていない場合でも点群データのセグメント化を可能にする。これにより、高精度な三次元形状データを生成することができる。
【００２９】
請求項１０に記載された発明は、前記セグメント段階は、前記セグメント化された点群データのセグメント形状情報から各形状間において、隣接する形状同士の連続性、法線方向、距離に基づきエッジ及び面を抽出することを特徴とする。
【００３０】
請求項１０記載の発明によれば、セグメント形状同士の連続性、法線方向、距離からエッジ及び面に関する情報を容易に取得することができる。これにより、高精度な三次元形状を生成することができる。
【００３１】
請求項１１に記載された発明は、前記形状判定生成段階は、セグメント化された各々のセグメントにおける点群データから最小二乗法を用いて前記所定の関数として設定された平面方程式又は曲面方程式に置き換え、その係数値により固有値及び固有ベクトルを生成することを特徴とする。
【００３２】
請求項１１記載の発明によれば、点群データに含まれていない三次元形状のオクルージョン部分に対しても三次元形状を生成することができる。これにより、高精度で均質な三次元形状データを生成することができる。
【００３３】
請求項１２に記載された発明は、前記形状判定生成段階は、前記固有値に対する寄与率と、予め設定した閾値とに基づいて平面又は二次曲面の形状を判定することを特徴とする。
【００３４】
請求項１２記載の発明によれば、閾値条件に基づき、生成される三次元形状の精度を設定することができ、より詳細で高精度な三次元形状データを生成することができる。
【００３５】
請求項１３に記載された発明は、前記形状判定生成段階は、前記二次曲面形状から移動量ベクトルを生成することを特徴とする。
【００３６】
請求項１３記載の発明によれば、移動量ベクトルにより、生成する形状における軸の座標等、形状に関する情報を得ることができるため、高精度な三次元形状データを生成することができる。
【００３７】
請求項１４に記載された発明は、前記形状判定生成段階は、前記固有ベクトル及び前記移動ベクトルにより前記セグメントの点群データをオブジェクト座標に変換して曲面形状を生成することを特徴とする。
【００３８】
請求項１４記載の発明によれば、点群データに含まれていない三次元形状のオクルージョン部分に対しても三次元形状を生成することができる。これにより、高精度で均質な三次元形状データを生成することができる。
【００３９】
請求項１５に記載された発明は、三次元座標を持つ複数の点群データから三次元形状を自動生成する三次元形状の自動生成をコンピュータに実行させるためのプログラムにおいて、前記点群データから三次元形状のエッジ及び面を抽出するためのセグメント化を行うセグメントステップと、前記セグメントステップにより生成されたセグメント情報及び予め設定された関数に基づいて三次元形状を判定し自動生成する形状判定生成ステップとをコンピュータに実行させる。
【００４０】
請求項１５記載の発明によれば、点群データにないオクルージョン部分が、単純な幾何形状で構成されている場合が多いことを利用し、近傍の可視部分の形状、色、対象物の種類等の補足情報から類推してオクルージョン部分のエッジや面を正確に生成することで高精度な三次元形状データを生成する。また、作業者による手作業をなくすことで均質な三次元形状データを生成することができる。
【００４１】
請求項１６に記載された発明は、前記セグメントステップは、前記点群データに整列情報が含まれる場合は整列順に基づきセグメント化を行い、前記点群データに整列情報が含まれていない場合は、三角ポリゴンを生成してセグメント化を行うことを特徴とする。
【００４２】
請求項１６記載の発明によれば、点群データからセグメントを容易に生成することができる。また、点群データに整列情報が含まれていない場合でも点群データのセグメント化を可能にする。これにより、高精度な三次元形状データを生成することができる。
【００４３】
請求項１７に記載された発明は、前記セグメントステップは、前記セグメント化された点群データのセグメント形状情報から各形状間において、隣接する形状同士の連続性、法線方向、距離に基づきエッジ及び面を抽出することを特徴とする。
【００４４】
請求項１７記載の発明によれば、セグメント形状同士の連続性、法線方向、距離からエッジ及び面に関する情報を容易に取得することができる。これにより、高精度な三次元形状を生成することができる。
【００４５】
請求項１８に記載された発明は、前記形状判定生成ステップは、セグメント化された各々のセグメントにおける点群データから最小二乗法を用いて前記所定の関数として設定された平面方程式又は曲面方程式に置き換え、その係数値により固有値及び固有ベクトルを生成することを特徴とする。
【００４６】
請求項１８記載の発明によれば、点群データに含まれていない三次元形状のオクルージョン部分に対しても三次元形状を生成することができる。これにより、高精度で均質な三次元形状データを生成することができる。
【００４７】
請求項１９に記載された発明は、前記形状判定生成ステップは、前記固有値に対する寄与率と、予め設定した閾値とに基づいて平面又は二次曲面の形状を判定することを特徴とする。
【００４８】
請求項１９記載の発明によれば、閾値条件に基づき、生成される三次元形状の精度を設定することができ、より詳細で高精度な三次元形状データを生成することができる。
【００４９】
請求項２０に記載された発明は、前記形状判定生成ステップは、前記二次曲面形状から移動量ベクトルを生成することを特徴とする。
【００５０】
請求項２０記載の発明によれば、移動量ベクトルにより、生成する形状における軸の座標等、形状に関する情報を得ることができるため、高精度な三次元形状データを生成することができる。
【００５１】
請求項２１に記載された発明は、前記形状判定生成ステップは、前記固有ベクトル及び前記移動ベクトルにより前記セグメントの点群データをオブジェクト座標に変換して曲面形状を生成することを特徴とする。
【００５２】
請求項２１記載の発明によれば、点群データに含まれていない三次元形状のオクルージョン部分に対しても三次元形状を生成することができる。これにより、高精度で均質な三次元形状データを生成することができる。
【００５３】
請求項２２に記載された発明は、前記請求項１５乃至２１何れか一項記載のプログラムを記録媒体に記録したものである。
【００５４】
【発明の実施の形態】
本発明は、レーザースキャニング等から取得した点群データを用いて、エッジと面の抽出及び生成と、パターン認識及びパターンマッチングによる点群データ欠落部の補完とを効率的で高精度に行うことにより三次元形状データを自動生成する。これにより、従来の三次元モデリング手法と比較して三次元形状データの生成を飛躍的に高効率化することができる。また、三次元形状データの生成に関して大幅なコストダウンを可能にする。
【００５５】
なお、本発明では、点群データにないオクルージョン部分が、単純な幾何形状で構成されている場合が多いことを利用し、近傍の可視部分の形状、色、対象物の種類等の補足情報から類推してオクルージョン部分のエッジや面を正確に生成することで高精度な三次元形状データを生成する。
【００５６】
次に、本発明の実施の形態について、図面を用いて説明する。
【００５７】
図１は、本発明における三次元形状自動生成装置の一構成例を示す図である。
【００５８】
図１の三次元形状自動生成装置１は、点群データ入力部２と、セグメンテーション部３と、形状生成部４と、記憶部５と、出力部６とを有するよう構成されている。
【００５９】
三次元形状自動生成装置１では、上述したように、点群データ入力部２から計測器で測定された入力データを入力しレンジ画像を生成して、セグメンテーション部３へ出力する。セグメンテーション部３では、レンジ画像における各計測点のセグメンテーション化を行い、その結果を形状生成部４に出力する。形状生成部４では、記憶部５に予め記憶されている関数及び閾値データを用いて三次元形状の生成を行う。三次元形状が生成された後、その出力データをディスプレイ等の出力部６から作業者が容易に自動生成された三次元形状を把握できるよう出力を行う。これにより、均質で高精度な三次元形状データを生成することができる。
【００６０】
次に、具体的な三次元形状生成手順について説明する。本発明における三次元形状データの自動生成では、大別して以下に示す２つの手順からなる。
【００６１】
（１）エッジ及び面の抽出及び生成
点群データ入力部２によりレーザースキャナーにより計測した点群データが入力されるとセグメンテーション部３で点群データを解析し、その幾何形状を利用してエッジ及び面の抽出を行う。具体的には、計測した点群データから矩形形状を生成し、その矩形形状間において、隣接するポリゴン同士の連続性、法線方向、距離等により、エッジ及び面を認識する。また、点群データの平面性又は曲面性を、平面方程式又は曲面方程式に対して最小二乗法を用いて置き換え、グループ分け（セグメンテーション化）を行う。ここで得られたグループをより計測対象物に類似又は同一となるようなプリミティブな形状へ再度置き換えることでエッジ及び面の生成を行う。
【００６２】
（２）オクルージョン部分の補完
抽出したエッジ及び面の情報を形状生成部４に出力し、形状生成部４は、点群データが取得できなかった部分（オクルージョン部分）の形状について、欠落部近傍の形状特徴によるパターンマッチングを行い当該欠落部分の形状を類推する。これにより、欠落部分を補完して全体の三次元形状データを生成する。
【００６３】
なお、形状特徴としては、平面形状、円柱、円錐、球等の予め記憶部５に設定された形状を用いる。生成された三次元形状データは出力部６にて出力され、これにより作業者が生成された三次元形状データを容易に確認することができる。また、記憶部５は、後述する各プロセスで設定される閾値データ及び関数データ、更には点群データ等の本発明における三次元形状データの自動生成に必要なデータを記憶することができ、セグメンテーション部３、又は形状生成部４が必要に応じてデータを読み出し、あるいは蓄積することができる。
【００６４】
ここで、本発明における三次元データの自動生成手順の概略についてフローチャートを用いて説明する。図２は、本発明における三次元データ自動生成手順の概略を示す一例のフローチャートである。
【００６５】
エッジ及び面の抽出及び生成するためのセグメンテーションプロセスでは、レーザースキャニングにより計測された頂点群であるレンジ画像のセグメンテーションを行う方法として、まず、セグメントの最小なユニットとして三角ポリゴンを形成し（Ｓ０１）、形成された複数の三角ポリゴンの夫々に対する隣接関係により、互いに接続関係にあるセグメント同士の同一平面性及び同一曲面性を最小二乗法により判定しながら繰り返しセグメンテーションの検索を行う（Ｓ０２）。
【００６６】
次に、セグメンテーションにより生成されたセグメントの形状情報からオクルージョン部分の補完するための形状判別と判別結果から三次元形状を自動生成する判別形状・自動生成プロセスでは、各々のセグメントは最小二乗法により求められた平面方程式又は曲面方程式に対応しているので、計測された物体形状はこれらのセグメントによって近似することができる。例えば、二次曲面形状の場合、実際には計測されていないオクル−ジョン部分を、曲面方程式により推定して形状生成を行うことが可能となる。
【００６７】
しかしながら、平面又は曲面が混在したセグメンテーションを行う場合、各々のセグメントは平面であっても二次曲面方程式に当てはまってしまうため、セグメントを平面又は曲面のどちらとして扱うか、また、曲面として扱う場合、二次曲面形状の中から、どの形状で近似を行うかが問題となる。
【００６８】
そこで、二次曲面形状は固有値により分類ができる性質に着目し、二次曲面方程式の係数により固有値、固有ベクトルの導出を行い（Ｓ０３）、固有値による平面、曲面あるいは二次曲面形状の判別を行う（Ｓ０４）。
【００６９】
更に、Ｓ０４から得られた判別結果に基づいて、平面形状の生成を行い（Ｓ０５）、二次曲面形状の生成を行った後（Ｓ０６）、三次元形状データの生成を行う（Ｓ０７）。これにより、三次元データの自動生成を均質で高精度に行うことができる。
【００７０】
次に、上述のセグメンテーションプロセス（Ｓ０１〜Ｓ０２）と、形状判別・自動生成プロセス（Ｓ０３〜Ｓ０７）について、具体的に説明する。
【００７１】
（Ｓ０１ステップ：点群データの三角ポリゴン化）
最初に点群データの三角ポリゴン化について説明する。
【００７２】
入力点群データが格子状に並べられている場合は、その並び順により三角ポリゴンを形成する。なお、三角形のエッジの長さが事前に設定した閾値より大きくなる場合は三角ポリゴンを生成しない。
【００７３】
そこで、点群データがｘ，ｙ，ｚ座標値のみで並び順に規則性がない場合は「Ｄｅｌａｕｎａｙ  Ｔｒｉａｎｇｌａｔｉｏｎ（ドロネイ分割：三角形の外接円の内部に、他の頂点を含まないようにして三角形群を生成する幾何アルゴリズム）」により三角ポリゴンを生成する。
【００７４】
つまり、計測した点群データの各点から三角形を生成する場合に、距離の近さだけで判断すると重なりあったデータから不適切な三角形が生成される可能性があるため、ドロネイの定義に基づき三角形の外接円の中に他の三角形の頂点は存在しないようにして三角形の生成を行う。なお、以上のプロセスが終了した段階で、個々の三角ポリゴンを一つのセグメントとして扱う。
ここで、上述により形成される入力レンジ画像に対する最小ユニットセグメントの結果を図に示す。
【００７５】
図３は、Ｓ０１のステップ実行後の結果の一例を示す図である。なお、図３（ａ）は、入力レンジ画像を示し、図３（ｂ）は、図３（ａ）から抽出された不規則な点群データを示し、図３（ｃ）は、上述した「Ｄｅｌａｕｎａｙ  Ｔｒｉａｎｇｌａｔｉｏｎ」により、形成された最小ユニットセグメント（三角ポリゴン）の形成結果を示す図である。
【００７６】
（Ｓ０２：最小二乗法により同一セグメントの検索）
次に、Ｓ０２として一次、二次方程式によるセグメンテーションとして最小二乗法による同一セグメントを検索する。
【００７７】
ここで、具体的な例をあげて説明すると、任意のセグメントＳｅ、及び、Ｓｅと接続関係にあるセグメントＳｉ（ｉ＝０，１，・・・、ｎ）が同一セグメントとして扱えるかどうかを判定する。図４は、Ｓ０２のステップにおける動作を説明するための一例の図である。なお、図４（ａ）は、Ｓ０２のステップを実施前の最小ユニットセグメントを生成した図であり、セグメントＳｅの周りには、Ｓ０，Ｓ１，Ｓ２，Ｓ３の４つのセグメントが隣接している。
【００７８】
まず、Ｓｅに属する点群データから最小二乗法を用いて下記平面方程式（（１）式）の係数を求める。
【００７９】
【数１】
2004272459.tif 000003
次に、Ｓｉに属する点群データの、平面方程式である（１）式に対する残差の分散値Ｖを下記（２）式により求める。
【００８０】
【数２】
2004272459.tif 000004
残差の分散値が事前に設定した閾値ＴＰ以下の場合、ＳｅとＳｉを同一セグメントとする。以上の処理を残りのセグメントに対しても同様に行い、セグメンテーションが行われなくなるまで繰り返す。
【００８１】
平面方程式によるセグメンテーションが終了したら、セグメントの点群データから最小二乗法を用いて、下記に示す二次曲面方程式（（３）式）の係数を求め、更に、残差の分散値Ｖを下記（４）式により求めて、残差の分散値が事前に設定した閾値ＴＱ以下の場合、ＳｅとＳｉを同一セグメントとする。
【００８２】
【数３】
2004272459.tif 000005
【００８３】
【数４】
2004272459.tif 000006
以上の処理を平面方程式の場合と同様に、セグメンテーションが行われなくなるまで繰り返す。これにより、個々のセグメントから同一セグメントとなる領域を抽出しセグメント化することができる。
【００８４】
図４（ｂ）では、上述の手法により算出されたセグメンテーション適用結果を示す一例の図であり、Ｓｅの同一セグメントとしてＳ１及びＳ３が適用されたことを示している。
【００８５】
（Ｓ０３：固有ベクトルの導出）
次に、形状判別・自動生成プロセスとして、Ｓ０２にて得られる各々のセグメントに属する点群データから最小二乗法を用いて下記（５）式に示す陰関数形式による二次曲面方程式の係数を求める。
【００８６】
【数５】
2004272459.tif 000007
ここで、
【００８７】
【数６】
2004272459.tif 000008
として、Ｍの固有値ｅｉ、固有ベクトルｅｖｉを求める（ｉ＝１，２，３）。次に、Ｍの固有値ｅｉの寄与率ｃｉを下記（７）式により求める。
【００８８】
【数７】
2004272459.tif 000009
ここで、寄与率ｃｉの値と予め設定された閾値ＴＥとを比較し、寄与率ｃｉより閾値ＴＥより小さい場合は固有値ｅｉを０にする。
【００８９】
これにより、形状判定を行うための固有値・固有ベクトルを算出することができる。
【００９０】
（Ｓ０４：平面・曲面の判別）
次に、平面・曲面の判別について説明する。Ｓ０４では、上述した（１）式の係数により求められた固有値ｅｉのうち２つが０の場合、そのセグメントを平面セグメントとみなし、それ以外を曲面セグメントとする。
【００９１】
（Ｓ０５：平面形状の生成）
上述したセグメンテーションプロセスが終了した段階で、各セグメントは平面であっても曲面方程式によるセグメンテーションを実行しているので、再度、平面セグメントの点群データから最小二乗法を用いて下記（８）式に示す陰関数形式による平面方程式の係数を求める。
【００９２】
【数８】
2004272459.tif 000010
ここで、陰関数形式による平面方程式の係数は、平面の法線ベクトルとなる。（８）式の係数及び点群の中心座標値により、点群データをオブジェクト座標に変換する。次に、平面セグメントの点群を囲む矩形のうち、最小面積となる矩形を検索し平面を生成する。
【００９３】
図５は、矩形の検索内容の一例を示す図である。ここで、図５に示す点群５１は、同一セグメント内に存在する点群である。図５に示すように点群５１の全ての点を含む最小矩形領域を検索する。検索方法は、図５に示すように矩形５２を外周にある点群に接触する矩形を少しずつ左に回転させながら、点群全体を含む矩形の面積を計算し、最小となる面積の矩形の配置を決定する。
【００９４】
なお、本発明では、同様に五角形やコの字形等、多角形データに蓄積された他の凹凸多角形に対しても最小面積を計算し、求めた最小面積の値の中で更に最小の多角形を最小面積矩形とする。また、図５では矩形を左に回転させたが本発明においては、この限りではなく、右に回転させてもよく、また、多角形を固定した状態にして点群グループを回転させてもよい。
【００９５】
なお、使用する矩形は、予め基本形状を設定した多角形データとして蓄積されており、例えば、凸多角形であれば矩形、菱形、正八角形等であり、凹多角形であればＬ字型、コの字型、Ｔ字型、十字型等である。点群グループ毎に各種凹凸多角形を割当ててもよい。
【００９６】
（Ｓ０６：二次曲面形状の生成）
（ｉ）曲面形状の判別
次に、二次曲面形状の生成について説明する。なお、本実施例では、曲面形状の判別として「楕円柱面」、「楕円錐面」、及び「楕円球面」を用いて曲面形状の判別手法について説明する。
【００９７】
曲面形状の判別では、（１）式における二次曲面方程式の係数により求められた固有値により曲面形状を判定する。
【００９８】
ここで、曲面判定基準の例について表を用いて説明する。表１は、本発明における曲面形状を分類する際の判定条件の一例を示すものである。
【００９９】
【表１】
2004272459.tif 000011
表１に示すように「楕円柱面」、「楕円錐面」、及び「楕円球面」の夫々について、係数ｅ１，ｅ２、及びｅ３の符号に基づいて形状の判定を行う。表１において、係数ｅ１，ｅ２、及びｅ３の符号は、０より大きい場合に「＋」とし、０より小さい場合は「−」とする。
（ｉｉ）移動ベクトルの抽出
次に、生成する三次元形状の軸の座標等を定める。上述の方法により判別された二次曲面形状が「楕円錐面」及び「楕円球面」の場合は、逆行列により移動量ベクトルを算出し、「楕円柱面」の場合は、特異値分解（ＳＶＤ：Ｓｉｎｇｕｌａｒ  Ｖａｌｕｅ  Ｄｅｃｏｍｐｏｓｉｔｉｏｎ）等により二次曲面形状の移動量ベクトルを求める。
（ｉｉｉ）曲面形状の生成
固有値に対する固有ベクトルはオブジェクトの軸になるので、移動量ベクトル、固有ベクトルによりセグメントの点群データをオブジェクト座標に変換する。次に、セグメントに属する点群データから最小二乗法を用いて、上述の「（ｉ）曲面形状の判別」で判別された二次曲面形状の方程式の係数を求め、曲面形状を生成する。ここで、上述した「楕円柱面」、「楕円錐面」、及び「楕円球面」の夫々の一般式を以下に示す。
【０１００】
【数９】
2004272459.tif 000012
また、上述の数式により、形成される曲面形状について、図を用いて説明する。図６は、曲面形状の一例を示す図である。ここで、図６（ａ）は、楕円柱面の形状の例を示し、図６（ｂ）は、楕円錐面の形状の例を示し、図６（ｃ）は、楕円球面の形状の例を示すものである。図６に示すように、上記数９にて記載された一般式の係数を求めることにより、三次元におけるオクリュージョン部分の形状の補間を行うことができ、高精度な三次元形状を生成することができる（Ｓ０７）。
【０１０１】
なお、生成される形状の種類についてはこの限りではなく、他の形状についても同様に形状に対応する数式を用いることで三次元形状を高精度に形成することができる。
【０１０２】
次に、上述したセグメンテーションプロセスと、形状判別・自動生成プロセスの処理手順として、フローチャートを用いて説明する。
【０１０３】
図７は、本発明おけるセグメンテーションプロセスの一例を示すフローチャートである。
【０１０４】
まず、既に取得されている点群データの読み込みを行い（Ｓ１１）、点群データが整列されて記述されているかを判断する（Ｓ１２）。点群データが整列されていない場合は（Ｓ１２において、ＮＯ）、上述したように「ＤｅｌａｕｎａｙＴｒｉａｎｇｌｅ」により最小ユニットセグメントの生成を行う（Ｓ１３）。また点群データが整列されている場合は（Ｓ１２において、ＹＥＳ）、並び順に基づいて最小ユニットセグメントメンの生成を行う（Ｓ１４）。
【０１０５】
Ｓ１３又はＳ１４のステップが終了後、生成された最小ユニットセグメントの中から隣接セグメントの検索を行い、平面方程式のよるセグメンテーションを行う（Ｓ１５）。次に、平面方程式によるセグメンテーションが終了しているかを判断し（Ｓ１６）、終了している場合は（Ｓ１６において、ＹＥＳ）、最小二乗法によりセグメントの曲面方程式を求める（Ｓ１７）。また、隣接セグメントの曲面方程式に対する残差の分散値を算出する（Ｓ１８）。
【０１０６】
また、平面方程式によるセグメンテーションが終了していない場合は（Ｓ１６において、ＮＯ）、最小二乗法によりセグメントの平面方程式を求め（Ｓ１９）、隣接セグメントの平面方程式に対する残差の分散値を算出する（Ｓ２０）。
【０１０７】
次に、Ｓ１８又はＳ２０のステップが終了後、算出された分散値が設定した閾値より小さいかを判断し（Ｓ２１）、小さい場合は（Ｓ２１において、ＹＥＳ）、セグメントと隣接セグメントを同一セグメントとする処理を行う（Ｓ２２）。また、Ｓ２１において、分散値が設定した閾値以上の場合（Ｓ２１において、ＮＯ）は、次の最小ユニットに対してＳ１６からの処理を行う。
【０１０８】
ここで、Ｓ１６からＳ２２までの隣接セグメントを生成するステップは、Ｓ１３又はＳ１４のステップにて生成された全ての最小ユニットセグメントに対して繰り返し処理を行い、また、Ｓ１５からＳ２２までのセグメントの生成ステップについて、全ての最小ユニットセグメントに対して行う。
【０１０９】
次に、全ての最小ユニットセグメントについてセグメンテーション処理を行った後、セグメンテーションが完了しているかを判断し（Ｓ２３）、完了していなかった場合は（Ｓ２３において、ＮＯ）、Ｓ１５における検索方法や、Ｓ２１における閾値等の設定条件を変更して（Ｓ２４）、再びセグメント処理を行う。また、セグメンテーションが完了している場合は（Ｓ２３において、ＹＥＳ）、曲面方程式によるセグメンテーションが終了しているかを判断し（Ｓ２５）、終了していない場合は（Ｓ２５において、ＮＯ）、閾値等の設定条件を変更して（Ｓ２４）、Ｓ１５からのセグメント処理を行う。また、曲面方程式によるセグメンテーションが終了している場合は（Ｓ２５において、ＹＥＳ）、セグメンテーションプロセスを終了する。
【０１１０】
次に、形状判別・自動生成プロセスについて説明する。図８は、本発明における形状判別・自動生成プロセスの一例を示すフローチャートである。
【０１１１】
まず前提として、上述したセグメンテーションプロセスにより、点群データのセグメンテーションが行われている（Ｓ３１）。次に、セグメンテーションにより生成されたセグメント形状情報に基づき、最小二乗法によりセグメントに属する点群データから二次曲面方程式の係数を求める（Ｓ３２）。２次曲面方程式の係数より固有値ｅｉ、固有ベクトルｅｖｉの計算を行う（Ｓ３３）。なお、固有値ベクトルは三次元であるため、３つの固有値が算出される。
【０１１２】
次に、計算した固有値ｅｉの寄与率が設定した閾値より小さい場合、固有値を０とする（Ｓ３４）。ここで、Ｓ３３のステップによる算出された固有値ｅｉのうち２つが０であるかを判断し（Ｓ３５）、２つが０である場合は（Ｓ３５において、ＹＥＳ）、平面セグメントの点群を囲む矩形のうち、最小面積となる矩形を抽出する（Ｓ３６）。また、Ｓ３６にて抽出された矩形を用いて平面におけるプリミティブな形状の生成を行う（Ｓ３７）。
【０１１３】
一方、固有値ｅｉのうち２つが０でない場合は（Ｓ３５において、ＮＯ）、ｅｉにおける３つの固有値ｅ１，ｅ２，ｅ３に基づく形状の生成を行う。なお、この条件は、上述の表１に対応するものであるが、ここでは、フローチャートに対応させて説明する。
【０１１４】
まず、ｅ１，ｅ２が０より大きく、更にｅ３が０であるかを判断し（Ｓ３８）、Ｓ３８の条件に該当する場合は（Ｓ３８において、ＹＥＳ）、楕円柱面の生成を行う（Ｓ３９）。また、Ｓ３８の条件に該当しない場合は（Ｓ３８において、ＮＯ）、ｅ１，ｅ２が０より大きく、ｅ３が０より小さいかを判断し（Ｓ４０）、Ｓ４０の条件に該当する場合は（Ｓ４０において、ＹＥＳ）、楕円錐面の生成を行う（Ｓ４１）。また、Ｓ４０の条件に該当しない場合は（Ｓ４０において、ＮＯ）、次に固有値ｅ１，ｅ２，及びｅ３が共に０であるかを判断する（Ｓ４２）。
【０１１５】
固有値ｅ１，ｅ２，及びｅ３が共に０である場合は楕円球面の生成を行い（Ｓ４３）、ｅ１，ｅ２，及びｅ３が共に０でない場合は、その他の形状の割り当てを行う（Ｓ４４）。Ｓ４４のステップでは、楕円ではない所定の曲面を割り当てることもでき、また、多角形状を割り当てることもできる。また、何も割り当てなくてもよい。なお、Ｓ３２からＳ４４までのステップは、Ｓ３１に取得した点群データの全てのセグメンテーションにおいて行う。
【０１１６】
これにより、点群データからでは取得することができなかった三次元形状のオクルージョン部分について補間することができ、高精度な三次元形状を生成するこができる。
【０１１７】
上述により本発明によれば、人手によることなく、低コストで自動的に且つ均質な三次元形状データを生成することができる。また、三次元形状データの生成に関して大幅なコストダウンを可能にする。
【０１１８】
なお、上述したセグメンテーションプロセスと、形状判別・自動生成プロセスとをコンピュータに実行させるような実行プログラムを生成し、例えば、汎用のパーソナルコンピュータ、ワークステーション等にインストールすることにより本発明における三次元形状の自動生成が容易に実行可能となる。ここで、実行可能となるコンピュータのハードウェア構成例について図を用いて説明する。
【０１１９】
図９は、本発明における三次元形状自動生成が実現可能なハードウェア構成の一例を示す図である。
【０１２０】
図９において、三次元形状の自動生成装置全体を統括的に制御するプログラムされた主制御部（制御手段、以下ＣＰＵと略称する）１０に、記憶装置２０が接続されている。ＣＰＵ１０には、入力制御部３０を介してキーボードやマウス等のポインティングデバイスからなる入力装置４０、実行指示画面表示、出力結果表示等のモニタに用いる表示装置５０、及び生成された三次元形状データを出力する出力装置６０が接続されている。
【０１２１】
ＣＰＵ１０は、ＯＳ（Ｏｐｅｒａｔｉｎｇ  Ｓｙｓｔｅｍ）等の制御プログラム、三次元形状を生成するための処理手順を規定したプログラム、及び所要データを格納するための内部メモリを有し、これらのプログラム等により、点群グループをセグメンテーションする処理、セグメント化された点群データから形状を判別し、三次元形状を自動生成する処理等を実現している。記憶装置２０は、ハードディスクやフレキシブルディスク、或いは光ディスク等のストレージ手段であり、点群データ２１、閾値データ２２、関数データ２３が格納されている。
【０１２２】
ここで、上述したセグメンテーションプロセス及び形状判別・自動生成プロセスにおける夫々のステップは、作業者が入力装置４０からのプログラムの実行指示することでＣＰＵ１０の制御に基づいて入力制御部３０によりデータ、制御信号の入出力が行われ、セグメンテーションプロセス及び形状判別・自動生成プロセスが実行される。また、本発明において三次元形状データを自動生成するのに必要な点群データ２１、閾値データ２２、及び関数データ２３は、必要に応じて記憶装置２０から取得することができる。上述において、生成された三次元形状データは出力装置６０に出力され、表示装置５０には処理結果が出力される。
【０１２３】
なお、上述したハードウェア構成において、入力装置４０は三次元形状自動生成装置１の点群データ入力部２に、記憶装置２０は記憶部５に、また表示装置５０，出力装置６０は出力部６に夫々相当し、セグメンテーション部３及び形状生成部４とにおける処理はＣＰＵ１０が実行プログラムにより実行する。
【０１２４】
上述のプログラムを用いることにより、パーソナルコンピュータに一般的に具備されているハードウェア構成を用いて本発明における三次元形状の自動生成を容易に行うことができる。
【０１２５】
また、本発明における三次元形状データを自動生成するためのプログラムはＣＤ−ＲＯＭ、フロッピー（登録商標）ディスク等の持ち運び可能な記録媒体に格納することにより任意の端末で実行することができる。上述したようなハードウェア構成により、人手によることなく、低コストで自動的に且つ均質な三次元形状データを生成することができる。
（自動生成結果）
次に、本発明を用いて自動生成された距離画像における三次元データの自動生成結果について説明する。なお、点群データのセグメンテーションと形状判別・自動生成については、計測に使用したレーザーレンジファインダ（距離計測器）として「ＶＩＶＩＤ９００」（精度Ｘ＝±１．４０ｍｍ，Ｙ＝±１．０４ｍｍ，Ｚ＝±０．６４ｍｍ）、及び「Ｃｙｒａｘ２５００」（精度Ｘ，Ｙ＝±６．００ｍｍ，Ｚ＝±４．００ｍｍ）を用いるものとする。また、後述の三次元形状の生成にて用いられる計測対象物（球体、円錐、立体）の実際のサイズを図に示す。
【０１２６】
図１０は、本発明における三次元形状データの自動生成に用いられる計測対象物の一例を示す図である。ここで、図１０（ａ）は円錐の図を示し、図１０（ｂ）は球体の図を示し、図１０（ｃ）は正方体の図を示している。図１０の図に基づいて、種々の条件に基づき、三次元形状データを自動生成した結果について説明する。
【０１２７】
まず、セグメンテーションプロセスにおいて、三次元レーザースキャナーから得られた点群データであるレンジ画像（距離画像）に対して、一次方程式によるセグメンテーションを行う際に設定する閾値ＴＰ、及び二次方程式によるセグメンテーションを行う際に設定する閾値ＴＱを変化させた場合におけるセグメンテーション結果について図を用いて説明する。
【０１２８】
図１１は、異なる閾値に基づくセグメンテーション結果の一例を示す図である。
【０１２９】
ここで、図１１（ａ）は、入力されるレンジ画像を示し、図１１（ｂ）は閾値ＴＰ，ＴＱを共に０．００１ｍに設定した結果を示し、図１１（ｃ）は閾値ＴＰを０．００１ｍ、ＴＱを０．００５ｍに設定して結果を示し、図１１（ｄ）は、閾値ＴＰ，ＴＱを共に０．０１ｍに設定した結果を示す図である。なお、図１１の結果は、計測器「ＶＩＶＩＤ９００」を使用して計測した点群データを使用したものである。
【０１３０】
図１１（ｂ）では、閾値が小さいため、二次曲面形状（球、円錐）が１つのセグメントとして判断されていないケースである。しかしながら、単純に閾値を大きくすれば、隣接関係にあるセグメント同士が同一セグメントとなるわけではない。図１１（ｄ）でオブジェクトの置かれている平面が同一セグメントとなっていないのは、閾値を大きく設定したために円錐と床の一部が同一セグメントとなってしまい、平面同士の隣接関係が途絶えてしまったためである。
【０１３１】
これにより、図１１の（ｂ）から（ｄ）において、最適な閾値の設定は、図１１（ｂ）であることがわかる。上述したように、閾値を設定してセグメンテーションを行うことにより高精度な形状を取得することができる。
【０１３２】
次に、図１１に示す球体のみを計測器「Ｃｙｒａｘ２５００」により計測して得られたレンジ画像に対するセグメンテーション結果について説明する。
【０１３３】
図１２は、異なる機器で計測して点群データを用いたセグメンテーション結果の一例を示す図である。
【０１３４】
ここで、図１２（ａ）は、入力レンジ画像を示し、図１２（ｂ）は、閾値ＴＰを０．００１ｍ、ＴＱを０．００５ｍに設定して結果を示し、図１２（ｃ）は、閾値ＴＰを０．０１ｍ、ＴＱを０．０２ｍに設定した結果を示し、図１２（ｄ）は、計測誤差を示す図である。
【０１３５】
図１２（ｂ）は、図１１（ｃ）と同じ閾値を設定した場合における結果であるが、計測器のレンジ誤差、及びレンジ画像の点群間隔よりも閾値が小さい値なので、平面内にあっても同一セグメントとなっていない個所が多数存在する。また、図１２（ｃ）は、見た目には良好な結果が得られているが、図１２（ｄ）に示すように奥行き方向へ流れたレンジ誤差が発生している。これは、図１２のレンジ画像が計測器で推奨している計測レンジの最小値付近（計測器から対象物までの距離が１．５ｍ）で計測されているために生じたものである。
【０１３６】
また、図１３は、広範囲を計測した場合のセグメンテーション結果を示す図である。ここで、図１３（ａ）は、図１２と同様に計測器「Ｃｙｒａｘ２５００」で計測したレンジ画像を示し、図１３（ｂ）は、閾値ＴＰを０．０２ｍ、ＴＱを０．０２ｍに設定して結果を示し、図１３（ｃ）は、閾値ＴＰを０．０２ｍ、ＴＱを０．０５ｍに設定した結果を示す図である。
【０１３７】
図１３（ｂ）と図１３（ｃ）を比較すると、図１３（ｃ）のほうが床面に対するセグメンテーションがうまく行われている。以上の実測結果によりセグメンテーション時に設定する閾値は、およそ閾値ＴＰが計測器の計測誤差の１〜２倍、閾値ＴＱが２〜５倍程度の範囲で設定するのが妥当であると考えられる。
【０１３８】
次に、形状判別・自動生成プロセスの三次元データの自動生成結果について説明する。ここで、後述する自動生成結果については、セグメンテーションが比較的良好に行われているレンジ画像に対して、固有値の寄与率を０にする閾値ＴＥを変化させた場合における形状判別・自動生成の違いを表したものである。
【０１３９】
図１４は、本発明における異なる閾値による形状判別・自動生成結果の一例を示す図である。
【０１４０】
ここで、図１４（ａ）は閾値ＴＥを０．００５に設定した結果であり、図１４（ｂ）は、閾値ＴＥを０．０１に設定した場合における形状生成の違いを示すものである。
【０１４１】
図１４（ａ）では、円錐が形成されているが、図１４（ｂ）では、固有値の寄与率の１つが閾値よりも小さい値になっているため、円柱として認識された結果である。また、自動生成の不具合は、上述した閾値ＴＥの設定の他に、レンジ誤差により自動生成の不具合もある。ここで、上述の内容について図を用いて説明する。
【０１４２】
図１５は、レンジ誤差による自動生成不具合の一例を示す図である。なお、図１５は、上述した図１２（ｃ）のセグメンテーション結果から自動生成を行った結果である。
【０１４３】
図１２（ｄ）に示すようなレンジ画像に誤差が含まれると図１５（ｂ）に示すように自動生成された三次元形状が楕円形になってしまう。この対処法として、レンジ誤差に対応した閾値に変更する方法や、実在する物体には楕円形より正形が多いので正形に当て嵌めてしまう方法により対応することができる。
【０１４４】
ここで、自動生成結果の一例として、図１４における形状判別・自動生成結果を表２、表３に示す。
【０１４５】
【表２】
2004272459.tif 000013
表２では、図１４において、計測器「ＶＩＶＩＤ９００」を用いて閾値ＴＰを０．００１ｍ、閾値ＴＱを０．０１ｍ、閾値ＴＥを０．００５ｍとして三次元形状判別を行った際の係数（固有値）ｅ１，ｅ２，ｅ３における固有値及び寄与率を示している。また、図１４の立方体については上面、左面、右面の夫々についての固有値、寄与率を示している。
【０１４６】
ここで、表２▲１▼において固有値ｅ３となる固有値「―０．０１０３３５」の寄与率が０．０７２７７と閾値ＴＥよりも小さい値になっているため、実際は円錐でありながら、図１４（ｂ）に示す円柱として図形が生成されている。ここで、閾値ＴＥを調整し再度計算した結果が表３に示すものである。
【０１４７】
【表３】
2004272459.tif 000014
表３は、図１０で示した実際の計測対象物における自動生成された三次元形状のサイズ（単位ｍ）を示すものである。表３に示すように最適となる閾値を設定することにより全ての計測対象物に対し、図１０に示す形状とほぼ同一の高精度な三次元形状を自動生成することができる。
【０１４８】
上述したように本発明により、高精度で均質な三次元形状データの自動生成を実現することができる。
【０１４９】
次に、より高精度に三次元形状を自動生成するための応用例について、いくつか例を用いて説明する。
（応用例１：複数レンジ画像の自動マージング）
計測対象が比較的簡単な形状である場合は、方程式により近似してオクル−ジョン部分を補完することができるが、より複雑な形状を対象とする場合は、対象物体を複数の地点から計測し、取得した各々のレンジ画像の位置合わせを行う必要がある。しかしながら、複数のレンジ画像の位置を合わせるには正確な計測地点の位置や計測方向が必要であり、それらの情報の取得には角度を計測するためのトランシットや、距離、角度を同時に測ることのできるトータルステーション等を用いた測量技術が求められる。これらの作業は熟練を要し、また計測効率も低下させる。
【０１５０】
そこで、複数の計測地点から得られた複数のレンジ画像を自動でマッチングして、全てのレンジ画像をグローバル座標系に変換する手法が必要となる。以下に具体的なマージング手順を示す。
【０１５１】
（応用例１−１：二つのレンジ画像のマージング）
まず、各レンジ画像から任意に３つのセグメントを選び、これらを対応するセグメントと仮定する。次に、対応するセグメントから、回転行列と移動量ベクトルを推定し、推定した回転行列と移動量ベクトルを用いて２つのレンジ画像を重ね合わせたとき互いに一致するセグメントの一致度を固有値、固有ベクトルにより求める。
【０１５２】
全てのセグメントの組み合わせで上述までの処理を行い、最も一致度の高い回転行列と移動量ベクトルを採用する。
【０１５３】
（応用例１−２：複数レンジ画像のマージング）
複数のレンジ画像の場合は、任意のレンジ画像Ｒ１と、計測地点がＲ１に最も近いレンジ画像Ｒ２のマージングを行い２つの画像を統合する。統合したレンジ画像に、計測地点が最も近いレンジ画像Ｒ３とのマージングを行う。
【０１５４】
残りのレンジ画像に対しても同様の処理を行い、複数レンジ画像を一つのレンジ画像に統合する。
【０１５５】
（応用例２：パラメトリック曲面への置き換え）
複雑な形状を対象とする自動生成においては、一般的な平面や二次曲面形状だけでは表現できないケースも存在する（例：いす、車のボディー等）。そのような形状を生成する場合は、得られた点群データに対して曲面上のある座標値（ｘ，ｙ，ｚ）があるパラメータの値によって一意に決定するよう、例えばベジェ曲面やＮＵＲＢＳ曲面等のパラメトリック曲面によりフィッティングを行う。これにより、形状を修正する必要が生じた際に、修正が行い易くなるという利点が考えられる。しかしながら、パラメトリック曲面のフィッティングでは、計測された部分に対するフィッティングは行えるが、計測されていない部分についての推定等ができないので複数地点からの計測が必要となってくる。この理由からも、上述した応用例１のマージングが必要となる。
【０１５６】
（応用例３：生成形状データベースへの登録と参照）
実務レベルでのデータ処理（形状生成）を行う際、これまでに挙げた幾つかの手法でセグメント化及び形状生成されたものが、そのまま最終形状とする場合と多少の手修正を加える場合とが起こり得る。形状生成の場合において、その修正したデータに関する情報を次回以降の自動生成を行う際の形状決定のための判断条件に加えることで、目的とする形状の生成効率を経験的に高めることが可能となる。そこで、形状に関する情報等を生成形状データベースに登録し、次に自動生成を行う際にそのデータベースを参照し、形状判断の条件に逐次加える事で、自動生成の効率を高めていく手法である。
【０１５７】
なお、上述した実施例では、３種類の曲面形状の曲面部分を生成する例について説明したが、それ以外の形状の特徴をパラメータや他の設定条件等をデータベースに登録し、必要に応じて参照することでより高精度に三次元形状の判定を行うことができる。
【０１５８】
上述したように本発明によれば、点群データにないオクルージョン部分が、単純な幾何形状で構成されている場合が多いことを利用し、近傍の可視部分の形状、色、対象物の種類等の補足情報から類推してオクルージョン部分のエッジや面を正確に生成することで高精度な三次元形状データを生成する。これにより、従来の三次元モデリング手法と比較して三次元形状データの生成を飛躍的に高効率化することができる。また、三次元形状データの生成に関して大幅なコストダウンを可能にする。
【０１５９】
なお、レーザースキャニングによる点群データだけでは、計測時間や計測対象物の大きさ・素材等の問題で、形状取得に不十分な点もある。そこで、ステレオ画像、動画像等を併用する方法も有効である。複数画像を用いる場合、その処理結果は計測時の光学的環境による影響が大きく、均一な環境光下においては、高精度な処理結果を得ることが可能となる。
【０１６０】
また、本発明において生成した三次元形状を用いれば、以下に示すような効果がある。
【０１６１】
自動車プラントの分野においては、ますます激化する国内外の競争の中、よりスピーディな新車の開発が必要となり、工場の生産ラインの迅速な変更を行うために正確な三次元データが必要とされている。ところが、従来の工場の施工においては現場合わせが多く、図面も完全に保管されなかった等の理由により、三次元化がほとんど行われていないのが現状である。現在、レーザースキャニングの実用検討が行われているが、面とエッジを備えた正確な三次元形状データを自動生成する技術は極めて重要である。今後、レーザースキャニングによる自動車プラントの三次元化の業務急速に増加することが確実である。
【０１６２】
自動車以外の分野では、原子力、化学等の各種プラントにおいても同様のニーズが存在し、今後の増加が予想される。
【０１６３】
また、文化財建造物においては保存修復等の際に現状の形状をデジタル化することが重要であり、従来の写真測量等に代わる技術としてレーザースキャニングが注目され、実験的に行われ始めている。本発明により面及びエッジを備えた正確な三次元形状データを自動生成することが可能になれば、特に古建築のデジタル化における利用が普及することとなる。
【０１６４】
また、測量業務としての利用や次世代カーナビでの利用等、多種の分野においての利用が実現できる。
【０１６５】
以上本発明の好ましい実施例について詳述したが、本発明は係る特定の実施形態に限定されるものではなく、特許請求の範囲に記載された本発明の要旨の範囲内において、種々の変形、変更が可能である。
【０１６６】
【発明の効果】
本発明によれば、点群データから高精度な三次元形状データを生成するこができる。
【図面の簡単な説明】
【図１】本発明における三次元形状自動生成装置の一構成例を示す図である。
【図２】本発明における三次元データ自動生成手順の概略を示す一例のフローチャートである。
【図３】Ｓ０１ステップ実行後の結果の一例を示す図である。
【図４】Ｓ０２のステップにおける動作を説明するための一例の図である。
【図５】矩形の検索内容の一例を示す図である。
【図６】曲面形状の一例を示す図である。
【図７】本発明おけるセグメンテーションプロセスの一例を示すフローチャートである。
【図８】本発明における形状判別・自動生成プロセスの一例を示すフローチャートである。
【図９】本発明における三次元形状自動生成が実現可能なハードウェア構成の一例を示す図である。
【図１０】本発明における三次元形状データの自動生成に用いられる計測対象物の一例を示す図である。
【図１１】異なる閾値に基づくセグメンテーション結果の一例を示す図である。
【図１２】異なる機器で計測して点群データを用いたセグメンテーション結果の一例を示す図である。
【図１３】広範囲を計測した場合のセグメンテーション結果の一例を示す図である。
【図１４】本発明における異なる閾値による形状判別・自動生成結果の一例を示す図である。
【図１５】レンジ誤差による自動生成不具合の一例を示す図である。
【符号の説明】
１  三次元形状自動生成装置
２  点群データ入力部
３  セグメンテーション部
４  形状生成部
５  記憶部
６  出力部
１０  主制御部
２０  記憶装置
２１  点群データ
２２  閾値データ
２３  関数データ
３０  入出力制御部
４０  入力装置
５０  表示装置
６０  出力装置
【図１】
2004272459.tif 000015
【図２】
2004272459.tif 000016
【図３】
2004272459.tif 000017
【図４】
2004272459.tif 000018
【図５】
2004272459.tif 000019
【図６】
2004272459.tif 000020
【図７】
2004272459.tif 000021
【図８】
2004272459.tif 000022
【図９】
2004272459.tif 000023
【図１０】
2004272459.tif 000024
【図１１】
2004272459.tif 000025
【図１２】
2004272459.tif 000026
【図１３】
2004272459.tif 000027
【図１４】
2004272459.tif 000028
【図１５】
2004272459.tif 000029