An error-tolerant approximate matching algorithm for labeled combinatorial maps

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.