SFM系統(tǒng)中的快速魯棒特征提取算法研究

陳康平，劉而云

(浙江大學(xué)信息與電子工程學(xué)院，浙江 杭州 310027)

SFM系統(tǒng)中的快速魯棒特征提取算法研究

陳康平，劉而云

(浙江大學(xué)信息與電子工程學(xué)院，浙江 杭州 310027)

介紹了典型運(yùn)動(dòng)恢復(fù)結(jié)構(gòu)SFM系統(tǒng)的結(jié)構(gòu)，分析了二維特征提取算法對(duì)系統(tǒng)的影響.針對(duì)SFM系統(tǒng)輸入圖像數(shù)量大、視角變化多的特點(diǎn)，提出了FASTX-DAISY快速特征提取算法.實(shí)驗(yàn)表明，與SIFT以及ORB-DAISY特征提取法比較，該方法不僅能提高SFM系統(tǒng)的重建效率，而且在視角發(fā)生較大變動(dòng)時(shí)仍有較好的魯棒性.

特征提??；運(yùn)動(dòng)恢復(fù)結(jié)構(gòu)；快速特征

0 引 言

運(yùn)動(dòng)恢復(fù)結(jié)構(gòu)(Structure From Motion, SFM)系統(tǒng)在近年來(lái)興起的VR等相關(guān)技術(shù)中扮演了重要角色.其旨在利用目標(biāo)在同一場(chǎng)景、不同視角下的二維圖像，來(lái)還原目標(biāo)的三維結(jié)構(gòu)，還原的結(jié)構(gòu)可以用三維點(diǎn)云(Point Cloud)數(shù)據(jù)來(lái)表示.以點(diǎn)云數(shù)據(jù)為基礎(chǔ)做進(jìn)一步分析和擬合，可以得到場(chǎng)景中直線(xiàn)和平面等更精細(xì)的結(jié)構(gòu)，最終實(shí)現(xiàn)高質(zhì)量的三維全景還原.

SFM系統(tǒng)輸入的圖像數(shù)量大而且視角變化多，傳統(tǒng)的二維特征提取方法如SIFT(Scale-invariant Feature Transform)[1]缺乏對(duì)這種情形的應(yīng)對(duì).為此，本文結(jié)合了高效角點(diǎn)提取算法FAST(Features From Accelerated Segment Test, FAST)[2]和能良好適應(yīng)視角變化的特征描述子DAISY(Dense descriptor Applied to wide-baseline Stereo, DAISY)[3]，提出了一種適用于SFM系統(tǒng)的快速特征提取算法——FASTX-DAISY.

1 典型的SFM系統(tǒng)架構(gòu)

一個(gè)典型的SFM系統(tǒng)可以分成3個(gè)部分：二維特征提取、特征跟蹤、多視角立體重建與優(yōu)化.這3個(gè)部分前后依賴(lài)，組成了SFM系統(tǒng)三級(jí)流水線(xiàn)，如圖1所示.

圖1 SFM系統(tǒng)三級(jí)流水線(xiàn)

1.1 二維特征提取

早期的SFM系統(tǒng)采用區(qū)塊匹配或是線(xiàn)匹配的方式來(lái)提取圖像特征[4]，這種方式得到的結(jié)果非常粗糙，往往只是帶二維表面貼圖的三維結(jié)構(gòu).隨著SIFT這類(lèi)基于點(diǎn)的局部特征的出現(xiàn)[1]，SFM系統(tǒng)逐漸開(kāi)始采用特征提取的方式來(lái)代替了原來(lái)的簡(jiǎn)單的線(xiàn)面匹配方式.

1.2 特征跟蹤與多視角立體重建

基于點(diǎn)的局部特征是離散化并且無(wú)關(guān)聯(lián)的二維特征，特征跟蹤的目的是在多幅圖像中建立相同特征的關(guān)聯(lián).然后，根據(jù)這些匹配關(guān)系，結(jié)合這些圖像的視角幾何約束，重建目標(biāo)的三維信息.常用的重建方法有三角測(cè)量法和8點(diǎn)法，但二維匹配并非總是正確的，因此通常還會(huì)引入光束法平差等魯棒性方法對(duì)結(jié)果作進(jìn)一步優(yōu)化[5].

1.3 面臨的問(wèn)題

二維特征提取算法是實(shí)現(xiàn)SFM系統(tǒng)的基礎(chǔ)，也是實(shí)現(xiàn)特征跟蹤和多視角立體恢復(fù)的前提.雖然已經(jīng)有諸如SIFT這類(lèi)成熟的特征提取算法，但考慮SFM系統(tǒng)的應(yīng)用場(chǎng)景的特殊性，要進(jìn)行特征提取面臨2個(gè)問(wèn)題：

1)計(jì)算效率問(wèn)題.SFM系統(tǒng)輸入的圖像數(shù)量龐大，并且圖像的尺寸、光照、環(huán)境等情況各不相同.為了恢復(fù)顯著的三維特征，需要在海量數(shù)據(jù)中快速提取穩(wěn)定且易分辨的二維特征.

