SFM系统中的快速鲁棒特征提取算法研究

陈康平，刘而云

(浙江大学信息与电子工程学院，浙江 杭州 310027)

SFM系统中的快速鲁棒特征提取算法研究

陈康平，刘而云

(浙江大学信息与电子工程学院，浙江 杭州 310027)

介绍了典型运动恢复结构SFM系统的结构，分析了二维特征提取算法对系统的影响.针对SFM系统输入图像数量大、视角变化多的特点，提出了FASTX-DAISY快速特征提取算法.实验表明，与SIFT以及ORB-DAISY特征提取法比较，该方法不仅能提高SFM系统的重建效率，而且在视角发生较大变动时仍有较好的鲁棒性.

特征提取；运动恢复结构；快速特征

0 引 言

运动恢复结构(Structure From Motion, SFM)系统在近年来兴起的VR等相关技术中扮演了重要角色.其旨在利用目标在同一场景、不同视角下的二维图像，来还原目标的三维结构，还原的结构可以用三维点云(Point Cloud)数据来表示.以点云数据为基础做进一步分析和拟合，可以得到场景中直线和平面等更精细的结构，最终实现高质量的三维全景还原.

SFM系统输入的图像数量大而且视角变化多，传统的二维特征提取方法如SIFT(Scale-invariant Feature Transform)[1]缺乏对这种情形的应对.为此，本文结合了高效角点提取算法FAST(Features From Accelerated Segment Test, FAST)[2]和能良好适应视角变化的特征描述子DAISY(Dense descriptor Applied to wide-baseline Stereo, DAISY)[3]，提出了一种适用于SFM系统的快速特征提取算法——FASTX-DAISY.

1 典型的SFM系统架构

一个典型的SFM系统可以分成3个部分：二维特征提取、特征跟踪、多视角立体重建与优化.这3个部分前后依赖，组成了SFM系统三级流水线，如图1所示.

图1 SFM系统三级流水线

1.1 二维特征提取

早期的SFM系统采用区块匹配或是线匹配的方式来提取图像特征[4]，这种方式得到的结果非常粗糙，往往只是带二维表面贴图的三维结构.随着SIFT这类基于点的局部特征的出现[1]，SFM系统逐渐开始采用特征提取的方式来代替了原来的简单的线面匹配方式.

1.2 特征跟踪与多视角立体重建

基于点的局部特征是离散化并且无关联的二维特征，特征跟踪的目的是在多幅图像中建立相同特征的关联.然后，根据这些匹配关系，结合这些图像的视角几何约束，重建目标的三维信息.常用的重建方法有三角测量法和8点法，但二维匹配并非总是正确的，因此通常还会引入光束法平差等鲁棒性方法对结果作进一步优化[5].

1.3 面临的问题

二维特征提取算法是实现SFM系统的基础，也是实现特征跟踪和多视角立体恢复的前提.虽然已经有诸如SIFT这类成熟的特征提取算法，但考虑SFM系统的应用场景的特殊性，要进行特征提取面临2个问题：

1)计算效率问题.SFM系统输入的图像数量庞大，并且图像的尺寸、光照、环境等情况各不相同.为了恢复显著的三维特征，需要在海量数据中快速提取稳定且易分辨的二维特征.

2)鲁棒性问题.输入目标的图像之间视角差异可能非常大，使得图像间的相似度降低，让特征识别和匹配变得困难.这类问题也称为宽基线几何问题[6].

为了解决上面提到的2个问题，本文提出了FASTX-DAISY快速特征提取算法.

2 FASTX-DAISY快速特征提取算法

目前主流的特征提取算法主要实现选取特征点和建立特征描述2个功能.SIFT首先通过对不同尺度的图像求高斯差分(DoG)的极值比较选取特征点；然后在得到的特征点附近取一个窗口，用梯度直方图的方式获得该点的特征描述向量[1].类似地，在FASTX-DAISY算法中，FASTX算法实现了特征点选取，DAISY算法实现了特征描述.

2.1 FASTX特征点选取

