(57)【特許請求の範囲】
【請求項１】
レンジ画像から勾配の大きさによる画像を判定するための方法であって、前記レンジ画像は各画素位置において複数の強度値を含み、
各画素（ｉ、ｊ）に対して、水平中心差分ｄｘおよび垂直中心差分ｄｙを判定することと、
勾配の大きさによる画像ＩＧＭ内の前記各画素（ｉ、ｊ）における２Ｄの勾配の大きさを、０．５＊ｓｑｒｔ（ｄｘ２＋ｄｙ２＋４）に設定することと、
前記レンジ画像をスケーリングし、スケーリングされたレンジ画像を生成することと、
３Ｄ点ｐを選択することと、
前記スケーリングされたレンジ画像と、前記勾配の大きさによる画像ＩＧＭとから、点ｐにおける勾配の大きさを判定することとを含み、
前記各画素における単位強度値は、単位距離値に対応し、
前記勾配の大きさを判定することは、
位置（ｘ，ｙ）を判定するために、前記スケーリングされたレンジ画像上に点ｐを垂直に投影することと、
前記位置（ｘ，ｙ）付近の対応する２Ｄの勾配の大きさによる画像値から、前記位置（ｘ，ｙ）における勾配の大きさを補間することと、
前記点ｐにおける前記勾配の大きさを、前記位置（ｘ，ｙ）において前記補間される勾配の大きさに設定することとを含む方法。
【請求項２】
レンジ画像から勾配の大きさによる画像を判定するための方法であって、前記レンジ画像は各画素位置において複数の強度値を含み、
各画素（ｉ、ｊ）に対して、水平中心差分ｄｘおよび垂直中心差分ｄｙを判定することと、
勾配の大きさによる画像ＩＧＭ内の前記各画素（ｉ、ｊ）における２Ｄの勾配の大きさを、０．５＊ｓｑｒｔ（ｄｘ２＋ｄｙ２＋４）に設定することと、
前記レンジ画像をスケーリングし、スケーリングされたレンジ画像を生成することと、
３Ｄ点ｐにおける補正された投影距離を判定するために、
前記スケーリングされたレンジ画像から前記点ｐにおいて投影された距離を判定することと、
前記スケーリングされたレンジ画像と、前記勾配の大きさによる画像（ＩＧＭ）とから前記点ｐにおける勾配の大きさを判定することとを含み、
前記各画素における単位強度値は単位距離値に対応し、
前記勾配の大きさを判定することは、
位置（ｘ，ｙ）を判定するために、前記スケーリングされたレンジ画像上に点ｐを垂直に投影することと、
前記位置（ｘ，ｙ）付近の対応する２Ｄの勾配の大きさによる画像から、前記位置（ｘ，ｙ）における勾配の大きさを補間することと、
前記点ｐにおける前記勾配の大きさを、前記位置（ｘ，ｙ）において補間される前記勾配の大きさに設定することと、
前記点ｐにおいて補正された投影距離を、前記点ｐにおいて投影された距離を前記点ｐにおける前記勾配の大きさで割った値に設定することとを含む方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
この発明は全般にコンピュータグラフィクスの分野に関し、詳細には、レンジ画像からグラフィクス物体のモデルを生成することに関する。
【０００２】
具体的には、この発明は、レンジ画像から直接に物体の形状を判定するための方法に関する。
【０００３】
【従来の技術】
１組の位置合わせされたレンジ画像から３Ｄ構造を判定するために、研究および産業においていくつかの方法が開発されている。Curlassによる「From range scans to 3D models」（Comp. Graphics, Vol. 33, No.4, 1999）を参照されたい。
【０００４】
最近の研究は、ボリュームを用いる方法がスキャナ雑音および位置合わせの不確定性に耐性があり、良好な品質の水密モデルを提供することを示している。Curlass他による「A volumetric method for building complex models from range images」（Proc. SIGGRAPH'96, pp. 303-312, 1996）、Hilton他による「Reliable surface reconstruction from multiple range images」（4th Euro. Conf. Comp. Vis., pp. 117-126, 1996）およびWheelerによる「Automatic modeling and localization for object recognition」（Ph. D. Thesis, Carnegie Mellon University, 1996）を参照されたい。
【０００５】
しかしながら、これらの方法の大部分は、解像度が制限され、大きなメモリを必要とし、処理時間が長いという問題を抱える。さらに、これらの方法は、過度の多くの三角形を用いるメッシュモデルを生成する。
【０００６】
これらの方法は、位置合わせされた各レンジ画像のためのレンジ表面を構成し、レンジ表面からの符号付の距離で、固定された解像度のボリューム表現を満たす。その方法は、距離値のランレングス符号化、その表面の限られた領域の外側の領域のバイナリ符号化、およびボリュームの３色八分木表現を含む種々の技術を用いて、ボリュームデータを満たし、さらにボリュームデータにアクセスするためにかかる時間を短縮する。多数の走査からの距離値は、順序に無関係の、あるいはインクリメンタルな更新を用いて、確率論的に組み合わせることができる。これらの方法は全て、よく知られているマーチングキューブ技術を用いて、距離ボリュームの等値面の三角形モデルを構築する。Lorensen他による「Marching Cubes: A High Resolution 3D Surface Construction Algorithm」（Proc. SIGGRAPH'87, pp. 163-169, 1987）を参照されたい。
【０００７】
３Ｄレンジ表面を構成し、これらの等値面からの距離を計算することは、計算に関する要件を著しく増加させる。代わりに、２Ｄレンジ画像から直接に距離フィールドを生成することができたなら、モデル生成時間を著しく短縮することができるであろう。
【０００８】
しかしながら、レンジ画像は正確な距離値を提供しない。最も簡単な場合には、レンジ画像は、物体の表面から画像平面に垂直に投影される距離を記録する。投影された距離フィールドは、２つの特別な場合にのみ、すなわち画像平面に厳密に平行な平坦な表面の場合の距離フィールドにわたってのみ、また正確な距離および投影される距離の両方が任意の表面の場合に０である表面においてのみ正確な距離フィールドと同じである。
【０００９】
第１の場合以外では、投影される距離フィールドは、その表面から外れた点のための正確な距離フィールドとは異なる。この結果として、異なる視点から投影される距離フィールドが組み合わせられる際にアーティファクトが生じる。
【００１０】
Frisken他によって１９９９年１２月４日に出願された「A Method for Estimating Volumetric Distance Maps from 2D depth Images」というタイトルの米国特許出願第０９／２０６，０７１号に記載される従来技術は、３Ｄ投影距離フィールドが、サンプリングされた距離を投影された距離フィールドの局所的な３Ｄ勾配の大きさで割ることにより補正されることができることを示した。この結果、その表面付近の正確な距離フィールドの良好な近似が得られ、投影される距離フィールドを組み合わせる際に良好な結果が生成される。しかしながら、サンプリングされた距離値から直接に、投影された距離フィールドの３Ｄ勾配を計算することは、それが勾配当たり６つ以上の付加的な距離フィールドの評価を必要とするようになるため、法外なコストがかかるようになる。
【００１１】
【発明が解決しようとする課題】
それゆえ、この発明の目的は、３Ｄボリュームデータではなく、レンジ画像から直接に、補正された距離フィールド勾配を判定することである。
【００１２】
【課題を解決するための手段】
この発明は、３Ｄの勾配の大きさを導出することができる物体のレンジ画像から、２Ｄの勾配の大きさにより画像を判定するための方法を提供する。そのレンジ画像は画素位置において複数の強度値を含む。その強度値は、その物体の表面までの距離に対応する。
【００１３】
本方法は、単位強度値が単位距離値に対応するようにレンジ画像をスケーリングする。その際、レンジ画像内の各画素ｓｉ，ｊに対して、本方法は、水平中心差分ｄｘと垂直中心差分ｄｙとを判定する。その後、各画素ｓｉ，ｊにおける２Ｄの勾配の大きさが、（ｄｘ２＋ｄｙ２＋４）の平方根の半分に設定される。
【００１４】
その際、３Ｄに投影された距離フィールドの勾配の大きさは、スケーリングされたレンジ画像の位置（ｘ，ｙ）上の点ｐを垂直に投影し、位置（ｘ，ｙ）付近の対応する２Ｄの勾配の大きさの画像値からの（ｘ，ｙ）において勾配の大きさを補間し、さらに、点ｐにおける３Ｄの勾配の大きさを、（ｘ，ｙ）において補間された２Ｄの勾配の大きさに設定することにより、３Ｄ点ｐにおいて判定されることができる。
【００１５】
【発明の実施の形態】
序論
２Ｄのレンジ画像から直接に、投影された距離フィールドの３Ｄの勾配の大きさを判定するための方法を記載する。この発明による方法を用いると、ある物体の３Ｄの形状を、従来技術のようなレンジ表面ではなく、２Ｄのレンジ画像から直接に導出することができる。さらに、この発明による方法を用いて、距離ボリュームあるいは３色の八分木ではなく、適応的にサンプリングされる距離フィールド（ＡＤＦ）を生成し、結果として、メモリおよび距離の計算を著しく節約することができる。
【００１６】
この発明は、サンプリングされた距離を局所的な勾配の大きさで割ることにより、３Ｄに投影された距離フィールドを補正する。この結果、表面付近の正確な距離フィールドの良好な近似が得られ、投影された距離フィールドを組み合わせる際に良好な結果が生成されるようになる。この発明による方法は、予備処理こと中に生成される２Ｄの勾配の画像から３Ｄの勾配を導出するので、結果として著しく速く生成できるようになる。
【００１７】
いくつかの走査システムのレンジ画像は単純に投影された距離ではないので、レンジ画像は最初にこの形に変換されなければならない。この変換の結果として、走査からの情報のある量の損失が生じるが、この発明の利点は、非常に高速に動作し、それゆえ、データの取得中にインタラクティブに更新できるようにすることを含む。
【００１８】
適応的にサンプリングされる距離フィールド
この発明は、ある物体の形状を表すために、適応的にサンプリングされた距離フィールド（ＡＤＦ）を用いることが好ましい。ここでは、物体の形状は、図１に示されるように、レンジ画像１０５によって取得される。ＡＤＦの基本的なデータ構造は、参照して全体として本明細書に援用される、Frisken他による１９９９年８月６日出願の「Detail-Directed Distance Fields」というタイトルの米国特許出願第０９／３７０，０９１号に記載される。
【００１９】
ＡＤＦは、ある物体の符号付の距離フィールドを適応的にサンプリングし、高速に処理するために、空間的な階層にサンプリング値を格納する。正の符号を有する距離値はその物体の外部にあり、負の距離値は内部にあり、０の距離値はその物体の表面を表す。
【００２０】
ＡＤＦにおいて動作することができる方法は、Perry他によって２００１年３月１６日に出願された「System and Method for Generating Adaptively Sampled Distance Fields with Bounded Distance Trees」というタイトルの米国特許出願第０９／８１０，９８３号、Frisken他によって２００１年３月１６日に出願された「Conversion of Adaptively Sampled Distance Fields to Triangles」というタイトルの米国特許出願第０９／８１０，８３９号、Perry他によって２００１年３月１６日に出願された「System and Method for Modeling Graphics Objects」というタイトルの米国特許出願第０９／８１１，０１０号およびFrisken他によって２００１年３月１６日に出願された「System and Method for Converting Range Data to 3D Models」というタイトルの米国特許出願第０９／８０９，６８２号に記載される。
【００２１】
「Adaptively sampled distance fields: a general representation of shape for computer graphics」（Proc. SIGGRAPH'00, pp. 249-254, 2000）においてFrisken他は、２Ｄの場合でも、ＡＤＦが「Automatic modeling and localization for object recognition」（Ph. D. Thesis, Carnegie Mellon University, 1996）においてWheelerによって用いられるような互換性のある３色八分木表現に比べて、２０分の１しか距離計算を必要としないことを見いだした。さらに、ＡＤＦは、オクルージョンおよびセンサ雑音からの孔および他の表面の特異点を容易に補正することができるように、モデリング用（sculping）インターフェースを介してインタラクティブに編集することができる。Perry他による「Kizamu: A system for sculpting digital characters」（Proc. SIGGRAPH'01, 2001）、およびPerry他により２００１年３月１６日に出願された「System and Method for Sculpting Digital Models」というタイトルの米国特許出願第０９／８１０，２６１号を参照されたい。
【００２２】
レンジ画像からの２Ｄの勾配の大きさによる画像
図１は、レンジ画像ＩＲ１０５から２Ｄの勾配の大きさによる画像ＩＧＭ１２５を判定するための方法を示す。こと１１０では、レンジ画像１０５の各画素における強度値がスケーリングされ、スケーリングされたレンジ画像ＩＲＳ１１５が生成される。スケーリングによって、各画素において正規化された単位強度値が単位距離値を確実に表すようになる。
【００２３】
こと１２０では、スケーリングされたレンジ画像１１５から勾配の大きさによる画像１２５が判定される。
【００２４】
各画素（ｉ、ｊ）の場合に、この発明による方法は中心差分値
dx = IRS(i+1, j) - IRS(i-1, j)
dy = IRS(i, j+1) - IRS(i, j-1)
と、（ｉ、ｊ）における２Ｄの勾配の大きさによる画像
ＩＧＭ(i,j) = 0.5 * sqrt(dx2 + dy2 + 4).
とを判定する。
【００２５】
３Ｄに投影された距離フィールドの勾配の大きさ
図２は、スケーリングされたレンジ画像１１５と、勾配の大きさによる画像１２５とから、３Ｄ点ｐ１３０における勾配１４０の大きさを判定するための方法を示す。最初に、スケーリングされたレンジ画像１１５上へのｐ１３０の垂直な投影（ｘ，ｙ）が判定される。次に、（ｘ，ｙ）における勾配の大きさが、位置（ｘ，ｙ）付近の２Ｄの勾配の大きさによる画像１２５の対応する値から補間される。双一次補間（bilinear interpolation）のような任意の知られている従来技術による補間方法を用いることができる。最後に、ｐ１３０における勾配の大きさ１４０が、（ｘ，ｙ）において補間された勾配の大きさに設定される。
【００２６】
この発明は特定の用語および例を用いて記載される。種々の他の適合形態および変更形態が、この発明の精神および特許請求の範囲内で行われる場合があることは理解されたい。それゆえ、併記の特許請求の範囲の目的は、この発明の真の精神および範囲内に入るような全てのそのような変形形態および変更形態を網羅することである。
【図面の簡単な説明】
【図１】  この発明による２Ｄの勾配の大きさによる画像を判定するための方法のブロック図である。
【図２】  ３Ｄに投影される距離フィールドの勾配の大きさを判定するための方法のブロック図である。
【図１】
0004102091.tif 000002
【図２】
0004102091.tif 000003