一种3d模型的配准算法(关键翻译)

1、一种3D模型的配准算法PaulJ.Besl,Member,IEEE,andNeilD.McKay摘要本篇文章描述精确和有效计算包含自由形态曲线和自由形态平面的3D模型的通用、独立表示的方法。该方法基于ICP算法处理“全六自由度”需要一个给定的点的几何实体发现最近点的程序。ICP算法总是对均方差度量的局部最小值单调收敛，实验表明在第一次迭代中收敛的比例加快。因此，通过测试每一次最初的配准为一个复杂模型的详细数据给出一个适当的初始旋转和转化能最小化“全六自由度”距离度量的均方差（错译）例如，一个已知的“model"模型和一个“data"模型代表着一个模型（考虑到复杂模型）的主要

2、部分通过一个最初变换还有一个相对较小的一系列旋转能在几分钟内配准。这个算法的一个主要应用就是在模型检查之前使用一个理想的几何模型记录读出数据。这个方法适用于决定基本问题上，比如不同几何体表达式的全等还有估算一致性不确定的点集的轨迹。实验的结果证明了这个配准算法在点集、曲线和曲面上的性能。自由形态曲线配准、自由形态曲面配准、运动估计、位姿估算、四元数、3D配准1介绍自由形态曲线、曲面、点集的全局和部分模型匹配度量在“几何建模与计算机视觉”中已经被描述出来，试图在计算机视觉中形式化和统一这个关键问题的描述：在一个传感器坐标系中已知3D数据，描述了一个可能和模型形状一致的数据模型，已知模型坐标系中的

3、模型形状，估算最理想的旋转变换，对齐或者配准模型形状和数据模型，最小化两个形状的距离，经由一个均方差度量最终决定等价模型。许多应用主要关注一下几个问题：一个深度图像的分割区域和在一个CAD模型中的B样条曲面子集匹配吗？本文为自由曲面匹配问题（该问题已经在“几何建模与计算机视觉”中定义，“自由形态曲面匹配问题”作为一个特例）提供了一个简单的、一般的、统一的方法，这个解决方法已经推及到n维度已经为以下问题提供了解决方案:1）无一致性的点集匹配问题；2）自由形态曲线匹配问题。该算法要求无提取特征，无曲线或平面派生，还有无3-D数据预处理（除了统计数据异常的排除）。此次提出的方法主要应用于在模型检查前

4、使用几何模型从移动的精确装置中记录数位化资料。当使用高精确无触点的测量设备在一个浅深度区域检查模型时，不同的感测点所得的数据并没有太大的变化。因此，出于简化的目的还有存在基于与检测应用相关的大量数据，在大量数据之中的不相等的点集并不在考虑之中。相似的排除异常值被视为进程的一个步骤，同样的，同样的这个步骤可能会是一个最好的手段，也可能不会被处理。在检测应用的环境中，假定一个有能够排除明显误差的感应器、高精准、无触点的检测设备，没有产生不良数据，数据合理。这个模型配准算法可以通过下列几个几何数据表达式应用：1）点集；2）线段集（折线）；3）隐性曲线：；4）参数曲线：；5）三角形集合；6）隐性曲面：

5、；7）参数曲面：这些包含了大多数应用将要利用一个方法匹配3D模型，其它的表达式通过一个估算已知模型到已知数字化点的最近点的程序处理。本文结构如下：首先回顾数个相关的论文；接下来会提及计算包含上文的集合表达式的一个模型到一个已知点的最近点的数学初步；然后介绍迭代最近点算法，一个证明关于其单调收敛性质的定理。初次配准的问题会在接下来提到。最后，从提供的点集、曲线、曲面集展示迭代最近点算法的性能。2文献回顾相关的一些工作已经被发表在3D自由形态模型的配准领域。目前有关于整体形状匹配或者配准的大部分的文献资料局限于特定的类型或者形状，也就是说1)多面模型；2)分段-二次曲面模型；3) 一致性已知的点集

