Ch6 小波变换&其他图像变换

[TOC]

绿色：考、红色：不考、黄色：可看。

Q: 为什么我们需要小波变换？

A: 那当然是因为傅里叶变换有缺陷。时域(空域)上的函数经过傅里叶变换之后，得到频域上对应的函数。当然二者是等价的，但是频域上的函数只含有频域信息、时域上的函数也只含有时域信息。

这就导致了一个问题：我们没法根据$F(u,v)$还原出原始的具有时间信息的时域函数(就是在一段时间内：存在固定频率的波形、经过不同顺序的排列：显然它们的时域函数不同、但是得到的频域函数确实完全一致的)。这说明傅里叶变换的时候丢失了时间的信息。

这也和测量不准性一致(海森堡定理)：时域和频域就像跷跷板的两端，我们没法都做到最好、要么取极端、要么取中庸。

在量子力学中，海森堡不确定性原理指出，我们不能同时精确地测量粒子的位置和动量，类似地，在傅里叶分析中，我们不能同时在时域和频域中获得完全精确的信息。

Q: 小波变换的优势？

A: 1. 弥补傅里叶变换丢失时域信息

2. 具有多分辨率分析的能力，能够在不同尺度下对信号进行分析(可以在不同分辨率下提取特征).

背景知识(bk)

图像金字塔(Image Pyramid)

一幅图像的金字塔是一系列以金字塔形状排列的分辨率逐步降低的图像集合。

下图是拉普拉斯金字塔的构建：

图(a)建立了一个简单的图像金字塔系统。$j-1$级的近似输出用来建立近似值金字塔，包括原始图像的一个or多个近似值。
图(b)表明：近似值和预测残差金字塔都是以一种迭代的方式进行计算的。$2\uparrow$:上采样(插值)、$2\downarrow$：下采样。

下图中：上图表示高斯金字塔、下图表示拉普拉斯金字塔。分辨率:512\256\128\64

若要生成拉普拉斯金字塔，必须先生成高斯金字塔。拉普拉斯金字塔首先从$64\times 64$大小的近似图像开始，预测( 插值or滤波实现 )$128\times 128$的高斯图像。对应的拉普拉斯金字塔图像=原始图像-上采样预测图像( 得到的插值 )。

子带编码(Sub-band Coding)

子带编码：一副图像被分解为一系列带限分量的集合，称为子带，它们可以重组在一起无失真地重建原始图像。每个子带可以通过带通滤波得到；因为得到的子带带宽比原始图像带宽小，因此子带可以无损地下采样( 奈奎斯特定理 )。原始图像的重建可以通过插值、滤波、叠加单个子带来完成。

Q: 得到的经过上下采样后的$g_0(n)$与原始信号$h_0(n)$一致吗？

A：通常来是不等的。上采样：插0.

Z - 变换(线性变换)

傅里叶变换是Z - 变换的一个特例。当$z$取复平面上单位圆上的一个点$e^{jw}$的时候，就是离散傅里叶变换的形式。

$X(z)=\sum_{n =-\infty}^{\infty}x(n)z^{-n}\\ X(k)=\sum_{n =-\infty}^{\infty}x(n)e^{-jwn}=\sum_{n =-\infty}^{\infty}x(n)e^{-j\frac{2\pi}{N}kn},\ k=0,1,\dots,N-1$

其中：$x(n)$是时域信号，$z$是复变量。

e.g. $x(n)=\begin{pmatrix}1&3&5&7\end{pmatrix}$,角标是$[-1,0,1,2]$

那么$x(z)=1·z+3+5·z^{-1}+7·z^{-2}$，可见Z-变换是将时域信号转换为一个多项式函数。

信号下采样Z-变换：
$\begin{align} x_{down}(n)&=x(2n)\\ X_{down}(z)&=\frac{1}{2}[X(z^{\frac{1}{2}})+X(-z^{\frac{1}{2}})] \end{align}$
信号上采样Z-变换：(上采样中间填充0)
$\begin{align} x_{up}(n)&=\begin{cases}x(n/2),&n = 0,2,4,\cdots\\0,&\text{otherwise}\end{cases}\\ X_{up}(z)&=X(z^{2}) \end{align}$

结合下采样和上采样，得到:

$\hat{X}(z)=\frac{1}{2}[X(z)+X(-z)]\\\\ s.t.\begin{cases} \hat{x}(n)=Z^{-1}[\hat{X}(z)]\\ Z^{-1}[\hat{X}(-z)]=(-1)^{n}\hat{x}(n) \end{cases}$

一个双子带编码和解码系统可表示为：

$\hat{X}(z)=\frac{1}{2}G_{0}(z)[H_{0}(z)X(z)+H_{0}(-z)X(-z)]+\\ \frac{1}{2}G_{1}(z)[H_{1}(z)X(z)+H_{1}(-z)X(-z)]$

其中滤波器$h_{0}(n)$的输出由变换对定义：

$h_{0}(n)*x(n)=\sum_{k}h_{0}(n - k)x(k)\Leftrightarrow H_{0}(z)X(z)$

因为Z-变换是线性变换。重新排列上述方程中的项，得到：

$\hat{X}(z)=\frac{1}{2}[H_{0}(z)G_{0}(z)+H_{1}(z)G_{1}(z)]X(z)\\+\frac{1}{2}[H_{0}(-z)G_{0}(z)+H_{1}(-z)G_{1}(z)]X(-z)$

我最终想要的结果是$\hat X(z)=X(z)$, 为了无误差地重建输入，施加以下条件：

