張 波，韓俊剛

(西安郵電大學(xué) 計(jì)算機(jī)學(xué)院，陜西 西安 710121)

基于SDSoC的SIFT特征點(diǎn)檢測(cè)

張 波，韓俊剛

(西安郵電大學(xué) 計(jì)算機(jī)學(xué)院，陜西 西安 710121)

為了在嵌入式機(jī)器視覺(jué)處理系統(tǒng)中能夠快速提取圖像的特征點(diǎn)，完成圖像匹配與物體識(shí)別等操作，提出了一種在全可編程器件上實(shí)現(xiàn)的SIFT(Scale Invariant Feature Transform)算法。該算法使用SDSoC開(kāi)發(fā)環(huán)境，采用PS(Processing System)和PL(Programmable Logic)協(xié)同開(kāi)發(fā)策略，通過(guò)流水線優(yōu)化、軟硬件并行和重構(gòu)算法順序等方法對(duì)算法進(jìn)行優(yōu)化。對(duì)多幅QVGA分辨率圖像進(jìn)行了處理，結(jié)果表明軟硬件協(xié)同開(kāi)發(fā)的策略能夠有效提高算法性能，同時(shí)能保留較多特征點(diǎn)。該算法生成的特征點(diǎn)在尺度變換、旋轉(zhuǎn)和縮放的情況下均能得到良好的匹配效果。與現(xiàn)有使用軟件實(shí)現(xiàn)的SIFT方案相比，具有一定的實(shí)時(shí)性，滿足了在嵌入式領(lǐng)域的應(yīng)用需求。

SIFT;SDSoC;軟硬件協(xié)同;FPGA

0 引 言

特征點(diǎn)檢測(cè)算法在物體識(shí)別、全景圖拼接、機(jī)器人導(dǎo)航等領(lǐng)域已經(jīng)得到了廣泛應(yīng)用。在實(shí)際應(yīng)用中想要在不同的尺度空間、視角中識(shí)別出相同的物體，這需要特征點(diǎn)具有可重現(xiàn)與精準(zhǔn)的特性。SIFT算法[1]正是具有較好效果的檢測(cè)算法之一，但其在應(yīng)用中有一個(gè)較大的缺點(diǎn)是計(jì)算量較大，實(shí)時(shí)性比SURF、Harris及FAST等算法有所不足。

為實(shí)現(xiàn)SIFT特征檢測(cè)算法在嵌入式設(shè)備中的應(yīng)用，文中使用軟硬協(xié)同的策略，并采用一系列方法對(duì)算法進(jìn)行加速。目前業(yè)內(nèi)已經(jīng)出現(xiàn)了一些軟硬件協(xié)同開(kāi)發(fā)環(huán)境,如可以使嵌入式開(kāi)發(fā)人員充分利用“全可編程”(All Programmable)器件[2]功能的SDSoC開(kāi)發(fā)環(huán)境[3]。SDSoC開(kāi)發(fā)環(huán)境提供的類C/C++開(kāi)發(fā)語(yǔ)言環(huán)境能夠使期望被加速的函數(shù)自動(dòng)轉(zhuǎn)換為與系統(tǒng)連接的硬件。

文獻(xiàn)[4]提出了與文中類似策略的基于HLS(High-level Synthesis)的SURF算法，其實(shí)驗(yàn)結(jié)果表明，基于HLS的SURF算法提速明顯，但是HLS生成的IP核無(wú)法被C語(yǔ)言直接調(diào)用，導(dǎo)致開(kāi)發(fā)靈活性不足；而文中使用的SDSoC開(kāi)發(fā)環(huán)境能夠自動(dòng)生成C語(yǔ)言可調(diào)用的RTL庫(kù)，簡(jiǎn)化了開(kāi)發(fā)流程。文獻(xiàn)[5]中提出的完全基于FPGA的SIFT算法在256×256的分辨率下具有良好的實(shí)時(shí)性，可見(jiàn)使用FPGA是一種有效的加速方法。

1 算法介紹及選擇加速部分

