宋征璽, 張明環(huán)

(1.西北工業(yè)大學(xué) 圖書館, 陜西 西安　710072；2.西北工業(yè)大學(xué) 航天學(xué)院, 陜西 西安　710072)

?

基于分塊聚類特征匹配的無人機(jī)航拍三維場景重建

宋征璽1, 張明環(huán)2

(1.西北工業(yè)大學(xué) 圖書館, 陜西 西安710072；2.西北工業(yè)大學(xué) 航天學(xué)院, 陜西 西安710072)

摘要：針對(duì)無人機(jī)航拍采集的海量無標(biāo)定圖像，在SFM(structure from motion)重建框架下，提出了基于分塊聚類特征匹配的三維重建方法。文章將航拍圖像的匹配問題轉(zhuǎn)化為待匹配圖像集合的篩選以及圖像局部特征配準(zhǔn)。通過增加篩選步驟，提出了在縮略圖尺度下利用詞匯樹的評(píng)分機(jī)制構(gòu)建待匹配圖像集合的方法；利用特征成簇狀分布的數(shù)據(jù)特性，提出了先聚類再匹配的局部特征配準(zhǔn)方法。優(yōu)化了SFM重建框架的特征匹配部分，在航拍數(shù)據(jù)庫PAMView中進(jìn)行了三維重建實(shí)驗(yàn)。實(shí)驗(yàn)結(jié)果表明，該方法在不影響重建性能下有效提高運(yùn)算速率。

關(guān)鍵詞：圖像匹配；像素點(diǎn)；無人機(jī)航拍視頻；三維重建；聚類

隨著計(jì)算機(jī)視覺理論以及無人機(jī)平臺(tái)技術(shù)的迅猛發(fā)展，無人機(jī)視覺研究將重新定義未來人類感知世界的能力與范圍。無人機(jī)視覺研究已經(jīng)逐步從二維的圖像處理、分析發(fā)展為三維場景的重構(gòu)與解析。復(fù)雜大場景的三維重建是當(dāng)前國內(nèi)外研究的熱點(diǎn)問題。無人機(jī)平臺(tái)在獲取三維數(shù)據(jù)方面具有視角靈活性大、飛行成本低以及時(shí)效性強(qiáng)等優(yōu)勢，可得到同一場景連續(xù)多視角、海量無標(biāo)定圖像序列。SFM重建框架[1]無需相機(jī)標(biāo)定信息，僅利用序列圖像特征的內(nèi)在約束，通過捆綁調(diào)整迭代優(yōu)化可同時(shí)得到場景的三維結(jié)構(gòu)與相機(jī)的位姿信息。因此，SFM重建框架是一種重要的無人機(jī)航拍圖像序列的三維重建方法。為海量圖像建立內(nèi)在約束是該框架應(yīng)用于無人機(jī)圖像序列三維重建最為基礎(chǔ)且耗時(shí)的步驟，因此快速實(shí)現(xiàn)大場景的三維結(jié)構(gòu)分析的首要任務(wù)即高效率地建立圖像間特征匹配關(guān)聯(lián)。為了最大限度獲取圖像間的約束關(guān)聯(lián)，該框架采用序列中當(dāng)前圖像與既往所有的圖像進(jìn)行配準(zhǔn)的策略[1]。但是航拍圖像的分辨率較高、數(shù)量大，圖像序列間隔較遠(yuǎn)的2幀信息重疊率低，采用上述策略將造成不必要的冗余計(jì)算。在目標(biāo)識(shí)別領(lǐng)域中，詞匯樹[2]是一種高效的海量信息檢索機(jī)制。本文擬利用詞匯樹技術(shù)對(duì)圖像集合進(jìn)行量化，將圖片相似度的評(píng)估轉(zhuǎn)化為向量的對(duì)比，得到待匹配圖像集合。