$H_{0}(z)G_{0}(z)+H_{1}(z)G_{1}(z)=2\\ H_{0}(-z)G_{0}(z)+H_{1}(-z)G_{1}(z)=0$

它们可以合并为单个矩阵表达式:

$[G_{0}(z)\quad G_{1}(z)]H_{m}(z)=[2\quad0]\\ H_{m}(z)=\begin{bmatrix}H_{0}(z)&H_{0}(-z)\\H_{1}(z)&H_{1}(-z)\end{bmatrix}$

其中$H_m(z)$是分析调制矩阵。

假设$H_{m}(z)$是非奇异(可逆)，我们可以得到(此处就是非常普通的求解方程$A^Tx=b$):

$\begin{bmatrix}G_{0}(z)\\G_{1}(z)\end{bmatrix}=\frac{2}{\text{det}(H_{m}(z))}\begin{bmatrix}H_{1}(-z)\\-H_{0}(-z)\end{bmatrix}$

上述方程表明$G_{0}(z)$是$H_{1}(-z)$的函数，$G_{1}(z)$是$H_{0}(-z)$的函数。所以分析和合成滤波器是交叉调制的。

完美重建滤波器组(PCFB, Perfect Construction Filter Banks)

有限脉冲响应（FIR）滤波器

Q: 有限脉冲响应（FIR）滤波器?

A: 一种能够按照设计好的规则处理信号，并且它对脉冲信号的响应在一段时间后会结束的工具。

脉冲响应：当你给一个滤波器一个很特殊的输入，就像用小锤子敲一下（在信号里叫脉冲信号），滤波器会输出一个信号，这个输出信号就叫脉冲响应。

有限：对于 FIR 滤波器，它的脉冲响应在一段时间后就会变成零。通俗来讲，就像是你敲了一下小锤子，滤波器 “响” 了一会儿，然后就安静下来了，这个 “响” 的时间是有限的。

Q: 纯延迟？

A: 当一个信号通过这个系统时，其输出信号在时间轴上会向后移动一定的时间单位。如果把信号看作是一系列随时间变化的数值，那么经过这个系统后，每个数值出现的时间会推迟，而数值本身的大小等其他特性不变。

例子：例如，你对着山谷呼喊，声音传播到山谷对面再反射回来，你听到回声的过程就类似于一个延迟。声音本身除了延迟出现之外，没有其他变化。

对于有限脉冲响应（FIR）滤波器，分析调制矩阵$H_{m}(z)$的行列式是纯延迟：

$\text{det}(H_{m}(z))=\alpha z^{-(2k + 1)}$

$z^{-(2k+1)}$项可以被认为是任意的，因为它只是改变了滤波器的整体延迟。忽略延迟，令$\alpha = 2$并取逆$Z$变换，得到：

$\begin{align} &g_{0}(n)=(-1)^{n}h_{1}(n)\\ &g_{1}(n)=(-1)^{n + 1}h_{0}(n) \end{align}$

如果$\alpha=-2$，得到的表达式符号反转，即:

$\begin{align} &g_{0}(n)=(-1)^{n+1}h_{1}(n)\\ &g_{1}(n)=(-1)^{n}h_{0}(n) \end{align}$

因此，FIR合成滤波器是分析滤波器的交叉调制版本，有且只有一个与分析滤波器方向相反。

双正交性(biorthogonality)

现在展示分析和合成滤波器的另一个重要特性：双正交性。

令$P(z)$为低通分析和合成滤波器传递函数的乘积，得到:

$P(z)=G_{0}(z)H_{0}(z)=\frac{2}{\text{det}(H_{m}(z))}H_{0}(z)H_{1}(-z)$

由于$\text{det}(H_{m}(z))=-\text{det}(H_{m}(-z))$，乘积$G_{1}(z)H_{1}(z)$可类似地定义为:

$G_{1}(z)H_{1}(z)=\frac{-2}{\text{det}(H_{m}(z))}H_{0}(-z)H_{1}(z)=P(-z)\\ \therefore G_{1}(z)H_{1}(z)=P(-z)=G_{0}(-z)H_{0}(-z)$

将其代入完美构建方程的约束条件，得到:

$\begin{align} &\because H_{0}(z)G_{0}(z)+H_{1}(z)G_{1}(z)=2\\ &\therefore G_{0}(z)H_{0}(z)+G_{0}(-z)H_{0}(-z)=2 \end{align}$

对$G_{0}(z)H_{0}(z)+G_{0}(-z)H_{0}(-z)=2$两边取逆$Z$变换$\begin{cases}\hat{x}(n)=Z^{-1}[\hat{X}(z)]\\
Z^{-1}[\hat{X}(-z)]=(-1)^{n}\hat{x}(n)\end{cases}$，得:

$\sum_{k}g_{0}(k)h_{0}(n - k)+(-1)^{n}\sum_{k}g_{0}(k)h_{0}(n - k)=2\delta(n)\\ \delta{(n)}=\begin{cases}1 ,&n=0\\0, &n\neq 0\end{cases}$

$\delta(n)$是单位脉冲序列，由于奇数索引项抵消, 偶数项有两倍，抵消$2\delta(n)$中的2倍，进一步简化得到:

$\sum_{k}g_{0}(k)h_{0}(2n - k)=\langle g_{0}(k),h_{0}(2n - k)\rangle=\delta(n)$

类似地，可以证明：

$\begin{align} &\langle g_{1}(k),h_{1}(2n - k)\rangle=\delta(n)\\ &\langle g_{0}(k),h_{1}(2n - k)\rangle = 0\\ &\langle g_{1}(k),h_{0}(2n - k)\rangle = 0 \end{align}$

