多重解像度解析

多重解像度解析（たじゅうかいぞうどかいせき、テンプレート:Lang-en-short）とは、2倍毎の解像度のウェーブレットを用いて離散ウェーブレット変換により解析する手法。スケーリング関数で基底展開された信号列を、半分の解像度のスケーリング関数とウェーブレット関数による基底展開の和に分解する。1989年に Stephane G. Mallat が発表した。

本来は異なる物だが、Mathematica や MATLAB をはじめとして、多くのソフトウェアでは多重解像度解析の事を離散ウェーブレット変換と呼んでいる。離散ウェーブレット変換の本来の定義は、離散ウェーブレット変換の項目を参照。

概要

関数 $f_j(x)$ をスケーリング関数 $\varphi$ で展開した上で、

$f_j(x)=\sum _k{c}_k^{(j)}{2}^{j/2}\varphi (2^{j}x-k)=\sum _k{c}_k^{(j)}{\varphi }_{j,k}(x)$

下記のウェーブレット関数 $\psi$ への展開を用いて、

$g_j(x)=\sum _k{d}_k^{(j)}{2}^{j/2}\psi (2^{j}x-k)=\sum _k{d}_k^{(j)}{\psi }_{j,k}(x)$

関数 $f_j(x)$ を異なる解像度（レベル）のウェーブレット関数に展開していく手法を多重解像度解析という。

$f_j(x)=g_{j-1}(x)+g_{j-2}(x)+\cdots +g_{j-m}(x)+f_{j-m}(x)$

下記関数集合が基底関数として使われる。

$\{{\varphi }_{j-m,k}(t),{\psi }_{j-m,k}(t),\cdots ,{\psi }_{j-1,k}(t)\mid k\in 𝐙\}$

スケーリング関数とウェーブレット関数の間にはトゥースケール関係が成立する事が必要である。

トゥースケール関係

以下の関係が成立する場合、トゥースケール関係と呼ぶ。

$\varphi (x)=\sum _{k\in 𝐙}{p}_k\varphi (2x-k)$

$\psi (x)=\sum _{k\in 𝐙}{q}_k\varphi (2x-k)$

$p_k,q_k$ の値はウェーブレット関数ごとに異なる。例えばハールウェーブレットの場合は、$p_0=p_1=q_0=1,q_1=-1$ 。

トゥースケール関係が成立していると、下記の式が成立する。

$\varphi (2x-l)=\frac{1}{2}\sum _{k\in 𝐙}(g_{2k-l}\varphi (x-k)+h_{2k-l}\psi (x-k)),l\in 𝐙$

$\{g_k\},\{h_k\}$ を分解数列と呼ぶ。例えば、直交ウェーブレットの場合、$g_k={\bar{p}}_{-k},h_k={\bar{q}}_{-k}$ 。

分解数列が分かると、$f_j(x)=g_{j-1}(x)+f_{j-1}(x)$ という変形が可能になり、これを再帰的に繰り返すと多重解像度解析になる。

2次元

2次元の場合は、まず、関数 $f_j(x,y)$ をスケーリング関数 $\varphi$ で基底展開する。

$f_j(x,y)=\sum _{k_1}\sum _{k_2}{c}_{k_1,k_2}^{(j)}{2}^j\varphi (2^{j}x-k_1)\varphi (2^{j}y-k_2)=\sum _{k_1}\sum _{k_2}{c}_{k_1,k_2}^{(j)}{\varphi }_{j,k_1}(x){\varphi }_{j,k2}(y)$

${\varphi }_{j,k_1}(x){\varphi }_{j,k_2}(y)$ に対して、

${\varphi }_{j,k_1}(x)$ は ${\varphi }_{j-1,k_1}(x)$ と ${\psi }_{j-1,k_1}(x)$ に分解し、

${\varphi }_{j,k_2}(y)$ は ${\varphi }_{j-1,k_2}(y)$ と ${\psi }_{j-1,k_2}(y)$ に分解し、

合わせて、

$\{{\varphi }_{j-1,k_1}(x){\varphi }_{j-1,k_2}(y),{\varphi }_{j-1,k_1}(x){\psi }_{j-1,k_2}(y),{\psi }_{j-1,k_1}(x){\varphi }_{j-1,k_2}(y),{\psi }_{j-1,k_1}(x){\psi }_{j-1,k_2}(y)\}$

の4つに分解する。そして、${\varphi }_{j-1,k_1}(x){\varphi }_{j-1,k_2}(y)$ を同じように再帰的に分解していく。

結果として、m 回繰り返すと、下記の関数集合が基底関数となる。

$\{{\varphi }_{j-m,k_1}(x){\varphi }_{j-m,k_2}(y)\mid k_1\in 𝐙,k_2\in 𝐙\}\cup \{{\varphi }_{j_1,k_1}(x){\psi }_{j_1,k_2}(y),{\psi }_{j_1,k_1}(x){\varphi }_{j_1,k_2}(y),{\psi }_{j_1,k_1}(x){\psi }_{j_1,k_2}(y)\mid k_1\in 𝐙,k_2\in 𝐙,j-1\le j_1\le j-m\}$

