Journal of Frontiers of Computer Science and Technology ›› 2015, Vol. 9 ›› Issue (11): 1382-1390.DOI: 10.3778/j.issn.1673-9418.1506039

Previous Articles     Next Articles

Line Grouping Matching Algorithm Based on Geometric Characteristics

LI Gang+   

  1. College of Mathematics and Computational Science, Yichun University, Yichun, Jiangxi 336000, China
  • Online:2015-11-01 Published:2015-11-03

几何特性的直线编组匹配算法

李  钢+   

  1. 宜春学院 数学与计算机科学学院, 江西 宜春 336000

Abstract: To reduce the huge computation and low efficiency of the traditional line grouping matching (LGM) algorithm, this paper proposes a new LGM algorithm based on geometric characteristics. Firstly, the proposed algorithm defines two kinds of binary relations for the line segment pair, undirected binary relation and directed binary relation. Secondly, the coarse matching procedure calculates the undirected dissimilarities, and generates a candidate line segment group (LSG) set by using two thresholds. Thirdly, the precise matching procedure calculates the directed dissimilarity for every LSG. Finally, the matching results are generated by utilizing the two kinds of dissimilarities. Compared with the line feature matching technique based on eigenvectors and the line matching based on geometric characteristics? binary relations (GCBR), on the one hand, the coarse matching procedure with designing two thresholds has less time consuming than designing only one threshold, on the other hand, the precise matching procedure can filter out the unreasonable candidate LSGs and get the optimized results. The experimental results show that the proposed algorithm is feasible and efficient, moreover has better effect.

Key words: line matching, geometric characteristics, line grouping, binary relation, line segment pair

摘要: 针对传统直线编组匹配算法中存在的数据计算量大,效率低等问题,提出了一种新的基于几何特性的直线编组匹配算法。该算法在定义线段对无向二元关系和有向二元关系的基础上,在粗匹配阶段计算所有线段对的无向不相似度,并采用双阈值生成候选线段组集合,再在精匹配阶段计算各个候选线段组的有向不相似度,最后结合两种不相似度生成最终的匹配线段组结果。与基于向量的特征直线匹配算法和基于几何特征二元关系的直线匹配算法相比,该算法在粗匹配阶段采用了双阈值设计,比只采用单阈值方法耗时更少,在精匹配阶段能有效地过滤掉不合理的候选线段组,得到最佳匹配结果。实验结果表明,所提算法不仅可行、高效,且效果更好。

关键词: 直线匹配, 几何特性, 直线编组, 二元关系, 线段对