(57)【要約】写真データと写真測量データから、シーンのデジタル３Ｄモデルを自動的又は半自動的に作成する方法は、推定解として初期ラフモデルを定義する段階を含む。リバースレンダリングステップは、誤差関数の導関数を正確に計算するため自動微分技術を利用する２次解法を含む。本方法の実施形態において、少なくとも１台のカメラは作成されるシーン内に配置され、このカメラからの写真データは解法プロセスで使用される。
2006507585.tif 000002
【特許請求の範囲】
【請求項１】
リバースレンダリング関数を使用して３次元シーンのパラメータを決定する方法であって、
複数の３次元シーンの写真画像からなる画像データを受信する段階と、
各々が前記複数の写真画像の中の少なくとも２つの写真画像に表れる複数の対応する特徴を指示するユーザ入力を受信する段階と、
前記３次元シーンの３次元座標と、前記複数の対応する特徴の対応する２次元座標との間の相関関係を定義する、リバースレンダリング関数の誤差関数を決定する段階と、
前記誤差関数を最小化して、前記誤差関数の最小値（ｇｌｏｂａｌ  ｍｉｎｉｍｕｍ）に対応する解を決定する段階と、
を含み、前記解を決定する段階が、自動微分を使って前記誤差関数の少なくとも一次導関数を計算し、それによって、前記推定値が解に収束するまで前記誤差関数の連続的な反復に対する中間推定解を計算する段階を含むことを特徴とする方法。
【請求項２】
前記決定段階は、カメラ位置、カメラ方向、焦点距離、絞りサイズ、レンズの歪み、焦点面の歪みから成るグループから選択されたリバースレンダリング・パラメータを含む前記誤差関数を決定する段階を更に含むことを特徴とする請求項１の方法。
【請求項３】
前記決定段階は、前記３次元シーンの少なくとも１台のカメラ位置を含むリバースレンダリング・パラメータを含む誤差関数を決定する段階を更に含むことを特徴とする請求項１の方法。
【請求項４】
少なくとも初期推定解の一部を含む初期シーングラフを受信する段階を更に含むことを特徴とする請求項１の方法。
【請求項５】
前記初期シーングラフを受信する段階は、親オブジェクトと子オブジェクトとの間の相関関係を定義する少なくとも１つのトランスフォームを含む前記初期シーングラフを受信する段階を更に含むことを特徴とする請求項４の方法。
【請求項６】
前記最小化段階は、前記誤差関数の正確なヘシアンを計算する段階を更に含むことを特徴とする請求項１の方法。
【請求項７】
初期推定解として、前記複数の写真画像に関する、前記複数の対応する特徴及びカメラパラメータの、少なくとも選択された３次元座標を初期化する段階を更に含むことを特徴とする請求項１の方法。
【請求項８】
前記解に一致するシーンに関する、結果として得られたシーングラフを定義する段階を更に含むことを特徴とする請求項１の方法。
【請求項９】
前記決定段階は、ユーザが選択したリバースレンダリング関数のパラメータ間のユーザが選択した微分可能な相関関係によって更に定義される前記誤差関数を決定する段階を更に含むことを特徴とする請求項１の方法。
【請求項１０】
前記決定段階は、映画シーケンスのフレーム間のマッチムービングの相関関係を解くために、アニメーションパラメータによって更に定義される前記誤差関数を決定する段階を更に含むことを特徴とする請求項１の方法。
【請求項１１】
前記受信段階は、時間シーケンスを表す複数の写真画像を受信する段階を更に含み、前記決定段階は、映画シーケンスのフレーム間のマッチムービングの相関関係を解くために、時間パラメータによって更に定義される前記誤差関数を決定する段階を更に含み、前記最小化段階は、前記フレーム全体にわたって同時に前記誤差関数を最小化する段階を更に含むことを特徴とする請求項１の方法。
【請求項１２】
前記画像データの受信段階は、デジタルカメラからのデジタル画像から成る前記写真画像を受信する段階を含むことを特徴とする請求項１の方法。
【請求項１３】
リバースレンダリング関数を使用して３次元シーンのパラメータを決定する方法であって、
少なくとも１つが３次元シーンの中に配置されたカメラを使って取り込まれた、複数の２次元画像を受信する段階と、
３次元シーンの３次元座標と、２次元画像の中の複数の対応する特徴の対応する２次元座標との間の相関関係を定義する、リバースレンダリング関数の誤差関数を決定する段階と、
前記誤差関数を最小化して、前記誤差関数の最小値に対応する解を決定する段階と、
を含み、前記解を決定する段階が、それによって、前記推定解が解に収束するまで前記誤差関数の連続的な反復に対する中間推定解を計算する段階を含むことを特徴とする方法。
【請求項１４】
推定シーンパラメータから成る初期シーングラフを受信する段階と、
前記推定シーンパラメータに基づいて前記誤差関数の初期推定解を定義する段階と、
を含むことを特徴とする請求項１３の方法。
【請求項１５】
前記初期シーングラフの受信段階は、親オブジェクトと子オブジェクトとの間の相関関係を定義する少なくとも１つのトランスフォームを含む前記シーンの前記推定パラメータを受信する段階を更に含むことを特徴とする請求項１４の方法。
【請求項１６】
前記決定段階は、ユーザが選択したパラメータ間のユーザが選択した微分可能な相関関係によって更に定義された前記誤差関数を決定する段階を更に含むことを特徴とする請求項１３の方法。
【請求項１７】
前記決定段階は、映画シーケンスのフレーム間のマッチムービングの相関関係を解くために、アニメーションパラメータによって更に定義された前記誤差関数を決定する段階を更に含むことを特徴とする請求項１３の方法。
【請求項１８】
前記最小化段階は、自動微分を使ってヘシアン行列を計算し、それによってニュートン法に基づく前記最小化段階を誘導する段階を更に含むことを特徴とする請求項１３の方法。
【請求項１９】
写真測量を使用して３次元シーンのデジタルモデルを定義するシステムであって、前記システムはメモリを有するコンピュータを備え、前記メモリは、
３次元シーンの複数の写真画像からなる画像データを受信する段階と、
各々が複数の写真画像の中の少なくとも２つの写真画像に表れる複数の対応する特徴を指示するユーザ入力を受信する段階と、
前記３次元シーンの３次元座標と、前記複数の対応する特徴の対応する２次元座標との間の相関関係を定義する、リバースレンダリング関数の誤差関数を決定する段階と、
前記誤差関数を最小化して、前記誤差関数の最小値（ｇｌｏｂａｌ  ｍｉｎｉｍｕｍ）に対応する解を決定する段階と、
を含み、前記解を決定する段階が、自動微分を使って前記誤差関数の少なくとも一次導関数を計算し、それによって、前記推定値が解に収束するまで前記誤差関数の連続的な反復に対する中間推定解を計算する段階を含むプログラム命令を格納することを特徴とするシステム。
【請求項２０】
前記プログラム命令は、少なくとも初期推定解の一部を含む初期シーングラフを受信する段階を更に含むことを特徴とする請求項１９のシステム。
【請求項２１】
前記プログラム命令は、ユーザが選択したパラメータ間のユーザが選択した微分可能な相関関係によって更に定義された前記誤差関数を決定する命令を更に備えることを特徴とする請求項１９のシステム。
【請求項２２】
前記プログラム命令は、映画シーケンスのフレーム間のマッチムービングの相関関係を解くために、アニメーションパラメータによって更に定義された前記誤差関数を決定する命令を更に備えることを特徴とする請求項１９のシステム。
【請求項２３】
前記プログラム命令は、自動微分を使ってヘシアン行列を計算することによって前記誤差関数を最小化し、それによってニュートン法に基づいて前記反復段階を誘導する命令を更に備えることを特徴とする請求項２０のシステム。
【請求項２４】
前記プログラム命令は、時間シーケンスを表す前記複数の写真画像を受信する命令を更に備え、前記決定段階は、映画シーケンスのフレーム間のマッチムービングの相関関係を解くために時間パラメータによって更に定義された前記誤差関数を決定する段階を更に含み、前記最小化段階は、前記フレーム全体にわたって前記誤差関数を同時に最小化する段階を更に含むことを特徴とする請求項２０のシステム。
【請求項２５】
前記プログラム命令は、前記３次元シーン内の未知の場所におけるカメラからの少なくとも１つの画像からなる前記画像データを受信する命令を更に備えることを特徴とする請求項１９のシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、デジタルイメージング分野での方法、より詳細には、デジタルモデリングのための写真測量及びマッチムービング等のリバースレンダリング法に関する。
【背景技術】
【０００２】
近年、例えばテレビや映画、コンピュータゲーム、及びエンジニアリングモデル作成など、ほとんど全ての動画の用途において、動画を生成及び／又は修正するためにコンピュータがますます使用されるようになっている。今後は、デジタルモデリングの利用がより一層広がると思われる。リバースレンダリング法、つまり、どのジオメトリ、動き、ライティング、カメラ、及びその他の入力が所望の画像又は画像シーケンスになるかを決定する方法は、さまざまな用途のためのデジタルモデルの開発において重要な役割を演じるであろう。
【０００３】
例えば、デジタルモデリングで生じる問題の１つは、写真測量を使用して２次元（「２Ｄ」）写真データから３次元（「３Ｄ」）モデルを作成することに関連する。マッチムービング法は、写真測量を画像シーケンス全体にわたる動きのモデリングに拡張する。現在の写真測量法及びマッチムービング法は、柔軟な方法で実行することが困難である。その結果として、一般的に従来技術のアプリケーションは、複雑性及びプログラミング要件を処理しやすいレベルに維持するため、受け取ることができる入力データに望ましくない制約を設けている。例えば、多数の従来技術の方法では、ユーザは、シーングラフのパラメータ間の相関関係を定義する任意の式を指定できない。さらに、従来技術の方法では、カメラをシーングラフの任意の場所に配置できない。また、現行の方法では、計算ループでロックしてしまうか又は間違った解にたどりつく場合があるので、利用可能な２Ｄデータから有効な３Ｄモデルを全く作成できない。従って、２Ｄ写真データから３Ｄデジタルモデルを作成するための、従来技術の写真測量技術の制約をなくす改善された方法を提供することが望ましい。
【０００４】
写真測量、マッチムービング、及びその他のリバースレンダリング法は、微分法の応用と見なすことができる。微分法には、デジタル映画制作において多数のアプリケーションが存在する。例えば、そのアプリケーションとしては、レンダリング（アンチエイリアシング、モーションブラーイング）、アニメーション（インバースキネマティクス、マッチムービング）、モデリング（標準判定、写真測量）、シミュレーション（運動方程式のインプリシット積分）、及びその他の多岐にわたるアプリケーション（レンズ及び色較正、オプティカルフローなど）がある。従来、微分法は、手作業の解析で式を導き出してこれらの式をソフトウェアコードの式として実行することよる、後処理による、又は差分を使用することによる等の、関数の導関数及び導関数の近似式を計算するソフトウェアを作成することで、この種の問題に適用されている。
【０００５】
これらの従来の方法の各々は、さまざまな制約を受けている。手書きの微分コードは面倒であり間違いの元であり、一般にコードの修正は困難である。微分式のコードを自動的に生成するソースコードの後処理は、プログラミングの過程を複雑にしてコーディングスタイルを制約する。差分δを使って微分の近似を計算する差分法は、十分正確でない場合がある。これらの方法については、適切なδの値を選択することに関連していくつかの問題が存在する。値が大きすぎると、近似の成果があがらない。値が小さすぎると、結果は丸め誤差になる場合がある。
【０００６】
しかしながら、自動微分という別の技術も存在する。微分法が広範囲に利用されているにもかかわらず、デジタルイメージング技術での自動微分は、参考文献がいくつか点在するがよく知られていない。さらに、写真測量及びその他の用途のためのデジタルイメージングの種々の微分法の問題の解決手法に、計算速度を高くする及び／又はプログラミング費用を低減するような方法で、自動微分を適用することが望ましい。
【発明の開示】
【課題を解決するための手段】
【０００７】
本発明は、従来技術の制約をなくす改善されたリバースレンダリング法に関する。さらに本発明は、写真測量問題点及び微分法を使用する同様の問題を、汎用のソフトウェアコードを使って解く方法を提供する。本発明による方法は、最近、長編映画の制作に適用されており、デジタルイメージング関連の用途に容易に拡張することができる。
【０００８】
本発明による方法の例示的なステップを以下に要約する。最初に、シーンの画像（スチール写真画像、ビデオ、又は映画を含む）を複数のカメラ位置から撮る。画像はデジタル形式で供給され、この方法の後続のステップでアクセスできるようにデータベースに保存する。カメラはシーン内に置くことができる。カメラの位置、焦点距離、及び方向は、後で使うために書き留めることができるが、この種の情報は非常に正確である必要はない。ユーザはカメラデータを収集して代表的な画像を調べて、シーンの最初の印象を得ることができる。
【０００９】
随意的に、ユーザはシーンの大まかな３次元モデルを初期推定値として作成できる。ＭａｙａＴＭ等の任意の適切なモデリングソフトウェアを使用することができる。あるいは、解法プロセスの開始推定値の定義に適切な他の任意の方法を使用することができる。これにより、解法プロセスを加速すること及び／又は間違った解を防止することができる。シーン内のモデル化オブジェクトの間の相関関係は、シーングラフ内にトランスフォームを介在させて定義することができる。
【００１０】
シーングラフは、選択した可視オブジェクト、及び少なくともシーン内に配置されたカメラに関する既知のデータデータを含む。また、写真と一致するシーングラフ内のノード間の所望の任意のトランスフォームは、シーングラフの一部として定義することができる。シーン内の全てのオブジェクトをシーングラフに含める必要はなく、全てのトランスフォームを定義する必要もない。シーングラフは、特に、写真の特性からその後の写真測量ステップで正しい解を得ることが難しい場合、例えば、オブジェクトの形状として複数の可能性が明白で、その全てが写真に適合する場合に有用である。３Ｄシーンのシーングラフを作成するソフトウェアツールは、本技術分野では公知である。
【００１１】
また、ユーザは、写真測量ソルバの入力として使用される画像を指定して、指定した画像の対応するポイント又はその他の特徴点を特定する必要がある。ユーザが関連する各画像上の共通ポイントを指定することをサポートするため、ユーザインタフェースを設けることができる。指定した画像、画像上の特定した対応ポイント、シーングラフ、及び任意の関連する３Ｄモデルは、写真測量ソルバへの入力として指定できる。シーングラフ又はモデル化オブジェクトで定義されない初期情報は、任意の補間値又は推定値に最適な方法で定義できる。初期の視覚座標とカメラパラメータは、最小二乗法関数及び／又は他の最適な誤差関数等の、誤差関数のベースラインを表す。
【００１２】
次に、写真で特定した対応ポイント及び／又は他の選択ポイント又は特徴を使用して、シーンの初期推定値（ジオメトリパラメータとカメラパラメータの両方を含む）と、カメラパラメータに基づいて選択したポイントを写真に投影することで計算したシーンとの間の差分の量、つまり誤差量を決定するために、写真測量の原理を適用することができる。例えば、ポイント「Ａ１」は、定義済み座標系の実際の空間座標ｕ１をもつことができる。対応するポイント「Ａ２」は、Ａ１の推定位置を表す座標ｕ２をもつことができる。推定ポイントＡ２は、各々の写真とそれに対応するカメラパラメータから決定されるので、写真平面内の推定ポイントＡ１を通過する光線の交差に基づく。差分ｅ＝ｕ１−ｕ２は、ポイントＡ１の誤差である。これを複数のポイントで反復して、最小二乗誤差ｅを対象の未知の全パラメータの関数として定義する。誤差を定義する技術は本技術分野では公知である。
【００１３】
誤差関数は、任意の適切な誤差最小化法を使って最小化することができる。一般に最小化ソフトウェアは、誤差の２乗（又は「信頼性の高い」方法では時に２乗の代替値）の合計を計算し、次に、処理を反復して誤差を最小化する解を見出すことを試行する。誤差関数を最小化することによってシーンの３次元ジオメトリを定義するのに使用される光線「バンドル」を調整する反復処理は、当業者には「バンドル調整」と呼ばれる場合もある。
【００１４】
本発明の方法では、ユーザがシーングラフを作成する場合、一部のパラメータを写真測量ツールが解くときの必須パラメータとして記録することができる。例えば、この種のパラメータとしてカメラの焦点距離、オブジェクトの相対倍率及び回転角を含むことができる。他のパラメータは、バンドル調整処理全体にわたって一定値として設定できる。一般に、誤差測度ｅは未知パラメータの関数として変化し、特定のパラメータ値の組は誤差を最小化することになる。
【００１５】
本発明では、任意の式を使って、１つ又はそれ以上の未知パラメータを、１つ又はそれ以上の別の未知パラメータに関連付けることができる。例えば、「ａ」と「ｂ」がシーン内のそれぞれのオブジェクトの倍率を表し、第１のオブジェクトが第２のオブジェクトの２倍大きいとすれば、それは「ａ＝２ｂ」という式で表現することができる。これらの別の相関関係は、自由に誤差関数に組み込むことができる。従来技術のバンドル調整法とは異なり、この種の変更点は自由に誤差関数に組み込むことができる。
【００１６】
バンドル調整は、誤差関数の一次導関数（「ヤコビ」）と二次導関数（「ヘシアン」）の両方を計算する二次ニュートン法を使用して進められる。これに関連して二次誤差の最小化については、例えば、Ｔｒｉｇｇｓ他著の「Ｂｕｎｄｌｅ  ａｄｊｕｓｔｍｅｎｔ−ａ  Ｍｏｄｅｒｎ  Ｓｙｎｔｈｅｓｉｓ」（２０００年）に説明されている。しかしながら、従来技術の方法は、ガウス・ニュートン近似を利用しており二次導関数を完全には計算しない。昔から二次導関数の正確な計算は複雑な計算と考えられており、ヤコビベースのレーベンベルク・マルクワルト法等の修正ニュートン法を使用してこの複雑さを回避している。
【００１７】
しかしながら、本発明によれば、誤差関数の一次導関数（ヤコビ）と二次導関数（ヘシアン）の両方を、自動微分の技術を使って正確に計算することができる。自動微分の原理と用途は、例えば、アルゴンヌ国立研究所、数学コンピュータ科学部門に属するＡｎｄｒｅａｓ  Ｇｒｉｅｗａｎｋ著の「Ｏｎ  Ａｕｔｏｍａｔｉｃ  Ｄｉｆｆｅｒｅｎｔｉａｔｉｏｎ」（プレプリントＡＮＬ／ＭＣＳ−Ｐ１０−１０８８、１９８８年１１月）等の他の文献で公知であり、この開示内容は引用によって本明細書に組み込まれている。自動微分の技術は、当業者であれば本明細書の開示又は他の自動微分に関する参考文献に基づいて、ヤコビ行列及びヘシアン行列の計算を行うために適合させることができる。また、自動微分は、ヘシアンを完全に計算せずにヤコビを計算するために使用できる。
【００１８】
従って、誤差関数の解は、新しい機能を比較的効率的にプログラミング、修正、追加するソフトウェアを使用しながら、従来の方法を使用するよりもはるかに高速に得ることができる。逆に、従来技術の写真測量法のプログラミングは比較的費用と時間がかかり、修正が困難である。ニュートン法の完全な利点は、導関数の計算を高速で実現しながら、高速に誤差最小値に収束させて実現することができる。好都合には、本発明の解法を使用すると、１つ又はそれ以上のカメラをシーングラフ内の任意の場所に配置しても何の問題も生じない。従って、この利点により、写真測量用の写真画像の収集がはるかに容易になり、これまで画像から適切に再構成することが困難又は不可能だったシーンに写真測量法を適用できるようになる。逆に、従来技術の写真測量法は、再構成されるシーン内へのカメラの配置に対して、そのような配置がそもそも許される範囲において柔軟性が全くない。
【００１９】
従来技術のバンドル調整法とは異なり、汎用プログラミングスキームに実装されている自動微分は、誤差関数の一次及び／又は二次導関数を正確に計算し、結果的にバンドル調整を解答に導くために使用されることが望ましい。さらに、バンドル調整はシーングラフに含まれる部分情報に導かれており、それによって解法にかかる時間が低減し、より正確な結果が保証される。追加的な利点として、本発明によるアルゴリズムは、従来のヤコビベースのレーベンベルク・マルクワルト法及び代数的導関数法よりもソースコードに実装することが非常に簡単である。これらの利点に加えて、本発明による自動微分の使用は、任意のほとんどの初期シーングラフに適応する柔軟性をもたらす。これは、任意の特定の方法で初期シーングラフを定義してシーンを作成することから当事者を解放するので、主要な利点である。また、補正及び変更にも容易に適応する。
【００２０】
本発明がもたらす柔軟性の一例として、シーングラフの任意のノードは、ユーザが入力した数式によって任意の他のノードと結合することができる。任意のほとんどの式を使用できる。例えば、オブジェクトの高さを任意の他のオブジェクトのスカラ倍として指定することができる。さらに、例えば、２台のカメラの焦点距離を等しくすること、又は関連付けることができる。数学的に表現可能な任意のほとんどの所望のノード間の相関関係は、シーングラフの一部として入力することができる。普通ではない相関関係、例えば、オブジェクトのサイズと、２つの別のオブジェクトの間の角度との間の相関関係ですら含むことができる。
【００２１】
本発明の別の利点は、カメラの処理（ｔｒｅａｔｍｅｎｔ）である。シーングラフでは、カメラデータは、可視オブジェクトのデータと同様にノードで表す。カメラは、他のオブジェクトの相関関係と同様にシーングラフ内に置くことができる。同時に、本発明による解法アルゴリズムは、シーンジオメトリ及びカメラポーズを同時に計算するように構成される。このアプローチによれば、従来技術の方法とは異なり、シーン内でカメラを自由に配置することができる。これに関連して「自由な配置」とは、定義済み解法アルゴリズムの制約なしに、カメラをシーン内の任意の所望の場所に配置できるという意味である。例えば、第１のカメラを自動車が通り過ぎる高速道路に向け、第２のカメラを自動車に搭載することができる。特に、第２のカメラは、実際のシーンオブジェクトであり解法の対象である自動車に搭載することができる。このことは、カメラ位置又は方向が解法の対象であるジオメトリに依存する状況においては非常に好都合である。例えば、カメラは、シーン外部の上空飛行や見晴らしの良い高所の必要性を取り除くために、シーン内の高さが不明のビルの屋上に配置することができる。
【００２２】
本発明の実施形態では、写真測量により再構成されるシーンは、一種の非循環有向グラフ（ＤＡＧ）であるシーングラフとして表わされる。一般にシーングラフは、ポストプロダクション業界用の写真測量と共に使用しない。その代わりに、従来技術の写真測量法では、通常、シーンは相関関係のないポイントのコレクションにより表わされる。シーングラフとは異なり、親／子関係やトランスフォームは定義されない。写真測量解法の原型として、部分的に定義された情報を含む初期シーングラフを使用することは公知であったが、基本的に制約されない方法で自由にトランスフォームを定義する機能は公知ではない。ユーザが柔軟に定義したこれらの部分的なトランスフォーム相関関係を使用することで、非常に正確な再構成及び少ない画像を使った再構成が可能になる。
【００２３】
本発明は静的な写真測量に制限されないことを理解されたい。時間座標を追加することで、本発明は、本技術分野で理解されている原理に基づいて、シーン内のカメラの動きやオブジェクトの動きを考慮するように適合させることが簡単である。例えば、５００フレームのフィルムのシーケンスは、５００の独立した画像として処理でき、次に、それぞれを通常の方法で解くことができる。いくつかのパラメータはフレームによって変化するが（例えば移動カメラの位置）、他のパラメータ（例えば家の高さ）は一定のままとすることができる。従って、本発明は、マッチムービングの問題を解決するのに容易に使用できる。
【００２４】
当業者であれば、本発明の好ましい実施形態に関する以下の詳細な説明を検討することにより、本発明による方法、並びに追加的な利点及びその目的を完全に理解できるであろう。
【発明を実施するための最良の形態】
【００２５】
本発明には、従来技術の制約をなくす複数の異なる態様があると見なすことができる。例えば、１つの態様において、本発明は、バンドル調整問題、及び微分法を使用する類似する問題を、自動微分の汎用コード化ソフトウェアを使用して解く方法を含む。別の態様として、本発明は、自動微分の利点を利用するために設計された、改良された写真測量法を含む。以下の詳細な説明では、まず自動微分をデジタルイメージングの微分法の問題へ適用するための解析的基準を説明する。次に、汎用プログラミングアプローチを使った自動微分のアプリケーションを第２のセクションで説明する。第３のセクションでは、本明細書で開示した自動微分と汎用プログラミングを利用した例示的な写真測量処理を説明する。
【００２６】
Ｉ．自動微分
本発明は、新しいタイプの導入及び演算子オーバーロードをサポートするＣ＋＋等のプログラミング言語を使用して、関数の導関数を計算する方法を提供する。この方法は、微分法について専門知識を必要とすることなくプログラミングが比較的容易であり、ソースコードの後処理を必要とせず、差分法より効率的かつ正確である。この方法は、以下に説明するように自動微分を数学的に利用する。
【００２７】
関数ｆの導関数は、ｆ’（ｘ）又はｄｆ／ｄｘと記述し、次のように定義する。
【数１】
2006507585.tif 000003
以下の実施例は、コンピュータグラフィックス・プログラミングの当業者に対して、解法テクニックとしての自動微分の基礎を説明する。その完全な処理は、例えば、「Ａｕｔｏｍａｔｉｃ  Ｄｉｆｆｅｒｅｎｔｉａｔｉｏｎ  ｏｆ  Ａｌｇｏｒｉｔｈｍｓ：Ｔｈｅｏｒｙ，ｉｍｐｌｅｍｅｎｔａｔｉｏｎ，ａｎｄ  Ａｐｐｌｉｃａｔｉｏｎ」（ＳＩＡＭ刊、米国ペンシルベニア州フィラデルフィア、１９９１年）等の数学文献に見いだすことができる。ｆ’（ｘ）＝２ｘ２＋１の例を検討する。変数δ＝ｄと設定するが、ｄは、ニュートンとライプニッツが最初に導入した無限小の概念に類似の小さな非ゼロの数値である。次に、ｆ’（ｘ）への近似式は次のように求められる。
【数２】
2006507585.tif 000004
【００２８】
この結果を正確な導関数４ｘと比較すると、追加の誤差項２ｄは明らかにｄと同じ桁数である。誤差項は、分子の２ｄ２項から導かれることに留意されたい。ゆえに、ｄを１より小さくて十分ゼロに近いように選択すると、ｄ２＜＜ｄでありゼロに非常に近くなる。例えば、ｄ＝１０−３の場合、ｄ２＝１０−６になる。結局、ｄ＞０及びｄ２＝０の場合、式（２）は正確な導関数をもたらすであろうが、そのような性質の実数は存在しない。しかしながら、別の文献でクリフォードが１８７３年に導入したように、記数法は、ｄ＞０及びｄ２＝０という特性の「微分」ｄを含むように拡張することができる。虚数ｉと同様、微分ｄには好都合ないくつかの特性がある。例えば、ｄは可換なので任意の実数に関してａｄ＝ｄａ及びａ＋ｄ＝ｄ＋ａが成り立つ。リミットδの代わりに微分ｄを使うと、式（１）は次のように書き換えることができる。
【数３】
2006507585.tif 000005
【００２９】
従って、ｆ（ｘ＋ｄ）を計算して係数ｄを読み取ることによって、正確な導関数を計算できる。例えば、ｆ（ｘ）＝ｘｎの場合は次のようになる。
【数４】
2006507585.tif 000006
式の右辺の全項は、最初の２つの要素を除いてゼロに等しい。従って、正確な導関数は、予想の通りｄの係数ｎｘｎ−１である。
【００３０】
前述の自動微分法は、偏導関数に一般化することができる。微分ｄのかわりに、ｉ∈Ｉの添字の集合で指定した非ゼロの数値の集合（ｄ０，ｄ１，．．．ｄｉ）を導入する。集合（ｄ０，ｄ１，．．．ｄｉ）は全て実数に交換でき、ｉ，ｊ∈Ｉを満たす全てのｉ、ｊに対してｄｉｄｊ＝０という追加の特性をもつ。この種の一般微分式は、
【数５】
2006507585.tif 000007
と記述できる。つまり、この新しい微分クラスの項は、実数ａ（実数部）と実数ベクタトル（ｂｉ）ｉ∈Ｉ（無限小部）から成る一対で表すことができる。式（３）をこの新しい微分クラスに拡張すると、多変量関数ｆ（ｘ０，ｘ１，．．．ｘｉ）の偏導関数は、ｆ（ｘ０＋ｄ０，ｘ１＋ｄ1，．．．ｘｉ＋ｄi）を計算して、ｄｉの係数から所望のｉｔｈ番目の偏導関数を読み取ることで得られる。例えば、一対の実数を別の実数にマッピングする関数ｆ（ｘ，ｙ）の偏導関数は、ｆ（ｘ＋ｄ０，ｙ＋ｄ1）を計算することで計算できる。ｘの偏導関数はｄ０の係数が読み取り、ｙの偏導関数はｄ１の係数を読み取る。全てのｄ０ｄ１項は定義によりゼロである。この手法では、差分法に比べて関数ｆ（ｘ，ｙ）の計算が実質的に少なくなる。
【００３１】
ＩＩ．汎用プログラミング
Ｃ＋＋等の適切なプログラミング言語は、「汎用プログラミング」可能性のために、各微分型で作動するように使用できる。汎用プログラミングとは、基礎となる使用データ形式に依存しないようにソフトウェアが書かれている方法論のことを言う。例えば、汎用プログラミングは、標準テンプレートライブラリで採用されており、このライブラリは、Ｃ＋＋テンプレートメカニズムを用いてコンテンツ及び引数の形式に依存しない抽象データ形式及びアルゴリズムを定義する。実際には、現在、多数のテンプレートベースのＣ＋＋の汎用数学ライブラリが存在する。汎用プログラミングで認識されている目的の１つは、浮動小数点数値（例えば、「浮動小数点」型又は「倍精度」型を使う場合）の機械語表現等の情報に依存しないコードを可能にすることである。
【００３２】
また、汎用プログラミングライブラリは、微分を扱うために特別に定義したオブジェクトクラスで作動する数学関数を提供するために利用できる。特別に定義したオブジェクトクラスは、通常の数値形式のインタフェースに非常に類似した、置き換え可能なインタフェースをエクスポートするように設計する必要がある。新しいクラスは、代数的に定義できるので（例えばｄ２＝０によって）、複素数のオブジェクトクラスと同様に実施することができる。一般的には、広範なクラスの関数の導関数の計算は、複素数に適用される関数の計算と同様に容易に実施できる。
【００３３】
以下にＣ＋＋の例示的な説明を示す。基本的データ形式の浮動小数点型を使用できる。浮動小数点型は、新しい微分クラスにおいて微分ｄで示す新しい要素を追加することにより拡張できる。微分クラスの全要素は、実数ａ、ｂに関してａ＋ｂｄの形式で記述できる。変数ａを実数部、変数ｂを無限小部と呼ぶ。Ｃ＋＋でコーディングすると、微分クラスは次のように定義できる。
class Differential { 
public : 
float a ;//Real part 
float b ;//Infinitesimal part 
Differential (floataO, float bO = O. Of) : a(aO), b(bO) { }
もしくは、微分クラスの要素をパブリックにする代わりに、アクセッサメソッドを使用できる。
【００３４】
微分型のオブジェクトの演算は、特定の方法で定義する必要がある。例えば、２つの微分オブジェクトａ０＋ｂ０ｄ及びａ1＋ｂ1ｄの合計は、（ａ０＋ｂ０ｄ）＋（ａ1＋ｂ1ｄ）＝（ａ０＋ａ1）＋（ｂ0ｄ＋ｂ1ｄ）と定義する必要がある。同様に、２つの微分オブジェクトの積は（ａ０＋ｂ０ｄ）（ａ1＋ｂ1ｄ）＝ａ０ａ1＋（ａ0ｂ1＋ａ1ｂ0）ｄと定義する必要がある。Ｃ＋＋において、演算子は、特別なオブジェクトクラスに対して特別に定義することができる。これは「演算子オーバーロード」と呼ばれる場合がある。以下のＣ＋＋の実施例は、微分データ型の加算及び乗算のそれぞれに関して、演算子オーバーロードを示す。
Differential 
operator+ (const Differential & x, const Differential & y) { return Differential (x.a+y. a, x. b+y. b); }
Differential 
operator* (const Differential & x, const Differential & y) { return Differential (x. a*y. a, x. a*y.b+x. b*y. a); }
【００３５】
演算子は、導関数の計算に使用できる。例えば、関数ｆ（ｘ）＝（ｘ＋２）（ｘ＋１）を検討する。これは、多相型関数として次の汎用形式で実施できる。
template < class X > X f (X x) { 
return (x+X (2))* (x+X (l)) ;
}
式中の定数は「ｔｅｍｐｌａｔｅ」パラメータ形式にキャストされているため、「＋」演算子の引数も同じ形式である。もしくは、演算子は、別の形式の引数を受け入れ可能なようにオーバーロードされる。従って、微分変数ｄは次のように定義できる。
Differential d(0,l) ;
次に、ｄは、引数に追加されたｄを用いて関数ｆ（ｘ）を評価することにより、ｘの任意の所望の値でｆ（ｘ）の導関数を計算するために使用できる。導関数は、戻り値の無限小部である。例えば、Ｘ＝３の場合、ｆ（Ｘ（３）＋ｄ）の値は次のようになる。
（３＋ｄ＋２）（３＋ｄ＋１）＝（５＋ｄ）（４＋ｄ）＝２０＋９ｄ      （５）
ここで定義によりｄ２＝０である。つまり、汎用形式の関数ｆ（Ｘ（３）＋ｄ）の計算結果は、微分オブジェクト（２０，９）を戻すが、正確な導関数は２番目の項の９で与えられる。これが正しい結果であることを理解されたい。ｘ＝３の場合に、
Differential d(3,l) ;
と定義してｆ（ｄ）を計算することによって全く同じ結果が得られることに留意されたい。この場合、ｘの所望の値は微分の実数部として与えられる。
【００３６】
前述の実施例では、テンプレートベースの数学的ライブラリから取得できるような汎用関数を使って導関数を計算するためのオーバーロードした加算演算子及び乗算演算子の使用法を説明した。減算は、加算の直接的な変分であるが、微分オブジェクトの適切な除算演算子の定義はより難解である。１つのアプローチとして、（１＋ｘ）−１の一般化された二項展開を用いることができる。以下に例を示す。
【数６】
2006507585.tif 000008
【００３７】
つまり、２つの微分オブジェクトの比は、式（６）に基づいて定義することができる。この結果は、分母のｄの実数部ａ１が非ゼロであることを必要とするが、これは容易に実現できることを理解されたい。
【００３８】
この自動微分の実施は、前述の演算子に制限された関数に限定されるものではない。実数に対して定義された任意の微分可能な関数は、以下の微分クラスのオブジェクトに拡張することができる。
ｆ（ａ＋ｂｄ）＝ｆ（ａ）＋ｂｆ’（ａ）ｄ      （７）
例えば、余弦演算は次のような微分オブジェクトとして定義できる。
Differential 
cos (const Differential & x) { 
return Differential (cos (x.a),-x. b*sin (x. a) ); 
} 
【００３９】
つまり、演算の比較的小さな数値が微分オブジェクトに関して定義されると、コンピュータグラフィックス及びその他のアプリケーションで一般に使用されているような、ほとんどの任意の微分可能な関数は自動的に微分することができる。適切に汎用のベクトル及び行列ライブラリの組み合わせると、同様にベクトル及び行列の式を微分することができる。また、流体力学シミュレーションで使用されているような複雑なコードは、微分をおこなって、例えば、出力パラメータが入力パラメータにどのように依存するかを判定することができる。Ｃ＋＋環境での自動微分の態様は、Ｍ．Ｅ．Ｊｅｒｒｅｌｌ著「Ｆｕｎｃｔｉｏｎ  Ｍｉｎｉｍｉｚａｔｉｏｎ  ａｎｄ  Ａｕｔｏｍａｔｉｃ  Ｄｉｆｆｅｒｅｎｔｉａｔｉｏｎ  Ｕｓｉｎｇ  Ｃ＋＋」（「Ｏｂｊｅｃｔ−Ｏｒｉｅｎｔｅｄ  Ｐｒｏｇｒａｍｍｉｎｇ  Ｓｙｓｔｅｍｓ，Ｌａｎｇｕａｇｅｓ，ａｎｄ  Ａｐｐｌｉｃａｔｉｏｎｓ」会議議事録、ＡＣＭ  Ｐｒｅｓｓ、１９８９年）、及びＣｌａｕｓ  Ｂｅｎｓｏｎ、Ｏｌｅ  Ｓｔａｕｎｉｎｇ著「ＦＡＤＢＡＤ，Ｆｌｅｘｉｂｌｅ  Ａｕｔｏｍａｔｉｃ  Ｄｉｆｆｅｒｅｎｔｉａｔｉｏｎ  Ｕｓｉｎｇ  Ｔｅｍｐｌａｔｅｓ  ａｎｄ  Ｏｐｅｒａｔｏｒ  Ｏｖｅｒｌｏａｄｉｎｇ  ｉｎ  ＡＮＳＩ  Ｃ＋＋」（２００３年、ｈｔｔｐ：／／ｗｗ．ｉｍｍ．ｄｔｕ．ｄｋ／ｆａｄｂａｄ）に詳細に説明されている。
【００４０】
例えば、本明細書で詳細に説明するようなバンドル調整等の多数のアプリケーションで、二次導関数を計算することが望ましいであろう。ＦＡＤＢＡＤライブラリで提案されているように、１つのアプローチは、単に導関数の計算を反復することである。例えば、変数が１つの場合、任意のクラスに対して微分オブジェクトのクラスを定義できる。
template < class X > 
class Differential { 
public : 
X a ;//Real part 
X b ;//Infinitesimal part 
Differential (X aO, X bO = 0) : a (a0), b (b0) 
{} static Differential < X > d () { 
return Differential < X > (X (O), X (l)) ; 
}
};
【００４１】
これは、浮動小数点型変数のクラスに対して定義された、微分クラスを定義する第１の実施例と比較することができる。前記の方法を反復することによって二次導関数を計算できる。例えば、第１の関数「ｆ」の二次導関数を計算するために、第２のＣ＋＋関数「ｇ」を使用してｆの導関数を一般的な方法で計算することができる。次に、ｇはその結果で反復することができる。以下のＣ＋＋コードの例は、この方法を説明する。
template < class X > 
X f (X x) { 
return...//Compute some function of x 
}
// 
//Compute f' (x) 
// 
X g (X x) { 
return f (Differential < X > (x) +Differential < X > : : d ()). b ; 
}
// 
//Compute f'' (x) =g' (x) 
// 
... = g (Differential < float > (x) +Differential < float > : : d ()). b ; 
【００４２】
また、汎用プログラミング手法は、区間演算及びアフィン変換演算と共に使用するのに適切である。これらの方法を一般的に実施することによって、区間演算及びアフィン変換演算は、同様に写真測量等のインバースレンダリング問題に対するアプリケーションの自動微分と組み合わせることができる。
【００４３】
ＩＩＩ．写真測量、マッチムービング、及びその他デジタルムービー用途のアプリケーション
デジタルムービーのポストプロダクション作業における多数のアプリケーションは、インバースレンダリングを含むことができ、これは所定の画像に一致する出力を生成するレンダラへの入力を決定する。例えば、多数のパラメータ（θ1，θ2，．．．）は、３Ｄレンダリング処理の入力として供給される。これらのパラメータは、回転角等の変換パラメータからＢｌｉｎｎ−Ｐｈｏｎｇシェーダの指数等のシェーダパラメータまで広範囲にわたる。一般に、レンダリング処理は、次の関数と見なすことができる。
ｆ：（θ1，θ２，．．．）→（Ｉi,j,c）      （８）
ここで（Ｉｉ，ｊ，ｃ）は、レンダリング画像の（ｉ，ｊ）番目の画素の「ｃ」チャンネルの色を表す。Jｉ，ｊ，ｃがベースラインとして使用される特定の「正しい」又は所望の結果である場合、二乗誤差項の合計は次のように記述できる。
【数８】
2006507585.tif 000009
【００４４】
レンダリングコードを十分に一般的に記述して、特定のパラメータを微分オブジェクトで置き換えることができる場合には、前述のように、これらのパラメータに関するｅ及びその導関数を自動的に計算することができる。自動微分ツールは、非線形共役勾配等の最小化アルゴリズムとの関連において、Ｊに最も一致する画像Ｉをもたらす入力パラメータを効率的に導き出すために適用できる。
【００４５】
ポストプロダクションにおける多数の問題は、３Ｄレンダラのサブシステムを微分又は反転することにより解くことができる。例えば、光線トレーサの一部は入力として光線のパラメータを取得し、出力として光線が交差するテクスチャ座標を戻す。この光線追跡コードを汎用的に実行することにより、テクスチャ座標の導関数を光線パラメータの関数として自動的に計算することができる。これは、例えば、アンチエイリアス・テクスチャマッピングを実施する上で好都合である。
【００４６】
別のインバースレンダリング問題は、３Ｄポイントを２Ｄ画面の座標に変換して投影することに関連する。この操作の逆は、投影した２Ｄポイントのコレクション、即ち写真測量及びマッチムービングに最も適合する３Ｄモデル化ジオメトリを導き出すことを含む。
【００４７】
図１を参照すると、３次元シーン１００を表す座標（ｐｉ）で３次元ポイントＰｉ，ｉ∈Ｉ（例えば、Ｐ１、Ｐ２、Ｐ３、Ｐ４）の集合を再構成することが望ましい。座標（ｐｉ）は、シーン１００が参照する座標系の最適データ１１０に対して定義することができる。集合Jのインデックスが付与された画像の集合が存在し、一部のＰｉは投影されているように見える。各々の画像ｊに関してカメラ投影関数ｃｊが存在するので、ｃｊ（Ｐｉ）は、ポイントＰｉをカメラｊに関連する２次元画面空間に投影したものである。例えば、画面空間１０４をカメラ１０２と関連させ、画面空間１０６をカメラ１０８と関連させることができる。例えばカメラ１０８である選択されたカメラは、シーン１００の中に自由に配置することができる。一般的に、カメラに関連した画面空間は、シーン内の対象の全てのポイントを含む必要がない。例えば、画面空間１０６はＰ４を含まないが、画面空間１０４には含まれる。投影関数は、一種のリバースレンダリング関数で構成される。適切な投影関数ｃｊを定義する方法は、写真測量の技術分野では良く理解されており本明細書では説明しない。
【００４８】
インデックス集合Ｒは、画像ｊに投影されているように見える各々のｐｉに関して（ｉ，ｊ）∈Ｒとして定義できる。各々の（ｉ，ｊ）∈Ｒに関して、関連する画面空間内の２Ｄの位置ｚｉ，ｊは、対応する画像から測定できる。例えば、ｚ１，１からｚ４，１の２Ｄの位置は、カメラ１０２からの画像で測定できる。同様に、ｚ１，２からｚ３，２の位置は、カメラ１０８からの画像で測定できる。
【００４９】
対象の位置（例えば、データ１１０に関するＰ１〜Ｐ４の座標）及び投影関数ｃｊは少なくとも部分的に未定義なので、位置ｚｉ，ｊは誤差ｅｉ，ｊの変量によって投影された位置ｃｊ（ｐｉ）に関連する。言い換えると、次の式になる。
【数９】
2006507585.tif 000010
ここでｅｉ，ｊは、Ｐｉの実際の投影と測定した投影との間の差分である。誤差ｅｉ，ｊは、ｃｊ及び（ｐｉ）を関数として変化し、測定された２Ｄ位置ｚｉ，ｊはほぼ一定である。
【００５０】
誤差量は、関連する画面空間の２Ｄ座標ｘ，ｙ上で定義することができる。ｅｉ，ｊのｘ−ｙ座標は、分散σｊをもつ要素の独立した正規分布変数であると想定する。従って、ポイントＰｉの位置（ｐｉ）及びｃｊの任意の未知のパラメータは、ｅｉ，ｊの偏差が最小二乗で最小化されるので決定できる。位置（ｐｉ）及びｃｊの未知のパラメータの最大尤度推定は、最小誤差ｅから決定でき、ｅは次のように定義される。
【数１０】
2006507585.tif 000011
導関数を見出して導関数がゼロになる（ｐｉ）の値を解くことにより、式（１１）から最小誤差を決定できることを理解されたい。当業者であれば、本技術分野では公知の誤差を表す別の関数を用いることができる。所望であれば、導関数を使用して、本技術分野では公知であるバンドル調整と呼ばれる場合もある最小化反復アルゴリズムを使って、誤差関数を最小化することができる。本明細書で開示したような汎用プログラミング手法を使って式（１１）を表し、自動微分によって導関数を解くことにより、解法プロセスを大幅に助長できることは明らかである。もちろん、本発明を実施する写真測量アプリケーションの設計時に、解法プロセスにはさまざまな選択肢が存在するが、以下に詳細を例示的に示す。
【００５１】
しかし、解法プロセスを詳細に説明する前に、ある種の他の一般的考察を行う。実際には、Ｐｉの構造についての詳細情報が利用できる場合が多い。例えば、Ｐｉの一部が共面であることが知られている場合がある。この種の情報は、解をさらに拘束するために使用することができる。同時に、投影関数ｃｊの少なくとも特定のパラメータが未知の場合がある。例えば、カメラの焦点距離及びレンズの歪みが未知の場合、又は未知の位置又は方向に配置される場合がある。未知のパラメータは、投影関数では変数として表すことができる。好都合なことに、汎用プログラミング／自動微分アプローチを用いると、解の定義及び拘束に大幅な柔軟性がもたらされる。例えば、ユーザインタフェースは、ユーザが柔軟に定義された関係式を使って解のパラメータを定義するために設けることができる。これらの関係式は、手動での微分を必要とすることなく、解の中に組み込んで自動的に微分することができる。
【００５２】
前述の一般原則は、さまざまな方法で解法プロセスに導入できる。図２を参照すると、本発明の実施形態による１つの解決方法２００は以下のように要約することができる。ステップ２０２では、解法プロセスはシーンの複数の画像を表す画像データを受信する。例えば、ユーザインタフェースは、ユーザがデータベースから関連のある画像を特定して選択し、次に選択した画像を使って解法プロセスを開始するために設けることができる。シーン画像は、本技術分野では公知のように、任意の適切なカメラを使用して収集できる。
【００５３】
ステップ２０４では、２つ又はそれ以上の選択した画像において表れる、対応するポイント及びその他の対応する特徴を指定するユーザ入力を受信する。ユーザ入力は、複数の画像に表れる対応する特徴をマークして特定する機能を果たす。対応する各々の特徴は、シーングラフのノード上に置く必要がある。例えば、複数の画像をコンピュータディスプレイに表示しながら、ユーザは画像上のポインティングデバイスを使って対応するポイントを指定することができる。任意の適切な方法を使用して、画像データの複数の対応する特徴のユーザ入力指示を受信できる。この種の実測値を入力して記録する方法は本技術分野では公知である。
【００５４】
ステップ２０６では、シーンの暫定推定解を解法プロセスで利用するために受信する。任意の所望の利用可能な情報又は推定に基づいて、ユーザは暫定推定解を作成することができる。好都合なアプローチとして、暫定３Ｄモデル、望ましくはシーングラフ形式の暫定３Ｄモデルを推定解として受け取ることができる。３Ｄモデリングソフトウェアに精通したユーザも多く、任意の適切なモデリングプログラムを使ってシーンの近似を作成することができる。例えば、本発明の実施形態では、解法アルゴリズムは、ＡｌｉａｓｊＷａｖｅｆｒｏｎｔ  ＭａｙａＴＭを入力として使ってシーングラフ形式で作成した近似モデルを受け取るように設計した。もしくは、初期推定解は、自動的に作成すること又は任意の値の組から選択することができる。シーングラフ内のポイント又はその他の推定解は、ステップ２０４のユーザ入力に基づいて、画像データ内のｚｉ，ｊ等の２Ｄ位置の測定値と関連付ける必要がある。
【００５５】
シーンをシーングラフ等のＤＡＧとして再構成して表すと、シーングラフを利用しない従来の方法よりもはるかに少ない入力画像の組から、より正確な結果を得ることがきる。例えば、Ｆｏｌｅｙ他著「Ｃｏｍｐｕｔｅｒ  Ｇｒａｐｈｉｃｓ，Ｐｒｉｎｃｉｐｌｅｓ  ａｎｄ  Ｐｒａｃｔｉｃｅ  ｉｎ  Ｃ」（アディソンウェズリー、１９９５年、ＩＳＢＮ  ０−２０１−８４８４０−６）の第７章「Ｏｂｊｅｃｔ  Ｈｉｅｒａｒｃｈｙ  ａｎｄ  Ｓｉｍｐｌｅ  ＰＨＩＧＳ（ＳＰＨＩＧＳ）」に説明されているシーングラフ階層は、コンピュータグラフィックスの技術分野では公知である。シーングラフの使用は、コンピュータグラフィックスの標準規格によって十分にサポートされている。多数のコンピュータグラフィックス・アプリケーションでは、関連するグラフィックデータ（「シーン」と呼ぶ）の個々の組は、対応するシーングラフで表される。
【００５６】
シーングラフ内の各々のオブジェクトは、シーン内の他のオブジェクトと階層関係に並ぶ。正確には、シーングラフは一種の非循環有向グラフであり、家系図のようにループしない一方向のツリー構造である。例えば、各々のオブジェクト又は各々のノードについて「親」及び／又は「子」が識別される。親は複数の子をもつことができ、子は複数の親をもつことができる。子が親の系列内の任意のノードの親であることは許されない。データ構成要素をもつ要素は、可視のオブジェクト又はカメラ位置と同様、ノードで表される。各々のノードは、空間及び時間を含む入力パラメータに基づく値を返すことになる関数を表す。
【００５７】
シーングラフの重要な態様は、「トランスフォーム」と呼ばれる場合もある階層関係オブジェクト間の定義された相関関係である。特に、相対的な方向、サイズ、アタッチメントのモード、又はその他の子オブジェクトと親の相関関係は、子オブジェクトのトランスフォームである。オブジェクトのトランスフォームを操作して、親オブジェクトと子オブジェクトとの間の相関関係を調整することができる。例えば、腕（親）に対する手（子）のサイズを調整するため、手トランスフォームのサイズパラメータを増加させることができる。トランスフォームは、オブジェクトのトランスフォームが子に継承されるという形で継承される。例えば、腕のトランスフォームを調整して腕を２倍大きくすると、手も２倍になる。オブジェクトの全コレクション、親−子の相関関係、及びトランスフォームはシーングラフを構成する。任意の所望のトランスフォームを微分関数として表す限り、ｅの式に組み込んで微分することは容易である。
【００５８】
シーングラフは、動きのモデリングとオブジェクトの拡大縮小に有用である。オブジェクトが動かされ、サイズが大きく又は小さくなる場合、通常、全ての子オブジェクトもそれにともなって動き、サイズが大きく又は小さくなる。その簡単な例がコンピュータで生成した俳優である。俳優の腕が動くと、付属の手も通常それにともなって動く。シーングラフとして見ると、手は腕の子と定義される。好都合なことに、俳優の腕が動いても、アニメータは手を別に描く必要がない。シーングラフ内で定義された相関関係は、手が腕と共に動くことを保証する。また、静的オブジェクトもシーングラフに加えることができる。静的オブジェクトの例として、ビルとその窓がある。ビルが窓の親だとすれば、写真測量法の間にビルが移転すると、それに伴って窓も自動的に動く。さらに、ビルのサイズ又は比率が変化すると、窓もそれに伴って拡大縮小する。相対的な方向、サイズ、アタッチメントのモード、及びその他の子オブジェクトと親との相関関係は、子オブジェクトのトランスフォームと呼ばれる。
【００５９】
任意の適切なソフトウェアアプリケーション、例えばＯｐｅｎ  ＩｎｖｅｎｔｏｒＴＭやＭａｙａＴＭは、本発明による方法で利用するシーングラフを作成するために使用できる。最初には（写真測量の適用前）、シーングラフは部分情報及び／又は近似情報を含む。例えば、窓は子オブジェクトとして、サイズ及び位置がまだ分からないビルに関連する。このような場合、各々の窓のトランスフォームは、相対的なサイズ及び方向の部分情報を含むように構成できる。例えば、窓については、窓の寸法を指定することなく、窓の周縁は矩形で、ビルの壁から突出しておらず、壁の周縁と並行であると指定することができる。不完全又は正しくないトランスフォームの任意のパラメータは、写真測量技術を使って自動的に計算される。初期シーングラフの中の情報が写真測量の解を決定はしないがそれを導くので、シーンに関する完全な情報は必要ない。
【００６０】
３Ｄモデル、望ましくはシーングラフ形式の３Ｄモデルは、初期推定解として受け取ることができる。さらに、ステップ２０８では、暫定推定解の相関関係は、ユーザ入力からさらに定義することができる。例えば、本発明の実施形態では、ユーザはＭａｙａＴＭシーングラフの変換を定義して、シーンの部分的に既知の情報を表すことができる。例えば、シーンのオブジェクトが直方体であることが既知であるが寸法が未知の場合、ユーザはシーングラフ内に「立方体」オブジェクトのインスタンスを作成して、トランスフォームを使って拡大縮小することができる。次に、ユーザは、シーングラフ内の未知の値の変数をマークできる。直方体の例では、ユーザは固体の未知の寸法を定義する３つの数値をマークすることができる。倍率、回転角度、変換、カメラの焦点距離等の種々の未知パラメータを、シーン内で未知としてマークできる。
【００６１】
さらに、写真測量の投影関数は、カメラ位置、カメラ方向、焦点距離、レンズ及び／又は焦点面の歪み、及びその他の画像の外観に影響する係数を含むがそれらに限定されないカメラパラメータに関する情報又は仮定を含むように定義する必要がある。ステップ２１０では、この種の既知パラメータを解法プロセスで使用するために受信できる。前述したように、少なくとも一部の投影関数パラメータは、未知とマークして解くことができる。例えば、特に画像がカメラ移動時の時間シーケンスを表す場合、又は配置が何らかの理由で測定されなかった場合、カメラの配置が分からない場合がある。焦点距離等のその他のカメラパラメータは既知である場合が多い。カメラパラメータの間の相関関係を定義することができる。例えば、２つ又はそれ以上のカメラの焦点距離を等しくすることができる。これら全てのカメラパラメータは、初期シーングラフ内のノードとして表すことができる。好都合なことに、これは、シーンのジオメトリと同じ方法で、つまり同種の式の組を使って、未知のカメラパラメータの解法を助長することができる。これは、カメラパラメータを別に処理する従来の方法に比べて、本発明による方法の能力及び柔軟性を大幅に強化することができる。例えば、任意の所定の時間のカメラ配置は、解の任意の他の未知のパラメータと同じように処理することができ、カメラをシーンの内側でも外側でも自由に配置できるようになる。
【００６２】
ステップ２１２では、解を計算する誤差関数ｅを決定する。解は、所望の位置（ｐｉ）、及び未知のカメラパラメータ等の投影関数の未知パラメータで構成される。誤差関数ｅは、微分可能であり、投影ポイントｚｉ，ｊの予測値と測定値との間の差分（例えば、一般に式（１１）で表わされる最小二乗差分）を表すように定義する。一般にｅは、行列形式で表わされる等式系で構成される必要があることを理解されたい。
【００６３】
本発明の実施形態では、既存のレンダリング・モデリングプログラムのレンダリングサブシステムを使って誤差関数を定義できる。レンダリングサブシステムを変更して、ポイントのこのシーン階層への投影を汎用的に計算することができる（つまり、リバースレンダリングを実施するために）。好ましくは、既存のレンダリングサブシステムは、トランスフォーム及びカメラパラメータを含むシーングラフを利用するので、結果として得られる汎用的にプログラミングされた投影関数ｃｊは、標準シーングラフフォーマットを使って容易に入力を受け取って出力を供給できる。
【００６４】
ステップ２１４では、未知とマークされたパラメータ及びシーンジオメトリのポイント（ｐｉ）等の、値を最小化する未知パラメータのコレクションを発見できるように、誤差関数ｅは反復されることができる。最小値ｅでのこれらのパラメータ値は、当初定義されたリバースレンダリング問題の解と見なすことができる。反復は、ステップ２０６〜２１０で受信した情報で構成される推定解から開始できる。最小化は、反復最小化アルゴリズムを使用して実行することができる。以下に詳細に説明するように、本明細書で開示した自動微分法を使用して、反復解法プロセスを導いてニュートン法に基づいて高速で解に到達するため、正確な二次導関数（ヘシアン）の完全な計算を含むことは好都合である。
【００６５】
特に、レーベンベルク・マルクワルト・アルゴリズムの動的バリエーションの組は、有界及び非有界の最小化に適合し、バンドル調整に使用できる。しかしながら、ヤコビの関数としてのヘシアン（二次導関数行列）近似ｅのかわりに（過去に例がある）、本明細書で開示した自動微分を使って、正確なヘシアン及び正確なヤコビを計算することができる。各々の反復では、共役勾配アルゴリズムを使用してヘシアンの線形系を解くことができる。
【００６６】
ステップ２１６では、ｅの最小値に対応するパラメータ値を使用して、３次元シーンのモデルを作成することができる。例えば、既存のノード又は新規追加のノードのパラメータとして、解法を完了するため、解いたパラメータを暫定推定シーングラフに組み込むことができる。最後に、再構成したシーンをユーザに提示することができる。再構成に相当の誤差が含まれていれば、ユーザにはラフモデルを調整して再び処理を実行する機会が与えられる。結果が十分に正しければ、グラフィックアーティストは、好都合なことにすでに標準シーングラフフォーマットになっているので、簡単に細部の詰めを行うことができる。
【００６７】
再び解法ステップ２１４について説明すると、一般にｅは複数の未知パラメータに依存するため、解法を一般化して偏微分を追加する必要があることを理解されたい。ベクトル（ｂｉ）ｉ∈Ｉ（自動微分で用いた偏微分オブジェクトの無限小部）を、値のデンスリストとしてではなく、インデックス値のペアとして散在的（ｓｐａｒｓｅｌｙ）に表すことが好都合である。これは、ヘシアンのスパース表現、及び反復ステップを解くためのスパース共役勾配法の使用を可能にする。スパース性（ｓｐａｒｓｉｔｙ）の利用は、優れた性能を実現するのに役立つことが分かっている。（ｘ1，．．．，ｘＮ）について、次のＮ２二次導関数を検討する。
【数１１】
2006507585.tif 000012
ここで、各々のｆｉはｘｉの所定の小さな数値Ｍの関数である。この結果、ヘシアンはＬＭ２だけの非ゼロ項を取る。マッチムービングの問題に関して、通常、非ゼロ項の数はＮ２よりも非常に小さい。
【００６８】
映画のポストプロダクション作業で使用される本発明の実施形態において、フォワードモード微分と呼ばれる自動微分の所定の形式を実施した。自動微分の代替のアプローチは、数学及び情報工学の分野で説明されるリバースモード自動微分である。リバースモード微分は、多数の入力変数を含む問題に最適である場合が多い。しかしながら、本発明の実施形態ではリバースモード微分を実施したが、実現できた性能は、微分をスパース表現するフォワードモード微分を実施した実施形態よりも劣っていた。また、本出願では試験していないが、リバースモード微分のスパース版を使用して、本発明を実施することもできる。
【００６９】
方法２００は、複雑なマッチムービング問題の解法を含むことが容易である。例えば、動画の画像シーケンスを独立した画像の組として処理して、静的パラメータ及び時間に依存するパラメータの両方を同時に解くことができる。実際には、マッチムーブは、従来のようにフレームからフレームへのマッチムーブを段階的に計算するかわりに、同時にフレーム全体にわたって最小化することによって計算できる。ユーザは、入力画像が時間的シーケンスを表す範囲において、パラメータがアニメーション化したと見なし得るか否かを指示することができる。アニメーション化（時間の関数として変化する）するように指示されたこれらのパラメータは、各時間ステップで解の独立したパラメータとして処理できる。実際には、本発明の実施形態をシーケンス内の複数のフレームに適用すると、１０，０００以上の寸法空間でレーベンベルク・マルクワルト法の最小化に成功する場合が多く、本技術分野の著しい進歩が明らかになった。
【００７０】
従来技術を凌ぐ進歩は、他の方法でも示されている。本発明は、本発明がユーザに提供するシーンに関する既知の情報を表現するための高水準の柔軟性をもたらす。本発明の実施形態において、回転角又は相対的倍率等の任意の変換パラメータを解法のためにマークすることができる。任意数のカメラをシーン階層内の任意の場所に配置でき、カメラトランスフォームのパラメータを解法のためにマークすることができる。この解法は、アニメーション化された関節ジオメトリを再構成できることが判明しており、関節ジオメトリに取り付けたカメラ（実際のカメラリグと共に）でさえも再構成できことが判明している。この種のカメラは任意の他のアニメーション化パラメータと同様に処理できる。
【００７１】
さらに、例えば、ＭａｙａＴＭ等の特定の３Ｄモデリングアプリケーションは、記号式を使ってシーングラフ中のパラメータの接続をサポートする。この種のアプリケーションは、解法ステップの入力を作成するために使用できる。本発明の実施形態では、ＭａｙａＴＭが提供するものに類似した等式評価モジュールは、汎用的及び従って微分可能な方法でもってＣ＋＋で記述される。シーンのパラメータ間の相関関係を表す式は、ｅの式に入力することができる。このような式を定義することにより、ユーザは、トランスフォームを使用して表現することは難しい、制約を表現することができる。例えば、ユーザは、２つの独立したオブジェクトが未知の同じ高さにあること、又は２台のカメラが未知の同じ焦点距離であることを指示できる。
【００７２】
前述の機能は、ｅの式を著しく複雑にする傾向にあることを理解されたい。この複雑化にもかかわらず、本発明の実施形態は、長編映画制作の非常に過酷な環境において、ｅの最小値（ｇｌｏｂａｌ  ｍｉｎｉｍｕｍ）を高い信頼性で高精度かつ高速に特定することが判明している。これは、本発明の現実的かつ立証された利点を示すものでもある。
【００７３】
一般に、本発明は、リバースレンダリング問題を解くために使用する導関数を計算する非常に効率的な方法であることが判明している。特に、本発明は、フィルムからジオメトリ及びカメラの動きを再構成する問題に対して効率的な解をもたらす。制作環境に提供すると、本発明は、構造化ジオメトリ及び非構造化ジオメトリの両方を解き得ることが判明している。本発明を実行するアプリケーションは、映画ための時間依存の主要なビジュアルエフェクト・プロジェクト用の、従来技術の商用マッチムービング及び写真測量ソフトウェアを完全に置き換えるのに最適であることが分かっている。
【００７４】
映画のポストプロダクションに用いた場合の本発明の有効性は、少なからず一貫して汎用的なｅの式の実行にある。再利用可能なライブラリの構成要素が、ｅを柔軟かつ汎用的な方法で定義するために記述されると、ｅの解を見つけることは、ポイントを単純に変換、投影するフォワードコードよりも易しい。ソルバは、ほとんど全てがｅを計算する汎用コード及び汎用関数を最適化するライブラリコードから成り立っている。
【００７５】
そのうえ、本発明、特に汎用プログラミング環境における効率的な自動微分は、一般に使用されているガウス−ニュートン法の近似のかわりに、完全ニュートン法を使った解法を可能にした。完全ニュートン法は正確な解を高速に生成するが、実際の検討には複雑すぎると見なされる場合が多い。汎用的にプログラミングされた環境における自動微分のアプリケーションは、以前は厄介であった制約を取り除いた。しかしながら、ガウス−ニュートン法を実行することも可能であり、一部の用途ではこの方法の方が好ましい。２つの方法の比較は複雑であり、いずれの方法も環境に応じて採用することができる。
【００７６】
写真測量及びマッチムービングのアプリケーションを比較する認知された標準ベンチマークの組は存在しないが、本発明を映画のポストプロダクションで実施した場合、同等の従来技術のアプリケーションよりはるかに効率的であると思われる。制作環境では、シーンの３Ｄモデルを段階的に作成でき（商用のモデラを使用して）、次に、写真測量／マッチムービング・ソルバを適用して、最新情報を使って最良の極小値を見つけ出すことができる。このように実施する場合、シングル２：８ＧＨｚ  ＸｅｏｎＴＭＣＰＵ上で解法を処理すると、一般に解に到達するのに必要な時間はワークフローの中ではあまり問題にならなかった。通常、シーンは段階的に構成され、暫定解の処理の後にシーン要素の近似が追加される。この種の段階的変更は、実際に非常に高速に解くことができる。
【００７７】
シーン全体を１度に解くバッチ解法でも高速に実行できる。  例えば、６００フレームのマッチムービーを解いて、各フレームについて６台のカメラのトランスフォームパラメータを決定し、また時間的に変化しない（３７００次元空間の最小化を必要とする）約１００のパラメータを決定するシナリオにおいて、誤差関数に到達するまでわずか５分しか必要とせず、解くのにせいぜい約４５分であった。処理時間のさらに著しい低減は、完全な解法を開始するために使用できる優れた近似を得るために選択したフレーム（例えば、フレームを１０個おきに選択）を使って実現することができる。これに対比して、従来技術の商用マッチムービングツールは全フレームを同時に使用せず、その代わりに一度に１フレームを解くか、又は小さなバッチを使って同時に解く。従って、従来技術のマッチムービングツールは、多数のフレームを解くためにかなりの長い時間を必要とする。しかし、本発明では、解法にかかる時間は、結果を３Ｄモデラに戻す通信時間よりも著しく短くなる場合が多い。
【００７８】
数千次元に及ぶことも多く、しかも回転角等のパラメータの存在により複雑なトポロジをもつこの種の非常に大規模な解空間を利用する場合、多数の極小値（ｌｏｃａｌ  ｍｉｎｉｍｕｍ）に遭遇する可能性があり、それが最小値の発見を妨げることがある。しかし驚くべきことに、本発明を、映画のポストプロダクション作業時に表われる現実の写真測量及びマッチムービング問題に実施すると、大抵、レーベンベルク・マルクワルト・アルゴリズムを開始して、直接一意の最小値に到達することができた。まれな場合として、最小値でない極小値を見出すこともあった。この種の極小値は、単純な対称操作により最小値に合致する場合が多かった。例えば、投影したカメラから直接前方に向いた軸を基に反転したオブジェクトに、極小値が見つかる場合がある。このような場合、反転を補正して、次に初期推定解として補正したシーングラフに対して解法アルゴリズムを反復するのは簡単なプロセスであった。
【００７９】
直接最小値に達する本発明の有効性の一部は、正確なヘシアンの計算を含めて完全ニュートン法を実行した結果であると思われる。換言すると、これは、前述のように各々の反復の間に汎用プログラミング及び自動微分法を使って微分を計算できる、効率性及び容易性により可能になった。これは、このアルゴリズムが最小値のまわりに「盆地（ｂａｓｉｎ）」を残すことなく解空間の中で迷わないように保証し、アルゴリズムが極小値に捕まらないように保証する点で有効である。
【００８０】
従って、前述の説明に基づいて当業者であれば、本発明による方法を実行する装置を作ることができる。図３は、データベース３０４から画像データを受信するために接続したコンピュータ３０２よりなる、この種の１つの装置３００を示す。さらに装置３００は、コンピュータに接続可能なメモリ３０６を備えることができる。メモリ３０６は、当業者が本発明による方法を実行できる命令コードを含むことができる。例えば、メモリ３０６は、本発明による方法のステップを実行する命令を備えることができる。例えば以下の通りである。
（ｉ）複数の３次元シーンの写真画像よりなる画像データを受信する段階。
（ｉｉ）複数の写真画像の中の少なくとも２つの写真画像に表れる複数の対応する特徴を指示するユーザ入力を受信する段階。
（ｉｉｉ）３次元シーンの３次元座標と、複数の対応する特徴の対応する２次元座標との間の相関関係を定義するリバースレンダリング関数の誤差関数を決定する段階。
（ｉｖ）誤差関数を最小化して、誤差関数の最小値に対応する解を決定する段階。この段階は、自動微分を使って誤差関数の少なくとも一次導関数を計算し、それによって推定解が解に収束するまで誤差関数の連続的な反復に対する中間推定解を計算する段階を含む。
【００８１】
また、コンピュータ３０２が実行する本発明による方法についての任意の他の所望のステップの命令を、メモリ３０６に記憶させることができる。また、前述の任意の命令を、コンピュータ３０２及びその他のコンピュータが読み取るために、取り外し可能な媒体３０８で符号化することができる。本発明を実施する最適なコンピュータシステムは本技術分野では公知であり、任意の適切な装置を使用することができる。
【００８２】
以上のように写真測量法の改良を説明したので、当業者であればこの装置により特定の利点を実現できることを理解できる。また、前述のように、本発明の範疇及び精神の範囲で、種々の修正例、適応例、及び変更例を行い得ることは明らかである。例えば、写真測量及びマッチムービングについて特定の用途を開示したが、本発明はそれに限定されないことは明らかである。本発明は、特許請求の範囲により定義されるものである。
【図面の簡単な説明】
【００８３】
【図１】リバースレンダリング法を使って再構成する３次元シーンを示す図である。
【図２】本発明の実施形態による例示的なリバースレンダリング法のステップを示すフローチャートである。
【図３】本発明のステップを実施する例示的な装置を示すブロック図である。
【図１】
2006507585.tif 000013
【図２】
2006507585.tif 000014
【図３】
2006507585.tif 000015
【手続補正書】
【提出日】平成17年7月5日(2005.7.5)
【手続補正２】
【補正対象書類名】明細書
【補正対象項目名】０００１
【補正方法】変更
【補正の内容】
【０００１】
（関連出願への相互参照）
本出願は、米国特許法１１９条（ｅ）項に基づいて２００２年１１月１５日出願の米国特許仮出願番号６０／４２６，５６０の優先権を主張し、その出願全体は引用により本明細書に組み込まれている。
本発明は、デジタルイメージング分野での方法、より詳細には、デジタルモデリングのための写真測量及びマッチムービング等のリバースレンダリング法に関する。
【国際調査報告】
2006507585.tif 000016