图形、图像与傅里叶变换

2024-05-05

背景

在图形学和计算机视觉的学习中，总是会看到大名鼎鼎傅里叶变换，但学了以后仿佛又没再用过了，搞不明白也仿佛完全不影响后续的学习，因此学了几次我都完全没明白。在最近又双叒叕学到这个名词以后，我终于决心把它一次性折腾个明白，顺便写一篇博客给以后的自己复习。当然傅里叶变换背后有一整套数学逻辑，且涉及傅里叶变换的其实都属于数字图像处理这一范畴，而这其中的复杂内容可以单独成课的。因此我这里只大略的涉及了它在图形图像方面应用的一些理论和逻辑（本来想深入研究，但是实在看不懂 QAQ 数学不是这点篇幅可以深入的）。考虑到数字信号本身就是基于数学人工生成的信号，在数学上的本质就是函数表达式，且本文的重点还是倾向于图形学，因此后文中信号、函数等名词使用可能非常混乱 = _ =。

数字信号：时域与频域

时域（time domain）描述信号随时间如何变化。对于一维波而言，时域图的 x 轴单位为时间 t，y 轴单位为振幅 A。时域图描述了不同时间时波的状态，t = 0 时 y 的值表当前波的振幅，t = 10 的 y 值表 10 单位时间之前波的振幅。

频域（frequency domain）描述的是组成信号的正弦波的振幅随频率变化。基于波的叠加原理，任何一个数字信号都可以拆解成若干个不频率不同振幅的正弦波。一维信号的频域图的 x 轴表示这些波的频率，而 y 轴则表示这个频率对应波的振幅。

归根究底，时域和频域只是对信号的不同表现形式，因此一个信号理应有一个在时域上的表现形式和在一个频域上的表现形式，区别只是信号不同表现形式下方便做不同的处理。而傅里叶变换就是那个将信号在时域和频域之间相互转换的变换。

傅里叶

傅里叶系列理论（包括傅里叶展开、傅里叶变换等等）的基础是，函数可以用三角函数构成的无穷级数表示，即函数可以由有限或无限个不同频率、振幅的正弦函数和余弦函数以及一个常数相加得到。当然这个变换中间的细节、条件等等要展开讲是可以出书的，这里就不仔细说了。反正核心的要素就是，将函数展开成为若干不同振幅、角频率、初相的正弦函数的和。三角公式（就是初中学的那个 $sin(\alpha +_ \beta) = sin\alpha cos\beta + cos\alpha sin\beta$ ）可以将不同初相的正弦函数转化为相同振幅、角频率的正弦函数和余弦函数之和。因此常见的傅里叶级数通常表示为成对的正弦函数和余弦函数和常数之和。

傅里叶级数

级数就是序列之和，如 $s = u_1 + u_2 + … + u_n + …$。一般我们所说的级数都是无穷级数（当然也有有穷级数）。级数的收敛就是指这个级数有一个一般意义上的和，即极限值。傅里叶级数就是一种级数，它由多个正弦和余弦函数相加而成，而傅里叶展开就是把函数展开成傅里叶级数。

傅里叶变换

而傅里叶变换则是傅里叶的理论更为复杂的应用，其作用是将函数从时域转为频域。当然逆傅里叶变换也可以将函数从频域转为时域。本质上它其实是一个坐标系转换，将函数从时域坐标转换为频域坐标，即将函数傅里叶级数中的频率和振幅提取出来。具体的计算逻辑这里就不展开了，总体来讲涉及到了采样、欧拉公式、极限等数学知识，推荐参考[3]中[苗华栋]的答案，讲得十分清晰且易于理解（且十分数学）。

图像处理

使用傅里叶变换进行图像处理，其本质就是将图片首尾相接当成空间中的二维信号（图片在空间维度上连续且循环，就像数字信号在时间维度上连续且循环），使用空间域（space domain）对应信号的时域。图片的频域图是一张灰度图，中点到图中像素点的方向是平面波的方向，距离是平面波的频率。频谱图的灰度值代表函数的振幅，即像素相对于相邻像素的差异强弱。相邻像素差异越强说明信号变化越快，即频率越大，所以频谱图上的灰度值也越大（图像颜色越黑）。通常展示的傅里叶变换后的频域图（如下图）都是移位后的结果，将最低频的信息移到原点，这样可以将不同图像的频谱图对齐，方便后续处理。最终将获得中间低频，边缘高频的灰度图。下图展现了图片经过傅里叶变换后的结果。

