ウェーブレット(wavelet)とは、1 つの関数 $\psi$ を 2 倍ずつ縮め整数ずつずらした関数 $\psi_{j,k}(x)=2^{j/2}\psi(2^jx-k)$ で信号を展開する方法である。多重解像度解析(閉部分空間の増加列 $V_j$ と、整数平行移動が $V_0$ の正規直交基底になる尺度関数 $\varphi$ で、和集合の稠密性・共通部分が $0$・2 倍の伸縮の条件を満たすもの)のウェーブレットについて、$\{\psi_{j,k}\}$ は $L^2(\mathbb{R})$ の正規直交基底になる。尺度方程式の有限なフィルタを使う高速ウェーブレット変換は、長さ $N$ の信号を $O(N)$ 回の掛け算で分解・再構成する。滑らかな部分の係数は速く小さくなるので、信号・画像の圧縮と雑音の除去に使う。
ウェーブレット(wavelet)は、1 つの関数 $\psi$ を 2 倍ずつ縮め、整数ずつずらして作った関数の族
$$
\psi_{j,k}(x)=2^{j/2}\psi(2^jx-k)\qquad(j,k\in\mathbb{Z})
$$
で信号を展開する方法である。$j$ は 尺度(解像度)、$k$ は 位置 を表す。Fourier級数 の $e^{2\pi inx}$ は全区間に広がっているので、局所的な跳びや尖りが全ての係数に影響する。これに対し $\psi_{j,k}$ は長さ $2^{-j}$ ほどの区間に集中しているので、信号の滑らかな部分では係数が小さく、跳びの近くの少数の係数だけが大きくなる。この性質が、信号・画像の圧縮と雑音の除去に使われる。
計算の中心は、関数の積分をいちいち計算しない 高速ウェーブレット変換 である。尺度方程式と呼ばれる有限個の係数 $a_k$ の関係から、細かい尺度の係数を 2 つずつまとめて粗い尺度の係数と詳細の係数を作る。長さ $N$ の信号を $O(N)$ 回の掛け算で変換でき、同じ回数で元に戻せる。
この記事では、多重解像度解析の定義から $\{\psi_{j,k}\}$ が $L^2(\mathbb{R})$ の正規直交基底になることを証明し、Haar ウェーブレットを完全に計算する。続いて高速変換の公式と計算量を証明し、Daubechies のウェーブレットの存在を主張として述べる。
$L^2(\mathbb{R})$ の内積を $\langle f,g\rangle=\int_{\mathbb{R}}f\bar g\,dx$、ノルムを $\lvert f\rvert_2=\langle f,f\rangle^{1/2}$ と書く。関数 $f$ に対し $f_{j,k}(x)=2^{j/2}f(2^jx-k)$ とおく。$x\mapsto f(2^jx-k)$ の $2^{j/2}$ 倍なので $\lvert f_{j,k}\rvert_2=\lvert f\rvert_2$ である。
$L^2(\mathbb{R})$ の閉部分空間の列 $\cdots\subset V_{-1}\subset V_0\subset V_1\subset\cdots$ と関数 $\varphi\in L^2(\mathbb{R})$ の組が 多重解像度解析(multiresolution analysis)であるとは、次が成り立つことをいう。
多重解像度解析に対し、$\psi\in W_0$ で $\{\psi(\cdot-k)\}_{k\in\mathbb{Z}}$ が $W_0$ の正規直交基底になるものを、この多重解像度解析の ウェーブレット(正規直交ウェーブレット)という。係数 $d_{j,k}=\langle f,\psi_{j,k}\rangle$ を $f$ の ウェーブレット係数 という。
$V_j$ は「解像度 $2^{-j}$ で見える関数」の空間、$W_j$ は解像度を $2^{-j}$ から $2^{-j-1}$ に上げたときに新しく見える「詳細」の空間である。条件 2 は条件 3・4 から従うことが知られている(Kna16 Proposition 10.15、p. 469)。一方、条件 1 は別に確かめる必要がある。
この記事の公式を使える条件をまとめる。
$V_j$ を $2^j$ 倍に伸び縮みさせる写像を $D_jf(x)=2^{j/2}f(2^jx)$ と書く。$D_j$ は $L^2(\mathbb{R})$ のユニタリ作用素で、$D_j^{-1}=D_{-j}$ である。
$\{V_j\}$ と $\varphi$ を多重解像度解析、$\psi$ をそのウェーブレットとする。このとき $\{\psi_{j,k}\}_{j,k\in\mathbb{Z}}$ は $L^2(\mathbb{R})$ の正規直交基底であり、任意の $f\in L^2(\mathbb{R})$ について
$$
f=\sum_{j\in\mathbb{Z}}\sum_{k\in\mathbb{Z}}\langle f,\psi_{j,k}\rangle\psi_{j,k}\qquad(L^2\text{ の収束})
$$
である。さらに各 $J$ について $\{\varphi_{J,k}\}_k\cup\{\psi_{j,k}\}_{j\ge J,\,k}$ も $L^2(\mathbb{R})$ の正規直交基底である。
1. 各尺度の基底。 条件 3 を繰り返すと $D_jV_0=V_j$ である。$D_j$ はユニタリなので、$V_0\subset V_1$ の中での直交補空間を $V_j\subset V_{j+1}$ の中での直交補空間に写す。すなわち $D_jW_0=W_j$ である。$\psi_{j,k}=D_j\bigl(\psi(\cdot-k)\bigr)$ なので、$\{\psi_{j,k}\}_k$ は $W_j$ の正規直交基底である。同様に $\{\varphi_{j,k}\}_k$ は $V_j$ の正規直交基底である。
2. 尺度の違うものは直交する。 $j< j'$ なら $W_j\subset V_{j+1}\subset V_{j'}$ で、$W_{j'}$ は $V_{j'}$ と直交する。よって $W_j\perp W_{j'}$ で、$\{\psi_{j,k}\}_{j,k}$ は正規直交系である。
3. 有限の分解。 $V_{j+1}=V_j\oplus W_j$(直交直和)を $j=I,\dots,J-1$ について繋ぐと、$I< J$ について
$$
V_J=V_I\oplus W_I\oplus W_{I+1}\oplus\cdots\oplus W_{J-1}
$$
である。これを有限の分解と呼ぶ。
4. 完全性。 $f$ が全ての $\psi_{j,k}$ と直交するとする。$P_J$ を $V_J$ への直交射影とする。有限の分解と $f\perp W_j$ から、$I< J$ なら $P_Jf=P_If$ である。したがって $g:=P_Jf$ は $J$ によらず、全ての $I$ について $g\in V_I$ である。条件 2 により $g=0$ である。すなわち $f$ は全ての $V_J$ と直交し、条件 1 によりそれらの和集合は稠密なので $f=0$ である。正規直交系の完全性から展開の式を得る(正規直交基底)。
5. 片側の基底。 $\{\varphi_{J,k}\}_k\cup\{\psi_{j,k}\}_{j\ge J,k}$ が正規直交系であることは 1・2 と $V_J\perp W_j$($j\ge J$)による。$f$ がこの全てと直交すれば、$P_Jf=0$ と 3 の有限の分解から全ての $J'>J$ で $P_{J'}f=0$ となり、4 と同様に $f=0$ である。$\square$
$P_J$ は「解像度 $2^{-J}$ での近似」である。$Q_j$ を $W_j$ への射影として、有限の分解は
$$
P_Jf=P_0f+Q_0f+Q_1f+\cdots+Q_{J-1}f
$$
と書ける。粗い近似に、尺度ごとの詳細を順に足していく式である。
$\varphi=\mathbf{1}_{[0,1)}$、$\psi=\mathbf{1}_{[0,1/2)}-\mathbf{1}_{[1/2,1)}$ とし、$V_j$ を「各区間 $[k2^{-j},(k+1)2^{-j})$ の上で定数である $L^2$ の関数」の空間とする。
上の $\{V_j\}$ と $\varphi$ は多重解像度解析で、$\psi$ はそのウェーブレットである。したがって $\{\psi_{j,k}\}$ は $L^2(\mathbb{R})$ の正規直交基底である。
$V_j$ は閉部分空間で増加し、条件 3 は定義から明らかである。条件 4:$f\in V_0$ は $f=\sum_kf(k)\varphi(\cdot-k)$ と書け、$\varphi(\cdot-k)$ の台は互いに交わらず、それぞれノルム $1$ である。
条件 1:連続で台がコンパクトな関数 $g$ は $L^2(\mathbb{R})$ で稠密である。$g$ の台が $[-M,M]$ に入るとき、$g_j$ を各区間 $[k2^{-j},(k+1)2^{-j})$ の上で $g$ の左端の値をとる階段関数とすると、$g_j\in V_j$ で、$g$ の一様連続性から $\sup\lvert g-g_j\rvert\to0$、台は $[-M-1,M+1]$ に入るので $\lvert g-g_j\rvert_2\to0$ である。
条件 2:$f$ が全ての $V_j$ に入れば、$j\to-\infty$ として $f$ は $[0,2^{-j})$ の上で定数、すなわち $[0,\infty)$ の上で定数である。同様に $(-\infty,0)$ の上でも定数で、2 乗可積分なので $f=0$ である。
$W_0$:$f\in V_1$ は区間 $[k,k+\frac12)$ で値 $\alpha_k$、$[k+\frac12,k+1)$ で値 $\beta_k$ をとる。$\langle f,\varphi(\cdot-k)\rangle=\frac12(\alpha_k+\beta_k)$ なので、$f\perp V_0$ は全ての $k$ で $\beta_k=-\alpha_k$ と同値で、このとき $f=\sum_k\alpha_k\psi(\cdot-k)$ である。$\psi(\cdot-k)$ は台が交わらずノルム $1$ なので、$W_0$ の正規直交基底である。最後の主張は thm-wv-onb による。$\square$
区間 $[0,1)$ に制限した同じ系は Haar関数系 で扱われている(Kna16 Theorem 10.4、p. 444 も参照)。
以下、$\varphi$ は実数値とする。$\varphi\in V_0\subset V_1$ で $\{\varphi_{1,k}\}_k$ は $V_1$ の正規直交基底なので、$a_k=\langle\varphi,\varphi_{1,k}\rangle$ とおくと
$$
\varphi(x)=\sum_{k}a_k\sqrt2\,\varphi(2x-k)
$$
である。これを 尺度方程式 といい、$(a_k)$ を 尺度フィルタ(低域フィルタ)という。Haar の場合は $a_0=a_1=\frac1{\sqrt2}$ で、$\varphi(x)=\varphi(2x)+\varphi(2x-1)$ である。
$(a_k)$ が有限個を除いて $0$ のとき、次が成り立つ。
3 から示す。尺度方程式の $x$ を $2^{j-1}x-k$ に替えて $2^{(j-1)/2}$ を掛けると
$$
\varphi_{j-1,k}(x)=\sum_la_l2^{j/2}\varphi(2^jx-2k-l)=\sum_la_l\varphi_{j,2k+l}(x)
$$
である。1:3 で $j=1$ とすると $\varphi(\cdot-m)=\varphi_{0,m}=\sum_la_l\varphi_{1,2m+l}$ で、$\{\varphi_{1,n}\}$ は正規直交なので
$$
\delta_{m,0}=\langle\varphi_{0,m},\varphi_{0,0}\rangle=\sum_{l,l'}a_la_{l'}\langle\varphi_{1,2m+l},\varphi_{1,l'}\rangle=\sum_la_la_{2m+l}
$$
である。2:尺度方程式を積分すると、$\int\varphi(2x-k)\,dx=\frac12\int\varphi\,dx$ なので $\int\varphi=\frac{\sqrt2}{2}\bigl(\sum_ka_k\bigr)\int\varphi$ で、$\int\varphi\ne0$ で割ればよい。$\square$
1 を全ての $m$ について足すと、左辺は $\sum_la_l\sum_ma_{l+2m}$ なので、偶数番の和 $E=\sum_ka_{2k}$ と奇数番の和 $O=\sum_ka_{2k+1}$ について $E^2+O^2=1$ である。2 の $E+O=\sqrt2$ と合わせると $(E-O)^2=2(E^2+O^2)-(E+O)^2=0$ なので、$E=O=\frac1{\sqrt2}$ である。
ウェーブレットはフィルタから作れる。$b_k=(-1)^ka_{1-k}$(ウェーブレットフィルタ、高域フィルタ)とおき
$$
\psi(x)=\sum_kb_k\sqrt2\,\varphi(2x-k)
$$
と定めると、$\psi$ はこの多重解像度解析のウェーブレットである(Kna16 Theorem 10.10、p. 456。そこで $\nu(y)=1$ と選んだ $\psi$ を $1$ だけ平行移動し、符号を替えたもの)。Haar の場合は $b_0=\frac1{\sqrt2}$、$b_1=-\frac1{\sqrt2}$ で、$\psi(x)=\varphi(2x)-\varphi(2x-1)$ である。prf-wv-filter の 3 と同じ計算で $\psi_{j-1,k}=\sum_lb_l\varphi_{j,2k+l}$ が成り立つ。
$c_{j,k}=\langle f,\varphi_{j,k}\rangle$(近似係数)、$d_{j,k}=\langle f,\psi_{j,k}\rangle$(詳細係数)とする。フィルタは実数で、有限個を除いて $0$ とする。
| 量 | 式 | 使える条件 | 根拠 |
|---|---|---|---|
| 尺度方程式 | $\varphi(x)=\sum_ka_k\sqrt2\,\varphi(2x-k)$、$a_k=\langle\varphi,\varphi_{1,k}\rangle$ | 多重解像度解析 | 節「尺度方程式とフィルタ」 |
| フィルタの直交性 | $\sum_la_la_{l+2m}=\delta_{m,0}$ | 同上 | prop-wv-filter |
| フィルタの和 | $\sum_ka_k=\sqrt2$、$\sum_kb_k=0$ | $\varphi$ が可積分で $\int\varphi\ne0$ | prop-wv-filter とその後の段落($\sum b_k=O-E=0$) |
| ウェーブレットフィルタ | $b_k=(-1)^ka_{1-k}$ | 同上 | Kna16 Theorem 10.10(証明しない) |
| 展開 | $f=\sum_{j,k}d_{j,k}\psi_{j,k}$ | $f\in L^2(\mathbb{R})$ | thm-wv-onb |
| 片側の展開 | $f=\sum_kc_{0,k}\varphi_{0,k}+\sum_{j\ge0}\sum_kd_{j,k}\psi_{j,k}$ | 同上 | thm-wv-onb |
| 分解 | $c_{j-1,k}=\sum_la_{l-2k}c_{j,l}$、$d_{j-1,k}=\sum_lb_{l-2k}c_{j,l}$ | 同上 | prop-wv-fast |
| 再構成 | $c_{j,l}=\sum_k\bigl(a_{l-2k}c_{j-1,k}+b_{l-2k}d_{j-1,k}\bigr)$ | 同上 | prop-wv-fast |
| エネルギー | $\sum_lc_{j,l}^2=\sum_kc_{j-1,k}^2+\sum_kd_{j-1,k}^2$ | 同上 | prop-wv-fast |
| 計算量 | 長さ $N=2^J$ の周期列の $J$ 段の分解で掛け算 $2L(N-1)$ 回 | フィルタ $a,b$ の長さが $L$ 以下 | prop-wv-fast |
| Haar の 1 段 | $c_{j-1,k}=\frac{c_{j,2k}+c_{j,2k+1}}{\sqrt2}$、$d_{j-1,k}=\frac{c_{j,2k}-c_{j,2k+1}}{\sqrt2}$ | Haar | 分解の式で $a_0=a_1=b_0=-b_1=\frac1{\sqrt2}$ |
| Haar 係数の大きさ | $\lvert d_{j,k}\rvert\le\frac M42^{-3j/2}$ | $f$ が台の区間で $C^1$、$\lvert f'\rvert\le M$ | prop-wv-decay |
| Daubechies(位数 2) | $a=\frac1{4\sqrt2}(1+\sqrt3,\,3+\sqrt3,\,3-\sqrt3,\,1-\sqrt3)$ | — | thm-wv-daubechies、ex-wv-d4 |
多重解像度解析のフィルタ $a,b$ が有限個を除いて $0$ のとき、$f\in L^2(\mathbb{R})$ の係数について表の分解・再構成・エネルギーの式が成り立つ。さらに、$a_k,b_k$ が $0$ でない $k$ がそれぞれ $L$ 個以下のとき、長さ $N=2^J$ の周期列 $c_J$ から $c_0,d_0,\dots,d_{J-1}$ を分解の式で求める掛け算の回数は $2L(N-1)$ 以下で、再構成も同じ回数以下である。
分解。 prf-wv-filter の 3 から
$$
c_{j-1,k}=\Bigl\langle f,\sum_la_l\varphi_{j,2k+l}\Bigr\rangle=\sum_la_lc_{j,2k+l}=\sum_la_{l-2k}c_{j,l}
$$
で、$d_{j-1,k}$ も $\psi_{j-1,k}=\sum_lb_l\varphi_{j,2k+l}$ から同じである(和は有限和である)。
再構成。 $P_j$ を $V_j$ への射影、$Q_{j-1}$ を $W_{j-1}$ への射影とすると $V_j=V_{j-1}\oplus W_{j-1}$ から $P_jf=P_{j-1}f+Q_{j-1}f$ で、thm-wv-onb の証明の 1 により
$$
\sum_lc_{j,l}\varphi_{j,l}=\sum_kc_{j-1,k}\varphi_{j-1,k}+\sum_kd_{j-1,k}\psi_{j-1,k}=\sum_l\Bigl(\sum_k\bigl(a_{l-2k}c_{j-1,k}+b_{l-2k}d_{j-1,k}\bigr)\Bigr)\varphi_{j,l}
$$
である。最後の等号では $\varphi_{j-1,k}=\sum_la_{l-2k}\varphi_{j,l}$ と、同じ形の $\psi_{j-1,k}$ の式を代入した。$\{\varphi_{j,l}\}_l$ は正規直交基底なので係数を比べて再構成の式を得る。エネルギーの式は、同じ等式の両辺のノルムを、左辺は $\{\varphi_{j,l}\}$、右辺は正規直交系 $\{\varphi_{j-1,k}\}\cup\{\psi_{j-1,k}\}$ の Parsevalの等式 で計算したものである。
計算量。 長さ $n$ の周期列から、分解の式で長さ $\frac n2$ の周期列 $c_{j-1}$、$d_{j-1}$ を作る。1 つの値に掛け算は $L$ 回以下なので、1 段で $Ln$ 回以下である。$n=N,\frac N2,\dots,2$ について足すと $L(N+\frac N2+\cdots+2)=2L(N-1)$ である。再構成は同じ積を逆向きに足し合わせるので、同じ回数で済む。$\square$
分解の 1 段は「フィルタとの畳み込みをとってから偶数番だけを残す」操作であり、信号処理の言葉では ダウンサンプリングつきのフィルタバンク である(Kna16 §X.11、pp. 532–534)。長さ $N$ の 高速Fourier変換 が $O(N\log N)$ 回の演算を要するのに対し、高速ウェーブレット変換は $O(N)$ 回で済む。
$I=[k2^{-j},(k+1)2^{-j}]$ とし、$f\in L^2(\mathbb{R})$ は $I$ の上で $C^1$ 級で $\lvert f'\rvert\le M$ とする。Haar ウェーブレットについて
$$
\lvert d_{j,k}\rvert\le\frac M4\,2^{-3j/2}
$$
である。$f(x)=x$($L^2(\mathbb{R})$ には入らないが、$d_{j,k}$ は $I$ の上の積分で定まる)のときは $d_{j,k}=-\frac142^{-3j/2}$ で、等号が成り立つ。
$a=k2^{-j}$、$h=2^{-j-1}$ とする。$\psi_{j,k}$ は $[a,a+h)$ で $2^{j/2}$、$[a+h,a+2h)$ で $-2^{j/2}$ なので
$$
d_{j,k}=2^{j/2}\int_0^h\bigl(f(a+t)-f(a+h+t)\bigr)\,dt
$$
である。平均値の定理 から $\lvert f(a+t)-f(a+h+t)\rvert\le Mh$ なので、$\lvert d_{j,k}\rvert\le2^{j/2}Mh^2=\frac M42^{-3j/2}$ である。$f(x)=x$ なら被積分関数は $-h$ で、$d_{j,k}=-2^{j/2}h^2$ である。$\square$
証明で使ったのは $\int\psi=0$ だけである。$\int x^l\psi(x)\,dx=0$($0\le l< N$)のとき $\psi$ は $N$ 個の消えるモーメント をもつという。台がコンパクトで $C^m$ 級の正規直交ウェーブレットは、$0\le l\le m$ のモーメントが消える(Kna16 Proposition 10.47、p. 526)。消えるモーメントが多いほど、滑らかな部分の係数は速く小さくなる。
各整数 $N\ge1$ に対し、実数のフィルタ $a_0,\dots,a_{2N-1}$ で、台がコンパクトな実数値の尺度関数をもつ多重解像度解析を与えるものが存在する。$N=1$ は Haar の場合で、$N$ を大きくとれば尺度関数とウェーブレットは任意に高い階数まで連続微分可能になる。
この記事では証明しない。構成は、尺度フィルタの母関数 $m_0(y)=\frac1{\sqrt2}\sum_ka_ke^{-2\pi iky}$ を $m_0(y)=\bigl(\frac{1+e^{-2\pi iy}}2\bigr)^NL(y)$($L$ は三角多項式)の形に選び、$\lvert L(y)\rvert^2$ が多項式 $\sum_{k=0}^{N-1}\binom{N-1+k}{k}w^k$ に $w=\sin^2\pi y$ を代入したものになるように $L$ を Fejér–Riesz の補題で決めるものである(Kna16 Theorem 10.39、p. 512。フィルタの長さが $2N$ であることは p. 515 の注意 (5)、滑らかさは Corollary 10.46、p. 526)。どの $N$ でも $C^\infty$ 級にはならない(同書 p. 513)。閉じた式はなく、尺度関数の値は尺度方程式を繰り返し使って 2 進点の上で求める(下の図)。
![図: 左は Haar の尺度関数(区間 [0,1) で 1)とウェーブレット([0,1/2) で 1、 1/2,1) で -1)。右は Daubechies の位数 2 の尺度関数(台 [0,3]、x=1 で最大値約 1.366)とウェーブレット(台 [-1,2])で、どちらも連続だが尖った形をしている。
標本値 $f(k2^{-J})$($k=0,\dots,N-1$、$N=2^J$)からウェーブレット係数を求めて加工する手順である。
| 端の扱い | やること | 結果 |
|---|---|---|
| 周期延長 | $c_{j,l+n}=c_{j,l}$ として分解の式の添字を $n$ を法として読む | 正規直交性が保たれる。両端の値が違うと端に大きな詳細係数が出る |
| 0 で延長 | 範囲外を $0$ とする | 係数の個数が段ごとにフィルタの長さ程度ずつ増える |
| 長さが $2$ の冪でない | 必要な段数だけ分解し、余りは $0$ か鏡映で埋める | 段数は $\lfloor\log_2N\rfloor$ 以下 |
$c_3=(4,6,10,12,8,6,5,5)$ を Haar で 3 段分解する。
使う公式:表の「Haar の 1 段」とエネルギーの式。
答え:
| 段 | 近似係数 | 詳細係数 |
|---|---|---|
| $j=2$ | $c_2=\sqrt2\,(5,11,7,5)$ | $d_2=\sqrt2\,(-1,-1,1,0)$ |
| $j=1$ | $c_1=(16,12)$ | $d_1=(-6,2)$ |
| $j=0$ | $c_0=14\sqrt2\approx19.7990$ | $d_0=2\sqrt2\approx2.8284$ |
$\sum c_{3,l}^2=446=392+8+40+6$ で、エネルギーの式が成り立つ。絶対値の大きい 3 個 $c_0,d_0,d_{1,0}$ だけを残して再構成すると $(5,5,11,11,6,6,6,6)$ になり、相対誤差は $\sqrt{10/446}\approx0.1497$ である。
1 段目は隣どうしの和と差を $\sqrt2$ で割る:$(4+6)/\sqrt2=5\sqrt2$、$(4-6)/\sqrt2=-\sqrt2$ など。2 段目は $(5\sqrt2+11\sqrt2)/\sqrt2=16$、$(5\sqrt2-11\sqrt2)/\sqrt2=-6$ など。3 段目は $(16+12)/\sqrt2=14\sqrt2$、$(16-12)/\sqrt2=2\sqrt2$。捨てた係数は $d_{1,1}=2$ と $d_2$ で、その 2 乗和 $4+6=10$ が誤差の 2 乗和に等しい(直交性)。再構成は、残した係数で逆向きに $(c+d)/\sqrt2$、$(c-d)/\sqrt2$ を繰り返す:$c_1=((14\sqrt2+2\sqrt2)/\sqrt2,(14\sqrt2-2\sqrt2)/\sqrt2)=(16,12)$、$c_2=\sqrt2\,(5,11,6,6)$、$c_3=(5,5,11,11,6,6,6,6)$。
Haar 係数を、$f(x)=x$ と跳びのある $g=\mathbf{1}_{[1/3,\infty)}$ で比べる($g$ は $L^2$ に入らないが、各係数は有限区間の積分で定まる)。
使う公式:prop-wv-decay。
答え:$f$ では全ての $k$ で $d_{j,k}=-\frac142^{-3j/2}$($j=2$ で $-0.03125$)。$g$ では $j\ge0$ のとき $\frac13$ を含む区間の係数が $d_{j,k}=-\frac132^{-j/2}$($j=2$、$k=1$ で $-\frac16\approx-0.1667$)で、ほかの $k$ では $0$ である。
$f$ は prf-wv-decay の最後の計算。$g$ について、$\frac13=0.0101\ldots_{(2)}$ なので、$\frac13$ を含む長さ $2^{-j}$ の 2 進区間の左右の半分のうち、$\frac13$ は $j$ が偶数なら左半分、奇数なら右半分に入る($2^j$ を $3$ で割った余りが $1$ か $2$ かによる)。左半分に入るとき、区間の左端から $\frac13$ までの長さは $\frac132^{-j}$ で、$d_{j,k}=2^{j/2}\bigl((\text{左半分のうち }g=1\text{ の長さ})-2^{-j-1}\bigr)=-2^{j/2}\cdot\frac132^{-j}$ である。右半分に入るときは $\frac13$ から区間の右端までの長さが $\frac132^{-j}$ で、左半分の積分は $0$ なので、同じく $d_{j,k}=-2^{j/2}\cdot\frac132^{-j}$ となる($j=0$:$-\frac13$、$j=1$:$-\frac{\sqrt2}6\approx-0.2357$)。跳びを含まない区間では $g$ は定数で、$\int\psi=0$ から係数は $0$ である。
$a_0,\dots,a_3=\frac1{4\sqrt2}(1+\sqrt3,3+\sqrt3,3-\sqrt3,1-\sqrt3)\approx(0.48296,0.83652,0.22414,-0.12941)$ とする。
使う公式:prop-wv-filter、$b_k=(-1)^ka_{1-k}$。
答え:$\sum a_k=\sqrt2$、$\sum a_k^2=1$、$a_0a_2+a_1a_3=0$ で、フィルタの条件を満たす。$b_{-2},\dots,b_1\approx(-0.12941,-0.22414,0.83652,-0.48296)$ について $\sum b_k=0$、$\sum kb_k=0$ である。したがって $c_{j,l}=l$(1 次式の列)の詳細係数は $d_{j-1,k}=\sum_mb_m(2k+m)=0$ となる。Haar では同じ列の詳細係数は全て $-\frac1{\sqrt2}\approx-0.7071$ である。
$\sum a_k=\frac{8}{4\sqrt2}=\sqrt2$。$\sum a_k^2=\frac{(1+\sqrt3)^2+(3+\sqrt3)^2+(3-\sqrt3)^2+(1-\sqrt3)^2}{32}=\frac{4+2\sqrt3+12+6\sqrt3+12-6\sqrt3+4-2\sqrt3}{32}=1$。$a_0a_2+a_1a_3=\frac{(1+\sqrt3)(3-\sqrt3)+(3+\sqrt3)(1-\sqrt3)}{32}=\frac{2\sqrt3-2\sqrt3}{32}=0$。$\sum kb_k=-2b_{-2}-b_{-1}+b_1=-2a_3+a_2-a_0=\frac{-2+2\sqrt3+3-\sqrt3-1-\sqrt3}{4\sqrt2}=0$。
$N=1024=2^{10}$ 個の値を Daubechies の位数 2($L=4$)で 10 段分解する。
使う公式:prop-wv-fast の計算量。
答え:掛け算は $2L(N-1)=8184$ 回である。1 段目が $4\cdot1024=4096$ 回、以後は半分ずつ減る。
各行は、示した主張の仮定を 1 つだけ外す。
| 主張と外す仮定 | 反例 | 成り立たなくなること |
|---|---|---|
| thm-wv-onb:条件 4(整数平行移動が正規直交) | 帽子関数 $\varphi(x)=\max(0,1-\lvert x\rvert)$ と、$2^{-j}\mathbb{Z}$ で折れる連続な折れ線の空間 $V_j$。条件 1〜3 は成り立つ | $\langle\varphi,\varphi\rangle=\frac23$、$\langle\varphi,\varphi(\cdot-1)\rangle=\frac16$。フィルタ $\frac1{\sqrt2}(\frac12,1,\frac12)$ は $\sum a_l^2=\frac34$、$\sum a_la_{l+2}=\frac18$ で prop-wv-filter の 1 が崩れ、分解して再構成しても元の列に戻らない |
| thm-wv-onb:$\psi\in W_0$ | $\psi=\sqrt2\,\varphi(2x)$(Haar の $\varphi$)。$\psi\in V_1$ で、整数平行移動は正規直交 | $\langle\psi_{0,0},\psi_{1,0}\rangle=\frac{\sqrt2}2\approx0.7071$ で、尺度の違うものが直交しない |
| prop-wv-decay:区間の上で $C^1$ | 跳び $\mathbf{1}_{[1/3,\infty)}$ | 係数が $\frac132^{-j/2}$ で、$2^{-3j/2}$ の速さで減らない(ex-wv-decay) |
| prop-wv-decay:$\int\psi=0$ | $\psi$ の代わりに箱 $2^{j/2}\mathbf{1}_{[k2^{-j},(k+1)2^{-j})}$ で内積をとる | 定数 $1$ との内積が $2^{-j/2}$ で、滑らかな関数でも係数が $2^{-3j/2}$ の速さで減らない |
| prop-wv-fast の計算量:フィルタが有限 | Shannon の多重解像度解析:$\varphi(x)=\frac{\sin\pi x}{\pi x}$、$V_0$ は Fourier 変換が $[-\frac12,\frac12]$ に台をもつ関数の空間(Kna16 §X.4、pp. 465–468) | $a_k=\frac{\sqrt2\sin(\pi k/2)}{\pi k}$($a_0=\frac1{\sqrt2}$)で、奇数の $k$ の全てで $0$ でなく $\frac1k$ の速さでしか減らない。打ち切らなければ分解の 1 つの値に無限和が要る |
1 行目の再構成の誤差は、乱数の列(長さ $16$、周期延長)で相対誤差 $0.269$ になる。同じ列を Daubechies の位数 2 で分解・再構成した誤差は $10^{-15}$ 程度である。
| 誤り | 正しくは | なぜ |
|---|---|---|
| 片側の展開で $j\ge0$ の $\psi_{j,k}$ だけを使う | $\varphi_{0,k}$ の項(または $j<0$ の全ての $\psi_{j,k}$)が要る | $\mathbf{1}_{[0,1)}$ は全ての $\psi_{j,k}$($j\ge0$)と直交する(thm-wv-onb の最後の主張) |
| フィルタを $\sum a_k=1$ に正規化したまま直交の式を使う | 直交の式は $\sum a_k=\sqrt2$ の正規化で書いてある | $\sum a_k=1$ の流儀では分解の 1 段で全体に $\frac1{\sqrt2}$ が掛かり、エネルギーの式がずれる |
| 標本値をそのまま $c_{J,k}$ とする | $c_{J,k}\approx2^{-J/2}f(k2^{-J})$ | $\varphi_{J,k}$ の正規化 $2^{J/2}$ を忘れると、全ての係数が $2^{J/2}$ 倍ずれる |
| 周期延長の端の大きな係数を信号の特徴とみなす | 端の係数は延長の継ぎ目による | 両端の値が違えば継ぎ目は跳びで、ex-wv-decay と同じ大きさの係数が出る |
| ウェーブレット係数を Fourier 係数のように周波数だけで読む | $d_{j,k}$ は尺度 $2^{-j}$ と位置 $k2^{-j}$ の 2 つの添字をもつ | 同じ $j$ でも $k$ ごとに値が違うことが局所性である |
$j,k$ を実数に替えた $W_\psi f(s,u)=\int f(x)\lvert s\rvert^{-1/2}\psi\bigl(\frac{x-u}s\bigr)dx$ を 連続ウェーブレット変換 という。$\widehat\varphi(\xi)=\int\varphi(x)e^{-2\pi ix\xi}dx$ と書くと、尺度方程式は $\widehat\varphi(\xi)=m_0(\xi/2)\widehat\varphi(\xi/2)$ の形になる(Kna16 p. 455)。フィルタの $\sqrt2$ の置き方、$b_k$ の平行移動と符号には文献ごとの違いがあるが、$\{\psi_{j,k}\}$ が正規直交基底であることは変わらない。2 次元の画像には、$\varphi(x)\varphi(y)$ と $\varphi\psi$、$\psi\varphi$、$\psi\psi$ の 4 つの積を使う。
多重解像度解析とウェーブレットの構成は Kna16 第 X 章(§X.3、pp. 454–465、Daubechies のウェーブレットは §X.9、pp. 498–515)による。
Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する