(57)【特許請求の範囲】
【請求項１】
測定対象に対して異なる計測ポイントにおいて取得される複数のレンジデータの位置合わせ処理を実行する三次元データ処理装置であり、
前記測定対象に対して異なる計測ポイントにおいて計測されたレンジデータおよびテクスチャデータの複数の組データを入力するデータ入力手段と、
前記データ入力手段に入力されたデータ中、重なり領域を持つ２つの組データの対応点を、該２つの組データ中の２つのテクスチャデータの重なり領域における相関に基づいて設定する対応点探索手段と、
前記対応点探索手段において設定された対応点に基づいて、前記２つの組データ中の２つのレンジデータの重なり領域における誤差を最小にする２つのレンジデータの相対位置を設定するための一方のレンジデータの移動量を求める移動量算出手段と、
を有することを特徴とする三次元データ処理装置。
【請求項２】
前記対応点探索手段は、
前記重なり領域を持つ２つの組データに含まれる２つのレンジデータについて、一方のレンジデータを他のレンジデータに対して複数の異なる相対位置に移動させる微少移動手段と、
前記複数の異なる相対位置の各々の位置に応じて、２つのレンジデータ間の対応点を設定する対応点算出手段と、
前記対応点算出手段において設定された対応点に基づいて定まる２つの組データの重なり領域における２つのテクスチャデータの相関を算出するテクスチャ相関算出手段と、
前記テクスチャ相関算出手段が算出した最も高い相関を示す２つのテクスチャデータの組に対する２つのレンジデータ対応点を出力対応点として出力する対応点出力手段と、
を有することを特徴とする請求項１に記載の三次元データ処理装置。
【請求項３】
前記対応点探索手段は、
重なり領域を持つ２つのテクスチャデータの相関を算出するテクスチャ相関算出手段を有し、
該テクスチャ相関手段の算出する相関は、２つのレンジデータの輝度値、または色値のいずれかに基づくものであることを特徴とする請求項１に記載の三次元データ処理装置。
【請求項４】
前記移動量算出手段により求める移動量は、一方のレンジデータの移動量を示す回転行列Ｒと、並進ベクトルｔの組として算出する構成であることを特徴とする請求項１に記載の三次元データ処理装置。
【請求項５】
前記移動量算出手段は、３以上の複数のレンジデータを入力し、すべての重なり合うレンジデータにおける誤差を同時に少なくなるように、各レンジ間の移動量を求める構成を有することを特徴とする請求項１に記載の三次元データ処理装置。
【請求項６】
測定対象に対して異なる計測ポイントにおいて取得される複数のレンジデータの位置合わせ処理を実行する三次元データ処理方法であり、
前記測定対象に対して異なる計測ポイントにおいて計測されたレンジデータおよびテクスチャデータの複数の組データを入力するデータ入力ステップと、
前記データ入力ステップにおいて入力されたデータ中、重なり領域を持つ２つの組データの対応点を、該２つの組データ中の２つのテクスチャデータの重なり領域における相関に基づいて設定する対応点探索ステップと、
前記対応点探索ステップにおいて設定された対応点に基づいて、前記２つの組データ中の２つのレンジデータの重なり領域における誤差を最小にする２つのレンジデータの相対位置を設定するための一方のレンジデータの移動量を求める移動量算出ステップと、
を有することを特徴とする三次元データ処理方法。
【請求項７】
前記対応点探索ステップは、
前記重なり領域を持つ２つの組データに含まれる２つのレンジデータについて、一方のレンジデータを他のレンジデータに対して複数の異なる相対位置に移動させる微少移動ステップと、
前記複数の異なる相対位置の各々の位置に応じて、２つのレンジデータ間の対応点を設定する対応点算出ステップと、
前記対応点算出ステップにおいて設定された対応点に基づいて定まる２つの組データの重なり領域における２つのテクスチャデータの相関を算出するテクスチャ相関算出ステップと、
前記テクスチャ相関算出ステップにおいて算出した最も高い相関を示す２つのテクスチャデータの組に対する２つのレンジデータ対応点を出力対応点として出力する対応点出力ステップと、
を含むことを特徴とする請求項６に記載の三次元データ処理方法。
【請求項８】
前記対応点探索ステップは、
重なり領域を持つ２つのテクスチャデータの相関を算出するテクスチャ相関算出ステップを有し、
該テクスチャ相関ステップにおいて算出する相関は、２つのレンジデータの輝度値、または色値に基づくものであることを特徴とする請求項６に記載の三次元データ処理方法。
【請求項９】
前記移動量算出ステップにおいて求められる移動量は、一方のレンジデータの移動量を示す回転行列Ｒと、並進ベクトルｔの組として算出することを特徴とする請求項６に記載の三次元データ処理方法。
【請求項１０】
前記移動量算出ステップは、３以上の複数のレンジデータを入力し、すべての重なり合うレンジデータにおける誤差を同時に少なくなるように、各レンジ間の移動量を求めるステップであることを特徴とする請求項６に記載の三次元データ処理方法。
【請求項１１】
測定対象に対して異なる計測ポイントにおいて取得される複数のレンジデータの位置合わせ処理をコンピュータ・システム上で実行せしめるコンピュータ・プログラムを提供するプログラム提供媒体であって、前記コンピュータ・プログラムは、
前記測定対象に対して異なる計測ポイントにおいて計測されたレンジデータおよびテクスチャデータの複数の組データを入力するデータ入力ステップと、
前記データ入力ステップにおいて入力されたデータ中、重なり領域を持つ２つの組データの対応点を該２つの組データ中の２つのテクスチャデータの重なり領域における相関に基づいて設定する対応点探索ステップと、
前記対応点探索ステップにおいて設定された対応点に基づいて、前記２つの組データ中の２つのレンジデータの重なり領域における誤差を最小にする２つのレンジデータの相対位置を設定するための一方のレンジデータの移動量を求める移動量算出ステップと、
を有することを特徴とするプログラム提供媒体。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、物体の三次元形状を求める三次元データ処理装置および三次元データ処理方法、並びにプログラム提供媒体に関する。特にある視点から被写体を観察して視点からの距離データを求め、異なる複数視点からの複数の距離データを合成して被写体全体の三次元形状を算出する三次元形状を求める三次元データ処理装置および三次元データ処理方法、並びにプログラム提供媒体に関する。
【０００２】
【従来の技術】
物体の三次元形状を取得する手法にはいくつかの方法がある。三次元形状計測方法は大きく分けると、アクティブ手法（Active vision）とパッシブ手法（Passive vision）とに分類される。アクティブ手法は、さらに、レーザ光や超音波等を発して、対象物からの反射光量や到達時間を計測し、奥行き情報を抽出するレーザー手法、スリット光などの特殊なパターン光源を用いて、対象表面パターンの幾何学的変形等の画像情報より対象形状を推定するパターン投影方法、光学的処理によってモアレ縞により等高線を形成させて、３次元情報を得る方法などに分類される。一方、パッシブ手法は、一枚の画像から３次元情報を推定する単眼立体視、三角測量原理で各画素の奥行き情報を推定するステレオ法等に分類される。
【０００３】
上述のレーザー手法、あるいはステレオ法を適用して得られる計測対象の距離情報は、計測対象の表面形状を表すデータであり、レンジデータと呼ばれる。レンジデータはレーザー手法、あるいはステレオ法等を適用して得られる計測ポイントの距離データ・サンプル点の集合データである。
【０００４】
また、計測対象の表面の色彩等、肉眼で観察したと同様の撮影データをテクスチャデータと呼ぶ。レンジデータとテクスチャデータとを対応付ける処理をテクスチャマッピングといい、テクスチャマッピングにより、測定対象の三次元モデルが生成される。
【０００５】
【発明が解決しようとする課題】
しかし、一般にレンジデータは、１回の測定で測定点として設定した一方向からの測定対象のレンジデータが求められるのみであり、物体全体の三次元形状を求める場合は、複数の測定点からのレンジデータを測定位置ごとに位置合わせて合成する処理が必要になる。これはテクスチャデータについても同様である。
【０００６】
複数のレンジデータの合成には、例えば、測定対象を回転テーブルの上に設置し、撮影方向と回転テーブルの回転角度を対応付けて複数のレンジデータを取得して、回転テーブルの回転角度に基づいて複数のレンジデータ、または複数のテクスチャデータの合成を行なうことが可能であるが、回転テーブルに設置することができない大きな物体、例えば家、建物、仏像、あるいは自然界に存在する地形等については、このような手法での複数のレンジデータの合成処理は、困難である。
【０００７】
複数のレンジデータの各々は、それぞれ他のレンジデータと一部重なりを持つように測定領域が設定され、それぞれのレンジデータの重なり領域における距離データの相関を算出して相関の高い位置を複数のレンジデータの合成位置として求める処理を実行するのが一般的であった。図１にレンジデータの相関によるレンジデータの合成処理例を示す。
【０００８】
図１（ａ）に示す測定対象１０１に対し、２つのレンジデータ測定器１０２，１０３の２つの測定点からのレンジデータの位置合わせ合成を行なう場合を想定する。レンジデータ測定器１０２，１０３から取得されたレンジデータは、図１（ｂ）のように示される。ここでは説明を簡易にするためにレンジデータをある平面で切ったＸ軸上に延びる線状のデータとして示している。このとき、一方のレンジデータを固定し、他方のレンジデータをＸ軸上で移動させて、２つのレンジデータの重なり領域における相関の最も高いポイントを求めて、２つのレンジデータの位置合わせ処理を実行する。図１に示すように測定対象の表面の形状が特徴的、すなわち凹凸がある場合には、隣接する異なるレンジデータの重なり領域をレンジデータの相関から求めることは比較的容易である。
【０００９】
異なるレンジデータの重なり領域における位置合わせのアルゴリズムは、例えば以下の式を最小にするレンジデータの対応位置を求める処理によって行われる。
【００１０】
【数１】
0004608152.tif 000002
【００１１】
上記式において、ｘ（ｉ）、ｙ（ｉ）は、レンジデータｘ、レンジデータｙのそれぞれのサンプル点（ｉ）の距離データ値であり、Ｒは回転行列、ｔは並進ベクトルである。上記式を最小にする処理は、一方のレンジデータを固定し、他方のレンジデータの移動量Ｒ，ｔを変化させる処理によって実行される。すなわち、上記式の最小値をとる移動量Ｒ，ｔを算出する処理として実行される。
【００１２】
レンジデータの位置合わせ処理の多くは、「Ｐ．Ｊ．Ｂｅｓｌ」が考案したアルゴリズムを基本とする（例えば、P.J.Besl,N.D.Mckey：A method of Registration of ３-D Shapes. IEEETrans. Pattern Analysis and Machine Intelligence Vol.14,No.2 pp239-256,1992）。この応用例として「Ｚ．Ｚｈａｎｇ」によって構成された例（Z.Zhang: Iterative Point Matching for Registration of Free-Form Curves and Surface. International Journal of Computer Vision,Vol.13, No.2, pp.119-152,1994）がある。この基本アルゴリズムは、ＩＣＰ（Iterative Closest Point）と呼ばれる。ＩＣＰでは重なり合うレンジデータ間の一番近い点同士を対応点とし、繰り返し上記式のεを最小にするように移動量Ｒ，ｔを求めることでレンジデータ間の位置合わせをを行なう。ただし、この方法は、重なり領域を持つレンジタデータ間でのみ適用可能であり、対応点を単純に近い点としているために、形状に特徴がない場合に誤対応が発生しやすいという欠点がある。
【００１３】
また、上記方法は、隣合う２つのレンジデータ間でのみ位置合わせを行なうものであり、３以上のレンジデータを順次位置合わせ処理を行なっていくと、位置合わせ誤差が順次伝播し、終端に誤差の蓄積が発生するという問題がある。物体を複数の方向からスキャンし、全体のレンジデータを撮影（測定）し、位置合わせを順次行なうと誤差が蓄積し、最悪の場合、データが閉じないことも発生し得る。
【００１４】
このような欠点を除去する方法として、複数のレンジデータを一度に位置合わせする方法の検討がなされている。代表的な手法には、「Ｎｅｕｇｅｂａｕｔｅｒ」の方法（Peter J.Neugebauter: Reconstruction of Real-World Objects Via Simultaneous Registration and Robust Combination of Multiple Range Images. International Journal of Shape Modeling, Vol/3 No.１＆２,pp７１-９０,June 1997）がある。この方法では、すべての重なり合うレンジデータにおける誤差を同時に少なくなるように、各レンジ間の移動量Ｒ，ｔを求めている。対応点は、あるレンジデータ上の点を通る撮影方向に平行な直線が、もう１つのレンジデータと交差した点を対応点としている。ただし、この方法もレンジデータから得られる表面形状の特徴のみを使用してレンジデータ相互の位置合わせを行なっている。そのため、例えば缶のような表面が均一な態様を持ち、表面形状に基づく位置合わせが難しい物体を測定対象とした場合には、複数のレンジデータ間の位置合わせは困難となる。
【００１５】
例えば、図２に示すような測定対象２０１に対して異なる測定ポイントからレンジデータを取得し、レンジデータの位置合わせ処理を相互のレンジデータから取得される距離情報（表面形状）の相関に基づいて実行しようとしても、図２（ｂ）に示すように、測定対象物表面に特徴的な凹凸が存在せず、一方のレンジデータを移動しても相関値の変化が殆ど発生しない。従って、レンジデータ相互の重なり領域の位置合わせをレンジデータの相関に基づいて実行することが難しく、測定対象物の全体の正確な表面形状の算出が困難となる。
【００１６】
上述のようなレンジデータのみの位置合わせ処理の困難性を補う手法として全周位置合わせを行なう際に、テクスチャの色の境界面を使用する方法も提案されている（石川知幸、大槻正樹、佐藤幸男：色の境界部分を用いた複数レンジデータの統合、コンピュータビジョンとイメージメディア１１０−１１，１９９８，３，１９）この方法では、物体表面に明確な色の違い（境界）がある場合に、その境界をてがかりとして対応点の補正を行なう。しかし、測定対象物に明確な色の境界が存在しない場合は、本方法は適用できない。
【００１７】
本発明は、上述の従来技術の問題点に鑑みてなされたものであり、レンジデータの相関からの位置合わせ処理が困難な測定対象であっても、正確にレンジデータの位置合わせ処理を実行することを可能とした三次元データ処理装置および三次元データ処理方法、並びにプログラム提供媒体を提供することを目的とする。
【００１８】
具体的には、異なる視点からのレンジデータとテクスチャデータの複数組を生成し、重なり領域を持つレンジデータの相対移動処理を実行し、微少移動された位置において、レンジデータ相互の対応点を算出し、算出した対応点に基づいて、テクスチャデータを用いたテクスチャの相関を計算する。レンジデータの微少移動、対応点算出、算出した対応点位置におけるテクスチャデータの相関値計算を繰り返し、最も高いテクスチャ相関を持つものを対応点として出力し、出力した対応点に基づいてレンジデータの移動量を算出する構成により、表面形状に特徴のない物体においても正確な位置合わせを可能とした三次元データ処理装置および三次元データ処理方法、並びにプログラム提供媒体を提供する。
【００１９】
【課題を解決するための手段】
本発明は、上記課題を参酌してなされたものであり、その第１の側面は、
測定対象に対して異なる計測ポイントにおいて取得される複数のレンジデータの位置合わせ処理を実行する三次元データ処理装置であり、
前記測定対象に対して異なる計測ポイントにおいて計測されたレンジデータおよびテクスチャデータの複数の組データを入力するデータ入力手段と、
前記データ入力手段に入力されたデータ中、重なり領域を持つ２つの組データの対応点を該２つの組データ中の２つのテクスチャデータの重なり領域における相関に基づいて設定する対応点探索手段と、
前記対応点探索手段において設定された対応点に基づいて、前記２つの組データ中の２つのレンジデータの重なり領域における誤差を最小にする２つのレンジデータの相対位置を設定するための一方のレンジデータの移動量を求める移動量算出手段と、
を有することを特徴とする三次元データ処理装置にある。
【００２０】
さらに、本発明の三次元データ処理装置の一実施態様において、前記対応点探索手段は、前記重なり領域を持つ２つの組データに含まれる２つのレンジデータについて、一方のレンジデータを他のレンジデータに対して複数の異なる相対位置に移動させる微少移動手段と、前記複数の異なる相対位置の各々の位置に応じて、２つのレンジデータ間の対応点を設定する対応点算出手段と、前記対応点算出手段において設定された対応点に基づいて定まる２つの組データの重なり領域における２つのテクスチャデータの相関を算出するテクスチャ相関算出手段と、前記テクスチャ相関算出手段が算出した最も高い相関を示す２つのテクスチャデータの組に対する２つのレンジデータ対応点を出力対応点として出力する対応点出力手段とを有することを特徴とする。
【００２１】
さらに、本発明の三次元データ処理装置の一実施態様において、前記対応点探索手段は、重なり領域を持つ２つのテクスチャデータの相関を算出するテクスチャ相関算出手段を有し、該テクスチャ相関手段の算出する相関は、２つのレンジデータの輝度値、または色値のいずれかに基づくものであることを特徴とする。
【００２２】
さらに、本発明の三次元データ処理装置の一実施態様において、前記移動量算出手段により求める移動量は、一方のレンジデータの移動量を示す回転行列Ｒと、並進ベクトルｔの組として算出する構成であることを特徴とする。
【００２３】
さらに、本発明の三次元データ処理装置の一実施態様において、前記移動量算出手段は、３以上の複数のレンジデータを入力し、すべての重なり合うレンジデータにおける誤差を同時に少なくなるように、各レンジ間の移動量を求める構成を有することを特徴とする。
【００２４】
さらに、本発明の第２の側面は、
測定対象に対して異なる計測ポイントにおいて取得される複数のレンジデータの位置合わせ処理を実行する三次元データ処理方法であり、
前記測定対象に対して異なる計測ポイントにおいて計測されたレンジデータおよびテクスチャデータの複数の組データを入力するデータ入力ステップと、
前記データ入力ステップにおいて入力されたデータ中、重なり領域を持つ２つの組データの対応点を該２つの組データ中の２つのテクスチャデータの重なり領域における相関に基づいて設定する対応点探索ステップと、
前記対応点探索ステップにおいて設定された対応点に基づいて、前記２つの組データ中の２つのレンジデータの重なり領域における誤差を最小にする２つのレンジデータの相対位置を設定するための一方のレンジデータの移動量を求める移動量算出ステップと、
を有することを特徴とする三次元データ処理方法にある。
【００２５】
さらに、本発明の三次元データ処理方法の一実施態様において、前記対応点探索ステップは、前記重なり領域を持つ２つの組データに含まれる２つのレンジデータについて、一方のレンジデータを他のレンジデータに対して複数の異なる相対位置に移動させる微少移動ステップと、前記複数の異なる相対位置の各々の位置に応じて、２つのレンジデータ間の対応点を設定する対応点算出ステップと、前記対応点算出ステップにおいて設定された対応点に基づいて定まる２つの組データの重なり領域における２つのテクスチャデータの相関を算出するテクスチャ相関算出ステップと、前記テクスチャ相関算出ステップにおいて算出した最も高い相関を示す２つのテクスチャデータの組に対する２つのレンジデータ対応点を出力対応点として出力する対応点出力ステップとを含むことを特徴とする。
【００２６】
さらに、本発明の三次元データ処理方法の一実施態様において、前記対応点探索ステップは、重なり領域を持つ２つのテクスチャデータの相関を算出するテクスチャ相関算出ステップを有し、該テクスチャ相関ステップにおいて算出する相関は、２つのレンジデータの輝度値、または色値に基づくものであることを特徴とする。
【００２７】
さらに、本発明の三次元データ処理方法の一実施態様において、前記移動量算出ステップにおいて求められる移動量は、一方のレンジデータの移動量を示す回転行列Ｒと、並進ベクトルｔの組として算出することを特徴とする。
【００２８】
さらに、本発明の三次元データ処理方法の一実施態様において、前記移動量算出ステップは、３以上の複数のレンジデータを入力し、すべての重なり合うレンジデータにおける誤差を同時に少なくなるように、各レンジ間の移動量を求めるステップであることを特徴とする。
【００２９】
さらに、本発明の第３の側面は、
測定対象に対して異なる計測ポイントにおいて取得される複数のレンジデータの位置合わせ処理をコンピュータ・システム上で実行せしめるコンピュータ・プログラムを提供するプログラム提供媒体であって、前記コンピュータ・プログラムは、
前記測定対象に対して異なる計測ポイントにおいて計測されたレンジデータおよびテクスチャデータの複数の組データを入力するデータ入力ステップと、
前記データ入力ステップにおいて入力されたデータ中、重なり領域を持つ２つの組データの対応点を該２つの組データ中の２つのテクスチャデータの重なり領域における相関に基づいて設定する対応点探索ステップと、
前記対応点探索ステップにおいて設定された対応点に基づいて、前記２つの組データ中の２つのレンジデータの重なり領域における誤差を最小にする２つのレンジデータの相対位置を設定するための一方のレンジデータの移動量を求める移動量算出ステップと、
を有することを特徴とするプログラム提供媒体にある。
【００３０】
本発明の第３の側面に係るプログラム提供媒体は、例えば、様々なプログラム・コードを実行可能な汎用コンピュータ・システムに対して、コンピュータ・プログラムをコンピュータ可読な形式で提供する媒体である。媒体は、ＣＤやＦＤ、ＭＯなどの記憶媒体、あるいは、ネットワークなどの伝送媒体など、その形態は特に限定されない。
【００３１】
このようなプログラム提供媒体は、コンピュータ・システム上で所定のコンピュータ・プログラムの機能を実現するための、コンピュータ・プログラムと提供媒体との構造上又は機能上の協働的関係を定義したものである。換言すれば、該提供媒体を介してコンピュータ・プログラムをコンピュータ・システムにインストールすることによって、コンピュータ・システム上では協働的作用が発揮され、本発明の他の側面と同様の作用効果を得ることができるのである。
【００３２】
本発明のさらに他の目的、特徴や利点は、後述する本発明の実施例や添付する図面に基づくより詳細な説明によって明らかになるであろう。
【００３３】
【発明の実施の形態】
以下、本発明の三次元データ処理装置および三次元データ処理方法の実施例について、図面を参照して説明する。まず、図３に本発明の三次元データ処理装置におけるレンジデータ相互の位置合わせ処理を実行するための構成を示すブロック図を示す。
【００３４】
レンジデータ入力部３０１およびテクスチャデータ入力部３０２は、測定対象物の各測定ポイントから取得したレンジデータとテクスチャデータを入力する。例えば図４に示す構成のように、測定対象物４０１に対してそれぞれ異なる視点から測定対象を観察する測定ポイント４０２Ａ〜４０２Ｚにおいて取得されるレンジデータとテクスチャデータを順次入力する。レンジデータは、前述したレーザー手法、あるいはステレオ法等の距離データ取得手法を適用して得られる計測対象の距離情報であり、テクスチャデータは、通常のカメラ等で取得される測定対象の表面の輝度、色情報等を含むデータである。
【００３５】
図４では、測定対象４０１に対して周囲を取り巻くように測定器（撮影手段）を設置してあるが、これは一例であり、測定対象物の一部のデータを取得したい場合は、測定対象物の一部のデータを取得するために必要な１以上の測定手段を設置する構成としてもよく、また、図４に示す測定ポイント以外に測定対象４０１に対して上方あるいは下方からレンジデータ、テクスチャデータを取得するポイントを設けてもよい。また、測定ポイントを多数設定する代わりに、測定対象を例えばテーブル等に載置してカメラに対して測定対象を相対的に移動する構成としてもよい。
【００３６】
なお、個々の測定ポイント４０２Ａ〜４０２Ｚでは、測定対象４０１のレンジデータおよびテクスチャデータを同一視点からのデータの組として取得され、１つの視点に属するレンジデータとテクスチャデータの組はそれぞれのデータ取得領域においてデータの対応付けがなされているものとする。また、測定対象４０１に対して設置される各測定ポイント４０２Ａ〜４０２Ｚから取得されるレンジデータおよびテクスチャデータは、それぞれ他のポイントからの測定データの少なくてもいずれかのデータとの重なり領域を有する。
【００３７】
図３に戻り、各構成部の機能について説明する。レンジデータ入力部３０１およびテクスチャデータ入力部３０２は、図４に示すような各測定ポイントにおいて取得したレンジデータおよびテクスチャデータを取り込むものであるが、実際の測定手段から直接、データを入力する構成に限らず、データを蓄積したハードディスク等の記憶手段を介してレンジデータ、テクスチャデータを取り込む構成としてもよい。
【００３８】
データ保持部３０３は、各測定ポイントにおいて取得されたレンジデータおよびテクスチャデータを格納するとともに、レンジデータの移動量Ｒ，ｔを保持する移動量保持部を各測定ポイント毎に有する。なお、レンジデータの移動量は、下記式に含まれる移動量としての回転行列Ｒ、並進ベクトルｔである。
【００３９】
【数２】
0004608152.tif 000003
【００４０】
上記式において、ｘ（ｉ）、ｙ（ｉ）は、レンジデータｘ、レンジデータｙのそれぞれのサンプル点（ｉ）の距離データ値であり、Ｒは回転行列、ｔは並進ベクトルである。位置合わせ処理は、上記式を最小にする処理、すなわち、上記式のεの最小値をとる移動量Ｒ，ｔを算出する処理として実行される。
【００４１】
例えば測定ポイントＡにおいて取得されたレンジデータは、レンジデータ保持部Ａ３０４に格納され、ポイントＡにおいて取得されたテクスチャデータは、テクスチャデータ保持部Ａ３０５に格納される。さらに、次に説明する対応点探索処理において求められたレンジデータＡの移動量Ｒ，ｔが移動量保持部Ａに格納される。各測定ポイントＢ〜Ｚについても同様にデータ保持部に設けられた各レンジデータ保持部Ｂ〜Ｚ、テクスチャデータ保持部Ｂ〜Ｚ、移動量保持部Ｂ〜Ｚに格納される。
【００４２】
対応点探索部３０８は、重なり領域を有する２つのデータ取得ポイントのレンジデータ、テクスチャデータ、例えば測定ポイントＡと測定ポイントＢの隣接ポイントのデータを入力して、重なり領域の位置合わせ処理を実行して対応点を求める処理を実行する。対応点探索部における処理については、図５を用いて後段で詳細に説明する。
【００４３】
移動量算出部３０９は、対応点探索部３０８において探索された重なり領域を持つ２つのレンジデータの対応点に基づいて前記式［数２］を計算し、［数２］のεを最小にするよう、一方のレンジデータの移動量を求める。移動量は前記式［数２］の移動量Ｒ，ｔである。例えばレンジデータＡと、レンジデータＢに基づいて、レンジデータＡを固定し、レンジデータＢを移動させて前記式［数２］の値を最小にするＲ，ｔを求めた場合には、移動量保持部Ｂにその求めた移動量Ｒ，ｔが格納される。
【００４４】
対応点探索部３０８においては位置合わせを実行する重なり領域を持つ２つのデータを入力して対応点がそれぞれ求められ、移動量算出部３０９は、それぞれの１組のデータに基づいて前記式［数２］に従ってεを最小にする移動量Ｒ，ｔを求める処理を実行する。移動量算出部３０９は、１組の２つのレンジデータ毎に移動量算出を実行する構成としてもよく、また、３以上のレンジデータを入力して重なり領域を持つレンジデータの組［Ａ，Ｂ］、［Ｂ，Ｃ］それぞれの前記式［数２］のε［Ａ，Ｂ］、ε［Ｂ，Ｃ］…を求めて、例えば「Ｎｅｕｇｅｂａｕｔｅｒ」の方法（Peter J.Neugebauter: Reconstruction of Real-World Objects Via Simultaneous Registration and Robust Combination of Multiple Range Images. International Journal of Shape Modeling, Vol/3 No.１＆２,pp７１-９０,June 1997）を適用して、すべての重なり合うレンジデータにおける誤差を同時に少なくなるように、各レンジ間の移動量Ｒ，ｔを求める構成としてもよい。
【００４５】
移動量出力部３０７は、移動量算出部３０９で求めた値を保持している移動量保持部Ａ〜Ｚの値を出力する。出力された移動量に基づいてレンジデータの位置が決定され、例えば測定対象全周囲の距離データが構成されて、テクスチャデータを貼り付けることにより、測定対象の三次元画像が生成される。
【００４６】
図５に対応点探索部の詳細構成を示す。図５の対応点探索部５０５には、２つの異なる測定ポイントから取得された重なり領域を持つ２つのレンジデータ、テクスチャデータが入力される。ここでは、入力データをレンジデータ保持部ｉ，５０１に格納されたレンジデータｉ、テクスチャデータ保持部ｉ，５０２に格納されたテクスチャデータｉ、レンジデータ保持部ｉ＋１，５０３に格納されたレンジデータｉ＋１、テクスチャデータ保持部ｉ＋１，５０４に格納されたテクスチャデータｉ＋１とする。
【００４７】
レンジデータ保持部ｉ，５０１に格納されたレンジデータｉと、レンジデータ保持部ｉ＋１，５０３に格納されたレンジデータｉ＋１に格納されたレンジデータは、対応点探索部５０５の微少移動部５０８に入力される。重なり領域を持つレンジデータは、その測定ポイント位置からおおよその相対位置関係が初期設定され、その初期設定位置から、微少移動部５０８において、あらかじめ定めた複数の移動バリエーションに応じてレンジデータの相対移動処理が実行される。微少移動されたポイントにおいて、対応点算出部５０７においてレンジデータ相互の対応点が算出され、設定した対応点に基づいて、同様の対応付けを行なったテクスチャデータを用いた相関がテクスチャ相関算出部５０６において計算される。テクスチャ相関算出部５０６において計算された相関は相関値保持部５０９に保持され、その相関値に対応する対応点が対応点保持部５１０に保持される。
【００４８】
微少移動部５０８における微少移動、対応点算出部５０７対応点算出処理、テクスチャ相関算出部５０６におけるテクスチャデータの相関値計算が、微少移動部５０８において実行される複数の移動バリエーションに従った様々な微少移動毎に繰り返し実行され、異なる対応点に基づいて計算されたテクスチャ相関値のうち、最も高い相関を持つものが対応点出力部５１１から出力される。
【００４９】
上記処理の詳細について、さらに、図６を用いて説明する。図６を用いて、重なり領域を持つ隣接する測定ポイントＸ，Ｙから取得された２つのレンジデータＸ，Ｙ、テクスチャデータＸ，Ｙを用いた対応点設定処理を説明する。レンジデータＸ，Ｙは、サンプル点Ｘｉ，Ｙｉの集合である。また、隣接サンプル点を結ぶことにより設定される三角メッシュの集合としてとらえることもできる。レンジデータＸにはテクスチャデータＸが対応付けられ、レンジデータＹにはテクスチャデータＹが対応付けられている。。
【００５０】
まず、レンジデータＸとレンジデータＹが微少移動部５０８に入力されると、予め定められた移動バリエーションに従って、レンジデータＹを微少移動させる。図６の例では、撮影視点（測定点）に垂直方向に一定距離レンジデータＹを移動させる処理が１つの移動バリエーションとして実行されるものとする。図６の位置において１つの移動バリエーションに基づくレンジデータＸ，Ｙの相対位置が設定されたものとする。
【００５１】
次に、対応点算出部５０７は、レンジデータＸのサンプルポイントＸｉと撮影視点（測定点）とを結ぶ線をレンジデータＹに伸ばした線との交点をＹｉ’として、このＸｉとＹｉ’を、この移動バリエーション位置における対応点として設定する。設定された対応点の位置は、対応点保持部５１０に保持される。
【００５２】
テクスチャ相関算出部５０６は、この位置におけるテクスチャデータＸとテクスチャデータＹ’との重なり領域における相関を算出する。テクスチャデータは、例えばそのＲＧＢ等の色値、あるいは輝度値を各座標位置において算出し、テクスチャデータＸの各座標（ｉ）における輝度値あるいはＲＧＢ等の色値をｘ（ｉ）とし、テクスチャデータＹ’の各座標（ｉ）における輝度値あるいはＲＧＢ等の色値をｙ’（ｉ）とし、この相関を次式によって求める。
【００５３】
【数３】
0004608152.tif 000004
【００５４】
上記式において、テクスチャデータＸと、テクスチャデータＹ’の相関が高ければＲ＝１に近づき、相関がなければｒ＝０、逆の相関が大きくなるとｒ＝−１に近づく。上記式において求められた相関値ｒは、相関値保持部５０９に保持される。
【００５５】
異なる移動バリエーションによって新たに対応点ｙ”、ｙ”’、ｙ””…が設定されそれぞれの対応点位置が対応点保持部５１０に格納されるとともに、テクスチャ相関算出部において上記式に従って相関が算出され、算出された相関が相関値保持部５０９に保持される。対応点保持部５１０に格納される対応点と、相関値保持部５０９に保持される相関値とはそれぞれ対応付けされている。
【００５６】
予め定めた移動バリエーションに基づく複数の移動処理が終了し、全ての対応点と相関値算出処理が終了すると、算出された相関値の中でもっとも高い相関値が算出された対応点位置を対応点出力部５１１から出力する。
【００５７】
対応点出力部から出力されるテクスチャデータの相関に基づいて設定された対応点情報は、図３の移動量算出部３０９に出力され、移動量算出部３０９は、設定された対応点に基づいて、レンジデータＸ，Ｙについて前記式［数２］に従ってεを最小にする移動量Ｒ，ｔを求める処理を実行する。εを最小にする移動量Ｒ，ｔが求められると、その移動量データをレンジデータＹの移動量保持部Ｙに格納する（レンジデータＸを固定し、レンジデータンを移動させた場合）。このようにして決定された移動量に基づいて複数のレンジデータの相対位置が決定され、例えば測定対象全周囲の距離データが構成されて、テクスチャデータを貼り付けることにより、測定対象の三次元画像が生成される。
【００５８】
次に、図７、図８を用いて本発明の三次元データ処理方法において実行されるテクスチャデータに基づく対応点設定を伴う移動量設定処理の各ステップについて説明する。
【００５９】
まず、ステップＳ１０１において、レンジデータ（ｉ）を入力し、レンジデータ保持部（ｉ）に格納し、ステップＳ１０２において、テクスチャデータ（ｉ）を入力し、テクスチャデータ保持部（ｉ）に格納する。ただし、ｉ＝１〜ｎとする。ｎは測定ポイント数に対応する。このデータ入力処理をすべての測定点数ｎまで繰り返し実行する（Ｓ１０３）。
【００６０】
すべてのレンジデータ、テクスチャデータの入力が終了すると、ステップＳ１０４以下の処理を実行する。以下のフローでは測定点ｉ，ｉ＋１の２つの隣接データ（ｉ）とデータ（ｉ＋１）の処理を実行する。ステップＳ１０４は、微少移動部５０８の処理であり、レンジデータ（ｉ＋１）を予め定めた複数の移動バリエーション（平行移動、回転移動等）の１つに従って微少移動させる。
【００６１】
ステップＳ１０５は、対応点算出部５０７の処理であり、レンジデータ（ｉ）と、移動処理後のレンジデータ（ｉ＋１）のサンプル点対応付けを行なう。この処理は例えば先に図６を用いて説明した処理である。ステップＳ１０６は、対応点保持部５１０において、対応点算出部５０７で対応付けた対応点を保存する処理である。
【００６２】
ステップＳ１０７は、テクスチャ相関算出部５０６の処理であり、対応算出部５０７で対応付けた対応点をもとに、重なり領域のテクスチャ相関を求める。これは例えば上記式［数３］に基づく処理として実行される。ステップＳ１０８は、相関値保持部５０９において、テクスチャ相関算出部５０６で算出した相関値を保持する処理である。
【００６３】
設定バリエーションの移動をすべて終了したか否かをステップＳ１０９で判定し、終了していない場合は、ステップＳ１０４〜Ｓ１０８の処理を繰り返し実行する。すべての設定バリエーションの移動をすべて終了すると、ステップＳ１１０に進む。
【００６４】
ステップＳ１１０は、対応点出力部５１１において、相関値保持部の値のうち最も相関の高い値を選択し、その位置における対応点を対応点保持部５１０から選択し出力する。
【００６５】
次のステップＳ１１１は、移動量算出部３０９（図３参照）の処理であり、対応点探索部において求められ出力された対応点をもとに各レンジデータの移動量を求め、移動量を移動量保持部に保存する。移動量は、前記式［数２］のＲ，ｔである。
【００６６】
次のステップＳ１１２，Ｓ１１３は、ステップＳ１１１で求められる移動量Ｒ，ｔに基づいて算出されるεを予め定めた閾値と比較するステップである。算出されたεが閾値より小さければ、正しい対応点位置に基づく移動量が算出されたと判断し、ステップＳ１１４に進む。一方、ステップＳ１１１で求められる移動量Ｒ，ｔに基づいて算出されるεが予め定めた閾値より小さくない場合は、誤った対応点位置に基づく移動量が算出されたと判定し、ステップＳ１１３で新たな移動バリエーションを設定して、新たな移動バリエーションに基づいてステップＳ１０４以下の処理を繰り返す。
【００６７】
ステップＳ１１４は、全ての重なり領域を持つレンジデータ相互の移動量が決定されたか否かを判定し、未処理データがある場合は、ステップＳ１０４に戻り、新たな重なり領域を持つデータの組を設定し処理を実行する。
【００６８】
全てのデータについての処理が終了すると、ステップＳ１１５において、移動量保持部に保持された移動量が移動量出力部３０７から出力される。出力された移動量に基づいて複数のレンジデータの相対位置が決定され、例えば測定対象全周囲の距離データが構成されて、テクスチャデータを貼り付けることにより、測定対象の三次元画像が生成される。
【００６９】
次に、図９を用いて、本発明の三次元データ処理装置のハードウェア構成について説明する。各種処理プログラムを実行する中央演算処理装置（ＣＰＵ:Central Processing Unit）６０１は、図９の各構成部位の処理を制御する。ＲＯＭ（Read only Memory）６０２は、ＩＰＬ（Initial Program Loading）等のプログラムを記憶したメモリである。ＲＡＭ（Random Access Memory）６０３は、ＣＰＵ６０１が実行するプログラム、ＣＰＵによって実行する処理におけるワークエリアとして使用される。
【００７０】
ビデオコントローラ６０４は、ＣＰＵ６０１の制御の下、ＶＲＡＭ（Video RAM）６０５を用いてモニタである画像表示部６０６の表示制御を行なう。ＶＲＡＭ６０５は、画像表示部６０６が表示するデータ、例えばレンジデータにテクスチャデータを貼り付けた三次元モデルデータ等を一次記憶する。すなわち、表示データは、ビデオコントローラ６０４を介してＶＲＡＭ６０５に一旦書き込まれ、ビデオコントローラ６０４がＶＲＡＭ６０５に格納されたデータを画像表示部６０６に供給することで画像表示が実行される。
【００７１】
ストレージコントローラ６０７は、例えばＨＤ（Hard Disk）や、ＦＤ（Floppy Disk）等の磁気ディスク６０８、ミニディスク等の光磁気ディスク６０９、ＣＤ−ＲＯＭ（Compact Disk ROM）などの光ディスク６１０、ＲＯＭやフラッシュメモリなどの不揮発性メモリ６１１に対するアクセスを制御する機能を持つ。磁気ディスク６０８、光磁気ディスク６０９、光ディスク６１０、不揮発性メモリ６１１はデータ、例えば上述のレンジデータ、テクスチャデータ、あるいはレンジデータにテクスチャデータを貼り付けた三次元データ等の各種データ等を記憶する。記憶データは、ＣＰＵ６０１によってストレージコントローラ６０７を介して読み出される。なお、各種記憶媒体にＣＰＵ６０１が実行するプログラムを格納する構成としてもよい。例えば、対応点探索、相関算出処理等、図７、図８のフロー中の各種の処理プログラムを磁気ディスク等の記憶媒体に格納可能である。
【００７２】
通信コントローラ６１２は、電波や赤外線などによる無線通信、イーサネットなどによる優先通信を制御するようになされている。レンジデータやテクスチャデータの各種測定データ、さらにＣＰＵ６０１が実行する各種処理プログラムを、この通信コントローラ６１２を介して通信を行なうことにより、外部装置から取得する構成とすることも可能である。
【００７３】
入力デバイスコントローラ６１３は、キーボード６１４や、例えばマウス等のポインティングデバイス６１５などの制御を実行し、各入力デバイスからのコマンド、データ入力をＣＰＵ６０１に出力する。
【００７４】
以上、特定の実施例を参照しながら、本発明について詳解してきた。しかしながら、本発明の要旨を逸脱しない範囲で当業者が該実施例の修正や代用を成し得ることは自明である。すなわち、例示という形態で本発明を開示してきたのであり、限定的に解釈されるべきではない。また、上述の実施例を適宜組み合わせて構成したものも、本発明の範囲に含まれるものであり、本発明の要旨を判断するためには、冒頭に記載した特許請求の範囲の欄を参酌すべきである。
【００７５】
【発明の効果】
以上、詳記したように、本発明の三次元データ処理装置および三次元データ処理方法によれば、レンジデータの相関に基づく位置合わせ処理が困難な測定対象であっても、テクスチャデータに基づいて対応点が高精度に設定されるので、表面形状に特徴のない物体におけるレンジデータの位置合わせが正確に実行され、高精度な三次元モデルの生成が可能となる。
【００７６】
また、本発明の三次元データ処理装置および三次元データ処理方法によれば、異なる視点からのレンジデータとテクスチャデータの組を生成し、レンジデータの相対移動処理を実行して、各微少移動ポイントにおいて、レンジデータ相互の対応点を算出し、算出した対応点に基づいて、テクスチャデータを用いたテクスチャの相関を計算して最も高い相関を示すデータに対する対応点を出力し、出力した対応点に基づいてレンジデータの移動量を算出する構成であるので、表面形状に特徴のない物体においても正確なレンジデータの位置合わせ、高精度な三次元モデルの生成が可能となる。
【図面の簡単な説明】
【図１】測定対象物のレンジデータの取得構成とレンジデータの相関について説明する図である。
【図２】測定対象物のレンジデータの取得構成と、レンジデータの相関による位置合わせが困難な例について説明する図である。
【図３】本発明の三次元データ処理装置の構成を示すブロック図である。
【図４】本発明の三次元データ処理装置におけるレンジデータ、テクスチャデータの取得構成について説明する図である。
【図５】本発明の三次元データ処理装置における対応点探索部の詳細構成について説明する図である。
【図６】本発明の三次元データ処理装置における対応点設定処理例について説明する図である。
【図７】本発明の三次元データ処理装置における処理フロー（その１）を示す図である。
【図８】本発明の三次元データ処理装置における処理フロー（その２）を示す図である。
【図９】本発明の三次元データ処理装置のハードウェア構成例を示す図である。
【符号の説明】
１０１  測定対象
１０２，１０３  レンジデータ測定器
２０１  測定対象
３０１  レンジデータ入力部
３０２  テクスチャデータ入力部
３０３  データ保持部
３０４  レンジデータ保持部Ａ
３０５  テクスチャデータ保持部Ａ
３０６  移動量保持部Ａ
３０７  移動量出力部
３０８  対応点探索部
３０９  移動量算出部
４０１  測定対象
４０２  測定ポイント
５０１  レンジデータ保持部ｉ
５０２  テクスチャデータ保持部ｉ
５０３  レンジデータ保持部ｉ＋１
５０４  テクスチャデータ保持部ｉ＋１
５０５  対応点探索部
５０６  テクスチャ相関算出部
５０７  対応点算出部
５０８  微少移動部
５０９  相関値保持部
５１０  対応点保持部
５１１  対応点出力部
６０１  中央演算処理装置（ＣＰＵ:Central Processing Unit）
６０２  ＲＯＭ（Read only Memory）
６０３  ＲＡＭ（Random Access Memory）
６０４  ビデオコントローラ
６０５  ＶＲＡＭ（Video RAM）
６０６  画像表示部
６０７  ストレージコントローラ
６０８  磁気ディスク６０８
６０９  光磁気ディスク
６１０  光ディスク
６１１  不揮発性メモリ
６１２  通信コントローラ
６１３  入力デバイスコントローラ
６１４  キーボード
６１５  ポインティングデバイス
【図１】
0004608152.tif 000005
【図２】
0004608152.tif 000006
【図３】
0004608152.tif 000007
【図４】
0004608152.tif 000008
【図５】
0004608152.tif 000009
【図６】
0004608152.tif 000010
【図７】
0004608152.tif 000011
【図８】
0004608152.tif 000012
【図９】
0004608152.tif 000013