可以建立更一般的表达式 :

$\langle h_{i}(2n - k),g_{j}(k)\rangle=\delta(i - j)\delta(n)\quad i,j\in\{0,1\}$

滤波器组满足此条件，即双正交性。 (每一行：自己和自己内积=1，不同行内积=0，i与j )

结论：所有两频段实系数的完美构建滤波器组的分析和合成滤波器脉冲响应都受双正交性约束。

通解

QMF（Quadrature Mirror Filter，正交镜像滤波器）：是一种在数字信号处理中用于子带编码的滤波器。它的特点是低通滤波器和高通滤波器的频率响应是彼此的镜像关系，且满足一定的正交性条件。
CQF（Conjugate Quadrature Filter，共轭正交滤波器）：也是一种用于数字信号处理的滤波器。
Orthonormal, 正交滤波器
被用于后续的快速小波变换的开发。

重要特性

双正交性（Biorthogonality） - 每种滤波器类型都满足双正交性要求，但它们的生成方式不同，从而定义了不同类别的完美重构滤波器。
原型滤波器（Prototype Filter） - 对于每一类，都有一个“原型”滤波器是按照特定规格设计的，其余的滤波器则是从这个原型滤波器计算得出的。

除了双正交性，完美重构滤波器组的正交性还定义为：

$\langle g_i(n), g_j(n + 2m) \rangle=\delta(i - j)\delta(m),\ i, j = \{0, 1\}$

可以看到，$G_1$与低通合成滤波器$G_0$通过调制、时域反转和奇数平移相关。此外，$H_1$和$H_0$分别是对应合成滤波器$G_1$和$G_0$的时域反转。

Z-变化其他两个重要性质：

$x(-n)\iff X(z^{-1})\\ x(n-k)\iff z^{-k}X(z)$

正交滤波器的逆Z变换

Filter	Orthonormal
$H_0(z)$	$G_0(z^{-1})$
$H_1(z)$	$G_1(z^{-1})$
$G_0(z)$	$G_0(z)G_0(z^{-1})+G_0(-z)G_0(-z^{-1})=2$
$G_1(z)$	$-z^{-2K+1}G_0(-z^{-1})$

对表格正交滤波器的适当项取逆Z变换，可以得到：

$h_0(n)=g_0(-n),h_1(n)=g_1(-n)\\ h_i(n)=g_i(2K - 1 - n), i = \{0, 1\}\\\\ g_1(n)=(-1)^n g_0(2K - 1 - n)\\$

这里$h_0$、$h_1$、$g_0$、$g_1$是定义的正交滤波器的脉冲响应。

可以看到式(1)与式(2)差了一个$2K-1$,也就是说将$g_i$推迟了$2K-1$个时刻发生。这个对应前面的”有限脉冲响应（FIR）滤波器，分析调制矩阵$H_{m}(z)$的行列式是纯延迟“。

加上2K-1的目的：延迟操作可以用来控制信号在时间轴上的位置，确保滤波器的不同部分（如分析滤波器和合成滤波器）在时间上正确对齐。

哈尔变换(Haar Transform)

Haar变换（Haar [1910]）的基函数是最古老且最简单的已知正交小波。Haar变换本身既是可分离的又是对称的，并且可以表示为矩阵形式：

$T = HFH^{T}$

其中$F$是一个$N\times N$矩阵，$H$是一个$N\times N$变换矩阵，$T$是一个结果$N\times N$变换。

变换矩阵$H$包含在区间$z\in[0,1]$上定义的Haar基函数$h_{k}(z)$，对于$k = 0,\cdots,N - 1$，其中$N = 2^{n}$。

为了生成$H$，我们定义整数$k$，$k = 2^{p}+q - 1$，其中$0\leq p\leq n - 1$.

对于$p = 0$: $q = 0/1$
对于$p\neq0$：$1\leq q\leq 2^{p}$

举例说明：

k/10进制 k/2进制 p q

11 1011 3 4

21 10101 4 6

0 0 0 0

1 1 0 1

k/10进制	k/2进制	p	q
11	1011	3	4
21	10101	4	6
0	0	0	0
1	1	0	1

Haar基函数是（$z\in[0,1]$）：

$h_{0}(z)=h_{00}(z)=\frac{1}{\sqrt{N}}\\ h_{k}(z)=h_{pq}(z)=\frac{1}{\sqrt{N}}\begin{cases}2^{p/2},&(q - 1)/2^{p}\leq z\leq (q - 0.5)/2^{p}\\-2^{p/2},&(q - 0.5)/2^{p}\leq z\leq q/2^{p}\\0,&\text{otherwise} \end{cases}$

q决定正脉冲起始位置、p决定脉冲宽窄。

当$N = 8$时，对应的$k$、$q$、$p$值,给出了一个表格：

$k$	$0$	$1$	$2$	$3$	$4$	$5$	$6$	$7$
$p$	$0$	$0$	$1$	$1$	$2$	$2$	$2$	$2$
$q$	$0$	$1$	$1$	$2$	$1$	$2$	$3$	$4$

$H_{8}$矩阵 :当$N = 8$时，$H_{8}$矩阵为：

$H_{8}=\frac{1}{\sqrt{8}}\begin{bmatrix} 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ 1 & 1 & 1 & 1 & -1 & -1 & -1 & -1 \\ \sqrt{2} &\sqrt{2} & -\sqrt{2}& -\sqrt{2} & 0 & 0 & 0 & 0\\ 0 & 0 &0 & 0 & \sqrt{2} &\sqrt{2} & -\sqrt{2}& -\sqrt{2}\\ 2 & -2 & 0 & 0 &0&0&0&0\\ 0 & 0 & 2 & -2 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 2 & -2 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 2 & -2 \\ \end{bmatrix}$

