一种二维单射曲面数据的特征提取与匹配方法

摘要

一种二维单射曲面数据的特征提取和匹配方法，该方法首先将二维单射曲面数据投影到灰度值与数据值成正比的灰度图像，并将图像中的灰度值归一化到区间[0，255]中，然后从图像中提取特征点集；以特征点集中的每一个特征点作为参考点，在图像中绘制通过该特征点的等灰度线，且在图像中连接同一等灰度线上的特征点，这些等灰度线以及特征点之间的连线将图像划分成连续的区域块，根据区域块之间的包围和相邻关系构造一个Reeb图。对于需要匹配的两个二维单射曲面数据，通过匹配两个Reeb图中的结点，计算结点之间的相似度，所有匹配结点的相似度之和为两个二维单射曲面数据之间的相似度。本发明所提供的方法使得提取的特征容易计算，并且稳定性强。

权利要求

1.一种二维单射曲面数据的特征提取和匹配方法，其特征在于该方法包含如下步骤：

1)将二维单射曲面数据投影到xy平面，获取一幅灰度与g值成正比的灰度图像，将图像的灰度值归一化到区间[0，255]，并利用高斯窗口对图像进行平滑操作，以减弱图像中的噪音；

2)从图像中提取特征点集，以特征点集中的每一个特征点作为参考点，按照灰度值是否与该特征点相等，在图像中绘制通过该特征点的等灰度线，以及绘制同一等灰度线上特征点之间的连线，等灰度线以及特征点之间的连线将图像划分成一系列的区域块，根据区域块之间的包围和相邻关系构造一个Reeb图；

3)选取高度和位置作为典型的细节特征，将这两个细节特征作为Reeb图中的每个结点的属性，所述高度是指该结点所代表的图像区域块内灰度最高值与灰度最低值之差，所述位置是指该结点所代表的图像区域块的中心位置，所述中心位置的具体计算公式如下：其中：N指的是所述图像区域中像素点的个数，(x，y)i指的是像素点i的坐标，(x，y)center指的是所述图像区域中心像素点的坐标；

4)对于需要匹配的两个数据，通过计算两个对应的A Reeb图和B Reeb图之间的相似度来求得这两个数据之间的相似度：

4.1)将A Reeb图中的根结点a与B Reeb图中的根结点b相匹配，根结点指的是Reeb图中没有父结点的结点，得到一个匹配对，并计算所述匹配对的相似度，具体公式如下：其中：dis(a位置，b位置)表示的是根结点a与根结点b的位置属性的欧式距离；

4.2)如果两个结点相匹配，则继续对它们的子结点之间进行两两匹配，构成一个完全二分图，从所述二分图中提取一个结点距离之和最小的子图，从而构成两个结点的子结点之间的匹配对，每个结点至多在一个匹配对中出现，且匹配对中的两个结点来自两个不同的Reeb图；

4.3)计算步骤4.1)和步骤4.2)中得到的所有的匹配对的相似度之和，所述相似度之和就是所述A Reeb图与所述B Reeb图之间的相似度，即两个数据之间的相似度。

2.如权利要求1所述的一种二维单射曲面数据的特征提取和匹配方法，其特征在于，所述步骤2)中特征点集提取操作包括如下步骤：

2.1)以图像中的每一个灰度值作为灰度参考值，获得一系列等灰度线，所述灰度参考值至少对应一条等灰度闭合曲线，所述等灰度线上的所有像素点的灰度值都相等；

2.2)按逆时针方向遍历等灰度线上的像素点，计算每一个像素点所在位置的曲率，设p为设定长度的等灰度线上的弧线段邻域U(p，s)内的曲率极小值点，且曲率小于0，如果该邻域内所有像素点的曲率都小于0，则记p为凹点，所述曲率K在像素点E处的计算公式如下：其中：F为像素点E按逆时针方向在等灰度线上的下一个相邻像素点，Δθ指的是以逆时针旋转方向为正方向，像素点E处的切线向量旋转到像素点F处的切线向量的旋转角度，角度的取值范围为[-π，π]，E处的所述切线向量的计算公式为(xF-xE，yF-yE)，x、y分别为像素点的横坐标和纵坐标，F处的所述切线向量的计算公式为(xG-xF，yG-yF)，G为像素点F按逆时针方向在等灰度线上的下一个相邻像素点，||F-E||指的是像素点F与像素点E之间的距离；