3次元以上も同じ。

フィルタバンクによる表現

1レベルの変換

信号$x$の離散ウェーブレット変換は、一組のフィルターを通すことによって計算される。ここではリフティングスキームではなく1989年に発表された手法を説明する。

下記の関係性を満たす $y_{\mathrm{l}\mathrm{o}\mathrm{w}}[k]$ と $y_{\mathrm{h}\mathrm{i}\mathrm{g}\mathrm{h}}[k]$ を $x[k]$ から計算するのが離散ウェーブレット変換である。j は入力依存の何らかの整数。$\varphi (t)$ はスケーリング関数、$\psi (t)$ はウェーブレット関数。

$\sum _{k}x[k]\varphi (2^{j}t-k)=\sum _k{y}_{\mathrm{l}\mathrm{o}\mathrm{w}}[k]\varphi (2^{j-1}t-k)+\sum _k{y}_{\mathrm{h}\mathrm{i}\mathrm{g}\mathrm{h}}[k]\psi (2^{j-1}t-k)$

最初に入力信号列から $x[k]$ を計算しないといけないが、ハールウェーブレットや Bior2.2 双直交ウェーブレットの場合は、入力信号の解像度と同じ解像度のスケーリング関数を使えば、$x[k]$ = 入力信号列になり、特に計算は不要となる。

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

$y_{\mathrm{l}\mathrm{o}\mathrm{w}}[n]=\sum _{k=-\mathrm{\infty }}^{\mathrm{\infty }}x[k]g[2n-k]$

$y_{\mathrm{h}\mathrm{i}\mathrm{g}\mathrm{h}}[n]=\sum _{k=-\mathrm{\infty }}^{\mathrm{\infty }}x[k]h[2n-k]$

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

フィルタ解析のブロックダイアグラム

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

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

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

$y_{\mathrm{l}\mathrm{o}\mathrm{w}}=(x*g)\downarrow 2$

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

しかしながら、$x*g$の計算の後にダウンサンプリングがあるため、計算に無駄がある。リフティングスキームは、この点を改善している。

多重解像度解析

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

3段階のフィルタバンク

各々のレベルにおいて、低周波と高周波に分解される。$2^n$ の長さの入力信号は、ハールウェーブレットの場合は $n$ のレベルに分解される。他のウェーブレットの場合も、おおよそ $n$ になるが、多少ずれる。

ハールウェーブレットの場合での、32サンプルの信号を例にとる。周波数レンジは0から $f_n$ であり、3レベルまで分解するとすると、以下の表のようになる。

レベル	周波数	係数の数	基底関数
3	$0$ 〜 $f_n/8$	4	${\varphi }_{j-3,k}$
	$f_n/8$ 〜 $f_n/4$	4	${\psi }_{j-3,k}$
2	$f_n/4$ 〜 $f_n/2$	8	${\psi }_{j-2,k}$
1	$f_n/2$ 〜 $f_n$	16	${\psi }_{j-1,k}$

多重解像度解析の周波数領域

リフティングスキーム

1996年に Wim Sweldens が新しい離散ウェーブレット変換の計算方法であるテンプレート:仮リンク（テンプレート:Lang-en-short）を発表した。信号を偶数番目の要素と奇数番目の要素に分け、偶数番目の要素で奇数番目の要素を予測し、予測とのズレを高周波成分とし、残差を低周波成分とする手法である。論文の中で、自由に双直交ウェーブレット関数を定義できること、計算が高速化する事を長所に挙げている。ハールウェーブレットと双直交ウェーブレットを扱える。

定義

閉部分空間の系列 $\{V_j:j\in 𝐙\}\subset L^2(𝐑)$ が次の条件1〜5を満たすとき、${\left\{V_j\right\}}_{j\in 𝐙}$ は多重解像度解析を成すという。$A^c$は$A$ の閉包を表す。

1. $V_j\subset V_{j+1},j\in 𝐙$
2. ${\cap }_{j\in 𝐙}{V}_j=\{0\},({\cup }_{j\in 𝐙}{V}_j{)}^c=L^2(𝐑)$
3. $f(x)\in V_j⟺f(2x)\in V_{j+1}$
4. $f(x)\in V_0$ ならば $f(x-k)\in V_0,\mathrm{\forall }k\in 𝐙$
5. $\varphi (x)\in V_0$ が存在して $\{\varphi (x-k):k\in 𝐙\}$ が $V_0$ においてRiesz基底を成す。すなわち、任意の$f\in V_0$ に対して数列 $\{a_k:k\in 𝐙\}\in l^2$ がただ一つ存在して、$f=\sum _k{a}_k\varphi (x-k)$ と表される。さらに定数 $C_2\ge C_1>0$ が存在して、任意の $\{a_k:k\in 𝐙\}\in l^2$ に対して不等式 $C_1\Vert a{\Vert }_2\le \Vert \sum _j{a}_j\varphi (x-j)\Vert \le C_2\Vert a{\Vert }_2$ が成立する。