2幀圖像的配準(zhǔn)主要有基于樹形索引結(jié)構(gòu)(tree-based method)與基于鄰域匹配查詢(patch match)這2類方法[3]。自然場景中的特征常常呈現(xiàn)簇狀的聚類特性，因此通過設(shè)計(jì)有效的索引樹結(jié)構(gòu)可以大大加快檢索的速度。從最為經(jīng)典的ANN+KD-tree到K-means tree[4]、bbd-tree、TSVQ[5]、Vp-tree[6]以及多種的隨機(jī)化的KD-tree[7]均有效提高了特征整理的效率。但是該類方法均孤立衡量特征的匹配性。基于鄰域匹配的查詢方法能夠充分利用特征關(guān)聯(lián)性。大量實(shí)驗(yàn)證明基于鄰域匹配的方法比KD-tree+PCA[8]的查詢方法快近20～100倍。但是該類方法不事先組織數(shù)據(jù)，因此隨機(jī)采樣得到的備選數(shù)據(jù)有時(shí)難于正確匹配。本文所提出的分塊聚類方法，在縮略圖尺度下計(jì)算索引樹結(jié)構(gòu)特征匹配信息，利用K-means聚類算法對(duì)匹配的特征進(jìn)行聚類得到特征分布密集的塊影射到原始尺寸下，進(jìn)行局部圖像塊特征的匹配。充分結(jié)合2種匹配思路的優(yōu)勢，實(shí)現(xiàn)由粗到細(xì)的局部配準(zhǔn)。

本文提出了基于分塊聚類特征匹配的無人機(jī)航拍三維場景重建方法，旨在提高SFM重建框架在建立圖像間特征關(guān)聯(lián)階段的算法執(zhí)行效率。本文對(duì)航拍數(shù)據(jù)庫PAMView[9]中多個(gè)不同場景進(jìn)行三維重建實(shí)驗(yàn)，證明該算法能夠提高圖像匹配階段的運(yùn)算速度，并優(yōu)化整個(gè)重建系統(tǒng)的執(zhí)行效率。實(shí)驗(yàn)結(jié)果證明優(yōu)化后的系統(tǒng)對(duì)多類不同場景進(jìn)行三維重建時(shí)具有較高的可信性和有效性。

1無人機(jī)航拍圖像分塊聚類匹配算法

1.1待匹配圖像集合構(gòu)建

SFM重建框架是將圖像序列中建立的特征匹配跡作為捆綁調(diào)整部分的輸入，通過迭代優(yōu)化復(fù)原三維場景與相機(jī)姿態(tài)。因此，最大限度挖掘圖像特征的匹配約束是三維重建效果的底層保證。由于無人機(jī)航跡自由度較高，序列的圖像間的特征重疊率無一定規(guī)律分布。待匹配圖像集合的建立擬采用詞匯樹技術(shù)對(duì)圖像特征進(jìn)行無監(jiān)督的學(xué)習(xí)，得到與查詢圖像相似度較高的圖像集合進(jìn)行局部特征匹配約束計(jì)算。

無人機(jī)航拍圖像的分辨率較大，為提高運(yùn)算效率本文對(duì)所有序列圖像建立縮略圖，并通過SIFT算子提取所有圖片的局部特征。采用K-means聚類方法對(duì)特征集合進(jìn)行有層次的聚類，訓(xùn)練過程如圖1所示。

圖1　基于K-means算法的場景特征訓(xùn)練學(xué)習(xí)

(1)

逐幀量化序列中所有圖像特征,可以將圖像集合P={pj}的特征轉(zhuǎn)化為由權(quán)值構(gòu)成的t×N矩陣。

(2)

至此完成了對(duì)場景描述詞匯的量化。重新以序列中每幀圖像為查詢圖像,構(gòu)建其縮略圖的特征集合。對(duì)詞匯樹中的每一個(gè)聚類中心ci,即描述場景的每一個(gè)單詞計(jì)算與查詢圖像的相關(guān)度權(quán)值向量,公式如下

(3)

式中，mi為查詢圖像特征在單詞中出現(xiàn)的頻數(shù),生成查詢圖像的權(quán)值向量:q=[w1,w2,…,wt]。該方法將查詢圖像與序列中圖像的相關(guān)性度量問題將轉(zhuǎn)化為向量q與矩陣H的行向量相似度計(jì)算問題。通過逐個(gè)計(jì)算q與訓(xùn)練集圖像的hi的2-范數(shù)

(4)

得到序列中所有圖像與查詢圖像的相關(guān)度評(píng)分,用快速排序算法選擇一定數(shù)量的圖像構(gòu)成待匹配圖像集合。

1.2圖像局部特征匹配約束

對(duì)每一幀縮略圖像的特征子集合建立KD-tree,并利用FLANN最近鄰算法將當(dāng)前圖像與待匹配集合中所有圖像計(jì)算匹配. 對(duì)已匹配特征分別進(jìn)行K-means聚類, 如圖2所示,將圖像特征聚為5類并分別標(biāo)注為5種不同的灰度, 圓圈所示位置為聚類中心的坐標(biāo):

