(57)【特許請求の範囲】
【請求項１】
大地の特性を表すＮサンプルの一次元アレーｘを圧縮する方法であって、
（a）前記アレーｘをＭのサンプルのブロックに分割する工程（ここで、Ｍ＜Ｎである）と、
（b）各ブロック境界ｌを横切ってサンプルxl(j)≡x(/M+j)を畳み込み演算する工程であって、以下の式、
0003865079.tif 000016
となる式にしたがって行われる工程と、
（c）アレーｙの各ブロック内の畳み込み演算されたサンプルを変換する工程であって、以下の式、
0003865079.tif 000017
となる式にしたがって行われる工程と
（d）アレーｚの各ブロック内の変換されたサンプルを量子化して整数を作る工程と、
（e）前記整数を圧縮されたアレーを表すビット流れに符号化する工程とを含む方法。
【請求項２】
請求項１の方法において、多次元アレーに適用され、前記(a)ブロック、(b)畳み込み演算及び(c)変換工程は、各アレーの次元に沿ってカスケード演算のように適用される方法。
【請求項３】
請求項２の方法において、前記多次元アレーのサブセットは圧縮される方法。
【請求項４】
請求項３の方法において、前記多次元アレーは地震信号を表す方法。
【請求項５】
請求項１の方法において、さらに、工程(a)から(e)までを逆順所に逆転させることによって前記圧縮されたアレーの圧縮を解除する工程を含む方法。
【請求項６】
請求項５の方法において、多次元アレーに適用され、前記(a)ブロック、(b)畳み込み演算及び(c)変換工程の逆工程は、各アレーの次元に沿ってカスケード演算のように適用される方法。
【請求項７】
請求項６の方法において、前記多次元アレーのサブセットの圧縮は解除される方法。
【請求項８】
請求項７の方法において、前記多次元アレーは地震信号を表す方法。
【発明の詳細な説明】
発明の背景
関連出願
本願は１９９７年５月７日に出願した先の出願番号第60/045,915号に基づいて優先権を主張する。
１．発明の分野
本願は概略データ圧縮方法に関し、特に、地震データに適用されるような画像圧縮のためのＪＰＥＧ方法の改良に関する。
２．従来技術の説明
画像圧縮用のＪＰＥＧ規格のアルゴリズム（Pennebaker及びMitchell、1993）は、二次元アレー内のピクセルの８×８の各ブロックに対し実行される以下の３つのステップからなる。
1.離散的コサイン変換を用いてピクセルの８×８ブロックを変換する。
2.変換係数を小さな整数に量子化する（スケール化およびまるめ)。
3.最大頻度の整数をあらわす２，３のビットを用いてビットを符号化する。
圧縮解除アルゴリズムは逆順序にそれらのステップの各々を逆にする。両方のアルゴリズムとも、どのような次元のアレーでも圧縮および圧縮解除できるように容易に拡張することができる。
図１は圧縮されていない地震データの２−Ｄアレーを示す。図１の３２ビット浮動小数点数の２−Ｄアレーは、３−Ｄ地震調査から抽出された定時間スライスである。図２は同一のアレーの拡大された一部を表示する。
図３は同一の拡大された一部を示しており、それは、ＪＰＥＧに類似のアルゴリズムを用いて２−Ｄアレー全体を圧縮および圧縮解除した後のものである。全体のアレーに対する圧縮比は約１０３：１で、それは、３２ビット浮動少数点数の元のアレーが、圧縮されたアレーの約１０３倍のビットを含んでいたことを意味する。
そのような大きな圧縮比の場合には、このＪＰＥＧに類似のアルゴリズムは図３に見えるようなブロッキングアーティファクトを生成する。低圧縮比では、ブロック間のそれらの不連続点はほとんど見えなくなるが、それらは、特に、圧縮解除後に処理またはインタプリテーションがさらに実行されるときに依然として際立つであろう。
図３に現れたアーティファクトは、ブロック間に連続性を維持する試みがなされない場合に、８×８のサンプルのブロックの各々を独立的に圧縮および圧縮解除したときの結果である。
これらのアーティファクトにもかかわらず、そのようなデータの小さなサブセットを圧縮および圧縮解除する能力は望ましい特徴である。特に、それにより、アレー全体の圧縮を解除することなく、圧縮された大きなアレーのいくつかの小さな部分にアクセスすることができる。また、それにより、圧縮アルゴリズムが、データ振幅およびスペクトルにおける空間的変形に適応することができる。これらの特徴は、ウェーブレット変換（例えば、Bradley他、1993、Wickerhauser、1994）に基づく圧縮方法には欠けている。本願で検討した課題は、ブロッキングアーティファクトを持つことなく、それらの特徴を得ようとするものである。
この課題の１つの解決方法は、ブロックの重なりを用いることによりデータを圧縮することで、それにより、圧縮解除されたサンプル値を、ブロックの境界の近くの値を参照することなく、計算することができることになる。この解決方法は、３−ＤメディカルイメージのボリュームレンダリングへＪＰＥＧアルゴリズムを適合する際に、Yeo及びLiuによって用いられた（1995)。残念ながら、ブロックの重なりの使用は、圧縮すべきブロックの数を増加させることになり、それにより、計算時間が増加し、圧縮比が小さくなる。
３．本願発明で引用した従来の実施の参考文献
Bradley, J. N., C. M..,及びHopper, T., 1993,グレースケールの指紋イメージ圧縮のためのFBIウエーブレット・スカラー量子化基準、ビジュアル情報処理II、SPIE処理、293-304(ftp://ftp.c3.lanl.gov/WSQ)
Jawerth, B.,及びSweldens, W., 1995,二直交スムースローカル三角法ベース、J. Fourier Anal. Appl., 2(http:/cm.bell-labs.com/who/wim.papers/-papers.html)
Jawerth, B., Liu, Y.,及びSweldens, W., 1996,スムースローカル三角法ベースhttp://cm.bell-labs.com/who/wim/papers/-papers.html.
Malvar, H.S.,及びStaelin, D.H., 1989,効果を阻止することのないLOT−変換コード化、IEEE、Transaction on Acoustic, Speech, and Signal Processing、37、no.4,553-559
Malvar, H.S., 1990,効率的変換/サブバンドコード化、IEEE、Transaction on Acoustic, Speech, and Signal Pmcessing、38、no.6,969-978
Pennebaker, W.B.,及びMitchell, J.L., 1993, JPEG still image datta compression standard, Van Nostrand Reinhold
Princen, J.P.,及びBradley, A.B., 1956,時間ドメインエイリアシングキャンセルに基づく分解/統合フィルターバンクデザイン、IEEE、Transaction on Acoustic, Speech, and Signal Processing、34、no.5, 1153-1161
Wickerhauser, M.V, 1994、理論からソフトウエアまで適合されたウエーブレット分析、A. K. Peters
Yeo, B.,及びLiu, B., 1995、DCT利用の圧縮3Dスカラーデータのボリュームレンダリング、IEEE Transactiqns on Visualization and Computer Graphics、1、no. 1, 29-43
４．本願発明の目的の識別
本願発明の第１の目的は改良されたＪＰＥＧアルゴリズムをデータ圧縮に適用する点にある。
本願発明の重要な目的は、ブロッキングアーティファクトを生じさせることなく、データの小さなサブセットを圧縮することに用いることのできる改良されたＪＰＥＧデータ圧縮アルゴリズムを提供する点にある。
本願発明は、離散的コサイン変換と、量子化された変換係数のホフマン符号化とのためにＪＰＥＧ方法を用いるデータ圧縮の方法に関する。この方法は、主として、ブロッキングアーティファクトを回避する追加のステップにおいて、また、変換係数の量子化において、標準的なＪＰＥＧ方法を改良するものである。
【図面の簡単な説明】
図１は３−Ｄ地震調査から抽出された定時間スライスであり、そこでの表示は圧縮されていない３２ビット浮動小数点数の２−Ｄアレーである。
図２は図１の２−Ｄアレーの拡大された一部である。
図３は、ＪＰＥＧアルゴリズムの直接の適用による圧縮及び圧縮解除の後の図２のデータを示しており、それは、ブロッキングアーティファクトと、独立して圧縮された８×８のサンプルブロックの間の不連続点を表す。
図４は、ブロッキングアーティファクトを抑制するように設計されたＪＰＥＧに類似のアルゴリズムによる圧縮及び圧縮解除後の図２のデータを示す。
図５は、長さ３２の逆ＤＣＴ−IIIに対応するマトリクスＣIII-1を示しており、そこでは、ブラックピクセルは正の値に対応し、ホワイトピクセルは負の値に対応する。
図６は、ブロック長さ８を持つ、ブロック化された逆ＤＣＴ-IIIに相当するマトリクスを示す。
図７は、図６におけるブロック化された逆ＤＣＴ-IIIからの列１１及び１９を示す。ここでＪＰＥＧ圧縮でのブロッキングアーティファクトは、サンプル１５と１６の間に見られるような不連続によって発生し、以下の式(1c)によって規定される関数b(j)における不連続のため各コサインの第１サンプルはこの図にプロットされている曲線から少し離れている。
図８は、図７に表示された切り詰められたコサインを逆畳み込み演算することによって得られた滑らかな漸減するコサインを示しており、それらは図９の逆畳み込み演算されたＤＣＴ-IIIマトリクスの列１１及び１９である。
図９は、逆畳み込み演算されたＤＣＴ-IIIに対応するマトリクスを示しており、そこでは、このマトリクスの列はブロックからブロックへと重なり、このマトリクスは、それらの列の重み付けられた合計がブロッキングアーティファクトを表さないようにゼロまで滑らかに漸減する値を持つ。
図１０は、ブロック化された逆ＤＣＴ-IIIを逆畳み込み演算するために用いられた演算に対応するマトリクスを示しており、そこでは、図９に示すマトリクスはこのマトリクスと図６に表示されたものとの積に等しい。
図１１は、ＤＣＴブロックの境界を横切るサンプル値のペアで行う組合せ及び置き換えである逆畳み込み演算を示しており、また、そこでは畳み込み演算はこの演算の逆である。
図１２は、ブロックＡ内で強調されたサンプルの圧縮を解除するためのステップを示しており、それは、ブロックＡ、Ｂ及びＤを最初に復号、逆量子化及び逆ＤＣＴ-IIIし、次に、４つの強調されたサンプルを逆畳み込み演算し、そこでは畳み込み演算及び逆畳み込み演算はＤＣＴブロック境界を横切ってペアで行うサンプルの混合である。
本願発明の望ましい実施例の詳細な説明
本願発明はＪＰＥＧに類似のアルゴリズムを用いて圧縮を行うときに隣り合うデータの混合に基づきデータ圧縮をおこなう改良されたデータ圧縮方法に関する。ＪＰＥＧに類似のデータ圧縮は、多くの著者によってさまざまな形式で説明されている（例えば、Prince及びBradley 1986、Malvar及びStaelin 1989、Malvar 1990、Wickerhauser 1994、Jawerth他1995)。ＪＰＥＧに類似のデータ圧縮の利点は、それが圧縮比を高め、計算時間をわずかにしか増加させないという点にある。
図４は、図１の２−Ｄアレーからの同一のサブセットを表示しており、それは、以下に説明する本願発明の方法に基づいて第２のＪＰＥＧに類似のアルゴリズムを用いて圧縮し、そして圧縮解除した後のものである。全体のアレーに対する圧縮比は約１１２：１である。それらの圧縮解除されたデータにはブロッキングアーティファクトは存在しない。
従来のＪＰＥＧに類似のアルゴリズムと本願発明に係る新たなＪＰＥＧに類似のアルゴリズムとの間の違いは、ＪＰＥＧ規格で指定されたブロック化された離散的コサイン変換の改良の中に見出される。本願発明におけるアルゴリズムの改良によりブロッキングアーティファクトが減衰するが、従来のＪＰＥＧに類似のアルゴリズムの望ましい特徴は維持する。
離散的コサイン変換
従来のＪＰＥＧ圧縮に用いられた変換は離散的コサイン変換であり、ＤＣＴ-IIと呼ぶ。本願発明によると、異なる離散的コサイン変換を用いており、ＤＣＴ-IIIと呼ぶ。（離散的コサイン変換の一覧に関しては、Wickerhauser、1994、84頁参照）
ＤＣＴ-III
順方向のＤＣＴ-III（順変換）は以下の式によって求められる。
0003865079.tif 000002
また、対応する逆変換は以下のとおりである。
0003865079.tif 000003
ここで、
0003865079.tif 000004
この順変換及び逆変換は、ｚ＝ＣIIIｙ及びｙ＝ＣIII-1ｚの場合のようにマトリクスの掛け算のように表すことができる。ここで、マトリクスＣIIIは以下の要素を持つ。
0003865079.tif 000005
その逆変換マトリクスＣIII-1を図５に示す。Ｍ＝32である。３２の実数のどのベクトルもこのマトリクスの列の重み付け合計として表すことができる。
一次元圧縮アルゴリズムでは、サンプル値のベクトルｙは、マトリクスＣIII-1からの２，３の列だけを用いてその概算値を求めることができる。各列の重みはベクトルｚにおける変換係数によって与えられる。高い圧縮比の場合には、ｚにおける係数の多くは無視でき、ほとんどゼロである。そのような小さな係数はゼロに量子化され、それはわずかなビットを用いて効率的に符号化することができる。
ＪＰＥＧ規格は、一次元ベクトルではなくて、二次元イメージの圧縮について記述する。ＪＰＥＧ圧縮に用いられた従来のＤＣＴ-IIは２−Ｄ変換である。しかし、多次元データの離散的コサイン変換は各データの次元に沿って１Ｄ変換のカスケードとして実行することができるので、簡略化のために１Ｄ変換のみを説明する。
ブロック化されたＤＣＴ-III
地震の追跡のような長いデータのベクトルの場合には、全体のベクトルの単一の離散的コサイン変換では、無視できる値の変換係数が多く生じるとは思えない。従って、ＪＰＥＧと同様に、変換長さがＭ＝８の、ブロック化されたＤＣＴを用い、パッドデータベクトルをゼロに設定し、必要に応じて、８の倍数である長さＮを設定する。ブロック化された逆ＤＣＴ-IIIに相当するマトリクスを図６に示す。そこでは、Ｎ＝３２で、Ｍ＝８である。より圧縮に適合することに加え、そのブロック化された変換はより効率的でもあり、コンピュータ使用コストがデータベクトルの長さＮにしたがって線形的に増えるだけである。
ＪＰＥＧ圧縮に用いられた従来のＤＣＴ-IIと同様に、ＤＣＴ-IIIは、有用な特性を持つ。第１に、ＤＣＴ-IIIは実数を実数に変換するので、複雑なアルゴリズムを必要としない。また、従来のＤＣＴ-IIと同様に、ＤＣＴ-IIIは、ユニタリ変換、つまり、ＣIII-1＝ＣIIITである。［この特性は上記の式(1)に示されている。］図６に対応するブロック化された順方向のＤＣＴ-IIIマトリクスは、そこに表示されたブロック化された逆ＤＣＴ-IIIの転置行列である。
他の有用な特性は、逆ＤＣＴ-IIIが順方向のＤＣＴ-IIと等価である点にある。つまり、ＣIII-1＝ＣIIである。ＤＣＴ-IIIとＤＣＴ-IIとの間の関係と、変換長さＭ＝８の選択とにより、単に順変換及び逆変換を入れ替えることによって、ＪＰＥＧ圧縮に用いられている非常に最適化されたＤＣＴ-IIアルゴリズムを用いることができる。
上記のすべての特性は有用であるが、なぜ単純に従来のＪＰＥＧのＤＣＴ-IIを用いることができないのだろうか。その答えは、ＪＰＥＧ圧縮によって生じるブロッキングアーティファクトを回避するための、ＤＣＴ-IIIの発明により改良がなされたことに見出される。
ブロッキングアーティファクトは、図６に示すマトリクスの列のサブセットのみがベクトルの近似のために用いられるときに現れる。おそらく、例えば、そのようなベクトルが、指数ｋ＝１１及びｋ＝１９を持つ２つの列のみを用いることによって大きく圧縮された場合であろう。図７に示すように、それらの２つの列の重要などのような組合せも、その近似値においてサンプル指数ｊ＝１５とｊ＝１６との間に不連続を生じさせる。そのような不連続は、ＪＰＥＧアルゴリズムを用いて圧縮されたイメージの中に肉眼で見えるようなブロッキングアーティファクトを作る。
畳み込み演算されたＤＣＴ-III
圧縮の際に、ブロック化されたＤＣＴ-IIIを用いることによって引き起こされるアーティファクトを排除するために、図７に示すブロック化されたコサインを、図８に示す滑らかに漸減するコサインと置き換える。図９に示す完全な逆変換マトリクスと図６のブロック化された逆ＤＣＴ-IIIマトリクスとを比較する。各コサインのサンプル数は１６に増えており（端にあるものは除く)、隣り合うブロックのコサインは重なり合い、各コサインは滑らかにゼロまで漸減する。それらのコサインの重み付けされた合計は図７に示された不連続は生じさせない。
これらの漸減するコサインに相当する変換は、「局所的コサイン変換又はラップされた直交変換（Wickerhauser、1994、370頁、図８とWickerhauserの図11.5との間には類似点が存在する）」と呼ばれることがある。ここでは、これらが計算される方法を反映させて、これらの変換を畳み込み演算されたコサイン変換と呼ぶ。特に、本願発明に係る圧縮アルゴリズムに用いられている変換は、畳み込み演算されたＤＣＴ-IIIである。図９に示すマトリクスに対応する逆変換は逆畳み込み演算されたＤＣＴ-IIIと呼ばれる。
畳み込み演算は、高度に最適化され、ブロック化されたＭ＝８のＤＣＴアルゴリズムを用いて、滑らかな漸減する１６サンプルコサインを達成する方法の１つである。Wickerhauser（1994、p.103）は、この方法を、「数名の個人によって無関係に行われた驚くべき観察」というように説明し、続けてその圧縮への応用について議論を進めている。本願発明で圧縮に用いた畳み込み演算はWcherhauserによって説明された多くのものの１つであるが、Jawerth及びSwelderns(1995)並びにJawerth他(1996)の実施の影響を受けたものである。後者の著者は特に圧縮に関連する畳み込み演算の観点を議論している。
畳み込み演算の優れた点及び有効な点は、図９に示す逆畳み込み演算されたＤＣＴ-IIIマトリクスが図１０に示す逆畳み込み演算マトリクスと図６に示すブロック化された逆ＤＣＴ-IIIマトリクスとの積であるという事実から見出される。逆畳み込み演算マトリクスの各行及び列はわずか２つの非ゼロ要素を含むだけなので、逆畳み込み演算のコンピュータ利用コストはブロック化されていない逆ＤＣＴ-IIIのコストにほとんど加わるものではない。
実際、図６、９及び１０に示すマトリクスは、実は構成されることはない。むしろ、演算は、それらのマトリクスによる掛け算と同一の結果を持つサンプル値に実行される。図６のブロック化された逆ＤＣＴ-IIIについては、その演算は、ＪＰＥＧ圧縮の際に用いられる高効率のブロック化された順方向のＤＣＴ-IIアルゴリズムである。図１０の逆畳み込み演算マトリクスについては、その演算は、図１１に示すように、指数ｊ＝８，１６，．．．においてブロック境界を横切るサンプル値のペアで行う混合である。
畳み込み演算は、単なる逆畳み込み演算の逆、同一のサンプル値の別のペアで行う混合である。畳み込み演算及び逆畳み込み演算はブロック境界の周りに集中するので、それらの演算は、シフトされたサンプル値によって簡潔に規定されており、それはｙl(j)＝ｙ（ｌＭ＋ｊ）によって規定されている。そのシンボルｌはブロック指数で、ｊはブロック内サンプル指数である。
そのとき、畳み込み演算は以下のように行われる。
0003865079.tif 000006
逆畳み込み演算は以下のように行われる。
0003865079.tif 000007
ここで、畳み込み演算関数f(j)は以下のように規定される。
0003865079.tif 000008
図８の滑らかな漸減コサイン及び図９のそのようなコサインのマトリクスは、式(3b)を図６に示すマトリクスの列に適用することによって計算されていた。
サンプリングされた値x(j)の順方向に畳み込み演算されたＤＣＴ-IIIは、最初に式(3a)を通じてy(j)を計算し、次に、８サンプルの各ブロックごとに、式(1a)を通じてz(k)を計算することによって決定される。同様に、逆畳み込み演算されたＤＣＴ-IIIは、最初に各ブロックごとに式(1b)を通じてy(j)を計算し、次に、式(3b)を通じてz(j)を計算することによって決定される。
Wickerhauser（1994、p.105)、Jawerth及びSweldens(1995)並びにJawerth他(1996)によって議論されているように、多くの他の、しかし、似たような逆畳み込み演算が可能である。式(3)により規定される逆畳み込み演算は２つの理由により選択される。
第１に、畳み込み演算はユニタリである。図１０に示す逆畳み込み演算マトリクスは、対応する畳み込み演算マトリクス（図示せず）の転置行列である。これを適切に証明するためには、式(3c)の畳み込み演算関数がf2(j)＋f2(-j)＝１を満足することを観察し、次に、式(3a)及び(3b)の畳み込み演算及び逆畳み込み演算を２×２のマトリクスによる掛け算のように表現する必要がある。２×２の畳み込み演算マトリクスを解析的に逆にすると、その逆にしたものはその転置行列と等しく、それは２×２の逆畳み込み演算マトリクスと等しい。従って、全体の逆畳み込み演算はブロック境界を横切るサンプル値のそれらの２×２の混合からなるので、それはユニタリである。
第２に、本願発明に係る畳み込み演算によると、確実に、x(j)＝１のような定数関数が、各ブロックにｋ＝０のみの場合に非ゼロとなる変換係数ｚl(k)を生じさせるので、一定値の（又はゆっくりと変化する）データの圧縮を強めることができる。Jawerth他の用語では、順方向に畳み込み演算されたＤＣＴ-IIIは「定数の分解」を達成する。
畳み込み演出されたＤＣＴ-IIIの第２の特性を証明するためには、式(3a)の畳み込み演算を定数サンプル値xl(j)＝１に解析的に適用し、その解が、
0003865079.tif 000009
であることを証明する必要がある。ここで、ＣIII(k,j)は式(2)によって求められる。言い換えると、その畳み込み演算は、定数サンプル値が、ＤＣＴ-IIIの第１(k=0)のコサインと（スケール係数
0003865079.tif 000010
内で）正確に調和するように畳み込み演算されるよう選択される。このコサインは、その変換の他のすべてのコサインと直交するので、各ブロックにおけるそのk=0変換係数のみが、順方向に畳み込み演算されたＤＣＴ-IIIの後に非ゼロとなる。各非ゼロ係数の値は
0003865079.tif 000011
となる。
より正確に述べると、この特性は最初の及び最後のブロックを除くすべてのブロックに維持されている。最初の及び最後のブロックに対する定数の分解は、畳み込み演算マトリクス及び逆畳み込み演算マトリクスを、それらのコーナーにおいてユニタリでないように修正することによって得られるのではあるが、それらのブロックでより低い圧縮の程度が受け入れられるのならば、厳密なユニタリ畳み込み演算及び逆畳み込み演算が維持される。
ＪＰＥＧ圧縮で用いられるＤＣＴ-IIとの比較
ＪＰＥＧ圧縮で用いられる順方向のＤＣＴ-IIは、ＤＣＴ-IIの第１のコサイン（例えば、図５のマトリクスの第１行）は定数なので、畳み込み演算されることなく定数の分解を達成する。実際に、その特性は、ＤＣＴ-IIIではなくて、ＤＣＴ-IIがＪＰＥＧ圧縮規格に規定されている理由となる。ＪＰＥＧ圧縮の前に畳み込み演算をおこない、ＪＰＥＧ圧縮解除の後に逆畳み込み演算を実行することになるので、標準のＪＰＥＧアルゴリズムを修正することなく、ＤＣＴ-IIによる畳み込み演算の技法を用いることを考慮すればよいと思うかもしれない。
残念ながら、式(3)の畳み込み演算及び逆畳み込み演算はＤＣＴ-IIには適さない。特に、式(3b)は、図８に示すもののようには、滑らかな漸減するコサインを生じさせない。
Jawerth他(1995)は、ＤＣＴ-IIに適合し、さらに定数の分解を維持する、別の畳み込み演算及び逆畳み込み演算について記述している。しかし、それらの演算はユニタリではない。それは実際は条件付けが不十分であり、その結果、ブロック境界の近くに発生するサンプル値における不連続を増大させ、圧縮の効率を減少させる。
それに対し、式(3)の畳み込み演算及び逆畳み込み演算は、式(1)の順方向ＤＣＴ-III及び逆ＤＣＴ-IIIと同様にユニタリである。Ｆが畳み込み演算マトリクスを意味するときには、順方向畳み込み演算されたＤＣＴ-IIIはｚ＝ＣIIIFxのように表すことができ、以下のようになる。
0003865079.tif 000012
言い換えると、畳み込み演算されたＤＣＴ-IIIの後に平方されたサンプル値の合計は、畳み込み演算されたＤＣＴ-IIIの前の合計と等しい。この性質は変換係数を量子化することに起因する圧縮解除データのひずみを推測するために用いることができる。
量子化及び符号化
上記のように、本願発明の圧縮アルゴリズムで用いられた変換は、まさに、ＪＰＥＧ圧縮で用いられるものの逆であるが、ブロッキングアーティファクトを減少するように畳み込み演算が含まれている。用いられている量子化及び符号化方法は、また、ＪＰＥＧ圧縮で用いられているものから作りかえられている。そのＪＰＥＧ方法と本願発明との間の相違点を以下に説明する。
量子化
ＪＰＥＧ圧縮はイメージを対象とするものであるが、圧縮前のデータは８ビット又は１２ビットである。（カラーイメージはサンプルの赤−緑−青の３つのものによって表される。）ＤＣＴ-IIを介しての２−Ｄ変換の後にサンプルごとに最大１１ビットを要求することがあるが、それは、２−ＤのＤＣＴ-IIの後の最大サンプル値が、変換前のものより最大で８倍大きいからである。一般的には、ＤＣＴ-IIの後の最大サンプル値は変換前の最大値のＭD/2倍以下となる。ここで、Ｄは変換された次元の数である。言い換えると、
0003865079.tif 000013
この上方の境界は、データが、一定の第１のコサインＣII(k=0,j)のようなＤＣＴ-IIで用いられるコサインの１つに正確に適合するときに達成される。
同一の因数ＭD/2は、本願発明の圧縮アルゴリズムで用いられる畳み込み演算されたＤＣＴ-IIIにも適用される。従って、畳み込み演算されたＤＣＴ-IIIを用いて８ビット整数データを変換した後に、本願発明の方法は、２−Ｄ圧縮における１１ビットの整数及び３−Ｄ圧縮における１３ビットの整数を量子化及び符号化する。
ＪＰＥＧ圧縮アルゴリズム及び本願発明の方法の両方における量子化ステップは、符号化されるビットの数を減少させるように設定されたスケーリング演算であり、圧縮されてその後圧縮解除されたデータのひずみの原因となるのは、このビット数の減少なのである。そのような損失のある圧縮方法では、そのひずみは高い圧縮比の引き換えとして受け入れられる。
ＪＰＥＧ圧縮では、各ブロック内の変換係数は別々に量子化され、高い波数（空間周波数）は低い波数より少ないビットで表される。ＪＰＥＧ圧縮でのこの波数依存スケーリングは、通常人間の視覚の認識に対し最適化される。
本願発明の圧縮方法では、波数はすべて等しく量子化される。波数に依存するエラーは持ち込まれない。その理由の１つは、地震データの場合、多くの場合高い波数部分に関心が高いという点にある。例えば、地震データを用いて映像化された地表下の断層は高い波数に対応する。他の理由は、地震データは多くの場合人間の視覚系とは別にコンピュータアルゴリズムによって分析されるという点にある。
局所的量子化
８ビットの画像データを圧縮するときには、サンプル値は−１２８と＋１２７との間にあり、また、小さな振幅のデータブロックはほんのわずかで、圧縮により安全に量子化してゼロにできると仮定することができる。ＪＰＥＧ規格は、特に、この仮定を行い、その場合、全体のイメージに対し量子化スケール係数の内の１組のみ用いることを許容する。上述のように、それらのスケール係数はブロック内の異なる係数（異なる波数）に対し変化するが、同一の組がすべてのブロックに用いられる。この場合は、ＪＰＥＧ量子化はグローバルとなる。
３２ビット浮動小数点データを圧縮するときには、ブロックごとに変化するスケール係数を用いて、局所的量子化を実行することが望ましい。そのようなデータを圧縮する前には、最大サンプル振幅|x|maxは知られていないかもしれない、その値を決定するために圧縮前に各サンプルを読むことはコスト的に高くなる。さらに、小さな振幅はわずかであると仮定することは適切ではなく、地震データは、特に、多くの場合、この仮定が有効になる前に多量の処理を必要とする。従って、ブロック内のすべての変換係数を量子化するために単一のスケール係数が用いられるが、スケール係数はブロックごとに変わることがある。特に、上記の式(5)では、|z|maxは各変換されたブロック内の最大係数を表し、異なるスケール係数ｓがブロックごとに計算される。
局所的量子化は、グローバル量子化より小さな圧縮比を生じさせる（サンプルごとにより多くのビットを生成する)。その理由として明白なのは、圧縮されたブロックごとに量子化スケール係数を記憶するために追加のビットが必要となるという点である。その理由として明白であるとまで言えないのは、局所的量子化の方がグローバル量子化よりサンプルをゼロに量子化できる数が少ない点である。従って、本願発明の圧縮アルゴリズムにおいて局所的又はグローバル量子化の一方を選択することが可能である。
局所的量子化は、単一ブロック内での大きなダイナミックレンジを対象としない。例えば、未処理の地震データにおける小さな振幅の反射は大きな振幅の表面波の下に隠れるであろう。大きな振幅のノイズの影響を受けたブロック内では、本願発明の圧縮アルゴリズムは、局所的量子化を用いた場合であっても、小さな振幅の信号をゼロに量子化することができ、それにより、その信号が圧縮後の処理によって回復することはない。従って、大きな振幅ノイズは圧縮前に減衰される。
圧縮された仮想メモリ
仮想メモリは物理的に利用可能なものより大きなメモリの錯覚を与える。この錯覚は最後にアクセスされた他のデータの近くに配置されたデータにアクセスする装置にとってもっとも有効である。そのような装置は優良な照合の場所を持つことになる。
２−Ｄ及び３−Ｄアレーで作動する装置は多くの場合優良な照合の場所を持つ。例えば、地震分析装置は３−Ｄアレーからデータの連続的な２−Ｄスライスを表示することができる。十分な高速の局所的圧縮解除アルゴリズムを持って、サンプルを含むブロックは、全体の３−Ｄアレーの圧縮を解除することなく、オンデマンドでそのようなスライスごとに圧縮解除することができる。本願発明の圧縮アルゴリズムは、特にそのような装置において有用である。
そのような装置の関門は、全体のアレーを圧縮又は圧縮解除することなく、大きなアレーのサブセットを圧縮又は圧縮解除できる性能である。ブロック化されたＤＣＴ-IIに基づいて圧縮する場合には、ＪＰＥＧ圧縮で用いられたものと同様に、その特徴は容易に現れる。特に、単一のサンプルを圧縮解除するためには、そのサンプルを含むブロックを復号化、逆量子化、及び逆ＤＣＴ-IIを行うことが必要なだけである。一旦１つのサンプルに対し圧縮解除を行うと、そのブロックのすべてのサンプルの圧縮解除が実行される。照合の場所を仮定すると、そのブロックでの他のサンプルの圧縮解除のコンピュータ利用のコストは浪費とならない。
本願発明の圧縮アルゴリズムの場合には、畳み込み演算されたＤＣＴ-IIIに基づいて、いくつかの別の実行が必要となる。２−Ｄ圧縮及び図１２に示す８×８サンプルの４つのブロックを考慮する。ブロックＡの黒丸に相当するサンプルの圧縮を解除するためには、(1)４つのすべてのブロック（Ａ，Ｂ，Ｃ及びＤ）を複合化し、逆量子化し、さらに逆ＤＣＴ-IIIを行い、(2)その黒丸に相当する４つのサンプルを逆畳み込み演算する必要がある。ブロック境界を横切る逆畳み込み演算は、ちょうど図１１に示されたようなもので、式(3b)によって記述され、それは最初に一次元に対し実行され、次に、他のものに対し実行される。４つのブロックが必要であるが、一旦ブロックＡのサンプルの圧縮解除が完了すると、隣り合うサンプルの圧縮解除に必要な多くの実行は完了されている。再度、照合の場所を仮定すると、追加の圧縮は浪費とはならない。
本願発明の量子化のステップと３２ビット浮動小数点データを量子化するための必要性からのＪＰＥＧのステップとの間には別の差があり、そのデータは８又は１２ビットの画像データよりかなり大きなダイナミックレンジを持つ。浮動小数点値ｚをＢ＋１ビット(符号ビットを含む)を持つ整数ｉに量子化するために、以下のアルゴリズムが用いられる。
0003865079.tif 000014
ここで、ｓは量子化スケール係数である。オーバーフローを回避するために、|i|＜２Bが必要である。この限定及び式(6)により、そのスケール係数に対し以下の式が導かれる。
0003865079.tif 000015
ここで、∈は浮動イプシロンで、１と等しくない数を得るために、浮動小数点アルゴリズムを用いた、１から減算することができる最小の正の数である。
ホフマン符号化
ＪＰＥＧ圧縮規格は、量子化により作られた整数を符号化する２つの方法、つまり、ホフマン符号化及び算術符号化を許容しており、さらに、他の多くの符号化方法も可能である。そのＪＰＥＧのホフマン符号化は本願発明の圧縮アルゴリズムで用いられるが、それは、その符号化はコンピュータ計算が速く行え、実行が簡単で、かつ自由に利用できるからである。
１つの例外を除いて、そのホフマン符号化及び復号化アルゴリズムは、ＪＰＥＧ仕様書に従っている。ＪＰＥＧ規格は、ＤＣ（k＝0)変換係数の特別の符号化を明記する。ＪＰＥＧ圧縮は、それらのＤＣ係数が多くの場合隣り合うブロックの間で高度に相関関係を持つという事実を活用する。この特別の処理は、２つの理由のため、本願発明に係る方法では用いない。つまり、(1)それは、単一のブロックの圧縮及び圧縮解除を複雑にするブロックとブロックとの依存関係を持ち込み、(2)地震データは典型的には比較的小さなＤＣ係数を持つからである。（小さいが、そのＤＣ係数は、用いられた短いＭ=8変換のため、めったに無視できない。）従って、そのＤＣ係数はまさに、他の（ＡＣ）係数が符号化されたときに符号化される。
局所的圧縮
ＪＰＥＧに類似のアルゴリズムの重要な利点は、多次元アレーの一部を圧縮でき、または、そのすべてを処理することなく用いることができるという点にある。これに対し、ウェーブレット変換（例えば、Bradley他1993、Wickerhauser 1994）に基づく圧縮アルゴリズムはこの特徴を欠く。ＪＰＥＧ規格はその特徴を明確にはサポートしていないが、ＪＰＥＧ圧縮で用いられるブロック化されたＤＣＴ-IIによりそれは実行可能になる。この性能は、畳み込み演算されたＤＣＴ-IIIに基づいて本願発明の圧縮アルゴリズムで活用される。
アレー内のデータの各ブロックは、仮想メモリのページに類似するものとして考えることができる。２−Ｄ圧縮の場合には、各ページは６４＝８×８のサンプルを含み、３−Ｄ圧縮の場合には、各ページは５１２＝８×８×８のサンプルを含むことになる。サンプルは、それらがページに挿入されると圧縮解除され、波数はそれらがページから削除されると圧縮される。未圧縮のページの実行中の組はメモリに維持され、一方、多くのページは圧縮状態及びメモリに又はディスク上に記憶された状態に維持される。（ディスクに記憶されると、ページはI/O効率を高めるように組み合わされる。）実行中の組が十分に大きく、また、本願発明の装置が優良な照合の場所を持つ場合には、各ページの圧縮及び圧縮解除又はそれらの一方の計算機利用のコストは、それらのページ内のほとんどのサンプルのアクセスのすべてにわたって償却されるであろう。
まとめ
本願発明に従ってＪＰＥＧ圧縮アルゴリズムを作り変えると、ほとんどのアルゴリズムを再利用できる。そのＪＰＥＧ方法は、順変換及び逆変換を単に入れ替えることによって、長さ８のＤＣＴに再利用される。ＪＰＥＧ量子化方法は、低い波数の優先的処理を回避するため、さらに、データ振幅のブロックごとの違いを処理するために改良される。また、サンプル値は、順方向のＤＣＴの前に、ブロック境界を横切るように畳み込み演算され、その値は逆ＤＣＴの後に逆畳み込み演算される。その畳み込み演算及び逆畳み込み演算により、ＪＰＥＧアルゴリズムを用いて圧縮されている画像においては肉眼で見える、ブロッキングアーティファクトが抑制される。
本願発明の方法の性能と他のアルゴリズムとを比較するため、性能の２つの有効な測定値は、特定された圧縮比の場合の計算時間及びひずみである。本願発明のアルゴリズムの早い実行についての予備的ベンチマークは有望である。計算時間は、圧縮比の広い範囲に対し、ほぼ半分で、ひずみはほとんどウェーブレット利用のアルゴリズムと同じである(Diller 1997個人的連絡)。計算時間は、ウェーブレット利用の方法の場合よりも本願発明の方法の場合がより短くなると思われる（少ない掛け算及び加算とメモリのいっそうの局所的利用とのためである)。
【図１】
0003865079.tif 000018
【図２】
0003865079.tif 000019
【図３】
0003865079.tif 000020
【図４】
0003865079.tif 000021
【図５】
0003865079.tif 000022
【図６】
0003865079.tif 000023
【図７】
0003865079.tif 000024
【図８】
0003865079.tif 000025
【図９】
0003865079.tif 000026
【図１０】
0003865079.tif 000027
【図１１】
0003865079.tif 000028
【図１２】
0003865079.tif 000029