哈尔矩阵：第一行永远是1，第二行永远一半1一半-1.

反正算就完事了。

多分辨率展开(Multi-resolution Expansions)

前面介绍了三种图像处理技术：图像金字塔、子带编码、哈尔变换。这在多分辨率分析(Multi-resolution Analysis, MRA)中会用到。

在多分辨率分析中，尺度函数被用于建立某一函数或是图像的一系列近似值，小波函数对相邻近似值之间的差异进行编码。

Q: 尺度函数、小波函数？

A: 尺度函数类似于低通滤波器的作用、小波函数描述高通滤波器的作用。

序列展开(Series Expansions)

一个信号或函数$f(x)$通常被分解为一系列展开函数的线性组合，即:

$f(x)=\sum_{k}\alpha_{k}\varphi_{k}(x)$

如果扩展是唯一的，即对于任何给定的$f(x)$只有一组$\alpha_{k}$，则$\varphi_{k}(x)$称为基函数，扩展集$\{\varphi_{k}(x)\}$称为可如此表示的函数类的基。

可表示的函数形成一个函数(张成)空间，称为扩展集的闭包（closed span），记为：

$V = \overline{Span_k\{\varphi_{k}(x)\}}$

对于任意张成空间$V$和相应的扩展集$\{\varphi_{k}(x)\}$，存在一组对偶函数$\{\tilde{\varphi}_{k}(x)\}$，可用于通过取对偶$\tilde{\varphi}_{k}(x)$和$f(x)$的积分内积来计算系数$\{\alpha_{k}\}$，即：

$\alpha_{k}=\langle\tilde{\varphi}_{k}(x),f(x)\rangle=\int\tilde{\varphi}_{k}^{*}(x)f(x)dx$

计算系数$\alpha_{k}$涉及三种情况、但基本都是正交小波、只用情况1.

情况I：如果扩展函数形成$V$的正交基，即：

$\langle\varphi_{j}(x),\varphi_{k}(x)\rangle=\delta_{jk}=\begin{cases}0&j\neq k\\1&j = k\end{cases}$

则基及其对偶是等价的。因此$\alpha_{k}=\langle\varphi_{k}(x),f(x)\rangle$。

尺度函数(Scaling Function)

现在考虑由实数、平方可积函数$\varphi(x)$的整数平移和二进制尺度组成的扩展函数集$\varphi_{j,k}(x)$，$\varphi_{j,k}(x)$称为尺度函数。

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

对于所有$j,k\in Z$且$\varphi_{j,k}(x)\in L^{2}(R)$都成立；此时$k$确定$\varphi_{j,k}(x)$沿$x$轴的位置，$j$确定$\varphi_{j,k}(x)$的宽度，$2^{j/2}$控制其高度或幅度。

当 $j$ 增大时，$2^{j}$ 变大，意味着$\varphi(2^{j}x - k)$中的$x$被压缩，即函数在$x$ 轴上的变化变得更快，宽度减小。

通过适当选择基函数$\varphi(x)$，$\{\varphi_{j,k}(x)\}$可以张成$L^{2}(R)$，即所有可度量的平方可积函数的集合。

对于特定值$j = j_{0}$，扩展集$\{\varphi_{j_{0},k}(x)\}$是$\{\varphi_{j,k}(x)\}$的子集。可以将该子空间定义为：

$V_{j_{0}}=\overline{Span\{\varphi_{j_{0},k}(x)\}}$

由于$V_{j_{0}}$是$\varphi_{j_{0},k}(x)$在$k$上的张成，如果$f(x)\in V_{j_{0}}$，它可以写成：

$f(x)=\sum_{k}\alpha_{k}\varphi_{j_{0},k}(x)$

一般地，对于任何$j$，我们将在$k$上张成的子空间记为:

$V_{j}=\overline{Span\{\varphi_{j,k}(x)\}}$

例：哈尔尺度函数(Haar scaling func)

哈尔尺度函数是高度为1、宽度为1的尺度函数。

$\varphi(x)=\begin{cases}1,&0\le x\le 1\\ 0,&otherwise \end{cases}$

来自Haar基函数。尺度=1时的宽度是尺度=0时的一半；对于x上已知间隔，尺度=1的尺度函数时尺度=0的2倍(纵坐标的值)。(f):$f(x)=\frac 1{2}\varphi_{1,0}(x)+\varphi_{1,1}(x)-\frac 1 4 \varphi_{1,4}(x)$

上图例子说明：

增加 $j$的值（$j \uparrow$）：意味着函数被缩小，即 $\varphi_{j,k}(x)$的宽度变窄，能够捕捉到更细微的细节。同时，$V_j$的容量增大，能够包含更多具有小尺度变化的函数。
减少 $j$的值（$j \downarrow$）：意味着函数被放大，即 $\varphi_{j,k}(x)$的宽度变宽，主要捕捉到整体的、低频的信息。

多分辨率分析的四项基本要求

在上面的例子中，简单的尺度函数遵循多分辨率分析的如下4个基本要求：