2.3)通过步骤2.2)获得一个凹点集，如果两个凹点之间的距离小于设定的值，则称这两个凹点相邻，若凹点T1与凹点T2相邻，凹点T2与凹点T3相邻，则称凹点T1与凹点T3也相邻，根据凹点之间相邻的关系从而将凹点集划分成一些凹点子集，去掉包含凹点数小于设定数目的凹点子集，对于每一个保留的凹点子集，如果所述凹点子集中存在两个凹点，这两个凹点之间的距离小于设定的值，且它们属于同一条等灰度线，并且它们为该凹点子集中灰度值的最大值点，则这两个凹点就是图像的两个特征点，所述特征点在凹点子集中，应该是成对出现的，所有的特征点则构成特征点集。

说明书

一种二维单射曲面数据的特征提取与匹配方法

技术领域

[0001] 本发明涉及一种二维单射曲面数据的特征提取和匹配方法，特别涉及一种基于Reeb图的二维单射曲面数据的特征提取和匹配方法。

背景技术

[0002] 随着科学技术不断发展，信息爆炸时代来临，二维单射曲面信息越来越多，例如地形图、三维光谱、水体的温度或物质分布图等等。大量的二维单射曲面信息的数据库相继建成。显然，人工检索存在费用昂贵、耗时长、漏检率高的缺点。利用计算机进行检索，往往是最好的选择。但对于一个庞大的数据库，如果逐点比对，计算机检索时间仍然过长。为了缩短检索时间，可对数据进行特征提取，然后用特征进行检索。这种方法除了显著缩短检索时间外，还可以克服不同仪器的系统误差对检索结果造成的负面影响。

[0003] 二维单射曲面数据可以表示为xy平面的单射函数，即可以用函数表示为：

[0004] g＝f(x，y) (1)

[0005] 本发明提出了一种可表示为xy平面的单调函数的二维单射曲面数据特征提取和匹配方法。目前国内外已经存在一些二维单射曲面数据特征的提取方法，其中Goldgof等在《Feature extraction and terrain matching》，1988，Proceedings of Computer Society Conference On Computer Vision & Pattern Recognition，pp.899-204中提出利用高斯曲率极值点作为地形的特征，但这种方法对噪音很敏感，特征不够稳定。Yu等在《A novel contour-based 3D terrain matching algorithm using wavelet transform》，2004，Pattern Recognition Letters，vol.25，pp.87-99中提出利用少数等高线作为整个
3D地形的特征，但少数等高线并不能很好地描述整体的地形，而采用更多的等高线则会提高复杂度。已有的对二维单射曲面数据特征提取的方法，大部分都是基于点、线、面等特征。
但这些特征描述的都是具体的细节，因而使得获得的特征不够稳定。

[0006] Reeb图是由法国Georges Reeb首次提出的，之后就被成功地应用在三维形状造型、体可视化等领域中。Reeb图包含了数据的骨架和拓扑结构信息。拓扑结构代表的是数据的整体信息，并且对具体的细节并不敏感。Hilaga等在《Topology matching for fully automatic similarity estimation of 3D shapes》，In Proceedings of SIGGRAPH 2001，ComputerGraphics Proceedings，Annual Conference Series，pp.203-212中提出了使用多分辨率Reeb图(MRG)来表示三维模型的特征。MRG是用多个Reeb图描述了三维模型拓扑结构信息。由于MRG是基于近似测地线形成的，使得MRG受三维模型表面细节的影响较大，并且计算了多个Reeb图，也使得算法复杂度高。

发明内容

[0007] 本发明的目的在于提出一种新型的二维单射曲面数据的特征提取和匹配方法，使得提取的特征容易计算，并且稳定性强。

[0008] 本发明的技术方案如下：

