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