文獻標識碼： A
DOI：10.16157/j.issn.0258-7998.180634
中文引用格式： 黃虎，楊丁，雷宇輝，等. 基于CORDIC的高速Sobel算法實現[J].電子技術應用，2018，44(9)：87-90.
英文引用格式： Huang Hu，Yang Ding，Lei Yuhui，et al. An implementation of high speed Sobel based on CORDIC[J]. Application of Electronic Technique，2018，44(9)：87-90.
0 引言
圖像邊緣檢測是數字圖像處理領域中的一項關鍵技術[1-3]，廣泛運用在軍事、農業、工業、醫學、航天等領域[4-6]。隨著電子信息技術的快速發展，各大相關領域對圖像邊緣檢測技術提出更高的要求，即：在保證精度的前提下，即時處理大規模數據。
文獻[6]、[7]使用硬件并行技術和流水線技術,大幅增加了數據的吞吐量，但在計算Sobel的梯度值時速度較慢,限制了系統的整體處理速度[6-7]。文獻[8]在文獻[6]、[7]的基礎上，解決了Sobel梯度值計算速度較慢的問題，使系統的整體處理速度提升[6-8]，但該方法犧牲了精度，導致邊緣檢測的效果較差。
針對上述問題，本文采用優化的CORDIC算法，將Sobel梯度計算公式轉換成數據的移位和相加的流水線操作，在保證運算精確度的前提下，大幅提高整體運算速度。
1 Sobel邊緣檢測算法
Sobel算子是一階導數的邊緣檢測算子，具有2組3×3的矩陣。圖像中的像素點分別和這兩個矩陣做卷積后，即可得到圖像的水平、垂直梯度。根據式(1)和式(2)得到圖像梯度值后，將該值和預設的閾值進行比較，即可判斷該點是不是圖像的邊緣部分。
圖1(a)為待處理的圖像數據，圖1(b)、圖1(c)為用于計算x和y方向梯度值的卷積表。
水平梯度Px、垂直梯度Py的計算公式如式(1)所示：
式(1)可以利用兩個行緩沖器(Line_buffer)和流水線型的乘加器完成。如圖2所示，當預存滿兩個行緩沖器后，再等2個時鐘，系統即可實時地得到待處理的圖像數據。
如圖3所示，得到待處理的圖像數據后，P02和P22直接進行加法運算，P12通過移位操作實現乘2效果。為降低D觸發器(Reg)之間的邏輯時延，增加系統的工作頻率，本文將P02和P22相加的結果、P12移位的結果寄存了一拍后，再進行加法運算。依據上述原理，對P02、P20和P10進行了類似操作。最后將兩組數據做減法，再取一個絕對值即可得到x方向的Sobel計算結果。y方向的Sobel計算方法如圖4所示，與圖3的原理類似。
最終梯度值可以根據梯度計算公式算出：
依據式(2)，即可得到最終梯度的模值|G|，將梯度的模值和閾值進行比較，就可以判斷出該點是否為邊緣點。關于梯度模值計算公式，文獻[6]和文獻[7]選擇調用IP核實現平方根運算，該方法在一定程度上保證了計算精度，但是運算速度受限。文獻[8]為解決這個問題，選擇將式(2)等效為|G|=|Px|+|Py|，較好地提高了運算速度，但是運算精度大幅度降低。
為解決上述問題，本文選擇用優化的流水線型的CORDIC算法，實現式(2)的運算。該方法既保證了精度，又提高了運算速度。
2 CORDIC算法原理
2.1 圓周系統下的CORDIC算法
為在保證運算精度的前提下，提高Sobel 算法的即時處理速度和數據吞吐量，本文選擇使用CORDIC算法對其進行優化。CORDIC是將復雜的計算轉換成移位和加法的迭代操作。CORDIC算法有旋轉模式和向量模式。在不同的坐標系下使用，可以實現不同的功能。因需要實現式(2)，本文選用圓周坐標系下的向量模式。
2.2 向量模式
向量模式下通過一系列的角度逼近，可以進行反正切和平方根的計算。旋轉模式的完整迭代公式如式(3)所示。其中xi為當前的橫坐標值，yi為當前的縱坐標值，zi為當前的角度累加值。其中yi控制著判決算子δi的值，yi的值為正時，δi為負；yi的值為負時，δi為正。
3 向量模式下CORDIC算法的優化
為提高系統的總體性能，本文對CORDIC算法進行了一定優化，最終提高了CORDIC算法的精度和速度。
3.1 覆蓋角度的擴展
如式(6)所示，CORDIC算法的旋轉角度有固定的規律，角度為2-i的反正切。當迭代次數趨于無窮時，所有角度值之和約等于99.827°。由此可知，覆蓋角的度數為[-99.827°，99.827°]，不能覆蓋圓周上的所有角度。
考慮到只需求解式(2)，輸入數據的符號變化不影響最終計算結果。因此在式(1)處，直接求取了|Px|、|Py|，通過該操作將所有數據計算限制在了第一象限。為減少迭代次數，還可將輸入數據進行進一步的處理。將|Px|和|Py|進行比較，如果|Py|大于|Px|，則將|Py|和|Px|的值互換；如果|Px|的值大于|Py|，則|Py|和|Px|的值保持不變。預處理后，數據的象限限制在[0°，45°]。因此可以減少一級迭代，收斂域也因此變為[-57.827°，54.827°]。經過上述處理后，式(5)變化成式(7)。
3.2 數據位擴展
CORDIC算法的迭代次數和運算數據的位寬對運算結果的精度有很大的影響。YU Y H在文獻[9]中提出了解決量化誤差(OQE)的方法。
YU Y H指出OQE由近似誤差和舍入誤差組成。近似誤差是由有限個確定旋轉角度量化CORDIC旋轉角度帶來的量化誤差，由最大向量模值和迭代次數決定。舍入誤差是因為計算時數據位不夠帶來的誤差，由數據的位寬決定。
增加數據位寬和迭代的次數都可以提高運算結果的精度。但是，當迭代次數達到一定值后，迭代次數的增加對運算精度的影響變得很小。而增加運算數據的位寬將帶來較好的效果，大幅度降低舍入誤差。每增加一位數據位寬，舍入誤差將變小1/2[9]。本文在用CORDIC算法實現式(2)時，在保證較大的迭代次數的前提下，將運算數據位擴展3位，大幅度降低了舍入誤差。
在進行數據迭代運算時，考慮到采用浮點數可以降低工作頻率，因此采用了定點數。如圖5所示，定點數由符號位(S)、整數位(I)、小數位(D)構成。
3.3 優化后CORDIC算法的實現
圓周模式下的向量模式可以根據輸入的|Px|和|Py|，直接求解出最終梯度的模值。梯度模值運算模塊的硬件結構圖如圖6所示，由預處理、CORDIC迭代流水線、后級處理3部分組成。預處理部分中，將判斷|Px|和|Py|的值是否需要互換。因為迭代次數已經提前確定，縮放因子已知，在預處理階段的數值修正部分可以提前對最終結果進行補償。補償后，將數據位數從24位擴展成27位。擴展后，舍入誤差將降低為之前的1/8，提高了運算的精確度。
預處理后進入CORDIC迭代部分，迭代部分采用15級的流水線模式。根據式(3)可知，在求解式(2)時只需要知道|Px|和|Py|的值，因此可舍棄zi的計算，以此節約一些資源。如圖7所示，迭代部分的每行存在兩個移位寄存器和兩個加/減法器。符號控制信號為Sign，由yi決定。通過式(3)可知，當yi為正時，xi處選用加法器，yi處選用減法器；當yi為負時，xi處選用減法器，yi處選用加法器。
數據通過迭代部分后，進入后級處理部分。后級處理部分將信號緩存一拍后，進行截位處理，然后就可得到x15[26:3]的值，即最終梯度的模值。此外，該設計采用了流水線結構，提高了吞吐量和最大工作頻率。
4 系統仿真及性能分析
本設計在ISE14.7軟件下，用Verilog HDL語言進行了實現。此外，使用MATLAB、Modelsim SE 10.1c進行了本設計的測試。
本文在Xilinx ISE編譯器中編譯好代碼后，通過Modelsim進行了軟件仿真。圖8為本設計關鍵路徑的仿真：CORDIC迭代運算的仿真。修正后的|Px|和|Py|采用定點數的方法進行表示，總計24位，0～12位為小數位，13～22位為整數位，23位為符號位。|Px[26:0]|和|Py[26:0]|為|Px|、|Py|擴展3位后的值，分別用x、y進行表示。Kn為最終梯度模值的計算結果。為了更直觀地表示，輸入值、中間值和輸出結果均用有符號十進制數進行表示。根據仿真結果可知，采用優化后的CORDIC進行式(2)的運算，精確度約為10-4，遠大于文獻[8]的精確度。
仿真后，將文獻[8]的算法和本文的算法進行了對比測試，結果如圖9所示。通過圖9(b)可以觀察到，使用文獻[8]的加速算法后，因為精確度較低的緣故，不能較好地檢測到邊緣，人像左下方、右上方處的頭發邊緣和背景混雜在了一起，人像面部左下方、右上方的邊緣檢測效果較差。使用本文的改進算法后，如圖9(c)所示，在保證運算速度的前提下，較好地識別出了圖像的邊緣，較好地檢測出了頭發和面部的邊緣，與圖9(d)使用MATLAB實現Sobel算法的效果近似。
本文也嘗試使用Xilinx ISE自帶的平方根IP核實現關鍵路徑的計算。選用Spartan6 XC6SLX16 2CSG324C芯片在Xilinx ISE14.7軟件平臺下，對平方根IP核進行編譯綜合。編譯綜合后，得到ISE計算出的最高工作頻率信息。為測試本文使用算法的性能，在同樣的條件下，對本文的算法也進行了編譯，得到了最高工作頻率信息。最終結果如表1所示。采用IP核進行關鍵路徑的計算，最高工作頻率為114.745 MHz。采用優化后的CORDIC算法進行關鍵路徑的計算，最高頻率為187.652 MHz。相比使用IP核的方法，采用優化后的CORDIC算法實現關鍵路徑的計算可以提速63.53％。
5 結論
本文在傳統Sobel加速算法的基礎上，在FPGA平臺上使用優化的CORDIC算法實現了Sobel算法加速。通過圖9可知，該方法的邊緣檢測效果良好，較好地檢測出了圖像的邊緣。通過表1可知，該方法與調用IP核相比提高了百分之63.53％的工作頻率。實驗結果表明，本設計進一步提高了系統的運算速度，適合在對速度有較高要求的系統中使用。
參考文獻
[1] AGGARWAL S，MEHER P K，KHARE K.Concept，design，and implementation of reconfigurable CORDIC[J].IEEE Transactions on Very Large Scale Integration Systems，2016，24(4)：1588-1592.
[2] PRASAD N，TRIPATHY M R，DAS D S，et al.Efficient VLSI implementation of CORDIC-based direct digital synthesizer[M].Intelligent Computting，Communication and Devices.Springer India，2015.
[3] 于莉潔，孫瑜亮，繆永偉.基于深度信息局部二值模式特征的室內場景邊緣檢測[J].計算機輔助設計與圖形學學報，2017，29(12)：2162-2170.
[4] 劉小寧，謝宜壯，陳禾，等.CORDIC算法的優化及實現[J].北京理工大學學報，2015，35(11)：1164-1170.
[5] SHUKLA R，RAY K C.Low latency hybrid CORDIC algorithm[J].IEEE Transactions on Computers，2013，63(12)：3066-3078.
[6] 李錦明，閆曉俊，江旭東，等.Sobel圖像邊沿檢測算法的優化設計與實現[J].電子技術應用，2016，42(3)：71-73.
[7] 楊新華，寇為剛.基于FPGA的Sobel算子圖像邊緣檢測算法[J].儀表技術與傳感器，2013(1)：102-104.
[8] 杜正聰，寧龍飛.基于Sobel算法圖像邊緣檢測的FPGA實現[J].電子技術應用，2016，42(10)：89-91.
[9] HU Y H.The quantization effects of the CORDIC algorithm[J].IEEE Transactions on Signal Processing，1992，40(4)：834-844.
作者信息:
黃 虎，楊 丁，雷宇輝，謝佳訊，陳詩瑤，鄒 瑜
(成都理工大學 信息科學與技術學院，四川 成都610059）