摘? 要： 通過對傳統(tǒng)Canny邊緣檢測" title="邊緣檢測">邊緣檢測算法的分析提出了相應(yīng)的改進(jìn)方法。通過模板代替卷積、適當(dāng)?shù)慕谱儞Q、充分利用并行處理單元等使其能夠用FPGA實(shí)現(xiàn)。

　　關(guān)鍵詞： Canny算子；高斯" title="高斯">高斯濾波；非極大值抑制" title="非極大值抑制">非極大值抑制；雙閾值；FPGA?

?

??? Canny邊緣檢測算法" title="邊緣檢測算法">邊緣檢測算法具有良好的信噪比和檢測精度，因此在圖像處理領(lǐng)域被廣泛采用。但由于其計(jì)算量巨大，實(shí)時性較差，而且軟件處理的設(shè)備體積較大，所以不適合實(shí)時檢測。本文對原始Canny算法進(jìn)行了分析、改進(jìn)，并在FPGA中實(shí)現(xiàn)。實(shí)驗(yàn)證明新算法能滿足實(shí)時性要求，而且檢測精度和抗噪能力也較理想。

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 計(jì)算梯度的幅值和方向

　　傳統(tǒng)Canny算法采用2×2鄰域一階偏導(dǎo)的有限差分來計(jì)算平滑后的數(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)化公式計(jì)算，用二階范數(shù)來計(jì)算梯度幅值為：

　　梯度方向?yàn)椋?/P>

???

1.3 對梯度幅值進(jìn)行非極大值抑制

　　為了精確定位邊緣，必須細(xì)化梯度幅值圖像M[i，j]中的屋脊帶，只保留幅值局部變化最大的點(diǎn)，這一過程就是非極大值抑制。在非極大值抑制過程中，Canny算法使用3×3大小，包含8方向的鄰域?qū)μ荻确店嚵蠱[i，j]的所有像素沿梯度方向進(jìn)行梯度幅值的插值。在每一個點(diǎn)上，鄰域的中心像素m[i，j]與沿梯度方向的2個梯度幅值的插值結(jié)果進(jìn)行比較。ζ[i，j]是像素鄰域中心處沿著梯度方向的扇形區(qū)域，非極大值抑制在此區(qū)域進(jìn)行。如果鄰域中心點(diǎ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á)到輪廓端點(diǎn)時，該算法就在由低閾值得到的邊緣圖像Tl[i，j]的8鄰域位置尋找可以連接到輪廓上的邊緣。這樣，利用遞歸跟蹤的算法不斷地在Tl[i，j]中搜集邊緣，直到將Th[i，j]中所有的間隙都連接起來為止。

2 算法的改進(jìn)

　　傳統(tǒng)Canny算子在2×2的鄰域內(nèi)求有限差分均值來計(jì)算梯度幅值的算法[2]，對邊緣的定位比較準(zhǔn)確，但對噪聲過于敏感，容易檢測出假邊緣和丟失一些真實(shí)邊緣的細(xì)節(jié)部分。針對傳統(tǒng)Canny算法在梯度幅值計(jì)算上的缺陷，提出了一種在像素8鄰域內(nèi)通過計(jì)算x方向、y方向、135°方向、45°方向一階偏導(dǎo)數(shù)有限差分來確定像素梯度幅值的方法。這種方法兼顧了梯度幅值計(jì)算中，邊緣定位準(zhǔn)確和抑制噪聲的要求，在試驗(yàn)中取得了很好的效果。具體算法如下：

　　像素的梯度幅值和梯度方向用直角坐標(biāo)到極坐標(biāo)的坐標(biāo)轉(zhuǎn)化公式來計(jì)算，用二階范數(shù)來計(jì)算梯度幅值為：

　　另外，傳統(tǒng)算法中的邊緣連接采取的是遞歸方法，不適合硬件實(shí)現(xiàn)" title="硬件實(shí)現(xiàn)">硬件實(shí)現(xiàn)，因此本文只進(jìn)行了一次連接。其他改進(jìn)具體體現(xiàn)在硬件實(shí)現(xiàn)的過程中，如用模板代替卷積， 加減法代替小數(shù)乘除等。

3 改進(jìn)算法及FPGA實(shí)現(xiàn)

　　根據(jù)以上的數(shù)學(xué)推導(dǎo)及分析，得到Canny 邊緣檢測用FPGA實(shí)現(xiàn)的流程圖，如圖1所示。

?

?

3.1 高斯濾波

