(57)【要約】画像圧縮は、入力画像を縦横所定の画素数のブロックに分割し、分割されたブロックを主走査方向および副走査方向に走査して順番に処理ブロックとして選択し、選択されたブロックとの位置関係及び画素値の関係が所定の条件を満たすブロックを参照ブロックとして選択する。続いて処理ブロックと参照ブロックの画素値を排他的論理和（ＸＯＲ）して差分画像を生成し、差分画像が所定の条件を満たす場合に処理ブロックを差分画像に置き換える。更に、ブロック置換を実行して得られた差分画像像を処理ブロックに含む画像を符号化し、この画像符号化を実行して得られた符号データ、ブロック置換を実行して得られた各処理ブロックの差分画像への置換有無、および参照ブロックの位置情報とを組み合わせて出力する。画像復元は、符号データから差分画像を含む画像を復号し、この復号画像をブロック分割した処理ブロックと参照ブロックとの排他的論理和（ＸＯＲ）により元の画像を復号する。
2004068844.tif 000002
【特許請求の範囲】
【請求項１】
ブロック分割部により、入力画像を縦横所定の画素数のブロックに分割する分割ステップと、
処理ブロック選択部により、前記分割されたブロックを主走査方向および副走査方向に走査して順番に処理ブロックとして選択する処理ブロック選択ステップと、
参照ブロック選択部により、前記処理ブロック選択ステップで選択されたブロックとの位置関係及び画素値の関係が所定の条件を満たすブロックを参照ブロックとして選択する参照ブロック選択ステップと、
差分画像生成部により、前記処理ブロックと参照ブロックの画素値を排他的論理和して差分画像を生成する差分画像生成ステップと、
ブロック置換部により、前記差分画像が所定の条件を満たす場合に前記処理ブロックを前記差分画像に置き換えるブロック置換ステップと、
を備えたことを特徴とする画像圧縮方法。
【請求項２】
請求の範囲１記載の画像圧縮方法に於いて、更に、
画像符号化部により、前記ブロック置換ステップを実行して得られた画像を符号化する画像符号化ステップと、
符号出力部により、前記画像符号化ステップを実行して得られた符号データと、前記ブロック置換ステップを実行して得られた各処理ブロックの差分画像への置換有無および参照ブロックの位置情報とを組み合わせて出力する出力ステップと、
を備えたことを特徴とする画像圧縮方法。
【請求項３】
請求の範囲１の画像圧縮方法に於いて、前記参照ブロック選択ステップは、前記処理ブロック選択ステップにより既に選択された処理済みブロックの中から現在の処理ブロックに近いブロックを参照ブロックとして優先して選択することを特徴とする画像圧縮方法。
【請求項４】
請求の範囲１の画像圧縮方法に於いて、前記画像置換ステップは、前記差分画像生成ステップを実行した結果に基づいて処理ブロックと参照ブロックとの画素差が所定の個数以上の場合には処理ブロックの差分画像への置き換えを行わないことを特徴とする画像圧縮方法。
【請求項５】
請求の範囲１の画像圧縮方法に於いて、前記処理ブロック選択ステップは、選択したブロックの画素値が予め定めた所定のパターンに合致する場合には、該処理ブロックの参照ブロックとの排他論理和の処理をスキップすることを特徴とする画像圧縮方法。
【請求項６】
請求の範囲１の画像圧縮方法に於いて、前記分割ステップは、ブロックの横画素数および縦画素数を８の倍数とすることを特徴とする画像圧縮方法。
【請求項７】
請求の範囲２の画像圧縮方法に於いて、前記画像符号化ステップは、
前記差分画像の処理ブロックを含む画像を主走査方向に走査することにより、任意の整数であるＫ行単位に黒画素を含む領域と黒画素を含まない領域に分離する第１領域分離ステップと、
前記第１領域分離ステップで得られた黒画素を含む前記Ｋの整数倍であるＮ行として定義される論理行を、主走査方向と交差する副走査方向に走査することにより、１列単位に黒画素を含む領域と黒画素を含まない領域とに分離する第２領域分離ステップと、
前記第１領域分離ステップおよび第２領域分離ステップで得られた各領域を要素として符号化する符号化ステップと、
を備えたこと特徴とする画像圧縮方法。
【請求項８】
符号入力部により、所定の符号データ、各処理ブロックの差分画像への置換有無、および参照ブロックの位置情報の組み合わせを含む画像圧縮データを入力する入力ステップと、
画像復号部により、入力された前記符号データを画像に復号する画像復号ステップと、
ブロック復号部により、前記画像復号ステップの復号画像を縦横所定の画素数の処理ブロックに分割し、差分画像に置き換えられた処理ブロックと参照ブロックの画素値を排他的論理和して前記処理ブロックの画素値と置き換えて復号するブロック復号ステップと、
を備えたことを特徴とする画像復元方法。
【請求項９】
請求の範囲８記載の画像元方法に於いて、前記各処理ブロックの差分画像への置換有無および参照ブロックの位置情報は、
入力画像を縦横所定の画素数のブロックに分割する分割ステップと、
前記分割されたブロックを主走査方向および副走査方向に走査して順番に処理ブロックとして選択する処理ブロック選択ステップと、
前記処理ブロック選択ステップで選択されたブロックとの位置関係及び画素値の関係が所定の条件を満たすブロックを参照ブロックとして選択する参照ブロック選択ステップと、
前記処理ブロックと参照ブロックの画素値を排他的論理和して差分画像を生成する差分画像生成ステップと、
前記差分画像が所定の条件を満たす場合に前記処理ブロックを該差分画像に置き換えるブロック置換ステップと、
を備えた圧縮側の処理により生成されたことを特徴とする画像復元方法。
【請求項１０】
請求の範囲２の画像圧縮方法に於いて、前記画像符号データは、
前記差分画像の処理ブロックを含む画像を主走査方向に走査することにより、任意の整数であるＫ行単位に黒画素を含む領域と黒画素を含まない領域に分離する第１領域分離ステップと、
前記第１領域分離ステップで得られた黒画素を含む前記Ｋの整数倍であるＮ行として定義される論理行を、主走査方向と交差する副走査方向に走査することにより、１列単位に黒画素を含む領域と黒画素を含まない領域とに分離する第２領域分離ステップと、
前記第１領域分離ステップおよび第２領域分離ステップで得られた各領域を要素として符号化する符号化ステップと、
を備えた圧縮側の処理により生成されたことを特徴とする画像圧縮方法。
【請求項１１】
コンピュータに、
入力画像を縦横所定の画素数のブロックに分割する分割ステップと、
前記分割されたブロックを主走査方向および副走査方向に走査して順番に処理ブロックとして選択する処理ブロック選択ステップと、
前記処理ブロック選択ステップで選択されたブロックとの位置関係及び画素値の関係が所定の条件を満たすブロックを参照ブロックとして選択する参照ブロック選択ステップと、
前記処理ブロックと参照ブロックの画素値を排他的論理和して差分画像を生成する差分画像生成ステップと、
前記差分画像が所定の条件を満たす場合に前記処理ブロックを該差分画像に置き換えるブロック置換ステップと、
を実行させることを特徴とするプログラム。
【請求項１２】
コンピュータに、
所定の符号データ、各処理ブロックの差分画像への置換有無、および参照ブロックの位置情報の組み合わせを含む画像圧縮データを入力する入力ステップと、
入力された前記符号データを画像に復号する画像復号ステップと、
前記画像復号ステップの復号画像を縦横所定の画素数の処理ブロックに分割し、差分画像に置き換えられた処理ブロックと参照ブロックの画素値を排他的論理和して前記処理ブロックの画素値と置き換えて復号するブロック復号ステップと、
を実行させることを特徴とするプログラム。
【請求項１３】
入力画像を縦横所定の画素数のブロックに分割するブロック分割部と、
前記分割されたブロックを主走査方向および副走査方向に走査して順番に処理ブロックとして選択する処理ブロック選択部と、
前記処理ブロック選択ステップで選択されたブロックとの位置関係及び画素値の関係が所定の条件を満たすブロックを参照ブロックとして選択する参照ブロック選択部と、
前記処理ブロックと参照ブロックの画素値を排他的論理和して差分画像を生成する差分画像生成部と、
前記差分画像が所定の条件を満たす場合に前記処理ブロックを該差分画像に置き換えるブロック置換部と、
前記ブロック置換部を実行して得られた画像を符号化する画像符号化部と、
前記画像符号化部を実行して得られた符号データと、前記ブロック置換部を実行して得られた各処理ブロックの差分画像への置換有無および参照ブロックの位置情報とを組み合わせて出力する符号出力部と、
を備えたことを特徴とする画像圧縮装置。
【請求項１４】
所定の符号データ、各処理ブロックの差分画像への置換有無、および参照ブロックの位置情報の組み合わせを含む画像圧縮データを入力する符号入力部と、
入力された前記符号データを画像に復号する画像復号部と、
前記画像復号部の復号画像を縦横所定の画素数の処理ブロックに分割し、差分画像に置き換えられた処理ブロックと参照ブロックの画素値を排他的論理和して前記処理ブロックの画素値と置き換えて復号するブロック復号部と、
を備えたことを特徴とする画像復元装置。
【発明の詳細な説明】
【技術分野】  本発明は、ビットマップ画像を圧縮してプリンタ等に転送した後に復元する画像圧縮方法、画像復元方法、プログラム及び装置に関し、特に、クラデーションのような画像変化を高圧縮可能な画像圧縮方法、画像復元方法、プログラム及び装置に関する。
【背景技術】  近年、パソコンなどの情報機器が普及し、様々な用途に使用されている。特に、パソコンで画像を処理する場合が多く見られ、パソコンにプリンタを接続し、画像を印刷したり、インターネットなどのネットワークを介して画像データを転送するなどの処理が行われている。しかし、画像が複雑になればなるほど、パソコンからプリンタへの画像データの転送や、ネットワークを介しての画像データの転送に時間がかかり過ぎるようになり、画像データを圧縮して転送することが望まれる。このためフォントを持たないプリンタにビットマップ画像を直接転送して印刷を行う場合に、画像データを圧縮することによって、送信すべきデータの量が少なくなり、転送時間を節約できるものである。この場合、画像データには、カラーのものや、グレースケールのものなどがあるが、以下では、これらの画像データを２値化した２値化ビットマップ画像の圧縮方法について述べる。
従来の２値ビットマップ画像の圧縮方法としては、ＭＨ（Ｍｏｄｉｆｉｅｄ  Ｈｕｆｆｍａｎ）やＭＲ（Ｍｏｄｉｆｉｅｄ  ＲＥＡＤ）、ＭＭＲ（Ｍｏｄｉｆｉｅｄ  Ｍｏｄｉｆｉｅｄ  ＲＥＡＤ）、ＪＢＩＧ（Ｊｏｉｎｔ  Ｂｉ−Ｌｅｖｅｌ  Ｉｍａｇｅ  Ｅｘｐｅｒｔｓ  Ｇｒｏｕｐ）等があり、ＦＡＸ通信や画像ファイリングに広く使用されている。
これらの圧縮方法はビット処理を多用するなど高速な符号化処理に向かないことから、高速処理を狙った「ビットマップデータの圧縮方法及び圧縮装置」（日本国特許第３２７８２９８号）を提案している。この画像圧縮方法では、文字を主体とするビットマップは効率良く圧縮できる反面、ディザ画像の圧縮効率が低いという問題がある。このため、本願発明者は、同じパターンが連続して繰り返し現れる一様なディザ画像の圧縮率を高める圧縮方法を提案している（日本国特許出願：特願２００１−３８８９３１号）。
しかしながら、本願発明者が提案している圧縮方法は、パターンの形状が変化せずに周期的に繰り返す一様なディザ画像は効率良く圧縮できる反面、グラデーションのようにパターンの形状が連続的に変化するディザ画像の場合には全く圧縮できないという問題があった。
【発明の開示】
本発明は、パターンの形状が連続的に変化するディザ画像の圧縮効率を高める画像圧縮方法、画像復元方法、プログラム及び装置を提供することを目的としている。
（圧縮方法）
本発明は画像圧縮方法を提供するものであり、
ブロック分割部により、入力画像を縦横所定の画素数のブロックに分割する分割ステップと、
処理ブロック選択部により、分割されたブロックを主走査方向および副走査方向に走査して順番に処理ブロックとして選択する処理ブロック選択ステップと、
参照ブロック選択部により、処理ブロック選択ステップで選択されたブロックとの位置関係及び画素値の関係が所定の条件を満たすブロックを参照ブロックとして選択する参照ブロック選択ステップと、
差分画像生成部により、前記処理ブロックと参照ブロックの画素値を排他的論理和（ＸＯＲ）して差分画像を生成する差分画像生成ステップと、
ブロック置換部により、差分画像が所定の条件を満たす場合に処理ブロックを差分画像に置き換えるブロック置換ステップと、
を備えたことを特徴とする。
更に本発明の画像圧縮方法は、
画像符号化部により、ブロック置換ステップを実行して得られた画像を符号化する画像符号化ステップと、
符号出力部により、画像符号化ステップを実行して得られた符号データと、ブロック置換ステップを実行して得られた各処理ブロックの差分画像への置換有無および参照ブロックの位置情報とを組み合わせて出力する出力ステップと、
を備えたことを特徴とする。
このように本発明は、画像符号化ステップで画像を符号化するための前処理として、画像を縦横（Ｎ×Ｍ）画素のブロックに分割して各ブロックをその近傍ブロックと排他的論理和（ＸＯＲ）を行い、画像内の符号化すべき黒画素の個数を削減することで圧縮効率を高める。即ち、ブロック間の画素値に排他的論理和（ＸＯＲ）を適用して差分画像を生成すると、両ブロックの同一位置の画素値が異なる部分、即ち白画素対黒画素、または黒画素対白画素となる部分だけが黒画素として残る。このため、グラデーションのようにパターンの形状が連続的に変化するディザ画像の場合、隣接するブロック間の画素値の相関が高いほど差分画像の黒画素が少なくなり、同一画素値のブロックの場合には差分画像内は全て白画素となる。画像符号化ステップの処理では、一般的に画像内の黒画素を符号化するため黒画素数が少ないほど圧縮率が高くなり、画像符号化前にブロック間の排他的論理和（ＸＯＲ）を適用することで、符号化対象となる黒画素の個数が減り、画像の圧縮率が高まる。
ここで参照ブロック選択ステップは、処理ブロック選択ステップにより既に選択された処理済みブロックの中から現在の処理ブロックに近いブロックを参照ブロックとして優先して選択する。このように圧縮時に、排他的論理和（ＸＯＲ）の処理を終えたブロックの中から前方参照により参照ブロックを選択することで、入力された画像を順次ブロックに分割し、排他的論理和（ＸＯＲ）を適用することで符号化処理を進めることができ、このため画像全体の入力の完了を待たずに圧縮処理を先行して開始できる。
また復元時には、符号データから差分画像のブロックが復号される毎に、既に差分画像から復号された復元済みの参照ブロックとの排他的論理和（ＸＯＲ）の処理が実行でき、全ブロック復元後に再度先頭ブロックから排他的論理和（ＸＯＲ）処理を実行するような２パス式の処理を必要とせず、より早く復元画像が得られ、復号が完了した画像から先行してプリンタで印刷するなど、復元画像を使用する側の待ち時間が短縮する。
画像置換ステップは、差分画像生成ステップを実行した結果に基づいて処理ブロックと参照ブロックとの画素差が所定の個数以上の場合には処理ブロックの差分画像への画素値の置き換えを行わない。これは処理ブロックと参照ブロックの画像が大きく異なる場合には、差分画像内の黒画素数が多くなり圧縮効率が低下することを考慮したもので、処理ブロックに最も近い隣接ブロックから順番にブロックを選択して処理ブロックと排他的論理和（ＸＯＲ）を行い、得られた差分画像内の黒画素数が所定の個数以下であり、かつ黒画素数が最小になるブロックを参照ブロックとして選択することにより、処理ブロックとの画素差がもっとも小さくなる参照ブロックが選択され、排他的論理和（ＸＯＲ）後の差分画像内の黒画素が最小となり符号化効率が高まる。
処理ブロック選択ステップは、選択したブロックの画素値が予め定めた所定のパターンに合致する場合には、この処理ブロックと参照ブロックとの排他論理和の処理をスキップする。これは黒画素が含まれないブロックや、各列の画素値が全て同一であるブロック等は、参照ブロックと排他的論理和（ＸＯＲ）しなくても、その後に適用する画像符号化ステップの符号化で効率良く圧縮できる場合があることを考慮したものであり、このように後段の画像符号化により高圧縮できることが予め分かっているブロックについては排他的論理和（ＸＯＲ）処理を適用しないようにすることで、排他的論理和（ＸＯＲ）による処理負荷を低減し圧縮効率の低下を防ぐ。
分割ステップは、ブロックの横画素数および縦画素数を８の倍数とする。これにより本発明の圧縮方法を実行する処理装置に搭載する中央処理装置（ＣＰＵ）の内部レジスタのビット長とブロックの縦画素数Ｍ及び又は横画素数Ｎを一致させ、必要最小限の処理ステップ数でブロック間の画素値の排他的論理和（ＸＯＲ）処理を実行する。一般的にＣＰＵの内部レジスタのビット長は８の倍数であることから、ブロックの縦横画素数も、それに合わせて８の倍数に設定する。
処理ブロックを参照ブロックとの排他的論理和（ＸＯＲ）により生成された差分画像に置き換える画像置換ステップに続いて実行される画像符号化ステップは、
差分画像の処理ブロックを含む画像を主走査方向に走査することにより、任意の整数であるＫ行単位に黒画素を含む領域と黒画素を含まない領域に分離する第１領域分離ステップと、
第１領域分離ステップで得られた黒画素を含むＫの整数倍であるＮ行として定義される論理行を、主走査方向と交差する副走査方向に走査することにより、１列単位に黒画素を含む領域と黒画素を含まない領域とに分離する第２領域分離ステップと、
第１領域分離ステップおよび第２領域分離ステップで得られた各領域を要素として符号化する符号化ステップと、
を備えたことを特徴とする。このように本発明は、排他的論理和（ＸＯＲ）により生成された差分画像を処理ブロックに含む画像を対象に、更に、所定のライン数Ｋで主走査方向に走査して黒画素を含む領域を論理行（ｌｏｇｉｃａｌ  ｌｉｎｅ）として分離し、この論理行を副走査方向に走査して黒画素を含む領域とそれ以外の領域に分離してそれぞれを要素として符号化する圧縮方法と組み合わせて、さらに圧縮効率を高める。このような２段階の圧縮により、最初に行う排他的論理和（ＸＯＲ）による差分画像の生成による圧縮は、後に行う符号化の前処理に位置付けられる。
本発明は、排他的論理和（ＸＯＲ）による差分画像の生成と、続いて行う符号化とにより生成された画像圧縮データから画像を復元する復元方法を提供する。
この画像復元方法は、
符号入力部により、所定の符号データ、各処理ブロックの差分画像への置換有無、および参照ブロックの位置情報の組み合わせを含む画像圧縮データを入力する入力ステップと、
画像復号部により、入力された前記符号データを画像に復号する画像復号ステップと、
ブロック復号部により、画像復号ステップの復号画像を縦横所定の画素数の処理ブロックに分割し、差分画像に置き換えられた処理ブロックと参照ブロックの画素値を排他的論理和（ＸＯＲ）して処理ブロックの画素値と置き換えて復号するブロック復号ステップと、
を備えたことを特徴とする。本発明の圧縮方法で符号化された符号データから元の画像への復元は、まず符号データから排他的論理和（ＸＯＲ）を適用した画像を復号した後、ブロック分けした各ブロックについて圧縮時に排他的論理和（ＸＯＲ）した同じ位置の参照ブロックと再び排他的論理和（ＸＯＲ）することで元のブロックを復元する。このように排他的論理和（ＸＯＲ）演算は２回実行すると完全に元のデータに戻る性質があり、画像の劣化が無く完全に元通りに復元される。
（プログラム）
本発明は、画像圧縮のためのプログラムを提供する。この画像圧縮用のプログラムは、コンピュータに、
入力画像を縦横所定の画素数のブロックに分割する分割ステップと、
分割されたブロックを主走査方向および副走査方向に走査して順番に処理ブロックとして選択する処理ブロック選択ステップと、
処理ブロック選択ステップで選択されたブロックとの位置関係及び画素値の関係が所定の条件を満たすブロックを参照ブロックとして選択する参照ブロック選択ステップと、
処理ブロックと参照ブロックの画素値を排他的論理和（ＸＯＲ）して差分画像を生成する差分画像生成ステップと、
差分画像が所定の条件を満たす場合に処理ブロックを差分画像に置き換えるブロック置換ステップと、
を実行させることを特徴とする。
更に本発明のプログラムは、コンピュータに、
ブロック置換ステップを実行して得られた画像を符号化する画像符号化ステップと、
画像符号化ステップを実行して得られた符号データと、ブロック置換ステップを実行して得られた各処理ブロックの差分画像への置換有無および参照ブロックの位置情報とを組み合わせて出力する出力ステップと、
を実行させる。
本発明は、画像圧縮データを復元するためのプログラムを提供する。この画像復元用のプログラムは、コンピュータに、
所定の符号データ、各処理ブロックの差分画像への置換有無、および参照ブロックの位置情報の組み合わせを含む画像圧縮データを入力する入力ステップと、
入力された符号データを画像に復号する画像復号ステップと、
画像復号ステップの復号画像を縦横所定の画素数の処理ブロックに分割し、差分画像に置き換えられた処理ブロックと参照ブロックの画素値を排他的論理和（ＸＯＲ）して処理ブロックの画素値と置き換えて復号するブロック復号ステップと、
を実行させることを特徴とする。なお、本発明のプログラムの詳細は画像圧縮方法及び画像復元方法の場合と基本的に同じになる。
（装置）
本発明は、画像圧縮装置を提供する。この画像圧縮装置は、入力画像を縦横所定の画素数のブロックに分割するブロック分割部と、分割されたブロックを主走査方向および副走査方向に走査して順番に処理ブロックとして選択する処理ブロック選択部と、処理ブロック選択部で選択されたブロックとの位置関係及び画素値の関係が所定の条件を満たすブロックを参照ブロックとして選択する参照ブロック選択部と、処理ブロックと参照ブロックの画素値を排他的論理和（ＸＯＲ）して差分画像を生成する差分画像生成部と、差分画像が所定の条件を満たす場合に処理ブロックを差分画像に置き換えるブロック置換部と、ブロック置換部を実行して得られた画像を符号化する画像符号化部と、画像符号化部を実行して得られた符号データと、ブロック置換部を実行して得られた各処理ブロックの差分画像への置換有無および参照ブロックの位置情報とを組み合わせて出力する符号出力部とを備えたことを特徴とする。
本発明は、画像圧縮装置から出力された画像圧縮データを復元する画像復元装置を提供する。この画像復元装置は、所定の符号データ、各処理ブロックの差分画像への置換有無、および参照ブロックの位置情報の組み合わせを含む画像圧縮データを入力する符号入力部と、入力された符号データを画像に復号する画像復号部と、画像復号部の復号画像を縦横所定の画素数の処理ブロックに分割し、差分画像に置き換えられた処理ブロックと参照ブロックの画素値を排他的論理和（ＸＯＲ）して処理ブロックの画素値と置き換えて復号するブロック復号部とを備えたことを特徴とする。なお、本発明の画像圧縮装置及び画像復元装置の詳細は、画像圧縮方法及び画像復元方法の場合と基本的に同じになる。
【図面の簡単な説明】図１は本発明が適用される装置環境の説明図；
図２は本発明による画像圧縮装置の機能構成のブロック図；
図３は本発明の圧縮時におけるブロックの排他論理和処理の説明図；
図４は本発明による画像圧縮処理の概略フローチャート；
図５は本発明が適用されるコンピュータのハードウェア環境の説明図；
図６は本発明による画像復元装置の機能構成のブロック図；
図７は本発明の復元時におけるブロックの排他論和処理の説明図；
図８は本発明による画像復元処理の概略フローチャート；
図９は入力画像のブロック分割と処理ブロック及び参照ブロックの説明図；
図１０はブロックラインと論理行のライン数との関係の説明図；
図１１は本発明の画像圧縮におけるブロック処理の順番の説明図；
図１２は本発明における参照ブロックの選択順序を指定するテンプレートの説明図；
図１３は本発明におけるブロックライン単位の画像圧縮処理の説明図；
図１４は本発明におけるブロックライン単位の画像復元処理の説明図；
図１５は本発明による画像圧縮処理のフローチャート；
図１６は図１５に続く画像圧縮処理のフローチャート；
図１７は排他論理和したブロックのブロックラインバッファへの格納位置の説明図；
図１８は参照ブロック位置格納テーブルの説明図；
図１９は参照ブロック位置格納テーブルと符号化の説明図；
図２０は図１５及び図１６における参照ブロック選択処理のフローチャート；
図２１は図２０の参照ブロック選択処理で使用される選択順序を指定するテンプレートの説明図；
図２２は本発明で排他論理和を適用しない処理ブロックと参照ブロックの説明図；
図２３は本発明によるブロックの排他論理和処理が行われた画像処理の例の説明図；
図２４は図２３で排他論理和処理をとるブロックと参照ブロックの対応関係の説明図；
図２５は排他論理和処理された画像を符号化する符号化処理のフローチャート；
図２６は図２５の符号化による画像圧縮の説明図；
図２７は本発明による画像復元処理のフローチャート；
【発明を実施するための最良の形態】  図１は、本発明による画像圧縮方法及び画像復元方法が適用される装置環境の説明図である。本発明の画像圧縮装置１０はパーソナルコンピュータ１１にプログラムとして実装されており、プリンタ１２側に本発明の画像復元装置４０を設けている。画像圧縮装置１０は、パーソナルコンピュータ１１で印刷のために生成した２値のビットマップデータを画像データとして入力し、この画像データを圧縮してプリンタ１２の画像復元装置４０に転送する。プリンタ１２はフォントを持たないプリンタであり、パーソナルコンピュータ１１からビットマップ画像の直接転送を受けて印刷を行うもので、画像復元装置４０を設けることで、本発明の画像圧縮装置１０から転送された画像圧縮データを復元して印刷することになる。
図２は、本発明による画像圧縮装置の機能構成のブロック図である。図２において、本発明の画像圧縮装置１０は、バッファメモリ１４、前処理部１５及び画像圧縮部１６を備える。バッファメモリ１４にはプリンタに転送する２値ビットマップデータが保持される。画像圧縮装置１０にあっては、前処理部１５による圧縮と画像圧縮部１６による圧縮との２段階の圧縮を行って、プリンタ１２に圧縮された画像データを転送する。前処理部１５には、ブロック分割部１８、処理ブロック選択部２０、参照ブロック選択部２２、差分画像生成部２４及びブロック置換部２６が設けられる。また画像圧縮部１６には、画像符号化部２８と符号出力部３０が設けられる。前処理部１５内の各処理部の機能は、次のようになる。ブロック分割部１８は、バッファメモリ１４に保持した入力画像を縦横所定画素数、例えば横画素数Ｍ、縦画素数Ｎの（Ｍ×Ｎ）画素数のブロックに分割する。処理ブロック選択部２０は、分割されたブロックを主走査方向及び副走査方向に走査して、順番に処理ブロックとして選択する。参照ブロック選択部２２は、処理ブロック選択部２０で選択されたブロックとの位置関係及び画素値の関係が所定の条件を満たすブロックを参照ブロックとして選択する。この参照ブロックの選択につき本発明にあっては、処理ブロック選択部２０において既に選択された処理済ブロックの中から、現在の処理ブロックに近いブロックを参照ブロックとして優先的に選択している。差分画像生成部２４は、選択された処理ブロックと参照ブロックの画素値を排他的論理和（ＸＯＲ）して差分画像を生成する。ブロック置換部２６は、差分画像生成部２４で生成した差分画像が所定の条件を満たす場合に、現在の処理ブロックを生成した差分画像に置き換える。この場合の差分画像の処理ブロックへの置き換えとしては、処理ブロックと参照ブロックとの画素数の差が所定個数以上の場合には排他的論理和による圧縮に適していないことから、処理ブロックの差分画像への置き換えは行わない。一方、処理ブロック選択部２０にあっても、選択したブロックの画素値が予め定めた所定のパターンに合致する場合、具体的には排他的論理和を行っても圧縮が望めない場合には、それ以降の処理を行わず、処理ブロックをそのまま出力する。またブロック分割部１８における入力画像の横画素数Ｍ及び縦画素数Ｎは、ＣＰＵの内部レジスタのビット長に適合させるため、８の倍数としている。
次に画像圧縮部１６の各処理部は次の機能を有する。画像符号化部２８は、前処理部１５のブロック置換部２６より得られた差分画像をブロックに含む画像を符号化する。この符号化は、本願発明者等が既に出願している日本特許出願の特願２００１−３８８９３１の画像圧縮方法を適用する。符号出力部３０は、画像符号化部２８の処理で得られた符号データと、前処理部１５のブロック置換部で得られた各処理ブロックの差分画像への置換の有無、及び差分ブロックの位置情報とを組み合わせて、画像圧縮データとして例えばプリンタ１２に転送する。
図３は、本発明の圧縮時におけるブロックの排他的論理和処理のブロック画像を用いた説明図である。図３において、処理ブロック３２は、この例では縦横画素Ｍ×Ｎ＝８×８とした場合を例にとっており、現在、処理対象となっている処理ブロック３２に対し、既に処理済のブロックの中から選択された参照ブロック３４との間で排他的論理和（ＸＯＲ）３６をとることにより、差分画像３８を生成している。このような処理ブロック３２と参照ブロック３４の同じ画素位置の画素についての排他的論理和をとった場合には、両ブロックの同一位置の画素値が異なる部分、即ち白画素対黒画素または黒画素対白画素の部分だけが差分画像３８の中に黒画素として残る。このため、グラデーションのようにパターン形状が連続的に変化するディザ画像にあっては、隣接ブロック間の画素値の相関が高く、相関が高いほど差分画像の黒画素は少なくなり、同一画素配置のブロックの場合には差分画像内は全て白画素となり高圧縮ができる。
図４は、図２の画像圧縮装置１０における画像圧縮処理の概略フローチャートである。この画像圧縮処理にあっては、まずステップＳ１で入力画像をブロック分割した後に、順番に処理ブロックを選択し、処理ブロックに対し選択された参照ブロックと排他的論理和（ＸＯＲ）を行って差分画像を生成する。次にステップＳ２で、排他的論理和（ＸＯＲ）を行った各ブロックの参照ブロックの位置情報を符号化する。続いて、ステップＳ３で排他的論理和（ＸＯＲ）した後の画像を符号化し、ステップＳ２で得られた参照ブロック位置情報と併せて入力画像に対する符号化データとして出力する。
図２における本発明の画像圧縮装置は，例えば図５のようなコンピュータのハードウェア資源により実現される。図５のコンピュータにおいて、ＣＰＵ２００のバス２０１にはＲＡＭ２０２、ハードディスドコントローラ（ソフト）２０４、フロッピィディスクドライバ（ソフト）２１０、ＣＤ−ＲＯＭドライバ（ソフト）２１４、マウスコントローラ２１８、キーボードコントローラ２２２、ディスプレイコントローラ２２６、通信用ボード２３０、プリンタドライバ２３４が接続される。ハードディスクコントローラ２０４はハードディスクドライブ２０６を接続し、本発明のデータ圧縮処理を実行するアプリケーションプログラムをローディングしており、コンピュータの起動時にハードディスクドライブ２０６から必要なプログラムを呼び出して、ＲＡＭ２０２上に展開し、ＣＰＵ２００により実行することにより画像圧縮を行う。フロッピィディスクドライバ２１０にはフロッピィディスクドライブ（ハード）２１２が接続され、フロッピィディスク（Ｒ）に対する読み書きができる。ＣＤ−ＲＯＭドライバ２１４に対しては、ＣＤドライブ（ハード）２１６が接続され、ＣＤに記憶されたデータやプログラムを読み込むことができる。マウスコントローラ２１８はマウス２２０の入力操作をＣＰＵ２００に伝える。キーボードコントローラ２２２はキーボード２２４の入力操作をＣＰＵ２００に伝える。ディスプレイコントローラ２２６は表示部２２８に対して表示を行う。通信用ボード２３０は通信回線２３２を使用し、インターネット等のネットワークを介して他のコンピュータやサーバとの間で通信を行う。プリンタドライバ２３４は本発明の画像圧縮装置により画像圧縮された符号データをプリンタ１２に転送し、プリンタ１２側に設けた本発明の画像復元装置で符号データを復元して印刷させる。
図６は、本発明による画像復元装置の機能構成のブロック図である。図６において、本発明の画像復元装置４０は例えばプリンタ１２側に設けられており、図２の画像圧縮装置１０から転送された画像圧縮データから画像を復元し、プリンタエンジン１３８に供給して、プリンタ機構部１４０により印刷動作を行わせる。画像復元装置４０には、バッファメモリ４２、符号入力部４４、画像復号部４６及びブロック復号部４８が設けられている。符号入力部４４は画像圧縮装置側から転送された画像圧縮データを入力するもので、この画像圧縮データは所定の符号データ、各処理ブロックの差分画像への置換の有無、及び参照ブロックの位置情報の組合せが含まれている。画像復号部４６は、入力された符号データを画像に復号する。この復号処理は、本願発明者が既に提案している日本特許出願の特願２００１−３８８９３１により圧縮された符号データの復元処理である。ブロック復号部４８は、画像復号部４６で復号された画像を縦横所定画素数、即ち画像圧縮側と同じ例えば（Ｍ×Ｎ）＝８×８画素の処理ブロックに分割し、差分画像に置き換えられた処理ブロックと参照ブロックの画素値を排他的論理和（ＸＯＲ）して処理ブロックの画素値と置き換えることで、処理ブロックを復号する。
図７は、本発明の復元時におけるブロックの排他的論理和処理の説明図である。この復元時の排他的論理和処理は、図３の圧縮時における排他的論理和処理で得られた差分画像３８の復元である。差分画像３８の排他的論理和（ＸＯＲ）５４を行うためには、圧縮側から送られてきた参照ブロックの位置情報により既に復元が済んだ処理ブロックの中から参照ブロック５２を選択する。この参照ブロック５２は図３の圧縮側における参照ブロック３４と同じである。そして、差分画像３８と参照ブロック５２の排他的論理和（ＸＯＲ）５４を行うと、元のブロック５６が復元され、これは図３の圧縮前の処理ブロック３２と同じである。このように本発明にあっては、処理ブロックに対し同じ参照ブロックを使用して２回、排他的論理和（ＸＯＲ）の演算を実行すると、完全に元のデータに戻るという性質を利用し、画像を劣化することなく完全に元通りに復元させることができる。
図８は、本発明による画像復元処理の概略フローチャートである。この復元処理にあっては、ステップＳ１で排他的論理和（ＸＯＲ）された画像を復号した後、ステップＳ２で参照ブロックの位置情報を復号し、更にステップＳ３で各ブロックを参照ブロックの位置情報に基づいて排他的論理和処理（ＸＯＲ）を行うことで元の画像を復元している。
続いて図２の画像圧縮装置１０における前処理部１５及び画像圧縮部１６における各処理を詳細に説明する。図９は、図２の前処理部１５におけるブロック分割と分割後の処理ブロック及び参照ブロックの説明図である。図９において、処理対象とする入力画像５８は、８の倍数となる横Ｍ画素、縦Ｎ画素のブロック６０−１１〜６０ＭＮに分割される。本発明にあっては、ブロック分割した入力画像５８につき、横方向のブロックライン６２−１〜６２−Ｎ単位に処理を行う。入力画像５８の下側には、現在処理中の処理ブロック６４とこれに対し選択されて排他的論理和（ＸＯＲ）をとるための参照ブロック６６を示している。
図１０は、入力画像におけるブロックラインと論理行のライン数との関係の説明図である。本発明にあっては、基本的には図１０（Ａ）のように排他的論理和（ＸＯＲ）の縦画素数Ｎを論理行のライン数と同じＫとするか、あるいは図１０（Ｂ）のようにＫの整数倍にしてブロック境界と論理行のライン境界を一致させる。ここで論理行とは、図２の画像圧縮部１６に設けている画像符号化部２８における本願発明者が既に提案している日本特許出願の特願２００１−３８８９３１における処理概念である。即ち、この符号化処理にあっては、画像を所定のライン数Ｋで主走査方向に走査して、黒画素を含む領域を論理行として分離し、この論理行を更に副走査方向に走査して、黒画素を含む領域とそれ以外の領域に分離し、それぞれ要素として符号化する圧縮を行っている。したがって、この場合の論理行と本発明の排他的論理和（ＸＯＲ）のブロックの縦画素数Ｎとの間に、論理行のライン数ＫとＮを同じにするかＮを論理行のＫの整数倍とすることで、ブロック境界と論理行のライン境界を一致させ、圧縮効率を高めることができる。これに対し図１０（Ｃ）のように、論理行７２のライン数Ｋとブロックライン７４の縦画素数Ｎが整数倍の関係になく、ブロック境界と論理行のライン境界が一致しない場合には、排他的論理和（ＸＯＲ）を行った後の差分画像が論理行間にまたがることとなり、圧縮効率が低下する不都合を生ずる。
図１１は、本発明の排他的論理和（ＸＯＲ）による画像圧縮におけるブロック処理の順番の説明図である。図１１において、入力画像５８を縦横（Ｍ×Ｎ）画素のブロックに分割した後、矢印のブロック処理順序７６のように、分割されたブロックを主走査方向に走査した後、次の行の先頭に戻って、主走査方向に走査する処理を繰り返す。このようなブロックの処理順序７６に対し、現在処理中のブロックが処理ブロック６４であったとすると、この処理ブロック６４との排他的論理和（ＸＯＲ）をとるための参照ブロックは、それ以前の処理済ブロックの中から選択する。このように処理ブロック６４に対する参照ブロックを処理済ブロックの中から選択することで、画像全体の入力完了を待たずに圧縮処理を先行して開始することができる。復元時についても同様に、ブロックの画像が復元されるごとに、現在処理対象となっている差分画像で置き換えられたブロックと既に復元済みの参照ブロックとの間で排他的論理和（ＸＯＲ）が実行されることで、復元処理についても１パスでブロック復号を行うことができ、復号が完了した画像部分から先行してプリンタで印刷することで、復元側での待ち時間を短縮できる。
図１２は、本発明の排他的論理和（ＸＯＲ）の処理で処理ブロックに対し選択する参照ブロックの選択順序を指定するテンプレートの説明図である。本発明の処理ブロックと参照ブロックの排他的論理和（ＸＯＲ）による差分画像にあっては、ブロック間の画素値の相関が高いほど差分画像の黒画素が少なくなって高圧縮でき、処理ブロックに隣接するブロックほど相関が高いことから、この関係を利用して、処理ブロックに対する処理済ブロックの中から参照ブロックを選択する。図１２（Ａ）は、２×２マトリクスのテンプレート７８−１であり、処理ブロック６４に対する処理済側の上、左、左上の３つのブロックを参照ブロック候補として設定し、選択順として１番は上、２番は左、３番は左上を設定している。図１２（Ｂ）は、図１２（Ａ）に対し処理ブロック６４の右上を追加したテンプレート７８−２であり、新たに追加した右上を選択順位４番としている。図１２（Ｃ）は、図１２（Ｂ）に加え更に、選択順位５番、６番、７番、８番の３ブロックを追加したテンプレート７８−３を示している。このテンプレートにおける参照ブロックの順番を指定する基本的な考え方は、処理ブロックに対し隣接するブロックについては上または右に続いて左上、右上の順番とし、更に外側のブロックについては、上、左、左上、右上の順番としている。この図１２の３種類のテンプレート７８−１〜７８−３のうちのいずれか１つを使用し、処理ブロック６４に対し番号順に参照ブロックを選択し、選択した参照ブロックとの排他的論理和（ＸＯＲ）をとって、生成された差分画像の黒画素数が最小となる参照ブロックを選択して差分画像を生成する。
図１３は、本発明におけるブロックライン単位の画像圧縮処理の説明図である。本発明における画像をブロック単位で符号化する際には、図１１に示したように、主走査方向及び副走査方向のラスタ走査順序に従って走査することになるが、この場合、１ブロックごとに参照ブロックと排他的論理和（ＸＯＲ）を行って符号化できるが、ブロックライン単位で符号化する方が効率がよい。例えばブロックライン単位で圧縮して符号データを出力すると、符号データを受け取った復元側では同じくブロックライン単位で画像を復元できるため、画像全体の圧縮処理の完了を待たずに復号を開始できるメリットがある。このため図１３のように、画像圧縮処理の際に入力ブロックライン８０を処理対象として取り出し、入力ブロックライン８０の先頭ブロックから順番にＸＯＲ処理を実行して、ＸＯＲ後のブロックライン８２を生成し、その後にブロックライン８２を一括して画像を圧縮し、既に得られた参照ブロック情報の符号データ９０とＸＯＲ後のブロックラインの符号データ８８を復元側に転送する。このような圧縮側でのブロックライン単位の圧縮による符号データを受けた復元側は、図１４に示す処理を行う。図１４の復元処理にあっては、ブロックライン単位の復号で得られたＸＯＲ後のブロックラインの符号データ８８と参照ブロック情報の符号データ９０を受信した後、ＸＯＲ後のブロックラインの符号データ８８の画像復元９２を行って、復号したブロックライン９６を生成する。続いて参照ブロック情報の符号データ９０から参照ブロックの位置を得て、排他的論理和処理であるＸＯＲ処理９４を行い、ブロックごとにＸＯＲしたブロックライン９８の各ブロックのデータを順次復号する。このブロックライン９８の画像復元が済んだ段階で、プリンタ側でブロックライン単位の印刷動作ができる。
図１５及び図１６は、ブロックライン単位で画像圧縮を行う本発明による画像圧縮処理のフローチャートである。この画像圧縮処理の処理手順は次のようになる。
ステップＳ１：
入力画像における最初のブロックラインを選択し、ブロックラインの番号を示す変数ｋに先頭のブロックラインを示す０を設定する。
ステップＳ２：
ブロックラインｋの最初のブロックを選択し、ブロック番号を示す番号ｉに先頭ブロックを示す０を設定する。
ステップＳ３：
ｉ番目のブロックが排他的論理和（ＸＯＲ）すべきブロックであるか否かを判断する。例えばブロック全体が全白や全黒であるなど排他的論理和（ＸＯＲ）による符号化効率が向上しないブロックの場合には、排他的論理和（ＸＯＲ）しないと判断してステップＳ５に進む。排他的論理和（ＸＯＲ）すると判断した場合には、ステップＳ４に進む。
ステップＳ４：
ｉ番目のブロックと排他的論理和（ＸＯＲ）すべき参照ブロックが存在するか否かを判断し、存在する場合にはステップＳ６に進み、存在しない場合にはステップＳ５に進む。
ステップＳ５：
別途準備している排他的論理和（ＸＯＲ）したブロックラインを格納するためのブロックラインバッファにｉ番目のブロックの画素値をそのまま出力した後、次のブロックを選択するためにステップＳ８に進む。
ステップＳ６：
ｉ番目のブロックと参照ブロックの画素の排他的論理和（ＸＯＲ）を行ってブロックラインバッファに出力する。なお、ステップＳ５，Ｓ６におけるブロックラインバッファへの出力は、図１７のようにブロックラインｋにおけるｉ番目のブロックと同じブロックラインバッファ８２の位置に参照ブロック６６との排他的論理和（ＸＯＲ）で得られた画素値を出力する。
ステップＳ７：
参照ブロックの位置を参照ブロック位置格納テーブルに追加する。参照ブロックの位置は図１２に示した参照ブロックテンプレートのブロック選択順序を示す番号を用いることができる。
ステップＳ８：
次のブロックを選択し、ブロック番号ｉに１を加える。
ステップＳ９：
ブロック番号ｉとブロックライン内のブロック数ＢＬＫ＿ＮＵＭを比較し、両者が一致すればブロックライン内の全ブロックの排他的論理和（ＸＯＲ）が完了したと判断してステップＳ１０に進み、不一致の場合には排他的論理和（ＸＯＲ）処理が終わっていないと判断してステップＳ３に戻る。
ステップＳ１０：
ブロックラインバッファ内の画像と参照ブロック位置格納テーブル内に格納された位置情報をそれぞれ符号化し、ブロックラインｋの符号データとして出力する。
ステップＳ１１：
次のブロックラインを選択し、ブロックライン番号ｋに１を加える。
ステップＳ１２：
ブロックライン番号ｋと入力画像内のブロックライン数ＬＩＮＥ＿ＮＵＭを比較し、両者が一致すれば全ブロックラインの符号化処理が完了したと判断して処理を終了し、不一致の場合には符号化処理を終わっていないブロックラインが存在すると判断してステップＳ２に戻る。
図１８は、図１５及び図１６のステップＳ７で使用される参照ブロック位置格納テーブル１００の説明図である。この参照ブロック位置格納テーブル１００は、処理ブロック番号、参照ブロック有無及び参照ブロック番号の格納領域を持ち、処理ブロック番号はブロックライン内の全ブロックに対応して番号０〜（ブロック数−１）を割り当て、それぞれに対応して参照ブロック番号の有無と参照ブロック番号を格納する。参照ブロック番号の有無には、存在する場合には１、存在しない場合には０を書き込む。
図１９は、図１５及び図１６の圧縮処理により生成された１ブロックラインの参照ブロック位置格納テーブル１００の具体例であり、処理ブロック番号として０〜１１の１２ブロックを１ブロックラインとした場合を例にとっている。また参照ブロック有無は、参照ブロックが存在すれば１、存在しない場合には０となっており、更に参照ブロック番号としては、参照ブロックとして選択した処理ブロック番号の数値を格納している。このような参照ブロック位置格納テーブル１００についての図１５及び図１６のステップＳ１０における符号化方法としては、参照ブロックが存在しないブロック数をオフセット値として符号化し、参照ブロックが存在する場合には参照ブロック番号とその連続参照回数を組み合わせて符号化する。例えば図１９において、処理ブロック番号０，１については参照ブロック番号がないことから、この場合には「オフセット２」としている。また処理ブロック番号２〜４については同じ参照ブロック番号２が連続していることから「参照ブロック番号＝２、ブロック数３」の組合せで符号化している。これにより、図１９の参照ブロック位置格納テーブル１００の例では、符号化しない場合には２４個の値が必要であるのに対し、上記の方法で符号化した場合には８個の値で済み、符号サイズを削減することができる。
２０、図１５及び図１６のステップＳ３における参照ブロック選択処理の詳細を示したフローチャートである。この図２０の処理にあっては参照ブロック自体が排他的論理和（ＸＯＲ）すべきブロックであるか否か、参照ブロックと排他的論理和（ＸＯＲ）をとる処理ブロックの画素値の関係及び画素差に基づいて参照ブロックを選択する。そこでこの参照ブロック選択処理の手順を説明すると次のようになる。
ステップＳ１：
参照ブロック番号を表す変数ｒに最初の参照ブロック番号を示す１を設定し、選択された参照ブロック番号を表す変数ｓに参照ブロックが未選択であることを表す０を設定する。また差分画素の個数の最小値を格納するＤｍｉｎに画素差が最大である値を示す位置ブロックの総画素数（＝横画素数Ｍ×縦画素数Ｎ）を設定する。
ステップＳ２：
参照ブロックｒが排他的論理和（ＸＯＲ）すべきブロックであるか否かを判断し、排他的論理和（ＸＯＲ）すると判断した場合にはステップＳ３に進み、しないと判断した場合にはステップＳ７に進む。
ステップＳ３：
処理ブロックと参照ブロックｒとの間で同一位置にある画素値を比較し、異なる画素値の個数Ｄを数える。
ステップＳ４：
画素差Ｄと予め定めておいた最大画素差ＭＡＸ＿ＤＩＦＦとを比較し、画素差Ｄが最大画素差ＭＡＸ＿ＤＩＦＦ以下である場合には画素差が所定に範囲内にあると判断してステップＳ５に進み、それ以外に場合には画素差が所定の範囲内にないと判断してステップＳ７に進む。
ステップＳ５：
処理ブロックに対し画素差が最も少ない参照ブロックを選択するために、参照画素差を格納するＤｍｉｎとステップＳ３で取得した画素差Ｄとを比較し、画素差Ｄが最小画素差Ｄｍｉｎより小さい場合には参照ブロックｒと処理ブロックとの画素差がより小さいと判断してステップＳ６に進み、それ以外に場合には参照ブロックｒは処理ブロックとの画素差が最小ではないと判断してステップＳ７に進む。
ステップＳ６：
処理ブロックとの画素差が最小となる参照ブロック番号を保持するための変数ｓに参照ブロックｒを格納し、最小画素差ＤｍｉｎにはステップＳ３で求めた処理ブロックと参照ブロックｒとの画素差Ｄを格納する。
ステップＳ７：
参照ブロック番号ｒに１を加え、例えば図２０のようなテンプレート７８−３の順番に従って次の参照ブロックを選択する。
ステップＳ８：
参照ブロック番号ｒと参照ブロックの個数ＲＥＦ＿ＮＵＭを比較し、参照ブロック番号ｒが参照ブロック個数ＲＥＦ＿ＮＵＭ未満の場合には全ての参照ブロックについて選択処理が完了していないとしてステップＳ２に戻り、それ以外の場合には全ての参照ブロックについて処理が終わったと判断してステップＳ９に進む。
ステップＳ９：
ｓが０より大きいか否か、即ちｒに選択された参照ブロック番号が格納されているか否かを確認し、ｓが０より大きい場合には参照ブロックが選択されたと判断してステップＳ１０に進み、ｓが０であった場合には参照ブロックが選択されなかったと判断してステップＳ１１に進む。
ステップＳ１０：
参照ブロックが存在したことを出力することに加え、選択された参照ブロック番号ｓを出力し、参照ブロック選択処理を終了する。
ステップＳ１１：
参照ブロックが存在しなかったことを出力して参照ブロック選択処理を終了する。
以上の処理によって図１５及び図１６のステップＳ４において処理ブロックに対し画素差が最小となり且つ画素差が所定の個数以下である参照ブロックを選択することができる。ここで図ふわにおける参照ブロックの選択基準をまとめると、参照ブロックを排他的論理和（ＸＯＲ）の対象とするか否かは２段階で判断する。第１段階にあっては参照ブロックが全て白画像や全て黒画像である場合などの排他的論理和（ＸＯＲ）による符号化効率が向上しない場合には参照ブロックとして選択しない。第２段階としては処理ブロックと参照ブロックの画素値の関係から、例えば図２ふに例として示す場合には、排他的論理和（ＸＯＲ）後の画素数が多くなるため即ち画素の相違が大きくなる組み合わせの場合には符号化効率の向上が期待できないため排他的論理和（ＸＯＲ）の対象としない。図２２（Ａ）は処理ブロック１０２が主走査方向に白から黒に変化しているのに対し、参照ブロック１０４は逆に黒から白に変化し、参照ブロック１０６は白黒の縦縞であり、参照ブロック１０８は全て黒画像の場合である。また図２２（Ｂ）の処理ブロック１１０は周走査方向に黒から白に変化しているのに対し、参照ブロック１１２は逆に白から黒に変化しており、参照ブロック１１４は縦縞であり、更に参照ブロック１１６は全て黒画像の場合である。更に図２２（Ｃ）の例では処理ブロック１１８が全て黒画像であるのに対し、参照ブロック１２０は縦縞、参照ブロック１２２は白から黒画像への変化、参照ブロック１２４は黒から白画像への変化である。いずれの場合にも処理ブロックと参照ブロックについて排他的論理和（ＸＯＲ）をとると、処理後の画素数が増加してしまい、従って、この関係にあるときには参照ブロックを排他的論理和（ＸＯＲ）の対象としては選択しない。
図２３は、本発明によるブロックの排他的論理和処理が行われた処理画像の具体例である。図２３（Ａ）は入力画像１２６であり、縦横（Ｍ×Ｎ）画素＝８×８のブロックに分解された後、図１１の処理順序に従った処理ブロックについて図２１と同じテンプレート７８−３の順番に従って参照ブロックを選択し、排他的論理和（ＸＯＲ）を実行することで、図２３（Ｂ）のＸＯＲ処理画像１２８を生成している。
ここで図２４（Ａ）は図２３（Ａ）の入力画像１２６をブロック分割した場合のブロック番号１〜８を示している。また図２４（Ｂ）は図２３（Ｂ）のＸＯＲ処理画像１２８を生成する際に選択した参照ブロックのブロック番号を処理ブロック番号に対するＸＯＲの右側の値として示している。
このような図２３（Ｂ）のＸＯＲ処理画像１２８から明らかなように、先頭のブロックについては処理済みのブロックがないことから、入力画像１２６の画素がそのまま配置されるが、２番目以降のブロックについては参照ブロックとのＸＯＲ処理により黒画像の数が大幅に低減した差分画像の配置によるブロック画像となっている。特に５番目、６番目、７番目の３つについては参照ブロック番号１，３，４との排他的論理和（ＸＯＲ）により両ブロックの画素配置が一致することで全白の画像となっている。この図２３（Ａ）のようなパターン形状が連続的に変化するディザ画像について、本発明によるＸＯＲ処理を行う圧縮は極めて効果的に高圧縮できることがわかる。
図２５は、図２の前処理部１５に続いて画像圧縮部１６に設けた画像符号化部２８で行われる排他的論理和処理の済んだ画像を符号化する符号化処理のフローチャートである。この符号化処理、即ち本発明者がすでに提案している日本特許の出願特願２００１−３８８９３１による符号化処理は次のようになる。
ステップＳ１：
入力された排他的論理和（ＸＯＲ）処理の済んだ画像を所定整数Ｋライン単位に水平方向に走査する（主走査方向走査）。
ステップＳ２：
行間のように連続する空白ラインと、空白ライン以外の領域を論理行として分離する（第１の領域分離）。
ステップＳ３：
分離した論理行を１列単位に垂直方向に走査する（副走査方向走査）。
ステップＳ４：
文字間のように黒画像を含まない空白領域と、空白領域以外の黒画像を含む領域に分離する（第２の領域分離）。
ステップＳ５：
領域分離結果に基づいて連続して繰り返し出現する同一幅及び同一画素値を有する反復パターンを分離する（第３の領域分離）。
ステップＳ６：
ステップＳ２、ステップＳ４、ステップＳ５で分離した各領域を要素として符号化を行う。
図２５は、図２４における符号化処理の原理を示している。図２５において、処理対象となる入力画像１２６における論理行１３０の中から連続して繰り返し出現するパターンを検出し、繰り返しの基本となる反復パターンの長さと画素値及びその繰り返し回数を使用して符号化することにより、符号データサイズを削減する。これにより符号データは符号語、反復回数Ｋ、画素幅Ｍ、反復パターンの基本パターン（Ｍバイト）からなる。この図２６にあっては、入力画像１２６として通常の同一形状が繰り返すディザパターンを例にとっているが、本発明にあっては、この入力画像１２６として例えば図２３（Ｂ）のようなＸＯＲ処理画像１２８を対象としており、このようなＸＯＲ処理画像１２８に対し、図２５の符号化処理を第２段階の符号化処理として行うことで、更に画像データを圧縮することができる。また図２４の符号化処理にあっては検出した反復パターンをそのまま符号データとして出力するかわりに、ランレングス符号化などのデータ圧縮方法により圧縮することで、符号データサイズを更に削減することができる。
図２７は、図６の画像復元装置４０における画像復元装置のフローチャートである。この画像復元装置は、図１５及び図１６の画像圧縮処理によりブロック単位毎に圧縮された符号データから元の画像データを復号する処理であり、図１１に示したブロック順に元の画像が復元される。この画像復元処理の処理手順は次のようになる。
ステップＳ１：
１ブロックライン分の画像を復号する。
ステップＳ２：
復号したブロックライン内の各ブロックの参照ブロック番号即ち参照ブロックの有無及び位置を復号する。
ステップＳ３：
復元したブロックラインの最初のブロックを選択し、ブロック番号を示すｉに０を設定する。
ステップＳ４：
ブロックライン内のブロックｉに対する参照ブロックの有無をステップＳ２で復号した参照ブロック情報を参照して識別し、参照ブロックが存在する場合にはステップＳ５に進み、参照ブロックが存在しない場合にはステップＳ６に進む。
ステップＳ５：
ブロックライン内のブロックｉと参照ブロックの画素値を排他的論理和（ＸＯＲ）し、排他的論理和（ＸＯＲ）で得られた画素値をブロックｉの画素値に置き換える。
ステップＳ６：
ブロックライン内で次のブロックを選択し、ブロック番号を示す変数ｉに１を加える。
ステップＳ７：
ブロック番号ｉとブロックライン内のブロック数ＢＬＫ＿ＮＵＭを比較し、一致した場合にはブロックライン内の全てのブロックの復元が完了したと判断して、ステップＳ８に進み、不一致の場合には復号が完了していないブロックが残っていると判断してステップＳ４に戻る。
ステップＳ８：
全てのブロックラインの復号処理が完了した場合には復号処理を完了し、完了していない場合にはステップＳ１に戻る。
ここで、ステップＳ８における全てのブロックラインの復号処理が完了したか否かの判断は復号されたブロック数を計数して判断する方法でも良いし、終了を示す符号で判断する方法であっても良い。復号されたブロック数を計数して処理終了を判断する場合には圧縮側で符号データの最初にブロックラインの個数を付加し、また終了を示す復号で判断する場合には符号データの最後に終了を示す符号を付加することで実現できる。
尚、上記の実施形態はパーソナルコンピュータに接続したプリンタ側に２値ビットマップデータを圧縮して転送し、プリンタ側で復元して印刷する場合を例にとるものであったが、本発明はこれに限定されず２値ビットマップデータを転送する例えばファクシミリなどの適宜の対象につきそのまま適用することができる。また本発明はその目的と利点を損なうことのない適宜の変形を含み、更に上記の実施形態に示した数値による限定は受けない。
【産業上の利用の可能性】
以上説明してきたように本発明のビットマップ画像の圧縮方法及び復元方法プログラム及び装置によれば、画像をブロック単位に分けて近傍ブロックと排他的論理和（ＸＯＲ）することで、画像内の符号化対象となる黒画素の個数を削減し、画像の圧縮効率を向上することができる。更に主走査方向及び副走査方向に走査して黒画素を含む領域とそれ以外の領域に分離してそれぞれを要素として符号化する圧縮方法と組み合わせ、排他的論理和を行うブロックの高さをこの圧縮方法における主走査方向に走査するライン数の整数倍とすることで、圧縮率をより一層向上させることができる。この結果、グラデーションのように連続的にパターンが変化するディザ画像の圧縮率を高めることができ、印刷画像に適用することでプリンタへの転送時間が大幅に短縮され、印刷速度の向上に大きく寄与することができる。
【図１】
2004068844.tif 000003
【図２】
2004068844.tif 000004
【図３】
2004068844.tif 000005
【図４】
2004068844.tif 000006
【図５】
2004068844.tif 000007
【図６】
2004068844.tif 000008
【図７】
2004068844.tif 000009
【図８】
2004068844.tif 000010
【図９】
2004068844.tif 000011
【図１０】
2004068844.tif 000012
【図１１】
2004068844.tif 000013
【図１２】
2004068844.tif 000014
【図１３】
2004068844.tif 000015
【図１４】
2004068844.tif 000016
【図１５】
2004068844.tif 000017
【図１６】
2004068844.tif 000018
【図１７】
2004068844.tif 000019
【図１８】
2004068844.tif 000020
【図１９】
2004068844.tif 000021
【図２０】
2004068844.tif 000022
【図２１】
2004068844.tif 000023
【図２２】
2004068844.tif 000024
【図２３】
2004068844.tif 000025
【図２４】
2004068844.tif 000026
【図２５】
2004068844.tif 000027
【図２６】
2004068844.tif 000028
【図２７】
2004068844.tif 000029
【国際調査報告】
2004068844.tif 000030
2004068844.tif 000031