(57)【要約】【課題】二値画像の可逆圧縮処理において、より良好な圧縮率を実現することが可能な技術を提供する。【解決手段】二値画像を次の方法で圧縮する。具体的には、二値画像を、所定サイズ（例えば４×２画素）の単位画素ブロックＢで区分する。各単位画素ブロックＢは、複数の画素で構成される画素列を副走査方向に有する。そして、この単位画素ブロックＢ内の複数の画素の画素値を所定の順序で読み出す動作を、二値画像において主走査方向に配列された複数の単位画素ブロックについて繰り返すことによって、二値画像における画素値の並べ換えを行い、並べ換えられた画素値の配列に対して所定の可逆圧縮手法を適用して圧縮を行う。また、伸張（解凍）時には、逆の手順で伸張処理および並べ換え処理を行う。【選択図】図７
2005295307.tif 000002
【特許請求の範囲】
【請求項１】
コンピュータに、
(a)二値画像における各単位画素ブロック内の複数の画素の画素値を所定の順序で読み出す動作を、前記二値画像において第１の方向に配列された複数の単位画素ブロックについて繰り返すことによって、前記二値画像における画素値の並べ換えを行う手順と、
(b)前記手順（a)で並べ換えられた画素値の配列に対して、所定の可逆圧縮手法を適用して圧縮を行う手順と、
を含む画像圧縮方法を実行させるためのプログラムであって、
前記単位画素ブロックは、前記第１の方向に直交する第２の方向において、複数の画素で構成される画素列を有することを特徴とするプログラム。
【請求項２】
二値画像を圧縮する画像圧縮方法であって、
(a)二値画像における各単位画素ブロック内の複数の画素の画素値を所定の順序で読み出す動作を、前記二値画像において第１の方向に配列された複数の単位画素ブロックについて繰り返すことによって、前記二値画像における画素値の並べ換えを行うステップと、
(b)前記ステップ（a)で並べ換えられた画素値の配列に対して、所定の可逆圧縮手法を適用して圧縮を行うステップと、
を含み、
前記単位画素ブロックは、前記第１の方向に直交する第２の方向において、複数の画素で構成される画素列を有することを特徴とする画像圧縮方法。
【請求項３】
二値画像を圧縮する画像圧縮装置であって、
二値画像における各単位画素ブロック内の複数の画素の画素値を所定の順序で読み出す動作を、前記二値画像において第１の方向に配列された複数の単位画素ブロックについて繰り返すことによって、前記二値画像における画素値の並べ換えを行う並べ換え手段と、
前記並べ換え手段によって並べ換えられた画素値の配列に対して、所定の可逆圧縮手法を適用して圧縮を行う圧縮手段と、
を備え、
前記単位画素ブロックは、前記第１の方向に直交する第２の方向において、複数の画素で構成される画素列を有することを特徴とする画像圧縮装置。
【請求項４】
所定の可逆圧縮手法で圧縮された二値画像を伸張する画像伸張装置であって、
(a)前記所定の可逆圧縮手法に対応する伸張手法を用いて、前記圧縮された二値画像に対する伸張処理を行い、伸張処理後の画素列を生成する伸張手段と、
(b)前記伸張処理後の画素列を前記二値画像における各単位画素ブロック内の各所定位置に配置して並べ換える動作を繰り返すことによって、前記二値画像において第１の方向に配列された複数の単位画素ブロックを復元する並べ換え手段と、
を備え、
前記単位画素ブロックは、前記第１の方向に直交する第２の方向において、複数の画素で構成される画素列を有することを特徴とする画像伸張装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、二値画像の圧縮技術および伸張技術に関する。
【背景技術】
【０００２】
画像の圧縮処理方式としては、可逆方式（ロスレス）と非可逆方式（ロッシー）とが存在する。
【０００３】
可逆方式は、圧縮された情報を復元する際に、完全に元の情報と同一の情報を得ることができる方式である。可逆方式としては、ランレングス法、ユニバーサル符号化法（ＬＺＳＳ法、ＬＺＷ法）、部分一致予測法、ブロックソーティング法などが知られている。
【０００４】
一方、非可逆方式は、圧縮された情報を復元する際に、完全に元の情報と同一の情報を得ることができない方式である。非可逆方式では、視覚特性を利用して見た目に影響の少ない情報を削減することなどによって、良好な圧縮率が実現される。この非可逆方式としては、ＤＣＴ（離散コサイン変換）等を利用したＪＰＥＧ、ウェーブレット変換等を利用したＪＰＥＧ２０００などが知られている。
【０００５】
これら両方式は、圧縮対象ファイル等の性質に応じて適宜に選択されて用いられる。たとえば、画像圧縮処理においては、圧縮率の点で有利な非可逆方式が用いられることが多い。しかしながら、伸張処理後の復元情報として、圧縮前の情報（元の情報）と完全に一致する情報を得ることが要請される場合には、画像圧縮処理においても可逆方式が用いられる。
【０００６】
ところで、「可逆方式」は、復元時に元の情報と同一の情報を得ることが可能であるという利点がある一方で、非可逆方式に比べて一般的に圧縮の度合いが小さい。
【０００７】
そこで、復元時に元の情報と同一の情報を得ることが可能であるという利点を得つつさらに良好な圧縮率を実現するため、様々な工夫を施した可逆圧縮技術が存在する。
【０００８】
たとえば、対象画像が多値画像の場合に、多値画像固有の特徴を利用してその圧縮度合いをさらに高める技術が存在する（例えば、特許文献１参照）。多値画像では、隣接する画素間の相関が高く、特に各画素値の上位のビット位ほど、隣接する画素間でそのビット値が同一である確率が高いという性質がある。この技術においては、このような性質を利用して、画像圧縮処理を行う前処理として、隣接する画素の同じビット位を連続させるように、多値画像データのビット列を並べ換えることによって、圧縮率を改善することが行われている。
【０００９】
【特許文献１】特開２００１−３０９１８５号公報
【発明の開示】
【発明が解決しようとする課題】
【００１０】
ところで、画像には、各画素の階調値（画素値）を３段階以上の値（たとえば２５６段階）で表現する「多値画像」だけでなく、各画素の階調値を２段階の値（たとえば、「０」および「１」）で表現する「二値画像」も存在する。
【００１１】
そして、このような二値画像を、非可逆方式ではなく可逆方式で圧縮したいという要請も存在する。
【００１２】
しかしながら、上述の技術は、対象画像が多値画像であることを前提としており、多値画像の性質を利用して圧縮率の改善を図るものであるため、二値画像の可逆圧縮を行う際にそのまま適用することができない。
【００１３】
そこで、この発明の課題は、二値画像の可逆圧縮処理において、より良好な圧縮率を実現することが可能な技術を提供することにある。
【課題を解決するための手段】
【００１４】
上記課題を解決すべく、請求項１の発明は、コンピュータに、(a)二値画像における各単位画素ブロック内の複数の画素の画素値を所定の順序で読み出す動作を、前記二値画像において第１の方向に配列された複数の単位画素ブロックについて繰り返すことによって、前記二値画像における画素値の並べ換えを行う手順と、(b)前記手順（a)で並べ換えられた画素値の配列に対して、所定の可逆圧縮手法を適用して圧縮を行う手順とを含む画像圧縮方法を実行させるためのプログラムであって、前記単位画素ブロックは、前記第１の方向に直交する第２の方向において、複数の画素で構成される画素列を有することを特徴とする。
【００１５】
請求項２の発明は、二値画像を圧縮する画像圧縮方法であって、(a)二値画像における各単位画素ブロック内の複数の画素の画素値を所定の順序で読み出す動作を、前記二値画像において第１の方向に配列された複数の単位画素ブロックについて繰り返すことによって、前記二値画像における画素値の並べ換えを行うステップと、(b)前記ステップ（a)で並べ換えられた画素値の配列に対して、所定の可逆圧縮手法を適用して圧縮を行うステップとを含み、前記単位画素ブロックは、前記第１の方向に直交する第２の方向において、複数の画素で構成される画素列を有することを特徴とする。
【００１６】
請求項３の発明は、二値画像を圧縮する画像圧縮装置であって、二値画像における各単位画素ブロック内の複数の画素の画素値を所定の順序で読み出す動作を、前記二値画像において第１の方向に配列された複数の単位画素ブロックについて繰り返すことによって、前記二値画像における画素値の並べ換えを行う並べ換え手段と、前記並べ換え手段によって並べ換えられた画素値の配列に対して、所定の可逆圧縮手法を適用して圧縮を行う圧縮手段と、を備え、前記単位画素ブロックは、前記第１の方向に直交する第２の方向において、複数の画素で構成される画素列を有することを特徴とする。
【００１７】
請求項４の発明は、所定の可逆圧縮手法で圧縮された二値画像を伸張する画像伸張装置であって、(a)前記所定の可逆圧縮手法に対応する伸張手法を用いて、前記圧縮された二値画像に対する伸張処理を行い、伸張処理後の画素列を生成する伸張手段と、(b)前記伸張処理後の画素列を前記二値画像における各単位画素ブロック内の各所定位置に配置して並べ換える動作を繰り返すことによって、前記二値画像において第１の方向に配列された複数の単位画素ブロックを復元する並べ換え手段とを備え、前記単位画素ブロックは、前記第１の方向に直交する第２の方向において、複数の画素で構成される画素列を有することを特徴とする。
【発明の効果】
【００１８】
請求項１から請求項３に記載の発明によれば、二値画像の第２の方向における画素列の規則性を利用して、圧縮率の更なる改善を図ることができる。
【００１９】
請求項４に記載の発明によれば、高効率に圧縮された状態の二値画像を元の状態に復号することが可能である。
【発明を実施するための最良の形態】
【００２０】
以下、本発明の実施形態を図面に基づいて説明する。
【００２１】
＜Ａ．システム構成＞
＜概要＞
図１は、本発明の実施形態に係るプリントシステム１を示す図である。図１に示すように、プリントシステム１は、コントローラ１０とプリンタ２０とを備えている。コントローラ１０とプリンタ２０とは、ＬＡＮなどのネットワークＮＷを介して接続されている。
【００２２】
コントローラ１０は、ユーザによって指定されたファイルについての印刷出力用のデータを作成して、当該データをプリンタ２０に向けてネットワークＮＷを介して送信する機能を有している。
【００２３】
この印刷出力用のデータは、ユーザによって指定されたファイルに基づいて、二値画像を表すデータとして生成される。具体的には、印刷対象のファイルが二値画像ではなく多値画像を含む場合においても、当該多値画像を表現するデータに対してハーフトーン処理等を施す変換処理を経ることによって、二値画像を表現するデータが生成される。また、印刷対象のファイルとしては、画像ファイルに限定されず、文字等を含むファイルであっても良い。これらの文字等を含むファイルは、印刷出力のため、直接若しくは一旦多値画像への変換を経由した後に二値画像に変換される。
【００２４】
二値画像を表す変換後のデータが、後述する圧縮処理での処理対象データとなる。言い換えれば、印刷出力用の二値画像データが圧縮されてプリンタ２０へと送信される。なお、印刷対象ファイルが元々二値画像を表すものである場合には、その二値画像のデータをそのまま圧縮処理の対象データとするようにしてもよい。
【００２５】
また、プリンタ２０は、コントローラ１０から送信されてきたデータに基づいて印刷出力を行う装置である。プリンタ２０は、コントローラ１０からの二値画像のデータ（圧縮データ）に対して伸張処理および並べ換え処理（後述）を施して元のデータを復元し、当該復元されたデータに基づいて印刷出力を行う。
【００２６】
なお、印刷出力は、モノクロ画像であってもよく、カラー画像であってもよい。モノクロ画像を印刷する際には、単一の二値画像データに基づいて印刷出力が行われる。一方、カラー画像を印刷する際には、複数（例えば３つ）の基本色（例えば、Ｙ（イエロー）、Ｍ（マゼンタ）、Ｃ（シアン））毎に生成された二値画像を重ね合わせて出力することによって、カラー画像を印刷出力することができる。以下では、簡単化のためモノクロ画像の印刷について説明するが、カラー画像についても、基本色成分ごとの二値画像に対してそれぞれ圧縮処理を施すことが可能である。
【００２７】
また、後述するように、本システム１において、コントローラ１０は画像圧縮装置として機能し、プリンタ２０は画像伸張装置として機能する。
【００２８】
＜コントローラ１０＞
コントローラ１０は、図１に示すように、ＣＰＵ２と、ＲＡＭ（および／またはＲＯＭ）などの半導体メモリにより構成される主記憶部３ａおよびハードディスクドライブ（ＨＤＤ）などの補助記憶部３ｂを有する記憶部３と、メディアドライブ（ここではＤＶＤドライブ）４と、液晶ディスプレイなどの表示部５と、キーボード６ａおよびマウス６ｂなどの入力部６と、ネットワークカードなどの通信部７とを備えるコンピュータシステム（以下、単に「コンピュータ」とも称する）として構成される。
【００２９】
メディアドライブ４は、ＣＤ−ＲＯＭ、ＤＶＤ（Digital Versatile Disk）、フレキシブルディスク、メモリカードなどの可搬性の記録媒体９からその中に記録されている情報を読み出す。
【００３０】
コントローラ１０は、記録媒体９に記録されたソフトウエアプログラム（以下、単に「プログラム」とも称する）を読み込み、そのプログラムをＣＰＵ２等を用いて実行することによって、各種の機能を実現する。なお、各機能を有するプログラムは、記録媒体９を介して供給される場合に限定されず、ＬＡＮおよびインターネットなどのネットワークを介して、このコンピュータに対して供給されてもよい。
【００３１】
図２は、コントローラ１０におけるソフトウエア構成および機能部ブロックを示す図である。図２（ａ）は、コントローラ１０におけるソフトウエア構成を示し、図２（ｂ）は、コントローラ１０における機能的構成を示している。
【００３２】
図２（ａ）に示すように、コントローラ１０上では、所定のオペレーションシステム（基本ソフトウエア）ＯＳとアプリケーションソフトウエアプログラム（以下、単に「アプリケーションソフト」とも略称する）ＡＳとプリンタドライバＰＤとが動作する。なお、これらのオペレーションシステムＯＳ、アプリケーションソフトＡＳ、およびプリンタドライバＰＤは、各階層でそれぞれ固有の機能を実現するためのプログラムである。
【００３３】
オペレーションシステムＯＳ上で呼び出されたアプリケーションソフトＡＳ（たとえばワードプロセッシングソフトウエア）において、印刷対象のファイルが選択され、そのファイルに対する印刷出力操作が受け付けられると、アプリケーションソフトＡＳはそのファイルに対する印刷出力処理を開始する。そして、アプリケーションソフトＡＳは、プリンタ２０に対応するプリンタドライバＰＤを用いて、プリンタ２０に適合する印刷出力用データを生成し、当該印刷出力用データをプリンタ２０に向けてネットワークを介して送信する。プリンタドライバＰＤ内には、並べ換え処理を含む画像圧縮機能（後述）が実装されており、圧縮された二値画像データ（印刷出力用データ）がコントローラ１０からプリンタ２０へ向けて送信される。
【００３４】
また、図２（ｂ）の機能ブロック図に示すように、コントローラ１０は、並べ換え処理部１１と圧縮部１２と送信部１３とを備えている。並べ換え処理部１１は、二値画像のデータを所定の規則（ルール）に従って並べ換える処理（後に詳述）を行う処理部であり、圧縮部１２は並べ換え後の二値画像のデータを圧縮する処理部である。また、送信部１３は、圧縮状態のデータをコントローラ１０に向けて送信する処理部である。
【００３５】
＜プリンタ２０＞
プリンタ２０は、図１に示すように、受信部２１と伸張部２２と並べ換え処理部２３と出力制御部２４と印刷出力部２５とを備えている。受信部２１は、コントローラ１０から送信されてくる二値画像のデータ（圧縮状態）を受信する処理部である。伸張部２２は、圧縮状態の二値画像のデータを伸張（「解凍」ないし「復号」とも称する）する処理部であり、並べ換え処理部２３は、伸張部２２によって伸張されたデータを所定の規則（ルール）に従って並べ換える処理（後に詳述）を行う処理部である。また、印刷出力部２５は、復元されたデータに基づいて印刷出力を行う処理部であり、出力制御部２４は、この印刷出力を制御する処理部である。
【００３６】
＜Ｂ．動作概要＞
つぎに、図３を参照しながら、二値画像の並べ換えを含む圧縮動作について説明する。図３は、コントローラ１０で行われる動作を示すフローチャートである。
【００３７】
図３に示すように、まず、ステップＳＰ１１において二値画像が取得される。
【００３８】
より詳細には、上述したように、コントローラ１０上のアプリケーションソフトＡＳにおいて、印刷対象のファイルに対する印刷出力操作が受け付けられると、アプリケーションソフトＡＳは、プリンタドライバＰＤに印刷対象ファイルを引き渡す。プリンタドライバＰＤは、印刷対象ファイルに関して、ビットマップ展開あるいはハーフトーン処理等を施すことによって、二値画像を生成する。
【００３９】
次に、ステップＳＰ１２において、この二値画像に対する並べ換え処理（後に詳述）を行う。この並べ換え処理は、並べ換え処理部１１によって行われる。なお、この並べ換え処理は、次のステップＳＰ１３における圧縮処理の前段階で行われる前処理であるとも表現される。
【００４０】
そして、ステップＳＰ１３では所定の可逆圧縮手法を用いて並べ換え後の二値画像データを圧縮する。この圧縮処理は、圧縮部１２によって、ユニバーサル符号化法（例えばＬＺ法）などの可逆圧縮手法を用いて行われる。
【００４１】
なお、後述するように、二値画像に対して所定の可逆圧縮手法を適用する前に、ステップＳＰ１２で予め並べ換え処理を行っておくことによって、繰り返しパターンの出現回数を増加させて、圧縮符号化における圧縮率の改善を図ることができる。
【００４２】
その後、ステップＳＰ１４において、圧縮後のデータが送信部１３によってプリンタ２０に向けてネットワークＮＷを介して送信される。
【００４３】
つぎに、図４を参照しながら、二値画像の伸張動作等について説明する。図４は、プリンタ２０で行われる動作を示すフローチャートである。
【００４４】
図４に示すように、まず、プリンタ２０の受信部２１（図１）が、圧縮状態の二値画像データを取得する（ステップＳＰ２１）と、伸張部２２がこの圧縮状態の二値画像データに対して伸張処理を施す（ステップＳＰ２２）。この伸張処理によって、ステップＳＰ１３の圧縮処理直前のデータと完全に同一のデータが得られる。その後、並べ換え処理部２３は、画素列の並べ換え処理を施す（ステップＳＰ２３）。このステップＳＰ２３での並べ換え処理は、ステップＳＰ１２での並べ換えの手法に対応するものであり、この並べ換え処理によって、ステップＳＰ１１における二値画像データ、言い換えればステップＳＰ１２の並べ換え処理直前の二値画像データ、が完全に復元される。なお、この並べ換え処理は、ステップＳＰ２２における伸張処理の後段階で行われる後処理であるとも表現される。
【００４５】
その後、復元されたデータに基づいて、出力制御部２４の制御下において、印刷出力部２５を用いた印刷出力が行われる（ステップＳＰ２４）。これによって、二値画像が印刷用紙上に出力される。
【００４６】
＜Ｃ．圧縮時の処理＞
＜概要＞
つぎに、上記ステップＳＰ１２での並べ換え処理を中心に、当該並べ換え処理を含む画像圧縮処理について詳細に説明する。
【００４７】
図５は、文字ファイルの印刷出力結果の一例を示す図である。このような印刷出力結果も、上述したように、ハーフトーン処理等を経た二値画像として実現される。
【００４８】
図６（ａ）は、この二値画像の一部を拡大した状態を示す図に相当する。図６（ａ）では、各画素がそれぞれ最小正方形で表されており、複数の画素が、互いに直交する２つの方向（水平方向および垂直方向）に並べられて２次元的に配列されている。なお、二値画像はその構成画素が２次元的に配置されたものとして形成されるが、当該二値画像を表現するデータは１次元の配列として構成されるようにしてもよい。その場合でも、水平方向の総画素数（幅）に基づいて１次元配列の画素列を（仮想的に）折り返すことによって、各画素の水平方向および垂直方向における位置（ｘ，ｙ）を特定することが可能である。
【００４９】
また、二値画像は、図６（ａ）にも示すように、画像内の各画素の画素値（階調値）を２段階の値で表現するものである。図中においては、二値画像の各画素の画素値（階調値）は、「０」および「１」のいずれかの値であり、画素値「０」の画素が白色正方形で示され、画素値「１」の画素が斜線付きの正方形で示されている。ここでは、説明の簡易化のため、水平方向（Ｘ方向）に１６画素、垂直方向（Ｙ方向）に８画素並べられた合計１２８画素を対象として、並べ換え処理および圧縮処理等を行う場合について説明する。なお、実際の画像は、水平方向および垂直方向にさらに広がりを有していることが多いが、同様の処理を適宜繰り返して適用すればよい。
【００５０】
さて、仮に並べ換えを行わない場合には、水平方向（Ｘ方向）を主走査方向とし垂直方向（Ｙ方向）を副走査方向とすると、図６（ｂ）に示されるような順序で各画素の画素値が読み出されて合計１２８画素の画素値の１次元配列が生成される。図６における各画素に付された数字０,１,２,...は、１次元配列変換後の配列順序を示す番号である。
【００５１】
そして、このような画素値の１次元配列に対して所定の可逆圧縮手法で圧縮処理を施すことによって、二値画像を圧縮することが考えられる。この場合には、結果的に、二値画像の水平方向（Ｘ方向）における画素列の規則性に起因して出現する画素の繰り返しパターンが利用されて、効率的に圧縮される。しかしながら、二値画像の垂直方向（Ｙ方向）における画素列の規則性はほとんど利用されない。
【００５２】
これに対して、以下のような技術によれば、垂直方向の画素列の規則性を利用して、圧縮率の更なる改善を図ることが可能になる。以下では、このような技術について説明する。
【００５３】
具体的には、まず、（i）二値画像を、所定の画素サイズを有する単位画素ブロックＢで区分する。この単位画素ブロックＢは、次述するように、二値画像の副走査方向（ここではＹ方向）において、複数の画素で構成される画素列を有している（図７〜図９等を参照）。そして、（ii）二値画像における単位画素ブロック内の複数（ここでは８つ）の画素の画素値を所定の順序で読み出す動作を、二値画像において主走査方向（ここではＸ方向）に配列された複数の単位画素ブロックについて繰り返すことによって、二値画像における画素の並べ換えを行い、（iii）並べ換え後の画素列に対して、所定の可逆圧縮手法を適用して圧縮処理を行う。
【００５４】
以下では、この並べ換え処理等について更に詳細に説明する。なお、単位画素ブロックとしては、様々なタイプのものを用いることが可能であるが、ここでは、単位画素ブロックＢとして、次の３種類のサイズの矩形形状、すなわち、（（水平方向の画素数Ｐ）×（垂直方向の画素数Ｑ））＝（４×２）、（２×４）、（１×８）を有する場合について、順次に例示する。
【００５５】
＜その１＞
図７は、上記システム１における並べ換え処理の一例について説明する図である。図７も図６と同様の図であり、図７（ａ）は二値画像の一部拡大図を示しており、図７（ｂ）は並べ換え後の画素列を示している。ただし、図６（ａ）と図７（ａ）とでは画素内の数字が異なっている。このことは、並べ換え後の画素列に関する、図６（ｂ）と図７（ｂ）との相違点としても表れている。
【００５６】
図７（ａ）に示すように、まず、単位画素ブロックＢとして、４画素（水平方向）×２画素（垂直方向）のサイズの８つの画素を含む画素ブロック（図中において黒太枠で囲まれた領域）を想定する。図７（ａ）の単位画素ブロックＢは、副走査方向の画素サイズは２であり、２つの画素で構成される画素列を副走査方向に有している。
【００５７】
そして、並べ換え処理部１１は、最初の単位画素ブロックＢ内の８つの画素の画素値を所定の順序で読み出す。ここでは、まず、二値画像（図７（ａ）参照）において水平方向に並んだ上段の４つの画素を左から右に順次に読み出した後、その下側に並んだ下段の４つの画素を左から右に順次に読み出す場合が例示されている。このように、番号０〜７の８つの画素がこの順序で読み出される。この結果、図７（ｂ）に示すような、番号０〜７の８つの画素の画素値に関する１次元配列が形成される。
【００５８】
つぎに、二値画像において主走査方向（Ｘ方向）に連続的に配列された複数の単位画素ブロックＢについて、同様の読出し動作が繰り返される。
【００５９】
具体的には、次の（右隣の）単位画素ブロック内の８つの画素を同様にして読み出すことによって、番号８〜１５の８つの画素がこの順序で読み出される。さらに、次の単位画素ブロック内の８つの画素を同様にして読み出すことによって、番号１６〜２３の画素がこの順序で読み出される。
【００６０】
また、主走査方向における終端位置の単位画素ブロック（例えば番号２４〜３１の画素を含むもの）についての読出しが完了したときには、副走査方向（Ｙ方向）に１ブロック移動して同様の動作が繰り返される。具体的には、主走査方向における開始位置の読出し済み単位画素ブロックの直下の単位画素ブロック（例えば番号３２〜３９の画素を含むもの）に進んで、主走査方向における各単位画素ブロックについての同様の読出し動作を続行すればよい。
【００６１】
以降同様に、単位画素ブロックごとの読出し動作を繰り返すことによって、全ての画素（ここでは１２８画素）が番号０から番号１２７に至る１次元画素配列（データ列）として読み出される。
【００６２】
以上の処理がステップＳＰ１２において実行される。
【００６３】
その後、ステップＳＰ１３の圧縮処理が実行される。具体的には、並べ換え後のデータ列に対して、予め定められた可逆圧縮手法を用いた圧縮処理が施される。各画素の画素値をそのまま１ビット単位で取り扱って圧縮処理を施すようにしても良いが、ここでは、各１ビットで表現される各画素の画素値を８つずつまとめて、１バイト（８ビット）単位の情報として取り扱い、圧縮処理を施すものとする。
【００６４】
より詳細には、（１）番号０〜７までの画素の画素値をまとめた最初の１バイト文字（二進数表現で「１００１１００１」）、（２）番号８〜１５までの画素の画素値をまとめた次の１バイト文字（二進数表現で「００００００００」）、（３）番号１６〜２３までの画素の画素値をまとめた次の１バイト文字（二進数表現で「００００００００」）、（４）番号２４〜３１までの画素の画素値をまとめた次の１バイト文字（二進数表現で「０００１００１０」）、（５）番号３２〜３９までの画素の画素値をまとめた次の１バイト文字（二進数表現で「１０１１１１０１」）、...（以下、同様）を含む複数の１バイト文字からなる文字列を圧縮する。
【００６５】
可逆圧縮手法としては、例えば、エイブラハム・レンペル（Abraham Lempel）およびヤコブ・チフ（Jacob Ziv）らによって開発されたＬＺ法を用いればよい。ＬＺ法には、ＬＺ７７，ＬＺ７８、およびそれらの各種の改良手法（例えばＬＺＳＳ法、ＬＺＷ法等）が含まれる。また、可逆圧縮手法としては、ＬＺ法に限定されず、ランレングス法、部分一致予測法、ブロックソーティング法などの各種の手法を用いることが可能である。
【００６６】
上記において、二値画像の副走査方向において近い位置に存在する画素は、この並べ換え後の一次元配列において近い位置に配されることになる。
【００６７】
たとえば、番号８〜１１の各画素と、その下側の番号１２〜１５の各画素とは並べ換え後に近接して配置される（図７参照）。このことは、図６において番号４〜７の各画素とその下側の番号２０〜２３の各画素とが並べ換え後に離れて配置されることと、対照的である。
【００６８】
言い換えれば、図７（ｂ）の並べ換え後の１次元配列は、二値画像における副走査方向の相関ないし規則性（特にここでは二値画像における垂直方向への連続性）が反映されたものとなっている。より詳細には、図７（ｂ）の番号０〜３１の画素列（ｂ）を、図６の同画素列と比較すると判るように、「０」が連続する所定の繰り返しパターン「００００００００」が、より多く出現するように並べ換えられている。詳細には、番号８〜１５の画素列、番号１６〜２３の画素列、および番号４０〜４７の画素列等は、いずれも「００００００００」となっている。端的に言えば、二値画像において、黒色部分（例えば文字部分）で分断されていた白色領域（例えば背景部分）が、並べ換え処理によって纏めて配列されることになるとも表現できる。このように、並べ換え後の一次元データは、圧縮されやすい状態となっていることが判る。
【００６９】
このように、並べ換え後の一次元データは、二値画像の「副走査方向」における画素列の規則性を利用して（言い換えれば、二値画像が２次元的広がりを有するという幾何学的性質を利用して）、圧縮率の更なる改善を図ることが可能となるように並べ換えられている。
【００７０】
＜その２＞
図８は、別の並べ換え処理について説明する図である。図８も図６、図７と同様の図であり、図８（ａ）は二値画像の一部拡大図を示しており、図８（ｂ）は並べ換え後の画素列を示している。ただし、図８（ａ）と図７（ａ）とでは画素内の数字が異なっている。このことは、並べ換え後の画素列に関する、図８（ｂ）と図７（ｂ）との相違点としても表れている。
【００７１】
図８においては、単位画素ブロックＢとして、２画素（水平方向）×４画素（垂直方向）の８つの画素を含む画素ブロック（図中において黒太枠で囲まれた領域）を想定する。図８（ａ）の単位画素ブロックＢは、副走査方向の画素サイズは４であり、４つの画素で構成される画素列を副走査方向に有している。
【００７２】
そして、この単位画素ブロックＢ内の８つの画素の画素値を所定の順序で読み出す。ここでは、まず水平方向に並んだ最上段の２つの画素を連続的に読み出した後、その直下の２段目の２つの画素、さらに３段目の２つの画素、そして最後に４段目の２つの画素を順次に読み出す場合が例示されている。このように、番号０〜７の８つの画素がこの順序で読み出される。
【００７３】
つぎに、二値画像において主走査方向（Ｘ方向）に繰り返し配列された複数の単位画素ブロックＢについて、同様の読出し動作が繰り返される。さらに、主走査方向の読出しが終端位置まで終了すると、Ｙ方向に単位画素ブロックのＹ方向長さ（ここでは４画素分）移動して、同様の動作を繰り返す。これによって、全ての画素（ここでは１２８画素）が番号０から番号１２７に至る１次元画素配列として読み出される。
【００７４】
ここにおいて、並べ換え後の１次元配列は、二値画像における垂直方向への連続性が反映されたものとなっている。例えば、番号１６〜２３の画素列、番号２４〜３１の画素列、および番号３２〜３９の画素列等は、いずれも「００００００００」となっている。言い換えれば、「０」が連続する所定の繰り返しパターンがより多く出現するように並べ換えられている。したがって、並べ換え後の一次元データは、圧縮されやすい状態となっていることが判る。
【００７５】
以上の処理がステップＳＰ１２において実行された後、予め定められた可逆圧縮手法で並べ換え後のデータ列が圧縮される（ステップＳＰ１３）。
【００７６】
ここでは、各１ビットで表現される各画素の画素値を８つずつまとめて、１バイト（８ビット）単位の情報として取り扱い、圧縮処理を施すものとする。より詳細には、（１）番号０〜７までの画素の画素値をまとめた最初の１バイト文字（二進数表現で「１０１０１０１１」）、（２）番号８〜１５までの画素の画素値をまとめた次の１バイト文字（二進数表現で「０１０１１１０１」）、（３）番号１６〜２３までの画素の画素値をまとめた次の１バイト文字（二進数表現で「００００００００」）、（４）番号２４〜３１までの画素の画素値をまとめた次の１バイト文字（二進数表現で「００００００００」）、（５）番号３２〜３９までの画素の画素値をまとめた次の１バイト文字（二進数表現で「００００００００」）、...（以下、同様）を含む複数の１バイト文字からなる文字列を圧縮する。
【００７７】
＜その３＞
図９は、さらに別の並べ換え処理について説明する図である。図９も図６〜８と同様の図であり、図９（ａ）は二値画像の一部拡大図を示しており、図９（ｂ）は並べ換え後の画素列を示している。ただし、図９（ａ）と図７（ａ）とでは画素内の数字が異なっている。このことは、並べ換え後の画素列に関する、図９（ｂ）と図７（ｂ）との相違点としても表れている。
【００７８】
図９においては、単位画素ブロックＢとして、１画素（水平方向）×８画素（垂直方向）の８つの画素を含む画素ブロック（図中において黒太枠で囲まれた領域）を想定する。図９（ａ）の単位画素ブロックＢは、副走査方向の画素サイズは８であり、８つの画素で構成される画素列を副走査方向に有している。
【００７９】
そして、この単位画素ブロックＢ内の８つの画素の画素値を所定の順序で読み出す。ここでは、垂直方向に一列に並んだ順序に従って上から下へと順次に読み出す場合が例示されている。このように、番号０〜７の８つの画素がこの順序で読み出される。
【００８０】
つぎに、二値画像において主走査方向（Ｘ方向）に繰り返し配列された複数の単位画素ブロックＢについて、同様の読出し動作が繰り返される。これによって、全ての画素（ここでは１２８画素）が番号０から番号１２７に至る１次元画素配列として読み出される。
【００８１】
ここにおいて、並べ換え後の１次元配列は、二値画像における垂直方向への連続性が反映されたものとなっている。例えば、番号３２〜３９の画素列、番号４０〜４７の画素列、および番号４８〜５５の画素列等は、いずれも「００００００００」となっている。言い換えれば、「０」が連続する所定の繰り返しパターンがより多く出現するように並べ換えられている。したがって、並べ換え後の一次元データは、圧縮されやすい状態となっていることが判る。
【００８２】
以上の処理がステップＳＰ１２において実行された後、予め定められた可逆圧縮手法で並べ換え後のデータ列が圧縮される（ステップＳＰ１３）。
【００８３】
ここでは、各１ビットで表現される各画素の画素値を８つずつまとめて、１バイト（８ビット）単位の情報として取り扱い、圧縮処理を施すものとする。より詳細には、（１）番号０〜７までの画素の画素値をまとめた最初の１バイト文字（二進数表現で「１１１１１１１１」）、（２）番号８〜１５までの画素の画素値をまとめた次の１バイト文字（二進数表現で「０００１００００」）、（３）番号１６〜２３までの画素の画素値をまとめた次の１バイト文字（二進数表現で「００１０００００」）、（４）番号２４〜３１までの画素の画素値をまとめた次の１バイト文字（二進数表現で「１１１１１１１１」）、（５）番号３２〜３９までの画素の画素値をまとめた次の１バイト文字（二進数表現で「００００００００」）、...（以下、同様）を含む複数の１バイト文字からなる文字列を圧縮する。
【００８４】
＜総括＞
図１０は、上述の並べ換え処理を概念的に示す図である。上述の３種類の単位画素ブロックＢ（図７〜図９）は、それぞれ、水平方向にＺ画素、垂直方向に（８／Ｚ）画素並べられた矩形状の画素配列で構成されている（Ｚ＝４，２，１）。そして、この単位ブロック内の各画素の画素値が所定の順序で読み出されることによって、並べ換え後に連続する８ビット（１バイト）のデータが生成されることになる。
【００８５】
図１０に示すように、最初の例（図７参照、Ｚ＝４）では、元の二値画像を水平方向に２倍に引き延ばし且つ垂直方向に半分に縮めるように画素を並べ換えることに相当する。次の例（図８参照、Ｚ＝２）では、元の二値画像を水平方向に４倍に引き延ばし且つ垂直方向に１／４に縮めるように画素を並べ換えることに相当する。また、最後の例（図９参照、Ｚ＝１）では、元の二値画像を水平方向に８倍に引き延ばし且つ垂直方向に１／８に圧縮するように画素を並べ換えることに相当する。なお、いずれの場合も、総画素数は画素の並べ換え前後で同一である。
【００８６】
このように、垂直方向の画素情報を水平方向に展開することができるので、二値画像の垂直方向における規則性を利用して、同一パターンの繰り返しをより多く出現させることが可能になる。したがって、その後の圧縮段階における圧縮の度合いをさらに大きくすること（圧縮率を改善すること）が可能になる。
【００８７】
＜Ｄ．伸張時の処理＞
つぎに、プリンタ２０における画像伸張処理について説明する。
【００８８】
まず、ステップＳＰ２２においては、所定の可逆画像圧縮手法に対応する伸張手法を適用して伸張を行う。たとえば、ＬＺＳＳ法で圧縮処理が行われている場合には、ＬＺＳＳ法での伸張処理が行われる。いずれの手法を用いるかは、予め取り決めておけばよい。このステップＳＰ２２の伸張処理によって、ステップＳＰ１３の圧縮処理直前のデータと完全に同一のデータが得られる。
【００８９】
つぎに、ステップＳＰ２３において、並べ換え処理部２３は、伸張後の画素列を所定の配置ルールに基づいて単位画素ブロック内の各所定位置に配置し並べ換える動作、を繰り返すことによって、二値画像において水平方向に配列された複数の単位画素ブロックを復元する。この並べ換え処理によって、コントローラ１０での圧縮処理前の二値画像データ（ステップＳＰ１２の並べ換え処理直前の二値画像データ）が完全に復元される。
【００９０】
より詳細には、並べ換え処理部２３は、予め定められた単位画素ブロック種類とその内部での配置順序とに従って、伸張後の画素列を並べ換えて、元の画素列を復元する。
【００９１】
たとえば、単位画素ブロック種類とその単位画素ブロック内部での配置順序とについて図７のものを採用することを予め取り決めておく場合には、プリンタ２０は、その取り決め（配置ルール）に従って、図７（ｂ）のような伸張後の画素列を図７（ａ）の配置順序で、並べ換えればよい。これによって、番号０〜３、８〜１１、１６〜１９、２４〜２７の画素で最上段の画素列を構成し、番号４〜７、１２〜１５、２０〜２３、２８〜３１の画素で次の段の画素列を構成することができる。その後同様にして、画素列全体を復元することができる。
【００９２】
このような処理によれば、高効率に圧縮された状態の二値画像を元の状態に戻すことが可能である。
【００９３】
なお、ここでは予め定められた並べ換え順序等に従って元の二値画像を復元する場合を例示しているが、これに限定されず、圧縮時に使用された単位画素ブロックの種類などを圧縮ファイルのヘッダ情報に格納しておき、プリンタ２０がそのヘッダ情報の内容に応じた並べ換え処理（ステップＳＰ２３）等を行うようにしてもよい。
【００９４】
＜Ｅ．その他＞
以上のように、このシステム１のコントローラ１０は、（i）二値画像を区分する単位画素ブロックとして、副走査方向（Ｙ方向）の画素サイズが２以上の単位画素ブロックを想定し、（ii）各単位画素ブロック内の複数（８つ）の画素の画素値を所定の順序で読み出す動作を、二値画像において主走査方向に配列された複数の単位画素ブロックについて繰り返すことによって、二値画像における画素の並べ換えを行い、（iii）並べ換え後の画素列に対して、所定の可逆圧縮手法を適用して圧縮処理を行う。したがって、垂直方向の画素列の規則性を考慮した並べ換えを行った上で圧縮処理が施されるので、圧縮率を更に改善することが可能である。
【００９５】
なお、ＬＺ法のうちのＬＺＳＳ法とＬＺＷ法とを比較した場合、（対象画像の相違およびハーフトーン処理内容の相違にも依存するが）一般的には、並べ換えを伴う上記思想をＬＺＳＳ法に適用する場合の方が、上記思想をＬＺＷ法に適用する場合に比べて、並べ換えの実施による圧縮率の改善効果が高い。これは、ＬＺＷ法では広域的な辞書を作成するのに対して、ＬＺＳＳ法では直近のデータ列を辞書として用いるという、辞書構造の相違に基づくものであると考えられる。
【００９６】
また、並べ換え時の単位画素ブロックの縦横比（言い換えれば、上記Ｚの値）は、圧縮手法に応じた適宜の値を採用することが好ましい。たとえば、或る幾つかの画像に対しては、ＬＺＳＳ法ではＺ＝１あるいはＺ＝２とした場合に圧縮率の改善効果が高くなり、ＬＺＷ法ではＺ＝２あるいはＺ＝４とした場合に圧縮率の改善効果が高くなるという傾向がある。なお、圧縮率の改善効果は、対象画像の相違およびハーフトーン処理内容の相違によっても異なるため、対象画像および／またはハーフトーン処理内容等に応じて、適宜の値（単位画素ブロックの縦横比）を選ぶことが好ましい。
【００９７】
また、上記実施形態においては、単位画素ブロック内の読出し順序として、図７〜図１０に示すケースを例示したが、これに限定されない。具体的には、図１１および図１２のような読出し順序を用いても良い。なお、図１１および図１２は、図７（ａ）等と同様の一部拡大図を様々な変形例について示す図であり、各画素に付された数字は単位画素ブロック内での各画素の読出し順序を表している。
【００９８】
図１１は、Ｚ＝４に対応する単位画素ブロックＢについて、図７と異なる順序で各画素値を読み出す様々な変形例を示す図である。
【００９９】
詳細には、図１１（ａ）は、上下２段にわたる単位画素ブロックＢ内の画素のうち、上段の画素と下段の画素とをこの順序で垂直画素列ごとに交互に読出して水平方向（Ｘ方向）に順次移動しながら全ての画素列の画素値を読み出す場合を例示する。また、図１１（ｂ）は、単位画素ブロックＢ内の所定位置に在る０番の画素の画素値からはじめて、所定方向回りに（ここでは反時計回りに）、８つの画素の画素値を読み出す場合を例示する。
【０１００】
また、図１２は、Ｚ＝２に対応する単位画素ブロックＢについて、図８と異なる順序で各画素値を読み出す様々な変形例を示す図である。
【０１０１】
詳細には、図１２（ａ）は、垂直方向（Ｙ方向）４段にわたる２つの垂直画素列のうち、まず左側の垂直画素列内の４つの画素の画素値を最上段から最下段へ向けてその配列順序に従って読出し、次に右側の垂直画素列内の４つの画素を最上段から最下段へ向けてその配列順序に従って読出す場合を例示する。また、図１２（ｂ）は、４段に並んだ２画素ずつの水平画素列を、最上段から最下段に向けて、段ごとに読出し順序を（左から右へ、右から左へと）交互に変更しつつ読み出す場合を例示する。さらに、図１２（ｃ）は、単位画素ブロックＢ内の所定位置に在る０番の画素の画素値からはじめて、所定方向回りに（ここでは時計回りに）８つの画素の画素値を読み出す場合を例示する。
【０１０２】
さらに、これ以外の読出し順序を用いて、単位画素ブロックＢ内の各画素の画素値を読み出すようにしてもよい。
【０１０３】
また、上記実施形態においては、８個の画素で単位画素ブロックＢを構成する場合を例示したが、これに限定されず、たとえば１６個の画素で単位画素ブロックＢを構成するようにしてもよい。
【０１０４】
さらに、上記実施形態においては、並べ換え後の一次元配列を、８個の画素ずつまとめて１バイト単位の文字として取り扱った上で、圧縮処理を施す場合について例示したが、これに限定されない。たとえば、１６個の画素をまとめて２バイト（１６ビット）単位で取り扱って圧縮処理を施すようにしてもよい。あるいは、４個の画素をまとめて４ビット単位で取り扱って圧縮処理を施すようにしてもよい。さらには、上述したように、各画素の画素値をそのまま１ビット単位で取り扱って圧縮処理を施すようにしてもよい。
【０１０５】
また、上記実施形態においては、水平方向（Ｘ方向）を主走査方向とする場合を例示しているが、これに限定されない。たとえば、上記とは逆に、垂直方向（Ｙ方向）を主走査方向とし、水平方向（Ｘ方向）を副走査方向としてもよい。言い換えれば、複数の単位画素ブロックをまず垂直方向に順次に読み出していくようにしてもよい。なお、その場合には、各単位画素ブロックは、二値画像の副走査方向（Ｘ方向）において、複数の画素で構成される画素列を有するように構成すればよい。端的に言えば、各単位画素ブロックにおける副走査方向（Ｘ方向）の画素サイズが２以上となるようにすればよい。
【０１０６】
さらに、上記実施形態においては、ネットワークＮＷを用いてデータを転送する場合を例示したが、これに限定されず、パラレルポートを経由したデータ転送など、様々なデータ転送を行うためのデータ圧縮に上記思想を適用してもよい。この場合でも、圧縮率の改善によって、データ転送の効率化を図ることが出来る。
【０１０７】
また、上記実施形態においては、印刷出力用二値画像の圧縮に上記思想を適用する場合について説明したが、これに限定されず、その他の用途の二値画像に対して上記思想を適用してもよい。これによれば、圧縮率の改善によってデータの保管効率の向上（例えば、メモリ領域の節約あるいはハードディスク領域の節約など）等を図ることができる。
【図面の簡単な説明】
【０１０８】
【図１】プリントシステムの概略構成を示す図である。
【図２】コントローラのソフトウエア構成および機能ブロックを示す図である。
【図３】コントローラの動作を示すフローチャートである。
【図４】プリンタの動作を示すフローチャートである。
【図５】文字ファイルの印刷出力結果の一例を示す図である。
【図６】二値画像の一部を拡大した状態等（比較例）を示す図である。
【図７】並べ換え処理の一例について説明する図である。
【図８】別の並べ換え処理について説明する図である。
【図９】さらに別の並べ換え処理について説明する図である。
【図１０】並べ換え処理を概念的に示す図である。
【図１１】並べ換え順序の変形例を示す図である。
【図１２】並べ換え順序の変形例を示す図である。
【符号の説明】
【０１０９】
１  プリントシステム
４  メディアドライブ
９  記録媒体
１０  コントローラ
２０  プリンタ
Ｂ  単位画素ブロック
ＮＷ  ネットワーク
【図１】
2005295307.tif 000003
【図２】
2005295307.tif 000004
【図３】
2005295307.tif 000005
【図４】
2005295307.tif 000006
【図５】
2005295307.tif 000007
【図６】
2005295307.tif 000008
【図７】
2005295307.tif 000009
【図８】
2005295307.tif 000010
【図９】
2005295307.tif 000011
【図１０】
2005295307.tif 000012
【図１１】
2005295307.tif 000013
【図１２】
2005295307.tif 000014