2. 西北工业大学 航天学院, 陕西 西安 710072
随着计算机视觉理论以及无人机平台技术的迅猛发展，无人机视觉研究将重新定义未来人类感知世界的能力与范围。无人机视觉研究已经逐步从二维的图像处理、分析发展为三维场景的重构与解析。复杂大场景的三维重建是当前国内外研究的热点问题。无人机平台在获取三维数据方面具有视角灵活性大、飞行成本低以及时效性强等优势，可得到同一场景连续多视角、海量无标定图像序列。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算法的场景特征训练学习 |
若对特征集合进行L层聚类,每一层的特征分为k类,产生K-means聚类中心数为
,即描述该场景的t个词汇C=｛ci｝。为提高检索效率而采用其熵值将序列中的每帧图像特征集量化到词汇中。场景包含图像集合P=｛pj｝,N为图像总数。ni表示包含有特征在词汇树中路经该聚类中心ci的图像数,mi,j为聚类中心ci出现在图片pj中频数。一帧图像可通过以下公式量化
逐帧量化序列中所有图像特征,可以将图像集合P=｛pj｝的特征转化为由权值构成的t×N矩阵。
至此完成了对场景描述词汇的量化。重新以序列中每帧图像为查询图像,构建其缩略图的特征集合。对词汇树中的每一个聚类中心ci,即描述场景的每一个单词计算与查询图像的相关度权值向量,公式如下
对每一帧缩略图像的特征子集合建立KD-tree,并利用 FLANN 最近邻算法将当前图像与待匹配集合中所有图像计算匹配. 对已匹配特征分别进行K-means聚类,如图 2所示,将图像特征聚为5类并分别标注为5种不同的灰度,圆圈所示位置为聚类中心的坐标:
|
| 图 2 图像的特征聚类特性与分组示意图 |
可以发现图像中的特征成簇状分布。将缩略图中的特征点映射到原始图像上,可以看到特征在原始图像上依旧成簇状分布。根据K-means聚类方法结果对特征进行分组,对第k个聚类组利用下式划分图像块。
|
| 图 3 聚类分块特征示意图 |
由于图像具有局部一致性假设[3],即匹配的特征附近分布大量的有价值匹配特征。因此根据图像之间的分块匹配信息,对在原始尺度下的图像块建立KD-tree子树,计算局部特征匹配信息。
1.3 算法流程无人机航拍图像特征分块聚类匹配算法的执行流程如表 1所示,该算法的输入是无人机航拍图像序列,输出是特征匹配迹(track)。该迹可以用于SFM重建系统的捆绑调整迭代优化。
| 无人机航拍图像特征分块聚类匹配算法 |
| 目标: 对给定的无人机航拍图像序列,计算特征匹配关系并在序列中建立特征匹配迹。 算法: Step 1 对航拍序列图像从水平与垂直2个方向进行降采样(间隔为4个像素),得到缩略图序列,并提取SIFT特征集合 Step 2 待匹配图像集合构建 Step2.1 合并序列中所有图像SIFT特征集合F=｛f｝,利用K-means聚类方法进行L层聚类,每层的特征分为k类,聚类中心数为t Step2.2 利用(1)式对每一帧图像特征集进行量化,并得到权值矩阵H Step2.3 利用(3)式构建当前图像权值向量q,并根据(4)式与矩阵H计算相关度向量 Step2.4 对向量的元素使用快速排序算法得到相关度较高的20张图像构成待匹配图像集合 Step 3 图像局部特征匹配约束 Step3.1 对查询图像的特征集合与待匹配图像集合中每张图像的特征集合构建KD-tree,并采用FLANN计算特征匹配 Step3.2 对查询图像已匹配特征分别进行K-means聚类,根据聚类对特征进行分组并利用(5)式对当前图像分块。 Step3.3 将图像分块映射回原始图像,构建KD-tree子树,计算特征匹配关联 Step 4 记录查询图像与待匹配图像集合的特征匹配关联,连接具有匹配关系的图像串生成特征迹。 |
无人机航拍视频三维重建系统旨在对输入系统中的无人机数据得到场景的三维重建结果。
2.1 系统需求分析三维重建技术的应用领域,利用无人机平台所采集到的数据离线进行三维场景的重建系统需要满足以下需求:
1) 能够提供对多种场景进行三维重建,在城市楼群密集环境以及机场等单调环境均能实现可观度较高的三维重建效果;
2) 能够对视频中每一个视角下相机的位置姿态参数进行复原与结算;
3) 提供二次开发功能,使用户可以快速将三维重建结果用于多种专业领域,如地理信息标注、三维虚拟漫游。
2.2 系统结构无人机航拍视频的三维重建系统以无人机采集到的场景多视点航拍视频图像为输入,通过离线处理的方式计算出场景的三维结构以及相机位姿,并在meshlab环境中显示。根据前述的无人机航拍视频三维重建算法研究,本系统的功能模块主要有:特征匹配模块、三维机构重建模块以及可视化渲染模块等,系统的输入是离线得到的无人机视频,系统的输出是格式为*.ply文件在meshlab环境中显示。
该无人机航拍视频三维重建是一个离线处理系统,但其中的图像特征获取与匹配,三维重建系统中的参数优化与捆绑调整,以及多视角渲染中的基于面片的匹配、膨胀、过滤操作均要面临海量计算的问题,因此提高运算速度是系统设计所面临的首要问题。为了使系统处理效率提高,除了在采用前述算法的改进以及优化,本系统选用高性能计算机作为运行平台;此外,大量的使用共享内存作为大数据高速通信的手段,不使用硬盘或网络,以减少计算延迟。
综上分析,本系统的总体结构如图 4所示:
|
| 图 4 系统总体结构框图 |
本文的实验数据来自公开PAMView的航拍数据集,包含对美国罗特岛洲普罗维登斯市27个场景的航拍数据,图片尺寸1080×720,对地面成像的分辨率为30cm/pixel. 实验环境为Windows 7 32位操作系统,Interl(R) Core(TM) i7处理器,4G内存。
3.1 特征匹配性能对比对PAMView数据集中的SITE02、SITE03、SITE25 3组数据进行特征匹配实验,从运行速度与特征匹配有效性2个方面将本文所提出的算法与SFM经典框架中的匹配策略进行对比。
如表 2所示,SITE02、SITE03以及SITE25分别包含193、312以及102帧图片,无人机航拍图像匹配旨在建立序列图像之间的内在匹配约束,因此运行速度随图片帧数的增多成倍增长。经典SFM重建框架中的图像匹配策略将当前图像与所有图像计算特征匹配关系,其算法复杂度为O(N×N)。本文所采用的匹配策略是将当前图像与待匹配图像集合元素逐一匹配,其算法复杂度为O(nN)。同时,通过引入词汇树,缩略图以及分块聚类等步骤,大幅提高特征匹配的运行速度。图 5和图 6展示的图像局部特征匹配的匹配效果,图 5a)、图 6a)是本文提出算法的匹配结果,采用不同的颜色表示不同块间的特征匹配,验证了算法有效性。
| 场景编号 | 图片数量/幅 | 本文方法/s | 传统方法/s |
| SITE02 | 193 | 1 474.6 | 18 270.9 |
| SITE03 | 312 | 7 861.1 | 24 956.1 |
| SITE25 | 102 | 784.6 | 1 781.7 |
|
| 图 5 SITE02匹配效果对比图 |
|
| 图 6 SITE25匹配效果对比图 |
用上述算法替换SFM重建框架的图像匹配模块,对SITE25、SITE22、SITE02以及SITE08 4个场景进行三维重建实验。捆绑调整模块调用Bundler[1],三维渲染部分采用CMVS+PMVS[10]的稠密渲染方法。本文提出的重建系统与经典系统的速度对比如表 3所示。
| 场景编号 | SFM捆绑调整/s | 传统系统总时间/s | 本文系统总时间/s |
| SITE25 | 723.114 | 32 417.991 | 6 215.712 |
| SITE22 | 3 892.231 | 253 241.988 | 78 923.115 |
| SITE2 | 4 231.892 | 293 134.221 | 81 229.315 |
| SITE8 | 633.201 | 27 214.454 | 5 332.633 |
可以看出通过优化特征匹配阶段算法的执行效率，三维重建系统的运行速度得到了大幅提升。
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 |
| Click to display the text | |
| [2] | Nister D, Stewenius H. Scalable Recognition with a Vocabulary Tree[C]//IEEE Conference on Computer Vision and Pattem Recognition, 2006: 2161-2168 |
| Click to display the text | |
| [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 |
| Click to display the text | |
| [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 |
| Click to display the text | |
| [5] | Wei L Y, Levoy M. Fast Texture Synthesis Using Tree Structured Vector Quantization[C]//Conference on Computer Graphics & Interactive Techniques, 2000: 479-488 |
| Click to display the text | |
| [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 |
| Click to display the text | |
| [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 |
| Click to display the text | |
| [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 |
| Click to display the text | |
| [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 |
| Click to display the text | |
| [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 |
| Click to display the text |
2. School of Astronautics, Northwestern Polytechnical University, Xi'an 710072, China