1.尺度函数与其积分变换正交。	2.由尺度函数在低尺度上张成的子空间嵌套在高尺度上张成的子空间中。	3.唯一在所有$V_{i}$中都存在的函数是$f(x) = 0$	4.任何函数都可以以任意精度表示
Haar尺度函数是紧支撑的，即在一个有限区间(支撑)外函数值为0。	$\dots \subset V_{-1}\subset V_0 \subset V_1 \subset V_2\subset \cdots $, 每个子空间 $V_j$都包含了比前一个子空间 $V_{j-1}$更多的细节信息。这就像是从模糊到清晰，一步步深入地观察信号或图像。	$V_{-\infty}=0$	$V_{\infty}=L^{2}(R)$

在这些条件下，子空间$V_{j}$的展开函数可以表示为子空间$V_{j + 1}$的展开函数的加权和，即：

$\varphi_{j,k}(x)=\sum_{n}\alpha_{n}\varphi_{j + 1,n}(x)$

将变量$\alpha_{n}$变换为$h_{\varphi}(n)$，进一步得到：

$\varphi_{j,k}(x)=\sum_{n}h_{\varphi}(n)2^{(j + 1)/2}\varphi(2^{(j + 1)}x - n)$

对于$\varphi(x)=\varphi_{0,0}(x)$，得到更简单的表达式：

$\varphi(x)=\sum_{n}h_{\varphi}(n)\sqrt{2}\varphi(2x - n)$

$h_{\varphi}(n)$被称为尺度函数系数，$h_{\varphi}$被称为尺度向量。该MRA方程表明任何子空间的扩展函数都可以由自身的双分辨率副本构建。

Haar函数的尺度函数系数是$h_{\varphi}(0)=h_{\varphi}(1)=\frac{1}{\sqrt{2}}$，所以MRA方程是:
$\begin{align} \varphi(x)&=\frac{1}{\sqrt{2}}[\sqrt{2}\varphi(2x)]+\frac{1}{\sqrt{2}}[\sqrt{2}\varphi(2x - 1)]\\ \varphi(x)&=\varphi(2x)+\varphi(2x - 1) \end{align}$

小波函数(Wavelet Function)

给定一个满足上述MRA要求的尺度函数（scaling function），我们可以定义一个小波函数 $\psi(x)$，它与它的整数平移和二进制尺度一起，跨越了任意两个相邻尺度子空间 $V_j$ 和 $V_{j + 1}$ 之间的差异。

定义小波函数集：

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

可以看见这个形式与尺度函数很相似，定义小波子空间：

$W_j=\overline{Span_k\{\psi_{j,k}(x)\}}$

注意: 如果 $f(x)\in W_j$，则有$f$可以被该空间的基唯一的线性表示。

$f(x)=\sum_{k}\alpha_{k}\psi_{j,k}(x)$

尺度和小波子空间之间的关系

尺度和小波函数子空间的关系是：

$V_{j + 1}=V_j\oplus W_j$

其中 $\oplus$表示空间的直和（类似于集合的并集）。

$V_j$ 在 $V_{j + 1}$ 中的正交补是 $W_j$，并且 $V_j$ 的所有元素与 $W_j$ 的元素正交，即 $\langle\varphi_{j,k}(x),\psi_{j,l}(x)\rangle = 0$，对于所有合适的 $j,k,l\in Z$。

所有可度量、平方可积函数的空间为:

$\begin{align} L^{2}(R)&=V_0\oplus W_0\oplus W_1\oplus\cdots\\ \text{or}\quad L^{2}(R)&=V_1\oplus W_1\oplus W_2\oplus\cdots\\ \text{or}\quad L^{2}(R)&=\cdots\oplus W_{-2}\oplus W_{-1}\oplus V_0\oplus W_0\oplus W_1\oplus W_2\oplus\cdots \end{align}$

有一个通用结果, 其中 $j_0$ 是任意起始尺度。

$L^{2}(R)=V_{j_0}\oplus W_{j_0}\oplus W_{j_0 + 1}\oplus\cdots$

由于小波空间存在于由下一个更高分辨率尺度函数张成的空间内，任何小波函数也可以表示为移位的、双分辨率尺度函数的加权和，即:

$\psi(x)=\sum_{n}h_{\psi}(n)\sqrt{2}\varphi(2x - n)$

其中 $h_{\psi}(n)$ 被称为小波函数系数，$h_{\psi}$ 是小波向量。

利用小波张成正交补空间且整数小波平移是正交的条件，可以证明由Burrus、Gopinath和Guo [1998]提出的：

$h_{\psi}(n)=(-1)^{n}h_{\varphi}(1 - n)$

Haar小波函数

对于Haar小波，相应的小波向量和小波函数是：

$\begin{align} h_{\psi}(0)&=(-1)^{0}h_{\varphi}(1 - 0)=\frac{1}{\sqrt{2}}\\ h_{\psi}(1)&=(-1)^{1}h_{\varphi}(1 - 1)=-\frac{1}{\sqrt{2}}\\\\ \psi(x)&=\sum_{n}h_{\psi}(n)\sqrt{2}\varphi(2x - n)\\&=\varphi(2x)-\varphi(2x - 1)\\ &=\begin{cases}1,&0\le x< 0.5\\-1,&0.5\le x< 1\\0,& otherwise\end{cases} \end{align}$

例：

