(57)【要約】【課題】従来よりも簡素に伸長することが可能な圧縮データを生成する技術を提供する。【解決手段】信号生成部は、設定値がゼロのレジスタ（順序決定部内）の中で最も優先順位の高いレジスタに対応するバッファ部内のバッファレジスタに要求信号を出力し、上記レジスタ及びデータ圧縮装置の符号化部へ圧縮データを出力させる（Ｓ１１０）。この圧縮データが連続数データであれば、連続数データが設定されたレジスタの中で最も優先順位の高いレジスタと、これよりも優先順位の高いレジスタとに対応する減算器に作動信号を出力して、設定値（圧縮データ）をダウンカウントさせ、これらレジスタのいずれかの設定値がゼロに達すると、これに対応するバッファレジスタに要求信号を出力し、新たな圧縮データを出力させる（Ｓ１２０〜Ｓ１５０）。【選択図】　図３
2004080148.tif 000002
【特許請求の範囲】
【請求項１】
複数種類の値を取り得る多値データからなるデータ列を圧縮するデータ圧縮方法であって、
前記多値データが取り得る値である特有値のそれぞれに互いに異なった優先順位を割り当て、
前記特有値のいずれかを注目値とし、該注目値より優先順位の高い特有値を持つ多値データを前記データ列から除いてなる部分データ列を、前記注目値の連続数を表す連続数データと、該注目値以外の非注目値の連続数を表すブランク数データとからなるランレングスデータ列に変換することで圧縮し、該圧縮を前記特有値の全てについて実施すると共に、
前記特有値毎に生成されたランレングスデータ列を構成する各データを、該データの伸長時に使用される順に配列することを特徴とするデータ圧縮方法。
【請求項２】
複数種類の値を取り得る多値データからなるデータ列を圧縮するデータ圧縮装置であって、
前記多値データが取り得る値である特有値のそれぞれに互いに異なった優先順位を割り当て、前記特有値のいずれかを注目値に設定し、該注目値より優先順位の高い特有値を持つ多値データを前記データ列から除いてなる部分データ列を、前記注目値の連続数を表す連続数データと、該注目値以外の非注目値の連続数を表すブランク数データとからなるランレングスデータ列に変換することで圧縮し、該圧縮を前記特有値の全てについて実施するデータ圧縮手段と、
該データ圧縮手段にて前記特有値毎に生成されたランレングスデータ列を構成する各データを、該データの伸長時に使用される順に配列するデータ配列手段と、
を備えていることを特徴とするデータ圧縮装置。
【請求項３】
前記データ配列手段は、
前記データ圧縮手段にて生成されたランレングスデータ列を、前記優先順位毎に分別して順次格納する格納手段と、
前記優先順位毎に設けられた複数のレジスタからなるレジスタ群と、
該レジスタ群を構成するレジスタの中に設定値がゼロのものがあれば、その中で前記優先順位の最も高いレジスタについて、該レジスタに対応する優先順位のランレングスデータ列の先頭に位置する前記連続数データ又は前記ブランク数データを前記格納手段から読み込んで該レジスタに設定するデータ設定手段と、
該データ設定手段により前記連続数データが設定されたレジスタの中で前記優先順位が最も高いレジスタの設定値を、該レジスタより優先順位の高いレジスタの設定値と共にダウンカウントするカウント手段と、
を備え、前記データ設定手段が前記格納手段から読み込んだ順に、前記連続数データ及び前記ブランク数データを配列することを特徴とする請求項２記載のデータ圧縮装置。
【請求項４】
前記カウント手段は、ダウンカウントすべきレジスタの設定値の中で最小のものを検出し、該設定値がゼロになるようにダウンカウントすることを特徴とする請求項３記載のデータ圧縮装置。
【請求項５】
前記データ圧縮手段は、
前記部分データ列を構成する前記多値データを順次取り込むデータ取込手段と、
該データ取込手段が取り込んだ前記多値データ数をカウントするアップカウンタと、
前記データ取込手段が取り込んだ多値データが前記注目値から前記非注目値、又は前記非注目値から前記注目値に切り替わると、前記アップカウンタのカウント値を前記連続数データ又は前記ブランク数データとして出力すると共に、前記アップカウンタのカウント値をリセットするカウント制御手段と、
を備えることを特徴とする請求項２乃至請求項４いずれか記載のデータ圧縮装置。
【請求項６】
前記データ圧縮手段は、
前記アップカウンタのカウント値が、予め設定された限界値に達すると、前記アップカウンタのカウントを一時停止して、前記限界値を前記連続数データ又は前記ブランク数データとして出力すると共に、前記アップカウンタのカウント値をリセットする第２カウント制御手段を備えることを特徴とする請求項５記載のデータ圧縮装置。
【請求項７】
前記格納手段は、各特有値毎にＦＩＦＯ（ｆｉｒｓｔ−ｉｎ　ｆｉｒｓｔ−ｏｕｔ）方式のレジスタを有してなり、該レジスタのいずれかの残り容量が、予め設定された値を下回った際には、前記データ圧縮手段の機能を一時停止させ、前記格納手段が次に格納すべきカウント値を出力させることを特徴とする請求項３乃至請求項６いずれか記載のデータ圧縮装置。
【請求項８】
前記アップカウンタは、一時停止したカウント値を出力して、カウント値がリセットされると、ゼロからなるカウント値を出力するように設定されていることを特徴とする請求項６又は請求項７記載のデータ圧縮装置。
【請求項９】
前記データ列は、画像を形成する画像データからなることを特徴とする請求項２乃至請求項８いずれか記載のデータ圧縮装置。
【請求項１０】
前記多値データは、表示色を示すことを特徴とする請求項９記載のデータ圧縮装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、複数種類の値を取り得る多値データからなるデータ列を圧縮する技術に関する。
【０００２】
【従来の技術】
従来より、画像データの記録や伝送を効率良く行うために、画像データの圧縮が行われている。
その１つとして、例えば、特開２００１−３１３５６９号公報には、画像データを、同じ特徴を有するデータ（以下、「特徴データ」）という。）毎に分離し、その特徴データ毎にランレングス変換等を行うことでデータ圧縮を行う画像圧縮装置が開示されている。
【０００３】
この種の画像圧縮装置では、予め設定された単位（例えば、ページ単位やマクロブロック単位）毎に、上述のようなデータ圧縮を行い、これにより生成される特徴データ毎の圧縮データは、図９に示すように、特徴データ（成分Ａ〜Ｃ）毎にまとめたものを連結した、所謂、ビットストリームとして記録媒体（例えば、ＤＶＤ−ＲＯＭなど）に記録されたり、伸長側の装置（以下、「デコーダ」という。）へ伝送される。但し、圧縮データ同士の間には、圧縮データの種類や圧縮データ同士の境界を示すタグが付加され、デコーダにて各圧縮データを識別できるようにされている。
【０００４】
【発明が解決しようとする課題】
ところで、ビットストリーム中の圧縮データは、伸長処理に使用する順序で配列されているわけではないため、デコーダは、処理単位に含まれる圧縮データが全て揃わなければ、元のデータ列に伸長する処理を開始することができなかった。
【０００５】
その結果、デコーダでは、少なくとも、処理単位のビットストリームを一時蓄積できるだけの大きな容量のバッファメモリが必要となるだけでなく、処理単位の先頭を受信してから、その処理単位について伸長を開始するまでの遅延時間が大きくなるという問題があった。
【０００６】
又、デコーダでは、圧縮データを伸長する際に、圧縮データの種類を把握しているため、圧縮データをその種別毎に、格納されているアドレスを管理するか、異なる領域に格納しなければならず、前者の場合には、アドレスを管理するためのメモリが別途必要となった。又、後者の場合には、各領域毎に空き容量が発生するため、バッファメモリの使用効率の低下を招いた。
【０００７】
更に、圧縮データを伸長するには、圧縮データを、その伸長処理に使用する順に配列し直す必要があり、その際、バッファメモリに逐次アクセスする必要が生じる。ここで、デコーダ内の伸長処理部とバッファメモリとが、デコーダ内の各処理部間のデータ通信に共通に用いられるデータバスに接続されていると、伸長処理のためにデータバスが占有されてしまい、画像データの伸長以外に行うべき画像データの表示処理などが妨げられ、その処理の実行に大きな遅延を生じてしまっていた。
【０００８】
以上から、従来の圧縮データでは、即座に伸長処理を開始することができない上、デコーダにおける伸長処理の負荷（所謂、オーバーヘッド）が大きくなってしまい、伸長処理に時間を要した。このため、例えば、カーナビゲーション装置に用いる地図データが上記のように圧縮されていると、車両の走行速度が高くなった際に、画面のスクロール表示が追従できず、運転者に時々刻々と変化する情報をリアルタイムに提供することが困難であった。
【０００９】
そこで、本発明は、上記問題点を解決するために、従来よりも簡素に伸長することが可能な圧縮データを生成する技術を提供することを目的とする。
【００１０】
【課題を解決するための手段】
上記目的を達成するためになされた請求項１記載のデータ圧縮方法では、複数種類の値を取り得る多値データからなるデータ列を圧縮する際に、多値データが取り得る値である特有値のそれぞれに互いに異なった優先順位を割り当てる。そして、特有値のいずれかを注目値とし、該注目値より優先順位の高い特有値を持つ多値データをデータ列から除いてなる部分データ列を、注目値の連続数を表す連続数データと、該注目値以外の非注目値の連続数を表すブランク数データとからなるランレングスデータ列に変換することで圧縮し、該圧縮を前記特有値の全てについて実施すると共に、特有値毎に生成されたランレングスデータ列を構成する各データを、該データの伸長時に使用される順に配列する。
【００１１】
このようなデータ圧縮方法によれば、伸長時に使用される順にランレングスデータ列中の各データを予め配列するため、データ列の伸長を行う際に、ランレングスデータ列を配列し直す必要がない。即ち、デコーダは、受信した順に伸長処理を施していくだけで圧縮データを伸長できる。
【００１２】
この結果、従来のように、大きな容量のバッファメモリを備えて、処理単位毎の圧縮データが全て揃うまで圧縮データを蓄積する必要がない上、バッファメモリに逐次アクセスする必要もなくなるため、伸長処理を開始するまでの遅延時間や伸長処理の負荷を低減できる。従って、伸長処理に要する時間を短縮できる。
【００１３】
又、デコーダ内の他の処理部の共有のデータバスを占有して、他の処理の実行を大きく妨げてしまうことがないため、他の処理の実行に遅延を生じさせることもない。
又、圧縮データのアドレスを管理するためのメモリを別途用意したり、バッファメモリに種別毎に異なる領域に格納する必要もない。
【００１４】
以上から、本発明により、従来よりも簡素に伸長可能な圧縮データを生成できる。
次に、請求項２記載のデータ圧縮装置では、データ圧縮手段が、特有値のそれぞれに互いに異なった優先順位を割り当て、特有値のいずれかを注目値に設定し、該注目値より優先順位の高い特有値を持つ多値データをデータ列から除いてなる部分データ列を、注目値の連続数を表す連続数データと、該注目値以外の非注目値の連続数を表すブランク数データとからなるランレングスデータ列に変換することで圧縮し、該圧縮を特有値の全てについて実施する。そして、データ配列手段が、データ圧縮手段にて特有値毎に生成されたランレングスデータ列を構成する各データを、該データの伸長時に使用される順に配列する。
【００１５】
即ち、本発明は、請求項１記載の発明を実現するための装置であり、請求項１記載の発明と同様の効果を得ることができる。
ここで、データ配列手段は、例えば、請求項３記載のように構成すれば良い。
即ち、請求項３記載のデータ圧縮装置におけるデータ配列手段では、格納手段が、データ圧縮手段にて生成されたランレングスデータ列を、優先順位毎に分別して順次格納する。次に、レジスタ群中のレジスタの中に設定値がゼロのものがあれば、データ設定手段が、その中で優先順位の最も高いレジスタについて、該レジスタに対応する優先順位のランレングスデータ列の先頭に位置する連続数データ又はブランク数データを格納手段から読み込んで該レジスタに設定する。
【００１６】
続いて、カウント手段が、データ設定手段により連続数データが設定されたレジスタの中で優先順位が最も高いレジスタの設定値を、該レジスタより優先順位の高いレジスタの設定値と共にダウンカウントし、ダウンカウントの結果、レジスタのいずれかの設定値がゼロになると、データ設定手段が、上記動作を繰り返す。
【００１７】
そして、データ配列手段が、データ設定手段が読み込んだ順に連続数データ及びブランク数データを配列することで、各特有値毎の連続数データやブランク数データが、伸長に使用する順に配列される。
ところで、上記カウント手段では、レジスタ群中のいずれかのレジスタの設定値がゼロになるまで、新たな連続数データやブランク数データの配列が行われず、ダウンカウントのみがなされる。このため、カウント手段は、例えば、請求項４記載のように、ダウンカウントすべきレジスタの設定値の中で最小のものを検出し、該設定値がゼロになるようにダウンカウントするように設定されていると良い。
【００１８】
即ち、カウント手段がダウンカウントする度にダウンカウントすべきレジスタのいずれかの設定値がゼロになるため、データ設定手段は、カウント手段がダウンカウントする度に、新たな連続数データやブランク数データを読み出すことができる。つまり、このようなカウント手段を備えたデータ圧縮装置では、連続数データやブランク数データの配列を効率良く、迅速に行うことができる。
【００１９】
ここで、データ圧縮手段は、例えば、請求項５記載のように、部分データ列を構成する多値データを順次取り込むデータ取込手段と、該データ取込手段が取り込んだ多値データ数をカウントするアップカウンタと、データ取込手段が取り込んだ多値データが注目値から非注目値、又は非注目値から注目値に切り替わると、アップカウンタのカウント値を連続数データ又はブランク数データとして出力すると共に、アップカウンタのカウント値をリセットするカウント制御手段とを備えていても良い。
【００２０】
このようなデータ圧縮手段では、データ取込手段が、部分データ列を構成する多値データを順次取込み、アップカウンタが、データ取込手段が取り込んだ多値データ数をカウントする。そして、カウント制御手段が、データ取込手段が取り込んだ多値データが注目値から非注目値、又は非注目値から注目値に切り替わると、アップカウンタのカウント値を連続数データ又はブランク数データとして出力すると共に、アップカウンタのカウント値をリセットする。
【００２１】
このようなデータ圧縮手段によれば、注目値と非注目値とをそれぞれカウントするだけでランレングスデータ列を構成する各データを生成することができる。
ここで、データ圧縮手段は、請求項６記載のように、アップカウンタのカウント値が、予め設定された限界値に達すると、アップカウンタのカウントを一時停止して、限界値を連続数データ又はブランク数データとして出力すると共に、アップカウンタのカウント値をリセットする第２カウント制御手段を備えると良い。
【００２２】
このようなデータ圧縮手段によれば、たとえ、注目値や非注目値の連続数がアップカウンタのカウント範囲を越えるような場合でも、アップカウンタのオーバーフローを防止することができる。尚、この場合、注目値や非注目値の連続数は、カウントの限界値と、リセット後のカウント値とに分割される。
【００２３】
又、請求項７記載のように、前記格納手段が、各特有値毎にＦＩＦＯ（ｆｉｒｓｔ−ｉｎ　ｆｉｒｓｔ−ｏｕｔ）方式のレジスタを有してなる場合には、該レジスタのいずれかの残り容量が、予め設定された値を下回った際に、データ圧縮手段の機能を一時停止させ、格納手段が次に格納すべきカウント値を出力させるように設定すると良い。
【００２４】
このように格納手段を設定すれば、データ設定手段は、逐次、連続数データやブランク数データをレジスタ群中のレジスタに設定することができるので、格納手段のレジスタに連続数データやブランク数データが溜まっていき、オーバーフローしてしまうことを防止できる。
【００２５】
ところで、アップカウンタは、カウントを一時停止して出力したカウント値に続けて、リセット後に再開したカウントのカウント値を出力すると、連続数データのカウント値であるにも関わらずブランク数データのカウント値と誤認識されたり、又、ブランク数データのカウント値であるにも関わらず、連続数データのカウント値として誤認識されてしまう。
【００２６】
これを防止するため、アップカウンタは、請求項８記載のように、一時停止したカウント値を出力して、カウント値がリセットされると、ゼロからなるカウント値を出力するように設定されることが望ましい。
尚、データ列は、例えば、請求項９記載のように、画像を形成する画像データからなっていても良く、この場合、多値データは、例えば、請求項１０記載のように、表示色を示していても良い。
【００２７】
即ち、例えば、カーナビゲーション装置に用いられる地図データが上記のように圧縮されていれば、簡素に伸長していくことができるため、運転者に従来よりもリアルタイムに情報を提供することができる。
【００２８】
【発明の実施の形態】
以下に本発明の実施形態を図面と共に説明する。
まず、本実施形態のデータ圧縮装置は、カーナビゲーション装置の地図データを圧縮するためのものである。そして、このカーナビゲーション装置のディスプレイに表示される地図上の背景や道路、建物などには、予め表示色が割り当てられており、上記地図データは、これら表示色を示す色データから構成されている。
【００２９】
ここで、図１は、本実施形態のデータ圧縮装置の構成を示すブロック図である。
図１に示すように、データ圧縮装置１は、シリアルに入力された地図データ中に含まれている色データの種類（本実施形態では、色データＡ〜Ｄとする。）を判別するデータ判別部１１と、データ判別部１１の判別結果に基づいて、地図データ中における各色データの連続性を示すランレングスデータ列を生成する圧縮部１２と、圧縮部１２にて生成されたランレングスデータ列を各色データ毎に格納するバッファ部１３と、バッファ部１３に格納された各ランレングスデータ列の出力順序を決定する順序決定部１４と、順序決定部１４から出力されたランレングスデータ列にハフマン符号を割り当て、ランレングスデータ列を符号化する符号化部１５とから構成されている。
【００３０】
尚、データ判別部１１には、予め色データＡ〜Ｄの値が記憶されており、データ判別部１１は、当該データ判別部１１に記憶されている色データＡ〜Ｄの値をそれぞれ注目値に設定して、入力された地図データ中の各色データの値と比較し、その一致及び不一致を示す判定フラグを各色データの種類毎に分別して圧縮部１２へ出力するようにされている。
【００３１】
但し、データ判別部１１に記憶された各色データの値には、予め優先順位が割り当てられている（ここでは、色データＡが最も優先順位が高く、以下、Ｂ→Ｃ→Ｄの順である。）。そして、データ判別部１１は、比較の際、優先順位の高い色データの値と地図データ中の色データの値が一致している区間では、それよりも優先順位の低い色データの値を比較の対象外に設定し、優先順位の高い色データの値と地図データ中の色データの値とが不一致な区間においてのみ、優先順位の低い色データの値を比較の対象に設定する。
【００３２】
つまり、データ判別部１１は、記憶された各色データの値毎に、それよりも優先順位の高い色データを地図データから除いてなる部分データ列中の各色データの値との一致及び不一致を判定するようにされている。
次に、圧縮部１２は、データ判別部１１から判定フラグを入力される度にアップカウントするアップカウンタを各色データ毎に備えて構成されている。
【００３３】
尚、このアップカウンタは、各々に入力される判定フラグが、一致を示す状態から不一致を示す状態へ、又、不一致を示す状態から一致を示す状態へ移行する度に、それまでのカウント値を固定ビット長にてバッファ部１３へ出力すると共に、直ちにカウント値をリセットして、新たなアップカウントを開始するようにされている。
【００３４】
これにより、圧縮部１２では、各色データ毎に、各色データの値がそれぞれ注目値に設定された際における、その色データの連続回数を示す連続数データと、他の色データの連続回数を示すブランク数データとが交互に生成される。そして、これらデータにより上記ランレングスデータ列が構成される。
【００３５】
尚、連続数データやブランク数データがアップカウンタのカウント範囲を越えるような場合に、アップカウンタがオーバーフローするのを防止するため、アップカウンタは、カウント値が、カウント範囲の限界に達すると、アップカウントを一時停止して、カウントの限界値をバッファ部１３へ出力すると共に、直ちにカウント値をリセットして、新たなアップカウントを開始するようにされている。
【００３６】
又、アップカウンタはそれぞれ、バッファ部１３から強制出力信号を受信するようにされており、強制出力信号を受信した際には、アップカウントを一時停止して、それまでのカウント値をバッファ部１３へ出力するようにされている。
但し、上記いずれの一時停止を行った場合でも、アップカウンタは、カウント値のリセット直後にゼロからなるカウント値をバッファ部１３へ出力するように設定されており、一時停止後の新たなアップカウントによるカウント値が、連続数データの続きであるにも関わらずブランク数データに、又、ブランク数データの続きであるにも関わらず連続数データに誤認識されることを防止している。
【００３７】
続いて、バッファ部１３は、圧縮部１２の各アップカウンタから出力された連続数データやブランク数データを格納するＦＩＦＯ方式のレジスタ（以下、「バッファレジスタ」という。）を各色データ毎に備えて構成されている。
そして、各バッファレジスタは、順序決定部１４から要求信号を受信する度に、格納している連続数データやブランク数データを、格納した順に順序決定部１４へ出力するようにされている。
【００３８】
尚、バッファ部１３は、バッファレジスタのオーバーフローを防止するため、バッファレジスタのいずれかの残り容量が予め設定された値を下回ると、次に当該バッファ部１３が格納すべき連続数データもしくはブランク数データを生成しているアップカウンタに対して、カウント値の送出を要求する強制出力信号を出力するように設定されている。
【００３９】
ここで、図２は、順序決定部１４の内部構成を示すブロック図である。
図２に示すように、順序決定部１４は、バッファ部１３の各バッファレジスタから出力される連続数データ及びブランク数データを各色データ毎にそれぞれ格納する４基のレジスタ１４１ａ，１４１ｂ，１４１ｃ，１４１ｄからなるレジスタ群１４１と、バッファ部１３の各バッファレジスタから出力される連続数データ及びブランク数データを符号化部１５へ出力するセレクタ１４２と、作動信号に従って、レジスタ群１４１中の各レジスタの設定値（つまり、格納された連続数データやブランク数データ）をそれぞれ１だけ減算する４つの減算器１４３ａ，１４３ｂ，１４３ｃ，１４３ｄからなる減算器群１４３と、バッファ部１３の各バッファレジスタへの要求信号を生成する信号生成部１４４とから構成されている。
【００４０】
尚、減算器群１４３中の各減算器は、減算結果をレジスタ群１４１中の対応するレジスタにそれぞれフィードバックするようにされている。これにより、レジスタ群１４１中のレジスタと減算器群１４３中の減算器とにより、所謂、ダウンカウンタが形成され、レジスタの設定値は、減算器の作動と共に１づつダウンカウントされていく。但し、データ圧縮装置１の起動時には、レジスタ群１４１中の各レジスタの設定値は、ゼロに設定されている。
【００４１】
又、順序決定部１４では、レジスタ群１４１中の各レジスタに、対応する色データと同様の優先順位が割り当てられており、信号生成部１４４は、各レジスタの優先順位と各レジスタの設定値とに基づいて、作動信号と要求信号とを生成するようにされている。又、連続数データ及びブランク数データは、交互にレジスタに設定されるため、信号生成部１４４は、各バッファレジスタへの要求信号の出力回数から、連続数データとブランク数データのどちらがレジスタに設定されたのかを判別するようにされている。
【００４２】
ここで、図３は、信号生成部１４４が行う処理の流れを示すフローチャートである。
図３に示すように、信号生成部１４４は、まず、レジスタ群１４１中のレジスタの中で最も優先順位の高いレジスタに対応するバッファレジスタに要求信号を出力し（Ｓ１１０）、このバッファレジスタに連続数データもしくはブランク数データを出力させる。
【００４３】
そして、上記レジスタに設定された設定値が連続数データであるか否かを判別し（Ｓ１２０）、連続数データであれば、連続数データが設定されたレジスタの中で最も優先順位の高いレジスタと、これよりも優先順位の高いレジスタとに対応する減算器に作動信号を出力して（Ｓ１３０）、これらレジスタの設定値をダウンカウントさせる。
【００４４】
そして、設定値のダウンカウントが行われたレジスタのいずれかの設定値がゼロに達したことを確認すると（Ｙｅｓ：Ｓ１４０）、設定値がゼロに達したレジスタに対応するバッファレジスタに要求信号を出力し（Ｓ１５０）、新たな設定値を上記レジスタに設定させる。
【００４５】
ここで、新たな設定値がブランク数データであると判別すると（Ｎｏ：Ｓ１６０）、本処理は、Ｓ１１０へ戻される。
尚、Ｓ１２０において、新た設定された設定値がブランク数データであると判別した場合にも、本処理は、Ｓ１１０へ戻される。
【００４６】
又、Ｓ１４０において、ダウンカウントの対象となっているいずれのレジスタの設定値がゼロに到達していなかったり、Ｓ１６０において、新たに設定された設定値が連続数データであった場合には、本処理は、Ｓ１３０へ戻される。
このような処理を経て、信号生成部１４１は、バッファ部１３に格納された各色データの連続数データやブランク数データの出力順序を決定する。
【００４７】
そして、セレクタ１４２は、信号生成部１４１が選択した順に連続数データ及びブランク数データを符号化部１５へ出力する。
以上のように構成されたデータ圧縮装置１によれば、例えば、「ＡＡＡＡＢＣＡＡＡＣＢＤＤＡ」という順番に色データが配列されてなる地図データの圧縮を行うと、まず、データ判別部１１及び圧縮部１２によって、地図データは、「４（Ａ），２（ＮＡ），３（Ａ），４（ＮＡ），１（Ａ）」「１（Ｂ），２（ＮＢ），１（Ｂ），２（ＮＢ）」、「２（Ｃ），２（ＮＣ）」、「２（Ｄ）」という４種類の圧縮データに変換され（図４参照）、これら圧縮データがそれぞれ、バッファ部１３に格納される。但し、ここでは、（Ａ），（Ｂ），（Ｃ），（Ｄ）は、各色データ毎の連続数データを示し、又、（ＮＡ），（ＮＢ），（ＮＣ）は、各色データ毎のブランク数データを示している。
【００４８】
そして、順序決定部１４によって、バッファ部１３に格納された４種類の圧縮データが、「４（Ａ），２（ＮＡ），１（Ｂ），２（ＮＢ），２（Ｃ），３（Ａ），４（ＮＡ），１（Ｂ），２（ＮＢ），２（ＮＣ），２（Ｄ）」という順番に配列され、符号化部１５にて符号化される。
【００４９】
即ち、圧縮データは伸長に使用される順番に配列されているため、伸長を行う際に、デコーダにて圧縮データを配列し直す必要がない。
このため、本実施形態のデータ圧縮装置１によれば、デコーダに大きな容量のバッファメモリを備えて、処理単位毎の圧縮データが全て揃うまで圧縮データを蓄積する必要がない上、バッファメモリに逐次アクセスする必要もなくなるため、伸長処理を開始するまでの遅延時間や伸長処理の負荷を低減できる。従って、伸長処理に要する時間を短縮できる。
【００５０】
又、デコーダ内の他の処理部の共有のデータバスを占有して、他の処理の実行を大きく妨げてしまうことがないため、他の処理の実行に遅延を生じさせることもない。
又、圧縮データのアドレスを管理するためのメモリを別途用意したり、バッファメモリに種別毎に異なる領域に格納する必要もない。
【００５１】
以上から、本実施形態のデータ圧縮装置１により、従来よりも簡素に伸長可能な圧縮データを生成できる。
尚、本実施形態では、データ判別部１１及び圧縮部１２が、本発明のデータ圧縮手段に相当し、バッファ部１３及び順序決定部１４が、本発明のデータ配列手段に相当する。
【００５２】
より詳細には、バッファ部１３が、本発明の格納手段に、信号生成部１４４が、本発明のデータ設定手段に、レジスタ群１４１及び減算器群１４３が、本発明のカウント手段に相当する。そして、データ判別部１１が、本発明のデータ取込手段に、圧縮部１２が、本発明のアップカウンタ及びカウント制御手段、第２カウント制御手段に相当する。
【００５３】
ここで、本実施形態のデータ圧縮装置１では、順序決定部１４に代えて、図５に示す順序決定部２４を備えても良い。
尚、順序決定部２４は、信号生成部及び減算器群の構成が、順序決定部１４の信号生成部１４４及び減算器群１４３の構成と一部異なるだけである。従って、ここでは、順序決定部１４と共通する部分については同一の符号を付してその説明を省略し、異なる部分についてのみ詳述する。
【００５４】
図５に示すように、順序決定部２４の信号生成部２４４には、ダウンカウントすべきレジスタの設定値のうちの最小のもの（最小値）を選択する最小値選択部２４５が具備されている。
そして、減算器２４３ａ，２４３ｂ，２４３ｃ，２４３ｄにはそれぞれ、最小値算出部２４５により選択された最小値が入力されており、これら減算器は、信号生成部２４４から作動信号を入力されると、レジスタ群１４１中のレジスタの設定値を、最小値算出部２４５により選択された最小値で減算するように設定されている。
【００５５】
ここで、図６は、最小値選択部２４５の構成を示すブロック図である。
図６に示すように、最小値選択部２４５は、レジスタ１４１ａ，１４１ｂの設定値の大きさを比較し、小さい方を選択する比較器２４６ａと、比較器２４６ａにより選択された設定値Ｓ２（つまり、レジスタ１４１ａ，１４１ｂの設定値のうちの小さい方）の大きさとレジスタ１４１ｃの設定値の大きさとを比較し、小さい方を選択する比較器２４６ｂと、比較器２４６ｂにより選択された設定値Ｓ３（つまり、レジスタ１４１ａ，１４１ｂ，１４１ｃの設定値のうちの最も小さなもの）の大きさとレジスタ１４１ｄの設定値の大きさを比較し、小さい方を選択する比較器２４６ｃと、レジスタ１４１ａの設定値Ｓ１及び比較器２４６ａ，２４６ｂ，２４６ｃによりそれぞれ選択された設定値Ｓ２，Ｓ３，Ｓ４のうちから減算器群２４３中の減算器に出力すべき設定値を選択するセレクタ２４７とから構成されている。
【００５６】
尚、セレクタ２４７は、信号生成部２４４の要求信号の出力回数から連続数データとブランク数データのどちらがレジスタに設定されたのかを判別するようにされている。
そして、セレクタ２４７は、図７に示す参照テーブルに基づいて動作するように設定されている。
【００５７】
即ち、レジスタ１４１ａに連続数データが設定された場合には、設定値Ｓ１を最小値に選択する。そして、レジスタ１４１ｂに連続数データが設定され、且つ、レジスタ１４１ｂが連続数データを設定されたレジスタの中で最も優先順位が高い場合には、設定値Ｓ２を最小値に選択する。又、レジスタ１４１ｃに連続数データを設定され、且つ、レジスタ１４１ｃが連続数データを設定されたレジスタの中で最も優先順位が高い場合には、設定値Ｓ３を最小値に選択し、レジスタ１４１ｄにのみ連続数データが設定された場合には、設定値Ｓ４を最小値に選択する。
【００５８】
このようにセレクタ２４７が動作することにより、ダウンカウントすべきレジスタの設定値のうちの最小値が選択される。
従って、以上のように構成された順序決定部２４を備えたデータ圧縮装置１では、図８に示すように、順序決定部２４がダウンカウントを行う度にダウンカウントすべきレジスタのいずれかの設定値がゼロになるため、ダウンカウントを行う度に新たな連続数データやブランク数データを配列することができる。
【００５９】
即ち、連続数データやブランク数データの配列を効率良く、迅速に行うことができる。
尚、順序決定部２４が、請求項４記載のカウント手段に相当する。
以上、本発明の実施の形態について説明したが、本発明は、上記実施形態に何ら限定されることはなく、本発明の技術的範囲に属する限り種々の形態をとり得ることはいうまでもない。
【００６０】
例えば、上記実施形態では、本発明をカーナビゲーション装置に用いる地図データの圧縮に適用していたが、例えば、ＪＰＥＧ（Ｊｏｉｎｔ　　Ｐｈｏｔｏｇｒａｐｈｉｃ　　Ｅｘｐｅｒｔｓ　Ｇｒｏｕｐ）規格やＭＰＥＧ（Ｍｏｖｉｎｇ　Ｐｉｃｔｕｒｅ　　Ｅｘｐｅｒｔｓ　Ｇｒｏｕｐ）規格などに基づいて画像データの圧縮を行うデータ圧縮装置に適用しても良い。
【００６１】
この場合、画像データから輝度信号や色差信号をそれぞれ判別するようにデータ判別部を設定すれば良い。
【図面の簡単な説明】
【図１】本発明に係るデータ圧縮装置１の構成を示すブロック図である。
【図２】順序決定部１４の内部構成を示すブロック図である。
【図３】信号生成部１４４が行う処理の流れを示すフローチャートである。
【図４】データ判別部１１及び圧縮部１２における処理の概要を示す説明図である。
【図５】順序決定部２４の内部構成を示すブロック図である。
【図６】最小値選択部２４５の内部構成を示すブロック図である。
【図７】設定値Ｓ１，Ｓ２，Ｓ３，Ｓ４の選択に用いる参照テーブルの概要である。
【図８】順序決定部２４における各レジスタの設定値の時系列的な変化を示す表である。
【図９】従来のデータ圧縮の概要を示す説明図である。
【符号の説明】
１…データ圧縮装置、　１１…データ判別部、　１２…圧縮部、　１３…バッファ部、　１４，２４…順序決定部、　１５…符号化部、　１４１…レジスタ群、　１４１ａ，１４１ｂ，１４１ｃ，１４１ｄ…レジスタ、　１４２，２４７…セレクタ、　１４３…減算器群、　１４３ａ，１４３ｂ，１４３ｃ，１４３ｄ，２４３ａ，２４３ｂ，２４３ｃ，２４３ｄ…減算器、　１４４，２４４…信号生成部、　２４５…最小値選択部、　２４６ａ，２５６ｂ，２４６ｃ…比較器。
【図１】
2004080148.tif 000003
【図２】
2004080148.tif 000004
【図３】
2004080148.tif 000005
【図４】
2004080148.tif 000006
【図５】
2004080148.tif 000007
【図６】
2004080148.tif 000008
【図７】
2004080148.tif 000009
【図８】
2004080148.tif 000010
【図９】
2004080148.tif 000011