6、；读者可能会查阅1985年以前的相关资料。为而来的其它最近的相关采集工作在下文中不会介绍，读者请阅读以下文章(引用)。从历史的观点上来说，使用3D数据匹配自由形态模型的工作早已经被Faugeras还有他在法国国家信息与自动化研究所(简称INRIA)的团队完成，早在1980年，他们就有效的匹配了法国雷诺公司的汽车配件。这个工作使得在计算机视觉团队中为3D点集的一致性使用四元数进行最小二乘法配准变得非常普及。选择性的使用SVD算法在这个时间范围内并不被世人所周知。这个工作的初始限制就是它依赖在自由形态模型中合理的大型2D区域中可能的存在。1985年，Schwartz和Sharir对没有抽取特征的自

7、由形态空间曲线匹配问题开发了一个解决方法。他们使用一个非四元数近似处理最小二乘法旋转矩阵。这个方法适用于处理质量合理的曲线数据，但是不适用面对有噪声的曲线数据，因为这个方法对曲线使用弧长抽样法获得一致点集。Haralicketal.发表了3D点集位置估算问题使用鲁棒性方法结合最小二乘法SVD配准方法，提供了一个鲁棒性统计量，选择性的最小二乘法或SVD点集进行匹配。这个算法能够处理统计的离群值而且只要标准正交矩阵的行列式为正就能够理论上被四元数算法取代。一个最近的会议议程里就包涵这个领域的贡献。Horn根据Faugera的最小二乘法四元数匹配提出了一个选择性使用4x4矩阵最大特征值代替最小特征值

8、的构想。Horn和Brou也发展了扩展高斯图像EGI方法允许曲线匹配还有基于曲面正常直方图的非凸模型的受限制集合的匹配。以上都是一些专家的研究。简单介绍，不必深究。3数学初步在这一部分，描述了在不同的几何表达式上计算一个已知点的最近点的方法。首先，内容包括基础几何实体、参数实体、隐性实体。读者可能需要查阅Mortenson的相关知识以扩充知识框架。欧式距离：，设A是点集中的一个点表示为;点到点A的欧氏距离就是：(1)A的最近点满足公式。设L为连接点与点的线段。点到线段L的欧式距离为：(2)，&，这个要求直接进行闭型计算。设L属于线段集合表示为，再令。点到线段集L的欧氏距离为：(3)我们

9、第一步先创造一个计算从一个点到一(14)曲线要求仅计算和。对每位实体，牛顿在线段集L上的最近点满足等式令t是被三个点、定义的三角形。点和三角形t的欧式距离为：，&，&，(4)要求直接进行闭型计算。令T是三角形集合的一个元素表示为，T=,i=1.。点和三角形集T的欧式距离为：(5)在三角形集合T上的最近点满足等式A. 点对参数实体的距离在这部分，一条参数曲线和一个参数曲面被视为一个单独的参数实体，当时代替参数曲线，当时应该代替参数曲面(R表示为实线)。曲线的评估区域是一个区间，但是这个评估区域对于曲面可以是在平面上的一个任意的闭合区域。对于更多的参数实体的信息，例如，Bezier

10、和B抽样曲线/曲面，可以参考其他的文章。从一个给定的点到一个参数实体E的距离为(6)对于距离的估算不是闭型是相对涉及。下面介绍一个对计算点对曲线还有点对曲面距离的方法。一旦对单独实体的距离度量，参数实体的集合直接进行闭型运算。令F属于参数实体集合表示为，再令；i=1.。点到这个参数实体F的距离为：(7)最近点在参数实体集合F上，满足等式个参数实体(线段或三角形)的距离的单行体几何学近似值。对一个参数空间曲线C=，能够计算一个多段线L(C,)比如分段线性近似值绝不脱离空间曲线预先设立的距离，通过相应的参数曲线的论证值u标记多线段的每一点，这能够获得一个估值，这个值就是线段集合的最近点的论证值。相