為了使圖像特征點(diǎn)具有旋轉(zhuǎn)、平移和尺度不變的特性，SIFT特征點(diǎn)檢測(cè)算法需要進(jìn)行大量計(jì)算。文獻(xiàn)[1]中將該算法分為4步：

(1)尺度空間極值檢測(cè)；

(2)特征點(diǎn)定位；

(3)方向賦值；

(4)特征點(diǎn)描述。

其中，最耗時(shí)的部分是尺度空間極值檢測(cè)[6]。

尺度空間極值檢測(cè)是掃描圖像尺度空間內(nèi)的所有點(diǎn)，并尋找潛在的特征點(diǎn)。其首先要做的是構(gòu)建尺度空間。

L(x,y,σ)=G(x,y,σ)*I(x,y)

(1)

(2)

其中，x,y表示像素所在行和列的位置；σ表示尺度坐標(biāo)；I(x,y)表示輸入圖像坐標(biāo)處的值；G(x,y,σ)表示尺度可變高斯函數(shù)。

對(duì)高斯卷積后的圖像做差得高斯差分尺度空間。

D(x,y,σ)=L(x,y,kσ)-L(x,y,σ)

(3)

在算法中，高斯卷積是影響算法性能的關(guān)鍵因素，因此這部分操作適合使用運(yùn)算性能較高的PL進(jìn)行加速，以此來(lái)提高算法的整體性能。

根據(jù)文獻(xiàn)[6]，算法中方向賦值和特征點(diǎn)描述這兩部分對(duì)算法的性能也有較大影響。由于在這兩部分中需要隨機(jī)訪問(wèn)卷積數(shù)據(jù)，為減少數(shù)據(jù)的傳輸量，將其放在PS端進(jìn)行處理。但是這兩部分都需要使用圖像的梯度，故把梯度計(jì)算模塊使用PL進(jìn)行加速。

2 算法的SDSoC實(shí)現(xiàn)

SDSoC開(kāi)發(fā)環(huán)境提供了高度簡(jiǎn)化，類似ASSP C/C++的開(kāi)發(fā)環(huán)境，讓軟件開(kāi)發(fā)人員能夠充分利用可編程邏輯對(duì)軟件進(jìn)行加速。其提供的系統(tǒng)級(jí)的特性描述能夠進(jìn)行快速系統(tǒng)評(píng)估，全系統(tǒng)優(yōu)化的編譯器可以幫助開(kāi)發(fā)人員生成最佳系統(tǒng)連接，快速完成架構(gòu)配置[3]。

文中使用的硬件環(huán)境有較豐富的板載資源，其在PS端提供了ARM Cortex-A9處理器，512 MB DDR3內(nèi)存和外部存儲(chǔ)接口。這使其可以運(yùn)行Linux等操作系統(tǒng)，為應(yīng)用的開(kāi)發(fā)提供了平臺(tái)。同時(shí)在PL端也提供了豐富的邏輯資源，利用系統(tǒng)內(nèi)部的AXI HP總線可以快速交換數(shù)據(jù)，使得PS和PL端可以做到協(xié)同開(kāi)發(fā)。

在設(shè)計(jì)中，圖像數(shù)據(jù)從PS端獲得，轉(zhuǎn)換為灰度圖像后，傳入PL端高斯卷積模塊進(jìn)行計(jì)算，計(jì)算完成后直接傳入梯度求值模塊進(jìn)行計(jì)算，同時(shí)傳入PS端構(gòu)造DoG(Difference of Gauss)尺度空間，接著檢測(cè)以及過(guò)濾極值點(diǎn)。隨后再根據(jù)梯度值和梯度方向分配特征點(diǎn)的主方向與描述特征點(diǎn)。算法流程如圖1所示。

圖1 SIFT算法流程圖

2.1 PL端高斯卷積模塊實(shí)現(xiàn)

