(57)【要約】【課題】高速に算術符号を得る。【解決手段】入力２値信号及びその発生確率の情報に対応した算術符号をその一部からなる部分算術符号と同一論理値が連続する挿入符号とに分け、前記部分算術符号及びその符号長並びに前記挿入符号の符号長に関する情報を保持するテーブルを用いて、前記入力２値信号及びその発生確率の情報から前記部分算術符号及びその符号長並びに前記挿入符号の符号長を求める算術符号テーブルブロック２１と、前記算術符号テーブルブロックからの前記部分算術符号及びその符号長並びに前記挿入符号の符号長を用いて、前記算術符号を生成する算術符号連接部２２とを具備したことを特徴とする。【選択図】図１
2009017232.tif 000002
【特許請求の範囲】
【請求項１】
入力２値信号及びその発生確率の情報に対応した算術符号をその一部からなる部分算術符号と同一論理値が連続する挿入符号とに分け、前記部分算術符号及びその符号長並びに前記挿入符号の符号長に関する情報を保持するテーブルを用いて、前記入力２値信号及びその発生確率の情報から前記部分算術符号及びその符号長並びに前記挿入符号の符号長を求める算術符号テーブルブロックと、
前記算術符号テーブルブロックからの前記部分算術符号及びその符号長並びに前記挿入符号の符号長を用いて、前記算術符号を生成する算術符号連接部とを具備したことを特徴とする算術符号化装置。
【請求項２】
前記算術符号テーブルブロックからの前記部分算術符号及びその符号長並びに前記挿入符号の符号長を保持して前記算術符号連接部に与えるメモリを具備したことを特徴とする請求項１に記載の算術符号化装置。
【請求項３】
前記算術符号テーブルブロックは、前記入力２値信号及びその発生確率に基づいて前記各入力２値信号の発生確率の存在範囲を示す区間長とその存在範囲の下限値とを求める第１の処理を具備し、
前記テーブルは、前記区間長及び下限値に対する前記部分算術符号及びその符号長並びに前記挿入符号の符号長に関する情報を保持することを特徴とする請求項１又は２のいずれか一方に記載の算術符号化装置。
【請求項４】
前記算術符号テーブルブロックは、前記第１の処理と前記部分算術符号及びその符号長並びに前記挿入符号の符号長に関する情報を得る第２の処理とを夫々１サイクルで実行し、
前記算術符号連接テーブルは、前記部分算術符号及びその符号長並びに前記挿入符号の符号長を用いて前記算術符号を生成する第３の処理を１サイクルで実行することを特徴とする請求項３に記載の算術符号化装置。
【請求項５】
請求項１に記載の算術符号化装置と、
入力画像信号を予測符号化して前記算術符号化装置に与える予測符号化手段とを具備したことを特徴とする画像符号化装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、画像信号の符号化処理に好適な算術符号化装置及び画像符号化装置に関する。
【背景技術】
【０００２】
近年、画像処理のディジタル化が普及している。ディジタル化された画像データは、符号量を削減するために、Ｈ．２６４、ＡＶＣ規格等の動画像符号化方法を採用して符号化後に伝送や記録が行われることが多い。
【０００３】
Ｈ．２６４規格等においては、エントロピー符号化として定常的な信号を理論限界まで圧縮することができる算術符号化が採用されている。ここで、定常的な信号とは、確率的な性質が変化しないような信号のことで、例えば０、１の発生確率が半々であったとしたら、最後まで半々の確率で発生するような性質をもつ信号のことである。
【０００４】
Ｈ．２６４において採用されている算術符号化方式は、圧縮率が高いＣＡＢＡＣと呼ばれる手法である。ＣＡＢＡＣ符号化では、マクロブロックの画素情報等を可変長符号化した２値信号列（ｂｉｎＶａｌ列）に対して、各２値信号（ｂｉｎＶａｌ）の発生確率を推定して算術符号化を行う。ｂｉｎＶａｌの発生確率は、その符号化の対象となるマクロブロックの周囲に隣接するマクロブロックの符号化情報を参照することで求められる。ＣＡＢＡＣ符号化は、符号化を各ｂｉｎＶａｌ１ビットずつ順番に行う必要があり、しかも各ｂｉｎＶａｌ１ビット毎の処理が複雑である。
【０００５】
即ち、ＣＡＢＡＣ符号化装置においては、２値信号列の各ｂｉｎＶａｌが“０”であるか“１”であるかの発生確率を推定し、入力された２値信号列に対して各ｂｉｎＶａｌの発生確率から２値信号列が得られる最終的な発生確率を求めて、符号化出力とするものである。各ｂｉｎＶａｌの発生確率が既知であれば、復号時において、最終的な発生確率から入力２値信号列を求めることができる。
【０００６】
このようなＣＡＢＡＣ符号化を行うためには、発生確率の最小値０と最大値１との間のいずれの位置に発生確率が存在するかを、その下限値（以下、ｃｏｄＩＬｏｗともいう）と下限値から上限値までの区間長（以下、ｃｏｄＩＲａｎｇｅともいう）とを用いて、各ｂｉｎＶａｌ毎に求めればよい。このようなＣＡＢＡＣ符号化装置については、特許文献１に開示されたものがある。
【０００７】
ところで、発生確率は０〜１の範囲であり、入力２値化信号列のビット数が増えると、区間長の桁数が増大し、レジスタに区間長を保持することができなくなってしまう。そこで、入力２値信号列の全てに対して順次求めて得た最終的な区間から出力ビットを得るのではなく、最終的な区間の位置を表す上位側のビットが確定する毎に、順次ビットを出力する処理を行う。例えば、最終的な区間が０．５〜１の範囲になることが確定した場合には、０．５を示す小数点以下第１桁目の２進数“１”を出力する。そして、０．５〜１の区間を０〜１の区間に拡大して処理を繰返す。このような再正規化処理及び出力処理によって、比較的小さい容量のレジスタを用いて算術符号化が可能である。
【０００８】
このようなＣＡＢＡＣ符号化処理は、ソフトウェア処理によって行われる。Ｈ．２６４規格においては、ＣＡＢＡＣ符号化を行うための３つの処理フロー、即ち、入力ｂｉｎｖａｌに対してｃｏｄＩＬｏｗ及びｃｏｄＩＲａｎｇｅを算出する処理であるＥｎｃｏｄｅＤｅｃｉｓｉｏｎ、再正規化処理ループであるＲｅｎｏｒｍ及び出力処理ループであるＰｕｔＢｉｔについて詳述されている。
【０００９】
ＥｎｃｏｄｅＤｅｃｉｓｉｏｎでは、各入力ｂｉｎｖａｌに対してｃｏｄＩＬｏｗ及びｃｏｄＩＲａｎｇｅを求めて、再正規化処理及び出力処理を呼び出すようになっている。これらの再正規化処理及び出力処理は、区間の位置によっては、複数回繰り返されることがある。また、再正規化処理は、出力処理を伴うこと無く複数回繰返されることがあり、この場合には、再正規化処理後において１ループで１ビットずつ出力する出力処理も再正規化処理回数だけ繰り返される。
【００１０】
ｃｏｄＩＬｏｗを１０ビットとし、ｃｏｄＩＲａｎｇｅを９ビットとすると、１ｂｉｎＶａｌに対する再正規化処理（Ｒｅｎｏｒｍ）のループは最大８回となる。また、再正規化のループ処理は次のｂｉｎｖａｌに繰り越すことができることから、所定の１ｂｉｎＶａｌに対する出力処理は、理論的には、処理が初期化されるスライスの範囲に応じた回数だけ繰返される可能性がある。
【００１１】
このように、１ビットのｂｉｎＶａｌを算術符号化するためには、多くの処理サイクル数が必要となる。Ｈ．２６４／ＡＶＣにおいて高解像度の画像を高ビットレート（例えば３０Ｍｂｐｓ）でＣＡＢＡＣ符号化する場合には、ＣＡＢＡＣ符号化装置に入力されるｂｉｎＶａｌ数は１フレームで４０〜５０Ｍｂｉｎとなり、１ｂｉｎＶａｌに多くの処理サイクル数を要する上述したフローを採用するとリアルタイム処理が困難となるという問題があった。
【特許文献１】特開２００７−７４６４８号公報
【発明の開示】
【発明が解決しようとする課題】
【００１２】
本発明は、比較的処理能力が低速であっても高速に算術符号化処理を行うことができる算術符号化装置及び画像符号化装置を提供することを目的とする。
【課題を解決するための手段】
【００１３】
本発明の一態様に係る算術符号化装置は、入力２値信号及びその発生確率の情報に対応した算術符号をその一部からなる部分算術符号と同一論理値が連続する挿入符号とに分け、前記部分算術符号及びその符号長並びに前記挿入符号の符号長に関する情報を保持するテーブルを用いて、前記入力２値信号及びその発生確率の情報から前記部分算術符号及びその符号長並びに前記挿入符号の符号長を求める算術符号テーブルブロックと、前記算術符号テーブルブロックからの前記部分算術符号及びその符号長並びに前記挿入符号の符号長を用いて、前記算術符号を生成する算術符号連接部とを具備したことを特徴とする。
【発明の効果】
【００１４】
本発明によれば、比較的処理能力が低速であっても高速に算術符号化処理を行うことができるという効果を有する。
【発明を実施するための最良の形態】
【００１５】
以下、図面を参照して本発明の実施の形態について詳細に説明する。図１は本発明の第１の実施の形態に係る算術符号化装置を示すブロック図である。また、図２は図１の算術符号化装置が組込まれた画像符号化装置を示すブロック図である。
【００１６】
上述したように、ＣＡＢＡＣ符号は、入力ｂｉｎｖａｌに対して求めたｃｏｄＩＬｏｗ及びｃｏｄＩＲａｎｇｅについて、再正規化処理（Ｒｅｎｏｒｍ）及び出力処理（ＰｕｔＢｉｔ）を実行することによって求められる。即ち、ｃｏｄＩＬｏｗ及びｃｏｄＩＲａｎｇｅに対して出力のＣＡＢＡＣ符号が一義的に決定される。そこで、ｃｏｄＩＬｏｗ及びｃｏｄＩＲａｎｇｅに対する符号化出力を記述したテーブルを用いることで、高速にＣＡＢＡＣ符号化を行うことが考えられる。
【００１７】
しかしながら、１ループで１ビットのデータが出力される出力処理は、理論的にはスライスの範囲に応じた回数だけ繰返されることがある。このため、所定のｂｉｎＶａｌに対する最初の出力処理において例えば３２ビットのビット数が発生することもあり、再正規化処理のループ数を考慮すると、１ｂｉｎＶａｌに対して例えば５０ビットの出力が発生する可能性がある。このような出力の全てを考慮したテーブルは、極めて膨大なテーブルとなり、大きなメモリ容量と大きな占有面積を必要とし、このようなテーブルを用いたＣＡＢＡＣ符号化では、１ｂｉｎＶａｌに対する処理に長時間を要してしまう。
【００１８】
そこで、本実施の形態においては、１ビットのｂｉｎＶａｌから生成される算術符号を、後述するように、挿入符号と部分算術符号とに分割し、挿入符号長に関するデータ及び部分算術符号長のデータと部分算術符号とをテーブルに保持して読み出すことにより、少ないメモリ容量のテーブルで構成可能とすると共に、高速な符号化処理を可能にしている。
【００１９】
図２において、コンテキストインデックス導出部１１には、２値信号列（ｂｉｎＶａｌ列）が入力される。このｂｉｎＶａｌ列は、例えば、Ｈ．２６４規格の量子化出力であるシンタックス要素に基づいて得られた可変長の２値のシンボル列である。コンテキストインデックス導出部１１は、２値信号（ｂｉｎＶａｌ）が入力されると、図示しないメモリに保持されている周囲のマクロブロック情報を参照してコンテキストインデックス（以下、ｃｔｘＩｄｘともいう）を算出して、ｂｉｎＶａｌ及びｃｔｘＩｄｘを出力する。
【００２０】
統計的には、ｂｉｎＶａｌは、シンタックスの種類に応じた発生確率を有する。ｂｉｎＶａｌの発生確率は、発生確率が高いシンボル（以下、ＭＰＳ：Ｍｏｓｔ  Ｐｒｏｂａｂｌｅ  Ｓｙｍｂｏｌともいう）とその発生確率テーブルの番号である確率状態インデックス（以下、ｐＳｔａｔｅＩｄｘともいう）とによって指定することができる。確率状態導出部１２は、図示しないメモリに、発生確率が高いシンボルの値（ｖａｌＭＰＳ）とｐＳｔａｔｅＩｄｘとを保持する。
【００２１】
ｐＳｔａｔｅＩｄｘはシンタックスの種類に応じた領域を有し、この領域はコンテキストインデックスによって指定することができる。確率状態導出部１２は、ｂｉｎＶａｌ及びｃｔｘＩｄｘを用いて、ｐＳｔａｔｅＩｄｘ及びｖａｌＭＰＳ（高発生確率シンボルの値）を読み出す。確率状態導出部１２はｂｉｎＶａｌ、ｐＳｔａｔｅＩｄｘ及びｖａｌＭＰＳを算術符号化部１４に出力するようになっている。
【００２２】
算術符号化部１４は、ｂｉｎＶａｌ、ｐＳｔａｔｅＩｄｘ及びｖａｌＭＰＳが入力されると、これらを用いて算術符号を生成して出力する。確率状態更新部１３は、算術符号化部１４によって生成された算術符号が入力され、確率状態導出部１２から入力されたｂｉｎＶａｌ、ｐＳｔａｔｅＩｄｘ、ｖａｌＭＰＳを、生成された算術符号に基づいて更新して、更新したｐＳｔａｔｅＩｄｘ及びｖａｌＭＰＳを確率状態導出部１２に戻して、記憶させるようになっている。
【００２３】
図１は算術符号化部１４の具体的な構成を示している。先ず、算術符号化部１４について説明する前に、図３乃至図７を参照して、Ｈ．２６４規格において規定されたＣＡＢＡＣ符号化の３つの処理フロー及び出力ビットについて説明する。図３乃至図５は夫々ＣＡＢＡＣ符号化におけるＥｎｃｏｄｅＤｅｃｉｓｉｏｎ処理フロー、再正規化（Ｒｅｎｏｒｍ）処理フロー及び出力（Ｐｕｔｂｉｔ）処理フロー（Ｈ.２６４/ＡＶＣ規格書のＦｉｇ９-７,９-８,９-９）を示している。また、図６はｃｏｄＩＲａｎｇｅ及びｃｏｄＩＬｏｗを説明するための説明図である。
【００２４】
＜ＥｎｃｏｄｅＤｅｃｉｓｉｏｎ＞
上述したように、算術符号は、ｃｏｄＩＲａｎｇｅ、ｃｏｄＩＬｏｗを用いたループ処理によって求められる。ＥｎｃｏｄｅＤｅｃｉｓｉｏｎにおいては、入力ｂｉｎＶａｌ毎にｃｏｄＩＲａｎｇｅ、ｃｏｄＩＬｏｗを求める。図６は、縦軸がｂｉｎＶａｌの発生確率に対応しており、連続して入力された２つのｂｉｎＶａｌによる発生確率の変化を示している。図６は、ＭＰＳのｂｉｎＶａｌに続いて発生確率が低いシンボル（以下、ＬＰＳ：Ｌｅａｓｔ  Ｐｒｏｂａｂｌｅ  Ｓｙｍｂｏｌともいう）のｂｉｎＶａｌが入力された例を示しており、斜線によってｃｏｄＩＲａｎｇｅの変化を示している。なお、図６の左側のｂｉｎＶａｌ入力によるｃｏｄＩＬｏｗは０．０であるものとする。
【００２５】
図６の右側のＬＰＳについてのｂｉｎＶａｌ及びｐＳｔａｔｅＩｄｘが入力されると、図３のステップＳ１においては、先ず、１つ前のＥｎｃｏｄｅＤｅｃｉｓｉｏｎにおいて正規化されたｃｏｄＩＲａｎｇｅを用いて、ｑＣｏｄＩＲａｎｇｅＩｄｘを求める。次に、入力されたｐＳｔａｔｅＩｄｘとｑｃｏｄＩＲａｎｇｅＩｄｘとを用いて、確率と区間長とに基づくテーブルから、ＬＰＳによる区間長（以下、ｃｏｄＩＲａｎｇｅＬＰＳともいう）を求める。
【００２６】
なお、ＭＰＳのｂｉｎＶａｌが入力された場合には、区間長（ｃｏｄＩＲａｎｇｅ）は、図６に示すように、前のｃｏｄＩＲａｎｇｅからｃｏｄＩＲａｎｇｅＬＰＳを減算することによって求められる（ステップＳ１）。
【００２７】
ステップＳ２では、ｂｉｎＶａｌがＭＰＳでないか否かが判定される。ＬＰＳである場合には、処理をステップＳ３に移行して、ｃｏｄＩＬｏｗ及びｃｏｄＩＲａｎｇｅが求められる。ｃｏｄＩＬｏｗは図６から明らかなように、元のｃｏｄＩＬｏｗとＭＰＳ時のｃｏｄＩＲａｎｇｅとの和で求められる。また、ｃｏｄＩＲａｎｇｅはｃｏｄＩＲａｎｇｅＬＰＳである。なお、ｂｉｎＶａｌがＭＰＳの場合には、ステップＳ１で求めたｃｏｄＩＲａｎｇｅをそのまま用いることができ、ｃｏｄＩＬｏｗは前ｂｉｎＶａｌ入力時から変化しておらず同じである。
【００２８】
次のステップＳ４では、ｐＳｔａｔｅＩｄｘが０であるか否かが判定される。 ｐＳｔａｔｅＩｄｘが０の場合には、ステップＳ５においてＭＰＳとＬＰＳを反転させ、ステップＳ６において、ｐＳｔａｔｅＩｄｘをＬＰＳ時のテーブルに基づいて更新する。なお、ステップＳ２で、入力ｂｉｎＶａｌがＭＰＳと判定された場合には、ステップＳ７において、ｐＳｔａｔｅＩｄｘをＭＰＳ時のテーブルに基づいて更新する。なお、ステップＳ６，Ｓ７の処理は、上述したように、確率状態更新部１３において行われる。
【００２９】
次のステップＳ８において、再正規化（Ｒｅｎｏｒｍ）処理が行われ、ステップＳ９において変数ｓｙｍＣｎｔをインクリメントする。
【００３０】
＜Ｒｅｎｏｒｍ＞
再正規化処理においては、算出されたｃｏｄＩＲａｎｇｅ、ｃｏｄＩＬｏｗを用いて算術符号を求める。図４に示すように、先ず、ｃｏｄＩＲａｎｇｅが０ｘ１００よりも小さいか否かが判定される（ステップＳ１１）。ｃｏｄＩＲａｎｇｅの初期値（最大値）は、０ｘ１ＦＥであり、ステップＳ１１ではｃｏｄＩＲａｎｇｅがｃｏｄＩＲａｎｇｅの最大値の１／２よりも小さいか否かが判定される。小さい場合には、再正規化処理が可能であり、処理をステップＳ１２に移行する。ｃｏｄＩＲａｎｇｅがｃｏｄＩＲａｎｇｅの最大値の１／２よりも大きい場合には、再正規化処理は不能であり、処理をＥｎｃｏｄｅＤｅｃｉｓｉｏｎに戻す。
【００３１】
次のステップＳ１２においては、ｃｏｄＩＬｏｗが０ｘ１００よりも小さいか否かが判定される。ｃｏｄＩＬｏｗが０ｘ１００よりも小さい場合には、処理をステップＳ１３に移行してＰｕｔＢｉｔ処理（ＰｕｔＢｉｔ（０））が行われる。ステップＳ１３のＰｕｔＢｉｔ（０）では図５のＢとして“０”が設定される。
【００３２】
一方、ステップＳ１２において、ｃｏｄＩＬｏｗが０ｘ１００以上の場合には、処理がステップＳ１４に移行する。ステップＳ１４では、ｃｏｄＩＬｏｗが０ｘ２００以上であるか否かが判定される。ｃｏｄＩＬｏｗが０ｘ２００以上である場合には、処理をステップＳ１５に移行してｃｏｄＩＬｏｗを０ｘ２００だけ小さな値としてＰｕｔＢｉｔ処理（ＰｕｔＢｉｔ（１））を行う（ステップＳ１６）。なお、この場合のＰｕｔＢｉｔ（１）は、図５のＢとして“１”が設定される。ｃｏｄＩＬｏｗが０ｘ２００よりも小さい場合には、処理をステップＳ１７に移行してｃｏｄＩＬｏｗを０ｘ１００だけ小さな値とし、変数ｂｉｔｓＯｕｔｓｔａｎｄｉｎｇをインクリメントする。なお、ｂｉｔｓＯｕｔｓｔａｎｄｉｎｇの初期値は０である。
【００３３】
ステップＳ１８においては、ｃｏｄＩＲａｎｇｅ及びｃｏｄＩＬｏｗを上位ビット側に１ビットシフトする。即ち、ｃｏｄＩＲａｎｇｅ，ｃｏｄＩＬｏｗを２倍する再正規化を行う。
【００３４】
＜ＰｕｔＢｉｔ＞
出力処理においては、ステップＳ２１において、ｆｉｒｓｔＢｉｔＦｌａｇが０でないか否かが判定される。ｆｉｒｓｔＢｉｔＦｌａｇは初期値が１であり、初期状態では処理がステップＳ２２に移行して、ｆｉｒｓｔＢｉｔＦｌａｇに０がセットされる。初期状態以外では、処理がステップＳ２３に移行して、１ビットのＢが出力される。即ち、図４のステップＳ１３のＰｕｔＢｉｔ（０）では“０”が出力され、ステップＳ１６のＰｕｔＢｉｔ（１）では“１”が出力される。
【００３５】
次のステップＳ２４では、ｂｉｔｓＯｕｔｓｔａｎｄｉｎｇが０よりも大きいか否かが判定される。図４のステップＳ１７の処理が１回以上行われている場合には、ｂｉｔｓＯｕｔｓｔａｎｄｉｎｇは１以上であり、次のステップＳ２５において、１−Ｂを１ビット出力する。即ち、ＰｕｔＢｉｔ（０）では“１”が出力され、ＰｕｔＢｉｔ（１）では“０”が出力される。次のステップＳ２６では、ｂｉｔｓＯｕｔｓｔａｎｄｉｎｇが１減算される。
【００３６】
即ち、ｆｉｒｓｔＢｉｔＦｌａｇが１の初期状態以外では、ＰｕｔＢｉｔ処理においては、先ず、Ｂが１ビット出力され、次にｂｉｔｓＯｕｔｓｔａｎｄｉｎｇの数のビット数だけ、Ｂの反転ビットが出力されることになる。
【００３７】
図７は図３乃至図５のフローに基づく算術符号化の処理サイクルを示す説明図である。
【００３８】
図７は一連のｂｉｎＶａｌ列のうちの所定の連続した３つのｂｉｎＶａｌ  ｍ〜ｍ＋２に対する算術符号化処理を示している。図７の塗り潰しはｂｉｎＶａｌの入力からＥｎｃｏｄｅＤｅｃｉｓｉｏｎまでの処理を示している。各ｂｉｎＶａｌ入力後の最初の１サイクルで、図３のＥｎｃｏｄｅＤｅｃｉｓｉｏｎが実施されて、ｃｏｄＩＲａｎｇｅ及びｃｏｄＩＬｏｗが決定される。図７の斜線で囲った１つの枠は、図４のＲｅｎｏｒｍ処理の１ループを示している。また、白地の枠はＰｕｔＢｉｔ処理の１ループを示しており、数字によって出力ビットが“０”であるか“１”であるかを示している。１ｂｉｎＶａｌに対するｒｅｎｏｒｍ処理の最大回数は８回であり、図７の例ではｂｉｎＶａｌ  ｍに対して最大回数のｒｅｎｏｒｍが実施されたことを示している。なお、図７はｆｉｒｓｔＢｉｔＦｌａｇが初期状態でない例である。
【００３９】
ｂｉｎＶａｌ  ｍ＋１の入力時には、４回のｒｅｎｏｒｍ処理が行われている。１〜３回目のｒｅｎｏｒｍ処理は、出力ビットが発生していないことから、図４のステップＳ１７においてｂｉｔｓＯｕｔｓｔａｎｄｉｎｇがインクリメントされたことを示している。ｂｉｎＶａｌ  ｍ＋１の入力時の４回目のｒｅｎｏｒｍ処理は、次にｒｅｎｏｒｍ処理が行われていないので、ステップＳ１１の判定からＥｎｃｏｄｅＤｅｃｉｓｉｏｎに処理を戻したことを示している。従って、ｂｉｎＶａｌ  ｍ＋２の入力時点において、ｂｉｔｓＯｕｔｓｔａｎｄｉｎｇは３となっている。
【００４０】
ｂｉｎＶａｌ  ｍ＋２入力時の１回目のｒｅｎｏｒｍ処理において、出力処理が行われている。即ち、この１回目のｒｅｎｏｒｍ処理によって、図４のステップＳ１３のＰｕｔＢｉｔ（０）がコールされ、図５のステップＳ２３において“０”が１ビット出力され、次いでステップＳ２５において、“０”がｂｉｔｓＯｕｔｓｔａｎｄｉｎｇ数（この場合には上述したように３）のビット数だけ出力される。
【００４１】
また、ｂｉｎＶａｌ  ｍ入力時には、２回目のｒｅｎｏｒｍ処理において、ＰｕｔＢｉｔ（１）が発生したことを示している。このＰｕｔＢｉｔ処理において“０”が５ビット出力されていることから、この２回目のｒｅｎｏｒｍ処理の前までのｒｅｎｏｒｍ処理において、ｂｉｔｓＯｕｔｓｔａｎｄｉｎｇが５になっていることが分かる。
【００４２】
図７の例では、ｂｉｎＶａｌ  ｍの入力に対して、２０サイクルで１１ビットが出力され、次のｂｉｎＶａｌ  ｍ＋１の入力に対して、５サイクルで処理が行われ、次のｂｉｎＶａｌ  ｍ＋２の入力に対して、８サイクルで４ビットが出力されている。上述したように、ｒｅｎｏｒｍ処理はスライス単位で初期化されることから、ｂｉｔｓＯｕｔｓｔａｎｄｉｎｇによる出力ビット数は３２ビット程度になることもある。
【００４３】
即ち、各ｂｉｎＶａｌ入力に対して、出力ビット数が大きくなり、出力に要するサイクル数が大きくなるのは、前ｂｉｎＶａｌ入力に対する処理で発生したｂｉｔｓＯｕｔｓｔａｎｄｉｎｇが順次繰り越されたことによる影響が大きい。そこで、本実施の形態においては、このように繰り越されたｂｉｔｓＯｕｔｓｔａｎｄｉｎｇによる最初の出力処理時には、１ビットのビットＢに続けてｂｉｔｓＯｕｔｓｔａｎｄｉｎｇ数だけビットＢの反転ビットが出力されることを利用して、そのｂｉｔｓＯｕｔｓｔａｎｄｉｎｇ数を挿入符号長として求めるようになっている。
【００４４】
図８は本実施の形態における算術符号化の方法を説明するための説明図である。本実施の形態においては、少なくとも図４及び図５のｒｅｎｏｒｍ処理及びＰｕｔＢｉｔ処理は採用しない。
【００４５】
図８の上欄は上述した図３乃至図５のフローにより得られる算術符号の一例を示している。図８の例は１ビットのｂｉｎＶａｌ入力に対する算術符号を示している。
【００４６】
図８の例では、入力ｂｉｎＶａｌ入力に対して、“１０００００００１０１０００”が得られるものとしている。本実施の形態においては、各ｂｉｎＶａｌ入力に対する最初の出力ビットＢに続く、ｂｉｔｓＯｕｔｓｔａｎｄｉｎｇによる反転ビット（以下、挿入符号ともいう）の数を挿入符号長とする。図８の例では、挿入符号長は６である。そして、出力すべき算術符号から挿入符号を除く符号を部分算術符号とする。図８の例では部分算術符号は、“１０１０１０００”である。また、部分算術符号のビット数を部分算術符号長とする。図８の例では部分算術符号長は８である。
【００４７】
本実施の形態においては、算術符号化部１４は算術テーブルブロック２１を有しており、算術テーブルブロック２１は、入力されたｂｉｎＶａｌに対して挿入符号長、部分算術符号及び部分算出符号長を求めるようになっている。
【００４８】
図９は図１中の算術テーブルブロック２１の具体的な構成を示すブロック図である。
【００４９】
確率状態導出部１２からのｐＳｔａｔｅＩｄｘは、算術テーブルブロック２１内のｃｏｄＩＲａｎｇｅ計算部３０に与えられる。また、確率状態導出部１２からのｂｉｎＶａｌ及びｖａｌＭＰＳは、算術テーブルブロック２１内のｃｏｄＩＲａｎｇｅ計算部３０及びｃｏｄＩＬｏｗ計算部３１の両方に与えられる。ｃｏｄＩＲａｎｇｅ計算部３０及びｃｏｄＩＬｏｗ計算部３１は、ｃｏｄＩＲａｎｇｅ及びｃｏｄＩＬｏｗを算出して、夫々ｃｏｄＩＲａｎｇｅ更新テーブル３２及びｃｏｄＩＬｏｗ更新テーブル３３に与える。ｃｏｄＩＲａｎｇｅ更新テーブル３２及びｃｏｄＩＬｏｗ更新テーブル３３は、更新されたｃｏｄＩＲａｎｇｅ及びｃｏｄＩＬｏｗを保持し、次回のｂｉｎＶａｌ入力時のｃｏｄＩＲａｎｇｅ，ｃｏｄＩＬｏｗの算出に用いるために、夫々バッファ３４，３５に出力する。
【００５０】
ｃｏｄＩＲａｎｇｅ計算部３０及びｃｏｄＩＬｏｗ計算部３１には、バッファ３４，３５から前ｂｉｎＶａｌ入力時に求めたｃｏｄＩＲａｎｇｅ及びｃｏｄＩＬｏｗも与えられる。ｃｏｄＩＲａｎｇｅ計算部３０及びｃｏｄＩＬｏｗ計算部３１は、図３と同様のフローによって、入力されたｐＳｔａｔｅＩｄｘ、ｂｉｎＶａｌ及びｖａｌＭＰＳを用いて、新たなｃｏｄＩＲａｎｇｅ及びｃｏｄＩＬｏｗを算出する。
【００５１】
なお、ｃｏｄＩＲａｎｇｅ計算部３０及びｃｏｄＩＬｏｗ計算部３１は、図３のフローと同様の手法によってｃｏｄＩＲａｎｇｅ及びｃｏｄＩＬｏｗを求めればよく、図３の処理をソフトウェアによって実行するマイクロコンピュータによって構成することができる。
【００５２】
ｃｏｄＩＲａｎｇｅ計算部３０及びｃｏｄＩＬｏｗ計算部３１からのｃｏｄＩＲａｎｇｅ及びｃｏｄＩＬｏｗは、部分算術符号テーブル３６，部分算術符号長テーブル３７及び挿入符号長計算部３８に与えられる。上述したように、ｃｏｄＩＲａｎｇｅ及びｃｏｄＩＬｏｗに対して算術符号は一義的に決定される。また、算術符号に対して、図８に示すように、部分算術符号、部分算術符号長及び挿入符号長も一義的に決定される。部分算術符号テーブル３６はこのような部分算術符号を格納し、部分算術符号長テーブル３７は部分算術符号長を格納している。また、挿入符号長計算部３８は挿入符号長テーブル３９を有しており、挿入符号長テーブル３９は、ｂｉｔｓＯｕｔｓｔａｎｄｉｎｇ数を格納している。
【００５３】
ＣＡＢＡＣ符号化においては、部分算術符号長の最大値は例えば８である。従って、部分算術符号テーブル３６としては８ビットの出力が得られるものを採用すればよい。また、部分算術符号長を保持する部分算術符号長テーブル３７としては、３ビット又は４ビット程度の出力が得られるものを採用すればよい。また、ＣＡＢＡＣ符号化においては、挿入符号長のビット数は例えば１９ビットであり、挿入符号長テーブル３９としては、１９ビットの出力が得られるものを採用すればよい。
【００５４】
部分算術符号テーブル３６は、入力されたｃｏｄＩＲａｎｇｅ及びｃｏｄＩＬｏｗに対応する部分算術符号を出力する。部分算術符号長テーブル３７は、入力されたｃｏｄＩＲａｎｇｅ及びｃｏｄＩＬｏｗに対応する部分算術符号長を出力する。
【００５５】
また、挿入符号長計算部３８は、入力されたｃｏｄＩＲａｎｇｅ及びｃｏｄＩＬｏｗに対応するｂｉｔｓＯｕｔｓｔａｎｄｉｎｇ数を挿入符号長テーブル３９から読み出す。挿入符号長は、各ｂｉｎＶａｌ入力に対する最初の出力処理時のｂｉｔｓＯｕｔｓｔａｎｄｉｎｇ数である。挿入符号長計算部３８は、各ｂｉｎＶａｌ入力に対する処理終了時点のｂｉｔｓＯｕｔｓｔａｎｄｉｎｇ数を繰り越し挿入符号長としてバッファ４０に出力する。挿入符号長計算部３８はバッファ４０から繰り越し挿入符号長を読み出し、各ｂｉｎＶａｌ入力に対する最初の出力処理時に挿入符号長テーブル３９から読み出したｂｉｔｓＯｕｔｓｔａｎｄｉｎｇ数と繰り越し挿入符号長とを加算して、挿入符号長として出力する。
【００５６】
部分算術符号テーブル３６、部分算術符号長テーブル３７及び挿入符号長計算部３８は、各テーブル３６，３７，３９の出力ビット数が比較的少ないので、高速に、部分算術符号、部分算術符号長及び挿入符号長を出力することができる。また、各テーブル３６，３７，３９を比較的小さい容量で構成することができ、占有面積も小さい。
【００５７】
算術テーブルブロック２１からの部分算術符号、部分算術符号長及び挿入符号長は、算術符号連接部２２に与えられる。算術符号連接部２２は入力された部分算術符号、部分算術符号長及び挿入符号長から算術符号を生成して出力する。
【００５８】
図１０は算術符号連接部２２の具体的な構成を示すブロック図である。
【００５９】
算術テーブルブロック２１からの部分算術符号長は算術符号連接部２２の部分算術符号シフト部４１に与えられ、部分算術符号及び挿入符号長は、部分算術符号シフト部４１及び挿入符号生成部４２の両方に与えられる。部分算術符号シフト部４１は、入力された算術符号の後方の（部分算術符号長−１）ビットを挿入符号長だけ後方側にシフトして、部分算術符号長＋挿入符号長のビット数の符号を符号生成部４３に出力する。即ち、部分算術符号シフト部４１の出力は、２ビット目から挿入符号長だけ不定ビットとなる。
【００６０】
挿入符号生成部４２は、部分算術符号の先頭ビットの反転ビットを挿入符号長のビット数生成する。挿入符号生成部４２の出力は挿入符号として符号生成部４３に与えられる。符号生成部４３は、部分算術符号シフト部４１の出力の不定ビットを挿入符号に置き換えて算術符号を生成するようになっている。
【００６１】
なお、算術符号連接部２２は、例えば、上述した不定ビットを全て“０” にし、符号生成部４３において、部分算術符号シフト部４１の出力と挿入符号とのＯＲ演算によって、算術符号を生成してもよい。
【００６２】
次に、このように構成された実施の形態の動作について図１１のタイミングチャートを参照して説明する。図１１は一連のｂｉｎＶａｌ列のうち図７と同一の算術符号に変換される連続した３つのｂｉｎＶａｌ  ｍ〜ｍ＋２に対する算術符号化処理を示している。図１１の塗り潰しはｂｉｎＶａｌ入力からＥｎｃｏｄｅＤｅｃｉｓｉｏｎまでの処理を示し、斜線は部分算術符号等の生成処理を示し、無地の枠は符号連接処理を示している。
【００６３】
図２のコンテキストインデックス導出部１１にｂｉｎＶａｌ  ｍが入力されると、コンテキストインデックス導出部１１はｂｉｎＶａｌ  ｍに対応したｃｔｘＩｄｘを導出する。確率状態導出部１２は、ｃｔｘＩｄｘを用いてｂｉｎＶａｌ  ｍに対するｐＳｔａｔｅＩｄｘ及びｖａｌＭＰＳを導出して、算術符号化部１４に供給する。算術符号化部１４は、算術テーブルブロック２１内のｃｏｄＩＲａｎｇｅ計算部３０及びｃｏｄＩＬｏｗ計算部３１において、ｃｏｄＩＲａｎｇｅ及びｃｏｄＩＬｏｗを算出する。
【００６４】
ｂｉｎＶａｌ  ｍの入力からｂｉｎＶａｌ  ｍに対するｃｏｄＩＲａｎｇｅ及びｃｏｄＩＬｏｗの導出までの処理（ＥｎｃｏｄｅＤｅｃｉｓｉｏｎまでの処理）が、図１１に示す塗り潰し期間に行われる。図１１に示すように、ｂｉｎＶａｌ  ｍの入力からＥｎｃｏｄｅＤｅｃｉｓｉｏｎまでの処理に要する時間は、１サイクル期間である。
【００６５】
次の１サイクル期間には、図１１に示すように、部分算術符号、部分算術符号長及び挿入符号長が求められる。部分算術符号、部分算術符号長及びｂｉｔｓＯｕｔｓｔａｎｄｉｎｇ数は、テーブル３６，３７，３９から求めることができ、挿入符号長はｂｉｔｓＯｕｔｓｔａｎｄｉｎｇ数から簡単に求めることができる。テーブル３６，３７，３９の出力ビット数は十分に小さく、部分算術符号、部分算術符号長及び挿入符号長の算出は、例えば１サイクル等の極めて短時間に行うことができる。
【００６６】
図７の例に対応させると、ｂｉｎＶａｌ  ｍに対する２サイクル目の処理によって、部分算術符号テーブル３６から部分算術符号として、“１０１１００”が出力され、部分算術符号長テーブル３７から部分算術符号長として６が出力され、挿入符号長算出部３から挿入符号長として５が出力される。
【００６７】
これらの部分算術符号、部分算術符号長及び挿入符号長は、次の３サイクル目において算術符号連接部２２に供給されて、算術符号が得られる。即ち、算術符号連接部２２の部分算術符号シフト部４１は、部分算術符号の２ビット目以降のビットを挿入符号長だけシフトする。これにより、“１×××××０１１００”が得られる。なお、×は不定ビットを表す。また、算術符号連接部２２の挿入符号生成部４２は、部分算術符号の先頭ビットの反転ビットを挿入符号長だけ配列した挿入符号“０００００”を出力する。符号生成部４３は、入力された不定ビットを挿入符号に置き換えて、“１００００００１１００”の算術符号を出力する。算術符号連接部２２におけるこれらの処理は１サイクルで行われる。
【００６８】
こうして、本実施の形態においては、ｂｉｎＶａｌ  ｍについての算術符号化処理は３サイクルで行われる。同様に、各ｂｉｎＶａｌについても、ｂｉｎＶａｌ入力から算術符号出力までは、夫々３サイクルで実行される。なお、ｂｉｎＶａｌ  ｍ＋１の入力時においては出力ビットは発生しない。また、入力からＥｎｃｏｄｅＤｅｃｉｓｉｏｎまでの処理、部分算術符号等の生成処理及び符号連接処理は、相互に独立して行うことができるので、図１１に示すように、これらの処理を並行して実行することにより、３サイクル目以降については毎サイクル、各ｂｉｎＶａｌ入力に対する算術符号を出力することができる。
【００６９】
このように本実施の形態においては、ｃｏｄＩＲａｎｇｅ及びｃｏｄＩＬｏｗに基づいて得られる算術符号を、部分算術符号と挿入符号とに分けてテーブルを用いて算術符号を求める。この場合において、挿入符号についてはその符号長に関連するｂｉｔｓＯｕｔｓｔａｎｄｉｎｇ数をテーブルに格納する。これにより、算術符号への変換に必要な部分算術符号、部分算術符号長及び挿入符号長のビット数を十分に低減して、これらのデータを保持するテーブルからのデータの読出しを高速にしている。これにより、ｂｉｎＶａｌから算術符号への変換を極めて高速に行うことができる。
【００７０】
例えば、クロック周波数が２６６ＭＨｚ、ゲート長６５ｎｍのＡＳＩＣ（Application Specific Integrated Circuit）を用いると、１サイクル／１ｂｉｎＶａｌのスループットでの算術符号化が可能である。
【００７１】
図１２は本発明の第２の実施の形態を示すブロック図である。図１２において図１と同一の構成要素には同一符号を付して説明を省略する。
【００７２】
本実施の形態は算術符号化部１４に代えて算術符号化部５１を採用した点が第１の実施の形態と異なる。算術符号化部５１は、算術テーブルブロック２１と算術符号連接部２２との間にＦＩＦＯ２３を設けた点が算術符号化部１４と異なる。ＦＩＦＯ２３は、算術テーブルブロック２１から出力される部分算術符号、部分算術符号長及び挿入符号長を保持し、入力順に算術符号連接部２２に順次出力するようになっている。
【００７３】
次に、このように構成された実施の形態の動作について図１３及び図１４のタイミングチャートを参照して説明する。
【００７４】
図１１の例では、ｂｉｎＶａｌ  ｍ入力に対する処理において、１１ビットの算術符号が出力される。しかし、算術符号の出力にはビット幅の制限がある場合がある。この場合には、１サイクルにおいて制限されたビット幅しか出力することはできない。図１３は、第１の実施の形態において、算術符号の出力にビット幅の制限がある場合の処理サイクルを示すタイミングチャートである。図１２の例はビット幅の制限が８ビットの例を示している。図１３の３番目のサイクルにおいては、出力する算術符号の“１００００００１１００”のうち、先頭８ビットの“１００００００１”のみが出力され、次の４番目のサイクルにおいて残りの３ビットの“１００”が出力される。
【００７５】
即ち、この場合に、１ｂｉｎＶａｌ入力に対して出力に２サイクルを要する。このため、次のｂｉｎＶａｌ  ｍ＋１の入力に対する部分算術符号等の生成処理に、１サイクル分のストールが生じている。
【００７６】
本実施の形態においては、算術テーブルブロック２１からの部分算術符号、部分算術符号長及び挿入符号長は、ＦＩＦＯ２３に蓄えられながら、入力順に順次算術符号連接部２２に与えられる。図１４の２サイクル目のｂｉｎＶａｌ  ｍに対する部分算術符号等の生成処理によって生成された部分算術符号、部分算術符号長及び挿入符号長は、ＦＩＦＯ２３を介して算術符号連接部２２に与えられる。ＦＩＦＯ２３は算術符号連接部２２において連接処理される算術符号のビット数がビット幅の制限よりも大きい場合には、制限を超えたビット数については、次のサイクルまで保持して算術符号連接部２２に出力する。
【００７７】
これにより、ｂｉｎＶａｌ入力からＥｎｃｏｄｅＤｅｃｉｓｉｏｎまでの処理、部分算術符号生成処理及び符号連接処理の間にストールが生じることなく、１ｂｉｎＶａｌに対する出力を毎サイクル連続的に出力することができる。
【００７８】
このように本実施の形態においては、第１の実施の形態と同様の効果が得られると共に、出力ビット幅が制限される場合においても、ＦＩＦＯによって算術符号の発生と出力の差を吸収することで、、ストールの発生を低減させてスループットを向上させることができる。
【図面の簡単な説明】
【００７９】
【図１】本発明の第１の実施の形態に係る算術符号化装置を示すブロック図。
【図２】図１の算術符号化装置が組込まれた画像符号化装置を示すブロック図。
【図３】ＣＡＢＡＣ符号化におけるＥｎｃｏｄｅＤｅｃｉｓｉｏｎ処理フローを示すフローチャート。
【図４】ＣＡＢＡＣ符号化における再正規化（Ｒｅｎｏｒｍ）処理フローを示すフローチャート。
【図５】ＣＡＢＡＣ符号化における出力（Ｐｕｔｂｉｔ）処理フローを示すフローチャート。
【図６】図６はｃｏｄＩＲａｎｇｅ及びｃｏｄＩＬｏｗを説明するための説明図。
【図７】図３乃至図５のフローに基づく算術符号化の処理サイクルを示す説明図。
【図８】第１の実施の形態における算術符号化の方法を説明するための説明図。
【図９】図１中の算術テーブルブロック２１の具体的な構成を示すブロック図。
【図１０】算術符号連接部２２の具体的な構成を示すブロック図。
【図１１】第１の実施の形態の動作を説明するためのタイミングチャート。
【図１２】本発明の第２の実施の形態を示すブロック図。
【図１３】第２の実施の形態の動作を説明するためのタイミングチャート。
【図１４】第２の実施の形態の動作を説明するためのタイミングチャート。
【符号の説明】
【００８０】
１１…コンテキストインデックス導出部、１２…確率状態導出部、１３…確率状態更新部、１４…算術符号化部、２１…算術テーブルブロック、２２…算術符号連接部。
【図１】
2009017232.tif 000003
【図２】
2009017232.tif 000004
【図３】
2009017232.tif 000005
【図４】
2009017232.tif 000006
【図５】
2009017232.tif 000007
【図６】
2009017232.tif 000008
【図７】
2009017232.tif 000009
【図８】
2009017232.tif 000010
【図９】
2009017232.tif 000011
【図１０】
2009017232.tif 000012
【図１１】
2009017232.tif 000013
【図１２】
2009017232.tif 000014
【図１３】
2009017232.tif 000015
【図１４】
2009017232.tif 000016