JP2000509212A - 二次元データ圧縮装置および方法 - Google Patents

Abstract

(57)【要約】 画像データ（２０４）を含むデータを圧縮するシステムおよび方法。画像データ（２０４）は、ピクセルアレイで形成されており、ピクセルアレイは、複数の目標ピクセル（２０６）および複数の前位ピクセル（２０６）を有しており、それそれの前位ピクセルは、そのピクセルアレイ内でそれぞれの目標ピクセルより前の位置にある。この発明の方法は、画像データ（２０４）を圧縮して圧縮画像を得ることを含んでいる。圧縮ステップにおいて、ピクセルアレイは、所定の非線形二次元トラバースパターンに従ってトラバースされる（２０６）。一致前位ピクセルのストリングを有する目標ピクセルの各ストリングについて、最長の一致前位ピクセルストリング（２０８、２１０）があれば、それが見つけ出される。目標ピクセルに対して、一致前位ピクセルが見つからなければ、そのような目標ピクセルは、不一致ピクセルと特徴付けられる（２１２）。最終的に、圧縮画像は、エンコードされ（４１２）、伝送されてもよいし、記憶されてもよい（４１６）。

Description

【発明の詳細な説明】 二次元データ圧縮装置および方法 発明の背景 １． 発明の分野 この発明は、データ圧縮システムに関するもので、より詳しくは、画像データ を圧縮形態に圧縮しそして圧縮形態のものを解凍する装置および方法に関するも のである。 ２． 関連技術の説明 一般に、データ圧縮とは、ある与えられたフォーマットのデータを代替フォー マットに変換してその代替フォーマットが原フォーマットよりも少ないビットを 有するようにする如何なるプロセスをも称する。種々のデータ圧縮システムが従 来技術においてよく知られており、デジタルデータ信号の原ストリーム（原デー タ列）を圧縮されたデジタルデータ信号にエンコードするために使用され、そし てその圧縮されたデジタルデータ信号を原データ信号にデコードし戻すのに使用 されている。データ圧縮システムの使用によって、コンピュータシステム同士の 間で通信されるデータの量と必要なデータ記憶空間の量の両方が減る。このよう にして、データ圧縮は、与えられたデジタル情報を伝送するのに必要な時間の量 の節約とデジタル情報を保持するのに必要な記憶装置の量の節約になるので、有 利なものである。 多くのデータ圧縮方法は、デジタルデータおよびデータファイルが典型的にか なりの量の冗長さを含んでいるという事実に頼っている。そのような「冗長圧縮 法」は、データファイルが記憶装置上でより少ない空間を占めるように、または データファイルが通信チャンネル上をより少ない時間で伝送され得るように、デ ータファイルを圧縮するため使われてきている。 冗長圧縮法は、「テキストファイル」を減らすためにも使用できる。テキスト ファイルは、アルファベットの文字、数字および／または句読点類などの一連の 文書文字を含むデータファイルである。テキストファイル用の典型的な冗長法に おいては、まず一連の文書文字中のあるひとつの最初の（先頭の）目標文字の位 置を指定する。最も簡単な形態としては、その最初の目標文字の直前の文字から 始めて、その目標文字と一致するひとつの前位文字（目標文字より前に位置する 文字）が見つかるまで、その最初の目標文字より前にある文字を逆向きに探索（ またはトラバース）する。ひとつの最初の一致する前位文字が見つかると、一致 性をその目標文字より後ろについて延長して、前位文字の中の一致する「文字列 」を見付けることが試みられる。このために、探索は、最初の目標文字の直後に ある新しい目標文字の方へ進むとともに、最初の一致前位文字の直後にある次の 前位文字へと進んで、システムは、後続の目標文字と後続の前位文字が一致する かを判断する。もし、一致すれば、処理は、後続の複数の前位文字に沿って、一 致しなくなるまで続けられる。このようにして、最初の一致前位文字から最後の 一致前位文字までとして、一致文字列が定義される。 このデータを圧縮するには、その一致文字列を二つのデータ項目により表すこ とができる。つまり、（１）一致前位文字列の開始点 （すなわち、一連の複数文字の中における最初の一致前位文字の所在位置）およ び（２）一致前位文字列の長さである。このようにして、前位文字と一致する目 標文字の列は、（１）一致文字列の始点位置と（２）その文字列の長さとを示す データとして簡単に表される。その結果、一致する前位文字列がある目標文字の 列（ストリング）は、各目標文字が独立にエンコードされた場合よりも少ないビ ットで表される。 多くの冗長圧縮法において、ひとつの「最長一致データ列」が探される。その ような方法では、ひとつの最初のデータストリング（データ列）が見つかったと きに処理が停止しない。その代わり、最初の一致前位文字の直前の前位文字から 始めて、複数の前位文字中を逆向きに探索が続けられる。処理は、ひとつの最長 一致データ列が見つかるまで続く（それは最初の一致データ列であるかも知れな い）。単に最初の一致データ列で停止しないで、最長の一致データ列を見つける ことにより、データテキストのさらなる圧縮が達成され得る。 以下の例において、冗長圧縮について説明する。次の文字列が伝送される場合 を仮定する：「ＴＨＥ ＲＡＩＮ ＩＮ ＳＰＡＩＮ ＦＡＬＬＳ ＭＡＩＮＬ Ｙ ＯＮ ＴＨＥ ＰＬＡＮＥ」。このデータは、次のようにエンコードされる 。最初の文字「Ｔ」は、「リテラル」コード（文字そのままのコード）としてエ ンコードされ、圧縮されない（それがリテラルコードであることを示すフラグビ ットにより実際は伸張されるかも知れない）。次いで、二番目の文字「Ｈ」が目 標文字となり、先にエンコードされている文字が探索探索されて、一致があるか 見る。この場合、エンコードされている唯一の先行文字は、次の文字「Ｈ」と一 致しない「Ｔ」である。 したがって、その「Ｈ」文字は、リテラルコードとしてエンコードされる。次い で、「Ｈ」の後の各後続文字が目標文字となり、先にエンコードされている文字 が探索されて、一致があるか探される。この例では、「ＲＡＩＮ」と「ＩＮ」の 間の空白スペースを数えないで、最初の文字一致は、最初に出てくる単語「ＩＮ 」の中の「Ｉ」のところで起こり、それは単語「ＲＡＩＮ」の中の「Ｉ」と一致 する。そこで、一致ストリング（文字列）のサーチが始まり、新しい目標文字は 「ＩＮ」の中の「Ｎ」になる。単語「ＲＡＩＮ」の中の一致した「Ｉ」の直後に ある文字が、その新しい目標文字と比較されて、一致するか調べられる。ご覧の とおり、新しい目標文字と先の一致文字直後の文字は両方とも「Ｎ」であるので 、正に一致する。この処理は、一致が起こらなくなるまで続けられる。このケー スでは、それは単語「ＳＰＡＩＮ」の中の最初の文字（つまり「Ｓ」）のところ で起こる。このようにして、この冗長技術により見つけられた一致データ列は、 「ＩＮ」である（「Ｎ」に続く空白もまた前の空白スペースと一致している）。 次いで、この一致データ列、つまり「ＩＮ」は、一致データ列中の先頭文字（つ まり「ＲＡＩＮ」の中の「Ｉ」）の先頭位置および一致データ列の長さ（このケ ースでは、「Ｉ」、「Ｎ」および「空白」の三文字）としてそれをエンコードす ることにより、圧縮される。この処理は、ファイル全体が圧縮されてエンコード されるまで、テキストファイル全体を通して続けられる。上述したように、最初 の一致ストリングが見つかった後、最長一致ストリングを見つけようとして継続 してもよい。 在来の冗長圧縮は、前位の文書文字を探索するのに、「線形トラバース法」か 「ハッシュ法」のいずれかを採用してきている。しかしながら、これらの両方法 とも、特に圧縮されるデータが文書デー タでなく画像データである場合に、不利な点や欠点を有している。しかしながら 、これらの欠点を説明する前に、画像データのいくつかの面を理解しておくこと が重要である。画像データは、ピクセルの二次元配列を含む。各ピクセルは、テ キストファイルにおける文字に等価であると考えてもよい。各ピクセルは、画像 中の一点を表し、例えば、そのピクセルの色と強度を表すデータを含んでいる。 画像は、エリア全体が一様であったり見かけが極めて類似していたりするような エリアがいくつもあり得る（例えば、青い海が画面の大きい面積を占める場合） ので、ピクセルデータは、パターン化された方式でその画像内で広範囲に複製さ れ得ることがある。したがって、ある目標ピクセルに関して、ある場所において は、他の場所よりも、冗長なピクセルが起こる確率がずっと高い。 画像を圧縮するのに線形トラバース法を採用すると、目標ピクセルと一致する 前位ピクセル（目標ピクセルより前に位置するピクセル）を見つけるのに、一度 に一ピクセルずつそして順番に全部の前位ピクセルを通して後ろ向きにトラバー スすることによって、探索が実行される。したがって、線形トラバース法では、 目標ピクセルに関してある場所には一致ピクセルがより高い確率で見つかるとい う事実を補う試みはなされない。そうではなくて、ピクセルは、一致があればそ れが見つかるまで、前位ピクセルを通して後ろ向きに線形的にトラバースされる にすぎない。したがって、画像データを圧縮するのに線形トラバース法を使用す るのは、非効率であり、高速画像データ圧縮を達成できない。データ圧縮システ ムにおいては画像データが圧縮される（または解凍される）スピードを最大にす ることが極度に重要であるので、線形トラバース法が比較的低速なことはシステ ムの機能を低下させ、その方法が画像データを圧縮お よび解凍するには不利であることになる。 在来のハッシュ法では、前位ピクセルを通して探索して一致ピクセル列（ピク セルストリング）を見つけるのに、「ヒストリアレイ」、「ヒストリアレイポイ ンタ」、「ハッシュ表」および「オフセットアレイ」が用いられる。ヒストリア レイは、ある数のエントリを有し、各エントリは前位ピクセルの入力データスト リームの一部を記憶するものである。ヒストリアレイポインタは、ハッシュアレ イ内の最後のエントリを指す。ハッシュ表は、ヒストリアレイポインタを有する 一連のエントリを含んでいる。オフセットアレイ（またはハッシュリンク表）は 、ある特定のハッシュ値に対応するヒストリアレイ中の前のエントリを指し、オ フセットアレイの中の別の項は、このハッシュ値と関連するヒストリアレイ中の 最も古いエントリを指す。ヒストリアレイポインタ、ハッシュ表およびオフセッ トアレイは、ハッシュデータ構造を構成する。 ハッシングにおいては、ピクセルのデータストリームがスキャンされまたはシ ステムに入力されつつあるとき、ヒストリアレイに記憶されている特定のストリ ングを見つけるのにヒストリアレイポインタ、ハッシュ表およびオフセットアレ イを使用し、ヒストリアレイの中を探索して入力データストリーム中のピクセル のストリングと一致する最長の一致ピクセル列を見つける。最長の一致ストリン グを見つけようとするとき、ハッシュ関数を実行しなければならず、それは数段 のステップを有する。最初に、ハッシュ関数の結果を得なければならず、その関 数はハッシュ表の中のエントリの一つに対するポインタを与えるものである。二 番目に、ハッシュ関数の結果により指されるハッシュ表中に記憶されているポイ ンタを得る。三番目に、ヒストリアレイポインタとハッシュ表から得られたポイ ン タとの差を求める計算をし、その差をヒストリアレイポインタにより指されるオ フセットアレイエントリの中に記憶する。最後に、ヒストリアレイポインタをハ ッシュ関数により指されるハッシュ表エントリの中に記憶する。 さらに、ハッシュデータ構造を維持するために、種々のポインタやエントリを 更新するための計算が実行されなければならない。そのような計算は、圧縮速度 を遅くし、他の機能を実行するのに使える筈の高価なＣＰＵの時間を占有する。 したがって、データ圧縮のためにハッシュ法を採用したシステムは、複雑で資 源集約的である。このように、画像データを圧縮するためにハッシュ法を採用し ているシステムは、難しくて、備えるのに高価であり、そしてハッシュ法を実行 するための計算条件でスピードが遅くなる。 したがって、従来の画像データ圧縮法に存在する不利や欠点を除去するような 、画像を圧縮し解凍する方法および装置に対する必要性が存在する。この発明は 、そのような方法と装置を提供するものである。 発明の概要 この発明は、データのストリームを圧縮するための装置および方法、並びに前 に圧縮されたデータを解凍するための装置および方法である。データは、二次元 か三次元のいずれの画像を表すものでもよい。しかしながら、この発明は、文字 データを含む如何なるタイプのデータを圧縮するのにも使用し得るものと認識さ れたい。 この発明は、画像データは、同一または類似の色の大きな面積部 分がいくつもあって、二次元に冗長性を有するであろうという観察をうまく利用 したものである。この発明は、この事実を利用して、前位ピクセルの最長一致ス トリングを見つけるのにトラバースしなければならない前位ピクセルの数を最小 限にするように設計された所定のパターンで画像ピクセルをトラバースするもの である。 この発明によれば、入力ストリームは、複数の入力データピクセルを含み、そ の内の二つ以上が入力データストリングを構成する。方法は、数段のステップを 含んでなる。入力データストリームが最初に読みとられて、前位データが得られ 、それは前位データストリングを含んでいる。次いで、前位データを所定の非線 形トラバースパターンで探索して、入力目標データストリングと一致する最長一 致前位データストリングを探す。何か最長一致データストリングが見つかったら 、それらを圧縮してコピートークンにエンコードする。一致前位ピクセルを持た ない入力目標ピクセルは、いずれもリテラルトークンとしてエンコードされる。 コピーおよびリテラルのトークンは、次いで、エントロピー符号化され、記憶へ または伝送用に出力される。 より詳しく説明すると、この発明においては、ひとつの目標ピクセルがピクセ ルアレイ中の複数の前位ピクセルと比較されて、前位ピクセルのどれかがその目 標ピクセルと一致するか、調べられる。好ましい実施態様では、一致前位ピクセ ルを見つける時間を最小にし圧縮速度を最適化するように設計された要領で前位 ピクセルをトラバースすべく経験的に予め定められた非線形二次元トラバースパ ターンで前位ピクセルを探索する。その非線形トラバースパターンは、画像全体 を圧縮するプロセス中を通して一定に保たれてもよいし、「境界」条件（例えば 、画像の縁）に適応させてまたは特定の 画像の「学究的」特性すなわち実践的に求めた特性に応じて変わってもよい。 非線形トラバースパターンを用いて、目標ピクセルと一致するひとつの前位ピ クセルが見つかったら、その目標ピクセルに関して非線形トラバースパターン内 の一致前位ピクセルの位置が、一致データストリングの開始点（または、「非線 形ピクセルオフセット」）となる。（この文脈において、「非線形ピクセルオフ セット」なる語は、非線形トラバースパターン内において最初の目標ピクセルと 最初の一致前位ピクセルの間にあるピクセルの数を意味する。）次の目標ピクセ ル、これは前記の最初の目標ピクセル（先頭目標ピクセル）の直後のピクセルで あるが、が次いで選択されて、最初に一致した前位ピクセルの直後の前位ピクセ ルが当該次の目標ピクセルと比較され、それら二つの直後ピクセルが互いに一致 するか判定される。もし一致すれば、このプロセス（処理）は、次の前位ピクセ ルが次の対応目標ピクセルと一致しなくなるまで続けられる。一致する前位ピク セルの数が一致データストリングのためのストリング長を構成し、非線形トラバ ースパターン中の最初の一致前位ピクセル（先頭一致前位ピクセル）の位置が一 致データストリングのための非線形ピクセルオフセットとなる。（この非線形ピ クセルオフセットからおよびピクセルアレイ中の目標ピクセルの位置から、最初 の一致ピクセルの「線形ピクセルオフセット」を生成することができる。この「 線形ピクセルオフセット」なる語は、ピクセルアレイ中の線形順序において目標 ピクセルと最初の一致ピクセルの間にあるピクセルの数を意味する。） ひとたび、第一の一致ストリングが見つかると、所定の非線形トラバースパタ ーンを使ってそのプロセスを続行し、さらに別の一致 前位ピクセルストリングがあれば、それを見つける。より長い一致のものが見つ かれば、以前のより短い一致のものをそれに置き換える。好ましくは、この方法 は、トラバースパターンを経てサーチされる前位ピクセルの数について合理的な 限界を有する。そうすれば、一致する前位ピクセルストリングを見つける探査プ ロセスは、全ての前位ピクセルの初めに到達する前に、停止することができる。 最長一致ストリングは、次いで、「コピートークン」としてエンコードされ、そ れは最長一致ストリングの非線形ピクセルオフセットとそのストリング長を示す データを含んでいる。もし、非線形トラバースパターンで前位ピクセルをトラバ ースするプロセスの間に目標ピクセルに対する一致前位ピクセルが見つからなけ れば、不一致の目標ピクセルは「リテラルトークン」としてエンコードされる。 一致ストリングを見つけるためのサーチプロセスは、画像を構成するピクセルの 終わりまで続けられ、全てのコピートークンと全てのリテラルトークンを位置づ けし、一つのトークンセットを形成する。 そのトークンセットは、さらに大域的にエンコードされ（好ましくは、ハフマ ンデータ圧縮アルゴリズムを使って）、エンコードされた圧縮画像データのスト リームが得られる。このエンコードされた圧縮画像データのストリームは、次い で、伝送されまたは記憶される。伝送された場合は、そのエンコードされた圧縮 画像データのストリームが受信されると、それはデコードアルゴリズムを使って デコードされ、圧縮画像データの復号ストリームが得られる。記憶された場合は 、そのエンコードされた圧縮画像データのストリームが検索されると、それはデ コードアルゴリズム（例えば、ハフマン復号化）を使ってデコードされ、同じく 圧縮画像データの復号ストリームが得られる。両方の場合とも、圧縮画像データ の復号ストリ ームのトークンセットが次いで伸張され、原画像と同一の解凍画像が得られる。 ひとつの実施態様においては、比較されつつあるピクセルが同一のデータを含 む場合のみ、ピクセルは、一致すると見られる。この実施態様では、非線形トラ バースパターンでトラバースされた前位ピクセルのいずれとも目標ピクセルが完 全に一致しなければ、その目標ピクセルはリテラルトークンとしてエンコードさ れ、プロセスはピクセルアレイ中を通して続行され、完全に一致するピクセルの ストリングを見つけようと試みられる。 別の代替実施態様においては、目標ピクセルと前位ピクセルとは、それらが完 全に同一でなくても、前位ピクセルが目標ピクセルの所定許容差内に入れば、「 一致」と見られる。この実施態様では、前位ピクセルが目標ピクセルと比較され て、その前位ピクセルがその目標ピクセルの当該所定許容差内に入れば、その前 位ピクセルは「一致」と見られる。このようにして、類似のしかし同一ではない 色が「一致する」とみなされることができる。一致データストリングを見つける ための検索が開始された後は、最初の目標ピクセルに続く目標ピクセルが最初の 一致前位ピクセルに続く各対応の前位ピクセルと比較され、それぞれについてプ リセット許容差が目標ピクセルに適用される。この実施態様は、高い圧縮比を可 能とするが、「損失のある」圧縮となる。 予め定められた非線形トラバースパターンを採用することにより、この発明は 、従来技術の圧縮法における不利と欠点を克服している。第一に、最長一致デー タストリングが、ずっと早くかつ従来技術の線形トラバース法で必要なよりも少 ないピクセルトラバースでもって見つかるように、非線形トラバースパターンが 経験的に求められ る。したがって、圧縮速度が実質的に向上する。第二に、この発明は、ハッシュ 法で要求される複雑な回路や時間のかかる計算の必要性を取り除く。したがって 、この発明は、ハッシュ法よりもコストが低く、複雑でなく、そして高速である 。 この発明の好ましい実施態様の詳細について、添付の図面および以下の説明に 述べる。ひとたび、この発明の詳細が分かれば、当業者にとって、無数の追加の 改革や変更が自明となるであろう。 図面の簡単な説明 図１は、この発明の圧縮および解凍方法を実施するためのプログラム可能なコ ンピュータシステムのブロック図である。 図２は、この発明の好ましい実施態様の基本的な方法を示す流れ図である。 図３は、この発明に従って最長一致データストリングおよび不一致目標ピクセ ルを見つけてトークン化するためのプロセスを詳細に示す流れ図である。 図４は、この発明の好ましい実施態様の圧縮／解凍の全体プロセスのより詳細 なバージョンを示す流れ図である。 各図において、同じ参照番号および名称は、同じ要素を意味している。 発明の詳細な説明 この説明の全体を通して、示されている好ましい実施態様および実例は、例示 と考えるべきであり、この発明に対する限定と考えて はいけない。 そのうえ、この説明の残りの部分の全体を通して、便宜上、画像データおよび ピクセルについて言及する。しかしながら、この発明は、画像データの圧縮と解 凍に限定されると認識されてはならない。むしろ、この発明は、データ圧縮が採 用される如何なるシステムやデータタイプにも応用できるものである。動作環境の大略 以下の記載は、好ましくは汎用コンピュータまたはプログラム可能な処理シス テムにより読み取り可能な記録媒体または記憶装置（例えば、ＲＯＭや磁気ディ スケット）に記録されたコンピュータプログラムとして実行される手続（手順） であって、記録媒体または記憶装置がコンピュータまたは処理システムにより読 み取られたとき、そのコンピュータまたは処理システムをそれらが下記に説明す る機能を果たすように配置構成および動作させる手続について説明するものであ る。 図１は、この発明の圧縮および解凍システムを実行するために使用できる典型 的なプログラマブル処理システム１０のブロック図を示す。処理システム１０は 、好ましくは、ＣＰＵ１２、ＲＡＭ１４、ＲＯＭ１６（これは、フラッシュＲＯ Ｍのように書き込み可能であってもよい）、Ｉ／Ｏコントローラ１８、および磁 気ディスクなどの採用任意の記憶装置１９を含んでいて、それらが図示のように ＣＰＵバスで接続されている。Ｉ／Ｏバスには、ディスプレイ２０、キーボード ２２および通信ポート２４などの入出力装置並びにＩ／Ｏコントローラ１８が接 続されている。ディスプレイ２０は、圧縮される原画像を表示するのに使用して もよい。プログラマブル処理 システム１０は、予めプログラムされていてもよいし、他のソース（例えば、他 のコンピュータ）からプログラムをダウンロードすることによりプログラム（お よび再プログラム）してもよい。ＣＰＵ１２は、データ値間の同一性または違い を判定するため、およびオプションとして二つのデータ値を第三の値（例えば、 しきい値）と比較するために、比較回路を有しているか、または一つのデータ値 を他のデータ値と比較するようにプログラマブルでなければならない。 プログラマブル処理システム１０は、通信リンク２６を介して遠隔データ処理 システム３０に接続されていてもよい。通信リンク２６を通ってプログラマブル 処理システム１０と第二のプログラマブル処理システム３０の間をデータが通信 されてもよい。図１に示すシステムを使って、原画像を圧縮しエンコードして圧 縮画像を得てもよい。圧縮画像は、次いで通信リンク２６を通して伝送され、そ れを受信して、デコードし解凍して原画像を得てもよい。その代わりに、原画像 を圧縮しエンコードして、例えば記憶装置１９に記憶し、記憶圧縮画像を得ても よい。記憶圧縮画像は、後でＣＰＵ１２で取り出し、デコードおよび解凍して、 原画像を得てもよく、それはまたディスプレイ２０上に表示することができる。 ＣＰＵ１２は、原画像１を圧縮、エンコード、デコードおよび解凍するのに使用 するハードウェアおよびソフトウェアを内蔵していてもよいし、そのようなハー ドウェアおよびソフトウェアは、遠隔コンピュータの中やプログラマブル処理シ ステム１０の別個のモジュールの中に設けてもよい。基本的方法の大略 図２は、この発明の基本的方法の流れ図である。図２に示す方法は、入力デー タストリームを圧縮するために使用されるもので、入カデータストリームは複数 の入力データピクセルを含んでおり、それらの二つ以上からなる一つのグループ が一つの入力データストリームを構成している。（ここで用いられる「ピクセル 」は、カラーデプスや使用されるカラースペースモデルに拘わらず、如何なるデ ータセグメント、データストラクチャ、またはひとつの画像のピクチャエレメン トを定義するビットの集合をも意味し、そして文字データも含む。）この方法は 、開始状態２０２から始まる。入力データストリーム（例えば、データファイル や伝送画像）がコンピュータメモリ内に読み込まれ、初期画像データを得る（ス テップ２０４）。データストリームは、ひとつの画像全体を表してもよいし、ま たはもしメモリ資源より大きければひとつの画像の一部を定義する複数ブロック を表してもよい。この後者の場合、各ブロックは「部分画像」として扱われ、こ の発明に従って別々に圧縮される。しかしながら、この発明は、通常、一つの画 像の複数部分を表す「動く窓」のデータを圧縮して、全体の画像を処理するのに 適用されるであろう。 一般には、圧縮されつつある画像は、原画像の形（例えば、長方形、円、など ）に拘わらず、ピクセルの長方形配列（アレイ）によって一つの画像を記述する データファイルとして表される。それにもかかわらず、六角形など他の配列形態 を有する画像もまた、以下に記載の手続（手順）を使用して圧縮してもよい。し かしながら、ピクセルアレイにより表される画像が何であれ、アレイには始まり と終わりがあって、一番目の「前位」ピクセルはピクセルアレイの初めのところ に位置し、したがって、そのアレイの中の一番目のピ クセルである。この説明の残り部分として、ピクセルアレイ中を通って「前方へ 」移動またはトラバースするという場合は、その移動またはトラバースがピクセ ルアレイの始めから終わりの方向（つまり、一番目の前位ピクセルから離れる方 向）に行われることを意味している。ピクセルアレイ中を通って「後方へ」移動 またはトラバースするという場合は、その移動またはトラバースがピクセルアレ イの終わりから始めの方向（つまり、一番目の前位ピクセルヘ向かう方向）に行 われることを意味している。 再び図２を参照して、各新しい、つまり「目標」ピクセルが読み取られると、 予め定められた所定の非線形の（二次元に）トラバースパターンで前位（＝「目 標」より前に位置する）ピクセルデータをサーチ（探索）して、前位データ内の 最長一致ストリングを探す。これにより、各最長一致前位データストリングは、 入力データストリームからのデータストリングと一致する前位データストリング を構成するものである。 好ましくは、その所定の非線形トラバースパターンは、単一の画像に対しては ひとつの固定した長さを有する。すなわち、各目標ピクセルに対して、所定の非 線形トラバースパターンは、トラバースすべき固定数の前位ピクセルを有し、そ して、各画像に対して、サーチされる前位ピクセルの所定数のところでトラバー スパターンが停止する。 替わりに、単一の画像内でトラバースパターンの長さを変化させることにより 、もっと有利にすることもできる。随意であるが、単一の画像に対してフルに変 化する（つまり、最適の）パターンを計算することもできる。すなわち、トラバ ースパターンは、画像ごとに変わってもよい。 非線形トラバースパターンの範囲とパスは、圧縮されるデータの構成形態によ り限定してもよい。例えば、圧縮する画像が境界または限界を有するピクセル配 列でできていて、トラバースパターンがピクセル配列の限界の外側になるセグメ ントを含んでいてもよい。その場合、ピクセル配列の限界の外側になるセグメン トは、例えば、配列の縁のところで動的に（ダイナミックに）取り除くことがで きる。取り除かれたセグメントは、最長一致データストリングを構成するベクト ルの中に再度登場しない。つまり、取り除かれたセグメントは、トラバースパタ ーン中にそれまで存在しなかったかのように扱われる。そのようなセグメントは 、最長一致ピクセルストリングを見つけるのに有用でないので、これにより高速 化が図れる。 上記に言及したように、予め定めておく非線形トラバースパターンは、経験的 に求めてもよい。最適のトラバースパターンを経験的に求めるには、目標ピクセ ルと一致する前位ピクセルを探して多数のテスト画像を徹底的にスキャンする。 そして、ヒストグラムを計算して、前位ピクセルの位置に一致する頻度を出す。 このヒストグラムを次いで降順にソートして、ソートされた一致頻度に対応する 相対的ピクセルオフセットが、好ましい非線形トラバースパターンになる。 ここで具体例で示すように、好ましいトラバースパターンは、上記の方法で決 定される。ピクセルオフセットは、目標ピクセルとの一致をサーチしている前位 ピクセルの、目標ピクセルに対する二次元配列における相対的位置として定義さ れる。経験的に求めた好ましいトラバースパターンでは、最初の２４個の相対的 ピクセルオフセットが、次の順序で（省略時に）スキャンされる。 上記表において、「＃」記号は、目標ピクセル、すなわちそれに対する一致前位 ピクセルをサーチしているエンコード中の位置を表す。１〜２４の数は、トラバ ースパターンにおける初めの２４個の相対的ピクセルオフセットをその順で表す 。 上記の表では、オフセット１〜５は、ピクセルをトークンにエンコードする際 に、僅かに優先的な取扱いを受ける。（トークンのスキーマは以下で詳細に説明 する。）好ましい実施態様では、オフセット１〜５は、追加のトークンフラグビ ットを添えないで、独特のトークンが割り当てられている。追加のトークンフラ グビットは、非優先的トークンに添えられるものである。このため、画像がトー クンとしてエンコードされた後は、上記の２４個の相対オフセットの内の最も頻 繁に起こる５つを同定し、最も頻繁に起こるオフセットに最適トークン位置１〜 ５が割り当てられるように、初めの２４個のオフセットの全部を丁度よいように 置換する。この置換は、デコード処理の間は、逆転され、他のエンコード／デコ ード処理部分に対しては何も影響しない。このことは、以下で詳細に説明する。 最も頻繁に起こるオフセットに僅かに優先的な扱いをする目的は、ビットパック 効率を上げるためである。初めの２４個のオフセットからの最も頻度の高い５つ のオフセットは、「最頻（most popular）」オフセットと呼ばれる。 この好ましい実施態様では、初めの２４個の相対オフセットをスキャンした後 は、次の４１個のオフセットを下記の順序でスキャンする： 前記の第一の表と同様に、「＃」記号は一致前位ピクセルを探している目標ピク セルを表す。 この好ましい実施態様においては、非線形トラバースパターンの中の位置（ロ ケーション）の数は、サーチの深さ（それで、より長い一致が得られるかも知れ ない）と圧縮のスピードとのバランスを取るためある合理的な数に制限される。 小さいコラム幅（縁から縁まで）を有する画像に対しては、上記のオフセット のいくつかは、最初のコラムから最後のコラムへと、または最後のコラムから最 初のコラムへと「巻き付くこと（wrapping around）」により、冗長性を生じる であろう。ここに実現しているように、そのような巻き付きは許容される。巻き 付きは、圧縮スキームの実行を簡単にする。それは、圧縮率の向上にもつながる 。というのは、画像の境界で起こる色は、しばしば関連しているからである。 残りの相対オフセットは、前のスキャン段階からすでに考慮された如何なるオ フセットをも考慮しないで、目標ピクセルの位置から 後ろ向きに線形パターンでスキャンされる。例えば、（１６コラムの画像を想定 する）、スキャンは下記のように続けられる。 再び図２を参照し、特にステップ２０８を参照して、もし、最長一致前位デー タストリングが見つかったら、対応の一致目標データストリングは、それを「コ ピートークン」でエンコードする（置き換える）ことにより圧縮される（ステッ プ２１０）。もし、最長の一致前位データストリングが見つからなかったら、入 力データストリームからの各不一致ピクセルは、「リテラルトークン」としてエ ンコードされる（ステップ２１２）。好ましくは、エンコードプロセスは、最長 一致前位データストリングおよび不一致ピクセルに出会うと、実行される。した がって、エンコードは、階段的な要領で生じる。つまり、この方法は、画像の全 体がスキャンされた後で、見つかった最長一致前位データストリングおよび不一 致ピクセルの全部がエンコードされなくてもよいような具合に実行してもよい。 しかしながら、エンコードステップを、画像全体がスキャンされて不一致ピクセ ルおよび最長一致前位ピクセルストリングの全部が見つけられた後に、行うよう にすることも、随意可能である。 エンコード後、コピートークンとリテラルトークンが出力され、 全ピクセルがエンコードされてしまうまでこのプロセスが繰り返され（ステップ ２１４）て、そこでこの基本プロセスは終了する（ステップ２１６）。コピート ークンとリテラルトークンは、次いで、通信リンク（図１に示したように）を通 って他のデータ処理システム３０へ伝送されてもよい。図２の方法を使って入力 データストリーム（または、画像）が圧縮されているので、より少ないビットが 通信リンク２６を通ってデータ処理システム３０へ伝送されればよい。替わりに 、圧縮されたデータは、記憶装置１９に記憶されることもでき、データまたは画 像が圧縮されていなければ必要であろうよりも、少ない記憶空間で済む。サーチアルゴリズム 図３は、図２のステップ２０４〜２１４をより詳しく図解して、画像を圧縮す る好ましい方法を示す。図４の最初のステップは、処理すべき「次の」目標ピク セルを選択するためのものである（ステップ３０２）。（この「次の」目標ピク セルは、処理すべき最初のピクセルのこともある。）ひとたび、目標ピクセルが 選択されると、複数の前位ピクセル（すなわち、ピクセルアレイの中で先頭目標 ピクセルに比べて前の位置にある複数のピクセル）が所定の非線形トラバースパ ターンでトラバースされる（ステップ３０４）。 前位ピクセルをトラバースするプロセスにおいて、目標ピクセルはトラバース パターンで出くわす各前位ピクセルと比較され、それら前位ピクセルのいずれか が目標ピクセルと一致するか判定される（ステップ３０８）。一致が見つからな ければ（ステップ３０８）、非線形パターンが全部終わったかが見られる（ステ ップ３１８）。終わってなければ、プロセスはステップ３０６で続行される。 もし、一致が見つかれば（ステップ３０８）、先頭の一致前位ピクセルにして 、一致がさらに延びるか見られる。そのやり方で、先頭目標ピクセルに続く目標 ピクセルと先頭前位ピクセルに続く前位ピクセルとが、前方への線形パターンで トラバースされ、先頭一致を延ばそうと試みられる（ステップ３１０）。このよ うにして、線形トラバースパターンがピクセルアレイの終わりへ向けて移動して いく。 さらに詳しくいうと、ひとたび先頭の一致前位ピクセルが見つかると、先頭の 一致目標ピクセルに続く各目標ピクセルは、対応する次の前位ピクセルを有する 。したがって、目標ピクセルのストリングが前位ピクセルのストリングと一致す るかをひとつひとつ判定するために、先頭の目標ピクセルに続く各目標ピクセル がそれに対応する前位ピクセルと比較される（ステップ３１２）。もし、比較中 の対応する目標ピクセルと前位ひくとが互いに一致していると分かれば、ステッ プ３１０が繰り返されて、次の対応する目標ピクセルと前位ピクセルとが互いに 一致するか判定される。このプロセスは、一致が見つからなくなるまで続き（ス テップ３１２）、前位ピクセルの現一致ストリングの終点を指示する。 ひとたび、一致前位ピクセルストリングの終わりに到達すると、現在の一致ス トリングの長さが現在処理中の先頭目標ピクセルについて前にセーブされている ストリング長のいずれとも比較される（ステップ３１４）。現在のストリングが 最初に見つかったものであるか、または現在のストリングが前にセーブされたス トリングより長ければ、現在の一致ストリングの相対オフセットおよびストリン グ長が「現在の」最長一致を表し、記憶される（ステップ３１６）。（好ましく は、概要の部分で定義したように、非線形ピクセルオフ セットが記憶され、それから目標ピクセルの位置とともに線形ピクセルオフセッ トを生成することができる。しかしながら、線形ピクセルオフセットを替わりに 記憶することができることも、認識されたい。）そうでなければ、現在の一致を 捨てて、プロセスはステップ３１８で続行する。替わりに、オフセットおよび長 さの情報が直ちにコピートークンで置き換えられる（下記参照）。 圧縮を最適にするためには、一致データのストリングのみでなく、一致データ の最長ストリング（ある限定したサーチ空間内で）を見つけてエンコードするの が、非常に好ましい。最長の一致ストリングをサーチして見つけることにより、 単に最初の一致ストリングを見つけてその点でプロセスを中止する場合よりも、 大きな圧縮が達成され得る。このようにして、次のステップは、前に見つけた一 致前位ピクセルストリングがひとつでもあるか、そしてそれは現在の最長一致よ りも長いかを判定するものである。したがって、もし非線形トラバースパターン が全部終わっていなければ（ステップ３１８）、画像パターンが終わるまでステ ップ３０６でプロセスが繰り返される。上に説明したように、好ましくは、非線 形トラバースは所定の終了点を有し、各前位ピクセルの全部がトラバースされる ことはない。もし、全ての前位ピクセルがトラバースされたら（すなわち、最初 の前位ピクセルに到達したときのみ非線形トラバースが終了する）、この発明に より達成される圧縮スピードの向上は減殺される。したがって、この発明の非線 形トラバースパターンを制定するには、圧縮スピードのみならずビット低減の量 をも最適化するためにどれだけの前位ピクセルをトラバースすべきかを決定する 。これは、非線形トラバースパターンの長さを、前位ピクセルをさらに後ろ向き にトラバースすることによりもっと長い一致ストリング を見つける可能性と、相互に関係させて決定する。圧縮が最適化される点は、上 に説明したように、経験的に求めてもよい。 トラバースパターンの続きは、一番最近の一致ストリングの先頭の一致前位ピ クセルの、トラバースパターンに従っての直前の前位ピクセルから始める。この ように、非線形トラバースが続けられるので、次のトラバースされる前位ピクセ ルは、必ずしも、そのような先頭の一致前位ピクセルの、ピクセルアレイ中での 直前の前位ピクセルでなくてもよい。むしろ、トラバースパターンが非線形であ るので、先頭の目標ピクセルと比較される次の前位ピクセルは、ピクセルアレイ の中で先頭の一致前位ピクセルからずっと離れた位置にあってもよい。（好まし い非線形トラバースパターンについては、トラバースパターンを構成する経験的 に求めた「ピクセルオフセット」を示す上記の図を参照されたい。）次いで、プ ロセスは、前位ピクセルの別の一致ストリングを見つけようとして、そしてその ようなストリングが最長の一致ストリングであるかを判定しようとして、続行す る。 もし、非線形トラバースパターンが全部終わったら（ステップ３１８）、その 先頭の目標ピクセルに対して一致が見つからなかったか、最長のストリングが見 つかったかの、いずれかである。前者の場合は、目標ピクセルがリテラルトーク ンで置き換えられ、後者の場合は、一致目標ストリングがコピートークンで置き 換えられる（ステップ３２０）。そのトークンは、次いで出力される。 次に、画像が全部処理されたかを見る（ステップ３２２）。そうであれば、プ ロセスは終了する（ステップ３２４）。そうでなければ、次の目標ピクセルが処 理のために選択される（ステップ３０４）。次の先頭目標ピクセルは、一致前位 ピクセルをサーチした最後の目 標ピクセルの直後の位置に位置決めされる。もし、非線形パターンで前位ピクセ ルをトラバースするプロセスの間に、先頭目標ピクセルと一致する前位ピクセル が見つからなかった場合は、次の先頭目標ピクセルは、一致が見つからなかった 前の先頭目標ピクセルの直後の目標ピクセルである。しかしながら、もし、前位 ピクセルの一致ストリングが見つかった場合は、次の先頭目標ピクセルは、一致 目標ピクセルのストリングの中の最後の目標ピクセルの直後の目標ピクセルであ る。プロセスは、次いでステップ３０６へ進、現在の目標ピクセルに対して（す なわち、「移動窓（moving window）」）の複数の前位ピクセルが、所定の非線 形トラバースパターンで再びトラバースされ、今回は次の先頭目標ピクセルに一 致する先頭の一致前位ピクセルをサーチする。「一致」の定義 この発明の方法は、ロスのある比較にも、ロスのない比較にも使えるものであ る。ロスのない比較のためには、二つのピクセルは、両者が同一である場合のみ 、「一致する」とみなされる。ロスのある比較では、二つのピクセルは、両者が 同一でなくても、それらが予め定めた許容差の範囲に入っていれば、「一致する 」とみなされる（これは、予めプログラムされていてもよいし、いろいろな程度 の圧縮が可能なように、ユーザ定義可能でもよい）。このようにして、目標ピク セルと前位ピクセルの間の比較の程度を予め定めた許容差によって変えることも できる。もし、目標ピクセルが前位ピクセルの許容差範囲内にあれば、その目標 ピクセルと前位ピクセルは一致するとみなされ、一致する前位ピクセルストリン グを見つけるための目標ピクセルと前位ピクセルの一致を見るプロセスは、許容 差内の最長ストリングが前位ピクセルの中に見つかるまで、続行する。 許容差（ロスのある）一致の正確度または有効度を向上させるために、いくつ かの変形や特徴を採用することができる。第一に、ロスの程度をコントロールす るために、可変許容差を使用することができる。この許容差は、画像ごとに、ま たは単一の画像の中で可変とすることができる。第二に、この方法は、許容差内 の一致をサーチしているとき許容差外のミスが生じたら、そのストリング内の追 加の後続ピクセルが許容差内にあるかを決めるために、サーチ中のストリングに ついて一致プロセスを続けられるように改変することができる。そうすれば、「 許容差外」ミスを「一致」とみなすことができる。第三に、このスキームの変形 は、ストリング比較における平均ヒット品質を指示する二次許容差を設けること である。第四に、一致ストリングを通しての合計誤差を監視していて、「誤差」 があるしきい値を超えたら一致プロセスを停止することができる（「誤差」とは 、前位ピクセルと目標ピクセルとの差を意味する）。これは、小さな誤差（依然 、許容差内にある）が、例えば背景色におけるような多数のピクセルにわたって 繰り返された結果生じる「ストリーキング」を最小にするのに使用することがで きる。 一致する前位ピクセルストリングを見つけるのに許容差比較を採用する場合は 、スキャン（サーチ）中の前位ピクセルは、再構成されたバージョンであり、現 ソース画像ピクセルではない。これは、圧縮中の画像を再構成するときに、デコ ーダに供給されるのと同じピクセルに対してスキャンニングプロセスが実行され なければならないからであり、さもなくば、許容差比較は不正確なものとなる。 そのうえ、許容差比較が採用された場合は、再構成ピクセルバージ ョンを作り出すステップを追加することができ、そこで、一致目標ピクセルを一 致前位ピクセル（すでに再構成された画像からの）で置き換える。この一致プロ セスは、潜在的に非同一の一致を作るので、一致前位ピクセルは、置き換えてい る目標ピクセルとは異なるかも知れない。トークン化 不一致の目標ピクセルについては、その目標ピクセルの原ピクセル値がリテラ ルトークンとしてトークン化される。デコーダまたはデコードステップ（以下に 説明）は、そのようなリテラルトークンに応答して、この単一のピクセル値を再 構成画像の中に挿入する。このリテラルピクセルは、その原ピクセルと正確には 一致しないかも知れないが、ピクセルを後で変更（許容差内で）して後続の一致 を改良する（例えば、長くするとか合計誤差を減らす）のに便利である。 より詳しくいえば、以下のテーブルは、トークンセットを記述するものであり 、好ましい実施態様においてリテラル要素およびコピー要素がマップされている （ここに、「ＭＬ」は「最小長」コピーストリングを表し、それは画像ごとに異 なり、２〜１７の間の任意の値に設定できる。）。 好ましいトークン化スキームでは、いくつかの他の考慮がなされる。第一に、 ２５５より大きいトークンは、コピーストリング（コピー要素）である。２５５ 以下のトークンは、トークンが表すリテラルピクセル値に直接マップされる。第 二に、コピー要素は、１６のブロックにグループ分けして、トークンビットの７ から４まででブロックを指定してもよい。各ブロック内で、ピクセルオフセット の意味は同一であり、下位の４トークンビットは、オフセットおよび／またはオ フセットをさらに定義するためにトークンに続く追加ビットの数を定義する。第 三に、各コピーブロックについてのトークンビット７から４までは、コピースト リングの長さおよび／またはその長さをさらに定義するためにトークンに続く追 加ビットの数を決定する。第四に、トークン４１６〜４３１（これらは延長され た長さを有するコピートークンを表す）については、二つのビットが追加長ビッ トに先行して、追加長ビットが何ビット後に続いているかを示している。方法の詳細バージョン 画像の処理 図４は、この発明の好ましい実施態様の圧縮／解凍プロセスの全体のより詳細 なバージョンを図解するものであり、図２に図解した方法を適用している。画像 データを圧縮する前に、画像データのカラースペースを公知の要領で変更しても よく、それは採用任意である（ステップ４０２）。好ましい実施態様では、画像 データをエンコードするカラースペースは、在来のＹＣｒＣｂである。ソース画 像（または原画像）が好ましくないカラースペース（例えば、ＲＧＢ）にあれば 、画像は、まず好ましいカラースペース（すなわち、 ＹＣｒＣｂ）に変換されればよい。（International Radio Consultative Commi ttee「ＣＣＩＲ」Recommendation 601を参照。）しかしながら、そのようなカラ ースペース変換は、典型的にロスレスではない。したがって、デコードされた画 像がソース（原）画像と正確に一致することがクリティカルでない場合のみ、ロ スレス変換を行ってもよい。 圧縮される画像は、画像データの値の範囲を減らすために、公知のやり方で副 標本化する（部分画像ごとに標本化する）ことも採用任意である（ステップ４０ ６）。副標本化（subsampling）を行うと、画像内の各色は、カラースペースを 変更した後、最初に公知のやり方で任意にフィルタを適用してもよい（ステップ ４０４）。好ましいフィルタは、１、２、１の３要素カーネルを使用する。二次 元画像に対しては、このフィルタを画像の両方の次元に沿って適用する。たとえ 、カラースペースが変更されなくても（ステップ４０２）、副標本化する（ステ ップ４０６）前に画像を任意にフィルタして（ステップ４０４）もよい。 この好ましい実施態様では、画像データは、一つ以上の動的に選択されるＤＰ ＣＭ（差分ＰＣＭ）アルゴリズムを用いて予めフィルタされる。連続したトーン の２４ビット画像に対しては、大部分のピクセル値が一組の小さいデルタに変形 されるので、そのようなフィルタリングは典型的に一致ストリングの数を増加さ せ、画像の圧縮後のサイズを小さくする。デルタをデコードするときは、逆ＤＰ ＣＭアルゴリズムが適用され（ステップ４２６）、それはエンコード／デコード のプロセスに何もロスを増やさない。 好ましくは、この発明では、以下の三つのＤＰＣＭアルゴリズムが使用される が、異なるＤＰＣＭを採用することも任意である。 （１）Ｘ＝Ｘ−Ｂ； （２）Ｘ＝Ｘ−Ｃ；または （３）Ｘ＝Ｘ−（（Ｂ＋Ｃ＋１）／２）、 ここに、Ｂ、ＣおよびＸは、下記のとおりである。 行（ｎ−２） ． ． ． ． 行（ｎ−１） ． Ｂ ． ． 行（ｎ） Ｃ Ｘ ． ． Ｘは目標ピクセルを表し、Ｂはピクセルアレイ内でＸのすぐ上の前位ピクセル であり、そしてＣはピクセルアレイ内でＸの直前の（または左の）前位ピクセル である。好ましい実施態様において、最初の画像列（コラム）に対してＤＰＣＭ アルゴリズム（１）が常に使用され、そして最初の画像行に対してＤＰＣＭアル ゴリズム（２）が常に使用される。画像内の最初のピクセルに対しては、この好 ましい実施態様ではＤＰＣＭが使用されない。 サーチおよびトークン化 次に、図２および図３に記述された基本的なアルゴリズムを使用して、所定の 非線形トラバースパターンで画像をピクセルごとにトラバースすることにより、 画像が圧縮される（ステップ４０８）。ここで、各目標ピクセルが、所定の非線 形トラバースパターンで出会う前位ピクセルと一致するか試される。さらに、目 標ピクセルの現在のストリングと一致する前位ピクセルの最長ストリングを見つ けるために、それぞれの一致を延ばすことが試される。 好ましい実施態様では、パレット化（８ビット）データまたは２４ビットデー タのいずれかを圧縮することができる。２４ビットの場合は、データは圧縮され て要素ごとに分けられて、あたかも２４ ビットデータがパレットのない三つの８ビット画像であるかのようにしてもよい 。もしくは、２４ビットの場合、データはインタリーブされた要素であってもよ く、あたかもその画像が３倍の数の列を持つ単一の要素であるかのようにしても よい。 上述したように、圧縮されたデータは、要素の列（シーケンス）からなってお り、各要素は、リテラルピクセル（例えば、非圧縮のソース画像からの転送同一 物）か「コピー」呼出しかの、いずれかを表している。コピー呼出しは、前にエ ンコードされている画像の中を指すデータ対［オフセット，長さ］であり、デコ ードされたとき、データ対の現在の位置にコピーされるべき一致前位ピクセルの ストリングを同定するものである。例えば、ピクセルストリングは、以下のよう であってもよい（下記の各桁はピクセルを表すと仮定する）。 ４３２１０２１０３２１０９８７９８７１１１１１ ロスなし圧縮を仮定して、上記のピクセルストリングは、下記の要素リストと してエンコードされてもよいかも知れない（ここに、「．」はリテラル要素が後 にくることを示し、「［］」（すなわち、［オフセット，長さ］）はコピー要素 （またはコピー呼出し）が後にくることを示す）。 ．４．３．２．１．０［３，３］［７，４］．９．８．７［３，３］ ．１［１，４］ 上記は、ロスなし圧縮の一例であるが、この発明はロスあり圧縮にも同じく使 用できると理解すべきである。上述のように、ロスあり圧縮の場合、圧縮されつ つある画像について、一致ストリングは、不正確であっても視覚的に近似してい るというので構わない。デコーダは、エンコーダが一致ストリングをロスありで 持っているかロ スなしで持っているかに関心がないので、この「ロスあり」は、デコーダの動作 に影響を与えない。 リテラル要素およびコピー要素は、上述のように、定義されたトークンのセッ ト（一組）に再マップされる。さらなる圧縮を達成するために、この好ましい実 施態様では、これらのトークンをヒストグラム化し、ハフマンコード化する。得 られるコードワードは、出力データストリームの大部分を作る。追加の非ハフマ ン化ビットがハフマンコードワードの間に置かれてもよい。これらの追加ビット は、必要な全ての情報を運ぶのにハフマンコードワードが不十分であるときに、 間に挟まれる。例えば、非常に大きいコピー長のコピー要素または非常に大きい オフセットのコピー要素は、より大きい値の上位ビットを記述するために、トー クンの後に続く追加のビットをしばしば必要とするであろう。これらの追加ビッ トが存在することは、これらのビットに先行するトークンの定義から知ることが できる。 ハフマンエンコード したがって、画像がトークン化された（ステップ４０８）後、得られたデータ ストリームは好ましくはハフマンコードを使用してエンコードされる（ステップ ４１０）。好ましくは、古典的なハフマンアルゴリズムを使用して、そのトーク ンのセットに対する最適なハフマンツリーを作り出す。ハフマンコードは、圧縮 画像を含むファイルの初めのところに、それ自体、圧縮フォーマットにエンコー ドされる。好ましくは、このステップの出力は、長さが１〜１６ビットのハフマ ンコードワードからなる圧縮ハフマンストリームであり、随意、追加のコードワ ード依存のデータを散在させてある。 この好ましい実施態様では、ハフマンツリーは、以下の要領でエンコードされ る。ハフマンツリーは、可能なトークンの全てに位置的に対応する４３２の整数 のベクトルで表され、各整数は０から１６の値を持つ。これらは、「トークン長 」と呼ばれる。トークン長ベクトルは、ハフマンツリーの形を完全にエンコード しており、どトークンがそのリーフに対応するかを示している。０から１６のト ークン長の値は、トークンの二進コードワード長をビット数で表している。コー ドワードの割当てにおいて、短いコードワードは、長いコードワードの等価長プ レフィックスより数値的に小さいと推定される（すなわち、長いコードは、１の ビットでプレフィックスされる傾向にあり、ツリーは右方向に深い）。 トークン長ベクトルは、まず、処理中の画像についてのエンコードパラメータ によって、０を持つと分かっている位置のいずれをも除くことにより、長さを減 じられる。例えば、もし、最大オフセット（ユーザ調整可能なエンコードパラメ ータ）が６５以下であれば、６５より大きいオフセットを表すトークン位置の全 てが取り除かれて、ベクトルを縮める。 次いで、トークン長ベクトルは、この好ましい実施態様においてそれ自身トー クン化されビットパックされる。下記のトークンが、 トークン長の圧縮に使用するために定義される（ここで、以下のテキストは、あ たかもトークンがデコードされつつあるとして解釈される）。 ＊ 前を一度繰り返す（「Ｒ１」）：前にデコードした値をもう一度出力する ＊ デルタ１：前にデコードした０でない値に＋／−１を加算して（範囲を１か ら１６に維持するためにモジュロ１６の演算を使用する）、それをもう一度出力 する。パックされたトークンに続いてデルタの符号を示す一つのビットがあり、 ０：正の修正 １：負の修正。 ＊ デルタ２：値を２とすることを除き、デルタ１と同じ。 ＊ デルタ３：値を３とすることを除き、デルタ１と同じ。 ＊ デルタ４：値を４とすることを除き、デルタ１と同じ。 ＊ デルタ５〜８：より大きいデルタコーディング。デルタトークンの直後に追 加の２ビットを続け、デルタの大きさを示す。これらの２ビットに続いて小さい デルタの場合のように符号ビットがある。［注：デルタ＋８は違法で、回避。デ ルタ演算はモジュロ１６で行うので、デルタ＋８はデルタ−８と等価である。両 方の場合にデルタ−８を使用しなければならない。］ ＊ 前を三度繰り返す（「Ｒ３」）：前にデコードした値を三度出力する（「二 度繰り返す」は、一対の「一度繰り返す」によりコードする） 前を三度繰り返すのトークン（「repeat threeトークン」）は、もしそれが一 つ以上の一度繰り返すのトークンに先行されていると、追加の意味を持つ。三度 繰り返すのトークンの直前にある連続した 一度繰り返すのトークンのそれぞれについて、追加のビット（最大８まで）が三 度繰り返すのトークンに後続し、以下のようにより長い繰り返しを示す（ここで 、Ｒ１［ｎ］は一度繰り返す（repeat-once）のトークンがｎ回連続することを 表す）。 説明として、全ての長さの「前を繰り返す」は以下に挙げるようにコードされ る［注：（１）先頭のＲｘはその前にＲ１がないものとする。そのような値を持 つ理由がないから。（２）ｘ＞３のＲｘは、前の行からの、より大きい複合繰り 返しの呼出しである。］。ハードの０：一つの０（不使用のトークン位置を示す）を出力する。これは、「 前にデコードされた値」のフィールドを変更しない。（「前にデコードされた値 」の定義に関しては、以下の説明を参照。） 多数のハードの０：二つ以上のハードの０を出力する。出力すべきハードの０の カウントは、トークンの直後に続く延長ビットにより決まる。 （ｎ［ｘ］は、ｘ回のｎ） （許される最長の延長は１６ビットである。） 前にデコードされた値 これは、出力された最後の０でない値（１〜１６）を反映する値である。（言 い換えれば、「ハードの０」のトークンは、このフィールドを更新させない。） スタートアップにおいて、このフィールドは８であると定義される。エンコード ／デコードが進行するにつ れて、デルタが計算され、それから及びそれに適用される。パックされた出力ビ ットストリームは、以下のようにフォーマットされている。 ビット ０…Ｎ： パックされたデルタコードトークン長（下記） ｎ＋１…： エンコードされたトークン長のビットストリームパックされたデルタコードトークン長 入力トークン長をモデル化するのに使用されるトークンについてのハフマンツ リーは、それ自体記述されていなければならない。これは、ストリームのビット ０〜ｎにおいてなされる。下記の静的ハフマンコードは、０から８までの値をエ ンコードするのに使用される。 この値は、次いで、次のように初期化されるルックアップテーブルの指標付け に使用される：（１，２，３，４，５，６，７，８，０）。これは、潜在的な「 ｄｃトークン長」（これは、主トークン長と区別するために、ｄｃトークン長と 呼ばれる）を表し、０で不使用コードを指定する。エンコード／デコードが進行 していくにつれて、ツリーレベルが全部達したためにもはや可能でなくなったｄ ｃトークン長は、ルックアップテーブルから除かれる。 もし、残っているゼロのｄｃトークン長があっても、それらは記憶されない。 むしろ、デコーダがそれらを自動的に検知する。なぜなら、ハフマンツリーはゼ ロが始まる点で正確に満たされるからで ある。また、最後のｄｃトークン長の位置は決して記憶されず、デコーダはハフ マンツリーを調べてそれが何でなければならないかを常に決定することができる 。 ブロック分け 再び図４を参照して、エンコードされた画像は、圧縮されエンコードされた画 像の記憶または伝送前に、随意、複数ブロックに区分けしてもよい（ステップ４ １２）。ステップ４１２では、ハフマンエンコードされたコピーおよびリテラル トークンに、ある構造体が課せられる。この構造体は、トークンファイルを行の ブロック（例えば、１６ブロック）に区分けし、デコーダに画像が到着したとき に、デコーダが画像の部分的な区域を表示または「ペイント」できるようにする 。（好ましいファイルフォーマットについて、下記を参照。） 画像のスプラッシュおよびプリスプラッシュ 圧縮されエンコードされた画像を伝送または記憶する前に、画像の「スプラッ シュ」バージョンをデータストリームの初めに、随意、前置してもよい（ステッ プ４１４）。スプラッシュ画像は、原画像を極度に小さく（サイズを）したバー ジョンであり、それはデシメーション（間引き）／フィルタリング（ろ波）によ って減じられている。スプラッシュ画像は、データストリーム中のスプラッシュ 画像に続く主画像と同じ圧縮スキームを使用してエンコードされる。スプラッシ ュ画像が受信されると、それはデコードされ、拡大されて、例えばスクリーン表 示窓の中に描画される。これは、画像が到達する前に、主画像の近似レンダリン グでもって画像のビューアを 提供する。主画像は、スプラッシュ画像の後に複数区分（上記のように、行のブ ロック）で到達し、スプラッシュ画像をオーバレイする。 スプラッシュ画像は、好ましくは、主画像をデコードするのには使用されない 。このことは、主画像をデコードする性能に影響せずに、スプラッシュ画像がデ ータファイルから取り除かれるのを可能にする。しかしながら、主画像をデコー ドするのにスプラッシュ画像が使用されてもよいことを、認識されたい。そのう え、例えば主画像データをスプラッシュ画像に対して差分ＰＣＭするなど、スプ ラッシュ画像の情報を使用することにより、主エンコード画像のサイズを減じる のにスプラッシュ画像を使用してもよい。 随意に、「プリスプラッシュ」コードを利用してもよい。プリスプラッシュコ ードは、スプラッシュ画像の中で最も「ポピュラーな」または優勢な色を表す。 スプラッシュコードは、スプラッシュ画像を枠決めするのにスプラッシュ画像が 表示されるエリアのための背景色として使用することができる。 さらに、パレット（８ビットのソース）を有する画像のために、伝送または記 憶中のファイルに「透明」色を設ける別の表示方式も随意である。デコードする ときは、呼出しアプリケーションで透明置換色を特定することができる。この色 は、ファイル透明色の先頭にあるパレットの中に入れられ、透明エリアを置換色 で効果的に塗り込む。 記憶または伝送 圧縮されてエンコードされた主画像が区分され（ステップ４１２）ていようと 、および／または主画像の前にスプラッシュ画像が前置 され（ステップ４１４）ていようと、圧縮されてエンコードされた主画像（すな わち、トークンのセット）は、伝送されまたは記憶される。（ステップ４１６） 。その画像は、図１のシステム１０からシステム３０へのように、ひとつのコン ピュータシステムから別のへ伝送されてもよいし、または、画像は、図１の記憶 装置１９のようなメモリデバイスの中に記憶されてもよい。いずれの場合も、画 像を圧縮することにより、利点が得られる。伝送される場合は、圧縮画像は、圧 縮されていない場合よりも速く受け側に到達し、より少ないバンド幅を使用する 。記憶される場合は、圧縮画像は、非圧縮画像よりも、メモリデバイス内でより 小さい空間を占有する。 デコード 伝送されてきた圧縮画像が受信され、または記憶された圧縮画像が再生される と、それは、好ましくは、公知の要領でエンコードプロセスを逆算するハフマン デコードアルゴリズムを使用して、デコーダでデコードされる（ステップ４１８ ）。画像は、次いで、同じく公知の要領で、解凍（または、伸張）されて、原画 像の表現を得る（ステップ４２０）。（例えば、米国特許第５、０１６、００９ 号およびそこに引用されている文献に記載の解凍についての説明を参照されたい 。）この点で画像を解凍することにより、図４のステップ４０８の圧縮段階に入 力されたとおりに画像を復元する。 従来の解凍においては、リテラルトークンは単純に直接ピクセルとして出力さ れ、コピートークンのオフセットおよび長さ情報で参照される解凍された前位ピ クセルストリングが、出力にコピーされる。しかしながら、コピーの代わりに補 間が用いられてもよい。好ましい補間方法は、両次元への簡単な線形補間を含み 、各色成分は 他と独立に補間される。例えば、二つの値、0x10および0x40の間を３倍に補間す ると、0x10[0x20][0x30]0x40となり、ここにブラケット内の値は補間で作られた 値である。画像の縁では、補間するための対の値が存在せず、単一の値がそのま ま写される。 解凍において、圧縮画像を定義するトークンは、ピクセル成分値に変換される 。次に、トークンが２４ビットであれば、トークンは他の色成分とインタリーブ されて、出力色を形成する。他方、トークンが８ビットであれば、画像パレット がインデックスされて、２４ビットの出力色を形成する。好ましくは、デコード （ステップ４１８）および解凍（ステップ４２０）は、同時に実行され、設計を 簡単にし、メモリの要求を減じ、時間効率を向上させる。しかしながら、デコー ドと解凍とは論理的には別であるので、異なる時点で実行する独立のステップと して組み入れることもできる。 任意に、デコードされ解凍された画像は、画像を強調するためにフィルタして もよい（ステップ４２２）。好ましい実施態様では、強調フィルタを解凍ステッ プから得られた画像成分値に適用して、解凍された行および列が出力（視聴）寸 法に拡大する前に使用される。あるいは、フィルタは、解凍されたピクセル成分 値に適用されてもよい。例えば、フィルタは、値によってイネーブルされるよう にして、例えばＹ成分のみまたはＸ成分のみを強調するようにすることもできる 。好ましいＦＩＲフィルタは、係数0.0625、-0.3125、1.5、-0.3125、0.0625を 有する７タップのものである。これは、この発明の譲受人に譲渡されている米国 特許出願第２７５、９４５号に開示されているフィルタを近似的に実現したもの である。ただ、デシメーションの間に用いられる改変フィルタに対応するように 変 更し、かつ係数をの数を減らした。この変更は、フィルタを適用するコストを低 減するために、フィルタの正確度が僅かながら低下するという犠牲のうえで、し たものである。 もし、原画像がステップ４０６で副標本化されていれば、デコードされ伸張さ れた画像は、公知のやり方で次いで再補間される（ステップ４２４）。再補間ス テップは、好ましくは、必要に応じ、両次元に線形補間である。２４ビットエン コードにおける各色成分は、個別にスケーリングすることができる。このように 、画像ごとに、再補間される成分とされない成分があってもよい。好ましいフィルタフォーマット 伝送されまたは記憶される圧縮されエンコードされた画像ファイルのフォーマ ットをここに詳述する。 ＧＴアートデータストリームのフォーマット 好ましいデータフォーマットは、「ＧＴアート」フォーマットとして知られて いる。これは、下記のように、ヘッダとそれに続く可変数のセグメントを有する データストリームで構成されている。 ヘッダのフォーマットは、この好ましい実施態様では、８バイトの長さである 。最初の２バイト（Byte０、Byte１）は、このデータがＧＴアートデータストリ ームであることを同定するためのシグネチャを形成する。Byte２とByte３は、こ のストリームのバージョンを同定する。典型的なデコーダは、メジャーバージョ ンおよ びある範囲のマイナーバージョンのストリームをデコードする。Byte４、Byte５ 、Byte６は予備である。Byte７は、そのストリームを生成したエンコーダを同定 する。まとめると、これらのバイトは、 各セグメントは、プレフィックスセクションとデータセクションとからなって いる。プレフィックスは、タグフィールドとサイズフィールドからなっており、 それらはその値に応じて三つのフォーマットの内の一つを使ってそれぞれエンコ ードされている。データセクションは、任意バイトのストリングであり、そのバ イトカウントがプレフィックスにサイズフィールドとしてエンコードされている 。 プレフイックスフォーマット プレフィックスのセグメントは、１、２または３バイトのシーケンスであり、 タグと呼ばれる「セグメントタイプ」および後に続くデータバイトのサイズと呼 ばれるカウントをエンコードするのに使用される。 １バイトのフォーマットは、０〜６３のタグ値とデータの０バイトを許容する 。２ばいとのフォーマットは、０〜３１のタグ値とデータの０〜５１１バイトを 許容する。３ばいとのフォーマットは、０〜２５５のタグ値とデータの０〜３２ ７６７バイトを許容する。このエンコーダは、タグ値およびサイズ値のための最 短のエンコードを選択する。 データセクション データセクションは、タグ識別子に特有のフォーマットのデータバイトを含ん でいる。その内容およびセグメントタイプの好ましい順序を下記に挙げる（全タ グの値を１６進で、およびフィールドを名称の隣に）。 セグメントタイプ（１）は、出力画像およびカラースペースの大きさを定義し、 次の６バイトで形成される。 バイト 各フラグは、サイズ、位置および意味において、ＧＴ＿ＩＮＳＴＡＮＣＥ＿Ｉ ＮＦＯセグメントの中のＪＧ＿ＧＴＦＬＡＧ＿ＣＬＲフィールド＿ｘｘｘとと同 一の単一フィールドを有している。（下記を参照。）このフィールドは、画像の カラースペースを決定する。（下記のセグメントタイプＪＧ＿ＳＥＧ＿ＧＴＩ＿ ＩＮＦＯを参照。） セグメントタイプ（２）は、画像の透明色を定義し、次の４バイトで形成され る。 バイト セグメントタイプ（３）は、画像をパレット化モードで表示するときに使用す るのに好ましい３色パレットを定義する。パレット化（８ビット）画像の場合、 このパレットをストリームパレットと称する。三つの成分（色０−Ｃ０、色１− Ｃ１、色２−Ｃ２、）は、順に、緑（Ｃ０）、次に青（Ｃ１）、次に赤（Ｃ２） である。 パレットのパック形式は： バイト ０−パレット内のエントリ数マイナス１（０〜２５５） １−フラグバイト ビットストリームのスタート位置より先は、データはビットの境界に記憶され ている。ビットは、昇順のアドレスバイトで上位桁から下位桁へ順序づけられて いる。フィールドは、上位桁から下位桁ビットへ記憶されている。 もし、「量子化／２次−３次圧縮」フラグビット（ビット３）がセットされる と、１０ビットのフィールド（Ｃ０＊８１＋Ｃ１＊９＋Ｃ２）が続き、Ｃ０（色 ０）、Ｃ１（色１）、およびＣ２（色２）が量子化されるレベル（０〜８）を示 す。（例えば、これら１０ビットフィールドは生エレメントあたりのビットの数 を表す。） もし色０が生で記憶されると（０／１ビット量子化の場合は常に生）、連続す るｎビット（色０の量子化因子に応じたビット数）のフィールドが用意され色０ の全部の値を保持する。他方、色０が圧縮されて記憶されると（これは、少なく とも８個の値があるときのみ起こる、８個より多い値が依然として生で記憶され るけれども）、最初の１６ビットはデルタマスクであり、どのデルタトークンが 使用中であるかを次のようにして選択する。第一のビットは、０のデ ルタがコードされるているとき１であり、第二のビットは、１のデルタに対して １になり、……、最後（１６番目）のビットは、１５のデルタがコードされてい るとき１である。 デルタトークンの意味は、次のとおりである。デルタトークンは、前のサンプ ルから次のものへの変化の量を示す。０〜１４のデルタ値は、次のサンプルを直 接（一つのトークンを介して）生成する。１５のデルタは特別なケースで、デル タが１５＋後続データを示す。多くのデルタ１５のトークンが一行に現れて、大 きいデルタをコードする。常に１５より小さい数のデルタトークンが存在して、 一回以上のデルタ１５の発生を終了させる。 デルタの値は、無符号である。それは、それらが現在値を一方向にのみ動かす ことができることを意味する。好ましい実行は、パレットを第一要素を介して降 順に記憶することから開始する。このように、第一の色のためのデルタトークン は、負の変化を表す（すなわち、デコードの間に現在の第一色の値から減算され る）。 デルタマスクの１６ビットに続くのは、デルタコードワード長のニブル（各４ ビット）である。デルタマスク内の全１ビットに対して一つのニブルが存在する 。（すなわち、コードワード長のニブルとデルタマスク内のビットとが位置的に 対応している。したがって、第一のニブルは、もし使われていれば、デルタ０に 対するコードワード長を表す。）コードワードに対するハフマン長は、１＋ニブ ルに記憶されている値である。 次のｎビットは、第一の色の値を生の形で保持している。一番最初の生のトー クンに続くのは、残りの第一の色の値を定義するデルタトークンに対する可変長 コードワードである。 もし、色１が生で記憶されると、（０／１ビット量子化の場合は 常に生）、次のようになる。連続するｎビット（色１の量子化因子に応じた数） のフィールドが用意され、色１の値の全部を保持する。そうでなければ、色１は 圧縮して記憶され、それは少なくとも８個の値でもって常に起こる。もし、圧縮 されると、圧縮表現は、デルタ１５のコードの定義を除き、色０と同一であり、 それは再定義されて、生へエスケープの定義のフラグを立て、次のｎビット（そ の色の量子化値に応じた数）が色の値を生の値で保持することを示す。 もし、色２が生で記憶されると、（０／１ビット量子化の場合は常に生）、次 のようになる。連続するｎビット（色２の量子化因子に応じた数）のフィールド が用意され、色２の値の全部を保持する。そうでなければ、色２は圧縮して記憶 され、それは少なくとも８個の値のときは常にそうであり、圧縮表現は、色１と 同一である。 セグメントタイプ４は、スプラッシュまたは画像データで描画またはパネリン グする前に画像ウィンドウを一つの色で溢れさせるのに使用する。このセグメン トは、次の４バイトを有する。 バイト ここに採用随意のスプラッシュの項を入れてもよい。そうするなら、それは、 正に主画像の項がそうであろう（データストリームの中で後続する）ように、セ グメントＪＧ＿ＳＥＧ＿ＧＴＩ＿ＩＮＦＯからＪＧ＿ＳＥＧ＿ＧＴＩ＿ＤＡＴＡ で構成されることになるであろう。 セグメントタイプ（５）は、各色成分について必須である。画像が２４ビット （３成分）であれば、三つの連続したＪＧ＿ＳＥＧ＿ＧＴＩ＿ＩＮＦＯセグメン トが他の如何なるセグメントより前に必要である。このフォーマットは、連続し たＪＧ＿ＳＥＧ＿ＧＴＩ＿ＩＮＦＯセグメントの数を数えてひとつの画像内の成 分の数を求める。それら成分は、０、１、２と番号付けされる（現れた順に）。 下記のＣ言語構造は、ＧＴ Ｉｎｆｏセグメントのパック形式を展開したもの である（ＵＩＮＴ８は「符号なし文字（unsigned char）タイプである」）。 全てのマルチバイトフィールドが複数の単一エンティティとして以下に記述さ れており、ストリーム内に下位バイトから上位バイトに記憶される。 以下の８つのフラグは、ＪＧ＿ＰＡＣＫＥＤ＿ＧＴ＿ＩＮＳＴＡＮＣＥ＿ＩＮ ＦＯセグメント（すなわち、セグメントタイプ（５））に対応する。 フラグ（１）は、セグメントあたりのパックされた画像の最大行 数が３２のときに立てられる。フラグが立っていなければ、セグメントあたり記 憶されている最大行数は１６である。 フラグ（２）は、画像の項がスプラッシュであることを示すために立てられる 。 フラグ（３）は、その項のピクセルフォーマットを決める４ビットのフィール ドである。これは、以下の６つの値のいずれをもとり得る。 ８ビットパレット化の項。この項でエンコードされる指標は、可変（エンコー ダ定義の）ストリームパレットを指す。 ８ビットの項。この項でエンコードされる指標は、プリセットされた２５６エ ントリのパレットを指し、３ビットが赤に、３ビットが緑に、そして２ビットが 青に割り当てられる。 ８ビットの項。この項でエンコードされる指標は、プリセットされた線形モノ クローム（グレイスケール）パレットを指し、０が黒を示し、０ｘｆｆが白を示 す。 ８ビットの項。この項でエンコードされる指標は、可変（エンコーダ定義の） パレットを指し、これはＩｎｆｏセグメントの直後に続く。 ２４ビットの項。三つのｉｎｆｏセグメントが存在しなければならない。圧縮 画像データは、パレットへの指標でなく、色成分値からなっている。 ２４ビットの項。この場合、唯一つのＩｎｆｏセグメントと一組のエンコード されたデータが存在する。三つの色成分は、一緒にインタリーブされた（Ｂ、Ｇ 、Ｒの順で）ままで、あたかも３倍の数のコラム（列）を持った単一の画像であ るかのようにエンコードされる。 フラグ（４）は、この項のカラースペースを決定する４ビットのフィールドで ある（２４ビットの場合に圧縮データ自体であるか、８ビットのパレット化され た項のパレットであるかのいずれか）。これは、以下の２つの値のいずれかを取 り得る。 カラースペースは、ＲＧＢである（名称中に使用のＢＧＲには意味がない）。 カラースペースは、ＹＵＶである。 解凍データをその最終寸法にスケーリング（尺度変換）する際に、フラグ（５ ）および（６）が強調フィルタ（上記）が関与するか否かを制御する。強調は、 行および列について個々に制御可能である。 立っていると、フラグ（７）および（８）は、画像全体を適当回数複製するこ とにより、スケーリングされた画像のサイズを増大させる。もし、画像のサイズ が減少しつつあるならば、範囲全体をスケーリングしないで、その最下行および 右列がクリップされる。 以下の８つのフィールドは、セグメントタイプ（５）（すなわち、ＪＧ＿ＳＥ Ｇ＿ＧＴＩ＿ＩＮＦＯセグメント）に関連して使用される。 フィールド（１）および（２）は、圧縮画像データの行数と列数を保持してい る。もし、これらの値がＪＧ＿ＳＥＧ＿ＷＩＮＤＯＷ＿ＩＮＦＯセグメントに記 録されているのと異なる場合は、その画像はＪＧ＿ＳＥＧ＿ＷＩＮＤＯＷ＿ＩＮ ＦＯセグメントの寸法に尺 度変換される。 ８ビットの項である場合、フィールド（３）は、エンコードプロセスにおいて 、下記のように色成分差に適用される色の重み係数を保持する。 これらの値は、情報の目的のためにのみ記憶される（ストリームのデコードに は影響しない）。 ２４ビットの項である場合、フィールド（３）は、エンコード中に使用された ものでデコードの間は逆転される必要のあるＤＰＣＭアルゴリズムを保持する。 上記は、次のピクセル関係を想定している。 ．．Ｂ ．ＣＸ （ここに、Ｘは目標ピクセルである） 「自動」が選択されている場合、ＤＰＣＭアルゴリズムは、行ごとの単位で動 的に（ダイナミックに）選択され、アルゴリズムタイプが各圧縮行の初めに記録 される。（ＤＰＣＭアルゴリズムについての上記の説明を参照されたい。） フィールド（４）および（５）は、エンコード時にプログラムされたように、 最小長および最大長のコピーストリングを表す。両フィールドは、４ビットであ る。最大長は、上位の４ビットに記憶される。この４ビットコードは、次のベク トルを指標して、実際の最小長さを作り出す：０、１、２、３、４、５、６、７ 、９、１３、２１、３７、６９、１３３、２６１、５１７、１０２９。この４ビ ットコードは、次のベクトルを指標して、実際の最大長さを作り出す：０、１、 ２、３、４、５、６、８、１２、２０、３７４６０、３７４６０、３７４６０、 ３７４６０、３７４６０、３７４６０。最大長テーブルを指標した後、その結果 に最小コピ一長が加算されて、最終的な最大コピー長を生成する。 フィールド（６）および（７）は、エンコード時にセットされた長さ２以上の コピーについての最大オフセットサイズである。両フィールドは、４ビットであ る。長さ２のサーチサイズが上位ビットに記憶される。これらのフィールドは、 コピーストリングが取り得る最大許容オフセットを制御する（長さ２以上の全て のコピーについて）。この４ビットコードは、次のベクトルを指標して、実際の 長さ２のコピーの最大オフセットサイズを作り出す：１、２、３、４、５、９、 １７、３３、６５、１２９、２５７、５１３、１０２５、２０４９、４０９７、 ８１９３。この４ビットコードは、次のベクトルを指標して、実際の長さが２よ り大きいコピーの最大オフセットサイズを作り出す：１、２、３、４、５、９、 １７、３３、６５、１２９、２５７、５１３、１０２５、２０４９、４０９７、 ８１９３。 フィールド８は、エンコード時にピクセルどうしの間の数値的な差に適用され て、それらが等しいとみなしてもよい程度に充分に近いか否かを決めるための許 容差である。「ＤｉｆＴｏｌ」が０であると、ピクセルが等しいとみなされるこ とはなく、いかなる一致をも生じさせない。２４ビットエンコードのためには、 このフィールドは、単に、ピクセル値の間の差の絶対値と比較される。パレット 化された（８ビット）エンコードのためには、比較されるべきピクセルは、まず 脱パレット化される（指標がパレット内で探索される）。次いで、色ベクトルは 、差が求められ（互いに他から減算され）、絶対値が取られて、ＣｘＷｅｉｇｈ ｔによって重み付けされる。次いで、得られたベクトル要素は、二乗され合計さ れる。この値が「ＤｉｆＴｏｌ」に対して比較され、等しいか判定される。 セグメントタイプ（６）は、局所または脱パレット化パレットを表す。このセ グメントは、採用任意で、８ビットパレット画像の場合のみ使用される。これは 、ストリームパレットと同じフォーマットで記憶される。（セグメントタイプＪ Ｇ＿ＳＥＧ＿ＧＴＩ＿ＰＡＬＥＴＴＥを参照されたい。） ハフマンセグメントは、採用任意である。成分についてハフマンセグメント（ タイプ（７））が受信されなければ、そのデータは生 であるに違いない（圧縮なしで記憶されている）。多色成分（２４ビット）画像 をデコードする際は、ＪＧ＿ＳＥＧ＿ＧＴＩ＿ＨＵＦＦＭＡＮセグメントが色成 分０、１、２に対応して順序付けされなければならない。ハフマンセグメントの 初めの１〜３バイトは、「最もポピュラーな」マスクを定義する。（上記参照。 ）記憶されたバイトの数は、五つの１ビットを出力するのに必要なバイト数によ って求められる。３バイト未満が必要なときは、後ろの１または２バイトは０と 推定される。論理的に記憶されたその３バイトは、２４ビットのマスクを表す。 五つの１ビットの位置は、初めの２４個のトラバースパターンオフセットの内の どれを前へ移動し、それにより最も効率的にコード化すべきであるかを示す。残 りのオフセットは、それらの相対的な順序を維持しており、五つの最もポピュラ ーなオフセットの後ろに移動される。（五つの最もポピュラーなオフセットの思 想は、上記に説明した。） 「何もするな」のマスクのサンプルは、下記の単バイト：０ｘＦ８であろう。 これは、初めの五つのオフセットを最もポピュラーなままとする。替わりとして 、 ０ｘ０ ０ｘ０ ０ｘ１Ｆ なら、最初の２４個のオフセットの内の最後の五つを最もポピュラーなものとす るであろう。 単一成分画像について、ＪＧ＿ＳＥＧ＿ＧＴＩ＿ＤＡＴＡセグメント（タイプ （８））は、画像の頭から始めて、行の順序ブロックとして順序づけられ、任意 の数（ＪＧ＿ＳＥＧ＿ＷＩＮＤＯＷ＿ＩＮＦＯセグメント（すなわち、セグメン トタイプ（１））の中で特 定された最大値まで）の画像行を含んでよい。全部の画像行を記憶するのに充分 なデータセグメントが存在する。もし、画像が多成分を有する場合は、デコード プロセスの要求に応じて各成分に対して新しいデータセグメントが使えるように 、各成分についてＪＧ＿ＳＥＧ＿ＧＴＩ＿ＤＡＴＡセグメント（すなわち、セグ メントタイプ（８））がインタリーブされる。これにより、デコーダは、キャッ シュ成分データセグメントを持つ必要がなくなる。この簡単な場合は、全部の成 分が同じ副標本化因子で記憶され、各セグメントにおいて同じ数の行が記憶され て、成分セグメントは、０、１、２、０、１、２、…とインタリーブされる。も し、最後の二つの成分が最初の成分の半分の速度で副標本化された（ＹＵＶの場 合については典型的）としら、成分の順序は、０、０、１、２、０、０、１、２ 、…。これは、成分１および２のデータの２倍の成分Ｏのデータがあるからであ る。 このＧＴ画像データセグメントの最初のバイトは、次の内容を保持する。 １番目のバイトに続いて、ビットストリームが始まる。データは、ビット境界 に記憶される。ビットは、昇順のアドレスバイトで上位桁から下位桁に順序付け られている。フィールドは、上位ビットから下位のビットへと記憶されている。 各データ行についての圧縮ビットは、連続（連接）して記憶される（行と行の 間にバイト境界なしに）。それらビットは、上述のように、その成分に対するハ フマンツリーを使用してコードワードに 変換されＧＴトークンを表す。 さらに、可変（自動）ＤＰＣＭモードが使用される場合は、下記のように、各 行の始めのところに１または２ビットのＤＰＣＭタイプのコードワードが記憶さ れる。 これは、後続の行のエンコード中に採用されたＤＰＣＭアルゴリズムのタイプ を示している。 セグメントタイプ（９）は、画像の許容可能な小型版（ミニチュアフォーム） を作り出すために、ストリーム中のどの点で充分なデータが受信されたかを示す 。もし、スプラッシュ画像がミニチュア画像を生成するのに使用しうるとみなさ れたときは、フラグをスプラッシュ画像に続いて置いてもよいし、またはフラグ は主画像の後に置いてもよい。 セグメントタイプ（１０）は、フォーマットされたストリームの終わりを示す 。 上記に挙げた種々のセグメント、フラグおよび値は、この発明に従って圧縮さ れてエンコードされた画像データを伝送するためのフォーマットを定義する。も ちろん、前記のフォーマットは改変されてもよいし、代替フォーマットが採用さ れてもよいことを、当業者は認識するであろう。例えば、上で注記したように、 セグメントの あるものは採用任意であり、使用する必要はない。同様に、「必須の」セグメン トも改変されてもよく、または代用が用意される場合は置換されてもよい。他の 例として、ハフマンエンコード以外の代替形式のエンコードが採用され場合は、 ハフマンセグメントはそれに応じて変更することができる。結言 予め定めた非線形トラバースパターンを採用することにより、この発明は、以 前の圧縮法の不利および欠点を克服している。圧縮スピードが実質的に向上し、 この発明は、従来技術のハッシュ法において要した複雑な回路およびｓ時間のか かる計算の必要性を除去するものである。 この発明のいくつかの実施態様について説明した。しかしながら、この発明の 精神および範囲から逸脱することなく、種々の変更がなされ得ることが、理解さ れるであろう。したがって、この発明は、具体的な説明された実施態様に限定さ れるべきでなく、添付の請求の範囲によってのみ限定されるものと理解されたい 。

