小波变换 | 离散小波变换

小波变换 离散小波变换

离散小波变换特指那些基于多分辨率分析构建的、具有正交基（如 Daubechies 小波, Haar 小波）或双正交基（如 CDF 小波）的小波变换。

核心算法——Mallat 算法，正是利用了多分辨率分析的内在结构（尺度空间嵌套）和尺度函数/小波函数的双尺度关系（即滤波器组），实现了无冗余（正交基）或低可控冗余（某些双正交），完美重构，计算高效 ($O(N)$) 的小波分解与重构。

因此，从连续小波变换到离散小波变换的“离散化”，不仅仅是参数的离散采样，更重要的是通过引入多分辨率分析理论和设计特定的滤波器组（寻找合适的尺度/小波函数），使得在离散的二进网格上，小波系统具有了正交基或（双）正交基的良好性质，从而克服了简单离散化（如二进小波变换）可能带来的重构困难、冗余过高、计算复杂等问题，实现了真正实用的、高效的小波分析工具。

连续小波变换的参数是连续的，这对于数值计算和存储是不实用的（无穷多个点）。从 连续小波变换到离散小波变换的核心，就是尺度参数 $j$，平移参数 $k$，和时间参数 $t$ 进行离散化。

尺度、平移离散化

对于尺度参数和平移参数，最常见的离散策略是采用二进制（Dyadic）采样，即只考虑 $(a,b)$ 落在如下网格点处的取值：

$$a_j=2^j,b_{j,k}=k\cdot 2^j,j,k\in \mathbb{Z}$$

• 这里不是对 $a$ 进行线性采样，而是按指数规律进行采样。这里选择底数为 2 非常关键，它自然地产生了倍频程关系（尺度翻倍相当于频率减半）。尺度 $2^j$ 对应分析频率是母小波中心频率的 $1/2^j$。
• 而对于 $b$ 来说，不同尺度（频率）下对平移精度的需求不同，波形宽，变化缓慢，不需很细的时间采样间隔。平移步长可较大。波形窄，变化快速，需要较精细的时间采样间隔。平移步长需较小。为保持每个尺度下小波函数的正交性（或至少构成一个框架），平移步长应与尺度成正比，这里引入整数倍数系数 $k$。

基于如下形式，就可以把 $W_f$ 从原本基于 ${\mathbb{R}}^2$ 上 $(a,b)$ 的连续形式。转换成基于索引 $(j,k)$ 的离散形式。

$$W_f(j,k)=W_f(a_j,b_{j,k})=\frac{1}{\sqrt{2^j}}{\int }_{-\infty }^{\infty }f(t)\overline{\Psi (\frac{t-2^{j}k}{2^j})}dt$$

则基函数变为：

$${\Psi }_{j,k}(t)=\frac{1}{\sqrt{2^j}}\Psi (\frac{t-2^{j}k}{2^j})=2^{-j/2}\Psi (2^{-j}t-k)$$

虽然 Dyadic 采样是走向离散化的第一步，但仅仅这一步并不能自动保证其构成紧框架或正交基。传统的连续小波（如墨西哥帽小波）在二进网格下采样后，通常不构成正交基，并且存在冗余（即冗余度 > 1）。它们的重构也比较复杂。

时间参数离散化

当尺度与平移参数被固定为 dyadic 网格 $a_j=2^j,b_{j,k}=k{2}^j$ 之后，仍然需要回答：积分里的时间变量 $t$ 如何离散？

在离散小波变换中，会把信号本身视为有限离散序列：$x[n],n=0,1,\dots ,N-1,N=2^{J_{\max }}$。处理过程中，首先对原始连续信号 $f(t)$ 在区间 $[0,T)$ （这里的时间范围通常是连续的非零值区域）上均匀采样，采样间隔为 ${\Delta }_t=\frac{T}{N}$，从而得到离散序列 $x[n]=f(n{\Delta }_t),n=0,1,\dots ,N-1$ 。