[0009] 一种二维单射曲面数据的特征提取和匹配方法，其特征在于该方法包含如下步骤：

[0010] 1)将二维单射曲面数据投影到xy平面，获取一幅灰度与g值成正比的灰度图像，将图像的灰度值归一化到区间[0，255]，并利用高斯窗口对图像进行平滑操作，以减弱图像中的噪音；

[0011] 2)从图像中提取特征点集，以特征点集中的每一个特征点作为参考点，按照灰度值是否与该特征点相等，在图像中绘制通过该特征点的等灰度线，以及绘制同一等灰度线上特征点之间的连线，等灰度线以及特征点之间的连线将图像划分成一系列的区域块，根据区域块之间的包围和相邻关系构造一个Reeb图；

[0012] 2.1)以图像中的每一个灰度值作为灰度参考值，获得一系列等灰度线，所述灰度参考值至少对应一条等灰度闭合曲线，所述等灰度线上的所有像素点的灰度值都相等；

[0013] 2.2)按逆时针方向遍历等灰度线上的像素点，计算每一个像素点所在位置的曲率，设p为设定长度的等灰度线上的弧线段邻域U(p，s)内的曲率极小值点，且曲率小于0，如果该邻域内所有像素点的曲率都小于0，则记p为凹点，所述曲率K在像素点E处的计算公式如下：

[0014]

[0015] 其中：F为像素点E按逆时针方向在等灰度线上的下一个相邻像素点，Δθ指的是以逆时针旋转方向为正方向，像素点E处的切线向量旋转到像素点F处的切线向量的旋转角度，角度的取值范围为[-π，π]，E处的所述切线向量的计算公式为(xF-xE，yF-yE)，x、y分别为像素点的横坐标和纵坐标，F处的所述切线向量的计算公式为(xG-xF，yG-yF)，G为像素点F按逆时针方向在等灰度线上的下一个相邻像素点，||F-E||指的是像素点F与像素点E之间的距离；

[0016] 2.3)通过步骤2.2)获得一个凹点集，如果两个凹点之间的距离小于设定的值，则称这两个凹点相邻，若凹点T1与凹点T2相邻，凹点T2与凹点T3相邻，则称凹点T1与凹点T3也相邻，根据凹点之间相邻的关系从而将凹点集划分成一些凹点子集，去掉包含凹点数小于设定数目的凹点子集，对于每一个保留的凹点子集，如果所述凹点子集中存在两个凹点，这两个凹点之间的距离小于设定的值，且它们属于同一条等灰度线，并且它们为该凹点子集中灰度值的最大值点，则这两个凹点就是图像的两个特征点，所述特征点在凹点子集中，应该是成对出现的，所有的特征点则构成特征点集。

[0017] 3)选取高度和位置作为典型的细节特征，将这两个细节特征作为Reeb图中的每个结点的属性，所述高度是指该结点所代表的图像区域块内灰度最高值与灰度最低值之差，所述位置是指该结点所代表的图像区域块的中心位置，所述中心位置的具体计算公式如下：

[0018]

[0019] 其中：N指的是所述图像区域中像素点的个数，(x，y)i指的是像素点i的坐标，(x，y)center指的是所述图像区域中心像素点的坐标；

[0020] 4)对于需要匹配的两个数据，通过计算两个对应的A Reeb图和B Reeb图之间的相似度来求得这两个数据之间的相似度：

[0021] 4.1)将A Reeb图中的根结点a与B Reeb图中的根结点b相匹配，根结点指的是Reeb图中没有父结点的结点，得到一个匹配对，并计算所述匹配对的相似度，具体公式如下：

[0022]

[0023] 其中：dis(a位置，b位置)表示的是根结点a与根结点b的位置属性的欧式距离；

[0024] 4.2)如果两个结点相匹配，则继续对它们的子结点之间进行两两匹配，构成一个完全二分图，从所述二分图中提取一个结点距离之和最小的子图，从而构成两个结点的子结点之间的匹配对，每个结点至多在一个匹配对中出现，且匹配对中的两个结点来自两个不同的Reeb图；

