清华大学 自动化系, 北京 100084
收稿日期: 2015-04-25
基金项目: 国家自然科学基金面上项目（61373074）；国家自然科学基金****基金项目（61225008）；国家自然科学基金重大国际合作项目（61020106004）
作者简介: 陈宝华(1978-),男,博士研究生
通讯作者: 周杰,教授,E-mail:jzhou@tsinghua.edu.cn
摘要：互联网图像三维可视化通常使用运动恢复结构方法将互联网图像重构成为三维点云，用于支持用户在三维空间中自由移动观察三维点云和图像。但由于同一场景互联网图像间光照条件差异巨大，传统方法往往不会重构成唯一的三维点云，而是依照光照条件的分布，构建成多个独立的点云。该文提出了一种三维点云配准框架，将这些因为光照差异而分离的点云融合成为统一的点云。首先利用点云的三维几何特征而非二维图像特征描述点云，克服了光照差异对配准的影响。其次提出了一种克服尺度差异的配准方法，以解决不同尺度点云的匹配问题。在两个数据集上的实验证明了该方法的有效性。
关键词： 三维模型配准 运动恢复结构 尺度自适应主成分迭代最近点算法
Multiple model fusion in 3-D reconstruction: Illumination and scale invariance
CHEN Baohua, DENG Lei, DUAN Yueqi, CHEN Zhixiang, ZHOU Jie
Department of Automation, Tsinghua University, Beijing 100084, China
Abstract:3-D internet photo visualization reconstructs objects in 3-D using structure information gained from the object's motion to give users motion experience. However, due to the large illumination difference between photographs on the Internet, traditional reconstruction methods cannot generate a single point cloud, but will generate multiple independent point clouds. This paper describes a 3-D model registration framework based on 3-D geometries that generates unified 3-D models from various illuminations to complete a structure from multiple models. The 3-D point cloud geometry is used instead of the 2-D features to overcome the influence of large illumination changes. Secondly, a scaled-PCA-ICP algorithm was then used to do the registration that can overcome the large scale variance between the two point clouds. Tests on two datasets show the effectiveness of this method.
Key words: 3-D model registrationstructure from motionscaled-PCA-ICP
近年来，针对互联网海量图片集的3-D可视化如图像旅游[1-2](photo tourism)和三维全景视图(photosynth)等，引起了计算机视觉研究者的注意。 在这些应用中，图像集在三维空间中被组织起来，支持用户获得在三维空间中自由浏览的视觉体验，如图 1所示。 其核心工作是使用基于运动恢复结构(structure from motion，SFM)[3]的三维重建技术[1, 4-5]，利用从互联网获取的海量图像构建目标场景的三维模型。 该三维模型包括三维点云和标定了位置和拍摄方向的图像，用于支持用户进行三维空间下的场景浏览。
 |
| 图 1 图像旅游(photo tourism)示意图 |
| 图选项 |
互联网图像的光照条件是多种多样的，例如黎明、 正午和夜间的光照差异非常明显。 利用这些图像进行三维重建时，通常不会生成一个统一的三维模型，而是根据光照条件分布自动生成多个三维模型，如图 2所示。 这是因为同一场景中具有近似光照条件的图像间会产生较多的特征匹配，而不同光照条件的图像间有效特征匹配较少。 当前对此类因光照差异带来的多模型处理问题还缺少深入研究，一般的策略是保留较大的模型，而舍弃其他较小的模型[1-2]，这种策略的代价是丢失了小模型所包含的场景结构信息和相关图像。
 |
| 图 2 图像匹配结果对三维重建的影响 |
| 图选项 |
对于因光照差异带来的多模型处理问题，本文采取融合多个模型的策略，提出一种三维模型配准框架,利用对光照条件鲁棒的三维结构信息实施配准，并着重解决不同尺度三维模型的配准问题。
1 方法框架对于同一场景的多个三维模型，选择较大的模型作为融合的基础，称为参考模型(reference model)。 其他较小的模型作为待融合的模型，称为输入模型(input model)。 配准是指是获取从输入模型到参考模型的最佳相似变换矩阵，利用其对输入模型进行旋转、 平移和缩放后，投射到参考模型的坐标系上，实现二者的融合。
首先选择较大的三维模型作为参考模型，而后逐一配准其他较小的输入模型，框架流程如图 3所示。 对每个参考模型和输入模型进行如下处理：
 |
