JPH1196345A - グラフィックス画像の圧縮及び逆圧縮方法 - Google Patents

Abstract

(57)【要約】 【課題】 本発明は、良好な圧縮率と短縮された処理時
間が得られるグラフィックス画像データの圧伸方法の提
供を目的とする。 【解決手段】 画像データの各ブロックの別個の色は識
別され、序数が割り当てられる。ブロックのデータ構造
は、別個の色の数、圧縮画質マスク値、実際のＲＧＢＡ
四つ組、並びに、ブロック内の特定画素での特定色の有
無を示す別個の色毎のグループフラグの組及び行フラグ
の組により構成され、記憶される。画像を逆圧縮するた
め、ブロックの全画素のＲＧＢＡ四つ組がブロックのデ
ータ構造から再生される。損失有り・無しの両方の圧縮
方法が得られる。

Description

【発明の詳細な説明】

【０００１】

【発明の属する技術分野】本発明はデータ圧縮及び逆圧
縮に係わり、特に、類似カラーの組に従ってカラーグラ
フィックス画像を符号化する方法に関する。

【０００２】

【従来の技術】カラーグラフィックス画像は、コンピュ
ータシステム、特に、マルチメディアパーソナルコンピ
ュータによる表示のため幅広く使用されている。提供さ
れる解像度及び画像に表現され得るカラー数が高まると
共に、カラーグラフィックス画像を表現するデータのサ
イズは拡大する。また、使用されるコンピュータモニタ
が大きくなると共に、ユーザはより大きい画像の表示を
要求する。カラーグラフィックス画像を格納するため必
要とされるメモリ空間の削減及びかかる画像を伝送及び
表示するため必要とされる時間の短縮は、従来からコン
ピュータグラフィックス技術の重要な目標である。

【０００３】図１は、従来技術によるカラーグラフィッ
クス画像及びその関連した記憶表現を示す図である。ビ
ットマップイメージ１０は、１行あたりｍ画素のｎ行を
有する。典型的に、ｎ及びｍは８で割り切れる数であ
る。ビットマップイメージ１０は、論理的に８画素×８
画素の矩形に分割され得る。従って、ビットマップイメ
ージの左右方向にｍ／８個のブロックがあり、ビットマ
ップイメージの上下歩行にｎ／８個のブロックがある。
換言すると、（ｍ／８）＊（ｍ／８）個の８×８形のブ
ロックがビットマップイメージに含まれる。ある８×８
形のブロックは、（ｉ，ｊ）のペアで参照することがで
き、ここで、ｉは０乃至（ｍ／８−１）の範囲内に収ま
り、ｊは０乃至（ｎ／８−１）の範囲に収まる。

【０００４】８×８形の各ブロック１２は６４画素を含
む。各画素はＲＧＢＡの四つ組１４として表現される。
ＲＧＢＡ四つ組１４は、赤色値（Ｒ）１６と、緑色値
（Ｇ）１８と、青色値（Ｂ）２０と、輝度値（Ａ）２２
とを含む。画素の色及び輝度は、Ｒ、Ｇ、Ｂ及びＡの値
によって決まる。殆どのカラー画像の場合、８×８形の
ブロックは、５乃至１２色の異なる色を含む。Ｒ、Ｇ、
Ｂ及びＡの各値は、８ビットのバイトに記憶される。従
って、各画素は４バイトの記憶容量を占有し、８×８形
のブロックは２５６バイトの記憶容量を占有する。これ
により、ビットマップイメージ１０は、２５６＊（ｍ／
８＊ｎ／８）バイトの記憶容量を必要とする。例えば、
ビットマップが１行あたり６４０画素の４８０行からな
るとき、圧縮されていないビットマップイメージデータ
のサイズは、２５６＊（６４０／８＊４８０／８）バイ
ト、即ち、1,228,800 バイトである。ビットマップが１
行あたり１２８０画素の１０２４行からなるとき、圧縮
されていないビットマップイメージデータのサイズは、
２５６＊（１２８０／８＊１０２４／８）バイト、即
ち、5,242,880 バイトである。従って、圧縮されていな
いビットマップイメージは大量の記憶容量を必要とす
る。

【０００５】従来の画像圧縮の一つの方法は、国際標準
化機構（ＩＳＯ）により認可されたグループであるジョ
イントフォトグラフィックエクスパートグループ（ＪＰ
ＥＧ）によって提案されている。ＪＰＥＧ圧縮標準は、
僅かに識別できる画像の劣化を伴ってビットマップ化さ
れた画像のサイズを縮小する損失のある画像圧縮アルゴ
リズムである。損失のある圧縮方法は、ある程度の絵的
な情報を無視することにより画像のサイズを縮小する。
対照的に、損失のない圧縮方法は、画像が通常要求する
ビット数をデータを失うことなく削減する。ＪＰＥＧ圧
縮アルゴリズムは、カラー画像を、上記の如く輝度及び
色を表す数値を有する画素の行に変換する。画像は、１
６画素×１６画素である各ブロックに分割され、各ブロ
ック毎に一つおきの画素を取り除くことにより８画素×
８画素のブロックに削減される。この圧縮アルゴリズム
は、少ないデータで表現することができるように各ブロ
ック毎に平均カラー値を計算する公式を使用する。画像
データを復元するため、この処理は画素の圧縮を解除す
べく反転される。

【０００６】ＪＰＥＧ標準は広く使用されているにも係
わらす欠点がある。ＪＰＥＧアルゴリズムは、画像内の
関連した画素に対する局部平均カラー値を計算するた
め、フーリエ変換、ハフマン符号化、“ジグザグ化(zig
zagging)”及びＹＵＶ変換の計算を使用する。このアル
ゴリズムは、画像内の画素の行に使用される各カラーを
曲線として表現する。局部平均カラー値は、曲線を表現
する多項式の項に対し、コサイン関数を計算し、浮動小
数点係数を乗算することにより計算される。

【０００７】

【発明が解決しようとする課題】上記の従来技術による
アルゴリズムの計算は、非常に時間がかかり、全体的な
画像圧伸の速度に悪影響を与える。コサイン関数の浮動
小数点演算及び乗算演算を行うことなくカラーグラフィ
ックス画像を圧伸する高速な方法が必要とされる。ま
た、良好な圧縮率を与え、逆圧縮の間に高程度の並列化
をなし得る方法は、コンピュータグラフィックス技術に
重要な価値を付加する。

【０００８】

【課題を解決するための手段】本発明はグラフィックス
画像データを圧縮及び逆圧縮する方法を提供する。複数
の行を有し、各行には複数の列があり、各列は画素を含
み、各画素は赤色値、緑色値、青色値及び強度値によっ
て表された色を有する複数の行からなるグラフィックス
画像データのブロックを圧縮されたブロックに圧縮する
方法は、上記ブロックの画素に在る全ての色を識別する
ことにより、各色序数が一つの色を表し、上記ブロック
内の各画素毎に１画素の色に対応した１個の色序数を含
む色序数の配列を作成する段階と、選択された一つの色
に対する赤色値、緑色値、青色値及び強度値を上記圧縮
されたブロックに格納する段階と、上記色序数の配列に
従って選択された色の画素を有するブロック内の行を示
すグループフラグの組を作成する段階と、上記グループ
フラグの組を圧縮されたブロックに格納する段階と、上
記色序数の配列に従って選択された色の画素を有するブ
ロックにおいて１組の行フラグによって表された選択さ
れた色の画素を有する行内で、選択された色の画素を有
する列を示す少なくとも１組の行フラグを作成する段階
と、上記行フラグの組を圧縮されたブロックに格納する
段階と、ブロックの全ての色に対し上記の段階を繰り返
す段階とからなる。

