一种基于轮廓随机采样的局部形状匹配方法

摘要

本发明公开一种基于轮廓随机采样的局部形状匹配方法，包括：采用几何圆半径方法提取待匹配目标轮廓上的所有子轮廓序列和模板轮廓上随机子轮廓；提取目标子轮廓和模板随机子轮廓的最小旋转外接矩形长宽比及轮廓面积特征，进行第一次匹配；对第一次匹配得到的轮廓点，提取其子轮廓基于角度分类的均值距离链码和均值角度链码特征；利用模板随机子轮廓得到的链码特征与第一次匹配后的子轮廓进行二次匹配，以得到少量最优匹配轮廓；计算模板随机子轮廓与匹配子轮廓的坐标变换矩阵，通过该变换矩阵将整个模板轮廓投影到目标轮廓上；更新子轮廓的坐标变换矩阵；识别最优匹配轮廓。本发明能够快速可靠地给出匹配结果，图像配准计算效率高，适应性强。

说明书

技术领域

本发明涉及一种形状匹配方法，尤其涉及一种基于轮廓随机采样的局部形状匹配方法。

背景技术

视觉是人类观察、认知世界的主要手段，人类从外界获取的信息大部分来自视觉系统。在观察周围环境时，人们首先注意到的是物体及周围环境的颜色、纹理、形状和空间关系等，其中形状是物体在实际感知意义下具有的最基本特征之一。形状匹配是指根据一定的度量准则来衡量形状间的相似性，它是图像自动识别和理解的基本问题之一，在计算机视觉、模式识别、遥感图像分析、文字识别等领域有着广泛的应用。然而，传统的形状匹配方法配准率低，配准速度慢，适应性差。

发明内容

本发明的目的在于通过一种基于轮廓随机采样的局部形状匹配方法，来解决以上背景技术部分提到的问题。

为达此目的，本发明采用以下技术方案：

一种基于轮廓随机采样的局部形状匹配方法，包括如下步骤：

A、提取待匹配目标轮廓上的所有子轮廓序列和模板轮廓上随机子轮廓；

B、提取待匹配目标子轮廓和模板随机子轮廓的特征，其中，该特征包括但不限于待匹配目标子轮廓和模板随机子轮廓的最小旋转外接矩形的长宽比和轮廓面积两个特征；

C、进行第一次匹配：设定匹配幅度阈值T_magnitude，当待匹配目标图像中子轮廓的所述两个特征同时满足在模板中随机子轮廓特征的±T_magnitude幅度内，则认为该轮廓点为匹配点，从而剔除非匹配轮廓点；

D、对第一次匹配得到的轮廓点，提取其子轮廓基于角度分类的均值距离链码和均值角度链码特征；

E、利用模板随机子轮廓得到的链码特征与第一次匹配后的子轮廓进行第二次匹配，对第一次匹配获得的轮廓点进行再次剔除；

F、计算模板随机子轮廓与匹配子轮廓的坐标变换矩阵，通过子轮廓坐标变换矩阵将整个模板轮廓投影到目标轮廓上；

G、更新子轮廓的坐标变换矩阵：采用均匀采样的方法得到投影模板轮廓上的轮廓采样点，并遍历目标轮廓上的坐标点，求得投影模板轮廓采样点在目标轮廓上的最近邻坐标点，然后再次利用奇异值分解求得整个模板轮廓的坐标变换矩阵；

H、识别最优匹配轮廓：采用均匀采样的方法将模板轮廓点投影到目标轮廓上，并计算这些采样点到目标轮廓与之相对应的最近邻点的欧式距离之和，以其为评判匹配误差的标准，对二次候选匹配轮廓进行匹配度评价，选取距离和最小的轮廓即为最优匹配轮廓。

特别地，所述步骤A之前还包括：

一、对相机采集得到的灰度图像进行预处理：(1)对灰度图像进行3×3模板的均值滤波，并采用最大类间方差法计算待匹配目标图像f(x,y)的全局最优阈值T，得到二值图像g(x,y)；(2)从待匹配目标图像序列中截取需匹配的目标区域作为模板图像，对该目标区域进行包括滤波、阈值分割在内的预处理，取得该模板图像的二值图像；

二、提取二值图像连通区域的轮廓：(1)通过采用链码方法搜索二值图像的轮廓，并将链码编码中的所有点转换为坐标点，即得到一系列逆时针排序的坐标点对；使用极大极小值来限定区域的周长，遍历所有轮廓移除过长或过短的轮廓，保留待匹配的轮廓；(2)采用链码提取模板图像的轮廓，即得到模板图像轮廓上的一系列坐标点；对位于模板图像四周边界的轮廓进行剔除，保留模板图像中的目标轮廓。

