(57)【要約】【課題】  入力イメージ内の単位イメージ領域内の情報の重要性に応じてその単位イメージ領域を調整するための方法、システム、およびコンピュータ・プログラム記録媒体を提供することにある。【解決手段】  イメージ・レシーバは、入力イメージを受信するように構成される。イメージ・ワーパは、重要性マップに結合され、入力イメージ内の重要性の高い領域がワープ・イメージ内で拡大され、入力イメージ内の重要性の低い領域がワープ・イメージ内で圧縮されるようなワープ・イメージを生成するように構成される。重要性マップは、入力イメージ内の重要性の高い領域と重要性の低い領域を描写するように構成される。テクスチャ座標も同様にワープすることができる。したがって、イメージは、テクスチャ・マッピング機能を有する最新のグラフィックス・アダプタによって自動的にワープ解除される。
2005518032.tif 000002
【特許請求の範囲】
【請求項１】
重要性マップを入手するステップであって、前記重要性マップが入力イメージ内の重要性の高い領域と重要性の低い領域を描写するステップと、
前記入力イメージをワープして、前記重要性の高い領域が拡大され、前記重要性の低い領域が収縮されるように、前記重要性マップに応じてワープ・イメージを生成するステップと、
を有する、入力イメージ内の単位イメージ領域内の情報の重要性に応じて前記単位イメージ領域を調整するための方法。
【請求項２】
前記入力イメージをワープするステップが、単位領域あたりの情報の重要性の割合が前記イメージの全体にわたって実質的に一定になるように前記入力イメージをワープするステップを含む、請求項１に記載の方法。
【請求項３】
逆ワープ関数を得るために、前記入力イメージに関連するテクスチャ座標の位置をワープするステップをさらに有する、請求項１に記載の方法。
【請求項４】
前記重要性マップを生成するステップをさらに有する、請求項１に記載の方法。
【請求項５】
前記重要性マップを生成するステップが、前記入力イメージ内の局部周波数成分を測定するステップを含む、請求項４に記載の方法。
【請求項６】
前記局部周波数成分を測定するステップが、
前記入力イメージの各単位領域を一対の活動クラスにソートするステップと、
活動測定基準に達するまで前記ソート操作を繰り返すステップと、
を含む、請求項５に記載の方法。
【請求項７】
均一グリッドを弛緩して、重要性の高い領域内のグリッド頂点が収縮され、重要性の低い領域内のグリッド頂点が拡大されるように、前記重要性マップに応じて弛緩グリッドを形成するステップをさらに有する、請求項１に記載の方法。
【請求項８】
前記入力イメージをワープするステップが、前記弛緩グリッドを使用する変換を各単位領域に適用して、前記入力イメージ内の単位領域の各位置ごとに前記入力イメージ内の新しい位置を計算するステップを有する、請求項７に記載の方法。
【請求項９】
前記ワープ・イメージを収縮するステップをさらに有する、請求項１に記載の方法。
【請求項１０】
前記ワープ・イメージをワープ解除するステップをさらに有する、請求項１に記載の方法。
【請求項１１】
入力イメージが関連の入力テクスチャ座標マッピングを有し、
前記入力イメージを受信するように構成されるイメージ・レシーバと、
重要性マップに結合されたイメージ・ワーパであって、前記入力イメージ内の重要性の高い領域がワープ・イメージ内で拡大され、前記入力イメージ内の重要性の低い領域が前記ワープ・イメージ内で圧縮されるような前記ワープ・イメージを生成するように構成され、前記重要性マップが前記入力イメージ内の前記重要性の高い領域と前記重要性の低い領域を描写するように構成されるイメージ・ワーパと、
を有する、入力イメージ内の重要な情報を保存するためのシステム。
【請求項１２】
前記イメージ・ワーパがワープ・テクスチャ座標マッピングを生成するようにさらに構成され、前記ワープ・テクスチャ座標マッピングが逆ワープ関数を得るために前記入力テクスチャ座標マッピングの変換を含む、請求項１１に記載のシステム。
【請求項１３】
前記イメージ・レシーバに結合されたイメージ・エバリュエータであって、前記重要性マップを生成するように構成されるイメージ・エバリュエータをさらに有する、請求項１１に記載のシステム。
【請求項１４】
前記イメージ・レシーバに結合されたグリッド・ジェネレータであって、前記入力イメージ内の均一グリッドを定義するように構成されるグリッド・ジェネレータと、
前記グリッド・ジェネレータに結合されたグリッド弛緩モジュールであって、前記均一イメージ・グリッドを弛緩し、重要性マップに応じて弛緩グリッドを生成するように構成されるグリッド弛緩モジュールと、
をさらに有する、請求項１１に記載のシステム。
【請求項１５】
有形媒体に結合され、入力イメージ内の単位イメージ領域内の情報の重要性に応じて前記単位イメージ領域を調整するためのコンピュータ可読プログラム・コードを有し、前記コンピュータ可読プログラム・コードが、
重要性マップを入手することであって、前記重要性マップが前記入力イメージ内の重要性の高い領域と重要性の低い領域を描写することと、
前記入力イメージをワープして、前記重要性の高い領域が拡大され、前記重要性の低い領域が収縮されるように、前記重要性マップに応じてワープ・イメージを生成すること、
を前記プログラムに実行させるように構成される、有形媒体に実施されるコンピュータ・プログラム記録媒体。
【請求項１６】
前記入力イメージをワープするための前記コンピュータ可読プログラム・コードが、単位領域あたりの情報の重要性の割合が前記イメージの全体にわたって実質的に一定になるように前記入力イメージをワープすることを含む、請求項１５に記載のコンピュータ・プログラム記録媒体。
【請求項１７】
逆ワープ関数を得るために、前記入力イメージに関連するテクスチャ座標の位置をワープするためのコンピュータ可読プログラム・コードをさらに有する、請求項１５に記載のコンピュータ・プログラム記録媒体。
【請求項１８】
前記重要性マップを生成するためのコンピュータ可読プログラム・コードをさらに有する、請求項１５に記載のコンピュータ・プログラム記録媒体。
【請求項１９】
前記重要性マップを生成するための前記コンピュータ可読プログラム・コードが、前記入力イメージ内の局部周波数成分を測定するためのコンピュータ可読プログラム・コードを含む、請求項１８に記載のコンピュータ・プログラム記録媒体。
【請求項２０】
前記局部周波数成分を測定するための前記コンピュータ可読プログラム・コードが、
前記入力イメージの各単位領域を一対の活動クラスにソートするためのコンピュータ可読プログラム・コードと、
活動測定基準に達するまで前記ソート操作を繰り返すためのコンピュータ可読プログラム・コードと、
を含む、請求項１９に記載のコンピュータ・プログラム記録媒体。
【請求項２１】
均一グリッドを弛緩して、重要性の高い領域内のグリッド頂点が収縮され、重要性の低い領域内のグリッド頂点が拡大されるように、前記重要性マップに応じて弛緩グリッドを形成するためのコンピュータ可読プログラム・コードをさらに有する、請求項１５に記載のコンピュータ・プログラム記録媒体。
【請求項２２】
前記入力イメージをワープするための前記コンピュータ可読プログラム・コードが、前記弛緩グリッドを使用する変換を各単位領域に適用して、前記入力イメージ内の単位領域の各位置ごとに前記入力イメージ内の新しい位置を計算することを有する、請求項２１に記載のコンピュータ・プログラム記録媒体。
【請求項２３】
前記ワープ・イメージを圧縮するためのコンピュータ可読プログラム・コードをさらに有する、請求項１５に記載のコンピュータ・プログラム記録媒体。
【請求項２４】
前記ワープ・イメージをワープ解除するためのコンピュータ可読プログラム・コードをさらに有する、請求項１５に記載のコンピュータ・プログラム記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
(関連出願)
本出願は、２００２年２月１２日出願の米国仮出願第６０／３５６４４１号に関連し、その出願日の恩典を請求するものであり、参照により本明細書に組み込まれる。
【０００２】
本発明は、一般に、イメージ処理に関し、
特に、イメージがダウンサイジングゆがみ（downsizingdistortion）に対してより抵抗力のあるものになるようなイメージ内の情報内容の等化に関する。
【背景技術】
【０００３】
テクスチャ・イメージは、低コストで多角形メッシュ（polygonal mesh）のリアリズムを高めるための単純だが効果的な方法である。最新のハードウェア・グラフィックス・アクセラレータは、テクスチャ・イメージを保管するためのメモリ・キャッシュを提供する。キャッシュ内のイメージは高帯域幅接続を介してグラフィックス処理装置（Graphics Processing Unit：ＧＰＵ）によってアクセスすることができ、フレーム・レートが改善される。しかし、キャッシュのサイズは、特に市販のゲーム指向グラフィックス・ボードおよびゲーム・コンソールでは、そのコストによって制限される。アプリケーションが使用するすべてのテクスチャが同時にメモリ内に常駐できるわけではないので、複雑なメモリ管理アルゴリズムを使用する必要がある。より大きいキャッシュが使用可能なフライト・シミュレータなどのハイエンド・アプリケーションでは、それに比例して使用するテクスチャの量が増大し、同様のテクスチャ・メモリの慎重な割振りを必要とする。
【０００４】
イメージ圧縮は、限られたテクスチャ・メモリの問題を緩和することができる。しかし、対話式フレーム・レートを入手するためには、レンダリング中にその場で圧縮テクスチャをデコードしなければならず、特殊ハードウェアを必要とする。今日の伝統的なグラフィックス・ボードで使用可能なテクスチャ・メモリを最適に使用するために、数人の作成者は、複雑なエンコードに頼らずに、テクスチャ・イメージを保管するために必要な空間を削減するという問題について考察した。
【０００５】
反復パターンを含む単純なテクスチャを除いて、詳細は、概して、イメージの全域に均一に分散されるわけではない。たとえば、３Ｄスキャニング・システムによって得られるモデルは、大量の背景ピクセルを含むイメージでテクスチャリングされる（textured）場合が多い。人間およびキャラクタの顔は目および口などの領域内に高解像度の詳細を必要とするが、他の領域の外観は単位領域あたり比較的少数のピクセルで取り込むことができる。
【発明の開示】
【発明が解決しようとする課題】
【０００６】
本発明は、テクスチャ・イメージが使用する空間を最適化する技法を実現することにより、上記の制限に対処するものである。本発明の一実現例では、イメージ周波数内容（image frequency content）はイメージの全域に均一に分散される。換言すれば、イメージは高周波領域で伸長され、低周波領域で収縮される。テクスチャ座標（texture coordinate）は、イメージのゆがみを考慮に入れるために、同様にリマップされる（remapped）。結果として得られるイメージは、その後、より低いレートで再サンプリングする（resampled）ことができ（収縮）、高周波数内容を囲む領域内の詳細の損失は最小限になる。別法として、イメージはより積極的に二次サンプリングする（subsampled）ことができ、その領域の全域で視覚的忠実度（visual fidelity）の損失が均一になる。この最適化プロセスによる影響を受けるのはテクスチャ・イメージとテクスチャ座標のみである。モデルの形状寸法もその接続性も変化しない。最適化イメージがより小さくなると使用するテクスチャ・メモリが少なくなるが、特殊なハードウェアを必要とせず、その「圧縮解除」は、一般的なグラフィック・ハードウェアで使用可能なテクスチャ・マッピング機能によって自動的に実行される。
【課題を解決するための手段】
【０００７】
したがって、本発明の一態様は、入力イメージ内の単位イメージ領域内の情報の重要性に応じてその単位イメージ領域を調整するための方法を含む。この方法は、重要性マップ（importance map）を入手するための入手操作（obtainingoperation）を含む。重要性マップは、入力イメージ内の重要性の高い領域と重要性の低い領域を描写する（delineate）ものである。次にワープ操作（warpingoperation）は、入力イメージをワープして、重要性の高い領域が拡大され、重要性の低い領域が収縮されるように、重要性マップに応じてワープ・イメージ（warped image）を生成する。
【０００８】
本発明の他の態様は、入力イメージ内の重要な情報を保存するためのシステムである。入力イメージは関連の入力テクスチャ座標マッピングを含み、システムはイメージ・レシーバ（image receiver）とイメージ・ワーパ（imagewarper）とを含む。イメージ・レシーバは、入力イメージを受信するように構成される。イメージ・ワーパは、重要性マップに結合され、入力イメージ内の重要性の高い領域がワープ・イメージ内で拡大され、入力イメージ内の重要性の低い領域がワープ・イメージ内で圧縮されるようなワープ・イメージを生成するように構成される。重要性マップは、入力イメージ内の重要性の高い領域と重要性の低い領域を描写するように構成される。
【０００９】
本発明のさらに他の態様は、入力イメージ内の単位イメージ領域内の情報の重要性に応じてその単位イメージ領域を調整するためのコンピュータ可読プログラム・コードを備えたコンピュータ・プログラム記録媒体である。このコンピュータ可読プログラム・コードは、重要性マップを入手し、重要性の高い領域が拡大され、重要性の低い領域が収縮されるように、重要性マップに応じて入力イメージをワープするように構成される。
【００１０】
本発明の上記その他の特徴、有用性、および利点は、添付図面に図示した通り、以下に示す本発明の様々な実施形態のより詳細な記述により明らかになるであろう。
【発明を実施するための最良の形態】
【００１１】
以下に詳述する通り、本発明は、イメージによって使用される空間を有益に最適化するものである。重要なイメージ情報はイメージ領域のより多くの部分をカバーするように伸長され、あまり重要ではない情報は収縮される。したがって、結果として得られるワープ・イメージは、単位領域あたりの情報の重要性の割合がイメージの全体にわたって実質的に一定になるように作成される。本発明については図１〜３１に関して本明細書に記載する。これらの図を参照すると、すべての図にわたって示される同様の構造および要素は同様の参照番号で示されている。
【００１２】
図１には、本発明の一実施形態による処理に適した例示的なイメージ１０２が示されている。イメージ１０２は、任意のイメージ・タイプにすることができ、当業者に知られている様々な技法を使用してエンコードすることができる。たとえば、イメージ１０２は、圧縮済み、未圧縮、モノクロ、グレースケール、またはカラーにすることができる。さらに、イメージ１０２は、コンピュータ・メモリに保管される場合もあれば、コンピュータ・ネットワークにより伝送される場合もある。したがって、イメージ１０２は一般に、メモリ空間またはネットワーク帯域幅などの何らかのシステム・リソースを消費する。
【００１３】
図２には、重要性の大きい領域と重要性の小さい領域が描写されたイメージ１０２が示されている。たとえば、顕著な顔の特徴を含むイメージ領域は、このような特徴を含まない領域より重要なものとして指定することができる。したがって、あるアプリケーションでは、目の領域１０４および口の領域１０６は、イメージ１０２内で重要性の大きい領域として指定することができる。逆に、背景領域１０８は、イメージ１０２内で重要性の低い領域として指定することができる。以下に詳述する通り、イメージ１０２内の重要性の大きい領域と重要性の小さい領域を区別するために、本発明では重要性マップを使用する。
【００１４】
本発明は、重要なものとして指定された領域内のイメージ詳細の損失量を最小限にしながら、イメージ１０２によって消費されるシステム・リソースの量を削減しようと努めるものである。この目標を達成するために、本発明は、重要性マップに応じて重要なイメージ領域が拡大され、あまり重要ではないイメージ領域が収縮されるように、イメージ１０２をワープする。次に、ワープ・イメージ全体が消費するシステム・リソースがより少なくなるように、ワープ・イメージ全体のサイズが低減される。その後のある時点で、そのイメージを使用する場合、この縮小ワープ・イメージは拡大され、ワープ解除される（unwarped）。
【００１５】
図３には、本発明によって企図されるワープ・イメージ１１０が示されている。ワープ・イメージ１１０では、重要性マップでより重要なものと指定された領域は拡大され、あまり重要ではないものと指定された領域は収縮されている。したがって、ワープ・イメージ１１０内の目の領域１１２および口の領域１１４は、元のイメージ１０２内の対応する目の領域１０４および口の領域１０６より大きくなっている。そのうえ、ワープ・イメージ１１０内の背景領域１１６は、元のイメージ１０２内の背景領域１０８より小さくなっている。ワープ・イメージ１１０のキャンバス・サイズは元のイメージ１０２のキャンバス・サイズと同じであることに留意されたい。
【００１６】
図４には、より小さいワープ・イメージ１１２が示されている。ワープ・イメージ１１２はより小さいので、元のイメージ１０２より使用するシステム・リソースが少ない。ワープ・イメージ１１０によって消費されるシステム・リソースを削減するために当業者に知られている任意のイメージ処理方法を本発明で使用できることが企図されている。一般に、本発明によって使用される処理方法は、イメージ・ダウンサイジング（image downsizing）、離散コサイン変換、または複数の圧縮技法の組み合わせなどの不可逆的圧縮方式（lossy compression scheme）である。
【００１７】
図５には、復元イメージ（restoredimage）１１４が示されている。復元イメージ１１４は、より小さいワープ・イメージ１１２に適用されたイメージ圧縮およびワープを逆転させることによって生成される。重要性の大きい領域はワープ・イメージ１１２内で拡大されるので、圧縮段階中に被る情報損失はあまり大きくない。その結果として、イメージ１１４が復元されたときに、より多くのイメージ詳細が重要性の大きい領域内に保存される。復元イメージ１１４は必ずしも元のイメージ１０２と同じキャンバス・サイズを占有するわけではないことに留意されたい。たとえば、復元イメージは、三次元モデルでのテクスチャ・ペイント（texture painting）に使用することができ、したがって、レンダリングした表面上に現れるように変換することができる。
【００１８】
図６には、本発明によって企図されるシステムで実行される操作の流れ図が示されている。示されている論理操作は、（１）コンピューティング・システム上で実行される一連のコンピュータ実行ステップとして、および／または（２）コンピューティング・システム内の相互接続マシン・モジュールとして実現可能であることに注目されたい。この実現例は、本発明を実現するシステムのパフォーマンス要件に依存する選択の問題である。したがって、本明細書に記載する本発明の実施形態を構成する論理操作は、別法として、操作、ステップ、またはモジュールともいう。
【００１９】
このプロセスは受信操作２０２から始まる。この操作中にイメージはシステムによって入力される。前述の通り、イメージは任意のタイプのものにすることができ、当技術分野で知られている様々な方法を使用してエンコードすることができる。本発明の一実施形態では、イメージは、コンピュータ・グラフィックス・アプリケーションにおいて三次元モデルを形成する多角形をペイントするために使用するテクスチャ・イメージである。概して、テクスチャ・イメージは、モデル表面上へのイメージ変換を可能にする、イメージ空間内の１組のテクスチャ座標を含む。受信操作２０２が完了した後、制御は生成操作２０４に移行する。
【００２０】
生成操作２０４では、そのイメージ関する重要性マップが生成される。この操作は、ユーザまたはグラフィックス開発パッケージから重要性マップを受信することを含むことができる。別法として、システムは、以下に詳述する通り、イメージを処理し、自動的に重要性マップを生成することができる。生成操作２０４が完了した後、制御はワープ操作２０６に移行する。
【００２１】
ワープ操作２０６では、イメージ内の重要性の大きい領域が拡大され、重要性の小さい領域が縮小されるように、重要性マップに応じてイメージがワープされる。本発明の一実施形態では、以下の詳述する通り、グリッド弛緩（grid relaxation）アルゴリズムを使用して、イメージを再サンプリングする。ワープ操作２０６が完了した後、制御は収縮操作２０８に移行する。
【００２２】
収縮操作２０８では、ワープ・イメージが必要とするシステム・リソースの量が削減される。この操作は、イメージ・サイズを収縮すること、イメージに圧縮アルゴリズムを適用すること、または当業者に知られている他のこのような手順を実行することを伴う可能性がある。収縮操作２０８が完了すると、ワープ・イメージは、コンピュータ・グラフィックス・メモリに保管するか、またはアクセラレイテッド・グラフィックス・ポート（accelerated graphics port：ＡＧＰ）などの通信リンクにより伝送することができる。ワープ・イメージを再表示する場合、制御はワープ解除操作２１０に移行する。
【００２３】
ワープ解除操作２１０では、ワープ・イメージは変換によりゆがみのないイメージに戻される。この操作は概して、前に実行された収縮操作２０８およびワープ操作２０６を取り消すことを含む。本発明の一実施形態では、ワープ解除操作２１０は、以下に詳述する通り、イメージの三次元レンダリングを形成するための多角形メッシュ上へのイメージ変換を含む。ワープ解除操作２１０が完了すると、プロセスは終了する。
【００２４】
図７には、本発明によって企図される例示的なシステム３０２が示されている。本発明によれば、システム３０２を形成するモジュールは、コンピュータ可読媒体に実施されるコンピュータ可読プログラム・コードにすることができる。制限ではなく例証として、コンピュータ可読媒体は、コンピュータ記憶媒体と通信媒体とを有することができる。コンピュータ記憶媒体は、コンピュータ可読命令、データ構造、プログラム・モジュール、またはその他のデータなどの情報を保管するための任意の方法または技術で実現される揮発性および不揮発性、取外し可能および取外し不能媒体を含む。コンピュータ記憶媒体は、ＲＡＭ、ＲＯＭ、ＥＥＰＲＯＭ、フラッシュ・メモリまたはその他のメモリ技術、ＣＤ−ＲＯＭ、ディジタル多目的ディスク（digital versatile disk：ＤＶＤ）またはその他の光学記憶装置、磁気カセット、磁気テープ、磁気ディスク記憶装置またはその他の磁気記憶装置、あるいは所望の情報を保管するために使用可能で、管理エージェントによってアクセス可能なその他の任意の媒体を含むが、これらに限定されない。通信媒体は概して、搬送波またはその他の移送メカニズムなどの被変調データ信号としてコンピュータ可読命令、データ構造、プログラム・モジュール、またはその他のデータを実施し、任意の情報送達媒体を含む。「被変調データ信号」という用語は、その特性のうちのうちの１つまたは複数が信号内の情報をエンコードするように設定または変更されている信号を意味する。制限ではなく例証として、通信媒体は、有線ネットワークまたは直接有線接続などの有線媒体と、音波、ＲＦ、赤外線、その他の無線媒体などの無線媒体を含む。上記のいずれかの媒体の組み合わせも、コンピュータ可読媒体の範囲内に含まれるはずである。
【００２５】
システム３０２は、入力イメージ１０２を受信するように構成されたイメージ・レシーバ３０４を含む。参考のため、例示的な入力イメージ１０２が図８に示されている。図７に戻ると、イメージ・レシーバ３０４はグリッド・ジェネレータ（grid generator）３０６に結合されている。このグリッド・ジェネレータは、入力イメージ１０２内の均一グリッド（uniform grid）を定義するように構成される。図９は、例示的な均一グリッドとともに入力イメージ１０２を示している。グリッド内の行および列の数は入力イメージ１０２に適合可能であることが企図されている。本発明の一実施形態では、グリッド解像度（grid resolution）は、ラプラシアン平滑化手順の収束の状態（以下に詳述する）に応じて、反復して洗練させることができる。この手法では、グリッド解像度は最初は低くなっているが、グリッド弛緩反復にわたって徐々に増加する。したがって、グリッド内の頂点の数は、イメージ・サイズ、カラー、および／またはその他のイメージ属性に依存する可能性がある。本発明の特定の一実施形態では、システム・ユーザは、グリッドの正確さを対話式に指定することができ、したがって、後述するワープ手順の正確さに直接、影響を及ぼす可能性がある。
【００２６】
もう一度、図７に戻ると、グリッド・ジェネレータ３０６はグリッド弛緩モジュール３０８に結合されている。グリッド弛緩モジュール３０８は、均一イメージ・グリッドを弛緩して、重要性マップに応じた弛緩グリッド（relaxed grid）を生成する。前述の通り、重要性マップ３１０がユーザによって指定される場合もあれば、重要性マップ３１２がシステム３０２によって生成される場合もある。ユーザが重要性マップ３１０を提供する場合、重要性マップ３１０は、各ピクセル位置が対応するイメージ・ピクセルに関する重要性を指定する、他のイメージになる可能性がある。ユーザが重要性マップ３１０を渡す可能性により、イメージ１０２の特定の変換を実行することができる。
【００２７】
別法として、イメージ・レシーバ３０４に結合されたイメージ・エバリュエータ（image evaluator）３１４は、重要性マップ３１２を生成するように構成することができる。本発明の一実施形態では、ウェーブレット・パケット拡張変換（wavelet packet expansion transform）を使用して入力イメージ１０２の周波数内容を分析して、重要性マップ３１２が生成される。この変換は、周波数サブバンドを特徴付ける１組の係数にイメージを分解するものである。
【００２８】
次に図１３を参照すると、本発明によって企図されるウェーブレット・パケット拡張変換プロセスが示されている。このプロセスは、マルチレベル手法を使用して、入力イメージ１０２内の各ピクセルに重要性の値を割り当てる。このプロセスは、各ピクセルを２つの重要性クラスに分類するための分類ループ５０２、５０４、５０６を含む。分類ループ５０２、５０４、５０６の反復ごとに、そのイメージの重要性クラスの数が二倍になる。したがって、分類ループ５０２、５０４、５０６の１回目の反復後、イメージ１０２内の各ピクセルは２つの重要性クラスのうちの１つにソートされる。分類ループ５０２、５０４、５０６の２回目の反復後、各ピクセルは４つの重要性クラスのうちの１つにソートされ、以下同様になる。判断操作５０６で活動基準を満足するまで、分類ループが繰り返される。
【００２９】
プロセス内のソート操作５０２は、入力イメージ１０２を受信し、各ピクセルを低周波（ＬＦ）クラスまたは高周波（ＨＦ）クラスにソートする。概して、高周波領域はエッジおよび小さい詳細を含み、低周波ゾーンは低い強度変化を含む。周波数変化を正確に検出するために、入力イメージ１０２のマルチスケール分析が実行される。このため、エッジは、詳細係数マトリックス内の局所極大をたどることにより、効率よく検出することができる。これらの値はウェーブレット極大という。
【００３０】
したがって、ソート操作５０２中に各ピクセルＩ（ｕ，ｖ）は、対応するウェーブレット係数付近の領域内にウェーブレット極大が存在するかどうかがテストされる。このような極大が存在する場合、その存在は、Ｍ（ｕ，ｖ）によって示される周波数マップに記録される。ウェーブレット・パケット変換により、複数のスケール（すなわち、周波数）で極大を見つけることができ、その結果、周波数領域へのイメージの分類が行われる。
【００３１】
ソート操作５０２の１回目の反復後、イメージは、１組のローパス係数（low-pass coefficient）（０〜ｎ／２の周波数を記述する）と、３組の詳細係数（detail coefficient）（ｎ／２〜ｎの周波数を表す）に変換される。各組の詳細係数ごとに、対応するサブバンド内の分散から推定されたしきい値を使用して、ウェーブレット極大が測定される。このため、分散ループ５０２、５０４、５０６の１回目の反復後、ピクセルは２組にソートされ、その結果は以下のように定義されるマトリックスＭ1（ｕ，ｖ）に保管される。
【数１】
2005518032.tif 000003
【００３２】
ソート操作５０２の２回目の反復後、各サブバンドはもう一度、２つのハーフバンド（half-band）に分割される。このため、Ｍ1（ｕ，ｖ）は洗練され、前の各入力は、対応する詳細マトリックス内のウェーブレット極大を探すことによってソートされる。したがって、新しいマトリックスＭ2（ｕ，ｖ）は以下のように定義される。
【数２】
2005518032.tif 000004
【００３３】
測定操作５０４では、分類ループ５０２、５０４、５０６の反復がもう１回必要であるかどうかを判定するために活動測定が実行される。活動測定は、重要性クラスの数、分類の正確さ、ユーザに提供される計算予算（computational budget）、入力イメージ１０２内の数量情報のサイズ、またはこのような活動測定の任意の組み合わせを含む、様々なメトリックに基づくものにすることができる。判断操作５０６で活動測定がしきいレベルに達しない場合、制御はソート操作５０２に戻る。活動測定がしきいレベルに達した場合、重要性マップ３１２が出力され、変換が終了する。図１０には、ウェーブレット・パケット拡張変換によって生成される例示的な重要性マップ３１２が示されている。
【００３４】
図７に戻ると、グリッド弛緩モジュール３０８は弛緩アルゴリズムを使用して、重要性マップ３１０または３１２が示すように、入力イメージ１０２のより重要な領域内でグリッド頂点を集中させ、入力イメージ１０２のあまり重要ではない領域内でグリッド頂点を分散させる。たとえば、図１１は、図１０の重要性マップによる弛緩グリッドとともに入力イメージを示している。図１１に図示した通り、弛緩グリッドの頂点は、より多くの詳細を含む領域内で集められ、あまり詳細を含まない領域内で分散される。
【００３５】
本発明の一実施形態では、ラプラシアン平滑化手順を使用してイメージの全域に情報を均一に分散し、重要性マップに応じて領域を伸長または縮小する。特に、グリッド弛緩モジュール３０８は、以下のエネルギー関数（energy function）を最小限にすることにより均一グリッドを弛緩する。
【数３】
2005518032.tif 000005
【００３６】
この弛緩手順は、グリッド・エッジｅ＝（ｉ，ｊ）によって接続された２つの頂点ｖiおよびｖjの間の距離｜ｖi−ｖj｜がエッジ中点における周波数マップσにほぼ反比例するように、頂点を新しい位置に移動する。この弛緩手順は、対応する現在位置ｖinに変位を追加することにより頂点の新しい位置ｖin+1が決定される逐次近似である。変位ベクトルは、
【数４】
2005518032.tif 000006
という式であって、式中、ｉ*がグリッド・エッジによってｉに接続されたグリッド頂点インデックスの集合である式と、
【数５】
2005518032.tif 000007
という式を使用して、計算される。
【００３７】
単位正方形の４つの隅（グリッドの４つの頂点に対応する）は移動しないように拘束され、他の境界頂点はそれぞれの支持直線境界セグメント（supporting straight boundary segment）に沿ってのみ移動するように拘束されている。その結果は拘束変位ベクトルδ（ｖn）iになり、続いて以下のように現在の頂点位置に適用される。
【数６】
2005518032.tif 000008
【００３８】
図７に戻ると、グリッド弛緩モジュール３０８で得られる弛緩グリッドを使用して、イメージ・ワーパ３１６によって入力イメージ１０２を再サンプリングし、それによりワープ・イメージ１１０を生成する。イメージ・ワーパ３１６によって実行される再サンプリング・プロセスは、弛緩グリッド（入力イメージの定義域内に存在する）を使用して入力イメージ１０２内の位置についてワープ・イメージ１１０内の各ピクセルに照会することを含む。返される位置を使用して、その後、ワープ・イメージ１１０内の開始位置にコピーされる色の濃さを検索する。これらのステップは、図１２に示す通り、ワープ・イメージ１１０内の各ピクセルごとに繰り返される。
【００３９】
本発明は、テクスチャ・マッピングを使用するグラフィックス・システムにおいて特に有益である。このようなシステムでは、二次元テクスチャ・イメージは、三次元モデルをペイントするために使用するテクスチャ座標に関連付けられる。最新のグラフィックス・アクセラレータは概して、提供されるテクスチャ座標を使用して、テクスチャ・イメージをモデル上に自動的に変換（またはテクスチャ・マッピング）することができる。
【００４０】
したがって、図７に戻ると、入力イメージ１０２に関連する１組の入力テクスチャ座標３０８も、入力イメージ１０２と同様にイメージ・ワーパ３１６によってワープされる。具体的には、入力テクスチャ座標３１８内の各座標は、弛緩グリッドによって指示される新しいワープ座標（warped coordinate）にワープされる。その結果は、ワープ・イメージ１１０に対応する１組の出力テクスチャ座標３２０になる。
【００４１】
たとえば、図１４〜１９には、本発明によって企図されるテクスチャ・マッピング・システムを示すイメージが示されている。このテクスチャ・マッピング・システムは、入力イメージ１０２と、入力イメージ定義域内の１組の入力イメージ座標３１８とを含む。入力イメージ座標３１８は、その上に入力イメージ１０２がペイントされる三次元モデル６０２の座標に対応する。したがって、入力イメージ１０２はモデル６０２上にマッピングされ、ペイントした三次元イメージ６０４を生成する。前述の通り、最新のグラフィックス・アクセラレータは、入力イメージ１０２および入力テクスチャ座標３１８が提供されたときに三次元モデル６０２を自動的にテクスチャ・マッピングするように構成されている。
【００４２】
本発明の一実施形態では、入力イメージ１０２と入力座標３１８の両方が弛緩グリッドに応じてワープされ、それによりワープ・イメージ１１０とワープ座標３２０を生成する。座標はイメージとともにワープされるので、ワープ・イメージ１１０とワープ座標３２０を使用してモデル６０２をペイントしたときに、三次元イメージ６０４にはほどんどまたはまったくゆがみが現れない。したがって、ワープ・イメージ１１０は、テクスチャ・マッピング機能を有する最新のグラフィックス・アクセラレータによって自動的に「ワープ解除」される。したがって、本発明を使用すると、処理したイメージをワープ解除するための既存のグラフィックス・アクセラレータ技術を使用してその詳細を保存しながらイメージを圧縮することができる。
【００４３】
本発明の利点をより十分に例証するために、次に図２０〜２３および図２４〜２７を参照する。図２０〜２３のイメージは、本発明によって企図される最適化プロセスを使用せずに三次元モデル上にテクスチャ・マッピングされている。図２４〜２７のイメージは、本発明によって企図される最適化プロセスにより三次元モデル上にテクスチャ・マッピングされている。図２０および図２４は、元の（未縮小）イメージを使用するテクスチャ・マッピングを示している。図２１および図２５は、イメージが元のイメージの３０％に縮小された後のテクスチャ・マッピングを示している。図２２および図２６は、イメージが元のイメージの２０％に縮小された後のテクスチャ・マッピングを示している。図２３および図２７は、イメージが元のイメージの１０％に縮小された後のテクスチャ・マッピングを示している。この２組の図を比較すると、特に元のサイズの３０％および２０％のときに未最適化テクスチャ（unoptimized texture）によってピクセル化作成物（pixelization artifact）がより見やすくなることは明らかである。元のサイズの１０％のときでも、最適化イメージは、未最適化バージョンにはない何らかの高周波詳細を保存している。
【００４４】
図２８には、地の精の石像のテクスチャ・アトラス・イメージ（atlas image）が示されている。このアトラス・イメージは、様々な視点から見た三次元モデルをテクスチャ・マッピングするために使用する。図２９には、本発明によりワープされた元のアトラス・イメージが示されている。元のアトラス・イメージとワープ・アトラス・イメージ（warped atlas image）の両方を使用して、図３０に示す三次元イメージをレンダリングする。次に、レンダリングした両方のイメージに対し様々なイメージ圧縮係数でイメージゆがみ分析を実行し、図３１にグラフで示す。横軸は、二次サンプリングしたイメージのサイズを元のイメージのパーセントとして示している。右から左に進むにつれて、テクスチャは累進的に収縮される。縦軸は、対数目盛でエラーを示している。したがって、本発明の最適化を使用する場合と使用しない場合にイメージの二次サンプリングによってもたらされるエラーが図３１に示されている。図示の通り、非常に小さい（１０％未満）収縮率を除き、最適化イメージは基本的にすべてのイメージ・サイズで発生するエラーが小さくなっている。
【００４５】
本発明の上記の説明は、例示および説明のために提示したものである。網羅することまたは開示された通りの形式に本発明を制限することを意図しているのではなく、上記の教示を考慮すると他の修正形態および変形形態が可能である。たとえば、最適送受信ノードを選択するために、本発明で代替メッセージ・シーケンスを使用することができる。したがって、開示されている実施形態は、本発明の原理およびその実用例を最も良く説明し、それにより他の当業者が企図された特定の使用に適した様々な実施形態および様々な修正形態において本発明を最も良く利用できるようにするために選択され記載されたものである。特許請求の範囲は、従来技術によって制限される範囲を除き、本発明の他の代替実施形態を含むように解釈するものとする。
【図面の簡単な説明】
【００４６】
【図１】本発明によって使用される例示的な入力イメージを示す図である。
【図２】重要性の大きい領域と重要性の小さい領域が描写された入力イメージを示す図である。
【図３】本発明の一実施形態によって企図される例示的なワープ・イメージを示す図である。
【図４】本発明の一実施形態によって企図される例示的な収縮ワープ・イメージを示す図である。
【図５】本発明の一実施形態によって企図される例示的な復元イメージを示す図である。
【図６】本発明によって企図されるシステムによって実行される操作の例示的な流れ図である。
【図７】本発明の一実施形態によって企図される例示的なシステムを示す図である。
【図８】本発明によって使用される例示的な入力イメージを示す図である。
【図９】均一グリッドとともに例示的な入力イメージを示す図である。
【図１０】本発明の一実施形態によって企図される例示的な重要性マップを示す図である。
【図１１】本発明によって企図される例示的な弛緩グリッドを示す図である。
【図１２】本発明の一実施形態によって企図されるワープ・イメージを示す図である。
【図１３】本発明によって企図される例示的なウェーブレット・パケット拡張変換プロセスを示す図である。
【図１４】本発明によって企図される例示的な入力イメージを示す図である。
【図１５】本発明によって企図される例示的な入力イメージ座標を示す図である。
【図１６】本発明によって企図される例示的なワープ・イメージを示す図である。
【図１７】本発明によって企図される例示的なワープ座標を示す図である。
【図１８】本発明によって企図される例示的なイメージ・モデルを示す図である。
【図１９】本発明によって企図される例示的なペイント・イメージ・モデル（painted image model）を示す図である。
【図２０】本発明によって企図される最適化プロセスを使用せずに三次元モデル上にマッピングされたイメージ・テクスチャを示す図である。
【図２１】本発明によって企図される最適化プロセスを使用せずに三次元モデル上にマッピングされたイメージ・テクスチャを示す図である。
【図２２】本発明によって企図される最適化プロセスを使用せずに三次元モデル上にマッピングされたイメージ・テクスチャを示す図である。
【図２３】本発明によって企図される最適化プロセスを使用せずに三次元モデル上にマッピングされたイメージ・テクスチャを示す図である。
【図２４】本発明によって企図される最適化プロセスを使用して三次元モデル上にマッピングされたイメージ・テクスチャを示す図である。
【図２５】本発明によって企図される最適化プロセスを使用して三次元モデル上にマッピングされたイメージ・テクスチャを示す図である。
【図２６】本発明によって企図される最適化プロセスを使用して三次元モデル上にマッピングされたイメージ・テクスチャを示す図である。
【図２７】本発明によって企図される最適化プロセスを使用して三次元モデル上にマッピングされたイメージ・テクスチャを示す図である。
【図２８】本発明によって企図される例示的なアトラス・イメージを示す図である。
【図２９】本発明によって企図される例示的なワープ・アトラス・イメージを示す図である。
【図３０】レンダリングした三次元モデルを示す図である。
【図３１】元のアトラス・イメージとワープ・アトラス・イメージの両方を使用して二次サンプリング・エラーを示すグラフである。
【図１】
2005518032.tif 000009
【図２】
2005518032.tif 000010
【図３】
2005518032.tif 000011
【図４】
2005518032.tif 000012
【図５】
2005518032.tif 000013
【図６】
2005518032.tif 000014
【図７】
2005518032.tif 000015
【図８】
2005518032.tif 000016
【図９】
2005518032.tif 000017
【図１０】
2005518032.tif 000018
【図１１】
2005518032.tif 000019
【図１２】
2005518032.tif 000020
【図１３】
2005518032.tif 000021
【図１４】
2005518032.tif 000022
【図１５】
2005518032.tif 000023
【図１６】
2005518032.tif 000024
【図１７】
2005518032.tif 000025
【図１８】
2005518032.tif 000026
【図１９】
2005518032.tif 000027
【図２０】
2005518032.tif 000028
【図２１】
2005518032.tif 000029
【図２２】
2005518032.tif 000030
【図２３】
2005518032.tif 000031
【図２４】
2005518032.tif 000032
【図２５】
2005518032.tif 000033
【図２６】
2005518032.tif 000034
【図２７】
2005518032.tif 000035
【図２８】
2005518032.tif 000036
【図２９】
2005518032.tif 000037
【図３０】
2005518032.tif 000038
【図３１】
2005518032.tif 000039
【国際調査報告】
2005518032.tif 000040
2005518032.tif 000041