(57)【特許請求の範囲】
【請求項１】
２値で表現されたバイナリデータと、当該バイナリデータにおいて発生頻度の低い劣勢シンボルの発生確率を示すシンボル比率と、当該バイナリデータにおいて発生頻度の高い優勢シンボルとを入力し、２値算術符号化を行う符号化区間幅と、当該符号化区間幅において発生頻度の低い劣勢シンボルが発生する劣勢確率の区間幅とを更新して前記バイナリデータの各ビットを符号化する２値算術符号化装置において、
符号化の対象となる対象ビットが前記優勢シンボルに一致するか否かの判定結果に基づいて、前記符号化区間幅と前記劣勢確率の区間幅とを仮に更新した仮符号化区間幅と仮劣勢確率の区間幅とを算出し、当該仮劣勢確率の区間幅と２値算術符号化で定める最大の符号化区間幅に対する所定の割合との比較の結果に応じて前記２値又は不確定値の３値のうちいずれかをビットとして出力すると共に当該仮劣勢確率の区間幅を更に更新するビット出力処理と、当該更に更新された仮劣勢確率の区間幅と前記２値算術符号化で定める最大の符号化区間幅に対する所定の割合との比較の結果に応じて行う前記ビット出力処理とを一定の回数繰り返し行うことで得られた複数のビットを出力順に並べた３値データ列を生成すると共に、当該３値データ列を構成する複数のビットの第１の有効範囲値を出力する２値算術再正規化手段と、
前記３値データ列と前記第１の有効範囲値とを格納する３値データ格納手段と、
前記３値データ列と前記第１の有効範囲値とを前記３値データ格納手段から読み出して、当該３値データ列の各ビットが前記２値のうちいずれかに一致するか否かの確認結果に基づいて、当該３値データ列を前記２値のうちいずれかをビットとする２値データ列に変換すると共に、当該２値データ列に変換できないビットの総数を未処理データ数として算出し、前記第１の有効範囲値から当該未処理データ数を引くことで得られる当該２値データ列におけるビットの第２の有効範囲値を算出する２値変換手段と、
前記２値データ列と前記第２の有効範囲値と前記未処理データ数とを格納する２値データ格納手段と、
前記２値データ列と前記第２の有効範囲値と前記未処理データ数とを前記２値データ格納手段から読み出して、当該第２の有効範囲値がゼロの場合に、前記対象ビットに対する符号化ビット列は出力しないと共に予め保持していた未処理データ数に読み出した前記未処理データ数を加算し、当該第２の有効範囲値がゼロよりも大きい場合には未処理データ数が予め保持されているか否かを判断し、保持されている場合には、前記２値データ列の先頭ビットの次に当該先頭ビットの反転値を当該予め保持されていた未処理データ数分挿入した符号化ビット列を出力すると共に予め保持されていた未処理データ数に読み出した前記未処理データ数を上書きし、保持されていない場合には、前記２値データ列を符号化ビット列として出力すると共に読み出した前記未処理データ数を保持するｆ値滞留処理手段と、
を有することを特徴とする２値算術符号化装置。
【請求項２】
前記２値算術再正規化手段は、
前記対象ビットが前記優勢シンボルに一致する場合に、前記劣勢確率の区間幅を前記仮劣勢確率の区間幅、前記符号化区間幅から前記シンボル比率を減算した値を前記仮符号化区間幅とし、前記対象ビットが前記優勢シンボルに一致しない場合に、前記符号化区間幅に前記劣勢確率の区間幅から前記シンボル比率を減算した値を加算した値を前記仮劣勢確率の区間幅、前記シンボル比率を前記仮符号化区間幅とすることを特徴とする請求項１に記載の２値算術符号化装置。
【請求項３】
前記ビット出力処理は、
前記仮劣勢確率の区間幅が前記２値算術符号化で定める最大の符号化区間幅の１／４よりも小さい場合に、前記２値のうち一方をビットとして出力すると共に、当該仮劣勢確率の区間幅を１ビット左シフトし、
前記仮劣勢確率の区間幅が前記２値算術符号化で定める最大の符号化区間幅の１／４以上の場合に、前記仮劣勢確率の区間幅と２値算術符号化で定める最大の符号化区間幅の１／２とを比較し、当該仮劣勢確率の区間幅が当該２値算術符号化で定める最大の符号化区間幅の１／２以上の場合に、前記２値のうち他方をビットとして出力すると共に、当該仮劣勢確率の区間幅から当該２値算術符号化で定める符号化区間幅の最大値の１／２を引算した値を１ビット左シフトし、前記仮劣勢確率の区間幅が前記２値算術符号化で定める最大の符号化区間幅の１／２よりも小さい場合に、前記不確定値をビットとして出力すると共に、当該仮劣勢確率の区間幅から当該２値算術符号化で定める符号化区間幅の最大値の１／４を引算した値を１ビット左シフトすることを特徴とする請求項１又は２に記載の２値算術符号化装置。
【請求項４】
前記２値算術再正規化手段は、
前記一定の回数をｎ回とした場合に、前記仮符号化区間幅をｎ−１ビット左シフトした値と２値算術符号化で定める最大の符号化区間幅の１／４との第１の比較を行い、当該仮符号化区間幅をｎ−１ビット左シフトした値が当該２値算術符号化で定める最大の符号化区間幅の１／４よりも小さい場合には、前記３値データ列の先頭ビットからｎ番目のビットまでのビット範囲が有効である前記第１の有効範囲値を出力し、
前記仮符号化区間幅をｎ−１ビット左シフトした値が前記２値算術符号化で定める最大の符号化区間幅の１／４以上の場合には、前段の比較で左シフトした仮符号化区間幅の値を更に１ビット左シフトした値と２値算術符号化で定める最大の符号化区間幅の１／４との第２の比較を行い、当該更に１ビット左シフトした値が当該２値算術符号化で定める最大の符号化区間幅の１／４よりも小さい場合には、前記３値データ列の先頭ビットから前段の出力処理で得られた前記ビット範囲よりも更に１つ少ないビット範囲を前記第１の有効範囲値として出力する出力処理を行い、
前記更に１ビット左シフトした値が前記２値算術符号化で定める最大の符号化区間幅の１／４以上の場合に、前記第２の比較と前記出力処理とを前記仮符号化区間幅に対する左シフト数がゼロになるまで繰り返し、前記仮符号化区間幅が２値算術符号化で定める最大の区間幅の１／４より小さい場合に、前記３値データ列の先頭ビットが有効である第１の有効範囲値を出力し、当該仮符号化区間幅が当該２値算術符号化で定める最大の区間幅の１／４以上である場合には、前記３値データ列の全てのビットが無効である第１の有効範囲値を出力することを特徴とする請求項１乃至３のいずれか１項に記載の２値算術符号化装置。
【請求項５】
前記２値算術再正規化手段は、
前記出力処理で前記第１の有効範囲値を出力すると共に、前記仮符号化区間幅を前記前段の比較で左シフトした数分左シフトした値を更新後の符号化区間幅として出力し、当該前段の比較で左シフトした数と同じ回数目の前記ビット出力処理で更新された前記仮劣勢確率の区間幅を更新後の劣勢確率の区間幅として出力し、当該更新後の符号化区間幅と当該更新後の劣勢確率の区間幅とを前記対象ビットの次に符号化の対象となるビットの符号化に用いることを特徴とする請求項４に記載の２値算術符号化装置。
【請求項６】
前記２値変換手段は、
前記３値データ列の各ビットのうちｓ番目のビットが前記２値のうちいずれかに一致するか否かの第１の比較を行い、当該ｓ番目のビットが当該２値のうちいずれかに一致する場合には、ｓ−１番目のビットが前記２値のうちいずれかに一致するか否かの第１の判定を行い、当該ｓ−１番目のビットが当該２値のうちいずれかに一致する場合には、前記ｓ番目のビットを前記２値データ列のｓ番目のビットとし、前記ｓ−１番目のビットが前記２値のうちいずれにも一致しない場合には、前記ｓ番目のビットの反転値を前記２値データ列のｓ番目のビットとし、
前記ｓ番目のビットが前記２値のうちいずれにも一致しない場合には、前段の比較で用いた次のビットが当該２値のうちいずれかに一致するか否かの第２の比較を行い、当該次のビットが前記２値のうちいずれかに一致する場合には、前記第１の判定を行い、前記ｓ−１番目のビットが前記２値のうちいずれかに一致する場合には、前記次のビットを前記２値データ列のｓ番目のビットとし、前記ｓ−１番目のビットが前記２値のうちいずれにも一致しない場合には、前記次のビットの反転値を前記２値データ列のｓ番目のビットとする変換処理を行い、
前記次のビットが前記２値のうちいずれにも一致しない場合には、当該第２の比較と前記第１の判定と前記変換処理とを前記３値データ列の最後のビットまで繰り返し、当該最後のビットが前記２値のうちいずれにも一致しない場合には、前記２値データ列のｓ番目のビットは無効として出力しないことを特徴とする請求項１乃至５のいずれか１項に記載の２値算術符号化装置。
【請求項７】
前記２値算術符号化で定める最大の符号化区間幅とは、Ｈ．２６４で規格された符号化区間幅の最大値であることを特徴とする請求項１乃至６のいずれか１項に記載の２値算術符号化装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、Ｈ．２４６のエントロピー符号化技術に関する。
【背景技術】
【０００２】
近年、カメラ等で取得した動画データを符号化処理する技術として、ＤＶＣ，ＭＥＰＧ２，ＭＰＥＧ４等のユーザの利用形態に応じた様々な技術が多く用いられている。
【０００３】
また最近では、従来のアナログ放送に加えて地上デジタル放送が開始されており、放送されるデジタル画像をより高画質に録画するため、より符号化効率のよい技術が求められている。これらの要求に対応するべく、動画データにおける圧縮符号化方式の標準の一つであるＨ．２６４という規格が既に標準化されており、ＭＰＥＧ２やＭＰＥＧ４等と比較して符号化及び復号化を行う際の演算量が多くなるものの、より高い符号化効率を得ることができる。
【０００４】
Ｈ．２６４には、ＣＡＶＬＣ（Context-Adaptive Variable Length Coding）と称される適応可変長符号化を用いる技術と、ＣＡＢＡＣ（Context-Adaptive Binary Arithmetic Coding）と称される適応２進法符号化を用いる技術の２種類が標準化されている。ハフマン符号化を用いるＣＡＶＬＣの場合、圧縮率が低くて計算量が少ないため、リアルタイム処理に適しているが画質が悪いという特徴がある。一方、２値算術符号化を用いるＣＡＢＡＣの場合、圧縮率が高く計算量が多いので、ＣＡＶＬＣを用いた場合よりも高画質であるものの、リアルタイム処理には向いていないという特徴がある。
【０００５】
図１０は、ＣＡＢＡＣを用いた従来の２値算術符号化装置の構成を示すブロック図である。従来の２値算術符号化装置は、図示しない前段の２値化器により多値データを予め決められた一定規則に基づいて任意の長さに２値化されたバイナリデータ（以降、「ＢＩＮ」と称する）と、このＢＩＮにおいて発生頻度の低い劣勢シンボルの発生確率を示すシンボル比率と、このＢＩＮにおいて発生頻度の高い優勢シンボルとを入力し、２値算術符号化を行う符号化区間幅（以降、「ｘＲａｎｇｅ」と称する）と、このｘＲａｎｇｅにおいて発生頻度の低い劣勢シンボルが発生する劣勢確率の区間幅（以降、「ｘＬｏｗ」と称する）とを更新する処理を繰り返すことにより、ＢＩＮを構成する各ビットの符号化を行う。
【０００６】
従来の２値算術符号化装置は、２値算術処理部３１１と再正規化部３１５とで構成された２値算術符号化部３を備える。２値算術処理部３１１は、符号化の対象となる対象ビットの前のビットの２値算術符号化時に更新されたｘＲａｎｇｅおよびｘＬｏｗを入力すると共に、ＢＩＮと、このＢＩＮのシンボル比率と、このＢＩＮの優勢シンボルとを入力し、ｘＲａｎｇｅを仮に更新した仮符号化区間幅（以降、「Ｒａｎｇｅ」と称する）と、ｘＬｏｗを仮に更新した仮劣勢確率の区間幅（以降、「Ｌｏｗ」と称する）とを出力する。
【０００７】
再正規化部３１５は、２値算術処理部３１１から出力されたＲａｎｇｅ及びＬｏｗを入力し、２値算術処理部３１１の処理によって小さくなったＲａｎｇｅ及びＬｏｗの区間幅をそれぞれ大きくするように更新して精度良く符号化を行う。再正規化部３１５では、後述する図１２及び図１３で示す処理によって得られた符号化ビットを出力すると共に、ＲａｎｇｅとＬｏｗとを更新し、更新後のｘＲａｎｇｅとｘＬｏｗとを出力する。出力された更新後のｘＲａｎｇｅとｘＬｏｗは、次のビットの２値算術符号化処理に用いられる。
【０００８】
続いて、従来の２値算術符号化装置の処理の流れについて説明する。図１１は、従来の２値算術処理部３１１における処理の流れを示すフロー図である。最初に、２値算術処理部３１１は、入力されたＢＩＮにおける符号化の対象となる対象ビットが優勢シンボルに一致するか否かを判定する（ステップＳ１１０１）。ステップＳ１１０１において入力されたＢＩＮの対象ビットが優勢シンボルの場合には、Ｌｏｗ＝ｘＬｏｗ，Ｒａｎｇｅ＝ｘＲａｎｇｅ−シンボル比率の処理を行う（ステップＳ１１０２）。一方、ステップＳ１１０１において入力されたＢＩＮの対象ビットが優勢シンボルでない場合には、Ｌｏｗ＝ｘＲａｎｇｅ＋ｘＬｏｗ−シンボル比率，Ｒａｎｇｅ＝シンボル比率の処理を行う（ステップＳ１１０３）。最後に、ステップＳ１１０２又はステップＳ１１０３で処理されたＲａｎｇｅ及びＬｏｗを出力する（ステップＳ１１０４）。
【０００９】
次に、再正規化部３１５における処理の流れについて説明する。図１２は、再正規化部３１５における処理の流れを示すフロー図である。最初に、再正規化部３１５は、２値算術処理部３１１から出力されたＲａｎｇｅ及びＬｏｗを入力し、ＲａｎｇｅとＲａｎｇｅの最大値の１／４の値を示すＱｕａｒｔｅｒとを比較する（ステップＳ１２１１）。ステップＳ１２１１において、ＲａｎｇｅがＱｕａｒｔｅｒ以上の場合には再正規化処理を終了する。一方、ＲａｎｇｅがＱｕａｒｔｅｒよりも小さい場合には、ＬｏｗとＱｕａｒｔｅｒとを比較する（ステップＳ１２１２）。ステップＳ１２１２において、ＬｏｗがＱｕａｒｔｅｒ以上の場合には、ＬｏｗとＲａｎｇｅの最大値の１／２の値を示すＨａｌｆとを比較する（ステップＳ１２１３）。ステップＳ１２１２において、ＬｏｗがＱｕａｒｔｅｒよりも小さい場合には、「０」のビットを出力する（ステップＳ１２１４）。なお、ステップＳ１２１４及び後に記載するステップＳ１２１７におけるビット出力の具体的なフローについては後述する。ステップＳ１２１３において、ＬｏｗがＨａｌｆよりも小さい場合には、Ｌｏｗ−Ｑｕａｒｔｅｒの値をＬｏｗに上書きし、再正規化処理時に出力値が確定できない状態を示す不確定値Ｂをインクリメントする（ステップＳ１２１５）。ステップＳ１２１３において、ＬｏｗがＨａｌｆ以上の場合には、Ｌｏｗ−Ｈａｌｆの値をＬｏｗに上書きする（ステップＳ１２１６）。ステップＳ１２１６においてＬｏｗを上書きした後に、「１」のビットを出力する（ステップＳ１２１７）。そして、ステップＳ１２１４及びステップＳ１２１７のビット出力、若しくは、ステップＳ１２１５のインクリメント処理の後に、Ｒａｎｇｅ及びＬｏｗの値をそれぞれ１ビット左シフト、即ち、Ｒａｎｇｅ及びＬｏｗの値を２倍にする（ステップＳ１２１８）。その後、ステップＳ１２１１に戻り、ＲａｎｇｅがＱｕａｒｔｅｒ以上になるまでステップＳ１２１１〜ステップＳ１２１８のループＡの処理を繰り返す。なお、ステップＳ１２１１において、ＲａｎｇｅがＱｕａｒｔｅｒ以上の場合には、その時点におけるＲａｎｇｅ及びＬｏｗを、ｘＲａｎｇｅ及びｘＬｏｗとして出力する。
【００１０】
ここで、ステップＳ１２１４及びステップＳ１２１７におけるビット出力の処理について説明する。図１３は、ビット出力の処理の流れを示すフロー図である。ビット出力処理は、ステップＳ１２１４の場合に、最初に符号化ビット「０」を出力し、ステップＳ１２１７の場合には、最初に符号化ビット「１」を出力する（ステップＳ１３０１）。符号化ビットの出力後、不確定値Ｂと０（ゼロ）とを比較する（ステップＳ１３０２）。ステップＳ１３０２において、不確定値Ｂが０（ゼロ）よりも大きい場合には、ステップＳ１３０１で出力した符号化ビットの反転値を出力する（ステップＳ１３０３）。反転値を出力した後に、不確定値Ｂをデクリメントする（ステップＳ１３０４）。デクリメントした後に、ステップＳ１３０２に戻り、不確定値Ｂが０（ゼロ）になるまでステップＳ１３０２〜ステップＳ１３０４のループＢの処理を繰り返す。ステップＳ１３０２において、不確定値Ｂが０（ゼロ）以下の場合に、ループＢの処理を終了し、図１２に示すループＡの処理であるステップＳ１２１８の処理を行う。
【００１１】
ここで、Ｈ．２６４の場合、非特許文献１に記載されているように、Ｒａｎｇｅの最大値は１０２４（＝２の１０乗）とされているため、Ｑｕａｒｔｅｒは２５６，Ｈａｌｆは５１２となる。Ｒａｎｇｅが最小値１であると仮定すると、ステップＳ１２１８の処理を行う毎にＲａｎｇｅの値が２倍となるため、８回（＝２の８乗）のループ処理でＱｕａｒｔｅｒと等しくなるので、最大８回のループＡの処理を必要とする。
【００１２】
続いて、図１２及び図１３に示す処理の流れに沿って、再正規化部３１５から出力される符号化ビットを算出する。ここで、Ｒａｎｇｅ＝１，Ｌｏｗ＝５，Ｒａｎｇｅの最大値＝１０２４，Ｑｕａｒｔｅｒ＝２５６，Ｈａｌｆ＝５１２，不確定値Ｂ＝０（ゼロ）とする。ＲａｎｇｅとＬｏｗが再正規化部３１５に入力された場合、ステップＳ１２１１においてＲａｎｇｅとＱｕａｔｅｒとが比較され、ＱｕａｒｔｅｒよりもＲａｎｇｅが小さいのでステップＳ１２１２に進む。ステップＳ１２１２では、ＬｏｗとＱｕａｒｔｅｒとが比較され、ＱｕａｒｔｅｒよりもＬｏｗが小さいのでステップＳ１２１４に進む。ステップＳ１２１４（ステップＳ１３０１）では「０」のビットが出力される。不確定値Ｂは０（ゼロ）のため、ステップＳ１２１８に進む。ステップＳ１２１８において、ＲａｎｇｅとＬｏｗが１ビット左シフトされ、Ｒａｎｇｅ＝２，Ｌｏｗ＝１０となり、ループＡの処理によってステップＳ１２１１に戻る。引き続き、ステップＳ１２１１→ステップＳ１２１２→ステップＳ１２１４と進み、「０」のビットが出力され、ステップＳ１２１８においてＲａｎｇｅ＝４，Ｌｏｗ＝２０となる。その後もループＡの処理によって、ステップＳ１２１１に戻り、ステップＳ１２１４で「０」のビットが出力され、ステップＳ１２１８においてＲａｎｇｅとＬｏｗが１ビット左シフトされる。
【００１３】
ビット出力が「００００００」となり、Ｒａｎｇｅ＝６４，Ｌｏｗ＝３２０となると、ステップＳ１２１１→ステップＳ１２１２→ステップＳ１２１３→ステップＳ１２１５と進み、ステップＳ１２１５においてＬｏｗ＝６４（＝３２０−２５６），不確定値Ｂ＝１となる。ステップＳ１２１８に進み、Ｒａｎｇｅ＝１２８，Ｌｏｗ＝１２８となりステップＳ１２１１に戻る。その後、ステップＳ１２１１→ステップＳ１２１２→ステップＳ１２１４と進み、ステップＳ１２１４（ステップＳ１３０１）において「０」のビットを出力する。ステップＳ１３０２において、不確定値Ｂは０（ゼロ）よりも大きいので、ステップＳ１３０３において、ステップＳ１３０１で出力されたビット「０」の反転ビット「１」を出力し、ステップＳ１３０４において、不確定値Ｂをデクリメントする。ループＢの処理によりステップＳ１３０２に戻り、不確定値Ｂは０（ゼロ）なのでステップＳ１２１８に進む。ステップＳ１２１８でＲａｎｇｅ＝２５６，Ｌｏｗ＝２５６となり、ループＡの処理によりステップＳ１２１１に戻る。ステップＳ１２１１では、ＲａｎｇｅがＱｕａｒｔｅｒ以上なので再正規化処理を終了する。
【００１４】
以上の処理から、再正規化部３１５から出力される符号化ビットは「０００００００１」，ｘＲａｎｇｅ＝２５６，ｘＬｏｗ＝２５６となる。
【非特許文献１】「Advanced video coding for generic audiovisual services」、ITU-T、2003年5月、JT-H264
【発明の開示】
【発明が解決しようとする課題】
【００１５】
前述したように、２値算術処理部から出力されるＲａｎｇｅとＬｏｗは、入力されるＢＩＮ，シンボル比率，優勢シンボルにより変化し、再正規化部でのループ処理の回数は、その変化したＲａｎｇｅとＬｏｗに依存するため、ｘＲａｎｇｅとｘＬｏｗが２値算術符号化部から出力されるタイミングは、前の２値算術符号化処理と次の２値算術符号化処理とにおいて常に同じとは限らないものとなっている。具体的には、ループ処理が前の２値算術符号化処理よりも多く繰り返される場合には、ｘＲａｎｇｅとｘＬｏｗの出力タイミングが遅れて、次のＢＩＮに対する符号化の処理が遅れることになる。
【００１６】
つまり、ｘＲａｎｇｅとｘＬｏｗの出力がされるまでには多くの処理時間を要し、入力されるＢＩＮ等によってループ処理の回数が変動するため、ループ処理の回数を画一的に定めることが難しく、リアルタイム処理が困難であるという問題があった。
【００１７】
また、従来の２値算術符号化でリアルタイム処理を行うには、ＣＡＢＡＣよりも圧縮率の低いＣＡＶＬＣを用いるか、ＣＡＢＡＣを用いる場合には量子化ステップを大きくして画質を下げる必要があるという問題があった。
【００１８】
本発明は、上記に鑑みてなされたものであり、高画質でリアルタイム処理が可能な２値算術符号化装置を提供することを課題とする。
【課題を解決するための手段】
【００１９】
第１の請求項に係る２値算術符号化装置は、２値で表現されたバイナリデータと、当該バイナリデータにおいて発生頻度の低い劣勢シンボルの発生確率を示すシンボル比率と、当該バイナリデータにおいて発生頻度の高い優勢シンボルとを入力し、２値算術符号化を行う符号化区間幅と、当該符号化区間幅において発生頻度の低い劣勢シンボルが発生する劣勢確率の区間幅とを更新して前記バイナリデータの各ビットを符号化する２値算術符号化装置において、符号化の対象となる対象ビットが前記優勢シンボルに一致するか否かの判定結果に基づいて、前記符号化区間幅と前記劣勢確率の区間幅とを仮に更新した仮符号化区間幅と仮劣勢確率の区間幅とを算出し、当該仮劣勢確率の区間幅と２値算術符号化で定める最大の符号化区間幅に対する所定の割合との比較の結果に応じて前記２値又は不確定値の３値のうちいずれかをビットとして出力すると共に当該仮劣勢確率の区間幅を更に更新するビット出力処理と、当該更に更新された仮劣勢確率の区間幅と前記２値算術符号化で定める最大の符号化区間幅に対する所定の割合との比較の結果に応じて行う前記ビット出力処理とを一定の回数繰り返し行うことで得られた複数のビットを出力順に並べた３値データ列を生成すると共に、当該３値データ列を構成する複数のビットの第１の有効範囲値を出力する２値算術再正規化手段と、前記３値データ列と前記第１の有効範囲値とを格納する３値データ格納手段と、前記３値データ列と前記第１の有効範囲値とを前記３値データ格納手段から読み出して、当該３値データ列の各ビットが前記２値のうちいずれかに一致するか否かの確認結果に基づいて、当該３値データ列を前記２値のうちいずれかをビットとする２値データ列に変換すると共に、当該２値データ列に変換できないビットの総数を未処理データ数として算出し、前記第１の有効範囲値から当該未処理データ数を引くことで得られる当該２値データ列におけるビットの第２の有効範囲値を算出する２値変換手段と、前記２値データ列と前記第２の有効範囲値と前記未処理データ数とを格納する２値データ格納手段と、前記２値データ列と前記第２の有効範囲値と前記未処理データ数とを前記２値データ格納手段から読み出して、当該第２の有効範囲値がゼロの場合に、前記対象ビットに対する符号化ビット列は出力しないと共に予め保持していた未処理データ数に読み出した前記未処理データ数を加算し、当該第２の有効範囲値がゼロよりも大きい場合には未処理データ数が予め保持されているか否かを判断し、保持されている場合には、前記２値データ列の先頭ビットの次に当該先頭ビットの反転値を当該予め保持されていた未処理データ数分挿入した符号化ビット列を出力すると共に予め保持されていた未処理データ数に読み出した前記未処理データ数を上書きし、保持されていない場合には、前記２値データ列を符号化ビット列として出力すると共に読み出した前記未処理データ数を保持するｆ値滞留処理手段と、を有することを要旨とする。
【００２０】
本発明にあっては、対象ビットに対する３値データ列を出力するタイミングで、更新後の符号化区間幅と更新後の劣勢確率の区間幅とを出力するため、２値変換手段とｆ値滞留処理手段とにより３値データ列を２値データ列に変換して符号化ビットを出力する間に、２値算術再正規化手段により次のビットに対する２値算術符号化の処理が可能となる。即ち、２値算術符号化に要するクロックサイクルを少なくするため、高画質でリアルタイム処理が可能な２値算術符号化装置を提供することができる。
【００２１】
第２の請求項に係る２値算術符号化装置は、前記２値算術再正規化手段が、前記対象ビットが前記優勢シンボルに一致する場合に、前記劣勢確率の区間幅を前記仮劣勢確率の区間幅、前記符号化区間幅から前記シンボル比率を減算した値を前記仮符号化区間幅とし、前記対象ビットが前記優勢シンボルに一致しない場合に、前記符号化区間幅に前記劣勢確率の区間幅から前記シンボル比率を減算した値を加算した値を前記仮劣勢確率の区間幅、前記シンボル比率を前記仮符号化区間幅とすることを要旨とする。
【００２２】
第３の請求項に係る２値算術符号化装置は、前記ビット出力処理が、前記仮劣勢確率の区間幅が前記２値算術符号化で定める最大の符号化区間幅の１／４よりも小さい場合に、前記２値のうち一方をビットとして出力すると共に、当該仮劣勢確率の区間幅を１ビット左シフトし、前記仮劣勢確率の区間幅が前記２値算術符号化で定める最大の符号化区間幅の１／４以上の場合に、前記仮劣勢確率の区間幅と２値算術符号化で定める最大の符号化区間幅の１／２とを比較し、当該仮劣勢確率の区間幅が当該２値算術符号化で定める最大の符号化区間幅の１／２以上の場合に、前記２値のうち他方をビットとして出力すると共に、当該仮劣勢確率の区間幅から当該２値算術符号化で定める符号化区間幅の最大値の１／２を引算した値を１ビット左シフトし、前記仮劣勢確率の区間幅が前記２値算術符号化で定める最大の符号化区間幅の１／２よりも小さい場合に、前記不確定値をビットとして出力すると共に、当該仮劣勢確率の区間幅から当該２値算術符号化で定める符号化区間幅の最大値の１／４を引算した値を１ビット左シフトすることを要旨とする。
【００２３】
第４の請求項に係る２値算術符号化装置は、前記２値算術再正規化手段が、前記一定の回数をｎ回とした場合に、前記仮符号化区間幅をｎ−１ビット左シフトした値と２値算術符号化で定める最大の符号化区間幅の１／４との第１の比較を行い、当該仮符号化区間幅をｎ−１ビット左シフトした値が当該２値算術符号化で定める最大の符号化区間幅の１／４よりも小さい場合には、前記３値データ列の先頭ビットからｎ番目のビットまでのビット範囲が有効である前記第１の有効範囲値を出力し、前記仮符号化区間幅をｎ−１ビット左シフトした値が前記２値算術符号化で定める最大の符号化区間幅の１／４以上の場合には、前段の比較で左シフトした仮符号化区間幅の値を更に１ビット左シフトした値と２値算術符号化で定める最大の符号化区間幅の１／４との第２の比較を行い、当該更に１ビット左シフトした値が当該２値算術符号化で定める最大の符号化区間幅の１／４よりも小さい場合には、前記３値データ列の先頭ビットから前段の出力処理で得られた前記ビット範囲よりも更に１つ少ないビット範囲を前記第１の有効範囲値として出力する出力処理を行い、前記更に１ビット左シフトした値が前記２値算術符号化で定める最大の符号化区間幅の１／４以上の場合に、前記第２の比較と前記出力処理とを前記仮符号化区間幅に対する左シフト数がゼロになるまで繰り返し、前記仮符号化区間幅が２値算術符号化で定める最大の区間幅の１／４より小さい場合に、前記３値データ列の先頭ビットが有効である第１の有効範囲値を出力し、当該仮符号化区間幅が当該２値算術符号化で定める最大の区間幅の１／４以上である場合には、前記３値データ列の全てのビットが無効である第１の有効範囲値を出力することを要旨とする。
【００２４】
第５の請求項に係る２値算術符号化装置は、前記２値算術再正規化手段が、前記出力処理で前記第１の有効範囲値を出力すると共に、前記仮符号化区間幅を前記前段の比較で左シフトした数分左シフトした値を更新後の符号化区間幅として出力し、当該前段の比較で左シフトした数と同じ回数目の前記ビット出力処理で更新された前記仮劣勢確率の区間幅を更新後の劣勢確率の区間幅として出力し、当該更新後の符号化区間幅と当該更新後の劣勢確率の区間幅とを前記対象ビットの次に符号化の対象となるビットの符号化に用いることを要旨とする。
【００２５】
第６の請求項に係る２値算術符号化装置は、前記２値変換手段が、前記３値データ列の各ビットのうちｓ番目のビットが前記２値のうちいずれかに一致するか否かの第１の比較を行い、当該ｓ番目のビットが当該２値のうちいずれかに一致する場合には、ｓ−１番目のビットが前記２値のうちいずれかに一致するか否かの第１の判定を行い、当該ｓ−１番目のビットが当該２値のうちいずれかに一致する場合には、前記ｓ番目のビットを前記２値データ列のｓ番目のビットとし、前記ｓ−１番目のビットが前記２値のうちいずれにも一致しない場合には、前記ｓ番目のビットの反転値を前記２値データ列のｓ番目のビットとし、前記ｓ番目のビットが前記２値のうちいずれにも一致しない場合には、前段の比較で用いた次のビットが当該２値のうちいずれかに一致するか否かの第２の比較を行い、当該次のビットが前記２値のうちいずれかに一致する場合には、前記第１の判定を行い、前記ｓ−１番目のビットが前記２値のうちいずれかに一致する場合には、前記次のビットを前記２値データ列のｓ番目のビットとし、前記ｓ−１番目のビットが前記２値のうちいずれにも一致しない場合には、前記次のビットの反転値を前記２値データ列のｓ番目のビットとする変換処理を行い、前記次のビットが前記２値のうちいずれにも一致しない場合には、当該第２の比較と前記第１の判定と前記変換処理とを前記３値データ列の最後のビットまで繰り返し、当該最後のビットが前記２値のうちいずれにも一致しない場合には、前記２値データ列のｓ番目のビットは無効として出力しないことを要旨とする。
【００２６】
第７の請求項に係る２値算術符号化装置は、前記２値算術符号化で定める最大の符号化区間幅とは、Ｈ．２６４で規格された符号化区間幅の最大値であることを要旨とする。
【発明の効果】
【００２７】
本発明によれば、高画質でリアルタイム処理が可能な２値算術符号化装置を提供することができる。
【発明を実施するための最良の形態】
【００２８】
以下、本発明の実施の形態について図面を用いて説明する。
【００２９】
＜２値算術符号化装置の構成についての説明＞
図１は、本実施の形態の係る２値算術符号化装置の構成を示すブロック図である。本実施の形態に係る２値算術符号化装置は、図示しない前段の２値化器により多値データを予め決められた一定規則に基づいて任意の長さに２値化されたバイナリデータ（以降、「ＢＩＮ」と称する）と、このＢＩＮにおいて発生頻度の低い劣勢シンボルの発生確率を示すシンボル比率と、このＢＩＮにおいて発生頻度の高い優勢シンボルとを入力し、２値算術符号化を行う符号化区間幅（以降、「ｘＲａｎｇｅ」と称する）と、このｘＲａｎｇｅにおいて発生頻度の低い劣勢シンボルが発生する劣勢確率の区間幅（以降、「ｘＬｏｗ」と称する）とを更新する処理を繰り返すことにより、ＢＩＮを構成する各ビットの符号化を行う。
【００３０】
この２値算術符号化装置は、２値算術再正規化部３１と、２値変換部３２と、ｆ値滞留処理部３３と、２値算術再正規化部３１から出力された３値データ列を格納する３値データ格納部３４と、２値変換部３２で変換された２値データ列を格納する２値データ格納部３５とで構成された２値算術符号化部３を備える。
【００３１】
２値算術再正規化部３１は、従来の処理と同様に、図１１に示す処理を行った後に、図１２に示すループＡの処理から図１３に示すループＢの処理を切り離した処理に相当する処理を行うことにより、更新後のｘＲａｎｇｅと更新後のｘＬｏｗを出力する。２値変換部３２とｆ値滞留処理部３３は、図１３に示すループＢの処理に相当する処理を行うことにより、符号化ビットを確定する。
【００３２】
図１２及び図１３に示す従来の再正規化処理の場合、Ｌｏｗの大きさによって、「０」を出力してからループＢの処理を行う処理、不確定値Ｂをインクリメントする処理、「１」を出力してからループＢの処理を行う処理を行っており、これらの処理が完了した後に、ＲａｎｇｅとＬｏｗの値を１ビット左シフトしてステップＳ１２１１に戻る処理であるため、ＲａｎｇｅとＬｏｗの更新値が出力されるまで多くの処理時間を要するものであった。
【００３３】
本実施の形態では、符号化ビットを確定する前に、ＲａｎｇｅとＬｏｗの更新値を確定し、更新されたｘＲａｎｇｅとｘＬｏｗをフィードバックすることにより、２値算術符号化処理におけるパイプライン処理を可能としている。
【００３４】
即ち、ループＡの処理からループＢの処理を切り離した処理を、ループＡの最大回数分シリアルに進め、その処理結果を３値化されたデータで保持しておく。この処理と共に、ｘＲａｎｇｅとｘＬｏｗの更新値を確定する。更新されたｘＲａｎｇｅと更新されたｘＬｏｗを次のビットの符号化を行う際に利用することで、パイプライン処理を可能としている。
【００３５】
更に、２値変換部３２とｆ値滞留処理部３３は、上記３値化されたデータの処理結果を受けて、実質的にループＢをほどいた処理を実施することで、符号化ビットを確定している。
【００３６】
＜２値算術再正規化部の構成についての説明＞
図２は、２値算術再正規化部の構成を示すブロック図である。２値算術再正規化部３１は、２値算術処理部３１１と、第１〜第ｎのＲＳ（Ｒｅｎｏｒｍａｌｉｚｅ  Ｓｕｂｂｌｏｃｋ）部３１２ａ〜３１２ｎと、ＳＬ（Ｓｅｌｅｃｔｏｒ）部３１３とで構成されている。２値算術処理部３１１は、符号化の対象となる対象ビットの前のビットの２値算術符号化時に更新されたｘＲａｎｇｅおよびｘＬｏｗを入力すると共に、ＢＩＮと、このＢＩＮのシンボル比率と、このＢＩＮの優勢シンボルとを入力し、ｘＲａｎｇｅを仮に更新した仮符号化区間幅（以降、「Ｒａｎｇｅ」と称する）と、ｘＬｏｗを仮に更新した仮劣勢確率の区間幅（以降、「Ｌｏｗ」と称する）とを出力する。
【００３７】
第１のＲＳ部３１２ａは、２値算術処理部３１１から出力されたＬｏｗを入力し、ｘＬｏｗ＃１と３値データｘｄ＃１とを出力する。第１〜第ｎのＲＳ部３１２ａ〜３１２ｎを構成する１つのＲＳ部は、図１２に示すループＡからループＢを切り離した処理の１回分に相当する処理を行うため、Ｈ．２６４の場合には、前述したように最大８つのＲＳ部を設けることで同様の処理が可能となる。以降の第２〜第ｎのＲＳ部は、前段の第１〜第ｎ−１のＲＳ部から出力されたｘＬｏｗ＃１〜ｘＬｏｗ＃ｎ−１を入力し、ｘＬｏｗ＃２〜ｘＬｏｗ＃ｎと３値データｘｄ＃２〜ｘｄ＃ｎとを出力する。以降、第１〜第ｎのＲＳ部３１２ａ〜３１２ｎに入力されるＬｏｗ及びｘＬｏｗ＃１〜ｘＬｏｗ＃ｎ−１をＬｏｗ’とする。
【００３８】
ＳＬ部３１３は、２値算術処理部３１１から出力されたＲａｎｇｅ及びＬｏｗと、第１〜第ｎのＲＳ部３１２ａ〜３１２ｎから出力されたｘＬｏｗ＃１〜ｘＬｏｗ＃ｎを入力し、更新後のｘＲａｎｇｅと更新後のｘＬｏｗと３値データｘｄ＃１〜ｘｄ＃ｎの有効範囲を示す有効範囲値（以降、「ｘｖａｌｉｄ」と称する）とを出力する。
【００３９】
＜２値算術処理部における処理の流れについての説明＞
２値算術処理部３１１における処理は、図１１に示す従来の処理と同様なので、ここでは重複説明を省略する。
【００４０】
＜第１〜第ｎのＲＳ部における処理の流れについての説明＞
図３は、第１〜第ｎのＲＳ部３１２ａ〜３１２ｎにおける処理の流れを示すフロー図である。各ＲＳ部における処理の流れは同じなので、ここではｅ段目の第ｅのＲＳ部に入力された場合の処理の流れについて説明する。
【００４１】
第ｅのＲＳ部は、入力されたＬｏｗ’とＱｕａｒｔｅｒとを比較する（ステップＳ３０１）。ステップＳ３０１において、Ｌｏｗ’がＱｕａｒｔｅｒよりも小さい場合には、入力されたＬｏｗ’の値を１ビット左シフトした値をｘＬｏｗ＃ｅとして出力すると共に、３値データｘｄ＃ｅ＝０を出力する（ステップＳ３０２）。ステップＳ３０１において、Ｌｏｗ’がＱｕａｒｔｅｒ以上の場合には、Ｌｏｗ’とＨａｌｆとを比較する（ステップＳ３０３）。ステップＳ３０３において、Ｌｏｗ’がＨａｌｆ以上の場合には、Ｌｏｗ’からＨａｌｆを引いた値を１ビット左シフトし、その値をｘＬｏｗ＃ｅとして出力すると共に、３値データｘｄ＃ｅ＝１を出力する（ステップＳ３０４）。ステップＳ３０３において、Ｌｏｗ’がＨａｌｆよりも小さい場合には、Ｌｏｗ’からＱｕａｒｔｅｒを引いた値を１ビット左シフトし、その値をｘＬｏｗ＃ｅとして出力すると共に、３値データｘｄ＃ｅ＝ｆを出力する（ステップＳ３０５）。ステップＳ３０５において、３値データとして出力される値ｆは、符号化ができないことを示す不確定値ｆを意味している。
【００４２】
そして、後段の第ｅ＋１のＲＳ部は、前段の第ｅのＲＳ部から出力されたｘＬｏｗ＃ｅを入力し、上述した処理と同様に、Ｌｏｗ値ｘＬｏｗ＃ｅ＋１と３値データｘｄ＃ｅ＋１とを出力する。
【００４３】
各ＲＳ部から出力された３値データｘｄ＃１〜ｘｄ＃ｎは、出力された順番に並べられた３値データ列として３値データ格納部３４を介して２値変換部３２に入力され、ｘＬｏｗ＃１〜ｘＬｏｗ＃ｎは後段のＲＳ部及びＳＬ部３１３に入力される。
【００４４】
＜ＳＬ部における処理の流れについての説明＞
図４は、ＳＬ部３１３における処理の流れを示すフロー図である。最初に、ＳＬ部３１３は、Ｒａｎｇｅをｎ−１ビット左シフトした第１のシフト値とＱｕａｒｔｅｒとを比較する（ステップＳ４０１）。ステップＳ４０１において、第１のシフト値がＱｕａｒｔｅｒよりも小さい場合には、３値データｘｄ＃１〜ｘｄ＃ｎが全て有効であることを示すｘｖａｌｉｄを出力すると共に、Ｒａｎｇｅをｎビット左シフトした値をｘＲａｎｇｅとして出力し、ｘＬｏｗ＃ｎをｘＬｏｗとして出力する（ステップＳ４０２）。ステップＳ４０１において、第１のシフト値がＱｕａｒｔｅｒ以上の場合には、Ｒａｎｇｅをｎ−２ビット左シフトした第２のシフト値とＱｕａｒｔｅｒとを比較する（ステップＳ４０３）。ステップＳ４０３において、第２のシフト値がＱｕａｒｔｅｒよりも小さい場合には、３値データｘｄ＃１〜ｘｄ＃ｎ−１が全て有効であることを示すｘｖａｌｉｄを出力すると共に、Ｒａｎｇｅをｎ−１ビット左シフトした値をｘＲａｎｇｅとして出力し、ｘＬｏｗ＃ｎ−１をｘＬｏｗとして出力する（ステップＳ４０４）。ステップＳ４０３において、第２のシフト値がＱｕａｒｔｅｒ以上の場合には、Ｒａｎｇｅをｎ−３ビット左シフトした第３のシフト値とＱｕａｒｔｅｒとを比較する（ステップＳ４０５）。ステップＳ４０５において、第３のシフト値がＱｕａｒｔｅｒよりも小さい場合には、３値データｘｄ＃１〜ｘｄ＃ｎ−２が全て有効であることを示すｘｖａｌｉｄを出力すると共に、Ｒａｎｇｅをｎ−２ビット左シフトした値をｘＲａｎｇｅとして出力し、ｘＬｏｗ＃ｎ−２をｘＬｏｗとして出力する（ステップＳ４０６）。以降、順次Ｒａｎｇｅを１ビットづつ少なく左シフトし、左シフトしたＲａｎｇｅとＱｕａｒｔｅｒとを比較し、その比較結果によってｘｖａｌｉｄとｘＲａｎｇｅ及びｘＬｏｗとを出力する。
【００４５】
最終的に、ＳＬ部３１３は、ＲａｎｇｅとＱｕａｒｔｅｒとを比較する（ステップＳ４０７）。ステップＳ４０７において、ＲａｎｇｅがＱｕａｒｔｅｒよりも小さい場合には、３値データｘｄ＃１のみが有効であることを示すｘｖａｌｉｄを出力すると共に、Ｒａｎｇｅを１ビット左シフトした値をｘＲａｎｇｅとして出力し、ｘＬｏｗ＃１をｘＬｏｗとして出力する（ステップＳ４０８）。ステップＳ４０７において、ＲａｎｇｅがＱｕａｒｔｅｒ以上の場合には、３値データｘｄ＃１〜ｘｄ＃ｎは全て無効であることを示すｘｖａｌｉｄを出力すると共に、ＲａｎｇｅをｘＲａｎｇｅとして出力し、ＬｏｗをｘＬｏｗとして出力する（ステップＳ４０９）。
【００４６】
ＳＬ部３１３から出力された更新後のｘＲａｎｇｅと更新後のｘＬｏｗは、再び２値算術再正規化部３１にフィードバックされ、次のビットに対する２値算術符号化処理に用いられる。ｘｖａｌｉｄは、各ＲＳ部から出力された３値データ列と共に、３値データ格納部３４を介して２値変換部３２に入力される。
【００４７】
＜２値変換部の構成についての説明＞
図５は、２値変換部３２の構成を示すブロック図である。２値変換部３２は、２値算出処理部３２１と、有効性算出部３２２とで構成されている。２値変換部３２は、３値データ格納部３４を介して２値算術再正規化部３１から出力されたｎ個の３値データｘｄ＃１〜ｘｄ＃ｎと、３値データｘｄ＃１〜ｘｄ＃ｎの有効範囲を示すｘｖａｌｉｄとを入力し、ｍ個の２値データｙｄ＃１〜ｙｄ＃ｍと、２値データｙｄ＃１〜ｙｄ＃ｍの有効範囲を示す有効範囲値（以降、「ｙｖａｌｉｄ」と称する）と、符号化できない不確定値ｆの数をカウントした未処理データ数（以降、「ｙｓｋｉｐ」と称する）とを出力する。
【００４８】
２値算出処理部３２１は、２値算術再正規化部３１から出力された３値データ列としての３値データｘｄ＃１〜ｘｄ＃ｎを入力し、入力された各３値データが「０」若しくは「１」の確定値か、若しくはｆの不確定値であるかを判断して２値データに変換し、変換したｍ個の２値データｙｄ＃１〜ｙｄ＃ｍを２値データ列として出力する。
【００４９】
有効性算出部３２２は、２値算術再正規化部３１から出力された３値データｘｄ＃１〜ｘｄ＃ｎとｘｖａｌｉｄとを入力し、入力された３値データｘｄ＃１〜ｘｄ＃ｎの最後に連続する不確定値ｆの数をカウントしたｙｓｋｉｐと、ｘｖａｌｉｄからｙｓｋｉｐを引くことで算出される２値データの有効範囲を示すｙｖａｌｉｄとを出力する。
【００５０】
＜２値算出処理部における処理の流れについての説明＞
図６は、２値算出処理部３２１における処理の流れを示すフロー図である。ｎ個の３値データｘｄ＃１〜ｘｄ＃ｎが２値変換部３２に入力した際のｓ番目の２値データを算出するフローについて説明する。
【００５１】
２値算出処理部３２１は、入力された３値データｘｄ＃ｓが確定値に一致するか否かを比較する（ステップＳ６０１）。ステップＳ６０１において、３値データｘｄ＃ｓが確定値であった場合には、一つ前の３値データｘｄ＃ｓ−１が確定値に一致するか否かを判定する（ステップＳ６０２）。ステップＳ６０１において、ｓ＝１の場合には１つ前の３値データがないため、３値データｘｄ＃ｓ−１は確定値として処理を行う。ステップＳ６０２において、３値データｘｄ＃ｓ−１が確定値の場合には、ｓ番目の３値データｘｄ＃ｓをｓ番目の２値データｙｄ＃ｓとして出力する（ステップＳ６０３）。ステップＳ６０２において、３値データｘｄ＃ｓ−１が不確定値の場合には、ｓ番目の３値データｘｄ＃ｓの反転値＾ｘｄ＃ｓをｓ番目の２値データｙｄ＃ｓとして出力する（ステップＳ６０４）。なお、「＾」は反転値を意味している。
【００５２】
ステップＳ６０１において、３値データｘｄ＃ｓが不確定値であった場合には、一つ後ろの３値データｘｄ＃ｓ＋１が確定値に一致するか否かを比較する（ステップＳ６０５）。ステップＳ６０５において、３値データｘｄ＃ｓ＋１が確定値であった場合には、ｓ−１番目の３値データｘｄ＃ｓ−１が確定値に一致するか否かを判定する（ステップＳ６０６）。ステップＳ６０６において、３値データｘｄ＃ｓ−１が確定値の場合には、ｓ＋１番目の３値データｘｄ＃ｓ＋１をｓ番目の２値データｙｄ＃ｓとして出力する（ステップＳ６０７）。ステップＳ６０６において、３値データｘｄ＃ｓ−１が不確定値の場合には、ｓ＋１番目の３値データｘｄ＃ｓ＋１の反転値＾ｘｄ＃ｓ＋１をｓ番目の２値データｙｄ＃ｓとして出力する（ステップＳ６０８）。
【００５３】
以降、同様に、ｔ番目の３値データｘｄ＃ｔが確定値に一致するか否かを比較する（ステップＳ６０９）。ステップＳ６０９において、３値データｘｄ＃ｔが確定値であった場合には、ｓ−１番目の３値データｘｄ＃ｓ−１が確定値に一致するか否かを判定する（ステップＳ６１０）。ステップＳ６１０において、３値データｘｄ＃ｓ−１が確定値の場合には、ｔ番目の３値データｘｄ＃ｔをｓ番目の２値データｙｄ＃ｓとして出力する（ステップＳ６１１）。ステップＳ６１０において、３値データｘｄ＃ｓ−１が不確定値の場合には、ｔ番目の３値データｘｄ＃ｔの反転値＾ｘｄ＃ｔをｓ番目の２値データｙｄ＃ｓとして出力する（ステップＳ６１２）。
【００５４】
ｎ−１番目の３値データｘｄ＃ｎ−１まで不確定値であった場合、ｎ番目の３値データｘｄ＃ｎが確定値に一致するか否かを比較する（ステップＳ６１３）。ステップＳ６１３において、３値データｘｄ＃ｎが確定値であった場合には、ｓ−１番目の３値データｘｄ＃ｓ−１が確定値に一致するか否かを判定する（ステップＳ６１４）。ステップＳ６１４において、３値データｘｄ＃ｓ−１が確定値の場合には、ｎ番目の３値データｘｄ＃ｎをｓ番目の２値データｙｄ＃ｓとして出力する（ステップＳ６１５）。ステップＳ６１４において、３値データｘｄ＃ｓ−１が不確定値の場合には、ｎ番目の３値データｘｄ＃ｎの反転値＾ｘｄ＃ｎをｓ番目の２値データｙｄ＃ｓとして出力する（ステップＳ６１６）。
【００５５】
ステップＳ６１３において、３値データｘｄ＃ｎが不確定値であった場合には、３値データｘｄ＃ｓ〜ｘｄ＃ｎは全て不確定値であるため、２値データに変換することなく、ｓ番目のビットは無効としてなにも出力しない（ステップＳ６１７）。この場合は、後述するｙｖａｌｉｄで認識可能となる。
【００５６】
２値算出処理部３２１から出力された２値データのｙｄ＃１〜ｙｄ＃ｍは、２値データ列として２値データ格納部３５を介してｆ値滞留処理部３３に入力される。
【００５７】
以上の処理を行うことで、図７に示すように、２値算出処理部３２１において１ビット分の２値データｙｄ＃ｚを決定するＣＨＧ（Ｃｈａｒｇｅ）部を３値データの数に合わせて設けることにより、並列な算出処理を行うことが可能となる。
【００５８】
＜有効性算出部における処理の流れについての説明＞
有効性算出部３２２は、先に説明したように、符号化できない不確定値ｆの数をカウントしたｙｓｋｉｐと、３値データｘｄ＃１〜ｘｄ＃ｎの有効範囲を示すｘｖａｌｉｄからｙｓｋｉｐを引くことで得られる２値データｙｄ＃１〜ｙｄ＃ｍの有効範囲を示すｙｖａｌｉｄとを出力する。
【００５９】
有効性算出部３２２から出力されたｙｓｋｉｐとｙｖａｌｉｄは、２値データ格納部３５を介してｆ値滞留処理部３３に入力される。
【００６０】
＜２値変換部で変換される具体例についての説明＞
ここで、図６に示す処理の流れをより具体的に説明する。図８は、２値算術再正規化部３１から出力された３値データｘｄ＃１〜ｘｄ＃８が、２値変換部３２により２値データｙｄ＃１〜ｙｄ＃５に変換された具体例を示す図である。図８（ａ）は、２値算術再正規化部３１から出力された８ビットの３値データｘｄ＃１〜ｘｄ＃８を示す図である。図８（ｂ）は、この８ビットの３値データｘｄ＃１〜ｘｄ＃８が２値データｙｄ＃１〜ｙｄ＃５に変換された後を示す図である。図８（ｃ）は、２値データに変換されなかった無効データを示す図である。
【００６１】
２値算出処理部３２１は、図８（ａ）に示す３値データｘｄ＃１〜ｘｄ＃８が入力された場合、ステップＳ６０１において、ｘｄ＃１が確定値であるかを確認する。ｘｄ＃１は不確定値ｆなので、ステップＳ６０５の処理を行い、ｘｄ＃２が確定値であるかを確認する。ｘｄ＃２は確定値「１」なので、ステップＳ６０６の処理を行う。ステップＳ６０６は、ｘｄ＃１−１を求める処理であるが、入力されたｘｄ＃１が１番目のビットなので、ステップＳ６０６は全て真であるとみなされ、ｘｄ＃２の値である「１」が２値データｙｄ＃１として出力される。
【００６２】
同様に、２番目の２値データｙｄ＃２を決定する際には、ステップＳ６０１でＹｅｓ、ステップＳ６０２でＮｏと判定されるので、ｘｄ＃２の反転値である「０」がｙｄ＃２として出力される。以降、図８（ｂ）に示すような２値データがｙｄ＃５まで出力される。３値データｘｄ＃６〜ｘｄ＃８は、不確定値ｆなので、図６に示す処理により無効とされ、図８（ｃ）に示すように２値データに変換されない。この場合、有効性算出部３２２は、３値データｘｄ＃６〜ｘｄ＃８の数をカウントした数をｙｓｋｉｐとして出力する。
【００６３】
有効性算出部３２２は、ｙｓｋｉｐを出力すると共に、ｘｖａｌｉｄからｙｖａｌｉｄを引いた数をｙｖａｌｉｄとして出力する。
【００６４】
＜ｆ値滞留処理部の構成についての説明＞
ｆ値滞留処理部３３は、２値データ格納部３５を介して、２値変換部３２から出力された２値データ列としてのｍ個の２値データｙｄ＃１〜ｙｄ＃ｍと、２値データｙｄ＃１〜ｙｄ＃ｍの有効範囲を示すｙｖａｌｉｄと、符号化できない不確定値ｆの数をカウントした未処理データ数を示すｙｓｋｉｐとを入力し、符号化ビットｚｄ＃１〜ｚｄ＃ｐと、符号化ビット列の有効範囲を示す有効範囲値（以降、「ｚｖａｌｉｄ」と称する）とを出力する。
【００６５】
＜ｆ値滞留処理部における処理の流れについての説明＞
図９は、ｆ値滞留処理部３３における処理の流れを示すフロー図である。ｆ値滞留処理部３３は、２値データｙｄ＃１〜ｙｄ＃ｍと、ｙｓｋｉｐと、ｙｖａｌｉｄとが入力された場合、ｙｖａｌｉｄの値に基づいて、有効な２値データがあるかを確認する（ステップＳ９０１）。ステップＳ９０１において、有効な２値データが存在しない場合には、符号化ビット列の出力はないものとしてｚｖａｌｉｄ＝０を出力し、ｙｓｋｉｐの入力よりも前にｆ値滞留処理部３３が保持していたｙｓｋｉｐ（以降「ｙｓｋｉｐ１」と称する）に、入力されたｙｓｋｉｐを加えた数値をｙｓｋｉｐ１として上書きして保持する（ステップＳ９０２）。ステップＳ９０１において、有効な２値データが存在する場合には、ｙｓｋｉｐ１を保持しているかを確認する（ステップＳ９０３）。ステップＳ９０３において、ｙｓｋｉｐ１を保持していない場合には、２値データｙｄ＃１〜ｙｄ＃ｍを符号化ビットｚｄ＃１〜ｚｄ＃ｍとして出力し、ｙｖａｌｉｄをｚｖａｌｉｄとして出力した後に、ｙｓｋｉｐをｙｓｋｉｐ１に上書きして保持する（ステップＳ９０４）。保持されたｙｓｋｉｐ１は、次の２値データが入力された際に利用される。ステップＳ９０３において、ｙｓｋｉｐ１を保持している場合には、先頭ビットであるｙｄ＃１の次にｙｄ＃１の反転値（＾ｙｄ＃１）を保持していたｙｓｋｉｐ１の数と同じ数だけ挿入する（ステップＳ９０５）。ステップＳ９０５の後、ｙｄ＃２〜ｙｄ＃ｍを加えた符号化ビットｚｄ＃１〜ｚｄ＃ｐを出力し、ｙｖａｌｉｄにｙｓｋｉｐ１を加えた数値をｚｖａｌｉｄとして出力した後に、ｙｓｋｉｐをｙｓｋｉｐ１に上書きして保持する（ステップＳ９０６）。例えば、図８（ｂ）に示すような２値データ列が入力され、ｙｓｋｉｐ１＝３であった場合は、ｙｄ＃１の次に１の反転値「０」が３個挿入され、「１００００１００」となる。
【００６６】
＜２値算術符号化部における具体的な処理の流れについての説明＞
図１〜図９を用いて説明した２値算術符号化部３における処理の具体的な流れについて説明する。ここで、２値算術処理部３１１から出力されるＲａｎｇｅとＬｏｗは、Ｒａｎｇｅ＝１，Ｌｏｗ＝５であり、Ｒａｎｇｅの最大値＝１０２４，Ｑｕａｒｔｅｒ＝２５６，Ｈａｌｆ＝５１２，不確定値Ｂ＝０（ゼロ）とする。
【００６７】
図２に示す第１のＲＳ部３１２ａにＬｏｗ＝５が入力されると、図３に示すステップＳ３０１→ステップＳ３０２と進み、ｘＬｏｗ＃１＝１０，ｘｄ＃１＝０が出力される。第２のＲＳ部３１２ｂでは、ｘＬｏｗ＃１＝１０が入力され、ｘＬｏｗ＃２＝２０，ｘｄ＃２＝０が出力される。以下、第３のＲＳ部では、ｘＬｏｗ＃３＝４０，ｘｄ＃３＝０が出力され、第４のＲＳ部では、ｘＬｏｗ＃４＝８０，ｘｄ＃４＝０が出力され、第５のＲＳ部では、ｘＬｏｗ＃５＝１６０，ｘｄ＃５＝０が出力され、第６のＲＳ部では、ｘＬｏｗ＃６＝３２０，ｘｄ＃６＝０が出力され、第７のＲＳ部では、ステップＳ３０１→ステップＳ３０３→ステップＳ３０５と進み、ｘＬｏｗ＃７＝１２８，ｘｄ＃７＝ｆが出力され、第８のＲＳ部では、ｘＬｏｗ＃８＝２５６，ｘｄ＃８＝０が出力され、３値データｘｄ＃１〜ｘｄ＃８は００００００ｆ０となる。そして、各ＲＳ部から出力されたｘＬｏｗ＃ｅは、ＳＬ部３１３に入力される。ＳＬ部３１３では、図４に示すステップＳ４０１において、Ｒａｎｇｅを７ビット（＝８−１）左シフトした第１のシフト値とＱｕａｒｔｅｒとを比較する。この場合、第１のシフト値は１２８となり、Ｑｕａｒｔｅｒよりも小さいので、ステップＳ４０２に進み、３値データｘｄ＃１〜ｘｄ＃８の全てが有効とされて、ｘＲａｎｇｅ＝２５６，ｘＬｏｗ＝２５６が出力される。
【００６８】
３値データｘｄ＃１〜ｘｄ＃８と、この３値データｘｄ＃１〜ｘｄ＃８の全てが有効であることを示すｘｖａｌｉｄは、３値データ格納部３４を介して２値変換部３２に入力される。ｘｄ＃１は確定値であり先頭の値であるため、図６に示すステップＳ６０１→ステップＳ６０２→ステップＳ６０３と進み、ｙｄ＃１＝０、以下、ｙｄ＃２＝０、ｙｄ＃３＝０、ｙｄ＃４＝０、ｙｄ＃５＝０、ｙｄ＃６＝０となる。ｘｄ＃７はｆであるため、ステップＳ６０１→ステップＳ６０５→ステップＳ６０６→ステップＳ６０７と進み、ｙｄ＃７＝０となる。ｘｄ＃８は０であるため、ステップＳ６０１→ステップＳ６０２と進み、ｘｄ＃７がｆであるため、ステップＳ６０４に進み、ｙｄ＃８＝１となる。従って、２値データｙｄ＃１〜ｙｄ＃８は０００００００１となる。また、２値データ列の不確定値数を示すｙｓｋｉｐは０（ゼロ）となり、２値データ列の有効範囲を示すｙｖａｌｉｄは、ｘｖａｌｉｄからｙｓｋｉｐを引いた８個であることを示す値を出力する。
【００６９】
２値変換部３２から出力された２値データｙｄ＃１〜ｙｄ＃８と、ｙｖａｌｉｄと、ｙｓｋｉｐとは、２値データ格納部３５を介してｆ値滞留処理部３３に入力される。有効な２値データがあるため、図９に示すステップＳ９０１→ステップＳ９０３に進み、ｙｓｋｉｐ１を保持していないため、ステップＳ９０４に進み、２値データｙｄ＃１〜ｙｄ＃８をそのまま符号化ビットとして出力し、ｙｓｋｉｐは０（ゼロ）であるため、０（ゼロ）をｙｓｋｉｐとして上書きする。
【００７０】
以上の処理によって、符号化ビット「０００００００１」、ｘＲａｎｇｅ＝２５６、ｘＬｏｗ＝２５６が出力される。
【００７１】
＜効果についての説明＞
所定の画像の１マクロブロックを再正規化した際のクロックサイクルは、従来の２値算術符号化装置の場合には１９，２００サイクルであったが、本実施の形態における２値算術符号化装置の場合には、３，２００サイクルであった。これにより、再正規化処理に要する時間を大幅に短縮することができ、リアルタイム処理の高画質化が可能となる。
【００７２】
最後に、本実施の形態で説明した２値算術符号化装置は、コンピュータで構成され、各処理はプログラムで実行される。また、各処理をプログラムとして、例えば、ＣＤやＦＤなどの記録媒体に記録して、この記録媒体をコンピュータに組み込んだり、または記録媒体に記録されたプログラムを通信回線を介してコンピュータにダウンロードしたり、または記録媒体からインストールし、プログラムでコンピュータを動作させることにより、上述した機能を処理させることができるのは勿論であり、このような記録媒体を用いることにより、その流通性を高めることができるものである。
【００７３】
本実施の形態によれば、対象ビットに対する３値データ列を出力するタイミングで、更新後の符号化区間幅と更新後の劣勢確率の区間幅とを出力するので、２値変換部３２とｆ値滞留処理部３３とにより３値データ列を２値データ列に変換して符号化ビットを出力する間に、２値算術再正規化手段により次のビットに対する２値算術符号化の処理が可能となる。即ち、２値算術符号化に要するクロックサイクルを少なくするため、高画質でリアルタイム処理が可能な２値算術符号化装置を提供することができる。
【図面の簡単な説明】
【００７４】
【図１】本実施の形態の係る２値算術符号化装置の構成を示すブロック図である。
【図２】２値算術再正規化部の構成を示すブロック図である。
【図３】第１〜第ｎのＲＳ部における処理の流れを示すフロー図である。
【図４】ＳＬ部における処理の流れを示すフロー図である。
【図５】２値変換部の構成を示すブロック図である。
【図６】２値算出処理部における処理の流れを示すフロー図である。
【図７】２値算出処理部の構成を示すブロック図である。
【図８】２値算術再正規化部から出力された３値データが、２変換部により２値データに変換された具体例を示す図である。
【図９】ｆ値滞留処理部における処理の流れを示すフロー図である。
【図１０】ＣＡＶＬＣを用いた従来の２値算術符号化装置の構成を示すブロック図である。
【図１１】従来の２値算術処理部における処理の流れを示すフロー図である。
【図１２】再正規化部における処理の流れを示すフロー図である。
【図１３】ビット出力の処理の流れを示すフロー図である。
【符号の説明】
【００７５】
３…２値算術符号化部
３１…２値算術再正規化部
３２…２値変換部
３３…ｆ値滞留処理部
３４…３値データ格納部
３５…２値データ格納部
３１１…２値算術処理部
３１２ａ〜３１２ｎ…第１〜第ｎのＲＳ部
３１３…ＳＬ部
３１５…再正規化部
３２１…２値算出処理部
３２２…有効性算出部
【図１】
0004382840.tif 000002
【図２】
0004382840.tif 000003
【図３】
0004382840.tif 000004
【図４】
0004382840.tif 000005
【図５】
0004382840.tif 000006
【図６】
0004382840.tif 000007
【図７】
0004382840.tif 000008
【図８】
0004382840.tif 000009
【図９】
0004382840.tif 000010
【図１０】
0004382840.tif 000011
【図１１】
0004382840.tif 000012
【図１２】
0004382840.tif 000013
【図１３】
0004382840.tif 000014