卷积

在泛函分析中，捲積（convolution），或译为疊積、-{褶}-積或旋積，是透過两个函数和生成第三个函数的一种数学算子，表徵函数与经过翻转和平移的的乘積函數所圍成的曲邊梯形的面積。如果将参加卷积的一个函数看作区间的指示函数，卷积还可以被看作是“滑動平均”的推廣。

 定义 
卷积是数学分析中一种重要的运算。设：和是实数上的两个可积函数，定义二者的卷积为如下特定形式的积分变换：

仍为可积函数，并且有着：

函数和，如果只支撑在之上，则积分界限可以截断为：

对于

对于两个得出复数值的，可以定义二者的卷积为如下形式的多重积分：


卷积有一个通用的工程上的符号约定：

它必须被谨慎解释以避免混淆。例如：等价于，而却实际上等价于。

历史
卷积运算的最早使用出现在达朗贝尔于1754年出版的《宇宙体系的几个要点研究》中对泰勒定理的推导之中Dominguez-Torres, p 2。还有，将类型的表达式，用在他的1797年–1800年出版的著作《微分与级数论文》中on page 505 of his book entitled Treatise on differences and series, which is the last of 3 volumes of the encyclopedic series: Traité du calcul différentiel et du calcul intégral, Chez Courcier, Paris, 1797–1800. Dominguez-Torres, p 4。此后不久，卷积运算出现在皮埃尔-西蒙·拉普拉斯、约瑟夫·傅里叶和西梅翁·泊松等人的著作中。这个运算以前有时叫做“Faltung”（德语中的折叠）、合成乘积、叠加积分或卡森积分。

“卷积”这个术语早在1903年就出现了，然而其定义在早期使用中是相当生僻的，直到1950年代或1960年代之前都未曾广泛使用。

简介
如果和都是在Lp 空间内的勒贝格可积函数，则二者的卷积存在，并且在这种情况下也是可积的。这是托內利定理的结论。对于在中的函数在离散卷积下，或更一般的对于在任何群的上的卷积，这也是成立的。同样的，如果而，这里的，则，并且其Lp 范数间有着不等式：

在的特殊情况下，这显示出是在卷积下的巴拿赫代数（并且如果和几乎处处非负则两边间等式成立）。

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

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

函数和的互相关，等价于的共轭复数与的卷积：

这里的叫做移位（displacement）或滞后（lag）。

对于單位脈衝函数和某个函数，二者得到的捲積就是本身，此被稱為衝激響應：

在连续时间线性非时变系统中，输出信号被描述为输入信号与冲激响应的卷积：

两个独立的随机变量和，每个都有一个概率密度函数，二者之和的概率密度，是它们单独的密度函数的卷积：

 图解 

已知右侧第一行图中两个函数和。
首先將兩個函數都用约束变量來表示，并将翻转至纵轴另一侧，从而得到右侧第二行图中和。
向函数增加一个时间偏移量，得到函数。不是常数而是自由变量，当取不同值时，能沿着轴“滑动”。如果是正值，则等于沿着轴向右（朝向）滑动数量。如果是负值，则等价于向左（朝向）滑动数量。
讓從变化至，当兩個函數交會時，計算交會範圍中兩個函數乘積的積分值。換句話說，在时间，计算函数经过权重函数施以权重后其下的面积。右侧第三、第四和第五行图中，分别是、和时的情况，从时开始有交会，例如在第四行图中，则，则，对于有着。
最後得到的波形（未包含在此圖中）就是和的捲積。468px两个矩形脈衝波的捲積。其中函数首先对反射，接著平移，成為。那么重叠部份的面积就相当于处的卷积，其中橫坐標代表待变量以及新函數的自變量。File:Convolution of box signal with itself2.gif矩形脈衝波和指數衰減脈衝波的捲積（後者可能出現於RC電路中），同樣地重疊部份面積就相當於處的捲積。注意到因為是對稱的，所以在這兩張圖中，反射並不會改變它的形狀。File:Convolution of spiky function with box2.gif

 周期卷积 

两个周期的函数和的“周期卷积”定义为：

这里的是任意参数。

任何，都可以通过求函数的所有整数倍的平移的总和，从而制作出具有周期的周期函数 ，这叫做：

对于无周期函数与，其周期的周期求和分别是与，与的周期卷积，可以定义为与的常规卷积，或与的常规卷积，二者都等价于与的周期积分：

圆周卷积是周期卷积的特殊情况，其中函数和二者的非零部份，都限定在区间之内，此时的周期求和称为“周期延拓”。中函数可以通过取非负余数的模除运算表达为“圆周函数”：

