Wavelet Transforms

目标

首先, 既然是变换, 那么就是从一个域到另一个域, 即如下:

\[f(x) = \sum_k c_{j_0} (k) \varphi_{j_0, k} (x) + \sum_{j=j_0}^{\infty} \sum_k d_j (k) \psi_{j, k}(x), \c_{j_0} = \langle f(x), \varphi_{j_0, k}(x) \rangle, \d_{j} = \langle f(x), \psi_{j, k}(x) \rangle. \\]

或者离散的情况:

\[f(x) = \frac{1}{\sqrt{N}}[\sum_{k} T_{\varphi}(j_0, k) \varphi_{0, 0}(x) + \sum_{j=j_0}^{J-1}\sum_{k=0}^{2^j -1} T_{\psi}(j, k)\psi_{j, k}(x)], \T_{\varphi}(j_0, k) = \langle f(x), \varphi_{0, 0}(x) \rangle = \langle f(x),\varphi_{j_0, k} (x) \rangle = \frac{1}{\sqrt{N}} \sum_{x=0}^{N-1}f(x) \varphi_{j_0, k}^*(x), \T_{\psi}(j, k) = \langle f(x), \psi_{j, k}(x) \rangle = \frac{1}{\sqrt{N}} \sum_{x=0}^{N-1}f(x)\psi_{j, k}^* (x). \]

通过上述的变换, 将\(f\)变换至系数\(c, d, T\).

上面\(\{\varphi, \psi\}\)共同组成正交基(或者书中定义的biorthogonal), 小波变换主要关注的就是下面几个目标:

  1. 迭代的构建正交基;
  2. \(\varphi\)能够提取低频信息, \(\psi\)能够提取高频信息;
  3. 快速变换, 即高效计算\(c, d, T\).

小波变换

Scaling Functions

小波变换的正交基是通过scaling functions引入的, 即如下的scaled and translated functions:

\[\varphi_{j, k}(x) = 2^{j/2}\varphi (2^j x - k), \\]

定义\(V_j\)为固定\(j\)平移\(k\)所张成的空间\(\overline{\mathrm{span}\{\varphi_{j, k}|k \in \mathbb{Z} \}}\), 平方可积的scaling functions 同时需要满足下列的四个条件:

  1. \(\langle \varphi (x) , \varphi(x - k) \rangle, k \not = 0\);
  2. \(V_{-\infty} \subset \cdots \subset V_{-1} \subset V_0 \subset V_2 \cdots \subset V_{+\infty}\);
  3. \(f(x) = 0\)是唯一属于任意空间\(V\)的函数;
  4. \(V_{+\infty} = L^2(\mathbb{R})\).

上面的4个条件的严格叙述还是看书上比较好, 不确定是否就是这样, 我没有看过原论文, 只是按照自己理解来.

对于平方可积函数, 可知:

\[\langle \varphi (x) , \varphi(x - k) \rangle, \Rightarrow \langle \varphi_{j,n} (x) , \varphi_{j, n}(x - k) \rangle, k \not = 0. \]

并由条件二可知:

\[\varphi (x) = \sum_{k \in \mathbb{Z}} h_{\varphi}(k) \sqrt{2} \varphi (2x - k), \]

\(x = 2^j x - n\)代入可知,

\[\varphi_{j, n}(x) = \sum_{k \in \mathbb{Z}} h_{\varphi}(k)\varphi_{j, 2n+k}(x). \]

接着, 根据

\[\langle \varphi_{j, n}(x), \varphi_{j, n}(x-n‘)\rangle = 0, n‘ \not = 0, \]

可知

\[\sum_{k \in \mathbb{Z}} h_{\varphi}(k)h_{\varphi}(k-2n‘) = h_{\varphi} \star h_{\varphi}‘ (2n‘) = 0, n‘ \not = 0\h_{\varphi}‘(k) = h_{\varphi}(-k). \]

注: 这里\(\star\)为卷积符号.

这说明, \(\{h_{\varphi}\}\)偶数个是正交向量组. 其重要意义, 请看refer部分.

Wavelet Functions

既然

\[V_{j} \subset V_{j+1}, \]

那么, 我们可以进而定义正交补\(W_j\)满足:

\[V_{j+1} = V_j \oplus W_j, \]

\[\langle f, g \rangle = 0, \quad \forall f \in V_j, g \in W_j, \]

进一步, 我们可以知道

\[V_{j} = V_{j_0} \oplus W_{j_0} \oplus W_{j_0 + 1} \oplus \cdots \oplus W_{j-1}, \]

\[\langle f, g \rangle = 0, \quad \forall f\in V_i, \forall g \in W_j, i \le j, \\langle f, g \rangle = 0, \quad \forall f\in W_i, \forall g \in W_j, i\not=j. \]

倘若\(W_j\)由下列满足上述4个条件的函数:

\[\psi_{j, k}(x) = 2^{j/2} \psi (2^j x - k), \]

生成, 即

\[W_j := \overline{\mathrm{span}\{\psi_{j, k}| k \in \mathbb{Z}\}}. \]

同样有:

\[\psi (x) = \sum_{k \in \mathbb{Z}} h_{\psi}(k) \sqrt{2} \varphi (2x - k), \\psi_{j, n}(x) = \sum_{k \in \mathbb{Z}} h_{\varphi}(k)\psi_{j, 2n+k}(x). \]

以及

\[\sum_{k \in \mathbb{Z}} h_{\psi}(k)h_{\psi}(k-2n‘) = h_{\psi} \star h_{\psi}‘ (2n‘) = 0, n‘ \not = 0\h_{\psi}‘(k) = h_{\psi}(-k). \]

倘若我们通过

\[\langle \psi_{j, n}(x), \varphi_{j, n}(x - k) \rangle = 0, \]

可以得出

\[\sum_{k \in \mathbb{Z}} h_{\psi}(k)h_{\varphi}(k-2n‘) = h_{\psi} \star h_{\varphi}‘ (2n‘) = 0, n‘ \not = 0.\\]

这说明\(h_{\varphi}(2n)\), 加上\(h_{\psi}(2n)\)能够构成正交基.

二者的联系

实际上, 可以证明(没去找这个证明),

\[h_{\psi}(k) = (-1)^k h_{\varphi}(1-k). \]

以haar小波为例:

\[\varphi(x) = \left \{ \begin{array}{ll} 1 & 0 \le x < 1, \ 0 & \text{otherwise}. \end{array} \right . \]

\[\varphi_{0, k}(x) = \frac{1}{\sqrt{2}}\varphi_{1, 2k}(x) + \frac{1}{\sqrt{2}}\varphi_{1, 2k+1}(x), \]

所以

\[h_{\varphi}(0) = h_{\varphi}(1) = \frac{1}{\sqrt{2}}, \h_{\varphi}(n) = 0, \quad n \not =0 ,1. \h_{\psi}(0) = \frac{1}{\sqrt{2}}, \h_{\psi}(1) = -\frac{1}{\sqrt{2}}, \h_{\psi}(n) = 0, \quad n \not =0 ,1. \]

离散的情形

上面的说明实际上都是在围绕平方可积的函数\(\varphi\)说明的, 在离散的情况下需要特殊的处理(此处只能写点自己的理解了, 不是特别明白). 以haar小波为例:

\[\tilde{\varphi}_{j, k}(x) = \varphi_{j, k}(\frac{x}{N}), \quad x = 0, 1, \cdots, N-1. \]

因为\(\varphi\)的支撑是\([0, 1]\). 以\(N=4\)为例:

\[\left [ \begin{array}{cccc} 1 & 1 & 1 & 1 \ 1 & 1 & -1 & -1 \ \sqrt{2} & -\sqrt{2} & 0 & 0 \ 0 & 0 & \sqrt{2} & -\sqrt{2} \end{array} \right ] \begin{array}{c} \rightarrow \varphi_{0, 0} \ \rightarrow \varphi_{0, 1} \ \rightarrow \varphi_{1, 0} \ \rightarrow \varphi_{1, 1} \ \end{array}. \]

但是需要注意的是, \(h_{\varphi}\)是不变的(既然我们只是等式两边都需要进行相同的变量替换).

只是, 问题是, 如何证明离散后的向量之间依旧能够保持正交关系(应该是需要别的条件吧). 不过幸运的是\(h\)之间的正交关系是保持的.

高效变换

假设我们已经求出\(\{h_{\varphi}, h_{\psi}\}\), 如何快速计算系数:

\[c, d, T. \]

实际上,

\[c_j(k) = \sum_{n} h_{\varphi}(n - 2k) c_{j+1}(n) = c \star h_{\varphi}‘ (2k), \d_j(k) = \sum_{n} h_{\psi}(n - 2k) c_{j+1}(n) = c \star h_{\psi}‘(2k), \T_{\varphi}(j, k) = \sum_{n} h_{\varphi}(n-2k)T_{\varphi}(j+1, n) = T_{\varphi}(j + 1, \cdot) \star h_{\varphi}‘ (2k), \T_{\psi}(j, k) = \sum_{n} h_{\psi}(n-2k)T_{\varphi}(j+1, n) = T_{\varphi}(j + 1, \cdot) \star h_{\psi}‘ (2k). \\]

从上面的公式可以看出, 我们可以从后向前地逐步计算系数. 又

\[[f \star g (0), f \star g (2) \cdots f\star g (2n) \cdots] = [f \star g (0), f \star g (1) \cdots f\star g (n) \cdots]_{2\downarrow}, \]

其中\(2\downarrow\)表示下采样, 即

\[y_{2\downarrow}(n) = y(2n). \]

具体的计算流程便如下图所示:

Wavelet Transforms

从上图可以看出, 我们首先需要知道\(T_{\varphi}(J, k)\), 但是实际上, 我们不会直接计算此, 而是直接从\(f(x)\)中采样. 具体原因见p515 底部, 但是说实话此解释并不是很理解, 这给我的感觉像是脱离了原来的基\(\varphi, \psi\)了. 而且书中给出的例子中, \(\varphi, \psi\)也似乎只有一个计算\(h\)的功能, 这让我对最初的变换的目标产生困惑, 但是暂时还是先不深入了.

我们可以通过下列的操作, 从叶节点回推之前的结果.

Wavelet Transforms

其原理如下:

注意到

\[h \star f (n) = \sum_{k=0}^{N-1} h(n-k) f(k) = a^T_n f, \a(n) = [h(0), h(n-1), \cdots, h(n-N+1)], \]

\[A = [a_0, a_1, \cdots, a_{N-1}] = \left [ \begin{array}{cccc} h(0) & h(1) &\cdots & h(N-1) \ h(-1) & h(0) & \cdots & h(N-2)\ \vdots & \vdots & \ddots & \vdots \ h(1-N) & h(2-N) & \cdots & h(0), \end{array} \right ] [h \star f] = A^T f. \]

定义

\[h‘(n) = h(-n), \]

则有

\[[h‘ \star f] = Af. \]

特别定义\(A_{\varphi}, A_{\psi}\)来特别指明\(h_{\varphi}, h_{\psi}\)所对于的矩阵, \(A_{\varphi_{2n}} = [a_0, a_2, \cdots, a_{2n} \cdots]\) 表示\(A_{\varphi}\)的偶数行, 则

\[[h_{\varphi}‘ \star f]_{2\downarrow} = {A_{\varphi_{2n}}} f, \]

于是:

\[[h_{\varphi} \star [h_{\varphi}‘ \star f]_{2\downarrow 2 \uparrow}] = A_{\varphi_{2n}}^T{A_{\varphi_{2n}}} f, \]

类似地, 有

\[[h_{\psi} \star [h_{\psi}‘ \star f]_{2\downarrow 2 \uparrow}] = A_{\psi_{2n}}^T{A_{\psi_{2n}}} f, \]

\[A^T_{\varphi_{2n}} A_{\varphi_{2n}} +A^T_{\psi{2n}} A_{\psi{2n}}= [A_{\varphi_{2n}}^T, A_{\psi_{2n}}^T] \left [ \begin{array}{cc} A_{\varphi_{2n}}\A_{\psi_{2n}} \end{array} \right ] = I, \]

这就保证了能够恢复\(f\), 这也是为什么需要\(2\downarrow, 2\uparrow\)的原因.

注: 不论\(j\)为多少, $ h \star f = \sum_{k=0}{2J-1}\dots$而不是 \(h \star f = \sum_{k=0}^{2^j-1}\dots\), 个人感觉后者是推不出上面的结果的.

二维的情形

二维考虑可分的情况, 按照下面的基:

\[\phi (x, y) = \varphi(x)\varphi(y), \\psi^H (x, y) = \psi(x)\varphi(y), \\psi^V (x, y) = \varphi(x)\psi(y), \\psi^D (x, y) = \psi(x)\psi(y). \\]

容易证明上面能够构成一组基.
假设

\[f(x, y), \quad x = 0, 1, \cdots, 2^{J_1-1}, y = 0 ,1 ,\cdots, 2^{J_2-1}. \]

为了计算对应的系数, 步骤如下:

Wavelet Transforms

Wavelet Transforms

计算的过程, 实际上就是将逐步采用一维的方式来(既然基是可分的), 第一步, 沿着\(x\)轴, 对每一列采取一维的DWT, 分别得到高频和低频信息, 如上图的阴影部分表示高频部分. 然后再在此基础上, 对于每一行采取一维的DWT, 再区分高频和低频信息. 故\(\phi\)实际上提取的是低频信息, \(\psi^H\)实际上提取的是水平方向的高频信息, \(\psi^V\)提取的是垂直方向上的高频信息, \(\psi^D\)是整体的高频信息(对角).

示例

PyWavelets

import numpy as np
import matplotlib.pyplot as plt
import pywt
from PIL import Image

img = np.array(Image.open("Lenna.jpg").convert(‘L‘))
LL, (LH, HL, HH) = pywt.dwt2(img, ‘haar‘)
fig, axes = plt.subplots(2, 2)
axes[0, 0].imshow(LL, cmap=plt.cm.gray)
axes[0, 1].imshow(LH, cmap=plt.cm.gray)
axes[1, 0].imshow(HL, cmap=plt.cm.gray)
axes[1, 1].imshow(HH, cmap=plt.cm.gray)

Wavelet Transforms

Wavelet Transforms

上一篇:分库分表


下一篇:idea 导入github项目