多幅深度图像自动配准方法

1.多幅深度图像自动配准方法，包括两幅深度图像配准过程和多幅深度图像全局匹配过程，其特征在于步骤如下：
所述的两幅深度图像配准如下：
(1)在两幅图像上分别计算SIFT特征，得到每个特征点对应一个128维特征向量；
(2)根据步骤(1)所述的特征向量，匹配对应点；
(3)确定匹配对应点之后，采用RANSAC算法求解基础矩阵，然后采用基础矩阵剔除匹配错误的对应点；
(4)将剔除匹配错误后的对应点按SIFT特征距离排序，去掉两幅图像的特征向量之间距离最大的20％的对应点；
(5)根据步骤(4)中得到的去掉两幅图像的特征向量之间距离最大的20％的对应点，采用四元数法求得变换矩阵，从而得到两两粗略配准；
(6)两两粗略配准后，使用ICP算法精确配准两幅深度图像；
所述的多幅深度图像全局匹配过程如下：
(7)根据步骤(6)得到的两两精确配准的两幅深度图像，建立多幅图像的模型图；
(8)求得模型图的导出圈基，建立导出圈基的邻接关系图Γ，所述的导出圈基是指没有弦的导出圈构成的基；起点和终点为同一顶点的基本通路称为圈，一条边连接一个圈中的两个顶点，但它并不是圈中的边，称为弦；
(9)搜索圈空间，所述的圈空间为模型图中所有回路的集合，在搜索时只搜索导出圈基的邻接关系图Γ中的连通顶点生成的圈，并且得到一个一致圈时，就删掉一个圈基，直到Γ所剩余的顶点个数小于要搜索的顶点个数为止，得到多幅图像的全局匹配；所述步骤(9)中的对于得到一个一致圈的判断方法：从圈中任取一幅深度图像，求得它的直径d，将该深度图像沿着圈中的两两变换变换一周，得到一幅新的深度图像，计算新的深度图像和初始深度图像对应点之间的误差e，将e/d作为圈的误差，如果圈的误差小于设定阈值圈就是一致的，否则，是不一致的；
所述步骤(2)中采用双向交叉方法匹配对应点，其步骤为：匹配对应点时，对于第一幅图像上的特征点p，其有一个特征向量，在第二幅深度图像的所有特征向量中找到距离特征点p的特征向量最近的特征点p′，反过来对于p′，在第一幅深度图像的所有特征向量中找到距离特征点p′的特征向量最近的特征点p″，如果p＝p″，则p与p′为匹配对应点；
所述步骤(7)中所述的模型图G＝是一个无向图，V是顶点的集合，E是边的集合，每个顶点vi∈V表示一幅深度图像，每一条边eij＝(vi，vj)∈E，当且仅当深度图像vi和vj的两两配准结果Tij存在，并且Tij作为边eij的属性，其中vi和vj是模型图的两个顶点。
2.根据权利要求1所述多幅深度图像自动配准方法，其特征在于：所述的步骤(6)后还要判断两两配准结果是否正确，判断步骤为：首先，在根据SIFT特征匹配对应点时，如果匹配成功的对应点数小于设定阈值，则判定配准不正确；其次，使用ICP算法精确配准时，如果误差过大，大于设定阈值，则判定配准不正确；如果以上两个条件均无法判定配准结果错误，则认为结果正确。

