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

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

1 Canny邊緣檢測(cè)算法的基本原理

1.1 平滑圖像

　　Canny邊緣檢測(cè)算法是高斯函數(shù)的一階導(dǎo)數(shù)，是對(duì)信噪比與定位精度之乘積的最優(yōu)化逼近算子。Canny算法首先用二維高斯函數(shù)的一階導(dǎo)數(shù)對(duì)圖像進(jìn)行平滑[1]。設(shè)二維高斯函數(shù)為：

其梯度矢量為：

用分解的方法提高速度，把ΔG的2個(gè)濾波卷積模板分解為2個(gè)一維的行列濾波器：

其中，k為常數(shù)，σ為高斯濾波器參數(shù)，它控制著平滑程度。對(duì)于σ小的濾波器，雖然定位精度高，但信噪比低；σ大的情況則相反。因此要根據(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個(gè)陣列Px[i，j]和Py[i，j]分別為：

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

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

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

　　為了精確定位邊緣，必須細(xì)化梯度幅值圖像M[i，j]中的屋脊帶，只保留幅值局部變化最大的點(diǎn)，這一過程就是非極大值抑制。在非極大值抑制過程中，Canny算法使用3×3大小，包含8方向的鄰域?qū)μ荻确店嚵蠱[i，j]的所有像素沿梯度方向進(jìn)行梯度幅值的插值。在每一個(gè)點(diǎn)上，鄰域的中心像素m[i，j]與沿梯度方向的2個(gè)梯度幅值的插值結(jié)果進(jìn)行比較。ζ[i，j]是像素鄰域中心處沿著梯度方向的扇形區(qū)域，非極大值抑制在此區(qū)域進(jìn)行。如果鄰域中心點(diǎn)的幅值m[i，j]不比梯度方向上的2個(gè)插值結(jié)果大，則將m[i，j]對(duì)應(yīng)的邊緣標(biāo)志位賦值為0，這一過程把M[i，j]寬屋脊帶細(xì)化為一個(gè)像素寬，并且保留了屋脊的梯度幅值。非極大值抑制NMS(non-maxima suppression)過程的數(shù)學(xué)表示為：


1.4 檢測(cè)和連接邊緣

　　雙閾值算法是對(duì)經(jīng)過非極大值抑制圖像N[i，j]分別使用高、低2個(gè)閾值th和tl分割，得到2個(gè)閾值邊緣圖像Th[i，j]和Tl[i，j]。由于圖像Th[i，j]是由高閾值得到，因此它應(yīng)該不含有假邊緣，但Th[i，j]可能在輪廓上有間斷。因此雙閾值算法要在Th[i，j]中把邊緣連接成輪廓，當(dāng)達(dá)到輪廓端點(diǎn)時(shí)，該算法就在由低閾值得到的邊緣圖像Tl[i，j]的8鄰域位置尋找可以連接到輪廓上的邊緣。這樣，利用遞歸跟蹤的算法不斷地在Tl[i，j]中搜集邊緣，直到將Th[i，j]中所有的間隙都連接起來為止。

2 算法的改進(jìn)

　　傳統(tǒng)Canny算子在2×2的鄰域內(nèi)求有限差分均值來計(jì)算梯度幅值的算法[2]，對(duì)邊緣的定位比較準(zhǔn)確，但對(duì)噪聲過于敏感，容易檢測(cè)出假邊緣和丟失一些真實(shí)邊緣的細(xì)節(jié)部分。針對(duì)傳統(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)，因此本文只進(jìn)行了一次連接。其他改進(jìn)具體體現(xiàn)在硬件實(shí)現(xiàn)的過程中，如用模板代替卷積， 加減法代替小數(shù)乘除等。

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

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


3.1 高斯濾波

　　根據(jù)具體情況選擇適當(dāng)?shù)?sigma;，為了便于硬件實(shí)現(xiàn)可以采用模板來代替卷積運(yùn)算。本文選擇圖2所示的模板，其中的乘除法系數(shù)都是2n的形式，因此可以用移位的方式實(shí)現(xiàn)，這避免了乘除法運(yùn)算帶來的時(shí)間與資源的消耗。計(jì)算中多次用到中心點(diǎn)的8鄰域的值，因此設(shè)計(jì)了窗口形成模塊，以便同時(shí)得到某個(gè)像素點(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°等為中心角度：每個(gè)方向包含±22.5°，根據(jù)Px Py的比值及正負(fù)確定其所在方向的區(qū)域范圍，其方向定義為中心角度的方向。對(duì)于整個(gè)坐標(biāo)系而言，梯度向量共分為8類，但是對(duì)于非局部最大值抑制的實(shí)現(xiàn)，利用中心對(duì)稱原理，只需要4個(gè)方向，如圖5所示。

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

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

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

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

0，即梯度135°和315°兩個(gè)扇區(qū)內(nèi)，則將其方向用3表示。 P>　　進(jìn)行方向計(jì)算時(shí)，需要計(jì)算tg22.5°和tg67.5°。在硬件設(shè)計(jì)中采用簡(jiǎn)化和近似的方法來實(shí)現(xiàn)。

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

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

這樣就可以用簡(jiǎn)單的移位和加減運(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ì)算存儲(chǔ)器寬度為16bit，深度為1 024。當(dāng)有梯度值輸入時(shí)，RAM中相應(yīng)地址的內(nèi)容被讀出來，加1后再存入該地址。如此進(jìn)行下去，直到整幅圖像掃描完畢，得到梯度的直方圖。按照地址從小到大的順序依次累加RAM中的值，當(dāng)累加和不小于圖像總像素的80%時(shí)，輸出對(duì)應(yīng)的地址，即為Th， 而Tl則由Th右移一位得到，如圖6所示。


3.4 非最大值抑制值抑制及邊緣檢測(cè)

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


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

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

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