(57)【特許請求の範囲】
【請求項１】
セルを単位とし当該セルが２次元に配列されている圧縮対象データを、符号化対象セルを順次選択しながら符号化することによって圧縮する圧縮処理装置において、
上記圧縮対象データでのセルが成す各行では同一方向に連続し、かつ、隣接する各２行では一方の行の末尾のセルが他方の行の先頭のセルと連続するようにセルのアドレスを１次元で管理する、アドレス管理手段と、
符号化対象セルを、アドレス順に、当該符号化対象セルのアドレスに対して、上記アドレス管理手段によって管理された１次元のアドレスにおける所定の相対アドレス位置にある複数の近傍セルに基づき符号化する符号化手段と、
を備えたことを特徴とする圧縮処理装置。
【請求項２】
空白セルからなる空白データに続けて上記圧縮対象データを記録領域に格納するデータ格納手段を備え、
上記アドレス管理手段は、空白データの各セルが連続し、かつ、空白データの末尾のセルが上記圧縮対象データの先頭のセルに続くようにセルのアドレスを管理することを特徴とする請求項１に記載の圧縮処理装置。
【請求項３】
上記データ格納手段は、上記符号化手段が、上記圧縮対象データにおける最初に符号化する符号化対象セルの符号化に用いる近傍セルを確保できる数だけ、上記空白セルを格納することを特徴とする請求項２に記載の圧縮処理装置。
【請求項４】
上記圧縮対象データは画像データであり、
上記アドレス管理手段は、上記セルとして当該画像データの画素のアドレスを管理することを特徴とする請求項１〜３の何れか１項に記載の圧縮処理装置。
【請求項５】
セルが２次元に配列されている圧縮対象データを、符号化対象セルを順次選択しながら符号化することによって圧縮する圧縮処理装置の制御方法において、
上記圧縮対象データでのセルが成す各行では同一方向に連続し、かつ、隣接する各２行では一方の行の末尾のセルが他方の行の先頭のセルと連続するようにセルのアドレスを１次元で管理する、アドレス管理ステップと、
符号化対象セルを、アドレス順に、当該符号化対象セルのアドレスに対して、上記アドレス管理ステップで管理された１次元のアドレスにおける所定の相対アドレス位置にある複数の近傍セルに基づき符号化する符号化ステップと、
を含むことを特徴とする圧縮処理装置の制御方法。
【請求項６】
請求項１〜４の何れか１項に記載の圧縮処理装置を動作させるための制御プログラムであって、コンピュータを上記圧縮処理装置における上記各手段として機能させるための圧縮処理制御プログラム。
【請求項７】
請求項６に記載の圧縮処理制御プログラムが記録されたコンピュータ読み取り可能な記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、２次元に配列されたデータを圧縮処理する圧縮処理装置、圧縮処理方法、圧縮処理プログラム、およびコンピュータ読み取り可能な記録媒体に関するものである。
【背景技術】
【０００２】
プリンタドライバ等の画像処理システムにおいて、２次元画像データ（画像データ）を圧縮する際、注目画素をその周辺画素の状態によって予測し、予測結果に応じて算術符号化する方式がある。このような２次元画像データを圧縮するアルゴリズムとして、例えばJBIG（Joint Bi-level Image coding experts Group）圧縮が知られている（例えば、非特許文献１、２参照）。JBIG圧縮においては、２次元画像データを上から横１ラインずつ、左から右に走査して符号化対象となる単位であるセル（画素）を選択し、セルを一つずつ符号化して画像データの圧縮を行う。各セルを符号化する際には、符号化対象セル（対象セル）の付近にある幾つかの近傍セル（コンテクスト）を参照し、この近傍セルに対して、対象セルが出現する確率を用いて符号化を行う。コンテクストとは、所定の形状のテンプレートにより指定される、対象セルと所定の相対位置にある、対象セルの符号化に用いられる近傍セルのことである。図１１は、JBIG方式の圧縮における２ラインの形状のテンプレート（２ラインテンプレート）の図である。図１１では、太枠で囲まれたセルが対象セルであり、その周辺の斜線が記されたセルが近傍セル（コンテクスト）である。なお、図１１のように、対象セルを太線で囲い、近傍セルには斜線を付ける記載の仕方は、本明細書中で説明する他の図でも同様に用いるものとする。
【０００３】
JBIG圧縮では、２ラインテンプレート又は３ラインテンプレートに基づいて読み取りを行うが、コンテクストが画像データの外側にはみ出して、近傍セルとして画像データの外にあるセルを参照しなければならない場合がある。図１１に示す２ラインテンプレートを用いると、対象セルが、画像データの右端から２セル以内にある場合（図１２（ａ））や、左端から４セル以内にある場合（図１２（ｂ））、あるいは画像の上端にある場合（図１２（ｃ））にはコンテクストが画像データの外側にはみ出してしまう。なお、図１２（ａ）〜（ｃ）において、Ｘが記載されたセルがデータが格納されたセル、「？」が記載されたセルが画像データから、はみ出してしまうセルである。また、太枠で囲まれたセルが対象セル、斜線のセルがコンテクストを成す近傍セルである。
【０００４】
このように、コンテクストが画像データの外側にはみ出してしまい、近傍セルとして画像データの外にあるセルを参照しなければならない場合には、JBIG圧縮では画像データの外にある近傍セルを空白（０、ゼロ）であるとみなして圧縮を行う。例えば、対象セルの符号化において、コンテクストを参照する（読み取る）際に、図１３に示すような処理が行われる。コンテクストが画像データからはみ出すか否かを検出し（Ｓ１０１）、はみ出さない場合（Ｓ１０１においてＮＯ）、対象セルとコンテクストである近傍セルを読み出す（Ｓ１０２）。はみ出す場合には（Ｓ１０１においてＹＥＳ）、対象セルの読み取りを行い（Ｓ１０３）、コンテクストである近傍セルのうち画像データからはみ出さないものを読み取り（Ｓ１０４）、コンテクストである近傍セルのうち画像データからはみ出す部分にゼロを代入する（Ｓ１０５）。
【０００５】
このように、画像データの外にある近傍セルを参照しなければならない場合には、上記のような処理が行われるため、JBIG圧縮をコンピュータ上で実行しようとすると、近傍セルが画像データの外にはみ出すかどうかを判定しながら符号化して圧縮を行なければならないため、圧縮速度が低下するという問題があった。
【０００６】
上記問題を解決する方法として、圧縮しようとしている２次元画像データの両端に空白領域を設ける圧縮処理装置が知られている（例えば、特許文献１参照）。この装置では、図１４（ａ）〜（ｃ）に示すように、画像データの上側に横１ライン、左側に縦４ライン、右側に縦２ライン分のメモリを確保し、それらのメモリに０を入れる。換言すれば、像データの上側に横１ライン、左側に縦４ライン、右側に縦２ライン分の空白セルを設ける。このようにすることによって、対象セルが、画像データの右端から２セル以内にある場合（図１４（ａ））や、左端から４セル以内にある場合（図１４（ｂ））や、画像の上端にある場合（図１４（ｃ））でも、特別な処理を行うことなく画像データの端のセルを符号化することができる。近傍をそのまま参照すれば、２次元画像データの両端に空白セルが設けられているために、特殊な処理をすることなく、正常に符号化を行うことができる。
【０００７】
他方で、３次元セル構造を一筆書きで空間充填走査を行って、１次元的データに変換し、その空間上で他のセルを参照して圧縮を行う方法がある（例えば、特許文献２参照）。
【特許文献１】特許第３６２２０４３号（２００４年１２月３日登録）
【特許文献２】特開２００２−１２２５３７号公報（２００２年４月２６日公開）
【非特許文献１】ITU-T(International Telecommunication Union Telecommunication standardization sector) WHITE BOOK ディジタル静止画像圧縮符号化関連勧告書(財団法人 新日本ITU協会) 勧告T.82
【非特許文献２】WTSC-93 (WORLD TELECOMMUNICATION STANDARDIZATION CONFERENCE), Helsinki, 1-12 MARCH 1993
【発明の開示】
【発明が解決しようとする課題】
【０００８】
しかしながら、メモリに格納された２元画像データの端に空白領域を設ける場合、メモリ空間上に格納された画像データの横ライン毎に該ラインを挟むように空白セルを挿入しなければならない。そのためには、元の２次元画像を格納していたものとは別のメモリ領域を確保し、そのメモリ領域に対して、画像データの横ラインの両端を空白セル部分で挟みながら画像を１ラインずつコピーしていくなどの方法を取らなければならない。そのため、時間とメモリの無駄となる。さらに、画像を圧縮する際には、メモリ上の空白セルを圧縮しないように読み飛ばす必要があるため、これも時間の無駄となる。
【０００９】
また他方で、一筆書きにして空間充填走査を行う場合には、走査に時間がかかり、また、空間充填走査を行ったデータを格納するメモリ領域が必要になる。その上、空間充填走査によって作られた１次元データ上では、近傍セルの決定に複雑な計算が必要となる。具体的に説明すると、セルの符号化を行う前に、図１５に示すように、２次元画像データが与えられると（Ｓ１１１）、空間補充アルゴリズムに沿って画像データのセルの再配置（空間補充走査）を行う（Ｓ１１２）。この空間補充走査は、画像データの全セルが一筆書きとなるように、例えば、図１６（ａ）の点線で示すようにセルを連続させて配置させる。つまり、図１６（ｂ）に示すように、図１６（ａ）に示す２次元画像データにおける奇数行の横ライン（図１６（ａ）では右から左への連続したセル、つまり、白抜きの矢印に対応するセルで）の次に、偶数行の横ライン（図１６（ａ）では右から左への連続したセル）を逆に（左から右へ連続させて）なるよう格納させて１次元のデータにする。なお、図１６（ａ）の四角いマス目ひとつひとつがセルである。図１６（ａ）では、横ラインは４セルからなるが、図１６（ｂ）では１ラインが７セルからなっている。
【００１０】
このように空間補充走査が行われて１次元データとなったデータについて、符号化するときには、次のようにしなければならない。ここでは、図１７（ａ）に示す２次元画像データについて空間補充走査が行われ、図１７（ｂ）に示す１次元データになったものとする。図１７（ａ）〜（ｄ）において、各四角いマス目ひとつひとつがセルである。図１７（ｂ）に示す１次元データにおいて、あるアドレスｘの対象セルを符号化する際に参照する近傍セルのアドレスは、次にように決める。対象セルが図１７（ａ）に示すように、元の画像データでは偶数行の横ラインの右端セルである場合には、コンテクストを成す近傍セルのアドレスは、それぞれ、ｘ＋１、ｘ＋２、ｘ＋３、ｘ＋４、ｘ＋（（元の画像データ横ラインのセル数）−１）、ｘ＋（（元の画像データ横ラインのセル数）−２）、ｘ−１、ｘ−２、ｘ−３、ｘ−４となる。ここでは、図７（ａ）に示すように、元の画像データの横ラインのセル数（ライン幅）は１２である。
【００１１】
また、図１７（ｃ）に示す２次元画像データについて空間補充走査が行われ、図１７（ｄ）に示す１次元データになったものとする。図１７（ｄ）に示す１次元データにおいて、あるアドレスｘの対象セルを符号化する際に参照する近傍セルのアドレスは、次にように決める。対象セルが図１７（ｃ）に示すように、元の画像データの偶数行の横ライン上であり、右端から２セルより内側かつ、左端から４セルより内側にある場合には、次のようになる。つまり、コンテクストを成す近傍セルのアドレスは、ｘ＋１、ｘ＋２、ｘ＋３、ｘ＋４、ｘ−（元の画像データにおいて、対象セルが存在する横ラインの右端セルから対象セル右隣のセルまでのセル数（右端セルと右隣のセルを含む）、図１７（ｃ）を用いて説明すると、ライン２と記載された白抜き矢印の先頭のセルから対象セル右隣のセルまでのセル数、以降では右端セルから右隣セルまでのセル数と呼ぶ）×２＋１、ｘ−（右端のセルから右隣セルまでのセル数）×２、ｘ−（右端のセルから右隣セルまでのセル数）×２−１、ｘ−（右端のセルから右隣セルまでのセル数）×２−２、ｘ−（右端のセルから右隣セルまでのセル数）×２−３、ｘ−（右端のセルから右隣セルまでのセル数）×２−４となる。図１７（ｃ）では、右端セルから右隣セルまでのセル数は、３である。
【００１２】
このように、一筆書きの空間充填走査によって作られた一次元データ上で、ＪＢＩＧの２ラインテンプレートのような固定されたコンテクストの参照を行おうとした場合には、元の２次元画像データにおいてどこにあるセル（例えば右端セル）であるかを認識して近傍セルを決定する必要がある。対象セルが元の２次元画像データにおける位置によって、近傍セルのアドレスの決め方が異なるため、複雑な計算をおこなわなければならない。これらのことから、一筆書きの空間充填走査を用いた符号化圧縮処理では、符号化処理の時間がかかり、圧縮速度が遅くなる。
【００１３】
本発明は、上記の問題点に鑑みてなされたものであり、その目的は、少ない記憶容量にて高速で符号化圧縮処理できる圧縮処理装置、圧縮処理方法、圧縮処理装置制御プログラム、およびコンピュータ読み取り可能な記録媒体を実現することにある。
【課題を解決するための手段】
【００１４】
本発明に係る圧縮処理装置は、上記課題を解決するために、セルが２次元に配列されている圧縮対象データを、符号化対象セルを順次選択しながら符号化することによって圧縮する圧縮処理装置において、上記圧縮対象データでのセルが成す各行では同一方向に連続し、かつ、隣接する各２行では一方の行の末尾のセルが他方の行の先頭のセルと連続するようにセルのアドレスを管理する、アドレス管理手段と、符号化対象セルを、アドレス順に、当該符号化対象セルのアドレスにより決定される所定の相対アドレス位置にある複数の近傍セルに基づき符号化する符号化手段と、を備えたことを特徴としている。
【００１５】
本発明に係る圧縮処理装置の制御方法は、上記課題を解決するために、セルが２次元に配列されている圧縮対象データを、符号化対象セルを順次選択しながら符号化することによって圧縮する圧縮処理装置の制御方法において、上記圧縮対象データでのセルが成す各行では同一方向に連続し、かつ、隣接する各２行では一方の行の末尾のセルが他方の行の先頭のセルと連続するようにセルのアドレスを管理する、アドレス管理ステップと、符号化対象セルを、アドレス順に、当該符号化対象セルのアドレスにより決定される所定の相対アドレス位置にある複数の近傍セルに基づき符号化する符号化ステップと、を含むことを特徴としている。
【００１６】
上記構成および上記方法によると、セルを単位とし当該セルが２次元に配列されている圧縮対象データでは、セルが成す各行では同一方向に連続し、かつ、隣接する各２行では一方の行の末尾のセルが他方の行の先頭のセルと連続するようセルのアドレスが管理される。これは、圧縮処理装置において、セルが２次元に配列されているデータを受領するモジュールで、２次元に配列されたデータの受け取り順通りに記憶領域に格納して作成したデータにおいて(ページデータなど)、元の２次元に配列されたデータのセルが、各行では同一方向に連続し、かつ、隣接する各２行では一方の行の末尾のセルが他方の行の先頭のセルと連続するようセルのアドレスを管理する、つまり、１次元的に記憶領域上で管理する、ことを利用している。
【００１７】
そして、符号化対象セルを圧縮する際には、符号化対象セルを、アドレス順に、符号化対象セルのアドレスにより決定される所定の相対アドレス位置にある複数の近傍セルに基づいて符号化する。ここで、「所定の相対アドレス位置」とは、符号化対象セルのアドレスに対して、一意に決まるアドレスの位置のことである。具体的に説明すると、例えば、符号化対象セルのアドレスがｎであるとする。そして、近傍セルのアドレスは、例えば、ｎ−１、ｎ−２、ｎ−３、ｎ−４、ｎ−（圧縮対象データの１行におけるセル数）＋２、ｎ−（圧縮対象データの１行におけるセル数）＋１、ｎ−（圧縮対象データの１行におけるセル数）、ｎ−（圧縮対象データの１行におけるセル数）−１、ｎ−（圧縮対象データの１行におけるセル数）−２、ｎ−（圧縮対象データの１行におけるセル数）−３、で求められるものとする。圧縮対象データの１行におけるセル数は、圧縮対象データで一つに決まっている。この場合、ｎとは別のアドレスの符号化対象セルであっても、そのアドレスを上記ｎに当てはめることで、別のアドレスの符号化対象セルの近傍セルのアドレスを求めることができる。このように、符号化対象セルがどのアドレスを有するセルであっても、常に同じ計算により求まるセルを、当該符号化対象セルのアドレスにより決定される所定の相対アドレス位置にある近傍セル、という。
【００１８】
従来では、ＪＢＩＧ圧縮での２ラインテンプレートを使用するように、符号化対象セルの相対位置にある近傍セルを用いて符号化する場合には、圧縮対象データの例えば右端を越えてアクセスを行う場合があったので、画像データの左右に空白のセルが必要であった。この場合、画像データに対して、空白セルを追加しようとすると、一度受け取った画像データをコピーしながら空白セルを追加していくか、もしくは、受け取るときに１ラインずつデータを受け取り空白セルを追加しなければならない。空白セルを追加するためには、最初に画像データを記憶領域に格納する際に行わなければならず、圧縮を行うモジュール単独で行うことはできない。
【００１９】
しかし、本発明では、空白セルが不要である。そして、本発明の上記構成および上記方法では、近傍セルに基づいて符号化を行う際に、符号化対象セルのアドレスに基づき決定される所定の相対アドレス位置にある複数の近傍セルを読み出すので、近傍セルが画像データからはみ出すようなことはない。これは、本発明では、例えば、セルを単位とし当該セルが２次元に配列されている圧縮対象データにおける右端のセルのアドレスは、次の行の先頭である左端のセルのアドレスに連続して管理される。そのため、セルが２次元に配列された圧縮対象データにおいて、近傍セルとしてアクセスする部分が圧縮対象データの右端のセルよりはみ出す場合には、はみ出してアクセスしようとしている行より一つ下の行の左端にあるセルにアクセスして、近傍セルとして読み出することができる。そのため、圧縮対象データが格納されるだけの少ない記憶容量でも、不正なアクセスを行ったり、本来の圧縮結果とは異なる圧縮結果になってしまうといった、不具合は発生しない。
【００２０】
このように、本発明の上記構成および上記方法によると、符号化に使用する記憶容量を削減できるとともに、空白セルを符号化しないように空白セルを読み飛ばす処理が不要となるため、その分の高速化を図ることができる。
【００２１】
また、従来で、２次元データを一筆書きにして空間充填走査をして１次元データに変換してから符号化を行う場合には、走査に時間がかかり、また、空間充填走査を行ってできた１次元データを格納するメモリ領域が必要であった。その上、空間充填走査によって作られた１次元データ上では、近傍セルの決定に複雑な計算が必要であった。これは、一筆書きの空間充填走査によって作られた１次元データ上で、ＪＢＩＧの２ラインテンプレートのような固定された近傍形の参照を行おうとした場合には、元の２次元画像データにおいて画像端であることを認識する必要があったからである。
【００２２】
しかし、上記本発明によると、符号化には、符号化対象セルに対して上記のように、符号化対象セルのアドレスに基づき決定される所定の相対アドレス位置にある複数の近傍セルを用いるだけでよく、元のセルを単位として当該セルが２次元に配列されている圧縮対象データにおける符号化対象セルの位置を認識して、位置毎にセルのアドレスを求める計算を変える、といった必要はない。よって、近傍セルのアドレスを容易に求めることができ近傍セルの読み出しが容易になる。また、空間充填走査も必要ない。そのため、これらの分、圧縮処理の高速化を図ることができる。本発明においては、一筆書きでの空間充填走査を行う必要が無く、また、空間充填走査を行ってできた１次元データを格納する必要も無く、圧縮モジュールのみで対応することができる。
【００２３】
以上のように、上記構成および上記方法によると、セルを単位とし当該セルが２次元に配列されている圧縮対象データを圧縮する際に、圧縮対象データの左右端において近傍セルが圧縮対象データ外にはみ出すかどうかの判定をする必要もなければ、画像データの左右端どちらにも空白セル領域を設ける必要もない。そのため、このような操作の必要がなく、与えられたセルを単位とし当該セルが２次元に配列されているデータをそのまま圧縮することが可能である。よって、少ない記憶容量で、高速で圧縮処理することができる。
【００２４】
本発明に係る圧縮処理装置では、上記構成に加え、空白セルからなる空白データに続けて上記圧縮対象データを記録領域に格納するデータ格納手段を備え、上記アドレス管理手段は、空白データの各セルが連続し、かつ、空白データの末尾のセルが上記圧縮対象データの先頭のセルに続くようにセルのアドレスを管理してもよい。
【００２５】
上記構成によると、圧縮対象データの前に、空白セルよりなる空白データが記憶領域に格納される。このとき、空白データは、各セルが連続し、かつ、空白データの末尾のセルが圧縮対象データの先頭のセルと連続するように、アドレスが管理される。そのため、圧縮対象データの最上部の行を成すセルを符号化するときに、近傍セルが空白セルを超えた外にはみ出すことがない。よって、圧縮対象データの最上部の符号化対象セルであっても、容易に近傍セルの取得を行いこの近傍セルに基づき符号化を行うことができ、特殊な処理をする必要がない。
【００２６】
本発明に係る圧縮処理装置では、上記構成に加え、上記データ格納手段は、上記符号化手段が、上記圧縮対象データにおける最初に符号化する符号化対象セルの符号化に用いる近傍セルを確保できる数だけ、上記空白セルを格納してもよい。
【００２７】
上記構成によると、空白セルの数が、上記符号化手段が上記圧縮対象データにおける最初に符号化する符号化対象セルの符号化に用いる近傍セルを確保できる数だけ、あるということは、符号化時に少なくとも１度は読み出される空白セルのみがあるということである。そのため、符号化に必要な記憶容量だけを最小限に留めて記憶領域に格納することができる。よって、符号化に使用する記憶容量を抑えることができる。
【００２８】
本発明に係る圧縮処理装置では、上記構成に加え、上記圧縮対象データは画像データであり、上記アドレス管理手段は、上記セルとして当該画像データの画素のアドレスを管理してもよい。
【００２９】
上記構成によると、画素からなる画像データを、各行では同一方向に連続し、かつ、隣接する各２行では一方の行の末尾の画素が他方の行の先頭の画素と連続するよう画素のアドレスを管理し、符号化対象画素を、アドレス順に、それぞれ、符号化対象画素のアドレスに基づき決定される所定の相対アドレス位置にある複数の近傍画素を参照に符号化して、画像データを圧縮する。よって、少ない記憶容量で高速に画像データを圧縮することができる。
【００３０】
ここで、セルは、１画素に対応するのではなく、例えば２画素に対応してもよい。もちろん、圧縮対象データは、画像データに限定されず、セルを単位とし当該セルが２次元に配列されているデータであれば、どのようなものであってもかまわない。また、セルは、圧縮対象データを符号化対象の単位に分けられるものであればどのようなものであってもかまわない。
【００３１】
また、本発明に係る圧縮処理装置は、コンピュータによって実現してもよく、この場合には、コンピュータを上記圧縮処理装置における上記各手段として動作させることにより上記圧縮処理装置をコンピュータにて実現させる圧縮処理装置制御プログラム、及びその圧縮処理装置制御プログラムを記録したコンピュータ読み取り可能な記録媒体も、本発明の範疇に入る。
【００３２】
これらの構成によれば、圧縮処理装置制御プログラムを、コンピュータに読み取り実行させることによって、上記圧縮処理装置と同一の作用効果を実現することができる。
【発明の効果】
【００３３】
本発明に係る圧縮処理装置は、以上のように、上記圧縮対象データでのセルが成す各行では同一方向に連続し、かつ、隣接する各２行では一方の行の末尾のセルが他方の行の先頭のセルと連続するようにセルのアドレスを管理する、アドレス管理手段と、符号化対象セルを、アドレス順に、当該符号化対象セルのアドレスに基づき決定される所定の相対アドレス位置にある複数の近傍セルを用いて符号化する符号化手段とを備えている。
【００３４】
上記構成によると、セルを単位とし当該セルが２次元に配列されている圧縮対象データでは、セルが成す各行では同一方向に連続し、かつ、隣接する各２行では一方の行の末尾のセルが他方の行の先頭のセルと連続するようセルのアドレスが管理される。これは、圧縮処理装置において、セルが２次元に配列されているデータを受領するモジュールで、２次元に配列されたデータの受け取り順通りに記憶領域に格納して作成したデータにおいて(ページデータなど)、元の２次元に配列されたデータのセルが、各行では同一方向に連続し、かつ、隣接する各２行では一方の行の末尾のセルが他方の行の先頭のセルと連続するようセルのアドレスを管理する、つまり、１次元的に記憶領域上で管理する、ことを利用している。
【００３５】
そして、符号化対象セルを圧縮する際には、符号化対象セルを、アドレス順に、符号化対象セルのアドレスに基づき決定される所定の相対アドレス位置にある複数の近傍セルに基づいて符号化する。ここで、「所定の相対アドレス位置」とは、符号化対象セルのアドレスに対して、一意に決まるアドレスの位置のことである。このように、符号化対象セルがどのアドレスを有するセルであっても、常に同じ計算により求まるセルを、当該符号化対象セルのアドレスにより決定される所定の相対アドレス位置にある近傍セル、という。
【００３６】
上記構成では、空白セルが不要である。そして、上記構成では、近傍セルに基づいて符号化を行う際に、符号化対象セルのアドレスに基づき決定される所定の相対アドレス位置にある複数の近傍セルを読み出すので、近傍セルが画像データからはみ出すようなことはない。これは、本発明の上記構成では、例えば、セルを単位とし当該セルが２次元に配列されている圧縮対象データにおける右端のセルのアドレスは、次の行の先頭である左端のセルのアドレスに連続して管理される。そのため、セルを単位とし当該セルが２次元に配列されている圧縮対象データにおいて、近傍セルとしてアクセスする部分が圧縮対象データの右端のセルよりはみ出す場合には、はみ出してアクセスしようとしている行より一つ下の行の左端にあるセルにアクセスして、近傍セルとして読み出することができる。そのため、圧縮対象データが格納されるだけの少ない記憶容量でも、不正なアクセスを行ったり、本来の圧縮結果とは異なる圧縮結果になってしまうといった、不具合は発生しない。
【００３７】
このように、本発明の上記構成によると、符号化に使用する記憶容量を削減できるとともに、空白セルを符号化しないように空白セルを読み飛ばす処理が不要となるため、その分の高速化を図ることができる。
【００３８】
また、本発明の上記構成によると、符号化には、符号化対象セルに対して上記のように、符号化対象セルのアドレスに基づき決定される所定の相対アドレス位置にある複数の近傍セルを用いるだけでよく、元のセルを単位として当該セルが２次元に配列されている圧縮対象データにおける符号化対象セルの位置を認識して、位置毎にセルのアドレスを求める計算を変える、といった必要はない。よって、近傍セルのアドレスを容易に求めることができ近傍セルの読み出しが容易になる。また、空間充填走査も必要ない。そのため、これらの分、圧縮処理の高速化を図ることができる。本発明においては、一筆書きでの空間充填走査を行う必要が無く、また、空間充填走査を行ってできた１次元データを格納する必要も無く、圧縮モジュールのみで対応することができる。
【００３９】
以上のように、本発明の上記構成によると、セルを単位とし当該セルが２次元に配列されている圧縮対象データを圧縮する際に、圧縮対象データの左右端において近傍セルが圧縮対象データ外にはみ出すかどうかの判定をする必要もなければ、画像データの左右端どちらにも空白セル領域を設ける必要もない。そのため、このような操作の必要がなく、与えられたセルを単位とし当該セルが２次元に配列されているデータをそのまま圧縮することが可能である。よって、少ない記憶容量で、高速で圧縮処理することができる。
【発明を実施するための最良の形態】
【００４０】
本発明の一実施形態について図１〜図１０に基づいて説明すると以下の通りである。
【００４１】
本実施形態の圧縮処理装置１は、２次元で示される画像データ（圧縮対象データ）について、各セル（画素）を算術符号化することで、圧縮し、それによって得られた圧縮画像データ（符号化データ）を出力する。ここで、セルは、１画素に対応するのではなく、例えば２画素に対応してもよい。もちろん、圧縮対象データは、２次元画像データに限定されず、セルを単位とし当該セルが２次元に配列されているデータであれば、どのようなものであってもかまわない。また、セルは、圧縮対象データを符号化対象の単位に分けられるものであればどのようなものであってもかまわない。
【００４２】
圧縮処理装置１は、符号化対象セルを、コンテクストを成す近傍セルを参照して（読み出して）符号化を行う。読み出す近傍セルの決定については、後段に詳細に説明する。本実施形態の圧縮処理装置１における圧縮処理では、算術符号化が行われる。算術符号化では、符号化結果を０から１までの少数で表す。優勢確率シンボルとは、符号化対象セルの近傍形から予測されるシンボルであり、劣勢確率シンボルとは、予測結果と異なるシンボルである。図８に示すように０から１までの領域を最初のインターバルとして優勢確率シンボルの出現確率（MPS出現確率）と劣勢確率シンボルの出現確率（LPS出現確率）とに分け、優勢確率シンボルが出現した場合には、MPSの出現確率を次のインターバルとし、劣勢確率シンボルが出現した場合にはLPSの出現確率を次のインターバルとする操作を繰り返す。全ての入力ビットに対してこの操作が完了したときの優勢確率シンボルの出現確率の下端が圧縮結果となる。
【００４３】
圧縮処理装置１は、図１に示すように、データ格納部（アドレス管理手段、データ格納手段）２、メモリ（記憶領域）３、コンテクスト生成部２２、取得部２３、算術符号部（符号化手段）２４、記録部２５、およびレジスタ２６を備えている。
【００４４】
データ格納部２は、圧縮処理装置１に画像データ（２次元画像データ）が入力されると、メモリ３に２次元画像データを格納する。このとき、元の２次元画像データのセルが成す各行では同一方向に連続し、かつ、隣接する各２行では一方の行の末尾のセルが他方の行の先頭のセルと連続するようにセルのアドレスを管理する。これは、２次元画像データを、連続したアドレスを持つ１次元的なメモリに格納したということになる。なお、本実施形態では、セルは２次元画像データの画素に対応させる。セルは、１画素に対応するのではなく、例えば２画素に対応させてもかまわない。また、データ格納部２は、入力されてメモリ３格納するデータだけでなく、元々圧縮処理装置１内にある圧縮対象データについても上記のようにアドレスを管理する。
【００４５】
また、データ格納部２は、空白セルからなる空白データを、画像データの前にメモリ３に格納する。そして、空白データの各セルが連続し、かつ、空白データの末尾のセルが上記圧縮対象データの先頭のセルに続くようにセルのアドレスを管理する。
【００４６】
このように空白セルを格納すると、２次元画像の最上部の行を成すセルを符号化するときに、近傍セルが空白セルを超えた外にはみ出すことがない。よって、２次元画像の最上部であっても、容易に近傍セルの取得を行うことができ、特殊な処理をする必要なく、符号化を行うことができる。なお、２次元画像の横ライン１行目のみ、従来と同様に近傍セルを空白とみなす処理を行うのであれば、空白セルを用意する必要はない。
【００４７】
このように格納された画像データの状態を図２に示す。図２においてＸと書かれたセルには画像データが格納されており、０と書かれたセルは空白セルである。このとき追加された空白セル領域は圧縮結果には影響しない。図２では「？」には空白セルを用意してもしなくてもよい。図２の「？」に空白セルを用意せずに、下記の算術符号部２４が、２次元画像データにおける最初に符号化する符号化対象セルの符号化に用いる近傍セルを確保できる数だけ、空白セルをメモリに格納すると、符号化時に少なくとも１度は読み出される空白セルのみ用意されるということになる。そのため、符号化に必要な記憶容量だけを最小限に留めて確保することができる。よって、符号化に使用する記憶容量を抑えることができる。
【００４８】
次にデータ格納部２のアドレスを管理について説明する。２次元画像データにおいて、各行では同一方向に連続し、かつ、隣接する各２行では一方の行の末尾のセルが他方の行の先頭のセルと連続するように、アドレスを管理する。これを具体例を用いて説明する。
【００４９】
例えば、図３（ａ）に示す２次元画像データがあるとする。ここで、図３（ａ）の四角いマス目ひとつひとつがセルである。また、１つの行は、図３（ａ）の横ラインであり、右から左への連続したセル、つまり、白抜きの矢印で表されるセルに対応している。データ格納部２は、図３（ｂ）に示すように、図３（ａ）に示す２次元画像データにおける１つ目の行（ライン１）のセルが左から右に順に並ぶように、かつ、その次に、次の行（ライン２）のセルが左から右に順に並ぶようにアドレスを管理する。３つ目の行以降も同様である。このように、各行では同一方向に連続し、かつ、ある行の右端のセルに続けて、次の行の左端のセルが連続するように、アドレスを管理する。なお、図３（ａ）では、横ラインは４セルからなるが、図３（ｂ）では１ラインが７セルからなっている。２次元に配列されたデータが、各行では同一方向に連続し、かつ、隣接する各２行では一方の行の末尾のセルが他方の行の先頭のセルと連続するようセルのアドレスがなっている。
【００５０】
メモリ３は、入力された画像データを格納する記憶手段である。
【００５１】
コンテクスト生成部２２は、メモリ３に格納された画像データから、符号化対象となる画素（符号化対象セル）およびその周辺（近傍）の複数の画素の配列であるコンテクスト（近傍セル）を抽出する。圧縮処理装置１では、予測の際に、前回の入力信号までの入力ビット列だけでなく、近傍セルの状態をも用いるようになっている。すなわち、圧縮処理装置１は、予測の際に、周辺の複数の近傍セルがとりうる状態の組み合わせそれぞれに対して、優勢確率シンボルおよび劣勢シンボルの出現確率を推定する機能を持つ。
【００５２】
コンテクスト生成部２２は、符号化対象セルを選択して読み取る。この符号化対象セルの選択は、メモリ３に格納されている画像データの各セルのアドレスの順に順次行う。また、コンテクスト生成部２２は、入力された画像データから、対象セルの近傍セルであるコンテクストを読み取る。このコンテクストの読み取りの際には、アドレスが上記のように管理されて格納された画像データにおいて、符号化対象セルのアドレスにより決定される所定の相対アドレス位置にある複数の近傍セルを読み取る。
【００５３】
ここで、「所定の相対アドレス位置」とは、符号化対象セルのアドレスに対して、一意に決まるアドレスの位置のことである。具体的に説明すると、例えば、符号化対象セルのアドレスがｎであるとする。近傍セルのアドレスは、ｎ−１、ｎ−２、ｎ−３、ｎ−４、ｎ−（圧縮対象データの１行におけるセル数）＋２、ｎ−（圧縮対象データの１行におけるセル数）＋１、ｎ−（圧縮対象データの１行におけるセル数）、ｎ−（圧縮対象データの１行におけるセル数）−１、ｎ−（圧縮対象データの１行におけるセル数）−２、ｎ−（圧縮対象データの１行におけるセル数）−３、で求められる。ここで、２次元画像データの１行におけるセル数は、２次元画像データで一つに決まっているものである。この場合、ｎとは別のアドレスの符号化対象セルであっても、そのアドレスを上記ｎに当てはめることで、別のアドレスの符号化対象セルの近傍セルのアドレスを求めることができる。このように、符号化対象セルがどのアドレスを有するセルであっても、常に同じ計算により求まるセルを、当該符号化対象セルに対して所定の相対アドレス位置にある近傍セル、という。
【００５４】
よって、図５に示すように、対象セルが、例えば、元の２次元画像データの右端にある場合（図５（ａ））でも、左端から４セル目にある場合（図５（ｂ））、あるいは画像の上端にある場合（図５（ｃ））でも、対象セルのアドレスをｎとすると、近傍セルのアドレスは、ｎ−１、ｎ−２、ｎ−３、ｎ−４、ｎ−（圧縮対象データの１行におけるセル数＝８）＋２、ｎ−８＋１、ｎ−８、ｎ−８−１、ｎ−８−２、ｎ−８−３、で、全て求められる。
【００５５】
そして、コンテクスト生成部２２は、抽出した符号化対象セルおよびコンテクストを成す近傍セルを取得部２３に出力する。また、コンテクスト生成部２２は、算術符号部２４の符号処理部２９からのセルインクリメント指示を受信すると、メモリに格納された画像データから、次の符号化対象セルおよびコンテクストを抽出する。
【００５６】
次に、取得部２３について説明する。取得部２３は、予測値としての優勢確率シンボル（ＭＰＳ）を、周辺画素の配列（コンテクスト）に対する優勢確率シンボルを記録した記録部２５の確率推定テーブル２７から取得する。
【００５７】
ここで、確率推定テーブル２７は、図６に示すように、コンテクストと、そのコンテクストから予想されるＭＰＳの値との関係を含んでいる。また、確率推定テーブル２７は、コンテクストと、このコンテクストに応じたＬＰＳインターバルの推定値（ＬＳＺ）のインデックスＳＴとの関係も含んでいる。ＬＳＺについては後述する。取得部２３は、入力されるコンテクストを用いて、記録部２５の確率推定テーブル２７にアクセスして、インデックスＳＴを得る。取得部２３は、ＭＰＳとインデックスＳＴとを得ると、画素の値（入力ビットの値；入力シンボル）、ＭＰＳ、インデックスＳＴを算術符号部２４に出力する。以上のように、符号化対象画素（符号化対象セル、符号化対象のビットに対応する画素）の近傍画素（近傍セル、コンテクスト）の値から符号化対象のビット（シンボル）のＬＰＳインターバル（この場合にはＬＰＳインターバルの推定値）を推定する推定ステップが、取得部２３と確率推定テーブル２７とによって実行される。すなわち、取得部２３および確率推定テーブル７は、上記推定ステップを実行する推定部として機能する。
【００５８】
算術符号部２４は、入力される画素の値、ＭＰＳ、インデックスＳＴから、符号化データである実数ｘを生成する。この算術符号部２４は、符号処理部２９および前処理部３０を含んでいる。
【００５９】
符号処理部２９は、前処理部３０から入力される選択信号に応じて、各処理部２９ａ〜２９ｃのうちから適切な処理部を選択する。また入力された画素の値、ＭＰＳ、ＳＴを用いて、選択した処理部によって符号化データを生成する。符号処理部２９は、優勢確率シンボルの符号化を行うＭＰＳ処理部９ａ、劣勢確率シンボルの符号化を行うＬＰＳ処理部９ｂ、正規化処理を実行するＲＥＮＯＲＭ処理部９ｃを含んでいる。
【００６０】
前処理部３０は、取得部２３から入力される画素の値、ＭＰＳ、ＳＴに応じて、選択信号を生成して、符号処理部２９に出力する。前処理部３０は、選択部３０ａを含んでいる。
【００６１】
選択部３０ａは、選択信号を生成するために、入力される画素の値（符号化対象のシンボル）と、そのコンテクストから予想されるＭＰＳとを比較し、符号化対象のシンボルが優勢確率シンボルか劣勢確率シンボルかを判断する。選択部３０ａは、入力に応じて選択信号を生成して、符号処理部２９に出力する。
【００６２】
記録部２５には、確率推定テーブル２７と確率推定表２８とが記録されている。なお、確率推定テーブル２７と確率推定表２８とは、全く別のものである。テーブルは表とも訳し得るが、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）にて符号化対象セルについての符号化を行い、１つのストライプにおける全ての画素の処理が完了すると１つのストライプの処理が完了したことになる。次に、Ｓ１５２〜Ｓ１６４の処理について説明する。
【００７４】
Ｓ１５２で、コンテクスト生成部２２は、セルのアドレスを管理されてメモリ３に格納された画像データから、符号化対象セル（対象セル）を選択する。この符号化対象セルの選択は、アドレスに従って順次行われる。また、Ｓ１５２ではコンテクスト生成部２２は、セルのアドレスを管理されてメモリ３に格納された画像データから、近傍セル（コンテクスト）を読み取る。この近傍セルは、符号化対象セルに対して所定の相対アドレス位置にあるものである。よって、符号化対象セルがどのアドレスを有するセルであっても、常に同じ計算により、当該符号化セルに対する近傍セルのアドレスが決まる。そして、取得部２３に送信する（Ｓ１５２）。また、コンテクスト生成部２２は、読み取った対象セルと近傍セルとを取得部２３に送信する。本実施形態の圧縮処理では、Ｓ１５２では、図１０（ｂ）で示すように、単に対象セルと近傍セルとを読み取ればよい。しかし、従来の圧縮処理では、図１３に示したように、近傍セルが画像からはみ出すか否かを判断してからそれぞれの処理を行う必要があった。
【００７５】
Ｓ１５３では、取得部２３が、コンテクスト生成部２２から送信された対象セルおよびコンテクストに応じて、記録部２５の確率推定テーブル２７にアクセスして、コンテクストについての優勢確率シンボルおよび劣勢確率シンボルの確率推定値のインデックス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の値が１か否かによって、入れ替えを行うかどうかを判断する。Ｓ１６１では、ＬＰＳ処理部２９ｂは、記録部２５の確率推定表２８を更新し、Ｓ１６２に進む。
【００７９】
Ｓ１６２では、符号処理部２９がコンテクスト生成部２２に対してセルインクリメントの指示を行い、セルについてのループを終了する。このような手順をストライプの全てのセルに対して行うことで、ストライプの圧縮を行う。Ｓ１６３では、ストライプについての処理が終了したか否かを判別し、終了していた場合にはレジスタ２６から符号化データを出力する（フラッシュ処理：Ｓ１６３）。このように、次のストライプの圧縮に進む前に、ここまでの圧縮結果のうちで、まだ出力されていない部分を出力する。Ｓ１６４では、コンテクスト生成部２２が新たなストライプを選択する。全てのストライプの圧縮が完了すれば画像全体の圧縮が完了したことになり、入力画像データの全てを符号化した場合には、処理を終了する。
【００８０】
圧縮処理装置１は、上記した構成を備えており、データ格納部２は、元の２次元画像データのセル（画素）がなす各行では同一方向に連続し、かつ、隣接する各２行では一方の行の末尾のセル（画素）が他方の行の先頭のセル（画素）と連続するようセル（画素）のアドレスを管理する。また、算術符号部２４は、符号化対象セルを、上記アドレス順に、当該符号化対象セルにより決定される所定の相対アドレス位置にある複数の近傍セルに基づいて符号化する。
【００８１】
圧縮処理装置１では、メモリ３には、元の２次元画像データのセルが成す各行では同一方向に連続し、かつ、隣接する各２行では一方の行の末尾のセルが他方の行の先頭のセルと連続するようセルのアドレスが管理されて、圧縮対象データが格納される。これは、圧縮処理装置において、２次元画像データを受領するモジュールで、２次元画像データの受け取り順通りに記憶領域に格納して作成したデータにおいて(ページデータなど)、２次元画像データのセルが成す各行では同一方向に連続し、かつ、隣接する各２行では一方の行の末尾のセルが他方の行の先頭のセルと連続するようセルのアドレスがなっている、つまり、１次元的にメモリ３上に格納される、ことを利用している。
【００８２】
そして、符号化対象セルを圧縮する際には、アドレスが管理されている２次元画像データの符号化対象セルに対して、アドレス順に、符号化対象セルのアドレスにより決定される所定の相対アドレス位置にある複数の近傍セルに基づいた符号化が行われる。ここで、「所定の相対アドレス位置」とは、符号化対象セルのアドレスに対して一意に決まるアドレスの位置のことである。つまり、どのようなアドレスの符号化対象セルでに対しても、同じ計算によりアドレスが決まるセルを、符号化対象セルのアドレスにより決定される所定の相対アドレス位置にある近傍セル、という。
【００８３】
また圧縮処理装置１では、上記のように空白セルが不要である。そして、圧縮処理装置１では、近傍セルに基づいて符号化を行う際に、所定の相対アドレス位置にある複数の近傍セルを読み出すので、近傍セルが画像データからはみ出すようなことはない。これは、圧縮処理装置１では、例えば、セルを単位とし当該セルが２次元に配列されている２次元画像データにおける右端のセルのアドレスは、次の行の先頭である左端のセルのアドレスに連続して管理されている。そのため、セルを単位とし当該セルにより２次に配列されている２次元画像データにおいて、近傍セルとしてアクセスする部分が圧縮対象データの右端のセルよりはみ出す場合には、はみ出してアクセスしようとしている行より一つ下の行の左端にあるセルにアクセスして、近傍セルとして読み出することができる。そのため、圧縮対象データが格納されるだけの少ない記憶容量でも、記憶領域に対して不正なアクセスを行ったり、本来の圧縮結果とは異なる圧縮結果になってしまうといった、不具合は発生しない。このように、本発明の上記構成および上記方法によると、記憶容量を削減できるとともに、空白セルを符号化しないように空白セルを読み飛ばす処理が不要となるため、その分の高速化を図ることができる。
【００８４】
また圧縮処理装置１では、符号化には、符号化対象セルに対して上記のような符号化対象セルのアドレスにより決定される所定の相対アドレス位置にある複数の近傍セルを用いるだけでよく、元のセル単位で２次元に配列された圧縮対象データにおける符号化対象セルの位置を認識して、位置毎にセルのアドレスを求める計算を変える、といった必要はない。よって、近傍セルのアドレスを容易に求めることができ近傍セルの読み出しが容易である。また、空間充填走査も必要ない。そのため、これらの分、圧縮処理の高速化を図ることができる。本発明においては、一筆書きでの空間充填走査を行う必要が無く、また、空間充填走査を行う必要がないので、空間充填走査を行ってできた１次元データを格納する必要もなく、圧縮モジュールのみで対応することができる。
【００８５】
以上のように、圧縮処理装置１によると、セルを単位とし当該セルが２次元に配列されている２次元画像データを圧縮する際に、２次元画像データの左右端において近傍セルが画像データ外にはみ出すかどうかの判定をする必要もなければ、２次元画像データの左右端どちらにも空白セル領域を設ける必要もない。そのため、このような操作の必要がなく、与えられた２次元画像データをそのまま圧縮することが可能である。よって、少ない記憶容量で、高速で圧縮処理することができる。
【００８６】
なお、本実施形態では圧縮処理装置１を上記のように、２値画像データをマルコフ情報源でモデル化し、符号化シンボルをその周辺画素の状態によって予測し、予測結果に応じて算術符号化する方式を用いるものとして説明した。しかし、本発明は、セルを単位として２次元に配列されたデータに対して、符号化対象セルの近傍から予測される値と符号化対象セルの値との差分を圧縮するようなあらゆる圧縮形式に適用することができる。このように、本発明は上述した実施形態に限定されるものではなく、請求項に示した範囲で種々の変更が可能である。すなわち、請求項に示した範囲で適宜変更した技術的手段を組み合わせて得られる実施形態についても本発明の技術的範囲に含まれる。
【００８７】
また、圧縮処理装置１の各ブロックは、ハードウェアロジックによって構成してもよいし、次のようにＣＰＵを用いてソフトウェアによって実現してもよい。
【００８８】
すなわち、圧縮処理装置１は、各機能を実現する制御プログラムの命令を実行するＣＰＵ（central processing unit）、上記プログラムを格納したＲＯＭ（read only memory）、上記プログラムを展開するＲＡＭ（random access memory）、上記プログラムおよび各種データを格納するメモリ等の記憶装置（記録媒体）などを備えている。そして、本発明の目的は、上述した機能を実現するソフトウェアである圧縮処理装置１の制御プログラムのプログラムコード（実行形式プログラム、中間コードプログラム、ソースプログラム）をコンピュータで読み取り可能に記録した記録媒体を、上記圧縮処理装置１に供給し、そのコンピュータ（またはＣＰＵやＭＰＵ）が記録媒体に記録されているプログラムコードを読み出し実行することによっても、達成可能である。
【００８９】
上記記録媒体としては、例えば、磁気テープやカセットテープ等のテープ系、フロッピー（登録商標）ディスク／ハードディスク等の磁気ディスクやＣＤ−ＲＯＭ／ＭＯ／ＭＤ／ＤＶＤ／ＣＤ−Ｒ等の光ディスクを含むディスク系、ＩＣカード（メモリカードを含む）／光カード等のカード系、あるいはマスクＲＯＭ／ＥＰＲＯＭ／ＥＥＰＲＯＭ／フラッシュＲＯＭ等の半導体メモリ系などを用いることができる。
【００９０】
また、圧縮処理装置１を通信ネットワークと接続可能に構成し、上記プログラムコードを通信ネットワークを介して供給してもよい。この通信ネットワークとしては、特に限定されず、例えば、インターネット、イントラネット、エキストラネット、ＬＡＮ、ＩＳＤＮ、ＶＡＮ、ＣＡＴＶ通信網、仮想専用網（virtual private network）、電話回線網、移動体通信網、衛星通信網等が利用可能である。また、通信ネットワークを構成する伝送媒体としては、特に限定されず、例えば、ＩＥＥＥ１３９４、ＵＳＢ、電力線搬送、ケーブルＴＶ回線、電話線、ＡＤＳＬ回線等の有線でも、ＩｒＤＡやリモコンのような赤外線、Ｂｌｕｅｔｏｏｔｈ（登録商標）、８０２．１１無線、ＨＤＲ、携帯電話網、衛星回線、地上波ディジタル網等の無線でも利用可能である。なお、本発明は、上記プログラムコードが電子的な伝送で具現化された、搬送波に埋め込まれたコンピュータデータ信号の形態でも実現され得る。
【００９１】
なお、本発明は、以下に記す画像圧縮方法として表現してもよい。すなわち、圧縮対象となる画素の近傍画素を参照しながら２次元画像を圧縮する方法であって、前記２次元画像のデータを連続したアドレスを持つ１次元的な記憶領域に格納し、画像の左端部分又は右端部分の画素を圧縮する際に、前記２次元画像における反対側の端部分にある画素を前記近傍画素として参照して圧縮を行なう画像圧縮方法、と表現してもよい。
【００９２】
また、上記画像圧縮方法では、さらに、２次元画像のデータを連続したアドレスを持つ１次元的な記憶領域に格納する際に、空白データに続いて２次元画像を格納してもよい。
【００９３】
また、上記画像圧縮方法では、さらに、２次元画像のデータを連続したアドレスを持つ１次元的な記憶領域に格納する際に、２次元画像の前に確保する空白データの領域の大きさは前記２次元画像の横1ライン分に画素３つ分のデータを加えたものであってもよい。
【産業上の利用可能性】
【００９４】
本発明は、２次元に配列されたデータの圧縮に利用することができ、例えば、ファクシミリ装置（ＦＡＸ）やプリンタ、パーソナルコンピュータのプリンタドライバ等における画像データの圧縮に有効である。
【図面の簡単な説明】
【００９５】
【図１】本実施形態の圧縮処理装置の要部構成を示すブロック図である。
【図２】上記圧縮処理装置における記憶領域の状態を示す図である。
【図３】（ａ）は２次元画像データの図であり、（ｂ）は上記圧縮処理装置における各セルのアドレスの管理を説明するための図である。
【図４】（ａ）は２次元画像データにおける符号化対象セルと近傍セルの位置を現す図であり、（ｂ）は上記圧縮処理装置が管理する同図（ａ）の符号化対象セルと近傍セルの１次元でのアドレスを説明する図である。
【図５】（ａ）〜（ｃ）は、上記圧縮処理装置にて、読み出す近傍セルを説明する図である。
【図６】上記圧縮処理装置にて用いる確率推定テーブルの一例を示す図である。
【図７】（ａ）は上記圧縮処理装置にて用いる確率推定表の一例の一部を示す図であり、（ｂ）は、確率推定表の他の一部を示す図である。
【図８】上記圧縮処理装置にて行う算術符号化を説明するための概念図である。
【図９】上記圧縮処理装置にて行う符号化処理の動作を示すフローチャートである。
【図１０】（ａ）、（ｂ）は図９のフォローチャートにおける処理の一部を説明する図である。
【図１１】テンプレートを説明するための図である。
【図１２】従来の通常の圧縮処理装置における、テンプレートの指定する領域を示す図である。
【図１３】従来の通常の圧縮処理装置における、近傍セルの読み出しの処理の流れを示す図である。
【図１４】データの両側に空白セル領域を設けた従来の圧縮処理装置における、テンプレートの指定する領域を示す図である。
【図１５】従来の空間充填走査を用いた圧縮処理での空間充填走査の処理の流れを示す図である。
【図１６】（ａ）は２次元画像データの図であり、（ｂ）は従来の空間充填走査を用いた圧縮処理における各セルのアドレスの管理を説明するための図である。
【図１７】（ａ）は２次元画像データにおける符号化対象セルと近傍セルの位置を現す図であり、（ｂ）は従来の空間充填走査を用いた圧縮処理における同図（ａ）の符号化対象セルと近傍セルの１次元でのアドレスを説明する図であり、（ｃ）は２次元画像データにおける符号化対象セルと近傍セルの位置を現す図であり、（ｄ）は従来の空間充填走査を用いた圧縮処理における同図（ｄ）の符号化対象セルと近傍セルの１次元でのアドレスを説明する図である。
【符号の説明】
【００９６】
１      圧縮処理装置
２      データ格納部（アドレス管理手段、データ格納手段）
３      メモリ（記憶領域）
２２    コンテクスト生成部
２３    取得部
２４    算術符号部（符号化手段）
２５    記録部
２６    レジスタ
２６ａ  Ｃｒｅｇ
２６ｂ  Ｃｒｅｇ
２７    確率推定テーブル
２８    確率推定表
２９    符号化処理部
２９ａ  ＭＰＳ処理部
２９ｂ  ＬＰＳ処理部
３０    前処理部
３０ａ  選択部
【図１】
0004722681.tif 000002
【図２】
0004722681.tif 000003
【図３】
0004722681.tif 000004
【図４】
0004722681.tif 000005
【図５】
0004722681.tif 000006
【図６】
0004722681.tif 000007
【図７】
0004722681.tif 000008
【図８】
0004722681.tif 000009
【図９】
0004722681.tif 000010
【図１０】
0004722681.tif 000011
【図１１】
0004722681.tif 000012
【図１２】
0004722681.tif 000013
【図１３】
0004722681.tif 000014
【図１４】
0004722681.tif 000015
【図１５】
0004722681.tif 000016
【図１６】
0004722681.tif 000017
【図１７】
0004722681.tif 000018