特别地，所述步骤A具体包括：

A1、采用几何圆半径范围的抽取方法提取待匹配目标轮廓每个坐标点上的子轮廓：首先计算所有轮廓点之间的欧式距离，并保存在相应的vector数组中，然后统计每个轮廓点处的前后小于圆半径长度radius的轮廓点个数，最后遍历轮廓上所有坐标点得到所有的子轮廓，并保存于vector数组；

A2、采用随机采样的方法提取模板轮廓上的随机轮廓点几何圆半径构成的子轮廓：通过计算随机轮廓点与前后轮廓点之间的欧式距离，并统计前后小于圆半径长度radius的轮廓坐标点的个数，最终提取出该点上的圆半径子轮廓。

特别地，所述步骤A2还包括：将模板轮廓的开始和末尾的在圆半径范围的点剔除。

特别地，所述步骤B中待匹配目标子轮廓和模板随机子轮廓的最小旋转外接矩形的长宽比和轮廓面积两个特征的提取过程如下：

一、计算最小旋转外接矩形的长宽比特征F_ratio：对给定的子轮廓坐标点集，按照水平轴逆时针旋转，每次旋转一次，查找包围轮廓点集最小面积的矩形minAreaRect，即得到该矩形的长和宽，从而得到长宽比特征：

$>F_{\mathrm{raito}}=\left(\begin{array}{c}\frac{\mathrm{width}}{\mathrm{height}},\mathrm{height}>\mathrm{width}\\ \frac{\mathrm{height}}{\mathrm{width}},\mathrm{height}\le \mathrm{width}\end{array}\right)$>

二、计算轮廓面积特征F_area：将子轮廓的两端连接，并与轮廓部分构成封闭区域，计算该区域的面积。

特别地，所述步骤D具体包括：

D1、计算最小旋转外接矩形的中心rect_center和轮廓的重心mass_center；通过计算最小旋转外接矩形得到该矩形的中心rect_center和四个角点的坐标rect_points[4]，通过零阶矩和一阶矩得到轮廓的重心，计算公式如下：

$>\mathrm{mass}\_\mathrm{center}=[\bar{x},\bar{y}]=[\frac{m_{10}}{m_{00}},\frac{m_{01}}{m_{00}}]$>

D2、依据轮廓的重心将矩形中心偏移到矩形外侧，并将该偏移中心位于矩形长边一侧：首先通过计算矩形四个角坐标点之间的欧式距离，锁定长边；然后计算矩形的两条长边和过中心点的平行线共三条直线的方程式a_ix+b_iy+c＝0其中，i＝1,2,3；最后，锁定重心位于过中心点平行线的一侧方向，作该中心点的对称点offset，即完成对中心点的偏移；

D3、以偏移点为中心，偏移点与轮廓起始点为边，计算轮廓上所有点角度，并搜索从轮廓起始点顺时针或逆时针出发的最大角度为参考角度angle，然后搜索在参考角度范围内的所有点角度和轮廓坐标点；

D4、将参考角度划分为n份，以偏移点为中心，偏移点与轮廓起始点为边，按照该平均角度步长进行顺时针或逆时针旋转将各个点角度和轮廓坐标点分别进行分类；

D5、计算各个角度内的轮廓坐标点的欧式距离，并对各个角度内的距离求平均值以构成距离链码，即为D_avg＝{d₀,d₁,…,d_n-1}，n为分类数；同理，对各个角度内的点角度求平均值以构成角度链码，即为A_avg＝{a₀,a₁,…,a_n-1}。

D6、利用如下公式，对均值距离链码和均值角度链码特征进行归一化处理：

$>\left(\begin{array}{c}{\bar{D}}_{\mathrm{avg}}=\{{\bar{d}}_0,{\bar{d}}_1,...,{\bar{d}}_{n-1}\}\\ {\bar{A}}_{\mathrm{avg}}=\{{\bar{a}}_0,{\bar{a}}_1,...,{\bar{a}}_{n-1}\}\end{array}\right).$>

特别地，所述步骤E具体包括：利用模板随机子轮廓得到的链码特征与一次匹配后的子轮廓进行二次匹配，采用欧式距离相似性度量公式：

$>\mathrm{SIM}=\underset{i=0}{\overset{n-1}{\Sigma }}\sqrt{{(\overline{d_i}-\overline{d_i^{\prime }})}^2+{(\overline{a_i}-\overline{a_i^{\prime }})}^2}$>

相似性度量值越小，认为与模板子轮廓越相似，因此设定相似性度量参数S，选取小于度量参数S的匹配点，对第一次匹配获得的轮廓点进行再次剔除。