文献[7]的研究指出，用多视角特征描述同一个场景目标的关键是找到稳定并且具有可重现性的点作为特征点，例如角点.FAST是一种基于图像分割比较的高效角点检测算法.但FAST没有衡量检测到的角点质量的指标，使得检出的特征点容易受噪声干扰.

ORB(Oriented BRIEF)[8]中的特征点选取算法称为oFAST(Oriented FAST)，是一种基于FAST算法的改进.它不仅赋予了FAST角点尺度和方向，还引了Harris角点评估的思想[9]来衡量特征点的质量.本文对oFAST进行简化，对FAST的结果中按角点评估的结果取前X个质量较好的点，不考虑尺度和方向问题，称为FASTX算法.FASTX算法描述如下：

1)建立像素环.设候选点为p，灰度值为Ip；在p点周围选取包含16个像素的环，如图2所示；

2)排除非角点与候选点测试.记测试通过条件为：像素点灰度值大于Ip+t或小于Ip-t(t是预先设定的阈值).首先进行快速测试，测试编号为1，9，5，13的灰度，若至少3个像素测试通过，则继续测试环上剩下的点，否则立刻排除该点.最后含快速测试在内若超过12个像素点测试通过，p点就是一个角点；

3)筛选角点.用质量函数R计算角点的响应，R=det(M)-s·Tr(M).其中，s为常数，M为角点及附近区域灰度偏微分的方阵，det(M)表示行列式值，Tr(M)是矩阵的迹.

最后对响应值由高到低排序，选择前X个结果(X为预设值)作为FASTX的最终输出.与oFAST相比，FAST失去了尺度和方向，但凭借卷积方向图，DAISY很好地弥补了不足.

图2 选取候选点附近的像素环[2]

2.2DAISY特征描述

2.2.1 卷积方向图

将方向梯度图的概念扩展，计算不同高斯尺度的方向图，就得到了“卷积方向图”：

(1)

(2)

2.2.2 特征描述向量

首先，把处在同一高斯尺度，具有不同关联方向的梯度组成一个梯度向量，记为

(3)

再根据DAISY的采样模式，同一尺度的卷积方向图中，以关键点为中心，共分为Q级不同的半径采样圆环，每一级圆上的采样点都有8个.把一个关键点坐标为(u0,v0)，距关键点距离Ri,方向为j的采样点记为lj(u0,v0,Ri).把关键点和采样点的h∑(u,v)向量归一化，并延伸到多个高斯尺度的卷积方向图上后组合起来，就生成了最终的DAISY描述子：

…

(4)

取参数T=8,H=8,Q=3[3]，得到(Q×T+1)×H=200维的向量.DAISY利用卷积特性简化了梯度计算，因此其计算速度比直接求邻域梯度的SIFT向量更快.

图3 DAISY采样模式与方向图

2.3 FASTX-DAISY组合算法

本文借鉴了ORB的思路，对提取到的FAST点进行质量评估.既提升了鲁棒性，也避免了因提取图像内所有点计算DAISY特征而带来的额外开销.再利用DAISY特征本身具有的尺度方向特性，简化了ORB在特征提取阶段就计算尺度和方向的不必要步骤.最后得到的FASTX-DAISY流程图如图4所示.

图4 FASTX-DAISY流程图

3 实验分析

为了表征FASTX-DAISY实际效果，本文在同一环境下分别使用SIFT，FASTX-DAISY以及ORB-DAISY进行SFM实验.其中ORB-DAISY中把FASTX算法替换成了ORB中的特征提取算法即oFAST，实验图像数据来自米德尔伯里学院的开放数据集，如图5所示.输出结果用三维点云表示，如图6所示，其中图6(a)、(d)表示使用SIFT特征的重建结果，(b)、(e)表示使用FASTX-DAISY的结果，(c)、(f)表示ORB-DAISY的结果.

图5 部分输入数据

图6 3种算法分别得到的三维点云

3.1 计算效率对比

本文使用平均三维点重建时间来评估算法的计算效率，即恢复单个三维点所耗费时长，时间越长效率越低，结果如图7所示.实验结果显示，随着输入图像数量增大，FASTX-DAISY重建效率高出SIFT近100%，略高于ORB-DAISY.

