计算机图形学基础-10-信号处理

《Fundamentals of Computer Graphics》5th（计算机图形学基础/虎书），中文翻译。

第 10 章 Signal Processing 信号处理

在图形学中，我们经常处理连续变量的函数：图像是你看到的第一个示例，但继续探索图形学后，你会遇到更多。由于其特有的性质，连续函数 (continuous functions) 无法直接在计算机中表示；我们必须以某种方式使用有限数量的位 (bits) 来表示它们。表示连续函数最有用的方法之一是使用函数的样本 (samples)：只需存储许多不同点上的函数值，并在需要时使用这些点重建 (reconstruct) 出函数的走势。

译者注：寻找若干个离散的点来表示连续函数的特征，这个过程称为“采样”。

你现在已经熟悉使用像素的二维坐标系来表示图像（光栅化），因此你已经看到了一个采样的例子！想象一下数字相机拍摄的图像：相机镜头形成的场景的实际图像是位置到图像平面上的函数，而相机将该函数转换为样本的二维坐标系。从数学上讲，相机将类型为 $\Bbb{R}^2 \rightarrow \bold C$ （其中 C 是颜色集）的函数转换为颜色样本的二维数组，即类型为 $\Bbb{Z}^2 \rightarrow \bold C$ 的函数。

另一个采样表示的例子是 2D 数字化平板，例如平板电脑屏幕或艺术家使用的绘板。在这种情况下，原始函数是笔尖的运动，即 2D 位置随时间变化的函数（类型为 $\Bbb{R} \rightarrow \Bbb{R}^2$ ）。数字化器在许多时间点上测量笔尖的位置，从而产生一系列 2D 坐标，或者类型为 $\Bbb{Z} \rightarrow \Bbb{R}^2$ 的函数。运动捕捉系统对于固定在演员身上的特殊标记也是完全相同的：它获取标记在时间上的 3D 位置（ $\Bbb{R} \rightarrow \Bbb{R}^3$ ）并将其转换为瞬时位置测量序列（ $\Bbb{Z} \rightarrow \Bbb{R}^3$ ）。

在维度上升之后，医用 CT 扫描仪用于非侵入性地检查人体内部，测量密度作为身体内部位置的函数。扫描仪的输出是一个密度值的 3D 网格：它将身体的密度（ $\Bbb{R}^3 \rightarrow \Bbb{R}$ ）转换为实数的 3D 数组（ $\Bbb{Z}^3 \rightarrow \Bbb{R}$ ）。

这些示例看起来不同，但实际上可以完全使用相同的数学方法处理。在所有情况下，都需要在一个或多个维度上对一组点进行函数采样，并且我们需要能够从这些样本的数组中重新构建出原始连续函数（或者是表现出原始函数的特征）。

从 2D 图像的例子可以看出，一旦相机对图像进行了离散化，似乎像素就足够了，我们永远不需要再考虑连续函数。但是，如果我们想通过非整数缩放因子在屏幕上放大或缩小图像呢？事实证明，最简单的算法表现很差，引入明显的视觉伪影，称为走样。解释走样发生的原因并理解如何防止它需要采样理论的数学知识。由此得出的算法相当简单，但是它们背后的推理以及使它们良好运行的详细信息可能会比较微妙。

在计算机中表示连续函数当然不仅适用于图形学；采样和重建的概念也是如此。采样表示在从数字音频到计算物理的应用中都有使用，并且图形学只是相关算法和数学的一个用途（而且远非第一个）。自 20 世纪 20 年代以来，关于如何进行采样和重建的基本事实在通信领域已经被人们所熟知，并且在 1940 年代以正好我们现在使用的形式陈述出来（Shannon＆Weaver，1964）。

本章首先通过具体的一维数字音频示例总结采样和重建的过程。然后，我们将介绍支撑一维和二维采样和重建的基本数学和算法。最后，我们将深入探讨频域视角的细节，这提供了许多有关这些算法行为的见解。

10.1 一维数字音频采样

虽然采样表示已经在通信领域使用多年，但 1982 年推出的紧凑型光盘是第一个高度可见的消费者采样应用，这是继上个十年数字音频记录的增加之后。

在音频录制中，麦克风将存在于空气中的压力波转换为随时间变化的电压，这相当于测量了麦克风位置处不断变化的气压。需要以某种方式存储该电信号，以便可以在稍后的时间进行播放，并将其发送到扬声器，扬声器通过与电压同步移动振膜来将电压再次转换为压力波。

数字记录音频信号（图 10.1）的方法使用采样：模拟到数字转换器（A/D 转换器）每秒测量电压数千次，生成一系列整数，可以轻松地存储在任何媒体上，例如在录音室计算机上的磁盘，或者发送到另一个位置，例如便携式音频播放器的内存中。在播放时间，数据以适当的速率读取并发送到数字到模拟转换器（D/A 转换器）。D/A 转换器根据接收到的数字产生电压，并且只要我们取足够的样本来公平地表示电压的变化，那么所得到的电信号在所有实际情况下都与输入相同。

图 10.1：数字音频中的采样和重建。

事实证明，为了获得良好的音频复制所需的每秒采样数取决于我们试图记录的声音有多高。对于复制低音提琴或重音鼓的采样率可以正常工作，但是如果我们尝试录制短笛或钹，将会产生奇怪的结果；但是这些声音使用更高的采样率可以很好地复制。为避免这些欠采样伪像，数字音频记录器会过滤 ADC 的输入以消除可能会引起问题的高频率。

另一种问题在输出端出现。 DAC 每当收到新样本时就会产生一个变化的电压，但在下一个样本之前保持不变，从而产生阶梯状的图形。这些台阶状图案就像噪声一样，添加了高频、信号相关的嗡嗡声。为了消除这种重建伪影，数字音频播放器会对 DAC 的输出进行滤波以平滑波形。

10.1.1 采样伪影和走样 (Sampling Artifacts and Aliasing)

数字音频记录链可以作为图形中发生采样和重建过程的具体模型。在图形中，也会出现与音频类似的欠采样和重建伪影，解决方案也是相同的：在采样前进行滤波，并在重建期间再次滤波。

图 10.2 展示了欠低采样频率可能产生的伪影示例。在此示例中，我们使用两种不同的采样频率对简单的正弦波进行采样：在上方，是 10.8 个样本每个周期；在下方，是 1.2 个样本每个周期。较高的采样频率产生了一组明显能够很好捕捉信号的样本；但是，较低采样率产生的样本却和低频正弦波的样本无法区分。事实上，面对这组样本，人们更可能将其解释为低频正弦波的采样。

图 10.2：以两种不同的采样率采样的正弦波（蓝色曲线）。（a）在高采样率下，产生的样本（黑点）可以很好地表示信号。（b）较低的采样率会产生一个模棱两可的结果：样本与从低频率波形（虚线曲线）进行采样得到的样本完全相同。

一旦采样完成，就无法知道这两个信号中的哪一个 —— 快速或慢速正弦波是原始信号，因此，没有单一的方法可以正确地重建这两种情况下的信号。由于高频信号“假装”成低频信号，因此这种现象被称为走样 (aliasing)。

走样出现在采样和重建中的缺陷导致在意料之外的频率产生伪像时。在音频中，走样会以奇怪的额外音调形式出现 —— 在 8KHz 采样后，铃声变成了一个 6KHz 的音调。在图像中，走样通常以 moire 图案的形式出现，这是由于样本网格与图像中的规则特征（例如图 10.34 中的百叶窗）相互作用所产生的。

另一个合成图像中走样的例子是仅使用黑色和白色像素渲染的直线上的熟悉的阶梯状图案（图 10.34）。这是小尺度特征（线的锐利边缘）在不同尺度上产生伪影的例子（对于浅斜率的线，台阶很长）。

采样和重建的基本问题可以简单地理解为特征过小或过大，但一些更定量的问题则难以回答：

什么样的采样率足够高以确保良好的结果？
哪些类型的滤波器适用于采样和重建？
需要多少程度的平滑处理才能避免走样？

对这些问题的明确答案将等到我们在第 10.5 节中充分发展了理论。

10.2 卷积 (Convolution)

在讨论采样和重建算法之前，我们首先要研究它们所基于的数学概念 —— 卷积。卷积是一种简单的数学概念，它是用于采样、滤波和重建的算法的基础，并且也是我们将在本章中分析这些算法的基础。

卷积是对函数进行操作的：它将两个函数组合起来生成一个新函数。在本书中，卷积运算符用星号表示：应用卷积到函数 $f$ 和 $g$ 的结果为 $f * g$ 。我们说 $f$ 与 $g$ 进行了卷积， $f * g$ 是 $f$ 和 $g$ 的卷积。

卷积可以应用于连续函数（对于任何实参 x 定义的函数 $f(x)$ ）或离散序列（仅对整数参数 i 定义的函数 $a[i]$ ）中。它还可以应用于定义在一维、二维或高维域上的函数（即一个、两个或多个参数的函数）。我们将首先从离散的一维情况开始，然后继续到连续函数和二维、三维函数。

