(57)【特許請求の範囲】
【請求項１】
画像を符号化する画像処理装置であって、
前記画像のパターンの行方向の周期ｐを検出する周期検出手段と、
前記画像に対してｎ行ｍ列のマトリクスを用いて擬似中間調処理を施す擬似中間調処理手段と、
前記擬似中間調処理を施された画像を符号化する符号化手段とを備え、
前記符号化手段は、
符号化対象画素から距離ｍ×ａ（ａ＞０）だけ行方向に離れた第１参照画素と、前記符号化対象画素から、前記周期ｐの整数倍である距離ｍ×ｂ（ｂ＞０，ａ≠ｂ）だけ行方向に離れた第２参照画素と、を用いて前記符号化対象画素を符号化することを特徴とする画像処理装置。
【請求項２】
前記擬似中間調処理手段は、画像に対してディザマトリクスを用いてディザ処理を施すことを特徴とする請求項１に記載の画像処理装置。
【請求項３】
符号化された画像を復号する画像処理装置であって、
ｎ行ｍ列のマトリクスを用いて擬似中間調処理が施され、符号化された画像を入力する入力手段と、
前記入力手段によって入力された画像を復号する復号手段とを備え、
前記復号手段は、
復号対象画素から距離ｍ×ａ（ａ＞０）だけ行方向に離れた第１参照画素と、前記復号対象画素から、前記画像のパターンの周期ｐの整数倍である距離ｍ×ｂ（ｂ＞０，ａ≠ｂ）だけ行方向に離れた第２参照画素と、を用いて前記復号対象画素を復号することを特徴とする画像処理装置。
【請求項４】
画像を符号化する画像処理方法であって、
前記画像のパターンの行方向の周期ｐを検出する周期検出工程と、
前記画像に対してｎ行ｍ列のマトリクスを用いて擬似中間調処理を施す擬似中間調処理工程と、
前記擬似中間調処理を施された画像を符号化する符号化工程とを備え、
前記符号化工程では、
符号化対象画素から距離ｍ×ａ（ａ＞０）だけ行方向に離れた第１参照画素と、前記符号化対象画素から、前記周期ｐの整数倍である距離ｍ×ｂ（ｂ＞０，ａ≠ｂ）だけ行方向に離れた第２参照画素と、を用いて前記符号化対象画素を符号化することを特徴とする画像処理方法。
【請求項５】
符号化された画像を復号する画像処理方法であって、
ｎ行ｍ列のマトリクスを用いて擬似中間調処理が施され、符号化された画像を入力する入力工程と、
前記入力工程で入力された画像を復号する復号工程とを備え、
前記復号工程では、
復号対象画素から距離ｍ×ａ（ａ＞０）だけ行方向に離れた第１参照画素と、前記復号対象画素から、前記画像のパターンの周期ｐの整数倍である距離ｍ×ｂ（ｂ＞０，ａ≠ｂ）だけ行方向に離れた第２参照画素と、を用いて前記復号対象画素を復号することを特徴とする画像処理方法。
【請求項６】
コンピュータに請求項４又は５に記載の画像処理方法を実行させるためのコンピュータプログラム。
【請求項７】
請求項６に記載のコンピュータプログラムを格納したことを特徴とする、コンピュータ読み取り可能な記憶媒体。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、画像を符号化する、もしくは符号化された画像を復号する画像処理装置、画像処理方法、プログラム、及び記憶媒体に関するものである。
【０００２】
【従来の技術】
壁紙あるいはテクスチャなどと呼ばれる、同一の背景パターンを並べて出力するアプリケーションプログラムが出力する印刷データを画像データに展開して印刷する場合において、データサイズを小さくするためにこの画像データを圧縮する場合、背景パターン自体がよく圧縮できる場合は画像データ全体をよく圧縮することは容易である。しかしながら、背景パターンそれ自体があまり圧縮できない場合も多く、そのような場合には画像データ全体をよく圧縮することは必ずしも容易ではない。
【０００３】
図１０はそのような印刷データの一例であり、図１１に示すように、同一のパターンを並べることにより、背景が構成されている。
【０００４】
従来の圧縮技術では、例えばランレングス符号化、あるいはデルタロウ符号化のように、画素値が近隣の画素と同じ値になる傾向が強いことを利用して、近隣の画素を参照し、値が同一であれば圧縮する符号化方法がある。
【０００５】
またＬＺ７７符号化、あるいはＬＺ７８符号化のように、広い範囲の画素を参照し、値が同一の並びの画素を検出してこれを利用することにより圧縮する符号化方法がある。これらの方法によればかなり離れた位置にある同一の値を有する画素を検出して圧縮に利用することができるため、上述の壁紙などをよく圧縮することができる。
【０００６】
またＪＰＥＧ符号のように、背景パターンそれ自体をよく圧縮できる符号化方法がある。
【０００７】
また、特願２０００−７６４２４にテクスチャの周期を検出して圧縮を行う方法が示されている。
【０００８】
【発明が解決しようとする課題】
しかしながら、上記ランレングス符号化、あるいはデルタロウ符号化によれば、上述の壁紙などを圧縮する場合、その繰り返し周期が例えば１０２４画素と大きな値をとるため、近隣の画素を参照しただけではよく圧縮することができないという欠点がある。
【０００９】
また、上記ＬＺ７７符号化、あるいはＬ７８符号化によれば、符号化時に広い範囲の画素を参照するため、計算量が多く、符号化に要する時間が長いという欠点がある。またこれらの方法によれば、復号時に広い範囲の画素を参照するために、大容量のバッファメモリが必要となるという欠点があり、例えばプリンタに復号機能を持たせる場合にコストアップの原因となる。
【００１０】
また、上記ＪＰＥＧによれば、符号化時の計算量が多いため、符号化に要する時間が長いという欠点がある。又、この方法によれば、復号時の計算量もまた多いという欠点があり、例えばプリンタに復号機能を持たせる場合にコストアップの原因となる。
【００１１】
また、上記特願２０００−７６４２４によれば、フーリエ解析あるいは自己相関係数によるもので、背景パターンのデータを用いて膨大な量の計算を行う必要があるため、高速に符号化することができない。
【００１２】
本発明は以上の問題に鑑みて成されたものであり、周期性を有する画像、特に壁紙などの背景パターンを並べた画像データを符号化する際に、画像全体をより高速に、且つより高圧縮率で圧縮することを目的とする。
【００１３】
また本発明の別の目的は、壁紙などの背景パターンを並べた画像を符号化した符号を復号する復号回路の回路規模を小さくし、かつ大量のバッファメモリを必要としない、低コストで構成可能な復号を行うことを目的とする。
【００１４】
【課題を解決するための手段】
本発明の目的を達成するために、例えば本発明の画像処理装置は以下の構成を備える。
【００１５】
すなわち、画像を符号化する画像処理装置であって、
前記画像のパターンの行方向の周期ｐを検出する周期検出手段と、
前記画像に対してｎ行ｍ列のマトリクスを用いて擬似中間調処理を施す擬似中間調処理手段と、
前記擬似中間調処理を施された画像を符号化する符号化手段とを備え、
前記符号化手段は、
符号化対象画素から距離ｍ×ａ（ａ＞０）だけ行方向に離れた第１参照画素と、前記符号化対象画素から、前記周期ｐの整数倍である距離ｍ×ｂ（ｂ＞０，ａ≠ｂ）だけ行方向に離れた第２参照画素と、を用いて前記符号化対象画素を符号化することを特徴とする。
【００１６】
本発明の目的を達成するために、例えば本発明の画像処理装置は以下の構成を備える。
【００１７】
すなわち、符号化された画像を復号する画像処理装置であって、
ｎ行ｍ列のマトリクスを用いて擬似中間調処理が施され、符号化された画像を入力する入力手段と、
前記入力手段によって入力された画像を復号する復号手段とを備え、
前記復号手段は、
復号対象画素から距離ｍ×ａ（ａ＞０）だけ行方向に離れた第１参照画素と、前記復号対象画素から、前記画像のパターンの周期ｐの整数倍である距離ｍ×ｂ（ｂ＞０，ａ≠ｂ）だけ行方向に離れた第２参照画素と、を用いて前記復号対象画素を復号することを特徴とする。
【００１８】
【発明の実施の形態】
以下、添付図面を参照して、本発明を好適な実施形態に従って詳細に説明する。
【００１９】
［第１の実施形態］
図１７に本実施形態の画像処理装置の基本構成を示す。本実施形態では画像処理装置として一般的なパーソナルコンピュータやワークステーションを用いる。
【００２０】
１７０１はＣＰＵで、ＲＡＭ１７０２やＲＯＭ１７０３に格納されたプログラムやデータを用いて本装置全体の制御を行うと共に、後述の画像圧縮処理も行う。１７０２はＲＡＭで、外部記憶装置１７０４や記憶媒体ドライブ１７０９からロードされたプログラムやデータ等を一時的に記憶するエリアを備えると共に、ＣＰＵ１７０１が各種の処理を実行する際に用いるワークエリアも備える。１７０３はＲＯＭで、本装置全体の制御プログラム（例えばブートプログラム）や制御データ（例えば本装置の設定データ）を格納する。１７０４はハードディスクなどの外部記憶装置で、記憶媒体ドライブ１７０９からインストールされたプログラムやデータなどを保存する。また、上述のワークエリアのサイズがＲＡＭ１７０２内に設けられなくなった場合に、不足分をファイルとして提供することもできる。１７０５，１７０６は夫々キーボード、マウスで、夫々ポインティングデバイスとして用いられ、各種の指示を本装置に入力することができる。１７０７は表示装置で、ＣＲＴや液晶画面などにより構成されており、画像や文字などを表示することができる。１７０８が画像入力装置で、ディジタルカメラやスキャナなどにより構成されており、撮像や取り込みなどの操作により画像をディジタルデータとしてＲＡＭ１７０２や外部記憶装置１７０４に入力することができる。
【００２１】
１７０９は記憶媒体ドライブで、ＣＤ−ＲＯＭやＤＶＤ−ＲＯＭなどの記憶媒体からプログラムやデータなどを読み込み、読み込んだプログラムやデータをＲＡＭ１７０２や外部記憶装置１７０４等に出力する。１７１０はＩ／Ｆ（インターフェース）で、インターネットやＬＡＮなどを介して外部の機器から圧縮処理対象の画像を受信したり、逆に圧縮した画像を外部の機器に対して送信する等、外部の機器とのデータの送受信を行う際のＩ／Ｆとして機能する。１７１１はプリンタで、圧縮された画像を伸長して紙などの記録媒体に印刷を行う画像伸長装置として機能する。１７１２は上述の各部を繋ぐバスである。
【００２２】
図１は画像を印刷する際に用いるソフトウェア群とプリンタとの関係を示す概念図である。外部記憶装置１７０４内にはオペレーティングシステム２（以下、ＯＳ）、アプリケーション３、プリンタドライバ４，ポートドライバ６が格納されている。
【００２３】
ＯＳ２は図１に示した各部（プリンタ１７１１は除く）、及びアプリケーション３、プリンタドライバ４、ポートドライバ５などのソフトウェアを管理する。アプリケーション３は、例えばワードプロセッサのようなアプリケーションソフトウェアであり、操作者からキーボード１７０５やマウス１７０６を用いて指示された内容に従って文書の作成・印刷などを行う。４はプリンタドライバであり、アプリケーション３が発行した印刷指令をＯＳ２を介して受け取り、該印刷指令をプリンタ１７１１が解釈可能なプリンタコマンドに変換する。５はポートドライバであり、プリンタドライバ４が変換したプリンタコマンドをＯＳ２を介して受け取り、不図示のパラレルポートを介してプリンタ１７１１に送信する。そしてプリンタ１７１１は、ポートドライバ５から受信したプリンタコマンドに従って印刷を行う。
【００２４】
図２はプリンタ１１１１の基本構成を示すブロック図である。図中、１１はパラレルポートであり、ポートドライバ６から出力されたプリンタコマンドを受信する。１２はＦＩＦＯ（ファーストインファーストアウト）メモリであり、パラレルポート１１が受信したプリンタコマンドに含まれる符号化データ（詳細は後述）を記憶し、記憶したデータを先入れ先出しの順に復号回路１３に出力する。復号回路１３は、ＦＩＦＯメモリ１２に記憶された符号列データを復号し、復元した画像データをシフトレジスタ１６に出力する。プリンタエンジン１４はレーザビームプリンタエンジンであり、制御回路１５の指示により、復号回路１３が出力した画像データに従って印刷を行う。１５は制御回路であり，例えば１チップＣＰＵで構成され、パラレルポート１１，ＦＩＦＯメモリ１２，復号回路１３，およびプリンタエンジン１４の制御を行う。１６はシフトレジスタであり、復号回路１３が復号したバイトデータを複数の画素に分割し、画素ごとに順次プリンタエンジン１４に出力する。
【００２５】
以下、印刷を行う際に、図１，２に示した各部の動作について以下、説明する。
【００２６】
操作者がキーボード１１０５やマウス１１０６を用いてアプリケーション３を操作して印刷データを生成し、更に、生成した印刷データを印刷する指示を入力すると、アプリケーション３からＯＳ２を介してプリンタドライバ４に印刷指令が渡される。プリンタドライバ４はアプリケーション３から発行された印刷指令に基づき、印刷対象となる画像データを作成し、次いでこの画像データに対してディザマトリックスを用いてディザ処理を行い、２値化処理行う。なお、その際、そして、プリンタドライバ４は、後述する符号化手順に基づき、２値化処理を施された画像データから符号化データを生成し、用紙サイズ、画像データ（ビットマップデータ）のラインの長さとライン数などを指定する印刷制御コマンド、圧縮パラメタを指定する圧縮パラメタコマンド、ページ終了を示すページ終了コマンドとともに出力する。ポートドライバ５は、プリンタドライバ４が作成した一連のコマンド群と上記符号化データをプリンタ１７１１に送信する。
【００２７】
制御回路１５はパラレルポート１１を経由してプリンタコマンドを受信する。受信したプリンタコマンドのうち印刷制御コマンド、圧縮パラメタ指定コマンドは、印刷制御のために制御回路１５の内部に保持される。また、受信したプリンタコマンドのうち符号化データは、ＦＩＦＯメモリ１２に格納される。その後、ページ終了コマンドの受信などにより、１ページを構成するプリンタコマンドの受信が完了したことを制御回路１５が検出したときに、プリンタエンジン１４に印刷の開始を指示する。印刷の開始が指示されると、プリンタエンジン１４は。シフトレジスタ１６に画像データの出力を要求する。シフトレジスタ１６は予め復号回路１３から復号データを読み出し、読み出した復号データを格納する。そして、プリンタエンジン１４からの出力要求を受けると格納しておいた復号データをプリンタエンジン１４に出力すると共に、シフトレジスタ１６内に空きのバッファができたときには、復号回路１３に引き続く復号データの出力を要求する。このようにして符号化データは順次復号されて画像データ（復号データ）として出力され、１ページの画像データの出力が全て終了すると、印刷が完了する。ここで、アプリケーション３から背景パターンのイメージ出力指令が発行されると、プリンタドライバ４は後述する手順にてこれを検出し、背景パターンの周期を求める。プリンタドライバ４はまた、背景パターンを検出した場合には、画像データを符号化する際に、後述する手順に従って背景パターンの周期を利用して符号化を行う。
【００２８】
次に、図３および図４に示すテーブルを参照し、図１に示したプリンタドライバ４が生成する符号について説明する。
【００２９】
図３は、図１に示したプリンタドライバ４が生成する符号化データに含まれる各符号の一例を説明するテーブルである。本実施形態で説明する符号は、所定ライン上のラインのデータ列を複写する上複写、同一ラインの所定バイト左のデータ列を複写する近い左複写、同一ラインの所定バイト左のデータ列を複写する遠い左複写、およびデータを直接指定する生データの４種類の操作のうち、一つを指定する。なお、上複写および近い左複写が参照する所定の位置は、上記ディザマトリクスの周期に応じた値であり、遠い左複写が参照する所定の位置は、背景パターンの周期に応じたものとなる。
【００３０】
図３に示すように、符号（コマンド符号）が「０」で開始する場合はＲＡＷコマンドであり、引き続く８ビットのデータ（＜ｄａｔａ８＞）をそのまま生データとして指定する。符号が「１０」で開始する場合はＣＯＰＹ  ＵＰコマンドであり、引き続くカウント符号（＜ｃｏｕｎｔ＞）が示すバイト数だけ上複写を行う。符号「１１０」で開始する場合はＣＯＰＹ  ＮＥＡＲ  ＬＦＴコマンドであり、引き続くカウント符号（＜ｃｏｕｎｔ＞）が示すバイト数だけ近い左複写を行う。符号「１１１０」で開始する場合はＣＯＰＹ  ＦＡＲ  ＬＥＦＴコマンドであり、引き続くカウント符号（＜ｃｏｕｎｔ＞）が示すバイト数だけ遠い左複写を行う。符号「１１１１０」で開始する場合はＣＯＵＮＴ  ＨＩＧＨコマンドであり、引き続くカウント符号（＜ｃｏｕｎｔ＞）が示す数の６４倍を、後続するＣＯＰＹ  ＵＰ、もしくはＣＯＰＹ  ＮＥＡＲ  ＬＥＦＴ、もしくはＣＯＰＹＦＡＲ  ＬＥＦＴコマンドのいずれかのカウント符号に加算することを示す。符号「１１１１１」で開始する場合はＥＯＢコマンドであり、符号列の終了を示す。
【００３１】
図４は上述のカウント符号の一例を示すテーブルを示す図である。同図に示すように、コマンド符号のビットが「１１１１１１」の場合は、ＣＯＵＮＴ０符号を示し、カウントが０であることを示す。コマンド符号のビットが「０」で開始される場合は、ＣＯＵＮＴ１符号を示し、カウントが１であることを示す。コマンド符号のビットが「１０」で開始される場合は、ＣＯＵＮＴ２−３符号を示し、後続する１ビットのデータ（＜ｄａｔａ１＞）が０の場合はコマンド符号としては「０１０」となり、意味としては２バイトを意味することになる。一方、後続する１ビットのデータが１の場合はコマンド符号としては「０１１」となり、意味としては３バイトを意味することになる。つまり、コマンド符号のビット列が「０１」で開始する場合は、２バイト、もしくは３バイトの長さを意味することにある。
【００３２】
また、コマンド符号のビットが「１１０」で開始される場合は、ＣＯＵＮＴ４−７符号を示し、２ビットのデータが後続することになるので４バイトから７バイトまでの長さを意味し、コマンド符号のビットが「１１１０」で開始される場合は、ＣＯＵＮＴ８−１５符号を示し、２ビットのデータが後続することになるので８バイトから１５バイトまでの長さを意味し、コマンド符号のビットが「１１１１０」で開始される場合は、ＣＯＵＮＴ１６−３１符号を示し、２ビットのデータが後続することになるので１６バイトから３１バイトまでの長さを意味し、コマンド符号のビットが「１１１１１０」で開始される場合は、ＣＯＵＮＴ３２−６３符号を示し、２ビットのデータが後続することになるので３２バイトから６３バイトを意味することになる。
【００３３】
次に図５を参照し、図３および図４に示した符号の使用例について説明する。なお、同図に示した符号列は上から記載された順番に解釈されるものとする。
【００３４】
同図において符号列「０  ００００００００」は以下のようにして解釈される。つまり、先頭の「０」はＲＡＷコマンドなので、引き続く８ビットのデータ「００００００００」をそのまま生データとして指定する。次に、符号列「１１００」は、以下のようにして解釈される。先頭の「１１０」は近い左複写コマンドであり、引き続く「０」はＣＯＵＮＴ１符号なので、１バイトの近い左複写を示す。次に、符号列「１０  １０  １」は以下のようにして解釈される。つまり、先頭の「１０」は上複写コマンドであり、引き続く「１０」はＣＯＵＮＴ２−３符号であるので、引き続く１ビット「１」に２を加算した値、すなわち３バイトの上複写を示す。次に、符号列「１１１１０  １０  ０」は以下のようにして解釈される。つまり、「１１１１０」はＣＯＵＮＴ  ＨＩＧＨコマンドであり、引き続く「１０」はＣＯＵＮＴ２−３符号であるので、引き続く１ビット「０」に２を加算した値の６４倍、すなわち１２８を後続するコマンドのカウントに加算することを示す。
【００３５】
次に、符号列「１１１０  １１１１１１」は以下のようにして解釈される。つまり、「１１１０」は遠い左複写コマンドであり、引き続く「１１１１１１」はＣＯＵＮＴ０符号なので、０バイトの遠い左複写を示す。ただし、この場合はＣＯＵＮＴ  ＨＩＧＨ  ２コマンドが先行しているため、１２８が加算され、１２８バイトの遠い左複写を示す。次に、「１１１１１」はＥＯＢコマンドであり、符号列の終了を示す。引き続く「０００００００」はバイト境界に整列するための詰め物であり、特別な意味を持たない。なお、上記の符号に符号化するに際し、上複写位置、近い左複写位置、および遠い左複写位置の選定にあたり、圧縮率を向上するためには下記の注意が必要である。
【００３６】
例えば８ビットのグレイスケール原画像を１ビットの２値画像、あるいは４ビット以下のグレイスケール画像に減色する場合、ディザマトリクスを用いて各マトリクス内の画素ごとに異なった閾値による演算処理を行って減色するのが一般的である。この場合、隣接した画素は異なった閾値によって演算が行われるため、原画像の画素値が同一であっても、減色後の画素値は異なった値になることが多く、相関が低いため、隣接した画素を参照しても圧縮率を向上することが困難である。
【００３７】
ディザマトリクスは周期的に適用されるため、隣接画素ではなく、むしろ少し離れた画素、通常はディザマトリクスの周期だけ離れた画素と同じ閾値が適用されるため、そのような画素との相関が高くなる。したがって、隣接画素の代わりに、ディザマトリクスの周期に応じた、少し離れた画素を参照することにより、圧縮率を向上することができる。
【００３８】
上位置に関しては、ディザマトリックスの周期に等しいライン数をそのまま適用することができるが、近い左位置および遠い左位置については、符号化の単位がバイト単位であるため、画素が８ビット未満の場合にはさらに注意が必要となる。例えば、画素が１ビットで、ディザマトリックスの基本周期が１２画素の場合、１．５バイトの周期となるが、符号化の単位が１バイトであるため、バイト単位で同一の閾値が適用される周期は３バイトとなり、この周期を近い左位置に適用する必要がある。遠い左位置についても同様で、例えば画素が１ビットで、背景パターンの周期が１０２４画素すなわち１２８バイトであり、ディザマトリックスの基本周期が１２画素の場合、背景パターンの１周期違いの位置には異なった閾値が適用されるため相関が低く、圧縮率を向上することは困難である。この場合は１２８バイトと３バイトの最小公倍数である３８４バイト離れた位置を遠い左位置とする必要がある。
【００３９】
次に、図６に示すフローチャートを参照し、プリンタドライバ４の処理の詳細について以下、説明する。図６はプリンタドライバ４が行うメインの処理のフローチャートである。プリンタドライバ４がオペレーティングシステム２から呼び出されると、まずステップＳ１にて呼び出しの種類が描画指令であるか否かを判定する。呼び出しの種類が描画指令であった場合は、処理をステップＳ２に進め、描画処理を行う。描画処理として具体的には、オペレーティングシステム２を経由してアプリケーション３から指示された文字、図形またはビットマップ等を８ビットのグレイスケール画像に変換し、ＲＡＭ１７０２、もしくは外部記憶装置１７０４に記録する。
【００４０】
次にステップＳ３にて呼び出しの種類がビットマップ描画指令であるか否かを判定する。呼び出しの種類がビットマップ描画指令でなかった場合には処理を終了する。一方、呼び出しの種類がビットマップ描画指令だった場合にはステップＳ４にて、後述する背景パターン周期検出処理を行い、処理を終了する。
【００４１】
一方、ステップＳ１にて呼び出しの種類が描画指令でなかった場合は、処理をステップＳ７に進め、呼び出しの種類がページ終了指令であるか判定する。呼び出しの種類がページ終了指令であった場合には、処理をステップＳ８に進め、２値化処理を行う。具体的にはステップＳ２にてＲＡＭ１７０２、もしくは外部記憶装置１７０４に記録された８ビットのグレイスケール画像を、ディザマトリックスを使用して、白黒１ビットの画像に変換する。
【００４２】
次にステップＳ９にて印刷制御コマンド、具体的には用紙サイズ、給紙カセット、解像度、階調数、１ラインのバイト数、１ページのライン数など、印刷に必要な条件を指定するコマンドを出力する。次にステップＳ１０にて、符号化時に使用する、上複写時に複写元が何ライン上の位置であるかを指定する上複写垂直オフセット値、近い左複写時に複写元が同一ラインの何バイト左の位置であるかを指定する近い左複写水平オフセット値、および遠い左複写時に複写元が同一ラインの何バイト左の位置であるかを指定する遠い左複写水平オフセット値を指定する圧縮パラメタ指定コマンドを出力する。
【００４３】
ここで、上複写垂直オフセット値および近い左複写水平オフセット値は、ステップＳ８にて使用したディザマトリックスに応じて、あらかじめ理論的に、あるいは実験により最適値を求めておき、それを使用する。また遠い左複写水平オフセット値は、ステップＳ４にて求めた背景パターン周期に応じた値を使用する。
【００４４】
次にステップＳ１１にて、後述する符号化手順に従い、画像データを符号化する。このときに、ステップＳ１０にて出力した圧縮パラメタ指定コマンドが指定する、上複写垂直オフセット値、近い左複写水平オフセット値、および遠い左複写水平オフセット値を用いて符号化を行う。次にステップＳ１２にて、ステップＳ１１にて符号化された画像データのサイズおよびライン数を指定する画像データコマンドヘッダを出力する。次にステップＳ１３にて、ステップＳ１１にて符号化された画像データを出力する。次にステップＳ１５にて、ページの終了を指定するコマンド（ページ終了コマンド）を出力して処理を終了する。
【００４５】
一方、ステップＳ７にて呼び出しの種類がページ終了指令でなかった場合には処理をステップＳ１６に進め、呼び出しの種類に応じたその他の処理、例えばページ開始指令あるいはプリンタ能力問い合わせ指令等に対応する処理を行い、終了する。
【００４６】
次に図７を参照し、上記ステップＳ４における処理の詳細について以下、説明する。図７は上記ステップＳ４における背景パターン周期検出処理の詳細を示すフローチャートである。
【００４７】
ビットマップ描画命令を受けると、まずステップＳ２１にてこのビットマップ（以下、第１のビットマップ）の幅が２５６画素以上であるか否かを判定する。該ビットマップの幅が２５６画素以上でない場合は処理を終了する。これは、背景パターンは例えば１０２４画素といった、大きな幅および高さを持つのが一般的であること、また、小さい幅または高さのビットマップを対象に処理を行うと、ビットマップを管理するテーブル（以下、ビットマップ管理テーブル）のサイズが大きくなり、またビットマップ管理テーブルを検索する処理時間も長くなることから、小さい幅または高さのビットマップの場合は背景パターン周期検出処理を行わないようにするためである。ここでビットマップ管理テーブルとは、１ページ内に含まれるビットマップを管理する予め定められた固定サイズのテーブルで、本実施形態では後述の条件を満たしたビットマップに対してのみ、このビットマップに関する情報を格納する。具体的には図１８に例示するように、ビットマップの左上隅のｘ座標、ｙ座標、幅、高さを管理する。図１８はビットマップ管理テーブルの構成例を示す図である。また、ビットマップ管理テーブルは、各ページの処理を開始するごとに空に初期化される。
【００４８】
図７に戻って、ビットマップの幅が２５６画素以上である場合は処理をステップＳ２２に進め、ビットマップの高さが２５６画素以上であるか判定する。ビットマップの高さが２５６画素以上でない場合は処理を終了する。
【００４９】
ビットマップの高さが２５６画素以上である場合は処理をステップＳ２３に進め、ビットマップ管理テーブルの検索が終了したか否かを判断する。終了していない場合は処理をステップＳ２４に進め、ビットマップ管理テーブルに格納されているビットマップの左上隅のｙ座標、高さを参照し、第１のビットマップの左上隅のｙ座標、高さと一致するものを検索する。そして一致しない場合は処理をステップＳ２３に戻し、上記検索の対象がビットマップ管理テーブルの最後に行き着くまで行われる。一方、一致するもの（第２のビットマップの左上隅のｙ座標、高さ）が見つかった場合には処理をステップＳ２５に進め、第１のビットマップが第２のビットマップの右に隣接しているか否かを判定する。具体的にはビットマップ管理テーブルを参照し、第２のビットマップの左上隅のＸ座標＋第２のビットマップの幅＝第１のビットマップの左上隅のＸ座標であれば、第１のビットマップが第２のビットマップの右に隣接していることになる。右に隣接している場合は処理をステップＳ２７に進める。
【００５０】
一方、右に隣接していない場合は処理をステップＳ２６に進め、第１のビットマップが、第２のビットマップの左に隣接しているか否かを判定する。具体的には、第２のビットマップの左上隅のＸ座標＝第１のビットマップの左上隅のＸ座標＋第１のビットマップの幅であれば、第１のビットマップは第２のビットマップの左に隣接していることになる。左に隣接している場合は処理をステップＳ２７に進め、左に隣接していない場合は処理をステップＳ２３に戻す。
【００５１】
ステップＳ２７では、第１のビットマップの幅と、後述の処理により求まる背景周期とを比較する。なお、背景周期は、各ページの処理を開始するごとに、０に初期化される。背景周期が第１のビットマップの幅より大きい場合は、処理をステップＳ２９に進める。一方、背景周期が第１のビットマップの幅以下である場合には処理をステップＳ２８に進め、ステップＳ２８にて背景周期に第１のビットマップの幅を代入し、処理をステップＳ２９に進める。
【００５２】
ステップＳ２９では、第２のビットマップの幅と背景周期とを比較する。背景周期が第２のビットマップの幅より大きい場合には、処理をステップＳ３１に進める。一方、背景周期がテーブル中の現在のビットマップの幅以下である場合には、処理をステップＳ３０に進め、ステップＳ３０にて背景周期に第２のビットマップの幅を代入し、処理をステップＳ３１に進める。このようにして、今までの背景周期、および左右に隣接する２つのビットマップの幅のうち、最大の値が新たに背景周期に代入される。最大の値を用いる理由は、背景ビットマップが用紙の左端または右端でクリップされることにより周期よりも小さい幅となることがあるため、この影響を除外するためである。
【００５３】
ステップＳ３１では、ビットマップ管理テーブルがフルであるか否かを判定する。ビットマップ管理テーブルがフルである場合は、新たにビットマップに関する情報を格納（登録）する余地がないため、何もせずに処理を終了する。一方、ビットマップ管理テーブルがフルでない場合は、第１のビットマップの左上隅のＸ座標、左上隅のＹ座標、幅、及び高さをビットマップ管理テーブルに格納して処理を終了する。
【００５４】
このようにして１ページの処理が終了すると、このページ内で隣接するビットマップの幅の最大値が背景周期に格納されていることになる。また、隣接するビットマップがこのページ内に存在しなかった場合は、背景周期には０が格納されている。
【００５５】
次に、図８を参照して、図６のステップＳ１０における処理の詳細について以下、説明する。図８はステップＳ１０における処理の詳細を示すフローチャートである。まずステップＳ４１にて、上記ステップＳ４にて求めた背景周期が０であるか否かを判定する。背景周期が０でない場合、すなわち背景パターンの周期が検出された場合は、処理をステップＳ４２に進め、背景周期と１バイトの画素数の最小公倍数を求める。例えば、背景周期が１０２４画素であり、１画素が１ビットで構成されている場合（１バイトの画素数が８）、その最小公倍数は１０２４となる。また、背景周期が５１１画素であり、１画素が４ビットで構成されている場合（１バイトの画素数が２）、その最小公倍数は１０２２となる。この処理は、符号化の単位が１バイトであるため、画素単位の周期をバイト単位の周期に変換するために行う。
【００５６】
次にステップＳ４３にて、ステップＳ４２で求めた最小公倍数をバイト単位に変換する。具体的には、最小公倍数を１バイトの画素数で除算する。次にステップＳ４４にて、ステップＳ４３で求めたバイト単位の背景周期と、ディザ周期の最小公倍数を求める。例えば、背景周期が１２８バイトであり、ディザ周期が２バイトである場合は、１２８バイトとなる。また、背景周期が５１１バイトであり、ディザ周期が３バイトである場合は、１５３３バイトとなる。この処理は、背景周期がディザ周期の整数倍でない場合は、背景周期だけ離れた点に異なったディザ処理がほどこされることにより、異なった画素値となるため、同一のディザ処理が行われる点を参照するようにするために行う。
【００５７】
次にステップＳ４５にて、ステップＳ４４で求めた最小公倍数が、ライン長の９０％未満であるか判定する。ライン長の９０％未満であった場合は、処理をステップＳ４７に進め、上記ステップＳ８の２値化処理にて使用したディザマトリックスの周期に応じた、上複写および近い左複写の位置、およびステップＳ４４にて求めた最小公倍数（遠い左複写の位置）を圧縮パラメタを指定するコマンド（圧縮パラメタ指定コマンド）として出力し、処理を終了する。
【００５８】
一方、ステップＳ４１にて背景周期が０であった場合、及びステップＳ４５にて、ステップＳ４４にて求めた最小公倍数がライン長の９０％以上であった場合、処理をステップＳ４６に進め、背景周期をディフォルトの値に設定する。これらの場合は、背景周期が検出できなかった、あるいは背景周期が過大であり、圧縮の向上に大きな寄与を与えない場合であるので、かわりにディフォルト値を設定する。ディフォルト値は、近い左複写の位置とは異なるようにあらかじめ定めておく。例えば、ディザ周期が１６画素であり、１バイトの画素数が８である場合、近い左複写の位置は２バイト左となる。この場合は背景周期のディフォルト値を１バイトに定めておく。前述のように、ディザ周期だけ離れた点と相関が高くなるのが一般的であるが、印刷データが通常のテキストまたは表のごとく、白黒２値で表現される場合は、ディザ処理を行わなかった場合と同じ結果となる。また、ディザ周期とはかかわりなく隣接する点との相関が高くなるため、かかる場合には２バイト離れた位置よりも１バイト離れた位置のほうが相関が高くなり、圧縮率の向上に寄与することができる。
【００５９】
次にステップＳ４７にて、上記ステップＳ８の２値化処理にて使用したディザマトリックスの周期に応じた、上複写および近い左複写の位置、およびステップＳ４６にて設定したディフォルトの背景周期（遠い左複写の位置）を圧縮パラメタを指定するコマンド（圧縮パラメタ指定コマンド）として出力し、処理を終了する。
【００６０】
次に図９を参照し、図６のステップＳ１１における符号化処理の詳細について説明する。図９はステップＳ１１における符号化処理の詳細を示すフローチャートである。
【００６１】
まずステップＳ５１にて、ライン番号Ｙを０に初期化する。次にステップＳ５２にて、ライン先頭からのバイトオフセットＸを０に初期化する。
【００６２】
次にステップＳ５３にて、上位置が有効な画像領域にあるか判定する。具体的には、図８のステップＳ４７にて出力した、上複写位置を示すライン数（以下、Ｚで表す）が、ライン番号Ｙよりも大きいか否かを判定する。上複写位置を示すライン数Ｚがライン番号Ｙ以下である場合は、上位置が有効な画像領域（符号化対象のビットマップ内に存在する領域）にある場合なので、ステップＳ５４にて現在の位置（Ｘ、Ｙ）から始まるバイト列と、上位置（Ｘ、Ｙ−Ｚ）から始まるバイト列とが連続して一致する長さを求める。なお、この際に、ライン末まで連続して一致している場合には、ライン末で打ち切るものとする。また、連続して一致する長さが、カウント符号の最大値である４０９５バイトを超える場合には、４０９５バイトで打ち切るものとする。
【００６３】
次にステップＳ５５にて、ステップＳ５４で求めた長さが０であるか否かを判定する。ステップＳ５４で求めた長さが０でない場合、処理をステップＳ５６に進め、ステップＳ５４で求めた長さ（カウント）が６３より大きいか否かを判定する。ステップＳ５４で求めた長さが６３より大きい場合は、処理をステップＳ５７に進め、ＣＯＵＮＴ  ＨＩＧＨコマンドをＲＡＭ１７０２、もしくは外部記憶装置１７０４に出力し、次いでステップＳ５８にて、ステップＳ５４で求めた長さを６４で除算した商（カウントの上位）をＲＡＭ１７０２、もしくは外部記憶装置１７０４に出力し、処理をステップＳ５９に進める。一方、ステップＳ５６にて、ステップＳ５４で求めた長さが６３以下である場合には処理をステップＳ５９に進める。
【００６４】
次にステップＳ５９にてＣＯＰＹ  ＵＰコマンドをＲＡＭ１７０２、もしくは外部記憶装置１７０４に出力し、次いでステップＳ６０にて、ステップＳ５４で求めた長さを６４で除算した剰余（カウントの下位）をＲＡＭ１７０２、もしくは外部記憶装置１７０４に出力する。
【００６５】
一方、ステップＳ５３にて、上複写位置を示すライン数が、ライン番号Ｙよりも大きい場合、及びステップＳ５５にて求めた長さが０であった場合は、処理をステップＳ６２に進め、近い左位置が有効な画像領域にあるか判定する。具体的には、上記ステップＳ４７にて出力した、近い左複写位置を示すバイト数（以下、Ｗで表す）が、ライン先頭からのバイトオフセットＸよりも大きいか否かを判定する。近い左複写位置を示すバイト数Ｗが、ライン先頭からのバイトオフセットＸ以下である場合は、近い左位置が有効な画像領域にある場合なので、処理をステップＳ６３に進め、現在の位置（Ｘ、Ｙ）から始めるバイト列と、近い左位置（Ｘ−Ｗ、Ｙ）から始まるバイト列とが連続して一致する長さ（カウント）を求める。なお、この際に、ライン末まで連続して一致している場合には、ライン末で打ち切るものとする。また、連続して一致する長さが、カウント符号の最大値である４０９５バイトを超える場合には、４０９５バイトで打ち切るものとする。
【００６６】
次にステップＳ６４にて、ステップＳ６３で求めた長さが０であるか否かを判定する。ステップＳ６３にて求めた長さが０でない場合には、処理をステップＳ６５に進め、ステップＳ６３にて求めた長さが６３より大きいか否かを判定する。ステップＳ６３にて求めた長さが６３より大きい場合には、処理をステップＳ６６に進め、ＣＯＵＮＴ  ＨＩＧＨコマンドをＲＡＭ１７０２、もしくは外部記憶装置１７０４に出力し、次いでステップＳ６７にて、カウントの上位、すなわちステップＳ６３にて求めた長さを６４で除算した商をＲＡＭ１７０２、もしくは外部記憶装置１７０４に出力し、処理をステップＳ６８に進める。一方、ステップＳ６５にて、ステップＳ６３で求めた長さが６３以下の場合には、処理をステップＳ６８に進める。
【００６７】
次にステップＳ６８にてＣＯＰＹ  ＮＥＡＲ  ＬＥＦＴコマンドをＲＡＭ１７０２、もしくは外部記憶装置１７０４に出力し、次にステップＳ６０にて、カウントの下位、すなわちステップＳ６３にて求めた長さを６４で除算した剰余をＲＡＭ１７０２、もしくは外部記憶装置１７０４に出力する。
【００６８】
一方、ステップＳ６２にて、近い左複写位置を示すバイト数Ｗが、ライン先頭からのバイトオフセットＸよりも大きい場合、及びステップＳ６４にて求めた長さが０であった場合は、処理をステップＳ６９に進め、遠い左位置が有効な画像領域にあるか判定する。具体的には、図８のステップＳ４７にて出力した、遠い左複写位置を示すバイト数（以下、Ｒで表す）が、ライン先頭からのバイトオフセットＸよりも大きいか否かを判定する。遠い左複写位置を示すバイト数Ｒが、ライン先頭からのバイトオフセットＸ以下である場合は、遠い左位置が有効な画像領域にある場合なので、処理をステップＳ７０に進め、現在の位置（Ｘ、Ｙ）から始めるバイト列と、遠い左位置（Ｘ−Ｒ、Ｙ）から始まるバイト列とが連続して一致する長さ（カウント）を求める。なお、この際に、ライン末まで連続して一致している場合には、ライン末で打ち切るものとする。また、連続して一致する長さが、カウント符号の最大値である４０９５バイトを超える場合には、４０９５バイトで打ち切るものとする。次にステップＳ７１にて、ステップＳ７０にて求めた長さが０であるか否かを判定する。ステップＳ７０にて求めた長さが０でない場合には、処理をステップＳ７２に進め、ステップＳ７０にて求めた長さが６３より大きいか否かを判定する。ステップＳ７０にて求めた長さが６３より大きい場合には、処理をステップＳ７３に進め、ＣＯＵＮＴ  ＨＩＧＨコマンドをＲＡＭ１７０２、もしくは外部記憶装置１７０４に出力し、次いでステップＳ７４にて、カウントの上位、すなわちステップＳ７０にて求めた長さを６４で除算した商をＲＡＭ１７０２、もしくは外部記憶装置１７０４に出力し、処理をステップＳ７５に進める。一方、ステップＳ７２にて、ステップＳ７０で求めた長さが６３以下である場合には処理をステップＳ７５に進める。
【００６９】
ステップＳ７５では、ＣＯＰＹ  ＦＡＲ  ＬＥＦＴコマンドをＲＡＭ１７０２、もしくは外部記憶装置１７０４に出力し、次いでステップＳ６０にて、カウントの下位、すなわちステップＳ７０にて求めた長さを６４で除算した剰余をＲＡＭ１７０２、もしくは外部記憶装置１７０４に出力する。
【００７０】
一方、ステップＳ６９にて、遠い左複写位置を示すバイト数Ｒが、ライン先頭からのバイトオフセットＸよりも大きい場合、及びステップＳ７１にて求めた長さが０であった場合は、処理をステップＳ７６に進め、ＲＡＷコマンドをＲＡＭ１７０２、もしくは外部記憶装置１７０４に出力し、次に現在の位置（Ｘ、Ｙ）のデータ（１バイト分）を生データとしてＲＡＭ１７０２、もしくは外部記憶装置１７０４に出力する。
【００７１】
上記の処理が終了すると処理をステップＳ７８に進め、処理したバイト数をＸに加算する。次にステップＳ７９にて、Ｘがライン末に達したか、すなわちＸが１ラインのバイト数に等しいか否かを判定する。Ｘが１ラインのバイト数より小さい場合は、処理をステップＳ５３に戻し、処理を継続する。一方、Ｘが１ラインのバイト数と等しい場合は、処理をステップＳ８０に進め、ライン番号Ｙに１を加算し、ステップＳ８１にて、画像の処理が終了したか、すなわちＹが画像のライン数と等しいか判定する。Ｙが画像のライン数より小さい場合は、処理をステップＳ５２に戻し、処理を継続する。一方、Ｙが画像のライン数と等しい場合は、処理をステップＳ８２に進め、ＥＯＢコマンドをＲＡＭ１７０２、もしくは外部記憶装置１７０４に出力し、次いでステップＳ８３にて、バイト境界に整列するために必要な数だけ（例えば上述の符号化処理によりＲＡＭ１７０２、もしくは外部記憶装置１７０４に出力されたビット列の長さが８の倍数となるように）ビット「０」をバッファに出力し、処理を終了する。
【００７２】
次に、図１２を参照し、図２に示した復号回路１３の構成について詳細に説明する。図１２は復号回路１３の詳細な構成を示すブロック図である。
【００７３】
同図において、入力バッファ２１は、ＦＩＦＯメモリ１２から読み出した符号データを格納する。入力バッファ２１は、少なくとも４バイトのデータを格納することができ、バッファに空きが生じ、かつＦＩＦＯメモリ１２にデータがある場合はＦＩＦＯメモリ１２からデータを読み出して格納する。入力バッファ２１はまた、ビットカウンタ２３に保持された、処理済ビット数が８以上になった場合には、不要になった処理済データを破棄する。
【００７４】
セレクタ２２は、例えば１１組の８入力セレクタであり、入力バッファ２１に格納された符号データを、ビットカウンタ２３が示す処理済ビット数に従って選択することにより、コマンドデコード回路２４が処理するために必要な、コマンドの開始位置合わせを行う。これは、入力バッファ２１がバイト単位にデータを保持するのに対し、コマンドはビット単位の可変長データであるため８箇所の開始位置があるために必要なものである。
【００７５】
ビットカウンタ２３は、入力バッファ２１に格納された符号データのうち処理済みのビット数を格納する。ビットカウンタ２３はまた、コマンドデコード回路２４から出力された、コマンドのビット数を加算することによりビットカウンタに格納された値を更新する。ビットカウンタ２３はまた、入力バッファが処理済データを破棄した場合には、破棄したビット数を減算する。ビットカウンタ２３はまた、コマンドデコード回路２３がＥＯＢコマンドを復号したときに、コマンドデコード回路２３からＥＯＢ信号を受信し、バイト境界合わせの処理を行う。具体的には、ビットカウンタの下位３ビットが全て０であれば何もせず、そうでなければ８を加算するとともに下位３ビットをクリアする。
【００７６】
コマンドデコード回路２４は、例えばリードオンリーメモリ、あるいはワイヤードロジックにより構成され、セレクタ２２によって位置合わせが行われた、入力バッファ２１に格納された符号データを復号し、復号したコマンドに従ってカウンタ２６、上複写出力回路２７、遠い左複写出力回路２８、近い左複写出力回路２９、生データ出力回路３０、およびビットカウンタ２３に、前述の、あるいは後述する各種の信号を出力する。
【００７７】
ライン長レジスタ２５は、制御回路１５があらかじめ出力した、１ラインのバイト数を保持する。
【００７８】
カウンタ２６は、ＣＯＰＹ  ＵＰ、ＣＯＰＹ  ＮＥＡＲ  ＬＥＦＴあるいはＣＯＰＹ  ＦＡＲ  ＬＥＦＴコマンドの処理バイト数を保持し、１バイトのデータ出力が行われる毎に減算される。カウンタ２６は上位６ビットと下位６ビットを独立に設定可能であり、コマンドデコード回路２３がＣＯＵＮＴ  ＨＩＧＨコマンドを復号した時にはコマンドデコード回路２３が出力する、処理バイト数の加算値をカウンタ２６の上位に格納する。また、コマンドデコード回路２３がＣＯＰＹ  ＵＰ、ＣＯＰＹ  ＮＥＡＲ  ＬＥＦＴあるいはＣＯＰＹ  ＦＡＲ  ＬＥＦＴコマンドを復号した時にはコマンドデコード回路２３が出力する、処理バイト数をカウンタ２６の下位に格納する。
【００７９】
上複写出力回路２７は、カウンタ２６が保持する処理バイト数に従って、ラインバッファ３１が出力する、上複写位置のデータを読み取り、出力する。遠い左複写出力回路２８は、カウンタ２６が保持する処理バイト数に従って、ラインバッファ３１が出力する、遠い左複写位置のデータを読み取り、出力する。近い左複写出力回路２９は、カウンタ２６が保持する処理バイト数に従って、可変段シフトレジスタ３８が出力する、近い左複写位置のデータを読み取り、出力する。生データ出力回路３０は、コマンドデコード回路２４が出力した１バイトの生データを出力する。
【００８０】
列カウンタ４１は、ラインバッファ３１の現在の列アドレスを保持し、ラインバッファ３１に書き込みが行われる毎に書き込まれたデータのサイズを随時加算することで、カウント値を求める。そしてこのカウント値がライン長レジスタ２５が保持する１ラインのバイト数に達した場合、０に復帰する。
【００８１】
ラインバッファ３１は、複数のラインの復号データを保持し、減算回路４０が出力するアドレスに従って、復号データの入力または出力を行う。
【００８２】
行カウンタ３２は、ラインバッファ３１の現在の行アドレスを保持し、上記カウント値が０に復帰する毎にカウントアップし、カウントの結果が行数レジスタ３６が保持するライン数に達した場合には、カウントを０に復帰する。行カウンタ３２はまた、行数レジスタ３６にライン数が出力されたときには０に復帰する。
【００８３】
乗算回路３３は、行カウンタ３２が保持する現在の行アドレスと、ライン長レジスタ２５が保持する１ラインのバイト数との積を計算することにより、ラインバッファ３１の現在の行の先頭アドレスを出力する。加算回路３４は、乗算回路３３が出力する現在の行の先頭アドレスと、列カウンタ４１が保持する現在の列アドレスとの和を計算することにより、ラインバッファ３１の現在のアドレスを出力する。背景周期レジスタ３９は、制御回路１５があらかじめ出力した、背景周期バイト数を保持する。
【００８４】
減算回路４０は、遠い左複写出力回路より、遠い左複写の読み取りを指示する信号を受信しているときは、加算回路３４が出力する現在のアドレスから、背景周期レジスタ３９が保持する背景周期バイト数を減算して出力するとともに、遠い左複写出力回路より、遠い左複写の読み取りを指示する信号を受信していないときは、加算回路３４が出力する現在のアドレスをそのまま出力する。
【００８５】
出力バッファ３５は、上複写出力回路２７、遠い左複写出力回路２８、近い左複写出力回路２９、または生データ出力回路３０から復号データが出力される毎に、出力された復号データを格納する。出力バッファ３５はまた、シフトレジスタ１６から画像データの出力を要求されたときに、格納された復号データを出力する。
【００８６】
行数レジスタ３６は、制御回路１５があらかじめ出力した、ライン数（上複写垂直オフセット値）を保持する。
【００８７】
段数レジスタ３７は、制御回路１５があらかじめ出力した、近い左位置を示すバイトオフセット値を保持する。可変段シフトレジスタ３８は、シフトレジスタとセレクタによって構成され、段数レジスタ３７が保持する近い左位置を示すバイトオフセット値に等しい段数のシフトレジスタを構成し、出力された復号データを、段数レジスタ３７が保持する近い左位置を示すバイトオフセット値で指定された値より１だけ小さい回数遅延したデータを出力する。
【００８８】
コマンドデコード回路２４はＣＯＰＹ  ＵＰコマンドをデコードすると、それに引き続くカウントをデコードし、カウンタ２６の下位に格納するとともに、上複写出力回路２７に上複写の読み取りを指示する信号を出力する。カウンタ２６の上位には、ＣＯＵＮＴ  ＨＩＧＨコマンドが先行しなかった場合には０が、先行した場合にはＣＯＵＮＴ  ＨＩＧＨコマンドが示す上位カウントが格納されている。上複写出力回路２７は、ラインバッファ３１において、加算回路３４、減算回路４０が出力するアドレス（言い換えれば、現在の位置）に格納されたデータを読み出し、ラインバッファ３１に出力する（同じデータを上書きすることになるので、この処理は行わなくても良いが）と共に、出力バッファ３５に出力する。一方、読み出された復号データは可変段シフトレジスタ３８に入力される（以下、先頭から）。そして可変段シフトレジスタ３８に既に保持されていたデータは一段ずつシフトされ、可変段シフトレジスタ３８の最終段からは、現在の位置の次の位置に対応する近い左複写位置の１バイトが出力される。次いで列カウンタ４１はカウントアップされ、カウンタ２６はカウントダウンされる。このようにして、カウンタ２６が０に達するまで、復号データの出力が行われる。
【００８９】
コマンドデコード回路２４はＣＯＰＹ  ＦＡＲ  ＬＥＦＴコマンドをデコードすると、引き続くカウントをデコードし、カウンタ２６の下位に格納するとともに、遠い左複写出力回路２８に遠い左複写を指示する信号を出力する。カウンタ２６の上位には、ＣＯＵＮＴ  ＨＩＧＨコマンドが先行しなかった場合には０が、先行した場合にはＣＯＵＮＴ  ＨＩＧＨコマンドが示す上位カウントが格納されている。ここで遠い左複写出力回路は、遠い左位置のデータ読み取りを指示する信号を一時的に出力するため、ラインバッファ３１において、加算回路４０の出力（現在のアドレス）から、背景周期レジスタ３９が保持する背景周期の値を減算した値、すなわち遠い左位置のアドレスに格納された復号データを読み取り、ラインバッファ３１の現在の位置に書き込むと共に、出力バッファ３５にも出力する。また、読み出した復号データは可変段シフトレジスタ３８に入力される。そして、可変段シフトレジスタ３８に保持されていたデータは一段ずつシフトされ、可変段シフトレジスタ３８の最終段からは、現在の位置の次の位置に対応する近い左複写位置の１バイトが出力される。次いで列カウンタ４１はカウントアップされ、カウンタ２６はカウントダウンされる。このようにして、カウンタ２６が０に達するまで、復号データの出力が行われる。
【００９０】
コマンドデコード回路２４はＣＯＰＹ  ＮＥＡＲ  ＬＥＦＴコマンドをデコードすると、引き続くカウントをデコードし、カウンタ２６の下位に格納するとともに、近い左複写出力回路２９に近い左複写を指示する信号を出力する。カウンタ２６の上位には、ＣＯＵＮＴ  ＨＩＧＨコマンドが先行しなかった場合には０が、先行した場合にはＣＯＵＮＴ  ＨＩＧＨコマンドが示す上位カウントが格納されている。近い左複写回路２９は、可変段シフトレジスタ３８が出力する近い左複写位置の１バイトの復号データを出力バッファ３５に出力すると共に、ラインバッファ３１の現在の位置に書き込む。又読み出した１バイトの復号データは可変段シフトレジスタ３８に入力する。可変段シフトレジスタ３８に保持されていたデータは一段ずつシフトされ、可変段シフトレジスタ３８の最終段からは、現在の位置の次の位置に対応する近い左複写位置の１バイトが出力される。次いで列カウンタ４１はカウントアップされ、カウンタ２６はカウントダウンされる。このようにして、カウンタ２６が０に達するまで、復号データの出力が行われる。
【００９１】
コマンドデコード回路２４はＲＡＷコマンドをデコードすると、引き続く１バイトの生データ（復号データ）を生データ出力回路３０に出力する。生データ出力回路３０はこの復号データを出力バッファ３５に出力すると共に、ラインバッファ３１の現在の位置に書き込む。またこの復号データは可変段シフトレジスタ３８に入力される。また可変段シフトレジスタ３８に保持されていたデータは一段ずつシフトされ、可変段シフトレジスタ３８の最終段からは、現在の位置の次の位置に対応する近い左複写位置の１バイトが出力される。
【００９２】
コマンドデコード回路２４はＣＯＵＮＴ  ＨＩＧＨコマンドをデコードすると、引き続くカウントをデコードし、カウンタ２６の上位に格納する。
【００９３】
次に図１３および図１４を参照し、ラインバッファ３１のデータ入出力の動作について説明する。図１３は、符号化前、もしくは復号後の画像データの構成を示すものであり、一例として１ラインの長さが１０バイトの場合を示す。図に示すように、先頭ラインの左から００、０１、．．．０９の順にバイト（画像データ）が並び、次のラインの左から１０、１１、．．．１９の順にバイトが並ぶ。以降のラインも同様である。
【００９４】
図１４は、ラインバッファ３１の各々のアドレスに、図１３に示す画像データがどのように格納されるのかを説明するものであり、一例として１ラインの長さが１０バイト、上複写位置を示すライン数が３ラインの場合を示す。
【００９５】
最初に行カウンタ３２および列カウンタ４１がともに０であったとすると、最初のデータ入出力は行アドレス０かつ列アドレス０に対して行われる。なお、最初の３ラインの画像が書き込まれるまでは、ラインバッファ３１から出力されるデータは不定である。
【００９６】
ラインバッファ３１の、行アドレス０かつ列アドレス０からデータが読み取られ、次いで同じアドレスに、図１１示のバイト００が書き込まれると、列カウンタ４１はカウントアップし、１を保持する。次に行アドレス０かつ列アドレス１からデータが読み取られ、次いで同じアドレスに、バイト０１が書き込まれると、列カウンタ４２はカウントアップし、２を保持する。このようにして１０バイトが書き込まれると、列カウンタ４１は１０を保持するので、ライン長レジスタ２５が保持する１ラインのバイト数と等しくなり、列カウンタ４１は０を保持し、行カウンタ３２はカウントアップし、１を保持する。次に行アドレス１かつ列アドレス０からデータが読み取られ、次いで同じアドレスに、バイト１０が書き込まれると、列カウンタ３０はカウントアップし、１を保持する。このようにして、２０バイトのデータが書き込まれると、列カウンタ４１は０を保持するとともに、行カウンタ３２はカウントアップして３を保持するので、行数レジスタ３６が保持するライン数と等しくなり、行カウンタ３２は０を保持することになる。
【００９７】
ここで行カウンタ３２および列カウンタ３０はともに０となっているので、最初に書き込まれた、バイト００が読み取られ、次いでバイト３０が書き込まれる。このようにして、順次、３ライン上のデータを読んだ後に現在のラインのデータが上書きされ、ラインバッファ３１は、いわゆるリングメモリとして動作する。
【００９８】
次に図１５を参照し、ラインバッファ３１、および可変段シフトレジスタ３８の動作タイミングを説明する。
【００９９】
図１５は、図１３に示す画像データがどのようなタイミングで処理されるかを説明するものであり、一例として１ラインの長さが１０バイト、上複写位置を示すライン数が３ライン、近い左複写位置を示すバイトオフセット値が２バイトの場合を示す。
【０１００】
図中、Ａ１はちょうど先頭の３ラインの処理を終えた時点を示す。上述の説明のごとく、このときに行カウンタ３２および列カウンタ４１はともに０に復帰するので、ラインバッファ３５からは図１１に示すバイト００が読み取られる。Ａ１時点にて、上複写回路２７が動作している場合には、Ａ２時点にて、ラインバッファ３５から読み取っているデータが確定すると、バイト００が上複写回路２７に入力される。次に上複写出力回路２７が復号データをＡ３時点までに出力する。Ａ３時点において、出力された復号データは、バイト３０として、ラインバッファ３５に格納される。このとき可変段レジスタ３８にクロックが入力され、可変段シフトレジスタ３８に保持されていたデータは１段ずつシフトするとともに、先頭段のシフトレジスタには出力された復号データ、すなわちデータバイト３０が保持される。また、可変段シフトレジスタ３８は、段数レジスタ３７が保持する、近い左位置を示すバイトオフセット値より１小さい段数のシフトレジスタを構成するため、可変段シフトレジスタ３８の最終段は、可変段シフトレジスタ３８の先頭段より１バイト遅れたデータ、すなわちバイト２９が出力される。このようにして、復号データが出力される毎に、データバッファ３５に格納されるとともに、可変段シフトレジスタ３８に保持されたデータは１段ずつシフトされる。
【０１０１】
Ｃ１時点で近い左複写出力回路２９が動作していた場合は、可変段シフトレジスタ３８の最終段が出力している、近い左位置のデータバイト、すなわちデータバイト３０が近い左複写出力回路２９に入力される。次に上複写出力回路２７が復号データをＡ３時点までに出力する。Ｃ３時点において、出力された復号データは、データバイト３２として、データバッファ３５に格納され、以下上述の例と同様に動作を行う。
【０１０２】
遠い左複写出力回路２８、あるいは生データ出力回路３０がデータ出力した場合も同様に動作する。
【０１０３】
次に図１６を参照し、制御回路１５が実行する印刷制御手順を説明する。図１６は、制御回路１５が実行する印刷制御手順を示すフローチャートであり、データの受信などその他の処理（不図示）と並行に動作する。
【０１０４】
印刷制御手順が起動されると、まずステップＳ１０１にて印刷可能ページがあるか、具体的には改ページコマンドを受信していて未印刷のページがあるか否かを判定する。印刷可能ページがない場合には、改ページコマンドを受信して印刷可能ページができるまでステップＳ１０１にて待機する。
【０１０５】
印刷可能ページがある場合は処理をステップＳ１０２に進め、プリンタエンジン１４に印刷の開始を指示する。次にステップＳ１０３にて、ページの印刷条件指定コマンドにて指定された１ラインのバイト数をライン長レジスタ２５に設定する。次にステップＳ１０４にて、ページの圧縮パラメタ指定コマンドにて指定された、上複写位置を示すライン数、近い左複写位置を示すバイトオフセット値、および遠い左複写位置を示すバイトオフセット値を、行数レジスタ３６、段数レジスタ３７、および背景周期レジスタ３９にそれぞれ設定する。次にステップＳ１０５にて、１ページの印刷が終了するまで待つ。印刷が開始されると、復号回路１３により、上記のレジスタに設定された値に基づいて復号が行われる。１ページの印刷が終了すると、処理をステップＳ１０１に戻し、印刷可能ページを待つ。
【０１０６】
このようにして、符号化の際に使用された圧縮パラメタを用いて復号が行われるため、常に正しい復号データが得られる。
【０１０７】
以上の説明により、本実施形態によって、背景パターンの周期を検出し、検出した周期に応じた位置を参照して符号化を行うため、背景パターンを効率よく圧縮することができる。また、検出した周期に応じた位置および限られた少数の位置のみを参照して符号化を行うため、高速に圧縮することができる。また、背景パターンの周期を検出する際に、背景パターンのデータ自体を使用せず、背景パターンの大きさと位置のみにより検出するため、高速に周期を検出することができる。また、検出した背景パターンの周期を、１バイトの画素数およびディザ周期に応じて補正しているため、ディザ処理が行われた画像であっても効率よく圧縮することができる。また、背景パターンの周期が検出されなかった場合に、ディフォルトの参照位置を使用して符号化を行うため、そのようなことを行わない場合に較べて効率よく圧縮することができる。
【０１０８】
［第２の実施形態］
なお上述の実施形態では、画像の左端付近で近い左複写位置が画像の左端からはみ出る場合には参照しないように構成されているが、これに代えて他の方法、例えば前ラインの右側に回り込むように、あるいは画像の左端からはみ出た場合には、固定値０を参照するようにしても良い。
【０１０９】
また、上述の実施形態では、画像データ１バイトを単位として符号化および復号が行われているが、これに代えて他の単位、例えば１画素あるいは２バイトなどを単位としても良い。
【０１１０】
また上述の実施形態では、白黒画像を扱っていたが、これに代えてカラー画像を扱うようにしてもよい。
【０１１１】
また上述の実施形態では、１画素が１ビットにより構成されていたが、これに代えて他の値、例えば２ビット、４ビットあるいは８ビットとしてもよい。
【０１１２】
また上述の実施形態では、ハードウェアによって復号していたが、これに代えてソフトウェアで復号するようにしてもよい。
【０１１３】
また上述の実施形態では、ディザ処理を行っているが、これに代えてディザ処理を行わないようにしてもよい。
【０１１４】
また上述の実施形態では、背景パターンの横方向の周期性を利用して圧縮を行っているが、これに代えて縦方向、あるいは縦横双方の周期性を利用して圧縮してもよい。
【０１１５】
また上述の実施形態では、異なる周期を検出した場合に最大値を周期としていたが、これに代えて、異なる周期のうち最も頻度が高い値を周期としてもよい。
【０１１６】
［他の実施形態］
なお、本発明は、複数の機器（例えばホストコンピュータ、インタフェイス機器、リーダ、プリンタなど）から構成されるシステムに適用しても、一つの機器からなる装置（例えば、複写機、ファクシミリ装置など）に適用してもよい。
【０１１７】
また、本発明の目的は、前述した実施形態の機能を実現するソフトウェアのプログラムコードを記録した記憶媒体（または記録媒体）を、システムあるいは装置に供給し、そのシステムあるいは装置のコンピュータ（またはCPUやMPU）が記憶媒体に格納されたプログラムコードを読み出し実行することによっても、達成されることは言うまでもない。この場合、記憶媒体から読み出されたプログラムコード自体が前述した実施形態の機能を実現することになり、そのプログラムコードを記憶した記憶媒体は本発明を構成することになる。また、コンピュータが読み出したプログラムコードを実行することにより、前述した実施形態の機能が実現されるだけでなく、そのプログラムコードの指示に基づき、コンピュータ上で稼働しているオペレーティングシステム(OS)などが実際の処理の一部または全部を行い、その処理によって前述した実施形態の機能が実現される場合も含まれることは言うまでもない。
【０１１８】
さらに、記憶媒体から読み出されたプログラムコードが、コンピュータに挿入された機能拡張カードやコンピュータに接続された機能拡張ユニットに備わるメモリに書込まれた後、そのプログラムコードの指示に基づき、その機能拡張カードや機能拡張ユニットに備わるCPUなどが実際の処理の一部または全部を行い、その処理によって前述した実施形態の機能が実現される場合も含まれることは言うまでもない。
【０１１９】
本発明を上記記憶媒体に適用する場合、その記憶媒体には、先に説明した（図６乃至９，１６の一部もしくは全部の）フローチャートに対応するプログラムコードが格納されることになる。
【０１２０】
【発明の効果】
以上の説明したとおり、本発明によれば、周期性を有する画像、特に壁紙などの背景パターンを並べた画像データを符号化する際に、画像全体をより高速に、且つより高圧縮率で圧縮することができる。
【０１２１】
また本発明によれば、壁紙などの背景パターンを並べた画像を符号化した符号を復号する復号回路の回路規模を小さくし、かつ大量のバッファメモリを必要としない、低コストで構成可能な復号を行うことができる。
【図面の簡単な説明】
【図１】画像を印刷する際に用いるソフトウェア群とプリンタとの関係を示す概念図である。
【図２】プリンタ１１１１の基本構成を示すブロック図である。
【図３】図１に示したプリンタドライバ４が生成する符号化データに含まれる各符号の一例を示すテーブルを示す図である。
【図４】カウント符号の一例を示すテーブルを示す図である。
【図５】図３及び図４に示した各符号の使用例を説明する図である。
【図６】プリンタドライバ４が行うメインの処理のフローチャートである。
【図７】ステップＳ４における処理の詳細を示すフローチャートである。
【図８】ステップＳ１０における処理の詳細を示すフローチャートである。
【図９】ステップＳ１１における処理の詳細を示すフローチャートである。
【図１０】印刷データの一例を示す図である。
【図１１】図１０の印刷データを構成する各パターンを示す図である。
【図１２】復号回路１３の詳細な構成を示すブロック図である。
【図１３】符号化前、もしくは復号後の画像データの構成を示す図である。
【図１４】ラインバッファ３１の各々のアドレスに、図１３に示す画像データがどのようにして格納されるのかを説明する図である。
【図１５】図１３に示す画像データがどのようなタイミングで処理されるかを説明する図である。
【図１６】制御回路１５が実行する印刷制御処理手順を示すフローチャートである。
【図１７】本発明の実施形態における画像処理装置の基本構成を示す図である。
【図１８】ビットマップ管理テーブルの構成例を示す図である。
【図１】
0004164257.tif 000002
【図２】
0004164257.tif 000003
【図３】
0004164257.tif 000004
【図４】
0004164257.tif 000005
【図５】
0004164257.tif 000006
【図６】
0004164257.tif 000007
【図７】
0004164257.tif 000008
【図８】
0004164257.tif 000009
【図９】
0004164257.tif 000010
【図１０】
0004164257.tif 000011
【図１１】
0004164257.tif 000012
【図１２】
0004164257.tif 000013
【図１３】
0004164257.tif 000014
【図１４】
0004164257.tif 000015
【図１５】
0004164257.tif 000016
【図１６】
0004164257.tif 000017
【図１７】
0004164257.tif 000018
【図１８】
0004164257.tif 000019