On the complexity of submap isomorphism and maximum common submap problems. Issue 2 (February 2015)

• Record Type: Journal Article
• Authors: Solnon, Christine; Damiand, Guillaume; de la Higuera, Colin; Janodet, Jean-Christophe
• Is Part Of: Pattern recognition. Volume 48:Issue 2(2015:Feb.)
• Page Start: 302
• Page End: 316
• Publication Date: 2015-02
• Subjects: Pattern perception -- Periodicals; Perception des structures -- Périodiques; Patroonherkenning; 006.4
• DOI: 10.1016/j.patcog.2014.05.019
• Languages: English
• ISSNs: 0031-3203

Abstract

<abstract abstract-type="author" id="ab0005"> <title id="sect0005">Abstract</title> <sec> <p id="sp0080">Generalized maps describe the subdivision of objects in cells and are widely used to model 2D and 3D images. In this context, several pattern recognition tasks involve solving submap isomorphism problems (to decide if a map is included in another map) or, more generally, computing maximum common submaps (to measure the distance between two maps). Recently, we have described a polynomial-time algorithm for solving the submap isomorphism problem when the pattern map is connected. In this paper, we show that submap isomorphism is <inline-formula><alternatives><inline-graphic xlink:href="ark:/27927/pgh2pjdfk9m" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math altimg="si0043.gif" overflow="scroll" id="d13e1323" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi mathvariant="script">NP</mml:mi><mml:mi mathvariant="normal">-complete</mml:mi></mml:math></alternatives></inline-formula> when the pattern map is not connected. Then, we characterize the inherent difficulty of submap isomorphism with respect to the number of connected components. We show that it is Fixed-Parameter Tractable (FPT) and we give an FPT algorithm for submap isomorphism. We experimentally compare this algorithm with a state-of-the-art subgraph isomorphism algorithm for searching for patterns in an image and we show that it is both more accurate and more efficient. Finally, we study the complexity of the maximum common submap problem, and we show that it is <inline-formula><alternatives><inline-graphic xlink:href="ark:/27927/pgh2pjdg3r1" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math altimg="si0044.gif" overflow="scroll" id="d13e1329" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi mathvariant="script">NP</mml:mi><mml:mi mathvariant="normal">-hard</mml:mi></mml:math></alternatives></inline-formula> even though we restrict the problem to the search of common connected submaps.</p> </sec> </abstract>