基于最小惯性轴及链码的图像形状描述方法.doc

第4期李宗民等：基于最小惯性轴及链码的图像形状描述方法5基于最小惯性轴及链码的图像形状描述方法李宗民1，陆天波2，桑鑫焱1，秦宝山3（1. 中国石油大学（华东） 计算机与通信工程学院，山东 东营 257061；2. 国家计算机网络应急技术处理协调中心，北京 100029；3. 北京邮电大学，北京 100876）摘 要：提出了基于最小惯性轴及链码的结合方法，这种方法能够同时利用形状边界轮廓和区域信息，并利用由特征点和形状质心构成的特征三角形计算得出的三角隶属函数值作为重要特征值进行相似性计算。此方法对于形状的转换是不变的，对凹边形匹配是健壮的，通过实验对比，此方法具有较高的检索性能。关键词：最小惯性轴；多边形；顶点；质心中图分类号：TP391.41 文献标识码：A 文章编号：1000-436X(2009)04-0001-05Shape description based on axis of least inertia and chain LI Zong-min1, LU Tian-bo2, SANG Xin-yan1, QIN Bao-shan3(1. School of Computer Science and Communication Engineering, China University of Petroleum, Dongying 257061, China;2. National Computer Network Emergency Response Technical Team/Coordination Center of China, Beijing 100029, China;3. Beijing University of Posts and Telecommunications, Beijing 100876, China)Abstract: The imaged could be seemed to the approximation of the polygons, so it was important to the image match that researched the polygon match method. It is based the combination of the axis of least inertia and the chain, this method was capable of preserving both contour as well as region information, and it utilized the degree of triangular membership which computed by the feature triangular to compute the similarity between the two objects. This method was invariant to image transformations, and robust to concave polygons. The experimental results show that this methods performance and retrieval efficiency is well.Key words: axis of least inertia; polygon; vertices; centroid1 引言如果将二维空间中的图像细致化，就可以将它们看作是多边形的近似。因而通过研究多边形匹配对基于形状的图像检索有着重要意义。收稿日期：2008-08-26；修回日期：2008-12-28基金项目：国家重点基础研究发展计划（“973”计划）基金资助项目（2004CB318000, 2007CB311100）；国家自然科学基金资助项目（60533090）Foundation Items: The National Basic Research Program of China (973 Program) (2004CB318000, 2007CB311100); The National Natural Science Foundation of China (60533090)Perez与Vidal1于1994年提出了数字化曲线的多边形逼近理想算法，这种算法的思想是基于动态规划的，算法的复杂度是O(P2S)，其中P是点的数目，S是片段数量。2001年，Marc Salotti2对于这种算法，利用启发式搜索策略的框架来找到一幅图中最短路径，从而使得复杂度接近O(P2)，可以看出，它不依赖于图像边界的片段数量。杨平3采用三角剖分算法将多边形重心与顶点连线，组成一系列三角形从而进行图形匹配，这种算法具有空间不变性且简单高效，但是不适用于凹多边形的匹配。Lun Hsing Tung4提出多边形检索的两步框架算法。首先利用二元形状描述子（BSD）执行多边形分类修剪搜索空间从而加速查询；第二步采用多重分解、区域匹配的方法进行多边形相似性的定性度量。孙百勇5提出基于钝角演化规则的多边形形状识别，采用多边形的合并与生长规则，使得目标对象与模型对象边数相同时开始计算配准，这种方法在执行过程中不需要设置任何参数，效果比较理想，但是因为要考虑边角的变化，因而复杂度较高。王学飞6提出一种适合凸凹多边形匹配的分层加权测度方法，对凹多边形进行模式分解形成新的凸多边形，然后利用预定义的互为模板的相似度量准则和分层加权测度模型计算多边形的相似度系数，这种方法结果虽然比较理想，但是在进行模式分解时对于复杂多边形是不易执行的。王丹7采用形心和形心与各顶点的连线来描述多边形，并通过线性差值对应连线的长度和相连两连线间的夹角得到几何信息从而生成多边形各顶点，这种方法虽然比Thomas8的方法多了凹凸性判断、终点对称变换及最后插值时的逆中点变换，但复杂度仍为O(N)。谢萍等人9提出快速复杂多边形匹配算法，该算法基于正切空间表示，先对复杂多边形进行离散曲线演化再选择简化得到的最大凸弧线作为匹配起始点，该算法能对复杂多边形快速精确匹配且不受噪声影响，但是受阈值影响较大，需要及时更改阈值的选取。D.S.Guru等人10提出利用最小惯性轴这个能保存形状方向的唯一相关直线来表示形状，这种方法可以同时保存轮廓和区域信息，对于形状转换是不变的，并且不像基于区域方法，它能考虑一个形状的内部细节，提高了检索能力。而错配原因主要是因为形状比例的不统一变化或者最小惯性轴方向的较大改变引起。对于以上提到的几种典型方法，首先进行了实验分析，利用统一的多边形图像库进行实验，并在现有的基础上进行结合改进，把新的方法实验结果与其他方法进行了对比。这篇文章的组织结构如下：第2节是方法的提出；第3节是实验结果对比；第4节是结束语。2 方法的提出及改进在此方法中，依然选择了最小惯性轴作为特征提取和形状相似性度量的参考，而与文献10,11不同的是，利用了类似于链码的编码方式来进行特征提取，这个方法方便快速，且检索率高。2.1 最小惯性轴最小惯性轴是与图形边界所有点之间全部距离的平方取积分后值最小的一条线，它的物理含义是图形绕此轴的转动惯量最小，它是保存图形形状定位的唯一参考线。在找到图形的最小惯性轴之后，将形状曲线上的所有点投影到轴上，距离最远的2个点E1和E2称为极点，两点间的距离称作轴长10。而由最小惯性轴物理定义可知，它必然通过图形的质心G。其数学表达式为：设直线，则最小惯性轴为其中，为边缘点集。再利用最小惯性轴过质心这一条件：，便可求出B、C，从而得出最小惯性轴表达式。在过去的工作中，已经通过利用最小惯性轴及图像边界上的特征点进行了检索实验，这种方法能同时利用形状边界轮廓和区域信息，对于形状的转换（平移、旋转、投影、尺度缩放）都是不变的。而实验证明，这种算法具有较高的性能和检索效率11。2.2 多变形的仿链码表示链码通过一个给定方向上的单位尺寸的直线片段的序列来描述目标。如果链码被用于匹配，它必须依赖于这个序列中第一边界像素的选择。对于归一化链码的一种可能性是找出边缘序列的像素；另一种则可以通过链码上逐次方向的差分代替通过相对方向表示边界。通过一个能产生最小索引的循环置换获得一个旋转不变性的链码。这样的一个归一化微分链码称为形状索引。尽管它能够将2个近似形状缩放到同一尺寸，但是结果形状的索引可能不同，导致2个形状的匹配不切实际。从一个选择的起点，通过利用4方向或8方向链码生成一个链码。以最小惯性轴为参考轴，通过它的垂线共同建立坐标系，图像质心为坐标系原点，然后根据方向链码的做法再将坐标系的4个区域分别从3个方向上3等分（依据经验取3），这样整个图像就被从12方向上生成一个链码。因为多边形的凹凸性，12条直线与图像边界的交点会等于或大于12个，因此为了在下一步的相似性度量中有一个统一标准且能对凹凸性增强识别性，规定当一个方向上的交点大于1时，采取加权处理方式。如图1所示：G是质心，规定距离质心较近的极点所在方向为0方向，逆时针分别为011方向，在方向CG上，直线于多边形边界交点大于1，、分别是这个方向上形成的3个特征三角形。图1 图像的12方向仿链码及特征三角形2.3 相似性度量及不变性性质因为整幅图像被12方向等分，而特征三角形中质心顶点的角度必定为30，所以利用三角隶属函数进行相似性度量。对于每个特征三角形，设、分别为三角形内角，且，对于它们有以下关系：，则可以求出其三角隶属函数：(1)(2)其中，d为特征三角形顶点间的欧式距离。对于待检索图像M的第n个特征三角形的隶属值及数据库中图像Q的第n个特征三角形的隶属值，它们之间的相似度为(3)所有特征值的全部相似度为(4)如果，则表明2个图像越相似。当同一方向上的交点大于1时，做一个加权处理，目的是平衡多个特征三角形的隶属度值，使得此特征点的隶属度更精确，便于对比。加权公式为(5)在此方法中，它具有以下不变性性质。性质1 缩放不变性当图像进行缩放时，通过交点和质心构造的三角形内角角度不发生改变，这样，三角隶属度及比值不会发生改变，因此是缩放不变的。性质2 旋转不变性最小惯性轴对于旋转是不变的，但是由于旋转使得多边形顶点顺序发生改变从而使得提取的特征三角形顺序可能发生改变，所以规定每次匹配均从第1方向开始。性质3 平移不变性这个性质是自动达到的。性质4 投影不变性最小惯性轴随同形状一同投影，且通过保存起始点使其保持在同一直线，因此具有投影不变性。3 实验对比下面分别针对现有的几种方法进行实验比较，这几种方法包括三角剖分方法3、形心法7以及改进方法。所采用的实验图库包括10类多边形，其中每类包含50幅图像。实验数据及对比结果如图3图5所示，其中图2图4分别为3类多边形的匹配结果，图内数字为相似度，第一列为待检索图像；图5为3种方法的查全查正率对比效果图。图2 三角形匹配结果图3 四边形匹配结果图4 任意多边形匹配结果从图5的检索结果及查全查正率对比看出，改进方法要优于其他2种方法，而且对凹多边形具有较高的检索率。图5 3种实验方法查全查正率对比当把此种方法用于其他不规则形状，也能得出比较理想的匹配效果，将这种方法用于人体图库，如图6所示，利用17号图像作为待检索图像，并将实验结果与文献11提到的方法进行对比，效果图如图7所示，而对比实验数据可以参照表1。图6 人体图库(a) 利用最小惯性轴方法得出的结果(b) 利用最小惯性轴与链码结合得出的结果图7 比较图表12种方法的相似度对比及图像排名相似图像原始最小惯性轴法最小惯性轴与链码结合法相似度排 名相似度排 名1 #0.870 540.903 529 #0.871 430.861 6517 #1.000 011.000 0118 #0.860 850.701 31028 #0.834 860.878 5429 #0.832 270.725 7933 #0.699 7100.798 78而这种方法的不变性也可以通过实验来验证，随机抽取人体图库中的图像，比如将17号图像进行缩放、平移、旋转后的检索结果如图8所示，而相似度与排名可以参照表1与表2进行对比。通过数据发现，变换前后的检索结果是完全一致的，因此这种方法具有较高的缩放、平移、旋转不变性。图8 图像的不变性实验表2不变性实验结果对比相似图像变换前检索结果变换后检索结果相似度排 名相似度排 名1 #0.903 520.903 529 #0.861 650.861 6517 #1.000 011.000 0118 #0.701 3100.701 31028 #0.878 540.878 5429 #0.725 790.725 7933 #0.798 780.798 78从以上的实验结果可以看到，这种方法也没有受到干扰图像的影响，而且对于掩蔽的图像（比如图7(b)中最后一幅图像）做出了正确的判断。而且从复杂度方面，这种方法直接利用质心将图像平面进行方向划分，无需进行边界特征点及最小惯性轴上特征点的判断寻找，这大大降低了计算的复杂度。4 结束语这种方法的优点是既利用了最小惯性轴这一确定图像的唯一轴，能同时利用边界和区域信息，又结合了链码方法，使得在复杂度上大大降低，而又不影响匹配效果。而对于凹多边形，还存在一定的错配和误差，这主要是因为形状比例的不统一变化及最小惯性轴方向的较大改变。因此，在今后的工作中将继续寻找更好的方法来改进对凹多边形的匹配。参考文献：1PEREZ J C. Optimum polygonal approximation of digitized curvesJ. PR Letters, 1994, 15(8): 743-750. 2SALOTTI M. An efficient algorithm for the optimal polygonal approximation of digitized curvesJ. PR Letters, 2001, 22(2): 215-221.3杨平, 林意. 一种三角剖分算法实现图形的匹配J.计算机应用与软件, 2003, 20(2):165-168.YANG P, LIN Y. A simple method for graphics matching using triangle segmentationJ. Computer Applications and Software, 2003, 20(2): 165-168.4TUNG L H, KING I. A two-stage framework for polygon retrievalJ. Multimedia Tools and Applications,2000,11(2):235-255.5孙百勇.基于钝角演化规则的多边形形状识别J. 计算机工程与科学, 2003, 25(2):105-107.SUN B Y. Polygonal shape recognition based on obtuse angle evolution rulesJ. Computer Engineering & Science, 2003, 25(2): 105-107.6王学飞, 胡青泥. 基于分层加权的多边形图形匹配J. 工程图学学报, 2002, (2):89-96.WANG X F, HU Q N. A multi-lager weighted approach to polygonal shapes matchingJ. Journal of Engineering Graphics, 2002, (2): 89-96.7王丹, 康宝生. 基于形心与顶点连线表示的多边形变形J. 工程图学学报, 2006, (3):115-120.WANG D, KANG B S. Metamorphosis of planar polygonsJ. Journal of Engineering Graphics, 2006, (3): 115-120.8SEDERBERG T W, GREENWOOD E. A p