(57)【特許請求の範囲】
【請求項１】
ビットマップ形式の画像データを圧縮する装置であって、
前記画像データを構成する画素データの種類毎に表示領域の全画素数と該表示領域の境界線として表される画素数を計数し、該計数結果から境界線として表される割合が高い順に前記画素データの種類を整列し、この整列させた順序に従って、前記画素データの種類毎に境界線部分を検出する境界線検出手段と、
前記境界線検出手段が境界線部分を検出した結果から、前記画像データを境界線部分と表示領域部分とに分けて符号化する符号化手段と、
を具備したことを特徴とする画像データ圧縮装置。
【請求項２】
前記境界線検出手段は、前記画像データの１画素データを注目画素データとしてビットマップ上を順次移動させながら、該注目画素データとそれに隣接する上下、及び左右の少なくとも一方の各画素データとを対比し、前記上下、及び左右の少なくとも一方の各画素データと前記注目画素データが異なると対比した少なくとも一方の場合に、該注目画素データを、前記表示領域の境界線として表される画素として計数する、ことを特徴とする請求項１記載の画像データ圧縮装置。
【発明の詳細な説明】
【０００１】
【産業上の利用分野】
本発明は、ビットマップ形式の画像データを圧縮する技術に関する。
【０００２】
【従来の技術および発明が解決しようとする課題】
例えば、ユーザが所望する画像を画面上に任意に描くことができる画像描画装置においては、通常、ユーザが描いた画像のデータはビットマップ形式で扱われる。ビットマップ形式は、画像上の１ドットと、メモリ上に記憶されているその１ドットの状態を示すデータ（画素データ）とを一意対応させたものである。このビットマップ形式において、画像を表現する画像データは、画像上の各点（ドット）の状態を示す画素データの集合体として構成される。
【０００３】
画像の大きさ、表示可能な色の数等にもよるが、普通、１画像の画像データは膨大である。このため、上記の画像描画装置には画像データ圧縮装置が搭載されることが多く、ユーザが作成した画像を保存する場合、その画像データは画像データ圧縮装置により圧縮された後、磁気ディスク装置等の外部記憶装置に格納される。
【０００４】
ビットマップ形式の画像データの場合、その圧縮にはランレングス符号化といった圧縮方式が用いられていた。現在では、多機能化、ユーザに対してより易しい対話型の操作環境の実現といった強い要請があり、これらの実現には膨大なデータを格納できる領域が必要である。このことから、装置のコストを抑えながらこれらを実現するためにも、より高い画像データの圧縮が行えることが望まれていた。
【０００５】
本発明の課題は、ビットマップ形式の画像データの高い圧縮率を実現することにある。
【０００６】
【課題を解決するための手段】
本発明の画像データ圧縮装置は、ビットマップ形式の画像データを圧縮することを前提とし、画像データを構成する画素データの種類毎に表示領域の全画素数と該表示領域の境界線として表される画素数を計数し、該計数結果から境界線として表される割合が高い順に画素データの種類を整列し、この整列させた順序に従って、画素データの種類毎に境界線部分を検出する境界線検出手段と、境界線検出手段が境界線部分を検出した結果から、画像データを境界線部分と表示領域部分とに分けて符号化する符号化手段と、を具備する。
【０００７】
上記構成において、境界線検出手段は、画像データの１画素データを注目画素データとしてビットマップ上を順次移動させながら、該注目画素データとそれに隣接する上下、及び左右の少なくとも一方の各画素データとを対比し、これら上下、及び左右の少なくとも一方の各画素データと注目画素データが異なると対比した少なくとも一方の場合に、該注目画素データを、表示領域の境界線として表される画素として計数する、ことが望ましい。
【０００９】
【作用】
本発明の画像データ圧縮装置は、画像データを構成する画素データの種類毎に表示領域の全画素数と該表示領域の境界線として表される画素数を計数し、該計数結果から境界線として表される割合が高い順に画素データの種類を整列し、この整列させた順序に従って、画素データの種類毎に境界線部分を検出した後、該境界線部分を検出した結果から、画像データを境界線部分と表示領域部分とに分けて各々符号化する。
【００１０】
境界線で囲まれた表示領域は、その境界線を含め、例えばシードフィル方式によってそれを塗りつぶすことができる。このシードフィル方式では、１表示領域の塗りつぶしに必要なデータはその内部の任意の座標と塗りつぶす色である。このため、表示領域毎のデータ量は大幅に低減される。
【００１１】
また、本発明では、例えば画素データの種類毎に表示領域の全画素数と該表示領域の境界線として表される画素数を計数することで、境界線が占める割合が大きい表示領域の画素データを優先させて境界線の検出を行う。
【００１２】
境界線は、隣接する表示領域を分けるためであり、必ず各表示領域毎に境界線を検出しなければならないものではない。境界線が占める割合が高い表示領域（画素データ）の境界線の検出を優先することで、例えばある大きな表示領域のなかに小さな別の表示領域が存在している場合には、小さいほうの表示領域の境界線が検出される。このため、最終的に検出した境界線の長さは短くなり、また、境界線を検出する表示領域を減らすことが可能となる。
【００１４】
【実施例】
以下、本発明の実施例について、図面を参照しながら詳細に説明する。
図１は、本実施例による画像データ圧縮装置が適用された画像描画装置１００のシステム構成を示すブロック図である。
【００１５】
図１に示す如く、この画像描画装置１００は、特には図示しない各種スイッチやポインティングデバイス等を備えた入力装置１０１と、各種制御用プログラムや画像表示用のデータ等を記憶したＲＯＭ（Read Only Memory）１０２と、このＲＯＭ１０２に記憶されたプログラムに従って、装置１００全体の制御を実行するＣＰＵ（Central Processing Unit ）１０３と、このＣＰＵ１０３がワーク領域として用いるＲＡＭ（Random Access Memory）１０４と、ＣＰＵ１０３からの指示に従い、Ｖ（ビデオ）ＲＡＭ１０６上にビットマップ形式で画像データを書き込むＶＤＰ（ビデオディスプレイプロセッサ）１０５と、ＶＲＡＭ１０５に書き込まれた画像データに従って画像をその画面上に表示する表示装置１０７とから構成されている。
【００１６】
上記の構成において、その概略動作を説明する。
ＣＰＵ１０３は、ＲＯＭ１０２から読み出した表示用データをＶＤＰ１０５に出力することで表示装置１０７に各種ボタンやツールを表示させる。その一方、例えばクリック操作で指定したツールに割り当てられた機能（コマンド）に従い、入力装置１０１を介して入力したポインティングデバイスの操作情報に応じて表示装置１０７の画面上に選択されている描画色が表示されるように、ＶＤＰ１０５に対して描画色のカラーコード、その表示座標データ等を出力する。このようにして、ユーザに対してＧＵＩ環境が提供され、ユーザは画面を見ながら所望の画像を描画（作成）することができる。
【００１７】
ユーザが作成した画像は、特には図示しない外部記憶装置に保存することができるようになっている。ＣＰＵ１０３は、入力装置１０１を介して表示装置１０７に表示されている画像の保存が指示された場合、先ず、ＶＲＡＭ１０６にビットマップ形式で格納されているその画像の画像データを、ＶＤＰ１０５を介して入力し、これをＲＡＭ１０４に格納する。その後、詳細は後述するように、画像データを境界線と境界線で囲まれた表示領域とに分けて各々符号化する圧縮処理を実行し、圧縮処理を施した画像データを外部記憶装置に格納する。
【００１８】
以上がその概略動作である。
次に、図２〜図９を参照しながら、ＣＰＵ１０３が実行する上記圧縮処理について詳細に説明する。図２は、この圧縮処理の動作フローチャートである。この図２は、その一連の処理の概要であり、各ステップの処理の詳細については後述する。上記したように、圧縮処理は、ＶＲＡＭ１０６に格納されているビットマップ形式の画像データをＲＡＭ１０４に記憶させ、このＲＡＭ１０４をワーク領域として実行する。
【００１９】
先ず、ステップ２０１では、表示装置１０７に表示可能な描画色（カラーコード）毎に、そのカラーコードで表現される表示領域の全画素数とその領域を境界線として表す画素数とをカウントし、該カウントしたこれらの値から表示領域に占める境界線の割合が高い順にカラーコードを配列する境界線検索色順序配列処理を実行する。これに続くステップ２０２では、ステップ２０１で決定したカラーコードの順序で境界線を作成する処理を実行する。このステップ２０２の処理により、画像データは表示領域と境界線とに分けられる。
【００２０】
ステップ２０２に続くステップ２０３では、上記ステップ２０２で２つに分けられた一方である表示領域の塗り潰す色（カラーコード）を取り出す処理を実行する。この処理が終了すると、ステップ２０４において、２つに分類した残りの一方である境界線を取り出して符号化する処理を実行した後、一連の処理を終了する。
【００２１】
上記ステップ２０３で取り出されたカラーコード、ステップ２０４で符号化された境界線等が外部記憶装置に送られ、そこに格納される。これにより、表示装置１０７に表示されていた画像の格納が完了する。
【００２２】
次に、上記ステップ２０１の境界線検索色順序整列処理の詳細について、図３に示すその動作フローチャートを参照して説明する。上記したように、この境界線検索色順序整列処理は、描画色（カラーコード）毎に、それによって表示される表示領域における境界線の割合が高い順序に、描画色（カラーコード）を整列する処理である。
【００２３】
本実施例では、画像の縦横のラインを各々処理単位とし、各描画色に割り当てられているカラーコードの値の昇順に、ライン上の注目画素を変更（画素データが格納されているアドレスを変更）しながら、注目画素とそれに隣接する２つ（注目画素が画像の端であった場合は異なる）の画素の表示状態、即ちカラーコード（データ）の値が同一であるか否か判定し、該判定結果に従って、境界線として表すことが特に望ましいと考えられる（これについては、後述する）画素数をカウントする。
【００２４】
先ず、検索する描画色（カラーコード）を設定した後、ステップ３０１において、変数ｔｏｔａｌ、ｄｏｔに各々０を代入する。変数ｔｏｔａｌは、現在設定しているカラーコードの画素数をカウントするための変数であり、他方の変数ｄｏｔは、そのカラーコード（描画色）の画素（表示領域）において境界線として表現（実際には格納）することが望ましい画素数をカウントするための変数である。これらはＲＡＭ１０４の所定の領域に格納される。また、現在設定されている検索する描画色（カラーコード）については、以降、検索色と記す。
【００２５】
ステップ３０１に続くステップ３０２〜３０９では、画像の横のラインを左から右に注目画素を移動させ、その横のラインを上から下に順次変更させながら、注目画素とこれの横方向に隣接する画素の色（カラーコード）の違いに着目して、境界線として表現することが特に望ましいと考えられる画素を特定し、その数をカウントする。
【００２６】
先ず、ステップ３０２では、注目画素は検索色と違う色か否か判定する。注目画素は検索色と違う色であった場合、その判定はＹＥＳとなってステップ３０６の処理に移行する。反対に注目画素が検索色であった場合、その判定はＮＯとなってステップ３０３の処理に移行する。
【００２７】
ステップ３０３では、変数ｔｏｔａｌの値をインクリメントする。このインクリメントが終了すると、次にステップ３０４において、注目画素がその両横隣の画素と違う色（カラーコード：データ）であるか否か判定する。注目画素とその両横隣の何方か一方の画素とが異なる色であった場合、その判定はＮＯとなってステップ３０６の処理に移行する。それ以外の場合、即ち注目画素とその両横隣の画素とが異なる色であった場合、その判定はＹＥＳとなり、ステップ３０５で変数ｄｏｔの値をインクリメントした後、ステップ３０６の処理に移行する。両横隣の画素と違う色の注目画素が、境界線として表現（格納）することが特に有効であると考えられる画素（以降、これを有効画素と記す）である。
【００２８】
ステップ３０６では、現在対象としている１横ライン上のすべての画素を注目画素としたか否か、即ちこのライン上の検索色である有効画素をすべてカウントしたか否か判定する。この判定は、現在の注目画素が画像の右端であるか否かにより行われ、注目画素が右端であれば、その判定はＹＥＳとなってステップ３０８の処理に移行する。そうでなければ、その判定はＮＯとなり、ステップ３０７で注目画素をその右隣に移動させた後、ステップ３０２の処理に戻る。
【００２９】
ステップ３０８では、すべての横ラインに対して検索色の有効画素のカウントが完了したか否か判定する。横方向の画素の状態変化に着目した検索色の有効画素のカウントがすべて終了した場合、その判定はＹＥＳとなってステップ３１０の処理に移行する。そうでない場合、その判定はＮＯとなり、ステップ３０９で次の横ラインの左端に注目画素の座標を移動させた後、ステップ３０２の処理に戻る。
【００３０】
ステップ３１０〜３１７では、画像の縦のラインを上から下に注目画素を移動させ、その縦のラインを左から右に順次変更させながら、注目画素とこれの縦方向に隣接する画素の色（カラーコード）の違いに着目して、検索色の有効画素を特定し、その数をカウントする。
【００３１】
先ず、注目画素を画像の左上端に設定した後、ステップ３１０において、注目画素は検索色と違う色か否か判定する。注目画素は検索色と違う色であった場合、その判定はＹＥＳとなってステップ３１４の処理に移行する。反対に注目画素が検索色であった場合、その判定はＮＯとなってステップ３１１の処理に移行する。
【００３２】
ステップ３１１では、変数ｔｏｔａｌの値をインクリメントする。このインクリメントが終了すると、次にステップ３１２において、注目画素がその両縦隣の画素と違う色（カラーコード：データ）であるか否か判定する。注目画素とその両縦隣の何方か一方の画素とが異なる色であった場合、その判定はＮＯとなってステップ３１４の処理に移行する。それ以外の場合、即ち注目画素とその両縦隣の画素とが異なる色であった場合、その判定はＹＥＳとなり、ステップ３１３で変数ｄｏｔの値をインクリメントした後、ステップ３１４の処理に移行する。両縦隣の画素と違う色の注目画素も有効画素である。
【００３３】
ステップ３１４では、現在対象としている１縦ライン上のすべての画素を注目画素としたか否か、即ちこのライン上の検索色である有効画素をすべてカウントしたか否か判定する。この判定は、現在の注目画素が画像の下端であるか否かにより行われ、注目画素が下端であれば、その判定はＹＥＳとなってステップ３１６の処理に移行する。そうでなければ、その判定はＮＯとなり、ステップ３１５で注目画素をその下隣に移動させた後、ステップ３１０の処理に戻る。
【００３４】
ステップ３１６では、すべての縦ラインに対して検索色の有効画素のカウントが完了したか否か判定する。縦方向の画素の状態変化に着目した検索色の有効画素のカウントがすべて終了した場合、その判定はＹＥＳとなってステップ３１８の処理に移行する。そうでない場合、その判定はＮＯとなり、ステップ３１７で次の縦ラインの上端に注目画素の座標を移動させた後、ステップ３１０の処理に戻る。
【００３５】
上述したステップ３０１〜３１７の処理を実行することで、変数ｔｏｔａｌには検索色である全画素数を２倍した値、変数ｄｏｔには縦横の両方向の色変化に着目して検出された有効画素数（重複有り）が各々代入される。
【００３６】
ステップ３１８では、変数ｄｏｔの値を変数ｔｏｔａｌの値で除算した値を配列変数ｐｅｒｃｅｎｔ（ｉ）に代入する。変数ｄｏｔ、変数ｔｏｔａｌには上記した値が代入されていることから、変数ｐｅｒｃｅｎｔ（ｉ）には、同一のカラーコードである画素における有効画素の割合を表す値が代入され、これによって１カラーコードに対する処理が完了する。なお、変数ｐｅｒｃｅｎｔ（ｉ）における括弧内の“ｉ”は各カラーコード（描画色）に対応した値である。
【００３７】
ステップ３１８に続くステップ３１９では、使用（表示）できる各色（カラーコード）毎にその有効画素の割合の算出が終了したか否か判定する。各色（カラーコード）毎のその割合の算出が終了していない場合、その判定はＮＯとなり、次の検索色（カラーコード）を設定してステップ３０１の処理に戻る。反対に全ての色（カラーコード）の有効画素の割合を算出していた場合、その判定はＹＥＳとなり、ステップ３２０において、変数ｐｅｒｃｅｎｔ（ｉ）に代入されている値（割合）が大きい順にカラーコードのソートを行った後、一連の処理を終了する。この境界線検索色順序配列処理については、図２のステップ２０２の境界線作成処理を説明した後、この境界線作成処理と合わせて具体的に説明する。
【００３８】
図４は、上記ステップ２０２の境界線作成処理の動作フローチャートである。この境界線作成処理では、上述した境界線検索色順序配列処理のステップ３１８においてソートされたカラーコードの順序に従って境界線を作成する。その全体の概要は、注目画素とそれに隣接する画素の状態の変化から境界線を形成する画素を特定し、この特定した画素のデータをカラーコード毎に割り当てた境界線を表すカラーコードに置き換えることにより、境界線をＲＡＭ１０４の画像データ上に作成するものである。
【００３９】
ステップ４０１〜４１０では、画像の横のラインを左から右に注目画素を移動させ、その横のラインを上から下に順次変更させながら、注目画素とその横方向に隣接する画素の状態の違いに着目した境界線の作成が行われる。
【００４０】
先ず、ステップ４０１では、注目画素が現在対象としているカラーコード（検索色）と違うか否か判定する。注目画素がそのカラーコード（検索色）とは異なる場合、その判定はＹＥＳとなってステップ４０６の処理に移行する。反対に、注目画素がそのカラーコード（検索色）と同一であった場合、その判定はＮＯとなってステップ４０２の処理に移行する。
【００４１】
ステップ４０２では、注目画素が横ラインの何方か一方の端であるか否か判定する。注目画素が何方かの端でもない場合、その判定はＮＯとなってステップ４０３の処理に移行し、そうでない場合、その判定はＹＥＳとなってステップ４０７の処理に移行する。
【００４２】
ステップ４０３では、注目画素の何方か一方の横隣の画素は透明色（背景色：ユーザが描画していない領域）であるか否か判定する。注目画素の両横隣の画素は透明色でない場合、その判定はＮＯとなってステップ４０４の処理に移行する。そうでない場合、即ち何方か一方の画素は透明色であった場合、その判定はＹＥＳとなってステップ４０７の処理に移行する。
【００４３】
ステップ４０４では、注目画素の両横隣の画素は境界線であるか否か判定する。注目画素の両横隣の画素が既に境界線として特定されていた場合、その判定はＹＥＳとなってステップ４０６の処理に移行する。そうでない場合、即ち、少なくとも一方の画素は境界線ではない場合、その判定はＮＯとなってステップ４０５の処理に移行する。
【００４４】
ステップ４０５では、両横隣の画素の少なくとも一方は注目画素とは異なる境界線でない別の色（カラーコード）であるか否か判定する。両横隣の少なくとも一方の画素は注目画素の色とは異なる境界線ではない別の色であった場合、その判定はＹＥＳとなってステップ４０７の処理に移行する。これとは異なる場合には、その判定はＮＯとなってステップ４０６の処理に移行する。
【００４５】
ステップ４０７では、注目画素を境界線とする処理を実行する。実際には、上述したように、ＲＡＭ１０４に格納されている注目画素の画素データを、現在のカラーコードに割り当てた境界線のカラーコードに変更することでこの処理は実現される。
【００４６】
ステップ４０７は、ステップ４０２でＹＥＳと判定、ステップ４０３でＹＥＳと判定、或いはステップ４０５でＹＥＳと判定した場合に実行される。従って、横方向の画素の状態変化に着目した場合、注目画素が画像の端か、或いはそれに隣接する画素が注目画素とは異なる境界線でない別の色のとき、注目画素は境界線であると特定される。この境界線を形成する画素を特定する方法は、縦方向の画素の状態変化に着目した場合も同様である。
【００４７】
ステップ４０６では、対象としている１横ライン上の境界線（対象とするカラーコード）の作成がすべて終了したか否か、即ちこのライン上のすべての画素を注目画素として境界線を作成したか否か判定する。１横ライン上の境界線の作成がすべて終了した場合、その判定はＹＥＳとなってステップ４０８の処理に移行する。境界線の検出がすべて終了していない場合、その判定はＮＯとなり、ステップ４０９で注目画素をその横隣の画素（ドット）に移動させた後、ステップ４０１の処理に戻る。
【００４８】
ステップ４０８では、すべての横ラインの境界線の作成が終了したか否か、即ち画素の横方向の状態変化に着目した境界線の作成を画像全体に対して行ったか否か判定する。横方向の画素の状態変化に着目した境界線の作成がすべて終了した場合、その判定はＹＥＳとなってステップ４１１の処理に移行する。境界線の作成がすべて終了していない場合、その判定はＮＯとなり、ステップ４１０で次の横ラインの左端に注目画素を移動させた後、ステップ４０１の処理に戻る。
【００４９】
ステップ４１１〜４２０では、画像の縦のラインを上から下に注目画素を移動させ、その縦のラインを左から右に順次変更させながら、注目画素とその縦方向に隣接する画素の状態の違いに着目した境界線の作成が行われる。
【００５０】
先ず、ステップ４１１では、注目画素が現在対象としているカラーコード（検索色）と違うか否か判定する。注目画素がそのカラーコード（検索色）とは異なる場合、その判定はＹＥＳとなってステップ４１６の処理に移行する。反対に、注目画素がそのカラーコード（検索色）と同一であった場合、その判定はＮＯとなってステップ４１２の処理に移行する。
【００５１】
ステップ４１２では、注目画素が縦ラインの何方か一方の端であるか否か判定する。注目画素が何方かの端でもない場合、その判定はＮＯとなってステップ４１３の処理に移行し、そうでない場合、その判定はＹＥＳとなってステップ４１７の処理に移行する。
【００５２】
ステップ４１３では、注目画素の何方か一方の縦隣の画素は透明色（背景色：ユーザが描画していない領域）であるか否か判定する。注目画素の両縦隣の画素は透明色でない場合、その判定はＮＯとなってステップ４１４の処理に移行する。そうでない場合、即ち何方か一方の画素は透明色であった場合、その判定はＹＥＳとなってステップ４１７の処理に移行する。
【００５３】
ステップ４１４では、注目画素の両縦隣の画素は境界線であるか否か判定する。注目画素の両縦隣の画素が既に境界線として特定されていた場合、その判定はＹＥＳとなってステップ４１６の処理に移行する。そうでない場合、即ち、少なくとも一方の画素は境界線ではない場合、その判定はＮＯとなってステップ４１５の処理に移行する。
【００５４】
ステップ４１５では、両縦隣の画素の少なくとも一方は注目画素とは異なる境界線でない別の色（カラーコード）であるか否か判定する。両縦隣の少なくとも一方の画素は注目画素の色とは異なる境界線ではない別の色であった場合、その判定はＹＥＳとなってステップ４１７の処理に移行する。これとは異なる場合には、その判定はＮＯとなってステップ４１６の処理に移行する。
【００５５】
ステップ４１７では、注目画素を境界線とする処理を実行する。実際には、上述したように、ＲＡＭ１０４に格納されている注目画素の画素データを、現在設定しているカラーコードに割り当てた境界線のカラーコードに変更することでこの処理は実現される。
【００５６】
ステップ４１６では、対象としている１縦ライン上の境界線（対象とするカラーコード）の作成がすべて終了したか否か、即ちこのライン上のすべての画素を注目画素として境界線を作成したか否か判定する。１縦ライン上の境界線の作成がすべて終了した場合、その判定はＹＥＳとなってステップ４１８の処理に移行する。境界線の作成がすべて終了していない場合、その判定はＮＯとなり、ステップ４１９で注目画素をその縦隣の画素（ドット）に移動させた後、ステップ４１１の処理に戻る。
【００５７】
ステップ４１８では、すべての縦ラインの境界線の作成が終了したか否か、即ち画素の縦方向の状態変化に着目した境界線の作成を画像全体に対して行ったか否か判定する。縦方向の画素の状態変化に着目した境界線の作成がすべて終了した場合、その判定はＹＥＳとなってステップ４２１の処理に移行する。境界線の作成がすべて終了していない場合、その判定はＮＯとなり、ステップ４２０で次の縦ラインの上端に注目画素を移動させた後、ステップ４１１の処理に戻る。
【００５８】
画素の状態変化を縦横の両方向で検出して境界線を作成することで、何方か一方では境界線と特定できなかった画素も境界線と特定され、各表示領域の境界線は完全形で作成される。
【００５９】
ステップ４２１では、使用（表示）できる色（カラーコード）数の境界線の作成が終了したか否か判定する。カラーコード毎の境界線の作成がまだ終了していない場合、その判定はＮＯとなり、図３のステップ３１８でソートしたカラーコードの順序に従って次のカラーコードを設定してステップ４０１の処理に戻る。反対にカラーコード毎の境界線の作成が終了した場合、ここで一連の処理を終了する。
【００６０】
ここで、図５、及び図６を参照して、境界線の作成について具体的に説明する。図５は、予め割り当てられたカラーコードの値に従った順序で境界線を作成した場合の経過例を示す。図５において、“０”〜“５”はカラーコード（“０”は背景色）、“Ａ”〜“Ｄ”は“１”〜“４”で表したカラーコードに各々割り当てた境界線のカラーコードである。これらは全て１文字が１ドットに対応している。
【００６１】
図５（ａ）は、原画像である。同図（ｂ）〜（ｅ）は、この原画像に対してカラーコード“１”、カラーコード“２”、カラーコード“３”、カラーコード“４”の順序で境界線を順次作成していった後の状態を各々示している。
【００６２】
図５（ａ）の原画像に対して図３の境界線検索色順序整列処理を実行した場合、変数ｔｏｔａｌに最終的に代入される値は、カラーコード“１”では２８０（＝１４０×２）となり、カラーコード“２”では１０４（＝５２×２）、カラーコード“３”では２４（＝１２×２）、カラーコード“４”では２４（＝１２×２）、カラーコード“５”では１６（＝８×２）となる。
【００６３】
変数ｄｏｔには、上述したように、隣接する画素の色と異なる画素数が代入される。カラーコード“５”を例とすれば、横方向の表示状態の変化に着目した場合、そのすべての画素は両横隣の画素とはカラーコードが異なることから、この場合には有効画素は８とカウントされ、他方の縦方向では、カラーコード“５”の画素は縦方向に連なっているので０とカウントされる。従って、カラーコード“５”のときには変数ｄｏｔに８が最終的に代入される。これ以外のカラーコードでは、カラーコード“１”は８、カラーコード“２”は５２、カラーコード“３”及び“４”はともに０が変数ｄｏｔに最終的に代入される。このことから、変数ｐｅｒｃｅｎｔ（ｉ）に代入される値（＝ｄｏｔ／ｔｏｔａｌ）は、カラーコード“１”では約０．０２９となり、カラーコード“２”では０．５、カラーコード“３”及び“４”ではともに０、カラーコード“５”では０．５となる。図３のステップ３１８では、変数ｐｅｒｃｅｎｔ（ｉ）に代入されているこれらの値から、境界線を作成するカラーコードの順序を、“２”、“５”、“１”、“３”、“４”とソートすることになる。
【００６４】
図６は、上記のソートされた順序に従って境界線の作成を行った場合の経過例を示している。図６（ａ）は、図５（ａ）に示す原画像と同一である。また、図６において、“Ｅ”はカラーコード“５”の境界線に割り当てたカラーコードである。
【００６５】
図６に示すように、境界線を作成するカラーコードの順序をその境界線の割合に基づいて決定することにより、カラーコード“２”、“５”、“１”の３種類の境界線を作成しただけで各表示領域を全て分けることができる。また、図５（ｅ）と図６（ｃ）とから明らかなように、画像全体に占める境界線の割合も、カラーコードのソートによって大幅に減少している。
【００６６】
本実施例では、隣接する画素とは色が異なる画素を有効画素としている。このため、極端な例を挙げれば、直線といった形状の表示領域程、有効画素の割合、即ち変数ｐｅｒｃｅｎｔ（ｉ）に代入される値が大きくなる。このような形状の表示領域を境界線で囲む場合、その外側で囲む（他の表示領域をこれの境界線とする）よりも内側で囲むほうが境界線の長さは短くなる。例えば図５（ａ）の原画像におけるカラーコード“５”を他のカラーコード“１”、“３”、及び“４”の境界線で囲んだ場合、その境界線の画素数は“１８”となるが、カラーコード“５”の表示領域内に境界線を形成させた場合、その画素数は“８”（図６（ｃ）参照）であり、境界線の画素数は大幅に減少する。また、１つの表示領域を複数種類の境界線で囲む確率も低くなる。このことは、例えば図６において、カラーコード“５”の境界線を作成する優先度をあげたことにより、カラーコード“３”、及び“４”の境界線の作成が不要になったことからも理解できる。
【００６７】
カラーコード毎に、それに占める境界線の割合を求め、その割合が高い順に境界線を作成した場合においても、図５のように予め定められている順序で境界線を作成するより画像全体に占める境界線の割合を低減させることができる。しかし、本実施例のように、有効画素の占める割合から境界線を作成するカラーコードの順序を決定することで、さらに画像全体に占める境界線の割合を減少させることができる。このため、境界線の割合の減少に対応させて、符号化後のデータ量を低減させることができる。なお、表示領域に占める境界線の割合、及び有効画素の占める割合の両方に基づいて境界線を作成するカラーコードの順序を決定してもよい。しかし、このようにした場合、様々な種類の画像に対してその符号量をより有効に低減できるように、単に境界線を形成している画素より有効画素のほうの重みを大きくさせて、その数をカウントすることが望ましい。
【００６８】
図７は、上記境界線作成処理の終了後に実行される、図２においてステップ２０３で示す塗り潰し色取り出し処理の動作フローチャートである。
本実施例では、符号化後の画像データの解凍（復号）方式としてシードフィル方式を想定している。このシードフィル方式は、境界線で描かれた画像に対し、境界線で囲まれた各領域内を、その内部に位置するシードピクセルと呼ばれる画素を基準として、境界線にぶつかるまで画素（ドット）の位置を水平、及び垂直方向に予め定められた規則に従って移動させながらそれを塗り潰していくことで画像全体の塗り潰しを行う方式である。
【００６９】
この塗り潰し色取り出し処理の実行時では、既に境界線に該当する画素のデータは描画色でないカラーコードに置き換えられている。このため、各表示領域は容易に検索することが可能である。塗り潰し色取り出し処理では、表示領域を重複させて取り出さないように、カラーコード毎に検索した表示領域内に位置する１画素（これがその領域の塗り潰し開始点となる）を取り出した後、この表示領域をシードフィル方式でクリアしながら、各表示領域内に位置する１画素の座標の取り出しを行う。
【００７０】
先ず、ステップ７０１では、取り出す表示領域のカラーコード（解凍時におけるその領域の塗り潰し色である）を設定する。この塗り潰し色を設定する順序は、既に境界線が作成した後であるので、どのような順序でも良い。
【００７１】
塗り潰し色を設定すると、続くステップ７０２では、ＲＡＭ１０４に格納されている画像上の画素を順次変更していくことで、設定した塗り潰し色（カラーコード）とそのデータ（カラーコード）とが一致する画素を検索し、その座標データを取得する。このとき検索された画素が、それを内部に有する表示領域の解凍（復号）時における塗り潰し開始点となる。ステップ７０２に続いて実行するステップ７０３では、この取得した画素の座標を基準として、この画素を内部に有する表示領域をシードフィル方式によってクリアする。これにより、同じ表示領域を重複して取り出すことが確実に回避され、また、塗り潰し色をまだ取り出していない表示領域を容易に検索することが可能となる。
【００７２】
ステップ７０３で１表示領域のクリアが終了すると、次にステップ７０４において、ステップ７０３でクリアした表示領域から、まだ検索が済んでいない部分があるか否か判定する。画像全体の検索が済んでいない場合、その判定はＹＥＳとなってステップ７０２の処理に戻る。反対にそれが済んだ場合、その判定はＮＯとなってステップ７０５の処理に移行する。
【００７３】
ステップ７０５では、描画色の数だけ表示領域の取り出しを行ったか否か、即ち画像を構成する全ての表示領域の取り出しが完了したか否か判定する。表示領域の取り出しが全て完了していない場合、その判定はＮＯとなってステップ７０１の処理に戻る。反対に表示領域の取り出しが全て完了した場合、その判定はＹＥＳとなり、ここで一連の処理を終了する。なお、特には図示していないが、ステップ７０２において、画像全体に対する検索を行った場合、ステップ７０５の処理に移行するようになっている。
【００７４】
この塗り潰し色取り出し処理によって表示領域部分の符号化が行われるが、この符号化した後の１表示領域毎のデータは、カラーコードと、その領域内の１画素の座標データである。このため、この符号化によりそのデータ量を大幅に低減することができる。
【００７５】
上記塗り潰し色取り出し処理を実行した後には、ＲＡＭ１０４には描画色毎の境界線だけがクリアされずに残っていることになる。この残った境界線は、塗り潰し色取り出し処理に続いて実行される図２のステップ２０４の境界線取り出し処理によって取り出されてクリアされる。図８は、この境界線取り出し処理の動作フローチャートである。
【００７６】
先ず、ステップ８０１では、取り出す境界線の色（カラーコード）を設定する。続くステップ８０２では、画素を移動させながら、ステップ８０１で設定した境界線の色の画素を検索し、検索した画素を境界線の開始点に設定する。
【００７７】
ステップ８０２で境界線の開始点を設定すると、続くステップ８０３でこの開始点の画素をクリアする。その後、ステップ８０４において、この開始点の８方向を検索し、開始点に連なって境界線を形成している画素があるか否か判定する。開始点から境界線が延びている場合、ステップ８０３に戻って検索した画素を新たにクリアした後、再度ステップ８０４の処理を実行する。このステップ８０３、８０４の処理を繰り返し行うことで、１つの境界線が１画素ずつ順次クリアされる。ステップ８０２で開始点として設定した画素の座標データ、及びステップ８０４で検索した境界線が連なる方向を検索したときのデータは、境界線の符号化データとして保持される。
【００７８】
ステップ８０４で境界線が連なる方向が検索できなくなった場合、ステップ８０５の処理に移行する。ステップ８０５では、ステップ８０２で設定した開始点から再び画素を移動させながら他の境界線の開始点を検索する。この検索によって新たに開始点を見つけた場合、その判定はＹＥＳとなってステップ８０２の処理に戻る。反対に新たな開始点が見つからなかった場合、その判定はＮＯとなってステップ８０６の処理に移行する。
【００７９】
ステップ８０６では、取り出す境界線の色を設定した数から、境界線の取り出しが全て完了したか否か判定する。境界線の取り出しが完了していない場合、その判定はＮＯとなってステップ８０１の処理に戻る。反対に境界線の取り出しが全て完了している場合、その判定はＹＥＳとなり、ここで一連の処理を終了する。
【００８０】
図９は、上述した境界線取り出し処理による境界線取り出しの例を説明する図である。同図（ａ）は、ステップ８０４で検索した境界線が連なる方向のデータを示し、同図（ｂ）は、境界線例を示す。この図６（ｂ）において、各枠は各々１つの画素（ドット）であり、境界線を形成している画素（ドット）は斜線で表している。
【００８１】
画像（本実施例ではＲＡＭ１０４に格納されている）から境界線を取り出す場合、例えば注目画素をｘ方向の右に、また、ｘ方向のラインを順次ｙ方向の下に移しながら、現在設定している境界線色の画素（境界線の開始点）を検索する。図９（ｂ）の画像では、この検索により、座標（２，１）の画素がその開始点として検索される。
【００８２】
座標（２，１）の画素を検索すると、その画素を開始点として、図９（ａ）に示すように、その開始点の８方向の画素のなかで同じ境界線色のものを検索する。図９（ｂ）の例では、この検索により、座標（２，１）の画素の下隣の画素が境界線として連なっていると判定される。開始点の画素に連なっている画素は下隣であることから、このときの方向データの値は“１”である。以降、同様にして、境界線として連なっている画素を順次検索していく。これにより、座標（２，１）の画素を開始点とする境界線を符号化したときのデータ列は、“１”、“１”、“０”、“０”、“６”、“６”、“５”、“５”となる。
【００８３】
画像は２次元であることから、普通、図９（ａ）に示すように、境界線として連なっている画素を検索する方向は８方向で十分であり、少ないビット長で方向、即ち１画素を表すことができる。このため、例えば境界線を形成する各画素の座標データを格納するような場合と対比すれば、そのデータ量を大幅に低減することが可能となる。なお、実際に境界線が連なっている画素の方向を検索する場合には、境界線の形状によっては複数の連なっている画素を検索することもあることから、１つのデータ列として符号化できる境界線を複数のデータ列で符号化（図８の処理のままではこれが発生する場合がある）するのを回避するために、１画素とそれに隣接する画素だけでなく、さらに領域を広げて連なっている画素の方向を検索することが望ましい。
【００８４】
なお、本実施例では、ユーザが作成した画像を符号化（格納）する場合を例としているが、これに限定するものではなく、当然ではあるが、スキャナといった画像読取装置から取り込んだ画像に対しても本発明は適用することができる。本発明は、特に、アニメ画像といった描画色があまり多くなく、また、表示領域がはっきりしている特徴を有する画像の符号化において有効である。
【００８５】
また、本実施例では、図３の境界線検索色順序整列処理において、注目画素とそれに隣接する上下、及び左右の各画素の色が異なる場合に、それぞれ変数ｄｏｔの値をインクリメントしている。これは、このようにしたことで実際上の大きな不具合はあまり発生しないと考えて処理内容を簡単にしたためであるが、境界線を作成する順序をより正確に決定したい場合には、注目画素とそれに隣接する上下、及び左右の各画素の色がそれぞれ異なっている際には、有効画素を重複してカウントしないことが望ましい。また、注目画素は１画素としているが、画像の解像度によっては１画素幅の表示領域はほとんどあり得ない場合も考えられる。このため、有効画素を検出するための注目画素は、例えば高い解像度であった場合には４×４の画素を１注目画素とするように、解像度に応じてその大きさを変更してもよい。
【００８６】
【発明の効果】
以上、説明したように本発明の画像データ圧縮装置は、画像データを構成する画素データの種類毎に、該画素データに従って表示される表示領域の境界線部分を検出した後、該境界線部分を検出した結果から、画像データを境界線部分と表示領域部分とに分けて各々符号化するため、シードフィル方式といった画像の塗りつぶし方式を採用することができ、符号化後の表示領域のデータ量を小さくすることができる。これにより、高い圧縮率が達成される。
【００８７】
また、画素データの種類毎に表示領域の全画素数と該表示領域の境界線として表される画素数を計数することで、境界線が占める割合が大きい表示領域の画素データを優先させて境界線の検出を行うため、最終的に検出した境界線の全長さを短くすることができ、更に、境界線を検出する表示領域を減らすことができる。これにより、境界線のデータ量が低減され、更に高い圧縮率が達成される。
【図面の簡単な説明】
【図１】本実施例が適用された画像描画装置のシステム構成のブロック図である。
【図２】圧縮処理の動作フローチャートである。
【図３】境界線検索色順序整列処理の動作フローチャートである。
【図４】境界線作成処理の動作フローチャートである。
【図５】境界線作成経過例を説明する図である（その１）。
【図６】境界線作成経過例を説明する図である（その２）。
【図７】塗り潰し色取り出し処理の動作フローチャートである。
【図８】境界線取り出し処理の動作フローチャートである。
【図９】境界線取り出しの例を説明する図である。
【符号の説明】
１００  画像描画装置
１０１  入力装置
１０２  ＲＯＭ
１０３  ＣＰＵ
１０４  ＲＡＭ
１０５  ＶＤＰ
１０６  ＶＲＡＭ
１０７  表示装置
【図１】
0003658796.tif 000002
【図２】
0003658796.tif 000003
【図３】
0003658796.tif 000004
【図４】
0003658796.tif 000005
【図５】
0003658796.tif 000006
【図６】
0003658796.tif 000007
【図７】
0003658796.tif 000008
【図８】
0003658796.tif 000009
【図９】
0003658796.tif 000010