在进行傅里叶变换后，我们就可以使用不同的滤波器对图片进行不同的处理。去除低频信号的滤波（高通滤波）可以用于边缘提取，而去除高频信号的滤波（低通滤波）可以将图片模糊。在图像处理中，我们所使用的滤波器也可以用图片表示，并且滤波器也可以使用傅里叶变换获取其频谱图。在具体的计算操作中，将滤波器外围补 0 放大至图片大小，分别获取二者的频谱图，偏移再相乘（矩阵每个元素相乘），就相当于使用滤波。因为当滤波器频率为零的地方，原图像的频率乘完就会一样变为零，只有滤波器包含的频谱的值才会继续存在。将通过滤波器后的频谱图进行逆傅里叶变换，就可以得到滤波后的图像。

卷积定理

卷积定理的定义是，函数卷积的傅里叶变换等于函数傅里叶变换的乘积，即都是对图片做了一次滤波处理。无论是卷积的定义还是这个定理本身，都有非常复杂的数学性，因此这里只考虑其在图形学方面的相关定义和使用。在图形学中，卷积的本质就是对原始图片的每一个像素点和它周围的像素点做加权平均，所谓卷积核就是像素点的权重。比如用一个一维的卷积核 $[1, 1, 1]$ 做卷积，结果中的每个像素值等于像素点左边、像素点右边和像素点本身的像素值的平均，即 $pi = (p{i-1} 1 + p_i 1 + p_{i+1} * 1) / 3$ 。在图片处理中比较常用的是二维卷积，具体使用可以参考下图。对于边缘的点，不同使用场景有不同的处理方案，常见的有直接不考虑边缘（图片缩减两行两列）、复制边缘数值、像平铺一样补另一侧的数值等。

将这条定理结合前文图像处理，我们可以得到，将图片和卷积核都经过傅里叶变换再相乘，相当于对图片做一次卷积。就直接的效果而言，如果一维卷积核 $[1, 1, 1]$，即一个像素新值等于其左右像素值之和，那若它和它左右像素相等则它的结果值不变，而如果它左右值相差较大，像素的结果就会等于左中右的平均值。计算后的图片边缘被左右平均后不再明显，相当于减小了图片的变化，对图片做了模糊，所以这个卷积核相当于去掉了高频信息，即是一个低通滤波。将这个滤波做傅里叶变换和图片做傅里叶变换，相乘再做逆傅里叶变换，就可以得到和卷积相同的效果。

一些应用

渲染效果

在实现一些渲染效果时，傅里叶变换可以快速实现原本使用卷积实现的效果，来优化渲染性能。比如做模糊效果，可以使用卷积做类似左右像素平均（或者更复杂的卷积核做更好的效果），也就可以用这个卷积核用傅里叶变换做一个滤波。同理当我们需要对边缘做一些操作（如实现边缘高亮之类的效果）时，我们也可以用傅里叶变换替代卷积的边缘提取计算。

图像识别

在做图像识别的时候，傅里叶变换可以对图像进行去噪或锐化。噪声一般也是图片中的突变，如白色衣服中出现一个毫无意义的黑色像素点。大部分时候，图像的高频信息既有边缘信息，也有噪音信息。因此当我们只需要图像的色块信息时，我们就可以通过去除高频信息来去除色块中的噪点。而图像增强、锐化则是将图像的边缘加强，即加强高频信号。总之，我们可以用傅里叶变换和不同的滤波器提取图像在各个频率上的信息，以方便对不同信号做不同的处理。

水波纹

水波纹是傅里叶变换的一种和图像处理无关的使用方式，就是获取海面波的频域图，再通过逆傅里叶变换获取它的时域图（其实就是波形图），通过波形图计算出法线等其他需要的信息，就可以得到水面的效果。具体计算方式这里就不展开了（当然是因为我还没机会去实现它）。当然这种计算方式非常消耗性能，只有对水面的效果要求比较高时才会使用。

添加水印

添加水印是我这次查资料才看到的神奇用法。简而言之就是将水印添加在频域。若水印分布合理的话，逆傅里叶变换后其实只会稍微影响一下对比度，基本不会改变肉眼效果。具体可以参考知乎回答[12]。

背景