基于知识的部分匹配方法研究

第２９卷第６期　２０１２年６月　计算机应用研究　Ａｐｐｌｉｃａｔｉｏｎ　Ｒｅｓｅａｒｃｈ　ｏｆ　Ｃｏｍｐｕｔｅｒｓ　Ｖｏ１．２９　Ｎｏ．６　

Ｊｕｎ．２０１２　

基于知识的部分匹配方法研究　张小洪，李相军，林晓泽　（重庆大学软件学院，重庆４０００３０）　

摘要：针对Ｓｕｐｅｒ提出的基于知识的部分匹配方法中，直接以坐标值描述部分轮廓的方法容易受形变或扭曲　等干扰因素的影响，基于ＳＩＦＴ描述思想提出了一种新的ＢＳＩＦＴ轮廓描述子，用于改进Ｓｕｐｅｒ的坐标值描述方法。　首先介绍了基于知识的部分匹配方法的基本思想、特点及实现过程；然后详细阐述了ＢＳＩＦＴ描述子的构建方法；　最后，通过实验验证了该方法具有更好的鲁棒性，部分匹配的准确度更高，匹配的部分轮廓更有意义。　关键词：部分轮廓；ＢＳＩＦＴ描述子；概率函数；部分匹配　中图分类号：ＴＰ３９１　文献标志码：Ａ　文章编号：１００１—３６９５（２０１２）０６—２３９７—０４　ｄｏｉ：１０．３９６９／ｊ．ｉｓｓｎ．１００１—３６９５．２０１２．０６．１０７　

Ｒｅｓｅａｒｃｈ　ｏｎ　ｋｎｏｗｌｅｄｇｅ—ｂａｓｅｄ　ｐａｒｔ　ｃｏｒｒｅｓｐｏｎｄｅｎｃｅ　ｍｅｔｈｏｄ　ＺＨＡＮＧ　Ｘｉａｏ—ｈｏｎｇ，ＬＩ　Ｘｉａｎｇ－ｊｕｎ，ＬＩＮ　Ｘｉａｏ—ｚｅ　（Ｓｃｈｏｏｌ　ｏｆＳｏｆｔｗａｒｅ　Ｅｎｇｉｎｅｅｒｉｎｇ，Ｃｈｏｎｇｑｉｎｇ　Ｕｎｉｖｅｒｓｉｔｙ，Ｃｈｏｎｇｑｉｎｇ　４０００３０，Ｃｈｉｎａ）　