【０００９】圧縮されたグラフィックス画像データのブ
ロックを圧縮されていないブロックに逆圧縮する方法
は、圧縮されたブロックから選択された色に対し、赤色
値、緑色値、青色値及び強度値を得る段階と、上記圧縮
されたブロックから選択された色に対し、グループフラ
グの組を得る段階と、上記圧縮されたブロックの少なく
とも１行で選択された色の有無を示す上記グループフラ
グの組の中の一つの組に対応する行フラグの組を得る段
階と、赤色値、緑色値、青色値及び強度値を、上記行フ
ラグの組により示されるような選択された色を有する列
及び上記グループフラグの組により示されるような選択
された色を有する行によって指定された選択された場所
で圧縮されていないブロックに書き込む段階と、上記圧
縮されたブロックの少なくとも１行で選択された色の有
無を示す上記グループフラグの組の各フラグに対し上記
段階を繰り返す段階と、上記圧縮されたブロックの全て
の別個の色組合せに対し上記段階を繰り返す段階とから
なる。

【００１０】本発明により得られる利点及び新規性のあ
る特徴は、以下の説明に記載され、以下の実施例に基づ
いて当業者には明らかであり、かつ、本発明を実施する
ことにより知ることができる。本発明の別の実施例によ
れば、上記の利点及び他の利点は、複数の行を有し、各
行には複数の列があり、各列は画素を含み、各画素は赤
色値、緑色値、青色値及び強度値によって表された色を
有する複数の行からなるグラフィック画像データを圧縮
されたブロックに圧縮する装置により達成される。この
装置は、上記ブロックの画素に在る全ての色を識別する
ことにより、各色序数が一つの色を表し、上記ブロック
内の各画素毎に１画素の色に対応した１個の色序数を含
む色序数の配列を作成する手段と、上記色序数の配列に
従って選択された色の画素を有するブロックの行を示す
第１のフラグの組を作成する手段と、上記色序数の配列
に従って上記選択された色の画素を有するブロックの行
の範囲内で選択された色の画素を有する列を示す第２の
フラグの組であって、選択された色の画素を有する各行
は１組の第２のフラグの組により表される第２のフラグ
の組を作成する手段と、選択された一つの色に対し、赤
色値、緑色値、青色値及び強度値と、上記第１のフラグ
の組と、上記少なくとも１組の第２のフラグの組を上記
圧縮されたブロックに格納する手段とからなる。

【００１１】本発明の別の実施例において、上記利点及
び他の利点は、グラフィックス画像データの圧縮された
ブロックを圧縮されていないブロックに逆圧縮する装置
によって実現される。上記装置は、複数の別個の赤、
緑、青及び強度値の色組合せを有する圧縮されたブロッ
クであって、別個の各色組合せは、圧縮されていないブ
ロックの行で別個の色組合せの有無を示すグループフラ
グの組と、別個の色組合せを有する圧縮されていないブ
ロックの各行に対し圧縮されていないブロックの列で別
個の色組合せの有無を示す少なくとも１組の行フラグの
組とを有するグラフィックス画像データの圧縮されたブ
ロックを圧縮されていないブロックに逆圧縮する。上記
装置は、圧縮されたブロックから選択された色に対し赤
色値、緑色値、青色値及び強度値を読み出し、上記圧縮
されたブロックから選択された色に対し上記グループフ
ラグの組を読み出し、上記圧縮されたブロックの少なく
とも１行で選択された色の有無を示す上記グループフラ
グの組の中のグループフラグに対応する行フラグの組を
読み出す手段と、赤色値、緑色値、青色値及び強度値
を、上記行フラグの組により示されるような選択された
色を有する列及び上記グループフラグの組により示され
るような選択された色を有する行によって指定された選
択された場所で圧縮されていないブロックに書き込む手
段とを有する。

【００１２】

【発明の実施の形態】本発明の他の目的及び利点は、以
下の本発明の実施例の詳細な説明を読むことにより当業
者にとって明らかであろう。以下の説明では、本発明を
実施するため熟慮されたベストモードの実例によって本
発明の好ましい実施例だけを示す。本発明は、他の実施
例及び異なる実施例として実現することが可能であり、
本発明の実施例の細部は、本発明から逸脱することな
く、種々の明瞭な点で変更することが可能である。従っ
て、添付図面及び以下の説明は、本質的に実例であり、
本発明を制限するものではないことに注意する必要があ
る。

【００１３】本発明は、図１に示されるような圧縮され
ていないビットマップ画像データに関して動作し、画像
の圧縮表現を生成する。本発明は、また、圧縮されたビ
ットマップ画像データに関して動作し、元の圧縮されて
いない表現を生成する。一般的に言うと、画像を圧縮す
るため、本発明は、画像の８画素×８画素からなる全ブ
ロックを順番に別々に処理する。各ブロック毎に、ブロ
ックに在る全ての別個の色が識別され、序数が割り当て
られる。ブロックのデータ構造は、ブロック内にある別
個の色の個数と、（以下に説明する）圧縮画像品質マス
ク値と、ブロックに在る各色に対する実際のＲＧＢＡ四
つ組と、ブロック内の特定の画素での特定の色の有無を
示すグループフラグの組及び行２値フラグの組とを格納
するため生成される。得られたデータ構造は、ブロック
に対する元のＲＧＢＡ四つ組の集合よりも遙かに少ない
記憶容量しか必要としない。ブロックのデータ構造は、
メモリ又はコンピュータファイルに格納され、画像の次
のブロックが処理される。この処理はビットマップイメ
ージの全てのブロックに対し繰り返される。画像を逆圧
縮するため、各ブロック内の全画素のＲＧＢＡ四つ組
は、ブロックのデータ構造から再生される。この再生は
画像の全てのブロックに対し繰り返される。

【００１４】本発明による圧縮された画像データの再生
は、簡単な例を参照することによって巧く理解できる。
図２は、本発明により序数として表されたＲＧＢＡ四つ
組を備えた８×８形ブロックの例を示す図である。ブロ
ック２４はビットマップイメージからの１個の８×８形
ブロックを表す。このブロックは、色序数テーブルとも
称される。図２に示されたブロックは、水平方向に０乃
至７の指数を有し、垂直方向に０乃至７の指数を有す
る。或いは、ブロックは６４要素の１次元配列として表
現してもよい。ブロックの画素は、ブロックに現れた別
個の色を判定するため走査される。見つけられた各別個
の色は序数が割り当てられる。

【００１５】図３は序数のＲＧＢＡ四つ組へのマッピン
グを示す図である。例えば、同図の最上行の序数１は、
赤色値Ｒ１と、緑色値Ｇ１と、青色値Ｂ１と、輝度値Ａ
１とにより構成された色を示す。同様に、序数２は、赤
色値Ｒ３と、緑色値Ｇ３と、青色値Ｂ３と、輝度値Ａ３
とにより構成された色を示す。ＲＧＢＡの各組合せは、
現在のブロックの少なくとも１個の画素に対する固有の
色及び輝度の指定である。図２のブロックの例に現れる
他の色は図３に示されている。

