Canny邊緣檢測算法在飛騰平臺上的實現與優化

郭恒亮，柴曉楠，韓 林，赫曉慧，商建東

（1.鄭州大學河南省超級計算中心，鄭州450000；2.鄭州大學信息工程學院，鄭州450000；3.鄭州大學地球科學與技術學院，鄭州450000）

0 概述

邊緣檢測是數字圖像處理領域的關鍵技術，近年來在道路車輛識別［1］、遙感影像處理［2-3］、醫學影像識別［4］等任務中得到廣泛應用。數字圖像處理中的邊緣是周圍像素極大變化點的集合。邊緣檢測是指一種保留圖像結構屬性點、大幅度減少圖像數據量并剔除不相關信息的圖像處理方法。經典的邊緣檢測算法主要基于邊緣算子，并且隨著人工智能技術的發展，又出現了基于形態學、小波變換和機器學習等的邊緣檢測算法［5-7］。由于圖像處理技術在人工智能、大數據等領域得到廣泛應用，因此對于硬件加速處理器的計算力要求越來越高。DSP 具有快速、高效、低功耗和便于集成等特點，適用于語音處理、圖像處理［8］、信息通信等應用場景。面對新應用對計算機性能提出的更高要求，目前DSP 趨向于通過單指令流多數據流（Single Instruction Multiple Data，SIMD）位長和超長指令字（Very Long Instruction Word，VLIW）等技術來增強DSP 內核指令的并行處理能力［9-11］。DSP 底層架構的不斷優化升級帶來性能提升的同時，也對上層軟件提出了更高的要求，因此優化軟件處理算法以充分利用高性能的DSP 架構也是DSP 應用領域亟需解決的問題。

針對不同應用場景提取的邊緣精度不同問題，文獻［12-14］通過根據不同的應用場景選擇不同的平滑去噪方式或增強邊緣輪廓來獲取更精準的邊緣。文獻［15-16］選取不同邊緣閾值以提取更精準的邊緣特征。Canny 邊緣檢測是一種廣泛使用的邊緣檢測算法，在此基礎上提出的改進濾波、疊加其他增強邊緣算法和改進閾值［17-19］等優化方案均是基于算法應用層面，而面向加速并行的優化方案目前還較少。由國防科技大學研制的FT-M7002 是一款具有512 位長SIMD 的高性能并行處理器，DSP 內核基于超長指令字結構，具有標量以及向量處理單元，32 位峰值性能可達200GFLOPS 和100GMACS［20-21］。由于國內對DSP 方面的研究起步較晚，硬件與軟件支持不匹配，面向國產平臺加速并行優化應用較少，而FT-M7002 具有高度并行處理特性，因此本文基于FT-M7002 架構進行Canny邊緣檢測算法的實現與優化。

1 Canny邊緣檢測算法原理與硬件平臺架構

常見的經典邊緣檢測算子包括Sobel 算子、Robel算子、Priwitt 算子、Laplacian 算子及Canny 算子。邊緣檢測算子的差異主要為計算邊緣點時的圖片結構特征提取方式不同。根據不同的圖片結構特征提取方式，提取的邊緣效果也不同。Canny邊緣檢測算子是由John F.Canny于1986年提出的具有附加響應最優檢測、檢測邊緣位置偏差最小以及單個邊緣點變化定位誤差小等優點的算子，是目前應用較廣泛的算子。

1.1 Canny邊緣檢測算法

Canny 邊緣檢測是一種基于模板卷積計算保留圖片特征信息的算法，檢測流程如圖1所示。

圖1 Canny 邊緣檢測流程Fig.1 Procedure of Canny edge detection

Canny邊緣檢測算法的具體步驟如下：

1）Canny 邊緣檢測屬于先平滑后求導的算法，通常使用高斯濾波平滑圖像。G(x,y)表示二維高斯函數，即圖像去噪平滑使用的卷積操作數，如式（1）所示。fS(x,y)為濾波卷積平滑后的圖像像素數據，其中f(x,y)表示原圖像像素數據，即輸入的原數據，如式（2）所示。