[0025] 4.3)计算步骤4.1)和步骤4.2)中得到的所有的匹配对的相似度之和，所述相似度之和就是所述A Reeb图与所述B Reeb图之间的相似度，即两个数据之间的相似度。

[0026] 所述方法将二维单射曲面数据预处理成灰度值与g值成正比的图像，并将图像中的灰度值归一化到区间[0，255]中，然后从图像中检测出一些特征点，特征点是根据图像的等灰度线上的曲率极小值点定义的。以特征点作为参考点，在图像中绘制通过该特征点的等灰度线，且在图像中连接同一等灰度线上的特征点，这些等灰度线以及特征点之间的连线将图像划分成连续的区域块，根据区域块之间的包围和相邻关系构造一个Reeb图；为Reeb图中的每一个的结点赋予包含典型细节特征的属性。通过结点之间的匹配，计算属性之间的距离，从而实现两个二维单射曲面数据之间的匹配。因此本发明所述的技术方案可以从二维单射曲面数据中提取一种区别性强的特征，并且该特征具有容易计算，对噪音不敏感的特点。通过计算Reeb图中各个匹配结点属性之间的相似度之和，就可以计算两个二维单射曲面数据之间的相似度。

附图说明

[0027] 图1为本发明的二维单射曲面数据特征提取方法的主要模块和流程。

[0028] 图2为二维单射曲面数据的投影示意图。

[0029] 图3为二维单射曲面数据的凹点示意图。

[0030] 图4(a)、(b)为二维单射曲面数据的Reeb图示意图。

具体实施方式

[0031] 以下结合附图对本发明的具体实施方式作详细说明。

[0032] 一、本发明实施方式的二维单射曲面数据特征提取方法的主要模块和流程[0033] 如图1所示为本发明实施方式的二维单射曲面数据特征提取方法的主要模块和流程。

[0034] 1)将二维单射曲面数据投影到xy平面，获取一幅灰度与g值成正比的灰度图像，将图像的灰度值归一化到区间[0，255]，并利用高斯窗口对图像进行平滑操作，以减弱图像中的噪音；

[0035] 2)从图像中提取特征点集，以特征点集中的每一个特征点作为参考点，按照灰度值是否与该特征点相等，在图像中绘制通过该特征点的等灰度线，以及绘制同一等灰度线上特征点之间的连线，等灰度线以及特征点之间的连线将图像划分成一系列的区域块，根据区域块之间的包围和相邻关系构造一个Reeb图；

[0036] 3)选取高度和位置作为典型的细节特征，将这两个细节特征作为Reeb图中的每个结点的属性，所述高度是指该结点所代表的图像区域块内灰度最高值与灰度最低值之差，所述位置是指该结点所代表的图像区域块的中心位置，所述中心位置的具体计算公式如下：

[0037]

[0038] 其中：N指的是所述图像区域中像素点的个数，(x，y)i指的是像素点i的坐标，(x，y)center指的是所述图像区域中心像素点的坐标；

[0039] 4)对于需要匹配的两个数据，通过计算两个对应的A Reeb图和B Reeb图之间的相似度来求得这两个数据之间的相似度：

[0040] 4.1)将A Reeb图中的根结点a与B Reeb图中的根结点b相匹配，根结点指的是Reeb图中没有父结点的结点，得到一个匹配对，并计算所述匹配对的相似度，具体公式如下：

[0041]

[0042] 其中：dis (a位置，b位置)表示的是根结点a与根结点b的位置属性的欧式距离；

[0043] 4.2)如果两个结点相匹配，则继续对它们的子结点之间进行两两匹配，构成一个完全二分图，从所述二分图中提取一个结点距离之和最小的子图，从而构成两个结点的子结点之间的匹配对，每个结点至多在一个匹配对中出现，且匹配对中的两个结点来自两个不同的Reeb图；

[0044] 4.3)计算步骤4.1)和步骤4.2)中得到的所有的匹配对的相似度之和，所述相似度之和就是所述A Reeb图与所述B Reeb图之间的相似度，即两个数据之间的相似度。

