(57)【要約】  ブロック変換ベースのデジタルメディアコーデックは、非ゼロ値の係数とゼロ値係数の後続のランとを接合的にコーディングすることによって、より効率的に変換係数をエンコードする（図１４）。ある非ゼロ値係数がそのブロック内の最後である場合、その係数に関しては最終インジケータがシンボル内のラン値の代わりとなる（図１４、項目１４３５）。初めの非ゼロ値係数は、非ゼロ値係数と初めおよび後続のゼロとを接合的にコーディングする、特殊なシンボル内に示される（図１４、項目１４４０）。コーデックは、非ゼロ値係数のラン内のブレークを認識すること、およびこうしたブレークの両側で非ゼロ値係数を別々にコーディングすることによって、複数のコーディングコンテキストが可能である（図１４、項目１４６０）。コーデックは、非ゼロ値係数が１より大きい絶対値を有するかどうか、およびゼロのランが正の値を有するかどうかを、各シンボル内に示すことによって、コードテーブルサイズを縮小し（図１４、項目１４７５）、係数のレベルとランの長さとを別々にシンボルの外でエンコードする（図１４、項目１４９０）。
2009505494.tif 000002
【特許請求の範囲】
【請求項１】
デジタル媒体データを表す変換係数の数列（１３００）をエンコードする方法であって、
変換係数の数列をシンボルの数列（１３４０）として表すステップ（１４００）であって、各シンボル（１３５５）は、前記変換係数の数列内の非ゼロ値係数の表示と、ゼロ値係数の後続のランの長さの表示とを備える、表すステップと、
前記シンボルの数列内の各シンボルについて、圧縮ビットストリーム（４２０）内にエンコードされるべき前記シンボルを送信するステップ（１６００）と
を含み、
前記変換係数の数列内の最後の非ゼロ値係数はシンボル（１３６５）によって表され、前記ゼロ値係数の後続のランの長さの表示は、前記係数が最後の非ゼロ値係数である旨のインジケータを備える、
ことを特徴とする方法。
【請求項２】
前記シンボルの数列内の最初のシンボルは、前記変換係数の数列内の最初の非ゼロ値係数に先行するゼロ値係数のランの長さの表示をさらに備えることを特徴とする請求項１に記載の方法。
【請求項３】
前記変換係数の数列は、広域変換係数の数列の正規化部分を決定した結果として生じることを特徴とする請求項２に記載の方法。
【請求項４】
前記シンボルの数列内の前記最初のシンボルをコーディングするために１つのコードテーブルセットが使用され、前記シンボルの数列内の他のシンボルをコーディングするために異なるコードテーブルセットが使用されることを特徴とする請求項２に記載の方法。
【請求項５】
前記シンボルの数列内の各シンボルは、関連付けられたコンテキストを有することを特徴とする請求項２に記載の方法。
【請求項６】
シンボルに関する前記コンテキストは、前記シンボルによって表される非ゼロ値係数が前記係数の数列内の最初のゼロ値係数の前または後ろのいずれで発生するかということに、少なくとも部分的に基づくことを特徴とする請求項５に記載の方法。
【請求項７】
シンボルに関する前記コンテキストは、前記変換係数の数列が輝度チャネルまたはクロミナンスチャネルのいずれに関するものであるかということに、少なくとも部分的に基づくことを特徴とする請求項５に記載の方法。
【請求項８】
シンボルに関する前記コンテキストは、前記変換係数の数列が内部変換、中間変換、または外部変換のいずれに関するものであるかということに、少なくとも部分的に基づくことを特徴とする請求項５に記載の方法。
【請求項９】
各シンボルに関して、該シンボル内の前記後続のゼロ値係数のランの長さの表示は、
前記ゼロ値係数のランが長さゼロであること、
前記ゼロ値係数のランが正の長さであること、
前記シンボルによって示される前記係数が前記変換係数の数列内の最後の係数であること
という条件のうちの１つを示す、３項シンボルを備えることを特徴とする請求項２に記載の方法。
【請求項１０】
前記シンボルの数列内の前記最初のシンボル内の前記最初の非ゼロ値係数に先行する前記ゼロ値係数のランの長さの表示は、前記最初の非ゼロ値係数に先行する前記ゼロ値係数のランが、長さゼロであるかまたは正の長さであるか否かを示すブール値を備えることを特徴とする請求項９に記載の方法。
【請求項１１】
シンボルが、ゼロ値係数のランが正の長さであることの表示を備える場合、前記ゼロ値係数のランの前記長さを、前記圧縮ビットストリーム内でエンコードするために送信するステップをさらに含むことを特徴とする請求項９に記載の方法。
【請求項１２】
各シンボルに関して、前記変換係数の数列内における、該シンボル内の前記非ゼロ値係数の表示が、前記非ゼロ値係数の前記絶対値が１より大きいか否かを示すブール値を備えることを特徴とする請求項１に記載の方法。
【請求項１３】
シンボルが、非ゼロ値係数が１より大きい絶対値を有することの表示を備える場合、前記非ゼロ値係数の前記絶対値を、前記圧縮ビットストリーム内でエンコードするために送信するステップをさらに含むことを特徴とする請求項１２に記載の方法。
【請求項１４】
エンコード済みデジタル媒体データを格納するためのデータストレージバッファ（２２８０）と、
プロセッサ（２２１０）であって、
変換係数の数列を記述する圧縮シンボルのセット（４２０）を受け取ること、
前記シンボルを圧縮解除すること（５１０）、および
前記圧縮解除されたシンボルのセットを分析することによって、前記変換係数の数列を再構築すること（５２０）
を実行するように構成されたプロセッサ（２２１０）と
を備え、
前記圧縮シンボルのセットは、コンテキストモデルに従って、コードテーブルのセットからエンコードされた（１６００）接合的にコーディングされたシンボル（１３４０）を備え、
各接合的にコーディングされたシンボル（１３５５）は、前記変換係数の数列内の非ゼロレベルと、前記非ゼロレベルに続くゼロ値係数が存在するかどうかとを、記述することを特徴とするデジタル媒体デコーダ。
【請求項１５】
各接合的にコーディングされたシンボルは、前記非ゼロレベルの絶対値が１より大きいかどうかを示すことによって、非ゼロレベルを記述し、
前記圧縮シンボルのセットは、各非ゼロレベルの前記値およびレベル符号の表示を記述するレベルシンボルをさらに備え、
さらに前記プロセッサは、絶対値が１より大きい非ゼロレベルを示す接合的にコーディングされたシンボルを分析する場合、前記非ゼロレベルの前記値を記述する前記レベルシンボルを見つけることを使用して、前記非ゼロレベルを再構築することを実行するように構成されることを特徴とする請求項１４に記載のデジタル媒体デコーダ。
【請求項１６】
前記圧縮シンボルのセット内の最初のシンボルは、前記変換係数の数列内に、前記非ゼロレベルに先行するゼロ値係数が存在するかどうかをさらに記述することを特徴とする請求項１４に記載のデジタル媒体デコーダ。
【請求項１７】
各接合的にコーディングされたシンボルは、前記ゼロ値係数のランの長さが０より大きいかどうかを示すことによって、ゼロ値係数のランを記述し、
前記圧縮シンボルのセットは、長さがゼロより大きいゼロ値係数の各ランの前記長さを記述するランシンボルをさらに備えることを特徴とする請求項１４に記載のデジタル媒体デコーダ。
【請求項１８】
圧縮デジタル媒体データをデコードする方法を実行するためのデジタル媒体デコーディングプログラムを記述する命令を搬送する、１つまたは複数のコンピュータ読み取り可能媒体であって、前記方法は、
コンテキストモデルに従って、コードテーブルのセットからエンコードされた、圧縮済みの接合的にコーディングされたシンボル（１３４０）を備えるビットストリーム（４２０）を受け取るステップ（２０００）と、
各シンボルに関して、変換係数レベルおよび後続の変換係数ゼロのランを決定するために、前記接合的にコーディングされたシンボルをデコードするステップ（２０００）と、
前記決定されたレベルおよび変換係数ゼロのランから、変換係数のセットを再構築するステップ（２１００）と
を含むことを特徴とするコンピュータ読み取り可能媒体。
【請求項１９】
前記ビットストリームは初めの接合的にコーディングされたシンボルをさらに備え、前記方法は、初めの変換係数ゼロのランと、変換係数レベルと、後続の変換係数ゼロのランとを決定するために、前記初めの接合的にコーディングされたシンボルをデコードするステップをさらに有することを特徴とする請求項１８に記載のコンピュータ読み取り可能媒体。
【請求項２０】
前記接合的にコーディングされたシンボルは、各変換係数レベルに関して、そのレベルが１より大きい絶対値を有するかどうかを示し、
前記接合的にコーディングされたシンボルは、各変換係数ゼロのランに関して、そのランが０より大きい長さを有するかどうかを示し、
前記ビットストリームは、前記変換係数ゼロのランの長さと、変換係数レベルの符号および大きさとを記述する、圧縮シンボルをさらに備え、
前記接合的にコーディングされたシンボルをデコードするステップは、
その変換係数レベルが１より大きい絶対値を有することを示す接合的にコーディングされたシンボルをデコードする場合、前記変換係数レベルの前記符号および値を示す前記ビットストリーム内の１つまたは複数のシンボルをデコードすることによって、その前記変換係数レベルを決定するステップと、
その変換係数ゼロのランが０より大きいことを示す接合的にコーディングされたシンボルをデコードする場合、前記ランの長さを示す前記ビットストリーム内のシンボルをデコードすることによって、前記変換係数ゼロのランの前記長さを決定するステップと
を備えることを特徴とする請求項１８に記載のコンピュータ読み取り可能媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
デジタル媒体データをエンコード及びデコードする方法に関する。
【背景技術】
【０００２】
変換コーディング（Transform coding）は、多くのオーディオ、イメージ、およびビデオの圧縮システムで使用される圧縮技法である。非圧縮のデジタルイメージおよびビデオは、通常、２次元（２Ｄ）グリッドで配列されたイメージまたはビデオフレーム内の位置で、ピクチャ要素または色のサンプルとして表現またはキャプチャされる。これは、イメージまたはビデオの空間領域表現と呼ばれる。例えば、イメージの通常のフォーマットは、グリッドとして配列された２４ビットのカラーピクチャ要素サンプルのストリームからなる。各サンプルは、とりわけＲＧＢまたはＹＩＱなどの色空間内での、グリッド内のピクセル位置で色構成要素を表す番号である。様々なイメージおよびビデオシステムは、様々な異なる色、空間、および時間のサンプリング解像度を使用することができる。同様に、デジタルオーディオは、通常、時間サンプリングされたオーディオ信号ストリームとして表される。例えば典型的なオーディオフォーマットは、定期的な時間間隔で採取されたオーディオ信号の１６ビット振幅サンプルのストリームからなる。
【０００３】
非圧縮のデジタルオーディオ、イメージ、およびビデオの信号は、かなりの格納および伝送容量を消費する可能性がある。変換コーディングは、この信号の空間領域表現を周波数領域（または他の同様の変換領域）表現に変換し、その後、一般にはそれほど知覚できない程度に変換領域表現の周波数構成要素の解像度を低減させることによって、デジタルオーディオ、イメージ、およびビデオのサイズを縮小する。これによって、通常、空間領域内のイメージまたはビデオの、あるいは時間領域内のオーディオの、色または空間解像度の低減に比べて、ほとんど知覚できない程度のデジタル信号の劣化が生じる。
【０００４】
とりわけ、図１に示された典型的なブロック変換ベースコーデック１００は、非圧縮デジタルイメージのピクセルを固定サイズの２次元ブロック（Ｘ１，．．．Ｘｎ）に分割し、各ブロックは他のブロックと重複する可能性がある。空間周波数分析を行う線形変換１２０〜１２１が各ブロックに適用され、これによってブロック内の空間サンプルは、一般に、ブロック間隔にわたる対応する周波数帯域内のデジタル信号の強度を表す、周波数（または変換）係数のセットに変換される。圧縮の場合、変換係数の選択的な量子化１３０（すなわち、係数値の最下位ビットをドロップすること、またはそうでなければ、高解像度数セット内の値を低解像度にマッピングすることなどによって、解像度を低下させる）、および、圧縮データストリームへのエントロピまたは可変長コーディング１３０も、可能である。デコード時には、オリジナルの色／空間サンプリングイメージ／ビデオ信号をほぼ再構築する（再構築ブロック
【０００５】
【数１】
2009505494.tif 000003
【０００６】
）ために、変換係数が逆変換１７０〜１７１されることになる。
【０００７】
ブロック変換１２０〜１２１は、サイズＮのベクトルｘに関する数学演算として定義することができる。ほとんどの場合、この演算は変換領域出力ｙ＝Ｍｘを生成する線形乗算であり、Ｍは変換行列である。入力データが任意の長さである場合、Ｎサイズベクトルにセグメント化され、各セグメントにブロック変換が適用される。データ圧縮の目的で、可逆的ブロック変換が選択される。言い換えれば、行列Ｍは可逆的である。多次元の場合（例えばイメージおよびビデオの場合）、ブロック変換は通常、分離可能操作として実施される。行列乗算は、データの各次元（すなわち行および列の両方）に沿って、別々に適用される。
【０００８】
圧縮の場合、変換係数（ベクトルｙの構成要素）の選択的な量子化（すなわち、係数値の最下位ビットをドロップすること、またはそうでなければ、高解像度数セット内の値を低解像度にマッピングすることなどによって、解像度を低下させる）、および、圧縮データストリームへのエントロピまたは可変長コーディングも、可能である。
【０００９】
デコーダ１５０におけるデコード時には、図１に示される様に、これらの操作の逆（逆量子化／エントロピデコーディング１６０および逆ブロック変換１７０〜１７１）がデコーダ１５０側に適用される。データを再構築する間に、逆行列Ｍ１（逆変換１７０〜１７１）が乗数として変換領域データに適用される。逆変換は、変換領域データに適用された場合、オリジナルの時間領域または空間領域のデジタルメディアをほぼ再構築する。
【００１０】
多くのブロック変換ベースのコーディングアプリケーションでは、変換は、量子化因数に応じて不可逆（ｌｏｓｓｙ）圧縮および可逆（ｌｏｓｓｌｅｓｓ）圧縮の両方をサポートするために、望ましくは可逆的である。例えば量子化なし（一般に、量子化因数１で表される）の場合、可逆的変換を使用するコーデックは、デコード時に入力データを正確に再生成することができる。しかしながら、これらの適用例における可逆性の要件は、コーデックを設計する際に基にする変換選択肢を制約する。
【００１１】
とりわけＭＰＥＧおよびＷｉｎｄｏｗｓ（登録商標）  Ｍｅｄｉａなどの多くのイメージおよびビデオ圧縮システムは、離散コサイン変換（ＤＣＴ）に基づく変換を私用する。ＤＣＴは、結果として近最適データ圧縮を生じさせる、有益なエネルギー圧縮特性を持つとして知られている。これらの圧縮システムでは、個々のイメージブロックを再構築するために、圧縮のエンコーダおよびデコーダの両方の再構築ループにおいて、逆ＤＣＴ（ＩＤＣＴ）が採用される。
【００１２】
ワイドレンジ変換係数のエントロピコーディング
ワイドダイナミックレンジ（ｗｉｄｅ  ｄｙｎａｍｉｃ  ｒａｎｇｅ）入力データは、イメージのエンコーディングプロセス中に生成される、さらにワイドなダイナミックレンジ変換係数につながる。例えば、Ｎ掛けるＮ  ＤＣＴ操作によって生成される変換係数は、オリジナルデータのダイナミックレンジのＮ倍よりもワイドなダイナミックレンジを有する。小さいかまたは１の量子化因数（低損失または可逆圧縮を実現するために使用される）を使用する場合、量子化される変換係数のレンジも大きい。統計的には、これらの係数は、図２および３に示されるようなラプラス分布を有する。図２は、ワイドダイナミックレンジ係数に関するラプラス分布を示す。図３は、典型的なナローダイナミックレンジ係数に関するラプラス分布を示す。
【００１３】
従来の変換コーディングは、ナローダイナミックレンジの入力データ（通常は８ビット）、および比較的大きな量子化子（ｑｕａｎｔｉｚｅｒ）（４およびそれ以上の数値など）用に調整される。したがって、図３は、こうした従来の変換コーディングにおける変換係数の分布を表す。さらに、こうした従来の変換コーディングで使用されるエントロピエンコーディングは、実行レベルエンコーディングの変形とすることが可能であり、ゼロの連続と非ゼロシンボルとが一緒にエンコードされる。これは、ゼロのラン（高い確率で発生する）、ならびにシンボル間の相関関係のキャプチャを表すための効果的な手段とすることができる。
【００１４】
他方で、従来の変換コーディングは、図２に示されるようなワイドダイナミックレンジ分布の圧縮には適していない。シンボルは任意の他の値よりもゼロである確率が高い（すなわち、分布のピークがゼロである）が、ある係数がゼロである確率は、ワイドダイナミックレンジ分布の場合極めて低い。したがって、ゼロは頻繁には発生せず、連続する非ゼロ値係数間のゼロの数に基づくラン長さエントロピコーディング技法は、ワイドダイナミックレンジ入力データには非常に非効率的である。
【００１５】
ワイドダイナミックレンジ分布には、ナローレンジ分布に比べて、シンボルのアルファベットの増加も見られる。このシンボルアルファベットの増加により、シンボルをエンコードするために使用されるエントロピテーブルは必然的に大きくなる。そうでない場合、多くのシンボルはコーディングされずに終わることになり、非効率的である。テーブルが大きくなるほど大きなメモリが必要であり、その結果、より複雑になる可能性もある。
【００１６】
したがって、従来の変換コーディングは多様性に欠けており、ナローダイナミックレンジ分布の場合は入力データに対して良好な働きをするが、ワイドダイナミックレンジ分布の場合はそうではない。
【００１７】
しかしながら、ナローレンジデータの場合、量子化された変換係数の効率的なエントロピコーディングを見つけることが不可欠なプロセスである。このステップで達成可能ないかなる性能利得（圧縮効率およびエンコード／デコード速度の両方に関する利得）も、全体の品質利得に変換される。
【００１８】
コンテキスト情報の使用、高圧縮要件（算術コーディングなど）、低圧縮要件（ハフマン符号化技法に見られるような）、およびエンコーダ／デコーダのメモリオーバヘッドを最小限にするための簡潔なコードテーブルセットの使用などのような、異なる種類の効率性基準を首尾よく利用できるように、様々なエントロピエンコーディングスキームの機能が特徴付けられている。
【発明の開示】
【発明が解決しようとする課題】
【００１９】
これらすべての特徴に合致しない従来のエントロピエンコーディング方法は、エンコーディング変換係数の完全な効率性を実証するものではない。
【課題を解決するための手段】
【００２０】
本明細書に記載されたデジタルメディアコーディングおよびデコーディング技法、ならびにデジタルメディアコーデックにおけるこの技法の実現は、変換係数のより効果的な圧縮を達成する。例えば、本明細書に示された例示的なブロック変換ベースのデジタルメディアコーデックは、非ゼロの係数ならびにゼロ値係数の連続するランを接合的にコーディングすることによって、より効率的に変換係数をエンコードする。ある非ゼロ値係数がそのブロックの最後である場合、最終インジケータがその係数に関するシンボル内のラン値の代わりとなる。初めの非ゼロ値係数は、非ゼロ値係数ならびに初めおよび後続のゼロのランを接合的にコーディングする、特殊なシンボル内に示される。
【００２１】
例示的コーデックは、非ゼロ値係数のラン内のブレークを認識すること、およびこうしたブレークの両側で別々に非ゼロ値係数をコーディングすることによって、複数のコーディングコンテキストが可能である。追加のコンテキストは、内部、中間、および外部の変換に基づくコンテキスト切り替えによって、ならびに変換が輝度またはクロミナンスのチャネルに対応するかどうかに基づくコンテキスト切り替えによって、提供される。これにより、コードテーブルは、コンテキストの有用性を弱めるほど多くのコンテキストを作成することなく、より小さなエントロピを有することができる。
【００２２】
例示的コーデックは、非ゼロ値係数が１より大きい絶対値を有するかどうか、およびゼロのランが正の値を有するかどうかを、各シンボル内に示すことによって、コードテーブルサイズも縮小し、係数のレベルとシンボル外部のランの長さとを別々にエンコードする。コーデックは、これらの別々にコーディングされたランおよびレベルに関するコンテキスト切り替えを利用することができる。
【００２３】
様々な技法およびシステムを組み合わせて、または独立して使用することができる。
【００２４】
この課題を解決するための手段は、以下の発明を実施するための最良の形態でさらに説明される、簡略化された形の概念の選択を紹介するために設けられている。この課題を解決するための手段は、記載された主題の主要な特徴または不可欠な特徴を識別することを意図するものではなく、また記載された主題の範囲を決定する際の補助として使用されることを意図するものでもない。
【００２５】
追加の特徴および利点は、添付の図面を参照しながら進められる以下の諸実施形態の詳細な説明から明らかとなろう。
【発明を実施するための最良の形態】
【００２６】
以下の説明は、ワイドレンジ変換係数のより効率的なエントロピコーディング用、ならびに一般的な変換係数のより効率的なエントロピコーディング用に、適応的に調整する、コーディングおよびデコーディング技法に関する。以下の説明は、デジタルメディア圧縮システムまたはコーデックとのコンテキストにおける、この技法の例示的実施について説明する。デジタルメディアシステムは、伝送または格納のために圧縮形式でデジタルメディアデータをコーディングし、再生または他の処理のためにデータをデコーディングする。説明では、このワイドレンジ係数の適応（ａｄａｐｔｉｖｅ）コーディングを組み込んだこの例示的圧縮システムは、イメージまたはビデオ圧縮システムである。別法として、この技法を他の２Ｄデータに関する圧縮システムまたはコーデックに組み込むこともできる。ワイドレンジ係数の適応コーディング技法は、デジタルメディア圧縮システムが、圧縮済みのデジタルメディアデータを特定のコーディング形式でエンコーディングすることを必要としない。
【００２７】
１．エンコーダ／デコーダ
図４および５は、代表的な２次元（２Ｄ）データのエンコーダ４００およびデコーダ５００で使用されるプロセスを示す概括図である。この図は、ワイドレンジ係数の適応コーディングを実施する２Ｄデータのエンコーダおよびデコーダを組み込んだ圧縮システムの、概括図または簡略図を提示する。ワイドレンジ係数の適応コーディングを使用する代替圧縮システムでは、この代表的なエンコーダおよびデコーダに示されるよりも多いかまたは少ないプロセスを、２Ｄデータ圧縮に使用することができる。例えば、一部のエンコーダ／デコーダは、カラー変換、カラーフォーマット、スケーラブルコーディング、可逆コーディング、マクロブロックモードなども含むことができる。圧縮システム（エンコーダおよびデコーダ）は、可逆から不可逆へと変化する量子化パラメータに基づくことが可能な量子化に依存する、２Ｄデータの可逆および／または不可逆圧縮を提供することができる。
【００２８】
２Ｄデータエンコーダ４００は、エンコーダへの入力として提示された２Ｄデータ４１０の（典型的な入力に関する）よりコンパクトな表現である、圧縮ビットストリーム４２０を生成する。例えば２Ｄデータ入力は、イメージ、ビデオシーケンスのフレーム、または他の２次元を有するデータとすることができる。２Ｄデータエンコーダは、この代表的なエンコーダでは１６×１６ピクセルサイズであるマクロブロックに、入力データをタイル表示（ｔｉｌｅ）４３０する。さらに２Ｄデータエンコーダは、各マクロブロックを４×４ブロックにタイル表示する。ブロック間の各縁部に「順方向オーバラップ」演算子４４０が適用され、その後、ブロック変換４５０を使用して各４×４ブロックが変換される。このブロック変換４５０は、Ｓｒｉｎｉｖａｓａｎによる２００４年１２月１７日出願の米国特許出願第１１／０１５７０７号、名称「Reversible Transform For Lossy And Lossless 2-D Data Compression」に記載された、可逆性のスケールフリーな２Ｄ変換とすることができる。オーバラップ演算子４４０は、Ｔｕらによる２００４年１２月１７日出願の米国特許出願第１１／０１５１４８号、名称「Reversible Overlap Operator for Efficient Lossless Data Compression」、および、Ｔｕらによる２００５年１月１４日出願の米国特許出願第１１／０３５９９１号、名称「Reversible 2-Dimensional Pre-/Post-Filtering For Lapped Biorthogonal Transform」に記載された、可逆性のオーバラップ演算子とすることができる。別法として、離散コサイン変換または他のブロック変換およびオーバラップ演算子を使用することができる。変換に続いて、各４×４変換ブロックのＤＣ係数４６０に、同様の処理チェーン（タイル表示、順方向オーバラップ、それに続く４×４ブロック変換）が施される。結果として生じるＤＣ変換係数およびＡＣ変換係数が、量子化４７０、エントロピコーディング４８０、およびパケット化４９０される。
【００２９】
デコーダは、逆プロセスを実行する。デコーダ側では、変換係数ビットがそれぞれのパケットから抽出５１０され、そこから係数自体がデコーディング５２０および逆量子化（ｄｅｑｕａｎｔｉｚｅ）５３０される。ＤＣ係数５４０は、逆変換を適用することによって再生成され、ＤＣ係数のプレーンは、ＤＣブロック縁部をまたがって適用される好適な平滑化演算子を使用して「逆方向オーバラップ」される。その後、４×４逆方向変換５５０をＤＣ係数に適用することによって、データ全体が再生成され、ＡＣ係数５４２がビットストリームからデコーディングされる。最終的に、結果として生じるイメージプレーン内のブロック縁部が逆方向オーバラップフィルタリング５６０される。これにより、再構築された２Ｄデータ出力が生成される。
【００３０】
例示的実施形態では、可逆または不可逆のいずれのコーディングが使用されるかに基づいて、エンコーダ４００（図４）が入力イメージを圧縮ビットストリーム４２０（例えばファイル）に圧縮し、デコーダ５００（図５）がオリジナルの入力またはその近似値を再構築する。エンコーディングのプロセスは、以下で論じる順方向重複変換（ｌａｐｐｅｄ  ｔｒａｎｓｆｏｒｍ）（ＬＴ）を含み、この変換は、同じく以下でより詳細に説明する可逆性２次元事前／事後フィルタリングで実施される。デコーディングプロセスは、可逆性２次元事前／事後フィルタリングを使用する、逆方向重複変換（ＩＬＴ）の適用を含む。
【００３１】
例示されたＬＴおよびＩＬＴは、正確に言えば互いに正反対であるため、まとめて可逆性重複変換と呼ばれる場合もある。このＬＴ／ＩＬＴペアは、可逆性変換として可逆イメージ圧縮に使用することができる。
【００３２】
例示されたエンコーダ４００／デコーダ５００によって圧縮される入力データ４１０は、様々なカラーフォーマット（例えば、ＲＧＢ／ＹＵＶ  ４：４：４、ＹＵＶ  ４：２：２、またはＹＵＶ  ４：２：０の、カラーイメージフォーマット）のイメージとすることができる。通常、入力イメージは、常に輝度（Ｙ）構成要素を有する。ＲＧＢ／ＹＵＶ  ４：４：４、ＹＵＶ  ４：２：２、またはＹＵＶ  ４：２：０のイメージの場合、そのイメージは、Ｕ構成要素およびＶ構成要素などのクロミナンス構成要素も有する。イメージの別々のカラープレーンまたは構成要素は、異なる空間解像度を有することができる。例えば、ＹＵＶ  ４：２：０のカラーフォーマットの入力イメージの場合、ＵおよびＶ構成要素は、Ｙ構成要素の半分の幅および高さを有する。
【００３３】
前述のように、エンコーダ４００は、入力イメージまたはピクチャをマクロブロックにタイル表示する。例示的な実施では、エンコーダ４００は入力イメージをＹチャネル内の１６×１６のマクロブロック（カラーフォーマットに応じて、ＵおよびＶチャネル内の１６×１６、１６×８、または８×８域であってもよい）にタイル表示する。各マクロブロックのカラープレーンは、４×４領域またはブロックにタイル表示される。したがって、マクロブロックは、この例示的エンコーダ実施に関して、以下のように様々なカラーフォーマット用に構成される。
【００３４】
１．グレースケールイメージの場合、各マクロブロックは１６の４×４輝度（Ｙ）ブロックを含む。
【００３５】
２．ＹＵＶ  ４：２：０フォーマットのカラーイメージの場合、各マクロブロックは１６の４×４  Ｙブロック、および４つのそれぞれ４×４クロミナンス（ＵおよびＶ）のブロックを含む。
【００３６】
３．ＹＵＶ  ４：２：２フォーマットのカラーイメージの場合、各マクロブロックは１６の４×４  Ｙブロック、および８つのそれぞれ４×４クロミナンス（ＵおよびＶ）のブロックを含む。
【００３７】
４．ＲＧＢまたはＹＵＶ  ４：４：４カラーイメージの場合、各マクロブロックは、それぞれＹ、Ｕ、およびＶチャネルの１６のブロックを含む。
【００３８】
２．ワイドレンジ係数の適応コーディング
ワイドダイナミックレンジデータ、特に（図４のエンコーダの係数４６０、４６２などの）無相関（ｄｅｃｏｒｒｅｌａｔｅｄ）変換データの場合、かなりの数の低位ビットが予測不可能であり「ノイジー（ｎｏｉｓｙ）」である。言い換えれば、効率的なエントロピコーディングに使用可能な低位ビットには、それほど多くの相関関係がない。このビットは、エンコーディングされたあらゆるビットに対して、１ビットに近い高エントロピを有する。
【００３９】
２．１  グループ化
さらに、
【００４０】
【数２】
2009505494.tif 000004
【００４１】
によって、図３に示されたワイドレンジ変換係数のラプラス確率分布関数が与えられる（便宜上、変換係数に対応する確率変数は連続値として扱われる）。ワイドダイナミックレンジデータの場合、λは小さく、絶対平均１／λは大きい。この分布の傾斜は±１／２内で境界が画され（λ２）、これは非常に小さい。これは、変換係数がｘに等しい確率が、小さなシフトξに関するｘ＋ξの確率に非常に近いことを意味する。離散領域内では、これは「隣接する値ｊおよび（ｊ＋１）を取る変換係数の確率がほぼ同じである」という主張になる。
【００４２】
次に図６を参照すると、ワイドレンジ係数の適応コーディングは、アルファベットの連続するシンボルの、Ｎシンボルの「ビン」へのグループ化６１０を実行する。１ビン当たりのシンボル数は、任意の数Ｎとすることができる。しかしながら実用上、数Ｎは望ましくは２の累乗（すなわちＮ＝２ｋ）であるため、ビン内の係数のインデックスまたはアドレスを固定長コードとして効率的にエンコードすることができる。例えば、シンボルはペアにグループ化することが可能であり、その結果、あるシンボルを、ペア内のシンボルのインデックスと共に、ペアのインデックスとして識別することができる。
【００４３】
このグループ化には、Ｎを好適に選択できることによって、ワイドレンジ係数に関するビンインデックスの確率分布が、例えば図３に示されたナローレンジデータの確率分布にさらによく似たものとなるという利点がある。グループ化は、量子化演算と数学的に同様である。これは、ナローレンジ確率分布を有するデータで最も良い働きをする可変長エントロピコーディング技法を使用して、ビンインデックスを効率的にエンコードできることを意味する。
【００４４】
係数をビンにグループ化することに基づいて、エンコーダは、そのビンのインデックス（本明細書では正規化係数６２０とも呼ばれる）およびビン内のそのアドレス（ビンアドレス６２５とも呼ばれる）を使用して、変換係数６１５をエンコードすることができる。正規化係数は可変長エントロピコーディングを使用してエンコードされるが、ビンアドレスは固定長コードを使用してエンコードされる。
【００４５】
Ｎ（または同等に、ビンアドレスの固定長コーディングに関するビットｋの数）の選択により、グループ化の細分性が決定する。一般に、変換係数のレンジが広くなるほど、選択するべきｋの値は大きくなる。ｋが慎重に選択された場合、正規化係数Ｙはゼロであり、Ｙに関するエントロピコーディングスキームに合致する確率が高い。
【００４６】
以下で説明するように、エンコーダおよびデコーダにおいて、値ｋは適宜（後方適応方式で）変化する可能性がある。より具体的に言えば、エンコーダおよびデコーダの両方で、ｋの値は、以前にエンコード／デコードされたデータに基づいてのみ変化する。
【００４７】
図７に示されたこのエンコーディングの特定の一例では、エンコーダは以下のように変換係数Ｘをエンコードする。初めのアクション７１０では、エンコーダは変換係数について正規化係数Ｙを算出する。この実施例では、正規化係数Ｙは、一定のビンサイズＮ＝２ｋを選択する場合、Ｙ＝ｓｉｇｎ（Ｘ）＊ｆｌｏｏｒ（ａｂｓ（Ｘ）／Ｎ）として定義される。エンコーダは、エントロピコードを使用して、シンボルＹを個別に、または他のシンボルと接合的に、エンコードする（アクション７２０）。次にアクション７３０で、エンコーダは、変換係数Ｘのビンアドレス（Ｚ）を決定する。この実施例では、ビンアドレスは、ビンサイズＮによるａｂｓ（Ｘ）の整数除算の剰余、すなわちＺ＝ａｂｓ（Ｘ）％Ｎである。エンコーダは、アクション７４０で、この値をｋビットの固定長コードとしてエンコードする。さらに非ゼロ変換係数の場合、エンコーダは符号もエンコードする。より具体的に言えば、アクション７５０〜７６０で示されるように、正規化係数が非ゼロの場合、エンコーダは正規化係数（Ｙ）の符号をエンコードする。さらに、正規化係数がゼロであり、変換係数が非ゼロの場合、エンコーダは変換係数（Ｘ）の符号をエンコードする。正規化係数は可変長エントロピコードを使用してエンコードされるため、本明細書では可変長部分とも呼ばれ、ビンアドレス（Ｚ）は固定長部分とも呼ばれる。他の代替実施では、正規化係数、ビンアドレス、および変換係数の符号の数学的定義は、変更可能である。
【００４８】
さらにこの例を続けると、図８は、プロセス７００（図７）によってエンコードされた変換係数を再構築するための、デコーダ５００（図５）によるプロセス例８００を示す。アクション８１０で、デコーダは、圧縮ビットストリーム４２０（図５）から正規化係数（Ｙ）を個別に、または、ブロックコーディングプロセスで定義されたように他のシンボルと一緒に、デコードする。さらにデコーダは、アクション８２０で、ビンアドレスおよび符号（エンコードされた場合）に関するｋビットのコードワードを圧縮ビットストリームから読み取る。次にアクション８３０から８７２で、デコーダは、以下のように変換係数を再構築する。
【００４９】
１．Ｙ＞０（アクション８３０）の場合、変換係数はＸ＝Ｙ＊Ｎ＋Ｚとして再構築される（アクション８３１）。
【００５０】
２．Ｙ＜０（アクション８４０）の場合、変換係数はＸ＝Ｙ＊Ｎ−Ｚとして再構築される（アクション８４１）。
【００５１】
３．Ｙ＝０およびＺ＝０（アクション８５０）の場合、変換係数はＸ＝０として再構築される（アクション８５１）。
【００５２】
４．Ｙ＝０およびＺ≠０の場合、さらにデコーダは、圧縮ビットストリームからエンコード済み符号（Ｓ）を読み取る（アクション８６０）。符号が正（Ｓ＝０）（アクション８７０）の場合、変換係数はＸ＝Ｚとして再構築される（アクション８７１）。そうではなく、符号が負（Ｓ＝１）の場合、変換係数はＸ＝−Ｚとして再構築される（アクション８７２）。
【００５３】
２．２  レイヤ化
再度図６を参照すると、望ましくはエンコーダおよびデコーダは、固定長コーディング済みビンアドレス６２５および符号を、圧縮ビットストリーム４２０（図４）内の別のコード済みレイヤ（本明細書では「フレックスビット（Ｆｌｅｘｂｉｔ）」レイヤ６４５と呼ばれる）に抽象化する。正規化係数６２０は、コアビットストリーム６４０のレイヤ内にエンコードされる。これによりエンコーダおよび／またはデコーダが、ビットレートまたは他の制約を満たすために、所望の通りに、エンコーディングのこのフレックスビット部分をグレードダウンするか、または完全にドロップするというオプションを可能にする。エンコーダがフレックスビットレイヤを完全にドロップする場合であっても、圧縮ビットストリームは、たとえ品質が低下しても依然としてデコードすることになる。デコーダは、正規化係数部分のみからでも依然として信号を再構築することができる。これは、エンコーダにおいてより多くの量子化４７０（図４）を適用することと、事実上同様である。ビンアドレスおよび符号を別のフレックスビットレイヤとしてエンコーディングすることには、何からのエンコーダ／デコーダの実施において、さらに圧縮を向上させるために、他の可変長エントロピコーディング（例えば、算術コーディング、Ｌｅｍｐｅｌ−Ｚｉｖ、Ｂｕｒｒｏｗｓ−Ｗｈｅｅｌｅｒなど）がこのレイヤ内のデータに適用可能であるという、潜在的な利点もある。
【００５４】
レイヤ化の場合、フレックスビット部分を含む圧縮ビットストリームの諸セクションは、ビットストリーム内の別のレイヤヘッダまたは他の表示によって信号が送られるため、デコーダは、コアビットストリーム６４０からフレックスビットレイヤ６４５（除外されない場合）を識別および分離（すなわち解析）することができる。
【００５５】
レイヤ化は、後方適応グループ化（以下の項で説明）の設計において、別の問題も提示する。フレックスビットレイヤは、所与のビットストリーム内に存在する場合または存在しない場合があるため、後方適応グループ化モデルは、フレックスビットレイヤ内の任意の情報を確実に参照することができない。（ビンサイズＮ＝２ｋに対応する）固定長コードビットｋの数を決定するために必要なすべての情報は、一時的な（ｃａｓｕａｌ）コアビットストリームに常駐するものとする。
【００５６】
２．３  適合
さらにエンコーダおよびデコーダは、エンコーディングおよびデコーディング時に、固定長コードビットの数ｋの選択、およびそれに応じて前述のグループ化のビンサイズＮの選択を、適応的に調整するための、後方適合プロセスを提供する。一実施では、適合プロセスは、変換係数のラプラス分布としてのモデル化に基づくものとすることが可能であるため、ｋの値はラプラスパラメータλから導出される。しかしながら、こうした高度なモデルでは、今後のブロックに関する分布をモデル化するのに先立って、デコーダが図６のグループ化６１０の逆（コアビットストリーム６４０内の正規化係数と、フレックスビットレイヤ６４５内のビンアドレス／符号との両方からの、変換係数の再構築）を実行することが必要となる。この要件は、デコーダが圧縮ビットストリーム４２０からのフレックスビットレイヤのドロップを許可するべきであるというレイヤ制約に違反することになる。
【００５７】
図９に示された実施例では、適合プロセス９００は、代わりに、係数のおよそ４分の１が非ゼロである場合、変換係数のより最適なラン長さエンコーディングが達成されるという観測結果に基づくものである。したがって、正規化係数のおよそ４分の３がゼロである「スイートスポット」状況に向けてグループ化を調節するために使用可能な適合パラメータは、良好なエントロピコーディング性能を提供することになる。したがって、あるブロック内の非ゼロの正規化係数の数は、この実施例では適合パラメータとして使用される。この適合パラメータは、変換係数が依然としてフレックスビットレイヤを除外してデコードすることができるという、レイヤ化制約を満たす、コアビットストリーム内に含まれる情報にのみ依存するという利点を有する。このプロセスは、現在のブロックをエンコーディング／デコーディングする場合に適用される適合モデルが、以前のブロックからの情報に基づくものであるという意味で、後方適合である。
【００５８】
その適合プロセスでは、このエンコーダおよびデコーダの例は後方適合ベースで適合を実行する。すなわち、適合の現在の反復は、以前のブロックまたはマクロブロック内などの、エンコーディングまたはデコーディングプロセスで以前に見られた情報に基づくものである。このエンコーダおよびデコーダの例では、所与の変換帯域についてマクロブロックごとに１回、適合更新が実行されるが、これは待ち時間および相互依存性を最低限に抑えるためである。代替のコーデック実施は、各変換ブロック後などの、異なる間隔で適合を実行することができる。
【００５９】
このエンコーダおよびデコーダの例では、適合プロセス９００が値ｋを更新する。非ゼロの正規化係数の数が大きすぎる場合、この数が今後のブロックでドロップする傾向となるように、ｋが引き上げられる。非ゼロの正規化係数の数が小さすぎる場合、ビンサイズＮがより小さいため、今後のブロックがさらに多くの非ゼロ正規化係数を生成することになるという予測で、ｋは下げられる。この適合プロセス例は、値ｋが数のセット｛０，１，．．．１６｝内にあるように制約するが、代替の実施では、ｋに対して他の値領域を使用することができる。各適合更新で、エンコーダおよびデコーダは、ｋを増分する、減分する、またはそのままで変更しない。このエンコーダおよびデコーダの例は、ｋを１ずつ増分または減分するが、代替実施では他のステップサイズを使用することができる。
【００６０】
さらにこのエンコーダおよびデコーダの例における適合プロセス９００は、内部モデルパラメータまたは状態変数（Ｍ）を使用して、ヒステリシス効果でグループ化パラメータｋの更新を制御する。このモデルパラメータは、グループ化パラメータに急速な変動（ｆｌｕｃｔｕａｔｉｏｎ）を発生させないように、グループ化パラメータｋを更新するまでのラグを与える。適合プロセス例におけるこのモデルパラメータは、−８から８までの１７の整数ステップを有する。
【００６１】
次に図９を参照すると、適合プロセス９００の例は、以下のように進行する。さらにこの適合プロセス例については、図１０および１１の擬似コードリストでも詳細に説明する。アクション９１０、９９０で示されるように、このエンコーダおよびデコーダの例における適合プロセスは、輝度帯域およびクロミナンス帯域、ＡＣおよびＤＣ係数などを含む、圧縮ビットストリーム内に示されている各変換帯域上で、別々に実行される。代替コーデックは、変換帯域の数を変更することが可能であり、さらに適合を別々に、または変換帯域と接合的に、適用することもできる。
【００６２】
次に適合プロセスは、アクション９２０で、直前のエンコード／デコード済みマクロブロックにおける変換帯域の非ゼロの正規化係数の数をカウントする。アクション９３０で、この未処理カウントは、通常サイズ領域内の非ゼロ値係数の整数化された数を反映するように正規化される。次に適合プロセスは、所望のモデル（すなわち、非ゼロである係数の４分の１の「スイートスポット」）からのカウントの偏差を算出する（アクション９４０）。例えば図４に示されたエンコーダ例では、ＡＣ係数のマクロブロックは２４０の係数を有する。したがって、所望のモデルは、非ゼロとなる２４０の係数のうちの７０に関するものである。さらにこの偏差は、内部モデルパラメータを更新するために、スケーリング、しきい値化、および使用される。
【００６３】
次のアクション９６０、９６５、９７０、９７５で、適合プロセスは内部モデルパラメータにおける何らかの変更に従って、値ｋを適合させる。モデルパラメータが負のしきい値未満である場合、値ｋは（その許容範囲内で）減分される。この適合により、さらに多くの非ゼロ値係数が生成されるはずである。他方で、モデルパラメータが正のしきい値を超える場合、値ｋは（許容範囲内で）増分される。こうした適合により、より少ない非ゼロ値係数が生成されるはずである。それ以外の場合、値ｋは変更されないままとなる。
【００６４】
再度、アクション９１０、９８０に示されるように、適合プロセスは、クロミナンスチャネルおよび輝度チャネルについて別々に、などのように、データの各チャネルおよびサブ帯域について別々に繰り返される。
【００６５】
適合プロセス例９００については、図１０および１１に示される擬似コードリスト１０００でさらに詳細に説明する。
【００６６】
３．効率的なエントロピエンコーディング
【００６７】
３．１  従来技術の方法
様々なエンコーディング規格では、変換ブロックのコーディングプロセスは係数文字列のコーディングに縮小される。こうした文字列の一例が、変換係数例１２００として図１２に示される。この例１２００では、係数Ｃ０、Ｃ１、Ｃ２、Ｃ３、およびＣ４は（正または負のいずれかの符号の）４つの非ゼロ値係数値を表すが、この数列内のその他の係数はゼロの値を有する。
【００６８】
通常、こうした変換係数の文字列に対しては、以下のような一定のプロパティが当てはまる。
【００６９】
・  通常、係数の合計数は決定性があり、変換サイズによって与えられる。
【００７０】
・  確率論的に言えば、多数の係数がゼロである。
【００７１】
・  少なくとも１つの係数は非ゼロである。すべての係数がゼロの場合、通常、このケースは、Ｓｒｉｎｉｖａｓａｎによる２００５年８月１２日出願の米国特許出願（番号未定）、名称「Non-Zero Coefficient Block Pattern Coding」に記載されているような、コード化されたブロックパターンを介して信号送信される。
【００７２】
・  確率論的に言えば、非ゼロおよびより大きな値の係数は文字列の始めに発生し、ゼロおよびより小さな値の係数は終わりに向かって発生する。
【００７３】
・  非ゼロ値係数は、知られた最低／最高の整数値を取る。
【００７４】
様々なエンコーディング技法は、通常はかなり頻繁に発生するゼロ値係数が、ラン長さコードでコーディングできるという事実を利用する。しかしながら、エンコードされる入力イメージが高ダイナミックレンジデータ（例えば８ビットより大きい）の場合、または量子化パラメータが１または小さい場合、前述のように、ゼロの変換係数は少なくなる。こうした状況では、前述の適応コーディングおよびデコーディング技法を使用して、条件付けされたデータがこれらの特徴を有するように、データを条件付けすることができる。他の技法も、例えば高量子化レベルの設定などの他の手段によって、変換係数例１２００のセットと同様の変換係数セットを生成することができる。
【００７５】
図１２は、変換係数例１２００の方法などの、変換係数をエンコーディングする２つの方法も示す。これらの方法は、コーディングの利点をもたらすために、ゼロのランと連続する非ゼロ値係数とを一緒にコーディングすることを利用する。２Ｄコーディング例１２２０は、こうしたランレベルのエンコーディングスキームに関する一技法を実証する。例１２２０が示すように、２Ｄコーディングでは、ゼロ値係数のラン（長さゼロまたは正の長さのいずれかのラン）が、変換係数の数列内の後続の非ゼロ値係数と一緒にシンボル１２２５としてコーディングされ、例示されたケースでは、シンボル＜０，Ｃ０＞は非ゼロ値係数Ｃ０に先行するゼロがないことを示す。「ブロックの終わり」またはＥＯＢと呼ばれる特殊なシンボル１２３５は、ゼロの最後のランを信号送信するために使用される。これは通常、各シンボルが、ラン（ゼロ値係数のラン）およびレベル（非ゼロ系数値）を接合的にコーディングするため、２つの値を有することから、２Ｄコーディングと呼ばれ、２次元の変換係数データのエンコーディングと考えることができる。これらのシンボルは、ハフマンコードまたは算術コーディングを使用してエントロピエンコーディングし、図４の圧縮ビットストリーム４２０に送信することが可能である。
【００７６】
他の代替エンコーディングスキームは３Ｄコーディングであり、その例が例１２４０に示される。３Ｄコーディングでは、ゼロのランは、通常、２Ｄコーディングの場合と同様に後続の非ゼロ値係数と接合的にコーディングされる。さらに、この非ゼロ値係数がブロック内の最後の非ゼロ値係数であるかどうかを示す、ブールデータ要素「ｌａｓｔ」がエンコードされる。したがってシンボル１２４５は、ラン、レベル、およびｌａｓｔを接合的にエンコードし、例示されたケースでは、シンボル＜２，Ｃ１，ｎｏｔ  ｌａｓｔ＞は、非ゼロ値係数Ｃ１に２つのゼロが先行すること、およびこれは数列内の最後の非ゼロ値係数ではないことを示す。これら要素はそれぞれすべての値を自由に取ることができるため、シンボルは、「３Ｄコーディング」という名前につながる３つの独立した次元をエンコードする。
【００７７】
これら技法はそれぞれ別々の利点を有する。２Ｄコーディングは３Ｄコーディングよりも少ない情報を搬送するため、２Ｄコーディング技法の各シンボルは、３Ｄコーディングで使用されるシンボルよりも小さなエントロピを有する。したがって、所与の３Ｄコーディングスキーム内で可能なシンボル数は、比較に値する２Ｄコーディングスキームの場合の２倍となる。これによりコードテーブルサイズが大きくなり、３Ｄコーディングスキームに関するエンコーディングおよびデコーディングを低速化する可能性がある。しかしながら、２Ｄコーディングでは、ブロックの終わりを信号送信するために追加のシンボルが送信され、追加のシンボル全体を送信する必要があるということは、ビットストリームのサイズという観点からすると費用がかかることである。実際、３Ｄコーディングは実用上、コードテーブルサイズが大きいという点を除いて、２Ｄコーディングよりも効率的である。
【００７８】
３．２  ３１／２Ｄ〜２１／２Ｄコーディング
図１２に示された従来技法は、非ゼロ値係数レベルならびに先行するゼロランの接合コーディングを使用するが、非ゼロ値係数の後続のゼロランは、非ゼロ値係数の大きさとの強力な相関関係を示すことが実証可能である。この特性は、レベルおよび後続ランの接合的エンコーディングの有用性を示唆する。
【００７９】
図１３は、図１２で概説された２Ｄおよび３Ｄ技法を改良する、こうした代替エンコーディング技法を実証する。図１３は、変換係数の数列例１３００に関するシンボルを作成するために、後続ゼロランのコーディングの考え方を利用するコーディングスキームの例１３４０を示す。図１３は、係数が、非ゼロ値係数の値、ならびに、（存在する場合は）非ゼロ値係数に続くゼロランの長さを、＜ｌｅｖｅｌ，ｒｕｎ＞のペアとして含む、シンボル１３５５に接合的にコーディングされることを示す。
【００８０】
非ゼロ値係数と後続のゼロランとの間の強力な相関関係を利用することに加えて、この方法は、ある非ゼロ値係数がブロック内の最後の非ゼロ値係数である場合、その非ゼロ値係数が数列内の最後の１つであることを信号送信するために特別なランの値を使用することによって、さらなる利点をもたらす。したがって、シンボルの接合コーディングにおいて送信される情報は、レベル値、および、ゼロランの長さまたは「ｌａｓｔ」値のいずれかを示す他の値である。これは図１３で、レベル値と、ラン長さではなく「ｌａｓｔ」値とを含む、シンボル１３６５＜Ｃ４，ｌａｓｔ＞によって示される。これらの異なる状況はシンボル内の同じ場所にエンコードされ、ランおよび「ｌａｓｔ」は独立しておらず、シンボル当たり１つのみが送信される。したがって、シンボルの次元数は２でも３でもなく、むしろその間のどこかである。発明者等はこのエンコーディングを「２１／２Ｄコーディング」と呼ぶ。
【００８１】
この２１／２Ｄコーディングの機能は、レベルと後続のランとを組み合わせる接合コーディングスキームに必ずしも必要ではなく、代替の実施では、伝送される最終シンボルは、最終のゼロランの長さをエンコードするのみである可能性があり、これはコーディング済みビットストリームのサイズを大幅に増加させる可能性があるため望ましくない。他の代替実施では、２Ｄコーディングで使用されるようなＥＯＢシンボルが使用される可能性がある。しかしながら、３Ｄコーディングの場合のように、「ｌａｓｔ」値を使用する２１／２Ｄコーディングは、ブロックの終わりを示すために特別なシンボルをコーディングする必要がないという点で、２Ｄコーディングよりも有利である。加えて２１／２Ｄコーディングは、（１）２１／２Ｄコーディングの各シンボルのエントロピが３Ｄコーディングのそれよりも少ないという点、および（２）２１／２Ｄコーディングのコードテーブル設計が３Ｄコーディングのそれよりもシンプルであるという点、において、３Ｄコーディングよりも有利である。これらの利点はどちらも、２１／２Ｄコードの確率が３Ｄコードよりも少ないことの結果である。
【００８２】
しかしながら、２１／２Ｄコーディングだけでは、最初の非ゼロ値係数に先立ってラン長さを送信する方法を提供しないため、変換係数のラン全体を記述することができない。このため、図１３に示されるように特別なシンボル１３７５が使用され、これが最初のゼロランの長さをさらにエンコードする。これによって、最初のシンボルが、ｆｉｒｓｔ＿ｒｕｎ、ｌｅｖｅｌ、および（ｒｕｎ  ＯＲ  ｌａｓｔ）の接合コーディングとなる。図１３では、最初のシンボル１３７５＜０，Ｃ０，２＞は、第１のラン（ゼロである）、最初の非ゼロ値係数のレベル、および第２のラン（これは２であり、最初の非ゼロ値係数はブロック内の最後の非ゼロ値係数ではない）を送信する。このシンボルが追加の次元を含むため、これに関するエンコーディングは「３１／２Ｄコーディング」と呼ばれる。
【００８３】
３１／２Ｄコーディングにおける特別な情報は、一見したところ、２１／２Ｄコーディングの利点の一部を否定するものと思われる場合があるが、最初のシンボルのこの異なる処理は、コーディング効率の観点から見て実際は有利である。３１／２Ｄシンボルは、他の２１／２Ｄシンボルとは異なるアルファベットを必然的に有し、これは、他のシンボルとは別にエンコードされ、２１／２Ｄエントロピを増加させないことを意味する。
【００８４】
図１４は、２１／２Ｄ〜３１／２Ｄコーディングに従って変換係数をエンコードするための、エンコーダ４００（図４）によるプロセス例１４００を示す。一実施形態では、プロセス１４００は、正規化係数をエンコーディングするための図７のプロセス７２０の一部として含めることができる。他の実施形態では、プロセス１４００を使用して、従来の技法によって量子化された変換係数を量子化することができる。プロセス１４００の様々な実施形態では、アクションの除去、組合せ、またはサブアクションへの分割が可能である。
【００８５】
プロセスはアクション１４２０で開始され、ここで最初の非ゼロ変換係数が識別される。次に、アクション１４３０で、初めのゼロランの長さ（長さ０または正の長さのいずれかとすることができる）および最初の非ゼロ値係数を使用して、３１／２Ｄシンボルが作成される。この時点で、３１／２Ｄシンボルは完全ではない。次に、プロセスは意思決定アクション１４３５に進み、ここで、現在識別されている非ゼロ値係数が、変換係数の数列における最後の非ゼロ値係数であるかどうかが判別される。これが最後の非ゼロ値係数である場合、プロセスはアクション１４８０に進み、後続のゼロランではなく「ｌａｓｔ」インジケータがシンボルに挿入される。次にプロセスは、アクション１４９０で、エントロピエンコーディングを使用してシンボルをエンコードし、プロセスは終了する。こうしたシンボルのエンコーディングプロセスの一例は、図１６を参照しながら以下で説明する。
【００８６】
しかしながら意思決定アクション１４３５で、プロセスが、これが最後の非ゼロ値係数ではないと判別すると、アクション１４４０で、後続のゼロランの長さ（０または正の数のいずれかとすることができる）がシンボルに挿入され、このシンボルはアクション１４５０でエンコードされる。こうしたシンボルのエンコーディングプロセスの一例は、図１６を参照しながら以下で説明する。次にプロセスは、アクション１４６０で次の非ゼロ値係数を識別し、これは先行する非ゼロ値係数が最後でなかったために存在することが知られている。次にアクション１４７０で、この非ゼロ値係数を使用して２１／２Ｄシンボルが作成される。前述の３１／２Ｄシンボルと同様に、この時点で、このシンボルはまだ完全ではない。次に、意思決定アクション１４７５で、プロセスは、現在の非ゼロ値係数が数列内の最後であるかどうかを判別する。最後である場合、プロセスはアクション１４８０に進み、「ｌａｓｔ」インジケータが含められてシンボルがエンコードされる。最後でない場合、プロセスはアクション１４４０に戻り、次のゼロランが含められてシンボルがエンコードされ、プロセスは次の非ゼロ値係数で続行される。
【００８７】
３．３  コンテキスト情報
２１／２Ｄおよび３１／２Ｄコーディングに従ったシンボルのエンコーディングに加えて、いくつかの一時的な情報を使用して、エンコードされるシンボルに関するコンテキストを生成することができる。このコンテキストは、エンコーダ４００（図４）またはデコーダ５００（図５）によって使用され、シンボルをコーディングおよびデコーディングするためのエントロピコーディングテーブルの集合のうちの１つにインデックス付けすることができる。コンテキストの数が増加すると、各特定のコンテキスト向けに調整されたテーブルを適合または使用するための、コーデックの柔軟性が向上する。しかしながら、多数のコンテキストを定義することのマイナス面は、（１）コンテキストの希薄化（ｄｉｌｕｔｉｏｎ）が存在すること（各コンテキストは少数のシンボルのみに適用されるため、適合効率が低下する）、および（２）コードテーブルの増加が複雑さおよびメモリ要件の増加を意味すること、である。
【００８８】
これらの点を考えると、本明細書に記載されたコンテキストモデルは、各シンボルについてどのコンテキストが選択されるかを決定するための３つの要素を参考にするために選択される。一実施では、これらの要素は（１）変換が内部、中間、または外部のいずれの変換であるかという、変換のレベル、（２）係数が、輝度チャネルまたはクロミナンスチャネルのいずれの係数であるか、および（３）係数の数列内で、非ゼロ値係数のランに何らかのブレークが存在するかどうか、である。代替実施では、これらの要素のうちの１つまたは複数は、コーディングコンテキストの決定に使用されない場合がある、ならびに／あるいは、他の要素が考慮される場合がある。
【００８９】
したがって、（１）によれば、内部変換は中間変換とは異なるコードテーブルセットを使用し、中間変換は外部変換とは異なるコードテーブルセットを使用する。他の実施では、コンテキストモデルは、２つの変換レベルしか区別することができない。同様に（２）によれば、輝度係数は、クロミナンス係数とは異なるコードテーブルセットを使用する。これらのコンテキスト要素はどちらも、所与の変換係数セット内では変更されない。
【００９０】
しかしながら、要素（３）は、変換係数セット内で変更される。図１５は、このコンテキスト切り替えをより良く示す、３つの変換係数数列の例を示す。３つすべての数列１５００、１５２０、および１５４０では、非ゼロ値係数が文字ごとに示される。
【００９１】
３つすべての例が示すように、ブロック内の最初のシンボルは３１／２Ｄシンボルであり、そのアルファベットが他のシンボルと異なるため、必然的に他のシンボルとは異なるテーブルでコーディングされる。これは、最初のシンボルに関する「自然な」コンテキストを形成する。したがって、３つすべての例の最初の非ゼロ値係数である係数Ａは、３１／２Ｄコードでコーディングされる。加えて、３１／２Ｄシンボルは、最初の非ゼロ値係数の先行および後続のゼロランをエンコードするため、例１５２０の最初の２つの係数（Ａ，０）および例１５４０の最初の２つの係数（０，Ａ）は、３１／２Ｄシンボル内で接合的にコーディングされる。このため一実施では、要素（３）は、３１／２Ｄシンボルのコンテキストを決定するために適用されない。
【００９２】
これに対して、２１／２Ｄシンボルは、要素（３）に応じて異なるようにエンコードされる。したがって例１５００では、係数Ｄの後まで非ゼロ値係数のラン内にいかなるブレークもないことから、係数Ｂ、Ｃ、およびＤ（ならびにＤに続くゼロ）は、第１のコンテキストモデルでエンコードされることがわかる。しかしながら、Ｄの後のゼロは、非ゼロ値係数のラン内にブレークを構築する。したがって、残りの係数Ｅ、Ｆ、Ｇ、Ｈ、（およびいかなる後続も）．．．は、第２のコンテキストモデルでコーディングされる。これは、Ａ以外の各非ゼロ値係数は２１／２Ｄシンボルでエンコードされるが、係数Ｂ、Ｃ、およびＤ（および関連するいかなるゼロ値のランも）に対しては、係数Ｅ、Ｆ、Ｇ、およびＨに対して使用されるものとは異なるコードテーブルが使用されることを意味する。
【００９３】
これに対して、例１５２０では、ＡとＢの間にブレークがある。これにより、非ゼロ値係数のラン内にブレークが構築されるため、係数Ｂとそれに続くすべての非ゼロ値係数は第２のコンテキストモデルでエンコードされる。同様に、例１５４０では、Ａの前にブレークがある。したがって、例１５２０の場合のように、係数Ｂ、Ｃ、Ｄ、．．．は第２のコンテキストモデルでコーディングされる。
【００９４】
図１６は、エンコーダ４００（図４）によってシンボルをエンコードするためのプロセス例１６００を示す。一実施では、プロセス１６００は、プロセス１４００（図１４）のアクション１４５０および１４９０のプロセスを実行する。プロセス１６００の様々な実施において、アクションの除去、組合せ、およびサブアクションへの分割が可能である。プロセスは意思決定アクション１６０５で開始され、ここでエンコーダは、シンボルが３１／２Ｄシンボルであるかどうかを判別する。３１／２Ｄシンボルである場合、プロセスはアクション１６１０に進み、ここでシンボルは３１／２Ｄテーブルを使用してエンコードされ、プロセスは終了する。様々な実施において、シンボルは、ハフマンコーディングまたは算術コーディングなどのエントロピエンコーディングを使用してエンコードすることができる。別法として、他のコーディングスキームを使用することもできる。
【００９５】
シンボルが３１／２Ｄシンボルでない場合、プロセスは意思決定アクション１６１５に進み、ここでエンコーダは、シンボル内で接合的にコーディングされた非ゼロ値係数に、少なくとも１つのゼロが先行するかどうかを判別する。先行していない場合、プロセスはアクション１６２０に進み、シンボルは第１のコンテキストモデルからの２１／２Ｄコードテーブルを使用してエンコードされ、プロセスは終了する。ブレークがある場合、アクション１６３０で、シンボルは第２のコンテキストモデルからの２１／２Ｄコードテーブルを使用してエンコードされ、プロセスは終了する。
【００９６】
３．４  コードテーブルサイズの縮小
前述の技法は従来の技法を超える効率性を生み出すが、依然として、単独ではコードテーブルサイズを大幅に縮小することはできない。この技法に対して作成されるコードテーブルは、２１／２Ｄシンボルに対する（ｍａｘ＿ｌｅｖｅｌ×（ｍａｘ＿ｒｕｎ＋２））と、３１／２Ｄシンボルに対する（ｍａｘ＿ｌｅｖｅｌ×（ｍａｘ＿ｒｕｎ＋１）×（ｍａｘ＿ｒｕｎ＋２））のすべての組合せを伝送できるものとし、この式でｍａｘ＿ｌｅｖｅｌは非ゼロ値係数の最大（絶対）値であり、ｍａｘ＿ｒｕｎはゼロランの可能な最大長さである。合計（ｍａｘ＿ｒｕｎ＋１）の場合、ゼロランに対する可能な値が０からｍａｘ＿ｒｕｎまでであるため、値（ｍａｘ＿ｒｕｎ＋１）は３１／２Ｄシンボルの初めのランについて導出される。同様に、各シンボルは、合計（ｍａｘ＿ｒｕｎ＋２）値の場合、０からｍａｘ＿ｒｕｎまでの長さの後続のゼロランならびに「ｌａｓｔ」シンボルをエンコードする。たとえエスケープコーディング（稀にしか発生しないシンボルが、エスケープコードを介して信号発信される１つまたは複数のメタシンボルと一緒にグループ化される）を使用しても、コードテーブルサイズは膨大な可能性がある。
【００９７】
コードテーブルサイズを縮小するために、前述の技法をさらに調整することができる。第１に、各ランおよび各レベルが以下のようにシンボルペアに分割される。
【００９８】
ｒｕｎ    ＝ｎｏｎＺｅｒｏ＿ｒｕｎ（＋ｒｕｎ１）
ｌｅｖｅｌ＝ｎｏｎＯｎｅ＿ｌｅｖｅｌ（＋ｌｅｖｅｌ１）
このシンボルペアでは、シンボルｎｏｎＺｅｒｏ＿ｒｕｎおよびｎｏｎＯｎｅ＿ｌｅｖｅｌのそれぞれが、ランがゼロより大きいかどうか、および絶対レベルが１より大きいかどうかを示す、ブール値である。値ｒｕｎ１およびｌｅｖｅｌ１は、ブール値が真である場合にのみ使用され、ラン（１とｍａｘ＿ｒｕｎの間）およびレベル（２とｍａｘ＿ｌｅｖｅｌの間）を示す。しかしながら「ｌａｓｔ」のケースもコーディングしなければならないため、接合的にコーディングされたシンボル内の任意の後続のゼロランの値（ｒｕｎ  ＯＲ  ｌａｓｔ）が、３項シンボルのｎｏｎＺｅｒｏ＿ｒｕｎ＿ｌａｓｔとして送信され、これは、ランがゼロ長を有する場合は値０、ランが非ゼロ長を有する場合は１、およびシンボルの非ゼロ値係数が数列の最後である場合は２を取る。
【００９９】
したがって、この縮小されたエンコーディングを利用するために、最初の３１／２Ｄシンボルは＜ｎｏｎＺｅｒｏ＿ｒｕｎ，ｎｏｎＯｎｅ＿ｌｅｖｅｌ，ｎｏｎＺｅｒｏ＿ｒｕｎ＿ｌａｓｔ＞の形を取る。これによって、２×２×３＝１２のサイズのアルファベットが作成される。後続の２１／２Ｄシンボルは、＜ｎｏｎＯｎｅ＿ｌｅｖｅｌ，ｎｏｎＺｅｒｏ＿ｒｕｎ＿ｌａｓｔ＞の形を取り、２×３＝６のサイズのアルファベットを作成する。一実施では、これらのシンボルは「Ｉｎｄｅｘ」と呼ばれる。いくつかの実施では、ｒｕｎ１はＮｏｎｚｅｒｏＲｕｎとも呼ばれ、ｌｅｖｅｌ１はＳｉｇｎｉｆｉｃａｎｔＬｅｖｅｌと呼ばれる。
【０１００】
Ｉｎｄｅｘはレベルおよびランが有意であるかどうかに関する情報のみを含むため、デコーダが一連の変換係数を正確に再作成できるようにするためには、追加の情報をシンボルと共に送信することが必要な可能性がある。したがって、インデックスからの各シンボル後に、レベルが有意レベルである場合、レベルの値は別々にエンコードされ、シンボル後に送信される。同様に、シンボルが、ゼロランが非ゼロ（正）長さであることを示す場合、その長さは別々にエンコードされ、シンボル後に送信される。
【０１０１】
図１７は、変換係数の絶対値の数列例１７００を示す、縮小された３１／２Ｄ〜２１／２Ｄコーディング１７４０の例を示す。変換係数の符号は他の場所にエンコードすることができる。図１７が示すように、係数の数列例１７００は「５，０，０」で始まる。上記で示されたような非縮小３１／２Ｄ〜２１／２Ｄでは、最初のシンボルは次に＜０，５，２＞となる。しかしながら、縮小されたコーディングでは、図１７はＩｎｄｅｘからの最初のシンボル１７４５、＜０，１，１＞を示す。このシンボルは、最初の非ゼロ値係数の前にゼロがないこと、最初の非ゼロ値係数が１より大きい絶対値を有すること、およびこの非ゼロ値係数の後に少なくとも１つのゼロがあることを示す。このシンボルの後には、非ゼロ値係数の絶対値が５であることを示すＳｉｇｎｉｆｉｃａｎｔＬｅｖｅｌ値の「ｌｅｖｅｌ＿５」（１７５５）と、係数の後に２つのゼロが続くことを示すＮｏｎｚｅｒｏＲｕｎ値「ｒｕｎ＿２」（１７６５）とが続く。これに対して、後にゼロが続かない絶対値１の非ゼロ値係数を示すシンボル１７７５、＜０，０＞は、情報を提供するためのこれに続く他の値を必要としない。
【０１０２】
いくつかのシンボルはその後に追加情報を送信する必要があるため、Ｉｎｄｅｘからのシンボルを分析して、それらと共に追加情報を送信するべきであるかどうかを判別しなければならない。図１８は、３１／２Ｄ  Ｉｎｄｅｘシンボルに何の情報が含まれているかを特定するため、および、適切であれば追加の情報を送信するための、エンコーダ４００（図４）によるプロセス例１８００を示す。プロセス１８００の様々な実施では、アクションの除去、組合せ、またはサブアクションへの分割が可能である。図１８に関するシンボルの説明では、値「ｘ」は、シンボルのその特定部分に関する任意の可能な値を表す、プレースホルダ（ｐｌａｃｅｈｏｌｄｅｒ）である。プロセスはアクション１８１０から開始され、ここで最初のエンコード済みシンボルが送信される。次に意思決定アクション１８２０で、エンコーダは、シンボルが＜ｘ，１，ｘ＞の形であるかどうかを判別する。これは、シンボルによって表される非ゼロ値係数が１より大きい絶対値を有するかどうかを問い合わせることと等価である。エンコーダがこのケースに当てはまるものと判別した場合、非ゼロ値係数の値がエンコードされ、アクション１８３０で送信される。図１８は、非ゼロ値係数の符号のコーディングについて明示的に考察していないが、この符号はプロセス１８００内のいくつかのポイントで含めることが可能であることに留意されたい。様々な実施では、これには、接合コーディングされたシンボルの直後に、接合コーディングシンボルの内部で、および／またはレベルの絶対値と共に、符号を送信することが含まれる。
【０１０３】
アクション１８２０での判別結果にかかわらず、意思決定１８４０では、エンコーダが、シンボルが＜１，ｘ，ｘ＞の形であるかどうかを判別する。この判別は、シンボルによって表された非ゼロ値係数がいずれかの先行ゼロを有するかどうかを問い合わせることと等価である。先行ゼロを有する場合、アクション１８５０で、エンコーダは非ゼロ値係数に先行するゼロランの長さをエンコードし、この値を送信する。
【０１０４】
次に意思決定アクション１８６０で、エンコーダは、シンボルが＜ｘ，ｘ，ｔ＞である場合のｔの値を考慮する。この意思決定は、このシンボルによって表される非ゼロ値係数が、それに続く何らかのゼロを有するかどうかを問い合わせることと等価である。ｔ＝０の場合、エンコーダには後続のゼロがないことがわかり、アクション１８８０でさらにシンボルを送信して、プロセス１８００は終了する。一実施では、図１９のプロセス１９００が次のシンボルに関して開始される。ｔ＝１の場合、エンコーダは、アクション１８７０で、非ゼロ値係数の後に続くゼロランの長さをエンコードして送信し、その後アクション１８８０でシンボルの送信を続行して、プロセス１８００は終了する。しかしながら、ｔ＝２の場合、エンコーダには、シンボルによって表される非ゼロ値係数が数列内の最後（および唯一）であることがわかり、変換係数で表されるブロックは完了する。このようにしてプロセス１８００は終了し、適切であれば、次のブロックを変換およびエンコードすることができる。
【０１０５】
図１９は、２１／２Ｄ  Ｉｎｄｅｘシンボルに何の情報が含まれているかを特定するため、および、適切であれば追加の情報を送信するための、エンコーダ４００（図４）によるプロセス例１９００を示す。プロセス１９００の様々な実施では、アクションの除去、組合せ、またはサブアクションへの分割が可能である。図１８の場合と同じく図１９では、値「ｘ」は、シンボルのその特定部分に関する任意の可能な値を表す、プレースホルダである。プロセスはアクション１９１０から開始され、ここで次のエンコード済みシンボルが送信される。次に意思決定アクション１９２０で、エンコーダは、シンボルが＜１，ｘ＞の形であるかどうかを判別する。これは、シンボルによって表される非ゼロ値係数が１より大きい絶対値を有するかどうかを問い合わせることと等価である。エンコーダがこのケースに当てはまるものと判別した場合、非ゼロ値係数の値がエンコードされ、アクション１９３０で送信される。プロセス１８００の場合と同様に、図１９は、非ゼロ値係数の符号のコーディングについて明示的に考察していないが、この符号はプロセス１９００内のいくつかのポイントで含めることが可能であることに留意されたい。
【０１０６】
次に意思決定アクション１９４０で、エンコーダは、シンボルが＜ｘ，ｔ＞である場合のｔの値を考慮する。この意思決定は、このシンボルによって表される非ゼロ値係数が、それに続く何らかのゼロを有するかどうかを問い合わせることと等価である。ｔ＝０の場合、エンコーダには後続のゼロがないことがわかり、アクション１９６０でさらにシンボルを送信して、プロセス１９００は終了する。一実施では、図１９のプロセス１９００は次のシンボルに関して反復される。ｔ＝１の場合、エンコーダは、アクション１９５０で、非ゼロ値係数の後に続くゼロランの長さをエンコードして送信し、その後アクション１９６０でシンボルの送信を続行して、プロセス１９００は終了する。しかしながら、ｔ＝２の場合、エンコーダには、シンボルによって表される非ゼロ値係数が数列内の最後であることがわかり、変換係数で表されるブロックは完了する。このようにしてプロセス１９００は終了し、適切であれば、次のブロックを変換およびエンコードすることができる。
【０１０７】
３．５  追加の効率性
前述のコードテーブルサイズの縮小に加えて、ランおよびレベルのシンボルを分析することの利点の１つは、３１／２Ｄ接合シンボルの伝送に続いて、デコーダが、ブロック内に何らかの先行ゼロが存在するか否かを判別できることである。これは、第１または第２のコンテキストモデルが保持するかどうかを記述するコンテキスト情報がデコーダ側で認識されており、最初の非ゼロ値係数のｌｅｖｅｌ１値をエンコードするための有効なコンテキストを構築することを意味する。これは、たとえ接合的にコーディングされたＩｎｄｅｘシンボルが異なるアルファベットを使用する場合であっても、２１／２Ｄシンボルのｌｅｖｅｌ１値に適用されるコンテキストが、３１／２Ｄシンボルのｌｅｖｅｌ１値にも等しく適用可能であることを意味する。
【０１０８】
さらに、ブロック内の変換係数の合計数は一定であるため、各連続ランは単調に減少するシーケンスによって境界が画される。好ましい実施では、この情報はラン値のエンコーディングで活用される。例えばコードテーブルは、係数セットの前半で開始されるランに関するラン値コードのセットと、後半で開始されるランに関する異なるセットとを含むことができる。後半で開始されるいかなる可能なランの長さも、前半で開始されるランの可能な長さより必然的に短いことから、第２のコードセットは同じように大きくならず、エントロピは減少し、コーディング性能は向上する。
【０１０９】
係数の配置を注意深く観察することによって、他の情報を集めることができる。例えば、シンボルによって表される非ゼロ値係数が係数の数列内の最後に発生する場合、「ｌａｓｔ」は常に真である。同様に、シンボルによって表される非ゼロ値係数が配列内の最後から２番目に発生する場合、「ｌａｓｔ」が真であるかまたは後続ランがゼロであるかのいずれかである。これらそれぞれの観察によって、より短いテーブルによるコーディングが可能となる。
【０１１０】
３．６  インデックス実施例
第１のＩｎｄｅｘのアルファベットサイズは１２である。一実施では、このシンボルについて５つのハフマンテーブルが使用可能であり、これはＦｉｒｓｔＩｎｄｅｘ＝ａ＋２ｂ＋４ｃと定義され、この式でシンボルは＜ａ，ｂ，ｃ＞であり、ａおよびｂは０または１、ｃは値０、１、または２を取ることができる。各テーブルの１２のシンボルに関するコードワード長さの一実施を、以下に示す。一実施では、以下の接頭辞コードワードセットを導出するために、標準のハフマンコード構造プロシージャが適用可能である。
【０１１１】
テーブル１：５，６，７，７，５，３，５，１，５，４，５，３
テーブル２：４，５，６，６，４，３，５，２，３，３，５，３
テーブル３：２，３，７，７，５，３，７，３，３，３，７，４
テーブル４：３，２，７，５，５，３，７，３，５，３，６，３
テーブル５：３，１，７，４，７，３，８，４，７，４，８，５
後続のＩｎｄｅｘシンボルのアルファベットサイズは６である。一実施では、Ｉｎｄｅｘ＝ａ＋２ｂとして定義され、この式でシンボルは＜ａ，ｂ＞であり、ａはブール値であって、ｂは０、１、または２の値を取ることができる。Ｉｎｄｅｘについて、以下のように４つのハフマンテーブルが定義される。
【０１１２】
テーブル１：１，５，３，５，２，４
テーブル２：２，４，２，４，２，３
テーブル３：４，４，２，２，２，３
テーブル４：５，５，２，１，４，３
【０１１３】
加えて、一実施では、前述の第３．５項で説明された情報の一部を利用するために、係数が最後の配列位置にある場合、１ビットコード（ａによって定義される）が使用される（この場合、ｂは独自に２である）。一実施では、係数が最後から２番目の位置にある場合、ｂ≠１であることがわかっているため、２ビットコードが使用される。
【０１１４】
ＳｉｇｎｉｆｉｃａｎｔＬｅｖｅｌの一実施では、レベルの範囲を７つのビンに省略（ｃｏｌｌａｐｓｅ）するビンプロシージャを使用して、レベルをコーディングする。ビン内のレベルは固定長コードを使用してコーディングされ、ビン自体はハフマンコードを使用してコーディングされる。これは、一実施では、前述のグループ化技法を介して実行可能である。同様に一実施では、ＮｏｎｚｅｒｏＲｕｎは、現在のシンボルの場所に基づいて５つのビンにインデックス付けするビンプロシージャを使用してコーディングされる。
【０１１５】
３．７  ３１／２Ｄ〜２１／２Ｄシンボルのデコーディング
図２０は、一連のシンボルを変換係数にデコードするための、デコーダ５００（図５）によるプロセス例２０００を示す。プロセス２０００の様々な実施では、アクションの除去、組合せ、またはサブアクションへの分割が可能である。さらにアクションは、ビットストリームの破損によってトリガされるようなエラー状況を処理するために定義することができる。プロセスはアクション２０１０で開始され、ここでデコーダは最初の接合的にコーディングされたシンボルを受け取り、３１／２Ｄコードテーブルを使用してこれをデコードする。次にアクション２０２０で、変換係数は、デコード済みシンボル（同じく圧縮ビットストリーム内に存在する任意のレベルまたはランの情報を含む）に基づいて読み込まれる。このアクションの一実施については、図２１に関して以下でより詳細に説明する。次にこのプロセスは、意思決定アクション２０３０へと続き、ここでデコーダは、シンボルが最後の非ゼロ値係数に関するものであることをシンボルが表示するかどうかを判別する。これに関するものである場合、プロセスはアクション２０９０へと続き、ここで残りの未読み込み係数があればこれがゼロと共に読み込まれ、プロセス２０００は終了する。
【０１１６】
シンボルが最後の非ゼロ値係数に関するものでない場合、プロセスは意思決定アクション２０４０へと続き、ここでデコーダは、これまでに何らかのゼロ係数が何らかのシンボルによって表示されているかどうかを判別する。表示されていない場合、プロセスはアクション２０５０へと続き、ここで第１のコンテキストモデルに続く２１／２Ｄコードテーブルを使用して、次のシンボルが受け取られ、デコードされる。これに代わって、意思決定アクション２０４０でゼロ係数が表示されている場合、プロセス２０６０で、第２のコンテキストモデルに続く２１／２Ｄコードテーブルを使用して、次のシンボルが受け取られ、デコードされる。どのコンテキストモデルが使用されたかにかかわらず、プロセスはアクション２０７０へと続き、ここで変換係数はデコード済みシンボル（同じく圧縮ビットストリーム内に存在する任意のレベルまたはランの情報を含む）に基づいて読み込まれる。アクション２０２０の場合と同様に、このアクションの一実施については、図２１に関して以下でより詳細に説明する。次にこのプロセスは、意思決定アクション２０８０へと続き、ここでデコーダは、シンボルが最後の非ゼロ値係数に関するものであることをシンボルが表示するかどうかを判別する。これに関するものでない場合、プロセスは意思決定アクション２０４０に戻り、反復される。これに関するものである場合、プロセスはアクション２０９０へと続き、ここで残りの未読み込み係数があればこれがゼロと共に読み込まれ、プロセス２０００は終了する。
【０１１７】
図２１は、変換係数を読み込むためのデコーダ５００（図５）によるプロセス例２１００を示す。プロセス２１００の様々な実施では、アクションの除去、組合せ、またはサブアクションへの分割が可能である。プロセス２１００は、前述の第３．４項の技法に従ってエンコードされたシンボルをデコードするように構成されるが、代替の実施では、レベル値およびラン長さを２１／２Ｄシンボルおよび３１／２Ｄシンボルに含めることが可能であり、これによってプロセス２１００を簡略化することができる。このプロセスは意思決定アクション２１１０で開始され、ここでデコーダは、シンボルが３１／２Ｄシンボルであるかどうかを判別する。３１／２Ｄシンボルでない場合、プロセスは意思決定アクション２１４０へとジャンプし、これについては以下で説明する。しかしながらシンボルが３１／２Ｄシンボルである場合、デコーダは意思決定アクション２１２０で、シンボルがゼロ係数の正の長さの初めのランを示すかどうかを判別する。これは、３１／２Ｄシンボル内のｎｏｎＺｅｒｏ＿ｒｕｎの値が、正の長さのランを示す１、またはゼロ長さのランを示す０であるかどうかの判別によって実行可能である。シンボルが、ゼロ係数の正の長さのランを示す場合、プロセスはアクション２１３０へと続き、３１／２Ｄシンボルに続くエンコード済みｌｅｖｅｌ１に基づいてランの長さがデコードされ、ラン長さに従って初めの変換係数がゼロと共に読み込まれる。
【０１１８】
次に、プロセスは意思決定アクション２１４０へと続き、ここでデコーダは、シンボルが、その非ゼロ値係数が１より大きい絶対値を有することを示すかどうかを判別する。これは、シンボル内のｎｏｎＯｎｅ＿ｌｅｖｅｌの値が、レベルが１より大きい絶対値を有することを示す１、あるいは非ゼロ値係数が−１または１のいずれかであることを示す０、であるかどうかを判別することによって実行される。シンボルが１より大きい絶対値を伴う係数を示さない場合、プロセスはアクション２１５０へと続き、ここで非ゼロ値係数の符号に応じて−１または１のいずれかと共に次の係数が読み込まれる。シンボルが１より大きい絶対値を伴う係数を示す場合、これに代わってプロセスはアクション２１６０へと続き、ここで係数のレベルがデコードされ、係数はレベル値ならびにその符号と共に読み込まれる。前述のように、符号は様々な方法で示すことが可能であるため、アクション２１５０または２１６０では、係数符号のデコーディングについて明示的に考察しない。
【０１１９】
次に、意思決定アクション２１７０で、デコーダは、シンボルがゼロ係数の正の長さの後続ランを示すかどうかを判別する。これは、シンボル内のｎｏｎＺｅｒｏ＿ｒｕｎ＿ｌａｓｔの値が、正の長さのランを示す１、またはゼロ長さのランを示す０、であるかどうかを判別することによって実行可能である。（２に等しいｎｏｎＺｅｒｏ＿ｒｕｎ＿ｌａｓｔのケースは、プロセス２０００で理解されているため、示さない。）シンボルがゼロ係数の正の長さのランを示す場合、プロセスはアクション２１８０へと続き、ここで、シンボルに続くエンコード済みのｒｕｎ１に基づいてランの長さがデコードされ、後続の変換係数がラン長さに従ってゼロと共に読み込まれ、プロセス２１００は終了する。
【０１２０】
４．コンピューティング環境
前述のエンコーダ４００（図４）およびデコーダ５００（図５）ならびに変換係数を効率良くエンコードおよびデコードするための技法は、とりわけ、コンピュータ、イメージおよびビデオの記録、送信、および受信機器、ポータブルビデオプレーヤ、ビデオ会議、その他の諸例を含む、デジタル媒体信号処理が実行される様々なデバイスのいずれかで実行可能である。デジタル媒体コーディング技法は、図２２に示されるようなコンピュータまたは他のコンピューティング環境内で実行される、ハードウェア回路ならびにデジタル媒体処理ソフトウェアで、実施可能である。
【０１２１】
図２２は、説明された諸実施形態が実施可能な、好適なコンピューティング環境（２２００）の一般化された例を示す。本発明は、多様な汎用または特定用途向けのコンピューティング環境で実施可能であるため、コンピューティング環境（２２００）は、本発明の用途または機能の範囲に関していかなる制限をも示唆することを意図しない。
【０１２２】
図２２を参照すると、コンピューティング環境（２２００）は、少なくとも１つの処理ユニット（２２１０）およびメモリ（２２２０）を含む。図２２では、この最も基本的な構成（２２３０）は破線内に含まれる。処理ユニット（２２１０）はコンピュータ実行可能命令を実行し、実プロセッサまたは仮想プロセッサとすることができる。多重処理システムでは、処理パワーを増加させるために多重処理ユニットがコンピュータ実行可能命令を実行する。メモリ（２２２０）は、揮発性メモリ（例えばレジスタ、キャッシュ、ＲＡＭ）、不揮発性メモリ（例えばＲＯＭ、ＥＥＰＲＯＭ、フラッシュメモリなど）、またはこの２つの何らかの組合せとすることができる。メモリ（２２２０）は、前述のエンコーダ／デコーダ、および効率的な変換係数のエンコーディング／デコーディング技法を実施する、ソフトウェア（１２８０）を格納する。
【０１２３】
コンピューティング環境は追加の機能を有することができる。例えば、コンピューティング環境（２２００）は、ストレージ（２２４０）、１つまたは複数の入力デバイス（２２５０）、１つまたは複数の出力デバイス（２２６０）、および１つまたは複数の通信接続（２２７０）を含む。バス、コントローラ、またはネットワークなどの相互接続メカニズム（図示せず）は、コンピューティング環境（２２００）の諸構成要素を相互接続する。通常、オペレーティングシステムソフトウェア（図示せず）は、コンピューティング環境（２２００）内で実行する他のソフトウェアに動作環境を提供し、コンピューティング環境（２２００）の諸構成要素のアクティビティを調整する。
【０１２４】
ストレージ（２２４０）は取り外し可能または取り外し不能とすることが可能であり、磁気ディスク、磁気テープまたはカセット、ＣＤ−ＲＯＭ、ＣＤ−ＲＷ、ＤＶＤ、または、情報の格納に使用可能であり、コンピューティング環境（２２００）内でアクセス可能な、任意の他の媒体を含む。ストレージ（２２４０）は、前述のエンコーダ／デコーダ、および効率的な変換係数のエンコーディング／デコーディング技法を実施する、ソフトウェア（２２８０）を格納する。
【０１２５】
入力デバイス（２２５０）は、キーボード、マウス、ペン、またはトラックボールなどのタッチ入力デバイス、音声入力デバイス、スキャンデバイス、あるいは、コンピューティング環境（２２００）に入力を提供する他のデバイスとすることができる。オーディオの場合、入力デバイス（２２５０）はサウンドカード、またはアナログ形式またはデジタル形式のオーディオ入力を受け入れる同様のデバイス、あるいは、コンピューティング環境のオーディオサンプルを提供するＣＤ−ＲＯＭリーダとすることができる。出力デバイス（２２６０）は、ディスプレイ、プリンタ、スピーカ、ＣＤライタ、またはコンピューティング環境（２２００）からの出力を提供する他のデバイスとすることができる。
【０１２６】
通信接続（２２７０）は、通信媒体を介した他のコンピューティングエンティティへの通信を可能にする。通信媒体は、コンピュータ実行可能命令などの情報、圧縮済みオーディオまたはビデオ情報、あるいは変調データ信号内の他のデータを、搬送する。変調データ信号とは、信号内の情報をエンコードした方法と同様の方法でその特徴のうちの１つまたは複数が設定または変更された信号である。例を挙げると、通信媒体は、電気、光、ＲＦ、赤外線、音波、または他の搬送波で実施される有線または無線の技法を含むが、これらに限定されるものではない。
【０１２７】
本明細書のデジタル媒体処理技法は、コンピュータ読み取り可能媒体の一般的なコンテキストで説明することができる。コンピュータ読み取り可能媒体は、コンピューティング環境内でアクセス可能な任意の使用可能媒体である。例を挙げると、コンピューティング環境（２２００）では、コンピュータ読み取り可能媒体は、メモリ（２２２０）、ストレージ（２２４０）、通信媒体、および上記のいずれかの組合せを含むが、これらに限定されるものではない。
【０１２８】
本明細書のデジタル媒体処理技法は、プログラムモジュールに含まれ、ターゲットの実または仮想プロセッサ上のコンピューティング環境内で実行中などの、コンピュータ実行可能命令の一般的なコンテキストで説明することができる。一般にプログラムモジュールは、特定のタスクを実行するかまたは特定の抽象データ型を実施する、ルーチン、プログラム、ライブラリ、オブジェクト、クラス、構成要素、データ構造などを含む。プログラムモジュールの機能は、様々な実施形態において、プログラムモジュール間で所望の通りに組み合わせるかまたは分割することができる。プログラムモジュールに関するコンピュータ実行可能命令は、ローカルまたは分散型のコンピューティング環境内で実行することができる。
【０１２９】
提示のために、詳細な説明では、「決定」、「生成」、「調整」、および「適用」などの用語を使用して、コンピューティング環境におけるコンピュータの動作を説明する。これらの用語はコンピュータによって実行される動作に関する高水準抽象概念であり、人間が実行する動作と混同されるべきではない。これらの用語に対応する実際のコンピュータ動作は、実施に応じて変化する。
【０１３０】
本明細書で説明される主題の多くの可能な変形において、発明者等は、こうしたすべての実施形態が添付の特許請求の範囲およびその等価物の範囲内にあるものとして、本発明を主張する。
【図面の簡単な説明】
【０１３１】
【図１】従来技術における、従来のブロック変換ベースのコーデックを示すブロック図である。
【図２】ワイドダイナミックレンジを有する変換係数の分布を示すヒストグラムである。
【図３】ナローレンジ係数の分布を示すヒストグラムである。
【図４】ワイドレンジ係数の適応コーディングを組み込んだ代表的なエンコーダを示す流れ図である。
【図５】適応的にコーディングされたワイドレンジ係数のデコーディングを組み込んだ代表的なデコーダを示す流れ図である。
【図６】図４のエンコーダの場合などの、ワイドレンジ係数の適応コーディングにおける変換係数のグループ化およびレイヤ化を示す流れ図である。
【図７】ビン内での変換係数の選択されたグループ化のために変換係数をエンコードするための、図４のエンコーダによるプロセスを示す流れ図である。
【図８】図７のプロセスを介してエンコードされた変換係数を再構築するための、図５のデコーダによるプロセスを示す流れ図である。
【図９】係数のエントロピコーディングに関するより最適な分布を生成するための、図６におけるグループ化を適応的に変更するための適合プロセスを示す流れ図である。
【図１０】図９の適合プロセスの擬似コードを列挙した図である。
【図１１】図９の適合プロセスの擬似コードを列挙した図である。
【図１２】従来技術におけるエンコードされた変換係数の例を示す図である。
【図１３】本明細書に記載のエンコーディング技法に従ってエンコードされた、変換係数の一例を示す図である。
【図１４】変換係数をエンコードするための図４のエンコーダによるプロセスを示す流れ図である。
【図１５】本明細書に記載の技法に従って変換係数をエンコードするために使用される、様々なコードテーブルコンテキストの例を示す流れ図である。
【図１６】変換係数をエンコードする際に使用されることになるコーディングコンテキストを決定するための、図４のエンコーダによるプロセスを示す流れ図である。
【図１７】本明細書に記載された技法に従ってエンコードされる変換係数を減少させる例を示す図である。
【図１８】初めの変換係数を減少した形でエンコードおよび送信するための、図４のエンコーダによるプロセスを示す流れ図である。
【図１９】後続の係数を減少した形でエンコードおよび送信するための、図４のエンコーダによるプロセスを示す流れ図である。
【図２０】エンコードされた変換係数をデコードするための、図５のデコーダによるプロセスを示す流れ図である。
【図２１】デコードされたシンボルから変換係数を読み込むための、図５のデコーダによるプロセスを示す流れ図である。
【図２２】図６のワイドレンジ係数の適応コーディングを実施するために好適なコンピューティング環境を示すブロック図である。
【図１】
2009505494.tif 000005
【図２】
2009505494.tif 000006
【図３】
2009505494.tif 000007
【図４】
2009505494.tif 000008
【図５】
2009505494.tif 000009
【図６】
2009505494.tif 000010
【図７】
2009505494.tif 000011
【図８】
2009505494.tif 000012
【図９】
2009505494.tif 000013
【図１０】
2009505494.tif 000014
【図１１】
2009505494.tif 000015
【図１２】
2009505494.tif 000016
【図１３】
2009505494.tif 000017
【図１４】
2009505494.tif 000018
【図１５】
2009505494.tif 000019
【図１６】
2009505494.tif 000020
【図１７】
2009505494.tif 000021
【図１８】
2009505494.tif 000022
【図１９】
2009505494.tif 000023
【図２０】
2009505494.tif 000024
【図２１】
2009505494.tif 000025
【図２２】
2009505494.tif 000026
【国際調査報告】
2009505494.tif 000027