1 卷积

图像卷积的工作原理与一维卷积相同。例如，图像可以被视为脉冲的总和，即缩放和移位的delta函数。同样，线性系统的特征在于它们如何响应脉冲。也就是说，通过它们的脉冲响应。系统的输出图像等于输入图像与系统脉冲响应的卷积。

二维 δ函数是由全零组成的图像，除了 row=0、column=0 处的单个像素（其值为 1）之外。现在，假设行索引和列索引可以同时具有正值和负值，使得 1 位于一大片零的中心。当 δ函数通过线性系统时，单个非零点将变成其他一些二维模式。由于点唯一可能发生的事情就是它扩散，因此脉冲响应在图像处理术语中通常称为点扩散函数 ( point spread function,PSF)。

与一维信号一样，可以通过两种方式查看图像卷积：从输入和从输出：

• 从输入侧来看，输入图像中的每个像素都将点扩散函数的缩放和移位版本贡献给输出图像。
• 从输出侧来看，输出图像中的每个像素都受到输入信号中的一组像素的影响。对于一维信号，该影响区域是左右翻转的脉冲响应。对于图像信号，它是从左到右、从上到下翻转的 PSF。

由于 DSP 中使用的大多数 PSF 围绕垂直轴和水平轴对称，因此这些翻转不会执行任何操作并且可以忽略。

图24-3显示了几种常见的PSF：

• 在 (a) 中，pillbox有一个圆形顶部和直边。例如，如果相机的镜头没有正确聚焦，图像中的每个点将被投影到图像传感器上的圆形点。换句话说，pillbox是离焦镜头的点扩散函数。
• (b) 中所示的高斯是受随机缺陷限制的成像系统的 PSF。例如，望远镜发出的图像因大气湍流而变得模糊，导致最终图像中的每个光点都变成高斯分布。图像传感器，例如 CCD 和视网膜，通常受到光和/或电子散射的限制。中心极限定理表明高斯模糊是由这些类型的随机过程产生的。
• pillbox和高斯在图像处理中的使用与移动平均滤波器用于一维信号的情况相同。与这些 PSF 卷积的图像将显得模糊且边缘不清晰，但随机噪声较低。由于它们在时域中的作用，它们被称为平滑滤波器；由于它们处理频域的方式，它们被称为低通滤波器。
• © 所示的方形 PSF 也可以用作平滑滤波器，但它不是圆对称的。这导致对角线方向的模糊与垂直和水平方向的模糊不同。
• 与平滑滤波器相反的是边缘增强或高通滤波器。如图(d)所示，通过取平滑滤波器的负值并在中心添加δ函数来形成边缘增强滤波器内核。视网膜中发生的图像处理就是这种类型的滤波器的一个例子。
• 图(e)显示了二维sinc函数。一维信号处理使用加窗 sinc 来分离频带。由于图像没有在频域中编码信息，因此 sinc 函数很少用作成像滤波器内核。 sinc 函数可能很难使用，因为它的尾部幅度 (1/x) 减小得非常缓慢，这意味着它必须被视为无限宽。相比之下，高斯的尾部减少得非常快 ($e^{-}x2$ )，最终可以被截断而不会产生不良影响。

所有这些滤波器内核在行和列中都使用负索引，允许 PSF 以 row=0 和 column=0 为中心。在一维 DSP 中，通常通过将滤波器内核向右移动直到所有非零值来消除负索引。样品具有正指数。这种偏移使输出信号移动等量，这通常是无关紧要的。相比之下，输入和输出图像之间的偏移通常是不可接受的。相应地，负索引是图像处理中滤波器核的常态。

图像卷积的一个问题是涉及大量的计算。例如，当 512x512 像素图像与 64x64 像素 PSF 进行卷积时，需要超过十亿次乘法和加法（即 64×64×512×512）。较长的执行时间会使这些技术变得不切实际。使用三种方法来加快速度。

• 第一个策略是使用非常小的 PSF，通常只有 3×3 像素。这是通过循环输出图像中的每个样本，使用优化代码乘以并累加输入图像中相应的九个像素来实现的。仅仅 3×3 PSF 就可以实现惊人的处理量，因为它大到足以影响图像的边缘。
• 当需要较大的 PSF 时使用第二种策略，但其形状并不重要。这需要一个可分离的滤波器内核，该属性允许图像卷积作为一系列一维运算来执行。这样可以将执行速度提高数百倍。
• 第三种策略是FFT卷积，当滤波器核很大并且具有特定形状时使用。即使高效 FFT 提供了速度改进，执行时间也将是可怕的。