　　根據(jù)具體情況選擇適當(dāng)?shù)摩遥瑸榱吮阌谟布?shí)現(xiàn)可以采用模板來代替卷積運(yùn)算。本文選擇圖2所示的模板，其中的乘除法系數(shù)都是2ⁿ的形式，因此可以用移位的方式實(shí)現(xiàn)，這避免了乘除法運(yùn)算帶來的時間與資源的消耗。計(jì)算中多次用到中心點(diǎn)的8鄰域的值，因此設(shè)計(jì)了窗口形成模塊，以便同時得到某個像素點(diǎn)的8鄰域的值。原理圖如圖3所示。

?

?

　　行延遲和列延遲分別由FIFO和寄存器完成，其中FIFO的深度等于圖像的列數(shù)。

3.2 梯度計(jì)算

　　經(jīng)過高斯濾波模塊的數(shù)據(jù)再通過窗口形成模塊，得到3×3鄰域，然后按照式15，計(jì)算梯度的幅值。

　　梯度方向計(jì)算：根據(jù)8連通區(qū)域，量化邊緣方向。首先將梯度角度的變化范圍減小到圓周的1/8扇區(qū)。如圖4所示，以0°、45°、90°、135°等為中心角度：每個方向包含±22.5°，根據(jù)Px Py的比值及正負(fù)確定其所在方向的區(qū)域范圍，其方向定義為中心角度的方向。對于整個坐標(biāo)系而言，梯度向量共分為8類，但是對于非局部最大值抑制的實(shí)現(xiàn)，利用中心對稱原理，只需要4個方向，如圖5所示。

?

?

　　當(dāng)|P_y/P_x|>tg22.5°，即梯度方向在0和180兩個扇區(qū)內(nèi)，則將其方向用0表示；

　　當(dāng)tg22.5°<|P_y/P_x|>tg67.5°且P_x/P_y>0，即梯度方向在45°和225°兩個扇區(qū)內(nèi)，則將其方向用1表示；

　　當(dāng)|Py/Px|>tg67.5°即梯度方向在90°和270°兩個扇區(qū)內(nèi)，則將其方向用2表示；

　　當(dāng)tg22.5°<|P_y/P_x|>tg67.5°且P_x/P_y>0，即梯度135°和315°兩個扇區(qū)內(nèi)，則將其方向用3表示。

　　進(jìn)行方向計(jì)算時，需要計(jì)算tg22.5°和tg67.5°。在硬件設(shè)計(jì)中采用簡化和近似的方法來實(shí)現(xiàn)。

　　tg22.5°≈0.4375=1/2-1/16

??? tg67.5°≈2.5=2+1/2

??? 這樣就可以用簡單的移位和加減運(yùn)算代替復(fù)雜的小數(shù)乘法運(yùn)算，而在實(shí)際的數(shù)字圖像處理中，近似引入的誤差是允許的^[3]。再利用比較器和編碼器就可以完成方向判斷。

3.3 閾值計(jì)算

　　閾值選取基于梯度直方圖，所以先統(tǒng)計(jì)梯度直方圖^[4]。以256×256×8bit的圖為例，基于雙端口RAM(hist_buffer)及其控制器完成。經(jīng)計(jì)算存儲器寬度為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 非最大值抑制值抑制及邊緣檢測

　　本文采取將強(qiáng)弱邊緣檢測同時進(jìn)行，并且在邊緣檢測之前形成窗口，這樣就避免了后續(xù)考慮同步的問題，節(jié)省了存儲單元。圖7為原理圖，其中粗線表示同時輸出9個值。

?

?

4 實(shí)驗(yàn)結(jié)果

　　圖8依次是原圖、軟件處理結(jié)果圖和硬件處理結(jié)果圖。實(shí)驗(yàn)結(jié)果表明本算法可以得到較準(zhǔn)確的邊緣。

?

?

　　本文通過對傳統(tǒng)Canny算子的分析，結(jié)合硬件實(shí)現(xiàn)的特點(diǎn)對算法進(jìn)行了改進(jìn)，并在FPGA上實(shí)現(xiàn)，結(jié)果表明該算法可以得到預(yù)期的邊緣。但仍存在一些問題，如閾值的選取雖然可以通過直方圖統(tǒng)計(jì)自動獲得，但該閾值仍缺乏自適應(yīng)性；邊緣連接未采用遞歸跟蹤，因此連續(xù)性有待改進(jìn)。

?

參考文獻(xiàn)

[1] 賈云得.機(jī)器視覺.北京：科學(xué)出版社，2000.

[2] 王植.一種基于Canny理論的自適應(yīng)邊緣檢測方法.中國圖像圖形學(xué)報(bào)，2004，(8).

[3] 韋海萍.Canny算法的改進(jìn)及其硬件實(shí)現(xiàn).光學(xué)技術(shù)，2006，32(2).

[4] 楊光宇.一種基于FPGA的實(shí)時直方圖統(tǒng)計(jì)方法.機(jī)電工程，2001，24(4).