计算机图形学基础-离散卷积

卷积是概率论中的一个核心结构,这一方法随处可见,在图像处理中尤为明显,在求解微分方程时也被大量使用。

定义

在了解卷积之前,我们都知道,光看没有上下文的公式化定义,卷积会变得十分唬人。
$$
(f*g)(t):=\int f(x)\cdot g(t-x)dx
$$
但是本质上,卷积具有十分美丽的定义。

从概率论开始

有一个最简单的例子,即“扔两枚骰子”,计算两枚骰子各个点数之和的概率。显然,每个骰子有六个面,我们也就能得到36种组合情形。

1 2 3 4 5 6
1 2 3 4 5 6 7
2 3 4 5 6 7 8
3 4 5 6 7 8 9
4 5 6 7 8 9 10
5 6 7 8 9 10 11
6 7 8 9 10 11 12

有一件很妙的事情是,相同点数和的组合都排列在一条对角线上,所以主要数出对角线上有多少个组合,就能知道某个组合的概率是多少。

我们可以用另一种方式来描述这个问题。我们把两个骰子每个面的结果排列在一起,并把下面一个骰子反转:

1 2 3 4 5 6
6 5 4 3 2 1

那在示例中,让上下两行相加,我们就得到了点数和为7的骰子的组合数。这时,我们挨个移动处于下方的骰子组合:

1 2 3 4 5 6
6 5 4 3 2 1

就得到了点数和为8的骰子的组合数。以此类推,我们可以得到所有的骰子组合数。

到目前为止,这个概率问题还不是很有趣,我们只是数出了每种组合的骰子和有多少个。但这里其实蕴含了一个假设,即骰子每个面向上的概率是相同的。

此时,如果我们换用灌铅的骰子,用一个数组来描述骰子某个面向上的概率:

0.16 0.21 0.17 0.16 0.12 0.18
0.13 0.20 0.10 0.24 0.22 0.11

这时,如果我们想算出组合出现2的情景,就要用上方骰子出现1的概率乘下方骰子出现1的概率。如果要计算出现2的概率,就要将对应组合点数出现的概率分别相乘。秉着公式化的精神,我们用字母替代原先的概率:

$a_1$ $a_2$ $a_3$ $a_4$ $a_5$ $a_6$
$b_1$ $b_2$ $b_3$ $b_4$ $b_5$ $b_6 $

这时我们可以发现,拿出两列不同的数组,将上下两列对应位置的值相乘,得到一组乘积之后将它们相加,这整个过程就是卷积的基本思考方式。说得更精确一些,我们通过这个过程,生成了对应点数和的概率,而这个通过某种运算将A和B数组的值交汇的过程,就是卷积。
$$
P(2)=a_1\cdot b_1
$$

$$
P(3)=a_1\cdot b_2 + a_2 \cdot b_1
$$

$$
P(4)=a_1 \cdot b_2 + a_2\cdot b_2 + a_3 \cdot b_1
$$

$$

$$

用更专业的话来说,两组数的卷积生成了新的一组数。新的数列包含11个值(2~12),每个值都是两数组中若干数对之积的加和。另一种思考卷积的方式是,列一个表格,计算各个组合的乘积,然后沿对角线相加,这样就把两组数混合了起来,得到了一组11个数。这个做法很像滑动窗口,只是换了一些方法。

我们可以这样表示卷积:
$$
(ab)n=\sum{i,j(i+j)=n}a_i\cdot b_jhe
$$
其结果是一个列表,它的第$n$项定义为:把下标$i,j$之和为$n$的诸元素的乘积累加起来的值。因此还有另一种形式的写法:
$$
(a
b)n=\sum{n-i}a_i\cdot b_j
$$

二维图像卷积

我们已经在求和得出概率分布的例子中看到了卷积运算是多么美妙,而另一个常见例子是滑动平均。假设有一个长数组和另一个所有数之和为1的短数组:

0.1 0.1 0.1 0.1 0.2 1.0 1.0 1.0 0.1
0.25 0.25 0.25 0.25

接下来,如果我们重复这个滑动窗口卷积的过程。我们很容易发现,每一次迭代时,我们实际上是在把长数组中的每个值乘上0.25,然后将它们加起来。换句话说,我们是在求小窗口里数据的平均值。而这个过程,实际上给了你一个原始数据的平滑版本。你可以修改它,使其从一个不同的短数组中开始,只要短数组的和还是1,你就仍然可以把它解读为滑动平均。

0.1 0.1 0.1 0.1 0.2 1.0 1.0 1.0 0.1
0.25 0.5 0.25

在这个新的例子中,滑动平均会给中间值更大的权重,我们得到的结果也将是原数据的平均版本。如果我们在二维图像上进行类似的操作,我们实际上就是对图像进行了模糊处理。而显然,在图像上,我们可以应用二维的列表进行卷积操作。我们把这样的用于进行卷积操作的列表称为卷积核

而事实上,我们能做的远不止是模糊。假设我们有这样一个3×3的卷积核:

0.25 0.00 -0.25
0.50 0.00 -0.50
0.25 0.00 -0.25

在使用它对图像进行影响时,我们可以发现,在这个3×3的卷积核范围内,最左边一列和最右边值的差距越小,卷积后所得到的值的绝对值就越小,反之则越大。那么实际上,我们可以认为,这里是在求像素值从左到右是否发生了变化。这里的卷积核让我们可以判断图像的竖边界。同样的,如果将卷积核旋转九十度,我们就能得到判断图像横边界的新处理效果。

