(57)【特許請求の範囲】
【請求項１】
各ピクセルが第１論理状態および第２論理状態を有し、これらのピクセル群の一連のものが第１の次元に並べられ、該一連のピクセル群が第２の次元に複数並べられた直交アレイのピクセル群を表すビット・マップ・データ・ファイルを圧縮するシステムであって、
前記ビット・マップ・データ・ファイルを圧縮されていない形態で含むデータ・ファイル記憶領域、
前記複数の一連のピクセル群のそれぞれを連続して分析して、前記第１の次元において、前記一連のピクセル群のピクセルが第１論理状態から第２論理状態に変化する位置および第２論理状態から第１論理状態に変化する位置を判断し、および、前記複数の一連のピクセル群のそれぞれについて変化ベクトル・データ・テーブルを作成するための、前記データ・ファイル記憶領域に接続された変化ベクトル・ジェネレータ、
前記変化ベクトル・データ・テーブルを分析して、各領域が第１論理状態を有する隣接したピクセル群を含む複数のチェーンゴン領域に前記ビット・マップ・データ・ファイルを分割するための、前記変化ベクトル・ジェネレータに接続されたチェーンゴン・ジェネレータであって、前記変化ベクトル・データ・テーブルを用いて前記複数のチェーンゴン領域のそれぞれについて符号化のためのヘッダ情報を有するチェーンゴン・リストを作成し、該ヘッダ情報が、前記複数のチェーンゴン領域のそれぞれについて、前記第１および第２の次元における前記各チェーンゴン領域の位置をそれぞれ示す第１および第２のオフセット・データ値および前記第２の次元における前記複数のチェーンゴン領域のそれぞれの長さを示す長さデータ値を含み、前記複数の一連のピクセル群のうち連続する１番目と２番目のものについて前記変化ベクトル・データ・テーブルを分析して、該１番目の隣接したピクセル群が第１論理状態を有し且つ第１論理状態を有する該２番目の隣接したピクセル群のピクセルに隣接する場合に、前記１番目および２番目の隣接したピクセル群からピクセルをチェーンゴン・リストに割り当てるチェーンゴン・ジェネレータ、
前記複数のチェーンゴン領域のそれぞれを分析し、および、前記複数のチェーンゴン領域のそれぞれに含まれるピクセル群を符号化して、前記複数のチェーンゴン領域のそれぞれについて符号化データを生成する符号化アナライザ、並びに、
前記符号化データを記憶するためのデータ記憶領域
を備えることを特徴とするシステム。
【請求項２】
各ピクセルが第１論理状態および第２論理状態を有し、これらのピクセル群の一連のものが第１の次元に並べられ、該一連のピクセル群が第２の次元に複数並べられた直交アレイのピクセル群を表すビット・マップ・データ・ファイルを圧縮するシステムであって、
前記ビット・マップ・データ・ファイルを分析して、各領域が第１論理状態を有する隣接したピクセル群を含む複数のチェーンゴン領域に前記ビット・マップ・データ・ファイルを分割するチェーンゴン・ジェネレータであって、前記複数のチェーンゴン領域のそれぞれについて符号化のためのヘッダ情報を有するチェーンゴン・リストを作成し、該ヘッダ情報が、前記複数のチェーンゴン領域のそれぞれについて、前記第１および第２の次元における前記各チェーンゴン領域の位置をそれぞれ示す第１および第２のオフセット・データ値および前記第２の次元における前記複数のチェーンゴン領域のそれぞれの長さを示す長さデータ値を含み、前記複数の一連のピクセル群のうち連続する１番目と２番目のものについて前記ビット・マップ・データ・ファイルを分析して、該１番目の隣接したピクセル群が第１論理状態を有し且つ第１論理状態を有する該２番目の隣接したピクセル群のピクセルに隣接する場合に、ピクセルをチェーンゴン・リストに割り当てるチェーンゴン・ジェネレータ、
前記複数のチェーンゴン領域のそれぞれを分析し、および、前記複数のチェーンゴン領域のそれぞれに含まれるピクセル群を符号化して、前記複数のチェーンゴン領域のそれぞれについて符号化データを生成する符号化アナライザ、並びに、
前記符号化データを記憶するためのデータ記憶領域
を備えることを特徴とするシステム。
【請求項３】
各ピクセルが第１論理状態および第２論理状態を有し、これらのピクセル群の一連のものが第１の次元に並べられ、該一連のピクセル群が第２の次元に複数並べられた直交アレイのピクセル群を表すビット・マップ・データ・ファイルから符号化データ・ファイルを生成するシステムであって、
前記ビット・マップ・データ・ファイルの前記複数の一連のピクセル群の各一連のピクセル群を連続して分析して、前記第１の次元において、前記一連のピクセル群のピクセルが第１論理状態から第２論理状態に変化する位置および第２論理状態から第１論理状態に変化する位置を判断し、および、前記複数の一連のピクセル群のそれぞれについて変化ベクトル・データ・テーブルを作成するための変化ベクトル・ジェネレータ、並びに、
前記変化ベクトル・データ・テーブルを分析して、各領域が第１論理状態を有する隣接したピクセル群を含む複数のチェーンゴン領域に前記ビット・マップ・データ・ファイルを分割するための、前記変化ベクトル・ジェネレータに接続されたチェーンゴン・ジェネレータであって、前記変化ベクトル・データ・テーブルを用いて前記複数のチェーンゴン領域のそれぞれについて符号化のためのヘッダ情報を有するチェーンゴン・リストを作成し、該ヘッダ情報が、前記複数のチェーンゴン領域のそれぞれについて、前記第１および第２の次元における前記各チェーンゴン領域の位置をそれぞれ示す第１および第２のオフセット・データ値および前記第２の次元における前記複数のチェーンゴン領域のそれぞれの長さを示す長さデータ値を含み、前記複数の一連のピクセル群のうち連続する１番目と２番目のものについて前記変化ベクトル・データ・テーブルを分析して、該１番目の隣接したピクセル群が第１論理状態を有し且つ第１論理状態を有する該２番目の隣接したピクセル群のピクセルに隣接する場合に、前記１番目および２番目の隣接したピクセル群からピクセルをチェーンゴン・リストに割り当てるチェーンゴン・ジェネレータ
を備えることを特徴とするシステム。
【請求項４】
前記複数のチェーンゴン領域のそれぞれを分析し、および、前記複数のチェーンゴン領域のそれぞれに含まれるピクセル群を符号化して、前記複数のチェーンゴン領域のそれぞれについて符号化データを生成する符号化アナライザをさらに備えることを特徴とする請求項３に記載のシステム。
【請求項５】
前記符号化アナライザはデルタ符号化を使用することを特徴とする請求項１、２または４に記載のシステム。
【請求項６】
前記符号化データを受け取り、圧縮された符号化データを生成するコンプレッサをさらに備えることを特徴とする請求項１〜３のいずれかに記載のシステム。
【請求項７】
前記コンプレッサは、ＲＬＥ圧縮、ＬＺ圧縮およびハフマン圧縮の少なくとも一つを含む予め定められた圧縮フォーマットを用いて前記符号化データを圧縮することを特徴とする請求項６に記載のシステム。
【請求項８】
各ピクセルが第１論理状態および第２論理状態を有し、これらのピクセル群の一連のものが第１の次元に並べられ、該一連のピクセル群が第２の次元に複数並べられた直交アレイのピクセル群を表すビット・マップ・データ・ファイルを圧縮するためにコンピュータを使用する方法であって、
前記複数の一連のピクセル群の各一連のピクセル群を連続して分析して、前記第１の次元において、前記一連のピクセル群のピクセルが第１論理状態から第２論理状態に変化する位置および第２論理状態から第１論理状態に変化する位置を判断するステップ、
前記第２の次元における前記一連のピクセル群のそれぞれに対する前記位置の値を変化ベクトル・データ・テーブルに記憶するステップ、
前記変化ベクトル・データ・テーブルを分析して、各領域が第１論理状態を有する隣接したピクセル群を含む複数のチェーンゴン領域に前記ビット・マップ・データ・ファイルを分割するステップであって、前記変化ベクトル・データ・テーブルを分析することが、前記複数の一連のピクセル群のうち連続する１番目と２番目のものについて前記変化ベクトル・データ・テーブルを分析すること、および、該１番目の隣接したピクセル群が第１論理状態を有し且つ第１論理状態を有する該２番目の隣接したピクセル群のピクセルに隣接する場合に、前記１番目および２番目の隣接したピクセル群からピクセルをチェーンゴン・リストに割り当てることによって符号化のためのヘッダ情報を有するチェーンゴン・リストを作成し、該ヘッダ情報が、前記複数のチェーンゴン領域のそれぞれについて、前記第１および第２の次元における前記各チェーンゴン領域の位置をそれぞれ示す第１および第２のオフセット・データ値を含み、且つ前記第２の次元における前記複数のチェーンゴン領域のそれぞれの長さを示す長さデータ値を含むステップ、並びに、
前記複数のチェーンゴン領域のそれぞれを分析し、および、前記複数のチェーンゴン領域のそれぞれに含まれるピクセルを符号化して、前記複数のチェーンゴン領域のそれぞれの符号化データを生成するステップ
を含むことを特徴とする方法。
【請求項９】
各ピクセルが第１論理状態および第２論理状態を有し、これらのピクセル群の一連のものが第１の次元に並べられ、該一連のピクセル群が第２の次元に複数並べられた直交アレイのピクセル群を表すビット・マップ・データ・ファイルから符号化データ・ファイルを生成するためにコンピュータを使用する方法であって、
前記ビット・マップ・データ・ファイルを、各領域が第１論理状態を有する隣接したピクセル群を含む複数のチェーンゴン領域に分割するステップ、
前記複数のチェーンゴン領域のそれぞれを分析し、および、前記複数のチェーンゴン領域のそれぞれに含まれるピクセルを符号化して、前記複数のチェーンゴン領域のそれぞれについての符号化データを生成するステップ、並びに、
前記複数のチェーンゴン領域のそれぞれについて符号化のためのヘッダ情報を有するチェーンゴン・リストを、前記複数の一連のピクセル群のうち連続する１番目と２番目のものについて前記ビット・マップ・データ・ファイルを分析すること、および、該１番目の隣接したピクセル群が第１論理状態を有し且つ第１論理状態を有する該２番目の隣接したピクセル群のピクセルに隣接する場合に、ピクセルをチェーンゴン・リストに割り当てることによって作成し、該ヘッダ情報が、前記複数のチェーンゴン領域のそれぞれについて、前記第１および第２の次元における前記各チェーンゴン領域の位置をそれぞれ示す第１および第２のオフセット・データ値を含み、且つ前記第２の次元における前記複数のチェーンゴン領域のそれぞれの長さを示す長さデータ値を含むステップ
を含むことを特徴とする方法。
【請求項１０】
各ピクセルが第１論理状態および第２論理状態を有し、これらのピクセル群の一連のものが第１の次元に並べられ、該一連のピクセル群が第２の次元に複数並べられた直交アレイのピクセル群を表すビット・マップ・データ・ファイルから符号化データ・ファイルを生成するためにコンピュータを使用する方法であって、
記憶場所から前記ビット・マップ・データ・ファイルを受け取るステップ、
前記ビット・マップ・データ・ファイルを、各領域が第１論理状態を有する隣接したピクセル群を含む複数のチェーンゴン領域に分割するステップ、並びに、
前記複数のチェーンゴン領域のそれぞれについて符号化のためのヘッダ情報を有するチェーンゴン・リストを、前記複数の一連のピクセル群のうち連続する１番目と２番目のものについて前記ビット・マップ・データ・ファイルを分析すること、および、該１番目の隣接したピクセル群が第１論理状態を有し且つ第１論理状態を有する該２番目の隣接したピクセル群のピクセルに隣接する場合に、ピクセルをチェーンゴン・リストに割り当てることによって作成し、該ヘッダ情報が、前記複数のチェーンゴン領域のそれぞれについて、前記第１および第２の次元における前記各チェーンゴン領域の位置をそれぞれ示す第１および第２のオフセット・データ値を含み、且つ前記第２の次元における前記複数のチェーンゴン領域のそれぞれの長さを示す長さデータ値を含むステップ
を含むことを特徴とする方法。
【請求項１１】
前記複数のチェーンゴン領域のそれぞれを分析し、および、前記複数のチェーンゴン領域のそれぞれにおけるピクセルを符号化して、前記複数のチェーンゴン領域のそれぞれについて符号化データを生成するステップをさらに含むことを特徴とする請求項１０に記載の方法。
【請求項１２】
前記複数のチェーンゴン領域のそれぞれを分析しおよびピクセルを符号化するときにデルタ符号化を用いることを特徴とする請求項８、９または１１に記載の方法。
【請求項１３】
前記符号化データを圧縮するステップをさらに含むことを特徴とする請求項１２に記載の方法。
【請求項１４】
前記圧縮するステップにおいて、ＲＬＥ圧縮、ＬＺ圧縮およびハフマン圧縮の少なくとも一つを含む予め定められた圧縮フォーマットを使用して前記符号化データを圧縮することを特徴とする請求項１３に記載の方法。
【発明の詳細な説明】
【０００１】
【技術分野】
本発明は、一般にデータ圧縮を行うシステムおよび方法に関し、具体的にはラスタ・グラフィック画像の圧縮を行うシステムおよび方法に関する。
【０００２】
【発明の背景】
コンピュータのアプリケーションにおいて、グラフィックスはたいへん広く使用されている。コンピュータ間のドキュメントの送信において、文字フォントのようなグラフィック・データ（画像データないし図形データ）の送信がよく行われる。この送信には、一方のファクシミリ（ＦＡＸ）装置から他のＦＡＸ装置へのファクシミリ・メッセージの送信やホスト・コンピュータからプリンタへのデータの送信が含まれる。
【０００３】
グラフィック・データは、ラスタ・グラフィック・データとして送信されることがある。この場合に、グラフィック画像は、送信に先立ってビット・マップ・データ・ファイルにされる。例えば、ＦＡＸ装置はドキュメントを走査（スキャン）し、各ページごとのビット・マップ・データ・ファイルを生成する。このビット・マップ・データ・ファイルは、送信時間を短縮するために送信に先立ち圧縮される。この圧縮により、コンピュータの使用効率が大幅にアップし、ファクシミリ電話コールが遠距離の場合には、通話料の節約にもなる。国際電信電話諮問委員会（ＣＣＩＴＴ）が作成した標準化の規定には、周知のファクシミリ圧縮の標準規格が多く存在する。これらは広く使用されているが、ＣＣＩＴＴの圧縮標準規格を使用したデータ圧縮は遅く、かつ、グラフィック画像の効率的な圧縮にはなっていない。
【０００４】
コンピュータ（例えば、ホスト・コンピュータに接続されたプリンタの一部であるコンピュータ）は、プリンタによって印刷されるべきページに関する画像データを転送することができる。プリンタは、テキスト・データに組み込まれた文字フォントを受信することが多い。プリンタは、組み込まれた文字フォントを使用して、所望のフォントで高品質の印刷を行うことができる。これらのすべての事例に共通する項目は、一方のコンピュータが他方のコンピュータに画像を送信するということである。
【０００５】
画像データを転送するのに必要なリソースは、システムによって異なる。例えば、“Microsoft Word”（マイクソフト・ワード）ワード・プロセッサのようなワード・プロセッシング・システムでは、画像データを処理するために高度な計算能力および大容量のメモリを備えた処理能力の高い中央処理装置（ＣＰＵ）が必要とされる。同様にして、“PostScript”（ポストスクリプト）ソフトウェアを使用するような印刷システムでは、送信側コンピュータと受信側コンピュータの双方に大量のデータ処理が必要となる。また、これにより、高処理能力のＣＰＵと大容量のメモリが必要となる。
【０００６】
上述したタイプの画像送信システムは、高処理能力のＣＰＵおよび大容量のメモリに必要なコストを許容できない低コストのシステムでの使用には適しないことが分かる。したがって、高処理能力のＣＰＵおよび大容量のメモリを必要としないラスタ・グラフィック画像の圧縮および画像データの転送を行うためのシステムおよび方法に対する要求が強く存在する。
【０００７】
【発明の概要】
本発明は、ピクセルの直交アレイ（直交配列）を表すビット・マップ・データ・ファイルを圧縮するシステムに組み込まれる。このピクセルの直交アレイは、第１の次元に配列した一連のピクセル群を第２の次元に複数個配列したものである。各ピクセルは第１論理状態および第２論理状態を有する。チェーンゴン（chaingon：鎖状につながったもの）・ジェネレータは、ビット・マップ・データ・ファイルを分析し、このファイルを複数のチェーンゴン領域に分割する。チェーンゴン領域のそれぞれは、第１論理状態を有する隣接したピクセルを含んでいる。符号化アナライザは複数のチェーンゴン領域のそれぞれを分析する。そして、符号化アナライザは、各チェーンゴン領域のピクセルを符号化（コード化）して、各チェーンゴン領域の符号化データを生成する。圧縮データ記憶領域はこの符号化データを受け取り、記憶する。
【０００８】
一実施例において、符号化アナライザはデルタ符号化（デルタ・エンコーディング）を使用する。さらに、システムは、符号化データを受け取って圧縮された符号化データを生成するコンプレッサ（圧縮器）を備えている。このコンプレッサは、予め定められた圧縮フォーマットを用いて、符号化データを圧縮することができる。予め定められた圧縮フォーマットには、ＲＬＥ圧縮、ＬＺ圧縮およびハフマン圧縮の少なくとも一つが含まれる。
【０００９】
さらに、システムには、変化ベクトル・ジェネレータが含まれる。変化ベクトル・ジェネレータは、前記複数個の一連のピクセル群を順次分析し、前記第１の次元において、この一連のピクセル群内のピクセルが第１論理状態から第２論理状態に変化する位置および第２論理状態から第１論理状態に変化する位置を決定する。変化ベクトル・ジェネレータは、前記複数個の一連のピクセル群のそれぞれについて変化ベクトル・テーブルを生成する。この実施例において、チェーンゴン・ジェネレータは、ビット・マップ・データ・ファイルを複数のチェーンゴン領域に分割するために変化ベクトル・テーブルを使用する。チェーンゴン領域のそれぞれには、第１論理状態にある隣接したピクセル群が含まれる。
【００１０】
他の実施例において、チェーンゴン・ジェネレータは、各チェーンゴン領域についてチェーンゴン・リストを作成する。第１の連続する複数の一連のピクセル群における一連のピクセル群の第１の特定のものの位置が、第２の連続する複数の一連のピクセル群における一連のピクセル群の第１の特定のものと隣接しているかどうかを判断する際に、チェーンゴン・ジェネレータは、前記複数個の一連のピクセル群の第１および第２の連続するものについてビット・マップ・データ・ファイルを分析する。
【００１１】
【実施例】
本発明は、高処理能力のＣＰＵおよび大容量メモリを必要とせずに、一方のコンピュータから他方のコンピュータへ画像データを転送するシステムを提供するものである。記憶容量およびコストの面から、考えうる全てのフォント・タイプを格納することは、プリンタのような装置では不可能である。プリンタに多くのフォント・タイプが格納されていても、プリンタは、今後必要となる新たな文字フォントを使用できるようにしておかなければならない。本発明のシステムは、ラスタ・データを処理して、ラスタ・データのサイズを大幅に削減する。これにより、高処理能力および大容量メモリを備えていない低コストのシステムであっても、テキスト・データに新たな文字フォントを組み込むための柔軟性が得られる。従来のシステムはアウトライン・フォントのようなラスタ・フォントを組み込むことができるが、これらのシステムは、そのようなフォントの一つをサポートすることでさえメモリを多く必要とする。例えば、アウトライン・フォント・セットは、一般に、フォント・セットの処理用に約60キロバイト（ＫＢ）のコードを、フォント・セットのアウトライン用に40ＫＢから100 ＫＢをそれぞれ必要とする。したがって、単一のアウトライン・フォント・セットの転送には、160 ＫＢ程度のメモリが必要となる。プリントされたページの代表的なものには、タイムズ・ローマン（Times-Roman ）、タイムズ・ローマン・ボールド（Times-Roman Bold）およびタイムズ・ローマン・イタリック（Times-Roman Italics ）のようないくつかのフォントが含まれている。これらのそれぞれは、個々に定める必要がある個別フォントと考えられる。したがって、複数のフォントの使用により、メモリの必要性が非常に増大する。
【００１２】
これに対して、本発明のシステムは、300 ＤＰＩ（ドット／インチ）の固定解像度における各フォント・セットについて、各フォント・セットのラスタ・データのサイズを約３ＫＢから15ＫＢに縮小する。これにより、メモリ・リソースが比較的制限されている多くの低コストの装置（例えば、複写機、ファクシミリ（ＦＡＸ）装置、プリンタ等）に本発明のシステムを使用することが可能となる。メモリの必要性が軽減されることにより、ファクシミリ・メッセージ内にフォント・セットを組み込むことが現実のものとなる。組み込まれたフォント・セットのサイズが劇的に縮小されることは、組み込まれたフォントを有するテキスト・データの転送時間が縮小されることをも意味する。転送時間が縮小されることにより、データの転送が効率的なものとなり、ファクシミリ装置のようなコンピュータの場合には転送コストの低減につながる。また、このシステムは、上述した装置間の通信に柔軟性をも提供する。本発明を多くの装置に利用することにより、相互運用能力が従来技術により達成できたものよりも増大する。
【００１３】
ビット・マップ・データは、非常に低レベルのデータ形式とみなされている。受信側コンピュータは、プリンタやＦＡＸ装置を問わず、従来システム（PostScriptのように、データは大量のデータ処理を必要とする高レベルのフォーマットで転送される）が必要とする高度なデータ処理を行うことなく、組み込まれた文字フォントを使用することができる。このように、本発明によると、あまり高度でないマイクロプロセッサを受信側コンピュータに使用することができ、コストがさらに低減される。
【００１４】
本発明により処理される画像データはラスタ画像である。ラスタ画像は、連続した水平方向の走査列（水平走査列）からなる。各水平走査列は、一連のピクセル群からなる。ラスタ画像の各ピクセルは一または複数のデータ・ビットによって表される。その最も簡単な形式において、各ピクセルは、そのピクセルが「有色」かどうかを表す一つのデータ・ビットだけで表される。「有色」とは、そのピクセルが特定の表示メディア上で見ることができることをいう。簡単な表示メディアは「背景色」（バックグラウンド・カラー）を有する。この「背景色」は、特定の表示メディアでは見ることができないピクセルのデータ値を示している。「前景色」（フォアグラウンド・カラー）は背景色のデータ値とは異なるデータ値を有するピクセルを対応する。したがって、前景色は特定の表示メディア上で見ることができる。例えば、レーザ・プリンタのような典型的なプリンタでは、各ピクセルは、そのピクセルが有色かどうかを示すためのデータ・ビットを一つ有する。ピクセルが前景色（例えば、黒色）の場合に、そのピクセルは第１のデータ値（すなわち、第１論理状態）を有し、背景色（例えば、白色）の場合に、第２のデータ値（すなわち、第２反転論理状態）を有する。一方、ビデオ・ディスプレイ端末のピクセルは、白色の前景色に対して第１論理状態を、黒色の背景色に対して第２論理状態をそれぞれ有することもある。したがって、同じ論理状態が、特定の表示メディアに依存して、異なった物理的表示になる場合がある。ピクセルの実際のデータ値は、特定の表示メディアに依存する。
【００１５】
一般のプリンタ（例えば、レーザ・プリンタ）は、各ピクセルについて、そのピクセルが有色かどうかを示すデータ・ビットを一つ有する。上述したように、ピクセルは、有色の場合（すなわち、画像で見える）に第１論理状態を、有色でない場合（すなわち、画像で見えない）に逆の第２論理状態をそれぞれ有する。解像度300 ＤＰＩの代表的なプリンタにおいて、解像度300 ＤＰＩとは、各水平走査列の１インチ当たりに300 ピクセルが存在し、また、１インチ当たりに300 本の水平走査列が存在することを意味する。したがって、8.5 インチ×11インチのページは、各水平走査列ごとに2550ピクセルを有する。各水平走査列におけるピクセルの位置を示す値は０〜2549の範囲となる。「水平走査列」は、各ピクセル列を水平方向に走査する一般的な装置について使用される用語である。本発明は、垂直方向に走査する装置にも同様に適用することができる。
【００１６】
本発明は、図１の機能ブロック図に示すシステム10に組み込まれる。システム10は、中央処理装置（ＣＰＵ）12およびメモリ14を含んでいる。メモリ14は、ランダム・アクセス・メモリ（ＲＡＭ）とリード・オンリー・メモリ（ＲＯＭ）の双方を含んでいてもよい。データ記憶領域16（メモリ14の一部であってもよい）は、システム10によって処理されるラスタ・フォントまたは他の画像データを含んでいる。システム10が画像データを処理するために、データ記憶領域16に全体画像が記憶されている必要はない。典型的なアプリケーションでは、データ記憶領域16は、画像データの一部を受け取り、画像データをデータ・ストリームとして実時間で処理するテンポラリー・バッファであってもよい。システム10がＦＡＸ装置に含まれている場合に、走査エンジン18は、送信対象である印刷されたページを走査するために使用される。走査エンジン18からのデータは、データ記憶領域16に与えられる。データ記憶領域16は、システム10がデータ・ストリームを実時間で処理している間、テンポラリー・バッファとして働き、画像データを保持する。
【００１７】
プリンタ20はシステム10によって使用され、受け取った画像データを印刷する。システム10がＦＡＸまたは複写機の場合には、プリンタ20をこのシステムの一構成部分とすることもできる。選択的に、プリンタ20はスタンド・アロンの装置とすることもできる。
【００１８】
従来型の変化ベクトル・ジェネレータ22は、各水平走査列を順次分析し、水平走査列内のピクセルが第１論理状態から第２論理状態へ変化する位置および第２論理状態から第１論理状態に変化する位置を決定する。論理状態が変化する位置は、水平走査列の第１の端部に相当する。したがって、この位置は、各水平走査列の開始点、水平方向、および水平走査列の前のピクセルの論理状態に対して論理状態が変化する各ピクセルの相対位置によって示される長さを有するベクトルと見ることができる。
【００１９】
変化ベクトル・ジェネレータ22は、各水平走査列における変化ベクトルを変化ベクトル・テーブル24に格納する。データ記憶領域16と同様に、変化ベクトル・テーブル24は、画像内の全ての水平走査列の変化ベクトルを含でいる必要はない。変化ベクトル・テーブル24は、一時に、一つの水平走査列の変化ベクトルのみを含んでいてもよい。
【００２０】
チェーンゴン（鎖状の形をしたもの）・ジェネレータ26は、変化ベクトル・テーブル24のデータを分析し、ラスタ画像データを表す一または二以上のチェーンゴンを生成する。チェーンゴンは、水平方向、垂直方向または対角線方向に隣接する同じ論理状態を有する連続したピクセル群として定められる。チェーンゴンの生成については、後に詳述する。この好ましい実施例においては、チェーンゴンは、水平方向、垂直方向または対角線方向に隣接する可視ピクセルとして定められるものとする。チェーンゴンは、チェーンゴン・テーブル28に格納される。チェーンゴン・テーブル28はメモリ14の一部であってもよい。
【００２１】
チェーンゴン・エンコーダ30は、各チェーンゴンを個別に分析し、チェーンゴンを符号化する。続いて、符号化されたチェーンゴンは圧縮され、圧縮データ記憶領域32に格納される。圧縮データ記憶領域32はメモリ14の一部であってもよい。上述したシステム10の様々なコンポーネントは、バス34によって相互に接続される。バス34は、データ信号だけでなく、タイミング信号や電力を供給することもできる。
【００２２】
図２は、水平走査列の変化ベクトルを生成するためにシステム10が用いる方法を示している。この方法はステップ50でスタートする。ステップ52において、変化ベクトル・ジェネレータ22（図１）は、分析対象の水平走査列の論理状態に初期値を設定する。本発明において、水平走査列の第１の端部（例えば、システム10が左から右へ水平走査列を分析する場合には左端）でスタートし、各水平走査列は白色のピクセル（すなわち、可視ピクセル）で始まるものと仮定する。ステップ54において、変化ベクトル・ジェネレータ22は、この最初のピクセルを指し示すように水平走査列のポインタを初期化する。判定ステップ56において、変化ベクトル・ジェネレータ22は、ポインタが指し示すピクセルの論理状態がその水平走査列における前のピクセルの論理状態と異なるかどうかを判定する。論理状態が前のピクセルのものと異なる場合には、判定ステップ56の結果はYES となる。この場合に、ステップ58に進み、変化ベクトル・ジェネレータ22は変化ベクトル・テーブル24（図１）にポインタの現在値を格納する。変化ベクトル・テーブル24の各値は、特定の水平走査列の変化ベクトルであることに注意すべきである。論理状態が前のピクセルのものと変化していない場合には、判定ステップ56の結果はNOとなる。判定ステップ56の結果がNOの場合またはステップ58の実行後に、変化ベクトル・ジェネレータ22は、判定ブロック60に進み、ポインタの現在値が水平走査列の第２の端部に相当するかどうかを判定する。ポインタの現在値が水平走査列の第２の端部に相当していない場合には、判定ブロック60の結果はNOとなる。この場合に、変化ベクトル・ジェネレータ22はステップ62に進み、水平走査列のポインタの現在値をインクリメントし、続いて判定ステップ56に戻り、水平走査列の分析を継続する。ポインタの現在値が水平走査列の第２の端部に相当する場合には、判定ステップ60の結果はYES となり、変化ベクトル・ジェネレータ22はステップ64において水平走査列の分析を終了する。
【００２３】
変化ベクトル・ジェネレータ22の処理の例が、ラスタ画像の一部分70を示す図３に示されている。ラスタ画像は、データ記憶領域16（図１）のビット・マップ・データ・ファイルとして格納されている。部分70は７つの水平走査列72ａ〜72ｇからなる。変化ベクトル・ジェネレータ22は、水平走査列72ａ〜72ｇの各列のピクセルを順次走査し、図２のフローチャートに示す方法で、各水平走査列の変化ベクトルを判定する。最初の水平走査列72ａはピクセル０（白色の最初のピクセルと仮定する）で変化を有する。したがって、最初の水平走査列72ａの最初の変化ベクトルはピクセル０で終了し、次の変化ベクトルはピクセル１（ピクセルが黒から白に変化する位置）で終了する。他の変化ベクトルはピクセル３と６でそれぞれ終了する。このように、最初の水平走査列72ａの変化ベクトルの大きさは、０、１、３および６となる。変化ベクトルは、システム10によってペアで処理される。変化ベクトルの各ペアは、その水平走査列上の同じ論理状態を有する連続したピクセル群を示す。変化ベクトル・ペアによって定められる各連続したピクセル群は、一続きのピクセル群と考えることができる。水平走査列上のまず最初の変化ベクトルは、一続きの黒色ピクセル群が開始する位置を示す。２番目の変化ベクトルは、水平走査列において、一続きの白色ピクセルが開始する位置を示す。したがって、変化ベクトル・ペアの最初の変化ベクトルは算入的であるのに対し、変化ベクトル・ペアの２番目の変化ベクトルは排除的である。すなわち、変化ベクトル・ペアの最初の変化ベクトルは黒色の一続きのピクセル群が開始するピクセル位置を示し、変化ベクトル・ペアの２番目の変化ベクトルはこの黒色の一続きのピクセル群の最後のピクセルの後の位置を示す。一続きのピクセル群の長さは、一ピクセル分の場合もあり、水平走査列全体の長さの場合もある。黒色の初期ピクセルを定め、変化ベクトル・ペアの最初の変化ベクトルとして白色ピクセルを用いることにより、同じタイプの処理が実現される。水平走査列72ａ〜72ｇの変化ベクトル・ペアが表１に示されている。
【００２４】
【表１】
0004101312.tif 000002
【００２５】
変化ベクトル・ジェネレータ22は、変化ベクトル・ペアを変化ベクトル・テーブル24に格納する。上述したように、変化ベクトル・テーブル24は、チェーンゴンの処理を開始するために、全水平走査列の変化ベクトルを含んでいる必要はない。
【００２６】
チェーンゴン・ジェネレータ26は、各水平走査列の変化ベクトル・ペアを順次分析し、一または二以上のチェーンゴン内に可視ピクセルを置いていく。システム10は、ラスタ画像の変化ベクトルを一回に一水平走査列ずつ分析することによって、全体のラスタ画像用に一または二以上のチェーンゴンを生成する。上述したように、チェーンゴンは、水平方向、垂直方向または対角線方向に隣接する可視ピクセルとして定められる。例えば、水平走査列72ａのピクセル３〜５は、水平方向に隣接している。したがって、チェーンゴン・ジェネレータ26は、それらのピクセルを一つのチェーンゴンに割り当てる。水平走査列72ｂのピクセル５および６は水平方向に互いに隣接し、水平走査列72ａのピクセル３〜５にも隣接している。したがって、水平走査列72ｂのピクセル５および６は、水平走査列72ａのピクセル３〜５を含むチェーンゴンに加えられる。同様にして、水平走査列72ｃのピクセル５および６は、水平方向に互いに隣接し、水平走査列72ｂのピクセル５および６にも隣接している。したがって、水平走査列72ｃのピクセル５および６は、水平走査列72ｂのピクセル５および６、ならびに水平走査列72ａのピクセル３〜５を含むチェーンゴンに加えられる。チェーンゴン・ジェネレータが、オープン状態にあるチェーンゴンに加えるべきピクセルが垂直方向と対角線方向のいずれにも隣接していない水平走査列を発見するまで、オープン状態のチェーンゴンは上述のように成長し続ける。例えば、水平走査列72ｆは、水平走査列72ｅのピクセル５および６に、垂直方向または対角線方向のいずれかにオーバラップするピクセルを含まない。したがって、チェーンゴン・ジェネレータはオープン状態のチェーンゴンをクローズする（閉じる）。各水平走査列に他のチェーンゴンに加えるべき新たなピクセルがある限り、そのチェーンゴンはオープン状態を維持し続けることに注意すべきである。また、全ての隣接したピクセルが同じチェーンゴンに含まれるとは限らないことにも注意すべきである。後述するように、ある特定のピクセルが複数のチェーンゴンに含まれる場合に、選択ルールが使用され、そのピクセルはある一つのチェーンゴンに割り当てられる。
【００２７】
変化ベクトルは、水平走査列上の一続きの黒色ピクセルの位置を効率的に決定し、チェーンゴンを定めるために使用される。選択的に、チェーンゴン・ジェネレータ26は、ビット・マップ・データ・ファイル自体を分析し、ピクセルが論理状態を変化させる位置を決定することもできる。チェーンゴン・ジェネレータ26は、変化ベクトルを含む最初の水平走査列上の変化ベクトル・ペアのそれぞれに対してチェーンゴンを生成またはオープン状態にする。なぜならば、その水平走査列の変化ベクトル・ペアのそれぞれは、水平方向に隣接していない分離した一続きの黒色ピクセルを示すからである。前の水平走査列の変化ベクトルと、これに続く次の水平走査列の変化ベクトルとが垂直方向または対角線方向のいずれかで隣接する限り、チェーンゴン・ジェネレータ26によってオープン状態にされたチェーンゴンは、オープン状態を維持する。
【００２８】
上述した表１に関連して、図４のフローチャートは、チェーンゴンを生成するプロセスを示している。チェーンゴン・ジェネレータ26（図１）は、ステップ80において、図２のフローチャートに基づいて予め生成された全ての変化ベクトルに対して処理を開始する。
【００２９】
ステップ82において、チェーンゴン・ジェネレータ26は、最初の水平走査列（変化ベクトルを含む）の各変化ベクトル・ペア用のチェーンゴン・リストを開始する。ファクシミリのページの上部で共通するように、変化ベクトルを有しない水平走査列が存在することがあるのは言うまでもない。表１から、最初の水平走査列72ａは、変化ベクトル・ペア（０，１）、（３，６）を有する。この二つの変化ベクトル・ペアは、二つの一続きの黒色ピクセル群が水平走査列72ａに存在することを示している。最初の一続きの黒色ピクセル群はピクセル０で始まり、ピクセル１で終了する。したがって、この一続きのピクセル群は一つの黒色ピクセルからなる。２番目の一続きのピクセル群は、ピクセル３で開始し、ピクセル６で終了する。したがって、この一続きのピクセル群は３つの黒色ピクセルからなる。水平走査列72ａは分析開始後の最初の水平走査列であるので、オープン状態のチェーンゴンは存在しない。したがって、チェーンゴン・ジェネレータ26は二つのチェーンゴンをオープン状態にする。第１のチェーンゴンはピクセル０を含み、第２のチェーンゴンはピクセル３、４および５を含むものである。チェーンゴン・ジェネレータ26は、各チェーンゴンに関する変化ベクトル・ペアを含むチェーンゴン・リストを生成する。チェーンゴン・リスト（変化ベクトル・ペアを含んでいる）は、チェーンゴン・テーブル28に格納される。
【００３０】
ステップ84において、チェーンゴン・ジェネレータ26は、次の水平走査列を処理対象にする。判定ステップ86において、チェーンゴン・ジェネレータ26は、現在分析中の水平走査列の変化ベクトル・ペアが、直前に分析された水平走査列のいずれかの変化ベクトル・ペアとオーバラップするかどうかを判断する。「オーバラップ」とは、ある変化ベクトル・ペアに対応するピクセルが、オープン状態にあるいずれかのチェーンゴンのピクセルと垂直方向または対角線方向において隣接していることをいう。オーバラップは、現在分析中の水平走査列の変化ベクトル・ペアと前に分析された水平走査列の一または複数の変化ベクトル・ペアとを比較することにより、数学的に判断され、オーバラップが存在するかどうかが決定される。例えば、水平走査列72ｂのピクセル５および６は、水平走査列72ａのピクセル３〜５と垂直方向でオーバラップしている（すなわち、水平走査列72ｂのピクセル５が水平走査列72ａのピクセル５と垂直方向で隣接している）。したがって、水平走査列72ｂの変化ベクトル・ペア（５，７）は、水平走査列72ａの変化ベクトル・ペア（３，６）を含んだチェーンゴン（オープン状態）に加えられる。
【００３１】
表１から、水平走査列72ｂは、変化ベクトル・ペア（１，４）、（５，７）を有する。これらの変化ベクトル・ペアは、１番目の一続きの黒色ピクセル群がピクセル１で開始しピクセル４で終了すること、および２番目の一続きの黒色ピクセル群がピクセル５で開始しピクセル７で終了することを示している。チェーンゴン・ジェネレータ26は、水平走査列72ｂの変化ベクトル・ペアとオープン状態のチェーンゴンとを比較し、オーバラップが存在するかどうかを判断する。
【００３２】
表１から分かるように、水平走査列72ａにおける１番目の一続きの黒色ピクセル群（変化ベクトル・ペア（０，１）によって示される）は、最初のオープン状態のチェーンゴンに対応する。水平走査列72ｂにおける１番目の一続きの黒色ピクセル群（変化ベクトル・ペア（１，４）で示される）は、水平走査列72ａの変化ベクトル・ペア（０，１）と対角線方向で隣接する。したがって、判定ステップ86の結果はYES となる。
【００３３】
また、水平走査列72ｂのピクセル３は水平走査列72ａのピクセル３（このピクセル３は２番目のチェーンゴンの一部である）の下にあるので、水平走査列72ｂにおける１番目の一続きの黒色ピクセル群は、２番目のチェーンゴンと垂直方向で隣接する。したがって、水平走査列72ｂの１番目の一続きの黒色ピクセル群に対応する変化ベクトル・ペアは、第１または第２のチェーンゴンのいずれかに置かれる。一続きのピクセル群を二以上のチェーンゴンに置くことが可能な場合に、チェーンゴン・ジェネレータ26は、複数のチェーンゴンの中で時間的に最も早くオープンしたものにピクセルを割り当てる。したがって、ステップ88において、１番目の変化ベクトル・ペア（水平走査列72ｂにおける１番目の一続きの黒色ピクセル群に対応する）は、１番目のチェーンゴン用のチェーンゴン・リストに置かれる。選択的に、１番目の変化ベクトル・ペア（水平走査列72ｂにおける１番目の一続きの黒色ピクセル群に対応する）を２番目のチェーンゴン用のチェーンゴン・リストに置くこともできる。
【００３４】
判定ステップ90において、チェーンゴン・ジェネレータ26は、現在分析中の水平走査列に未処理の変化ベクトル・ペアが残っているかどうかを判断する。水平走査列に未処理の変化ベクトル・ペアが残っている場合に、判定ステップ90の結果はYES となる。この場合に、ステップ92において、チェーンゴン・ジェネレータは現在分析中の水平走査列の次の変化ベクトル・ペアの処理に移り、判定ステップ86に戻る。表１の例では、水平走査列72ｂの変化ベクトル・ペア（５，７）が残っている。チェーンゴン・ジェネレータ22は、判定ステップ86に戻り、２番目の変化ベクトル・ペアが２番目のチェーンゴンに属すると判断する。チェーンゴン・ジェネレータは、２番目の変化ベクトル・ペアを２番目のチェーンゴン・リストに置く。チェーンゴン・ジェネレータは、水平走査列72ｂの変化ベクトル・ペアのそれぞれに対してこの処理を繰り返す。
【００３５】
現在分析中の水平走査列に未処理の変化ベクトル・ペアが残っていない場合には、判定ステップ90の結果はNOとなり、チェーンゴン・ジェネレータ26は判定ステップ96に進む。判定ステップ96において、チェーンゴン・ジェネレータ26は、現在分析中の水平走査列がデータ・ファイルの最後の水平走査列かどうかを判定する。分析すべき水平走査列がまだ残っている場合には、判定ステップ96の結果はNOとなり、チェーンゴン・ジェネレータ26はステップ84に戻り、次の水平走査列（分析済の水平走査列72ｂに対しては水平走査列72ｃ）を分析する。図３の例では、変化ベクトル・ジェネレータ22およびチェーンゴン・ジェネレータ26は、水平走査列を上から下へ分析する。各水平走査列は左から右へ走査される。上または下から開始し、左から右へまたは右から左へ分析される任意のビット・マップ・データ・ファイルに本発明の原理を適用できることは言うまでもない。例えば、ビット・マップ・データ・ファイルがランドスケープ・モードにおける文字を含む場合には、左から右の代わりに上から下へ符号化を行う方が効率的である。また、選択的に、前景ピクセルよりも背景ピクセルを符号化するために一または複数のチェーンゴンを生成する方が効率的な場合もある。本発明は、ビット・マップ・データ・ファイルにおいて、任意の方向における任意の論理状態のチェーンゴン生成を包含するように意図されている。
【００３６】
上記例において、水平走査列72ｂは最後の水平走査列ではない。したがって、チェーンゴン・ジェネレータ26はステップ84に戻り、水平走査列72ｃを分析する。表１から、水平走査列72ｃは変化ベクトル・ペア（０，３）、（５，７）を有する。水平走査列72ｃのピクセル０，１および２は水平走査列72ｂのピクセル１、２および３にオーバラップしている。水平走査列72ｂのピクセル１、２および３は１番目のチェーンゴンの一部である。したがって、チェーンゴン・ジェネレータ26は、１番目の変化ベクトル・ペア（０，３）を１番目のチェーンゴン・リストに割り当てる。水平走査列72ｃの２番目の一続きの黒色ピクセル群と２番目のチェーンゴンとの間にはオーバラップが存在するので、チェーンゴン・ジェネレータ26は、変化ベクトル・ペア（５，７）を２番目のチェーンゴンに割り当てる。
【００３７】
変化ベクトル・ペアが、前の水平走査列からのチェーンゴンの一ピクセル内にない場合には、判定ステップ86の結果はNOとなる。この場合に、ステップ94に進み、チェーンゴン・ジェネレータ26は、現在の水平走査列の変化ベクトル・ペア用に新たなチェーンゴン・リストを作成する。現在の水平走査列において加えるべき新たな変化ベクトル・ペアを持たないチェーンゴン・リストは、クローズまたはリタイヤされる。これは、その特定のチェーンゴン・リストがもはや成長（拡大）することはなく、その特定のチェーンゴンがチェーンゴン・リストの変化ベクトル・ペアによって完全に確定したことを意味する。例えば、水平走査列72ｆには一つの変化ベクトル・ペア（１，３）のみがある。チェーンゴン・ジェネレータ26は、水平走査列72ｆの分析において、水平走査列72ｅの２番目のチェーンゴンにオーバラップする変化ベクトル・ペアがないと判断する。したがって、この２番目のチェーンゴンはクローズされる。この２番目のチェーンゴン用のチェーンゴン・リストには、水平走査列72ａ〜72ｅの変化ベクトル・ペアが含まれている。同様にして、水平走査列72ｇの変化ベクトル・ペアの中で、水平走査列72ｆの１番目のチェーンゴンにオーバラップするものはない。したがって、チェーンゴン・ジェネレータが水平走査列72ｇを分析したときに、この１番目のチェーンゴンはクローズされる。この１番目のチェーンゴン用のチェーンゴン・リストには、水平走査列72ａ〜72ｆの変化ベクトル・ペアが含まれている。
【００３８】
表１に示す変化ベクトルから分かるように、水平走査列72ｇには変化ベクトル・ペア（４，６）が存在する。この水平走査列72ｇの変化ベクトル・ペア（４，６）に対応するピクセルは、前の水平走査列72ｆの変化ベクトルに対応するピクセルと全く隣接していない。水平走査列72ｇの変化ベクトル・ペアがオーバラップするチェーンゴンが存在しないので、チェーンゴン・ジェネレータ26は、水平走査列72ｇの変化ベクトル・ペア（４，６）のみを含む３番目のチェーンゴンを生成（開始）する。ステップ94において新たなチェーンゴンを生成（開始）した後、チェーンゴン・ジェネレータ26は判定ステップ90に進み、現在の水平走査列において他の変化ベクトル・ペアが存在するかどうかを判断する。
【００３９】
全ての水平走査列が分析され、かつ、変化ベクトル・ペアがチェーンゴン・リストに割り当てられるまで、チェーンゴン・ジェネレータ26は未処理の各水平走査列を順次分析し続ける。分析すべき水平走査列が存在しなくなると、判定ステップ96の結果はYES となり、チェーンゴン・ジェネレータ26はオープン状態にあるチェーンゴンをクローズし、ステップ98においてチェーンゴンの生成処理を終了する。図３の例では、３番目のチェーンゴンは、これに続く水平走査列においてオーバラップするピクセルが存在しないので、クローズされる。
【００４０】
チェーンゴン・リストは、チェーンゴン・テーブル28（図１）に格納される。以下の表２は、図３に示すピクセルに対して生成されたチェーンゴン・テーブルを示している。
【００４１】
【表２】
0004101312.tif 000003
【００４２】
システム10は、各チェーンゴンの符号化を容易にする方法で、チェーンゴン・リストをフォーマットする。フォーマットされた各チェーンゴン・リストは、ヘッダを含んでいる。ヘッダには、ラスタ画像データ・ファイルにおけるチェーンゴンの左上コーナの位置、およびチェーンゴンの長さ（水平走査列の総数）に関する情報が含まれている。チェーンゴン内の各水平走査列のデータがヘッダに続く。表２に示すチェーンゴンNo.1（１番目のチェーンゴン）〜No.3（３番目のチェーンゴン）のデータをフォーマットしたチェーンゴン・リストが、以下の表３に示されている。
【００４３】
【表３】
0004101312.tif 000004
【００４４】
１番目のチェーンゴン（チェーンゴンNo.1）のヘッダにあるＸオフセットおよびＹオフセットは、このチェーンゴンが１番目の水平走査列の１番目のピクセルで開始することを示している。同様にして、２番目のチェーンゴン（チェーンゴンNo.2）および３番目のチェーンゴン（チェーンゴンNo.3）のヘッダのＸオフセットおよびＹオフセットは、これらのチェーンゴンが１番目の水平走査列の４番目のピクセルおよび７番目の水平走査列の５番目のピクセルからそれぞれ開始することを示している。１番目のチェーンゴンのヘッダにあるＹエクステントは、このチェーンゴンが６つの水平走査列の長さを有することを示している。２番目のチェーンゴンおよび３番目のチェーンゴンのヘッダにあるＹエクステントは、これらのチェーンゴンがそれぞれ５つおよび１つの水平走査列の長さを有することを示している。このようにして、全体のラスタ画像データ・ファイルは、一または二以上の一連のチェーンゴンに置き換えられる。
【００４５】
チェーンゴン・リストの確定、チェーンゴン・リストのチェーンゴン・テーブル28（図１）への格納、および上記方法によるチェーンゴン・リストのフォーマットが完了すると、システム10は、デルタ符号化を各チェーンゴンに適用して、各チェーンゴンを独立に符号化する。デルタ符号化はデータ符号化の周知の形式であり、ここでは簡単に示されている。デルタ符号化の開始前に、システム10が全てのチェーンゴンを完全に確定させておく必要はない。例えば、図３における２番目のチェーンゴンは、水平走査列72ｆの分析中にクローズされる。そして、チェーンゴン・ジェネレータ26が変化ベクトル・テーブル24内の水平走査列72ｇについてのエントリをまだ分析している最中に、チェーンゴン・エンコーダ30（図１）がこの２番目のチェーンゴンの符号化を開始することができる。
【００４６】
チェーンゴン・エンコーダ30は、各水平走査列に関連したチェーンゴン・データを、前の水平走査列におけるチェーンゴン・データに関連したチェーンゴンで符号化することにより、各チェーンゴンを符号化する。したがって、各水平走査列のチェーンゴン・データは、前の水平走査列からのチェーンゴン・データに関連してデルタ値またはオフセット値として符号化される。例えば、図５は、図３の１番目のチェーンゴンのみの符号化プロセスを表している。上述したように、表３は、１番目のチェーンゴンが１番目の水平走査列の１番目のピクセルから始まり、６つの水平走査列の長さを有することを示している。表３のフォーマットされた１番目のチェーンゴン・リストのデータ部分（ヘッダに続く部分）の１番目の変化ベクトル・ペアは、変化ベクトル・ペア（０，１）である。１番目のチェーンゴンの次の変化ベクトル・ペア（１，４）は、この直前のエントリに関連して符号化される。図３の例では、１番目のチェーンゴンの次の変化ベクトル・ペア（１，４）のデルタ値は（＋１，＋３）となる。これは、次の水平走査列における一続きの黒色ピクセル群が、前の開始位置の右へ１ピクセルだけ移動した箇所から開始し、前の終了位置の右へ３ピクセルだけ移動した箇所で終了することを示している。これらのデルタ値は、現在のチェーンゴン・データから前のチェーンゴン・データを差し引くことにより容易に求められる。元のチェーンゴンの変化ベクトル・ペアと１番目のチェーンゴンのデルタ値は、以下の表４に示されている。
【００４７】
【表４】
0004101312.tif 000005
【００４８】
表４から分かるように、全てのデルタ値は前のデータの値からのオフセットのみである。したがって、デルタ符号化を使用することにより、データの値のサイズが削減される。チェーンゴンは、その定義から、ビット・マップ・データ・ファイル内の閉じた関連ピクセル群であるので、デルタ値は一般に小さなものとなる。各デルタ値は複数のデータ・ビットによって表される。ほとんどのデルタ値が小さくなる傾向にあるので、符号化プロセスはより予測可能なものとなる。後に詳述するように、これにより、最もよく出現するオフセット値に対しては少ないデータ・ビット数を使用し、大きく、あまり出現しないオフセット値に対してはデータ・ビット数を多く使用してデルタ符号化を行うことができる。このタイプの統計的符号化は、この技術分野において周知である。例えば、修正ハフマン符号（ファクシミリのデータ符号化に共通して使用されている）は、統計学に依存しており、よく出現するデータ・パターンに対しては少ないデータ・ビット数を選択し、あまり出現しないデータ・パターンに対しては多くのデータ・ビット数を選択している。
【００４９】
図６に示す曲線は、チェーンゴンのデルタ符号化プロセスの統計的性質を示している。オフセット値零（０）は非常に多く出現し、最大の頻度で発生する。オフセット値＋１および−１は次に多く出現するものである。他のオフセット値の発生頻度は小さい。システム10は２つのデータ・ビットを使用して、３つの最もよく出現するオフセット値を表現する。例えば、データ・ビット００はオフセット値零を表す。データ・ビット０１はオフセット値＋１を表し、データ・ビット１１はオフセット値−１を表す。あまり出現しないオフセット値は、より多くのデータ・ビットで表される。例えば、データ・ビット１０１１はオフセット値＋２を表し、データ・ビット１０１０はオフセット値−２を表す。同様にして、データ・ビット１００１はオフセット値＋３を表す。出現頻度の小さなオフセット値を表すためには、より多くのデータ・ビットが必要となる。表４の１番目のチェーンゴンに対するデルタ符号化の値と上記データ・ビット・パターンを使用すると、１番目のチェーンゴンを符号化したデータは、００  ０１  ０１  １００１  １１  １１  ０１  ００  ００  ００  ００  ００となる。
【００５０】
チェーンゴン・エンコーダ30によって生成された符号化データは、一方の符号の終端部分と他の新たな符号の開始部分とを識別するためのデリミタを必要としない。各符号のデータ・ビットはユニークであり、システム10はその符号のデータ・ビットのパターンにより特定の符号の終端部分を認識する。例えば、上記例における１番目のデータ・ビット００は、オフセット値０を表す。データ・ビット００で始まる他のデータ・ビット・パターンは存在しない。したがって、システム10は、このデータ・ビット００を完結した符号として認識する。同様にして、データ・ビット０１はオフセット値＋１を表す。データ・ビット０１で始まる他のデータ・ビット・パターンは存在しない。このようにして、各符号は、そのデータ・ビット・パターンによってユニークに識別される。
【００５１】
オフセット値を表すデルタ符号化データ・ビットがチェーンゴン・エンコーダ30によって決定されると、このデルタ符号化データ・ビットを、受信側コンピュータに送信する前にさらに圧縮することができる。これを行うために、システム10はＬＺデータ圧縮を使用する。ＬＺデータ圧縮により、デルタ符号化データ・ビットはさらに圧縮される。ＬＺデータ圧縮は、この技術分野において周知であり、ここでは説明を省略する。選択的に、他の多くの周知のデータ圧縮技術（例えば、ＲＬＥ（Run Length Encoding ）やハフマン符号化）を用いることもできる。本発明は、圧縮技術の特定の適用順序に制限されるものではない。例えば、システム10はハフマン符号化を行った後にＬＺデータ圧縮を行うこともできるし、まずＬＺデータ圧縮を行い、続いてハフマン符号化を行うこともできる。チェーンゴンを圧縮したデータは、圧縮データ記憶領域32（図１）に格納される。この記憶領域32はメモリ14の一部であってもよい。
【００５２】
圧縮データ記憶領域32の圧縮データは、上述したように、テキスト・データまたはファクシミリ・メッセージ内に組み込み、データまたはメッセージとして送信することができる。圧縮データは、そのデータに施された圧縮プロセスを逆に行うことにより、効率的に伸張される。データの圧縮および伸張はこの技術分野において周知であり、ここでは説明を省略する。
【００５３】
チェーンゴン・データは、上述のプロセスの逆を行うことにより復号することができる。１番目のチェーンゴンのデータ・ビット・パターンは、チェーンゴンの開始点からのオフセット値を示している。ＸオフセットおよびＹオフセットは１番目のチェーンゴンの水平走査列の位置を、Ｙエクステントは１番目のチェーンゴンの水平走査列の個数をそれぞれ示している。この情報により、符号化プロセスを容易に実行することができる。複数のチェーンゴンを含むデータに対しては、論理ＯＲ演算により前のチェーンゴンと組み合わせて、各チェーンゴンを一つのバッファに連続して伸張することができる。一続きのピクセル群を満たすことは、特に機械語サイズ（例えば、32ビット）と適合した繰り返しの一続きピクセル群に対しては高速である。
【００５４】
チェーンゴンで表現することにより、文字フォント・セットのようなラスタ画像データは、典型的な文字フォント・セットに必要なスペースよりも劇的に小さなスペースで表すことが可能となる。以下の表５のデータは、従来技術を用いた場合に典型的な文字フォント・セットに必要となるデータ記憶容量、システム10が同じ文字フォント・セットをチェーンゴンに処理した場合のデータ記憶容量、およびチェーンゴンをさらにＬＺデータ圧縮を用いて圧縮した場合のデータ記憶容量を示している。
【００５５】
【表５】
0004101312.tif 000006
0004101312.tif 000007
【００５６】
表５から分かるように、12ポイントのタイムズ・ローマンの文字フォント・セットは、従来のシステムの記憶量として14.4ＫＢを必要とする。これに対し、システム10は、同じ文字フォント・セットを3.5 ＫＢの少ない記憶量にすることができる。ＬＺデータ圧縮を用いてチェーンゴン・データを圧縮すると、同じ文字フォント・セットが僅か1.5 ＫＢになる。したがって、システム10を使用することにより、約13ＫＢの記憶量が節約できることになる。スペース（記憶量）の節約は、より大きなフォント・サイズに対しては一層劇的なものとなる。
【００５７】
データ圧縮自体によっても、文字フォント・セット・データと比較すると、スペースの節約になるが、システム10は、データ圧縮のみにより得られるスペースの節約よりも一層の節約を行うことができる。以下の表６に示すデータは、チェーンゴンのみ、ＬＺデータ圧縮のみ、およびチェーンゴンとＬＺデータ圧縮を組み合せたものの圧縮比を示している。
【００５８】
【表６】
0004101312.tif 000008
【００５９】
表６から分かるように、12ポイントのタイムズ・ローマン（Times-Roman ）文字フォント・セットをチェーンゴン処理することにより、圧縮比は文字フォント・データ・セットに対して4.1 ：１になる。ＬＺデータ圧縮のみを使用した場合には、圧縮比は2.3 ：１になる。これは、チェーンゴン・ラスタ化処理だけでもデータ圧縮のみの使用よりも圧縮比が改善されていることを示している。チェーンゴン・ラスタ化処理をＬＺデータ圧縮と組み合わせると、圧縮比は9.4 ：１になる。したがって、システム10がラスタ画像データを処理する有効なツールを提供することは容易に理解されるであろう。システム10を用いたスペースの節約およびデータ処理の容易化は、より多くの装置が画像処理機能を組み込むことができることを意味する。画像データ処理に必要なメモリが少なくて済み、かつ、高処理能力および高コストのＣＰＵがデータ処理に必要なくなることから、これらの装置は結局、低コストとなる。
【００６０】
本発明についての様々実施例および利点について説明してきたが、上記説明は例示であり、本発明の広い原理内において、詳細な変更を加えることができるのは言うまでもない。したがって、本発明は、特許請求の範囲によってのみ限定されるものである。
【図面の簡単な説明】
【図１】本発明のシステムを示す機能ブロック図である。
【図２】図１に示すシステムが変化ベクトル・テーブルを生成する方法を示すフローチャートである。
【図３】図２のフローチャートを使用して変化ベクトルを生成する様子を示すビット・マップ・データ・ファイルのサンプルである。
【図４】図１に示すシステムがチェーンゴンを生成する方法を示すフローチャートである。
【図５】図４に示すフローチャートを使用してチェーンゴンを生成する様子を示すビット・マップ・データ・ファイルのサンプルである。
【図６】図１のシステムの符号化部分によって使用される予測符号頻度を示す。
【符号の説明】
12  ＣＰＵ
14  メモリ
16  データ記憶領域
18  走査エンジン
20  プリンタ
22  変化ベクトル・ジェネレータ
24  変化ベクトル・テーブル
26  チェーンゴン・ジェネレータ
28  チェーンゴン・テーブル
30  チェーンゴン・エンコーダ
32  圧縮データ記憶領域
【図１】
0004101312.tif 000009
【図２】
0004101312.tif 000010
【図３】
0004101312.tif 000011
【図４】
0004101312.tif 000012
【図５】
0004101312.tif 000013
【図６】
0004101312.tif 000014