對(duì)圖像數(shù)據(jù)流進(jìn)行處理時(shí)，最大的瓶頸在于訪問(wèn)存儲(chǔ)和緩存。在高斯卷積的過(guò)程中，被處理的圖像數(shù)據(jù)按照流的方式傳入計(jì)算單元，計(jì)算單元在計(jì)算完數(shù)據(jù)后存入輸出緩沖區(qū)。因?yàn)榫矸e過(guò)程需要訪問(wèn)圖像的局部數(shù)據(jù)，并且對(duì)每個(gè)被處理的數(shù)據(jù)不止訪問(wèn)一次，故PL端的存儲(chǔ)結(jié)構(gòu)需要能夠?qū)?shù)據(jù)進(jìn)行多次訪問(wèn)，但PL端存儲(chǔ)資源有限，所以PL端的存儲(chǔ)結(jié)構(gòu)需要保證在正確訪問(wèn)數(shù)據(jù)的情況下盡可能少的占用資源。

一個(gè)有效的方法是采用行緩沖區(qū)(line buffer)和滑窗(window buffer)的組合[7-8]。圖2展示了采用滑窗思想如何進(jìn)行卷積操作。行緩沖區(qū)可存放7行圖像數(shù)據(jù)，使用7×7大小的滑窗來(lái)存儲(chǔ)局部數(shù)據(jù)。首先讀取圖像數(shù)據(jù)存入行緩沖區(qū)中，每次存放時(shí)行緩沖區(qū)中已經(jīng)存在的數(shù)據(jù)按照列對(duì)齊方式上移一位；接著每一次滑窗都需從左向右滑動(dòng)一列，根據(jù)行緩沖區(qū)的最新數(shù)據(jù)進(jìn)行更新，最終從數(shù)據(jù)流中得到一個(gè)7×7的滑窗。因SIFT會(huì)舍棄圖像邊緣的特征點(diǎn)，故本文在處理圖像邊緣數(shù)據(jù)時(shí)直接賦值填充，以減小計(jì)算量。

圖2 卷積操作過(guò)程中的行緩沖區(qū)和滑窗

在滑窗中的局部數(shù)據(jù)確定后就可以進(jìn)行圖像數(shù)據(jù)的卷積操作。不同值的高斯核，每組圖像只需使用一次，為節(jié)省PL端資源，將高斯核放在PS端求得。將每次得到的滑窗中的數(shù)據(jù)進(jìn)行卷積操作后傳出，就得到所需要的卷積后的圖像。生成完本組數(shù)據(jù)，對(duì)本組第3幅圖像進(jìn)行下采樣操作，得到下一組輸入數(shù)據(jù)，最終通過(guò)多次調(diào)用高斯卷積模塊生成高斯金字塔。

2.2 高斯卷積SDSoC優(yōu)化

在高斯模糊的過(guò)程中需要對(duì)圖像的局部像素進(jìn)行循環(huán)處理。為更進(jìn)一步優(yōu)化性能，使用SDSoC中提供的循環(huán)優(yōu)化指令。在高斯卷積主循環(huán)中使用優(yōu)化指令的偽代碼如下：