而积分的界限可以缩简至函数的长度范围：

 离散卷积 
对于定义在整數上且得出复数值的函数和，离散卷积定义为：

這裡一樣把函數定義域以外的值當成零，所以可以擴展函數到所有整數上（如果本來不是的話）。两个有限序列的卷积的定义，是将这些序列扩展成在整数集合上有限支撑的函数。在这些序列是两个多项式的系数之时，这两个多项式的普通乘积的系数，就是这两个序列的卷积。这叫做序列系数的柯西乘积。

當的支撐集為有限長度的之时，上式會變成有限求和：

多维离散卷积

类似于一维情况，使用星号表示卷积，而维度体现在星号的数量上，维卷积就写为个星号。下面是维信号的卷积的表示法：

对于离散值的信号，这个卷积可以直接如下这样计算：

结果的离散多维卷积所支撑的输出区域，基于两个输入信号所支撑的大小和区域来决定。

离散周期卷积
对于离散序列和一个参数，无周期函数和的“周期卷积”是为：

这个函数有周期，它有最多个唯一性的值。和的非零范围都是的特殊情况叫做圆周卷积：

离散圆周卷积可简约为矩阵乘法，这里的积分变换的核函数是循环矩阵:

圆周卷积最经常出现的快速傅里叶变换的实现算法比如雷德演算法之中。

 性质 
代数

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

交换律


结合律


分配律


数乘结合律

其中为任意实数（或复数）。

复数共轭


微分有关

积分有关
如果，并且，则有：

 积分 
如果和是可积分函数，则它们在整个空间上的卷积的积分，简单的就是它们积分的乘积：


这是富比尼定理的结果。如果和只被假定为非负可测度函数，根据托内利定理，这也是成立的。

微分
在一元函数情况下，和的卷积的导数有着：

这里的是微分算子。更一般的说，在多元函数的情况下，对偏导数也有类似的公式：

这就有了一个特殊结论，卷积可以看作“光滑”运算：和的卷积可微分的次数，是和的总数。

这些恒等式成立的严格条件，为和是绝对可积分的，并且至少二者之一有绝对可积分（）弱导数，这是的结论。

在离散情况下，差分算子满足类似的关系：


 卷积定理 

卷积定理指出，在适当的条件下，两个函数（或信号）的卷积的傅里叶变换，是它们的傅里叶变换的逐点乘积。更一般的说，在一个域（比如时域）中的卷积等于在其他域（比如频域）逐点乘法。

设两个函数和，分别具有傅里叶变换和：

这里的算子指示傅里叶变换。

卷积定理声称：

应用逆傅里叶变换产生推论：

这里的算符指示逐点乘法。

这一定理对拉普拉斯变换、双边拉普拉斯变换、Z变换、梅林变换和等各种傅里叶变换的变体同样成立。在调和分析中还可以推广到在局部紧致的阿贝尔群上定义的傅里叶变换。

周期卷积
对于周期为的函数和，可以被表达为二者的：

它们的傅里叶级数系数为：

这里的算子指示傅里叶级数积分。

逐点乘积的周期也是，它的傅里叶级数系数为：

周期卷积的周期也是，周期卷积的卷积定理为：

离散卷积
对于作为两个连续函数采样的序列和，它们具有离散时间傅里叶变换和：

这里的算子指示离散时间傅里叶变换（DTFT）。

离散卷积的卷积定理为：

离散周期卷积
对于周期为的序列和：

相较于离散时间傅里叶变换和的周期是，它们是按间隔采样和，并在个采样上进行了逆离散傅里叶变换（DFT-1或IDFT）的结果。

离散周期卷积的周期也是。离散周期卷积定理为：

这里的算子指示长度的离散傅里叶变换（DFT）。

它有着推论：

对于其非零时段小于等于的和，离散圆周卷积的卷积定理为：

推广
卷积的概念还可以推广到数列、测度以及广义函数上去。函数是定義在上的可測函數（measurable function），与存在卷积并记作。如果函數不是定義在上，可以把函數定義域以外的值都規定成零，這樣就變成一個定義在上的函數。

若G是有某m 测度的群（例如豪斯多夫空间上哈尔测度下局部紧致的拓扑群），对于G上m-勒贝格可积的实数或复数函数f和g，可定义它们的卷积：

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

离散卷積的計算方法 
計算卷積有三種主要的方法，分別為
直接計算（Direct Method）
快速傅立葉轉換（FFT）
分段卷積（sectioned convolution）
方法1是直接利用定義來計算卷積，而方法2和3都是用到了FFT來快速計算卷積。也有不需要用到FFT的作法，如使用數論轉換。

