(57)【特許請求の範囲】
【請求項１】
画像に対して、ｎ行ｍ列のマトリクスを用いて擬似中間調処理を施す擬似中間調処理手段と、
前記擬似中間調処理が施された画像における符号化対象画素から行方向に距離ｎ×ａ（ａ＞０）だけ離れた第１参照画素と、前記符号化対象画素から列方向に距離ｍ×ｂ（ｂ＞０）離れた第２参照画素とを、設定された参照順位に従って参照する参照手段と、
前記参照手段が参照している参照画素が、前記符号化対象画素を符号化するのに有効である場合には、当該参照画素を用いて前記符号化対象画素を符号化する符号化手段とを備え、
前記参照順位は、前記第１参照画素と前記第２参照画素のうち前記符号化対象画素との位置関係が、前記符号化対象画素の直前に符号化された前画素と当該前画素の符号化時に前記符号化手段が用いた参照画素との位置関係を満たす参照画素から参照するように設定されることを特徴とする画像符号化装置。
【請求項２】
前記第１参照画素は、それぞれ異なるａに対応する複数の参照画素であり、前記第２の参照画素は、それぞれ異なるｂに対応する複数の参照画素であることを特徴とする請求項１に記載の画像符号化装置。
【請求項３】
画像に対して、ｎ行ｍ列のマトリクスを用いて擬似中間調処理を施す擬似中間調処理工程と、
前記擬似中間調処理が施された画像における符号化対象画素から行方向に距離ｎ×ａ（ａ＞０）だけ離れた第１参照画素と、前記符号化対象画素から列方向に距離ｍ×ｂ（ｂ＞０）離れた第２参照画素とを、設定された参照順位に従って参照する参照工程と、
前記参照工程で参照している参照画素が、前記符号化対象画素を符号化するのに有効である場合には、当該参照画素を用いて前記符号化対象画素を符号化する符号化工程とを備え、
前記参照順位は、前記第１参照画素と前記第２参照画素のうち前記符号化対象画素との位置関係が、前記符号化対象画素の直前に符号化された前画素と当該前画素の符号化時に前記符号化手段が用いた参照画素との位置関係を満たす参照画素から参照するように設定されることを特徴とする画像符号化方法。
【請求項４】
コンピュータに請求項３に記載の画像符号化方法を実行させるためのコンピュータプログラム。
【請求項５】
請求項４に記載のコンピュータプログラムを格納したことを特徴とする、コンピュータ読み取り可能な記憶媒体。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、画像を符号化する画像符号化装置、符号コマンドからなる符号データに基づいて画像を復号する画像復号装置、画像符号化号方法、画像復号方法、プログラム、記憶媒体に関するものである。
【０００２】
【従来の技術】
従来、画像データを圧縮する際に、水平方向および垂直方向に同一の画素値を持つ画素が連続する傾向が高いことを利用して、注目位置との相関が高い、直左または直上の位置を参照して符号化を行うことが一般的であった。
【０００３】
また、圧縮しようとする画像データがディザマトリクスによる減色処理を施した画像データである場合には、減色処理を施す際に隣接した画素には異なった演算が適用されるため、近隣の画素よりもむしろ減色処理に使用したディザマトリクスの周期だけ離れた画素との相関が高い。したがってこのような場合、減色処理に使用したディザマトリックスの周期が既知である場合には、注目位置からディザマトリクスの周期だけ離れた、左または上の位置を参照して符号化を行うという方法がある。
【０００４】
【発明が解決しようとする課題】
しかしながら、上記方法によれば、画像データの周期とディザマトリクスの周期が異なる場合に、注目位置と参照位置の相関があまり高くないために、効率よく圧縮を行うことができないという欠点を有する。例えば、圧縮しようとする画像データが、解像度が異なる原画像に解像度変換を施した後に減色処理を施した画像データであるような場合に、このような問題が発生することがある。
【０００５】
本発明は以上問題に鑑みて成されたものであり、画像を効率よく、特に短い符号で符号化することを目的とする。
【０００６】
【課題を解決するための手段】
本発明の目的を達成するために、例えば本発明の画像符号化装置は以下の構成を備える。
【０００７】
すなわち、画像に対して、ｎ行ｍ列のマトリクスを用いて擬似中間調処理を施す擬似中間調処理手段と、
前記擬似中間調処理が施された画像における符号化対象画素から行方向に距離ｎ×ａ（ａ＞０）だけ離れた第１参照画素と、前記符号化対象画素から列方向に距離ｍ×ｂ（ｂ＞０）離れた第２参照画素とを、設定された参照順位に従って参照する参照手段と、
前記参照手段が参照している参照画素が、前記符号化対象画素を符号化するのに有効である場合には、当該参照画素を用いて前記符号化対象画素を符号化する符号化手段とを備え、
前記参照順位は、前記第１参照画素と前記第２参照画素のうち前記符号化対象画素との位置関係が、前記符号化対象画素の直前に符号化された前画素と当該前画素の符号化時に前記符号化手段が用いた参照画素との位置関係を満たす参照画素から参照するように設定されることを特徴とする。
【００１０】
本発明の目的を達成するために、例えば本発明の画像符号化方法は以下の構成を備える。
【００１１】
すなわち、画像に対して、ｎ行ｍ列のマトリクスを用いて擬似中間調処理を施す擬似中間調処理工程と、
前記擬似中間調処理が施された画像における符号化対象画素から行方向に距離ｎ×ａ（ａ＞０）だけ離れた第１参照画素と、前記符号化対象画素から列方向に距離ｍ×ｂ（ｂ＞０）離れた第２参照画素とを、設定された参照順位に従って参照する参照工程と、
前記参照工程で参照している参照画素が、前記符号化対象画素を符号化するのに有効である場合には、当該参照画素を用いて前記符号化対象画素を符号化する符号化工程とを備え、
前記参照順位は、前記第１参照画素と前記第２参照画素のうち前記符号化対象画素との位置関係が、前記符号化対象画素の直前に符号化された前画素と当該前画素の符号化時に前記符号化手段が用いた参照画素との位置関係を満たす参照画素から参照するように設定されることを特徴とする。
【００１４】
【発明の実施の形態】
以下添付図面を参照して、本発明を好適な実施形態に従って詳細に説明する。
【００１５】
［第１の実施形態］
図１は本実施形態における画像符号化装置として機能するコンピュータ１内の各ソフトウェア群とプリンタ６との関係を示す図である。
【００１６】
図中、１はコンピュータであり図１０に示す基本構成を備える。図１０はコンピュータ１の基本構成を示すブロック図である。図１０において１１０１はＣＰＵで、ＲＡＭ１１０２やＲＯＭ１１０３内に格納されたプログラムやデータを用いて本装置全体の制御を行うと共に、後述の画像符号化処理やプリンタに対してプリントコマンドを出力する出力制御処理などを行う。１１０２はＲＡＭで、外部記憶装置１１０４や記憶媒体ドライブ１１０９からロードされたプログラムやデータを一時的に記憶するエリアを備えると共に、ＣＰＵ１０１が各種の処理を実行する際に用いるワークエリアも備える。１１０３はＲＯＭで、本装置全体の制御を行うプログラムや設定データ等を格納する。
【００１７】
１１０４はハードディスクなどの外部記憶装置で、下記のソフトウェア群や符号化対象のデータをファイルとして保存することができる。１１０５、１１０６は夫々キーボード、マウスで、ポインティングデバイスとして各種の指示を本装置に対して入力することができる。１１０７は表示装置で、ＣＲＴや液晶画面などにより構成されており、符号化対象のデータやアプリケーションのＧＵＩなどを表示することができる。１１０８は画像入力装置で、スキャナやディジタルカメラなど、画像を本装置に対してディジタルデータとして入力することができる装置により構成されており、入力した画像はファイルとして外部記憶装置１１０４やＲＡＭ１１０２に出力される。
【００１８】
１１０９は記憶媒体ドライブで、ＣＤ−ＲＯＭやＤＶＤ−ＲＯＭなどの記憶媒体からプログラムやデータなどを読み込んで外部記憶装置１１０４に出力する。なお、下記のソフトウェア群や符号化対象のデータを上記記憶媒体に記憶しておき、記憶媒体ドライブ１１０９からこれらを本装置に供給しても良い。１１１０はＩ／Ｆ（インターフェース）でＬＡＮやインターネットに接続するための、ＵＳＢやパラレルポートなどにより構成されており、本実施形態では後述のプリンタ６と接続するためにパラレルポートとするが、これに限定されるものではない。１１１１は上述の各部を繋ぐバスである。
【００１９】
図１に戻って、２はオペレーティングシステムであり、コンピュータ１が備えるハードウェア、およびアプリケーション３、プリンタドライバ４、ポートドライバ５などのソフトウェアを管理する。アプリケーション３は、例えばワードプロセッサのようなアプリケーションソフトウェアであり、操作者の指示に従って文書の作成・印刷などを行う。４はプリンタドライバであり、アプリケーション３が発行した印刷指令をオペレーティングシステム２を経て受け取り、該印刷指令をプリンタ６が解釈可能なプリンタコマンドに変換する。５はポートドライバであり、プリンタドライバ４が変換したプリンタコマンドをオペレーティングシステム２を経て受け取り、パラレルポートを経由してプリンタ６に送信する。
【００２０】
上記オペレーティングシステム２、アプリケーション３、プリンタドライバ４、ポートドライバ５などのソフトウェア群は上述の通り、外部記憶装置１１０４に保存されている。６はプリンタであり、ポートドライバ５から受信したプリンタコマンドに従って印刷を行う。
【００２１】
図２は本実施形態における画像復号装置として機能するプリンタ６の基本構成を示すブロック図である。図中、１１はパラレルポートであり、コンピュータ１からプリンタコマンドを受信する。１２はＦＩＦＯ（ファーストインファーストアウト）メモリであり、パラレルポート１１が受信した符号化データを記憶し、記憶したデータを先入れ先出しの順に復号回路１３に出力する。復号回路１３は、ＦＩＦＯメモリ１２に記憶された符号列データを復号し、プリンタエンジン１４に出力する。プリンタエンジン１４はレーザビームプリンタエンジンであり、制御回路１５の指示により、復号回路１３が出力した画像データに従って印刷を行う。画像データはシアン、マゼンタ、黄、黒の各色ごとに面順次で出力される。１５は制御回路であり、例えば１チップＣＰＵで構成され、パラレルポート１１、ＦＩＦＯメモリ１２、復号回路１３、およびプリンタエンジン１４の制御を行う。
【００２２】
以下、印刷動作について説明する。
【００２３】
操作者がコンピュータ１側でキーボード１１０５やマウス１１０６を用いてアプリケーション３を操作して印刷データを生成し、これを印刷指示すると、アプリケーション３からオペレーティングシステム２を経由してプリンタドライバ４に印刷指令が渡される。プリンタドライバ４はアプリケーション３から発行された印刷指令に基づき、赤、緑、青の３色からなるＲＧＢ画像データを作成し、次いでＲＧＢ画像データを、シアン、マゼンタ、黄、黒の４色からなるＣＭＹＫ画像データに変換する。この際同時に所定のディザマトリクスを使用して減色処理を行う。そして、プリンタドライバ３は、後述する符号化手順に基づき、作成した画像データから符号化データを生成し、用紙サイズ、ビットマップデータのラインの長さとライン数などを指定する印刷制御コマンドとともに出力する。ポートドライバ５は、プリンタドライバ３が作成した、印刷制御コマンドおよび符号化データからなる一連のプリンタコマンドを、プリンタ６に送信する。
【００２４】
制御回路１５はパラレルポート１１を経由してプリンタコマンドを受信する。受信したプリンタコマンドが印刷制御コマンドであれば、印刷制御のために制御回路１５の内部に保持する。また、受信したプリンタコマンドが符号化データであった場合は、ＦＩＦＯメモリ１２に格納する。その後、ページ終了コマンドの受信などにより、１ページを構成するプリンタコマンドの受信が完了したことを検出したときに、制御回路１５はプリンタエンジン１４に印刷の開始を指示する。
【００２５】
印刷の開始が指示されると、プリンタエンジン１４は給紙カセットから用紙を給紙し、用紙が所定の位置に到達したときに、復号回路１３に画像データの出力を要求する。復号回路１３は、あらかじめＦＩＦＯメモリ１２から符号化データを読み出し、復号した画像データを内部のバッファに保持しておき、プリンタエンジン１４から画像データの出力を要求されたときに、内部のバッファに保持していた画像データを出力する。復号回路１３は、画像データを保持していたバッファに空きができたときに、ＦＩＦＯメモリ１２から引き続く符号化データを読み出し、復号して内部のバッファに保持する。このようにして符号化データは順次復号されて画像データとして出力され、１ページの画像データの出力が全て終了すると、印刷が完了する。
【００２６】
次に、図３および図４に示すテーブルを参照し、図１に示したプリンタドライバ３が生成する符号について説明する。
【００２７】
図３は、図１に示したプリンタドライバ３が生成する符号化テーブルの一例を示す図である。本実施形態で説明する符号は、ビット単位で可変長であり、例えば２ビットから１８ビットまでのビット列で表現される。各符号は、ハフマン符号と同様に、先頭から順に調べることにより符号を識別することができるように構成されている。
【００２８】
なお、本実施形態では符号化の際に２箇所の左参照位置、および２箇所の上参照位置を参照するものとし、減色処理の際に使用されたディザマトリクスの特性に合わせ、例えば左参照位置は、注目位置の１バイト左、および４バイト左の位置が、また上参照位置は注目位置の４ライン上、および２ライン上かつ２バイト左の位置に決められている。
【００２９】
図３に示すように、符号のビット列が「１」で開始する場合はＣＯＰＹ  ＵＰ１コマンドである。このコマンドは後述する長さを示す符号が後続し、あらかじめ決定された高順位の上参照位置から、後続する符号が示す長さのバイト列を複写することを指示する。
【００３０】
また、符号のビット列が「０１１」で開始する場合は、ＣＯＰＹ  ＵＰ２コマンドである。このコマンドは後述する長さを示す符号が後続し、あらかじめ決定された低順位の上参照位置から、後続する符号が示す長さのバイト列を複写し、かつ高順位の上参照位置と低順位の上参照位置とを入れ替えることを指示する。
【００３１】
また、符号のビット列が「００１」で開始する場合はＲＡＷコマンドである。このコマンドは生データを示す８ビットデータが後続し、後続する８ビットのデータの値を持つ１バイトのデータを指定する。
【００３２】
また、符号のビット列が「０１０」で開始する場合はＣＯＰＹ  ＬＥＦＴ１コマンドである。このコマンドは後述する長さを示す符号が後続し、あらかじめ決定された高順位の左参照位置位置から、後続する符号が示す長さのバイト列を複写することを指示する。
【００３３】
また、符号のビット列が「０００１」で開始する場合はＣＯＰＹ  ＬＥＦＴ２コマンドである。このコマンドは後述する長さを示す符号が後続し、あらかじめ決定された低順位の左参照位置位置から、後続する符号が示す長さのバイト列を複写し、かつ高順位の左参照位置と低順位の左参照位置とを入れ替えることを指示する。
【００３４】
また、符号のビット列が「００００」の場合はＥＯＢコマンドであり、符号ブロックの終了を指示する。
【００３５】
低順位の参照位置にてデータが一致した場合には、以後もその参照位置にてデータが一致する可能性が高い。したがって低順位の参照位置を識別するより長い符号を出力した際には、該参照位置の順位を上げて以後より短い符号により識別されるようにすれば、その後該参照位置にてデータが一致した場合に出力する符号の長さは短くなる。よって、ＣＯＰＹ  ＵＰ２コマンド、ＣＯＰＹ  ＬＥＦＴ２コマンドを実行することで、高順位の参照位置と低順位の参照位置とを入れ替え、今後出力する符号の長さが短くなる。
【００３６】
図４は図３に示したＣＯＰＹ  ＵＰ１コマンド、ＣＯＰＹ  ＵＰ２コマンド、ＣＯＰＹ  ＬＥＦＴ１コマンドあるいはＣＯＰＹ  ＬＥＦＴ２コマンドに後続する、長さを示す符号の符号化テーブルの一例である。
【００３７】
図４に示すように、符号のビット列が「１」である場合は１バイトの長さを指示する。
【００３８】
また、符号のビット列が「０１」で開始する場合は１ビットのデータが後続し、後続する１ビットのデータに２を加えた長さ、すなわち２バイトまたは３バイトの長さを指示する。
【００３９】
また、符号のビット列が「００１」で開始する場合は２ビットのデータが後続し、後続する２ビットのデータに４を加えた長さ、すなわち４バイトから７バイトまでの長さを指示する。
【００４０】
また、符号のビット列が「０００１」で開始する場合は３ビットのデータが後続し、後続する３ビットのデータに８を加えた長さ、すなわち８バイトから１５バイトまでの長さを指示する。
【００４１】
また、符号のビット列が「００００１」で開始する場合は４ビットのデータが後続し、後続する４ビットのデータに１６を加えた長さ、すなわち１６バイトから３１バイトまでの長さを指示する。
【００４２】
また、符号のビット列が「０００００１」で開始する場合は５ビットのデータが後続し、後続する５ビットのデータに３２を加えた長さ、すなわち３２バイトから６３バイトまでの長さを指示する。
【００４３】
また、符号のビット列が「００００００１」で開始する場合は６ビットのデータが後続し、後続する６ビットのデータに６４を加えた長さ、すなわち６４バイトから１２７バイトまでの長さを指示する。
【００４４】
また、符号のビット列が「０００００００」で開始する場合は７ビットのデータが後続し、後続する７ビットのデータに１２８を加えた長さ、すなわち１２８バイトから２５５バイトまでの長さを指示する。
【００４５】
なお、これらの符号は、あらかじめ多数の画像データで各コマンドの出現頻度を求めておき、ハフマン符号と同様に、出現頻度の高いコマンドに短い符号を、出現頻度の低いコマンドに比較的長い符号を割り当てることにより圧縮率を高くすることができる。
【００４６】
次に図５（ａ）、（ｂ）を参照し、符号化処理について実例を挙げて説明する。図５（ａ）は符号化対象の画像データを示し、図５（ｂ）は符号化されたデータを示す図である。図５（ａ）に示すように、最下行には１０バイトの画像データ（注目データ）００、００、１２、３４、５６、７８、００、ＢＣ、ＤＥ、００が左から並んでおり、その２行上には画像データ１２、３４、５６、７８、９Ａ、ＢＣ、ＤＥ、００、００、００（参照データ）が左から並んでいる。現在符号化あるいは復号しようとしている画像データは最下行であり、またこの時点で高順位の左参照位置は１バイト左の位置に（つまり低順位の左参照位置は４バイト左の位置に）、低順位の上参照位置は２ライン上かつ２バイト左の位置に（つまり高順位の上参照位置は４ライン上の位置に）なっているものとする。
【００４７】
ここで最下行の先頭バイト００は、ビット列００１  ００００００００、すなわち生データ００を示すＲＡＷコマンドに符号化することができる。
【００４８】
また、次のバイト００は、ビット列０１０  １、すなわち１バイトの長さを高順位の左参照位置、すなわち１バイト左の位置から複写するＣＯＰＹ  ＬＥＦＴ１コマンドに符号化することができる。
【００４９】
また、その次のバイト列１２、３４、５６、７８はビット列０１１  ００１  ００、すなわち４バイトの長さを低順位の上参照位置、すなわち２ライン上かつ２バイト左の位置から複写するＣＯＰＹ  ＵＰ２コマンドに符号化することができる。この結果、上参照位置の順位が入れ替わり、以後のＣＯＰＹ  ＵＰ１コマンドは低順位から高順位となった２ライン上かつ２バイト左の位置を、またＣＯＰＹ  ＵＰ２コマンドは高順位から低順位となった４ライン上の位置をそれぞれ参照する。
【００５０】
その次のバイト００は再び、ビット列００１  ００００００００、すなわち生データ００を示すＲＡＷコマンドに符号化することができる。
【００５１】
また、その次のバイト列ＢＣ、ＤＥ、００はビット列１  ０１  １、すなわち３バイトの長さを高順位の上参照位置、すなわち２ライン上かつ２バイト左の位置から複写するＣＯＰＹ  ＵＰ１コマンドに符号化することができる。
【００５２】
以上のようにして、画像データを符号化することができる。次に、図６に示すフローチャートを参照し、プリンタドライバ４の処理の詳細を説明する。図６はプリンタドライバ４が行う処理のフローチャートである。このフローチャートに従ったプログラムはプリンタドライバ４として上述のとおり外部記憶装置１１０４、もしくは記憶媒体に格納されており、ＣＰＵ１０１により（記憶媒体の場合、記憶媒体ドライブ１１０９により）ＲＡＭ１１０２に読み出され実行される。
【００５３】
プリンタドライバ４がオペレーティングシステム２から呼び出されると、まずステップＳ５にて呼び出しの種類が描画指令であるか否かを判定する。呼び出しの種類が描画指令であった場合は、ステップＳ６にて描画処理を行い、処理を終了する。具体的には、オペレーティングシステム２を経由してアプリケーション３から指示された、文字、図形またはビットマップ等を赤、緑、青の３色を用いた各色８ビットの画像に変換し、ＲＡＭ１１０２に記録する。
【００５４】
ステップＳ５にて呼び出しの種類が描画指令でなかった場合は、ステップＳ７にて呼び出しの種類がページ終了指令であるか否かを判定する。呼び出しの種類がページ終了指令であった場合には、ステップＳ８にて色変換処理を行う。具体的にはステップＳ６にてＲＡＭ１１０２に記録された赤、緑、青の３色を用いた各色８ビットの画像を、所定のディザマトリックスを使用して、シアン、マゼンタ、黄、黒の４色からなるたとえば各色４ビットの画像に変換する。変換後の画像もＲＡＭ１１０２に記憶しておく。
【００５５】
次にステップＳ９にて、印刷条件指定コマンド、具体的には用紙サイズ、給紙カセット、解像度、階調数、１ラインのバイト数、１ページのライン数など印刷に必要な条件を指定するコマンドを出力する。
【００５６】
次にステップＳ１０からステップＳ１４までの各処理を、シアン、マゼンタ、黄、黒の各色に対して行い、各色毎の画像データコマンドを出力する。まずステップＳ１０にて、ステップＳ８にて使用したディザマトリックスに応じた圧縮パラメタ、すなわち符号化時に使用する、ＣＯＰＹ  ＵＰコマンドおよびＣＯＰＹＬＥＦＴコマンドが参照する位置（高順位の上参照位置、低順位の上参照位置、高順位の左参照位置、低順位の左参照位置）を出力する。次にステップＳ１１にて、後述する符号化手順に従い、画像データを符号化する。このときに、ステップＳ１０にて出力した圧縮パラメタが指定する、ＣＯＰＹ  ＵＰコマンドおよびＣＯＰＹ  ＬＥＦＴコマンドが参照する位置を用いて符号化を行う。詳細は後述する。
【００５７】
次にステップＳ１２にて、ステップＳ１１で符号化された画像データのサイズおよびライン数を指定する画像データコマンドヘッダを出力する。次にステップＳ１３にて、ステップＳ１１で符号化された画像データを出力する。次にステップＳ１４にて、シアン、マゼンタ、黄、黒の各プレーンの処理が全て終了したか否かを判定する。シアン、マゼンタ、黄、黒の各プレーンの処理が全て終了していない場合はステップＳ１０に戻り、色を変えて次のプレーンの処理を行う。こうしてシアン、マゼンタ、黄、黒の各プレーンの処理が全て終了すると、ステップＳ１４からステップＳ１５に進み、ページの終了を指定する改ページコマンドを出力して処理を終了する。
【００５８】
ステップＳ７にて呼び出しの種類がページ終了指令でなかった場合には、ステップＳ１６にて、呼び出しの種類に応じたその他の処理、例えばページ開始指令あるいはプリンタ能力問い合わせ指令等に対応する処理を行い、終了する。
【００５９】
次に、上記ステップＳ１１における符号化処理について、同処理のフローチャートを示す図７を参照して説明する。このフローチャートに従ったプログラムは上記フローチャートのサブルーチンとしてプリンタドライバ４に組み込まれている。
【００６０】
まずステップＳ１９にて、高順位の上参照位置、低順位の上参照位置、高順位の左参照位置および低順位の左参照位置をそれぞれ所定の初期値、すなわち、上記ステップＳ１０で求めた圧縮パラメタに従って設定する。次にステップＳ２０にて、現在の位置、すなわち符号化する画像の位置を画像の先頭行左端に設定する。
【００６１】
次にステップＳ２１にて、現在の位置に対応する高順位の上参照位置が有効な画像データを参照しているか否かを判定する。高順位の上参照位置が有効な画像データを参照している場合には、ステップＳ２２にて、高順位の上参照位置と一致する長さを、現在の位置から始まるバイト列と、高順位の上参照位置から始まるバイト列を比較することにより求める。なおこの際に、行末に達した場合および長さが２５５バイトに達した場合には処理を打ち切るものとする。次にステップＳ２３にて、ステップＳ２２にて求めた、高順位の上参照位置と一致する長さが０であるか否かを判定する。０でない場合にはＣＯＰＹ  ＵＰ１コマンドに符号化できるので、ステップＳ２４にてＣＯＰＹ  ＵＰ１コマンド、すなわち符号１とそれに後続するバイト数（ステップＳ２２で求めた長さ）を示す符号を出力し、処理をステップＳ４０に進める。
【００６２】
一方、ステップＳ２１にて高順位の上参照位置が無効であると判定された場合、ステップＳ２３にて、ステップＳ２２で求めた、高順位の上参照位置と一致する長さが０であると判定された場合は、いずれもステップＳ２５にて、現在の位置に対応する高順位の左参照位置が有効な画像データを参照しているか否かを判定する。高順位の左参照位置が有効な画像データを参照している場合には、ステップＳ２６にて、高順位の左参照位置と一致する長さを、現在の位置から始まるバイト列と、高順位の左参照位置から始まるバイト列を比較することにより求める。なおこの際に、行末に達した場合および長さが２５５バイトに達した場合には処理を打ち切るものとする。次にステップＳ２７にて、ステップＳ２６で求めた、高順位の左参照位置と一致する長さが０であるか否かを判定する。０でない場合にはＣＯＰＹ  ＬＥＦＴ１コマンドに符号化できるので、ステップＳ２８にてＣＯＰＹ  ＬＥＦＴ１コマンド、すなわち符号０１０とそれに後続するバイト数（ステップＳ２６で求めた長さ）を示す符号を出力し、処理をステップＳ４０に進める。
【００６３】
ステップＳ２５にて高順位の左参照位置が無効であると判定された場合、ステップＳ２７にて、ステップＳ２６で求めた、高順位の左参照位置と一致する長さが０であると判定された場合は、いずれもステップＳ２９にて、現在の位置に対応する低順位の上参照位置が有効な画像データを参照しているか否かを判定する。低順位の上参照位置が有効な画像データを参照している場合には、ステップＳ３０にて、低順位の上参照位置と一致する長さを、現在の位置から始まるバイト列と、低順位の上参照位置から始まるバイト列を比較することにより求める。なおこの際に、行末に達した場合および長さが２５５バイトに達した場合には処理を打ち切るものとする。次にステップＳ３１にて、ステップＳ３０で求めた、低順位の上参照位置と一致する長さが０であるか否かを判定する。０でない場合にはＣＯＰＹ  ＵＰ２コマンドに符号化できる場合ので、ステップＳ３２にてＣＯＰＹ  ＵＰ２コマンド、すなわち符号０１１とそれに後続するバイト数（ステップＳ３０で求めた長さ）を示す符号を出力し、次にステップＳ３３にて高順位の上参照位置と低順位の上参照位置を入れ替え、処理をステップＳ４０に進める。
【００６４】
ステップＳ２９にて低順位の上参照位置が無効であると判定された場合、およびステップＳ３１にて、ステップＳ３０で求めた、低順位の上参照位置と一致する長さが０であると判定された場合は、いずれもステップＳ３４にて、現在の位置に対応する低順位の左参照位置が有効な画像データを参照しているか否かを判定する。低順位の左参照位置が有効な画像データを参照している場合には、ステップＳ３５にて、低順位の左参照位置と一致する長さを、現在の位置から始まるバイト列と、低順位の左参照位置から始まるバイト列を比較することにより求める。なおこの際に、行末に達した場合および長さが２５５バイトに達した場合には処理を打ち切るものとする。次にステップＳ３６にて、ステップＳ３５で求めた、低順位の左参照位置と一致する長さが０であるか否かを判定する。０でない場合にはＣＯＰＹ  ＬＥＦＴ２コマンドに符号化できるので、ステップＳ３７にてＣＯＰＹ  ＬＥＦＴ２コマンド、すなわち符号０００１とそれに後続するバイト数（ステップＳ３５で求めた長さ）を示す符号を出力し、次にステップＳ３８にて高順位の左参照位置と低順位の左参照位置を入れ替え、処理をステップＳ４０に進める。
【００６５】
ステップＳ３４にて低順位の左参照位置が無効であると判定された場合、およびステップＳ３６にて、ステップＳ３５で求めた、低順位の左参照位置と一致する長さが０であると判定された場合は、いずれもステップＳ３９にて、ＲＡＷコマンド、すなわち符号００１とそれに後続する現在の位置の１バイトのデータを出力し、処理をステップＳ４０に進める。
【００６６】
ステップＳ４０では、ＣＯＰＹ  ＵＰ１、ＣＯＰＹ  ＵＰ２、ＣＯＰＹ  ＬＥＦＴ１、ＣＯＰＹ  ＬＥＦＴ２あるいはＲＡＷコマンドで処理されたバイト数だけ現在の位置を進める。次にステップＳ４１にて、全ての画像データを処理したか否かを判定する。全ての画像データを処理していない場合はステップＳ２１に戻り、符号化を続ける。全ての画像データを処理し終えた場合は、ステップＳ４２にてＥＯＢコマンド、すなわち符号００００を出力し、次にステップＳ４３にて符号をバイト境界に整列する。具体的には、出力した符号の総ビット数が８の整数倍でない場合に、８の整数倍に達するまでビット０を出力する。このようにして符号化の処理が終了すると復帰する。
【００６７】
次に図２に示した復号回路１３の構成を示す図８を用いて、同回路の詳細について説明する。図８は、図２に示した復号回路１３の基本構成を示すブロック図である。
【００６８】
図８において、入力バッファ２１は、ＦＩＦＯメモリ１２から読み出した符号データを格納する。入力バッファ２１は、少なくとも４バイトのデータを格納することができ、バッファに空きが生じ、かつＦＩＦＯメモリ１２にデータがある場合はＦＩＦＯメモリ１２からデータを読み出して格納する。入力バッファ２１はまた、ビットカウンタ２３に保持された、処理済ビット数が８以上になった場合には、不要になった処理済データを破棄する。
【００６９】
第一のセレクタ２２は、例えば１８組の８入力セレクタであり、入力バッファ２１に格納された符号データを、ビットカウンタ２３が示す処理済ビット数に従って選択することにより、コマンドデコード回路２４が処理するために必要な、コマンドの開始位置合わせを行う。これは、入力バッファ２１がバイト単位にデータを保持するのに対し、コマンドはビット単位の可変長データであるため８箇所の開始位置があるために必要なものである。
【００７０】
ビットカウンタ２３は、入力バッファ２１に格納された符号データのうち処理済みのビット数を格納する。ビットカウンタ２３はまた、コマンドデコード回路２４から出力された、コマンドのビット数を加算することによりビットカウンタに格納された値を更新する。ビットカウンタ２３はまた、入力バッファが処理済データを破棄した場合には、破棄したビット数を減算する。ビットカウンタ２３はまた、コマンドデコード回路２４がＥＯＢコマンドを復号したときに、コマンドデコード回路２４からＥＯＢ信号を受信し、バイト境界合わせの処理を行う。具体的には、ビットカウンタの下位３ビットが全て０であれば何もせず、そうでなければ８を加算するとともに下位３ビットをクリアする。
【００７１】
コマンドデコード回路２４は、例えばリードオンリーメモリ、あるいはワイヤードロジックにより構成され、第一のセレクタ２２によって位置合わせが行われた、入力バッファ２１に格納された符号データを復号し、復号したコマンドがＥＯＢコマンドの場合はビットカウンタ２３、上優先ＦＦ２９および左優先ＦＦ３０に、復号したコマンドがＣＯＰＹ  ＵＰ１コマンドまたはＣＯＰＹ  ＵＰ２コマンドの場合は第二のセレクタ２５および第三のセレクタ２６に、復号したコマンドがＣＯＰＹ  ＬＥＦＴ１コマンドまたはＣＯＰＹ  ＬＥＦＴ２コマンドの場合は第四のセレクタ２７および第五のセレクタ２８に、復号したコマンドがＲＡＷコマンドの場合は生データ出力回路３６にそれぞれ信号を出力する。コマンドデコード回路２４はまた、ＣＯＰＹ  ＵＰ１、ＣＯＰＹ  ＵＰ２、ＣＯＰＹ  ＬＥＦＴ１またはＣＯＰＹ  ＬＥＦＴ２コマンドを復号した場合は符号が示すバイト数をも復号し出力するとともに、ＲＡＷコマンドを復号した場合には符号が示す８ビットデータをも復号して出力する。
【００７２】
２５は第二のセレクタであり、上優先ＦＦ２９が０を保持する場合には、コマンドデコード回路２４がＣＯＰＹ  ＵＰ１コマンドを復号したときに出力する信号を、また上優先ＦＦ２９が１を保持する場合には、コマンドデコード回路２４がＣＯＰＹ  ＵＰ２コマンドを復号したときに出力する信号を出力する。
【００７３】
２６は第三のセレクタであり、上優先ＦＦ２９が０を保持する場合には、コマンドデコード回路２４がＣＯＰＹ  ＵＰ２コマンドを復号したときに出力する信号を、また上優先ＦＦ２９が１を保持する場合には、コマンドデコード回路２４がＣＯＰＹ  ＵＰ１コマンドを復号したときに出力する信号を出力する。
【００７４】
２７は第四のセレクタであり、左優先ＦＦ３０が０を保持する場合には、コマンドデコード回路２４がＣＯＰＹ  ＬＥＦＴ１コマンドを復号したときに出力する信号を、また左優先ＦＦ３０が１を保持する場合には、コマンドデコード回路２４がＣＯＰＹ  ＬＥＦＴ２コマンドを復号したときに出力する信号を出力する。
【００７５】
２８は第五のセレクタであり、左優先ＦＦ３０が０を保持する場合には、コマンドデコード回路２４がＣＯＰＹ  ＬＥＦＴ２コマンドを復号したことを示す信号を、また左優先ＦＦ３０が１を保持する場合には、コマンドデコード回路２４がＣＯＰＹ  ＬＥＦＴ１コマンドを復号したことを示す信号を出力する。
【００７６】
２９は上優先ＦＦであり、第一の上複写回路３１あるいは第二の上複写回路３２のいずれが優先されているかを示す値を保持する。上優先ＦＦ２９はまた、コマンドデコード回路２４がＣＯＰＹ  ＵＰ２コマンドを復号したときに、保持している値を反転する。
【００７７】
３０は左優先ＦＦであり、第一の左複写回路３３あるいは第二の左複写回路３４のいずれが優先されているかを示す値を保持する。左優先ＦＦ３０はまた、コマンドデコード回路２４がＣＯＰＹ  ＬＥＦＴ２コマンドを復号したときに、保持している値を反転する。
【００７８】
３１は第一の上複写回路であり、第二のセレクタ２５から信号を受信したときに、複写すべきバイト数をあわせて受信し、受信したバイト数に応じて、ラインバッファ３５からデータを読み取り、読み取ったデータを出力することを繰り返す。
【００７９】
３２は第二の上複写回路であり、第三のセレクタ２６から信号を受信したときに、複写すべきバイト数をあわせて受信し、受信したバイト数に応じて、ラインバッファ３５からデータを読み取り、読み取ったデータを出力することを繰り返す。
【００８０】
３３は第一の左複写回路であり、第四のセレクタ２７から信号を受信したときに、複写すべきバイト数をあわせて受信し、受信したバイト数に応じて、ラインバッファ３５からデータを読み取り、読み取ったデータを出力することを繰り返す。
【００８１】
３４は第二の左複写回路であり、第五のセレクタ２８から信号を受信したときに、複写すべきバイト数をあわせて受信し、受信したバイト数に応じて、ラインバッファ３５からデータを読み取り、読み取ったデータを出力することを繰り返す。
【００８２】
３５はラインバッファであり、複数のラインの復号データを保持するリングメモリとして動作し、第一の上複写回路３１、第二の上複写回路３２、第一の左複写回路３３または第二の左複写回路３４が出力するアドレスに格納されたデータを出力するとともに、現在アドレスレジスタ３７が出力するアドレスに、復号されたデータを格納する。
【００８３】
３６は生データ出力回路であり、コマンドデコード回路２４がＲＡＷコマンドを復号したときに同時に出力される生データを示す８ビットのデータを受信し、受信したデータを出力する。
【００８４】
３７は現在アドレスレジスタであり、現在復号しようとしているデータの位置を示すアドレスを出力するとともに、復号されたデータがラインバッファ３５に格納される毎にカウントアップされる。
【００８５】
また、第一の上複写回路３１、第二の上複写回路３２、第一の左複写回路３３および第二の左複写回路３４には、第一の上複写位置、第二の上複写位置、第一の左複写位置および第二の左複写位置をそれぞれ示すアドレスが保持されており、現在アドレスレジスタ３７がカウントアップされる毎に同様にカウントアップされる。
【００８６】
コマンドデコード回路２４がＣＯＰＹ  ＵＰ１コマンドをデコードすると、引き続くカウントをデコードし、第二のセレクタ２５および第三のセレクタ２６に信号を出力する。そして上優先ＦＦ２９が保持する値にしたがって、第二のセレクタ２５または第三のセレクタ２６のいずれか一方から信号が出力され、その信号にしたがって第一の上複写回路３１または第二の上複写回路３２のいずれか一方が動作する。
【００８７】
例えば上優先ＦＦ２９が保持する値が０である場合、ＣＯＰＹ  ＵＰ１コマンドがデコードされたときに第二のセレクタ２５は信号を第一の上複写回路３１に出力し、第三のセレクタ２６は信号を出力しない。第一の上複写回路３１は、内部に保持する第一の上複写位置を示すアドレスをラインバッファ３５に出力し、ラインバッファ３５に格納された第一の上複写位置のデータを読み込み、読み込んだデータを復号データとしてプリンタエンジン１４に出力する。現在アドレスレジスタ３７は現在位置を示すアドレスを出力し、ラインバッファ３５はそのアドレスに復号データを格納する。次に第一の上複写回路３１、第二の上複写回路３２、第一の左複写回路３３および第二の左複写回路３４の内部にそれぞれ保持される、第一の上複写位置を示すアドレス、第二の上複写位置を示すアドレス、第一の左複写位置を示すアドレスおよび第二の左複写位置を示すアドレス、および現在アドレスレジスタ３７が保持する現在位置を示すアドレスがカウントアップされる。この動作が指定されたバイト数繰り返される。
【００８８】
コマンドデコード回路２４がＣＯＰＹ  ＵＰ２コマンドをデコードすると、引き続くカウントをデコードし、第二のセレクタ２５および第三のセレクタ２６に信号を出力する。そして上優先ＦＦ２９が保持する値にしたがって、第二のセレクタ２５または第三のセレクタ２６のいずれか一方から信号が出力され、その信号に従って第一の上複写回路３１または第二の上複写回路３２のいずれか一方が動作する。
【００８９】
例えば上優先ＦＦ２９が保持する値が０である場合、ＣＯＰＹ  ＵＰ２コマンドがデコードされたときに第三のセレクタ２６は信号を第二の上複写回路３２に出力し、第二のセレクタ２５は信号を出力しない。第二の上複写回路３２は、上述の第一の上複写回路３１の動作と同様に動作するが、上優先ＦＦ２９は保持する値が反転して１となるため、以後のＣＯＰＹ  ＵＰ１コマンドは第二の上参照位置に、またＣＯＰＹ  ＵＰ２コマンドは第一の上参照位置に、それぞれ対応するようになる。
【００９０】
コマンドデコード回路２４がＣＯＰＹ  ＬＥＦＴ１コマンドおよびＣＯＰＹ  ＬＥＦＴ２コマンドをデコードした場合も、上述のＣＯＰＹ  ＵＰ１コマンドおよびＣＯＰＹ  ＵＰ２コマンドの動作と同様に動作する。
【００９１】
コマンドデコード回路２４がＲＡＷコマンドをデコードすると、引き続く８ビットデータをデコードし、生データ出力回路３６に信号を出力する。生データ出力回路３６は、受信した８ビットデータをそのまま復号データとしてプリンタエンジン１４に出力する。現在アドレスレジスタ３７は現在位置を示すアドレスを出力し、ラインバッファ３５はそのアドレスに復号データを格納する。次に第一の上複写回路３１、第二の上複写回路３２、第一の左複写回路３３および第二の左複写回路３４の内部にそれぞれ保持される、第一の上複写位置を示すアドレス、第二の上複写位置を示すアドレス、第一の左複写位置を示すアドレスおよび第二の左複写位置を示すアドレス、 および現在アドレスレジスタ３７が保持する現在位置を示すアドレスがカウントアップされる。
【００９２】
コマンドデコード回路２４がＥＯＢコマンドをデコードすると、ビットカウンタ２３は前述のごとくバイト境界合わせの処理を行うとともに、上優先ＦＦ２９および左優先ＦＦ３０は初期値、例えば０に初期化される。
【００９３】
なお、第一の上複写回路３１、第二の上複写回路３２、第一の左複写回路３３および第二の左複写回路３４の内部にそれぞれ保持される、第一の上複写位置を示すアドレス、第二の上複写位置を示すアドレス、第一の左複写位置を示すアドレスおよび第二の左複写位置を示すアドレス、および現在アドレスレジスタ３７が保持する現在位置を示すアドレスには、あらかじめ制御回路１５により、圧縮パラメタ指定コマンドによって指定された位置に基づいた初期値が設定されているものとする。
【００９４】
また、ラインバッファ３５はリングメモリとして動作するため、第一の上複写回路３１、第二の上複写回路３２、第一の左複写回路３３および第二の左複写回路３４の内部にそれぞれ保持される、第一の上複写位置を示すアドレス、第二の上複写位置を示すアドレス、第一の左複写位置を示すアドレスおよび第二の左複写位置を示すアドレス、 または現在アドレスレジスタ３７が保持する現在位置を示すアドレスがラインバッファ３５の末尾のアドレスである場合には、カウントアップの際にラップアラウンドしてラインバッファ３５の先頭のアドレスが格納されるものとする。
【００９５】
以上の説明により、本実施形態における画像符号化装置、画像復号装置によって、より長い符号に符号化される参照位置が参照された場合に、参照位置と符号の対応を入れ替えることにより、以後該参照位置が参照された際により短い符号に符号化することが出来るため、データの周期にかかわらず効率よく圧縮を行うことが出来る。
【００９６】
また、画像データの周期とディザマトリクスの周期が異なる場合、注目位置の近隣でかつ減色処理の際に注目位置にて適用される演算に近い演算が適用される位置との相関が高い傾向がある。このような位置は少数の位置に限られ、またあらかじめディザマトリクスを調べることにより、あるいはあらかじめさまざまな画像データを用いて統計を取ることにより決定することができるので、このような位置およびディザマトリクスの周期だけ離れた位置の中から参照位置として複数の位置をあらかじめ選んでおくことにより、画像データの周期にかかわらず効率的に符号化することができる。
【００９７】
また、画像データの周期は広い範囲で一定である傾向がある。このため、低順位の参照位置にてデータが一致した場合には、以後もその参照位置にてデータが一致する可能性が高い。したがって低順位の参照位置を識別するより長い符号を出力した際に、該参照位置の順位を上げて以後より短い符号により識別されるようになることにより、その後該参照位置にてデータが一致した場合に出力する符号が短くなるため、順位の入れ替えを行わない場合に較べて、効率的に符号化することができる。
【００９８】
［第２の実施形態］
なお、上述の実施形態では、復号をハードウェアで行っているが、これに代えて復号をソフトウェアで行うようにしてもよい。
【００９９】
また上述の実施形態では、符号化の単位データサイズは１バイトであったが、これに代えて他のサイズ、例えば１画素あるいは２バイトであってもよい。
【０１００】
また上述の実施形態では、２つの参照位置の優先順位を切り替えているが、これに代えて３つ以上の参照位置の優先順位を切り替えるようにしてもよい。
【０１０１】
［他の実施形態］
本発明の目的は、前述した実施形態の機能を実現するソフトウェアのプログラムコードを記録した記憶媒体（または記録媒体）を、システムあるいは装置に供給し、そのシステムあるいは装置のコンピュータ（またはCPUやMPU）が記憶媒体に格納されたプログラムコードを読み出し実行することによっても、達成されることは言うまでもない。この場合、記憶媒体から読み出されたプログラムコード自体が前述した実施形態の機能を実現することになり、そのプログラムコードを記憶した記憶媒体は本発明を構成することになる。また、コンピュータが読み出したプログラムコードを実行することにより、前述した実施形態の機能が実現されるだけでなく、そのプログラムコードの指示に基づき、コンピュータ上で稼働しているオペレーティングシステム(OS)などが実際の処理の一部または全部を行い、その処理によって前述した実施形態の機能が実現される場合も含まれることは言うまでもない。
【０１０２】
さらに、記憶媒体から読み出されたプログラムコードが、コンピュータに挿入された機能拡張カードやコンピュータに接続された機能拡張ユニットに備わるメモリに書込まれた後、そのプログラムコードの指示に基づき、その機能拡張カードや機能拡張ユニットに備わるCPUなどが実際の処理の一部または全部を行い、その処理によって前述した実施形態の機能が実現される場合も含まれることは言うまでもない。
【０１０３】
【発明の効果】
以上の説明により、本発明によって、画像を効率よく、特に短い符号で符号化することができる。
【図面の簡単な説明】
【図１】本発明の実施形態における画像符号化装置として機能するコンピュータ１内の各ソフトウェア群とプリンタ６との関係を示す図である。
【図２】本発明の実施形態における画像復号装置として機能するプリンタ６の基本構成を示すブロック図である。
【図３】図１に示したプリンタドライバ３が生成する符号化テーブルの一例を示す図である。
【図４】図３に示したＣＯＰＹ  ＵＰ１コマンド、ＣＯＰＹ  ＵＰ２コマンド、ＣＯＰＹ  ＬＥＦＴ１コマンドあるいはＣＯＰＹ  ＬＥＦＴ２コマンドに後続する、長さを示す符号の符号化テーブルの一例を示す図である。
【図５】（ａ）は符号化対象の画像データを示す図、（ｂ）符号化されたデータを示す図である。
【図６】プリンタドライバ４が行う処理のフローチャートである。
【図７】ステップＳ１１における符号化処理のフローチャートである。
【図８】図２に示した復号回路１３の基本構成を示すブロック図である。
【図９】コンピュータ１の基本構成を示すブロック図である。
【図１】
0004109875.tif 000002
【図２】
0004109875.tif 000003
【図３】
0004109875.tif 000004
【図４】
0004109875.tif 000005
【図５】
0004109875.tif 000006
【図６】
0004109875.tif 000007
【図７】
0004109875.tif 000008
【図８】
0004109875.tif 000009
【図９】
0004109875.tif 000010