为了方便起见，在定义中，我们通常假设函数的域无限延伸，尽管在实践中它们必须在某个地方停止，而且我们必须以特殊的方式处理端点。

10.2.1 移动平均值

为了对卷积有一个基本的认识，考虑使用移动平均法来平滑一维函数的示例（图 10.3）。为了在任何点获得平滑值，我们计算函数在每个方向上扩展 r 距离的范围内的平均值。距离 r 称为平滑操作的半径，它是控制平滑程度的参数。

我们可以用离散或连续函数的形式数学地表达这个想法。如果我们正在平滑连续函数 $g(x)$ ，则平均意味着对 $g$ 在区间上进行积分，然后除以该区间的长度：

图 10.3：使用移动平均法进行平滑处理。

h(x)=\frac{1}{2 r} \int_{x-r}^{x+r} g(t) d t

另一方面，如果我们正在平滑离散函数 a[i]，则平均意味着对一系列索引的 a 求和，然后除以值的数量：

c[i]=\frac{1}{2 r+1} \sum_{j=i-r}^{i+r} a[j] \tag{10.1}

在每种情况下，标准化常数被选择为使得如果我们平滑一个常量函数，结果将是相同的函数。

这个移动平均值的想法是卷积的本质；唯一的区别在于，在卷积中，移动平均值是加权平均值。

10.2.2 离散卷积

我们将从最具体的卷积情况开始：将离散序列 $a[i]$ 与另一个离散序列 $b[i]$ 进行卷积。结果是一个离散序列 $(a \star b)[i]$ 。这个过程就像使用移动平均法对 $a$ 进行平滑处理，但这一次，我们使用第二个序列 $b$ 来为每个样本赋予权重（图 10.4）。值 $b[i-j]$ 给出了位置 $j$ 处样本的权重，该位置距离我们正在评估卷积的索引 $i$ 有距离 $i-j$ 。以下是 $(a \star b)$ 的定义，用公式表示：

图 10.4：计算序列 $a$ 与宽度为五个样本的滤波器 $b$ 进行离散卷积的一个值。 $a \star b$ 中的每个样本都是由加权的邻近样本在 $a$ 中的平均值组成，其权重由 $b$ 的值确定。

(a \star b)[i]=\sum_{j} a[j] b[i-j] \tag{10.2}

通过省略 j 的边界，我们指出这个总和覆盖了所有整数（即从-∞到+∞）。图 10.4 说明了如何使用 $b={1 \over 16}[…,0,1,4,6,4,1,0,...]$ 来计算一个输出样本——也就是说， $b[0]=6/16$ ， $b[±1]=4/16$ 等等。

在图形学中，两个函数中的一个通常会具有有限支持（如图 10.4 中的示例），这意味着它仅在一定的自变量值区间内非零。如果我们假设 $b$ 具有有限支持，则存在一些半径 $r$ ，使得当 $|k|>r$ 时， $b[k]=0$ 。

(a \star b)[i]=\sum_{j=i-r}^{i+r} a[j] b[i-j],

在这种情况下，我们可以将上面的总和写成：

卷积滤波器

卷积很重要，因为我们可以使用它来执行滤波操作。回顾我们第一个滤波示例——移动平均法，我们现在可以将该平滑操作重新解释为与特定序列进行卷积。当我们计算一些索引的有限范围内的平均值时，这就相当于将该范围内的点全部以相同的权重加权，而将其余点加权为零。这种滤波器，在非零区间内具有常量值的，被称为矩形滤波器（因为如果你画出它的图像，它看起来像一个矩形 —— 见图 10.5）。对于半径 $r$ 的矩形滤波器，其权重为 $1/(2r+1)$ ：