【００１６】図２を再度参照するに、色序数テーブル
は、第１の色が０行１列（第０行第１列）と、５行０列
と、５行２乃至７列と、６行２乃至６列で検出されたこ
とを示す。第２の色は、３行０及び６列、４行０乃至４
列、５行１列、６行０乃至１列で検出される。第３の色
は、０行０列、０行２乃至３列、１行１、３、５列、２
行０乃至７列、６行６乃至７列で検出される。残りの色
も同様に識別される。図２に示された例では、１６個の
異なる色がブロック２４に現れている。ブロック内の各
色の出現は、圧縮されたブロックのビットによりブロッ
クの行における特定の色の有無を示す２値フラグの組と
して表すことが可能である。別のフラグの組は、指定さ
れた色を有する選択された行に対応する全ての列を示す
指定された色を有する行毎に発生される。

【００１７】図２に示されたブロック２４の表現が与え
られた場合、ブロックで検出された各色に対するフラグ
の組が作成され、ブロックのデータ構造に格納される。
例えば、第１の色は第０、５及び６行で検出される。ブ
ロックの上記行に対する２値フラグの組は値｛1000011
0｝を有する第１の色に対し生成される。上記のフラグ
はグループフラグと称される。グループフラグの組の各
位置は、第０行から始まり第７行まで続くブロックの行
を表す。組の位置が１であるとき、選択された色が行の
どこかに存在することを示し、組の位置が０であると
き、選択された色がその行に無いことを示す。選択され
た色を有する各行に対し、現在の行の各列に選択された
色が存在するかどうかを示す２値フラグの組が生成され
る。

【００１８】これらのフラグは行フラグと称される。例
えば、第１の色は第１行の第１列だけで検出される。従
って、値｛01000000｝を有する２値フラグの組は、第１
の色が列１で検出され、その行の他の列で検出されない
ことを示すため生成される。同様に、値｛10111111｝を
有する２値フラグの組は、行５の列０、２−７に第１の
色が在ることを表すため生成される。値｛00111100｝を
有する２値フラグの組は、行６の列２乃至５に第１の色
が存在することを示すため生成される。この組を生成す
る処理は、ブロックで見つけられた全ての色に対し行わ
れる。全ての色が処理されたとき、従来の方法よりも必
要な記憶容量が著しく減少し、コサイン関数評価又は浮
動小数点係数乗算演算を必要としないブロックのデータ
構造が完全に作成される。

【００１９】図４は、図２のブロックの例に対するデー
タ構造をテキスト的に表現した図である。データ構造の
各フィールドは、メモリの１バイトに格納される。Ｎフ
ィールド３０は、ブロックで検出された別個の色の数を
示す。Ｎ＝６である本例の場合、色の数は６個である。
マスク値フィールド３２は類似した色の組を比較する場
合に使用される。マスク値フィールドについて後で詳し
く説明する。Ｒ１、Ｇ１、Ｂ１及びＡ１バイト３４は、
第１の色に対するＲ値、Ｇ値、Ｂ値及びＡ値を保持す
る。損失のない圧縮の場合、Ｒ値、Ｇ値、Ｂ値及びＡ値
は、元のブロックと同様に４バイトに格納される。損失
のある圧縮の場合、各成分は４ビットで格納される。そ
の場合、Ｒ値、Ｇ値、Ｂ値及びＡ値は２バイトに格納さ
れる。グループ１フィールド３６は、ブロックの行に第
１の色が在るか否かを示すビットを含む。上記の如く、
第１の色は行０、５及び６で検出される。従って、グル
ープ１フィールド３６のグループフラグの組は、値｛10
000110｝を有する第１の色に対し作成される。最下位ビ
ットはブロックの一番下の行を表す。第１の色は３本の
行で見つけられるので、３個の別の２値フラグの組が第
１の色が見つけられた上記３本の行のコラムを表わすた
め必要とされる。従って、データ構造は、行１０のフィ
ールド３８と、行１５のフィールド４０と、行１６のフ
ィールド４２の３組の行フラグの組を含む。フィールド
名の数字は、グループ番号及び行番号を示す。例えば、
行１０はグループ番号１と行番号０を表し、行１５はグ
ループ番号１と行番号５を表し、行１６はグループ番号
１と行番号６を表す。上記の如く、値｛01000000｝は、
第１の色が第１列で検出され、それ以外の列では検出さ
れないことを表すため生成される。この値は行１０のフ
ィールド３８に格納される。同様に、値｛10111111｝
は、第１の色が第５行の第０、２乃至７行に存在するこ
とを表すため生成され、行１５のフィールド４０に格納
される。値｛00111100｝は、第１の色が第６行の第２乃
至５列に在ることを示すため生成され、行１６のフィー
ルド４２に格納される。

【００２０】本例において、第４の色は、Ｒ２、Ｇ２、
Ｂ２、Ａ２の組合せフィールド４４にマップされる。第
４の色は、第０、１、３及び４行で検出されるので、グ
ループ２のフィールド４６には値｛11011000｝が与えら
れる。この色は４本の行で検出されるので、４組のライ
ンフラグの組は、行２０、行２１、行２３及び行２４で
ある。これらのフィールドには、夫々、値｛0000111
1｝、｛10101011｝、｛00000100｝及び｛00000111｝が
与えられる。第２の色は、Ｒ３、Ｇ３、Ｂ３、Ａ３の組
合せフィールド４８にマップされる。第２の色は、第３
乃至６行で検出されるので、グループ３のフィールド５
０には値｛00011110｝が与えられる。この色は４本の行
で検出されるので、４組のラインフラグの組は、行３
３、行３４、行３５及び行３６である。これらのフィー
ルドには、夫々、値｛10000010｝、｛11111000｝、｛01
000000｝及び｛11000000｝が与えられる。第５の色は、
Ｒ４、Ｇ４、Ｂ４、Ａ４の組合せフィールド５２にマッ
プされる。第５の色は、第３行で検出されるので、グル
ープ４のフィールド５４には値｛00010000｝が与えられ
る。この色は１本の行だけで検出されるので、１組のラ
インフラグの組は、行４３である。このフィールドに
は、第５の色が第３行の第１乃至４列で検出されたこと
を反映させるため、値｛01111001｝が与えられる。第６
の色は、Ｒ５、Ｇ５、Ｂ５、Ａ５の組合せフィールド５
６にマップされる。第６の色は、第７行で検出されるの
で、グループ５のフィールド５８には値｛00000001｝が
与えられる。第６の色は１本の行だけで検出されるの
で、１組のラインフラグの組は、行５７である。このフ
ィールドには、第６の色が第７行の第０乃至６列で検出
されたことを反映させるため、値｛11111110｝が与えら
れる。

【００２１】第３の色は、Ｒ６、Ｇ６、Ｂ６、Ａ６の組
合せフィールド６０にマップされる。しかし、第３の色
にはグループフラグの組又は行フラグの組が付随しな
い。ブロック中の第３の色の位置を記述する情報は逆圧
縮処理中に再生され得る。これらの位置は、全ての他の
色が処理された後に残されたブロックの画素である。従
って、第３の色を有するがその指定は不必要である。

【００２２】図５は、図４に示されたデータ構造がコン
ピュータメモリに記憶された場合の一例である。本例で
は損失のある圧縮を使用し、Ｒ、Ｇ、Ｂ及びＡの値は、
全部でバイトに格納される。この例の場合、ブロックを
表す圧縮されたデータを格納するため必要とされるバイ
トの総数は３２である。圧縮されていないブロックは２
５６バイトを必要とするので、本発明の動作によってサ
ンプルブロックに対し８：１の圧縮率が得られる。

