(57)【特許請求の範囲】
【請求項１】
任意の形状のオブジェクトを表す画素(ピクセル)に対応する入力データを前処理する方法であって、前記入力データは前記各オブジェクトについて、前記オブジェクトの前記ピクセルの値に対応するテクスチャ部分と、前記入力データを前記テクスチャ部分内の完全に又は部分的に不透明なピクセルと透明なピクセルとにそれぞれ対応するデータの第1の及び第2のサブセットに細分するオブジェクトマスクとを有し、該前処理方法は、前記不透明なピクセルに対応するDCT(離散コサイン変換)係数を決定するために提供されており、各考慮されたオブジェクトに対して、
(1) オブジェクト平面を2次元のブロックに分割するステップと、
(2) 元のピクセル値の推定を基底ベクトルの線形結合として表すために選択された前記基底ベクトルの組を、前記ブロックによって規定される前記画面領域に導入するステップと、
(3) 前記ピクセル値の前記元の表現とこの元の表現の前記推定との間の歪みを測定するための費用関数ψを規定するステップと、
(4) 前記費用関数ψを最小化することを可能にする係数を求めるステップと、
を有する方法において、
(a) 前記費用関数ψは、次の関係によって与えられ：
【数１】
0003876227.tif 000021
ここでfは考慮されているブロックのピクセルの列ベクトルであり、((bi), i∈(1〜64))は8x8 DCTの基底ベクトルであり、fopaqueはfの前記ブロックの前記不透明なピクセルへの制限であり、((bopaque),i∈(1〜64))は、前記基底ベクトルの、前記ブロックの前記不透明なピクセルの位置への制限であり、
【数２】
0003876227.tif 000022
はfopaqueの再構成と呼ばれる、ことと、
(b) 前記求めるステップ自身は、
- 以下のパラメータ、即ち、
繰返しパラメータk = 0と、
最初の推定fopaqueE= 0と、
最初の再構成係数ci0= 0とを含むパラメータの初期化と、
- 前記不透明なピクセルに制限される前記基底ベクトルの抽出及び投射係数の以下のような算出と、
【数３】
0003876227.tif 000023
(ここで｛｝は相互相関関数を表し、iは1から64まで変化し、(bopaque)は、前記制限された基底ベクトルである)
- 繰り返しであって、当該繰り返しの各々が、
[a] 前記費用関数を最小化するのに最も寄与する前記基底ベクトルの添え字i*を求めるサブステップと、
[b] 以下の関係に従ってfopaqueEの前記再構成を更新するサブステップと、
【数４】
0003876227.tif 000024
[c] 再構成係数c i k+1=cik (i≠i*)及び
【数５】
0003876227.tif 000025
並びに投射係数
【数６】
0003876227.tif 000026
を更新するサブステップと、
を実行するように提供される繰返しと、
- 前記費用関数ψが所与の閾値を下回るか、又は所定の数の繰返しが到達された場合の、前記繰返しの中断と、
の動作を有することとを特徴とする方法。
【請求項２】
請求項1に記載の前処理方法において、
前記費用関数が
【数７】
0003876227.tif 000027
によって規定され、
前記サブステップ[a]は、残余
【数８】
0003876227.tif 000028
の最大エネルギーを得る前記基底ベクトルの前記添字i*を求めるように提供され、i = 1〜64について
【数９】
0003876227.tif 000029
であることを特徴とする前処理方法。
【請求項３】
任意の形状のオブジェクトのテクスチャに対応する入力データを符号化する方法であって、前記テクスチャ入力データのDCT変換と、前記変換から得られる係数の量子化と、符号化されるべき前記データの差分予測と、前記量子化された係数の可変長エンコーディング動作とを少なくとも含む方法において、前記DCT係数は、請求項1による前処理方法の実行によって得られる前記係数cikであると共に前記任意の形状のオブジェクトの不透明なピクセルに対応することを特徴とする方法。
【請求項４】
任意の形状のオブジェクトのテクスチャに対応する入力データを符号化するためのエンコーディング装置であって、前記テクスチャ入力データのDCT変換と、前記変換から得られる係数の量子化と、符号化されるべき前記データの差分予測と、前記量子化された係数の可変長エンコーディング動作とを実行するための手段を少なくとも含むエンコーディング装置において、前記DCT係数は、請求項1による前処理方法の実行によって得られる係数cikであると共に前記任意の形状のオブジェクトの前記不透明なピクセルに対応することを特徴とするエンコーディング装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、任意の形状のオブジェクトを表す画素(ピクセル)に対応する入力データを前処理する方法であって、前記入力データは各オブジェクトについて、前記オブジェクトの前記ピクセルの値に対応するテクスチャ部分と、前記入力データを前記テクスチャ部分内の完全に又は部分的に不透明なピクセルと透明なピクセルとにそれぞれ対応するデータの第1の及び第2のサブセットに細分するオブジェクトマスクとを有し、該前処理方法が、前記不透明なピクセルに対応するDCT(離散コサイン変換)係数を決定するために提供されており、各考慮されたオブジェクトに対して、
(1) オブジェクト平面を2次元のブロックに分割するステップと、
(2) 元のピクセル値の推定を基底ベクトルの線形結合として表すために選択された前記基底ベクトルの組を、前記ブロックによって規定される前記画面領域に導入するステップと、
(3) 前記ピクセル値の前記元の表現とこの元の表現の前記推定との間の歪みを測定する費用関数ψを規定するステップと、
(4) 前記費用関数ψを最小化することを可能にする前記係数を求めるステップと、
を有する方法に関する。
【０００２】
任意の形状のテクスチャを効率的にエンコーディングすることを目的とする本発明は、特にMPEG-4規格との関連で役立つが、このような適用に制限されるものではない。
【０００３】
【従来の技術】
1999年に発行されたMPEG-4規格は、自然の及び合成の画像中の視覚的オブジェクトを効率的にエンコードするための統一された手段を提案することを目的とされた。これらのオブジェクト(一般に幾つかの層でできており、これらの層は任意の形状のオブジェクトを含み得る)を処理しなければならないエンコーダに対して、これらのオブジェクトは2つの構成要素として供給される。これらは、バイナリであるか又はグレーレベルのピクセルから構成されていてよく、また、場面の構成のためにデコーダによって使用されるアルファチャンネル値を表すことができる、オブジェクトマスクと、テクスチャ部分、即ち、オブジェクトのピクセルの値(マスク中の白いピクセルは、テクスチャ部分の対応するピクセルは不透明であり、従って、そのピクセルの後ろにある如何なる他のオブジェクトのピクセルをも置換するものであるということを意味し、黒いピクセルは、テクスチャ部分の対応するピクセルは完全に透明である、即ち見えないということを意味する)とである。本発明は、特にテクスチャ部分のエンコーディング動作を対象とする。
【０００４】
MPEG-4エンコーダにおいて動くテクスチャをエンコードするためには、従来の方法は、画像ブロックに対してDCT変換(離散コサイン変換)を使用することである。より正確に言うと、エンコードされるべき平面は、大きさ16x16ピクセルのマクロブロックに分割され、16x16輝度情報は、2次元の8x8 DCT変換によってエンコードされた4つの8x8ブロックに更に分割される(U及びVクロミナンス情報を含む2つの8x8ブロックに対して同じ2D変換が再び用いられる)。任意の形状のオブジェクトに対して、いかなる8x8ブロックも、次の3つのカテゴリに分類されることができる：即ち、ブロックが透明なピクセルのみを含む(このときテクスチャ情報をエンコードする必要はない)か、不透明なピクセルのみを含む(テクスチャ情報をエンコードするために標準の長方形の8x8 DCTが用いられる)か、又は、少なくとも不透明なピクセル及び透明なピクセルを含む。この第3の状況で解決されるべき問題は、この部分的なテクスチャ情報の、ビット消費に関して効率的なエンコーディングである。
【０００５】
最初に、テクスチャ境界ピクセルを延長することによって空の空間が埋められた(不透明な領域の境界にある各サンプルは、透明な領域を置換するために左又は右の方向に水平に複製され、同じプロセスが垂直方向に繰り返され、得られたパディングピクセルは、デコーダがオブジェクトマスクを知っているため、デコーダによって後で除去される)後、テクスチャは、長方形のマクロブロックとして古典的にDCTエンコーディングされることができる。しかし、このパディング方法は、周波数スペクトルの観点からは最適ではない可能性のあるパターンを導入する(これらパターンは、水平方向に平坦であり垂直方向にランダムに変化している可能性があり、マクロブロックがDCTエンコーディングされるときにより多くのビットを消費する望まれない周波数成分を生じさせる)。
【０００６】
MPEG-4規格において正規化される他の解法は、図1のパターン(説明として与えられる)をエンコードするように2つのステップで進行するいわゆる形状適応DCTである。図2に示すように、全ての不透明なピクセルは、最初に、エンコードされるべきブロック中の最も上の位置へ移動され、次に、適応1次元n-DCTが各列に適用される。ここでnは、前記列中の不透明なピクセルの数である(図2の例においては左から右の順で1、4、7、5、7で、垂直方向に1-DCTがそれぞれ適用される)。次に、得られた垂直DCT係数が同様に、ブロックの最も左の位置へ移動され、これは図3のパターンを与える。同様に1次元n-DCTが各行に適用される(nは考慮される列の不透明なピクセルの数である)。残念なことに、この方法は、(完全に不透明なブロックに用いられる古典的な8x8DCTアルゴリズムとは反対に)関連するMPEG-4デコーダに特別な機能を必要とし、移動動作は、空間的に分離されておりそのためほとんど相関のないピクセル又は係数を連結するので、一般に高周波を導入することになる。
【０００７】
【発明が解決しようとする課題】
従って、本発明の目的は、このような望ましくない周波数を導入することを防止して、より良い符号化効率につながる前処理方法を提案することである。
【０００８】
【課題を解決するための手段】
このために、本発明は、本説明の序言の部分に規定される方法において、
(a) 前記費用関数ψは、次の関係によって与えられ：
【数１０】
0003876227.tif 000002
ここでfは考慮されているブロックのピクセルの列ベクトルであり、((bi), i∈(1〜64))は8x8 DCTの基底ベクトルであり、fopaqueはfの前記ブロックの前記不透明なピクセルへの制限であり、((bopaque),i∈(1〜64))は、前記基底ベクトルの、前記ブロックの前記不透明なピクセルの位置への制限であり、
【数１１】
0003876227.tif 000003
はfopaqueの再構成と呼ばれる、ことと、
(b) 前記求めるステップ自身は、
- 以下のパラメータ、即ち、
繰返しパラメータk = 0と、
最初の推定fopaqueE = 0と、
最初の再構成係数ci0 = 0とを含むパラメータの初期化と、
- 前記不透明なピクセルに制限される前記基底ベクトルの抽出及び投射係数の以下のような算出と、
【数１２】
0003876227.tif 000004
(ここで｛｝は相互相関関数を表し、iは1から64まで変化し、(bopaque)は、前記制限された基底ベクトルである)
- 繰り返しであって、当該繰り返しの各々が、
[a] 前記費用関数を最小化するのに最も寄与する前記基底ベクトルの添え字i*を求めるサブステップと、
[b] 以下の関係に従ってfopaqueEの前記再構成を更新するサブステップと、
【数１３】
0003876227.tif 000005
[c] 再構成係数cik+1 = cik(i≠i*)及び
【数１４】
0003876227.tif 000006
並びに投射係数
【数１５】
0003876227.tif 000007
を更新するサブステップと、
を実行するように提供される繰返しと、
- 前記費用関数ψが所与の閾値を下回るか、又は所定の数の繰返しが到達された場合の、前記繰返しの中断と、
の動作を有することとを更に特徴とする方法に関する。
【０００９】
【発明の実施の形態】
ここで本発明は、添付の図面を参照して例示により説明される。
【００１０】
本発明による前処理方法は、MPEG-4規格に記載の既存のデコーダ構造を利用するために、古典的8x8 DCT変換に基づいているが、当該方法は、ゼロでない係数の数を最小化すると同時に、透明なピクセルに関係なく不透明なピクセルを最もよく再構成するDCT係数を計算することによってより良い符号化効率を提供する。前記方法は、J.H.Chang他による、「A projection onto the overcomplete basis approach for block loss recovery」、Proceedings ICIP-97, October 26-29, 1997, Santa Barbara, Calif., USA, vol.II, pp.93-96において説明される方法の適応である。この文書において説明されたこの提案された適応は、元々、破壊されたMPEG-4ビデオストリーム(このような場合、このようなストリーム中の小さなエラーですらも多数のブロックに伝播し、損傷した画像ブロックを識別して回復することが必要である)の失われた情報の隠蔽技術になるよう意図されたものであるが、基本的な考えは、オーバーコンプリート基準を導入して、層ブロックの推定を基底ベクトルの線形結合として表し、歪み測度を最小化するためにベースベクトルの投射係数を得ることにより、一連の損傷していない値から損傷していない元のピクセル値の推定を得ることである。以下の表記法により、
D =損傷したブロック
N =損傷していない前記ブロックの近傍
U = D及びNの結合(=より大きいブロック)
損傷していない近傍情報Nから、考慮されている損傷したブロックDを含むより大きいブロックUを推定することが、実際に提案されている。従って、f =(fi,j(i,j))∈Uが損傷していない元のピクセル値を示す場合(i,j∈Nのとき)、課題はfを推定することである。Nのピクセル値が既知であるので、fの推定fEの歪みの測度は予測されることができ、歪み測度は以下の二乗差として規定される：
【数１６】
0003876227.tif 000008
(b)l=(bi,jl)がUの基準であり、基底ベクトルの組が元のfを基底ベクトルの線形結合として表すよう選択されたら、ブロック間相関のため、また、何らかの関連した推定を考慮して、損傷したブロック及び該ブロックの近傍は類似したスペクトル特性を有する可能性が高い。それゆえに、投射係数：
【数１７】
0003876227.tif 000009
は元の係数の良い推定であり得るので、
【数１８】
0003876227.tif 000010
である。
従って、al’Sが、
【数１９】
0003876227.tif 000011
がfNの良い近似になるようなものであれば、
【数２０】
0003876227.tif 000012
はfUの良い推定になる(下付き文字N及びUはベクトルのドメインを表す)。
【００１１】
このとき損傷したブロックを回復させる問題は、ψを最小化することを可能にするこれらの係数al'sを得ることであり、これは本明細書にて説明される反復アルゴリズムによって可能である。本発明の目的である前処理方法によれば、問題はここで修正された表記法及び考察によって再公式化される：
- このときfは、エンコードされるべきマクロブロックのピクセルの列ベクトルである;
- fopaqueは、前記マクロブロックの不透明なピクセルに対するfの制限である;
- Bは、8x8 DCT変換の基準式を表わす：B =(bi), i∈(1〜64);
- Bopaque =(bopaque(i)), i∈(1〜64)は、不透明なピクセルの位置に対するこれらの基底ベクトルの制限を示す。
前記問題は、このとき、最大数のゼロ係数を有する費用関
【数２１】
0003876227.tif 000013
を最小化することによって、最小平均自乗でfopaqueを再構成する係数(ci)の小さな組を求めることである。
【００１２】
マクロブロックfが完全に不透明な場合、全てのピクセルを再構成することができるDCT係数の固有の組合せが存在するだろう(これは、長方形の8x8 DCTである)。しかし、fの特定の部分の再構成が求められているのみであれば、同じ不透明なピクセルを含むブロックを再構成することができる無限のDCT係数が存在する。実際は、正しいDCT係数(係数の最も小さな組)の決定は明確でない。なぜなら、不透明なピクセルの位置に制限されると、DCT変換の基底関数はもはや正規直交でないからである。費用関数ψを最小化する係数を得るために、最大のエネルギーを有する投射係数を順に検索する以下の反復的なアルゴリズムが、ここで提案される(図4に表される)：即ち、
(1) 第1のステップ(初期化INIT)と：
k = 0(繰返しの数)
fopaqueE = 0(fopaqueの最初の推定)
ci0 = 0(最初の再構成係数)
(2) 投射係数
【数２２】
0003876227.tif 000014
が計算され、ここで｛｝は相互相関関数を表し、iは1から64まで変化し、(bopaque(i))は不透明ピクセルに限定された抽出された8x8DCT(形状マスクMにより区切られる、テクスチャを有するピクセルPWT)である、第2のステップ(抽出副ステップEXTR及び算出副ステップCALC)と、
(3) 推定についてのk回繰返しであって、各繰返し(例えばk番目の繰り返し)自身は、
(a) 残余の最大のエネルギーを得る基底ベクトルの添え字i*を求めるステップ(サブステップFIND)と、
【数２３】
0003876227.tif 000015
(b) fopaqueEの再構成を以下の関係に従って更新するステップ(サブステップUPDA中)と、
【数２４】
0003876227.tif 000016
(c) 再構成係数
【数２５】
0003876227.tif 000017
及び
【数２６】
0003876227.tif 000018
を更新するステップ(サブステップUPDA中)と、
(d) 以下の残留の投射係数を更新するステップ(サブステップUPDA中)と、
【数２７】
0003876227.tif 000019
を有する第3のステップと、
(4) 反復的なアルゴリズムの中断試験又はサブステップTESTであって、残留が所与の閾値ε：
【数２８】
0003876227.tif 000020
より下の場合、又は、所定の数の繰返しkmaxが到達された場合、反復プロセスは停止する(試験に対する応答YES)一方、これらの条件のいずれも満たされない限り、第3のステップ(3)の繰り返しにより反復プロセスは続く(試験に対する応答NO)第4のステップとを有するアルゴリズムである。アルゴリズムの実行の終わりには、cikは任意の形状の不透明なピクセルを製作する8x8 DCT係数である。
【００１３】
このとき、このように説明された前処理方法に、テクスチャエンコーディングのために一般に提供される通常の動作が続いてもよい：即ち、量子化、(必要ならば)該係数のエントロピーを更に低減するための個々の係数予測、スキャニング及び従来のMPEG符号化方策において完全に不透明なブロックのDCT係数のために提供されるような係数の可変長エンコーディングである。本発明はMPEG-4規格の特定の例との関連で説明されたが、本発明はこれに限定又は制限されることを意図されるものではないということが理解されるであろう。本発明は、得られた出力ビットストリームにこのとき使用されるいかなる特定の符号化方策にも限定されるものではない。
【図面の簡単な説明】
【図１】  任意の形状のオブジェクトのテクスチャピクセルをエンコードするために用いる従来技術の方法(形状適応DCT)を示す。
【図２】  任意の形状のオブジェクトのテクスチャピクセルをエンコードするために用いる従来技術の方法(形状適応DCT)を示す。
【図３】  任意の形状のオブジェクトのテクスチャピクセルをエンコードするために用いる従来技術の方法(形状適応DCT)を示す。
【図４】  本発明による前処理方法の主要なステップを与えるフローチャートを示す。
【図１】
0003876227.tif 000030
【図２】
0003876227.tif 000031
【図３】
0003876227.tif 000032
【図４】
0003876227.tif 000033