b[k]=\left\{\begin{array}{ll} \frac{1}{2 r+1} & -r \leq k \leq r \\ 0 & \text { otherwise } \end{array}\right.

图 10.5：一个离散的矩形滤波器。

如果你将这个滤波器代入方程 (10.2)，你会发现它简化为方程 (10.1) 中的移动平均值。

就像这个例子一样，卷积滤波器通常被设计成它们总和为 1。这样，它们不会影响信号的整体水平。

示例 20（矩形和阶跃函数的卷积）

举一个简单的滤波示例，假设信号是阶跃函数

a[i]=\left\{\begin{array}{ll} 1 & i \geq 0 \\ 0 & i<0 \end{array}\right.

并且滤波器是以零为中心的五点矩形滤波器，

b[k]=\frac{1}{5}\left\{\begin{array}{ll} 1 & -2 \leq k \leq 2 \\ 0 & \text { Otherwise } \end{array}\right.

将 $a$ 和 $b$ 进行卷积的结果是什么？在特定的索引 $i$ 处，如图 10.6 所示，结果是在从 $i-2$ 到 $i+2$ 的范围内对阶跃函数求平均值。如果 $i < -2$ ，则平均所有为零的值，结果为零。如果 $i≥2$ ，则平均所有为一的值，结果为一。在两者之间，有 $i+3$ 个 $1$ ，导致输出值为 $i+3 \over 5$ 。输出是一个线性斜坡，在五个样本中从 0 到 1： ${1 \over 5}[…,0,0,1,2,3,4,5,5,...]$ 。

图 10.6: 对于示例 20 的卷积计算，蓝色代表滤波器 b，红色代表输入序列 a，绿色代表卷积结果。（图片来源：《计算机图形学：实践与原理》）

卷积的特性

到目前为止，我们写的方式使得卷积似乎是一种不对称的操作： $a$ 是我们要平滑的序列，而 $b$ 提供权重。但卷积的一个好的特性是实际上哪个是哪个并没有什么区别：滤波器和信号是可以互换的。为了看到这一点，只需重新考虑方程 (10.2) 中的总和，其中的指标从滤波器 $b$ 的原点开始计数，而不是从 $a$ 的原点开始计数。也就是说，我们用 $i-k$ 代替 $j$ 。这种变量的改变的结果是

\begin{aligned} (a \star b)[i] & =\sum_{k} a[i-k] b[i-(i-k)] \\ & =\sum_{k} b[k] a[i-k] . \end{aligned}

这与方程 (10.2) 完全相同，但是 $a$ 充当滤波器， $b$ 充当信号。因此，对于任何序列 $a$ 和 $b$ ， $(a \star b) = (b \star a)$ ，我们说卷积是一种可交换的操作。

你可能已经注意到，卷积总和中的一个函数似乎是翻转过来的——也就是说， $b[k]$ 给出了 $k$ 个单位之前的样本的权重，而 $b[–k]$ 给出了 $k$ 个单位之后的样本的权重。这样做的原因与确保结合性有关；请参见练习 4。我们使用的大多数滤波器都是对称的，因此你几乎不需要担心这个问题。

更一般地说，卷积是一种“类乘法”的操作。就像数字或函数的乘法或加法一样，参数的顺序或括号的位置都不会影响结果。此外，卷积关于加法的关系与乘法相同。准确来说，卷积是可交换的和可结合的，并且在加法上是分配的。

交换律：\quad(a \star b)[i]=(b \star a)[i] \\ 结合律：\quad(a \star(b \star c))[i]=((a \star b) \star c)[i] \\ 分配律：\quad(a \star(b+c))[i]=(a \star b+a \star c)[i]

如果我们将卷积看作类似于乘法，那么这些特性就非常自然了。这些特性非常有用，因为它们可以帮助我们在实际计算卷积之前简化卷积以节省工作量。例如，假设我们想要对序列 $a$ 进行三个滤波器 $b1$ 、 $b2$ 和 $b3$ 的卷积——也就是说，我们想要 $((a \star b1) \star b2) \star b3$ 。如果序列很长，而滤波器很短（即它们具有较小的半径），那么首先将三个滤波器卷积在一起（计算 $b1 \star b2 \star b3$ ）会更快，最后再将结果与信号进行卷积，计算 $a \star (b1 \star b2 \star b3)$ ，我们知道根据结合律可以得到相同的结果。

一个非常简单的滤波器可作为离散卷积的恒等元：它是半径为零的离散滤波器，或者序列 $d[i]=..., 0, 0, 1, 0, 0,...$ （见图 10.7）。如果我们将 $d$ 与信号 $a$ 进行卷积，总和中只会有一个非零项：

\begin{aligned} (a \star d)[i] & =\sum_{j=i}^{j=i} a[j] d[i-j] \\ & =a[i] . \end{aligned}

图 10.7：一个离散的单位脉冲函数，也称为 Kronecker delta 函数。

因此，很明显，用 $d$ 对 $a$ 进行卷积只会得到 $a$ 本身。序列 $d$ 被称为离散脉冲响应。它偶尔在表示滤波器时很有用：例如，使用滤波器 $b$ 平滑信号 $a$ ，然后从原始信号中减去平滑结果可以表示为使用滤波器 $d-b$ 进行单次卷积：

c=a-a \star b=a \star d-a \star b=a \star(d-b) .

10.2.3 卷积作为移位滤波器的总和

有一种完全等价的方式来解释方程 (10.2)。逐个观察 $a \star b$ 的样本会得到我们已经看到的加权平均解释。但是，如果我们省略 $[i]$ ，我们可以将总和视为将整个序列相加。为了使这个想法起作用，需要一些符号：如果 $b$ 是一个序列，那么向右移动 $j$ 个位置的同样的序列被称为 $b→j$ （见图 10.8）：

图 10.8：将一个序列 $b$ 向右移动得到 $b→j$ 。

b_{\rightarrow j}[i]=b[i-j]

然后，我们可以将方程 (10.2) 写成关于整个序列 $(a \star b)$ 的语句，而不是逐个元素：

(a \star b)=\sum_{j} a[j] b_{\rightarrow j}

这样看来，卷积是一组平移的 $b$ 副本的加权和，其中权值由 $a$ 的条目确定（见图 10.9）。因为可交换性，我们可以选择 $a$ 或 $b$ 作为滤波器；如果我们选择 $b$ ，则我们将对输入中的每个样本添加一个滤波器的副本。

图 10.9：离散卷积作为滤波器的平移副本的总和。

10.2.4 连续函数的卷积

虽然在计算机程序中实际使用的是离散序列，但这些采样序列应该表示连续函数，并且通常我们需要对连续函数进行数学推理以确定要做什么。因此，定义连续函数之间以及连续函数与离散函数之间的卷积是有用的。

两个连续函数的卷积是方程 (10.2) 的明显推广，其中积分代替了求和：

(f \star g)(x)=\int_{-\infty}^{+\infty} f(t) g(x-t) d t \tag{10.3}

解释这个定义的一种方式是， $f$ 和 $g$ 的卷积，在参数 $x$ 处求值，是在将 $g$ 向右移动，使得 $g(0)$ 与 $f(t)$ 对齐后，两个函数乘积下的曲线下面的面积。就像在离散情况下一样，卷积是一个移动平均，滤波器提供平均值的权重（见图 10.10）。

图 10.10：连续卷积。

像离散卷积一样，连续函数的卷积是可交换和可结合的，并且在加法上是可分配的。与离散情况类似，连续卷积可以看作是滤波器的副本之和，而不是加权平均的计算。只是在这种情况下，有无限多个滤波器 $g$ 的副本：

(f \star g)=\int_{-\infty}^{+\infty} f(t) g_{\rightarrow t} d t .

例 21（两个矩形函数的卷积）设 f 是一个矩形函数：

f(x)=\left\{\begin{array}{ll} 1 & -\frac{1}{2} \leq x<\frac{1}{2} \\ 0 & \text { Otherwise } \end{array}\right.

那么 $f \star f$ 是什么？根据定义 (Equation 10.3)，有：

(f \star f)(x)=\int_{-\infty}^{\infty} f(t) f(x-t) d t

图 10.11 展示了这个积分的两种情况。当两个矩形没有重叠时，即 $x ≤ –1$ 或 $x ≥ 1$ 时，结果为零。当 $–1 < x < 1$ 时，重叠取决于两个矩形之间的距离，即 $|x|$ ；结果为 $1–|x|$ 。因此：

(f \star f)(x)=\left\{\begin{array}{ll} 1-|x| & -1<x<1 \\ 0 & \text { otherwise } \end{array}\right.

图 10.11：两个矩形的卷积产生一个帐篷函数。

这个函数称为帐篷函数，是另一种常见的滤波器（见第 10.3.1 节）。

Dirac Delta 函数

在离散卷积中，我们看到离散的脉冲响应 $d$ 作为恒等元： $d \star a = a$ 。在连续情况下，也有一个称为 Dirac 脉冲或 Dirac delta 函数的恒等函数，表示为 $δ(x)$ 。

直观地说，Delta 函数是一个非常窄、非常高的尖峰，具有无穷小的宽度，但仍然具有面积为 1（见图 10.12）。Delta 函数的关键定义属性是将其乘以一个函数会选择出恰好在零点处的值：

\int_{-\infty}^{\infty} \delta(x) f(x) d x=f(0)

图 10.12：Dirac Delta 函数 $δ(x)$ 。

Delta 函数在 0 处没有明确定义的值（可以松散地将其值视为 $+∞$ ），但它确实对所有 $x ≠ 0$ 具有值 $δ(x) = 0$ 。

从这个选择单个值的属性中，可以得出 Delta 函数是连续卷积的单位元（见图 10.13），因为将 $δ$ 与任何函数 $f$ 进行卷积都会产生

图 10.13：将函数与δ(x) 进行卷积会返回相同函数的副本。

(\delta \star f)(x)=\int_{-\infty}^{\infty} \delta(t) f(x-t) d t=f(x)

因此， $δ \star f = f$ （而且由于可交换性， $f \star δ = f$ 也是一样的）。

10.2.5 离散-连续卷积

有两种将离散和连续的世界连接起来的方法。一种方法是采样：我们通过写下函数在所有整数参数处的值并忘记其余部分来将连续函数转换为离散函数。给定一个连续函数 $f(x)$ ，我们可以对其进行采样，将其转换为离散序列 $a[i]$ ：

a[i]=f(i)

另一种方式是从离散函数或序列到连续函数的重建，这是使用另一种形式的卷积，即离散-连续形式完成的。在这种情况下，我们使用一个连续滤波器 $f(x)$ 来过滤离散序列 $a[i]$ ：

(a \star f)(x)=\sum_{i} a[i] f(x-i) .

重建函数 $a * f$ 在 $x$ 处的值是 $a[i]$ 的加权和，其中 $i$ 的值接近 $x$ （见图 10.14）。权重来自于滤波器 $f$ ，在间隔为 1 个单位的一组点上评估。例如，如果 $x=5.3$ ， $f$ 的半径为 2，则在 $1.3$ 、 $0.3$ 、 $–0.7$ 和 $–1.7$ 处评估 f。请注意，在离散-连续卷积中，通常先写下序列，再写下滤波器，以便求和是在整数上进行的。

图 10.14：离散-连续卷积。

与离散卷积一样，如果我们知道滤波器的半径 $r$ ，可以对求和进行限制，从而消除所有差异大于等于 $r$ 的 $i$ 和 $x$ 的点：

(a \star f)(x)=\sum_{i=\lceil x-r\rceil}^{\lfloor x+r\rfloor} a[i] f(x-i) .

请注意，如果一个点恰好与 $x$ 的距离为 $r$ （即 $x–r$ 是整数），它将被排除在求和之外。这与离散情况不同，在离散情况下，我们包括 $i–r$ 处的点。

将其编写成代码形式：

与其他形式的卷积一样，离散-连续卷积可以看作是滤波器的平移副本之和（见图 10.15）：

图 10.15：重建（离散-连续卷积）作为滤波器平移副本的和。

(a \star f)=\sum_{i} a[i] f_{\rightarrow i}

离散-连续卷积与样条曲线密切相关。对于均匀样条曲线（例如均匀 B 样条），样条曲线的基函数与控制点序列的卷积是精确匹配的（见第 15.6.2 节）。

10.2.6 多维卷积

到目前为止，我们关于采样和重建所说的一切都是一维的：只有一个变量 x 或一个单一的序列索引 i。在图形学中，许多重要的采样和重建应用都应用于二维函数，特别是二维图像。幸运的是，从一维到二维、三维甚至更高维度的采样算法和理论的概念推广非常简单。

从离散卷积的定义开始，我们可以通过将求和变为双重求和来将其推广到二维：

(a \star b)[i, j]=\sum_{i^{\prime}} \sum_{j^{\prime}} a\left[i^{\prime}, j^{\prime}\right] b\left[i-i^{\prime}, j-j^{\prime}\right]

如果 $b$ 是一个有限支持半径 $r$ 的滤波器（即它具有 $(2r+1)2$ 个值），那么我们可以用边界表示这个求和（见图 10.16）：

(a \star b)[i, j]=\sum_{i^{\prime}=i-r}^{i+r} \sum_{j^{\prime}=j-r}^{j+r} a\left[i^{\prime}, j^{\prime}\right] b\left[i-i^{\prime}, j-j^{\prime}\right]

图 10.16：对于半径为 $1$ 的滤波器 $b$ ，在点 $(i,j)$ 处对离散卷积做出贡献的九个输入样本的权重。

并将其表示为代码：

这个定义可以与一维情况类似地解释：每个输出样本都是输入中一个区域的加权平均值，使用 2D 滤波器作为“蒙版”来确定在平均值中每个样本的权重。

继续推广，我们也可以将连续-连续（见图 10.17）和离散-连续（见图 10.18）卷积推广到二维：

\begin{array}{c} (f \star g)(x, y)=\iint f\left(x^{\prime}, y^{\prime}\right) g\left(x-x^{\prime}, y-y^{\prime}\right) d x^{\prime} d y^{\prime} \\ (a \star f)(x, y)=\sum_{i} \sum_{j} a[i, j] f(x-i, y-j) \end{array}

图 10.17. 连续卷积在 $(x,y)$ 处得到的输入信号无限小面积的权重。

图 10.18。对于一个半径为 2 的重建滤波器，对位于 $(x, y)$ 处的离散-连续卷积做出贡献的 16 个输入样本的权重值。

在每种情况下，特定点的结果是该点附近输入的加权平均值。对于连续-连续情况，它是一个以该点为中心的区域的加权积分；对于离散-连续情况，则是所有落在该点附近的样本的加权平均值。

一旦我们从 1D 推广到 2D，进一步推广到 3D 甚至更高维度就应该相当清楚了。

10.3 卷积滤波器

现在我们有了卷积的机制，让我们来研究一些在图形学中常用的特定滤波器。

以下每个滤波器都有一个自然半径，在样本间距为 1 个单位时采样或重建时默认使用该大小。在本节中，滤波器以这种自然大小定义：例如，框滤波器的自然半径为 $1/2$ ，立方体滤波器的自然半径为 $2$ 。我们还需要使每个滤波器的积分为 $1: \space ∫_{x=0}^∞f(x)dx=1$ ，以便进行采样和重建而不改变信号的平均值。

如第 10.4.3 节所述，某些应用需要不同大小的滤波器，可以通过缩放基本滤波器来实现。对于滤波器 $f(x)$ ，我们可以定义尺度 $s$ 的版本：

f_s(x)={f(x/s) \over s}。

将滤波器在水平方向上拉伸因子 $s$ 倍，然后在垂直方向上压缩因子 $1/s$ 倍，以使其面积不变。在尺度 $s$ 处使用具有自然半径 $r$ 的滤波器，则其支持半径为 $sr$ （见图 10.20）。

10.3.1 卷积滤波器库

框滤波器

框滤波器（见图 10.19）是一个分段常数函数，其积分等于 1。作为离散滤波器，它可以写成

a_{\text {box }, r}[i]=\left\{\begin{array}{ll} 1 /(2 r+1) & |i| \leq r \\ 0 & \text { Otherwise } \end{array}\right.

图 10.19 离散和连续的盒状滤波器。

请注意，为了满足对称性，我们包括两个端点。

作为一个连续的滤波器，我们将其写成：

f_{\text {box }, r}(x)=\left\{\begin{array}{ll} 1 /(2 r) & -r \leq x<r \\ 0 & \text { Otherwise. } \end{array}\right.

在这种情况下，我们排除一个端点，这使得半径为 0.5 的盒状滤波器可以用作重建滤波器。正因为盒状滤波器是不连续的，所以这些边界情况非常重要，因此对于这种特定的滤波器，我们需要注意它们。我们使用 fbox 表示半径为 r=1/2 的自然半径。

帐篷滤波器

帐篷滤波器（图 10.20），也称为线性滤波器，是一种连续的、分段线性的函数：

f_{\text {tent }}(x)=\left\{\begin{array}{ll} 1-|x| & |x|<1 \\ 0 & \text { otherwise } \end{array}\right.

图 10.20。帐篷滤波器和两个缩放版本。

它的自然半径为 1。对于至少是 C0 的滤波器（即其值没有像方盒一样的突然跳跃），我们不再需要分离离散滤波器和连续滤波器的定义：离散滤波器只是对整数进行采样的连续滤波器。

高斯滤波器

高斯函数（图 10.21）也称为正态分布，在理论和实践中都是一个重要的滤波器。当我们继续阅读本章时，我们将看到更多它的特殊属性。

图 10.21。高斯滤波器。

f_{g}, \sigma(x)=\frac{1}{\sigma \sqrt{2 \pi}} e^{-x^{2} / 2 \sigma^{2}}

参数 $σ$ 称为标准差。高斯滤波器非常平滑，因此适用于作为一个好的采样滤波器；我们将在第 10.5 节中更加准确地论述这一点。

高斯滤波器没有特定的自然半径；它是一种适用于一系列σ的采样滤波器。高斯滤波器也没有有限的支持半径，但是由于指数衰减，它的值迅速变小，因此可以忽略。因此，必要时，我们可以通过在某个半径 $r$ 之外将其设置为零来从函数截取尾部，从而得到一个 trimed Gaussian。这意味着滤波器的宽度和自然半径可以根据应用而变化，并且由 s 缩放的 trimed Gaussian 与标准差为 $sσ$ 和半径为 $sr$ 的未缩放的 trimed Gaussian 相同。在实践中处理这个问题的最好方法是，让 $σ$ 和 $r$ 作为滤波器的属性进行设置，并在指定滤波器时固定，然后在应用滤波器时像任何其他滤波器一样进行缩放。

好的起点是 $σ = 1$ 和 $r = 3$ 。

B-Spline 三次滤波器

许多滤波器被定义为分段多项式，具有四个部分（自然半径为 2）的三次滤波器常常被用作重构滤波器之一。其中一种滤波器称为 B 样条滤波器（图 10.22），因为它最初是样条曲线的混合函数（请参见第 15 章）：

图 10.22。B 样条滤波器。

f_{B}(x)=\frac{1}{6}\left\{\begin{array}{ll} -3(1-|x|)^{3}+3(1-|x|)^{2}+3(1-|x|)+1 & -1 \leq x \leq 1 \\ (2-|x|)^{3} & 1 \leq|x| \leq 2 \\ 0 & \text { otherwise } \end{array}\right.

在分段三次函数中，B 样条比较特殊，因为它具有连续的一阶和二阶导数，即 $\bold C^2$ 。更简洁的定义方法是 $f_{\bold B} = f_{box}\star f_{box}\star f_{box} \star f_{box}$ ，证明上面更长的形式等价是卷积运算中的一个好练习（请参见练习 3）。

Catmull-Rom 三次滤波器

Catmull-Rom 滤波器是另一种以样条曲线命名的分段三次滤波器（图 10.23）。它在 x = -2、-1、1 和 2 的位置上的值为零，这意味着当用作重构滤波器时，它将插值样本（见第 10.3.2 节）：

图 10.23。Catmull-Rom 滤波器。

f_{C}(x)=\frac{1}{2}\left\{\begin{array}{ll} -3(1-|x|)^{3}+4(1-|x|)^{2}+(1-|x|) & -1 \leq x \leq 1 \\ (2-|x|)^{3}-(2-|x|)^{2} & 1 \leq|x| \leq 2 \\ 0 & \text { otherwise } \end{array}\right.

Mitchell-Netravali 立方滤波器

对于图像重新采样这个至关重要的应用，Mitchell 和 Netravali（1988）研究了立方滤波器并推荐了一种介于前两种滤波器之间的最佳选择（见图 10.24）。它只是前两个滤波器的加权组合：

图 10.24 Mitchell-Netravali 立方滤波器。

\begin{aligned} f_{M}(x) & =\frac{1}{3} f_{B}(x)+\frac{2}{3} f_{C}(x) \\ & =\frac{1}{18}\left\{\begin{array}{ll} -21(1-|x|)^{3}+27(1-|x|)^{2}+9(1-|x|)+1 & -1 \leq x \leq 1, \\ 7(2-|x|)^{3}-6(2-|x|)^{2} & 1 \leq|x| \leq 2, \\ 0 & \text { otherwise. } \end{array}\right. \end{aligned}

10.3.2 滤波器的属性

滤波器有一些传统术语，用于描述滤波器并将它们彼此比较。

滤波器的脉冲响应只是另一个名称：它是滤波器对仅包含脉冲的信号的响应（回想一下，用脉冲进行卷积只会得到滤波器）。

如果连续滤波器用于从离散序列重建连续函数时，结果函数恰好在样本点处取样本值，则连续滤波器是插值滤波器-也就是说，它“连接了点”，而不是产生仅接近这些点的函数。插值滤波器正是那些对于所有非零整数 $i$ 都具有 $f(0)=1$ 和 $f(i)=0$ 的过滤器（见图 10.25）。

具有负值的滤波器会产生振铃或过冲：它会在被过滤的函数值急剧变化处产生额外的振荡。

例如，Catmull-Rom 滤波器在两侧有负瓣，如果你用它来过滤一个阶跃函数，它会稍微夸大阶跃，导致函数值低于 $0$ 和高于 $1$ （见图 10.26）。

图 10.26：带有负瓣的滤波器在过滤或重建锐度不连续时总会产生一些过冲。

如果连续滤波器用作重建滤波器时，它可以将恒定序列重建为恒定函数，则连续滤波器是无波动的（见图 10.27）。这相当于要求任何整数间隔网格上的滤波器总和等于 1：

图 10.27：半径为 1 的帐篷滤波器是无波动的重建滤波器；标准偏差为 1/2 的高斯滤波器不是。

\sum_{i} f(x+i)=1 \text { for all } x

除了高斯滤波器外，第 10.3.1 节中的所有滤波器都在其自然半径处没有波动，但它们中的任何一个在非整数尺度下使用时都不一定无波动。如果需要消除离散-连续卷积中的波动，可以轻松实现：将每个计算样本除以用于计算它的权重之和：

(\overline{a \star f})(x)=\frac{\sum_{i} a[i] f(x-i)}{\sum_{i} a[i]} \tag{10.4}

该表达式仍然可以解释为 $a$ 和滤波器 $\overline{\vphantom{M}f}$ 之间的卷积（请参见 Exercise 6）。

连续滤波器具有连续度，它是在任何地方定义的最高阶导数。像框滤波器一样，在值上突然跳跃的滤波器根本不连续。具有连续性但具有尖锐拐角（第一阶导数的不连续性）的滤波器，例如帐篷滤波器，具有零阶连续性，我们称其为 C0。具有连续导数（没有尖锐拐角）的滤波器，例如上一节中的分段三次滤波器，是 C1；如果它的二阶导数也是连续的，就像 B 样条滤波器那样，它是 C2。滤波器的连续度对于重建滤波器尤其重要，因为重建函数继承滤波器的连续性。

可分离滤波器

到目前为止，我们只讨论了用于 1D 卷积的滤波器，但对于图像和其他多维信号，我们也需要滤波器。一般来说，任何 2D 函数都可以是 2D 滤波器，并且偶尔定义它们也很有用。但在大多数情况下，我们可以使用我们已经看过的 1D 滤波器构建适当的 2D（或更高维）滤波器。

最常用的方法是使用可分离滤波器。可分离滤波器 $f_2(x, y)$ 在特定 $x$ 和 $y$ 处的值就是评估 $x$ 和 $y$ 时 1D 滤波器 $f_1$ 的乘积：

f_2(x,y)=f_1(x)f_1(y)

同样，对于离散滤波器，

b_2[i,j]=b_1[i]b_1[j]

通过 $f_2$ 的任何水平或垂直切片都是 $f_1$ 的缩放副本。 $f_2$ 的积分是 $f_1$ 积分的平方，因此特别地，如果 $f_1$ 被归一化，则 $f_2$ 也是如此。

例 22（可分离帐篷滤波器）如果我们选择帐篷函数作为 $f_1$ ，则得到的分段双线性函数（见图 10.28）为

图 10.28：可分离的 2D 帐篷滤波器。

f_{2, \text { tent }}(x, y)=\left\{\begin{array}{lll} (1-|x|)(1-|y|) & |x|<1 \quad \text { and } \quad|y|<1 \\ 0 & \text { otherwise. } \end{array}\right.

坐标轴沿着切线函数，但沿对角线的剖面是二次函数（例如，沿着第一象限中的 $x=y$ 这条直线，我们可以看到二次函数 $(1−x)^2$ ）。

例 23（2D 高斯滤波器）如果我们选择高斯函数作为 $f_1$ ，则得到的 2D 函数（见图 10.29）为

图 10.29：2D 高斯滤波器，既可分离又具有径向对称性。

\begin{aligned} f_{2, g}(x, y) & =\frac{1}{2 \pi}\left(e^{-x^{2} / 2} e^{-y^{2} / 2}\right) \\ & =\frac{1}{2 \pi}\left(e^{-\left(x^{2}+y^{2}\right) / 2}\right) \\ & =\frac{1}{2 \pi} e^{-r^{2} / 2} \end{aligned}

请注意，（比例因子除外）这与我们绕原点旋转 1D 高斯函数以产生圆对称函数得到的函数相同。同时具有圆对称和可分离属性的特性是高斯函数独有的。坐标轴沿着高斯函数，但是在任何偏移量的任何方向上，从中心开始的剖面也是高斯函数。

可分离滤波器相对于其他 2D 滤波器的主要优势在于实现效率。让我们将 a2 的定义代入离散卷积的定义：

\left(a \star b_{2}\right)[i, j]=\sum_{i^{\prime}} \sum_{j^{\prime}} a\left[i^{\prime}, j^{\prime}\right] b_{1}\left[i-i^{\prime}\right] b_{1}\left[j-j^{\prime}\right]

注意， $b_1[i-i']$ 不依赖于 $j'$ ，可以从内部求和中分解出来：

=\sum_{i^{\prime}} b_{1}\left[i-i^{\prime}\right] \sum_{j^{\prime}} a\left[i^{\prime}, j^{\prime}\right] b_{1}\left[j-j^{\prime}\right]

让我们将内部总和简写为 $S[i']$ ：

\begin{array}{c} S\left[i^{\prime}\right]=\sum_{j^{\prime}} a\left[i^{\prime}, j^{\prime}\right] b_{1}\left[j-j^{\prime}\right] \\ \left(a \star b_{2}\right)[i, j]=\sum_{i^{\prime}} b_{1}\left[i-i^{\prime}\right] S\left[i^{\prime}\right] \end{array}

使用这种形式的公式，我们可以首先计算并存储每个 $i′$ 值的 $S[i′]$ ，然后使用这些存储的值计算外部总和。乍一看，这似乎并不显着，因为我们仍然必须执行与 $(2r+1)^2$ 成比例的工作来计算所有内部总和。但是，如果我们需要计算许多点 $[i,j]$ 的值，则情况就非常不同。

假设我们需要在 $[2,2]$ 和 $[3,2]$ 处计算 $a \star b_2$ ，并且 $b_1$ 的半径为 2。查看式子 10.5，我们可以看到我们需要计算 $S[0]，...，S[4]$ 以计算 $[2,2]$ 处的结果，我们需要计算 $S[1]，...，S[5]$ 以计算 $[3,2]$ 处的结果。因此，在可分离的形式中，我们只需计算所有六个值的 $S$ 并共享 $S[1]，...，S[4]$ （见图 10.30)。

图 10.30：使用 25 个样本的分离 2D 数组计算两个输出点（a）与沿列滤波一次，然后使用单独的 1D 数组的五个样本（b）。

对于大型滤波器，这种节省具有重要意义。在一般情况下使用半径为 $r$ 的滤波器过滤图像需要每像素计算 $(2r+1)^2$ 次乘积，而使用相同大小的可分离滤波器对图像进行滤波只需要 $2(2r+1)$ 次乘积（代价是一些中间存储）。从 $O(r^2)$ 到 $O(r)$ 的渐进复杂度的这种变化使得可以使用更大的滤波器。

该算法是：

为简单起见，此函数通过从输出图像的四个边缘裁剪 r 个像素来避免所有边界问题。在实践中，有各种方法处理这些边界问题；请参见 10.4.3 节。

10.4 图像信号处理

到目前为止，我们已经在抽象层面上讨论了采样、滤波和重构，主要使用 1D 信号作为例子。但正如我们在本章开始时观察到的那样，信号处理在图形学中最重要和最常见的应用是对采样图像进行处理。让我们仔细看看所有这些如何应用于图像。

10.4.1 使用离散滤波器的图像滤波

卷积的最简单应用可能是使用离散卷积处理图像。图像处理程序中最常用的一些功能是简单的卷积滤波器。可以通过与许多常见的低通滤波器卷积来模糊图像，范围从盒式滤波器到高斯滤波器（图 10.31）。高斯滤波器创建了一个非常平滑的模糊效果，通常用于此目的。

图 10.31：通过卷积每个不同滤波器模糊图像。

模糊的反义词是锐化，一种方法是使用“反向掩蔽”程序：从原始图像中减去模糊图像的α分之一。为了避免改变总体亮度，我们进行了重新调整比例，得到：

\begin{aligned} I_{\text {sharp }} & =(1+\alpha) I-\alpha\left(I \star f_{g, \sigma}\right) \\ & =I \star\left((1+\alpha) d-\alpha f_{g, \sigma}\right) \\ & =I \star f_{\text {sharp }}(\sigma, \alpha), \end{aligned}

其中 $f_{g,σ}$ 是宽度为 $σ$ 的高斯滤波器。使用离散脉冲 $d$ 和卷积的分配律，我们能够将整个过程写成一个单一的滤波器，在这个滤波器中，锐化的程度取决于模糊的宽度和程度（图 10.32）。

图 10.32：使用卷积滤波器锐化图像。

另一个结合两个离散滤波器的例子是下拉阴影。通常会通过对对象轮廓的模糊、平移副本来创建柔和的下拉阴影（图 10.33）。我们可以将平移操作表示为与偏心脉冲的卷积：

图 10.33：柔和的下拉阴影。

d_{m, n}(i, j)=\left\{\begin{array}{ll} 1 & i=m \text { and } j=n \\ 0 & \text { otherwise } \end{array}\right.

平移，然后模糊，通过同时卷积两个滤波器来实现：

\begin{aligned} I_{\text {shadow }} & =\left(I \star d_{m, n}\right) \star f_{g, \sigma} \\ & =I \star\left(d_{m, n} \star f_{g, \sigma}\right) \\ & =I \star f_{\text {shadow }}(m, n, \sigma) . \end{aligned}

在这里，我们使用关联性将两个操作分组为具有三个参数的单个滤波器。

10.4.2 图像采样中的抗锯齿

在图像合成中，我们经常需要生成一个采样表示，该表示有一个连续的数学公式（或者至少是一个我们可以用于计算任何点的颜色的过程，而不仅仅是整数像素位置）。光线追踪是一个常见的例子；关于光线追踪和特定的抗锯齿方法，在第 4 章中会有更多讨论。以信号处理的语言来说，我们有一个连续的 2D 信号（图像），需要在规则的 2D 格子上对其进行采样。如果我们直接对图像进行采样而没有采取任何特殊措施，则结果将显示出各种走样伪影（图 10.34）。在图像的尖锐边缘处，我们可以看到阶梯状的伪影，称为“jaggies”（锯齿）。在存在重复模式的区域中，我们会看到宽带，称为 Moiré 图案（摩尔纹）。

图 10.34：图像中走样伪影的两个例子：周期纹理中的 Moiré 图案（a）和直线上的 “jaggies”（b）。

问题在于，图像包含太多小尺度特征；我们需要在采样之前通过滤波将其平滑。回顾连续卷积的定义方程（10.3），我们需要在像素位置周围的区域内对图像进行平均处理，而不仅仅是在单个点上取值。具体的方法在第 4 章中讨论。像盒式滤波器这样简单的滤波器可以改善尖锐边缘的外观，但仍会产生一些 Moiré 图案（图 10.35）。高斯滤波器非常平滑，对 Moiré 图案的抗性更强，代价是整体模糊程度稍微更大。这两个例子说明了选择抗锯齿滤波器时基础的清晰度和走样之间的权衡。

图 10.35：使用三种不同的采样滤波器对一个包含圆形密集程度逐渐增加的困难测试图像进行抗锯齿操作的比较。

10.4.3 重构和重采样

最常见的需要认真过滤的图像操作之一是重采样——更改采样率或更改图像大小。

假设我们拍摄了一个 3000×2000 像素大小的数字相机图像，并且我们想在一个只有 1280×1024 像素的显示屏上显示它。为了使其适合，同时保持 3:2 的长宽比，我们需要将其重采样为 1278×852 像素。我们该如何处理这个问题？

解决这个问题的一种方法是将这个过程看作是丢失像素：尺寸比在 2 和 3 之间，因此我们需要在保留的像素之间删除一个或两个像素。可以通过这种方式缩小图像，但结果质量很低——图 10.34 中的图像是使用像素删除制作的。然而，像素删除非常快速，并且在交互式操作期间制作调整大小后的预览图像是一个合理的选择。

重新调整图像大小的思路是将其看作为重采样操作：我们希望在新图像尺寸所定义的特定网格上获得一组图像采样，并通过对输入采样重建连续函数来获得它们（图 10.36）。以这种方式看待它，它只是一系列标准的图像处理操作：首先，我们从输入采样中重建一个连续函数，然后，我们就可以像采样任何其他连续图像一样采样该函数。为了避免走样伪影，每个阶段都需要使用适当的滤波器。

图 10.36：重新采样图像包括两个逻辑步骤，将它们组合成单个操作的代码。首先，我们使用重构滤波器从输入采样中定义一个平滑的连续函数。然后，在新网格上对该函数进行采样以获取输出采样。

图 10.37 展示了一个小例子：如果原始图像是 12×9 像素，新图像是 8×6 像素，则每个维度的输出像素数为输入像素数的 2/3，因此它们在整个图像中的间距是原始采样的 3/2 倍。

图 10.37：重采样 12×9 图像以制作 8×6 图像时输入和输出网格的采样位置。

为了为每个输出采样计算一个值，我们需要以某种方式计算样本之间图像的值。像素删除算法给出了一种实现的方法：只需取最接近输入图像中的样本的值，并将其用作输出值。这与使用 1 像素宽度（半径为 1/2）的盒式滤波器重构图像并进行点采样完全等价。

当然，如果选择像素删除或其他非常简单的滤波器的主要原因是性能，那么就不会将该方法实现为通用重构-重采样过程的特殊情况。事实上，由于不连续性，要在通用框架中使盒式滤波器工作很困难。但对于高质量的重采样来说，重构/采样框架提供了有价值的灵活性。

为了解决算法细节，最简单的方法是回到 1D 并讨论重采样序列。编写实现的最简单方法是使用我们在第 10.2.5 节中定义的重构函数。

参数 $x_0$ 以旧序列的样本为单位给出了新序列的第一个采样点的位置。也就是说，如果第一个输出采样点位于输入序列的第 3 个和第 4 个样本之间， $x_0$ 为 3.5。

该过程通过将输入序列与连续滤波器卷积来重建连续图像，然后进行点采样。不是说这两个操作按顺序进行 —— 连续函数只存在于原则上，在采样点处计算其值。但从数学上讲，该函数计算函数 $a \star f$ 的一组点样本。

然而，这种点采样似乎是错误的，因为我们刚刚说过应该使用适当的平滑滤波器对信号进行采样以避免走样。我们应该用重构函数与采样滤波器 $g$ 进行卷积并对 $g\star (f\star a)$ 进行点采样。但由于这与 $(g\star f)\star a$ 相同，我们可以将采样滤波器与重构滤波器合并在一起；我们只需要一次卷积操作（图 10.38）。这个组合的重构和采样滤波器称为重采样滤波器。

图 10.38：重采样涉及用于重构和采样的滤波器。由于连续应用两个卷积滤波器可以用单个滤波器替换，因此我们只需要一个重采样滤波器，它扮演了重构和采样的角色。

在重采样图像时，通常会指定一个源矩形，其单位是旧图像，指定我们要在新图像中保留的部分。例如，使用第 3 章中的像素采样位置约定，我们用于对整个图像进行重采样的矩形为 $(-0.5，n_x^{old}-0.5)×(-0.5，n_y^{old}-0.5)$ 。给定源矩形 $(x_l，x_h)×(y_l，y_h)$ ，新图像的采样间距为 $Δx = (x_h-x_l) / n_x^{new}$ 和 $Δy = (y_h-y_l) / n_y^{new}$ 。左下角的样本位于 $(x_l + Δx/2, y_l + Δy/2)$ 。

将 1D 伪代码修改为使用这种约定，并将对重构函数的调用扩展为暗示的双重循环，我们得到

这个例程包含了重采样图像的所有基础知识。最后一个问题需要解决的是在图像边缘时应该怎么做，因为这里的简单版本将访问超出输入序列的范围。我们可以采取以下几种方法：

在序列的末尾停止循环。这相当于在所有侧面用零填充图像。
将所有数组访问剪裁到序列末端——也就是说，当我们想要访问 $a[-1]$ 时，返回 $a[0]$ 。这相当于通过扩展最后一行或列来填充图像的边缘。
在接近图像边缘时修改滤波器，使其不超出序列的边界。

第一种选择会导致在对整个图像进行重采样时出现暗淡的边缘，这并不理想。第二种方法易于实现；第三种方法可能具有最佳性能。在图像边缘处修改滤波器的最简单方法是重新归一化：将滤波器除以落在图像中的滤波器部分的总和。这样，滤波器始终在实际图像采样点上加起来等于 1，因此它保留了图像强度。为了提高性能，希望单独处理滤波器半径以内的像素带（需要进行这种重新归一化）和中心（包含更多像素且不需要重新归一化）。

重采样的滤波器选择很重要。有两个独立的问题：滤波器形状和大小（半径）。因为该滤波器既作为重构滤波器又作为采样滤波器，所以两个角色的要求都会影响滤波器的选择。对于重构，我们希望一个足够平滑的滤波器来避免当我们放大图像时出现走样伪影，并且滤波器应该是无波动的。对于采样，滤波器应该足够大以避免欠采样，并且足够平滑以避免莫尔纹伪影。图 10.39 说明了这两种不同的需求。

图 10.39：使用不同大小的滤波器来上采样（放大）或下采样（缩小）图像的效果。

通常，我们会选择一个滤波器形状，并根据输入和输出的相对分辨率进行缩放。两个分辨率中较低的那一个决定了滤波器的大小：当输出比输入更粗略地采样（下采样或缩小图像）时，为得到适当的采样所需的平滑程度高于重构所需的平滑程度，因此我们根据输出采样间距确定滤波器的大小（在图 10.39 中为半径 3）。另一方面，当输出更细致地采样（上采样或扩大图像）时，用于重构的平滑程度主导（重建函数已经足够平滑，以便以比起始值更高的速率进行采样），因此滤波器的大小由输入采样间距确定（在图 10.39 中为半径 1）。

选择滤波器本身是速度和质量之间的权衡。常见的选择是盒式滤波器（当速度至关重要时）、帐篷滤波器（中等质量）或分段立方滤波器（优秀质量）。在分段立方情况下，可以通过在 fB 和 fC 之间插值来调整平滑程度；Mitchell-Netravali 滤波器是一个不错的选择。

与图像滤波类似，可分离的滤波器可以提供显着的加速。基本思路是首先重新采样所有行，产生一个宽度改变但高度不变的图像，然后重新采样该图像的列以产生最终结果（图 10.40）。修改先前给出的伪代码以利用此优化相对简单。

图 10.40：使用可分离方法重采样图像。

第 10.5 节采样理论

如果你只对实现感兴趣，那么你可以在这里停止阅读；前面章节中的算法和建议将让你实现能够执行采样和重构，并获得优秀结果的程序。然而，有一个更深入的数学采样理论，其历史可以追溯到通信中首次使用采样表示的时期。采样理论回答了许多仅基于比例推理很难回答的问题。

但是最重要的是，采样理论为采样和重构的工作原理提供了有价值的洞察力。它为学习它的学生提供了额外的思考工具，以理解如何通过最有效的代码实现最佳效果。

10.5.1 傅里叶变换

傅里叶变换与卷积一起，是支持采样理论的主要数学概念。你可以在许多分析数学书籍以及信号处理书籍中阅读有关傅里叶变换的内容。

傅里叶变换背后的基本思想是通过将所有频率的正弦波（正弦曲线）相加来表达任何函数。通过使用不同频率的适当权重，我们可以使这些正弦波加起来等于任何（合理的）我们想要的函数。

例如，图 10.41 中的方波可以用正弦波序列表示：

\sum_{n=1,3,5, \ldots}^{\infty} \frac{4}{\pi n} \sin 2 \pi n x

这个傅里叶级数从频率为 1.0 的正弦波（sin2πx）开始——与方波相同——其余项增加了越来越小的修正以减少波浪，并在极限情况下完全复制方波。请注意，求和中的所有项的频率都是方波频率的整数倍。这是因为其他频率会产生不具有与方波相同周期的结果。

一个惊人的事实是，一个信号不必是周期性的才能用这种方式表示为一组正弦波的和：非周期性信号只需要更多的正弦波。我们将不再对一系列离散的正弦波求和，而是在连续的正弦波族中进行积分。例如，一个矩形函数可以写成余弦波族的积分：

\int_{-\infty}^{\infty} \frac{\sin \pi u}{\pi u} \cos 2 \pi u x d u \tag{10.6}

在等式（10.6）中，该积分将无限多个余弦波相加，将频率为 u 的余弦乘以权重（sinπu）/πu。当我们包括越来越高的频率时，结果收敛于矩形函数（参见图 10.42）。当一个函数 f 以这种方式表示时，这个权重是频率 u 的函数，被称为 f 的傅里叶变换，表示为 f^。函数 f^告诉我们如何通过在一族正弦波上积分来构建 f：

图 10.42：使用余弦积分逐步逼近矩形函数，直到每个截止频率为止。

f(x)=\int_{-\infty}^{\infty} \hat{f}(u) e^{2 \pi i u x} d u \tag{10.7}

式（10.7）被称为反傅里叶变换（IFT），因为它从 $f$ 的傅里叶变换开始，最终得到 $f^2$

请注意，在等式（10.7）中，复指数 $e^{2πiux}$ 已替换了前一个等式中的余弦波。此外， $\hat f$ 是一个复值函数。复数的机制是必需的，以允许控制正弦波的相位和频率；这是用于表示任何不对称于零的函数所必需的。 $\hat f$ 的幅度称为傅里叶谱，对于我们的目的来说，这已经足够了——我们不需要担心相位或直接使用任何复数。

事实证明，从 $f$ 计算 $\hat f$ 看起来非常像从 $\hat f$ 计算 $f$ ：

\hat{f}(u)=\int_{-\infty}^{\infty} f(x) e^{-2 \pi i u x} d x \tag{10.8}

式（10.8）被称为正（向前）傅里叶变换（FT）。指数中的符号是正向和反向傅里叶变换之间唯一的差异，并且实际上只是一个技术细节。对于我们的目的，我们可以将 FT 和 IFT 视为相同的操作。

有时， $f-\hat f$ 符号表示不方便，然后我们将 $f$ 的傅里叶变换表示为 $\mathcal{F} \{f\}$ ，将 $\hat f$ 的反傅里叶变换表示为 $\mathcal{F^{-1}} \{\hat f\}$ 。

函数及其傅里叶变换之间存在许多有用的关系。本章稍后将使用的一些事实（大多数易验证）是：

函数及其傅里叶变换具有相同的平方积分：

\int(f(x))^{2} d x=\int(\hat{f}(u))^{2} d u

物理解释是两者具有相同的能量（图 10.43）。

特别地，将函数按比例缩放 a 会将其傅里叶变换也缩放 a 倍。即， $\mathcal{F} \{af\} = a\mathcal{F} \{f\}$ 。

将函数沿 x 轴伸展会使其傅里叶变换沿 u 轴压缩相同的比例（图 10.44）：

\mathcal{F}\{f(x / b)\}=b \hat{f}(b x)

（需要通过 $b$ 进行重新调整以保持能量不变。）

这意味着，如果我们对不同宽度和高度的一组函数感兴趣（例如所有居中于零的矩形函数），那么我们只需要知道一个规范函数（例如宽度和高度都为 1 的矩形函数）的傅里叶变换，就可以轻松知道该函数的所有缩放和扩展版本的傅里叶变换。例如，我们可以立即推广公式（10.6）以给出宽度为 b、高度为 a 的矩形的傅里叶变换：

ab{sin⁡πbu \over πbu}

$f$ 的平均值等于 $\hat f(0)$ 。这是有意义的，因为 $\hat f(0)$ 应该是信号的零频率分量（如果我们考虑电压，则是直流分量）。

如果 $f$ 是实数（对于我们来说通常如此），则 $\hat f$ 是一个偶函数 —— 即 $\hat f(u)=\hat f(-u)$ 。同样，如果 $f$ 是偶函数，则 $\hat f$ 将是实数（在我们的领域中通常不是这种情况，但请记住我们只关心 $\hat f$ 的幅度）。

10.5.2 卷积和傅里叶变换

傅里叶变换的最后一个值得特别提及的特性是它与卷积的关系（图 10.45）。简而言之，

\mathcal{F}\{f \star g\}=\hat{f} \hat{g}

两个函数卷积的傅里叶变换是它们的傅里叶变换的乘积。根据现在已经熟悉的对称性，

\hat{f} \star \hat{g} = \mathcal{F}\{fg\}

两个傅里叶变换的卷积是两个函数乘积的傅里叶变换。这些事实从定义中非常容易推导出来。

这种关系是傅里叶变换在研究采样和重构效果时有用的主要原因。我们已经看到了如何通过卷积来看待采样、滤波和重构；现在傅里叶变换为我们提供了一个新的域——频率域，在这个域中，这些操作只是简单的乘积。

图 10.45。一张可视化展示卷积和乘法之间关系的交换图。如果我们在空间中将 $f$ 和 $g$ 相乘，然后转换到频率域，最终结果与我们先将 $f$ 和 $g$ 转换到频率域，然后进行卷积得到的结果是相同的。同样地，如果我们在空间中对 $f$ 和 $g$ 进行卷积，然后将其转换为频率域，最终结果也与我们将 $f$ 和 $g$ 转换到频率域，然后将它们相乘得到的结果相同。

图 10.46。盒状、帐篷、B 样条和高斯滤波器的傅里叶变换。

10.5.3 傅里叶变换示例

现在我们已经了解了一些关于傅里叶变换的事实，让我们来看一些单个函数的示例。特别地，我们将查看第 10.3.1 节中的一些滤波器，它们的傅里叶变换如图 10.46 所示。我们已经看到了矩形函数：

\mathcal{F}\left\{f_{\text {box }}\right\}=\frac{\sin \pi u}{\pi u}=\operatorname{sinc} \pi u

函数 3 $sin x/x$ 很重要，有它自己的名称 —— $sinc x$ 。

倒角函数是矩形函数与自身卷积，因此它的傅里叶变换只是矩形函数傅里叶变换的平方：

\mathcal{F}\left\{f_{\text {tent }}\right\}=\frac{\sin ^{2} \pi u}{\pi^{2} u^{2}}=\operatorname{sinc}^{2} \pi u

我们可以继续这个过程以得到 B-spline 滤波器的傅里叶变换（参见练习 3）：

\mathcal{F}\left\{f_{\mathrm{B}}\right\}=\frac{\sin ^{4} \pi u}{\pi^{4} u^{4}}=\operatorname{sinc}^{4} \pi u

高斯分布具有非常好的傅里叶变换：

\mathcal{F}\left\{f_{\mathrm{G}}\right\}=e^{-(2 \pi u)^{2} / 2}

它又是一个高斯分布！标准偏差为 1.0 的高斯分布变成了标准偏差为 $1/2π$ 的高斯分布。

10.5.4 采样理论中的狄拉克脉冲

狄拉克脉冲在采样理论中非常有用的原因是，我们可以使用它们来描述连续函数和傅里叶变换的采样。我们通过将一个翻译到该位置并乘以该值的冲量表示一个具有位置和值的样本。位置为 $a$ 、值为 $b$ 的样本表示为 $bδ(x – a)$ 。这样，我们可以通过将 $f$ 乘以 $δ(x – a)$ 来表示在位置 $a$ 对函数 $f$ 进行采样的操作。结果是 $f(a)δ(x – a)$ 。

因此，在一系列等间距点上对函数进行采样被表示为将函数乘以一系列等间距冲量的总和，称为脉冲列（图 10.47）。周期为 T 的脉冲列（意味着脉冲之间相隔 T 距离）为

s_{T}(x)=\sum_{i=-\infty}^{\infty} \delta(x-T i) .

$s_1$ 的傅里叶变换与 $s_1$ 相同：一个包含所有整数频率的脉冲序列。你可以想象一下，当我们将脉冲列乘以正弦波并积分时会发生什么。我们最终会将正弦波在所有整数处的值相加。对于非整数频率，这个总和将完全抵消为零，对于整数频率，它将发散为正无穷大。

由于傅里叶变换的扩张属性，我们可以猜测周期为 $T$ 的脉冲列（类似于 $s_1$ 的扩展）的傅里叶变换是一个具有周期 $1/T$ 的脉冲列。在空间域中进行更细的采样会使频率域中的冲量距离变得更远。

10.5.5 采样和走样

现在我们已经建立了数学工具，需要从频率域的角度理解采样和重构过程。引入傅里叶变换的关键优势是，它使卷积滤波对信号的影响更加清晰，并提供了更精确的说明为什么在进行采样和重构时需要进行滤波。

我们从原始连续信号开始这个过程。一般来说，它的傅里叶变换可以包括任何频率的分量，尽管对于大多数类型的信号（特别是图像），随着频率增加，信号内容会逐渐减少。图像也往往具有一个较大的零频率分量——请记住，零频率或直流分量是整个图像的积分，而且由于图像都是正值，它往往是一个很大的数字。

让我们看看如果没有进行任何特殊的滤波就进行采样和重构会发生什么（图 10.48）。当我们对信号进行采样时，我们将该操作建模为与脉冲列相乘；采样信号为 $fs_T$ 。由于乘法-卷积属性，采样信号的傅里叶变换为 $\hat{f} \star \hat{s_{T}}=\hat{f} \star s_{1 / T}$ 。

图 10.48。没有过滤的采样和重建。采样产生了与基频谱重叠并混合的伪频谱。使用盒状滤波器进行重建从伪频谱中收集了更多信息。结果是一个带有严重混叠伪影的信号。

回想一下， $δ$ 是卷积的恒等元素。这意味着

\left(\hat{f} \star s_{1 / T}\right)(u)=\sum_{i=-\infty}^{\infty} \hat{f}(u-i / T)

换句话说，与冲量列卷积会产生一整个等间隔的 $f$ 频谱的副本序列。对这一看似奇怪的结果的一个很好的直观解释是，所有这些副本只是表明（正如我们在 10.1.1 节中看到的那样），一旦我们进行了采样，相差采样频率整数倍的频率是无法区分的——它们将产生完全相同的一组样本。原始频谱称为基频谱，复制品称为别名频谱。

问题开始出现在这些信号频谱的复制品重叠在一起时。如果信号包含任何超过采样频率一半的显著内容，这种情况就会发生。当这种情况发生时，频谱相加，不同频率的信息被混合在一起，无法逆转。这是走样的第一个发生点，如果在这里发生了走样，那么是由于欠采样——对信号使用了太低的采样频率。

假设我们使用最近邻技术来重构信号。这等价于用宽度为 1 的矩形函数进行卷积。（用于执行此操作的离散-连续卷积与代表采样值的一系列脉冲的连续卷积相同。）卷积-乘积属性意味着重构信号的频谱将是采样信号的频谱与矩形函数的频谱的乘积。生成的重构傅里叶变换包含基频谱（虽然在高频时有所衰减），以及所有别名频谱的衰减副本。由于矩形函数具有相当宽的傅里叶变换，这些衰减的别名频谱部分非常显著，它们是第二种走样形式，由于不足的重构滤波器而产生。这些别名组成成为图像中最近邻重构的特征方块模式。

预防采样走样

为了进行高质量的采样和重构，我们已经看到需要适当选择采样和重构滤波器。从频率域的角度来看，采样时低通滤波的目的是限制信号的频率范围，使别名频谱不会重叠基频谱。图 10.49 显示了采样率对采样信号傅里叶变换的影响。更高的采样率将别名频谱分开，最终，任何剩余的重叠都不会产生问题。

图 10.49。采样信号频谱的采样率效应。更高的采样率使频谱的重复部分分离，减少了重叠带来的问题。

关键标准是频谱宽度必须小于副本之间的距离，也就是信号中存在的最高频率必须小于采样频率的一半。这被称为奈奎斯特准则，允许的最高频率被称为奈奎斯特频率或奈奎斯特限制。奈奎斯特-香农采样定理指出，一个其频率不超过奈奎斯特限制（或者说带限制到奈奎斯特频率）的信号，原则上可以从样本中完全恢复。

对于特定信号的采样率足够高，我们不需要使用采样滤波器。但如果我们遇到包含广泛频率范围的信号（例如带有锐利边缘的图像），在采样之前必须使用采样滤波器对信号进行带限制。图 10.50 显示了三个低通（平滑）滤波器在频率域中的效果，图 10.51 显示了在采样时使用这些相同的滤波器的效果。即使没有滤波器，频谱重叠，将信号与低通滤波器卷积可以缩小足够的频谱以消除重叠，并产生过滤后信号的良好采样表示。当然，我们已经失去了高频，但这比它们与信号混合并变成伪影要好。

图 10.50。应用低通（平滑）滤波器会缩窄信号的频谱。

图 10.51。图 10.50 中的低通滤波器如何在采样过程中防止混叠。低通滤波缩窄了频谱，因此重复部分重叠更少，并且来自伪频谱的高频成分对基频谱的干扰减少了。

预防重构走样

从频率域的角度来看，重构滤波器的作用是除去别名频谱，同时保留基频谱。在图 10.48 中，我们可以看到最简单的重构滤波器——矩形函数确实会衰减别名频谱。最重要的是，它完全阻止了所有别名频谱的直流成分。这是所有合理的重构滤波器的特征：它们在所有采样频率的倍数处在频率空间中具有零值。这恰好相当于空间域中的无纹波特性。

因此，一个好的重构滤波器需要是一个良好的低通滤波器，并具有完全阻止所有采样频率倍数的额外要求。使用不同于矩形函数滤波器的重构滤波器的目的是更彻底地消除别名频谱，减少高频伪影进入重构信号中的泄漏，同时尽可能少地干扰基频谱。图 10.52 说明了在重构过程中使用不同滤波器的效果。正如我们所见，矩形函数滤波器非常“泄漏”，即使采样率足够高，也会产生大量伪影。Tent 滤波器，即线性插值，对高频进行更多的衰减，产生较轻微的伪影，而 B 样条滤波器非常平滑，极其有效地控制别名频谱。它也稍微平滑了基频谱——这就是我们之前看到的平滑和走样之间的权衡。

图 10.52。不同重构滤波器在频率域中的效果。一个良好的重构滤波器可以有效地衰减别名频谱，同时保留基频谱。

预防重采样走样

当重构和采样操作在重采样中结合时，相同的原则适用，但是一个滤波器要同时完成重构和采样的工作。图 10.53 说明了重采样滤波器必须除去别名频谱并使频谱狭窄到足以在新采样率下进行采样。

图 10.53。在频率域中看到的重采样。重采样滤波器既重构信号（除去别名频谱），又对其进行带限制以减小其宽度，以便在新的采样率下进行采样。

10.5.6 理想滤波器 vs 实用滤波器

按照频率域分析的逻辑推论，一个在频率域中完全是矩形函数的滤波器对于采样和重构都是理想的。这样的滤波器可以在两个阶段都防止走样，而不会降低频率到奈奎斯特频率以下。

回想一下，反向和正向傅里叶变换本质上是相同的，因此具有矩形函数作为其傅里叶变换的空间域滤波器是函数 $\bold {sin} πx/πx = \bold {sinc} \space πx$ 。

但是，Sinc 滤波器在实践中通常不使用，无论是用于采样还是重构，因为它是不切实际的，并且尽管根据频率域标准它是最优的，但对于许多应用程序来说并不能产生最佳结果。

对于采样，Sinc 滤波器的无限延伸和与中心距离的增加相对缓慢的速率是一个劣势。此外，对于某些采样类型，负瓣是有问题的。高斯滤波器对于需要从输入信号中去除高频模式的困难情况也是一个很好的采样滤波器，因为它的傅里叶变换呈指数下降，没有任何凸点，可以防止别名泄漏。对于较简单的情况，Tent 滤波器通常足够。

对于重构，Sinc 函数的大小再次会产生问题，但更重要的是，许多纹波会在重构信号中形成“振铃”伪影。

练习

证明离散卷积是可交换和可结合的，同时也做同样的事情来证明连续卷积。
离散-连续卷积不能是可交换的，因为它的参数有两种不同的类型。然而，证明它是可结合的。
证明 B 样条是四个矩形函数的卷积。
通过使用“反转”定义，试图证明卷积是可交换和可结合的，并说明这是必要的（参见第 214 页上的脚注）： $(a \star b)[i]=\sum_{j} a[j] b[i+j]$
证明 $\mathcal{F}\{f \star g\}=\hat{f} \hat{g}$ 和 $\hat{f} \star \hat{g} = \mathcal{F}\{fg\}$ 。
方程 10.4 可以被解释为 $a$ 与滤波器 $\bar{f}$ 的卷积。写出“去除纹波”的滤波器 $\bar{f}$ 的数学表达式。绘制从缩放到 $s = 1.25$ 的矩形、帐篷和 B 样条滤波器去除纹波后得到的滤波器的图像。

目录