(57)【要約】【課題】分割してデータを圧縮する際、高速で、かつ、処理に必要な記憶容量を増やすことなく、符号化圧縮処理できる圧縮処理装置を実現する。【解決手段】圧縮処理装置１では、格納処理部２は、１つの画像データを列方向に複数に分割した分割画像データを、これら分割画像データの圧縮処理に応じて分割処理用の格納領域に順次格納する際に、今回格納する分割画像データについては、上記分割処理用の格納領域に前回格納された分割画像データの後端行から先端行方向へ上記参照セルの行数から１引いた数分除いた次の行を始端として、上記前回格納された分割画像データの先端行方向へ順次上書きする。【選択図】図１
2009159105.tif 000002
【特許請求の範囲】
【請求項１】
セルを単位とし行方向および列方向に２次元に配列されるデータに対して、セルの行方向に沿って符号化対象セルを順次選択し、選択した符号化対象セルを、テンプレートにより指定される複数の参照セルに基づいて符号化することで、上記データを圧縮する圧縮処理装置において、
１つの圧縮対象データを列方向に複数に分割した分割データを、これら分割データの圧縮処理に応じて分割処理用の格納領域に順次格納する際に、今回格納する分割データについては、上記分割処理用の格納領域に前回格納された分割データの後端行から先端行方向へ上記参照セルの行数から１引いた数分除いた次の行を始端として、上記前回格納された分割データの先端行方向へ順次上書きする格納処理手段を備えたことを特徴とする圧縮処理装置。
【請求項２】
上記格納処理手段は、上記圧縮対象データを列方向に分割した最初の分割データを格納する際には、少なくとも、上記参照セルの行数から１引いた行数に上記最初の分割データの１行に含まれるセル数を乗算したセルを格納できる領域を除いた箇所から格納を始めることを特徴とする請求項１に記載の圧縮処理装置。
【請求項３】
上記格納処理手段は、上記圧縮対象データを列方向に分割した最初の分割データを格納する前に、少なくとも、上記参照セルの行数から１引いた行数に上記最初の分割データの１行に含まれるセル数を乗算したセルを格納できる領域を、０で初期化することを特徴とする請求項１または２に記載の圧縮処理装置。
【請求項４】
上記圧縮対象データは画像データであり、上記セルは、当該画像データの一以上の画素に対応することを特徴とする請求項１から３のいずれか１項に記載の圧縮処理装置。
【請求項５】
上記行方向は、画像読取装置の走査方向に対応していることを特徴とする請求項４に記載の圧縮処理装置。
【請求項６】
上記前回格納された分割データの圧縮時と上記今回格納された分割データの圧縮時とでは、上記テンプレートの形状が変更されることを特徴とする請求項１から５のいずれか１項に記載の圧縮処理装置。
【請求項７】
上記テンプレートが２行からなる２ラインテンプレートであり、上記前回格納された分割データの圧縮時と上記今回格納された分割データとにそれぞれ対応させて、上記２ラインテンプレートと当該２ラインテンプレートを符号化対象セルの存在する行を中心線として線対称移動させたテンプレートとのいずれかが用いられることを特徴とする請求項６に記載の圧縮処理装置。
【請求項８】
セルを単位とし行方向および列方向に２次元に配列されるデータに対して、セルの行方向に沿って符号化対象セルを順次選択し、選択した符号化対象セルを、テンプレートにより指定される複数の参照セルに基づいて符号化することで、上記データを圧縮する圧縮処理方法において、
１つの圧縮対象データを列方向に複数に分割した分割データを、これら分割データの圧縮処理に応じて分割処理用の格納領域に順次格納する際に、今回格納する分割データについては、上記分割処理用の格納領域に前回格納された分割データの後端行から先端行方向へ上記参照セルの行数から１引いた数分除いた次の行を始端として、上記前回格納された分割データの先端行方向へ順次上書きする格納処理ステップを含むことを特徴とする圧縮処理方法。
【請求項９】
請求項１から７の何れか１項に記載の圧縮処理装置を動作させるための制御プログラムであって、コンピュータを上記圧縮処理装置における上記各手段として機能させるための圧縮処理制御プログラム。
【請求項１０】
請求項９に記載の圧縮処理制御プログラムが記録されたコンピュータ読み取り可能な記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、圧縮対象データを分割した分割データを圧縮処理する圧縮処理装置、圧縮処理方法、圧縮処理プログラム、およびコンピュータ読み取り可能な記録媒体に関するものである。
【背景技術】
【０００２】
画像データを高圧縮率で圧縮する方法として、算術圧縮が知られている。算術圧縮においては、圧縮対象セル（符号化シンボル、符号化対象セル）の近傍セルを参照して、その近傍セルから圧縮対象セルを予測したときの予測値と実際の値とのずれを保存することによって圧縮を行う。このように圧縮の際に圧縮対象セルに対する近傍セルを参照して圧縮を行う数多くのアルゴリズムが知られている。
【０００３】
このようなアルゴリズムでは、データを２次元的に表現して、２ライン以上の形状を持つ近傍形（テンプレート）が使用されることが多い。元々２次元的な画像データであれば、その画像データに対して２ライン以上の形状を持つ近傍形を適用できる。また、画像データ以外のデータであっても、そのデータを一定のビット数ごとに折り返すなどして仮想的に２次元データとして捉えれば２ライン以上のテンプレートを使用して近傍形を決定することができる。
【０００４】
このようなアルゴリズムの中で、２値画像をマルコフ情報源でモデル化し、符号化シンボルをその周辺画素（近傍セル）の状態によって予測し、予測結果を算術符号化する方式としてJBIG(ITU-T T.82)のQM-Coderが知られている（非特許文献１、２参照）。
【０００５】
まず、QM-Coderについて説明する前に、算術圧縮の概念について説明する。算術圧縮は、入力信号列を０以上１未満の実数ｘに変換する。なお、圧縮結果は非常に長い一つの小数となる。この変換は次のように行われる。現時点までの入力に対して実数ｘの存在しうる範囲をインターバルという。まだ１ビットも入力が行なわれていない時点では、明らかにインターバルは０以上１未満の領域となる。現時点までの入力列から次の入力ビットを予測し、出現すると予想された入力ビットは優勢確率シンボル（MPS）となり、予想されなかった入力ビットは劣勢確率シンボル（LPS）となる。インターバルを優勢確率シンボルの出現確率と劣勢確率シンボルの出現確率との比によって分割する。インターバルを分割する際には、０により近い方を優勢確率シンボルの出現確率とし、これをMPSインターバル、０から遠い方を劣勢確率シンボルの出現確率とし、LPSインターバルと呼ぶ。
【０００６】
１ビットの入力が行なわれると、その時点までの入力から予測していた値（優勢確率シンボル）との比較が行なわれ、一致する場合には、インターバルからLPSインターバルが取り除かれる。一致しない場合には、インターバルからMPSインターバルが取り除かれる。このとき、インターバルは大きさと低数（その時点でのインターバルの最小値）とで記憶されているため、インターバルからLPSを取り除く操作は、インターバル全体の大きさからLPSインターバルの大きさを引くことで実現でき、インターバルからMPSを取り除く操作は、インターバル全体の大きさからMPSインターバルの大きさを引く操作と低数にMPSインターバルの大きさを加える操作とによって実現できる。
【０００７】
全ての入力列に対する処理が完了したときのインターバルの低数が、実数ｘ（圧縮結果）となる。
【０００８】
ここで、入力ビットが予想される入力ビットと一致する場合には低数に変化が生じないことから、出力（圧縮結果）にも変化が生じず、新たなビットを出力する必要がない。このことを利用して圧縮を行う。
【０００９】
例えば、０００１のような入力が与えられ、そのときの優勢確率シンボル（MPS）が０１０１のようであった場合には、圧縮結果ｘは図１０のようにして求められる。２ビット目の入力は劣勢確率シンボルであるから、LPSインターバルが選択され、その他は優勢確率シンボルであるからMPSのインターバルが選択される。もし、全ての入力が優勢確率シンボルであれば圧縮結果ｘは０となる。
【００１０】
QM-coderにおいては、上記の圧縮処理を計算機上などで実施するために、固定精度の整数演算で近似している。
【００１１】
ここで、QM-Coderにおいて、レジスタＡはインターバルの大きさを保持している。しかし、上述の算術圧縮処理を実施していくとインターバルの大きさはどんどん小さくなり、やがて固定精度では表現できなくなる。そこで、レジスタＡには大きさが０．５以上、１以下になるように正規化されたインターバルを入れる。正規化とは、インターバルの大きさが０．５以上となるまで繰り返しインターバルの大きさを２倍にする処理である。
【００１２】
レジスタＣには低数が入る。レジスタＣがオーバーフローしないようにレジスタＣの上位バイトは適時取り出され、圧縮結果として出力される（この際に発生するキャリーオーバーを解決する方法については、ITU-T T.82に記載されているが、本発明の内容を理解する上で必須ではないため、ここでは触れない）。
【００１３】
レジスタＡが正規化処理によって２倍にされる度に、レジスタＣも２倍にされるため、レジスタを２倍にしていることによる出力への影響は相殺される。
【００１４】
LPSインターバルを計算するには、本来は、（インターバルの大きさ）×（LPS出現確率）という演算が必要となるが、QM-Coderでは統計的に求められた値（LSZ）で近似する。この方法ではインターバルの大きさによってLPSインターバルのインターバル中に占める割合が変化してしまうが、インターバルは大きさが０．５以上１以下に正規化されているため、誤差はそれほど大きくはならない。
【００１５】
入力としてMPSが与えられた際にはインターバルからLSZを引き、LPSが与えられたときにはインターバルをLSZとする。この操作の結果、インターバルが０．５以下となったときには正規化を行う。正規化が行われたときにはLSZの値を更新する。この更新には統計的に求められた確率推定表が用いられる。現在のLSZ（のインデックス）と、MPSが与えられたかLPSが与えられたかなどによって、次のLSZが確率推定表から求められる。このLSZの値は固定精度の整数として表現されるために、上限だけでなく下限もある。
【００１６】
ここで、時々MPSインターバルよりもLPSインターバルの方が大きくなってしまう場合がある。この場合はMPSインターバルとLPSインターバルの入れ替えを行う。
【００１７】
QM-Coderにおいて、優勢確率シンボルは、符号化画素の周辺の幾つかの画素を用いて決定される。周辺画素の配列（コンテクスト、テンプレート）に対する優勢確率シンボルが確率推定テーブルに記録されており、この確率推定テーブルを参照することによって優勢確率シンボルを得ることができる。また、この確率推定テーブルにはLSZのインデックスも入っているため、確率推定表からLSZを求めるのにも使用される。なお、確率推定テーブルにはコンテクストごとのMPS（１ビット）とLSZのインデックスST（７ビット）が保存されており、各コンテクストに対して１バイトの大きさを持っている。コンテクストが１０セル分の大きさを持つのであれば２の１０乗個のコンテクストそれぞれに対して１バイトの大きさとなる。
【００１８】
ここで、従来のJBIGのQM-Coderを用いた圧縮処理装置の圧縮処理のフローは図１１のようになる。まず、圧縮処理装置に入力された入力画像は、メモリに格納される（Ｓ１４９）。そして、入力画像は１以上のストライプに分けられる。このストライプとは、圧縮処理を行う単位であり、画像中の１ライン以上の横ライン（行）からなる。つまり、ストライプの横幅は画像の横幅と等しく、ストライプの縦幅は画像の縦幅と同じか、それ以下（ただし１画素の縦幅以上）となる。図１１のＳ１５０からＳ１６４までのストライプのループ(LOOP_A)によって、全てのストライプに対して処理が完了すると、画像全体の圧縮が完了したことになる。
【００１９】
圧縮処理装置では、図１１のＳ１５１からＳ１６２までのセル（画素）のループ(LOOP_B)において、ストライプの左から順にセル（画素）とコンテクストとを読み取り圧縮処理を行う。ここで、コンテクストとは、所定の形状のテンプレートにより指定される、圧縮対象セル（符号化対象セル）と所定の相対位置にある近傍セル（周辺画素）のことを指す。横方向に１ライン分のセルとコンテクストとを読み取り圧縮処理が完了すると、その下のラインの読み取りへと進む。つまり、圧縮処理は、画像データの左上から右下に向かって進む。
【００２０】
１つのストライプに含まれる全てのセルの処理が完了すると、その１つのストライプの処理が完了する。図５において、斜線が引かれた四角が圧縮対象のセルであり、その周辺の１０個の四角がコンテクストを成す各セルを表している。JBIG圧縮では、最低解像度レイヤのコンテクストとして図５に示す２ラインテンプレートの他に３ラインテンプレートが用意されている。ここでは２ラインテンプレートを用いて説明する。
【００２１】
コンテクストのセル数は１０個であり、各セルは０または１の値を持つので、その組み合わせの数は１０２４通りである。圧縮処理装置２１は圧縮対象セルとコンテクストを読み取る（Ｓ１５２）と、図８に示す確率推定テーブルを参照し（Ｓ１５３）、圧縮対象セルの値（シンボル）がコンテクストに対する優勢確率シンボルか劣勢確率シンボルかを判断する（Ｓ１５４）。優勢確率シンボルであると、Ｓ１５５からＳ１５８のCODE MPS処理を実行する。劣勢確率シンボルであると、Ｓ１５９からＳ１６１のCODE LPSを実行する。
【００２２】
以上の手順をストライプの全てのセルに対して行うことで、ストライプの圧縮が行なわれる。LOOP_Bが一巡したら、次のストライプの圧縮に進む前に、ここまでの圧縮結果のうちまだ出力されていない部分を出力する（フラッシュ処理：Ｓ１６３）。全てのストライプの圧縮が完了すれば画像全体の圧縮が完了する。
【特許文献１】特開平１０−１３６４１号公報（平成１０年１月１０日公開）
【非特許文献１】ITU-T(International Telecommunication Union Telecommunication standardization sector) WHITE BOOK ディジタル静止画像圧縮符号化関連勧告書(財団法人 新日本ITU協会) 勧告T.82
【非特許文献２】WTSC-93 (WORLD TELECOMMUNICATION STANDARDIZATION CONFERENCE), Helsinki, 1-12 MARCH 1993
【発明の開示】
【発明が解決しようとする課題】
【００２３】
ここで、算術圧縮を行う場合に、圧縮処理装置のメモリ領域の容量が十分でない場合など、元の画像データを複数の分割画像データに分割して入力することがある。このとき、圧縮対象セルが存在するラインの上のラインを圧縮時に近傍セルとして参照するため、ある分割画像データの圧縮が完了した後、次の分割画像データを同じメモリ領域に上書きする前に、前回の分割画像データの最終ラインを含むライン（２ラインテンプレートであると最終ラインが必要であり、３ラインプレートでは最終ラインとその上のラインが必要である）をどこかにコピーして保存しておく必要がある。また、次の分割画像データを圧縮する際に、１ライン目（最上部）は上記コピーして保存しておいたラインを参照しながら圧縮を行うための専用のコードを用いて圧縮を行わなければならない。つまり、最上部のラインを圧縮する際に近傍セルを参照するのに特殊な処理が必要となる。以上のようなことから、従来の圧縮処理装置では、処理速度が低下したり、処理に必要な記憶容量が増加したりする。
【００２４】
なお、特許文献１には、２つの画像データを圧縮してメモリに書き込む際に、一方のデータをメモリの最上位アドレスから順に格納し、他方のデータを最下位アドレスから順に格納する点が示されている。しかし、メモリに格納される画像データそれぞれは全く別の画像データであり、１つの画像の部分画像データではない。また、近傍セルを参照して圧縮を行うものでもない。よって分割データの圧縮時に、処理速度が低下したり、処理に必要な記憶容量が増加したりする問題を、解決できない。
【００２５】
本発明は、上記の問題点に鑑みてなされたものであり、その目的は、分割してデータを圧縮する際、高速で、かつ、処理に必要な記憶容量を増やすことなく、符号化圧縮処理できる圧縮処理装置、圧縮処理装置の制御方法、圧縮処理制御プログラム、およびコンピュータ読み取り可能な記録媒体を実現することにある。
【課題を解決するための手段】
【００２６】
本発明に係る圧縮処理装置は、上記課題を解決するために、セルを単位とし行方向および列方向に２次元に配列されるデータに対して、セルの行方向に沿って符号化対象セルを順次選択し、選択した符号化対象セルを、テンプレートにより指定される複数の参照セルに基づいて符号化することで、上記データを圧縮する圧縮処理装置において、１つの圧縮対象データを列方向に複数に分割した分割データを、これら分割データの圧縮処理に応じて分割処理用の格納領域に順次格納する際に、今回格納する分割データについては、上記分割処理用の格納領域に前回格納された分割データの後端行から先端行方向へ上記参照セルの行数から１引いた数分除いた次の行を始端として、上記前回格納された分割データの先端行方向へ順次上書きする格納処理手段を備えたことを特徴としている。
【００２７】
上記構成によると、格納処理手段は、１つの圧縮対象データを列方向に複数に分割した分割データを、これら分割データの圧縮処理に応じて分割処理用の格納領域に順次格納する際に、今回格納する分割データについては、上記分割処理用の格納領域に前回格納された分割データの後端行から先端行方向へ上記参照セルの行数から１引いた数分除いた次の行を始端として、上記前回格納された分割データの先端行方向へ順次上書きする。よって、本発明の係る圧縮装置は、今回の分割データ格納時、上記分割処理用の格納領域において上書きされていない領域では、前回の格納された分割データの最終行（ライン）を含む行（ライン）が格納されたままになっている。そのため、前回格納された分割データの最終行を含む行に含まれるセルも参照セルの読み取り対象にすることができる。なお、分割データの後端行とは、分割データにおいて分割された最後の行（ライン）、つまり、１つ後の分割データの１行前の行である。また、先端行とは、分割データにおいて分割された最初の行、つまり、１つ前の分割データの１行後の行、あるいは前に分割データがなければ、自身の始まりの行、である。
【００２８】
ここで、圧縮処理は分割データの分割の順に行なわれるため、今回上書きされていない前回格納された分割データの最終行を含む行に含まれるセルは、今回格納された分割データのセルの符号化時に、参照セルとして用いることができる。よって、前回格納された分割データの最終行を含む行を別途保存することなく、今回格納された分割データの圧縮処理を適切に行える。つまり、今回格納された分割データを圧縮する際に、分割データの先頭行を含む行に含まれるセルの符号化に、分割処理用の格納領域で上書きされず残されている前回の分割データの最終行を含む行に含まれるセルを参照セルとして参照できるので、専用のコードを用いた特殊な処理は必要ない。また、圧縮処理装置のメモリ領域の容量が十分でない場合でも、適切に処理することができる。
【００２９】
よって、本願発明に係る圧縮処理装置は、分割してデータを圧縮する際、高速で、かつ、処理に必要な記憶容量を増やすことなく、圧縮処理できる。
【００３０】
ここで、前回格納された分割データの圧縮時と今回格納された分割データの圧縮時とでは、上記テンプレートの形状が変更されることで、それぞれ格納した場合に対応させて、参照セルを読み出すことができる。例えば、上記テンプレートが２行からなる２ラインテンプレートである場合、上記前回格納された分割データの圧縮時と上記今回格納された分割データとにそれぞれ対応させて、上記２ラインテンプレートと当該２ラインテンプレートを符号化対象セルの存在する行を中心線として線対称移動させたテンプレートとのいずれかが用いられる。このように参照セルを指定するテンプレートが２ラインテンプレートである場合、テンプレートを線対称移動させるだけで、容易に参照セルを読み出することができるため、本発明に係る圧縮処理装置を容易に動作させることができる。
【００３１】
本発明に係る圧縮処理装置では、上記構成に加え、上記格納処理手段は、上記圧縮対象データを列方向に分割した最初の分割データを格納する際には、少なくとも、上記参照セルの行数から１引いた行数に上記最初の分割データの１行に含まれるセル数を乗算したセルを格納できる領域を除いた箇所から格納を始めてもよい。
【００３２】
上記構成によると、圧縮対象データの圧縮が始まる際、つまり、上記圧縮対象データを列方向に分割した最初の分割データを格納する際に、少なくとも、上記参照セルの行数から１引いた行数に上記最初の分割データの１行に含まれるセル数を乗算したセルを格納できる領域を除いた箇所から格納が始まる。よって、参照セルとし読み出す際に新たな処理をすることなく、上記参照セルの行数から１引いた行数に上記最初の分割データの１行に含まれるセル数を乗算したセルを格納できる領域を、参照セルを読み出す領域に用いることができる。よって、処理が複雑化することがなく符号化を行える。
【００３３】
本発明に係る圧縮処理装置では、上記構成に加え、上記格納処理手段は、上記圧縮対象データを列方向に分割した最初の分割データを格納する前に、少なくとも、上記参照セルの行数から１引いた行数に上記最初の分割データの１行に含まれるセル数を乗算したセルを格納できる領域を、０で初期化することを特徴とする請求項１または２に記載の画像圧縮装置。
【００３４】
上記構成によると、圧縮対象データの圧縮を行う前に、少なくとも、上記参照セルの行数から１引いた行数に上記最初の分割データの１行に含まれるセル数を乗算したセルを格納できる領域が、０で初期化される。予め０で初期化しておけば、上記最初の分割データを圧縮する際、参照セルとし読み出す際に新たな処理をすることなく、そのまま初期化したセルを読み出し参照セルとして符号化に用いることができる。よって、最初の分割データを圧縮する際に、符号化における処理が複雑化することがなく、時間を短縮することができる。
【００３５】
本発明に係る圧縮処理装置では、上記構成に加え、上記圧縮対象データは画像データであり、上記セルは、当該画像データの一以上の画素に対応していてもよい。
【００３６】
上記構成によると、画像データを分割して圧縮する際、高速で、かつ、メモリ容量を増やすことなく処理することができる。
【００３７】
本発明に係る圧縮処理装置では、上記構成に加え、上記行方向は、画像読取装置の走査方向に対応していてもよい。
【００３８】
上記構成によると、画像データを分割して圧縮する際、画像読取装置の走査方向で分割した画像データを処理することができ、画像読取装置で読み取った順に圧縮処理することができるので、効率よく処理できる。
【００３９】
本発明に係る圧縮処理方法は、上記課題を解決するために、セルを単位とし行方向および列方向に２次元に配列されるデータに対して、セルの行方向に沿って符号化対象セルを順次選択し、選択した符号化対象セルを、テンプレートにより指定される複数の参照セルに基づいて符号化することで、上記データを圧縮する圧縮処理方法において、１つの圧縮対象データを列方向に複数に分割した分割データを、これら分割データの圧縮処理に応じて分割処理用の格納領域に順次格納する際に、今回格納する分割データについては、上記分割処理用の格納領域に前回格納された分割データの後端行から先端行方向へ上記参照セルの行数から１引いた数分除いた次の行を始端として、上記前回格納された分割データの先端行方向へ順次上書きする格納処理ステップを含むことを特徴としている。
【００４０】
上記方法によると、上記圧縮処理装置と同様の効果を奏し、分割してデータを圧縮する際、高速で、かつ、メモリ容量を増やすことなく、符号化圧縮処理することできる。
【００４１】
また、本発明に係る圧縮処理装置は、コンピュータによって実現してもよく、この場合には、コンピュータを上記圧縮処理装置における上記各手段として動作させることにより上記圧縮処理装置をコンピュータにて実現させる圧縮処理装置制御プログラム、及びその圧縮処理装置制御プログラムを記録したコンピュータ読み取り可能な記録媒体も、本発明の範疇に入る。
【００４２】
これらの構成によれば、圧縮処理装置制御プログラムを、コンピュータに読み取り実行させることによって、上記圧縮処理装置と同一の作用効果を実現することができる。
【発明の効果】
【００４３】
本発明に係る圧縮処理装置は、以上のように、１つの圧縮対象データを列方向に複数に分割した分割データを、これら分割データの圧縮処理に応じて分割処理用の格納領域に順次格納する際に、今回格納する分割データについては、上記分割処理用の格納領域に前回格納された分割データの後端行から先端行方向へ上記参照セルの行数から１引いた数分除いた次の行を始端として、上記前回格納された分割データの先端行方向へ順次上書きする格納処理手段を備えている。
【００４４】
上記構成によると、格納処理手段は、１つの圧縮対象データを列方向に複数に分割した分割データを、これら分割データの圧縮処理に応じて分割処理用の格納領域に順次格納する際に、今回格納する分割データについては、上記分割処理用の格納領域に前回格納された分割データの後端行から先端行方向へ上記参照セルの行数から１引いた数分除いた次の行を始端として、上記前回格納された分割データの先端行方向へ順次上書きする。よって、本発明の係る圧縮装置は、今回の分割データ格納時、上記分割処理用の格納領域において上書きされていない領域では、前回の格納された分割データの最終行（ライン）を含む行（ライン）が格納されたままになっている。そのため、前回格納された分割データの最終行を含む行に含まれるセルも参照セルの読み取り対象にすることができる。なお、分割データの後端行とは、分割データにおいて分割された最後の行（ライン）、つまり、
１つ後の分割データの１行前の行である。また、先端行とは、分割データにおいて分割された最初の行、つまり、１つ前の分割データの１行後の行、あるいは前に分割データがなければ、自身の始まりの行、である。
【００４５】
ここで、圧縮処理は分割データの分割の順に行なわれるため、今回上書きされていない前回格納された分割データの最終行を含む行に含まれるセルは、今回格納された分割データのセルの符号化時に、参照セルとして用いることができる。よって、前回格納された分割データの最終行を含む行を別途保存することなく、今回格納された分割データの圧縮処理を適切に行える。つまり、今回格納された分割データを圧縮する際に、分割データの先頭行を含む行に含まれるセルの符号化に、分割処理用の格納領域で上書きされず残されている前回の分割データの最終行を含む行に含まれるセルを参照セルとして参照できるので、専用のコードを用いた特殊な処理は必要ない。また、圧縮処理装置のメモリ領域の容量が十分でない場合でも、適切に処理することができる。
【００４６】
よって、本願発明に係る圧縮処理装置は、分割してデータを圧縮する際、高速で、かつ、処理に必要な記憶容量を増やすことなく、圧縮処理できる。
【発明を実施するための最良の形態】
【００４７】
本発明の一実施形態について図１〜図１０に基づいて説明すると以下の通りである。本実施形態は、本発明に係る圧縮処理装置を、非特許文献１に記載されている、ＪＢＩＧのＱＭ−Ｃｏｄｅｒに適用した場合の例として説明する。なお、説明を簡単にするため、ＪＢＩＧの仕様に含まれる付加的な機能に関しては説明を省略する。
【００４８】
図１に示す本実施形態の圧縮処理装置１は、セルを単位とし行方向および列方向に２次元で示される画像データ（圧縮対象データ）に対して、セルの行方向に沿って符号化対象セルを順次選択し、各セルを算術符号化することで圧縮処理を行い、それによって得られた圧縮画像データ（符号化データ）を出力する。ここで、セルは、画像データの１画素に対応するのではなく、例えば２画素に対応してもよい。なお、圧縮対象データは、２次元画像データに限定されず、セルを単位とし当該セルが行方向および列方向に２次元に配列されるデータであれば、どのようなものであってもかまわない。また、セルは、圧縮対象データを符号化対象の単位に分けられるものであればどのようなものであってもかまわない。
【００４９】
圧縮処理装置１は、符号化対象セルを、コンテクストを成す近傍セル（参照セル）を読み出して（参照して）符号化を行う。読み出す近傍セルの決定については、後段に詳細に説明する。本実施形態の圧縮処理装置１における圧縮処理では、算術符号化が行われる。算術符号化では、符号化結果を０から１までの少数で表す。優勢確率シンボルとは、符号化対象セルの近傍形から予測されるシンボルであり、劣勢確率シンボルとは、予測結果と異なるシンボルである。図１０に示すように０から１までの領域を最初のインターバルとして優勢確率シンボルの出現確率（ＭＰＳ出現確率）と劣勢確率シンボルの出現確率（ＬＰＳ出現確率）とに分け、優勢確率シンボルが出現した場合には、ＭＰＳの出現確率を次のインターバルとし、劣勢確率シンボルが出現した場合にはＬＰＳの出現確率を次のインターバルとする操作を繰り返す。全ての入力ビットに対してこの操作が完了したときの優勢確率シンボルの出現確率の下端が圧縮結果となる。
【００５０】
圧縮処理装置１は、図１に示すように、格納処理部（格納処理手段）２、分割画像用メモリ（分割処理用の格納領域）３、コンテクスト生成部２２、取得部２３、算術符号部２４、記録部２５、およびレジスタ２６を備えている。
【００５１】
以下の説明では、圧縮処理装置１は、符号化対象セルを、テンプレートにより指定される、当該符号化対象セルと所定の相対位置にある複数の近傍セルに基づいて符号化し、その際、上記テンプレートとして、図５に示すＪＢＩＧ方式の圧縮における２ラインの形状の２ラインテンプレートを用いるものとする。図５において、斜線が引かれた四角が圧縮対象のセルであり、その周辺の１０個の四角がコンテクストを成す各近傍セルである。ＪＢＩＧ圧縮では、最低解像度レイヤのコンテクストとして図５に示す２ラインテンプレートの他に３ラインテンプレートが用意されている。ここでは２ラインテンプレートを用いて説明する。図５に示すように、２ラインテンプレートに含まれる近傍セル（参照セル）は２行を成すので、本実施形態では、参照セルの行数は、２ということになる。
【００５２】
格納処理部２は、圧縮処理装置１に分割画像データが入力されると、分割画像用メモリ３に格納する。本実施形態では、分割画像データ（分割データ）は、１つの圧縮対象の画像データ（圧縮対象データ）が、ｎライン（ｎ行）ずつ分割されたデータとする。
【００５３】
分割画像用メモリ３は、圧縮処理装置１に入力された分割画像データの１つを格納でき、分割画像データの１ラインを格納するライン格納領域をｎ＋１行分（ｎ＋１ライン分）有してしている記憶手段である。つまり、本実施形態では、分割画像用メモリ３は、図３および４に示すように２次元に管理されており、分割画像データの１ラインは分割画像用メモリ３のライン格納領域（図３，４では、升目の横の一行）に格納されるものとして説明するが、これに限定されない。なお、分割画像用メモリ３は、より大きな容量を有する他のメモリ内に部分画像用メモリの為の領域が確保されている形態であってもよい。
【００５４】
そして、分割画像用メモリ３は、０で初期化されている。予め０で初期化されていれば、近傍セルとし読み出す際に新たな処理をすることなく、そのまま初期化したセルを読み出し近傍セルとして符号化に用いることができる。よって、符号化における時間を短縮することができる。なお、少なくとも、２−１＝１行（参照セルの行数から１引いた行数）のライン格納領域を、０で初期化しておけばよい。
【００５５】
なお、本実施形態では、上記のように２ラインテンプレートを用いているため、分割画像用メモリ３に含まれるライン格納領域の数は、ｎ＋１であるが、３ラインテンプレートの場合には、分割画像用メモリ３には、ｎ＋２のライン格納領域が必要となる。また、ｍランプレートの場合には、ｎ＋ｍ−１のライン格納領域が必要となる。
【００５６】
また、本実施形態では、分割画像用メモリ３が有するライン格納領域の数はｎ＋１としたが、これは最低限の数であり、これ以上であってもよい。つまり、必要なライン格納領域の数は、分割画像データの行数（ライン数）に、上記テンプレートの行数から１を引いた数を加えた数以上であればよい。
【００５７】
また、本実施形態では、１つのライン領域は画像データの走査方向の１ライン（行）が格納される大きさとなっており、行方向とは、画像読み取り装置の走査方向に相当するものとする。この場合、画像読取装置で読み取った順に圧縮処理することができるので、効率よく処理できる。ただし、データの送り方によってはそうならない可能性もあるので、上記に限定されない。
【００５８】
格納処理部２は、各分割画像データを分割された順に分割画像用メモリ３に格納する際、今回格納する分割画像データについては、分割用メモリ３に前回格納された分割画像データの後端ラインから先端ライン方向へ１（参照セルの行数から１引いた行数）引いた数分除いた次のラインを始端として、上記前回格納された分割画像データの先端ライン方向へ順次上書きする。ここで、なお、分割画像データの後端ラインとは、分割画像データにおいて分割された最後のライン、つまり、１つ後の分割画像データの１ライン前の行である。また、先端ラインとは、分割画像データにおいて分割された最初のライン、つまり、１つ前の分割画像データの１行後のライン、あるいは前に分割画像データがなければ、自身の始まりのライン、である。
【００５９】
格納処理部２について、より詳細に説明する。格納処理部２は、各分割画像データを分割された順に分割画像用メモリ３に格納する際、１つ目の分割画像データを、分割画像用メモリ３の先頭のライン格納領域から数えて１ライン分除いた次のライン格納領域から、末尾のライン格納領域に同一方向に連続して上書きする（第１の格納処理）。また、格納処理部２は、２つ目の分割画像データを、分割画像用メモリ３の末尾のライン格納領域から数えて１ライン分除いた次のライン格納領域から、先頭のライン格納領域に向かって上記第１の格納処理と同一方向に連続して上書きする（第２の格納処理）。そして、格納処理部２は、分割画像データの圧縮毎に第１の格納処理と第２の格納処理とを交互に繰り返す。
【００６０】
これらのことを、簡単のため、ｎ＝６であり、分割画像データは６ラインから成るものとして、図３および４を用いて説明する。分割画像用メモリ３は、７ライン分（７行）のライン格納領域を有しており、その上から２行目のライン格納領域から７行目のライン格納領域まで、１つ目の分割画像データをラインの順に上書きして格納する。図３において、白抜きの矢印が貫いているライン格納領域が、１つ目の分割画像データが格納された領域である。白抜きの矢印の左に付した数字が１つ目の分割画像データにおけるライン番号である。つまり、分割画像用メモリ３の２行目のライン格納領域に１つ目の分割画像データの１番目のラインが格納され、分割画像用メモリ３の３行目のライン格納領域に１つ目の分割画像データの２番目のラインが格納され、分割画像用メモリ３の４行目のライン格納領域に１つ目の分割画像データの３番目のラインが格納され、…、分割画像用メモリ３の７行目（末尾）のライン格納領域に１つ目の分割画像データの６番目のラインが格納される。ここでは、格納は分割画像用メモリ３の上から下へと行われる。これにより、１つ目の分割画像データは全て分割画像用メモリ３に格納される。格納は、白抜きの矢印の方向であり、同一方向（図３および４では、左から右）に連続して行われる。
【００６１】
ここで、１つ目の分割画像データの場合には、分割画像用メモリ３が０で初期化されているため、その０初期化されたところに、分割画像データを格納していくが、これも上書きと呼ぶことにする。
【００６２】
２つ目の分割画像データの場合、分割画像用メモリ３の下から２行目のライン格納領域（上からは６行目のライン格納領域）から先頭のライン格納領域（１行目のライン格納領域）まで、２つ目の分割画像データをラインの順に上書きして格納する。図４においても、白抜きの矢印が貫いているライン格納領域が、２つ目の分割画像データが格納された領域である。白抜きの矢印の左に付した数字が２つ目の分割画像データにおけるライン番号である。つまり、分割画像用メモリ３の上から６行目のライン格納領域に２つ目の分割画像データの１番目のラインが格納され、分割画像用メモリ３の上から５行目のライン格納領域に２つ目の分割画像データの２番目のラインが格納され、分割画像用メモリ３の上から４行目のライン格納領域に２つ目の分割画像データの３番目のラインが格納され、…、分割画像用メモリ３の先頭である上から１行目のライン格納領域に２つ目の分割画像データの６番目のラインが格納される。ここでは、格納は分割画像用メモリ３の下から上へと行われる。これにより、２つ目の分割画像データは全て分割画像用メモリ３に格納される。格納は、白抜きの矢印の方向であり、上記第１の格納処理と同一方向に連続して行われる。このとき、図４の点線で囲まれた、今回上書きされていない上から７行目のライン格納領域には、その前に格納された分割画像データつまり１つ目の分割画像データの、最終ラインである６番目のラインが、格納されたままになっている。
【００６３】
３つ目以降の分割画像データがある場合には、格納処理部２は、分割画像データの圧縮毎に上記第１の格納処理と第２の格納処理とを交互に繰り返す。つまり、３つ目の分割画像データは、上記第１の格納処理にて格納が行われ、４つ目の分割画像データは、上記第２の格納処理にて格納が行われるということである。ただし、３つ目以降の分割画像データは、上記第１の格納処理にて格納されると、１行目のライン格納領域に、その前に格納された分割画像データ（３つ目の分割画像データを格納する場合には、２つ目の分割画像データ）の最終ラインが格納されたままとなる。
【００６４】
上記では２ラインテンプレート用いた場合で、ｎ＝６として説明したが、圧縮処理装置１では、ｍラインの形状を有するテンプレートを用いた圧縮を行う場合、格納処理部２は、ｎ行からなる分割画像データのうち１，３，５…つ目の分割画像データを、ｎ＋ｍ−１行のライン格納領域を有する分割画像用メモリ３の、先頭のライン格納領域から数えて、ｍ−１行分除いた次のライン格納領域であるｍ行目のライン格納領域から、ｎ＋ｍ−１行目の末尾のライン格納領域まで、同一方向に連続して上書き格納する。２，４，６…つ目の分割画像データを、分割画像用メモリ３のｎ＋ｍ−１行目の末尾のライン格納領域から数えてｍ行目のライン格納領域（先頭のライン格納領域から数えてｎ行目のライン格納領域）から先頭のライン格納領域まで上記と同一方向に連続して上書き格納する。
【００６５】
コンテクスト生成部２２は、分割画像用メモリ３に格納された分割画像データから、符号化対象となる符号化対象セルおよび、コンテクスト抽出する。ここで、コンテクストとは、所定の形状のテンプレート（ここでは、２ラインテンプレート）により指定される、符号化対象セルと所定の相対位置にある近傍セルのことである。圧縮処理装置１では、予測の際に、前回の入力信号までの入力ビット列だけでなく、近傍セルの状態をも用いるようになっている。すなわち、圧縮処理装置１は、予測の際に、周辺の複数の近傍セルがとりうる状態の組み合わせそれぞれに対して、優勢確率シンボルおよび劣勢シンボルの出現確率を推定する機能を持つ。
【００６６】
ここで、コンテクスト生成部２２は、分割画像データの圧縮毎に、符号化対象セルを、格納処理部２により分割画像用メモリ３に今回上書きして格納された順に読み出す。かつ、読み出した符号化対象セルに対するコンテクストを、分割画像用メモリ３の今回の格納では上書きされていないライン格納領域のセルも読み出し対象に含めて読み出す。そして、コンテクスト生成部２２は、分割画像データが上記第２の格納処理にて格納されると、上記テンプレートの形状を変更して、上記近傍セルを読み出す。本実施形態では、図５のテンプレートを符号化対象セルの存在する行を中心線として線対称移動させたテンプレートを用いて、近傍セルを読み出す。
【００６７】
このことを説明するため、図３から図７を用いて説明する。今回の分割画像データの圧縮時、分割画像データが格納処理部２により分割画像用メモリ３に、上記第１の格納処理にて図３のように上から下へ格納される。すると、コンテクスト生成部２２は、今回格納された順に、つまり上から下へ一方向に、符号化対象セルを読み出す。また、図５に示す２ラインテンプレートを用いて、読み出した符号化対象セルに対するコンテクストを成す近傍セルを読み出す。ここで、Ｘを符号化対象セルのアドレス、１ライン長（画像データの横幅）をＷｉｄｔｈとすると、この場合のコンテクストを成す近傍セルのアドレスは、次の１０個のアドレスとなる。つまり、「Ｘ−１，Ｘ−２，Ｘ−３，Ｘ−４，Ｘ−Ｗｉｄｔｈ＋２，Ｘ−Ｗｉｄｔｈ＋１，Ｘ−Ｗｉｄｔｈ，Ｘ−Ｗｉｄｔｈ−１，Ｘ−Ｗｉｄｔｈ−２，Ｘ−Ｗｉｄｔｈ−３」である。
【００６８】
他方、今回の分割画像データの圧縮時、分割画像データが格納処理部２により分割画像用メモリ３に、上記第２の格納処理にて図４のように上から下へ格納される。すると、コンテクスト生成部２２は、今回格納された順に、つまり下から上へ一方向に、符号化対象セルを読み出す。また、図５のテンプレートを符号化対象セルの存在する行を中心線として線対称移動させたテンプレートを用いて、読み出した符号化対象セルに対するコンテクストを成す近傍セルを読み出す。この場合のコンテクストを成す近傍セルのアドレスは、次の１０個のアドレスとなる。つまり、「Ｘ−１，Ｘ−２，Ｘ−３，Ｘ−４，Ｘ＋Ｗｉｄｔｈ＋２，Ｘ＋Ｗｉｄｔｈ＋１，Ｘ＋Ｗｉｄｔｈ，Ｘ＋Ｗｉｄｔｈ−１，Ｘ＋Ｗｉｄｔｈ−２，Ｘ＋Ｗｉｄｔｈ−３」である。
【００６９】
ここで、図７に示すように、近傍セルの読み出しには、分割画像用メモリ３全体を対象としており、つまり、分割画像用メモリ３の今回の格納では上書きされていないライン格納領域のセルも読み出し対象に含めて読み出す。
【００７０】
ここで、圧縮処理は分割画像データの分割の順に行なわれるため、今回上書きされていない前回格納された分割画像データの最終行を含む行に含まれるセルは、今回格納された分割画像データのセルの符号化時に、参照セルとして用いることができる。よって、前回格納された分割画像データの最終行を含む行を別途保存することなく、今回格納された分割画像データの圧縮処理を適切に行える。つまり、今回格納された分割画像データを圧縮する際に、分割画像データの先頭行を含む行に含まれるセルの符号化に、分割画像用メモリ３で上書きされず残されている前回の分割画像データの最終行を含む行に含まれるセルを参照セルとして参照できるので、専用のコードを用いた特殊な処理は必要ない。また、圧縮処理装置１のメモリ領域の容量が十分でない場合でも、適切に処理することができる。
【００７１】
よって、圧縮処理装置１は、分割してデータを圧縮する際、高速で、かつ、処理に必要な記憶容量を増やすことなく、圧縮処理できる。
【００７２】
以上のように、２ラインテンプレートである場合、上記第２の格納処理にて格納した場合でも、テンプレートを線対称移動させたテンプレートを用いるだけで、容易に近傍セルを読み出せるので、本発明に係る圧縮処置装置は、近傍セルの読み出しに２ラインテンプレートを用いる場合に適用するのが、特に好ましい。しかし、３ラインの以上のテンプレートを用いる場合にも適用できる。
【００７３】
ただし、ｍが３以上であるｍラインのテンプレートを用いた圧縮を行なう場合には、２つ目以降の分割画像データでは、次のように、元のｍラインのテンプレートの形状を適宜変更する必要がある。つまり、上記第２の格納処理で格納した場合には、末尾のライン格納領域から数えて２ｍ−１行目以降のライン格納領域に格納されているセルには、元のｍラインのテンプレートを符号化対象セルの存在する行を中心線として線対称移動させたテンプレートを用いればよい。上記第１の格納処理で格納した場合では、先頭のライン格納領域から数えて２ｍ−１行目以降のライン格納領域に格納されているセルには、元のｍラインのテンプレートをそのまま用いればよい。しかし、末尾あるいは先頭のライン格納領域から数えて２ｍ−２行目までのライン格納領域に格納されているセルには、元のｍラインのテンプレートを、符号化対象セルの位置に合わせて、適宜変更したテンプレート用いて圧縮を行なう。
【００７４】
そして、コンテクスト生成部２２は、抽出した符号化対象セルおよびコンテクストを成す近傍セルを取得部２３に出力する。また、コンテクスト生成部２２は、算術符号部２４の符号処理部２９からのセルインクリメント指示を受信すると、分割画像用メモリ３に格納された分割画像データから、次の符号化対象セルおよびコンテクストを抽出する。
【００７５】
次に、取得部２３について説明する。取得部２３は、予測値としての優勢確率シンボル（ＭＰＳ）を、周辺画素の配列（コンテクスト）に対する優勢確率シンボルを記録した記録部２５の確率推定テーブル２７から取得する。
【００７６】
ここで、確率推定テーブル２７は、図８に示すように、コンテクストと、そのコンテクストから予想されるＭＰＳの値との関係を含んでいる。また、確率推定テーブル２７は、コンテクストと、このコンテクストに応じたＬＰＳインターバルの推定値（ＬＳＺ）のインデックスＳＴとの関係も含んでいる。ＬＳＺについては後述する。取得部２３は、入力されるコンテクストを用いて、記録部２５の確率推定テーブル２７にアクセスして、インデックスＳＴを得る。取得部２３は、ＭＰＳとインデックスＳＴとを得ると、画素の値（入力ビットの値；入力シンボル）、ＭＰＳ、インデックスＳＴを算術符号部２４に出力する。以上のように、符号化対象画素（符号化対象セル、符号化対象のビットに対応する画素）の近傍画素（近傍セル、コンテクスト）の値から符号化対象のビット（シンボル）のＬＰＳインターバル（この場合にはＬＰＳインターバルの推定値）を推定する推定ステップが、取得部２３と確率推定テーブル２７とによって実行される。すなわち、取得部２３および確率推定テーブル７は、上記推定ステップを実行する推定部として機能する。
【００７７】
算術符号部２４は、入力される画素の値、ＭＰＳ、インデックスＳＴから、符号化データである実数ｘを生成する。この算術符号部２４は、符号処理部２９および前処理部３０を含んでいる。
【００７８】
符号処理部２９は、前処理部３０から入力される選択信号に応じて、各処理部２９ａ〜２９ｃのうちから適切な処理部を選択する。また入力された画素の値、ＭＰＳ、ＳＴを用いて、選択した処理部によって符号化データを生成する。符号処理部２９は、優勢確率シンボルの符号化を行うＭＰＳ処理部９ａ、劣勢確率シンボルの符号化を行うＬＰＳ処理部９ｂ、正規化処理を実行するＲＥＮＯＲＭ処理部９ｃを含んでいる。
【００７９】
前処理部３０は、取得部２３から入力される画素の値、ＭＰＳ、ＳＴに応じて、選択信号を生成して、符号処理部２９に出力する。前処理部３０は、選択部３０ａを含んでいる。
【００８０】
選択部３０ａは、選択信号を生成するために、入力される画素の値（符号化対象のシンボル）と、そのコンテクストから予想されるＭＰＳとを比較し、符号化対象のシンボルが優勢確率シンボルか劣勢確率シンボルかを判断する。選択部３０ａは、入力に応じて選択信号を生成して、符号処理部２９に出力する。
【００８１】
記録部２５には、確率推定テーブル２７と確率推定表２８とが記録されている。なお、確率推定テーブル２７と確率推定表２８とは、全く別のものである。テーブルは表とも訳し得るが、ITU-T T.82の日本語訳(ITU-T WHITE BOOK ディジタル静止画像圧縮符号化関連勧告書 勧告T.82)でこのようになっているため、その語句をそのまま用いることとする。
【００８２】
確率推定テーブル２７は、コンテクストごとの優勢確率シンボルＭＰＳと、ＬＳＺのインデックスＳＴとを保存するテーブルである。
【００８３】
なお、優勢確率シンボルは、０または１の値を取る。ＬＳＺのインデックスＳＴは、ＪＢＩＧにおいては、０から１１２までのどれかの値を取る。また、コンテクストが１０ビットである一方で、インデックスは７ビットであるので、同じインデックスをもつ異なるコンテクストが存在することになる。例えばコンテクスト“００００００００００”のＬＳＺのインデックスＳＴと、“０００００００００１”のＬＳＺのインデックスＳＴとが共に１３というようなことも起こり得る。このＬＳＺのインデックスＳＴは、後述するＪＢＩＧの確率推定表８において、近傍セルに出現した０または１の値（シンボル）の組合せ状況（コンテクスト）ごとに、これまで注目画素の位置に出現した値（シンボル）の履歴から注目画素に出現するであろう値（シンボル）の出現確率の予測を表すために用いられる。
【００８４】
確率推定表２８は、図９（ａ），（ｂ）に示す非特許文献１の表２４のように、ＬＳＺのインデックスＳＴから、ＬＳＺや次のＳＴなどを求めるための表である。確率推定表８からＬＳＺを求めるために、確率推定テーブル７から得たＬＳＺのインデックスＳＴが使用される。この確率推定表８は、符号化処理の際にも書き換えられることはない。すなわち、確率推定表８は、参照されるだけで、書き換えられることはない。
【００８５】
また、圧縮処理装置１は、作業用メモリとしてのレジスタ２６を備えている。このレジスタ２６は、高速アクセス可能なメモリである。レジスタ２６は、Ａｒｅｇ２６ａ、Ｃｒｅｇ２６ｂを含んでいる。
【００８６】
Ａｒｅｇ２６ａは、インターバルの大きさの値Ａｒｅｇを保持（蓄積）するための記憶領域である。また、Ｃｒｅｇ２６ｂは、インターバルの低数の値Ｃｒｅｇを保持する記憶領域である。Ａｒｅｇ２６ａおよびＣｒｅｇ２６ｂは、整数で固定精度である。
【００８７】
なお、コンテクスト生成部２２と取得部２３とが、算術符号部２４に含まれていてもよい。算術符号部２４における符号化の処理は上記したものに限定されず、符号化対象セルを、近傍セルを用いて符号化するような処理ものであれば、どのようなものであってもかまわない。
【００８８】
次に、圧縮処理装置１における圧縮処理について、図２のフローチャートに基づいて説明する。圧縮処理装置１に二次元の分割画像データ（ページデータ）が入力されると、入力された分割画像データを格納処理部２が分割画像用メモリ３に格納する（Ｓ１）。本実施形態の圧縮処理では、Ｓ１は、図３に示すように分割画像用メモリ３のライン格納領域の上から下に順に分割画像データを格納する場合と、図４に示すように分割画像用メモリ３のライン格納領域の下から上に順に分割画像データを格納する場合とがあり、部分画像データの圧縮の度に交互に入れ替わる。
【００８９】
次に、分割画像用メモリ３に格納された分割画像データを少なくとも１つ以上のストライプに分ける（Ｓ２）。このストライプとは、圧縮処理を行う単位であり、元の分割画像データ中の１ライン以上の横ライン（行）からなる。本実施形態では、１ストライプは、分割画像データの１ラインに対応するものとする。
【００９０】
Ｓ２からＳ１６までのストライプのループ（LOOP_A）の内部では個々のストライプの処理を行う。Ｓ２から一つのストライプについての処理を開始し、Ｓ２〜Ｓ１６のストライプのループ（LOOP_A）においてそのストライプの処理（セルの符号化を繰り返す処理）が完了すると、Ｓ２〜Ｓ１６のストライプのループ（LOOP_A）の先頭のＳ２に戻って、次のストライプの処理をＳ３から開始する。Ｓ２からＳ１６までのループによって全てのストライプに対して処理が完了すると、画像データ全体の符号化が完了する。
【００９１】
ストライプのループ（LOOP_A）の中にセルのループ（LOOP_B）がある。セルのループ（LOOP_B）では、Ｓ３からＳ１４までであり、各セルの符号化処理が行われる。１つのセルの処理が完了すると、セルのループ（LOOP_B）の先頭Ｓ３に戻って次のセルの符号化がＳ４から行われる。
【００９２】
そして、Ｓ３〜Ｓ１４のセルのループ（LOOP_B）にて符号化対象セルについての符号化を行い、１つのストライプにおける全ての画素の処理が完了すると１つのストライプの処理が完了したことになる。次に、Ｓ４からＳ１６までの処理について説明する。
【００９３】
Ｓ４で、コンテクスト生成部２２は、分割画像用メモリ３から、符号化対象セル（対象セル）を選択する。この符号化対象セルの選択は、格納処理部２が分割画像用メモリ３に上書きして格納した順に行う。また、Ｓ４ではコンテクスト生成部２２は、分割画像用メモリ３から、近傍セル（コンテクスト）を読み出す。近傍セルの読み出しには、分割画像用メモリ３全体を対象としており、つまり、分割画像用メモリ３の今回の格納では上書きされていないライン格納領域のセルも読み出し対象に含めて読み出す。ここでは、JBIG方式の圧縮における２ラインの形状の２ラインテンプレートを用いて近傍セルを読み出すとする。Ｓ１の格納で、上から下に順に分割画像データを格納させている場合には、図５に示すテンプレートをそのまま用い、下から上に順に分割画像データを格納させている場合には、図５のテンプレートを符号化対象セルの存在する行を中心線として線対称移動させて用いて、近傍セルを読み出す。そして、コンテクスト生成部２２は、読み取った符号化対象セルと近傍セル（コンテクスト）とを取得部２３に送信する。
【００９４】
Ｓ５では、取得部２３が、コンテクスト生成部２２から送信された対象セルおよびコンテクストに応じて、記録部２５の確率推定テーブル２７にアクセスして、コンテクストについての優勢確率シンボルおよび劣勢確率シンボルの確率推定値のインデックスＳＴを取得する。
【００９５】
Ｓ６では、算術符号部２４の前処理部３０において、選択部３０ａが、入力される符号化対象セルの値とMPSとに応じて、符号化対象セルがMPSであるか否かを判別する。Ｓ６において符号化対象セルがMPSであると判別された場合には、算術符号部２４の符号処理部２９において、ＭＰＳ処理部２９ａがＭＰＳ処理（CODEMPS：Ｓ７〜Ｓ１０）を行う。一方、Ｓ６において符号化対象セルがLPSであると判別された場合には、算術符号部２４の符号処理部２９において、ＬＰＳ処理部２９ｂがＬＰＳ処理（CODELPS：Ｓ１１〜Ｓ１３）を行
う。
【００９６】
Ｓ７では、ＭＰＳ処理部２９ａは、記録部２５の確率推定表２８にアクセスして、劣勢確率シンボルの確率推定値のインデックスＳＴを用いて、劣勢確率シンボルの確率推定値を取得し、これに応じてレジスタ２６のＡｒｅｇ２６ａ、Ｃｒｅｇ２６ｂを書き換える。Ｓ８では、ＭＰＳ処理部２９ａは、Ａｒｅｇ２６ａの値が０．５未満であるか否かを判別して、０．５未満である場合にはＳ９に進み、０．５以上の場合にはＳ１４に進む。Ｓ９ではＭＰＳ処理部２９ａがＲＥＮＯＲＭ処理部２９ｃに指示して、ＲＥＮＯＲＭ処理部２９ｃがレジスタ２６のＡｒｅｇ２６ａ、Ｃｒｅｇ２６ｂに対して正規化処理をして、得られた符号化データを必要に応じて出力する。Ｓ１０では、ＭＰＳ処理部２９ａは、記録部２５の確率推定表２８を更新し、Ｓ１４に進む。
【００９７】
一方、Ｓ１１では、ＬＰＳ処理部２９ｂが、記録部２５の確率推定表２８にアクセスして、劣勢確率シンボルの確率推定値のインデックスＳＴを用いて、劣勢確率シンボルの確率推定値を取得し、これに応じてレジスタ２６のＡｒｅｇ２６ａ、Ｃｒｅｇ２６ｂを書き換える。Ｓ１２では、ＬＰＳ処理部２９ｂが、レジスタ２６のＡｒｅｇ２６ａ、Ｃｒｅｇ２６ｂに対して、確率推定表のＳＷＩＴＣＨの値に応じて、ＬＰＳとＭＰＳの入れ替えと符号出力を行う。すなわち、ＬＰＳ処理部２９ｂは、ＬＳＺのインデックスに対応する確率推定表のＳＷＩＴＣＨの値が１か否かによって、入れ替えを行うかどうかを判断する。Ｓ１３では、ＬＰＳ処理部２９ｂは、記録部２５の確率推定表２８を更新し、Ｓ１４に進む。
【００９８】
Ｓ１４では、符号処理部２９がコンテクスト生成部２２に対してセルインクリメントの指示を行い、セルについてのループを終了する。このような手順をストライプの全てのセルに対して行うことで、ストライプの圧縮を行う。Ｓ１５では、ストライプについての処理が終了したか否かを判別し、終了していた場合にはレジスタ２６から符号化データを出力する（フラッシュ処理）。このように、次のストライプの圧縮に進む前に、ここまでの圧縮結果のうちで、まだ出力されていない部分を出力する。Ｓ１６では、コンテクスト生成部２２が新たなストライプを選択する。全てのストライプの圧縮が完了すれば画像全体の圧縮が完了したことになり、入力画像データの全てを符号化した場合には、処理を終了する。
【００９９】
なお、本実施形態では圧縮処理装置１を上記のように、２値画像データをマルコフ情報源でモデル化し、符号化シンボルをその周辺画素の状態によって予測し、予測結果に応じて算術符号化する方式を用いるものとして説明した。しかし、本発明は、セルを単位として２次元に配列されたデータに対して、符号化対象セルの近傍から予測される値と符号化対象セルの値との差分を圧縮するようなあらゆる圧縮形式に適用することができる。
【０１００】
また、圧縮処理装置１の各ブロックは、ハードウェアロジックによって構成してもよいし、次のようにＣＰＵを用いてソフトウェアによって実現してもよい。
【０１０１】
すなわち、圧縮処理装置１は、各機能を実現する制御プログラムの命令を実行するＣＰＵ（central processing unit）、上記プログラムを格納したＲＯＭ（read only memory）、上記プログラムを展開するＲＡＭ（random access memory）、上記プログラムおよび各種データを格納するメモリ等の記憶装置（記録媒体）などを備えている。そして、本発明の目的は、上述した機能を実現するソフトウェアである圧縮処理装置１の制御プログラムのプログラムコード（実行形式プログラム、中間コードプログラム、ソースプログラム）をコンピュータで読み取り可能に記録した記録媒体を、上記圧縮処理装置１に供給し、そのコンピュータ（またはＣＰＵやＭＰＵ）が記録媒体に記録されているプログラムコードを読み出し実行することによっても、達成可能である。
【０１０２】
上記記録媒体としては、例えば、磁気テープやカセットテープ等のテープ系、フロッピー（登録商標）ディスク／ハードディスク等の磁気ディスクやＣＤ−ＲＯＭ／ＭＯ／ＭＤ／ＤＶＤ／ＣＤ−Ｒ等の光ディスクを含むディスク系、ＩＣカード（メモリカードを含む）／光カード等のカード系、あるいはマスクＲＯＭ／ＥＰＲＯＭ／ＥＥＰＲＯＭ／フラッシュＲＯＭ等の半導体メモリ系などを用いることができる。
【０１０３】
また、圧縮処理装置１を通信ネットワークと接続可能に構成し、上記プログラムコードを通信ネットワークを介して供給してもよい。この通信ネットワークとしては、特に限定されず、例えば、インターネット、イントラネット、エキストラネット、ＬＡＮ、ＩＳＤＮ、ＶＡＮ、ＣＡＴＶ通信網、仮想専用網（virtual private network）、電話回線網、移動体通信網、衛星通信網等が利用可能である。また、通信ネットワークを構成する伝送媒体としては、特に限定されず、例えば、ＩＥＥＥ１３９４、ＵＳＢ、電力線搬送、ケーブルＴＶ回線、電話線、ＡＤＳＬ回線等の有線でも、ＩｒＤＡやリモコンのような赤外線、Ｂｌｕｅｔｏｏｔｈ（登録商標）、８０２．１１無線、ＨＤＲ、携帯電話網、衛星回線、地上波ディジタル網等の無線でも利用可能である。なお、本発明は、上記プログラムコードが電子的な伝送で具現化された、搬送波に埋め込まれたコンピュータデータ信号の形態でも実現され得る。
【０１０４】
なお、本発明は上述した実施形態に限定されるものではなく、請求項に示した範囲で種々の変更が可能である。すなわち、請求項に示した範囲で適宜変更した技術的手段を組み合わせて得られる実施形態についても本発明の技術的範囲に含まれる。
【産業上の利用可能性】
【０１０５】
本発明は、２次元で表現することができるデータの圧縮に利用することができ、例えば、ファクシミリ装置（ＦＡＸ）やプリンタ、パーソナルコンピュータのプリンタドライバ等における画像データの圧縮に有効である。
【図面の簡単な説明】
【０１０６】
【図１】本実施形態の圧縮処理装置の要部構成を示すブロック図である。
【図２】上記圧縮処理装置にて行う符号化処理のフローチャートを示す図である。
【図３】分割画像データを、部分画像格納メモリの上から下に向かって一方向で格納することを説明するための概念図である。
【図４】分割画像データを、部分格納メモリの下から上に向かって一方向で格納することを説明するための概念図である。
【図５】符号化対象セルとそのコンテクストを成す近傍セルとを説明するための図である。
【図６】図３のように格納した場合の、符号化対象セルに対するコンテクストを成す近傍セルを説明するための図である。
【図７】図４のように格納した場合の、符号化対象セルに対するコンテクストを成す近傍セルを説明するための図である。
【図８】上記圧縮処理装置にて用いる確率推定テーブルの一例を示す図である。
【図９】（ａ）は上記圧縮処理装置にて用いる確率推定表の一例の一部を示す図であり、（ｂ）は、確率推定表の他の一部を示す図である。
【図１０】算術符号化を説明するための概念図である。
【図１１】従来の圧縮処理装置にて行う符号化処理のフローチャートを示す図である。
【符号の説明】
【０１０７】
１      圧縮処理装置
２      格納処理部（格納処理手段）
３      分割画像用メモリ（分割処理用の格納領域）
２２    コンテクスト生成部
２３    取得部
２４    算術符号部
２５    記録部
２６    レジスタ
２６ａ  Ｃｒｅｇ
２６ｂ  Ｃｒｅｇ
２７    確率推定テーブル
２８    確率推定表
２９    符号化処理部
２９ａ  ＭＰＳ処理部
２９ｂ  ＬＰＳ処理部
３０    前処理部
３０ａ  選択部
【図１】
2009159105.tif 000003
【図２】
2009159105.tif 000004
【図３】
2009159105.tif 000005
【図４】
2009159105.tif 000006
【図５】
2009159105.tif 000007
【図６】
2009159105.tif 000008
【図７】
2009159105.tif 000009
【図８】
2009159105.tif 000010
【図９】
2009159105.tif 000011
【図１０】
2009159105.tif 000012
【図１１】
2009159105.tif 000013