2）計算圖像每個像素的點梯度，x方向和y方向偏導求梯度的具體計算過程為通過一階有限差分近似求取灰度的梯度值，如式（3）和式（4）所示。梯度值為矢量，即包含幅值和方向，根據式（5）求出幅值M(x,y)。變化率又稱為幅值，幅值越大，像素區域灰度值變化越明顯，而像素灰度值變化越明顯的點越能標識圖片結構特征。根據式（6）計算得到判斷其方向變化的α(x,y)。

3）對幅值圖像進行非極大值抑制，根據象限兩個對角線的4 個方向進行劃分，如圖2（a）和圖2（b）所示，共分為8 個部分，即上（Up）、下（Down）、左（Left）、右（Right）、左上（LU）、左下（LD）、右上（RU）和右下（RD），對幅值進行非極大值抑制。

圖2 4 個方向的角度圖Fig.2 Angle diagram of four directions

4）選取高閾值TH和低閾值TL，判斷經過極大值抑制之后的像素梯度，若幅值小于TL的點則拋棄，若大于TH的點則標記，而大于TL且小于TH的點根據周圍N連通區域判斷其是否為邊緣點。

1.2 飛騰平臺架構

飛騰平臺是一款高性能數字信號處理器，搭載自主設計的高性能處理芯片，芯片主頻為1 GHz，峰值性能為200GFLOPS，包含1 個RISC CPU 核和2 個DSP 核，如圖3所示，具有全局共享Cache（SubGC）、核間同步、DDR3 存儲器以及PCIE 等多個設備。內核與核外設備為環形連接，環形互連包含雙向讀寫環路與單項配置命令環路，其中單項數據位寬為256 位。內核采用超長指令字結構，包含向量處理單元（Vector Processing Unit，VPU）與標量處理單元（Scalar Processing Unit，SPU）。飛騰平臺架構的主要特點是支持512 位SIMD 操作以及半字（16 位數據）和字（32位數據）大小的數據變量。

圖3 飛騰平臺架構Fig.3 FT platform architecture

2 基于飛騰平臺的Canny 算法實現與優化

2.1 Canny邊緣檢測算法的實現

飛騰平臺具有相應的FT-M7002 IDE，借助IDE生成工程后，C 程序通過M7002 編譯器生成對應的匯編文件，經M7002 匯編器將匯編文件轉換為ELF目標文件，最終通過M7002 鏈接器將目標文件以及對應相關庫鏈接生成一個可執行文件。可執行文件經過IDE 下載到飛騰對應的內存地址空間處執行程序。在飛騰平臺上實現Canny 算法時，考慮到實際檢測邊緣過程中采用的去噪平滑方式不同，因此本文將高斯平滑去噪部分略去，在濾波平滑去噪后進行梯度計算以及邊緣閾值提取?；陲w騰平臺的Canny邊緣檢測算法實現流程如圖4所示。

圖4 基于飛騰平臺的Canny邊緣檢測算法實現流程Fig.4 The implementation procedure of Canny edge detection algorithm based on FT platform

在實際代碼的實現過程中，首先Canny 接口直接進行圖片的梯度計算，圖片讀入默認為8 位數據變量類型（char），然后進行梯度計算，按照式（3）和式（4）分別計算x方向梯度與y方向梯度，每個方向的梯度計算過程為：參考具有中心對稱的二維卷積核可以分解為兩個互相垂直的一維卷積，即將先計算出的行卷積結果與其方向垂直的一維卷積核進行卷積，得到二維卷積結果。因此，在實現每個方向的梯度計算時，將再次劃分為橫向與縱向的卷積計算。

在梯度計算完成后，根據高低閾值以及梯度計算后的幅值與方向來標記邊緣，根據橫軸、縱軸以及對角線劃分8個方向區域，將每個像素計算出的幅值變化方向α(x,y)對應到方向角度為［0.0°，22.5°］、［22.5°，67.5°］和［67.5°，90.0°］。若α值在［0.0°，22.5°］范圍內，則對比區域為左右鄰域，若在［22.5°，67.5°］范圍內，則對比區域為對角線所有鄰域，若在［67.5°，90.0°］范圍內，則對比區域為上下鄰域。對比獲得的結果值，若其為上下、左右、對角線鄰域內的最大幅值，則為邊緣點。

