摘? 要： 通過對傳統(tǒng)Canny邊緣檢測" title="邊緣檢測">邊緣檢測算法的分析提出了相應(yīng)的改進(jìn)方法。通過模板代替卷積、適當(dāng)?shù)慕谱儞Q、充分利用并行處理單元等使其能夠用FPGA實現(xiàn)。
關(guān)鍵詞： Canny算子；高斯" title="高斯">高斯濾波；非極大值抑制" title="非極大值抑制">非極大值抑制；雙閾值；FPGA?
?
??? Canny邊緣檢測算法" title="邊緣檢測算法">邊緣檢測算法具有良好的信噪比和檢測精度，因此在圖像處理領(lǐng)域被廣泛采用。但由于其計算量巨大，實時性較差，而且軟件處理的設(shè)備體積較大，所以不適合實時檢測。本文對原始Canny算法進(jìn)行了分析、改進(jìn)，并在FPGA中實現(xiàn)。實驗證明新算法能滿足實時性要求，而且檢測精度和抗噪能力也較理想。
1 Canny邊緣檢測算法的基本原理
1.1 平滑圖像
Canny邊緣檢測算法是高斯函數(shù)的一階導(dǎo)數(shù)，是對信噪比與定位精度之乘積的最優(yōu)化逼近算子。Canny算法首先用二維高斯函數(shù)的一階導(dǎo)數(shù)對圖像進(jìn)行平滑[1]。設(shè)二維高斯函數(shù)為：
其梯度矢量為：
用分解的方法提高速度，把ΔG的2個濾波卷積模板分解為2個一維的行列濾波器：
其中，k為常數(shù)，σ為高斯濾波器參數(shù)，它控制著平滑程度。對于σ小的濾波器，雖然定位精度高，但信噪比低；σ大的情況則相反。因此要根據(jù)需要適當(dāng)?shù)剡x取高斯濾波器參數(shù)σ。
1.2 計算梯度的幅值和方向
傳統(tǒng)Canny算法采用2×2鄰域一階偏導(dǎo)的有限差分來計算平滑后的數(shù)據(jù)陣列I(x，y)的梯度幅值和梯度方向。其中，x和y方向偏導(dǎo)數(shù)的2個陣列Px[i，j]和Py[i，j]分別為：
像素的梯度幅值和梯度方向用直角坐標(biāo)到極坐標(biāo)的坐標(biāo)轉(zhuǎn)化公式計算，用二階范數(shù)來計算梯度幅值為：
梯度方向為：
??? 
1.3 對梯度幅值進(jìn)行非極大值抑制
為了精確定位邊緣，必須細(xì)化梯度幅值圖像M[i，j]中的屋脊帶，只保留幅值局部變化最大的點，這一過程就是非極大值抑制。在非極大值抑制過程中，Canny算法使用3×3大小，包含8方向的鄰域?qū)μ荻确店嚵蠱[i，j]的所有像素沿梯度方向進(jìn)行梯度幅值的插值。在每一個點上，鄰域的中心像素m[i，j]與沿梯度方向的2個梯度幅值的插值結(jié)果進(jìn)行比較。ζ[i，j]是像素鄰域中心處沿著梯度方向的扇形區(qū)域，非極大值抑制在此區(qū)域進(jìn)行。如果鄰域中心點的幅值m[i，j]不比梯度方向上的2個插值結(jié)果大，則將m[i，j]對應(yīng)的邊緣標(biāo)志位賦值為0，這一過程把M[i，j]寬屋脊帶細(xì)化為一個像素寬，并且保留了屋脊的梯度幅值。非極大值抑制NMS(non-maxima suppression)過程的數(shù)學(xué)表示為：
1.4 檢測和連接邊緣
雙閾值算法是對經(jīng)過非極大值抑制圖像N[i，j]分別使用高、低2個閾值th和tl分割，得到2個閾值邊緣圖像Th[i，j]和Tl[i，j]。由于圖像Th[i，j]是由高閾值得到，因此它應(yīng)該不含有假邊緣，但Th[i，j]可能在輪廓上有間斷。因此雙閾值算法要在Th[i，j]中把邊緣連接成輪廓，當(dāng)達(dá)到輪廓端點時，該算法就在由低閾值得到的邊緣圖像Tl[i，j]的8鄰域位置尋找可以連接到輪廓上的邊緣。這樣，利用遞歸跟蹤的算法不斷地在Tl[i，j]中搜集邊緣，直到將Th[i，j]中所有的間隙都連接起來為止。
2 算法的改進(jìn)
傳統(tǒng)Canny算子在2×2的鄰域內(nèi)求有限差分均值來計算梯度幅值的算法[2]，對邊緣的定位比較準(zhǔn)確，但對噪聲過于敏感，容易檢測出假邊緣和丟失一些真實邊緣的細(xì)節(jié)部分。針對傳統(tǒng)Canny算法在梯度幅值計算上的缺陷，提出了一種在像素8鄰域內(nèi)通過計算x方向、y方向、135°方向、45°方向一階偏導(dǎo)數(shù)有限差分來確定像素梯度幅值的方法。這種方法兼顧了梯度幅值計算中，邊緣定位準(zhǔn)確和抑制噪聲的要求，在試驗中取得了很好的效果。具體算法如下：
像素的梯度幅值和梯度方向用直角坐標(biāo)到極坐標(biāo)的坐標(biāo)轉(zhuǎn)化公式來計算，用二階范數(shù)來計算梯度幅值為：
另外，傳統(tǒng)算法中的邊緣連接采取的是遞歸方法，不適合硬件實現(xiàn)" title="硬件實現(xiàn)">硬件實現(xiàn)，因此本文只進(jìn)行了一次連接。其他改進(jìn)具體體現(xiàn)在硬件實現(xiàn)的過程中，如用模板代替卷積， 加減法代替小數(shù)乘除等。
3 改進(jìn)算法及FPGA實現(xiàn)
根據(jù)以上的數(shù)學(xué)推導(dǎo)及分析，得到Canny 邊緣檢測用FPGA實現(xiàn)的流程圖，如圖1所示。
?
?
3.1 高斯濾波
根據(jù)具體情況選擇適當(dāng)?shù)摩遥瑸榱吮阌谟布崿F(xiàn)可以采用模板來代替卷積運算。本文選擇圖2所示的模板，其中的乘除法系數(shù)都是2n的形式，因此可以用移位的方式實現(xiàn)，這避免了乘除法運算帶來的時間與資源的消耗。計算中多次用到中心點的8鄰域的值，因此設(shè)計了窗口形成模塊，以便同時得到某個像素點的8鄰域的值。原理圖如圖3所示。
?
?
行延遲和列延遲分別由FIFO和寄存器完成，其中FIFO的深度等于圖像的列數(shù)。
3.2 梯度計算
經(jīng)過高斯濾波模塊的數(shù)據(jù)再通過窗口形成模塊，得到3×3鄰域，然后按照式15，計算梯度的幅值。
梯度方向計算：根據(jù)8連通區(qū)域，量化邊緣方向。首先將梯度角度的變化范圍減小到圓周的1/8扇區(qū)。如圖4所示，以0°、45°、90°、135°等為中心角度：每個方向包含±22.5°，根據(jù)Px Py的比值及正負(fù)確定其所在方向的區(qū)域范圍，其方向定義為中心角度的方向。對于整個坐標(biāo)系而言，梯度向量共分為8類，但是對于非局部最大值抑制的實現(xiàn)，利用中心對稱原理，只需要4個方向，如圖5所示。
?
?
當(dāng)|Py/Px|>tg22.5°，即梯度方向在0和180兩個扇區(qū)內(nèi)，則將其方向用0表示；
當(dāng)tg22.5°<|Py/Px|>tg67.5°且Px/Py>0，即梯度方向在45°和225°兩個扇區(qū)內(nèi)，則將其方向用1表示；
當(dāng)|Py/Px|>tg67.5°即梯度方向在90°和270°兩個扇區(qū)內(nèi)，則將其方向用2表示；
當(dāng)tg22.5°<|Py/Px|>tg67.5°且Px/Py>0，即梯度135°和315°兩個扇區(qū)內(nèi)，則將其方向用3表示。
tg22.5°≈0.4375=1/2-1/16 ??? tg67.5°≈2.5=2+1/2 ??? 這樣就可以用簡單的移位和加減運算代替復(fù)雜的小數(shù)乘法運算，而在實際的數(shù)字圖像處理中，近似引入的誤差是允許的[3]。再利用比較器和編碼器就可以完成方向判斷。 3.3 閾值計算 閾值選取基于梯度直方圖，所以先統(tǒng)計梯度直方圖[4]。以256×256×8bit的圖為例，基于雙端口RAM(hist_buffer)及其控制器完成。經(jīng)計算存儲器寬度為16bit，深度為1 024。當(dāng)有梯度值輸入時，RAM中相應(yīng)地址的內(nèi)容被讀出來，加1后再存入該地址。如此進(jìn)行下去，直到整幅圖像掃描完畢，得到梯度的直方圖。按照地址從小到大的順序依次累加RAM中的值，當(dāng)累加和不小于圖像總像素的80%時，輸出對應(yīng)的地址，即為Th， 而Tl則由Th右移一位得到，如圖6所示。 ? ? 3.4 非最大值抑制值抑制及邊緣檢測 本文采取將強弱邊緣檢測同時進(jìn)行，并且在邊緣檢測之前形成窗口，這樣就避免了后續(xù)考慮同步的問題，節(jié)省了存儲單元。圖7為原理圖，其中粗線表示同時輸出9個值。 ? ? 4 實驗結(jié)果 圖8依次是原圖、軟件處理結(jié)果圖和硬件處理結(jié)果圖。實驗結(jié)果表明本算法可以得到較準(zhǔn)確的邊緣。 ? ? 本文通過對傳統(tǒng)Canny算子的分析，結(jié)合硬件實現(xiàn)的特點對算法進(jìn)行了改進(jìn)，并在FPGA上實現(xiàn)，結(jié)果表明該算法可以得到預(yù)期的邊緣。但仍存在一些問題，如閾值的選取雖然可以通過直方圖統(tǒng)計自動獲得，但該閾值仍缺乏自適應(yīng)性；邊緣連接未采用遞歸跟蹤，因此連續(xù)性有待改進(jìn)。 ? 參考文獻(xiàn) [1] 賈云得.機器視覺.北京：科學(xué)出版社，2000. [2] 王植.一種基于Canny理論的自適應(yīng)邊緣檢測方法.中國圖像圖形學(xué)報，2004，(8). [3] 韋海萍.Canny算法的改進(jìn)及其硬件實現(xiàn).光學(xué)技術(shù)，2006，32(2). [4] 楊光宇.一種基于FPGA的實時直方圖統(tǒng)計方法.機電工程，2001，24(4).