Ａｂｓｔｒａｃｔ：Ｆｏｃｕｓｉｎｇ　ｏｎ　ｔｈｅ　ｐｒｏｂｌｅｍ　ｏｆ　ｐａｒｔ　ｒｅｐｒｅｓｅｎｔａｔｉｏｎ　ｂａｓｅｄ　ｏｎ　ｃｏｏｒｄｉｎａｔｅ—ｖａｌｕｅｓ　ｉｎ　Ｓｕｐｅｒ’Ｓ　ｋｎｏｗｌｅｄｇｅ—ｂａｓｅｄ　ｐａｒｔ　ｃｏｒｒｅ—　ｓｐｏｎｄｅｎｃｅ　ａｌｇｏｒｉｔｈｍ，ｔｈａｔ　ｔｈｅ　ｃｏｎｔｏｕｒ’Ｓ　ｃｏｏｒｄｉｎａｔｅ　ｖａｌｕｅｓ　ａｒｅ　ｅａｓｙ　ｃｈａｎｇｅｄ　ｂｙ　ｔｈｅ　ｆａｃｔｏｒｓ　ｏｆ　ｄｅｆｏｒｍａｔｉｏｎ，ｄｉｓｔｏｒｔｉｏｎ　ａｎｄ　ＳＯ　ｏｎ．Ｔｈｉｓ　ｐａｐｅｒ　ｐｒｏｐｏｓｅｄ　ａ　ｎｏｖｅｌ　ＢＳＩＦＴ　ｄｅｓｃｒｉｐｔｏｒ　ｗｈｉｃｈ　ｗａｓ　ｂａｓｅｄ　ｏｎ　ｔｈｅ　ｉｄｅａ　ｏｆ　ＳＩＦＴ　ｄｅｓｃｒｉｐｔｏｒ　ｔｏ　ｉｍｐｒｏｖｅ　Ｓｕｐｅｒ’Ｓ　ｃｏｏｒｄｉ—　ｎａｔｅ—ｖａｌｕｅ　ｄｅｓｃｒｉｐｔｉｏｎ　ｍｅｔｈｏｄ．Ｆｉｒｓｔ，ｉｔ　ｉｎｔｒｏｄｕｃｅｄ　ｔｈｅ　ｂａｓｉｃ　ｉｄｅａｓ，ｃｈａｒａｃｔｅｒｉｓｔｉｃ　ａｎｄ　ｉｍｐｌｅｍｅｎｔａｔｉｏｎ　ｏｆ　ｋｎｏｗｌｅｄｇｅ－ｂａｓｅｄ　ｐａｒｔ　ｃｏｒｒｅｓｐｏｎｄｅｎｃｅ　ｍｅｔｈｏｄ，ｔｈｅｎ　ｄｅｓｃｒｉｂｅｄ　ｔｈｅ　ＢＳＩＦＴ　ｄｅｓｃｒｉｐｔｏｒ’Ｓ　ｃｏｎｓｔｒｕｃｔｉｏｎ　ｐｒｏｃｅｓｓ　ｉｎ　ｄｅｔａｉｌ．Ｆｉｎａｌｌｙ，ｔｈｅ　ｅｘｐｅｒｉｍｅｎｔ　ｒｅｓｕｌｔ　ｄｅｍｏｎｓｔｒａｔｅｓ　ｔｈｉｓ　Ｈｏｖｅｌ　ｍｅｔｈｏｄ　ｃａｎ　ｏｂｔａｉｎ　ａ　ｂｅｔｔｅｒ　ｒｏｂｕｓｔｎｅｓｓ，ｇｅｔ　ｈｉｇｈｅｒ　ａｃｃｕｒａｃｙ　ａｎｄ　ｌｅｔ　ｔｈｅ　ｍａｔｃｈｉｎｇ　ｐａｒｔｓ　ｍｏｒｅ　ｍｅａｎｉｎｇ—　ｆｕｌ＿　Ｋｅｙ　ｗｏｒｄｓ：ｐａｒｔ　ｃｏｎｔｏｕｒ；ＢＳＩＦＴ　ｄｅｓｃｒｉｐｔｏｒ；ＣＰＦ（ｃｈａｎｃｅ　ｐｒｏｂａｂｉｌｉｔｙ　ｆｕｎｃｔｉｏｎｓ）；ｐａｒｔ　ｃｏｒｒｅｓｐｏｎｄｅｎｃｅ　

０　引言　目前对于形状匹配问题的研究主要集中在两个形状之间　的匹配问题的研究。形状轮廓作为形状最显著的特征，一直是　形状匹配研究中的研究重点…。至今，学者们已提出了大量　的形状匹配方法，这些方法可以分为几何形状匹配方法和结构　化匹配方法。　几何匹配方法通过寻找形状之问轮廓点或底层空间数据　的对应关系进行匹配，这类方法的主要缺点是形状底层空间数　据之间的对应关系很模糊，容易造成歧义现象。针对此问题，　学者们提出许多改进方法，这些方法基于全局优化　’　或中心　点上下文信息　来消除底层空间数据之间的模糊性。例如：　Ｍｏｉｌ等人提出的形状上下文匹配方法　Ｊ，该方法具有平移、旋　转和伸缩不变等特征；Ｂａｉ等人　研究了形状骨骼线，提出了　形状骨骼匹配方法；Ｌｉ等人　定义了一种复杂矩用于形状的　特征描述；ｘｕ等人　定义了一种轮廓柔韧性来实现二维形状　的匹配等。　结构化匹配方法基于形状的部分轮廓，以及部分轮廓之间　的相互关系来匹配形状。这种方法的主要缺点是结构化表示　的可靠性很差，因为较小的几何变换就可能导致形状结构上发　生很大的变化。目前，解决该问题的主要方法都是通过构建近　似的图、树或序列进行形状匹配　”　。　针对目前几何方法和结构化方法存在的问题，Ｓｕｐｅｒ　１４］提　出了一种基于知识的部分匹配方法，该方法从多个方面解决了　几何和结构化方法的缺点。首先，该方法采用复合分割的方式　减少底层几何数据的模糊性，生成的复合ｐａｒｔｓ更能体现形状　的本质特征；同时，与结构化方法相比，部分匹配方法直接用形　状之问的ｐａｒｔｓ进行匹配，不需要考虑部分轮廓之间的相互关　系；其次，基于知识的部分匹配方法不需要任何的形状类别信　息，可以处理任意类型的形状匹配问题。部分匹配可以视为是　介于几何和结构化方法之间的一种新方法。　在Ｓｕｐｅｒ方法中，分割出来的ｐａｒｔｓ直接以采样后轮廓点　的坐标值进行描述，而形状的轮廓容易受到形变、扭曲等干扰　因素的影响，使得轮廓点的坐标值变得不稳定，因此这种坐标　值描述方法不具有很好的鲁棒性。为此，本文提出了一种新的　用于部分轮廓描述的ＢＳＩＦＴ（ｂｏｕｎｄａｒｙ　ｓｃａｌｅ—ｉｎｖａｒｉａｎｔ　ｆｅａｔｕｒｅ　ｔｒａｎｓｆｏｒｍ）描述子，该描述子是基于ＳＩＦＴ　描述子的思想所构　建的。ＳＩＦＴ描述子＿１　对图像的旋转、尺度缩放、视角变化、仿　射变换以及噪声都具有较强的鲁棒性。实验表明，本文提出的　ＢＳＩＦＴ保持了ＳＩＦＴ描述子的强鲁棒性，与Ｓｕｐｅｒ方法相比，基　于ＢＳＩＦＹ描述子的部分匹配具有更好的匹配效果。　

