(57)【特許請求の範囲】
【請求項１】
離散コサイン変換の整数近似を使用してビデオまたはイメージのデータを復号化する方法であって、
１組の量子化済み変換係数を受け取るステップと、
前記量子化済み変換係数を非量子化変換係数に非量子化するステップであって、そこでは、前記１組の量子化済み変換係数は論理的に１つのブロック内に配置されており、各量子化済み変換係数について、
前記ブロック内の前記量子化済み変換係数の位置に基づいて１グループが複数の増倍率からなる複数のグループから１つのグループを選択するステップであって、そこでは、当該選択されたグループがグループインデックスで示される、グループを選択するステップと、
量子化パラメータインデックスに依存して、当該選択されたグループ内で１つの増倍率を選択するステップであって、そこでは、ルックアップオペレーションで選択される前記増倍率は前記量子化パラメータインデックスおよび前記グループインデックスにより示される、増倍率を選択するステップと、
前記変換済み変換係数と選択された増倍率とを乗算するステップと
を含むステップと、
前記変換係数に逆変換処理を適用してそこから情報を再構築するステップであって、そこでは、前記逆変換処理は複数の値の１つおよび複数の非量子化変換係数の１つの間での各乗算演算がシフト演算によって実行できるような値を有する逆変換計算を適用し、前記逆変換処理は直交であるステップと
を実行し、前記逆変換計算の値は、異なるノルムを有する複数の列を持つ逆変換行列で示される値に基づいており、前記逆変換処理は行および列の逆変換を有する２次元の逆変換であり、当該２次元の逆変換は異なるノルムを有し、前記非量子化するステップでは前記逆変換行列の複数の列の異なるノルムを少なくとも部分的に調整するための倍率要素の複数のグループからの選択を使用することを特徴とする方法。
【請求項２】
前記量子化済み係数および増倍率の値が１６ビット演算での非量子化を可能にすることを特徴とする請求項１に記載の方法。
【請求項３】
前記逆変換処理を非量子化変換係数に適用する処理では、１６ビット演算が実行されることを特徴とする請求項１に記載の方法。
【請求項４】
再構築される前記情報は４×４ブロックについての予測誤差情報を有することを特徴とする請求項１乃至３のいずれかに記載の方法。
【請求項５】
前記逆変換計算における前記複数の値の１つおよび複数の非量子化変換係数の１つの間の各乗算演算は１ビット右シフト演算により実行されることを特徴とする請求項１乃至４のいずれかに記載の方法。
【請求項６】
前記逆変換計算は前記再構築の情報の４×４ブロックについて１６回の１ビット右シフト演算、複数の加算演算および複数の減算演算で構成されることを特徴とする請求項５に記載の方法。
【請求項７】
前記逆変換行列の複数の列は互いに直交であり、前記増倍率の複数のグループの各々について、量子化ステップサイズがテーブルインデックス内の増分６ごとにほぼ２倍となるように各グループ内の量子化パラメータの値が定められていることを特徴とする請求項１乃至６のいずれかに記載の方法。
【請求項８】
請求項１乃至７のいずれかに記載の方法を実行するための、コンピュータ実行可能命令を有することを特徴とするコンピュータ読取可能な記録媒体。
【請求項９】
前記量子化済み変換係数のブロックは４×４のブロックであり、前記増倍率の複数のグループは増倍率の３つのグループで構成され、前記２次元の逆変換は３つの異なるノルムを有し、前記倍率要素の３つのグループの各々は前記２次元の逆変換の３つの異なるノルムの１つを調整するように適合されていることを特徴とする請求項１に記載の方法。
【請求項１０】
離散コサイン変換の整数近似を使用して符号化されたビデオ情報を復号化するビデオデコーダであって、
１組の量子化済み変換係数を受け取る手段と、
前記量子化済み変換係数を非量子化変換係数に非量子化する手段であって、そこでは、前記１組の量子化済み変換係数は論理的に１つのブロック内に配置されており、前記非量子化する処理は、前記量子化済み変換係数と、１つのグループが複数の増倍率からなる複数のグループから選択された増倍率とを乗算する処理を含み、前記選択は前記ブロック内の量子化済み変換係数の相対位置に依存し、および量子化パラメータインデックスにも依存し、増倍率の選択のグループはグループインデックスにより示され、ルックアップオペレーションで選択される前記増倍率は前記量子化パラメータインデックスおよび前記グループインデックスにより示される、非量子する手段と、
を含む手段と、
前記変換係数に逆変換処理を適用してそこから再構築の情報を生成する手段であって、そこでは、前記逆変換処理は複数の値の１つおよび複数の非量子化変換係数の１つの間での各乗算演算がシフト演算によって実行できるような値を有する逆変換計算を適用し、前記逆変換処理は直交である手段と
を有し、前記逆変換計算の値は、異なるノルムを有する複数の列を持つ逆変換行列で示される値に基づいており、前記逆変換処理は行および列の逆変換を有する２次元の逆変換であり、当該２次元の逆変換は異なるノルムを有し、前記非量子化するステップでは前記逆変換行列の複数の列の異なるノルムを少なくとも部分的に調整するための倍率要素の複数のグループからの選択を使用することを特徴とするビデオデコーダ。
【請求項１１】
再構築の前記情報は４×４ブロックについての予測誤差情報を有することを特徴とする請求項１０に記載のデコーダ。
【請求項１２】
前記逆変換計算における前記複数の値の１つおよび複数の非量子化変換係数の１つの間の各乗算演算は１ビット右シフト演算により実行されることを特徴とする請求項１０に記載のデコーダ。
【請求項１３】
前記逆変換計算は前記再構築の情報の４×４ブロックについて１６回の１ビット右シフト演算、複数の加算演算および複数の減算演算で構成されることを特徴とする請求項１２に記載のデコーダ。
【請求項１４】
前記逆変換行列の複数の列は互いに直交であり、前記増倍率の複数のグループの各々について、量子化ステップサイズがテーブルインデックス内の増分６ごとにほぼ２倍となるように各グループ内の量子化パラメータの値が定められていることを特徴とする請求項１０乃至１３のいずれかに記載のデコーダ。
【請求項１５】
前記量子化済み変換係数のブロックは４×４のブロックであり、前記増倍率の複数のグループは３つの増倍率のグループで構成され、前記２次元の逆変換は３つの異なるノルムを有し、前記倍率要素の３つのグループの各々は前記２次元の逆変換の３つの異なるノルムの１つを調整するように適合されていることを特徴とする請求項１０に記載のデコーダ。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は一般に、イメージおよびビデオ信号の符号化および復号化に関し、より詳細には、イメージビデオ信号を符号化かつ復号化するための、ブロック変換および逆変換、ならびに量子化および非量子化方法の改善に関する。
【背景技術】
【０００２】
離散コサイン変換（ＤＣＴ）は、ブロック変換イメージおよびビデオ（イメージのシーケンス）コード化、例えばＪＰＥＧおよびＭＰＥＧにおいて一般的に使用されている。多々ある理由の中で、これは、ＤＣＴが、（イメージデータに対応するような）ランダム信号を、イメージの視覚品質に関してより重要な低周波数部分と、より重要でない高周波数部分に分離し、したがって圧縮を容易にするという理由からである。
【０００３】
例としてＨ．２６Ｌは、４×４ブロックの画素を使用してフレームを構築するイメージおよび／またはビデオコード化技術である。８×８ブロックを使用するＭＰＥＧおよびＪＰＥＧとは異なり、Ｈ．２６Ｌは、同じフレーム内の既存の他のブロックの予測情報（すなわちフレーム内コード化）、ならびにフレーム間の推定および動き補正（すなわちフレーム間コード化）を使用することによって、４×４画素ブロックで比較的高品質の圧縮を取得する。一般に、フレーム内予測を達成するために、Ｈ．２６Ｌエンコーダは、構築されるフレーム内の他の前の画素ブロックのどれが予測のための基礎として使用されているかを、対応するＨ．２６Ｌデコーダに伝え、新しいブロックのための画素を決定する際に、（前のフレーム内ブロックの画素から）６つの可能な予測法（公式）のどれを使用するかを識別する。これは予測誤差につながり、この予測誤差もまた、新しいブロックを訂正するためにデコーダに提供される。予測誤差情報は、予測されたブロックを訂正するための誤差情報を再計算するために、ブロック変換（ＤＣＴ）で符号化されてデコーダに送られる。上記再計算の中には逆変換が含まれる。
【０００４】
イメージおよびビデオ符号化または復号化には、著しい量の処理パワーがかかる。知られているように、エンコーダは通常、デコーダすなわち、データをイメージに変換する多数のデコーダよりはるかに大きい処理パワーを有する。デコーダは通常、消費者デバイス内に実装されているからである。例えとして、イメージおよびビデオ復号化は、テレビジョンセットトップボックス、パーソナルデジタルアシスタント（ＰＤＡ）、ポケットサイズのパーソナルコンピュータ、およびより進んだ携帯電話内で行なわれる。
【発明の開示】
【発明が解決しようとする課題】
【０００５】
したがって、イメージおよびビデオ符号化および復号化の方法を考えるとき、復号化を単純にしておくことは、たとえそれによって符号化が計算上複雑になることを意味しても、重要である。復号化を単純化することはそれがなんであれ、そうすることによって符号化および復号化処理が、既存の圧縮レベル、最終イメージ品質、およびデコーダで必要な他のリソース量に、既存技術と比べて実質的にどのような点でも不利なインパクトを与えなければ、望ましい。
【課題を解決するための手段】
【０００６】
簡単には、本発明は、エンコーダおよびデコーダの双方において、計算の複雑さを著しく単純化する、イメージおよびビデオのための改善方法、改善システムおよび改善ブロック変換を提供する。同時に、圧縮、イメージ／ビデオ品質、および他のリソースは、無視し得る程にしか影響を受けない。
【０００７】
より詳細には、離散コサイン変換（ＤＣＴ）に対して新しい整数近似を行う直交ブロック変換および対応する逆変換が、提供される。エンコーダおよびデコーダの双方において計算の複雑性を著しく減少させる他の計算上の変更も提供される。実際、一実施例では、エンコーダおよびデコーダにおいて、係数当たりの変換処理数が、（Ｈ．２６Ｌに指定された変換で必要な、３２ビット演算での４つの加算および３つの乗算から）１６ビット演算での４つの加算および１つのシフトに減少した。本発明は、画素情報（例えば誤差訂正データ）を正しく変換する。それぞれの係数の位置に基づいて選択された３つのテーブルの１つを使用して、符号化における量子化（倍率（スケーリング）変更および整数への丸め）、および復号化における非量子化は、変換および逆変換処理中にシフト動作によって実行される１つを除いて、他の変換乗算の要素のために既に補正されたパラメータ値を有するからである。
【０００８】
さらに、復号化において、それぞれの量子化済み係数に対して、デコーダは、（Ｈ２６．Ｌにおいて必要とされる）３２ビット乗算の代わりに、その量子化済み係数を変換係数に非量子化するために１６ビット乗算を実行する。したがって典型的イメージおよびビデオを有する多数のデバイス上では、Ｈ．２６Ｌに比べて本発明の処理の利益は著しく、特に品質および／または圧縮の損失がたとえあっても無視し得るデコーダにおいて著しい。
【０００９】
他の利益および利点は、図面と共に見れば次の詳細な説明から明らかになろう。
【発明の効果】
【００１０】
以上説明したように、本発明によれば、エンコーダおよびデコーダの双方において、計算の複雑さを著しく単純化する、イメージおよびビデオのための改善方法、改善システムおよび改善ブロック変換が提供される。同時に、圧縮、イメージ／ビデオ品質、および他のリソースは、無視し得る程にしか影響を受けない。
【発明を実施するための最良の形態】
【００１１】
図１は、特にイメージおよび／またはビデオデータを復号化するために、本発明を実施することができる、適切なオペレーティング環境１２０の一実施例を示す。オペレーティング環境１２０は、適切なオペレーティング環境の一実施例に過ぎず、本発明の使用法または機能の範囲に関して制限を設けるものでもない。本発明を適用した、よく知られているコンピューティングシステム、環境、および／または構成は、パーソナルコンピュータ、サーバコンピュータ、ハンドヘルドまたはラップトップデバイス、マルチプロセッサシステム、マイクロプロセッサに基づくシステム、プログラム可能消費者電子機器、ネットワークＰＣ、ミニコンピュータ、メインフレームコンピュータ、任意の上記システムまたはデバイス等を含む分散コンピューティング環境を含むが、これらに制限されない。例えば、イメージおよび／またはビデオイメージデータを符号化することは、現代のハンドヘルドパーソナルコンピュータより大きな処理パワーを有するコンピュータ上でしばしば実行される可能性が高いが、符号化が例示的デバイス上で実行できない、またはよりパワフルなマシン上で復号化できないという理由はない。
【００１２】
本発明を、１つまたは複数のコンピュータまたは他のデバイスによって実行されるプログラムモジュールなど、コンピュータ実行可能命令の一般的文脈において述べることができる。一般にプログラムモジュールは、特定のタスクを実行するかまたは特定の抽象的データタイプを実施するルーチン、プログラム、オブジェクト、コンポーネント、データ構造等を含む。通常、プログラムモジュールの機能は、様々な実施形態において望まれているように、組み合わせるかまたは分散してもよい。コンピューティングデバイス１２０は通常、少なくとも何らかの形態のコンピュータ読取り可能媒体を含む。コンピュータ読取り可能媒体は、コンピューティングデバイス１２０によってアクセスすることができる任意の利用可能な媒体でよい。制限ではなく実施例として、コンピュータ読取り可能媒体は、コンピュータ記憶媒体および通信媒体を含むことができる。コンピュータ記憶媒体は、コンピュータ読取り可能命令、データ構造、プログラムモジュール等の情報記憶のための任意の方法または技術で実施される揮発性および不揮発性の取外し可能および取外し不能媒体を含む。コンピュータ記憶媒体は、ＲＡＭ、ＲＯＭ、ＥＥＰＲＯＭ、フラッシュメモリまたは他のメモリ技術、ＣＤ−ＲＯＭ、ＤＶＤ（デジタルバーサタイルディスク）または他の光記憶、磁気カセット、磁気テープ、磁気ディスク記憶または他の磁気記憶デバイス、あるいは希望する情報を格納するために使用することができコンピューティングデバイス１２０によってアクセスすることができる他の任意の媒体を含むが限定はされない。通信媒体は通常、コンピュータ読取り可能命令、データ構造、プログラムモジュールあるいは搬送波または他の搬送機構などの変調済みデータ信号内の他のデータを実施し、任意の情報配信媒体を含む。用語「変調済みデータ信号」は、１つまたは複数のその特性セットを有する信号、またはその信号内に情報を符号化するような方法で変更された信号を意味する。制限ではなく実施例として、通信媒体は、有線ネットワークまたは直接有線接続などの有線媒体、ならびに音響、ＲＦ、赤外線および他の無線媒体などの無線媒体を含む。上記の任意の組み合わせもまた、コンピュータ読取り可能媒体の範囲内に含まれるべきである。
【００１３】
図１は１つのそのようなハンドヘルドコンピューティングデバイス１２０の、それはプロセッサ１２２、メモリ１２４、ディスプレイ１２６、およびキーボード１２８（物理または仮想キーボードでもよい）を含むが、機能コンポーネントを示す。メモリ１２４は一般に、揮発性メモリ（例えばＲＡＭ）および不揮発性メモリ（例えばＲＯＭ、ＰＣＭＣＩＡカードなど）の双方を含む。Ｍｉｃｒｏｓｏｆｔ（登録商標）ＣｏｒｐｏｒａｔｉｏｎからのＷｉｎｄｏｗｓ（登録商標）ＣＥオペレーティングシステム、または他のオペレーティングシステムなどのオペレーティングシステム１３０は、メモリ１２４内に常駐し、プロセッサ１２２上で実行される。
【００１４】
１つまたは複数のアプリケーションプログラム１３２は、メモリ１２４にロードされ、オペレーティングシステム１３０上で実行される。アプリケーションの実施例は、電子メールプログラム、スケジューリングプログラム、ＰＩＭ（個人情報管理）プログラム、ワードプロセッシングプログラム、スプレッドシートプログラム、インターネットブラウザプログラムなどを含む。ハンドヘルドパーソナルコンピュータ１２０は、メモリ１２４内にロードされた通知マネージャ１３４もまた含み、その通知マネージャ１３４はプロセッサ１２２上で実行される。通知マネージャ１３４は、例えばアプリケーションプログラム１３２からの通知要求を処理する。
【００１５】
ハンドヘルドパーソナルコンピュータ１２０は、１つまたは複数のバッテリとして実装される電源１３６を有する。電源１３６は、ＡＣアタプタまたはパワードドッキングクレードルなど、ビルトインバッテリにオーバーライドまたは再充電する外部電源をさらに含むことができる。
【００１６】
図１に示す例示的ハンドヘルドパーソナルコンピュータ１２０は、３つのタイプの外部通知機構、すなわち１つまたは複数の発行ダイオード（ＬＥＤ）１４０およびオーディオジェネレータ１４４と共に示されている。これらのデバイスは、活動化（アクチベート）されたときに、たとえこのハンドヘルドパーソナルコンピュータプロセッサ１２２および他のコンポーネントがバッテリパワーを保存するために遮断されていても、通知機構によって命じられた期間はオンであり続けるように、これらの機器は電源１３６に直接、接続される。ＬＥＤ１４０は、ユーザがアクションを起こすまで無制限にオンのままが好ましい。現在のバージョンのオーディオジェネレータ１４４は、今日のハンドヘルドパーソナルコンピュータバッテリにとって過大なパワーを使用し、その結果システムの残りが遮断されるときまたは活動化後ある有限期間で遮断されるように構成されることに留意されたい。
【００１７】
符号化および復号化
背景として、離散コサイン変換（ＤＣＴ）は、線形変換Ｘ＝Ｈｘによって長さＮのベクトルｘを変換係数の新しいベクトルＸに写像する。ここで、Ｈの第ｋ行第ｎ列の要素は、ｋ＝０、１、．．．、Ｎ−１、ｎ＝０、１、．．．、Ｎ−１に対して、
【００１８】
【数１】
0004560033.tif 000002
【００１９】
によって定義され、ｃ０＝√２、かつｋ＞１に対してｃｋ＝１である。ＤＣＴ行列は直交であり、その逆行列はその転置行列に等しい。すなわちｘ＝Ｈー１Ｘ＝ＨｔＸである。
【００２０】
ＤＣＴの１つの欠点は、要素Ｈ（ｋ、ｎ）が無理数であり、その結果、整数入力データｘ（ｎ）が無理変換係数（ｉｒｒａｔｉｏｎａｌ  ｔｒａｎｓｆｏｒｍａ  ｃｏｅｆｆｉｃｉｅｎｔｉｅｎｔｅｓ）Ｘ（ｋ）に写像されることである。結果として、デジタルコンピュータでは、直接および逆変換を連続して計算するとき、出力データは入力データと正確に等しくはならない。換言すれば、Ｘ＝Ｈｘ、かつｕ＝ｒｏｕｎｄ（ＨＴＸ）として計算する場合、すべてのｎに対してｕ（ｎ）＝ｘ（ｎ）、は真ではない。しかし適切な倍率変更要素ａ＾、ａ〜を導入し、たとえばＸ＝ａ〜Ｈｘかつｕ＝ｒｏｕｎｄ（ａ＾ＨｔＸ）とすることによって、ａ＾およびａ〜を充分大きく選ぶとき、ほとんど全てのｎに対してｕ（ｎ）＝Ｇｘ（ｎ）、ここでＧは整数、となるが、これは正確な結果を保証するものではない。
【００２１】
動き補正ビデオエンコーダでは、例えば過去の復号化済みフレームのデータが予測情報のための参照情報として使用される。この予測情報は現在のフレームを生成するために使用される。したがって、符号化の一部として、エンコーダは、自分自身の復号化済みフレームを生成する。それによってエンコーダは、逆変換を計算しなければならない。公式ｕ＝ｒｏｕｎｄ（ａ＾、ＨＴＸ）が使用される場合、異なるプロセッサ内の異なる浮動小数点フォーマットおよび丸め方法は、異なる結果につながる。結果として、エンコーダで復号化されたデータと（異なるプロセッサを有する）デコーダによって復号化されたデータの間でずれが生じ、エンコーダは、デコーダが生成しているブロックのフレームとますます似ていないブロックのフレームに予測／動き情報の基礎を置くので、それによってイメージは、それぞれの新しいフレームごとにますます悪くなる。
【００２２】
データずれの問題に対する１つの解決方法は、整数のみを含む行列によって行列Ｈを近似し、それによって丸め誤差を無くする方法ことである。Ｈの行が直交で同じノルム（２乗の和）を有する場合、すべての整数ｘに対して、ｕは整数演算で正確に計算できることになる。換言すれば、直接変換がＸ＝Ｈｘによって、逆変換がｕ＝ＨＴＸによって計算されるときｕ＝Ｇｘとなる。ここでＧはＨ内の任意の行の２乗ノルムに等しい整数である。
【００２３】
ＤＣＴに対する整数近似を生成する一方法は、一般公式
Ｑ（ｋ、ｎ）＝ｒｏｕｎｄ（ａ＾Ｈ（ｋ、ｎ））
を使用することである。ここでａ＾は倍率変更パラメータである。
【００２４】
Ｈ．２６Ｌビデオ圧縮標準では、４画素×４画素のブロックからイメージが構成され、この場合、Ｈ．２６ＬのＤＣＴ公式においてＮ＝４である。これは、
【００２５】
【数２】
0004560033.tif 000003
【００２６】
に等しいＤＣＴ行列となる。ここでｃ□√２ｃｏｓ（π／８）かつｓ□√２ｓｉｎ（π／８）である。
【００２７】
Ｈ．２６Ｌの現在のバージョンでの変換行列は、ａ＾＝２６と設定することによって得られ、値は、
【００２８】
【数３】
0004560033.tif 000004
【００２９】
と計算される。
【００３０】
倍率変更パラメータ値が２６なので、Ｑ０の行および列は互いに直交であり（すなわち、任意の２つの列の内積が０）、すべての行および列が６７６に等しいノルムを有する。実際、ａ＾＜５０の値に対して、ａ＾＝２またはａ＾＝２６のみが、等しいノルム行を有する直交行列を与える。しかし、ａ＾＝２に対する解は、よい圧縮にならず、ａ＾に対するより大きい値は、直接変換Ｘ＝Ｑ０ｘの結果を計算するのに必要な計算の複雑性（例えば、ワード長）が増すので魅力的ではない。したがって、Ｈ．２６Ｌではａ＾＝２６が今まで選ばれていた。
【００３１】
逆変換はｘ′＝Ｑ０Ｘによって定義され、その結果同様に整数演算で計算することができる。上記定義から、ｘ′＝６７６ｘ、すなわち再構築されたデータｘ′は、元のデータｘを整数利得の６７６（Ｑ０内の任意の行のノルム）によって増幅したものに等しい。
【００３２】
本発明の一態様によれば、符号化および復号化のときに計算の複雑性を著しく減少させ、直交でありさらに異なる値を有する整数近似を使用するブロック変換行列が提供される。より詳細には、ａ＾＝２．５を使用して次の行列が生成される。
【００３３】
【数４】
0004560033.tif 000005
【００３４】
ＱＤの行は互いに直交である一方、それらのノルムは異なり（行０および２は４に等しいノルムを有し、行１および３は１０に等しいノルムを有する）、以下に述べるように、計算の複雑性を著しくは増加させない方法での量子化および非量子化で処理される。
【００３５】
図面の図２に移ると、何らかのタイプの媒体および／または中間デバイス２２０を介して接続可能なブロック変換エンコーダ２００およびブロック変換デコーダ２２２がここに示されている。理解されるように、エンコーダ２００はその出力をデコーダ２２２に対して直接利用可能にする必要はなく、したがって図２内の２２０のラベルを付けられたラインは、ネットワークケーブル、無線伝送媒体、電話回線、記憶装置、ルータ、および／またはそれらの実質的に任意の組み合わせなど、実質的に任意のタイプの媒体またはデバイスを表す。
【００３６】
一般にエンコーダ２００は、（例えば、誤差訂正情報を表す）ＮｘＮ入力画素データ２０２の各ブロックを分離可能な２次元変換２０４を介して変換することによって動作する。より詳細には、最初に、ブロック内の画素データの行が行変換処理２０６によって変換され、次いで行変換の結果（図２には具体的に表されていない）が、列変換処理２０８によって結果としての変換係数２１０に変換される。換言すれば、この２次元ＤＣＴは本質的に、画素ブロックの各行に対して１次元ＤＣＴを実行し、行に対する１次元ＤＣＴによって生成された画素ブロックの各列に対して１次元のＤＣＴを続行する。行および列変換は、反対の順序で実行して同じ結果を得ることができる。
【００３７】
Ｈ．２６Ｌでは、指定された変換行列は、変換係数を計算するための次の公式になる。
Ａ＝１３ａ＋１３ｂ＋１３ｃ＋１３ｄ
Ｂ＝１７ａ＋７ｂ−７ｃ−１７ｄ
Ｃ＝１３ａ−１３ｂ−１３ｃ＋１３ｄ
Ｄ＝７ａ−１７ｂ＋１７ｃ−７ｄ
ここで［ａｂｃｄ］は、最初に４×４ブロック内の画素値の行を表し、次いで行変換後に、それらの行変換されたデータ値の列を表す。しかし、実際には、これらの公式を単純化することができ、ＤＣＴ行列は、必要な乗算および加算演算の数を減らす反復的構造を有する。それにもかかわらず、上記行列は、それぞれの画素に対する変換係数を計算するのに、少なくとも４つの加算および３つの乗算を必要とする。さらに、それぞれの画素は符号付き９ビット値であるので、行および列の要素によって乗算する（利得はノルムである６７６に等しい）とき、その計算は３２ビット演算を必要とする。３２ビット演算は単一計算が多数の１６ビット計算と同じ時間がかかる。これらの考慮は符号化中は通常重要ではないが、これらのＨ．２６Ｌに指定された行列値では、特別な演算および３２ビット演算もまた復号化中に行われ、その労力が著しい。
【００３８】
Ｈ．２６で規定された行列とは対照的に、同じ一般的公式表現を使用すると、上述のように本発明のブロック変換行列は、
【００３９】
【数５】
0004560033.tif 000006
【００４０】
であり、この行列は、変換係数を計算するための次の公式を提供する。
Ａ＝ａ＋ｂ＋ｃ＋ｄ
Ｂ＝２ａ＋ｂ−ｃ−２ｄ
Ｃ＝ａ−ｂ−ｃ＋ｄ
Ｄ＝ａ−２ｂ＋２ｃ−ｄ
【００４１】
この公式／行列がより最適に機能する理由の一部は、変換段階において個々の乗算を実行する代わりに、倍率変更において使用される値を単純に変更することによって、その増倍率が本質的に量子化段階で処理されることである。結果として、これらの公式で唯一の乗算は、２の累乗によるものであり、これはプロセッサ内で、単純な左シフト演算によって達成され、実際の乗算ではない。補助変数としてｕ、ｖ、ｙおよびｚを使用し、「＜＜１」が１ビット左シフト（２を乗じることに等価であるが計算はより速い）を意味する場合、上記公式は、次の公式に単純化される。
ｕ＝ａ＋ｄ、
ｖ＝ｂ＋ｃ、
ｙ＝ｂ−ｃ、
ｚ＝ａ−ｄ、
Ａ＝ｕ＋ｖ、
Ｃ＝ｕ−ｖ、
Ｂ＝ｙ＋（ｚ＜＜１）、
Ｄ＝ｚ−（ｙ＜＜１）
【００４２】
図３内に表されるバタフライ構造を介して、（２点間の線は合計を示し、線上の数（−１、２および−２）は増倍率を示す）これらの変換係数を見つけることは、それぞれの所与の画素に対して４つの加算および１つのシフトだけを実際必要とし、Ｈ．２６Ｌに指定された要素に比べると非常に著しい性能改善を提供する。さらに、より低い係数値のため、すべての変換動作は（９ビットの画素データを有する）１６ビット演算で実行することができる。より詳細には、上記に定義された変換行列ＱＤで、２次元２−Ｄ変換後に、最大信号増幅は３６であり、この２次元変換後の出力係数は、入力より６ビット多く広がる。したがって、９ビットの入力に対して、出力係数は、１５ビットの動的範囲を有し、この２次元直接変換は１６ビット演算で計算できることを意味する。さらに、以下に述べるように、それぞれが１６ビット演算だけを必要とするはるかに少ない演算からもたらされる性能向上は、逆変換を有する復号化演算中に本質的に繰り返され、復号化性能の著しい向上を提供する。
【００４３】
変換係数２１０が計算されると、係数ブロック２１０は、値を倍率変更しそれらをそのもっとも近い整数に丸めることによって量子化される。これは、量子化処理２１２によって図２内に表され、この処理は、量子化パラメータ２１４からの量子化値の中から変換係数２１０を量子化済み係数２１６に倍率変更することを選択する。上述のように、改善された行列内には１つではなくて３つのノルムがあるので、量子化される変換済み係数がブロック内のどこに位置するかに応じて、３つの量子化テーブルＱ０、Ｑ１およびＱ２がこれらの値を含む。
【００４４】
倍率変更および丸めのための量子化公式は、次のとおりであり、３２ビットの正確さで計算されるべきである。
Ｌ＝［Ｋ×Ａ（ＱＰ、ｒ）＋ｆＸ］＞＞２０
ここでＬは量子化済み係数、Ｋは変換済み係数、Ａ（ＱＰ、ｒ）は量子化パラメータＱＰおよびｒによってインデックス付けされた増倍率であり、ｒはどのテーブル（ＱＯ、Ｑｌ、Ｑ２）を使用するかを識別し、ｆＸは範囲［０〜０．５］×２２０（ｆＸはＫと同じ符号を有する）、＞＞２０は数を倍率縮小するために右に２０個シフトすること（１，０４８，５７６で除すること）を意味する。したがって量子化処理には、誤差が持ち込まれる。量子化のために３２ビット演算が使用されるが、これは、符号化のときにのみ必要であり、それは復号化のときほどには重要ではない（非量子化は、以下に述べるように１６ビットの正確さしか必要ではない）ことに留意されたい。
【００４５】
したがってインデックス（索引）ｒは、３つの異なるノルムに適合させるために３つの量子化テーブルＱ０、Ｑｌ、Ｑ２のどれを使用するかを、ブロック内の係数Ｋの位置に基づき選択する。
【００４６】
係数が位置｛（０、０）、（０、１）、（１、０）、（１，１）｝の１つから来た場合、ｒ＝０（Ｑ０を使用）
係数が位置｛（０、２）、（０、３）、（１、２）、（１、３）、（２、０）、（２、１）、（３、０）、（３、１）｝から来た場合、ｒ＝１（Ｑ１を使用）
係数が位置｛（２、２）、（２、３）、（３、２）、（３、３）｝から来た場合、ｒ＝２（Ｑ２を使用）
２０ビット右にシフトの後に、それぞれの量子化済み結果Ｌは１６ビット整数に適合する。
【００４７】
例示的実施例では、増倍率Ａ（ＱＰ、ｒ）は、次のテーブルにしたがって、量子化パラメータＱＰおよび係数位置グループｒに依存する。
Ａ（ＱＰ＝０．．３１，ｒ＝０）＝｛１０４８５８，９３４１８，８３２２６，
７４１４６，６６０５６，５８８４９，５２４２９，４６７０９，４１６１３，
３７０７３，３３０２８，２９４２５，２６２１４，２３３５４，２０８０６，
１８５３６，１６５１４，１４７１２，１３１０７，１１６７７，１０４０３，
９２６８，８２５７，７３５６，６５５４，５８３９，５２０２，４６３４，
４１２９，３６７８，３２７７，２９１９｝；
Ａ（ＱＰ＝０．．３１，ｒ＝１）＝｛６６３１８，５９０８２，５２６３６，
４６８９４，４１７７８，３７２２０，３３１５９，２９５４１，２６３１８，
２３４４７，２０８８９，１８６１０，１６５７９，１４７７１，１３１５９，
１１７２３，１０４４４，９３０５，８２９０，７３８５，６５８０，
５８６２，５２２２，４６５２，４１４５，３６９３，３２９０，２９３１，
２６１１，２３２６，２０７２，１８４６｝；
Ａ（ＱＰ＝０．．３１，ｒ＝２）＝｛４１９４３，３７３６７，３３２９０，
２９６５８，２６４２２，２３５４０，２０９７２，１８６８４，１６６４５，
１４８２９，１３２１１，１１７７０，１０４８６，９３４２，８３２３，
７４１５，６６０６，５８８５，５２４３，４６７１，４１６１，３７０７，
３３０３，２９４２，２６２１，２３３５，２０８１，１８５４，１６５１，
１４７１，１３１１，１１６８｝．
【００４８】
上記の特定の値は、テーブルインデックスが６増える毎に量子化ステップサイズが２倍になるべきであるというＨ．２６Ｌ内の設計仕様を満足させるように定められた。他のビデオまたは固定イメージコード化アプリケーションに対しては、希望する忠実度の増加を考慮して他の量子化テーブルを設計することができる。エンコーダで量子化テーブルを格納するためには、１つではなくて３つのテーブルを格納するための何らかの特別なテーブルスペースが必要であるが、特別なスペースのこの量は、わずか６４バイトであり無視し得ることに留意されたい。
【００４９】
図２に戻ると、量子化処理に続いて、量子化済み係数２１６は、一般にブロックを符号化するのに必要なビット数をさらに減らすエントロピエンコーダ２１８に供給される。エントロピエンコーダ（およびデコーダ）は知られており、したがって本発明がエントロピ符号化の前に実質的に独立して動作し、エントロピ復号化の後に実質的に独立して動作するので、本明細書では述べない。
【００５０】
ブロック変換デコーダ２２２内の復号化を考慮すると、どのように配信されるかにかかわらず、エントロピ符号化済み出力ビットは、エントロピデコーダ２２４に対する入力ビットとして供給される。一般に、そのようなエントロピデコーダは知られており、したがって他の可能な動作の中で、エントロピエンコーダ２２４が所与のブロックに対する量子化済み係数２２６を再生成することを述べれば充分である。通常、符号化および復号化は損失が大きくない、すなわちエントロピエンコーダ２１８に供給される量子化済み係数２１６は、エントロピデコーダ２２４によって生成される量子化済み係数２２６と同一であることに留意されたい。
【００５１】
以下に述べるように、復号化処理全体で１６ビット演算を使用できるように、本発明と調和して、したがってデコーダの計算の複雑性を非常に単純化する修正の逆変換行列が提供されるけれども、一般に、ブロック変換デコーダ２２２は、ブロック変換エンコーダ２００の動作を反映する。
【００５２】
量子化済み係数２２６がエントロピデコーダ２２４から取り出されると、それぞれの量子化済み係数Ｌは、公式
Ｋ′＝Ｌ×Ｂ（ＱＰ、ｒ）
を実行する非量子化処理２２８によって再構築された（非量子化された）値Ｋ′に変換される。ここで、増倍率Ｂは、符号化時に使用されるインデックスＱＰに依存し、ｒは、（３ノルムに適合するための）テーブルＤ０、Ｄ１、Ｄ２の１つからパラメータを選択することによって、非量子化パラメータ２３０を決定する。おそらくデコーダ上の計算の複雑性を減らすが、少なくともｒを識別するために係数毎に２ビット余計に送ることが必要なこのｒ値をエンコーダから送ることは実現可能であるが、量子化に関して上述したように、ブロック内の非量子化されている係数の位置からｒを導き出すことができることに留意されたい。
【００５３】
このように、増倍率Ｂ（ＱＰ、ｒ）は、符号化時に使用されるＱＰに対する量子化パラメータインデックス、および係数位置グループｒに依存する。一例示的実施例では、その依存性は次のテーブルによって指定される。
Ｂ（ＱＰ＝０．．３１，ｒ＝０）＝｛８０，９０，１０１，１１３，１２７，
１４３，１６０，１８０，２０２，２２６，２５４，２８５，３２０，３５９，
４０３，４５３，５０８，５７０，６４０，７１８，８０６，９０５，
１０１６，１１４０，１２８０，１４３７，１６１３，１８１０，２０３２，
２２８１，２５６０，２８７４｝；
Ｂ（ＱＰ＝０．．３１，ｒ＝１）＝｛１０１，１１４，１２７，１４３，
１６１，１８０，２０２，２２７，２５５，２８６，３２１，３６１，４０５，
４５４，５１０，５７２，６４３，７２１，８１０，９０９，１０２０，
１１４５，１２８５，１４４３，１６１９，１８１７，２０４０，２２９０，
２５７０，２８８５，３２３９，３６３５｝；
Ｂ（ＱＰ＝０．．３１，ｒ＝２）＝｛１２８，１４４，１６１，１８１，
２０３，２２８，２５６，２８７，３２３，３６２，４０６，４５６，５１２，
５７５，６４５，７２４，８１３，９１２，１０２４，１１４９，１２９０，
１４４８，１６２５，１８２５，２０４８，２２９９，２５８０，２８９６，
３２５２，３６５０，４０９５，４５９６｝．
【００５４】
符号化テーブルのように、上記特定の値は、量子化ステップサイズがテーブルインデックス内の増分６毎に２倍になるべきであるというＨ．２６Ｌ内の設計仕様を満足させるように定められた。他のビデオまたは固定イメージコード化アプリケーションに対して、希望する忠実さの増加を考慮して、他の量子化テーブルを設計することができる。
【００５５】
理解できるように、これらの増倍率値のそれぞれは、デコーダで１６ビット演算しか必要としないことを保証するほど充分低いが、非量子化公式は、係数をより大きな値に倍率拡大して戻す。テーブル内のそれぞれのエントリが他の２つのテーブル内のＱＰでインデックス付けされた対応するテーブルエントリに（ノルムに基づいて）数学的に関連する。このため、３つのテーブルを有するのではなくて、ｒ値に基づく適切な数学的調整を有するＱＰ値の１テーブルだけを有することが、代替例として可能である。しかし、小さいテーブル内のルックアップは比較的効率的であり、（指定されたＨ．２６Ｌ変換に必要な）エントリ当たり４ビットで３２エントリの１つのテーブルの代わりに、エントリ当たり２バイトで３２エントリの３つのテーブルを格納するために必要なバイト数は６４の余分なバイトであり、現代のコンピューティングデバイスにおいて、特に非量子化によって生成された変換係数が３２ビットのダブルワードではなくて１６ビットワードに適合し、それによって必要なメモリの合計量を減らすことを考慮すると、このバイトは無視し得る。
【００５６】
図２に同様に表すように、量子化済み係数２２６が上記公式およびテーブルを介して非量子化されると、再構築された変換係数２３２の４×４行列が存在する。それらの変換係数２３２から、列および行逆変換処理２３６および２３８をそれぞれ含む２次元逆変換処理２３４にそれらを供給することによって、再構築された画素が生成される。
【００５７】
本発明にしたがって、通常行われる逆変換ＱＩ＝ＱＤＴを使用する代わりに、１６ビット非量子化および逆変換計算を可能にするために、本発明は、次の逆変換行列を定義して使用する。
【００５８】
【数６】
0004560033.tif 000007
【００５９】
ＱＩの列は互いに直交であるがそのノルムは異なることに留意されたい。しかし上述のように、これは非量子化パラメータを選択する際に使用される「ｒ」値を介して処理された。さらに、ＱＤからＱＩを生成する際に、ＱＤは転置され、列１および３は１／２倍された。しかし再び、テーブルＤ０、Ｄ１およびＤ２内に既にあるＱＰ値は、このために事前に調整され、補正するためのどんな追加計算の複雑性も必要ない。さらに、そのような行列で逆変換を計算するときに行う必要のある唯一の「乗算」は、１／２倍であり、実際には非常に効率的な右シフト演算によって実行される。そのような不正確な除算によって導入される小量のノイズは本質的に、レート歪み性能に何もインパクトを有しないことに留意されたい。
【００６０】
上記に定義されたＱＩで、その最大利得は４に等しい。したがって、２次元逆変換処理は、動的範囲を４ビット拡大するのみであり、１６ビット演算の計算を可能にする。
【００６１】
図２に表される列逆変換処理２３６および（列逆変換処理の結果に対して動作する）行逆変換処理２３８は、出力画素データ２４０を生成する。この目的のために、上記逆変換行列を使用し［Ａ  Ｂ  Ｃ  Ｄ］を逆変換すべき特定の行または列とすると、対応する逆変換済み値［ａ′ｂ′ｃ′ｄ′］は、
ｕ＝Ａ＋Ｃ；
ｖ＝Ａ−Ｃ；
ｙ＝（Ｂ＞＞１）−Ｄ；
ｚ＝（Ｄ＞＞１）＋Ｂ；
ａ′＝ｕ＋ｚ；
ｂ′＝ｖ＋ｙ；
ｃ′＝ｖ−ｙ；
ｄ′＝ｕ−ｚ；
によって計算され、ここでｕ、ｖ、ｙおよびｚは補助変数であり、＞＞１は１ビット右にシフト（１／２を乗算することに等価）することを意味する。符号化と同様に、図４に表されるバタフライ構造を介して、これらの方程式は実際に、係数当たりすべて１６ビット演算の４つの加算演算および１つのシフト演算に減少させる。最後に、逆変換処理２３４（図２）は、再構築済み画素値を２−７だけ倍率変更する（７ビット右にシフト演算を介して実行される）。
【００６２】
７ビットシフト後の再構築済み画素値は、９ビットの範囲を有し、したがって逆変換は、１６ビット演算で計算することができる。上述の非量子化テーブルＤ０、Ｄ１、およびＤ２がそのようなので、非量子化方程式は、１６ビット演算で計算されるときにオーバーフローしない。次のテーブルは、Ｈ．２６Ｌに指定されたものに比較して、本発明の変換および逆変換を使用するときの計算の利点のいくつかを要約する。
【００６３】
【表１】
0004560033.tif 000008
【００６４】
容易に理解できるように、そのような節約は、特に１６ビット対応プロセッサ上で著しい。例えば、実際、典型的１６ビットＰＤＡプロセッサは本発明で、復号化の速度がおよそ２倍になる改善をすることができる。
【００６５】
さらに、この変換／逆変換は、品質および圧縮に対するそのインパクトに関してテストされた。（信号対ノイズ比率の増加として通常定義される）コード化利得に対する結果は、本発明の変換をテストデータと共に使用すると、Ｈ２６Ｌ変換に比較して約０．０１ｄＢの損失しかなく、この損失は無視し得るものであり、実際、画素予測誤差などの実際のビデオ信号情報での損失よりはるかに小さい可能性が高い。さらに、３２個の量子化パラメータのそれぞれ全てについて、Ｈ．２６Ｌに指定された変換と比較して全性能がテストされ、プラス／マイナス０．５％の範囲の相違しかなく平均が０に非常に近いという結果となり、それによって、本発明の変換がＨ．２６Ｌに指定された変換と同じほどよい性能であることが示された。
【００６６】
前述の詳細な説明から分かるように、圧縮または品質に不利なインパクトを与えることなく、他の知られている変換に比べて計算の複雑性を著しく減少させる、イメージまたはビデオ符号化および復号化のための改善された変換および逆変換行列がそれぞれここに提供される。変換乗算はなくなるが、変換および逆変換処理中のシフト演算を除いて、量子化および非量子化パラメータ値がそれらの増倍率を補正するので、正しい結果が得られる。使用される値のため、符号化中の変換動作ならびに復号化中の非量子化および変換動作は、（９ビット以下で表される画素データに対する）１６ビット演算で実行することができる。
【００６７】
本発明は様々な修正および代替構築の余地があるが、その特定の例示の実施形態が図面に示され、詳細に上述された。しかし、本発明を開示された具体的形態に制限するものではなく、反対に本発明の精神および範囲内にあるすべての修正、代替構築、および等価物をカバーするものであることを理解されたい。
【図面の簡単な説明】
【００６８】
【図１】本発明を組込むことができる例示的コンピュータシステムを表すブロック図である。
【図２】本発明の一態様による、変換、量子化、非量子化および逆変換を含む、ビデオまたはイメージデータの画素を符号化済みビデオに符号化すること、および符号化済みビデオを画素情報に復号化することの際に使用されるコンポーネントを表すブロック図である。
【図３】本発明の一態様による、改善された変換行列を表すバタフライ構造の構成図である。
【図４】本発明の一態様による改善された逆変換行列を表すバタフライ構造の構成図である。
【符号の説明】
【００６９】
２００  ブロック変換エンコーダ
２０２  入力画素データ
２０４  画素変換処理
２０６  行変換処理
２０８  列変換処理
２１０  変換係数
２１２  量子化処理
２１４  量子化パラメータ
２１６  量子化済み係数（整数）
２１８  エントロピエンコーダ
２２２  ブロック変換デコーダ
２２４  エントロピデコーダ
２２６  量子化済み係数（整数）
２２８  非量子化処理
２３０  非量子化パラメータ
２３２  変換係数
２３４  逆変換処理
２３６  列逆変換処理
２３８  行逆変換処理
２４０  出力画素データ
【図１】
0004560033.tif 000009
【図２】
0004560033.tif 000010
【図３】
0004560033.tif 000011
【図４】
0004560033.tif 000012