11、似的，对一个参数曲面,一个能计算三角形集合T(S,)，这个分段三角形的近似值绝不脱离曲面预先设立的距离。通过相应的参数曲面论证值(U,V)标记每一个三角形的顶点，能获得一个估值(，即三角形集的最近点估值。作为这些曲线和曲面的程序的结果，假定一个有效的初值能致的值非常接近参数实体最近点。当一个可信赖的开始的点是可用的时候，点对参数实体的距离问题对使用一个纯牛顿的最小值方法来说是理想的。标量的客观功能最小化为(8)令为向量不同倾斜度操作数。当f=0时最小值产生。当这个参数实体是曲面时，2D倾斜度向量为，2D海塞矩阵为：(9)当客观功能的局部派生为以下：(10)(11)(12)(13)校正公式为：(

12、15)当使用初始点选择方法描述以上基于一个理性小值的单一方法时，牛顿计算最近点在迭代一至五下分成三次的一般收敛方法。这个计算牛顿方法在对比寻找最好初始点时费时较少。B. 点对隐性实体的距离一个定义为空集(可能向量值多元)的隐性参数实体满足。从一个给定点到一个隐性实体的距离I为(16)计算距离的估值不是闭型的，是相对涉及。下面是一个对计算点对曲线还有点对曲面距离方法的概述。一旦实施对独立实体的距离度量那么隐性实体的集合直接进行闭型运算。令J属于参数实体集合表示为,J=,k=1。点到一个隐性实体集合J的距离为(17)在隐性实体上的最近点满足等式我们第一步先通过计算从一个点到一个隐性实体的距离为完成

13、参数实体创造一个单行体几何学近似值(线段或三角形)。计算点到线集合或者是点到三角形集合的距离产生一个近似最近点，这个近似值能被用来计算精确距离。参数实体达到无约束的最优化就足够了，隐性实体距离问题与其完全不同。为了寻找在一个定义为的隐性实体上的最近点，一定要解决在最小化二次的客观功能项目、一个非线性受约束最小化方面受约束的最优化问题,(18)一个解决这个问题的方法是去构建增强的拉格朗日乘数法系统方程式：+=0(19)当，经由数字方法解决这个系统非线性方程式。方程式还有未知的非线性系统的数字为三个2D曲线、四个曲面、还有五个定义好的参数空间曲线。连续方法能用来解决此类代数实体问题(甚至是没有好的

14、初始点)，但是一个好的初始点会允许使用更快的方法，比如多维的牛顿寻根方法。从数字的观点，参数方法更容易解决。从应用的观点，没有工业CAD系统存储在隐性结构下的自由形态曲线或曲面。因为这个原因用我们的工具系统或者经由特殊数学事件或经由参数架构处理隐性曲面的利益。当然，如果这里有一个必要去处理在隐形架构中自由形态隐性实体的申请，以上算法能够实现。Taubin使用一个近似距离算法，该算法蕴含了为曲面和2D曲线简单升级的公式。当g接近为零时：(20)此方法仅在起始点为、方向为的无限线与隐性实体交叉在一点，而这一点向量与无限线同向时精确。在一般情况下并不正确，这个近似值通常更远离隐性实体的点。因此，如果

15、需要精确结果的话不能使用其结果。C相对点集配准所有的最近点(距离最小)算法都提到扩展到N维。一个更必要的程序就是评估产生的最小二乘旋转与变换。对我们的目的来说，在2D和3D中，只要不要求映射，四元数算法比SVD方法更好。SVD方法，基于两点分布的互协方差矩阵，容易推广至n维，当维度大于3为时，此算法可能会成为我们的选择。Horn的解决方法如下尽管等价于Faugeras方法。我们简要的陈述一下SVD互协方差矩阵的重要作用。组成四元数的是四个向量要求，。在本部分的末尾，你会发现，可以由一个单元旋转四元数产生一个3的旋转矩阵令为一个变换向量。完成配准状态的向量被表示为。令P=为测试数据点集，与一个模

16、型点集X=对齐，当还有每个点和与之对应的点有相同的指数。均方差客观的功能的最小化为3是3x3单独矩阵。与特征向量单元相应的是最大化特征向量矩阵Q(上式)被选为理想的旋转。理想的变换向量为:It=总-岡和亦(26)最小二乘四元数运算是O(Np)表示为：(27)QP.X)他)誌兔-凤爾-刑®(P)是被用变换之后t-1dms是最小二乘法点匹配误差。符号来表示点集P在通过配准向量(23)单；点被三角形集合还有线段集合作为起始点与被测试的点集P的质量的重心还有相对的点集X的质心由下列公式给出:点集P与X的互协方差矩阵为:环=*莎-掰i-制=+脸卜就，4'日(24)反对称矩阵Aij=(.

