小波入门（一）

Posted on 2018-04-11 Edited on 2021-10-26 In Algorithm

东西太多，学不过来啊。信号处理这边学到一半，因为项目需要开始接触一些小波。用的是《小波与傅立叶分析（第二版）》，做个简单笔记吧。这次我主要以 Haar 小波为例说明小波的基础知识。

Haar 尺度函数

有两个函数在小波分析中有很重要的作用，即尺度函数 $\phi$ 和小波函数 $\psi$。这两个函数产生一组用于分解和重构信号的函数族。$\phi$ 称为父小波，$\psi$ 称为母小波。Haar 尺度函数定义为

\[\phi(x)=\begin{cases} 1, & \text{if $0 \leq x < 1$} \\ 0, & \text{otherwise} \end{cases}\]

令 $V_0$ 是所有形如$\sum_{k \in Z}a_k \phi(x-k),a_k \in R$的函数组成的空间，$k$ 可在任一有限整数范围内取值。也就是说 $V_0$ 是所有不连续点仅在整数集中的分段常量函数组成的空间。

将 $V_0$ 推广到一般情况，设 $j$ 是一个非负整数，$j$ 级阶梯函数空间表示为 $V_j$，它是由函数集

\[\{...,\phi(2^jx+1),\phi(2^jx),\phi(2^jx-1),...\}\]

在实数域上张成。则 $V_j$ 是分段常量函数空间，其间断点在

\[\{...,-1/2^j,0,1/2^j,...\}\]

注意到我们有一个严格包含关系

\[V_0 \subset V_1 \subset ... V_j \subset V_{j+1}...\]

$V_j$ 包含所有在分辨率为 $2^{-j}$ 下的相关信息，随着 $j$ 的增加，分辨率变得更为精细。$V_j \subset V_{j+1}$ 意味着随着分辨率的提高，不会损失任何信息，这就是为什么使用 $\phi(2^jx)$ 而不是 $\phi(ax)$。

略过证明，我们直接给出定理：函数集 $\{ 2^{j/2}\phi(2^jx-k);k \in Z\}$ 是 $V_j$ 的一个标准正交基。

Haar 小波函数

假设我们的信号内含有尖峰噪声（形状为突然向下的冲激信号再跟上一个突然向上的冲激信号）。有了 $V_j$ 的正交基后只完成了一半的工作，为了解决噪声滤除问题，需要一个孤立属于 $V_j$ 但不属于 $V_{j-1}$ 的尖峰的方法，于是就有了小波函数 $\psi$。将 $V_j$ 分解成 $V_{j-1}$ 及其正交补。我们以 $V_1$ 为例，构造 $\psi$ 的两个关键点

$\psi$ 是 $V_1$ 的成员，所以可表示为 $\phi(x)=\sum_la_l\phi(2x-1),a_l \in R$ （仅有有限个 $a_l$ 非零）
$\psi$ 与 $V_0$ 正交，即 $\int \phi(x) \psi(x-k)dx=0$ 对所有的整数 $k$ 成立

符合以上两点的最简单函数为 $\psi(x)=\phi(2x)-\phi(2x-1)$。可以证明，任一函数

\[f_1=\sum_ka_k\phi(2x-k) \in V_1\]

当且仅当 $a_1=-a_0,a_3=-a_2,...$ 时，与 $V_0$ 正交，即与每个 $\phi(x-l),l \in Z$ 正交。此时

\[f_1=\sum_{k \in Z}a_{2k}(\phi(2x-2k)-\phi(2x-2k-1))=\sum_{k \in Z}a_{2k}\psi(x-k)\]

也就是说，当且仅当 $V_1$ 中某一函数具有 $\sum_ka_k\psi(x-k)$ 形式时（将 $a_{2k}$ 重新标记为 $a_k$），该函数与 $V_0$ 正交。

推广到一般情况，设 $W_j$ 是由形如

\[\sum_{k \in Z}a_k \psi(2^jx-k),a_k \in R\]

的函数构成的空间，设仅有有限个 $a_k$ 非零。则 $W_j$ 是 $V_{j+1}$ 中 $V_j$ 的正交补，即 $V_{j+1}=V_j \oplus W_j$。

推广一下即有 $V_j=W_{j-1} \oplus W_{j-2} \oplus ... \oplus W_0 \oplus V_0$。所以 $V_j$ 中的任一 $f$ 可以唯一地分解为以下和式

\[f=w_{j-1}+w_{j-2}+...+w_0+f_0\]