【手続補正書】 【提出日】１９９９年４月３０日（１９９９．４．３０） 【補正内容】 請求の範囲 １．複数の目標ピクセルおよび複数の前位ピクセルを有するピクセルアレイで、 それぞれの前位ピクセルはそのピクセルアレイ内でそれぞれの目標ピクセルより 前の位置にあるようなピクセルアレイを有する原画像を圧縮する方法であって、 （ａ）（１）所定の非線形トラバースパターンに従って前記ピクセルアレイをト ラバースして、ひとつの目標ピクセルと一致するひとつの前位ピクセルが有れば 、それを見つけだし、 （２）もし、そのような一致する前位ピクセルが見つけだされたら、当該 一致した目標ピクセルおよび前位ピクセルから線形的に次々たどりながら対応す る目標ピクセルと前位ピクセルを比較していって、一致する前位ピクセルストリ ングが有る場合、それを見つけだし、 （３）ステップ（１）および（２）を繰り返して、最長の一致前位ピクセ ルストリングを見つけだし、 （４）それぞれのそのような最長の一致前位ピクセルストリングを表す圧 縮表現としてコピートークンを生成し、 （５）一致前位ピクセルを有しない目標ピクセルのそれぞれについてリテ ラルトークンを生成する ことを繰り返し行うことにより原画像を圧縮して圧縮画像を得るステップ を含んでなる方法。 ２．複数の目標ピクセルおよび複数の前位ピクセルを有するピクセルアレイで、 それぞれの前位ピクセルはそのピクセルアレイ内でそ れぞれの目標ピクセルより前の位置にあるようなピクセルアレイを有する原画像 を圧縮して、圧縮画像を得る方法であって、 （ａ）所定の非線形トラバースパターンに従って前記ピクセルアレイを繰り返し トラバースして、ひとつの目標ピクセルストリングと一致するひとつの最長の一 致前位ピクセルストリングが有れば、それを見つけだすステップと、 （ｂ）そのような一致した目標ピクセルストリングを表す圧縮表現としてそのよ うな最長の一致前位ピクセルストリングを参照するコピートークンを生成するス テップと、 （ｃ）一致する前位ピクセルを有しない目標ピクセルのそれぞれについてリテラ ルトークンを生成するステップと を含んでなる方法。 ３．請求項１または２に記載の方法であって、さらに、 ハフマン符号化アルゴリズムを使用して前記圧縮画像をエンコードすることに より前記圧縮画像をさらに圧縮するステップを含んでなる方法。 ４．請求項３に記載の方法であって、 全ての可能なコピートークンおよび全ての可能なリテラルトークンがひとつの トークンセットを形成していて、さらに、 （ａ）そのトークンセットについてハフマンツリーを生成するステップと、 （ｂ）そのハフマンツリーを出力するステップと、 （ｃ）そのハフマンツリーを出力した後に前記圧縮画像を出力するステップと を含んでなる方法。 ５．請求項４に記載の方法であって、さらに、 （ａ）前記ハフマンツリーを出力する前にハフマンツリーをひとつの圧縮フォー マットにエンコードして、圧縮されたハフマンツリーを得るステップと、 （ｂ）そのハフマンツリーを使用して前記エンコードされた圧縮画像をデコード するステップと、 （ｃ）そのデコードされた圧縮画像を解凍して原画像を得るステップと を含んでなる方法。 ６．請求項１に記載の方法であって、さらに、 （ａ）原画像を圧縮する前に原画像を部分標本化するステップを含んでなる方法 。 ７．請求項１に記載の方法において、 前記所定の非線形トラバースパターンは固定長を有することを特徴とする方法 。 ８．請求項６に記載の方法において、 前記所定の非線形トラバースパターンは経験的に定められることを特徴とする 方法。 ９．請求項８に記載の方法において、 前記所定の非線形トラバースパターンは複数のピクセルオフセッ トを有し、その初めの２４個は下記表のものであり、 ここに、「＃」はエンコード中のピクセル位置を示し、１から２４の数字は初め の２４個のピクセルオフセットをその順に示していることを特徴とする方法。 １０．請求項１または２に記載の方法において、 各最長の一致データストリングは、目標ピクセルのストリングに対応する一致 ピクセルのストリングを有し、 最長の一致データストリングを見つける際に、ピクセルアレイ内の各ピクセル は許容差を有していて、もし一致ピクセルのストリング内の一致ピクセルのそれ ぞれが目標ピクセルのストリング内の対応目標ピクセルの許容差範囲内に入って いれば、最長一致データストリング内の一致ピクセルのストリングは目標ピクセ ルのストリングに一致するとみなされる ことを特徴とする方法。 １１．複数の目標ピクセルおよび複数の前位ピクセルを有するピクセルアレイで 、それぞれの前位ピクセルはそのピクセルアレイ内でそれぞれの目標ピクセルよ り前の位置にあるようなピクセルアレイを有する原画像を圧縮して、圧縮画像を 得るシステムであって、 （ａ）所定の非線形トラバースパターンに従って前記ピクセルアレイを繰り返し トラバースして、ひとつの目標ピクセルストリングと一致するひとつの最長の一 致前位ピクセルストリングが有れば、それを見つけだす手段と、 （ｂ）そのような一致した目標ピクセルストリングを表す圧縮表現としてそのよ うな最長の一致前位ピクセルストリングを参照するコピートークンを生成する手 段と、 （ｃ）一致する前位ピクセルを有しない目標ピクセルのそれぞれについてリテラ ルトークンを生成する手段と を備えてなるシステム。 １２．ピクセルアレイを有する原画像を圧縮して圧縮画像を得るコンピュータプ ログラムであって、 そのプログラムはコンピュータシステムにより読み取り可能な媒体上に認識可 能に記録されており、プログラムがコンピュータシステムにより読み取られて実 行されると、 （ａ）所定の非線形トラバースパターンに従って前記ピクセルアレイを繰り返し トラバースして、ひとつの目標ピクセルストリングと一致するひとつの最長の一 致前位ピクセルストリングが有れば、それを見つけだす機能と、 （ｂ）そのような一致した目標ピクセルストリングを表す圧縮表現としてそのよ うな最長の一致前位ピクセルストリングを参照するコピートークンを生成する機 能と、 （ｃ）一致する前位ピクセルを有しない目標ピクセルのそれぞれについてリテラ ルトークンを生成する機能と を実行するようにコンピュータシステムの構成を配置するように適 合させてなるコンピュータプログラム。 １３．先頭の目標ピクセルおよび複数の前位ピクセルを有するピクセルアレイで 、それぞれの前位ピクセルはそのピクセルアレイ内でそれぞれの目標ピクセルの 前に位置しているピクセルアレイよりなる画像データを圧縮する方法であって、 （ａ）前記画像データを逆向き非線形トラバースパターンに従って前記ピクセル アレイ内で逆向きにトラバースするステップと、 （ｂ）前記先頭の目標ピクセルと一致する、ひとつの先頭の一致前位ピクセルが があれば、それを見つけだすステップと、 （ｃ）もしひとつの先頭の一致前位ピクセルが見つけだされたら、前記ピクセル アレイ内で前向きの線形トラバースパターンに従って、前記先頭の目標ピクセル に続く複数のピクセルと前記先頭の一致前位ピクセルに続く複数のピクセルの両 方を、前記先頭の目標ピクセルに続く目標ピクセルが前記先頭の一致前位ピクセ ルに続く前位ピクセルと一致しなくなるまでトラバースして一致データストリン グを定義するステップと、 （ｄ）前記非線形トラバースパターン内の前記画像データをトラバースすること を続けて前記先頭の目標ピクセルと一致する他の前位ピクセルを見つけだすこと を試みるステップと、 （ｅ）もし他の一致前位ピクセルが見つけだされたらば、他の一致データストリ ングをステップ（ｃ）に従って定義するステップと、 （ｆ）ステップ（ｄ）と（ｅ）を繰り返してすべての一致データストリングを定 義するステップと、 （ｇ）前記一致データストリングの何れが最長の一致データストリ ングであるかを決定するステップと、 （ｈ）前記最長の一致データストリングをコピートークンとしてエンコードする ステップと を含んでなる方法。 １４．複数の目標ピクセルおよび複数の前位ピクセルを含んでおり、それぞれの 前位ピクセルはピクセルアレイ内で目標ピクセルより前の位置にあるようなピク セルアレイよりなる画像データを圧縮する方法であって、 （ａ）前記前位ピクセルを、先頭の目標ピクセルに関して所定の位置を有する最 初の前位ピクセルのところで起こる始まりと、前記先頭の目標ピクセルに関して 他の所定の位置を有する最後の前位ピクセルのところで起こる終わりを有する所 定の非線形トラバースパターンに従ってトラバースするステップと、 （ｂ）前記所定の非線形トラバースパターンに従ってトラバースされた前位ピク セルの中から、前記先頭の目標ピクセルと一致する先頭の一致前位ピクセルがあ れば、それを見つけだすステップと （ｃ）もしひとつの先頭の一致前位ピクセルが見つけだされたら、線形トラバー スパスに従って、前記先頭の目標ピクセルに後続する目標ピクセルと前記先頭の 一致前位ピクセルに後続する前位ピクセルの両方を、各後続の目標ピクセルに前 記線形トラバースパスに沿って後続の前位ピクセルを対応させながらトラバース するステップと、 （ｄ）それぞれの続く目標ピクセルを対応する前位ピクセルと比較して、続く目 標ピクセルが対応する続く前位ピクセルと一致し ないことが見つけだされるまで前記線形トラバースパス内のトラバースを続けて 非一致前位ピクセルを見つけだすステップと、 （ｅ）一致データストリングを、前記先頭の一致前位ピクセルで始まり前記ピク セルアレイ内で前記非一致前位ピクセルの直前の前位ピクセルで終わるピクセル のストリングとして定義するステップと、 （ｆ）前記非線形トラバースパターン内の前記前位ピクセルのトラバースを、前 記非線形トラバースパターン内の前記先頭の一致前位ピクセルに先行する前位ピ クセルで開始して続けて、前記先頭の目標ピクセルと一致する他の前位ピクセル を見つけ出すことを試みるステップと、 （ｇ）もし他の一致前位ピクセルが見つけだされたらば、ステップ（ｃ）から（ ｅ）を繰り返して他の一致データストリングを定義するステップと、 （ｈ）ステップ（ｆ）と（ｇ）を最後の前位ピクセルに達するまで繰り返すステ ップと、 （ｉ）もしただひとつの一致データストリングだけが定義されたらば、そのひと つの一致データストリングを最長の一致データストリングとするステップと、 （ｊ）もし複数の一致データストリングが定義されたらば、この複数の一致デー タストリングの何れが最長の一致データストリングであるかを決定するステップ と、 （ｋ）前記最長の一致データストリングをコピートークンとしてエンコードする ステップと を含んでなる方法。 １５．スキャンされている目標ピクセルを示すピクセルポインタを含むデータ圧 縮システム内においてピクセルアレイを含む画像データのストリームをエンコー ドされた画像データのストリームに圧縮すると共にこのエンコードされた画像デ ータのストリームを解凍された画像に解凍する方法であって、 （ａ）ピクセルアレイ内の少なくともひとつのピクセルをスキャンして前記ピク セルアレイ内に位置を有するスキャンされた前位ピクセルを得るステップと、 （ｂ）（１）前記ピクセルアレイ内に位置を有する先頭目標ピクセルをスキャン し、 （２）前記スキャンされた前位ピクセルを所定の非線形トラバースパター ンに従ってトラバースし、 （３）トラバースされた前記スキャンされた前位ピクセルの何れかがスキ ャンされた前記先頭目標ピクセルと一致するかを決定して、先頭のスキャンされ た一致前位ピクセルを見つけだし、 （４）前記ピクセルポインタを、前記ピクセルアレイ内で前記先頭の目標 ピクセルの位置の直後に続く位置にあるスキャンされる次の目標ピクセルに進め 、 （５）前記次の目標ピクセルが、前記ピクセルアレイ内で前記先頭のスキ ャンされた一致前位ピクセルの直後に続く位置を有する後続のスキャンされた前 位ピクセルと一致するかどうかを決定し、 （６）ピクセルポインタを進めて、スキャンされた一致前位ピクセルが見 いだされなくなるまでステップｂ（５）を繰り返して前記ピクセルポインタによ り示されたピクセルと 一致する全ての後続のスキャンされた前位ピクセルを見つけだして、一致データ ストリングを定義する ことにより、スキャンされるピクセルのストリングと一致する一致データス トリングを求めて、前記スキャンされた前位ピクセルをサーチするステップと、 （ｃ）前記ピクセルアレイ内における前記先頭の目標ピクセルに関する、前記先 頭のスキャンされた一致前位ピクセルの位置を表すオフセットを決定するステッ プと、 （ｄ）前記一致データストリング内のスキャンされた一致前位ピクセルの数であ る前記一致データストリングのストリング長を決定するステップと、 （ｅ）前記一致データストリングを、前記先頭のスキャンされた一致ピクセルの オフセットと前記一致データストリングのストリング長を含むコピートークンに 変換するステップと、 （ｆ）前記コピートークンをエンコードするステップと を含んでなる方法。 １６．請求項１５に記載の方法であって、さらに （ａ）前記ピクセルアレイを部分標本化して、画像データのストリーム内のデー タを、前記一致データストリングのために前記スキャンされた前位ピクセルをサ ーチする前に減少させるステップ を含んでなる方法。 １７．それぞれのピクセルが色画像データを含んでいる請求項１６に記載の方法 であって、さらに （ａ）前記ピクセルアレイを部分標本化する前に、それぞれのピクセルの色画像 データをフィルタするステップ を含んでなる方法。 １８．色画像データがカラースペースを有している請求項１７に記載の方法であ って、さらに （ａ）前記画像データをフィルタする前に、前記画像データのカラースペースを 他のカラースペースに変換するステップ を含んでなる方法。 １９．前記カラースペースがＹＣｒＣｂカラースペースである請求項１８に記載 の方法。 ２０．請求項１５に記載の方法であって、 前記ピクセルアレイ内のそれぞれのピクセルは、スキャンされた一致ピクセル が見つけだされたときを決定するのに使用される予め定められた許容差を有して いて、 スキャンされた前位ピクセルが目標ピクセルと一致するかどうかを決定す るために、 （ａ）スキャン中の目標ピクセルをスキャンされた前位ピクセルと比較するステ ップと、 （ｂ）前記スキャンされた前位ピクセルが前記目標ピクセルの前記予め定められ た許容差内にあるかどうかを決定するステップと、 （ｃ）前記スキャンされた前位ピクセルが前記目標ピクセルの前記予め定められ た許容差内にあるときは前記スキャンされた前位ピクセルを一致目標ピクセルと 見なすステップと が実行されることを特徴とする 方法。 ２１．請求項１５に記載の方法において、 前記所定の非線形トラバースパターンは圧縮される個々の画像データのストリ ームごとに画像トラバース長さを含む固定長を有しており、 前記画像トラバース長さは画像ごとに異なっている ことを特徴とする方法。 ２２．請求項１５に記載の方法において、 前記所定の非線形トラバースパターンは、圧縮される画像データの単一のスト リームの圧縮の間に変化する長さを有している ことを特徴とする方法。 ２３．請求項１５に記載の方法において、 前記所定の非線形トラバースパターンは、圧縮される画像データの各個々のス トリームごとに、画像ごとに異なる固定したパターンを含んでいる ことを特徴とする方法。 ２４．請求項１５に記載の方法において、 前記所定の非線形トラバースパターンは圧縮される画像データの単一のストリ ームの圧縮の間に変化する ことを特徴とする方法。２５．請求項１５に記載の方法であって、 前記ピクセルアレイはアレイの限界を有し、前記所定の非線形トラバースパタ ーンは複数のセグメントを有し、その複数のセグメントのそれぞれはスキャンさ れた前位ピクセルに対応しており、 この方法は、さらに、 （ａ）前記複数のセグメントから前記アレイの限界の外側にある全てのセグメン トを取り除くステップ を含んでなる ことを特徴とする方法。 ２６．請求項２５に記載の方法において、 前記所定の非線形トラバースパターンは経験的に定めたトラバースパターンで あり、その経験的に定めたパターンは経験的に定めた要領で前記複数のセグメン トがトラバースされるようにすることを特徴とする方法。 ２７．請求項２６に記載の方法において、 トラバースされる初めの２４個のセグメントの前記経験的に定めたパターンは 下記表のものであり、 ここに、「＃」はスキャン中の目標ピクセルであり、１から２４の 数字は１から２４の順にトラバースされる初めの２４個のセグメントに対応して いる ことを特徴とする方法。 ２８．請求項２７に記載の方法において、 トラバースされる次の４１個のセグメントの前記経験的に定めたパターンは下 記表のものであり、 ここに、２５から６５の数字は２５から６５の順にトラバースされる次の４１個 のセグメントに対応している ことを特徴とする方法。 ２９．請求項２６に記載の方法において、 前記所定の非線形トラバースパターンにおける前記複数のセグメントの少なく とも一つは当該トラバースパターンにおける他のセグメントよりも優先的な扱い を受け、 前記コピートークンは複数のトークン位置を有し、 前記優先的な扱いを受ける少なくとも一つのセグメントは前記コピートークン の内の前記複数のトークン位置の中から最適なトーク ン位置が割り当てられる ことを特徴とする方法。 ３０．請求項１５に記載の方法において、 前記画像データのストリームは長方形の画像を含む ことを特徴とする方法。 ３１．請求項１５に記載の方法において、 前記一致データストリングはハフマンアルゴリズムに従ってエンコードされる ことを特徴とする方法。 ３２．請求項１５に記載の方法であって、 前記エンコードされた画像データのストリームは、それぞれがスキャン中のピ クセルに対応しかつスキャンされた一致前位ピクセルを有しないリテラルトーク ンと、もし一致データストリングに対応するコピートークンがあればそのコピー トークンとを含むトークン化されたデータを含んでおり、 この方法は、さらに、 （ａ）スキャンされた一致前位ピクセルを有しないスキャン中のピクセルの各々 をリテラルトークンに変換するステップと、 （ｂ）もし、一致データストリングがあれば、その各々をコピートークンに変換 するステップと、 （ｃ）前記リテラルトークンの各々と前記コピートークンの各々をハフマン圧縮 アルゴリズムを用いてエンコードして前記エンコードされた画像データのストリ ームを得るステップと、 （ｄ）前記エンコードされた画像データのストリームを伝達するステップと、 （ｅ）前記エンコードされた画像データのストリームをハフマン解凍アルゴリズ ムを用いてデコードして画像データのデコードされたストリームを得るステップ と を含んでなる ことを特徴とする方法。 ３３．請求項３２に記載の方法であって、さらに、 （ａ）前記解凍された画像を得るために、前記リテラルトークンの各々と前記コ ピートークンの各々をピクセル成分値に伸張することを含んで前記画像データの デコードされたストリームを伸張するステップ を含んでなる方法。 ３４．請求項３３に記載の方法において、 前記エンコードされた画像データのストリームが、同時にデコード及び伸張さ れる ことを特徴とする方法。 ３５．請求項３３に記載の方法であって、さらに、 （ａ）前記ピクセル成分値をフィルタして前記解凍された画像を強調するステッ プ を含んでなる方法。 ３６．請求項１５に記載の方法であって、 前記解凍された画像は二次元の画像であり、 この方法は、さらに、 （ａ）前記二次元の画像の両次元において線形補間を実施することを含んで前記 解凍された画像を再補間するステップ を含んでなる ことを特徴とする方法。 ３７．請求項２０に記載の方法において、 前記予め定められた許容差は可変である ことを特徴とする方法。 ３８．請求項２０に記載の方法であって、さらに、 （ａ）もし比較される前記スキャンされた前位ピクセルが、比較される前記目標 ピクセルの前記予め定められた許容差外であれば、前記ピクセルアレイのサーチ を続行して他のスキャンされた前位ピクセルが前記ピクセルアレイ中の前記目標 ピクセルの直後に続く位置にあるピクセルの前記予め定められた許容差内にある かどうかを決定するステップ を含んでなる ことを特徴とする方法。 ３９．請求項３３に記載の方法であって、さらに、 （ａ）前記画像データのストリームを副標本化してスプラッシ画像を得るステッ プと、 （ｂ）前記スプラッシュ画像をエンコードしてエンコードされたスプラッシュ画 像を得るステップと、 （ｃ）前記エンコードされたスプラッシュ画像を伝達するステップと、 （ｄ）前記エンコードされたスプラッシュ画像をデコードしてデコ ードされたス プラッシュ画像を得るステップと、 （ｅ）前記エンコードされたデータのストリームがデコード及び伸張されている 間に前記デコードされたスプラッシュ画像を表示するステップと を含んでなる方法。 ４０．請求項３９に記載の方法であって、 前記スプラッシ画像は複数の色を含み、 この方法は、さらに、 （ａ）前記複数の色から最も普通の色を表すプリスプラッシコードを決定するス テップと、 （ｂ）前記最も普通の色を前記デコードされたスプラッシ画像の背景色として表 示するステップと を含んでなる ことを特徴とする方法。 ４１．データ圧縮システム内においてそれ自体からの少なくともひとつのピクセ ルを受け入れるストリングに分割可能なピクセルアレイを含む画像データのスト リームを圧縮するとともにこの画像データのストリームを解凍された画像に解凍 するための方法であって、 （ａ）前記ピクセルアレイを所定の非線形トラバースパターンに従ってスキャン してスキャンされた前位ピクセルを得るステップと、 （ｂ）前記スキャンされたピクセルを前記スキャンされた前位ピクセルと比較し てスキャンされたピクセルの何れかが前記スキャンされた前位ピクセルと一致す るかどうかを決定するステップと、 （ｃ）スキャンされたピクセルと一致する少なくともひとつのスキャンされた前 位ピクセルと対応するストリングを有するスキャンされた少なくともひとつのピ クセルの各ストリングに対する一致データストリングで、前記スキャンされた一 致前位ピクセルと対応する画像データを含む一致データストリングが、もしあれ ば、それを生成するステップと、 （ｄ）もし一致データストリングが生成されれば、そのような一致データストリ ングをコピートークンに変換するステップと、 （ｅ）スキャンされたピクセルがスキャンされた一致前位ピクセルを有しないな らば、スキャンされたピクセルをリテラルトークンに変換するステップと、 （ｆ）前記コピートークンがあればそれをエンコードし、また前記リテラルトー クンをエンコードされたトークンセットにエンコードするステップと、 （ｇ）エンコードされた前記トークンセットを伝達するステップと、 （ｈ）前記エンコードされたトークンセットをデコードしてデコードされたトー クンセットを得るステップと、 （ｉ）前記デコードされたトークンセットを伸張して解凍された画像を得るステ ップと を含んでなる方法。 ４２．請求項４１に記載の方法であって、 前記比較して決定するステップは、さらに、 （ａ）スキャンされている先頭ピクセルを選択するステップと、 （ｂ）前記所定の非線形トラバースパターンに従って前記スキャンされた前位ピ クセルをトラバースし、前記スキャンされている先頭ピクセルが前記所定の非線 形トラバースパターンに従ってスキャンされた個々の前位ピクセルと比較される ステップと、 （ｃ）もし前記先頭ピクセルに一致する最初のスキャンされた一致前位ピクセル が見つけだされたら、前記所定の非線形トラバースパターンで前記スキャンされ た前位ピクセルをトラバースすることを停止するステップと、 （ｄ）前記ピクセルアレイ内の前記先頭ピクセルの直後に続く位置に見つけださ れる次のスキャンされるべきピクセルを選択するステップと、 （ｅ）前記次のピクセルを、前記ピクセルアレイ内で前記最初のスキャンされた 一致前位ピクセルの直後に続く位置に見つけだされる後続のスキャンされた前位 ピクセルと比較するステップと、 （ｆ）前記後続のスキャンされた前位ピクセルが前記次のピクセルと一致するか どうかを決定し、それにより他のスキャンされた一致前位ピクセルが存在するか どうかを決定するステップと、 （ｇ）スキャンされるべき次のピクセルを選択することと、そのような次のピク セルを他の後続のスキャンされた前位ピクセルと比較することを、後続のスキャ ンされた前位ピクセルが次のピクセルと一致しなくなるまで繰り返すステップと を含む方法。 ４３．請求項４１に記載の方法であって、 前記一致データストリングをコピートークンに変換するステップは、さらに、 （ａ）前記ピクセルアレイ内で前記先頭ピクセルに対比して前記スキャンされた 最初の一致前位ピクセルの位置を表すオフセットを決定するステップと、 （ｂ）前記決定されたスキャンされた一致前位ピクセルの数を表すストリング長 さを決定するステップと、 （ｃ）前記スキャンされた最初の一致前位ピクセルのオフセットと前記ストリン グ長さを結合して前記コピートークンを形成するステップと を含む方法。 ４４．請求項４１に記載の方法において、 前記コピートークンおよびリテラルトークンはハフマンアルゴリズムに従って エンコードされる ことを特徴とする方法。 ４５．請求項４１に記載の方法であって、さらに、 （ａ）全ての可能性のあるコピートークンとリテラルトークンに位置的に対応す るハフマンツリーを生成するステップと、 （ｂ）前記ハフマンツリーを圧縮されたフォーマットにエンコードして圧縮され たハフマンツリーを得るステップと、 （ｃ）前記エンコードされたトークンのセットを伝達する前に前記 圧縮されたハフマンツリーを伝達するステップと、 （ｄ）前記圧縮されたハフマンツリーをデコードおよび伸張するステップと、 （ｅ）前記ハフマンツリーを用いて前記エンコードされたトークンのセットをデ コードするステップと を含んでなる方法。 ４６．請求項４１に記載の方法であって、さらに、 （ａ）前記エンコードされたトークンのセットを複数のブロックに区分けして、 それら複数のブロックを伝達される度に順次デコードするステップと、 （ｂ）前記複数のブロックがデコードされるにつれて、そのブロックの各々を表 示し、各々が前記複数のブロックの一つに対応する前記デコードされた画像の部 分のそれぞれは、それがデコードされた直後に表示され得るようにするステップ と を含んでなる方法。 ４７．請求項４１に記載の方法であって、さらに、 （ａ）前記ピクセルアレイをスキャンする前に前記画像データのストリームを副 標本化して前記画像データのストリーム内のデータを減らすステップと、 （ｂ）前記解凍された画像を再補間するステップと を含んでなる方法。 ４８．請求項４１に記載の方法において、 スキャン中の各ピクセルは許容差を有し、もしスキャンされた前 位ピクセルが前記スキャン中のピクセルの許容差内に入っていれば、前記スキャ ンされた前位ピクセルが前記スキャン中のピクセルと一致することとする ことを特徴とする方法。 ４９．請求項４８に記載の方法であって、さらに、 （ａ）スキャンされた一致ピクセルの平均品質を示す第二許容差を与えるステッ プ を含んでなる方法。 ５０．ピクセルアレイを含む画像データのストリームをエンコードされた画像デ ータのストリームに圧縮すると共にこのエンコードされた画像データのストリー ムを解凍された画像に解凍するための、スキャンされる目標ピクセルを示すピク セルポインタを含むデータ圧縮システムであって、 （ａ）ピクセルアレイ内の少なくともひとつのピクセルをスキャンして前記ピク セルアレイ内に位置を有するスキャンされた前位ピクセルを得るスキャナと、 （ｂ）（１）前記ピクセルアレイ内に位置を有する先頭目標ピクセルをスキャン する手段と、 （２）前記スキャンされた前位ピクセルを所定の非線形トラバースパター ンを用いててトラバースする手段と、 （３）前記スキャンされた前位ピクセルの何れかがスキャンされた前記先 頭目標ピクセルと一致するかを決定して、先頭のスキャンされた一致前位ピクセ ルを見つけだす第１比較手段と、、 （４）前記ピクセルポインタを、前記ピクセルアレイ内で前記先頭の目標 ピクセルの位置の直後に続く位置にあるスキャンされる次の目標ピクセルに進め る手段と、 （５）前記次の目標ピクセルが、前記ピクセルアレイ内で前記先頭のスキ ャンされた一致前位ピクセルの直後に続く位置を有する後続のスキャンされた前 位ピクセルと一致するかどうかを決定する第２比較手段と、 （６）ピクセルポインタを進めて、スキャンされた一致前位ピクセルが見 いだされなくなるまでステップｂ（５）を繰り返して前記ピクセルポインタによ り示されたピクセルと一致する全ての後続のスキャンされた前位ピクセルを見つ けだして、一致データストリングを定義する手段と を含む、スキャンされるピクセルのストリングと一致する一致データストリ ングを求めて、前記スキャンされた前位ピクセルをサーチする手段と、 （ｃ）前記ピクセルアレイ内における前記先頭の目標ピクセルに関する、前記先 頭のスキャンされた一致前位ピクセルの位置を表すオフセットを決定する手段と 、 （ｄ）前記一致データストリング内のスキャンされた一致前位ピクセルの数であ る前記一致データストリングのストリング長を決定する手段と、 （ｅ）前記一致データストリングを、前記先頭のスキャンされた一致前位ピクセ ルのオフセットと前記一致データストリングのストリング長を含むコピートーク ンに変換するコンバータと、 （ｆ）前記コピートークンをエンコードするエンコーダと を含んでなるシステム。５１．請求項５０に記載のシステムであって、さらに、 （ａ）前記スキャンされた前位ピクセルをサーチする手段が作動する前に前記ピ クセルアレイを副標本化して画像データストリーム内のデータを減らす標本化装 置 を含んでなるシステム。 ５２．請求項５１に記載のシステムであって、 各ピクセルは色画像データをんでおり、 このシステムは、さらに、 （ａ）前記標本化装置が前記ピクセルアレイを副標本化する前に各ピクセルの前 記色画像データをフィルタリングするフィルタを含んでなる ことを特徴とするシステム。 ５３．請求項５２に記載のシステムであって、 前記色画像データはカラースペースを有しており、 このシステムは、さらに、 （ａ）前記色画像データをフィルタリングする前に前記画像データのカラースペ ースを他のカラースペースに変換するコンバータ を含んでなる ことを特徴とするシステム。 ５４．請求項５３に記載のシステムにおいて、 前記カラースペースはＹＣｒＣｂカラースペースである ことを特徴とするシステム。 ５５．請求項５０に記載のシステムであって、 前記ピクセルアレイの各ピクセルはスキャンされた一致前位ピクセルが見つけ だされたときを決定するのに使用される予め定められた許容差を有していて、 前記第１および第２比較手段の各々は、 （ａ）スキャン中の目標ピクセルをスキャンされた前位ピクセルと比較するコン パレータと、 （ｂ）前記スキャンされた前位ピクセルが前記目標ピクセルの前記予め定められ た許容差の範囲内にあるかどうかを決定する手段と、 （ｃ）前記スキャンされた前位ピクセルが前記目標ピクセルの前記予め定められ た許容差内にあるときは前記スキャンされた前位ピクセルをスキャンされた一致 前位ピクセルと同定する手段と を含んでいる ことを特徴とするシステム。 ５６．請求項５０に記載のシステムにおいて、 前記所定の非線形トラバースパターンは圧縮される個々の画像データのストリ ームごとに画像トラバース長さを含む固定長を有しており、 前記画像トラバース長さは画像ごとに異なっている ことを特徴とするシステム。 ５７．請求項５０に記載のシステムにおいて、 前記所定の非線形トラバースパターンは、圧縮される画像データの単一のスト リームの圧縮の間に変化する長さを有している ことを特徴とするシステム。 ５８．請求項５０に記載のシステムにおいて、 前記所定の非線形トラバースパターンは、圧縮される画像データの各個々のス トリームに対して、画像ごとに異なる固定パターンを含んでいる ことを特徴とするシステム。 ５９．請求項５０に記載のシステムにおいて、 前記所定の非線形トラバースパターンは圧縮される画像データの単一のストリ ームの圧縮の間に変化する ことを特徴とするシステム。 ６０．請求項５０に記載のシステムであって、 前記ピクセルアレイはアレイの限界を有しており、 前記所定の非線形トラバースパターンは、それぞれがスキャンされた前位ピク セルに対応する複数のセグメントを含んでおり、 このシステムは、さらに、 （ａ）前記複数のセグメントから前記アレイの限界の外側にある全てのセグメン トを取り除く手段 を含んでなる ことを特徴とするシステム。 ６１．請求項６０に記載のシステムにおいて、 前記所定の非線形トラバースパターンは経験的に定めたトラバースパターンで あり、前記スキャンされた前位ピクセルをトラバースする手段は経験的に定めら れた要領で前記複数のセグメントがトラバースされるようにする ことを特徴とするシステム。 ６２．請求項６１に記載のシステムにおいて、 トラバースされる初めの２４個のセグメントの前記経験的に定めたパターンは 下記表のものであり、 ここに、「＃」はスキャン中の目標ピクセルであり、１から２４の数字は１から ２４の順にトラバースされる初めの２４個のセグメントに対応している ことを特徴とするシステム。 ６３．請求項６２に記載のシステムにおいて、 トラバースされる次の４１個のセグメントの前記経験的に定められたパターン は下記表のものであり、 ここに、２５から６５の数字は２５から６５の順にトラバースされる次の４１個 のセグメントに対応している ことを特徴とするシステム。 ６４．請求項６１に記載のシステムでにおいて、 前記経験的に定められたパターンにおける複数のセグメントの少なくとも一つ は前記経験的に定められたパターンにおける他のセグメントよりも優先的な扱い を受け、 前記コピートークンは複数のトークン位置を有し、 前記優先的な扱いを受けるセグメントには前記コピートークンの内の前記複数 のトークン位置の中から最適なトークン位置が割り当てられる ことを特徴とするシステム。 ６５．請求項５０に記載のシステムにおいて、 前記画像データのストリームは長方形の画像を含む ことを特徴とするシステム。 ６６．請求項５０に記載のシステムにおいて、 前記一致データストリングはハフマンアルゴリズムに従ってエンコードされる ことを特徴とするシステム。 ６７．請求項５０に記載のシステムであって、 前記エンコードされた画像データのストリームは、それぞれがスキャン中のピ クセルに対応しかつスキャンされた一致前位ピクセルを有しないリテラルトーク ンと、もし一致データストリングに対応するコピートークンがあればそのコピー トークンとを含むトークン化されたデータを含んでおり、 このシステムは、さらに、 （ａ）スキャンされた一致前位ピクセルを有しないスキャン中のピクセルの各々 をリテラルトークンに変換するコンバータと、 （ｂ）もし、一致データストリングがあれば、その各々をコピートークンに変換 するコンバータと、 （ｃ）前記リテラルトークンの各々と前記コピートークンの各々をハフマン圧縮 アルゴリズムを用いてエンコードして前記エンコードされた画像データのストリ ームを得るエンコーダと、 （ｄ）前記エンコードされた画像データのストリームを伝達するトランスミッタ と、 （ｅ）ハフマン解凍アルゴリズムを用いて前記エンコードされた画像データのス トリームをデコードして画像データのデコードされたストリームを得るデコーダ と を含んでなる ことを特徴とするシステム。 ６８．請求項６７に記載のシステムであって、さらに、 （ａ）前記解凍された画像を得るために、前記リテラルトークンの各々と前記コ ピートークンの各々をピクセル成分値に伸張することを含んで前記画像データの デコードされたストリームを伸張する手段 を含んでなるシステム。 ６９．請求項６８に記載のシステムにおいて、 前記エンコードされた画像データのストリームが、同時にデコード及び伸張さ れる ことを特徴とするシステム。 ７０．請求項６８に記載のシステムであって、さらに、 （ａ）前記ピクセル成分値をフィルタして前記解凍された画像を強調するフィル タ を含んでなるシステム。 ７１．請求項５０に記載のシステムであって、 前記解凍された画像は二次元の画像であり、 このシステムは、さらに、 （ａ）前記二次元の画像の両次元において線形補間を実施する手段を含む前記解 凍された画像を再補間する手段 を含んでなる ことを特徴とするシステム。 ７２．請求項５５に記載のシステムにおいて、 前記予め定められた許容差は可変である ことを特徴とするシステム。 ７３．請求項５５に記載のシステムであって、さらに、 （ａ）もし前記コンパレータにより比較されている前記スキャンされた前位ピク セルが、同コンパレータにより比較されている前記目標ピクセルの前記予め定め られた許容差外であれば、前記ピクセルアレイのサーチを続行して他のスキャン された前位ピクセルが前記ピクセルアレイ中の前記目標ピクセルの直後に続く位 置にあるピクセルの前記予め定められた許容差内にあるかどうかを決定する手段 を含んでなるシステム。 ７４．請求項６８に記載のシステムであって、さらに、 （ａ）前記画像データのストリームを副標本化してスプラッシ画像を得るサンプ ラと、 （ｂ）前記スプラッシ画像をエンコードしてエンコードされたスプラッシ画像を 得るエンコーダと、 （ｃ）前記エンコードされたスプラッシ画像を伝達するトランスミッタと、 （ｄ）前記エンコードされたスプラッシ画像をデコードしてデコードされたスプ ラッシ画像を得るデコーダと、 （ｅ）前記エンコードされたデータのストリームがデコード及び伸張されている 間に前記デコードされたスプラッシ画像を表示するディスプレイと を含んでなるシステム。 ７５．請求項７４に記載のシステムであって、 前記スプラッシュ画像は複数の色を含み、 このシステムは、さらに、 （ａ）前記複数の色から最も普通の色を表すプリスプラッシコードを決定する手 段と、 （ｂ）前記最も普通の色を前記デコードされたスプラッシ画像の背景色として表 示するディスプレイと を含んでなる ことを特徴とするシステム。 ７６．それ自体からの少なくともひとつのピクセルを受け入れるストリングに分 割可能なピクセルアレイを含む画像データのストリームを圧縮すると共にこの画 像データのストリームを解凍された画像に解凍するためのシステムであって、 （ａ）前記ピクセルアレイを所定の非線形トラバースパターンでスキャンしてス キャンされた前位ピクセルを得るスキャナと、 （ｂ）前記スキャンされたピクセルを前記スキャンされた前位ピクセルと比較し てスキャンされたピクセルの何れかが前記スキャンされた前位ピクセルと一致す るかどうかを決定するコンパレータと、 （ｃ）スキャンされたピクセルと一致する少なくともひとつのスキャンされた前 位ピクセルと対応するストリングを有するスキャンされた少なくともひとつのピ クセルの各ストリングに対する一致データストリングで、前記スキャンされた一 致前位ピクセ ルと対応する画像データを含む一致データストリングが、もしあれば、それを生 成する手段と、 （ｄ）もし一致データストリングが生成されれば、そのような一致データストリ ングをコピートークンに変換するコンバータと、 （ｅ）スキャンされたピクセルがスキャンされた一致前位ピクセルを有しないな らば、スキャンされたピクセルをリテラルトークンに変換するコンバータと、 （ｆ）前記コピートークンがあればそれをエンコードし、また前記リテラルトー クンをエンコードされたトークンセットにエンコードするエンコーダと、 （ｇ）エンコードされた前記トークンセットを伝達するトランスミッタと、 （ｈ）前記エンコードされたトークンセットをデコードしてデコードされたトー クンセットを得るデコーダと、 （ｉ）前記デコードされたトークンセットを伸張して解凍された画像を得る手段 と を含んでなるシステム。７７．請求項７６に記載のシステムにおいて、 前記コンパレータは、さらに、 （ａ）スキャン中の先頭ピクセルを選択する手段と、 （ｂ）前記所定の非線形トラバースパターンに従って前記スキャンされた前位ピ クセルをトラバースし、前記スキャン中の先頭ピクセルが前記所定の非線形トラ バースパターンに従ってスキャンされた個々の前位ピクセルと比較される手段と 、 （ｃ）もし前記先頭ピクセルに一致する最初のスキャンされた一致 前位ピクセルが見つけだされたら、前記所定の非線形トラバースパターンで前記 スキャンされた前位ピクセルをトラバースすることを停止する手段と、 （ｄ）前記ピクセルアレイ内の前記先頭ピクセルの直後に続く位置に見つけださ れる次のスキャンされるべきピクセルを選択する手段と、 （ｅ）前記次のピクセルを、前記ピクセルアレイ内で前記最初のスキャンされた 一致ピクセルの直後に続く位置において見つけだされる後続のスキャンされた前 位ピクセルと比較する手段と、 （ｆ）前記後続のスキャンされた前位ピクセルが前記次のピクセルと一致するか どうかを決定し、それにより他のスキャンされた一致前位ピクセルが存在するか どうかを決定する手段と、 （ｇ）スキャンされるべき次のピクセルを選択することと、そのような次のピク セルを他の後続のスキャンされた前位ピクセルと比較することを、後続のスキャ ンされた前位ピクセルがそのような次のピクセルと一致しなくなるまで繰り返す 手段とを含む ことを特徴とするシステム。 ７８．請求項７６に記載のシステムであって、 前記一致データストリングをコピートークンに変換する前記コンバータは、さ らに、 （ａ）前記ピクセルアレイ内で前記先頭ピクセルに対比して前記スキャンされた 最初の一致前位ピクセルの位置を表すオフセットを決定する手段と、 （ｂ）前記決定されたスキャンされた一致前位ピクセルの数を表すストリング長 さを決定する手段と、 （ｃ）前記スキャンされた最初の一致ピクセルのオフセットと前記ストリング長 さを結合して前記コピートークンを形成する手段と を含む ことを特徴とするシステム。 ７９．請求項７６に記載のシステムにおいて、 前記コピートークンおよびリテラルトークンはハフマンアルゴリズムに従って エンコードされる ことを特徴とするシステム。 ８０．請求項７６に記載のシステムであって、さらに、 （ａ）全ての可能性のあるコピートークンとリテラルトークンに位置的に対応す るハフマンツリーを生成する手段と、 （ｂ）前記ハフマンツリーを圧縮されたフォーマットにエンコードして圧縮され たハフマンツリーを得るエンコーダと、 （ｃ）前記エンコードされたトークンのセットを伝達する前に前記圧縮されたハ フマンツリーを伝達するトランスミッタと、 （ｄ）前記圧縮されたハフマンツリーをデコード及び伸張するデコータと、 （ｅ）前記ハフマンツリーを用いて前記エンコードされたトークンのセットをデ コードする手段と を含んでなるシステム。 ８１．請求項７６に記載のシステムであって、さらに、 （ａ）前記エンコードされたトークンのセットを複数のブロックに区分けして、 それら複数のブロックを伝達される度に順次デコードする手段と、 （ｂ）前記複数のブロックがデコードされるにつれて、そのブロックの各々を表 示し、各々が前記複数のブロックの一つに対応する前記デコードされた画像の部 分のそれぞれは、それがデコードされた直後に表示され得るようになっているデ ィスプレイユニットと を含んでなるシステム。 ８２．請求項７６に記載のシステムであって、さらに、 （ａ）前記ピクセルアレイをスキャンする前に前記画像データのストリームを副 標本化して前記画像データのストリーム内のデータを減らすサンプラと、 （ｂ）前記解凍された画像を再補間する手段と を含んでなるシステム。 ８３．請求項７６に記載のシステムにおいて、 スキャンされている各ピクセルは許容差を有し、もしスキャンされた前位ピク セルが前記スキャンされているピクセルの許容差内に入っていれば、前記スキャ ンされた前位ピクセルが前記スキャンされているピクセルと一致することとする ことを特徴とするシステム。 ８４．請求項８３に記載のシステムであって、さらに、 （ａ）スキャンされた一致ピクセルの平均品質を示す第二許容差を与える手段を 含んでなるシステム。 ８５．ピクセルアレイを含む画像データのストリームをエンコードされた画像デ ータのストリームに圧縮すると共にこのエンコードされた画像データのストリー ムを解凍された画像に解凍するためのコンピュータプログラムであって、そのコ ンピュータプログラムは、スキャンされる目標ピクセルを示すピクセルポインタ を含むコンピュータシステムにより読み取り可能な媒体上に認識可能に記録され ており、プログラムがコンピュータシステムにより読み取られて実行されると、 前記コンピュータシステムにより （ａ）ピクセルアレイ内の少なくともひとつのピクセルをスキャンして前記ピク セルアレイ内に位置を有するスキャンされた前位ピクセルを得る機能と、 （ｂ）（１）前記ピクセルアレイ内に位置を有する先頭目標ピクセルをスキャン し、 （２）前記スキャンされた前位ピクセルを所定の非線形トラバースパター ンに従ってトラバースし、 （３）トラバースされた前記スキャンされた前位ピクセルの何れかがスキ ャンされた前記先頭目標ピクセルと一致するかを決定して、先頭のスキャンされ た一致前位ピクセルを見つけだし、 （４）前記ピクセルポインタを、前記ピクセルアレイ内で前記先頭の目標 ピクセルの位置の直後に続く位置にあるスキャンされる次の目標ピクセルに進め 、 （５）前記次の目標ピクセルが、前記ピクセルアレイ内で前記先頭のスキ ャンされた一致前位ピクセルの直後に続く位置を有する後続のスキャンされた前 位ピクセルと一致するかどうかを決定し、 （６）ピクセルポインタを進めて、スキャンされた一致前位ピクセルが見 いだされなくなるまで機能ｂ（５）を繰り返して前記ピクセルポインタにより示 されたピクセルと一致する全ての後続のスキャンされた前位ピクセルを見つけだ して、一致データストリングを定義する ことにより、スキャンされるピクセルのストリングと一致する一致データス トリングを求めて、前記スキャンされた前位ピクセルをサーチする機能と、 （ｃ）前記ピクセルアレイ内における前記先頭の目標ピクセルに関する、前記先 頭のスキャンされた一致前位ピクセルの位置を表すオフセットを決定する機能と 、 （ｄ）前記一致データストリング内のスキャンされた一致前位ピクセルの数であ る前記一致データストリングのストリング長を決定する機能と、 （ｅ）前記一致データストリングを、前記先頭のスキャンされた一致ピクセルの オフセットと前記一致データストリングのストリング長を含むコピートークンに 変換する機能と、 （ｆ）前記コピートークンをエンコードする機能と を実行するようにコンピュータシステムの構成を配置するように適合させてなる コンピュータプログラム。８６．請求項８５に記載のコンピュータプログラムであって、さら に （ａ）前記一致データストリングを見つけようと前記スキャンされた前位ピクセ ルの中をサーチする前に、前記ピクセルアレイを副標本化して画像データのスト リーム内のデータを減少させる機能 を実行するコンピュータプログラム。 ８７．請求項８５に記載のコンピュータプログラムであって、 前記ピクセルアレイ内のそれぞれのピクセルは、スキャンされた一致前位ピク セルが見つけだされたときを決定するのに使用される予め定められた許容差を有 していて、スキャンされた前位ピクセルが目標ピクセルと一致するかどうかを決 定するために、 このコンピュータプログラムが、さらに、 （ａ）スキャン中の目標ピクセルをスキャンされた前位ピクセルと比較する機能 と、 （ｂ）前記スキャンされた前位ピクセルが前記目標ピクセルの前記予め定められ た許容差内にあるかどうかを決定する機能と、 （ｃ）前記スキャンされた前位ピクセルが前記目標ピクセルの前記予め定められ た許容差内にあるときは前記スキャンされた前位ピクセルをスキャンされた一致 ピクセルと見なす機能と を実行する ことを特徴とするコンピュータプログラム。 ８８．請求項８５に記載のコンピュータプログラムにおいて、 前記所定の非線形トラバースパターンは圧縮される個々の画像データのストリ ームごとに画像トラバース長さを含む固定長を有しており、 前記画像トラバース長さは画像ごとに異なっている ことを特徴とするコンピュータプログラム。 ８９．請求項８５に記載のコンピュータプログラムであって、 前記ピクセルアレイはアレイの限界を有し、前記所定の非線形トラバースパタ ーンは複数のセグメントを有し、その複数のセグメントのそれぞれはスキャンさ れた前位ピクセルに対応しており、 このコンピュータプログラムは、さらに、 （ａ）前記複数のセグメントから前記アレイの限界の外側にある全てのセグメン トを取り除く機能 を実行する ことを特徴とするコンピュータプログラム。 ９０．請求項８５に記載のコンピュータプログラムであって、 前記一致データストリングはハフマンアルゴリズムに従ってエンコードされる ことを特徴とするコンピュータプログラム。 ９１．請求項８５に記載のコンピュータプログラムにおいて、 前記エンコードされた画像データのストリームは、それぞれがスキャン中のピ クセルに対応しかつスキャンされた一致前位ピクセルを有しないリテラルトーク ンと、もし一致データストリングに対応するコピートークンがあればそのコピー トークンとを含むトークン化されたデータを含んでおり、 このコンピュータプログラムは、さらに、 （ａ）スキャンされた一致前位ピクセルを有しないスキャン中の各ピクセルの各 々をリテラルトークンに変換する機能と、 （ｂ）もし、一致データストリングがあれば、その各々をコピートークンに変換 する機能と、 （ｃ）前記リテラルトークンの各々と前記コピートークンの各々をハフマン圧縮 アルゴリズムを用いてエンコードして前記エンコードされた画像データのストリ ームを得る機能と、 （ｄ）前記エンコードされた画像データのストリームを伝達する機能と、 （ｅ）前記エンコードされた画像データのストリームをハフマン解凍アルゴリズ ムを用いてデコードして画像データのデコードされたストリームを得る機能と を実行する ことを特徴とするコンピュータプログラム。 ９２．請求項９１に記載のコンピュータプログラムであって、さらに、 （ａ）前記解凍された画像を得るために、前記リテラルトークンの各々と前記コ ピートークンの各々をピクセル成分値に伸張することを含んで前記画像データの デコードされたストリームを伸張する機能 を実行するコンピュータプログラム。 ９３．請求項９２に記載のコンピュータプログラムにおいて、 前記エンコードされた画像データのストリームが、同時にデコード及び伸張さ れる ことを特徴とするコンピュータプログラム。 ９４．請求項９２に記載のコンピュータプログラムであって、さらに、 （ａ）前記画像データのストリームを副標本化してスプラッシ画像を得る機能と 、 （ｂ）前記スプラッシ画像をエンコードしてエンコードされたスプラッシ画像を 得る機能と、 （ｃ）前記エンコードされたスプラッシ画像を伝達する機能と、 （ｄ）前記エンコードされたスプラッシ画像をデコードしてデコードされたスプ ラッシ画像を得る機能と、 （ｅ）前記エンコードされたデータのストリームがデコード及び伸張されている 間に前記デコードされたスプラッシ画像を表示する機能と を実行するコンピュータプログラム。 ９５．それ自体からの少なくともひとつのピクセルを受け入れるストリングに分 割可能なピクセルアレイを含む画像データのストリームを圧縮すると共にこの画 像データのストリームを解凍された画像に解凍するためのコンピュータプログラ ムであって、そのコンピュータプログラムはコンピュータシステムにより読み取 り可能な媒体上に認識可能に記録されており、プログラムがコンピュータシステ ムにより読み取られて実行されると、前記コンピュータシステムにより （ａ）前記ピクセルアレイを所定の非線形トラバースパターンに従ってスキャン してスキャンされた前位ピクセルを得る機能と、 （ｂ）前記スキャン中のピクセルを前記スキャンされた前位ピクセルと比較して スキャン中のピクセルの何れかが前記スキャンさ れた前位ピクセルと一致するかどうかを決定する機能と、 （ｃ）スキャンされたピクセルと一致する少なくともひとつのスキャンされた前 位ピクセルと対応するストリングを有するスキャンされた少なくともひとつのピ クセルの各ストリングに対する一致データストリングで、前記スキャンされた一 致前位ピクセルと対応する画像データを含む一致データストリングを生成する機 能と、 （ｄ）もし一致データストリングが生成されれば、そのような一致データストリ ングをコピートークンに変換する機能と、 （ｅ）スキャンされたピクセルがスキャンされた一致前位ピクセルを有しないな らば、スキャンされたピクセルをリテラルトークンに変換する機能と、 （ｆ）前記コピートークンがあればそれをエンコードし、また前記リテラルトー クンをエンコードされたトークンセットにエンコードする機能と、 （ｇ）エンコードされた前記トークンセットを伝達する機能と、 （ｈ）前記エンコードされたトークンセットをデコードしてデコードされたトー クンセットを得る機能と、 （ｉ）前記デコードされたトークンセットを伸張して解凍された画像を得る手段 と を実行するようにコンピュータシステムの構成を配置するように適合させてなる コンピュータプログラム。９６．請求項９５に記載のコンピュータプログラムであって、 前記スキャン中のピクセルを比較して決定する機能は、さらに、 （ａ）スキャンされている先頭ピクセルを選択する機能と、 （ｂ）前記所定の非線形トラバースパターンに従って前記スキャンされた前位ピ クセルをトラバースし、前記スキャンされている先頭ピクセルが前記所定の非線 形トラバースパターンに従ってスキャンされた個々の前位ピクセルと比較される 機能と、 （ｃ）もし前記先頭ピクセルに一致する最初のスキャンされた一致前位ピクセル が見つけだされたら、前記所定の非線形トラバースパターンで前記スキャンされ た前位ピクセルをトラバースすることを停止する機能と、 （ｄ）前記ピクセルアレイ内の前記先頭ピクセルの直後に続く位置に見つけださ れる次のスキャンされるべきピクセルを選択する機能と、 （ｅ）前記次のピクセルを、前記ピクセルアレイ内で前記最初のスキャンされた 一致前位ピクセルの直後に続く位置に見つけだされる後続のスキャンされた前位 ピクセルと比較する機能と、 （ｆ）前記後続のスキャンされた前位ピクセルが前記次のピクセルと一致するか どうかを決定し、それにより他のスキャンされた一致前位ピクセルが存在するか どうかを決定する機能と、 （ｇ）スキャンされるべき次のピクセルを選択することと、そのような次のピク セルを他の後続のスキャンされた前位ピクセルと比較することを、後続のスキャ ンされた前位ピクセルが次のピクセルと一致しなくなるまで繰り返す機能と を含んでなるコンピュータプログラム。 ９７．請求項９６に記載のコンピュータプログラムであって、 前記一致データストリングをコピートークンに変換する前記機能 は、さらに、 （ａ）前記ピクセルアレイ内で前記先頭ピクセルに対比して前記スキャンされた 最初の一致ピクセルの位置を表すオフセットを決定する機能と、 （ｂ）前記決定されたスキャンされた一致前位ピクセルの数を表すストリング長 さを決定する機能と、 （ｃ）前記スキャンされた最初の一致前位ピクセルのオフセットと前記ストリン グ長さを結合して前記コピートークンを形成する機能と を含んでなるコンピュータプログラム。 ９８．請求項９５に記載のコンピュータプログラムであって、さらに、 （ａ）全ての可能性のあるコピートークンとリテラルトークンに位置的に対応す るハフマンツリーを生成する機能と、 （ｂ）前記ハフマンツリーを圧縮されたフォーマットにエンコードして圧縮され たハフマンツリーを得る機能と、 （ｃ）前記エンコードされたトークンのセットを伝達する前に前記圧縮されたハ フマンツリーを伝達する機能と、 （ｄ）前記圧縮されたハフマンツリーをデコード及び伸張する機能と、 （ｅ）前記ハフマンツリーを用いて前記エンコードされたトークンのセットをデ コードする機能と を実行するコンピュータプログラム。 ９９．請求項９５に記載のコンピュータプログラムであって、さら に、 （ａ）前記エンコードされたトークンのセットを複数のブロックに区分けして、 それら複数のブロックを伝達される度に順次デコードするステップと、 （ｂ）前記複数のブロックがデコードされるにつれて、そのブロックの各々を表 示し、各々が前記複数のブロックの一つに対応する前記デコードされた画像の部 分のそれぞれは、それがデコードされた直後に表示され得るようにする機能と を実行するコンピュータプログラム。 １００．請求項９５に記載のコンピュータプログラムにおいて、 スキャンされている各ピクセルは許容差を有し、もしスキャンされた前位ピク セルが前記スキャンされているピクセルの許容差内に入っていれば、前記スキャ ンされた前位ピクセルが前記スキャンされているピクセルと一致することとする ことを特徴とするコンピュータプログラム。 １０１．入力データストリングをからなる２またはそれ以上のグループの複数の 入力データセグメントを含む入力データストリームを圧縮する方法であって、 （ａ）入力データストリームを読み込んで、前位データストリングからなる２ま たはそれ以上のグループの複数の前位データセグメントを含む前位データを得る ステップと、 （ｂ）前記前位データを、それぞれ前位データストリングを含み前記入力データ ストリームからの入力データストリングと一致す る最長の一致前位データストリングを求めて、所定の非線形トラバースパターン でサーチするステップと、 （ｃ）前記前位データ内に最長の一致前位データストリングが見いだせたらば、 その最長の一致前位データストリングを圧縮して圧縮ストリングを得ると共にこ の圧縮ストリングをコピートークンとしてエンコードするステップと、 （ｄ）一致前位データセグメントを有しない入力データセグメントについて、そ のような入力データセグメントをリテラルトークンとしてエンコードするステッ プと、 （ｅ）前記コピートークンがあればそれを、またリテラルトークンを出力するス テップと を含んでなる方法。１０２．請求項１０１に記載の方法において、 前記入力データストリームは複数のピクセルを有する画像を含み、 前記複数の前位データセグメントは前記画像内に複数の前位ピクセルを含むと ともに、前記複数の入力セグメントは前記画像内に複数の目標ピクセルを含み、 前記所定の非線形トラバースパターンは前位ピクセルと選択された目標ピクセ ルとの一致頻度に基づいて経験的に決定された変化するパターンである ことを特徴とする方法。 １０３．請求項１０１に記載の方法において、 前記目標ピクセルは許容差レベルを有し、 前位ピクセルのストリングは、もし前記前位ピクセルのストリン グが前記目標ピクセルのストリングの前記許容差レベル内にあれば、前記目標ピ クセルのストリングに一致するものとみられる ことを特徴とする方法。 １０４．入力データストリングをからなる２またはそれ以上のグループの複数の 入力データセグメントを含む入力データストリームを圧縮するシステムであって 、 （ａ）入力データストリームを読み込んで、前位データストリングからなる２ま たはそれ以上のグループの複数の前位データセグメントを含む前位データを得る 手段と、 （ｂ）前記前位データを、それぞれ前位データストリングを含み前記入力データ ストリームからの入力データストリングと一致する最長の一致前位データストリ ングを求めて、所定の非線形トラバースパターンでサーチする手段と、 （ｃ）前記前位データ内に最長の一致前位データストリングが見いだせたらば、 その最長の一致前位データストリングを圧縮して圧縮ストリングを得る圧縮手段 及びこの圧縮ストリングをコピートークンとしてエンコードするエンコーダと、 （ｄ）一致前位データセグメントを有しない入力データセグメントについて、そ のような入力データセグメントをリテラルトークンとしてエンコードするエンコ ーダと、 （ｅ）前記コピートークンがあればそれを、またリテラルトークンを出力するポ ートと を含んでなるシステム。 １０５．ある順序を有している複数のデータセグメントを含むデー タを圧縮する方法で、前記複数のデータセグメントは目標セグメントと前位セグ メントを含み、前記前位セグメントは前記複数のデータセグメントの順序内で前 記目標セグメントに先行しているデータを圧縮する方法であって、 （ａ）先頭の目標セグメントを選択するステップと、 （ｂ）前記前位セグメントを所定の非線形トラバースパターンに従ってトラバー スするステップと、 （ｃ）前記先頭の目標セグメントで始まる目標セグメントのストリングと一致す る、前記所定の非線形トラバースパターン内にある先頭の一致前位セグメントを 有する最長の一致する前位セグメントのストリングを見つけだすステップと を含んでなる方法。１０６．請求項１０５に記載の方法において、 前記ストリングを見つけだすステップは、 （ａ）前記先頭の一致前位セグメントから始めて、前記前位セグメントを第一の 線形トラバースパスでトラバースするステップと、 （ｂ）前記先頭の目標セグメントから始めて、第二の線形トラバースパスに沿っ て各々が第一の線形トラバースパスに沿う対応する前位セグメントを有する前記 目標セグメントを、前記第二の線形トラバースパスでトラバースするステップと 、 （ｃ）前記第二の線形トラバースパスに沿って存在する各目標セグメントを前記 第一の線形トラバースパスに沿って存在する前記対応する前位セグメントと比較 し、各目標セグメントが前記対応する前位セグメントと一致するかどうかを決定 するス テップと、 （ｄ）もし、目標セグメントが前記対応する前位セグメントと一致しないならば 、前記前位セグメントと目標セグメントのトラバースを停止し、前記先頭の一致 前位セグメントで始る一致前位セグメントの数は第一の一致ストリング長を有す る第一の一致ストリングを含むこととなるステップと を含んでいる ことを特徴とする方法。 １０７．請求項１０６に記載の方法であって、 前記見つけだすステップは、さらに、 （ａ）前記停止するステップの後に、前記先頭の一致前位セグメントに先行して いる前記前位セグメントを前記所定の非線形トラバースパターンでトラバースし 続けるステップと、 （ｂ）もし、前記非線形トラバースパターンの範囲内に前記先頭の目標セグメン トと一致する次の一致前位セグメントがあれば、それを見つけだすステップと、 （ｃ）前記次の一致前位セグメントから始めて前記前位セグメントを第三の線形 トラバースパスでトラバースするステップと、 （ｄ）前記先頭の目標セグメントから始めて、且つ前記第二の線形トラバースパ スに沿って前記第三の線形トラバースパスに沿って対応する前位セグメントを有 する前記目標セグメントを前記第二の線形トラバースパスでトラバースするステ ップと、 （ｅ）前記第二の線形トラバースパスに沿って存在する各目標セグメントを前記 第三の線形トラバースパスに沿って存在する前記対応する前位セグメントと比較 し、各目標セグメントが前 記対応する前位セグメントに一致するかどうかを決定するステップと、 （ｆ）もし、目標セグメントが前記対応する前位セグメントに一致しないならば 、前記前位セグメントと目標セグメントのトラバースを停止し、前記次の一致前 位セグメントで始る一致前位セグメントの数が第二の一致ストリング長を有する 第二の一致ストリングを含むこととなるステップと、 （ｇ）前記第一の一致ストリングの前記第一の一致ストリング長を前記第二の一 致ストリングの前記第二の一致ストリング長と比較し、いずれが長いかを決定す るステップと、 （ｈ）前記の長い方の長さを有する一致ストリングを前位セグメントの最長一致 ストリングとして定義するステップと を含んでなる方法。 １０８．請求項１０５に記載の方法において、 前記最長一致ストリングを見つけだすステップは、前記前位セグメントに許容 レベルを適用し、前位セグメントが目標セグメントに一致するかどうかを決定す るステップを含む ことを特徴とする方法。 １０９．請求項１０５に記載の方法において、 前記所定の非線形トラバースパターンは固定した長さを有することを特徴とす る方法。 １１０．請求項１０５に記載の方法において、 前記所定の非線形トラバースパターンは固定した長さを有し、前 記所定の非線形トラバースパターンによりトラバースされる最初の２４個のデー タセグメントは下記表のものであり、 ここに、「＃」は前記先頭の目標セグメントを示し、１から２４の数字は１から ２４の順に、トラバースされる最初の２４個のデータを示している ことを特徴とする方法。 １１１．請求項１０５に記載の方法において、 前記データは画像データを含み、前記複数のデータセグメントは複数のピクセ ルを含んでいる ことを特徴とする方法。 １１２．ある順序を有している複数のタセグメントを含むデータを圧縮するシス テムで、前記複数のセグメントは目標セグメントと前位セグメントを含み、前記 前位セグメントは前記複数のセグメントの順序内で前記目標セグメントに先行し ているデータを圧縮するシステムであって、 （ａ）先頭の目標セグメントを選択する手段と、 （ｂ）前記前位セグメントを所定の非線形トラバースパターンに従 ってトラバースする手段と、 （ｃ）前記先頭の目標セグメントで始まる目標セグメントのストリングと一致す る、前記所定の非線形トラバースパターン内にある先頭の一致前位セグメントを 有する最長の一致する前位セグメントのストリングを見つけだす手段と を含んでなるシステム。１１３．請求項１１２に記載のシステムにおいて、 前記見つけだす手段は、 （ａ）前記先頭の一致前位セグメントから始めて、前記前位セグメントを第一の 線形トラバースパスでトラバースする手段と、 （ｂ）前記先頭の目標セグメントから始めて、第二の線形トラバースパスに沿っ て各セグメントが前記第一の線形トラバースパスに沿う対応する前位セグメント を有する前記目標セグメントを、前記第二の線形トラバースパスでトラバースす る手段と、 （ｃ）前記第二の線形トラバースパスに沿って存在する各目標セグメントを前記 第一の線形トラバースパスに沿って存在する前記対応する前位セグメントと比較 し、各目標セグメントが前記対応する前位セグメントと一致するかどうかを決定 する手段と、 （ｄ）もし、目標セグメントが前記対応する前位セグメントと一致しないならば 、前記前位セグメントと目標セグメントのトラバースを停止し、前記先頭の一致 前位セグメントで始る一致前位セグメントの数は第一の一致ストリング長を有す る第一の一致ストリングを含むこととなる手段と を含んでいる ことを特徴とするシステム。 １１４．請求項１１３に記載のシステムであって、 前記見つけだす手段は、さらに、 （ａ）前記停止する手段の作動後に、前記先頭の一致前位セグメントに先行して いる前記前位セグメントを前記所定の非線形トラバースパターンでトラバースし 続ける手段と、 （ｂ）もし、前記非線形トラバースパターンの範囲内に前記先頭の目標セグメン トと一致する次の一致前位セグメントがあれば、それを見つけだす手段と、 （ｃ）前記次の一致前位セグメントから始めて、前記前位セグメントを第三の線 形トラバースパスでトラバースする手段と、 （ｄ）前記先頭目標セグメントから始めて、前記第三の線形トラバースパスに沿 って対応する前位セグメントを前記第二の線形トラバースパスに沿って有する前 記目標セグメントを前記第二の線形トラバースパスでトラバースする手段と、 （ｅ）前記第二の線形トラバースパスに沿って存在する各目標セグメントを前記 第三の線形トラバースパスに沿って存在する前記対応する前位セグメントと比較 し、各目標セグメントが前記対応する前位セグメントに一致するかどうかを決定 する手段と、 （ｆ）もし、目標セグメントが前記対応する前位セグメントに一致しないならば 、前記前位セグメントと目標セグメントのトラバースを停止し、前記次の一致前 位セグメントで始る一致前位セグメントの数が第二の一致ストリング長を有する 第二の 一致ストリングを含むこととなる手段と、 （ｇ）前記第一の一致ストリングの前記第一の一致ストリング長を前記第二の一 致ストリングの前記第二の一致ストリング長と比較し、いずれが長いかを決定す る手段と、 （ｈ）前記の長い方の長さを有する前記一致ストリングを前位セグメントの最長 一致ストリングとして定義する手段と を含んでなる ことを特徴とするシステム。 １１５．請求項１１２に記載のシステムにおいて、 前記最長一致ストリングを見つけだす手段は、前記前位セグメントに許容レベ ルを適用し、前位セグメントが目標セグメントに一致するかどうかを決定する手 段を含む ことを特徴とするシステム。 １１６．請求項１１２に記載のシステムにおいて、 前記所定の非線形トラバースパターンは固定した長さを有することを特徴とす るシステム。 １１７．請求項１１２に記載のシステムにおいて、前記所定の非線形トラバース パターンは固定したパターンを有し、前記所定の非線形トラバースパターンによ りトラバースされる最初の２４個のデータセグメントは下記表のものであり、 ここに、「＃」は前記先頭の目標セグメントを示し、１から２４の数字は１から ２４の順に、トラバースされる前記最初の２４個のデータを示している ことを特徴とするシステム。 １１８．請求項１１２に記載のシステムにおいて、 前記データは画像データを含み、前記複数のデータセグメントは複数のピクセ ルを含んでいる ことを特徴とするシステム。 １１９．ある順序を有している複数のタセグメントを含むデータを圧縮するコン ピュータプログラムで、前記複数のセグメントは目標セグメントと前位セグメン トを含み、前記前位セグメントは前記複数のセグメントの順序内で前記目標セグ メントに先行しているデータを圧縮するコンピュータプログラムであって、その コンピュータプログラムはコンピュータシステムにより読み取り可能な媒体上に 認識可能に記録されており、プログラムがコンピュータシステムにより読み取ら れて実行されると、前記コンピュータシステムにより （ａ）先頭の目標セグメントを選択する機能と、 （ｂ）前記前位セグメントを所定の非線形トラバースパターンに従ってトラバー スする機能と、 （ｃ）前記先頭の目標セグメントで始まる目標セグメントのストリングと一致す る、前記所定の非線形トラバースパターン内にある先頭の一致前位セグメントを 有する最長の一致する前位セグメントのストリングを見つけだす機能と を実行するようにコンピュータシステムの構成を配置するように適合させてなる コンピュータプログラム。１２０．請求項１１９に記載のコンピュータプログラムにおいて、前記見つけだ す機能は、 （ａ）前記先頭の一致前位セグメントから始めて、前位セグメントを第一の線形 トラバースパスでトラバースする機能と、 （ｂ）前記先頭の目標セグメントから始めて、第二の線形トラバースパスに沿っ て各セグメントが前記第一の線形トラバースパスに沿う対応する前位セグメント を有する前記目標セグメントを、前記第二の線形トラバースパス内トラバースす る機能と、 （ｃ）前記第二の線形トラバースパスに沿って存在する各目標セグメントを前記 第一の線形トラバースパスに沿って存在する前記対応する前位セグメントと比較 し、各目標セグメントが前記対応する前位セグメントと一致するかどうかを決定 する機能と、 （ｄ）もし、目標セグメントが前記対応する前位セグメントと一致しないならば 、前記前位セグメントと目標セグメントのトラバースを停止し、前記先頭の一致 前位セグメントで始る一致 前位セグメントの数は第一の一致ストリング長を有する第一の一致ストリングを 含むこととなる機能と を含んでいる ことを特徴とするコンピュータプログラム。 １２１．請求項１２０に記載のコンピュータプログラムであって、 前記見つけだす機能は、さらに、 （ａ）前記停止する機能の作動後に、前記先頭の一致前位セグメントに先行して いる前記前位セグメントを前記所定の非線形トラバースパターンによりトラバー スし続ける機能と、 （ｂ）もし、前記非線形トラバースパターンの範囲内に前記先頭の目標セグメン トと一致する次の一致前位セグメントがあれば、それを見つけだす機能と、 （ｃ）前記次の一致前位セグメントから始めて、前記前位セグメントを第三の線 形トラバースパスでトラバースする機能と、 （ｄ）前記先頭の目標セグメントから始めて、前記第三の線形トラバースパスに 沿って対応する前位セグメントを前記第二の線形トラバースパスに沿って有する 前記目標セグメントを前記第二の線形トラバースパスでトラバースする機能と、 （ｅ）前記第二の線形トラバースパスに沿って存在する各目標セグメントを前記 第三の線形トラバースパスに沿って存在する前記対応する前位セグメントと比較 し、各目標セグメントが前記対応する前位セグメントに一致するかどうかを決定 する機能と、 （ｆ）もし、目標セグメントが前記対応する前位セグメントに一致しないならば 、前記前位セグメントと目標セグメントのトラ バースを停止し、前記次の一致前位セグメントで始る一致前位セグメントの数が 第二の一致ストリング長を有する第二の一致ストリングを含むこととなる機能と 、 （ｇ）前記第一の一致ストリングの前記第一の一致ストリング長を前記第二の一 致ストリングの前記第二の一致ストリング長と比較し、いずれが長いかを決定す る機能と、 （ｈ）前記の長い方の長さを有する前記一致ストリングを前位セグメントの最長 一致ストリングとして定義する機能と を含んでなる ことを特徴とするコンピュータプログラム。