| 图 3 本文方法框架 |
| 图选项 |
1) 过滤噪声。 基于图像重建的三维点云通常会包含噪声，影响配准精度。 因此本文使用统计过滤(statistical outlier removal)与聚类过滤(cluster outlier removal)对其进行降噪。
2) 3-D关键点提取。 初始点云可能包含众多对描述三维结构贡献较小的点，影响配准的质量和速度，因此本文对三维点云提取ISS (intrinsic shape signatures)关键点[6]，得到由关键点构成的较稀疏的点云。 过滤噪声和提取关键点可以保证三维点云只包含场景中最稳定可靠的三维结构，这一结构是后续三维配准的基础。
3) 迭代配准。 与利用kinect等技术产生的点云[7-9]拥有近似的尺度不同,基于图像重建的点云通常具有不同的尺度。 此处引入尺度自适应功能来克服尺度差异，构建尺度自适应主成分分析算法(scaled-PCA)进行粗配准，构建尺度自适应迭代最近点算法(scaled-ICP)进行精确配准，同时计算相似变换矩阵。
4) 三维模型融合。 应用相似变换矩阵将输入模型中的点云和图像投射到参考模型上,得到一个具有较完整三维结构的最终模型。
本文中需要配准的模型集合为{Mk|k=1，2，…，l}，三维模型Mk包含一个3-D点云(3-D点集合)Ck={xki|i=1，2，…，m}和摄像机姿态集合Pk={Pjk|j=1，2，…，n}，其中Pjk=[Rjk|tjk]为摄像机姿态矩阵，包括相对坐标原点的旋转矩阵Rjk和平移向量tjk。 对于3-D点云，点云中心
1.1 噪声过滤和关键点提取原始点云可能包含单点噪声和团状噪声，分别对应异常的点和点集。 本文首先使用统计过滤方法过滤单点噪声。 对于一个查询点及其k个近邻xi(1≤i≤k)，计算它们的标准差σ和均值μ，如果查询点远离中心即|xi-μ|>Kσ，则被过滤掉。
然而，统计方法并不能去除成团状的噪声。 对于这类噪声，本文首先对原始点云做k-means聚类。 聚类的距离阈值采用原点云中的点平均距离的常数倍。 点平均距离(mesh resolution unit)为点云中每个点与最近点距离的统计平均值。 其次按照每类点云数量从大到小排序。 点云数量贡献低于相应阈值(如10%)的团簇将被视为噪声过滤掉。
经过上述2种方法过滤后，点云中游离的点和点云团被过滤掉。 之后进行ISS[6]特征提取，获得三维点云中稳定且具有代表性的点，形成2个点数较少但结构清晰的关键点云，即参考点云yj(j=1,2,…,n)和输入点云xi(i=1,2,…,m)，输入到下一个配准的环节中。
1.2 迭代配准框架的核心工作是解决输入点云xi和参考点云yj的配准问题，目标是找到一个最佳相似变换 T=[SR|t]，将其作用于xi之上，将xi变换为 x′i=sRxi+t,使x′i与yj重合度最高。 本文组合使用主成分分析(PCA)和迭代最近点(ICP)算法实现由粗到精的配准，并在这2种方法中引入处理尺度变化的功能。 这种方法称之为尺度自适应主成分迭代最近点算法(Scaled PCA-ICP)。
1.2.1 Scaled-PCAScaled-PCA方法的目的是求取2个模型的主轴方向，并将2个模型进行大致的尺度调整和配准。 配准结果将作为后续Scaled-ICP方法的初始输入。
首先，使用式(1)对每一个点云进行PCA处理,即对点云的协方差矩阵Covx进行奇异值分解(SVD)，得到左奇异向量矩阵U、 特征值矩阵D和右奇异向量矩阵V：
| $UD{{V}^{T}}=svd(Co{{v}_{x}}).$ | (1) |
| $~{{T}_{pca}}=sR\left[ I|-C \right]=\frac{1}{\sqrt{{{D}_{0}}{{D}_{1}}}}U\left[ I|-\overline{x} \right].$ | (2) |
因为主轴方向的不确定性，所以有4个候选变换，分别对这4个变换进行测试，从中选出一个最佳变换，实现最小化配准误差，同时实现yj中的法向量与xi的法向量一致性最大化。
Scaled-PCA的意义在于将输入点云和参考点云进行旋转、 平移和缩放后，投射到一个标准的坐标系下，进而实现二者的基本配准，这一基本配准结果将作为后续Scaled-ICP方法的输入。
1.2.2 Scaled-ICP传统ICP[10]配准算法适用于配准质量较好、 结构近似的三维点云，其抗尺度变换能力较弱。 将其直接用于基于图像重建的点云时，由于点云质量不佳和尺度差异，配准效果不佳。 通过节1.1的去噪和提取三维关键点，点云的质量问题已经得到解决，当前需要解决的是如何进一步消除尺度差异的问题。
传统ICP算法基本步骤如下： 1) 对输入点云中的每个点，找到其在参考点云中的最近点； 2) 使用这些对应关系计算刚体变换(旋转和平移)； 3) 将这一变换作用于输入点云，完成变换旋转和平移； 4) 迭代直到收敛。
为解决尺度差异问题，本文对步骤2的内容进行了改进，将优化目标从仅估计旋转和平移(刚体变换)变为同时估计尺度、 旋转和平移(相似变换)，其在最小平方误差下的目标函数为
| ${{e}^{2}}\left( R,t,s \right)=\frac{1}{n}\sum\limits_{i=1}^{n}{\|{{y}_{i}}-(sR{{x}_{i}}+t){{\|}^{2}}}.$ | (3) |
| $Co{{v}_{yx}}=\frac{1}{n}\sum\limits_{i}{\left( y-y \right){{\left( x-x \right)}^{T}}};$ | (4) |
| $UD{{V}^{T}}=svd(Co{{v}_{x}});$ | (5) |
| $S=\left\{ \begin{align} & I,\left| U \right|\left| V \right|=1; \\ & diag\left( 1,\ldots ,1,-1 \right),\left| U \right|\left| V \right|=-1; \\ \end{align} \right.$ | (6) |
| $R=US{{V}^{T}};$ | (7) |
| $t=\overline{y}-sR\overline{x}$ | (8) |
| $s=\frac{1}{\sigma _{x}^{2}}tr\left( DS \right);$ | (9) |
| ${{T}_{icp}}=\left[ sR|t \right].$ | (10) |
将Ticp与Tpca进行串联，本文得到从输入点云到参考点云的最终变换矩阵：
| $T=T_{pca}^{-1}\left( ref \right){{T}_{icp}}\left( input,ref \right){{T}_{pca}}\left( input \right).$ | (11) |
对于xki的变换如下:
| $~x\prime _{i}^{k}=sRx_{i}^{k}+t.$ | (12) |
| $D_{i}^{k}=-sR{{(R_{i}^{k})}^{T}}t_{i}^{k}+t,$ | (13) |
| $(P_{i}^{k})\prime =[R_{i}^{k}{{R}^{T}}|st_{i}^{k}-R_{i}^{k}{{R}^{T}}t].$ | (14) |
2 实验验证本文使用2个地标建筑的数据集测试提出的三维模型配准框架。 这2个地标建筑分别是巴黎圣母院(Notre dame)和凯旋门(Triumphal Arch)，数据集下载于图像共享网站Flickr。 为验证本文方法的有效性，选择了光照差异最大的昼间图像和夜间图像，在巴黎圣母院数据集中包含59张昼间图像和47张夜间图像，在凯旋门数据集中相应图像数量为24张和15张。
初始三维点云中携带了许多噪声，包括稀疏点噪声和团状噪声，这些噪声在去噪阶段被消除，见图 4c、4d和4e。 在去噪的基础上提取ISS关键点云，见图 4f。 最后，使用本文的scaled-PCA-ICP算法将两个模型配准融合成一个模型，见图 4g。 这一最终模型包含了昼间和夜间的图像集，点云的结构相比任何单一的模型都更加完整。
 |
| 图 4 在巴黎圣母院和凯旋门数据集上的实验结果 |
| 图选项 |
本文的配准框架中使用的参数如下： 在统计过滤阶段，最近邻数量为50，判定是否是噪声的标准差阈值为1； 在聚类噪声过滤的环节，相邻半径为10 mr； 提取IIS中所需的关键点描述半径为10 mr，非极大抑制半径为2 mr，其中mr为点云的点间距离的平均值。
本文用体素网格(voxel grid)覆盖数量来评价三维模型的结构完整性。 每个体素是三维空间网格中的1个格子。 对于某一点云，用其落入某一体素的点数来判断该体素处的点云质量，超过一定阈值，则认为点云覆盖了该体素。 本文中，格子的边长取最终模型点平均距离的4倍，覆盖点数阈值为1。 由表 1的第2—4列可以看到，相比昼间和夜间模型，最终模型覆盖了更多的体素。 使用覆盖增长率ICR=(VCf-VCr)/VCr来描述参考模型融合了输入模型后的增长效果，其中VCf和VCr分别为最终模型和参考模型所覆盖的体素数。 由表 1的第5列中可以看出，相比参考模型(昼间模型)，在融合了输入模型(夜间模型)后，最终模型所覆盖的体素数有较高的增长，表明模型结构的完整性有显著的提升。
表 1 点云结构完整性分析
| 数据集 | 昼间模型覆盖体素数 | 夜间模型覆盖体素数 | 最终模型覆盖体素数 | 相对昼间模型的ICR/% |
| 巴黎圣母院 | 10 640 | 9 330 | 16 532 | 55.3 |
| 凯旋门 | 1 850 | 1 619 | 2 573 | 39.1 |
表选项
表 2给出了各个模型包含的图像数量和融合后相对于参考模型图像数的增长率。 可以看到，输入模型(夜间模型)与参考模型(昼间模型)的图像规模越接近，融合后的增长率越高，意味着本文“留大融小”策略比传统“留大弃小”策略的优势越大。
表 2 有效图像数量增长分析
| 数据集 | 昼间模型图像数 | 夜间模型图像数 | 最终模型图像数 | 相对昼间模型增长率/% |
| 巴黎圣母院 | 59 | 47 | 106 | 79.7 |
| 凯旋门 | 24 | 15 | 39 | 62.5 |
表选项
3 结 论本文提出了一种三维模型配准框架，利用三维几何特征的配准点云，解决了因光照条件差异引起的三维模型无法配准的问题。 引入克服尺度变换的方法以改进传统PCA和ICP方法，解决了因尺度不同引起的三维模型无法配准的问题。 使用这一配准框架，能够将多个独立的三维模型融合为一个统一的三维模型，提升了三维点云的结构完整性，并包含更多的有效图像。 在2个数据集上的实验结果证明了本文方法的有效性。 然而，本文方法要求输入的三维模型结构尽量相似，下一步将研究如何降低这一要求。
参考文献
| [1] | Journal of Central South University(Science and Technology), 41(2):649-654.-->Snavely N, Seitz S M, Szeliski R. Photo tourism: Exploring photo collections in 3-D[J]. ACM transactions on graphics, 2006, 25(3) : 835–846.DOI:10.1145/1141911 |
| [2] | Journal of Central South University(Science and Technology), 41(2):649-654.-->Snavely N, Seitz S M, Szeliski R. Modeling the world from internet photo collections[J]. International Journal of Computer Vision, 2008, 80(2) : 189–210.DOI:10.1007/s11263-007-0107-3 |
| [3] | Journal of Central South University(Science and Technology), 41(2):649-654.--> Lowe D G. Object recognition from local scale-invariant features [C]//Proceedings of the 7th IEEE International Conference on Computer Vision (ICCV). Kerkyra, Greece: IEEE, 1999: 1150-1157. http://www.oalib.com/references/14507849 |
| [4] | Journal of Central South University(Science and Technology), 41(2):649-654.--> Yin L, Snavely N, Gehrke J. MatchMiner: Efficient spanning structure mining in large image collections [C]//European Conference on Computer Vision (ECCV). Firenze, Italy: Springer Berlin Heidelberg, 2012:45-58. http://cn.bing.com/academic/profile?id=29546508&encoded=0&v=paper_preview&mkt=zh-cn |
| [5] | Journal of Central South University(Science and Technology), 41(2):649-654.--> Li Y, Snavely N, Dan H, et al. Worldwide pose estimation using 3D point clouds [C]//European Conference on Computer Vision (ECCV). Firenze, Italy: Springer Berlin Heidelberg, 2012:15-29. |
| [6] | Journal of Central South University(Science and Technology), 41(2):649-654.--> Zhong Y. Intrinsic shape signatures: A shape descriptor for 3-D object recognition [C]//2009 IEEE 12th International Conference on Computer Vision Workshops (ICCV Workshops). Kyoto, Japan: IEEE, 2009: 689-696. |
| [7] | Journal of Central South University(Science and Technology), 41(2):649-654.-->Henry P, Krainin M, Herbst E, et al. RGB-D mapping: Using Kinect-style depth cameras for dense 3-D modeling of indoor environments[J]. The International Journal of Robotics Research, 2012, 31(5) : 647–663.DOI:10.1177/0278364911434148 |
| [8] | Journal of Central South University(Science and Technology), 41(2):649-654.--> Newcombe R A, Izadi S, Hilliges O, et al. Kinect fusion: Real-time dense surface mapping and tracking [C]//10th IEEE International Symposium on Mixed and Augmented Reality (ISMAR). Basel, Switzerland: IEEE, 2011: 127-136. |
| [9] | Journal of Central South University(Science and Technology), 41(2):649-654.-->Pomerleau F, Colas F, Siegwart R, et al. Comparing ICP variants on real-world data sets[J]. Autonomous Robots, 2013, 34(3) : 133–148.DOI:10.1007/s10514-013-9327-2 |
| [10] | Journal of Central South University(Science and Technology), 41(2):649-654.-->Besl P J, Mckay N D. Method for registration of 3-D shapes[J]. Proceedings of SPIE-The International Society for Optical Engineering, 1992, 14(3) : 239–256. |
| [11] | Journal of Central South University(Science and Technology), 41(2):649-654.-->Umeyama S. Least-squares estimation of transformation parameters between two point patterns[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 1991(4) : 376–380. |
| [12] | Journal of Central South University(Science and Technology), 41(2):649-654.--> Wu C. Towards linear-time incremental structure from motion [C]//International Conference on 3-D Vision (3-DV). Seattle, WA, USA: IEEE, 2013: 127-134. |
| [13] | Journal of Central South University(Science and Technology), 41(2):649-654.--> Furukawa Y, Curless B, Seitz S M, et al. Towards internet-scale multi-view stereo [C]//IEEE Conference on Computer Vision and Pattern Recognition (CVPR). San Francisco, CA, USA: IEEE, 2010: 1434-1441. |
| [14] | Journal of Central South University(Science and Technology), 41(2):649-654.-->Furukawa Y, Ponce J. Accurate, dense, and robust multiview stereopsis[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2010, 32(8) : 1362–1376.DOI:10.1109/TPAMI.2009.161 |
