从采样定理到多分辨率

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。

因此压缩是必要的。

---

观察图像的傅里叶变化

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

---

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

\[ f=\sum\left(f, e_n\right) e_n \]

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

近似 approximation

---

定义

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

\[ f_N = \sum_{n=0}^{N-1} (f, e_n)e_n \]

---

近似误差 error of approximation

近似误差被定义为：

\[ \varepsilon_1(N)=\left\|f-f_N\right\|^2=\sum_{n=N}^{+\infty}\left|\left(f, e_n\right)\right|^2 \]

Shannon-Whittaker 定理及其推广

---

采样规则 Regular Sampling

---

符号定义

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

\[ f_T=\sum_{n=-\infty}^{+\infty} f(n T) \delta_{n T} \]

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

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

\[ \hat{f}_T(\omega)=\sum_{n=-\infty}^{+\infty} f(n T) e^{-i n T \omega} \]

Shannon-Whittaker 定理

---

命题

对于所有\(\omega\in \mathbb R\)，有：

\[ \hat{f}_T(\omega)=\sum_{n=-\infty}^{+\infty} f(n T) e^{-i n T \omega}=\frac{1}{T} \sum_{k=-\infty}^{+\infty} \hat{f}\left(\omega-\frac{2 k \pi}{T}\right) \]

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

---

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

\[ \mathcal{F}\left\{\sum_{n=-\infty}^{+\infty} \delta_{n T}\right\}=\sum_{n=-\infty}^{+\infty} e^{-i n T \omega}=\frac{2 \pi}{T} \sum_{k=-\infty}^{+\infty} \delta_{\frac{2 \pi k}{T}}(\omega) \]

证明：

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

\[ \omega_0=\frac{2 \pi}{T}, \quad c_n=\frac{1}{T} \int_T f(t) e^{-i n \omega_0 t} d t \]

根据傅里叶变换的性质：

\[ \mathcal{F}\{f(t)\}=\mathcal{F}\left\{\sum_{n=-\infty}^{+\infty} c_n e^{i n \omega_0 t}\right\}=\sum_{n=-\infty}^{+\infty} c_n \mathcal{F}\left\{e^{i n \omega_0 t}\right\} \]

因此：

\[ \hat{f}(\omega)=2 \pi \sum_{n=-\infty}^{+\infty} c_n \delta_{n \omega_0}(\omega) \]

对于梳函数\(f=\sum_{n=-\infty}^{+\infty} \delta_{n T}\)，有\(c_n=\frac{1}{T}\)。因此：

\[ \mathcal{F}\left\{\sum_{n=-\infty}^{+\infty} \delta_{n T}\right\}=\frac{2 \pi}{T} \sum_{n=-\infty}^{+\infty} \delta_{n \omega_0}(\omega) \]

---

推广

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

\[ f_T=f \cdot c_T, \quad c_T=\sum_{n=-\infty}^{+\infty} \delta_{n T} \]

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

\[ \hat{f}_T=\frac{1}{2 \pi} \hat{f} * \hat{c}_T \]

根据引理，有：

\[ \hat{c}_T=\frac{2 \pi}{T} \sum_{k=-\infty}^{+\infty} \delta_{\frac{2 \pi k}{T}}(\omega) \]

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

\[ u * \delta_a=\tau_a u \]

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

\[ \hat{f}_T(\omega)=\frac{1}{T} \sum_{k=-\infty}^{+\infty} \hat{f}\left(\omega-\frac{2 k \pi}{T}\right) \]

---

---

定理

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

\[ f(t)=\sum_{n=-\infty}^{\infty} f(n T) h_T(t-n T) \]

其中：

\[ h_T(t)=\frac{\sin (\pi t / T)}{\pi t / T} \]

---

证明

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

\[ \hat{f}_T(\omega)=\frac{1}{T} \sum_{k=-\infty}^{+\infty} \hat{f}\left(\omega-\frac{2 k \pi}{T}\right) \]

中，对于\(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}\)没有贡献。因此有：

\[ \hat{f}_T(\omega)=\frac{1}{T} \hat{f}(\omega) \]

设\(\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\)，有：

\[ \begin{aligned}f(t) & =\left(h_T \star f_T\right)(t) \\& =\left(h_T \star \sum_{-\infty}^{\infty} f(n T) \delta_{n T}\right)(t) \\& =\sum_{-\infty}^{\infty} f(n T) h_T(t-n T)\end{aligned} \]

其中，

\[ h_T(t)=\frac{\sin (\pi t / T)}{\pi t / T} \]

