计算机图形学基础
本文章是Fundamental of Computer Graphics一书的读书笔记。纯文盲，如果有任何问题可以去翻阅书籍原文，如果能够私信告诉我更是感激不尽。我们已经学会了如何在计算机中绘制出一幅质量勉强还行的图像了，下一步我们便是需要精益求精，追求更好的画面质量。上一章介绍的抗锯齿算法就是一个典型的提升画面质量的算法，我仅仅只是告诉你需要将像素进行“平均”，但没有告诉你为什么。这一章我们就要来研究提升画面质量的算法背后的原理，并且可以看到这个原理在图形学之外的领域也有广泛应用。
采样(sampling)和重构(reconstruction)
让我们从照相机开始，照相机是如何拍出一张照片的？照相机中有一个由许多对光敏感的小传感器排列成的网格，在拍照时外界的光从镜头打到传感器上，然后照相机记录网格上所有小传感器的状态，再经过一系列的处理之后就变成了以二进制形式存储的照片
这便是一个采样(sampling)的例子，采样就是一种近似，我们将现实当中连续的图像映射到不连续的像素网格上，也就是对连续的图像采样。与之相似的摄像也是取样的一个例子，我们将沿连续的时间变化的画面映射到每秒几十张的照片上，也就是沿着时间采样。另外一个更经典的取样的例子是音频，数字音频同时也是信号处理的一个重要的应用领域。
如果我们的讨论到此为止，那么这一章就没有什么存在的必要了，但我们显然在记录了这些取样得到的信息之后，还需要通过某种方法将它们再现出来，这被称为重构(reconstruction). 比如我们如何对一张照片进行非等比缩放？如果我们凭借直觉去编写图片缩放的算法，会发现它的产出特别糟糕，尤其是图片的清晰度遭到了不必要的损害，这种现象就被称为走样(artifact). 要想消灭这些碍眼的家伙，就需要采样理论(sampling theory)来帮助我们。
数字音频：一维采样
数字音频的记录是使用麦克风完成的。在录制时麦克风将声音——即空气中的声波，转化成随时间变化的电压；在播放时播放设备就根据随时间变化的电压播放音频。
电压并不能被直接存储，因此我们还需要想办法以某种形式将电压记录的信息存储起来。从上图我们可以看到声音以声波的形式被麦克风转换成随时间变化的电压，接着模拟数字转换器(Analog-to-Digital converter, A/D converter or ADC)以一定频率将随时间变化的电压记录成离散的一串数字（也就是隔一段时间读取一次电压值并转化成相应数值），因此音频就可以以数字形式被记录在存储介质上。在播放时数字模拟转换器(Digital-to-Analog conveter, D/A converter or DAC)将存储着的一系列数字再转换成电压作为输入提供给播放设备，最后播放设备才能播放出声音。
电压和音频文件之间的转换对播放器最终播放的音频的质量有非常大的影响，如果我们做对了的话，最后我们听到的音频和记录的音频应该是相差无几的。
回想一下上一节介绍的概念，可以发现从电压到离散的数字序列也是一个采样的过程，这个采样的质量高低和其采样的频率正相关。不同声音是有不同的频率的，采集鼓声这种较低频率的声音就可以用较低的采样频率，而对镲片声这种频率较高的声音就需要更高的采样频率。采样频率过高会降低性能（做了多余的采样），而过低会带来更严重的后果：声音失真。
例如上面这个例子，蓝色的正弦曲线就是声波，而灰色的竖直线就代表一次采样，可以看到当采样频率过低时，我们重建出来的正弦曲线和原来的曲线相去甚远，其频率大大降低，这被称为低采样走样(undersampling artifacts)，所有重建出来的信号的频率都是偏低的。实际上给定任何一个采样频率，我们的采样能力都是有限的，任何超出采样能力的高频信号都会在采样结果中产生走样。因此我们对付它的策略也很简单——不处理过高频率的信号，我们可以在上一幅图中看到一个名为lowpass filter的元件，它正是用于过滤高频信号的。
接下来我们讲讲重建技术。数字模拟转换器将输入的数字序列转化成对应的电压，但是这种转换并不是完美的重现原来被记录下来的电压。在我们对输入电压进行采样的那一刻，原来的信息就已经丢失了，我们只能近似地重现原信息。正是因为信息缺失了，如果我们只是简单输出这些离散的电压值的话，输出的电压只会在输入的数字改变时才会改变，如此会呈现阶梯状的电压图像：
这种电压输入得到的声音质量是非常差的，这种一段时间频率不变地声音在人听来与噪音无异，这被称为重建走样(reconstruction artifact)。我们同样需要信号过滤器来使输出的电压图像更加光滑，更加接近原电压图像。
我们通过研究声音的采样和重建得到了减少走样的一个通用策略：在采样前过滤掉无法正确采集的高频信号，同时在重建过程中过滤掉过于尖锐的信号使得输出的信号更加平滑。在了解了对付走样的基本思路之后，我们就需要详细考虑以下三个问题：
[*]为了得到好的采样结果，同时保证采样的效率，我们应该选择多高的采样频率？
[*]采样和重建阶段分别需要使用什么样的信号过滤器？
[*]在重建时我们使信号光滑到什么程度来避免重建走样？
我们下面将会慢慢回答这几个问题，无需着急，信号处理会用好果汁招待每一个客人的。
卷积(Convolution)
工欲善其事，必先利其器，而在这一章中卷积将是我们进行采样、重建和过滤的有力工具，也是这一节我们将要重点介绍的概念。卷积是一种组合，它将两个函数通过移动和加权平均得到新的函数，我们记为 https://www.zhihu.com/equation?tex=f%5Cstar+g%3Dh ，后面我们将会看到卷积其实就可以看作函数的乘法。
卷积操作的应用范围非常广，我们可以计算两个连续（定义在实数集上，不是数学分析里的连续！）函数的卷积、两个离散函数（定义在整数集上）的卷积、连续函数和离散函数的卷积，以及一维函数的卷积、二维函数的卷积、三维函数的卷积等等。可以看到我们没有考虑定义域有边界的函数，这是因为卷积操作在边缘的情况比较复杂，其解决方案视具体情况而定，我们先搁置对它的讨论。
离散函数的卷积
让我们看看移动和加权平均这两个概念的实际含义。首先从最容易理解的离散情况开始，假设我们有两个离散函数a, b，它们在i处的值用类似数组的a形式表示，卷积结果为 https://www.zhihu.com/equation?tex=a%5Cstar+b ，我们约定在卷积号左边的称为原函数，而在卷积号右边的称为过滤器，并且过滤器会比被卷积函数“短”得多。在我们的例子中，a作为原函数，其中的值大部分不为0；b是过滤器，b=[..., 0, 0, 1/16, 4/16, 6/16, 4/16, 1/16, 0, 0, ...]，其中b=6/16（过滤器基本都是对称的），当|k|>2时b=0，2称为过滤器b的半径，那么a和b的卷积操作如下图所示：
可以从整体的趋势看出，经过卷积之后的函数变得更加平滑了。这就是卷积操作中所谓“过滤器”的含义，原函数经过加权平均之后过滤掉了过高或过低的函数值后获得了更加平滑的图形。
下面给出几个计算的例子，省略的部分都是零：
https://www.zhihu.com/equation?tex=%28a%5Cstar+b%29%5B-1%5D%3D...%2B0%2Ba%5B-3%5D%5Ctimes+b%5B2%5D%2Ba%5B-2%5D%5Ctimes+b%5B1%5D%2Ba%5B-1%5D%5Ctimes+b%5B0%5D%2Ba%5B0%5D%5Ctimes+b%5B-1%5D%2Ba%5B1%5D%5Ctimes+b%5B-2%5D%2B0%2B...%5C%5C+%28a%5Cstar+b%29%5B0%5D%3D...%2B0%2Ba%5B-2%5D%5Ctimes+b%5B2%5D%2Ba%5B-1%5D%5Ctimes+b%5B1%5D%2Ba%5B0%5D%5Ctimes+b%5B0%5D%2Ba%5B1%5D%5Ctimes+b%5B-1%5D%2Ba%5B2%5D%5Ctimes+b%5B-2%5D%2B0%2B...%5C%5C+%28a%5Cstar+b%29%5B1%5D%3D...%2B0%2Ba%5B-1%5D%5Ctimes+b%5B2%5D%2Ba%5B0%5D%5Ctimes+b%5B1%5D%2Ba%5B1%5D%5Ctimes+b%5B0%5D%2Ba%5B2%5D%5Ctimes+b%5B-1%5D%2Ba%5B3%5D%5Ctimes+b%5B-2%5D%2B0%2B...+%5C%5C
可以看到卷积就是一个不断前移，不断加权平均的过程。以上卷积操作扩展到i就是：
https://www.zhihu.com/equation?tex=%28a%5Cstar+b%29%5Bi%5D%3D%5Csum_j+a%5Bj%5Db%5Bi-j%5D+%5C%5C
你可能注意到随着j变化，a和b的自变量的走向是相反的，这或许不合直觉，但是因为过滤器都是对称的，所以b的自变量设置成i-j或是j-i都是一样的，而且特意设置成这样是有原因的，后面我们会看到。
因为b的大部分值都是0，所以半径之外的值都可以不考虑：
https://www.zhihu.com/equation?tex=+%28a%5Cstar+b%29%5Bi%5D%3D%5Csum_%7Bj%3Di-r%7D%5E%7Bi%2Br%7Da%5Bj%5Db%5Bi-j%5D+%5C%5C
写成代码就是：
function convolve(sequence a, filter b, int i)
sum = 0
r = b.radius
for j = i-r to i+r
sum = sum + a * b
return sum可以把卷积中的被卷积函数看作输入，而过滤器是卷积的参数，所以卷积的效果完全取决于选择了什么过滤器。一种常见的过滤器是箱式过滤器(box filter)，它其实就是求平均值：
https://www.zhihu.com/equation?tex=+b%5Bk%5D%3D+%5Cbegin%7Bcases%7D+%5Cfrac%7B1%7D%7B2r%2B1%7D%26-r%5Cleq+k%5Cleq+r%2C%5C%5C+0%26otherwise.+%5Cend%7Bcases%7D%5C%5C
一般来说过滤器的所有值之和都是1，这是为了保证经过卷积之后的函数和原函数的整体趋势不变。下面是一个应用箱式过滤器的例子：
可以看到原函数在i=0处的剧烈变化在卷积之后被抚平了，而在远离i=0的两端，卷积得到的函数的图像和原函数一致。另一种常见的过滤器是离散识别过滤器(discrete identify filter)，d=..., 0, 0, 1, 0, 0, ...，它和任何函数的卷积都是那个函数本身：
https://www.zhihu.com/equation?tex=%28a%5Cstar+d%29%5Bi%5D%3Da%5Bi%5D%5C%5C
卷积的性质
和乘法一样，卷积也遵从交换律、结合律和对加法（我们定义离散函数的加法为 https://www.zhihu.com/equation?tex=%28a%2Bb%29%5Bi%5D%3Da%5Bi%5D%2Bb%5Bi%5D ）的分配律，即：
https://www.zhihu.com/equation?tex=%28a%5Cstar+b%29%5Bi%5D%3D%28b%5Cstar+a%29%5Bi%5D%5C%5C+%28a%5Cstar%28b%5Cstar+c%29%29%5Bi%5D%3D%28%28a%5Cstar+b%29%5Cstar+c%29%5Bi%5D%5C%5C+%28a%5Cstar%28b%2Bc%29%29%5Bi%5D%3D%28a%5Cstar+b%2Ba%5Cstar+c%29%5Bi%5D+%5C%5C
卷积遵从交换律是因为：
https://www.zhihu.com/equation?tex=%28a%5Cstar+b%29%5Bi%5D%3D%5Csum_ja%5Bj%5Db%5Bi-j%5D%5C%5C+%3D%5Csum_ka%5Bi-k%5Db%5Bi-%28i-k%29%5D%5C%5C+%3D%5Csum_kb%5Bk%5Da%5Bi-k%5D%5C%5C
经过变换之后我们可以看到b变成了原函数，a变成了过滤器，所以在卷积操作中函数的角色是可以互换的。现在可以回答为什么在卷积公式中过滤器的自变量是i-j而非j-i了，如果过滤器的自变量是后者的话，让我们试试证明卷积操作遵从交换律：
https://www.zhihu.com/equation?tex=%28a%5Cstar+b%29%5Bi%5D%3D%5Csum_ja%5Bj%5Db%5Bj-i%5D%5C%5C+%3D%5Csum_ka%5Bi-k%5Db%5B%28i-k%29-i%5D%5C%5C+%3D%5Csum_kb%5B-k%5Da%5Bi-k%5D%5C%5C+%3D%5Csum_lb%5Bl%5Da%5Bi%2Bl%5D+%5C%5C
可以看到变换得到的结果已经不是卷积公式了，我们无法证明卷积遵从交换律。
卷积遵从结合律是因为：
https://www.zhihu.com/equation?tex=%28%28a%5Cstar+b%29%5Cstar+c%29%5Bi%5D%3D%5Csum_k%28a%5Cstar+b%29%5Bk%5Dc%5Bi-k%5D%5C%5C+%3D%5Csum_k%5Csum_ja%5Bj%5Db%5Bk-j%5Dc%5Bi-k%5D%5C%5C+%3D%5Csum_ja%5Bj%5D%5Csum_kb%5Bk-j%5Dc%5Bi-j-%28k-j%29%5D%5C%5C+%3D%5Csum_jaj%5Bi-j%5D%5C%5C+%3D%28a%5Cstar+%28b%5Cstar+c%29%29%5Bi%5D+%5C%5C
我们有时会对一个函数做多次卷积，如 https://www.zhihu.com/equation?tex=%28a%5Cstar+b_1%5Cstar+b_2%5Cstar+b_3%29 ，此时可以先算较短的过滤器的卷积 https://www.zhihu.com/equation?tex=%28b_1%5Cstar+b_2%5Cstar+b_3%29 ，再与原函数做卷积，节省运算时间。卷积遵从对加法的分配律是显然的，这里不再赘述。利用以上卷积的性质，我们可以在进行实际的卷积操作前将式子化简，毕竟卷积是一个比较复杂的操作。
移动的过滤器
事实上，我们可以从另一个角度来理解卷积这个操作，不再从单个函数值的角度去理解卷积，而是将卷积理解为把滤波器图像的中心和原函数的每一个值都对齐相乘得到一系列在水平方向上被拉伸压缩的图像，最后将这一系列图像相加得到的就是卷积的结果。
以上定义的关键部分就在于被移动的过滤器，我们定义其为：
https://www.zhihu.com/equation?tex=b_%7B%5Crightarrow+j%7D%5Bi%5D%3Db%5Bi-j%5D%5C%5C
那么 https://www.zhihu.com/equation?tex=b_%7B%5Crightarrow+j%7D 就是将过滤器b的图像右移j个单位（j为负就是左移|j|个单位）得到的新的过滤器，因此卷积的第二种定义就是：
https://www.zhihu.com/equation?tex=+%28a%5Cstar+b%29%3D%5Csum_ja%5Bj%5Db_%7B%5Crightarrow+j%7D+%5C%5C
连续函数的卷积
在讨论完离散函数的卷积之后，连续函数的卷积就可以非常自然地写出了，连续区间上的求和就是积分，因此其卷积为：
https://www.zhihu.com/equation?tex=%28f%5Cstar+g%29%28x%29%3D%5Cint_%7B-%5Cinfty%7D%5E%7B%2B%5Cinfty%7Df%28t%29g%28x-t%29dt+%5C%5C
也就是说 https://www.zhihu.com/equation?tex=%28f%5Cstar+g%29%28x%29 的值是原函数f与过滤器g相乘得到的曲线与x轴围成的面积：
连续函数的卷积的第二种定义也呼之欲出了：
https://www.zhihu.com/equation?tex=%28f%5Cstar+g%29%3D%5Cint_%7B-%5Cinfty%7D%5E%7B%2B%5Cinfty%7Df%28t%29g_%7B%5Crightarrow+t%7Ddt%5C%5C
让我们来看一个卷积的例子，设f是连续版本的箱式过滤器：
https://www.zhihu.com/equation?tex=f%28x%29%3D+%5Cbegin%7Bcases%7D+1%26-%5Cfrac%7B1%7D%7B2%7D%5Cleq+x+%3C+%5Cfrac%7B1%7D%7B2%7D%2C%5C%5C+0%26otherwise.+%5Cend%7Bcases%7D%5C%5C
这个箱式过滤器和自身的卷积会得到另一个常用的连续过滤器，三角形函数(tent function)：
三角形函数的解析式为：
https://www.zhihu.com/equation?tex=+%28f%5Cstar+f%29%3D+%5Cbegin%7Bcases%7D+1-%7Cx%7C%26-1%3Cx%3C1%2C%5C%5C+0%26otherwise.+%5Cend%7Bcases%7D+%5C%5C
同样让我们来看看连续版本的离散识别过滤器德尔塔函数(dirac delta function) https://www.zhihu.com/equation?tex=%5Cdelta%28x%29 ，它是均值为0，方差为 https://www.zhihu.com/equation?tex=%5Cfrac%7B%7Ca%7C%7D%7B%5Csqrt%7B2%7D%7D 的正态分布的概率密度函数在a趋近于无穷时的极限函数：
https://www.zhihu.com/equation?tex=+%5Cdelta%28x%29%3Dlim_%7Ba%5Crightarrow+0%7D%5Cfrac%7B1%7D%7B%7Ca%7C%5Csqrt%7B%5Cpi%7D%7Dexp%7B-%28%5Cfrac%7Bx%7D%7Ba%7D%29%5E2%7D%5C+%5C%5C
简单来说德尔塔函数是一个分段函数：
https://www.zhihu.com/equation?tex=%5Cdelta%28x%29%3D+%5Cbegin%7Bcases%7D+%2B%5Cinfty%26x%3D0%2C%5C%5C+0%26otherwise.+%5Cend%7Bcases%7D%5C%5C+
因为它本质上是个密度概率函数，它有这样的性质：
https://www.zhihu.com/equation?tex=%5Cint_%7B-%5Cinfty%7D%5E%7B%2B%5Cinfty%7D%5Cdelta%28x%29dx%3D1%5C%5C
因此其和任何函数的卷积都是那个函数本身：
https://www.zhihu.com/equation?tex=+%28%5Cdelta%5Cstar+f%29%28x%29%3D%5Cint_%7B-%5Cinfty%7D%5E%7B%2B%5Cinfty%7D%5Cdelta%28t%29f%28x-t%29dt%3Df%28x%29%5C%5C
离散函数与连续函数
乍一看离散函数和连续函数似乎风马牛不相及，但我们可以通过某种方法将它们联系在一起，一种方法是采样，我们取连续函数上的自变量为整数时的值得到一个新的离散函数，就像我们录制音频那样：
https://www.zhihu.com/equation?tex=a%5Bi%5D%3Df%28i%29%5C%5C
另一种方法是重建，我们通过离散函数和连续函数的卷积将离散的函数点“连”起来，得到新的连续函数，就像我们播放音频那样：
比如说当过滤器f的半径为2时，对x=5.3，卷积式是：
https://www.zhihu.com/equation?tex=+%28a%5Cstar+f%29%285.3%29%3D...%2B0%2Ba%5B4%5D%5Ctimes+f%281.3%29%2Ba%5B5%5D%5Ctimes+f%280.3%29%2Ba%5B6%5D%5Ctimes+f%28-0.7%29%2Ba%5B7%5D%5Ctimes+f%28-1.7%29%2B0%2B...
忽略掉所有的0，设过滤器f的半径为r，那么离散函数和连续函数的卷积公式就是：
https://www.zhihu.com/equation?tex=%28a%5Cstar+f%29%28x%29%3D%5Csum_%7Bi%3D%5Clceil+x-r%5Crceil%7D%5E%7B%5Clfloor+x%2Br%5Crfloor%7Da%5Bi%5Df%28x-i%29%5C%5C+%28a%5Cstar+f%29%28x%29%3D%5Csum_ia%5Bi%5Df_%7B%5Crightarrow+i%7D+%5C%5C
写成代码就是：
function reconstruct(sequence a, filter f, real x)
sum = 0
r = f.radius
for i = int(x-r)+1 to int(x+r):
sum = sum + a * f(x - i)
return sum更高维的卷积
到目前为止讨论的卷积都是一维函数的卷积，而图形学中更常用的是二维函数（如图像）的卷积，这一节我们将卷积拓展到更高维的函数上去。
离散函数的二维卷积：
https://www.zhihu.com/equation?tex=+%28a%5Cstar+b%29%5Bi%2C+j%5D+%3D+%5Csum_%7Bi%27%7D%5Csum_%7Bj%27%7Da%5Bi%27%2C+j%27%5Db%5Bi-i%27%2Cj-j%27%5D%5C%5C+%28a%5Cstar+b%29%5Bi%2C+j%5D+%3D+%5Csum_%7Bi%27%3Di-r%7D%5E%7Bi%2Br%7D%5Csum_%7Bj%27%3Dj-r%7D%5E%7Bj%2Br%7Da%5Bi%27%2C+j%27%5Db%5Bi-i%27%2Cj-j%27%5D+%5C%5C
其代码为：
function convolve2d(sequence2d a, filter2d b, int i, int j)
sum = 0
r = b.radius
for i' = i - r to i + r:
for j' = j - r to j + r:
sum = sum + ab
return sum连续函数的二维卷积：
https://www.zhihu.com/equation?tex=%28f%5Cstar+g%29%28x%2C+y%29%3D%5Cint%5Cint+f%28x%27%2Cy%27%29g%28x-x%27%2Cy-y%27%29dx%27dy%27%5C%5C
离散函数和连续函数的二维卷积：
https://www.zhihu.com/equation?tex=%28a%5Cstar+f%29%28x%2Cy%29%3D%5Csum_i%5Csum_ja%5Bi%2Cj%5Df%28x-i%2Cy-j%29%5C%5C
其代码为：
function convolve2d(sequence2d a, filter2d f, int x, int y)
sum = 0
r = f.radius
for i = int(x-r)+1 to int(x+r):
for j = int(y-r)+1 to int(y + r):
sum = sum + af
return sum边界处理
我们最后来看看卷积如何处理边缘的情况，在计算边缘的卷积时是缺少值的，因此我们需要补充新的值，有以下几种处理办法：
[*]扩展(extend)：将边缘的值扩展r个长度
[*]重复(wrap)：取另一边的值，比如在右边卷积时，直接来到左边取缺少的值
[*]镜像(mirror)：想象在边缘放上一面镜子，那么在信号之外的值可以在信号内的对称位置找到
[*]裁剪(crop)：在缺少值的位置选择不卷积，因此卷积结果会比输入要小一圈
[*]常量(constant)：使用一个固定的值补全所有缺少的值
[*]重正化(renormalization)：只选取边界以内的值进行计算，最后对结果进行正规化（保留原函数的趋势）
常用的过滤器
我们已经介绍了卷积的原理，接下来我们将讨论几个在图形学中常用的过滤器，它们的应用场景一般是重构定义在整数集上的离散函数。下面的讨论不再区分过滤器的连续或是离散，所有过滤器都以连续形式给出，对连续形式的过滤器在整数集上采样就可以得到离散版本。
箱式过滤器
我们在上一章已经介绍过这种过滤器了，可以说箱式过滤器代表的就是求平均值，定义为一类函数：
https://www.zhihu.com/equation?tex=f_%7Bbox%2Cr%7D%28x%29%3D+%5Cbegin%7Bcases%7D+1%2F%282r%29%26-r%5Cleq+x+%3C+r%2C%5C%5C+0%26otherwise.+%5Cend%7Bcases%7D%5C%5C
其中半径r是箱式过滤器的参数，注意到连续版本的箱式过滤器中x不取到x=r，否则结果就可能因为多取了值而产生偏差。
三角形过滤器
三角形过滤器(tent filter)是由两个半径为1/2的箱式过滤器做卷积得到的，它的半径为1：
https://www.zhihu.com/equation?tex=%EF%BC%88f_%7Bbox%2C1%2F2%7D%5Cstar+f_%7Bbox%2C1%2F2%7D%29%28x%29%3D%5C+f_%7Btent%7D%28x%29%3D+%5Cbegin%7Bcases%7D+1-%7Cx%7C%26%7Cx%7C%3C1%2C%5C%5C+0%26otherwise.+%5Cend%7Bcases%7D+%5C%5C
三角形过滤器是连续的，但它的一阶导数不连续，因此是
高斯过滤器
高斯过滤器(Gaussian filter)其实就是均值为0的正态分布的概率密度函数：
https://www.zhihu.com/equation?tex=f_%7Bg%2C%5Csigma%7D%28x%29%3D%5Cfrac%7B1%7D%7B%5Csigma%5Csqrt%7B2%5Cpi%7D%7Dexp%7B-%5Cfrac%7Bx%5E2%7D%7B2%5Csigma%5E2%7D%7D%5C%5C
高斯过滤器拥有任意阶的连续导数，很“光滑”，因此是一个效果相当好的过滤器。同时因为它是一个概率密度函数，在实数轴上的积分值为1，所以高斯过滤器没有半径（或者说是无穷大），但我们在实际应用的时候不可能把卷积算到无穷远处，所以需要将它“修剪”一下，忽略其远处几乎为0的函数值，也就是人为赋予它一个半径r。高斯过滤器因此有两个参数：方差σ和半径r.
B-spline filter
B-spline filter是我们遇到的第一个立方式过滤器(cubic filter)，后者往往半径为2，并且是在[-2,2]上的分段多项式函数。B-spline filter是由四个箱式过滤器卷积得到的，我们可以证明之：
https://www.zhihu.com/equation?tex=+f_B%28x%29%3D%28f_%7Bbox%7D%5Cstar+f_%7Bbox%7D%5Cstar+f_%7Bbox%7D%5Cstar+f_%7Bbox%7D%29%28x%29%5C%5C+%3D%28%28f_%7Bbox%7D%5Cstar+f_%7Bbox%7D%29%5Cstar+%28f_%7Bbox%7D%5Cstar+f_%7Bbox%7D%29%28x%29%5C%5C+%3D%28f_%7Btent%7D%5Cstar+f_%7Btent%7D%29%28x%29%5C%5C+%3D%5Cint+f_%7Btent%7D%28t%29f_%7Btent%7D%28x-t%29dt%5C%5C+
根据前文三角形过滤器的解析式，进一步化为：
https://www.zhihu.com/equation?tex=%3D%5Cint_%7B-1%7D%5E1%281-%7Ct%7C%29f_%7Btent%7D%28x-t%29dt%5C%5C
第一个 https://www.zhihu.com/equation?tex=f_%7Btent%7D%28t%29 的情况比较明朗，可以直接写出，但是麻烦的是第二个 https://www.zhihu.com/equation?tex=f_%7Btent%7D%28x-t%29 ，观察三角形函数的解析式，可以得知我们只需要找到 https://www.zhihu.com/equation?tex=f_%7Btent%7D 不为零的区间A，然后根据t, x和0的大小情况在区间A上求积分即可，求不等式组：
https://www.zhihu.com/equation?tex=%5Cbegin%7Bcases%7D+-1%3Ct%3C1%5C%5C+-1%3Cx-t%3C1+%5Cend%7Bcases%7D%5C%5C
因此区间A为：
https://www.zhihu.com/equation?tex=A%3D%5C%7Bt%5C%3B%7Ct%5Cin%28-1%2C1%29%5C%3Band%5C%3Bt%5Cin%28x-1%2Cx%2B1%29%5C%7D%5C%5C
最简单的情况就是区间A为空集，此时积分为0:
https://www.zhihu.com/equation?tex=x-1%3E1%5C%3Bor%5C%3Bx%2B1%3C-1%5C%5C+x%5Cin%28-%5Cinfty%2C-2%29%5Ccup%282%2C%5Cinfty%29%5C%5C
接下来我们讨论 https://www.zhihu.com/equation?tex=x%5Cin%5B-2%2C2%5D 的情况，A是两个长度相同的区间的交集，并且x恰好是其中一个区间的中心点，因此积分区间只需要考虑x和0的关系，只有两种情况：
https://www.zhihu.com/equation?tex=%5Cbegin%7Bcases%7D+A%3D%5B-1%2Cx%2B1%5D%26x%5Cin%5B-2%2C0%29%5C%5C+A%3D%5Bx-1%2C1%5D%26x%5Cin%5B0%2C2%5D+%5Cend%7Bcases%7D%5C%5C+
我们现在可以大概写出的解析式了：
https://www.zhihu.com/equation?tex=f_B%3D+%5Cbegin%7Bcases%7D+%5Cint_%7Bx-1%7D%5E1%281-%7Ct%7C%29%281-%7Cx-t%7C%29dt%26x%5Cin%5B0%2C2%5D%5C%5C+%5Cint_%7B-1%7D%5E%7Bx%2B1%7D%281-%7Ct%7C%29%281-%7Cx-t%7C%29dt%26x%5Cin%5B-2%2C0%29%5C%5C+0%26%7Cx%7C%3E2.+%5Cend%7Bcases%7D%5C%5C
为了求积分还需要去掉绝对值符号，接下来我们讨论x和t以及t和0的关系：
[*]https://www.zhihu.com/equation?tex=x%5Cin%281%2C2%5D%5C%3Band%5C%3Bt%5Cin%28x-1%2C1%29%5Cimplies+x-t%3E0%5C%3Band%5C%3Bt%3E0
[*]https://www.zhihu.com/equation?tex=x%5Cin%5B-2%2C-1%29%5C%3Band%5C%3Bt%5Cin%28-1%2Cx%2B1%29%5Cimplies+x-t%3C0%5C%3Band%5C%3Bt%3C0
[*]https://www.zhihu.com/equation?tex=x%5Cin%5B0%2C1%5D
[*]https://www.zhihu.com/equation?tex=t%5Cin%28x-1%2C0%29%5Cimplies+x-t%3E0%5C%3Band%5C%3Bt%3C0
[*]https://www.zhihu.com/equation?tex=t%5Cin%280%2Cx%29%5Cimplies+x-t%3E0%5C%3Band%5C%3Bt%3E0
[*]https://www.zhihu.com/equation?tex=t%5Cin%28x%2C1%29%5Cimplies+x-t%3C0%5C%3Band%5C%3Bt%3E0
[*]https://www.zhihu.com/equation?tex=x%5Cin%5B-1%2C0%29
[*]https://www.zhihu.com/equation?tex=t%5Cin%28-1%2Cx%29%5Cimplies+x-t%3E0%5C%3Band%5C%3Bt%3C0
[*]https://www.zhihu.com/equation?tex=t%5Cin%28x%2C0%29%5Cimplies+x-t%3C0%5C%3Band%5C%3Bt%3C0
[*]https://www.zhihu.com/equation?tex=t%5Cin%280%2Cx%2B1%29%5Cimplies+x-t%3C0%5C%3Band%5C%3Bt%3E0
根据以上讨论，进一步写出的解析式：
https://www.zhihu.com/equation?tex=f_B%3D+%5Cbegin%7Bcases%7D+%5Cint_%7Bx-1%7D%5E0%281%2Bt%29%281-x%2Bt%29dt%2B%5Cint_%7B0%7D%5Ex%281-t%29%281-x%2Bt%29dt%2B%5Cint_%7Bx%7D%5E1%281-t%29%281%2Bx-t%29dt%26x%5Cin%5B0%2C1%5D%5C%5C+%5Cint_%7B-1%7D%5Ex%281%2Bt%29%281-x%2Bt%29dt%2B%5Cint_%7Bx%7D%5E0%281%2Bt%29%281%2Bx-t%29dt%2B%5Cint_%7B0%7D%5E%7Bx%2B1%7D%281-t%29%281%2Bx-t%29dt%26x%5Cin%5B-1%2C0%29%5C%5C+%5Cint_%7B-1%7D%5E%7Bx%2B1%7D%281-t%29%281-x%2Bt%29dt%26x%5Cin%281%2C2%5D%5C%5C+%5Cint_%7B-1%7D%5E%7Bx%2B1%7D%281%2Bt%29%281%2Bx-t%29dt%26x%5Cin%5B-2%2C-1%29%5C%5C+0%26%7Cx%7C%3E2.+%5Cend%7Bcases%7D%5C%5C
求积分并化简得到最后的答案：
https://www.zhihu.com/equation?tex=f_B%28x%29%3D%5Cfrac%7B1%7D%7B6%7D+%5Cbegin%7Bcases%7D+-3%281-%7Cx%7C%29%5E3%2B3%281-%7Cx%7C%29%5E2%2B3%281-%7Cx%7C%29%2B1%26-1%5Cleq+x%5Cleq+1%2C%5C%5C+%282-%7Cx%7C%29%5E3%261%5Cleq+%7Cx%7C%5Cleq2%2C%5C%5C+0%26otherwise.+%5Cend%7Bcases%7D%5C%5C
B-spline filter拥有二阶连续导数，因此是 https://www.zhihu.com/equation?tex=C%5E2
Catmull-Rom cubic filter
另外一个重要的立方式过滤器是Catmull-Rom cubic filter，从下图可以看出它存在负数值，并且在±1, ±2处的函数值都为零，因此我们可以称Catmull-Rom cubic filter为重建时的插值过滤器（后面会解释）
这个过滤器的解析式如下：
https://www.zhihu.com/equation?tex=f_C%28x%29%3D+%5Cfrac%7B1%7D%7B2%7D+%5Cbegin%7Bcases%7D+-3%281-%7Cx%7C%29%5E3%2B4%281-%7Cx%7C%29%5E2%2B%281-%7Cx%7C%29%26-1%5Cleq+x%5Cleq1%2C%5C%5C+%282-%7Cx%7C%29%5E3-%282-%7Cx%7C%29%5E2%261%5Cleq%7Cx%7C%5Cleq2%2C%5C%5C+0%26otherwise.+%5Cend%7Bcases%7D%5C%5C
Mitchell-Netravali cubic filter
B-spline filter和Catmull-Rom cubic filter都有各自的优缺点，不能在所有应用场景中都有较好的表现，Mitchell-Netravali cubic filter综合了这两个过滤器，是一个相对全能的过滤器。可能令人有些惊讶，这个过滤器只是B-spline filter和Catmull-Rom cubic filter的线性组合：
https://www.zhihu.com/equation?tex=+f_M%28x%29%3D%5Cfrac%7B1%7D%7B3%7Df_B%28x%29%2B%5Cfrac%7B2%7D%7B3%7Df_C%28x%29%5C%5C+%3D%5Cfrac%7B1%7D%7B18%7D+%5Cbegin%7Bcases%7D+-21%281-%7Cx%7C%29%5E3%2B27%281-%7Cx%7C%29%5E2%2B9%281-%7Cx%7C%29%2B1%26-1%5Cleq+x%5Cleq+1%2C%5C%5C+7%282-%7Cx%7C%29%5E3-6%282-%7Cx%7C%29%5E2%261%5Cleq%7Cx%7C%5Cleq2%2C%5C%5C+0%26otherwise.%5C+%5Cend%7Bcases%7D%5C%5C+
过滤器的性质
[*]插值的(interpolating)：使用这种过滤器重建出来的图像会经过用于重建的所有的采样点，形象地说就是将采样点“连了起来”，所有存在这个性质的过滤器都满足以下条件： https://www.zhihu.com/equation?tex=f%280%29%3D1%5C%3Band%5C%3Bf%28i%29%3D0%2C%5C%3B%5C%3Bi%5Cin+Z%2F%7B0%7D ，这样一来在过滤器中心与采样点对齐时只会取当前采样点。
[*]过冲(overshoot)：所有带有负的函数值的过滤器都是过冲的，这一性质会在重建出来的图像上引入本来不存在的震荡，例如下图是在使用Catmull-Rom cubic filter重建一个阶梯函数，这个过滤器的过冲性质在阶梯函数的值变化时将变化的趋势扩大了，造成了不自然的震荡。
[*]无波纹的(ripple free)：如果一个过滤器被用于重建一个常数序列时得到的函数时常数函数，那么这个过滤器就是无波纹的，它将常数序列重建成常数函数，写成公式就是 https://www.zhihu.com/equation?tex=%5Csum_if%28x%2Bi%29%3D1 ，其实任何过滤器都可以修正为无波纹的，只需在卷积时除以采样点序列的和即可： https://www.zhihu.com/equation?tex=%28%5Coverline%7Ba%5Cstar+f%7D%29%28x%29%3D%5Cfrac%7B%5Csum_ia%5Bi%5Df%28x-i%29%7D%7B%5Csum_ia%5Bi%5D%7D
[*]连续度(degree of continuity)：连续度衡量的是过滤器最高阶的连续导数的阶，如果只有它本身连续，那么这个过滤器的连续度就是，以此类推。因为离散函数重建后图像的连续度就来自于过滤器，所以连续度越高的过滤器重建出的函数图像就越光滑，高斯过滤器也因此能产出非常光滑的图像
分离式过滤器(separable filters)
我们接下来讨论二维的过滤器，通常来说，任何二维函数都可以用作过滤器，当然我们不会如此随便，我们要在已经介绍的一维过滤器的基础上构造出二维过滤器，实际上使用我们接下来要介绍的构造方法的话，我们可以将一维过滤器有效率地扩展到任意维度上。这个方法很简单，就是把多个一维过滤器相乘！
我们称通过这种方法构造出来的多维过滤器为分离式过滤器，其数学表达式为：
https://www.zhihu.com/equation?tex=+f_2%28x%2Cy%29%3Df_1%28x%29f_1%28y%29%5C+b_2%5Bi%2Cj%5D%3Db_1%5Bi%5Db_1%5Bj%5D+%5C%5C
当然为了保证不改变原函数的平均趋势，被用于相乘的这些一维过滤器都是经过标准化的。让我们看几个分离式过滤器的例子。
二维三角形过滤器
二维三角形过滤器的解析式为：
https://www.zhihu.com/equation?tex=+f_%7B2%2Ctent%7D%28x%2Cy%29%3D+%5Cbegin%7Bcases%7D+%281-%7Cx%7C%29%281-%7Cy%7C%29%26%7Cx%7C%3C1%5C%3Band%5C%3B%7Cy%7C%3C1%2C%5C%5C+0%26otherwise.%5C+%5Cend%7Bcases%7D%5C%5C+
图像如下：
这是一个形状有些古怪的二维函数，沿着x轴和y轴得到的一维函数都是三角形函数，而沿着其他经过原点的直线得到的一维函数是二次函数，比如沿着x=y得到的一维函数是 https://www.zhihu.com/equation?tex=%281-x%29%5E2
二维高斯过滤器
我们选定方差为1的一维高斯过滤器，则二维高斯过滤器的解析式为：
https://www.zhihu.com/equation?tex=+f_%7B2%2Cg%7D%28x%2Cy%29%3D%5Cfrac%7B1%7D%7B2%5Cpi%7Dexp%7B-%5Cfrac%7Bx%5E2%2By%5E2%7D%7B2%7D%7D%5C%5C+%3D%5Cfrac%7B1%7D%7B2%5Cpi%7Dexp%7B-%5Cfrac%7Br%5E2%7D%7B2%7D%7D%5C%5C
其图像为：
这是一个完美的环形对称的形状，如果我们拿出一把刀经过原点在任意方向上切开这个几何体，都会看到一样的截面，沿所有经过原点的直线得到的一维函数都是一维高斯函数。
分离式过滤器的性能
我们之所以要用这种方法来构建高维过滤器，是因为这样构建出来的过滤器有性能上的优势。简单起见，我们使用离散形式的分离式过滤器讨论，这个讨论对连续形式也成立。二维卷积的计算式可以化为：
https://www.zhihu.com/equation?tex=+%28a%5Cstar+b_2%29%5Bi%2Cj%5D%3D%5Csum_%7Bi%27%7D%5Csum_%7Bj%27%7Da%5Bi%27%2Cj%27%5Db_2%5Bi-i%27%2Cj-j%27%5D%5C%5C+%3D%5Csum_%7Bi%27%7D%5Csum_%7Bj%27%7Da%5Bi%27%2Cj%27%5Db_1%5Bi-i%27%5Db_1%5Bj-j%27%5D%5C%5C+%3D%5Csum_%7Bi%27%7Db_1%5Bi-i%27%5D%5Csum_%7Bj%27%7Da%5Bi%27%2Cj%27%5Db_1%5Bj-j%27%5D+%5C%5C
因此我们可以利用提出来的 https://www.zhihu.com/equation?tex=%5Csum_%7Bi%27%7Db%5Bi-i%27%5D 减少计算步骤：
https://www.zhihu.com/equation?tex=+S%5Bi%27%5D%3D%5Csum_%7Bj%27%7Da%5Bi%27%2Cj%27%5Db_1%5Bj-j%27%5D%5C+%28a%5Cstar+b_2%29%5Bi%2Cj%5D%3D%5Csum_%7Bi%27%7Db_1%5Bi-i%27%5DS%5Bi%27%5D%5C%5C
如此我们就极大地减少了计算每个像素时需要的步骤数量，给定过滤器的半径r，原来计算每个像素都需要进行 https://www.zhihu.com/equation?tex=%282r%2B1%29%5E2 次乘法，而在使用了分离式过滤器之后，我们就只需要在每个像素进行 https://www.zhihu.com/equation?tex=2%282r%2B1%29 次乘法。
其代码形式如下：
function filterImage(image I, filter b)
r = b.radius
nx = I.width
ny = I.height
allocate storage array S
allocate sotrage image Iout
//将输出的图片的边界裁剪掉
for i = r to nx - r - 1:
for j = r to ny - r - 1:
Iout=0
for j = r to ny - r - 1:
for i' = 0 to nx - 1:
S = 0
for j' = j - r to j + r:
S = S + Ib
for i = r to nx - r - 1:
for i' = i - r to i + r:
Iout = Iout + Sb
return Iout图片的信号处理(Singal Processing for Images)
在讨论完卷积和过滤器之后，我们终于可以来讨论卷积在图像处理方面的应用了，这也是我们研究卷积的最初动机，接下来让我们看看卷积在图像处理上的几种重要的应用。
使用离散过滤器进行图片过滤(Image Filtering)
图片过滤中最简单的操作就是图片模糊(image blurring)，我们只需要使用一个或多个过滤器对图片（实际上就是离散的二维函数）进行卷积即可。高斯过滤器可以产出效果极佳的结果，因此常被用于图片模糊，写成公式为 https://www.zhihu.com/equation?tex=I_%7Bblur%7D%3DI%5Cstar+f_%7Bg%2C%5Csigma%7D ，其中是二维高斯过滤器的宽度（半径的两倍）。
与之相对的是图片锐化，锐化可以类似地看作模糊的逆操作，我们实际上也是如此实现锐化的，将“模糊”的部分从图片中以某个比例去除，就得到了锐化的图像：
https://www.zhihu.com/equation?tex=I_%7Bsharp%7D%3D%281%2B%5Calpha%29I-%5Calpha%28I%5Cstar+f_%7Bg%2C%5Csigma%7D%29%5C%5C+%3DI%28%281%2B%5Calpha%29d-%5Calpha+f_%7Bg%2C%5Csigma%7D%29%5C%5C+%3DI%5Cstar+f_%7Bsharp%7D%28%5Csigma%2C+%5Calpha%29%5C%5C
其中 https://www.zhihu.com/equation?tex=f_%7Bsharp%7D%28%5Csigma%2C%5Calpha%29%3D%28%281%2B%5Calpha%29d-%5Calpha+f_%7Bg%2C%5Csigma%7D%29 ，它有两个参数，\sigma是二维高斯过滤器的宽度， https://www.zhihu.com/equation?tex=%5Calpha 是锐化度。
另一个卷积在图像处理的应用例子是阴影(drop shadow)，如下图：
要想达到这个效果需要多个过滤器组合发挥作用，包括一个模糊过滤器和一个位移过滤器（阴影和物体本身肯定存在相对位移）:
https://www.zhihu.com/equation?tex=d_%7Bm%2Cn%7D%28i%2Cj%29%3D+%5Cbegin%7Bcases%7D+1%26i%3Dm%2Cj%3Dn%2C%5C%5C+0%26otherwise.%5C%5C+%5Cend%7Bcases%7D%5C%5C+I_%7Bshadow%7D%3D%28I%5Cstar+d_%7Bm%2Cn%7D%29%5Cstar+f_%7Bg%2C%5Csigma%7D%5C%5C+%3DI%5Cstar+%28d_%7Bm%2Cn%7D%5Cstar+f_%7Bg%2C%5Csigma%7D%29%5C%5C+%3DI%5Cstar+f_%7Bshadow%7D%28m%2Cn%2C%5Csigma%29%5C%5C
图片采样中的反走样(antialiasing)
在图片处理中我们时常会遇到采样操作，尤其是从一个连续的图片信号中采样得到一个离散的图片信号，正如我们在绘制直线或者三角形时做的那样。如果我们在采样时不采取任何措施，也就是使用离散识别过滤器(discrete identify filter)进行采样，得到的图片将会产生十分明显的走样。常见的例子有锯齿和摩尔纹：
这里遇到的问题和我们在本章一开始介绍的数字音频采样的问题是一模一样的：被采样的图片信号中存在频率高过采样能力的信号。因此我们需要使用过滤器将过高频率的信号过滤掉，下面是几种过滤器采样同一个连续图片信号的的结果，这个连续图片描述了一组随着半径增大彼此距离逐渐减小的同心圆：
可以看到从左到右摩尔纹不断减少，采样的效果是逐渐变好的。其实高斯过滤器在减少摩尔纹上有更好的效果，但同时经过它采样出来的图片也更模糊。所以在选择采样使用的过滤器时，我们需要在锐化度和走样程度之间做出取舍，没有过滤器可以做到既可以极大降低走样，同时又能保证很高的锐化度。
重建和重采样(Resampling)
另一个常见的图片操作就是调整图片的尺寸，这一操作属于重采样的一种，也就是改变信号的采样率。比如我们将一张12x9的图片调整成8x6的尺寸，输出的图像的像素就位于原图像的像素之间了，因此我们就需要计算离散的像素之间的值，如下图：
对此我们先将原图像从离散函数重建成连续函数，然后再根据新的图片尺寸或采样率对重建出来的连续函数采样，这样就得到了调整尺寸后的图像，这就是重采样。
为了减少重采样中的走样，在重建和采样步骤中我们都需要选择合适的过滤器。选择过滤器时我们需要在性能和重采样效果之间做取舍，如果需要极致的性能，我们会在重采样中直接选择距离新的像素点最近的原像素值，也就是在重采样中首先使用以半个像素为半径的箱式过滤器重建，然后使用离散识别过滤器(discrete identify filter)直接取得当前点上的值。一般来说这种策略产出的画面是非常差的，并且由于离散识别过滤器的不连续性（只在x=0处为1），在很多通用框架中都无法使用这一过滤器。
重采样操作写成公式为 https://www.zhihu.com/equation?tex=g%5Cstar+%28f%5Cstar+I%29 ，f是重建过滤器，g是采样过滤器，使用之前介绍的卷积性质，可以得到重采样过滤器就是 https://www.zhihu.com/equation?tex=g%5Cstar+f
二维图像上的重采样写成代码为（忽略边界情况）：
function resample(image I, float x0, float y0, float deltaX, float deltaY, int nx, int ny, filter f):
create image Iout of width nx and height ny
r = f.radius
for x = 0 to nx-1:
for y = 0 to ny-1:
sum = 0
for i = int(x0+x*deltaX-r)+1 to int(x0+x*deltaX+r):
for j = int(y0+y*deltaY-r)+1 to int(y0+y*deltaY+r):
sum = sum + f(x-i, y-j) * I
Iout = sum
return Iout其中(x0, y0)是重采样开始的点，deltaX, deltaY是重采样在两个方向上的步长，nx, ny是输出图片的尺寸。
对这个合并而来的重采样过滤器来说有两方面的要求，一方面重建要求该过滤器足够光滑，另一方面采样要求该过滤器的半径足够大，不至于产生低采样走样(undersampling artifacts)，并且也需要足够光滑来避免如摩尔纹这样的走样。在选定了过滤器的形状以后，我们就需要根据应用场景来决定使用多大半径的过滤器。
对于将图片缩小的操作来说，采样的要求更加严格，我们需要半径足够大的过滤器来进行重采样；而对于将图片放大的操作来说，重建的要求更加严格，我们需要更多的信息来进行重建，因此我们需要半径较小的过滤器进行重采样。
采样定理(Sampling Theory)
目前为止介绍的所有算法已经足以让我们实现一个优秀的采样和重建程序了，但我们的讨论到此仍有缺失，我们只定义了什么是“好”，但没有真正说明“好”为什么好，这一节我们将使用更多数学来说服自己这就是“好”。
傅里叶变换(Fourier Transform)
傅里叶变换是所有涉及信号处理的书籍绕不开的概念，傅里叶变换的基本思路就是使用一系列的三角函数之和来表示任意函数在所有频率上的函数值，例如下面这个被一系列正弦函数之和表示的方波函数：
https://www.zhihu.com/equation?tex=+%5Csum%5E%7B%5Cinfty%7D_%7Bn%3D1%2C3%2C5%2C...%7D%5Cfrac%7B4%7D%7B%5Cpi+n%7Dsin%282%5Cpi+nx%29+%5C%5C
下面这幅图像展示了随着n增大，和函数不断趋近于真正的方波函数的过程：
方波函数是一个典型的周期函数，但傅里叶变换可以用三角函数估计任何函数，包括非周期函数，只是这时我们会需要更多三角函数，此时和就变成了积分，比如说箱式过滤器用三角函数表示就是：
https://www.zhihu.com/equation?tex=f_%7Bbox%7D%28x%29%3D%5Cint_%7B-%5Cinfty%7D%5E%5Cinfty+%5Cfrac%7Bsin%5Cpi+u%7D%7B%5Cpi+u%7Dcos%282%5Cpi+ux%29du%5C%5C
这个被积分式可以写成 https://www.zhihu.com/equation?tex=%5Chat+f%28u%29%5Ccdot+g%28u%2Cx%29 的形式，函数 https://www.zhihu.com/equation?tex=g 的权重是函数，箱式过滤器的傅里叶变换就是这个权重，可以看到傅里叶变换即指一种数学运算，又指这种运算得到的结果。将这个式子进一步变换就可以得到傅里叶变换公式：
https://www.zhihu.com/equation?tex=f_%7Bbox%7D%28x%29%3D%5Cint_%7B-%5Cinfty%7D%5E%5Cinfty+%5Cfrac%7Bsin%5Cpi+u%7D%7B%5Cpi+u%7Dcos%282%5Cpi+ux%29du%5C%5C+%3D%5Cint_%7B-%5Cinfty%7D%5E%5Cinfty+%5Cfrac%7Bsin%5Cpi+u%7D%7B%5Cpi+u%7Dcos%282%5Cpi+ux%29du%2B0i%5C%5C+%3D%5Cint_%7B-%5Cinfty%7D%5E%5Cinfty+%5Cfrac%7Bsin%5Cpi+u%7D%7B%5Cpi+u%7Dcos%282%5Cpi+ux%29du%2Bi%5Cint_%7B-%5Cinfty%7D%5E%5Cinfty+%5Cfrac%7Bsin%5Cpi+u%7D%7B%5Cpi+u%7Dsin%282%5Cpi+ux%29du%5C%5C+%3D%5Cint_%7B-%5Cinfty%7D%5E%5Cinfty+%5Cfrac%7Bsin%5Cpi+u%7D%7B%5Cpi+u%7D%5Bcos%282%5Cpi+ux%29%2Bisin%282%5Cpi+ux%29%5Ddu%5C%5C+%3D%5Cint_%7B-%5Cinfty%7D%5E%5Cinfty+%5Chat+f%28u%29e%5E%7B2%5Cpi+iux%7Ddu%5C%5C
因为这一章的函数都是关于y轴对称的，我们的讨论不会涉及复数。我们约定原函数 https://www.zhihu.com/equation?tex=f 是时域上的函数，而其傅里叶变换是频域上的函数，我们通过傅里叶变换将时域上的函数变换到频域上，而又能通过逆傅里叶变换将频域上的函数变换回时域上。我们用 https://www.zhihu.com/equation?tex=%5Cdigamma%5C%7Bf%5C%7D 表示傅里叶变换运算，而 https://www.zhihu.com/equation?tex=%5Cdigamma%5E%7B-1%7D%5C%7B%5Chat+f%5C%7D 表示傅里叶逆运算。
https://www.zhihu.com/equation?tex=%5Chat+f%28u%29%3D%5Cint_%7B-%5Cinfty%7D%5E%5Cinfty+f%28x%29e%5E%7B-2%5Cpi+iux%7Ddx%5C%5C+f%28x%29%3D%5Cint_%7B-%5Cinfty%7D%5E%5Cinfty+%5Chat+f%28u%29e%5E%7B2%5Cpi+iux%7Ddu%5C%5C
傅里叶变换有以下性质：
[*]https://www.zhihu.com/equation?tex=%5Cdigamma+%5C%7Baf%5C%7D%3Da%5Cdigamma%5C%7Bf%5C%7D
[*]根据积分的性质，我们可以得到傅里叶变换不会改变函数图像与x轴围成的图形的面积，即：
https://www.zhihu.com/equation?tex=%5Cint%5E%7B%5Cinfty%7D%7B-%5Cinfty%7D%5Bf%28x%29%5D%5E2dx%3D%5Cint%5E%7B%5Cinfty%7D%7B-%5Cinfty%7D%5B%5Chat+f%28u%29%5D%5E2du%5C%5C
[*]在水平方向上拉伸时域上的函数会导致时域上的函数在水平方向上被压缩，并且在竖直方向上被拉伸，即 https://www.zhihu.com/equation?tex=%5Cdigamma%7Bf%28x%2Fb%29%7D%3Db%5Chat+f%28bx%29 。根据这一结论我们可以由一个基过滤器的傅里叶变换得到它的其他宽度（两倍半径）以及高度的版本，比如我们可以直接写出宽度为b，高度为a的箱式过滤器的傅里叶变换为 https://www.zhihu.com/equation?tex=ab%5Cfrac%7Bsin%28%5Cpi+bu%29%7D%7Bbu%7D 。这一结论的证明以及图示如下。
https://www.zhihu.com/equation?tex=%5Cint_%7B-%5Cinfty%7D%5E%5Cinfty+f%28x%2Fb%29e%5E%7B-2%5Cpi+iux%7Ddx+%3D+b%5Cint_%7B-%5Cinfty%7D%5E%5Cinfty+f%28x%2Fb%29e%5E%7B-2%5Cpi+iub%5Ccdot+x%2Fb%7Dd%28x%2Fb%29%5C%5C+%3Db%5Cint_%7B-%5Cinfty%7D%5E%5Cinfty+f%28y%29e%5E%7B-2%5Cpi+ibu%5Ccdot+y%7Ddy%5C%5C+%3Db%5Chat+f%28bu%29+%5C%5C
[*] 约定 https://www.zhihu.com/equation?tex=%5Cdigamma+%5C%7Bf%5C%7D%3D%5Chat+f ，那么 https://www.zhihu.com/equation?tex=%5Cint_%7B-%5Cinfty%7D%5E%5Cinfty+f%28x%29dx%3D%5Chat+f%280%29 ，这可以从频域的概念上理解，函数f中所有的周期性的函数值在积分后全部彼此抵消了，因此其在实数域中的积分就只有非周期的部分的函数值，即 https://www.zhihu.com/equation?tex=%5Chat+f%280%29
[*]时域和频域上的乘法和卷积是可以互换的，这是最后也是最重要的一条性质，根据这一条性质我们就可以将时域上的卷积转换成频域上的乘法，这就直观了许多
https://www.zhihu.com/equation?tex=%5Cdigamma%5C%7Bf%5Cstar+g%5C%7D%3D%5Chat+f%5Chat+g%5C%5C+%5Cdigamma%5C%7Bfg%5C%7D%3D%5Chat+f%5Cstar+%5Chat+g%5C%5C
常用过滤器的傅里叶变换
这里首先介绍一些常用过滤器的傅里叶变换，为之后在频域上的讨论做准备。
[*]箱式过滤器： https://www.zhihu.com/equation?tex=%5Cdigamma%5C%7Bf_%7Bbox%7D%5C%7D%3D%5Cfrac%7Bsin%28%5Cpi+u%29%7D%7B%5Cpi+u%7D%3Dsinc%28%5Cpi+u%29
[*]三角过滤器： https://www.zhihu.com/equation?tex=%5Cdigamma%5C%7Bf_%7Btent%7D%5C%7D%3D%5Cfrac%7Bsin%5E2%28%5Cpi+u%29%7D%7B%5Cpi%5E2+u%5E2%7D%3Dsinc%5E2%28%5Cpi+u%29
[*]B-spline filter： https://www.zhihu.com/equation?tex=%5Cdigamma%5C%7Bf_%7Btent%7D%5C%7D%3D%5Cfrac%7Bsin%5E4%28%5Cpi+u%29%7D%7B%5Cpi%5E4+u%5E4%7D%3Dsinc%5E4%28%5Cpi+u%29
[*]高斯过滤器，其傅里叶变换仍然是一个高斯过滤器： https://www.zhihu.com/equation?tex=%5Cdigamma%5C%7Bf_%7BG%7D%5C%7D%3De%5E%7B-%282%5Cpi+u%29%5E2%2F2%7D
采样函数和走样
一直到现在我们都将采样视为一个游离在卷积之外的操作，但实际上我们可以定义采样函数来将采样变成一个乘法操作。对笛卡尔平面上任意一点(a,b)，我们可以用 https://www.zhihu.com/equation?tex=b%5Cdelta%28x-a%29 代表之，因此对任意函数f在x=a处取样的操作就可以写成 https://www.zhihu.com/equation?tex=f%28a%29%5Cdelta%28x-a%29 ，而根据一定频率进行采样就是将一系列德尔塔函数相加：
https://www.zhihu.com/equation?tex=s_T%28x%29%3D%5Csum%5E%5Cinfty_%7Bi%3D-%5Cinfty%7D%5Cdelta%28x-Ti%29%5C%5C
其中1/T是取样的频率，这样的函数图像就像一列无限长的火车：
采样函数有个非常优秀的性质，其傅里叶变换仍是采样函数，只是它的周期从T变成了1/T，比如 https://www.zhihu.com/equation?tex=%5Cdigamma%5C%7Bs_1%28x%29%5C%7D%3Ds_1%28u%29 ，我们可以从这个特例出发反向证明这个性质：
https://www.zhihu.com/equation?tex=%5Cint_%7B-%5Cinfty%7D%5E%5Cinfty+e%5E%7B-2%5Cpi+iux%7D%5Csum%5E%5Cinfty_%7Bi%3D-%5Cinfty%7D%5Cdelta%28x-i%29dx%3D%5Csum%5E%5Cinfty_%7Bi%3D-%5Cinfty%7D%5Cdelta%28u-i%29%5C%5C+%5Cdigamma%5C%7Bs_T%28x%29%5C%7D%3D%5Cint_%7B-%5Cinfty%7D%5E%5Cinfty+e%5E%7B-2%5Cpi+iux%7D%5Csum%5E%5Cinfty_%7Bi%3D-%5Cinfty%7D%5Cdelta%28x-Ti%29dx%5C%5C%3D%5Cint_%7B-%5Cinfty%7D%5E%5Cinfty+e%5E%7B-2%5Cpi+iux%7D%5Csum%5E%5Cinfty_%7Bi%3D-%5Cinfty%7D%5Cdelta%28T%28x%2FT-i%29%29dx%5C%5C+%3DT%5Cint_%7B-%5Cinfty%7D%5E%5Cinfty+e%5E%7B-2%5Cpi+iTu%5Ccdot+x%2FT%7D%5Csum%5E%5Cinfty_%7Bi%3D-%5Cinfty%7D%5Cdelta%28%28x%2FT-i%29%2F%281%2FT%29%29d%5Cfrac%7Bx%7D%7BT%7D%5C%5C+%3D%281%2FT%29%5Ccdot+T%5Ccdot%5Csum%5E%5Cinfty_%7B-%5Cinfty%7D%5Cdelta%28%281%2FT%29%5Ccdot+Tu+-+i%2FT%29%5C%5C+%3D%5Csum%5E%5Cinfty_%7Bi%3D-%5Cinfty%7D%5Cdelta%28u-i%2FT%29%5C%5C
因此就有 https://www.zhihu.com/equation?tex=%5Cdigamma%5C%7Bs_T%28x%29%5C%7D%3Ds_%7B1%2FT%7D%28u%29 。使用采样函数，我们就可以解释采样中产生的走样究竟是从何而来的了，时域上被采样的函数和采样函数相乘尚不明朗，因此我们将它转换到频域上：
https://www.zhihu.com/equation?tex=%5Cdigamma%5C%7Bf%5Ccdot+s_T%5C%7D%3D%5Chat+f%5Cstar+s_%7B1%2FT%7D%5C%5C+%3D%5Csum_%7B-%5Cinfty%7D%5E%5Cinfty+%5Chat+f%28u+-+i%2FT%29%5C%5C+%3D%5Csum_%7B-%5Cinfty%7D%5E%5Cinfty+%5Chat+f%28u+-+%5Cupsilon+i%29%5C%5C
根据德尔塔函数的性质，就得到采样实际上就是将原信号按照采样频率 https://www.zhihu.com/equation?tex=%5Cupsilon 的整数倍平移无数次得到一系列新信号，最后将这一系列新信号相加就得到最后的结果，信号重叠相加的部分就自然产生了走样，正如下图看到的那样，在 https://www.zhihu.com/equation?tex=u%5Cin%5B-%5Cupsilon%2F2%2C%5Cupsilon%2F2%5D 区间内的信息受到的影响很小，而在这个区间之外的频率上就开始出现明显的信号重叠了，首先出现的是整体平移了一个采样频率的新波峰，然后是平移了两个采样频率的新波峰，然后是平移了三个采样频率的图像...
如果我们在使用了这么糟糕的采样之后，再使用箱式过滤器来重建图片，最终呈现出来的图片效果就是上幅图第三行的结果。箱式过滤器的傅里叶变换已经给出，因此这个卷积就相当于频域上的函数相乘：
https://www.zhihu.com/equation?tex=%5Chat+I%28u%29%5Ccdot%5Cfrac%7Bsin%28%5Cpi+u%29%7D%7B%5Cpi+u%7D%5C%5C
因为 https://www.zhihu.com/equation?tex=sinc%28%5Cpi+u%29 这个函数在相当大的范围内都有不可忽略的函数值，因此在采样阶段产生的重叠信号也不可避免地和不小的函数值相乘，成为最后结果中的走样，在这幅图中表现为方块样的色块。
减少采样中的走样
在讨论音频信号的采样时我们就已经提到过，采样中的走样就是来自超出采样频率的信号，我们直接提高采样频率，可以十分明显地提升采样的质量。这一操作相当于在频域上将被平移的其他频谱移动到尽可能远的地方，当采样频率达到我们需要的频率范围的边界时，走样程度达到最小。如果我们能够将采样频率提高到高于信号的最高频率的水平，我们就能够将信号原封不动地重建出来。
当然，提高走样频率是一个代价很大的方案，采样频率的每一次翻倍也就意味着运算量的翻倍。我们还需要通过将高频信号过滤掉，去掉这些高频信号基本是无伤大雅的，可以从图像看出来大部分信息都集中在低频率范围内。过滤器将时域上的函数图像抚平，也就相当于在水平方向上挤压频域上的函数图像。
因此好的采样需要足够光滑的过滤器和足够高的采样频率相互配合，即使在一个极高的采样频率下我们不需要过滤器，其仍然能够在相当程度上减少图像重叠相加的问题。
减少重建中的走样
理想情况下，重建过滤器应该将采样阶段产生的重叠信号变得尽可能小。因为卷积在频域上成为了乘法操作，重建过滤器因此成为了采样后信号在各个频率上的权重，就这要求其傅里叶变换只在0的一个相当小的邻域内有不可忽略的函数值，而在这个邻域之外的函数值都可以认为是0，可以看到越优秀的重建过滤器其傅里叶变换的图像越窄，但是这个图像不能过分窄，因为这反而会影响到低频范围上的信息。
好 请问，计算机图形学，除了信号与系统，还需要哪些基础？ 实际上图形学是一个非常庞杂的学科，基本上入门的话有高数和线代基础就行，其他的知识用到再学都是没问题的 除了高数和线代，还需要什么？我提前学下。
页:
[1]