【正文】 對于N=4， W陣為 由W的周期性得：W4＝W0，W6＝W2，W9＝W1；再由W的對稱性可得： W3＝－W1，W2＝－W0。這樣，可將式一維離散傅立葉變換（DFT）用矩陣的形式表示： 式中，由Wux構(gòu)成的矩陣稱為W陣或系數(shù)矩陣 觀察DFT的W陣，并結(jié)合W的定義表達式W=ej2π／N，可以發(fā)現(xiàn)系數(shù)W是以N為周期的。 由于二維離散傅立葉變換具有可分離性， 即它可由兩次一維離散傅立葉變換計算得到，因此，僅研究一維離散傅立葉變換的快速算法即可。采用該FFT算法，其運算次數(shù)正比于NlbN，當N很大時計算量可以大大減少。為此，研究離散傅立葉變換的快速算法（Fast Fourier Transform， FFT）是非常有必要的。 3 快速離散傅立葉變換離散傅立葉變換計算量非常大，運算時間長。（9）相關(guān)定理如果為兩個二維時域函數(shù)，那么可以定義相關(guān)運算“0”如下 則： 其中為函數(shù)f(x,y)的傅立葉變換，為函數(shù)g(x,y)的傅立葉變換；G的共軛。（8） 能量保持定理能量保持定理也稱帕斯維爾定理。2 傅立葉變換的性質(zhì) 傅立葉變換有很多重要的性質(zhì)，這些性質(zhì)為運算處理提供了方便。傅立葉變換也可以推廣到二維情況。如果再令，則上式可寫成： 由上面的公式可以看出，傅立葉變換結(jié)果是一個復數(shù)表達式。1 傅立葉變換的基本概念傅立葉變換在數(shù)學中的定義是非常嚴格的，它的定義如下：設(shè)f(X)為x的函數(shù)，如果f(X)滿足下面的狄里赫萊條件：1） 具有有限個間隔點；2） 具有有限個極點；3） 絕對可積。常用的正交變換有傅立葉變換、余弦變換及沃爾什變換等。一般采用先行正交變換來進行圖像的頻域變換。 case HOUGH: return ConvoluteDIB(hDib, Hough, Strength, 4)。Sobel，Hough邊緣檢測使用的卷積核數(shù)組如附件基于上述卷積核數(shù)組，調(diào)用ConvoluteDIB函數(shù)就能實現(xiàn)Sobel和Hough邊緣檢測。（附件）Sobel邊緣檢測＆Hough邊緣檢測的實現(xiàn)方法完全相同，只是使用不同的卷積核而已。首先應(yīng)定義用于邊緣增強的卷積核。下面給出邊緣增強的實現(xiàn)方法：邊緣增強也是用卷積來實現(xiàn)的一種圖像處理方法。當中心點像素值大于閾值時，輸出像素置白，否則置黑。分別計算出每條直線的兩個子區(qū)域平均值之差的絕對值，并將得到的4個值中最大的賦給中心像素e。其中每一條直線都將區(qū)域劃分為兩部分，每一部分有3個像素，稱之為一個子區(qū)域。下面介紹其中一種。 Laplace邊緣增強使用的卷積核如下：0 1 0 －1 －1 －1 －1 －1 －1 1 －2 1 1 －4 1 －1 8 －1 －1 9 －1 －2 4 －2 0 1 0 －1 －1 －1 －1 －1 －1 1 －2 1LAP1 LAP2 LAP3 LAP4 (4) Sobel邊緣檢測 Sobel邊緣檢測是一種非線性的邊緣檢測算法，效率很高，用途很廣。由于卷積核中所有卷積系數(shù)之和為0，因此，圖像中亮度基本不變的區(qū)域（空域頻率較低的區(qū)域）的結(jié)果像素值將很小，即這些部分經(jīng)處理后將變黑。用于這8個方向的卷積核如下所示：1 1 1 1 1 1 －1 1 1 －1 －1 11 －2 1 －1 －2 1 －1 －2 1 －1 －2 1－1 －1 －1 －1 －1 1 －1 1 1 1 1 1 北 東北 東 東南－1 －1 －1 1 －1 －1 1 1 －1 1 1 1 1 －2 1 1 －2 －1 1 －2 －1 1 －2 1 1 1 1 1 1 1 1 1 －1 －1 －1 －1 南 西南 西 西北如果在卷積核方向上存在著正的像素亮度變化率，則輸出圖像上的像素變亮。（2） 梯度方向邊緣增強梯度方向邊緣增強用于增強8個不同方向的邊緣。3） 當要同時增強水平和垂直方向的邊緣時，使用水平與垂直方向卷積核。2） 當要增強水平方向的邊緣時，使用水平方向卷積核。1） 要增強垂直方向的邊緣時，使用垂直方向卷積核。對于原圖像中像素值保持不變的區(qū)域，相減的結(jié)果為0，即像素為黑；對于圖像中像素變化劇烈的區(qū)域，相減后得到較大的變化率，對應(yīng)的像素很亮，而且像素值差別越大，則得到的像素就越亮。（1） 平移和差分邊緣增強平移和差分邊緣增強可分為垂直邊緣增強、水平邊緣增強和水平與垂直邊緣增強，它們分別使用如下所示的不同卷積核：0 0 0 0 －1 0 －1 0 0 －1 1 0 0 1 0 0 1 00 0 0 0 0 0 0 0 0垂直邊緣 水平邊緣 水平與垂直邊緣該方法的基本原理是首先將圖像平移一個像素，然后用原圖像減去平移后的圖像。常用的邊緣增強方法有平移和差分邊緣檢測增強、梯度方向邊緣增強、Laplace邊緣增強和Sobel邊緣檢測等。用于邊緣增強的卷積核的基本特征是：1） 卷積核的行、列數(shù)為奇數(shù)，通常為3；2） 卷積系數(shù)以中心點為中心反對稱分布；3） 中心的卷積系數(shù)一般為正數(shù)；4） 中心周圍的卷積系數(shù)一般為負數(shù)或0；5） 卷積系數(shù)之和等于0（個別例外）。邊緣增強也可用卷積來實現(xiàn)。處理后邊界的亮度與原圖中邊緣周圍的亮度變化率成正比。在對圖像進行特征提取之前，一般都需要先進行邊緣檢測，然后再進行二值化處理。}4．5 邊緣檢測和增強使圖像的輪廓更加突出的圖像處理方法叫做邊緣檢測或邊緣增強。HP3, Strength)。HP2, Strength)。HP1, Strength)。KERNEL HP3 = { // HP filter 3 { 1, 2, 1, 2, 5, 2, 1, 2, 1}, 1 // Divisor = 1}。首先利用KERNEL結(jié)構(gòu)定義的3個高通濾波器：KERNEL HP1 = { // HP filter 1 {1, 1, 1, 1, 9, 1, 1, 1, 1}, 1 // Divisor = 1}。因此，卷積之后，圖像中像素的突變變得更加突出，即圖像中的像素值的差得到增強；同時，圖像中像素值變化更加醒目，在視覺上，就顯得更加清晰。 －1 －1 －1 0 －1 0 1 －2 1 －1 9 －1 －1 5 －1 －2 5 －2 －1 －1 －1 0 －1 0 1 －2 1HP1 HP2 HP3在高頻濾波器中，卷積核中心的卷積系數(shù)最大，在處理中起著關(guān)鍵的作用。下面的HPHPHP3是3個常用的高通濾波器。高通濾波可通過卷積來實現(xiàn)，這時使用的卷積核叫做高通濾波器。相對于高頻成分來說，低頻成分被削弱了。 } return FALSE。 case FILTER3: return ConvoluteDIB(hDib, amp。 case FILTER2: return ConvoluteDIB(hDib, amp。實現(xiàn)低通濾波的函數(shù)可簡單地調(diào)用ConvoluteDIB來實現(xiàn)：BOOL LowPassDIB(HDIB hDib, int Strength, int nAlgorithm) { switch (nAlgorithm) { case FILTER1: return ConvoluteDIB(hDib, amp。KERNEL LP2 = { // LP filter 2 { 1, 1, 1, 1, 2, 1, 1, 1, 1}, 10 // Divisor = 10}。下面是利用KERNEL結(jié)果定義的3個低通濾波器。1/9 1/9 1/9 1/10 1/10 1/10 1/16 1/8 1/161/9 1/9 1/9 1/10 1/5 1/10 1/8 1/4 1/81/9 1/9 1/9 1/10 1/10 1/10 1/16 1/8 1/16LP1 LP2 LP3由于低頻濾波消弱了圖像的高頻部分，圖像中像素值的突變被平均值所代替，因此低頻濾波使圖像變得平滑，在視覺上變得模糊。如下的LPLPLP3是三個常用的低通濾波器。用于低通濾波的卷積叫做低通濾波器。低通濾波可以降低圖像中的視覺噪聲，同時除去了圖像中的高頻部分后，圖像中那些本來不明顯的低頻成分就更容易識別了。完成卷積后，再次調(diào)用ConvertDIBFormat函數(shù)將DIB恢復為wBitCount位格式。函數(shù)ConvoluteDIB實現(xiàn)了33卷積核對DIB的卷積操作，能同時支持“標準”卷積或“擴展”卷積?！皹藴省本矸e之外，有的算法涉及一個“擴展”的卷積方法，即涉及兩個，甚至更多各卷積核的操作。} KERNEL。KERNEL的定義如下： // Definitions required for convolution image filteringdefine KERNELCOLS 3define KERNELROWS 3define KERNELELEMENTS (KERNELCOLS * KERNELROWS)// struct for convolute kernel typedef struct { int Element[KERNELELEMENTS]。先對卷積核中各卷積系數(shù)乘以它們的最小公倍數(shù)，得到一個所有的卷積系數(shù)都為整數(shù)的新卷積核進行操作，然后將結(jié)果除以原卷積核各卷積系數(shù)的最小公倍數(shù)，就可以求得真正的卷積結(jié)果，而且運算效率有很大的提高。3） 由于有的卷積核中的卷積系數(shù)是浮點數(shù)，如果直接用它們進行運算，則運算量很大，速度很慢。因此，為了簡化操作，可以先將DIB格式轉(zhuǎn)化為24位。所以，應(yīng)分別用同一卷積核對各像素的R,G,B顏色分量分別卷積，并將3個分量的卷積結(jié)果作為像素新RGB值的3個分量。對DIB進行圖像處理的基礎(chǔ)是實現(xiàn)DIB的卷積操作。負的像素值沒有意義，也不能顯示，必須進行適當?shù)奶幚?。卷積運算的第三個復雜問題是卷積結(jié)果像素值的符號問題。但也有一些卷積核卷積的結(jié)果超出了像素的有效范圍。卷積運算的第二個復雜問題是計算得到的中心像素的動態(tài)范圍問題。這時在原圖像上就不能完整找到與卷積核中的卷積系數(shù)想對應(yīng)的9個（對33的卷積核）圖像像素。進行卷積時會遇到一些較復雜的問題，首先時圖像邊界的問題。卷積核中卷積系數(shù)的大小、方向及排列次序決定了卷積的圖像處理效果。這種權(quán)矩陣叫做卷積核，區(qū)域中的每個像素分別與卷積核中的每個元素相乘，所有乘積之和即為區(qū)域中心像素的新值。 卷積法卷積可以簡單地看成加權(quán)求和的過程。例如，若有序數(shù)為a,b,c,則它的中值可寫成：Median(a,b,c)=Max[min(a,b),min(b,c),min(a,c)]或 Median(a,b,c)=Min[max(a,b),max(b,c),max(a,c)]因為區(qū)域中像素值發(fā)生隨即突變的像素，經(jīng)排序后將位于隊伍的隊首或者隊尾，因此取得的中位像素值是正常的像素值。 等提出對圖像用一個NN的滑動窗口進行中值濾波時，每次求中值只要考慮去掉最左列的，補上最右列的像素，其余的像素不變，因此可大大縮小計算量，特別是當N較大時更顯示出其優(yōu)越性。例如，Narendra提出對圖像先做行方向的一維中值濾波，再做列方向的一維中值濾波方法。 窗口的形狀可為方形、十字形等，如圖所示?，F(xiàn)在用中值5代替。5大于0、3而等于5，其中包括3個5；同時5小于63這4個元素。具體做法與一維情況類似。一般情況下，序列為N的一維窗口的中值為： median(x)=m如果N為偶數(shù)，則取兩個中間數(shù)的平均值作為中值。將m=110放在這5個數(shù)中間，對序列重新