[0045] 二、本发明实施方式的二维单射曲面数据的投影示意图

[0046] 如图2所示为本发明实施方式的二维单射曲面数据的投影示意图。二维单射曲面数据通过投影，可获得一个灰度值与高度成正比的灰度图像，并且通过归一化的方法将图像的灰度值映射到区间[0，255]内。以图像中的每一个灰度值作为灰度参考值，获得一系列等灰度线，所述灰度参考值对应至少一条等灰度闭合曲线，所述等灰度线上的所有像素点的灰度值都相等。

[0047] 三、二维单射曲面数据的凹点示意图

[0048] 如图3所示为本发明实施方式的二维单射曲面数据的凹点示意图。

[0049] 按逆时针方向遍历等灰度线上的像素点，计算每一个像素点所在位置的曲率，设p为设定长度的等灰度线上的弧线段邻域U(p，s)内的曲率极小值点，且曲率小于0，如果该邻域内所有像素点的曲率都小于0，则记p为凹点。限定设定长度领域内所有的像素点的曲率都小于0，是为了防止等灰度线上的噪音被误检测成凹点。图3中的4个点即为检测出来的凹点。所述曲率K在像素点E处的计算公式如下：

[0050]

[0051] 其中：F为像素点E按逆时针方向在等灰度线上的下一个相邻像素点，Δθ指的是以逆时针旋转方向为正方向，像素点E处的切线向量旋转到像素点F处的切线向量的旋转角度，角度的取值范围为[-π，π]，E处的所述切线向量的计算公式为(xF-xE，yF-yE)，x、y分别为像素点的横坐标和纵坐标，F处的所述切线向量的计算公式为(xG-xF，yG-yF)，G为像素点F按逆时针方向在等灰度线上的下一个相邻像素点，||F-E||指的是像素点F与像素点E之间的距离；

[0052] 获得一个凹点集后，如果两个凹点之间的距离小于设定的值，则称这两个凹点相邻，若凹点T1与凹点T2相邻，凹点T2与凹点T3相邻，则称凹点T1与凹点T3也相邻，根据凹点之间相邻的关系从而将凹点集划分成一些凹点子集，去掉包含凹点数小于设定数目的凹点子集，对于每一个保留的凹点子集，如果所述凹点子集中存在两个凹点，这两个凹点之间的距离小于设定的值，且它们属于同一条等灰度线，并且它们为该凹点子集中灰度值的最大值点，则这两个凹点就是图像的两个特征点，所述特征点在凹点子集中，应该是成对出现的，所有的特征点则构成特征点集。在实际设计中，采集的等灰度线会非常密集，则图3中的4个凹点会因为距离相近而分配到同一个凹点子集中，中间的两个凹点因为满足特征点的条件，则会被检测成两个特征点。两个凹点被检测成特征点需满足三个条件，这三个条件分别是，一是这两个凹点属于同一个凹点集且这两个凹点之间的距离小于设定的值，二是这两凹点的灰度值相等，三是灰度值必须是凹点集中的最大值。

[0053] 四、本发明实施方式的二维单射曲面数据的Reeb图示意图

[0054] 如图4(a)、4(b)所示为本发明实施方式的二维单射曲面数据的Reeb图示意图。根据步骤(2.3)中获得的特征点，以每一个特征点作为一个参考点，在图像中绘制一条通过该特征点的等灰度线，如图4的(a)中黑线所示。同时在属于同一条等灰度线的特征点(图中的红点)之间绘制一条线，等灰度线和特征点之间的线将图像划分成一些连续的区域块，m0、m1、m2。每个连续区域块对应Reeb图中的一个结点，如果结点a所对应的区域块包围结点b所对应的区域块，且这两个区域块相邻，如m0与m1，m0与m2，则在结点a与结点b之间构造一条边，所有的结点以及结点之间的边构成一个Reeb图，如图4(b)所示。将高度和位置作为Reeb图中的每个结点的属性，高度指的是该结点所代表的图像区域块内灰度最高值与灰度最低值之差，位置指的是该结点所代表的图像区域块的中心位置。