(57)【要約】  【課題】  ランダム性の高いデータであっても比較的圧縮率を低下させることなく圧縮し得るデータ圧縮装置等を提供する。  【解決手段】  周辺要素データの値に基づいて注目要素データに対応する予測値を求める予測値生成部２と、注目要素データの値と予測値との差分に基づき予測誤差値を演算する予測誤差値生成部３と、周辺要素データに対して既に演算して得られている修正値と注目要素データに対応する予測誤差値との実質的な線形結合により表現される値を注目要素データの予測誤差値の下位ｎビットを０とした値に対応する修正値として演算する修正値生成部４と、予測誤差値の下位ｎビットを０とした値と修正値との差分に基づいて修正予測誤差値を求めこの修正予測誤差値と予測誤差値の下位ｎビット分のデータとを出力する修正予測誤差値生成部５と、を備えたデータ圧縮装置。【選択図】図１
2006211155.tif 000002
【特許請求の範囲】
【請求項１】
任意の２つの要素データ間に距離を定め得る複数の要素データを含むデータ、を処理するためのデータ圧縮装置であって、
注目要素データの上記距離に関して周辺にある周辺要素データの値に基づいて、該注目要素データに対応する予測値を求める予測値演算手段と、
上記注目要素データの値と上記予測値との差分に基づいて、該注目要素データに対応する予測誤差値を演算する予測誤差値演算手段と、
上記予測誤差値に所定の演算を施すことにより該予測誤差値に対する修正値を求める修正値演算手段と、
上記予測誤差値に相応する値と上記修正値との差分に基づいて修正予測誤差値を求める修正予測誤差値演算手段と、
を具備し、
上記修正値演算手段は、上記周辺要素データに対して既に演算して得られている修正値と、上記予測誤差値演算手段により演算して得られた注目要素データに対応する予測誤差値と、の実質的な線形結合により表現される値を、注目要素データの予測誤差値に相応する値に対応する修正値として演算するものであることを特徴とするデータ圧縮装置。
【請求項２】
上記データは画像データであり、上記要素データは該画像データを構成する画素データである、ことを特徴とする請求項１に記載のデータ圧縮装置。
【請求項３】
上記修正予測誤差値演算手段は、上記予測誤差値に相応する値を、該予測誤差値の下位ｎ（ｎは１以上の整数）ビットを０とした値とするものであるとともに、該予測誤差値の下位ｎビット分のデータを別途出力するものであることを特徴とする請求項１に記載のデータ圧縮装置。
【請求項４】
上記修正値演算手段は、
上記周辺要素データに対して既に演算して得られている修正値Ｃi-1 （ｉは０以上の整数）と、上記予測誤差値演算手段により演算して得られた注目要素データに対応する予測誤差値Ｐi と、の実質的な線形結合を、
上記周辺要素データに対して既に演算して得られている修正値Ｃi-1 を下位側へｎビットシフトさせた値と、上記予測誤差値演算手段により演算して得られた注目要素データに対応する予測誤差値Ｐi を下位側へｎビットシフトさせた値と、の１以上２n未満の整数である係数ａ，ｂを用いた線形結合により、
2006211155.tif 000015
のように表現し（ここに、右辺の括弧は床関数を表す）、
この値Ｃi を、注目要素データの予測誤差値に相応する値に対応する修正値とするものであることを特徴とする請求項３に記載のデータ圧縮装置。
【請求項５】
任意の２つの要素データ間に距離を定め得る複数の要素データを含むデータ、を処理するためのデータ圧縮方法であって、
注目要素データの上記距離に関して周辺にある周辺要素データの値に基づいて、該注目要素データに対応する予測値を求める予測値演算ステップと、
上記注目要素データの値と上記予測値との差分に基づいて、該注目要素データに対応する予測誤差値を演算する予測誤差値演算ステップと、
上記予測誤差値に所定の演算を施すことにより該予測誤差値に対する修正値を求める修正値演算ステップと、
上記予測誤差値に相応する値と上記修正値との差分に基づいて修正予測誤差値を求める修正予測誤差値演算ステップと、
を含み、
上記修正値演算ステップは、上記周辺要素データに対して既に演算して得られている修正値と、上記予測誤差値演算ステップにより演算して得られた注目要素データに対応する予測誤差値と、の実質的な線形結合により表現される値を、注目要素データの予測誤差値に相応する値に対応する修正値として演算するステップであることを特徴とするデータ圧縮方法。
【請求項６】
コンピュータに、任意の２つの要素データ間に距離を定め得る複数の要素データを含むデータ、を処理させるためのデータ圧縮プログラムであって、
コンピュータに、
注目要素データの上記距離に関して周辺にある周辺要素データの値に基づいて、該注目要素データに対応する予測値を求める予測値演算ステップと、
上記注目要素データの値と上記予測値との差分に基づいて、該注目要素データに対応する予測誤差値を演算する予測誤差値演算ステップと、
上記予測誤差値に所定の演算を施すことにより該予測誤差値に対する修正値を求める修正値演算ステップと、
上記予測誤差値に相応する値と上記修正値との差分に基づいて修正予測誤差値を求める修正予測誤差値演算ステップと、
を実行させるためのプログラムであり、
上記修正値演算ステップは、上記周辺要素データに対して既に演算して得られている修正値と、上記予測誤差値演算ステップにより演算して得られた注目要素データに対応する予測誤差値と、の実質的な線形結合により表現される値を、注目要素データの予測誤差値に相応する値に対応する修正値として演算するステップであることを特徴とするデータ圧縮プログラム。
【請求項７】
任意の２つの要素データ間に距離を定め得る複数の要素データを含むデータを処理することにより得られたデータであって、注目要素データの上記距離に関して周辺にある周辺要素データの値に基づいて該注目要素データに対応する予測値を求め、上記注目要素データの値と上記予測値との差分に基づいて該注目要素データに対応する予測誤差値を演算し、上記周辺要素データに対して既に演算して得られている修正値と上記演算により得られた注目要素データに対応する予測誤差値との実質的な線形結合により表現される値を注目要素データの予測誤差値に相応する値に対応する修正値として演算し、上記予測誤差値に相応する値と上記修正値との差分に基づいて求められた修正予測誤差値、を処理するためのデータ伸張装置であって、
既に求められた上記周辺要素データに対応する予測誤差値に相応する値に基づき上記修正値を求め、この修正値と、注目要素データに対応する上記修正予測誤差値と、に基づき注目要素データに対応する予測誤差値に相応する値を求める予測誤差値演算手段と、
既に求められた上記周辺要素データに対応する要素データの値に相応する値に基づき、予測値に相応する値を求める予測値演算手段と、
上記予測値に相応する値と、上記予測誤差値に相応する値と、の和に基づいて、要素データの値に相応する値を求める要素データ値演算手段と、
を具備したことを特徴とするデータ伸張装置。
【請求項８】
任意の２つの要素データ間に距離を定め得る複数の要素データを含むデータを処理することにより得られたデータであって、注目要素データの上記距離に関して周辺にある周辺要素データの値に基づいて該注目要素データに対応する予測値を求め、上記注目要素データの値と上記予測値との差分に基づいて該注目要素データに対応する予測誤差値を演算し、上記周辺要素データに対して既に演算して得られている修正値と上記演算により得られた注目要素データに対応する予測誤差値との実質的な線形結合により表現される値を注目要素データの予測誤差値に相応する値に対応する修正値として演算し、上記予測誤差値の下位ｎ（ｎは１以上の整数）ビットを０とした値と上記修正値との差分に基づいて求められた修正予測誤差値と、該予測誤差値の下位ｎビット分のデータと、を処理するためのデータ伸張装置であって、
既に求められた上記周辺要素データに対応する予測誤差値に相応する値に基づき上記修正値を求め、この修正値と、注目要素データに対応する上記修正予測誤差値と、に基づき上記予測誤差値の下位ｎビットを０とした値を求め、該予測誤差値の下位ｎビットを０とした値と、該予測誤差値の下位ｎビット分のデータの値と、の和を演算することにより、予測誤差値を求める予測誤差値演算手段と、
既に求められた上記周辺要素データに対応する要素データの値に基づき、予測値を求める予測値演算手段と、
上記予測値と、上記予測誤差値と、の和に基づいて、要素データの値を求める要素データ値演算手段と、
を具備したことを特徴とするデータ伸張装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、任意の２つの要素データ間に距離を定め得る複数の要素データを含むデータを処理するためのデータ圧縮装置、データ圧縮方法、データ圧縮プログラム、データ伸張装置に関する。
【背景技術】
【０００２】
複数の要素データを含んで構成されるデータは、要素データ間に、何らかの距離概念を設定し得る（数学的な距離空間に写像し得る）ことが多い。例えば、静止画像データでは、２次元的に配列されている画素データ間に空間的な距離がある。さらに、動画像データでは、複数のフレームにおける同一画素位置に着目すると、時間間隔を距離概念として設定することが可能である。同様に、例えば音声データや株価データでは、時間を距離として捉えることができる。このようなデータは、従来より、データ圧縮（データ符号化）の対象となっており、データ圧縮においては、従来より良く知られているように、可逆圧縮方式（Lossless）と非可逆圧縮方式（Lossy）とがある。
【０００３】
例えば、静止画像データに関する可逆圧縮方式では、画像データの隣接相関の大きさを利用して、予測符号化における参照画素として隣接画素を用いることが行われている。
【０００４】
ところで、撮像素子により撮像された画像データは、下位ビット部分のランダム性が非常に高い。このようなランダム性の高いデータは、可逆圧縮する場合に、圧縮率が低下する傾向があることが知られている。従って、撮像素子により撮像された画像データは、そのままでは、高い圧縮率で圧縮するのが困難である。
【０００５】
そこで、例えば特開２００１−６０８７６号公報には、予測符号化を行う前にランダム性の高い下位ビットを分離することにより、圧縮率の向上を図るようにした技術が記載されている。
【特許文献１】特開２００１−６０８７６号公報
【発明の開示】
【発明が解決しようとする課題】
【０００６】
しかしながら、上述したような、空間相関性を利用して可逆圧縮を行う従来の技術では、突発的なノイズや急峻なエッジにおいて、予測が大きく外れることになり、予測誤差が非常に大きくなってしまう。そのために、空間相関性の低い画像（例えば、ランダム性の高い画像）を従来のデータ圧縮装置で圧縮しようとすると、圧縮率が大きく低下してしまうことになる。
【０００７】
また、上記特開２００１−６０８７６号公報に記載されたものでも、上位ビットまでランダム性が存在する画像データについては、圧縮率の向上を図ることは困難である。
【０００８】
本発明は上記事情に鑑みてなされたものであり、ランダム性の高いデータであっても比較的圧縮率を低下させることなく圧縮することが可能なデータ圧縮装置、データ圧縮方法、データ圧縮プログラムを提供することを目的としている。
【０００９】
また本発明は、上記データ圧縮装置、データ圧縮方法、またはデータ圧縮プログラムにより圧縮されたデータを伸張し得るデータ伸張装置を提供することを目的としている。
【課題を解決するための手段】
【００１０】
上記の目的を達成するために、第１の発明によるデータ圧縮装置は、任意の２つの要素データ間に距離を定め得る複数の要素データを含むデータを処理するためのデータ圧縮装置であって、注目要素データの上記距離に関して周辺にある周辺要素データの値に基づいて該注目要素データに対応する予測値を求める予測値演算手段と、上記注目要素データの値と上記予測値との差分に基づいて該注目要素データに対応する予測誤差値を演算する予測誤差値演算手段と、上記予測誤差値に所定の演算を施すことにより該予測誤差値に対する修正値を求める修正値演算手段と、上記予測誤差値に相応する値と上記修正値との差分に基づいて修正予測誤差値を求める修正予測誤差値演算手段と、を具備し、上記修正値演算手段は、上記周辺要素データに対して既に演算して得られている修正値と、上記予測誤差値演算手段により演算して得られた注目要素データに対応する予測誤差値と、の実質的な線形結合により表現される値を、注目要素データの予測誤差値に相応する値に対応する修正値として演算するものである。
【００１１】
また、第２の発明によるデータ圧縮装置は、上記第１の発明によるデータ圧縮装置において、上記データが画像データであり、上記要素データは該画像データを構成する画素データである。
【００１２】
さらに、第３の発明によるデータ圧縮装置は、上記第１の発明によるデータ圧縮装置において、上記修正予測誤差値演算手段が、上記予測誤差値に相応する値を、該予測誤差値の下位ｎ（ｎは１以上の整数）ビットを０とした値とするものであるとともに、該予測誤差値の下位ｎビット分のデータを別途出力するものである。
【００１３】
第４の発明によるデータ圧縮装置は、上記第３の発明によるデータ圧縮装置において、上記修正値演算手段が、上記周辺要素データに対して既に演算して得られている修正値Ｃi-1 （ｉは０以上の整数）と上記予測誤差値演算手段により演算して得られた注目要素データに対応する予測誤差値Ｐi との実質的な線形結合を、上記周辺要素データに対して既に演算して得られている修正値Ｃi-1 を下位側へｎビットシフトさせた値と上記予測誤差値演算手段により演算して得られた注目要素データに対応する予測誤差値Ｐi を下位側へｎビットシフトさせた値との１以上２n未満の整数である係数ａ，ｂを用いた線形結合により、
2006211155.tif 000003
のように表現し（ここに、右辺の括弧は床関数を表す）、この値Ｃi を、注目要素データの予測誤差値に相応する値に対応する修正値とするものである。
【００１４】
第５の発明によるデータ圧縮方法は、任意の２つの要素データ間に距離を定め得る複数の要素データを含むデータを処理するためのデータ圧縮方法であって、注目要素データの上記距離に関して周辺にある周辺要素データの値に基づいて該注目要素データに対応する予測値を求める予測値演算ステップと、上記注目要素データの値と上記予測値との差分に基づいて該注目要素データに対応する予測誤差値を演算する予測誤差値演算ステップと、上記予測誤差値に所定の演算を施すことにより該予測誤差値に対する修正値を求める修正値演算ステップと、上記予測誤差値に相応する値と上記修正値との差分に基づいて修正予測誤差値を求める修正予測誤差値演算ステップと、を含み、上記修正値演算ステップは、上記周辺要素データに対して既に演算して得られている修正値と、上記予測誤差値演算ステップにより演算して得られた注目要素データに対応する予測誤差値と、の実質的な線形結合により表現される値を、注目要素データの予測誤差値に相応する値に対応する修正値として演算するステップである。
【００１５】
第６の発明によるデータ圧縮プログラムは、コンピュータに任意の２つの要素データ間に距離を定め得る複数の要素データを含むデータを処理させるためのデータ圧縮プログラムであって、コンピュータに、注目要素データの上記距離に関して周辺にある周辺要素データの値に基づいて該注目要素データに対応する予測値を求める予測値演算ステップと、上記注目要素データの値と上記予測値との差分に基づいて該注目要素データに対応する予測誤差値を演算する予測誤差値演算ステップと、上記予測誤差値に所定の演算を施すことにより該予測誤差値に対する修正値を求める修正値演算ステップと、上記予測誤差値に相応する値と上記修正値との差分に基づいて修正予測誤差値を求める修正予測誤差値演算ステップと、を実行させるためのプログラムであり、上記修正値演算ステップは、上記周辺要素データに対して既に演算して得られている修正値と、上記予測誤差値演算ステップにより演算して得られた注目要素データに対応する予測誤差値と、の実質的な線形結合により表現される値を、注目要素データの予測誤差値に相応する値に対応する修正値として演算するステップである。
【００１６】
第７の発明によるデータ伸張装置は、任意の２つの要素データ間に距離を定め得る複数の要素データを含むデータを処理することにより得られたデータであって、注目要素データの上記距離に関して周辺にある周辺要素データの値に基づいて該注目要素データに対応する予測値を求め、上記注目要素データの値と上記予測値との差分に基づいて該注目要素データに対応する予測誤差値を演算し、上記周辺要素データに対して既に演算して得られている修正値と上記演算により得られた注目要素データに対応する予測誤差値との実質的な線形結合により表現される値を注目要素データの予測誤差値に相応する値に対応する修正値として演算し、上記予測誤差値に相応する値と上記修正値との差分に基づいて求められた修正予測誤差値、を処理するためのデータ伸張装置であって、既に求められた上記周辺要素データに対応する予測誤差値に相応する値に基づき上記修正値を求めこの修正値と注目要素データに対応する上記修正予測誤差値とに基づき注目要素データに対応する予測誤差値に相応する値を求める予測誤差値演算手段と、既に求められた上記周辺要素データに対応する要素データの値に相応する値に基づき予測値に相応する値を求める予測値演算手段と、上記予測値に相応する値と上記予測誤差値に相応する値との和に基づいて要素データの値に相応する値を求める要素データ値演算手段と、を具備したものである。
【００１７】
第８の発明によるデータ伸張装置は、任意の２つの要素データ間に距離を定め得る複数の要素データを含むデータを処理することにより得られたデータであって、注目要素データの上記距離に関して周辺にある周辺要素データの値に基づいて該注目要素データに対応する予測値を求め、上記注目要素データの値と上記予測値との差分に基づいて該注目要素データに対応する予測誤差値を演算し、上記周辺要素データに対して既に演算して得られている修正値と上記演算により得られた注目要素データに対応する予測誤差値との実質的な線形結合により表現される値を注目要素データの予測誤差値に相応する値に対応する修正値として演算し、上記予測誤差値の下位ｎ（ｎは１以上の整数）ビットを０とした値と上記修正値との差分に基づいて求められた修正予測誤差値と、該予測誤差値の下位ｎビット分のデータと、を処理するためのデータ伸張装置であって、既に求められた上記周辺要素データに対応する予測誤差値に相応する値に基づき上記修正値を求めこの修正値と注目要素データに対応する上記修正予測誤差値とに基づき上記予測誤差値の下位ｎビットを０とした値を求め該予測誤差値の下位ｎビットを０とした値と該予測誤差値の下位ｎビット分のデータの値との和を演算することにより予測誤差値を求める予測誤差値演算手段と、既に求められた上記周辺要素データに対応する要素データの値に基づき予測値を求める予測値演算手段と、上記予測値と上記予測誤差値との和に基づいて要素データの値を求める要素データ値演算手段と、を具備したものである。
【発明の効果】
【００１８】
本発明のデータ圧縮装置、データ圧縮方法、データ圧縮プログラムによれば、ランダム性の高いデータであっても比較的圧縮率を低下させることなく圧縮することが可能となる。
【００１９】
また本発明のデータ伸張装置によれば、上記データ圧縮装置、データ圧縮方法、またはデータ圧縮プログラムにより圧縮されたデータを良好に伸張することが可能となる。
【発明を実施するための最良の形態】
【００２０】
以下、図面を参照して本発明の実施の形態を説明する。
【００２１】
［実施形態１］
図１から図１１は本発明の実施形態１を示したものであり、図１はデータ圧縮装置の構成を示すブロック図、図２はデータ伸張装置の構成を示すブロック図である。
【００２２】
図１に示すように、データ圧縮装置１は、予測値演算手段たる予測値生成部２と、予測誤差値演算手段たる予測誤差値生成部３と、修正値演算手段たる修正値生成部４と、修正予測誤差値演算手段たる修正予測誤差値生成部５と、符号化パラメータ生成部６と、エントロピー符号化部７と、を含んで構成されている。このデータ圧縮装置１の詳細については、後で図３等を参照しながら作用に沿って説明する。
【００２３】
また、このデータ圧縮装置１により圧縮されたデータは、図２に示すようなデータ伸張装置１１により伸張されるようになっている。すなわち、データ伸張装置１１は、復号化部１２と、予測誤差値演算手段たる予測誤差値生成部１３と、予測値演算手段たる予測値生成部１４と、要素データ値演算手段たる画素値生成部１５と、符号化パラメータ生成部１６と、を含んで構成されている。このデータ伸張装置１１の詳細については、後で図４等を参照しながら作用に沿って説明する。
【００２４】
次に、図３はデータ圧縮装置１による圧縮処理を示すフローチャート、図５はデータ圧縮装置１による処理の対象となる画素データを示す図、図６はデータ圧縮装置１により算出される修正予測誤差値を示す図である。
【００２５】
まず、処理対象とする画素データ（データ圧縮装置１への入力データ）が、図５に示すようなものであるとする。すなわち、２次元状をなす画像データの例えば１ライン分に着目したときに、左から右へ向かってｘ0 ，ｘ1 ，…，ｘi ，ｘi+1 となっているものとする。
【００２６】
着目画素の画素値を予測したものである予測値Ｒi は、このような画素データの空間相関性に基づいて、予測値生成部２により、例えば次の数式１に示すように求められる（ステップＳ１）。 
［数１］
2006211155.tif 000004
【００２７】
なお、ここでは左側に隣接する画素値を、着目画素の予測値としたが、これに限るものではないことは勿論であり、着目画素よりも前に読み出される画素であって、着目画素に空間的（ここでは２次元空間的）な距離が近接する画素であれば、任意の１以上の画素の画素データを用いて予測値を算出することが可能である。
【００２８】
次に、予測誤差値生成部３が、実際の画素値と予測値との差分である予測誤差値Ｐi を、次の数式２に示すように算出する（ステップＳ２）。 
［数２］
2006211155.tif 000005
【００２９】
さらに、修正値生成部４が、次の数式３に示すように、予測誤差値Ｐi の下位ビット（ここでは、最下位の１ビット）を落とす（０にする）ことにより、変換予測誤差値Ｐ'iを算出する。 
［数３］
2006211155.tif 000006
ここに、数式３の右辺における括弧は、いわゆる床関数であって、括弧内の数を超えない最大の整数を表している。なお、この括弧は、以下でも同様のものとして用いることにする。このような処理を行うのは、予測誤差値Ｐi の下位ビットはランダム性が高いために、分離して別途処理した方が圧縮効率が高くなるためである。
【００３０】
続いて、修正値生成部４は、変換予測誤差値Ｐ'iを用いて、次の数式４に示す漸化式により修正値Ｃi を算出する（ステップＳ３）。 
［数４］
2006211155.tif 000007
【００３１】
数式５を見れば分かるように、修正値Ｃi は、変換予測誤差値Ｐ'iをほぼ半分の割合で含むとともに、その漸化式の構造により、変換予測誤差値Ｐ'i-1をほぼ１／４の割合，変換予測誤差値Ｐ'i-2をほぼ１／８の割合，…でそれぞれ含んでいる。従って、修正値Ｃi は、着目画素から離れるほど小さい割合で変換予測誤差値Ｐ' （ひいては、予測誤差値Ｐ）を含むものとなっており、隣接画素からのみ算出される予測誤差値を、周辺の複数画素の画素値から算出するように修正するためのものであると考えることができる。
【００３２】
また、修正予測誤差値生成部５は、数式３において予測誤差値Ｐi からビット落ちした予測誤差下位ビットＰＬi を、次の数式５に示すように算出して、エントロピー符号化部７へ出力する。 
［数５］
2006211155.tif 000008
【００３３】
さらに、修正予測誤差値生成部５は、次の数式６に示すように、変換予測誤差値Ｐ'iから修正値Ｃi を減算することにより、修正予測誤差値Ｐ"i（図６参照）を算出する（ステップＳ４）。 
［数６］
2006211155.tif 000009
【００３４】
修正値Ｃi は、上述したように複数の画素に係る予測誤差値Ｐの情報を含むものとなっているために、修正予測誤差値Ｐ"iも、複数の画素に係る予測誤差値Ｐの情報を含むものとなる。従って、予測誤差値Ｐに代えてこの修正予測誤差値Ｐ"iを用いることにより、空間相関の低い画像データ（例えば、ランダム性の高い画像データなど）が入力されたときにも、値が大きくなって圧縮率が低下するのを防ぐことができると期待される。
【００３５】
次に、符号化パラメータ生成部６は、修正予測誤差値Ｐ"iを符号化するための符号化パラメータを生成し、エントロピー符号化部７へ出力する（ステップＳ５）。
【００３６】
エントロピー符号化部７は、符号化パラメータ生成部６からの符号化パラメータに基づいて、修正予測誤差値Ｐ"iと予測誤差下位ビットＰＬi とを例えばロスレス（損失なし）に符号化し、圧縮データとして出力する（ステップＳ６）。
【００３７】
続いて、図７はデータ圧縮装置１により画素値から修正予測誤差値を算出するまでの各値を示す図表、図８は画素値と予測誤差値と修正予測誤差値とを示す線図である。
【００３８】
図７および図８は、０〜２０までの２１個の画素位置に、図８の黒い四角に示すような比較的なだらかな変化をする画素値がある場合の、上述したような処理による、各値の算出例を示している。
【００３９】
このような画素データの例において、従来の圧縮方式においてエントロピー符号化の対象となる予測誤差値は、図８の白い四角（□）に示すようなデータとなる。これに対して、本実施形態の圧縮方式においてエントロピー符号化の対象となる修正予測誤差値は、図８の×印に示すようなデータとなる。画素位置が０である部分を除いてこれらを比較すると、予測誤差値は最小値が０、最大値が２０であって、最大振幅が２０となるのに対して、修正予測誤差値は最小値が−５、最大値が５であって、最大振幅が１０と半減している。こうして、圧縮対象となるデータの分散が小さくなっているために、より効率的な圧縮を行い得ると期待できる。
【００４０】
次に、図４はデータ伸張装置１１による伸張処理を示すフローチャート、図９はデータ伸張装置１１による処理の対象となる修正予測誤差値を示す図、図１０はデータ伸張装置１１により算出される画素データを示す図である。
【００４１】
データ伸張装置１１は、処理を開始すると、入力された圧縮データをまず復号化部１２により復号化する（ステップＳ７）。これにより、修正予測誤差値Ｐ" と予測誤差下位ビットＰＬとが復号化される。
【００４２】
続いて、予測誤差値生成部１３が、修正予測誤差値Ｐ" と予測誤差下位ビットＰＬとを用いて、予測誤差値Ｐi を生成する（ステップＳ８）。
【００４３】
すなわち、予測誤差値生成部１３は、まず、次の数式７を用いて、変換予測誤差値Ｐ'iを算出する。 
［数７］
2006211155.tif 000010
ここに、数式７の右辺における修正値Ｃi-1 は、既に算出されている変換予測誤差値Ｐ'i-1と、既に算出されている修正値Ｃi-2 と、を用いて、上述した数式４により算出される。
【００４４】
その後、予測誤差値生成部１３は、次の数式８を用いて、数式７により算出した変換予測誤差値Ｐ'iと、予測誤差下位ビットＰＬi と、に基づき予測誤差値Ｐi を算出する。 
［数８］
2006211155.tif 000011
【００４５】
次に、予測値生成部１４が、既に算出されているｘi-1 を用いて、上記数式１により、予測値Ｒi を生成する（ステップＳ９）。
【００４６】
そして、画素値生成部１５が、次の数式９により、予測値Ｒi と予測誤差値Ｐi とに基づき、画素値ｘi を算出する（ステップＳ１０）。 
［数９］
2006211155.tif 000012
【００４７】
こうして算出された画素値ｘi がデータ伸張装置１１からの出力データになるとともに、符号化パラメータ生成部１６にも入力されて、符号化パラメータの生成に用いられる（ステップＳ１１）。符号化パラメータ生成部１６により生成された符号化パラメータは、復号化部１２へ出力されて復号処理に用いられるようになっている。
【００４８】
続いて、図１１はデータ伸張装置１１により修正予測誤差値と予測誤差下位ビットとに基づき画素値を算出するまでの各値を示す図表である。
【００４９】
上述したような数式に基づいて、修正予測誤差値と予測誤差下位ビットとに基づき、画素値が算出される。また、図１１の２重線から下に示すように、既に算出された画素値に実質的に基づき、次の画素値の算出に必要な修正値が算出される（ただし、実際には上述したように、数式７の右辺を算出する際に必要な修正値Ｃi-1 は、既に算出されている変換予測誤差値Ｐ'i-1と、既に算出されている修正値Ｃi-2 と、を用いて、上述した数式４により算出可能である。）。
【００５０】
データ伸張装置１１により算出された図１１の画素値を、図７に示した圧縮前の画素値と比較してみると、完全に復号化されていることが分かる。すなわち、上述したようなデータ圧縮装置１を用いることにより可逆圧縮が行われ、該可逆圧縮されたデータが上述したようなデータ伸張装置１１を用いることにより、ロスレスに伸張される。
【００５１】
なお、上述した数式３においては、予測誤差値Ｐの最下位の１ビットを０にして予測誤差値Ｐ' を算出するようにしているが、より一般にはこれに限らず、下位の複数ビットを落とす（０にする）ことが可能である。このときには、数式３に代えて、次の数式１０を用いることになる。 
［数１０］
2006211155.tif 000013
【００５２】
そして、この場合の上記数式４に対応する式は、次の数式１１に示すようになる。 
［数１１］
2006211155.tif 000014
ここに、係数ａ，ｂは、１以上２n未満の整数である。なお、係数ａ，ｂは、１以上２n未満の範囲内でそれぞれ独立に任意に設定することが可能であるが、例えばａ＋ｂ＝２nとなるように制限を課すことも考えられる。
【００５３】
また、数式１１の右辺第１項の床関数部分は、変換予測誤差値Ｐ'iを下位側へｎビットシフトさせた値であるが、これは、数式１０から、注目画素データに対応する予測誤差値Ｐi を下位側へｎビットシフトさせた値と等しいことが分かる。さらに、数式１１の右辺第２項の床関数部分は、周辺画素データに対して既に演算して得られている修正値Ｃi-1 を下位側へｎビットシフトさせた値である。
【００５４】
そして、このような、より一般化した圧縮処理を行う場合には、復号化処理においても、これらの数式に対応するより一般化した数式を用いることは勿論である。
【００５５】
加えて、画像データは、撮像素子によって撮像することにより得られた画像データであっても良いし、コンピュータグラフィックス等により作成された画像データであっても勿論構わない。
【００５６】
また、上述では、処理対象となるデータとして、画像データを例に挙げたが、データ圧縮装置１やデータ伸張装置１１により処理し得るデータは、これに限るものではない。例えば、音声データ、気象観測データ、実験計測データ、株価データなど（これらは、例えば時間を距離とすることができる。あるいは、空間的に分布するデータであれば、該空間における距離を定めることができる。）も処理対象にすることが可能である。このように、本実施形態の圧縮処理および伸張処理は、要素データ間に距離を定め得る任意のデータに対して、広く適用することができる。
【００５７】
そして、上述では、修正予測誤差値と予測誤差下位ビットとを出力して可逆圧縮や可逆伸張を行うようにしているが、本発明は可逆方式にのみ適用されるものではなく、例えば予測誤差下位ビットの出力を省略するようにすれば、本発明を非可逆方式にも適用し得ることが分かる。このときには、データ伸張時の変換予測誤差値が、予測誤差値に相応する値となる。従って、従って、この予測誤差値に相応する値に基づいて画素値を求めるための演算を行うと、その結果として得られるのは画素値に相応する値となる。
【００５８】
そして、上述では、データ圧縮装置１やデータ伸張装置１１により処理を行っているが、既存の演算器等にデータ圧縮方法やデータ伸張方法を適用することにより処理するようにしても構わない。あるいは、上記データ圧縮装置１やデータ伸張装置１１と同等の処理を行うためのデータ圧縮プログラムやデータ伸張プログラムにより、コンピュータで処理させるようにしても良い。
【００５９】
このような実施形態１によれば、ランダム性の高いデータであっても、比較的圧縮率を低下させることなく圧縮し、あるいは該圧縮データを伸張することが可能となる。さらに、予測誤差下位ビットを出力することにより、可逆圧縮方式を構成することが可能となり、元のデータを完全に復元することができる。
【００６０】
また、変換予測誤差値の算出を、予測誤差値を２nで除算する演算に基づき行っているために、コンピュータ等においてビットシフトで算出することが可能となり、高速な処理を行うことができる。
【００６１】
そして、修正値の算出を、既に得られている修正値と、変換予測誤差値と、の実質的な線形結合により算出するようにしているために、コンピュータ等において高速な処理を行うことが可能となる。
【００６２】
なお、本発明は上述した実施形態に限定されるものではなく、発明の主旨を逸脱しない範囲内において種々の変形や応用が可能であることは勿論である。
【産業上の利用可能性】
【００６３】
本発明は、任意の２つの要素データ間に距離を定め得る複数の要素データを含むデータを処理するためのデータ圧縮装置、データ圧縮方法、データ圧縮プログラム、データ伸張装置に好適に利用することができる。
【図面の簡単な説明】
【００６４】
【図１】本発明の実施形態１におけるデータ圧縮装置の構成を示すブロック図。
【図２】上記実施形態１におけるデータ伸張装置の構成を示すブロック図。
【図３】上記実施形態１のデータ圧縮装置による圧縮処理を示すフローチャート。
【図４】上記実施形態１のデータ伸張装置による伸張処理を示すフローチャート。
【図５】上記実施形態１のデータ圧縮装置による処理の対象となる画素データを示す図。
【図６】上記実施形態１のデータ圧縮装置により算出される修正予測誤差値を示す図。
【図７】上記実施形態１のデータ圧縮装置により画素値から修正予測誤差値を算出するまでの各値を示す図表。
【図８】上記実施形態１における画素値と予測誤差値と修正予測誤差値とを示す線図。
【図９】上記実施形態１のデータ伸張装置による処理の対象となる修正予測誤差値を示す図。
【図１０】上記実施形態１のデータ伸張装置により算出される画素データを示す図。
【図１１】上記実施形態１のデータ伸張装置により修正予測誤差値と予測誤差下位ビットとに基づき画素値を算出するまでの各値を示す図表。
【符号の説明】
【００６５】
１…データ圧縮装置
２…予測値生成部（予測値演算手段）
３…予測誤差値生成部（予測誤差値演算手段）
４…修正値生成部（修正値演算手段）
５…修正予測誤差値生成部（修正予測誤差値演算手段）
６…符号化パラメータ生成部
７…エントロピー符号化部
１１…データ伸張装置
１２…復号化部
１３…予測誤差値生成部（予測誤差値演算手段）
１４…予測値生成部（予測値演算手段）
１５…画素値生成部（要素データ値演算手段）
１６…符号化パラメータ生成部
代理人    弁理士      伊    藤      進
【図１】
2006211155.tif 000016
【図２】
2006211155.tif 000017
【図３】
2006211155.tif 000018
【図４】
2006211155.tif 000019
【図５】
2006211155.tif 000020
【図６】
2006211155.tif 000021
【図７】
2006211155.tif 000022
【図８】
2006211155.tif 000023
【図９】
2006211155.tif 000024
【図１０】
2006211155.tif 000025
【図１１】
2006211155.tif 000026