【００２３】図６は、本発明による圧縮されたブロック
を格納する一般化されたデータ構造を示す図である。圧
縮されたブロックの（バイト単位）サイズ６２は、マス
ク値４と共に格納される。ブロックの各色に対し、Ｒ、
Ｇ、Ｂ及びＡの値６６が格納され、グループフラグの組
６８が生成される。現在の色を有する各行毎に、行内の
現在の色の位置を記憶するため行フラグの組７０が生成
される。このデータ構造は、ビットマップイメージの全
ブロックに対し繰り返される。

【００２４】圧縮中に画像データのブロックに対するデ
ータ構造を構築する本発明の方法は、二つの例外処理が
ある。ブロックが一つの色しか含まない場合、１個のＲ
ＧＢＡの色グループしかなく、データ構造のフォーマッ
トは、｛Ｎ＝４，マスク値，ＲＧ，ＢＡ｝である。従っ
て、ブロックは損失のある圧縮の場合、４バイトだけで
表され、損失のない圧縮の場合、６バイトで表される。
６４通りのＲＧＢＡ色グループが存在する場合、即ち、
各画素が異なる色である場合、フォーマットは、 ｛Ｎ＝１３０，マスク値，Ｒ１Ｇ１，Ｂ１Ａ１，Ｒ２Ｇ
２，Ｂ２Ａ２，Ｒ３Ｇ３，Ｂ３Ａ３，．．．Ｒ６４Ｇ６
４，Ｂ６４Ａ６４｝ である。しかし、実際上、８×８形のブロックの各画素
の色が異なる可能性は殆ど無い。

【００２５】図４を参照するに、マスク値のフィールド
３２は、ブロックの２個の画素を比較する際に使用され
るマスクビットの数を保持する。マスク値は、圧縮され
ていないブロックの圧縮中に使用され、圧縮されたブロ
ックの逆圧縮中に使用するため逆圧縮機能に伝えられ
る。本発明の好ましい実施例において、マスク値のデフ
ォルト値は１６Ｄ、又は、０００１００００Ｂである。
これは、色を比較する際にＲ、Ｇ、Ｂ及びＡの各値の最
下位４ビットがマスクされることを意味する。即ち、
Ｒ、Ｇ、Ｂ及びＡの各値の最上位４ビットだけが各画素
毎に比較される。これにより、類似しているが一致しな
い２個の色が得られ、これらの２個の色は圧縮目的のた
めには同じ色であるとみなされる。マスク値は、圧縮ア
ルゴリズムのユーザによる設定が行える変数である。形
式的に言うと、２個のＲＧＢＡ四つ組であるＲｐＧｐＢ
ｐＡｐ及びＲｑＧｑＢｑＡｑは、 Ｒｐ ｄｉｖ マスク値＝Ｒｑ ｄｉｖ マスク値
（Ｒｐのマスク値による除算の商＝Ｒｑのマスク値によ
る除算の商） Ｇｐ ｄｉｖ マスク値＝Ｇｑ ｄｉｖ マスク値 Ｂｐ ｄｉｖ マスク値＝Ｇｑ ｄｉｖ マスク値 及
び Ａｐ ｄｉｖ マスク値＝Ａｑ ｄｉｖ マスク値 である場合に、色に関して一致しているとみなされる。
マスク値が零に設定されたとき、マスキングは行われな
い。これは損失のない圧縮であり、元の情報を全て含む
ので、逆圧縮された画像は最良の品質を有する。しか
し、この場合、得られる圧縮率は低い。マスク値が１０
進の１６に設定された場合、逆圧縮された画像の品質は
マスク値が零の時ほど良好ではないが、圧縮率は改善さ
れる。本発明のデフォルト値で、殆どのユーザは、圧縮
及び逆圧縮動作が行われた後、画質の劣化を検出できな
い。ユーザは、圧縮率対画質に関するユーザの好みに基
づいてマスク値を選択することができる。マスク値が小
さいほど、圧縮目的のため同じ色であるとみなされる別
個の色は少なくなり、圧縮率が低下し、マスク値が大き
くなると共に、圧縮目的のため同じ色であるとみなされ
る別個の色が増加し、圧縮率は上昇する。

【００２６】図７及び８は、本発明による画像データの
圧縮方法の上位レベルのフローチャートである。圧縮ス
タートステップ１００の後、この圧縮動作のマスク値が
ステップ１０２で得られる。マスク値は、所望の圧縮率
と結果として得られる逆圧縮された画像の品質とに基づ
いて本圧縮方法のユーザによって設定され得る。或い
は、マスク値は１６Ｄのようなデフォルト値にプリセッ
トしてもよい。マスク値は圧縮されるべき画像の全ての
ブロックに対し同一でもよく、又は、新しいマスク値が
各ブロックに対し指定されてもよい。画像データの圧縮
されていない８画素×８画素形ブロックは、圧縮処理の
ためステップ１０４で取得される。典型的に、画像デー
タはコンピュータシステムのファイルに格納され、ファ
イルが開かれ、画像データの最初のブロックがファイル
から読み出される。

【００２７】ステップ１０６において、圧縮されていな
いブロックの６４画素は、マスク値に従って、（図２に
示されたテーブルの例と類似した）全ての別個の色の色
序数テーブルを作成するため走査される。ブロックに存
在する色は識別され、各画素は画素に在る色の序数が割
り当てられる。２個の画素は画素のＲＧＢＡ値の差がマ
スク値よりも小さい場合、同じ色であるとみなされる。
ブロックの色序数テーブルが作成された後、色序数テー
ブルからの第１の色がステップ１０８で選択される。こ
の色は、ブロックに関する圧縮された画像データを保持
するデータ構造を作成する際に、最初に処理されるべき
色である。次に、ステップ１１０において、処理されて
いる現在の色に関するＲＧＢＡ値が画像データの圧縮さ
れていないブロックから抽出され、指定されてたマスク
値に従って圧縮されたブロックデータ構造に格納され
る。圧縮されたブロックデータ構造は図６に示されてい
る。色序数テーブルは、現在の色を有する圧縮されてい
ないブロック中の行を示すグループフラグの組を作成す
るため、ステップ１１２で走査される。ブロック中に８
本の行が在るので、８個の２値フラグの組はブロックの
行における現在の色の有無を示すために足りる。グルー
プフラグの組は８ビットのバイトで格納してもよい。グ
ループフラグの組は圧縮されたブロックに格納される。
ステップ１１４において、色序数テーブルは、現在のグ
ループフラグの組でフラグを立てられた各行に対し現在
の色を有する列を示す１組以上の行フラグの組を作成す
るため処理される。即ち、関連したビットがグループフ
ラグの組にセットされたブロックの各行に対し、ライン
フラグの組が生成される。ブロックには８本の列がある
ので、８個の２進フラグの組は、選択された行の列にお
ける現在の色の有無を充分に示すことができる。行フラ
グの組は８ビットのバイトで格納される。グループフラ
グの組にセットされたビットに対応する全ての行フラグ
の組は、圧縮されたブロックに格納される。圧縮処理は
結合子８Ａを経由して図８へ続く。

【００２８】図８のテストステップ１１６において、処
理すべき色が色序数テーブルに残されている場合、ＹＥ
Ｓ側パス１１８が選ばれ、結合子７Ｂを経由して図７の
ステップ１０８に進む。ステップ１０８では、処理され
るべき次の色が色序数テーブルの色から選択され、その
色が上記の通り処理される。ステップ１１６において、
処理されるべき色が色序数テーブルに残されていない場
合、ＮＯ側パス１２０が選ばれ、ステップ１２２に進
む。