2)魯棒性問(wèn)題.輸入目標(biāo)的圖像之間視角差異可能非常大，使得圖像間的相似度降低，讓特征識(shí)別和匹配變得困難.這類(lèi)問(wèn)題也稱(chēng)為寬基線(xiàn)幾何問(wèn)題[6].

為了解決上面提到的2個(gè)問(wèn)題，本文提出了FASTX-DAISY快速特征提取算法.

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

目前主流的特征提取算法主要實(shí)現(xiàn)選取特征點(diǎn)和建立特征描述2個(gè)功能.SIFT首先通過(guò)對(duì)不同尺度的圖像求高斯差分(DoG)的極值比較選取特征點(diǎn)；然后在得到的特征點(diǎn)附近取一個(gè)窗口，用梯度直方圖的方式獲得該點(diǎn)的特征描述向量[1].類(lèi)似地，在FASTX-DAISY算法中，F(xiàn)ASTX算法實(shí)現(xiàn)了特征點(diǎn)選取，DAISY算法實(shí)現(xiàn)了特征描述.

2.1 FASTX特征點(diǎn)選取

文獻(xiàn)[7]的研究指出，用多視角特征描述同一個(gè)場(chǎng)景目標(biāo)的關(guān)鍵是找到穩(wěn)定并且具有可重現(xiàn)性的點(diǎn)作為特征點(diǎn)，例如角點(diǎn).FAST是一種基于圖像分割比較的高效角點(diǎn)檢測(cè)算法.但FAST沒(méi)有衡量檢測(cè)到的角點(diǎn)質(zhì)量的指標(biāo)，使得檢出的特征點(diǎn)容易受噪聲干擾.

ORB(Oriented BRIEF)[8]中的特征點(diǎn)選取算法稱(chēng)為oFAST(Oriented FAST)，是一種基于FAST算法的改進(jìn).它不僅賦予了FAST角點(diǎn)尺度和方向，還引了Harris角點(diǎn)評(píng)估的思想[9]來(lái)衡量特征點(diǎn)的質(zhì)量.本文對(duì)oFAST進(jìn)行簡(jiǎn)化，對(duì)FAST的結(jié)果中按角點(diǎn)評(píng)估的結(jié)果取前X個(gè)質(zhì)量較好的點(diǎn)，不考慮尺度和方向問(wèn)題，稱(chēng)為FASTX算法.FASTX算法描述如下：

1)建立像素環(huán).設(shè)候選點(diǎn)為p，灰度值為Ip；在p點(diǎn)周?chē)x取包含16個(gè)像素的環(huán)，如圖2所示；

2)排除非角點(diǎn)與候選點(diǎn)測(cè)試.記測(cè)試通過(guò)條件為：像素點(diǎn)灰度值大于Ip+t或小于Ip-t(t是預(yù)先設(shè)定的閾值).首先進(jìn)行快速測(cè)試，測(cè)試編號(hào)為1，9，5，13的灰度，若至少3個(gè)像素測(cè)試通過(guò)，則繼續(xù)測(cè)試環(huán)上剩下的點(diǎn)，否則立刻排除該點(diǎn).最后含快速測(cè)試在內(nèi)若超過(guò)12個(gè)像素點(diǎn)測(cè)試通過(guò)，p點(diǎn)就是一個(gè)角點(diǎn)；

3)篩選角點(diǎn).用質(zhì)量函數(shù)R計(jì)算角點(diǎn)的響應(yīng)，R=det(M)-s·Tr(M).其中，s為常數(shù)，M為角點(diǎn)及附近區(qū)域灰度偏微分的方陣，det(M)表示行列式值，Tr(M)是矩陣的跡.

最后對(duì)響應(yīng)值由高到低排序，選擇前X個(gè)結(jié)果(X為預(yù)設(shè)值)作為FASTX的最終輸出.與oFAST相比，F(xiàn)AST失去了尺度和方向，但憑借卷積方向圖，DAISY很好地彌補(bǔ)了不足.

圖2 選取候選點(diǎn)附近的像素環(huán)[2]

2.2DAISY特征描述

2.2.1 卷積方向圖

將方向梯度圖的概念擴(kuò)展，計(jì)算不同高斯尺度的方向圖，就得到了“卷積方向圖”：

(1)

(2)

2.2.2 特征描述向量

首先，把處在同一高斯尺度，具有不同關(guān)聯(lián)方向的梯度組成一個(gè)梯度向量，記為

(3)

再根據(jù)DAISY的采樣模式，同一尺度的卷積方向圖中，以關(guān)鍵點(diǎn)為中心，共分為Q級(jí)不同的半徑采樣圓環(huán)，每一級(jí)圓上的采樣點(diǎn)都有8個(gè).把一個(gè)關(guān)鍵點(diǎn)坐標(biāo)為(u0,v0)，距關(guān)鍵點(diǎn)距離Ri,方向?yàn)閖的采樣點(diǎn)記為lj(u0,v0,Ri).把關(guān)鍵點(diǎn)和采樣點(diǎn)的h∑(u,v)向量歸一化，并延伸到多個(gè)高斯尺度的卷積方向圖上后組合起來(lái)，就生成了最終的DAISY描述子：

