从采样定理到多分辨率

PLAN

  • 近似和近似误差
  • Shannon-Whittaker 定理及其推广
  • 多分辨率

近似和近似误差

数据的表示方式

  • 数据属于向量空间（$\mathbb{N}, \mathbb{R}, \mathbb{R}^d$）
  • 对于连续或者离散的信号或图像，可使用希尔伯特空间的元素（正交投影定理 + 希尔伯特基（Hilbert basis））

希尔伯特空间是满足向量加法和数乘的运算规则。定义了具备正定性，线性和共轭对称性的内积。却空间中的每个柯西序列都收敛于空间中的某个元素。

如果两个向量$x$，$y$满足$\langle x, y\rangle=0$，则称它们是正交的。构成空间的基的正交向量系统被称为希尔伯特基。

  • 数据存在压缩的可能

自然表示法 Natural representation

图像是一个像素矩阵，每个像素通过一个颜色空间（color space，例如 RGB、CMYK、Lab、CIE XYZ 等）以规定的比特数进行编码（例如，RGB 颜色空间中，每个像素需要$3\times 8 = 24$位。

考虑一部1080p的电影，每一帧的大小为：$1920\times 1080\times 8\times 3 = 6MB$，也就是说一小时的电影位540GB。

因此压缩是必要的。

观察图像的傅里叶变化

自然图像的傅里叶变换通常分布在低频。

也就是说，存在一种可能。即我们找到一个正交归一基，使得原本的图片可以被表示为：

这样的形式，且求和只包含重要的项。

近似 approximation

定义

设 $B=\left(en\right){n \in \mathbb{N}}$是一个可分希尔伯特空间的希尔伯特基（Hilbert basis）。函数 $f \in E$ 的线性近似（linear approximation）是 $f$ 在由 $B$ 的前 $N$ 个元素张成的有限维空间上的正交投影 $f_N$（不失一般性的）：

近似误差 error of approximation

近似误差被定义为：

Shannon-Whittaker 定理及其推广

采样规则 Regular Sampling

符号定义

对于$f\in L^2, T>0$，定义采样：

其中$\delta_{nT}$是$nT$处的狄拉克函数。

$\hat{f}_T$是$f_T$的傅里叶变换，其表达式为：

Shannon-Whittaker 定理

命题

对于所有$\omega\in \mathbb R$，有：

通过间隔$T$对$f$进行规则采样，其傅里叶变换将呈现出$2\pi/T$周期性。

引理：狄拉克梳函数的傅里叶变换

证明：

令$f(t)$是一个周期为$T$的函数，并考虑其傅里叶级数：

根据傅里叶变换的性质：

因此：

对于梳函数$f=\sum{n=-\infty}^{+\infty} \delta{n T}$，有$c_n=\frac{1}{T}$。因此：

推广

对于有紧支撑弗利特变换的$f$，可以写为：

同样，可以将其傅里叶变换$\hat f$写作：

根据引理，有：

更进一步的，对于$u\in S^{‘}$ ，当$u$与一个狄拉克函数$\delta_a$卷积，相当于对$u$进行平移：

其中，$\tau_a$是平移算子。即可证明：

定理

令$V_T$为所有满足傅里叶变换支撑在区间$[-\pi / T, \pi / T]$中的$L^2$函数的空间。如果$f\in V_T$，则对所有$t\in \mathbb R$，有：

其中：

证明

假设 $\hat{f}$ 和 $\hat{f}\left(\cdot-\frac{2 k \pi}{T}\right)$ 对于 $k \neq 0$ 的支撑互不重叠。则在 $|\omega| \leq \pi / T$ 上，有：

中，对于$k\ne 0$，有$\hat{f}\left(\omega-\frac{2 k \pi}{T}\right)\ne\hat{f}(\omega)$，而当$k\ne 0$时，$\hat{f}\left(\omega-\frac{2 k \pi}{T}\right)$对$|\omega| \leq \frac{\pi}{T}$没有贡献。因此有：

设$\widehat{f}(\omega)=\hat{h}T(\omega) \hat{f}_T(\omega)$，其中$\widehat{h}_T=T \mathbb{1}{[-\pi / T, \pi / T]}$。

对于$t\in \mathbb R$，有：

其中，

结论