2 3x3 边缘修改

图 24-4 显示了几个 3×3 操作：

• 图(a)是机场X射线行李扫描仪获取的图像。当该图像与 3×3 delta 函数(一个被 8 个零包围的 1)进行卷积时，图像保持不变。
• (b) 显示了与由 1、-1 和 7 个 0 组成的 3×3 核进行卷积的图像，这称为移位和减法运算(shift and subtract)，因为从原始图像（对应于 1）中减去图像的移位版本（对应于 -1）。这种处理会产生一些物体比背景更近或更远的视觉错觉，从而产生 3D 或浮雕效果。大脑将图像解读为光线来自上方，这是世界呈现自身的正常方式。如果物体的边缘顶部较亮，底部较暗，则该物体会被认为是从背景中伸出来的。

常见的图像处理技术如（d）所示：边缘增强。这有时称为锐化操作。在 (a) 中，对象具有良好的对比度（适当的暗度和亮度），但边缘非常模糊。在（c）中，物体完全没有对比度，但边缘非常锐利。该策略是将具有良好边缘的图像乘以常数 k，并将其添加到具有良好对比度的图像。这相当于将原始图像与 (d) 中所示的 3×3 PSF 进行卷积。如果 k 设置为 0，PSF变成delta函数，并且图像保持不变。当 k 变大时，图像显示出更好的边缘清晰度。对于 (d) 中的图像，使用 k = 2 的值：图像 © 的两部分与图像 (a) 的一部分。此操作模仿眼睛锐化边缘的能力，使物体更容易从背景中分离出来。

与任何这些 PSF 进行卷积都可能导致最终图像中出现负像素值。即使程序可以处理像素的负值，图像显示也不能。最常见的解决方法是为每个计算出的像素添加偏移量，就像这些图像中所做的那样。另一种方法是截断超出范围的值。

3 通过可分离性进行卷积

这是一种快速卷积的技术，只要 PSF 是可分离的。如果 PSF 可以分解为两个一维信号：垂直投影和水平投影，则称其是可分离的。图 24-5 显示了可分离图像的示例，即方形 PSF。具体来说，图像中每个像素的值等于水平投影中的对应点乘以垂直投影中的对应点。以数学形式表示：

其中 x[r,c] 是二维图像，vert[r] 和 horz[c] 是一维投影。这可以通过生成任意水平和垂直投影并找到与它们相对应的图像来理解。例如，图 24-6 用双面指数曲线说明了这一点。然后从等式 24-1 中找到与这些轮廓相对应的图像。显示时，图像显示为菱形，随着距原点距离的增加，该菱形呈指数衰减至零。

在大多数图像处理任务中，理想的 PSF 是圆对称的，例如 pillbox。这就提出了一个问题：是否存在一个圆对称且可分离的PSF？答案是，是的。

但只有一种，即高斯分布。如图 24-7 所示，二维高斯图像的投影也是高斯的。图像和投影高斯具有相同的标准差。

要将图像与可分离滤波器内核进行卷积，请将图像中的每一行与水平投影进行卷积，从而得到中间图像。接下来，将该中间图像的每一列与 PSF 的垂直投影进行卷积。得到的图像与原始图像和滤波器内核的直接卷积相同。如果愿意，可以先对列进行卷积，然后再对行进行卷积；结果是一样的。

N×N 图像与 M×M 滤波器内核的卷积需要与 $N^2{M}^2$ 成正比的时间。换句话说，输出图像中的每个像素都取决于滤波器内核中的所有像素。相比之下，可分离性卷积只需要与 $N^{2}M$ 成正比的时间。对于数百像素宽的滤波器内核，该技术会将执行时间减少数百倍。

4 PSF 的示例：照明平坦化

