第３０卷第１１期 ２０１３年１１月 计算机应用研究 Ａｐｐｌｉｃａｔｉｏｎ Ｒｅｓｅａｒｃｈ ｏｆ Ｃｏｍｐｕｔｅｒｓ Ｖｏ１．３０ Ｎｏ．１１ ＮＯＶ．２０１３ 一种基于形状描述的模型配准方法术 刘学术 （大连理工大学工业装备结构分析国家重点实验室运载工程与力学学部汽车工程学院，辽宁大连１１６０２４） 摘要：针对模型配准中需要预配准操作的问题，提出了一种基于几何形状描述的模型配准方法。首先利用一 种基于距离场的几何形状描述方法从预配准模型中获取特征点并建立对应关系，即构造预配准模型间的特征点 对；之后，以特征点对为基础计算模型配准所需的转换矩阵以实现对模型的一步精确配准。实例表明该方法在 不需要对模型进行预配准操作的情况下可实现模型的精确配准。 关键词：特征点；形状描述；模型配准 中图分类号：ＴＰ３９１．４１ 文献标志码：Ａ 文章编号：１００１—３６９５（２０１３）１１－３４９２—０３ ｄｏｉ：１０ ３９６９／ｊ．ｉｓｓｎ．１００１－３６９５．２０１３，１ １．０７５ Ｎｅｗ ａｐｐｏａｃｈ ｔｏ ｍｏｄｅｌ ｒｅｇｉｓｔｒａｔｉｏｎ ｖｉａ ｓｈａｐｅ ｄｅｓｃｒｉｐｔｏｒ （Ｓｃｈｏｏｌ ｏｆ Ａｕｔｏｍｏｔｉｖｅ Ｅｎｇｉｎｅｅｒｉｎｇ，Ｆａｃｕｌｔｙ ｏｆ Ｖｅｈｉｃｌｅ Ｅｎｇｉｎｅｅｒｉｎｇ＆Ｍｅｃｈａｎｉｃｓ，Ｓｔａｔｅ Ｋｅｙ Ｌａｂｏｒａｔｏｒｙ ｏｆ Ｓｔｒｕｃｔｕｒａｌ Ａｎａｌｙｓｉｓ ｆｏｒ Ｉｎｄｕｓｔｒｉａｌ Ｅｑｕｉｐｍｅｎｔ，Ｄａｌｉａｎ Ｕｎｉｖｅｒｓｉｔｙ ｏｆＴｅｃｈｎｏｌｏｇｙ，Ｄａｌｉａｎ Ｌｉａｏｎｉｎｇ １１６０２４，Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ：Ｆｏｒ ｍｏｄｅｌ ｒｅｇｉｓｔｒａｔｉｏｎ，ｔｈｉｓ ｐａｐｅｒ ｐｒｏｐｏｓｅｄ ａ ｎｅｗ ｍｅｔｈｏｄ ｂａｓｅｄ ｏｎ ｓｈａｐｅ ｄｅｓｃｒｉｐｔｏｒ．Ｆｉｒｓｔ，ｔｈｅ ｍｅｔｈｏｄ ｅｘｔｒａｃｔｅｄ ｆｅａｔｕｒｅ ｐｏｉｎｔｓ ｏｎ ｔｈｅ ｇｉｖｅｎ ｍｏｄｅｌｓ ｂｙ ｕｓｉｎｇ ａ ｄｉｓｔａｎｃｅ—ｂａｓｅｄ ｓｈａｐｅ ｄｅｓｃｒｉｐｔｏｒ．Ｎｅｘｔ．ｉｔ ｃａｌｃｕｌａｔｅｄ ｓｉｍｉｌａｒｉｔｉｅｓ ｏｆ ｔｈｅｓｅ ｆｅａｔｕｒｅ ｐｏｉｎｔｓ ｏｎ ｄｉｆｆｅｒｅｎｔ ｍｏｄｅｌｓ ａｎｄ ｕｓｅｄ ｆ０ｒ ｄｅｔｅｒｍｉｎａｔｉｏｎ ｏｆ ｆｅａｔｕｒｅ ｐｏｉｎｔ ｐａｉｒ．Ｆｉｎａｌｌｙ．ｉｔ ｃａｌｃｕｌａｔｅｄ ｔｈｅ ｔｒａｎｓｆｏｒｍａｔｉｏｎ ｍａｔｒｉｘ ｂａｓｅｄ ｏｎ ｆｅａｔｕｒｅ ｐｏｉｎｔ ｐａｉｒｓ．ａｎｄ ｕｓｅｄ ｔｈｅ ｍａｔｒｉｘ ｔｏ ｒｅｇｉｓｔｅｒ ｔｈｅ ｇｉｖｅｎ ｍｏｄｅｌｓ．Ｔｈｅ ｅｘｐｅｒｉｍｅｎｔａｌ ｒｅｓｕｌｔｓ ｓｈｏｗ ｔｈａｔ ｔｈｅ ｐｒｏｐｏｓｅｄ ｍｅｔｈ－ ｏｄ ｃａｎ ｍａｋｅ ａ ｈｉｇｈ ｑｕａｌｉｔｙ ｒｅｇｉｓｔｒａｔｉｏｎ ｗｉｔｈｏｕｔ ｎｅｅｄｉｎｇ ａｎｙ ｐｒｅ—ｐｒｏｃｅｓｓｉｎｇ． Ｋｅｙ ｗｏｒｄｓ：ｆｅａｔｕｒｅ ｐｏｉｎｔ；ｓｈａｐｅ ｄｅｓｃｒｉｐｔｏｒ；ｍｏｄｅｌ ｒｅｇｉｓｔｒａｔｉｏｎ 征面上三组对应点计算转换矩阵来实现模型的预配准。文献 ０引言 模型配准技术在几何造型、图形处理等方面有着广泛的应 用。模型配准技术是通过一定的算法或统计学规律，利用计算 ［８］提出利用图像中的边缘面和角点等特征实现模型的初始 配准，再结合角点特征点集和奇异值分解－ＩＣＰ算法进行精配 准。文献［９］提出利用分层的法向空间采样方法来获取模型 上的对应点以实现模型的预配准。此外，针对ＩＣＰ算法的计算 机计算两个模型之间的错位，从而达到两个模型自动配准的效 果。在模型配准技术中ＩＣＰ（ｉｔｅｒａｔｉｖｅ ｃｌｏｓｅｔ ｐｏｉｎｔ）算法是应用 效率不高，文献［１０］提出利用逆向定标法和随机搜寻法来提 高速度，但这会对配准精度产生一定的影响。文献［１１］提出 了ＩＣＬ（ｉｔｅｒａｔｉｖｅ ｃｌｏｓｅｔ ｌｉｎｅ）方法，该方法通过对两个点云中的 最广泛的 ｊ。但由于该算法存在收敛于局部最优和计算效率 不高等不足，国内外许多研究者都曾努力改进ＩＣＰ。例如，针 对ＩＣＰ收敛于局部最优的缺点，目前所采用的自动配准技术一 般通过初始配准和精确配准两步来完成。初始配准是为了缩 点连线并寻找对应线段进行配准，但存在着无法保证线段之间 对应关系的缺陷。文献［１２］提出通过寻找两片点云重叠区域 内的有效点与对应三角形对，并将有效点与对应三角形对所夹 的空间三棱锥体积作为误差测量度来指导配准操作，提高了 ＩＣＰ算法的效率。文献［１３］提出了一种距离约束改进的ＩＣＰ 算法，该方法针对ＩＣＰ算法中找到的配准点，采用最近原则排 小模型间的错位以保证精确配准的效率和精度，而精确配准则 是为了使两个模型之间的配准误差最小。针对初始配准方法， 文献［２］通过计算点云的包围盒后获得点云的中心，继而使两 个点云的中心重合以完成点云数据的初始配准操作，该方法的 不足在于其只能缩小平移错位而无法缩小旋转错位。文献 ［３，４］提出了利用标签实现初始配准的思想，在测量时人为贴 除含相同点的点对，在配准速度和精度方面都获得了较高的效 果。文献［１４］提出通过提取并利用局部特征来完成预配准， 上一些特征点，然后利用这些特征点进行配准操作。文献［５］ 提出的是基于轮廓曲线的初始配准方法，首先提取点云数据中 的曲率点，通过连接这些曲率点形成模型的轮廓曲线用于模型 的初始配准。文献［６］提出了利用对测量仪器和点云没有特 之后在结构约束下利用ＩＣＰ算法实现模型的精确配准，在配准 效率上获得了较大的提升。文献［１５］提出通过计算一个双向 的距离场来实现模型的预配准，继而利用成分分析（ｉｎｄｅ－ ｐｅｎｄｅｎｔ ｃｏｍｐｏｎｅｎｔ ａｎａｌｙｓｉｓ）来实现模型的精确配准。 殊要求的主方向贴合法来实现平移和旋转错位快速缩小的初 始配准方法。文献［７］提出了一种基于简化模型曲率计算的 配准方法，该方法通过计算简化的点云模型和ＣＡＤ模型各点 本文提出一种基于匹配模型特征点实现模型精确配准的 方法。首先利用本文提出的基于距离场的形状描述方法搜寻 模型上的特征点并建立不同模型上特征点间的对应关系，即构 的曲率，继而提取出两模型上的某一对应的特征面，利用该特 收稿日期：２０１３－０１・２Ｏ；修回日期：２０１３－０３・０８ 造特征点对；之后利用特征点对计算转换矩阵并实现模型的配 基金项目：辽宁省教育厅一般科学研究项目（Ｌ２０１２０１２） 作者简介：刘学术，男，天津人，讲师，博士，主要研究方向为逆向工程、快速设计（１ｉｕｘｓ＠ｄｌｕｔ．ｅｄｕ．ｃｎ）． 第１１期 刘学术：一种基于形状描述的模型配准方法 ・３４９３・ 准操作。实例表明本文方法对模型的初始位置无特殊要求，在 无须预配准操作的情况下，可实现模型的一步精确配准。 式（４）的Ｄ（ｐ：）内的极ｋ是与Ｄ（ｐ。）内的极１相对应，并以此 为依据按顺序比较Ｄ（ｐ ）和Ｄ（ｐ：）。 任意两个采样点的相似度由式（５）给出。 ｒ１—６ ｉｆ０≤６≤１ １ 基于形状描述的模型配准方法 １．１ 基于距离场的形状描述方法 ｛０ ０ｌｈｅ ｅ 式中：６：Ｉ监 ＾（‘，Ｊ） （ ） 一假设预配准模型 上存在一特征点ｐ∈Ｍ，Ｐ点的邻域由 Ｎ（ｐ）＝｛Ｐ ∈ＭＩｄ（ｐ，Ｐ ）≤ｒ｝给出。其中：ｄ（）表示欧式距离，ｒ 为一实常数。为了能够数字化描述特征点Ｐ，在Ｎ（Ｐ）内提取 ：（ ＋ ）ｍ。ｄ （ ：０， ， 一１）。 由公式可以看出，结果越趋近于１，说明两个采样点的相似度 越高。 ｍ×ｎ个采样点｛ｇ（ｆｌ『）｝ｃＮ（ｐ）。其中：ｍ和ｎ是整数；ｉ＝０， １，…，ｍ一１ ＝０，１，…，ｎ一１。假设ｍ＝３，ｎ＝８，Ｐ及Ｎ（ｐ）内ｍ 特征点Ｐ 和Ｐ：的相似度由式（６）给出。 ｍ—ｌ 一１ ×ｎ＝２４个采样点的位置关系如图１所示。图中特征点Ｐ以 深色圆点表示，其邻域内的采样点｛ｑ｝以浅色圆点表示。以特 征点为起点的射线称为极，本例中包含ｎ＝８个极，每极包含 ｍ＝３个采样点。以特征点为中心的圆称为环，本例中包含 ｍ＝３个环，每环包含ｎ＝８个采样点。采样点位于环和极的交 点处。 特征点Ｐ的基于距离场的形状描述Ｄ（ｐ）由式（１）给出。 Ｄ（ｐ）＝｛｛Ａ（００），…，Ａ（０）｝，…，Ａ（ 』），…，Ａ（ｍ—ｌ，， ，， 一１）｝ （１） 式中，Ａ ）由式（２）给出。 Ａ（ ）＝ｓｉｇｎ×ｄ（ｑ（ｉ一１， ｑ（ｉ， （２） 符号ｓｉｇｎ用来表示ｇ［ｆ．『】采样点的凸凹性，由式（３）给出。 ｓｉｓｎ＝｛： ㈩ 式（３）中字母的含义如图２所示。ｈ∈Ｎ（ｐ）表示ｇ（ ｌ『）和 ｇ（ｆ．，）之间的一点，ｎ（ｈ）表示曲面 在ｈ点处的法向量（黑色箭 头所示），ｍ表示线段ｇ（ ，，）ｇ（ ， ）的中心，ｈｍ表示由ｈ到ｍ的 向量（红色箭头所示）。如果采样点ｑ（ 和ｇ（１．『）之间存在曲 线如图中粉红色曲线所示，则采样点ｑ ｎ的凸凹性为凸，用 “＋”表示；如果采样点间存在曲线如图中蓝色曲线所示，则其 凸凹性为凹，用“一”表示。详见电子版。 图ｌ特征点Ｐ及其 邻域内的采样点 图２采样点凸凹性的确定 １．２特征点的相似度计算 特征点的相似度用于确定特征点间的对应关系。本文把 不同模型上具有较高相似度的两个特征点称为特征点对。 在获得模型 和Ⅳ上的两个点Ｐ ∈Ｍ和Ｐ：∈Ｎ的形状描 述Ｄ（ｐ ）和Ｄ（ｐ：）之后，需对Ｄ（ｐ。）和Ｄ（ｐ：）进行比较以判断 Ｐ 和Ｐ：是否构成特征点对。为避免Ｄ（ｐ）中数据排列顺序对 相似度计算的影响，同时考虑到采样点的分布情况，利用式 （４）来确定Ｄ（ｐ，）和Ｄ（ｐ：）的比对顺序。 ｍ ｍｉｎ ＩＡ １）一Ａ住 ）Ｉ （４） 式中：Ａ‰）中上标Ｐ 表示该值为特征点Ｐ。所有。 式（４）的基本含义是以Ｄ（Ｐ ）内第１极上的采样点为基 准，按照顺序与Ｄ（ｐ ）内所有极上的采样点相比较，认定满足 ∑∑ｓ Ｓ（ｐ－，Ｐ２）＝ （６） 对于任意一点Ｐ∈Ｍ，可根据相似度的高低在模型Ⅳ上找 到对应点Ｐ Ｎ满足ｍａｘ Ｓ（ｐ ，Ｐ ），继而形成特征点对。 １．３转换矩阵计算 通过特征点的相似度计算，找出三组特征点对｛Ｐ ，Ｐ：，Ｐ ｝ 和｛Ｐ 。，Ｐ ：，Ｐ ，｝。模型配准所需的旋转矩阵只和平移矩阵７－ 将依据这三组特征点对求取。计算步骤如下： ａ）计算特征点｛Ｐ。，Ｐ ，Ｐ，｝的中心Ｏ。和｛Ｐ ，Ｐ ：，Ｐ ，｝的中 心Ｏ：。此后用Ｐ 表示特征点Ｐ 的位置矢量，其他符号类似。 ｂ）分别以０ 和Ｏ：为原点，以单位矢量组ｅ。，ｅ：，ｅ，与ｅ ，， ｅ ：，ｅ 按照右手法则构建两个局部坐标系。假设存在旋转变 化矩阵Ｒ与平移变化矩阵７－使两个局部坐标系重合，于是有 ｅｌ：（Ｐｌ一０１）／ＩＰ１—０ｌＩ ｅ３＝ｅ１×（Ｐ２—０１）／ＩＰ２—０１ Ｉ ｅ２ ｅ３×ｅＩ ｅ １＝（Ｐ ｌ一０２）／ＩＰ １—０２ Ｉ （７） ｅ ３＝ｅ １×（Ｐ ２—０２）／ｌＰ ２一Ｏ２ ｅ ２＝ ×ｅ ｌ ［ｅ ｌ ｅ ２ ｅ ３］ 开＝［ｅ１ ｅ２ ｅ３ （８） 由式（８）可求得旋转矩阵只为 开＝（［ｅ １ ｅ ２ ｅ ３］Ｔ） ［ｅｌ ｅ２ ｅ３］ （９） 待配准模型中任意一点Ｐ 变换到另一模型上的对应点 Ｐ 的关系式为 Ｐ ＝Ｂ＇Ｐ ＋Ｔ （１０） 把Ｐ 和Ｐ 代人式（１Ｏ）可得到平移矩阵７－为 ７－＝Ｐ ｌ—Ｆ１Ｐｌ （１１） ｃ）把求得的旋转矩阵片和平移矩阵７．应用到模型Ⅳ后， 可完成模型的配准操作。 ２应用实例 ２．１采样点的提取 在本文给出的算例中，取ｍ＝３，ｎ：８，ｒ＝２．０，环间距为ｒ／ （ｍ一１）＝１。 对三维图形而言，每一个采样点是三个面的交点。一个是 所给模型曲面，如肘；一个是以特征点为中心，以ｉ ｒ（ｉ＝０， ｍ １，…，ｍ一１）为半径的球面 ；一个是通过特征点Ｐ并以 ｎ（ｐ） ’７，（ ＝１，２，…，ｎ）为法向量的平面卢，。ｎ（ｐ）表示曲面 在Ｐ点所在处的法向量，叼 表示极 的方向矢量。因此每一个 采样点可由式（１２）给出。
