(57)【特許請求の範囲】
【請求項１】
各画素は赤色値、緑色値、青色値及び強度値によって表された色を有し、各列は上記画素を含み、各行に複数の上記列が含まれている複数の行からなるグラフィックス画像データを処理する方法において、
グラフィックス画像データの圧縮されたブロックからグラフィックス画像データの圧縮されていないブロックを作成する段階、並びに、
グラフィックス画像データの圧縮されていないブロックからグラフィックス画像データの圧縮されたブロックを形成する段階の中の少なくとも一方の段階を行なう段階からなり、
上記データは、赤色値、緑色値、青色値及び強度値を有する複数の別個の色組合せと、別個の色組合せ毎に上記圧縮されていないブロックの行での別個の色組合わせの有無を表すグループフラグの組と、別個の色組合せを有する上記圧縮されていないブロックの行毎に上記圧縮されていないブロックの列での別個の色組合せの有無を表す少なくとも１組の行フラグの組とにより構成されていることを特徴とする方法。
【請求項２】
上記グラフィックス画像データの圧縮されたブロックを形成する段階は、
（Ａ）上記ブロックの画素に在る全ての色を識別することにより、上記ブロック内の各画素毎に１画素の色に対応し、一つの色を表す１個の色序数を含む色序数の配列を作成する段階と、
（Ｂ）選択された一つの色に対する上記赤色値、緑色値、青色値及び強度値を上記圧縮されたブロックに格納する段階と、
（Ｃ）上記色序数の配列に従って選択された色の画素を有するブロック内の行を示す第１のフラグの組を作成する段階と、
（Ｄ）上記第１のフラグの組を上記圧縮されたブロックに格納する段階と、
（Ｅ）上記選択された色の画素を有する各行を１組で表現する第２のフラグの組であって、上記色序数の配列に従って選択された色の画素を有するブロックの行内で選択された色の画素を有する列を示す少なくとも１組の第２のフラグの組を作成する段階と、
（Ｆ）上記少なくとも１組の第２のフラグの組を上記圧縮されたブロックに格納する段階と、
（Ｇ）ブロックの全ての色に対し上記段階（Ｂ）乃至（Ｆ）を繰り返す段階とからなる請求項１記載の方法。
【請求項３】
上記圧縮されたブロックのサイズを上記圧縮されたブロックに格納する段階を更に有する請求項２記載の方法。
【請求項４】
上記ブロックは、１行毎に８列を含む８行により構成されている請求項２記載の方法。
【請求項５】
マスク値を取得する段階を更に有し、
上記色序数の配列を作成する段階において、上記マスク値に従って上記ブロックの画素に存在する全ての色が識別される請求項２記載の方法。
【請求項６】
上記マスク値を上記圧縮されたブロックに格納する段階をっさらに有する請求項５記載の方法。
【請求項７】
第１の赤色値、第１の緑色値、第１の青色値及び第１の強度値を有する第１の色と、第２の赤色値、第２の緑色値、第２の青色値及び第２の強度値を有する第２の色は、上記第１の赤色値の上記マスク値による除算の商が上記第２の赤色値の上記マスク値による除算の商と一致しない場合、上記第１の緑色値の上記マスク値による除算の商が上記第２の緑色値の上記マスク値による除算の商と一致しない場合、上記第１の青色値の上記マスク値による除算の商が上記第２の青色値の上記マスク値による除算の商と一致しない場合、並びに、上記第１の強度値の上記マスク値による除算の商が上記第２の強度値の上記マスク値による除算の商と一致しない場合に別個の色である請求項６記載の方法。
【請求項８】
上記ブロックの画素に最も頻繁に出現する色の赤色値、緑色値、青色値及び強度値を上記圧縮されたブロックの端に移す段階を更に有する請求項２記載の方法。
【請求項９】
コンピュータシステムにおいて、請求項１記載の方法を実施する装置。
【請求項１０】
上記グラフィックス画像データの圧縮されていないブロックを作成する段階は、
（ａ）上記圧縮されたブロックから選択された色に関する上記赤色値、緑色値、青色値及び強度値を得る段階と、
（ｂ）上記圧縮されたブロックから選択された色に関する上記グループフラグの組を得る段階と、
（ｃ）上記圧縮されたブロックの少なくとも１行での選択された色の有無を示す上記グループフラグの組の中で選択されたグループフラグに対応する行フラグの組を得る段階と、
（ｄ）上記圧縮されていないブロックの上記選択されたグループフラグにより示されるような選択された色を有する行に関する行フラグの組によって示されるような選択された色を有する列によって指定された選択された場所に、上記赤色値、緑色値、青色値及び強度値を書き込む段階と、
（ｅ）上記圧縮されたブロックの少なくとも１行での選択された色の有無を示す上記グループフラグの組の各グループフラグに対し上記段階（ｃ）及び（ｄ）を繰り返す段階と、
（ｆ）上記圧縮されたブロックの全ての別個の色組合せに対し上記段階（ａ）乃至（ｅ）を繰り返す段階とからなる。
【請求項１１】
上記圧縮されたブロックから最後の色に関する上記赤色値、緑色値、青色値及び強度値を得る段階と、
上記圧縮されていないブロックの全ての画素に対し、上記最後の色に関する上記赤色値、緑色値、青色値及び強度値を上記圧縮されていないブロックに書き込む段階とを更に有する請求項１０記載の方法。
【請求項１２】
上記圧縮されたブロックはマスク値を含み、
上記マスク値を上記圧縮されたブロックから得る段階と、
上記マスク値に従って上記赤色値、緑色値、青色値及び強度値を変更する段階とを更に有する請求項１０記載の方法。
【請求項１３】
第１の赤色値、第１の緑色値、第１の青色値及び第１の強度値を有する第１の色と、第２の赤色値、第２の緑色値、第２の青色値及び第２の強度値を有する第２の色は、上記第１の赤色値の上記マスク値による除算の商が上記第２の赤色値の上記マスク値による除算の商と一致しない場合、上記第１の緑色値の上記マスク値による除算の商が上記第２の緑色値の上記マスク値による除算の商と一致しない場合、上記第１の青色値の上記マスク値による除算の商が上記第２の青色値の上記マスク値による除算の商と一致しない場合、並びに、上記第１の強度値の上記マスク値による除算の商が上記第２の強度値の上記マスク値による除算の商と一致しない場合に別個の色である請求項１２記載の方法。
【請求項１４】
各画素は赤色値、緑色値、青色値及び強度値によって表された色を有し、各列は上記画素を含み、各行に複数の上記列が含まれている複数の行からなるグラフィックス画像データの圧縮されていないブロックに基づいて、グラフィックス画像データの圧縮されたブロックを表現するデータを格納するメモリにおいて、
赤色値、緑色値、青色値及び強度値を有する複数の別個の色組合せと、別個の色組合せ毎に上記圧縮されていないブロックの行での別個の色組合わせの有無を表すグループフラグの組と、別個の色組合せを有する上記圧縮されていないブロックの行毎に上記圧縮されていないブロックの列での別個の色組合せの有無を表す少なくとも１組の行フラグの組とにより構成されているデータ構造が格納されていることを特徴とするメモリ。
【請求項１５】
上記データ構造は上記圧縮されたブロックに関するマスク値を更に有し、
第１の赤色値、第１の緑色値、第１の青色値及び第１の強度値を有する第１の色と、第２の赤色値、第２の緑色値、第２の青色値及び第２の強度値を有する第２の色は、上記第１の赤色値の上記マスク値による除算の商が上記第２の赤色値の上記マスク値による除算の商と一致しない場合、上記第１の緑色値の上記マスク値による除算の商が上記第２の緑色値の上記マスク値による除算の商と一致しない場合、上記第１の青色値の上記マスク値による除算の商が上記第２の青色値の上記マスク値による除算の商と一致しない場合、並びに、上記第１の強度値の上記マスク値による除算の商が上記第２の強度値の上記マスク値による除算の商と一致しない場合に別個の色である請求項１４記載のメモリ。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明はデータ圧縮及び逆圧縮に係わり、特に、類似カラーの組に従ってカラーグラフィックス画像を符号化する方法に関する。
【０００２】
【従来の技術】
カラーグラフィックス画像は、コンピュータシステム、特に、マルチメディアパーソナルコンピュータによる表示のため幅広く使用されている。提供される解像度及び画像に表現され得るカラー数が高まると共に、カラーグラフィックス画像を表現するデータのサイズは拡大する。また、使用されるコンピュータモニタが大きくなると共に、ユーザはより大きい画像の表示を要求する。カラーグラフィックス画像を格納するため必要とされるメモリ空間の削減及びかかる画像を伝送及び表示するため必要とされる時間の短縮は、従来からコンピュータグラフィックス技術の重要な目標である。
【０００３】
図１は、従来技術によるカラーグラフィックス画像及びその関連した記憶表現を示す図である。ビットマップイメージ１０は、１行あたりｍ画素のｎ行を有する。典型的に、ｎ及びｍは８で割り切れる数である。ビットマップイメージ１０は、論理的に８画素×８画素の矩形に分割され得る。従って、ビットマップイメージの左右方向にｍ／８個のブロックがあり、ビットマップイメージの上下歩行にｎ／８個のブロックがある。換言すると、（ｍ／８）＊（ｍ／８）個の８×８形のブロックがビットマップイメージに含まれる。ある８×８形のブロックは、（ｉ，ｊ）のペアで参照することができ、ここで、ｉは０乃至（ｍ／８−１）の範囲内に収まり、ｊは０乃至（ｎ／８−１）の範囲に収まる。
【０００４】
８×８形の各ブロック１２は６４画素を含む。各画素はＲＧＢＡの四つ組１４として表現される。ＲＧＢＡ四つ組１４は、赤色値（Ｒ）１６と、緑色値（Ｇ）１８と、青色値（Ｂ）２０と、輝度値（Ａ）２２とを含む。画素の色及び輝度は、Ｒ、Ｇ、Ｂ及びＡの値によって決まる。殆どのカラー画像の場合、８×８形のブロックは、５乃至１２色の異なる色を含む。Ｒ、Ｇ、Ｂ及びＡの各値は、８ビットのバイトに記憶される。従って、各画素は４バイトの記憶容量を占有し、８×８形のブロックは２５６バイトの記憶容量を占有する。これにより、ビットマップイメージ１０は、２５６＊（ｍ／８＊ｎ／８）バイトの記憶容量を必要とする。例えば、ビットマップが１行あたり６４０画素の４８０行からなるとき、圧縮されていないビットマップイメージデータのサイズは、２５６＊（６４０／８＊４８０／８）バイト、即ち、1,228,800 バイトである。ビットマップが１行あたり１２８０画素の１０２４行からなるとき、圧縮されていないビットマップイメージデータのサイズは、２５６＊（１２８０／８＊１０２４／８）バイト、即ち、5,242,880 バイトである。従って、圧縮されていないビットマップイメージは大量の記憶容量を必要とする。
【０００５】
従来の画像圧縮の一つの方法は、国際標準化機構（ＩＳＯ）により認可されたグループであるジョイントフォトグラフィックエクスパートグループ（ＪＰＥＧ）によって提案されている。ＪＰＥＧ圧縮標準は、僅かに識別できる画像の劣化を伴ってビットマップ化された画像のサイズを縮小する損失のある画像圧縮アルゴリズムである。損失のある圧縮方法は、ある程度の絵的な情報を無視することにより画像のサイズを縮小する。対照的に、損失のない圧縮方法は、画像が通常要求するビット数をデータを失うことなく削減する。ＪＰＥＧ圧縮アルゴリズムは、カラー画像を、上記の如く輝度及び色を表す数値を有する画素の行に変換する。画像は、１６画素×１６画素である各ブロックに分割され、各ブロック毎に一つおきの画素を取り除くことにより８画素×８画素のブロックに削減される。この圧縮アルゴリズムは、少ないデータで表現することができるように各ブロック毎に平均カラー値を計算する公式を使用する。画像データを復元するため、この処理は画素の圧縮を解除すべく反転される。
【０００６】
ＪＰＥＧ標準は広く使用されているにも係わらす欠点がある。ＪＰＥＧアルゴリズムは、画像内の関連した画素に対する局部平均カラー値を計算するため、フーリエ変換、ハフマン符号化、“ジグザグ化(zigzagging)”及びＹＵＶ変換の計算を使用する。このアルゴリズムは、画像内の画素の行に使用される各カラーを曲線として表現する。局部平均カラー値は、曲線を表現する多項式の項に対し、コサイン関数を計算し、浮動小数点係数を乗算することにより計算される。
【０００７】
【発明が解決しようとする課題】
上記の従来技術によるアルゴリズムの計算は、非常に時間がかかり、全体的な画像圧伸の速度に悪影響を与える。コサイン関数の浮動小数点演算及び乗算演算を行うことなくカラーグラフィックス画像を圧伸する高速な方法が必要とされる。また、良好な圧縮率を与え、逆圧縮の間に高程度の並列化をなし得る方法は、コンピュータグラフィックス技術に重要な価値を付加する。
【０００８】
【課題を解決するための手段】
本発明はグラフィックス画像データを圧縮及び逆圧縮する方法を提供する。
複数の行を有し、各行には複数の列があり、各列は画素を含み、各画素は赤色値、緑色値、青色値及び強度値によって表された色を有する複数の行からなるグラフィックス画像データのブロックを圧縮されたブロックに圧縮する方法は、
上記ブロックの画素に在る全ての色を識別することにより、各色序数が一つの色を表し、上記ブロック内の各画素毎に１画素の色に対応した１個の色序数を含む色序数の配列を作成する段階と、
選択された一つの色に対する赤色値、緑色値、青色値及び強度値を上記圧縮されたブロックに格納する段階と、
上記色序数の配列に従って選択された色の画素を有するブロック内の行を示すグループフラグの組を作成する段階と、
上記グループフラグの組を圧縮されたブロックに格納する段階と、
上記色序数の配列に従って選択された色の画素を有するブロックにおいて１組の行フラグによって表された選択された色の画素を有する行内で、選択された色の画素を有する列を示す少なくとも１組の行フラグを作成する段階と、
上記行フラグの組を圧縮されたブロックに格納する段階と、
ブロックの全ての色に対し上記の段階を繰り返す段階とからなる。
【０００９】
圧縮されたグラフィックス画像データのブロックを圧縮されていないブロックに逆圧縮する方法は、
圧縮されたブロックから選択された色に対し、赤色値、緑色値、青色値及び強度値を得る段階と、
上記圧縮されたブロックから選択された色に対し、グループフラグの組を得る段階と、
上記圧縮されたブロックの少なくとも１行で選択された色の有無を示す上記グループフラグの組の中の一つの組に対応する行フラグの組を得る段階と、
赤色値、緑色値、青色値及び強度値を、上記行フラグの組により示されるような選択された色を有する列及び上記グループフラグの組により示されるような選択された色を有する行によって指定された選択された場所で圧縮されていないブロックに書き込む段階と、
上記圧縮されたブロックの少なくとも１行で選択された色の有無を示す上記グループフラグの組の各フラグに対し上記段階を繰り返す段階と、
上記圧縮されたブロックの全ての別個の色組合せに対し上記段階を繰り返す段階とからなる。
【００１０】
本発明により得られる利点及び新規性のある特徴は、以下の説明に記載され、以下の実施例に基づいて当業者には明らかであり、かつ、本発明を実施することにより知ることができる。
本発明の別の実施例によれば、上記の利点及び他の利点は、複数の行を有し、各行には複数の列があり、各列は画素を含み、各画素は赤色値、緑色値、青色値及び強度値によって表された色を有する複数の行からなるグラフィック画像データを圧縮されたブロックに圧縮する装置により達成される。この装置は、上記ブロックの画素に在る全ての色を識別することにより、各色序数が一つの色を表し、上記ブロック内の各画素毎に１画素の色に対応した１個の色序数を含む色序数の配列を作成する手段と、上記色序数の配列に従って選択された色の画素を有するブロックの行を示す第１のフラグの組を作成する手段と、上記色序数の配列に従って上記選択された色の画素を有するブロックの行の範囲内で選択された色の画素を有する列を示す第２のフラグの組であって、選択された色の画素を有する各行は１組の第２のフラグの組により表される第２のフラグの組を作成する手段と、選択された一つの色に対し、赤色値、緑色値、青色値及び強度値と、上記第１のフラグの組と、上記少なくとも１組の第２のフラグの組を上記圧縮されたブロックに格納する手段とからなる。
【００１１】
本発明の別の実施例において、上記利点及び他の利点は、グラフィックス画像データの圧縮されたブロックを圧縮されていないブロックに逆圧縮する装置によって実現される。上記装置は、複数の別個の赤、緑、青及び強度値の色組合せを有する圧縮されたブロックであって、別個の各色組合せは、圧縮されていないブロックの行で別個の色組合せの有無を示すグループフラグの組と、別個の色組合せを有する圧縮されていないブロックの各行に対し圧縮されていないブロックの列で別個の色組合せの有無を示す少なくとも１組の行フラグの組とを有するグラフィックス画像データの圧縮されたブロックを圧縮されていないブロックに逆圧縮する。上記装置は、圧縮されたブロックから選択された色に対し赤色値、緑色値、青色値及び強度値を読み出し、上記圧縮されたブロックから選択された色に対し上記グループフラグの組を読み出し、上記圧縮されたブロックの少なくとも１行で選択された色の有無を示す上記グループフラグの組の中のグループフラグに対応する行フラグの組を読み出す手段と、赤色値、緑色値、青色値及び強度値を、上記行フラグの組により示されるような選択された色を有する列及び上記グループフラグの組により示されるような選択された色を有する行によって指定された選択された場所で圧縮されていないブロックに書き込む手段とを有する。
【００１２】
【発明の実施の形態】
本発明の他の目的及び利点は、以下の本発明の実施例の詳細な説明を読むことにより当業者にとって明らかであろう。以下の説明では、本発明を実施するため熟慮されたベストモードの実例によって本発明の好ましい実施例だけを示す。本発明は、他の実施例及び異なる実施例として実現することが可能であり、本発明の実施例の細部は、本発明から逸脱することなく、種々の明瞭な点で変更することが可能である。従って、添付図面及び以下の説明は、本質的に実例であり、本発明を制限するものではないことに注意する必要がある。
【００１３】
本発明は、図１に示されるような圧縮されていないビットマップ画像データに関して動作し、画像の圧縮表現を生成する。本発明は、また、圧縮されたビットマップ画像データに関して動作し、元の圧縮されていない表現を生成する。一般的に言うと、画像を圧縮するため、本発明は、画像の８画素×８画素からなる全ブロックを順番に別々に処理する。各ブロック毎に、ブロックに在る全ての別個の色が識別され、序数が割り当てられる。ブロックのデータ構造は、ブロック内にある別個の色の個数と、（以下に説明する）圧縮画像品質マスク値と、ブロックに在る各色に対する実際のＲＧＢＡ四つ組と、ブロック内の特定の画素での特定の色の有無を示すグループフラグの組及び行２値フラグの組とを格納するため生成される。得られたデータ構造は、ブロックに対する元のＲＧＢＡ四つ組の集合よりも遙かに少ない記憶容量しか必要としない。ブロックのデータ構造は、メモリ又はコンピュータファイルに格納され、画像の次のブロックが処理される。この処理はビットマップイメージの全てのブロックに対し繰り返される。画像を逆圧縮するため、各ブロック内の全画素のＲＧＢＡ四つ組は、ブロックのデータ構造から再生される。この再生は画像の全てのブロックに対し繰り返される。
【００１４】
本発明による圧縮された画像データの再生は、簡単な例を参照することによって巧く理解できる。図２は、本発明により序数として表されたＲＧＢＡ四つ組を備えた８×８形ブロックの例を示す図である。ブロック２４はビットマップイメージからの１個の８×８形ブロックを表す。このブロックは、色序数テーブルとも称される。図２に示されたブロックは、水平方向に０乃至７の指数を有し、垂直方向に０乃至７の指数を有する。或いは、ブロックは６４要素の１次元配列として表現してもよい。ブロックの画素は、ブロックに現れた別個の色を判定するため走査される。見つけられた各別個の色は序数が割り当てられる。
【００１５】
図３は序数のＲＧＢＡ四つ組へのマッピングを示す図である。例えば、同図の最上行の序数１は、赤色値Ｒ１と、緑色値Ｇ１と、青色値Ｂ１と、輝度値Ａ１とにより構成された色を示す。同様に、序数２は、赤色値Ｒ３と、緑色値Ｇ３と、青色値Ｂ３と、輝度値Ａ３とにより構成された色を示す。ＲＧＢＡの各組合せは、現在のブロックの少なくとも１個の画素に対する固有の色及び輝度の指定である。図２のブロックの例に現れる他の色は図３に示されている。
【００１６】
図２を再度参照するに、色序数テーブルは、第１の色が０行１列（第０行第１列）と、５行０列と、５行２乃至７列と、６行２乃至６列で検出されたことを示す。第２の色は、３行０及び６列、４行０乃至４列、５行１列、６行０乃至１列で検出される。第３の色は、０行０列、０行２乃至３列、１行１、３、５列、２行０乃至７列、６行６乃至７列で検出される。残りの色も同様に識別される。図２に示された例では、１６個の異なる色がブロック２４に現れている。ブロック内の各色の出現は、圧縮されたブロックのビットによりブロックの行における特定の色の有無を示す２値フラグの組として表すことが可能である。別のフラグの組は、指定された色を有する選択された行に対応する全ての列を示す指定された色を有する行毎に発生される。
【００１７】
図２に示されたブロック２４の表現が与えられた場合、ブロックで検出された各色に対するフラグの組が作成され、ブロックのデータ構造に格納される。例えば、第１の色は第０、５及び６行で検出される。ブロックの上記行に対する２値フラグの組は値｛10000110｝を有する第１の色に対し生成される。上記のフラグはグループフラグと称される。グループフラグの組の各位置は、第０行から始まり第７行まで続くブロックの行を表す。組の位置が１であるとき、選択された色が行のどこかに存在することを示し、組の位置が０であるとき、選択された色がその行に無いことを示す。選択された色を有する各行に対し、現在の行の各列に選択された色が存在するかどうかを示す２値フラグの組が生成される。
【００１８】
これらのフラグは行フラグと称される。例えば、第１の色は第１行の第１列だけで検出される。従って、値｛01000000｝を有する２値フラグの組は、第１の色が列１で検出され、その行の他の列で検出されないことを示すため生成される。同様に、値｛10111111｝を有する２値フラグの組は、行５の列０、２−７に第１の色が在ることを表すため生成される。値｛00111100｝を有する２値フラグの組は、行６の列２乃至５に第１の色が存在することを示すため生成される。この組を生成する処理は、ブロックで見つけられた全ての色に対し行われる。全ての色が処理されたとき、従来の方法よりも必要な記憶容量が著しく減少し、コサイン関数評価又は浮動小数点係数乗算演算を必要としないブロックのデータ構造が完全に作成される。
【００１９】
図４は、図２のブロックの例に対するデータ構造をテキスト的に表現した図である。データ構造の各フィールドは、メモリの１バイトに格納される。Ｎフィールド３０は、ブロックで検出された別個の色の数を示す。Ｎ＝６である本例の場合、色の数は６個である。マスク値フィールド３２は類似した色の組を比較する場合に使用される。マスク値フィールドについて後で詳しく説明する。Ｒ１、Ｇ１、Ｂ１及びＡ１バイト３４は、第１の色に対するＲ値、Ｇ値、Ｂ値及びＡ値を保持する。損失のない圧縮の場合、Ｒ値、Ｇ値、Ｂ値及びＡ値は、元のブロックと同様に４バイトに格納される。損失のある圧縮の場合、各成分は４ビットで格納される。その場合、Ｒ値、Ｇ値、Ｂ値及びＡ値は２バイトに格納される。グループ１フィールド３６は、ブロックの行に第１の色が在るか否かを示すビットを含む。上記の如く、第１の色は行０、５及び６で検出される。従って、グループ１フィールド３６のグループフラグの組は、値｛10000110｝を有する第１の色に対し作成される。最下位ビットはブロックの一番下の行を表す。第１の色は３本の行で見つけられるので、３個の別の２値フラグの組が第１の色が見つけられた上記３本の行のコラムを表わすため必要とされる。従って、データ構造は、行１０のフィールド３８と、行１５のフィールド４０と、行１６のフィールド４２の３組の行フラグの組を含む。フィールド名の数字は、グループ番号及び行番号を示す。例えば、行１０はグループ番号１と行番号０を表し、行１５はグループ番号１と行番号５を表し、行１６はグループ番号１と行番号６を表す。上記の如く、値｛01000000｝は、第１の色が第１列で検出され、それ以外の列では検出されないことを表すため生成される。この値は行１０のフィールド３８に格納される。同様に、値｛10111111｝は、第１の色が第５行の第０、２乃至７行に存在することを表すため生成され、行１５のフィールド４０に格納される。値｛00111100｝は、第１の色が第６行の第２乃至５列に在ることを示すため生成され、行１６のフィールド４２に格納される。
【００２０】
本例において、第４の色は、Ｒ２、Ｇ２、Ｂ２、Ａ２の組合せフィールド４４にマップされる。第４の色は、第０、１、３及び４行で検出されるので、グループ２のフィールド４６には値｛11011000｝が与えられる。この色は４本の行で検出されるので、４組のラインフラグの組は、行２０、行２１、行２３及び行２４である。これらのフィールドには、夫々、値｛00001111｝、｛10101011｝、｛00000100｝及び｛00000111｝が与えられる。第２の色は、Ｒ３、Ｇ３、Ｂ３、Ａ３の組合せフィールド４８にマップされる。第２の色は、第３乃至６行で検出されるので、グループ３のフィールド５０には値｛00011110｝が与えられる。この色は４本の行で検出されるので、４組のラインフラグの組は、行３３、行３４、行３５及び行３６である。これらのフィールドには、夫々、値｛10000010｝、｛11111000｝、｛01000000｝及び｛11000000｝が与えられる。第５の色は、Ｒ４、Ｇ４、Ｂ４、Ａ４の組合せフィールド５２にマップされる。第５の色は、第３行で検出されるので、グループ４のフィールド５４には値｛00010000｝が与えられる。この色は１本の行だけで検出されるので、１組のラインフラグの組は、行４３である。このフィールドには、第５の色が第３行の第１乃至４列で検出されたことを反映させるため、値｛01111001｝が与えられる。第６の色は、Ｒ５、Ｇ５、Ｂ５、Ａ５の組合せフィールド５６にマップされる。第６の色は、第７行で検出されるので、グループ５のフィールド５８には値｛00000001｝が与えられる。第６の色は１本の行だけで検出されるので、１組のラインフラグの組は、行５７である。このフィールドには、第６の色が第７行の第０乃至６列で検出されたことを反映させるため、値｛11111110｝が与えられる。
【００２１】
第３の色は、Ｒ６、Ｇ６、Ｂ６、Ａ６の組合せフィールド６０にマップされる。しかし、第３の色にはグループフラグの組又は行フラグの組が付随しない。ブロック中の第３の色の位置を記述する情報は逆圧縮処理中に再生され得る。これらの位置は、全ての他の色が処理された後に残されたブロックの画素である。従って、第３の色を有するがその指定は不必要である。
【００２２】
図５は、図４に示されたデータ構造がコンピュータメモリに記憶された場合の一例である。本例では損失のある圧縮を使用し、Ｒ、Ｇ、Ｂ及びＡの値は、全部でバイトに格納される。この例の場合、ブロックを表す圧縮されたデータを格納するため必要とされるバイトの総数は３２である。圧縮されていないブロックは２５６バイトを必要とするので、本発明の動作によってサンプルブロックに対し８：１の圧縮率が得られる。
【００２３】
図６は、本発明による圧縮されたブロックを格納する一般化されたデータ構造を示す図である。圧縮されたブロックの（バイト単位）サイズ６２は、マスク値４と共に格納される。ブロックの各色に対し、Ｒ、Ｇ、Ｂ及びＡの値６６が格納され、グループフラグの組６８が生成される。現在の色を有する各行毎に、行内の現在の色の位置を記憶するため行フラグの組７０が生成される。このデータ構造は、ビットマップイメージの全ブロックに対し繰り返される。
【００２４】
圧縮中に画像データのブロックに対するデータ構造を構築する本発明の方法は、二つの例外処理がある。ブロックが一つの色しか含まない場合、１個のＲＧＢＡの色グループしかなく、データ構造のフォーマットは、
｛Ｎ＝４，マスク値，ＲＧ，ＢＡ｝
である。従って、ブロックは損失のある圧縮の場合、４バイトだけで表され、損失のない圧縮の場合、６バイトで表される。６４通りのＲＧＢＡ色グループが存在する場合、即ち、各画素が異なる色である場合、フォーマットは、
｛Ｎ＝１３０，マスク値，Ｒ１Ｇ１，Ｂ１Ａ１，Ｒ２Ｇ２，Ｂ２Ａ２，Ｒ３Ｇ３，Ｂ３Ａ３，．．．Ｒ６４Ｇ６４，Ｂ６４Ａ６４｝
である。しかし、実際上、８×８形のブロックの各画素の色が異なる可能性は殆ど無い。
【００２５】
図４を参照するに、マスク値のフィールド３２は、ブロックの２個の画素を比較する際に使用されるマスクビットの数を保持する。マスク値は、圧縮されていないブロックの圧縮中に使用され、圧縮されたブロックの逆圧縮中に使用するため逆圧縮機能に伝えられる。本発明の好ましい実施例において、マスク値のデフォルト値は１６Ｄ、又は、０００１００００Ｂである。これは、色を比較する際にＲ、Ｇ、Ｂ及びＡの各値の最下位４ビットがマスクされることを意味する。即ち、Ｒ、Ｇ、Ｂ及びＡの各値の最上位４ビットだけが各画素毎に比較される。これにより、類似しているが一致しない２個の色が得られ、これらの２個の色は圧縮目的のためには同じ色であるとみなされる。マスク値は、圧縮アルゴリズムのユーザによる設定が行える変数である。形式的に言うと、２個のＲＧＢＡ四つ組であるＲｐＧｐＢｐＡｐ及びＲｑＧｑＢｑＡｑは、
Ｒｐ  ｄｉｖ  マスク値＝Ｒｑ  ｄｉｖ  マスク値  （Ｒｐのマスク値による除算の商＝Ｒｑのマスク値による除算の商）
Ｇｐ  ｄｉｖ  マスク値＝Ｇｑ  ｄｉｖ  マスク値
Ｂｐ  ｄｉｖ  マスク値＝Ｇｑ  ｄｉｖ  マスク値  及び
Ａｐ  ｄｉｖ  マスク値＝Ａｑ  ｄｉｖ  マスク値
である場合に、色に関して一致しているとみなされる。マスク値が零に設定されたとき、マスキングは行われない。これは損失のない圧縮であり、元の情報を全て含むので、逆圧縮された画像は最良の品質を有する。しかし、この場合、得られる圧縮率は低い。マスク値が１０進の１６に設定された場合、逆圧縮された画像の品質はマスク値が零の時ほど良好ではないが、圧縮率は改善される。本発明のデフォルト値で、殆どのユーザは、圧縮及び逆圧縮動作が行われた後、画質の劣化を検出できない。ユーザは、圧縮率対画質に関するユーザの好みに基づいてマスク値を選択することができる。マスク値が小さいほど、圧縮目的のため同じ色であるとみなされる別個の色は少なくなり、圧縮率が低下し、マスク値が大きくなると共に、圧縮目的のため同じ色であるとみなされる別個の色が増加し、圧縮率は上昇する。
【００２６】
図７及び８は、本発明による画像データの圧縮方法の上位レベルのフローチャートである。圧縮スタートステップ１００の後、この圧縮動作のマスク値がステップ１０２で得られる。マスク値は、所望の圧縮率と結果として得られる逆圧縮された画像の品質とに基づいて本圧縮方法のユーザによって設定され得る。或いは、マスク値は１６Ｄのようなデフォルト値にプリセットしてもよい。マスク値は圧縮されるべき画像の全てのブロックに対し同一でもよく、又は、新しいマスク値が各ブロックに対し指定されてもよい。画像データの圧縮されていない８画素×８画素形ブロックは、圧縮処理のためステップ１０４で取得される。典型的に、画像データはコンピュータシステムのファイルに格納され、ファイルが開かれ、画像データの最初のブロックがファイルから読み出される。
【００２７】
ステップ１０６において、圧縮されていないブロックの６４画素は、マスク値に従って、（図２に示されたテーブルの例と類似した）全ての別個の色の色序数テーブルを作成するため走査される。ブロックに存在する色は識別され、各画素は画素に在る色の序数が割り当てられる。２個の画素は画素のＲＧＢＡ値の差がマスク値よりも小さい場合、同じ色であるとみなされる。ブロックの色序数テーブルが作成された後、色序数テーブルからの第１の色がステップ１０８で選択される。この色は、ブロックに関する圧縮された画像データを保持するデータ構造を作成する際に、最初に処理されるべき色である。次に、ステップ１１０において、処理されている現在の色に関するＲＧＢＡ値が画像データの圧縮されていないブロックから抽出され、指定されてたマスク値に従って圧縮されたブロックデータ構造に格納される。圧縮されたブロックデータ構造は図６に示されている。色序数テーブルは、現在の色を有する圧縮されていないブロック中の行を示すグループフラグの組を作成するため、ステップ１１２で走査される。ブロック中に８本の行が在るので、８個の２値フラグの組はブロックの行における現在の色の有無を示すために足りる。グループフラグの組は８ビットのバイトで格納してもよい。グループフラグの組は圧縮されたブロックに格納される。ステップ１１４において、色序数テーブルは、現在のグループフラグの組でフラグを立てられた各行に対し現在の色を有する列を示す１組以上の行フラグの組を作成するため処理される。即ち、関連したビットがグループフラグの組にセットされたブロックの各行に対し、ラインフラグの組が生成される。ブロックには８本の列があるので、８個の２進フラグの組は、選択された行の列における現在の色の有無を充分に示すことができる。行フラグの組は８ビットのバイトで格納される。グループフラグの組にセットされたビットに対応する全ての行フラグの組は、圧縮されたブロックに格納される。圧縮処理は結合子８Ａを経由して図８へ続く。
【００２８】
図８のテストステップ１１６において、処理すべき色が色序数テーブルに残されている場合、ＹＥＳ側パス１１８が選ばれ、結合子７Ｂを経由して図７のステップ１０８に進む。ステップ１０８では、処理されるべき次の色が色序数テーブルの色から選択され、その色が上記の通り処理される。ステップ１１６において、処理されるべき色が色序数テーブルに残されていない場合、ＮＯ側パス１２０が選ばれ、ステップ１２２に進む。
【００２９】
本発明の最適化の特徴として、画像データの元のブロックに最も頻繁に出現する色は、圧縮されたブロックの最後の色として表現され、グループフラグの組と行フラグの組は省略される。逆圧縮処理中に、この色は、他のグループフラグの組及び行フラグの組によって参照されない全ての画素に配置されているとみなされる。従って、最大の色グループのＲＧＢＡ値は、ステップ１２２において、圧縮されたブロックの端に移され、圧縮されたブロックの他のバイトはブロックを詰め、必要に応じて、最大色グループによって残された記憶場所の隙間を埋めるべく移される。ステップ１２４において、ブロックの処理中に使用された圧縮されたブロックのサイズ及びマスク値が圧縮されたブロックに格納される。圧縮されたブロックは、次に、ステップ１２６で出力される。典型的に、この出力動作は、圧縮された画像データを格納するため圧縮されたブロックのファイルへの書き込みを必然的に伴う。ステップ１２８において、処理されるべき画像データのブロックが未だ有るならば、ＹＥＳ側パス１３０が選ばれ、結合子７Ａを経由して図７のステップ１０４に進む。ステップ１０４において、画像データの次の圧縮されていないブロックが圧縮処理のため取得される。さもなければ、ＮＯ側パス１３２が選ばれ、エンドステップ１３４に進み、この画像データに対する圧縮処理が終了する。
【００３０】
以下の表１のリストには、本発明により画像データのブロックを圧縮する疑似コードが記載されている。本発明の圧縮アルゴリズムのＣ言語による実装は添付リストＡとして添付されている。
0004189443.tif 000002
0004189443.tif 000003
0004189443.tif 000004
図９及び１０は、本発明による先に圧縮された画像データを逆圧縮する方法の上位レベルのフローチャートである。逆圧縮ステップは、圧縮された画像の表示が求められる際に行われる。逆圧縮スタートステップ１５０の後に、画像データの圧縮されたブロックは、ステップ１５２で逆圧縮処理のため取得される。典型的に、圧縮されたブロックはコンピュータシステム上のファイルに格納され、ファイルが開かれ、画像データの最初に圧縮されたブロックがファイルから読み出される。圧縮されたブロックのサイズ及びマスク値は、ステップ１５４で圧縮されたブロックの最初の二つの記憶場所から取り出される。ステップ１５６で、圧縮されたブロックの最後のＲＧＢＡ値が取り出され、逆圧縮処理によって出力されるべき圧縮されていないブロックの全ての場所に書き込まれる。圧縮されていないブロックの選択された場所への後続の書き込みはデフォルト色を上書きするが、この色はブロックで最も頻繁に使用される色であるため、記憶容量及び逆圧縮処理時間はこのステップによって節約される。ステップ１５８において、圧縮されたブロックの第１の色が選択される。この色に対するＲＧＢＡ値は、ステップ１６０においてマスク値を用いて圧縮されたブロックから取り出される。次に、ステップ１６２において、この色に対するグループフラグの組は圧縮されたブロックから取り出される。この色がブロックの対応する行で検出されることを示すグループフラグの組のあるビットがセットされているならば、この色に関する行フラグの組は、ステップ１６４で圧縮されたブロックから取り出される。この色の処理は結合子１０Ａを経由して図１０のステップ１６６に進む。
【００３１】
ステップ１６６において、ＲＧＢＡ値はビットがセットされた行フラグの組の全ての列に関するグループフラグと行フラグの組合せによって示される選択された場所で圧縮されていないブロックに書き込まれる。行フラグの各組は、ブロックの現在の行の列に現在の色が存在することを示す。列ビットが特定の行に関してセットされているならば、ＲＧＢＡ値は圧縮されていないブロックの選択された画素に対する場所に書き込まれる。次に、ステップ１６８において、他の行フラグの組が現在の色グループに対し存在するならば、ＹＥＳ側のパス１７０が選ばれ、この色に関する次の行フラグの組を得るため結合子９Ｃを経由して図９のステップ１６４に進む。さもなければ、ＮＯ側のパス１７２が選ばれ、テストステップ１７４に進む。ステップ１７４において、現在のブロックに対し、未だ処理されるべき色が残されているならば、ＹＥＳ側のパス１７６が選ばれ、次の色を選択するため結合子９Ｂを介して図９のステップ１５８に戻る。さもなければ、ＮＯ側のパス１７８が選ばれ、テストステップ１８０に進む。テストステップ１８０において、この圧縮された画像に関して処理すべきブロックが未だ有るならば、ＹＥＳ側のパス１８２が選ばれ、処理すべき次の圧縮されたブロックを得るため結合子９Ａを経由して図９のステップ１５２に戻る。画像の全ブロックが処理された場合、ＮＯ側のパス１８４が選ばれ、エンドステップ１８６に進み、逆圧縮処理が終了する。
【００３２】
以下の表２のリストには、本発明による画像データの先に圧縮されたブロックを逆圧縮する方法の疑似コードが記載されている。本発明の逆圧縮アルゴリズムのＣ言語による実装は添付リストＢに開示されている。
0004189443.tif 000005
0004189443.tif 000006
【００３３】
【実施例】
本発明は、１０進１６のデフォルトマスク値を用いて（各Ｒ、Ｇ、Ｂ、Ａ値の４ビットがマスクされた）数種類のサンプルビットマップイメージに適用される。かくして、損失のある圧縮は検査され、マスク値は画質の劣化が目立たないようにセットされる。最初に、サンプル画像が圧縮され、次に、画像の圧縮された表現が逆圧縮される。サンプル画像は６４０画素×４８０画素のサイズであり、３２ビットで各画素が表される。圧縮／逆圧縮動作はパーソナルコンピュータによる実行中に計測された。比較の目的のため、圧縮及び逆圧縮動作はＪＰＥＧ標準の実装を用いて同一画像上で行われた。以下に示す正確なタイミング値は、上記アルゴリズムが異なるコンピュータシステム上で実現された場合には変化するが、重要な統計量は、本発明の結果とＪＰＥＧ標準の結果との間の相対的な差である。以下の表３には、圧縮及び逆圧縮動作の結果が示されている。Ｒは得られた圧縮率であり、Ｔは圧縮及び逆圧縮に関する秒単位の消費時間である。
【００３４】
0004189443.tif 000007
上記の試験結果によると、本発明の圧縮比は、著しくはないがＪＰＥＧ標準の圧縮比よりも優れている。しかし、画像を圧縮及び逆圧縮するため必要な総時間は、本発明を用いる場合にＪＰＥＧ標準を用いる場合よりも著しく短縮される。本発明を用いる場合の処理時間は、各画像に対しＪＰＥＧ標準を用いる場合の処理時間の約１．３％である。
【００３５】
以下、本発明のソフトウェア実装について説明する。図１１はコンピュータシステム上に実現された本発明のソフトウェアによる実施例を示す図である。圧縮されていない画像１８０はコンピュータシステム１８４に連結された記憶装置１８２に格納される。コンピュータシステム１８４は、非圧縮画像１８０を読み込み、その画像を圧縮するため本発明による圧縮機能１８６を実行する。圧縮動作の結果は更なる用途のため記憶装置１８２の圧縮画像１８８に格納される。次に、同じコンピュータシステム１８４、又は、（図示しない）異なるコンピュータシステムは、圧縮画像を読み込み、その画像を逆圧縮するため、本発明による逆圧縮機能１９０を実行する。逆圧縮画像はコンピュータシステムのユーザに提示するため表示装置１９２に送られる。
【００３６】
上記圧縮及び逆圧縮方法は、汎用コンピュータで動作するソフトウェアに実装してもよいが、本発明の好ましい実施例は、本発明の方法を用いて利用可能な固有の並列性の利点を生かすマルチプロセッサハードウェア実装である。圧縮及び逆圧縮はどちらも重要ではあるが、実際上、画像は典型的に１回だけ圧縮され、何回も逆圧縮される。従って、逆圧縮の速度が非常に重要である。逆圧縮ステップがマルチプロセス装置上に並列に実現され得るならば、全体的な逆圧縮時間は劇的に短縮され得る。以下の表４のリストには、逆圧縮処理が疑似コードで一般的に記載されている。
0004189443.tif 000008
表４の疑似コードに基づいて、３通りの各内部ループに対し一つずつの３通りのレベルのＲＧＢＡ四つ組書き込み動作を逆圧縮処理中に同時に行うことが可能である。各ＲＧＢＡ四つ組書き込み動作は、全ての他の書き込み動作とは独立しているので、圧縮されたデータ表現から元のビットマップイメージを再生するため多重処理装置を並列に使用することが可能である。例えば、画像データのブロックに８色が存在する場合、異なる色を処理する８台のプロセッサが各プロセッサに割り当てられた色に関するＲＧＢＡ四つ組を書き込むため並列に動作し得る。かかるシステムは、マルチメディアパーソナルコンピュータアプリケーションの逆圧縮速度を増大する。
【００３７】
好ましいハードウェア実装において、逆圧縮装置は３２ビット幅のデータパスを備えたＭ×Ｎ形の分配器によって実現される。図１２には、逆圧縮のため使用されるＭ＊Ｎ形の分配器が示されている。分配器への入力ライン数（Ｍ）は８にセットされ、出力ライン数（Ｎ）は６４にセットされる。出力ラインは（図示しない）連続したメモリ要素に接続される。入力ライン数Ｍは実際の画像の色グループ数と一致すべきである。しかし、入力ライン数Ｍを８にセットし、画像中の色グループ数が８よりも大きい場合、色グループの組の全体は、８個の色グループの細分に分割され、その細分は順番に処理され得る。この処理レベルは並列化を使用しない。
【００３８】
現在の色グループのあらゆる細分に対し、分配器はマトリクス中の要素の値に応じてＭ本の入力からＮ本の入力にデータを送る。１台の分配器が色グループの細分毎に使用される。マトリクスはグループフラグの組及び行フラグの組によって与えられた情報を用いて形成される。入力ｉに対応するマトリクス：
Ａ＝｛ａij｝，  １＜＝ｉ＜＝８，  １＜＝ｊ＜＝６４
の第１行は以下の通り設定される。
【００３９】
Ｐ＝１  かつ  Ｑ＝１  であるならば  ａij＝１
さもなければ                        ａij＝０
但し、Ｐは、ｍ＝（ｉｎｔ）（ｊ／８）であるとき、グループフラグの組のビットｍの値であり、Ｑは、ｎ＝ｊ％８であるとき、色グループｉに対応するｍに対する行フラグの組のビットｎの値である。
【００４０】
図１３は逆圧縮回路のブロック図である。圧縮データ２００はローカルメモリ２０２に格納される。ローカルメモリはＭ本の入力ラインを介して圧縮データを少なくとも１台のＭ×Ｎ形分配器２０４に伝達する。分配器２０４の入力／出力マトリクスはデータに関するシフト演算によって形成される。加算又は乗算演算は必要とされず、浮動小数点数値は処理されない。Ｍ×Ｎ形分配器２０４は全てのデータをＭ本の入力から関連したＮ本の出力に送り、高速６４×３２形ローカルメモリ２０６に転送する。非圧縮データ２０８は、非圧縮画像のコンピュータモニタへの表示のような更なる処理のため高速６４×３２ローカルメモリから読み出される。
【００４１】
上記の通り、本発明は現在考量し得るベストモードに関して説明されているが、本発明に、当業者の能力の範囲内で、かつ、別の新たな発明を行うことなく種々の変形、動作モード及び実施例が許されることは明らかである。従って、特許請求の範囲に記載された技術範囲が保護されることを意図している。
以下、添付リストＡ及び添付リストＢは、夫々、本発明の圧縮アルゴリズム及び逆圧縮アルゴリズムのＣ言語による実装例である。上記疑似コードのリスト及び以下の添付リストは、著作権の保護を受けている。
【００４２】
図１４乃至１６は、画像データのブロックを圧縮するアルゴリズムのＣ言語による実装例のリストである。図１７は、予め圧縮された画像データのブロックを逆圧縮するアルゴリズムのＣ言語による実装例のリストである。
【図面の簡単な説明】
【図１】従来技術によるカラーグラフィックス画像と、関連した記憶表現とを示す図である。
【図２】本発明よる序数として表されたＲＧＢＡ四つ組を用いた８×８形ブロックの例を示す図である。
【図３】序数のＲＧＢＡ四つ組へのマッピングを示す図である。
【図４】図２のブロックの例に対するデータ構造をテキストで表現した図である。
【図５】コンピュータメモリに記憶された図４のデータ構造の例を示す図である。
【図６】本発明による圧縮されたブロックを記憶する一般化されたデータ構造を示す図である。
【図７】本発明による画像データ圧縮方法の上位レベルフローチャートである。
【図８】本発明による画像データ圧縮方法の上位レベルフローチャートである。
【図９】本発明による先に圧縮された画像データの逆圧縮方法の上位レベルフローチャートである。
【図１０】本発明による先に圧縮された画像データの逆圧縮方法の上位レベルフローチャートである。
【図１１】本発明のソフトウェアによる実施例を示す図である。
【図１２】逆圧縮のため使用されるＭ＊Ｎ分配器を示す図である。
【図１３】逆圧縮回路のブロック図である。
【図１４】画像データのブロックを圧縮するアルゴリズムのＣ言語による実装例のリストである。
【図１５】画像データのブロックを圧縮するアルゴリズムのＣ言語による実装例のリストである。
【図１６】画像データのブロックを圧縮するアルゴリズムのＣ言語による実装例のリストである。
【図１７】予め圧縮された画像データのブロックを逆圧縮するアルゴリズムのＣ言語による実装例のリストである。
【図１】
0004189443.tif 000009
【図２】
0004189443.tif 000010
【図３】
0004189443.tif 000011
【図４】
0004189443.tif 000012
【図５】
0004189443.tif 000013
【図６】
0004189443.tif 000014
【図７】
0004189443.tif 000015
【図８】
0004189443.tif 000016
【図９】
0004189443.tif 000017
【図１０】
0004189443.tif 000018
【図１１】
0004189443.tif 000019
【図１２】
0004189443.tif 000020
【図１３】
0004189443.tif 000021
【図１４】
0004189443.tif 000022
【図１５】
0004189443.tif 000023
【図１６】
0004189443.tif 000024
【図１７】
0004189443.tif 000025