(57)【特許請求の範囲】
【請求項１】
任意サイズの画像データを矩形領域の複数の画像データに分割し、各矩形領域に分割された画像データに位置番号を付与し、各画像データのカラーコードを隣接する前記分割された矩形領域同士でそれぞれ比較し、比較先の第１の画像データのカラーコードと比較元の第２の画像データのカラーコードが一致したときには、前記第１の画像データに付与された位置番号で前記第２の画像データのカラーコードを置換し、
前記第２の画像データが、カラーコードが一致する比較対象の画像データが存在しない画像データである場合には、さらに前記第２の画像データを矩形領域の第３の画像データ及び第４の画像データを含む複数の画像データに分割し、
各矩形領域に分割された前記第３の画像データ及び第４の画像データを含む複数の画像データに位置番号を付与し、
前記第３の画像データ及び第４の画像データを含む複数の画像データのカラーコードを隣接する前記分割された矩形領域同士でそれぞれ比較する処理を繰り返し、
比較先の前記第３の画像データのカラーコードと比較元の前記第４の画像データのカラーコードが一致したときには、前記第３の画像データに付与された位置番号で前記第４の画像データのカラーコードを置換することを特徴とする画像データの圧縮方法。
【請求項２】
任意サイズの画像データを矩形領域の複数の画像データに分割し、
各矩形領域に分割された画像データに位置番号を付与し、
各画像データのカラーコードを隣接する前記分割された矩形領域同士でそれぞれ比較し、比較先の第１の画像データのカラーコードと比較元の第２の画像データのカラーコードが一致したときには、前記第１の画像データに付与された位置番号で前記第２の画像データのカラーコードを置換し、
前記第２の画像データが、カラーコードが一致する比較対象の画像データが存在しない画像データである場合には、さらに前記第２の画像データを矩形領域の第３の画像データ及び第４の画像データを含む複数の画像データに分割し、
各矩形領域に分割された前記第３の画像データ及び第４の画像データを含む複数の画像データに位置番号を付与し、
前記第３の画像データ及び第４の画像データを含む複数の画像データのカラーコードを隣接する前記分割された矩形領域同士でそれぞれ比較する処理を繰り返し、
比較先の前記第３の画像データのカラーコードと比較元の前記第４の画像データのカラーコードが一致したときには、前記第３の画像データに付与された位置番号で前記第４の画像データのカラーコードを置換することによって生成される圧縮画像データの伸長方法であって、 
前記比較先の画像データに付与された位置番号を参照先アドレスデータとして使用することを特徴とする画像データの伸長方法。
【請求項３】
画像データを圧縮する画像データの圧縮装置であって、
任意サイズの画像データを矩形領域の複数の画像データに分割する画像データ分割手段と、
各矩形領域に分割された画像データに位置番号を付与し、各画像データのカラーコードを隣接する前記分割された矩形領域同士でそれぞれ比較する画像データ比較手段と、
前記比較の結果、比較先の第１の画像データのカラーコードと比較元の第２の画像データのカラーコードが一致したときには、前記第１の画像データに付与された位置番号で前記第２の画像データのカラーコードを置換し、前記第２の画像データが、カラーコードが一致する比較対象の画像データが存在しない画像データである場合には、さらに前記画像データ分割手段により、前記第２の画像データを矩形領域の第３の画像データ及び第４の画像データを含む複数の画像データに分割させ、各矩形領域に分割された前記第３の画像データ及び第４の画像データを含む複数の画像データに位置番号を付与し、前記第３の画像データ及び第４の画像データを含む複数の画像データのカラーコードを隣接する前記分割された矩形領域同士でそれぞれ比較する処理を繰り返し、比較先の前記第３の画像データのカラーコードと比較元の前記第４の画像データのカラーコードが一致したときには、前記第３の画像データに付与された位置番号で前記第４の画像データのカラーコードを置換する画像データ圧縮手段とを備えたことを特徴とする画像データの圧縮装置。
【請求項４】
任意サイズの画像データを矩形領域の複数の画像データに分割し、各矩形領域に分割された画像データに位置番号を付与し、各画像データのカラーコードを隣接する前記分割された矩形領域同士でそれぞれ比較し、比較先の第１の画像データのカラーコードと比較元の第２の画像データのカラーコードが一致したときには、前記第１の画像データに付与された位置番号で前記第２の画像データのカラーコードを置換し、前記第２の画像データが、カラーコードが一致する比較対象の画像データが存在しない画像データである場合には、さらに前記第２の画像データを矩形領域の第３の画像データ及び第４の画像データを含む複数の画像データに分割し、各矩形領域に分割された前記第３の画像データ及び第４の画像データを含む複数の画像データに位置番号を付与し、前記第３の画像データ及び第４の画像データを含む複数の画像データのカラーコードを隣接する前記分割された矩形領域同士でそれぞれ比較する処理を繰り返し、比較先の前記第３の画像データのカラーコードと比較元の前記第４の画像データのカラーコードが一致したときには、前記第３の画像データに付与された位置番号で前記第４の画像データのカラーコードを置換することによって生成される圧縮画像データの伸長装置であって、 
前記比較先の画像データに付与された位置番号を参照先アドレスデータとして使用する画像データ伸長手段を備えたことを特徴とする画像データの伸長装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、特に、コンピュータゲーム等で用いられる比較的色数が少ないアニメーション画像の圧縮、伸長に用いて好適な、画像データの圧縮ならびに伸長方法およびその装置に関する。
【０００２】
【従来の技術】
画像データ量は膨大であるため、その描画、通信にかかるコストを低減する目的で、画像データの圧縮、伸長処理が行われる。画像の圧縮方法としては、従来から、ハフマン符号化法、ランレングス法が知られている。
【０００３】
前者は、データの出現確率により符号長を変更することで、出現頻度の高いデータの圧縮率を高めることにより、トータルとしての圧縮率を高める方法であるが、出現確率が一定しない画像データの場合には、符号の変換テーブルを圧縮、伸長時にパラメータとして持つ必要がある。また、後者は、２値データの圧縮については最適であるが、色数等画像データの種類が増えるにつれて効果が薄れるといった特性を有する。
【０００４】
【発明が解決しようとする課題】
ところで、上述したコンピュータゲームやコンピュータグラフィックの分野では、あらかじめ所定サイズ長の矩形パターンをあらかじめ作成して部品化しておき、これら部品を適当に組み合わせることによって、例えば、背景画を作るといったテクニックが頻繁に用いられるようになった。
これら部品を、上述したハフマン符号化法やランレングス法のように、従来からある古典的な方法で、圧縮、伸長しようとしても、上述したように期待するほどの圧縮率が得られないといった不都合があった。
【０００５】
本発明は上記事情に鑑みてなされたものであり、ある領域の画像を、それを構成する複数の領域の画像に分割してそれぞれに固有の番号を付与し、分割された画像同士で比較を行なうことにより、同じ画像が使用されている場合にはその画像データを比較先の画像データに付与された固有の番号に置換し、同じ画像が使用されていない場合には更に分割された領域の画像に対しても同様の操作を行なうことにより高い圧縮率を得ることのできる画像データの圧縮方法およびその装置を提供することを目的とする。
また、比較先の画像データに付与された固有の番号を参照先アドレスデータとして使用することにより、分割前の画像データと一致したために描画が省略された画像データを再現することのできる、画像データの伸長方法およびその装置を提供することも目的とする。
【０００６】
【課題を解決するための手段】
上述した課題を解決するために請求項１に記載の発明は、任意サイズの画像データを矩形領域の複数の画像データに分割し、各矩形領域に分割された画像データに位置番号を付与し、各画像データのカラーコードを隣接する前記分割された矩形領域同士でそれぞれ比較し、比較先の第１の画像データのカラーコードと比較元の第２の画像データのカラーコードが一致したときには、前記第１の画像データに付与された位置番号で前記第２の画像データのカラーコードを置換し、前記第２の画像データが、カラーコードが一致する比較対象の画像データが存在しない画像データである場合には、さらに前記第２の画像データを矩形領域の第３の画像データ及び第４の画像データを含む複数の画像データに分割し、各矩形領域に分割された前記第３の画像データ及び第４の画像データを含む複数の画像データに位置番号を付与し、前記第３の画像データ及び第４の画像データを含む複数の画像データのカラーコードを隣接する前記分割された矩形領域同士でそれぞれ比較する処理を繰り返し、比較先の前記第３の画像データのカラーコードと比較元の前記第４の画像データのカラーコードが一致したときには、前記第３の画像データに付与された位置番号で前記第４の画像データのカラーコードを置換することとした。
このことにより、ある領域の画像を、それを構成する複数の領域の画像に分割し、それぞれに位置番号を付与し、分割した画像同士で比較し、同じ画像が使用されている場合にはその画像データを比較先の画像データに付与された位置番号に置換し、更に分割された領域の画像に対しても同様にそれを構成する複数の領域に分割し一致する画像を位置番号に置換する圧縮を分割された階層毎に行なうことで高い圧縮率を得ることができる。
【０００８】
請求項２に記載の発明は、任意サイズの画像データを矩形領域の複数の画像データに分割し、各矩形領域に分割された画像データに位置番号を付与し、各画像データのカラーコードを隣接する前記分割された矩形領域同士でそれぞれ比較し、比較先の第１の画像データのカラーコードと比較元の第２の画像データのカラーコードが一致したときには、前記第１の画像データに付与された位置番号で前記第２の画像データのカラーコードを置換し、前記第２の画像データが、カラーコードが一致する比較対象の画像データが存在しない画像データである場合には、さらに前記第２の画像データを矩形領域の第３の画像データ及び第４の画像データを含む複数の画像データに分割し、各矩形領域に分割された前記第３の画像データ及び第４の画像データを含む複数の画像データに位置番号を付与し、前記第３の画像データ及び第４の画像データを含む複数の画像データのカラーコードを隣接する前記分割された矩形領域同士でそれぞれ比較する処理を繰り返し、比較先の前記第３の画像データのカラーコードと比較元の前記第４の画像データのカラーコードが一致したときには、前記第３の画像データに付与された位置番号で前記第４の画像データのカラーコードを置換することによって生成される圧縮画像データの伸長方法であって、 前記比較先の画像データに付与された位置番号を参照先アドレスデータとして使用することとした。
このことにより、比較先の画像データに付与された位置番号を参照先アドレスデータとして使用することにより、分割前の画像データと一致したために省略された画像データを再現することができる。
【０００９】
請求項３に記載の発明は、画像データを圧縮する画像データの圧縮装置であって、任意サイズの画像データを矩形領域の複数の画像データに分割する画像データ分割手段と、各矩形領域に分割された画像データに位置番号を付与し、各画像データのカラーコードを隣接する前記分割された矩形領域同士でそれぞれ比較する画像データ比較手段と、前記比較の結果、比較先の第１の画像データのカラーコードと比較元の第２の画像データのカラーコードが一致したときには、前記第１の画像データに付与された位置番号で前記第２の画像データのカラーコードを置換し、前記第２の画像データが、カラーコードが一致する比較対象の画像データが存在しない画像データである場合には、さらに前記画像データ分割手段により、前記第２の画像データを矩形領域の第３の画像データ及び第４の画像データを含む複数の画像データに分割させ、各矩形領域に分割された前記第３の画像データ及び第４の画像データを含む複数の画像データに位置番号を付与し、前記第３の画像データ及び第４の画像データを含む複数の画像データのカラーコードを隣接する前記分割された矩形領域同士でそれぞれ比較する処理を繰り返し、比較先の前記第３の画像データのカラーコードと比較元の前記第４の画像データのカラーコードが一致したときには、前記第３の画像データに付与された位置番号で前記第４の画像データのカラーコードを置換する画像データ圧縮手段とを備えたこととした。
上記構成により、ある画像を、それを構成する複数の画像に分割し、分割された画像同士で比較操作を行ない、同じ画像が使用されている場合にはその画像データを比較先の画像データから取得することで高い圧縮率が得られる画像データの圧縮装置を提供することができる。
【００１０】
請求項４に記載の発明は、任意サイズの画像データを矩形領域の複数の画像データに分割し、各矩形領域に分割された画像データに位置番号を付与し、各画像データのカラーコードを隣接する前記分割された矩形領域同士でそれぞれ比較し、比較先の第１の画像データのカラーコードと比較元の第２の画像データのカラーコードが一致したときには、前記第１の画像データに付与された位置番号で前記第２の画像データのカラーコードを置換し、前記第２の画像データが、カラーコードが一致する比較対象の画像データが存在しない画像データである場合には、さらに前記第２の画像データを矩形領域の第３の画像データ及び第４の画像データを含む複数の画像データに分割し、各矩形領域に分割された前記第３の画像データ及び第４の画像データを含む複数の画像データに位置番号を付与し、前記第３の画像データ及び第４の画像データを含む複数の画像データのカラーコードを隣接する前記分割された矩形領域同士でそれぞれ比較する処理を繰り返し、比較先の前記第３の画像データのカラーコードと比較元の前記第４の画像データのカラーコードが一致したときには、前記第３の画像データに付与された位置番号で前記第４の画像データのカラーコードを置換することによって生成される圧縮画像データの伸長装置であって、 
前記比較先の画像データに付与された位置番号を参照先アドレスデータとして使用する画像データ伸長手段を備えたこととした。
上記構成により、比較先の画像データに付与された位置番号を参照先アドレスデータとして使用することにより、分割前の画像データと一致したために省略された画像データを再現可能な画像データの伸長装置を提供することができる。
【００１５】
【発明の実施の形態】
図１は、本発明における画像圧縮伸長装置の一実施形態を示すブロック図である。本発明の画像圧縮伸長装置１０は、画像データ入出力部１１と、画像データ分割部１２と、画像データ比較部１３と、画像データ圧縮部１４と、画像データ伸長部１５で構成される。
【００１６】
画像データ入出力部１１は、外部装置とのインタフェースとなる部分であり、外部装置が通信装置であったり、記憶装置を含む処理装置であったりする。
画像データ分割部１２は、画像データ入出力部１１を介して到来する画像データを任意画像データに分割するものであり、ここでは矩形領域に分割するものとする。画像データ比較部１３は、画像データ分割部１２によって分割された矩形領域同士の画像パターンを比較し、その結果を画像データ圧縮部１４へ伝え、画像データ圧縮部１４による画像圧縮処理をコントロールする。
【００１７】
画像データ圧縮部１４は、画像データ分割部１２によってあらかじめ分割された画像データのそれぞれに固有の番号が付与されており、画像データ比較部１３で分割されたパターン同士を比較した結果、一致した画像データを、比較先の画像データに付与された固有の番号に置換する。このことにより、一致した画像データの描画が省略され圧縮処理がなされたことになる。画像データ伸長部１５は、画像データ入出力部１１を介して圧縮画像データを得、比較先の画像データに付与された固有の番号を参照先アドレスデータとして参照することにより、分割前の画像データと一致したために記憶データが省略された画像データを取得することによって伸長処理を行う。
【００１８】
図２、図３は、本発明による画像データの圧縮方法を説明するために引用した図である。以下、図２、図３を参照しながら図１に示す画像圧縮伸長装置の動作について詳細に説明する。
ここでは、画像データを構成する矩形領域（正方形）の分割を縦横２分割（計４分割）で行なう場合の圧縮方法を例示して説明する。従って、一辺が２nの正方形に対し縦横２分割してできた４つの一辺が２(n-1)の正方形にそれぞれ２ビットの位置番号（“００”，“０１”，“１０”，“１１”）を付与する。そして、４つの２(n-1)の正方形を“００”の画素パターンから“１１”の画素パターンまで比較し、同じパターンの正方形があればその位置番号を付与し、同じパンターンがなければ、自身の位置番号を付与したうえで２(n-1)の正方形を２(n-1)の集まりとしてこのルールに従って圧縮処理を行う。
【００１９】
具体的に、４ビットのカラーコード（画像データＣＣ）を０〜Ｆで表現すると、図２（ａ）に示すようになる。図２（ａ）において、まず、画像データ分割部１２は、４×４の絵柄を縦横２分割して４つの２×２の絵柄に分割し、それぞれに位置番号ＰＮ２［１：０］を付与する。このことにより、図２（ｂ）に示すように、左上絵柄に“００”、右上絵柄に“０１”、左下絵柄に“１０”、右下絵柄に“１１”が付与される。
そして、画像データ比較部１３でそれぞれの絵柄を比較し、その結果、画像データ圧縮部１４は、一致する場合参照先の位置番号を付与し、一致するもののない絵柄は、自身の位置番号を付与する。ここでは、位置番号“０１”と“１０”の絵柄が一致するため、“１０”の位置番号を“０１”に置換し、“１０”の画像データは省略される。このときの位置番号ＰＮ２［１：０］のデータ構造は図２（ｃ）に示すようになる。
【００２０】
次に、一致する絵柄が無い画像を、更に１×１の絵柄に４分割して位置番号（ＰＮ１［１：０］）を付与する。このことにより、図３（ａ）に示すように、左上絵柄に“００”、右上絵柄に“０１”、左下絵柄に“１０”、右下絵柄に“１１”が付与される。そして、１×１の４つの絵柄で一致する場合参照先の位置番号で置換し、一致するもののない絵柄は、自身の位置番号を付与する。この場合は、全て０ｈで同じであるので、位置番号ＰＮ１［１：０］のデータ構造は図３（ｂ）に示すようになる。
【００２１】
以下、同様に、２×２絵柄で一致しなかった画像について１×１絵柄で比較し、符号化すると、圧縮後のデータ構造は、図３（ｃ）に示すようになる。このことにより、４８ビットの２進データ“００００ ００ ００ ００ ０１ ００００ ０１ ０００１ ０１ １１ １１１１ ０１ １１ １１１１ ００ ００ １１ １０１１”が得られ、圧縮率は、圧縮前６４ビット（４ビット×１６区画）、圧縮後４８ビットの７５％になる。
【００２２】
なお、カラーコードが全て同じ場合、４×４画素の絵柄を圧縮すると１６ビット（２５％）に、８×８画素の絵柄を圧縮すると２２ビット（９％）に圧縮できる。本発明は、単純には、正方形の近傍４点で比較して一致する画像データ、ここではカラーコードは位置番号のみとし、その画像データの描画を省略する手順を階層的に行ない圧縮することを特徴とするものである。
【００２３】
次に上記のようにして圧縮した画像データを復元する際の伸長方法につき、以下に説明する。本発明による伸長のアルゴリズムをソースコード表現した場合、以下のようになる。
0003911986.tif 000002
【００２４】
上記したソースコード表現を基に、図４に示すフローチャートを参照しながら本発明の伸長の手順について説明する。
まず、変数Ｓ、位置番号Ｐｎ［０］、Ｐｎ［１］、Ｐｎ［２］のそれぞれに初期値“０”をセットする（ステップＳ４１）。そして、左上絵柄４ビットのカラーコードＣＣを取得し、描画する（ステップＳ４２）。次に、２ビットの参照コードを取得し（ステップＳ４３）、位置番号Ｐｎ［Ｓ］をＰｎ＋１に更新した後（ステップＳ４４）、Ｐｎ［Ｓ］と先に取得した参照コードとの比較演算が行なわれる（ステップＳ４５）。
比較演算の結果、等しいか大きくなった場合に、更に変数Ｓが“０”であることを確認（ステップＳ４６）してその４ビットのカラーコードを取得し、描画する（ステップＳ４７）。変数Ｓが“０”でない場合は、変数Ｓを−１更新すると共に、位置番号Ｐｎ［Ｓ］に“０”をセットし（ステップＳ５１）、変数Ｓが“０”であることを確認したうえでその４ビットのカラーコードを取得し、描画する（ステップＳ４７）。
【００２５】
一方、ステップ４５における比較演算の結果、位置番号Ｐｎ［Ｓ］が参照コードより小さかった場合、その位置番号Ｐｎ［Ｓ］相当位置に、その参照コードが示す位置のデータをコピーし（ステップＳ５３）、位置番号Ｐｎ［Ｓ］を＋１更新（ステップＳ５４）してステップＳ４８の処理にジャンプする。すなわち、ここでは、比較先の画像データに付与された固有の番号を参照先アドレスデータとして使用することにより、分割前の画像データと一致したために描画が省略された画像データを再現する処理を行っている。
【００２６】
ステップＳ４８では、位置番号Ｐｎ［Ｓ］が“１１”より大きくないことをチェックし、上述したステップＳ４２以降の処理を繰り返す。位置番号Ｐｎ［Ｓ］が“１１”より大きくなった場合は、変数Ｓを＋１更新し（ステップＳ４９）、更に、変数Ｓが２以下であることをチェック（ステップＳ５０）して２ビットの参照コードを取得し（ステップＳ５６）、位置番号Ｐｎ［Ｓ］を＋１更新して（ステップＳ５５）、上述したステップＳ４２以降の処理を繰り返す。変数Ｓが“２”を越えたときに上述した伸長処理が終了となる。
【００２７】
以上説明した、圧縮、伸長処理では、ある矩形領域の画像を、それを構成する複数の矩形領域の画像に分割し、その分割された隣接する矩形領域毎の画像データ同士を比較したが、比較対象を、例えば、左上の画素に固定し、そのカラーコードと一致すれば“０”、異なっていれば“１”を付加してそのカラーコードを描画することも可能である。この場合、一致、不一致を示す符号が１ビットで済むため、複雑な画像でもデータの増加が抑えられるといった利点がある。
この方法を用いた場合の位置番号ＰＮ１［１：０］のデータ構造を図５に示す。この場合、図から明らかなように、５９ビットの２進データ“００００ ０ ００ １ ００００ １ ０００１ １ ０００１ １ １１１１ １ ００００ １ ０００１ １ ０００１ １ １１１１ １ １１１１ ０ ０ １ １０１１”が得られる。
【００２８】
以上説明のように本発明は、ある領域の画像を、それを構成する複数の領域の画像に分割してそれぞれに固有の番号を付与し、分割された画像同士で比較を行なうことにより、同じ画像が使用されている場合にはその画像データを比較先の画像データに付与された固有の番号に置換し、同じ画像が使用されていない場合には更に分割された領域の画像に対しても同様の操作を行なうことにより高い圧縮率を得ることができ、また、比較先の画像データに付与された固有の番号を参照先アドレスデータとして使用することにより、分割前の画像データと一致したためにデータが省略された画像データを容易に再現することができる。
なお、本発明は、コンピュータゲーム等で背景画として用いられる比較的色数の少ないアプリケーションに使用して顕著な効果が得られる。
【００２９】
【発明の効果】
以上説明のように、請求項１に記載の発明によれば、ある領域の画像を、それを構成する複数の領域の画像に分割し、それぞれに位置番号を付与し、分割した画像同士で比較し、同じ画像が使用されている場合にはその画像データを比較先の画像データに付与された位置番号に置換し、更に分割された領域の画像に対しても同様にそれを構成する複数の領域に分割し一致する画像を位置番号に置換する圧縮を分割された階層毎に行なうことで高い圧縮率を得ることができる。
【００３１】
請求項２に記載の発明によれば、比較先の画像データに付与された位置番号を参照先アドレスデータとして使用することにより、分割前の画像データと一致したために省略された画像データを再現することができる。
【００３２】
請求項３に記載の発明によれば、ある画像を、それを構成する複数の画像に分割し、分割された画像同士で比較操作を行ない、同じ画像が使用されている場合にはその画像データを比較先の画像データから取得することで高い圧縮率が得られる画像データの圧縮装置を提供することができる。
【００３３】
請求項４に記載の発明によれば、比較先の画像データに付与された位置番号を参照先アドレスデータとして使用することにより、分割前の画像データと一致したために省略された画像データを再現可能な画像データの伸長装置を提供することができる。
【図面の簡単な説明】
【図１】  本発明における画像圧縮伸長装置の一実施形態を示すブロック図である。
【図２】  本発明における画像データの圧縮方法の一実施形態を説明するために引用した図である。
【図３】  本発明における画像データの圧縮方法の一実施形態を説明するために引用した図である。
【図４】  本発明における画像データの伸長方法を説明するために引用したフローチャートである。
【図５】  本発明における画像データの圧縮方法の他の実施形態を説明するために引用した図である。
【符号の説明】
１０  画像データ圧縮伸長装置
１１  画像データ入出力部
１２  画像データ分割部
１３  画像データ比較部
１４  画像データ圧縮部
１５  画像データ伸長部
【図１】
0003911986.tif 000003
【図２】
0003911986.tif 000004
【図３】
0003911986.tif 000005
【図４】
0003911986.tif 000006
【図５】
0003911986.tif 000007