基于SDSoC的SIFT特征點檢測

張 波，韓俊剛

(西安郵電大學 計算機學院，陜西 西安 710121)

基于SDSoC的SIFT特征點檢測

張 波，韓俊剛

(西安郵電大學 計算機學院，陜西 西安 710121)

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

SIFT;SDSoC;軟硬件協同;FPGA

0 引 言

特征點檢測算法在物體識別、全景圖拼接、機器人導航等領域已經得到了廣泛應用。在實際應用中想要在不同的尺度空間、視角中識別出相同的物體，這需要特征點具有可重現與精準的特性。SIFT算法[1]正是具有較好效果的檢測算法之一，但其在應用中有一個較大的缺點是計算量較大，實時性比SURF、Harris及FAST等算法有所不足。

為實現SIFT特征檢測算法在嵌入式設備中的應用，文中使用軟硬協同的策略，并采用一系列方法對算法進行加速。目前業內已經出現了一些軟硬件協同開發環境,如可以使嵌入式開發人員充分利用“全可編程”(All Programmable)器件[2]功能的SDSoC開發環境[3]。SDSoC開發環境提供的類C/C++開發語言環境能夠使期望被加速的函數自動轉換為與系統連接的硬件。

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

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

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

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

(2)特征點定位；

(3)方向賦值；

(4)特征點描述。

其中，最耗時的部分是尺度空間極值檢測[6]。

尺度空間極值檢測是掃描圖像尺度空間內的所有點，并尋找潛在的特征點。其首先要做的是構建尺度空間。

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

(1)

(2)

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

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

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

(3)

在算法中，高斯卷積是影響算法性能的關鍵因素，因此這部分操作適合使用運算性能較高的PL進行加速，以此來提高算法的整體性能。

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

2 算法的SDSoC實現

SDSoC開發環境提供了高度簡化，類似ASSP C/C++的開發環境，讓軟件開發人員能夠充分利用可編程邏輯對軟件進行加速。其提供的系統級的特性描述能夠進行快速系統評估，全系統優化的編譯器可以幫助開發人員生成最佳系統連接，快速完成架構配置[3]。

文中使用的硬件環境有較豐富的板載資源，其在PS端提供了ARM Cortex-A9處理器，512 MB DDR3內存和外部存儲接口。這使其可以運行Linux等操作系統，為應用的開發提供了平臺。同時在PL端也提供了豐富的邏輯資源，利用系統內部的AXI HP總線可以快速交換數據，使得PS和PL端可以做到協同開發。

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

圖1 SIFT算法流程圖

2.1 PL端高斯卷積模塊實現

對圖像數據流進行處理時，最大的瓶頸在于訪問存儲和緩存。在高斯卷積的過程中，被處理的圖像數據按照流的方式傳入計算單元，計算單元在計算完數據后存入輸出緩沖區。因為卷積過程需要訪問圖像的局部數據，并且對每個被處理的數據不止訪問一次，故PL端的存儲結構需要能夠對數據進行多次訪問，但PL端存儲資源有限，所以PL端的存儲結構需要保證在正確訪問數據的情況下盡可能少的占用資源。

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

圖2 卷積操作過程中的行緩沖區和滑窗

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

2.2 高斯卷積SDSoC優化

在高斯模糊的過程中需要對圖像的局部像素進行循環處理。為更進一步優化性能，使用SDSoC中提供的循環優化指令。在高斯卷積主循環中使用優化指令的偽代碼如下：

for(int row=0;row

{

for(int col=0;col

{

#pragma AP PIPELINE II=1

// processing code

}

}

在沒有使用循環優化指令的情況下，每次迭代都會使用相同的硬件狀態和資源。假設自增操作需要1個時鐘周期，那么完整的循環至少有Rows×Cols個時鐘的執行時延。使用AP PIPELINE優化指令能有效減少時延，提高性能。指令中“II”代表新循環開始之前的延時時鐘數[9]。

在計算卷積時，也需要對滑窗內的數據進行循環訪問。使用SDSoC的APUNROLL指令對內部循環進行優化，這樣能同時執行7個浮點乘法運算，提高了并行性。

為保證PS和PL兩端的傳輸性能，在PS端申請圖像緩沖區時使用SDSoC開發環境中的sds_alloc函數，其可以為緩沖區分配連續的物理地址作為存儲空間，而物理地址連續的數據在傳輸的過程只需很少的開銷。在硬件函數聲明時需要指出圖像數據為流數據，另外還需要指出傳輸數據的長度，以便支持不同尺寸的圖像。上述操作可以使用如下指令：

#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 梯度求值模塊

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

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)

由求梯度公式可知，求值時需要大小為3×3的滑窗就可完成，同時行緩沖區變為可存放3行圖像數據即可。

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

2.4 特征點定位

在PS端，獲取每組相鄰的兩個經過高斯模糊處理的圖像就可以得到差分數據。特征點定位時需要3層差分數據，文中算法構造高斯金字塔時每組會生成5層圖像數據。由于高斯卷積、圖像差分和極值檢測分別在PL端和PS端實現，在高斯卷積模塊對第3層圖像進行卷積計算的同時可以對前2層已經卷積處理過的圖像進行差分。當差分圖像有3層后就可以進行特征點定位操作。為使軟、硬件函數同時執行，文中使用了同步指令對極值檢測部分進行優化。

當CPU對高斯卷積的操作做好數據傳輸準備，硬件開始工作后，SDSoC的async指令會交還CPU控制權，繼續執行PS端任務，而wait指令是等待硬件函數完成操作。文中在PL端函數執行前添加async指令，在差分和特征點定位后執行wait指令[10]，這樣就增加了系統的并行性，提高了算法效率。方向賦值和描述特征點部分在文獻[11]中實現，這里不再敘述。需要說明的是方向賦值和特征點描述時使用的梯度直接從PL端計算結果中獲取。

3 實驗分析

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

3.1 性能分析

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

從表1可以看出，文中算法特征點個數較多，與文獻[5]算法相比，在尺度變換、旋轉的情況下依然保持了較高的匹配率，但性能不及FPGA平臺實現的SIFT算法，與文獻[13]中軟件實現的算法相比速度提高了70倍。文中算法為保證較高的匹配率，保留了較多的特征點，造成PS端進行極值檢測、特征點過濾和特征點描述時需要花費較多的時間。總體來看文中算法具有一定的實時性，就嵌入式領域來說已經達到了應用的需求。

圖3 尺度變換、旋轉、縮放圖像匹配圖

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

3.2 PL端資源占用分析

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

表2 FPGA資源占用表

4 結束語

文中使用SDSoC開發環境在Zedboard平臺上實現了SIFT特征檢測算法。實驗結果表明，算法在QVGA分辨率下速度達到了21 幀/s，與完全使用軟件實現的算法相比性能有了較大提高，并具有一定的實時性。使用高斯卷積模塊和梯度計算模塊直連的方法，提高了并行性。同時采用的軟硬協同開發策略充分發揮了平臺性能，而且也方便了未來應用的開發。

[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特征提取硬件加速單元設計與實現[J].微電子學與計算機,2015,32(9):133-137.

[5] 李木國,孫慧濤,杜 海.一種基于FPGA的尺度不變特征轉換算法[J].系統仿真學報,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] 陸愷立,耿俊梅,顧國華,等.SIFT特征提取算法的FPGA實時實現[J].電視技術,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

時間：2016-11-21

國家自然科學基金重大項目(61136002)

張 波(1989-)，男，碩士研究生,研究方向為圖像處理;韓俊剛，教授,研究方向為軟件和硬件的形式化驗證、圖形處理器和新型計算機體系結構。

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