(57)【要約】コサイン変換係数の整数近似を得るため、制限された値の範囲を設定する。直交性の条件の考慮の下に下位の行列に対する基底関数の係数を選択して、それらの平方の和が直流成分係数の平方になるようにする。これらの係数から交流成分の係数を導出する。この手段により、量子化および正規化の際にすべての係数に対して単一の正規化および量子化ファクタを使用できるという利点が得られる。
2004506990.tif 000002
【特許請求の範囲】
【請求項１】
例えばピクセルブロックの符号化に対して、整数近似されたコサイン変換係数を得る方法において、
当該変換係数を選択して、
該変換係数に対して、制限された値の範囲が設定され、
直交性の条件の考慮の下に下位の行列に対する基底関数の係数が選択されて、当該係数の平方の和が、直流成分の係数の平方に等しくなるようにし、
該係数から交流成分の係数が導出されるようにすることを特徴とする、
整数近似されたコサイン変換係数を得る方法。
【請求項２】
すべての係数に対して単一の正規化および／または量子化ファクタを使用する、
請求項１に記載の方法。
【請求項３】
前記変換に対して、動き補償に関連付けられたブロックサイズを使用する、
請求項１または２に記載の方法。
【請求項４】
変換行列を用いて、同じ行列サイズ、例えば１６×１６のアダマール変換から前記の整数コサイン変換行列を形成する、
請求項１から３までのいずれか１項に記載の方法。
【請求項５】
直流成分に対する基底ベクトルの係数に対してそれぞれ値１７を選択する、
請求項１から４までのいずれか１項に記載の方法。
【請求項６】
最も低い交流成分に対する基底ベクトルの係数の絶対値を１５および８に選択する、
請求項４または５に記載の方法。
【請求項７】
２番目に低い交流成分に対する基底ベクトルの係数の絶対値を１２，９および８に選択する、
請求項４から６までのいずれか１項に記載の方法。
【請求項８】
３番目に低い交流成分に対する基底ベクトルの係数の絶対値を１３，１０，４および２に選択する、
請求項４から７までのいずれか１項に記載の方法。
【請求項９】
３番目に低い交流成分に対する基底ベクトルの係数の絶対値を１６，５，２および２に選択する、
請求項４から７までのいずれか１項に記載の方法。
【請求項１０】
動画像列を周波数領域符号化するための、変換装置を有する符号器において、
該変換装置を構成して、請求項１から９までのいずれか１項に記載の方法ステップによって供給された、動画像列に対する変換係数が作成されるようにすることを特徴とする、
動画像列を周波数領域符号化するための符号器。
【請求項１１】
動画像列を周波数領域復号化するための、変換装置を有する復号器において、
該変換装置を構成して、請求項１から９までのいずれか１項に記載の方法ステップによって供給された、動画像列に対する変換係数から動画像列が再構成されるようにすることを特徴とする、
動画像列を周波数領域復号化するための復号器。
【請求項１２】
近似された変換に対して実質的に対称なアルゴリズムを使用して、入力側の変換係数を段階的に加算ないしは減算ノードにそれぞれ案内し、必要な乗算に対して相応に重み付けを行う、
請求項１から９までのいずれか１項に記載の方法。
【発明の詳細な説明】
【０００１】
従来の技術
ＤＣＴ（Ｄｉｓｃｒｅｔｅ Ｃｏｓｉｎｅ Ｔｒａｎｓｆｏｒｍ）の整数（ｉｎｔｅｇｅｒ）による近似は、動画列の周波数領域における符号化の際に適用され、この符号化では純粋な整数演算が要求される。この整数演算により、異なる計算精度に起因する符号器と復号器との間の差異が排除される。
【０００２】
ビデオ符号化規格Ｈ．２６Ｌのテストモデルに対して、サイズ４×４の整数コサイン変換が提案されている。文献［１］では変換に対して、動き補償に関連付けられたブロックサイズを使用するコンセプトが提案されている。このためには付加的にサイズ８×８および１６×１６の整数コサイン変換が必要であり、ここで係数は、利用可能な数の範囲が例えば３２ビットに制限されていることに起因して、限られた範囲だけでしか選択することができない。サイズ８×８の直交整数コサイン変換は、例えば文献［２］に記載されている。
【０００３】
ＤＣＴを整数コサイン変換によって近似するためには種々異なるアプローチがある。文献［３］および［４］には、ＤＣＴの種々異なる大きさの係数が整数値によって置き換えられる方法が示されている。
【０００４】
文献［５］では、アダマール変換を使用したＤＣＴの近似方法が使用されている。このＤＣＴは、アダマール変換と直交変換行列とを乗算することによって形成可能である。実数の変換行列を、整数係数を有する直交行列によって置き換えることによって、ＤＣＴの整数による近似が形成される。
【０００５】
発明の利点
請求項１ならびに従属請求項のステップに記載された方法により、整数の変換行列が、例えばブロックサイズ８×８および１６×１６に対して得られ、ここでこれらは、動画列用ピクセルブロックの周波数領域符号化に対するＤＣＴの特性を近似的に有しており、したがって符号化効率を高めることが可能である。
【０００６】
符号化は、本発明の手段により純粋に整数演算で行うことができる。本発明のように変換係数を選択することによって、殊に３２ビットである限られた数の範囲において、発生し得る互いに異なる整数の係数を最大限に使用可能であり、ここでこれら係数は、整数でないＤＣＴ係数の良好な近似である。変換の整数の係数は、変換される係数の量子化および正規化の点から、２５よりも小さい上記の数の範囲で選択される。整数演算であるためにこれはテーブル値を介して実現可能である。
【０００７】
本発明で殊に有利であるのは、すべての基底ベクトルの係数が、同じノルムを有することであり、これによって、量子化および正規化の際に単一の正規化および量子化ファクタを使用できることである。これに対して文献［３］および［４］による方法では、与えられた整数変換の偶数および奇数の基底関数は、別個のノルムを有しているため、これらのマトリクスは直交性の要求を満たさない。文献［５］には、例えば１６×１６のサイズのＤＣＴの直交整数近似に結び付く解決手段は示されていない。
【０００８】
実施例の説明
本発明そのものを説明する前に、前提知識をいくつか説明しておく。
【０００９】
Ｎ×Ｎ−ＤＣＴの直交整数近似は、つぎの条件、すなわち、
【００１０】
【数１】
2004506990.tif 000003
【００１１】
を満たさなければならず、ここでＩＮは、サイズＮ×Ｎの単位行列を示し、ｋＮは整数の定数である。
【００１２】
本発明のサイズ８×８の直交整数変換は、２７である係数の範囲内で、最も小さな最大近似誤差が、
【００１３】
【数２】
2004506990.tif 000004
【００１４】
であり、ここでｔＤＣＴ，ｍおよびｔＩＣＴ，ｍは、ＤＣＴないしはＩＣＴ（Ｉｎｔｅｇｅｒ Ｃｏｓｉｎｅ Ｔｒａｎｓｆｏｍ）の係数を表し、ｍ＝０，…，７である。上記の文献には、ブロックサイズ１６×１６のＤＣＴの整数による近似、すなわちＮ＝１６に対して数式（１）および（２）を満たすＤＣＴの整数近似について示唆されていない。本発明のよる整数変換はこの条件を満たしているため、文献［４］に示された解決手段とは異なり、すべての基底ベクトルは同じノルムを有する。このことが意味するのは、変換された係数の量子化および正規化の際に殊に有利なことである。それはすべての係数に対して、単一の正規化および量子化ファクタを使用できるからである。
【００１５】
サイズ８×８の整数近似Ｔ８は、８×８−ＤＣＴの係数の実数の相異なる７つの絶対値を、Ｎ＝８に対して直交条件（１）および（２）を考慮して、７つの整数値によって置き換えることによって形成され、
【００１６】
【数３】
2004506990.tif 000005
【００１７】
である。
【００１８】
文献［５］によればこのＤＣＴは、サイズ１６×１６の変換行列を用いて、サイズ１６×１６のアダマール変換ＨＢＲＯから形成可能である。ここでＢＲＯは、例えば文献［６］から公知であるアダマール変換の基底ベクトルのビット逆順（ｂｉｔ ｒｅｖｅｒｓａｌ ｏｒｄｅｒ）を表す。実数の変換行列は、整数の直交変換行列Ｃ１６によって置き換えられ、これにより、
Ｔ１６，ＢＲＯ ＝ Ｃ１６・ＨＢＲＯ　　　　　　　　　　　　　　　　　（５）
が成り立つ。
【００１９】
【数４】
2004506990.tif 000006
【００２０】
これによればこの整数（Ｉｎｔｅｇｅｒ）のコサイン変換（ＩＣＴ）の一定の基底ベクトルの係数（直流成分）はそれぞれ値１７を有する。交流成分に対する下位の行列の係数は、この値１７からつぎようにして導出可能である。すなわち、値１７の平方が、下位の行列の各行の２乗された係数値の和になることにより導出可能である。ここから最も低い交流成分の係数に対して、絶対値として値１５および８が得られる。それは１７２＝１５２＋８２だからである。つぎに２番目に低い交流成分に対する係数値は、相応に例えば１２，９および８になり、３番目に低い交流成分に対しては例えば１３，１０，４および２になる。わかりやすくするために以下では、行列Ｃ１６に対して、ひいてはＴＩＣＴ，１６に対して考えられ得る解を示す。
【００２１】
【数５】
2004506990.tif 000007
【００２２】
つぎにＴ１６，ＢＲＯの行ベクトルを相応に並べ直すことによって直交整数変換行列
【００２３】
【数６】
2004506990.tif 000008
【００２４】
が得られる。
【００２５】
これらの行ベクトルは、ＤＣＴに相応して交互に偶数および奇数に対称に継続される。
【００２６】
１６×１６直交整数変換行列の別の例はつぎの形を有する。
【００２７】
【数７】
2004506990.tif 000009
【００２８】
これはつぎのように構成される。
【００２９】
偶数の行０：２：１４は、すでに前に示したＴＩＣＴ，８の偶数の行に相応し、ここで行の長さ８の１６への延長は、係数を鏡映反転することによって行われる。奇数の行１：２：１５は、つぎのようにして得られる。
【００３０】
【数８】
2004506990.tif 000010
【００３１】
Ｍａｔｌａｂ記法では、
Ａ ＝ ［ｚｅｒｏｓ （８）， ｚｅｒｏｓ （８）； ｚｅｒｏｓ （８）， Ｃ８］；
Ｔｎ ＝ Ａ ＊ Ｈ１６．
Ｃ８−行列の行における係数の値２，２，５および１６はそれぞれ２乗して合計すると、ここでも直流成分１７の２乗になる。
【００３２】
Ｔ１６の奇数の基底関数は（ここでもＭａｔｌａｂ記法を使用する）
Ｔ１６ （２：２：１６，：） ＝ Ｔｎ （［９ １３ １１ １５ １０ １４ １２ １６］，：）
になる。
【００３３】
すなわちＴｎの第９行はＴ１６の第２行になり、Ｔｎの第１３行はＴ１６の第４行になり、これが継続される。
【００３４】
この行列Ｔ１６の利点は、変換利得が比較的高いことの他に、前に示した極めて対称性の高い行列を用いて構成できることである。これによって符号器ないしは相応する復号器において、ブロック内のピクセル情報の変換符号化に対して効率的な実現が可能である。
【００３５】
Ｎ個の基底ベクトルによる直交変換の変換利得は、変換行列ＴＮによって変換されその後量子化された信号の分散に対する、量子化後の入力信号の分散の比にから得られる。この変換利得は、通例ｄＢで示される。文献では実数の画像信号は１次の自己回帰過程によってモデル化されることが多い。このモデルは、信号分散および相関係数を与えることによって完全に記述される。最適な量子化および符号化の前提の下では、この信号モデルに対する変換利得を直接示すことができる。画像信号に典型的な０．９５の相関係数に対しては、ＤＣＴについて９．４６ｄＢの変換利得が得られ、最初の例に示した１６×１６行列については８．１７ｄＢ、最後の１６×１６行列については８．８６ｄＢが得られる。
【００３６】
本発明の方法によれば、動画像列を周波数領域符号化／復号化する符号器および復号器を構成することができる。それらの変換装置はこのためにつぎように構成する必要がある。すなわち変換係数が上に示した方法ステップによって得られるか、ないしは元々の動画列がこれらの係数から再構成可能であるようにする必要がある。
【００３７】
サイズ８×８および１６×１６のサイズのＩＣＴ行列に対して高速アルゴリズムを開発することができ、この高速アルゴリズムによって所要の加算および乗算の数が最小化される。
【００３８】
図１にはこのようなアルゴリズムの例が示されており、このアルゴリズムでは２つの変換が概略的に流れ線図で示されている。サイズ８×８および１６×１６のＩＣＴ行列は、図１においてそれぞれ参照符号Ｔ８およびＴ１６を有するボックスで示されている。Ｔ１６の偶数の基底関数はＴ８のそれに対応するため、Ｔ８ブロックはＴ１８ブロックに完全に組み込まれている。長さ１６の入力信号の係数は、ｘ０，ｘ１，ｘ２，…，ｘＦによって示されており、線図の左側に加えられる。出力信号の係数はｙ０，ｙ１，…，ｙＦである。この線図のノードは加算を表す。一定値による乗算は、縁の相応する数によって示されている。縁のマイナス符号は加算の代わりに減算が行われることを意味する。図をわかりやすくするため、この線図は、ボックスによってマークが付されたノードにおいて分割されており、別の経過の部分がメインの線図の横に示されている。対応するノード点はそれぞれ同じ参照符合を有する。
【００３９】
８×８変換および１６×１６変換に必要な加算および乗算の回数は、つぎの表に示されている。比較のためにこの表には、文献［７］に記載された高速離散コサイン変換に対する加算および乗算の回数についての値も含まれている。
【００４０】
【表１】
2004506990.tif 000011
【００４１】
Ｔ１６およびＴ８を高速に実現する図１の流れ線図には、複数個存在する要素がいくつかある。この規則性には変換内の対称性が反映されている。この線図は、４段階に分割され、これらはノード点からなる垂直面によって特徴付けられている。これらを以下では段階１〜４によって示す。段階１では２つずつの入力係数が加算および減算されるため、ここでも１６個の係数が得られる。ｘ０とｘＦとの和，ｘ１とｘＥとの和，ｘ２とｘＤとの和等々によって、Ｔ８ブロックの入力係数が形成され、これは偶数の基底関数を表す。差分は、この図に示されているノード０〜７に加えられる。これらから奇数の成分が得られる。このような加算および減算から得られる星形構造は、１６個の係数の代わりに８個の係数により、段階２のＴ８と記されたブロックの入力側において繰り返される。つぎに段階３の上側の４つの係数（Ｔ８の偶数の基底関数）により、さらに段階４の出力側ｙ０およびｙＦの前の２つの係数により繰り返される。この構造は、離散コサイン変換の高速な実現と同等である。純粋な加算および減算を表さず、重み付け係数を含む星形も複数生じている。例えば、図１に示したノード３−４，２−５，１−６および０−７から４つの係数を有する重み付けられた２つの星形が分岐しており、ここでこれらの２つの星形は重み付けの配置構成だけが異なっている。この構造は、出力側ｙ４およびｙＣの前で別個の重み付けと２つの係数とによって繰り返される。Ｔ１６の奇数の基底関数に対しては、この重み付けられた構造の変形が得られる。ここでは段階３に４つの構造が生じ、これらは重み付けられた係数を有する２つの出力側と、純粋の加算／乗算を有する２つの出力側をそれぞれ有する。これらは重み付けの配分が異なる。これらの構造のうちの３つでは、２つのノードだけが入力側を形成する。したがって歪んだ星形が得られるのである。
【００４２】
文献
［１］ Ｔｅｌｅｃｏｍ． Ｓｔａｎｄａｒｄｉｚａｔｉｏｎ Ｓｅｃｔｏｒ ｏｆ ＩＴＵ， ”Ｎｅｗ ｉｎｔｅｇｅｒ ｔｒａｎｓｆｏｒｍｓ ｆｏｒ Ｈ．２６Ｌ”， ｉｎ Ｓｔｕｄｙ Ｇｒｏｕｐ １６， Ｑｕｅｓｔｉｏｎ １５， Ｍｅｅｔｉｎｇ Ｊ， （Ｏｓａｋａ， Ｊａｐａｎ）， ＩＴＵ， Ｍａｙ ２０００．
［２］ Ｔｅｌｅｃｏｍ． Ｓｔａｎｄａｒｄｉｚａｔｉｏｎ Ｓｅｃｔｏｒ ｏｆ ＩＴＵ， ”Ａｄｄｉｔｉｏｎ ｏｆ ８ｘ８ ｔｒａｎｓｆｏｒｍｓ ｆｏｒ Ｈ．２６Ｌ”， ｉｎ Ｓｔｕｄｙ Ｇｒｏｕｐ １６， Ｑｕｅｓｔｉｏｎ １５， Ｍｅｅｔｉｎｇ Ｉ， （Ｒｅｄ Ｂａｎｋ， Ｎｅｗ Ｊｅｒｓｅｙ）， ＩＴＵ， Ｍａｙ １９９９．
［３］ Ｗ． Ｃｈａｍ， ”Ｄｅｖｅｌｐｏｍｅｎｔ ｏｆ ｉｎｔｅｇｅｒ ｃｏｓｉｎｅ ｔｒａｎｓｆｏｒｍｓ ｂｙ ｔｈｅ ｐｒｉｎｃｉｐｌｅ ｏｆ ｄｙａｄｉｃ ｓｙｍｍｅｔｒｙ”， ＩＥＥＥ Ｐｒｏｃ．， ｖｏｌ． １３６， ｐｐ．２７６−２８２， Ａｕｇ． １９９９．
［４］ Ｗ． Ｃｈａｍ ａｎｄ Ｙ． Ｃｈａｎ， ”Ａｎ ｏｒｄｅｒ−１６ ｉｎｔｅｇｅｒ ｃｏｓｉｎｅ ｔｒａｎｓｆｏｒｍ”， ＩＥＥＥ Ｔｒａｎｓ． Ｓｉｇｎａｌ Ｐｒｏｃｅｓｓｉｎｇ， ｖｏｌ．３９， ｐｐ．１２０５−１２０８， Ｍａｙ １９９１．
［５］ Ｒ． Ｓｒｉｎｉｖａｓａｎ ａｎｄ Ｋ． Ｒａｏ， ”Ａｎ ａｐｐｒｏｘｉｍａｔｉｏｎ ｔｏ ｔｈｅ ｄｉｓｃｒｅｔｅ ｃｏｓｉｎｅ ｔｒａｎｓｆｏｒｍ ｆｏｒ ｎ ＝ １６”， Ｓｉｇｎａｌ Ｐｒｏｃｅｓｓｉｎｇ ５， ｐｐ．８１−８５， １９８３．
［６］ Ａ．Ｋ． Ｊａｉｎ， Ｆｕｎｄａｍｅｎｔａｌｓ ｏｆ ｄｉｇｉｔａｌ ｉｍａｇｅ ｐｒｏｃｅｓｓｉｎｇ． Ｅｎｇｌｅｗｏｏｄ Ｃｌｉｆｆｓ， ＮＪ： Ｐｒｅｎｔｉｃｅ Ｈａｌｌ， １９８９．
［７］ Ｗ．Ｈ． Ｃｈｅｎ， Ｃ．Ｈ． Ｓｍｉｔｈ， ａｎｄ Ｓ．Ｃ． Ｆｒａｌｉｃｋ， ”Ａ Ｆａｓｔ Ｃｏｍｐｕｔａｔｉａｌ Ａｌｇｏｒｉｔｈｍ ｆｏｒ ｔｈｅ Ｄｉｓｃｒｅｔｅ Ｃｏｓｉｎｅ Ｔｒａｎｓｆｏｒｍ”， ＩＥＥＥ Ｔｒａｎｓ． Ｃｏｍｍ．， Ｖｏｌ． ＣＯＭ−２５， Ｎｏ．９， Ｓｅｐ．１９７７， ｐｐ．１００４−１００９．
【図面の簡単な説明】
【図１】
２つの変換のアルゴリズムを概略的に示す流れ線図である。
【国際公開パンフレット】
2004506990.tif 000012
2004506990.tif 000013
2004506990.tif 000014
2004506990.tif 000015
2004506990.tif 000016
2004506990.tif 000017
2004506990.tif 000018
2004506990.tif 000019
2004506990.tif 000020
2004506990.tif 000021
2004506990.tif 000022
2004506990.tif 000023
2004506990.tif 000024
2004506990.tif 000025
2004506990.tif 000026
2004506990.tif 000027
2004506990.tif 000028
2004506990.tif 000029
2004506990.tif 000030
2004506990.tif 000031
2004506990.tif 000032
【国際公開パンフレット（コレクトバージョン）】
2004506990.tif 000033
2004506990.tif 000034
【国際調査報告】
2004506990.tif 000035
2004506990.tif 000036
2004506990.tif 000037
2004506990.tif 000038