文獻(xiàn)標(biāo)識碼： A
DOI：10.16157/j.issn.0258-7998.180634
中文引用格式： 黃虎,，楊丁，雷宇輝,，等. 基于CORDIC的高速Sobel算法實(shí)現(xiàn)[J].電子技術(shù)應(yīng)用,，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 引言
圖像邊緣檢測是數(shù)字圖像處理領(lǐng)域中的一項(xiàng)關(guān)鍵技術(shù)[1-3]，廣泛運(yùn)用在軍事,、農(nóng)業(yè),、工業(yè)、醫(yī)學(xué),、航天等領(lǐng)域[4-6],。隨著電子信息技術(shù)的快速發(fā)展，各大相關(guān)領(lǐng)域?qū)D像邊緣檢測技術(shù)提出更高的要求,，即：在保證精度的前提下,，即時處理大規(guī)模數(shù)據(jù)。
文獻(xiàn)[6],、[7]使用硬件并行技術(shù)和流水線技術(shù),大幅增加了數(shù)據(jù)的吞吐量,，但在計算Sobel的梯度值時速度較慢,限制了系統(tǒng)的整體處理速度[6-7]。文獻(xiàn)[8]在文獻(xiàn)[6],、[7]的基礎(chǔ)上,，解決了Sobel梯度值計算速度較慢的問題，使系統(tǒng)的整體處理速度提升[6-8],，但該方法犧牲了精度,，導(dǎo)致邊緣檢測的效果較差。
針對上述問題,，本文采用優(yōu)化的CORDIC算法，將Sobel梯度計算公式轉(zhuǎn)換成數(shù)據(jù)的移位和相加的流水線操作,，在保證運(yùn)算精確度的前提下,，大幅提高整體運(yùn)算速度。
1 Sobel邊緣檢測算法
Sobel算子是一階導(dǎo)數(shù)的邊緣檢測算子,，具有2組3×3的矩陣,。圖像中的像素點(diǎn)分別和這兩個矩陣做卷積后，即可得到圖像的水平、垂直梯度,。根據(jù)式(1)和式(2)得到圖像梯度值后,，將該值和預(yù)設(shè)的閾值進(jìn)行比較，即可判斷該點(diǎn)是不是圖像的邊緣部分,。
圖1(a)為待處理的圖像數(shù)據(jù),，圖1(b)、圖1(c)為用于計算x和y方向梯度值的卷積表,。
水平梯度Px,、垂直梯度Py的計算公式如式(1)所示：
式(1)可以利用兩個行緩沖器(Line_buffer)和流水線型的乘加器完成。如圖2所示,，當(dāng)預(yù)存滿兩個行緩沖器后,，再等2個時鐘，系統(tǒng)即可實(shí)時地得到待處理的圖像數(shù)據(jù),。
如圖3所示,，得到待處理的圖像數(shù)據(jù)后，P02和P22直接進(jìn)行加法運(yùn)算,，P12通過移位操作實(shí)現(xiàn)乘2效果,。為降低D觸發(fā)器(Reg)之間的邏輯時延，增加系統(tǒng)的工作頻率,，本文將P02和P22相加的結(jié)果,、P12移位的結(jié)果寄存了一拍后，再進(jìn)行加法運(yùn)算,。依據(jù)上述原理,，對P02、P20和P10進(jìn)行了類似操作,。最后將兩組數(shù)據(jù)做減法,，再取一個絕對值即可得到x方向的Sobel計算結(jié)果。y方向的Sobel計算方法如圖4所示,，與圖3的原理類似,。
最終梯度值可以根據(jù)梯度計算公式算出：
依據(jù)式(2)，即可得到最終梯度的模值|G|,，將梯度的模值和閾值進(jìn)行比較,，就可以判斷出該點(diǎn)是否為邊緣點(diǎn)。關(guān)于梯度模值計算公式,，文獻(xiàn)[6]和文獻(xiàn)[7]選擇調(diào)用IP核實(shí)現(xiàn)平方根運(yùn)算,，該方法在一定程度上保證了計算精度，但是運(yùn)算速度受限,。文獻(xiàn)[8]為解決這個問題,，選擇將式(2)等效為|G|=|Px|+|Py|,，較好地提高了運(yùn)算速度，但是運(yùn)算精度大幅度降低,。
為解決上述問題,，本文選擇用優(yōu)化的流水線型的CORDIC算法，實(shí)現(xiàn)式(2)的運(yùn)算,。該方法既保證了精度,，又提高了運(yùn)算速度。
2 CORDIC算法原理
2.1 圓周系統(tǒng)下的CORDIC算法
為在保證運(yùn)算精度的前提下,，提高Sobel 算法的即時處理速度和數(shù)據(jù)吞吐量,，本文選擇使用CORDIC算法對其進(jìn)行優(yōu)化。CORDIC是將復(fù)雜的計算轉(zhuǎn)換成移位和加法的迭代操作,。CORDIC算法有旋轉(zhuǎn)模式和向量模式,。在不同的坐標(biāo)系下使用，可以實(shí)現(xiàn)不同的功能,。因需要實(shí)現(xiàn)式(2),，本文選用圓周坐標(biāo)系下的向量模式。
2.2 向量模式
向量模式下通過一系列的角度逼近,，可以進(jìn)行反正切和平方根的計算,。旋轉(zhuǎn)模式的完整迭代公式如式(3)所示。其中xi為當(dāng)前的橫坐標(biāo)值,，yi為當(dāng)前的縱坐標(biāo)值,，zi為當(dāng)前的角度累加值。其中yi控制著判決算子δi的值,，yi的值為正時,，δi為負(fù)；yi的值為負(fù)時,，δi為正,。
3 向量模式下CORDIC算法的優(yōu)化
為提高系統(tǒng)的總體性能，本文對CORDIC算法進(jìn)行了一定優(yōu)化,，最終提高了CORDIC算法的精度和速度,。
3.1 覆蓋角度的擴(kuò)展
如式(6)所示，CORDIC算法的旋轉(zhuǎn)角度有固定的規(guī)律,，角度為2-i的反正切,。當(dāng)?shù)螖?shù)趨于無窮時，所有角度值之和約等于99.827°,。由此可知,，覆蓋角的度數(shù)為[-99.827°，99.827°],，不能覆蓋圓周上的所有角度,。
考慮到只需求解式(2)，輸入數(shù)據(jù)的符號變化不影響最終計算結(jié)果,。因此在式(1)處,，直接求取了|Px|、|Py|,，通過該操作將所有數(shù)據(jù)計算限制在了第一象限,。為減少迭代次數(shù)，還可將輸入數(shù)據(jù)進(jìn)行進(jìn)一步的處理,。將|Px|和|Py|進(jìn)行比較,，如果|Py|大于|Px|，則將|Py|和|Px|的值互換,；如果|Px|的值大于|Py|,，則|Py|和|Px|的值保持不變。預(yù)處理后,，數(shù)據(jù)的象限限制在[0°,，45°]。因此可以減少一級迭代,，收斂域也因此變?yōu)閇-57.827°,，54.827°]。經(jīng)過上述處理后,，式(5)變化成式(7),。
3.2 數(shù)據(jù)位擴(kuò)展
CORDIC算法的迭代次數(shù)和運(yùn)算數(shù)據(jù)的位寬對運(yùn)算結(jié)果的精度有很大的影響。YU Y H在文獻(xiàn)[9]中提出了解決量化誤差(OQE)的方法,。
YU Y H指出OQE由近似誤差和舍入誤差組成,。近似誤差是由有限個確定旋轉(zhuǎn)角度量化CORDIC旋轉(zhuǎn)角度帶來的量化誤差，由最大向量模值和迭代次數(shù)決定,。舍入誤差是因?yàn)橛嬎銜r數(shù)據(jù)位不夠帶來的誤差,，由數(shù)據(jù)的位寬決定。
增加數(shù)據(jù)位寬和迭代的次數(shù)都可以提高運(yùn)算結(jié)果的精度,。但是,，當(dāng)?shù)螖?shù)達(dá)到一定值后，迭代次數(shù)的增加對運(yùn)算精度的影響變得很小,。而增加運(yùn)算數(shù)據(jù)的位寬將帶來較好的效果,，大幅度降低舍入誤差。每增加一位數(shù)據(jù)位寬,，舍入誤差將變小1/2[9],。本文在用CORDIC算法實(shí)現(xiàn)式(2)時，在保證較大的迭代次數(shù)的前提下,，將運(yùn)算數(shù)據(jù)位擴(kuò)展3位,，大幅度降低了舍入誤差,。
在進(jìn)行數(shù)據(jù)迭代運(yùn)算時，考慮到采用浮點(diǎn)數(shù)可以降低工作頻率,，因此采用了定點(diǎn)數(shù),。如圖5所示，定點(diǎn)數(shù)由符號位(S),、整數(shù)位(I),、小數(shù)位(D)構(gòu)成。
3.3 優(yōu)化后CORDIC算法的實(shí)現(xiàn)
圓周模式下的向量模式可以根據(jù)輸入的|Px|和|Py|,，直接求解出最終梯度的模值,。梯度模值運(yùn)算模塊的硬件結(jié)構(gòu)圖如圖6所示，由預(yù)處理,、CORDIC迭代流水線,、后級處理3部分組成。預(yù)處理部分中,，將判斷|Px|和|Py|的值是否需要互換,。因?yàn)榈螖?shù)已經(jīng)提前確定，縮放因子已知,，在預(yù)處理階段的數(shù)值修正部分可以提前對最終結(jié)果進(jìn)行補(bǔ)償,。補(bǔ)償后，將數(shù)據(jù)位數(shù)從24位擴(kuò)展成27位,。擴(kuò)展后,，舍入誤差將降低為之前的1/8，提高了運(yùn)算的精確度,。
預(yù)處理后進(jìn)入CORDIC迭代部分,，迭代部分采用15級的流水線模式。根據(jù)式(3)可知,，在求解式(2)時只需要知道|Px|和|Py|的值,，因此可舍棄zi的計算，以此節(jié)約一些資源,。如圖7所示,，迭代部分的每行存在兩個移位寄存器和兩個加/減法器。符號控制信號為Sign,，由yi決定,。通過式(3)可知，當(dāng)yi為正時,，xi處選用加法器,，yi處選用減法器；當(dāng)yi為負(fù)時,，xi處選用減法器,，yi處選用加法器,。
數(shù)據(jù)通過迭代部分后，進(jìn)入后級處理部分,。后級處理部分將信號緩存一拍后,，進(jìn)行截位處理，然后就可得到x15[26:3]的值,，即最終梯度的模值。此外,，該設(shè)計采用了流水線結(jié)構(gòu),，提高了吞吐量和最大工作頻率。
4 系統(tǒng)仿真及性能分析
本設(shè)計在ISE14.7軟件下,，用Verilog HDL語言進(jìn)行了實(shí)現(xiàn),。此外，使用MATLAB,、Modelsim SE 10.1c進(jìn)行了本設(shè)計的測試,。
本文在Xilinx ISE編譯器中編譯好代碼后，通過Modelsim進(jìn)行了軟件仿真,。圖8為本設(shè)計關(guān)鍵路徑的仿真：CORDIC迭代運(yùn)算的仿真,。修正后的|Px|和|Py|采用定點(diǎn)數(shù)的方法進(jìn)行表示，總計24位,，0～12位為小數(shù)位,，13～22位為整數(shù)位，23位為符號位,。|Px[26:0]|和|Py[26:0]|為|Px|,、|Py|擴(kuò)展3位后的值，分別用x,、y進(jìn)行表示,。Kn為最終梯度模值的計算結(jié)果。為了更直觀地表示,，輸入值,、中間值和輸出結(jié)果均用有符號十進(jìn)制數(shù)進(jìn)行表示。根據(jù)仿真結(jié)果可知,，采用優(yōu)化后的CORDIC進(jìn)行式(2)的運(yùn)算,，精確度約為10-4，遠(yuǎn)大于文獻(xiàn)[8]的精確度,。
仿真后,，將文獻(xiàn)[8]的算法和本文的算法進(jìn)行了對比測試，結(jié)果如圖9所示,。通過圖9(b)可以觀察到,，使用文獻(xiàn)[8]的加速算法后,，因?yàn)榫_度較低的緣故，不能較好地檢測到邊緣,，人像左下方,、右上方處的頭發(fā)邊緣和背景混雜在了一起，人像面部左下方,、右上方的邊緣檢測效果較差,。使用本文的改進(jìn)算法后，如圖9(c)所示,，在保證運(yùn)算速度的前提下,，較好地識別出了圖像的邊緣，較好地檢測出了頭發(fā)和面部的邊緣,，與圖9(d)使用MATLAB實(shí)現(xiàn)Sobel算法的效果近似,。
本文也嘗試使用Xilinx ISE自帶的平方根IP核實(shí)現(xiàn)關(guān)鍵路徑的計算。選用Spartan6 XC6SLX16 2CSG324C芯片在Xilinx ISE14.7軟件平臺下,，對平方根IP核進(jìn)行編譯綜合,。編譯綜合后，得到ISE計算出的最高工作頻率信息,。為測試本文使用算法的性能,，在同樣的條件下，對本文的算法也進(jìn)行了編譯,，得到了最高工作頻率信息,。最終結(jié)果如表1所示。采用IP核進(jìn)行關(guān)鍵路徑的計算,，最高工作頻率為114.745 MHz,。采用優(yōu)化后的CORDIC算法進(jìn)行關(guān)鍵路徑的計算，最高頻率為187.652 MHz,。相比使用IP核的方法,，采用優(yōu)化后的CORDIC算法實(shí)現(xiàn)關(guān)鍵路徑的計算可以提速63.53％。
5 結(jié)論
本文在傳統(tǒng)Sobel加速算法的基礎(chǔ)上,，在FPGA平臺上使用優(yōu)化的CORDIC算法實(shí)現(xiàn)了Sobel算法加速,。通過圖9可知，該方法的邊緣檢測效果良好,，較好地檢測出了圖像的邊緣,。通過表1可知，該方法與調(diào)用IP核相比提高了百分之63.53％的工作頻率,。實(shí)驗(yàn)結(jié)果表明,，本設(shè)計進(jìn)一步提高了系統(tǒng)的運(yùn)算速度，適合在對速度有較高要求的系統(tǒng)中使用。
參考文獻(xiàn)
[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] 于莉潔，孫瑜亮,，繆永偉.基于深度信息局部二值模式特征的室內(nèi)場景邊緣檢測[J].計算機(jī)輔助設(shè)計與圖形學(xué)學(xué)報，2017,，29(12)：2162-2170.
[4] 劉小寧,，謝宜壯，陳禾,，等.CORDIC算法的優(yōu)化及實(shí)現(xiàn)[J].北京理工大學(xué)學(xué)報,，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圖像邊沿檢測算法的優(yōu)化設(shè)計與實(shí)現(xiàn)[J].電子技術(shù)應(yīng)用,，2016,，42(3)：71-73.
[7] 楊新華，寇為剛.基于FPGA的Sobel算子圖像邊緣檢測算法[J].儀表技術(shù)與傳感器,，2013(1)：102-104.
[8] 杜正聰,，寧龍飛.基于Sobel算法圖像邊緣檢測的FPGA實(shí)現(xiàn)[J].電子技術(shù)應(yīng)用，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.
作者信息:
黃 虎,，楊 丁,，雷宇輝，謝佳訊，陳詩瑤,，鄒 瑜
(成都理工大學(xué) 信息科學(xué)與技術(shù)學(xué)院,，四川 成都610059）