An error-tolerant approximate matching algorithm for labeled combinatorial maps

作者：Wang Tao^*; Yang Hua; Lang Congyan; Feng Songhe

来源：Neurocomputing, 2015, 156: 211-220.

DOI：10.1016/j.neucom.2014.12.058

• Combinatorial map
• Similarity measure
• Pattern recognition
• Graph

Combinatorial maps are widely used in image representation and processing, and measuring distance or similarity between combinatorial maps is therefore an important issue in this field. The existed distance measures between combinatorial maps based on the largest common submap and the edit distance have high computational complexity, and are hard to be applied in real applications. This paper addresses the problem of inexact matching between labeled combinatorial maps, and aims to find a rapid algorithm for measuring distance between maps. We first define joint-tree of combinatorial maps and prove that it can be used to decide of isomorphism between combinatorial maps. Subsequently, a distance measure based on joint-trees and an approximate approach are proposed to compute the distance between combinatorial maps. Experimental results show that the proposed approach performs better in practice than the previous approach based on approximate map edit distance.

• 出版日期2015-5-25
• 单位中国人民解放军信息工程大学; 北京交通大学; 开封大学