(57)【特許請求の範囲】
【請求項１】
２値の入力信号からなる入力信号列を、各入力信号に対して定められた優勢確率シンボルと、各入力信号に対して定められた劣勢確率シンボルが当該入力信号として出現する出現確率の推定値とを用いて圧縮する算術圧縮方法において、
上記入力信号列のうち、優勢確率シンボルに一致し、かつ、劣勢確率シンボルの出現確率の推定値が予め設定された下限値に一致する入力信号からなる入力信号群を一括して符号化する一括符号化工程を含んでおり、
上記一括符号化工程は、上記入力信号群を一括して符号化することにより得られる部分符号化データの末尾において特定値が連続する部分のバイト数を算出するバイト数算出工程と、算出されたバイト数分の上記特定値を上記部分符号化データの一部として一括して出力する一括出力工程と、を含んでいることを特徴とする算術圧縮方法。
【請求項２】
上記一括符号化工程は、上記部分符号化データにおいて上記特定値が連続する部分を除いた残りの部分を１バイトずつ出力する逐次出力工程を更に含んでいる、
ことを特徴とする、
請求項１に記載の算術圧縮方法。
【請求項３】
上記逐次出力工程において出力する部分は、上記部分符号化データの上位５バイトであることを特徴とする、
請求項２に記載の算術圧縮方法。
【請求項４】
上記一括符号化工程は、
上記部分符号化データを表すインターバルの大きさと上記一括セルカウンタとに基づいて正規化回数ｎを算出する正規化回数算出工程と、
上記インターバルを２倍する回数と上記正規化回数とに基づいてカウンタＣＴの値を算出するカウンタ算出工程と、を含んでおり、
上記バイト数算出工程は、上記正規化回数算出工程において算出された正規化回数ｎと、上記カウンタ算出工程において算出された上記カウンタＣＴの値とに基づいて、上記部分符号化データにおいて上記特定値が連続する部分のバイト数を算出する工程である、
ことを特徴とする、
請求項１から３までの何れか１項に記載の算術圧縮方法。
【請求項５】
上記バイト数算出工程は、上記部分符号化データの総バイト数を、
（ｎ／８）＋（ｘ  ＜＝（ｎ  ｍｏｄ  ８））（ｘは上記一括符号化工程開始時における上記カウンタＣＴの値）
によって算出する総バイト数算出工程を含んでいることを特徴とする、
請求項４に記載の算術圧縮方法。
【請求項６】
上記バイト数算出工程は、上記部分符号化データにおいて上記特定値が連続する部分を除いた残りの部分のバイト数を、上記総バイト数算出工程において算出された総バイト数から減算することによって、上記部分符号化データにおいて上記特定値が連続する部分のバイト数を算出する、ことを特徴とする、
請求項５に記載の算術圧縮方法。
【請求項７】
上記カウンタ算出工程は、当該一括符号化工程終了時点で上記カウンタＣＴの値を、
ＣＴ＝８−（｜ｎ−ｘ｜  ｍｏｄ  ８）（ｘは上記一括符号化工程開始時における上記カウンタＣＴの値）
に基づいて更新することを特徴とする、
請求項４から６までの何れか１項に記載の算術圧縮方法。
【請求項８】
２値の入力信号からなる入力信号列を、各入力信号に対して定められた優勢確率シンボルと、各入力信号に対して定められた劣勢確率シンボルが当該入力信号として出現する出現確率の推定値とを用いて圧縮する算術圧縮装置において、
上記入力信号列のうち、優勢確率シンボルに一致し、かつ、劣勢確率シンボルの出現確率の推定値が予め設定された下限値に一致する入力信号からなる入力信号群を一括して符号化する一括符号化手段を備えており、
上記一括符号化手段は、上記入力信号群を一括して符号化することにより得られる部分符号化データの末尾において特定値が連続する部分のバイト数を算出するバイト数算手段と、算出されたバイト数分の上記特定値を上記部分符号化データの一部として一括して出力する一括出力手段と、を備えていることを特徴とする算術圧縮装置。
【請求項９】
請求項８に記載の算術圧縮装置を動作させるプログラムであって、コンピュータを上記の各手段として機能させるための算術圧縮プログラム。
【請求項１０】
請求項９に記載の算術圧縮プログラムを記録しているコンピュータ読み取り可能な記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は算術圧縮方法、及び算術圧縮装置に関する。また、コンピュータを算術圧縮装置として動作させるプログラム、及び、そのプログラムを記録した記録媒体に関する。
【背景技術】
【０００２】
２値画像をマルコフ情報源でモデル化し、符号化シンボルをその周辺画素の状態によって予測し、予測結果を算術圧縮（算術符号化）する方式としてＪＢＩＧ（ＩＴＵ−Ｔ  Ｔ．８２）のＱＭ−Ｃｏｄｅｒが知られている（非特許文献１、２参照）。
【０００３】
ＱＭ−Ｃｏｄｅｒについて説明する前に、まず算術圧縮の概念について説明する。算術圧縮は、入力信号列を０以上１未満の実数ｘに変換する（圧縮結果は非常に長い一つの小数となる）。この変換は次のように行なわれる。
【０００４】
現時点までの入力に対して実数ｘの存在しうる範囲をインターバルという。まだ１ビットも入力が行なわれていない時点では、明らかにインターバルは０以上１未満の区間となる。
【０００５】
インターバルは２つに分割される。現時点までの入力信号列（入力ビット列）から次の入力信号（入力ビット）を予測し、出現すると予想された入力信号は優勢確率シンボル（ＭＰＳ）となり、予想されなかった入力信号は劣勢確率シンボル（ＬＰＳ）となる。インターバルを優勢確率シンボルの出現確率と劣勢確率シンボルの出現確率の比によって分割する。インターバルを分割する際には、０により近い方を優勢確率シンボルの出現確率とし、これをＭＰＳインターバル、０から遠い方をＬＰＳインターバルと呼ぶ。
【０００６】
１ビットの入力が行なわれると、そこまでの入力から予測していた値（優勢確率シンボル）との比較が行なわれ、一致する場合にはインターバルからＬＰＳインターバルが取り除かれる。一致しない場合にはインターバルからＭＰＳインターバルが取り除かれる。インターバルは大きさと低数（その時点でのインターバルの最小値）で記憶されているため、インターバルからＬＰＳを取り除く操作はインターバル全体の大きさからＬＰＳインターバルの大きさを引くことで実現でき、インターバルからＭＰＳを取り除く操作はインターバル全体の大きさからＭＰＳインターバルの大きさを引く操作と低数にＭＰＳインターバルの大きさを加える操作によって実現できる。
【０００７】
全ての入力信号に対する処理が完了したときのインターバルの低数が実数ｘ（圧縮結果）となる。
【０００８】
ここで、入力信号が予想される入力信号と一致する場合には低数に変化が生じないことから、出力（圧縮結果）にも変化が生じず、新たなビットを出力する必要がない。算術圧縮はこのことを利用して圧縮を行なうものである。
【０００９】
たとえば０００１のような入力が与えられ、そのときの優勢確率シンボル（ＭＰＳ）が０１０１であった場合には、圧縮結果ｘは図９のようにして求められる。２ビット目の入力は劣勢確率シンボルであるから、ＬＰＳインターバルが選択され、その他は優勢確率シンボルであるからＭＰＳのインターバルが選択される。
【００１０】
もし、全ての入力が優勢確率シンボルであれば圧縮結果ｘは０となる。
【００１１】
以上のような圧縮処理を計算機上で実行するために、ＱＭ−Ｃｏｄｅｒにおいてはインターバルの大きさ、及び、インターバルの低数を固定精度の整数で近似して、それぞれレジスタＡ、及び、レジスタＣに保持するようにしている。
【００１２】
レジスタＡにはインターバルの大きさ（より厳密には、インターバルの大きさを２16した値）が入る。しかし、上述の算術圧縮処理を実行していくとインターバルの大きさはどんどん小さくなり、やがて固定精度では表現できなくなってしまう。そこで、レジスタＡには大きさが０．５以上１以下になるように正規化されたインターバルの大きさを入れる。ここで正規化とは、インターバルの大きさが０．５以上となるまで繰り返しインターバルの大きさを２倍にしていくことである。
【００１３】
レジスタＣにはインターバルの低数（より厳密にはインターバルの低数を２16した値）が入る。レジスタＣがオーバーフローしないようにレジスタＣの上位バイトは適時取り出され、圧縮結果として出力される（この際に発生するキャリーオーバーを解決する方法については、ＩＴＵ−Ｔ  Ｔ．８２に記載されているが、本発明の内容を理解する上で必須ではないため、ここでは触れない）。
【００１４】
レジスタＡの値が正規化処理によって２倍にされる度に、レジスタＣの値も２倍にされるため、レジスタＡの値を２倍化していることによる出力への影響は相殺される。
【００１５】
ＬＰＳインターバルを計算するには、本来、（インターバルの大きさ）×（ＬＰＳ出現確率）という演算が必要となるが、ここでは統計的に求められた値（ＬＳＺ）で近似する。この方法ではインターバルの大きさによってＬＰＳインターバルのインターバル中に占める割合が変化してしまうが、インターバルは大きさが０．５以上１以下に正規化されているため誤差はそれほど大きくはならない。
【００１６】
入力としてＭＰＳが与えられた際にはインターバルからＬＳＺを引き、ＬＰＳが与えられたときにはインターバルをＬＳＺとする。この操作の結果、インターバルが０．５以下となったときに正規化を行なう。正規化が行なわれたときにはＬＳＺの値を更新する。この更新には統計的に求められた確率推定表が用いられる。現在のＬＳＺ（のインデックス）と入力されたシンボルがＭＰＳであるかＬＰＳであるかとによって、次のＬＳＺが確率推定表から求められる。このＬＳＺの値は固定精度の整数として表現されるために上限だけでなく下限もある。
【００１７】
ここで、時々ＭＰＳインターバルよりもＬＰＳインターバルの方が大きくなってしまう場合がある。このときはＭＰＳインターバルとＬＰＳインターバルの入れ替えを行なう。
【００１８】
ＱＭ−Ｃｏｄｅｒにおける優勢確率シンボルの決定は符号化画素の周辺の幾つかの画素によって決定される。周辺画素の配列（以下、「コンテクスト」と呼称する）に対する優勢確率シンボルが確率推定テーブルに記録されており、この確率推定テーブルを参照することによって優勢確率シンボルを得ることができる。また、この確率推定テーブルにはＬＳＺのインデックスも入っているため、確率推定表からＬＳＺを求めるためにも使用される。確率推定テーブルにはコンテクストごとのＭＰＳ（１ビット）とＬＳＺのインデックスＳＴ（７ビット）が保存されており、各コンテクストに対して１バイトの大きさを持つ。コンテクストが１０セル分の大きさを持つのであれば２の１０乗個のコンテクストそれぞれに対して１バイトの大きさとなる。
【００１９】
ＪＢＩＧのＱＭ−Ｃｏｄｅｒを実装した従来の算術圧縮装置は図１５のようになる。この算術圧縮装置における圧縮処理のフローチャートについて図１４を用いて説明する。なお、下記の文章中に出現するＣＯＤＥＭＰＳ、ＣＯＤＥＬＰＳ、確率推定テーブル、確率推定表については、各々、図２、図８、図１１、及び、図１２において説明を行なっているので参照されたい。
【００２０】
算術圧縮装置に入力画像が与えられると、算術圧縮装置は入力画像を幾つか（１つ以上）のストライプに分ける。圧縮処理はストライプ単位で行なわれる。ストライプは画像中の１ライン以上の横ラインからなる。つまり、ストライプの幅は画像の幅と等しく、ストライプの高さは画像の高さと同じか、それ以下（ただし１以上）となる。図１４のストライプのループ（ＬＯＯＰ＿Ａ）によって、全てのストライプに対して処理が完了すると、画像全体の圧縮が完了したことになる。
【００２１】
算術圧縮装置は図１４のセル（画素）のループ（ＬＯＯＰ＿Ｂ）において、ストライプの左上から右下に向けてセルとコンテクストの読み取りを行なう。横方向に１ライン分のセルとコンテクストの読み取りを完了すると、その下のラインの読み取りへと進む。全ての画素の処理が完了すると１つのストライプの処理が完了したことになる。図１０において、斜線部分が圧縮対象となるセルであり、その周辺の１０個の四角がコンテクストの各セルを表している。ＪＢＩＧ圧縮では、最低解像度レイヤのコンテクストとして図１０の２ラインテンプレートの他に３ラインテンプレートが用意されている。ここでは２ラインテンプレートを用いる。
【００２２】
コンテクストのセル数は１０個、各セルは０または１の値を持つので、その組み合わせの数は１０２４通りである。
【００２３】
算術圧縮装置は圧縮対象のセル上のシンボルとコンテクストとを読み取る（Ｓ１４１）と、確率推定テーブル（図１１）を参照（Ｓ１４２）し、圧縮対象のシンボルがコンテクストに対する優勢確率シンボルか劣勢確率シンボルかを判断する（Ｓ１４３）。
【００２４】
優勢確率シンボルであったときには、工程Ｓ１４７〜Ｓ１５０を含む手順ＣＯＤＥＭＰＳ（図２）を、劣勢確率シンボルであったときには、工程Ｓ１４４〜Ｓ１４６を含む手順ＣＯＤＥＬＰＳ（図８）を実行する。
【００２５】
このような手順をストライプの全てのセルに対して行うことで、ストライプの圧縮が行なわれる。ＬＯＯＰ＿Ｂが一巡したら、次のストライプの圧縮に進む前にここまでの圧縮結果のうちまだ出力されていない部分を出力する（Ｓ１５１）。全てのストライプの圧縮が完了すれば画像全体の圧縮が完了したことになる。
【００２６】
ここまでは通常のＱＭ−Ｃｏｄｅｒの動作であるが、ＱＭ−Ｃｏｄｅｒの動作を高速化するために、様々な方法が開示されている。
【００２７】
特許文献１には、ＱＭ−Ｃｏｄｅｒにおいて、コンテクストが同一で、優勢確率シンボルが連続するときには各シンボルの予測条件には変化がないことを利用し、（インターバル）−ｎ×（ＬＰＳインターバル）のように予め定めたｎシンボル分の入力信号群を、一括して符号化する方法が開示されている。しかしながら、正規化が発生すると劣勢確率シンボルの確率推定が変化するため、一括圧縮を続けることができない。すなわち、正規化処理がいつ発生するかによって一括圧縮可能なセルの個数が制限されてしまう。
【００２８】
また特許文献２においては、算術圧縮装置において、ＭＰＳ符号の入力が続く場合に、それらの符号を一括して圧縮する方法が開示されている。これは、一括圧縮の際に正規化が発生しないことを検知して、正規化の発生しない範囲でのみ一括圧縮を行うものである。しかしながら、正規化処理が発生しないことを検知するためには、インターバルからＬＰＳインターバルを何回引くと正規化が発生するかを求めるという演算が毎回発生する。そのため、画像によっては高速化の効果が全く得られないか、逆に遅くなってしまう場合もある。
【００２９】
さらに特許文献３においては、コンテクストが特定のパターンとなり、かつ他の条件が一括圧縮可能な条件を満たす場合に処理を高速化する方法について開示されている。しかしながら、この方法ではコンテクストが特定のパターンになっている場合以外は高速化を行なうことはできない。すなわち、同一のコンテクストが続く場合のみにしか適用できない。
【００３０】
これらの問題を解決するために、特許文献４において、劣勢確率シンボルの確率推定が一定となったときに一括して圧縮を行なう方法が開示されている。
【００３１】
具体的には、ＪＢＩＧのＱＭ−ＣｏｄｅｒにおいてはＬＳＺのインデックスが１３のときにＬＳＺが最小となり、その後は正規化処理が行われても劣勢確率シンボルの確率推定が変化しない。そこで、ＬＳＺのインデックスが１３となっている近傍形が連続する分だけ圧縮処理を一括して行う。通常、このような状況はページ上下の余白や、テキストの行間などで発生することが多い。
【００３２】
この方法では、圧縮の途中で正規化処理が行われても劣勢確率シンボルの確率推定が変化しない状況において、任意の個数のセルを圧縮した際の各レジスタの値の変化を計算して一括で圧縮を行うことができる。
【００３３】
しかし、正規化回数に略比例した回数だけ出力処理を行っている点で完全な一括圧縮とはいえない。すなわち、正規化回数が多くなると、出力処理もそれだけ多く行わなければならないので、圧縮に無駄な時間がかかる（一括圧縮処理の際の正規化回数とは、一括圧縮する対象のシンボル列を１シンボルずつ通常の圧縮を行った場合に必要な正規化の回数を意味する）。
【特許文献１】特公平７−９５６９３号公報（平成７年１０月１１日公開）
【特許文献２】特開２０００−３５００４３号公報（平成１２年１２月２５日公開）
【特許文献３】特開平５−６７９７８号公報（平成５年３月１９日公開）
【特許文献４】特開２００５−２１７５１７号公報（平成１７年８月１１日公開）
【非特許文献１】ITU-T(International Telecommunication Union Telecommunication standardization sector) WHITE BOOK ディジタル静止画像圧縮符号化関連勧告書 勧告T.82,日本,財団法人 新日本ITU協会
【非特許文献２】WTSC-93(WORLD TELECOMMUNICATION STANDARIZATION CONFERENCE), Helsinki, 1-12 MARCH 1993
【発明の開示】
【発明が解決しようとする課題】
【００３４】
しかしながら、特許文献４に開示された方法では、正規化回数に略比例した回数だけ出力処理を呼び出す点において完全な一括圧縮とはいえない。すなわち、一括圧縮の際に正規化回数が多くなると、出力処理もそれだけ多く行わなければならないので、圧縮に無駄な時間がかかるという問題がある。
【００３５】
本発明は、上記の問題点に鑑みてなされたものであり、その目的は、一括圧縮において正規化回数に関わりなく、出力処理を行う回数が一定の上限値以下になるような方法を用いて圧縮処理を行うことによって、さらなる圧縮の高速化を図ることにある。
【課題を解決するための手段】
【００３６】
本発明に係る算術圧縮方法は、上記課題を解決するために、２値の入力信号からなる入力信号列を、各入力信号に対して定められた優勢確率シンボルと、各入力信号に対して定められた劣勢確率シンボルが当該入力信号として出現する出現確率の推定値とを用いて圧縮する算術圧縮方法であって、
上記入力信号列のうち、優勢確率シンボルに一致し、かつ、劣勢確率シンボルの出現確率の推定値が予め設定された下限値に一致する入力信号からなる入力信号群を一括して符号化する一括符号化工程を含んでおり、
上記一括符号化工程は、上記入力信号群を一括して符号化することにより得られる部分符号化データの末尾において特定値が連続する部分のバイト数を算出するバイト数算出工程と、算出されたバイト数分の上記特定値を上記部分符号化データの一部として一括して出力する一括出力工程と、を含んでいることを特徴としている。
【００３７】
上記の構成によれば、上記部分符号化データの末尾を一括して出力することにより、上記部分符号化データの長さに関わらず、容易に上記部分符号化データを出力することができるという効果を奏する。
【００３８】
なお、ここで、部分符号化データとは、入力信号列全体を符号化して得られる符号化データの全部ではなく、上記一括符号化工程において上記入力信号群を一括して符号化することにより得られる、上記符号化データの一部分である。
【００３９】
本発明に係る算術圧縮装置は、上記課題を解決するために、２値の入力信号からなる入力信号列を、各入力信号に対して定められた優勢確率シンボルと、各入力信号に対して定められた劣勢確率シンボルが当該入力信号として出現する出現確率とを用いて圧縮する算術圧縮装置であって、
上記入力信号列のうち、優勢確率シンボルに一致し、かつ、劣勢確率シンボルの出現確率の推定値が予め設定された下限値に一致する入力信号からなる入力信号群を一括して符号化する一括符号化手段を含んでおり、
上記一括符号化手段は、上記入力信号群を一括して符号化することにより得られる部分符号化データの末尾において特定値が連続する個数を算出する算出手段と、算出された個数分の特定値を上記部分符号化データの一部として一括して出力する一括出力手段と、を備えていることを特徴としている。
【００４０】
上記の構成によれば、本発明に係る算術圧縮方法と同様の作用効果を奏する。
【００４１】
本発明に係る算術圧縮方法は、上記一括符号化工程は、上記部分符号化データにおいて上記特定値が連続する部分を除いた残りの部分を１バイトずつ出力する逐次出力工程を更に含んでいることが望ましい。
【００４２】
上記の構成によれば、上記部分符号化データにおいて上記特定値が連続する部分を除いた残りの部分を１バイトずつ出力した後に、上記部分符号化データにおいて上記特定値が連続する部分を一括して出力することができるという効果を奏する。
【００４３】
本発明に係る算術圧縮方法は、上記逐次出力工程において出力する部分は、上記部分符号化データの上位５バイトであることが望ましい。
【００４４】
上記の構成によれば、上記部分符号化データにおいて上記特定値が連続する部分を除いた残りの部分を１バイトずつ５バイト分出力した後に、上記部分符号化データにおいて６バイト目から上記特定値が連続する部分を一括して出力することができるという効果を奏する。
【００４５】
本発明に係る算術圧縮方法において、上記一括符号化工程は、上記部分符号化データを表すインターバルの大きさと上記一括セルカウンタとに基づいて正規化回数ｎを算出する正規化回数算出工程と、上記インターバルを２倍する回数と上記正規化回数とに基づいてカウンタＣＴの値を算出するカウンタ算出工程と、を含んでおり、
上記バイト数算出工程は、上記正規化回数算出工程において算出された正規化回数ｎと、上記カウンタ算出工程において算出された上記カウンタＣＴの値とに基づいて、上記部分符号化データにおいて上記特定値が連続する部分のバイト数を算出する工程であることが好ましい。
【００４６】
上記の構成によれば、上記部分符号化データにおいて上記特定値が連続する部分のバイト数を容易に算出することができる、という効果を奏する。
【００４７】
本発明に係る算術圧縮方法において、上記バイト数算出工程は、上記部分符号化データの総バイト数を、
（ｎ／８）＋（ｘ  ＜＝（ｎ  ｍｏｄ  ８））
によって算出する総バイト数算出工程を含んでいることが望ましい。
【００４８】
上記の構成によれば、上記部分符号化データの総バイト数を容易に算出することができるという効果を奏する。
【００４９】
本発明に係る算術圧縮方法において、上記バイト数算出工程は、上記部分符号化データにおいて上記特定値が連続する部分を除いた残りの部分のバイト数を、上記総バイト数算出工程において算出された総バイト数から減算することによって、上記部分符号化データにおいて上記特定値が連続する部分のバイト数を算出することが望ましい。
【００５０】
上記の構成によれば、上記部分符号化データにおいて上記特定値が連続する部分の出力を一括して行うために、上記部分符号化データにおいて上記特定値が連続する部分のバイト数を容易に算出することができるという効果を奏する。
【００５１】
本発明に係る算術圧縮方法において、上記カウンタ算出工程は、当該一括符号化工程終了時点で上記カウンタＣＴの値を、
ＣＴ＝８−（｜ｎ−ｘ｜  ｍｏｄ  ８）
に基づいて更新することが望ましい。
【００５２】
上記の構成によれば、次に上記一括符号化工程を開始するために必要な上記カウンタＣＴの値を容易に算出することができるという効果を奏する。
【００５３】
なお、上記算術圧縮装置は、コンピュータによって実現しても良い。この場合、コンピュータを上記各手段として動作させることにより上記算術圧縮装置をコンピュータにおいて実現する算術圧縮プログラム、およびその算術圧縮プログラムを記録したコンピュータ読み取り可能な記録媒体も本発明の範疇に入る。
【発明の効果】
【００５４】
本発明に係る算術圧縮方法は、以上のように、一括圧縮の際に、従来技術において、正規化が発生する回数に略比例した回数だけ出力処理を呼び出すことにより取得した出力結果を、一定の上限回数だけ上記出力処理を呼び出し、その後１回だけ別の出力処理を行うことによって、一括して取得することができるので、圧縮処理を高速化することができるという効果を奏する。
【発明を実施するための最良の形態】
【００５５】
本発明の一実施形態について図１から図１３に基づいて説明すると以下の通りである。
【００５６】
本発明における圧縮方法をＩＴＵ−Ｔ  ＷＨＩＴＥ  ＢＯＯＫ  ディジタル静止画像圧縮符号化関連勧告書（財団法人  新日本ＩＴＵ協会）勧告Ｔ．８２記載されている、ＪＢＩＧのＱＭ−Ｃｏｄｅｒに適用した場合には次のようになる。ＪＢＩＧ圧縮はプログレッシブ方式を取っているが、ここでは、説明を簡単にするために最低解像度レイヤのみを持つＪＢＩＧ圧縮について扱う。本発明における圧縮高速化方式は複数の解像度レイヤを持つプログレッシブなＪＢＩＧ圧縮に対しても応用できる。また、説明を簡単にするため、コンテクストの形状を変化させるＡＴ（Ａｄａｐｔｉｖｅ  Ｔｅｍｐｌａｔｅ）移動などＪＢＩＧの仕様に含まれる付加的な機能に関してもここでは考えない。本発明における圧縮高速化方式はＡＴ移動を伴うＪＢＩＧ圧縮に対しても応用可能である。
【００５７】
（算術圧縮装置１の構成）
図１３は本発明の一実施形態に係る算術圧縮装置の要部構成を示す図である。
【００５８】
算術圧縮装置１はコンテクスト生成部２、取得部３、算術符号部４、記録部５、及び、レジスタ６を備えている。この算術圧縮装置１においては、上述の圧縮処理を計算機上で実装するために、インターバルの大きさ、及び、インターバルの低数を固定精度の整数で近似をしている。
【００５９】
（コンテクスト生成部２）
コンテクスト生成部２は、入力画像データから、対象となるセルの値、及び、そのセルの周辺のコンテクストを抽出する。
【００６０】
（取得部３）
取得部３は、各コンテクストに対応する優勢確率シンボルを記録した記録部５から、予測値としての優勢確率シンボル（ＭＰＳ）、及び、インデックスＳＴを取得する。取得した優勢確率シンボル、及び、インデックスＳＴ、並びに、入力されたセルの値を算術符号部４に出力する。
【００６１】
（記録部５）
記録部５には、確率推定テーブル７と確率推定表８とが記録されている。確率推定テーブル７は、図１１に示すように、コンテクストと、そのコンテクストから予測される優勢確率シンボル（ＭＰＳ）と、そのコンテクストに応じたＬＰＳインターバルの推定値（ＬＳＺ）のインデックスＳＴとを互いに関連付けるテーブルである。
【００６２】
また、確率推定表８は、図１２に示すように、ＬＳＺのインデックスＳＴから、ＬＳＺ、ＮＬＰＳ、ＮＭＰＳ，及び、ＳＷＩＴＣＨを求めるための表である。ここで、ＬＳＺは、ＬＳＺのインデックスＳＴに応じた劣勢確率シンボルのインターバルの近似値を意味する。ＮＬＳＰは、劣勢確率シンボルを圧縮したときの次のＳＴの値を意味する。ＮＭＰＳは、優勢確率シンボルを圧縮して正規化が発生したときの次のＳＴの値を意味する。なお、正規化が発生しないときには、ＳＴの値は更新されない。また、ＳＷＩＴＣＨは、優勢確率シンボルの入れ替えを行うか否かを示すフラグである。
【００６３】
なお、確率推定テーブル７と確率推定表８とは、全く別のものである。テーブルは表とも訳し得るが、ITU-T T.82の日本語訳(ITU-T WHITE BOOK ディジタル静止画像圧縮符号化関連勧告書 勧告T.82)でこのようになっているため、その語句をそのまま用いることとする。
【００６４】
（算術符号部４）
算術符号部４は、符号処理部９および前処理部１０を備えている。符号処理部９は、前処理部１０から入力される選択信号に応じて、各処理部９ａから９ｇのうちから適切な処理部を選択する。また、入力されたセルの値、ＭＰＳ、及び、インデックスＳＴを用いて選択した処理部によって符号化データを生成する。符号処理部９はＭＰＳ処理部９ａ、ＬＰＳ処理部９ｂ、ＲＥＮＯＲＭ処理部９ｃ、ＮＥＷＭＵＬＭＰＳ処理部９ｄ（一括符号化手段）、ＮＥＷＭＵＬＲＥＮＯＲＭ処理部９ｅ（一括符号化手段、算出手段、一括出力手段）を備えている。各処理部の詳細は後述する。
【００６５】
前処理部１０は取得部３から入力されるセルの値、ＭＰＳ、及び、ＳＴに応じて、選択信号を生成して、符号処理部９に出力する。前処理部１０は最小検知部１０ａ、一括チェック部１０ｂ、及び、選択部１０ｃを備えている。
【００６６】
最小検知部１０ａは、入力されるインデックスＳＴが１３となっているか否かを調べる。後述するように、インデックスＳＴが１３の場合、ＬＳＺの値は最小となる。最小検知部１０ａは、インデックスＳＴが１３となっている場合には、レジスタ６の一括圧縮レジスタ６ｃの値（セルカウンタ）を１だけインクリメントする。このように、最小検知部１０ａが確率推定最小値検知装置として機能して、ＬＳＺが最小値となっているか否かを調べるようになっている。
【００６７】
一括チェック部１０ｂは、レジスタ６の一括圧縮セルカウンタ６ｃの値が０を超えているか（１以上であるか）否かを判別するものである。一括チェック部１０ｂは、最小検知部１０ａおよび一括チェック部１０ｂ自身の判別結果を選択部１０ｃに出力する。
【００６８】
選択部１０ｃは、選択信号を生成するために、入力されるセルの値とＭＰＳとから、圧縮対象のシンボルがコンテクストに対する優勢確率シンボルか劣勢確率シンボルかを判断する。また、選択部１０ｃは、一括チェック部１０ｂの判別結果を受信する。選択部１０ｃは、入力に応じて選択信号を生成して、符号処理部９に出力する。
【００６９】
（レジスタ６）
レジスタ６は高速アクセス可能なメモリである。レジスタ６は、Ａｒｅｇ（レジスタＡ）６ａ、Ｃｒｅｇ（レジスタＣ）６ｂ、および、一括圧縮セルカウンタ６ｃを含んでいる。
【００７０】
Ａｒｅｇ６ａは、インターバルの大きさを２16乗した値を保持するための記憶領域である。また、Ｃｒｅｇ６ｂは、インターバルの低数を２16乗した値を保持する記憶領域である。Ａｒｅｇ６ａおよびＣｒｅｇ６ｂに格納される値は、固定精度の整数である。
【００７１】
一括圧縮セルカウンタ６ｃは、一括圧縮を行うセルの数ｔの値を格納するメモリである。一括圧縮セルカウンタ６ｃは、一括圧縮を行うセルの数を記録するものであり、初期値ｔは０である。この一括圧縮セルカウンタ６ｃの値ｔは、最小検知部１０ａが変化させる。
【００７２】
（算術圧縮処理のフロー）
本発明における一実施形態である算術圧縮処理のフローについて図１を用いて説明する。
【００７３】
まず、算術圧縮装置１に入力画像（入力信号列）が与えられる。算術圧縮装置１のコンテクスト生成部２は入力画像を幾つか（１つ以上）のストライプに分ける。圧縮処理はストライプ単位で行なわれる。ストライプは画像中の１ライン以上の横ラインからなる。つまり、ストライプの幅は画像の幅と等しく、ストライプの高さは画像の高さと同じか、それ以下（ただし１以上）となる。Ｓ１〜Ｓ１１のストライプのループ（ＬＯＯＰ１）によって、全てのストライプに対して処理が完了すると、画像全体の圧縮が完了したことになる。
【００７４】
算術圧縮装置１のコンテクスト生成部２はＳ１〜Ｓ９のセル（画素）のループ（ＬＯＯＰ２）において、ストライプの左上から右下に向けてセルと周辺画素（以下、「コンテクスト」と呼称する）との読み取りを行なう。横方向に１ライン分のセルとコンテクストとの読み取りを完了すると、その下のラインの読み取りへと進む。全ての画素の処理が完了すると１つのストライプの処理が完了したことになる。図１０において、斜線部分が圧縮対象となるセルであり、その周辺の１０個の四角がコンテクストの各セルを表している。ＪＢＩＧ圧縮では、最低解像度レイヤのコンテクストとして図１０の２ラインテンプレートの他に３ラインテンプレートが用意されている。ここでは２ラインテンプレートを用いる。
【００７５】
コンテクストのセル数は１０個、各セルは０または１の値を持つので、その組み合わせの数は１０２４通りである。
【００７６】
算術圧縮装置１のコンテクスト生成部２は圧縮対象のセル上のシンボル（入力信号）とコンテクストとを読み取る（Ｓ１）。次に取得部３は確率推定テーブル７を参照（Ｓ２）し、入力されたコンテクストに応じたＭＰＳを取得する。また、取得部３は、入力されたコンテクストに応じたＬＳＺ（ＬＰＳインターバルの推定値）のインデックスＳＴを確率推定テーブル７から取得する。取得部３は、セルの値、ＭＰＳ、及びインデックスＳＴを算術符号部４へと出力する。
【００７７】
次に算術符号部４において、前処理部１０の選択部１０ｃが、取得部３から入力されるセルの値とＭＰＳとに応じて、対象セルのシンボルがコンテクストに対する優勢確率シンボルか劣勢確率シンボルかを判断する（Ｓ３）。対象セルが優勢確率シンボルの場合（Ｓ３においてＭＰＳ）Ｓ６に進む。この場合Ｓ６〜Ｓ９の手順を行い、ストライプ内に圧縮するセルがなければ、Ｓ１０に進む。ストライプ内に圧縮するセルがまだあればＳ３に戻る。対象セルが劣勢確率シンボルの場合（Ｓ３においてＬＰＳ）Ｓ４に進む。この場合Ｓ４，Ｓ５の手順を行い、ストライプ内に圧縮するセルがなければＳ１０に進む、ストライプ内に圧縮するセルがまだあればＳ３に戻る。
【００７８】
選択部１０ｃが、対象セルのシンボルは優勢確率シンボルであると判定した場合（Ｓ３においてＭＰＳ）、前処理部の最小検知部１０ａが確率推定テーブル７上のＬＳＺインデックスを参照し、ＬＰＳインターバルが最小となっているかどうかを調べる（Ｓ６）。ＪＢＩＧ圧縮においてはＬＳＺのインデックスが１３となっていた場合にはＬＰＳインターバルが最小となっていることがわかる。ＬＰＳインターバルが最小である場合にはＳ７に進み、それ以外の場合はＳ８に進む。
【００７９】
ＬＰＳインターバルが最小となっていた場合（Ｓ６においてＹＥＳ）には、この時点では圧縮を行なわず、最小検知部１０ａは一括圧縮を行なうセルの個数を記録した一括圧縮セルカウンタ６ｃに１を加える（Ｓ７）。最小検知部１０ａはインターバルが最小であるという判定結果を一括チェック部１０ｂに送信し、一括チェック部１０ｂから上記判別結果を取得した選択部１０ｃが選択信号を符号処理部９に送信する。この選択信号は、符号処理部９において符号化をせずに、符号処理部９からコンテクスト生成部２へのセルインクリメントのみを行う旨を伝える信号である。なお、符号処理部９は、この時点では圧縮せず、後でまとめて圧縮を行う。符号処理部９がコンテクスト生成部２にセルインクリメントのための信号を出力する。その後、ストライプ内に圧縮するセルがなければＳ１０に進み、ストライプ内に圧縮するセルがまだあればＳ３に戻る。
【００８０】
ＬＰＳインターバルが最小となっていなかった場合（Ｓ６においてＮＯ）には、一括圧縮チェックＳ８に進む。一括圧縮チェックＳ８は、工程Ｓ１２と、工程Ｓ１３とを含む。すなわち、まず一括チェック部１０ｂが一括圧縮セルカウンタ６ｃの値をチェック（Ｓ１２）し、一括圧縮を行なう必要があるかどうかを調べる。
【００８１】
一括圧縮セルカウンタ６ｃが０である場合（Ｓ１２においてＮＯ）、選択部１０ｃは、一括チェック部１０ｂから一括チェックを行わないことを示す判別結果を受けとり、ＭＰＳ処理部９ａを選択する旨の選択信号を符号処理部９に出力して、Ｓ９に進む。
【００８２】
一括圧縮セルカウンタ６ｃが０でない場合（Ｓ１２においてＹＥＳ）、選択部１０ｃは、一括チェック部１０ｂから一括チェックを行うことを示す判別結果を受け取りＮＥＷＭＵＬＭＰＳ処理部９ｄを選択する旨を示す選択信号を符号処理部９に出力して、Ｓ１３に進む。Ｓ１３では、符号処理部９のＮＥＷＭＵＬＭＰＳ処理部９ｄが、ＮＥＷ＿ＣＯＤＥＭＵＬＭＰＳ処理を行う。ＮＥＷ＿ＣＯＤＥＭＵＬＭＰＳ処理は、一括圧縮セルカウンタ６ｃの値ｔに応じて、正規化の起こる回数を計算して、一括圧縮を行う処理である。ＮＥＷ＿ＣＯＤＥＭＵＬＭＰＳ処理は図４のＳ４１〜Ｓ４４の処理に相当する。ＮＥＷ＿ＣＯＤＥＭＵＬＭＰＳ処理を行った後、Ｓ９に進む。ＮＥＷ＿ＣＯＤＥＭＵＬＭＰＳ処理については後に詳細な説明を行う。
【００８３】
Ｓ９では、符号処理部９のＭＰＳ処理部９ａが、ＣＯＤＥＭＰＳ処理を行う。ＣＯＤＥＭＰＳ処理は、図２に示すＳ２１〜Ｓ２５の処理に相当する。ＭＰＳ処理部９ａは算術圧縮において入力信号がＭＰＳであった場合、インターバルの範囲を変更し、必要がある場合にはＲＥＮＯＲＭ処理部９ｃを呼び出してＲＥＮＯＲＭＥ処理を行わせる。ＲＥＮＯＲＭＥ処理は図３に示すＳ３１〜Ｓ３４の処理に相当する。その後、ストライプ内に圧縮するセルがなければＳ１０に進み、ストライプ内に圧縮するセルがまだあればＳ３に戻る。ＣＯＤＥＭＰＳ処理、及び、ＣＯＤＥＲＥＮＯＲＭＥ処理については後に詳細な説明を行う。
【００８４】
選択部１０ｃが、対象セルのシンボルは劣勢確率シンボルであると判定した場合（Ｓ３においてＬＰＳ）、一括圧縮チェックＳ４に進む。一括圧縮チェックＳ４は、上述した一括圧縮チェックＳ８と同様、工程Ｓ１２と工程Ｓ１３とを含む。すなわち、まず一括チェック部１０ｂが一括圧縮セルカウンタ６ｃの値をチェック（Ｓ１２）し、一括圧縮を行なう必要があるかどうかを調べる。
【００８５】
一括圧縮セルカウンタ６ｃが０である場合（Ｓ１２においてＮＯ）、選択部１０ｃは、一括チェック部１０ｂから一括チェックを行わないことを示す判別結果を受けとり、ＬＰＳ処理部９ｂを選択する旨の選択信号を符号処理部９に出力して、Ｓ５に進む。
【００８６】
一括圧縮セルカウンタ６ｃが０でない場合（Ｓ１２においてＹＥＳ）、選択部１０ｃは、一括チェック部１０ｂから一括チェックを行うことを示す判別結果を受け取りＮＥＷＭＵＬＭＰＳ処理部９ｄを選択する旨の選択信号を符号処理部９に出力して、Ｓ１３に進む。Ｓ１３では、符号処理部９のＮＥＷＭＵＬＭＰＳ処理部９ｄが、ＮＥＷ＿ＣＯＤＥＭＵＬＭＰＳ処理を行う。ＮＥＷ＿ＣＯＤＥＭＵＬＭＰＳ処理は、一括圧縮セルカウンタ６ｃの値ｔに応じて、正規化の起こる回数を計算して、一括圧縮を行う処理である。ＮＥＷ＿ＣＯＤＥＭＵＬＭＰＳ処理は図４のＳ４１〜Ｓ４４の処理に相当する。ＮＥＷ＿ＣＯＤＥＭＵＬＭＰＳ処理を行った後、Ｓ５に進む。ＮＥＷ＿ＣＯＤＥＭＵＬＭＰＳ処理については後で説明を行う。
【００８７】
Ｓ５では、符号処理部９のＬＰＳ処理部９ｂが、ＣＯＤＥＬＰＳ処理を行う。ＣＯＤＥＬＰＳ処理は、図８に示すＳ８１〜Ｓ８６の処理に相当する。ＬＰＳ処理部９ｂは算術圧縮において入力信号がＬＰＳであった場合、現在のインターバルからＭＰＳインターバルを取り除いてインターバルの範囲を変更する。また必要がある場合、ＬＰＳ処理部９ｂはＲＥＮＯＲＭ処理部９ｃを呼び出してＲＥＮＯＲＭＥ処理を行わせる。ＲＥＮＯＲＭＥ処理は図３に示すＳ３１〜Ｓ３４の処理に相当する。その後、ストライプ内に圧縮するセルがなければＳ１０に進み、ストライプ内に圧縮するセルがまだあればＳ３に戻る。ＣＯＤＥＬＰＳ処理、及び、ＲＥＮＯＲＭＥ処理の詳細については後で説明を行う。
【００８８】
ループ（ＬＯＯＰ２）においてストライプ内のすべてのセルの圧縮を終了した後、Ｓ１０が実行される。Ｓ１０はＳ１２、Ｓ１３の処理に相当する。まず一括チェック部１０ｂが一括圧縮セルカウンタ６ｃの値をチェック（Ｓ１２）し、一括圧縮を行なう必要があるかどうかを調べる。
【００８９】
一括圧縮セルカウンタ６ｃが０である場合（Ｓ１２においてＮＯ）には、選択部１０ｃは、一括チェック部１０ｂから一括チェックを行わないことを示す判別結果を受けとり、ＭＰＳ処理部９ａを選択する旨の選択信号を符号処理部９に出力して、Ｓ１１に進む。
【００９０】
一括圧縮セルカウンタ６ｃが０でない場合（Ｓ１２においてＹＥＳ）には、選択部１０ｃは、一括チェック部１０ｂから一括チェックを行うことを示す判別結果を受け取りＮＥＷＭＵＬＭＰＳ処理部９ｄを選択する旨の選択信号を符号処理部９に出力して、Ｓ１３に進む。Ｓ１３では、符号処理部９のＮＥＷＭＵＬＭＰＳ処理部９ｄが、ＮＥＷ＿ＣＯＤＥＭＵＬＭＰＳ処理を行う。ＮＥＷ＿ＣＯＤＥＭＵＬＭＰＳ処理は、一括圧縮セルカウンタ６ｃの値ｔに応じて、正規化回数を計算して、一括圧縮を行う処理である。ＮＥＷ＿ＣＯＤＥＭＵＬＭＰＳ処理は図４のＳ４１〜Ｓ４４の処理に相当する。ＮＥＷ＿ＣＯＤＥＭＵＬＭＰＳ処理を行った後、Ｓ１１に進む。ＮＥＷ＿ＣＯＤＥＭＵＬＭＰＳ処理については後に詳細な説明を行う。
【００９１】
Ｓ１１では、レジスタ６のＣｒｅｇ６ｂから圧縮結果としてのインターバルの低数を取得し、圧縮データとして算術圧縮装置の外部へと出力するフラッシュ処理を行う。その後、圧縮するストライプがまだあればＳ３に戻る。すべてのストライプの圧縮を完了していれば、算術圧縮処理は終了し、画像全体の圧縮が完了したことになる。
【００９２】
（ＣＯＤＥＭＰＳ処理のフロー）
ＣＯＤＥＭＰＳ処理のフローについて図２を用いて説明する。本発明をＪＢＩＧ圧縮に応用した場合のフローと従来のＪＢＩＧ圧縮のフローとは同一である。
【００９３】
このフローに従って優勢確率シンボルの符号化が行われる。ここでは、レジスタＡに格納されている、インターバルを２16した値をＡｒｅｇと表し、インターバルを０ｘ０から０ｘ１００００により表現する。また、レジスタＣに格納されている、インターバルの低数を２16した値をＣｒｅｇで表す。
【００９４】
ＭＰＳ処理部９ａはＡｒｅｇからＬＳＺを引いた後（Ｓ２１）、正規化が必要（Ａｒｅｇ＜０ｘ８０００）か否かの判断を行う（Ｓ２２）。正規化が必要ない場合（Ｓ２２においてＮＯ）、ＣＯＤＥＭＰＳの処理を完了する。正規化が必要な場合（Ｓ２２においてＹＥＳ）、ＭＰＳ処理部９ａはＭＰＳインターバルがＬＰＳインターバルより小さい（Ａｒｅｇ＜ＬＳＺ）かどうかの判定を行う（Ｓ２３）。
【００９５】
ＡｒｅｇがＬＳＺより小さい場合（Ｓ２３においてＹＥＳ）、ＭＰＳ処理部９ａはＣｒｅｇにＡｒｅｇの値を加え、ＡｒｅｇにＬＳＺの値を代入する（Ｓ２４）。すなわち、優勢確率シンボルと劣勢確率シンボルの入れ替えを行う。その後Ｓ２５に進む。
【００９６】
ＡｒｅｇがＬＳＺより大きければ（Ｓ２３においてＮＯ）、Ｓ２５に進む。
【００９７】
Ｓ２５において、ＭＰＳ処理部９ａはＬＳＺのインデックスを更新する（これは、確率推定表８を用いて優勢確率シンボルを符号化し、それによって正規化が発生した場合の次の値であるＮＭＰＳを読み取ることにより行われる）。また、ＭＰＳ処理部９ａはＲＥＮＯＲＭ処理部９ｃを呼び出して、手順ＲＥＮＯＲＭＥを実行させる。Ｓ２５が終了するとＣＯＤＥＭＰＳ処理が終了する。
【００９８】
（ＲＥＮＯＲＭＥ処理のフロー）
次にＲＥＮＯＲＭＥ処理のフローについて図３を用いて説明する。
【００９９】
最初にＲＥＮＯＲＭ処理部９ｃは、Ｃｒｅｇ６ｂの出力ビット数を示すカウンタＣＴをデクリメントし、Ａｒｅｇ６ａおよびＣｒｅｇ６ｂをそれぞれ１ビットシフトさせる（Ａｒｅｇ＝Ａｒｅｇ＜＜１、Ｃｒｅｇ＝Ｃｒｅｇ＜＜１）（Ｓ３１）。次にＲＥＮＯＲＭ処理部９ｃは、ＣＴの値が０であるか否かを判定する（Ｓ３２）。ＣＴ＝０の場合（Ｓ３２においてＹＥＳ）、Ｃｒｅｇ６ｂから圧縮結果を１バイト分算術圧縮装置１の外部に出力すると共にＣＴ＝８とする（Ｓ３３）。その後Ｓ３４に進む。ＣＴ＝０でない場合、Ｓ３４に進む。Ｓ３４において、ＲＥＮＯＲＭ処理部９ｃはＡｒｅｇ＜０ｘ８０００であるか否か判定を行なう。
【０１００】
Ａｒｅｇ＜０ｘ８０００の場合（Ｓ３４においてＹＥＳ）、Ｓ３１に戻る。Ａｒｅｇ＜０ｘ８０００でない場合（Ｓ３４においてＮＯ）、ＲＥＮＯＲＭＥの処理が完了する。
【０１０１】
（ＮＥＷ＿ＣＯＤＥＭＵＬＭＰＳ処理のフロー）
ＮＥＷ＿ＣＯＤＥＭＵＬＭＰＳ処理のフローについて図４を用いて説明する。
【０１０２】
まずＮＥＷＭＵＬＭＰＳ処理部９ｄは、Ａｒｅｇ６ａの値と一括圧縮セルカウンタ６ｃの値ｔとを用いて一括圧縮の間に与えられたセルに対する正規化回数を算出する（Ｓ４１）。
【０１０３】
ＪＢＩＧ圧縮の場合、ＩＴＵ−Ｔ  Ｔ．８２の表２４確率推定表から劣勢シンボルの確率推定（ＬＰＳ幅）は０ｘ０００１であるので、一括圧縮の開始時点でのＡｒｅｇ６ａの値をＡｒｅｇ１とすると、正規化回数Ｘｎｏｒは、
Ｘｎｏｒ＝（ｔ−（Ａｒｅｇ１−０ｘ８０００））／０ｘ７ｆｆｅ  ・・・・（１）
となる。なお、小数点以下は切り上げとなる。Ｘｎｏｒが０以下の場合は、正規化回数が０であることを意味する。
【０１０４】
また、一括圧縮が終了した時点におけるＡｒｅｇ６ａの値Ａｒｅｇ２は、正規化回数が０である場合には、
Ａｒｅｇ２＝Ａｒｅｇ１−ｔ・・・・・・・・・・・・・・・・・・・・・・（２）
正規化回数が１以上である場合には、
Ａｒｅｇ２＝（ｔ−（Ａｒｅｇ１―０ｘ８０００））  ｍｏｄ  ０ｘ７ｆｆｅ
・・・・（３）
となる（ｍｏｄは剰余を表す）。
【０１０５】
ＮＥＷＭＵＬＭＰＳ処理部９ｄは上記の式（１）から正規化回数を求めた後、ＮＥＷＭＵＬＲＥＮＯＲＭ処理部９ｅを呼び、ＮＥＷ＿ＭＵＬＲＥＮＯＲＭＥ処理を実行させる（Ｓ４２）。Ｓ４２は図６のＳ６１〜Ｓ７０の処理に相当する。その後ＮＥＷＭＵＬＭＰＳ処理部９ｄは、上記の式（２）、（３）から新しいＡｒｅｇの値を求め、この値をＡｒｅｇ６ａに代入する（Ｓ４３）。その後、ＮＥＷＭＵＬＭＰＳ処理部９ｄは一括圧縮セルカウンタ６ｃに０を代入し（Ｓ４４）、ＮＥＷ＿ＣＯＤＥＭＵＬＭＰＳ処理が完了する。
【０１０６】
（ＮＥＷ＿ＭＵＬＲＥＮＯＲＭＥ処理のフロー）
次にＮＥＷ＿ＭＵＬＲＥＮＯＲＭＥ処理のフローについて図６を用いて説明する。
【０１０７】
最初にＮＥＷＭＵＬＲＥＮＯＲＭ処理部９ｅは変数ｉｔｅｒａｔｉｏｎに（ｎ／８）＋（ｘ＜＝（ｎ  ｍｏｄ  ８））か５のどちらか小さい数値を入れる（Ｓ６１）。ここで、ｎは正規化回数、ｘは一括圧縮開始時のＣＴの値である。
【０１０８】
次にＮＥＷＭＵＬＲＥＮＯＲＭ処理部９ｅは、Ｓ６２〜Ｓ６５をＳ６１において求めたｉｔｅｒａｔｉｏｎの回数だけ実行する。Ｓ６２において、ＮＥＷＭＵＬＲＥＮＯＲＭ処理部９ｅは、Ｃｒｅｇ６ｂの値を１９−８＊ｉビット右シフトした値をＴＥＭＰに代入する。１９−８＊ｉが負の値を取るときは、その絶対値の分だけＣｒｅｇ６ｂを左シフトする。
【０１０９】
Ｓ６３において、ＮＥＷＭＵＬＲＥＮＯＲＭ処理部９ｅはＴＥＭＰ＆０ｘｆｆｆｆｆｆ００の値を判定する。
【０１１０】
ＮＥＷＭＵＬＲＥＮＯＲＭ処理部９ｅがＴＥＭＰ＆０ｘｆｆｆｆｆｆ００＞０ｘｆｆと判定した場合（Ｓ６３において０ｘｆｆより大きい）、Ｓ６４に進む。ＮＥＷ＿ＭＵＬＲＥＮＯＲＭ処理部９ｅがＴＥＭＰ＆０ｘｆｆｆｆｆｆ００＝＝０ｘｆｆと判定した場合（Ｓ６３において０ｘｆｆ）、Ｓ６５に進む。ＮＥＷＭＵＬＲＥＮＯＲＭ処理部９ｅがＴＥＭＰ＆０ｘｆｆｆｆｆｆ００＜０ｘｆｆと判定した場合（Ｓ６３において０ｘｆｆより小さい）、Ｓ６６に進む。
【０１１１】
Ｓ６４において、ＮＥＷＭＵＬＲＥＮＯＲＭ処理部９ｅは、暫定出力ｂｕｆｆｅｒに１を加え、圧縮結果として出力する。また、ｓｃの数だけ圧縮結果として０ｘ００を出力し、ｓｃの値を０にする。さらに、ｂｕｆｆｅｒの値をＴＥＭＰ＆０ｘｆｆとする。ループ処理をｉｔｅｒａｔｉｏｎ回実行していれば、Ｓ６７に進み、ｉｔｅｒａｔｉｏｎ回実行していなければ、Ｓ６２に戻る。
【０１１２】
Ｓ６５において、ＮＥＷＭＵＬＲＥＮＯＲＭ処理部９ｅは、ｓｃに１を加える。ループ処理をｉｔｅｒａｔｉｏｎ回実行していれば、Ｓ６７に進み、ｉｔｅｒａｔｉｏｎ回実行していなければ、Ｓ６２に戻る。
【０１１３】
Ｓ６６において、ＮＥＷＭＵＬＲＥＮＯＲＭ処理部９ｅは、ｂｕｆｆｅｒを圧縮結果として出力する。また、ｓｃの数だけ圧縮結果として０ｘｆｆを出力し、ｓｃの値を０にする。さらに、ｂｕｆｆｅｒの値をＴＥＭＰとする。ループ処理をｉｔｅｒａｔｉｏｎ回実行していれば、Ｓ６７に進み、ｉｔｅｒａｔｉｏｎ回実行していなければ、Ｓ６２に戻る。
【０１１４】
上記においてｂｕｆｆｅｒ及びｓｃの初期値は、ＮＥＷ＿ＣＯＤＥＭＵＬＭＰＳ処理の開始時点の値である。ＮＥＷ＿ＣＯＤＥＭＵＬＭＰＳ処理を開始するまでに圧縮を行なった過程において、上記初期値が決定される。また、ＮＥＷ＿ＣＯＤＥＭＵＬＭＰＳ処理を行うセル群の先頭のセルが入力画像データの最初のセルとなる場合は、ｂｕｆｆｅｒ及びｓｃの値は０となる。
【０１１５】
Ｓ６７において、ＮＥＷＭＵＬＲＥＮＯＲＭ処理部９ｅは、Ｃｒｅｇ６ｂの値をｎビット左シフト（Ｃｒｅｇ＜＜ｎ）し、Ｓ６８に進む。
【０１１６】
Ｓ６８において、ＮＥＷＭＵＬＲＥＮＯＲＭ処理部９ｅは、（ｎ／８）＋（ｘ＜＝（ｎ  ｍｏｄ  ８））＞＝６を満たすか否かを判定する。（ｎ／８）＋（ｘ＜＝（ｎ  ｍｏｄ  ８））＜６である場合（Ｓ６８においてＮＯ）、ＮＥＷ＿ＭＵＬＲＥＮＯＲＭＥ処理を終了する。（ｎ／８）＋（ｘ＜＝（ｎ  ｍｏｄ  ８））＞＝６である場合（Ｓ６８においてＹＥＳ）、Ｓ６９に進む。
【０１１７】
Ｓ６９において、ＮＥＷＭＵＬＲＥＮＯＲＭ処理部９ｅは、ＣＴに８−（｜ｎ−ｘ｜  ｍｏｄ  ８）を代入する。さらに、Ｓ７０において、（（ｎ／８）＋（ｘ＜＝（ｎ  ｍｏｄ  ８））−５）個の０ｘ００を出力し、ＮＥＷ＿ＭＵＬＲＥＮＯＲＭＥ処理を終了する。
【０１１８】
（ＣＯＤＥＬＰＳ処理のフロー）
ＣＯＤＥＬＰＳのフローについて図８を用いて説明する。
【０１１９】
最初に、ＬＰＳ処理部９ｂは、Ａｒｅｇ６ａの値からＬＳＺを引く（Ｓ８１）。次に、ＬＰＳ処理部９ｂは、Ａｒｅｇ＜ＬＳＺであるか否かを判定する（Ｓ８２）。Ａｒｅｇ＜ＬＳＺでない場合（Ｓ８２においてＮＯ）、Ｃｒｅｇ６ｂの値にＡｒｅｇ６ａの値を加え、Ａｒｅｇ６ａにＬＳＺを代入する（Ｓ８３）。その後Ｓ８４に進む。Ａｒｅｇ＜ＬＳＺである場合（Ｓ８２においてＹＥＳ）、Ｓ８４に進む。
【０１２０】
Ｓ８４において、ＬＰＳ処理部９ｂは、確率推定表８のＬＳＺのインデックスに対応するＳＷＩＴＣＨの値が１かどうかを判定する。ＳＷＩＴＣＨの値が１の場合（Ｓ８４においてＹＥＳ）、ＬＰＳ処理部９ｂはコンテクストに対するＭＰＳを入れ替える（０ならば１、１ならば０にする）（Ｓ８５）。その後Ｓ８６に進む。ＳＷＩＴＣＨが１でない場合（Ｓ８４においてＮＯ），Ｓ８６に進む。
【０１２１】
Ｓ８６において、ＬＰＳ処理部９ｂは、確率推定表８を用いて、現在のＳＴの値に関連づけられたＮＬＰＳの値を参照し、ＬＳＺのインデックスＳＴの値をＮＬＰＳの値にする。ここでＮＬＰＳには、注目セルのシンボルが劣勢確率シンボルの場合にシンボルを符号化した後のＳＴの値が格納されている。その後、ＬＰＳ処理部９ｂはＲＥＮＯＲＭ処理部９ｃを呼び出し、ＲＥＮＯＲＭＥ処理を実行させる。
【０１２２】
（確率推定テーブル７）
確率推定テーブル７について図１１を用いて説明する。
【０１２３】
確率推定テーブル７は、それぞれのコンテクストに対するＬＳＺのインデックスと優勢確率シンボルを保存するための領域である。ＬＳＺのインデックス（ＳＴ）は７ビット、優勢確率シンボルを記録する領域は１ビットの大きさを持ち、各コンテクストに対して１バイト（８ビット）の大きさとなる。
【０１２４】
ＬＳＺのインデックスはＪＢＩＧでは０から１１２までのいずれの値を取る。優勢確率シンボルは０または１となる。
【０１２５】
このテーブルに対しては圧縮処理を行なっている間に書き換えが行なわれる。
コンテクストの大きさがセル１０個分の場合には、２の１０乗で１０２４バイト分の領域が必要となる。
【０１２６】
（確率推定表８（ＩＴＵ−Ｔ  Ｔ．８２  表２４））
確率推定表８はＬＳＺのインデックスからＬＳＺの値や次のインデックスを求めるのに使う表である。圧縮処理の際にも書き換えられることはない。
【０１２７】
ＪＢＩＧのＱＭ−Ｃｏｄｅｒの確率推定表８について図１２を用いて説明する。
【０１２８】
確率推定表８はＬＳＺのインデックスＳＴ、劣勢確率シンボルのインターバル（ＬＳＺ）、劣勢確率シンボルを圧縮したときの次のＳＴの値ＮＬＰＳ、優勢確率シンボルを圧縮して正規化が発生したときの次のＳＴの値ＮＭＰＳ、及び、優勢確率シンボルの入れ替えを行なうか否かを示すフラグＳＷＩＴＣＨからなる。
【０１２９】
ＳＴは０から１１２までの値を取り、ＳＴが１３のときにＬＳＺは最小となる。ＳＴが１３のときにはＮＭＰＳが１３となっており、優勢確率シンボルを圧縮しているときに正規化が発生してもＳＴの値は１３のまま変化しないことが分かる。このようなＳＴの値は１３だけである。
【０１３０】
また、ＳＴが１３の時、ＬＳＺの値は０ｘ１であり、圧縮中に正規化が発生したときに必要な２倍化処理の回数は正規化１回につき２倍化処理１回だけで良い。
【０１３１】
なぜなら一個の優勢確率シンボルを符号化した結果、正規化が発生する直前のインターバル（Ａレジスタの値）は０ｘ８０００であり、１個の優勢確率シンボルを符号化したときにはこれからＬＳＺの値（このとき０ｘ１）を引くことになるためＡレジスタの値は０ｘ７ＦＦＦとなり、これを２倍にすると０ｘＦＦＦＥとなる。この値は０ｘ８０００より大きいためこれ以上２倍化処理を行なう必要はないからである。
【０１３２】
（ＮＥＷ＿ＭＵＬＲＥＮＯＲＭＥ処理の概要）
従来技術のように正規化回数だけＯＬＤ＿ＭＵＬＲＥＮＯＲＭＥ処理を呼んだ場合、（ｎ／８）＋（ｘ＜＝（ｎ  ｍｏｄ  ８））回ＢＹＴＥＯＵＴ処理を行う必要がある。しかし、ＮＥＷ＿ＭＵＬＲＥＮＯＲＭＥ処理を行うと、出力処理は最大６回となり、圧縮処理にかかる時間が短縮される。
【０１３３】
ＯＬＤ＿ＭＵＬＲＥＮＯＭＥ処理において、Ｃレジスタ等の初期値に関わらずＢＹＴＥＯＵＴ処理の５回目の呼び出し完了時に、ｂｕｆｆｅｒ、ｓｃの値は共に必ず０になる。すなわち、６回目以降のＢＹＴＥＯＵＴ呼び出しでは、出力が常に０ｘ００となり、Ｃレジスタの値が０となる。そのため、ＮＥＷ＿ＭＵＬＲＥＮＯＲＭＥ処理のように、６回目の出力処理において、（ｎ／８）＋（ｘ＜＝（ｎ  ｍｏｄ  ８））−５バイト分の０ｘ００を一括して出力しても、正規化回数だけＯＬＤ＿ＭＵＬＲＥＮＯＲＭＥ処理を呼んだ場合と同様の出力結果を得られる。
【０１３４】
また、ＮＥＷ＿ＭＵＬＲＥＮＯＲＭＥ処理を実行後のＣＴの値に関しても、ＣＴ＝８−（｜ｎ−ｘ｜  ｍｏｄ  ８）としてＣＴを計算すれば、ＯＬＤ＿ＭＵＬＲＥＮＯＲＭＥ処理を実行後のＣＴと同じ値を得られる。
【０１３５】
以上のように、本実施形態に係る算術圧縮方法は、２値の入力信号からなる入力画像データを、各セルに対して定められた優勢確率シンボルＭＰＳと、各セルに対して定められた劣勢確率シンボルＬＰＳが当該セルに出現する出現確率の推定値ＬＳＺとを用いて圧縮する算術圧縮方法である。
【０１３６】
そして、本実施形態に係る算術圧縮方法は、図１に示したように、入力画像データのうち、優勢確率シンボルにＭＰＳに一致し、かつ、劣勢確率シンボルＬＰＳの出現確率の推定値ＬＳＺが予め設定された下限値に一致する値をもつセルの集合であるセル群を一括して符号化するＮＥＷ＿ＣＯＤＥＭＵＬＭＰＳ処理Ｓ１３を含んでいる。
【０１３７】
ここで、ＮＥＷ＿ＣＯＤＥＭＵＬＭＰＳ処理Ｓ１３において一括して符号化されるセル群は、入力画像データにおいて連続した領域をなす互いに隣接したセルの集合であって、末尾のセルがセルループ（ＬＯＯＰ２）において処理対象となっているセルの直前のセルとなるセルの集合である。
【０１３８】
そして、ＮＥＷ＿ＣＯＤＥＭＵＬＭＰＳ処理Ｓ１３は、図６に示したように、上記セル群を一括して符号化することにより得られる部分符号化データの末尾において値０ｘ００（特定値）が連続する部分のバイト数を算出するとともに、算出されたバイト数分の０ｘ００（特定値）を上記部分符号化データの一部として一括して出力する工程Ｓ７０と、を含んでいる。なお、本実施形態においては、特定値が０ｘ００であるとしているが、特定値が別の値であっても良い。
【０１３９】
＜算術圧縮方法の変型例＞
（ＮＥＷ＿ＣＯＤＥＭＵＬＭＰＳ処理のフロー）
本実施形態におけるＮＥＷ＿ＣＯＤＥＭＵＬＭＰＳ処理のフローについて、Ｓ４２において、ＮＥＷＭＵＬＭＰＳ処理部９ｄはＮＥＷＭＵＬＲＥＮＯＲＭ処理部９ｅを呼び出し、ＮＥＷ＿ＭＵＬＲＥＮＯＲＭＥ改処理を実行させてもよい。ＮＥＷ＿ＭＵＬＲＥＮＯＲＭＥ改処理は図７のＳ７１〜Ｓ７６の処理に相当する。ＮＥＷ＿ＭＵＬＲＥＮＯＲＭＥ処理を実行しても、ＮＥＷ＿ＭＵＬＲＥＮＯＲＭＥ改処理を実行しても、どちらでも出力結果は同じである。
【０１４０】
（ＮＥＷ＿ＭＵＬＲＥＮＯＲＭＥ改処理のフロー）
次にＮＥＷ＿ＭＵＬＲＥＮＯＲＭＥ改処理のフローについて図７を用いて説明する。
【０１４１】
最初にＮＥＷＭＵＬＲＥＮＯＲＭ処理部９ｅはｉｔｅｒａｔｉｏｎに（ｎ／８）＋（ｘ＜＝（ｎ  ｍｏｄ  ８））か５のどちらか小さい数値を入れる（Ｓ７１）。ここで、ｎは正規化回数。ｘは一括圧縮開始時のＣＴの値である。
【０１４２】
次にＮＥＷＭＵＬＲＥＮＯＲＭ処理部９ｅは、Ｓ７２をＳ７１において求めたｉｔｅｒａｔｉｏｎの値と等しい回数実行する。Ｓ７２において、ＮＥＷＭＵＬＲＥＮＯＲＭ処理部９ｅはＯＬＤ＿ＭＵＬＲＥＮＯＲＭＥ処理を呼び出す。ループ処理をｉｔｅｒａｔｉｏｎ回実行していれば、Ｓ７３に進み、ｉｔｅｒａｔｉｏｎ回実行していなければ、Ｓ７２を再度実行する。
【０１４３】
Ｓ７３において、ＮＥＷＭＵＬＲＥＮＯＲＭ処理部９ｅは、Ｃｒｅｇ６ｂの値をｎビット左シフト（Ｃｒｅｇ＜＜ｎ）し、Ｓ７４に進む。
【０１４４】
Ｓ７４において、ＮＥＷＭＵＬＲＥＮＯＲＭ処理部９ｅは（ｎ／８）＋（ｘ＜＝（ｎ  ｍｏｄ  ８））＞＝６を満たすか否かを判定する。（ｎ／８）＋（ｘ＜＝（ｎ  ｍｏｄ  ８））＜６である場合（Ｓ７４においてＮＯ）、ＮＥＷ＿ＭＵＬＲＥＮＯＲＭＥ改処理を終了する。（ｎ／８）＋（ｘ＜＝（ｎ  ｍｏｄ  ８））＞＝６である場合（Ｓ７４においてＹＥＳ）、Ｓ７５に進む。
【０１４５】
Ｓ７５において、ＮＥＷＭＵＬＲＥＮＯＲＭ処理部９ｅは、ＣＴに８−（｜ｎ−ｘ｜  ｍｏｄ  ８）を代入する。さらに、Ｓ７６において、（（ｎ／８）＋（ｘ＜＝（ｎ  ｍｏｄ  ８））−５）個の０ｘ００を出力し、ＮＥＷ＿ＭＵＬＲＥＮＯＲＭＥ改処理を終了する。
【０１４６】
（ＯＬＤ＿ＭＵＬＲＥＮＯＲＭＥ処理のフロー）
ＯＬＤ＿ＭＵＬＲＥＮＯＲＭＥ処理のフローについて図５を用いて説明する。
【０１４７】
ＮＥＷＭＵＬＲＥＮＯＲＭ処理部９ｅは、Ｃｒｅｇ６ｂを１ビットシフト（Ｃ＝Ｃ＜＜１）し、ＣＴから１を減ずる（Ｓ５１）。次に、ＮＥＷＭＵＬＲＥＮＯＲＭ処理部９ｅは、ＣＴが０か否かを判定する（Ｓ５２）．ＣＴが０と判定された場合（Ｓ５２においてＹＥＳ）には、ＮＥＷＭＵＬＲＥＮＯＲＭ処理部９ｅはＣｒｅｇ６ｂから１バイト出力を行なうと共にＣＴに８を代入して（Ｓ５３）、ＯＬＤ＿ＭＵＬＲＥＮＯＲＭＥ処理を終了する。ＣＴが０ではないと判定された場合（Ｓ５２においてＮＯ）、ＯＬＤ＿ＭＵＬＲＥＮＯＲＭＥ処理を終了する。
【０１４８】
（ＩＴＵ−Ｔ  Ｔ．８２の図２４ＣＯＤＥＭＰＳにおけるＡｒｅｇ＜ＬＳＺ［ＳＴ［ＣＸ］］もＬＳＺ（劣勢シンボルの確率推定）が０ｘ４０００より小さいことから、この条件を満たすことはなく、Ａｒｅｇに劣勢シンボル確率推定が代入される操作は行われることがない。また、コンテクストＣＸに対するＬＳＺのインデックスＳＴ［ＣＸ］も変化しないため、上記手順でＣＯＤＥＭＰＳの動作をシミュレーションすることができる）。
【０１４９】
＜ＯＬＤ＿ＭＵＬＲＥＮＯＲＭＥ処理と、ＮＥＷ＿ＭＵＬＲＥＮＯＲＭＥ処理、及び、ＮＥＷ＿ＭＵＬＲＥＮＯＲＭＥ処理改との比較＞
ＳＴ＝１３であるようなＭＰＳが連続で出現する間の正規化回数がｎであるとき、
ＯＬＤ＿ＭＵＬＲＥＮＯＲＭＥ処理をｎ回実行することと、ＮＥＷ＿ＭＵＬＲＥＮＯＲＭＥ処理を１回実行することは等価である。
【０１５０】
すなわち、正規化回数ｎ、Ｃレジスタの値Ｃｒｅｇ、ＣＴの値、及び、Ａレジスタの値Ａｒｅｇといったパラメータ、及び、圧縮モジュールからの出力値は、ＯＬＤ＿ＭＵＬＲＥＮＯＲＭＥ処理をｎ回呼び出す場合と、ＮＥＷ＿ＭＵＬＲＥＮＯＲＭＥ処理を１回呼び出す場合とで一致する（Ａｒｅｇの値は、ＯＬＤ＿ＭＵＬＲＥＮＯＲＭＥ処理をｎ回呼び出しても、ＮＥＷ＿ＭＵＬＲＥＮＯＲＭＥ処理を１回呼び出しても変化しない）。
【０１５１】
なお、ＮＥＷ＿ＭＵＬＲＥＮＯＲＭＥ処理を１回実行後の上記パラメータ及び出力値とＯＬＤ＿ＭＵＬＲＥＮＯＲＭＥ処理をｎ回実行後の上記パラメータ及び出力値とが一致する理由は次の通りである。
【０１５２】
（ｎ／８）＋（ｘ  ＜＝  （ｎ  ｍｏｄ  ８））＜＝５である場合、ＮＥＷ＿ＭＵＬＲＥＮＯＲＭＥ処理においてＯＬＤ＿ＭＵＬＲＥＮＯＲＭＥ処理と全く同じパラメータ操作及び出力を行なうため明らかに一致する。
【０１５３】
（ｎ／８）＋（ｘ  ＜＝  （ｎ  ｍｏｄ  ８））＞＝６である場合、ＮＥＷ＿ＭＵＬＲＥＮＯＲＭＥ処理において行われるパラメータ操作、及び、出力は、ＮＥＷ＿ＭＵＬＲＥＮＯＲＭＥのループ処理における、５回目のループが完了するまで、ＯＬＤ＿ＭＵＬＲＥＮＯＲＭＥ処理、及び、その内部で呼ばれているＢＹＴＥＯＵＴ処理により行われるパラメータ操作及び出力と全く同じであるため明らかに一致する。
【０１５４】
ループ処理の終了後、Ｓ６７においてＣｒｅｇに行なわれる操作はシフト演算だけであり、（ｎ／８）＋（ｘ  ＜＝  （ｎ  ｍｏｄ  ８））＞＝６を満たすか否かを判定（Ｓ６８）した後、Ｃｒｅｇの値はＳ６７で行われたシフト演算によって、必ず０ｘ０となっている（（ｎ／８）＋（ｘ  ＜＝  （ｎ  ｍｏｄ  ８））＞＝６を満たすか否かを判定するステップ（Ｓ６８）までは、ＣＴの値によってはＣｒｅｇの値が０ｘ０になっていない場合があり、この場合には出力値は０ｘ０にならないことになる）。
【０１５５】
そのため、８回正規化が行なわれて、８ビット(１バイト)分出力ビット０ｘ０が溜まると、１バイトの０ｘ００を出力する。すなわち、ＮＥＷ＿ＭＵＬＲＥＮＯＲＭＥ処理においては、ｎ／８＋（ｘ  ＜＝  （ｎ  ｍｏｄ  ８））個の０x００を出力することになるが、（ｎ／８）＋（ｘ  ＜＝  （ｎ  ｍｏｄ  ８））＞＝６を満たすか否かを判定するステップ（Ｓ６８）の前において、すでに５個の０ｘ００を出力しているので、ここでは（ｎ／８）＋（ｘ  ＜＝  （ｎ  ｍｏｄ  ８））−５個の０ｘ００を出力すれば、ＯＬＤ＿ＭＵＬＲＥＮＯＲＭＥ処理をｎ回呼び出した場合と同じ出力が得られる。また、このときＣＴ＝８−（｜ｎ−ｘ｜  ｍｏｄ  ８）とすればＣＴの値が求められる。
【０１５６】
ＮＥＷ＿ＭＵＬＲＥＮＯＲＭＥ改は、ＮＥＷ＿ＭＵＬＲＥＮＯＲＭＥ処理におけるループ内の処理をＯＬＤ＿ＭＵＬＲＥＮＯＲＭＥ処理を呼び出す処理に置き換えただけであり、パラメータに対する操作はＮＥＷ＿ＭＵＬＲＥＮＯＲＭＥ処理と全く同じである。
【０１５７】
（プログラムおよび記憶媒体）
最後に、算術圧縮装置に含まれている各ブロックは、ハードウェアロジックによって構成すればよい。または、次のように、ＣＰＵ（Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ）を用いてソフトウェアによって実現してもよい。
【０１５８】
すなわち算術圧縮装置は、各機能を実現する制御プログラムのプログラムコード（実行形式プログラム、中間コードプログラム、ソースプログラム）をコンピュータで読み取り可能に記録していればよい。算術圧縮装置（またはＣＰＵやＭＰＵ）が、供給された記録媒体に記録されているプログラムコードを読み出し、実行すればよい。
【０１５９】
プログラムコードを算術圧縮装置に供給する記録媒体は、たとえば、磁気テープやカセットテープ等のテープ系、フロッピー（登録商標）ディスク／ハードディスク等の磁気ディスクやＣＤ−ＲＯＭ／ＭＯ／ＭＤ／ＤＶＤ／ＣＤ−Ｒ等の光ディスクを含むディスク系、ＩＣカード（メモリカードを含む）／光カード等のカード系、あるいはマスクＲＯＭ／ＥＰＲＯＭ／ＥＥＰＲＯＭ／フラッシュＲＯＭ等の半導体メモリ系などとすることができる。
【０１６０】
また算術圧縮装置は、通信ネットワークと接続可能に構成しても、本発明の目的を達成できる。この場合、上記のプログラムコードを、通信ネットワークを介して算術圧縮装置に供給する。この通信ネットワークは、算術圧縮装置にプログラムコードを供給できるものであればよく、特定の種類または形態に限定されない。たとえば、インターネット、イントラネット、エキストラネット、ＬＡＮ、ＩＳＤＮ、ＶＡＮ、ＣＡＴＶ通信網、移動体通信網、衛星通信網等であればよい。
【０１６１】
この通信ネットワークを構成する伝送媒体も、プログラムコードを伝送可能な任意の媒体であればよく、特定の構成または種類のものに限定されない。たとえば、ＩＥＥＥ１３９４、ＵＳＢ（Ｕｎｉｖｅｒｓａｌ  Ｓｅｒｉａｌ  Ｂｕｓ）、電力線搬送、ケーブルＴＶ回線、電話線、ＡＤＳＬ（Ａｓｙｍｍｅｔｒｉｃ  Ｄｉｇｉｔａｌ  Ｓｕｂｓｃｒｉｂｅｒ  Ｌｉｎｅ）回線などの有線でも、ＩｒＤＡやリモコンのような赤外線、Ｂｌｕｅｔｏｏｔｈ（登録商標）、８０２．１１無線、ＨＤＲ、携帯電話網、衛星回線、地上波デジタル網等の無線でも利用可能である。なお、本発明は、上記プログラムコードが電子的な伝送で具現化された、搬送波に埋め込まれたコンピュータデータ信号の形態でも実現され得る。
【０１６２】
（付記事項）
本発明は上述した実施形態に限定されるものではなく、請求項に示した範囲で種々の変更が可能であり、異なる実施形態にそれぞれ開示された技術的手段を適宜組み合わせて得られる実施形態についても本発明の技術的範囲に含まれる。
【０１６３】
本発明に係る算術符号化方法は、２値の入力信号列を、入力信号の予測値である優勢確率シンボルおよび予測値ではない劣勢確率シンボルの出現確率に応じて、この出現確率の推定値を用いて符号化する符号化方法において、上記劣勢確率シンボルの出現確率の推定値に下限を設けてあり、入力信号が優勢確率シンボルである場合に、劣勢確率シンボルの出現確率の推定値が下限の値であるか否かを検知する最小検知工程と、上記最小検知工程にて上記劣勢確率シンボルの出現確率の推定値が下限の値であると検知した場合に符号化をせずにインクリメントした一括圧縮セルカウンタが１以上であるときに、この一括圧縮セルカウンタの数に応じて一括圧縮をする一括圧縮工程とを含んでいることを特徴とする符号化方法であって、優勢確率シンボルの出現確率に関する値の精度を維持するために、この優勢確率シンボルの出現確率に基づく値を変更する回数を求め、その回数を基に圧縮結果を複数ビット分一括して生成することを特徴とする。
【０１６４】
本発明に係る算術符号化方法は、２値の入力信号列を、入力信号の予測値である優勢確率シンボルおよび予測値ではない劣勢確率シンボルの出現確率に応じて、この出現確率の推定値を用いて符号化する符号化方法において、上記劣勢確率シンボルの出現確率の推定値に下限を設けてあり、入力信号が優勢確率シンボルである場合に、劣勢確率シンボルの出現確率の推定値が下限の値であるか否かを検知する最小検知工程と、上記最小検知工程にて上記劣勢確率シンボルの出現確率の推定値が下限の値であると検知した場合に符号化をせずにインクリメントした一括圧縮セルカウンタが１以上であるときに、この一括圧縮セルカウンタの数に応じて一括圧縮をする一括圧縮工程とを含んでいることを特徴とする符号化方法であって、優勢確率シンボルの出現確率に関する値の精度を維持するために、この優勢確率シンボルの出現確率に基づく値を変更する回数を求め、その回数を基に出力用データの出力バイト数又は/及び出力回数を求め、圧縮結果出力を複数ビット分一括して生成することを特徴とする。
【０１６５】
本発明に係る算術符号化方法は、例えば、一括圧縮を開始したときは圧縮結果出力を１バイトずつ出力し、一括圧縮の途中から、圧縮結果出力を一括して出力することができる。
【０１６６】
本発明に係る算術符号化方法は、例えば、一括圧縮の途中から圧縮結果出力を一括して出力する場合に、その一括出力は一括圧縮開始後６バイト目以降から行なうことができる。
【０１６７】
本発明に係る算術符号化方法は、例えば、一括圧縮中の出力されていない圧縮結果のビット数を計算によって求めることができる。
【０１６８】
本発明に係る算術符号化方法は、例えば、出力されていない圧縮結果のビット数は、
８−（｜正規化回数  −  一括圧縮開始時のビット数|  ｍｏｄ  ８）
により求めることができる。
【０１６９】
本発明に係る算術符号化方法は、例えば、出力バイト数の値は、
（正規化回数／８）＋（一括圧縮開始時のビット数＜＝（正規化回数  ｍｏｄ  ８））
により求めることができる。
【０１７０】
本発明に係る算術符号化方法は、例えば、前記求めた出力バイト数の値から、一括して圧縮結果を出力するまでのバイト数を引いたバイト数を一括して出力することができる。
【０１７１】
本発明に係る算術符号化方法は、一括して圧縮結果を出力するまでのバイト数は、５であることが望ましい。
【産業上の利用可能性】
【０１７２】
本発明に係る算術圧縮方法は、画像の符号化に好適に利用することができる。取り分け、ファクシミリ装置（ＦＡＸ）やプリンタなどの装置における画像の符号化に好適に利用することができる。
【図面の簡単な説明】
【０１７３】
【図１】本発明の実施形態を示すものであり、算術圧縮方法の概略を示すフローチャートである。
【図２】図１に示した算術圧縮方法の一部を示すフローチャートである。
【図３】図１に示した算術圧縮方法の他の一部を示すフローチャートである。
【図４】図１に示した算術圧縮方法のさらに他の一部を示すフローチャートである。
【図５】図１に示した算術圧縮方法のさらに他の一部を示すフローチャートである。
【図６】図１に示した算術圧縮方法のさらに他の一部を示すフローチャートである。
【図７】図１に示した算術圧縮方法のさらに他の一部を示すフローチャートである。
【図８】図１に示した算術圧縮方法のさらに他の一部を示すフローチャートである。
【図９】図１に示した算術圧縮方法で用いる算術圧縮を説明する概略図である。
【図１０】図１に示した算術圧縮方法で符号化を行なう対象セルと、そのセルについてのコンテクストとの一例を示す平面図である。
【図１１】図１に示した算術圧縮方法で用いる確率推定テーブルの一例を示す図である。
【図１２】図１に示した算術圧縮方法で用いる確率推定表の一例を示す図である。
【図１３】本発明に係る算術圧縮装置の一実施形態を示すブロック図である。
【図１４】従来技術を示すものであり、算術圧縮装置にて行なう圧縮処理の概略を示すフローチャートである。
【図１５】従来の算術圧縮装置の一例を示すブロック図である。
【符号の説明】
【０１７４】
１  算術圧縮装置
２  コンテクスト生成部
３  取得部
４  算術符号部
５  記録部
６  レジスタ
６ａ  Ａｒｅｇ（レジスタＡ）
６ｂ  Ｃｒｅｇ（レジスタＣ）
６ｃ  一括圧縮セルカウンタ
７  確率推定テーブル
８  確率推定表
９  符号処理部
９ａ  ＭＰＳ処理部
９ｂ  ＬＰＳ処理部
９ｃ  ＲＥＮＯＲＭ処理部
９ｄ  ＮＥＷＭＵＬＭＰＳ処理部
９ｅ  ＮＥＷＭＵＬＲＥＮＯＲＭ処理部
１０  前処理部
１０ａ  最小検知部
１０ｂ  一括チェック部
１０ｃ  選択部
【図１】
0004786676.tif 000002
【図２】
0004786676.tif 000003
【図３】
0004786676.tif 000004
【図４】
0004786676.tif 000005
【図５】
0004786676.tif 000006
【図６】
0004786676.tif 000007
【図７】
0004786676.tif 000008
【図８】
0004786676.tif 000009
【図９】
0004786676.tif 000010
【図１０】
0004786676.tif 000011
【図１１】
0004786676.tif 000012
【図１２】
0004786676.tif 000013
【図１３】
0004786676.tif 000014
【図１４】
0004786676.tif 000015
【図１５】
0004786676.tif 000016