特别地，所述步骤F具体包括：对模板随机子轮廓坐标点和目标子轮廓坐标点进行奇异值分解，获得满足旋转和平移特性的坐标变换矩阵，再通过子轮廓坐标变换矩阵将整个模板轮廓投影到目标轮廓上。

本发明提出的基于轮廓随机采样的局部形状匹配方法能够快速可靠地给出匹配结果，提高了图像配准的计算效率，而且具有很强的适应性。

附图说明

图1为本发明实施例提供的基于轮廓随机采样的局部形状匹配方法流程图。

具体实施方式

下面结合附图和实施例对本发明作进一步说明。可以理解的是，此处所描述的具体实施例仅仅用于解释本发明，而非对本发明的限定。另外还需要说明的是，为了便于描述，附图中仅示出了与本发明相关的部分而非全部内容，除非另有定义，本文所使用的所有的技术和科学术语与属于本发明的技术领域的技术人员通常理解的含义相同。本文中所使用的术语只是为了描述具体的实施例的，不是旨在于限制本发明。

请参照图1所示，图1为本发明实施例提供的基于轮廓随机采样的局部形状匹配方法流程图。

本实施例中基于轮廓随机采样的局部形状匹配方法具体如下步骤：

S101、对相机采集得到的灰度图像进行预处理：(1)对灰度图像进行3×3模板的均值滤波，并采用最大类间方差法(Otsu法)计算待匹配目标图像f(x,y)的全局最优阈值T，得到二值图像g(x,y)；(2)从待匹配目标图像序列中截取需匹配的目标区域作为模板图像，对该目标区域进行包括滤波、阈值分割在内的预处理，取得该模板图像的二值图像。

S102、提取二值图像连通区域的轮廓：(1)通过采用链码(freeman)方法搜索二值图像的轮廓，并将链码编码中的所有点转换为坐标点，即得到一系列逆时针排序的坐标点对；使用极大极小值来限定区域的周长，遍历所有轮廓移除过长或过短的轮廓，保留待匹配的轮廓；(2)采用链码提取模板图像的轮廓，即得到模板图像轮廓上的一系列坐标点；对位于模板图像四周边界的轮廓进行剔除，保留模板图像中的目标轮廓。

S103、提取待匹配目标轮廓上的所有子轮廓序列和模板轮廓上随机子轮廓。

采用几何圆半径范围的抽取方法提取待匹配目标轮廓每个坐标点上的子轮廓：首先计算所有轮廓点之间的欧式距离，并保存在相应的vector数组中，然后统计每个轮廓点处的前后小于圆半径长度radius的轮廓点个数，最后遍历轮廓上所有坐标点得到所有的子轮廓，并保存于vector数组。

采用随机采样的方法提取模板轮廓上的随机轮廓点几何圆半径构成的子轮廓：通过计算随机轮廓点与前后轮廓点之间的欧式距离，并统计前后小于圆半径长度radius的轮廓坐标点的个数，最终提取出该点上的圆半径子轮廓。考虑到匹配的准确性，需将模板轮廓的开始和末尾的在圆半径范围的点剔除，以保证得到的随机点能够获得匹配。

S104、提取待匹配目标子轮廓和模板随机子轮廓的特征，其中，该特征包括但不限于待匹配目标子轮廓和模板随机子轮廓的最小旋转外接矩形的长宽比和轮廓面积两个特征。

待匹配目标子轮廓和模板随机子轮廓的最小旋转外接矩形的长宽比和轮廓面积两个特征的提取过程如下：

一、计算最小旋转外接矩形的长宽比特征F_ratio：对给定的子轮廓坐标点集，按照水平轴逆时针旋转，每次旋转一次，查找包围轮廓点集最小面积的矩形minAreaRect，即得到该矩形的长和宽，从而得到长宽比特征：

$>F_{\mathrm{raito}}=\left(\begin{array}{c}\frac{\mathrm{width}}{\mathrm{height}},\mathrm{height}>\mathrm{width}\\ \frac{\mathrm{height}}{\mathrm{width}},\mathrm{height}\le \mathrm{width}\end{array}\right)$>

二、计算轮廓面积特征F_area：将子轮廓的两端连接，并与轮廓部分构成封闭区域，计算该区域的面积。

S105、进行第一次匹配：设定匹配幅度阈值T_magnitude，当待匹配目标图像中子轮廓的所述两个特征同时满足在模板中随机子轮廓特征的±T_magnitude幅度内，则认为该轮廓点为匹配点，从而剔除非匹配轮廓点。

S106、对第一次匹配得到的轮廓点，提取其子轮廓基于角度分类的均值距离链码和均值角度链码特征。

计算最小旋转外接矩形的中心rect_center和轮廓的重心mass_center；通过计算最小旋转外接矩形得到该矩形的中心rect_center和四个角点的坐标rect_points[4]，通过零阶矩和一阶矩得到轮廓的重心，计算公式如下：