方法1：直接計算

作法：利用卷積的定義



若和皆為實數信號，則需要個乘法。

若和皆為更一般性的複數信號，不使用複數乘法的快速演算法，會需要個乘法；但若使用複數乘法的快速演算法，則可簡化至個乘法。

因此，使用定義直接計算卷積的複雜度為。

方法2：快速傅立葉轉換

概念：由於兩個離散信號在時域（time domain）做卷積相當於這兩個信號的離散傅立葉轉換在頻域（frequency domain）做相乘：

，可以看出在頻域的計算較簡單。

作法：因此這個方法即是先將信號從時域轉成頻域：



，於是



，最後再將頻域信號轉回時域，就完成了卷積的計算：



總共做了2次DFT和1次IDFT。

特別注意DFT和IDFT的點數要滿足。

由於DFT有快速演算法FFT，所以運算量為

假設點DFT的乘法量為，和為一般性的複數信號，並使用複數乘法的快速演算法，則共需要個乘法。

方法3：分段卷積

概念：將切成好幾段（section），每一段分別和做卷積後，再將結果相加。

作法：先將切成每段長度為的區段（），假設共切成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類，並列出適合使用的方法：

 為一非常小的整數 - 直接計算
  - 分段卷积
  - 快速傅里叶变换
  - 分段卷积
 為一非常小的整數 - 直接計算

基本上，以上只是粗略的分類。在實際應用時，最好還是算出三種方法所需的總乘法量，再選擇其中最有效率的方法來計算卷積。

 例子 

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。
因此，當，所需總乘法量：快速傅立葉轉換 = 分段卷積<直接計算。故，此時選擇使用分段卷積來計算卷積最適合。

 应用 
卷积在科学、工程和数学上都有很多应用：
 代数中，整数乘法和多项式乘法都是卷积。
 卷积神经网络应用了多重级联的卷积，它被用于机器视觉和人工智能，尽管在多数情况下实际上用的是互相关而非卷积。
 在非人工智能的图像处理中，用作图像模糊、锐化、边缘检测。
 统计学中，加权的滑动平均是一种卷积。
 概率论中，两个统计独立变量X与Y的和的概率密度函数是X与Y的概率密度函数的卷积。
 声学中，回声可以用源声与一个反映各种反射效应的函数的卷积表示。
 电子工程与信号处理中，任一个线性系统的输出都可以通过将输入信号与系统函数（系统的冲激响应）做卷积获得。
 物理学中，任何一个线性系统（符合叠加原理）都存在卷积。

 参见 
 反卷积
 自相关函数
 傅里叶变换

引用

延伸阅读
 .


 Dominguez-Torres, Alejandro (Nov 2, 2010). "Origin and history of convolution". 41 pgs. http://www.slideshare.net/Alexdfar/origin-adn-history-of-convolution . Cranfield, Bedford MK43 OAL, UK. Retrieved Mar 13, 2013.


 .
 .
 .
 .
 .


 .

 .
 .
 .
 .


 .

 外部链接 

 Earliest Uses: The entry on Convolution has some historical information. 
 Convolution, on The Data Analysis BriefBook
 http://www.jhu.edu/~signals/convolve/index.html  Visual convolution Java Applet
 http://www.jhu.edu/~signals/discreteconv2/index.html  Visual convolution Java Applet for discrete-time functions
 https://get-the-solution.net/projects/discret-convolution discret-convolution online calculator
https://lpsa.swarthmore.edu/Convolution/CI.html  Convolution demo and visualization in javascript
https://phiresky.github.io/convolution-demo/  Another convolution demo in javascript
 Lectures on Image Processing: A collection of 18 lectures in pdf format from Vanderbilt University. Lecture 7 is on 2-D convolution., by Alan Peters
 * https://archive.org/details/Lectures_on_Image_Processing
 Convolution Kernel Mask Operation Interactive tutorial 
 Convolution  at MathWorld
 Freeverb3 Impulse Response Processor : Opensource zero latency impulse response processor with VST plugins
 Stanford University CS 178 interactive Flash demo   showing how spatial convolution works.
 A video lecture on the subject of convolution  given by Salman Khan
 Example of FFT convolution for pattern-recognition (image processing) 
Intuitive Guide to Convolution  A blogpost about an intuitive interpretation of convolution.

J
J
J
Category:双线性算子
Category:特征检测_(计算机视觉)