在图像处理上应用卷积的巧妙之处在于,只需要选择不同的卷积核,就可以产生不同的图像处理效果,包括模糊、边缘检测和锐化等等。

我们常常谈到的卷积神经网络,其基本思想就是用数据来算出应该选取什么样的核,这取决于想用神经网络进行检测的目标。

另一个应该提及的事情是输出的长度。对于滑动平均这样的情况,或许只需要考虑取样窗口完全对应的情况就好了。或者在图像处理中,我们常常想要保证输出图像的尺寸和原图像相同。事实上,在纯数学过程中的卷积,产生的数组总是比两个初始数组更长,至少在数组长度都大于1的时候是这样的。而在某些计算机的输出情景下,我们需要刻意截取掉部分输出值,只考虑卷积核的完全覆盖部分。同时,在计算机运算的情境下,我们常常不会翻转卷积核,因为这看起来就很不适合理解,也没有必要。

快速卷积算法

卷积采样与多项式恢复

上文中,我们提到了一个“计算各组合对角线”的例子计算卷积。事实上,这种方法并不只是在概率论里用得上——只要是求两个数的卷积时,我们就可以这么思考。有一种情况会让这样的对角运算看起来十分自然且合理,那就是我们耳熟能详的多项式乘法:
$$
(1+2x+3x^2)(4+5x+6x^2)=4+13x+28x^2+27x^3+18x^4
$$
我们把两个多项式写入表格:

$1$ $2x$ $3x^2$
$4$ $4$ $8x$ $12x^2$
$5x$ $5x$ $10x^2$ $15x^3$
$6x^2$ $6x^2$ $12x^3$ $18x^4$

很容易发现,我们在沿对角线求和的时候,就是在合并多项式乘法的同类项。换句话说,拓展并合并多项式的过程实际上和卷积的过程是一模一样的。

再回想一下,我们究竟是在干什么。如果把多项式看成是一个函数,那我们实际上就是在对两个函数本身做乘法运算,也就是一个简单的逐顶点运算。这相当于是,假设它们为多项式,首先提取多项式的系数,然后对这些系数组成的数组进行卷积。非常有意思的是,卷积看起来要比直接相乘更复杂一点,这不仅是在概念上的,也是在时间复杂度上的。相较于两个数组逐点进行乘积来说,卷积需要更多的步骤来执行计算。

然而,如果我们只考虑多项式的函数输出值,比如只对少数几个输入值进行采样计算,那么乘法运算的执行次数就等于样本的数量,因为这也是一个逐顶点操作。那么考虑回多项式的情况,我们只需要有限的样本量就足以重现多项式的系数。比如,两个函数输出值就能确定一个唯一的线性多项式$y=ax+b$,三个函数输出值就能确定唯一的一个二次多项式$y=ax^2+bx+c$。推而广之,如果我们知道$N$个函数输出值,就能确定一个唯一的$n-1$次多项式。

如果用方程组的形式来表述,假设我们有一些系数未知的多项式,且我们假定了不同的输入值后,可以得知这个多项式的输出值,同时我们可以得到与未知数系数个数相同数量的方程式,这就已经足够用于恢复系数了,因为它们已经构成了一个基本的线性方程组。

所以粗略的算法大纲是,当需要对两个数组进行卷积时,我们可以把它们视作两个多项式的系数,对这些多项式的输出值尽可能地采样,并对这些样本逐顶点地相乘,最后求解并恢复系数。

然而,求解这个多项式样本同样十分复杂。不过幸运的是,我们可以使用傅里叶变换的思路进行计算。

快速傅里叶变换

使用傅里叶变换加速卷积运算的基本思路是,如果我们不像原先那样,输入任意的数值集合来计算,而是通过输入特定的复数来进行求解,尤其是在单位圆上分布均匀的那些,我们的多项式中就会出现许多冗余项,巧妙地利用这些冗余项,就能为我们加快运算速度。而这一变换,就是系数的离散傅里叶变换。在这里,我们不会进行过多的对FFT的介绍,而我们只需要知道,快速傅里叶变换可以将数从时域变换到频域,逆变换则可以将数从频域变换到时域。对数进行时域上的卷积,其实就相当于进行频域上的乘积。而对数进行频域上的乘积,亦相当于进行时域上的乘积。

那么总结一下,在快速卷积算法中,我们先对原序列和卷积核分别进行快速傅里叶变换,随后我们将对应的两个结果逐顶点相乘,随后进行逆快速傅里叶变换,我们就得到了一个计算卷积的取巧方法。

尽管应用到卷积的情景仅仅是多项式相乘,但它引出了FFT,而在任何使用卷积的地方,我们都能看到FFT的身影。例如,在一些大型的图像处理中,添加一些概率分布之类的东西。这有力地证明了,一个值得我们兴奋的情形在于,看似无关的几个领域,出现了相同的数学运算或是概念。

考虑一个更让人兴奋的点,实际上在进行我们熟知的乘法运算时,实际上就相当于在求两数各个数位之间的卷积。而应用这一快速算法,我们就可以在进行大数计算时,用更高的效率得到两个大数的乘积。


计算机图形学基础-离散卷积
https://tridiamond.tech/post/CGMath-1.html
作者
想变成一只白泽
发布于
2023年4月11日
许可协议