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

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

0 概述

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

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

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

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

1.1 Canny邊緣檢測算法

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

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

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

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

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

3）對幅值圖像進行非極大值抑制，根據(jù)象限兩個對角線的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，判斷經(jīng)過極大值抑制之后的像素梯度，若幅值小于TL的點則拋棄，若大于TH的點則標記，而大于TL且小于TH的點根據(jù)周圍N連通區(qū)域判斷其是否為邊緣點。

1.2 飛騰平臺架構

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

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

2 基于飛騰平臺的Canny 算法實現(xiàn)與優(yōu)化

2.1 Canny邊緣檢測算法的實現(xiàn)

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

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

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

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

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

2.2 Canny邊緣檢測算法的優(yōu)化

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

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

2.2.1 梯度計算并行化

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

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

2.2.2 梯度計算存儲優(yōu)化

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

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

2.2.3 其他優(yōu)化

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

3 實驗結果與分析

3.1 實驗環(huán)境

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

3.2 Canny 算法優(yōu)化前后性能對比

Canny邊緣檢測算法經(jīng)過橫向梯度計算優(yōu)化前后的性能如表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。實驗數(shù)據(jù)表明，x方向梯度與y方向梯度計算在相同實驗環(huán)境下的加速效果相差不大，隨著卷積核尺寸的增大，加速效果也隨之增加，但是該加速效果與預期加速效果不太符合，根據(jù)飛騰平臺架構的512 位SIMD 計算同時疊加其他優(yōu)化方式，應該達到更好的加速效果。這是因為在計算過程中，雖然數(shù)據(jù)是可重用的并且傳輸數(shù)據(jù)是雙緩沖的，但是數(shù)據(jù)傳輸仍然需要占用時間，同時在整個計算過程中的外層循環(huán)控制過程的計算較復雜，使用向量部件也需要消耗計算時間，因此加速效果不明顯，而只有計算量足夠大才可能忽略向量部件的計算時間消耗，達到預期的加速效果。

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

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

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

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

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

4 結束語

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