for(int row=0;row

{

for(int col=0;col

{

#pragma AP PIPELINE II=1

// processing code

}

}

在沒(méi)有使用循環(huán)優(yōu)化指令的情況下，每次迭代都會(huì)使用相同的硬件狀態(tài)和資源。假設(shè)自增操作需要1個(gè)時(shí)鐘周期，那么完整的循環(huán)至少有Rows×Cols個(gè)時(shí)鐘的執(zhí)行時(shí)延。使用AP PIPELINE優(yōu)化指令能有效減少時(shí)延，提高性能。指令中“II”代表新循環(huán)開(kāi)始之前的延時(shí)時(shí)鐘數(shù)[9]。

在計(jì)算卷積時(shí)，也需要對(duì)滑窗內(nèi)的數(shù)據(jù)進(jìn)行循環(huán)訪問(wèn)。使用SDSoC的APUNROLL指令對(duì)內(nèi)部循環(huán)進(jìn)行優(yōu)化，這樣能同時(shí)執(zhí)行7個(gè)浮點(diǎn)乘法運(yùn)算，提高了并行性。

為保證PS和PL兩端的傳輸性能，在PS端申請(qǐng)圖像緩沖區(qū)時(shí)使用SDSoC開(kāi)發(fā)環(huán)境中的sds_alloc函數(shù)，其可以為緩沖區(qū)分配連續(xù)的物理地址作為存儲(chǔ)空間，而物理地址連續(xù)的數(shù)據(jù)在傳輸?shù)倪^(guò)程只需很少的開(kāi)銷。在硬件函數(shù)聲明時(shí)需要指出圖像數(shù)據(jù)為流數(shù)據(jù)，另外還需要指出傳輸數(shù)據(jù)的長(zhǎng)度，以便支持不同尺寸的圖像。上述操作可以使用如下指令：

#pragma SDS data 〗zero_copy(gInPixs[0:rows*cols])

#pragma SDS data〗zero_copy(gOutPixs[0:rows*cols])

#pragma SDS data〗access_pattern(gInPixs:SEQUENTIAL)

#pragma SDS dataaccess_pattern(gOutPixs:SEQUENTIAL)。

2.3 梯度求值模塊

梯度求值模塊的存儲(chǔ)方法與高斯卷積模塊類似，只是滑窗區(qū)域更小。求梯度時(shí)需要分別計(jì)算梯度模值和梯度方向，公式如下：

m(x,y)=((L(x+1,y)-L(x-1,y))2+ (L(x,y+1)-L(x,y-1))2)1/2

(4)

θ(x,y)=arctan((L(x,y+1)-L(x,y- 1))/(L(x+1,y)-L(x-1,y)))

(5)

由求梯度公式可知，求值時(shí)需要大小為3×3的滑窗就可完成，同時(shí)行緩沖區(qū)變?yōu)榭纱娣?行圖像數(shù)據(jù)即可。

由于SDSoC編譯鏈支持PL端函數(shù)之間的數(shù)據(jù)直接傳輸，無(wú)需再經(jīng)過(guò)PS[10]。同時(shí)SIFT算法需要高斯模糊后圖像的梯度，文中在PL端進(jìn)行高斯卷積后直接將數(shù)據(jù)傳入梯度求值模塊，這樣不僅減少了數(shù)據(jù)傳輸量，而且由于高斯卷積耗時(shí)是梯度求值的3倍，直接連接后的性能與單獨(dú)的高斯卷積模塊性能相當(dāng)。

2.4 特征點(diǎn)定位

在PS端，獲取每組相鄰的兩個(gè)經(jīng)過(guò)高斯模糊處理的圖像就可以得到差分?jǐn)?shù)據(jù)。特征點(diǎn)定位時(shí)需要3層差分?jǐn)?shù)據(jù)，文中算法構(gòu)造高斯金字塔時(shí)每組會(huì)生成5層圖像數(shù)據(jù)。由于高斯卷積、圖像差分和極值檢測(cè)分別在PL端和PS端實(shí)現(xiàn)，在高斯卷積模塊對(duì)第3層圖像進(jìn)行卷積計(jì)算的同時(shí)可以對(duì)前2層已經(jīng)卷積處理過(guò)的圖像進(jìn)行差分。當(dāng)差分圖像有3層后就可以進(jìn)行特征點(diǎn)定位操作。為使軟、硬件函數(shù)同時(shí)執(zhí)行，文中使用了同步指令對(duì)極值檢測(cè)部分進(jìn)行優(yōu)化。

當(dāng)CPU對(duì)高斯卷積的操作做好數(shù)據(jù)傳輸準(zhǔn)備，硬件開(kāi)始工作后，SDSoC的async指令會(huì)交還CPU控制權(quán)，繼續(xù)執(zhí)行PS端任務(wù)，而wait指令是等待硬件函數(shù)完成操作。文中在PL端函數(shù)執(zhí)行前添加async指令，在差分和特征點(diǎn)定位后執(zhí)行wait指令[10]，這樣就增加了系統(tǒng)的并行性，提高了算法效率。方向賦值和描述特征點(diǎn)部分在文獻(xiàn)[11]中實(shí)現(xiàn)，這里不再敘述。需要說(shuō)明的是方向賦值和特征點(diǎn)描述時(shí)使用的梯度直接從PL端計(jì)算結(jié)果中獲取。

3 實(shí)驗(yàn)分析

