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

宋征璽, 張明環

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

?

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

宋征璽1, 張明環2

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

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

關鍵詞：圖像匹配；像素點；無人機航拍視頻；三維重建；聚類

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

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

本文提出了基于分塊聚類特征匹配的無人機航拍三維場景重建方法，旨在提高SFM重建框架在建立圖像間特征關聯階段的算法執行效率。本文對航拍數據庫PAMView[9]中多個不同場景進行三維重建實驗，證明該算法能夠提高圖像匹配階段的運算速度，并優化整個重建系統的執行效率。實驗結果證明優化后的系統對多類不同場景進行三維重建時具有較高的可信性和有效性。

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

1.1待匹配圖像集合構建

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

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

圖1　基于K-means算法的場景特征訓練學習

(1)

逐幀量化序列中所有圖像特征,可以將圖像集合P={pj}的特征轉化為由權值構成的t×N矩陣。

(2)

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

(3)

式中，mi為查詢圖像特征在單詞中出現的頻數,生成查詢圖像的權值向量:q=[w1,w2,…,wt]。該方法將查詢圖像與序列中圖像的相關性度量問題將轉化為向量q與矩陣H的行向量相似度計算問題。通過逐個計算q與訓練集圖像的hi的2-范數

(4)

得到序列中所有圖像與查詢圖像的相關度評分,用快速排序算法選擇一定數量的圖像構成待匹配圖像集合。

1.2圖像局部特征匹配約束

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

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

可以發現圖像中的特征成簇狀分布。將縮略圖中的特征點映射到原始圖像上,可以看到特征在原始圖像上依舊成簇狀分布。根據K-means聚類方法結果對特征進行分組,對第k個聚類組利用下式劃分圖像塊。

(5)

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

圖3　聚類分塊特征示意圖

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

1.3算法流程

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

表1　算法流程

2三維重建系統設計

無人機航拍視頻三維重建系統旨在對輸入系統中的無人機數據得到場景的三維重建結果。

2.1系統需求

分析三維重建技術的應用領域,利用無人機平臺所采集到的數據離線進行三維場景的重建系統需要滿足以下需求:

1) 能夠提供對多種場景進行三維重建,在城市樓群密集環境以及機場等單調環境均能實現可觀度較高的三維重建效果;

2) 能夠對視頻中每一個視角下相機的位置姿態參數進行復原與結算;

3) 提供二次開發功能,使用戶可以快速將三維重建結果用于多種專業領域,如地理信息標注、三維虛擬漫游。

2.2系統結構

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

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

綜上分析,本系統的總體結構如圖4所示:

圖4　系統總體結構框圖

3實驗結果與分析

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

3.1特征匹配性能對比

對PAMView數據集中的SITE02、SITE03、SITE25 3組數據進行特征匹配實驗,從運行速度與特征匹配有效性2個方面將本文所提出的算法與SFM經典框架中的匹配策略進行對比。

表2　匹配步驟運行時間對比圖

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

圖5　SITE02匹配效果對比圖

圖6　SITE25匹配效果對比圖

3.2系統運行速度對比

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

表3　不同數據上的重建時間的對比

可以看出通過優化特征匹配階段算法的執行效率，三維重建系統的運行速度得到了大幅提升。

3.3三維重建效果展示

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

圖7　SITE25重建效果圖

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

圖8　SITE22重建效果圖

SITE02包含場景深度變化較小的機場環境193個視角的航拍圖像，其重建效果如圖9所示。

圖9　SITE02重建效果圖

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

可見該算法能夠對多種復雜大場景進行有效三維重建，場景的中心部分重建效果更為細致。

4結論

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

參考文獻：

[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

基金項目：航天支撐技術基金(N2015KC0121)資助

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

中圖分類號：TP391.4

文獻標志碼：A

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