接下来把 $t=n\Delta t$ 代入系数在离散网格上的形式中，用矩形求积近似（这里将 $T$ 设置为 1 来简化运算），则原本的归一化基函数转变为如下形式：

$${\Psi }_{j,k}(t)=\sqrt{2^{-j}}\Psi (2^{-j}t-k)\Rightarrow {\Psi }_{j,k}’[n]=\sqrt{\frac{2^{-j}}{N}}\Psi \left(\frac{2^{-j}}{N}n-k\right),$$

注意这里使用的是 $-j$，这是延续了前面连续小波变换中的形式。实际上在后面多分辨率分析中，使用的是 $j$ 的形式。

具体形式是基于划分矩形 $\frac{1}{N}\times f(\frac{n}{N})g(\frac{n}{N})$ 的方式近似逼近积分，从而实现时间上的离散。

$$\begin{array}{rl}⟨{\Psi }_{j,k}{\Psi }_{j,k}⟩& =1(基函数的属性，能量为1)\\ & ={\int }_0^1{\Psi }_{j,k}(t)\overline{{\Psi }_{j,k}(t)}dt\\ & =2^{-j}{\int }_0^1\Psi (2^{-j}t-k)\overline{\Psi (2^{-j}t-k)}dt\\ & =2^{-j}\sum _{n=0}^{N-1}\Psi (2^{-j}\frac{n}{N}-k)\overline{\Psi (2^{-j}\frac{n}{N}-k)}\frac{1}{N}+O(\frac{1}{N})(N\to \infty 实现相等)\\ & =\sum _0^{N-1}\sqrt{\frac{2^{-j}}{N}}\Psi \left(\frac{2^{-j}}{N}n-k\right)\overline{\sqrt{\frac{2^{-j}}{N}}\Psi \left(\frac{2^{-j}}{N}n-k\right)}+O(\frac{1}{N})\\ & =\sum _0^{N-1}{\Psi }_{j,k}[n]\overline{{\Psi }_{j,k}[n]}+O(\frac{1}{N})\\ & =⟨{\Psi }_{j,k}^{\prime }{\Psi }_{j,k}^{\prime }⟩+O(\frac{1}{N})\end{array}$$

从而整体系数可以表示为如下离散形式：

$$\begin{array}{r}{W}_f(j,k)={\int }_0^{1}f(t)\overline{{\Psi }_{j,k}(t)}dt\approx \sum _{n=0}^{N-1}x[n]\overline{{\Psi }_{j,k}^{\prime }[n]}\end{array}$$

多分辨率分析

正如前面的分析中提到的，通过离散索引，基函数形式变为：

$${\Psi }_{j,k}(t)=2^{-j/2}\Psi (2^{-j}t-k)$$

这里只是提供了基函数的一般形式，对于任何一个母函数都可以通过这套缩放、平移操作生成一组正交基函数。我们希望其能构建正交归一基，从而可以重构任意函数

$$f(t)=\sum _{j,k}⟨f,{\Psi }_{j,k}⟩{\Psi }_{j,k}(t)$$

要满足这些条件直接构造正交小波很难，因此多分辨率分析（MRA）提供了一种更系统的小波函数设计指导。

多分辨率分析是离散小波变换背后的关键理论基础，它并不是随意设计，而是为了解决以下目标，即：如何从连续小波变换中，构造出一组离散、正交、可重构的基函数，使得我们可以稳定、唯一地表示和重建信号？

在如下的表示中，$-j$ 被替换为 $j$，表达了不同的放缩方向。越大，表示分辨率越高（越细）：${\Psi }_{j,k}(t)=2^{j/2}\Psi (2^{j}t-k)$

