基于标志点匹配算法的研究

刘星明，王辉静，蔡铁，桂荣枝，唐琪

（深圳信息职业技术学院 计算机学院，广东 深圳 518172）

引言

复杂曲面的三维建模与检测技术目前已广泛应用于工业制造、目标测量、文物保护、虚拟现实以及工业过程控制等领域[1-4]。该测量技术不需要接触物体即可以实现对物体的三维形貌进行检测和测量，不会对目标物体造成任何破坏性损坏和伤害，具有成像速度快、精度高、易操作等优点[5,6]，具有传统技术（如指针式三维测量仪，通过指针接触探测物体，可能对被测物体造成损坏）无法比拟的优点，是一项无损检测。由于受采集设备测量范围和采集视场的限制，通常在一个视场下采集设备不能实现目标物体全部数据的采集，只能获取部分三维点云数据，这就需要在不同视场下对目标物体数据进行采集，然后把各个局部坐标采集的数据统一到同一世界坐标系下，实现目标物体深度像的匹配[7,8]。常用的方法是把采集装置固定在机械设备上（如机械臂）或把物体放在旋转体上[9,10]，在不同视场对目标物体进行深度数据的采集，然后通过坐标变换统一到全局坐标系下，建立目标物体的完整数据模型。通过控制机械设备能实现物体的精确数据匹配，通常其成本高，导致其应用范围受到限制。此外，如果把目标物体放在旋转体上进行目标数据采集，该方法对球形或对称的目标物体建模通常无法完成精确的匹配。此外，通过人工标志点进行深度数据的匹配也是一种常见的匹配算法，算法需要在目标物体表面或周围粘贴人工标志点[11-13]，该方法简便且有效，在工业测量和检测中经常用到，适合任何曲率和形状的目标物体，是应用最为广泛的一种三维建模方法。

基于标志点的深度像匹配通常有两种：编码标志点和非编码标志点匹配[14,15]。本文提出一种基于非编码标志点的深度像自动匹配算法，该算法利用非编码标志点实现了复杂曲面的自动深度数据匹配，在标志点匹配算法中构建了多视角网络匹配算法，利用光速平差算法进行全局优化，减少三维数据全局匹配的累积误差，实现深度数据的高精度匹配。本文的主要贡献是提出一种实现目标物体全自动三维建模方法，减少了过程中的人工干预，提高了数据的采集效率。与文献[15]相比，本文不仅实现了几何形状的建模，而且对物体表面的纹理色彩属性进行了恢复，且对人工标志点遮挡区域的纹理进行复原，实现了目标物体的真实感三维重建，在虚拟现实、人机交互等方面具有重要的应用。此外，本文利用优化算法对过程中产生的累积误差进行全局优化，对过程中由于噪声、相机畸变、数据匹配、融合等建模过程中产生的误差进行优化，提高了目标物体的重建精度。最后，用实际采集的实验数据结果验证了该算法的鲁棒性和有效性。

1 标志点的定位

实验把人工标志点粘贴在目标物体表面进行数据采集，利用标志点建立目标物体的空间数据模型。在数据采集过程中，对人工标志点的提取精度直接影响到数据采集和最终目标模型的精度。本文采用带有黑色外圆的圆形作为标志点（见图1a），并设有带反光和不带反光的两类模式，带反光的标志点应用在采集视场环境较暗的情况下，标志点容易识别，如果采集环境比较充足，则用普通标志点就可以满足。采用圆形标志点有以下几方面的优点：（1）圆形标志点制作比较方便，且圆形标志点的识别方法成熟，可以通过算法实现亚像素级别的精确定位；（2）黑白标志点对比度高，易利用算法进行自动图像分割处理；（3）圆形标志点的中心定位算法较为普遍，算法定位精度高。

2.1 标志点的自动识别

标志点通常粘贴在被测目标物体的表面上，标志点匹配就是通过识别物体上的标志点进行深度像匹配，调整局部坐标数据到全局坐标系下，建立目标物体的数据模型。在实际应用中，工作场景复杂以及光照环境难以预测，采集的原始图像存在噪声和其他干扰，导致对标志点的识别复杂化。因此，通常先对采集的图像进行预处理，然后再对标志点进行拟合和检测，提取标志点圆心坐标。

对标志点的拟合用椭圆曲线进行表示，椭圆的一般表现形式为：

利用上述方程对边界离散点进行最小二乘法求取圆心，取其平方得：

对上式分别对参数B,C,D,E,F求偏导，并令偏导方程为零，求解标志点的圆心坐标为：

求解标志点圆心定位的主要步骤概括为：

(1)对采集的原始标志点图像进行自适应高斯滤波处理，抑制图像的噪声干扰。

(2)采用Canny算法对标志点进行边缘提取，根据目标点的尺寸、特征、以及灰度等特征变化提取目标点的轮廓。

(3)利用最小二乘法对轮廓特征进行椭圆拟合，进而通过椭圆的拟合获得标志点中心的精确定位。