…

(4)

取參數(shù)T=8,H=8,Q=3[3]，得到(Q×T+1)×H=200維的向量.DAISY利用卷積特性簡(jiǎn)化了梯度計(jì)算，因此其計(jì)算速度比直接求鄰域梯度的SIFT向量更快.

圖3 DAISY采樣模式與方向圖

2.3 FASTX-DAISY組合算法

本文借鑒了ORB的思路，對(duì)提取到的FAST點(diǎn)進(jìn)行質(zhì)量評(píng)估.既提升了魯棒性，也避免了因提取圖像內(nèi)所有點(diǎn)計(jì)算DAISY特征而帶來(lái)的額外開(kāi)銷(xiāo).再利用DAISY特征本身具有的尺度方向特性，簡(jiǎn)化了ORB在特征提取階段就計(jì)算尺度和方向的不必要步驟.最后得到的FASTX-DAISY流程圖如圖4所示.

圖4 FASTX-DAISY流程圖

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

為了表征FASTX-DAISY實(shí)際效果，本文在同一環(huán)境下分別使用SIFT，F(xiàn)ASTX-DAISY以及ORB-DAISY進(jìn)行SFM實(shí)驗(yàn).其中ORB-DAISY中把FASTX算法替換成了ORB中的特征提取算法即oFAST，實(shí)驗(yàn)圖像數(shù)據(jù)來(lái)自米德?tīng)柌飳W(xué)院的開(kāi)放數(shù)據(jù)集，如圖5所示.輸出結(jié)果用三維點(diǎn)云表示，如圖6所示，其中圖6(a)、(d)表示使用SIFT特征的重建結(jié)果，(b)、(e)表示使用FASTX-DAISY的結(jié)果，(c)、(f)表示ORB-DAISY的結(jié)果.

圖5 部分輸入數(shù)據(jù)

圖6 3種算法分別得到的三維點(diǎn)云

3.1 計(jì)算效率對(duì)比

本文使用平均三維點(diǎn)重建時(shí)間來(lái)評(píng)估算法的計(jì)算效率，即恢復(fù)單個(gè)三維點(diǎn)所耗費(fèi)時(shí)長(zhǎng)，時(shí)間越長(zhǎng)效率越低，結(jié)果如圖7所示.實(shí)驗(yàn)結(jié)果顯示，隨著輸入圖像數(shù)量增大，F(xiàn)ASTX-DAISY重建效率高出SIFT近100%，略高于ORB-DAISY.

3.2 魯棒性對(duì)比

定義如下：在輸入圖像集合中，如果存在一幅圖像，它的旋轉(zhuǎn)矩陣的歐拉角真值與其他圖像差值φ超過(guò)30°，那么就認(rèn)為輸入集合存在寬基線(xiàn)問(wèn)題.在每5幅圖像中加入1幅符合寬基線(xiàn)問(wèn)題要求的圖像，衡量最終得到的三維點(diǎn)數(shù)量.得到的點(diǎn)云數(shù)量直方圖如圖8所示.通過(guò)FASTX-DAISY得到的點(diǎn)云數(shù)量是SIFT得到的2倍以上，在視覺(jué)上FASTX-DAISY的點(diǎn)云(圖6(b),(e))相比SIFT(圖6(a),(d))更為稠密.與ORB-DAISY相比，F(xiàn)ASTX-DAISY在輸入較少時(shí)優(yōu)勢(shì)明顯，但隨著輸入增大，兩者效果近似，都能獲得較多的重建點(diǎn).

圖7 平均三維點(diǎn)重建時(shí)間對(duì)比

圖8 包含寬基線(xiàn)情形的重建點(diǎn)云數(shù)量對(duì)比

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

SIFT算法是SFM系統(tǒng)的主流特征提取方法，但它的效率和魯棒性并不足以滿(mǎn)足SFM系統(tǒng)的需要.本文針對(duì)這兩個(gè)問(wèn)題提出了FASTX-DAISY快速特征提取算法.實(shí)驗(yàn)結(jié)果表明，采用FASTX-DAISY相比SIFT不僅能有效提升SFM系統(tǒng)的效率，而且強(qiáng)化了應(yīng)對(duì)寬基線(xiàn)問(wèn)題的魯棒性.在實(shí)驗(yàn)中，沒(méi)有針對(duì)特征的搜索匹配過(guò)程進(jìn)行優(yōu)化，有關(guān)如何降低FASTX-DAISY特征匹配開(kāi)銷(xiāo)的問(wèn)題還有待進(jìn)一步研究.

[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]李竹林,張根耀.基于特征的寬基線(xiàn)立體匹配技術(shù)研究[J].計(jì)算機(jī)技術(shù)與發(fā)展,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算法和隨機(jī)kd樹(shù)的快速圖像配準(zhǔn)[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-)，男，浙江杭州人，碩士研究生，機(jī)器視覺(jué)相關(guān)技術(shù).通信作者：劉而云講師，E-mail：eryunliu@zju.edu.cn.

TP391.4

A

1001-9146(2017)02-0034-05