離散ウェーブレット変換

出典: フリー百科事典『ウィキペディア(Wikipedia)』
移動: 案内検索

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

概要[編集]

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

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

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

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

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

定義[編集]

1レベルの変換[編集]

信号xの離散ウェーブレット変換は、一組のフィルターを通すことによって計算される。

信号は、インパルス応答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によって記述した。

/**
 * 注意:このメソッドは input 配列を破壊する。
 * input.length は2以上の2のべき乗でないといけない。
 */
public static int[] calc(int[] input) {
    int[] output = new int[input.length];

    // length は 2^n で n は1つずつ減っていく
    for (int length = input.length >> 1; ; length >>= 1) {
        for (int i = 0; i < length; i++) {
            int a = input[i * 2];
            int b = input[i * 2 + 1];
            output[i] = a + b;
            output[i + length] = a - b;
        }

        if (length == 1)
            return output;

        // 次の反復のために配列を入れ替える
        System.arraycopy(output, 0, input, 0, length << 1);
    }
}

C言語による、CDF 9/7 ウェーブレット変換 (JPEG-2000で利用) のリフティングを用いた高速な実装は、dwt97.c を参照。

参照[編集]

関連項目[編集]