【００２９】本発明の最適化の特徴として、画像データ
の元のブロックに最も頻繁に出現する色は、圧縮された
ブロックの最後の色として表現され、グループフラグの
組と行フラグの組は省略される。逆圧縮処理中に、この
色は、他のグループフラグの組及び行フラグの組によっ
て参照されない全ての画素に配置されているとみなされ
る。従って、最大の色グループのＲＧＢＡ値は、ステッ
プ１２２において、圧縮されたブロックの端に移され、
圧縮されたブロックの他のバイトはブロックを詰め、必
要に応じて、最大色グループによって残された記憶場所
の隙間を埋めるべく移される。ステップ１２４におい
て、ブロックの処理中に使用された圧縮されたブロック
のサイズ及びマスク値が圧縮されたブロックに格納され
る。圧縮されたブロックは、次に、ステップ１２６で出
力される。典型的に、この出力動作は、圧縮された画像
データを格納するため圧縮されたブロックのファイルへ
の書き込みを必然的に伴う。ステップ１２８において、
処理されるべき画像データのブロックが未だ有るなら
ば、ＹＥＳ側パス１３０が選ばれ、結合子７Ａを経由し
て図７のステップ１０４に進む。ステップ１０４におい
て、画像データの次の圧縮されていないブロックが圧縮
処理のため取得される。さもなければ、ＮＯ側パス１３
２が選ばれ、エンドステップ１３４に進み、この画像デ
ータに対する圧縮処理が終了する。

【００３０】以下の表１のリストには、本発明により画
像データのブロックを圧縮する疑似コードが記載されて
いる。本発明の圧縮アルゴリズムのＣ言語による実装は
添付リストＡとして添付されている。 −−−−−−−−−−−−−−−− 表１ −−−−−−−−−−−−−−−− 著作権 １９９７ 富士通マイクロエレクトロニクス インコーポレーティッド 色序数テーブルデータ構造を作成 圧縮されたブロックデータ構造を作成 マスク値を設定 色序数テーブルを初期化 圧縮されたブロックを初期化 異なる色の数を０に設定 現在マークされた色序数テーブル要素の数を０に設定 開始： ｉに関して０から６３までループ //色序数テーブル構築 もし ｉ番目の色序数テーブルが０であるならば 異なる色の数をインクリメント 現在の画素に対する入力データからのＲＧＢＡ値をｃに格納 ｋに関してｉから６３までループ もし ｋ番目の色序数テーブルが０であるならば もし ｃのマスク値による除算の商が入力データのｋ番目 の画素のＲＧＢＡ値のマスク値による除算の商と一 致するならば カラー序数テーブル[k] を異なる色の数に設定 現在マークされた色序数テーブル要素の数をインク リメント もしステートメントの終わり もしステートメントの終わり ｋに関するループの終わり 「続き」へ進む もしステートメントの終わり ｉに関するループの終わり 続き： もし 現在マークされた色序数テーブル要素の数が６４未満ならば 開始に戻る //未だ終了しない もしステートメントの終わり ｉに関して１から異なる色の数までループ //色を処理 新しい行フラグを真に設定 既にオンにされている現在の色フラグを偽に設定 ｊに関して０から６３までループ //色序数テーブルを処理 もし 新しい行が真ならば 行フラグインデックスを最も左側ビットに設定 新しい行を偽に設定 もしステートメントの終わり もし ｊ番目の色序数テーブルが１であるならば もし 既にオンされている現在の色フラグが偽ならば 現在の画素に対するＲＧＢＡ値を取得し圧縮されたブ ロックに格納 グループフラグのインデックスを圧縮されたブロック に設定 既にオンされている現在の色フラグを真に設定 圧縮されたブロックのＲＧＢＡグループの行フラグの 第１の組のインデックスを設定 もしステートメントの終わり もしステートメントの終わり 行フラグインデックスを右に１ビットシフト もし 行フラグインデックスが０ならば グループフラグのインデックスをインクリメント 行フラグインデックスを最も左側の位置にセット もしステートメントの終わり もしステートメントの終わり もし 圧縮されたブロックの長さが最大長さよりも大きいならば 非常に長いブロックを真にセット 「ファイナル」へ進む もしステートメントの終わり もしステートメントの終わり 最大の色グループのＲＧＢＡ値を圧縮されたブロックの端に移動 ファイナル： もし 非常に長いブロックが真ならば 全ての色のＲＧＢＡ値を圧縮されたブロックに詰める もしステートメントの終わり 圧縮されたブロックのサイズを圧縮されたブロックに格納 マスク値を圧縮されたブロックに格納 −−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−− 図９及び１０は、本発明による先に圧縮された画像デー
タを逆圧縮する方法の上位レベルのフローチャートであ
る。逆圧縮ステップは、圧縮された画像の表示が求めら
れる際に行われる。逆圧縮スタートステップ１５０の後
に、画像データの圧縮されたブロックは、ステップ１５
２で逆圧縮処理のため取得される。典型的に、圧縮され
たブロックはコンピュータシステム上のファイルに格納
され、ファイルが開かれ、画像データの最初に圧縮され
たブロックがファイルから読み出される。圧縮されたブ
ロックのサイズ及びマスク値は、ステップ１５４で圧縮
されたブロックの最初の二つの記憶場所から取り出され
る。ステップ１５６で、圧縮されたブロックの最後のＲ
ＧＢＡ値が取り出され、逆圧縮処理によって出力される
べき圧縮されていないブロックの全ての場所に書き込ま
れる。圧縮されていないブロックの選択された場所への
後続の書き込みはデフォルト色を上書きするが、この色
はブロックで最も頻繁に使用される色であるため、記憶
容量及び逆圧縮処理時間はこのステップによって節約さ
れる。ステップ１５８において、圧縮されたブロックの
第１の色が選択される。この色に対するＲＧＢＡ値は、
ステップ１６０においてマスク値を用いて圧縮されたブ
ロックから取り出される。次に、ステップ１６２におい
て、この色に対するグループフラグの組は圧縮されたブ
ロックから取り出される。この色がブロックの対応する
行で検出されることを示すグループフラグの組のあるビ
ットがセットされているならば、この色に関する行フラ
グの組は、ステップ１６４で圧縮されたブロックから取
り出される。この色の処理は結合子１０Ａを経由して図
１０のステップ１６６に進む。

【００３１】ステップ１６６において、ＲＧＢＡ値はビ
ットがセットされた行フラグの組の全ての列に関するグ
ループフラグと行フラグの組合せによって示される選択
された場所で圧縮されていないブロックに書き込まれ
る。行フラグの各組は、ブロックの現在の行の列に現在
の色が存在することを示す。列ビットが特定の行に関し
てセットされているならば、ＲＧＢＡ値は圧縮されてい
ないブロックの選択された画素に対する場所に書き込ま
れる。次に、ステップ１６８において、他の行フラグの
組が現在の色グループに対し存在するならば、ＹＥＳ側
のパス１７０が選ばれ、この色に関する次の行フラグの
組を得るため結合子９Ｃを経由して図９のステップ１６
４に進む。さもなければ、ＮＯ側のパス１７２が選ば
れ、テストステップ１７４に進む。ステップ１７４にお
いて、現在のブロックに対し、未だ処理されるべき色が
残されているならば、ＹＥＳ側のパス１７６が選ばれ、
次の色を選択するため結合子９Ｂを介して図９のステッ
プ１５８に戻る。さもなければ、ＮＯ側のパス１７８が
選ばれ、テストステップ１８０に進む。テストステップ
１８０において、この圧縮された画像に関して処理すべ
きブロックが未だ有るならば、ＹＥＳ側のパス１８２が
選ばれ、処理すべき次の圧縮されたブロックを得るため
結合子９Ａを経由して図９のステップ１５２に戻る。画
像の全ブロックが処理された場合、ＮＯ側のパス１８４
が選ばれ、エンドステップ１８６に進み、逆圧縮処理が
終了する。