(a)原小波函数$\psi_{0,0}(x)$、(b)$\psi_{0,2}(x)$、(c)$\psi_{1,0}(x)$：对于空间$W_1$, $小波\psi_{1,0}(x)$比针对$W_0$的小波$\psi_{0,2}(x)$窄，这说明它能表示更加细微的细节。
(d)显示了在子空间$V_1$而不在子空间$V_0$中的函数。该函数在前述例子中曾考虑过[见上图Haar尺度函数(f)]。虽然该函数不能在$V_0$中精确表示，但它可以用$V_0$和$W_0$的展开函数进行展开。展开结果如下：
$f(x) = f_a(x) + f_d(x)\\ f_a(x) = \frac{3\sqrt{2}}{4}\varphi_{0,0}(x) - \frac{\sqrt{2}}{8}\varphi_{0,2}(x)\\ f_d(x) = \frac{-\sqrt{2}}{4}\psi_{0,0}(x) - \frac{\sqrt{2}}{8}\psi_{0,2}(x)$
$f_a(x)$是$f(x)$使用$V_0$尺度函数的近似，而$f_d(x)$为$f(x) - f_a(x)$的差，用$W_0$小波和表示。这两个展开式，如(e)和(f)所示，将$f(x)$用类似高通和低通滤波器的方法分成两部分。$f_a(x)$的低频部分在$f_a(x)$中得到，$f_a(x)$给出了$f(x)$在每个积分区间上的平均值，而高频细节则在$f_d(x)$中编码。

一维小波变换(Wavelet Transforms in One Dimension)

小波函数作为一系列的函数族，需要满足以下两个约束条件：

均值为0：(容许条件，小波函数不应该含有0频分量=函数的平均值)
$\int^{\infty}_{-\infty}\Psi(t)dt=0$
在傅里叶变换中，我们使用正弦函数展开。可以看到正弦函数也满足这个条件。BUT，正弦函数不满足下面这个条件。

平方可积(有限能量)：
$\int^{\infty}_{-\infty}|\Psi(t)|^2dt<\infty$

文中提及的可度量、平方可积，意思是要满足上面的两个条件。

小波序列展开(Wavelet series expansion)

我们定义函数$f(x)\in L^{2}(R)$相对于小波函数$\psi(x)$和尺度函数$\varphi(x)$的小波级数展开为：

$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)$

其中$j_{0}$是任意起始尺度，$c_{j_{0}}(k)$通常被称为近似系数，$d_{j}(k)$被称为细节系数。

这说明：任何可度量的、平方可积的一维函数都可以表示为$j\ge j_0$的$V_{j0}$尺度函数和$W_j$小波的加权和。

如果展开函数形成一个正交基或紧支撑（=尺度函数与其积分变换正交。这是常见情况），展开系数通过以下方式计算：

$c_{j_{0}}(k)=\langle f(x),\varphi_{j_{0},k}(x)\rangle=\int f(x)\varphi_{j_{0},k}(x)dx\\ d_{j}(k)=\langle f(x),\psi_{j,k}(x)\rangle=\int f(x)\psi_{j,k}(x)dx$

例：$y=x^2$的哈尔小波级数展开

考虑如下的简单函数，计算使用Haar小波表示它的展开系数。

$y = \begin{cases} x^{2},&0\leq x < 1\\ 0,&\text{otherwise} \end{cases}$

解：令$j_{0}=0$：

$\begin{align} c_{0}(0)&=\int_{0}^{1}x^{2}\varphi_{0,0}(x)dx=\int_{0}^{1}x^{2}dx=\frac{x^{3}}{3}\Big|_{0}^{1}=\frac{1}{3}\\ d_{0}(0)&=\int_{0}^{1}x^{2}\psi_{0,0}(x)dx=\int_{0}^{0.5}x^{2}dx-\int_{0.5}^{1}x^{2}dx=-\frac{1}{4}\\ d_{1}(0)&=\int_{0}^{1}x^{2}\psi_{1,0}(x)dx=\int_{0}^{0.25}x^{2}\sqrt{2}dx-\int_{0.25}^{0.5}x^{2}\sqrt{2}dx=-\frac{\sqrt{2}}{32}\\ d_{1}(1)&=\int_{0}^{1}x^{2}\psi_{1,1}(x)dx=\int_{0.5}^{0.75}x^{2}\sqrt{2}dx-\int_{0.75}^{1}x^{2}\sqrt{2}dx=-\frac{3\sqrt{2}}{32} \end{align}$

将这些值带入小波级数展开式，有：

离散小波变换(Discrete Wavelet Transforms)

小波级数展开将单个连续变量的函数映射为离散系数序列。如果被展开的函数是离散的，例如连续函数$f(x)$的样本，则展开的系数是函数的离散小波变换( DWT )、展开本身是函数的离散小波反变换。

DWT变换对定义为:

$W_{\varphi}(j_{0},k)=\frac{1}{\sqrt{M}}\sum_{x}f(x)\varphi_{j_{0},k}(x)\\ W_{\psi}(j,k)=\frac{1}{\sqrt{M}}\sum_{x}f(x)\psi_{j,k}(x) \quad \text{for } j\geq j_{0}\\\\ f(x)=\frac{1}{\sqrt{M}}\sum_{k}W_{\varphi}(j_{0},k)\varphi_{j_{0},k}(x)+\frac{1}{\sqrt{M}}\sum_{j = j_{0}}^{\infty}\sum_{k}W_{\psi}(j,k)\psi_{j,k}(x)$

这里$f(x)$，$\varphi_{j_{0},k}(x)$和$\psi_{j,k}(x)$是离散变量$x = 0,1,\cdots,M - 1$的函数; $W_{\varphi}(j_{0},k)$, $W_{\psi}(j,k)$对应上面小波序列展开中的$c_{j_{0}}(k)$近似系数(低频部分)，$d_{j}(k)$细节系数(高频部分)。

第四版：感觉更简单一点点。

