(57)【要約】【課題】正規化の発生にかかわらず一括圧縮を行う符号化装置を提供する。【解決手段】符号化装置１の最小検知部１０ａは、セルの周辺画素であるコンテクストから決定されるインデックスＳＴが、劣勢確率シンボルの確率推定値を最小値とするインデックスである場合には、一括圧縮セルカウンタ６ｃの値を増加させる一方で、符号処理部９にて圧縮処理をせずにセルインクリメントのみを行うように、選択部１０ｃから選択信号を出力する。コンテクスト生成部２にて新たなセルを圧縮対象となるセルとするセルインクリメントを行う。その後、一括圧縮セルカウンタ６ｃの値が０でない場合に、最小値である劣勢確率シンボルの確率推定値は正規化が発生しても変化しないことを利用して、ＭＵＬＭＰＳ処理部９ｄが一括圧縮をする。【選択図】図１
2005217517.tif 000002
【特許請求の範囲】
【請求項１】
２値の入力信号列を、入力信号の予測値である優勢確率シンボルおよび予測値ではない劣勢確率シンボルの出現確率に応じて、この出現確率の推定値を用いて符号化する符号化方法において、
上記劣勢確率シンボルの出現確率の推定値に下限を設けてあり、
入力信号が優勢確率シンボルである場合に、劣勢確率シンボルの出現確率の推定値が下限の値であるか否かを検知する最小検知工程と、
上記最小検知工程にて上記劣勢確率シンボルの出現確率の推定値が下限の値であると検知した場合に符号化をせずにインクリメントした一括圧縮セルカウンタが１以上であるときに、この一括圧縮セルカウンタの数に応じて一括圧縮をする一括圧縮工程とを含んでいることを特徴とする符号化方法。
【請求項２】
符号化方法自身の実装形態がQM-coderまたはQM-coderと同じ出力を行なうものであり、
上記最小検知工程において、劣勢確率シンボルの出現確率の推定値が下限の値であることを、上記QM-coderの確率推定表における劣勢確率シンボルの出現確率の推定値のインデックスが１３であることによって判定することを特徴とする請求項１に記載の符号化方法。
【請求項３】
上記一括圧縮工程において、上記一括圧縮セルカウンタの数に応じて、圧縮によって発生する正規化の回数を算出し、その算出した正規化回数に基づいて符号化処理を行うことを特徴とする請求項１に記載の符号化方法。
【請求項４】
２値の入力信号列を、入力信号の予測値である優勢確率シンボルおよび予測値ではない劣勢確率シンボルの出現確率に応じて、この出現確率の推定値を用いて符号化する符号化装置において、
上記劣勢確率シンボルの出現確率の推定値に下限を設けてあり、
入力信号が優勢確率シンボルである場合に、劣勢確率シンボルの出現確率の推定値が下限の値であるか否かを検知する最小検知部と、
上記最小検知部にて上記劣勢確率シンボルの出現確率の推定値が下限の値であると検知した場合に符号化をせずにインクリメントした一括圧縮セルカウンタが１以上であるときに、この一括圧縮セルカウンタの数に応じて一括圧縮をする一括圧縮部とを含んでいることを特徴とする符号化装置。
【請求項５】
コンピュータを、請求項４に記載の符号化装置を有するプリンタドライバとして機能させるためのプログラム。
【請求項６】
請求項５に記載のプログラムを記録したコンピュータ読み取り可能な記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、２値データを符号化圧縮する符号化方法、符号化装置、プログラムおよび記録媒体に関するものである。
【背景技術】
【０００２】
２値画像データをマルコフ情報源でモデル化し、符号化シンボルをその周辺画素の状態によって予測し、予測結果に応じて算術符号化する方式として、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から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の値が１か否かによって、入れ替えを行なうかどうかを判断する。ＬＰＳ処理部２９ｂは、記録部２５の確率推定表２８を更新し（Ｓ６１）、Ｓ６２に進む。
【００１７】
Ｓ６２では、符号処理部２９がコンテクスト生成部２２に対してセルインクリメントの指示を行い、セルについてのループを終了する。このような手順をストライプの全てのセルに対して行うことで、ストライプの圧縮を行う。Ｓ６３では、ストライプについての処理が終了したか否かを判別し、終了していた場合にはレジスタ２６から符号化データを出力する（フラッシュ処理：Ｓ６３）。このように、次のストライプの圧縮に進む前に、ここまでの圧縮結果のうちで、まだ出力されていない部分を出力する。Ｓ６４では、コンテクスト生成部２２が新たなストライプを選択する。全てのストライプの圧縮が完了すれば画像全体の圧縮が完了したことになり、入力画像データの全てを符号化した場合には、処理を終了する。
【００１８】
上述のように、適応型の算術圧縮では、画像圧縮を行なう過程でLPSインターバルが変化するために、圧縮結果もLPSインターバルの変化に伴って変化する。LPSインターバルは正規化処理が行なわれた際に変化するため、正規化処理が行なわれないことをあらかじめ検知した上で一括圧縮を行なって画像圧縮の高速化を図るという方法が知られている。
【００１９】
例えば、特許文献１には、コンテクストが同一で優勢確率シンボルが連続するときの一括符号化について記載がある。このとき各シンボルの予測条件には変化がないため、(インターバル)-n×(LPSインターバル)のように予め定めたnシンボル分、一括して符号化することができる。
【００２０】
また、特許文献２には、算術圧縮装置において、MPS符号の入力が続く場合に、それらの符号を一括して圧縮する方法について記載がある。これは、一括圧縮の際に正規化が発生しないことを検知して、正規化の発生しない範囲でのみ一括圧縮を行うものである。
【００２１】
また、特許文献３には、コンテクストが特定のパターンとなり、かつ他の条件が一括圧縮可能な条件を満たす場合に処理を高速化する方法について記載がある。
【特許文献１】特公平７−９５６９３号公報（公告日：1995年10月11日）
【特許文献２】特開２０００−３５００４３号公報（公開日：2000年12月15日）
【特許文献３】特開平５−６７９７８号公報（公開日：1993年3月19日）
【非特許文献１】ITU-T(International Telecommunication Union Telecommunication standardization sector) WHITE BOOK ディジタル静止画像圧縮符号化関連勧告書(財団法人 新日本ITU協会) 勧告T.82
【非特許文献２】WTSC-93 (WORLD TELECOMMUNICATION STANDARDIZATION CONFERENCE), Helsinki, 1-12 MARCH 1993
【発明の開示】
【発明が解決しようとする課題】
【００２２】
しかしながら、上述の従来の構成では、正規化の発生によって圧縮条件（劣勢シンボルの確率推定）が変わってしまうので、正規化の発生の有無を検知する必要があるという問題を生ずる。
【００２３】
特許文献１の方式では、正規化が発生すると劣勢確率シンボルの確率推定が変化するため、一括圧縮を続けることはできない。すなわち、正規化処理がいつ発生するかによって一括圧縮可能なセルの個数が制限されてしまう。
【００２４】
また、特許文献２に記載されている方法では、一括符号化するために、nシンボルの間にわたって正規化処理が発生しないことを検知する必要がある。これは、一括圧縮の途中で正規化処理が行われると、(インターバル)-n×(LPSインターバル)のLPSインターバルが変化してしまうためである。
【００２５】
しかしながら、このように正規化処理が発生しないことを検知するためには、インターバルからLPSインターバルを何回引くと正規化が発生するかを求めるという演算が毎回発生する。そのため、画像によっては高速化の効果が全く得られないか、逆に遅くなってしまう場合もある。
【００２６】
また、特許文献３の方式では、特定のパターン以外は高速化を行うことはできない。すなわち、同一のコンテクストが続く場合にのみしか適用できない。
【００２７】
本発明は、上記の問題点に鑑みてなされたものであり、その目的は、正規化の発生にかかわらず一括圧縮を行う符号化方法符号化装置、プログラムおよび記録媒体を提供することにある。
【課題を解決するための手段】
【００２８】
本発明に係る符号化方法は、上記課題を解決するために、２値の入力信号列を、入力信号の予測値である優勢確率シンボルおよび予測値ではない劣勢確率シンボルの出現確率に応じて、この出現確率の推定値を用いて符号化する符号化方法において、上記劣勢確率シンボルの出現確率の推定値に下限を設けてあり、入力信号が優勢確率シンボルである場合に、劣勢確率シンボルの出現確率の推定値が下限の値であるか否かを検知する最小検知工程と、上記最小検知工程にて上記劣勢確率シンボルの出現確率の推定値が下限の値であると検知した場合に符号化をせずにインクリメントした一括圧縮セルカウンタが１以上であるときに、この一括圧縮セルカウンタの数に応じて一括圧縮をする一括圧縮工程とを含んでいることを特徴としている。
【００２９】
本発明に係る符号化方法は、上記課題を解決するために、上記構成において、符号化方法自身の実装形態がQM-coder又はQM-coderと同じ圧縮結果を出力するものであり、上記最小検知工程において、劣勢確率シンボルの出現確率の推定値が下限の値であることを、上記QM-coderの確率推定表における劣勢確率シンボルの出現確率の推定値のインデックスが１３であることによって判定することを特徴としている。
【００３０】
本発明に係る符号化方法は、上記課題を解決するために、上記構成において、上記一括圧縮工程において、上記一括圧縮セルカウンタの数に応じて、圧縮によって発生する正規化の回数を算出し、その算出した正規化回数に基づいて符号化処理を行うことを特徴としている。
【００３１】
本発明に係る符号化装置は、上記課題を解決するために、２値の入力信号列を、入力信号の予測値である優勢確率シンボルおよび予測値ではない劣勢確率シンボルの出現確率に応じて、この出現確率の推定値を用いて符号化する符号化装置において、上記劣勢確率シンボルの出現確率の推定値に下限を設けてあり、入力信号が優勢確率シンボルである場合に、劣勢確率シンボルの出現確率の推定値が下限の値であるか否かを検知する最小検知部と、上記最小検知部にて上記劣勢確率シンボルの出現確率の推定値が下限の値であると検知した場合に符号化をせずにインクリメントした一括圧縮セルカウンタが１以上であるときに、この一括圧縮セルカウンタの数に応じて一括圧縮をする一括圧縮部とを含んでいることを特徴としている。
【００３２】
本発明に係るプログラムは、コンピュータを、上述の符号化装置を有するプリンタドライバとして機能させるためのプログラムである。
【００３３】
本発明に係る記録媒体は、上述のプログラムを記録したコンピュータ読み取り可能な記録媒体である。
【発明の効果】
【００３４】
本発明に係る符号化方法は、２値の入力信号列を、入力信号の予測値である優勢確率シンボルおよび予測値ではない劣勢確率シンボルの出現確率に応じて、この出現確率の推定値を用いて符号化する符号化方法において、上記劣勢確率シンボルの出現確率の推定値に下限を設けてあり、入力信号が優勢確率シンボルである場合に、劣勢確率シンボルの出現確率の推定値が下限の値であるか否かを検知する最小検知工程と、上記最小検知工程にて上記劣勢確率シンボルの出現確率の推定値が下限の値であると検知した場合に符号化をせずにインクリメントした一括圧縮セルカウンタが１以上であるときに、この一括圧縮セルカウンタの数に応じて一括圧縮をする一括圧縮工程とを含んでいる構成である。
【００３５】
上記構成において、２値の入力信号（入力ビット）列を、入力信号の予測値である優勢確率シンボル(MPS)および予測値ではない劣勢確率シンボル(LPS)の出現確率に応じて、この出現確率の推定値を用いて符号化する際には、入力信号に応じて、予め定めた手順で、圧縮結果である実数ｘの存在し得る範囲（以下ではインターバルと呼ぶ。）を変化させる。
【００３６】
より詳細には、前回の入力信号までの入力列から次の（今回の）入力ビットの予測値（優勢確率シンボル）を計算する。また、この予測に応じて、優勢確率シンボルの出現確率と予想されなかった方の劣勢確率シンボルの出現確率の比に応じて、インターバルを２つの領域に分割する。優勢確率シンボルの出現確率に応じたMPSインターバルは、０により近い方の領域とする。また、０から遠い方の領域は、LPSの出現確率に応じたLPSインターバルとする。入力ビットとMPSとが一致する場合には、現在のインターバルからLPSインターバルを取り除くように、インターバルを変化させる。一方、入力ビットとMPSとが一致しない場合には、現在のインターバルからMPSインターバルを取り除くように、インターバルを変化させる。
【００３７】
上述のような手順を行うにあたって、圧縮処理を実施していくと、インターバルの大きさが次第に小さくなり、やがて計算機の固定精度では表現できなくなってしまう。そこで、インターバルの大きさが0.5以上となるまで繰り返しインターバルの大きさを２倍にしていく、正規化処理と呼ばれる処理を行う。
【００３８】
さらに、上記構成においては、劣勢確率シンボルの出現確率の推定値に下限を設けている。これは、符号化方法を計算機において実現する場合に、劣勢確率シンボルの推定値の精度が有限となり、下限を持つことになるからである。
【００３９】
上記符号化方法においては、入力信号が優勢確率シンボルである場合に、劣勢確率シンボルの出現確率の推定値が下限の値であるか否かを検知する最小検知工程を行う。
【００４０】
さらに、最小検知工程にて劣勢確率シンボルの出現確率の推定値が下限の値であると検知した場合には、符号化をせずに一括圧縮セルカウンタをインクリメントする。すなわち、符号化はあとでまとめて行なうため、ここでは符号化しない。その後、この一括圧縮セルカウンタの数に応じて一括圧縮をする（一括圧縮工程）。なお、一括圧縮工程は、例えば入力ビットがLPSであり、かつ一括圧縮セルカウンタの値が１以上であるときに行う。または、一括圧縮工程は、例えば入力ビットがMPSであり、かつ劣勢確率シンボルの出現確率の推定値が下限の値ではなく、かつ一括圧縮セルカウンタの値が１以上であるときに行う。
【００４１】
上記構成のように、劣勢確率シンボル(LPS)の確率推定値が最小値の場合に限って一括圧縮を行なう。この場合、正規化が発生してもLPSの確率推定値はそれ以上変化しない。つまり、優勢確率シンボル(MPS)を符号化する際に、正規化が発生しても、LPSインターバルを取り除くようにインターバルから減ずる値が変化しない。このため、一括圧縮の最後での簡単な演算によって、正規化が発生した後の各パラメータの値を求めることが可能である。したがって、正規化の発生にかかわらず一括圧縮を行なって圧縮の高速化を図ることができる。なお、上記構成において、劣勢確率シンボルの確率推定値が最小値の場合には、この状態についての確率推定値のインデックスは、正規化後後も同じインデックスとなる。
【００４２】
なお、上述の符号化方法を、劣勢シンボル（ＬＰＳ）の確率推定値に下限を設けた算術符号化において、２値シンボル列から逐次注目シンボルを選択するステップと、注目シンボルが優勢シンボル（ＭＰＳ）である（条件１）か否か判定するステップと、注目シンボルのコンテクストに対するＬＰＳの確率推定値が最小値である（条件２）か否か判定するステップと、二つの条件が共に真である場合は、ＭＰＳに対する符号化処理に代えて二つの条件が共に真である注目シンボル連続数をカウントするステップと、二つの条件のいずれかが偽でありかつ直前までの二つの条件が共に真である注目シンボル連続数がゼロでなければ、この連続数分の符号化を一括して行うステップとを有することを特徴とする算術符号化方法である、と表現することもできる。
【００４３】
本発明に係る符号化方法は、上記構成において、符号化方法自身の実装形態がQM-coder又はQM-coderと同じ圧縮結果を得られるものであり、上記最小検知工程において、劣勢確率シンボルの出現確率の推定値が下限の値であることを、上記QM-coderの確率推定表における劣勢確率シンボルの出現確率の推定値のインデックスが13であることによって判定する構成である。
【００４４】
ここで、QM-Coderとは、２値画像データをマルコフ情報源でモデル化し、符号化シンボルをその周辺画素の状態によって予測し、予測結果を算術符号化する方式の一つであり、JBIG(ITU-T T.82)における符号化方式である。
【００４５】
また、上記符号化方法は、JBIGの仕様に基づくQM-coderに限るものではなく、QM-coderと同じ圧縮結果を得られるものであればよく、QM-Coderの動作を模倣しているものであればよい。このように表現するのは、本発明における高速化を行なった場合には、QM-coderと同じ出力が得られるが、それをQM-coderと呼ぶことが適切でない場合も考えられるためである。
【００４６】
QM-Coderにおいては、LPSの確率推定値の最小値に対してLSZのインデックスＳＴの値として13が割り当てられている。このため、ＳＴの値が13かどうかを調べるだけで、LPSの確率推定値が最小であることを知ることができ、処理を減らすことができる。
【００４７】
本発明に係る符号化方法は、上記構成において、上記一括圧縮工程において、上記一括圧縮セルカウンタの数に応じて、圧縮によって発生する正規化の回数を算出し、その算出した正規化回数に基づいて符号化処理を行う構成である。
【００４８】
ここで、正規化処理を行なうと、圧縮に必要なパラメータが変化するとともに、場合によっては圧縮結果の出力を行なう必要が生じる。一括圧縮を行なう場合においても、通常の圧縮手順と同じように、正規化によって圧縮結果の出力を行なう必要が生ずる場合がある。
【００４９】
上述のようにLPSの確率推定値が最小の場合においては、この出力すべき圧縮結果と、一括圧縮後の各パラメータの値とを、通常の手順によって圧縮を行なった場合に発生する正規化の回数から、簡単な演算によって求めることができる。
【００５０】
このため、一括圧縮の最後での正規化の発生回数とその際の出力、各パラメータの変化を求めれば、本来一括圧縮中に正規化処理が必要となる場合であっても、通常の手順で圧縮を行なった場合と同じ結果を得ることができる。
【００５１】
なお、上述の符号化方法を、二つの条件が共に真である注目シンボル連続数分の符号化は、連続中に本来発生したはずの正規化の回数を算出し、算出した正規化回数に基づいて符号化処理を行う構成である、と表現することもできる。
【００５２】
本発明に係る符号化装置は、２値の入力信号列を、入力信号の予測値である優勢確率シンボルおよび予測値ではない劣勢確率シンボルの出現確率に応じて、この出現確率の推定値を用いて符号化する符号化装置において、上記劣勢確率シンボルの出現確率の推定値に下限を設けてあり、入力信号が優勢確率シンボルである場合に、劣勢確率シンボルの出現確率の推定値が下限の値であるか否かを検知する最小検知部と、上記最小検知部にて上記劣勢確率シンボルの出現確率の推定値が下限の値であると検知した場合に符号化をせずにインクリメントした一括圧縮セルカウンタが１以上であるときに、この一括圧縮セルカウンタの数に応じて一括圧縮をする一括圧縮部とを含んでいる構成である。
【００５３】
上記構成の符号化装置は、例えばQM-coderのような算術圧縮装置である。符号化装置は、例えば計算機上で実現されるため、劣勢シンボルの確率推定の精度が有限である。このため、劣勢シンボルの確率推定は下限を持つ。
【００５４】
この場合、上記符号化装置は、例えば上述の符号化方法を用いて、LPSの確率推定値が最小であるようなMPSが連続する部分を、一括して圧縮することができる。
【００５５】
より詳細には、符号化装置は、入力信号が優勢確率シンボルである場合に、劣勢確率シンボルの出現確率の推定値が下限の値であるか否かを検知する、最小検知工程を行う最小検知部を備えている。また、最小検知部にて最小検知工程として劣勢確率シンボルの出現確率の推定値が下限の値であると検知した場合には、符号化をせずに一括圧縮セルカウンタをインクリメントする。符号化装置は、この一括圧縮セルカウンタの値が１以上であると検知したときに、一括圧縮セルカウンタの数に応じて一括圧縮をする、一括圧縮工程を行う一括圧縮部を備えている。したがって、この符号化装置を用いて、上述の符号化方法を実現できる。
【００５６】
なお、上述の符号化装置を、劣勢シンボル（ＬＰＳ）の確率推定値に下限を設けた算術符号化において、コンテクストに対するＬＰＳの確率推定値が最小値であることを判定する手段と、注目シンボルがＭＰＳでありかつ注目シンボルのコンテクストに対するＬＰＳの確率推定値が最小値であるシンボルの連続数をカウントする手段と、を備えた算術符号化装置である、と表現することもできる。
【００５７】
本発明に係るプログラムは、コンピュータを、上述の符号化装置を有するプリンタドライバとして機能させるためのプログラムである。
【００５８】
このプログラムを用いて、コンピュータを、上述の符号化装置を有するプリンタドライバとして機能させることができる。
【００５９】
本発明に係る記録媒体は、上述のプログラムを記録したコンピュータ読み取り可能な記録媒体である。
【００６０】
この記録媒体を用いて、コンピュータを、上述の符号化装置を有するプリンタドライバとして機能させることができる。
【発明を実施するための最良の形態】
【００６１】
本発明の一実施形態について図１ないし図１１に基づいて説明すると以下の通りである。
【００６２】
本実施形態は、本発明に係る符号化方法を、ITU-T(International Telecommunication Union Telecommunication standardization sector) WHITE BOOK ディジタル静止画像圧縮符号化関連勧告書(財団法人 新日本ITU協会) 勧告T.82に記載されている、JBIGのQM-Coderに適用した場合の例である。
【００６３】
JBIGのQM-Coderは、２値画像データをマルコフ情報源でモデル化し、符号化シンボルをその周辺画素の状態によって予測し、予測結果に応じて算術符号化する方式を用いている。JBIG圧縮はプログレッシブ方式を取っているが、ここでは、説明を簡単にするために最低解像度レイヤのみを持つJBIG圧縮について扱う。また、説明を簡単にするため、コンテクストの形状を変化させるAT(Adaptive Template)移動などJBIGの仕様に含まれる付加的な機能に関しては説明を省略する。
【００６４】
本実施形態の符号化装置（算術圧縮装置）１は、２値画像データを符号化して符号化データを出力する。この符号化装置１は、例えば図示しないパーソナルコンピュータのプリンタドライバにおける符号化圧縮部として機能する。このプリンタドライバは、パーソナルコンピュータの図示しない記憶部（記録媒体）に蓄積されたプログラムをパーソナルコンピュータのＣＰＵ(Central Processing Unit)が読み込んで実行することによって実現される。パーソナルコンピュータに対するユーザの指示に応じて、プリンタドライバは、印刷ドキュメントを画像に変換したデータを符号化装置１を用いてJBIG圧縮して、プリンタ本体に送信する。プリンタ本体では、受信したJBIG画像を復号して、印刷を行う。これによって、プリンタドライバにおける圧縮を高速化することができる。
【００６５】
符号化装置１における算術圧縮について、図２に基づいて概略の説明をする。符号化装置１は、算術圧縮として、２値の入力信号（入力ビット）列を０以上１未満の実数ｘに変換する。圧縮結果である符号化データは、非常に長い一つの小数となる。
【００６６】
ここで、圧縮結果である実数ｘの存在し得る範囲を、以下ではインターバルと呼ぶ。図２に示すように、まだ１ビットも入力が行なわれていない時点では、明らかにインターバルは０以上１未満の領域となる。
【００６７】
このインターバルを、入力信号に応じて、予め定めた手順で変化させる。入力信号にも関わらずインターバルが変化しなくなった場合に、そのインターバルの最小値である低数を圧縮結果とする。符号化装置１において、インターバルは、その時点でのインターバルの最小値である低数と、インターバルの大きさとによって記憶されている。
【００６８】
より詳細には、符号化装置１は、前回の入力信号までの入力列から次の（今回の）入力ビットを予測する。また、この予測に応じて、インターバルを２つの領域に分割する。本実施形態の符号化装置１においては、予測の際に、周辺の画素の状態それぞれに対して優勢確率シンボルと劣勢シンボル確率推定を持つ。これにより、周辺の画素の状態に対して過去の入力から０または１のどちらのシンボルが出現しやすいかを判断する。
【００６９】
ここで、出現すると予想された入力ビットを優勢確率シンボル(MPS)と呼ぶ。予想されなかった方の入力ビットを劣勢確率シンボル(LPS)とする。また、予想とともに、優勢確率シンボルの出現確率と劣勢確率シンボルの出現確率の比に応じて、インターバルを２つの領域に分割する。優勢確率シンボルの出現確率に応じたMPSインターバルは、０により近い方の領域とする。また、0から遠い方の領域は、LPSの出現確率に応じたLPSインターバルとする。
【００７０】
この状態で、信号の入力に応じて、入力ビットと優勢確率シンボル(MPS)との比較を行う。入力ビットとMPSとが一致する場合には、現在のインターバルからLPSインターバルを取り除くように、インターバルを変化させる。一方、入力ビットとMPSとが一致しない場合には、現在のインターバルからMPSインターバルを取り除くように、インターバルを変化させる。
【００７１】
図２には、入力ビットが0001であり、そのときの優勢確率シンボル(MPS)が0101のようであった場合の一例を示す。２ビット目の入力は劣勢確率シンボルであるから、LPSインターバルが選択され、その他は優勢確率シンボルであるからMPSインターバルが選択される。
【００７２】
ここで、全ての入力列に対する処理が完了したときのインターバルの低数を実数ｘとし、この実数ｘを圧縮結果とする。上述の処理手順によって、入力ビットが予想される入力ビットと一致する場合には、インターバルの低数に変化を生じない。このため、出力(圧縮結果)にも変化を生ずることがなく、新たなビットを出力する必要もないので、これを利用して圧縮を行なうことができる。なお、全ての入力が優勢確率シンボルであれば圧縮結果ｘは０となる。
【００７３】
上述のような手順を行うにあたって、QM-Coderの動作を模倣している符号化装置１においては、以下の手順がさらに必要となる。すなわち、上述の算術圧縮処理を実施していくと、インターバルの大きさが次第に小さくなる。このため、やがて計算機の固定精度では表現できなくなってしまう。そこで、インターバルの大きさが0.5以上となるまで繰り返しインターバルの大きさを２倍にしていく、正規化処理と呼ばれる処理を行う。
【００７４】
符号化装置１においては、インターバルの大きさをメモリ領域のレジスタＡ（Areg）に保持し、インターバルの低数をメモリ領域のレジスタＣ(Creg)に保持している。ここで、本実施形態では、インターバルを、0x0から0x10000で表現する。この場合、レジスタＡには、大きさが0.5(0x8000で表す)以上かつ１(0x10000で表す)以下となるように正規化されたインターバルが入る。
【００７５】
また、レジスタＡに記憶される値が、正規化処理によって２倍にされる度に、レジスタＣに記憶される値も２倍とする。このため、レジスタＡの値を２倍化していることによる出力への影響は相殺される。また、レジスタＣの値は、オーバーフローしないように、上位バイトが適時取り出され、圧縮結果として出力されるようになっている。なお、この際に発生するキャリーオーバーを解決する方法がITU-T T.82に記載されているが、本発明の内容を理解する上で必須ではないため、ここでは説明を省略する。
【００７６】
また、符号化装置１においては、以下のような近似を行うようになっている。例えば、LPSインターバルを計算するには、本来(インターバルの大きさ)×(LPS出現確率)という演算が必要である。符号化装置１においては、このLPSインターバルの値を、統計的に求められた推定値(LSZ)によって近似する。このように近似すると、その時点でのインターバルの大きさが0x10000とは限らないということを考慮せずにLPSインターバルの値を決めることになるため、インターバル全体のうちLPSインターバルの占める割合は、インターバルの大きさに応じて変化してしまう。しかしながら、インターバルは大きさが0.5以上かつ１以下となるように正規化されているため、誤差はそれほど大きくはならない。
【００７７】
すなわち、インターバル全体の値は0または1の出現確率の合計であるから、本来は１であるべきだが、演算を行なう都合上、0.5から1.0までの範囲におさまっていればよいこととしている。このため、インターバルの大きさが小さければ、LPSインターバルを引いたときにLPSインターバル＞MPSインターバルとなる可能性がある。
【００７８】
以上をまとめると、符号化装置１において、入力としてMPSが与えられた際にはインターバルからLSZを引く。また、符号化装置１は、入力としてLPSが与えられたときには、インターバルをLSZとする。符号化装置１は、この操作の結果インターバルが0.5以下となったときには正規化を行なう。正規化が行なわれたときにはLSZの値を更新する。また、上述の操作によって、MPSインターバルよりもLPSインターバルの方が大きくなってしまう場合がある。このときは、MPSインターバルとLPSインターバルの入れ替えを行なう。
【００７９】
ここで、上述のような算術圧縮の手順を、計算機や電子回路などに実装する場合には、有限の計算精度でも圧縮を行うことができるように、劣勢確率シンボルの確率推定には最小値を持たせるのが一般的である。算術圧縮においては圧縮中に正規化が発生すると劣勢確率シンボルの確率推定を減少させるが、上述のような実装形態においては、既に劣勢確率シンボルの確率推定が最小になっていれば、それ以上劣勢確率シンボルの確率推定は減少しない。このような場合には、簡単な演算で、任意個のMPSを一括圧縮した際のパラメータの変化とその際の符号化出力とを求めることが可能となり、通常の手順で圧縮を行った場合と同じ出力を得ることができる。
【００８０】
次に、上述の圧縮処理を行う符号化装置１の構成について、図１に基づいて詳細に説明する。本実施形態の符号化装置１は、図１に示すように、概略的に、コンテクスト生成部２、取得部３、算術符号部４、記録部５、およびレジスタ（メモリ）６を備えている。この符号化装置１においては、上述の圧縮処理を計算機上で実装するために、固定精度の整数演算で近似をしている。
【００８１】
コンテクスト生成部２は、入力画像データから、対象となるセルおよびその周辺のコンテクストを抽出するものである。対象となるセルとコンテクストとの関係を、図３に基づいて説明する。上述のように、QM-coderの動作を模倣した符号化装置１においては、予測の際に、前回の入力信号までの入力列だけでなく、周辺の画素の状態をも用いるようになっている。すなわち、符号化装置１は、予測の際に、周辺の画素の状態それぞれに対して優勢確率シンボルと劣勢シンボル確率推定を持つ。
【００８２】
ここで、今回の入力ビットである対象セル（符号化画素）を選択した場合に、この符号化画素の周辺の幾つかの画素として、図３に示すようにコンテクスト（周辺画素の配列）を選択する。図３において、斜線部分が圧縮対象となる対象セルであり、その周辺の10個の四角がコンテクストの各セルを表している。なお、コンテクストのセル数は10個であり、各セルは0または1の値を持つので、その組み合わせの数は1024通りとなる。また、JBIG圧縮では、最低解像度レイヤのコンテクストとして、図３に示すような２ラインテンプレートの他に、３ラインテンプレートも用意されており、こちらを用いることもできる。ここでは２ラインテンプレートを用いるものとする。
【００８３】
コンテクスト生成部２は、抽出したセルおよびコンテクストを取得部３に出力する。また、コンテクスト生成部２は、算術符号部４の符号処理部９からのセルインクリメント指示を受信すると、入力画像データから、次の対象セルおよびコンテクストを抽出する。
【００８４】
次に、取得部３について説明する。取得部３は、予測値としての優勢確率シンボル(MPS)を、周辺画素の配列(コンテクスト)に対する優勢確率シンボルを記録した記録部５の確率推定テーブル７から取得する。
【００８５】
ここで、確率推定テーブル７は、図４に示すように、コンテクストと、そのコンテクストから予想されるMPSの値との関係を含んでいる。また、確率推定テーブル７は、コンテクストと、このコンテクストに応じたLPSインターバルの推定値(LSZ)のインデックスＳＴとの関係も含んでいる。LSZについては後述する。取得部３は、入力されるコンテクストを用いて、記録部５の確率推定テーブル７にアクセスして、インデックスＳＴを得る。取得部３は、MPSとインデックスＳＴとを得ると、セルの値、MPS、インデックスＳＴを算術符号部４に出力する。
【００８６】
算術符号部４は、入力されるセルの値、MPS、インデックスＳＴから、符号化データである実数ｘを生成する。この算術符号部４は、符号処理部９および前処理部１０を含んでいる。
【００８７】
符号処理部９は、前処理部１０から入力される選択信号に応じて、各処理部９ａ〜９ｅのうちから適切な処理部を選択する。また入力されたセルの値、MPS、ＳＴを用いて、選択した処理部によって符号化データを生成する。符号処理部９は、ＭＰＳ処理部９ａ、ＬＰＳ処理部９ｂ、ＲＥＮＯＲＭ処理部９ｃ、ＭＵＬＭＰＳ処理部（一括圧縮部）９ｄ、ＭＵＬＲＥＮＯＲＭ処理部（一括圧縮部）９ｅを含んでいる。各処理部９ａ〜９ｅにおける処理の詳細については後述する。
【００８８】
前処理部１０は、取得部３から入力されるセルの値、MPS、ＳＴに応じて、選択信号を生成して、符号処理部９に出力する。前処理部１０は、最小検知部１０ａ、一括チェック部１０ｂ、および選択部１０ｃを含んでいる。
【００８９】
前処理部１０の最小検知部１０ａは、入力されるインデックスＳＴが13となっているかどうかを調べる。後述するように、インデックスＳＴが13のとき、ＬＳＺの値は最小となる。最小検知部１０ａは、インデックスＳＴが１３となっている場合には、レジスタ６の一括圧縮セルカウンタ６ｃの値（セルカウンタ）ｔを１だけインクリメントする。このように、最小検知部１０ａが確率推定最小値検知装置として機能して、LSZが最小値となっているかどうかを調べるようになっている。
【００９０】
一括チェック部１０ｂは、レジスタ６の一括圧縮セルカウンタ６ｃの値ｔが０を超えているか（１以上であるか）否かを判別するものである。一括チェック部１０ｂは、最小検知部１０ａおよび一括チェック部１０ｂ自身の判別結果を選択部１０ｃに出力する。
【００９１】
選択部１０ｃは、選択信号を生成するために、入力されるセルの値とＭＰＳとから、圧縮対象のシンボルがコンテクストに対する優勢確率シンボルか劣勢確率シンボルかを判断する。また、選択部１０ｃは、一括チェック部１０ｂの判別結果を受信する。選択部１０ｃは、入力に応じて選択信号を生成して、符号処理部９に出力する。選択部１０の詳細な動作については後述する。
【００９２】
記録部５には、確率推定テーブル７と確率推定表８とが記録されている。なお、確率推定テーブル７と確率推定表８とは、全く別のものである。テーブルは表とも訳し得るが、ITU-T T.82の日本語訳(ITU-T WHITE BOOK ディジタル静止画像圧縮符号化関連勧告書 勧告T.82)でこのようになっているため、その語句をそのまま用いることとする。
【００９３】
確率推定テーブル７は、コンテクストごとの優勢確率シンボルMPSと、LSZのインデックスSTとを保存するテーブルである。本実施形態においては、コンテクストごとのMPS(1ビット)とLSZのインデックスST(7ビット)とを保存している。このため、各コンテクストに対して１バイト(8ビット)の情報を有している。本実施形態のように、コンテクストが10セル分の大きさを持つ場合には、２の10乗個のコンテクストそれぞれに対して１バイトの大きさを有することになり、確率推定テーブル７全体は1024バイトとなる。この確率推定テーブル７は、圧縮処理の間、書き換えが行なわれる。
【００９４】
より詳細には、確率推定テーブル７は、確率推定表８のインデックスSTと優勢確率シンボルMPSとを更新しながら圧縮される。なお、一括圧縮中には、STの値、および優勢確率シンボルMPSのどちらも変化しないので、確率推定テーブル７の書き換えは発生しない。一方、通常の圧縮中には、MPSかLPSかをエンコードするたびにSTの値が変化するため、確率推定テーブル７の書き換えが生じる。また、LPSがMPSを超えれば優勢確率シンボルが入れ替わるため、このときも確率推定テーブル７を書き換える。
【００９５】
なお、優勢確率シンボルは、０または１の値を取る。LSZのインデックスＳＴは、JBIGにおいては、0から112までのどれかの値を取る。また、コンテクストが１０ビットである一方で、インデックスは７ビットであるので、同じインデックスをもつ異なるコンテクストが存在することになる。すなわち、それぞれのコンテクストの持つLSZのインデックスや優勢確率シンボルは独立なので、例えばコンテクスト0x0000000000と0x0000000001のLSZのインデックスＳＴが共に13というようなことも起こり得る。このLSZのインデックスＳＴは、後述するJBIGの確率推定表８において、近傍１０画素に出現したシンボル０or１の組合せ状況（コンテクスト）ごとに、これまで注目画素の位置に出現したシンボルの履歴から注目画素に出現するであろうシンボルの出現確率の予測を表すために用いられる。
【００９６】
一方、確率推定表８は、図５（ａ）（ｂ）に示すITU-T T.82表24のように、LSZのインデックスSTから、LSZや次のSTなどを求めるための表である。確率推定表８からLSZを求めるために、確率推定テーブル７から得たLSZのインデックスＳＴが使用される。この確率推定表８は、圧縮処理の際にも書き換えられることはない。すなわち、確率推定表８は、参照されるだけで、書き換えられることはない。
【００９７】
LSZのインデックスＳＴは、確率推定テーブル７に関して説明したように、７ビットの情報である。本実施形態のようにJBIG圧縮の場合には、インデックスSTのとり得る値は0から112までとなる。また、LSZは、上述のように、LSZのインデックスに応じた、劣勢確率シンボルのインターバル（の近似値）を意味する。また、ＮＬＰＳは、劣勢確率シンボルを圧縮したときの次のＳＴの値を意味する。また、ＮＭＰＳは、優勢確率シンボルを圧縮して正規化が発生したときの次のＳＴの値を意味する。なお、正規化が発生しないときには、ＳＴの値は更新されない。また、ＳＷＩＴＣＨは、優勢確率シンボルの入れ替えを行なうかどうかのフラグを意味する。
【００９８】
ここで、図５（ａ）（ｂ）に示すように、ＳＴの値は0から112までの値を取るが、このＳＴが13のときにLSZは最小となる。また、ＳＴが13のときには、優勢確率シンボルを圧縮して正規化が発生したときの次のＳＴの値であるNMPSが13となっている。すなわち、ＳＴが13のときには、優勢確率シンボルを圧縮しているときに正規化が発生してもＳＴの値は13のまま変化しないことが分かる。図５（ａ）（ｂ）に示すように、このようなＳＴの値は13だけである。
【００９９】
また、STが13のときのLSZの値は0x1である。このため、一括圧縮中に正規化が発生したときに必要な２倍化処理の回数は、正規化一回につき２倍化処理１回だけで良い。なぜなら、一個の優勢確率シンボルを符号化して正規化が発生する場合、直前のインターバル(Ａレジスタの値)は0x8000であり、一個の優勢確率シンボルを符号化したときにはこれから0x1であるLSZの値を引くことになるためＡレジスタの値は0x7fffとなり、これを2倍にすると0xfffeとなる。この値は0x8000より大きいため、これ以上２倍化処理を行なう必要はないからである。
【０１００】
なお、優勢確率シンボルを符号化した場合には、正規化が発生しない場合が存在する。このように正規化が発生しないときにはＳＴは変化しない。確率推定表８を参照してインデックスＳＴを変化させるのは正規化が発生したときだけである。なお、例えば従来の構成では、このことを利用して正規化の発生しない範囲で一括圧縮を行なっている。
【０１０１】
また、図５（ａ）（ｂ）に示すように、STの値が112のときにLSZは最大となる。このときには、劣勢確率シンボルを圧縮してもＳＴは変化しなくなる。これを利用して劣勢確率シンボルを符号化したときの演算を高速化することが考えられるが、実際にはＳＷＩＴＣＨの値が１であり、MPSとLPSの入れ替えが発生するためにうまく高速化できない。
【０１０２】
また、符号化装置１は、作業用メモリとしてのレジスタ６を備えている。このレジスタ６は高速アクセス可能なメモリである。レジスタ６は、Areg６ａ、Creg６ｂおよび一括圧縮セルカウンタ６ｃを含んでいる。
【０１０３】
Areg６ａは、インターバルの大きさを保持するための記憶領域であるレジスタＡに蓄積された値を意味する。また、Creg６ｂは、インターバルの低数を保持する記憶領域であるレジスタＣに蓄積された値を意味する。Areg６ａおよびCreg６ｂは、整数で固定精度である。
【０１０４】
一括圧縮セルカウンタ６ｃは、一括圧縮を行なうセルの数ｔの値である。一括圧縮セルカウンタ６ｃの初期値はｔ＝０とする。この一括圧縮セルカウンタ６ｃの値ｔは、最小検知部１０ａが変化させる。
【０１０５】
上記構成の符号化装置１における圧縮処理の詳細について、図６に基づいて説明する。
【０１０６】
符号化装置１のコンテクスト生成部２に入力画像データが入力されると、コンテクスト生成部２は、入力画像データを、１ライン以上の横ラインからなるストライプに分割する。このストライプは、幅が画像の幅と同じであり、高さは１ライン以上で画像の高さ以下の領域である。
【０１０７】
符号化装置１は、圧縮処理をストライプ単位で行う。Ｓ１から一つのストライプについての処理を開始し、Ｓ１〜Ｓ１８のループ(LOOP1)においてそのストライプの処理が完了すると、次のストライプの処理をＳ１から開始する。Ｓ１〜Ｓ１８までのループによって全てのストライプに対して処理が完了すると、画像データ全体の圧縮が完了する。また、Ｓ１では、Creg６ｂに何ビット分の出力があるかを計測するためのカウンタである出力ビットカウンタＣＴを１１に初期化する。このように、JBIGの仕様では、3ビットのダミーがあるため、ストライプの圧縮を開始する際にＣＴの初期値を１１にセットする。なお、ＣＴを１１にセットするのはストライプの先頭でＣＴを初期化するときだけで、実際に出力を行なったときにはＣＴを８にセットする。
【０１０８】
Ｓ２において、コンテクスト生成部２は、選択したストライプのうちから、圧縮対象となる一つのセルを選択する。Ｓ２〜Ｓ１４のループ(LOOP2)において対象となるセルの圧縮を行うと、次のセルについての処理をＳ２から開始する。このとき、次のセルは、例えばストライプの左上から右下に向けて移動させるように順次一つずつ選択する。したがって、例えば横方向に１ライン分のセルとコンテクストの読み取りを完了すると、その下のラインの読み取りへと進む。全ての画素の処理が完了すると１つのストライプの処理が完了したことになる。
【０１０９】
Ｓ３において、コンテクスト生成部２は、対象となるセルと、対象となるセルについてのコンテクストを、ストライプから抽出する。コンテクスト生成部２は、抽出したセルとコンテクストとを、取得部３へと出力する。
【０１１０】
Ｓ４では、取得部３が、確率推定テーブル７を参照して、入力されたコンテクストに応じたMPSを取得する。また、取得部３は、入力されたコンテクストに応じたLSZのインデックスＳＴを確率推定テーブル７から取得する。取得部３は、セルの値、MPS、インデックスＳＴを算術符号部４へと出力する。
【０１１１】
Ｓ５では、算術符号部４において、前処理部１０の選択部１０ｃが、取得部３から入力されるセルの値とＭＰＳとに応じて、対象セルがＭＰＳであるか否かを判別する。対象セルがＭＰＳである場合にはＳ６に進む。この場合、Ｓ６〜Ｓ１０の手順を行い、Ｓ１４に進む。また、Ｓ５において対象セルがＬＰＳである場合にはＳ１１に進む。この場合、Ｓ１１〜Ｓ１３の手順を行い、Ｓ１４に進む。
【０１１２】
Ｓ６においては、前処理部１０の最小検知部１０ａが、入力されるLSZのインデックスＳＴから、LPSインターバルが最小となっているかどうかを判別する。より詳細には、本実施形態においてはJBIG圧縮するので、最小検知部１０ａは、LSZのインデックスＳＴが13であるか否かを判別する。これによって、例えば記録部５の確率推定表８にアクセスして、実際にＬＳＺが最小となっているかどうか確認する手間を省くことができる。LSZのインデックスＳＴが13である場合には、LPSインターバルが最小となっている。LPSインターバルが最小である場合にはＳ７に進み、それ以外の場合にはＳ８に進む。
【０１１３】
Ｓ７においては、最小検知部１０ａが、一括圧縮セルカウンタ(図６中では「セルカウンタ」と略記している。）６ｃの値ｔを１だけインクリメントする。これに応じて、一括チェック部１０ｂからの判別結果を得た選択部１０ｃが選択信号を図１に示す符号処理部９に送信する。この選択信号は、符号処理部９において符号化をせずに、符号処理部９からコンテクスト生成部２へのセルインクリメントのみを行う旨の内容である。なお、符号処理部９は、この時点では圧縮しないが、後でまとめて圧縮を行う。符号処理部９がコンテクスト生成部２にセルインクリメントのための信号を出力し、Ｓ１４に進む。
【０１１４】
一方、Ｓ６においてＬＰＳインターバルが最小でなかった場合のＳ８では、一括チェック部１０ｂが、レジスタ６の一括圧縮セルカウンタ６ｃにアクセスして、このカウンタ値ｔが０を超えているか否かを判別する。このカウンタ値の判別は、一括圧縮を行なう必要があるかどうかを調べるためのものである。カウンタ値が０である場合には一括チェック部１０ｂから判別結果を得た選択部１０ｃがＭＰＳ処理部９ａを選択する旨の選択信号を符号処理部９に出力してＳ９に進む。カウンタ値が０を超えている場合には一括チェック部１０ｂから判別結果を得た選択部１０ｃがまずＭＵＬＭＰＳ処理部９ｄを選択する旨の選択信号を符号処理部９に出力してＳ１０に進む。このように、セルカウンタの値が１以上であれば一括圧縮を行なう必要がある。
【０１１５】
Ｓ９では、符号処理部９のＭＰＳ処理部９ａが、ＣＯＤＥＭＰＳ処理を行う。このＣＯＤＥＭＰＳ処理は、図７に示すＳ２０〜Ｓ２４の処理に相当する。ＭＰＳ処理部９ａは、算術圧縮において入力ビットがＭＰＳであった場合に、インターバルの範囲を変更し、必要がある場合にはＲＥＮＯＲＭ処理部９ｃを呼び出してＣＯＤＥＲＥＮＯＲＭ処理を行わせる。
【０１１６】
入力ビットがＭＰＳであったため、ＭＰＳ処理部９ａは、Ｓ２０において、現在のインターバルからLPSインターバルを取り除くようにインターバルを変化させる。より詳細には、ＭＰＳ処理部９ａは、記録部５の確率推定表８にアクセスして、インデックスＳＴを用いて、LPSインターバルの近似値であるLSZを取得する。また、ＭＰＳ処理部９ａは、レジスタ６にアクセスしてAreg６ａを取得する。ＭＰＳ処理部９ａは、Areg６ａからLSZの値を引くことによって、インターバルを変化させる。ＭＰＳ処理部９ａは、得た値を新たなAreg６ａの値として、レジスタ６に記録する。
【０１１７】
Ｓ２１では、ＭＰＳ処理部９ａが、新たなAreg６ａの値が0.5(0x8000)未満であるか否かを判別する。0.5以上の場合には正規化の必要はないので、ＣＯＤＥＭＰＳ処理を終了し、図６に戻りＳ１４に進む。
【０１１８】
一方、Ｓ２１において新たなAreg６ａの値が0.5(0x8000)未満である場合には、Ｓ２２に進む。Ｓ２２では、ＭＰＳ処理部９ａが、新たなAreg６ａの値がLSZ未満であるか否かを判別する。Areg６ａの値がLSZ以上の場合には、MPSインターバルとLPSインターバルとの入れ替えは不要であるので、Ｓ２４に進む。
【０１１９】
一方、Ｓ２２においてAreg６ａの値がLSZ未満の場合には、ＭＰＳ処理部９ａは、Ｓ２３においてMPSインターバルとLPSインターバルとを入れ替えてＳ２４に進む。より詳細には、ＭＰＳ処理部９ａは、レジスタ６にアクセスしてCreg６ｂを取得する。ＭＰＳ処理部９ａは、Creg６ｂの値にAreg６ａを加えて、新たなCreg６ｂとする。ＭＰＳ処理部９ａは、新たなAreg６ａの値をLSZとする。ＭＰＳ処理部９ａは、新たなAreg６ａ、Creg６ｂを、レジスタ６に記録する。
【０１２０】
Ｓ２４では、ＭＰＳ処理部９ａが、正規化に応じてLSZのインデックスＳＴを更新する。これは、確率推定表８を用いて、優勢確率シンボルを符号化して、かつ正規化が発生した場合の次のSTの値であるNMPSを読取ることによって行う。
【０１２１】
また、Ｓ２４では、ＭＰＳ処理部９ａは、ＲＥＮＯＲＭ処理部９ｃを呼び出して、ＣＯＤＥＲＥＮＯＲＭを実行させる。ＣＯＤＥＲＥＮＯＲＭ処理については後述する。Ｓ２４が終了すると、ＣＯＤＥＭＰＳ処理を終了して、図６に戻り、Ｓ１４に進む。
【０１２２】
次に、ＲＥＮＯＲＭ処理部９ｃの行うＣＯＤＥＲＥＮＯＲＭについて、図８に基づいて説明する。このＣＯＤＥＲＥＮＯＲＭは、正規化が完了するまで２倍化処理を繰り返すとともに、Creg６ｂに値が蓄積されると適宜出力するという処理である。
【０１２３】
Ｓ２５では、ＲＥＮＯＲＭ処理部９ｃは、Areg６ａおよびCreg６ｂをそれぞれ１ビットシフトさせる（Areg＝Areg≪１、Creg＝Creg≪１）とともに、Creg６ｂに何ビット分の出力があるかのカウンタであるＣＴから、１を減ずる。
【０１２４】
Ｓ２５の次のＳ２６では、ＲＥＮＯＲＭ処理部９ｃは、ＣＴの値が０であるか否かを判別する。ＣＴの値が０である場合にはＳ２７に進み、０でない場合にはＳ２８に進む。
【０１２５】
Ｓ２７では、ＲＥＮＯＲＭ処理部９ｃが、Creg６ｂから圧縮結果を１バイト分だけ符号化装置１の外部に出力するとともに、ＣＴの値を８として、Ｓ２８に進む。
【０１２６】
Ｓ２８では、ＲＥＮＯＲＭ処理部９ｃは、Areg６ａの値が0.5(0x8000)未満であるか否かを判別する。Areg６ａの値が0.5(0x8000)未満である場合にはＳ２５に戻り、Areg６ａの値が0.5(0x8000)以上である場合には処理を終了する。
【０１２７】
以上のＳ２５〜Ｓ２８にて、図７のＳ２４において呼び出されたＣＯＤＥＲＥＮＯＲＭ処理が終了する。
【０１２８】
図６に戻ると、Ｓ８において一括圧縮セルカウンタ６ｃのカウンタ値ｔが０を超えていた場合のＳ１０では、符号処理部９のＭＵＬＭＰＳ処理部９ｃが、ＣＯＤＥＭＵＬＭＰＳ処理を行う。この手順は本発明において新しく追加された手順である。ＣＯＤＥＭＵＬＭＰＳ処理は、一括圧縮セルカウンタの値ｔに応じて、正規化の起こる回数を計算して、一括圧縮を行う処理である。ＣＯＤＥＭＵＬＭＰＳ処理は、LSZが最小でない場合、劣勢確率シンボルが与えられる場合、ストライプの終端に達した場合、画像の終端に達した場合、または例えば実装上の都合によってそれ以上一括して圧縮することが好ましくないセルまで達した場合に、そこまでに一括圧縮セルカウンタ６ｃに加えられていた個数分のセルを一括して圧縮するために用いる。ＣＯＤＥＭＵＬＭＰＳ処理について、図１０に基づいて説明する。
【０１２９】
まず、Ｓ４０において、ＭＵＬＭＰＳ処理部９ｃは、Aregの値６ａと一括圧縮セルカウンタの値tとから、一括圧縮の間に与えられたセルに対して何回の正規化処理が発生するかを調べる。なお、t=0の場合はこの手順に来ないため、カウンタ値ｔはt＞0の整数である。
【０１３０】
ここで、LPSインターバルの最小値が0.25より小さい場合には、正規化処理の発生回数と２倍化処理の発生回数は一致する。すなわち、１セルの圧縮を行ったときに劣勢シンボル確率推定の最小値が0.25より小さいならば、一括圧縮の際にインターバルが0.25以下となることはない。このため、一回だけ２倍にすれば0.5以上になる。２倍化処理の発生回数が分かれば、以下のように一括圧縮の際の出力やレジスタ等の値の変化を求めることが可能となる。なお、通常、LPSインターバルの最小値は非常に小さな値となり、0.25よりはるかに小さい値となる。例えば、MPSが連続する場合の圧縮効率を最良にするためには、LPSインターバルの格納領域のビット数で表現可能な最小の値(0x1)を用いる。
【０１３１】
ここで、JBIG圧縮の場合、ITU-T T.82の表24である確率推定表８からすると、図５（ａ）（ｂ）に示すように、劣勢シンボルの最小の確率推定(LPS幅)は、ST=13の場合の0x0001である。そこで、一括圧縮の開始時点でのAreg６ａの値をAreg1とすると、正規化処理回数Xnorは
Xnor = (t - (Areg1 - 0x8000))/0x7fff       …式(1)
となる。なお、小数点以下は切り上げとなる。また、Xnorが0以下の場合には正規化は発生せず、正規化処理は行われない。この式（１）について以下で説明をする。
【０１３２】
まず、ST=13の１つのセルを圧縮するということは、Ａレジスタ(インターバル)から0x0001を引くことに相当する。このとき、0x8000よりＡレジスタの値が小さくなったときには正規化が発生して、Ａレジスタの値が２倍化される。ここで、Ａレジスタからは0x0001ずつ引くことになるので、正規化が発生するときのＡレジスタの値は必ず0x7fffである。この値を2倍するので、正規化後のＡレジスタの値は必ず0xfffeとなる。そして、その0xfffeからさらに0x7fff個圧縮するとまた正規化が発生する。
【０１３３】
計算のためには、まず最初にtから(Areg1 - 0x8000)を引く。Areg1が0x7fffを超えている分については、圧縮を行なっても正規化が発生することはない。さらに、切り上げしたときに正規化の回数が得られるように、Areg1から0x1だけ引くことにする。ここでは、代わりにtに0x1だけ足しているので、元々の演算は((t - (Areg1 - 0x7fff)) + 0x1)である。
【０１３４】
ここで値が0以下(tが1でAreg1=0x10000ならマイナスになる)になるということは、t個圧縮を行なっても(Ａレジスタからtを引いても)Ａレジスタの値は0x8000より小さくなることはなく、正規化は発生しないということを意味する。tから(Areg1 - 0x8000)を引く動作が完了した時点で、1回目の正規化が発生する直前の状態と同じ状態となる。つまり、Ａレジスタの値は0x8000であとt-(Areg1-0x8000)個のセルを圧縮しなければならない。この状態であと0x1個圧縮すると正規化が発生し、次の正規化は0x1+0x7fff個後に発生し、その次の正規化はさらに0x1+0x7fff+0x7fff個圧縮すると発生する。このため、先程のような式(1)となる。
【０１３５】
次に、Ｓ４１では、ＭＵＬＭＰＳ処理部９ｄが、得られたXnorの数に応じて、Xnor回だけ、手順ＭＵＬＲＥＮＯＲＭ処理を呼び出す。このＭＵＬＲＥＮＯＲＭ処理については後述する。
【０１３６】
次に、Ｓ４２においては、ＭＵＬＭＰＳ処理部９ｄが、正規化処理後のＡレジスタの値を、以下のように求める。正規化処理が一度も行われない場合における、一括圧縮が終了した時点でのAregの値Areg2は、
Areg2 = Areg1-t       …式(2)
で与えられる。すなわち、ST=13のときに確率推定は0x0001であるので、１つのセルを圧縮するということは、Ａレジスタ(インターバル)から0x0001を引くということに対応する。すなわち、正規化処理が行なわれないことが分かっている場合には、Ａレジスタの２倍化処理が行なわれることもなく、Areg1-t>=0x8000ということも明らかであるので、単にAreg2=Areg1-(t×0x0001)=Areg1-tとするだけで、一括圧縮後のＡレジスタの値を求めることができる。
【０１３７】
一方、正規化処理が一度でも行われた場合には、一括圧縮が終了した時点でのAregの値Areg2は、
Areg2 = 0xfffe-((t - (Areg1 - 0x7fff)) mod 0x7fff)       …式(3)
で与えられる。ここで、Areg2 > 0x7fffであり、またmodは剰余を表す。
【０１３８】
このように、正規化が発生する場合には、最後の正規化処理を行なった後にまだ処理されていないセルの個数を、正規化が完了した直後のＡレジスタの値0xfffeから引く。ここで、t - (Areg1 - 0x7fff)は、1回目の正規化が終わった時点で、まだ処理しなければならないセルの数を表す。この時点(1回目の正規化が終わった時点)のＡレジスタの値は0xfffeである。ここから0x7fff個セルを処理するごとに正規化が発生するため、0x7fffで割った剰余が最後の正規化が終わった後に処理しなければならないセル数となる。この個数を0xfffeから引くことで、一括圧縮後のＡレジスタの値が得られる。すなわち、
Areg2 = 0xfffe - ((t - (Areg1 - 0x7fff)) mod 0x7fff) 
= 0xfffe - |(t - Areg1) mod 0x7fff|
である。なお、|x|はxの絶対値を表す。
【０１３９】
以上のように、Ｓ４２では、ＭＵＬＭＰＳ処理部９ｄが、上記の式(2)または(3)から新しいAreg６ａの値を求め、この値をレジスタ６のAreg６ａに代入する。
【０１４０】
Ｓ４３において、符号化装置１の最小検知部１０ａが、一括圧縮セルカウンタ６ｃに0を代入する。
【０１４１】
以上のＳ４０〜Ｓ４３にてＣＯＤＥＭＵＬＭＰＳ処理を終了し、図６に戻る。Ｓ１０のＣＯＤＥＭＵＬＭＰＳ処理の後は、Ｓ９のＣＯＤＥＭＰＳ処理に進む。ＣＯＤＥＭＰＳ処理については既に説明したのでここでは説明を省略する。
【０１４２】
次に、図１０のＳ４１にて呼び出されるＭＵＬＲＥＮＯＲＭ処理について、図１１に基づいて説明する。このＭＵＬＲＥＮＯＲＭ処理は、ＭＵＬＭＰＳ処理の一括圧縮において正規化をまとめて行なった際に、出力を得るためにCreg６ｂの値を変化させる処理である。
【０１４３】
Ｓ４５では、ＭＵＬＲＥＮＯＲＭ処理部９ｅが、Creg６ｂを１ビットシフト（Creg＝Creg≪１）する。また、ＭＵＬＲＥＮＯＲＭ処理部９ｅが、Creg６ｂに何ビット分の出力があるかのカウンタであるＣＴから、１を減ずる。
【０１４４】
Ｓ４５の次のＳ４６では、ＭＵＬＲＥＮＯＲＭ処理部９ｅは、ＣＴが０であるか否かを判別する。ＣＴが０である場合には、Ｓ４７に進み、ＭＵＬＲＥＮＯＲＭ処理部９ｅは、Creg６ｂから１バイト分のデータを符号化データとして符号化装置１の外部へと出力する。また、ＭＵＬＲＥＮＯＲＭ処理部９ｅは、出力とともに、ＣＴを８にする。
【０１４５】
Ｓ４６においてＣＴが０でない場合や、またはＳ４７の後は、ＭＵＬＲＥＮＯＲＭ処理を終了し、図１０に示すＳ４１に戻る。なお、図７に示すＣＯＤＥＭＰＳにおけるＳ２２のAreg<LSZ[ST]は、LSZが0.25(0x4000で表す)より小さいことから、この条件を満たすことはない。また、AregにLSZを代入する操作が行われることもない。また、コンテクストに対するLSZのインデックスSTも変化しないので、上記手順によって、CODEMPSの動作をシミュレーションすることができる。なお、STが13のときのLSZの値は0.25より小さいため、インターバルが取り得る最小値0.5であったとしても、LPSインターバル＞MPSインターバルとなることはない。例えば、インターバルが0.5、LSZが0.24であったとすると、インターバル−LSZ＞0.26でLSZより大きくなる。
【０１４６】
図６に戻ると、Ｓ５において対象セルがＬＰＳであった場合のＳ１１では、一括チェック部１０ｂが、レジスタ６の一括圧縮セルカウンタ６ｃにアクセスして、このカウンタ値ｔが０を超えているか否かを判別する。カウンタ値が０である場合には一括チェック部１０ｂから判別結果を得た選択部１０ｃがＬＰＳ処理部９ｂを選択する旨の選択信号を符号処理部９に出力してＳ１２に進む。カウンタ値が０を超えている場合には一括チェック部１０ｂから判別結果を得た選択部１０ｃがＭＵＬＭＰＳ処理部９ｃを選択する旨の選択信号を符号処理部９に出力してＳ１３に進む。
【０１４７】
Ｓ１２では、符号処理部９のＬＰＳ処理部９ｂが、ＣＯＤＥＬＰＳ処理を行う。このＣＯＤＥＬＰＳ処理は、図９に示すＳ３０〜Ｓ３６の処理に相当する。
【０１４８】
ＬＰＳ処理部９ｂは、算術圧縮において入力ビットがＬＰＳであった場合に、インターバルの範囲を変更し、また必要がある場合にはＲＥＮＯＲＭ処理部９ｃを呼び出してＣＯＤＥＲＥＮＯＲＭ処理を行わせる。入力ビットがＬＰＳであったため、ＬＰＳ処理部９ｂは、現在のインターバルからMPSインターバルを取り除くようにインターバルを変化させる。
【０１４９】
Ｓ３０では、ＬＰＳ処理部９ｂは、Areg６ａの値からLSZを引く。より詳細には、ＬＰＳ処理部９ｂは、レジスタ６にアクセスしてAreg６ａの値を取得する。ＬＰＳ処理部９ｂは、記録部５の確率推定表８にアクセスして、インデックスＳＴを用いて、LPSインターバルの近似値であるLSZを取得する。その後、ＬＰＳ処理部９ｂは、Areg６ａからLSZを引く。
【０１５０】
Ｓ３０の次のＳ３１では、ＬＰＳ処理部９ｂは、現在のAreg６ａの値がLSZ未満であるか否かを判別する。なお、Ｓ３０の処理によって、現在のAreg６ａの値は、MPSインターバルの近似値となっている。
【０１５１】
Ｓ３１において、現在のAreg６ａの値がLSZ未満であると判別された場合にはＳ３３に進む。この場合には、MPSインターバルの近似値がLSZ未満であるため、LPSインターバルとMPSインターバルとを交換し、その後に新たなインターバルとしてLPSインターバルを選択することになる。この処理は、結局MPSインターバルを新たなインターバルとするのと同じことになる。このため、特に処理は不要で、単にＳ３３に進めばよい。
【０１５２】
また、現在のAreg６ａの値がLSZ以上である場合にはＳ３１からＳ３２に進む。Ｓ３２では、ＬＰＳ処理部９ｂは、新たなインターバルとしてLPSインターバルを選択する処理を行う。ＬＰＳ処理部９ｂは、レジスタ６にアクセスしてCreg６ａの値を取得する。ＬＰＳ処理部９ｂは、現在のCreg６ａの値に、現在のAreg６ａの値を加えて新たなCreg６ａの値とする。また、ＬＰＳ処理部９ｂは、Areg６ａの値にLSZを代入する。これによって、新たなインターバルとしてLPSインターバルが選択される。Ｓ３２からはＳ３３に進む。
【０１５３】
Ｓ３３では、ＬＰＳ処理部９ｂは、インデックスＳＴに対応する確率推定表８のＳＷＩＴＣＨの項目が１であるか否かを判別する。ＳＷＩＴＣＨの項目が１である場合には、Ｓ３４に進み、ＬＰＳ処理部９ｂはコンテクストに対するＭＰＳの値の入れ替えをして、Ｓ３５に進む。ＳＷＩＴＣＨの項目が１でない場合にはＳ３５に進む。
【０１５４】
Ｓ３５では、ＬＰＳ処理部９ｂは、確率推定表８にアクセスし、劣勢確率シンボルを圧縮したときの次のＳＴの値を意味するＮＬＰＳを得る。
【０１５５】
Ｓ３５の次のＳ３６では、ＬＰＳ処理部９ｂがＲＥＮＯＲＭ処理部９ｃを呼び出して、ＣＯＤＥＲＥＮＯＲＭを実行させる。
【０１５６】
Ｓ３６までの処理によって、ＣＯＤＥＬＰＳ処理が終了すると、図６のＳ１４に進む。
【０１５７】
図６に戻ると、Ｓ１１において一括圧縮セルカウンタ６ｃのカウンタ値ｔが０を超えていた場合のＳ１３では、符号処理部９のＭＵＬＭＰＳ処理部９ｃが、ＣＯＤＥＭＵＬＭＰＳ処理を行う。このＳ１３にて行う処理は、上述のＳ１０にて行う処理と同様であるので、ここでは説明を省略する。Ｓ１３のＣＯＤＥＭＵＬＭＰＳ処理の後は、Ｓ１２のＣＯＤＥＬＰＳ処理に進む。ＣＯＤＥＬＰＳ処理については既に説明したのでここでは説明を省略する。
【０１５８】
Ｓ１４は、Ｓ２にて選択した対象セルについての処理の終わりを示すものである。ここでは、符号処理部９がコンテクスト生成部２にセルインクリメントのための信号を出力する。コンテクスト生成部２では、対象となるセルを更新しようとしたときに、セルがストライプの終点にきているかどうか、セルを更新できるかどうかを判別する。更新できない場合には次のＳ１５に進み、更新できる場合にはＳ２に戻る。
【０１５９】
Ｓ１５・Ｓ１６は、本実施形態のようにストライプごとに処理を行う場合に、圧縮していない未処理のセルの有無を判別するための手順である。このようにＳ１５にて一括圧縮の要否をチェックするので、一括圧縮セルカウンタが０の場合のＳ９，Ｓ１２においては、一括圧縮をする必要がない。
【０１６０】
すなわち、Ｓ１４において、コンテクスト生成部２が対象となるセルを更新しようとしたときに、セルがストライプの終点にきており、更新できないと判別した場合には、以下のようにして未処理のセルの有無を判別する。
【０１６１】
Ｓ１５では、コンテクスト生成部２から取得部３・最小検知部１０ａを介して指示を受けた一括チェック部１０ｂが、レジスタ６の一括圧縮セルカウンタ６ｃにアクセスして、このカウンタ値ｔが０を超えているか否かを判別する。カウンタ値ｔが０である場合には一括チェック部１０ｂの判別結果を得た選択部１０ｃが、なにもしない旨の選択信号を符号処理部９に出力してＳ１７に進む。カウンタ値ｔが０を超えている場合には一括チェック部１０ｂの判別結果を得た選択部１０ｃが、ＭＵＬＭＰＳ処理部９ｃを選択する旨の選択信号を符号処理部９に出力してＳ１６に進む。
【０１６２】
Ｓ１６では、符号処理部９のＭＰＳ処理部９ａが、ＣＯＤＥＭＰＳ処理を行う。このＣＯＤＥＭＰＳ処理は、Ｓ１０およびＳ１３で行うものと同様であるので、説明は省略する。
【０１６３】
Ｓ１７は、レジスタ６のCreg６ｂとして保存されている、圧縮結果としてのインターバルの低数を、符号化データとして符号化装置１の外部へと出力する、フラッシュ処理を行う。
【０１６４】
Ｓ１８は、Ｓ１にて選択したストライプについての処理の終わりを示すものである。Ｓ１４においてコンテクスト生成部２が対象となるセルを更新しようとしたときに、セルがストライプの終点にきており、更新できないと判別した場合には、このＳ１８からＳ１に戻って、コンテクスト生成部２が新たなストライプとセルとを選択する。全てのストライプの圧縮が完了すれば画像全体の圧縮が完了したことになる。
【０１６５】
以上で説明したように、本実施形態の符号化装置１によれば、正規化が起こらないことを検知する必要が無いため、その分の演算を省略できる。また、一括圧縮可能なセル数に制限が無い。
【０１６６】
すなわち、符号化装置１において、ＬＰＳの確率推定値が最小であるST=13の状態で優勢確率シンボルを圧縮し続けていくと、やがて正規化が発生するが、正規化が発生しても確率推定が変化しない。すなわち、あるコンテクストに対するLPSインターバルの近似値(LSZ)が一旦最小となれば、そのコンテクストに対して優勢確率シンボルが入力され続けている限り、正規化処理が発生してもLSZはそれ以上変化しない。また、どのコンテクストに対してもLSZの最小値は同じである。したがって、これを利用して、正規化の発生に関わらず一括圧縮できる。
【０１６７】
ここで、上述の符号化装置１において、すでに劣勢確率シンボルの確率推定が最小になっていれば、正規化の発生にもかかわらず、それ以上劣勢確率シンボルの確率推定は減少しない点について、説明を補足する。
【０１６８】
JBIG圧縮における確率推定の値（ＬＳＺ）は、確率推定表８から、確率推定のインデックスＳＴを用いて参照される。すなわち、ＳＴがある値であったときの確率推定は、確率推定表８のＳＴに対応する行のLSZから求めることができる。例えば、ＳＴ＝０のときは確率推定値LSZは0x5a1dとなり、ＳＴ＝１３のときにはLSZは0x0001となる。また、確率推定表８から、優勢確率シンボルを符号化して、かつ正規化が発生した場合の次のＳＴの値であるNMPSや、劣勢確率シンボルを符号化した場合の次のＳＴの値であるNLPSを求めることができる。
【０１６９】
ここで、劣勢確率シンボルを符号化した場合には、毎回正規化が発生してＳＴが変化する。一方、優勢確率シンボルを符号化した場合には、Ａレジスタの値から確率推定を減算して、Ａレジスタの値が0x8000より小さくなった場合にのみ正規化が発生してＳＴが変化する。
【０１７０】
ここで、表中の確率推定値LSZを見ると、確率推定はLSZ=0x0001となるＳＴ＝１３のときが最小値となる。また、ＳＴ＝１３のところのNMPSを見ると13となっており、ＳＴ＝１３のときに優勢確率シンボルを符号化して、正規化が発生してもＳＴは変化しない。このことから、確率推定のインデックスＳＴが変化しないと、確率推定も変化しないことになる。
【０１７１】
本来、算術符号化の考え方からすると、優勢確率シンボルが出現し続けている場合には、劣性確率シンボルの出願確率はどんどん小さくすることになる。しかしながら、実際の符号化に応用する場合には、レジスタの幅などデジタルで表現できる精度に限りがあるため、JBIGでは上記のようにしている。すなわち、上記のように、劣勢確率シンボルの確率推定が最小になっていれば、それ以上劣勢確率シンボルの確率推定は減少しない。このように劣勢シンボル確率推定の値が最小値を持ち、一旦最小値になれば優勢シンボルが与えられる限り劣勢シンボル確率推定の値が変化しないという性質を満たすものであれば、JBIGに限らず、本発明を適用できる。
【０１７２】
言い換えると、劣勢シンボルの確率推定が下限値を持ち、劣勢シンボルの確率推定が下限値に達した状態でMPS入力を受けても劣勢シンボルの確率推定が変化しない算術圧縮であれば、本発明を適用できる。また、上述の実施の形態で挙げている式(正規化の発生回数や正規化後のパラメータ計算の式)を使って正規化の発生をシミュレーションするためには、インターバル全体の取り得る最小値がLSZの最小値の２倍より大きいことが必要である。もしそうでなければ、一回の正規化で２回以上の２倍化処理が発生する可能性があるため、実施例に挙げた式は使えない。JBIGのQM-coderはこの基準を満たし、またLSZの最小値がインターバルの最小値の半分以上という算術圧縮はまず考えられないため、実際には、ほとんどの算術圧縮に応用可能と考えられる。
【０１７３】
また、劣勢確率シンボルの符号化の際にも同様に、LPSの確率推定が最大のとき劣勢確率シンボルを符号化してもＳＴは変化しないという性質が成り立つように思われるが、実際にはそれは成り立たない。例えば、ＳＴ＝１１２のときに劣勢確率シンボルが符号化された場合には、次のＳＴ(NLPS)は１１２となるが、このときはＳＷＩＴＣＨが１となっている。これは、ＳＴ＝１１２というのは予測が外れつづけた場合なので、次に予測が外れると優勢確率シンボルと劣勢確率シンボルを入れ替えるためである。このため劣勢確率シンボルと優勢確率シンボルの入れ替えが起こる。したがって、この場合、次回からＳＴが変化するようになっている。
【０１７４】
なお、符号化装置１においては、ST=13以外では、優勢確率シンボルの入力が続いた場合でも、正規化が発生したときにSTが変化してしまう。このため、一括圧縮の際にＡレジスタから引く値が変化するので、正規化の発生する場所で一括圧縮を中断せざるを得ない。この場合でも、正規化が発生するまでの入力列に対しては一括圧縮が可能であるが、どこで正規化が発生するかを検知するための演算が必要となるため、計算量が増大してしまう。
【０１７５】
また、上述の符号化装置１によれば、複数の高速化可能なコンテクストが混在する場合でも、ＬＰＳの確率推定値が最小の下限値であるという条件を満たしていればコンテクストのパターンについて制限が無く、あらゆるコンテクストのパターンについて高速化の対象とし得る。
【０１７６】
すなわち、符号化装置１によれば、ＬＰＳの確率推定値が最小のＳＴ＝１３となっているという条件を満たしていれば、近傍形の中のパターンは何であっても高速化を行うことができる。例えば、２ラインテンプレートを使用している場合に、コンテクスト中の全てのセルの値が０か、または１が２つ以下しか含まれていないあらゆるコンテクストについてＳＴ＝１３となっている場合に、
00001000
00001000
という入力列が与えられたとする。そして、上のラインについては圧縮完了しており、下のラインを今から圧縮するものとする。さらに、下のラインは、全て近傍形に対する優勢確率シンボルであるとする。この場合、符号化装置１を用いて圧縮すれば、圧縮を中断することなく、ライン全体を一括して圧縮することができる。このように、複数のコンテクストが混在する状況でも高速化が行なえる。
【０１７７】
一方、従来法では、最初の４つの０を一括圧縮したところで、異なる近傍形が出現するため、一旦一括圧縮を中断しなければならない。すなわち、従来法は、例えば０がずっと続くような、１通りの近傍形に対して正規化が発生しない範囲で高速化を行なうものであり、コンテクストのパターンについて制限があった。
【０１７８】
なお、上述の実施の形態においては、確率推定テーブル７にコンテクストごとのMPS(1ビット)とLSZのインデックスST(7ビット)が保存され、LPSインターバルが最小値となっているか否かを最小検知部１０ａにおいてインデックスＳＴを用いて判別する構成について説明したが、本発明はこれに限るものではない。
【０１７９】
例えば、確率推定テーブル７に、コンテクストごとのMPS(1ビット)とLSZのインデックスST(7ビット)に加えて、LPSインターバルが最小値となっているかどうかを示す1ビット（最小LPSインターバル判定ビット）を保存する構成であってもよい。
【０１８０】
あるコンテクストと優勢確率シンボルに対してLPSインターバルが最小であることが認識された場合には、確率推定テーブルのそのコンテクストに対する最小LPSインターバル判定ビットを1とする。また、あるコンテクストに対して劣勢確率シンボルが与えられた場合には最小LPSインターバル判定ビットを0とする。
【０１８１】
なお、通常は圧縮開始の時点でLPSインターバルが最小となっていることはないので、各コンテクストに対して最小LPSインターバル判定ビットに初期値0を与えるが、圧縮開始時点でLPSインターバルが最小となることがあるような算術圧縮方式ではLPSインターバルが最小となっているコンテクストに対してのみ初期値0,1のどちらを与えても構わない。
【０１８２】
LSZの最小値に対応するLSZのインデックスを確率推定テーブルに書き込むことが、最小LPSインターバル判定ビットに1を入れる(高速化可能であると記録する)ことと同じ効果を持つ。LSZの最小値に対応しないLSZのインデックスを確率推定テーブルに書き込むことが、最小LPSインターバル判定ビットに0を入れる(高速化できないと記録する)ことと同じ効果を持つと考えることができる。
【０１８３】
ただし、確率推定テーブルに最小LPSインターバル判定ビットを追加すると、各コンテクストに対して9ビット(LSZのインデックス7ビット、MPSが1ビット、LPSインターバル判定ビットが1ビット)の情報を保持しなければならなくなる。このため、記録部５に必要となる記録容量を増大させてしまう。
【０１８４】
また、各コンテクストに対する情報を１バイト（８ビット）のままとするためには、例えばLPSインターバル判定ビットを残したまま、LSZのインデックスを6ビットで扱うことになる。これは、LSZのインデックスとして用いることのできる範囲が半分となってしまい、不都合である。上記実施の形態のように、LPSインターバル判定ビットを利用しない構成であれば、この不都合を回避できる。この場合であっても、LSZのインデックスの値を参照すれば、LSZが最小になっているかどうかは分かるので、問題はない。
【０１８５】
また、上述の実施の形態においては、簡単のために最低解像度レイヤのみを持つJBIG圧縮について説明したが、これに限るものではなく、複数の解像度レイヤを持つプログレッシブなJBIG圧縮に対しても応用できる。また、説明を簡単にするため、コンテクストの形状を変化させるAT移動などJBIGの仕様に含まれる付加的な機能に関しても説明を省略したが、本発明における圧縮高速化方式はAT移動を伴うJBIG圧縮に対しても応用可能である。
【０１８６】
ここで、AT(Adaptive Template)移動とは、JBIG圧縮の仕様に含まれている特殊な操作である。圧縮において必須のものではなく、AT移動を行なわないようにすることもできる。通常、近傍形は一定で圧縮中に変化することはないが、AT移動を使用する場合には近傍形そのものが変化する。AT移動するかどうか、いつAT移動するかは圧縮する側で決めることができるため、本発明はAT移動の有無に関わらず適用することができる。ただし、一括圧縮中にAT移動させることはできない。
【０１８７】
なお、従来法では、正規化が起こらないことを検知して圧縮の高速化を行うために、一括圧縮可能なセル数に制限がある。また、単一のコンテクストに対してしか圧縮の高速化を行うことができなかった。また、例えば特許文献２に記載の構成では、連続するMPS符号を一括圧縮する技術が公開されている。この方法では一括圧縮の際に正規化処理が発生しないことを検出した上で、一括圧縮を行う。なぜなら、一括圧縮中に正規化が発生すると、ＬＰＳの確率推定値が変化してしまうためである。ＬＰＳの確率推定値が変化した場合には、ＭＰＳを符号化する際にインターバルから減ずる値が変化することになり、一括圧縮を継続することができない。ここで、通常は、正規化の発生によってLSZのインデックスSTの値が変化する。STの値が変化する場合にはLSZも変化するため、一括して圧縮することができない。一方、本発明のように、ST=13のときには、変化しない。
【０１８８】
また、上述した本発明の構成を使用して圧縮を行なった場合でも、圧縮結果は通常の方法で圧縮を行なった場合と同じである。このため、圧縮復号化装置に関しては特別な機構は必要ない。例えば、符号化装置をプリンタドライバに用いる構成であっても、プリンタ側の復号化装置には特別な機構は不要である。
【０１８９】
上述の具体的な実施形態または実施例は、あくまでも、本発明の技術内容を明らかにするものであって、本発明はそのような具体例にのみ限定して狭義に解釈されるべきものではなく、特許請求の範囲に示した範囲で種々の変更が可能であり、変更した形態や、実施の形態にそれぞれ開示された技術的手段を適宜組み合わせて得られる実施の形態についても、本発明の技術的範囲に含まれる。
【産業上の利用可能性】
【０１９０】
本発明に係る符号化装置は、JBIG圧縮として実装され、ファクシミリ装置（FAX）やプリンタなどで使用される。パーソナルコンピュータのプリンタドライバが上記符号化装置を有する構成であれば、印刷ドキュメントを画像に変換したものを上記符号化装置によってJBIG圧縮してプリンタ本体に送信する際に、圧縮を高速化できる。
【図面の簡単な説明】
【０１９１】
【図１】本発明に係る符号化装置の一実施の形態を示すブロック図である。
【図２】上記符号化装置にて行う算術圧縮を説明するための概念図である。
【図３】上記符号化装置にて符号化を行う対象セルと、そのセルについてのコンテクストの一例を示す平面図である。
【図４】上記符号化装置にて用いる確率推定テーブルの一例を示す図である。
【図５】（ａ）は上記符号化装置にて用いる確率推定表の一例の一部を示す図であり、（ｂ）は上記確率推定表の他の一部を示す図である。
【図６】上記符号化装置にて行う符号化処理の概略を示すフローチャートである。
【図７】上記符号化装置にて行う符号化処理の一部を示すフローチャートである。
【図８】上記符号化装置にて行う符号化処理の他の一部を示すフローチャートである。
【図９】上記符号化装置にて行う符号化処理のさらに他の一部を示すフローチャートである。
【図１０】上記符号化装置にて行う符号化処理のさらに他の一部を示すフローチャートである。
【図１１】上記符号化装置にて行う符号化処理のさらに他の一部を示すフローチャートである。
【図１２】従来の符号化装置の一例を示すブロック図である。
【図１３】従来の符号化装置にて行う符号化処理の概略を示すフローチャートである。
【符号の説明】
【０１９２】
１          符号化装置
２          コンテクスト生成部
３          取得部
４          算術符号部
５          記録部
６          レジスタ
６ａ        Areg（Ａレジスタ）
６ｂ        Creg（Ｃレジスタ）
６ｃ        一括圧縮セルカウンタ（セルカウンタ）
７          確率推定テーブル
８          確率推定表
９          符号処理部
９ａ        ＭＰＳ処理部
９ｂ        ＬＰＳ処理部
９ｃ        ＲＥＮＯＲＭ処理部
９ｄ        ＭＵＬＭＰＳ処理部（一括圧縮部）
９ｅ        ＭＵＬＲＥＮＯＲＭ処理部（一括圧縮部）
１０        前処理部
１０ａ      最小検知部
１０ｂ      一括チェック部
１０ｃ      選択部
ＣＴ        出力ビットカウンタ
ＳＴ        インデックス
ｔ          セルカウンタ（一括圧縮セルカウンタ）
ＬＳＺ      LPSインターバルの推定値（劣勢確率シンボルの出現確率の推定値）
【図１】
2005217517.tif 000003
【図２】
2005217517.tif 000004
【図３】
2005217517.tif 000005
【図４】
2005217517.tif 000006
【図５】
2005217517.tif 000007
【図６】
2005217517.tif 000008
【図７】
2005217517.tif 000009
【図８】
2005217517.tif 000010
【図９】
2005217517.tif 000011
【図１０】
2005217517.tif 000012
【図１１】
2005217517.tif 000013
【図１２】
2005217517.tif 000014
【図１３】
2005217517.tif 000015