【００３２】以下の表２のリストには、本発明による画
像データの先に圧縮されたブロックを逆圧縮する方法の
疑似コードが記載されている。本発明の逆圧縮アルゴリ
ズムのＣ言語による実装は添付リストＢに開示されてい
る。 −−−−−−−−−−−−−−−− 表２ −−−−−−−−−−−−−−−− 著作権 １９９７ 富士通マイクロエレクトロニクス インコーポレーティッド 圧縮されたブロックの寸法を取得 マスク値を取得 もし 圧縮されたブロックのサイズが１３０であるならば マスク値を用いて６４組のＲＧＢＡ値を取り出し ＲＧＢＡ値を出力された圧縮されていないブロックに格納 圧縮されたブロックのサイズを返し、戻る もしステートメントの終わり マスク値を用いて圧縮されたブロックから最後のＲＧＢＡ値を取り出し 最後のＲＧＢＡ値を圧縮されていないブロックの全ての場所に格納 もし 圧縮されたブロックのサイズが４であるならば 圧縮されたブロックのサイズを返し、戻る もしステートメントの終わり 開始： インデックスを圧縮されたブロック中に初期化 もし インデックスがブロックの端であるならば ファイナルへ進む もしステートメントの終わり 圧縮されたブロックから最初のＲＧＢＡ値を取り出し 圧縮されたブロックからグループフラグの組を取り出し グループフラグのビットインデックスを最も左側のビットにセット 続き： グループフラグのビットインデックスにより示された行フラグビットを取り出し もし 行フラグがセットされているならば ／／現在の行がこの色を有する／／ 行フラグの組を取り出し 行フラグのビットインデックスを最も左側のビットにセット ｊに関して１から７までループ ／／列の左から右へ／／ もし 列フラグがセットされているならば ／／現在の列がこの色 ／／を有する ＲＧＢＡ値を圧縮されていないブロックに格納 もしステートメントの終わり 行フラグのビットインデックスを右に１ビットシフト 圧縮されていないブロックへの出力書き込み用のインデックスをイ ンクリメント ループの終わり さもなければ 次の行へ飛び越し もしステートメントの終わり グループフラグのビットインデックスを右に１ビットシフト もし グループフラグインデックスが０であるならば 開始へ戻る ／／現在の色を処理済み さもなければ 続くへ戻る ／／同じ色を処理し続ける ファイナル： 圧縮されたブロックのサイズを返し、戻る −−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−

【００３３】

【実施例】本発明は、１０進１６のデフォルトマスク値
を用いて（各Ｒ、Ｇ、Ｂ、Ａ値の４ビットがマスクされ
た）数種類のサンプルビットマップイメージに適用され
る。かくして、損失のある圧縮は検査され、マスク値は
画質の劣化が目立たないようにセットされる。最初に、
サンプル画像が圧縮され、次に、画像の圧縮された表現
が逆圧縮される。サンプル画像は６４０画素×４８０画
素のサイズであり、３２ビットで各画素が表される。圧
縮／逆圧縮動作はパーソナルコンピュータによる実行中
に計測された。比較の目的のため、圧縮及び逆圧縮動作
はＪＰＥＧ標準の実装を用いて同一画像上で行われた。
以下に示す正確なタイミング値は、上記アルゴリズムが
異なるコンピュータシステム上で実現された場合には変
化するが、重要な統計量は、本発明の結果とＪＰＥＧ標
準の結果との間の相対的な差である。以下の表３には、
圧縮及び逆圧縮動作の結果が示されている。Ｒは得られ
た圧縮率であり、Ｔは圧縮及び逆圧縮に関する秒単位の
消費時間である。

【００３４】 表３ −−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−− １．ビットマップ４ 本発明 Ｒ＝５．９５ Ｔ＝０．２４ ＪＰＥＧ Ｒ＝５．０４ Ｔ＝１８．５０ ２．ビットマップ５ 本発明 Ｒ＝７．２８ Ｔ＝０．２３ ＪＰＥＧ Ｒ＝５．４５ Ｔ＝１８．００ ３．ビットマップ６ 本発明 Ｒ＝４．９１ Ｔ＝０．２０ ＪＰＥＧ Ｒ＝４．６６ Ｔ＝１８．５０ ４．ビットマップ８ 本発明 Ｒ＝６．８２ Ｔ＝０．２５ ＪＰＥＧ Ｒ＝５．４１ Ｔ＝１８．１０ −−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−− 上記の試験結果によると、本発明の圧縮比は、著しくは
ないがＪＰＥＧ標準の圧縮比よりも優れている。しか
し、画像を圧縮及び逆圧縮するため必要な総時間は、本
発明を用いる場合にＪＰＥＧ標準を用いる場合よりも著
しく短縮される。本発明を用いる場合の処理時間は、各
画像に対しＪＰＥＧ標準を用いる場合の処理時間の約
１．３％である。

【００３５】以下、本発明のソフトウェア実装について
説明する。図１１はコンピュータシステム上に実現され
た本発明のソフトウェアによる実施例を示す図である。
圧縮されていない画像１８０はコンピュータシステム１
８４に連結された記憶装置１８２に格納される。コンピ
ュータシステム１８４は、非圧縮画像１８０を読み込
み、その画像を圧縮するため本発明による圧縮機能１８
６を実行する。圧縮動作の結果は更なる用途のため記憶
装置１８２の圧縮画像１８８に格納される。次に、同じ
コンピュータシステム１８４、又は、（図示しない）異
なるコンピュータシステムは、圧縮画像を読み込み、そ
の画像を逆圧縮するため、本発明による逆圧縮機能１９
０を実行する。逆圧縮画像はコンピュータシステムのユ
ーザに提示するため表示装置１９２に送られる。

【００３６】上記圧縮及び逆圧縮方法は、汎用コンピュ
ータで動作するソフトウェアに実装してもよいが、本発
明の好ましい実施例は、本発明の方法を用いて利用可能
な固有の並列性の利点を生かすマルチプロセッサハード
ウェア実装である。圧縮及び逆圧縮はどちらも重要では
あるが、実際上、画像は典型的に１回だけ圧縮され、何
回も逆圧縮される。従って、逆圧縮の速度が非常に重要
である。逆圧縮ステップがマルチプロセス装置上に並列
に実現され得るならば、全体的な逆圧縮時間は劇的に短
縮され得る。以下の表４のリストには、逆圧縮処理が疑
似コードで一般的に記載されている。 −−−−−−−−−−−−−−−− 表４ −−−−−−−−−−−−−−−− 著作権 １９９７ 富士通マイクロエレクトロニクス インコーポレーティッド 圧縮ビットマップの全てのブロックに関してループ Ｎ個(m = 1, 2, ... N)の全色グループに関してループ 色ｍが出現する全行に関してループ 色ｍが出現する行内の全列に関してループ 色ｍに対するＲＧＢＡ四つ組を非圧縮画像の現在の位 置に書き込み ループの終わり ループの終わり ループの終わり ループの終わり −−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−− 表４の疑似コードに基づいて、３通りの各内部ループに
対し一つずつの３通りのレベルのＲＧＢＡ四つ組書き込
み動作を逆圧縮処理中に同時に行うことが可能である。
各ＲＧＢＡ四つ組書き込み動作は、全ての他の書き込み
動作とは独立しているので、圧縮されたデータ表現から
元のビットマップイメージを再生するため多重処理装置
を並列に使用することが可能である。例えば、画像デー
タのブロックに８色が存在する場合、異なる色を処理す
る８台のプロセッサが各プロセッサに割り当てられた色
に関するＲＧＢＡ四つ組を書き込むため並列に動作し得
る。かかるシステムは、マルチメディアパーソナルコン
ピュータアプリケーションの逆圧縮速度を増大する。

