係数の位置をコード化する方法及び装置
【課題】係数のようなデータの位置をコード化し、又、デコードする方法及び装置を提供する。
【解決手段】ツリーデータ構造を使用して特定された、データがゼロであるか又は非ゼロであるかの指標に基づいて、データのベクトル中のデータをコード化するデータコード化ステップと、コード化されたデータに基づいてビットストリームを生成するビットストリーム生成ステップとを備える符号化を行い、そのようにして生成されたビットストリームを受信し復号を行う。
【解決手段】ツリーデータ構造を使用して特定された、データがゼロであるか又は非ゼロであるかの指標に基づいて、データのベクトル中のデータをコード化するデータコード化ステップと、コード化されたデータに基づいてビットストリームを生成するビットストリーム生成ステップとを備える符号化を行い、そのようにして生成されたビットストリームを受信し復号を行う。
【発明の詳細な説明】
【技術分野】
【0001】
[0001]本特許文献の開示の一部は著作権保護の対象となる素材を含んでいる。著作権所有者は、特許商標局における特許ファイル又は記録物において明白であるので、何人による特許文献又は特許情報開示の複製にも異議を唱えないが、それ以外は、いかなるものであれ全ての著作権を留保する。
[優先権]
[0002]本特許出願は、発明の名称が“Method and Apparatus for Coding Positions of Non−zero Coefficients in a Block”である、2004年12月22日に出願された、対応する仮特許出願第60/639,430号に基づく優先権を主張する。
【0002】
[0003]本発明は、コード化の分野に関し、より詳しくは、本発明は、グループ(例えば、係数のブロック)内のある種の係数(例えば、非ゼロ係数)のコード化に関係する。
【背景技術】
【0003】
[0004]データ圧縮は、大量のデータを蓄積及び伝送するための非常に有用なツールである。例えば、文書のネットワーク伝送のような画像を伝送するために要する時間は、画像を再現するために必要とされるビット数を減少させるため圧縮が使用されたとき、大幅に短縮される。
【0004】
[0005]多種多様なデータ圧縮技術が従来技術に存在している。圧縮技術は、損失のあるコード化と損失のないコード化の2つに大別される。損失のあるコード化は、元データの完全な再構成の保証がないほどに、情報の損失を生じるコード化を含む。損失のある圧縮の目標は、元データへの変更が、異議の余地なしに、又は、検出できないように行われる。損失のない圧縮では、全ての情報が保持され、完全な再構成を可能にするようにデータは圧縮される。
【0005】
[0006]画像符号化器及びビデオ符号化器において、画像は典型的にブロックの組に区分化される。各ブロックは係数の集合に変換され量子化される。係数は、変換(例えば、離散コサイン変換(DCT)、ウェーブレット変換)をデータに適用することにより作成できる。例えば、JPEGでは、DCT変換は、係数を作成するため画像データに適用される。その後、これらの係数は量子化されてもよい。ブロック毎に、どの係数が非ゼロ値を有するかを記述する情報が伝送されなければならない。
【0006】
[0007]量子化された係数は、典型的に値の1次元配列に配置される。配列中の係数の順序は、走査順序によって、例えば、ジグザグ走査順序によって決定される。非ゼロ係数の位置は、その後に、ランレングス符号化法を使用してコード化される。
【0007】
[0008]走査方法は、多くの場合に効率が制限されている。例えば、ジグザグ走査方法に関して、ブロックが水平周波数だけ又は垂直周波数だけを収容するとき、多数のゼロ係数がジグザグパターンに沿って訪問され、効率が悪いという結果になる。
【発明の概要】
【0008】
係数のようなデータの位置をコード化する方法及び装置が記載されている。一実施形態では、方法は、ツリーデータ構造を使用して特定された、データがゼロであるか又は非ゼロであるかの指標に基づいて、データのベクトル中のデータをコード化するデータコード化ステップと、コード化されたデータに基づいてビットストリームを作成するビットストリーム作成ステップとを備える。
【0009】
[0009]本発明は、後述される詳細な説明と、本発明を特定の実施形態に制限するように解釈されるべきでなく、説明と理解のためだけに用いられる本発明の種々の実施形態の添付図面とから、より十分に理解される。
【図面の簡単な説明】
【0010】
【図1A】データを符号化するプロセスの一実施形態のフローチャートである。
【図1B】データを復号化するプロセスの一実施形態のフローチャートである。
【図2】エンコーダ及びデコーダのシステムの一実施形態のブロック図である。
【図3】変換エンコーダの一実施形態のブロック図である。
【図4】ツリー構造データの例である。
【図5】係数エンコーダの一実施形態のブロック図である。
【図6】係数エンコーダによって実行される符号化プロセスの一実施形態のフローチャートである。
【図7】値をツリーのノードに割り当てるプロセスの一実施形態のフローチャートである。
【図8】ツリー中のノードを符号化するプロセスの一実施形態のフローチャートである。
【図9】子ノードの値を符号化するプロセスの一実施形態のフローチャートである。
【図10】子ノードの値を符号化するプロセスの別の実施形態のフローチャートである。
【図11】変換デコーダの一実施形態のブロック図である。
【図12】係数デコーダの一実施形態のブロック図である。
【図13】量子化された係数を復号化するプロセスの一実施形態のフローチャートである。
【図14】ノードを復号化するプロセスの一実施形態のフローチャートである。
【図15】子ノードの値を復号化するプロセスの一実施形態のフローチャートである。
【図16】子ノードの値を復号化するプロセスの代替的な実施形態のフローチャートである。
【図17】図4のツリー構造の表現の例を説明する図である。
【図18】量子化された係数を復号化するプロセスの一実施形態のフローチャートである。
【図19】係数デコーダの一実施形態のブロック図である。
【図20】コンピュータシステムの一実施形態のブロック図である。
【発明を実施するための形態】
【0011】
[0031]データのグループ(例えば、データのブロック)内の係数(例えば、非ゼロ係数)の位置をコード化する方法及び装置について記載されている。一実施形態では、係数は二分木に配置される。ツリーは節(ノード)を系統的に一つ残らず一回ずつなぞられ(以下、トラバースされ)、非ゼロ係数の位置をコード化する。本発明の実施形態は、伝統的なジグザグ走査を使用する係数のコード化への代替案を提供し、ツリー内での係数の体系化に依存し、それによって、単一の走査より高い柔軟性及び良い効率を提供する。
【0012】
[0032]後に続く実施形態は係数を用いて動作するものとして記載されているが、本明細書に記載された技術が任意のデータのベクトルに適用されることは当業者に明白であろう。
【0013】
[0033]以下の記載では、本発明のより徹底的な説明を行うために様々な詳細が示されている。しかし、本発明が、これらの特定の詳細を用いることなく実施されてもよいことは当業者にとって明白であろう。他の例では、よく知られている構成及び機器は、本発明を不明瞭化することを避けるために、詳細にではなく、ブロック図形式で示されている。
【0014】
[0034]後述する詳細な説明の一部は、コンピュータメモリ内のデータビットに関する演算のアルゴリズム及び記号的表現という点で提示されている。これらのアルゴリズム的な記述及び表現は、データ処理技術の当業者によって、自分の業績の内容をその技術における他の当業者へ最も効率的に伝達するために使用される手段である。アルゴリズムは、ここでは、一般的に、望ましい結果をもたらすステップの首尾一貫したシーケンスであると考えられる。ステップは物理量の物理的操作を必要とするステップである。通常、不可欠ではないが、これらの量は、記憶、転送、合成、比較及びそれ以外の操作がなされ得る、電気的又は磁気的信号の形式をとる。主として慣用上の理由で、これらの信号を、ビット、値、要素、記号、文字、項、数などと呼ぶことが、時として好都合であることがわかった。
【0015】
[0035]しかし、上記の用語及び類似した用語の全ては、適切な物理量と関連付けられるべきであり、これらの量に当てはめられた便宜的なラベルに過ぎないことに留意されたい。以下の説明から明白であるように、特に断らない限り、説明の全体を通じて、「処理」又は「コンピューティング」又は「計算」又は「決定」又は「表示」などのような用語を利用する説明は、コンピュータシステムのレジスタ及びメモリ内で物理(電子)量として表現されたデータを、コンピュータシステムメモリ若しくはレジスタ内、又は、その他のこのような情報記憶装置、伝送機器若しくは表示機器内で同じように物理量として表現されたその他のデータへ操作、変換する、コンピュータシステム又は類似した電子コンピューティング機器の作用及びプロセスを指すことが認められる。
【0016】
[0036]本発明は、本明細書に記載された演算を実行する装置にも関係する。この装置は、要求された目的のため特に構成されるか、又は、コンピュータに格納されたコンピュータプログラムによって選択的に作動若しくは再構成される汎用コンピュータを備えてもよい。このようなコンピュータプログラムは、限定されることはないが、例えば、フロッピー(登録商標)ディスク、光ディスク、CD−ROM、及び、磁気光ディスクを含む任意のタイプのディスク、リードオンリーメモリ(ROM)、ランダムアクセスメモリ(RAM)、EPROM、EEPROM、磁気若しくは光カード、又は、電子命令を格納するのに適当であり、それぞれコンピュータシステムバスに接続されている任意のタイプの媒体のような、コンピュータ読み取り可能な記憶媒体に格納されてもよい。
【0017】
[0037]本明細書に提示されているアルゴリズム及びディスプレイは、本質的に特定のコンピュータ又はその他の装置に関連していない。種々の汎用システムが本明細書における教示に従うプログラムと共に使用されてもよく、又は、要求された方法ステップを実行するためにより特化された装置を構築すると好都合であることがわかる。多種多様のこれらのシステムに要求される構成は以下の記載から明らかであろう。さらに、本発明は特定のプログラミング言語に関して記載されていない。多種多様のプログラミング言語が、本明細書に記載されているような発明の教示を実施するために使用されてもよいことが認められるであろう。
【0018】
[0038]機械読み取り可能な媒体は、機械(例えば、コンピュータ)によって読み取り可能な形式で情報を格納又は伝送する任意の仕組みを含む。例えば、機械読み取り可能な媒体は、リードオンリーメモリ(ROM)、ランダムアクセスメモリ(RAM)、磁気ディスク記憶媒体、光記憶媒体、フラッシュメモリデバイス、電気的、光学的、音響的又はその他の形式の伝搬信号(例えば、搬送波、赤外線信号、デジタル信号など)などを含む。
【0019】
(概要)
[0039]図1Aはデータを符号化するプロセスの一実施形態のフローチャートである。プロセスは、ハードウェア(例えば、回路、専用ロジックなど)、(汎用コンピュータシステム又は専用機械上で動かされるような)ソフトウェア、又は、両方の組み合わせを備えてもよい、プロセッシングロジックによって実行される。プロセッシングはファームウェアによって実行されてもよい。
【0020】
[0040]図1Aを参照すると、プロセスは、プロセッシングロジックが、前に生成されたデータ構造を使用して特定された非ゼロ係数の位置の指標に基づいて、係数のグループ内の非ゼロ係数の位置をコード化することによって開始する(処理ブロック101)。一実施形態では、データ構造はツリーを表現する。ツリーは二分木でもよい。一実施形態では、係数のグループは係数のブロックを含む。
【0021】
[0041]次に、プロセッシングロジックはコード化された非ゼロ係数に基づいてビットストリームを生成する(処理ブロック102)。
【0022】
[0042]図1Bはデータを復号化するプロセスの一実施形態のフローチャートである。プロセスは、ハードウェア(例えば、回路、専用ロジックなど)、(汎用コンピュータシステム又は専用機械上で動かされるような)ソフトウェア、又は、両方の組み合わせを備えてもよい、プロセッシングロジックによって実行される。プロセッシングはファームウェアによって実行されてもよい。
【0023】
[0043]図1Bを参照すると、プロセスは、プロセッシングロジックがビットストリームを受信することによって開始する(処理ブロック111)。次に、プロセッシングロジックは、前に生成されたデータ構造によって特定された量子化された係数の位置の指標に基づいて、係数のグループ内の量子化された係数の位置を得るために前に生成されたデータ構造を使用することを含めて、量子化された係数の集合を生成するためにビットストリームを復号化する(処理ブロック112)。
【0024】
[0044]一実施形態では、データ構造表現はツリーである。ツリーは二分木でもよい。一実施形態では、係数のグループは係数のブロックを含む。
【0025】
[0045]図2はエンコーダ及びデコーダシステムの一実施形態のブロック図である。一部のシステムはエンコーダ又はデコーダだけを含んでもよい。
【0026】
[0046]図2を参照すると、エンコーダ202はソース画像201を、ソース画像201の圧縮表現であるビットストリーム203に変換する。デコーダ204は、ビットストリーム203を、再構成画像205に変換する。再構成画像205は、ソース画像201の近似(損失のある圧縮コンフィギュレーションにおける)又は(損失のない圧縮コンフィギュレーションにおける)正確な複製である。ビットストリーム203は、通信チャネル(例えば、インターネットなど)を介して、又は、物理的な媒体(例えば、CD−ROM)を介して、エンコーダ202からデコーダ203へ送信されてもよい。
【0027】
[0047]図3は、変換エンコーダの一実施形態のブロック図である。図3の変換エンコーダは、図2のエンコーダ202のコンポーネントでもよい。エンコーダは、ソース画像を1個以上の画像データのブロック、例えば、4×4又は8×8のサイズのブロックに区分化できる。その他の画像データのグループ分けが使用されてもよい。
【0028】
[0048]図3を参照すると、変換ユニット302は、画像データのブロック301を係数303の集合に変換する。一実施形態では、変換ユニット302は、離散コサイン変換(DCT)を実施できる。量子化器304は、係数303を量子化された係数305の集合に変換する。一実施形態では、係数は実数値をとり、量子化された係数305のうちの1個の値は整数に制限される。一実施形態では、量子化器304は、所定の数によって各係数を除算し、結果を最も近い整数に丸め、量子化された係数を生成する。係数エンコーダ306は、量子化された係数305をビットストリーム307に変換する。一実施形態では、ビットストリーム307は、量子化された係数305の表現を含むビットの順序付き集合である。一実施形態では、係数エンコーダ306はハフマン符号化を使用する。代替的に、係数エンコーダ306は、算術符号化を、単独で又はハフマン符号化と併せて使用する。その他のコード化スキームもまた同様に使用できる。
【0029】
[0049]本明細書における目的のため、ツリーを記述する用語は以下の通り使用される。図4は二分木の例である。図4を参照すると、ツリーは、5個のノードA、B、C、D及びEを収容している。ノードAはルートノードである。ノードD及びEは、本明細書では、Cの子ノードと呼ばれる。ノードDはリーフノードの例である。リーフノードは子ノードを所有しない。ノードB及びEもまたリーフノードである。
【0030】
[0050]以降の記載は二分木を考慮するが、二分木以外のツリー(例えば、三分木)も同様に使用される。
【0031】
[0051]図17は、ツリー構造データの例である。図17を参照すると、ツリー構造データは、ノードタイプデータ1701及びリーフインデックスデータ1702を収容してもよい。ノードタイプデータ1701は、図4の二分木のようなツリー中の各ノードのノードタイプを収容する。例えば、値0はリーフノードではないノードに対し使用されてもよく、値1はリーフノードであるノードに対し使用される。一実施形態では、ノードタイプの順序付けは、ツリーの深さ優先トラバースによって決定される。代替的に、幅優先トラバースが使用される。リーフインデックスデータ1702はツリー中のリーフ毎に係数インデックスを収容する。ツリーのリーフにおけるインデックスは、量子化された係数の配列へのインデックスを表現する。一実施形態では、リーフインデックスの順序付けは、ツリーの深さ優先トラバースによって決定できる。代替的に、幅優先トラバースが考慮される。図17の例では、図4に描かれたツリーが記述され、ノードBはインデックス0を、ノードDはインデックス2を、ノードEはインデックス1を有することを仮定している。
【0032】
[0052]図5は、係数エンコーダの一実施形態のブロック図である。図5を参照すると、ツリー生成器502は、量子化された係数501を受信し、メモリ510からツリー構造データ506を取り出す。ツリー構造データ506は、二分木を記述する。一実施形態では、ツリー構造データ506は、ツリーのトポロジーに関係する情報と、ならびに、ツリー中の各リーフのインデックスとを含む。ツリー生成器502は、値をツリーの各ノードに割り当てる。最初に、ツリー生成器502は、ツリーの各リーフに、対応する量子化された係数がゼロと一致するならば、ゼロ値を割り当てる。そうでなければ、ツリー生成器502は非ゼロ値をリーフに割り当てる。次に、値が、ツリー中のリーフではない各ノードに再帰的に割り当てられる。このようなノードはそれぞれが2個の子を保有する。両方の子が値ゼロを有するならば、ゼロ値がノードに割り当てられる。そうでなければ、ツリー生成器502は非ゼロ値をノードに割り当てる。ノードに値が割り当てられているツリー503は、エントロピーエンコーダ504へ送信される。
【0033】
[0053]エントロピーエンコーダ504は、ツリー生成器502からのツリー503と量子化された係数501とを受信する。エントロピーエンコーダ504は、メモリ510からツリー構造データ506をさらに受信する。エントロピーエンコーダ504は、さらに後述されるように、ツリー503のノードに割り当てられた値を符号化する。その後、非ゼロである量子化された係数毎に、エントロピーエンコーダ504は量子化された係数の値を符号化する。一実施形態では、ツリー及び係数の符号化は、ハフマン符号化を使用して実行される。別の実施形態では、算術符号化が使用されるが、どのようなコード化スキームが使用されてもよい。エントロピーエンコーダ504の出力は、コード化された情報を収容するビットストリーム505である。
【0034】
[0054]選択的に、エントロピーエンコーダ504は、メモリ510から取り出されたビットストリーム505にツリー構造データを挿入してもよい。一実施形態では、ツリー構造データは、符号化された形式のビットストリームと共に挿入される。ノードタイプ情報は、1ノード当たり1ビットずつで符号化されてもよく、ノードがリーフであるか否かを示す。リーフインデックスに関する情報は、ツリーのサイズに依存する多数のビットにより符号化されてもよい。例えば、3個のリーフインデックスを伴うツリーは、これらのインデックスを2ビットで符号化可能であり、16個のリーフインデックスを備えるツリーはこれらのインデックスを4ビットで符号化可能である。一般に、必要なビット数は、log2(リーフインデックスの個数)におおよそ等しい。ツリー構造データは様々な時点で送信されてもよい。例えば、代替的な実施形態では、ツリー構造データは、1ピクチャー毎に1回ずつ、ピクチャーのグループ毎に1回ずつ、又は、ビデオシーケンス全体について1回ずつ送信されてもよい。
【0035】
[0055]図6は、係数エンコーダによって実行される符号化プロセスの一実施形態のフローチャートである。プロセスは、ハードウェア(例えば、回路、専用ロジックなど)、(汎用コンピュータシステム又は専用機械上で動かされるような)ソフトウェア、又は、両方の組み合わせを備えてもよい、係数エンコーダのプロセッシングロジックによって実行される。プロセッシングロジックはファームウェアを備えてもよい。
【0036】
[0056]図6を参照すると、プロセスは、プロセッシングロジックが、例えば、量子化器から量子化された係数を受信することによって開始する(処理ブロック601)。プロセッシングロジックは、その後、係数の全部がゼロであるか否かをテストする(処理ブロック602)。全係数がゼロであるならば、フラグは全係数がゼロであることを示し、プロセスは終了する。そうでなければ、プロセッシングロジックは、ブロック中の少なくとも1個の係数がゼロに等しくないということを特定するフラグを符号化し(処理ブロック604)、メモリからツリー構造データを取り出し(処理ブロック605)、さらに後述されるように、量子化された係数に基づいてツリー内の各ノードに値を割り当てる(処理606)。換言すると、プロセッシングロジックはツリーノード値を生成する。
【0037】
[0057]ツリーノード値を生成した後、プロセッシングロジックは、さらに後述されるように、ツリー内の各ノードに割り当てられた値を符号化する(処理ブロック607)。ツリーを符号化した後、プロセッシングロジックは、非ゼロの量子化された係数の値を符号化する(処理ブロック608)。一実施形態では、ハフマン符号化が使用される。代替的に、算術符号化又は別のコード化スキームが使用されてもよい。
【0038】
[0058]図7は、ツリーのノードの値を割り当てるプロセスの一実施形態のフローチャートである。プロセスは、ハードウェア(例えば、回路、専用ロジックなど)、(汎用コンピュータシステム又は専用機械上で動かされるような)ソフトウェア、又は、両方の組み合わせを備えてもよい、プロセッシングロジックによって実行される。
【0039】
[0059]プロセスはルートノードに設定された現ノード(以下、カレントノード)で始まる。図7を参照すると、プロセッシングロジックは、カレントノードがリーフノードであるかどうかを判定する(処理ブロック701)。カレントノードがリーフノードであるならば、プロセッシングロジックは、カレントノードに関連付けられた量子化された係数がゼロ係数であるかどうかを判定する(処理ブロック702)。係数がゼロであるならば、プロセッシングロジックは0という値をカレントノードに割り当て(処理ブロック703)、プロセスは終了し、そうでなければ、プロセッシングロジックは1という値をカレントノードに割り当て(処理ブロック704)、プロセスは終了する。
【0040】
[0060]カレントノードがリーフノードでないならば、プロセスは処理ブロック710へ移り、プロセッシングロジックが、カレントノードの第1の子をカレントノードとして用いて図7のプロセスを再帰的に実行し(処理ブロック710)、その後、カレントノードの第2の子をカレントノードとして用いて再び図7のプロセスを再帰的に実行する(処理ブロック711)。
【0041】
[0061]その後、プロセッシングロジックは、両方の子ノードが0という値を割り当てられているかどうかを判定する(処理ブロック712)。両方の子ノードが0という値を保有するならば、プロセッシングロジックは0という値をカレントノードに割り当て(処理ブロック703)、プロセスは終了し、そうでなければ、プロセッシングロジックは1という値をカレントノードに割り当て(処理ブロック704)、プロセスは終了する。
【0042】
[0062]カレントノードがルートノードに設定されるプロセスが終了した後、ツリー中の全ノードは0又は1という値が割り当てられている。ルートノードは、1個以上の係数がゼロに等しくないならば、値1を保有する。
【0043】
[0063]図8は、ツリー中のノードを符号化するプロセスの一実施形態のフローチャートである。プロセスは、ハードウェア(例えば、回路、専用ロジックなど)、(汎用コンピュータシステム又は専用機械上で動かされるような)ソフトウェア、又は、両方の組み合わせを備えてもよい、プロセッシングロジックによって実行される。プロセッシングロジックはファームウェアを備えてもよい。
【0044】
[0064]図8を参照すると、プロセスは最初にルートノードを引数として用いて呼び出される。プロセスは、プロセッシングロジックがノードはリーフであるかどうかを判定することによって開始する(処理ブロック801)。ノードがリーフであるならば、プロセッシングロジックは、そのノードの対応する係数の値を符号化し(処理ブロック802)、プロセスは終了する。種々の符号化スキーム(例えば、ハフマン符号化、算術符号化など)が使用されてもよい。
【0045】
[0065]ノードがリーフでないならば、プロセッシングロジックはノードの2個の子の値を符号化する(処理ブロック803)。符号化はさらに後述されている。その後、プロセッシングロジックは第1の子が1という値を保有するかどうかをテストする(処理ブロック804)。第1の子が値1を保有するならば、処理ブロックは、第1の子を引数として用いてノード符号化プロセスを再帰的に実行する(処理ブロック806)。プロセッシングロジックは、その後、第2の子の値が1であるかどうかをテストする(処理ブロック807)。第1の子が値0を保有するか、又は、第2の子が値1を有するならば、プロセッシングロジックは、第2の子を引数として用いてノード符号化プロセスを再帰的に実行する(処理ブロック805)。その後、プロセスは終了する。
【0046】
[0066]図9は、子ノードの値を符号化するプロセスの一実施形態のフローチャートである。プロセスは、ハードウェア(例えば、回路、専用ロジックなど)、(汎用コンピュータシステム又は専用機械上で動かされるような)ソフトウェア、又は、両方の組み合わせを備えてもよい、プロセッシングロジックによって実行される。プロセッシングロジックはファームウェアを備えてもよい。
【0047】
[0067]図9を参照すると、プロセスは、プロセッシングロジックが第1の子の値を符号化することによって開始する(処理ブロック901)。一実施形態では、値はビットストリームに付加される単一ビットとして符号化される。代替的に、値は算術符号化器を使用してさらに圧縮される。
【0048】
[0068]プロセッシングロジックは、その後、第1の子の値が1であるかどうかを決定する(処理ブロック902)。第1の子の値が0に等しいならば、プロセスは終了する。そうでなければ、プロセッシングロジックは第2の子の値を符号化する(処理ブロック903)。一実施形態では、値はビットストリームに付加される単一ビットとして符号化される。代替的に、値は算術符号化器を使用してさらに圧縮される。第2の子の値を符号化した後、プロセスは終了する。
【0049】
[0069]図10は、子ノードの値を符号化するプロセスの別の実施形態のフローチャートである。これは図9に記載されたプロセスへの代替的な実施形態であることに留意されたい。代替的に、方法の選択はノードに基づいて行われてもよい。選択情報は、メモリに格納され、ビットストリームに符号化されてもよい。このような符号化は選択された方法を示すためにビットを使用して行われてもよい。代替的に、エンコーダ及びデコーダの両方が、ノード毎にどの方法を使用すべきであるかに関する所定の引数を保有してもよい。
【0050】
[0070]図10のプロセスは、ハードウェア(例えば、回路、専用ロジックなど)、(汎用コンピュータシステム又は専用機械上で動かされるような)ソフトウェア、又は、両方の組み合わせを備えてもよいプロセッシングロジックによって実行される。プロセッシングロジックはファームウェアを備えてもよい。
【0051】
[0071]図10を参照すると、プロセスは、プロセッシングロジックが2個の子ノードの結合された値を符号化することにより開始する(処理ブロック1001)。一実施形態では、結合された値は、両方の子の値の間の論理AND演算の結果によって決定される。プロセッシングロジックは、次に、両方の子が1という値を保有するかどうかを判定する(処理ブロック1003)。コード化された値が1であるならば、プロセスは終了する。そうでなければ、プロセッシングロジックは第1の子の値を符号化し(処理ブロック1004)、プロセスは終了する。一実施形態では、値を符号化するとき、値はビットストリームにそのままで付加される。代替的に、値は算術符号化器を使用してさらに圧縮されてもよい。
【0052】
[0072]代替的に、三つ組のアルファベットが子ノードの値を表現するために使用されてもよい。このような場合、単一記号がビットストリームに付加される。
【0053】
[0073]図11は、変換デコーダの一実施形態のブロック図である。図11を参照すると、ビットストリーム1120が係数デコーダ1110に入力されている。係数デコーダ1110は、ビットストリーム1120からのビットを量子化された係数1111の集合に変換する。変換プロセスはさらに後述されている。逆量子化器1101は、量子化された係数1111を係数1102の集合にスケール変換する。逆変換1103は、係数1102を再構成画像データ1104に変換する。
【0054】
[0074]図12は、係数デコーダの一実施形態のブロック図である。図12を参照すると、エントロピーデコーダ1202は、さらに後述されているように、ビットストリーム1201からのビットを量子化された係数1203の集合に変換する。このため、エントロピーデコーダ1202は、メモリ1210に格納されているツリー構造データに依存する。エントロピーデコーダ1202は、ビットストリーム1201からツリー構造データを読み、メモリ1210に格納してもよい。
【0055】
[0075]図13は、量子化された係数を復号化するプロセスの一実施形態のフローチャートである。プロセスは、ハードウェア(例えば、回路、専用ロジックなど)、(汎用コンピュータシステム又は専用機械上で動かされるような)ソフトウェア、又は、両方の組み合わせを備えてもよい、プロセッシングロジックによって実行される。プロセッシングロジックはファームウェアを備えてもよい。
【0056】
[0076]図13を参照すると、プロセスは、プロセッシングロジックが集合中の全係数をゼロに設定することによって開始する(処理ブロック1301)。係数をゼロに設定した後、プロセッシングロジックはフラグを復号化する(処理ブロック1302)。プロセッシングロジックは、その後、全係数がゼロであるかどうかを判定する(処理ブロック1303)。全係数がゼロであることを示す第1の値をフラグがとるならば、プロセスは終了する。そうでなければ、プロセッシングロジックは、さらに後述されるように、ツリー中のノード値を復号化し(処理ブロック1304)、同様に係数値を復号化する(処理ブロック1305)。その後、プロセスは終了する。
【0057】
[0077]図14は、ノードを復号化するプロセスの一実施形態のフローチャートである。プロセスは、ハードウェア(例えば、回路、専用ロジックなど)、(汎用コンピュータシステム又は専用機械上で動かされるような)ソフトウェア、又は、両方の組み合わせを備えてもよい、プロセッシングロジックによって実行される。プロセッシングロジックはファームウェアを備えてもよい。
【0058】
[0078]図14を参照すると、プロセスはルートノードを引数として用いて開始する。プロセッシングロジックはノードがリーフであるかどうかを判定する(処理ブロック1401)。ノードがリーフノードであるならば、プロセッシングロジックは係数の値をさらに復号化し(処理ブロック1402)、その後にプロセスが終了する。復号化は種々の復号化技術(例えば、ハフマン符号化、算術符号化など)を使用して実行されてもよい。
【0059】
[0079]ノードがリーフでないならば、プロセッシングロジックはそのノードの2個の子の値を復号化する(処理ブロック1403)。復号化はさらに後述されている。その後、プロセッシングロジックは、第1の子が1という値を保有するかどうかをテストする(処理ブロック1404)。第1の子が値1を保有するならば、処理ブロックは、第1の子を引数として用いてノード復号化プロセスを再帰的に実行する(処理ブロック1406)。プロセッシングロジックは、その後、第2の子が値1を保有するかどうかをテストする(処理ブロック1407)。第1の子が値0を保有するか、又は、第2の子が値1を保有するならば、プロセッシングロジックは、第2の子を引数として用いてノード復号化プロセスを再帰的に実行する(処理ブロック1405)。その後、プロセスは終了する。
【0060】
[0080]図15は、子ノードの値を復号化するプロセスの一実施形態のフローチャートである。プロセスは、ハードウェア(例えば、回路、専用ロジックなど)、(汎用コンピュータシステム又は専用機械上で動かされるような)ソフトウェア、又は、両方の組み合わせを備えてもよい、プロセッシングロジックによって実行される。プロセッシングロジックはファームウェアを備えてもよい。
【0061】
[0081]図15を参照すると、プロセスは第1の子の値を復号化することによって開始する(処理ブロック1501)。復号化プロセスは、ビットストリームから単一ビットを取り出すこと、又は、算術デコーダを用いてビットストリームからバイナリ記号を復号化することを伴ってもよい。プロセッシングロジックは、第1の子の値が1であるかどうかを判定する(処理ブロック1502)。復号化された値が0であるならば、プロセスは終了し、そうではなく、値が1であるならば、プロセッシングロジックは、第1の値と同様に、第2の子の値を復号化し(処理ブロック1503)、その後、プロセスは終了する。
【0062】
[0082]図16は、子ノードの値を復号化するプロセスの代替的な実施形態のフローチャートである。プロセスは、ハードウェア(例えば、回路、専用ロジックなど)、(汎用コンピュータシステム又は専用機械上で動かされるような)ソフトウェア、又は、両方の組み合わせを備えてもよい、プロセッシングロジックによって実行される。プロセッシングロジックはファームウェアを備えてもよい。
【0063】
[0083]図16を参照すると、プロセスは両方の子の結合された値を復号化して開始する(処理ブロック1601)。結合された値は、両方の子が値1を保有するかどうかを示すことができる。プロセッシングロジックは、両方の子が1という値を保有するかどうかを判定する(処理ブロック1602)。両方の子が1という値を保有するならば、プロセスは終了し、そうではなく、値が1であるならば、プロセッシングロジックは第1の子の値を復号化し、第2の子の値を反対の値に設定し(処理ブロック1603)、その後、プロセスは終了する。
【0064】
[0084]代替的に、両方の子の値は三つ組のアルファベットを用いて表現される。このような場合、単一記号が子ノードの値を取得するために復号化されてもよい。
【0065】
[0085]図18は量子化された係数を復号化するプロセスの一実施形態のフローチャートである。プロセスは、ハードウェア(例えば、回路、専用ロジックなど)、(汎用コンピュータシステム又は専用機械上で動かされるような)ソフトウェア、又は、両方の組み合わせを備えてもよい、プロセッシングロジックによって実行される。プロセッシングロジックはファームウェアを備えてもよい。
【0066】
[0086]図18を参照すると、プロセスは、プロセッシングロジックが状態を1に設定し、スタックを空状態に初期化することにより開始する(処理ブロック1801)。その後、プロセッシングロジックはメモリからノードタイプを取り出す(処理ブロック1802)。プロセッシングロジックは、その後、ノードがリーフノードであるかどうかを判定する(処理ブロック1803)。ノードタイプがリーフノードであることを示すならば、処理は処理ブロック1820へ移り、そうでなければ、処理は処理ブロック1810へ移る。
【0067】
[0087]処理ブロック1820において、プロセッシングロジックはメモリからリーフインデックスIを取り出し、状態が値0を有するかどうかをテストする(処理ブロック1821)。状態が値0を有するならば、処理は処理ブロック1823へ移り、プロセッシングロジックはインデックスIをもつ係数に値0を割り当て、その後、処理は処理ブロック1824へ移る。状態が値1を有するならば、処理は処理ブロック1822へ移り、プロセッシングロジックはビットストリームから係数値を復号化し、インデックスIをもつ係数に復号化された係数値を割り当て、その後、処理は処理ブロック1824へ移る。
【0068】
[0088]処理ブロック1824において、プロセッシングロジックは、スタックが空であるかどうかを判定する。スタックが空であるならば、プロセスは終了する。スタックが空でなければ、処理は処理ブロック1825へ移り、プロセッシングロジックはスタックから値をポップし、状態をその値に設定する。その後、処理は処理ブロック1802へ移る。
【0069】
[0089]ノードがリーフノードでないならば(処理ブロック1803)、プロセッシングロジックは状態が1に等しいかどうかを判定する(処理ブロック1810)。そうでなければ(すなわち、値が0であるならば)、プロセッシングロジックは2個のノードの値をゼロに設定し、処理ブロック1814へ移る。状態が1に等しければ、プロセッシングロジックはビットストリームから2個のノード値を復号化する(処理ブロック1812)。ノード値を復号化する方法の例は、図15及び16に記載されている。2個のノード値を復号化した後、プロセッシングロジックは状態を第1のノード値に設定し(処理ブロック1813)、処理ブロック1814へ移る。処理ブロック1814において、プロセッシングロジックは第2のノード値をスタックへプッシュする。その後、処理は処理ブロック1802へ移る。
【0070】
[0090]図19は、係数デコーダの一実施形態のブロック図である。図19を参照すると、係数デコーダは状態レジスタ1920を含む。一実施形態では、状態レジスタ1920は最初に値1に設定される。エントロピーデコーダ1902は、ノードタイプメモリ1923からノードタイプを取り出す。ノードタイプメモリ1923は、図4に記載されているように、ツリーの構造に関するデータを収容する。ノードタイプがリーフノードを示し、状態レジスタの値が1であるならば、エントロピーデコーダ1902はビットストリームから量子化された係数を復号化し、それを選択器1903へ送信する。選択器1903は、量子化された係数を選択し、それを係数メモリ1904へ送信する。係数メモリ1904へのインデックスは、リーフインデックスメモリ1921から取り出されたリーフインデックスによって決定される。そうではなく、状態レジスタ1920が0であるならば、選択器1903は値0を選択し、それを係数メモリ1904へ送信する。量子化された係数が量子化された係数メモリ1904に格納された後、値がスタック1922からポップされ、状態レジスタ1920に割り当てられる。そうでなく、ノードタイプがリーフノードを示さないならば、係数デコーダは以下の通り動作する。状態レジスタ1920が1であるならば、エントロピーデコーダ1902は、例えば、図15及び16に記載されているように、ビットストリーム1901から2個のノード値を復号化する。第1のノード値はエントロピーデコーダ1902によって状態レジスタ1920に割り当てられ、第2のノード値はエントロピーデコーダ1902によってスタック1922へプッシュされる。そうではなく、状態レジスタ1920が0であるならば、状態レジスタ1920の内容がスタックへプッシュされる。
【0071】
[0091]一実施形態では、デコーダは、量子化された係数メモリ内の全ての量子化された係数に値が割り当てられるまで、この方式で動作する。量子化された係数メモリの内容は、その後、量子化された係数の順序付き集合として出力される。
【0072】
[0092]上述のように、本明細書に記載された技術は任意のデータのベクトルに適用されてもよい。例えば、これらの技術は、前方向動きベクトルに対応する水平移動及び垂直移動と後方向動きベクトルに対応する水平移動及び垂直移動とを有するデータのブロックを含む次元4のベクトルをコード化するためにbフレームをビデオコード化するときに使用されてもよい。この場合、本明細書に記載された技術は、ゼロでない方を示すために使用されてもよい。
【0073】
(コードの例)
[0093]以下のサンプルCコードは、本発明に記載されているような係数を復号化するために使用できる。ツリーの深さ優先トラバース及び幅優先トラバースの例が提供されている。
【数1】
【数2】
【0074】
[0094]適切なツリー構造データは、係数ブロックの集合から導出できる。以下のサンプルCコードは、係数の各組み合わせが非ゼロであることを頻度を用いて示す統計量の集合からツリー構造データを構築する。
【数3】
【数4】
【数5】
【数6】
【数7】
【数8】
【0075】
(典型的なコンピュータシステム)
[0095]図20は、本明細書に記載された1個以上の演算を実行できる典型的なコンピュータシステムのブロック図である。コンピュータシステム2000は、典型的なクライアント又はサーバーコンピュータシステムを備えてもよい。コンピュータシステムに関して記述されたコンポーネントは、ハンドヘルド機器又はモバイル機器(例えば、携帯電話機)の一部であってもよい。
【0076】
[0096]図20を参照すると、コンピュータシステム2000は、情報を通信する通信メカニズム又はバス2011と、バス2011と接続され情報を処理するプロセッサ2012とを備える。プロセッサ2012は、マイクロプロセッサを含むが、例えば、Pentium(登録商標)プロセッサなどのようなマイクロプロセッサに限定されない。
【0077】
[0097]システム2000は、バス2011に接続され、情報とプロセッサ2012によって実行されるべき命令とを格納する、ランダムアクセスメモリ(RAM)又はその他のダイナミック記憶装置2004(メインメモリとして参照される)を、さらに備える。メインメモリ2004はまた、プロセッサ2012による命令の実行中に、一時変数又はその他の中間情報を格納するためにも使用できる。
【0078】
[0098]コンピュータシステム2000は、バス2011に接続され、スタティック情報及びプロセッサ2012のための命令を格納するリードオンリーメモリ(ROM)及び/又はその他のスタティック記憶装置2006と、磁気ディスク又は光ディスク、及び、それに対応するディスクドライブのようなデータ記憶装置2007とを、さらに備える。データ記憶装置2007は、バス2011に接続され、情報及び命令を格納する。
【0079】
[0099]コンピュータシステム2000は、バス2011に接続され、情報をコンピュータユーザへ表示する陰極線管(CRT)又は液晶ディスプレイ(LCD)のようなディスプレイ機器2021に、さらに接続されてもよい。英数字キー及びその他のキーを含む英数字入力機器2022は、同様にバス2011に接続され、情報及びコマンド選択をプロセッサ2012へ通信できる。付加的なユーザ入力機器は、カーソル制御機器2023である。このカーソル制御機器2023は、例えばマウス、トラックボール、トラックパッド、スタイラス、又は、カーソル方向キーである。カーソル制御機器2023は、方向情報及びコマンド選択をプロセッサ2012へ通信し、ディスプレイ2021上のカーソル移動を制御するために、バス2011に接続されている。
【0080】
[00100]バス2011に接続できる別の機器は、ハードコピー機器2024である。ハードコピー機器2024は、紙、フィルム、又は、類似したタイプの媒体のような媒体上に情報を残すために使用できる。バス2011に接続できる別の機器は、電話機又はハンドヘルドパーム機器へ通信するための有線/無線通信機能部2025である。
【0081】
[00101]システム2000のコンポーネント、及び、関連したハードウェアの何れか又は全部が本発明において使用できることに留意されたい。しかし、コンピュータシステムのその他の構成は、機器の一部又は全部を含んでもよいことが認められるであろう。
【0082】
[00102]以上の説明を読んだ後に、本発明の多数の代替及び変形が当業者に明白になることは確実であるが、説明のために図示され記載された特定の実施形態が制限的であるとみなされることは決して意図されていないことが理解されるべきである。したがって、種々の実施形態の詳細への言及は、本発明に不可欠であると考えられる構成要件だけをそれ自体に列挙する請求項の範囲を制限することを意図していない。
【技術分野】
【0001】
[0001]本特許文献の開示の一部は著作権保護の対象となる素材を含んでいる。著作権所有者は、特許商標局における特許ファイル又は記録物において明白であるので、何人による特許文献又は特許情報開示の複製にも異議を唱えないが、それ以外は、いかなるものであれ全ての著作権を留保する。
[優先権]
[0002]本特許出願は、発明の名称が“Method and Apparatus for Coding Positions of Non−zero Coefficients in a Block”である、2004年12月22日に出願された、対応する仮特許出願第60/639,430号に基づく優先権を主張する。
【0002】
[0003]本発明は、コード化の分野に関し、より詳しくは、本発明は、グループ(例えば、係数のブロック)内のある種の係数(例えば、非ゼロ係数)のコード化に関係する。
【背景技術】
【0003】
[0004]データ圧縮は、大量のデータを蓄積及び伝送するための非常に有用なツールである。例えば、文書のネットワーク伝送のような画像を伝送するために要する時間は、画像を再現するために必要とされるビット数を減少させるため圧縮が使用されたとき、大幅に短縮される。
【0004】
[0005]多種多様なデータ圧縮技術が従来技術に存在している。圧縮技術は、損失のあるコード化と損失のないコード化の2つに大別される。損失のあるコード化は、元データの完全な再構成の保証がないほどに、情報の損失を生じるコード化を含む。損失のある圧縮の目標は、元データへの変更が、異議の余地なしに、又は、検出できないように行われる。損失のない圧縮では、全ての情報が保持され、完全な再構成を可能にするようにデータは圧縮される。
【0005】
[0006]画像符号化器及びビデオ符号化器において、画像は典型的にブロックの組に区分化される。各ブロックは係数の集合に変換され量子化される。係数は、変換(例えば、離散コサイン変換(DCT)、ウェーブレット変換)をデータに適用することにより作成できる。例えば、JPEGでは、DCT変換は、係数を作成するため画像データに適用される。その後、これらの係数は量子化されてもよい。ブロック毎に、どの係数が非ゼロ値を有するかを記述する情報が伝送されなければならない。
【0006】
[0007]量子化された係数は、典型的に値の1次元配列に配置される。配列中の係数の順序は、走査順序によって、例えば、ジグザグ走査順序によって決定される。非ゼロ係数の位置は、その後に、ランレングス符号化法を使用してコード化される。
【0007】
[0008]走査方法は、多くの場合に効率が制限されている。例えば、ジグザグ走査方法に関して、ブロックが水平周波数だけ又は垂直周波数だけを収容するとき、多数のゼロ係数がジグザグパターンに沿って訪問され、効率が悪いという結果になる。
【発明の概要】
【0008】
係数のようなデータの位置をコード化する方法及び装置が記載されている。一実施形態では、方法は、ツリーデータ構造を使用して特定された、データがゼロであるか又は非ゼロであるかの指標に基づいて、データのベクトル中のデータをコード化するデータコード化ステップと、コード化されたデータに基づいてビットストリームを作成するビットストリーム作成ステップとを備える。
【0009】
[0009]本発明は、後述される詳細な説明と、本発明を特定の実施形態に制限するように解釈されるべきでなく、説明と理解のためだけに用いられる本発明の種々の実施形態の添付図面とから、より十分に理解される。
【図面の簡単な説明】
【0010】
【図1A】データを符号化するプロセスの一実施形態のフローチャートである。
【図1B】データを復号化するプロセスの一実施形態のフローチャートである。
【図2】エンコーダ及びデコーダのシステムの一実施形態のブロック図である。
【図3】変換エンコーダの一実施形態のブロック図である。
【図4】ツリー構造データの例である。
【図5】係数エンコーダの一実施形態のブロック図である。
【図6】係数エンコーダによって実行される符号化プロセスの一実施形態のフローチャートである。
【図7】値をツリーのノードに割り当てるプロセスの一実施形態のフローチャートである。
【図8】ツリー中のノードを符号化するプロセスの一実施形態のフローチャートである。
【図9】子ノードの値を符号化するプロセスの一実施形態のフローチャートである。
【図10】子ノードの値を符号化するプロセスの別の実施形態のフローチャートである。
【図11】変換デコーダの一実施形態のブロック図である。
【図12】係数デコーダの一実施形態のブロック図である。
【図13】量子化された係数を復号化するプロセスの一実施形態のフローチャートである。
【図14】ノードを復号化するプロセスの一実施形態のフローチャートである。
【図15】子ノードの値を復号化するプロセスの一実施形態のフローチャートである。
【図16】子ノードの値を復号化するプロセスの代替的な実施形態のフローチャートである。
【図17】図4のツリー構造の表現の例を説明する図である。
【図18】量子化された係数を復号化するプロセスの一実施形態のフローチャートである。
【図19】係数デコーダの一実施形態のブロック図である。
【図20】コンピュータシステムの一実施形態のブロック図である。
【発明を実施するための形態】
【0011】
[0031]データのグループ(例えば、データのブロック)内の係数(例えば、非ゼロ係数)の位置をコード化する方法及び装置について記載されている。一実施形態では、係数は二分木に配置される。ツリーは節(ノード)を系統的に一つ残らず一回ずつなぞられ(以下、トラバースされ)、非ゼロ係数の位置をコード化する。本発明の実施形態は、伝統的なジグザグ走査を使用する係数のコード化への代替案を提供し、ツリー内での係数の体系化に依存し、それによって、単一の走査より高い柔軟性及び良い効率を提供する。
【0012】
[0032]後に続く実施形態は係数を用いて動作するものとして記載されているが、本明細書に記載された技術が任意のデータのベクトルに適用されることは当業者に明白であろう。
【0013】
[0033]以下の記載では、本発明のより徹底的な説明を行うために様々な詳細が示されている。しかし、本発明が、これらの特定の詳細を用いることなく実施されてもよいことは当業者にとって明白であろう。他の例では、よく知られている構成及び機器は、本発明を不明瞭化することを避けるために、詳細にではなく、ブロック図形式で示されている。
【0014】
[0034]後述する詳細な説明の一部は、コンピュータメモリ内のデータビットに関する演算のアルゴリズム及び記号的表現という点で提示されている。これらのアルゴリズム的な記述及び表現は、データ処理技術の当業者によって、自分の業績の内容をその技術における他の当業者へ最も効率的に伝達するために使用される手段である。アルゴリズムは、ここでは、一般的に、望ましい結果をもたらすステップの首尾一貫したシーケンスであると考えられる。ステップは物理量の物理的操作を必要とするステップである。通常、不可欠ではないが、これらの量は、記憶、転送、合成、比較及びそれ以外の操作がなされ得る、電気的又は磁気的信号の形式をとる。主として慣用上の理由で、これらの信号を、ビット、値、要素、記号、文字、項、数などと呼ぶことが、時として好都合であることがわかった。
【0015】
[0035]しかし、上記の用語及び類似した用語の全ては、適切な物理量と関連付けられるべきであり、これらの量に当てはめられた便宜的なラベルに過ぎないことに留意されたい。以下の説明から明白であるように、特に断らない限り、説明の全体を通じて、「処理」又は「コンピューティング」又は「計算」又は「決定」又は「表示」などのような用語を利用する説明は、コンピュータシステムのレジスタ及びメモリ内で物理(電子)量として表現されたデータを、コンピュータシステムメモリ若しくはレジスタ内、又は、その他のこのような情報記憶装置、伝送機器若しくは表示機器内で同じように物理量として表現されたその他のデータへ操作、変換する、コンピュータシステム又は類似した電子コンピューティング機器の作用及びプロセスを指すことが認められる。
【0016】
[0036]本発明は、本明細書に記載された演算を実行する装置にも関係する。この装置は、要求された目的のため特に構成されるか、又は、コンピュータに格納されたコンピュータプログラムによって選択的に作動若しくは再構成される汎用コンピュータを備えてもよい。このようなコンピュータプログラムは、限定されることはないが、例えば、フロッピー(登録商標)ディスク、光ディスク、CD−ROM、及び、磁気光ディスクを含む任意のタイプのディスク、リードオンリーメモリ(ROM)、ランダムアクセスメモリ(RAM)、EPROM、EEPROM、磁気若しくは光カード、又は、電子命令を格納するのに適当であり、それぞれコンピュータシステムバスに接続されている任意のタイプの媒体のような、コンピュータ読み取り可能な記憶媒体に格納されてもよい。
【0017】
[0037]本明細書に提示されているアルゴリズム及びディスプレイは、本質的に特定のコンピュータ又はその他の装置に関連していない。種々の汎用システムが本明細書における教示に従うプログラムと共に使用されてもよく、又は、要求された方法ステップを実行するためにより特化された装置を構築すると好都合であることがわかる。多種多様のこれらのシステムに要求される構成は以下の記載から明らかであろう。さらに、本発明は特定のプログラミング言語に関して記載されていない。多種多様のプログラミング言語が、本明細書に記載されているような発明の教示を実施するために使用されてもよいことが認められるであろう。
【0018】
[0038]機械読み取り可能な媒体は、機械(例えば、コンピュータ)によって読み取り可能な形式で情報を格納又は伝送する任意の仕組みを含む。例えば、機械読み取り可能な媒体は、リードオンリーメモリ(ROM)、ランダムアクセスメモリ(RAM)、磁気ディスク記憶媒体、光記憶媒体、フラッシュメモリデバイス、電気的、光学的、音響的又はその他の形式の伝搬信号(例えば、搬送波、赤外線信号、デジタル信号など)などを含む。
【0019】
(概要)
[0039]図1Aはデータを符号化するプロセスの一実施形態のフローチャートである。プロセスは、ハードウェア(例えば、回路、専用ロジックなど)、(汎用コンピュータシステム又は専用機械上で動かされるような)ソフトウェア、又は、両方の組み合わせを備えてもよい、プロセッシングロジックによって実行される。プロセッシングはファームウェアによって実行されてもよい。
【0020】
[0040]図1Aを参照すると、プロセスは、プロセッシングロジックが、前に生成されたデータ構造を使用して特定された非ゼロ係数の位置の指標に基づいて、係数のグループ内の非ゼロ係数の位置をコード化することによって開始する(処理ブロック101)。一実施形態では、データ構造はツリーを表現する。ツリーは二分木でもよい。一実施形態では、係数のグループは係数のブロックを含む。
【0021】
[0041]次に、プロセッシングロジックはコード化された非ゼロ係数に基づいてビットストリームを生成する(処理ブロック102)。
【0022】
[0042]図1Bはデータを復号化するプロセスの一実施形態のフローチャートである。プロセスは、ハードウェア(例えば、回路、専用ロジックなど)、(汎用コンピュータシステム又は専用機械上で動かされるような)ソフトウェア、又は、両方の組み合わせを備えてもよい、プロセッシングロジックによって実行される。プロセッシングはファームウェアによって実行されてもよい。
【0023】
[0043]図1Bを参照すると、プロセスは、プロセッシングロジックがビットストリームを受信することによって開始する(処理ブロック111)。次に、プロセッシングロジックは、前に生成されたデータ構造によって特定された量子化された係数の位置の指標に基づいて、係数のグループ内の量子化された係数の位置を得るために前に生成されたデータ構造を使用することを含めて、量子化された係数の集合を生成するためにビットストリームを復号化する(処理ブロック112)。
【0024】
[0044]一実施形態では、データ構造表現はツリーである。ツリーは二分木でもよい。一実施形態では、係数のグループは係数のブロックを含む。
【0025】
[0045]図2はエンコーダ及びデコーダシステムの一実施形態のブロック図である。一部のシステムはエンコーダ又はデコーダだけを含んでもよい。
【0026】
[0046]図2を参照すると、エンコーダ202はソース画像201を、ソース画像201の圧縮表現であるビットストリーム203に変換する。デコーダ204は、ビットストリーム203を、再構成画像205に変換する。再構成画像205は、ソース画像201の近似(損失のある圧縮コンフィギュレーションにおける)又は(損失のない圧縮コンフィギュレーションにおける)正確な複製である。ビットストリーム203は、通信チャネル(例えば、インターネットなど)を介して、又は、物理的な媒体(例えば、CD−ROM)を介して、エンコーダ202からデコーダ203へ送信されてもよい。
【0027】
[0047]図3は、変換エンコーダの一実施形態のブロック図である。図3の変換エンコーダは、図2のエンコーダ202のコンポーネントでもよい。エンコーダは、ソース画像を1個以上の画像データのブロック、例えば、4×4又は8×8のサイズのブロックに区分化できる。その他の画像データのグループ分けが使用されてもよい。
【0028】
[0048]図3を参照すると、変換ユニット302は、画像データのブロック301を係数303の集合に変換する。一実施形態では、変換ユニット302は、離散コサイン変換(DCT)を実施できる。量子化器304は、係数303を量子化された係数305の集合に変換する。一実施形態では、係数は実数値をとり、量子化された係数305のうちの1個の値は整数に制限される。一実施形態では、量子化器304は、所定の数によって各係数を除算し、結果を最も近い整数に丸め、量子化された係数を生成する。係数エンコーダ306は、量子化された係数305をビットストリーム307に変換する。一実施形態では、ビットストリーム307は、量子化された係数305の表現を含むビットの順序付き集合である。一実施形態では、係数エンコーダ306はハフマン符号化を使用する。代替的に、係数エンコーダ306は、算術符号化を、単独で又はハフマン符号化と併せて使用する。その他のコード化スキームもまた同様に使用できる。
【0029】
[0049]本明細書における目的のため、ツリーを記述する用語は以下の通り使用される。図4は二分木の例である。図4を参照すると、ツリーは、5個のノードA、B、C、D及びEを収容している。ノードAはルートノードである。ノードD及びEは、本明細書では、Cの子ノードと呼ばれる。ノードDはリーフノードの例である。リーフノードは子ノードを所有しない。ノードB及びEもまたリーフノードである。
【0030】
[0050]以降の記載は二分木を考慮するが、二分木以外のツリー(例えば、三分木)も同様に使用される。
【0031】
[0051]図17は、ツリー構造データの例である。図17を参照すると、ツリー構造データは、ノードタイプデータ1701及びリーフインデックスデータ1702を収容してもよい。ノードタイプデータ1701は、図4の二分木のようなツリー中の各ノードのノードタイプを収容する。例えば、値0はリーフノードではないノードに対し使用されてもよく、値1はリーフノードであるノードに対し使用される。一実施形態では、ノードタイプの順序付けは、ツリーの深さ優先トラバースによって決定される。代替的に、幅優先トラバースが使用される。リーフインデックスデータ1702はツリー中のリーフ毎に係数インデックスを収容する。ツリーのリーフにおけるインデックスは、量子化された係数の配列へのインデックスを表現する。一実施形態では、リーフインデックスの順序付けは、ツリーの深さ優先トラバースによって決定できる。代替的に、幅優先トラバースが考慮される。図17の例では、図4に描かれたツリーが記述され、ノードBはインデックス0を、ノードDはインデックス2を、ノードEはインデックス1を有することを仮定している。
【0032】
[0052]図5は、係数エンコーダの一実施形態のブロック図である。図5を参照すると、ツリー生成器502は、量子化された係数501を受信し、メモリ510からツリー構造データ506を取り出す。ツリー構造データ506は、二分木を記述する。一実施形態では、ツリー構造データ506は、ツリーのトポロジーに関係する情報と、ならびに、ツリー中の各リーフのインデックスとを含む。ツリー生成器502は、値をツリーの各ノードに割り当てる。最初に、ツリー生成器502は、ツリーの各リーフに、対応する量子化された係数がゼロと一致するならば、ゼロ値を割り当てる。そうでなければ、ツリー生成器502は非ゼロ値をリーフに割り当てる。次に、値が、ツリー中のリーフではない各ノードに再帰的に割り当てられる。このようなノードはそれぞれが2個の子を保有する。両方の子が値ゼロを有するならば、ゼロ値がノードに割り当てられる。そうでなければ、ツリー生成器502は非ゼロ値をノードに割り当てる。ノードに値が割り当てられているツリー503は、エントロピーエンコーダ504へ送信される。
【0033】
[0053]エントロピーエンコーダ504は、ツリー生成器502からのツリー503と量子化された係数501とを受信する。エントロピーエンコーダ504は、メモリ510からツリー構造データ506をさらに受信する。エントロピーエンコーダ504は、さらに後述されるように、ツリー503のノードに割り当てられた値を符号化する。その後、非ゼロである量子化された係数毎に、エントロピーエンコーダ504は量子化された係数の値を符号化する。一実施形態では、ツリー及び係数の符号化は、ハフマン符号化を使用して実行される。別の実施形態では、算術符号化が使用されるが、どのようなコード化スキームが使用されてもよい。エントロピーエンコーダ504の出力は、コード化された情報を収容するビットストリーム505である。
【0034】
[0054]選択的に、エントロピーエンコーダ504は、メモリ510から取り出されたビットストリーム505にツリー構造データを挿入してもよい。一実施形態では、ツリー構造データは、符号化された形式のビットストリームと共に挿入される。ノードタイプ情報は、1ノード当たり1ビットずつで符号化されてもよく、ノードがリーフであるか否かを示す。リーフインデックスに関する情報は、ツリーのサイズに依存する多数のビットにより符号化されてもよい。例えば、3個のリーフインデックスを伴うツリーは、これらのインデックスを2ビットで符号化可能であり、16個のリーフインデックスを備えるツリーはこれらのインデックスを4ビットで符号化可能である。一般に、必要なビット数は、log2(リーフインデックスの個数)におおよそ等しい。ツリー構造データは様々な時点で送信されてもよい。例えば、代替的な実施形態では、ツリー構造データは、1ピクチャー毎に1回ずつ、ピクチャーのグループ毎に1回ずつ、又は、ビデオシーケンス全体について1回ずつ送信されてもよい。
【0035】
[0055]図6は、係数エンコーダによって実行される符号化プロセスの一実施形態のフローチャートである。プロセスは、ハードウェア(例えば、回路、専用ロジックなど)、(汎用コンピュータシステム又は専用機械上で動かされるような)ソフトウェア、又は、両方の組み合わせを備えてもよい、係数エンコーダのプロセッシングロジックによって実行される。プロセッシングロジックはファームウェアを備えてもよい。
【0036】
[0056]図6を参照すると、プロセスは、プロセッシングロジックが、例えば、量子化器から量子化された係数を受信することによって開始する(処理ブロック601)。プロセッシングロジックは、その後、係数の全部がゼロであるか否かをテストする(処理ブロック602)。全係数がゼロであるならば、フラグは全係数がゼロであることを示し、プロセスは終了する。そうでなければ、プロセッシングロジックは、ブロック中の少なくとも1個の係数がゼロに等しくないということを特定するフラグを符号化し(処理ブロック604)、メモリからツリー構造データを取り出し(処理ブロック605)、さらに後述されるように、量子化された係数に基づいてツリー内の各ノードに値を割り当てる(処理606)。換言すると、プロセッシングロジックはツリーノード値を生成する。
【0037】
[0057]ツリーノード値を生成した後、プロセッシングロジックは、さらに後述されるように、ツリー内の各ノードに割り当てられた値を符号化する(処理ブロック607)。ツリーを符号化した後、プロセッシングロジックは、非ゼロの量子化された係数の値を符号化する(処理ブロック608)。一実施形態では、ハフマン符号化が使用される。代替的に、算術符号化又は別のコード化スキームが使用されてもよい。
【0038】
[0058]図7は、ツリーのノードの値を割り当てるプロセスの一実施形態のフローチャートである。プロセスは、ハードウェア(例えば、回路、専用ロジックなど)、(汎用コンピュータシステム又は専用機械上で動かされるような)ソフトウェア、又は、両方の組み合わせを備えてもよい、プロセッシングロジックによって実行される。
【0039】
[0059]プロセスはルートノードに設定された現ノード(以下、カレントノード)で始まる。図7を参照すると、プロセッシングロジックは、カレントノードがリーフノードであるかどうかを判定する(処理ブロック701)。カレントノードがリーフノードであるならば、プロセッシングロジックは、カレントノードに関連付けられた量子化された係数がゼロ係数であるかどうかを判定する(処理ブロック702)。係数がゼロであるならば、プロセッシングロジックは0という値をカレントノードに割り当て(処理ブロック703)、プロセスは終了し、そうでなければ、プロセッシングロジックは1という値をカレントノードに割り当て(処理ブロック704)、プロセスは終了する。
【0040】
[0060]カレントノードがリーフノードでないならば、プロセスは処理ブロック710へ移り、プロセッシングロジックが、カレントノードの第1の子をカレントノードとして用いて図7のプロセスを再帰的に実行し(処理ブロック710)、その後、カレントノードの第2の子をカレントノードとして用いて再び図7のプロセスを再帰的に実行する(処理ブロック711)。
【0041】
[0061]その後、プロセッシングロジックは、両方の子ノードが0という値を割り当てられているかどうかを判定する(処理ブロック712)。両方の子ノードが0という値を保有するならば、プロセッシングロジックは0という値をカレントノードに割り当て(処理ブロック703)、プロセスは終了し、そうでなければ、プロセッシングロジックは1という値をカレントノードに割り当て(処理ブロック704)、プロセスは終了する。
【0042】
[0062]カレントノードがルートノードに設定されるプロセスが終了した後、ツリー中の全ノードは0又は1という値が割り当てられている。ルートノードは、1個以上の係数がゼロに等しくないならば、値1を保有する。
【0043】
[0063]図8は、ツリー中のノードを符号化するプロセスの一実施形態のフローチャートである。プロセスは、ハードウェア(例えば、回路、専用ロジックなど)、(汎用コンピュータシステム又は専用機械上で動かされるような)ソフトウェア、又は、両方の組み合わせを備えてもよい、プロセッシングロジックによって実行される。プロセッシングロジックはファームウェアを備えてもよい。
【0044】
[0064]図8を参照すると、プロセスは最初にルートノードを引数として用いて呼び出される。プロセスは、プロセッシングロジックがノードはリーフであるかどうかを判定することによって開始する(処理ブロック801)。ノードがリーフであるならば、プロセッシングロジックは、そのノードの対応する係数の値を符号化し(処理ブロック802)、プロセスは終了する。種々の符号化スキーム(例えば、ハフマン符号化、算術符号化など)が使用されてもよい。
【0045】
[0065]ノードがリーフでないならば、プロセッシングロジックはノードの2個の子の値を符号化する(処理ブロック803)。符号化はさらに後述されている。その後、プロセッシングロジックは第1の子が1という値を保有するかどうかをテストする(処理ブロック804)。第1の子が値1を保有するならば、処理ブロックは、第1の子を引数として用いてノード符号化プロセスを再帰的に実行する(処理ブロック806)。プロセッシングロジックは、その後、第2の子の値が1であるかどうかをテストする(処理ブロック807)。第1の子が値0を保有するか、又は、第2の子が値1を有するならば、プロセッシングロジックは、第2の子を引数として用いてノード符号化プロセスを再帰的に実行する(処理ブロック805)。その後、プロセスは終了する。
【0046】
[0066]図9は、子ノードの値を符号化するプロセスの一実施形態のフローチャートである。プロセスは、ハードウェア(例えば、回路、専用ロジックなど)、(汎用コンピュータシステム又は専用機械上で動かされるような)ソフトウェア、又は、両方の組み合わせを備えてもよい、プロセッシングロジックによって実行される。プロセッシングロジックはファームウェアを備えてもよい。
【0047】
[0067]図9を参照すると、プロセスは、プロセッシングロジックが第1の子の値を符号化することによって開始する(処理ブロック901)。一実施形態では、値はビットストリームに付加される単一ビットとして符号化される。代替的に、値は算術符号化器を使用してさらに圧縮される。
【0048】
[0068]プロセッシングロジックは、その後、第1の子の値が1であるかどうかを決定する(処理ブロック902)。第1の子の値が0に等しいならば、プロセスは終了する。そうでなければ、プロセッシングロジックは第2の子の値を符号化する(処理ブロック903)。一実施形態では、値はビットストリームに付加される単一ビットとして符号化される。代替的に、値は算術符号化器を使用してさらに圧縮される。第2の子の値を符号化した後、プロセスは終了する。
【0049】
[0069]図10は、子ノードの値を符号化するプロセスの別の実施形態のフローチャートである。これは図9に記載されたプロセスへの代替的な実施形態であることに留意されたい。代替的に、方法の選択はノードに基づいて行われてもよい。選択情報は、メモリに格納され、ビットストリームに符号化されてもよい。このような符号化は選択された方法を示すためにビットを使用して行われてもよい。代替的に、エンコーダ及びデコーダの両方が、ノード毎にどの方法を使用すべきであるかに関する所定の引数を保有してもよい。
【0050】
[0070]図10のプロセスは、ハードウェア(例えば、回路、専用ロジックなど)、(汎用コンピュータシステム又は専用機械上で動かされるような)ソフトウェア、又は、両方の組み合わせを備えてもよいプロセッシングロジックによって実行される。プロセッシングロジックはファームウェアを備えてもよい。
【0051】
[0071]図10を参照すると、プロセスは、プロセッシングロジックが2個の子ノードの結合された値を符号化することにより開始する(処理ブロック1001)。一実施形態では、結合された値は、両方の子の値の間の論理AND演算の結果によって決定される。プロセッシングロジックは、次に、両方の子が1という値を保有するかどうかを判定する(処理ブロック1003)。コード化された値が1であるならば、プロセスは終了する。そうでなければ、プロセッシングロジックは第1の子の値を符号化し(処理ブロック1004)、プロセスは終了する。一実施形態では、値を符号化するとき、値はビットストリームにそのままで付加される。代替的に、値は算術符号化器を使用してさらに圧縮されてもよい。
【0052】
[0072]代替的に、三つ組のアルファベットが子ノードの値を表現するために使用されてもよい。このような場合、単一記号がビットストリームに付加される。
【0053】
[0073]図11は、変換デコーダの一実施形態のブロック図である。図11を参照すると、ビットストリーム1120が係数デコーダ1110に入力されている。係数デコーダ1110は、ビットストリーム1120からのビットを量子化された係数1111の集合に変換する。変換プロセスはさらに後述されている。逆量子化器1101は、量子化された係数1111を係数1102の集合にスケール変換する。逆変換1103は、係数1102を再構成画像データ1104に変換する。
【0054】
[0074]図12は、係数デコーダの一実施形態のブロック図である。図12を参照すると、エントロピーデコーダ1202は、さらに後述されているように、ビットストリーム1201からのビットを量子化された係数1203の集合に変換する。このため、エントロピーデコーダ1202は、メモリ1210に格納されているツリー構造データに依存する。エントロピーデコーダ1202は、ビットストリーム1201からツリー構造データを読み、メモリ1210に格納してもよい。
【0055】
[0075]図13は、量子化された係数を復号化するプロセスの一実施形態のフローチャートである。プロセスは、ハードウェア(例えば、回路、専用ロジックなど)、(汎用コンピュータシステム又は専用機械上で動かされるような)ソフトウェア、又は、両方の組み合わせを備えてもよい、プロセッシングロジックによって実行される。プロセッシングロジックはファームウェアを備えてもよい。
【0056】
[0076]図13を参照すると、プロセスは、プロセッシングロジックが集合中の全係数をゼロに設定することによって開始する(処理ブロック1301)。係数をゼロに設定した後、プロセッシングロジックはフラグを復号化する(処理ブロック1302)。プロセッシングロジックは、その後、全係数がゼロであるかどうかを判定する(処理ブロック1303)。全係数がゼロであることを示す第1の値をフラグがとるならば、プロセスは終了する。そうでなければ、プロセッシングロジックは、さらに後述されるように、ツリー中のノード値を復号化し(処理ブロック1304)、同様に係数値を復号化する(処理ブロック1305)。その後、プロセスは終了する。
【0057】
[0077]図14は、ノードを復号化するプロセスの一実施形態のフローチャートである。プロセスは、ハードウェア(例えば、回路、専用ロジックなど)、(汎用コンピュータシステム又は専用機械上で動かされるような)ソフトウェア、又は、両方の組み合わせを備えてもよい、プロセッシングロジックによって実行される。プロセッシングロジックはファームウェアを備えてもよい。
【0058】
[0078]図14を参照すると、プロセスはルートノードを引数として用いて開始する。プロセッシングロジックはノードがリーフであるかどうかを判定する(処理ブロック1401)。ノードがリーフノードであるならば、プロセッシングロジックは係数の値をさらに復号化し(処理ブロック1402)、その後にプロセスが終了する。復号化は種々の復号化技術(例えば、ハフマン符号化、算術符号化など)を使用して実行されてもよい。
【0059】
[0079]ノードがリーフでないならば、プロセッシングロジックはそのノードの2個の子の値を復号化する(処理ブロック1403)。復号化はさらに後述されている。その後、プロセッシングロジックは、第1の子が1という値を保有するかどうかをテストする(処理ブロック1404)。第1の子が値1を保有するならば、処理ブロックは、第1の子を引数として用いてノード復号化プロセスを再帰的に実行する(処理ブロック1406)。プロセッシングロジックは、その後、第2の子が値1を保有するかどうかをテストする(処理ブロック1407)。第1の子が値0を保有するか、又は、第2の子が値1を保有するならば、プロセッシングロジックは、第2の子を引数として用いてノード復号化プロセスを再帰的に実行する(処理ブロック1405)。その後、プロセスは終了する。
【0060】
[0080]図15は、子ノードの値を復号化するプロセスの一実施形態のフローチャートである。プロセスは、ハードウェア(例えば、回路、専用ロジックなど)、(汎用コンピュータシステム又は専用機械上で動かされるような)ソフトウェア、又は、両方の組み合わせを備えてもよい、プロセッシングロジックによって実行される。プロセッシングロジックはファームウェアを備えてもよい。
【0061】
[0081]図15を参照すると、プロセスは第1の子の値を復号化することによって開始する(処理ブロック1501)。復号化プロセスは、ビットストリームから単一ビットを取り出すこと、又は、算術デコーダを用いてビットストリームからバイナリ記号を復号化することを伴ってもよい。プロセッシングロジックは、第1の子の値が1であるかどうかを判定する(処理ブロック1502)。復号化された値が0であるならば、プロセスは終了し、そうではなく、値が1であるならば、プロセッシングロジックは、第1の値と同様に、第2の子の値を復号化し(処理ブロック1503)、その後、プロセスは終了する。
【0062】
[0082]図16は、子ノードの値を復号化するプロセスの代替的な実施形態のフローチャートである。プロセスは、ハードウェア(例えば、回路、専用ロジックなど)、(汎用コンピュータシステム又は専用機械上で動かされるような)ソフトウェア、又は、両方の組み合わせを備えてもよい、プロセッシングロジックによって実行される。プロセッシングロジックはファームウェアを備えてもよい。
【0063】
[0083]図16を参照すると、プロセスは両方の子の結合された値を復号化して開始する(処理ブロック1601)。結合された値は、両方の子が値1を保有するかどうかを示すことができる。プロセッシングロジックは、両方の子が1という値を保有するかどうかを判定する(処理ブロック1602)。両方の子が1という値を保有するならば、プロセスは終了し、そうではなく、値が1であるならば、プロセッシングロジックは第1の子の値を復号化し、第2の子の値を反対の値に設定し(処理ブロック1603)、その後、プロセスは終了する。
【0064】
[0084]代替的に、両方の子の値は三つ組のアルファベットを用いて表現される。このような場合、単一記号が子ノードの値を取得するために復号化されてもよい。
【0065】
[0085]図18は量子化された係数を復号化するプロセスの一実施形態のフローチャートである。プロセスは、ハードウェア(例えば、回路、専用ロジックなど)、(汎用コンピュータシステム又は専用機械上で動かされるような)ソフトウェア、又は、両方の組み合わせを備えてもよい、プロセッシングロジックによって実行される。プロセッシングロジックはファームウェアを備えてもよい。
【0066】
[0086]図18を参照すると、プロセスは、プロセッシングロジックが状態を1に設定し、スタックを空状態に初期化することにより開始する(処理ブロック1801)。その後、プロセッシングロジックはメモリからノードタイプを取り出す(処理ブロック1802)。プロセッシングロジックは、その後、ノードがリーフノードであるかどうかを判定する(処理ブロック1803)。ノードタイプがリーフノードであることを示すならば、処理は処理ブロック1820へ移り、そうでなければ、処理は処理ブロック1810へ移る。
【0067】
[0087]処理ブロック1820において、プロセッシングロジックはメモリからリーフインデックスIを取り出し、状態が値0を有するかどうかをテストする(処理ブロック1821)。状態が値0を有するならば、処理は処理ブロック1823へ移り、プロセッシングロジックはインデックスIをもつ係数に値0を割り当て、その後、処理は処理ブロック1824へ移る。状態が値1を有するならば、処理は処理ブロック1822へ移り、プロセッシングロジックはビットストリームから係数値を復号化し、インデックスIをもつ係数に復号化された係数値を割り当て、その後、処理は処理ブロック1824へ移る。
【0068】
[0088]処理ブロック1824において、プロセッシングロジックは、スタックが空であるかどうかを判定する。スタックが空であるならば、プロセスは終了する。スタックが空でなければ、処理は処理ブロック1825へ移り、プロセッシングロジックはスタックから値をポップし、状態をその値に設定する。その後、処理は処理ブロック1802へ移る。
【0069】
[0089]ノードがリーフノードでないならば(処理ブロック1803)、プロセッシングロジックは状態が1に等しいかどうかを判定する(処理ブロック1810)。そうでなければ(すなわち、値が0であるならば)、プロセッシングロジックは2個のノードの値をゼロに設定し、処理ブロック1814へ移る。状態が1に等しければ、プロセッシングロジックはビットストリームから2個のノード値を復号化する(処理ブロック1812)。ノード値を復号化する方法の例は、図15及び16に記載されている。2個のノード値を復号化した後、プロセッシングロジックは状態を第1のノード値に設定し(処理ブロック1813)、処理ブロック1814へ移る。処理ブロック1814において、プロセッシングロジックは第2のノード値をスタックへプッシュする。その後、処理は処理ブロック1802へ移る。
【0070】
[0090]図19は、係数デコーダの一実施形態のブロック図である。図19を参照すると、係数デコーダは状態レジスタ1920を含む。一実施形態では、状態レジスタ1920は最初に値1に設定される。エントロピーデコーダ1902は、ノードタイプメモリ1923からノードタイプを取り出す。ノードタイプメモリ1923は、図4に記載されているように、ツリーの構造に関するデータを収容する。ノードタイプがリーフノードを示し、状態レジスタの値が1であるならば、エントロピーデコーダ1902はビットストリームから量子化された係数を復号化し、それを選択器1903へ送信する。選択器1903は、量子化された係数を選択し、それを係数メモリ1904へ送信する。係数メモリ1904へのインデックスは、リーフインデックスメモリ1921から取り出されたリーフインデックスによって決定される。そうではなく、状態レジスタ1920が0であるならば、選択器1903は値0を選択し、それを係数メモリ1904へ送信する。量子化された係数が量子化された係数メモリ1904に格納された後、値がスタック1922からポップされ、状態レジスタ1920に割り当てられる。そうでなく、ノードタイプがリーフノードを示さないならば、係数デコーダは以下の通り動作する。状態レジスタ1920が1であるならば、エントロピーデコーダ1902は、例えば、図15及び16に記載されているように、ビットストリーム1901から2個のノード値を復号化する。第1のノード値はエントロピーデコーダ1902によって状態レジスタ1920に割り当てられ、第2のノード値はエントロピーデコーダ1902によってスタック1922へプッシュされる。そうではなく、状態レジスタ1920が0であるならば、状態レジスタ1920の内容がスタックへプッシュされる。
【0071】
[0091]一実施形態では、デコーダは、量子化された係数メモリ内の全ての量子化された係数に値が割り当てられるまで、この方式で動作する。量子化された係数メモリの内容は、その後、量子化された係数の順序付き集合として出力される。
【0072】
[0092]上述のように、本明細書に記載された技術は任意のデータのベクトルに適用されてもよい。例えば、これらの技術は、前方向動きベクトルに対応する水平移動及び垂直移動と後方向動きベクトルに対応する水平移動及び垂直移動とを有するデータのブロックを含む次元4のベクトルをコード化するためにbフレームをビデオコード化するときに使用されてもよい。この場合、本明細書に記載された技術は、ゼロでない方を示すために使用されてもよい。
【0073】
(コードの例)
[0093]以下のサンプルCコードは、本発明に記載されているような係数を復号化するために使用できる。ツリーの深さ優先トラバース及び幅優先トラバースの例が提供されている。
【数1】
【数2】
【0074】
[0094]適切なツリー構造データは、係数ブロックの集合から導出できる。以下のサンプルCコードは、係数の各組み合わせが非ゼロであることを頻度を用いて示す統計量の集合からツリー構造データを構築する。
【数3】
【数4】
【数5】
【数6】
【数7】
【数8】
【0075】
(典型的なコンピュータシステム)
[0095]図20は、本明細書に記載された1個以上の演算を実行できる典型的なコンピュータシステムのブロック図である。コンピュータシステム2000は、典型的なクライアント又はサーバーコンピュータシステムを備えてもよい。コンピュータシステムに関して記述されたコンポーネントは、ハンドヘルド機器又はモバイル機器(例えば、携帯電話機)の一部であってもよい。
【0076】
[0096]図20を参照すると、コンピュータシステム2000は、情報を通信する通信メカニズム又はバス2011と、バス2011と接続され情報を処理するプロセッサ2012とを備える。プロセッサ2012は、マイクロプロセッサを含むが、例えば、Pentium(登録商標)プロセッサなどのようなマイクロプロセッサに限定されない。
【0077】
[0097]システム2000は、バス2011に接続され、情報とプロセッサ2012によって実行されるべき命令とを格納する、ランダムアクセスメモリ(RAM)又はその他のダイナミック記憶装置2004(メインメモリとして参照される)を、さらに備える。メインメモリ2004はまた、プロセッサ2012による命令の実行中に、一時変数又はその他の中間情報を格納するためにも使用できる。
【0078】
[0098]コンピュータシステム2000は、バス2011に接続され、スタティック情報及びプロセッサ2012のための命令を格納するリードオンリーメモリ(ROM)及び/又はその他のスタティック記憶装置2006と、磁気ディスク又は光ディスク、及び、それに対応するディスクドライブのようなデータ記憶装置2007とを、さらに備える。データ記憶装置2007は、バス2011に接続され、情報及び命令を格納する。
【0079】
[0099]コンピュータシステム2000は、バス2011に接続され、情報をコンピュータユーザへ表示する陰極線管(CRT)又は液晶ディスプレイ(LCD)のようなディスプレイ機器2021に、さらに接続されてもよい。英数字キー及びその他のキーを含む英数字入力機器2022は、同様にバス2011に接続され、情報及びコマンド選択をプロセッサ2012へ通信できる。付加的なユーザ入力機器は、カーソル制御機器2023である。このカーソル制御機器2023は、例えばマウス、トラックボール、トラックパッド、スタイラス、又は、カーソル方向キーである。カーソル制御機器2023は、方向情報及びコマンド選択をプロセッサ2012へ通信し、ディスプレイ2021上のカーソル移動を制御するために、バス2011に接続されている。
【0080】
[00100]バス2011に接続できる別の機器は、ハードコピー機器2024である。ハードコピー機器2024は、紙、フィルム、又は、類似したタイプの媒体のような媒体上に情報を残すために使用できる。バス2011に接続できる別の機器は、電話機又はハンドヘルドパーム機器へ通信するための有線/無線通信機能部2025である。
【0081】
[00101]システム2000のコンポーネント、及び、関連したハードウェアの何れか又は全部が本発明において使用できることに留意されたい。しかし、コンピュータシステムのその他の構成は、機器の一部又は全部を含んでもよいことが認められるであろう。
【0082】
[00102]以上の説明を読んだ後に、本発明の多数の代替及び変形が当業者に明白になることは確実であるが、説明のために図示され記載された特定の実施形態が制限的であるとみなされることは決して意図されていないことが理解されるべきである。したがって、種々の実施形態の詳細への言及は、本発明に不可欠であると考えられる構成要件だけをそれ自体に列挙する請求項の範囲を制限することを意図していない。
【特許請求の範囲】
【請求項1】
データのベクトル中のデータを、ツリーデータ構造を使用して特定された前記データがゼロであるか又は非ゼロであるかの指標に基づいてコード化するデータコード化ステップと、
コード化されたデータに基づいてビットストリームを作成するビットストリーム作成ステップと、
を備える方法。
【請求項2】
データのベクトルを受信する入力と、
前記入力に接続され、前記データのベクトル中のデータを、ツリーデータ構造を使用して特定された前記データがゼロであるか又は非ゼロであるかの指標に基づいてコード化する、エントロピーエンコーダと、
を備える、係数を符号化する装置。
【請求項3】
システムによって実行されたとき、前記システムに、
データのベクトル中のデータを、ツリーデータ構造を使用して特定された前記データがゼロであるか又は非ゼロであるかの指標に基づいてコード化するデータコード化ステップと、
コード化されたデータに基づいてビットストリームを作成するビットストリーム作成ステップと、
を備える方法を実行させる命令を記憶する1つ以上の記録可能な媒体を有する製品。
【請求項4】
ビットストリームを受信するビットストリーム受信ステップと、
復号化されたデータのベクトルを、ツリーデータ構造によって特定されるような前記データがゼロであるか又は非ゼロであるかの指標に基づいて作成するため、前記ビットストリームを復号化するビットストリーム復号化ステップと、
を備える方法。
【請求項5】
ビットストリームを受信する入力と、
前記入力に接続され、復号化されたデータのベクトルを、ツリーデータ構造によって特定されるような前記データがゼロであるか又は非ゼロであるかの指標に基づいて作成する、エントロピーデコーダと、
を備える、量子化された係数を復号化する装置。
【請求項6】
システムによって実行されたとき、前記システムに、
復号化されたデータのベクトルを、ツリーデータ構造によって特定されるような前記データがゼロであるか又は非ゼロであるかの指標に基づいて作成するため、ビットストリームを復号化するビットストリーム復号化ステップを備える方法を実行させる命令を記憶する1つ以上の記録可能な媒体を有する製品。
【請求項1】
データのベクトル中のデータを、ツリーデータ構造を使用して特定された前記データがゼロであるか又は非ゼロであるかの指標に基づいてコード化するデータコード化ステップと、
コード化されたデータに基づいてビットストリームを作成するビットストリーム作成ステップと、
を備える方法。
【請求項2】
データのベクトルを受信する入力と、
前記入力に接続され、前記データのベクトル中のデータを、ツリーデータ構造を使用して特定された前記データがゼロであるか又は非ゼロであるかの指標に基づいてコード化する、エントロピーエンコーダと、
を備える、係数を符号化する装置。
【請求項3】
システムによって実行されたとき、前記システムに、
データのベクトル中のデータを、ツリーデータ構造を使用して特定された前記データがゼロであるか又は非ゼロであるかの指標に基づいてコード化するデータコード化ステップと、
コード化されたデータに基づいてビットストリームを作成するビットストリーム作成ステップと、
を備える方法を実行させる命令を記憶する1つ以上の記録可能な媒体を有する製品。
【請求項4】
ビットストリームを受信するビットストリーム受信ステップと、
復号化されたデータのベクトルを、ツリーデータ構造によって特定されるような前記データがゼロであるか又は非ゼロであるかの指標に基づいて作成するため、前記ビットストリームを復号化するビットストリーム復号化ステップと、
を備える方法。
【請求項5】
ビットストリームを受信する入力と、
前記入力に接続され、復号化されたデータのベクトルを、ツリーデータ構造によって特定されるような前記データがゼロであるか又は非ゼロであるかの指標に基づいて作成する、エントロピーデコーダと、
を備える、量子化された係数を復号化する装置。
【請求項6】
システムによって実行されたとき、前記システムに、
復号化されたデータのベクトルを、ツリーデータ構造によって特定されるような前記データがゼロであるか又は非ゼロであるかの指標に基づいて作成するため、ビットストリームを復号化するビットストリーム復号化ステップを備える方法を実行させる命令を記憶する1つ以上の記録可能な媒体を有する製品。
【図1A】
【図1B】
【図2】
【図3】
【図4】
【図5】
【図6】
【図7】
【図8】
【図9】
【図10】
【図11】
【図12】
【図13】
【図14】
【図15】
【図16】
【図17】
【図18】
【図19】
【図20】
【図1B】
【図2】
【図3】
【図4】
【図5】
【図6】
【図7】
【図8】
【図9】
【図10】
【図11】
【図12】
【図13】
【図14】
【図15】
【図16】
【図17】
【図18】
【図19】
【図20】
【公開番号】特開2012−135017(P2012−135017A)
【公開日】平成24年7月12日(2012.7.12)
【国際特許分類】
【外国語出願】
【出願番号】特願2012−32861(P2012−32861)
【出願日】平成24年2月17日(2012.2.17)
【分割の表示】特願2010−161644(P2010−161644)の分割
【原出願日】平成17年12月15日(2005.12.15)
【出願人】(392026693)株式会社エヌ・ティ・ティ・ドコモ (5,876)
【Fターム(参考)】
【公開日】平成24年7月12日(2012.7.12)
【国際特許分類】
【出願番号】特願2012−32861(P2012−32861)
【出願日】平成24年2月17日(2012.2.17)
【分割の表示】特願2010−161644(P2010−161644)の分割
【原出願日】平成17年12月15日(2005.12.15)
【出願人】(392026693)株式会社エヌ・ティ・ティ・ドコモ (5,876)
【Fターム(参考)】
[ Back to top ]