文中使用基于Zynq7000系列的Zedboard開(kāi)發(fā)板作為硬件環(huán)境，其板載XC7Z020 CLG484-1 EEP芯片[12]提供了可編程邏輯陣列單元。求得的特征點(diǎn)描述存儲(chǔ)在SD卡中，然后使用臺(tái)式計(jì)算機(jī)進(jìn)行匹配操作。圖3展示了文中算法在尺度變換、模糊和旋轉(zhuǎn)情況下的匹配情況。圖中圖像的特征描述均使用文中算法，在PC端進(jìn)行匹配。通過(guò)觀察可以發(fā)現(xiàn)在尺度變化旋轉(zhuǎn)以及縮放的情況下依舊能夠較好地匹配特征點(diǎn)，達(dá)到了應(yīng)用需求。

3.1 性能分析

算法使用QVGA分辨率的圖像作為輸入，算法參數(shù)取O=4，S=3，threshold=0.04，r=10.0，高斯卷積模板為7×7。表1展示了文中算法與其他基于軟件實(shí)現(xiàn)或基于FPGA實(shí)現(xiàn)算法的性能對(duì)比。

從表1可以看出，文中算法特征點(diǎn)個(gè)數(shù)較多，與文獻(xiàn)[5]算法相比，在尺度變換、旋轉(zhuǎn)的情況下依然保持了較高的匹配率，但性能不及FPGA平臺(tái)實(shí)現(xiàn)的SIFT算法，與文獻(xiàn)[13]中軟件實(shí)現(xiàn)的算法相比速度提高了70倍。文中算法為保證較高的匹配率，保留了較多的特征點(diǎn)，造成PS端進(jìn)行極值檢測(cè)、特征點(diǎn)過(guò)濾和特征點(diǎn)描述時(shí)需要花費(fèi)較多的時(shí)間?？傮w來(lái)看文中算法具有一定的實(shí)時(shí)性，就嵌入式領(lǐng)域來(lái)說(shuō)已經(jīng)達(dá)到了應(yīng)用的需求。

圖3 尺度變換、旋轉(zhuǎn)、縮放圖像匹配圖

比較項(xiàng)圖像尺寸特征點(diǎn)數(shù)速度/(幀/s)文中算法QVGA34321軟件算法[13]QVGA590.30文獻(xiàn)[14]算法QVGA-30文獻(xiàn)[5]算法256×2567337

3.2 PL端資源占用分析

SDSoC是針對(duì)軟件人員開(kāi)發(fā)硬件的開(kāi)發(fā)環(huán)境，它使得軟件工程師也能夠充分利用可編程邏輯的性能優(yōu)勢(shì)，且擁有較短的開(kāi)發(fā)流程。表2展示了PL端高斯卷積模塊和梯度模塊的資源占用。由于每個(gè)模塊都采用了SDSoC循環(huán)優(yōu)化指令，PL端資源得到充分利用。

表2 FPGA資源占用表

4 結(jié)束語(yǔ)

文中使用SDSoC開(kāi)發(fā)環(huán)境在Zedboard平臺(tái)上實(shí)現(xiàn)了SIFT特征檢測(cè)算法。實(shí)驗(yàn)結(jié)果表明，算法在QVGA分辨率下速度達(dá)到了21 幀/s，與完全使用軟件實(shí)現(xiàn)的算法相比性能有了較大提高，并具有一定的實(shí)時(shí)性。使用高斯卷積模塊和梯度計(jì)算模塊直連的方法，提高了并行性。同時(shí)采用的軟硬協(xié)同開(kāi)發(fā)策略充分發(fā)揮了平臺(tái)性能，而且也方便了未來(lái)應(yīng)用的開(kāi)發(fā)。

[1] Lowe D G. Distinctive image features from scale-invariant keypoints[J].International Journal of Computer Vision,2004,60(2):91-110.

[2] Xilinx.Zynq architecture[EB/OL].[2016-01-26].http://www.ioe.nchu.edu.tw/Pic/CourseItem/4468_20_Zynq_Architecture.pdf.

[3] Xilinx.SDSoC development environment[EB/OL].[2016-01-26].http://china.xilinx.com/products/design-tools/software-zone/sdsoc.html.