【００３７】好ましいハードウェア実装において、逆圧
縮装置は３２ビット幅のデータパスを備えたＭ×Ｎ形の
分配器によって実現される。図１２には、逆圧縮のため
使用されるＭ＊Ｎ形の分配器が示されている。分配器へ
の入力ライン数（Ｍ）は８にセットされ、出力ライン数
（Ｎ）は６４にセットされる。出力ラインは（図示しな
い）連続したメモリ要素に接続される。入力ライン数Ｍ
は実際の画像の色グループ数と一致すべきである。しか
し、入力ライン数Ｍを８にセットし、画像中の色グルー
プ数が８よりも大きい場合、色グループの組の全体は、
８個の色グループの細分に分割され、その細分は順番に
処理され得る。この処理レベルは並列化を使用しない。

【００３８】現在の色グループのあらゆる細分に対し、
分配器はマトリクス中の要素の値に応じてＭ本の入力か
らＮ本の入力にデータを送る。１台の分配器が色グルー
プの細分毎に使用される。マトリクスはグループフラグ
の組及び行フラグの組によって与えられた情報を用いて
形成される。入力ｉに対応するマトリクス： Ａ＝｛ａ_ij｝， １＜＝ｉ＜＝８， １＜＝ｊ＜＝６４ の第１行は以下の通り設定される。

【００３９】 Ｐ＝１ かつ Ｑ＝１ であるならば ａ_ij＝１ さもなければ ａ_ij＝０ 但し、Ｐは、ｍ＝（ｉｎｔ）（ｊ／８）であるとき、グ
ループフラグの組のビットｍの値であり、Ｑは、ｎ＝ｊ
％８であるとき、色グループｉに対応するｍに対する行
フラグの組のビットｎの値である。

【００４０】図１３は逆圧縮回路のブロック図である。
圧縮データ２００はローカルメモリ２０２に格納され
る。ローカルメモリはＭ本の入力ラインを介して圧縮デ
ータを少なくとも１台のＭ×Ｎ形分配器２０４に伝達す
る。分配器２０４の入力／出力マトリクスはデータに関
するシフト演算によって形成される。加算又は乗算演算
は必要とされず、浮動小数点数値は処理されない。Ｍ×
Ｎ形分配器２０４は全てのデータをＭ本の入力から関連
したＮ本の出力に送り、高速６４×３２形ローカルメモ
リ２０６に転送する。非圧縮データ２０８は、非圧縮画
像のコンピュータモニタへの表示のような更なる処理の
ため高速６４×３２ローカルメモリから読み出される。

【００４１】上記の通り、本発明は現在考量し得るベス
トモードに関して説明されているが、本発明に、当業者
の能力の範囲内で、かつ、別の新たな発明を行うことな
く種々の変形、動作モード及び実施例が許されることは
明らかである。従って、特許請求の範囲に記載された技
術範囲が保護されることを意図している。以下、添付リ
ストＡ及び添付リストＢは、夫々、本発明の圧縮アルゴ
リズム及び逆圧縮アルゴリズムのＣ言語による実装例で
ある。上記疑似コードのリスト及び以下の添付リスト
は、著作権の保護を受けている。

【００４２】図１４乃至１６は、画像データのブロック
を圧縮するアルゴリズムのＣ言語による実装例のリスト
である。図１７は、予め圧縮された画像データのブロッ
クを逆圧縮するアルゴリズムのＣ言語による実装例のリ
ストである。

【図面の簡単な説明】

【図１】従来技術によるカラーグラフィックス画像と、
関連した記憶表現とを示す図である。

【図２】本発明よる序数として表されたＲＧＢＡ四つ組
を用いた８×８形ブロックの例を示す図である。

【図３】序数のＲＧＢＡ四つ組へのマッピングを示す図
である。

【図４】図２のブロックの例に対するデータ構造をテキ
ストで表現した図である。

【図５】コンピュータメモリに記憶された図４のデータ
構造の例を示す図である。

【図６】本発明による圧縮されたブロックを記憶する一
般化されたデータ構造を示す図である。

【図７】本発明による画像データ圧縮方法の上位レベル
フローチャートである。

【図８】本発明による画像データ圧縮方法の上位レベル
フローチャートである。

【図９】本発明による先に圧縮された画像データの逆圧
縮方法の上位レベルフローチャートである。

【図１０】本発明による先に圧縮された画像データの逆
圧縮方法の上位レベルフローチャートである。

【図１１】本発明のソフトウェアによる実施例を示す図
である。

【図１２】逆圧縮のため使用されるＭ＊Ｎ分配器を示す
図である。

【図１３】逆圧縮回路のブロック図である。

【図１４】画像データのブロックを圧縮するアルゴリズ
ムのＣ言語による実装例のリストである。

【図１５】画像データのブロックを圧縮するアルゴリズ
ムのＣ言語による実装例のリストである。

【図１６】画像データのブロックを圧縮するアルゴリズ
ムのＣ言語による実装例のリストである。

【図１７】予め圧縮された画像データのブロックを逆圧
縮するアルゴリズムのＣ言語による実装例のリストであ
る。

Claims (15)

【特許請求の範囲】
1. 【請求項１】 各画素は赤色値、緑色値、青色値及び強
   度値によって表された色を有し、各列は上記画素を含
   み、各行に複数の上記列が含まれている複数の行からな
   るグラフィックス画像データを処理する方法において、 グラフィックス画像データの圧縮されたブロックからグ
   ラフィックス画像データの圧縮されていないブロックを
   作成する段階、並びに、 グラフィックス画像データの圧縮されていないブロック
   からグラフィックス画像データの圧縮されたブロックを
   形成する段階の中の少なくとも一方の段階を行なう段階
   からなり、 上記データは、赤色値、緑色値、青色値及び強度値を有
   する複数の別個の色組合せと、別個の色組合せ毎に上記
   圧縮されていないブロックの行での別個の色組合わせの
   有無を表すグループフラグの組と、別個の色組合せを有
   する上記圧縮されていないブロックの行毎に上記圧縮さ
   れていないブロックの列での別個の色組合せの有無を表
   す少なくとも１組の行フラグの組とにより構成されてい
   ることを特徴とする方法。