圖2　圖像的特征聚類特性與分組示意圖

可以發(fā)現(xiàn)圖像中的特征成簇狀分布。將縮略圖中的特征點(diǎn)映射到原始圖像上,可以看到特征在原始圖像上依舊成簇狀分布。根據(jù)K-means聚類方法結(jié)果對(duì)特征進(jìn)行分組,對(duì)第k個(gè)聚類組利用下式劃分圖像塊。

(5)

式中,x、y分別表示第i個(gè)特征點(diǎn)的像素位置,并得到第k個(gè)聚類下圖像塊4個(gè)方向的邊界,并映射到原始圖像的尺度下.當(dāng)前圖像與待匹配圖像分塊聚類結(jié)果如圖3所示。

圖3　聚類分塊特征示意圖

由于圖像具有局部一致性假設(shè)[3],即匹配的特征附近分布大量的有價(jià)值匹配特征。因此根據(jù)圖像之間的分塊匹配信息,對(duì)在原始尺度下的圖像塊建立KD-tree子樹,計(jì)算局部特征匹配信息。

1.3算法流程

無人機(jī)航拍圖像特征分塊聚類匹配算法的執(zhí)行流程如表1所示,該算法的輸入是無人機(jī)航拍圖像序列,輸出是特征匹配跡(track)。該跡可以用于SFM重建系統(tǒng)的捆綁調(diào)整迭代優(yōu)化。

表1　算法流程

2三維重建系統(tǒng)設(shè)計(jì)

無人機(jī)航拍視頻三維重建系統(tǒng)旨在對(duì)輸入系統(tǒng)中的無人機(jī)數(shù)據(jù)得到場景的三維重建結(jié)果。

2.1系統(tǒng)需求

分析三維重建技術(shù)的應(yīng)用領(lǐng)域,利用無人機(jī)平臺(tái)所采集到的數(shù)據(jù)離線進(jìn)行三維場景的重建系統(tǒng)需要滿足以下需求:

1) 能夠提供對(duì)多種場景進(jìn)行三維重建,在城市樓群密集環(huán)境以及機(jī)場等單調(diào)環(huán)境均能實(shí)現(xiàn)可觀度較高的三維重建效果;

2) 能夠?qū)σ曨l中每一個(gè)視角下相機(jī)的位置姿態(tài)參數(shù)進(jìn)行復(fù)原與結(jié)算;

3) 提供二次開發(fā)功能,使用戶可以快速將三維重建結(jié)果用于多種專業(yè)領(lǐng)域,如地理信息標(biāo)注、三維虛擬漫游。

2.2系統(tǒng)結(jié)構(gòu)

無人機(jī)航拍視頻的三維重建系統(tǒng)以無人機(jī)采集到的場景多視點(diǎn)航拍視頻圖像為輸入,通過離線處理的方式計(jì)算出場景的三維結(jié)構(gòu)以及相機(jī)位姿,并在meshlab環(huán)境中顯示。根據(jù)前述的無人機(jī)航拍視頻三維重建算法研究,本系統(tǒng)的功能模塊主要有:特征匹配模塊、三維機(jī)構(gòu)重建模塊以及可視化渲染模塊等,系統(tǒng)的輸入是離線得到的無人機(jī)視頻,系統(tǒng)的輸出是格式為*.ply文件在meshlab環(huán)境中顯示。

該無人機(jī)航拍視頻三維重建是一個(gè)離線處理系統(tǒng),但其中的圖像特征獲取與匹配,三維重建系統(tǒng)中的參數(shù)優(yōu)化與捆綁調(diào)整,以及多視角渲染中的基于面片的匹配、膨脹、過濾操作均要面臨海量計(jì)算的問題,因此提高運(yùn)算速度是系統(tǒng)設(shè)計(jì)所面臨的首要問題。為了使系統(tǒng)處理效率提高,除了在采用前述算法的改進(jìn)以及優(yōu)化,本系統(tǒng)選用高性能計(jì)算機(jī)作為運(yùn)行平臺(tái);此外,大量的使用共享內(nèi)存作為大數(shù)據(jù)高速通信的手段,不使用硬盤或網(wǎng)絡(luò),以減少計(jì)算延遲。

綜上分析,本系統(tǒng)的總體結(jié)構(gòu)如圖4所示:

圖4　系統(tǒng)總體結(jié)構(gòu)框圖

3實(shí)驗(yàn)結(jié)果與分析

本文的實(shí)驗(yàn)數(shù)據(jù)來自公開PAMView的航拍數(shù)據(jù)集,包含對(duì)美國羅特島洲普羅維登斯市27個(gè)場景的航拍數(shù)據(jù),圖片尺寸1080×720,對(duì)地面成像的分辨率為30cm/pixel. 實(shí)驗(yàn)環(huán)境為Windows7 32位操作系統(tǒng),Interl(R)Core(TM)i7處理器, 4G內(nèi)存。

3.1特征匹配性能對(duì)比

對(duì)PAMView數(shù)據(jù)集中的SITE02、SITE03、SITE25 3組數(shù)據(jù)進(jìn)行特征匹配實(shí)驗(yàn),從運(yùn)行速度與特征匹配有效性2個(gè)方面將本文所提出的算法與SFM經(jīng)典框架中的匹配策略進(jìn)行對(duì)比。

表2　匹配步驟運(yùn)行時(shí)間對(duì)比圖

如表2所示,SITE02、SITE03以及SITE25分別包含193、312以及102幀圖片,無人機(jī)航拍圖像匹配旨在建立序列圖像之間的內(nèi)在匹配約束,因此運(yùn)行速度隨圖片幀數(shù)的增多成倍增長。經(jīng)典SFM重建框架中的圖像匹配策略將當(dāng)前圖像與所有圖像計(jì)算特征匹配關(guān)系,其算法復(fù)雜度為O(N×N)。本文所采用的匹配策略是將當(dāng)前圖像與待匹配圖像集合元素逐一匹配,其算法復(fù)雜度為O(nN)。同時(shí),通過引入詞匯樹,縮略圖以及分塊聚類等步驟,大幅提高特征匹配的運(yùn)行速度。圖5和圖6展示的圖像局部特征匹配的匹配效果,圖5a)、圖6a)是本文提出算法的匹配結(jié)果,采用不同的顏色表示不同塊間的特征匹配,驗(yàn)證了算法有效性。

圖5　SITE02匹配效果對(duì)比圖

圖6　SITE25匹配效果對(duì)比圖

3.2系統(tǒng)運(yùn)行速度對(duì)比

用上述算法替換SFM重建框架的圖像匹配模塊,對(duì)SITE25、SITE22、SITE02以及SITE08 4個(gè)場景進(jìn)行三維重建實(shí)驗(yàn)。捆綁調(diào)整模塊調(diào)用Bundler[1],三維渲染部分采用CMVS+PMVS[10]的稠密渲染方法。本文提出的重建系統(tǒng)與經(jīng)典系統(tǒng)的速度對(duì)比如表3所示。

表3　不同數(shù)據(jù)上的重建時(shí)間的對(duì)比

可以看出通過優(yōu)化特征匹配階段算法的執(zhí)行效率，三維重建系統(tǒng)的運(yùn)行速度得到了大幅提升。

3.3三維重建效果展示

以數(shù)據(jù)集中有代表性的3個(gè)場景為例，展示了基于分塊聚類特征匹配的無人機(jī)航拍三維場景重建結(jié)果。SITE25是對(duì)醫(yī)院以及周邊建筑物103個(gè)視角的觀測，該場景包含建筑與道路，場景紋理較復(fù)雜，其重建效果如圖7所示。

圖7　SITE25重建效果圖

SITE22包含市中心分布較為密集的建筑群173個(gè)多視角的航拍圖像，該場景圖像存在較大的深度變化，其重建效果如圖8所示。

圖8　SITE22重建效果圖

SITE02包含場景深度變化較小的機(jī)場環(huán)境193個(gè)視角的航拍圖像，其重建效果如圖9所示。

圖9　SITE02重建效果圖

圖7～圖9的第一行表示無人機(jī)采集到的場景的原始圖像，其下方數(shù)字為該圖片在圖像序列中的排序。第二行是經(jīng)過CMVS+PMVS渲染的三維重建結(jié)果在meshlab中2個(gè)不同視點(diǎn)下的顯示效果。

可見該算法能夠?qū)Χ喾N復(fù)雜大場景進(jìn)行有效三維重建，場景的中心部分重建效果更為細(xì)致。

4結(jié)論