多分辨率分析引入嵌套（$\cdots \subset V_{j-1}\subset V_j\subset V_{j+1}\subset \cdots \subset L^2(\mathbb{R})$）的对应不同分辨率的子空间集合来逼近整体空间，从而系统地控制分辨率。并引入了两套基函数，即尺度函数和小波函数。$V_j$ 表示可以使用分辨率为 $2^{-j}$ （支撑宽度）的尺度函数 $\varphi (2^{j}t-k)$ 来近似信号的部分。随着 $j$ 的增加，对应尺度函数更宽，对应着更低的频率，从而实现更模糊的近似。

尺度函数

由于子空间之间的关联，所以只要在 $V_0$ 中找对合适的基函数，就能通过“缩放”把它推广到所有 $V_j$。多尺度分析设定中，尺度基函数 $\varphi (t)\in V_0$，的与同一尺度的其他基函数 {ϕ(t−k)}k∈Z\{\phi(t-k)\}_{k \in \mathbb{Z}}{ϕ(t−k)}k∈Z​ 正交且张成 $V_0$。

这里的 $\varphi$ 可以看做是尺度函数的母函数，其他不同尺度、不同位置的尺度函数都可以通过其放缩平移得到：

$${\varphi }_{j,k}(t)=2^{j/2}\varphi (2^{j}t-k)$$

但是通常情况下，只有统一尺度内的基函数之间相互正交（多分辨率分析中，基函数自身范数默认是 1，即都是正交归一的。如果系统只要求“正交”而不强制范数为 1，则称为半正交），即：

$$⟨{\varphi }_{j,k},{\varphi }_{j,k^{\prime }}⟩={\delta }_{k,k^{\prime }},\forall k,k^{\prime }\in \mathbb{Z}$$

尺度函数之间存在细化关系，粗尺度可以用更细的尺度来表示，即存在“细化或膨胀方程”（refinement or dilation equation，也称为双尺度方程）：

$$\varphi (t)=\sum _{n\in \mathbb{Z}}h[n]2^{1/2}\varphi (2t-n)=\underset{归一化因子}{\underbrace{2^{1/2}}}\sum _{n\in \mathbb{Z}}h[n]\varphi (2t-n)$$

• 尺度函数又称 “父小波”（scaling wavelet）或 “低通基”，承担对信号的粗尺度（低频）逼近。
• 它所张成的空间 $V_j$ 捕捉了信号在分辨率 $2^{-j}$ 下的整体轮廓，这是因为对应基函数支撑宽度变为原始母函数的 $2^{-j}$ 倍（有效范围被压缩）。

• 式子本身具有递推的特性，也代表了其他相邻尺度的细化关系。
• 这里把归一化因子提取了出来，整体会更清晰一些；后面小波函数部分也同样处理。
• 这里的一组系数 $h[n]$ 也被称为滤波器抽头。

“滤波器的抽头”（filter taps）是数字滤波器设计和实现中的一个基本概念，特指 FIR（有限冲激响应）滤波器中那些乘以输入样本的系数。这个名称源自于早期数字滤波器的硬件实现：信号 $x[n]$ 经过一串延时器，每经过一级延时就得到 $x[n-1],x[n-2],\dots$；在每一级延时输出处接一个抽头，乘以对应的系数 $h[m]$，再累加到一起，得到 $y[n]$。每个系数乘法点就像一个“抽头”——从延时线上“抽”一个分支出来。

结合细化方程，尺度基函数可以写成如下形式：

$${\varphi }_{j,k}(t)=2^{j/2}\varphi (2^{j}t-k)=\sum _{n\in \mathbb{Z}}h[n]2^{(j+1)/2}\varphi (2^{j+1}t-(2k+n))=\sum _{n\in \mathbb{Z}}h[n]{\varphi }_{j+1,2k+n}(t)$$

对于尺度内正交归一的尺度函数 {ϕ(t−m)}m∈Z\{\phi(t-m)\}_{m \in \mathbb{Z}}{ϕ(t−m)}m∈Z​ （即 $⟨\varphi (t),\varphi (t-m)⟩={\delta }_m$），可以基于上面的细化方程，得到如下推导：

