(57)【要約】【課題】高速に符号化を行うことができる符号化方法、符号化装置、プログラム、および記録媒体を提供する。【解決手段】符号化装置１は、符号化対象シンボルが優勢確率シンボルであり、ＬＳＺ検知部１０ａによって推定ＬＰＳインターバル（ＬＳＺ）が０．２５以下であり、かつ、現在のＬＳＺが直前のＬＳＺと同一である（あるいは、符号化対象のシンボルが全シンボル列の最初のシンボルまたは一括符号化直後のシンボルである）か否かをチェックする一括チェック部１０ｂと、チェックの結果、条件を満たしていればシンボルを一括して符号化するＭＵＬＭＰＳ１処理部９ｄとを備える。【選択図】  図１
2005348155.tif 000002
【特許請求の範囲】
【請求項１】
シンボル列を、各シンボルを順次に符号化対象とし、優勢確率シンボルおよび劣勢確率シンボルの出現確率に基づいて符号化する算術符号化方法において、
「符号化対象シンボルが、優勢確率シンボルである」という第１の条件と、「符号化対象シンボルにおける劣勢確率シンボルのインターバルが、閾値以下である」という第２の条件と、「符号化対象シンボルにおける劣勢確率シンボルのインターバルが、符号化対象シンボルの直前のシンボルにおける劣勢確率シンボルのインターバルと同一であるか、あるいは、符号化対象のシンボルが、全シンボル列の最初のシンボルまたは一括符号化直後のシンボルである」という第３の条件とが何れも満たされるか否かを判定する第１の判定ステップと、
上記第１の判定ステップにおいて第１〜３の条件の何れかが満たされないと判定されたシンボルを個別に符号化し、上記第１の判定ステップにおいて第１〜３の条件の何れもが満たされると判定されたシンボルの符号化を省略する第１の符号化ステップと、
第１の符号化ステップで符号化を省略したシンボルを一括して符号化する第１の一括符号化ステップとを含むことを特徴とする算術符号化方法。
【請求項２】
上記第１の一括符号化ステップは、
一括して符号化すべきシンボルの数と、符号化対象シンボルにおけるインターバルとに基づいて、一括して符号化すべきシンボルを順次符号化した場合に発生する正規化の回数を算出し、その算出した正規化回数に等しい回数だけ正規化を繰り返す第１の一括正規化ステップを含むことを特徴とする請求項１に記載の算術符号化方法。
【請求項３】
シンボル列を、各シンボルを順次に符号化対象とし、優勢確率シンボルおよび劣勢確率シンボルの出現確率に基づいて符号化する算術符号化方法において、
上記劣勢確率シンボルのインターバルに下限値が存在し、
「符号化対象シンボルが、優勢確率シンボルである」という第１の条件と、「符号化対象シンボルにおける劣勢確率シンボルのインターバルが、閾値以下である」という第２の条件と、「符号化対象シンボルがシンボル列の２番目以降のシンボルであり、かつ、符号化対象シンボルにおける劣勢確率シンボルのインターバルが、符号化対象シンボルの直前のシンボルにおける劣勢確率シンボルのインターバルと同一であるか、あるいは、符号化対象のシンボルが、全シンボル列の最初のシンボルまたは一括符号化直後のシンボルである」という第３の条件とが何れも満たされるか否かを判定する第１の判定ステップと、
「符号化対象シンボルが、優勢確率シンボルである」という第１の条件と、「符号化対象シンボルにおける劣勢確率シンボルのインターバルが、下限値である」という第４の条件との両方が満たされるか否かを判定する第２の判定ステップと、
上記第１の判定ステップにおいて第１〜３の条件の何れかが満たされないと判定され、かつ、第２の判定ステップにおいて第１および第４の条件の何れかが満たされないと判定されたシンボルを個別に符号化し、上記第１の判定ステップにおいて第１〜３の条件の何れもが満たされると判定されたシンボル、および上記第２の判定ステップにおいて第１および第４の条件の何れもが満たされると判定されたシンボルの符号化を省略する第２の符号化ステップと、
第２の符号化ステップで符号化を省略したシンボルを一括して符号化する第２の一括符号化ステップとを含むことを特徴とする算術符号化方法。
【請求項４】
上記第２の一括符号化ステップは、
一括して符号化すべきシンボルの数と、符号化対象シンボルにおけるインターバルおよび劣勢確率シンボルのインターバルとに基づいて、一括して符号化すべきシンボルを順次符号化した場合に発生する正規化の回数を算出し、その算出した正規化回数に等しい回数だけ正規化を繰り返す第２の一括正規化ステップを含むことを特徴とする請求項３に記載の算術符号化方法。
【請求項５】
上記閾値が、０．２５以下であることを特徴とする請求項１または３に記載の算術符号化方法。
【請求項６】
上記シンボル列が、複数の画素の値を示す複数のシンボルからなる画像データであり、
上記推定ステップにおいて、符号化対象シンボルの劣勢確率シンボルのインターバルを、上記符号化対象シンボルに対応する画素の近傍画素の値から推定し、
上記第１の判定ステップにおいて、「符号化対象シンボルの劣勢確率シンボルのインターバルを推定するのに用いられる近傍画素のパターンが、符号化対象シンボルの直前にあるシンボルの劣勢確率シンボルのインターバルを推定するのに用いられた近傍画素のパターンと同一であるか、あるいは、符号化対象のシンボルが、全シンボル列の最初のシンボルまたは一括符号化直後のシンボルである」という条件を第３の条件として用いることを特徴とする請求項１または３に記載の算術符号化方法。
【請求項７】
算術符号化の実装形態が、ＱＭ−ｃｏｄｅｒまたはＭＱ−ｃｏｄｅｒであることを特徴とする請求項１または３に記載の算術符号化方法。
【請求項８】
シンボル列を、各シンボルを順次に符号化対象とし、優勢確率シンボルおよび劣勢確率シンボルの出現確率に基づいて符号化する算術符号化装置において、
「符号化対象シンボルが、優勢確率シンボルである」という第１の条件と、「符号化対象シンボルにおける劣勢確率シンボルのインターバルが、閾値以下である」という第２の条件と、「符号化対象シンボルがシンボル列の２番目以降のシンボルであり、かつ、符号化対象シンボルにおける劣勢確率シンボルのインターバルが、符号化対象シンボルの直前のシンボルにおける劣勢確率シンボルのインターバルと同一であるか、あるいは、符号化対象のシンボルが、全シンボル列の最初のシンボルまたは一括符号化直後のシンボルである」という第３の条件とが何れも満たされるか否かを判定する第１の判定部と、
上記第１の判定部において第１〜３の条件の何れかが満たされないと判定されたシンボルを個別に符号化し、上記第１の判定部において第１〜３の条件の何れもが満たされると判定されたシンボルの符号化を省略する第１の符号化部と、
第１の符号化部で符号化を省略したシンボルを一括して符号化する第１の一括符号化部とを含むことを特徴とする算術符号化装置。
【請求項９】
シンボル列を、各シンボルを順次に符号化対象とし、優勢確率シンボルおよび劣勢確率シンボルの出現確率に基づいて符号化する算術符号化装置において、
上記劣勢確率シンボルのインターバルに下限値が存在し、
「符号化対象シンボルが、優勢確率シンボルである」という第１の条件と、「符号化対象シンボルにおける劣勢確率シンボルのインターバルが、閾値以下である」という第２の条件と、「符号化対象シンボルがシンボル列の２番目以降のシンボルであり、かつ、符号化対象シンボルにおける劣勢確率シンボルのインターバルが、符号化対象シンボルの直前のシンボルにおける劣勢確率シンボルのインターバルと同一であるか、あるいは、符号化対象のシンボルが、全シンボル列の最初のシンボルまたは一括符号化直後のシンボルである」という第３の条件とが何れも満たされるか否かを判定する第１の判定部と、
「符号化対象シンボルが、優勢確率シンボルである」という第１の条件と、「符号化対象シンボルにおける劣勢確率シンボルのインターバルが、下限値である」という第４の条件との両方が満たされるか否かを判定する第２の判定部と、
上記第１の判定部において第１〜３の条件の何れかが満たされないと判定され、かつ、第２の判定部において第１および第４の条件の何れかが満たされないと判定されたシンボルを個別に符号化し、上記第１の判定部において第１〜３の条件の何れもが満たされると判定されたシンボル、および上記第２の判定部において第１および第４の条件の何れもが満たされると判定されたシンボルの符号化を省略する第２の符号化部と、
第２の符号化部で符号化を省略したシンボルを一括して符号化する第２の一括符号化部とを含むことを特徴とする算術符号化装置。
【請求項１０】
請求項１〜７の何れかに記載の方法が含む各ステップをコンピュータに実行させるためのプログラム。
【請求項１１】
請求項１０記載のプログラムを記録したコンピュータ読み取り可能な記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、２値画像データや多値画像データ等を算術符号化する符号化方法、符号化装置、プログラムおよび記録媒体に関するものである。
【背景技術】
【０００２】
２値画像データをマルコフ情報源でモデル化し、符号化シンボルをその周辺画素の状態によって予測し、予測結果に応じて算術符号化する方式として、JBIG(ITU-T T.82)のQM-Coderが知られている（非特許文献１、２参照）。
【０００３】
このQM-Coderは、２値の入力信号（入力ビット）列を０以上１未満の実数ｘに変換する。入力信号に応じて、予め定めた手順で、圧縮結果である実数ｘの存在し得る範囲（以下ではインターバルと呼ぶ。）を変化させる。入力信号にも関わらずインターバルが変化しなくなった場合に、そのインターバルの最小値である低数を圧縮結果とする。
【０００４】
より詳細には、QM-Coderは、前回の入力信号までの入力列から次の（今回の）入力ビットの予測値（優勢確率シンボル(MPS)）を計算する。また、この予測に応じて、優勢確率シンボルの出現確率と予想されなかった方の劣勢確率シンボル(LPS)の出現確率との比に応じて、インターバルを２つの領域に分割する。優勢確率シンボルの出現確率に応じたMPSインターバルは、０により近い方の領域とする。また、0から遠い方の領域は、LPSの出現確率に応じたLPSインターバルとする。
【０００５】
入力ビットとMPSとが一致する場合には、現在のインターバルからLPSインターバルを取り除くように、インターバルを変化させる。一方、入力ビットとMPSとが一致しない場合には、現在のインターバルからMPSインターバルを取り除くように、インターバルを変化させる。全ての入力列に対する処理が完了したときのインターバルの低数を実数ｘとし、この実数ｘを圧縮結果とする。上述の処理手順によって、入力ビットが予想される入力ビットと一致する場合には、インターバルの低数に変化を生じない。このため、出力(圧縮結果)にも変化を生ずることがなく、新たなビットを出力する必要もないので、これを利用して圧縮を行う。
【０００６】
上述のような手順を行うにあたって、圧縮処理を実施していくと、インターバルの大きさが次第に小さくなり、やがて計算機の固定精度では表現できなくなってしまう。そこで、インターバルの大きさが0.5以上となるまで繰り返しインターバルの大きさを２倍にしていく、正規化処理と呼ばれる処理を行う。
【０００７】
ここで、QM-Coderにおいては、インターバルの大きさをメモリ領域のレジスタＡ（Areg）に保持し、インターバルの低数をメモリ領域のレジスタＣ(Creg)に保持する。また、0から1までのインターバルを、実装の際には、２１６（＝６５５３６）倍した値、すなわち0x0（＝０；"0x"は１６進数であることを表す）から0x10000（＝６５５３６）の１６ビットで表現する。この場合、レジスタＡには、大きさが0.5(0x8000)以上かつ１以下となるように正規化されたインターバルが入る。なお、レジスタＡに記憶される値が、正規化処理によって２倍にされる度に、レジスタＣに記憶される値も２倍とする。このため、レジスタＡの値を２倍化していることによる出力への影響は相殺される。
【０００８】
また、LPSインターバルを計算するには本来(インターバルの大きさ)×(LPS出現確率)という演算が必要であるが、QM-Coderの実装形態においては、このLPSインターバルの値を、統計的に求められた推定値(LSZ)によって近似する。
【０００９】
以上をまとめると、QM-Coderの実装形態においては、入力としてMPSが与えられた際にはインターバルからLSZを引き、入力としてLPSが与えられたときにはインターバルをLSZとする。また、この操作の結果インターバルが0.5以下となったときには正規化を行う。正規化が行なわれたときにはLSZの値を更新する。また、上述の操作によって、MPSインターバルよりもLPSインターバルの方が大きくなってしまう場合がある。このときは、MPSインターバルとLPSインターバルの入れ替えを行う。
【００１０】
図１９に示すように、JBIGのQM-Coderを実装した従来の符号化装置２１は、概略的に、コンテクスト生成部２２、取得部２３、算術符号部２４、記録部２５、レジスタ２６を備えている。この符号化装置２１における圧縮処理について、図２０に基づいて説明する。
【００１１】
符号化装置２１に画像データが入力されると、コンテクスト生成部２２が、入力画像を少なくとも１つ以上のストライプに分ける（Ｓ１５０）。このストライプとは、圧縮処理を行う単位であり、画像中の１ライン以上の横ラインからなる。Ｓ１５０〜Ｓ１６０におけるストライプについてのループ(LOOP＿A)によって、全てのストライプに対して処理が完了すると、画像全体の圧縮が完了する。
【００１２】
コンテクスト生成部２２は、圧縮対象となるセル（対象セル）を選択する（Ｓ１５１）。この対象セルの選択は、ストライプの左上から右下に向けて順次行う。Ｓ１５１〜Ｓ１６２のループにて対象セルについての圧縮を行い、ストライプの全ての画素の処理が完了すると１つのストライプの処理が完了したことになる。また、コンテクスト生成部２２は、入力された画像データから、対象セルの近傍セル（周辺画素）であるコンテクストを抽出し（読み取り）、取得部２３に送信する（Ｓ１５２）。また、コンテクスト生成部２２は、入力された画像データから、対象セルを読み取り、取得部２３に送信する（Ｓ１５２）。
【００１３】
取得部２３が、コンテクスト生成部２２から送信された対象セルおよびコンテクストに応じて、記録部２５の確率推定テーブル２７にアクセスして、コンテクストについての優勢確率シンボルおよび劣勢確率シンボルの確率推定値のインデックスSTを取得する（Ｓ１５３）。
【００１４】
算術符号部２４の前処理部３０では、選択部３０ａが、入力される対象セルの値とMPSとに応じて、対象セルがMPSであるか否かを判別する（Ｓ１５４）。Ｓ１５４において対象セルがMPSであると判別された場合には、算術符号部２４の符号処理部２９において、ＭＰＳ処理部２９ａがＭＰＳ処理（CODEMPS：Ｓ１５５〜Ｓ１５８）を行う。一方、Ｓ１５４において対象セルがLPSであると判別された場合には、算術符号部２４の符号処理部２９において、ＬＰＳ処理部２９ｂがＬＰＳ処理（CODELPS：Ｓ１５９〜Ｓ１６１）を行う。
【００１５】
ＭＰＳ処理部２９ａは、記録部２５の確率推定表２８にアクセスして、劣勢確率シンボルの確率推定値のインデックスＳＴを用いて、劣勢確率シンボルの確率推定値を取得し、これに応じてレジスタ２６のAreg２６ａ、Creg２６ｂを書き換える（Ｓ１５５）。ＭＰＳ処理部２９ａは、Areg２６ａの値が0.5未満であるか否かを判別して（Ｓ１５６）、0.5未満である場合にはＳ１５７に進み、0.5以上の場合にはＳ１６２に進む。Ｓ１５７ではＭＰＳ処理部２９ａがＲＥＮＯＲＭ処理部２９ｃに指示して、ＲＥＮＯＲＭ処理部２９ｃがレジスタ２６のAreg２６ａ、Creg２６ｂに対して正規化処理をして、得られた符号化データを必要に応じて出力する。ＭＰＳ処理部２９ａは、記録部２５の確率推定表２８を更新し（Ｓ１５８）、Ｓ１６２に進む。
【００１６】
一方、Ｓ１５９では、ＬＰＳ処理部２９ｂが、記録部２５の確率推定表２８にアクセスして、劣勢確率シンボルの確率推定値のインデックスＳＴを用いて、劣勢確率シンボルの確率推定値を取得し、これに応じてレジスタ２６のAreg２６ａ、Creg２６ｂを書き換える（Ｓ１５９）。Ｓ１６０では、ＬＰＳ処理部２９ｂが、レジスタ２６のAreg２６ａ、Creg２６ｂに対して、確率推定表のSWITCHの値に応じて、ＬＰＳとＭＰＳの入れ替えと符号出力を行う。すなわち、ＬＰＳ処理部２９ｂは、LSZのインデックスに対応する確率推定表のSWITCHの値が１か否かによって、入れ替えを行うかどうかを判断する。ＬＰＳ処理部２９ｂは、記録部２５の確率推定表２８を更新し（Ｓ１６１）、Ｓ１６２に進む。
【００１７】
Ｓ１６２では、符号処理部２９がコンテクスト生成部２２に対してセルインクリメントの指示を行い、セルについてのループを終了する。このような手順をストライプの全てのセルに対して行うことで、ストライプの圧縮を行う。Ｓ１６３では、ストライプについての処理が終了したか否かを判別し、終了していた場合にはレジスタ２６から符号化データを出力する（フラッシュ処理：Ｓ１６３）。このように、次のストライプの圧縮に進む前に、ここまでの圧縮結果のうちで、まだ出力されていない部分を出力する。Ｓ１６４では、コンテクスト生成部２２が新たなストライプを選択する。全てのストライプの圧縮が完了すれば画像全体の圧縮が完了したことになり、入力画像データの全てを符号化した場合には、処理を終了する。
【００１８】
例えば、特許文献１および特許文献２には、コンテクストが特定のパターンとなり、かつ他の条件が一括符号化可能な条件を満たす場合に一括符号化を行う方法が記載されている。
【００１９】
また、特許文献３には、算術圧縮装置において、同一のコンテクストが連続し、かつ、ＭＰＳ符号の入力が連続する場合に、それらの符号を一括して圧縮する方法が記載されている。このとき、各シンボルの予測条件には変化がないため、予め定めたｎシンボル分、
（インターバル）−ｎ×（ＬＰＳインターバル）
という計算式により一括して符号化することができる。上記方法の例として、特許文献３の段落［００２６］〜［００７３］には、一括符号化の際に正規化が発生しないことを検知して、正規化の発生しない範囲でのみ一括符号化を行う方法が記載されている。また、特許文献３の段落［００７４］〜［００７７］には、正規化が発生しても一括符号化を行う方法が記載されている。
【００２０】
なお、本願発明者による先行出願、特願２００４−１８５６８（２００４年１月２７日出願；本件の出願時には未公開）の明細書および図面には、本願発明と関連する発明が記載されている。
【特許文献１】特開平５−６７９７８号公報（公開日：１９９３年３月１９日）
【特許文献２】特公平７−９５６９３号公報（公告日：１９９５年１０月１１日）  （特許文献１の公告公報）
【特許文献３】特開２０００−３５００４３公報（公開日：２０００年１２月１５日）
【非特許文献１】ITU-T(International Telecommunication Union Telecommunication standardization sector) WHITE BOOK ディジタル静止画像圧縮符号化関連勧告書(財団法人 新日本ITU協会) 勧告T.82
【非特許文献２】WTSC-93 (WORLD TELECOMMUNICATION STANDARDIZATION CONFERENCE), Helsinki, 1-12 MARCH 1993
【発明の開示】
【発明が解決しようとする課題】
【００２１】
特許文献１および特許文献２の方式では、正規化が発生すると劣勢確率シンボルの確率推定が変化するため、一括符号化を続けることはできない。すなわち、正規化処理がいつ発生するかによって一括符号化可能なセルの個数が制限されてしまう。そのため、特許文献１および特許文献３の方式は、劣勢確率シンボルの確率推定が変化するような適応型の算術符号化に適用した場合、一括符号化による高速化の効果が低い。
【００２２】
また、特許文献３の段落［００２６］〜［００７３］に記載されている方法では、正規化処理が発生しないｎシンボルの間にわたってしか正規化処理を行っていない。これは、上記方法では、一括符号化の途中で正規化処理が行われると、一括符号化の計算式
（インターバル）−ｎ×（ＬＰＳインターバル）
におけるＬＰＳインターバルが変化してしまい、一括符号化を続けることができないためである。それゆえ、上記方法は、一括符号化による高速化の効果が低い。また、特許文献２の段落［００２６］〜［００７３］に記載されている方法では、正規化処理が発生しないｎシンボルの間にわたって一括符号化するために、ｎシンボルの間にわたって正規化処理が発生しないことを検知する必要がある。このように正規化処理が発生しないことを検知するためには、インターバルからＬＰＳインターバルを何回引くと正規化が発生するか（何シンボルの符号化を行うと正規化が発生するか）を求める演算が、一括符号化をするたびに発生する。そのため、画像によっては高速化の効果が全く得られないか、逆に遅くなってしまう場合もある。
【００２３】
また、特許文献３の段落［００７４］〜［００７７］に記載されている方法は、正規化発生までのシンボル数を求める計算が複雑となるという問題点がある。すなわち特許文献３の段落［００７７］ではＡｒｅｇ，Ｑｅ（ｓ），0x8000を使ってｎ１の計算を行うと記述されているが、場合によって、一括符号化中に優勢確率シンボルの符号化時に優勢確率シンボルと劣勢確率シンボルとの入れ替えが発生する可能性がある。一括符号化中に優勢確率シンボルと劣勢確率シンボルとの入れ替えが発生すると、正規化と正規化との間にインターバルの低数（典型的にはＣレジスタに格納される値）が変化する。そのため、これを考慮した計算を行わなければならず、計算が非常に複雑なものとなる。実際に、これを考慮した計算を行った場合には、演算回路が非常に大きくなるか、一括符号化による高速化分を帳消しにするほどの計算時間がかかると考えられる。
【００２４】
本発明は、上記の問題点に鑑みてなされたものであり、その目的は、高速に符号化を行うことができる符号化方法、符号化装置、プログラム、および記録媒体を提供することにある。
【課題を解決するための手段】
【００２５】
本発明に係る算術符号化方法は、上記の課題を解決するために、シンボル列を、各シンボルを順次に符号化対象とし、優勢確率シンボルおよび劣勢確率シンボルの出現確率に基づいて符号化する算術符号化方法において、「符号化対象シンボルが、優勢確率シンボルである」という第１の条件と、「符号化対象シンボルにおける劣勢確率シンボルのインターバルが、閾値以下である」という第２の条件と、「符号化対象シンボルにおける劣勢確率シンボルのインターバルが、符号化対象シンボルの直前のシンボルにおける劣勢確率シンボルのインターバルと同一であるか、あるいは、符号化対象のシンボルが、全シンボル列の最初のシンボルまたは一括符号化直後のシンボルである」という第３の条件とが何れも満たされるか否かを判定する第１の判定ステップと、上記第１の判定ステップにおいて第１〜３の条件の何れかが満たされないと判定されたシンボルを個別に符号化し、上記第１の判定ステップにおいて第１〜３の条件の何れもが満たされると判定されたシンボルの符号化を省略する第１の符号化ステップと、第１の符号化ステップで符号化を省略したシンボルを一括して符号化する第１の一括符号化ステップとを含むことを特徴としている。
【００２６】
また、本発明に係る算術符号化装置は、上記の課題を解決するために、シンボル列を、各シンボルを順次に符号化対象とし、優勢確率シンボルおよび劣勢確率シンボルの出現確率に基づいて符号化する算術符号化装置において、「符号化対象シンボルが、優勢確率シンボルである」という第１の条件と、「符号化対象シンボルにおける劣勢確率シンボルのインターバルが、閾値以下である」という第２の条件と、「符号化対象シンボルがシンボル列の２番目以降のシンボルであり、かつ、符号化対象シンボルにおける劣勢確率シンボルのインターバルが、符号化対象シンボルの直前のシンボルにおける劣勢確率シンボルのインターバルと同一であるか、あるいは、符号化対象のシンボルが、全シンボル列の最初のシンボルまたは一括符号化直後のシンボルである」という第３の条件とが何れも満たされるか否かを判定する第１の判定部と、上記第１の判定部において第１〜３の条件の何れかが満たされないと判定されたシンボルを個別に符号化し、上記第１の判定部において第１〜３の条件の何れもが満たされると判定されたシンボルの符号化を省略する第１の符号化部と、第１の符号化部で符号化を省略したシンボルを一括して符号化する第１の一括符号化部とを含むことを特徴としている。
【００２７】
上記方法および上記装置によれば、上記第１の判定ステップにおいて第１〜３の条件の何れもが満たされると判定された場合のみ、すなわち閾値以下でかつ同一の劣勢確率シンボルインターバルが連続した場合にのみ、優勢確率シンボルを一括符号化するようになっている。そのため、インターバルから劣勢確率シンボルインターバルを引いて優勢確率シンボルインターバルを求める優勢確率シンボルの符号化処理を行ったときに、優勢確率シンボルインターバルがＬＰＳのインターバルより小さくなる可能性が低い。そのため、優勢確率シンボルインターバルと劣勢確率シンボルインターバルとの入れ替えを行う処理が必要となる可能性が低い。それゆえ、正規化と正規化との間にインターバルの低数が変化する可能性が低い。それゆえ、何回目の正規化と何回目の正規化との間にインターバルの低数がどのように変化するかを求めなくとも、逐次符号化をシミュレーションすることができる。それゆえ、比較的少ない演算量で逐次符号化をシミュレーションすることができるので、より高速に符号化を行うことができる。
【００２８】
また、本発明の方法および装置は、先行出願である特願２００４−１８５６８の明細書および図面に記載されている方法および装置に対して、以下の利点を有している。
【００２９】
すなわち、特願２００４−１８５６８に記載されている方法および装置では、一括符号化を行うための条件として、劣勢シンボルのインターバルの推定値がその符号化形式での最小値となる必要がある。通常の算術圧縮では、優勢確率シンボルが連続すると、やがて劣勢シンボルのインターバルの推定値はその算術圧縮の実装形態で表現可能な最小値となり、優勢確率シンボルの入力が続く限りそれ以上変化しなくなる。そのため、一般的な算術圧縮では、十分な数の優勢確率シンボルが連続すれば一括圧縮可能な状態になる。しかし、劣勢シンボルのインターバルの推定値が最小値とならない部分では一括圧縮を行わないため、一部しか圧縮を高速化できない可能性がある。
【００３０】
これに対し、本発明の方法および装置では、劣勢確率シンボルのインターバルが最小でなくとも一括して符号化することができ、算術符号化をさらに高速化できる。
【００３１】
なお、本願明細書において、「正規化」とは、インターバルの大きさが０．５以上となるまでインターバルの大きさを２倍にする処理を（必要に応じて繰り返し）行うことを指すものとする。
【００３２】
上記方法において、第１の一括符号化ステップは、一括して符号化すべきシンボルの数と、符号化対象シンボルにおけるインターバルとに基づいて、一括して符号化すべきシンボルを順次符号化した場合に発生する正規化の回数を算出し、その算出した正規化回数に等しい回数だけ正規化を繰り返す第１の一括正規化ステップを含むことが好ましい。
【００３３】
上記方法によれば、正規化が発生する場合であっても一括符号化を行うことができるので、より多くのシンボルを一括符号化することができる。その結果、より高速に符号化を行うことができる。
【００３４】
本発明に係る算術符号化方法は、上記の課題を解決するために、シンボル列を、各シンボルを順次に符号化対象とし、優勢確率シンボルおよび劣勢確率シンボルの出現確率に基づいて符号化する算術符号化方法において、上記劣勢確率シンボルのインターバルに下限値が存在し、「符号化対象シンボルが、優勢確率シンボルである」という第１の条件と、「符号化対象シンボルにおける劣勢確率シンボルのインターバルが、閾値以下である」という第２の条件と、「符号化対象シンボルがシンボル列の２番目以降のシンボルであり、かつ、符号化対象シンボルにおける劣勢確率シンボルのインターバルが、符号化対象シンボルの直前のシンボルにおける劣勢確率シンボルのインターバルと同一であるか、あるいは、符号化対象のシンボルが、全シンボル列の最初のシンボルまたは一括符号化直後のシンボルである」という第３の条件とが何れも満たされるか否かを判定する第１の判定ステップと、「符号化対象シンボルが、優勢確率シンボルである」という第１の条件と、「符号化対象シンボルにおける劣勢確率シンボルのインターバルが、下限値である」という第４の条件との両方が満たされるか否かを判定する第２の判定ステップと、上記第１の判定ステップにおいて第１〜３の条件の何れかが満たされないと判定され、かつ、第２の判定ステップにおいて第１および第４の条件の何れかが満たされないと判定されたシンボルを個別に符号化し、上記第１の判定ステップにおいて第１〜３の条件の何れもが満たされると判定されたシンボル、および上記第２の判定ステップにおいて第１および第４の条件の何れもが満たされると判定されたシンボルの符号化を省略する第２の符号化ステップと、第２の符号化ステップで符号化を省略したシンボルを一括して符号化する第２の一括符号化ステップとを含むことを特徴としている。
【００３５】
また、本発明に係る算術符号化装置は、上記の課題を解決するために、シンボル列を、各シンボルを順次に符号化対象とし、優勢確率シンボルおよび劣勢確率シンボルの出現確率に基づいて符号化する算術符号化装置において、上記劣勢確率シンボルのインターバルに下限値が存在し、「符号化対象シンボルが、優勢確率シンボルである」という第１の条件と、「符号化対象シンボルにおける劣勢確率シンボルのインターバルが、閾値以下である」という第２の条件と、「符号化対象シンボルがシンボル列の２番目以降のシンボルであり、かつ、符号化対象シンボルにおける劣勢確率シンボルのインターバルが、符号化対象シンボルの直前のシンボルにおける劣勢確率シンボルのインターバルと同一であるか、あるいは、符号化対象のシンボルが、全シンボル列の最初のシンボルまたは一括符号化直後のシンボルである」という第３の条件とが何れも満たされるか否かを判定する第１の判定部と、「符号化対象シンボルが、優勢確率シンボルである」という第１の条件と、「符号化対象シンボルにおける劣勢確率シンボルのインターバルが、下限値である」という第４の条件との両方が満たされるか否かを判定する第２の判定部と、上記第１の判定部において第１〜３の条件の何れかが満たされないと判定され、かつ、第２の判定部において第１および第４の条件の何れかが満たされないと判定されたシンボルを個別に符号化し、上記第１の判定部において第１〜３の条件の何れもが満たされると判定されたシンボル、および上記第２の判定部において第１および第４の条件の何れもが満たされると判定されたシンボルの符号化を省略する第２の符号化部と、第２の符号化部で符号化を省略したシンボルを一括して符号化する第２の一括符号化部とを含むことを特徴としている。
【００３６】
上記方法および装置によれば、前記の方法および装置と同様に、劣勢確率インターバルが閾値以下で、かつ、同一の劣勢確率シンボルのインターバルが連続する場合に、第１の一括符号化処理を行うのに加えて、劣勢確率インターバルが最小値となった後は、第１の一括符号化と異なる第２の一括符号化処理を行うことができる。この第２の一括符号化処理は、劣勢確率インターバルの値が既知であることから、第１の一括符号化処理と比較して簡素な演算で実現できる。それゆえ、符号化をより高速化することができる。
【００３７】
上記方法において、第２の一括符号化ステップは、一括して符号化すべきシンボルの数と、符号化対象シンボルにおけるインターバルおよび劣勢確率シンボルのインターバルとに基づいて、一括して符号化すべきシンボルを順次符号化した場合に発生する正規化の回数を算出し、その算出した正規化回数に等しい回数だけ正規化を繰り返す第２の一括正規化ステップを含むことが好ましい。
【００３８】
上記方法によれば、正規化が発生する場合であっても第２の一括符号化ステップを実行することができるので、より多くのシンボルを一括符号化することができる。その結果、より高速に符号化を行うことができる。
【００３９】
本発明の算術符号化方法においては、上記閾値が、０．２５以下であることが好ましい。
【００４０】
上記方法によれば、インターバルから劣勢確率シンボルインターバルを引いて優勢確率シンボルインターバルを求める優勢確率シンボルの符号化処理を行ったときに、優勢確率シンボルインターバルが、必ずＬＰＳのインターバルより小さくなる。そのため、優勢確率シンボルインターバルと劣勢確率シンボルインターバルとの入れ替えを行う処理が決して必要とならない。それゆえ、正規化と正規化との間にインターバルの低数が変化することがない。それゆえ、何回目の正規化と何回目の正規化との間にインターバルの低数がどのように変化するかを求めなくとも、逐次符号化をシミュレーションすることができる。それゆえ、比較的少ない演算量で逐次符号化をシミュレーションすることができるので、より高速に符号化を行うことができる。
【００４１】
また、上記方法において、１回の正規化で発生する２倍化処理は１回となる。そのため、正規化の回数と２倍化処理の回数とが一致し、正規化に係わる演算を行いやすくなる。
【００４２】
本発明の算術符号化方法においては、上記シンボル列が、複数の画素の値を示す複数のシンボルからなる画像データであり、上記推定ステップにおいて、符号化対象シンボルの劣勢確率シンボルのインターバルを、上記符号化対象シンボルに対応する画素の近傍画素の値から推定し、上記第１の判定ステップにおいて、「符号化対象シンボルの劣勢確率シンボルのインターバルを推定するのに用いられる近傍画素のパターンが、符号化対象シンボルの直前にあるシンボルの劣勢確率シンボルのインターバルを推定するのに用いられた近傍画素のパターンと同一であるか、あるいは、符号化対象のシンボルが、全シンボル列の最初のシンボルまたは一括符号化直後のシンボルである」という条件を第３の条件として用いることが好ましい。
【００４３】
上記方法では、符号化対象シンボルの劣勢確率シンボルのインターバルを、上記符号化対象シンボルに対応する画素の近傍画素の値から推定し、この推定値を用いて第３の条件にかかる判定を行うので、劣勢確率シンボルのインターバルを比較的少ない演算量で求めることができる。それゆえ、より高速に符号化を行うことができる。
【００４４】
本発明の算術符号化方法においては、算術符号化の実装形態が、ＱＭ−ｃｏｄｅｒまたはＭＱ−ｃｏｄｅｒであることが好ましい。
【００４５】
上記方法によれば、算術符号化の実装形態が、ＱＭ−ｃｏｄｅｒまたはＭＱ−ｃｏｄｅｒであるので、通常のＱＭ−ｃｏｄｅｒまたは通常のＭＱ−ｃｏｄｅｒによって復号化が可能な符号化データを得ることができる。
【００４６】
また、上記方法において、第２の判定ステップを含み、算術符号化の実装形態がＱＭ−ｃｏｄｅｒである場合には、符号化対象シンボルの劣勢確率シンボルのインターバルの値が下限値であることを、ＱＭ−ｃｏｄｅｒの確率推定表における劣勢確率シンボルのインターバル（推定値）のインデックスが１３であることによって判定できる。そのため、そのインデックスの値が１３かどうかを調べるだけで、ＬＰＳの確率推定値が最小であることを知ることができ、処理を減らすことができる。
【００４７】
また、上記方法において、第２の判定ステップを含み、算術符号化の実装形態がＭＱ−ｃｏｄｅｒである場合には、符号化対象シンボルの劣勢確率シンボルのインターバルの値が下限値であることを、ＭＱ−ｃｏｄｅｒの確率推定表における劣勢確率シンボルのインターバル（推定値）のインデックスが４５であることによって判定できる。そのため、そのため、そのインデックスの値が４５かどうかを調べるだけで、ＬＰＳの確率推定値が最小であることを知ることができ、処理を減らすことができる。
【００４８】
なお、本発明に係る算術符号化方法は、本発明に係る算出符号化装置によって実行することが好ましい。さらに、本発明に係る算術符号化方法は、好ましくは、本発明に係る算出符号化装置を用いた方法であって、前記第１の判定部によって実行される前記第１の判定ステップと、前記第１の符号化部によって実行される前記第１の符号化ステップと、前記第１の一括符号化部によって実行される第１の一括符号化ステップとを含むことが好ましい。また、本発明に係る算術符号化方法は、好ましくは、本発明に係る算出符号化装置を用いた方法であって、前記第１の判定部によって実行される前記第１の判定ステップと、前記第２の判定部によって実行される前記第２の判定ステップと、前記第２の符号化部によって実行される前記第２の符号化ステップと、前記第２の一括符号化部によって実行される第２の一括符号化ステップとを含むことが好ましい。
【発明の効果】
【００４９】
本発明は、以上のように、上記第１の判定ステップにおいて第１〜３の条件の何れもが満たされると判定された場合のみ、すなわち閾値以下でかつ同一の劣勢確率シンボルインターバルが連続した場合にのみ、優勢確率シンボルを一括符号化するようになっているので、優勢確率シンボルインターバルと劣勢確率シンボルインターバルとの入れ替えを行う処理を省くことができる。それゆえ、何回目の正規化と何回目の正規化との間にインターバルの低数がどのように変化するかを求めなくとも、逐次符号化をシミュレーションすることができる。それゆえ、比較的少ない演算量で逐次符号化をシミュレーションすることができる。したがって、本発明は、高速に符号化を行うことができる符号化方法および符号化装置を提供できるという効果を奏する。
【発明を実施するための最良の形態】
【００５０】
〔算術符号化方法の概略〕
本発明に係る算術符号化方法の実施の一形態の概略を説明する。ここでは、算術符号化の対象となるシンボル列が、画素の値をそれぞれが示す複数のビットからなる２値画像データであり、算術符号化の実装形態が、ＱＭ−ｃｏｄｅｒである場合について説明する。
【００５１】
本実施形態に係る算術符号化方法は、２値画像データを構成する複数のビットを、各ビットを順次に符号化対象シンボルとし、優勢確率シンボルおよび劣勢確率シンボルの出現確率に基づいて符号化する算術符号化方法である。本実施形態に係る算術符号化方法は、符号化対象シンボルの劣勢確率シンボル（以下、ＬＰＳと略記する）のインターバルを、上記符号化対象ビットに対応する画素の近傍にある複数の近傍画素の値から推定する推定ステップと、「符号化対象シンボルが、優勢確率シンボル（以下、ＭＰＳと略記する）である」という第１の条件と、「符号化対象シンボルにおけるＬＰＳのインターバルが、０．２５（２１６倍した場合、すなわち0x0〜0x10000の１６ビットで表現した場合に、0x4000となる値）以下である」という第２の条件と、「符号化対象シンボルのＬＰＳのインターバルを推定するのに用いられる近傍画素のパターン（コンテクストとも呼ばれる；以下、「近傍形」と称する）が、符号化対象シンボルの直前にあるシンボルの近傍形と同一であるか、あるいは、符号化対象のシンボルが、全シンボル列の最初のシンボルまたは一括符号化直後のシンボルである」という第３の条件とが何れも満たされるか否かを判定する第１の判定ステップと、上記第１の判定ステップにおいて第１〜３の条件の何れかが満たされないと判定されたシンボルを個別に符号化し、上記第１の判定ステップにおいて第１〜３の条件の何れもが満たされると判定されたシンボルの符号化を省略する第１の符号化ステップと、第１の符号化ステップで符号化を省略したシンボルを一括して符号化する第１の一括符号化ステップとを含む方法である。
【００５２】
この方法では、推定ステップにて推定された符号化対象シンボルにおけるＬＰＳのインターバル（劣勢シンボルの推定出現確率；以下、「推定ＬＰＳインターバル」と称する）が最小でなくとも、一括して符号化（圧縮）することができる。ただし、この方法では、一度の一括符号化で符号化することのできるシンボルは１種類の近傍形を持つものに限られる。つまり、同じ近傍形を持つシンボルが連続して出現する場合に限って符号化を高速化することができる。注意すべきなのは、同じ近傍形を持つシンボルが連続して出現する場合に限って一括符号化を行うというのは、あくまで複数の近傍形を持つシンボルが混在しているようなシンボル列の部分を一括で符号化できないというだけである。特定の近傍形、例えば近傍画素の値が全て０である近傍形を持つシンボルが連続していなければ一括符号化できないなどということはない。どのような近傍形であっても、同じ近傍形を持つシンボルが連続しており、ＭＰＳが連続して出現しており、符号化対象シンボルにおける推定ＬＰＳインターバルが０．２５以下であれば、一括符号化の対象とすることができる。
【００５３】
符号化中に、推定ＬＰＳインターバルが０．２５以下となるような近傍形を持つシンボルの入力としてＭＰＳが与えられ、かつ、同じ近傍形を持つシンボルが連続した場合に、通常の算術符号化手順で画素の値（シンボル）を１画素（セル）ずつ符号化する方法から、一括符号化に切り替える。
【００５４】
具体的には、符号化対象の画素の値（シンボル）とその近傍形とを次々と読んでいき、符号化対象の画素の値がＬＰＳであるか、あるいは、符号化対象の画素の推定ＬＰＳインターバルが０．２５より大きければ、そこまでのシンボルの一括符号化を行う。符号化対象の画素の値がＭＰＳであり、かつ、符号化対象の画素の推定ＬＰＳインターバルが０．２５以下であれば、符号化対象の画素の値（シンボル）およびその近傍形が、直前の符号化対象の画素の値（シンボル）およびその近傍形と一致するかどうかを調べる。一致するならば、符号化対象画素の符号化をスキップ（省略）し、一括符号化するべき画素の数（典型的には一括符号化する画素の数をカウントする一括符号化画素カウンタの値）に１を加えて、次の符号化対象画素とその近傍形とを読み込む。一致しなければ、それより前の一括符号化するべき画素の数に等しい数の画素（まだ一括符号化されていない画素）の一括符号化を行うと共に、現在の符号化対象画素の符号化を行う。
【００５５】
一括符号化を行う時点の符号化対象画素より前の画素であって、一括符号化を行う対象となる画素の近傍形の種類を示す値（この場合、実装形態がＱＭ−ｃｏｄｅｒであるので、ＱＭ−ｃｏｄｅｒで規定された確率推定表における近傍形のインデックスＳＴの値）、インターバルの大きさ（典型的にはＡレジスタに格納される値）、およびＭＰＳの連続回数（典型的には一括符号化画素カウンタの値）が与えられれば、それらから、逐次符号化（通常の手順）によって符号化を行った場合の正規化発生回数と、一括符号化後のインターバルの大きさを求めることが可能となる。逐次符号化した場合の正規化発生回数が分かれば、まとめて正規化を行うこと（一括正規化）で、逐次に正規化を行った場合と同じ出力を行うことが可能となる。つまり、一括符号化および一括正規化によって逐次符号化および逐次正規化（通常の手順）をシミュレーションすることが可能となる。
【００５６】
推定ＬＰＳインターバルが０．２５以下の場合にのみ、近傍形が同一で連続するＭＰＳを一括符号化することで、このシミュレーションが容易に可能となっている。すなわち、推定ＬＰＳインターバルが０．２５以下の場合にのみ、近傍形が同一で連続する優勢確率シンボルをエンコードした場合には、インターバルから推定ＬＰＳインターバルを引いてＭＰＳのインターバルを求めたときに、ＭＰＳのインターバルがＬＰＳのインターバルより小さくなることがない。そのため、ＭＰＳとＬＰＳとの入れ替えが決して発生しない。それゆえ、インターバルの低数（典型的にはＣレジスタに格納される値）は２倍化される以外には決して変化することはなく、しかもインターバルの低数が２倍化されるのは、正規化のときにインターバルの大きさを２倍化するときだけである。したがって、正規化と正規化との間にインターバルの低数が変化しない。
【００５７】
もし正規化と正規化との間にインターバルの低数が変化してしまうと、何回目の正規化と何回目の正規化との間にインターバルの低数がどのように変化するかを求めなければ、逐次符号化の動作をシミュレーションすることができない。そのため、まとめて正規化を行うこと（一括正規化）が容易にはできない。
【００５８】
本発明の方法では、正規化と正規化との間にインターバルの低数が変化しないので、このような不都合が生じることがなく、逐次符号化および逐次正規化の動作を一括符号化および一括正規化によってシミュレーションが可能となる。
【００５９】
さらに、推定ＬＰＳインターバルが０．２５以下の場合にのみ、優勢確率シンボルを符号化した場合には、一回の正規化で発生する２倍化処理は１度だけである。なぜなら、インターバルの大きさは０．５（２１６倍した場合に0x8000となる値）以上になるように正規化されているため、ＭＰＳを符号化するときにインターバルから０．２５以下の推定ＬＰＳインターバルを引けば、インターバルの大きさは必ず０．２５以上となる。そのため、インターバルの大きさは、必ず一度の２倍化処理で０．５以上となる。そのため、正規化の回数と２倍化処理の回数とが一致し、正規化に係わる演算を行いやすくなる。
【００６０】
特許文献１・２の方法や、特許文献３における正規化の起こらない範囲で一括符号化を行う方法では、正規化の起こらない範囲でしか一括符号化を行うことができなかった。また、先行出願である特願２００４−１８５６８の符号化方法では、ＬＰＳのインターバルが最小値であるとき（実装形態がＱＭ−ｃｏｄｅｒである場合、ＱＭ−ｃｏｄｅｒで規定された確率推定表における近傍形のインデックスＳＴがＳＴ＝１３の条件を満たすとき）しか一括符号化を行うことができなかった。
【００６１】
これらに対し、本発明による方法では、ＬＰＳのインターバルが０．２５以下という比較的緩い条件で一括符号化を行うことが可能となるので、一括符号化可能なシンボル数が増加し、符号化の高速化が実現できる。
【００６２】
さらに、この方法はＬＰＳのインターバルが最小値であるときに符号化を高速化する特願２００４−１８５６８の方法と併用することが可能である。また、本発明は、柔軟にさまざまな変形を行うことが可能であり、例えば、ハードウェア的な制約がある場合などには、あらかじめ決まった近傍形を持つＭＰＳが連続したときだけに一括符号化を行うように変更したり、あらかじめ同じ近傍形を持つＭＰＳが連続することが分かっている領域にのみ本発明の方法を用いるなどの応用が可能である。
【００６３】
〔実施の形態１〕
本発明の一実施形態について図１ないし図１３に基づいて説明すると以下の通りである。本実施形態および以降の実施形態では、算術符号化装置を構成する各部が、ＣＰＵなどの演算手段がＲＯＭやＲＡＭなどの記録媒体に格納されたプログラムコードを実行することで実現される機能ブロックである場合を例にして説明する。また、ここでは、算術符号化の実装形態が、ＱＭ−ｃｏｄｅｒである場合について説明する。
【００６４】
本実施形態は、本発明に係る符号化方法を、ITU-T(International Telecommunication Union Telecommunication standardization sector) WHITE BOOK ディジタル静止画像圧縮符号化関連勧告書(財団法人 新日本ＩＴＵ協会)勧告T.82に記載されている、ＪＢＩＧのＱＭ−Ｃｏｄｅｒに適用した場合の例である。
【００６５】
ＪＢＩＧのＱＭ−Ｃｏｄｅｒは、２値画像データをマルコフ情報源でモデル化し、符号化シンボルをその周辺画素の状態によって予測し、予測結果に応じて算術符号化する方式を用いている。ＪＢＩＧ圧縮はプログレッシブ方式を取っているが、ここでは、説明を簡単にするために最低解像度レイヤのみを持つＪＢＩＧ圧縮について扱う。また、説明を簡単にするため、コンテクストの形状を変化させるＡＴ(Adaptive Template)移動などＪＢＩＧの仕様に含まれる付加的な機能に関しては説明を省略する。
【００６６】
本実施形態に係る算術符号化装置１は、２値の画像データを算術符号化により圧縮し、それによって得られた圧縮画像データ（符号化データ）を出力する。この算術符号化装置１は、例えば図示しないパーソナルコンピュータのプリンタドライバにおける符号化圧縮部として機能する。このプリンタドライバは、パーソナルコンピュータの図示しない記憶部（記録媒体）に蓄積されたプログラムをパーソナルコンピュータのＣＰＵ(Central Processing Unit)が読み込んで実行することによって実現される。パーソナルコンピュータに対するユーザの指示に応じて、プリンタドライバは、印刷ドキュメントを画像に変換したデータを算術符号化装置１を用いてＪＢＩＧ圧縮して、プリンタ本体に送信する。プリンタ本体では、受信したＪＢＩＧ画像を復号して、印刷を行う。これによって、プリンタドライバにおける圧縮を高速化することができる。
【００６７】
算術符号化装置１における算術符号化について、図２に基づいて概略を説明する。算術符号化装置１は、算術符号化として、外部から入力された２値の画像データである入力ビット列（入力シンボル列）を０以上１未満の実数ｘに変換する。より詳細には、０以上１未満の半開区間を、入力ビット（入力シンボル）に応じて分割することにより、実数ｘに対応する半開区間（ｘ以上ｙ未満の区間）を求め、半開空間の下限値を符号結果とする。符号化結果である符号化データは、桁数の多い一つの小数となる。
【００６８】
ここで、符号化結果である実数ｘに対応する半開区間（実数ｘの存在し得る範囲）を、以下ではインターバルと呼ぶ。図２に示すように、まだ１ビット（１シンボル）も入力が行なわれていない時点では、明らかにインターバルは０以上１未満の領域となる。
【００６９】
このインターバルを、入力ビットに応じて、予め定めた手順で変化させる。全ての入力ビットに応じてインターバルを変化させた後におけるインターバルの下限値（最小値）である低数を符号化結果とする。算術符号化装置１において、インターバルは、インターバルの下限値である低数と、インターバルの大きさ（下限値と上限値との差）との組み合わせとして記憶されている。
【００７０】
より詳細には、算術符号化装置１は、次の（今回の）入力ビットを前回の入力ビットまでの入力ビット列、より詳細には周辺の画素（コンテクスト）の状態（周辺の画素に対応する複数の入力ビットの値の組み合わせ）から予測する。また、この予測に応じて、インターバルを２つの領域に分割する。算術符号化装置１は、予測の際に、周辺の画素がとりうる複数の状態のそれぞれから優勢確率シンボルおよび劣勢確率シンボルの出現確率を推定する機能を持つ。これにより、周辺の画素の状態から０または１のどちらのシンボルが出現しやすいかを判断する。
【００７１】
ここで、入力ビットに出現すると予想された入力値（入力シンボル）を優勢確率シンボル（ＭＰＳ）と呼ぶ。予想されなかった方の入力値（入力シンボル）を劣勢確率シンボル（ＬＰＳ）とする。また、予想とともに、優勢確率シンボルの出現確率と劣勢確率シンボルの出現確率との比に応じて、インターバルを２つの領域に分割し、一方の領域をＭＰＳインターバル、他方の領域をＬＰＳインターバルとする。優勢確率シンボルの出現確率に応じたＭＰＳインターバルは、０により近い方の領域とする。また、０から遠い方の領域は、ＬＰＳの出現確率に応じたＬＰＳインターバルとする。
【００７２】
入力ビット列（入力シンボル列）の符号化時には、各ビット（シンボル）の入力に応じて、入力ビット（入力シンボル）と優勢確率シンボル（ＭＰＳ）との比較を行う。入力ビットと優勢確率シンボル（ＭＰＳ）とが一致する場合には、現在のインターバルからＬＰＳインターバルを取り除くように、インターバルを変化させる。一方、入力ビットとＭＰＳとが一致しない場合には、現在のインターバルからＭＰＳインターバルを取り除くように、インターバルを変化させる。
【００７３】
一例として、入力ビット列（入力シンボル列）「０００１」であり、そのときの優勢確率シンボル（ＭＰＳ）が「０１０１」である場合の符号化処理を図２に基づいて説明する。２ビット目の入力（前から２つ目の入力シンボル）は劣勢確率シンボルであるから、その入力の符号化時には、ＬＰＳインターバルが符号化後の新たなインターバルとして選択される。すなわち、現在のインターバルからＭＰＳインターバルを取り除くようにインターバルを変化させることで、符号化が行われる。一方、２ビット目以外の入力（前から１つ目、３つ目、４つ目のシンボル）は優勢確率シンボルであるから、その入力の符号化時には、ＭＰＳインターバルが符号化後のインターバルとして選択される。すなわち、現在のインターバルからＬＰＳインターバルを取り除くようにインターバルを変化させることで、符号化が行われる。
【００７４】
ここで、全ての入力ビット列に対する処理が完了したときのインターバルの低数を実数ｘとし、この実数ｘを符号化結果とする。上述の処理手順によって、入力ビットが予想される入力ビット（優勢確率シンボル）と一致する場合には、インターバルの低数に変化を生じない。このため、出力（符号化結果）にも変化を生ずることがなく、新たなビットを出力する必要もないので、これを利用して符号化を行うことができる。なお、全ての入力ビットが優勢確率シンボルであれば符号化結果ｘは０となる。
【００７５】
上述のような手順を行うにあたって、ＱＭ−Ｃｏｄｅｒの動作を模倣している算術符号化装置１においては、以下の手順をさらに行う。すなわち、上述の算術符号化処理を実施していくと、インターバルの大きさが次第に小さくなる。このため、やがて計算機の固定精度では表現できなくなってしまう。そこで、インターバルの大きさが０．５以上となるまで繰り返しインターバルの大きさを２倍にしていく、正規化処理と呼ばれる処理を行う。
【００７６】
算術符号化装置１においては、インターバルの大きさを後述するレジスタ６内のレジスタＡ（以下、「Ａｒｅｇ」と記す）６ａに保持（記憶）し、インターバルの低数を後述するレジスタ６内のレジスタＣ（以下、「Ｃｒｅｇ」と記す）６ｂに保持（記憶）している。ここで、本実施形態では、インターバルを、実際の値を２１６倍した値、すなわち0x0〜0x10000の範囲の値で表現する。以下では、１６進表示の数字（"0x"を前に付けた数字）は、この表現による値である。したがって、１６進表示の数字を２１６で割った値が実際の値である。この場合、Ａｒｅｇ６ａには、０．５（"0x8000"で表わされる）以上かつ１（"0x10000"で表わされる）以下となるように正規化されたインターバルの大きさが格納される。
【００７７】
また、Ａｒｅｇ６ａに記憶される値Ａｒｅｇ（インターバルの大きさ）が、正規化処理によって２倍にされる度に、Ｃｒｅｇ６ｂに記憶される値Ｃｒｅｇ（インターバルの低数）も２倍とする。このため、Ａｒｅｇ６ａに記憶される値Ａｒｅｇを２倍化していることによる出力への影響は、相殺（キャンセル）される。また、Ｃｒｅｇ６ｂの値Ｃｒｅｇは、オーバーフローしないように、上位バイトが適時取り出され、符号化結果として出力されるようになっている。なお、この際に発生するキャリーオーバーを解決する方法がITU-T T.82に記載されているが、本発明の内容を理解する上で必須ではないため、ここでは説明を省略する。
【００７８】
また、算術符号化装置１においては、以下のような近似を行うようになっている。ＬＰＳインターバルを計算するには、本来は、（インターバルの大きさ）×（ＬＰＳ出現確率）という演算が必要である。算術符号化装置１においては、このＬＰＳインターバルの値を、統計的に求められた推定値（推定ＬＰＳインターバル；以下、適宜、「ＬＳＺ」と略記する）によって近似する。この近似では、その時点でのインターバルの大きさが１（"0x10000"）とは限らないということを考慮せずにインターバルの大きさが１であるものとみなし、ＬＰＳインターバルの値を、統計的な推定によって求められたＬＰＳの出現確率の推定値（ＬＳＺ）で近似する。そのため、インターバル全体のうち、推定ＬＰＳインターバルの占める割合は、インターバルの大きさに応じて変化してしまう。しかしながら、インターバルは大きさが０．５以上かつ１以下となるように正規化されているため、誤差はそれほど大きくはならない。
【００７９】
すなわち、上記の近似は、インターバル全体の大きさが０の出現確率と１の出現確率との合計であるものとみなして行うものであるから、本来はインターバル全体の大きさは１であるべきである。しかしながら、演算を行う都合上、インターバル全体の大きさを１にする処理は行わず、インターバル全体の大きさが０．５から１．０までの範囲におさまっていればよいこととしている。このため、インターバルの大きさが小さければ、インターバルからＬＰＳインターバルを引いてＭＰＳインターバルを求めたときに、ＬＰＳインターバルの大きさがＭＰＳインターバルの大きさより大きくなる可能性がある。
【００８０】
以上をまとめると、算術符号化装置１において、入力ビット（入力シンボル）としてＭＰＳが与えられた際にはインターバルからＬＳＺを引き、その結果得られた値を新たなインターバルとする。また、算術符号化装置１は、入力ビットとしてＬＰＳが与えられたときには、インターバルをＬＳＺに変更する。この操作によって、入力ビットが符号化される。算術符号化装置１は、この操作の結果としてインターバルが０．５以下となったときには正規化を行う。正規化が行われたときにはＬＳＺの値を更新する。また、上述の符号化によって、ＭＰＳインターバルよりもＬＰＳインターバルの方が大きくなってしまう場合がある。このときは、ＭＰＳインターバルとＬＰＳインターバルとの入れ替えを行なう。
【００８１】
ここで、上述のような算術符号化の手順を、計算機や電子回路などに実装する場合には、有限の計算精度でも符号化を行うことができるように、劣勢確率シンボルの推定出現確率（ＬＳＺ）には最小値を持たせるのが一般的である。算術符号化においては、符号化中に正規化が発生すると、劣勢確率シンボルの推定出現確率（ＬＳＺ）を減少させる。ただし、上述のような実装形態においては、既に劣勢確率シンボルの推定出現確率（ＬＳＺ）が最小になっていれば、それ以上劣勢確率シンボルの推定出現確率（ＬＳＺ）は減少しない。
【００８２】
次に、上述の符号化処理を行う算術符号化装置１の構成について、図１に基づいて詳細に説明する。本実施形態の算術符号化装置１は、図１に示すように、概略的に、コンテクスト生成部２、取得部３、算術符号化部４、記録部５、およびレジスタ（メモリ）６を備えている。この算術符号化装置１においては、上述の符号化処理を計算機上で実装するために、固定精度の整数演算で近似をしている。
【００８３】
コンテクスト生成部２は、入力画像データから、対象となる画素（セル）およびその周辺（近傍）の複数画素の配列であるコンテクストを抽出するものである。対象となる画素とコンテクストとの関係を、図３に基づいて説明する。上述のように、ＱＭ−ｃｏｄｅｒの動作を模倣した算術符号化装置１においては、予測の際に、前回の入力信号までの入力ビット列だけでなく、周辺の複数画素（コンテクスト）の状態をも用いるようになっている。すなわち、算術符号化装置１は、予測の際に、周辺の複数画素がとりうる状態の組み合わせそれぞれに対して、優勢確率シンボルおよび劣勢シンボルの出現確率を推定する機能を持つ。
【００８４】
ここで、今回の入力ビット（入力シンボル）である対象画素（符号化画素）を選択した場合に、この符号化画素の周辺の複数画素（コンテクスト）として、図３に示すように、符号化画素より前に処理された画像のうちで、符号化画素と同じラインおよびそれに隣接するライン（図３では１つ上のライン）における符号化画素の周辺に存在する複数画素（コンテクスト）を選択する。図３において、斜線部分が符号化対象となる対象画素であり、その周辺の１０個の四角がコンテクストの各画素を表している。なお、この場合、コンテクストの画素数は１０個であり、各画素の値（シンボル）は０または１の値を持つので、コンテクストの各画素がとりうる値の組み合わせの数は１０２４通りとなる。また、ＪＢＩＧ圧縮では、最低解像度レイヤのコンテクストとして、図３に示すような２ラインテンプレートの他に、３ラインテンプレートも用意されており、こちらを用いることもできる。ここでは２ラインテンプレートを用いるものとする。
【００８５】
コンテクスト生成部２は、抽出した画素およびコンテクストを取得部３に出力する。また、コンテクスト生成部２は、算術符号化部４の符号処理部９からの画素インクリメント指示を受信すると、入力画像データから、次の対象画素およびコンテクストを抽出する。
【００８６】
次に、取得部３について説明する。取得部３は、予測値としての優勢確率シンボル（ＭＰＳ）を、周辺画素の配列（コンテクスト）に対する優勢確率シンボルを記録した記録部５の確率推定テーブル７から取得する。
【００８７】
ここで、確率推定テーブル７は、図４に示すように、コンテクストと、そのコンテクストから予想されるＭＰＳの値との関係を含んでいる。また、確率推定テーブル７は、コンテクストと、このコンテクストに応じたＬＰＳインターバルの推定値（ＬＳＺ）のインデックスＳＴとの関係も含んでいる。ＬＳＺについては後述する。取得部３は、入力されるコンテクストを用いて、記録部５の確率推定テーブル７にアクセスして、インデックスＳＴを得る。取得部３は、ＭＰＳとインデックスＳＴとを得ると、画素の値（入力ビットの値；入力シンボル）、ＭＰＳ、インデックスＳＴを算術符号化部４に出力する。以上のように、符号化対象画素（符号化対象のビットに対応する画素）の近傍画素（コンテクスト）の値から符号化対象のビット（シンボル）のＬＰＳインターバル（この場合にはＬＰＳインターバルの推定値）を推定する推定ステップが、取得部３と確率推定テーブル７とによって実行される。すなわち、取得部３および確率推定テーブル７は、上記推定ステップを実行する推定部として機能する。
【００８８】
算術符号化部４は、入力される画素の値、ＭＰＳ、インデックスＳＴから、符号化データである実数ｘを生成する。この算術符号化部４は、符号処理部９および前処理部１０を含んでいる。
【００８９】
符号処理部９は、前処理部１０から入力される選択信号に応じて、各処理部９ａ〜９ｅのうちから適切な処理部を選択する。また入力された画素の値、ＭＰＳ、ＳＴを用いて、選択した処理部によって符号化データを生成する。符号処理部９は、優勢確率シンボルの符号化（第１の符号化ステップ）を行うＭＰＳ処理部（第１の符号化部）９ａ、劣勢確率シンボルの符号化を行うＬＰＳ処理部９ｂ、正規化処理を実行するＲＥＮＯＲＭ処理部９ｃ、後述するＭＵＬＭＰＳ１処理による一括符号化処理（第１の一括符号化ステップ）を実行するＭＵＬＭＰＳ１処理部（第１の一括符号化部）９ｄ、および一括正規化処理（第１の一括正規化ステップ）を実行するＭＵＬＲＥＮＯＲＭ処理部（第１の正規化部）９ｅを含んでいる。各処理部９ａ〜９ｅにおける処理の詳細については後述する。
【００９０】
前処理部１０は、取得部３から入力される画素の値、ＭＰＳ、ＳＴに応じて、選択信号を生成して、符号処理部９に出力する。前処理部１０は、ＬＳＺ検知部１０ａ、一括チェック部（第１の判定部）１０ｂ、選択部１０ｃ、および近傍形検知部１０ｄを含んでいる。
【００９１】
ＬＳＺ検知部１０ａは、ＬＰＳインターバルの推定値であるＬＳＺが０．２５以下となっているかを検知するものである。
【００９２】
一括チェック部１０ｂは、レジスタ６の第１の第１の一括符号化画素カウンタ６ｃのカウント値ｔが０を超えているか（１以上であるか）否かを判別するものである。一括チェック部１０ｂは、最小検知部１０ａおよび一括チェック部１０ｂ自身の判別結果を選択部１０ｃに出力する。
【００９３】
選択部１０ｃは、選択信号を生成するために、入力される画素の値（符号化対象のシンボル）と、そのコンテクストから予想されるＭＰＳとを比較し、符号化対象のシンボルが優勢確率シンボルか劣勢確率シンボルかを判断する。また、選択部１０ｃは、一括チェック部１０ｂの判別結果を受信する。選択部１０ｃは、入力に応じて選択信号を生成して、符号処理部９に出力する。選択部１０ｃの詳細な動作については後述する。
【００９４】
近傍形検知部１０ｄは、後述する近傍形記憶領域６ｄにアクセスし、近傍形記憶領域６ｄに一括符号化の対象となる画素の近傍形が記憶されていれば、それを読み出して現在の符号化対象の近傍形と一致するかを判定するものである。
【００９５】
記録部５には、確率推定テーブル７と確率推定表８とが記録されている。なお、確率推定テーブル７と確率推定表８とは、全く別のものである。テーブルは表とも訳し得るが、ITU-T T.82の日本語訳(ITU-T WHITE BOOK ディジタル静止画像圧縮符号化関連勧告書 勧告T.82)でこのようになっているため、その語句をそのまま用いることとする。
【００９６】
確率推定テーブル７は、コンテクストごとの優勢確率シンボルＭＰＳと、ＬＳＺのインデックスＳＴとを保存するテーブルである。本実施形態においては、コンテクストごとのＭＰＳ（１ビット）とＬＳＺのインデックスＳＴ（７ビット）とを保存している。このため、各コンテクストに対して１バイト（８ビット）の情報を有している。本実施形態のように、コンテクストが１０画素分の大きさを持つ場合には、２の１０乗個のコンテクストそれぞれに対して１バイトの大きさを有することになり、確率推定テーブル７全体は１０２４バイトとなる。この確率推定テーブル７は、符号化処理の間、書き換えが行なわれる。
【００９７】
より詳細には、確率推定テーブル７は、インデックスＳＴと優勢確率シンボルＭＰＳとを更新しながら符号化される。なお、一括符号化中には、インデックスＳＴの値、および優勢確率シンボルＭＰＳのどちらも変化しないので、確率推定テーブル７の書き換えは発生しない。一方、通常の符号化（逐次の符号化）中には、優勢確率シンボルまたは劣勢確率シンボルを符号化するたびにインデックスＳＴの値が変化するため、確率推定テーブル７の書き換えが生じる。また、ＬＰＳインターバルの大きさがＭＰＳインターバルの大きさを超えれば優勢確率シンボルと劣勢確率シンボルとが入れ替わるため、このときも確率推定テーブル７を書き換える。
【００９８】
なお、優勢確率シンボルは、０または１の値を取る。ＬＳＺのインデックスＳＴは、ＪＢＩＧにおいては、０から１１２までのどれかの値を取る。また、コンテクストが１０ビットである一方で、インデックスは７ビットであるので、同じインデックスをもつ異なるコンテクストが存在することになる。例えばコンテクスト“００００００００００”のＬＳＺのインデックスＳＴと、“０００００００００１”のＬＳＺのインデックスＳＴとが共に１３というようなことも起こり得る。このＬＳＺのインデックスＳＴは、後述するＪＢＩＧの確率推定表８において、近傍１０画素に出現した０または１の値（シンボル）の組合せ状況（コンテクスト）ごとに、これまで注目画素の位置に出現した値（シンボル）の履歴から注目画素に出現するであろう値（シンボル）の出現確率の予測を表すために用いられる。
【００９９】
一方、確率推定表８は、図５（ａ）（ｂ）に示すITU-T T.82の表２４のように、ＬＳＺのインデックスＳＴから、ＬＳＺや次のＳＴなどを求めるための表である。確率推定表８からＬＳＺを求めるために、確率推定テーブル７から得たＬＳＺのインデックスＳＴが使用される。この確率推定表８は、符号化処理の際にも書き換えられることはない。すなわち、確率推定表８は、参照されるだけで、書き換えられることはない。
【０１００】
ＬＳＺのインデックスＳＴは、確率推定テーブル７に関して説明したように、７ビットの情報である。本実施形態のようにＪＢＩＧ圧縮の場合には、インデックスＳＴのとり得る値は０から１１２までとなる。また、ＬＳＺは、上述のように、ＬＳＺのインデックスＳＴに応じた、劣勢確率シンボルのインターバル（の近似値）を意味する。また、ＮＬＰＳは、劣勢確率シンボルを符号化したとき（このときには必ず正規化が発生する）の次のインデックスＳＴの値を意味する。また、ＮＭＰＳは、優勢確率シンボルを符号化して正規化が発生したときの次のインデックスＳＴの値を意味する。したがって、正規化が発生したときには、インデックスＳＴの値がＮＬＰＳの値（劣勢確率シンボルを符号化した優勢確率シンボルを符号化した場合）またはＮＭＰＳの値（優勢確率シンボルを符号化した場合）に更新される。なお、正規化が発生しないときには、インデックスＳＴの値は更新されない。また、ＳＷＩＴＣＨは、優勢確率シンボルと劣勢確率シンボルとの入れ替えを行うかどうかのフラグを意味する。
【０１０１】
また、算術符号化装置１は、作業用メモリとしてのレジスタ６を備えている。このレジスタ６は、高速アクセス可能なメモリである。レジスタ６は、Ａｒｅｇ６ａ、Ｃｒｅｇ６ｂ、第１の一括符号化画素カウンタ６ｃ、近傍形記憶領域６ｄ、および出力ビットカウンタ６ｅを含んでいる。なお、図面中では、「第１の一括符号化画素カウンタ」を「第１画素カウンタ」と略記している。
【０１０２】
Ａｒｅｇ６ａは、インターバルの大きさの値Ａｒｅｇを保持（蓄積）するための記憶領域である。また、Ｃｒｅｇ６ｂは、インターバルの低数の値Ｃｒｅｇを保持する記憶領域である。Ａｒｅｇ６ａおよびＣｒｅｇ６ｂは、整数で固定精度である。
【０１０３】
第１の一括符号化画素カウンタ６ｃは、後述するＭＵＬＭＰＳ１処理による一括符号化を行う画素の数の値ｔをカウントするものである。第１の一括符号化画素カウンタ６ｃにおけるカウント値ｔの初期値はｔ＝０とする。この第１の一括符号化画素カウンタ６ｃのカウント値ｔは、一括チェック部１０ｂが変化させる。
【０１０４】
近傍形記憶領域６ｄは、一括符号化の対象となる画素の近傍形を記憶するものである。この近傍形は、近傍形検知部１０ｄによって参照される。
【０１０５】
出力ビットカウンタ６ｅは、Ｃｒｅｇ６ｂの空きビット数（上位側の「０」の数）である値ＣＴをカウントするためのカウンタである。この空きビット数は、Ｃｒｅｇ６ｂに格納される出力（値Ｃｒｅｇ）がとりうる最大のビット数（この場合には８ビット）から、Ｃｒｅｇ６ｂに実際に格納されている出力（値Ｃｒｅｇ）のビット数（上位側の「０」を除く）を引いた値に等しい。
【０１０６】
上記構成の算術符号化装置１における符号化処理の詳細について、図６に基づいて説明する。図６は、本実施形態にかかる図１に示す算術符号化装置１の処理をフローチャートとして表したものである。
【０１０７】
算術符号化装置１のコンテクスト生成部２に入力画像データが入力されると、コンテクスト生成部２は、入力画像データを、１ライン以上の横ラインからなるストライプに分割する。このストライプは、幅が画像の幅と同じであり、高さは１ライン以上で画像の高さ以下の領域である。
【０１０８】
算術符号化装置１は、符号化処理をストライプ単位で行う。Ｓ１〜Ｓ１７のストライプのループ（ＬＯＯＰ１）の内部では個々のストライプの処理を行う。Ｓ１から一つのストライプについての処理を開始し、Ｓ１〜Ｓ１７のストライプのループ（ＬＯＯＰ１）においてそのストライプの処理（画素の符号化を繰り返す処理）が完了すると、Ｓ１〜Ｓ１７のストライプのループ（ＬＯＯＰ１）の先頭のＳ１に戻って、次のストライプの処理をＳ２から開始する。Ｓ１〜Ｓ１７までのループによって全てのストライプに対して処理が完了すると、画像データ全体の符号化が完了する。
【０１０９】
また、Ｓ２では、出力ビットカウンタ６ｄ（Ｃｒｅｇ６ｂに何ビット分の出力があるかを計測するためのカウンタ）のカウント値ＣＴを１１に初期化する。このように、ＪＢＩＧの仕様では、３ビットのダミーがあるため、ストライプの符号化を開始する際に、出力ビットカウンタ６ｄのカウント値ＣＴを１１に初期化する。なお、出力ビットカウンタ６ｄのカウント値ＣＴの初期値を１１にセットするのはストライプの先頭でカウント値ＣＴを初期化するときだけで、実際に正規化や出力を行うときにはカウント値ＣＴを８にセットする。
【０１１０】
ストライプのループ（ＬＯＯＰ１）の内部には画素のループ（ＬＯＯＰ２）がある。画素のループ（ＬＯＯＰ２）の内部では、Ｓ４〜Ｓ１４において各画素の処理が行われる。１つの画素の処理が完了すると、画素のループ（ＬＯＯＰ２）の先頭Ｓ３に戻って次の画素の符号化が行われる。画素のループ（ＬＯＯＰ２）の先頭Ｓ３において、コンテクスト生成部２は、選択したストライプのうちから、符号化対象となる一つの画素を選択する。このとき、次の画素は、例えばストライプの左上から右下に向けて移動させるように順次一つずつ選択する。したがって、例えば横方向に１ライン分の画素とコンテクストの読み取りを完了すると、その下のラインの読み取りへと進む。全ての画素の処理が完了すると１つのストライプの処理が完了したことになる。
【０１１１】
Ｓ４において、コンテクスト生成部２は、対象となる画素と、対象となる画素についてのコンテクストを、ストライプから抽出する。コンテクスト生成部２は、抽出した画素とコンテクストとを、取得部３へと出力する。
【０１１２】
Ｓ５では、取得部３が、確率推定テーブル７を参照して、入力されたコンテクストに応じたＭＰＳを取得する。また、取得部３は、入力されたコンテクストに応じたＬＳＺのインデックスＳＴを確率推定テーブル７から取得する。取得部３は、画素の値、ＭＰＳ、インデックスＳＴを算術符号化部４へと出力する。
【０１１３】
Ｓ６では、算術符号化部４において、前処理部１０の選択部１０ｃが、取得部３から入力される画素の値とＭＰＳとに応じて、「対象画素の値（入力シンボル）がＭＰＳである」という第１の条件が満たされているか否かを判別する。この条件は、「符号化対象シンボルが、優勢確率シンボルである」という第１の条件に対応する。対象画素がＭＰＳである場合にはＳ７に進む。この場合、Ｓ８〜Ｓ１１の手順を行い、Ｓ１４に進む。また、Ｓ６において対象画素がＬＰＳである場合にはＳ１２に進む。この場合、Ｓ１２〜Ｓ１３の手順を行い、Ｓ１４に進む。
【０１１４】
Ｓ７に進んだ場合、処理はＬＳＺの値に応じて２つに分岐する。すなわち、Ｓ７においては、前処理部１０のＬＳＺ検知部１０ａが、入力されるＬＳＺのインデックスＳＴから、「ＬＰＳインターバル（ＬＳＺ）が０、２５（"0x4000"）以下である（ＬＳＺ≦０．２５）」という第２の条件が満たされているかどうかを判別する。ここで、ＬＳＺ＝０、２５（"0x4000"）となることはないので、上記の条件を「ＬＰＳインターバル（ＬＳＺ）が０、２５（"0x4000"）未満である（ＬＳＺ＜０．２５）」という条件に変更してもよい。この条件は、「符号化対象シンボルにおける劣勢確率シンボルのインターバルが、閾値以下である」という第２の条件に対応する。ＬＰＳインターバル（ＬＳＺ）が０、２５（"0x4000"）以下である場合には、一括符号化を行うことができるので、Ｓ８に進む。上記の条件が満たされていない場合（ＭＰＳが与えられても、ＬＳＺが０．２５（"0x4000"）より大きかった場合）には、一括符号化を行うことができないので、Ｓ１０に進む。そして、Ｓ１０・Ｓ１１の手順を行った後、Ｓ１４に進む。
【０１１５】
本発明における符号化方法では、ＬＳＺが０．２５以下での一括符号化では、近傍形は同一でなければならない。すなわち、本発明における符号化方法では、近傍形が一定である場合に一括符号化を行う。なぜなら、近傍形が一定でなければ、近傍形ごとのＬＳＺの値がバラバラであるために、近傍形の出現順序が分からない限り一括符号化を行うことができず、一括符号化の処理の実現が難しくなるためである。
【０１１６】
そこで、Ｓ８で近傍形検知部１０ｄが近傍形のチェックを行う。すなわち、一括符号化の対象となる画素として第１の一括符号化画素カウンタ６ｃで計数されている画素の近傍形を予め近傍形記憶領域６ｄに記録しておき、その近傍形を参照して近傍形検知部１０ｄが一括符号化対象画素のカウントを新規に開始、あるいは継続できるかどうかを判定する。
【０１１７】
このときのチェックの結果は、現在の近傍形（現在の符号化対象画素のコンテクスト）が前回の近傍形（前回の符号化対象画素のコンテクスト）と一致する、前回の近傍形が近傍形記憶領域６ｄに記録されていない（第１の一括符号化画素カウンタ６ｃのカウント値ｔが０のとき）、現在の近傍形が前回の近傍形と一致しない、の３通りが考えられる。現在の近傍形が前回の近傍形と一致するとき及び前回の近傍形が近傍形記憶領域６ｄに記録されていないとき（第１の一括符号化画素カウンタ６ｃのカウント値ｔが０のとき）には、Ｓ９で一括符号化対象画素のカウントを継続する、あるいは新規に開始することになるので、そこまでの画素を一括符号化する必要はない。一方、現在の近傍形が前回の近傍形と一致しない場合には、一括符号化対象画素のカウントを中断して一括符号化を行うか、あるいは一括符号化対象画素のカウントを開始しない。そこで、Ｓ１０に進み、一括チェック部１０ｂが第１の一括符号化チェックを行う。前回の近傍形が近傍形記憶領域６ｄに記録されていなかった場合、及び現在の近傍形が前回の近傍形と一致しなかった場合には、Ｓ８の中で現在の近傍形を記録する。Ｓ８で記録された近傍形は第１の一括符号化チェック時に削除される。
【０１１８】
言い換えると、Ｓ８においては、前処理部１０の近傍形検知部１０ｄが、「レジスタ６の近傍形記憶領域６ｄに直前の符号化対象画素（一括符号化の対象となる画素）のコンテクスト（近傍形）が保存されていないか、あるいは保存されている直前の符号化対象画素のコンテクスト（近傍形）に現在の符号化対象画素のコンテクスト（近傍形）が一致している」という第３の条件が満たされているかどうかを判別する。レジスタ６の近傍形記憶領域６ｄに直前の符号化対象画素のコンテクスト（近傍形）が保存されていないのは、符号化対象の画素がストライプの最初の画素（全シンボル列の最初のシンボル）または一括符号化直後の画素であるときである。この条件は、「符号化対象シンボルにおける劣勢確率シンボルのインターバルが、符号化対象シンボルの直前のシンボルにおける劣勢確率シンボルのインターバルと同一であるか、あるいは符号化対象のシンボルが、全シンボル列の最初のシンボルまたは一括符号化直後のシンボルである」という第３の条件に対応する。上記の条件が満たされている場合には、一括符号化すべき画素を計数する処理を継続または新規に開始できると判断して、Ｓ９に進み、Ｓ９で第１の一括符号化画素カウンタ６ｃを使って一括符号化すべき画素を計数する処理を、継続または新規に開始する。それ以外の場合には、一括符号化すべき画素を計数する処理を新規に開始できない、あるいは継続できないと判断して、Ｓ１０に進み、一括符号化すべき画素を計数する処理を、行わないか、あるいは中断する。その後、一括符号化（Ｓ１０）および個別の符号化（Ｓ１１）を行った後、Ｓ１４に進む。
【０１１９】
Ｓ８の近傍形チェック処理について、図１０に基づいて詳細に説明する。
まず、近傍形検知部１０ｄが、レジスタ６の近傍形記憶領域６ｄにアクセスして、近傍形記憶領域６ｄに記憶された近傍形（コンテクスト）が存在するか否かを判定する（Ｓ５１）。レジスタ６の近傍形記憶領域６ｄに近傍形が記憶されていなかった場合（第１の一括符号化画素カウンタ６ｃのカウント値ｔが０のとき）には、近傍形検知部１０ｄが、現在の符号化対象の近傍形をコンテクスト生成部２から取得してレジスタ６の近傍形記憶領域６ｄに保存（記録）する（Ｓ５２）。さらに、上記第３の条件が満たされている（ＹＥＳ）と判定し、Ｓ９へ進む。
【０１２０】
一方、Ｓ５１において、レジスタ６の近傍形記憶領域６ｄに記憶された近傍形が存在する場合には、レジスタ６の近傍形記憶領域６ｄに記憶された近傍形、すなわち直前の符号化対象画素の近傍形を読み出すと共に、現在の符号化対象画素の近傍形をコンテクスト生成部２から取得する。そして、レジスタ６の近傍形記憶領域６ｄに記憶された近傍形と、現在の符号化対象画素の近傍形とが一致するか否かを判定する（Ｓ５３）。両者が一致しない場合には、近傍形検知部１０ｄが、現在の符号化対象の近傍形をコンテクスト生成部２から取得してレジスタ６の近傍形記憶領域６ｄに保存する（Ｓ５４）。さらに、上記第３の条件が満たされていない（ＮＯ）と判定し、Ｓ１０へ進む。一方、Ｓ５３において、２つの近傍形が一致する場合には、上記第３の条件が満たされている（ＹＥＳ）と判定し、Ｓ９へ進む。
【０１２１】
以上のように、Ｓ６〜Ｓ８により、「対象画素の値がＭＰＳである」という第１の条件と、「ＬＰＳインターバル（ＬＳＺ）が０、２５以下である」という第２の条件と、「レジスタ６の近傍形記憶領域６ｄに直前の符号化対象画素の近傍形が保存されていないか、あるいは保存されている直前の符号化対象画素の近傍形に現在の符号化対象画素のコンテクストが一致している」という第３の条件が何れも満たされるか否かが判定されることになる。そして、第１〜３の条件の何れかが満たされないと判定された場合にはＳ１０またはＳ１２に進み、上記第１の判定ステップにおいて第１〜３の条件の何れもが満たされると判定された場合にはＳ９に進む。
【０１２２】
Ｓ９においては、一括チェック部１０ｂが、第１の一括符号化画素カウンタ６ｃのカウント値ｔを１だけインクリメントする。これに応じて、一括チェック部１０ｂからの判別結果を得た選択部１０ｃが選択信号を図１に示す符号処理部９に送信する。この選択信号は、符号処理部９において符号化をせずに、符号処理部９からコンテクスト生成部２への画素インクリメントのみを行う旨の内容である。なお、符号処理部９は、この時点では符号化しないが、後でまとめて符号化を行う。符号処理部９がコンテクスト生成部２に画素インクリメントのための信号を出力し、Ｓ１４に進む。
【０１２３】
一括符号化対象画素の計数を中断した場合、あるいは一括符号化対象画素の計数を開始していない場合に、Ｓ１０において、第１の一括符号化チェックが行われる。第１の一括符号化チェックでは、一括符号化対象画素の計数を中断した場合である（一括符号化すべき画素がある）のか一括符号化対象画素の計数を開始していない場合である（一括符号化すべき画素がない）のかを判定し、一括符号化対象画素の計数を中断した場合であれば、それまでに計数した一括符号化対象画素の一括符号化を行うと共に、近傍形記憶領域６ｄに記憶された近傍形を消去する。
【０１２４】
Ｓ１０の第１の一括符号化チェックについて、図７および図８に基づいて詳細に説明する。
【０１２５】
第１の一括符号化チェックでは、Ｓ１０で画素カウンタの値をチェックし、第１の一括符号化画素カウンタ６ｃのカウント値ｔが０でなければ、そこまでに一括符号化対象としてカウントされた画素の一括符号化を行う。
【０１２６】
すなわち、まず、一括チェック部１０ｂが、レジスタ６の第１の一括符号化画素カウンタ６ｃにアクセスして、このカウント値ｔが０を超えているか否かを判別する（Ｓ２１）。このカウント値ｔの判別は、一括符号化を行う必要があるかどうかを調べるためのものである。カウント値ｔが０である場合には、一括チェック部１０ｂから判別結果を得た選択部１０ｃがＭＰＳ処理部９ａを選択する旨の選択信号を符号処理部９に出力して、Ｓ９に進む。カウント値ｔが０を超えている場合には、一括チェック部１０ｂから判別結果を得た選択部１０ｃが、まずＭＵＬＭＰＳ１処理部９ｄを選択する旨の選択信号を符号処理部９に出力して、符号処理部９のＭＵＬＭＰＳ１処理部９ｄが、本発明による一括符号化処理であるＣＯＤＥＭＵＬＭＰＳ１処理を実行する（ＣＯＤＥＭＵＬＭＰＳ１を呼ぶ）（Ｓ２２）。その後、レジスタ６の近傍形記憶領域６ｄに記録（登録）された近傍形を削除し（Ｓ２３）、Ｓ９へ進む。このように、第１の一括符号化画素カウンタ６ｃのカウント値ｔが１以上であれば一括符号化を行う。
【０１２７】
Ｓ２２のＣＯＤＥＭＵＬＭＰＳ１処理では、ＬＳＺが０．２５より大きい場合、符号化対象画素の近傍形が近傍形記憶領域６ｄに記憶されており、かつ、記憶された近傍形と現在の符号化対象画素の近傍形とが一致する場合、劣勢確率シンボルが与えられる場合、ストライプの終端に達した場合、または画像の終端に達した場合、または例えば実装上の都合によってそれ以上一括して符号化することが好ましくない画素まで達した場合に、そこまでに第１の一括符号化画素カウンタ６ｃに加えられていた個数（カウント値ｔ）分の画素を一括して符号化する。
【０１２８】
ＣＯＤＥＭＵＬＭＰＳ１処理は、本発明において新しく追加された手順であり、ＭＵＬＭＰＳ１処理部９ｄによって実行される。ＣＯＤＥＭＵＬＭＰＳ１処理は、第１の一括符号化画素カウンタ６ｃのカウント値（一括符号化する画素の個数）ｔ、Ａｒｅｇ６ａの格納値Ａｒｅｇ（インターバルの大きさ）、および一括符号化する画素の近傍形（コンテクスト）に応じたＬＳＺのインデックスＳＴの値から、一括符号化時に連続的に行う正規化の回数、一括符号化終了時のＡｒｅｇ６ａの格納値Ａｒｅｇ（インターバルの大きさ）、および一括符号化終了直後に処理する画素の近傍形（コンテクスト）に応じたＬＳＺのインデックスＳＴの値を求め、一括符号化および一括正規化を行う処理である。
【０１２９】
このＣＯＤＥＭＵＬＭＰＳ１処理は、ＬＰＳインターバルが０．２５以下となるような近傍形を持つＭＰＳが連続した場合のみ行われるようになっているため、ＭＰＳインターバルとＬＰＳインターバルとの入れ替えが発生しない。その結果、ＣＯＤＥＭＵＬＭＰＳ１処理は、逐次の正規化処理をシミュレーションする比較的簡素な演算処理で実現できる。
【０１３０】
ＣＯＤＥＭＵＬＭＰＳ１処理を実現する方法は幾つもあるが、ここでは、計算量のことを無視して、比較的分かりやすいと思われる方法を例に挙げて説明する。ＣＯＤＥＭＵＬＭＰＳ１処理の一例について、図８に基づいて説明する。
【０１３１】
この方法では、まず、正規化回数ｒを０に初期化する。次いで、Ｓ３１〜Ｓ３３の演算ループ（ＬＯＯＰ＿Ａ）の処理をループ脱出条件「ｔ＜ｎ」を満たさない限り繰り返し行う。
【０１３２】
Ａｒｅｇ６ａの格納値をＡｒｅｇ、一括符号化する画素の個数（第１の一括符号化画素カウンタ６ｃのカウント値）をｔ、インデックスＳＴの値がｓｔのときのＬＳＺの値をｌｓｚ（ｓｔ）とすると、一括符号化を開始してから最初の正規化発生まで、あるいは正規化が発生した時点から次回の正規化が発生するまでに処理できる画素の個数ｎは、
ｎ＝（Ａｒｅｇ−0x8000）／ｌｓｚ（ｓｔ）＋１
となる。Ｓ３１では、この演算により、一括符号化を開始してから最初の正規化発生まで、あるいは正規化が発生した時点から次回の正規化が発生するまでに処理できる画素の個数ｎを求める。
【０１３３】
次に、ｔ≦ｎであるか否かを判定する（Ｓ３２）。もし、ｔ≦ｎならば正規化は発生しないが、ｔ＞ｎであれば正規化が発生する。
【０１３４】
ｔ＞ｎであるとき、すなわちｎ個の画素の符号化が完了する前に正規化が発生するときは、Ｓ３３に進む。Ｓ３３では、正規化発生前におけるＡｒｅｇ６ａの値ＡｒｅｇおよびインデックスＳＴの値ｓｔから、正規化発生後におけるＡｒｅｇ６ａの値Ａｒｅｇ’およびインデックスＳＴの値ｓｔ’を、次式
Ａｒｅｇ’＝（Ａｒｅｇ−ｌｓｚ（ｓｔ）＊ｎ）＊２
ｓｔ’＝ｎｍｐｓ（ｓｔ）
ｔ’＝ｔ−ｎ
により求める。ここで、ｎｍｐｓ（ｓｔ）は、インデックスＳＴの値がｓｔのときのＮＭＰＳ（優勢確率シンボルを符号化して、かつ正規化が発生した場合の次のインデックスＳＴ）の値を示す。この後、Ｓ３１に戻り、（ｔ−ｎ）個の画素を処理することになる。
【０１３５】
また、Ｓ３３では、正規化回数ｒに１を足す。Ｓ３３に到達する回数と一括符号化時に連続的に行うべき正規化の回数ｒとが一致するため、Ｓ３１〜Ｓ３３の演算ループを抜けた時点で、正規化回数ｒは、一括符号化時に連続的に行うべき正規化の回数ｒとなる。
【０１３６】
一方、Ｓ３３においてｔ≦ｎで正規化が発生しない場合には、演算ループ（ＬＯＯＰ＿Ａ）を脱出し、その時点におけるＡｒｅｇ６ａの値（ＡｒｅｇまたはＡｒｅｇ’）、インデックスＳＴの値ｓｔ（ｓｔまたはｓｔ’）、およびｔ（ｔまたはｔ’）から、ｎ個の画素を符号化した後におけるＡｒｅｇ６ａの値Ａｒｅｇ’およびインデックスＳＴの値ｓｔ’を、次式
Ａｒｅｇ’＝（Ａｒｅｇ−ｌｓｚ（ｓｔ）＊ｔ）
ｓｔ’＝ｓｔ
により求める（Ｓ３４）。これで、ｎ個の画素を符号化した後におけるＡｒｅｇ６ａの値Ａｒｅｇ’およびインデックスＳＴの値ｓｔ’が求められる。
【０１３７】
以上のＳ３１〜Ｓ３４の処理により、ｔ個の画素を符号化した後における、Ａｒｅｇ６ａの値、インデックスＳＴの値、正規化の発生回数ｒを求めることができる。
【０１３８】
次に、Ｓ３５では、ＭＵＬＭＰＳ１処理部９ｄが、求められた正規化発生回数ｒに等しい回数だけ、手順ＭＵＬＲＥＮＯＲＭを読み出して実行する。これによって、一括符号化を行った場合と同じ出力を得ることができる。このＭＵＬＲＥＮＯＲＭ処理については、後述する。
【０１３９】
この後、Ｓ３６に進み、次の符号化処理に備えて、一括チェック部１０ｂが第１の一括符号化画素カウンタ６ｃに０を代入（カウント値ｔを０にする）する。この後、図７のＳ２３に進み、前述したように、レジスタ６の近傍形記憶領域６ｄに記録（登録）された近傍形を削除することになる。
【０１４０】
なお、ＣＯＤＥＭＵＬＭＰＳ１処理を実現する方法としては、実装に必要なメモリ量を無視して計算量の最小化を追求するならば、一括符号化する画素の個数ｔ、Ａｒｅｇ６ａの格納値Ａｒｅｇ、および一括符号化する画素の近傍形に応じたＬＳＺのインデックスＳＴの値のあらゆる組み合わせに対する出力値（一括符号化終了時のＡｒｅｇ６ａの格納値Ａｒｅｇ、および一括符号化終了直後に処理する画素の近傍形（コンテクスト）に応じたＬＳＺのインデックスＳＴの値）を予め計算して３次元的な表にしておき、この表を参照して出力値を計算する方法もある。一括符号化する画素の個数ｔ、Ａｒｅｇ６ａの格納値Ａｒｅｇ、および一括符号化する画素の近傍形に応じたＬＳＺのインデックスＳＴの値はすべて、精度と範囲との両方が有限であるため、この表は、有限の大きさで実現できる。
【０１４１】
次に、図８のＳ３５にて呼び出されるＭＵＬＲＥＮＯＲＭ処理について、図９に基づいて説明する。このＭＵＬＲＥＮＯＲＭ処理は、一括符号化において正規化をまとめて行なった際に、出力を得るためにＣｒｅｇ６ｂの格納値Ｃｒｅｇを変化させる処理である。
【０１４２】
Ｓ４１では、ＭＵＬＲＥＮＯＲＭ処理部９ｅが、Ｃｒｅｇ６ｂを上位側へ１ビットシフト（Ｃｒｅｇ＝Ｃｒｅｇ≪１）する（すなわち、格納値Ｃｒｅｇを２倍にする）。また、ＭＵＬＲＥＮＯＲＭ処理部９ｅが、出力ビットカウンタ６ｄのカウント値ＣＴから、１を減ずる。
【０１４３】
Ｓ４１の次のＳ４２では、ＭＵＬＲＥＮＯＲＭ処理部９ｅは、出力ビットカウンタ６ｄのカウント値ＣＴが０であるか否かを判別する。出力ビットカウンタ６ｄのカウント値ＣＴが０である場合には、出力ビットカウンタ６ｄに８ビット（１バイト）の出力データ（Ｃｒｅｇ）が格納されているので、Ｓ４３に進み、ＭＵＬＲＥＮＯＲＭ処理部９ｅは、Ｃｒｅｇ６ｂから１バイト分のデータ（Ｃｒｅｇ）を符号化データとして算術符号化装置１の外部へと出力する。また、ＭＵＬＲＥＮＯＲＭ処理部９ｅは、出力とともに、出力ビットカウンタ６ｄのカウント値ＣＴを８にする。
【０１４４】
Ｓ４２において出力ビットカウンタ６ｄのカウント値ＣＴが０でない場合や、またはＳ４３の後は、ＭＵＬＲＥＮＯＲＭ処理を終了する。
【０１４５】
以上のＣＯＤＥＭＵＬＭＰＳ２処理によって、通常の符号化処理（ＣＯＤＥＭＰＳ）の動作をシミュレーションすることができる。なお、ＳＴが１３のときのＬＳＺの値は０．２５より小さいため、インターバルが取り得る最小値０．５であったとしても、ＬＰＳインターバルの大きさがＭＰＳインターバルの大きさより大きくなることはない。例えば、インターバルが０．５、ＬＳＺが０．２４であったとすると、ＭＰＳインターバルの大きさは、（インターバルの大きさ）−ＬＳＺ＝０．２６で、ＬＳＺより大きくなる。
【０１４６】
図６に戻ると、Ｓ１０の第１の一括符号化チェックの後、Ｓ１１では、符号処理部９のＭＰＳ処理部９ａが、通常のＱＭ−Ｃｏｄｅｒと同じ手順でＣＯＤＥＭＰＳ処理（ＭＰＳの符号化）を行う。
【０１４７】
このＣＯＤＥＭＰＳ処理は、図１１に示すＳ６１〜Ｓ６５の処理に相当する。ＭＰＳ処理部９ａは、算術符号化において入力ビットがＭＰＳであった場合に、インターバルの範囲を変更し、必要がある場合にはＲＥＮＯＲＭ処理部９ｃを呼び出してＣＯＤＥＲＥＮＯＲＭ処理を行わせる。ＣＯＤＥＲＥＮＯＲＭ処理については、後述する。
【０１４８】
入力ビットがＭＰＳであったため、ＭＰＳ処理部９ａは、Ｓ２０において、現在のインターバルからＬＰＳインターバルを取り除くようにインターバルを変化させる。より詳細には、ＭＰＳ処理部９ａは、記録部５の確率推定表８にアクセスして、インデックスＳＴを用いて、ＬＰＳインターバルの近似値であるＬＳＺを取得する。また、ＭＰＳ処理部９ａは、レジスタ６のＡｒｅｇ６ａにアクセスしてＡｒｅｇを取得する。ＭＰＳ処理部９ａは、ＡｒｅｇからＬＳＺの値を引くことによって、インターバルの大きさを変化させる。ＭＰＳ処理部９ａは、ＡｒｅｇからＬＳＺの値を引くことによって得た値を新たなＡｒｅｇの値として、レジスタ６のＡｒｅｇ６ａに記録する。
【０１４９】
Ｓ６２では、ＭＰＳ処理部９ａが、新たなＡｒｅｇの値が０．５（"0x8000"）未満であるか否かを判別する。新たなＡｒｅｇの値が０．５以上の場合には正規化の必要はないので、ＣＯＤＥＭＰＳ処理を終了し、図６に戻りＳ１４に進む。
【０１５０】
一方、Ｓ６２において新たなＡｒｅｇの値が０．５（"0x8000"）未満である場合には、Ｓ６３に進む。Ｓ６３では、ＭＰＳ処理部９ａが、新たなＡｒｅｇの値がＬＳＺ未満であるか否かを判別する。Ａｒｅｇの値がＬＳＺ以上の場合には、ＭＰＳインターバルとＬＰＳインターバルとの入れ替えは不要であるので、Ｓ６５に進む。
【０１５１】
一方、Ｓ６３においてＡｒｅｇ６ａの値がＬＳＺ未満の場合には、ＭＰＳ処理部９ａは、Ｓ６４においてＭＰＳインターバルとＬＰＳインターバルとを入れ替えてＳ６５に進む。より詳細には、ＭＰＳ処理部９ａは、レジスタ６のＣｒｅｇ６ｂにアクセスしてＣｒｅｇを取得する。ＭＰＳ処理部９ａは、ＣｒｅｇにＡｒｅｇを加えて、新たなＣｒｅｇとする。ＭＰＳ処理部９ａは、ＬＳＺを新たなＡｒｅｇの値とする。ＭＰＳ処理部９ａは、新たなＡｒｅｇおよびＣｒｅｇをそれぞれ、レジスタ６のＡｒｅｇ６ａおよびＣｒｅｇ６ｂに記録する。
【０１５２】
Ｓ６５では、まず、ＭＰＳ処理部９ａが、正規化に応じてＬＳＺのインデックスＳＴを更新する。これは、確率推定表８を用いて、優勢確率シンボルを符号化して、かつ正規化が発生した場合の次のＳＴの値であるＮＭＰＳを読取ることによって行う。さらに、Ｓ６５では、ＭＰＳ処理部９ａは、ＲＥＮＯＲＭ処理部９ｃを呼び出して、正規化処理であるＣＯＤＥＲＥＮＯＲＭを実行させる。ＣＯＤＥＲＥＮＯＲＭ処理については後述する。Ｓ６５が終了すると、ＣＯＤＥＭＰＳ処理を終了して、図６に戻り、Ｓ１４に進む。
【０１５３】
次に、ＲＥＮＯＲＭ処理部９ｃの行うＣＯＤＥＲＥＮＯＲＭについて、図１２に基づいて説明する。このＣＯＤＥＲＥＮＯＲＭは、正規化が完了するまで２倍化処理を繰り返すとともに、Ｃｒｅｇ６ｂに値が蓄積されると適宜出力するという処理である。
【０１５４】
Ｓ６６では、ＲＥＮＯＲＭ処理部９ｃは、ＡｒｅｇおよびＣｒｅｇをそれぞれ上位側に１ビットシフトさせる（Ａｒｅｇ＝Ａｒｅｇ≪１、Ｃｒｅｇ＝Ｃｒｅｇ≪１）とともに、Ｃｒｅｇ６ｂの空きビット数を表す、出力ビットカウンタ６ｅのカウント値ＣＴから、１を減ずる。
【０１５５】
Ｓ６６の次のＳ６７では、ＲＥＮＯＲＭ処理部９ｃは、カウント値ＣＴが０であるか否かを判別する。カウント値ＣＴが０である場合にはＳ６８に進み、カウント値ＣＴが０でない場合にはＳ６９に進む。
【０１５６】
Ｓ６８では、ＲＥＮＯＲＭ処理部９ｃが、Ｃｒｅｇ６ｂから符号化結果を１バイト分だけ算術符号化装置１の外部に出力するとともに、カウント値ＣＴを８として、Ｓ６９に進む。
【０１５７】
Ｓ６９では、ＲＥＮＯＲＭ処理部９ｃは、Ａｒｅｇ６ａの格納値Ａｒｅｇが０．５（"0x8000"）未満であるか否かを判別する。Ａｒｅｇ６ａの格納値Ａｒｅｇが０．５（"0x8000"）未満である場合にはＳ６６に戻り、Ａｒｅｇ６ａの格納値がＡｒｅｇ０．５（"0x8000"）以上である場合には処理を終了する。
【０１５８】
以上のＳ６６〜Ｓ６９にて、ＣＯＤＥＲＥＮＯＲＭ処理が終了する。
【０１５９】
図６に戻ると、Ｓ６において対象画素の値（入力ビット）がＬＰＳであった場合に、Ｓ１２では、一括チェック部１０ｂ、選択部１０ｃ、およびＣＯＤＥＭＵＬＭＰＳ処理部９ｄが、第１の一括符号化チェックを行い、Ｓ１３に進む。この第１の一括符号化チェックは、Ｓ１０で行うものと同様であるので、説明は省略する。
【０１６０】
Ｓ１３では、符号処理部９のＬＰＳ処理部９ｂが、ＣＯＤＥＬＰＳ処理を行う。このＣＯＤＥＬＰＳ処理は、図１３に示すＳ７１〜Ｓ７７の処理に相当する。
【０１６１】
ＬＰＳ処理部９ｂは、算術符号化において入力ビットがＬＰＳであった場合に、インターバルの範囲を変更し、また必要がある場合にはＲＥＮＯＲＭ処理部９ｃを呼び出してＣＯＤＥＲＥＮＯＲＭ処理を行わせる。入力ビットがＬＰＳであったため、ＬＰＳ処理部９ｂは、現在のインターバルからＭＰＳインターバルを取り除くようにインターバルを変化させる。
【０１６２】
Ｓ７１では、ＬＰＳ処理部９ｂは、Ａｒｅｇ６ａの値からＬＳＺを引く。より詳細には、ＬＰＳ処理部９ｂは、レジスタ６にアクセスしてＡｒｅｇ６ａの格納値Ａｒｅｇを取得する。ＬＰＳ処理部９ｂは、記録部５の確率推定表８にアクセスして、インデックスＳＴを用いて、ＬＰＳインターバルの近似値であるＬＳＺを取得する。その後、ＬＰＳ処理部９ｂは、Ａｒｅｇ６ａからＬＳＺを引く。
【０１６３】
Ｓ７１の次のＳ７２では、ＬＰＳ処理部９ｂは、現在のＡｒｅｇ６ａの格納値ＡｒｅｇがＬＳＺ未満であるか否かを判別する。なお、Ｓ７１の処理によって、現在のＡｒｅｇ６ａのの格納値Ａｒｅｇは、ＭＰＳインターバルの近似値となっている。
【０１６４】
Ｓ７２において、現在のＡｒｅｇの格納値ＡｒｅｇがＬＳＺ未満であると判別された場合にはＳ７４に進む。この場合には、ＭＰＳインターバルの近似値がＬＳＺ未満であるため、ＬＰＳインターバルとＭＰＳインターバルとを入れ替え、その後に新たなインターバルとしてＬＰＳインターバルを選択することになる。この処理は、結局ＭＰＳインターバルを新たなインターバルとするのと同じことになる。このため、特に処理は不要で、単にＳ７４に進めばよい。
【０１６５】
また、現在のＡｒｅｇ６ａの値がＬＳＺ以上である場合にはＳ７２からＳ７３に進む。Ｓ７３では、ＬＰＳ処理部９ｂは、新たなインターバルとしてＬＰＳインターバルを選択する処理を行う。ＬＰＳ処理部９ｂは、レジスタ６にアクセスしてＣｒｅｇ６ａの格納値Ｃｒｅｇを取得する。ＬＰＳ処理部９ｂは、現在のＣｒｅｇ６ａの格納値Ｃｒｅｇに、現在のＡｒｅｇ６ａの格納値Ａｒｅｇを加えて新たなＣｒｅｇ６ａの格納値Ｃｒｅｇとする。また、ＬＰＳ処理部９ｂは、Ａｒｅｇ６ａの格納値ＡｒｅｇにＬＳＺを代入する。これによって、新たなインターバルとしてＬＰＳインターバルが選択される。Ｓ７３からはＳ７４に進む。
【０１６６】
Ｓ７４では、ＬＰＳ処理部９ｂは、インデックスＳＴに対応する確率推定表８のＳＷＩＴＣＨの項目が１であるか否かを判別する。ＳＷＩＴＣＨの項目が１である場合には、Ｓ７５に進み、ＬＰＳ処理部９ｂは、コンテクストに対するＭＰＳの値の入れ替え（例えば「０」であれば「１」に変更する）をして、Ｓ７６に進む。ＳＷＩＴＣＨの項目が１でない場合にはＳ７６に進む。
【０１６７】
Ｓ７６では、ＬＰＳ処理部９ｂは、確率推定表８にアクセスし、劣勢確率シンボルを符号化したときの次のインデックスＳＴの値を意味するＮＬＰＳを得る。
【０１６８】
Ｓ７６の次のＳ７７では、ＬＰＳ処理部９ｂがＲＥＮＯＲＭ処理部９ｃを呼び出して、ＣＯＤＥＲＥＮＯＲＭを実行させる。このＣＯＤＥＲＥＮＯＲＭは、Ｓ６５で行うものと同様であるので、説明は省略する。
【０１６９】
Ｓ７７までの処理によって、ＣＯＤＥＬＰＳ処理が終了すると、図６のＳ１４に進む。
【０１７０】
以上のようにして、第１の一括符号化画素カウンタ６ｃへの加算（Ｓ９）、ＣＯＤＥＭＰＳ処理（Ｓ１１）、またはＣＯＤＥＬＰＳ処理（Ｓ１３）が完了すると、画素のループ（ＬＯＯＰ２）の終端（Ｓ３にて選択した対象画素についての処理の終わりを示す）であるＳ１４に進む。
【０１７１】
Ｓ１４では、符号処理部９がコンテクスト生成部２に画素インクリメントのための信号を出力する。コンテクスト生成部２では、対象となる画素を更新しようとしたときに、画素がストライプの終点にきており、対象画素を更新できないかどうかを判別する。対象画素がストライプの終点にきており、対象画素を更新できない場合には次のＳ１５に進み、対象画素がストライプの終点にきておらず、対象画素を更新できる場合には画素のループ（ＬＯＯＰ２）の先頭Ｓ３へと戻り、次の画素の符号化へと移る。
【０１７２】
ストライプ内の全ての画素の符号化が完了したら、Ｓ１５で、本実施形態のようにストライプごとに処理を行う場合に、対象画素がストライプの終点にきた時点で符号化していない未処理の画素（一括符号化すべき画素）の有無を判別する。一括符号化すべき画素があれば、一括符号化すべき画素の一括符号化を行う。すなわち、Ｓ１５では、一括チェック部１０ｂ、選択部１０ｃ、およびＣＯＤＥＭＵＬＭＰＳ処理部９ｄが、第１の一括符号化チェックを行う。この第１の一括符号化チェックは、Ｓ１０およびＳ１２で行うものと同様であるので、説明は省略する。
【０１７３】
Ｓ１６では、レジスタ６のＣｒｅｇ６ｂに保存されている、符号化結果としてのインターバルの低数を、符号化データとして算術符号化装置１の外部へと出力する、フラッシュ処理を行う。
【０１７４】
Ｓ１７は、Ｓ１にて選択したストライプについての処理の終わりを示すものである。Ｓ１７においては、符号化が完了していないストライプがあるか否かを判別し、符号化が完了していないストライプがあると判別した場合には、このストライプのループ（ＬＯＯＰ）の最後Ｓ１７からストライプのループ（ＬＯＯＰ）の先頭Ｓ１に戻って、次のストライプの符号化に移る（コンテクスト生成部２が新たなストライプを選択する）。全てのストライプの符号化が完了していれば、画像全体の符号化を完了する。
【０１７５】
以上で説明したように、本実施形態の算術符号化装置１によれば、正規化が起こらないことを検知する必要が無いため、その分の演算を省略できる。また、正規化が起こる範囲でも、「ＬＰＳインターバルが０．２５以下となるような近傍形を持つシンボルの入力としてＭＰＳが与えられ、かつ、同じ近傍形を持つシンボルが連続する」という条件が満たされる範囲であれば一括符号化を行うことができるため、符号化をより高速化することができる。また、この条件は、特願２００４−１８５６８の方法で一括符号化が行われる条件、すなわち「ＬＰＳのインターバルが最小値であるＭＰＳが連続する」という条件よりも緩いため、より多くのシンボルを符号化することができ、その結果、符号化をより高速化することができる。
【０１７６】
〔実施の形態２〕
本発明の他の実施の形態について図１４ないし図１８に基づいて説明すれば、以下の通りである。なお、説明の便宜上、前記実施の形態１にて示した各部材と同一の機能を有する部材には、同一の符号を付記し、その説明を省略する。
【０１７７】
本実施形態に係る算術符号化装置１１は、図１４に示すように、実施の形態１の算術符号化装置１における符号処理部９および前処理部１０からなる算術符号化部４とレジスタ６とに代えて、符号処理部１９および前処理部２０からなる算術符号化部１４とレジスタ１６とを備える以外は、実施の形態１の算術符号化装置１と同一の構成を備えている。
【０１７８】
レジスタ１６は、実施の形態１の算術符号化装置１におけるレジスタ６が備える各部、すなわちＡｒｅｇ６ａ、Ｃｒｅｇ６ｂ、第１の一括符号化画素カウンタ６ｃ、近傍形記憶領域６ｄ、および出力ビットカウンタ６ｅに加えて、第２の一括符号化画素カウンタ６ｆを含んでいる。なお、図面中では、「第２の一括符号化画素カウンタ」を「第２画素カウンタ」と略記している。
【０１７９】
第２の一括符号化画素カウンタ６ｆは、後述するＭＵＬＭＰＳ２処理による一括符号化を行う画素の数の値ｕをカウントするものである。第２の一括符号化画素カウンタ６ｆにおけるカウント値ｕの初期値はｔ＝０とする。この第２の一括符号化画素カウンタ６ｆのカウント値ｕは、一括チェック部１０ｂが変化させる。
【０１８０】
符号処理部１９は、実施の形態１の算術符号化装置１における符号処理部９が備える各部、すなわち、処理部９ａ〜９ｅに加えて、後述するＭＵＬＭＰＳ２処理による括符号化処理（第１の一括符号化ステップ）を実行するＭＵＬＭＰＳ２処理部（第２の一括符号化部）９ｆを含んでいる。
【０１８１】
前処理部２０は、実施の形態１の算術符号化装置１における前処理部１０が備える各部、すなわち、ＬＳＺ検知部１０ａ、一括チェック部（第１の判定部）１０ｂ、選択部１０ｃ、および近傍形検知部１０ｄに加えて、最小検知部１０ｅを含んでいる。
【０１８２】
最小検知部１０ｅは、入力されるインデックスＳＴが１３となっているかどうかを調べる。後述するように、インデックスＳＴが１３のとき、ＬＳＺの値は最小となる。最小検知部１０ｅは、インデックスＳＴが１３となっている場合には、レジスタ６の第１の第１の一括符号化画素カウンタ６ｃのカウント値ｔ（一括符号化すべき画素の数）を１だけインクリメントする（増加させる）。このように、最小検知部１０ｅが、ＬＳＺが最小値となっているかどうかを調べるようになっている。
【０１８３】
ここで、図５（ａ）（ｂ）に示すように、インデックスＳＴの値は０から１１２までの値を取るが、このインデックスＳＴが１３のときにＬＳＺは最小となる。また、インデックスＳＴが１３のときには、優勢確率シンボルを符号化して正規化が発生したときの次のインデックスＳＴの値であるＮＭＰＳが１３となっている。すなわち、インデックスＳＴが１３のときには、優勢確率シンボルを符号化しているときに正規化が発生してもインデックスＳＴの値は１３のまま変化しないことが分かる。図５（ａ）（ｂ）に示すように、このようなインデックスＳＴの値は１３だけである。
【０１８４】
また、インデックスＳＴが１３のときのＬＳＺの値は"0x1"である。このため、インデックスＳＴが１３であれば、一括符号化中に正規化が発生したときに必要な２倍化処理の回数は、正規化一回につき２倍化処理は１回だけで良い。なぜなら、インデックスＳＴが１３で、一個の優勢確率シンボルを符号化して正規化が発生する場合、直前のインターバル（Ａｒｅｇ６ａの格納値Ａｒｅｇ）は"0x8000"であり、一個の優勢確率シンボルを符号化したときにはこの値から0x1であるＬＳＺの値を引くことになる。そのため、符号化後のＡｒｅｇ６ａの格納値Ａｒｅｇは"0x7fff"となる。この値"0x7fff"は、正規化時に２倍化処理を１回行えば"0xfffe"となる。この値は、"0x8000"より大きいため、これ以上２倍化処理を行う必要はない。それゆえ、正規化一回につき２倍化処理は１回だけで良い。
【０１８５】
なお、優勢確率シンボルを符号化した場合には、正規化が発生しない場合が存在する。このように正規化が発生しないときにはインデックスＳＴは変化しない。確率推定表８を参照してインデックスＳＴを変化させるのは正規化が発生したときだけである。従来の構成では、このことを利用して正規化の発生しない範囲で一括符号化を行なっている。
【０１８６】
上記構成の算術符号化装置１１における符号化処理の詳細について、図１５に基づいて説明する。図１５は、本実施形態にかかる図１４に示す算術符号化装置１１の処理をフローチャートとして表したものである。
【０１８７】
算術符号化装置１１のコンテクスト生成部２に入力画像データが入力されると、コンテクスト生成部２は、入力画像データを、１ライン以上の横ラインからなるストライプに分割する。このストライプは、幅が画像の幅と同じであり、高さは１ライン以上で画像の高さ以下の領域である。
【０１８８】
算術符号化装置１１は、符号化処理をストライプ単位で行う。Ｓ１〜Ｓ１７のストライプのループ（ＬＯＯＰ１）の内部では個々のストライプの処理を行う。Ｓ１から一つのストライプについての処理を開始し、Ｓ８１〜Ｓ１０００のストライプのループ（ＬＯＯＰ１）においてそのストライプの処理（画素の符号化を繰り返す処理）が完了すると、Ｓ８１〜Ｓ１０００のストライプのループ（ＬＯＯＰ１）の先頭のＳ８１に戻って、次のストライプの処理をＳ８２から開始する。Ｓ８１〜Ｓ１０００までのループによって全てのストライプに対して処理が完了すると、画像データ全体の符号化が完了する。
【０１８９】
また、Ｓ８２では、出力ビットカウンタ６ｄ（Ｃｒｅｇ６ｂに何ビット分の出力があるかを計測するためのカウンタ）のカウント値ＣＴを１１に初期化する。このように、ＪＢＩＧの仕様では、３ビットのダミーがあるため、ストライプの符号化を開始する際に、出力ビットカウンタ６ｄのカウント値ＣＴを１１に初期化する。なお、出力ビットカウンタ６ｄのカウント値ＣＴの初期値を１１にセットするのはストライプの先頭でカウント値ＣＴを初期化するときだけで、実際に正規化や出力を行うときにはカウント値ＣＴを８にセットする。
【０１９０】
ストライプのループ（ＬＯＯＰ１）の内部には画素のループ（ＬＯＯＰ２）がある。画素のループ（ＬＯＯＰ２）の内部では、Ｓ８４〜Ｓ１４において各画素の処理が行われる。１つの画素の処理が完了すると、画素のループ（ＬＯＯＰ２）の先頭Ｓ８３に戻って次の画素の符号化が行われる。画素のループ（ＬＯＯＰ２）の先頭Ｓ８３において、コンテクスト生成部２は、選択したストライプのうちから、符号化対象となる一つの画素を選択する。このとき、次の画素は、例えばストライプの左上から右下に向けて移動させるように順次一つずつ選択する。したがって、例えば横方向に１ライン分の画素とコンテクストの読み取りを完了すると、その下のラインの読み取りへと進む。全ての画素の処理が完了すると１つのストライプの処理が完了したことになる。
【０１９１】
Ｓ８４において、コンテクスト生成部２は、対象となる画素と、対象となる画素についてのコンテクストを、ストライプから抽出する。コンテクスト生成部２は、抽出した画素とコンテクストとを、取得部３へと出力する。
【０１９２】
Ｓ８５では、取得部３が、確率推定テーブル７を参照して、入力されたコンテクストに応じたＭＰＳを取得する。また、取得部３は、入力されたコンテクストに応じたＬＳＺのインデックスＳＴを確率推定テーブル７から取得する。取得部３は、画素の値、ＭＰＳ、インデックスＳＴを算術符号化部４へと出力する。
【０１９３】
Ｓ８６では、算術符号化部４において、前処理部１０の選択部１０ｃが、取得部３から入力される画素の値とＭＰＳとに応じて、「対象画素の値（入力シンボル）がＭＰＳである」という第１の条件が満たされているか否かを判別する。この条件は、「符号化対象シンボルが、優勢確率シンボルである」という第１の条件に対応する。対象画素がＭＰＳである場合にはＳ８７に進む。この場合、Ｓ８８〜Ｓ９５の手順を行い、Ｓ９８に進む。また、Ｓ８６において対象画素がＬＰＳである場合にはＳ９６に進む。この場合、Ｓ９６〜Ｓ９７の手順を行い、Ｓ９８に進む。
【０１９４】
Ｓ８７に進んだ場合、処理はＬＳＺの値に応じて３つに分岐する。すなわち、まず、Ｓ８７においては、前処理部１０の最小検知部１０ａが、入力されるＬＳＺのインデックスＳＴから、ＬＰＳインターバル（ＬＳＺ）が最小となっているかどうかを判別する。より詳細には、本実施形態においてはＪＢＩＧ圧縮するので、最小検知部１０ａは、ＬＳＺが最小値であるか（ＬＳＺのインデックスＳＴが１３であるか）否かを判別する。これによって、例えば記録部５の確率推定表８にアクセスして、実際にＬＰＳインターバル（ＬＳＺ）が最小となっているかどうか確認する手間を省くことができる。ＬＳＺのインデックスＳＴが１３である場合には、ＬＰＳインターバルが最小となっている。ＬＰＳインターバルが最小である場合にはＳ８８に進み、それ以外の場合にはＳ９０に進む。
【０１９５】
ＬＰＳインターバルが最小である場合には、Ｓ８８の一括符号化チェックで第１の一括符号化画素カウンタ６ｃの値が０でなければ第１の一括符号化画素カウンタ６ｃの値の分だけ一括符号化を行った上で、Ｓ８９で第２の一括符号化画素カウンタ６ｆを使って一括符号化する画素数のカウントアップを行う。
【０１９６】
より詳細には、まず、Ｓ８８において、第１の一括符号化チェックが行われる。第１の一括符号化チェックでは、第１の一括符号化画素カウンタ６ｃによる一括符号化対象画素の計数を中断した場合である（一括符号化すべき画素がある）のか第１の一括符号化画素カウンタ６ｃによる一括符号化対象画素の計数を開始していない場合である（一括符号化すべき画素がない）のかを判定し、第１の一括符号化画素カウンタ６ｃによる一括符号化対象画素の計数を中断した場合であれば、それまでに第１の一括符号化画素カウンタ６ｃで計数した一括符号化対象画素の一括符号化を行うと共に、近傍形記憶領域６ｄに記憶された近傍形を消去する。Ｓ８８の第１の一括符号化チェックは、実施の形態１で説明した第１の一括符号化チェックと同様である。ただし、この第１の一括符号化チェックにおいては、第２の一括符号化画素カウンタ６ｆを使用せず、第１の一括符号化画素カウンタ６ｃのみについて、カウント値（ｔ）が０かどうかをチェックし、０でなければ一括符号化を行う。また、この実施形態における第１の一括符号化チェックに含まれるＣＯＤＥＭＵＬＭＰＳ１処理は、基本的には実施の形態１におけるＣＯＤＥＭＵＬＭＰＳ１処理と同様である。ただし、一括符号化する画素の個数ｔの値には上限が設けられている。すなわち、この実施形態におけるＣＯＤＥＭＵＬＭＰＳ１は、画素の個数ｔの値がある上限値まで達したときに終了するようになっている。これは、ＭＰＳが出現し続ければ、ＳＴの値はやがて１３となるので、そこからは、ＣＯＤＥＭＵＬＭＰＳ１による一括符号化を終了してＣＯＤＥＭＵＬＭＰＳ２による一括符号化を行うためである。
【０１９７】
Ｓ８９においては、最小検知部１０ａが、第２の一括符号化画素カウンタ６ｆのカウント値ｕを１だけインクリメントする。これに応じて、一括チェック部１０ｂからの判別結果を得た選択部１０ｃが選択信号を図１に示す符号処理部９に送信する。この選択信号は、符号処理部９において符号化をせずに、符号処理部９からコンテクスト生成部２への画素インクリメントのみを行う旨の内容である。なお、符号処理部９は、この時点では符号化しないが、後でまとめて符号化を行う。符号処理部９がコンテクスト生成部２に画素インクリメントのための信号を出力し、Ｓ９８に進む。
【０１９８】
Ｓ９０においては、前処理部１０のＬＳＺ検知部１０ａが、入力されるＬＳＺのインデックスＳＴから、「ＬＰＳインターバル（ＬＳＺ）が０、２５（"0x4000"）以下である（ＬＳＺ≦０．２５）」という第２の条件が満たされているかどうかを判別する。ここで、ＬＳＺ＝０、２５（"0x4000"）となることはないので、上記の条件を「ＬＰＳインターバル（ＬＳＺ）が０、２５（"0x4000"）未満である（ＬＳＺ＜０．２５）」という条件に変更してもよい。この条件は、「符号化対象シンボルにおける劣勢確率シンボルのインターバルが、閾値以下である」という第２の条件に対応する。ＬＰＳインターバル（ＬＳＺ）が０、２５（"0x4000"）以下である場合には、一括符号化を行うことができるので、Ｓ９１に進む。上記の条件が満たされていない場合（ＭＰＳが与えられても、ＬＳＺが０．２５（"0x4000"）より大きかった場合）には、一括符号化を行うことができないので、Ｓ９４に進む。そして、Ｓ９４・Ｓ９５の手順を行った後、Ｓ９８に進む。
【０１９９】
本発明における符号化方法では、ＬＳＺが０．２５以下での一括符号化では、近傍形は同一でなければならない。すなわち、本発明における符号化方法では、近傍形が一定である場合に一括符号化を行う。なぜなら、近傍形が一定でなければ、近傍形ごとのＬＳＺの値がバラバラであるために、近傍形の出現順序が分からない限り一括符号化を行うことができず、一括符号化の処理の実現が難しくなるためである。
【０２００】
そこで、Ｓ９１で近傍形検知部１０ｄが近傍形のチェックを行う。すなわち、一括符号化の対象となる画素として第１の一括符号化画素カウンタ６ｃで計数されている画素の近傍形を予め近傍形記憶領域６ｄに記録しておき、その近傍形を参照して近傍形検知部１０ｄが、第１の一括符号化画素カウンタ６ｃによる一括符号化対象画素のカウントを新規に開始、あるいは継続できるかどうかを判定する。
【０２０１】
このときのチェックの結果は、現在の近傍形（現在の符号化対象画素のコンテクスト）が前回の近傍形（前回の符号化対象画素のコンテクスト）と一致する、前回の近傍形が近傍形記憶領域６ｄに記録されていない（第１の一括符号化画素カウンタ６ｃのカウント値ｔが０のとき）、現在の近傍形が前回の近傍形と一致しない、の３通りが考えられる。現在の近傍形が前回の近傍形と一致するとき及び前回の近傍形が近傍形記憶領域６ｄに記録されていないとき（第１の一括符号化画素カウンタ６ｃのカウント値ｔが０のとき）には、Ｓ９３で第１の一括符号化画素カウンタ６ｃによる一括符号化対象画素のカウントを継続する、あるいは新規に開始することになるので、第１の一括符号化画素カウンタ６ｃにより一括符号化対象画素としてそれまでにカウントされた画素を一括符号化する必要はない。一方、現在の近傍形が前回の近傍形と一致しない場合には、第１の一括符号化画素カウンタ６ｃによる一括符号化対象画素のカウントを中断して一括符号化を行うか、あるいは第１の一括符号化画素カウンタ６ｃによる一括符号化対象画素のカウントを開始しない。そこで、Ｓ９４に進み、一括チェック部１０ｂが第１の一括符号化チェックを行う。Ｓ９４では、第１の一括符号化チェックと共に、一括チェック部１０ｂが第２の一括符号化チェックを行う。すなわち、一括チェック部１０ｂが第１及び第２の一括符号化チェックを行う。前回の近傍形が近傍形記憶領域６ｄに記録されていなかった場合、及び現在の近傍形が前回の近傍形と一致しなかった場合には、Ｓ９１の中で現在の近傍形を記録する。Ｓ９１で記録された近傍形は、第１の一括符号化チェック時に削除される。
【０２０２】
言い換えると、Ｓ９１においては、前処理部１０の近傍形検知部１０ｄが、「レジスタ６の近傍形記憶領域６ｄに直前の符号化対象画素（一括符号化の対象となる画素）のコンテクスト（近傍形）が保存されていないか、あるいは保存されている直前の符号化対象画素のコンテクスト（近傍形）に現在の符号化対象画素のコンテクスト（近傍形）が一致している」という第３の条件が満たされているかどうかを判別する。レジスタ６の近傍形記憶領域６ｄに直前の符号化対象画素のコンテクスト（近傍形）が保存されていないのは、符号化対象の画素がストライプの最初の画素（全シンボル列の最初のシンボル）または一括符号化直後の画素であるときである。この条件は、「符号化対象シンボルにおける劣勢確率シンボルのインターバルが、符号化対象シンボルの直前のシンボルにおける劣勢確率シンボルのインターバルと同一であるか、あるいは符号化対象のシンボルが、全シンボル列の最初のシンボルまたは一括符号化直後のシンボルである」という第３の条件に対応する。上記の条件が満たされている場合には、一括符号化すべき画素を第１の一括符号化画素カウンタ６ｃによって計数する処理を継続または新規に開始できると判断して、Ｓ９２に進み、Ｓ９３で第１の一括符号化画素カウンタ６ｃを使って一括符号化すべき画素を計数する処理を、継続または新規に開始する。それ以外の場合には、一括符号化すべき画素を第１の一括符号化画素カウンタ６ｃによって計数する処理を第１の一括符号化画素カウンタ６ｃによって新規に開始できない、あるいは継続できないと判断して、Ｓ９４に進み、一括符号化すべき画素を第１の一括符号化画素カウンタ６ｃによって計数する処理を、行わないか、あるいは中断する。その後、一括符号化（Ｓ９４）および個別の符号化（Ｓ９５）を行った後、Ｓ９８に進む。なお、Ｓ９１の近傍形チェック処理の詳細については、実施の形態１で説明した通りであるので、ここではその説明を省略する。
【０２０３】
Ｓ９２では、第２の一括符号化チェックが行われる。第２の一括符号化チェックについて、図１６および図１８に基づいて詳細に説明する。
【０２０４】
まず、一括チェック部１０ｂが、レジスタ６の第２の一括符号化画素カウンタ６ｆにアクセスして、このカウント値ｕが０を超えているか否かを判別する（Ｓ１１１）。このカウント値ｔの判別は、一括符号化を行う必要があるかどうかを調べるためのものである。カウント値ｕが０である場合には、Ｓ９３に進む。カウント値ｕが０を超えている場合には、一括チェック部１０ｂから判別結果を得た選択部１０ｃが、まずＭＵＬＭＰＳ２処理部９ｆを選択する旨の選択信号を符号処理部９に出力して、符号処理部９のＭＵＬＭＰＳ２処理部９ｆが、本発明による一括符号化処理であるＣＯＤＥＭＵＬＭＰＳ２処理を実行する（ＣＯＤＥＭＵＬＭＰＳ２を呼ぶ）（Ｓ１１２）。その後、Ｓ９３へ進む。このように、第２の一括符号化画素カウンタ６ｆのカウント値ｕが１以上であれば一括符号化を行う。なお、実際には、今回の近傍形が前回の近傍形と一致するときには第２の一括符号化画素カウンタ６ｆの値は必ず０となるので、Ｓ９２では第２の一括符号化チェックを行う必要はない（Ｓ９４・Ｓ９６・Ｓ９９では第２の一括符号化チェックを行う必要がある）。
【０２０５】
Ｓ１１２のＣＯＤＥＭＵＬＭＰＳ２処理は、本発明において新しく追加された手順である。ＣＯＤＥＭＵＬＭＰＳ２処理は、第１の一括符号化画素カウンタ６ｃのカウント値ｔ、およびＡｒｅｇ６ａの値から、正規化の発生回数、および一括符号化終了時のＡｒｅｇ６ａの値を計算して、一括符号化を行う処理である。ＣＯＤＥＭＵＬＭＰＳ２は、ＣＯＤＥＭＵＬＭＰＳ１と違って、ＳＴの値は常に１３であるから、ＳＴの値は考える必要がなく、簡単な演算処理で実現できる。
【０２０６】
ＣＯＤＥＭＵＬＭＰＳ２処理は、ＬＳＺが最小でない場合、劣勢確率シンボルが与えられる場合、ストライプの終端に達した場合、画像の終端に達した場合、または例えば実装上の都合によってそれ以上一括して圧縮することが好ましくないセルまで達した場合に、そこまでに第１の一括符号化画素カウンタ６ｃに加えられていた個数分の画素を一括して符号化するために用いる。ＣＯＤＥＭＵＬＭＰＳ２処理について、図１８に基づいて説明する。
【０２０７】
まず、Ｓ１１３において、ＭＵＬＭＰＳ２処理部９ｆは、Ａｒｅｇ６ａの値と一括圧縮セルカウンタの値ｔとから、一括圧縮の間に与えられたセルに対して何回の正規化処理が発生するかを調べる。なお、ｔ＝０の場合はこの手順に来ないため、カウンタ値ｔはｔ＞０の整数である。
【０２０８】
ここで、ＬＰＳインターバルの最小値が０．２５より小さい場合には、正規化処理の発生回数と２倍化処理の発生回数は一致する。すなわち、１セルの圧縮を行ったときに劣勢シンボル確率推定の最小値が０．２５より小さいならば、一括圧縮の際にインターバルが０．２５以下となることはない。このため、一回だけ２倍にすれば０．５以上になる。２倍化処理の発生回数が分かれば、以下のように一括圧縮の際の出力やレジスタ等の値の変化を求めることが可能となる。
【０２０９】
なお、通常、ＬＰＳインターバルの最小値は非常に小さな値となり、０．２５よりはるかに小さい値となる。例えば、ＭＰＳが連続する場合の符号化効率を最良にするためには、ＬＰＳインターバルの格納領域のビット数で表現可能な最小の値（"0x1"）を用いる。
【０２１０】
ここで、ＪＢＩＧ圧縮の場合、ITU-T T.82の表２４である確率推定表８からすると、図５（ａ）（ｂ）に示すように、劣勢シンボルの最小の確率推定（ＬＰＳ幅）は、ＳＴ＝１３の場合の"0x0001"である。そこで、一括符号化の開始時点でのＡｒｅｇ６ａの格納値ＡｒｅｇをＡｒｅｇ１とすると、正規化処理回数Ｘｎｏｒは
Ｘｎｏｒ＝（ｔ−（Ａｒｅｇ１−0x8000））／0x7fff      …（１）
となる。なお、小数点以下は切り上げとなる。また、Ｘｎｏｒが０以下の場合には正規化は発生せず、正規化処理は行われない。この式（１）について以下で説明をする。
【０２１１】
まず、ＳＴ＝１３の１つの画素を符号化するということは、Ａｒｅｇ６ａの格納値Ａｒｅｇ（インターバルの大きさ）から"0x0001"を引くことに相当する。このとき、"0x8000"よりＡレジスタの値が小さくなったときには正規化が発生して、Ａｒｅｇ６ａの値Ａｒｅｇが２倍化される。ここで、Ａレジスタからは"0x0001"ずつ引くことになるので、正規化が発生するときのＡレジスタの値は必ず"0x7fff"である。この値を２倍するので、正規化後のＡレジスタの値は必ず"0xfffe"となる。そして、その"0xfffe"からさらに"0x7fff"個符号化するとまた正規化が発生する。
【０２１２】
計算のためには、まず最初にtから（Ａｒｅｇ１−0x8000）を引く。Ａｒｅｇ１が"0x7fff"を超えている分については、符号化を行なっても正規化が発生することはない。さらに、切り上げしたときに正規化の回数が得られるように、Areg1から0x1だけ引くことにする。ここでは、代わりにtに"0x1"だけ足しているので、元々の演算は（（ｔ−（Ａｒｅｇ１−0x7fff））＋0x1）である。
【０２１３】
ここで値が０以下（ｔが１でＡｒｅｇ１＝0x10000ならマイナスになる）になるということは、t個符号化を行なっても(Ａレジスタからtを引いても)Ａレジスタの値は"0x8000"より小さくなることはなく、正規化は発生しないということを意味する。ｔから（Ａｒｅｇ１−0x8000)を引く動作が完了した時点で、1回目の正規化が発生する直前の状態と同じ状態となる。つまり、Ａレジスタの値は"0x8000"であとｔ−（Ａｒｅｇ１−0x8000）個の画素を符号化しなければならない。この状態であと0x1個符号化すると正規化が発生し、次の正規化は0x1＋0x7fff個後に発生し、その次の正規化はさらに0x1+0x7fff+0x7fff個符号化すると発生する。このため、先程のような式(1)となる。
【０２１４】
次に、Ｓ１１４では、ＭＵＬＭＰＳ２処理部９ｆが、得られたＸｎｏｒの数に応じて、Ｘｎｏｒ回だけ、手順ＭＵＬＲＥＮＯＲＭ処理を呼び出す。このＭＵＬＲＥＮＯＲＭ処理については後述する。
【０２１５】
次に、Ｓ１１５においては、ＭＵＬＭＰＳ２処理部９ｆが、正規化処理後のＡｒｅｇ６ａの値（Ａｒｅｇ）であるＡｒｅｇ２（インターバルの大きさ）を、以下のように、正規化処理が行われる前のＡｒｅｇ６ａの値（Ａｒｅｇ）であるＡｒｅｇ１から求める。正規化処理が一度も行われない場合における、一括符号化が終了した時点でのＡｒｅｇ６ａの値Ａｒｅｇ２は、
Ａｒｅｇ２＝Ａｒｅｇ１−ｔ      …（２）
で与えられる。すなわち、インデックスＳＴ＝１３のときにＬＰＳインターバルＬＳＺ（ＬＰＳの推定出現確率）は"0x0001"であるので、１つの画素を符号化するということは、Ａｒｅｇ６ａの値（インターバルの大きさ）から"0x0001"を引くということに対応する。すなわち、正規化処理が行なわれないことが分かっている場合には、Ａｒｅｇ６ａの値の２倍化処理が行なわれることもなく、Ａｒｅｇ−ｔ≧0x8000ということも明らかであるので、単にＡｒｅｇ２＝Ａｒｅｇ１−（ｔ×0x0001）＝Ａｒｅｇ１−ｔとするだけで、一括符号化後のＡｒｅｇ６ａの値Ａｒｅｇ２を求めることができる。
【０２１６】
一方、正規化処理が一度でも行われた場合には、一括符号化が終了した時点でのＡｒｅｇ６ａの値Ａｒｅｇ２は、
Ａｒｅｇ２＝0xfffe−（（ｔ−（Ａｒｅｇ１−0x7fff））mod 0x7fff）      …（３）
で与えられる。ここで、Ａｒｅｇ２＞0x7fffであり、またmodは剰余を表す。
【０２１７】
このように、正規化が発生する場合には、最後の正規化処理を行なった後にまだ処理されていない画素の個数を、正規化が完了した直後のＡｒｅｇ６ａの値0xfffeから引く。ここで、ｔ−（Ａｒｅｇ１−0x7fff）は、1回目の正規化が終わった時点で、まだ処理しなければならない画素の数を表す。この時点（１回目の正規化が終わった時点）のＡｒｅｇ６ａの値は"0xfffe"である。ここから0x7fff個画素を処理するごとに正規化が発生するため、"0x7fff"で割った剰余が最後の正規化が終わった後に処理しなければならない画素数となる。この個数を"0xfffe"から引くことで、一括符号化後のＡｒｅｇ６ａの値Ａｒｅｇ２が得られる。すなわち、
Ａｒｅｇ２＝0xfffe−（（ｔ−（Ａｒｅｇ１−0x7fff））mod 0x7fff）
＝0xfffe−｜（ｔ−Ａｒｅｇ１）mod 0x7fff｜
である。なお、｜ｘ｜はｘの絶対値を表す。
【０２１８】
以上のように、Ｓ１１５では、ＭＵＬＭＰＳ２処理部９ｆが、上記の式（２）または（３）から新しいＡｒｅｇ６ａの値を求め、この値をレジスタ６のＡｒｅｇ６ａに代入する。
【０２１９】
Ｓ１１６において、最小検知部１０ａが、第２の一括符号化画素カウンタ６ｆに０を代入する。
【０２２０】
以上のＳ１１３〜Ｓ１１６にてＣＯＤＥＭＵＬＭＰＳ２処理を終了し、図１５のＳ９５のＣＯＤＥＭＰＳ処理に進む。ＣＯＤＥＭＰＳ処理については、実施の形態１で説明した通りであるので、ここでは説明を省略する。
【０２２１】
Ｓ９３においては、一括チェック部１０ｂが、第１の一括符号化画素カウンタ６ｃのカウント値ｔを１だけインクリメントする。これに応じて、一括チェック部１０ｂからの判別結果を得た選択部１０ｃが選択信号を符号処理部９に送信する。この選択信号は、符号処理部９において符号化をせずに、符号処理部９からコンテクスト生成部２への画素インクリメントのみを行う旨の内容である。なお、符号処理部９は、この時点では符号化しないが、後でまとめて符号化を行う。符号処理部９がコンテクスト生成部２に画素インクリメントのための信号を出力し、Ｓ９８に進む。
【０２２２】
Ｓ９４では、第１及び第２の一括符号化チェックが行われる。その場合には、第１の一括符号化画素カウンタ６ｃおよび第２の一括符号化画素カウンタ６ｆの両方の値を一括チェック部１０ｂでチェックし、第１の一括符号化画素カウンタ６ｃおよび第２の一括符号化画素カウンタ６ｆの何れかが０でなければ、そこまでに一括符号化対象としてカウントされた画素の一括符号化を行う。
【０２２３】
Ｓ９４の第１及び第２の一括符号化チェックについて、図１７に基づいて詳細に説明する。
【０２２４】
まず、一括チェック部１０ｂが、レジスタ６の第１の一括符号化画素カウンタ６ｃにアクセスして、このカウント値ｔが０を超えているか否かを判別する（Ｓ１０１）。このカウント値ｔの判別は、一括符号化を行う必要があるかどうかを調べるためのものである。カウント値ｔが０を超えている場合には、一括チェック部１０ｂから判別結果を得た選択部１０ｃが、まずＭＵＬＭＰＳ１処理部９ｄを選択する旨の選択信号を符号処理部９に出力して、符号処理部９のＭＵＬＭＰＳ１処理部９ｄが、本発明による一括符号化処理であるＣＯＤＥＭＵＬＭＰＳ１処理を実行する（ＣＯＤＥＭＵＬＭＰＳ１を呼ぶ）（Ｓ１０２）。その後、レジスタ６の近傍形記憶領域６ｄに記録（登録）された近傍形を削除し（Ｓ１０３）、Ｓ９５へ進む。このように、第１の一括符号化画素カウンタ６ｃのカウント値ｔが１以上であれば、ＣＯＤＥＭＵＬＭＰＳ１処理を行う。
【０２２５】
一方、カウント値ｔが０である場合には、Ｓ１０４に進む。一括チェック部１０ｂが、レジスタ６の第２の一括符号化画素カウンタ６ｆにアクセスして、このカウント値ｕが０を超えているか否かを判別する（Ｓ１０４）。このカウント値ｔの判別は、一括符号化を行う必要があるかどうかを調べるためのものである。カウント値ｕが０である場合には、Ｓ９５に進む。カウント値ｕが０を超えている場合には、一括チェック部１０ｂから判別結果を得た選択部１０ｃが、まずＭＵＬＭＰＳ２処理部９ｆを選択する旨の選択信号を符号処理部９に出力して、符号処理部９のＭＵＬＭＰＳ２処理部９ｆが、本発明による一括符号化処理であるＣＯＤＥＭＵＬＭＰＳ２処理を実行する（ＣＯＤＥＭＵＬＭＰＳ２を呼ぶ）（Ｓ１０５）。その後、Ｓ９５へ進む。このように、第２の一括符号化画素カウンタ６ｆのカウント値ｕが１以上であれば、ＣＯＤＥＭＵＬＭＰＳ２処理を行う。
【０２２６】
Ｓ９４の第１及び第２の一括符号化チェックの後、Ｓ９５では、符号処理部９のＭＰＳ処理部９ａが、通常のＱＭ−Ｃｏｄｅｒと同じ手順でＣＯＤＥＭＰＳ処理（ＭＰＳの符号化）を行う。このＣＯＤＥＭＰＳ処理は、実施の形態１で説明した通りであるので、その説明を省略する。
【０２２７】
Ｓ８６において対象画素の値（入力ビット）がＬＰＳであった場合に、Ｓ９６では、第１及び第２の一括符号化チェックを行い、Ｓ９７に進む。この第１及び第２の一括符号化チェックは、Ｓ９４で行うものと同様であるので、説明は省略する。
【０２２８】
Ｓ９７では、符号処理部９のＬＰＳ処理部９ｂが、ＣＯＤＥＬＰＳ処理を行う。ＣＯＤＥＬＰＳ処理が終了すると、Ｓ９８に進む。このＣＯＤＥＬＰＳ処理は、実施の形態１で説明した通りであるので、その説明を省略する。
【０２２９】
以上のようにして、第２の一括符号化画素カウンタ６ｆへの加算（Ｓ８９）、第１の一括符号化画素カウンタ６ｃへの加算（Ｓ９３）、ＣＯＤＥＭＰＳ処理（Ｓ９５）、またはＣＯＤＥＬＰＳ処理（Ｓ９７）が完了すると、画素のループ（ＬＯＯＰ２）の終端（Ｓ８３にて選択した対象画素についての処理の終わりを示す）であるＳ９８に進む。
【０２３０】
Ｓ９８では、符号処理部９がコンテクスト生成部２に画素インクリメントのための信号を出力する。コンテクスト生成部２では、対象となる画素を更新しようとしたときに、画素がストライプの終点にきており、対象画素を更新できないかどうかを判別する。対象画素がストライプの終点にきており、対象画素を更新できない場合には次のＳ９９に進み、対象画素がストライプの終点にきておらず、対象画素を更新できる場合には画素のループ（ＬＯＯＰ２）の先頭Ｓ８３へと戻り、次の画素の符号化へと移る。
【０２３１】
ストライプ内の全ての画素の符号化が完了したら、Ｓ９９で、本実施形態のようにストライプごとに処理を行う場合に、対象画素がストライプの終点にきた時点で符号化していない未処理の画素（一括符号化すべき画素）の有無を判別する。一括符号化すべき画素があれば、一括符号化すべき画素の一括符号化を行う。すなわち、Ｓ９９では、第１及び第２の一括符号化チェックを行う。すなわち、第１の一括符号化画素カウンタ６ｃおよび第２の一括符号化画素カウンタ６ｆの両方の値を一括チェック部１０ｂでチェックし、第１の一括符号化画素カウンタ６ｃおよび第２の一括符号化画素カウンタ６ｆの何れかが０でなければ、残った一括符号化すべき画素の一括符号化を行う。この第１及び第２の一括符号化チェックは、Ｓ９４で行うものと同様であるので、説明は省略する。
【０２３２】
Ｓ１００では、レジスタ６のＣｒｅｇ６ｂに保存されている、符号化結果としてのインターバルの低数を、符号化データとして算術符号化装置１の外部へと出力する、フラッシュ処理を行う。
【０２３３】
Ｓ１０００は、Ｓ１にて選択したストライプについての処理の終わりを示すものである。Ｓ１００においては、符号化が完了していないストライプがあるか否かを判別し、符号化が完了していないストライプがあると判別した場合には、このストライプのループ（ＬＯＯＰ）の最後Ｓ１００からストライプのループ（ＬＯＯＰ）の先頭Ｓ１に戻って、次のストライプの符号化に移る（コンテクスト生成部２が新たなストライプを選択する）。全てのストライプの符号化が完了していれば、画像全体の符号化を完了する。
【０２３４】
ここで、一括符号化チェックについて、補足的に説明する。算術符号化装置１１においては、第１の一括符号化画素カウンタ６ｃと第２の一括符号化画素カウンタ６ｆとの２つの画素カウンタを使用するため、一括符号化チェックには、（１）第１の一括符号化画素カウンタ６ｃのカウント値ｔのみが０かどうかをチェックし、０でなければ一括符号化を行う第１の一括符号化チェックと、第２の一括符号化画素カウンタ６ｆのカウント値ｕのみをチェックし、０でなければ一括符号化を行う第２の一括符号化チェック、および第１の一括符号化画素カウンタ６ｃのカウント値ｔと第２の一括符号化画素カウンタ６ｆのカウント値ｕとの両方をチェックし、何れかが０でなければ一括符号化を行う第１及び第２の一括符号化チェックの３通りがある。一括符号化は、第１の一括符号化画素カウンタ６ｃによって計数された一括符号化対象画素については、本発明による方法に基づいてＣＯＤＥＭＵＬＭＰＳ１を呼び出して行い、第２の一括符号化画素カウンタ６ｆによって計数された一括符号化対象画素については、特願２００４−１８５６８による方法に基づいてＣＯＤＥＭＵＬＭＰＳ２を呼び出して一括符号化を行う。なお、第１の一括符号化画素カウンタ６ｃおよび第２の一括符号化画素カウンタ６ｆは、少なくとも一方が０であるため、どちらか一方に０以外の値が入っていればもう一方は０であると分かる。
【０２３５】
ここで、上述の実施の形態２の算術符号化装置１１において、すでに劣勢確率シンボルの確率推定が最小になっていれば、正規化の発生にもかかわらず、それ以上劣勢確率シンボルの確率推定は減少しない点について、説明を補足する。
【０２３６】
ＪＢＩＧ圧縮における確率推定の値（ＬＳＺ）は、確率推定表８から、確率推定のインデックスＳＴを用いて参照される。すなわち、ＳＴがある値であったときの確率推定は、確率推定表８のＳＴに対応する行のＬＳＺから求めることができる。例えば、ＳＴ＝０のときは確率推定値ＬＳＺは"0x5a1d"となり、ＳＴ＝１３のときにはＬＳＺは"0x0001"となる。また、確率推定表８から、優勢確率シンボルを符号化して、かつ正規化が発生した場合の次のＳＴの値であるＮＭＰＳや、劣勢確率シンボルを符号化した場合の次のＳＴの値であるＮＬＰＳを求めることができる。
【０２３７】
ここで、劣勢確率シンボルを符号化した場合には、毎回正規化が発生してＳＴが変化する。一方、優勢確率シンボルを符号化した場合には、Ａレジスタの値から確率推定を減算して、Ａレジスタの値が"0x8000"より小さくなった場合にのみ正規化が発生してＳＴが変化する。
【０２３８】
ここで、表中の確率推定値ＬＳＺを見ると、確率推定はＬＳＺ＝0x0001となるＳＴ＝１３のときが最小値となる。また、ＳＴ＝１３のところのＮＭＰＳを見ると１３となっており、ＳＴ＝１３のときに優勢確率シンボルを符号化して、正規化が発生してもＳＴは変化しない。このことから、確率推定のインデックスＳＴが変化しないと、確率推定も変化しないことになる。
【０２３９】
本来、算術符号化の考え方からすると、優勢確率シンボルが出現し続けている場合には、劣性確率シンボルの出願確率はどんどん小さくすることになる。しかしながら、実際の符号化に応用する場合には、レジスタの幅などデジタルで表現できる精度に限りがあるため、ＪＢＩＧでは上記のようにしている。すなわち、上記のように、劣勢確率シンボルの確率推定が最小になっていれば、それ以上劣勢確率シンボルの確率推定は減少しない。
【０２４０】
以上のように、本実施形態の算術符号化装置１１によれば、簡単な演算で、任意個のＭＰＳを一括符号化した際のパラメータの変化とその際の符号化出力とを求めることが可能となり、通常の手順で符号化を行った場合と同じ出力を一括符号化によって得ることができる。本実施形態の算術符号化装置１１によれば、実施の形態１の算術符号化装置１と同様に、ＬＰＳインターバルの推定値が０．２５以下で、同じ近傍形を持つＭＰＳが連続する場合に、実施の形態１と同様の一括符号化であるＣＯＤＥＭＵＬＭＰＳ１処理を行うのに加えて、ＬＰＳインターバルの推定値が最小値となった後は、ＣＯＤＥＭＵＬＭＰＳ１処理と比較して簡素な一括符号化処理であるＣＯＤＥＭＵＬＭＰＳ２処理を行う。これによって、ＬＰＳインターバルの推定値が最小値となった後の一括符号化処理に係る演算量を削減することができるので、符号化をより高速化することができる。
【０２４１】
また、上述の算術符号化装置１１によれば、ＬＰＳインターバルの推定値が最小値となった後は、複数の高速化可能なコンテクストが混在する場合でも、ＬＰＳインターバルの推定値が最小の下限値であるという条件を満たしていればコンテクストのパターンについて制限が無く、あらゆるコンテクストのパターンについて高速化の対象とし得る。
【０２４２】
すなわち、算術符号化装置１１によれば、ＬＰＳインターバルの推定値が最小値となっているという条件を満たしていれば、近傍形の中のパターンは何であっても高速化を行うことができる。例えば、２ラインテンプレートを使用している場合に、コンテクスト中の全ての画素の値が０か、または１が２つ以下しか含まれていないあらゆるコンテクストについてＬＰＳインターバルの推定値が最小値（インデックスＳＴ＝１３）となっている場合に、
００００１０００
００００１０００
という入力列が与えられたとする。そして、上のラインについては符号化完了しており、下のラインを今から符号化するものとする。さらに、下のラインは、全て近傍形に対する優勢確率シンボルであるとする。この場合、算術符号化装置１１を用いて符号化すれば、符号化を中断することなく、ライン全体を一括して符号化することができる。このように、複数のコンテクストが混在する状況でも高速化が行なえる。
【０２４３】
上述した本発明の構成を使用して符号化を行なった場合でも、符号化結果は通常の一括符号化を行わない方法で符号化を行った場合と同じである。このため、復号化装置に関しては特別な機構は必要ない。例えば、符号化装置をプリンタドライバに用いる構成であっても、プリンタ側の復号化装置には特別な機構は不要である。
【０２４４】
本発明は、上述した各実施形態に限定されるものではなく、請求項に示した範囲で種々の変更が可能であり、異なる実施形態にそれぞれ開示された技術的手段を適宜組み合わせて得られる実施形態についても本発明の技術的範囲に含まれる。
【０２４５】
例えば、実施の形態２では、第１の一括符号化画素カウンタ６ｃおよび第２の一括符号化画素カウンタ６ｆの２つのカウンタを用いていたが、それに代えて、一括符号化画素カウンタは１つだけで、フラグを使ってこの一括符号化画素カウンタのカウント値を切り替えることにより第１の一括符号化画素カウンタ６ｃおよび第２の一括符号化画素カウンタ６ｆと同等の機能を持たせても良い。なぜなら、第１の一括符号化画素カウンタ６ｃと第２の一括符号化画素カウンタ６ｆとの２つの画素カウンタを同時に使用することはない、つまり、常に第１の一括符号化画素カウンタ６ｃと第２の一括符号化画素カウンタ６ｆとの少なくとも一方の値は０であるためである。
【０２４６】
例えば、実施の形態２に係る劣勢シンボルのインターバルの推定値が最小値である場合に一括符号化を行う符号化方法は、劣勢シンボルのインターバルの推定値が最小値を持ち、一旦最小値になれば優勢シンボルが与えられる限り劣勢シンボルのインターバルの推定値の値が変化しないという性質を満たすものであれば、ＪＢＩＧに限らず適用できる。言い換えると、実施の形態２に係る発明は、劣勢シンボルのインターバルの推定値が下限値を持ち、劣勢シンボルのインターバルの推定値が下限値に達した状態でＭＰＳ入力を受けても劣勢シンボルのインターバルの推定値が変化しない算術符号化であれば、適用できる。また、上述の実施の形態で挙げている式（正規化の発生回数や正規化後のパラメータ計算の式）を使って正規化の発生をシミュレーションするためには、インターバル全体の取り得る最小値がＬＳＺの最小値の２倍より大きいことが必要である。もしそうでなければ、一回の正規化で２回以上の２倍化処理が発生する可能性があるため、実施例に挙げた式は使えない。ＪＢＩＧのＱＭ−ｃｏｄｅｒはこの基準を満たし、またＬＳＺの最小値がインターバルの最小値の半分以上という算術符号化はまず考えられないため、実際には、ほとんどの算術符号化に応用可能と考えられる。
【０２４７】
また、上述の実施の形態２においては、確率推定テーブル７にコンテクストごとのＭＰＳ（１ビット）とＬＳＺのインデックスＳＴ（７ビット）が保存され、ＬＰＳインターバルが最小値となっているか否かを最小検知部１０ａにおいてインデックスＳＴを用いて判別する構成について説明したが、本発明はこれに限るものではない。
【０２４８】
例えば、確率推定テーブル７に、コンテクストごとのＭＰＳ（１ビット）とＬＳＺのインデックスＳＴ（７ビット）に加えて、ＬＰＳインターバルが最小値となっているかどうかを示す１ビット（最小ＬＰＳインターバル判定ビット）を保存する構成であってもよい。あるコンテクストと優勢確率シンボルに対してＬＰＳインターバルが最小であることが認識された場合には、確率推定テーブルのそのコンテクストに対する最小ＬＰＳインターバル判定ビットを１とする。また、あるコンテクストに対して劣勢確率シンボルが与えられた場合には最小ＬＰＳインターバル判定ビットを０とする。なお、通常は符号化開始の時点でＬＰＳインターバルが最小となっていることはないので、各コンテクストに対して最小ＬＰＳインターバル判定ビットに初期値０を与えるが、符号化開始時点でＬＰＳインターバルが最小となることがあるような算術符号化方式ではＬＰＳインターバルが最小となっているコンテクストに対してのみ初期値０，１のどちらを与えても構わない。ＬＳＺの最小値に対応するＬＳＺのインデックスを確率推定テーブルに書き込むことが、最小ＬＰＳインターバル判定ビットに１を入れる（高速化可能であると記録する）ことと同じ効果を持つ。ＬＳＺの最小値に対応しないＬＳＺのインデックスを確率推定テーブルに書き込むことが、最小ＬＰＳインターバル判定ビットに０を入れる（高速化できないと記録する）ことと同じ効果を持つと考えることができる。ただし、確率推定テーブルに最小ＬＰＳインターバル判定ビットを追加すると、各コンテクストに対して９ビット（ＬＳＺのインデックス７ビット、ＭＰＳが１ビット、ＬＰＳインターバル判定ビットが１ビット）の情報を保持しなければならなくなる。このため、記録部５に必要となる記録容量を増大させてしまう。
【０２４９】
また、各コンテクストに対する情報を１バイト（８ビット）のままとするためには、例えばＬＰＳインターバル判定ビットを残したまま、ＬＳＺのインデックスを６ビットで扱うことになる。これは、ＬＳＺのインデックスとして用いることのできる範囲が半分となってしまい、不都合である。上記実施の形態のように、ＬＰＳインターバル判定ビットを利用しない構成であれば、この不都合を回避できる。この場合であっても、ＬＳＺのインデックスの値を参照すれば、ＬＳＺが最小になっているかどうかは分かるので、問題はない。
【０２５０】
また、上述の各実施の形態においては、簡単のために最低解像度レイヤのみを持つＪＢＩＧ圧縮について説明したが、これに限るものではなく、複数の解像度レイヤを持つプログレッシブなＪＢＩＧ圧縮に対しても応用できる。
【０２５１】
また、上述の各実施の形態は、ＪＢＩＧに使用されているＱＭ−ｃｏｄｅｒに適用したものであったが、上述の各実施の形態は、ＪＢＩＧ２に使用されているＭＱ−ｃｏｄｅｒにもそのまま適用できる。ただし、ＭＱ−ｃｏｄｅｒに使用されている確率推定表は、ＱＭ−ｃｏｄｅｒに使用されている確率推定表とは異なっているため、劣勢確率シンボルのインターバルが最低となるインデックスＳＴの値は、１３ではなく４５となる。
【０２５２】
また、上述の実施の形態においては、本発明を２値画像データの圧縮に適用した場合について説明したが、多値画像データの圧縮であっても、適応型の算術圧縮を使用しているならば、本発明を利用して圧縮の高速化を図ることができる。多値画像の場合であっても、画像データが０と１のビット列で表されていることに変わりはなく、たとえば１画素を８ビットで表す画像データであれば幅が８倍になった２値画像データと考えることができる。この場合、必要に応じて近傍形の参照パターンを変更すればよい。また、必要に応じて確率推定表の内容を変更すればよい。その場合、劣勢確率シンボルのインターバルが最低となるインデックスＳＴの値が変化する可能性はあるが、それ以外の点では２値画像データの場合と変化はない。そのため、２値画像データの場合と同様に、一括符号化による圧縮の高速化を図ることができる。さらに、文字データ等のような画像データ以外のデータであっても、統計的な予測に基づく算術符号化によってデータを圧縮することができるものであれば、本発明を適用できる。
【０２５３】
また、説明を簡単にするため、コンテクストの形状を変化させるＡＴ移動などＪＢＩＧの仕様に含まれる付加的な機能に関しても説明を省略したが、本発明における符号化高速化方式はＡＴ移動を伴うＪＢＩＧ圧縮に対しても応用可能である。ここで、ＡＴ（Adaptive Template）移動とは、ＪＢＩＧ圧縮の仕様に含まれている特殊な操作である。符号化において必須のものではなく、ＡＴ移動を行なわないようにすることもできる。通常、コンテクストの形（テンプレート）は一定で符号化中に変化することはないが、ＡＴ移動を使用する場合にはコンテクストの形そのものが変化する。ＡＴ移動するかどうか、いつＡＴ移動するかは符号化する側で決めることができるため、本発明はＡＴ移動の有無に関わらず適用することができる。ただし、一括符号化中にＡＴ移動させることはできない。
【０２５４】
また、上記各実施形態では、本発明にかかる第３の条件は「レジスタ６の近傍形記憶領域６ｄに直前の符号化対象画素のコンテクストが保存されていないか、あるいは保存されている直前の符号化対象画素のコンテクストに現在の符号化対象画素のコンテクストが一致している」条件であったが、「符号化対象シンボルがシンボル列の２番目以降のシンボルであり、かつ、符号化対象シンボルにおける劣勢確率シンボルのインターバルが、符号化対象シンボルの直前のシンボルにおける劣勢確率シンボルのインターバルと同一であるか、あるいは、符号化対象のシンボルが、全シンボル列の最初のシンボルまたは一括符号化直後のシンボルである」という条件であれば、他の条件であってもよい。
【０２５５】
また、上記各実施形態では、算術符号化装置を構成する各部が、「ＣＰＵなどの演算手段がＲＯＭやＲＡＭなどの記録媒体に格納されたプログラムコードを実行することで実現される機能ブロックである」場合を例にして説明したが、同様の処理を行うハードウェアで実現してもよい。また、処理の一部を行うハードウェアと、当該ハードウェアの制御や残余の処理を行うプログラムコードを実行する上記演算手段とを組み合わせても実現することもできる。さらに、上記各部材のうち、ハードウェアとして説明した部材であっても、処理の一部を行うハードウェアと、当該ハードウェアの制御や残余の処理を行うプログラムコードを実行する上記演算手段とを組み合わせても実現することもできる。なお、上記演算手段は、単体であってもよいし、装置内部のバスや種々の通信路を介して接続された複数の演算手段が共同してプログラムコードを実行してもよい。
【０２５６】
上記演算手段によって直接実行可能なプログラムコード自体、または、後述する解凍などの処理によってプログラムコードを生成可能なデータとしてのプログラムは、当該プログラム（プログラムコードまたは上記データ）を記録媒体に格納し、当該記録媒体を配付したり、あるいは、上記プログラムを、有線または無線の通信路を介して伝送するための通信手段で送信したりして配付され、上記演算手段で実行される。
【０２５７】
なお、通信路を介して伝送する場合、通信路を構成する各伝送媒体が、プログラムを示す信号列を伝搬し合うことによって、当該通信路を介して、上記プログラムが伝送される。また、信号列を伝送する際、送信装置が、プログラムを示す信号列により搬送波を変調することによって、上記信号列を搬送波に重畳してもよい。この場合、受信装置が搬送波を復調することによって信号列が復元される。一方、上記信号列を伝送する際、送信装置が、デジタルデータ列としての信号列をパケット分割して伝送してもよい。この場合、受信装置は、受信したパケット群を連結して、上記信号列を復元する。また、送信装置が、信号列を送信する際、時分割／周波数分割／符号分割などの方法で、信号列を他の信号列と多重化して伝送してもよい。この場合、受信装置は、多重化された信号列から、個々の信号列を抽出して復元する。いずれの場合であっても、通信路を介してプログラムを伝送できれば、同様の効果が得られる。
【０２５８】
ここで、プログラムを配付する際の記録媒体は、取外し可能である方が好ましいが、プログラムを配付した後の記録媒体は、取外し可能か否かを問わない。また、上記記録媒体は、プログラムが記憶されていれば、書換え（書き込み）可能か否か、揮発性か否か、記録方法および形状を問わない。記録媒体の一例として、磁気テープやカセットテープなどのテープ、あるいは、フロッピー（登録商標）ディスクやハードディスクなどの磁気ディスク、または、ＣＤ−ＲＯＭや光磁気ディスク（ＭＯ）、ミニディスク（ＭＤ）やデジタルビデオディスク（ＤＶＤ）などのディスクが挙げられる。また、記録媒体は、ＩＣカードや光カードのようなカード、あるいは、マスクＲＯＭやＥＰＲＯＭ、ＥＥＰＲＯＭまたはフラッシュＲＯＭなどのような半導体メモリであってもよい。あるいは、ＣＰＵなどの演算手段内に形成されたメモリであってもよい。
【０２５９】
なお、上記プログラムコードは、上記各処理の全手順を上記演算手段へ指示するコードであってもよいし、所定の手順で呼び出すことで、上記各処理の一部または全部を実行可能な基本プログラム（例えば、オペレーティングシステムやライブラリなど）が既に存在していれば、当該基本プログラムの呼び出しを上記演算手段へ指示するコードやポインタなどで、上記全手順の一部または全部を置き換えてもよい。
【０２６０】
また、上記記録媒体にプログラムを格納する際の形式は、例えば、実メモリに配置した状態のように、演算手段がアクセスして実行可能な格納形式であってもよいし、実メモリに配置する前で、演算手段が常時アクセス可能なローカルな記録媒体（例えば、実メモリやハードディスクなど）にインストールした後の格納形式、あるいは、ネットワークや搬送可能な記録媒体などから上記ローカルな記録媒体にインストールする前の格納形式などであってもよい。また、プログラムは、コンパイル後のオブジェクトコードに限るものではなく、ソースコードや、インタプリトまたはコンパイルの途中で生成される中間コードとして格納されていてもよい。いずれの場合であっても、圧縮された情報の解凍、符号化された情報の復号、インタプリト、コンパイル、リンク、または、実メモリへの配置などの処理、あるいは、各処理の組み合わせによって、上記演算手段が実行可能な形式に変換可能であれば、プログラムを記録媒体に格納する際の形式に拘わらず、同様の効果を得ることができる。
【０２６１】
なお、本発明は、以下のようにも表現できる。
【０２６２】
（１）算術符号化において、ＬＰＳのインターバルの値がある値以下となったときに圧縮をスキップして後でまとめて圧縮を行うことを特徴とする算術符号化方法。（算術符号化では、ＬＰＳインターバルがある値以下となると、ＭＰＳ符号化時にＭＰＳとＬＰＳの入れ替えが発生する可能性がなくなるため、一括して圧縮することができる。）
（２）上記（１）の算術符号化方法において、ある値が0x4000または０．２５又はそれに相当する値である算術符号化方法。（ＬＰＳインターバルが0x4000＝０．２５以下であれば、ＭＰＳ符号化時にＭＰＳとＬＰＳの入れ替えが発生する可能性がなくなる。)
（３）上記（１）の算術符号化方法において、算術符号化の実装形態がＱＭ−ｃｏｄｅｒである算術符号化方法。（ＪＢＩＧ圧縮では、ＬＰＳインターバルが0x4000以下であれば、正規化発生時の２倍化処理が１回しか発生しないメリットもある。）
（４）算術符号化方法において、ＬＳＺが最小値となった場合に一括圧縮を行う算術符号化方法と上記（１）の算術符号化方法とを組み合わせる算術符号化方法。（本発明の方法でＳＴ＝１３となるまで一括圧縮を行い、ＳＴ＝１３となってからは特願２００４−１８５６８の圧縮高速化方法で一括圧縮を行うことでさらに高速化が期待できる。）
【産業上の利用可能性】
【０２６３】
本発明は、ファクシミリ装置（ＦＡＸ）やプリンタ、パーソナルコンピュータのプリンタドライバ等における画像データの圧縮（ＪＢＩＧやＪＢＩＧ２等）に特に有効であり、特に印刷ドキュメントを画像に変換したものをプリンタに送信する際の画像データ圧縮を高速化するのに有効である。
【図面の簡単な説明】
【０２６４】
【図１】本発明に係る符号化装置の一実施の形態を示すブロック図である。
【図２】上記符号化装置にて行う算術符号化を説明するための概念図である。
【図３】上記符号化装置にて符号化を行う対象画素と、その画素についてのコンテクストの一例を示す平面図である。
【図４】上記符号化装置にて用いる確率推定テーブルの一例を示す図である。
【図５】（ａ）は上記符号化装置にて用いる確率推定表の一例の一部を示す図であり、（ｂ）は上記確率推定表の他の一部を示す図である。
【図６】上記符号化装置にて行う符号化処理の概略を示すフローチャートである。
【図７】上記符号化装置にて行う符号化処理の一部を示すフローチャートである。
【図８】上記符号化装置にて行う符号化処理の他の一部を示すフローチャートである。
【図９】上記符号化装置にて行う符号化処理のさらに他の一部を示すフローチャートである。
【図１０】上記符号化装置にて行う符号化処理のさらに他の一部を示すフローチャートである。
【図１１】上記符号化装置にて行う符号化処理のさらに他の一部を示すフローチャートである。
【図１２】上記符号化装置にて行う符号化処理のさらに他の一部を示すフローチャートである。
【図１３】上記符号化装置にて行う符号化処理のさらに他の一部を示すフローチャートである。
【図１４】本発明に係る符号化装置の他の実施の形態を示すブロック図である。
【図１５】上記符号化装置にて行う符号化処理の概略を示すフローチャートである。
【図１６】上記符号化装置にて行う符号化処理の一部を示すフローチャートである。
【図１７】上記符号化装置にて行う符号化処理の他の一部を示すフローチャートである。
【図１８】上記符号化装置にて行う符号化処理のさらに他の一部を示すフローチャートである。
【図１９】従来の符号化装置の一例を示すブロック図である。
【図２０】従来の符号化装置にて行う符号化処理の概略を示すフローチャートである。
【符号の説明】
【０２６５】
１    算術符号化装置
２    コンテクスト生成部
３    取得部
４    算術符号化部
５    記録部
６    レジスタ
６ａ  Ｃｒｅｇ
６ｂ  Ｃｒｅｇ
６ｃ  第１の一括符号化画素カウンタ
６ｄ  近傍形記憶領域
６ｄ  出力ビットカウンタ
６ｅ  出力ビットカウンタ
６ｆ  第２の一括符号化画素カウンタ
７    確率推定テーブル
８    確率推定表
９    符号処理部
９ａ  ＭＰＳ処理部
９ｂ  ＬＰＳ処理部
９ｃ  ＲＥＮＯＲＭ処理部
９ｄ  ＣＯＤＥＭＵＬＭＰＳ処理部
９ｅ  ＭＵＬＲＥＮＯＲＭ処理部
１０    前処理部
１０ａ  ＬＳＺ検知部
１０ａ  最小検知部
１０ｂ  一括チェック部
１０ｃ  選択部
１０ｄ  近傍形検知部
１０ｅ  最小検知部
１１    算術符号化装置
１４    算術符号化部
１６    レジスタ
１９    符号処理部
２０    前処理部
【図１】
2005348155.tif 000003
【図２】
2005348155.tif 000004
【図３】
2005348155.tif 000005
【図４】
2005348155.tif 000006
【図５】
2005348155.tif 000007
【図６】
2005348155.tif 000008
【図７】
2005348155.tif 000009
【図８】
2005348155.tif 000010
【図９】
2005348155.tif 000011
【図１０】
2005348155.tif 000012
【図１１】
2005348155.tif 000013
【図１２】
2005348155.tif 000014
【図１３】
2005348155.tif 000015
【図１４】
2005348155.tif 000016
【図１５】
2005348155.tif 000017
【図１６】
2005348155.tif 000018
【図１７】
2005348155.tif 000019
【図１８】
2005348155.tif 000020
【図１９】
2005348155.tif 000021
【図２０】
2005348155.tif 000022