【０００１】
【発明の属する技術分野】
本発明は、画像データの圧縮方法、プログラムおよびその装置に関する。
【０００２】
【従来の技術】
一般に、画像データは、そのデータ量が膨大であるため、これらのデータを記憶し、処理し、通信手段により送受信するためにかかるコストを低減する目的でデータの圧縮が行われている。画像データを圧縮する手法としては、ランレングスやハフマン符号、算術符号等の古典的な圧縮方法から、隣接するセル間で一致するパターンを見つけるセル参照圧縮方式、そして、ＪＰＥＧ（Ｊｏｉｎｔ Ｐｈｏｔｏｇｒａｐｈｉｃ Ｅｘｐｅｒｔｓ Ｇｒｏｕｐ）やＭＰＥＧ（Ｍｏｖｉｎｇ Ｐｉｃｔｕｒｅ Ｅｘｐｅｒｔｓ Ｇｒｏｕｐ）等に至るまでの多数のアルゴリズムが存在する。
【０００３】
これらの画像データ圧縮方法のうち、ランレングス等の古典的な圧縮方法やセル参照圧縮方式等のデータ圧縮方法は、特に、可逆方式と呼ばれ、原画像と復号画像の品質が同じ圧縮方式であって、画像品質が良好である反面、圧縮率があまり高くないという特色がある。一方で、ＪＰＥＧやＭＰＥＧのようなデータ圧縮方式は、特に、非可逆方式と呼ばれ、復号画像の品質が原画像よりも劣るが、高い圧縮率が得られるという特色がある。したがって、どのような圧縮方式を選択するかは、システム上の用途や画像品質の重要度および取り扱うデータ量等により、適宜、決定する必要がある。
【０００４】
図４は、画像データ圧縮方式の１つであるセル参照圧縮方式を用いた画像データの圧縮方法を示したものである。
セル参照圧縮方式では、８ドット（画素）×８ドット（画素）の画像データのかたまりをセルという単位で定義し、画面をこのセルの単位で分割するとともに、圧縮しようとするセルに隣接するセルの中に、圧縮しようとするセルのパターンと同一のパターンが存在するか否かを検索する。そして、同一のパターンを有するセルが検索できたときは、本来、記録すべき画像の実データに代えて、同一のパターンを有するセルの位置を示すデータのみを記録して、画像データの圧縮を行う方式のものである。
【０００５】
これを図４により、もう少し詳しく説明する。いま、圧縮をしようとするセルを図４の右下隅のセルとすると、参照すべきセルは図に実線で示す３つのセル（参照セルＩ、ＩＩ、ＩＩＩ）になる。また、図４（ｂ）および（ｃ）は、セル参照圧縮方式が実行された後のデータ符号化のしくみを示した図である。これによると、圧縮をしようとするセルについては、参照するセルとの間でセル内の画像パターンが一致するか否かの判断が行われ、一致するセルがあった場合は、その一致したセルの位置を示す２ビットのヘッダデータを記録するのみで、実際の画像データを省略する符号化を行う。また、隣接するセルに画像パターンが一致するセルがなかった場合は、２ビットのヘッダデータ「００」に続いて実際の画像データを記録する符号化を行う。
【０００６】
【発明が解決しようとする課題】
しかし、上記のように、従来、可逆方式の画像圧縮方法であるセル参照圧縮方式を採用していたシステムにおいても、扱う画像データが時代とともに複雑化したことから、従来のように、画面をセルという固定された枠で区切って、このセルの中から被圧縮セルと同パターンを有するセルを検索するやり方では、十分な圧縮率が得られない場合が生じてきた。一方で、圧縮率を高めるために、非可逆方式を採用するには、扱うデータ量やコストの面からみて妥当でないケースもある。
【０００７】
そこで、本発明は、上述した問題点に鑑みてなされたものであって、従来の可逆方式の圧縮方法を踏襲しながら、同一パターンの検出方法や符号化の方法を改良することにより、低コストで圧縮率の高い画像データの圧縮方法、プログラムおよび装置を提供することを目的とする。
【０００８】
【課題を解決するための手段】
前記課題を解決するため、本発明は、以下の手段を提案している。
請求項１に係る発明は、複数の画素データからなる画像データを複数のセルに分割する第１のステップと、これらのセルの中から圧縮処理の対象となる圧縮対象セルを特定する第２のステップと、前記画像データの中から前記圧縮対象セルと同一の画素データを有する当該圧縮対象セル自体以外のエリアを検索する第３のステップと、前記圧縮対象セルと同一の画素データを有するエリアを発見したときは、前記圧縮対象セルと前記エリアとの間の位置のオフセットデータを前記圧縮対象セルの画素データを表す情報として記録する第４のステップとからなる画像データの圧縮方法を提案している。
また、第３のステップにおける「同一の画素データ」とは、圧縮対象セルと検索エリアの相互に対応する画素データがすべて同一である場合のほか、圧縮対象セルと検索エリアの対応する画素データの差分値が画質に影響しない範囲の値である場合を含むものとする。
【０００９】
請求項４に係る発明は、複数の画素データからなる画像データを複数のセルに分割する第１のステップと、これらのセルの中から圧縮処理の対象となる圧縮対象セルを特定する第２のステップと、前記画像データの中から前記圧縮対象セルと同一の画素データを有する当該圧縮対象セル自体以外のエリアを検索する第３のステップと、前記圧縮対象セルと同一の画素データを有するエリアを発見したときは、前記圧縮対象セルと前記エリアとの間の位置のオフセットデータを前記圧縮対象セルの画素データを表す情報として記録する第４のステップとをコンピュータに実行させるためのプログラムを提案している。
【００１０】
これらの発明によれば、画像データの圧縮処理の対象となるセルと同一の画素データを有するエリアを、分割されたセルに限定されることなく、検索する方法としたので、検索範囲内のあらゆる画素データからなるエリアを検索の対象とすることができる。また、検索範囲内で、同一の画素データを有するエリアが発見されたときは、処理対象のセルに対する該当エリアまでの移動量に相当する位置のオフセットデータを圧縮処理対象セルの画素データとして記録する方法としたので、記録すべきデータ量を減少させることができる。
【００１１】
請求項２に係る発明は、請求項１に記載された画像データの圧縮方法において、前記第３のステップが、圧縮処理の終了したセルおよび前記圧縮対象セルからなる画像データの範囲からエリアを検索する画像データの圧縮方法を提案している。
【００１２】
請求項５に係る発明は、請求項３に記載されたコンピュータに実行させるためのプログラムについて、前記第３のステップが、圧縮処理の終了したセルおよび前記圧縮対象セルからなる画像データの範囲からエリアを検索するコンピュータに実行させるためのプログラムを提案している。
【００１３】
これらの発明によれば、各圧縮処理対象セルの画素データを表す情報は、すでに圧縮処理されたデータに基づいて構成されるので、これを伸張する際には、伸張処理された画像データをもとに画像データが再現されることとなり正確な再現が可能となる。
【００１４】
請求項３に係る発明は、請求項１または請求項２に記載された画像データの圧縮方法において、前記第３のステップが、前記圧縮対象セルを基点として、順次遠ざかる方向にエリアを検索する画像データの圧縮方法を提案している。
【００１５】
請求項６に係る発明は、請求項４または請求項５に記載されたコンピュータに実行させるためのプログラムにおいて、前記第３のステップが、前記圧縮対象セルを基点として、順次遠ざかる方向にエリアを検索するコンピュータに実行させるためのプログラムを提案している。
【００１６】
これらの発明によれば、圧縮対象セルと同一の画素データを有するエリアを検索する順序を一般的な画像データの構成を考慮して、圧縮対象セルを基点として、その近傍から行うこととしたので、一般的な画像データの構成から考えても、早いタイミングで同一の画素データを有するエリアを検索できる。
【００１７】
請求項７に係る発明は、複数の画素データからなる画像データを複数のセルに分割するセル分割手段と、これらのセルの中から圧縮処理の対象となる圧縮対象セルを特定する圧縮対象特定手段と、前記画像データの中から前記圧縮対象セルと同一の画素データを有する当該圧縮対象セル自体以外のエリアを検索するエリア検索手段と、前記圧縮対象セルと同一の画素データを有するエリアを発見したときは、前記圧縮対象セルと前記エリアとの間の位置のオフセットデータを前記圧縮対象セルの画素データを表す情報として記録するデータ圧縮処理手段とからなる画像データの圧縮装置を提案している。
【００１８】
この発明によれば、セル分割手段により、画像データを複数のセルに分割し、圧縮対象特定手段により圧縮処理の対象となるセルを特定する。そして、エリア検索手段により、同一の画素データを有する圧縮対象セル自体以外のエリアを検索して、同一の画素データを有するエリアが発見されたときは、データ圧縮処理手段により、処理対象のセルに対する該当エリアまでの移動量に相当するオフセットデータが圧縮処理対象セルの画素データとして記録される。したがって、エリア検索手段によって、分割されたセルに限定されることなく、検索範囲内のあらゆる画像データを検索の対象とすることができ、また、データ圧縮処理手段によって、記録すべきデータ量を減少させることができる。
【００１９】
請求項８に係る発明は、請求項７に記載された画像データの圧縮装置について、前記エリア検索手段が、圧縮処理の終了したセルおよび前記圧縮対象セルからなる画像データの範囲からエリアを検索する画像データの圧縮装置を提案している。 この発明によれば、エリア検索手段が検索するエリアを、圧縮処理が終了したセルと圧縮処理対象セルを一部に含む範囲とする装置としたことから、圧縮処理対象セルと同一の画素データを有するエリアを検索できる確率が高くなる。
【００２０】
請求項９に係る発明は、請求項７または請求項８に記載された画像データの圧縮装置において、前記エリア検索手段が、前記圧縮対象セルを基点として、順次遠ざかる方向にエリアを検索する画像データの圧縮装置を提案している。
【００２１】
この発明によれば、エリア検索手段が、圧縮対象セルと同一の画素データを有するエリアを検索する順序を一般的な画像データの構成を考慮して、圧縮対象セルを基点として、その近傍から行うこととしたので、早いタイミングで同一の画素データを有するエリアを検索できる。
【００２２】
【発明の実施の形態】
以下、本発明の一実施形態に係る画像データの圧縮方法、プログラムおよび装置について図１から図３を参照して詳細に説明する。
図１は、本発明の一実施形態に係る画像データの圧縮方法を示す図であり、同図（ａ）は、圧縮処理対象セルと同一の画素データを有するエリアを検索する場合の概念図を、同図（ｂ）は、同一の画素データを有するエリアが発見できたときに記録されるデータのデータ構造を、同図（ｃ）は、同一の画素データを有するエリアが検索できなかったときに記録されるデータのデータ構造を、それぞれ示している。また、同図（ｄ）は、Ｘ軸、Ｙ軸のオフセット量がそれぞれＸ−Ｘ１＝５、Ｙ−Ｙ１＝７の場合に記録されるデータ例を示している。
【００２３】
ここで、前提として全画面は、図６に示すように３２０ドット×２４０ドット（４０セル×３０セル）の長方形とする。また、図１（ａ）は、全画面における１２００個のセルの内、ある特定された１つのセルと、そのセルを圧縮処理対象とした場合の検索範囲を示す。検索範囲は図のように圧縮処理対象セルから左に４セル分、上に４セル分とし、圧縮処理対象セルも含めて５セル×５セル（４０ドット×４０ドット）とする。なお、全画面中における圧縮処理対象セルを特定する順番については、次のとおりとする。まず、図６において、全画面中の最も左上にあるセルの右隣のセル（セル２）を特定する。次に、セル２の圧縮処理を実行し、終了後はその右隣のセル（セル３）に移る。以下、同様に、図６の矢印のとおりにセル２→セル３→・・・→セル４０→セル４１→セル４２・・・→セル１２００と進む。なお、セル１は圧縮処理対象とはしないため、後に詳細に説明する図１（ｃ）の方法にて記録する。また、セルを特定したときのセル検索範囲（４０ドット×４０ドット）が画面からはみ出してしまう場合は、画面内を検索範囲とする。
【００２４】
点線の囲みで示されている８ドット（画素）×８ドット（画素）のブロックは、圧縮処理対象セルと同一の画素データを有する仮想セルと呼ばれるものである。仮想セルは、検索範囲内において圧縮処理対象セルと同一の画素データを有するエリアを発見する際の架空のセルであって、圧縮処理対象セルと仮想セルの左上隅に書かれている黒点はポインタと呼ばれ、仮想セルは、圧縮処理対象セルのポインタを原点として、画像データを描画するラインに平行な軸方向と、これに直交する軸方向にそれぞれ１ドット（画素）ずつ移動させることができる。なお、検索エリアのセルと仮想セルの画素データが同一であるか否かは、相互に対応する画素データの差分を取って、これが画質に影響しない所定の範囲内の値であるか否かを判断することにより行われる。
【００２５】
これらのポインタは、仮想セルが検索範囲内で圧縮処理対象セルと同一の画素データを有するエリアを発見した場合に、圧縮処理対象セルと仮想セルの相対位置（オフセット量）を算出するために用いられる、いわゆる、それぞれのセルの座標値を示す役割を果たすものである。なお、ポインタの（Ｘ、Ｙ）値の正方向を示す軸の向きは、画面上をデ−タが走査する向きと同一であることから、Ｘ軸の正方向は画面を正面から見たときの右方向を、Ｙ軸の正方向は同様に下方向となる。以後、この向きを各軸の正方向として説明する。
【００２６】
図１（ｂ）中、左端には、オフセット量の範囲が記載され、これに続いてヘッダデータと、実際の画像データに代わって記録されるオフセットデータとの関係を示すデータ構造が記載されている。
本発明の実施形態の場合、オフセット量は図１のように、大きく３つの領域、［Ｉ］、［ＩＩ］、［ＩＩＩ］に分けられており、これに準じて、符号化されるデータの長さが異なっている。これは、画像データの性質上、圧縮処理対象セルの近傍ほど、圧縮処理対象セルと同一の画素データを有するエリアが出現する可能性が高いと考えられることから、圧縮処理対象セルからのオフセット量が少ないものほど、記録されるデータを短くする可変長符号として、データ圧縮の効果を上げることを意図したものである。
【００２７】
具体的なデータ構造は、実際の画像データあるいは本発明におけるオフセットデータと、これらのデータの先頭に付加され後続のデータの種別を示すヘッダデータとから構成されており、オフセットデータには、ヘッダデータのデータビット長に対して１ビット多いビット長が割り当てられている。また、オフセットの演算式は、圧縮処理対象セルのポインタを（Ｘ、Ｙ）とし、仮想セルのポインタを（Ｘ１、Ｙ１）としたときのものであり、前述した、Ｘ軸、Ｙ軸の正方向の向きを考慮して、オフセットの値が正の数になるよう符号が与えられている。
【００２８】
例えば、図１（ｂ）の演算式で表されるオフセット量が、Ｘ軸、Ｙ軸ともに７以下であれば、オフセット量は、Ｘ軸、Ｙ軸それぞれ３ｂｉｔのデータで表すことができる。ヘッダが「１，０」の時は、「０」の後の３ｂｉｔがＸ軸のオフセット量を表し、その後の３ｂｉｔがＹ軸のオフセット量を表すことになる。したがって、オフセット量がＸ−Ｘ１＝５、Ｙ−Ｙ１＝７の場合のデータは図１（ｄ）のようになる。なお、検索範囲を検索しても、圧縮処理対象セルと同一の画素データを有するエリアを検索できなかったときは、ヘッダデータを「０」のみの１ビットとして、その後に、６４バイトの実際の画像デ−タ、すなわち圧縮処理対象セルの画像データをそのまま記録する。これが図１（ｃ）に記載されている。
【００２９】
図２、図３は、仮想セルを検索範囲内で移動させる場合の処理を示したフローチャートである。ただし、図２、図３の実施の形態では、検索範囲を圧縮処理対象セルを含めた４０ドット（画素）×４０ドット（画素）としている。
図２から、まず、圧縮処理対象セルが画面の中の上端または左端に位置するか否かの判断を行う（ステップ１０１）。判断の結果、画面の上端または左端でないと確認されたときは、仮想セルをＸ軸のマイナス方向に１ドット移動し（ステップ１０２）、仮想セルと検索エリアのパターンが一致するか否かを判断する（ステップ１０３）。判断の結果、両者のパターンが一致したときは、ヘッダデータとオフセットデータを作成し（ステップ１０４）、次の圧縮対象セルに移動する（ステップ１０５）とともに、処理をスタートに戻す。
【００３０】
仮想セルと検索エリアのパターンが一致しなかったときは、Ｘ軸方向の移動量がすでに３１ドットに達しているか、あるいは、画面の端に到達しているかの判断を行い（ステップ１０６）、移動量がまだ３１ドットに達しておらず、画面の端でもないときはステップ１０２の戻って、仮想セルをＸ軸のマイナス方向に１ドット移動して、上記と同様の処理を再び行う。一方、移動量がすでに３１ドットに達している、あるいは、画面の端に到達していると判断されたときには、次に、Ｙ軸方向の移動量がすでに３１ドットに達しているか、あるいは、画面の端に到達しているかの判断を行う（ステップ１０７）。判断の結果、Ｙ軸方向の移動量は３１ドットに達しておらず、画面の端にも到達していない場合は、仮想セルのＸ軸を初期に戻すとともに、Ｙ軸のマイナス方向に１ドット移動して（ステップ１０８）、仮想セルと検索エリアのパターンが一致するか否かを判断する。また、Ｙ軸方向の移動量がすでに３１ドットに達しており、あるいは、画面の端に到達していると判断されたときは、ヘッダデータを「０」とし、その後に実データを付加した画像データを作成し（ステップ１０９）、次の圧縮対象セルに移動する（ステップ１１０）とともに、処理をスタートに戻す。
【００３１】
次に、図３により、圧縮処理対象セルが画面の中の上端または左端に位置する場合には、そのセルが画面の左端にあるのか否かの判断を行う（ステップ１１１）。判断の結果、圧縮処理対象セルが画面の左端にあるときは、仮想セルをＹ軸のマイナス方向に１ドット移動して仮想セルと検索エリアのパターンが一致するか否かを判断する（ステップ１１３）。判断の結果、両者のパターンが一致したときは、ヘッダデータとオフセットデータを作成し（ステップ１１４）、次の圧縮対象セルに移動する（ステップ１１５）とともに、処理をスタートに戻す。
【００３２】
仮想セルと検索エリアのパターンが一致しなかったときは、Ｙ軸方向の移動量がすでに３１ドットに達しているか、あるいは、画面の端に到達しているかの判断を行い（ステップ１１６）、移動量がすでに３１ドットに達している、あるいは、画面の端に到達していると判断されたときには、ヘッダデータを「０」とし、その後に実データを付加した画像データを作成し（ステップ１１７）、次の圧縮対象セルに移動する（ステップ１１５）とともに、処理をスタートに戻す。一方、移動量がまだ３１ドットに達しておらず、画面の端でもないときはステップ１１２の戻って、仮想セルをＹ軸のマイナス方向に１ドット移動して、上記と同様の処理を再び行う。
【００３３】
圧縮処理対象セルが画面の中の上端に位置するが、画面の左端ではない場合は、仮想セルをＸ軸のマイナス方向に１ドット移動して（ステップ１１８）、仮想セルと検索エリアのパターンが一致するか否かを判断する（ステップ１１９）。判断の結果、両者のパターンが一致したときは、ヘッダデータとオフセットデータを作成し（ステップ１２０）、次の圧縮対象セルに移動する（ステップ１１５）とともに、処理をスタートに戻す。
【００３４】
仮想セルと検索エリアのパターンが一致しなかったときは、Ｘ軸方向の移動量がすでに３１ドットに達しているか、あるいは、画面の端に到達しているかの判断を行い（ステップ１２１）、移動量がすでに３１ドットに達している、あるいは、画面の端に到達していると判断されたときには、ヘッダデータを「０」とし、その後に実データを付加した画像データを作成し（ステップ１２２）、次の圧縮対象セルに移動する（ステップ１１５）とともに、処理をスタートに戻す。一方、移動量がまだ３１ドットに達しておらず、画面の端でもないときはステップ１１８に戻って、仮想セルをＸ軸のマイナス方向に１ドット移動して、上記と同様の処理を再び行う。
【００３５】
次に、復号化の処理について、図４のフローチャートを用いて説明する。前記の圧縮方法にて圧縮されたデータを受けた復号装置は、図６におけるセル１をスタートして矢印の順番に復号する。具体的な処理の手順としては、図４から、まず、ヘッダデータが「０」であるか否かが確認される（ステップ２０１）。確認の結果、ヘッダデータが「０」である場合は、ヘッダデータ後の実データに基づいて画像が形成され（ステップ２０２）、次いで、このセルが最後のセルであるか否かの判断がされる（ステップ２０８）。判断の結果、これが最後のセルである場合は、復号処理を終了し、そうでない場合には、セルを移動して（ステップ２０９）、スタートに戻り、処理を続行する。
【００３６】
一方、ヘッダデータが「０」でない場合には、オフセットデータから同一のパターンを有するエリアを特定し（ステップ２０３）、まず、このエリアの最も左上の画素データを特定して（ステップ２０４）、この特定された画素データをセルにコピーする（ステップ２０５）。この作業を順次進めていき、最後の画素データについて処理を終了したときは（ステップ２０６）、今、復号処理をしたセルが最後のセルであるかどうかを確認し（ステップ２０８）、最後のセルである場合は、復号作業を終了する。また、最後のセルでない場合は、セルを移動して（ステップ２０９）、スタートに戻り、処理を続行する。一方、上記のコピー処理をした画素データが最後の画素データでないときは、走査方向に１ドット進んで、画素を特定したのち（ステップ２０７）、上記と同様な処理を順次行う。
【００３７】
なお、仮想セルと圧縮処理対象セルがオーバーラップする位置関係にある場合でも、図４のフローチャートどおりに処理すれば問題はない。図５において、仮想セルの最も左上の画素である画素「Ａ」は、いかなる場合にあってもオーバーラップすることはないため、まず画素「Ａ」を圧縮処理対象セル内の該当する位置（この場合、圧縮処理対象セル左上の「Ａ」の位置）にコピーする。以下、同様に走査方向に従ってコピーするが、仮想セルの３行目の「Ｑ」「Ｒ」の次の画素「Ａ」はすでにコピーされて存在するため、その画素を用いて再度コピーすることができる。こうして、仮想セルと圧縮処理対象セルがオーバーラップする位置関係にある場合でも最後まで復号化することができる。
【００３８】
以上、図面を参照して本発明の実施の形態について詳述してきたが、具体的な構成はこれらの実施の形態に限られるものではなく、この発明の要旨を逸脱しない範囲の設計等も含まれる。例えば、本発明の実施の形態においては、圧縮処理対象セルおよび仮想セルの大きさを８ドット（画素）×８ドット（画素）のサイズとしたが、これは圧縮をする画像の種類により、最も圧縮効率を上げられるような任意のサイズとしてよい。
【００３９】
また、同様に、仮想セルによる検索範囲についても画像の種類や画像データを処理するシステムの内容に応じて、適宜決定してよい。また、本発明の実施の形態においては、仮想セルを１ドット（画素）ずつ動かして、同一の画素データを有するエリアを検索する例について説明したが、仮想セルの移動量については、これに限られるわけではなく、任意としてよい。
【００４０】
【発明の効果】
以上のように、この発明によれば、従来、固定化されたセルとの間でのみ行われていた圧縮処理対象セルとの同一の画素データを有するか否かの検索を、セルという境界を取り除いた検索範囲内において行うこととしたため、同一の画素データを有するエリアを検索できる確率が高く、従来よりも高い圧縮率を期待できるという効果がある。また、従来の方式では、データの圧縮をあまり期待できなかった画像データにおいても、十分な圧縮率を期待できる。
【００４１】
また、本発明においては、符号化処理の段階で、本来記録されるべき画素データに代えて、圧縮処理対象セルに対する検索エリアの移動量に相当する位置のオフセットデータを記録することとしたため、十分な圧縮率を期待できる。加えて、伸張処理の段階では、位置のオフセットデータを読み出し、圧縮処理対象セルからこの位置のオフセットデータに相当する分だけ移動をした場所にあるすでに伸張処理の終わったエリアの画素データをコピーすることにより、容易にもとの画像データを完全に復元できるという効果がある。
【００４２】
また、さらに、本発明においては、圧縮対象セルと同一の画素データを有するエリアを検索する範囲に、圧縮対象セルも含めたことから、グラデーション処理された画像のように多少複雑な画像でも、従来以上の圧縮の効果が期待できる。
【００４３】
また、さらに、本発明においては、上述の画像データを圧縮する方法をプログラムとしても定義したことから、コンピュータを用いた画像データ処理システムにおいては、直ちに、本発明に係る画像データの圧縮処理を実行することができる。
【図面の簡単な説明】
【図１】本発明の実施の形態に係る画像データの圧縮方法およびデータ構造を示す図である。
【図２】本発明の実施の形態に係る仮想セルを検索範囲内で移動させる場合の処理の一部を示したフローチャートである。
【図３】本発明の実施の形態に係る仮想セルを検索範囲内で移動させる場合の処理の一部を示したフローチャートである。
【図４】本発明の実施の形態に係る画像データの復号処理を示したフローチャートである。
【図５】本発明の実施の形態に係る圧縮処理対象セルと仮想セルが重複する場合の復号化方法を示した図である。
【図６】本発明の実施の形態に係る圧縮処理時およびデータ復号時における画像データの走査方法を示す図である
【図７】従来例であるセル参照圧縮方式による圧縮方法を示す図である。
【符号の説明】
１・・・検索範囲、 ２・・・圧縮処理対象セル、 ３・・・仮想セル[0001]
TECHNICAL FIELD OF THE INVENTION
The present invention relates to a method, a program and an apparatus for compressing image data.
[0002]
[Prior art]
In general, since image data has a huge data amount, data compression is performed in order to reduce costs for storing, processing, and transmitting and receiving the data by a communication unit. Methods for compressing image data include classical compression methods such as run-length, Huffman codes, and arithmetic codes, cell reference compression methods for finding matching patterns between adjacent cells, and JPEG (Joint Photographic Experts Group). And a number of algorithms up to MPEG (Moving Picture Experts Group) and the like.
[0003]
Among these image data compression methods, classical compression methods such as run-length and data compression methods such as a cell reference compression method are particularly referred to as a lossless method, in which the original image and the decoded image have the same quality. Thus, the image quality is good, but the compression ratio is not so high. On the other hand, a data compression method such as JPEG or MPEG is particularly called an irreversible method, in which the quality of a decoded image is inferior to that of an original image, but has a feature that a high compression ratio can be obtained. Therefore, it is necessary to appropriately determine what kind of compression method to select depending on the use on the system, the importance of image quality, the amount of data to be handled, and the like.
[0004]
FIG. 4 shows a method of compressing image data using a cell reference compression method, which is one of the image data compression methods.
In the cell reference compression method, a block of image data of 8 dots (pixels) × 8 dots (pixels) is defined in units of cells, and the screen is divided in units of cells, and cells adjacent to the cells to be compressed are defined. Is searched for the same pattern as that of the cell to be compressed. Then, when a cell having the same pattern can be searched, only data indicating the position of the cell having the same pattern is recorded instead of the actual data of the image to be recorded, and compression of the image data is performed. It is a method of performing.
[0005]
This will be described in more detail with reference to FIG. Now, assuming that the cell to be compressed is the cell at the lower right corner of FIG. 4, the cells to be referred to are three cells (reference cells I, II, and III) indicated by solid lines in FIG. FIGS. 4B and 4C are diagrams showing the structure of data encoding after the cell reference compression method has been executed. According to this, for a cell to be compressed, it is determined whether or not the image pattern in the cell matches with the cell to be referenced, and if there is a matching cell, the matching cell is determined. The encoding is performed by only recording the 2-bit header data indicating the position of, and omitting the actual image data. If there is no cell whose image pattern matches an adjacent cell, encoding is performed to record the actual image data following the 2-bit header data “00”.
[0006]
[Problems to be solved by the invention]
However, as described above, even in a system that has conventionally adopted a cell reference compression method, which is a reversible image compression method, the image data to be handled has become more complicated with the times, and the screen has been changed to a cell as before. In the method of searching for cells having the same pattern as the cell to be compressed from among these cells by dividing the cell by a fixed frame, a sufficient compression ratio may not be obtained. On the other hand, adopting the irreversible method to increase the compression ratio may not be appropriate in terms of the amount of data to be handled and the cost.
[0007]
Therefore, the present invention has been made in view of the above-described problems, and has been made to reduce the cost by improving the same pattern detection method and encoding method while following the conventional lossless compression method. It is an object of the present invention to provide a method, a program and an apparatus for compressing image data having a high compression ratio.
[0008]
[Means for Solving the Problems]
In order to solve the above problems, the present invention proposes the following means.
According to the first aspect of the present invention, a first step of dividing image data composed of a plurality of pixel data into a plurality of cells, and a second step of specifying a compression target cell to be subjected to compression processing from these cells A third step of searching the image data for an area other than the compression target cell itself having the same pixel data as the compression target cell; and an area having the same pixel data as the compression target cell. A fourth step of recording offset data at a position between the compression target cell and the area as information representing pixel data of the compression target cell when the image data is found. I have.
The “same pixel data” in the third step means that the pixel data corresponding to the compression target cell and the search area are all the same, and that the pixel data corresponding to the compression target cell and the search area are the same. It is assumed that the difference value is a value in a range that does not affect the image quality.
[0009]
According to a fourth aspect of the present invention, there is provided a first step of dividing image data composed of a plurality of pixel data into a plurality of cells, and a second step of specifying a compression target cell to be subjected to compression processing from these cells. A third step of searching the image data for an area other than the compression target cell itself having the same pixel data as the compression target cell; and an area having the same pixel data as the compression target cell. And a fourth step of recording the offset data of the position between the compression target cell and the area as information representing the pixel data of the compression target cell when the computer finds it. ing.
[0010]
According to these inventions, an area having the same pixel data as a cell to be subjected to image data compression processing is searched for without being limited to divided cells. An area composed of pixel data can be a search target. When an area having the same pixel data is found in the search range, offset data at a position corresponding to the movement amount of the processing target cell to the corresponding area is recorded as pixel data of the compression processing target cell. With this method, the amount of data to be recorded can be reduced.
[0011]
According to a second aspect of the present invention, in the method for compressing image data according to the first aspect, the third step searches for an area from a range of image data including a cell for which compression processing has been completed and the compression target cell. A method of compressing image data is proposed.
[0012]
According to a fifth aspect of the present invention, in the program to be executed by the computer according to the third aspect, the third step is performed by changing an area from a range of image data including a cell for which compression processing has been completed and the compression target cell. Proposes a program to be executed by a computer for searching.
[0013]
According to these inventions, the information representing the pixel data of each compression processing target cell is configured based on the data that has already been subjected to the compression processing. Then, the image data is reproduced, so that accurate reproduction is possible.
[0014]
According to a third aspect of the present invention, in the image data compression method according to the first or second aspect, the third step includes searching for an area sequentially in a direction away from the compression target cell as a base point. We propose a data compression method.
[0015]
According to a sixth aspect of the present invention, in the program executed by the computer according to the fourth or fifth aspect, the third step searches for an area in a direction away from the compression target cell as a starting point. It proposes a program to be executed by a computer.
[0016]
According to these inventions, the order of searching for an area having the same pixel data as that of the compression target cell is determined starting from the compression target cell and its vicinity in consideration of the configuration of general image data. Even in consideration of the general configuration of image data, an area having the same pixel data can be searched at an early timing.
[0017]
According to a seventh aspect of the present invention, there is provided a cell dividing means for dividing image data composed of a plurality of pixel data into a plurality of cells, and a compression target specifying means for specifying a compression target cell to be subjected to compression processing from among these cells. And area search means for searching an area other than the compression target cell itself having the same pixel data as the compression target cell from the image data, and finding an area having the same pixel data as the compression target cell. In some cases, the present invention proposes an image data compression apparatus including data compression processing means for recording offset data at a position between the compression target cell and the area as information representing pixel data of the compression target cell.
[0018]
According to the present invention, the image data is divided into a plurality of cells by the cell dividing means, and the cells to be subjected to the compression processing are specified by the compression target specifying means. The area search means searches areas other than the compression target cell itself having the same pixel data, and when an area having the same pixel data is found, the data compression processing means Offset data corresponding to the movement amount to the corresponding area is recorded as pixel data of the compression processing target cell. Therefore, the image data within the search range can be searched by the area search means without being limited to the divided cells, and the amount of data to be recorded can be reduced by the data compression processing means. Can be done.
[0019]
According to an eighth aspect of the present invention, in the image data compression apparatus according to the seventh aspect, the area search unit searches an area from a range of image data including a cell for which compression processing has been completed and the compression target cell. An image data compression device has been proposed. According to the present invention, since the area to be searched by the area search means is set to be a range that includes the cell for which compression processing has been completed and the cell to be compressed as a part, the same pixel data as the cell to be compressed The probability of being able to search for the area that has it is increased.
[0020]
According to a ninth aspect of the present invention, in the image data compression apparatus according to the seventh or eighth aspect, the area search means searches for areas sequentially in a direction away from the compression target cell as a base point. Has proposed a compression device.
[0021]
According to the present invention, the area search unit searches the area having the same pixel data as the compression target cell in order from the neighborhood of the compression target cell, taking the compression target cell as a base point in consideration of a general image data configuration. Therefore, an area having the same pixel data can be searched at an early timing.
[0022]
BEST MODE FOR CARRYING OUT THE INVENTION
Hereinafter, an image data compression method, program, and apparatus according to an embodiment of the present invention will be described in detail with reference to FIGS.
FIG. 1 is a diagram illustrating a method of compressing image data according to an embodiment of the present invention. FIG. 1A is a conceptual diagram illustrating a case where an area having the same pixel data as a compression target cell is searched. FIG. 3B shows a data structure of data recorded when an area having the same pixel data is found, and FIG. 3C shows a case where an area having the same pixel data cannot be searched. Shows the data structure of the data recorded in the. FIG. 4D shows an example of data recorded when the X-axis and Y-axis offset amounts are XX1 = 5 and YY1 = 7, respectively.
[0023]
Here, it is assumed that the entire screen is a rectangle of 320 dots × 240 dots (40 cells × 30 cells) as shown in FIG. FIG. 1A shows one specified cell out of 1200 cells in the entire screen and a search range when the cell is subjected to compression processing. As shown in the figure, the search range is 4 cells to the left and 4 cells above the compression processing target cell, and includes 5 cells × 5 cells (40 dots × 40 dots) including the compression processing cell. The order in which the compression processing target cells in the entire screen are specified is as follows. First, in FIG. 6, a cell (cell 2) on the right of the upper leftmost cell in the entire screen is specified. Next, the compression process of the cell 2 is executed, and after the completion, the process moves to the cell on the right (cell 3). Hereinafter, similarly, the process proceeds in the order of cell 2 → cell 3 →... → cell 40 → cell 41 → cell 42. Since the cell 1 is not to be subjected to the compression processing, it is recorded by the method shown in FIG. If a cell search range (40 dots × 40 dots) when a cell is specified protrudes from the screen, the search range is set within the screen.
[0024]
The block of 8 dots (pixels) × 8 dots (pixels) indicated by a dotted line is called a virtual cell having the same pixel data as the compression target cell. The virtual cell is a fictitious cell used to find an area having the same pixel data as the compression processing target cell in the search range. The black point written in the upper left corner of the compression processing target cell and the virtual cell is a pointer. The virtual cell can be moved by one dot (pixel) in each of an axis direction parallel to a line on which image data is drawn and an axis direction orthogonal thereto, with the pointer of the compression processing target cell as the origin. . Whether or not the cell data of the search area and the pixel data of the virtual cell are the same is determined by taking the difference between the corresponding pixel data and determining whether or not this is a value within a predetermined range that does not affect the image quality. This is done by making a judgment.
[0025]
These pointers are used to calculate a relative position (offset amount) between the compression processing target cell and the virtual cell when the virtual cell finds an area having the same pixel data as the compression processing target cell within the search range. That is, it serves to indicate the coordinate value of each cell. Since the direction of the axis indicating the positive direction of the (X, Y) value of the pointer is the same as the direction in which data scans on the screen, the positive direction of the X axis is when the screen is viewed from the front. , And the positive direction of the Y-axis is similarly downward. Hereinafter, this direction will be described as the positive direction of each axis.
[0026]
In FIG. 1B, at the left end, a range of the offset amount is described, followed by a data structure indicating a relationship between the header data and the offset data recorded in place of the actual image data. I have.
In the embodiment of the present invention, the offset amount is roughly divided into three regions, [I], [II], and [III], as shown in FIG. The lengths are different. This is because, due to the nature of image data, it is considered that an area having the same pixel data as the compression processing target cell is more likely to appear near the compression processing target cell, and thus the offset amount from the compression processing target cell is high. This is intended to increase the effect of data compression by using a variable-length code that shortens the data to be recorded as the number becomes smaller.
[0027]
The specific data structure is composed of actual image data or offset data according to the present invention, and header data added to the head of these data and indicating the type of subsequent data. Is assigned a bit length that is one bit greater than the data bit length. The offset expression is obtained when the pointer of the compression target cell is (X, Y) and the pointer of the virtual cell is (X1, Y1). Considering the direction of the direction, a sign is given so that the value of the offset is a positive number.
[0028]
For example, if the offset amount represented by the operation formula in FIG. 1B is 7 or less for both the X axis and the Y axis, the offset amount can be represented by 3-bit data for each of the X axis and the Y axis. When the header is “1, 0”, the three bits after “0” represent the X-axis offset amount, and the subsequent three bits represent the Y-axis offset amount. Therefore, data when the offset amount is X-X1 = 5 and Y-Y1 = 7 is as shown in FIG. If an area having the same pixel data as that of the compression target cell cannot be searched for even when the search range is searched, the header data is set to 1 bit of only “0”, and then the actual 64 bytes of the header data are set. The image data, that is, the image data of the compression target cell is recorded as it is. This is illustrated in FIG.
[0029]
FIG. 2 and FIG. 3 are flowcharts showing processing when a virtual cell is moved within a search range. However, in the embodiment of FIGS. 2 and 3, the search range is set to 40 dots (pixels) × 40 dots (pixels) including the compression processing target cell.
As shown in FIG. 2, first, it is determined whether or not the compression processing target cell is located at the upper end or the left end in the screen (step 101). If it is determined that the virtual cell is not at the top or left end of the screen, the virtual cell is moved by one dot in the minus direction of the X axis (step 102), and it is determined whether or not the pattern of the virtual cell matches the pattern of the search area. (Step 103). If the two patterns match as a result of the determination, header data and offset data are created (step 104), the process moves to the next compression target cell (step 105), and the process returns to the start.
[0030]
If the pattern of the virtual cell does not match the pattern of the search area, it is determined whether the movement amount in the X-axis direction has already reached 31 dots or has reached the edge of the screen (step 106). If the amount has not yet reached 31 dots and is not at the end of the screen, the process returns to step 102, where the virtual cell is moved by one dot in the minus direction of the X axis, and the same processing as above is performed again. On the other hand, if it is determined that the movement amount has already reached 31 dots or has reached the edge of the screen, then it is determined whether the movement amount in the Y-axis direction has already reached 31 dots or (Step 107). If the result of the determination is that the movement amount in the Y-axis direction has not reached 31 dots and has not reached the edge of the screen, the X-axis of the virtual cell is returned to the initial state and one dot is moved in the minus direction of the Y-axis. After moving (step 108), it is determined whether or not the pattern of the virtual cell matches the pattern of the search area. When it is determined that the movement amount in the Y-axis direction has already reached 31 dots or has reached the edge of the screen, the header data is set to “0”, and then the image to which the actual data is added is added. Data is created (step 109), the data is moved to the next cell to be compressed (step 110), and the process returns to the start.
[0031]
Next, according to FIG. 3, when the compression processing target cell is located at the upper end or the left end of the screen, it is determined whether or not the cell is at the left end of the screen (step 111). If the result of the determination is that the compression processing target cell is at the left end of the screen, the virtual cell is moved by one dot in the minus direction of the Y axis to determine whether or not the pattern of the virtual cell matches the pattern of the search area (step 113). ). If the two patterns match as a result of the determination, header data and offset data are created (step 114), the process moves to the next cell to be compressed (step 115), and the process returns to the start.
[0032]
If the pattern of the virtual cell does not match the pattern of the search area, it is determined whether the movement amount in the Y-axis direction has already reached 31 dots or has reached the edge of the screen (step 116). If it is determined that the amount has already reached 31 dots or has reached the edge of the screen, the header data is set to "0", and then image data to which actual data is added is created (step 117). Then, the process moves to the next compression target cell (step 115), and the process returns to the start. On the other hand, if the movement amount has not yet reached 31 dots and is not at the end of the screen, the process returns to step 112 to move the virtual cell by one dot in the minus direction of the Y axis, and performs the same processing again. .
[0033]
If the compression target cell is located at the upper end of the screen but is not at the left end of the screen, the virtual cell is moved by one dot in the minus direction of the X axis (step 118), and the pattern of the virtual cell and the search area are changed. It is determined whether they match (step 119). If the two patterns match as a result of the determination, header data and offset data are created (step 120), and the process moves to the next compression target cell (step 115), and the process returns to the start.
[0034]
When the pattern of the virtual cell does not match the pattern of the search area, it is determined whether the movement amount in the X-axis direction has already reached 31 dots or has reached the edge of the screen (step 121). If it is determined that the amount has already reached 31 dots or has reached the end of the screen, the header data is set to "0", and then image data to which actual data is added is created (step 122). Then, the process moves to the next compression target cell (step 115), and the process returns to the start. On the other hand, if the movement amount has not yet reached 31 dots and is not the end of the screen, the process returns to step 118, moves the virtual cell by one dot in the minus direction of the X axis, and performs the same processing again. .
[0035]
Next, the decoding process will be described with reference to the flowchart of FIG. The decoding device receiving the data compressed by the above-described compression method starts the cell 1 in FIG. 6 and decodes the data in the order of the arrows. As a specific processing procedure, it is first confirmed from FIG. 4 whether or not the header data is “0” (step 201). If the result of the check is that the header data is "0", an image is formed based on the actual data after the header data (step 202), and then it is determined whether or not this cell is the last cell. (Step 208). If the result of the determination is that this is the last cell, the decoding process is terminated; otherwise, the cell is moved (step 209), the process returns to the start, and the process is continued.
[0036]
On the other hand, if the header data is not "0", an area having the same pattern is specified from the offset data (step 203), and first, the top left pixel data of this area is specified (step 204). The specified pixel data is copied to the cell (Step 205). This operation is sequentially performed, and when the processing for the last pixel data is completed (step 206), it is confirmed whether or not the cell which has been subjected to the decoding processing is the last cell (step 208). If so, the decoding operation ends. If it is not the last cell, the cell is moved (step 209), the process returns to the start, and the process is continued. On the other hand, when the pixel data subjected to the above-described copy processing is not the last pixel data, the pixel is advanced by one dot in the scanning direction, the pixel is specified (step 207), and the same processing as described above is sequentially performed.
[0037]
It should be noted that even if the virtual cell and the compression processing target cell have a positional relationship of overlapping, there is no problem if the processing is performed according to the flowchart of FIG. In FIG. 5, the pixel “A”, which is the upper leftmost pixel of the virtual cell, does not overlap in any case. Therefore, first, the pixel “A” is placed at the corresponding position (this In this case, the data is copied to the compression processing target cell at the upper left position “A”). Hereinafter, copying is performed in the same manner in the scanning direction. However, since the pixel “A” next to “Q” and “R” in the third row of the virtual cell has already been copied and copied, it is possible to copy again using that pixel. it can. In this way, even if the virtual cell and the compression processing target cell have a positional relationship overlapping, decoding can be performed to the end.
[0038]
As described above, the embodiments of the present invention have been described in detail with reference to the drawings. However, the specific configuration is not limited to these embodiments, and includes a design and the like within a range not departing from the gist of the present invention. It is. For example, in the embodiment of the present invention, the size of the compression processing target cell and the virtual cell is set to 8 dots (pixels) × 8 dots (pixels). Any size that can increase the compression efficiency may be used.
[0039]
Similarly, the search range by the virtual cell may be appropriately determined according to the type of image and the contents of the system that processes the image data. Further, in the embodiment of the present invention, an example in which the virtual cell is moved by one dot (pixel) and an area having the same pixel data is searched has been described, but the movement amount of the virtual cell is limited to this. It does not mean that it is optional.
[0040]
【The invention's effect】
As described above, according to the present invention, a search for whether or not to have the same pixel data as that of a compression processing target cell, which has been performed only with a fixed cell in the related art, is performed using a cell boundary. Since the search is performed within the removed search range, there is a high probability that an area having the same pixel data can be searched, and there is an effect that a higher compression ratio than in the related art can be expected. Further, in the conventional method, a sufficient compression ratio can be expected even for image data for which data compression was not so expected.
[0041]
Further, in the present invention, at the stage of the encoding process, instead of the pixel data to be originally recorded, offset data at a position corresponding to the moving amount of the search area with respect to the compression processing target cell is recorded, so that sufficient A high compression ratio can be expected. In addition, at the stage of the decompression process, the offset data of the position is read out, and the pixel data of the area where the decompression process has been completed at the location moved from the compression target cell by an amount corresponding to the offset data at this position is copied. This has an effect that the original image data can be easily completely restored.
[0042]
Further, in the present invention, since the compression target cell is included in the search range for the area having the same pixel data as the compression target cell, even a somewhat complicated image such as a gradation-processed image can be used. The effect of the above compression can be expected.
[0043]
Further, in the present invention, since the above-described method of compressing image data is defined as a program, the image data processing system using the computer immediately executes the image data compression processing according to the present invention. can do.
[Brief description of the drawings]
FIG. 1 is a diagram showing a compression method and a data structure of image data according to an embodiment of the present invention.
FIG. 2 is a flowchart showing a part of a process for moving a virtual cell within a search range according to the embodiment of the present invention.
FIG. 3 is a flowchart showing a part of a process for moving a virtual cell within a search range according to the embodiment of the present invention.
FIG. 4 is a flowchart showing a decoding process of image data according to the embodiment of the present invention.
FIG. 5 is a diagram illustrating a decoding method according to the embodiment of the present invention when a compression target cell and a virtual cell overlap.
FIG. 6 is a diagram showing a method of scanning image data during compression processing and data decoding according to the embodiment of the present invention.
FIG. 7 is a diagram showing a compression method using a conventional cell reference compression method.
[Explanation of symbols]
1: Search range, 2: Target cell for compression processing, 3: Virtual cell