在處理每個像素點時，判斷高低閾值以及梯度幅值，根據不同分支情況對圖片進行標記入棧操作來區分是否為邊緣點。標記分為邊緣點、可能是邊緣點、不是邊緣點等3 種情況，3 種情況對應的入棧賦值為2、0、1。當所有像素處理完畢后，針對棧中值為0，即可能是邊緣點的情況進行單獨處理，查看該像素周圍是否含有邊緣，若有則標記為邊緣點。

2.2 Canny邊緣檢測算法的優化

針對Canny邊緣檢測算法的實現過程進行各部分計算時間的分析，如圖5所示，根據常見的3 種卷積核測試得到計算梯度的時間約占總時間的2/3，而剩余的1/3 主要是提取邊緣處理圖片的計算時間。根據上述分析結果可知，梯度計算時間是Canny邊緣檢測算法實現過程中占用時間最多的計算過程，因此根據飛騰平臺架構特點針對梯度計算進行優化。

圖5 Canny邊緣檢測算法實現過程中各部分的計算時間占比Fig.5 The proportion of calculation time of each part in the implementation process of Canny edge detection algorithm

2.2.1 梯度計算并行化

由于梯度計算算法存在計算量大、局部數據連續訪問和計算過程重復等特點，而飛騰平臺具有長向量位支持特性，因此可以利用SIMD 對其進行并行化處理。在將圖片讀入轉換為矩陣時，默認圖片矩陣數據類型為8 位數據變量類型（char），但是在計算梯度時卷積核為浮點數，即32f，因此利用飛騰內嵌的混洗指令、移位指令和打包指令封裝生成數據轉換并行接口，以便調用實現8u 數據類型變量圖片讀入與32f 類型數據計算，同時增加了int轉為short類型的并行接口。在解決數據類型問題后，利用其他內嵌指令進行并行化，具體實現的核心代碼如算法1所示，首先使用圖片vec_ld 指令分別取出3 行連續的16 個數據，然后利用向量乘加指令進行計算。在梯度計算完成后的計算過程中使用的數據類型為半字類型，因此通過vec_fdstru指令將計算結果的數據類型由float轉為int類型，這樣就可以使用int_to_short并行接口將數據類型由float轉為short類型。同時，由于float類型數據轉換為short類型數據，在理論上內存空間要縮減一半，因此并行接口每轉換一次short 類型的數據變量，float 類型數據需計算兩次（即循環展開一次）才可以獲得一次的轉換數據量。

算法1Canny 梯度計算并行算法

2.2.2 梯度計算存儲優化

梯度計算分為橫向梯度與縱向梯度計算。橫向梯度是連續訪問的，其左右偏移也為固定通道數?？v向梯度因為是不同行之間的訪問計算，每次計算均需跨行訪問，因此數據訪問是不連續的。

根據飛騰平臺架構分為標量存儲空間與向量存儲空間，在每次進行SIMD 計算前需要將數據傳輸到向量存儲空間，利用DMA 數據傳輸機制并結合雙緩沖的方式傳輸數據，即將數據劃分為兩個區域，一部分用來計算，另一部分用來存取下一次計算所需的數據。在每次計算橫向梯度時，傳輸需要計算的一行數據，以便減少數據傳輸次數，達到數據重用的目的。在計算縱向數據時，使用SIMD 指令取值是通過定義的首地址進行偏移取值，在實際計算過程中按照矩陣跨行訪存的方式，每次計算結果得到一行數據，共需跨卷積核乘列的內存單元。因此，在計算縱向數據時需根據數據訪問特性，設置固定地址起始存儲計算涉及的行數數據來減少數據訪問的不連續性問題，并使用DMA 數據傳輸將其在計算之前存儲到固定地址，達到連續訪問的效果。

2.2.3 其他優化

本文結合Canny 并行梯度算法的實現程序，深入了解飛騰的編譯工具鏈對核心計算部分代碼進行函數內聯、消除冗余代碼段、刪除不使用的參數、指令重排等編譯優化。使用循環展開和軟流水使得指令重新排序，解決程序指令處理時隙問題，并利用循環置換及不變量外提減少計算過程中數據的訪問次數，增加數據重用性，提升程序執行性能。

