信號處理中的一個重要運算是卷積.初學卷積的時候,往往是在連續的情形,

兩個函數f(x),g(x)的卷積,是∫f(u)g(x-u)du
當然，證明卷積的一些性質并不困難，比如交換，結合等等，但是對于卷積運算的來處，初學者就不甚了了。

其實，從離散的情形看卷積，或許更加清楚，
對于兩個序列f[n],g[n],一般可以將其卷積定義為s[x]= ∑f[k]g[x-k]

卷積的一個典型例子,其實就是初中就學過的多項式相乘的運算,
比如(x*x+3*x+2)(2*x+5)
一般計算順序是這樣,
(x*x+3*x+2)(2*x+5)
= (x*x+3*x+2)*2*x+(x*x+3*x+2)*5
= 2*x*x*x+3*2*x*x+2*2*x+ 5*x*x+3*5*x+10
然后合并同類項的系數,
2 x*x*x
3*2+1*5 x*x
2*2+3*5 x
2*5
----------
2*x*x*x+11*x*x+19*x+10

實際上,從線性代數可以知道,多項式構成一個向量空間,其基底可選為
{1,x,x*x,x*x*x,...}
如此,則任何多項式均可與無窮維空間中的一個坐標向量相對應,
如,(x*x+3*x+2)對應于
(1 3 2),
(2*x+5)對應于
(2,5).

線性空間中沒有定義兩個向量間的卷積運算,而只有加法,數乘兩種運算,而實際上,多項式的乘法,就無法在線性空間中說明.可見線性空間的理論多么局限了.
但如果按照我們上面對向量卷積的定義來處理坐標向量,
(1 3 2)*(2 5)
則有
2 3 1
_ _ 2 5
--------
2


2 3 1
_ 2 5
-----
6+5=11

2 3 1
2 5
-----
4+15 =19


_ 2 3 1
2 5
-------
10

或者說,
(1 3 2)*(2 5)=(2 11 19 10)

回到多項式的表示上來,
(x*x+3*x+2)(2*x+5)= 2*x*x*x+11*x*x+19*x+10

似乎很神奇,結果跟我們用傳統辦法得到的是完全一樣的.
換句話,多項式相乘,相當于系數向量的卷積.

其實,琢磨一下,道理也很簡單,
卷積運算實際上是分別求 x*x*x ,x*x,x,1的系數，也就是說，他把加法和求和雜合在一起做了。(傳統的辦法是先做乘法，然后在合并同類項的時候才作加法)
以x*x的系數為例，得到x*x，或者是用x*x乘5，或者是用3x乘2x,也就是
2 3 1
_ 2 5
-----
6+5=11
其實,這正是向量的內積.如此則,卷積運算,可以看作是一串內積運算.既然是一串內積運算，則我們可以試圖用矩陣表示上述過程。

[ 2 3 1 0 0 0]
[ 0 2 3 1 0 0]==A
[ 0 0 2 3 1 0]
[ 0 0 0 2 3 1]

[0 0 2 5 0 0]' == x

b= Ax=[ 2 11 19 10]'

采用行的觀點看Ax,則b的每行都是一個內積。
A的每一行都是序列[2 3 1]的一個移動位置。

---------

顯然,在這個特定的背景下,我們知道,卷積滿足交換,結合等定律,因為,眾所周知的,多項式的乘法滿足交換律,結合律.在一般情形下,其實也成立.

在這里,我們發現多項式,除了構成特定的線性空間外,基與基之間還存在某種特殊的聯系,正是這種聯系,給予多項式空間以特殊的性質.

在學向量的時候，一般都會舉這個例子，甲有三個蘋果，5個橘子，乙有5個蘋果，三個橘子，則共有幾個蘋果，橘子。老師反復告誡，橘子就是橘子，蘋果就是蘋果，可不能混在一起。所以有(3,5)+(5,3)=(8,8).是的，橘子和蘋果無論怎么加，都不會出什么問題的，但是，如果考慮橘子乘橘子，或者橘子乘蘋果，這問題就不大容易說清了。

又如復數,如果僅僅定義復數為數對（a,b),僅僅在線性空間的層面看待C2,那就未免太簡單了。實際上，只要加上一條(a,b)*(c,d)=(ac-bd,ad+bc)
則情況馬上改觀，復變函數的內容多么豐富多彩，是眾所周知的。

另外，回想信號處理里面的一條基本定理,頻率域的乘積,相當于時域或空域信號的卷積.恰好跟這里的情形完全對等.這后面存在什么樣的隱態聯系,需要繼續參詳.

從這里看,高等的卷積運算其實不過是一種初等的運算的抽象而已.中學學過的數學里面，其實還蘊涵著許多高深的內容（比如交換代數）。溫故而知新,斯言不謬.

其實這道理一點也不復雜，人類繁衍了多少萬年了，但過去n多年，人們只知道男女媾精，乃能繁衍后代。精子，卵子的發現，生殖機制的研究，也就是最近多少年的事情。

孔子說，道在人倫日用中，看來我們應該多用審視的眼光看待周圍，乃至自身，才能知其然，而知其所以然。