$>\mathrm{mass}\_\mathrm{center}=[\bar{x},\bar{y}]=[\frac{m_{10}}{m_{00}},\frac{m_{01}}{m_{00}}]$>

依据轮廓的重心将矩形中心偏移到矩形外侧，并将该偏移中心位于矩形长边一侧：首先通过计算矩形四个角坐标点之间的欧式距离，锁定长边；然后计算矩形的两条长边和过中心点的平行线共三条直线的方程式a_ix+b_iy+c＝0其中，i＝1,2,3；最后，锁定重心位于过中心点平行线的一侧方向，作该中心点的对称点offset，即完成对中心点的偏移。

以偏移点为中心，偏移点与轮廓起始点为边，计算轮廓上所有点角度，并搜索从轮廓起始点顺时针或逆时针出发的最大角度为参考角度angle，然后搜索在参考角度范围内的所有点角度和轮廓坐标点。

将参考角度划分为n份，以偏移点为中心，偏移点与轮廓起始点为边，按照该平均角度步长进行顺时针或逆时针旋转将各个点角度和轮廓坐标点分别进行分类。

计算各个角度内的轮廓坐标点的欧式距离，并对各个角度内的距离求平均值以构成距离链码，即为D_avg＝{d₀,d₁,…,d_n-1}，n为分类数；同理，对各个角度内的点角度求平均值以构成角度链码，即为A_avg＝{a₀,a₁,…,a_n-1}。

利用如下公式，对均值距离链码和均值角度链码特征进行归一化处理：

$>\left(\begin{array}{c}{\bar{D}}_{\mathrm{avg}}=\{{\bar{d}}_0,{\bar{d}}_1,...,{\bar{d}}_{n-1}\}\\ {\bar{A}}_{\mathrm{avg}}=\{{\bar{a}}_0,{\bar{a}}_1,...,{\bar{a}}_{n-1}\}\end{array}\right).$>

S107、利用模板随机子轮廓得到的链码特征与第一次匹配后的子轮廓进行第二次匹配，对第一次匹配获得的轮廓点进行再次剔除。

利用模板随机子轮廓得到的链码特征与一次匹配后的子轮廓进行二次匹配，采用欧式距离相似性度量公式：

$>\mathrm{SIM}=\underset{i=0}{\overset{n-1}{\Sigma }}\sqrt{{(\overline{d_i}-\overline{d_i^{\prime }})}^2+{(\overline{a_i}-\overline{a_i^{\prime }})}^2}$>

相似性度量值越小，认为与模板子轮廓越相似，因此设定相似性度量参数S，选取小于度量参数S的匹配点，对第一次匹配获得的轮廓点进行再次剔除。从而通过链码这唯一性特征，进一步剔除第一次匹配得到的轮廓点，保留极少量匹配点,得到少量最优匹配轮廓。

S108、计算模板随机子轮廓与匹配子轮廓的坐标变换矩阵，通过子轮廓坐标变换矩阵将整个模板轮廓投影到目标轮廓上。

对模板随机子轮廓坐标点和目标子轮廓坐标点进行奇异值分解(SingularValue Decomposition，SVD)，获得满足旋转和平移特性的坐标变换矩阵，再通过子轮廓坐标变换矩阵将整个模板轮廓投影到目标轮廓上。

S109、更新子轮廓的坐标变换矩阵：采用均匀采样的方法得到投影模板轮廓上的轮廓采样点，并遍历目标轮廓上的坐标点，求得投影模板轮廓采样点在目标轮廓上的最近邻坐标点，然后再次利用奇异值分解求得整个模板轮廓的坐标变换矩阵。

S1010、识别最优匹配轮廓：采用均匀采样的方法将模板轮廓点投影到目标轮廓上，并计算这些采样点到目标轮廓与之相对应的最近邻点的欧式距离之和，以其为评判匹配误差的标准，对二次候选匹配轮廓进行匹配度评价，选取距离和最小的轮廓(误差最小)即为最优匹配轮廓。

本发明的技术方案能够快速可靠地给出匹配结果，提高了图像配准的计算效率，而且具有很强的适应性。

注意，上述仅为本发明的较佳实施例及所运用技术原理。本领域技术人员会理解，本发明不限于这里所述的特定实施例，对本领域技术人员来说能够进行各种明显的变化、重新调整和替代而不会脱离本发明的保护范围。因此，虽然通过以上实施例对本发明进行了较为详细的说明，但是本发明不仅仅限于以上实施例，在不脱离本发明构思的情况下，还可以包括更多其他等效实施例，而本发明的范围由所附的权利要求范围决定。