本文采用Canny对标志点进行边缘检测，该算法对边缘检测识别率高，尤其对弱边缘具有较高的识别度，检测的结果也具有较好的连通性和密闭性，检测的计算复杂度较高，算法耗费时间较长。图1b为采用Canny边缘检测的结果。

图1 标志点的检测与识别。(a)粘贴在被测目标物体的标志点；(b)利用Canny算法对标志点进行检测。Fig.1 Marker points detection and identification. (a): the marker points are pasted on the target object; (b): used the cannyalgorithm to detect the marker points.

2.2 标志点的自动匹配

实验用结构光扫描设备对标志点的边缘进行提取，进而求解标志点的圆心坐标。实验采用的是非编码标志点，非编码标志点制作简单，但非编码标志点的形状是一样的，从外观上不能对标志点进行编号或区分。因此，通过检测目标物体表面标志点与相邻标志点的距离，对每个标志点进行标识。然后再通过局部采集标系下标志点坐标与全局标志点坐标系之间的对应关系，解得局部扫描视场坐标系和全局坐标系之间的变换关系。坐标系之间的变换为刚体变换，可用3x3的旋转矩阵R和3x1的平移矩阵t来描述。

假设S1和S2为对应的标志点集合，如何寻找坐标系之间的最佳变换h(R,t)，统一局部采集的坐标系到全局坐标系下，构建目标物体的完整数据模型。假设给定标志点坐标点集分别为，pi，pi′为3x1的列向量，i=1,2,3…,N，这里N≥3（点云之间的变换至少需要3个点对），则局部坐标系之间的变换关系可以表示为：

这里，R,T分别为3x3的旋转矩阵和3x1的平移向量，Ni为受噪声等因素影响的误差。根据给定的N个点对，求解R、T以下目标函数：

因此，式（5）的最小二乘法化简为对式（9）的求解，通过SVD分解，得到旋转矩阵R。

坐标变换的平移矩阵T则通过以下计算得到

3 光束平差优化

采集的深度像匹配到全局坐标系的过程中由于噪声、相机畸变等原因，会有误差产生，而数据匹配、融合等建模过程中也会有误差产生，且过程的误差会有累积误差的影响，使误差的不确定性加大。为此，本文利用光束平差算法对全局误差进行优化，减少系统全局匹配误差。

4 实验及结果分析

本文的实验扫描系统为实验室研制的扫描系统，系统由2个CCD相机（DH-HV1303UM, DHHV3103UC，分辨率为1280x1024）和1个投影仪（OPTOMA，分辨率为1280x800），以及研发的扫描软件系统组成，见图2，系统采用Zhang[16]的标定方法进行标定，确定扫描系统相机的参数（即主点、焦距、畸变系数等参数），系统的扫描视场为300x300x150mm，系统配套的计算机设备为Intel® Core(TM) i7-4500u CPU @1.8GHz, 2.4GHz 32位Windows操作系统，系统是基于结构光的扫描系统，系统工作时，投影条纹光到被测量物体进行数据采集，并利用粘贴在物体表面的标志点进行深度像匹配。

图2 实验采集装置图Fig.2 The layout of the acquiring equipment

实验对汽车配件进行三维几何重建，配件表面具有不规则的几何形状，传统的工具（如游标卡尺）不方便或者不能够实现其精度的测量，而采用标志点进行三维建模，可以轻松地实现曲面的检测和建模。实验首先在目标物体上粘贴标志点，然后利用实验室研制的采集设备进行标志点的检测和数据采集（单视角采集的数据见图3a,b，红色圈注的为粘贴的标志点），然后根据重叠区域的标志点进行匹配，统一局部采集的数据到同一坐标系下，实现目标物体的数据建模（实验采集的结果如图3c）。实验过程中系统自动对标志点进行识别、定位和匹配，不需要进行任何的人工操作，操作简单、便捷，在工业测量和检测中具有很大的应用价值和前景。

图3 实验结果。(a-b)局部坐标系下采集的深度像数据；（c）标志点配置的结果。Fig.3 The experimental results. (a-b) the acquired range image in local coordination system. (c) The results of the registration based on the marker points.

实验还对花瓶进行曲面重建，目标物体高约为35cm，直径约为20cm，且结构为相对对称。传统的匹配算法对拓扑结构为对称的物体，由于其特征点不明显很容易导致匹配错误（深度像错配）。标志点匹配算法则避免了该类问题的产生，算法通过粘贴在目标物体的标志点进行坐标定位并实现深度像匹配，建立物体的完整数据。在实际采集过程中，围绕物体在8个不同的视角进行数据采集（单视角采集的数据见图4a），每个视角采集的数据坐标都是建立在局部坐标系下，不同视角采集的数据有重叠区域，实验通过重叠区域的标志点进行匹配（图4b,c为两视角采集数据匹配的结果），统一局部采集的数据到全局坐标系下，并通过融合祛除重叠区域的冗余数据，得到物体的完整数据和拓扑连接关系，实验结果见图4。从实验结果可以看出，利用标志点进行匹配，可以很方便地实现曲面的三维重建，且该算法不受曲面结构或形状的限制。

