離散ウェーブレット変換

離散ウェーブレット変換（りさんウェーブレットへんかん、Discrete wavelet transform, DWT）は、数値解析や関数解析において、離散的にサンプリングされたウェーブレットを用いたウェーブレット変換である。

概要

最初のDWTは、ハンガリーの数学者アルフレッド・ハールによって示された。 これは、$2^n$の長さを持つ数列が入力されると、隣接した値の差分と和を求めるものである。この処理は再帰的に行われ、和の数列は次の処理の入力となる。最終的には、$2^n-1$の差分値と一つの和の値を得る。

この単純なDWTは、ウェーブレットの一般的な特性を示している。離散ウェーブレット変換の計算量は$O(n)$である。また、この変換は、時間及び周波数の両方の特性をつかむことができる。これら2つの特徴は、FFTと比較した場合のDWTの大きな特徴である。

もっとも一般的な離散ウェーブレット変換は、ベルギーの数学者イングリッド・ドブシーによって証明された(1988年)。この証明では、解像度が以前のスケールの2倍となっていく漸化式によって、もっとも密にサンプリングされたマザーウェーブレットを生成している。彼女の講義資料には、ドブシー・ウェーブレットと呼ばれるウェーブレットファミリーが提供されており、その中の最初のウェーブレットはハール・ウェーブレットである。このあと、これをベースとした多くのウェーブレットが開発された。

離散ウェーブレット変換の別の表現としては、Stationaryウェーブレット変換 （ダウンサンプリングが無い離散ウェーブレット変換）がある。また、関連した変換としては、ウェーブレット・パケットや複素ウェーブレット変換がある。

離散ウェーブレット変換は、科学・工学・数学・計算機科学の分野で数多くの応用が存在する。 顕著な例としては、信号符号化やデータ圧縮などに用いられる。特に画像圧縮に対してはモスキートノイズが理論上ほとんど発生しないため、JPEG 2000のアルゴリズムにも採用されている。

定義

1レベルの変換

信号$x$のDWTは、一組のフィルターを通すことによって計算される。

信号は、インパルス応答が$g$であるローパスフィルタと、同じく$h$であるハイパスフィルタを利用して分解される。得られた出力は、ハイパスフィルタから得たものを詳細係数(detail coefficients)、ローパスフィルタから得たものを近似係数(approximation coefficients)とよぶ。これら2つのフィルタは互いに密接な関係があり、直交ミラーフィルタとして知られたものである。

$y_{\mathrm{low}} [n] = \sum\limits_{k = - \infty }^\infty {x[k] \cdot g[2\cdot n - k]}$

$y_{\mathrm{high}} [n] = \sum\limits_{k = - \infty }^\infty {x[k] \cdot h[2\cdot n - k]}$

次に、半分にダウンサンプリングを行う。

この分解によって、時間解像度は元の信号の半分になり、周波数解像度は2倍となる。これは、ハイゼンベルクの不確定性原理を満たしている。

Block diagram of filter analysis

ダウンサンプリングのオペレータとして$\downarrow$を使う。

$(y \downarrow k)[n] = y[k\cdot n]$

以上の式をまとめると以下のようになる。

$y_{\mathrm{low}} = (x*g)\downarrow 2$

$y_{\mathrm{high}} = (x*h)\downarrow 2$

しかしながら、$x*g$の計算の後にダウンサンプリングがあるため、計算に無駄がある。

Lifting schemeは、この点を改善している。

カスケード計算およびフィルタバンク

この分解は、近似係数を再び分解することによって繰り返される。 これは、異なる時間周波数の局在性を持った部分空間を枝とする二分木によって表すことが出来る。 これはフィルタバンクとして知られているものである。

A 3 level filter bank

各々のレベルにおいて、低周波と高周波に分解される。 $2^n$の長さの入力信号は、$n$のレベルに分解される。

16サンプルの信号を例にとる。周波数レンジは0から$f_n$であり、3レベルまで分解するとすると

Level	Frequencies	Samples
3	$0$ to ${{f_n}}/8$	4
	${{f_n}}/8$ to ${{f_n}}/4$	4
2	${{f_n}}/4$ to ${{f_n}}/2$	8
1	${{f_n}}/2$ to $f_n$	16

Frequency domain representation of the DWT

プログラム例

もっとも単純な例である。 Haar waveletをJavaによって記述した。

   public static int[] invoke(int[] input){
       //WARNING: This will destroy the contents of the input array
       //This function assumes input.length=2^n, n>1
       int[] output = new int[input.length];
       
       for(int length = input.length >> 1; ; length >>= 1){
           //length=2^n, WITH DECREASING n
           for(int i = 0; i < length; i++) {
               int sum = input[i*2]+input[i*2+1];
               int difference = input[i*2]-input[i*2+1];
               output[i] = sum;
               output[length+i] = difference;
           }
           if (length == 1) 
               return output;
           
           //Swap arrays to do next iteration
           System.arraycopy(output, 0, input, 0, length<<1);
       }
   }

References

Stéphane Mallat, A Wavelet Tour of Signal Processing

関連項目

• ウェーブレット変換
• 直交ミラーフィルタ
• en:List of wavelet-related transforms