需要大 PSF 的常见应用是增强不均匀照明的图像。可分离性卷积是执行此处理的理想算法。除了少数例外，眼睛看到的图像都是由反射光形成的。这意味着观看的图像等于物体的反射率乘以环境照明。图 24-8 显示了其工作原理。图 (a) 表示所观察场景的反射率，在本例中为一系列明暗带。图 (b) 说明了照明信号示例，即落在 (a) 上的光图案。与现实世界一样，照明在成像区域上缓慢变化。图 © 是人眼看到的图像，等于反射图像 (a) 乘以照明图像 (b)。 © 中照明不良的区域很难看到，原因有两个：它们太暗且对比度太低（峰和谷之间的差异）。

图像处理的目标是平坦化所获取图像中的照明分量。根据图24-8，给定©，求(a)。这是一个非线性滤波问题，因为分量图像是通过乘法而不是加法组合的。

首先，将图像 © 与大 PSF（整个图像大小的五分之一）进行卷积。目标是消除（c）中的尖锐特征，从而产生原始照明信号的近似值（b），这是使用可分离性卷积的地方。 图 (d) 是使用高斯滤波器内核的结果。

由于平滑滤波器提供了照明图像的估计，因此将使用边缘增强滤波器来查找反射率图像。也就是说，图像 © 将与由 delta 函数减去高斯函数组成的滤波器内核进行卷积。为了减少执行时间，这是通过从 © 中的原始图像中减去 (d) 中的平滑图像来完成的。图(e)显示了结果。虽然黑暗区域已被适当提亮，但这些区域的对比度仍然很糟糕。

线性滤波在此应用中表现不佳，因为反射率和照明信号最初是通过乘法而不是加法组合的。线性滤波无法正确分离由非线性运算组合的信号。要分离这些信号，必须不对它们进行相乘。换句话说，原始图像应除以平滑图像，如(f)所示。这可以校正亮度并将对比度恢复到适当的水平。

同态处理是一种处理通过非线性运算组合的信号的方法。该策略是通过适当的数学运算将非线性问题转变为线性问题。当两个信号通过组合乘法，同态处理首先对获取的信号取对数。有了恒等式：log(a×b) = log(a) + log(b)，分离相乘信号的问题转化为分离相加信号的问题。

划分或沿着同态路径哪个更好？ 它们几乎相同，因为取对数并减去等于除法。唯一的区别是用于照明图像的近似值。一种方法使用所获取图像的平滑版本，而另一种方法使用所获取图像的对数的平滑版本。

虽然这可以保持图像大小相同，但并不能解决整个问题；这些仍然是卷积的边界条件。例如，想象一下尝试计算 (d) 右上角的像素。这是通过将高斯 PSF 集中在 © 的右上角来完成的。然后将 © 中的每个像素乘以覆盖 PSF 中的相应像素，并将乘积相加。问题是，四分之三的 PSF 位于定义的图像之外。最简单的方法是将未定义的像素分配为零值。这就是 (d) 的创建方式，考虑了图像周边的暗带。也就是说，亮度平滑地降低到定义图像外部的像素值零。

幸运的是，边界周围的黑暗区域可以得到纠正。这是通过将 (d) 中的每个像素除以校正因子来完成的。校正因子是计算像素时浸入输入图像中的 PSF 的分数。也就是说，为了校正 (d) 中的单个像素，假设 PSF 以 © 中的相应像素为中心。例如，© 中的右上角像素仅由 25% 的 PSF 与输入图像重叠而产生。因此，通过将 (d) 中的该像素除以 0.25 来校正该像素。这意味着（d）中心的像素不会改变，但周边的暗像素将会变亮。为了找到校正因子，想象一下将滤波s内核与所有像素值都等于 1 的图像进行卷积。所得图像中的像素是消除边缘效应所需的校正因子。

5 傅里叶图像分析

傅立叶分析在图像处理中的使用方式与一维信号的使用方式非常相似。然而，图像的信息并未在频域中编码，这使得这些技术的用处大大减弱。例如，当对音频信号进行傅立叶变换时，令人困惑的时域波形被转换为易于理解的频谱。相比之下，对图像进行傅里叶变换将空间域中的直接信息转换为频域中的加扰形式。简而言之，不要指望傅立叶变换可以帮助理解图像中编码的信息。