与傅里叶级数展开类似，上一节的小波级数展开将单个连续变量的函数映射为一系列离散系数。如果被展开的函数是离散的，那么展开的系数就是它们的离散小波变换（DWT），而展开式本身就是函数的逆离散小波变换。

令$j_0 = 0$，并将注意力限制在$N$为2的幂次方（即$N = 2^J$）的$N$点离散函数上，我们得到：
$f(x)=\frac{1}{\sqrt{N}}\left[T_{\varphi}(0,0)\varphi(x)+\sum_{j = 0}^{J - 1}\sum_{k = 0}^{2^{j}-1}T_{\psi}(j,k)\psi_{j,k}(x)\right]$
其中：
$T_{\varphi}(0,0)=\langle f(x),\varphi_{0,0}(x)\rangle=\langle f(x),\varphi(x)\rangle=\frac{1}{\sqrt{N}}\sum_{x = 0}^{N - 1}f(x)\varphi^{*}(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) \quad (7 - 138)$
其中$j = 0,1,\cdots,J - 1$且$k = 0,1,\cdots,2^{j}-1$。由上面公式定义的变换系数分别被称为近似系数和细节系数。

例：计算一维离散小波变换

考虑四点离散函数：$f(0)=1$，$f(1)=4$，$f(2)= - 3$，$f(3)=0$。我们将使用Haar尺度和小波函数，并假设$f(x)$的四个样本分布在基函数的支撑集上。

令$j_{0}=0$，我们可以计算DWT系数为：

$\begin{align} W_{\varphi}(0,0)&=\frac{1}{2}\sum_{x = 0}^{3}f(x)\varphi_{0,0}(x)=\frac{1}{2}[1 + 4 + (- 3)+0]=1\\ W_{\psi}(0,0)&=\frac{1}{2}[1 + 4 + (- 3)\cdot(- 1)+0\cdot(- 1)]=4\\ W_{\psi}(1,0)&=\frac{1}{2}[1\cdot\sqrt{2}+4\cdot(-\sqrt{2})+(- 3)\cdot0+0\cdot0]=- 1.5\sqrt{2}\\ W_{\psi}(1,1)&=\frac{1}{2}[1\cdot0+4\cdot0+(- 3)\cdot\sqrt{2}+0\cdot(-\sqrt{2})]=- 1.5\sqrt{2}\end{align}$

因此，我们的简单四样本函数相对于Haar缩放和小波函数的离散小波变换是$\{1, 4, - 1.5\sqrt{2}, - 1.5\sqrt{2}\}$。由于变换系数是两个变量——尺度$j$和平移$k$的函数，我们将它们组合成一个有序集合。这个集合中的元素与该函数按顺序排列的Haar变换的元素相同：

$t^{H}=\mathbf{A}_{H} f=\frac{1}{2}\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]\left[\begin{array}{c} 1 \\ 4 \\ - 3 \\ 0 \end{array}\right]=\left[\begin{array}{c} 1 \\4\\ - 1.5\sqrt{2} \\ - 1.5\sqrt{2} \end{array}\right]$

回顾上一节，Haar变换是单个变换域变量（记为$u$）的函数。方程:

$f(x)=\frac 1 {\sqrt{M}}\left[W_{\varphi}(0,0)\varphi(x)+\sum^{J-1}_{j=0}\sum^{2^j-1}_{k=0}W_{\psi}(j,k)\psi_{j,k}(x)\right]$

使得能够从其小波变换系数重建原始函数。展开求和式可以构造原始函数：

$f(x)=\frac{1}{2}[W_{\varphi}(0,0)\varphi_{0,0}(x)+W_{\psi}(0,0)\psi_{0,0}(x)+W_{\psi}(1,0)\psi_{1,0}(x)+W_{\psi}(1,1)\psi_{1,1}(x)]$

对于$x = 0$:

$f(0)=\frac{1}{2}[1\cdot1 + 4\cdot1+(- 1.5\sqrt{2})\cdot\sqrt{2}+(- 1.5\sqrt{2})\cdot0]=1$

基本的假设是开始尺度$j_0=0$, 此例的4点DWT是$f(x)$的二尺度分解，即$j=\{0,1\}$.

快速小波变换(The Fast Wavelet Transform)

实现DWT的快速实现。

再次考虑MRA方程:

$\varphi(x)=\sum_{n}h_{\varphi}(n)\sqrt{2}\varphi(2x - n)$

将$x$乘以$2^{j}$，平移$k$，并令$m = 2k + n$，得到 :

$\begin{align}\varphi(2^{j}x - k)&=\sum_{n}h_{\varphi}(n)\sqrt{2}\varphi(2(2^{j}x - k)-n)\\ &=\sum_{n}h_{\varphi}(n)\sqrt{2}\varphi(2^{j+1}x-2k-n)\\ &=\sum_{m}h_{\varphi}(m - 2k)\sqrt{2}\varphi(2^{j + 1}x - m) \end{align}$

对于小波函数，有类似结果：

$\psi(2^{j}x - k)=\sum_{m}h_{\psi}(m - 2k)\sqrt{2}\varphi(2^{j + 1}x - m)$

对于离散小波函数，有：

$W_{\psi}(j,k)=\frac{1}{\sqrt{M}}\sum_{x}f(x)2^{j/2}\psi(2^{j}x - k)$

进一步，有：

$W_{\psi}(j,k)=\frac{1}{\sqrt{M}}\sum_{x}f(x)2^{j/2}\left[\sum_{m}h_{\psi}(m - 2k)\sqrt{2}\varphi(2^{j + 1}x - m)\right]$

交换求和与积分并重新排列项，得到：

