卷积

泛函分析中,卷积(又称叠积(convolution)、褶积旋积),是透过两个函数 fg 生成第三个函数的一种数学算子,表征函数 f 与经过翻转和平移的 g 的乘积函数所围成的曲边梯形的面积。如果将参加卷积的一个函数看作区间指示函数,卷积还可以被看作是“移动平均”的推广。

图示两个方形脉冲波的卷积。其中函数"g"首先对反射,接着平移"t",成为。那么重叠部分的面积就相当于"t"处的卷积,其中横坐标代表待变量以及新函数的自变量"t"。
图示方形脉冲波和指数衰退的脉冲波的卷积(后者可能出现于RC电路中),同样地重叠部分面积就相当于"t"处的卷积。注意到因为"g"是对称的,所以在这两张图中,反射并不会改变它的形状。

简单介绍

卷积是数学分析中一种重要的运算。设:   上的两个可积函数,作积分

 

可以证明,关于几乎所有的 ,上述积分是存在的。这样,随着 的不同取值,这个积分就定义了一个新函数 ,称为函数  的卷积,记为 。我们可以轻易验证: ,并且 仍为可积函数。这就是说,把卷积代替乘法, 空间是一个代数,甚至是巴拿赫代数。虽然这里为了方便我们假设  ,不过卷积只是运算符号,理论上并不需要对函数   有特别的限制,虽然常常要求   至少是可测函数(measurable function)(如果不是可测函数的话,积分可能根本没有意义),至于生成的卷积函数性质会在运算之后讨论。

卷积与傅里叶变换有着密切的关系。例如两函数的傅里叶变换的乘积等于它们卷积后的傅里叶变换,利用此一性质,能简化傅里叶分析中的许多问题。

由卷积得到的函数 一般要比  都光滑。特别当 为具有紧支集的光滑函数 为局部可积时,它们的卷积 也是光滑函数。利用这一性质,对于任意的可积函数 ,都可以简单地构造出一列逼近于 的光滑函数列 ,这种方法称为函数的光滑化或正则化

卷积的概念还可以推广到数列测度以及广义函数上去。

定义

函数   是定义在   上的可测函数(measurable function),  的卷积记作 ,它是其中一个函数反转(reverse),并平移后,与另一个函数的乘积的积分,是一个对平移量的函数,也就是:

 

如果函数不是定义在   上,可以把函数定义域以外的值都规定成零,这样就变成一个定义在   上的函数。

图解卷积
  1. 已知两函数f(t)和g(t)。右图第一行两图分别为f(t)和g(t)。
  2. 首先将两个函数都用 来表示,从而得到f( )和g( )。将函数g( )向左移动t个单位,得到函数g( +t)的图像。将g( +t)翻转至纵轴另一侧,得到g(t- )的图像。右图第二行两图分别为f( )和g(t- )。
  3. 由于t非常数(实际上是时间变量),当时间变量(以下简称“时移”)取不同值时, 能沿着 轴“滑动”。右图第三四五行可理解为“滑动”。
  4. 让t从-∞滑动到+∞。两函数交会时,计算交会范围中两函数乘积的积分值。换句话说,我们是在计算一个滑动的的加权总和(weighted-sum)。也就是使用 当做加权函数,来对 取加权值。
最后得到的波形(未包含在此图中)就是fg的卷积。如果ft是一个单位脉冲,我们得到的乘积就是gt本身,称为冲激响应

离散卷积

对于定义在整数   上的函数  ,卷积定义为

 
 

这里一样把函数定义域以外的值当成零,所以可以扩展函数到所有整数上(如果本来不是的话)。

  的支撑集(support)为有限长度 ,上式会变成有限和:

 

计算离散卷积的方法

计算卷积 有三种主要的方法,分别为

  1. 直接计算(Direct Method)
  2. 快速傅里叶变换(FFT)
  3. 分段卷积(sectioned convolution)

方法1是直接利用定义来计算卷积,而方法2和3都是用到了FFT来快速计算卷积。也有不需要用到FFT的作法,如使用数论变换

方法1:直接计算

  • 作法:利用卷积的定义
 
  •   皆为实数信号,则需要 个乘法。
  •   皆为更一般性的复数信号,不使用复数乘法的快速算法,会需要 个乘法;但若使用复数乘法的快速算法,则可简化至 个乘法。
因此,使用定义直接计算卷积的复杂度为 

方法2:快速傅里叶变换(FFT)

  • 概念:由于两个离散信号在时域(time domain)做卷积相当于这两个信号的离散傅里叶变换在频域(frequency domain)做相乘:
 
,可以看出在频域的计算较简单。
  • 作法:因此这个方法即是先将信号从时域转成频域:
 
,于是
 
,最后再将频域信号转回时域,就完成了卷积的计算:
 