同样，滤波器设计也不要考虑频域。图像的基本特征是边缘，即将一个对象或区域与另一个对象或区域分开的线。由于边缘由各种频率分量组成，因此尝试通过操纵频谱来修改图像通常是没有成效的。图像滤波器通常在空间域中设计，其中信息以最简单的形式进行编码。考虑平滑和边缘增强操作（空间域），而不是高通和低通滤波器（频域）。

图像的频谱可以通过多种方法计算，但这里介绍的 FFT 方法是唯一实用的方法。原始图像必须由 N 行 N 列组成，其中 N 是 2 的幂，即 256、512、1024 等。如果原始图像的大小不是 2 的幂，则值为添加零以使其大小正确。保存图像的二维数组称为真实数组。此外，还需要另一个相同大小的数组，称为虚数数组。

计算图像傅里叶变换的方法非常简单：对每行进行一维 FFT，然后对每列进行一维 FFT。具体来说：

• 首先对实际数组第 0 行中的 N 个像素值进行 FFT。 FFT 输出的实部被放回到实数数组的第 0 行，而 FFT 输出的虚部被放置到虚数数组的第 0 行。在第 1 行到第 N-1 行上重复此过程后，实数数组和虚数数组都包含中间图像。
• 接下来，对中间数据的每一列重复该过程。从实数数组的第 0 列获取 N 个像素值，从虚数数组的第 0 列获取 N 个像素值，并计算 FFT。 FFT 输出的实部被放回实数数组的第 0 列，而 FFT 输出的虚部被放回虚数数组的第 0 列。在第 1 列到第 N-1 列上重复此操作后，两个阵列都已被图像的频谱覆盖。

由于图像中垂直方向和水平方向是等效的，因此该算法也可以先变换列，再变换行。无论使用的顺序如何，结果都是相同的。从 FFT 跟踪数据的方式来看，低频分量的幅度最终位于二维频谱的角落，而高频则位于中心。图像的逆傅里叶变换是通过对每行进行逆 FFT，然后对每列进行逆 FFT 来计算的（反之亦然）。

图 24-9 显示了图像的傅立叶变换示例：

• 图(a)是原始图像
• 图 (b) 显示了该图像频谱的实部和虚部。由于频域可以包含负像素值，因此这些图像的灰度值被偏移，使得负值是暗的，零是灰色的，正值是亮的。图像中的低频分量的幅度通常比高频分量大得多。这说明了 (b) 的四个角上非常亮和很暗的像素。除此之外，典型图像的光谱没有可辨别的顺序，显得随机。
• 如 © 所示，图像光谱的极坐标形式只是稍微容易理解一些。幅度的低频具有较大的正值（白色角），而高频具有较小的正值（黑色中心）。相位在低频和高频下看起来相同，似乎在 -π 和 π 弧度之间随机运行。
• 图 (d) 显示了显示图像光谱的另一种方法。由于空间域包含离散信号，因此频域是周期性的。换句话说，频域阵列向左、右、上、下无限次复制。例如，想象一面瓷砖墙，每个瓷砖的大小为 © 中所示的 N×N 大小。图（d）也是这面瓷砖墙的 N×N 截面，但它横跨四块瓷砖；图像的中心是四个瓷砖接触的地方。换句话说，© 是与 (d) 相同的图像，只不过它在周期频谱中水平（向左或向右）移动了 N/2 个像素，垂直（向上或向下）移动了 N/2 个像素。这将 © 四个角的明亮像素聚集到 (d) 的中心。

图 24-10 说明了二维频域的组织方式（低频位于角落）。 N/2 行和 N/2 列将频谱分为四个象限。对于实部和幅度，右上象限是左下象限的镜像，而左上象限是右下象限的镜像。 这种对称性也适用于虚部和相位，只是镜像像素的值符号相反。换句话说，频谱中的每个点都有一个匹配点，对称地放置在图像中心的另一侧（第 N/2 行和第 N/2 列）。其一是正频，其二是匹配负频率，在方程形式中，这种对称性表示为：

这些方程考虑到频谱是周期性的，每 N 个样本重复一次，索引从 0 到 N-1。换句话说，X[r,N] 应解释为 X[r,0]，X[N,c] 应解释为 X[0,c]，X[N,N] 应解释为 X[0,0]。这种对称性使得光谱中的四个点彼此匹配。这些点位于：[0,0]、[0,N/2]、[N/2,0] 和 [N/2,N/2]。