---

结论

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

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

\[ B=\left\{\frac{1}{T^{1 / 2}} h_T(\cdot-n T)\right\}_{n \in \mathbb{Z}} \]

是 \(V_T\) 的一个Hilbert基。

其中：

\[ h_T(t)=\frac{\sin (\pi t / T)}{\pi t / T} \]

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

\[ \begin{aligned} \left(f, \frac{1}{T^{1 / 2}} h_T(\cdot-n T)\right) & =\frac{1}{2 \pi T^{1 / 2}} \int_{-\infty}^{\infty} \widehat{f}(\omega) \widehat{h}_T(\omega) e^{\mathrm{i} n T \omega} \mathrm{~d} \omega \\ & =\frac{T^{1 / 2}}{2 \pi} \int_{-\infty}^{\infty} \widehat{f}(\omega) e^{\mathrm{i} n T \omega} \mathrm{~d} \omega=T^{1 / 2} f(n T) \end{aligned} \]

\[ \begin{aligned}\left(\frac{1}{T^{1 / 2}} h_T(\cdot-m T), \frac{1}{T^{1 / 2}} h_T(\cdot-n T)\right) & =h_T((n-m) T) \\& =\mathbb{1}_{\{n=m\}}\end{aligned} \]

以及，Parseval恒等式：

\[ \begin{aligned} f & =\sum_{n=-\infty}^{\infty} f(n T) h_T(\cdot-n T) \\ & =\sum_{n=-\infty}^{\infty}\left(f, \frac{1}{T^{1 / 2}} h_T(\cdot-n T)\right) \frac{1}{T^{1 / 2}} h_T(\cdot-n T) \end{aligned} \]

---

如果 \(f \in L^2\) 但 \(f \notin V_T\)

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

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

  \[ \hat{\widehat{f}} = 1_{[-\pi/T, \pi/T]} \hat{f} \]

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

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

其他采样定理

---

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

\[ f \in V_T \Longrightarrow f=\sum_n f(n T) h_T(\cdot-n T) \]

---

分段常数函数 Piecewise constant functions

考虑 \(h_T=1_{[0, T[}\)

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

\[ B=\left\{\frac{1}{T^{1 / 2}} h_T(\cdot-n T)\right\}_{n \in \mathbb{Z}} \]

是一个正交归一集合。

用 \(V_T\) 表示由 \(\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\) ：

\[ \left(f, T^{-1 / 2} h_T(\cdot-n T)\right)=T^{1 / 2} f(n T) \]

Parseval恒等式：

\[ f=\sum_{n \in \mathbb{Z}} f(n T) h_T(\cdot-n T) \]

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

\[ P_{V_T}(f)=\frac{1}{T} \sum_{n \in \mathbb{Z}}\left(f, h_T(\cdot-n T)\right) h_T(\cdot-n T) \]

其中：

\[ \frac{1}{T}\left(f, h_T(\cdot-n T)\right)=\frac{1}{T} \int_{n T}^{(n+1) T} f(t) d t \quad(f \text { 的平均值 }) \]

---

分段线性函数 Piecewise linear functions

考虑 \(h_T=\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[\) 上的分段线性函数。

这定义了另一个 \(V_T\) 空间，使得 \(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基，设计如下形式的基函数：

\[ \phi_{j, n}(t)=\frac{1}{\sqrt{2^j}} \phi\left(\frac{t-2^j n}{2^j}\right) \]

其中\(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）

  • \(V_j\) 的函数扩展将生成在 \(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 \to -\infty} \|f - P_{V_j} f\| = 0 \]

• \(\lim _{j \rightarrow+\infty} V_j=\bigcap_{j=-\infty}^{\infty} V_j=\{0\}\)

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

  \[ \lim_{j \to +\infty} P_{V_j} f = 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}\)，使得：

    \[ f = \sum_{n = -\infty}^\infty a_n \theta(\cdot - n) \]

  • 且满足：

    \[ A \|f\|^2 \leq \sum_{n = -\infty}^\infty |a_n|^2 \leq B \|f\|^2 \]

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

---

• Riesz基类似于Hilbert基，但放宽了正交性假设。

• 当 \(A = B = 1\) 时，\((\theta(\cdot - n))_{n \in \mathbb{Z}}\) 是 \(V_0\) 的Hilbert基。

• 很容易验证，序列

  \[ \left( 2^{-j/2} \theta(2^{-j} \cdot - n) \right)_{n \in \mathbb{Z}} \]

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