总共做了2次DFT和1次IDFT。
  • 特别注意DFT和IDFT的点数 要满足 
  • 由于DFT有快速算法FFT,所以运算量为 
  • 假设 点DFT的乘法量为   为一般性的复数信号,并使用复数乘法的快速算法,则共需要 个乘法。

方法3:分段卷积(sectioned convolution)

  • 概念:将 切成好几段,每一段分别和 做卷积后,再将结果相加。
  • 作法:先将 切成每段长度为 的区段( ),假设共切成S段:
 
Section 1:  
Section 2:  
 
Section r:  
 
Section S:  
 为各个section的和
 
因此,
 
每一小段作卷积则是采用方法2,先将时域信号转到频域相乘,再转回时域:
 
  • 总共只需要做 点FFT  次,因为 只需要做一次FFT。
  • 假设 点DFT的乘法量为   为一般性的复数信号,并使用复数乘法的快速算法,则共需要 个乘法。
  • 运算量: 
  • 运算复杂度: ,和 呈线性,较方法2小。
  • 分为 Overlap-Add 和 Overlap-Save 两种方法。

分段卷积: Overlap-Add

欲做 的分段卷积分,  长度为    长度为  ,

Step 1: 将   分成一段

Step 2: 再每段   点后面添加   个零,变成长度  

Step 3: 把   添加  个零,变成长度   

Step 4: 把每个   的小段和   做快速卷积,也就是 ,每小段会得到长度   的时域信号

Step 5: 放置第   个小段的起点在位置   上,  

Step 6: 会发现在每一段的后面   点有重叠,将所有点都相加起来,顾名思义 Overlap-Add,最后得到结果

举例来说:

 , 长度  

 , 长度  

 

  切成三段,分别为  , 每段填   个零,并将   填零至长度  

将每一段做 

若将每小段摆在一起,可以注意到第一段的范围是   ,第二段的范围是  ,第三段的范围是  ,三段的范围是有重叠的

最后将三小段加在一起,并将结果和未分段的卷积做比较,上图是分段的结果,下图是没有分段并利用快速卷积所算出的结果,验证两者运算结果相同。

分段卷积: Overlap-Save

欲做 的分段卷积分,  长度为    长度为  ,

Step 1: 将   前面填   个零

Step 2: 第一段  , 从新的    取到   总共   点当做一段,因此每小段会重复取到前一小段的   点,取到新的一段全为零为止

Step 3: 把   添加   个零,变成长度   

Step 4: 把每个   的小段和   做快速卷积,也就是 ,每小段会得到长度   的时域信号

Step 5: 对于每个   小段,只会保留末端的   点,因此得名 Overlap-Save

Step 6: 将所有保留的点合再一起,得到最后结果

举例来说:

 , 长度  

 , 长度  

 

  前面填   个零以后,按照 Step 2 的方式分段,可以看到每一段都重复上一段的  

再将每一段做  以后可以得到

保留每一段末端的   点,摆在一起以后,可以注意到第一段的范围是   ,第二段的范围是  ,第三段的范围是  ,第四段的范围是  ,四段的范围是没有重叠的

将结果和未分段的卷积做比较,下图是分段的结果,上图是没有分段并利用快速卷积所算出的结果,验证两者运算结果相同。

至于为什么要把前面   丢掉?

以下以一例子来阐述:

 , 长度  

 , 长度  ,

第一条蓝线代表   轴,而两条蓝线之间代表长度  ,是在做快速卷积时的周期

当在做快速卷积时 ,是把信号视为周期  ,在时域上为循环卷积分,

而在一开始前   点所得到的值,是    内积的值,

然而    个值应该要为零,以往在做快速卷积时长度为   时不会遇到这些问题,

而今天因为在做快速卷积时长度为   才会把这   点算进来,因此我们要丢弃这   点内积的结果

为了要丢弃这   点内积的结果,位移     点,并把位移以后内积合的值才算有效。

应用时机

以上三种方法皆可用来计算卷积,其差别在于所需总体乘法量不同。基于运算量以及效率的考量,在计算卷积时,通常会选择所需总体乘法量较少的方法。

以下根据  的长度( )分成5类,并列出适合使用的方法:

  1.  为一非常小的整数 - 直接计算
  2.   - 分段卷积
  3.   - 快速傅里叶变换
  4.   - 分段卷积
  5.  为一非常小的整数 - 直接计算

基本上,以上只是粗略的分类。在实际应用时,最好还是算出三种方法所需的总乘法量,再选择其中最有效率的方法来计算卷积。

例子

Q1:当 ,适合用哪种方法计算卷积?

Ans:

方法1:所需乘法量为 
方法2: ,而2016点的DFT最少乘法数 ,所以总乘法量为 
方法3:
若切成8块( ),则 。选 ,则总乘法量为 ,比方法1和2少了很多。
但是若要找到最少的乘法量,必须依照以下步骤
(1)先找出 :解  :  
(2)由 算出点数在 附近的DFT所需最少的乘法量,选择DFT的点数
(3)最后由 算出 
因此,
(1)由运算量对 的偏微分为0而求出 
(2) ,所以选择101点DFT附近点数乘法量最少的点数  
(3-1)当 ,总乘法量为 
(3-2)当 ,总乘法量为 
由此可知,切成20块会有较好的效率,而所需总乘法量为21480。
  • 因此,当 ,所需总乘法量:分段卷积<快速傅里叶变换<直接计算。故,此时选择使用分段卷积来计算卷积最适合。

Q2:当 ,适合用哪种方法计算卷积?

Ans:

方法1:所需乘法量为 
方法2: ,选择1026点DFT附近点数乘法量最少的点数, 
因此,所需乘法量为 
方法3:
(1)由运算量对 的偏微分为0而求出 
(2) ,所以选择7点DFT附近点数乘法量最少的点数   
(3-1)当 ,总乘法量为 
(3-2)当 ,总乘法量为 
(3-3)当 ,总乘法量为 
由此可知,切成171块会有较好的效率,而所需总乘法量为5476。
  • 因此,当 ,所需总乘法量:分段卷积<直接计算<快速傅里叶变换。故,此时选择使用分段卷积来计算卷积最适合。
  • 虽然当 是个很小的正整数时,大致上适合使用直接计算。但实际上还是将3个方法所需的乘法量都算出来,才能知道用哪种方法可以达到最高的效率。

Q3:当 ,适合用哪种方法计算卷积?

Ans:

方法1:所需乘法量为 
方法2: ,选择1026点DFT附近点数乘法量最少的点数, 
因此,所需乘法量为 
方法3:
(1)由运算量对 的偏微分为0而求出 
(2) ,所以选择1623点DFT附近点数乘法量最少的点数 
(3)当 ,总乘法量为 
由此可知,此时切成一段,就跟方法2一样,所需总乘法量为44232。
  • 因此,当 ,所需总乘法量:快速傅里叶变换 = 分段卷积<直接计算。故,此时选择使用分段卷积来计算卷积最适合。

多元函数卷积

按照翻转、平移、积分的定义,还可以类似的定义多元函数上的积分:

 

性质

各种卷积算子都满足下列性质:

交换律
 
结合律
 
分配律
 
数乘结合律
 

其中 为任意实数(或复数)。

微分定理
 

其中Df表示f微分,如果在离散域中则是指差分算子,包括前向差分与后向差分两种:

  • 前向差分: 
  • 后向差分: 

卷积定理

卷积定理指出,函数卷积的傅里叶变换是函数傅里叶变换的乘积。即,一个域中的卷积相当于另一个域中的乘积,例如时域中的卷积就对应于频域中的乘积。

 

其中 表示f傅里叶变换

这一定理对拉普拉斯变换双边拉普拉斯变换Z变换Mellin变换Hartley变换(参见Mellin inversion theorem英语Mellin inversion theorem)等各种傅里叶变换的变体同样成立。在调和分析中还可以推广到在局部紧致的阿贝尔群上定义的傅里叶变换。

利用卷积定理可以简化卷积的运算量。对于长度为 的序列,按照卷积的定义进行计算,需要做 组对位乘法,其计算复杂度 ;而利用傅里叶变换将序列变换到频域上后,只需要一组对位乘法,利用傅里叶变换的快速算法之后,总的计算复杂度为 。这一结果可以在快速乘法计算中得到应用。

在群上的卷积

G是有某m 测度(例如豪斯多夫空间哈尔测度局部紧致拓扑群),对于Gm-勒贝格可积实数复数函数fg,可定义它们的卷积:

 

对于这些群上定义的卷积同样可以给出诸如卷积定理等性质,但是这需要对这些群的表示理论以及调和分析的彼得-外尔定理

应用

卷积在科学、工程和数学上都有很多应用:

  • 代数中,整数乘法和多项式乘法都是卷积。
  • 图像处理中,用作图像模糊、锐化、边缘检测
  • 统计学中,加权的滑动平均是一种卷积。
  • 概率论中,两个统计独立变量X与Y的和的概率密度函数是X与Y的概率密度函数的卷积。
  • 声学中,回声可以用源声与一个反映各种反射效应的函数的卷积表示。
  • 电子工程与信号处理中,任一个线性系统的输出都可以通过将输入信号与系统函数(系统的冲激响应)做卷积获得。
  • 物理学中,任何一个线性系统(符合叠加原理)都存在卷积。

参见

外部链接