(57)【要約】【課題】  コンピュータグラフィックスに用いられる一定の長さごとに相関を有するデータを、リアルタイムで効率良く符号化する符号化装置を実現する。【解決手段】  複数の入力データを符号化テーブル１３１中の列方向に配列された複数の参照データと比較して、一致検出部１２３で一致が検出された場合は、登録データ行列用カウンタ１３２の一致回数に１を加算し、不一致の場合には、入力データをデータ記憶領域１３３に格納し、格納された複数の入力データ同士を類似検出部１２４で比較し、類似している場合に入力データを符号化テーブル１３１の同じ列の一致回数が少ない参照データと置換し、符号化テーブル１３１を更新して入力データを符号化アルゴリズム実行部１２で符号化するようにして構成した。【選択図】      図１
2006129357.tif 000002
【特許請求の範囲】
【請求項１】
マトリクス状に配列され、所定ビット数の参照データを有する符号化テーブルに基づいて、コンピュータグラフィックス画像生成に用いられる複数の入力データを符号化する符号化装置において、
前記複数の入力データを前記符号化テーブル中の列方向に配列された前記複数の参照データと比較して、一致した場合には、一致回数をカウントするカウント部と、
不一致であった場合には、前記入力データを格納するデータ記憶部と、
前記データ記憶部の中に格納された前記複数の入力データ同士を比較し、類似している場合に前記類似しているいずれか１つの入力データを前記符号化テーブルの複数の参照データ中における同じ列にある前記一致回数が少ない参照データと置換させて、前記符号化テーブルを更新させるデータ更新部と、
前記データ更新部で更新された前記符号化テーブルを格納する格納部と、
更新された前記符号化テーブルを用いて前記複数の入力データを符号化する符号化部と、
有することを特徴とする符号化装置。
【請求項２】
マトリクス状に配列され、所定ビット数の参照データを有する符号化テーブルに基づいて、コンピュータグラフィックス画像生成に用いられる複数の入力データを符号化する符号化方法において、
前記複数の入力データを前記符号化テーブル中の列方向に配列された前記複数の参照データと比較して、一致した場合には、一致回数をカウントし、
不一致であった場合には、前記入力データをデータ記憶領域に格納し、
前記記憶領域に格納された前記複数の入力データ同士を比較し、類似している場合に前記類似しているいずれか１つの入力データを前記符号化テーブルの複数の参照データ中における同じ列にある前記一致回数が少ない参照データと置換させて、前記符号化テーブルを更新し、
更新された前記符号化テーブルを用いて前記複数の入力データを符号化することを特徴とする符号化方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、所定のデータ単位毎に相関を有して入力されるディジタルデータを、リアルタイムで高能率符号化し、及び符号化されたデータを復号化するデータ符号化装置及び符号化方法に関する。
【背景技術】
【０００２】
大容量のディジタルデータを高能率に圧縮し、できるだけ少ない容量で記憶し、あるいは転送するための技術として高能率符号化技術が開発されている。例えば、ハフマン符号化法のように出現率の高いものには短い符号を割り当て、出現率の低いものには長い符号を割り当てるＦＶ（Fixed-to-Variable）符号化法、特許文献１に開示されるＬＺ（Lempel-Ziv）符号化法、及び特許文献２に開示されるＬＺＷ（Lempel-Ziv Wilch）符号化法がある。それらの符号化方法は過去に出現したデータ列とこれから圧縮しようとしているデータ列の一致性を利用して符号化する方式である。
【特許文献１】米国特許第４４６４６５０号明細書
【特許文献２】米国特許第４５５８３０２号明細書
【発明の開示】
【発明が解決しようとする課題】
【０００３】
従来までのデータ圧縮技術では、データ圧縮の際に圧縮対象となる全てのデータを一旦スキャンする必要があるために、データを入力しながら圧縮処理を実行することができず、全てのデータの圧縮処理が完了するまでに多くの時間を要する等の問題があった。圧縮処理時間を短縮する方法として、データを入力しながら圧縮処理を行う、ゼロ圧縮法や連長圧縮法等のいわゆる１パス圧縮、復元法が提案されている。
しかしながら、それらの１パス圧縮、復元法は、圧縮対象であるデータが特定ワードの繰り返し構造を有する場合には高い圧縮率を達成することができるものの、例えばコンピュータグラフィクス画像生成に用いられる、一定のデータ単位毎に相関を有して高いビットレートで出力される大容量のデータをリアルタイムで圧縮することはできなく、効率の良い圧縮方法ではなかった。
【０００４】
そこで、本発明は、上記のような問題点を解消するためになされたもので、一定のデータ単位毎に相関を有して発生されるデータを、リアルタイムで効率良く符号化することができる符号化装置及び符号化方法を提供することを目的とする。
【課題を解決するための手段】
【０００５】
本願発明における第１の発明は、マトリクス状に配列され、所定ビット数の参照データを有する符号化テーブルに基づいて、コンピュータグラフィックス画像生成に用いられる複数の入力データを符号化する符号化装置において、前記複数の入力データを前記符号化テーブル中の列方向に配列された前記複数の参照データと比較して、一致した場合には、一致回数をカウントするカウント部と、不一致であった場合には、前記入力データを格納するデータ記憶部と、前記データ記憶部の中に格納された前記複数の入力データ同士を比較し、類似している場合に前記類似しているいずれか１つの入力データを前記符号化テーブルの複数の参照データ中における同じ列にある前記一致回数が少ない参照データと置換させて、前記符号化テーブルを更新させるデータ更新部と、前記データ更新部で更新された前記符号化テーブルを格納する格納部と、更新された前記符号化テーブルを用いて前記複数の入力データを符号化する符号化部と、有することを特徴とする符号化装置を提供する。
第２の発明は、マトリクス状に配列され、所定ビット数の参照データを有する符号化テーブルに基づいて、コンピュータグラフィックス画像生成に用いられる複数の入力データを符号化する符号化方法において、前記複数の入力データを前記符号化テーブル中の列方向に配列された前記複数の参照データと比較して、一致した場合には、一致回数をカウントし、不一致であった場合には、前記入力データをデータ記憶領域に格納し、前記記憶領域に格納された前記複数の入力データ同士を比較し、類似している場合に前記類似しているいずれか１つの入力データを前記符号化テーブルの複数の参照データ中における同じ列にある前記一致回数が少ない参照データと置換させて、前記符号化テーブルを更新し、更新された前記符号化テーブルを用いて前記複数の入力データを符号化することを特徴とする符号化方法を提供する。
【発明の効果】
【０００６】
本発明によれば、複数の入力データを符号化テーブル中の列方向に配列された複数の参照データと比較して、一致した場合には、一致回数をカウントし、不一致であった場合には、前記入力データをデータ記憶領域に格納し、前記記憶領域に格納された前記複数の入力データ同士を比較し、類似している場合に前記類似しているいずれか１つの入力データを前記符号化テーブルの複数の参照データ中における同じ列にある前記一致回数が少ない参照データと置換させて、前記符号化テーブルを更新し、更新された前記符号化テーブルを用いて前記複数の入力データを符号化する格別な動作をするので、例えばコンピュータグラフィックス画像生成に用いられる一定のデータ単位毎に相関を有して高いビットレートで発生されるデータを、リアルタイムで効率良く符号化することができる符号化装置及び符号化方法を実現できる。
【発明を実施するための最良の形態】
【０００７】
以下に本発明の各実施例に係るデータ符号化装置及び符号化データ復号化装置について図１〜図１２を用いて説明する。
図１は、本発明の実施に係るデータ符号化装置の構成例を示したブロック図である。
図２は、本発明の実施に係るデータ符号化装置の構成例を詳細に示したブロック図である。
図３は、本発明の実施に係る第ｎ列の登録データ行と入力データ列の関係を例示した図である。
図４は、本発明の実施に係る２ビットの行指定符号テーブルを例示した図である。
図５は、本発明の実施に係る４ビットの位置指定符号テーブルを例示した図である。
図６は、本発明の実施に係る登録データ、入力データ及び出力データの関係を例示した図である。
図７は、本発明の実施に係る登録データ行、列及びカウント値の更新例を示した図である。
図８は、本発明の実施に係る不一致データを例示した図である。
図９は、本発明の実施に係る更新された登録データ行、列を例示した図である。
図１０は、本発明の実施に係るデータ復号化装置の構成例を示したブロック図である。
図１１は、本発明の実施に係るデータ符号化装置の動作をフローチャートで例示した図である。
図１２は、本発明の実施に係るデータ復号化装置の動作をフローチャートで例示した図である。
【０００８】
そのデータ符号化装置は、例えばコンピュータグラフィックス画像生成に用いられるような、一定のデータ単位毎に相関を有して高いビットレートで発生されるデータを、リアルタイムで効率良く符号化することを実現するという目的を、複数の入力データを符号化テーブル中の列方向に配列された複数の参照データと比較して、一致した場合には、一致回数をカウントし、不一致であった場合には、前記入力データをデータ記憶領域に格納し、前記記憶領域に格納された前記複数の入力データ同士を比較し、類似している場合に前記類似しているいずれか１つの入力データを前記符号化テーブルの複数の参照データ中における同じ列にある前記一致回数が少ない参照データと置換させて、前記符号化テーブルを更新し、更新された前記符号化テーブルを用いて前記複数の入力データを符号化するようにして実現した。
【０００９】
データ符号化装置の構成について述べる。
図１に示すデータ符号化装置１はデータ入力部１１と、行指定符号化テーブル１２１、及び位置指定符号化テーブル１２２を格納する符号化アルゴリズム実行部１２と、登録データ記憶領域１３１、登録データ行列用カウンタ１３２、及び次候補データ記憶領域１３３を格納する登録データ行列用メモリ１３と、データ出力部１４とより構成される。データ入力部１１には符号化するデータが入力される。データ出力部１４からは符号化されたデータが出力される。
図２に示すデータ符号化装置１は図１に示した符号化アルゴリズム実行部１２の構成を詳細に示したものであり、その符号化アルゴリズム実行部１２は行指定符号化テーブル１２１、位置指定符号化テーブル１２２、一致検出部１２３、類似検出部１２４、登録更新データ作成部１２５、及びアルゴリズム実行部１２６より構成される。
図１０に示す符号化データ復号化装置２はデータ入力部２１と、行指定復号化テーブル２２１、及び位置指定復号化テーブル２２２を格納する符号化アルゴリズム実行部２２と、登録データ記憶領域２３１、登録データ行列用カウンタ２３２、及び次候補データ記憶領域２３３を格納する登録データ行列用メモリ２３と、データ出力部２４とより構成される。データ入力部１には符号化された復号化対象のデータが入力される。データ出力部１４からは復号化されたデータが出力される。
【００１０】
データ符号化装置の動作について述べる。
そのデータ符号化装置１には、登録データ記憶領域１３１に出現確率の高い入力データと類似する登録データが予め記憶されており、その登録データと類似する入力データが入力されたときに、登録データ記憶領域１３１では記憶されている登録データが参照されて符号化がなされる。符号化される信号は、参照された登録データを指定するための指定符号と、登録データと入力データとが異なる部分の入力データに係るデータとが用いられて符号化データとして生成され、生成された符号化データはデータ符号化装置１から出力される。
符号化データ復号化装置２にある登録データ記憶領域２３１には、符号化装置の登録データ記憶領域１３１に記憶されると同じ登録データを記憶する。入力された符号化データから、符号化時に参照された登録データに係る情報を得、得られた登録データと、その登録データと入力データの異なり情報が基にされて符号化装置で符号化されたデータが復号化される。
【００１１】
ここで、データ符号化装置１に入力されるデータは、例えばコンピュータグラフィクス映像信号の制作に用いられるような、所定の間隔で類似するデータが繰り返して配置される、自己相関の高いデータが符号化対象とされる。登録データ記憶領域１３１には入力データと相関性の高いデータが記憶されている。その相関性の高いデータは、過去に符号化して得られた同種類のデータ符号化時煮えられた登録データを用いられる方法と、入力データから相関性の高いデータを抽出し、登録データ記憶領域１３１に記憶しつつ符号化する方法とがある。いずれの方法による場合であっても、登録データ記憶領域１３１に記憶される登録データは入力データに対してさらに相関性の高いデータに更新され、効率の高い符号化がなされる。
【００１２】
更に説明する。
まず、符号化される入力データはデータ入力部１１に入力される。そこでは入力データが有する相関性に応じて、例えば３２ビット-ごとに分割され、分割された３２ビットのデータは４個ごとにグルーピングされた１２８ビットが１セットのデータとされて符号化アルゴリズム実行部１２に入力される。符号化アルゴリズム実行部１２に入力されるデータは、登録データ行列用メモリ１３の登録データ記憶領域１３１に記憶される登録データと比較され、類似される登録データが検出される。符号化アルゴリズム実行部１２では、後述の方法により検出された登録データがマトリクス配置されて格納される行の位置が行指定符号化テーブル１２１に記述される行指定符号により指定される。登録データと一致するデータが存在する位置は位置指定符号化テーブル１２２に記述される位置指定符号により指定される。入力データは、行指定符号、位置指定符号、及び一致しなかったデータ部分の順に配列されたデータとして符号化される。
【００１３】
登録データの更新について述べる。
入力データと類似度の高い登録データが存在するときは高い圧縮率が得られるのに比し、登録データが存在しない場合は符号化効率が低下する。そこで、登録データ毎に参照される回数を計数し、参照される度合いの低い登録データは参照される新たな登録データに置換する。
入力されるデータのうち、参照する登録データが存在しない入力データは次候補データ記憶領域１３３に記憶される。
次に、例えば１６回にわたり、入力データと登録データとの比較が行われて記憶された複数の不一致データ同士が比較される。比較して一致される部分が存在するデータは次候補データとして記憶領域１３３に記憶される。１６回の比較で１度も参照されなかった登録データは次候補データと交換される。交換された次候補データである入力データに係る情報により、登録データ記憶領域１３１の登録データが更新される。次回以降の符号化は、更新された登録データが用いられて行われる。
【００１４】
図２を参照して符号化アルゴリズム実行部１２を説明する。
一致検出部１２３で、データ入力部１１から供給される入力データは登録データ行列用メモリ１３の登録データ記憶領域１３１に記憶される登録データと比較される。一致する登録データが存在する場合には、行及び列で配列される登録データの位置に係る登録データ行列用カウンタ１３２のカウント値が１増加されると共に、行情報はアルゴリズム実行部１２６に入力される。同時に一致するデータが存在するＭＳＢ（Most Significant Bit）からのビット位置情報はアルゴリズム実行部１２６に入力される。どの行にも一致するデータが存在しない場合には、一致ビットなしに係る情報及び入力データはアルゴリズム実行部１２６に供給されると共に、入力データは次候補データ記憶領域１３３に記憶される。
次候補データ記憶領域１３３には、登録データとの比較で一致するビットが存在しなかった入力データが記憶される。類似検出部１２４では、例えば１６回の比較により次候補データ記憶領域１３３に記憶された複数の入力データ同士が比較される。比較の結果、ＭＳＢからの所定のビットが一致している入力データがある場合には、その一致ビットが存在する入力データは同一ビット部分を有する類似データとして登録更新データ作成部１２５に供給される。登録更新データ作成部１２５では、同一ビット部分が存在する入力データが存在し、且つ過去に登録データ行列用カウンタ１３２でカウントされなかった登録データが検出された場合には、カウントされなかった登録データを同一ビット部分が存在する一方の入力データに置換させるための信号が生成され、登録データ記憶領域１３１に供給される。
【００１５】
図３〜図５を参照してアルゴリズム実行部１２６の符号化方法を説明する。
図３において、行と列でマトリックス配列される登録データ行列の第ｎ番目（ｎは自然数）の列である１つの列の構造と、その列に対応して入力される入力データ列を示したものである。ここで、入力データ列はそれぞれが４ビットであるＥ０〜Ｅ７の８個のデータで構成される。登録データはそれぞれが４ビットであるＡ０〜Ａ７の３２ビットである第１行、同様にして３２ビットの第２行、第３行、及び第４行で構成される。
一致検出部１２３では、最初にＥ７とＡ７、Ｂ７、Ｃ７、及びＤ７のそれぞれが比較され、一致する４ビットが存在するかが検出される。例えばＥ７とＣ７とが一致する場合には一致する行は第３行として検出される。次に、Ｅ６とＣ６、Ｅ５とＣ５、Ｅ４とＣ４の順に第３行の同じビット位置の４ビット同士が比較される。その比較は一致しないビットが検出されるまでなされる。Ｅ３とＣ３の手前まで一致した場合にはＥ７〜Ｅ４の上位１６ビット（＝４×４ビット）が一致したとして検出される。
【００１６】
図４は、行指定符号化テーブル１２１に格納されるテーブルである。上記の、例えばＥ７とＣ７とが一致する場合には一致する行は第３行であり、第３行に記憶されるデータが参照されて符号化がなされる。参照される行の第１行〜第４行に対して２ビットの行指定符号は０〜３（２進数表示で００〜１１）が用いられる。
【００１７】
図５は、位置指定符号化テーブル１２２に格納されるテーブルである。
入力データの上位何ビットが一致しているかが４ビットごとに指定される。入力データＥ７〜Ｅ０の全３２ビットが一致する場合は位置指定符号として４ビットの位置指定符号を８（２進数表示で１０００）として指定する。全ビットが一致する場合には割り当て符号は８のみである。
上記のＥ３とＣ３の手前まで、即ちＥ７〜Ｅ４の上位１６ビットが一致した場合の位置指定符号は４（２進数表示で０１００）である。割り当て符号は４に続けて一致しなかったデータＥ３、Ｅ２、Ｅ１、及びＥ０を記述した符号が割り当て符号とされる。
Ｅ７〜Ｅ０の全てが一致しない場合には位置指定符号０（２進数表示で００００）に続けてＥ７〜Ｅ０の３２ビットの入力データを記述した符号が割り当て符号とされる。
本実施例における符号化は、入力データ列と一致度の高い登録データをデータ行として有することにより符号化効率を高める。
【００１８】
図６〜図９を参照して登録データの更新について述べる。
図６は、４行、４列で記述される登録データと、その登録データを用いて行う符号化を説明するための入力データと、出力データとを示している。例えば第１行第１列の登録データｆｆｆｆ＿ｆｆｆｆは、１６進数で示されるｆ（２進数表示で１１１１）が８個からなるデータであることを示している。なお、「＿（＝アンダーバー）」はデータを４個ずつ読みやすくするために便宜上挿入した記号であり、信号としては無視される。第１行第１列の右側に四角に囲んで示される数字の３は、第１行第１列のｆｆｆｆ＿ｆｆｆｆが３回参照されて符号化がなされたことを示す登録データ行列用カウンタ１３２に記憶されるカウント値である。
【００１９】
次に、入力データの符号化について述べる。
同図において３２ビットごとに分割された４個（４列）のデータが入力されている。第１列目のデータはｆｆｆｆ＿ｆｆｆｆである。そのデータは第１列のｆｆｆｆ＿ｆｆｆｆと一致している。従って、符号化出力データは、第１列を示す行指定符号が０（２進数表現で００）に続いて全３２ビットが一致していることを示す位置指定符号８（２進数表現で１０００）が出力される。入力データの第２列は００００＿００３２であり、第２行と上位２４ビットが一致している。従って、行指定符号は１に続いて上位２４ビットが一致していることを示す位置指定符号６と一致しないデータ３２が出力される。第３列は第４行と上位１６ビットが一致しており、一致しない下位１６ビットのデータは００００であるので、３＿４＿００００が出力される。第４列は第４行と上位８ビットが一致しているので３＿２＿ｆｆ＿ｆｆｆｆが出力される。出力される符号化データのビット数は、第１列が６ビット、第２列以降は順に１４、２２、３０ビットであり、合計７２ビットである。入力データのビット数は４×３２＝１４４べビットであり、この場合の符号化データは５０％に圧縮されている。
【００２０】
図７には、上記の符号化の結果参照された列の行のカウント数が１増加している状態が示されている。図中、カウント数の増加している個所は太線で囲まれている。なお、そのカウント値そのものは符号化されて符号化データ復号化装置２に送られない。復号化装置側では符号化信号に含まれる行指定符号や位置指定符号を検出し、登録データ行列用カウンタ２３２では符号化側の登録データ行列用カウンタ１３２と同様のカウント値を得ている。
【００２１】
図８には、４×３２ビットで１セットの入力データを１６セット入力した後に、上位４ビット以上がいずれの行の登録データとも一致しなかった場合の出力データが示されている。これらの一致ビットが存在しない３２ビットのデータ同士は類似検出部１２４で比較され、ＭＳＢ以降の４ビット以上でお互いに一致するデータが検出される。例えば、第２列のａｃ２４＿６１３２とａｃ５ａ＿ｃ８ｅｆとでは上位８ビットが一致しており、類似するデータとして検出される。ｃｅ３ａ＿７１ｆｆとｃｅ３ａ＿００２１は上位１６ビットが一致する類似データとして検出される。
【００２２】
図９には、更新された登録データ行、列が示されている。
類似するとして検出された第２列のデータはカウント値が０である第３行のデータと置換され、第４列のデータは第２行のデータと置換される。カウント値は１６セットの符号化が終了した直後であり、「０」にリセットされている。
登録データ行列の更新は符号化データ復号化装置２側でもなされる。復号化装置側では一致ビットなしとする位置指定符号が付されて伝送される３２ビットのデータは次候補データ記憶領域２３３に記憶される。類似検出が行われた後、登録データ行列用カウンタ２３２のカウント値を基にし、カウント値が０である登録データ記憶領域２３１の登録データは更新される。
【００２３】
図１０を参照して符号化データ復号化装置２でなされる信号処理を説明する。
データ符号化装置１で符号化された符号化データはデータ入力部２１に入力される。そこでは、行指定符号及び位置指定符号が検出される。符号化アルゴリズム実行部２２では、検出された行指定符号は行指定復号化テーブル２２１が参照されて登録データ記憶領域２３１のどの行が参照されて符号化された信号であるかが検出される。次に、位置指定符号は位置指定復号化テーブル２２２が参照されて登録データの何ビットまでが一致しているかが検出される。一致していないデータ部分は位置指定符号に続けて伝送される符号が用いられ、復号化データが得られる。同時に登録データ行列用カウンタ２３２では検出された行指定符号と位置指定符号とが基にされ、該当する行のカウント値がインクリメントされる。一致ビットなしの符号は次候補データ記憶領域２３３に記憶され、そこで登録データ更新用のデータが作成される。例えば１６セットの復号化終了後にカウント値が０である箇所のデータは更新用のデータと置換される。登録データ記憶領域２３１に記憶される登録データは登録データ記憶領域１３１に記憶される登録データと同一に保たれている。それにより、データ出力部２４からは、データ入力部１１に入力されたと同一のデータが出力される。
【００２４】
図１１を参照してデータ符号化装置１の処理の流れを説明する。
Ｓ（ステップ）６１で符号化データのセット数に係るカウンタのカウント値を１にリセットし、登録データ行列に登録データをセットし、次に全ての登録データ行列用のカウンタを０にリセットする。Ｓ６２で入力データを取得する。Ｓ６３で入力データと一致するビット数の多い行に係る登録データを取得する。Ｓ６４で取得した登録データと入力データを比較し、ＭＳＢから何ビット一致しているかを検出する。Ｓ６５で取得した登録データの行情報を基に行指定符号を行指定符号テーブルから取得する。Ｓ６６で、検出されたＭＳＢからの一致するビット数に応じた位置指定符号を位置指定符号テーブルから取得する。Ｓ６７で取得された行指定符号、位置指定符号、及び指定される位置以降の入力データを基に符号語を生成する。Ｓ６８で、符号化時に取得、参照された登録データの行列に係るカウント数に１を加える。Ｓ６９で全ての列を符号化したかが検出され、符号化されていない列が検出される場合にはＳ６２からの動作を繰り返す。全ての列の符号化が成された場合にはＳ７１で、全ての列（この例では４列）の符号化をセットとする場合のセット数の値が例えば１５セット以下であるかが検出される。１５以下の場合はＳ７２でセット数に１を加えてＳ６２以降を繰り返す。セット数が１５を超える場合はＳ７４で前述の方法による登録データの更新を行う。Ｓ７５でさらに入力データがあるかが検出され、入力データがなくなるまでＳ６２からの動作を繰り返す。
【００２５】
図１２を参照してデータ復号化装置２の処理の流れを説明する。
Ｓ８１でセットカウント数を１にセットし、登録データ行列に登録データをセットする。Ｓ８２では全ての登録データ行列用のカウンタをリセットする。Ｓ８３で復号化用符号化データを取得し、Ｓ８４で符号化データから行指定符号及び位置指定符号を取得する。Ｓ８５で行指定符号により指定される、符号化時に参照した登録データの行の位置情報を得る。Ｓ８６で、位置指定符号を基に参照する登録データのＭＳＢからのデータを取得する。Ｓ８７で指定された登録データと、位置指定符号に続けて送られる入力データの不一致部分とを組み合わせる。Ｓ８８で組み合わせて得られる復号化データが出力される。Ｓ８９で参照した登録データに係る行列カウント値に１を加算する。Ｓ９１で全ての列を復号化したかを検出し、復号化していない場合はＳ８３からの処理を繰り返す。全ての列を復号化した場合はＳ９２でセットカウンタのカウント値が、例えば１５以下であるかが検出される。１５以下の場合Ｓ９３でセット数に１を加えＳ８３以降の処理を繰り返す。１５を超える場合にはＳ９４でセット数を１にリセットし、Ｓ９５で前述の登録データの更新を行う。Ｓ９６で復号化すべき入力データが存在するか否かが検出され、存在する場合はＳ８３からの処理を繰り返す。入力データが存在しないときには復号化処理を終了する。
【００２６】
以上、データ符号化装置１及び符号化データ復号化装置２の構成とその動作について述べた。
なお、１セットのデータを、３２ビット×４列のデータ列として述べたが、それらの数は任意の数であっても良い。また、１６セット毎に登録データを更新するとして述べたが、その数も任意の数でよい。また、位置指定符号に係る一致ビットを４ビットごとに与えた。これらの数は符号化効率と処理時間を参照して適当な値に設定すればよく、それらの数の選択は設計事項である。
さらに、符号化するデータをコンピュータグラフィクス画像生成用データを例として述べたが、コンピュータグラフィクス画像生成用データと同様に所定のデータ間隔で高い相関を有するデータである限り、他の用途で用いられるディジタルデータの符号化に適応することができる。
【００２７】
本実施例で述べたデータ符号化装置１によれば、複数の入力データを符号化テーブル１３１中の列方向に配列された複数の参照データと比較して、一致した場合には、一致回数をカウントし、不一致であった場合には、前記入力データをデータ記憶領域１３３に格納し、前記記憶領域に格納された前記複数の入力データ同士を類似検出部１２４で比較し、類似している場合に前記類似しているいずれか１つの入力データを前記符号化テーブルの複数の参照データ中における同じ列にある前記一致回数が少ない参照データと置換させて、前記符号化テーブルを更新し、更新された前記符号化テーブルを用いて前記複数の入力データを符号化アルゴリズム実行部１２で符号化する格別な構成を有するので、例えばコンピュータグラフィックス画像生成に用いられる一定のデータ間隔毎に高い相関を有し、高いビットレートで発生されるデータをリアルタイムで効率良く符号化することができるディジタルデータ符号化装置を実現できる。
【産業上の利用可能性】
【００２８】
コンピュータグラフィクスデータのような、所定のデータ単位毎に相関を有して入力されるディジタルデータを、リアルタイムで高能率符号化するデータ符号化装置に適用できる。
【図面の簡単な説明】
【００２９】
【図１】本発明の実施に係るデータ符号化装置の構成例を示したブロック図である。
【図２】本発明の実施に係るデータ符号化装置の構成例を詳細に示したブロック図である。
【図３】本発明の実施に係る第ｎ列の登録データ行と入力データ列の関係を例示した図である。
【図４】本発明の実施に係る２ビットの行指定符号テーブルを例示した図である。
【図５】本発明の実施に係る４ビットの位置指定符号テーブルを例示した図である。
【図６】本発明の実施に係る登録データ、入力データ及び出力データの関係を例示した図である。
【図７】本発明の実施に係る登録データ行、列及びカウント値の更新例を示した図である。
【図８】本発明の実施に係る不一致データを例示した図である。
【図９】本発明の実施に係る更新された登録データ行、列を例示した図である。
【図１０】本発明の実施に係るデータ復号化装置の構成例を示したブロック図である。
【図１１】本発明の実施に係るデータ符号化装置の動作をフローチャートで例示した図である。
【図１２】本発明の実施に係るデータ復号化装置の動作をフローチャートで例示した図である。
【符号の説明】
【００３０】
１    データ符号化装置
２    符号化データ復号化装置
１１    データ入力部
１２    符号化アルゴリズム実行部
１３    登録データ行列用メモリ
１４    データ出力部
２１    データ入力部
２２    符号化アルゴリズム実行部
２３    登録データ行列用メモリ
２４    データ出力部
１２１    行指定符号化テーブル
１２２    位置指定符号化テーブル
１２３    一致検出部
１２４    類似検出部
１２５    登録更新データ作成部
１２６    アルゴリズム実行部
１３１    登録データ記憶領域
１３２    登録データ行列用カウンタ
１３３    次候補データ記憶領域
２２１    行指定復号化テーブル
２２２    位置指定復号化テーブル
２３１    登録データ記憶領域
２３２    登録データ行列用カウンタ
２３３    次候補データ記憶領域
【図１】
2006129357.tif 000003
【図２】
2006129357.tif 000004
【図３】
2006129357.tif 000005
【図４】
2006129357.tif 000006
【図５】
2006129357.tif 000007
【図６】
2006129357.tif 000008
【図７】
2006129357.tif 000009
【図８】
2006129357.tif 000010
【図９】
2006129357.tif 000011
【図１０】
2006129357.tif 000012
【図１１】
2006129357.tif 000013
【図１２】
2006129357.tif 000014