多边形顶点匹配优化算法

Optimal vertex matching algorithm for polygonal shapes

分析了3种有代表性的平面多边形顶点匹配算法的特点,即基于极小化形变功的匹配算法、基于轮郭绕行趋势变化的匹配算法和基于边界局部剖分的匹配算法,综合利用不同算法的优点,在修正动态规划框架下设计了一种新的匹配算法.新算法结合了多边形局部和全局的几何本质特性,其匹配结果不受图形平移、缩放和旋转等形变的影响.分别利用4种算法对52幅平面多边形图形样本进行了试验,按照算法匹配结果和人为判断结果的一致性进行评分.统计分析结果显示,在不同规模的图形组实验中,新算法较前3种算法均表现出明显的优越性.

After analyzing the characteristics of three typical vertex matching approaches for planar polygonal shapes, i. e. , deformation minimization based matching approach, contour tangential variation based approach, and boundary segmentation based approach, a novel polygonal shape matching algorithm was developed based on an improved dynamic programming framework. The proposed algorithm considers both the local and the global geometrical properties of the shapes, and the matching result is invariant to the geometric transformation including translation, scaling, and rotation. Fifty-two sample shapes were tested using the four algorithms, and users scored all the matching results. Statistic data showed that the proposed algorithm performed much better than the other three algorithms.