$$\begin{array}{rl}⟨\varphi (t),\varphi (t-m)⟩& =⟨\sum _{n\in \mathbb{Z}}h[n]2^{1/2}\varphi (2t-n),\sum _{k\in \mathbb{Z}}h[k]2^{1/2}\varphi (2t-(2m+k))⟩\\ & =\int \sum _{n\in \mathbb{Z}}h[n]2^{1/2}\varphi (2t-n)\overline{\sum _{k\in \mathbb{Z}}h[k]2^{1/2}\varphi (2t-(2m+k))}dt\\ & =\int \sum _{n\in \mathbb{Z}}h[n]2^{1/2}\varphi (2t-n)\sum _{k\in \mathbb{Z}}h[k]2^{1/2}\overline{\varphi (2t-(2m+k))}dt\\ & =\sum _{n\in \mathbb{Z}}\sum _{k\in \mathbb{Z}}h[n]h[k]\int 2^{1/2}\varphi (2t-n)2^{1/2}\overline{\varphi (2t-(2m+k))}dt\\ & =\sum _{n\in \mathbb{Z}}\sum _{k\in \mathbb{Z}}h[n]h[k]\underset{只有带上系数才正交归一，{\delta }_{n,2m+k}}{\underbrace{⟨2^{1/2}\varphi (2t-n),2^{1/2}\varphi (2t-(2m+k))⟩}}\\ & =\sum _{n\in \mathbb{Z}}h[n]h[n-2m]{\delta }_{2m+k}(只有n=2m+k时内积非零)\end{array}$$

这里实际上提供了关于低频系数序列 $h$ 的一个重要属性，也是把“函数正交”翻译成“滤波器代数”的桥梁，也是所有正交小波工程实现的起点：

$$\sum _{n\in \mathbb{Z}}h[n]h[n-2m]={\delta }_m$$

1. 这把无穷维函数空间的正交问题，降维成有限长序列 $h[n]$ 的卷积方程 ${\sum }_{n}h[n]h[n-2m]={\delta }_m$。这使得设计正交小波等价于设计有限滤波器。
   1. 有限滤波器指，有限区间内有非零值，其余全为 0 的序列。
2. 给出完美重构滤波器组的数学来源。
   1. 只要 $h[n]$ 满足上式，就能由“有限乘加的卷积 + 下采样”的组合操作构造出可完美逆变换的离散小波系统。
   2. $O(N)$ 复杂度：因为卷积长度 $L$ 固定，初始信号长度为 $N$，随着不断下采样，每层信号长度缩减一半，导致整体的计算量逼近 $2LN$。
3. 为 Daubechies、Coiflet、Symlet 等所有正交小波提供了统一的代数设计入口。
   1. 求解满足上述方程的最短长度有限冲激响应滤波器即可。
   2. 有限冲激响应（Finite Impulse Response，FIR）表示输出只跟当前和过去有限个输入有关，没有反馈。

小波函数

在更高的层级中，我们关注的是那些低层级中以及考虑的信息之外的部分，即“补空间”$W_J=V_{J+1}\ominus V_J$（这里表示正交补空间，orthogonal complement），整体来看，如过从第 $J$ 个子空间向更高尺度累积，则存在这样的组合关系：

$$V_J\oplus W_J\oplus W_{J+1}\oplus W_{J+2}\oplus \cdots =L^2(\mathbb{R})$$

对于补空间，其基函数（称为小波函数）表示为：

$$\psi (t)=\sum _{n\in \mathbb{Z}}g[n]2^{1/2}\varphi (2t-n)=\underset{归一化因子}{\underbrace{2^{1/2}}}\sum _{n\in \mathbb{Z}}g[n]\varphi (2t-n)$$

• 又称 “子小波” 或 “高通基”，专门提取相邻两层尺度之间的细节（高频），即 $W_j$。
• 它所张成的空间 $W_j$ 恰好是 $V_{j+1}$ 对 $V_j$ 的补空间，负责把“多出来”的细节补回来。

