(57)【要約】【課題】同一パターンの検出方法や符号化の方法を改良することにより、低コストで圧縮率の高い画像データの圧縮方法、プログラムおよび装置を提供することを目的とする。【解決手段】複数の画素データからなる画像データを複数のセルに分割する第１のステップと、これらのセルの中から圧縮処理の対象となる圧縮対象セル２を特定する第２のステップと、画像データの中から圧縮対象セルと同一の画素データを有する圧縮対象セル自体以外のエリアを検索する第３のステップと、圧縮対象セルと同一の画素データを有するエリアを検索したときは、圧縮対象セルとエリアとの間の位置のオフセットデータを圧縮対象セルの画素データを表す情報として記録する第４のステップとからなる画像データの圧縮方法により低コストで圧縮率の高い画像データの圧縮方法、プログラムおよび装置を提供する。【選択図】　　　図１
2004048091.tif 000002
【特許請求の範囲】
【請求項１】
複数の画素データからなる画像データを複数のセルに分割する第１のステップと、これらのセルの中から圧縮処理の対象となる圧縮対象セルを特定する第２のステップと、前記画像データの中から前記圧縮対象セルと同一の画素データを有する当該圧縮対象セル自体以外のエリアを検索する第３のステップと、前記圧縮対象セルと同一の画素データを有するエリアを発見したときは、前記圧縮対象セルと前記エリアとの間の位置のオフセットデータを前記圧縮対象セルの画素データを表す情報として記録する第４のステップとからなる画像データの圧縮方法。
【請求項２】
前記第３のステップが、圧縮処理の終了したセルおよび前記圧縮対象セルからなる画像データの範囲からエリアを検索する請求項１に記載された画像データの圧縮方法。
【請求項３】
前記第３のステップが、前記圧縮対象セルを基点として、順次遠ざかる方向にエリアを検索する請求項１または請求項２に記載された画像データの圧縮方法。
【請求項４】
複数の画素データからなる画像データを複数のセルに分割する第１のステップと、これらのセルの中から圧縮処理の対象となる圧縮対象セルを特定する第２のステップと、前記画像データの中から前記圧縮対象セルと同一の画素データを有する当該圧縮対象セル自体以外のエリアを検索する第３のステップと、前記圧縮対象セルと同一の画素データを有するエリアを発見したときは、前記圧縮対象セルと前記エリアとの間の位置のオフセットデータを前記圧縮対象セルの画素データを表す情報として記録する第４のステップとをコンピュータに実行させるためのプログラム。
【請求項５】
前記第３のステップが、圧縮処理の終了したセルおよび前記圧縮対象セルからなる画像データの範囲からエリアを検索する請求項４に記載されたコンピュータに実行させるためのプログラム。
【請求項６】
前記第３のステップが、前記圧縮対象セルを基点として、順次遠ざかる方向にエリアを検索する請求項４または請求項５に記載されたコンピュータに実行させるためのプログラム。
【請求項７】
複数の画素データからなる画像データを複数のセルに分割するセル分割手段と、これらのセルの中から圧縮処理の対象となる圧縮対象セルを特定する圧縮対象特定手段と、前記画像データの中から前記圧縮対象セルと同一の画素データを有する当該圧縮対象セル自体以外のエリアを検索するエリア検索手段と、前記圧縮対象セルと同一の画素データを有するエリアを発見したときは、前記圧縮対象セルと前記エリアとの間の位置のオフセットデータを前記圧縮対象セルの画素データを表す情報として記録するデータ圧縮処理手段とからなる画像データの圧縮装置。
【請求項８】
前記エリア検索手段が、圧縮処理の終了したセルおよび前記圧縮対象セルからなる画像データの範囲からエリアを検索する請求項７に記載された画像データの圧縮装置。
【請求項９】
前記エリア検索手段が、前記圧縮対象セルを基点として、順次遠ざかる方向にエリアを検索する請求項７または請求項８に記載された画像データの圧縮装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、画像データの圧縮方法、プログラムおよびその装置に関する。
【０００２】
【従来の技術】
一般に、画像データは、そのデータ量が膨大であるため、これらのデータを記憶し、処理し、通信手段により送受信するためにかかるコストを低減する目的でデータの圧縮が行われている。画像データを圧縮する手法としては、ランレングスやハフマン符号、算術符号等の古典的な圧縮方法から、隣接するセル間で一致するパターンを見つけるセル参照圧縮方式、そして、ＪＰＥＧ（Ｊｏｉｎｔ　Ｐｈｏｔｏｇｒａｐｈｉｃ　Ｅｘｐｅｒｔｓ　Ｇｒｏｕｐ）やＭＰＥＧ（Ｍｏｖｉｎｇ　Ｐｉｃｔｕｒｅ　Ｅｘｐｅｒｔｓ　Ｇｒｏｕｐ）等に至るまでの多数のアルゴリズムが存在する。
【０００３】
これらの画像データ圧縮方法のうち、ランレングス等の古典的な圧縮方法やセル参照圧縮方式等のデータ圧縮方法は、特に、可逆方式と呼ばれ、原画像と復号画像の品質が同じ圧縮方式であって、画像品質が良好である反面、圧縮率があまり高くないという特色がある。一方で、ＪＰＥＧやＭＰＥＧのようなデータ圧縮方式は、特に、非可逆方式と呼ばれ、復号画像の品質が原画像よりも劣るが、高い圧縮率が得られるという特色がある。したがって、どのような圧縮方式を選択するかは、システム上の用途や画像品質の重要度および取り扱うデータ量等により、適宜、決定する必要がある。
【０００４】
図４は、画像データ圧縮方式の１つであるセル参照圧縮方式を用いた画像データの圧縮方法を示したものである。
セル参照圧縮方式では、８ドット（画素）×８ドット（画素）の画像データのかたまりをセルという単位で定義し、画面をこのセルの単位で分割するとともに、圧縮しようとするセルに隣接するセルの中に、圧縮しようとするセルのパターンと同一のパターンが存在するか否かを検索する。そして、同一のパターンを有するセルが検索できたときは、本来、記録すべき画像の実データに代えて、同一のパターンを有するセルの位置を示すデータのみを記録して、画像データの圧縮を行う方式のものである。
【０００５】
これを図４により、もう少し詳しく説明する。いま、圧縮をしようとするセルを図４の右下隅のセルとすると、参照すべきセルは図に実線で示す３つのセル（参照セルＩ、ＩＩ、ＩＩＩ）になる。また、図４（ｂ）および（ｃ）は、セル参照圧縮方式が実行された後のデータ符号化のしくみを示した図である。これによると、圧縮をしようとするセルについては、参照するセルとの間でセル内の画像パターンが一致するか否かの判断が行われ、一致するセルがあった場合は、その一致したセルの位置を示す２ビットのヘッダデータを記録するのみで、実際の画像データを省略する符号化を行う。また、隣接するセルに画像パターンが一致するセルがなかった場合は、２ビットのヘッダデータ「００」に続いて実際の画像データを記録する符号化を行う。
【０００６】
【発明が解決しようとする課題】
しかし、上記のように、従来、可逆方式の画像圧縮方法であるセル参照圧縮方式を採用していたシステムにおいても、扱う画像データが時代とともに複雑化したことから、従来のように、画面をセルという固定された枠で区切って、このセルの中から被圧縮セルと同パターンを有するセルを検索するやり方では、十分な圧縮率が得られない場合が生じてきた。一方で、圧縮率を高めるために、非可逆方式を採用するには、扱うデータ量やコストの面からみて妥当でないケースもある。
【０００７】
そこで、本発明は、上述した問題点に鑑みてなされたものであって、従来の可逆方式の圧縮方法を踏襲しながら、同一パターンの検出方法や符号化の方法を改良することにより、低コストで圧縮率の高い画像データの圧縮方法、プログラムおよび装置を提供することを目的とする。
【０００８】
【課題を解決するための手段】
前記課題を解決するため、本発明は、以下の手段を提案している。
請求項１に係る発明は、複数の画素データからなる画像データを複数のセルに分割する第１のステップと、これらのセルの中から圧縮処理の対象となる圧縮対象セルを特定する第２のステップと、前記画像データの中から前記圧縮対象セルと同一の画素データを有する当該圧縮対象セル自体以外のエリアを検索する第３のステップと、前記圧縮対象セルと同一の画素データを有するエリアを発見したときは、前記圧縮対象セルと前記エリアとの間の位置のオフセットデータを前記圧縮対象セルの画素データを表す情報として記録する第４のステップとからなる画像データの圧縮方法を提案している。
また、第３のステップにおける「同一の画素データ」とは、圧縮対象セルと検索エリアの相互に対応する画素データがすべて同一である場合のほか、圧縮対象セルと検索エリアの対応する画素データの差分値が画質に影響しない範囲の値である場合を含むものとする。
【０００９】
請求項４に係る発明は、複数の画素データからなる画像データを複数のセルに分割する第１のステップと、これらのセルの中から圧縮処理の対象となる圧縮対象セルを特定する第２のステップと、前記画像データの中から前記圧縮対象セルと同一の画素データを有する当該圧縮対象セル自体以外のエリアを検索する第３のステップと、前記圧縮対象セルと同一の画素データを有するエリアを発見したときは、前記圧縮対象セルと前記エリアとの間の位置のオフセットデータを前記圧縮対象セルの画素データを表す情報として記録する第４のステップとをコンピュータに実行させるためのプログラムを提案している。
【００１０】
これらの発明によれば、画像データの圧縮処理の対象となるセルと同一の画素データを有するエリアを、分割されたセルに限定されることなく、検索する方法としたので、検索範囲内のあらゆる画素データからなるエリアを検索の対象とすることができる。また、検索範囲内で、同一の画素データを有するエリアが発見されたときは、処理対象のセルに対する該当エリアまでの移動量に相当する位置のオフセットデータを圧縮処理対象セルの画素データとして記録する方法としたので、記録すべきデータ量を減少させることができる。
【００１１】
請求項２に係る発明は、請求項１に記載された画像データの圧縮方法において、前記第３のステップが、圧縮処理の終了したセルおよび前記圧縮対象セルからなる画像データの範囲からエリアを検索する画像データの圧縮方法を提案している。
【００１２】
請求項５に係る発明は、請求項３に記載されたコンピュータに実行させるためのプログラムについて、前記第３のステップが、圧縮処理の終了したセルおよび前記圧縮対象セルからなる画像データの範囲からエリアを検索するコンピュータに実行させるためのプログラムを提案している。
【００１３】
これらの発明によれば、各圧縮処理対象セルの画素データを表す情報は、すでに圧縮処理されたデータに基づいて構成されるので、これを伸張する際には、伸張処理された画像データをもとに画像データが再現されることとなり正確な再現が可能となる。
【００１４】
請求項３に係る発明は、請求項１または請求項２に記載された画像データの圧縮方法において、前記第３のステップが、前記圧縮対象セルを基点として、順次遠ざかる方向にエリアを検索する画像データの圧縮方法を提案している。
【００１５】
請求項６に係る発明は、請求項４または請求項５に記載されたコンピュータに実行させるためのプログラムにおいて、前記第３のステップが、前記圧縮対象セルを基点として、順次遠ざかる方向にエリアを検索するコンピュータに実行させるためのプログラムを提案している。
【００１６】
これらの発明によれば、圧縮対象セルと同一の画素データを有するエリアを検索する順序を一般的な画像データの構成を考慮して、圧縮対象セルを基点として、その近傍から行うこととしたので、一般的な画像データの構成から考えても、早いタイミングで同一の画素データを有するエリアを検索できる。
【００１７】
請求項７に係る発明は、複数の画素データからなる画像データを複数のセルに分割するセル分割手段と、これらのセルの中から圧縮処理の対象となる圧縮対象セルを特定する圧縮対象特定手段と、前記画像データの中から前記圧縮対象セルと同一の画素データを有する当該圧縮対象セル自体以外のエリアを検索するエリア検索手段と、前記圧縮対象セルと同一の画素データを有するエリアを発見したときは、前記圧縮対象セルと前記エリアとの間の位置のオフセットデータを前記圧縮対象セルの画素データを表す情報として記録するデータ圧縮処理手段とからなる画像データの圧縮装置を提案している。
【００１８】
この発明によれば、セル分割手段により、画像データを複数のセルに分割し、圧縮対象特定手段により圧縮処理の対象となるセルを特定する。そして、エリア検索手段により、同一の画素データを有する圧縮対象セル自体以外のエリアを検索して、同一の画素データを有するエリアが発見されたときは、データ圧縮処理手段により、処理対象のセルに対する該当エリアまでの移動量に相当するオフセットデータが圧縮処理対象セルの画素データとして記録される。したがって、エリア検索手段によって、分割されたセルに限定されることなく、検索範囲内のあらゆる画像データを検索の対象とすることができ、また、データ圧縮処理手段によって、記録すべきデータ量を減少させることができる。
【００１９】
請求項８に係る発明は、請求項７に記載された画像データの圧縮装置について、前記エリア検索手段が、圧縮処理の終了したセルおよび前記圧縮対象セルからなる画像データの範囲からエリアを検索する画像データの圧縮装置を提案している。　この発明によれば、エリア検索手段が検索するエリアを、圧縮処理が終了したセルと圧縮処理対象セルを一部に含む範囲とする装置としたことから、圧縮処理対象セルと同一の画素データを有するエリアを検索できる確率が高くなる。
【００２０】
請求項９に係る発明は、請求項７または請求項８に記載された画像データの圧縮装置において、前記エリア検索手段が、前記圧縮対象セルを基点として、順次遠ざかる方向にエリアを検索する画像データの圧縮装置を提案している。
【００２１】
この発明によれば、エリア検索手段が、圧縮対象セルと同一の画素データを有するエリアを検索する順序を一般的な画像データの構成を考慮して、圧縮対象セルを基点として、その近傍から行うこととしたので、早いタイミングで同一の画素データを有するエリアを検索できる。
【００２２】
【発明の実施の形態】
以下、本発明の一実施形態に係る画像データの圧縮方法、プログラムおよび装置について図１から図３を参照して詳細に説明する。
図１は、本発明の一実施形態に係る画像データの圧縮方法を示す図であり、同図（ａ）は、圧縮処理対象セルと同一の画素データを有するエリアを検索する場合の概念図を、同図（ｂ）は、同一の画素データを有するエリアが発見できたときに記録されるデータのデータ構造を、同図（ｃ）は、同一の画素データを有するエリアが検索できなかったときに記録されるデータのデータ構造を、それぞれ示している。また、同図（ｄ）は、Ｘ軸、Ｙ軸のオフセット量がそれぞれＸ−Ｘ１＝５、Ｙ−Ｙ１＝７の場合に記録されるデータ例を示している。
【００２３】
ここで、前提として全画面は、図６に示すように３２０ドット×２４０ドット（４０セル×３０セル）の長方形とする。また、図１（ａ）は、全画面における１２００個のセルの内、ある特定された１つのセルと、そのセルを圧縮処理対象とした場合の検索範囲を示す。検索範囲は図のように圧縮処理対象セルから左に４セル分、上に４セル分とし、圧縮処理対象セルも含めて５セル×５セル（４０ドット×４０ドット）とする。なお、全画面中における圧縮処理対象セルを特定する順番については、次のとおりとする。まず、図６において、全画面中の最も左上にあるセルの右隣のセル（セル２）を特定する。次に、セル２の圧縮処理を実行し、終了後はその右隣のセル（セル３）に移る。以下、同様に、図６の矢印のとおりにセル２→セル３→・・・→セル４０→セル４１→セル４２・・・→セル１２００と進む。なお、セル１は圧縮処理対象とはしないため、後に詳細に説明する図１（ｃ）の方法にて記録する。また、セルを特定したときのセル検索範囲（４０ドット×４０ドット）が画面からはみ出してしまう場合は、画面内を検索範囲とする。
【００２４】
点線の囲みで示されている８ドット（画素）×８ドット（画素）のブロックは、圧縮処理対象セルと同一の画素データを有する仮想セルと呼ばれるものである。仮想セルは、検索範囲内において圧縮処理対象セルと同一の画素データを有するエリアを発見する際の架空のセルであって、圧縮処理対象セルと仮想セルの左上隅に書かれている黒点はポインタと呼ばれ、仮想セルは、圧縮処理対象セルのポインタを原点として、画像データを描画するラインに平行な軸方向と、これに直交する軸方向にそれぞれ１ドット（画素）ずつ移動させることができる。なお、検索エリアのセルと仮想セルの画素データが同一であるか否かは、相互に対応する画素データの差分を取って、これが画質に影響しない所定の範囲内の値であるか否かを判断することにより行われる。
【００２５】
これらのポインタは、仮想セルが検索範囲内で圧縮処理対象セルと同一の画素データを有するエリアを発見した場合に、圧縮処理対象セルと仮想セルの相対位置（オフセット量）を算出するために用いられる、いわゆる、それぞれのセルの座標値を示す役割を果たすものである。なお、ポインタの（Ｘ、Ｙ）値の正方向を示す軸の向きは、画面上をデ−タが走査する向きと同一であることから、Ｘ軸の正方向は画面を正面から見たときの右方向を、Ｙ軸の正方向は同様に下方向となる。以後、この向きを各軸の正方向として説明する。
【００２６】
図１（ｂ）中、左端には、オフセット量の範囲が記載され、これに続いてヘッダデータと、実際の画像データに代わって記録されるオフセットデータとの関係を示すデータ構造が記載されている。
本発明の実施形態の場合、オフセット量は図１のように、大きく３つの領域、［Ｉ］、［ＩＩ］、［ＩＩＩ］に分けられており、これに準じて、符号化されるデータの長さが異なっている。これは、画像データの性質上、圧縮処理対象セルの近傍ほど、圧縮処理対象セルと同一の画素データを有するエリアが出現する可能性が高いと考えられることから、圧縮処理対象セルからのオフセット量が少ないものほど、記録されるデータを短くする可変長符号として、データ圧縮の効果を上げることを意図したものである。
【００２７】
具体的なデータ構造は、実際の画像データあるいは本発明におけるオフセットデータと、これらのデータの先頭に付加され後続のデータの種別を示すヘッダデータとから構成されており、オフセットデータには、ヘッダデータのデータビット長に対して１ビット多いビット長が割り当てられている。また、オフセットの演算式は、圧縮処理対象セルのポインタを（Ｘ、Ｙ）とし、仮想セルのポインタを（Ｘ１、Ｙ１）としたときのものであり、前述した、Ｘ軸、Ｙ軸の正方向の向きを考慮して、オフセットの値が正の数になるよう符号が与えられている。
【００２８】
例えば、図１（ｂ）の演算式で表されるオフセット量が、Ｘ軸、Ｙ軸ともに７以下であれば、オフセット量は、Ｘ軸、Ｙ軸それぞれ３ｂｉｔのデータで表すことができる。ヘッダが「１，０」の時は、「０」の後の３ｂｉｔがＸ軸のオフセット量を表し、その後の３ｂｉｔがＹ軸のオフセット量を表すことになる。したがって、オフセット量がＸ−Ｘ１＝５、Ｙ−Ｙ１＝７の場合のデータは図１（ｄ）のようになる。なお、検索範囲を検索しても、圧縮処理対象セルと同一の画素データを有するエリアを検索できなかったときは、ヘッダデータを「０」のみの１ビットとして、その後に、６４バイトの実際の画像デ−タ、すなわち圧縮処理対象セルの画像データをそのまま記録する。これが図１（ｃ）に記載されている。
【００２９】
図２、図３は、仮想セルを検索範囲内で移動させる場合の処理を示したフローチャートである。ただし、図２、図３の実施の形態では、検索範囲を圧縮処理対象セルを含めた４０ドット（画素）×４０ドット（画素）としている。
図２から、まず、圧縮処理対象セルが画面の中の上端または左端に位置するか否かの判断を行う（ステップ１０１）。判断の結果、画面の上端または左端でないと確認されたときは、仮想セルをＸ軸のマイナス方向に１ドット移動し（ステップ１０２）、仮想セルと検索エリアのパターンが一致するか否かを判断する（ステップ１０３）。判断の結果、両者のパターンが一致したときは、ヘッダデータとオフセットデータを作成し（ステップ１０４）、次の圧縮対象セルに移動する（ステップ１０５）とともに、処理をスタートに戻す。
【００３０】
仮想セルと検索エリアのパターンが一致しなかったときは、Ｘ軸方向の移動量がすでに３１ドットに達しているか、あるいは、画面の端に到達しているかの判断を行い（ステップ１０６）、移動量がまだ３１ドットに達しておらず、画面の端でもないときはステップ１０２の戻って、仮想セルをＸ軸のマイナス方向に１ドット移動して、上記と同様の処理を再び行う。一方、移動量がすでに３１ドットに達している、あるいは、画面の端に到達していると判断されたときには、次に、Ｙ軸方向の移動量がすでに３１ドットに達しているか、あるいは、画面の端に到達しているかの判断を行う（ステップ１０７）。判断の結果、Ｙ軸方向の移動量は３１ドットに達しておらず、画面の端にも到達していない場合は、仮想セルのＸ軸を初期に戻すとともに、Ｙ軸のマイナス方向に１ドット移動して（ステップ１０８）、仮想セルと検索エリアのパターンが一致するか否かを判断する。また、Ｙ軸方向の移動量がすでに３１ドットに達しており、あるいは、画面の端に到達していると判断されたときは、ヘッダデータを「０」とし、その後に実データを付加した画像データを作成し（ステップ１０９）、次の圧縮対象セルに移動する（ステップ１１０）とともに、処理をスタートに戻す。
【００３１】
次に、図３により、圧縮処理対象セルが画面の中の上端または左端に位置する場合には、そのセルが画面の左端にあるのか否かの判断を行う（ステップ１１１）。判断の結果、圧縮処理対象セルが画面の左端にあるときは、仮想セルをＹ軸のマイナス方向に１ドット移動して仮想セルと検索エリアのパターンが一致するか否かを判断する（ステップ１１３）。判断の結果、両者のパターンが一致したときは、ヘッダデータとオフセットデータを作成し（ステップ１１４）、次の圧縮対象セルに移動する（ステップ１１５）とともに、処理をスタートに戻す。
【００３２】
仮想セルと検索エリアのパターンが一致しなかったときは、Ｙ軸方向の移動量がすでに３１ドットに達しているか、あるいは、画面の端に到達しているかの判断を行い（ステップ１１６）、移動量がすでに３１ドットに達している、あるいは、画面の端に到達していると判断されたときには、ヘッダデータを「０」とし、その後に実データを付加した画像データを作成し（ステップ１１７）、次の圧縮対象セルに移動する（ステップ１１５）とともに、処理をスタートに戻す。一方、移動量がまだ３１ドットに達しておらず、画面の端でもないときはステップ１１２の戻って、仮想セルをＹ軸のマイナス方向に１ドット移動して、上記と同様の処理を再び行う。
【００３３】
圧縮処理対象セルが画面の中の上端に位置するが、画面の左端ではない場合は、仮想セルをＸ軸のマイナス方向に１ドット移動して（ステップ１１８）、仮想セルと検索エリアのパターンが一致するか否かを判断する（ステップ１１９）。判断の結果、両者のパターンが一致したときは、ヘッダデータとオフセットデータを作成し（ステップ１２０）、次の圧縮対象セルに移動する（ステップ１１５）とともに、処理をスタートに戻す。
【００３４】
仮想セルと検索エリアのパターンが一致しなかったときは、Ｘ軸方向の移動量がすでに３１ドットに達しているか、あるいは、画面の端に到達しているかの判断を行い（ステップ１２１）、移動量がすでに３１ドットに達している、あるいは、画面の端に到達していると判断されたときには、ヘッダデータを「０」とし、その後に実データを付加した画像データを作成し（ステップ１２２）、次の圧縮対象セルに移動する（ステップ１１５）とともに、処理をスタートに戻す。一方、移動量がまだ３１ドットに達しておらず、画面の端でもないときはステップ１１８に戻って、仮想セルをＸ軸のマイナス方向に１ドット移動して、上記と同様の処理を再び行う。
【００３５】
次に、復号化の処理について、図４のフローチャートを用いて説明する。前記の圧縮方法にて圧縮されたデータを受けた復号装置は、図６におけるセル１をスタートして矢印の順番に復号する。具体的な処理の手順としては、図４から、まず、ヘッダデータが「０」であるか否かが確認される（ステップ２０１）。確認の結果、ヘッダデータが「０」である場合は、ヘッダデータ後の実データに基づいて画像が形成され（ステップ２０２）、次いで、このセルが最後のセルであるか否かの判断がされる（ステップ２０８）。判断の結果、これが最後のセルである場合は、復号処理を終了し、そうでない場合には、セルを移動して（ステップ２０９）、スタートに戻り、処理を続行する。
【００３６】
一方、ヘッダデータが「０」でない場合には、オフセットデータから同一のパターンを有するエリアを特定し（ステップ２０３）、まず、このエリアの最も左上の画素データを特定して（ステップ２０４）、この特定された画素データをセルにコピーする（ステップ２０５）。この作業を順次進めていき、最後の画素データについて処理を終了したときは（ステップ２０６）、今、復号処理をしたセルが最後のセルであるかどうかを確認し（ステップ２０８）、最後のセルである場合は、復号作業を終了する。また、最後のセルでない場合は、セルを移動して（ステップ２０９）、スタートに戻り、処理を続行する。一方、上記のコピー処理をした画素データが最後の画素データでないときは、走査方向に１ドット進んで、画素を特定したのち（ステップ２０７）、上記と同様な処理を順次行う。
【００３７】
なお、仮想セルと圧縮処理対象セルがオーバーラップする位置関係にある場合でも、図４のフローチャートどおりに処理すれば問題はない。図５において、仮想セルの最も左上の画素である画素「Ａ」は、いかなる場合にあってもオーバーラップすることはないため、まず画素「Ａ」を圧縮処理対象セル内の該当する位置（この場合、圧縮処理対象セル左上の「Ａ」の位置）にコピーする。以下、同様に走査方向に従ってコピーするが、仮想セルの３行目の「Ｑ」「Ｒ」の次の画素「Ａ」はすでにコピーされて存在するため、その画素を用いて再度コピーすることができる。こうして、仮想セルと圧縮処理対象セルがオーバーラップする位置関係にある場合でも最後まで復号化することができる。
【００３８】
以上、図面を参照して本発明の実施の形態について詳述してきたが、具体的な構成はこれらの実施の形態に限られるものではなく、この発明の要旨を逸脱しない範囲の設計等も含まれる。例えば、本発明の実施の形態においては、圧縮処理対象セルおよび仮想セルの大きさを８ドット（画素）×８ドット（画素）のサイズとしたが、これは圧縮をする画像の種類により、最も圧縮効率を上げられるような任意のサイズとしてよい。
【００３９】
また、同様に、仮想セルによる検索範囲についても画像の種類や画像データを処理するシステムの内容に応じて、適宜決定してよい。また、本発明の実施の形態においては、仮想セルを１ドット（画素）ずつ動かして、同一の画素データを有するエリアを検索する例について説明したが、仮想セルの移動量については、これに限られるわけではなく、任意としてよい。
【００４０】
【発明の効果】
以上のように、この発明によれば、従来、固定化されたセルとの間でのみ行われていた圧縮処理対象セルとの同一の画素データを有するか否かの検索を、セルという境界を取り除いた検索範囲内において行うこととしたため、同一の画素データを有するエリアを検索できる確率が高く、従来よりも高い圧縮率を期待できるという効果がある。また、従来の方式では、データの圧縮をあまり期待できなかった画像データにおいても、十分な圧縮率を期待できる。
【００４１】
また、本発明においては、符号化処理の段階で、本来記録されるべき画素データに代えて、圧縮処理対象セルに対する検索エリアの移動量に相当する位置のオフセットデータを記録することとしたため、十分な圧縮率を期待できる。加えて、伸張処理の段階では、位置のオフセットデータを読み出し、圧縮処理対象セルからこの位置のオフセットデータに相当する分だけ移動をした場所にあるすでに伸張処理の終わったエリアの画素データをコピーすることにより、容易にもとの画像データを完全に復元できるという効果がある。
【００４２】
また、さらに、本発明においては、圧縮対象セルと同一の画素データを有するエリアを検索する範囲に、圧縮対象セルも含めたことから、グラデーション処理された画像のように多少複雑な画像でも、従来以上の圧縮の効果が期待できる。
【００４３】
また、さらに、本発明においては、上述の画像データを圧縮する方法をプログラムとしても定義したことから、コンピュータを用いた画像データ処理システムにおいては、直ちに、本発明に係る画像データの圧縮処理を実行することができる。
【図面の簡単な説明】
【図１】本発明の実施の形態に係る画像データの圧縮方法およびデータ構造を示す図である。
【図２】本発明の実施の形態に係る仮想セルを検索範囲内で移動させる場合の処理の一部を示したフローチャートである。
【図３】本発明の実施の形態に係る仮想セルを検索範囲内で移動させる場合の処理の一部を示したフローチャートである。
【図４】本発明の実施の形態に係る画像データの復号処理を示したフローチャートである。
【図５】本発明の実施の形態に係る圧縮処理対象セルと仮想セルが重複する場合の復号化方法を示した図である。
【図６】本発明の実施の形態に係る圧縮処理時およびデータ復号時における画像データの走査方法を示す図である
【図７】従来例であるセル参照圧縮方式による圧縮方法を示す図である。
【符号の説明】
１・・・検索範囲、　２・・・圧縮処理対象セル、　３・・・仮想セル
【図１】
2004048091.tif 000003
【図２】
2004048091.tif 000004
【図３】
2004048091.tif 000005
【図４】
2004048091.tif 000006
【図５】
2004048091.tif 000007
【図６】
2004048091.tif 000008
【図７】
2004048091.tif 000009