基于分块聚类特征匹配的无人机航拍三维场景重建

宋征玺, 张明环

(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