卷积

本页使用了标题或全文手工转换
维基百科,自由的百科全书
卷积、互相关自相关的图示比较。运算涉及函数,并假定的高度是1.0,在5个不同点上的值,用在每个点下面的阴影面积来指示。的对称性是卷积和互相关在这个例子中相同的原因。

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

定义

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

仍为可积函数,并且有着:

函数,如果只支撑之上,则积分界限可以截断为:

对于

对于两个得出复数值的多元实变函数英语Function of several real variables,可以定义二者的卷积为如下形式的多重积分

卷积有一个通用的工程上的符号约定[1]

它必须被谨慎解释以避免混淆。例如:等价于,而却实际上等价于[2]

历史

卷积运算的最早使用出现在达朗贝尔于1754年出版的《宇宙体系的几个要点研究》中对泰勒定理的推导之中[3]。还有西尔维斯特·拉克鲁瓦英语Sylvestre François Lacroix,将类型的表达式,用在他的1797年–1800年出版的著作《微分与级数论文》中[4]。此后不久,卷积运算出现在皮埃尔-西蒙·拉普拉斯约瑟夫·傅里叶西梅翁·泊松等人的著作中。这个运算以前有时叫做“Faltung”(德语中的折叠)、合成乘积、叠加积分或卡森积分[5]

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

简介

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

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

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

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

函数互相关,等价于共轭复数的卷积:

这里的叫做移位(displacement)或滞后(lag)。

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

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

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

图解

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

周期卷积

两个周期的函数的“周期卷积”定义为[10][11]

这里的是任意参数。

任何可积分函数英语Absolutely integrable function,都可以通过求函数的所有整数倍平移总和,从而制作出具有周期周期函数 ,这叫做周期求和英语Periodic summation

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

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

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

离散卷积

离散卷积示意图

对于定义在整數上且得出复数值的函数,离散卷积定义为[13]

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

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

多维离散卷积

用离散二维卷积对图像进行锐化英语Kernel (image processing)处理的动画

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

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

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

在两个二维信号之间的卷积的可视化

离散周期卷积

对比离散无周期卷积(左列)与离散圆周卷积(右列)

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

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

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

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

性质

代数

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

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

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

复数共轭
微分有关
积分有关
如果,并且,则有:

积分

如果是可积分函数,则它们在整个空间上的卷积的积分,简单的就是它们积分的乘积[14]

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

微分

在一元函数情况下,的卷积的导数有着:

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

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

这些恒等式成立的严格条件,为是绝对可积分的,并且至少二者之一有绝对可积分()弱导数,这是Young卷积不等式英语Young's convolution inequality的结论。

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

卷积定理

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

设两个函数,分别具有傅里叶变换

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

卷积定理声称:

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

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

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

周期卷积

对于周期为的函数,可以被表达为二者的周期求和英语Periodic summation

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

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

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

周期卷积的周期也是,周期卷积的卷积定理为:

离散卷积

对于作为两个连续函数采样序列,它们具有离散时间傅里叶变换

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

离散卷积的卷积定理为:

离散周期卷积

对于周期为序列

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

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

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

它有着推论:

对于其非零时段小于等于,离散圆周卷积的卷积定理为:

推广

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

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

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

离散卷積的計算方法

計算卷積有三種主要的方法,分別為

  1. 直接計算(Direct Method)
  2. 快速傅立葉轉換(FFT)
  3. 分段卷積(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類,並列出適合使用的方法:

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

应用

高斯模糊可被用来从半色调印刷品复原出光滑灰度数字图像。

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

参见

引用

  1. ^ Smith, Stephen W. 13.Convolution. The Scientist and Engineer's Guide to Digital Signal Processing 1. California Technical Publishing. 1997 [22 April 2016]. ISBN 0-9660176-3-3. (原始内容存档于2023-06-26). 
  2. ^ Irwin, J. David. 4.3. The Industrial Electronics Handbook 1. Boca Raton, FL: CRC Press. 1997: 75. ISBN 0-8493-8343-9. 
  3. ^ Dominguez-Torres, p 2
  4. ^ 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
  5. ^ R. N. Bracewell, Early work on imaging theory in radio astronomy, W. T. Sullivan (编), The Early Years of Radio Astronomy: Reflections Fifty Years After Jansky's Discovery, Cambridge University Press: 172, 2005, ISBN 978-0-521-61602-7 
  6. ^ John Hilton Grace and Alfred Young, The algebra of invariants, Cambridge University Press: 40, 1903 
  7. ^ Leonard Eugene Dickson, Algebraic invariants, J. Wiley: 85, 1914 
  8. ^ Stein & Weiss 1971,Theorem 1.3)
  9. ^ Crutchfield, Steve, The Joy of Convolution, Johns Hopkins University, October 12, 2010 [November 21, 2010], (原始内容存档于2013-09-11) 
  10. ^ Jeruchim, Michel C.; Balaban, Philip; Shanmugan, K. Sam. Simulation of Communication Systems: Modeling, Methodology and Techniques 2nd. New York: Kluwer Academic Publishers. October 2000: 73–74. ISBN 0-30-646267-2. 
  11. ^ 11.0 11.1 Udayashankara, V. Real Time Digital Signal Processing. India: Prentice-Hall. June 2010: 189. ISBN 978-8-12-034049-7. 
  12. ^ Priemer, Roland. Introductory Signal Processing. Advanced Series in Electrical and Computer Engineering 6. Teaneck,N.J.: World Scientific Pub Co Inc. July 1991: 286–289 [2023-10-26]. ISBN 9971-50-919-9. (原始内容存档于2023-10-11). 
  13. ^ Damelin & Miller 2011,第219頁
  14. ^ Weisstein, Eric W. Convolution. mathworld.wolfram.com. [2021-09-22]. (原始内容存档于2002-01-14) (英语). 
  15. ^ Weisstein, Eric W. From MathWorld--A Wolfram Web Resource. [2023-10-23]. (原始内容存档于2000-07-11). 
  16. ^ Zhang, Yingjie; Soon, Hong Geok; Ye, Dongsen; Fuh, Jerry Ying Hsi; Zhu, Kunpeng. Powder-Bed Fusion Process Monitoring by Machine Vision With Hybrid Convolutional Neural Networks. IEEE Transactions on Industrial Informatics. September 2020, 16 (9): 5769–5779 [2023-10-24]. ISSN 1941-0050. S2CID 213010088. doi:10.1109/TII.2019.2956078. (原始内容存档于2023-07-31). 
  17. ^ Chervyakov, N.I.; Lyakhov, P.A.; Deryabin, M.A.; Nagornov, N.N.; Valueva, M.V.; Valuev, G.V. Residue Number System-Based Solution for Reducing the Hardware Cost of a Convolutional Neural Network. Neurocomputing. September 2020, 407: 439–453 [2023-10-24]. S2CID 219470398. doi:10.1016/j.neucom.2020.04.018. (原始内容存档于2023-06-29) (英语). Convolutional neural networks represent deep learning architectures that are currently used in a wide range of applications, including computer vision, speech recognition, time series analysis in finance, and many others. 
  18. ^ Atlas, Homma, and Marks. An Artificial Neural Network for Spatio-Temporal Bipolar Patterns: Application to Phoneme Classification (PDF). Neural Information Processing Systems (NIPS 1987). (原始内容存档 (PDF)于2021-04-14). 

延伸阅读

外部链接