基于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