频域中的每一对点对应于空间域中的正弦曲线。如图(a)所示，a的值对应于空间域中的零频率正弦波，即图像的DC分量。该图中只显示了一个点，因为这是它自己匹配的点之一。如图（b）、（c）和（d）所示，其他点对对应于二维正弦曲线，看起来像海洋上的波浪。一维正弦曲线具有频率、相位和幅度。二维正弦曲线也有方向。

每个正弦波的频率和方向由频域中一对点的位置决定。如图所示，从每个点到该点所在象限外角的零频率位置画一条线，即[0,0]、[0,N/2]、[N/2,0]和[N/2,N/2]（如图中圆圈所示）。这条线的方向决定了空间正弦波的方向，而其长度则与波的频率成正比。这导致低频位于角落附近，而高频位于中心附近。

当频谱以中心零频率显示时（图24-9d），从每对点开始的线绘制到图像中心的DC值，即[N/2,N/2] 。这个组织更容易理解和使用，因为所有的线都画到同一个点。将零置于中心的另一个优点是它与连续图像的频谱相匹配。当空间域是连续的时，频域是非周期的。这将零频率置于中心，频率在所有方向上变得更高直至无穷大。

6 快速傅立叶变换卷积

尽管傅里叶变换很慢，但它仍然是用大滤波器内核对图像进行卷积的最快方法。例如，与传统卷积相比，使用 FFT 将 512×512 图像与 50×50 PSF 进行卷积的速度大约快 20 倍。

将通过一个示例演示 FFT 卷积，这是一种在图像中定位预定模式的算法。假设构建一个用于检查一美元钞票的系统，例如可用于印刷质量控制、伪造品检测或自动售货机中的付款验证。如图24-11所示，获取了一张100×100像素的钞票图像，以乔治·华盛顿的肖像为中心。目标是在该图像中搜索已知模式，在本例中为面部的 29×29 像素图像。问题是这样的：给定获取的图像和已知的图案，定位图案出现在图像中的位置（或是否出现）的最有效方法是什么？这个问题的解决方案是相关性（匹配滤波器），并且可以通过使用卷积来实现。

在执行实际的卷积之前，需要进行两项修改才能将目标图像转换为 PSF。这些如图 24-12 所示。图 (a) 显示了目标信号，即试图检测的模式。在(b)中，图像旋转了180°，与从左到右翻转然后从上到下翻转相同。

第二个修改是提高算法有效性的技巧。与其尝试在原始图像中检测人脸，不如在原始图像的边缘中检测人脸的边缘。这是因为边缘比原始特征更尖锐，使得相关性具有更尖锐的峰值。此步骤不是必需的，但它可以使结果明显更好。最简单的形式是对原始图像和目标信号应用 3×3 边缘检测滤波器在执行关联之前。从卷积的关联性质来看，这与对目标信号应用边缘检测滤波器两次，而保留原始图像相同。在实际应用中，通常只应用一次边缘检测 3×3 内核就足够了。这就是图24-12中的(b)变为©的方式。这使得 © PSF 用于卷积

图 24-13 说明了 FFT 卷积的细节。在此示例中，将图像 (a) 与图像 (b) 进行卷积以生成图像 ©。这些图像已被选择和预处理以实现相关性这一事实是无关紧要的；这是卷积的流程图。第一步是用足够的零填充两个卷积信号，使它们的大小为 2 的幂，并且足够大以容纳最终图像。也就是说，当100×100和29×29像素的图像进行卷积时，得到的图像将是128×128像素。因此，必须向 (a) 和 (b) 添加足够的零，使它们的大小均为 128×128 像素。如果不这样做，循环发生卷积，最终图像会失真。如果您在理解这些概念时遇到困难，请返回并回顾第 18 章，其中更详细地讨论了一维情况。

FFT算法用于将(a)和(b)变换到频域。这会产生四个 128×128 阵列，两个图像的实部和虚部进行卷积。将 (a) 的实部和虚部与 (b) 的实部和虚部相乘，生成 © 的实部和虚部。通过逆 FFT 生成最终的卷积图像来完成算法。