2. 【請求項２】 上記グラフィックス画像データの圧縮さ
   れたブロックを形成する段階は、 （Ａ）上記ブロックの画素に在る全ての色を識別するこ
   とにより、上記ブロック内の各画素毎に１画素の色に対
   応し、一つの色を表す１個の色序数を含む色序数の配列
   を作成する段階と、 （Ｂ）選択された一つの色に対する上記赤色値、緑色
   値、青色値及び強度値を上記圧縮されたブロックに格納
   する段階と、 （Ｃ）上記色序数の配列に従って選択された色の画素を
   有するブロック内の行を示す第１のフラグの組を作成す
   る段階と、 （Ｄ）上記第１のフラグの組を上記圧縮されたブロック
   に格納する段階と、 （Ｅ）上記選択された色の画素を有する各行を１組で表
   現する第２のフラグの組であって、上記色序数の配列に
   従って選択された色の画素を有するブロックの行内で選
   択された色の画素を有する列を示す少なくとも１組の第
   ２のフラグの組を作成する段階と、 （Ｆ）上記少なくとも１組の第２のフラグの組を上記圧
   縮されたブロックに格納する段階と、 （Ｇ）ブロックの全ての色に対し上記段階（Ｂ）乃至
   （Ｆ）を繰り返す段階とからなる請求項１記載の方法。
3. 【請求項３】 上記圧縮されたブロックのサイズを上記
   圧縮されたブロックに格納する段階を更に有する請求項
   ２記載の方法。
4. 【請求項４】 上記ブロックは、１行毎に８列を含む８
   行により構成されている請求項２記載の方法。
5. 【請求項５】 マスク値を取得する段階を更に有し、 上記色序数の配列を作成する段階において、上記マスク
   値に従って上記ブロックの画素に存在する全ての色が識
   別される請求項２記載の方法。
6. 【請求項６】 上記マスク値を上記圧縮されたブロック
   に格納する段階をっさらに有する請求項５記載の方法。
7. 【請求項７】 第１の赤色値、第１の緑色値、第１の青
   色値及び第１の強度値を有する第１の色と、第２の赤色
   値、第２の緑色値、第２の青色値及び第２の強度値を有
   する第２の色は、上記第１の赤色値の上記マスク値によ
   る除算の商が上記第２の赤色値の上記マスク値による除
   算の商と一致しない場合、上記第１の緑色値の上記マス
   ク値による除算の商が上記第２の緑色値の上記マスク値
   による除算の商と一致しない場合、上記第１の青色値の
   上記マスク値による除算の商が上記第２の青色値の上記
   マスク値による除算の商と一致しない場合、並びに、上
   記第１の強度値の上記マスク値による除算の商が上記第
   ２の強度値の上記マスク値による除算の商と一致しない
   場合に別個の色である請求項６記載の方法。
8. 【請求項８】 上記ブロックの画素に最も頻繁に出現す
   る色の赤色値、緑色値、青色値及び強度値を上記圧縮さ
   れたブロックの端に移す段階を更に有する請求項２記載
   の方法。
9. 【請求項９】 コンピュータシステムにおいて、請求項
   １記載の方法を実施する装置。
10. 【請求項１０】 上記グラフィックス画像データの圧縮
    されていないブロックを作成する段階は、 （ａ）上記圧縮されたブロックから選択された色に関す
    る上記赤色値、緑色値、青色値及び強度値を得る段階
    と、 （ｂ）上記圧縮されたブロックから選択された色に関す
    る上記グループフラグの組を得る段階と、 （ｃ）上記圧縮されたブロックの少なくとも１行での選
    択された色の有無を示す上記グループフラグの組の中で
    選択されたグループフラグに対応する行フラグの組を得
    る段階と、 （ｄ）上記圧縮されていないブロックの上記選択された
    グループフラグにより示されるような選択された色を有
    する行に関する行フラグの組によって示されるような選
    択された色を有する列によって指定された選択された場
    所に、上記赤色値、緑色値、青色値及び強度値を書き込
    む段階と、 （ｅ）上記圧縮されたブロックの少なくとも１行での選
    択された色の有無を示す上記グループフラグの組の各グ
    ループフラグに対し上記段階（ｃ）及び（ｄ）を繰り返
    す段階と、 （ｆ）上記圧縮されたブロックの全ての別個の色組合せ
    に対し上記段階（ａ）乃至（ｅ）を繰り返す段階とから
    なる。
11. 【請求項１１】 上記圧縮されたブロックから最後の色
    に関する上記赤色値、緑色値、青色値及び強度値を得る
    段階と、 上記圧縮されていないブロックの全ての画素に対し、上
    記最後の色に関する上記赤色値、緑色値、青色値及び強
    度値を上記圧縮されていないブロックに書き込む段階と
    を更に有する請求項１０記載の方法。
12. 【請求項１２】 上記圧縮されたブロックはマスク値を
    含み、 上記マスク値を上記圧縮されたブロックから得る段階
    と、 上記マスク値に従って上記赤色値、緑色値、青色値及び
    強度値を変更する段階とを更に有する請求項１０記載の
    方法。
13. 【請求項１３】 第１の赤色値、第１の緑色値、第１の
    青色値及び第１の強度値を有する第１の色と、第２の赤
    色値、第２の緑色値、第２の青色値及び第２の強度値を
    有する第２の色は、上記第１の赤色値の上記マスク値に
    よる除算の商が上記第２の赤色値の上記マスク値による
    除算の商と一致しない場合、上記第１の緑色値の上記マ
    スク値による除算の商が上記第２の緑色値の上記マスク
    値による除算の商と一致しない場合、上記第１の青色値
    の上記マスク値による除算の商が上記第２の青色値の上
    記マスク値による除算の商と一致しない場合、並びに、
    上記第１の強度値の上記マスク値による除算の商が上記
    第２の強度値の上記マスク値による除算の商と一致しな
    い場合に別個の色である請求項１２記載の方法。
14. 【請求項１４】 各画素は赤色値、緑色値、青色値及び
    強度値によって表された色を有し、各列は上記画素を含
    み、各行に複数の上記列が含まれている複数の行からな
    るグラフィックス画像データの圧縮されていないブロッ
    クに基づいて、グラフィックス画像データの圧縮された
    ブロックを表現するデータを格納するメモリにおいて、 赤色値、緑色値、青色値及び強度値を有する複数の別個
    の色組合せと、別個の色組合せ毎に上記圧縮されていな
    いブロックの行での別個の色組合わせの有無を表すグル
    ープフラグの組と、別個の色組合せを有する上記圧縮さ
    れていないブロックの行毎に上記圧縮されていないブロ
    ックの列での別個の色組合せの有無を表す少なくとも１
    組の行フラグの組とにより構成されているデータ構造が
    格納されていることを特徴とするメモリ。
15. 【請求項１５】 上記データ構造は上記圧縮されたブロ
    ックに関するマスク値を更に有し、 第１の赤色値、第１の緑色値、第１の青色値及び第１の
    強度値を有する第１の色と、第２の赤色値、第２の緑色
    値、第２の青色値及び第２の強度値を有する第２の色
    は、上記第１の赤色値の上記マスク値による除算の商が
    上記第２の赤色値の上記マスク値による除算の商と一致
    しない場合、上記第１の緑色値の上記マスク値による除
    算の商が上記第２の緑色値の上記マスク値による除算の
    商と一致しない場合、上記第１の青色値の上記マスク値
    による除算の商が上記第２の青色値の上記マスク値によ
    る除算の商と一致しない場合、並びに、上記第１の強度
    値の上記マスク値による除算の商が上記第２の強度値の
    上記マスク値による除算の商と一致しない場合に別個の
    色である請求項１４記載のメモリ。