(57)【特許請求の範囲】
【請求項１】
対象物を表わす複数の３次元形状データを格納する工程と、
前記複数の３次元形状データ同士の位置合わせを行なう工程と、
前記位置合わせを行なった複数の３次元形状データに対して、前記複数の３次元形状データの境界近傍に切断面を設定する工程と、
前記切断面により分離された部分形状データを求める工程と、
前記切断面毎に、前記部分形状データの切断面を挟む領域のデータを２次元座標系で表現し、ドロネー網を用いて該領域に三角形パッチデータを生成する工程と、
を有することを特徴とする３次元形状データ統合方法。
【請求項２】
対象物を表わす複数の３次元形状データを格納する工程と、
前記複数の３次元形状データに対し２つの形状データ毎に、前記３次元形状データの境界近傍に切断面を設定する工程と、
前記切断面により分離された部分形状データを求める工程と、
前記切断面毎に、前記部分形状データの切断面を挟む領域のデータを２次元座標系で表現し、ドロネー網を用いて該領域に三角形パッチデータを生成する工程と、
を有することを特徴とする３次元形状データ統合方法。
【請求項３】
前記三角形パッチデータを追加した統合データを作成して保存する工程を更に有することを特徴とする請求項１又は２に記載の３次元形状データ統合方法。
【請求項４】
前記３次元形状データは、三角形パッチにより表現されたデータであることを特徴とする請求項１乃至３のいずれか１項に記載の３次元形状データ統合方法。
【請求項５】
前記３次元形状データは、各三角形の頂点座標及び各頂点同士の接続情報を含むことを特徴とする請求項４に記載の３次元形状データ統合方法。
【請求項６】
対象物を表わす複数の３次元形状データを格納する格納手段と、
前記複数の３次元形状データ同士の位置合わせを行なう位置合わせ手段と、
前記位置合わせ手段により位置合わせを行なった複数の３次元形状データに対して、前記複数の３次元形状データの境界近傍に切断面を設定する切断面設定手段と、
前記切断面により分離された部分形状データを求める形状分割手段と、
前記切断面毎に、前記部分形状データの切断面を挟む領域のデータを２次元座標系で表現し、ドロネー網を用いて該領域に三角形パッチデータを生成して前記複数の３次元形状データを統合する統合手段と、
を有することを特徴とする３次元形状データ統合装置。
【請求項７】
対象物を表わす複数の３次元形状データを格納する格納手段と、
前記複数の３次元形状データに対し２つの形状データ毎に、前記３次元形状データの境界近傍に切断面を設定する設定手段と、
前記切断面により分離された部分形状データを求める形状分割手段と、
前記切断面毎に、前記部分形状データの切断面を挟む領域のデータを２次元座標系で表現し、ドロネー網を用いて該領域に三角形パッチデータを生成して前記複数の３次元形状データを統合する統合手段と、
を有することを特徴とする３次元形状データ統合装置。
【請求項８】
前記３次元形状データは、三角形パッチにより表現されたデータであることを特徴とする請求項６又は７に記載の３次元形状データ統合装置。
【請求項９】
前記３次元形状データは、各三角形の頂点座標及び各頂点同士の接続情報を含むことを特徴とする請求項８に記載の３次元形状データ統合装置。
【請求項１０】
複数の３次元形状データ同士の位置合わせを行なう工程と、
前記位置合わせを行なった複数の３次元形状データに対して、前記複数の３次元形状データの境界近傍に切断面を定義する工程と、
前記切断面により分離された部分形状データを求める工程と、
前記部分形状データの切断面を挟む領域のデータを２次元座標系で表現し、三角形パッチデータを生成する工程と、
を有することを特徴とする３次元画像処理方法。
【請求項１１】
前記三角形パッチデータを追加した統合データを作成して保存する工程を更に有することを特徴とする請求項１０に記載の３次元画像処理方法。
【請求項１２】
前記３次元形状データは、三角形パッチにより表現されたデータで、各三角形の頂点座標及び各頂点同士の接続情報を含むことを特徴とする請求項１１に記載の３次元画像処理方法。
【発明の詳細な説明】
【０００１】
【産業上の利用分野】
本発明は、複数の三角形パッチを使用した形状データを１つの３次元形状データに統合するための３次元形状データ統合方法及びその装置と３次元画像処理方法に関するものである。
【０００２】
【従来の技術】
従来より距離画像を入力できる画像入力装置などを使用して、対象物体の３次元形状データを入力する技術が開発されている。このような距離画像の入力技術としては、
(１)  光の飛行時間を時間計測や位相計測の手法を用いて計測し、光が物体に当たって帰ってくるまでの時間から物体までの距離を測定する光波距離計測を用いる。
【０００３】
(２)  複数台のカメラを用いて同じ情景を異なる角度から撮影し、各カメラにより撮影された画像中の対応点を求めて三角測量の原理で距離を計測する。
【０００４】
(３)  カメラと光のパターンなどを投影する投影器を用いて、三角測量の原理で計測するなどの方法がある［参考文献：オプトエレクトロニクス(1985),No.12,pp.59-,井口征士ほか］。そして、距離画像データより複数の解像度の法線ベクトルを作成し、この距離画像データと法線ベクトルより複数のエッジマップデータを作成して複数の大きさを持つポリゴンデータを生成し、そのポリゴンデータを三角形に分割することにより三角形パッチを生成して、対象物体の形状データを生成していた。
【０００５】
【発明が解決しようとする課題】
しかしながら上記従来例によれば、鏡の回転を利用して光を２次元的に対象物体上を走査させたり、固定したカメラを用いて対象物体を撮像するので、表面に現れない対象物体の裏や上面、底面を測定することができない。このため、対象物体を全方位から見た３次元の形状データを生成できないという問題点があった。
【０００６】
本発明は上記従来例に鑑みてなされたもので、複数方向から入力した距離画像データを基に独立に生成した複数の３次元形状データを１つに統合し、対象物体の完全な幾何形状データを作成することができる３次元形状データ統合方法及びその装置と３次元画像処理方法を提供することを目的とする。
【０００７】
【課題を解決するための手段】
上記目的を達成するために本発明の３次元形状データ統合装置は以下のような構成を備える。即ち、
対象物を表わす複数の３次元形状データを格納する格納手段と、前記複数の３次元形状データ同士の位置合わせを行なう位置合せ手段と、前記位置合せ手段により位置合わせを行なった複数の３次元形状データに対して、前記複数の３次元形状データの境界近傍に切断面を設定する切断面設定手段と、前記切断面により分離された部分形状データを求める形状分割手段と、前記切断面毎に、前記部分形状データの切断面を挟む領域のデータを２次元座標系で表現し、ドロネー網を用いて該領域に三角形パッチデータを生成して前記複数の３次元形状データを統合する統合手段とを有する。
【０００８】
また、上記目的を達成するために本発明の３次元形状データ統合方法は以下のような工程を備える。即ち、
対象物を表わす複数の３次元形状データを格納する工程と、前記複数の３次元形状データ同士の位置合わせを行なう工程と、前記位置合わせを行なった複数の３次元形状データに対して、前記複数の３次元形状データの境界近傍に切断面を設定する工程と、前記切断面により分離された部分形状データを求める工程と、前記切断面毎に、前記部分形状データの切断面を挟む領域のデータを２次元座標系で表現し、ドロネー網を用いて該領域に三角形パッチデータを生成する工程とを有する。
【０００９】
【作用】
以上の構成において、対象物を表わす複数の３次元形状データを格納し、それら複数の３次元形状データ同士の位置合わせを行ない、その位置合わせを行なった複数の３次元形状データに対して、複数の３次元形状データの境界近傍に切断面を設定する。そして、この切断面により分離された部分形状データを求め、その切断面毎に、部分形状データの切断面を挟む領域のデータを２次元座標系で表現し、ドロネー網を用いて該領域に三角形パッチデータを生成するして統合するように動作する。
【００１０】
【実施例】
以下、添付図面を参照して本発明の好適な実施例を詳細に説明する。以下、本実施例を説明する前に、本実施例の３次元形状データ統合方法の概要を図１を参照して説明する。
【００１１】
本実施例の３次元形状データ統合装置では、距離画像データから生成される対象物の形状を表す、三角形ポリゴンデータ１０１，１０２を入力する。ここで、入力される形状データが１つだけでは、対象物体を一方から見た、或は対象画像の一部だけの形状を表現しているにすぎない場合がある。例えば、対象物体を上方から観察して入力される距離画像から生成される形状データには、その対象物体の側面や底面の形状が表現されていない。そこで、その対象物体を別の方向から表現した３次元のポリゴンデータを複数入力する必要がある。図１の１０３は格納される形状データを示し、１０４は形状データ１０２を回転させたデータを示している。
【００１２】
このように複数の形状データを入力する場合、入力される形状データ１０１，１０２のそれぞれは独自の座標系で構成されている場合がある。このような場合には、個々の座標系の間の位置関係（必要に応じて平行移動と回転を行う）の整合をとり、全ての形状データを１つの世界座標系で表現できるように、位置合わせを行なう（図１の１０５で示す）。本実施例では、この工程は操作者による対話操作により行なう。
【００１３】
次に、互いに共有する部分を有する２つの形状データを選択し、これら２つの形状データにおける重なり合った部分に切断面（図１の１０９）を設定する。そして、この切断面を境界として、上記の２つの形状データが後の処理で統合する。なお、この切断面は必ず２つの形状データの重複する部分に設定される。本実施例では、この工程は操作者による対話操作により行なう。
【００１４】
更に、この切断面で、個々の形状データを２つの部分に分割し、その内の１つの部分を選択する。この部分を選択する際には、精度が高く、より多くのデータが含まれる部分形状データを選択する。こうして２つの形状データから１つずつ部分形状データが選択される。
【００１５】
次に、これら２つの部分形状データを統合する。そのために、一方の部分形状データの内、切断面に隣接している点データを、他方の部分形状データの座標系(３次元座標系)に変換する。さらに、後者の部分座標データ中で切断面に隣接する点データと共に、適当な画像の座標系(２次元座標系)に射影する。そして、この座標系上に射影された点データを用いて、ドロネー三角網を生成する。こうして生成される三角網の接続関係を、切断面を境界に接している元の点データの接続関係とし、その切断面を挟んで三角形パッチの存在しない領域に三角形パッチを生成する。そして、個々の部分形状データと、生成される三角形パッチとにより、元の２つの形状データを統合する。そして最後に、このようにして統合された対象物体の形状データを、他のアプリケーションで利用できるように出力する。
【００１６】
以下、本実施例の３次元形状データ統合装置について詳細に説明する。
【００１７】
図２は、本発明の一実施例による３次元形状データ統合装置の基本構成を表すブロック図である。
【００１８】
図２において、２０１は記憶装置で、ＣＰＵ２０３により実行される処理手順を記述したプログラムやデータ等を記憶している。２０２は処理に必要な情報及び入出力データを記憶するための記憶装置である。ＣＰＵ２０３は、記憶装置２０１に記憶された処理手順を記述する制御プログラムに従って各種制御処理を行なっている。２０４は、液晶やＣＲＴ等の表示部で、処理に必要な情報や、３次元形状データなどを表示する。２０５はバリュエータで、操作者が形状データの平行移動や回転を指示するのに使用される。２０６はキーボードで、ユーザからのデータや各種指示を入力するのに使用される。２０７はマウス等のポインティングデバイスで、表示部２０４の表示画面上でマウスカーソルの移動を指示したり、各種コマンドやメニューなどを指示するのに使用される。２０８はインターフェース部で、図示しない外部機器とのデータの交換を行なうために使用される。
【００１９】
図３は、本実施例の３次元形状データの統合装置の記憶装置２０２に格納される形状データファイル、即ち三角形ポリゴンデータのデータフォーマットを示す図である。
【００２０】
図３において、２１は対象物体１の形状を表す形状データである。識別子２２(ＩＤ0)と、頂点座標２３（ＩＤp，Ｘ，Ｙ，Ｚ）と、頂点間の接続情報２５が記述されている。撮影条件２７は、形状データを生成する基となる距離画像の撮影条件、または複数の形状データが統合された形状データの場合、元の形状データの情報が記憶されている。２８はデリミタであり、各対象物体情報の区切りを表している。このデリミタ２８を用いて複数の対象物体のポリゴンデータを格納できる。
【００２１】
頂点データ２３は、対象物体の形状データに含まれる全ての三角形パッチの頂点の３次元座標(Ｘ,Ｙ,Ｚ)に識別子ＩＤpを付与したデータである。デリミタ２４は、頂点データ２３と接続情報２５との区切りを表している。接続情報２５は、ポリゴンデータの接続情報を表しており、３つの頂点の識別子を一組として１つの三角形を表している。２６はデリミタであり、接続情報２５と撮影条件２７との区切りを表している。デリミタ２６は、接続情報２５と撮影条件２７の区切りを表している。デリミタ２８は１つの対象物体の形状データの終了を表すコード、ＥＯＦ２９は、形状データファイルの終了を表すコードである。
【００２２】
次に、本実施例の３次元形状データの統合装置の記憶装置２０２に格納された形状データを用いて３次元形状データを統合する手順を図４のフローチャートを参照して説明する。この処理を実行するプログラムは記憶装置２０１に記憶されており、ＣＰＵ２０３の制御の下に実行される。
【００２３】
まずステップＳ１で、形状データを記憶している形状データファイルを、記憶装置２０２から読み込む。この形状データファイルのデータフォーマットは図３に示すようであり、１つの形状データファイルには複数の形状データが含まれるが、ステップＳ２で示すように、複数の形状データファイルを読み込んで、複数の形状データを読み込むようにしても良い。
【００２４】
次にステップＳ３に進み、ステップＳ１で読み込まれたて記憶された形状データに基づく画像を表示部２０４の画面に表示する。ここで各形状データが独自の座標系に基づいて構成されている場合には、表示部２０４の画面に映しだされた各形状データを見ながら、オペレータがキーボード２０６及びバリュエータ２０５を操作して、個々の座標系の間の位置関係(必要に応じて平行移動や回転等を実行して)の整合をとり、全ての形状データが１つの世界座標系で表現できるように位置合わせを行なう。ここでは、３次元空間内での平行移動と回転の自由度は“６”であるので、本実施例では６つの自由度を、オペレータが対話的に指定することにより位置合わせを行なっている。
【００２５】
そしてステップＳ４に進み、全ての（図１の例では２つの）形状データを選択し、それらの図形が重なった部分に切断面を設定する(ステップＳ５)。このステップＳ５も、表示部の画面上に映しだされた各形状データをオペレータが見ながら、キーボード２０６及びバリュエータ２０５を操作して行なう。さらに、この切断面で、個々の形状データを２つの部分に分割し、個々の形状データにおいて、統合後の形状データとして残す部分の形状データを選択する(ステップＳ６)。これにより切断面を挟む２つの部分形状データが選択される。次にステップＳ７に進み、これら２つの部分形状データ同士を統合する(ステップＳ７)。そしてステップＳ８では、上記の処理による形状統合を、全ての形状データが統合されるまで繰り返し、全ての形状データが統合されるとステップＳ９に進み、このようにして統合された対象物体の形状データを、図３で示すフォーマットの形状データファイルとして出力する。
【００２６】
図５は、図４のステップＳ６の形状分割処理を示すフローチャートで、この処理は、２つの形状データそれぞれに対して実行される。
【００２７】
まずステップＳ１１で、形状データに含まれる頂点の集合を、切断面を境界とする２つの部分に分割する。即ち、頂点の３次元座標を(ｘ1,ｙ1,ｚ1)，切断面の方程式をａｘ＋ｂｙ＋ｃｚ＋ｄ＝０とすると、
ａｘ1＋ｂｙ1＋ｃｚ1＋ｄ≧０  と  ａｘ1＋ｂｙ1＋ｃｚ1＋ｄ＜０
とで示されるの２つの部分に分割される。これにより、頂点の集合が２つの部分集合ＡとＢに分割されることになる。次にステップＳ１２に進み、形状データのポリゴンデータの頂点と頂点を結ぶ辺Ｐ1Ｐ2に対して、両端点Ｐ1，Ｐ2が部分集合ＡまたはＢのどちらに属するかを求める。そして、両端点がそれぞれ部分集合ＡとＢに属する頂点の場合、即ち、
（(Ｐ1∈Ａ)∧(Ｐ2∈Ｂ)）∨（(Ｐ1∈Ｂ)∧(Ｐ2∈Ａ)）
が真かどうかを判定し（ステップＳ１３）、真であればステップＳ１４に進む。ステップＳ１４では、その辺Ｐ1Ｐ2が切断面により切断されていることを示しているため、その辺Ｐ1Ｐ2をポリゴンデータから削除する。この処理を、ポリゴンデータの全ての辺に対して行ない、全ての辺に対する処理が終了するとステップＳ１５からステップＳ１６に進み、頂点の部分集合Ａ又はＢに属する頂点のみにより構成されるポリゴンデータＤA，ＤBが生成される。そしてステップＳ１６で、統合後のデータとして残すポリゴンデータを、ポリゴンデータＤA，ＤBより１つだけ選択する。この選択ステップは、表示部２０４の画面上に表示された２つのポリゴンデータＤA，ＤBの形状を観察しながら、オペレータがマウス２０７やキーボード２０６を使用して対話的に選択する。
【００２８】
図６は、図４のステップＳ７で示された形状統合処理を示すフローチャートである。
【００２９】
まずステップＳ２１で、切残面により切断された２つの部分形状データの個々について、前述の図５のステップＳ１４で削除された辺Ｐ1Ｐ2の端点であった頂点を選択する。次にステップＳ２２に進み、ステップＳ２１で選ばれた点群を１つの２次元座標系へ変換する。本実施例では、１つのポリゴンパッチＤ1を生成した元の画像の座標系へ、ポリゴンパッチＤ1及びもう１つのポリゴンパッチＤ2から選択された点群を投影する。ポリゴンパッチＤ1に対するステップＳ３（図４）での位置合わせのための変換行列をＲ1(４×４行列)，ポリゴンパッチＤ1に独自の３次元座標系(形状データファイルに記録されている座標)と、このポリゴンパッチの元となる距離画像の２次元座標系との変換行列をＣ1(３×４行列)とすると、世界座標系Ｗで表現される点(ｘ,ｙ,ｚ)は、
【００３０】
【数１】
【００３１】
0003658038.tif 000002
で計算される２次元座標(Ｉ，Ｊ)へ変換される。この投影の際必要な変換パラメータＣ1は、ポリゴンパッチＤ1を記述した形状データの撮影条件２７（図３）に記憶されている。
【００３２】
次にステップＳ２３に進み、投影された点群を用いて２次元座標上でドロネー網を生成する。［参考文献：情報処理(1989),Vol.30,No.9,pp.1067-1075,杉原厚吉］。ドロネー網の辺の内、ポリゴンパッチＤ1の頂点とＤ2の頂点とを接続する辺を選択し、この接続関係をポリゴンパッチＤ1及びＤ2に付加する(ステップＳ２４)。これにより、元のポリゴンパッチＤ1及びＤ2に存在した隙間がポリゴンパッチで接続され、両データの統合が行なえる。
【００３３】
この処理の流れを図７の模式図で示す。
【００３４】
図７において、７０１は、切断面を境に形状データを分割した例を示し、７０２は、ポリゴンデータより削除された辺の端点を選択した（Ｓ２１）結果を示す。７０３は、こうして選択された端点を１つの２次元座標系に変換した（Ｓ２２）例を示している。そして７０４は、これら２次元座標系に変換された端点を用いて、ドロネー網を生成した例を示している。７０５は、これらドロネー網の辺の内、切断面の上側のポリゴンバッチの頂点と切断面の下側のポリゴンバッチの頂点とを接続する辺を選択し、これら選択された辺に基づく接続関係を追加する。これにより切断面を挟む形状データ同士が接続されたことになる。
【００３５】
［第２実施例］
図８は本発明の第２実施例の３次元形状データの統合装置の概略構成を示すブロック図で、前述の図２の構成と共通する部分は同じ番号で示し、それらの説明を省略する。。
【００３６】
図８では、２０８は、液晶シャッタ眼鏡或は偏光フィルタ眼鏡で、この眼鏡２０８と表示部２０４とを用いることにより、３次元形状データを立体的に観察することができる。これにより、オペレータが、前述した図４のステップＳ３やＳ５の操作を効率的に行なうことが可能である。
【００３７】
またこの場合、前述の図４の処理の代わりに、図９に示す処理の流れを実行しても、その効果は変わらない。
【００３８】
この図９のフローチャートと図４のフローチャートとを比較すると、ステップＳ３１とＳ３２、及びステップＳ３５〜Ｓ３９は、それぞれ図４のステップＳ１，Ｓ２とステップＳ５〜Ｓ９に対応しており、図４のステップＳ３，Ｓ４が図９のステップＳ３３，Ｓ３４のように順番が入れ替えられているだけである。従って、図９のフローチャートでは、統合する２つの対象物体の形状データを選択した後、それら２つについてのみ位置合わせを行なう。
【００３９】
尚、本発明は、複数の機器から構成されるシステムに適用しても、１つの機器から成る装置に適用しても良い。また、本発明はシステム或は装置に本発明を実施するプログラムを供給することによって達成される場合にも適用できる。
【００４０】
以上説明したように本実施例によれば、対象物体を複数方向から見た距離画像データを基にそれぞれ独立に生成したポリゴンパッチデータを１つのデータに統合することにより、対象物体の形状を表わす欠如部分のない幾何形状データを生成することができる。このような幾何形状データを用いることにより、ＣＡＤやバーチャルリアリティ等で利用できる形状モデルの高機能化が可能となる。
【００４１】
【発明の効果】
以上説明したように本発明によれば、複数方向から入力した距離画像データを基に独立に生成した複数の３次元形状データを１つに統合し、対象物体の完全な幾何形状データを作成することができる効果がある。
【００４２】
また本発明によれば、複数の方向から対象物を捉えた３次元形状データに基づいて対象物体の完全な形状データを容易に作成することができる。
【００４３】
【図面の簡単な説明】
【図１】本実施例における３次元形状データを統合する工程を示す模式図である。
【図２】本発明の実施例の３次元形状データ統合装置の概略構成を示すブロック図である。
【図３】本実施例で扱う三角形ポリゴンデータの形状データのデータフォーマットを示す図である。
【図４】本実施例の３次元形状データ統合処理の流れを示すフローチャートである。
【図５】本実施例の３次元形状データ統合処理におけるステップＳ６の形状分割処理の流れを示すフローチャートである。
【図６】本実施例の３次元形状データ統合処理におけるステップＳ７の形状統合処理の流れを示すフローチャートである。
【図７】本実施例における３次元形状データ統合処理を示す模式図である。
【図８】本発明の他の実施例の３次元形状データ統合装置の機器構成を示すブロック図である。
【図９】他の実施例の３次元形状データ統合処理の流れを示すフローチャートである。
【符号の説明】
２２  識別子
２３  頂点データ
２４，２６，２８  デリミタ
２５  ポリゴンデータ
２７  撮影条件
２０１  記憶装置
２０２  記憶装置
２０３  ＣＰＵ
２０４  表示部
２０５  バリュエータ
２０６  キーボード
２０７  マウス
２０８  立体視用メガネ
【図１】
0003658038.tif 000003
【図２】
0003658038.tif 000004
【図３】
0003658038.tif 000005
【図４】
0003658038.tif 000006
【図５】
0003658038.tif 000007
【図６】
0003658038.tif 000008
【図７】
0003658038.tif 000009
【図８】
0003658038.tif 000010
【図９】
0003658038.tif 000011