(57)【要約】  本発明は、多次元テクスチャを表現するデータを符号化するための方法であって、前記データが、少なくとも3である多数の次元上で最初は編成され、前記次元の少なくとも1つが、前記テクスチャを描画するためのパラメータに関連付けられている方法において、前記次元上で前記データをウェーブレット解析するステップ(C2)と、前記解析の結果から得られたデータを圧縮するステップ(C3)とを含むことを特徴とする方法に関する。
2010518667.tif 000002
【特許請求の範囲】
【請求項１】
多次元テクスチャを表現するデータを符号化する方法であって、前記データが、少なくとも3に等しい多数の次元上で最初は編成され、前記次元の少なくとも1つが、前記テクスチャ用の描画パラメータに関連付けられている方法において、
前記次元上で前記データをウェーブレット解析するステップ(C2)と、
前記解析(C2)の結果から得られたデータを圧縮するステップ(C3)と
を含むことを特徴とする方法。
【請求項２】
前記データを所定の数の次元に従って再編成するための予備ステップ(C1)を含むことを特徴とする請求項1に記載の符号化方法。
【請求項３】
前記再編成ステップにおいて、前記データが、前記データの2つの連続するサンプルの間の、少なくとも1つの次元による相関を最大化するように配列されることを特徴とする請求項2に記載の符号化方法。
【請求項４】
前記データが、YUV色符号化方式によって色を表現することを特徴とする請求項1から3のいずれか一項に記載の符号化方法。
【請求項５】
前記圧縮ステップ(C3)が、「ゼロツリー」型符号化を使用することを特徴とする請求項1から4のいずれか一項に記載の符号化方法。
【請求項６】
多次元テクスチャを表現するデータを復号する方法であって、前記データが、少なくとも3に等しい多数の次元上で最初は編成され、前記次元の少なくとも1つが、前記テクスチャ用の描画パラメータに関連付けられている方法において、
前記データを伸張するステップ(D1)と、
前記伸張(D1)から得られたデータを前記次元上でウェーブレット合成するステップ(D2)と
を含むことを特徴とする方法。
【請求項７】
少なくとも3に等しい多数の次元上で編成されたデータによって最初は表現される多次元テクスチャを表す信号であって、前記次元の少なくとも1つが、前記テクスチャ用の描画パラメータに関連付けられている信号において、前記データが、前記次元上でのウェーブレット解析によって、そして前記解析の結果から得られたデータの圧縮によって符号化されていることを特徴とする信号。
【請求項８】
多次元テクスチャを表現するデータを符号化するためのデバイスであって、前記データが、少なくとも3に等しい多数の次元上で最初は編成され、前記次元の少なくとも1つが、前記テクスチャ用の描画パラメータに関連付けられているデバイスにおいて、
前記次元上で前記データをウェーブレット解析する手段と、
前記解析手段から得られたデータを圧縮する手段と
を含むことを特徴とするデバイス。
【請求項９】
多次元テクスチャを表現するデータを復号するためのデバイスであって、前記データが、少なくとも3に等しい多数の次元上で最初は編成され、前記次元の少なくとも1つが、前記テクスチャ用の描画パラメータに関連付けられているデバイスにおいて、
前記データを伸張する手段と、
前記伸張手段から得られたデータを前記次元上でウェーブレット合成する手段と
を含むことを特徴とするデバイス。
【請求項１０】
コンピュータ上で実行されたときに請求項1から6のいずれか一項による方法の1つを実施するための命令を含むコンピュータプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、グラフィックスコンピューティングの分野に含まれ、より具体的には、仮想シーンを表示するためのデータの符号化および圧縮の分野に含まれる。
【０００２】
本発明は、実際上、フォトリアリスティックな合成画像を送信および生成するために使用される多次元テクスチャ(multidimensional texture)を符号化する方法に関する。
【背景技術】
【０００３】
リアルな表面の外観を表現することは、グラフィックスコンピューティングにおける主要問題の1つである。表面の全体的な外観は、しばしば、異なるスケールで定義される。
【０００４】
表面の形状は、最も粗いレベル、巨視的レベルに配置され、表面が表現される物体の幾何学的形状に対応する。グラフィックスハードウェアにおける現行の描画モードを用いた場合、この幾何学的形状は、大抵、メッシュ、すなわち、ポリゴンの集合によって表現される。
【０００５】
最も精細なレベルは、微細構造に対応し、表面がその環境と相互作用する仕方を決定する。最も精細なレベルは、材質の特性を表現し、木材から作られた表面は、金属表面と同じようには光を反射しない。グラフィックスコンピューティングでは、これらの相互作用は、双方向反射分布関数(BRDF: bilateral reflectance distribution function)、視点および光の方向に依存する4次元関数によって表現される。
【０００６】
中間レイヤ、中間構造は、例えば、ざらついた表面上の小突起など、幾何学的形状の詳細をカプセル化する。応用の観点から、このレイヤは、しばしば、いわゆる法線摂動(disturbance of the normal)もしくは「バンプマッピング(bump mapping)」法によって、またはさもなければ、「ディスプレースメントマッピング(displacement mapping)」法と呼ばれる、メッシュ点の法線に沿った幾何学的変位による方法によって表現される。表面の局所的変位は、例えば、遮蔽または影の生成に起因する光強度の局所的変化をもたらすので、このレベルは、トップレイヤに乱れを引き起こす。
【０００７】
複数の方向から光を当て、異なる視点から、デジタルカメラを使用して、表面の描画をキャプチャすることによって、表面の描画を実行するのに必要な中間構造と微細構造の間の相互作用の複雑な計算が回避される。したがって、1999年に機関紙「Association for Computer Machinery (ACM) Transactions On Graphics」に発表された、「Reflectance and texture of real-world surfaces」と題する、K. J. Dana、B. van Ginneken、S. K. Nayar、およびJ. J. Koenderinkによる論文において説明されている、双方向テクスチャ関数(BTF: bilateral texture function)と呼ばれる関数が取得される。これらの関数は、例えば、
BTF = BTF (x, y, θv, φv, θl, φl)
という形式で表現され、ここで、
- xおよびyは、パラメトリック座標で表現される空間座標を表し、
- θvおよびφvは、極座標における視点の方向を定義し、
- θlおよびφlは、極座標における光の方向を定義する。
【０００８】
したがって、BTFは、各画像が視点および光の方向に関連付けられた、画像の集合に対応する。このキャプチャ方法は、同一の材質について、中間構造、微細構造、およびこれら2つのレイヤの間に存在するすべての相互作用を、1回の試みでモデル化することを可能にする。異なる視点の間または光の方向の間での緩やかな推移を保証するには、細かなサンプリングが必要とされるが、それは、1つのBTFが多数の画像に対応することを意味する。
【０００９】
したがって、テクスチャまたは多次元テクスチャとも呼ばれる、これらのモデル化された材質に対応するデータを送信する場合、またこれらのテクスチャをリアルタイムで描画する場合、BTFによって伝えられた生情報は、データアクセス速度および限界のあるメモリサイズ制約を満たすために、異なる仕方で表現されなければならない。
【００１０】
BTFを取得することを可能にする、後者に類似する他の方法も存在し、BTFと比べてより少数または多数の次元を使用することによって、多次元テクスチャを生成する。したがって、「多項式テクスチャマップ(PTM: polynomial texture map)」は、光の方向だけが関連する表面の外観を変化させるテクスチャである。同様に、「時間変化BTF(time-varying BTF)」は、それに次元が追加され、表面の外観を時間とともに変化させることを可能にするBTFである。これらのテクスチャも、適切な符号化を必要とする膨大な量のデータによって表現される。
【００１１】
これらの多次元テクスチャのデータを圧縮するために使用できる既存の符号化技法は、本質的に2つの手法に従って発展する。
【００１２】
第1の手法は、連続関数モデルによって多次元テクスチャを近似することに、その本質が存する。例えば、BTFの形式で表現されるテクスチャは、BRDF関数のモデルによって、または双2次多項式(biquadratic polynomial)によって近似される。
【００１３】
実際のところ、このBTFは、画像の集合によって表現され、各画像は、与えられた視点および光の方向からの、テクスチャに対応する材質の表面の写真であるので、これらのデータを異なる仕方で分類することによって、関係する光の方向および関係する視点に従った各ピクセルの変化が取得される。言い換えると、このBTFは、BRDF関数のモデルの集合
BTF(z, v, l) ≒ {BRDFz(v, l)}, ∀z
によって近似され、ここで、
- zは、最初にBTFにおいてピクセルを定義した空間座標xおよびyの、単一次元上への射影であり、
- vは、最初にBTFにおいて視点の方向を定義した初期極座標θvおよびφvの、単一次元上への射影であり、
- lは、最初にBTFにおいて光の方向を定義した初期極座標θlおよびφlの、単一次元上への射影であり、
- BRDFz(v, l)は、光の方向および視点の方向の各々が単一次元上で表現された、ピクセルzについてのBRDF関数モデルである。
【００１４】
BRDF関数モデルによる近似のそのような方法は、以下の論文、すなわち、
- 2004年2月に機関紙「Computers and Graphics」に発表された、J. Meseth、G. Muller、およびR. Kleinによる、「Reflectance field based real-time, high-quality rendering of bidirectional texture functions」、
- 2002年に会議「ACM SIGGRAPH/EUROGRAPHICS conference on Graphics Hardware」の際に発表された、D. K. McAllister、A. Lastra、およびW. Heidrichによる、「Efficient rendering of spatial bi-directional reflectance distribution functions」、
- 2004年に会議「International Conference on Pattern Recognition (ICPR)」の際に発表された、J. FilipおよびM. Haindlによる、「Non-linear reflectance model for bidirectional texture function synthesis」
において特に説明されている。
【００１５】
この近似のために使用されるBRDF関数モデルは、例えば、1997年に会議「ACM SIGGRAPH」の際に発表された、論文「Non-linear approximation of reflectance functions」において説明されている、E. P. F. Lafortune、S-C. Foo、K. E. Torrance、およびD. P. GreenbergのBRDF関数モデルである。
【００１６】
同様に、BTFは、時には、双2次多項式
BTF(z, v, θl, φl) ≒ {Pv(z, θl, φl)}, ∀v
によって近似され、ここで、
- zは、最初にBTFにおいてピクセルを定義した空間座標xおよびyの、単一次元上への射影であり、
- vは、最初にBTFにおいて視点の方向を定義した極座標θvおよびφvの、単一次元上への射影であり、
- Pv(z, θl, φl)は、与えられた視点についてのBTFの近似の双2次多項式である。
【００１７】
この第1の手法による近似ベースの方法は、テクスチャのコンパクトで連続した表現を取得することを可能にし、その表現は、通常はプログラム可能グラフィックスカード上で直接実行される現行の描画アルゴリズムによく適合する。しかし、そうした方法は、必要な計算の複雑さによって制限される。実際のところ、双2次多項式によって近似を取得するには、BTFの特異値分解(breakdown in singular value)で十分であるが、BRDF関数モデルによる同じ関数の近似は、しばしば、解法が非常に複雑であることが判明する。さらに、これらの近似は、BTFの収集時にキャプチャされる様々な効果を描画することが可能ではない。視点または光の方向の変位に関連する効果は、それらを考慮するために、以下の論文、すなわち、
- 1982年に雑誌「ACM Transactions On Graphics」に発表された、R. L. CookおよびK. E. Torranceによる、「A reflectance model for computer graphics」、または
- 1992年に会議「ACM SIGGRAPH」の際に発表された、G. J. Wardによる、「Measuring and modeling anisotropic reflection」
において説明されているような、はるかに複雑なBRDF関数モデルまたは異なる多項式の使用を必要とする。
【００１８】
加えて、モデル化された表面の中間構造によって引き起こされる、遮蔽または陰影などの、鏡面性(specularity)および特異性(singularity)は、これらの近似ベースの方法によって奪われる。
【００１９】
第2の手法は、多次元テクスチャの線形ベースの分解を実行することに、その本質が存する。例えば、BTFの形式で表現されたテクスチャが与えられ、このBTFが多次元信号に類似している場合、主成分分析(main components analysis)または特異値分解が適用される。この方法は、BTFであるデータの集合の相関を最も良く表す空間内の方向を探索することに、その本質が存する。その場合、BTFに関連する共分散行列(covariance matrix)の特定のベクトルおよび特定の値の探索による、分析体(analysis field)の直交化からもたらされる、新しい基底が定義される。新しい関連する座標系の軸は、BTFの初期サンプルの分散が最大となるようなものである。
【００２０】
その後、特定のベクトルは、対応する特定の値による重要性の順序で、降順にソートされる。したがって、最も影響のある軸だけが保持される。その後、BTFの初期データは、次元の減少したこの新しい空間に射影される。したがって、この新しい基底における元の信号の近似は、以下の1次結合によって取得され、
【００２１】
【数１】
2010518667.tif 000003
【００２２】
ここで、関数giは、次元の減少から得られたc個のベクトルからなる新しい基底{hi}における射影から導出された重みを表す。
【００２３】
この第2の手法に基づいた既存の方法は、分析されるデータの選択によって、また分解がどのように編成されるかに関して異なっている。
【００２４】
したがって、いくつかの方法は、上記の式に関するとともに、2003年に国際ワークショップ「Texture Analysis and Synthesis」の際に発表された、「Acquisition, compression and synthesis of bidirectional texture functions」と題する、M. L. Koudelka、S. Magda、P. N. Belhumeu、およびD. J. Kriegmanによる論文において説明されているような、分析空間として、BTFのすべてのデータを使用する。
【００２５】
他の方法は、視点の変化におけるよりも強い、光の方向の変化におけるコヒーレンスを利用するために、以下の視点による表現を使用し、
BTF(z, v, l) ≒ {BTFv(z, l)}, ∀v
ただし、
【００２６】
【数２】
2010518667.tif 000004
【００２７】
ここで、関数gv, iは、与えられた視点vのBTFのデータBTF(z, v, l)に対応するサンプルBTFv(z, l)の、新しい基底{hv, i}における射影から導出された重みを表す。視点による表現のこれらの方法は、以下の論文、すなわち、
- 2003年に国際会議「Eurographics Symposium on Rendering」の際に発表された、M. Sattler、R. Sarlette、およびR. Kleinによる、「Efficient and realistic visualization of cloth」、
- 2003年に国際会議「OpenSG Symposium」の際に発表された、J. Meseth、G. Muller、およびR. Kleinによる、「Preserving realism in real-time rendering of bidirectional texture functions」
において説明されている。
【００２８】
同じ著者G. Muller、J. Meseth、およびR. Kleinは、以下の論文、すなわち、2003年に国際ワークショップ「Vision, Modeling and Visualisation」において提示された、「Compression and real-time rendering of measured BTFs using local Principal Component Analysis (PCA)」、および2004年に国際会議「Computer Graphics International (CGI)」の際に発表された、「Fast environmental lighting for local-PCA encoded BTFs」において、最大尤度を有するデータを一緒にパケットにグループ化することによる、多次元テクスチャのブロック表現を提案している。その後、分析は、各ブロックにおいて個別に実行され、関連するBTFの分析近似は、以下のようになり、
【００２９】
【数３】
2010518667.tif 000005
【００３０】
ここで、関数gk(z), iは、相関が最も高いピクセルに従ってデータが一緒にブロックにグループ化されたBTF BTF(z, v, l)の、新しい基底{hk(z), i}における射影から導出された重みを表し、k(z)は、ピクセルを尤度ブロックに関連付けるマッピングテーブルに対応する関数である。
【００３１】
さらに、この第2の手法によれば、多重解像度法(multiresolution method)が、2005年に国際会議「Symposium on Interactive 3D graphics and games」の際に発表された、論文「Level-of-detail representation of bidirectional texture functions for real-time rendering」において、W.-C. Ma、S.-H. Chao、Y.-T. Tseng、Y.-Y. Chuang、C.-F. Chang、B.-Y. Chen、およびM. Ouhyoungによって提案されている。彼らは、まず最初に、各ピクセルについて、ラプラスピラミッド(Laplace pyramid)として、初期領域の変換を生成する。複数のレベルからなるこのピラミッドは、より低い解像度の表現を取得するために、最も高いレベルの詳細をフィルタリングすることによって構成される。その後、ピラミッドの係数が、主成分分析によって分解される。
【００３２】
最後に、M. A. O. VasilescuおよびD. Terzopoulosは、2004年に機関紙「ACM Transactions On Graphics」に発表された、論文「Tensortextures: multilinear image-based rendering」において、多重線形法(multilinear method)を提案しており、彼らは、BTFをテンソル積に分解する。各テンソルは、BTFの2つの次元を表し、
- 空間テンソルは、空間座標xおよびyの、単一次元上への射影を表し、
- 視点に関連するテンソルは、極座標θvおよびφvの、単一次元上への射影を表し、
- 光の方向に関連するテンソルは、極座標θlおよびφlの、単一次元上への射影を表す。
【００３３】
これらのテンソルは、3つの次元において特異値分解を使用して計算され、各次元は、先に述べられたように、2重項(doublet)を表す。したがって、この方法は、個々に、1次元だけ、すなわち、1テンソルだけ有利にすることが可能である点で、より良い次元の減少を可能にする。したがって、各次元について保持される主成分の数に従って、近似誤差の目標を設定することができるので、デシメーションは、すべてのBTFにわたって完全にランダムなわけではない。
【００３４】
この第2の手法による分解ベースの方法は、近似ベースの方法と比べた際の質的結果、そのような方法によって圧縮されるテクスチャの質を決定する主成分の数の選択を改善する。そうした方法は、多次元テクスチャのコンパクトで離散的な表現も定める。このコンパクト性は、分解から導出されたベクトルが重要性の順序で分類され、最も代表的なベクトルだけが考慮されるという事実によっている。しかし、このデシメーションは、ランダムであり、変換時にどの細部をブロックアウトするかを定めることが可能ではない。このデシメーションはまた、収集プロセスにおいてキャプチャされたある特異性、相関が低い領域に対応する置換軸を奪う。周波数領域情報のこの欠落は、これらの方法の柔軟性を制限し、これらの方法は、情報のプログレッシブ復号(progressive decoding)によって、異なるレベルの詳細に従った表現を直接提供することを可能にしない。3つの方法によって圧縮されたテクスチャの多重解像度表現は、論文「Level-of-detail representation of bidirectional texture functions for real-time rendering」におけるように、追加の変換を必要とする。
【００３５】
この論文において言及された分解ベースの多重解像度法は、実際には、解像度によるテクスチャの表現を生成し、したがって、解像度の選択に従った情報のプログレッシブ復号を可能にする、単一の多重解像度表現に対応しないことにも留意されたい。
【００３６】
さらに、これらの方法は、離散的な表現を提供するので、テクスチャが描画されるときにテクスチャの領域にわたって高いレベルの詳細が必要とされる場合、このテクスチャの次元のすべてにわたって、収集プロセスから得られた近隣サンプルを使用する補間を必要とする。
【００３７】
したがって、テクスチャ圧縮の既存の方法は、テクスチャのすべてのキャプチャされた詳細を保持することを可能にはせず、例えば、受信器のグラフィックスカードの能力または使用ネットワークのビットレートに関連する、テクスチャ情報を送信するときのハードウェア制約に適合するために、テクスチャ情報のプログレッシブ復号を提供することも可能にしない。しかし、この能力は、テクスチャの使用を非集中システムまたは移動端末などのより広範な周辺デバイスに拡大するために必要である。
【先行技術文献】
【非特許文献】
【００３８】
【非特許文献１】K. J. Dana, B. van Ginneken, S. K. Nayar and J. J. Koenderink, “Reflectance and texture of real-world surfaces”, published in the journal “Association for Computer Machinery (ACM) Transactions On Graphics” in 1999
【非特許文献２】J. Meseth, G. Muller and R. Klein, “Reflectance field based real-time, high-quality rendering of bidirectional texture functions”, published in the journal “Computers and Graphics” in February 2004
【非特許文献３】D.K. McAllister, A. Lastra and W. Heidrich, “Efficient rendering of spatial bi-directional reflectance distribution functions”, published on the occasion of a conference “ACM SIGGRAPH/EUROGRAPHICS conference on Graphics Hardware” in 2002
【非特許文献４】J. Filip and M. Haindl, “Non-linear reflectance model for bidirectional texture function synthesis”, published on the occasion of a conference “International Conference on Pattern Recognition (ICPR)” in 2004
【非特許文献５】E. P. F. Lafortune, S-C. Foo, K.E. Torrance and D. P. Greenberg, “Non-linear approximation of reflectance functions”, published on the occasion of a conference “ACM SIGGRAPH” in 1997
【非特許文献６】R. L. Cook and K. E. Torrance, “A reflectance model for computer graphics”, published in the magazine “ACM Transactions On Graphics” in 1982
【非特許文献７】G. J. Ward, “Measuring and modeling anisotropic reflection” published on the occasion of a conference “ACM SIGGRAPH” in 1992
【非特許文献８】M. L. Koudelka, S. Magda, P. N. Belhumeu and D. J. Kriegman, “Acquisition, compression and synthesis of bidirectional texture functions”, published on the occasion of an international workshop “Texture Analysis and Synthesis” in 2003
【非特許文献９】M. Sattler, R. Sarlette and R. Klein, “Efficient and realistic visualization of cloth” published on the occasion of an international conference “Eurographics Symposium on Rendering” in 2003
【非特許文献１０】J. Meseth, G. Muller and R. Klein, “Preserving realism in real-time rendering of bidirectional texture functions”, published on the occasion of an international conference “OpenSG Symposium” in 2003
【非特許文献１１】G. Muller, J. Meseth and R. Klein, “Compression and real-time rendering of measured BTFs using local Principal Component Analysis (PCA)”, presented at the international workshop “Vision, Modeling and Visualisation” in 2003
【非特許文献１２】G. Muller, J. Meseth and R. Klein, “Fast environmental lighting for local-PCA encoded BTFs”, published on the occasion of the international conference “Computer Graphics International (CGI)” in 2004
【非特許文献１３】W.-C. Ma, S.-H. Chao, Y.-T. Tseng, Y.-Y. Chuang, C.-F. Chang, B.-Y. Chen and M. Ouhyoung, "Level-of-detail representation of bidirectional texture functions for real-time rendering", published on the occasion of an international conference "Symposium on Interactive 3D graphics and games" in 2005
【非特許文献１４】M. A. O. Vasilescu and D. Terzopoulos, “Tensortextures: multilinear image-based rendering”, published in the journal “ACM Transactions On Graphics” in 2004
【非特許文献１５】G. Muller, G. H. Bendels and R. Klein, “Rapid synchronous acquisition of geometry and BTF for cultural heritage artefacts”, published on the occasion of a conference “6th International Symposium on Virtual Reality, Archaeology and Cultural Heritage (VAST)” in November 2005
【非特許文献１６】W. Sweldens and P. Schroder, “Building your own wavelets at home”, published by ACM SIGGRAPH in “Wavelets in Computer Graphics” in 1996
【非特許文献１７】A. Said and W. Pearlman, “Reversible image compression via multiresolution representation and predictive coding”, published on the occasion of an international conference “Visual Communications and Image Processing” in 1993
【非特許文献１８】B.-J. Kim and W. A. Pearlman, “An embedded wavelet video coder using three-dimensional set partitioning in hierarchical trees (SPIHT)” published on the occasion of an international conference “Data Compression Conference” in 1997
【非特許文献１９】J. M. Shapiro, “An embedded hierarchical image coder using zerotrees of wavelet coefficients”, published on the occasion of another international conference “Data Compression Conference” in 1993
【非特許文献２０】N. Rajpoot, R. Wilson, F. Meyer and R. Coifman, “Adaptive wavelet packet basis selection for zerotree image coding”, published in the review “Institute of Electrical and Electronics Engineers (IEEE) Transactions on image processing” in 2003
【発明の概要】
【発明が解決しようとする課題】
【００３９】
本発明の目的は、特に、多次元テクスチャの次元のすべてにウェーブレット解析(wavelet analysis)の特性を使用して、多次元テクスチャを表現するデータを符号化するための方法およびデバイスを提供することによって、従来技術の難点を解決することである。
【課題を解決するための手段】
【００４０】
この目的のため、本発明は、多次元テクスチャを表現するデータを符号化する方法であって、前記データが、少なくとも3に等しい多数の次元上で最初は編成され、前記次元の少なくとも1つが、前記テクスチャ用の描画パラメータに関連付けられている方法において、
- 前記次元上で前記データをウェーブレット解析するステップと、
- 前記解析の結果から得られたデータを圧縮するステップと
を含むことを特徴とする方法を提案する。
【００４１】
本発明のおかげで、効果的に圧縮された多次元テクスチャ表現が得られ、得られた圧縮レートは、従来技術におけるよりも良好である一方で、良好なレベルの詳細を保持し、低い計算量しか必要とせず、そのことが、描画時にリアルタイムで初期データを再構成することを可能にする。実際のところ、多重線形代数は、合成時、すなわち、復号時に高コストであることが時に判明するが、本発明において使用されるテンソルは中空であり、すなわち、係数のほとんどがゼロであり、そのことは、実際のところ、計算が僅かであることを意味する。
【００４２】
本発明による符号化方法によって得られる高い圧縮レートは、非常に良好な品質のテクスチャ表現を保持することを可能にし、そうした表現は、特に、視点の変位または光の方向の変位に関連するすべての効果を保持する。
【００４３】
これらの利点は、ウェーブレット解析の特性に関連し、ウェーブレット解析は、事前変換を行うことなく、次元(dimensional)および次元間(interdimensional)相関を利用する。加えて、ウェーブレット解析は、初期信号の周波数解析に対応し、初期信号は、周波数帯に分解される。このため、周波数関連のデシメーションに目標を定め、信号の各次元についてそれを行うことが可能である。このことが、本発明によって圧縮されたテクスチャのすべての特異性を保持することを可能にする。
【００４４】
この解析は、多重解像度解析でもあり、スケールによって初期信号の表現を生成し、その際、低周波数係数は、最も粗いレベルと見なされ、高周波数係数からの再構成は、最も精細なレベルと見なされる。この特徴は、同一のテクスチャ表現から異なるレベルの詳細を定めることを可能にする。それは、テクスチャ情報をプログレッシブに表現することも可能にし、そのような表現においては、データは、重要性の順序で編成され、再構成誤差を最小化する係数が、最初に配置される。この表現の原理は、原信号の近似に詳細を追加することに、その本質が存する。
【００４５】
したがって、本発明に従って符号化されたテクスチャデータの、ネットワークを介した送信またはプロセッサへの送信が、例えば、受信データのサイズなど、ある基準に従って中断された場合、すでに送信された情報は、利用可能である。このプログレッシブ表現の別の利点は、計算およびメモリサイズに関して同じ能力を有さずとも、本発明に従って符号化されたテクスチャデータを、バーチャルリアリティセンタ、オフィスコンピュータ、またはモバイル周辺デバイスなど、異なるタイプのグラフィックスデバイスに適合させることが可能なことである。このプログレッシブ表現は、データを非集中アプリケーションにおける送信ビットレートに適合させることも可能にする。
【００４６】
ウェーブレット解析に関連する別の利点は、本発明による符号化を際立って構成可能にすることであり、可能な限り良質の表現が好ましいか、それとも可能な限りコンパクトな表現が好ましいかに応じて、可逆的圧縮または非可逆的圧縮が選択される。
【００４７】
本発明による符号化を、グラフィックス処理ユニット(GPU: graphics processing unit)と呼ばれる現行のグラフィックスプロセッサ、マルチコアプロセッサ、またはパーソナルコンピュータのクラスタなど、並列アーキテクチャデバイスまたはシステムにおいて実行することも可能である。
【００４８】
テクスチャデータのプログレッシブ表現および並列計算の可能性に関連する利点のため、本発明による符号化方法は、耐障害性および大きな情報送信フレキシビリティを必要とする「ピアツーピア」仮想ブラウジングシステムに適合することに留意されたい。本発明による符号化方法は、特に、異なる送信器から、能力が大きく異なる受信器にテクスチャデータを並列に送信することを可能にする。
【００４９】
最後に、本発明による符号化方法は、本発明に従って符号化されたテクスチャデータへの動的で高速なアクセスを可能にする。実際のところ、本発明によるデータの符号化は、対象領域の局所的再構成を可能にするので、テクスチャが描画されるとき、同一のテクスチャの新しい画像ごとに、必ずしもすべての初期データを再構成する必要はない。
【００５０】
好ましい一特徴によれば、本発明による符号化方法は、多次元テクスチャを表現する前記データを所定の数の次元に従って再編成するための予備ステップを含む。
【００５１】
テクスチャデータを再編成するこのステップは、特に次元の数を減少させることによって、ウェーブレットへの分解を簡略化することを可能にする。
【００５２】
好ましい別の特徴によれば、前記再編成ステップにおいて、前記データは、前記データの2つの連続するサンプルの間の、少なくとも1つの次元に従った相関を最大化するように配列される。
【００５３】
ウェーブレットへの分解の前に、サンプルの間の相関を最大化することによって、データを符号化する際のデータの圧縮が改善される。
【００５４】
好ましい別の特徴によれば、多次元テクスチャを表現する前記データは、YUV色符号化方式によって色を表現する。
【００５５】
本発明に従って符号化されたテクスチャの色を表現するための、従来の赤/緑/青RGB符号化方式に代わる、YUV色符号化方式の使用は、同等の視覚的品質に対して、より良い圧縮レートを得ることを可能にする。実際のところ、人間の目は、彩度変化に対してあまり敏感でなく、輝度に対してより敏感であるので、この選択は、符号化に関連する量子化ステップにおいて、彩度を表現するUおよびVパラメータを、輝度を表現するYパラメータよりも精度を低くして符号化することを可能にする。
【００５６】
好ましい別の特徴によれば、本発明による符号化方法の圧縮ステップは、「ゼロツリー」型符号化(“zerotree” type coding)を使用する。
【００５７】
このタイプの符号化は、ウェーブレット解析されたテクスチャデータの圧縮を最適化することを可能にする。
【００５８】
本発明はまた、多次元テクスチャを表現するデータを復号する方法であって、前記データが、少なくとも3に等しい多数の次元上で最初は編成され、前記次元の少なくとも1つが、前記テクスチャ用の描画パラメータに関連付けられている方法において、
- 前記データを伸張するステップと、
- 前記伸張から得られたデータを前記次元上でウェーブレット合成するステップと
を含むことを特徴とする方法に関する。
【００５９】
本発明はまた、少なくとも3に等しい多数の次元上で編成されたデータによって最初は表現される多次元テクスチャを表す信号であって、前記次元の少なくとも1つが、前記テクスチャ用の描画パラメータに関連付けられている信号において、前記データが、前記次元上でのウェーブレット解析によって、そして前記解析の結果から得られたデータの圧縮によって符号化されていることを特徴とする信号に関する。
【００６０】
本発明はまた、多次元テクスチャを表現するデータを符号化するためのデバイスであって、前記データが、少なくとも3に等しい多数の次元上で最初は編成され、前記次元の少なくとも1つが、前記テクスチャ用の描画パラメータに関連付けられているデバイスにおいて、
- 前記次元上で前記データをウェーブレット解析する手段と、
- 前記解析手段から得られたデータを圧縮する手段と
を含むことを特徴とするデバイスに関する。
【００６１】
本発明はまた、多次元テクスチャを表現するデータを復号するためのデバイスであって、前記データが、少なくとも3に等しい多数の次元上で最初は編成され、前記次元の少なくとも1つが、前記テクスチャ用の描画パラメータに関連付けられているデバイスにおいて、
- 前記データを伸張する手段と、
- 前記伸張手段から得られたデータを前記次元上でウェーブレット合成する手段と
を含むことを特徴とするデバイスに関する。
【００６２】
復号方法、信号、符号化デバイス、および復号デバイスは、本発明による符号化方法の利点と類似する利点を提供する。
【００６３】
本発明は、最後に、コンピュータプログラムに関し、コンピュータプログラムは、それがコンピュータ上で実行されたときに、本発明による符号化方法または本発明による復号方法を実施するための命令を含む。
【００６４】
他の特徴および利点は、図面を参照しながら説明される好ましい実施形態について読むことから明らかになる。
【図面の簡単な説明】
【００６５】
【図１】テクスチャをモデル化するBTFの収集のサンプリングを表す図である。
【図２】このサンプリングの値を示す表である。
【図３】このBTFの解釈を表す図である。
【図４】本発明による符号化方法および復号方法の一実施形態を表す図である。
【図５】この実施形態で説明される、本発明による符号化方法のステップを表す図である。
【図６】テクスチャデータのウェーブレットへの分解のレベルを表す図である。
【図７】テクスチャデータのウェーブレットへの分解を表す図である。
【図８】テクスチャデータのウェーブレットパケットへの分解を示すツリーを表す図である。
【図９】ウェーブレットパケットへのこの分解の要素へのコストの割り当てを表す図である。
【図１０】テクスチャデータのウェーブレットパケットへの分解を示す別のツリーを表す図である。
【図１１】本発明に従って符号化されたテクスチャデータの表現のためのフォーマットを表す図である。
【図１２】この実施形態で説明される、本発明による復号方法のステップを表す図である。
【発明を実施するための形態】
【００６６】
本発明の好ましい一実施形態によれば、本発明による符号化方法は、6次元BTFの形式で表現された多次元テクスチャを圧縮するために使用される。しかし、ウェーブレットへの分解は、任意の次元数に拡張できるので、本発明による方法は、例えば、4次元の「多項式テクスチャマップ」または7次元の「時間変化BTF」の形式など、異なる仕方で表現された多次元テクスチャにも適用可能である。
【００６７】
このテクスチャを表現するBTFは、図1に表された収集プロセスの結果である。BTFは、ショットからなる半球に従ってサンプリングされる。したがって、原点Oとx、y、z軸からなる直交座標系では、テクスチャの各点は、視点の方向を極座標のθvおよびφvとし、光の方向を極座標のθlおよびφlとして撮影される。
【００６８】
図2の表TABは、与えられた緯度θvおよびθlについて撮影された写真の数を示している。したがって、緯度θvが15度に等しい場合、角度φvは、72度ずつ変化し、これは、この緯度では5枚の写真が撮影されることに対応する。したがって、第1列のサンプルの数の値を合計すると、サンプリング用に使用される、80個の視点の方向の値と、80個の光の方向の値が存在し、これは、6400個の画像からなるBTFを生成する。
【００６９】
図3は、BTFのこの解釈を示しており、これら6400個の画像のうちの画像Iの各々は、パラメトリック座標xおよびyにおけるテクスチャを表し、視点の方向(θv, φv)および光の方向(θl, φl)に対応する。
【００７０】
BTFに類似したデータは、インターネットアドレスhttp://btf.cs.uni-bonn.de/のボン大学のサイトからダウンロードすることができ、これらのデータの収集モードは、2005年11月に会議「6th International Symposium on Virtual Reality, Archaeology and Cultural Heritage (VAST)」の際に発表された、「Rapid synchronous acquisition of geometry and BTF for cultural heritage artefacts」と題する、G. Muller、G. H. Bendels、およびR. Kleinによる論文においてより完全に説明されていることに留意されたい。
【００７１】
加えて、サンプリングは規則的ではなく、また境界領域を有するので、第1世代ウェーブレットは、このタイプのサンプリングには適しておらず、そのため、本発明による符号化方法は、明らかに「第2世代」型ウェーブレットであるウェーブレットを使用する。
【００７２】
BTFのデータを形成する画像Iは、図4に示されたデータベースBDD内に保存され、この実施形態では、本発明による符号化方法は、このデータベースにアクセスするコンピュータORDにおいてソフトウェア方式で実施される。本発明による符号化方法に必要な計算は、コンピュータORDのプロセッサCPUにおいて実行される。一変形として、符号化に必要な計算がそれに基づいて実行されるデータのサイズのスケールが与えられた場合、これらの計算は、並列で動作する複数のコンピュータ上で実行される。
【００７３】
図5を参照すると、本発明による符号化方法が、ステップC1からステップC3を含むアルゴリズムの形式で表されている。
【００７４】
第1のステップC1は、BTFのデータの再編成化であり、BTFのデータは、最初は6次元で編成されるが、計算の複雑さを制限するために、次元数を削減される。この次元数の選択は、圧縮データを使用するアプリケーションに依存し、複雑な計算が少ない方が好ましいか、それとも圧縮レートが大きい方が好ましいかによって決まる。実際のところ、より多くの次元が維持されるほど、より大きな次元間コヒーレンスが利用され、圧縮率はより大きくなる。この実施形態では、BTFのデータの4次元への再編成化が選択され、速度と圧縮の間のトレードオフは、以下の式で表され、
BTF(x, y, θv, φv, θl, φl) = BTF(x, y, v, l)
ここで、
- vは、最初にBTFにおいて視点の方向を定義した初期極座標θvおよびφvの、単一次元上への射影であり、
- lは、最初にBTFにおいて光の方向を定義した初期極座標θlおよびφlの、単一次元上への射影である。
【００７５】
一変形として、BTFのデータは再編成されず、その場合、ウェーブレット解析は6つの次元上で行われる。この変形では、例えば、2つのタイプのウェーブレットが使用される。
- 解析フィルタを視点の方向および光の方向に従ったBTFのサンプリングに適合させるための、2つの非分離次元(inseparable dimension)におけるウェーブレット。
- 空間解析のための、1つの分離可能次元(separable dimension)におけるウェーブレット。
【００７６】
別の変形実施形態では、BTFの初期データは、「反射場(reflectance field)」分解に従って3次元に再編成され、言い換えると、データは、視点vごとに表現され、光の方向が、単一次元上に射影される。
BTF(x, y, θv, φv, θl, φl) = {BTFv(x, y, l)}, ∀v
【００７７】
別の変形実施形態では、BTFのデータは、5次元に再編成され、光の方向が、単一次元上に射影される。
BTF(x, y, θv, φv, θl, φl) = BTF(x, y, θv, φv, l)
【００７８】
後者の変形は、例えば、視点の方向が光の方向より多くサンプリングされる場合に関心を引く。
【００７９】
BTFのデータを再編成するためのこのステップC1では、2重項(θv, φv)に対応する射影vは、θvおよびφvによる昇順で分類され、すなわち、視点vの次元に応じて、画像Iは、以下のサンプリング順序、すなわち、(0, 0), (15, 0),(15, 72),…,(75, 345)の順序で分類される。同様に、2重項(θl, φl)に対応する射影lは、θlおよびφlによる昇順で分類される。
【００８０】
一変形として、画像Iは、2つの連続する画像の間の、光の方向に依存する相関を最大化するように分類される。この分類は、例えば、同一の視点の方向を共通して有するすべての画像において、以下のように行われる。
- この集合の中からルート画像が、例えば、極座標における2重項(0, 0)に対応する、射影lの画像が選択される。
- その後、次の画像が先行画像から反復的に探索され、この画像は、先行画像とまだ分類されていない画像の集合との間の差を最小化する画像に対応する。
【００８１】
射影lに対応する軸に従った尤度の順序による画像Iのこの分類は、その後、ステップC3における圧縮を改善することを可能にする。
【００８２】
BTFのデータは、収集時にRGB形式で符号化されることに留意されたい。現在、この色符号化形式は、知覚因子(perception factor)を最大限利用することを可能にしない。実際のところ、人間の目は、輝度変化に特に敏感であるので、このステップC1は、好ましくは、RGB色空間からYUV色空間への変更を含み、YUV色空間において、Yは輝度を表し、UおよびVは彩度を表す。そのような修正のポイントは、ステップC3における量子化に関して、彩度と比べてより大量の情報を輝度に提供することにあるので、この変更は、残りの処理動作に影響を及ぼす。
【００８３】
符号化方法の第2のステップC2は、ステップC1において選択された4つの次元上で正当に再編成および再フォーマットされたデータのウェーブレット解析である。
【００８４】
「ウェーブレット解析」という表現は、連続的なウェーブレット変換によって、信号がウェーブレットまたはウェーブレットのパケット(packet of wavelets)に分解されることを意味することに留意されたい。したがって、ウェーブレット解析は、少なくとも1つのウェーブレット分解を含む。
【００８５】
このウェーブレット分解は、ステップC1において選択された編成化に従って行われる。上で指摘されたように、サンプリング間隔の不規則性および境界境域のため、第2世代のウェーブレットの使用が必要である。これらの間隔を規則的にするために、ステップC1において、新しいサンプルが合成されることを仮定したとしても、解析領域は、依然として境界を有したままであり、そのため、第2世代のウェーブレットが、依然として必要であることにも留意されたい。
【００８６】
この実施形態では、簡略化のため、単純な1次「不平衡ハール変換(Unbalanced Haar Transform)」型のウェーブレット変換が使用され、この変換は、「リフティングスキーム(lifting scheme)」法を使用して容易に構成される直交第2世代ウェーブレットを利用する。この構成は、1996年にACM SIGGRAPHによって「Wavelets in Computer Graphics」に発表された、「Building your own wavelets at home」と題する、W. SweldensおよびP. Schroderによる講座において詳細に説明されている。これらのウェーブレットは分離可能であるので、各次元上で分解が順々に実行され、そのことが、ステップC1において選択されたデータの編成化から独立であり続けることを可能にする。さらに、ハールウェーブレット基底(Haar wavelet base)を使用することによって、分解は2つの連続するサンプル上で実行され、言い換えると、境界付近での分解の計算は、ダミーサンプルの付加を必要としないので、境界における適合は必要でない。最後に、この分解を簡略化するため、およびステップC1における4次元へのデータの再編成化のため、このステップC2では、サンプリング間隔は規則的であると見なすことができる。
【００８７】
一変形として、BTFのデータが、4より大きな多数の次元に従って、ステップC1において再編成される場合、不規則的な間隔を規則的な間隔に変換し、結局は規則的なケースとなる状況を得るために、ウェーブレットへの分解時に、計算に加重が施される。この加重は、ウェーブレットへの分解を現実に、より忠実にすることを可能にし、すなわち、伸張時に、新しい非常にリアリスティックなテクスチャビュー(texture view)を合成するために、伸張データを使用することができる。
【００８８】
一変形として、より高次でより複雑な基底付きウェーブレット(higher order, more complex based wavelet)が、この分解において使用される。これは、計算がより複雑でより長くなるという犠牲を払うが、圧縮にも関わらず、解像度が非常に良好なテクスチャ表現を保持することを可能にする。例えば、双直交ウェーブレット(biorthogonal wavelet)が使用され、このウェーブレットは、「リフティングスキーム」法を使用する構成の容易さのため実用的であり、またはテクスチャの空間的配置を同一次元空間における幾何学と見なすことによって、幾何学的ウェーブレット(geometrical wavelet)が使用される。例えば、ステップC1において3次元上で再編成されたデータにおいて、基本要素として四辺形を使用し、「バタフライ」法などの従来の細分技法を適用する、メッシュベースのウェーブレットが使用される。一般に、2つのゼロモーメントを有するウェーブレット基底の使用は、再生品質と計算速度との折り合いをつけるための良好なトレードオフである。
【００８９】
より具体的には、本発明による符号化方法の主要な変形実施形態では、ステップC2におけるウェーブレットへの分解は、図6の方式に従って、各分解レベルjにおいて行われる。Sjを、ステップC1の終了時に得られた再編成データからの、ハール基底におけるウェーブレットへの第jレベルの分解のデータの集合
【００９０】
【数４】
2010518667.tif 000006
【００９１】
から形成された信号とし、ここで、
- kは、空間座標の軸xに従った、信号の第kの値を表すインデックスであり、
- pは、空間座標の軸yに従った、信号の第pの値を表すインデックスであり、
- mは、射影の軸lに従った、信号の第mの値を表すインデックスであり、
- nは、射影の軸vに従った、信号の第nの値を表すインデックスである。
【００９２】
分解は、他の3つの次元の各々が与えられた値に設定された場合に、1つの次元に従ったBTFのすべての値に各々が対応するデータブロックごとに、各次元において順々に行われる。これらの次元の処理の順序は、BTFのデータの相関に従って選択される。テクスチャの空間相関は、光の方向の変化における相関よりも強いので、それは、視点の方向の変化におけるよりもさらに強く、ウェーブレットへの分解は、最初にインデックスk、次にインデックスp、次にインデックスm、最後にインデックスnに従って実行される。
【００９３】
したがって、ウェーブレットへの分解時に、信号Sjは、最初に空間座標の軸xに従って、以下の機能の作用を受ける。
- 「分離」オペレータsは、関連する方向において偶数インデックスのデータと奇数インデックスのデータを分離し、したがって、ここではインデックスkに従うとすると、
【００９４】
【数５】
2010518667.tif 000007
【００９５】
であり、ここで、k'は、
kが偶数の場合は、k = 2k'
kが奇数の場合は、k = 2k' + 1
によって定義される整数インデックスである。
- ローパスフィルタhは、関連する方向に従って、データ
【００９６】
【数６】
2010518667.tif 000008
【００９７】
の平均を実行し、これは、
【００９８】
【数７】
2010518667.tif 000009
【００９９】
によって定義されるデータ
【０１００】
【数８】
2010518667.tif 000010
【０１０１】
を生成する。
- ハイパスフィルタgは、関連する方向に従って、データ
【０１０２】
【数９】
2010518667.tif 000011
【０１０３】
の間の差を計算し、これは
【０１０４】
【数１０】
2010518667.tif 000012
【０１０５】
によって定義されるデータ
【０１０６】
【数１１】
2010518667.tif 000013
【０１０７】
を生成する。
【０１０８】
現実には、分解は、「リフティングスキーム」法によって実行され、これは、ハール基底における分解の場合、以下のように、最初に、信号Sjの2つの値の間の差が計算され、次に、これら2つの値の和がこの差から計算されることを意味する。
【０１０９】
【数１２】
2010518667.tif 000014
【０１１０】
次に
【０１１１】
【数１３】
2010518667.tif 000015
【０１１２】
これは、プロセッサCPUが、
【０１１３】
【数１４】
2010518667.tif 000016
【０１１４】
の値と同じ場所に
【０１１５】
【数１５】
2010518667.tif 000017
【０１１６】
の値を保存することを可能にし、その後、
【０１１７】
【数１６】
2010518667.tif 000018
【０１１８】
の値と同じ場所に
【０１１９】
【数１７】
2010518667.tif 000019
【０１２０】
の値を保存することを可能にする。これは、プロセッサCPUレベルにおいて、メモリ空間を節約することを可能にする。さらに、2つの連続するサンプルというこのケースでは、ウェーブレットへの分解の局所性が、「アウトオブコア(out of core)」方式で、すなわち、処理されるすべてのデータがメインメモリに完全に格納されずに、分解を実行することを可能にする。この特徴は、データが複数のプロセッサによって並列に処理されることも可能にする。さらに、従来技術の方法とは異なり、解析領域は、処理されるためにその全体が区分化される必要はない。
【０１２１】
次に、データ
【０１２２】
【数１８】
2010518667.tif 000020
【０１２３】
および
【０１２４】
【数１９】
2010518667.tif 000021
【０１２５】
は、同じ機能の作用を受けるが、それはインデックスpに従ったものである。
- オペレータsは、偶数インデックスか、それとも奇数インデックスかに従って、データ
【０１２６】
【数２０】
2010518667.tif 000022
【０１２７】
および
【０１２８】
【数２１】
2010518667.tif 000023
【０１２９】
を分離し、
- フィルタhは、データ
【０１３０】
【数２２】
2010518667.tif 000024
【０１３１】
からデータ
【０１３２】
【数２３】
2010518667.tif 000025
【０１３３】
を、データ
【０１３４】
【数２４】
2010518667.tif 000026
【０１３５】
からデータ
【０１３６】
【数２５】
2010518667.tif 000027
【０１３７】
を生成し、
- フィルタgは、データ
【０１３８】
【数２６】
2010518667.tif 000028
【０１３９】
からデータ
【０１４０】
【数２７】
2010518667.tif 000029
【０１４１】
を、データ
【０１４２】
【数２８】
2010518667.tif 000030
【０１４３】
からデータ
【０１４４】
【数２９】
2010518667.tif 000031
【０１４５】
を生成し、
ここで、p'は、
pが偶数の場合は、p = 2p'
pが奇数の場合は、p = 2p' + 1
によって定義される整数インデックスである。
【０１４６】
次に、取得されたデータ
【０１４７】
【数３０】
2010518667.tif 000032
【０１４８】
および
【０１４９】
【数３１】
2010518667.tif 000033
【０１５０】
のすべてが、再び、同じ機能の作用を受けるが、それはインデックスmに従ったものである。したがって、データ
【０１５１】
【数３２】
2010518667.tif 000034
【０１５２】
の分解のみが説明されるとすると、
- オペレータsは、偶数インデックスか、それとも奇数インデックスかに従って、以下のように、これらのデータを分離し、
【０１５３】
【数３３】
2010518667.tif 000035
【０１５４】
ここで、m'は、
mが偶数の場合は、m = 2m'
mが奇数の場合は、m = 2m' + 1
によって定義される整数インデックスであり、
- フィルタhは、データ
【０１５５】
【数３４】
2010518667.tif 000036
【０１５６】
から、
【０１５７】
【数３５】
2010518667.tif 000037
【０１５８】
によって定義されるデータ
【０１５９】
【数３６】
2010518667.tif 000038
【０１６０】
を生成し
- フィルタgは、データ
【０１６１】
【数３７】
2010518667.tif 000039
【０１６２】
から、
【０１６３】
【数３８】
2010518667.tif 000040
【０１６４】
によって定義されるデータ
【０１６５】
【数３９】
2010518667.tif 000041
【０１６６】
を生成する。
【０１６７】
最後に、インデックスmに従った分解によってこのように取得されたデータのすべてが、インデックスnに従って分解される。データ
【０１６８】
【数４０】
2010518667.tif 000042
【０１６９】
の分解のみが説明されるとすると、
- オペレータsは、以下のように、偶数インデックスのデータおよび奇数インデックスのデータを分離し、
【０１７０】
【数４１】
2010518667.tif 000043
【０１７１】
ここで、n'は、
nが偶数の場合は、n = 2n'
nが奇数の場合は、n = 2n' + 1
によって定義される整数インデックスであり、
- フィルタhは、インデックスnに従って、データ
【０１７２】
【数４２】
2010518667.tif 000044
【０１７３】
の平均を実行し、これは、
【０１７４】
【数４３】
2010518667.tif 000045
【０１７５】
によって定義されるデータ
【０１７６】
【数４４】
2010518667.tif 000046
【０１７７】
を生成し、
- フィルタgは、インデックスnに従って、データ
【０１７８】
【数４５】
2010518667.tif 000047
【０１７９】
の間の差を計算し、これは、
【０１８０】
【数４６】
2010518667.tif 000048
【０１８１】
によって定義されるデータ
【０１８２】
【数４７】
2010518667.tif 000049
【０１８３】
を生成する。
【０１８４】
インデックスnに従ったこの最後の分解において生成されたデータのすべては、信号Sjのウェーブレットへの分解の結果、またはステップC1の終了時に得られたデータの、ウェーブレットへの第j-1レベルの分解のデータを形成する。この結果、低周波数で低解像度の信号Sj-1を形成するデータ
【０１８５】
【数４８】
2010518667.tif 000050
【０１８６】
と、より高い周波数の信号dj-1を形成する他のデータが、区別される。
【０１８７】
一変形実施形態では、上で詳細に説明された分解は、ステップC1において得られたデータから形成された初期信号SJの、ウェーブレットへの従来の分解である。図7に表されたこの分解では、低周波数信号SJ-1だけが、次のレベルの分解にさらに分解され、詳細な信号dJ-1は、保持される。したがって、分解の第J-1レベルでは、信号SJ-1は、ウェーブレットに分解されて、信号SJ-1よりも周波数が低い信号SJ-2と、信号dJ-1よりも周波数が低い信号dJ-2を生成し、その後、次のレベルの分解において、信号SJ-2自体が、ウェーブレットに分解され、それ以降も同様である。信号S1におけるウェーブレットへの最終的な分解は、信号d0およびS0を生成する。ステップC1の終了時に得られたデータは、YUV形式に従って符号化され、80個の視点の方向と80個の光の方向に従って分類された画像Iであるので、これらの画像が256*256の解像度をもつと仮定すると、プロセスは、例えば、ウェーブレットへの第3レベルの分解後に停止する。その後、ウェーブレット解析の結果が、信号S0およびd0からdJ-1によって形成され、ここで、Jは3である。低周波数信号S0は、YUV色空間において符号化された10*10*32*32個の色を含む。
【０１８８】
本発明による符号化方法の主要な変形実施形態では、テクスチャを最適に符号化するために、ステップC1の終了時に得られたデータは、実際には、このステップC2において、ウェーブレットのパケットに分解される。そのような分解は、低周波数信号Sjばかりでなく、高周波数信号djも再帰的に分解することを可能にする。この分解は、図8のツリーに表されている。ツリーのルートは、ステップC1の終了時に得られたデータを含む初期信号SJに対応する。次のレベルは、ウェーブレットへの変換の反復の結果であり、すなわち、低周波数信号SJ-1と、高周波数信号dJ-1である。その後、これらの信号の再帰的な分解が、ツリーのより低いレベルで完了する。したがって、信号SJ-1の分解は、2つの信号SJ-2およびdJ-2を与え、一方、信号dJ-1の分解も、2つの信号
【０１８９】
【数４９】
2010518667.tif 000051
【０１９０】
および
【０１９１】
【数５０】
2010518667.tif 000052
【０１９２】
を与える。
【０１９３】
ウェーブレットのパケットへのこの分解は、符号化のエントロピ、所定の閾値、または符号化によって生じる歪みなど、与えられた基準に従って、最適な分解ツリーを選択することを可能にする。このため、コスト関数が、ウェーブレットへの各分解、すなわち、図8に表されたツリーの各ノードに割り当てられる。このコスト関数は、ツリーを最適化するように選択された基準に対応する。
【０１９４】
例えば、閾値を下回る値の数を超える分割を好むように選択が行われる場合、信号Sjに対応する分割ノードにおけるコスト関数の値は、値
【０１９５】
【数５１】
2010518667.tif 000053
【０１９６】
を有し、ここで、
【０１９７】
【数５２】
2010518667.tif 000054
【０１９８】
の場合。それ以外の場合は、
【０１９９】
【数５３】
2010518667.tif 000055
【０２００】
であり、tは、この閾値に対応する。
【０２０１】
その場合、ツリーの各親について、その子のコストの合計が、親のコストと比較される。この合計が親のコストより低い場合、子の分割は保持され、それ以外の場合、符号化方法における親の分割後のところで、プロセスは停止させられる。
【０２０２】
例えば、図8の各ノードがその分解のコストによって置き換えられた図9のツリーにおいては、ウェーブレットのパケットへの分解は、ツリーの左側ブランチの信号SJ-2およびdJ-2のところで停止させられ、それらのコストの合計は親信号SJ-1のコスト以上であるので、それらは分解されない。
【０２０３】
本発明のこの実施形態では、分解のツリーに加重するためにエントロピ基準を使用するように選択され、信号Sjに対応する分解ノードにおけるコスト関数の値は、値
【０２０４】
【数５４】
2010518667.tif 000056
【０２０５】
を有する。
【０２０６】
このコスト関数は、シャノンのエントロピを定義し、このエントロピは、情報の量、すなわち、分解における異なる係数の量を測定する。そのようにして、より低いコストのエントロピ分解が保持されるので、この基準は、本発明による符号化方法にとって有用である。
【０２０７】
一変形として、本発明に従って符号化されたBTFが、最初は整数で表現される場合、このステップC2において実行されるウェーブレット解析は、ウェーブレットへの整数分解またはウェーブレットのパケットへの整数分解である。そのような方法は、1993年に国際会議「Visual Communications and Image Processing」の際に発表された、A. SaidおよびW. Pearlmanによる論文「Reversible image compression via multiresolution representation and predictive coding」において説明されている。これはさらに、この解析の結果のサイズを制限することによって、ウェーブレット解析を最適化する。したがって、実際のところ、解析から得られるデータは、より僅かなリソースを用いて表現され、整数のバイト単位のサイズは、小数のそれよりも小さい。どのウェーブレット基底も、そのような整数分解を実行するように変更できることに留意されたい。例えば、インデックスkに従った信号Sjのハールウェーブレットによる変換は、
【０２０８】
【数５５】
2010518667.tif 000057
【０２０９】
次に
【０２１０】
【数５６】
2010518667.tif 000058
【０２１１】
となり、ここで、
【０２１２】
【数５７】
2010518667.tif 000059
【０２１３】
は、デフォルト除算(default division)uの整数値を表す。
【０２１４】
最後に、本発明による符号化方法のステップC3は、ステップC2の終了時に得られたデータ、すなわち、ステップC1において再編成および再フォーマットされたBTFのデータのウェーブレット解析の結果の圧縮である。
【０２１５】
この実施形態では、この圧縮は、ウェーブレットへの分解のツリー構造を利用する、「ゼロツリー」符号化を使用する。当業者に知られたこの符号化技法は、例えば、以下の論文、すなわち、
- 1997年に国際会議「Data Compression Conference」の際に発表された、B.-J. KimおよびW. A. Pearlmanによる、「An embedded wavelet video coder using three-dimensional set partitioning in hierarchical trees (SPIHT)」、
- 1993年に別の国際会議「Data Compression Conference」の際に発表された、J. M. Shapiroによる、「An embedded hierarchical image coder using zerotrees of wavelet coefficients」
において詳細に説明されている。
【０２１６】
この符号化技法の原理は、信号Sjに含まれる低解像度係数は、信号djに含まれる詳細係数と比べて大きく、jが小さくなればなるほど詳細係数は大きくなる、と考えることである。これは、データの符号化を実行するために、これらの係数のスケール間依存性(interscale dependency)、すなわち、2つの分解レベルの間の依存性を使用することを可能にする。
【０２１７】
より具体的には、最も粗いレベルにおける詳細係数は、同一の方向においてより高いレベルに配置された多数の係数に関連付けられ、次にこれらの係数は、順々に次のレベルに関連付けられ、以降も同様である。この数は、2のべきに等しく、このべきは、解析空間の次元に等しい。
【０２１８】
例えば、保持されたウェーブレットのパケットへの分解が、図10に示された分解である場合、すなわち、ステップC2の終了時に得られたデータが、信号
【０２１９】
【数５８】
2010518667.tif 000060
【０２２０】
および
【０２２１】
【数５９】
2010518667.tif 000061
【０２２２】
のデータである場合、信号dJ-3の係数は、信号dJ-2の16個の係数に関連付けられる。
【０２２３】
「ゼロツリー」符号化法は通常はウェーブレットへの分解に適用されるので、それをウェーブレットのパケットへの分解に適用するためには、2003年に評論誌「Institute of Electrical and Electronics Engineers (IEEE) Transactions on image processing」に発表された、N. Rajpoot、R. Wilson、F. Meyer、およびR. Coifmanによる、論文「Adaptive wavelet packet basis selection for zerotree image coding」に詳細に説明されているような、僅かな適合が必要であることに留意されたい。
【０２２４】
実際のところ、「ゼロツリー」符号化における階層の意味は、ウェーブレットへの従来の分解におけるものともはや同じではない。したがって、分解レベルを進めていく際に係数における実際の減少を保持するために、1つのレベルの係数を別のレベルに組み込むためのある規則が、追加されなければならない。
【０２２５】
したがって、図10において、信号dJ-2が最終レベルJ-3にさらに分解される場合、信号dJ-3の係数は、ステップC2の終了時に保持されていない信号dJ-2の16個の係数ではなく、信号dJ-2の分解から得られる16個の信号の各々の係数に関連付けられる。
【０２２６】
同様に、上で説明されたのと同じ規則を信号dJ-2に適用することによって、信号dJ-2の係数は、信号dJ-1の分解から得られる16個の信号の各々の係数に関連付けられる必要がある。今度は、この分解から得られた信号
【０２２７】
【数６０】
2010518667.tif 000062
【０２２８】
自体が、とりわけ、信号dJ-2のレベルより粗いレベルの信号
【０２２９】
【数６１】
2010518667.tif 000063
【０２３０】
に分解される。「ゼロツリー」符号化原理に従うため、信号
【０２３１】
【数６２】
2010518667.tif 000064
【０２３２】
および
【０２３３】
【数６３】
2010518667.tif 000065
【０２３４】
の係数は、信号dJ-2の係数ではなく、信号dJ-3の係数に関連付けられる。したがって、信号
【０２３５】
【数６４】
2010518667.tif 000066
【０２３６】
および
【０２３７】
【数６５】
2010518667.tif 000067
【０２３８】
の係数の値は、信号dJ-3の係数の理論的にはより大きい値に従って符号化される。「ゼロツリー」符号化によって実行されるこの内在的な量子化は、「逐次近似による量子化(quantization by successive approximation)」とも呼ばれる。
【０２３９】
「ゼロツリー」符号化の完了時に、ビットのストリームが、ステップC2において実行されたウェーブレットパケットへの分解を符号化するステップC3の終了時に得られる。このようにして得られたデータは、ステップC2の終了時におけるよりもはるかに小さいサイズを有する。実際のところ、ウェーブレット解析がゼロに近い多くの係数を生成するという事実に加えて、スケールにつれての係数の減少を利用するという事実は、「ゼロツリー」符号化法が、高い圧縮率を獲得することを可能にする。さらに、得られたデータは、図11に表されるように、重要性の順序で編成される。データZT0は、最も粗い詳細レベルに対応する係数を符号化し、一方、データZT1は、僅かに粗さの低いレベルで詳細係数を符号化し、データZT2は、さらに精細なレベルで詳細係数を符号化し、以降も同様である。データZT0は、原データを最も多く説明する情報に対応する。したがって、データZT0の後に配置されたデータは、これらのデータZT0に含まれるテクスチャの粗い表現を前進的に精細化することを可能にするので、テクスチャのプログレッシブ表現が得られる。したがって、ステップC3の終了時に得られたこの表現の最初のデータだけが送信される場合、テクスチャの粗い表現が獲得される。
【０２４０】
一変形として、このステップC3において、「ゼロツリー」符号化を使用する代わりに、動的な「ハフマン(Huffman)」型の符号化が、非一様スカラ量子化と一緒に使用される。特に、ステップC2から得られたデータのY成分は、UおよびV成分よりも小さく量子化される。例えば、この量子化のステップは、固定圧縮データのサイズにとって適切に設定される。「レートアロケーション(Rate Allocation)」と呼ばれるこの方法は、「ジョイントフォトグラフィックエキスパートグループ(JPEG: Joint Photographic Experts Group)2000」規格で使用されている。このため、例えば、所望の圧縮レートが達成されるまで、量子化ステップが反復的に計算される。例えば、ネットワークを介して固定ビットレートで圧縮データを送信する場合、この後処理が有益である。さらに、そのような量子化は、テクスチャの関心を引くある領域が識別される場合、そのような領域を、あまり関心を引かない他の領域と比べて、小さく量子化するように適合することができる。
【０２４１】
この変形は、伸張時の計算の複雑さを低減することを可能にするが、圧縮率に関しては、本発明の主要な変形実施形態よりも有効性ははるかに低い。本発明の主要な変形の「ゼロツリー」符号化を動的な「ハフマン」型の符号化と結合することも可能であるが、これは、得られたデータの圧縮率をごく僅か改善するに過ぎないことに留意されたい。
【０２４２】
今度は、本発明による復号方法が、図4および図12と併せて説明される。ステップC3の終了時に得られたデータは、コンピュータORDによって、通信ネットワークRESを介して、リモート端末Tに送信される。対応するデータストリームFは、図11に関連して上で説明されたような重要性の順序で編成された「ゼロツリー」符号化データの表現を含む。
【０２４３】
データストリームFを受信すると、端末Tは、すべての受信データを、または端末Tが限られたメモリ容量しかもたない場合、もしくはデータZT2が送信された直後に通信障害がデータの送信を遮断した場合、例えば、データZT0、ZT1、およびZT2など、最初の方のデータをメモリ内に保存する。
【０２４４】
端末Tは、データストリームFを搬送する信号をチャネル復号した後、図12に表されたステップD1からステップD3に従って、受信データを復号する。
【０２４５】
ステップD1は、受信データの伸張である。このため、端末Tは、ステップC3において符号化のために使用されたアルゴリズムの反対である「ゼロツリー」復号アルゴリズムを使用し、すなわち、端末Tは、ウェーブレットパケットへの分解から得られたデータを取り出すために、解像度の1つのレベルから別のレベルへの係数の関連付けについて同じ規則を使用する。データZT0、ZT1、およびZT2だけが伸張される場合、ステップC2のウェーブレットパケットへの分解の第1のレベルの解像度の係数だけが取得される。
【０２４６】
さらに、「ゼロツリー」符号化時には、ウェーブレット解析の局所性が保持される。したがって、復号時に、端末Tは、例えば、視点のある方向または光のある方向からだけテクスチャを描画するために、受信データの一部だけを復号することができる。
【０２４７】
ステップD2は、ステップD1において伸張されたデータのウェーブレット合成である。「ゼロツリー」符号化は、ステップC2において保持されたウェーブレットパケット分解ツリーの構造に依存するので、端末Tは、ステップC1の終了時に得られた再編成および再フォーマットテクスチャデータの全部または一部を容易に再構成する。このために必要なことは、次元ごとに、ウェーブレットパケットへの分解の順序で、逆ハール変換を実行することだけである。
【０２４８】
最後に、ステップD3は、ステップD2の終了時に得られたデータの、6次元への再編成化である。したがって、端末Tは、BTFの形式で表現されたテクスチャを獲得し、そのテクスチャは、画面上で描画を実行するために、直接使用することができる。ステップD2において、データZT0、ZT1、およびZT2だけが合成された場合、このBTFは、実際には、本発明に従って圧縮されたテクスチャの粗い表現である。
【符号の説明】
【０２４９】
ORD  コンピュータ
CPU  プロセッサ
BDD  データベース
RES  通信ネットワーク
T  端末
F  データストリーム
【図１】
2010518667.tif 000068
【図２】
2010518667.tif 000069
【図３】
2010518667.tif 000070
【図４】
2010518667.tif 000071
【図５】
2010518667.tif 000072
【図６】
2010518667.tif 000073
【図７】
2010518667.tif 000074
【図８】
2010518667.tif 000075
【図９】
2010518667.tif 000076
【図１０】
2010518667.tif 000077
【図１１】
2010518667.tif 000078
【図１２】
2010518667.tif 000079
【国際調査報告】
2010518667.tif 000080
2010518667.tif 000081
2010518667.tif 000082
2010518667.tif 000083
2010518667.tif 000084
2010518667.tif 000085