(57)【特許請求の範囲】
【請求項１】
３Ｄ空間上の点から３Ｄ物体表面までのユークリッド距離Ａ（２０３）を、投影面から３Ｄ物体表面までの投影方向に沿った投影距離Ｂを画素値とするメモリに記憶された投影距離画像から求める方法であって、
前記投影距離画像を使用し、前記３Ｄ空間上の点にて前記投影距離画像の画素点の前記投影距離Ｂを補間して、前記３Ｄ空間上の点から前記３Ｄ物体表面までの前記投影方向に沿った投影距離Ｃ（２０２）を求めることと、
前記投影距離画像を使用して前記３Ｄ空間上の点から前記３Ｄ物体表面内の最も近い崖までのユークリッド距離、すなわち、前記３Ｄ物体表面において前記投影面から前記３Ｄ物体表面までの前記投影距離Ｃ（２０２）が不連続になる領域を崖とし、前記３Ｄ空間上の点が崖の上部（２２１）よりも上方に位置する場合には、前記３Ｄ空間上の点から崖の上部（２２１）までのユークリッド距離であり、前記３Ｄ空間上の点が崖の下部（２２２）よりも下方に位置する場合には、前記３Ｄ空間上の点から崖の下部（２２２）までのユークリッド距離であり、前記３Ｄ空間上の点が崖の上部（２２１）と下部（２２２）との間に位置する場合には、前記３Ｄ空間上の点から崖の表面（２１２）までの最短距離ユークリッド距離である、崖距離Ｄを求めることと、
前記３Ｄ空間上の点から前記３Ｄ物体表面までの前記ユークリッド距離Ａ（２０３）を求めるために前記投影距離Ｃ（２０２）と前記崖距離Ｄとを組み合わせることと
を含み、
前記投影距離Ｃ（２０２）と前記崖距離Ｄとを組み合わせることは、
前記投影距離Ｃ（２０２）と前記崖距離Ｄとのうちの短い方を前記３Ｄの点から前記３Ｄ物体表面までの前記ユークリッド距離Ａ（２０３）として選択すること
をさらに含む方法。
【請求項２】
前記投影距離Ｃ（２０２）を前記ユークリッド距離Ａ（２０３）に修正するための、前記３Ｄ物体表面の前記投影方向に対する勾配量を画素値とする、メモリに記憶された勾配量修正画像の対応する勾配量により、前記投影距離Ｃを修正すること
をさらに含む請求項１に記載の方法。
【請求項３】
前記勾配量修正画像は、前記投影面の２Ｄ投影距離画像の勾配から求められた各画像値を有する２Ｄ画像を含む請求項２に記載の方法。
【請求項４】
前記投影距離画像は、距離スキャナにより取得される視線距離画像から求められる請求項１に記載の方法。
【請求項５】
前記投影距離画像は、グラフィックプロセッサのｚバッファから求められる請求項１に記載の方法。
【請求項６】
前記投影距離画像は、テクスチャを持つ請求項１に記載の方法。
【請求項７】
前記投影距離画像は、高さフィールドである請求項１に記載の方法。
【請求項８】
前記投影距離画像は、標高マップである請求項１に記載の方法。
【請求項９】
複数の投影距離画像から前記３Ｄ空間上の点における複数のユークリッド距離が求められ、
前記複数のユークリッド距離を組み合わせて前記３Ｄ空間上の点から前記３Ｄ物体表面までの合成されたユークリッド距離とすること
をさらに含む請求項１に記載の方法。
【請求項１０】
前記３Ｄ物体表面の距離フィールドをサンプリングするために、３Ｄ空間上の複数の点における複数のユークリッド距離を求める請求項１に記載の方法。
【請求項１１】
前記３Ｄ空間上の複数の点における前記複数のユークリッド距離Ａ（２０３）は、３Ｄモデルを表す請求項１０に記載の方法。
【請求項１２】
距離フィールドを規則的にサンプリングされた体積データセットとして保存することをさらに含む請求項１０に記載の方法。
【請求項１３】
前記３Ｄ物体表面の表面モデルを前記規則的にサンプリングされた体積データセットから生成することをさらに含む請求項１２に記載の方法。
【請求項１４】
前記距離フィールドを適応サンプリングされた距離フィールドとして保存することをさらに含む請求項１０に記載の方法。
【請求項１５】
前記適応サンプリングされた距離フィールドから表面モデルを生成することをさらに含む請求項１４に記載の方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
この発明は、コンピュータグラフィックスに関し、特に距離画像に関する。
【０００２】
【従来の技術】
コンピュータグラフィックスにおいては、情景または物体のモデル内のジオメトリの量を最小にしてモデルの効率的な描画を可能にすることが望ましいことが多い。テクスチャマッピングやバンプマッピングなど低解像度のモデルに視覚的なディテールを追加するためにいくつかの効果的なアプローチが開発されており、Apodaca等の著、「Advanced Renderman」、Morgan Kaufmann、ＩＳＢＮ１５５８６０６１８１、２０００を参照されたい。
【０００３】
しかし、低解像度モデルでは不十分な場合がある。たとえば、高品質志向の制作スタジオでは、詳細な明示的なジオメトリを持つモデルが変形や衝突の検出などの物理シミュレーションのために必要になることが多い。さらに、そのようなスタジオでは、高解像度ジオメトリを持つモデルが必要になる複雑な照明を使用することが多い。
【０００４】
ディスプレースメントマッピングは、基本となるモデルの低解像度ジオメトリに適用して正しい照明を実現できる。この方法は、通常、描画中に動的に実施される操作であり、そのため得られた高解像度ジオメトリを持つモデルを物理シミュレーションに使用することはできない。さらに、芸術家、設計者、技術者、彫刻家などのユーザーには、３Ｄ印刷方法によりソリッド３Ｄモデルを作成するために高解像度のジオメトリを持つモデルが必要な場合がある。
【０００５】
情景や物体の３Ｄジオメトリを直接モデリングするための多数のシステムが知られている。しかし、高解像度ジオメトリを持つモデルの生成は、困難で時間のかかる作業である。自然界で発生する幾何学的なテクスチャの複雑さや多様さを再現するのは非常に困難なことが多い。
【０００６】
Ｃｙｂｅｒｗａｒｅ  ３０３０などの高解像度距離スキャナは、既存のジオメトリを取得するための手段として使用できるが、高解像度スキャナは高価で、持ち運びが困難である。さらに、それらの空間解像度は限られている。手持ち式距離スキャナは、持ち運びは簡単であるが、たまに使用するユーザーにとっては同様に高価で、持ち運びのために空間解像度と奥行き解像度が犠牲になっている。
【０００７】
それに対して、デジタルカメラは持ち運びやすく、安価で、空間解像度が高く、簡単に使用することができる。さらに、Ｐｈｏｔｏｓｈｏｐなどの２Ｄ写真編集システムは、３Ｄモデリングシステムに比べて使用が非常に簡単である。しかし、デジタルカメラは、明示的な奥行き情報を提供しない。
【０００８】
２Ｄ画像から３Ｄモデル用のジオメトリを生成する方法は、コンピュータビジョンの分野と深く関連している。影から形状を抽出したり、焦点から形状を抽出したり、ステレオ対から形状を抽出するための多くの方法が従来技術で知られている。Szeliskiは、「Determining Geometry from Images」、「Course Notes #３９Image-Based Modeling, Rendering, and Lighting」、ＳＩＧＧＲＡＰＨ  １９９９、１９９９においてさまざまなアプローチの文献一覧と概要を述べている。
【０００９】
これまでの研究は、物体や情景の正確なグローバルな形状の記述を取得するための自動化された技法の開発に主に注力されてきた。それに対して、ここでは、対話的な方法を使用して２Ｄ画像から幾何学的な詳細を取得することにより情景内のジオメトリの特徴（spirit）を取得することが目的である。それから、処理に積極的に関わったユーザーは、物体または情景のグローバルな形状の記述を修正したり強調することができる。したがって、この発明の目標は、コンピュータビジョンにおける方法の目標とは大きく異なっている。
【００１０】
しかし、Efros等の著、「Image Quilting for Texture Synthesis and Transfer」、SIGGRAPH Proceedings、pp３４１〜３４６、２００１などのテクスチャ合成方法を拡張して、合成距離画像を生成することができるが、これらの技法では「ディレクタビリティ」が欠如している。ディレクタビリティとは、すべての詳細部分の正確な制御を可能にする処理に対してアニメーション産業でしばしば使用される用語である。
【００１１】
距離データから３Ｄモデルを構築するための既知の従来技術の基本的なアプローチを図１に示す。距離スキャナ１１０は、情景や物体１０１の距離データ１０２を取得する。以降では、「情景」１０１という用語は、屋外の自然の情景、屋内の情景、１つ以上の物体を含んだ情景、それらの組み合わせを指す。岩に覆われた地面、葉、草などテクスチャが顕著な情景や、凹凸のある複雑な表面構造を持つ物体が特に興味の対象である。距離データ１０２を処理１２０して、距離画像１０３と距離３Ｄ表面１０４を形成することができる。ジオメトリ１３０を再構築する方法を使用して、距離画像１０３と距離表面１０４から３Ｄモデル１０５が生成される。
【００１２】
従来技術には多くの再構築方法がある。これらの方法の評価は、Curless等の著、「From range scans to 3D models」、Computer Graphics、Volume３３、No.４、１９９９に記載されている。通常、サンプリングされた距離フィールドの形式を持つ表面の暗示的な表現を求めてから、３Ｄモデルをその暗示的表現の３Ｄ等値面として再構築する方法がある。たとえば、編成されてないばらばらの表面の点の形態を持つ距離データを受け入れることができる非常に一般的に考えられた方法もある。規則的にサンプリングされた２Ｄ格子として距離計測結果が取得された距離画像の形態で利用可能な距離データを使用するその他の方法もある。
【００１３】
距離フィールドを使用する、距離データから３Ｄモデルを再構築するための方法にはいくつかある。これらの方法の中には、データは整列されていない表面の点の集合としてだけ使用可能であることを一般的に仮定する方法もある。Hoppe等の著、「Surface Reconstruction from Unorganized Points」、Proceedings SIGGRAPH ’92、pp７１〜７８、１９９２は、走査された表面の点の近傍からローカル接平面を画定し、これらの平面への符号付き距離を計算することにより規則的にサンプリングされた符号付き距離ボリュームを生成する。Lorensen等の著、「Marching Cubes: a High Resolution 3D Surface Reconstruction Algorithm」、Proceedings SIGGRAPH ’87、pp１６３〜１６９、１９８７に記述されたマーチングキューブをそれから使用して体積表現から表面モデルを生成する。
【００１４】
Bajaj他は、「Automatic Reconstruction of Surfaces and Scalar Fields from 3D Scans」、「Proceedings SIGGRAPH ’95」、pp１０９〜１１８、１９９５において、また、Boissormat他は、「Smooth Surface Reconstruction via Natural Neighbor Interpolaration of Distance Functions」、Proceedings of the 16th Annual ACM Symposium on Computaitonal Geometory、pp２２３〜２３２、２０００において、走査された表面の点からボロノイグラフを構築している。それから、彼らは、ボロノイグラフを使用して効果的に表面への最短距離を評価して、モデルの表面パッチを画定する。
【００１５】
Carr等は、「Reconstruction and Representation of 3D Objects with Radial Basis Functions」、Proceedings SIGGRAPH 2001、pp６７〜７６、２００１において、放射基底関数を走査された表面の点から求められた表面上と表面外の点の集合に当てはめている。表面上の点には、値ゼロが割り当てられ、表面上の点から構築された表面外の点には表面からの、割り当てられた距離に等しい値が割り当てられる。
【００１６】
これらの方法は、すべて、整列されていない点の集合に適用可能であるため、非常に一般的である。しかし、距離データが距離画像の形態で使用可能な場合、その距離画像から距離フィールドを直接求めるのが望ましい。
【００１７】
Curless等は、「A Volumetric Method for Building Complex Models from Range Images」、Proceedings SIGGRAPH ’96、pp３０３〜３１２、１９９６において、Hilton等は、「Reliable Surface Reconstruction from Multiple Range Images」、「Proceedings of the 4th Eurographics Conference on Computer Vision」、１pp１７〜１２６、１９９６において、Wheeler等は、「Consensus surfaces for Modeling 3D Objects from Multiple Range Images」、Proceedings of the International Conference of Computer Vision、１９９８において、距離画像内の最も近い近傍を三角形の小表面により連結することで生成された距離表面から距離フィールドの体積表現を生成する方法を発表している。
【００１８】
これらの方法は、距離値が大きく異なる近傍を接続しないようにすることで、モデル表面内の隠蔽されているかもしれない部分にまたがって三角形による連結を行うことを回避している。このアプローチは、保守的で、観測されていない領域で表面を構築することを避けている。しかし、Curless等が記述しているように、その方法では、別個の対応が必要な穴がモデルに発生することがある。これらの３つの方法は、すべて加重平均方式を使用して、複数の走査の距離値を結合する。Hoppe等の方法に対しては、これらの方法はマーチングキューブを使用して、体積表現から三角形モデルを生成する。
【００１９】
Curless等は、視線距離を使用して、表面を囲む限定された殻内で距離を計算するだけである。距離ボリュームはランレングスにコード化されて、記憶領域と処理時間を減少させる。Hilton等は、表面を囲む限定された殻内で距離表面からのユークリッド距離を求め、結果を規則的にサンプリングされた体積に保存している。Wheeler等も、距離表面からのユークリッド距離を求めているが、距離の評価を三色オクツリーの頂点に限定している。
【００２０】
Whitakerは、「A Level-Set Approach to 3D Reconstruction fromRange Data」、International Journal of Computer Vision、pp２０３〜２３１、１９９８で、距離画像から視線距離を直接求め、窓により限定された加重平均を使用して複数の走査から得られた距離の値を組み合わせている。それから、Whitakerはレベルセット法を使用して、表面を距離フィールドのゼロ値の等値面に引き寄せ、表面の滑らかさなどの形状要件を満たす力の影響を受ける表面を作成することでスキャナの雑音を減らしている。Zhao等は、「Fast Surface Reconstruction using the Level Set Method」、Proceedings 1st IEEE Workshop on Variational and Level Set Methods、pp１９４〜２０２、１９９８でWhitkerと同様の方法を使用しているが、作成する表面を整列されていない点の集合から引き寄せるのに使用する距離フィールドを初期設定する。
【００２１】
最近、Perry等は、「Kizamu: A System for Sculpting Digital Characters」、Proceedings SIGGRAPH 2001、pp４７〜５６、２００１において、また、Sagawa等は、「Robust and Adaptive Integration of Multiple Range Images with Photometric Attributes」、Proceedings IEEE Computer Society Conference on Computer Vision and Pattern Recognition、Volume２、pp１７２〜１７９、２００１において、Wheeler等と同様の方法を記述しているが、３色オクツリーの代わりに適応的にサンプリングされた距離フィールド（ＡＤＦ）を使用して必要な距離評価の数を減らしている。
【００２２】
Frisken等の著、「Adaptively sampled distance fieleds: a general representation of shape for computer graphics」、Proceedings SIGGRAPH 2000、pp２４９〜２５４、２０００に記載されているように、ＡＤＦは適応的に情景や物体の距離フィールドをサンプリングして、高速処理のために空間的階層、たとえばオクツリーにサンプル値を保存する。ＡＤＦはメモリの面で効率的であり、詳細な処理向きであるため、非常に複雑な物体をデスクトップマシーンで扱うことが可能になる。さらに、ＡＤＦは、距離データからジオメトリを再構築するための体積的なアプローチに基づいて（upon）構築するのに使用可能な体積の表現である。
【００２３】
ＡＤＦは、本明細書に参照により援用されるFrisken他により１９９９年８月６日に出願された米国特許出願第０９／３７０，０９１号「Detail directed hierarchical distance fields」に詳細に記載されている。この発明を使用して生成されるＡＤＦモデルは、ここに参照により組み込まれる２００１年３月１６日にPerry他のより出願された米国特許出願第０９／８１０，２６１号「System and method for sculpting digital model」に記載されているように、生成されたＡＤＦを手動で編集し、本明細書に参照により援用される２００１年３月１６日にFrisken他のより出願された米国特許出願第０９／８１０，８３０号「Conversion of adaptively sampled distance field traiangles」に記載されているようにＡＤＦから詳細度（ＬＯＤ）三角形モデルを作成するための直観的なインターフェイスを提供する既存のＡＤＦ彫刻システムに組み込み可能である。
【００２４】
さらに、H. Hoppe著、「Smooth View-Dependent Level-of-Detail Control and its Application to Terrain Rendering」、IEEE Visuarization、pp３５〜４２、October、１９９８などのように、単一の距離画像からのジオメトリの再構築に関連する高さフィールドや標高マップから３Ｄモデルを生成するためのいくつかの方法も存在する。
【００２５】
【発明が解決しようとする課題】
これらの方法は、効率的な描画と効果的な視覚化を提供することに重点を置いているが、ここで必要なそれ以降の編集には重点を置いていない。
そのため、安価なデジタルカメラと２Ｄ編集システムの利点を組み合わせ、２Ｄ画像から直接３Ｄモデルのジオメトリと詳細なテクスチャを生成するための簡潔で高速で費用効果の高い方法を提供することが望まれている。
【００２６】
［発明の概要］
この発明の目的は、２Ｄ写真からテクスチャ付きの距離画像を取得する方法を提供することである。
さらにこの発明の目的は、テクスチャ付き距離画像を３Ｄモデルに対話的に変換するために距離画像から距離を計算するための方法を提供することである。
さらに、この発明の目的は、デジタルカメラと２Ｄ画像エディタを使用して３Ｄモデルのための詳細なジオメトリとテクスチャを取得するための対話的方法を提供することである。
【００２７】
これらの方法は、単独に使用可能であるが、たとえば、対話方法により作成されたテクスチャ付き距離画像を他の手段を使用して距離を計算する再構築方法により３Ｄモデルに変換することが可能で、方法の組み合わせにより、費用効果が高く（たとえば安価なデジタルカメラを使用し、大幅に労力を低減することにより）、実用的で（たとえば、カメラはレンジスキャナを持ち運べない（go）場所に持ち運べる）、わかりやすく（たとえば、カメラと２Ｄエディタは、使用が簡単だがレンジスキャナと３Ｄモデルはそうではない）、堅牢で（たとえば、穴がない水密モデルが作成される）、効率的な（たとえば、モデル生成作業がデスクトップマシーンで数秒でできる）詳細な３Ｄモデルを生成する手段が提供される。
【００２８】
【課題を解決するための手段】
そのため、この発明は、距離画像から３Ｄモデルのジオメトリと表面テクスチャを構築する方法を提供する。より具体的には、距離画像は、非常に際だったテクスチャを含んでいてもよい。この方法は、単一の画像や複数の画像に適用可能である。この方法は、高速でメモリの効率が高く、３次元で詳細に形状を変化させて隠れた部分を修正することが可能な水密で穴のないモデルを提供する。
【００２９】
この発明は、安価なデジタルカメラにより取得された画像から３Ｄモデルを生成するための対話的方法も提供する。この方法は、写真からテクスチャのある距離画像を生成する。テクスチャのある距離画像は、精緻な詳細を持つモデルのジオメトリとテクスチャを生成するための簡単で効果的な方法として、構築過程で使用可能である。
【００３０】
これらの２つの方法は、３Ｄデジタル彫刻システムと組み合わせて、詳細な３Ｄモデルの生成と編集のための強力な新しい設計アプローチを提供することができる
【００３１】
さらに具体的には、２Ｄの投影距離画像から３Ｄの点から３Ｄの表面までの距離が求められる。投影距離と３Ｄの点から３Ｄの表面までの崖の距離は、投影距離画像を使用して求められる。それから、投影距離と崖の距離を組み合わせて３Ｄの点から３Ｄの表面までの距離が求められる。
【００３２】
【発明の実施の形態】
［好ましい実施形態の説明］
投影距離
２次元（２Ｄ）距離画像は、スキャナから物体までの視線距離の２Ｄ格子を提供する。視線距離は、スキャナから物体までの視線光線に沿って計測される。以下の説明では、我々は、距離画像中の各距離値は、垂直投影距離を表すと仮定し、距離はスキャナから物体までスキャナの平面に垂直な光線に沿って計測されると仮定し、この問題の詳細については、本明細書に参照により援用される２００１年７月１７日にGibson他に対して発行された米国特許第６，２６２，７３８号、「Method for estimating volumetric distance maps from 2D depth images」も参照されたい。
【００３３】
走査システムは必ず投影距離を出力するとは限らないが、この形式への変換は簡単である。たとえば、レーザーストライプシステムは、距離画像の各走査線がレーザー源の点から物体までの光線に沿った視線距離をサンプリングするように、レーザー光の平面を形成するようにレーザー光線を「扇状に照射」する。レーザーストライピングシステムのジオメトリと各光線のレーザー源に対する角度が与えられれば、これらの視線距離は投影距離に変換可能で、スキャナ平面に逆にマッピングすることができる。これらのマッピングされた投影距離を規則正しい格子に再サンプリングすることで、必要な投影距離画像が得られる。この変換により、隠れた部分に近いデータがいくらか失われる可能性があるが、損失は通常わずかである。
【００３４】
ユークリッド距離
距離ベースの再構築方法において、Curless等は視線距離を使用するが、Whitakerは投影距離を使用しており、前述の引用を参照されたい。この発明による方法ではユークリッド距離を使用するが、これはユークリッド距離が表面上にない点についての表面に対する向きと、複数の走査を組み合わせるときの表面自体の両方をより正確に表現できるからである。ユークリッド距離を使用することで、適応サンプリング距離フィールド（ＡＤＦ）を高速に生成し、ＡＤＦ内で距離フィールドをより高い効率で圧縮できるので、高解像度モデルの表現が可能になる。
【００３５】
投影距離は、図２に示すようにユークリッド距離と２つの点で大きく異なる。第１に、表面２０１が走査方向２０２に対して角度２０４を持つとき、真の距離値２０３は投影距離値２０２よりも小さくなる。第２に、距離画像は、隠れた表面への距離や走査方向にほぼ平行な表面への距離を表現しない。
【００３６】
そのような表面上では、距離画像中の投影距離は不連続で、投影距離フィールド中に境界が生じ、境界では隣り合うサンプルの中に大きな正の距離と大きな負の距離が存在することになる。投影距離フィールドは、ユークリッド距離フィールドと同じゼロ値の等値面を持つが、投影距離フィールドの勾配は、真のユークリッド距離フィールドの勾配とは異なる。これは、距離フィールドの勾配を使用してゼロ値の等値面に向けて表面を生成する方法では問題となることがある。
【００３７】
さらに、複数の距離画像を組み合わせるとき、異なる視線方向からの投影距離は尺度が異なる。すべての走査での距離を線形に平均しても、結果として得られる組み合わせた投影距離のゼロ値等値面は、物体の面を正確に表現する。しかし、ほとんどの方法は、異なる走査から得られた距離値の、ウィンドウにより選択された、重み付きの、非線形の平均を使用する。その結果、２つの走査が重なる表面では、アーチファクトが生じる。
【００３８】
正確さ以外に、ＡＤＦを使用するときにユークリッド距離が好ましいのには、実際的な理由がある。第１に、表面の近傍の距離フィールドに主に興味がある場合、セルが表面を含んでいないことが保証される場合、セルの細分はＡＤＦの生成中の初期に終了することができる。ユークリッド距離を使用すると、距離値はセルの大きさに比例し、セルの距離値からそのセルが表面を含むかどうかを容易に判定することができる。たとえば、セルの各距離値が同じ符号で、かつ、セルの各距離値の絶対値がセルの対角線の半分よりも大きい場合、セルは表面の外部か内部かのどちらかで、表面とは交差しない。
【００３９】
しかし、投影距離はセルの大きさには比例しない。その代わりに、投影距離は、走査方向に対する表面の角度によってスケーリングされ、隠れ面の近傍では不連続になる。したがって、投影距離を使用すると、セルの細分が早期終了することを利用できなくなり、通常、一桁以上大きい距離の評価がさらに必要になり、ＡＤＦ生成時に一時保存領域が大量に必要になる。ユークリッド距離が好ましい別の理由は、投影距離フィールドを使用すると、隠れ面の近傍の投影距離フィールドでの不連続のために、これらの隠れ面の近傍のセルがＡＤＦの最高レベルにまで強制的に細分されることである。そのため、三色オクツリーの場合と同様にメモリの要求が増加する。
【００４０】
投影距離の補正
図２ａに示したように、平面２０１の近傍の点については、ユークリッド距離２０３、ｄｔ、は、ｃｏｓ（θ）を乗じた投影距離２０２、ｄｐ、に等しく、ここでθ２０４は、走査方向と表面法線との間の角度で、つまりｄｔ＝ｄｐ＊ｃｏｓ（θ）になる。式がＡｘ＋Ｂｙ＋Ｃｚ＋Ｄ＝０の平面と法線（Ａ，Ｂ，Ｃ）２０３が与えられると、点ｐ＝（ｐ．ｘ，ｐ．ｙ，ｐ．ｚ）から平面までのｚ方向に沿った投影距離ｄｐは、
ｄｐ＝ｐ．ｚ−（−ｐ．ｘ＊Ａ／Ｃ−ｐ．ｙ＊Ｂ／Ｃ−Ｄ／Ｃ）で表される。
【００４１】
微分すると、投影距離フィールドの勾配、∇（ｄｐ）は、
∇（ｄｐ）＝（Ａ／Ｃ，Ｂ／Ｃ，１）で、大きさは、
|∇（ｄｐ）|＝（Ａ２＋Ｂ２＋Ｃ２）１／２／Ｃで表される。
【００４２】
したがって、|∇（ｄｐ）|＝１／ｃｏｓ（θ）となるが、これは平面への法線が（Ａ，Ｂ，Ｃ）であるためである。そのため、平面については、ｄｔ＝ｄｐ＊ｃｏｓ（θ）＝ｄｐ／|∇（ｄｐ）|、つまり、我々は、投影距離を投影距離フィールドの局所勾配の量で割ることで、表面の比較的平坦な領域に近い投影距離フィールドを修正することができる。この修正により、滑らかな表面に近いユークリッド距離の良好な近似を得ることができる。
【００４３】
この修正を、規則的にサンプリングされた体積に対して実施することは、単純であるが低速である。そこで、我々は、投影距離フィールドを３Ｄ体積内の各点についてサンプリングして投影距離ボリュームを生成し、それから、たとえば中央差分を使用して計算された局所勾配量で割ることで投影距離をサンプリングされた各点で修正する。
【００４４】
投影距離画像から投影距離を勾配量により修正する体積ディスタンスマップを生成する方法は、本明細書に参照により援用されるFrisken他により２００１年３月１６日に出願された米国特許出願第０９／８０９，６８２号「System and method for correcting range data to 3D models」に記述されている。しかし、その方法はまず物体の距離ボリュームを生成し、距離ボリュームから３Ｄ勾配量を求める。
【００４５】
逆に、本方法では、距離ボリュームは必要ない。代わりに勾配量は、２Ｄ距離画像か、２Ｄ距離画像から直接決定される２Ｄ勾配量修正画像から直接求められる。距離画像に垂直な方向では、物体への投影距離は一定の割合で減少する。したがって、投影距離フィールドの勾配は、距離画像に垂直な光線に沿って一定である。これは、３Ｄ投影距離フィールドの勾配は、距離画像の平面内の２Ｄフィールドによって完全に表現可能ということである。この２Ｄフィールドと関連付けられた３Ｄ投影距離フィールドの勾配量は、各画像の点に対して求めることが可能で、以下のように２Ｄ勾配量修正画像に保存可能である。
【００４６】
距離画像と同じ次元の勾配量修正画像のために保存領域を割り当てる。それから、距離画像内の各画素について、中央差分などの方法を使用して距離画像の局所２Ｄ勾配、（ｄｘ、ｄｙ）を求め、この画素の３Ｄ投影距離の勾配を（ｋｘ＊ｄｘ，ｋｙ＊ｄｙ，１）として求め、ここでｋｘとｋｙは画像の大きさに関連する尺度で、たとえば、ｋｘは距離画像の幅で、ｋｙは距離画像の高さであり、３Ｄ投影距離の勾配量で１を除した勾配量の逆数を求め、勾配量の逆数を勾配量修正画像に保存する。
【００４７】
そのため、投影距離値は、直接距離画像から導き出すことが可能で、勾配量修正画像から補間される値を使用して修正可能である。
【００４８】
崖の近傍の距離の修正
距離値は、隠れ面や走査方向にほぼ平行に延びる表面の近傍の距離画像内の画素の間で不連続になる。距離表面を使用する従来技術の方法は、これらの画素上で三角による連結を実施しないことでこれらの不連続に対応する。しかし、この結果、距離表面や場合によっては結果の３Ｄモデルに、特別に措置したり、独立して対応しなければならい穴が発生する。
【００４９】
図２ｂに示したように、ここでは、これらの不連続部分の近傍のデータを破棄する代わりに、我々は、表面２１１は距離画像の不連続部にまたがって連続していて、距離画像にほぼ垂直に延びて不連続部の各側の画素を結合する崖２１２を形成すると仮定する。このアプローチにより、再構築された表面の穴がなくなり、使用できるデータのない表面の部分について妥当な推定を行うことができる。この方法では、隠れ面に対して正確な距離が得られるとは限らないことに注意しなければならない。しかし、我々は、複数の走査を組み合わせるときには、崖に対して計算された距離の優先度を低くすることで、隠れた部分がよく見える距離画像による距離が崖の距離よりも優先されるようにする。
【００５０】
図３に示すように、３Ｄ対象点（query point）ｐ３０１における３Ｄ表面への距離３０６は以下のように求められる。２Ｄ投影距離画像３０２を補間３１０することで投影距離３０３を求める。投影距離画像は、カメラやグラフィックプロセッサのｚバッファなどの視線距離スキャナにより取得可能である。崖距離３０５を求める。以下で説明するように、崖距離は、崖マップ３０４を補間３２０することで求めることができる。最後に、投影距離３０３と崖距離３０５を組み合わせ３３０て距離３０６を求める。組み合わせ方法３３０では、投影距離３０３と崖距離３０５の短い方を選択することができる。
【００５１】
距離画像内の不連続部分の近傍の画素である崖画素は、前処理手順中に検出しマーキングすることが可能である。しかし、既存の方法を使用してこれらの崖画素から崖距離を計算するのは、依然として時間のかかる作業である。生成時間を減少させるために、我々は、崖距離を使用して３Ｄ距離フィールド内の不連続部を除去することを提案していることを思い出さなければならない。崖画素を空間階層に配置し、高速検索技法を使用して最も近傍の崖画素を見つけても、このアプローチでは依然として、崖に沿って完全なＡＤＦの三色オクツリー細分を単純に求めることに比べて、大幅な改善は見られない。
【００５２】
幸い、３Ｄ崖距離は、生成前に計算可能な注釈付き２Ｄ画像や、崖マップ３０４から推定可能である。図２ｂから、崖マップは、距離画像内の各画素について、表面２１１内の最も近い崖２１２の上部２２１と下部２２２への距離とともに、高さ、つまり崖２１２の上部と下部の投影距離値をコード化する。
【００５３】
図４は、投影距離画像３０２について崖マップ３０４を求める方法４４０を示す。まず、投影距離画像３０２内の各画素について、２つの距離値と２つの崖の高さのための保存領域を割り当てる。崖画素を初期化４１０して、初期化された崖マップ４０１を決定する。各画素の初期崖距離は、可能な限り最大の正の値に設定される。それから、距離画像中の各画素について、その画素の距離値を隣接する画素の距離値と比較して、画素が上部および／または下部の崖画素かどうかを判定する。隣接する距離値の差が所定のしきい値よりも大きい場合、表面に不連続部があると仮定できる。画素が崖の上部または崖の下部の画素の場合、対応する（上部または下部の）崖距離をゼロに設定し、対応する崖高さを画素の距離値に設定する。
【００５４】
隣接する１画素幅の崖を、崖の上部と下部の両方のタグが付けられた画素を非崖画素に設定する、たとえば両方の崖距離を大きい正の値に設定することで単一の複数画素幅の崖４０２に縮小４２０することが可能である。
【００５５】
最後に、崖マップ３０４内のすべての非崖画素について崖距離と崖高さを求める４３０。これは、まず、距離変換、たとえば３×３近傍ユークリッド変換を使用して最も近い崖画素までの符号のない距離を対応する崖高さと共に設定して、次に、崖の外側の画素の崖距離を否定することにより行うことができる。
【００５６】
崖マップ３０４を使用して、対象点３０１から最も近い崖までの崖距離３０５を求めるには、まず、たとえば崖マップ３０４を補間することで、最も近い崖の上部と崖の下部への距離と対応する崖の上部と崖の下部の高さを求める。次に、対象点３０１の距離値を、崖の上部の高さ、および崖の下部の高さと比較して対象点３０１が崖の上部、崖の下部、または崖の表面のどれに最も近いかを判定する。対象点が崖の上部より上の場合、崖距離は、崖の上部への距離として求められる。対象点が崖の下部より下の場合、距離は、崖の下部への距離として求められる。それ以外は、対象点３０１は、崖の表面に最も近く、距離は崖の上部と下部を結合する線への距離として求められる。
【００５７】
ユークリッド距離の推定
図５は、単一距離画像について対象点３０１におけるユークリッド距離３０６を求める手順５４０を示す。投影距離３０３は、投影距離画像３０２から補間３１０される。関連する勾配量５０２は、勾配量修正画像５０１から補間５１０される。投影距離は、勾配量５０２を使用して修正５２０され、修正投影距離５０３が求められる。最も近い崖への距離３０５は、崖マップ３０４を使用して求められる３２０。最後に、修正された投影距離と崖距離の小さい方が選択５３０され、距離３０６が求められる。
【００５８】
複数の距離画像の組み合わせ
複数の走査から得られた距離は、表面の再構築に使用される方法に従って、いくつかのやり方で組み合わせることができる。たとえば、Curless等、Hilton等、Wheeler等、Whitaker等により記述された任意の加重平均方式を使用可能で、前述の引用を参照されたい。最良の組み合わせ方法は、距離スキャナの雑音特性と再構築方法により適用されるそれ以降の処理により決定される。
【００５９】
たとえば、単純な組み合わせ方式は、複数の走査から「最良」の距離値を選択するが、「最良」とは、短い距離が長い距離よりも優先され、小さい勾配量を持つ距離が大きい勾配量を持つ距離よりも優先され、崖距離よりも修正された投影距離が優先されることを意味する。
【００６０】
適応サンプリング距離フィールドの生成
図６は、ユークリッド距離フィールドのＡＤＦを生成するための手順を示す。まず、距離画像６０１が取得６１０され、投影距離画像６０２に変換６２０される。これらの投影距離画像は、前処理されて、勾配量修正画像５０１が求め６３０られ、崖マップ３０４が求め４４０られる。
【００６１】
ＡＤＦのルートセルから開始して、ＡＤＦジェネレータ６４０は、誤差ベースの再分割判定を使用して、セル内のフィールドがセルの８つの距離値で十分に記述されるまで再起的にＡＤＦ６０６のセルを細分する。各ＡＤＦ対象点６０３での距離は、各距離画像について評価５４０され、点ｐでの距離６０５を求めるために組み合わされる６５０各距離画像６０４についての距離が作成される。この用途のために、面の境界となるセルに細分を限定して、ＡＤＦ階層の最小レベルを超えた外部と内部のセルの細分を行わないようにする面を中心としたＡＤＦが使用される。
【００６２】
また、我々は、前述のように、以下で説明する対話的方法により作成されたテクスチャ付き距離画像からジオメトリを生成する方法を使用する。
写真からのテクスチャ付き距離画像の生成
写真からの詳細ジオメトリテクスチャの抽出
【００６３】
図７に示すように、我々は、明示的な奥行き情報のない２つの２Ｄ画像である一対の写真から、距離画像を生成するための対話的方法も提供する。しかし、従来技術で通常実施されるように、互いにオフセットされた一対のステレオ画像を使用する代わりに、使用する画像は、驚くべきことに、実質的に同一の光軸に揃えられる。つまり、２つの写真は実質的に同一の視点から撮影される。
【００６４】
第１の画像７０１は、周辺光の下で情景１０１をカメラ８００で撮影したものである。カメラ８００は、以下で詳細に説明する。カメラ８００を同一位置で使用して、第２の画像７０２が、カメラ８００のレンズと実質的に同一の位置に配置されたフラッシュなどの指向性照明を使用して撮影される。
【００６５】
光度補償画像が１対の写真７０１と７０２から得られる７１０。我々は、この画像を、テクスチャ付き距離画像７０３と呼ぶ。ユーザーは、２Ｄ画像エディタ７２１を使用して、テクスチャ付き画像７０２を任意に編集し強調７２０することができる。それから、３Ｄモデル７０４が、前述の方法を使用して、この強調されたテクスチャ付き距離画像７０３から生成７３０される。所要の結果が達成されるまで最後の２つの手順を繰り返すことができる。
【００６６】
指向性照明を使用した光度変動の補償
写真には、物体や情景のジオメトリとテクスチャに関する多量の情報が含まれている。たとえば、石壁の写真では、石の間の割れ目は影により暗くなり、石の突起部分は明るく見える。これは、情景１０１から取得した第１の画像７０１が周辺光により照明されているときには一般的な現象である。ハイライトは、表面の凸部を明るくし、影は表面の凹部を暗くする傾向がある。表面の明るさと暗さの強度の変動は、この効果を支配することが多い。
【００６７】
しかし、直接光により撮影された写真では、写真の凹凸部分は、はるかに均一に照明される傾向がある。レンズとフラッシュは、実質的に同一位置に配置されるので、直接照明条件下で取得された画像７０２にはほとんど影はない。従来技術のステレオ対の画像とは対照的に、第２の画像は、実質的に同一の視点から取得される。
【００６８】
第２の写真７０２は、自然に照明された第１の写真７０１の影により得られる奥行きの手がかりなしに情景の光度の変動を記録する。これは、フラッシュ画像７０２を使用して、周辺光で照明された写真７０１内の光度の変動を補償７１０することを意味する。
【００６９】
したがって、我々は、周辺光で照明された画像７０１の各画素の輝度を、指向性光で照明された画像７０２内の対応する画素の輝度で除算することで光度の変動を補償７１０して、光度補償済み画像７０３を得る。我々は、浮動小数点演算を使用して光度補償を実施して打ち切りアーチファクトの発生を回避する。光度補償済み画像では、光度の変動が除去されるが、奥行きの手がかりは保持される。実際に、我々は、光度補償済み画像を近似テクスチャ付き距離画像として使用して、情景１０１のモデル７０４の３Ｄジオメトリを生成７４０する。
【００７０】
さまざまなカメラとさまざまな照明で実験を行い、我々は以下の観察結果を得ている。第１に、我々は、「周辺光」が、屋内屋外の照明、日当たりのよいおよび曇った条件、影または日光中で撮影された画像など広い範囲の照明条件を包含することがわかっている。必要なことは、情景内の影が望ましい詳細ジオメトリを強調し、直接光が背景照明内で優勢になるようにすること、特に短い露出のときにそうすることだけである。
【００７１】
任意の数の露出とフィルムの設定が使用可能であるが、我々は、カメラ８００の既定の自動露出設定を使用して撮影された写真が通常最良の結果を達成することがわかっている。可能な限り最高の解像度の画像を使用したとき、つまり画像圧縮を無効にしたときに最良の結果が得られる。
【００７２】
カメラ８００が三脚７１１上に取り付けられると、周辺光による画像とフラッシュによる画像の撮影の間に遅延が存在する可能性があり、２つの画像は、依然として実質的に揃えて配置されている。その代わりに、カメラが手に保持されていても、カメラが周辺光による画像とフラッシュによる画像を短い間隔で連続して撮影し、カメラの移動を無視できるようにすることが可能である。ビデオカメラを使用して画像の対のシーケンスを撮影し、光度補償済み画像のシーケンスを生成することも可能である。これにより、アニメーションの作成のための興味深い新規の源を提供することができる。たとえば、ビデオカメラが１秒当たり６０フレームを撮影すると、これにより、３Ｄテクスチャ付き距離画像、つまり３Ｄビデオが生成される。これは、ほとんどのアニメーションに適している。
【００７３】
我々は、２つのデジタルカメラ、チャネル解像度あたり８ビットの妥当な品質の消費者向けカメラのニコンＣｏｏｌｐｉｘ７７５と、チャネル解像度あたり１２ビットのハイエンドのプロ向けカメラのキャノンＤ３０を比較した。我々は、どちらのカメラでも非常に良好な結果を得ることができ、低解像度カメラにより得られるテクスチャ付き距離画像でほとんどの用途に十分であることがわかっている。
【００７４】
２Ｄエディタを使用したテクスチャ付き距離画像の強調
対話的方法では、テクスチャ付き距離画像つまり３Ｄモデル７０３を、Ａｄｏｂｅ  Ｐｈｏｔｏｓｈｏｐなどの２Ｄ画像エディタ７２１を使用して強調し、特徴を明確にし強調することができる。たとえば、フラッシュ画像７０２内の影がある場所に発生した白い画素は除去可能である。
【００７５】
テクスチャ付き距離画像７０３は、２Ｄ画像エディタ７２１により、画像を有向勾配フィルタと組み合わせて、テクスチャ付き距離画像内の選択された特徴の形状や曲率を強調したり、標高マップ、高さフィールド、距離画像などの画像と組み合わせて３Ｄモデル７０４のグローバル形状を提供したり、手続きにより生成された画像などの他の画像と組み合わせて３Ｄモデルに合成テクスチャを追加して強調することもできる。
【００７６】
さらに、テクスチャ付き距離画像７０３は、距離値に局所的に影響する２Ｄ画像ブラシを使用して２Ｄ画像エディタで強調することもできる。たとえば、勾配ベースのブラシを使用して、３Ｄモデルの局所領域を高くしたり低くしたり、手続きベースのテクスチャを持つブラシを使用して局所テクスチャの詳細を追加したり、テクスチャ付き距離画像や標高マップなどの距離画像から派生したブラシを使用して局所的な特徴を追加することができる。たとえば、山の標高データを示す画素値を持つブラシを使用して、テクスチャ付き距離画像上でその山ブラシを大きく動かすことで連山を３Ｄモデルに追加することができる。
【００７７】
テクスチャ付き距離画像７０２を強調するのは、画像編集用に洗練されたツールが使用可能なため素早く簡単である。この編集過程により、前述の方法を使用して３Ｄモデル７０４に変換７３０可能な強調済みテクスチャ付き距離画像が生成される。変換には数秒しかかからず、設計に効果的なフィードバックループを提供する。
【００７８】
最終的な３Ｄ編集
前述の対話的編集の結果に満足したときは、我々は、それから３次元でＡＤＦ彫刻システムを使用してモデル７０４を彫刻７４０して、２Ｄでは編集不可能な特徴形状、たとえば、深い凹部や大きな凸部などを編集することができる。
【００７９】
テクスチャ付き距離画像を取得する３Ｄカメラ
図８は、カメラ８００を非常に詳細に示している。カメラ８００は、単一レンズ８０１、レンズ８０１と実質的に同一位置に配置されたフラッシュ８０２を有する最初の画像８１１は、周辺光８０３を使用して取得され、第２の画像８１２は指向性光８０４を発生するフラッシュ８０２を使用して取得される。画像を取得する順番は重要ではない。画像８１１と８１２は、メモリ８３０に保存される。プロセッサ８２０は、上述のように光度補償を実施して、テクスチャ付き距離画像８１３を生成する。光度補償は、周辺光で照明された画像811の各画素の輝度を、指向性光で照明された画像812内の対応する画素の輝度で除算することで実施され、光度補償済み画像81３が得られる。それから、テクスチャ付き距離画像８１３が、ＵＳＢポートなどのインターフェイス８４０を介して他のシステムにエクスポートされる。カメラは、画像のシーケンスを撮影して３Ｄビデオ８５０を作成できることには注意しなければならない。
【００８０】
【発明の効果】
我々は、安価なデジタルカメラを使用して３Ｄジオメトリとテクスチャを取得する対話的方法を説明した。この方法は、２Ｄ写真から精緻な詳細を持つジオメトリとテクスチャの生成に使用可能なテクスチャ付き３Ｄ距離画像を生成する。我々は、３Ｄジオメトリを距離画像から再構築する方法も説明した。これら２つの技法を組み合わせることで、費用効果が高く、実用的で、わかりやすく、堅牢で、効率の高い詳細な３Ｄモデルを生成する手段が提供される。
【図面の簡単な説明】
【図１】  ２Ｄ距離データを３Ｄモデルに変換するための従来技術の方法の流れ図である。
【図２ａ】  投影距離とユークリッド距離の図である。
【図２ｂ】  崖のある非連続な表面の図である。
【図３】  この発明による投影距離と崖への距離を使用して距離画像から表面への距離を求めるための方法の流れ図である。
【図４】  この発明による投影距離画像から崖マップを生成する方法の流れ図である。
【図５】  この発明による修正済み投影距離画像、崖への距離、勾配量画像を使用して距離画像から表面への距離を求める方法の流れ図である。
【図６】  この発明による距離画像から情景の適応サンプリングされた距離フィールドを生成する方法の流れ図である。
【図７】  この発明によるテクスチャ付き距離画像を生成する流れ図である。
【図８】  この発明によるテクスチャ付き距離画像を取得するカメラの概要である。
【図１】
0004428936.tif 000002
【図２ａ】
0004428936.tif 000003
【図２ｂ】
0004428936.tif 000004
【図３】
0004428936.tif 000005
【図４】
0004428936.tif 000006
【図５】
0004428936.tif 000007
【図６】
0004428936.tif 000008
【図７】
0004428936.tif 000009
【図８】
0004428936.tif 000010