这里的 $\psi$ 同样可以看做是母函数，可以通过平移放缩出其他的 ${\psi }_{j,k}$：

$${\psi }_{j,k}(t)=2^{j/2}\psi (2^{j}t-k)=\sum _{n\in \mathbb{Z}}g[n]2^{(j+1)/2}\varphi (2^{j+1}t-(2k+n))=\sum _{n\in \mathbb{Z}}g[n]{\varphi }_{j+1,2k+n}(t)$$

二者联合

尺度空间和小波空间中的基函数之间也是正交的，即 $⟨{\psi }_{j,k},{\varphi }_{j,k^{\prime }}⟩=0$。注意，这里只是正交，而不是正交归一的，因为二者是来自两个正交空间的函数。

为了确保二者的正交关系，往往需要对这里的系数 $g[n]$ 精心设计，比如常见的 Haar、Daubechies 等的构造 $g[n]=(-1{)}^{n}h[1-n]$，这就是所谓的 Quadrature Mirror Filter (QMF) 设计：

$$\begin{array}{rl}⟨{\psi }_{j,k},{\varphi }_{j,k^{\prime }}⟩& =\int 2^{j/2}\psi (2^{j}t-k)2^{j/2}\overline{\varphi (2^{j}t-k^{\prime })}dt\\ & =\int [2^{(j+1)/2}\sum _{n\in \mathbb{Z}}g[n]\varphi (2(2^{j}t-k)-n)][2^{(j+1)/2}\overline{\sum _{m\in \mathbb{Z}}h[m]\varphi (2(2^{j}t-k^{\prime })-m)}]dt\\ & =\int [\sum _{n\in \mathbb{Z}}g[n]2^{(j+1)/2}\varphi (2^{j+1}t-(2k+n))][\overline{\sum _{m\in \mathbb{Z}}h[m]2^{(j+1)/2}\varphi (2^{j+1}t-(2k^{\prime }+m))}]dt\\ & =\sum _{n\in \mathbb{Z}}\sum _{m\in \mathbb{Z}}h[m]g[n]\int [2^{(j+1)/2}\varphi (2^{j+1}t-(2k+n))][\overline{2^{(j+1)/2}\varphi (2^{j+1}t-(2k^{\prime }+m))}]dt\\ & =\sum _{n\in \mathbb{Z}}\sum _{m\in \mathbb{Z}}h[m]g[n]\int {\varphi }_{j+1,2k+n}(t)\overline{{\varphi }_{j+1,2k^{\prime }+m}(t)}dt\\ & =\sum _{n\in \mathbb{Z}}\sum _{m\in \mathbb{Z}}h[m]g[n]{\delta }_{2k+n,2k^{\prime }+m}dt\\ & =\sum _{n\in \mathbb{Z}}h[n+2(k-k^{\prime })]g[n](m=n+2(k-k^{\prime }))\\ & =\sum _{n\in \mathbb{Z}}h[n+2l]g[n](l=k-k^{\prime })\\ & =\sum _{n\in \mathbb{Z}}(-1{)}^{n}h[n+2l]h[1-n]\\ & =\sum _{m\in \mathbb{Z}}(-1{)}^{m-2l}h[m]h[1-m+2l](换元：m=n+2l)\\ & =\sum _{m\in \mathbb{Z}}(-1{)}^{m}h[m]h[1+2l-m]\\ & =0(偶数m存在对应的结果符号相反的奇数m，综合后为0)\end{array}$$

即同一尺度内的任意尺度函数与小波函数内积为零，完成了它们的正交性。同时二者各自又分别是两个不同空间的正交基函数，本质上是两个正交子空间的“构造单位”。把一个尺度层的尺度函数基，加上所有更细层的小波基，按尺度从粗到细“拼”在一起，就得到一套互相正交、能完全展开信号的统一正交基，这也对应了前面的空间组合公式：

