一种结合纹理信息的深度图像自动配准方法

1.一种结合纹理信息的深度图像自动配准方法，其特征在于：分为两幅深度图像的配准和多幅深度图像的配准，其中：
两幅深度图像的配准步骤如下：
设P和Q是待配准的扫描数据，P的纹理图像和深度图像分别是Ip和Rp，Q的纹理图像和深度图像分别是Iq和Rq，
第一步，从P和Q中提取纹理图像Ip和Iq或根据深度图像Rp和Rq生成纹理图像Ip和Iq，其中，根据深度图像Rp和Rq生成纹理图像Ip和Iq的方法为：
对深度图像做Laplacian平滑，得到它的基模型，再计算出深度图像中的每个顶点到基模型上对应顶点的距离，并以每一距离值作为每个顶点在纹理图像上对应像素的亮度值；
第二步，基于SIFT特征提取纹理图像Ip和Iq中的兴趣像素，并通过交叉检验的方法从中找出匹配像素对的候选集C，具体的步骤为：
(2.1)使用SIFT算法分别找出Ip和Iq中的兴趣像素集，对于SIFT算法检测出的每一个兴趣像素p，用sift(p)表示p的SIFT特征向量，则定义距离d(p，q)＝||sift(p)，sift(q)||表示两个兴趣像素p和q之间的相似程度，这个距离越小则这两个像素越相似，反之，距离越大则它们差别越大；
(2.2)根据两个像素的SIFT特征向量间的欧式距离，在Ip和Iq的兴趣像素集之间寻找对应的像素，其方法为：
(2.2.1)删除在深度图像中没有对应顶点的兴趣像素；
(2.2.2)对于纹理图像中的兴趣像素p，如果p在深度图像中对应的顶点在深度图像网格的边界上，则删除p；
p
(2.2.3)对于Ip中的每一个关键像素i，在Iq中找出使 最小的两个关键像素 和设 定义 和 间的差异度为 并预先定义差异
p
度阈值δdiff，如果 则 和 间有明显差异，能够作为i 的对应像素，否则p p
i 在Iq中有多重对应，应舍弃i，当 时，再以同样的方法在Ip中找出像素p p
的对应像素 如果 和i 为同一个像素，则i 和 是Ip和Iq间的一对候选对应像素，将p
加入候选集C，否则仍认为i 在Iq中没有对应像素；
第三步，使用自适应的RANSAC算法，根据几何信息约束找出候选集C中正确的匹配像素对，具体的步骤是：
p q p q
(3.1)对候选集C中所有元素(i，i)根据d(i，i)以升序进行排序，并将结果放入一个队列L中；
(3.2)检验L中前l个元素是否是正确的匹配，检验方法为：
(3.2.1)从L的前l个元素中随机选取3个元素作为一个样本；
(3.2.2)根据3对匹配像素在深度图像中对应顶点的几何信息计算出刚体置换矩阵；
(3.2.3)根据对应顶点的几何信息，判断其余l-3个元素在此刚体置换下是否为正确的匹配；正确匹配的元素为内点，其余的为外点，所有内点组成本次采样的一致集，然后根据内点的数目更新采样次数上限；
(3.2.4)重复以上步骤(3.2.1)-(3.2.3)，直到循环次数达到采样次数上限，然后找出一致集中元素最多，即内点数目最多的采样，并将这次采样的一致集作为正确的匹配的元素集；
第四步，在三维空间中找出和匹配像素对对应的匹配顶点对，并根据这些顶点对应关系，计算出两幅深度图像间的刚体置换矩阵；
第五步，使用改进的ICP算法优化第四步中的结果，完成两幅深度图像的精确配准；具体的步骤是：首先，在迭代过程中不考虑位于深度图像边界上和临近边界的顶点，这样能够取得更好的准确性；其次，依照每次迭代时对应点的距离来动态调整距离阈值，这样在每次迭代过程中，只有阈值范围内的对应点用于计算新的变换矩阵和最小化对应点的距离和；
多幅扫描数据的配准步骤如下：
设表示深度图像间拓扑关系的模型图为G(V，E)，图G的每个顶点vi∈V均表示一幅深度图像，图G的每一条边ei，j表示顶点vi和vj代表的两幅深度图像间有重叠区域，且这条边的权值是从vi到vj的刚体置换矩阵，S＝(s1，s2，...，sn)是待配准的n幅深度图像的输入序列；
第六步，基于两幅深度图像配准，将多幅深度图像的输入序列S分成k条带状的子序列S＝(W1，W2，...，Wk)，其中Wi∈S，i＝1...k，是若干幅深度图像的子序列，Wi中的任意两幅相邻的深度图像都有重叠区域；
第七步，采用向前搜索的策略，合并子序列，根据合并完的子序列构造完整的三维模型。
2.根据权利要求1所述的结合纹理信息的深度图像自动配准方法，其特征在于：所述第六步中，基于两幅深度图像配准，将多幅深度图像的输入序列分成若干条带状的子序列的步骤为：
(1)将s1加入第一个子序列W1中；
(2)依次配准序列S中所有相邻的深度图像si，si+1∈S，i＝1...n-1，如果si与si+1有重叠区域，则将si+1加入si所在的子序列，否则将si+1加入一个新的子序列，并在图G中加入相关的边。
3.根据权利要求1所述的结合纹理信息的深度图像自动配准方法，其特征在于：所述第七步中，采用向前搜索的策略，合并这些子序列，并根据合并完的子序列构造完整的三维模型的步骤为：
(1)对子序列Wi∈S，i＝2...k中的每幅深度图像，依次检索子序列Wj∈S，j＝i-1...1中是否存在深度图像和Wi中的深度图像有重叠区域，如果存在这样的深度图像，那么就将Wi和Wj合并，即将Wj中的各元素插入到Wi的首元素之前，同时在图G中加入相关的边；
(2)不断循环步骤(1)，直至只剩余一个子序列，或者在剩余子序列Wi中任意两个间都不存在重叠区域；
(3)根据图G重建整个模型。