相关图像中每个像素的值是目标图像与搜索图像在该点的匹配程度的度量。在此特定示例中，© 中的相关图像由噪声加上单个亮峰组成，表明与目标信号良好匹配。只需找到该图像中最亮的像素即可指定检测到的面部坐标。如果我们没有对目标信号使用边缘检测修改，峰值仍然会存在，但不太明显。

虽然相关性是图像处理中的强大工具，但它有一个显着的限制：目标图像必须与搜索图像中相应区域的大小和旋转方向完全相同。每个像素幅度的噪声和其他变化相对不重要，但精确的空间匹配至关重要。例如，这使得该方法在军事侦察照片中寻找敌方坦克、医学图像中的肿瘤以及机场行李扫描中的手枪方面几乎毫无用处。一种方法是将图像与目标图像的各种形状和旋转多次关联。

7 仔细观察图像卷积

使用最后一个示例来更详细地探讨二维卷积。正如一维信号一样，图像卷积可以从输入侧或输出侧观察。输入视点是卷积工作原理的最佳描述，而输出视点则是大多数数学和算法的编写方式。

图24-14显示了图像卷积的输入侧描述。输入图像中的每个像素都会导致将缩放和移位的 PSF 添加到输出图像。然后将输出图像计算为所有贡献 PSF 的总和。该图显示了输入图像中位置 [r,c] 处的点对输出图像的贡献。 PSF 发生偏移，使得 PSF 中的像素 [0,0] 与输出图像中的像素 [r,c] 对齐。如果仅使用正索引定义 PSF（如本例所示），则移位后的 PSF 将完全位于 [r,c] 的右下角。不对图中倒置的脸感到困惑；这个颠倒的面就是在本例中使用的 PSF（图 24-13a）。在输入侧视图中，PSF 没有旋转，只是移动了。

从输出来看图像卷积如图24-15所示。输出图像中的每个像素（例如 [r,c] 处的样本所示）接收输入图像中许多像素的贡献。 PSF 围绕像素 [0,0] 旋转 180°，然后进行移位，以使 PSF 中的像素 [0,0] 与输入图像中的像素 [r,c] 对齐。如果 PSF 仅使用正索引，则它将位于输入图像中像素 [r,c] 的左上角。通过将旋转的 PSF 中的像素与输入图像中的相应像素相乘并对乘积求和，可以找到输出图像中 [r,c] 处的像素值。该过程由方程式24-3给出以及表24-1的程序中。

请注意，由卷积产生的 PSF 旋转撤销了 PSF 设计中所做的旋转。这使得人脸在图 24-15 中显得直立，使其与输入图像中检测到的图案处于相同的方向。也就是说，已经成功地利用卷积来实现相关性。将图 24-13c 与图 24-15 进行比较，看看相关图像中的亮点如何表明目标已被检测到。

FFT 卷积提供与表 24-1 的传统卷积程序相同的输出图像。 FFT 卷积所减少的执行时间真的值得增加额外的程序复杂性吗？ 图 24-16 显示了使用浮点的传统卷积（标记为 FP）、使用整数的传统卷积（标记为 INT）和使用浮点的 FFT 卷积（标记为 FFT）之间的执行时间比较。提供了两种不同图像尺寸的数据：512×512 和 128×128。

首先，FFT 卷积所需的执行时间不取决于内核的大小。在 100 MHz Pentium 个人计算机上，可以对 128×128 图像进行卷积使用 FFT 卷积大约需要 15 秒，而 512×512 图像需要 4 分钟以上。将计算次数加起来可以看出，对于 N×N 图像，FFT 卷积的执行时间与 $N^{2}Log2(N)$ 成正比。也就是说，512×512 图像所需的长度大约是 128×128 图像的 20 倍。

对于与 M×M 核进行卷积的 N×N 图像，传统卷积的执行时间与 $N^2{M}^2$ 成正比。通过检查表 24-1 中的程序可以理解这一点。换句话说，传统卷积的执行时间很大程度上取决于所使用的内核的大小。如图所示，如果内核大于约 10×10 像素，FFT 卷积比使用浮点的传统卷积更快。在大多数情况下，整数可以用于传统的卷积，将盈亏平衡点增加到大约 30×30 像素。这些盈亏平衡点稍微取决于正在卷积的图像的大小，如图所示。要记住的概念是 FFT 卷积仅对大型滤波器内核有用。