$W_{\psi}(j,k)=\sum_{m}h_{\psi}(m - 2k)\left[\frac{1}{\sqrt{M}}\sum_{x}f(x)2^{(j + 1)/2}\varphi(2^{j + 1}x - m)\right]\\ W_{\psi}(j,k)=\sum_{m}h_{\psi}(m - 2k)W_{\varphi}(j + 1,m)\\ 同理,\ W_{\varphi}(j,k)=\sum_{m}h_{\varphi}(m - 2k)W_{\varphi}(j + 1,m)$

上述方程表示了快速小波变换(FWT), 揭示了相邻尺度的离散小波变换（DWT）系数之间的显著关系。

可以看到，尺度$j$的近似系数$W_{\varphi}(j,k)$和细节系数$W_{\psi}(j,k)$都可以通过将尺度$j+1$的近似系数$W_{\varphi}(j + 1,k)$与时间反转的缩放向量$h_{\varphi}(-n)$和小波向量$h_{\psi}(-n)$进行卷积，并对结果进行下采样得到。

T与W同

与两频段子带编译码系统的关系

Q: 两频段子带编译码系统?

A: 是一种将信号分解为低频和高频子带的系统

低通通道（Low-Pass Channel）：对应于尺度滤波器 $h_{\varphi}(n)$，用于提取信号的低频成分。

高通通道（High-Pass Channel）：对应于小波滤波器 $h_{\psi}(n)$，用于提取信号的高频成分。

$\sum_{k}g_{0}(k)h_{0}(n - k)+(-1)^{n}\sum_{k}g_{0}(k)h_{0}(n - k)=2\delta(n)，\delta{(n)}=\begin{cases}1 ,&n=0\\0, &n\neq 0\end{cases}\\ \sum_{k}g_{0}(k)h_{0}(2n - k)=\langle g_{0}(k),h_{0}(2n - k)\rangle=\delta(n)\\ \langle h_{i}(2n - k),g_{j}(k)\rangle=\delta(i - j)\delta(n)\quad i,j\in\{0,1\}$

上述快速小波变换过程与两频段子带编译码系统的分析部分相同，其中:

$h_{0}(n)=h_{\varphi}(-n)\\ h_{1}(n)=h_{\psi}(-n)$

可以写出 :

$W_{\psi}(j,k)=h_{\psi}(-n)\ast W_{\varphi}(j + 1,n)\big|_{n = 2k,k\geq0}\\ W_{\varphi}(j,k)=h_{\varphi}(-n)\ast W_{\varphi}(j + 1,n)\big|_{n = 2k,k\geq0}$

其中卷积在$n = 2k(k\geq0)$时刻进行求值。在非负、偶数时刻，计算卷积与以2为步长进行过滤和抽样的效果相同。

值得注意的是，滤波器组可以“迭代”以创建多级结构，用于计算两个或多个连续尺度的 DWT 系数，如图所示。

例：计算一维小波变换

与上面的例子同：$f(n)=\{1,4,-3,0\}$, 但现在使用相应的尺度和小波向量：

$h_{\varphi}(n)=\begin{cases}\frac{1}{\sqrt{2}},&n=0,1\\0,& otherwise\end{cases}\\\\ h_{\psi}(n)=\begin{cases}\frac{1}{\sqrt{2}},&n=0\\-\frac{1}{\sqrt{2}},&n=1\\0,& otherwise\end{cases}$

这是用于建立FWT滤波器族的函数，它们给出了滤波器系数。

一维快速小波反变换

上采样序列定义为：

$y_{2\uparrow}(n)=\begin{cases}y(n/2),&n是偶数\\0,&其他\end{cases}$

其中$y(n)$是一维取样序列，上采样因子为2。因子2上取样可以被视为在$y(n)$的每个样本后插入一个0.

例：计算一维小波反变换

快速小波反变换的计算与正变换的计算呈镜像关系。在开始计算之前，先对0级近似系数和细节系数进行上取样，分别得到{4,0},{1,0},然后继续向右移动，卷积，最终可以得到$f(x)=T_{\varphi}(2,n)$.

FFT与FWT的区别

计算长度为$M = 2^j$序列的FWT所涉及的数学运算量为$O(M)$阶。
这与FFT算法相比具有优势，FFT算法需要$O(M\log M)$。
虽然傅里叶基函数（即正弦函数）保证了FFT的存在，但FWT的存在取决于所使用小波的缩放函数的可用性，以及缩放函数和相应小波的正交性（或双正交性）。
FFT无法同时在时间和频率上分析函数，但FWT可以。

小波包(Wavelet Packets)

快速小波变换（FWT）将函数分解为尺度和小波函数之和，其中尺度和小波函数的带框呈对数关系。也就是说，函数的低频内容被分组到窄频带(尺度和小波函数)中，而高频内容被分组到较宽的频带(尺度和小波函数)中。

如果我们想要对时频平面的划分进行更精细的控制，FWT必须被推广以产生一种更灵活的分解——称为小波包。

分析树

根节点被赋予最高尺度的近似系数，这些系数是函数本身的样本，而叶子节点继承变换的近似和细节系数输出。注意：每个节点的系数都是线性展开的权重。

例：三尺度分析树

例如，上图中的三尺度分析树提供了以下三种展开选项：

$\begin{align} V_j& = V_{j - 1} \oplus W_{j - 1}\\ V_j &= V_{j - 2} \oplus W_{j - 2} \oplus W_{j - 1}\\ V_j &= V_{j - 3} \oplus W_{j - 3} \oplus W_{j - 2} \oplus W_{j - 1} \end{align}$