---------------------------------------------------------------------------------------------------------------

從上文我們得知了卷積的來源。我們再找一下卷積的官方定義：數學中關于兩個函數的一種無窮積分運算。對于函數f1(t)和f2(t)，其卷積表示為：式中：“*”為卷積運算符號。

在泛函分析中，卷積(卷積)、旋積或摺積(英語：Convolution)是通過兩個函數f 和g 生成第三個函數的一種數學算子，表徵函數f 與經過翻轉和平移與g 的重疊部分的累積。函數f與g的卷積記作f(t)*g(t)，它是其中一個函數翻轉并平移后與另一個函數的乘積的積分，是一個對平移量的函數。

函數f與g的卷積可以定義為： z(t)=f(t)*g(t)= ∫f(m)g(t-m)dm.

并且卷積定理指出：二個二維連續函數在空間域中的卷積可求其相應的二個傅立葉變換乘積的反變換而得。反之，在頻域中的卷積可用的在空間域中乘積的傅立葉變換而得。

其實，說了這么多，我還是不太明白為什么要對圖像進行卷積，怎樣進行卷積。

1.2 卷積運算

提到卷積運算，首先離不開的就是卷積核，這個卷積核其實就是一個大小固定、由數值參數構成的數組，數組的參考點通常位于數組的中心，數組的大小稱為核支撐。單就技術而言，核支撐實際上僅僅由核數組的非0部分組成。或者，像其他說法，卷積核就是所謂的模板。

卷積運算，其實就是可看作是加權求和的過程，使用到的圖像區域中的每個像素分別與卷積核(權矩陣)的每個元素對應相乘，所有乘積之和作為區域中心像素的新值。
卷積示例：

3 * 3 的像素區域R與卷積核G的卷積運算：
R5(中心像素)=R1G1 + R2G2 + R3G3 + R4G4 + R5G5 + R6G6 + R7G7 + R8G8 + R9G9

如果對一幅圖像進行卷積運算，可利用以數組為中心為參考點的3*3卷積核。首先將核的參考點定位于圖像的第一個像素點，核的其余元素覆蓋圖像總其對應的局部像素點。對于每一個核點，我們可以得到這個點的值以及圖像中對應圖像點的值。將這些值相乘并求和，并將這個結果放在與輸入圖像參考點所對應的位置。通過在整個圖像上掃描卷積核，對圖像的每個點重復此操作。最終可以得到圖像的卷積圖像。

當然，我們可以利用方程表示這個過程，定義圖像為I(x,y),核為G（i,y）(其中0) 參考點位于（ai,aj）坐標上，則卷積H(x,y)定義如下：

H(x,y) = sum[ I(x+i-ai,y+j-aj)G(i,j)].

.常用模板（卷積核）

連續空間的卷積定義是 f(x)與g(x)的卷積是 f(t-x)g(x) 在t從負無窮到正無窮的積分值.t-x要在f(x)定義域內,所以看上去很大的積分實際上還是在一定范圍的.
實際的過程就是f(x) 先做一個Y軸的反轉,然后再沿X軸平移t就是f(t-x),然后再把g(x)拿來,兩者乘積的值再積分.想象一下如果g(x)或者f(x)是個單位的階越函數. 那么就是f(t-x)與g(x)相交部分的面積.這就是卷積了.
把積分符號換成求和就是離散空間的卷積定義了.

1.3 意義

卷積是各種圖像變換的基礎，一個特殊卷積所實現的功能是由其卷積核（模板）的形式決定的。高斯變換就是用高斯函數對圖像進行卷積。

平滑處理：平滑類型：簡單模糊（對鄰域求和，并縮放），簡單無縮放變換的模糊（對鄰域求和），中值模糊（中值濾波），高斯模糊（高斯卷積），雙邊模糊（雙線性濾波）。

膨脹和腐蝕。

圖像金字塔

拉普拉斯變換、canny算子（求導數）

卷積性質：

1.卷積的符號表示式表明卷積是一種特殊類型的乘法，乘法某些代數性質可用于卷積。

(1)commutative law：f1(t)*f2(t)=f2(t)*f1(t)
(2)distributive law：f1(t)*[f2(t)+f3(t)]=f1(t)*f2(t)+f1(t)*f3(t)
(3)associative law：[f1(t)*f2(t)]*f3(t)=f1(t)*[f2(t)*f3(t)]
(4)shift invariace：若f1(t)*f2(t)=f3(t)，則f1(t-t0)*f2(t)=f1(t)*f2(t-t0)=f3(t-t0)
此性質表明無論哪個函數平移了一個距離t0,則所得的卷積就是簡單平移了同一距離，但大小和形狀保持不變。

3.奇異信號的卷積特性：

(1)f(t)*δ(t)=f(t) f(t)*δ(t-t0)=f(t-t0) f(t-t1)*δ(t-t0)=f(t-t0-t1)
(2)δ(t)*δ(t)=δ(t)
(3)f(t)*δ'(t)=f'(t)
(4)
推廣：f(t)*δ(k)(t)=f(k)(t) f(t)*δ(k)(t-t0)=f(k)(t-t0)
(5)f(t)*δ'(t)*u(t)=f'(t)*u(t)=f(t) f(t)*δ''(t)*tu(t)=f''(t)*tu(t)=f(t)