17、)的循环部分被用来构建列向量。这个向量接下来被用于构建对称4x4矩阵Q:的形式。4迭代最近点算法(ICPAlgorithm)既然已经概述了从一个给定的点计算几何形状最近点的方法还有计算最小二乘法配准向量，ICP算法能够依照一个抽象的几何体X(内部表达式必须精确描述算法，但是并不是讨论的中心)描述下来。因此，被很好的应用于一下几个部分：1、点集；2、线段集；3、参数曲线集；4、隐性曲线集；5、三角形集；6、参数曲面集；7、隐性曲面集。在算法的描述中，一个data模型P移动到对齐的model模型X中。data还有model模型可能被表示在任何允许的形式中。对于我们的目的来说，如果data模型没有在

18、点集形式中的话，那么此模型必须被分解为点集。幸运的是，这个很简末尾点使用，如果data模型在曲面或者曲线形式中，那么则使用三角形/线段的起始点和末尾点(上面提到)的近似值。点的数量在data模型中被表示为Np。令Nx为model模型包含的点、线段、或者三角形的数量。如上文说到，曲线与曲面最近点估算实现了我们的系统要求一个线或三角形框架去产出牛顿迭代的初始参数值，因此Nx的数量仍然与这些平滑实体相关但是根据估值的精确性有所不同。单独数据点与model模型x之间的距离度量d被描述为=mn|j：-p|.(28)在X中的最近点产生的最小距离表示为，致d(,)=d(,X),y属于X,(以上除X皆为向量)

19、。标记计算最近点为O(Nx)最坏事件与期望事件log(Nx).当最近点计算(从p到X)被表示为每一个在P中的点时，程序是最坏事件O(NpNx)。令Y表示最近点的结果集，然后令C为最近点操作数：Y=C(P,X)(29)给结果一个相关的点集Y,最小二乘法配准为计算以上描述的:(,d)=Q(P,Y)(30)Data模型点集的位置经由P=校正。A.ICP算法声明c) 应用配准：Pk+1=(P0)(消耗：O(Np)。d) 当变化在方差误差下降到一个预先设定的临界值>0时终止迭代，指定迭代期望精确值为：dk-dk+1<如果期望的是一个无穷小量临界值，能用替代，当model模型的协方差轨迹的平方