多幅深度图像自动配准方法\n技术领域\n[0001] 本发明属于计算机虚拟现实技术领域，具体地说是涉及多幅深度图像自动配准，得到完整模型，该方法可用于三维模型的几何建模。\n背景技术\n[0002] 近些年来，三维扫描技术快速发展，使得自动配准技术变得越来越重要。深度图像是三维扫描设备扫描后得到的带有深度信息的图像。配准是指将从不同位置、不同角度扫描到的深度图像通过刚性变换变到同一坐标系的过程。通过配准，将多幅深度图像拼接到一起，从而获得完整的三维模型。配准计算过程主要可分为两幅深度图像配准和多幅深度图像配准。两幅深度图像配准是计算两幅图像之间的相对位置关系进行配准；多幅深度图像配准也称全局配准是在两幅深度图像配准的基础上，去除错误的两两配准结果，计算全局一致的配准结果，然后优化全局配准的总体误差。\n[0003] 两幅深度图像配准主要包括粗略两两配准和精确两两配准两步。精确两两配准主要采用ICP(Iterative Closest Point)算法(参见P.J.Besl，N.D.McKay.A Method for Registration of3DShapes.IEEE Trans.Pattern Anal[J].and Machine Intell.Vol.14，pp.239-256，1992和Y.Chen，G.Medioni.Object Modeling by Registration of Multiple Range Images[J].IEEE Conference onRobotics and Automation，pp.2724-2729，1991.和 [Rusinkiewicz2001]Rusinkiewicz，S.，Levoy，M.Efficient Variants of the ICP Algorithm[J].In International Conference on3D Digital Imagingand Modeling，\n2001.)，已经取得了很好的效果，但是，由于ICP算法是局部收敛的，所以在采用ICP算法之前，先要进行两两粗略配准，以获得较好的初始位置，避免陷入局部最优。两两粗略配准主要利用特征描述符，如旋转图像、积分球体等，匹配至少三对或者更多对应点，进而求得刚性变换。\n[0004] 全局匹配是在两两配准基础上，判断两两配准的正确性，去掉错误结果，得到整体一致的配准结果。Huber(参见Huber D.Automatic Three-dimensional Modeling from Reality.CarnegieMellon University，2002)提出了第一个全局匹配算法。他利用可见性标准，判断深度图像之间是否存在遮挡，进而判断配准是否正确，并利用贝叶斯概率得到每个配准的可靠性系数，然后，使用贪心法，生成一颗配准整个模型的最小生成树。但每次遮挡判断之前都要优化总体误差，而且遮挡计算复杂度也比较高，因此计算效率比较低。而且在计算生成树开始阶段，由于只有较少的深度图像聚合到一起，所以遮挡性判断的可靠性也较低。Hunag(参见HuangQ X，Flory S，Gelfand N，Hofer M，Pottmann H.Reassembling fractured objects by geometricmatching.ACM Transactions on Graphics(SIGGRAPH)，\n2006：569—578)改进了Huber的方法，他注意到两个多幅深度图像合并的子模型之间可能存在多个两两配准关系，这比单一关系要可靠，因此他优先合并有更多相容配准关系的子图，而不是仅仅依赖单一配准结果求最小生成树，但该方法还是要多次优化总误差，计算复杂度高，在模型合并初期同样可靠性不高。注意到子模型间的多个相容配准关系，实质上是构成了回路，而且两两配准结果在回路中要满足一致性约束。\n[0005] 全局匹配后需要优化总体误差。与ICP算法类似，通过迭代逐渐减小误差，但由于涉及到多幅深度图像，所以计算更为复杂。全局配准算法主要分为两类，两两优化Bergevin和Pulli(参见Bergevin R.，Soucy M.，Gagnon H.，et al.Towards a General Multi-View RegistrationTechnique.IEEE Trans.Pattern Anal.and Machine Intell，\n1996，18(5)：540-547 和 Pulli K.Multiview Registration for Large Data Sets.nternational Conference on3D Digital Imaging andModeling)和同时优化Krishnan和Neugebauer算法(参见Krishnan S.，Lee P.Y.，Moore J.，etal.Global Registration of Multiple3D Point Sets via Optimization-on-a-Manifold.Proc.ofSymposium on Geometry Processing，2005：187-196 和 Neugebauer P.J.Geometrical Cloning of3D Objects via Simultaneous Registration of Multiple Range Images[C].Proceed-ings of the1997International Conference on Shape Modeling and Applications(SMA’97)，\n1997，130)。两两优化反复采用ICP算法优化两幅图像，因此收敛速度慢而且可能无法收敛，同时优化的方法直接优化总误差，收敛速度较快，但复杂的优化计算稳定性较差。\n发明内容\n[0006] 本发明的技术解决问题：克服现有技术的不足，提供一种多幅深度图像自动配准方法，该方法进行多幅深度图像配准速度快，且匹配准确。\n[0007] 本发明的技术解决方案：多幅深度图像自动配准方法，包括两幅深度图像配准和多幅深度图像全局匹配过程，其中：\n[0008] 所述的两幅深度图像配准如下：\n[0009] (1)在两幅图像上分别计算SIFT特征，得到每个特征点对应一个128维特征向量；\n[0010] (2)根据步骤(1)所述的特征向量，匹配对应点；\n[0011] (3)确定匹配对应点之后，采用RANSAC算法求解基础矩阵，然后采用基础矩阵剔除匹配错误的对应点；\n[0012] (4)将剔除匹配错误后的对应点按SIFT特征距离排序，去掉两幅图像的特征向量之间距离最大的20％的对应点；\n[0013] (5)根据两幅图像的对应点采用四元数法求得变换矩阵，从而得到两两粗略配准；\n[0014] (6)两两粗略配准后，使用ICP算法精确配准两幅深度图像；\n[0015] 所述的多幅深度图像全局匹配过程如下：\n[0016] (7)根据步骤(6)得到的两两精确配准的两幅深度图像，建立多幅图像的模型图；\n[0017] (8)求得模型图的导出圈基，建立导出圈基的邻接关系图 ，所述的导出圈基是指没有弦的导出圈构成的基；\n[0018] (9)搜索圈空间，所述的圈空间为模型图中所有回路的集合，在搜索时只搜索导出圈基的邻接关系图Γ中的连通顶点生成的圈，并且得到一个一致圈时，就删掉一个圈基，直到Γ所剩余的顶点个数小于要搜索的顶点个数为止，得到多幅图像的全局匹配。\n[0019] 所述步骤(2)中采用双向交叉方法匹配对应点，其步骤为：匹配对应点时，对于第一幅图像上的特征点p，其有一个特征向量，在第二幅深度图像的所有特征向量中找到距离特征点p的特征向量最近的特征点p′，反过来对于p′，在第一幅深度图像的所有特征向量中找到距离特征点p′的特征向量最近的特征点p′，如果p＝p′，则p与p′为匹配对应点。\n[0020] 所述的步骤(6)后还要判断两两配准结果是否正确，判断步骤为：首先，在根据SIFT特征匹配对应点时，如果匹配成功的对应点数小于设定阈值，则判定配准不正确；其次，使用ICP算法精确配准时，如果误差过大，大于设定阈值，则判定配准不正确；如果以上两个条件均无法判定配准结果错误，则认为结果正确。\n[0021] 所述步骤(7)中所述的模型图G＝是一个无向图，V是顶点的集合，E是边的集合，每个顶点vi∈V表示一幅深度图像，每一条边eij＝(vi，vj)∈E，当且仅当深度图像vi和vj的两两配准结果Tij存在，并且Tij作为边eij的属性，其中vi和vj是模型图的两个顶点。\n[0022] 所述步骤(8)中的对于得到一个一致圈的判断方法：从圈中任取一幅深度图像，求得它的直径d，将该深度图像沿着圈中的两两变换变换一周，得到一幅新的深度图像，计算新的深度图像和初始深度图像对应点之间的误差e，将e/d作为圈的误差，如果圈的误差小于设定阈值圈就是一致的，否则，是不一致的。\n[0023] 本发明与现有技术相比的优点在于：\n[0024] (1)本发明基于SIFT的特征配准计算速度快，交叉匹配对应点可靠性高，用RANSAC算法过滤对应点，最大程度提高了对应点的可靠性。\n[0025] (2)本发明建立多幅图像的模型图，求得模型图的导出圈基，建立导出圈基的邻接关系图r，在搜索圈空间时只搜索导出圈基的邻接关系图Γ中的连通顶点生成的圈，并且得到一个一致圈时，就删掉一个圈基，直到Γ所剩余的顶点个数小于要搜索的顶点个数为止，得到多幅图像的全局匹配，大大提高了搜索速度，从而快速可靠地得到多幅图像全局一致的配准结果。\n[0026] (3)而且本发明通过圈的一致性判断，进一步提高了多幅图像的可靠性。\n附图说明\n[0027] 图1为本发明方法的流程图；\n[0028] 图2为本发明中建立模型图的示意图；\n[0029] 图3为本发明中采用64个圈的误差分布图；\n[0030] 图4为图3的局部放大图；\n[0031] 图5为采用本发明方法进行自动配准的弥勒下生经变相窟图。\n具体实施方式\n[0032] 如图1所示，本发明分为两幅深度图像配准和多幅深度图像全局匹配过程。\n[0033] 1、两幅深度图像配准\n[0034] 两幅深度图像粗略配准是对处在任意位置的部分重叠的两幅深度图像粗略配准的过程。目的是为精确配准提供较好的初始位置，以确保其收敛。由于深度图像中包含颜色信息，因此本发明采用图像对应点匹配方法进行配准，其步骤为：\n[0035] (1)首先，分别在两幅图像上计算SIFT特征，每个特征点对应一个128维特征向量，采用欧氏距离度量两个SIFT特征之间的距离；在此步骤中计算SIFT特征采用Lowe，D.Distinctive image features from scale-invariant keypoints.Int.J.of Computer Vision60，2，91-110.2004.文中介绍了方法即可。\n[0036] (2)采用双向交叉匹配对应点，即匹配对应点时，对于第一幅图像上的特征点p，其有一个特征向量，在第二幅深度图像的所有特征向量中找到距离特征点p的特征向量最近的特征点p′，反过来对于p′，在第一幅深度图像的所有特征向量中找到距离特征点p′的特征向量最近的特征点p′，如果p＝p′，则p与p′为匹配对应点。\n[0037] (3)匹配之后，采用RANSAC算法求解基础矩阵，以剔除误差点，采用RANSAC算法求解基础矩阵可以参见Hartley，R.I.，AND ZISSERMAN，A.2004.Multiple View Geometry inComputer Vision.Cambridge University Press，Cambridge，UK。\n[0038] (4)然后，将对应点按SIFT特征距离排序，去掉距离最大的20％的对应点。\n[0039] (5)最后，根据对应点使用四元数法求得变换矩阵，使用四元数法的求解变换矩阵的过程可以参见Horn，B.Closed Form Solutions of Absolute Orientation Using Unit Quaternions.Journal of the Optical Society，Vol.4，629-642，1987。\n[0040] (6)两两粗略配准后，使用ICP(Iterative Closest Point)算法精确配准两幅深度图像。ICP算法参见P.J.Besl，N.D.McKay.A Method for Registration of3D Shapes.IEEE Trans.Pattern Anal[J].and Machine Intell.Vol.14，pp.239-256，1992.，每次迭代根据误差动态修改距离阈值，这样得到了两幅深度图像精确的配准的结果。\n[0041] (7)对两幅深度图像精确的配准的结果进行两两配准的一致性判断。特征点匹配错误或两幅深度图像没有部分重叠，都可能造成两两配准结果错误。因此要两两配准是要判断其结果是否正确，判断步骤为：首先，在根据SIFT特征匹配对应点时，如果匹配成功的对应点数小于设定阈值，则判定配准不正确；其次，使用ICP算法精确配准时，如果误差过大，大于设定阈值，则判定配准不正确。如果以上两个条件均无法判定配准结果错误，则认为结果正确，并且将两两配准结果加入到后面多幅图像全局匹配的模型图中。\n[0042] 2、多幅深度图像全局匹配\n[0043] (1)根据得到的两两精确配准的两幅深度图像，建立多幅图像的模型图；\n[0044] 两两配准之后，得到模型图G，但仅仅依靠两两配准的一致性判断得到的结果是不可靠的，例如由于模型的自对称性，造成配准错误，但通过两两配准难以判断出来。因此，两两配准之后，要进行全局一致性判断。由于模型图G的任意回路都应满足一致性约束，否则就是不正确的，这样在一条回路中的配准结果可以自我校验，本发明提出基于回路的全局匹配方法。\n[0045] 模型图G＝是一个无向图，每个顶点vi∈V表示一幅深度图像，边ejj＝(vi，vj)∈E当且仅当深度图像vi和vj的两两配准结果Tij存在，并且Tij作为边eij的属性。值得注意的是，任何一条回路都要满足一致性约束，即总的变换应为单位变换。如图2，在回路16521中，应满足T12·T25·T56·T61＝I。一条回路如果满足一致性约束，则称为一致回路，否则称为不一致。\n[0046] (2)求得模型图的导出圈基，建立导出圈基的邻接关系图r；\n[0047] 先简单介绍有关图、圈和圈空间的概念。一个图G＝，其中V＝v(G)表示顶点集合，E＝ε(G)表示边的集合。每个顶点出现不超过一次的通路称为基本通路(Path)。\n起点和终点为同一顶点的基本通路称为圈(Cycle)。一条边连接一个圈中的两个顶点，但它并不是圈中的边，称为弦(Chord)。一个没有弦的圈称为导出圈(Induced Cycle)。如果图G1和G2没有公共边，则G1∪G2称为图G1和G2的边不重并。环路是指圈与圈的边不重并。显然圈是环路，圈是连通的，但环路不一定连通。图G1和G2的对称差(Syrmnetric Difference)运算定义为 对称差运算满足交换律和结合律。\n[0048] 连通图G＝的所有环路及空集组成的集合为C＝{C1，C2…，Cn}，在其上定义对称差运算与数乘运算0Ci＝Φ，1·Ci＝Gi，则其构成数域Z2＝{0，1}上的一个|E|-|V|+1维线性空间，记作C(G)，称为圈空间(Cycle Space)。任何圈空间都可以由导出圈基以生成整个圈空间。\n[0049] (3)搜索圈空间；\n[0050] 设模型图G的导出圈基为 整个圈空间C(G)由 张成，因\n|E|-|V|+1\n此C(G)的大小为2 ，是指数复杂度，搜索效率太低。模型图中所有一致圈构成了一个线性子空间，称为一致子空间。本发明提出一种快速求得一致子空间的一组基的方法，大大提高了圈空间的搜索效率，理想情况下是线性复时间杂度。\n[0051] 注意到如果两个圈的对称差仍为圈，那么这两个圈必有公共边。为了加速搜索，首先定义圈基的邻接关系图 L>，边(Bi，Bj)∈L当且仅当ε(Bi)∩ε(Bj)≠Φ。因此有以下结论：设 如果C是圈，那么在 L>中 ， ，…， 是\n连通的。注意由Γ中连通的顶点所对应的圈基生成的环路也可能不是圈，因此还要检验其是不是圈。这样在搜索圈空间时，只要搜索由任意多个连通的基生成的所有圈，判断它们的一致性，这样可以大大减少搜索次数。\n[0052] 在搜索一 致圈时，首先 根据两两配 准的模型 图G求出导出圈 基并且生成 的邻接关系图 L>，采用导出圈基是因为它的长\n度较小，因而一致的可能性较大，有助于提高搜索效率。然后求S(G)的一组基，首先，判断每个圈C＝Bi是否一致，如果一致，则将C加入到S(G)的基中，并从Γ中删除Bi；然后判断由任何两个连通的圈基生成的圈 是否一致，如果一致，将C加入到S(G)的基中，并从Γ中删除Bi；然后判断由任何三个连通的圈基生成的圈，这样下去，直到Γ中剩余的顶点小于要搜索的连通顶点个数为止。然后，将所有一致圈的边合并得到一致模型图G′，详细算法在算法1中给出。该算法在最好情况下是线性复杂度，与指数复杂度相比，大大提高了计算效率。如果G′只有一个连通子图，则全局配准计算完成。如果G′有多个连通子图，则连通子图之间不再存在一致回路，本发明采用基于可见性的判断方法——自由空间冲突(Free Space Violation)继续全局配准[Huber2002]，生成连通子图之间的最小生成树，以合并更多的子图。因为一般情况下，每个连通子图都含有多幅深度图像，所以，相对于单幅图像而言，可见性判断具有更高的可靠性。\n[0053] \n[0054] \n[0055] (4)圈的一致性判断；\n[0056] 求得一个圈之后，要判断其是否一致。一个圈是一致的，是指圈中的总的两两变换近似单位变换。设圈C＝V1V2…VnV1，任取一幅深度图像Vi，求得Vi到Vi回路中总变换T＝Ti.i+1…Tn，1…Ti-1，i，Ti，j表示Vj到Vi的变换矩阵。计算圈中总的变换误差为其中pk∈Vi为深度图像Vi中的点，n表示Vi中点的个数。\n[0057] 设深度图像Vi的包围球直径为d。如果ε<