一种结合纹理信息的深度图像自动配准方法\n技术领域\n[0001] 本发明涉及一种根据三维扫描数据自动重建物体三维模型的方法，特别是一种结合纹理信息的深度图像自动配准方法，属于计算机虚拟现实和计算机图形学技术领域，主要应用于各种真实物体三维逼真模型的重建，特别是应用于数字博物馆中文物的三维模型重建。\n背景技术\n[0002] 重建真实世界中物体的三维模型，被越来越广泛的应用在虚拟仿真、计算机动画、反求工程、计算机辅助设计以及数字博物馆等方面。随着三维扫描设备的不断发展，基于三维扫描设备采集到的数据重建真实物体的模型，逐渐成为一种流行的三维建模方法。主流的三维扫描仪不但能够获取模型表面顶点的深度信息，而且还能获取它们的颜色信息，即可以同时采集到等分辨率的深度图像(range image)和纹理图像(texture image)，深度图像也称作点云数据(point cloud data，PCD)。真实物体的几何形状往往较复杂，而三维扫描仪的视角又有限，因此，为了获取三维物体表面全部的几何信息，需要在多个不同的视点扫描，再将每一次采集到的扫描数据拼接起来，恢复成一个完整的三维模型，这一过程就是扫描数据的配准。\n[0003] 目前，对于扫描数据配准可以分为两个过程：两幅视图配准(pair-wise registration)和多幅视图配准(multi-view registration)。对于有部分重叠区域的两幅深度图像，两幅视图配准的目的是找出这两幅深度图像间的最优运动矩阵，在误差最小的情况下，将其中的一幅深度图像拼接到另一幅上。两幅深度图像的配准一般分为两步：粗略配准(coarse registration)和精细配准(accurate registration)。首先，在粗略配准阶段计算出两幅深度图像间刚体置换矩阵的估计值，然后，在精细配准阶段通过最小化预先定义的一个误差函数优化前一步的结果。类似的，多幅数据配准的目的是拼接给定的多幅深度图像，其主要包括两个方面：找出这些深度图像间的邻接关系，即哪些深度图像间有重叠区域和最小化全局误差。\n[0004] 在常用的两种粗配准中，一类粗略配准的方法是定义一种局部特征描述符，然后计算所有点处的特征值，再通过比较和匹配这些特征值找出两幅深度图像间三对或以上的对应特征点，最后用Horn(参见Horn，B.Closed-form solution of absolute orientation using unit quaternions.Journal of the Optical Society ofAmerica 4(1987)，\n629-642.)的方法，就可计算出两幅数据间的刚体置换矩阵。常见的局部特征描述符有：旋转图像(spin images)(参见Huber，D.F.Automatic three-dimensional modeling from reality.PhD thesis，Carnegie Mellon University，2002.Chair-Martial Hebert.)，基于物体表面微分特性的描述符(参见Gal R，Cohen-Or D.Salient geometric features for partial shape matching and similarity.ACM Trans.Graph.2006，25，130-150.)，基于积分体的描述符(参见Gelfand，N.，Mitra，N.J.，Guibas，L.J.，and Pottmann，H.Robust global registration.In Symposium on Geometry Processing(2005)，pp.197-206.)和基于尺度空间的描述符(参见Li，X.，and Guskov，I.Multi-scale features for approximate alignment of point-based surfaces.In SGP′05：Proceedings of the third Eurographics symposium on Geometry processing(Aire-la-Ville，Switzerland，Switzerland，2005)，Eurographics Association，p.217.)；另一类粗略配准的方法是基于如随机抽样一致性(RANdom SAmple Consensus，RANSAC)算法的随机算法的。例如Chen(参见Chen，C.-S.，Hung，Y.-P.，and Cheng，J.-B.Ransac-based darces：A new approach to fast auto-matic registration of partially overlapping range images.IEEE Trans.Pattern Anal.Mach.Intell.21，11(1999)，1229-1234.)提出的方法，通过在两幅深度图像上预先选取一些参考点和引入空间约束条件改进了RANSAC算法，在配准速度和结果的鲁棒性间找到一个平衡点。\n[0005] 尽管已有的局部几何特征的特征表示在刚体变换下保持不变，甚至在一定噪声条件下也具有鲁棒性。但是，由于低维特征和高维特征在配准速度和稳定性方面的固有矛盾以及深度图像中存在噪声和大量几何缺陷，对于大规模数据的配准，单纯使用局部几何特征难以取得较好效果。另外，对于任何一种局部特征描述符，每个顶点的特征值都是根据其邻域内顶点计算出来的，因此，对于物体表面不同的顶点，如果它们邻域的几何特征相似，那么在这些顶点处将取得相近的特征值，这使得在两幅深度图像间寻找匹配的特征点成为一件困难的事情。加入其他的约束条件进行剪枝或者对特征做聚合都是解决这一问题的有效方法，但它们极大的增加了特征点匹配算法的时间复杂性。\n[0006] 考虑到针对二维图像配准的研究工作已取得较好的成果，研究者们开始尝试结合纹理图像解决两幅深度图像配准的问题。其中Roth(参见Roth G.Registering two overlapping range images.In：3-D Digital Imaging and Modeling，Proceedings.Second International Conference on，1999，191-200.)通过匹配兴趣顶点组成的三角形寻找正确的对应关系，这种方法的效率和准确性都不高。Bendels(参见Bendels GH，Degener P，Wahl R，Kortgen M，Klein R.Image-based registration of 3d-range data using feature surface elements.In VAST，2004，115-124.)在找出兴趣像素的对应顶点后，先对这些顶点及其邻域做特征提取，再利用几何信息的约束找出它们之间正确的匹配关系，最终完成配准.Bendels的方法在扫描数据质量较好且数据间角度变化较小时，可以取得较好的配准结果。Seo(参见Seo JK，Sharp GC，Lee SW.Range data registration using photometric features.In：Computer Vision and Pattern Recognition，CVPR \n2005，1140-145.)在Bendels方法基础上利用光学校正技术处理纹理图像间存在的三维旋转和投影扭曲问题，但是只能校正平面或近似平面的区域的纹理，所以很难用于表面几何信息复杂的物体。刘晓利(参见刘晓利，彭翔，李阿蒙，高鹏东.结合纹理信息的深度像匹配.。计算机辅助设计与图形学学报，2007，19(3)，340-345.)使用Sobel算子提取纹理图像上的特征像素，然后通过归一化的相关系数找出对应的特征像素，最后通过Hausdorff距离检验这些特征像素对的有效性.这种方法单纯依赖纹理图像的信息找出匹配像素，且需要人机交互选出重叠区域，只适用于简单的拍摄角度变化不大的纹理图像的配准。\n[0007] 在两幅深度图像精细配准中，研究者们提出了许多的精确配准方法，其中最具里程碑意义的是迭代最近点(Iterative Closest Point，ICP)算法(参见Besl，P.J.，and McKay，N.D.Amethod for registration of 3-d shapes.IEEE Trans.Pattern Anal.Mach.Intell.14，2(1992)，239-256. 和 Chen，Y.，and Medioni，G.Object modelling by registration of multiple range images.Image Vision Comput.10，3(1992)，\n145-155.)。ICP算法以两幅深度图像的初始位置为初始状态，然后通过一个迭代过程，不断减小两幅深度图像间所有对应点的距离和，直到达到某个阈值，从而计算出两幅深度图像间的运动矩阵。ICP算法和它的变种，一般需要一个较好的初始状态，因此需要一个粗略配准的过程计算出两幅深度图像间刚体运动的估计值作为精确配准的初始状态。\n[0008] 当配准多幅深度图像时，通常会建立一个表示整个模型的各幅深度图像间拓扑关系的图G(V，E)，称为模型图(model graph)。其中，图的每个顶点vi表示一幅深度图像，每一条边ei，j表示顶点vi和vj代表的两幅深度图像间有重叠区域，且它们之间的运动矩阵也被赋给这条边。当构造图G的边集合时，在最坏的情况下，需要对任意两幅深度图像判断它们\n2\n是否重叠，这时的算法时间复杂度是O(n)。Pingi(Pingi P，Fasano A，Cignoni P，Montani C，Scopigno R.Exploiting the scanning sequence for automatic registration of large sets of range maps.Computer Graphics Forum 2005，24(3)，517-526.)通过预先定义一种扫描策略来简化这种穷举的算法。这个关于整个模型的图的生成树表示了由这些深度图像构建完整模型的最小元素集，因此一旦G被构建出来，就可以通过寻找G的一个生成树重建完整的模型。\n[0009] 但是，Pingi提出的面向条带的扫描和配准策略过于理想化，实际中很难保证深度图像序列中任意相邻的数据间均存在重叠区域。\n发明内容\n[0010] 本发明的技术解决问题：克服现有技术的不足，提供一种结合纹理信息的自动深度图像配准方法，可以快速处理大数据量的扫描数据，生成三维模型，同时抗噪声能力强。\n[0011] 本发明的技术解决方案：一种结合纹理信息的自动深度图像配准方法，分为两幅深度图像的配准和多幅深度图像的配准，其中：\n[0012] 两幅深度图像的配准步骤如下：\n[0013] 设P和Q是待配准的扫描数据，P的纹理图像和深度图像分别是Ip和Rp，Q的纹理图像和深度图像分别是Iq和Rq，\n[0014] 第一步，从P和Q中提取纹理图像Ip和Iq或根据深度图像Rp和Rq生成纹理图像Ip和Iq；\n[0015] 第二步，基于SIFT特征提取纹理图像Ip和Iq中的兴趣像素，并通过交叉检验的方法从中找出匹配像素对的候选集C；\n[0016] 第三步，使用自适应的RANSAC算法，根据几何信息约束找出候选集C中正确的匹配像素对；\n[0017] 第四步，在三维空间中找出和匹配像素对对应的匹配顶点对，并根据这些顶点对应关系，计算出两幅深度图像间的刚体置换矩阵；\n[0018] 第五步，使用改进的ICP算法优化第四步中的结果，完成两幅深度图像的精确配准；\n[0019] 多幅扫描数据的配准步骤如下：\n[0020] 设表示深度图像间拓扑关系的模型图为G(V，E)，图G的每个顶点vi∈V均表示一幅深度图像，图G的每一条边ei，j表示顶点vi和vj代表的两幅深度图像间有重叠区域，且这条边的权值是从vi到vj的刚体置换矩阵，S＝(s1，s2，...，sn)是待配准的n幅深度图像的输入序列；\n[0021] 第六步，基于两幅深度图像配准，将多幅深度图像的输入序列S分成k条带状的子序列S＝(W1，W2，...，Wk)，其中Wi∈S，i＝1...k是若干幅深度图像的子序列，Wi中的任意两幅相邻的深度图像都有重叠区域；\n[0022] 第七步，采用向前搜索的策略，合并子序列，根据合并完的子序列构造完整的三维模型。\n[0023] 所述第一步中，根据深度图像Rp和Rq生成纹理图像Ip和Iq的方法为：\n[0024] 对深度图像做Laplacian平滑，得到它的基模型，再计算出深度图像中的每个顶点到基模型上对应顶点的距离，并以每一距离值作为每个顶点在纹理图像上对应像素的亮度值。\n[0025] 所述第二步中，基于SIFT特征提取纹理图像Ip和Iq中的兴趣像素，并通过交叉检验的方法从中找出匹配像素对的候选集C的方法为：\n[0026] (1)使用SIFT算法分别找出Ip和Iq中的兴趣像素集；对于SIFT算法检测出的每一个兴趣像素p，用sift(p)表示p的SIFT特征向量，则定义距离d(p，q)＝||sift(p)，sift(q)||表示两个兴趣像素p和q之间的相似程度，这个距离越小则这两个像素越相似，反之，距离越大则它们差别越大；\n[0027] (2)根据两个像素的SIFT特征向量间的欧式距离，在Ip和Iq的兴趣像素集之间寻找对应的像素，其方法为：\n[0028] (2.1)删除在深度图像中没有对应顶点的兴趣像素；\n[0029] (2.2)对于纹理图像中的兴趣像素i，如果i在深度图像中对应的顶点在深度图像网格的边界上，则删除i；\n[0030] (2.3)对于Ip中的每一个关键像素ip，在Iq中找出使 最小的两个关键像素和 设 定义 和 间的差异度为 并预先定义差\n异度阈值δdiff，如果 则 和 间有明显差异，可作为ip的对应像素，否则p p\ni 在Iq中有多重对应，应舍弃i，当 时，再以同样的方法在Ip中找出像素\np p\n的对应像素 如果 和i 为同一个像素，则i 和 是Ip和Iq间的一对候选对应像素，将加入候选集C，否则仍认为ip在Iq中没有对应像素。\n[0031] 所述第三步中，使用自适应的RANSAC算法，根据几何信息约束找出候选集C中正确的匹配像素对的方法是：\n[0032] (1)对候选集C中所有元素(ip，iq)根据d(ip，iq)以升序进行排序，并将结果放入一个队列L中；\n[0033] (2)检验L中前l个元素是否是正确的匹配，检验方法为：\n[0034] (2.1)从L的前l个元素中随机选取3个元素作为一个样本；\n[0035] (2.2)根据3对匹配像素在深度图像中对应顶点的几何信息计算出刚体置换矩阵；\n[0036] (2.3)根据对应顶点的几何信息，判断其余L-3个元素在此刚体置换下是否为正确的匹配；正确匹配的元素为内点，其余的为外点，所有内点组成本次采样的一致集，然后根据内点的数目更新采样次数上限；\n[0037] (2.4)重复以上步骤(2.1)-(2.3)，直到循环次数达到采样次数上限，然后找出一致集中元素最多(即内点数目最多)的采样，并将这次采样的一致集作为正确的匹配的元素集。\n[0038] 所述第六步中，基于两幅深度图像配准，将多幅深度图像的输入序列分成若干条带状的子序列的步骤为：\n[0039] (1)将s1加入第一个子序列W1中；\n[0040] (2)依次配准序列S中所有相邻的深度图像si，si+1∈S，i＝1...n-1，如果si与si+1有重叠区域，则将si+1加入si所在的子序列，否则将si+1加入一个新的子序列，并在图G中加入相关的边。\n[0041] 所述第七步中，采用向前搜索的策略，合并这些子序列，并根据合并完的子序列构造完整的三维模型的步骤为：\n[0042] (1)对子序列Wi∈S，i＝2...k中的每幅深度图像，依次检索子序列Wj∈S，j＝i-1...1中是否存在深度图像和Wi中的深度图像有重叠区域，如果存在这样的深度图像，那么就可以将Wi和Wj合并，即将Wj中的各元素插入到Wi的首元素之前，同时在图G中加入相关的边；\n[0043] (2)不断循环步骤(1)，直至只剩余一个子序列，或者在剩余子序列Wi中任意两个间都不存在重叠区域；\n[0044] (3)根据图G重建整个模型。\n[0045] 本发明与现有技术相比的有益效果在于：\n[0046] (1)本发明从P和Q中提取纹理图像Ip和Iq或根据深度图像Rp和Rq生成纹理图像Ip和Iq，与传统的基于局部几何特征匹配的方法相比，当纹理图像已知时，本发明方法不计算每个顶点的几何特征值，极大提高了速度，且能很好的处理存在几何噪声的数据。\n[0047] (2)从P和Q中提取纹理图像Ip和Iq或根据深度图像Rp和Rq生成纹理图像Ip和Iq，与已有的基于纹理信息的配准方法相比，当纹理图像未知时，本发明方法可以根据三维空间中顶点的低维几何特征生成纹理图像，明显更具通用性。\n[0048] (3)与传统的基于局部几何特征匹配的方法相比，本发明基于SIFT特征提取纹理图像Ip和Iq中的兴趣像素，并通过交叉检验的方法从中找出匹配像素对的候选集C，能够利用图像配准方法找出顶点间的对应关系，当处理复杂模型的扫描数据时具有明显的速度优势。\n[0049] (3)与已有的结合纹理图像的配准方法相比，本发明方法采用基于SIFT特征提取纹理图像Ip和Iq中的兴趣像素，并通过交叉检验的方法从中找出匹配像素对的候选集C，即引入了对兴趣像素交叉检验的过程，并结合深度图像挑选正确的匹配像素，提高了配准结果的准确性。\n[0050] (4)本发明将多幅深度图像的输入序列S分成若干条带状的子序列，采用向前搜索的策略，合并子序列，根据合并完的子序列构造完整的三维模型，对于输入的多幅深度图像，这种基于分治策略的方法可以快速生成模型图，避免了传统方法中对任意两幅深度图像都要做配准的问题，极大的提高了多幅视图配准的速度，因此极大地减小了整个多幅配准过程的时间。\n附图说明\n[0051] 图1为本发明的两幅深度图像配准过程流程图；\n[0052] 图2为本发明实施例的两幅深度图像的自动配准过程，其中：(a)是两幅待配准的深度图像，(b)是从扫描数据中提取的两幅纹理图像，其中白点表示两幅图像间的对应像素，(c)中的黑点是纹理图像间的对应像素在三维空间中对应的顶点，(d)是最终的配准结果；\n[0053] 图3为本发明实施例的多幅深度图像的配准过程，对于输入的13幅深度图像，先对所有相邻的两幅数据做配准，这样可以将整个扫描序列分成5个条带状子序列，然后合并这5个子序列，最终生成一个完整的模型。\n[0054] 图4、5、6、7分别为采用本发明方法的不同模型扫描数据的配准结果，其中图4为大足一号模型的配准结果，图5为大足二号模型的配准结果，图6为Buddha模型的配准结果，图7为兵马俑模型的配准结果。\n具体实施方式\n[0055] 如图1所示，本发明包括两幅扫描数据的配准和多幅扫描数据的配准过程，具体如下：\n[0056] 1.从扫描数据中提取或生成纹理图像。\n[0057] 设P和Q是待配准的扫描数据，P的纹理图像和深度图像分别是Ip和Rp，Q的纹理图像和深度图像分别是Iq和Rq。若P和Q中已包含纹理图像，则直接提取它们并转换成灰度图像作为Ip和Iq，若P和Q中不包含纹理图像或者包含的纹理图像无法配准时，则首先根据深度图像生成纹理图像。\n[0058] 给定一幅深度图像R，则 令Γ是一种几何特征描述符，\nΓ(v)表示v处的特征值，可以对所有顶点的特征值做线性变换，使得它们的值域为[0，1]，那么定义由Γ生成的纹理图像 这样即可根据三维空间的几\n何特征Γ生成一幅二维纹理图像。理论上任何一种几何特征描述符都可被用来生成纹理图像，但考虑到算法的效率和结果的准确性，则希望Γ具有很好的区分度，并且易于计算。\n[0059] 本发明生成纹理图像的基本思想是：设扫描数据中包含的深度图像是\n0\n而 是对R 做k次平滑后得到的基模型，其\n中 是 经平滑后的对应点，那么定义 i＝1...n，其中\n是 处的法向量。具体实现中，本发明使用基于网格的\n0 0\nLaplacian平滑得到基模型.由于深度图像R 中已蕴含点云的二维结构信息，故网格化Rk k k\n是简单并快速的。在平滑过程中，顶点间拓扑关系保持不变，设M ＝(V，E)为R 对应的k k\n三角网格，其中V 和E分别代表顶点和边的集合， 是M 的边界. 则\n其中N(i)＝{j|(i，j)∈E}，di＝|N(i)，在实验中，一般取k＝64。\n[0060] 2.找出纹理图像间对应像素的候选集。\n[0061] (1)考虑到SIFT特征不但对图像的缩放和旋转具有不变性，同时在光照变化、噪声、遮挡和较小的视点变化等条件下也有较好的鲁棒性，本发明使用SIFT算法分别找出Ip和Iq中的兴趣像素集；\n[0062] (2)在Ip和Iq的兴趣像素集之间寻找对应的像素，对于SIFT算法检测出的每一个兴趣像素p，用sift(p)表示p的SIFT特征向量，则定义距离d(p，q)＝||sift(p)，sift(q)||表示两个兴趣像素p和q之间的相似程度，这个距离越小则这两个像素越相似，反之，距离越大则它们差别越大。由于深度图像间可能存在角度变化以及纹理图像自身的复杂性，简单使用SIFT特征向量的欧氏距离作为评价标准来寻找对应像素，经常会引入大量错误的匹配，同时由于使用SIFT算法找出的兴趣像素过多，本发明采用以下步骤找出两幅纹理图像间对应像素的候选集C，其具体过程为：\n[0063] (2.1)为保证结果集中的像素在深度图像中都有对应的顶点，删除在深度图像中没有对应顶点的兴趣像素；\n[0064] (2.2)对于纹理图像中的兴趣像素p，如果p在深度图像中对应的顶点在深度图像网格的边界上，则删除p；\n[0065] (2.3)通过交叉检验的方法找出Ip和Iq间对应像素的候选集。对于Ip中p\n的每一个关键像素i，在Iq中找出使距离 最小的两个关键像素 和 不妨设\n定义 和 间的差异度为 并预先定义差异度\np\n阈值δdiff，如果 则认为 和 间有明显差异，可作为i 的对应像素，否则p p\n认为i 在Iq中有多重对应，应舍弃i，当 时，再以同样的方法在Ip中找出\np p\n像素 的对应像素 如果 和i 为同一个像素，则认为i 和 是Ip和Iq间的一对候选对应p\n像素，将 加入候选集C，否则，仍认为i 在Iq中没有对应像素。在实验中，一般取δdiff＝0.2。\n[0066] 3.根据深度图像选取正确匹配像素的集合\n[0067] 单纯使用SIFT特征向量找出的对应像素候选集C中仍包含错误的匹配，需要引入其他的方法找出C中正确匹配的像素对.在像素对应顶点的三维信息已知的情况下，完全可以用三维空间的约束条件来判断匹配的正确性。本发明结合顶点的三维信息，使用一种自适应的RANSAC算法，从候选集C中找出正确匹配的像素对，其方法为：\np q p q\n[0068] (1)对候选集C中所有元素(i，i)根据d(i，i)以升序进行排序，并将结果放入一个队列L中；\n[0069] (2)由于恢复一个刚体置换矩阵最少只需要三维空间中不共线的三对匹配顶点，因此本发明只检验L中前l个元素是否是正确的匹配，实验中一般取l＝50。\n[0070] (2.1)从L的前l个元素中随机选取3个元素作为一个样本；\n[0071] (2.2)根据这3对匹配像素在深度图像中对应顶点的几何信息计算出刚体置换矩阵；\n[0072] (2.3)根据对应顶点的几何信息，判断其余l-3个元素在此刚体置换下是否为正确的匹配。正确匹配的元素为内点(inlier)，其余的为外点(outlier)，所有内点组成本次采样的一致集(consensus set)，然后根据内点的数目更新采样次数上限；\n[0073] (2.4)重复以上三步，直到循环次数达到采样次数上限，最终取内点数目最多的采样的一致集作为结果集作为正确的匹配的元素集。\n[0074] 4.找出正确匹配像素对在深度图像中对应的顶点对，并使用基于四元数的方法计算出两幅深度图像间刚体置换矩阵的估计值。\n[0075] 在深度图像和纹理图像间存在映射Fp∶Rp→Ip和Fq∶Rq→Iq。由于本发明算法在第2、3步中可以保证结果集Gr中的像素对在深度图像中都能找到对应顶点，即使得 故一旦找出Cr，即可根据Fp和Fq找出Rq和Rq间的对应顶\n点集，再用Horn的方法求解刚体置换矩阵。\n[0076] 5.精细配准\n[0077] 一旦计算出两幅深度图像间刚体置换矩阵的估计值，就可以使用ICP算法或其变种以这一结果为初始状态，完成迭代优化。在精细配准过程中，本发明改进了经典的ICP算法：首先，在迭代过程中不考虑位于深度图像边界上和临近边界的顶点，这样可以取得更好的准确性；其次，依照每次迭代时对应点的距离和来动态调整距离阈值，这样在每次迭代过程中，只有阈值范围内的对应点用于计算新的变换矩阵和最小化对应点的距离和。\n[0078] 在精细配准过程中，如果对应点的距离和不收敛，或者收敛于一个超过了预先定义阈值的值，则认为无法配准这两幅深度图像，即这两幅深度图像间粗略配准的结果不正确或根本不存在重叠区域。在多幅深度图像配准的过程中，这一准则被用来判别两幅深度图像是否存在重叠区域。\n[0079] 多幅扫描数据的配准步骤如下：\n[0080] 在配准n幅深度图像时，设表示深度图像间拓扑关系的模型图为G(V，E)，其中，图G的每个顶点vi∈V均表示一幅深度图像，|V|＝n，图G的每一条边ei，j表示顶点vi和vj代表的两幅深度图像间有重叠区域，且这条边的权值是从Vi到vj的刚体置换矩阵，易知，若ei，j存在则ej，i也存在，且其权值是ei，j的逆矩阵.图G的生成树表示由这些深度图像构建完整模型的最小元素集，因此一旦构建出图G，就可以通过寻找G的生成树来重建完整的模型。\n[0081] 6.基于两幅深度图像配准，将多幅深度图像的输入序列分成若干条带状的子序列。\n[0082] 设S＝(s1，s2，...，sn)是待配准的n幅深度图像的输入序列，当配准这些数据时，本发明同样需要建立模型图G(V，E)，尽管可以对S中任意两幅深度图像做一次配准以判断它们是否有重叠区域，若有则计算出相关的刚体置换矩阵，从而构造出图G中所有的边。但当处理大规模数据时，这是一项非常耗时的任务。在Pingi的扫描策略下， si与si-1及si+1间均存在重叠区域，这样就可以依次对相邻的两幅深度图像si，si+1∈S(i＝\n1...n-1)做配准，从而构造出图G，并保证图G是连通的。然而，Pingi的这种扫描和配准的策略过于理想，在实际中很难保证S中相邻的两幅数据si，si+1(i＝1...n-1)间均存在重叠区域。本发明假定用户在扫描时会按照一定顺序，即以条带状的方式完成扫描，但是每两个扫描条带间不一定连续，即前一条带的最后一幅深度图像和下一条带的第一幅深度图像间不一定存在重叠区域，在此假设下，序列S可以被分成k个条带状子序列：S＝(W1，W2，...，Wk)， 均满足Pingi的假设，即Wi中任意两幅相邻的深度图像都有重叠区域。具体划分方法是：\n[0083] (1)将s1加入第一个子序列W1中；\n[0084] (2)依次配准序列S中所有相邻的深度图像si，si+1∈S，i＝1...n-1，如果si与si+1有重叠区域，则将si+1加入si所在的子序列，否则将si+1加入一个新的子序列，并在图G中加入相关的边。\n[0085] 7.采用一种向前搜索的策略合并这些子序列，并构造完整的三维模型。\n[0086] (1)对子序列Wi∈S，i＝2...k中的每幅深度图像，依次检索子序列Wj∈S，j＝i-1...1中是否存在深度图像和Wi中的深度图像有重叠区域，如果存在这样的深度图像，那么就可以将Wi和Wj合并，即将Wj中的各元素插入到Wi的首元素之前，同时在图G中加入相关的边；\n[0087] (2)不断循环过程(1)，直到只剩余一个子序列，或者在剩余子序列中任意两个间都不存在重叠区域，前者表明图G是连通的，即可以找出它的一棵生成树并构造出完整的模型；而在后一情形下，每个剩余的子序列均代表模型的一个部分，但是使用本发明的自动配准算法无法将这些部分再拼接起来。\n[0088] (3)根据图G的生成树重建整个模型\n[0089] 显然，Pingi提出的策略可以看作本发明的一个特例。与传统的需要配准任意两\n2\n幅扫描数据的O(n)时间复杂度的多幅配准方法相比，采用本发明的方法，同一子序列中的扫描数据不会再做配准，因此极大的减小了整个多幅配准过程的时间。\n[0090] 如图2所示，(a)是两幅待配准的深度图像，(b)是从扫描数据中提取的两幅纹理图像，其中白点表示两幅图像间的对应像素，(c)中的黑点是纹理图像间的对应像素在三维空间中对应的顶点，(d)是最终的配准结果；图2以实例说明了两幅深度图像自动配准的过程。\n[0091] 如图3所示，对于输入的13幅深度图像，先对所有相邻的两幅数据做配准，这样可以将整个扫描序列分成5个条带状子序列，然后合并这5个子序列，最终生成一个完整的模型。\n[0092] 如图4、5、6、7分别为采用本发明方法的不同模型扫描数据的配准结果，图4为大足一号模型的配准结果，图5为大足二号模型的配准结果，图6为Buddha模型的配准结果，图7为兵马俑模型的配准结果。其中，大足一号模型和大足二号模型的扫描数据中包含了纹理图像，可以直接基于已知纹理图像来配准，而Buddha模型和兵马俑模型的扫描数据中没有包含纹理图像，需要先根据深度图像生成纹理图像，再基于生成的纹理图像来配准。从配准结果来看，对于包含纹理图像和不包含纹理图像的扫描数据，本发明均可以很好的配准它们。