这里可以注意到，我们需要滤除的噪声信号和 $\psi$ 形状十分相似。这也就是小波处理的一个特性：选用和待处理信号相似的小波能获得更好的效果。

Haar 小波分解

理论

$f$ 可由一阶梯函数 $f_j \in V_j$ ($j$ 足够大)近似，然后把 $f_j$ 分解如下

\[f_j=f_0+w_1+w_2+...+w_{j-1},w_l \in W_l\]

其中 $w_l$ 表示为宽为 $1/2^{l+1}$ 的尖峰。例如，脉宽小于 0.01 的尖峰表示噪声，因为 $2^{-6} > 0.01 > 2^{-7}$，那么任何 $w_j, j \ge 6$ 均表示噪声。将这些项设定为 0，和式的其他部分表示了同原始信号十分相似但没有噪声的信号。为了进行小波分解，我们首先用如下式子近似原信号 $f$

\[f_j(x)=\sum_{l \in Z}a_l \phi(2^jx-l)\]

即是信号在 $x=...,-1/2^j,0,1/2^j,...$ 处的采样。有 $a_l=f(l/2^j),l \in Z$。注意 $l$ 的定义域和原信号定义域直接相关。接下来要把 $\phi(2^jx-l)$ 分解为各个 $W_l(l<j)$ 的分量。注意$\phi$ 父小波，$\psi$ 母小波之间的关系为

\[\begin{split} \phi(2x)=(\psi(x)+\phi(x))/2 \\ \phi(2x-1)=(\phi(x)-\psi(x))/2 \end{split}\]

给出分解的推导。首先是把和式 $f_j(x)=\sum_ka_k\phi(2^jx-k)$ 分解为偶部和奇部

\[f_j(x)=\sum_{k \in Z}a_{2k}\phi(2^jx-2k)+\sum_{k \in Z}a_{2k+1}\phi(2^jx-2k-1)\]

根据$\phi$ 父小波，$\psi$ 母小波之间的关系有

\[\begin{split} \phi(2^jx-2k)=(\psi(2^{j-1}x-k)+\phi(2^{j-1}x-k))/2 \\ \phi(2^jx-2k-1)=(\phi(2^{j-1}x-k)-\psi(2^{j-1}x-k))/2 \end{split}\]

将式子联合起来

\[\begin{split}f_j(x)=&\sum_{k \in Z}a_{2k}(\psi(2^{j-1}x-k)+\phi(2^{j-1}x-k))/2+ \\ &\sum_{k \in Z}a_{2k+1}(\phi(2^{j-1}x-k)-\psi(2^{j-1}x-k))/2 \\ =&\sum_{k \in Z} \left( \frac{a_{2k}-a_{2k+1}}2 \right)\psi(2^{j-1}x-k) + \left( \frac{a_{2k} + a_{2k+1}}2 \right)\phi(2^{j-1}x-k) \\ =&w_{j-1} + f_{j-1} \end{split} \]

这样我们就得到了小波分解的递推公式，根据以上式子，我们就可以将 $f_j$ 分解为

\[f_j=w_{j-1}+w_{j-2}+...+w_0+f_0\]

总结一下

\[\begin{split} f_j=&w_{j-1}+f_{j-1} \\ w_{j-1}=&\sum_{k \in Z}b_k^{j-1} \psi(2^{j-1}x-k) \in W_{j-1} \\ f_{j-1}=&\sum_{k \in Z}a_k^{j-1} \psi(2^{j-1}x-k) \in V_{j-1} \end{split}\]

其中

\[\begin{split} b_k^{j-1}=\frac{a_{2k}^j-a_{2k+1}^j}2 \\ a_k^{j-1}=\frac{a_{2k}^j + a_{2k+1}^j}2\end{split}\]

例子

还是看个例子吧，以书上为例

\[f(x)=2 \phi(4x) + 2 \phi(4x-1) + \phi(4x-2)-\phi(4x-3)\]

此时 $j=2,a_0=2,a_1=2,a_2=1,a_3=-1$

\[\begin{split} f_2(x)=&\left( \frac{a_0-a_1}2 \right)\psi(2^1x)+ \left( \frac{a_2-a_3}2 \right)\psi(2^1 x-1) + \\ &\left( \frac{a_0+a_1}2 \right)\phi(2^1x) + \left( \frac{a_2+a_3}2 \right)\phi(2^1 x-1) \\ =& \psi(2x-1)+2\phi(2x) \\ =& \psi(2x-1)+ \psi(x) + \phi(x) \end{split}\]

Haar 小波重构

理论