[4] 丁帥帥,柴志雷.基于HLS的SURF特征提取硬件加速單元設(shè)計(jì)與實(shí)現(xiàn)[J].微電子學(xué)與計(jì)算機(jī),2015,32(9):133-137.

[5] 李木國(guó),孫慧濤,杜 海.一種基于FPGA的尺度不變特征轉(zhuǎn)換算法[J].系統(tǒng)仿真學(xué)報(bào),2014,26(5):1071-1077.

[6] Wu Changchang.SiftGPU:a GPU implementation of scale invariant feature transform (SIFT)[EB/OL].[2016-01-18].http://www.cs.unc.edu/～ccwu/siftgpu/.

[7] Abdelgawad H M,Safar M,Wahba A M.High level synthesis of canny edge detection algorithm on Zynq platform[J].Journal of Computer,Electrical,Automation,Control and Information Engineering,2015,9(1):148-152.

[8] Chati H D,Muhlbauer F,Braun T,et al.Hardware/software co-design of a key point detector on FPGA[C]//15th annual IEEE symposium on field-programmable custom computing machines.[s.l.]:IEEE,2007:355-356.

[9] Xilinx. Vivado design suite user guide:high-level synthesis[EB/OL].[2016-02-13].http://www.xilinx.com/support/documentation/sw_manuals/xilinx2015_4/ug902-vivado-high-level-synthesis.pdf.

[10] Xilinx.SDSoC environment user guide[EB/OL].[2016-01-26].http://www.xilinx.com/support/documentation/sw_manuals/xilinx2015_4/ug1027-sdsoc-user-guide.pdf.

[11] Vedaldi A.An open implementation of the SIFT detector and descriptor[R].[s.l.]:[s.n.],2006.

[12] Avnet Inc.ZedBoard (ZynqTMevaluation and development) hardware user’s guide[EB/OL].[2016-01-27].http://www.zedboard.org/sites/default/files/documentations/ZedBoard_HW_UG_v2_2.pdf.

[13] 陸愷立,耿俊梅,顧國(guó)華,等.SIFT特征提取算法的FPGA實(shí)時(shí)實(shí)現(xiàn)[J].電視技術(shù),2014,38(13):54-58.

[14] Bonato V,Marques E,Constantinides G.A parallel hardware architecture for scale and rotation invariant feature detection[J].IEEE Transactions on Circuits and Systems for Video Technology,2008,18(12):1703-1712.

Scale Invariant Feature Transform Algorithm Based on SDSoC

ZHANG Bo，HAN Jun-gang

(School of Computer and Technology,Xi’an University of Posts and Telecommunications,Xi’an 710121,China)

In order to extract image feature points in embedded machine vision system quickly and complete operations such as image matching and object recognition,a SIFT (Scale Invariant Feature Transform) algorithm is put forward on an all programmable device.It uses SDSoC environment and PS (Processing System) and PL (Programmable Logic) co-design strategy,and is optimized through the pipeline optimization,parallel hardware and software and reconstruction of algorithm sequence.Images of QVGA resolution are processed,and the results show that the methodology of hardware and software co-design can effectively improve performance of SIFT algorithm,while retaining many feature points.This algorithm generates the feature points to match well under the condition of the scale transform,rotation and scaling.Compared with the existing implementation of SIFT by software,the performance of real-time meets the application requirements in the embedded field.

SIFT;SDSoC;co-design of software and hardware;FPGA

2016-02-02

2016-06-09

時(shí)間：2016-11-21

國(guó)家自然科學(xué)基金重大項(xiàng)目(61136002)

張 波(1989-)，男，碩士研究生,研究方向?yàn)閳D像處理;韓俊剛，教授,研究方向?yàn)檐浖陀布男问交?yàn)證、圖形處理器和新型計(jì)算機(jī)體系結(jié)構(gòu)。

http://www.cnki.net/kcms/detail/61.1450.TP.20161121.1641.030.html

TP391

A

1673-629X(2016)12-0103-04

10.3969/j.issn.1673-629X.2016.12.023