JP2012135017A - 係数の位置をコード化する方法及び装置 - Google Patents

係数の位置をコード化する方法及び装置 Download PDF

Info

Publication number
JP2012135017A
JP2012135017A JP2012032861A JP2012032861A JP2012135017A JP 2012135017 A JP2012135017 A JP 2012135017A JP 2012032861 A JP2012032861 A JP 2012032861A JP 2012032861 A JP2012032861 A JP 2012032861A JP 2012135017 A JP2012135017 A JP 2012135017A
Authority
JP
Japan
Prior art keywords
data
zero
node
tree
value
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Granted
Application number
JP2012032861A
Other languages
English (en)
Other versions
JP5579760B2 (ja
Inventor
Frank Bossen
フランク ボッセン，
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
NTT Docomo Inc
Original Assignee
NTT Docomo Inc
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by NTT Docomo Inc filed Critical NTT Docomo Inc
Publication of JP2012135017A publication Critical patent/JP2012135017A/ja
Application granted granted Critical
Publication of JP5579760B2 publication Critical patent/JP5579760B2/ja
Anticipated expiration legal-status Critical
Expired - Lifetime legal-status Critical Current

Links

Images

Classifications

    • H—ELECTRICITY
    • H03—ELECTRONIC CIRCUITRY
    • H03M—CODING; DECODING; CODE CONVERSION IN GENERAL
    • H03M7/00—Conversion of a code where information is represented by a given sequence or number of digits to a code where the same, similar or subset of information is represented by a different sequence or number of digits
    • H03M7/30—Compression; Expansion; Suppression of unnecessary data, e.g. redundancy reduction
    • H03M7/3082—Vector coding
    • H—ELECTRICITY
    • H03—ELECTRONIC CIRCUITRY
    • H03M—CODING; DECODING; CODE CONVERSION IN GENERAL
    • H03M7/00—Conversion of a code where information is represented by a given sequence or number of digits to a code where the same, similar or subset of information is represented by a different sequence or number of digits
    • H03M7/30—Compression; Expansion; Suppression of unnecessary data, e.g. redundancy reduction
    • H03M7/40—Conversion to or from variable length codes, e.g. Shannon-Fano code, Huffman code, Morse code
    • H—ELECTRICITY
    • H03—ELECTRONIC CIRCUITRY
    • H03M—CODING; DECODING; CODE CONVERSION IN GENERAL
    • H03M7/00—Conversion of a code where information is represented by a given sequence or number of digits to a code where the same, similar or subset of information is represented by a different sequence or number of digits
    • H03M7/30—Compression; Expansion; Suppression of unnecessary data, e.g. redundancy reduction
    • H03M7/46—Conversion to or from run-length codes, i.e. by representing the number of consecutive digits, or groups of digits, of the same kind by a code word and a digit indicative of that kind
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04N—PICTORIAL COMMUNICATION, e.g. TELEVISION
    • H04N19/00—Methods or arrangements for coding, decoding, compressing or decompressing digital video signals
    • H04N19/10—Methods or arrangements for coding, decoding, compressing or decompressing digital video signals using adaptive coding
    • H04N19/102—Methods or arrangements for coding, decoding, compressing or decompressing digital video signals using adaptive coding characterised by the element, parameter or selection affected or controlled by the adaptive coding
    • H04N19/129—Scanning of coding units, e.g. zig-zag scan of transform coefficients or flexible macroblock ordering [FMO]
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04N—PICTORIAL COMMUNICATION, e.g. TELEVISION
    • H04N19/00—Methods or arrangements for coding, decoding, compressing or decompressing digital video signals
    • H04N19/10—Methods or arrangements for coding, decoding, compressing or decompressing digital video signals using adaptive coding
    • H04N19/102—Methods or arrangements for coding, decoding, compressing or decompressing digital video signals using adaptive coding characterised by the element, parameter or selection affected or controlled by the adaptive coding
    • H04N19/13—Adaptive entropy coding, e.g. adaptive variable length coding [AVLC] or context adaptive binary arithmetic coding [CABAC]
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04N—PICTORIAL COMMUNICATION, e.g. TELEVISION
    • H04N19/00—Methods or arrangements for coding, decoding, compressing or decompressing digital video signals
    • H04N19/10—Methods or arrangements for coding, decoding, compressing or decompressing digital video signals using adaptive coding
    • H04N19/134—Methods or arrangements for coding, decoding, compressing or decompressing digital video signals using adaptive coding characterised by the element, parameter or criterion affecting or controlling the adaptive coding
    • H04N19/136—Incoming video signal characteristics or properties
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04N—PICTORIAL COMMUNICATION, e.g. TELEVISION
    • H04N19/00—Methods or arrangements for coding, decoding, compressing or decompressing digital video signals
    • H04N19/10—Methods or arrangements for coding, decoding, compressing or decompressing digital video signals using adaptive coding
    • H04N19/169—Methods or arrangements for coding, decoding, compressing or decompressing digital video signals using adaptive coding characterised by the coding unit, i.e. the structural portion or semantic portion of the video signal being the object or the subject of the adaptive coding
    • H04N19/17—Methods or arrangements for coding, decoding, compressing or decompressing digital video signals using adaptive coding characterised by the coding unit, i.e. the structural portion or semantic portion of the video signal being the object or the subject of the adaptive coding the unit being an image region, e.g. an object
    • H04N19/176—Methods or arrangements for coding, decoding, compressing or decompressing digital video signals using adaptive coding characterised by the coding unit, i.e. the structural portion or semantic portion of the video signal being the object or the subject of the adaptive coding the unit being an image region, e.g. an object the region being a block, e.g. a macroblock
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04N—PICTORIAL COMMUNICATION, e.g. TELEVISION
    • H04N19/00—Methods or arrangements for coding, decoding, compressing or decompressing digital video signals
    • H04N19/46—Embedding additional information in the video signal during the compression process
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04N—PICTORIAL COMMUNICATION, e.g. TELEVISION
    • H04N19/00—Methods or arrangements for coding, decoding, compressing or decompressing digital video signals
    • H04N19/50—Methods or arrangements for coding, decoding, compressing or decompressing digital video signals using predictive coding
    • H04N19/503—Methods or arrangements for coding, decoding, compressing or decompressing digital video signals using predictive coding involving temporal prediction
    • H04N19/51—Motion estimation or motion compensation
    • H04N19/513—Processing of motion vectors
    • H04N19/517—Processing of motion vectors by encoding
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04N—PICTORIAL COMMUNICATION, e.g. TELEVISION
    • H04N19/00—Methods or arrangements for coding, decoding, compressing or decompressing digital video signals
    • H04N19/90—Methods or arrangements for coding, decoding, compressing or decompressing digital video signals using coding techniques not provided for in groups H04N19/10-H04N19/85, e.g. fractals
    • H04N19/96—Tree coding, e.g. quad-tree coding

Landscapes

  • Engineering & Computer Science (AREA)
  • Multimedia (AREA)
  • Signal Processing (AREA)
  • Theoretical Computer Science (AREA)
  • Compression, Expansion, Code Conversion, And Decoders (AREA)
  • Compression Or Coding Systems Of Tv Signals (AREA)
  • Compression Of Band Width Or Redundancy In Fax (AREA)

Abstract

【課題】係数のようなデータの位置をコード化し、又、デコードする方法及び装置を提供する。
【解決手段】ツリーデータ構造を使用して特定された、データがゼロであるか又は非ゼロであるかの指標に基づいて、データのベクトル中のデータをコード化するデータコード化ステップと、コード化されたデータに基づいてビットストリームを生成するビットストリーム生成ステップとを備える符号化を行い、そのようにして生成されたビットストリームを受信し復号を行う。
【選択図】図１Ａ

Description

[0001]本特許文献の開示の一部は著作権保護の対象となる素材を含んでいる。著作権所有者は、特許商標局における特許ファイル又は記録物において明白であるので、何人による特許文献又は特許情報開示の複製にも異議を唱えないが、それ以外は、いかなるものであれ全ての著作権を留保する。
［優先権］
[0002]本特許出願は、発明の名称が“Ｍｅｔｈｏｄ ａｎｄ Ａｐｐａｒａｔｕｓ ｆｏｒ Ｃｏｄｉｎｇ Ｐｏｓｉｔｉｏｎｓ ｏｆ Ｎｏｎ−ｚｅｒｏ Ｃｏｅｆｆｉｃｉｅｎｔｓ ｉｎ ａ Ｂｌｏｃｋ”である、２００４年１２月２２日に出願された、対応する仮特許出願第６０／６３９，４３０号に基づく優先権を主張する。
[0003]本発明は、コード化の分野に関し、より詳しくは、本発明は、グループ（例えば、係数のブロック）内のある種の係数（例えば、非ゼロ係数）のコード化に関係する。
[0004]データ圧縮は、大量のデータを蓄積及び伝送するための非常に有用なツールである。例えば、文書のネットワーク伝送のような画像を伝送するために要する時間は、画像を再現するために必要とされるビット数を減少させるため圧縮が使用されたとき、大幅に短縮される。
[0005]多種多様なデータ圧縮技術が従来技術に存在している。圧縮技術は、損失のあるコード化と損失のないコード化の２つに大別される。損失のあるコード化は、元データの完全な再構成の保証がないほどに、情報の損失を生じるコード化を含む。損失のある圧縮の目標は、元データへの変更が、異議の余地なしに、又は、検出できないように行われる。損失のない圧縮では、全ての情報が保持され、完全な再構成を可能にするようにデータは圧縮される。
[0006]画像符号化器及びビデオ符号化器において、画像は典型的にブロックの組に区分化される。各ブロックは係数の集合に変換され量子化される。係数は、変換（例えば、離散コサイン変換（ＤＣＴ）、ウェーブレット変換）をデータに適用することにより作成できる。例えば、ＪＰＥＧでは、ＤＣＴ変換は、係数を作成するため画像データに適用される。その後、これらの係数は量子化されてもよい。ブロック毎に、どの係数が非ゼロ値を有するかを記述する情報が伝送されなければならない。
[0007]量子化された係数は、典型的に値の１次元配列に配置される。配列中の係数の順序は、走査順序によって、例えば、ジグザグ走査順序によって決定される。非ゼロ係数の位置は、その後に、ランレングス符号化法を使用してコード化される。
[0008]走査方法は、多くの場合に効率が制限されている。例えば、ジグザグ走査方法に関して、ブロックが水平周波数だけ又は垂直周波数だけを収容するとき、多数のゼロ係数がジグザグパターンに沿って訪問され、効率が悪いという結果になる。
係数のようなデータの位置をコード化する方法及び装置が記載されている。一実施形態では、方法は、ツリーデータ構造を使用して特定された、データがゼロであるか又は非ゼロであるかの指標に基づいて、データのベクトル中のデータをコード化するデータコード化ステップと、コード化されたデータに基づいてビットストリームを作成するビットストリーム作成ステップとを備える。
[0009]本発明は、後述される詳細な説明と、本発明を特定の実施形態に制限するように解釈されるべきでなく、説明と理解のためだけに用いられる本発明の種々の実施形態の添付図面とから、より十分に理解される。
データを符号化するプロセスの一実施形態のフローチャートである。 データを復号化するプロセスの一実施形態のフローチャートである。 エンコーダ及びデコーダのシステムの一実施形態のブロック図である。 変換エンコーダの一実施形態のブロック図である。 ツリー構造データの例である。 係数エンコーダの一実施形態のブロック図である。 係数エンコーダによって実行される符号化プロセスの一実施形態のフローチャートである。 値をツリーのノードに割り当てるプロセスの一実施形態のフローチャートである。 ツリー中のノードを符号化するプロセスの一実施形態のフローチャートである。 子ノードの値を符号化するプロセスの一実施形態のフローチャートである。 子ノードの値を符号化するプロセスの別の実施形態のフローチャートである。 変換デコーダの一実施形態のブロック図である。 係数デコーダの一実施形態のブロック図である。 量子化された係数を復号化するプロセスの一実施形態のフローチャートである。 ノードを復号化するプロセスの一実施形態のフローチャートである。 子ノードの値を復号化するプロセスの一実施形態のフローチャートである。 子ノードの値を復号化するプロセスの代替的な実施形態のフローチャートである。 図４のツリー構造の表現の例を説明する図である。 量子化された係数を復号化するプロセスの一実施形態のフローチャートである。 係数デコーダの一実施形態のブロック図である。 コンピュータシステムの一実施形態のブロック図である。
[0031]データのグループ（例えば、データのブロック）内の係数（例えば、非ゼロ係数）の位置をコード化する方法及び装置について記載されている。一実施形態では、係数は二分木に配置される。ツリーは節（ノード）を系統的に一つ残らず一回ずつなぞられ（以下、トラバースされ）、非ゼロ係数の位置をコード化する。本発明の実施形態は、伝統的なジグザグ走査を使用する係数のコード化への代替案を提供し、ツリー内での係数の体系化に依存し、それによって、単一の走査より高い柔軟性及び良い効率を提供する。
[0032]後に続く実施形態は係数を用いて動作するものとして記載されているが、本明細書に記載された技術が任意のデータのベクトルに適用されることは当業者に明白であろう。
[0033]以下の記載では、本発明のより徹底的な説明を行うために様々な詳細が示されている。しかし、本発明が、これらの特定の詳細を用いることなく実施されてもよいことは当業者にとって明白であろう。他の例では、よく知られている構成及び機器は、本発明を不明瞭化することを避けるために、詳細にではなく、ブロック図形式で示されている。
[0034]後述する詳細な説明の一部は、コンピュータメモリ内のデータビットに関する演算のアルゴリズム及び記号的表現という点で提示されている。これらのアルゴリズム的な記述及び表現は、データ処理技術の当業者によって、自分の業績の内容をその技術における他の当業者へ最も効率的に伝達するために使用される手段である。アルゴリズムは、ここでは、一般的に、望ましい結果をもたらすステップの首尾一貫したシーケンスであると考えられる。ステップは物理量の物理的操作を必要とするステップである。通常、不可欠ではないが、これらの量は、記憶、転送、合成、比較及びそれ以外の操作がなされ得る、電気的又は磁気的信号の形式をとる。主として慣用上の理由で、これらの信号を、ビット、値、要素、記号、文字、項、数などと呼ぶことが、時として好都合であることがわかった。
[0035]しかし、上記の用語及び類似した用語の全ては、適切な物理量と関連付けられるべきであり、これらの量に当てはめられた便宜的なラベルに過ぎないことに留意されたい。以下の説明から明白であるように、特に断らない限り、説明の全体を通じて、「処理」又は「コンピューティング」又は「計算」又は「決定」又は「表示」などのような用語を利用する説明は、コンピュータシステムのレジスタ及びメモリ内で物理（電子）量として表現されたデータを、コンピュータシステムメモリ若しくはレジスタ内、又は、その他のこのような情報記憶装置、伝送機器若しくは表示機器内で同じように物理量として表現されたその他のデータへ操作、変換する、コンピュータシステム又は類似した電子コンピューティング機器の作用及びプロセスを指すことが認められる。
[0036]本発明は、本明細書に記載された演算を実行する装置にも関係する。この装置は、要求された目的のため特に構成されるか、又は、コンピュータに格納されたコンピュータプログラムによって選択的に作動若しくは再構成される汎用コンピュータを備えてもよい。このようなコンピュータプログラムは、限定されることはないが、例えば、フロッピー（登録商標）ディスク、光ディスク、ＣＤ−ＲＯＭ、及び、磁気光ディスクを含む任意のタイプのディスク、リードオンリーメモリ（ＲＯＭ）、ランダムアクセスメモリ（ＲＡＭ）、ＥＰＲＯＭ、ＥＥＰＲＯＭ、磁気若しくは光カード、又は、電子命令を格納するのに適当であり、それぞれコンピュータシステムバスに接続されている任意のタイプの媒体のような、コンピュータ読み取り可能な記憶媒体に格納されてもよい。
[0037]本明細書に提示されているアルゴリズム及びディスプレイは、本質的に特定のコンピュータ又はその他の装置に関連していない。種々の汎用システムが本明細書における教示に従うプログラムと共に使用されてもよく、又は、要求された方法ステップを実行するためにより特化された装置を構築すると好都合であることがわかる。多種多様のこれらのシステムに要求される構成は以下の記載から明らかであろう。さらに、本発明は特定のプログラミング言語に関して記載されていない。多種多様のプログラミング言語が、本明細書に記載されているような発明の教示を実施するために使用されてもよいことが認められるであろう。
[0038]機械読み取り可能な媒体は、機械（例えば、コンピュータ）によって読み取り可能な形式で情報を格納又は伝送する任意の仕組みを含む。例えば、機械読み取り可能な媒体は、リードオンリーメモリ（ＲＯＭ）、ランダムアクセスメモリ（ＲＡＭ）、磁気ディスク記憶媒体、光記憶媒体、フラッシュメモリデバイス、電気的、光学的、音響的又はその他の形式の伝搬信号（例えば、搬送波、赤外線信号、デジタル信号など）などを含む。
（概要）
[0039]図１Ａはデータを符号化するプロセスの一実施形態のフローチャートである。プロセスは、ハードウェア（例えば、回路、専用ロジックなど）、（汎用コンピュータシステム又は専用機械上で動かされるような）ソフトウェア、又は、両方の組み合わせを備えてもよい、プロセッシングロジックによって実行される。プロセッシングはファームウェアによって実行されてもよい。
[0040]図１Ａを参照すると、プロセスは、プロセッシングロジックが、前に生成されたデータ構造を使用して特定された非ゼロ係数の位置の指標に基づいて、係数のグループ内の非ゼロ係数の位置をコード化することによって開始する（処理ブロック１０１）。一実施形態では、データ構造はツリーを表現する。ツリーは二分木でもよい。一実施形態では、係数のグループは係数のブロックを含む。
[0041]次に、プロセッシングロジックはコード化された非ゼロ係数に基づいてビットストリームを生成する（処理ブロック１０２）。
[0042]図１Ｂはデータを復号化するプロセスの一実施形態のフローチャートである。プロセスは、ハードウェア（例えば、回路、専用ロジックなど）、（汎用コンピュータシステム又は専用機械上で動かされるような）ソフトウェア、又は、両方の組み合わせを備えてもよい、プロセッシングロジックによって実行される。プロセッシングはファームウェアによって実行されてもよい。
[0043]図１Ｂを参照すると、プロセスは、プロセッシングロジックがビットストリームを受信することによって開始する（処理ブロック１１１）。次に、プロセッシングロジックは、前に生成されたデータ構造によって特定された量子化された係数の位置の指標に基づいて、係数のグループ内の量子化された係数の位置を得るために前に生成されたデータ構造を使用することを含めて、量子化された係数の集合を生成するためにビットストリームを復号化する（処理ブロック１１２）。
[0044]一実施形態では、データ構造表現はツリーである。ツリーは二分木でもよい。一実施形態では、係数のグループは係数のブロックを含む。
[0045]図２はエンコーダ及びデコーダシステムの一実施形態のブロック図である。一部のシステムはエンコーダ又はデコーダだけを含んでもよい。
[0046]図２を参照すると、エンコーダ２０２はソース画像２０１を、ソース画像２０１の圧縮表現であるビットストリーム２０３に変換する。デコーダ２０４は、ビットストリーム２０３を、再構成画像２０５に変換する。再構成画像２０５は、ソース画像２０１の近似（損失のある圧縮コンフィギュレーションにおける）又は（損失のない圧縮コンフィギュレーションにおける）正確な複製である。ビットストリーム２０３は、通信チャネル（例えば、インターネットなど）を介して、又は、物理的な媒体（例えば、ＣＤ−ＲＯＭ）を介して、エンコーダ２０２からデコーダ２０３へ送信されてもよい。
[0047]図３は、変換エンコーダの一実施形態のブロック図である。図３の変換エンコーダは、図２のエンコーダ２０２のコンポーネントでもよい。エンコーダは、ソース画像を１個以上の画像データのブロック、例えば、４×４又は８×８のサイズのブロックに区分化できる。その他の画像データのグループ分けが使用されてもよい。
[0048]図３を参照すると、変換ユニット３０２は、画像データのブロック３０１を係数３０３の集合に変換する。一実施形態では、変換ユニット３０２は、離散コサイン変換（ＤＣＴ）を実施できる。量子化器３０４は、係数３０３を量子化された係数３０５の集合に変換する。一実施形態では、係数は実数値をとり、量子化された係数３０５のうちの１個の値は整数に制限される。一実施形態では、量子化器３０４は、所定の数によって各係数を除算し、結果を最も近い整数に丸め、量子化された係数を生成する。係数エンコーダ３０６は、量子化された係数３０５をビットストリーム３０７に変換する。一実施形態では、ビットストリーム３０７は、量子化された係数３０５の表現を含むビットの順序付き集合である。一実施形態では、係数エンコーダ３０６はハフマン符号化を使用する。代替的に、係数エンコーダ３０６は、算術符号化を、単独で又はハフマン符号化と併せて使用する。その他のコード化スキームもまた同様に使用できる。
[0049]本明細書における目的のため、ツリーを記述する用語は以下の通り使用される。図４は二分木の例である。図４を参照すると、ツリーは、５個のノードＡ、Ｂ、Ｃ、Ｄ及びＥを収容している。ノードＡはルートノードである。ノードＤ及びＥは、本明細書では、Ｃの子ノードと呼ばれる。ノードＤはリーフノードの例である。リーフノードは子ノードを所有しない。ノードＢ及びＥもまたリーフノードである。
[0050]以降の記載は二分木を考慮するが、二分木以外のツリー（例えば、三分木）も同様に使用される。
[0051]図１７は、ツリー構造データの例である。図１７を参照すると、ツリー構造データは、ノードタイプデータ１７０１及びリーフインデックスデータ１７０２を収容してもよい。ノードタイプデータ１７０１は、図４の二分木のようなツリー中の各ノードのノードタイプを収容する。例えば、値０はリーフノードではないノードに対し使用されてもよく、値１はリーフノードであるノードに対し使用される。一実施形態では、ノードタイプの順序付けは、ツリーの深さ優先トラバースによって決定される。代替的に、幅優先トラバースが使用される。リーフインデックスデータ１７０２はツリー中のリーフ毎に係数インデックスを収容する。ツリーのリーフにおけるインデックスは、量子化された係数の配列へのインデックスを表現する。一実施形態では、リーフインデックスの順序付けは、ツリーの深さ優先トラバースによって決定できる。代替的に、幅優先トラバースが考慮される。図１７の例では、図４に描かれたツリーが記述され、ノードＢはインデックス０を、ノードＤはインデックス２を、ノードＥはインデックス１を有することを仮定している。
[0052]図５は、係数エンコーダの一実施形態のブロック図である。図５を参照すると、ツリー生成器５０２は、量子化された係数５０１を受信し、メモリ５１０からツリー構造データ５０６を取り出す。ツリー構造データ５０６は、二分木を記述する。一実施形態では、ツリー構造データ５０６は、ツリーのトポロジーに関係する情報と、ならびに、ツリー中の各リーフのインデックスとを含む。ツリー生成器５０２は、値をツリーの各ノードに割り当てる。最初に、ツリー生成器５０２は、ツリーの各リーフに、対応する量子化された係数がゼロと一致するならば、ゼロ値を割り当てる。そうでなければ、ツリー生成器５０２は非ゼロ値をリーフに割り当てる。次に、値が、ツリー中のリーフではない各ノードに再帰的に割り当てられる。このようなノードはそれぞれが２個の子を保有する。両方の子が値ゼロを有するならば、ゼロ値がノードに割り当てられる。そうでなければ、ツリー生成器５０２は非ゼロ値をノードに割り当てる。ノードに値が割り当てられているツリー５０３は、エントロピーエンコーダ５０４へ送信される。
[0053]エントロピーエンコーダ５０４は、ツリー生成器５０２からのツリー５０３と量子化された係数５０１とを受信する。エントロピーエンコーダ５０４は、メモリ５１０からツリー構造データ５０６をさらに受信する。エントロピーエンコーダ５０４は、さらに後述されるように、ツリー５０３のノードに割り当てられた値を符号化する。その後、非ゼロである量子化された係数毎に、エントロピーエンコーダ５０４は量子化された係数の値を符号化する。一実施形態では、ツリー及び係数の符号化は、ハフマン符号化を使用して実行される。別の実施形態では、算術符号化が使用されるが、どのようなコード化スキームが使用されてもよい。エントロピーエンコーダ５０４の出力は、コード化された情報を収容するビットストリーム５０５である。
[0054]選択的に、エントロピーエンコーダ５０４は、メモリ５１０から取り出されたビットストリーム５０５にツリー構造データを挿入してもよい。一実施形態では、ツリー構造データは、符号化された形式のビットストリームと共に挿入される。ノードタイプ情報は、１ノード当たり１ビットずつで符号化されてもよく、ノードがリーフであるか否かを示す。リーフインデックスに関する情報は、ツリーのサイズに依存する多数のビットにより符号化されてもよい。例えば、３個のリーフインデックスを伴うツリーは、これらのインデックスを２ビットで符号化可能であり、１６個のリーフインデックスを備えるツリーはこれらのインデックスを４ビットで符号化可能である。一般に、必要なビット数は、ｌｏｇ２（リーフインデックスの個数）におおよそ等しい。ツリー構造データは様々な時点で送信されてもよい。例えば、代替的な実施形態では、ツリー構造データは、１ピクチャー毎に１回ずつ、ピクチャーのグループ毎に１回ずつ、又は、ビデオシーケンス全体について１回ずつ送信されてもよい。
[0055]図６は、係数エンコーダによって実行される符号化プロセスの一実施形態のフローチャートである。プロセスは、ハードウェア（例えば、回路、専用ロジックなど）、（汎用コンピュータシステム又は専用機械上で動かされるような）ソフトウェア、又は、両方の組み合わせを備えてもよい、係数エンコーダのプロセッシングロジックによって実行される。プロセッシングロジックはファームウェアを備えてもよい。
[0056]図６を参照すると、プロセスは、プロセッシングロジックが、例えば、量子化器から量子化された係数を受信することによって開始する（処理ブロック６０１）。プロセッシングロジックは、その後、係数の全部がゼロであるか否かをテストする（処理ブロック６０２）。全係数がゼロであるならば、フラグは全係数がゼロであることを示し、プロセスは終了する。そうでなければ、プロセッシングロジックは、ブロック中の少なくとも１個の係数がゼロに等しくないということを特定するフラグを符号化し（処理ブロック６０４）、メモリからツリー構造データを取り出し（処理ブロック６０５）、さらに後述されるように、量子化された係数に基づいてツリー内の各ノードに値を割り当てる（処理６０６）。換言すると、プロセッシングロジックはツリーノード値を生成する。
[0057]ツリーノード値を生成した後、プロセッシングロジックは、さらに後述されるように、ツリー内の各ノードに割り当てられた値を符号化する（処理ブロック６０７）。ツリーを符号化した後、プロセッシングロジックは、非ゼロの量子化された係数の値を符号化する（処理ブロック６０８）。一実施形態では、ハフマン符号化が使用される。代替的に、算術符号化又は別のコード化スキームが使用されてもよい。
[0058]図７は、ツリーのノードの値を割り当てるプロセスの一実施形態のフローチャートである。プロセスは、ハードウェア（例えば、回路、専用ロジックなど）、（汎用コンピュータシステム又は専用機械上で動かされるような）ソフトウェア、又は、両方の組み合わせを備えてもよい、プロセッシングロジックによって実行される。
[0059]プロセスはルートノードに設定された現ノード（以下、カレントノード）で始まる。図７を参照すると、プロセッシングロジックは、カレントノードがリーフノードであるかどうかを判定する（処理ブロック７０１）。カレントノードがリーフノードであるならば、プロセッシングロジックは、カレントノードに関連付けられた量子化された係数がゼロ係数であるかどうかを判定する（処理ブロック７０２）。係数がゼロであるならば、プロセッシングロジックは０という値をカレントノードに割り当て（処理ブロック７０３）、プロセスは終了し、そうでなければ、プロセッシングロジックは１という値をカレントノードに割り当て（処理ブロック７０４）、プロセスは終了する。
[0060]カレントノードがリーフノードでないならば、プロセスは処理ブロック７１０へ移り、プロセッシングロジックが、カレントノードの第１の子をカレントノードとして用いて図７のプロセスを再帰的に実行し（処理ブロック７１０）、その後、カレントノードの第２の子をカレントノードとして用いて再び図７のプロセスを再帰的に実行する（処理ブロック７１１）。
[0061]その後、プロセッシングロジックは、両方の子ノードが０という値を割り当てられているかどうかを判定する（処理ブロック７１２）。両方の子ノードが０という値を保有するならば、プロセッシングロジックは０という値をカレントノードに割り当て（処理ブロック７０３）、プロセスは終了し、そうでなければ、プロセッシングロジックは１という値をカレントノードに割り当て（処理ブロック７０４）、プロセスは終了する。
[0062]カレントノードがルートノードに設定されるプロセスが終了した後、ツリー中の全ノードは０又は１という値が割り当てられている。ルートノードは、１個以上の係数がゼロに等しくないならば、値１を保有する。
[0063]図８は、ツリー中のノードを符号化するプロセスの一実施形態のフローチャートである。プロセスは、ハードウェア（例えば、回路、専用ロジックなど）、（汎用コンピュータシステム又は専用機械上で動かされるような）ソフトウェア、又は、両方の組み合わせを備えてもよい、プロセッシングロジックによって実行される。プロセッシングロジックはファームウェアを備えてもよい。
[0064]図８を参照すると、プロセスは最初にルートノードを引数として用いて呼び出される。プロセスは、プロセッシングロジックがノードはリーフであるかどうかを判定することによって開始する（処理ブロック８０１）。ノードがリーフであるならば、プロセッシングロジックは、そのノードの対応する係数の値を符号化し（処理ブロック８０２）、プロセスは終了する。種々の符号化スキーム（例えば、ハフマン符号化、算術符号化など）が使用されてもよい。
[0065]ノードがリーフでないならば、プロセッシングロジックはノードの２個の子の値を符号化する（処理ブロック８０３）。符号化はさらに後述されている。その後、プロセッシングロジックは第１の子が１という値を保有するかどうかをテストする（処理ブロック８０４）。第１の子が値１を保有するならば、処理ブロックは、第１の子を引数として用いてノード符号化プロセスを再帰的に実行する（処理ブロック８０６）。プロセッシングロジックは、その後、第２の子の値が１であるかどうかをテストする（処理ブロック８０７）。第１の子が値０を保有するか、又は、第２の子が値１を有するならば、プロセッシングロジックは、第２の子を引数として用いてノード符号化プロセスを再帰的に実行する（処理ブロック８０５）。その後、プロセスは終了する。
[0066]図９は、子ノードの値を符号化するプロセスの一実施形態のフローチャートである。プロセスは、ハードウェア（例えば、回路、専用ロジックなど）、（汎用コンピュータシステム又は専用機械上で動かされるような）ソフトウェア、又は、両方の組み合わせを備えてもよい、プロセッシングロジックによって実行される。プロセッシングロジックはファームウェアを備えてもよい。
[0067]図９を参照すると、プロセスは、プロセッシングロジックが第１の子の値を符号化することによって開始する（処理ブロック９０１）。一実施形態では、値はビットストリームに付加される単一ビットとして符号化される。代替的に、値は算術符号化器を使用してさらに圧縮される。
[0068]プロセッシングロジックは、その後、第１の子の値が１であるかどうかを決定する（処理ブロック９０２）。第１の子の値が０に等しいならば、プロセスは終了する。そうでなければ、プロセッシングロジックは第２の子の値を符号化する（処理ブロック９０３）。一実施形態では、値はビットストリームに付加される単一ビットとして符号化される。代替的に、値は算術符号化器を使用してさらに圧縮される。第２の子の値を符号化した後、プロセスは終了する。
[0069]図１０は、子ノードの値を符号化するプロセスの別の実施形態のフローチャートである。これは図９に記載されたプロセスへの代替的な実施形態であることに留意されたい。代替的に、方法の選択はノードに基づいて行われてもよい。選択情報は、メモリに格納され、ビットストリームに符号化されてもよい。このような符号化は選択された方法を示すためにビットを使用して行われてもよい。代替的に、エンコーダ及びデコーダの両方が、ノード毎にどの方法を使用すべきであるかに関する所定の引数を保有してもよい。
[0070]図１０のプロセスは、ハードウェア（例えば、回路、専用ロジックなど）、（汎用コンピュータシステム又は専用機械上で動かされるような）ソフトウェア、又は、両方の組み合わせを備えてもよいプロセッシングロジックによって実行される。プロセッシングロジックはファームウェアを備えてもよい。
[0071]図１０を参照すると、プロセスは、プロセッシングロジックが２個の子ノードの結合された値を符号化することにより開始する（処理ブロック１００１）。一実施形態では、結合された値は、両方の子の値の間の論理ＡＮＤ演算の結果によって決定される。プロセッシングロジックは、次に、両方の子が１という値を保有するかどうかを判定する（処理ブロック１００３）。コード化された値が１であるならば、プロセスは終了する。そうでなければ、プロセッシングロジックは第１の子の値を符号化し（処理ブロック１００４）、プロセスは終了する。一実施形態では、値を符号化するとき、値はビットストリームにそのままで付加される。代替的に、値は算術符号化器を使用してさらに圧縮されてもよい。
[0072]代替的に、三つ組のアルファベットが子ノードの値を表現するために使用されてもよい。このような場合、単一記号がビットストリームに付加される。
[0073]図１１は、変換デコーダの一実施形態のブロック図である。図１１を参照すると、ビットストリーム１１２０が係数デコーダ１１１０に入力されている。係数デコーダ１１１０は、ビットストリーム１１２０からのビットを量子化された係数１１１１の集合に変換する。変換プロセスはさらに後述されている。逆量子化器１１０１は、量子化された係数１１１１を係数１１０２の集合にスケール変換する。逆変換１１０３は、係数１１０２を再構成画像データ１１０４に変換する。
[0074]図１２は、係数デコーダの一実施形態のブロック図である。図１２を参照すると、エントロピーデコーダ１２０２は、さらに後述されているように、ビットストリーム１２０１からのビットを量子化された係数１２０３の集合に変換する。このため、エントロピーデコーダ１２０２は、メモリ１２１０に格納されているツリー構造データに依存する。エントロピーデコーダ１２０２は、ビットストリーム１２０１からツリー構造データを読み、メモリ１２１０に格納してもよい。
[0075]図１３は、量子化された係数を復号化するプロセスの一実施形態のフローチャートである。プロセスは、ハードウェア（例えば、回路、専用ロジックなど）、（汎用コンピュータシステム又は専用機械上で動かされるような）ソフトウェア、又は、両方の組み合わせを備えてもよい、プロセッシングロジックによって実行される。プロセッシングロジックはファームウェアを備えてもよい。
[0076]図１３を参照すると、プロセスは、プロセッシングロジックが集合中の全係数をゼロに設定することによって開始する（処理ブロック１３０１）。係数をゼロに設定した後、プロセッシングロジックはフラグを復号化する（処理ブロック１３０２）。プロセッシングロジックは、その後、全係数がゼロであるかどうかを判定する（処理ブロック１３０３）。全係数がゼロであることを示す第１の値をフラグがとるならば、プロセスは終了する。そうでなければ、プロセッシングロジックは、さらに後述されるように、ツリー中のノード値を復号化し（処理ブロック１３０４）、同様に係数値を復号化する（処理ブロック１３０５）。その後、プロセスは終了する。
[0077]図１４は、ノードを復号化するプロセスの一実施形態のフローチャートである。プロセスは、ハードウェア（例えば、回路、専用ロジックなど）、（汎用コンピュータシステム又は専用機械上で動かされるような）ソフトウェア、又は、両方の組み合わせを備えてもよい、プロセッシングロジックによって実行される。プロセッシングロジックはファームウェアを備えてもよい。
[0078]図１４を参照すると、プロセスはルートノードを引数として用いて開始する。プロセッシングロジックはノードがリーフであるかどうかを判定する（処理ブロック１４０１）。ノードがリーフノードであるならば、プロセッシングロジックは係数の値をさらに復号化し（処理ブロック１４０２）、その後にプロセスが終了する。復号化は種々の復号化技術（例えば、ハフマン符号化、算術符号化など）を使用して実行されてもよい。
[0079]ノードがリーフでないならば、プロセッシングロジックはそのノードの２個の子の値を復号化する（処理ブロック１４０３）。復号化はさらに後述されている。その後、プロセッシングロジックは、第１の子が１という値を保有するかどうかをテストする（処理ブロック１４０４）。第１の子が値１を保有するならば、処理ブロックは、第１の子を引数として用いてノード復号化プロセスを再帰的に実行する（処理ブロック１４０６）。プロセッシングロジックは、その後、第２の子が値１を保有するかどうかをテストする（処理ブロック１４０７）。第１の子が値０を保有するか、又は、第２の子が値１を保有するならば、プロセッシングロジックは、第２の子を引数として用いてノード復号化プロセスを再帰的に実行する（処理ブロック１４０５）。その後、プロセスは終了する。
[0080]図１５は、子ノードの値を復号化するプロセスの一実施形態のフローチャートである。プロセスは、ハードウェア（例えば、回路、専用ロジックなど）、（汎用コンピュータシステム又は専用機械上で動かされるような）ソフトウェア、又は、両方の組み合わせを備えてもよい、プロセッシングロジックによって実行される。プロセッシングロジックはファームウェアを備えてもよい。
[0081]図１５を参照すると、プロセスは第１の子の値を復号化することによって開始する（処理ブロック１５０１）。復号化プロセスは、ビットストリームから単一ビットを取り出すこと、又は、算術デコーダを用いてビットストリームからバイナリ記号を復号化することを伴ってもよい。プロセッシングロジックは、第１の子の値が１であるかどうかを判定する（処理ブロック１５０２）。復号化された値が０であるならば、プロセスは終了し、そうではなく、値が１であるならば、プロセッシングロジックは、第１の値と同様に、第２の子の値を復号化し（処理ブロック１５０３）、その後、プロセスは終了する。
[0082]図１６は、子ノードの値を復号化するプロセスの代替的な実施形態のフローチャートである。プロセスは、ハードウェア（例えば、回路、専用ロジックなど）、（汎用コンピュータシステム又は専用機械上で動かされるような）ソフトウェア、又は、両方の組み合わせを備えてもよい、プロセッシングロジックによって実行される。プロセッシングロジックはファームウェアを備えてもよい。
[0083]図１６を参照すると、プロセスは両方の子の結合された値を復号化して開始する（処理ブロック１６０１）。結合された値は、両方の子が値１を保有するかどうかを示すことができる。プロセッシングロジックは、両方の子が１という値を保有するかどうかを判定する（処理ブロック１６０２）。両方の子が１という値を保有するならば、プロセスは終了し、そうではなく、値が１であるならば、プロセッシングロジックは第１の子の値を復号化し、第２の子の値を反対の値に設定し（処理ブロック１６０３）、その後、プロセスは終了する。
[0084]代替的に、両方の子の値は三つ組のアルファベットを用いて表現される。このような場合、単一記号が子ノードの値を取得するために復号化されてもよい。
[0085]図１８は量子化された係数を復号化するプロセスの一実施形態のフローチャートである。プロセスは、ハードウェア（例えば、回路、専用ロジックなど）、（汎用コンピュータシステム又は専用機械上で動かされるような）ソフトウェア、又は、両方の組み合わせを備えてもよい、プロセッシングロジックによって実行される。プロセッシングロジックはファームウェアを備えてもよい。
[0086]図１８を参照すると、プロセスは、プロセッシングロジックが状態を１に設定し、スタックを空状態に初期化することにより開始する（処理ブロック１８０１）。その後、プロセッシングロジックはメモリからノードタイプを取り出す（処理ブロック１８０２）。プロセッシングロジックは、その後、ノードがリーフノードであるかどうかを判定する（処理ブロック１８０３）。ノードタイプがリーフノードであることを示すならば、処理は処理ブロック１８２０へ移り、そうでなければ、処理は処理ブロック１８１０へ移る。
[0087]処理ブロック１８２０において、プロセッシングロジックはメモリからリーフインデックスＩを取り出し、状態が値０を有するかどうかをテストする（処理ブロック１８２１）。状態が値０を有するならば、処理は処理ブロック１８２３へ移り、プロセッシングロジックはインデックスＩをもつ係数に値０を割り当て、その後、処理は処理ブロック１８２４へ移る。状態が値１を有するならば、処理は処理ブロック１８２２へ移り、プロセッシングロジックはビットストリームから係数値を復号化し、インデックスＩをもつ係数に復号化された係数値を割り当て、その後、処理は処理ブロック１８２４へ移る。
[0088]処理ブロック１８２４において、プロセッシングロジックは、スタックが空であるかどうかを判定する。スタックが空であるならば、プロセスは終了する。スタックが空でなければ、処理は処理ブロック１８２５へ移り、プロセッシングロジックはスタックから値をポップし、状態をその値に設定する。その後、処理は処理ブロック１８０２へ移る。
[0089]ノードがリーフノードでないならば（処理ブロック１８０３）、プロセッシングロジックは状態が１に等しいかどうかを判定する（処理ブロック１８１０）。そうでなければ（すなわち、値が０であるならば）、プロセッシングロジックは２個のノードの値をゼロに設定し、処理ブロック１８１４へ移る。状態が１に等しければ、プロセッシングロジックはビットストリームから２個のノード値を復号化する（処理ブロック１８１２）。ノード値を復号化する方法の例は、図１５及び１６に記載されている。２個のノード値を復号化した後、プロセッシングロジックは状態を第１のノード値に設定し（処理ブロック１８１３）、処理ブロック１８１４へ移る。処理ブロック１８１４において、プロセッシングロジックは第２のノード値をスタックへプッシュする。その後、処理は処理ブロック１８０２へ移る。
[0090]図１９は、係数デコーダの一実施形態のブロック図である。図１９を参照すると、係数デコーダは状態レジスタ１９２０を含む。一実施形態では、状態レジスタ１９２０は最初に値１に設定される。エントロピーデコーダ１９０２は、ノードタイプメモリ１９２３からノードタイプを取り出す。ノードタイプメモリ１９２３は、図４に記載されているように、ツリーの構造に関するデータを収容する。ノードタイプがリーフノードを示し、状態レジスタの値が１であるならば、エントロピーデコーダ１９０２はビットストリームから量子化された係数を復号化し、それを選択器１９０３へ送信する。選択器１９０３は、量子化された係数を選択し、それを係数メモリ１９０４へ送信する。係数メモリ１９０４へのインデックスは、リーフインデックスメモリ１９２１から取り出されたリーフインデックスによって決定される。そうではなく、状態レジスタ１９２０が０であるならば、選択器１９０３は値０を選択し、それを係数メモリ１９０４へ送信する。量子化された係数が量子化された係数メモリ１９０４に格納された後、値がスタック１９２２からポップされ、状態レジスタ１９２０に割り当てられる。そうでなく、ノードタイプがリーフノードを示さないならば、係数デコーダは以下の通り動作する。状態レジスタ１９２０が１であるならば、エントロピーデコーダ１９０２は、例えば、図１５及び１６に記載されているように、ビットストリーム１９０１から２個のノード値を復号化する。第１のノード値はエントロピーデコーダ１９０２によって状態レジスタ１９２０に割り当てられ、第２のノード値はエントロピーデコーダ１９０２によってスタック１９２２へプッシュされる。そうではなく、状態レジスタ１９２０が０であるならば、状態レジスタ１９２０の内容がスタックへプッシュされる。
[0091]一実施形態では、デコーダは、量子化された係数メモリ内の全ての量子化された係数に値が割り当てられるまで、この方式で動作する。量子化された係数メモリの内容は、その後、量子化された係数の順序付き集合として出力される。
[0092]上述のように、本明細書に記載された技術は任意のデータのベクトルに適用されてもよい。例えば、これらの技術は、前方向動きベクトルに対応する水平移動及び垂直移動と後方向動きベクトルに対応する水平移動及び垂直移動とを有するデータのブロックを含む次元４のベクトルをコード化するためにｂフレームをビデオコード化するときに使用されてもよい。この場合、本明細書に記載された技術は、ゼロでない方を示すために使用されてもよい。
（コードの例）
[0093]以下のサンプルＣコードは、本発明に記載されているような係数を復号化するために使用できる。ツリーの深さ優先トラバース及び幅優先トラバースの例が提供されている。
Figure 2012135017
Figure 2012135017
[0094]適切なツリー構造データは、係数ブロックの集合から導出できる。以下のサンプルＣコードは、係数の各組み合わせが非ゼロであることを頻度を用いて示す統計量の集合からツリー構造データを構築する。
Figure 2012135017
Figure 2012135017
Figure 2012135017
Figure 2012135017
Figure 2012135017
Figure 2012135017
（典型的なコンピュータシステム）
[0095]図２０は、本明細書に記載された１個以上の演算を実行できる典型的なコンピュータシステムのブロック図である。コンピュータシステム２０００は、典型的なクライアント又はサーバーコンピュータシステムを備えてもよい。コンピュータシステムに関して記述されたコンポーネントは、ハンドヘルド機器又はモバイル機器（例えば、携帯電話機）の一部であってもよい。
[0096]図２０を参照すると、コンピュータシステム２０００は、情報を通信する通信メカニズム又はバス２０１１と、バス２０１１と接続され情報を処理するプロセッサ２０１２とを備える。プロセッサ２０１２は、マイクロプロセッサを含むが、例えば、Ｐｅｎｔｉｕｍ（登録商標）プロセッサなどのようなマイクロプロセッサに限定されない。
[0097]システム２０００は、バス２０１１に接続され、情報とプロセッサ２０１２によって実行されるべき命令とを格納する、ランダムアクセスメモリ（ＲＡＭ）又はその他のダイナミック記憶装置２００４（メインメモリとして参照される）を、さらに備える。メインメモリ２００４はまた、プロセッサ２０１２による命令の実行中に、一時変数又はその他の中間情報を格納するためにも使用できる。
[0098]コンピュータシステム２０００は、バス２０１１に接続され、スタティック情報及びプロセッサ２０１２のための命令を格納するリードオンリーメモリ（ＲＯＭ）及び／又はその他のスタティック記憶装置２００６と、磁気ディスク又は光ディスク、及び、それに対応するディスクドライブのようなデータ記憶装置２００７とを、さらに備える。データ記憶装置２００７は、バス２０１１に接続され、情報及び命令を格納する。
[0099]コンピュータシステム２０００は、バス２０１１に接続され、情報をコンピュータユーザへ表示する陰極線管（ＣＲＴ）又は液晶ディスプレイ（ＬＣＤ）のようなディスプレイ機器２０２１に、さらに接続されてもよい。英数字キー及びその他のキーを含む英数字入力機器２０２２は、同様にバス２０１１に接続され、情報及びコマンド選択をプロセッサ２０１２へ通信できる。付加的なユーザ入力機器は、カーソル制御機器２０２３である。このカーソル制御機器２０２３は、例えばマウス、トラックボール、トラックパッド、スタイラス、又は、カーソル方向キーである。カーソル制御機器２０２３は、方向情報及びコマンド選択をプロセッサ２０１２へ通信し、ディスプレイ２０２１上のカーソル移動を制御するために、バス２０１１に接続されている。
[00100]バス２０１１に接続できる別の機器は、ハードコピー機器２０２４である。ハードコピー機器２０２４は、紙、フィルム、又は、類似したタイプの媒体のような媒体上に情報を残すために使用できる。バス２０１１に接続できる別の機器は、電話機又はハンドヘルドパーム機器へ通信するための有線／無線通信機能部２０２５である。
[00101]システム２０００のコンポーネント、及び、関連したハードウェアの何れか又は全部が本発明において使用できることに留意されたい。しかし、コンピュータシステムのその他の構成は、機器の一部又は全部を含んでもよいことが認められるであろう。
[00102]以上の説明を読んだ後に、本発明の多数の代替及び変形が当業者に明白になることは確実であるが、説明のために図示され記載された特定の実施形態が制限的であるとみなされることは決して意図されていないことが理解されるべきである。したがって、種々の実施形態の詳細への言及は、本発明に不可欠であると考えられる構成要件だけをそれ自体に列挙する請求項の範囲を制限することを意図していない。

Claims (6)

  1. データのベクトル中のデータを、ツリーデータ構造を使用して特定された前記データがゼロであるか又は非ゼロであるかの指標に基づいてコード化するデータコード化ステップと、
    コード化されたデータに基づいてビットストリームを作成するビットストリーム作成ステップと、
    を備える方法。
  2. データのベクトルを受信する入力と、
    前記入力に接続され、前記データのベクトル中のデータを、ツリーデータ構造を使用して特定された前記データがゼロであるか又は非ゼロであるかの指標に基づいてコード化する、エントロピーエンコーダと、
    を備える、係数を符号化する装置。
  3. システムによって実行されたとき、前記システムに、
    データのベクトル中のデータを、ツリーデータ構造を使用して特定された前記データがゼロであるか又は非ゼロであるかの指標に基づいてコード化するデータコード化ステップと、
    コード化されたデータに基づいてビットストリームを作成するビットストリーム作成ステップと、
    を備える方法を実行させる命令を記憶する１つ以上の記録可能な媒体を有する製品。
  4. ビットストリームを受信するビットストリーム受信ステップと、
    復号化されたデータのベクトルを、ツリーデータ構造によって特定されるような前記データがゼロであるか又は非ゼロであるかの指標に基づいて作成するため、前記ビットストリームを復号化するビットストリーム復号化ステップと、
    を備える方法。
  5. ビットストリームを受信する入力と、
    前記入力に接続され、復号化されたデータのベクトルを、ツリーデータ構造によって特定されるような前記データがゼロであるか又は非ゼロであるかの指標に基づいて作成する、エントロピーデコーダと、
    を備える、量子化された係数を復号化する装置。
  6. システムによって実行されたとき、前記システムに、
    復号化されたデータのベクトルを、ツリーデータ構造によって特定されるような前記データがゼロであるか又は非ゼロであるかの指標に基づいて作成するため、ビットストリームを復号化するビットストリーム復号化ステップを備える方法を実行させる命令を記憶する１つ以上の記録可能な媒体を有する製品。
JP2012032861A 2004-12-22 2012-02-17 係数の位置をコード化する方法及び装置 Expired - Lifetime JP5579760B2 (ja)

Applications Claiming Priority (4)

Application Number Priority Date Filing Date Title
US63943004P 2004-12-22 2004-12-22
US60/639,430 2004-12-22
US11/172,052 US7660475B2 (en) 2004-12-22 2005-06-29 Method and apparatus for coding positions of coefficients
US11/172,052 2005-06-29

Related Parent Applications (1)

Application Number Title Priority Date Filing Date
JP2010161644A Division JP2011004406A (ja) 2004-12-22 2010-07-16 係数の位置をコード化する方法及び装置

Publications (2)

Publication Number Publication Date
JP2012135017A true JP2012135017A (ja) 2012-07-12
JP5579760B2 JP5579760B2 (ja) 2014-08-27

Family

ID=36091601

Family Applications (3)

Application Number Title Priority Date Filing Date
JP2007548335A Pending JP2008530829A (ja) 2004-12-22 2005-12-15 係数の位置をコード化する方法及び装置
JP2010161644A Pending JP2011004406A (ja) 2004-12-22 2010-07-16 係数の位置をコード化する方法及び装置
JP2012032861A Expired - Lifetime JP5579760B2 (ja) 2004-12-22 2012-02-17 係数の位置をコード化する方法及び装置

Family Applications Before (2)

Application Number Title Priority Date Filing Date
JP2007548335A Pending JP2008530829A (ja) 2004-12-22 2005-12-15 係数の位置をコード化する方法及び装置
JP2010161644A Pending JP2011004406A (ja) 2004-12-22 2010-07-16 係数の位置をコード化する方法及び装置

Country Status (3)

Country Link
US (2) US7660475B2 (ja)
JP (3) JP2008530829A (ja)
WO (1) WO2006068957A1 (ja)

Cited By (5)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
WO2018123314A1 (ja) * 2016-12-26 2018-07-05 日本電気株式会社 映像符号化方法、映像復号方法、映像符号化装置、映像復号装置及びプログラム
WO2018123316A1 (ja) * 2016-12-26 2018-07-05 日本電気株式会社 映像符号化方法、映像復号方法、映像符号化装置、映像復号装置及びプログラム
WO2018123313A1 (ja) * 2016-12-26 2018-07-05 日本電気株式会社 映像符号化方法、映像復号方法、映像符号化装置、映像復号装置及びプログラム
WO2018123312A1 (ja) * 2016-12-26 2018-07-05 日本電気株式会社 映像符号化方法、映像復号方法、映像符号化装置、映像復号装置及びプログラム
WO2018123317A1 (ja) * 2016-12-26 2018-07-05 日本電気株式会社 映像符号化方法、映像復号方法、映像符号化装置、映像復号装置及びプログラム

Families Citing this family (25)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US7660475B2 (en) * 2004-12-22 2010-02-09 Ntt Docomo, Inc. Method and apparatus for coding positions of coefficients
US7716250B1 (en) * 2005-05-27 2010-05-11 Microsoft Corporation Erasure coding and group computations using rooted binary and ternary trees
US8515996B2 (en) * 2008-05-19 2013-08-20 Emulex Design & Manufacturing Corporation Secure configuration of authentication servers
US7872993B2 (en) * 2008-10-30 2011-01-18 Alcatel Lucent Method and system for classifying data packets
CN102246525A (zh) * 2008-12-16 2011-11-16 松下电器产业株式会社 运动图像编码方法、运动图像解码方法、运动图像编码装置、运动图像解码装置、程序、及集成电路
US8107750B2 (en) * 2008-12-31 2012-01-31 Stmicroelectronics S.R.L. Method of generating motion vectors of images of a video sequence
JP5001964B2 (ja) 2009-02-18 2012-08-15 株式会社エヌ・ティ・ティ・ドコモ 画像符号化装置、方法およびプログラム、並びに、画像復号装置、方法およびプログラム
JP5258664B2 (ja) 2009-04-14 2013-08-07 株式会社エヌ・ティ・ティ・ドコモ 画像符号化装置、方法およびプログラム、並びに、画像復号装置、方法およびプログラム
US8620098B2 (en) * 2009-06-09 2013-12-31 Sony Corporation Trees for adaptive coding of images and videos using set partitioning in generalized hierarchical trees having directionality
US8406546B2 (en) * 2009-06-09 2013-03-26 Sony Corporation Adaptive entropy coding for images and videos using set partitioning in generalized hierarchical trees
KR102683408B1 (ko) 2009-07-02 2024-07-10 인터디지털 브이씨 홀딩스 인코포레이티드 적응적 트리 선택을 사용한 이진 집합의 비디오 인코딩 및 디코딩을 위한 방법 및 장치
KR101739603B1 (ko) * 2009-08-20 2017-05-24 톰슨 라이센싱 2진 세트들을 인코딩 및 디코딩하기 위해 트리 구조들을 재이용하는 방법 및 장치
KR101703327B1 (ko) 2010-01-14 2017-02-06 삼성전자 주식회사 계층적 데이터 단위의 패턴 정보를 이용하는 비디오 부호화 방법과 그 장치, 및 비디오 복호화 방법과 그 장치
WO2011129052A1 (ja) * 2010-04-13 2011-10-20 パナソニック株式会社 画像復号装置、画像符号化装置、画像復号方法および画像符号化方法
KR20120009618A (ko) 2010-07-19 2012-02-02 에스케이 텔레콤주식회사 주파수변환단위 분할부호화 방법 및 장치와 이를 이용한 영상 부호화/복호화 방법 및 장치
KR20120035096A (ko) * 2010-10-04 2012-04-13 한국전자통신연구원 쿼드 트리 변환 구조에서 부가 정보의 시그널링 방법 및 장치
CN101990104A (zh) * 2010-11-17 2011-03-23 中兴通讯股份有限公司 视频图像编码方法及装置
ITVI20120087A1 (it) 2012-04-17 2013-10-18 St Microelectronics Srl Stabilizzazione video digitale
US9628107B2 (en) 2014-04-07 2017-04-18 International Business Machines Corporation Compression of floating-point data by identifying a previous loss of precision
US9959299B2 (en) 2014-12-02 2018-05-01 International Business Machines Corporation Compression-aware partial sort of streaming columnar data
US10909078B2 (en) 2015-02-25 2021-02-02 International Business Machines Corporation Query predicate evaluation and computation for hierarchically compressed data
CN109151477B (zh) * 2017-06-28 2020-08-07 华为技术有限公司 一种图像数据的编码、解码方法及装置
US10484695B2 (en) 2017-10-23 2019-11-19 Google Llc Refined entropy coding for level maps
US10645381B2 (en) 2018-04-30 2020-05-05 Google Llc Intra-prediction for smooth blocks in image/video
CN109982086B (zh) * 2019-04-10 2020-12-08 上海兆芯集成电路有限公司 图像压缩方法及其装置

Citations (1)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JPH11191153A (ja) * 1997-12-26 1999-07-13 Ricoh Co Ltd ウェーブレット変換係数の符号化方法

Family Cites Families (16)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US5263124A (en) * 1991-02-27 1993-11-16 Neural Systems Corporation Method for producing a binary tree, pattern recognition and binary vector classification method using binary trees, and system for classifying binary vectors
US5274718A (en) * 1991-09-30 1993-12-28 At&T Bell Laboratories Image representation using tree-like structures
US5335088A (en) * 1992-04-01 1994-08-02 Xerox Corporation Apparatus and method for encoding halftone images
US5379355A (en) * 1992-08-24 1995-01-03 Ricoh Corporation Data encoding using one or more adaptive decision trees
US5550541A (en) * 1994-04-01 1996-08-27 Dolby Laboratories Licensing Corporation Compact source coding tables for encoder/decoder system
JP3278297B2 (ja) * 1994-07-20 2002-04-30 富士通株式会社 データ圧縮方法及びデータ復元方法並びにデータ圧縮装置及びデータ復元装置
DE69734386D1 (de) * 1997-02-06 2006-03-02 St Microelectronics Srl Verfahren zur Speicherungsverringerung in einem Videodekodierer
US6157746A (en) * 1997-02-12 2000-12-05 Sarnoff Corporation Apparatus and method for encoding wavelet trees generated by a wavelet-based coding method
DE69735262D1 (de) * 1997-11-24 2006-04-20 St Microelectronics Srl MPEG-2 Dekodierung mit reduziertem Speicherbedarf durch Rekomprimierung mit adaptiver baumstrukturierter Vektorquantisierung
US6101275A (en) * 1998-01-26 2000-08-08 International Business Machines Corporation Method for finding a best test for a nominal attribute for generating a binary decision tree
US7187804B2 (en) * 2001-01-30 2007-03-06 California Institute Of Technology Lossless and near-lossless source coding for multiple access networks
US7016547B1 (en) * 2002-06-28 2006-03-21 Microsoft Corporation Adaptive entropy encoding/decoding for screen capture content
JP2004297416A (ja) * 2003-03-26 2004-10-21 Monolith Co Ltd 対応点情報圧縮方法および装置
US7286710B2 (en) * 2003-10-01 2007-10-23 Fraunhofer-Gesellschaft Zur Foerderung Der Angewandten Forschung E.V. Coding of a syntax element contained in a pre-coded video signal
US7379608B2 (en) * 2003-12-04 2008-05-27 Fraunhofer-Gesellschaft Zur Foerderung Der Angewandten Forschung, E.V. Arithmetic coding for transforming video and picture data units
US7660475B2 (en) * 2004-12-22 2010-02-09 Ntt Docomo, Inc. Method and apparatus for coding positions of coefficients

Patent Citations (1)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JPH11191153A (ja) * 1997-12-26 1999-07-13 Ricoh Co Ltd ウェーブレット変換係数の符号化方法

Cited By (7)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
WO2018123314A1 (ja) * 2016-12-26 2018-07-05 日本電気株式会社 映像符号化方法、映像復号方法、映像符号化装置、映像復号装置及びプログラム
WO2018123316A1 (ja) * 2016-12-26 2018-07-05 日本電気株式会社 映像符号化方法、映像復号方法、映像符号化装置、映像復号装置及びプログラム
WO2018123313A1 (ja) * 2016-12-26 2018-07-05 日本電気株式会社 映像符号化方法、映像復号方法、映像符号化装置、映像復号装置及びプログラム
WO2018123312A1 (ja) * 2016-12-26 2018-07-05 日本電気株式会社 映像符号化方法、映像復号方法、映像符号化装置、映像復号装置及びプログラム
WO2018123317A1 (ja) * 2016-12-26 2018-07-05 日本電気株式会社 映像符号化方法、映像復号方法、映像符号化装置、映像復号装置及びプログラム
US10536724B2 (en) 2016-12-26 2020-01-14 Nec Corporation Video encoding method, video decoding method, video encoding device, video decoding device, and program
US10542293B2 (en) 2016-12-26 2020-01-21 Nec Corporation Video encoding method, video decoding method, video encoding device, video decoding device, and program

Also Published As

Publication number Publication date
JP2011004406A (ja) 2011-01-06
US7920750B2 (en) 2011-04-05
JP2008530829A (ja) 2008-08-07
US20060133680A1 (en) 2006-06-22
JP5579760B2 (ja) 2014-08-27
US20100124381A1 (en) 2010-05-20
US7660475B2 (en) 2010-02-09
WO2006068957A1 (en) 2006-06-29

Similar Documents

Publication Publication Date Title
JP5579760B2 (ja) 係数の位置をコード化する方法及び装置
US5966465A (en) Compression/decompression using reversible embedded wavelets
US7634145B2 (en) Compression and decompression with wavelet style and binary style including quantization by device-dependent parser
US6031940A (en) System and method for efficiently encoding video frame sequences
US7629904B2 (en) Image coding with scalable context quantization
US6757437B1 (en) Compression/decompression using reversible embedded wavelets
US10382789B2 (en) Systems and methods for digital media compression and recompression
JP2006502604A (ja) 任意形状オブジェクトの画像圧縮方法
KR20010095109A (ko) 이미지 처리 장치 및 방법
US5949911A (en) System and method for scalable coding of sparse data sets
JP2007267384A (ja) 圧縮装置及び圧縮方法
KR20240025629A (ko) 광학 흐름를 이용한 비디오 압축
US7463782B2 (en) Data encoding with an amplitude model and path between the data and corresponding decoding
JP2004040248A (ja) 情報処理装置、情報処理方法、プログラム、記憶媒体
WO2006119051A1 (en) Compression and decompression of media data
US7123656B1 (en) Systems and methods for video compression
Bonomini et al. Implementing an MPEG2 Video Decoder Based on TMS320C80 MVP
JP3452115B2 (ja) 画像処理装置
Hema et al. Efficient Compression of Multimedia Data using Lempel–Ziv–Markov Chain Adaptive Block Compressive Sensing (LZMC-ABCS)
JP2001218208A (ja) 画像復号装置及びその方法
Beebe et al. A Bibliography on Data Compression
JPH10215459A (ja) 画像符号化装置および画像復号化装置
JP2004048731A (ja) モディファイドアダマール変換による画像データのプログレッシブ送受信
JP2007134860A (ja) 暗号化プログラムおよび復号化プログラム
JP2001251623A (ja) 画像処理装置、表示装置、システム、それらの制御方法及び記憶媒体

Legal Events

Date Code Title Description
A977 Report on retrieval

Free format text: JAPANESE INTERMEDIATE CODE: A971007

Effective date: 20130531

A131 Notification of reasons for refusal

Free format text: JAPANESE INTERMEDIATE CODE: A131

Effective date: 20130604

A521 Request for written amendment filed

Free format text: JAPANESE INTERMEDIATE CODE: A523

Effective date: 20130801

A131 Notification of reasons for refusal

Free format text: JAPANESE INTERMEDIATE CODE: A131

Effective date: 20140304

A521 Request for written amendment filed

Free format text: JAPANESE INTERMEDIATE CODE: A523

Effective date: 20140507

TRDD Decision of grant or rejection written
A01 Written decision to grant a patent or to grant a registration (utility model)

Free format text: JAPANESE INTERMEDIATE CODE: A01

Effective date: 20140701

A61 First payment of annual fees (during grant procedure)

Free format text: JAPANESE INTERMEDIATE CODE: A61

Effective date: 20140709

R150 Certificate of patent or registration of utility model

Ref document number: 5579760

Country of ref document: JP

Free format text: JAPANESE INTERMEDIATE CODE: R150

R250 Receipt of annual fees

Free format text: JAPANESE INTERMEDIATE CODE: R250

R250 Receipt of annual fees

Free format text: JAPANESE INTERMEDIATE CODE: R250

R250 Receipt of annual fees

Free format text: JAPANESE INTERMEDIATE CODE: R250

R250 Receipt of annual fees

Free format text: JAPANESE INTERMEDIATE CODE: R250

R250 Receipt of annual fees

Free format text: JAPANESE INTERMEDIATE CODE: R250

R250 Receipt of annual fees

Free format text: JAPANESE INTERMEDIATE CODE: R250

R250 Receipt of annual fees

Free format text: JAPANESE INTERMEDIATE CODE: R250

R250 Receipt of annual fees

Free format text: JAPANESE INTERMEDIATE CODE: R250

R250 Receipt of annual fees

Free format text: JAPANESE INTERMEDIATE CODE: R250

EXPY Cancellation because of completion of term