至此，我们已经将 $f$ 分解为 $V_0$ 和 $W_{j'}(0 \le j' < j)$ 下的各个分量。如果需要滤除之前提到的噪声，则可以舍弃噪声分量 $W_{j'}$。如果需要数据压缩，幅值较小的分量 $W_{j'}$ 可以丢弃而对原信号没有太大的影响。

根据需要，我们会把某一层的 $b_k^j$ 修改为 $b_k^{j'}$。接下来就需要一个重构算法，使得信号能由 $V_j$ 中基元素构建，有

\[f(x)=\sum_{l \in Z} a_l^j \phi(2^jx-l)\]

根据前述，我们的小波分解为

\[\begin{split} f(x)=f_0(x)+w_0(x)+...+w_{j-1}(x), w_l \in W_l \\ f_0(x)=\sum_{k \in Z}a_k^0 \phi(x-k) \in V_0, w_l= \sum_kb_k^l \psi(2^lx-k) \in W_l\end{split}\]

注意我们有

\[\begin{split} \phi(x)=\phi(2x)+\phi(2x-1) \\ \psi(x)=\phi(2x)-\phi(2x-1)\end{split}\]

所以

\[f_0(x)=\sum_{k \in Z}a_k^0\phi(2x-2k)+a_k^0\phi(2x-2k-1)=\sum_{k \in Z}\hat{a}_l^1\phi(2x-l)\]

\[\hat{a}_l^1=\begin{cases} a_k^0, & \text{if $l=2k$ is even} \\ a_k^0, & \text{if $l=2k+1$ is odd} \end{cases}\]

同样地有

\[w_0(x)=\sum_{l \in Z}\hat{b}_l^1\phi(2x-1)\]

\[\hat{b}_l^1=\begin{cases} b_k^0, & \text{if $l=2k$ is even} \\ -b_k^0, & \text{if $l=2k+1$ is odd} \end{cases}\]

将上式相加

\[f_0(x)+w_0(x)=\sum_{l \in Z}a_l^1 \phi(2x-l)\]

\[a_l^1=\hat{a}_l^1+\hat{b}_l^1 = \begin{cases} a_k^0+b_k^0, & \text{if $l=2k$ is even} \\ a_k^0-b_k^0, & \text{if $l=2k+1$ is odd} \end{cases}\]

以此类推，我们可以得到一般性的结论。设

\[f=f_0+w_0+w_1+...+w_j-1\]

\[f_0(x)=\sum_{k \in Z}a_k^0\phi(x-k) \in V_0, w_{j'}(x)=\sum_{k \in Z}b_k^{j'} \psi(2^{j'}x-k) \in W_{j'}\]

其中 $0 \le j' < j$，那么

\[f(x)=\sum_{l \in Z}a_l^j\phi(2^jx-l) \in V_j\]

$a_l^{j'}$ 根据如下算法，由 $j'=1,j'=2,...,j'=j$ 确定

\[a_l^{j'}=\begin{cases} a_k^{j'-1}+b_k^{j'-1}, & \text{if $l=2k$ is even} \\ a_k^{j'-1}-b_k^{j'-1}, & \text{if $l=2k+1$ is odd} \end{cases}\]

例子

以之前为例子，原函数为

\[f(x)=2 \phi(4x) + 2 \phi(4x-1) + \phi(4x-2)-\phi(4x-3)\]

分解后得到

\[f_2(x)= \psi(2x-1)+ \psi(x) + \phi(x)\]

现在要按照原样重构，$l=0,1,2,3,j'=1,2$

\[\begin{split} a_0^1&=a_0^0 + b_0^0=1+1=2 \\ a_1^1&=a_0^0 - b_0^0 = 1-1=0 \\ a_2^1&=a_1^0 + b_1^0 = 0+0=0\\ a_3^1&=a_1^0 - b_1^0 = 0-0=0\\ a_0^2&=a_0^1 + b_0^1 = 2+0=2 \\ a_1^2&=a_0^1 - b_0^1 = 2-0=2 \\ a_2^2&=a_1^1 + b_1^1 = 0+1=1 \\ a_3^2&=a_1^1 - b_1^1 = 0-1=-1 \end{split}\]

所以有

\[\begin{split} f(x)&=a_0^2 \phi(4x) + a_1^2 \phi(4x-1)+ a_2^2 \phi(4x-2)+ a_3^2 \phi(4x-3) \\ &=2 \phi(4x) + 2 \phi(4x-1) + \phi(4x-2)-\phi(4x-3) \end{split}\]