跳至內容

卷積

本頁使用了標題或全文手工轉換
維基百科,自由的百科全書
卷積、互相關自相關的圖示比較。運算涉及函數,並假定的高度是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). 

延伸閱讀

外部連結