確率推定のための状態マシンを生成する方法、算術エンコーダ、算術デコーダ、及び、復号方法
【課題】符号化アルゴリズム及び復号アルゴリズムの複雑さを低減し、符号化、送信、及び復号を行うデータを減らし、記憶の必要性を緩和するため効率の良い解決手段を提供する。
【解決手段】確率推定用の状態マシンを生成する方法(a)所与の状態の番号をiとし、かつ、適応レートが1より小さいとする場合に、LUTの状態の各状態iに対する確率を、LPSの最大確率に適応レートのi乗を乗算した値に等しくセットし、(b)MPS及びLPSを観察し、遷移れるべきLUTの状態に対して状態遷移を発生する。複数の状態に対しLPSが観察されたときに現在の状態から状態マシンが遷移する次の状態が、現在の状態の番号+log((現在の状態の確率*適応レート+(1−適応レート))/現在の状態の確率)/log(適応レート)の計算結果が丸められた値である。
【解決手段】確率推定用の状態マシンを生成する方法(a)所与の状態の番号をiとし、かつ、適応レートが1より小さいとする場合に、LUTの状態の各状態iに対する確率を、LPSの最大確率に適応レートのi乗を乗算した値に等しくセットし、(b)MPS及びLPSを観察し、遷移れるべきLUTの状態に対して状態遷移を発生する。複数の状態に対しLPSが観察されたときに現在の状態から状態マシンが遷移する次の状態が、現在の状態の番号+log((現在の状態の確率*適応レート+(1−適応レート))/現在の状態の確率)/log(適応レート)の計算結果が丸められた値である。
【発明の詳細な説明】
【版権について】
【0001】
[0001] この特許文書の開示の一部分は、版権保護を受ける資料を含む。版権所有者は、如何なる者が特許文書又は特許開示を特許商標庁の特許ファイル又は記録に残るように複写することに異議を唱えるものではないが、それ以外は、全ての版権権利が保護されるものとする。
【優先権】
【0002】
[0002] 本特許出願は、2002年9月20日に出願された「TERMINATION OF ARITHMETIC CODING AND BYTE STUFFING」と題する対応の仮特許出願第60/412,245号、及び2002年10月4日に出願された「CABAC CLEANUP AND COMPLEXITY REDUCTION」と題する仮特許出願第60/415,000号に対する優先権を主張する。
【技術分野】
【0003】
[0003] 本発明は、広く、情報理論、ビデオ圧縮及び算術符号化に関する。より詳細には、本発明は、バイトスタフィング(byte stuffing)及び算術符号化の終了を行うと共に、算術符号化中に状態マシンを生成して使用する方法及び装置に関する。
【背景技術】
【0004】
[0004] データ圧縮は、大量のデータの記憶及び送信に非常に有用なツールである。例えば、文書のネットワーク送信のような画像の送信に必要な時間は、圧縮を用いて画像の復元に必要なビット数を減少させると、大幅に短縮される。
【0005】
[0005] 先行技術には、多数の異なるデータ圧縮技術が存在する。圧縮技術は、非可逆符号化(lossy coding)及び可逆符号化(losslesscoding)の2つの広いカテゴリーに分類される。非可逆符号化とは、情報のロスを招く符号化であり、オリジナルデータの完全な再構成が保証されない。非可逆圧縮の目標は、オリジナルデータに対する変更を、それが支障のないように又は検出されないように行うことである。可逆圧縮では、完全な再構成が可能な方法でデータが圧縮され、全ての情報が維持される。
【0006】
[0006] 算術符号化は、周知の圧縮技術であり、送信に必要なビット又はシンボルの数を削減するために幾つかのデータ符号化・圧縮システムに使用されている。算術エンコーダは、イベント(例えば、2進イベント)又はシンボルのシーケンスを含む入力を受信する。このエンコーダは、入力シーケンスを符号化して、対応のビット又はバイトシーケンスとする。ある場合には、エンコーダの入力に受信されたものより少数のデータビットをエンコーダの出力に発生させることによって、データを圧縮する。算術デコーダは、符号化データを受信し又はそれにアクセスすることができる。算術デコーダは、符号化データのシーケンスを読み取って、復号データを生成するが、これは、デコーダに受信された入力シンボルに一致しなければならない。圧縮は、符号化されているイベントに対して情報シーケンスに少数のビットを発生させることによって達成される。イベントと、符号化されている情報ビットとの比は、イベントの確率分布にもよるが、64:1又は128:1にも達し得る。
【0007】
[0007] デコーダのオペレーションは、エンコーダのオペレーションと対称であることが好ましい。エンコーダとデコーダのオペレーションが対称であるならば、デコーダで読み取られる符号化データのビット数は、エンコーダによって生成された符号化ビットの数に一致する。
【0008】
[0008] ある算術デコーダでは、復号オペレーションを開始する際に、デコーダがビットのグループを先読みする。しかしながら、デコーダがビットのグループを先読みするので、不一致又は非対称性が生じ得る。
【0009】
[0009] この非対称性を補償するための従来の一解決策では、エンコーダにおいて符号化データに余分なビットを追加している。別の従来の解決策では、追加の符号化ビットを発生させず、デコーダにおいて、符号化データのビットストリームを先読みした後、後戻りさせている。
【発明の概要】
【発明が解決しようとする課題】
【0010】
[0010] これら従来の解決策は、両者ともに、効率が悪い。符号化アルゴリズム及び復号アルゴリズムの複雑さを低減し、符号化、送信、及び復号を行うデータを減らし、更に、記憶の必要性を緩和するために、より効率の良い解決策が要望されている。
【課題を解決するための手段】
【0011】
算術符号化及び/又は算術復号を実行する方法及び装置を開示する。一実施形態において、データ符号化方法は、イベントシーケンスにおける複数のイベントを符号化して、符号化データを生成するステップと、当該符号化データを用いてビットストリームを生成するとともに、当該符号化データの後のビットストリームにゼロ以上のスタフィングビットを追加することを含むステップとを備える。当該ゼロ以上のスタフィングビットは、符号化されたイベントの量と、符号化されているブロックの数と、ビットストリームにおけるビットの数との間の関係を実質的に維持するように機能する。
【0012】
別の実施形態において、算術デコーダは、イベントシーケンスのイベントに対してコンテクスト識別子を生成するシーケンサと、LPSの値及びLPSの確率推定値を決定する確率推定器と、LPSのレンジに値を割り当てるレンジレジスタを含む復号エンジンとを備えている。コンテクスト識別子がインデックスに等しくない場合に、当該値は、LPSの確率推定値と、レンジレジスタに記憶された値と、LPSのレンジへのコンテクスト識別子とに基づき、また、コンテクスト識別子がインデックスに等しい場合に、当該値は、レンジレジスタに記憶された値に基づかない。復号エンジンは、更に、LPSのレンジの値及び情報シーケンスからのビットに基づいて2進イベントの値を決定する。
【0013】
他の実施形態において、確率推定のための状態マシンを生成する方法は、ルックアップテーブル(LUT)の状態に確率を割り当てるステップを含み、このステップは、所与の状態の番号をiとし、かつ、適応レートが1より小さいとする場合に、各状態iに対する確率を、適応レートのi乗が乗算されたLPSの最大確率に等しくセットする処理を含む。この方法は、また、MPS及びLPSを観察して、遷移されるべきLUTの状態に対する状態遷移を発生させるステップを備え、MPSが観察されたときに現在の状態から状態マシンが遷移する次の状態を、当該現在の状態が最も高い状態でない場合に現在の状態より高い次の状態とし、当該現在の状態が最も高い状態である場合に当該現在の状態とする。更に、複数の状態に対しLPSが観察されたときに現在の状態から状態マシンが遷移する次の状態は、
現在の状態の番号+log((現在状の態の確率*適応レート+(1−適応レート))/現在の状態の確率)/log(適応レート)
の計算結果が丸められた値となる。
【0014】
[0011] 本発明は、本発明の種々の実施形態を示す添付図面及び以下の詳細な説明から完全に理解されるであろうが、これは、本発明を特定の実施形態に限定するものではなく、本発明を例示し理解するためのものに過ぎない。
【図面の簡単な説明】
【0015】
【図1】符号化及び復号システムの実施形態のブロック図である。
【図2】ビットストリームを生成するための符号化プロセスのフロー図である。
【図3】図1のシステムにおいて送信することのできる符号化データのデータフォーマットの一例を示す図である。
【図4】算術エンコーダの一実施形態のブロック図である。
【図5】イベントの符号化に関する一実施形態のフロー図である。
【図6】エンコーダ再正規化手順の一実施形態のフロー図である。
【図7】プットビット手順の実施形態を実行するプロセスの一実施形態を示す図である。
【図8】終了前にイベントを復号するプロセスの一実施形態を示すフロー図である。
【図9】終了時のフラッシュに係るプロセスの一実施形態を示すフロー図である。
【図10】算術デコーダの一実施形態を示すブロック図である。
【図11】算術デコーダの初期化プロセスの一実施形態を示すフロー図である。
【図12】2進イベントを復号するプロセスの一実施形態を示すフロー図である。
【図13】再正規化手順のフロー図である。
【図14A】同じ確率で2進イベントを復号するためのフロー図の一つである。
【図14B】同じ確率で2進イベントを復号するためのフロー図の一つである。
【図15A】終了前にスライス終了フラグ又は他の2進イベントを復号する実施形態を示すフロー図の一つである。
【図15B】終了前にスライス終了フラグ又は他の2進イベントを復号する実施形態を示すフロー図の一つである。
【図16A】確率推定ルックアップを実行するためのテーブルの一例である。
【図16B】確率推定ルックアップを実行するためのテーブルの一例である。
【図17】コンピュータシステムの一例を示すブロック図である。
【発明を実施するための形態】
【0016】
[0029] 以下、情報、特にビデオデータを符号化及び復号する方法及び装置について説明する。符号化及び復号中に、算術符号化されているイベントの終了を知らせるために、インジケータ(例えば、スライスの終了)が使用される。一実施形態では、情報の符号化中に、エンコーダによって生成される符号化データのビットストリームに、数ビット又は数バイトのスタフィング情報が追加される。これら追加のビットを符号化データのビットストリームの中間にスタフィングするのではなく、スタフィングバイト(又はビット)を、符号化データの最後に追加する。このようなスタフィングを使用することによって、符号化されているイベントの数と、ビデオデータのブロック(例えばマクロブロック)の数と、生成されている情報シーケンスのサイズとの間の関係を維持することができる。
【0017】
[0030] 以下、本発明をより完全に説明するために多数の細部について述べる。しかしながら、当業者であれば、これら特定の細部がなくとも本発明を実施できることが明らかであろう。他の例では、本発明を不明瞭にしないために、周知の構造及び装置を、詳述する代わりに、ブロック図形態で示す。
【0018】
[0031] 以下の詳細な説明では、コンピュータメモリ内のデータビットに対する操作のアルゴリズム及び記号表示の形で記載している部分がある。これらのアルゴリズム記述及び表示は、データ処理分野の当業者によって、当該当業者の仕事の実体をその分野の他の当事者に最も効果的に伝達するために使用される手段である。アルゴリズムとは、ここにおいても、且つ一般においても、所望の結果を導く自己一貫性のあるステップのシーケンスであると考えられる。ステップとは、物理的な量の物理的な操作を要求するものである。必ずしもそうでないが、通常、これらの量は、記憶、転送、合成、比較、及びその他操作を行うことができる電気的又は磁気的信号の形態をとる。主として一般に使用される理由は、これらの信号を、ビット、値、エレメント、シンボル、キャラクタ、用語、番号等として参照することが時に便利であるとわかっているからである。
【0019】
[0032] しかしながら、これら及び同様の全ての用語は、適切な物理量に関連付けられており、これらの量に適用される単なる便利な表示に過ぎないことに留意されたい。以下の説明から明らかなように、特に指示のない限り、説明全体にわたり、「処理」又は「計算」又は「算出」又は「決定」或いは「表示」等の用語を用いた説明は、コンピュータシステムのレジスタ及びメモリ内の物理(電子)量として表わされたデータを、コンピュータシステムのメモリ又はレジスタ或いは他の情報記憶、送信又は表示装置内の物理的量として同様に表わされた他のデータへと操作及び変換するコンピュータシステム、又は同様の電子計算装置のアクション及びプロセスを指すことは理解されよう。
【0020】
[0033] また、本発明は、本明細書に記載されたオペレーションを実行する装置に関する。この装置は、要求された目的のために特別に構成されてもよく、又はコンピュータ内に記憶されたコンピュータプログラムによって選択的に起動され又は再構成される汎用コンピュータを備えてもよい。このようなコンピュータプログラムは、コンピュータ読み取り可能な記憶媒体、例えば、フロッピーディスク、光学的ディスク、CD−ROM、磁気−光学ディスクを含む任意の形式のディスク、リードオンリメモリ(ROM)、ランダムアクセスメモリ(RAM)、EPROM、EEPROM、磁気又は光学カード、或いは電子的命令の記憶に適した任意の形式の媒体に記憶され得るが、これらに限定されない。これらは各々、コンピュータのシステムバスに接続される。
【0021】
[0034] 本明細書に記載したアルゴリズム及び表示は、特定のコンピュータ又は他の装置に固有に関連するものではない。本明細書の教示に基づくプログラムと共に種々の汎用システムを使用することができ、また、要求の方法のステップを実行するための更に特殊な装置を構成することも便利であることは理解されよう。種々のこれらシステムに必要とされる構造は、以下の説明から明らかとなろう。更に、本発明を、特定のプログラミング言語を参照して説明していない。本明細書に記載された本発明の教示を実施するために、種々のプログラミング言語を使用できることは明らかであろう。
【0022】
[0035] マシン読み取り可能な媒体は、マシン(例えばコンピュータ)で読み取りできる形態で情報を記憶又は転送するためのメカニズムを含む。例えば、マシン読み取り可能な媒体は、リードオンリメモリ(ROM)、ランダムアクセスメモリ(RAM)、磁気ディスク記憶媒体、光学記憶媒体、フラッシュメモリデバイス、電気的、光学的、音響的又は他の形態の伝播信号(例えば、搬送波、赤外線信号、デジタル信号等)、等々を含む。
【0023】
<符号化及び復号システムの概要>
【0024】
[0036] 図1は、符号化及び復号システム100の実施形態のブロック図である。図1に示すように、システム100は、チャンネル120を介して通信するエンコーダ102及びデコーダ104を備えている。これに代えて、システム100は、エンコーダ102又はデコーダ104だけを備えてもよい。
【0025】
[0037] チャンネル120は、有線チャンネル、無線チャンネル又はそれらの組合せを含む相応のデータ通信チャンネルとすることができる。チャンネル120には、適当なデータ通信及び変調機構が使用される。システム100の一例は、画像のシーケンスを含むビデオデータを符号化し、圧縮し、復号するためのシステムである。一実施形態では、各ピクチャーは、一つ以上のスライスに分割される。
【0026】
[0038] エンコーダ102は、入力データ(例えばビデオ情報)といった入力情報を受信する入力106を有する。一実施形態では、エンコーダ102は、算術符号化を使用してデータを符号化する。したがって、エンコーダ102は、データ記憶部、操作レジスタ、及び算術符号化エンジンを備えている。一実施形態では、エンコーダ102は、レンジレジスタ、即ちRレジスタと、ロー(Low)レジスタ、即ちLレジスタとを含む。更に、一実施形態では、エンコーダ102は、確率推定状態マシンを含む。エンコーダ102によって実行される符号化アルゴリズムは、当該技術において周知のコンテクスト適応二値算術符号化であり、本明細書ではCABACと称している。また、本明細書に記載された技術及び構成を、他の符号化及び復号のアルゴリズム並びに手順に拡張することもできる。エンコーダ102は、符号化データをチャンネル120へ供給する出力108を有する。
【0027】
[0039] 一実施形態において、エンコーダ102は、算術符号化データの終了を指示する符号化イベント(例えば、決定(decision))を含む符号化データのビットストリームを生成する。一実施形態において、算術符号化データの終了を示すイベントは、スライス終了フラグを含む。また、ビットストリームは、より詳細には以下に述べるスタフィングバイト(又はビット)を含んでもよい。
【0028】
[0040] デコーダ104は、チャンネル120から符号化データを受信する入力110と、復号データを供給する出力112とを有する。一実施形態において、符号化データを復号するためのデコーダ104のオペレーションは、エンコーダ102の符号化のオペレーションと概ね対称である。尚、システム100は、2つ以上のエンコーダ及び/又は2つ以上のデコーダを備えてもよい。
【0029】
[0041] エンコーダ102及びデコーダ104は、ビデオデータ、例えば、ビデオプロセッサ(例えばビデオコーデック)によって生成されたビデオデータの処理に使用される。一実施形態では、ビデオ画像は、記録され、当該記録された画像の16×16、8×8又は4×4のサンプルを表すデータのサンプルブロックに分割される。これらブロックは、次いで、ビデオプロセッサによって(例えば、離散コサイン変換を使用して)変換、量子化されて、サンプルブロックを表す整数値が得られる。これら整数値は、ビデオプロセッサによってイベント(例えば2進イベント)のシーケンスに変換され、エンコーダへ送られて、符号化される。或いは又、ビデオプロセッサは、個々のサンプルを直接操作してもよく、この操作は、サンプルを変換及び量子化し、サンプルに対する個別の量子化整数値をイベントシーケンスに変換する処理を含むものであってもよい。
【0030】
[0042] 図2は、ビットストリームを生成するための符号化プロセスのフロー図である。このプロセスは、処理ロジックによって実行される。当該処理ロジックは、ハードウェア(例えば、回路、専用ロジック等)、ソフトウェア(例えば、汎用コンピュータシステム又は専用マシンで実行されるソフトウェア)或いはその両方の組合せによって構成され得る。
【0031】
[0043] 図2に示すように、この処理ロジックは、イベントシーケンス内のイベントを符号化して、符号化データを生成する(処理ブロック201)。イベントは、2進決定(binary decision)とすることができる。また、イベントは、同じスライスからのものであってもよい。一実施形態では、イベントの一つは、算術符号化の終了(例えば、スライスの終了)を指示する。次いで、処理ロジックは、全てのイベントに対する符号化データと、それに続くスタフィングバイト(又はビット)とをもつビットストリームを生成する(処理ロジック202)。このスタフィングバイト(又はビット)は、ビットストリームにおいて、算術符号化の終了を指示する符号化インジケータの後に入れられる。
【0032】
[0044] 図3は、符号化データを、図1のシステムのようなシステムにおいて送信することのできる例示のデータフォーマット300を示す。フォーマット300は、ヘッダ302と、算術符号304と、一つ以上のストップビット306と、0,1又はそれより多くの整列ビット308と、0,1又はそれより多くのスタフィングバイト310とを含む。別の実施形態では、0,1又はそれ以上のスタフィングビットをバイトに代えて使用することができる。
【0033】
[0045] 上述したように、図1のシステム及び図3のデータフォーマットを使用して、ピクチャーのシーケンスに関連するデータを含むビデオ情報の符号化及び送信を行うことができる。一実施形態では、ピクチャーが一つ以上のスライスに分割される。ここで、1スライスは、16×16ピクセルのアレーのマクロブロックを一つ以上含む。各スライスは、ピクチャー内の他のスライスと独立して符号化される。ピクチャーデータは、図3に示すフォーマットで符号化される。
【0034】
[0046] 一実施形態では、ヘッダ302は、バイト境界で始まり、固定長符号又は可変長符号のいずれかを用いて符号化(例えば、ハフマン符号化)されたデータを含む。ヘッダ302は、スライスヘッダとすることができる。スライスヘッダの場合に、ヘッダ302の前に、スタートコード(SC)と、その次に続くスライスデータの形式を識別するインジケータとを設けることができる。
【0035】
[0047] 算術符号304は、エンコーダ102(図1)のようなエンコーダの算術符号化エンジンによって生成されたビットのシーケンスである。一実施形態では、ビットのシーケンスがバイト境界でスタートする。一つ以上のストップビット303が、算術符号304に続く。別の実施形態では、ストップビット303が算術符号304に含まれてもよい。幾つかの(0から7)の後続の整列ビット308がストップビット306に続き、一実施形態では、スタフィングバイト310のバイト整列を保証する。データに追加されるスタフィングバイト310の数は、符号化されているイベントの数と、ビデオデータのブロック(例えばマクロブロック)の数と、生成された情報シーケンスのサイズとの間の関係を維持することに要するバイト数に基づいて、0バイト、1バイト又は2バイト以上にすることができる。
【0036】
<コードストリームの終了>
【0037】
[0048] 一実施形態では、エンコーダは、算術符号化データの終了をデコーダに指示するイベント(例えば決定)を符号化する。算術符号化データの終了は、スライスの終了に達したときに指示されてもよい。また、算術符号化データの終了は、ビットストリームにおける算術符号化データがストップし、その後に非算術符号化データが続くときにも発生させてもよい。
【0038】
[0049] 図3に戻り、一実施形態では、スライス内の各マクロブロックに対して、算術符号204は、典型的には、以下のデータ、即ちマクロブロックモード、任意に動きベクトル及び変換係数、並びにend_of_slice_flagを含む。このend_of_slice_flagによって、デコーダ104(図1)がスライス内の最後のマクロブロックがいつ復号されたかを画定することが可能となる。このフラグが使用されるのは、算術符号の最終ビットが、2つ以上のマクロブロックを記述するデータを含む可能性があるからである。
【0039】
[0050] 算術符号化データの終了を符号化することの利点は、従来の手法を検討することによって説明できる。従来の手法では、算術エンコーダの終了は、通常、2つの代案のうちの一方に基づいて行われる。第1のアプローチでは、そのままのレジスタLが送信される。第2のアプローチでは、レジスタLのコンテンツにオフセットが追加され、レジスタLの最上位ビットだけが送信される。第1のアプローチの利点は、デコーダが、エンコーダによって生成されたものと同数のビットを正確に読み取ることである。しかしながら、これによって、余分なビットを送信するという損失がもたらされる。第2のアプローチでは、ビットは節約されるが、デコーダは、エンコーダによって生成されたものより多くのビットを読み取る。これは、デコーダでビットストリームにパディングを行うことによって克服することができる。
【0040】
[0051] 本明細書に開示するアプローチは、両者の最良な点を供する。即ち、デコーダはエンコーダによって生成されたものと同数のビットを読み取り、エンコーダには必要以上のビットを送信させない。これは、イベント、即ちend_of_slice_flagを符号化して、スライスの終了を知らせることによって可能となっている。良好に定められた確率がこのイベントに割り付けられると、デコーダはそれを復号でき、当該イベントの結果が終了を知らせる場合に、デコーダは再正規化を先行することができる。即ち、通常、符号化中に、符号化される全てのシンボルについて、値Rに確率が乗算されて、サブインターバルが得られる。その後、再正規化が行われて、Rの値がある範囲の値に戻される。再正規化は、算術符号化の当業者に周知である。再正規化を先行することによって、読み取られるビットの数がエンコーダによって生成されるビットの数に一致することが保証される。
【0041】
[0052] 一実施形態では、end_of_sliceイベント(又は算術符号化の終了を指示する他のイベント)に割り当てられる確率は、符号化の終了中にレジスタRに割り当てられた数値によって、再正規化が実行される前に、定められる。一実施形態では、エンコーダとデコーダとが同期することを保証するために、スライス終了フラグに対して、サブインターバルの計算は、Rに記憶された値に確率を乗算することによって実行されない。代わりに、サブインターバルには、固定値、即ち定数が割り当てられる。一実施形態では、固定値2が使用される。より一般的には、end_of_slice_flagを符号化する前に、この値は、レジスタRのコンテンツの値とは独立していなければならない。これは、ビットストリームに入れられる最後のシンボル(ビット)のために行われる。サブインターバルを値2に設定することによって、デコーダのオペレーションに影響なく、値1をレジスタLの値に加算することができる。これによって、ロー(L)レジスタ全体のコンテンツをビットストリームに送り込むことが可能となる。全レジスタLのコンテンツが送信されるので、この例では再正規化が不要である。
【0042】
[0053] 一実施形態では、レジスタLの最下位ビットを1に設定して、Lのコンテンツを送信する。レジスタLの最下位ビットを1に設定することは、その最下位ビットがゼロである場合にLに1を加算することと等価である。したがって、算術エンコーダによって生成される最終ビットは1に等しく、算術符号を含むビットストリームの最終バイトは非ゼロの値を有する。結果において、レジスタLの最下位ビットは、ストップビットとなる。
【0043】
<スタフィングバイトの追加>
【0044】
[0054] 一実施形態では、エンコーダは、圧縮されたデータのビットストリームにスタフィングバイト又はビットを挿入する。一実施形態では、スタフィングバイトは、スライスの算術符号の後に、ストップビット及び0、1又はそれ以上の整列ビットに続いて挿入される。整列ビットを挿入して、追加されるスタフィングバイトがバイト境界に挿入されることを保証する。ストップビットの後にスタフィングバイトを入れることの利点の一つは、デコーダがスタフィングバイトを復号する必要がないことである。したがって、デコーダは、エンコーダによって生成された符号化データのビット数と同数のビットを復号する。
【0045】
[0055] 一実施形態では、圧縮されたビットストリームに挿入されるスタフィングバイトの数は、エンコーダに入力されるイベントの数と、データブロックの数と、エンコーダから出力されるビットの数との間の関係を維持することに基づいている。この関係を、より詳細に以下に説明する。
【0046】
[0056] 一実施形態では、スタフィングバイトが特定のパターンを有している。このパターンは、ユニークであり、デコーダは、スタフィングバイトが存在することを、ストップビット及び一つ以上の整列ビットに続くこの特定パターンのビットを識別することによって、決定することができる。このような決定がなされると、デコーダは、スタフィングバイトを復号する必要がない。一実施形態では、デコーダは、デマルチプレクス機能を有しており、この機能は、ヘッダビット(ヘッダビットは復号エンジンへ送信されない)と同様に、スタフィングバイトがデコーダの算術復号エンジンへ送信されることを防止する。
【0047】
[0057] 一実施形態では、スタフィングビットのパターンは、16進表記で000003の3バイトシーケンスであり、当該バイトシーケンスがビットストリームに追加される。最初の2バイトは、ゼロワード(0000)となっており、第3バイト(03)は、スライスの終了の後に、デコーダによって認識され、当該バイトがスタフィングバイトとして識別される。
【0048】
[0058] 一実施形態では、スライスの終了に詰め込まれたスタフィングバイト310の数は、算術復号のオペレーション数とビット数との関係が4以下であることを保証する。図1のエンコーダ102のようなエンコーダは、レジスタCを使用して、イベント(復号オペレーション)対ビット(又はバイト)の比をカウントし、さもなければ、追跡することができる。イベントが処理されるたびに、カウンタCが1増加され、更に、ビットが生成されるたびに、カウンタCが4(又はバイト生成のたびに32)減らされる。一実施形態では、カウント処理は、ヘッダ及びそれに後続するストップ及び整列ビットを含むスライス(又は他のイベントセット)の全ビットを考慮に入れている。
【0049】
[0059] 一実施形態では、end_of_slice_flagに対する復号オペレーションは、カウンタCによってカウントされない(代替の方法ではカウントされるが)ことに注意されたい。しかしながら、マクロブロック当たり一つのこのようなイベントがあり、このようなイベントの数は、ピクチャーサイズによって良好に制限されることが知られている。この場合、end_of_slice_flagイベントをカウントしないことは、それらをカウントする(故に、マクロブロックごとに一度、Cを1増加する)が、同時に、256ピクセルごとに(マクロブロックごとに一度)Cを1減少させることと等価である。或いは又、マクロブロックごとにCを任意の値だけ減少させることもできる。
【0050】
[0060] 一実施形態では、本明細書に記載された手法でスタフィングバイトを追加すると、符号化されたスライスの最小長さが保証される。符号化されたスライスの中間にスタフィングビットを挿入する従来の技術に対し、この進歩によって、エンコーダがデータを符号化する規定、特に、どれほど多くのデータを符号化するかを定める規定が簡単になる。
【0051】
[0061] エンコーダは、イベントシーケンスにおけるイベントの数を、情報ビットのシーケンスにおける情報ビットの数と、イベントシーケンスで表わされた入力データのセグメント数、即ちブロック数との関数として制約する。例えば、この制約は、次のような線形結合の形態をとる。
e≦αB+βS
ここで、eは、情報ビット(又は他のエレメント)のシーケンスで表わされたイベントの数であり、Bは、情報ビット(又は他のエレメント)のシーケンスにおける情報ビットの数であり、Sは、イベントシーケンスで表わされたセグメント(例えばマクロブロック)の数である。また、α及びβは、カウンタへの減少値を表しており、生成される情報ビットの数及び処理されるセグメントの数に対するイベントシーケンスのイベント数の制約を実質的に維持する。
【0052】
[0062] α及びβの値は、通常、算術コーダのコントローラへ提供される。α及びβの導出について以下に説明する。αの値は、例えば、算術コーダにおいて情報ビットを生成する際のカウンタへの減少値を表わす。一方、βの値は、例えば、データブロックの処理が完了した際のカウンタへの減少値を表わす。別の形態では、当業者には明らかなように、値βを、セグメントの処理の開始時に又はデータブロックの処理中の他の任意の時間にカウンタ値から減少させてもよい。
【0053】
[0063] 全ブロック数S及び値βは既知であるから、β×Sの積を、入力データのブロック(例えばマクロブロック)の処理後にイベントシーケンスのイベントの数eから減算してもよい。例えば、カウンタを使用して、生成されたビットの数に応じてイベントの数を制約する場合に、当該カウンタを、最初にβ×Sの値だけ減少させ、情報ビットが生成されるたびに値αだけ減少させ、一方、イベントシーケンスの各イベントがエントロピーエンコーダによって処理される度に、「1」だけ増加させる。
【0054】
[0064] βの値は、通常、1から100までの範囲内の任意の値であることができ、例えば、以下に述べるように、決定される。αの値は、通常、1から10までの範囲内の任意の値であり、例えば、以下に述べるように決定される。
【0055】
[0065] ある環境において、例えば、通信媒体が、情報シーケンスに与えられる情報ビットの数を制限する場合には、処理されるべき入力データのブロック数が前もって分からない。これは、例えば、情報シーケンスがインターネットプロトコル(IP)パケットとしてインターネットを経て送信されるものであって、このIPパケットが最大サイズ制限を有する場合に生じる。これらの環境では、個別の画像の複雑さに依存するが、一つ以上の情報ビットのシーケンスが、入力データの一画像を表わすために、必要となる。しかしながら、情報ビットのシーケンスの生成に使用されるブロックの数は、前もって分からない。その理由は、どれほど多くのセグメントを処理した後に情報ビットシーケンスの最大サイズに達するか分からないからである。処理されるべき入力データのセグメント数が前もって分からない場合には、コントローラは、個別のイベントシーケンスを表す一つ以上のブロックが符号化されるときに、イベントシーケンスを考慮する。例えば、カウンタを使用し、生成されたビットの数に応じてイベントの数を制約する場合には、当該カウンタを、各ブロックが処理されるたびに値βだけ減少させ、情報ビットが生成されるたびに値αだけ減少させ、一方、イベントシーケンスのイベントがエントロピーエンコーダによって処理される度に「1」だけ増加させる。
【0056】
[0066] α及びβの値は、エンコーダのシステム設計者が上述した一つ以上の制限を考慮することによって前もって決定されて、コントローラに与えられてもよい。これに代えて又はこれに加えて、α及びβの値は、上述した制限の一つ以上に基づいて、又はエンコーダのデフォルト値として、コントローラ、又はエンコーダの他の要素によって、決定されてもよい。コントローラが、規格又は復号装置によって課せられる制限の一つ又は両者を使用してα及びβの値を決定する場合に、一つ以上の当該制限に関する情報がコントローラのメモリ(図示せず)に記憶され、α及びβの値を決定する際にコントローラによって使用される。加えて又はこれに代えて、当該制限に関する情報は、例えば、外部メモリ(即ちデジタルビデオディスク(DVD))や、DVDプレーヤ装置のような外部装置によって、或いは、例えば特定の入力データの符号化に関する幾つかの機能を取り扱うシステムエンジニアから、コントローラへ供給されてもよい。後者の場合に、システムエンジニアは、当業者には明らかなように、符号化規格及び/又は復号装置によって課せられる制限に関する情報をコンソール又は他の入力装置(図示せず)に入力することができ、又は、他の方法で指定することができる。
【0057】
[0067] 更に、α及びβの値を決定する場合に、複雑さの制約が厳し過ぎるかどうか、例えば、α及び/又はβの値が低過ぎるかどうかを考慮してもよい。情報ビットシーケンスの終端に存在するスタフィング情報ビットの割合が高いこと(即ち、スタフィングバイト(又はビット)の数が情報シーケンスの情報ビットの約1%又は2%以上であること)は、その制約が厳し過ぎることを示す。当業者であれば、例えば、使用できる特定の規格及び/又はデコーダを考慮に入れて、他の割合がスタフィング情報ビットの高い割合を示してもよいことは明らかであろう。
【0058】
[0068] 例えば、α及びβの値が制約を過度に厳しくすると決定された場合に、α及びβの値を高くして、スタフィングバイトが追加される見込みを低減する(即ち、符号化情報シーケンスにおけるクオリティペナルティの見込みを低減する)ことができる。α及びβの値を高くする場合には、符号化された情報シーケンスの復号に使用されるデコーダについて得られる複雑さの限界に対してその影響が考慮される。このような考慮は、デコーダを実施するためのコストを含むことができる。複雑さの限界が高い場合には、より大きな処理能力がデコーダに必要とされる。必要な処理能力の増加は、おそらく高い実施コストを招く。尚、一実施形態では、各マクロブロックからデータを符号化した後にα及びβの変更がなされてもよい。
【0059】
[0069] α及びβの値は、線形回帰技術を使用して実験的に決定することができる。各々がS個のセグメントを表すイベントシーケンスが、複雑さの制約を強いることなく、符号化されてもよい。イベントシーケンスzごとに、イベント数e(z)に対し、生成される情報ビット数B(z)が分かる。これは、線形回帰式、即ちデータ対(e(z)、B(z))を近似する線e+c*B+dを使用して決定することができる。したがって、線e=α*β+β*Sの上に存在するデータ対(e(z)、B(z))の数を減らし、潜在的にはそれを最小にするように、α及び/又はβの初期値を高くすることができる。
【0060】
[0070] 上述した種々の技術の一つ以上によって決定されたα及びβの値を使用して、エンコーダは、生成される各情報ビットに対しαの値を考慮し(即ち、αの値だけカウンタを減少させ)、入力データのセグメントが完了した際にβの値を考慮する(即ち、βの値だけカウンタを減少させる)ことができる。例えば、α及びβが整数値である場合には、このような考慮(即ち、一つ以上のカウンタに対する減少)を直接行うことができる。
【0061】
[0071] 例えば、α及びβの一方又は両方が分数値である場合には、共通の分母を決定して、α及びβの非分数値を与えることができる。この環境では、α及びβの新たな非分数値は、例えば、情報ビットの発生時及びセグメント処理の完了時に各々α及びβの値だけカウンタを減少させることによって、上述したように考慮される。決定された共通の分母は、例えば、イベントシーケンスにおける各イベントを処理する際に共通の分母の値をカウンタ値に加算することによって考慮される。例えば、α及びβの値が各々4/3及び25と決定された場合には、共通の分母は、3と決定される。したがって、α及びβの非分数値は、共通の分母を使用して各々4及び75と決定される。したがって、カウンタを使用してα及びβの値を考慮する場合には、カウンタを、情報ビットが発生されるたびに4だけ減少させ、各セグメントの処理が完了すると75だけ減少させ、更に、イベントが処理されるたびに3だけ増加させる。
【0062】
<エンコーダのオペレーションの例>
【0063】
[0072] 図4は、算術エンコーダの一実施形態のブロック図である。図4に示すように、算術エンコーダ400は、シーケンサ405と、確率推定器410と、符号化エンジン415とを備え、これらは互いに接続されている。一つ以上の入力データライン420は、エンコーダ400にイベントシーケンス425(例えば、2進イベントの順序付けされたシーケンス)を受信するための入力ポートを備えている。イベントシーケンスは、エンコーダ400によって、以下に述べるように処理されて、情報シーケンスを生成する。一実施形態では、この情報シーケンスは、順序付けされたシーケンスであり、少なくとも一つの情報エレメント(例えばビット)で構成されている。一実施形態では、情報シーケンスにおける情報ビットの数は、イベントシーケンスにおけるイベントの数より少ない。出力430は、エンコーダ400から情報シーケンス435を送信するための出力ポートを備えている。この情報シーケンスの順序付けされたビットのシーケンスは、「0」又は「1」の値を有する一つ以上のビットを含む。
【0064】
[0073] イベントシーケンス425を受信すると、シーケンサ405は、確率推定器410及び符号化エンジン415の両者にイベント425を順次送信する。また、イベントシーケンス425の2進イベントごとに、シーケンサ405は、当該2進イベント用に確率推定器410へコンテクスト情報を送信する。確率推定器410は、受信したコンテクスト情報を使用して、確率推定値P(A)を生成する。確率推定値P(A)は、符号化エンジン415へ送信される。一実施形態において、確率推定器410は、多数の確率推定値を符号化エンジン415へ送信し、符号化エンジン415は、確率推定値の一つをR値に基づいて選択する。これに代えて、R値が確率推定器410へ送信され、確率推定器が当該R値を使用して、送信されるべき一つの確率推定値を選択してもよい。確率推定器410は、次いで、受信した2進イベントの値に基づいてその内部状態を更新する。符号化エンジン415は、受信した2進イベント及び対応の確率推定値P(A)を使用して0以上の情報ビットを生成する。
【0065】
[0074] 一実施形態において、符号化エンジン415は、算術符号化データの終了を指示するイベントを符号化する。このイベントは、スライス終了フラグであってもよく、又はビットストリームにおいて非算術符号化データが少なくとも続くという別のインジケータであってもよい。
【0066】
[0075] ゼロ以上の情報ビットを発生する際に、符号化エンジン415は、レンジレジスタ465、ローレジスタ470、ビットアウトスタンディングレジスタ475及びカウンタレジスタ480を含む種々のレジスタを使用する。算術符号化を実行するエンコーダ400のオペレーションは、この技術分野では周知である。
【0067】
[0076] 一実施形態では、エンコーダ400は、情報ビットに対するイベントの関係を限定する。このことは、本明細書の他の部分で説明している。エンコーダ400は、このオペレーションを、その一部分については、上述したようにスタフィングバイト(又はビット)を情報シーケンスに挿入することによって実行する。
【0068】
[0077] 図5は、イベントの符号化に関する一実施形態のフロー図である。このプロセスは、ハードウェア(例えば、回路、専用ロジック等)、ソフトウェア(例えば、汎用コンピュータシステム又は専用マシンで実行されるようなソフトウェア)或いはその両方の組合せで構成される処理ロジックによって実行される。算術符号化プロセスへの入力は、コンテクストを識別するコンテクストID、値R、L、及びsymCntを用いて復号される2進イベントであり、出力に書き込まれるのは、符号化によって生じたビットである。一実施形態では、符号化は、復号と対称であり、算術符号化エンジンの状態は、上述したように、サブインターバルの下端を指すLの値と、サブインターバルの対応レンジを特定するRの値とで表わされる。
【0069】
[0078] 一実施形態では、符号化プロセスは、符号化エンジンが初期化された後にのみ呼び出される。一実施形態では、初期化は、ゼロに等しいLの値及び0x01FEに等しいRの値を送信し、第1ビットフラグを1に、ビットアウトスタンディング(BO)値及びsymCnt(C)カウンタを0にセットすることによって実行される。第1ビットフラグは、符号化中に、エンコーダが初めてプットビット(put bit)手順に入るときを指示するために使用される。symCntカウンタは、符号化されるイベントの数を指示する値を記憶する。
【0070】
[0079] 図5を参照する。このプロセスは、値RLPSを次のように導出することによって(処理ブロック501)、単一イベント(例えばビット)の符号化を開始する。一実施形態では、処理ロジックは、Rインデックス(即ちRidx)を、Rの値を右へ6位置シフトして数値3Hexとアンドした値に等しくすることによって、変数RLPSを導出する。次いで、処理ロジックは、RLPSの値を、Ridxの値と、コンテクストに関連付けられている現在のコンテクストに対する状態の値とを使用し、図16Aに示すテーブルのような確率推定状態マシンテーブルにアクセスすることによって決定される値に、等しくする。Rの値は、次いで、現在のR値からRLPSを引いたものにセットされる。
【0071】
[0080] MPSカウントに対するサブレンジインターバルを計算した後に、処理ロジックは、符号化されている2進イベントの値がMPSの値に等しくないかどうかテストする(処理ブロック502)。2進イベントの値がMPSに等しい場合には、処理ロジックは、MPSパスをとって処理ブロック503へ移行し、そこで、処理ロジックは、状態マシンを、図16Bのテーブルを使用して、そのコンテクストに対して状態マシンに指示された次の状態へと更新し、次いで、プロセスが処理ブロック508へ移行する。符号化されている2進イベントがMPSの値に等しくないと判断すると、処理ロジックは、LPSパスをとって処理ブロック504へ移行し、そこで、処理ロジックは、Lの値を、Lの値とRの値の和に等しくセットし、次いで、Rの値を、RLPSの値に等しくする。
【0072】
[0081] その後、処理ロジックは、特定のコンテクストに対する状態がゼロに等しくないかどうか決定する(処理ブロック505)。一実施形態では、状態ゼロは、50/50の確率に対応する状態である。或いは又、状態ゼロは、例えば、50/50の確率に近い別の確率に対応する状態である。コンテクストの状態がゼロに等しくない場合には、処理ロジックは、処理ブロック507へ移行する。コンテクストの状態がゼロに等しい場合には、処理ロジックは、MPSの意味を切り換え(処理ブロック506)、次いで、処理ブロック507へ移行し、ここで、処理ロジックは、コンテクストの状態番号を、図16Bのテーブルを使用して次の状態へ更新する(処理ブロック507)。
【0073】
[0082] 処理ブロック507及び503を実行した後に、プロセスは、処理ブロック508へ移行し、そこで、処理ロジックは、図6に示す再正規化のような再正規化手順を実行する。次いで、処理ロジックは、イベントカウンタの値を1だけ増加し(処理ブロック509)、処理を終了する。
【0074】
[0083] 図6は、エンコーダの再正規化手順の一実施形態のフロー図である。このプロセスは、ハードウェア(例えば、回路、専用ロジック等)、ソフトウェア(例えば、汎用コンピュータシステム又は専用マシンで実行される)或いはその両方の組合せで構成される処理ロジックによって実行される。
【0075】
[0084] 次に、図6を参照する。まず、処理ロジックは、Rの値が100Hex未満であるかどうかテストする(処理ブロック601)。Noの場合、プロセスは終了となる。Yesの場合、プロセスは、処理ブロック602へ移行し、そこで、処理ロジックは、Lの値が100Hex未満であるかどうかテストする。Yesの場合、処理ブロックは、処理ブロック603へ移行し、そこで、プットビット手順がパラメータ0で実行され、その後、プロセスは、処理ブロック608へ移行する。処理ロジックは、Lの値が100Hex以上であると判断すると、Lの値が200Hexより大きいかどうかテストする。Noの場合、処理ロジックは、Lの値から100Hexを減算した値にLの値をセットし、ビットアウトスタンディング(BO)の値を、パラメータ1で1だけ増加する(処理ブロック605)。次いで、プロセスは、処理ブロック608へ移行する。Lの値が200Hex以上である場合には、プロセスは、処理ブロック606へ移行し、そこで、処理ロジックは、Lの値を、Lの値から200Hexを減算した値にセットし、プットビット手順を実行し(処理ブロック607)、次いで、処理ブロック608へ移行する。
【0076】
[0085] 処理ブロック608では、処理ロジックがRの値を左へ1位置シフトし、且つLの値を1位置シフトする。その後、プロセスは、処理ブロック601へ移行し、プロセスが繰り返される。
【0077】
[0086] 図7は、プットビット手順の実施形態を実行するプロセスの一実施形態を示す。プットビット手順は、ゼロ以上のビットをビットストリームに書き込む。このプロセスは、ハードウェア(例えば、回路、専用ロジック等)、ソフトウェア(例えば、汎用コンピュータシステム又は専用マシンで実行される)或いはその両方の組合せで構成される処理ロジックによって実行される。
【0078】
[0087] 図7に示すように、処理ロジックは、最初に、第1ビットフラグがゼロに等しくないかどうかチェックする(処理ブロック701)。第1ビットフラグが1にセットされている場合には、処理ロジックは、第1ビットフラグをゼロに等しくセットする(処理ブロック702)。次いで、プロセスは、処理ブロック704へ移行する。Noの場合、処理ロジックは、値Bをもつビットを送信し(処理ブロック703)、次いで、処理ロジックが、処理ブロック704へ移行する。
【0079】
[0088] 処理ブロック704において、処理ロジックは、ビットアウトスタンディング(BO)の値がゼロより大きいかどうかテストする。Noの場合、プロセスは終了となる。Yesの場合、処理ロジックは、値1−Bをもつビットを送信し、BOの値を1だけ減少させる(処理ブロック705)。その後、処理ロジックが、処理ブロック704へと移行する。
【0080】
[0089] 図8は、終了前にイベントを符号化するプロセスの一実施形態を示すフロー図である。このプロセスは、スライスの終了と、算術符号化の終了を知らせる他の2進イベントとの符号化に使用される。このプロセスは、ハードウェア(例えば、回路、専用ロジック等)、ソフトウェア(例えば、汎用コンピュータシステム又は専用マシンで実行される)或いはその両方の組合せで構成される処理ロジックによって実行される。
【0081】
[0090] 図8に示すように、処理ロジックは、最初にRの値を2だけ減少させる(処理ブロック801)。次いで、処理ロジックは、符号化されている2進イベントの値がゼロに等しくないかどうかテストする(処理ブロック802)。イベントがゼロに等しい場合には、処理ロジックは、図6に示したような再正規化手順を実行し(処理ブロック803)、次いで、プロセスは、処理ブロック806へ移行する。符号化されるべき2進イベントの値がゼロに等しくない場合には、処理ロジックは、Lの値を、Lの値とRの値の加算値にセットし(処理ブロック804)、エンコーダフラッシング手順を実行し(処理ブロック805)、次いで、処理ブロック806へ移行する。処理ブロック806では、処理ロジックが、イベントカウンタの値を1だけ増加し、符号化プロセスが終了する。
【0082】
[0091] 上記プロセスにおいて明らかなように、一実施形態では、2進イベントの値が1に等しい場合に、算術符号化が終了となり、イベントを符号化した後にフラッシング手順が適用される。このようなイベントを符号化すると、書き込まれる最後のビットは、1に等しいストップビットを含む。
【0083】
[0092] 図9は、終了時のフラッシュに係るプロセスの一実施形態を示すフロー図である。このプロセスは、ハードウェア(例えば、回路、専用ロジック等)、ソフトウェア(例えば、汎用コンピュータシステム又は専用マシンで実行される)或いはその両方の組合せで構成される処理ロジックによって実行される。
【0084】
[0093] 図9に沿って説明する。処理ロジックは、最初に、Rの値を2にセットする(処理ブロック901)。処理ロジックは、次いで、図6に示した再正規化手順のような再正規化手順を実行する(処理ブロック902)。処理ロジックは、次いで、Lの値を右に9位置シフトして、値1Hexとアンドしたものに等しい値に対して図7に示すプットビット手順を実行する(処理ブロック903)。Lレジスタの値をシフトしたコンテンツに対してアンドオペレーションを実行した結果は、10番目のビット位置(最下位ビットから数えて)にビットを生成させ、その後、プットビット手順を使用して出力される。
【0085】
[0094] 最終的に、処理ロジックは、Lレジスタの値を7位置右へシフトして、3Hexの値とアンドし、次いで、1Hexとオアしたものに等しい2つのビットを送信する(処理ブロック904)。1Hexとのオアオペレーションは、ストップビットを追加するために実行される。
【0086】
<デコーダのオペレーションの例>
【0087】
[0095] 図10は、算術デコーダ1000の一実施形態を示すブロック図である。図10に示すように、デコーダ1000は、シーケンサ1005と、確率推定器1010と、復号エンジン1015とを備え、これらは互いに接続されている。入力1020は、デコーダ1000への情報シーケンス1025(例えば2進ビットの順序付けされたシーケンス)のためのポートを提供する。シーケンス1025の2進ビットは、「0」又は「1」の値を有する。一実施形態では、デコーダ1000は、情報シーケンスを処理して、イベントシーケンス1035を生成する。生成されたイベントシーケンスは、単一ビット値以外の値を有する多数のイベント(例えば2進イベント)を含む順序付けされたイベントシーケンスである。このイベントシーケンスは、デコーダ1000からの少なくとも一つの出力ポートを含む出力1030へ供給される。
【0088】
[0096] 情報シーケンス1025を受信すると、シーケンサ1005は、復号エンジン1015に一つ以上のビットを送信する。デコーダ1000は、イベントシーケンスの一つ以上のイベントを次のように繰り返し生成する。シーケンサ1005は、各イベントについて、対応のコンテクストを確率推定器1010に送信する。
【0089】
[0097] 確率推定器1010は、受け取ったコンテクストの値に基づいて、対応の確率推定値P(A)を発生する。この確率推定値P(A)は、復号エンジン1015へ送信され、復号エンジン1015によってイベントの生成に使用される。一実施形態では、確率推定器1010は、多数の確率推定値を復号エンジン1015へ送信し、次いで、復号エンジン1015は、Rの値に基づいて確率推定値の一つを選択する。或いは又、Rの値が確率推定器1010へ送信され、確率推定器がこれを使用して、送信されるべき一つの確率推定値を選択してもよい。次いで、確率推定器1010は、復号エンジン1015から受け取った2進イベントの値に基づいてその内部状態を更新する。
【0090】
[0098] 復号エンジン1015は、生成された各イベントを確率推定器1010及びシーケンサ1005へ送信する。復号エンジン1015は、生成された各2進イベントに対してゼロ以上の情報ビットを消費する。したがって、シーケンサ1005は、イベントの生成後に、情報シーケンスからのゼロ以上のビットを復号エンジン1015へ送信する。復号エンジン1015は、レンジレジスタ1065や値レジスタ1070を含む種々のレジスタを使用して、イベントシーケンス1035のイベントを生成する。デコーダ1000のオペレーションは、以下に説明するフロー図に示されている。
【0091】
[0099] 以下のフロー図は、デコーダ1000のようなデコーダの一実施形態によってスライスに対して実行される復号オペレーションを示している。一実施形態において、デコーダは、図12、14A、14B、15A又は15Bに示されたフロー図に従い、コンテクストの値に基づいて復号を実行する。図示されたプロセスは、他のプロセスに組み込まれてもよく、それに具体化された改善の利益を得るように他の方法で適用、或いは変更されてもよい。一実施形態では、デコーダは、一度に1バイトを読み取る。別の実施形態では、デコーダは、一度に1ビットを読み取る。
【0092】
[0100] 図11は、算術デコーダの初期化プロセスの一実施形態を示すフロー図である。このプロセスは、ハードウェア(例えば、回路、専用ロジック等)、ソフトウェア(例えば、汎用コンピュータシステム又は専用マシンで実行される)或いはその両方の組合せで構成される処理ロジックによって実行される。
【0093】
[0101] 図11を参照する。まず、プロセスは、処理ロジックがレンジRを所定の数値にセットすることで始まる(処理ブロック1101)。一実施形態において、当該所定の数値は、0xff00である。レンジRを初期化した後、処理ロジックは、圧縮されたデータの2バイトをレジスタVへ読み込む(処理ブロック1102)。一実施形態では、レジスタVは、圧縮されたビットを一度に1バイト記憶する。レジスタVは、圧縮されたデータを一度に1ビット記憶するように実施されてもよいが、本明細書に記載されたプロセスに使用される定数が、それに応じて変更されなければならない。
【0094】
[0102] より詳細には、図示されたように、処理ロジックは、1バイトを読み込み、それを左に8位置シフトし、次いで、別のバイトを取得し、それを算術オアオペレーションを用いてレジスタVへ加算する。圧縮されたデータがレジスタVに読み込まれると、処理ロジックは、レジスタBの値を所定値にセットする。レジスタBは、処理に使用できるレジスタV内の余りのビット数を指示する。レジスタBの値が0未満になると、圧縮されたデータの別のバイトをフェッチすることが必要となる。一実施形態では、所定値は7である。
【0095】
[0103] 図12は、2進イベントを復号するプロセスの一実施形態を示すフロー図である。このプロセスは、ハードウェア(例えば、回路、専用ロジック等)、ソフトウェア(例えば、汎用コンピュータシステム又は専用マシンで実行される)或いはその両方の組合せで構成される処理ロジックによって実行される。
【0096】
[0104] 図12に示すように、このプロセスは、LPSのインターバルのサイズを計算することによって開始する(処理ブロック1202)。一実施形態において、この計算は、乗算によって実行される。乗算は、コンテクスト(CTX)に関連付けられた状態に基づくテーブルルックアップを使用することによって近似される。一実施形態では、有限状態マシンを使用して、マシンの状態に依存している確率が何であるかを指示する。次いで、ルックアップするのは、状態の値と、Rの最上位ビット後の次の2つの最上位ビットである。ルックアップを実行するテーブルの例を図16Aに示す。また、テーブルを生成する方法の例を以下に示す。
【0097】
[0105] テーブルルックアップの結果は、7シフトされる。その理由は、この手法では、一度にビットではなくバイトが読み取られるからである。テーブルルックアップのシフトされた結果は、LPSのサブレンジインターバルであり、RLPSと称される。
【0098】
[0106] また、処理ブロック1202の一部分として、処理ロジックは、LPSのサブレンジインターバルRLPSをレジスタRの値から減算することによって、MPSのサブインターバルレンジを計算する。処理ロジックは、Rの値を減算の結果に等しくセットする。
【0099】
[0107] MPSのサブレンジインターバルを計算した後に、処理ロジックは、レジスタVの値が、レジスタRに記憶されたMPSのサブインターバル以上であるかどうかテストし、処理されている現在のビットがLPSのサブレンジ内であることを指示する(処理ブロック1203)。Noの場合、処理ロジックは、MPSパスをとって処理ブロック1204へ移行し、そこで、処理ロジックは、復号される値(即ち戻される結果)Sを、その特定のコンテクストに対するMPSであると定義された値に等しくセットする。次いで、処理ロジックは、当該コンテクストに対する状態マシンを、図16Bのテーブルを使用して当該コンテクストに対して状態マシンに指示された次の状態へと更新する。一実施形態では、MPSに対し、状態マシンの更新は、状態テーブルの状態を1だけ増加することからなる。
【0100】
[0108] 処理ロジックは、値VがレジスタRの値以上であると判断すると、LPS経路をとって処理ブロック1205へ移行し、そこで、結果Sを、特定のコンテクストCTXに対するLPS(MPSではない)に等しくセットし、値Vを、Vの現在値からレンジRの値を減算した結果に等しくセットし、更に、レンジRを、LPSのレンジ、即ちRLPSに等しくセットする(処理ブロック1205)。
【0101】
[0109] また、処理ロジックは、2進イベントのコンテクストに対する状態がゼロであるかどうかもチェックする(処理ブロック1206)。一実施形態では、状態0は、50/50の確率に対応する状態である。或いは又、状態ゼロは、例えば、50/50の確率に近い別の確率に対応する状態であってもよい。2進イベントのコンテクストに対する状態がゼロでない場合に、プロセスは、処理ブロック1208へ移行する。2進イベントのコンテクストに対する状態がゼロである場合に、処理ロジックは、MPSの意味を切り換える(処理ブロック1207)。
【0102】
[0110] その後、コンテクストの状態番号は、図16Bのテーブルを使用して次の状態へ更新され(処理ブロック1208)、処理ロジックは、以下に詳細に述べる再正規化手順を実行する(処理ブロック1209)。
【0103】
[0111] 図13は、再正規化手順のフロー図である。このプロセスは、ハードウェア(例えば、回路、専用ロジック等)、ソフトウェア(例えば、汎用コンピュータシステム又は専用マシンで実行される)或いはその両方の組合せで構成される処理ロジックによって実行される。
【0104】
[0112] 図13に示すように、プロセスは、Rが8000Hex未満であるかどうか処理ロジックがテストすることによって開始する(処理ブロック1301)。Rが8000Hex以上である場合には、再正規化プロセスが終了となる。Yesの場合、処理ロジックは、R及びVの値を2倍にする(処理ブロック1302)。一実施形態では、処理ロジックは、R及びVのビットを左へ1位置シフトすることによってR及びVの値を2倍にする。また、Bの値は、1だけ減少される。その理由は、シフト処理によって処理に利用可能なビットが一つ少なくなるからである。次いで、処理ロジックは、Bの値が0未満であるかどうかチェックする(処理ブロック1303)。Noの場合、処理は処理ブロック1301へ移行し、プロセスが繰り返される。Bの値が0未満である場合には、処理が処理ブロック1304へ移行し、そこで、Bの値が7にセットされ、処理されるべき別のバイトがフェッチされて、レジスタVの現在のコンテンツと論理オアされる。その後、処理は処理ブロック1301へ移行し、プロセスが繰り返される。
【0105】
[0113] 図14A及び14Bは、同じ確率でイベントを復号するためのフロー図である。図14Aは、レジスタVのサイズが16ビットより大きいときに使用され、一方、図14Bは、レジスタVのサイズが16ビットであるときに使用される。これらの手法は、一度に1バイトをフェッチするときに使用される。
【0106】
[0114] これらのプロセスは、ハードウェア(例えば、回路、専用ロジック等)、ソフトウェア(例えば、汎用コンピュータシステム又は専用マシンで実行される)或いはその両方の組合せで構成される処理ロジックによって実行される。
【0107】
[0115] 分布がゼロを中心とするものであって、正の値又は負の値を得る見込みがほぼ同じである場合に、これらのプロセスを使用できる。例えば、これらプロセスは、係数の符号値を処理するときに使用される。それが正であるか負であるかの見込みを推定するのではなく、固定推定値を使用して、確率が50/50であることを認識する。したがって、Rに確率を乗算するためのテーブルルックアップを実行する必要がない。尚、これらは、終了に影響しない。
【0108】
[0116] 図14Aを参照する。プロセスは、処理ロジックがVの値を2倍にすると共にBの値を1だけ減少させることによって開始する(処理ロジック1401)。Vの値を2倍にすることは、Vのビットを左へ1位置シフトすることで行われる。
【0109】
[0117] 次いで、処理ロジックは、Bの値が0未満であるかどうかチェックする(処理ブロック1402)。Noの場合、処理は、処理ブロック1404へ移行する。Bの値が0未満である場合には、処理ブロック1403へ移行し、そこで、Bの値が7にセットされ、処理されるべき別のバイトをフェッチされて、レジスタVの現在のコンテンツと論理オアされる。
【0110】
[0118] 処理ブロック1404において、処理ロジックは、Vの値がRの値以上であるかどうかテストする。Yesの場合、処理ロジックは、結果Sを1にセットし、更に、Vの値を、Vの値からRの値を減算した結果にセットし(処理ブロック1405)、プロセスが終了する。Noの場合、処理ロジックは、結果Sを0にセットし(処理ブロック1406)、プロセスは終了となる。
【0111】
[0119] 次に、図14Bを参照する。処理ロジックが値V’をVに等しくセットし、Vの値を2倍にし、Bの値を1だけ減少させることによって、プロセスが開始する(処理ロジック1411)。Vの値を2倍にすることは、Vのビットを左へ1位置シフトすることによって実行される。
【0112】
[0120] 次いで、処理ロジックは、Bの値が0未満であるかどうかチェックする(処理ブロック1412)。Noの場合、処理は、処理ブロック1414へ移行する。Bの値が0未満である場合には、処理ブロック1413へ移行し、そこで、Bの値が7にセットされ、処理されるべき別のバイトがフェッチされて、レジスタVの現在のコンテンツと論理オアされる。
【0113】
[0121] 処理ブロック1414では、処理ロジックは、Vの値がRの値以上であるかどうか、又はV’が8000Hex以上であるかどうかテストする。Yesの場合、処理ロジックは、結果Sを1にセットすると共に、Vの値を、Vの値からRの値を減算した結果にセットし(処理ブロック915)、プロセスが終了する。Noの場合、処理ロジックは、結果Sを0にセットし(処理ブロック916)、プロセスは終了となる。
【0114】
[0122] 図15Aは、算術符号化の終了を示す符号化イベントを復号するための一実施形態を示すフロー図である。このようなイベントは、スライス終了フラグを構成する。スライス終了フラグについては、シンタックスを使用して、スライス終了フラグの存在をデコーダに指示することができる。一実施形態では、このプロセスは、各マクロブロックについて実行されるが、スライスにおける最後のマクロブロックについてのみ、スライスの終了を指示する結果が得られる(例えば、1の結果が出力される)。
【0115】
[0123] 算術符号化の終了を知らせるためのイベント(デコーダに対する)は、ビットストリームにおいて算術符号化の後に続こうとするデータが、非圧縮のものか又は算術符号化以外の別の符号化技術で圧縮されたものであるときに使用される。尚、この非圧縮のデータ又は非算術符号化技術で圧縮されたデータの後に、追加の算術符号化データが続いてもよい。したがって、終了を知らせるためのイベントは、非算術符号化データがビットストリームにおいて算術符号化データとインターリーブされる場合に使用される。
【0116】
[0124] このプロセスは、ハードウェア(例えば、回路、専用ロジック等)、ソフトウェア(例えば、汎用コンピュータシステム又は専用マシンで実行される)或いはその両方の組合せで構成される処理ロジックによって実行される。
【0117】
[0125] 図15Aに沿って説明する。まず、処理ロジックは、Vの値が100Hex未満であるかどうかテストし(処理ブロック1501)、それによって、スライスにおける最後のマクロブロックに到達したことを指示する。Vの値が100Hex未満である場合に、処理ロジックは、復号されたシンボルを表わす結果Sを1にセットし(処理ブロック1502)、スライスに対する復号プロセスが終了する。Vの値が100Hex未満でない場合に、処理ロジックは、出力結果Sを0にセットし、Rの値を、Rの値から100Hexを減算した結果にセットし、更に、Vの値を、Vの値から100Hexを減算した結果にセットする(処理ロジック1503)。次いで、処理ロジックが、図3の再正規化手順を実行して(処理ブロック1504)、プロセスが終了となる。
【0118】
[0126] 尚、一実施形態では、MPSとLPSとの間の規定を切り換えてもよい。図15Bは、MPSとLPSとの間の規定を切り換えた場合に、終了前のイベントを符号化するプロセスの一実施形態を示すフロー図である。このプロセスは、ハードウェア(例えば、回路、専用ロジック等)、ソフトウェア(例えば、汎用コンピュータシステム又は専用マシンで実行される)或いはその両方の組合せで構成される処理ロジックによって実行される。
【0119】
[0127] 図15Bに示すように、処理ロジックは、Rの値から100Hexを減算することで開始する(処理ブロック1511)。次いで、処理ロジックは、Vの値がRの値以上であるかどうかテストする(処理ブロック1512)。Yesの場合、処理ロジックは、復号されたシンボルを表わす出力結果Sを1にセットし(処理ブロック1513)、次いで、終了前のイベントを復号する復号プロセスが終了となる。したがって、再正規化は実行されない。Noの場合、処理ロジックは、出力結果Sを0にセットし(処理ブロック1514)、図13の再正規化手順を実行し(処理ブロック1515)、次いで、プロセスは終りとなる。
【0120】
<確率推定のための状態マシンの構造>
[0128] 図16A及び16Bにおける状態マシンを構成するためのプロセスの一例をCコードで以下に示す。
C-code:
#define N b4
#define Pmax 0.5
#define Pmin 0.01875
#define regsize 9
#define ONE(1<<regsize)
double alpha;
double sum;
int i,j;
double q;
float prob64[N];
intnext_state_MPS_64[N];
intnext_state_LPS_64[N];
int switch_MPS_64[N];
int gLPS[N][4] ;
alpha=pow(Pmin/Pmax,1.0/(N-1));
sum=0.5;
for(i=0; i<N; i++){
prob64[i]=Pmax*pow(alpha,i);
next_state_MPS_64[i]=(i==N-1)?N-1:i+1;
q=prob64[i]*alpha+(1-alpha);
q=q/prob64[i];
q=-log(q)/log(alpha);
sum+=q;
k=(int)(sum);
sum-=k;
next_state_LPS_64[i]=(i-k<0)?O:i-k;
for(j=0; j<4; j++){
RTAB[i][j]=(int)(ONE/8*prob64[i]/log((j+5.0)/(j+4.0))+0.5);
if(j == 0 && RTAB[i][j] > ONE/4)
RTAB[i][j]=ONE/4;
}
}
【0121】
[0129] 上記コードにおいて、Nは、状態マシンにおける状態の数を定める。一実施形態において、状態マシンは対称的であり、合計状態数は、2*N(この例では128)である。状態は、状態(0とN−1(それらも含めて)との間の数値)と、MPSフラグ(0又は1のいずれがMPSであるかを決定する)との2つの変数で表わされる。
【0122】
[0130] 一実施形態では、大きな状態番号がLPSの低確率に対応するように、状態が編成される。状態マシンは、以下の手順に近づくように定義される。
(a)p(LPS) <-- p(LPS)*alpha、MPSが観察される場合
(b)p(LPS) <--p(LPS)*alpha+(1−alpha)、その他の場合
ここで、alphaは、適応レートを定める。alphaは、通常、0.9から1の範囲であるが、所望の適応に基づいて他の範囲内へ広がってもよく、又は他の範囲内にあってもよい。
【0123】
[0131] 上記コードにおいて、alphaは、pow(0.01875/0.5、1.0/63)に等しくセットされる。ここで、0.01875(Pmin)は、状態N−1に対するLPSの確率を定義し、0.5(Pmax)は、状態0に対するLPSの確率を定義し、更に、1.0/63は、1割るN−1である。尚、pow(a、b)は、数値aのb乗である。
【0124】
[0132] prob64と称するアレーは、各状態に関連付けられたLPSの確率を表わす浮動小数点値を含む。Prob64[i]は、Pmax*pow(alpha、i)にセットされる。Prob64[0]は、Pmaxに等しく、Prob64[N−1]は、Pminに等しい。
【0125】
[0133] Next_state_MPS_64[i]は、MPSが観察された際の状態遷移を定める。iがN−1と異なる場合には、状態が1だけ増加される。他の場合には、状態は不変に保たれる。Prob64[i]及びNext_state_MPS_64[i]の組合せが与えられると、上述した更新手順の(a)の部分が上手く近似される。
【0126】
[0134] 更新手順の(b)の部分を近似するために、Next_state_LPS_64[i]をi−(−log((prob64[i]*alpha+(1−alpha))/prob64[i])/log(alpha))にセットしなければならない。しかしながら、この値は、整数ではなく、したがって、整数近似を求めねばならない。一実施形態では、当該値は、最も近い整数に丸められる。しかしながら、別の実施形態では、丸め切り上げと丸め切り捨てとのバランスをとるために、丸めによって導入される差が平均でゼロに近づくように変数和が使用される。
【0127】
[0135] RTAB[i][j]の値は、R*prob64[j]に近づくように計算される。変数jは、Rが存在するインターバルによって決定される。変数jは、Rが[256、319]の場合には0に等しくセットされ、[320、383]の場合には1に等しくセットされ、[384、447]の場合には2に等しくセットされ、更に、[448、511]の場合には3に等しくセットされる。ここで、例えば、(ONE*4)/8は、256に等しく、(ONE*5)/8−1は、319に等しく、等々である。(ONE/8)log((j+5)/(j+4))は、jが与えられた場合のRの期待値となっている。
【0128】
[0136] より高速な実施を可能にするために、MPSを符号化する際には、再正規化の繰り返しを多くても1回しか行わないよう保証することが望ましい。このために、RTAB[i][0]は、ONE/4に切り取られる。それ故、Rは、再正規化の前にONE/4より小さくなることはない。より一般的には、一実施形態において、RTAB[i][j]は、(ONE/4)+(ONE/8)*jに切り取られるが、ここに示す例ではjが0と異なる場合はこのようにならない。
【0129】
[0137] したがって、上述した技術を使用すると、一実施形態では一つの状態を除いて、図16A及び16Bの状態テーブルを発生することができる。図16Aでは、状態63は、2,2,2,2のR値を含む。図16Bでは、いったん状態63になると、次の状態も、状態63である。したがって、LPSが発生するかMPSが発生するかに拘らず、状態は変化しない。また、図16Bでは、いったん状態62になると、状態は、MPS発生時に状態62に留まる。
【0130】
<ソースコードの実施例>
【0131】
[0138] Cコードでのサンプルエンコーダ及びサンプルデコーダを以下に示す。これらの方法は、データ(例えばビデオデータ)を符号化及び復号する適当な処理装置を使用して実装される。ある実施形態では、ハードウェア及びソフトウェア要素の組み合せによってプロセスが実行される。他の適応もなされる。符号化及び復号の機能はCの形態で以下に示されている。
Encoder:
void start_encode() {
encode_slice_header();
while (!byte_aligned)
send_bit(0);
R=0x1fe;
L=O;
BO=0;
FB=1;
}
void finish_encode() {
R=2;
renorm_encode();
bit_plus_follow((L >> 9) & 1);
send_bit((L >> 8) & 1);
send_bit(1); // stop_bit
while (!byte_aligned())
send_bit(0); // alignment_bit
}
voidbit_plus_follow(int b) {
if (FB == 1)
FB = 0;
else
send_bit(b);
while (BO > 0) {
BO--;
send_bit(!b);
}
}
void encode_renorm() {
while (!(R&0x100) {
if (L+R < 0x200)
bit_plus_follow(0);
else if (L >= 0x200) {
bit_plus_follow(1);
L -= 0x200;
}
else {
BO++;
L -= 0x100;
}
R <<= 1;
L <<= 1;
}
}
void encode_event(intctx, int b) {
rLPS = table[state[ctx]][(R>>6)-4];
R -= rLPS;
if (b == MPS[state[ctx]])
state[ctx] = next_state_MPS[state[ctx]];
else {
L += R;
R = rLPS;
if (state[ctx] == 0)
MPS[state[ctx]] = !MPS[state[ctx]];
state[ctx] = next_state_LPS[state[ctx]];
}
encode_renorm();
}
voidencode_equiprob_event(int b) {
L <<= 1;
if (b)
L+=R;
if (L+R < 0x400)
bit_plus_follow(0);
else if (L >= 0x400) {
bit_plus_follow(1);
L -= 0x400;
}
else {
BO++;
L -= 0x200;
}
}
void encode_end_of_slice_flag(intb) {
if (b == O) {
R-=2;
L+=2;
encode_renorm();
}
}
Decoder (bytebased):
void start_decode() {
decode_slice_header();
while (!byte_aligned())
get_bit();
R = 0xff80;
V = get_byte() << 8;
V |= get_byte();
B = 7;
}
void finish_decode() {
while (more_bytes_in_slice())
get_byte(); // stuffing byte
}
void decode_renorm() {
while (R<0x8000) {
R <<= 1;
V <<= 1;
B--;
if (B<0) {
B= 7;
V |= get_byte();
}
}
}
int decode_equiprob() {
V = (V<<1);
B--;
if (B<0) {
V |= get_byte();
B = 7;
}
if (V >= R) {
V -= R;
bit = 1;
}
else
bit = 0;
return bit;
}
int decode_event(intctx) {
rLPS =table[state[ctx]][(R>>13)-4]<<7;
R -= rLPS;
if (V < R) {
state[ctx] = next_state_MPS[state[ctx]];
bit = MPS[state[ctx]];
}
else {
bit = !MPS[state[ctx]];
V -= R;
R = rLPS;
if (state[ctx] == 0)
MPS[state[ctx]] = !MPS[state[ctx]];
state[ctx] = next_state_LPS[state[ctx]];
}
decode_renorm();
return bit;
}
intdecode_end_of_slice_flag() {
if (V < 0x100)
bit = 1;
else {
bit = 0;
R-=0x100;
V-=0x100;
decode_renorm();
}
return bit;
}
Alternative byte-basedend of slice decoding for use when the MPS/LPS convention is switched(MPS/LPSの規定が切り替えられるときに使用される、代替のバイトベースのスライス終了ラグの復号)
intdecode_end_of_slice_flag(){
R -= 0x100;
if (V >= R)
bit = 1;
else {
bit = 0
decode_renorm();
}
return bit;
}
Decoder (bit based):
void start_decode() {
decode_slice_header();
while (!byte_aligned())
get_bit();
R = 0x1fe;
V = 0;
for (i=0; i<9; i++)
V = (V<<1) | get_bit();
}
void finish_decode() {
while (!byte_aligned())
get_bit(); // alignement bit
while (more_bytes_in_slice())
get_byte(); // stuffing byte
}
int decode_renorm() {
while (R<0x100) {
R <<= 1;
V = (V<<1)|get_bit();
}
}
int decode_equiprob() {
V = (V<<1) | get_bit();
if (V >= R) {
V -=R;
bit = 1;
}
else
bit = 0;
return bit;
}
int decode_event(intctx) {
rLPS = table[state[ctx]][(R>>6)-4];
R -= rLPS;
if (V < R) {
state[ctx] = next_state_MPS[state[ctx]];
bit = MPS[state[ctx]];
}
else {
bit = !MPS[state[ctx]];
V -= R; R = rLPS;
if (state[ctx] == 0)
MPS[state[ctx]] = !MPS[state[ctx]];
state[ctx] = next_state_LPS[state[ctx]];
}
decode_renorm();
return bit;
}
intdecode_end_of_slice_flag() {
if (V < 2)
bit = 1;
else {
bit = 0;
R-=2;
V-=2;
decode_renorm();
}
return bit;
}
Alternative bit-basedend_of_slice flag decoding for use when the MPS/LPS convention is switched(MPS/LPSの規定が切り替えられるときに使用される、代替のビットベースのスライス終了フラグの復号)
intdecode_end_of_slice_flag(){
R -= 2;
if (V >= R)
bit = 1
else {
bit = 0;
decode_renorm();
}
return bit;
}
【0132】
[0139] 尚、上述した算術コーダには、上部インターバル及び下部インターバルの2つに分割されるインターバルがある。一方のインターバルは、MPSを表わし、他方のインターバルは、LPSを表わす。一実施形態では、MPS及びLPSをインターバルに割り当てる処理は、一方のインターバルに1を割り当て、他方のインターバルに0を割り当てる処理を含む。上述したソースコードでは、end_of_slice_flagを符号化するためにインターバルが分割される場合に、MPS(値0)が上部サブインターバルに割り当てられる。また、MPSを下部サブインターバルに割り当てることもできる。
【0133】
[0140] 以下のコードは、別のエンコーダ例を示す。尚、このコードでは、Sは、上述したように制限する関係を満足するためのスライスにおける最小バイト数である。
void start_encode() {
send_NAL_first_byte();
encode_slice_header();
while (!byte_aligned())
send_bit(0);
R = 0x1fe; // range
L = 0; // low
BO = 0; // bits outstanding
C = 0; // event counter
FB = 1; // first bit flag
}
void finish_encode() {
bit_plus_follow((L >> 9) & 1);
for (i=8; i>=1; i--)
send_bit((L >> i) & 1);
send_bit(1); // stop_bit
while (!byte_aligned())
send_bit(0); // alignment bit
RBSP_to_EBSP();
S = min_bytes(C,number_of_macroblocks_in_slice);
while (S > bytes_in_NAL_unit())
send_three_bytes(Ox000003); // write bytesdirectly into
NAL unit
}
voidbit_plus_follow(int b) {
if (FB == 1)
FB = 0;
else
send_bit(b);
while (BO > 0) {
BO--;
send_bit(!b);
}
}
void encode_renorm() {
while (!(R&0x100) {
if (L+R < 0x200)
bit_plus_follow(0);
else if (L >= 0x200) {
bit_plus_follow(1);
L -= 0x200;
}
else {
BO++;
L -= 0x100;
}
R <<= 1;
L <<= 1;
}
}
void encode_event(intctx, int b) {
rLPS = table[state[ctx]][(R>>6)-4];
R -= rLPS;
if (b == MPS[state[ctx]])
state[ctx] = next_state_MPS[state[ctx]];
else {
L += R;
R = rLPS;
if (state[ctx] == 0)
MPS[state[ctx]] = !MPS[state[ctx]];
state[ctx] = next_state_LPS[state[ctx]];
}
encode_renorm();
C++;
}
voidencode_equiprob_event(int b) {
L <<= 1;
if (b)
L += R;
if (L+R < 0x400)
bit_plus_follow(0);
else if (L >= 0x400) {
bit_plus_follow(1);
L -= 0x400;
}
else {
BO++;
L -= 0x200;
}
C++;
}
voidencode_end_of_slice_flag(int b) {
if (b == 0) {
R-=2;
L+=2;
encode_renorm();
}
}
【0134】
[0141] 上記コードにおいて、ヘッダの一部分である第1バイトをNALユニットに送信する処理は、後続するデータの形式を指示するために実行される。NALユニット及びその使用法は、この技術分野では周知である。
【0135】
[0142] RBSP_to_EBSP()の関数呼び出しは、データをビットストリームに挿入させる。より好ましくは、一実施形態において、ビットストリームに所定数の連続するゼロが発生するのを防止する方法として、03Hexが0000Hexバイトの後に次のパターン、例えば、000000、000001、000002、000003で挿入される。その結果、000000Hex、000001Hex及び000002Hexのパターンが圧縮されたデータに現われることがなく、これを再同期マーカーとして使用することができる。デコーダが000003Hexパターンに遭遇すると、逆の手順によって「03」がビットストリームから除去される。
【0136】
[0143] 本明細書に説明したエンコーダ及びデコーダのこのような一つの使い方は、ビデオデータを符号化及び復号するものであるが、当業者であれば、本明細書に説明したエンコーダ及びデコーダは、エンコーダの場合にイベントシーケンスが情報シーケンスへ圧縮され、デコーダの場合にその情報シーケンスが圧縮解除されるような任意の場面に使用できることが明らかであろう。更に、エンコーダの上記説明は、多数の2進イベントで構成されたイベントシーケンスを、少なくとも1ビットで構成された情報シーケンスへと処理することに関して述べ、デコーダについては、少なくとも1ビットで構成された情報シーケンスを、多数の2進イベントで構成されたイベントシーケンスへと処理することに関して述べたが、エンコーダ及びデコーダは、当業者に明らかなように、本明細書に説明した教示を利用して、M進(M-ary)性のイベント(即ち、各M進イベントは2ビット以上のデータを表わす)で構成されたイベントシーケンス及び情報シーケンスに対して演算を行うことができる。
【0137】
<コンピュータシステムの例>
【0138】
[0144] 図17は、本明細書に説明された一つ以上のオペレーションを実行することのできるコンピュータシステムの一例を示すブロック図である。尚、これらのブロック又はブロックのサブセットは、本明細書に説明された技術を実行するように、例えば、セルラー電話のような装置に一体化できる。
【0139】
[0145] 図17を参照すれば、コンピュータシステム1700は、情報を通信するための通信メカニズム即ちバス1711と、情報を処理するためにこのバス1711に接続されたプロセッサ1712とを備えている。このプロセッサ1712は、例えば、Pentium(登録商標)、PowerPC(登録商標)、Alpha(登録商標)等のマイクロプロセッサを含むが、これに限定されない。
【0140】
[0146] システム1700は、更に、プロセッサ1712によって実行される情報及び命令を記憶するためにバス1711に接続されたランダムアクセスメモリ(RAM)又は他のダイナミック記憶装置1704を備えている。また、このメインメモリ1704は、プロセッサ1712によって命令を実行する間に一時的な変数又は他の中間情報を記憶するために使用されることができる。
【0141】
[0147] また、コンピュータシステム1700は、プロセッサ1712用のスタティック情報及び命令を記憶するためにバス1711に接続されたリードオンリメモリ(ROM)及び/又は他のスタティック記憶装置1706と、磁気ディスク又は光学ディスク及びそれに対応するディスクドライブのようなデータ記憶装置1707とを備えている。このデータ記憶装置1707は、情報及び命令を記憶するためにバス1711に接続される。
【0142】
[0148] コンピュータシステム1700は、更に、コンピュータのユーザに情報を表示するためにバス1711に接続された陰極線管(CRT)又は液晶ディスプレイ(LCD)のようなディスプレイ装置1721にも接続される。また、アルファニューメリック及び他のキーを含むアルファニューメリック入力装置1722も、情報及びコマンドの選択をプロセッサ1712へ通信するためにバス1711に接続される。更に別のユーザ入力装置は、マウス、トラックボール、トラックパッド、スタイラス、又はカーソル方向キーのようなカーソル制御器1723であり、これは、方向情報及びコマンド選択をプロセッサ1712と送受すると共に、ディスプレイ1721上のカーソル移動を制御するためにバス1711に接続される。
【0143】
[0149] バス1711に接続される別の装置は、ハードコピー装置1724である。ハードコピー装置1724は、命令、データ又は他の情報をペーパーやフィルムのような媒体や同様の形式の媒体にプリントするために使用される。更に、スピーカ及び/又はマイクロホンのような音声記録及び再生装置も、コンピュータシステム1700と音声インターフェイスするようにバス1711に任意に接続できる。バス1711に接続できる別の装置は、電話、ハンドヘルド式の手のひら装置又は他の装置と通信するための有線/無線通信装置1725である。
【0144】
[0150] 尚、システム1700のいずれか又は全部の要素及びそれに関連したハードウェアを本発明に適用できる。しかしながら、当該コンピュータシステムの他の構成は、上記デバイスの幾つか又は全てを含められることは明らかであろう。
【0145】
[0151] 当業者であれば、以上の説明を読んだ後、本発明の多数の変更や修正が明らかとなるであろうが、図示して説明した特定の実施形態は、本発明を限定するためのものではないことを理解されたい。それ故、種々の実施形態の詳細な説明は、本発明の本質とみなす特徴のみを記載した特許請求の範囲を何ら限定するものではない。
【符号の説明】
【0146】
100…システム、102…エンコーダ、104…デコーダ、300…データフォーマット、302…ヘッダ、303…ストップビット、304…算術符号、306…ストップビット、308…整列ビット、310…スタフィングバイト、400…算術エンコーダ、405…シーケンサ、410…確率推定器、415…符号化エンジン、465…レンジレジスタ、470…ローレジスタ、475…ビットアウトスタンディングレジスタ、480…カウンタレジスタ、1000…算術デコーダ、1005…シーケンサ、1010…確率推定器、1015…復号エンジン、1065…レンジレジスタ、1070…値レジスタ、1700…コンピュータシステム、1704…メインメモリ、1706…スタティック記憶装置、1707…データ記憶装置、1711…バス、1712…プロセッサ、1721…ディスプレイ装置、1722…アルファニューメリック入力装置、1723…カーソル制御器、1724…ハードコピー装置、1725…通信装置。
【版権について】
【0001】
[0001] この特許文書の開示の一部分は、版権保護を受ける資料を含む。版権所有者は、如何なる者が特許文書又は特許開示を特許商標庁の特許ファイル又は記録に残るように複写することに異議を唱えるものではないが、それ以外は、全ての版権権利が保護されるものとする。
【優先権】
【0002】
[0002] 本特許出願は、2002年9月20日に出願された「TERMINATION OF ARITHMETIC CODING AND BYTE STUFFING」と題する対応の仮特許出願第60/412,245号、及び2002年10月4日に出願された「CABAC CLEANUP AND COMPLEXITY REDUCTION」と題する仮特許出願第60/415,000号に対する優先権を主張する。
【技術分野】
【0003】
[0003] 本発明は、広く、情報理論、ビデオ圧縮及び算術符号化に関する。より詳細には、本発明は、バイトスタフィング(byte stuffing)及び算術符号化の終了を行うと共に、算術符号化中に状態マシンを生成して使用する方法及び装置に関する。
【背景技術】
【0004】
[0004] データ圧縮は、大量のデータの記憶及び送信に非常に有用なツールである。例えば、文書のネットワーク送信のような画像の送信に必要な時間は、圧縮を用いて画像の復元に必要なビット数を減少させると、大幅に短縮される。
【0005】
[0005] 先行技術には、多数の異なるデータ圧縮技術が存在する。圧縮技術は、非可逆符号化(lossy coding)及び可逆符号化(losslesscoding)の2つの広いカテゴリーに分類される。非可逆符号化とは、情報のロスを招く符号化であり、オリジナルデータの完全な再構成が保証されない。非可逆圧縮の目標は、オリジナルデータに対する変更を、それが支障のないように又は検出されないように行うことである。可逆圧縮では、完全な再構成が可能な方法でデータが圧縮され、全ての情報が維持される。
【0006】
[0006] 算術符号化は、周知の圧縮技術であり、送信に必要なビット又はシンボルの数を削減するために幾つかのデータ符号化・圧縮システムに使用されている。算術エンコーダは、イベント(例えば、2進イベント)又はシンボルのシーケンスを含む入力を受信する。このエンコーダは、入力シーケンスを符号化して、対応のビット又はバイトシーケンスとする。ある場合には、エンコーダの入力に受信されたものより少数のデータビットをエンコーダの出力に発生させることによって、データを圧縮する。算術デコーダは、符号化データを受信し又はそれにアクセスすることができる。算術デコーダは、符号化データのシーケンスを読み取って、復号データを生成するが、これは、デコーダに受信された入力シンボルに一致しなければならない。圧縮は、符号化されているイベントに対して情報シーケンスに少数のビットを発生させることによって達成される。イベントと、符号化されている情報ビットとの比は、イベントの確率分布にもよるが、64:1又は128:1にも達し得る。
【0007】
[0007] デコーダのオペレーションは、エンコーダのオペレーションと対称であることが好ましい。エンコーダとデコーダのオペレーションが対称であるならば、デコーダで読み取られる符号化データのビット数は、エンコーダによって生成された符号化ビットの数に一致する。
【0008】
[0008] ある算術デコーダでは、復号オペレーションを開始する際に、デコーダがビットのグループを先読みする。しかしながら、デコーダがビットのグループを先読みするので、不一致又は非対称性が生じ得る。
【0009】
[0009] この非対称性を補償するための従来の一解決策では、エンコーダにおいて符号化データに余分なビットを追加している。別の従来の解決策では、追加の符号化ビットを発生させず、デコーダにおいて、符号化データのビットストリームを先読みした後、後戻りさせている。
【発明の概要】
【発明が解決しようとする課題】
【0010】
[0010] これら従来の解決策は、両者ともに、効率が悪い。符号化アルゴリズム及び復号アルゴリズムの複雑さを低減し、符号化、送信、及び復号を行うデータを減らし、更に、記憶の必要性を緩和するために、より効率の良い解決策が要望されている。
【課題を解決するための手段】
【0011】
算術符号化及び/又は算術復号を実行する方法及び装置を開示する。一実施形態において、データ符号化方法は、イベントシーケンスにおける複数のイベントを符号化して、符号化データを生成するステップと、当該符号化データを用いてビットストリームを生成するとともに、当該符号化データの後のビットストリームにゼロ以上のスタフィングビットを追加することを含むステップとを備える。当該ゼロ以上のスタフィングビットは、符号化されたイベントの量と、符号化されているブロックの数と、ビットストリームにおけるビットの数との間の関係を実質的に維持するように機能する。
【0012】
別の実施形態において、算術デコーダは、イベントシーケンスのイベントに対してコンテクスト識別子を生成するシーケンサと、LPSの値及びLPSの確率推定値を決定する確率推定器と、LPSのレンジに値を割り当てるレンジレジスタを含む復号エンジンとを備えている。コンテクスト識別子がインデックスに等しくない場合に、当該値は、LPSの確率推定値と、レンジレジスタに記憶された値と、LPSのレンジへのコンテクスト識別子とに基づき、また、コンテクスト識別子がインデックスに等しい場合に、当該値は、レンジレジスタに記憶された値に基づかない。復号エンジンは、更に、LPSのレンジの値及び情報シーケンスからのビットに基づいて2進イベントの値を決定する。
【0013】
他の実施形態において、確率推定のための状態マシンを生成する方法は、ルックアップテーブル(LUT)の状態に確率を割り当てるステップを含み、このステップは、所与の状態の番号をiとし、かつ、適応レートが1より小さいとする場合に、各状態iに対する確率を、適応レートのi乗が乗算されたLPSの最大確率に等しくセットする処理を含む。この方法は、また、MPS及びLPSを観察して、遷移されるべきLUTの状態に対する状態遷移を発生させるステップを備え、MPSが観察されたときに現在の状態から状態マシンが遷移する次の状態を、当該現在の状態が最も高い状態でない場合に現在の状態より高い次の状態とし、当該現在の状態が最も高い状態である場合に当該現在の状態とする。更に、複数の状態に対しLPSが観察されたときに現在の状態から状態マシンが遷移する次の状態は、
現在の状態の番号+log((現在状の態の確率*適応レート+(1−適応レート))/現在の状態の確率)/log(適応レート)
の計算結果が丸められた値となる。
【0014】
[0011] 本発明は、本発明の種々の実施形態を示す添付図面及び以下の詳細な説明から完全に理解されるであろうが、これは、本発明を特定の実施形態に限定するものではなく、本発明を例示し理解するためのものに過ぎない。
【図面の簡単な説明】
【0015】
【図1】符号化及び復号システムの実施形態のブロック図である。
【図2】ビットストリームを生成するための符号化プロセスのフロー図である。
【図3】図1のシステムにおいて送信することのできる符号化データのデータフォーマットの一例を示す図である。
【図4】算術エンコーダの一実施形態のブロック図である。
【図5】イベントの符号化に関する一実施形態のフロー図である。
【図6】エンコーダ再正規化手順の一実施形態のフロー図である。
【図7】プットビット手順の実施形態を実行するプロセスの一実施形態を示す図である。
【図8】終了前にイベントを復号するプロセスの一実施形態を示すフロー図である。
【図9】終了時のフラッシュに係るプロセスの一実施形態を示すフロー図である。
【図10】算術デコーダの一実施形態を示すブロック図である。
【図11】算術デコーダの初期化プロセスの一実施形態を示すフロー図である。
【図12】2進イベントを復号するプロセスの一実施形態を示すフロー図である。
【図13】再正規化手順のフロー図である。
【図14A】同じ確率で2進イベントを復号するためのフロー図の一つである。
【図14B】同じ確率で2進イベントを復号するためのフロー図の一つである。
【図15A】終了前にスライス終了フラグ又は他の2進イベントを復号する実施形態を示すフロー図の一つである。
【図15B】終了前にスライス終了フラグ又は他の2進イベントを復号する実施形態を示すフロー図の一つである。
【図16A】確率推定ルックアップを実行するためのテーブルの一例である。
【図16B】確率推定ルックアップを実行するためのテーブルの一例である。
【図17】コンピュータシステムの一例を示すブロック図である。
【発明を実施するための形態】
【0016】
[0029] 以下、情報、特にビデオデータを符号化及び復号する方法及び装置について説明する。符号化及び復号中に、算術符号化されているイベントの終了を知らせるために、インジケータ(例えば、スライスの終了)が使用される。一実施形態では、情報の符号化中に、エンコーダによって生成される符号化データのビットストリームに、数ビット又は数バイトのスタフィング情報が追加される。これら追加のビットを符号化データのビットストリームの中間にスタフィングするのではなく、スタフィングバイト(又はビット)を、符号化データの最後に追加する。このようなスタフィングを使用することによって、符号化されているイベントの数と、ビデオデータのブロック(例えばマクロブロック)の数と、生成されている情報シーケンスのサイズとの間の関係を維持することができる。
【0017】
[0030] 以下、本発明をより完全に説明するために多数の細部について述べる。しかしながら、当業者であれば、これら特定の細部がなくとも本発明を実施できることが明らかであろう。他の例では、本発明を不明瞭にしないために、周知の構造及び装置を、詳述する代わりに、ブロック図形態で示す。
【0018】
[0031] 以下の詳細な説明では、コンピュータメモリ内のデータビットに対する操作のアルゴリズム及び記号表示の形で記載している部分がある。これらのアルゴリズム記述及び表示は、データ処理分野の当業者によって、当該当業者の仕事の実体をその分野の他の当事者に最も効果的に伝達するために使用される手段である。アルゴリズムとは、ここにおいても、且つ一般においても、所望の結果を導く自己一貫性のあるステップのシーケンスであると考えられる。ステップとは、物理的な量の物理的な操作を要求するものである。必ずしもそうでないが、通常、これらの量は、記憶、転送、合成、比較、及びその他操作を行うことができる電気的又は磁気的信号の形態をとる。主として一般に使用される理由は、これらの信号を、ビット、値、エレメント、シンボル、キャラクタ、用語、番号等として参照することが時に便利であるとわかっているからである。
【0019】
[0032] しかしながら、これら及び同様の全ての用語は、適切な物理量に関連付けられており、これらの量に適用される単なる便利な表示に過ぎないことに留意されたい。以下の説明から明らかなように、特に指示のない限り、説明全体にわたり、「処理」又は「計算」又は「算出」又は「決定」或いは「表示」等の用語を用いた説明は、コンピュータシステムのレジスタ及びメモリ内の物理(電子)量として表わされたデータを、コンピュータシステムのメモリ又はレジスタ或いは他の情報記憶、送信又は表示装置内の物理的量として同様に表わされた他のデータへと操作及び変換するコンピュータシステム、又は同様の電子計算装置のアクション及びプロセスを指すことは理解されよう。
【0020】
[0033] また、本発明は、本明細書に記載されたオペレーションを実行する装置に関する。この装置は、要求された目的のために特別に構成されてもよく、又はコンピュータ内に記憶されたコンピュータプログラムによって選択的に起動され又は再構成される汎用コンピュータを備えてもよい。このようなコンピュータプログラムは、コンピュータ読み取り可能な記憶媒体、例えば、フロッピーディスク、光学的ディスク、CD−ROM、磁気−光学ディスクを含む任意の形式のディスク、リードオンリメモリ(ROM)、ランダムアクセスメモリ(RAM)、EPROM、EEPROM、磁気又は光学カード、或いは電子的命令の記憶に適した任意の形式の媒体に記憶され得るが、これらに限定されない。これらは各々、コンピュータのシステムバスに接続される。
【0021】
[0034] 本明細書に記載したアルゴリズム及び表示は、特定のコンピュータ又は他の装置に固有に関連するものではない。本明細書の教示に基づくプログラムと共に種々の汎用システムを使用することができ、また、要求の方法のステップを実行するための更に特殊な装置を構成することも便利であることは理解されよう。種々のこれらシステムに必要とされる構造は、以下の説明から明らかとなろう。更に、本発明を、特定のプログラミング言語を参照して説明していない。本明細書に記載された本発明の教示を実施するために、種々のプログラミング言語を使用できることは明らかであろう。
【0022】
[0035] マシン読み取り可能な媒体は、マシン(例えばコンピュータ)で読み取りできる形態で情報を記憶又は転送するためのメカニズムを含む。例えば、マシン読み取り可能な媒体は、リードオンリメモリ(ROM)、ランダムアクセスメモリ(RAM)、磁気ディスク記憶媒体、光学記憶媒体、フラッシュメモリデバイス、電気的、光学的、音響的又は他の形態の伝播信号(例えば、搬送波、赤外線信号、デジタル信号等)、等々を含む。
【0023】
<符号化及び復号システムの概要>
【0024】
[0036] 図1は、符号化及び復号システム100の実施形態のブロック図である。図1に示すように、システム100は、チャンネル120を介して通信するエンコーダ102及びデコーダ104を備えている。これに代えて、システム100は、エンコーダ102又はデコーダ104だけを備えてもよい。
【0025】
[0037] チャンネル120は、有線チャンネル、無線チャンネル又はそれらの組合せを含む相応のデータ通信チャンネルとすることができる。チャンネル120には、適当なデータ通信及び変調機構が使用される。システム100の一例は、画像のシーケンスを含むビデオデータを符号化し、圧縮し、復号するためのシステムである。一実施形態では、各ピクチャーは、一つ以上のスライスに分割される。
【0026】
[0038] エンコーダ102は、入力データ(例えばビデオ情報)といった入力情報を受信する入力106を有する。一実施形態では、エンコーダ102は、算術符号化を使用してデータを符号化する。したがって、エンコーダ102は、データ記憶部、操作レジスタ、及び算術符号化エンジンを備えている。一実施形態では、エンコーダ102は、レンジレジスタ、即ちRレジスタと、ロー(Low)レジスタ、即ちLレジスタとを含む。更に、一実施形態では、エンコーダ102は、確率推定状態マシンを含む。エンコーダ102によって実行される符号化アルゴリズムは、当該技術において周知のコンテクスト適応二値算術符号化であり、本明細書ではCABACと称している。また、本明細書に記載された技術及び構成を、他の符号化及び復号のアルゴリズム並びに手順に拡張することもできる。エンコーダ102は、符号化データをチャンネル120へ供給する出力108を有する。
【0027】
[0039] 一実施形態において、エンコーダ102は、算術符号化データの終了を指示する符号化イベント(例えば、決定(decision))を含む符号化データのビットストリームを生成する。一実施形態において、算術符号化データの終了を示すイベントは、スライス終了フラグを含む。また、ビットストリームは、より詳細には以下に述べるスタフィングバイト(又はビット)を含んでもよい。
【0028】
[0040] デコーダ104は、チャンネル120から符号化データを受信する入力110と、復号データを供給する出力112とを有する。一実施形態において、符号化データを復号するためのデコーダ104のオペレーションは、エンコーダ102の符号化のオペレーションと概ね対称である。尚、システム100は、2つ以上のエンコーダ及び/又は2つ以上のデコーダを備えてもよい。
【0029】
[0041] エンコーダ102及びデコーダ104は、ビデオデータ、例えば、ビデオプロセッサ(例えばビデオコーデック)によって生成されたビデオデータの処理に使用される。一実施形態では、ビデオ画像は、記録され、当該記録された画像の16×16、8×8又は4×4のサンプルを表すデータのサンプルブロックに分割される。これらブロックは、次いで、ビデオプロセッサによって(例えば、離散コサイン変換を使用して)変換、量子化されて、サンプルブロックを表す整数値が得られる。これら整数値は、ビデオプロセッサによってイベント(例えば2進イベント)のシーケンスに変換され、エンコーダへ送られて、符号化される。或いは又、ビデオプロセッサは、個々のサンプルを直接操作してもよく、この操作は、サンプルを変換及び量子化し、サンプルに対する個別の量子化整数値をイベントシーケンスに変換する処理を含むものであってもよい。
【0030】
[0042] 図2は、ビットストリームを生成するための符号化プロセスのフロー図である。このプロセスは、処理ロジックによって実行される。当該処理ロジックは、ハードウェア(例えば、回路、専用ロジック等)、ソフトウェア(例えば、汎用コンピュータシステム又は専用マシンで実行されるソフトウェア)或いはその両方の組合せによって構成され得る。
【0031】
[0043] 図2に示すように、この処理ロジックは、イベントシーケンス内のイベントを符号化して、符号化データを生成する(処理ブロック201)。イベントは、2進決定(binary decision)とすることができる。また、イベントは、同じスライスからのものであってもよい。一実施形態では、イベントの一つは、算術符号化の終了(例えば、スライスの終了)を指示する。次いで、処理ロジックは、全てのイベントに対する符号化データと、それに続くスタフィングバイト(又はビット)とをもつビットストリームを生成する(処理ロジック202)。このスタフィングバイト(又はビット)は、ビットストリームにおいて、算術符号化の終了を指示する符号化インジケータの後に入れられる。
【0032】
[0044] 図3は、符号化データを、図1のシステムのようなシステムにおいて送信することのできる例示のデータフォーマット300を示す。フォーマット300は、ヘッダ302と、算術符号304と、一つ以上のストップビット306と、0,1又はそれより多くの整列ビット308と、0,1又はそれより多くのスタフィングバイト310とを含む。別の実施形態では、0,1又はそれ以上のスタフィングビットをバイトに代えて使用することができる。
【0033】
[0045] 上述したように、図1のシステム及び図3のデータフォーマットを使用して、ピクチャーのシーケンスに関連するデータを含むビデオ情報の符号化及び送信を行うことができる。一実施形態では、ピクチャーが一つ以上のスライスに分割される。ここで、1スライスは、16×16ピクセルのアレーのマクロブロックを一つ以上含む。各スライスは、ピクチャー内の他のスライスと独立して符号化される。ピクチャーデータは、図3に示すフォーマットで符号化される。
【0034】
[0046] 一実施形態では、ヘッダ302は、バイト境界で始まり、固定長符号又は可変長符号のいずれかを用いて符号化(例えば、ハフマン符号化)されたデータを含む。ヘッダ302は、スライスヘッダとすることができる。スライスヘッダの場合に、ヘッダ302の前に、スタートコード(SC)と、その次に続くスライスデータの形式を識別するインジケータとを設けることができる。
【0035】
[0047] 算術符号304は、エンコーダ102(図1)のようなエンコーダの算術符号化エンジンによって生成されたビットのシーケンスである。一実施形態では、ビットのシーケンスがバイト境界でスタートする。一つ以上のストップビット303が、算術符号304に続く。別の実施形態では、ストップビット303が算術符号304に含まれてもよい。幾つかの(0から7)の後続の整列ビット308がストップビット306に続き、一実施形態では、スタフィングバイト310のバイト整列を保証する。データに追加されるスタフィングバイト310の数は、符号化されているイベントの数と、ビデオデータのブロック(例えばマクロブロック)の数と、生成された情報シーケンスのサイズとの間の関係を維持することに要するバイト数に基づいて、0バイト、1バイト又は2バイト以上にすることができる。
【0036】
<コードストリームの終了>
【0037】
[0048] 一実施形態では、エンコーダは、算術符号化データの終了をデコーダに指示するイベント(例えば決定)を符号化する。算術符号化データの終了は、スライスの終了に達したときに指示されてもよい。また、算術符号化データの終了は、ビットストリームにおける算術符号化データがストップし、その後に非算術符号化データが続くときにも発生させてもよい。
【0038】
[0049] 図3に戻り、一実施形態では、スライス内の各マクロブロックに対して、算術符号204は、典型的には、以下のデータ、即ちマクロブロックモード、任意に動きベクトル及び変換係数、並びにend_of_slice_flagを含む。このend_of_slice_flagによって、デコーダ104(図1)がスライス内の最後のマクロブロックがいつ復号されたかを画定することが可能となる。このフラグが使用されるのは、算術符号の最終ビットが、2つ以上のマクロブロックを記述するデータを含む可能性があるからである。
【0039】
[0050] 算術符号化データの終了を符号化することの利点は、従来の手法を検討することによって説明できる。従来の手法では、算術エンコーダの終了は、通常、2つの代案のうちの一方に基づいて行われる。第1のアプローチでは、そのままのレジスタLが送信される。第2のアプローチでは、レジスタLのコンテンツにオフセットが追加され、レジスタLの最上位ビットだけが送信される。第1のアプローチの利点は、デコーダが、エンコーダによって生成されたものと同数のビットを正確に読み取ることである。しかしながら、これによって、余分なビットを送信するという損失がもたらされる。第2のアプローチでは、ビットは節約されるが、デコーダは、エンコーダによって生成されたものより多くのビットを読み取る。これは、デコーダでビットストリームにパディングを行うことによって克服することができる。
【0040】
[0051] 本明細書に開示するアプローチは、両者の最良な点を供する。即ち、デコーダはエンコーダによって生成されたものと同数のビットを読み取り、エンコーダには必要以上のビットを送信させない。これは、イベント、即ちend_of_slice_flagを符号化して、スライスの終了を知らせることによって可能となっている。良好に定められた確率がこのイベントに割り付けられると、デコーダはそれを復号でき、当該イベントの結果が終了を知らせる場合に、デコーダは再正規化を先行することができる。即ち、通常、符号化中に、符号化される全てのシンボルについて、値Rに確率が乗算されて、サブインターバルが得られる。その後、再正規化が行われて、Rの値がある範囲の値に戻される。再正規化は、算術符号化の当業者に周知である。再正規化を先行することによって、読み取られるビットの数がエンコーダによって生成されるビットの数に一致することが保証される。
【0041】
[0052] 一実施形態では、end_of_sliceイベント(又は算術符号化の終了を指示する他のイベント)に割り当てられる確率は、符号化の終了中にレジスタRに割り当てられた数値によって、再正規化が実行される前に、定められる。一実施形態では、エンコーダとデコーダとが同期することを保証するために、スライス終了フラグに対して、サブインターバルの計算は、Rに記憶された値に確率を乗算することによって実行されない。代わりに、サブインターバルには、固定値、即ち定数が割り当てられる。一実施形態では、固定値2が使用される。より一般的には、end_of_slice_flagを符号化する前に、この値は、レジスタRのコンテンツの値とは独立していなければならない。これは、ビットストリームに入れられる最後のシンボル(ビット)のために行われる。サブインターバルを値2に設定することによって、デコーダのオペレーションに影響なく、値1をレジスタLの値に加算することができる。これによって、ロー(L)レジスタ全体のコンテンツをビットストリームに送り込むことが可能となる。全レジスタLのコンテンツが送信されるので、この例では再正規化が不要である。
【0042】
[0053] 一実施形態では、レジスタLの最下位ビットを1に設定して、Lのコンテンツを送信する。レジスタLの最下位ビットを1に設定することは、その最下位ビットがゼロである場合にLに1を加算することと等価である。したがって、算術エンコーダによって生成される最終ビットは1に等しく、算術符号を含むビットストリームの最終バイトは非ゼロの値を有する。結果において、レジスタLの最下位ビットは、ストップビットとなる。
【0043】
<スタフィングバイトの追加>
【0044】
[0054] 一実施形態では、エンコーダは、圧縮されたデータのビットストリームにスタフィングバイト又はビットを挿入する。一実施形態では、スタフィングバイトは、スライスの算術符号の後に、ストップビット及び0、1又はそれ以上の整列ビットに続いて挿入される。整列ビットを挿入して、追加されるスタフィングバイトがバイト境界に挿入されることを保証する。ストップビットの後にスタフィングバイトを入れることの利点の一つは、デコーダがスタフィングバイトを復号する必要がないことである。したがって、デコーダは、エンコーダによって生成された符号化データのビット数と同数のビットを復号する。
【0045】
[0055] 一実施形態では、圧縮されたビットストリームに挿入されるスタフィングバイトの数は、エンコーダに入力されるイベントの数と、データブロックの数と、エンコーダから出力されるビットの数との間の関係を維持することに基づいている。この関係を、より詳細に以下に説明する。
【0046】
[0056] 一実施形態では、スタフィングバイトが特定のパターンを有している。このパターンは、ユニークであり、デコーダは、スタフィングバイトが存在することを、ストップビット及び一つ以上の整列ビットに続くこの特定パターンのビットを識別することによって、決定することができる。このような決定がなされると、デコーダは、スタフィングバイトを復号する必要がない。一実施形態では、デコーダは、デマルチプレクス機能を有しており、この機能は、ヘッダビット(ヘッダビットは復号エンジンへ送信されない)と同様に、スタフィングバイトがデコーダの算術復号エンジンへ送信されることを防止する。
【0047】
[0057] 一実施形態では、スタフィングビットのパターンは、16進表記で000003の3バイトシーケンスであり、当該バイトシーケンスがビットストリームに追加される。最初の2バイトは、ゼロワード(0000)となっており、第3バイト(03)は、スライスの終了の後に、デコーダによって認識され、当該バイトがスタフィングバイトとして識別される。
【0048】
[0058] 一実施形態では、スライスの終了に詰め込まれたスタフィングバイト310の数は、算術復号のオペレーション数とビット数との関係が4以下であることを保証する。図1のエンコーダ102のようなエンコーダは、レジスタCを使用して、イベント(復号オペレーション)対ビット(又はバイト)の比をカウントし、さもなければ、追跡することができる。イベントが処理されるたびに、カウンタCが1増加され、更に、ビットが生成されるたびに、カウンタCが4(又はバイト生成のたびに32)減らされる。一実施形態では、カウント処理は、ヘッダ及びそれに後続するストップ及び整列ビットを含むスライス(又は他のイベントセット)の全ビットを考慮に入れている。
【0049】
[0059] 一実施形態では、end_of_slice_flagに対する復号オペレーションは、カウンタCによってカウントされない(代替の方法ではカウントされるが)ことに注意されたい。しかしながら、マクロブロック当たり一つのこのようなイベントがあり、このようなイベントの数は、ピクチャーサイズによって良好に制限されることが知られている。この場合、end_of_slice_flagイベントをカウントしないことは、それらをカウントする(故に、マクロブロックごとに一度、Cを1増加する)が、同時に、256ピクセルごとに(マクロブロックごとに一度)Cを1減少させることと等価である。或いは又、マクロブロックごとにCを任意の値だけ減少させることもできる。
【0050】
[0060] 一実施形態では、本明細書に記載された手法でスタフィングバイトを追加すると、符号化されたスライスの最小長さが保証される。符号化されたスライスの中間にスタフィングビットを挿入する従来の技術に対し、この進歩によって、エンコーダがデータを符号化する規定、特に、どれほど多くのデータを符号化するかを定める規定が簡単になる。
【0051】
[0061] エンコーダは、イベントシーケンスにおけるイベントの数を、情報ビットのシーケンスにおける情報ビットの数と、イベントシーケンスで表わされた入力データのセグメント数、即ちブロック数との関数として制約する。例えば、この制約は、次のような線形結合の形態をとる。
e≦αB+βS
ここで、eは、情報ビット(又は他のエレメント)のシーケンスで表わされたイベントの数であり、Bは、情報ビット(又は他のエレメント)のシーケンスにおける情報ビットの数であり、Sは、イベントシーケンスで表わされたセグメント(例えばマクロブロック)の数である。また、α及びβは、カウンタへの減少値を表しており、生成される情報ビットの数及び処理されるセグメントの数に対するイベントシーケンスのイベント数の制約を実質的に維持する。
【0052】
[0062] α及びβの値は、通常、算術コーダのコントローラへ提供される。α及びβの導出について以下に説明する。αの値は、例えば、算術コーダにおいて情報ビットを生成する際のカウンタへの減少値を表わす。一方、βの値は、例えば、データブロックの処理が完了した際のカウンタへの減少値を表わす。別の形態では、当業者には明らかなように、値βを、セグメントの処理の開始時に又はデータブロックの処理中の他の任意の時間にカウンタ値から減少させてもよい。
【0053】
[0063] 全ブロック数S及び値βは既知であるから、β×Sの積を、入力データのブロック(例えばマクロブロック)の処理後にイベントシーケンスのイベントの数eから減算してもよい。例えば、カウンタを使用して、生成されたビットの数に応じてイベントの数を制約する場合に、当該カウンタを、最初にβ×Sの値だけ減少させ、情報ビットが生成されるたびに値αだけ減少させ、一方、イベントシーケンスの各イベントがエントロピーエンコーダによって処理される度に、「1」だけ増加させる。
【0054】
[0064] βの値は、通常、1から100までの範囲内の任意の値であることができ、例えば、以下に述べるように、決定される。αの値は、通常、1から10までの範囲内の任意の値であり、例えば、以下に述べるように決定される。
【0055】
[0065] ある環境において、例えば、通信媒体が、情報シーケンスに与えられる情報ビットの数を制限する場合には、処理されるべき入力データのブロック数が前もって分からない。これは、例えば、情報シーケンスがインターネットプロトコル(IP)パケットとしてインターネットを経て送信されるものであって、このIPパケットが最大サイズ制限を有する場合に生じる。これらの環境では、個別の画像の複雑さに依存するが、一つ以上の情報ビットのシーケンスが、入力データの一画像を表わすために、必要となる。しかしながら、情報ビットのシーケンスの生成に使用されるブロックの数は、前もって分からない。その理由は、どれほど多くのセグメントを処理した後に情報ビットシーケンスの最大サイズに達するか分からないからである。処理されるべき入力データのセグメント数が前もって分からない場合には、コントローラは、個別のイベントシーケンスを表す一つ以上のブロックが符号化されるときに、イベントシーケンスを考慮する。例えば、カウンタを使用し、生成されたビットの数に応じてイベントの数を制約する場合には、当該カウンタを、各ブロックが処理されるたびに値βだけ減少させ、情報ビットが生成されるたびに値αだけ減少させ、一方、イベントシーケンスのイベントがエントロピーエンコーダによって処理される度に「1」だけ増加させる。
【0056】
[0066] α及びβの値は、エンコーダのシステム設計者が上述した一つ以上の制限を考慮することによって前もって決定されて、コントローラに与えられてもよい。これに代えて又はこれに加えて、α及びβの値は、上述した制限の一つ以上に基づいて、又はエンコーダのデフォルト値として、コントローラ、又はエンコーダの他の要素によって、決定されてもよい。コントローラが、規格又は復号装置によって課せられる制限の一つ又は両者を使用してα及びβの値を決定する場合に、一つ以上の当該制限に関する情報がコントローラのメモリ(図示せず)に記憶され、α及びβの値を決定する際にコントローラによって使用される。加えて又はこれに代えて、当該制限に関する情報は、例えば、外部メモリ(即ちデジタルビデオディスク(DVD))や、DVDプレーヤ装置のような外部装置によって、或いは、例えば特定の入力データの符号化に関する幾つかの機能を取り扱うシステムエンジニアから、コントローラへ供給されてもよい。後者の場合に、システムエンジニアは、当業者には明らかなように、符号化規格及び/又は復号装置によって課せられる制限に関する情報をコンソール又は他の入力装置(図示せず)に入力することができ、又は、他の方法で指定することができる。
【0057】
[0067] 更に、α及びβの値を決定する場合に、複雑さの制約が厳し過ぎるかどうか、例えば、α及び/又はβの値が低過ぎるかどうかを考慮してもよい。情報ビットシーケンスの終端に存在するスタフィング情報ビットの割合が高いこと(即ち、スタフィングバイト(又はビット)の数が情報シーケンスの情報ビットの約1%又は2%以上であること)は、その制約が厳し過ぎることを示す。当業者であれば、例えば、使用できる特定の規格及び/又はデコーダを考慮に入れて、他の割合がスタフィング情報ビットの高い割合を示してもよいことは明らかであろう。
【0058】
[0068] 例えば、α及びβの値が制約を過度に厳しくすると決定された場合に、α及びβの値を高くして、スタフィングバイトが追加される見込みを低減する(即ち、符号化情報シーケンスにおけるクオリティペナルティの見込みを低減する)ことができる。α及びβの値を高くする場合には、符号化された情報シーケンスの復号に使用されるデコーダについて得られる複雑さの限界に対してその影響が考慮される。このような考慮は、デコーダを実施するためのコストを含むことができる。複雑さの限界が高い場合には、より大きな処理能力がデコーダに必要とされる。必要な処理能力の増加は、おそらく高い実施コストを招く。尚、一実施形態では、各マクロブロックからデータを符号化した後にα及びβの変更がなされてもよい。
【0059】
[0069] α及びβの値は、線形回帰技術を使用して実験的に決定することができる。各々がS個のセグメントを表すイベントシーケンスが、複雑さの制約を強いることなく、符号化されてもよい。イベントシーケンスzごとに、イベント数e(z)に対し、生成される情報ビット数B(z)が分かる。これは、線形回帰式、即ちデータ対(e(z)、B(z))を近似する線e+c*B+dを使用して決定することができる。したがって、線e=α*β+β*Sの上に存在するデータ対(e(z)、B(z))の数を減らし、潜在的にはそれを最小にするように、α及び/又はβの初期値を高くすることができる。
【0060】
[0070] 上述した種々の技術の一つ以上によって決定されたα及びβの値を使用して、エンコーダは、生成される各情報ビットに対しαの値を考慮し(即ち、αの値だけカウンタを減少させ)、入力データのセグメントが完了した際にβの値を考慮する(即ち、βの値だけカウンタを減少させる)ことができる。例えば、α及びβが整数値である場合には、このような考慮(即ち、一つ以上のカウンタに対する減少)を直接行うことができる。
【0061】
[0071] 例えば、α及びβの一方又は両方が分数値である場合には、共通の分母を決定して、α及びβの非分数値を与えることができる。この環境では、α及びβの新たな非分数値は、例えば、情報ビットの発生時及びセグメント処理の完了時に各々α及びβの値だけカウンタを減少させることによって、上述したように考慮される。決定された共通の分母は、例えば、イベントシーケンスにおける各イベントを処理する際に共通の分母の値をカウンタ値に加算することによって考慮される。例えば、α及びβの値が各々4/3及び25と決定された場合には、共通の分母は、3と決定される。したがって、α及びβの非分数値は、共通の分母を使用して各々4及び75と決定される。したがって、カウンタを使用してα及びβの値を考慮する場合には、カウンタを、情報ビットが発生されるたびに4だけ減少させ、各セグメントの処理が完了すると75だけ減少させ、更に、イベントが処理されるたびに3だけ増加させる。
【0062】
<エンコーダのオペレーションの例>
【0063】
[0072] 図4は、算術エンコーダの一実施形態のブロック図である。図4に示すように、算術エンコーダ400は、シーケンサ405と、確率推定器410と、符号化エンジン415とを備え、これらは互いに接続されている。一つ以上の入力データライン420は、エンコーダ400にイベントシーケンス425(例えば、2進イベントの順序付けされたシーケンス)を受信するための入力ポートを備えている。イベントシーケンスは、エンコーダ400によって、以下に述べるように処理されて、情報シーケンスを生成する。一実施形態では、この情報シーケンスは、順序付けされたシーケンスであり、少なくとも一つの情報エレメント(例えばビット)で構成されている。一実施形態では、情報シーケンスにおける情報ビットの数は、イベントシーケンスにおけるイベントの数より少ない。出力430は、エンコーダ400から情報シーケンス435を送信するための出力ポートを備えている。この情報シーケンスの順序付けされたビットのシーケンスは、「0」又は「1」の値を有する一つ以上のビットを含む。
【0064】
[0073] イベントシーケンス425を受信すると、シーケンサ405は、確率推定器410及び符号化エンジン415の両者にイベント425を順次送信する。また、イベントシーケンス425の2進イベントごとに、シーケンサ405は、当該2進イベント用に確率推定器410へコンテクスト情報を送信する。確率推定器410は、受信したコンテクスト情報を使用して、確率推定値P(A)を生成する。確率推定値P(A)は、符号化エンジン415へ送信される。一実施形態において、確率推定器410は、多数の確率推定値を符号化エンジン415へ送信し、符号化エンジン415は、確率推定値の一つをR値に基づいて選択する。これに代えて、R値が確率推定器410へ送信され、確率推定器が当該R値を使用して、送信されるべき一つの確率推定値を選択してもよい。確率推定器410は、次いで、受信した2進イベントの値に基づいてその内部状態を更新する。符号化エンジン415は、受信した2進イベント及び対応の確率推定値P(A)を使用して0以上の情報ビットを生成する。
【0065】
[0074] 一実施形態において、符号化エンジン415は、算術符号化データの終了を指示するイベントを符号化する。このイベントは、スライス終了フラグであってもよく、又はビットストリームにおいて非算術符号化データが少なくとも続くという別のインジケータであってもよい。
【0066】
[0075] ゼロ以上の情報ビットを発生する際に、符号化エンジン415は、レンジレジスタ465、ローレジスタ470、ビットアウトスタンディングレジスタ475及びカウンタレジスタ480を含む種々のレジスタを使用する。算術符号化を実行するエンコーダ400のオペレーションは、この技術分野では周知である。
【0067】
[0076] 一実施形態では、エンコーダ400は、情報ビットに対するイベントの関係を限定する。このことは、本明細書の他の部分で説明している。エンコーダ400は、このオペレーションを、その一部分については、上述したようにスタフィングバイト(又はビット)を情報シーケンスに挿入することによって実行する。
【0068】
[0077] 図5は、イベントの符号化に関する一実施形態のフロー図である。このプロセスは、ハードウェア(例えば、回路、専用ロジック等)、ソフトウェア(例えば、汎用コンピュータシステム又は専用マシンで実行されるようなソフトウェア)或いはその両方の組合せで構成される処理ロジックによって実行される。算術符号化プロセスへの入力は、コンテクストを識別するコンテクストID、値R、L、及びsymCntを用いて復号される2進イベントであり、出力に書き込まれるのは、符号化によって生じたビットである。一実施形態では、符号化は、復号と対称であり、算術符号化エンジンの状態は、上述したように、サブインターバルの下端を指すLの値と、サブインターバルの対応レンジを特定するRの値とで表わされる。
【0069】
[0078] 一実施形態では、符号化プロセスは、符号化エンジンが初期化された後にのみ呼び出される。一実施形態では、初期化は、ゼロに等しいLの値及び0x01FEに等しいRの値を送信し、第1ビットフラグを1に、ビットアウトスタンディング(BO)値及びsymCnt(C)カウンタを0にセットすることによって実行される。第1ビットフラグは、符号化中に、エンコーダが初めてプットビット(put bit)手順に入るときを指示するために使用される。symCntカウンタは、符号化されるイベントの数を指示する値を記憶する。
【0070】
[0079] 図5を参照する。このプロセスは、値RLPSを次のように導出することによって(処理ブロック501)、単一イベント(例えばビット)の符号化を開始する。一実施形態では、処理ロジックは、Rインデックス(即ちRidx)を、Rの値を右へ6位置シフトして数値3Hexとアンドした値に等しくすることによって、変数RLPSを導出する。次いで、処理ロジックは、RLPSの値を、Ridxの値と、コンテクストに関連付けられている現在のコンテクストに対する状態の値とを使用し、図16Aに示すテーブルのような確率推定状態マシンテーブルにアクセスすることによって決定される値に、等しくする。Rの値は、次いで、現在のR値からRLPSを引いたものにセットされる。
【0071】
[0080] MPSカウントに対するサブレンジインターバルを計算した後に、処理ロジックは、符号化されている2進イベントの値がMPSの値に等しくないかどうかテストする(処理ブロック502)。2進イベントの値がMPSに等しい場合には、処理ロジックは、MPSパスをとって処理ブロック503へ移行し、そこで、処理ロジックは、状態マシンを、図16Bのテーブルを使用して、そのコンテクストに対して状態マシンに指示された次の状態へと更新し、次いで、プロセスが処理ブロック508へ移行する。符号化されている2進イベントがMPSの値に等しくないと判断すると、処理ロジックは、LPSパスをとって処理ブロック504へ移行し、そこで、処理ロジックは、Lの値を、Lの値とRの値の和に等しくセットし、次いで、Rの値を、RLPSの値に等しくする。
【0072】
[0081] その後、処理ロジックは、特定のコンテクストに対する状態がゼロに等しくないかどうか決定する(処理ブロック505)。一実施形態では、状態ゼロは、50/50の確率に対応する状態である。或いは又、状態ゼロは、例えば、50/50の確率に近い別の確率に対応する状態である。コンテクストの状態がゼロに等しくない場合には、処理ロジックは、処理ブロック507へ移行する。コンテクストの状態がゼロに等しい場合には、処理ロジックは、MPSの意味を切り換え(処理ブロック506)、次いで、処理ブロック507へ移行し、ここで、処理ロジックは、コンテクストの状態番号を、図16Bのテーブルを使用して次の状態へ更新する(処理ブロック507)。
【0073】
[0082] 処理ブロック507及び503を実行した後に、プロセスは、処理ブロック508へ移行し、そこで、処理ロジックは、図6に示す再正規化のような再正規化手順を実行する。次いで、処理ロジックは、イベントカウンタの値を1だけ増加し(処理ブロック509)、処理を終了する。
【0074】
[0083] 図6は、エンコーダの再正規化手順の一実施形態のフロー図である。このプロセスは、ハードウェア(例えば、回路、専用ロジック等)、ソフトウェア(例えば、汎用コンピュータシステム又は専用マシンで実行される)或いはその両方の組合せで構成される処理ロジックによって実行される。
【0075】
[0084] 次に、図6を参照する。まず、処理ロジックは、Rの値が100Hex未満であるかどうかテストする(処理ブロック601)。Noの場合、プロセスは終了となる。Yesの場合、プロセスは、処理ブロック602へ移行し、そこで、処理ロジックは、Lの値が100Hex未満であるかどうかテストする。Yesの場合、処理ブロックは、処理ブロック603へ移行し、そこで、プットビット手順がパラメータ0で実行され、その後、プロセスは、処理ブロック608へ移行する。処理ロジックは、Lの値が100Hex以上であると判断すると、Lの値が200Hexより大きいかどうかテストする。Noの場合、処理ロジックは、Lの値から100Hexを減算した値にLの値をセットし、ビットアウトスタンディング(BO)の値を、パラメータ1で1だけ増加する(処理ブロック605)。次いで、プロセスは、処理ブロック608へ移行する。Lの値が200Hex以上である場合には、プロセスは、処理ブロック606へ移行し、そこで、処理ロジックは、Lの値を、Lの値から200Hexを減算した値にセットし、プットビット手順を実行し(処理ブロック607)、次いで、処理ブロック608へ移行する。
【0076】
[0085] 処理ブロック608では、処理ロジックがRの値を左へ1位置シフトし、且つLの値を1位置シフトする。その後、プロセスは、処理ブロック601へ移行し、プロセスが繰り返される。
【0077】
[0086] 図7は、プットビット手順の実施形態を実行するプロセスの一実施形態を示す。プットビット手順は、ゼロ以上のビットをビットストリームに書き込む。このプロセスは、ハードウェア(例えば、回路、専用ロジック等)、ソフトウェア(例えば、汎用コンピュータシステム又は専用マシンで実行される)或いはその両方の組合せで構成される処理ロジックによって実行される。
【0078】
[0087] 図7に示すように、処理ロジックは、最初に、第1ビットフラグがゼロに等しくないかどうかチェックする(処理ブロック701)。第1ビットフラグが1にセットされている場合には、処理ロジックは、第1ビットフラグをゼロに等しくセットする(処理ブロック702)。次いで、プロセスは、処理ブロック704へ移行する。Noの場合、処理ロジックは、値Bをもつビットを送信し(処理ブロック703)、次いで、処理ロジックが、処理ブロック704へ移行する。
【0079】
[0088] 処理ブロック704において、処理ロジックは、ビットアウトスタンディング(BO)の値がゼロより大きいかどうかテストする。Noの場合、プロセスは終了となる。Yesの場合、処理ロジックは、値1−Bをもつビットを送信し、BOの値を1だけ減少させる(処理ブロック705)。その後、処理ロジックが、処理ブロック704へと移行する。
【0080】
[0089] 図8は、終了前にイベントを符号化するプロセスの一実施形態を示すフロー図である。このプロセスは、スライスの終了と、算術符号化の終了を知らせる他の2進イベントとの符号化に使用される。このプロセスは、ハードウェア(例えば、回路、専用ロジック等)、ソフトウェア(例えば、汎用コンピュータシステム又は専用マシンで実行される)或いはその両方の組合せで構成される処理ロジックによって実行される。
【0081】
[0090] 図8に示すように、処理ロジックは、最初にRの値を2だけ減少させる(処理ブロック801)。次いで、処理ロジックは、符号化されている2進イベントの値がゼロに等しくないかどうかテストする(処理ブロック802)。イベントがゼロに等しい場合には、処理ロジックは、図6に示したような再正規化手順を実行し(処理ブロック803)、次いで、プロセスは、処理ブロック806へ移行する。符号化されるべき2進イベントの値がゼロに等しくない場合には、処理ロジックは、Lの値を、Lの値とRの値の加算値にセットし(処理ブロック804)、エンコーダフラッシング手順を実行し(処理ブロック805)、次いで、処理ブロック806へ移行する。処理ブロック806では、処理ロジックが、イベントカウンタの値を1だけ増加し、符号化プロセスが終了する。
【0082】
[0091] 上記プロセスにおいて明らかなように、一実施形態では、2進イベントの値が1に等しい場合に、算術符号化が終了となり、イベントを符号化した後にフラッシング手順が適用される。このようなイベントを符号化すると、書き込まれる最後のビットは、1に等しいストップビットを含む。
【0083】
[0092] 図9は、終了時のフラッシュに係るプロセスの一実施形態を示すフロー図である。このプロセスは、ハードウェア(例えば、回路、専用ロジック等)、ソフトウェア(例えば、汎用コンピュータシステム又は専用マシンで実行される)或いはその両方の組合せで構成される処理ロジックによって実行される。
【0084】
[0093] 図9に沿って説明する。処理ロジックは、最初に、Rの値を2にセットする(処理ブロック901)。処理ロジックは、次いで、図6に示した再正規化手順のような再正規化手順を実行する(処理ブロック902)。処理ロジックは、次いで、Lの値を右に9位置シフトして、値1Hexとアンドしたものに等しい値に対して図7に示すプットビット手順を実行する(処理ブロック903)。Lレジスタの値をシフトしたコンテンツに対してアンドオペレーションを実行した結果は、10番目のビット位置(最下位ビットから数えて)にビットを生成させ、その後、プットビット手順を使用して出力される。
【0085】
[0094] 最終的に、処理ロジックは、Lレジスタの値を7位置右へシフトして、3Hexの値とアンドし、次いで、1Hexとオアしたものに等しい2つのビットを送信する(処理ブロック904)。1Hexとのオアオペレーションは、ストップビットを追加するために実行される。
【0086】
<デコーダのオペレーションの例>
【0087】
[0095] 図10は、算術デコーダ1000の一実施形態を示すブロック図である。図10に示すように、デコーダ1000は、シーケンサ1005と、確率推定器1010と、復号エンジン1015とを備え、これらは互いに接続されている。入力1020は、デコーダ1000への情報シーケンス1025(例えば2進ビットの順序付けされたシーケンス)のためのポートを提供する。シーケンス1025の2進ビットは、「0」又は「1」の値を有する。一実施形態では、デコーダ1000は、情報シーケンスを処理して、イベントシーケンス1035を生成する。生成されたイベントシーケンスは、単一ビット値以外の値を有する多数のイベント(例えば2進イベント)を含む順序付けされたイベントシーケンスである。このイベントシーケンスは、デコーダ1000からの少なくとも一つの出力ポートを含む出力1030へ供給される。
【0088】
[0096] 情報シーケンス1025を受信すると、シーケンサ1005は、復号エンジン1015に一つ以上のビットを送信する。デコーダ1000は、イベントシーケンスの一つ以上のイベントを次のように繰り返し生成する。シーケンサ1005は、各イベントについて、対応のコンテクストを確率推定器1010に送信する。
【0089】
[0097] 確率推定器1010は、受け取ったコンテクストの値に基づいて、対応の確率推定値P(A)を発生する。この確率推定値P(A)は、復号エンジン1015へ送信され、復号エンジン1015によってイベントの生成に使用される。一実施形態では、確率推定器1010は、多数の確率推定値を復号エンジン1015へ送信し、次いで、復号エンジン1015は、Rの値に基づいて確率推定値の一つを選択する。或いは又、Rの値が確率推定器1010へ送信され、確率推定器がこれを使用して、送信されるべき一つの確率推定値を選択してもよい。次いで、確率推定器1010は、復号エンジン1015から受け取った2進イベントの値に基づいてその内部状態を更新する。
【0090】
[0098] 復号エンジン1015は、生成された各イベントを確率推定器1010及びシーケンサ1005へ送信する。復号エンジン1015は、生成された各2進イベントに対してゼロ以上の情報ビットを消費する。したがって、シーケンサ1005は、イベントの生成後に、情報シーケンスからのゼロ以上のビットを復号エンジン1015へ送信する。復号エンジン1015は、レンジレジスタ1065や値レジスタ1070を含む種々のレジスタを使用して、イベントシーケンス1035のイベントを生成する。デコーダ1000のオペレーションは、以下に説明するフロー図に示されている。
【0091】
[0099] 以下のフロー図は、デコーダ1000のようなデコーダの一実施形態によってスライスに対して実行される復号オペレーションを示している。一実施形態において、デコーダは、図12、14A、14B、15A又は15Bに示されたフロー図に従い、コンテクストの値に基づいて復号を実行する。図示されたプロセスは、他のプロセスに組み込まれてもよく、それに具体化された改善の利益を得るように他の方法で適用、或いは変更されてもよい。一実施形態では、デコーダは、一度に1バイトを読み取る。別の実施形態では、デコーダは、一度に1ビットを読み取る。
【0092】
[0100] 図11は、算術デコーダの初期化プロセスの一実施形態を示すフロー図である。このプロセスは、ハードウェア(例えば、回路、専用ロジック等)、ソフトウェア(例えば、汎用コンピュータシステム又は専用マシンで実行される)或いはその両方の組合せで構成される処理ロジックによって実行される。
【0093】
[0101] 図11を参照する。まず、プロセスは、処理ロジックがレンジRを所定の数値にセットすることで始まる(処理ブロック1101)。一実施形態において、当該所定の数値は、0xff00である。レンジRを初期化した後、処理ロジックは、圧縮されたデータの2バイトをレジスタVへ読み込む(処理ブロック1102)。一実施形態では、レジスタVは、圧縮されたビットを一度に1バイト記憶する。レジスタVは、圧縮されたデータを一度に1ビット記憶するように実施されてもよいが、本明細書に記載されたプロセスに使用される定数が、それに応じて変更されなければならない。
【0094】
[0102] より詳細には、図示されたように、処理ロジックは、1バイトを読み込み、それを左に8位置シフトし、次いで、別のバイトを取得し、それを算術オアオペレーションを用いてレジスタVへ加算する。圧縮されたデータがレジスタVに読み込まれると、処理ロジックは、レジスタBの値を所定値にセットする。レジスタBは、処理に使用できるレジスタV内の余りのビット数を指示する。レジスタBの値が0未満になると、圧縮されたデータの別のバイトをフェッチすることが必要となる。一実施形態では、所定値は7である。
【0095】
[0103] 図12は、2進イベントを復号するプロセスの一実施形態を示すフロー図である。このプロセスは、ハードウェア(例えば、回路、専用ロジック等)、ソフトウェア(例えば、汎用コンピュータシステム又は専用マシンで実行される)或いはその両方の組合せで構成される処理ロジックによって実行される。
【0096】
[0104] 図12に示すように、このプロセスは、LPSのインターバルのサイズを計算することによって開始する(処理ブロック1202)。一実施形態において、この計算は、乗算によって実行される。乗算は、コンテクスト(CTX)に関連付けられた状態に基づくテーブルルックアップを使用することによって近似される。一実施形態では、有限状態マシンを使用して、マシンの状態に依存している確率が何であるかを指示する。次いで、ルックアップするのは、状態の値と、Rの最上位ビット後の次の2つの最上位ビットである。ルックアップを実行するテーブルの例を図16Aに示す。また、テーブルを生成する方法の例を以下に示す。
【0097】
[0105] テーブルルックアップの結果は、7シフトされる。その理由は、この手法では、一度にビットではなくバイトが読み取られるからである。テーブルルックアップのシフトされた結果は、LPSのサブレンジインターバルであり、RLPSと称される。
【0098】
[0106] また、処理ブロック1202の一部分として、処理ロジックは、LPSのサブレンジインターバルRLPSをレジスタRの値から減算することによって、MPSのサブインターバルレンジを計算する。処理ロジックは、Rの値を減算の結果に等しくセットする。
【0099】
[0107] MPSのサブレンジインターバルを計算した後に、処理ロジックは、レジスタVの値が、レジスタRに記憶されたMPSのサブインターバル以上であるかどうかテストし、処理されている現在のビットがLPSのサブレンジ内であることを指示する(処理ブロック1203)。Noの場合、処理ロジックは、MPSパスをとって処理ブロック1204へ移行し、そこで、処理ロジックは、復号される値(即ち戻される結果)Sを、その特定のコンテクストに対するMPSであると定義された値に等しくセットする。次いで、処理ロジックは、当該コンテクストに対する状態マシンを、図16Bのテーブルを使用して当該コンテクストに対して状態マシンに指示された次の状態へと更新する。一実施形態では、MPSに対し、状態マシンの更新は、状態テーブルの状態を1だけ増加することからなる。
【0100】
[0108] 処理ロジックは、値VがレジスタRの値以上であると判断すると、LPS経路をとって処理ブロック1205へ移行し、そこで、結果Sを、特定のコンテクストCTXに対するLPS(MPSではない)に等しくセットし、値Vを、Vの現在値からレンジRの値を減算した結果に等しくセットし、更に、レンジRを、LPSのレンジ、即ちRLPSに等しくセットする(処理ブロック1205)。
【0101】
[0109] また、処理ロジックは、2進イベントのコンテクストに対する状態がゼロであるかどうかもチェックする(処理ブロック1206)。一実施形態では、状態0は、50/50の確率に対応する状態である。或いは又、状態ゼロは、例えば、50/50の確率に近い別の確率に対応する状態であってもよい。2進イベントのコンテクストに対する状態がゼロでない場合に、プロセスは、処理ブロック1208へ移行する。2進イベントのコンテクストに対する状態がゼロである場合に、処理ロジックは、MPSの意味を切り換える(処理ブロック1207)。
【0102】
[0110] その後、コンテクストの状態番号は、図16Bのテーブルを使用して次の状態へ更新され(処理ブロック1208)、処理ロジックは、以下に詳細に述べる再正規化手順を実行する(処理ブロック1209)。
【0103】
[0111] 図13は、再正規化手順のフロー図である。このプロセスは、ハードウェア(例えば、回路、専用ロジック等)、ソフトウェア(例えば、汎用コンピュータシステム又は専用マシンで実行される)或いはその両方の組合せで構成される処理ロジックによって実行される。
【0104】
[0112] 図13に示すように、プロセスは、Rが8000Hex未満であるかどうか処理ロジックがテストすることによって開始する(処理ブロック1301)。Rが8000Hex以上である場合には、再正規化プロセスが終了となる。Yesの場合、処理ロジックは、R及びVの値を2倍にする(処理ブロック1302)。一実施形態では、処理ロジックは、R及びVのビットを左へ1位置シフトすることによってR及びVの値を2倍にする。また、Bの値は、1だけ減少される。その理由は、シフト処理によって処理に利用可能なビットが一つ少なくなるからである。次いで、処理ロジックは、Bの値が0未満であるかどうかチェックする(処理ブロック1303)。Noの場合、処理は処理ブロック1301へ移行し、プロセスが繰り返される。Bの値が0未満である場合には、処理が処理ブロック1304へ移行し、そこで、Bの値が7にセットされ、処理されるべき別のバイトがフェッチされて、レジスタVの現在のコンテンツと論理オアされる。その後、処理は処理ブロック1301へ移行し、プロセスが繰り返される。
【0105】
[0113] 図14A及び14Bは、同じ確率でイベントを復号するためのフロー図である。図14Aは、レジスタVのサイズが16ビットより大きいときに使用され、一方、図14Bは、レジスタVのサイズが16ビットであるときに使用される。これらの手法は、一度に1バイトをフェッチするときに使用される。
【0106】
[0114] これらのプロセスは、ハードウェア(例えば、回路、専用ロジック等)、ソフトウェア(例えば、汎用コンピュータシステム又は専用マシンで実行される)或いはその両方の組合せで構成される処理ロジックによって実行される。
【0107】
[0115] 分布がゼロを中心とするものであって、正の値又は負の値を得る見込みがほぼ同じである場合に、これらのプロセスを使用できる。例えば、これらプロセスは、係数の符号値を処理するときに使用される。それが正であるか負であるかの見込みを推定するのではなく、固定推定値を使用して、確率が50/50であることを認識する。したがって、Rに確率を乗算するためのテーブルルックアップを実行する必要がない。尚、これらは、終了に影響しない。
【0108】
[0116] 図14Aを参照する。プロセスは、処理ロジックがVの値を2倍にすると共にBの値を1だけ減少させることによって開始する(処理ロジック1401)。Vの値を2倍にすることは、Vのビットを左へ1位置シフトすることで行われる。
【0109】
[0117] 次いで、処理ロジックは、Bの値が0未満であるかどうかチェックする(処理ブロック1402)。Noの場合、処理は、処理ブロック1404へ移行する。Bの値が0未満である場合には、処理ブロック1403へ移行し、そこで、Bの値が7にセットされ、処理されるべき別のバイトをフェッチされて、レジスタVの現在のコンテンツと論理オアされる。
【0110】
[0118] 処理ブロック1404において、処理ロジックは、Vの値がRの値以上であるかどうかテストする。Yesの場合、処理ロジックは、結果Sを1にセットし、更に、Vの値を、Vの値からRの値を減算した結果にセットし(処理ブロック1405)、プロセスが終了する。Noの場合、処理ロジックは、結果Sを0にセットし(処理ブロック1406)、プロセスは終了となる。
【0111】
[0119] 次に、図14Bを参照する。処理ロジックが値V’をVに等しくセットし、Vの値を2倍にし、Bの値を1だけ減少させることによって、プロセスが開始する(処理ロジック1411)。Vの値を2倍にすることは、Vのビットを左へ1位置シフトすることによって実行される。
【0112】
[0120] 次いで、処理ロジックは、Bの値が0未満であるかどうかチェックする(処理ブロック1412)。Noの場合、処理は、処理ブロック1414へ移行する。Bの値が0未満である場合には、処理ブロック1413へ移行し、そこで、Bの値が7にセットされ、処理されるべき別のバイトがフェッチされて、レジスタVの現在のコンテンツと論理オアされる。
【0113】
[0121] 処理ブロック1414では、処理ロジックは、Vの値がRの値以上であるかどうか、又はV’が8000Hex以上であるかどうかテストする。Yesの場合、処理ロジックは、結果Sを1にセットすると共に、Vの値を、Vの値からRの値を減算した結果にセットし(処理ブロック915)、プロセスが終了する。Noの場合、処理ロジックは、結果Sを0にセットし(処理ブロック916)、プロセスは終了となる。
【0114】
[0122] 図15Aは、算術符号化の終了を示す符号化イベントを復号するための一実施形態を示すフロー図である。このようなイベントは、スライス終了フラグを構成する。スライス終了フラグについては、シンタックスを使用して、スライス終了フラグの存在をデコーダに指示することができる。一実施形態では、このプロセスは、各マクロブロックについて実行されるが、スライスにおける最後のマクロブロックについてのみ、スライスの終了を指示する結果が得られる(例えば、1の結果が出力される)。
【0115】
[0123] 算術符号化の終了を知らせるためのイベント(デコーダに対する)は、ビットストリームにおいて算術符号化の後に続こうとするデータが、非圧縮のものか又は算術符号化以外の別の符号化技術で圧縮されたものであるときに使用される。尚、この非圧縮のデータ又は非算術符号化技術で圧縮されたデータの後に、追加の算術符号化データが続いてもよい。したがって、終了を知らせるためのイベントは、非算術符号化データがビットストリームにおいて算術符号化データとインターリーブされる場合に使用される。
【0116】
[0124] このプロセスは、ハードウェア(例えば、回路、専用ロジック等)、ソフトウェア(例えば、汎用コンピュータシステム又は専用マシンで実行される)或いはその両方の組合せで構成される処理ロジックによって実行される。
【0117】
[0125] 図15Aに沿って説明する。まず、処理ロジックは、Vの値が100Hex未満であるかどうかテストし(処理ブロック1501)、それによって、スライスにおける最後のマクロブロックに到達したことを指示する。Vの値が100Hex未満である場合に、処理ロジックは、復号されたシンボルを表わす結果Sを1にセットし(処理ブロック1502)、スライスに対する復号プロセスが終了する。Vの値が100Hex未満でない場合に、処理ロジックは、出力結果Sを0にセットし、Rの値を、Rの値から100Hexを減算した結果にセットし、更に、Vの値を、Vの値から100Hexを減算した結果にセットする(処理ロジック1503)。次いで、処理ロジックが、図3の再正規化手順を実行して(処理ブロック1504)、プロセスが終了となる。
【0118】
[0126] 尚、一実施形態では、MPSとLPSとの間の規定を切り換えてもよい。図15Bは、MPSとLPSとの間の規定を切り換えた場合に、終了前のイベントを符号化するプロセスの一実施形態を示すフロー図である。このプロセスは、ハードウェア(例えば、回路、専用ロジック等)、ソフトウェア(例えば、汎用コンピュータシステム又は専用マシンで実行される)或いはその両方の組合せで構成される処理ロジックによって実行される。
【0119】
[0127] 図15Bに示すように、処理ロジックは、Rの値から100Hexを減算することで開始する(処理ブロック1511)。次いで、処理ロジックは、Vの値がRの値以上であるかどうかテストする(処理ブロック1512)。Yesの場合、処理ロジックは、復号されたシンボルを表わす出力結果Sを1にセットし(処理ブロック1513)、次いで、終了前のイベントを復号する復号プロセスが終了となる。したがって、再正規化は実行されない。Noの場合、処理ロジックは、出力結果Sを0にセットし(処理ブロック1514)、図13の再正規化手順を実行し(処理ブロック1515)、次いで、プロセスは終りとなる。
【0120】
<確率推定のための状態マシンの構造>
[0128] 図16A及び16Bにおける状態マシンを構成するためのプロセスの一例をCコードで以下に示す。
C-code:
#define N b4
#define Pmax 0.5
#define Pmin 0.01875
#define regsize 9
#define ONE(1<<regsize)
double alpha;
double sum;
int i,j;
double q;
float prob64[N];
intnext_state_MPS_64[N];
intnext_state_LPS_64[N];
int switch_MPS_64[N];
int gLPS[N][4] ;
alpha=pow(Pmin/Pmax,1.0/(N-1));
sum=0.5;
for(i=0; i<N; i++){
prob64[i]=Pmax*pow(alpha,i);
next_state_MPS_64[i]=(i==N-1)?N-1:i+1;
q=prob64[i]*alpha+(1-alpha);
q=q/prob64[i];
q=-log(q)/log(alpha);
sum+=q;
k=(int)(sum);
sum-=k;
next_state_LPS_64[i]=(i-k<0)?O:i-k;
for(j=0; j<4; j++){
RTAB[i][j]=(int)(ONE/8*prob64[i]/log((j+5.0)/(j+4.0))+0.5);
if(j == 0 && RTAB[i][j] > ONE/4)
RTAB[i][j]=ONE/4;
}
}
【0121】
[0129] 上記コードにおいて、Nは、状態マシンにおける状態の数を定める。一実施形態において、状態マシンは対称的であり、合計状態数は、2*N(この例では128)である。状態は、状態(0とN−1(それらも含めて)との間の数値)と、MPSフラグ(0又は1のいずれがMPSであるかを決定する)との2つの変数で表わされる。
【0122】
[0130] 一実施形態では、大きな状態番号がLPSの低確率に対応するように、状態が編成される。状態マシンは、以下の手順に近づくように定義される。
(a)p(LPS) <-- p(LPS)*alpha、MPSが観察される場合
(b)p(LPS) <--p(LPS)*alpha+(1−alpha)、その他の場合
ここで、alphaは、適応レートを定める。alphaは、通常、0.9から1の範囲であるが、所望の適応に基づいて他の範囲内へ広がってもよく、又は他の範囲内にあってもよい。
【0123】
[0131] 上記コードにおいて、alphaは、pow(0.01875/0.5、1.0/63)に等しくセットされる。ここで、0.01875(Pmin)は、状態N−1に対するLPSの確率を定義し、0.5(Pmax)は、状態0に対するLPSの確率を定義し、更に、1.0/63は、1割るN−1である。尚、pow(a、b)は、数値aのb乗である。
【0124】
[0132] prob64と称するアレーは、各状態に関連付けられたLPSの確率を表わす浮動小数点値を含む。Prob64[i]は、Pmax*pow(alpha、i)にセットされる。Prob64[0]は、Pmaxに等しく、Prob64[N−1]は、Pminに等しい。
【0125】
[0133] Next_state_MPS_64[i]は、MPSが観察された際の状態遷移を定める。iがN−1と異なる場合には、状態が1だけ増加される。他の場合には、状態は不変に保たれる。Prob64[i]及びNext_state_MPS_64[i]の組合せが与えられると、上述した更新手順の(a)の部分が上手く近似される。
【0126】
[0134] 更新手順の(b)の部分を近似するために、Next_state_LPS_64[i]をi−(−log((prob64[i]*alpha+(1−alpha))/prob64[i])/log(alpha))にセットしなければならない。しかしながら、この値は、整数ではなく、したがって、整数近似を求めねばならない。一実施形態では、当該値は、最も近い整数に丸められる。しかしながら、別の実施形態では、丸め切り上げと丸め切り捨てとのバランスをとるために、丸めによって導入される差が平均でゼロに近づくように変数和が使用される。
【0127】
[0135] RTAB[i][j]の値は、R*prob64[j]に近づくように計算される。変数jは、Rが存在するインターバルによって決定される。変数jは、Rが[256、319]の場合には0に等しくセットされ、[320、383]の場合には1に等しくセットされ、[384、447]の場合には2に等しくセットされ、更に、[448、511]の場合には3に等しくセットされる。ここで、例えば、(ONE*4)/8は、256に等しく、(ONE*5)/8−1は、319に等しく、等々である。(ONE/8)log((j+5)/(j+4))は、jが与えられた場合のRの期待値となっている。
【0128】
[0136] より高速な実施を可能にするために、MPSを符号化する際には、再正規化の繰り返しを多くても1回しか行わないよう保証することが望ましい。このために、RTAB[i][0]は、ONE/4に切り取られる。それ故、Rは、再正規化の前にONE/4より小さくなることはない。より一般的には、一実施形態において、RTAB[i][j]は、(ONE/4)+(ONE/8)*jに切り取られるが、ここに示す例ではjが0と異なる場合はこのようにならない。
【0129】
[0137] したがって、上述した技術を使用すると、一実施形態では一つの状態を除いて、図16A及び16Bの状態テーブルを発生することができる。図16Aでは、状態63は、2,2,2,2のR値を含む。図16Bでは、いったん状態63になると、次の状態も、状態63である。したがって、LPSが発生するかMPSが発生するかに拘らず、状態は変化しない。また、図16Bでは、いったん状態62になると、状態は、MPS発生時に状態62に留まる。
【0130】
<ソースコードの実施例>
【0131】
[0138] Cコードでのサンプルエンコーダ及びサンプルデコーダを以下に示す。これらの方法は、データ(例えばビデオデータ)を符号化及び復号する適当な処理装置を使用して実装される。ある実施形態では、ハードウェア及びソフトウェア要素の組み合せによってプロセスが実行される。他の適応もなされる。符号化及び復号の機能はCの形態で以下に示されている。
Encoder:
void start_encode() {
encode_slice_header();
while (!byte_aligned)
send_bit(0);
R=0x1fe;
L=O;
BO=0;
FB=1;
}
void finish_encode() {
R=2;
renorm_encode();
bit_plus_follow((L >> 9) & 1);
send_bit((L >> 8) & 1);
send_bit(1); // stop_bit
while (!byte_aligned())
send_bit(0); // alignment_bit
}
voidbit_plus_follow(int b) {
if (FB == 1)
FB = 0;
else
send_bit(b);
while (BO > 0) {
BO--;
send_bit(!b);
}
}
void encode_renorm() {
while (!(R&0x100) {
if (L+R < 0x200)
bit_plus_follow(0);
else if (L >= 0x200) {
bit_plus_follow(1);
L -= 0x200;
}
else {
BO++;
L -= 0x100;
}
R <<= 1;
L <<= 1;
}
}
void encode_event(intctx, int b) {
rLPS = table[state[ctx]][(R>>6)-4];
R -= rLPS;
if (b == MPS[state[ctx]])
state[ctx] = next_state_MPS[state[ctx]];
else {
L += R;
R = rLPS;
if (state[ctx] == 0)
MPS[state[ctx]] = !MPS[state[ctx]];
state[ctx] = next_state_LPS[state[ctx]];
}
encode_renorm();
}
voidencode_equiprob_event(int b) {
L <<= 1;
if (b)
L+=R;
if (L+R < 0x400)
bit_plus_follow(0);
else if (L >= 0x400) {
bit_plus_follow(1);
L -= 0x400;
}
else {
BO++;
L -= 0x200;
}
}
void encode_end_of_slice_flag(intb) {
if (b == O) {
R-=2;
L+=2;
encode_renorm();
}
}
Decoder (bytebased):
void start_decode() {
decode_slice_header();
while (!byte_aligned())
get_bit();
R = 0xff80;
V = get_byte() << 8;
V |= get_byte();
B = 7;
}
void finish_decode() {
while (more_bytes_in_slice())
get_byte(); // stuffing byte
}
void decode_renorm() {
while (R<0x8000) {
R <<= 1;
V <<= 1;
B--;
if (B<0) {
B= 7;
V |= get_byte();
}
}
}
int decode_equiprob() {
V = (V<<1);
B--;
if (B<0) {
V |= get_byte();
B = 7;
}
if (V >= R) {
V -= R;
bit = 1;
}
else
bit = 0;
return bit;
}
int decode_event(intctx) {
rLPS =table[state[ctx]][(R>>13)-4]<<7;
R -= rLPS;
if (V < R) {
state[ctx] = next_state_MPS[state[ctx]];
bit = MPS[state[ctx]];
}
else {
bit = !MPS[state[ctx]];
V -= R;
R = rLPS;
if (state[ctx] == 0)
MPS[state[ctx]] = !MPS[state[ctx]];
state[ctx] = next_state_LPS[state[ctx]];
}
decode_renorm();
return bit;
}
intdecode_end_of_slice_flag() {
if (V < 0x100)
bit = 1;
else {
bit = 0;
R-=0x100;
V-=0x100;
decode_renorm();
}
return bit;
}
Alternative byte-basedend of slice decoding for use when the MPS/LPS convention is switched(MPS/LPSの規定が切り替えられるときに使用される、代替のバイトベースのスライス終了ラグの復号)
intdecode_end_of_slice_flag(){
R -= 0x100;
if (V >= R)
bit = 1;
else {
bit = 0
decode_renorm();
}
return bit;
}
Decoder (bit based):
void start_decode() {
decode_slice_header();
while (!byte_aligned())
get_bit();
R = 0x1fe;
V = 0;
for (i=0; i<9; i++)
V = (V<<1) | get_bit();
}
void finish_decode() {
while (!byte_aligned())
get_bit(); // alignement bit
while (more_bytes_in_slice())
get_byte(); // stuffing byte
}
int decode_renorm() {
while (R<0x100) {
R <<= 1;
V = (V<<1)|get_bit();
}
}
int decode_equiprob() {
V = (V<<1) | get_bit();
if (V >= R) {
V -=R;
bit = 1;
}
else
bit = 0;
return bit;
}
int decode_event(intctx) {
rLPS = table[state[ctx]][(R>>6)-4];
R -= rLPS;
if (V < R) {
state[ctx] = next_state_MPS[state[ctx]];
bit = MPS[state[ctx]];
}
else {
bit = !MPS[state[ctx]];
V -= R; R = rLPS;
if (state[ctx] == 0)
MPS[state[ctx]] = !MPS[state[ctx]];
state[ctx] = next_state_LPS[state[ctx]];
}
decode_renorm();
return bit;
}
intdecode_end_of_slice_flag() {
if (V < 2)
bit = 1;
else {
bit = 0;
R-=2;
V-=2;
decode_renorm();
}
return bit;
}
Alternative bit-basedend_of_slice flag decoding for use when the MPS/LPS convention is switched(MPS/LPSの規定が切り替えられるときに使用される、代替のビットベースのスライス終了フラグの復号)
intdecode_end_of_slice_flag(){
R -= 2;
if (V >= R)
bit = 1
else {
bit = 0;
decode_renorm();
}
return bit;
}
【0132】
[0139] 尚、上述した算術コーダには、上部インターバル及び下部インターバルの2つに分割されるインターバルがある。一方のインターバルは、MPSを表わし、他方のインターバルは、LPSを表わす。一実施形態では、MPS及びLPSをインターバルに割り当てる処理は、一方のインターバルに1を割り当て、他方のインターバルに0を割り当てる処理を含む。上述したソースコードでは、end_of_slice_flagを符号化するためにインターバルが分割される場合に、MPS(値0)が上部サブインターバルに割り当てられる。また、MPSを下部サブインターバルに割り当てることもできる。
【0133】
[0140] 以下のコードは、別のエンコーダ例を示す。尚、このコードでは、Sは、上述したように制限する関係を満足するためのスライスにおける最小バイト数である。
void start_encode() {
send_NAL_first_byte();
encode_slice_header();
while (!byte_aligned())
send_bit(0);
R = 0x1fe; // range
L = 0; // low
BO = 0; // bits outstanding
C = 0; // event counter
FB = 1; // first bit flag
}
void finish_encode() {
bit_plus_follow((L >> 9) & 1);
for (i=8; i>=1; i--)
send_bit((L >> i) & 1);
send_bit(1); // stop_bit
while (!byte_aligned())
send_bit(0); // alignment bit
RBSP_to_EBSP();
S = min_bytes(C,number_of_macroblocks_in_slice);
while (S > bytes_in_NAL_unit())
send_three_bytes(Ox000003); // write bytesdirectly into
NAL unit
}
voidbit_plus_follow(int b) {
if (FB == 1)
FB = 0;
else
send_bit(b);
while (BO > 0) {
BO--;
send_bit(!b);
}
}
void encode_renorm() {
while (!(R&0x100) {
if (L+R < 0x200)
bit_plus_follow(0);
else if (L >= 0x200) {
bit_plus_follow(1);
L -= 0x200;
}
else {
BO++;
L -= 0x100;
}
R <<= 1;
L <<= 1;
}
}
void encode_event(intctx, int b) {
rLPS = table[state[ctx]][(R>>6)-4];
R -= rLPS;
if (b == MPS[state[ctx]])
state[ctx] = next_state_MPS[state[ctx]];
else {
L += R;
R = rLPS;
if (state[ctx] == 0)
MPS[state[ctx]] = !MPS[state[ctx]];
state[ctx] = next_state_LPS[state[ctx]];
}
encode_renorm();
C++;
}
voidencode_equiprob_event(int b) {
L <<= 1;
if (b)
L += R;
if (L+R < 0x400)
bit_plus_follow(0);
else if (L >= 0x400) {
bit_plus_follow(1);
L -= 0x400;
}
else {
BO++;
L -= 0x200;
}
C++;
}
voidencode_end_of_slice_flag(int b) {
if (b == 0) {
R-=2;
L+=2;
encode_renorm();
}
}
【0134】
[0141] 上記コードにおいて、ヘッダの一部分である第1バイトをNALユニットに送信する処理は、後続するデータの形式を指示するために実行される。NALユニット及びその使用法は、この技術分野では周知である。
【0135】
[0142] RBSP_to_EBSP()の関数呼び出しは、データをビットストリームに挿入させる。より好ましくは、一実施形態において、ビットストリームに所定数の連続するゼロが発生するのを防止する方法として、03Hexが0000Hexバイトの後に次のパターン、例えば、000000、000001、000002、000003で挿入される。その結果、000000Hex、000001Hex及び000002Hexのパターンが圧縮されたデータに現われることがなく、これを再同期マーカーとして使用することができる。デコーダが000003Hexパターンに遭遇すると、逆の手順によって「03」がビットストリームから除去される。
【0136】
[0143] 本明細書に説明したエンコーダ及びデコーダのこのような一つの使い方は、ビデオデータを符号化及び復号するものであるが、当業者であれば、本明細書に説明したエンコーダ及びデコーダは、エンコーダの場合にイベントシーケンスが情報シーケンスへ圧縮され、デコーダの場合にその情報シーケンスが圧縮解除されるような任意の場面に使用できることが明らかであろう。更に、エンコーダの上記説明は、多数の2進イベントで構成されたイベントシーケンスを、少なくとも1ビットで構成された情報シーケンスへと処理することに関して述べ、デコーダについては、少なくとも1ビットで構成された情報シーケンスを、多数の2進イベントで構成されたイベントシーケンスへと処理することに関して述べたが、エンコーダ及びデコーダは、当業者に明らかなように、本明細書に説明した教示を利用して、M進(M-ary)性のイベント(即ち、各M進イベントは2ビット以上のデータを表わす)で構成されたイベントシーケンス及び情報シーケンスに対して演算を行うことができる。
【0137】
<コンピュータシステムの例>
【0138】
[0144] 図17は、本明細書に説明された一つ以上のオペレーションを実行することのできるコンピュータシステムの一例を示すブロック図である。尚、これらのブロック又はブロックのサブセットは、本明細書に説明された技術を実行するように、例えば、セルラー電話のような装置に一体化できる。
【0139】
[0145] 図17を参照すれば、コンピュータシステム1700は、情報を通信するための通信メカニズム即ちバス1711と、情報を処理するためにこのバス1711に接続されたプロセッサ1712とを備えている。このプロセッサ1712は、例えば、Pentium(登録商標)、PowerPC(登録商標)、Alpha(登録商標)等のマイクロプロセッサを含むが、これに限定されない。
【0140】
[0146] システム1700は、更に、プロセッサ1712によって実行される情報及び命令を記憶するためにバス1711に接続されたランダムアクセスメモリ(RAM)又は他のダイナミック記憶装置1704を備えている。また、このメインメモリ1704は、プロセッサ1712によって命令を実行する間に一時的な変数又は他の中間情報を記憶するために使用されることができる。
【0141】
[0147] また、コンピュータシステム1700は、プロセッサ1712用のスタティック情報及び命令を記憶するためにバス1711に接続されたリードオンリメモリ(ROM)及び/又は他のスタティック記憶装置1706と、磁気ディスク又は光学ディスク及びそれに対応するディスクドライブのようなデータ記憶装置1707とを備えている。このデータ記憶装置1707は、情報及び命令を記憶するためにバス1711に接続される。
【0142】
[0148] コンピュータシステム1700は、更に、コンピュータのユーザに情報を表示するためにバス1711に接続された陰極線管(CRT)又は液晶ディスプレイ(LCD)のようなディスプレイ装置1721にも接続される。また、アルファニューメリック及び他のキーを含むアルファニューメリック入力装置1722も、情報及びコマンドの選択をプロセッサ1712へ通信するためにバス1711に接続される。更に別のユーザ入力装置は、マウス、トラックボール、トラックパッド、スタイラス、又はカーソル方向キーのようなカーソル制御器1723であり、これは、方向情報及びコマンド選択をプロセッサ1712と送受すると共に、ディスプレイ1721上のカーソル移動を制御するためにバス1711に接続される。
【0143】
[0149] バス1711に接続される別の装置は、ハードコピー装置1724である。ハードコピー装置1724は、命令、データ又は他の情報をペーパーやフィルムのような媒体や同様の形式の媒体にプリントするために使用される。更に、スピーカ及び/又はマイクロホンのような音声記録及び再生装置も、コンピュータシステム1700と音声インターフェイスするようにバス1711に任意に接続できる。バス1711に接続できる別の装置は、電話、ハンドヘルド式の手のひら装置又は他の装置と通信するための有線/無線通信装置1725である。
【0144】
[0150] 尚、システム1700のいずれか又は全部の要素及びそれに関連したハードウェアを本発明に適用できる。しかしながら、当該コンピュータシステムの他の構成は、上記デバイスの幾つか又は全てを含められることは明らかであろう。
【0145】
[0151] 当業者であれば、以上の説明を読んだ後、本発明の多数の変更や修正が明らかとなるであろうが、図示して説明した特定の実施形態は、本発明を限定するためのものではないことを理解されたい。それ故、種々の実施形態の詳細な説明は、本発明の本質とみなす特徴のみを記載した特許請求の範囲を何ら限定するものではない。
【符号の説明】
【0146】
100…システム、102…エンコーダ、104…デコーダ、300…データフォーマット、302…ヘッダ、303…ストップビット、304…算術符号、306…ストップビット、308…整列ビット、310…スタフィングバイト、400…算術エンコーダ、405…シーケンサ、410…確率推定器、415…符号化エンジン、465…レンジレジスタ、470…ローレジスタ、475…ビットアウトスタンディングレジスタ、480…カウンタレジスタ、1000…算術デコーダ、1005…シーケンサ、1010…確率推定器、1015…復号エンジン、1065…レンジレジスタ、1070…値レジスタ、1700…コンピュータシステム、1704…メインメモリ、1706…スタティック記憶装置、1707…データ記憶装置、1711…バス、1712…プロセッサ、1721…ディスプレイ装置、1722…アルファニューメリック入力装置、1723…カーソル制御器、1724…ハードコピー装置、1725…通信装置。
【特許請求の範囲】
【請求項1】
確率推定のための状態マシンを生成する方法であって、
ルックアップテーブル(LUT)の状態に確率を割り当てるステップであって、所与の状態の番号をiとし、かつ、適応レートが1より小さいとする場合に、前記状態の各状態iに対する確率を、LPSの最大確率に適応レートのi乗を乗算した値に等しくセットする処理を含むステップと、
MPS及びLPSを観察し、遷移れるべきLUTの状態に対して状態遷移を発生するステップであって、MPSが観察されたときに現在の状態から状態マシンが遷移する次の状態が、当該現在の状態が最も高い状態でない場合には、当該現在の状態より高い次の状態であり、当該現在の状態が最も高い状態である場合には当該現在の状態であり、更に、複数の状態に対しLPSが観察されたときに当該現在の状態から状態マシンが遷移する次の状態が、
現在の状態の番号+log((現在の状態の確率*適応レート+(1−適応レート))/現在の状態の確率)/log(適応レート)
の計算結果が丸められた値である、ステップと、
を含む方法。
【請求項2】
前記結果の丸められた値は、LPSが観察されて次の状態を発生するときに導入される丸めが平均で実質的にゼロとなるようになっている、請求項1に記載の方法。
【請求項3】
前記LUTは、各状態に関連付けられた複数の値を有し、該複数の値の各々は、予想されるインターバルレンジに前記状態に関連した確率を乗算した積に近似する、請求項1に記載の方法。
【請求項4】
状態に関連付けられた値は、配列における列のインデックスをjとし、当該配列における列の数をMとし、定数をNとする場合に、N/(2*M*log((j+M+1)/(j+M)))と状態に関連付けられた確率との積を整数に丸めることによって得られる、請求項3に記載の方法。
【請求項5】
前記複数の状態の少なくとも一つに対する前記複数の値の少なくとも一つは、所定値に切り取られる、請求項3に記載の方法。
【請求項6】
前記所定値は、MPSの符号化中に再正規化を多くて1回繰り返せるようにする、請求項5に記載の方法。
【請求項7】
前記LUTにおける状態の数は、63であり、
前記適応レートは、0.5/0.01875の1.0/63乗であり、
LPSの最高確率は、0.5であり、
前記配列における列の数は、4であり、
前記配列の第1列における値は、N/4に切り取られる、
請求項4に記載の方法。
【請求項8】
前記定数Nは、512である、請求項7に記載の方法。
【請求項9】
イベントシーケンスの各イベントが個別の値を有する確率推定値を発生するための確率推定器と、
前記確率推定器に接続され、各イベント及び対応の確率推定値に応じて情報シーケンスのゼロ以上のビットを生成する符号化エンジンと、
を備え、
前記確率推定器は、前記各イベントに対応するコンテクスト情報に応じて、確率推定状態マシンを使用して前記確率推定値を発生し、
前記確率推定状態マシンは、
所与の状態の番号をiとし、適応レートが1より小さい場合に、各状態iに対する確率を、LPSの最大確率に適応レートのi乗を乗算した値に等しくセットして、ルックアップテーブル(LUT)の状態に確率を割り当て、
MPSが観察されたときに現在の状態から状態マシンが遷移する次の状態が、当該現在の状態が最も高い状態でない場合には当該現在の状態より高い次の状態となり、当該現在の状態が最も高い状態である場合には当該現在の状態となり、更に、複数の状態に対しLPSが観察されたときに現在の状態から状態マシンが遷移する次の状態が、
現在の状態の番号+log((現在の状態の確率*適応レート+(1−適応レート))/現在の状態の確率)/log(適応レート)
の計算結果が丸められた値となるように、MPS及びLPSを観察して、遷移されるべきLUTの状態に対して状態遷移を発生する
ことによって生成される、算術エンコーダ。
【請求項10】
前記結果の丸められた値は、LPSが観察されて次の状態を発生するときに導入される丸めが平均で実質的にゼロとなるようになっている、請求項9に記載の算術エンコーダ。
【請求項11】
前記LUTは、各算術エンコーダに関連付けられた複数の値を有し、該複数の値の各々は、予想されるインターバルレンジに、前記状態に関連した確率を乗算した積に近似する、請求項9に記載の算術エンコーダ。
【請求項12】
状態に関連した値は、配列における列インデックスをjとし、当該配列における列の数をMとし、定数をNとした場合、N/(2*M*log((j+M+1)/(j+M)))と状態に関連付けられた確率との積を整数へと丸めることによって得られる、請求項11に記載の算術エンコーダ。
【請求項13】
前記複数の状態の少なくとも一つに対する前記複数の値の少なくとも一つは、ある数に切り取られる、請求項11に記載の算術エンコーダ。
【請求項14】
前記数は、MPSの符号化中に再正規化を多くて1回繰り返せるようにする、請求項13に記載の算術エンコーダ。
【請求項15】
前記LUTにおける状態の数は、63であり、
前記適応レートは、0.5/0.01875の1.0/63乗であり、
LPSの最高確率は、0.5であり、
前記配列における列の数は、4であり、
前記配列の第1列における値は、N/4に切り取られる、
請求項12に記載の算術エンコーダ。
【請求項16】
前記定数Nは、512である、請求項15に記載の算術エンコーダ。
【請求項17】
イベントシーケンスのイベントが個別の値を有する確率推定値を生成する確率推定器と、
前記確率推定器に接続され、対応する確率推定値及び情報シーケンスに応じてイベントシーケンスのイベントを生成するための復号エンジンと、を備え、
前記確率推定器は、前記イベントシーケンスの前記イベントに対応するコンテクスト情報に応じて、確率推定状態マシンを使用して前記確率推定値を生成し、
前記確率推定状態マシンは、
所与の状態の番号をiとし、適応レートが1より小さいとする場合に、各状態iに対する確率を、LPSの最大確率に適応レートのi乗を乗算した値に等しくセットして、ルックアップテーブル(LUT)の状態に確率を割り当て、
MPSが観察されたときに現在の状態から状態マシンが遷移する次の状態が、当該現在の状態が最も高い状態でない場合には当該現在の状態より高い次の状態となり、当該現在の状態が最も高い状態である場合には当該現在の状態となり、更に、複数の状態に対しLPSが観察されたときに現在の状態から状態マシンが遷移する次の状態が、
現在の状態の番号+log((現在の状態の確率*適応レート+(1−適応レート))/現在の状態の確率)/log(適応レート)
の計算結果が丸められた値となるように、MPS及びLPSを観察して、遷移されるべきLUTの状態に対する状態遷移を発生することによって生成される、算術デコーダ。
【請求項18】
前記結果の丸められた値は、LPSが観察されて次の状態を発生するときに導入される丸めが平均で実質的にゼロとなるようになっている、請求項17に記載の算術デコーダ。
【請求項19】
前記LUTは、各算術エンコーダに関連付けられた複数の値を有し、該複数の値の各々は、予想されるインターバルレンジに、前記状態に関連付けられた確率を乗算した積に近似する、請求項17に記載の算術デコーダ。
【請求項20】
状態に関連した値は、配列における列インデックスをjとし、配列における列の数をMとし、定数をNとすれば、N/(2*M*log((j+M+1)/(j+M)))と状態に関連した確率との積を整数へと丸めることによって得られる、請求項19に記載の算術デコーダ。
【請求項21】
前記複数の状態の少なくとも一つに対する前記複数の値の少なくとも一つは、ある数に切り取られる、請求項19に記載の算術デコーダ。
【請求項22】
前記数は、MPSの符号化中に再正規化を多くて1回繰り返せるようにする、請求項21に記載の算術デコーダ。
【請求項23】
前記LUTにおける状態の数は、63であり、
前記適応レートは、0.5/0.01875の1.0/63乗であり、
LPSの最高確率は、0.5であり、
前記配列における列の数は、4であり、
前記配列の第1列における値は、N/4に切り取られる、
請求項20に記載の算術デコーダ。
【請求項24】
前記定数Nは、512である、請求項23に記載の算術デコーダ。
【請求項25】
イベントシーケンスのイベントが個別の値を有する確率推定値を生成するステップであって、前記確率推定値は、前記イベントシーケンスの各イベントに対応するコンテクスト情報に応じて、確率推定状態マシンを使用して生成される、ステップと、
対応する確率推定値及び情報シーケンスに応答してイベントシーケンスのイベントを生成するステップと、を含み、
前記確率推定状態マシンは、
所与の状態の番号をiとし、適応レートが1より小さいとする場合に、各状態iに対する確率を、LPSの最大確率に適応レートのi乗を乗算した値に等しくセットして、ルックアップテーブル(LUT)の状態に確率を割り当て、
MPSが観察されたときに現在の状態から状態マシンが遷移する次の状態が、当該現在の状態が最も高い状態でない場合には当該現在の状態より高い次の状態となり、当該現在の状態が最も高い状態である場合には当該現在の状態となり、更に、複数の状態に対しLPSが観察されたときに現在の状態から状態マシンが遷移する次の状態が、
現在の状態の番号+log((現在の状態の確率*適応レート+(1−適応レート))/現在の状態の確率)/log(適応レート)
の計算の結果が丸められた値になるように、MPS及びLPSを観察して遷移されるべきLUTの状態に対する状態遷移を発生することによって、生成される、復号方法。
【請求項1】
確率推定のための状態マシンを生成する方法であって、
ルックアップテーブル(LUT)の状態に確率を割り当てるステップであって、所与の状態の番号をiとし、かつ、適応レートが1より小さいとする場合に、前記状態の各状態iに対する確率を、LPSの最大確率に適応レートのi乗を乗算した値に等しくセットする処理を含むステップと、
MPS及びLPSを観察し、遷移れるべきLUTの状態に対して状態遷移を発生するステップであって、MPSが観察されたときに現在の状態から状態マシンが遷移する次の状態が、当該現在の状態が最も高い状態でない場合には、当該現在の状態より高い次の状態であり、当該現在の状態が最も高い状態である場合には当該現在の状態であり、更に、複数の状態に対しLPSが観察されたときに当該現在の状態から状態マシンが遷移する次の状態が、
現在の状態の番号+log((現在の状態の確率*適応レート+(1−適応レート))/現在の状態の確率)/log(適応レート)
の計算結果が丸められた値である、ステップと、
を含む方法。
【請求項2】
前記結果の丸められた値は、LPSが観察されて次の状態を発生するときに導入される丸めが平均で実質的にゼロとなるようになっている、請求項1に記載の方法。
【請求項3】
前記LUTは、各状態に関連付けられた複数の値を有し、該複数の値の各々は、予想されるインターバルレンジに前記状態に関連した確率を乗算した積に近似する、請求項1に記載の方法。
【請求項4】
状態に関連付けられた値は、配列における列のインデックスをjとし、当該配列における列の数をMとし、定数をNとする場合に、N/(2*M*log((j+M+1)/(j+M)))と状態に関連付けられた確率との積を整数に丸めることによって得られる、請求項3に記載の方法。
【請求項5】
前記複数の状態の少なくとも一つに対する前記複数の値の少なくとも一つは、所定値に切り取られる、請求項3に記載の方法。
【請求項6】
前記所定値は、MPSの符号化中に再正規化を多くて1回繰り返せるようにする、請求項5に記載の方法。
【請求項7】
前記LUTにおける状態の数は、63であり、
前記適応レートは、0.5/0.01875の1.0/63乗であり、
LPSの最高確率は、0.5であり、
前記配列における列の数は、4であり、
前記配列の第1列における値は、N/4に切り取られる、
請求項4に記載の方法。
【請求項8】
前記定数Nは、512である、請求項7に記載の方法。
【請求項9】
イベントシーケンスの各イベントが個別の値を有する確率推定値を発生するための確率推定器と、
前記確率推定器に接続され、各イベント及び対応の確率推定値に応じて情報シーケンスのゼロ以上のビットを生成する符号化エンジンと、
を備え、
前記確率推定器は、前記各イベントに対応するコンテクスト情報に応じて、確率推定状態マシンを使用して前記確率推定値を発生し、
前記確率推定状態マシンは、
所与の状態の番号をiとし、適応レートが1より小さい場合に、各状態iに対する確率を、LPSの最大確率に適応レートのi乗を乗算した値に等しくセットして、ルックアップテーブル(LUT)の状態に確率を割り当て、
MPSが観察されたときに現在の状態から状態マシンが遷移する次の状態が、当該現在の状態が最も高い状態でない場合には当該現在の状態より高い次の状態となり、当該現在の状態が最も高い状態である場合には当該現在の状態となり、更に、複数の状態に対しLPSが観察されたときに現在の状態から状態マシンが遷移する次の状態が、
現在の状態の番号+log((現在の状態の確率*適応レート+(1−適応レート))/現在の状態の確率)/log(適応レート)
の計算結果が丸められた値となるように、MPS及びLPSを観察して、遷移されるべきLUTの状態に対して状態遷移を発生する
ことによって生成される、算術エンコーダ。
【請求項10】
前記結果の丸められた値は、LPSが観察されて次の状態を発生するときに導入される丸めが平均で実質的にゼロとなるようになっている、請求項9に記載の算術エンコーダ。
【請求項11】
前記LUTは、各算術エンコーダに関連付けられた複数の値を有し、該複数の値の各々は、予想されるインターバルレンジに、前記状態に関連した確率を乗算した積に近似する、請求項9に記載の算術エンコーダ。
【請求項12】
状態に関連した値は、配列における列インデックスをjとし、当該配列における列の数をMとし、定数をNとした場合、N/(2*M*log((j+M+1)/(j+M)))と状態に関連付けられた確率との積を整数へと丸めることによって得られる、請求項11に記載の算術エンコーダ。
【請求項13】
前記複数の状態の少なくとも一つに対する前記複数の値の少なくとも一つは、ある数に切り取られる、請求項11に記載の算術エンコーダ。
【請求項14】
前記数は、MPSの符号化中に再正規化を多くて1回繰り返せるようにする、請求項13に記載の算術エンコーダ。
【請求項15】
前記LUTにおける状態の数は、63であり、
前記適応レートは、0.5/0.01875の1.0/63乗であり、
LPSの最高確率は、0.5であり、
前記配列における列の数は、4であり、
前記配列の第1列における値は、N/4に切り取られる、
請求項12に記載の算術エンコーダ。
【請求項16】
前記定数Nは、512である、請求項15に記載の算術エンコーダ。
【請求項17】
イベントシーケンスのイベントが個別の値を有する確率推定値を生成する確率推定器と、
前記確率推定器に接続され、対応する確率推定値及び情報シーケンスに応じてイベントシーケンスのイベントを生成するための復号エンジンと、を備え、
前記確率推定器は、前記イベントシーケンスの前記イベントに対応するコンテクスト情報に応じて、確率推定状態マシンを使用して前記確率推定値を生成し、
前記確率推定状態マシンは、
所与の状態の番号をiとし、適応レートが1より小さいとする場合に、各状態iに対する確率を、LPSの最大確率に適応レートのi乗を乗算した値に等しくセットして、ルックアップテーブル(LUT)の状態に確率を割り当て、
MPSが観察されたときに現在の状態から状態マシンが遷移する次の状態が、当該現在の状態が最も高い状態でない場合には当該現在の状態より高い次の状態となり、当該現在の状態が最も高い状態である場合には当該現在の状態となり、更に、複数の状態に対しLPSが観察されたときに現在の状態から状態マシンが遷移する次の状態が、
現在の状態の番号+log((現在の状態の確率*適応レート+(1−適応レート))/現在の状態の確率)/log(適応レート)
の計算結果が丸められた値となるように、MPS及びLPSを観察して、遷移されるべきLUTの状態に対する状態遷移を発生することによって生成される、算術デコーダ。
【請求項18】
前記結果の丸められた値は、LPSが観察されて次の状態を発生するときに導入される丸めが平均で実質的にゼロとなるようになっている、請求項17に記載の算術デコーダ。
【請求項19】
前記LUTは、各算術エンコーダに関連付けられた複数の値を有し、該複数の値の各々は、予想されるインターバルレンジに、前記状態に関連付けられた確率を乗算した積に近似する、請求項17に記載の算術デコーダ。
【請求項20】
状態に関連した値は、配列における列インデックスをjとし、配列における列の数をMとし、定数をNとすれば、N/(2*M*log((j+M+1)/(j+M)))と状態に関連した確率との積を整数へと丸めることによって得られる、請求項19に記載の算術デコーダ。
【請求項21】
前記複数の状態の少なくとも一つに対する前記複数の値の少なくとも一つは、ある数に切り取られる、請求項19に記載の算術デコーダ。
【請求項22】
前記数は、MPSの符号化中に再正規化を多くて1回繰り返せるようにする、請求項21に記載の算術デコーダ。
【請求項23】
前記LUTにおける状態の数は、63であり、
前記適応レートは、0.5/0.01875の1.0/63乗であり、
LPSの最高確率は、0.5であり、
前記配列における列の数は、4であり、
前記配列の第1列における値は、N/4に切り取られる、
請求項20に記載の算術デコーダ。
【請求項24】
前記定数Nは、512である、請求項23に記載の算術デコーダ。
【請求項25】
イベントシーケンスのイベントが個別の値を有する確率推定値を生成するステップであって、前記確率推定値は、前記イベントシーケンスの各イベントに対応するコンテクスト情報に応じて、確率推定状態マシンを使用して生成される、ステップと、
対応する確率推定値及び情報シーケンスに応答してイベントシーケンスのイベントを生成するステップと、を含み、
前記確率推定状態マシンは、
所与の状態の番号をiとし、適応レートが1より小さいとする場合に、各状態iに対する確率を、LPSの最大確率に適応レートのi乗を乗算した値に等しくセットして、ルックアップテーブル(LUT)の状態に確率を割り当て、
MPSが観察されたときに現在の状態から状態マシンが遷移する次の状態が、当該現在の状態が最も高い状態でない場合には当該現在の状態より高い次の状態となり、当該現在の状態が最も高い状態である場合には当該現在の状態となり、更に、複数の状態に対しLPSが観察されたときに現在の状態から状態マシンが遷移する次の状態が、
現在の状態の番号+log((現在の状態の確率*適応レート+(1−適応レート))/現在の状態の確率)/log(適応レート)
の計算の結果が丸められた値になるように、MPS及びLPSを観察して遷移されるべきLUTの状態に対する状態遷移を発生することによって、生成される、復号方法。
【図1】
【図2】
【図3】
【図4】
【図5】
【図6】
【図7】
【図8】
【図9】
【図10】
【図11】
【図12】
【図13】
【図14A】
【図14B】
【図15A】
【図15B】
【図16A】
【図16B】
【図17】
【図2】
【図3】
【図4】
【図5】
【図6】
【図7】
【図8】
【図9】
【図10】
【図11】
【図12】
【図13】
【図14A】
【図14B】
【図15A】
【図15B】
【図16A】
【図16B】
【図17】
【公開番号】特開2013−51721(P2013−51721A)
【公開日】平成25年3月14日(2013.3.14)
【国際特許分類】
【出願番号】特願2012−235859(P2012−235859)
【出願日】平成24年10月25日(2012.10.25)
【分割の表示】特願2011−248692(P2011−248692)の分割
【原出願日】平成15年9月19日(2003.9.19)
【公序良俗違反の表示】
(特許庁注:以下のものは登録商標)
1.フロッピー
【出願人】(392026693)株式会社エヌ・ティ・ティ・ドコモ (5,876)
【Fターム(参考)】
【公開日】平成25年3月14日(2013.3.14)
【国際特許分類】
【出願日】平成24年10月25日(2012.10.25)
【分割の表示】特願2011−248692(P2011−248692)の分割
【原出願日】平成15年9月19日(2003.9.19)
【公序良俗違反の表示】
(特許庁注:以下のものは登録商標)
1.フロッピー
【出願人】(392026693)株式会社エヌ・ティ・ティ・ドコモ (5,876)
【Fターム(参考)】
[ Back to top ]