本文針對(duì)復(fù)雜大場景三維重建運(yùn)算速度較慢的問題，基于SFM三維重建框架，提出了一種基于分塊聚類特征匹配的無人機(jī)航拍三維場景重建方法。通過引入詞匯樹對(duì)縮略圖序列進(jìn)行無監(jiān)督學(xué)習(xí)，本文提出了待匹配圖像集合篩選策略；根據(jù)K-means聚類特征結(jié)果對(duì)圖像進(jìn)行分塊，提出了分塊聚類局部特征配準(zhǔn)方法。通過優(yōu)化圖像特征匹配階段的算法結(jié)構(gòu)，整個(gè)重建系統(tǒng)的運(yùn)算速度得到了有效提升。在公開數(shù)據(jù)集PAMView進(jìn)行了多組圖像匹配與三維重建實(shí)驗(yàn)，證明了該算法能夠有效對(duì)多種室外復(fù)雜大場景進(jìn)行重建。

參考文獻(xiàn)：

[1]Snavely N, Seitz S M, Szeliski R. Photo Tourism: Exploring Photo Collections in 3D[J]. ACM Trans on Graphics, 2006, 25(3): 835-846

[2]Nister D, Stewenius H. Scalable Recognition with a Vocabulary Tree[C]∥IEEE Conference on Computer Vision and Pattem Recognition, 2006: 2161-2168

[3]He K M, Sun J. Computing Nearest-Neighbor Fields Via Propagation-Assisted KD-Trees[C]∥IEEE Conference on Computer Vision and Pattem Recognition, 2012: 111-118

[4]Muja M, Lowe D G. Fast Approximate Nearest Neighbors with Automatic Algorithm Configuration[C]∥International Conference on Computer Vision Theory and Applications, 2009: 331-340

[5]Wei L Y, Levoy M. Fast Texture Synthesis Using Tree Structured Vector Quantization[C]∥Conference on Computer Graphics & Interactive Techniques, 2000: 479-488

[6]Kumar N, Zhang L, Nayar S. What is a Good Nearest Neighbors Algorithm for Finding Similar Patches in Images[C]∥European Conference on Computer Vision, 2008: 364-378

[7]Silpa-Anan C, Hartley R. Optimised KD-Trees for Fast Image Descriptor Matching[C]∥IEEE Conference on Computer Vision and Pattem Recognition, 2008: 1-8

[8]Barnes C, Shechtman E, Finkelstein A, et al. Patchmatch: A Randomized Correspondence Algorithm for Structural Image Editing[J]. Acm Transactions on Graphics, 2009, 28(3): 341-352

[9]Restrepo M I, Mayer B A, Ulusoy A O, et al. Characterization of 3-D Volumetric Probabilistic Scenes for Object Recognition[J]. IEEE Journal of Selected Topics in Signal Processing, 2012, 6: 522-537

[10] Furukawa Y , Curless B, Seitz S M, et al. Towards Internet-Scale Multi-View Stereo[C]∥IEEE Conference on Computer Vision and Pattern Recognition, 2010: 1434-1441

3D Reconstruction on Unmanned Aerial Video by Using Patch Clustering Matching Method

Song Zhengxi1, Zhang Minghuan2

1.Library, Northwestern Polytechnical University, Xi′an 710072, China 2.School of Astronautics, Northwestern Polytechnical University, Xi′an 710072, China

Abstract:Under Structure from Motion (SFM) framework, this paper proposes a 3D Reconstruction method on unmanned aerial video by using Patch Clustering Matching. This method separates massive uncalibrated images matching into candidate image set screening and local feature matching. Through screening procedure, candidate set is build by scoring process of vocabulary tree on thumbnail images; Take the feature spatial distribution, this paper presents a local feature matching method after clustering. By optimizing image matching module of SFM frame, 3D reconstruction experiment is carried out on the aerial database in PAMView. The experiment results show that this method improves operating rate without impact the reconstruction performance.

Keywords:image matching; pixels; unmanned aerial video; 3D reconstruction; clustering

收稿日期：2016-03-18

基金項(xiàng)目：航天支撐技術(shù)基金(N2015KC0121)資助

作者簡介：宋征璽(1990—)，女，西北工業(yè)大學(xué)碩士研究生，主要從事計(jì)算機(jī)視覺及應(yīng)用的研究。

中圖分類號(hào)：TP391.4

文獻(xiàn)標(biāo)志碼：A

文章編號(hào):1000-2758(2016)04-0731-07