图4 实验结果。 (a)在局部坐标系下采集的单视角深度数据； （b）通过重叠区域的标志点进行两两匹配，得到的局部匹配结果图。（c-d）匹配结果的不同视角截图，在结果表面存有标志点遮挡了物体部分表面纹理。Fig.4 The experimental results. (a) The acquired range images in the local coordination system; (b) The registration results based on the marker points of the overlapping regions. (c-d) the views of the registration results, and parts of texture are blocked by the marker points.

利用标志点进行匹配，由于标准点粘贴在目标物体的表面，进而导致模型表面部分纹理的损失（图5a），实验通过标志点周围的颜色对覆盖的颜色进行泊松融合，对遮挡的纹理进行了表面恢复。相比传统的线性插值纹理恢复方法[4]，该方法更有效地保证了遮挡区域的纹理与周围纹理的一致性。实验通过对遮挡区域纹理的梯度纹理进行了分析，也验证了泊松纹理恢复比线性插值效果更好。遮挡区域纹理恢复实验结果见图5，该方法保证了被遮挡区域纹理的连续性，从而拓展了在虚拟现实、影视艺术以及虚拟博物馆等领域的应用。

图5 纹理修复，纹理修复前(a)和修复后(b)的效果对比。Fig.5 The texture restoration, comparison of results before (a) and after (b) texture restoration.

为了对标志点匹配的精度进行评估，实验对局部坐标系下采集的两视角深度数据进行匹配，并用匹配之后标志点对的距离来衡量匹配误差。因为标志点在目标物体重叠区域的分布基本上呈区域分布（如图6，标志点分布并不是集中在某一小块区域），故标志点的距离在一定程度上反映了标志点匹配的精度。表1为标准点对的匹配误差距离，从表中可以看出，利用光束平差优化算法可以使累积的误差进行误差优化，提高了算法的匹配精度，优化后标志点匹配误差约为0.04mm。实验结果表明，标志点匹配能实现高精度深度像匹配，且该方法操作简单，过程中不需要人工进行干预，适合实际工程的应用。

表1 标志点对的匹配误差Tab.1 The matching error of marker points pairs.

为了验证算法的稳定性和可靠性，实验对具有复杂结果的人物结构物体进行几何结构和表面纹理属性的恢复，人物结构的高和宽分别约为15cm和7cm，人物的头部具有头发和饰品等复杂形结构，增加了三维重构物体的难度。复杂形状结构的物体表面的数据融合也是一个比较难解决的问题，利用传统的权重融合，往往在三维物体表面会有空洞现象发生，因此，实验采用梯度融合算法，对三维模型表面的重叠数据进行数据融合处理，构造完整的三维模型。

实验利用实验自制的扫描仪（见图2），并采用投影标准点到目标物体，物体放在转台上从8个不同的方向进行数据的采集(CCD相机DH-HV1303UM, DH-HV3103UC，分辨率为1280x1024）,单视角采集的三维数据约为3.5M，含约40,000～60,000的点坐标和80,000～100,000的三角面片。为了得到完整的目标物体，局部坐标下采集的数据需要配准到同一世界坐标系下，建立物体的完整几何数据，即进行深度像配准操作，实验结果见图7。

图7 实验结果。(a,b)采集的局部深度数据；（c,d）配准局部数据到全局坐标系，建立物体的完整数据。Fig.7 The experimental results. (a,b) the acquired range images in the local coordination system; (c,d)register local data to a common coordinate system to establish the complete data of the object.

重叠区域的冗余数据需要进行合并和优化处理，即数据的融合处理，本文利用如文献[5]的方法进行数据融合处理，实验结果见图8。实验还对数据融合效果进行了分析，实验结果见图9。从实验结果可以看出，数据融合消除了冗余数据，同时减少了误差，提高了系统精度。

图8 数据融合处理，消除重叠区域的冗余数据。Fig.8 The data fusion processing to eliminate the redundant data in the overlapping regions.

图9 数据的处理，融合处理前重叠区域有多层冗余的数据（a），和对重叠区域的数据进行融合处理后(b）,细节对比见红色标注部分。Fig.9 The data processing. (a) there has redundant data exists, (b)the redundant data is eliminated, and the detials are compared(in red mark).

5 结语

本文基于结构光对目标物体进行扫描，利用在被测物体表面粘贴标志点进行标志点识别、提取和坐标定位，实现局部坐标系到全局坐标系的深度像匹配，重建目标物体的三维几何模型，该扫描全过程不需要进行人工操作，算法操作简单且有效。但对于精密的设备或文物来说，由于不允许在目标物体上粘贴标志点，该算法具有局限性，对于该类物体的三维几何重建，以及表面特殊属性（如反光材质）物体的重建，将是下一步研究的内容。