(57)【特許請求の範囲】
【請求項１】
復号に必要な算術符号の確率推定値を格納するメモリと、
入力された２値算術符号を前記確率推定値を用いて復号し、２値シンボルを得る算術符号復号器と、
前記復号された２値シンボルを蓄積するバッファと、
前記バッファから前記２値シンボルを取り出して文法解析を行いながら復号して出力データを得る第一のデータ復号器と、
前記２値シンボルに対して前記文法解析と同一の文法解析を行い前記確率推定値の更新に必要なデータを復号する第二のデータ復号器と、
を有し、
前記メモリ、前記算術符号復号器及び前記第二のデータ復号器は、前記算術符号復号器に入力されるストリームのビット、バイトまたはバイト列に合わせて処理を進め、前記第一のデータ復号器は復号後の信号出力に合わせて処理を進める２値化算術符号の復号器。
【請求項２】
入力されたデータを２値シンボルに変換する２値化変換器と、
前記２値シンボルを蓄積するバッファと、
前記バッファから２値シンボルを取り出して算術符号を生成する算術符号化器と、
前記算術符号化器が取り出した２値シンボル数と生成した符号のビット数から、２値シンボル数と符号ビット数の関係を推定し、前記バッファの蓄積量から算術符号化後に生成される符号ビット数を求めるビット数推定器と、
前記ビット数推定器で推定された前記算術符号化後に生成される符号ビット数を参考にして、入力信号から、ストリームの構成に必要な情報であるブロック情報を生成し、前記２値化変換器へ出力するブロック符号化器と、
有し、
前記２値化変換器、前記ビット推定器及び前記ブロック符号化器は、前記ブロック符号化器に入力される信号のビット、バイト、バイト列に合わせて処理を進め、前記算術符号化器はストリームの出力に合わせて処理を進める２値化算術符号の符号化器。
【請求項３】
２値シンボルを蓄積するためのバッファと確率推定値を格納するメモリとを有する復号器における復号方法であって、
入力された２値算術符号を前記確率推定値を用いて復号し、２値シンボルを得て前記バッファに書き込む算術符号復号ステップと、
前記バッファから前記２値シンボルを取り出して文法解析を行いながら復号して出力データを得る第一のデータ復号ステップと、
前記２値シンボルに対して前記文法解析と同一の文法解析を行い前記確率推定値の更新に必要なデータを復号する第二のデータ復号ステップと、
を有し、
前記メモリ、前記算術符号復号ステップ及び前記第二のデータ復号ステップを、前記算術符号復号ステップに入力されるストリームのビット、バイトまたはバイト列に合わせて処理を進め、前記第一のデータ復号ステップを復号後の信号出力に合わせて処理を進める２値化算術符号の復号方法。
【請求項４】
２値シンボルを蓄積するためのバッファを有する符号化器における符号化方法であって、
入力されたデータを２値シンボルに変換し、前記バッファに書き込む２値化変換ステップと、
前記バッファから２値シンボルを取り出して算術符号を生成する算術符号化ステップと、
前記算術符号化ステップで取り出した２値シンボル数と生成した符号のビット数から、２値シンボル数と符号ビット数の関係を推定し、前記バッファの蓄積量から算術符号化後に生成される符号ビット数を求めるビット数推定ステップと、
前記ビット数推定ステップから与えられる推定生成ビット数を参考にして、入力信号からストリーム構成に必要な情報であるブロック情報を生成し、前記２値化変換ステップへ供給するブロック符号化ステップと、
を有し、
前記２値化変換ステップ、前記ビット推定ステップ及び前記ブロック符号化ステップを、前記ブロック符号化ステップに入力される信号のビット、バイト、バイト列に合わせて処理を進め、前記算術符号化ステップをストリームの出力に合わせて処理を進める２値化算術符号の符号化方法。
【請求項５】
２値シンボルを蓄積するためのバッファと確率推定値を格納するメモリとを有するコンピュータに実行させるためのプログラムであって、
前記コンピュータに、
入力された２値算術符号を前記確率推定値を用いて復号し、２値シンボルを得て前記バッファに書き込む算術符号復号ステップと、
前記バッファから前記２値シンボルを取り出して文法解析を行いながら復号して出力データを得る第一のデータ復号ステップと、
前記２値シンボルに対して前記文法解析と同一の文法解析を行い前記確率推定値の更新に必要なデータを復号する第二のデータ復号ステップと、
を実行させ、
前記メモリ、前記算術符号復号ステップ及び前記第二のデータ復号ステップを、前記算術符号復号ステップに入力されるストリームのビット、バイトまたはバイト列に合わせて処理を進め、前記第一のデータ復号ステップを復号後の信号出力に合わせて処理を進めるためのプログラム。
【請求項６】
２値シンボルを蓄積するためのバッファを有するコンピュータに実行させるためのプログラムであって、
前記コンピュータに、
入力されたデータを２値シンボルに変換し、前記バッファに書き込む２値化変換ステップと、
前記バッファから２値シンボルを取り出して算術符号を生成する算術符号化ステップと、
前記算術符号化ステップで取り出した２値シンボル数と生成した符号のビット数から、２値シンボル数と符号ビット数の関係を推定し、前記バッファの蓄積量から算術符号化後に生成される符号ビット数を求めるビット数推定ステップと、
前記ビット数推定ステップから与えられる推定生成ビット数を参考にして、入力信号からストリーム構成に必要な情報であるブロック情報を生成し、前記２値化変換ステップへ供給するブロック符号化ステップと、
を実行させ、
前記２値化変換ステップ、前記ビット推定ステップ及び前記ブロック符号化ステップを、前記ブロック符号化ステップに入力される信号のビット、バイト、バイト列に合わせて処理を進め、前記算術符号化ステップをストリームの出力に合わせて処理を進めるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、算術符号の復号および符号化に関する。特に、多値シンボルを２値化した２値シンボル列の算術符号の復号および符号化の実装に関する。
【背景技術】
【０００２】
２値化算術符号化は圧縮符号化技術の１つである。２値化算術符号化では、１つの多値シンボルを２値化して２値シンボル列を生成し、この２値シンボル列を算術符号化することで、最終的な２値化算術符号を得る。算術符号はハフマン符号などと比較すると処理コストが高く、これまでファイル圧縮や静止画圧縮などの実時間性が要求されないアプリケーションで利用されてきたにすぎない。ところが近年のＬＳＩの高速化にともない、映像の符号化にも採用されるようになってきた。その１つに、Ｉｎｔｅｒｎａｔｉｏｎａｌ  Ｔｅｌｅｃｏｍｍｕｎｉｃａｔｉｏｎ  Ｕｎｉｏｎ  Ｔｅｌｅｃｏｍｍｕｎｉｃａｔｉｏｎ  Ｓｔａｎｄａｒｄｉｚａｔｉｏｎ  Ｓｅｃｔｏｒ（ＩＴＵ−Ｔ）が制定している新しいビデオコーデックの国際標準規格Ｈ．２６４のＭａｉｎ  Ｐｒｏｆｉｌｅがある。【０００３】
Ｈ．２６４では２値化算術符号をＣｏｎｔｅｘｔ−ｂａｓｅｄ  Ａｄａｐｔｉｖｅ  Ｂｉｎａｒｙ  Ａｒｉｔｈｍｅｔｉｃ  Ｃｏｄｉｎｇ（ＣＡＢＡＣ：キャバック）と呼んでいる。ＣＡＢＡＣの詳細については、ＩＥＥＥ学会のＩｎｔｅｒｎａｔｉｏｎａｌ  Ｃｏｎｆｅｒｅｎｃｅ  ｏｎ  Ｉｍａｇｅ  Ｐｒｏｃｅｓｓｉｎｇ（ＩＣＩＰ）において、Ｄ．Ｍａｒｐｅらが、２００２年会合で「Ｃｏｎｔｅｘｔ−ｂａｓｅｄ  ａｄａｐｔｉｖｅ  ｂｉｎａｒｙ  ａｒｉｔｈｍｅｔｉｃ  ｃｏｄｉｎｇ  ｉｎ  ＪＶＴ／Ｈ．２６Ｌ」という題で報告しており（２００２  ＩＥＥＥ  Ｉｎｔｅｒｎａｔｉｏｎａｌ  Ｃｏｎｆｅｒｅｎｃｅ  ｏｎ  Ｉｍａｇｅ  Ｐｒｏｃｅｓｓｉｎｇ，ＩＳＢＮ：０−７８０３−７６２３−４  ＩＥＥＥ  Ｃａｔａｌｏｇ  Ｎｏ．：０２ＣＨ３７３９６，ｐａｇｅｓ  ２−５１３〜２−５３６）、２００１年会合で「Ｖｉｄｅｏ  ｃｏｍｐｒｅｓｓｉｏｎ  ｕｓｉｎｇ  ｃｏｎｔｅｘｔ−ｂａｓｅｄ  ａｄａｐｔｉｖｅ  ａｒｉｔｈｍｅｔｉｃ  ｃｏｄｉｎｇ」という題で報告している（２００１  ＩＥＥＥ  Ｉｎｔｅｒｎａｔｉｏｎａｌ  Ｃｏｎｆｅｒｅｎｃｅ  ｏｎ  Ｉｍａｇｅ  Ｐｒｏｃｅｓｓｉｎｇ，ＩＳＢＮ：０−７８０３−６７２５−１，ｐａｇｅｓ  ５５８〜５６１）。【０００４】
ＣＡＢＡＣでは、まず符号化すべき多値シンボルを２値シンボル（Ｂｉｎ）の列に２値化変換（Ｂｉｎａｒｉｚａｔｉｏｎ）し、各ＢｉｎをＢｉｎごとに定められたコンテクスト（Ｃｏｎｔｅｘｔ）に対する確率推定値にしたがって２値算術符号化する。２値化変換は数値を数式で規定されたフォーマットに合わせて多値をビットパターンに変換するが、これは簡易な可変長符号化（ＶＬＣ）と考えることができる。コンテクストの選択では、もともとの多値シンボルが何を表しているか、周辺ブロックのパラメータ、２値シンボル列の何番目か、という状況が用いられる。逆に復号では、現在復号しようとしている２値シンボルのコンテクストから確率推定値を求め、算術符号の復号を行う。２値シンボルが復元されれば、確率推定値の更新を行うとともに、次に復号すべき２値シンボルのコンテクストを選択する。【０００５】
理想的な算術符号化はデータをエントロピーの限界まで圧縮できるので、理論的には１ビットで無限のＢｉｎを表すことができる。ただしこのままでは実装が困難なので、ＣＡＢＡＣでは簡略化した算術符号化を採用するとともに、１ビット当たりの平均Ｂｉｎ数に上限を設けている。簡略化では乗算をテーブル引きで代用しており、１つのＢｉｎのデコードに必要な演算を、テーブル引き、比較、減算に抑えている。【０００６】
Ｈ．２６４  ＣＡＢＡＣのような２値化算術符号化では、算術符号の復号および符号化の処理コストが高い。【０００７】
図１にＨ．２６４復号器の全体構成を示す。【０００８】
Ｈ．２６４復号器はストリームを受信してとどめておくＣＰＢバッファ４１と、各フレームをフレーム間隔ごとに復号する瞬時復号器４２から構成される。瞬時復号器４２は、ＣＡＢＡＣ復号器４３とブロック復号器４４から構成される。ブロック復号器４４は、逆量子化、逆離散整数変換、動き補償予測、ループ内フィルタ処理などを行っており、画素数に比例した処理コストとなっている。【０００９】
これに対してＣＡＢＡＣ復号器４３の処理コストはＢｉｎ数に比例する。【００１０】
図２にＣＡＢＡＣ復号器の詳細を示す。【００１１】
ＣＡＢＡＣ復号器５１は２値算術符号復号器５４、逆２値化変換器５５、コンテクストごとの確率推定値を保存するメモリ５２と、これらを制御する制御器５３から構成される。処理の単位はＢｉｎの復号であり、制御器５３はＢｉｎを復号するたびに、確率推定値を更新するとともに、Ｈ．２６４規格の文法にしたがって内部のステートを遷移させる。これらの処理は複数のＢｉｎをまとめて行うことができないため、Ｂｉｎ数が処理コストを決定する。【００１２】
ここで具体的にどれだけの処理コストになるのかを算出してみる。各フレームの圧縮率はフレームの符号化タイプ（フレーム内もしくはフレーム間）や予測の的中度合い、画質によって異なるため、各フレームのビット数はフレームごとに変動する。つまり、ＣＡＢＡＣ復号器の処理コストはフレームごとに変動する。規格では１フレームの最大ビット数は２０４８×Ｍａｘ  ＭＢＰＳ×Ｄｅｌｔａ  Ｔｉｍｅ×Ｃｈｒｏｍａ  Ｆｏｒｍａｔ  Ｆａｃｔｏｒ／ＭｉｎＣＲで与えられており、フレーム期間平均の最大ビットレートに換算すると２０４８×Ｍａｘ  ＭＢＰＳ×Ｃｈｒｏｍａ  Ｆｏｒｍａｔ  Ｆａｃｔｏｒ／ＭｉｎＣＲとなる。ここでＭａｘ  ＭＢＰＳは１秒当たりの最大マクロブロック数、Ｄｅｌｔａ  Ｔｉｍｅはフレーム時間間隔、Ｃｈｒｏｍａ  Ｆｏｒｍａｔ  Ｆａｃｔｏｒは輝度信号に対して色信号を加えた場合のサンプル数の比率、ＭｉｎＣＲは最低圧縮率である。【００１３】
Ａｎｎｅｘ  Ａ記載のＬｅｖｅｌ  ４．１ではＭａｘ  ＭＢＰＳ＝２４５７６０、Ｃｈｒｏｍａ  Ｆｏｒｍａｔ  Ｆａｃｔｏｒ＝１．５、ＭｉｎＣＲ＝２なので、最大ビットレートは３７７Ｍｂｐｓとなる。Ｂｉｎ対ビットの圧縮率は１．３３以下となるように規定されているので、最大Ｂｉｎレートに換算すると５０３Ｍｂｉｎ／ｓｅｃとなる。最大ビットレートをフレーム期間平均で求めているので、ここでの最大Ｂｉｎレートはフレーム期間平均で処理すべきＢｉｎの数をフレーム期間で除した値となっている。復号器の性能がこの最大Ｂｉｎレートを達成できていないと、フレームを表示すべき時刻までに復号処理が終わらず、フレームの欠落といった大きな画質劣化を引き起こす。【００１４】
以上は復号器の実装について説明したが、逆の動作を行う符号化器も同様になる。【００１５】
図３にＨ．２６４符号化器の構成を示す。【００１６】
ブロック符号化器６３は入力された画素レートで、動き補償予測、離散整数変換、量子化、逆量子化、逆離散整数変換、ループ内フィルタ処理などを行う。その後、ブロック情報は２値化変換器６４でＢｉｎ列に変換される。Ｂｉｎ列は算術符号化器６５で符号ビット列に変換され、出力バッファ６６に送られる。出力バッファ６６の蓄積量はブロック符号化器６３にフィードバックされ、ブロック符号化器６３内部の符号量制御に用いられる。【００１７】
２値化ではブロック情報の１つの要素、たとえば変換係数が複数のＢｉｎに変換される。そのため、Ｂｉｎ列の生成速度は瞬間的には画素レートの１０倍以上になる。それ以後のＢｉｎ列を扱う制御器６２やメモリ６１、算術符号化器６５はその速度で動く必要がある。フレーム期間での処理を考えると、Ｈ．２６４符号化器の最大ＢｉｎレートはＨ．２６４復号器の場合と同じく５０３Ｍｂｉｎ／ｓｅｃとなる。【００１８】
従来の技術では、高いビットレートでの実時間処理が依然として困難である。たとえば、Ｈ．２６４規格書の記載の通りに復号処理を行おうとすると、処理すべきＢｉｎレートは非現実的な値となる。Ｈ．２６４  Ｌｅｖｅｌ  ４．１の規定を満たす最大Ｂｉｎレートは５０３Ｍｂｉｎ／ｓｅｃであり、１つのＢｉｎを２サイクルで処理できたとしても、１ＧＨｚ以上の周波数でＣＡＢＡＣ復号器や算術符号化器を動作させなければならない。この値は現状のＬＳＩで容易に、もしくは安価に実現可能な速度の数倍となってしまっている。
【発明の開示】
【００１９】
本発明の目的は、従来技術と比較して、低い最大Ｂｉｎレートで実時間での２値化算術符号の復号を行う復号器、および符号化を行う符号化器を提供することにある。
【００２０】
上記目的を達成するために、本発明の復号器は、２値算術符号の入力に応じて、２値算術符号を復号し、２値シンボルを得る算術符号復号手段と、復号された２値シンボルを蓄積するバッファと、バッファから２値シンボルを取り出す際、自身の出力に応じて２値シンボルを取り出し、多値シンボルに変換して出力する逆２値化変換手段を有することを特徴とする。
【００２１】
この構成において、算術符号復号手段と逆２値化変換手段は別々に動作しており、通常異なる速度で処理を進める。
【００２２】
上記目的を達成するために、本発明の符号化器は、多値シンボルの入力に応じて、多値シンボルを２値シンボルに変換する２値化変換手段と、２値シンボルを蓄積するバッファと、バッファから２値シンボルを取り出す際、自身の出力に応じて２値シンボルを取り出して２値算術符号を生成する算術符号化手段を有することを特徴とする。
【００２３】
この構成において、算術符号化手段と２値化変換手段は別々に動作しており、通常異なる速度で処理を進める。算術符号化手段が達成すべき処理性能は出力符号レートの最大値で規定できる。一方、２値化変換手段では多値シンボルの単位で処理が可能なため、これが達成すべき処理性能は入力多値シンボルレートの最大値で規定できる。
【００２４】
本発明によれば、２値化算術符号の復号器および符号化器が達成すべき２値シンボル処理レートの最大値を大幅に下げることができる。本発明の算術符号復号手段が達成すべき処理性能は入力符号レートの最大値で規定でき、同様に本発明の算術符号の符号化手段が達成すべき処理性能は出力符号レートの最大値で規定できる。
【００２５】
たとえば、Ｈ．２６４のＬｅｖｅｌ  ４．１に適用する場合、Ｍａｘ  Ｖｉｄｅｏ  Ｂｉｔｒａｔｅが５０Ｍｂｐｓなので、最大Ｂｉｎレートは６６．７Ｍｂｉｎ／ｓｅｃとなる。この値は従来の技術の場合の７分の１以下となっており、実装が大幅に容易になることが分かる。
【００２６】
従来技術ではＣＰＢバッファにストリームをためていたが本発明では不要となる。その代わりにＣＰＢバッファよりも若干大きなメモリ手段を必要としている。Ｈ．２６４の場合には算術符号の圧縮率が１．３３以下となるように制限されているので、メモリ手段はＣＰＢバッファの１．３３倍の大きさがあればよい。
【００２７】
本発明の符号化器は２値もしくは多値シンボルのバッファを持っているため、バッファ遅延分だけ遅れるが、ビット数推定手段が生成される実際の符号ビット数を得ることができるので、遅れのない推定値をその代替として提供できる。また、ビデオ符号化器などの符号量制御が必要な場合、遅延された生成ビット数を用いると制御が不安定になるが、本発明ではその推定値が使えるのでバッファ遅延の影響を抑圧できる。
【図面の簡単な説明】
【００２８】
【図１】国際標準規格ＩＴＵ−Ｔ  Ｈ．２６４復号器のブロック図である。
【図２】Ｈ．２６４  ＣＡＢＡＣ復号器の内部のブロック図である。
【図３】Ｈ．２６４符号化器のブロック図である。
【図４】本発明の２値化算術符号の復号器を用いた映像復号器のブロック図である。
【図５】本発明の２値化算術符号の符号化器を用いた映像符号化器のブロック図である。
【図６】本発明の２値化算術符号の復号器もしくは符号化器のブロック図である。
【図７】本発明の２値化算術符号の復号処理を示すフローチャートである。
【図８】本発明の復号処理サブルーチンのフローチャートである。
【図９】本発明の２値化算術符号の符号化処理を示すフローチャートである。
【図１０】本発明の符号化処理サブルーチンのフローチャートである。
【発明を実施するための最良の形態】
【００２９】
本発明の算術符号の復号器は、２値算術符号の入力に応じて復号して２値シンボルを得る算術符号復号器と、２値シンボルを蓄積する中間バッファと、中間バッファから２値シンボル列を取り出して多値シンボルに変換して出力し、この多値シンボルの出力に応じて中間バッファから２値シンボル列を取り出す逆２値化変換手段を備える。【００３０】
また、本発明における算術符号の符号化器は、多値シンボルの入力に応じて多値シンボルを２値シンボルに変換する２値化変換手段と、２値シンボルを蓄積するバッファと、バッファから２値シンボルを取り出す際、自身の出力に応じて２値シンボルを取り出して２値算術符号を生成する算術符号化手段を備える。【００３１】
また、本発明における算術符号の復号器は、算術符号の入力に応じて算術符号を復号して多値シンボルを得る算術符号復号手段と、多値シンボルを蓄積するバッファと、バッファから多値シンボルを取り出す際、自身の出力に応じて多値シンボルを取り出して出力シンボルに変換して出力する逆変換手段を備える。【００３２】
また、本発明における算術符号の符号化器は、入力シンボルの入力に応じて入力シンボルを多値シンボルに変換する変換手段と、多値シンボルを蓄積するバッファと、バッファから多値シンボルを取り出す際、自身の出力に応じて多値シンボルを取り出して算術符号を生成する算術符号化手段を備える。【００３３】
図４は、本発明の２値化算術符号の復号器を用いた映像復号器のブロック図である。【００３４】
算術符号復号器１０は入力されたストリームの算術符号を復号して２値シンボル（Ｂｉｎ）を得て、制御器１１、逆２値化変換機１２に供給するとともに、中間バッファ１４に格納する。復号に必要となるコンテクストの確率推定値は制御器１１から供給される。【００３５】
制御器１１はストリームの文法にしたがい、現在復号すべき２値シンボルからコンテクストを選択し、メモリ１３からその確率推定値を取得するとともに、確率推定値を算術符号復号器１０に供給する。コンテクストの選択においては、必要であればメモリ１３に格納されているブロック情報を用いる。制御器１１は算術符号復号器１０から２値シンボルを得ると、メモリ１３に格納されている確率推定値を更新するとともに、２値シンボル列の構成情報を逆２値化変換器１２に供給する。構成情報としては、多値シンボルの示しているパラメータ名、２値シンボル列のフォーマット情報、逆変換を行うタイミングなどがある。【００３６】
逆２値化変換器１２は、算術符号復号器１０から得られる２値シンボルと制御器１１から供給される構成情報から、必要に応じて２値シンボル列を多値シンボルに変換し、その結果として得られるブロック情報をメモリ１３に格納する。ストリームに含まれるブロック情報には、量子化された変換係数、量子化パラメータ、有効ブロックパターン、予測モード、動きベクトルなどがあるが、メモリ１３に格納すべきブロック情報は制御器１１が参照するものである。【００３７】
中間バッファ１４は、算術符号復号器１０で得られた２値シンボルを格納し、後段の制御器１５と逆２値化変換器１６に２値シンボルを供給する。また、制御器１５に２値シンボルを供給する際、制御器１５からの指示に基づいて、２値シンボルを供給する。【００３８】
制御器１５はストリームの文法にしたがい、中間バッファ１４から２値シンボル列を得て、構成情報を逆２値化変換器１６に供給する。【００３９】
逆２値化変換器１６は、中間バッファ１４から２値シンボル列を得て、制御器１５から供給される構成情報から、２値シンボル列を多値シンボルに変換し、その結果として得られるブロック情報をブロック復号器１７に供給する。【００４０】
ブロック復号器１７は、逆２値化変換器１６から供給されるブロック情報にもとづき、逆量子化、逆整数変換、動き補償予測、ループ内フィルタの処理を行うことで復号画像を得て、得られた復号画像を出力する。【００４１】
中間バッファ１４よりも前段のブロックである算術符号復号器１０、制御器１１、逆２値化変換器１２、メモリ１３は、算術符号復号器１０に入力されるストリームのビット、バイトまたはバイト列などに合わせて処理を進めていく。これに対して、中間バッファ１４よりも後段のブロックである制御器１５、逆２値化変換器１６、ブロック復号器１７は、復号画像の出力に合わせて処理を進める。このように算術符号復号器１０と逆２値化変換器１６は別々に動作しており、通常異なる速度で処理を進めている。中間バッファ１４は前後の処理速度の違いを吸収する。【００４２】
図５は本発明の２値化算術符号の符号化器を用いた映像符号化器のブロック図である。【００４３】
ブロック符号化器２０は、ビット数推定器２７から与えられる推定生成ビット数を参考にして、入力画像に対して動きベクトル探索、動き補償予測、離散整数変換、量子化、逆量子化、逆離散整数変換、ループ内フィルタの処理を行い、ブロック情報を生成する。ブロック情報はストリーム構成に必要な情報であり、量子化された変換係数、量子化パラメータ、有効ブロックパターン、予測モード、動きベクトルなどが含まれる。【００４４】
得られたブロック情報は２値化変換器２１で２値シンボル列に変換され、その結果は中間バッファ２２に格納される。【００４５】
中間バッファ２２は、２値化変換器２１で変換された２値シンボル列を格納し、算術符号化器２５からの指示にもとづいて、算術符号化器２５に２値シンボルを供給する。また、中間バッファ２２は、蓄積量をビット数推定器２７に供給する。【００４６】
逆２値化変換器２３は、中間バッファ２２から得られる２値シンボル列と、制御器２４から供給される構成情報から、ブロック情報を復元し、メモリ２６に格納する。ここで復元すべきブロック情報は制御器２４が参照するものである。【００４７】
制御器２４はストリームの文法にしたがい、現在符号化すべき２値シンボルからコンテクストを選択し、メモリ２６からその確率推定値を取得するとともに、確率推定値を算術符号化器２５に供給する。コンテクストの選択においては、必要であればメモリ２６に格納されているブロック情報を用いる。中間バッファ２２から２値シンボルを得ると、メモリ２６に格納されている確率推定値を更新するとともに、２値シンボル列の構成情報を逆２値化変換器２３に供給する。【００４８】
算術符号化器２５は、中間バッファ２２から得た２値シンボルと、制御器２４から得た確率推定値から２値算術符号化を行い、得られたストリームを出力する。また、算術符号化で読み出した２値シンボル数と生成した符号のビット数をビット数推定器２７に供給する。【００４９】
ビット数推定器２７は、算術符号化器２５から供給される２値シンボル数と符号ビット数から、２値シンボル数と符号ビット数の関係を推定し、中間バッファ２２から供給される蓄積量をビット数に換算して生成ビット数を求め、ブロック符号化器２０に供給する。【００５０】
中間バッファ２２よりも前段のブロックであるブロック符号化器２０、２値化変換器２１、ビット数推定器２７は、ブロック符号化器２０に入力される画像のビット、バイト、バイト列に合わせて処理を進めていく。これに対して、中間バッファ２２よりも後段のブロックである逆２値化変換器２３、制御器２４、算術符号化器２５、メモリ２６はストリームの出力に合わせて処理を進める。このように２値化変換器２１と算術符号化器２５は別々に動作しており、通常異なる速度で処理を進めている。中間バッファ２２は前後の処理速度の違いを吸収する。【００５１】
図６は本発明の別の実施の形態を示すブロック図である。【００５２】
図６で本発明の２値算術符号の復号器を構成する場合、処理部３１は算術符号の復号を行い、処理部３２は逆２値化変換を行う。メモリ３３は、処理部３１と処理部３２からアクセス可能であり、処理部３１の入力となる符号列、処理部３１の出力かつ処理部３２の入力となる２値シンボル列、処理部３２の出力となる多値シンボル、処理で必要となる確率期待値やブロック情報などを保持する。【００５３】
なお、図６は論理的な構成を示すために処理部３１と処理部３２を分けているが、オペレーティングシステムがマルチプロセス機能を提供している場合や、米Ｉｎｔｅｌ製Ｈｙｐｅｒ  Ｔｈｒｅａｄｉｎｇ対応ＣＰＵのように単体プロセッサでマルチプロセス処理が可能な場合、物理的には１つとなる。また、メモリ３３は物理的に単一メモリである必要はなく、処理部３１からしかアクセスしない変数はバス接続でなく処理部３１に直結していても構わない。【００５４】
次に図７を参照して、処理部３１で算術符号の復号を行う場合の動作を説明する。【００５５】
符号化方式のシンタックスには、符号化モード、動きベクトル、コーデッドフラグ、係数が存在し、これらが２値算術符号化されていることを想定している。ここで、符号化モードからは動きベクトル情報の有無を知ることができ、コーデッドフラグは係数の有無を知ることができる。【００５６】
まず、ステップＡ１００において初期化を行う。初期化では、コンテクストごとの確率推定値を初期値に設定する。ステップＡ１１０ではブロックの符号化モードを復号する。ステップＡ１１１では動きベクトル情報があるかどうかで分岐する。動きベクトル情報がある場合にはステップＡ１２０へ、動きベクトル情報がない場合にはステップＡ１３０へ進む。【００５７】
ステップＡ１２０では動きベクトル水平値を復号する。ステップＡ１２１では動きベクトル垂直値を復号する。ステップＡ１３０ではコーデッドフラグを復号する。ステップＡ１３１では係数があるかないかで分岐する。係数がある場合にはステップＡ１４０へ、係数がない場合にはステップＡ１５０へ進む。【００５８】
ステップＡ１４０では係数を復号する。ステップＡ１４１では係数が終了かどうかで分岐する。終了の場合にはステップＡ１５０へ、係数が続いている場合にはステップＡ１４０へ進む。【００５９】
ステップＡ１５０は符号列の終了かどうかで分岐する。終了でなければステップＡ１１０へ進む。【００６０】
これらのステップで行われる復号では、多値シンボルを復号するサブルーチンを呼び出している。このサブルーチンは図８の動作を行う。【００６１】
図８を参照して、サブルーチンを説明する。【００６２】
まずステップＡ１０ではシンボル列バッファを空にする。ステップＡ１１では現在のシンタックスに適合するコンテクストを選択する。必要であれば周辺ブロックの情報を用いる。ステップＡ１２では現在のコンテクストの確率推定値を取得する。ステップＡ１３では算術符号の復号を行う。符号の入力を待ち、入力されれば符号語の現在値と確率推定値を比較して、大小関係から２値シンボルを得る。２値シンボルの０と１に対して対称の動作をするのであれば、確率推定値をＭＰＳの値とＭＰＳの確率推定値とで表現（対称表現）することもできる。ここで、ＭＰＳとは発生確率の推定値の高いシンボルであり、ＭＰＳの確率推定値は０．５から１の値を取る。ステップＡ１４では得られた２値シンボルをシンボル列バッファに蓄えるとともに、メモリへ出力する。ステップＡ１５では２値シンボルの値に応じて確率推定値を更新する。確率推定値が対称表現の場合、ＭＰＳの確率推定値が０．５未満となれば、ＭＰＳを反転する。ステップＡ１６では、シンボル列バッファ内の２値シンボル列が、完結した２値シンボル列を構成しているかどうかで分岐する。完結した２値シンボル列を構成していればステップＡ１７へ進み、そうでなければステップＡ１１に戻って算術符号の復号を続ける。【００６３】
ステップＡ１７では必要に応じて逆２値化変換を行う。必要となる条件としては、シンタックスに関わる要素やコンテクスト選択で参照される可能性がある要素がある。【００６４】
次に処理部３２で逆２値化変換を行う場合の動作を説明する。全体の処理の流れは処理部３１と同様に図７のフローで動作する。ただし、呼び出される復号サブルーチンが処理部３１とは異なる。処理部３２で用いる復号サブルーチンは逆２値変換であり、２値シンボル列から多値シンボルを復号するものとなる。処理部３２は算術符号に関係しないので、ステップＡ１００で確率推定値を初期値に設定する必要はない。【００６５】
図６で本発明の２値算術符号の符号化器を構成する場合、処理部３１は２値化変換を行い、処理部３２は算術符号化を行う。メモリ３３は、処理部３１と処理部３２からアクセス可能であり、処理部３１の入力となる多値シンボル、処理部３１の出力かつ処理部３２の入力となる２値シンボル列、処理部３２の出力となる符号列、処理で必要となる確率期待値やブロック情報などを保持する。【００６６】
次に図９を参照して、処理部３１で２値化変換を行う場合の動作を説明する。【００６７】
まず、ステップＡ２００において初期化を行う。ステップＡ２１０ではブロックの符号化モードを符号化処理する。ステップＡ２１１では動きベクトル情報があるかどうかで分岐する。ある場合にはステップＡ２２０へ、ない場合にはステップＡ２３０へ進む。【００６８】
ステップＡ２２０では動きベクトル水平値を符号化処理する。ステップＡ２２１では動きベクトル垂直値を符号化処理する。ステップＡ２３０ではコーデッドフラグを符号化処理する。ステップＡ２３１では係数があるかないかで分岐する。係数がある場合にはステップＡ２４０へ、係数がない場合にはステップＡ２５０へ進む。【００６９】
ステップＡ２４０では係数を符号化処理する。ステップＡ２４１では係数終了かどうかで分岐する。終了の場合にはステップＡ２５０へ、係数が続いている場合にはステップＡ２４０へ進む。【００７０】
ステップＡ２５０は符号化の終了かどうかで分岐する。符号化の終了でなければステップＡ２１０へ進む。これらのステップで行われる符号化処理は２値化変換であり、多値シンボルを２値シンボル列に変換し、出力する出力サブルーチンを呼び出している。出力サブルーチンでは、出力した２値シンボル数をカウントし、外部からの参照可能にしておく。【００７１】
次に処理部３２で算術符号化を行う場合の動作を説明する。全体の処理の流れは処理部３１と同様に図９のフローで動作する。ただし、ステップＡ２００の初期化と呼び出される符号化処理サブルーチンが処理部３１とは異なる。処理部３２で用いる符号化処理サブルーチンでは、逆２値変換により２値シンボル列から多値シンボルを復号するとともに、２値シンボル列の算術符号化を行う。算術符号化を行うにあたり、ステップＡ２００の初期化では確率期待値を初期値に設定しておく。【００７２】
図１０を参照して、処理部３２の符号化処理サブルーチンの動作を説明する。【００７３】
まずステップＡ２０において、逆２値化変換を行い、多値シンボルを出力するとともに、対応する２値シンボル列をシンボル列バッファに格納する。ステップＡ２１では現在のコンテクストの確率推定値を取得する。【００７４】
ステップＡ２３では、シンボル列バッファの先頭から２値シンボルを１つ取り出し、算術符号化を行って出力する。算術符号化の回数と生成したビット数とをカウントし、外部からの参照可能にしておく。【００７５】
ステップＡ２４では２値シンボルの値に応じて確率推定値を更新する。確率推定値が対称表現の場合、ＭＰＳの確率推定値が０．５未満となれば、ＭＰＳを反転する。ステップＡ２５では、シンボル列バッファが空か否かで分岐する。シンボル列バッファが空であれば終了し、そうでなければステップＡ２１に戻って算術符号化を続ける。【００７６】
処理部３１では出力した２値シンボル数が、処理部３２では算術符号化の回数と生成したビット数が分かる。メモリ上に蓄積されている２値シンボル数は、出力した２値シンボル数から算術符号化の回数を減じることで求まる。また、２値シンボル数と符号ビット数の関係は、算術符号化の回数と生成したビット数から求めることができる。これらの値から推定生成ビット数を算出することができる。推定生成ビット数は、処理部３１の出力サブルーチン内で算出して外部から参照可能にしておいてもよいし、外部で元となる値から算出してもよい。【００７７】
次に、上述した２値算術符号の復号を行う復号器および符号化器をコンピュータシステムにより実行する例を説明する。【００７８】
コンピュータシステムには、ＣＰＵが装備されており、ＣＰＵにはバッファおよびメモリが接続されている。【００７９】
メモリには、本発明における復号処理および符号化処理を実行するためのプログラムが格納されている。このプログラムをＣＰＵで実行することにより、本発明における復号処理および符号化処理が実行される。【００８０】
なお、上述した実施の形態では２値算術符号を扱う場合について説明したが、本発明は２値算術符号への適用に限られるものではない。４値の算術符号を用いる場合には、図および説明の２値を４値に読み替えるだけで、本発明の４値算術符号の復号器や符号化器を構成できる。また、２値と３値との算術符号が混在するような場合でも、コンテクストに合わせて２値算術符号の処理と３値算術符号の処理を切り替えるように構成すればよい。【００８１】
以上、映像復号器と映像符号化器を例にして、本発明の実施の形態を説明したが、本発明はこれらの適用に限られるものではない。ブロック復号器１７を音声フレーム復号器、ブロック符号化器２０を音声フレーム符号化器に置き換えれば、容易に音声復号器、音声符号化器への適用が可能である。他のメディアやデータの符号化器や復号器でも、２値化算術符号を用いるものであれば、映像や音声の場合と同様に、本発明の２値化算術符号の符号化器と復号器を適用できる。
【図１】
0004677901.tif 000002
【図２】
0004677901.tif 000003
【図３】
0004677901.tif 000004
【図４】
0004677901.tif 000005
【図５】
0004677901.tif 000006
【図６】
0004677901.tif 000007
【図７】
0004677901.tif 000008
【図８】
0004677901.tif 000009
【図９】
0004677901.tif 000010
【図１０】
0004677901.tif 000011