$$V_J\oplus W_J\oplus W_{J+1}\oplus W_{J+2}\oplus \cdots =L^2(\mathbb{R})$$

所以相对应，完整信号 $f(t)$ 的表示应该是：

$$\begin{array}{r}f(t)=\underset{信号低频主干}{\underbrace{\sum _k{a}_J[k]{\varphi }_{J,k}(t)}}+\underset{信号在各层上的高频细节}{\underbrace{\sum _{j=J}^{\infty }\sum _k{d}_j[k]{\psi }_{j,k}(t)}}\end{array}$$

而对应系数可以表示为：

$$\begin{array}{rl}{a}_j[k]& =⟨f,{\varphi }_{j,k}⟩=\int f(t)2^{j/2}\varphi (2^{j}t-k)dt\\ & =\int f(t)\left[\sum _{n}h[n]2^{(j+1)/2}\varphi (2^{j+1}t-2k-n)\right]dt\\ & =\sum _{m}h[m-2k]\int f(t)2^{(j+1)/2}\varphi (2^{j+1}t-m)dt(m=2k+n\to n=m-2k)\\ & =\sum _{m}h[m-2k]\int f(t){\varphi }_{j+1,m}(t)dt\\ & =\sum _{m}h[m-2k]a_{j+1}[m]\\ d_j[k]& =⟨f,{\psi }_{j,k}⟩=\int f(t)2^{j/2}\psi (2^{j}t-k)dt\\ & =\int f(t)\left[\sum _{n}g[n]2^{(j+1)/2}\varphi (2^{j+1}t-2k-n)\right]dt\\ & =\sum _{m}g[m-2k]\int f(t){\varphi }_{j+1,m}(t)dt\\ & =\sum _{m}g[m-2k]a_{j+1}[m]\end{array}$$

这里的 $a$ 和 $d$ 的形式正好是先离散卷积，再隔点采样的计算。

对于离散信号 a[k] 和 h[m]，其离散卷积定义为：$(a\ast h)[m]={\sum }_{k}a[k]h[m-k]$。而上式中的系数 $m-2k$ 实际上可以看做是这里 ${\sum }_k$ 中的偶数部分，即对结果进行所谓的“隔点采样”。

另外，基于在特定层分解所对应的公式 $V_J\oplus W_J=V_{J+1}$，我们可以进一步推导出重构的系数关系：

$$\begin{array}{rl}{f}_{J+1}(t)& =\sum _k{a}_J[k]{\varphi }_{J,k}(t)+\sum _k{d}_J[k]{\psi }_{J,k}(t)\\ & =\sum _k{a}_J[k]\left(\sum _{n}h[n]{\varphi }_{J+1,2k+n}(t)\right)+\sum _k{d}_J[k]\left(\sum _{n}g[n]{\varphi }_{J+1,2k+n}(t)\right)\\ & =\sum _k\sum _n{a}_J[k]h[n]{\varphi }_{J+1,2k+n}(t)+\sum _k\sum _n{d}_J[k]g[n]{\varphi }_{J+1,2k+n}(t)\\ & =\sum _m\left(\sum _k{a}_J[k]h[m-2k]+d_J[k]g[m-2k]\right){\varphi }_{J+1,m}(t)(m=2k+n)\\ & =\sum _m\underset{a_{J+1}[m]}{\underbrace{\sum _k{a}_J[k]h[m-2k]+d_J[k]g[m-2k]}}{\varphi }_{J+1,m}(t)(m=2k+n)\\ & \Downarrow \\ a_{J+1}[m]& =\sum _k{a}_J[k]h[m-2k]+d_J[k]g[m-2k]\end{array}$$

参考资料

• https://rafat.github.io/sites/wavebook/intro/mra.html
• https://dezeming.top/wp-content/uploads/2022/05/Mallat快速小波算法.pdf