最後の条件はより厳しい条件として、

5'. $\varphi (x)\in V_0$ が存在して、$\{\varphi (x-k):k\in 𝐙\}$ が $V_0$ の正規直交基底となる。

が用いられる事も多い。ここではこの条件5'を用いる。

条件1は空間が入れ子になっていることを意味する。条件2は $P_j$ を空間 $V_j$ への直交射影作用素とすると、全ての $f\in L^2(𝐑)$ に対して $\underset{j\to \mathrm{\infty }}{\lim }{P}_{j}f=f$ であることを意味する。条件3は条件1の全ての空間がスケール変換で得られる事を意味する。条件4は平行移動に対して空間が普遍であることを意味する。

閉部分空間の集まりが条件1〜5'を満たすときには、いつでも正規直交ウェーブレット ${\psi }_{j,k}(x)=2^{j/2}\psi (2^{j}x-k)$ による $L^2(𝐑)$ の基底 $\{{\psi }_{j,k}:j,k\in 𝐙\}$ が存在し、$P_{j+1}f=P_{j}f+\sum _{k\in 𝐙}⟨f,{\psi }_{j,k}⟩{\psi }_{j,k}$ が成立する。

プログラム例

Python（ハールウェーブレット）

ハールウェーブレットの離散ウェーブレット変換は下記のテンプレート:仮リンクの数式にて行える。入力を x として、$x_e(z)$ は入力 x の先頭を1番目として偶数番目の要素、つまり、x[1::2]、$x_o(z)$ は奇数番目の要素、つまり、x[0::2]。c が低周波成分（基底関数がスケーリング関数）、d が高周波成分（基底関数がウェーブレット関数）。

$\left(\begin{array}{c}c\\ d\end{array}\right)=\left(\begin{array}{cc}1& 1/2\\ 0& 1\end{array}\right)\left(\begin{array}{cc}1& 0\\ -1& 1\end{array}\right)\left(\begin{array}{c}{x}_e(z)\\ x_o(z)\end{array}\right)$

ハールウェーブレットの離散ウェーブレット変換のソースコードは下記のようになる。入力は x で NumPy の配列で与える。多重解像度解析をしたい場合は、x = c して長さが1になるまで繰り返す。${\varphi }_{n,k}(t)=\sqrt{2^n}\varphi (2^{n}t-k)$ の形の基底関数の係数にしたい場合は、c *= sqrt(2) と d /= sqrt(2) をする。

d = x[0::2] - x[1::2]
c = x[1::2] + d / 2

ハールウェーブレットの逆離散ウェーブレット変換のソースコード。

x[1::2] = c - d / 2
x[0::2] = d + x[1::2]

Python（Bior2.2双直交ウェーブレット）

Bior2.2双直交ウェーブレット（2階Bスプライン、線形スプライン）の離散ウェーブレット変換は下記のリフティングスキームの数式にて行える。$z$ は一つ次の要素、$z^{-1}$ は一つ前の要素を表す。

$\left(\begin{array}{c}c\\ d\end{array}\right)=\left(\begin{array}{cc}1& (z^{-1}+1)/4\\ 0& 1\end{array}\right)\left(\begin{array}{cc}1& 0\\ -(1+z)/2& 1\end{array}\right)\left(\begin{array}{c}{x}_e(z)\\ x_o(z)\end{array}\right)$

Bior2.2の離散ウェーブレット変換のソースコード。配列の境界で足りない分は対称パディングで埋めている。

y = np.pad(x, (4, 2), "symmetric")
d = y[2::2] - (y[1:-2:2] + y[3::2]) / 2
c = y[3:-2:2] + (d[:-1] + d[1:]) / 4
d = d[1:]

Bior2.2の逆離散ウェーブレット変換のソースコード。

x[1::2] = c[1:] - (d[:-1] + d[1:]) / 4
x[0] = 2 * d[0] + x[1]
x[2::2] = d[1:-1] + (x[1:-2:2] + x[3::2]) / 2

Java

もっとも単純な例である。ハールウェーブレットによる多重解像度解析を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);
    }
}

下記コードは上記を逆ウェーブレット変換する。

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

    for (int length = 1; ; length *= 2) {
        for (int i = 0; i < length; i++) {
            int a = output[i];
            int b = output[i + length];
            input[i * 2] = (a + b) / 2;
            input[i * 2 + 1] = (a - b) / 2;
        }

        if (length == output.length >> 1)
            return input;

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

C言語

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

関連項目

• ウェーブレット
• ウェーブレット変換
• 離散ウェーブレット変換