所以，圖像卷積與積分圖像有什么關系嗎？知者告知我啊。。。。。。

2 積分圖像

surf算法中要用到積分圖像的概念。借助積分圖像，圖像與高斯二階微分模板的濾波轉化為對積分圖像的加減運算。積分圖像（Integral Image）的概念是由viola和Jones提出來的，而將類似積分圖像用于盒子濾波是由Simard等人提出。

積分圖像中任意一點（i,j）的值為ii(i,j)為原圖像左上角到任意點（i,j）相應的對角線區域灰度值的總和即：

公式中，I(x`,y`)表示原圖像中點（i`,j`）的灰度值，ii（x,y）可以由下面兩公式迭代計算得到：

公式中，S（x,y）表示一列的積分，且S（i,-1）=0,ii(-1,j)=0.求積分圖像，只需對原圖像的所有像素素進行一遍掃描。下面的代碼為c++語言的實現

pOutImage[0][0] = pInImage[0][0];

for(int x = 1, x < nWidth; i++)
{
pOutImage[x][0] = pInImage[x-1][0] + pInImage[x][0];

}

for(int y=1; y< nHeight ;y++)
{
int nSum = 0;

for(int x=0; x < nWidth;x++)
{
nSum = pInImage[x][y];

pOutImage[x][y]= pInImage[x][y-1]+nSum;
}

}

如圖表示，在求取窗口w內的像元灰度和時，不管窗口W的大小如何，均可利用積分圖像的4個對應點（i1,j1）（i2,j2）（i3,j3）（i4,j4）的值計算的到。也就是說，求取窗口W內的像元灰度和與窗口的尺寸是無關的。窗口W內的像元的灰度和為

Sum（W）= ii(i4,j4) -ii(i2,j2) - ii(i3,j3) + ii(i1,j1)

下面看以截圖，相信都可以看懂

關于矩形區域內像素點的求和應該是一種簡單重復性運算，采用這種思路總體上提高了效率。為什么這么說呢？假設一幅圖片共有n個像素點，則計算n個位置的積分圖總共的加法運算有n-1次（注意：可不是次哦，要充分利用遞推思想），將這些結果保存在一個跟原圖對應的矩陣M中。當需要計算圖像中某個矩形區域內的所有像素之和是直接像查表一樣，調出A,B,C,D四點的積分圖值，簡單的加減法（注意只需要三次哦）即可得到結果。反之，如果采用naive的方式直接在原圖像中的某個矩形區域內求和，你想想，總共可能的矩形組合有多少？ ！！且對于一幅圖像n那是相當大啊，所以2^n

那可是天文數字，而且這里面絕大部分的矩形有重疊，重疊意味著什么？在算求和的時候有重復性的工作，其實我們是可以有效的利用已經計算過的信息的。這就是積分圖法的內在思想：它實際上是先計算n個互不重疊（專業點說是不相交）的矩形區域內的像素點求和，充分利用這些值（已有值）計算未知值，有點類似遞推的味道...這就完全避免了重復求和運算。

這樣就可以進行2種運算：

（1）任意矩形區域內像素積分。由圖像的積分圖可方便快速地計算圖像中任意矩形內所有像素灰度積分。如下圖2.3所示，點1的積分圖像ii1的值為(其中Sum為求和) :

ii1=Sum（A）

同理，點2、點3、點4的積分圖像分別為：

ii2=Sum(A)+Sum(B); ii3=Sum(A)+Sum(C); ii4=Sum(A)+Sum(B)+Sum(C)+Sum(D);

矩形區域D內的所有像素灰度積分可由矩形端點的積分圖像值得到:

Sum(D)=ii1+ii4-(ii2+ii3) (1)

(2) 特征值計算
矩形特征的特征值是兩個不同的矩形區域像素和之差，由(1)式可以計算任意矩形特征的特征值，下面以圖2.1中特征原型A為例說明特征值的計算。

如圖2.4 所示，該特征原型的特征值定義為:

Sum（A）-Sum（B）

根據（1）式則有：Sum(A)=ii4+ii1-(ii2+ii3); Sum(B)=ii6+ii3-(ii4+ii5);

所以此類特征原型的特征值為:

(ii4-ii3)-(ii2-ii1)+(ii4-ii3)-(ii6-ii5)

另示：運用積分圖可以快速計算給定的矩形之所有象素值之和Sum(r)。假設r=(x,y,w,h),那么此矩形內部所有元素之和等價于下面積分圖中下面這個式子:

Sum(r) = ii(x+w,y+h)+ii(x-1,y-1)-ii(x+w,y-1)-ii(x-1,y+h)

由此可見，矩形特征特征值計算只與此特征端點的積分圖有關，而與圖像坐標值無關。對于同一類型的矩形特征，不管特征的尺度和位置如何，特征值的計算所耗費的時間都是常量，而且都只是簡單的加減運算。其它類型的特征值計算方法類似。