3.2 鲁棒性对比

定义如下：在输入图像集合中，如果存在一幅图像，它的旋转矩阵的欧拉角真值与其他图像差值φ超过30°，那么就认为输入集合存在宽基线问题.在每5幅图像中加入1幅符合宽基线问题要求的图像，衡量最终得到的三维点数量.得到的点云数量直方图如图8所示.通过FASTX-DAISY得到的点云数量是SIFT得到的2倍以上，在视觉上FASTX-DAISY的点云(图6(b),(e))相比SIFT(图6(a),(d))更为稠密.与ORB-DAISY相比，FASTX-DAISY在输入较少时优势明显，但随着输入增大，两者效果近似，都能获得较多的重建点.

图7 平均三维点重建时间对比

图8 包含宽基线情形的重建点云数量对比

4 结束语

SIFT算法是SFM系统的主流特征提取方法，但它的效率和鲁棒性并不足以满足SFM系统的需要.本文针对这两个问题提出了FASTX-DAISY快速特征提取算法.实验结果表明，采用FASTX-DAISY相比SIFT不仅能有效提升SFM系统的效率，而且强化了应对宽基线问题的鲁棒性.在实验中，没有针对特征的搜索匹配过程进行优化，有关如何降低FASTX-DAISY特征匹配开销的问题还有待进一步研究.

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

[2]ROSTEN E, DRUMMOND T. Machine learning for high-speed corner detection[C]//European conference on computer vision. Springer Berlin Heidelberg, 2006:430-443.

[3]TOLA E, LEPETIT V, FUA P. Daisy: An efficient dense descriptor applied to wide-baseline stereo[J]. Pattern Analysis and Machine Intelligence, IEEE Transactions on, 2010,32(5):815-830.

[4]TOMASI C, KANADE T. Shape and motion from image streams under orthography: a factorization method[J]. International Journal of Computer Vision, 1992,9(2):137-154.

[5]SZELISKI R. Computer vision: algorithms and applications[M]. Berlin: Springer Science & Business Media, 2010:347-373.

[6]李竹林,张根耀.基于特征的宽基线立体匹配技术研究[J].计算机技术与发展,2013,23(5):86-89.

[7]SCHMID C, MOHR R, BAUCKHAGE C. Evaluation of interest point detectors[J]. International Journal of computer vision, 2000,37(2):151-172.

[8]RUBLEE E, RABAUD V, KONOLIGE K, et al. ORB: An efficient alternative to SIFT or SURF[C]//2011 International conference on computer vision. IEEE,2011:2564-2571.

[9]HARRIS C, STEPHENS M. A combined corner and edge detector[C]//Alvey Vision Conference. 1988:147-151.

[10]丁南南,刘艳滢,张叶.基于SURF-DAISY算法和随机kd树的快速图像配准[J].光电子·激光,2012,23(7):1395-1402.

An Efficient and Robust Feature Extraction Algorithm in Structure from Motion Systems

CHEN Kangping, LIU Eryun

(CollegeofInformationScienceandElectronicEngineering,ZhejiangUniversity,HangzhouZhejiang310027,China)

Feature extraction and matching is the cornerstone of the structure from motion system. This paper introduces the typical structure of a structure from motion (SFM) system and discusses the problems in the applications. Feature extraction plays an important role in a SFM system. For dealing with large inputs and variant views, it proposes an efficient extraction algorithm called FASTX-DAISY. Experimental results show that comparing to SIFT, ORB-DAISY and similar traditional methods, proposed method not only speed up the process of reconstruction, but is also more robust when there are large changes in views.

feature extraction; structure from motion; fast features

10.13954/j.cnki.hdu.2017.02.008

2016-05-31

陈康平(1994-)，男，浙江杭州人，硕士研究生，机器视觉相关技术.通信作者：刘而云讲师，E-mail：eryunliu@zju.edu.cn.

TP391.4

A

1001-9146(2017)02-0034-05