3 實驗結果與分析

3.1 實驗環境

實驗平臺為FT-M7002 的單個DSP 內核，使用680 像素×480 像素的經典邊緣檢測測試圖片，評價指標為運行時間。實驗主要對卷積核大小為3×3、5×5、7×7 情況下Canny邊緣檢測算法優化前后的性能進行對比分析。

3.2 Canny 算法優化前后性能對比

Canny邊緣檢測算法經過橫向梯度計算優化前后的性能如表1所示。當卷積核大小為3×3 時，x方向梯度與y方向梯度計算的加速效果為1.316 與1.346；當卷積核大小為5×5 時，x方向梯度與y方向梯度計算的加速比為1.430 與1.459；當卷積核大小為7×7 時，x方向梯度與y方向梯度計算的加速比為1.512 與1.540。實驗數據表明，x方向梯度與y方向梯度計算在相同實驗環境下的加速效果相差不大，隨著卷積核尺寸的增大，加速效果也隨之增加，但是該加速效果與預期加速效果不太符合，根據飛騰平臺架構的512 位SIMD 計算同時疊加其他優化方式，應該達到更好的加速效果。這是因為在計算過程中，雖然數據是可重用的并且傳輸數據是雙緩沖的，但是數據傳輸仍然需要占用時間，同時在整個計算過程中的外層循環控制過程的計算較復雜，使用向量部件也需要消耗計算時間，因此加速效果不明顯，而只有計算量足夠大才可能忽略向量部件的計算時間消耗，達到預期的加速效果。

在表1 中，在卷積核大小為3×3、5×5 與7×7 時，Canny 橫向梯度計算優化之后算法的整體加速效果分別為1.138、1.173、1.221。可以看出，整體的加速效果要比單獨計算x方向梯度與y方向梯度差，由算法整體計算時間分布可以看出，x方向梯度與y方向梯度計算約占整體計算時間的2/3，并且本文主要針對梯度計算進行優化，因此剩余約1/3 的計算時間優化較少，整體加速效果不明顯。在結合縱向梯度計算優化后，由表2 可以看出，在不同卷積核尺寸下，x方向梯度與y方向梯度計算加速效果提升明顯，這充分證明了數據量與加速效果在飛騰并行處理部件存儲空間可承受范圍內是成正比的。

表1 橫向梯度計算優化前后的Canny 算法性能對比Table 1 Performance comparison of Canny algorithm before and after transverse gradient calculation optimization

表2 橫向梯度計算與縱向梯度計算優化前后的Canny 算法性能對比Table 2 Performance comparison of Canny algorithm before and after transverse gradient calculation and vertical gradient calculation optimization

根據飛騰平臺的周期置換時間公式將周期乘以16 再除以106可置換為ms，基于橫向梯度計算優化、橫向與縱向梯度計算優化后與整體優化的Canny邊緣檢測算法運行時間對比結果如圖6所示?？梢钥闯觯谟嬎銉灮熬矸e核大小為7×7 的運行時間幾乎為3×3 的2 倍，但是優化后的運行時間相差較小，這充分證明了Canny邊緣檢測算法本身不容易優化的計算基數所占的運行時間是固定的，在卷積核大小為3×3 時可優化的計算時間占比較小，因此整體優化效果不明顯，而卷積核大小為7×7 時的計算量大，因此優化效果最明顯。

圖6 基于3 種計算優化方式的Canny 算法運行時間對比Fig.6 Comparison of running time of Canny algorithm based on three calculation optimization modes

4 結束語

本文基于FT-M7002 高性能處理架構，提出Canny梯度計算并行算法，采用手工向量化、訪存優化、DMA數據雙緩沖、循環展開和軟件流水等技術，提升該算法在FT-M7002 平臺下的并行性與運行效率。實驗結果表明，與原始Canny邊緣檢測算法相比，該算法整體運行速度提升了1.490～2.112 倍，縮小了與主流加速器件在圖像處理領域的性能差距。然而由于本文研究僅局限于單個FT-DSP 核上Canny邊緣檢測算法的優化，因此后續將進一步提升其在多DSP 核硬件平臺架構中的運行速度，增強Canny梯度并行算法在國產高性能DSP中的適用性。