20、根表明了这个model模型的大致尺寸时。B.收敛定理ICP算法的收敛定理现在开始证明。大意如下：1、最小二乘法配准每次迭代一般会减少相应的独立点之间的平均距离；2、最近点决定一般减少每个独立点的距离。当然，这个独立距离的缩小减少了平均距离因为正数集合的平均值更小了。在下面的证明中，我们提供一个更详尽的解释。定理：考虑到均方差距离的客观功能，迭代最近点算法对一个局部最小值也单调收敛。证明：给定P_k=(P0)还有X，计算最近点集Y_k=作为上面规定的内部的几何表达式X。均方差误差e_k被下式给出：坯=亍£|角:-除(31操作数Q被用于得到还有：ICP算法陈述如下: 点集P同Np点从da

21、ta模型和model模型X(Nx支持原始几何图形：点、线、三角形)中获取。 迭代是通过设置P0=P,=，k=0初始化。配准向量被定义为与初始数据集P0相关，为了使得最后的配准代表完全变换。步骤1、2、3、4被应用，直到公差r收敛。计算需要的每个操作数已经在方括号中给出。a) 计算最近点Yk=C(Pk,X)(消耗：O(NpNx)最坏事件，O(NpLogNx)平均)b) 计算配准：(,dk)=Q(P0,Yk)(消耗：O(Np)仁f£life-R丽恤-制2(32)D_k<=e_k;假定d_k>e_k如果确实是这样，那么在点集的恒等式变换可以产生一个比最小二乘法配准更小的均方差误

22、差，这个对于这个事件来说是不可能的。接下来令最小二乘配准被用于点集P_0，(37)产生点集Pk+1。如果与早先的点集Y_k相关的被保持，那么均方差误差依旧是d_k，如下式：再令为一个足够小的角度临界值。如果弘<皿(ind弘-i<別(36)foreachi=l.An(34)然而，在随后的最近点操作数应用中，获取了一个新的点集Y_k+1：Y_k+1=C(P_k+1,X)。很明显：因为在通过变换还有在一些与相关的新的距离不变之前点是最近点。如果到的距离比的更远，那么会直接否定C最近点操作数的基础操作数。因此，均方差误差e_k还有的d_k必须服从下列关系：BLSLANDMETflUDFOR

23、RHGlSlRATIONOFIDSHAPkS那么这里有一个为最近三个配准状态向量最好的方向队列：，令d_k,d_k-1,d_k-2为关联的均方差误差，再令v_k,v_k-1,v_k-2，为关联近似值弧长论证值：UnetirTheMe曲瓠ICTAl脚uthi"0<心+：<fit.i<4<for汕1kFig-LConsistenrdirectionalloaccelerationof(heICPalgflrtthm-当然，只要均方差误差不能为负，更低的约束就会产生。因为均方差误差序列不再增长还有约束下降，上面描述的算法对最小值来说一定单调收敛。实验中，我们发现在第

24、一次迭代中的快速收敛因为接近局部最小值而减缓。甚至在减缓的节奏上，一些地方在30和50次迭代的时候产生了精确的结果：d_k0.1%的model模型。在下一部分使用一个简易的附加操作数能精确收敛。C. 一个精确的ICP算法精确的ICP算法在基础线段搜索方法上使用一个较小的变动多元无约束极小值。作为迭代最近点算法程序，一个配准向量的序数被推广为,这些表示了为了局部理想模型匹配进行的恒等式变换在配准状态空间的轨迹。考虑到不同向量序数被下式定义：Pla-ncRepre&cnas7-DSpiCi.!Lint-arlupduie舟nhoMIJjxLik观察上面的形势图fig.1。接下来，用一个线性

25、近似值还有一个抛物线插值计算最近的三个数据点：上式给我们一个可能的线性校正，基于令交叉线上式定义了一个在配准状态空间方向。令在两个最近的方向之间的7个空间的角度表示为：在可靠的一边，我们采集了一个允许的最大(«)一个可能的抛物线校正，基于抛物线极值点：BOTAIIDNfig.2.VariousquantjeicsjoltediicRiiuncomilfarfixbssUonaccclerJicdICPalgorithm*值v_max。下列的逻辑式用来执行一个试图校正：1) 如果0<v_2<v_1<v_max或者0<v_2<v_max<v_1,当在点

26、集上执行校正时使用抛物线校正迭代向量：=+代替一般向量选择性最小化方法，P_k+1=(P_0)。2) 如果0<v_1<v_2<v_max或者0<v_1<v_max<v_2或者v_2<0&0<v_1<v_max，使用基于线段的校正向量代替一般向量。3) 如果v_1>v_max&&v_2>v_max，使用最大值进行允许的校正般的向量。我们已经发现实验时适应性地设置v_max=25|提供了一个好的明智的检查在校正允许迭代最近点算法用一个给定的精度移动到局部最小值在许多更小的步骤中。对一个给定的值进行一个名义上的

27、超过50次ICP迭代是在15至20此迭代的时候就精确了。如果校正配准向量以某种方法超越足够产生一个更坏均方误差的最小值，可能会有利于用最近两步使用新的配准去构造一个新的抛物线并移动到适当的最小值。这个在我们的试验中并不必要。严格的来说，如果建议的校正引起了一个更差的均方误差的话，可以直接忽略。为了提供一个四元数例子，在一样的自由形态曲面匹配测试中使用基础而且精确的ICP算法，通过50次迭代的过程，记录比较关系、配准值、均方根误差(RMSroot-mean-square)、最大值误差、角度变形、还有累积弧长值。基础ICP算法的结果已经在Fig.2中表示出来。注意所有的曲线都是平滑的。最重要的特征是cos()绘图表明所有的校正方向一致除了第一次迭代。与此相反加速的ICP算法显示出令人满意跳跃性的表现(图Fig.3)。另外，注意在第一次和紧接着的第二个加速过程，大多数特性接近他们的最终结果。加速步骤发生了当V-型下降发生在cos()图与迭代次数相对抗。D选择性最小值方法比较用其它的可选项，ICP算法允许我们相对快速地用7步从一个给定的开始点移动到一个局部最小。每一次迭代要求仅仅一个最近点