Claims (1)

1. 【特許請求の範囲】 １．複数の目標ピクセルおよび複数の前位ピクセルを有するピクセルアレイで、 それぞれの前位ピクセルはそのピクセルアレイ内でそれぞれの目標ピクセルより 前の位置にあるようなピクセルアレイを有する原画像を圧縮する方法であって、 （ａ）（１）所定の非線形トラバースパターンに従って前記ピクセルアレイをト ラバースして、ひとつの目標ピクセルと一致するひとつの前位ピクセルが有れば 、それを見つけだし、 （２）もし、そのような一致する前位ピクセルが見つけだされたら、当該 一致した目標ピクセルおよび前位ピクセルから線形的に次々たどりながら対応す る目標ピクセルと前位ピクセルを比較していって、一致する前位ピクセルストリ ングが有る場合、それを見つけだし、 （３）ステップ（１）および（２）を繰り返して、最長の一致前位ピクセ ルストリングを見つけだし、 （４）それぞれのそのような最長の一致前位ピクセルストリングを表す圧 縮表現としてコピートークンを生成し、 （５）一致前位ピクセルを有しない目標ピクセルのそれぞれについてリテ ラルトークンを生成する ことを繰り返し行うことにより原画像を圧縮して圧縮画像を得るステップ を含んでなる方法。 ２．複数の目標ピクセルおよび複数の前位ピクセルを有するピクセルアレイで、 それぞれの前位ピクセルはそのピクセルアレイ内でそ れぞれの目標ピクセルより前の位置にあるようなピクセルアレイを有する原画像 を圧縮して、圧縮画像を得る方法であって、 （ａ）所定の非線形トラバースパターンに従って前記ピクセルアレイを繰り返し トラバースして、ひとつの目標ピクセルストリングと一致するひとつの最長の一 致前位ピクセルストリングが有れば、それを見つけだすステップと、 （ｂ）そのような一致した目標ピクセルストリングを表す圧縮表現としてそのよ うな最長の一致前位ピクセルストリングを参照するコピートークンを生成するス テップと、 （ｃ）一致する前位ピクセルを有しない目標ピクセルのそれぞれについてリテラ ルトークンを生成するステップと を含んでなる方法。 ３．請求項１または２に記載の方法であって、さらに、 ハフマン符号化アルゴリズムを使用して前記圧縮画像をエンコードすることに より前記圧縮画像をさらに圧縮するステップを含んでなる方法。 ４．請求項３に記載の方法であって、 全ての可能なコピートークンおよび全ての可能なリテラルトークンがひとつの トークンセットを形成していて、さらに、 （ａ）そのトークンセットについてハフマンツリーを生成するステップと、 （ｂ）そのハフマンツリーを出力するステップと、 （ｃ）そのハフマンツリーを出力した後に前記圧縮画像を出力するステップと を含んでなる方法。 ５．請求項４に記載の方法であって、さらに、 （ａ）前記ハフマンツリーを出力する前にハフマンツリーをひとつの圧縮フォー マットにエンコードして、圧縮されたハフマンツリーを得るステップと、 （ｂ）そのハフマンツリーを使用して前記エンコードされた圧縮画像をデコード するステップと、 （ｃ）そのデコードされた圧縮画像を解凍して原画像を得るステップと を含んでなる方法。 ６．請求項１に記載の方法であって、さらに、 （ａ）原画像を圧縮する前に原画像を部分標本化するステップを含んでなる方法 。 ７．請求項１に記載の方法において、 前記所定の非線形トラバースパターンは固定長を有することを特徴とする方法 。 ８．請求項６に記載の方法において、 前記所定の非線形トラバースパターンは経験的に定められることを特徴とする 方法。 ９．請求項８に記載の方法において、 前記所定の非線形トラバースパターンは複数のピクセルオフセッ トを有し、その初めの２４個は下記表のものであり、 ここに、「＃」はエンコード中のピクセル位置を示し、１から２４の数字は初め の２４個のピクセルオフセットをその順に示していることを特徴とする方法。 １０．請求項１または２に記載の方法において、 各最長の一致データストリングは、目標ピクセルのストリングに対応する一致 ピクセルのストリングを有し、 最長の一致データストリングを見つける際に、ピクセルアレイ内の各ピクセル は許容差を有していて、もし一致ピクセルのストリング内の一致ピクセルのそれ ぞれが目標ピクセルのストリング内の対応目標ピクセルの許容差範囲内に入って いれば、最長一致データストリング内の一致ピクセルのストリングは目標ピクセ ルのストリングに一致するとみなされる ことを特徴とする方法。 １１．複数の目標ピクセルおよび複数の前位ピクセルを有するピクセルアレイで 、それぞれの前位ピクセルはそのピクセルアレイ内でそれぞれの目標ピクセルよ り前の位置にあるようなピクセルアレイを有する原画像を圧縮して、圧縮画像を 得るシステムであって、 （ａ）所定の非線形トラバースパターンに従って前記ピクセルアレイを繰り返し トラバースして、ひとつの目標ピクセルストリングと一致するひとつの最長の一 致前位ピクセルストリングが有れば、それを見つけだす手段と、 （ｂ）そのような一致した目標ピクセルストリングを表す圧縮表現としてそのよ うな最長の一致前位ピクセルストリングを参照するコピートークンを生成する手 段と、 （ｃ）一致する前位ピクセルを有しない目標ピクセルのそれぞれについてリテラ ルトークンを生成する手段と を備えてなるシステム。 １２．ピクセルアレイを有する原画像を圧縮して圧縮画像を得るコンピュータプ ログラムであって、 そのプログラムはコンピュータシステムにより読み取り可能な媒体上に認識可 能に記録されており、プログラムがコンピュータシステムにより読み取られて実 行されると、 （ａ）所定の非線形トラバースパターンに従って前記ピクセルアレイを繰り返し トラバースして、ひとつの目標ピクセルストリングと一致するひとつの最長の一 致前位ピクセルストリングが有れば、それを見つけだす機能と、 （ｂ）そのような一致した目標ピクセルストリングを表す圧縮表現としてそのよ うな最長の一致前位ピクセルストリングを参照するコピートークンを生成する機 能と、 （ｃ）一致する前位ピクセルを有しない目標ピクセルのそれぞれについてリテラ ルトークンを生成する機能と を実行するようにコンピュータシステムの構成を配置するように適 合させてなるコンピュータプログラム。 １３．先頭の目標ピクセルおよび複数の前位ピクセルを有するピクセルアレイで 、それぞれの前位ピクセルはそのピクセルアレイ内でそれぞれの目標ピクセルの 前に位置しているピクセルアレイよりなる画像データを圧縮する方法であって、 （ａ）前記画像データを逆向き非線形トラバースパターンに従って前記ピクセル アレイ内で逆向きにトラバースするステップと、 （ｂ）前記先頭の目標ピクセルと一致する、ひとつの先頭の一致前位ピクセルが があれば、それを見つけだすステップと、 （ｃ）もしひとつの先頭の一致前位ピクセルが見つけだされたら、前記ピクセル アレイ内で前向きの線形トラバースパターンに従って、前記先頭の目標ピクセル に続く複数のピクセルと前記先頭の一致前位ピクセルに続く複数のピクセルの両 方を、前記先頭の目標ピクセルに続く目標ピクセルが前記先頭の一致前位ピクセ ルに続く前位ピクセルと一致しなくなるまでトラバースして一致データストリン グを定義するステップと、 （ｄ）前記非線形トラバースパターン内の前記画像データをトラバースすること を続けて前記先頭の目標ピクセルと一致する他の前位ピクセルを見つけだすこと を試みるステップと、 （ｅ）もし他の一致前位ピクセルが見つけだされたらば、他の一致データストリ ングをステップ（ｃ）に従って定義するステップと、 （ｆ）ステップ（ｄ）と（ｅ）を繰り返してすべての一致データストリングを定 義するステップと、 （ｇ）前記一致データストリングの何れが最長の一致データストリ ングであるかを決定するステップと、 （ｈ）前記最長の一致データストリングをコピートークンとしてエンコードする ステップと を含んでなる方法。 １４．複数の目標ピクセルおよび複数の前位ピクセルを含んでおり、それぞれの 前位ピクセルはピクセルアレイ内で目標ピクセルより前の位置にあるようなピク セルアレイよりなる画像データを圧縮する方法であって、 （ａ）前記前位ピクセルを、先頭の目標ピクセルに関して所定の位置を有する最 初の前位ピクセルのところで起こる始まりと、前記先頭の目標ピクセルに関して 他の所定の位置を有する最後の前位ピクセルのところで起こる終わりを有する所 定の非線形トラバースパターンに従ってトラバースするステップと、 （ｂ）前記所定の非線形トラバースパターンに従ってトラバースされた前位ピク セルの中から、前記先頭の目標ピクセルと一致する先頭の一致前位ピクセルがあ れば、それを見つけだすステップと （ｃ）もしひとつの先頭の一致前位ピクセルが見つけだされたら、線形トラバー スパスに従って、前記先頭の目標ピクセルに後続する目標ピクセルと前記先頭の 一致前位ピクセルに後続する前位ピクセルの両方を、各後続の目標ピクセルに前 記線形トラバースパスに沿って後続の前位ピクセルを対応させながらトラバース するステップと、 （ｄ）それぞれの続く目標ピクセルを対応する前位ピクセルと比較して、続く目 標ピクセルが対応する続く前位ピクセルと一致し ないことが見つけだされるまで前記線形トラバースパス内のトラバースを続けて 非一致前位ピクセルを見つけだすステップと、 （ｅ）一致データストリングを、前記先頭の一致前位ピクセルで始まり前記ピク セルアレイ内で前記非一致前位ピクセルの直前の前位ピクセルで終わるピクセル のストリングとして定義するステップと、 （ｆ）前記非線形トラバースパターン内の前記前位ピクセルのトラバースを、前 記非線形トラバースパターン内の前記先頭の一致前位ピクセルに先行する前位ピ クセルで開始して続けて、前記先頭の目標ピクセルと一致する他の前位ピクセル を見つけ出すことを試みるステップと、 （ｇ）もし他の一致前位ピクセルが見つけだされたらば、ステップ（ｃ）から（ ｅ）を繰り返して他の一致データストリングを定義するステップと、 （ｈ）ステップ（ｆ）と（ｇ）を最後の前位ピクセルに達するまで繰り返すステ ップと、 （ｉ）もしただひとつの一致データストリングだけが定義されたらば、そのひと つの一致データストリングを最長の一致データストリングとするステップと、 （ｊ）もし複数の一致データストリングが定義されたらば、この複数の一致デー タストリングの何れが最長の一致データストリングであるかを決定するステップ と、 （ｋ）前記最長の一致データストリングをコピートークンとしてエンコードする ステップと を含んでなる方法。 １５．スキャンされている目標ピクセルを示すピクセルポインタを含むデータ圧 縮システム内においてピクセルアレイを含む画像データのストリームをエンコー ドされた画像データのストリームに圧縮すると共にこのエンコードされた画像デ ータのストリームを解凍された画像に解凍する方法であって、 （ａ）ピクセルアレイ内の少なくともひとつのピクセルをスキャンして前記ピク セルアレイ内に位置を有するスキャンされた前位ピクセルを得るステップと、 （ｂ）（１）前記ピクセルアレイ内に位置を有する先頭目標ピクセルをスキャン し、 （２）前記スキャンされた前位ピクセルを所定の非線形トラバースパター ンに従ってトラバースし、 （３）トラバースされた前記スキャンされた前位ピクセルの何れかがスキ ャンされた前記先頭目標ピクセルと一致するかを決定して、先頭のスキャンされ た一致前位ピクセルを見つけだし、 （４）前記ピクセルポインタを、前記ピクセルアレイ内で前記先頭の目標 ピクセルの位置の直後に続く位置にあるスキャンされる次の目標ピクセルに進め 、 （５）前記次の目標ピクセルが、前記ピクセルアレイ内で前記先頭のスキ ャンされた一致前位ピクセルの直後に続く位置を有する後続のスキャンされた前 位ピクセルと一致するかどうかを決定し、 （６）ピクセルポインタを進めて、スキャンされた一致前位ピクセルが見 いだされなくなるまでステップｂ（５）を繰り返して前記ピクセルポインタによ り示されたピクセルと 一致する全ての後続のスキャンされた前位ピクセルを見つけだして、一致データ ストリングを定義する ことにより、スキャンされるピクセルのストリングと一致する一致データス トリングを求めて、前記スキャンされた前位ピクセルをサーチするステップと、 （ｃ）前記ピクセルアレイ内における前記先頭の目標ピクセルに関する、前記先 頭のスキャンされた一致前位ピクセルの位置を表すオフセットを決定するステッ プと、 （ｄ）前記一致データストリング内のスキャンされた一致前位ピクセルの数であ る前記一致データストリングのストリング長を決定するステップと、 （ｅ）前記一致データストリングを、前記先頭のスキャンされた一致ピクセルの オフセットと前記一致データストリングのストリング長を含むコピートークンに 変換するステップと、 （ｆ）前記コピートークンをエンコードするステップと を含んでなる方法。 １６．請求項１５に記載の方法であって、さらに （ａ）前記ピクセルアレイを部分標本化して、画像データのストリーム内のデー タを、前記一致データストリングのために前記スキャンされた前位ピクセルをサ ーチする前に減少させるステップ を含んでなる方法。 １７．それぞれのピクセルが色画像データを含んでいる請求項１６に記載の方法 であって、さらに （ａ）前記ピクセルアレイを部分標本化する前に、それぞれのピクセルの色画像 データをフィルタするステップ を含んでなる方法。 １８．色画像データがカラースペースを有している請求項１７に記載の方法であ って、さらに （ａ）前記画像データをフィルタする前に、前記画像データのカラースペースを 他のカラースペースに変換するステップ を含んでなる方法。 １９．前記カラースペースがＹＣｒＣｂカラースペースである請求項１８に記載 の方法。 ２０．請求項１５に記載の方法であって、 前記ピクセルアレイ内のそれぞれのピクセルは、スキャンされた一致ピクセル が見つけだされたときにスキャンされた前位ピクセルが目標ピクセルと一致する かどうかを決定するのに使用される予め定められた許容差を有している方法であ って、 （ａ）スキャンされた目標ピクセルをスキャンされた前位ピクセルと比較するス テップと、 （ｂ）前記スキャンされた前位ピクセルが前記目標ピクセルの前記予め定められ た許容差内にあるかどうかを決定するステップと、 （ｃ）前記スキャンされた前位ピクセルが前記目標ピクセルの前記予め定められ た許容差内にあるときは前記スキャンされた前位ピクセルを一致目標ピクセルと 見なすステップと が実行される方法。 ２１．請求項１５に記載の方法において、 前記所定の非線形トラバースパターンは圧縮される個々の画像データのストリ ームごとに画像トラバース長を含む固定長を有しており、 前記画像トラバース長さは画像ごとに異なっている ことを特徴とする方法。 ２２．請求項１５に記載の方法において、 前記所定の非線形トラバースパターンは、圧縮される画像データの単一のスト リームの圧縮の間に変化する長さを有している ことを特徴とする方法。 ２３．請求項１５に記載の方法において、 前記所定の非線形トラバースパターンは、圧縮される画像データの各個々のス トリームごとに、画像ごとに異なる固定したパターンを含んでいる ことを特徴とする方法。 ２４．請求項１５に記載の方法において、 前記所定の非線形トラバースパターンは圧縮される画像データの単一のストリ ームの圧縮の間に変化する ことを特徴とする方法。 ５０．ピクセルアレイを含む画像データのストリームをエンコードされた画像デ ータのストリームに圧縮すると共にこのエンコードさ れた画像データのストリームを解凍された画像に解凍するための、スキャンされ る目標ピクセルを示すピクセルポインタを含むデータ圧縮システムであって、 （ａ）ピクセルアレイ内の少なくともひとつのピクセルをスキャンして前記ピク セルアレイ内に位置を有するスキャンされた前位ピクセルを得るスキャナと、 （ｂ）（１）前記ピクセルアレイ内に位置を有する先頭目標ピクセルをスキャン する手段と、 （２）前記スキャンされた前位ピクセルを所定の非線形トラバースパター ンを用いててトラバースする手段と、 （３）前記スキャンされた前位ピクセルの何れかがスキャンされた前記先 頭目標ピクセルと一致するかを決定して、先頭のスキャンされた一致前位ピクセ ルを見つけだす第１比較手段と、、 （４）前記ピクセルポインタを、前記ピクセルアレイ内で前記先頭の目標 ピクセルの位置の直後に続く位置にあるスキャンされる次の目標ピクセルに進め る手段と、 （５）前記次の目標ピクセルが、前記ピクセルアレイ内で前記先頭のスキ ャンされた一致前位ピクセルの直後に続く位置を有する後続のスキャンされた前 位ピクセルと一致するかどうかを決定する第２比較手段と、 （６）ピクセルポインタを進めて、スキャンされた一致前位ピクセルが見 いだされなくなるまでステップｂ（５）を繰り返して前記ピクセルポインタによ り示されたピクセルと一致する全ての後続のスキャンされた前位ピクセルを見つ けだして、一致データストリングを定義する手段と を含む、スキャンされるピクセルのストリングと一致する一致データストリング を求めて、前記スキャンされた前位ピクセルをサーチする手段と、 （ｃ）前記ピクセルアレイ内における前記先頭の目標ピクセルに関する、前記先 頭のスキャンされた一致前位ピクセルの位置を表すオフセットを決定する手段と 、 （ｄ）前記一致データストリング内のスキャンされた一致前位ピクセルの数であ る前記一致データストリングのストリング長を決定する手段と、 （ｅ）前記一致データストリングを、前記先頭のスキャンされた一致前位ピクセ ルのオフセットと前記一致データストリングのストリング長を含むコピートーク ンに変換するコンバータと、 （ｆ）前記コピートークンをエンコードするエンコーダと を含んでなるシステム。 ７６．それ自体からの少なくともひとつのピクセルを受け入れるストリングに分 割可能なピクセルアレイを含む画像データのストリームを圧縮すると共にこの画 像データのストリームを解凍された画像に解凍するためのシステムであって、 （ａ）前記ピクセルアレイを所定の非線形トラバースパターンでスキャンしてス キャンされた前位ピクセルを得るスキャナと、 （ｂ）前記スキャンされたピクセルを前記スキャンされた前位ピクセルと比較し てスキャンされたピクセルの何れかが前記スキャンされた前位ピクセルと一致す るかどうかを決定するコンパレータと、 （ｃ）スキャンされたピクセルと一致する少なくともひとつのスキ ャンされた前位ピクセルと対応するストリングを有するスキャンされた少なくと もひとつのピクセルの各ストリングに対する一致データストリングで、前記スキ ャンされた一致前位ピクセルと対応する画像データを含む一致データストリング が、もしあれば、それを生成する手段と、 （ｄ）もし一致データストリングが生成されれば、そのような一致データストリ ングをコピートークンに変換するコンバータと、 （ｅ）スキャンされたピクセルがスキャンされた一致前位ピクセルを有しないな らば、スキャンされたピクセルをリテラルトークンに変換するコンバータと、 （ｆ）前記コピートークンがあればそれをエンコードし、また前記リテラルトー クンをエンコードされたトークンセットにエンコードするエンコーダと、 （ｇ）エンコードされた前記トークンセットを伝達するトランスミッタと、 （ｈ）前記エンコードされたトークンセットをデコードしてデコードされたトー クンセットを得るデコーダと、 （ｉ）前記デコードされたトークンセットを伸張して解凍された画像を得る手段 と を含んでなるシステム。 ８５．ピクセルアレイを含む画像データのストリームをエンコードされた画像デ ータのストリームに圧縮すると共にこのエンコードされた画像データのストリー ムを解凍された画像に解凍するためのコンピュータプログラムであって、そのコ ンピュータプログラムは、スキャンされる目標ピクセルを示すピクセルポインタ を含むコンピ ュータシステムにより読み取り可能な媒体上に認識可能に記録されており、プロ グラムがコンピュータシステムにより読み取られて実行されると、前記コンピュ ータシステムにより （ａ）ピクセルアレイ内の少なくともひとつのピクセルをスキャンして前記ピク セルアレイ内に位置を有するスキャンされた前位ピクセルを得る機能と、 （ｂ）（１）前記ピクセルアレイ内に位置を有する先頭目標ピクセルをスキャン し、 （２）前記スキャンされた前位ピクセルを所定の非線形トラバースパター ンに従ってトラバースし、 （３）トラバースされた前記スキャンされた前位ピクセルの何れかがスキ ャンされた前記先頭目標ピクセルと一致するかを決定して、先頭のスキャンされ た一致前位ピクセルを見つけだし、 （４）前記ピクセルポインタを、前記ピクセルアレイ内で前記先頭の目標 ピクセルの位置の直後に続く位置にあるスキャンされる次の目標ピクセルに進め 、 （５）前記次の目標ピクセルが、前記ピクセルアレイ内で前記先頭のスキ ャンされた一致前位ピクセルの直後に続く位置を有する後続のスキャンされた前 位ピクセルと一致するかどうかを決定し、 （６）ピクセルポインタを進めて、スキャンされた一致前位ピクセルが見 いだされなくなるまで機能ｂ（５）を繰り返して前記ピクセルポインタにより示 されたピクセルと一致する全ての後続のスキャンされた前位ピクセルを見つけだ して、一致データストリングを定義する ことにより、スキャンされるピクセルのストリングと一致する一致データストリ ングを求めて、前記スキャンされた前位ピクセルをサーチする機能と、 （ｃ）前記ピクセルアレイ内における前記先頭の目標ピクセルに関する、前記先 頭のスキャンされた一致前位ピクセルの位置を表すオフセットを決定する機能と 、 （ｄ）前記一致データストリング内のスキャンされた一致前位ピクセルの数であ る前記一致データストリングのストリング長を決定する機能と、 （ｅ）前記一致データストリングを、前記先頭のスキャンされた一致ピクセルの オフセットと前記一致データストリングのストリング長を含むコピートークンに 変換する機能と、 （ｆ）前記コピートークンをエンコードする機能と を実行するようにコンピュータシステムの構成を配置するように適合させてなる コンピュータプログラム。 ９５．それ自体からの少なくともひとつのピクセルを受け入れるストリングに分 割可能なピクセルアレイを含む画像データのストリームを圧縮すると共にこの画 像データのストリームを解凍された画像に解凍するためのコンピュータプログラ ムであって、そのコンピュータプログラムはコンピュータシステムにより読み取 り可能な媒体上に認識可能に記録されており、プログラムがコンピュータシステ ムにより読み取られて実行されると、前記コンピュータシステムにより （ａ）前記ピクセルアレイを所定の非線形トラバースパターンに従ってスキャン してスキャンされた前位ピクセルを得る機能と、 （ｂ）前記スキャンされたピクセルを前記スキャンされた前位ピクセルと比較し てスキャンされたピクセルの何れかが前記スキャンされた前位ピクセルと一致す るかどうかを決定する機能と、 （ｃ）スキャンされたピクセルと一致する少なくともひとつのスキャンされた前 位ピクセルと対応するストリングを有するスキャンされた少なくともひとつのピ クセルの各ストリングに対する一致データストリングで、前記スキャンされた一 致前位ピクセルと対応する画像データを含む一致データストリングを生成する機 能と、 （ｄ）もし一致データストリングが生成されれば、そのような一致データストリ ングをコピートークンに変換する機能と、 （ｅ）スキャンされたピクセルがスキャンされた一致前位ピクセルを有しないな らば、スキャンされたピクセルをリテラルトークンに変換する機能と、 （ｆ）前記コピートークンがあればそれをエンコードし、また前記リテラルトー クンをエンコードされたトークンセットにエンコードする機能と、 （ｇ）エンコードされた前記トークンセットを伝達する機能と、 （ｈ）前記エンコードされたトークンセットをデコードしてデコードされたトー クンセットを得る機能と、 （ｉ）前記デコードされたトークンセットを伸張して解凍された画像を得る手段 と を実行するようにコンピュータシステムの構成を配置するように適合させてなる コンピュータプログラム。 １０１．入力データストリングをからなる２またはそれ以上のグル ープの複数の入力データセグメントを含む入力データストリームを圧縮する方法 であって、 （ａ）入力データストリームを読み込んで、前位データストリングからなる２ま たはそれ以上のグループの複数の前位データセグメントを含む前位データを得る ステップと、 （ｂ）前記前位データを、それぞれ前位データストリングを含み前記入力データ ストリームからの入力データストリングと一致する最長の一致前位データストリ ングを求めて、所定の非線形トラバースパターンでサーチするステップと、 （ｃ）前記前位データ内に最長の一致前位データストリングが見いだせたらば、 その最長の一致前位データストリングを圧縮して圧縮ストリングを得ると共にこ の圧縮ストリングをコピートークンとしてエンコードするステップと、 （ｄ）一致前位データセグメントを有しない入力データセグメントについて、そ のような入力データセグメントをリテラルトークンとしてエンコードするステッ プと、 （ｅ）前記コピートークンがあればそれを、またリテラルトークンを出力するス テップと を含んでなる方法。 １０４．入力データストリングをからなる２またはそれ以上のグループの複数の 入力データセグメントを含む入力データストリームを圧縮するシステムであって 、 （ａ）入力データストリームを読み込んで、前位データストリングからなる２ま たはそれ以上のグループの複数の前位データセグメントを含む前位データを得る 手段と、 （ｂ）前記前位データを、それぞれ前位データストリングを含み前記入力データ ストリームからの入力データストリングと一致する最長の一致前位データストリ ングを求めて、所定の非線形トラバースパターンでサーチする手段と、 （ｃ）前記前位データ内に最長の一致前位データストリングが見いだせたらば、 その最長の一致前位データストリングを圧縮して圧縮ストリングを得る圧縮手段 及びこの圧縮ストリングをコピートークンとしてエンコードするエンコーダと、 （ｄ）一致前位データセグメントを有しない入力データセグメントについて、そ のような入力データセグメントをリテラルトークンとしてエンコードするエンコ ーダと、 （ｅ）前記コピートークンがあればそれを、またリテラルトークンを出力するポ ートと を含んでなるシステム。 １０５．ある順序を有している複数のデータセグメントを含むデータを圧縮する 方法で、前記複数のデータセグメントは目標セグメントと前位セグメントを含み 、前記前位セグメントは前記複数のデータセグメントの順序内で前記目標セグメ ントに先行しているデータを圧縮する方法であって、 （ａ）先頭の目標セグメントを選択するステップと、 （ｂ）前記前位セグメントを所定の非線形トラバースパターンに従ってトラバー スするステップと、 （ｃ）前記先頭の目標セグメントで始まる目標セグメントのストリングと一致す る、前記所定の非線形トラバースパターン内にある先頭の一致前位セグメントを 有する最長の一致する前位セグ メントのストリングを見つけだすステップと を含んでなる方法。 １１２．ある順序を有している複数のタセグメントを含むデータを圧縮するシス テムで、前記複数のセグメントは目標セグメントと前位セグメントを含み、前記 前位セグメントは前記複数のセグメントの順序内で前記目標セグメントに先行し ているデータを圧縮するシステムであって、 （ａ）先頭の目標セグメントを選択する手段と、 （ｂ）前記前位セグメントを所定の非線形トラバースパターンに従ってトラバー スする手段と、 （ｃ）前記先頭の目標セグメントで始まる目標セグメントのストリングと一致す る、前記所定の非線形トラバースパターン内にある先頭の一致前位セグメントを 有する最長の一致する前位セグメントのストリングを見つけだす手段と を含んでなるシステム。 １１９．ある順序を有している複数のタセグメントを含むデータを圧縮するコン ピュータプログラムで、前記複数のセグメントは目標セグメントと前位セグメン トを含み、前記前位セグメントは前記複数のセグメントの順序内で前記目標セグ メントに先行しているデータを圧縮するコンピュータプログラムであって、その コンピュータプログラムはコンピュータシステムにより読み取り可能な媒体上に 認識可能に記録されており、プログラムがコンピュータシステムにより読み取ら れて実行されると、前記コンピュータシステムにより （ａ）先頭の目標セグメントを選択する機能と、 （ｂ）前記前位セグメントを所定の非線形トラバースパターンに従ってトラバー スする機能と、 （ｃ）前記先頭の目標セグメントで始まる目標セグメントのストリングと一致す る、前記所定の非線形トラバースパターン内にある先頭の一致前位セグメントを 有する最長の一致する前位セグメントのストリングを見つけだす機能と を実行するようにコンピュータシステムの構成を配置するように適合させてなる コンピュータプログラム。