信號(hào)處理中的一個(gè)重要運(yùn)算是卷積.初學(xué)卷積的時(shí)候,往往是在連續(xù)的情形,

兩個(gè)函數(shù)f(x),g(x)的卷積,是∫f(u)g(x-u)du
當(dāng)然，證明卷積的一些性質(zhì)并不困難，比如交換，結(jié)合等等，但是對(duì)于卷積運(yùn)算的來(lái)處，初學(xué)者就不甚了了。

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

卷積的一個(gè)典型例子,其實(shí)就是初中就學(xué)過的多項(xiàng)式相乘的運(yùn)算,
比如(x*x+3*x+2)(2*x+5)
一般計(jì)算順序是這樣,
(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
然后合并同類項(xiàng)的系數(shù),
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

實(shí)際上,從線性代數(shù)可以知道,多項(xiàng)式構(gòu)成一個(gè)向量空間,其基底可選為
{1,x,x*x,x*x*x,...}
如此,則任何多項(xiàng)式均可與無(wú)窮維空間中的一個(gè)坐標(biāo)向量相對(duì)應(yīng),
如,(x*x+3*x+2)對(duì)應(yīng)于
(1 3 2),
(2*x+5)對(duì)應(yīng)于
(2,5).

線性空間中沒有定義兩個(gè)向量間的卷積運(yùn)算,而只有加法,數(shù)乘兩種運(yùn)算,而實(shí)際上,多項(xiàng)式的乘法,就無(wú)法在線性空間中說明.可見線性空間的理論多么局限了.
但如果按照我們上面對(duì)向量卷積的定義來(lái)處理坐標(biāo)向量,
(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)

回到多項(xiàng)式的表示上來(lái),
(x*x+3*x+2)(2*x+5)= 2*x*x*x+11*x*x+19*x+10

似乎很神奇,結(jié)果跟我們用傳統(tǒng)辦法得到的是完全一樣的.
換句話,多項(xiàng)式相乘,相當(dāng)于系數(shù)向量的卷積.

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

[ 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]'

采用行的觀點(diǎn)看Ax,則b的每行都是一個(gè)內(nèi)積。
A的每一行都是序列[2 3 1]的一個(gè)移動(dòng)位置。

---------

顯然,在這個(gè)特定的背景下,我們知道,卷積滿足交換,結(jié)合等定律,因?yàn)?眾所周知的,多項(xiàng)式的乘法滿足交換律,結(jié)合律.在一般情形下,其實(shí)也成立.

在這里,我們發(fā)現(xiàn)多項(xiàng)式,除了構(gòu)成特定的線性空間外,基與基之間還存在某種特殊的聯(lián)系,正是這種聯(lián)系,給予多項(xiàng)式空間以特殊的性質(zhì).

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

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

另外，回想信號(hào)處理里面的一條基本定理,頻率域的乘積,相當(dāng)于時(shí)域或空域信號(hào)的卷積.恰好跟這里的情形完全對(duì)等.這后面存在什么樣的隱態(tài)聯(lián)系,需要繼續(xù)參詳.

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

其實(shí)這道理一點(diǎn)也不復(fù)雜，人類繁衍了多少萬(wàn)年了，但過去n多年，人們只知道男女媾精，乃能繁衍后代。精子，卵子的發(fā)現(xiàn)，生殖機(jī)制的研究，也就是最近多少年的事情。

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

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

從上文我們得知了卷積的來(lái)源。我們?cè)僬乙幌戮矸e的官方定義：數(shù)學(xué)中關(guān)于兩個(gè)函數(shù)的一種無(wú)窮積分運(yùn)算。對(duì)于函數(shù)f1(t)和f2(t)，其卷積表示為：式中：“*”為卷積運(yùn)算符號(hào)。

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

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

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

其實(shí)，說了這么多，我還是不太明白為什么要對(duì)圖像進(jìn)行卷積，怎樣進(jìn)行卷積。

1.2 卷積運(yùn)算

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

卷積運(yùn)算，其實(shí)就是可看作是加權(quán)求和的過程，使用到的圖像區(qū)域中的每個(gè)像素分別與卷積核(權(quán)矩陣)的每個(gè)元素對(duì)應(yīng)相乘，所有乘積之和作為區(qū)域中心像素的新值。
卷積示例：

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

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

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

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

.常用模板（卷積核）

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

1.3 意義

卷積是各種圖像變換的基礎(chǔ)，一個(gè)特殊卷積所實(shí)現(xiàn)的功能是由其卷積核（模板）的形式?jīng)Q定的。高斯變換就是用高斯函數(shù)對(duì)圖像進(jìn)行卷積。

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

膨脹和腐蝕。

圖像金字塔

拉普拉斯變換、canny算子（求導(dǎo)數(shù)）

卷積性質(zhì)：

1.卷積的符號(hào)表示式表明卷積是一種特殊類型的乘法，乘法某些代數(shù)性質(zhì)可用于卷積。

(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)
此性質(zhì)表明無(wú)論哪個(gè)函數(shù)平移了一個(gè)距離t0,則所得的卷積就是簡(jiǎn)單平移了同一距離，但大小和形狀保持不變。

3.奇異信號(hào)的卷積特性：

(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)

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

2 積分圖像

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

積分圖像中任意一點(diǎn)（i,j）的值為ii(i,j)為原圖像左上角到任意點(diǎn)（i,j）相應(yīng)的對(duì)角線區(qū)域灰度值的總和即：

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

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

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內(nèi)的像元灰度和時(shí)，不管窗口W的大小如何，均可利用積分圖像的4個(gè)對(duì)應(yīng)點(diǎn)（i1,j1）（i2,j2）（i3,j3）（i4,j4）的值計(jì)算的到。也就是說，求取窗口W內(nèi)的像元灰度和與窗口的尺寸是無(wú)關(guān)的。窗口W內(nèi)的像元的灰度和為

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

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

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

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

這樣就可以進(jìn)行2種運(yùn)算：

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

ii1=Sum（A）

同理，點(diǎn)2、點(diǎn)3、點(diǎn)4的積分圖像分別為：

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

矩形區(qū)域D內(nèi)的所有像素灰度積分可由矩形端點(diǎn)的積分圖像值得到:

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

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

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

Sum（A）-Sum（B）

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

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

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

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

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

由此可見，矩形特征特征值計(jì)算只與此特征端點(diǎn)的積分圖有關(guān)，而與圖像坐標(biāo)值無(wú)關(guān)。對(duì)于同一類型的矩形特征，不管特征的尺度和位置如何，特征值的計(jì)算所耗費(fèi)的時(shí)間都是常量，而且都只是簡(jiǎn)單的加減運(yùn)算。其它類型的特征值計(jì)算方法類似。