收稿日期：２０１１—１０—３０；修回日期：２０１１—１２—０２　基金项目：国家自然科学基金资助项目（６０９７５０１５）；重庆大学研究生科技创新基金资助　项目（ＣＤＪＸＳＩＯ０９０００２）；中央高校基本科研业务费科研重点专项（ＣＤＪＺＲ１１０９５５０１）；重庆自然科学基金资助项目（ｃｓｒｓ２０１０ＢＢ２０６１）　作者简介：张小洪（１９７３－），男，教授，主要研究方向为模式识别、人工智能、软件工程及应用；李相军（１９８７一），男，重庆巫溪人，硕士研究生，主　要研究方向为模式识别（ｗｅｉｈａｉ　６２４＠１２６．ｃｏｍ）；林晓泽（１９８８－），男，福建泉州人，硕士研究生，主要研究方向为图像处理．　・２３９８・　计算机应用研究　第２９卷　１　基于知识的部分匹配方法　Ｓｕｐｅｒ提出了基于知识的部分匹配思想，其将部分匹配分　为ｐａｎ生成、ｐａｎ表示和ｐａｒｔ匹配三个部分。　

１．１　Ｐａｎ生成　在Ｓｕｐｅｒ的部分匹配方法中，采用复合分割的方式获取形　状的ｐａｒｔｓ。复合分割的步骤是：ａ）若Ｃ表示形状的轮廓，首先　采用特征检测算法获取形状的特征点集Ｋ＝｛ｋ　”，　｝；ｂ）对　于集合Ｋ中的任意两个值ｋ　、　，用［ｋ　，｜ｉ｝　］表示Ｃ中从点ｋ　到　点　包含的轮廓点，［ｋ　，　，］是不同特征点之间的方向间隔，有　［ｋ　，　ｕ［　，，ｋ　］＝Ｃ，［ｋ　，　，］表示形状的一个ｐａｎ。采用复合　分割的方式，若检测出形状轮廓有ｎ个特征点，则可分割出　ｎ（ｎ一１）个ｐａｎｓ。　Ｓｕｐｅｒ在其部分匹配方法中没有给出获取形状特征点的具　体方法。角点是轮廓最重要的特征之一，因此本文以轮廓角点　作为特征点。与其他角点检测算法相比，ＢＤｏＧ角点检测算　法　的实现简单，准确度高，因此本文用该方法获取形状的角　点信息。　复合分割获得的ｐａｎｓ，除了相邻角点构成的ｐａｒｔｓ只包含　单个角点的信息外，其他ｐａｎｓ都包含了多个角点的信息，有些　ｐａｎｓ甚至可以近似表示形状的整体轮廓。这种方式虽然包含　了一定的冗余数据，但却可以表示出形状及其部分轮廓在不同　形态下的分布，从而保证了匹配时，该方法对形状的旋转、缩放　等几何变换具有不变性。对于相邻角点构成的ｐａｎｓ，由于轮　廓段太小，显然这类ｐａｒｔｓ包含的有用信息很少。在部分匹配　时，可以通过设定阈值的方法将这些ｐａｎｓ去掉，从而减少算法　的计算时间。　１．２　Ｐａｎ表示　形状分割获得的ｐａｎｓ不具有尺度不变性，通过平移、旋　转、对称和缩放等几何变换方法将其统一到以角点为坐标轴的　［０，１］标准尺度空间，从而保证了每个ｐａｎ的几何不变性。同　时，不同的ｐａｎｓ包含的轮廓点个数不相同，因此需要对其进行　采样。Ｓｕｐｅｒ在其部分匹配方法中没有给出具体的采样方法，　本文根据ｐａｎ归一化后轮廓点的顺序进行均匀采样。采样的　计算过程如式（１）所示：　ｋ＝Ｎ／Ｓ　Ｐ＝ｋ　ｘｊ；　≤ｓ，第　次采样　Ｐ　＝ｉｎｔ（ｐ）；取整　，Ｉ、　ｓ＿Ｘ（　）＝Ｘ（ｐ　）＋（Ｘ（ｐ　＋１）一ｘ（ｐ　））×（ｐ－ｐ　）　ｓ—ｌ，∽：ｌ，（ｐｒ）＋　捌　（ｐ　ｒ））　其中：Ⅳ表示ｐａｎ包含的轮廓点个数；Ｓ是设置的采样数；Ｘ、Ｙ　表示ｐａｎ轮廓点坐标的　、Ｙ坐标值。该采样方法是按照采样　间隔，对相邻的两个点用线性插值的方法进行采样。ＰａＮ分割　和ｐａｎ表示的整个过程如图１所示。　Ｓｕｐｅｒ直接以ｐａｎ采样后轮廓点的坐标值描述形状，由于　形状受到形变或扭曲等因素干扰后，其局部轮廓会发生较大变　化，因此坐标值描述方法的稳定性较差。本文用ＢＳＩＦＴ描述子　表示ｐａｒｔ采样后的轮廓点。ＢＳＩＦＴ描述子通过多种加权操作，　可以很好地消除各种干扰因素对形状的影响，同时降低了ｐａｎ　表示的维度。本文第２章对ＢＳＩＦＴ描述子的构建过程进行了　详细的阐述。　轮　（ｈ）采样　（ｇＪ镅放变换　图１　Ｐａｒｔ分割及表示示意图　１．３　Ｐａｒｔ匹配　Ｓｕｐｅｒ提出了一种概率函数（ＣＰＦ）　用于匹配两个ｐａｎｓ。　ＣＰＦ的基本思想是：要判断Ｐ、ｑ之间的相似度，首先用一种度　量标准（如欧氏距离）计算出Ｐ、ｑ之间的距离Ｄ；然后用训练数　据库中的每个ｐａｒｔ分别与Ｐ、ｑ进行比较，求出获得一个到Ｐ或　ｑ的距离小于Ｄ的ｐａｎ的概率。也就是说，ＣＰＦ通过计算获得　一个新ｐａｎ，它与Ｐ或ｑ的相似度要高于Ｐ、ｇ之间相似度的概　率，来表示Ｐ、ｑ之间的相似性。如果这种概率值很低，则说明　Ｐ、ｇ之间的相似度很高；反之，则说明Ｐ、ｑ之间的相似度很低。　ＣＰＦ与以往依靠某种度量标准来计算两个物体之问的相　似性的方法不同，它引入了一个知识库，通过与知识库中已有　物体的比较，来确定两个物体相似的概率值。这种匹配的思　想，符合人类视觉系统对事物的认知过程。　２　ＢＳＩＦＴ描述子　ＳＩＦＴ描述子是一种用于图像区域特征描述的鲁棒描述方　法。本文基于ＳＩＦＴ描述子的基本思想，提出了一种用于轮廓　曲线特征描述的ＢＳＩＦＴ描述子。两种描述方法的主要区别在　于位置、高斯、方向加权的实现。　对分割出的每个ｐａｎ，ＢＳＩＦＦ描述子首先计算该轮廓段上　点的梯度方向和梯度模值，如式（２）所示。对于ｐａｎ上的每个　点，根据与其相邻的前后两个点的坐标值计算该点的梯度值和　梯度方向。　ｍ（ｉ）＝￣／（ｙ（ｉ＋１）一ｙ（ｉ一１））‘＋（　（ｉ＋１）一　（ｉ一１））‘　（　）＝ａｔａｎ　２（（ｙ（　＋１）一ｙ（　一１））／（　（ｉ＋１）一　（ｉ—Ｉ）））（２）　类似于ＳＩＦＦ描述子需要对其邻域进行分块，在计算ｐａｎ　的权重之前，首先需要将其轮廓进行分段。若采样后的ｐａｒｔ有　Ｓ个点，设分段间隔为Ｄ，则可将该ｐａｎ分为Ｓ／Ｄ段，表示为ｎ。　每Ｄ个轮廓点被分为一段，每一段的中心点作为该段的加权　点，用ｃ，（第　段的中心点）表示。对ｐａｎ上的每个轮廓点，依　次计算其高斯、位置、方向加权，然后将同一分段内的所有轮廓　点的权重向量累加，生成描述子。ＢＳＩＦＴ描述子的加权过程如