在信号处理中，Shannon－Whittaker定理指出，属于 $V_T$ 的函数 $f$ 可以通过以规则间隔栗样完全重建。

实际上，这一结果表明，以下集合：

是 $V_T$ 的一个Hilbert基。

其中：

具体来说，由于 $\hat{h}T=T 1{[-\pi / T, \pi / T]}$ ，我们可以验证：对于所有 $f \in V_T$ ，有：

以及，Parseval恒等式：

如果 $f \in L^2$ 但 $f \notin V_T$

  • 我们可以通过考虑正交投影 $\hat{f} = P_{V_T}f$，构造一个 $f$ 的近似 $\hat{f}$。

  • $\hat{f}$ 可以通过在频域中进行滤波简单地获得：

  • 正交投影 $\hat{f}$ 会最小化 $| f - \hat{f} |$。

  • 然而，这并不意味着 $\hat{f}$ 在实际中是好的近似。它会去除混叠（Aliasing），但会产生Gibbs效应（Gibbs Effect）。

其他采样定理

所谓的其他采样定理，即找到其他$h_T$和$V_T$，使得：

分段常数函数 Piecewise constant functions

考虑 $hT=1{[0, T[}$

集合 $\left{hT(\cdot-n T)\right}{n \in \mathbb{Z}}$ 在 $L^2(\mathbb{R})$ 中是正交的。进一步，由于 $\left|h_T(\cdot-n T)\right|^2=T$ ，集合：

是一个正交归一集合。

用 $VT$ 表示由 $\left{\operatorname{span} h_T(\cdot-n T)\right}{n \in \mathbb{Z}}$ 组成的Hilbert和（ $B$ 是 $V_T$ 的Hilbert基）。$V_T$ 中的函数是定义在区间 $[n T,(n+1) T[$ 上的分段常数函数。

对于所有 $f \in V_T$ ：

Parseval恒等式：

当 $f \notin VT$ 时，我们仍然可以构造 $f$ 的一个近似 $\hat{f}=P{V_T} f$ ，使得 $|f-\hat{f}|$ 最小。
有：

其中：

分段线性函数 Piecewise linear functions

考虑 $hT=\mathbb{1}{[0, T[ } \star \mathbb{1}_{[0, T[ }$

函数 $f=\sum_{n \in \mathbb{Z}} f(n T) h_T(\cdot-n T)$ 是定义在区间 $[n T,(n+1) T[$ 上的分段线性函数。

这定义了另一个 $VT$ 空间，使得 $f \in V_T$ 的函数可以通过规则采样精确重建。同样地，如果 $f \notin V_T$ ，我们仍然可以构造一个近似 $P{V_T} f$ 。

如果我们希望通过函数 $f$（信号或图像）的规则网格值（步长为 $T$）在计算机中存储 $f$，只要 $f \in V_T$，我们就可以完美地重建 $f$。

为了最小化信息丢失，即最小化 $|f - P_{V_T}f|$，我们可能需要选择较小的 $T$ 值（对应高分辨率）。

反之，如果我们希望压缩信号或图像，可以使用较粗的网格，即降低分辨率，在对信号进行某种低通滤波或局部平均后进行下采样。

为了解决这个问题，我们希望构造一种自适应非均匀网格，在信号快速变化的区域使用更精细的网格。

实现这一目标的一种方法是构造一个多分辨率网格层次结构：

这就是构造小波（Wavelets）的主要思想。

多分辨率：函数表示与压缩问题的尺度空间方法

目标是构建一个Hilbert基，设计如下形式的基函数：

其中$j,n\in\mathbb Z$，通过缩放参数$s = 2^j$和平移参数$ns$得到。缩放因子相当于之前的$T$。这使得可以在不同尺度$s$ 上对信号进行近似，并通过一系列Hilvert子空间描述信号。

多分辨率 mulyisolution

一个 $\left(V_j\right){j \in \mathbb{Z}}$ 的 $L^2(\mathbb{R})$ 的Hilbert子空间序列是一个多分溯率
（Multiresolution），如果它满足以下六个性质（对所有 $j, n \in \mathbb{Z}$ ）：

  • $f \in V_j \Longleftrightarrow f\left(\cdot-2^j n\right) \in V_j$
    • $V_j$ 是关于与 $2^j$ 成比例的平移不变的；这一假设定义了一个步长为 $s = 2^j$ 的统一网格，对应于在尺度 $2^j$ （或分辨率 $2^{-j}$）上构造近似。
  • $f \in V_j \Longleftrightarrow f(\cdot / 2) \in V{j+1}$（扩展比例为2）
    • $Vj$ 的函数扩展将生成在 $V{j+1}$ 中的函数，具有较粗的分辨率。
  • $V_{j+1} \subset V_j$
    • 低分辨率空间包含在高分辨率空间中；这些空间是嵌套的。

  • $\lim {j \rightarrow-\infty} V_j=\overline{\bigcup{j=-\infty}^{\infty} V_j}=L^2(\mathbb{R})$

    • 当分辨率趋于 $+\infty$ （尺度趋于零）时，对于所有 $f \in L^2(\mathbb{R})$，有：

  • $\lim {j \rightarrow+\infty} V_j=\bigcap{j=-\infty}^{\infty} V_j={0}$

    • 分辨率趋于零时，所有的细节将丢失：

  • 存在 $\theta \in L^2(\mathbb{R})$ ，使得 $(\theta(\cdot-n))_{n \in \mathbb{Z}}$ 是 $V_0$ 的 Riesz基。

    • Riesz 基的定义
      令$(\theta(\cdot-n))_{n \in \mathbb{Z}}$ 是 $L^2(\mathbb{R})$ 的一组线性无关的函数序列。如果存在常数 $A, B > 0$，满足对于 $V_0$ 中的任意函数 $f$，存在一个序列 $(a_n){n \in \mathbb{Z}} \in \mathbb{R}$，使得：

    • 且满足：

    • 则序列$(\theta(\cdot-n))_{n \in \mathbb{Z}}$是Riesz基。

  • Riesz基类似于Hilbert基，但放宽了正交性假设。
  • 当 $A = B = 1$ 时，$(\theta(\cdot - n))_{n \in \mathbb{Z}}$ 是 $V_0$ 的Hilbert基。

  • 很容易验证，序列

    是 $V_j$ 的Riesz基，其界限 $A$ 和 $B$ 在所有尺度 $2^j$ 上相同。

示例

分段常数多分辨率

  • 选择 $\theta = 1{[0,1[}$，于是 $(\theta(\cdot - n)){n \in \mathbb{Z}}$ 是 $L^2(\mathbb{R})$ 的Hilbert子空间 $V_0$ 的Hilbert基，其中每个分段常数函数定义在区间 $[n, n+1[$ 上。
  • 每个 $V_j$ 是 $L^2(\mathbb{R})$ 的Hilbert子空间，其上的函数在区间 $[2^j n, 2^j(n+1)[, n \in \mathbb{Z}$ 内为常数。
  • 显然，$Vj \subset V{j-1}$，因为在较大区间上为常数的函数也在较小区间上为常数。

Shannon多分辨率

  • 选择 $\theta : t \mapsto \frac{\sin(\pi t)}{\pi t}$，于是 $(\theta(\cdot - n))_{n \in \mathbb{Z}}$ 是 $L^2(\mathbb{R})$ 的Hilbert子空间 $V_0$ 的Hilbert基，其中函数的傅里叶变换支撑在 $[-\pi, \pi]$ 内。
  • 每个 $V_j$ 是 $L^2(\mathbb{R})$ 的函数集合，其傅里叶变换支撑在 $[-2^j \pi, 2^j \pi]$ 内。

样条多分辨率 Spline multiresolution

  • 定义一个阶数为 $m$ 的box样条 $\thetam$，通过将box $\theta_0 = 1{[0,1[}$ 与自身卷积 $m$ 次，并以0或1/2为中心。
  • 当 $m$ 为偶数时，$\theta_m$ 的支撑以 $t = 1/2$ 为中心。
  • 当 $m$ 为奇数时，$\theta_m$ 的支撑以 $t = 0$ 为中心，且对称。
  • 对于所有 $m \geq 0$，$(\thetam(\cdot - n)){n \in \mathbb{Z}}$ 是 $L^2$ 空间 $V_0$ 的Riesz基，其上的函数是分段多项式（阶数为 $m$），定义在区间 $[n, n+1[$，且连续可微 $m-1$ 次。
  • 当 $m > 0$ 时，计算 $P_{V_j} f$ 并不简单。