Guillaume Damiand
email: guillaume.damiand@liris.cnrs.fr

Christine Solnon
email: christine.solnon@liris.cnrs.fr

Colin De La Higuera

Jean-Christophe Janodet
email: janodet@univ-st-etienne.fr

Émilie Samuel
email: emilie.samuel@univ-st-etienne.fr

Polynomial Algorithms for Subisomorphism of nD Open Combinatorial Maps

Keywords: open combinatorial maps, isomorphism and subisomorphism, pattern detection, 2D and 3D images

Combinatorial maps describe the subdivision of objects in cells, and incidence and adjacency relations between cells, and they are widely used to model 2D and 3D images. However, there is no algorithm for comparing combinatorial maps, which is an important issue for image processing and analysis. In this paper, we address two basic comparison problems, i.e., map isomorphism, which involves deciding if two maps are equivalent, and submap isomorphism, which involves deciding if a copy of a pattern map may be found in a target map. We formally define these two problems for nD open combinatorial maps, we give polynomial time algorithms for solving them, and we illustrate their interest and feasibility for searching patterns in 2D and 3D images, as any child would aim to do when he searches Wally in Martin Handford's books.

Introduction

Graphs are used in many computer graphic applications to describe images (see, for example, [START_REF] Conte | Applied Graph Theory in Computer Vision and Pattern Recognition, chapter How and Why Pattern Recognition and Computer Vision Applications Use Graphs[END_REF] for a review of graph-based methods for pattern recognition and computer vision). In particular, Region Adjacency Graphs (RAGs) [START_REF] Rosenfeld | Adjacency in digital pictures[END_REF] model images by means of vertices -corresponding to maximal homogeneous sets of connected pixels-and edges -corresponding to adjacency relationships. RAGs are used in many image processing applications like, for example, segmentation, object extraction or comparison, and image analysis [SC84, JB93, Saa94, GMBM95, LMV01].

However, RAGs cannot model some important information contained in images. In particular, they cannot model the order in which neighbor regions are encountered when turning around some given region, as the edges incident to a vertex are not ordered. Also, RAGs cannot represent multi-adjacency. Hence, two different images may be represented by the same RAG [START_REF] Kovalevsky | Finite topology as applied to image analysis[END_REF].

To get round this default, the RAG model has been extended. For example, [START_REF] Kropatsch | Finding the structure of connected components using dual irregular pyramids[END_REF] defines the dual graph structure, which is a pair of multi-graphs that represent multi-adjacency relations, and [START_REF] Jiang | Marked subgraph isomorphism of ordered graphs[END_REF] defines ordered graphs, such that edges incident to a vertex are uniquely ordered.

Several works have proposed some solutions in 2D [START_REF] Domenger | Conception et implémentation du noyau graphique d'un environnement 2D1/2 d'édition d'images discrètes[END_REF][START_REF] Fiorio | A topologically consistent representation for image analysis: the frontiers topological graph[END_REF][START_REF] Brun | Segmentation d'images couleur à base Topologique[END_REF][START_REF] Damiand | Topological model for two-dimensional image representation: definition and optimal extraction algorithm[END_REF] and in 3D [START_REF] Braquelaire | A topological structuring for aggregates of 3d discrete objects[END_REF][START_REF] Damiand | Topological model for 3d image representation: Definition and incremental extraction algorithm[END_REF] based on combinatorial maps. Indeed, combinatorial maps [START_REF] Lienhardt | Topological models for boundary representation: a comparison with n-dimensional generalized maps[END_REF] have many advantages: they are defined in any dimension; they are based on a single element called dart; they describe the subdivision of objects in cells, and incidence and adjacency relations between cells; thus they describe the topology of objects. Actually, many works have used combinatorial maps in 2D and 3D image processing algorithms [BDB97, BDD01, DR02, DD08]. However, there is no algorithm for comparing combinatorial maps, which is an important issue for image processing and image analysis.

Contribution and outline of the paper

In this paper, we address two comparison problems, i.e., map isomorphism, which involves deciding if two maps are equivalent, and submap isomorphism, which involves deciding if a copy of a pattern map may be found in a target map. We formally define these two problems for nD open combinatorial maps. Then we develop polynomial time algorithms for solving them, and illustrate their efficiency for searching patterns in 2D and 3D images.

Part of this work was published in [DDLHJ + 09]. Nevertheless, our previous results were limited to 2D; moreover, the material presented in Sections 4 and 5 is totally new.

In Section 2, we recall basic definitions and notations for nD combinatorial maps [START_REF] Lienhardt | Topological models for boundary representation: a comparison with n-dimensional generalized maps[END_REF], and from open combinatorial maps [START_REF] Poudret | Cartes combinatoires ouvertes[END_REF] thus the paper is self-contained. We use open maps to represent objects with boundaries, that allow us to model images that have blurred or that contain undefined regions.

In Section 3, we first extend the definition of map isomorphism of [START_REF] Lienhardt | N-dimensional generalized combinatorial maps and cellular quasi-manifolds[END_REF] to open combinatorial maps and give a polynomial time algorithm for solving this problem. This algorithm is close to that of [START_REF] Cori | Un code pour les graphes planaires et ses applications[END_REF], but we extend it to nD open maps. Then we tackle the submap isomorphism problem and again, we develop a polynomial time algorithm for nD open maps. We prove the correctness and study the complexity of both algorithms. Note that from a graph-theoretical perspective, these results imply that the subisomorphism problem for plane graphs (that is, planar graphs that are embedded in a plane) is solvable in polynomial time, whereas this problem is known intractable for general graphs. However, our algorithms are restricted to patterns which are connected maps, such that there exists a path of sewn darts between every pair of darts.

In Section 4, we introduce planar maps, that are 2D maps embedded in a plane. The goal is to design a model that is close to standard pictures: images are usually drawn on the plane, thus one region, called the external or infinite region, is distinguished and should play a particular role. Comparing planar maps ultimately returns to the problem of comparing 2D maps and then checking whether the external regions are matched or not. Therefore, we essentially use the algorithms developed in Section 3, adding new constraints. However, the knowledge of external regions allows us to optimize the efficiency of these algorithms in practice (although the worst-case complexity does not change).

Finally, in Section 5, we describe a large experimental study that proves the efficiency of our procedures in practice. We first show how to use submap isomorphism for searching for a 2D subimage into a database of 2D images. Then we tackle the searching of a 3D submesh into a database of 3D objects. These results show the interest of having generic definitions and algorithms based on nD open maps. Indeed, we use the same method and algorithm in different types of applications, with different dimensions, the corresponding maps being open or closed.

We conclude the paper on some related works and perspectives in Section 6.

Combinatorial Maps

An nD cellular complex is the subdivision of an nD object into cells of dimensions at most n (0D corresponding to vertices, 1D to edges, 2D to faces, 3D to volumes, etc), plus incidence and adjacency relationships between cells. Cellular complexes can be modeled with combinatorial maps, which provide a generic definition based on a single basic element called dart. In Section 2.1, we recall some definitions on combinatorial maps, and in Section 2.2, we give the definition of open combinatorial maps and related notions that we use to model cellular complexes with boundaries.

Recalls on combinatorial maps

Combinatorial maps were originally defined for 2D [START_REF] Edmonds | A combinatorial representation for polyhedral surfaces[END_REF][START_REF] Tutte | A census of planar maps[END_REF][START_REF] Cori | Un code pour les graphes planaires et ses applications[END_REF], then extended to 3D [AK89, Spe91] and finally to nD [START_REF] Lienhardt | Topological models for boundary representation: a comparison with n-dimensional generalized maps[END_REF]. Below, we briefly recall the main definitions. Definition 1 (Combinatorial map). An nD combinatorial map, (or n-map) is a tuple M = (D, β 1 , . . . , β n ) where

1. D is a finite set of darts; 2. β 1 is a permutation 1 on D; 3. ∀i : 2 ≤ i ≤ n, β i is an involution 2 on D with no fixed point 3 ; 4. ∀i : 1 ≤ i ≤ n -2, ∀j : i + 2 ≤ j ≤ n, β i • β j is an involution on D.
We note β 0 for β -1 1 , and β ij for β j • β i . Two darts d and d ′ such that d = β i (d ′ ) are said to be i-sewn. Let f be a function defined on a set E, and

X ⊆ E, we denote f (X) = {f (x)|x ∈ X}.
Examples of 2D and 3D combinatorial maps are provided in Figures 1 and2. Intuitively, β i defines adjacency relationships between cells of dimension i (e.g., edges for β 1 , faces for β 2 , volumes for β 3 ). β 1 is a permutation (so that β 1 (d) may be different from β -1 1 (d)) whereas all other β i are involutions. Indeed, in 2D, a face is adjacent to at most one other face whereas an edge may be adjacent to two edges of the same face: β 1 (d) is the dart that follows d whereas β -1 1 (d) = β 0 (d) is the dart that precedes d. Note that β 1 may contain fixed points: in 2D, they correspond to loops, i.e. faces that are bordered by a single dart.

In combinatorial maps, cells are defined by means of orbits. Given a set E, a set {p 1 , . . . , p j } of permutations on E and an element e ∈ E, the orbit p 1 , . . . , p j (e) is the set of all elements of E that can be reached from e by composing any p 1 , . . . , p j and their inverses p -1 1 , . . . , p -1 j . The link between cells and orbits is given in Def. 2.

Definition 2 (i-cell). Let M be an n-map, and d a dart.

• The 0-cell incident to d is β 02 , . . . , β 0n (d);

• ∀i : 1 ≤ i ≤ n, the i-cell incident to d is β 1 , . . . , β i-1 , β i+1 , . . . , β n (d).
Hence, a cell is a set of darts.

• A 0-cell corresponds to a vertex and is a set of darts that share a same origin. In 2D, a 0-cell is obtained by the orbit β 02 (e.g., β 02 (8) = {1, 8, 12} in Fig. 1). In 3D, it is obtained by the orbit β 02 , β 03 (e.g., β 02 , β 03 (3) = {3, 6, 10, 11, 12, 13, 14, 15, 16} in Fig. 2);

(a) The corresponding 3D combinatorial map (external volume on the left; interior on the middle and the right). The graphical convention is the same as in 2D. β 3 is not drawn, but (partially) given in the array.

• A 1-cell corresponds to an edge and is a set of darts that share their endpoints. In 2D, it is obtained by the orbit β 2 (e.g., β 2 (8) = {7, 8} in Fig. 1). In 3D, it is obtained by the orbit β 2 , β 3 (e.g., β 2 , β 3 (2) = {2, 6, 9, 10} in Fig. 2);

• A 2-cell corresponds to a face. In 2D, it is obtained by the orbit β 1 (e.g., β 1 (8) = {8, 9, 10, 11} in Fig. 1). In 3D, it is obtained by the orbit β 1 , β 3 (e.g., β 1 , β 3 (1) = {1, 2, 3, 4, 5, 6, 7, 8} in Fig. 2);

• A 3-cell corresponds to a volume and is obtained in 3D by the orbit β 1 , β 2 (e.g., β 1 , β 2 (5) contains the 24 darts of the internal cube in Fig. 2).

We can define the incidence and adjacency relations between cells:

• Two cells are incident if their intersection is not empty. E.g., edge β 2 (7) = {7, 8} is incident to face β 1 (8) = {8, 9, 10, 11} in Fig. 1.

• Two i-cells are adjacent if there is an (i-1)-cell incident to both i-cells. E.g., faces β 1 (8) and β 1 (15) are adjacent because they are both incident to edge β 2 (11) in Fig. 1.

Open combinatorial maps

In [START_REF] Lienhardt | Topological models for boundary representation: a comparison with n-dimensional generalized maps[END_REF], Lienhardt has defined generalized maps, which can be used to model open or closed objects, thus allowing one to model objects with boundaries. A preliminary report [START_REF] Poudret | Cartes combinatoires ouvertes[END_REF] extended the definition of nD combinatorial maps to open nD combinatorial maps.

Open maps may contain free darts, i.e., darts that are not linked with other darts for some dimensions. In generalized maps [START_REF] Lienhardt | Topological models for boundary representation: a comparison with n-dimensional generalized maps[END_REF], a dart is i-free whenever it is i-sewn with itself (i.e., β i (d) = d). However, in combinatorial maps, β 1 may contain fixed points (in case of loops), thus such a trick is impossible to re-use. Therefore, to denote that a dart is 1-free, a new element ∅ is considered in addition to the set of darts, and darts can be 1-sewn with ∅. To make things similar in every dimensions, we use the same principle for i-free darts, with i > 1. Thus, a dart d is i-free, for i ∈ {0, . . . , n}, if

β i (d) = ∅.
However, if some darts are i-sewn with ∅, then β i is no longer a permutation or an involution on D, but a partial permutation or partial involution such that only a subset X ⊆ D of darts is linked to another subset of darts of D whereas other darts are i-free. We formally define a partial permutation as well as its inverse as follows.

Definition 3 (Partial permutation). Let E be a finite set. A mapping p : E ∪ {∅} → E ∪ {∅} is a partial permutation defined on E if: Figure 3: Open combinatorial map example. Darts 3 and 5 are 1-free, and darts 1, 7, 8 and 9 are 2-free.

1. p(∅) = ∅; 2. ∀e 1 ∈ E, ∀e 2 ∈ E, p(e 1 ) = p(e 2 ) = ∅ ⇒ e 1 = e 2 .
The inverse p -1 of this partial permutation is also a partial permutation and is defined by:

1. p -1 (∅) = ∅; 2. ∀e ∈ E, if it exists a ∈ E such that p(a) = e, then p -1 (e) = a, otherwise p -1 (e) = ∅.
In other words, a partial permutation of E is a bijection between two subsets F and G of E such that the elements of E that do not belong to F or G are linked to ∅.

A partial involution is a specific partial permutation, satisfying the condition f (f (e)) = e for any element e such that f (e) = ∅.

Definition 4 (Partial involution). A partial involution f on E is a partial permutation on E such that:

∀e ∈ E, f (e) = ∅ ⇒ f (f (e)) = e.
Since a partial involution f is a partial permutation (with an additional property), its inverse is defined in Def. 3, and we have f -1 = f . Moreover, we can verify that, given two partial permutations f and g, f • g is a partial permutation, and (f

• g) -1 = g -1 • f -1 .
We can now define open combinatorial maps.

≤ i ≤ n -2, ∀j : 3 ≤ j ≤ n, i + 2 ≤ j, β ij is a partial involution.
Open n-maps differ from n-maps on three points: (1) β 1 is a partial permutation instead of a permutation; (2) other β i are partial involutions instead of involutions; (3) Condition 4 is modified such that β ij is a partial involution, and this condition must also be satisfied for i = 0. An example of open 2-map is represented in Fig. 3.

The first two differences directly come from the fact that we can have free darts. For the third difference, we need to add the condition on β 0j because β 1j is a partial involution does not imply that β 0j is a partial involution (contrary to the original definition of combinatorial maps where β 1j is an involution implies that β 0j is an involution).

A combinatorial map is said to be i-open (resp. i-closed), for i ∈ {1, . . . , n}, if it contains at least one i-free dart (resp. no i-free dart). The map is said to be open (resp. closed) if it is i-open for at least one i ∈ {1, . . . , n} (resp. i-closed for all i ∈ {1, . . . , n}). When nothing is specified, a combinatorial map may be either open or closed, and thus it is defined with respect to Def. 5.

From a mathematical standpoint, any combinatorial map denotes an nD cellular quasi-manifold [START_REF] Lienhardt | N-dimensional generalized combinatorial maps and cellular quasi-manifolds[END_REF]. As every combinatorial map can easily be converted into a generalized map, this semantics still holds for our definition of open combinatorial map. Now let us tackle the definition of cells. The definition of orbits given in Section 2.1 is still valid for open combinatorial maps, since it uses "the set of all elements of E that can be reached. . . ", which avoid to have ∅ in any orbit (since ∅ / ∈ E by partial permutation definition). For this reason, the Def. 2 of i-cells given for closed maps, is still valid for i > 1.

For instance, in the 2-map displayed in Fig. 3, the edge incident to dart 1 is β 2 (1) = {1} (since dart 1 is 2-free) while the edge incident to dart 11 is β 2 (11) = {11, 12}. The face incident to dart 2 is β 1 (2) = {2, 3}.

However, we need to modify the definition of vertices (0-cells in Def. 6).

Definition 6 (0-cell). Let M = (D, β 1 , . . . , β n ) be an n-map, and d ∈ D. The 0-cell incident to d is the set β 02 , . . . , β 0n ,

{β ij |∀i, j : 2 ≤ i < j ≤ n} (b).
The difference with the previous definition of 0-cells is that we need to add β ij for all 2 ≤ i < j ≤ n in order not to miss some darts that cannot be reached due to some free darts. Let us consider, for example, the 0-cell incident to 3 in the closed 3-map of Fig. 2, that is, β 02 , β 03 (3) = {3, 6, 10, 11, 12, 13, 14, 15, 16}. Some darts in this orbit are reached from 3 by composing some permutations, e.g., β 02 (β 03 (3)) = 11. Let us now consider the 3-map obtained by removing darts 2 and 4 (i.e., dart 3 is 0-free and 1-free). In this case, we have to use β 23 and β -1 23 to reach other darts of the vertex incident to dart 3 (e.g.,

β 23 (3) = 11), since β 02 (3) = β 03 (3) = β 21 (3) = β 31 (3) = ∅.
In the example of the 2-map displayed in Fig. 3, the vertex incident to dart 12 is β 02 (12) = {8, 12}.

Map and Submap Isomorphism

(Sub)map isomorphism allows one to compare maps. In Section 3.1, we define map isomorphism -which allows one to decide the equivalence of two maps-and give a polynomial time algorithm for solving this problem. In Section 3.2, we consider submap isomorphism -which allows one to decide of the inclusion of a pattern map into a target map-and propose a polynomial time algorithm for solving this problem too.

In this paper, we only consider patterns which are connected maps, i.e. there exists a path of sewn darts between every pair of darts. Formally:

Definition 7 (Path). Let M = (D, β 1 , . . . , β n ) be a combinatorial map. A sequence of darts (d 1 , . . . , d k ) is a path between d 1 and d k if ∀i : 1 ≤ i < k, ∃j i ∈ {0, 1, . . . , n}, d i+1 = β ji (d i ). Definition 8 (Connected map). A combinatorial map M = (D, β 1 , . . . , β n ) is connected if ∀d ∈ D, ∀d ′ ∈ D,
there exists a path between d and d ′ .

Map isomorphism

Lienhardt [START_REF] Lienhardt | N-dimensional generalized combinatorial maps and cellular quasi-manifolds[END_REF] has defined isomorphism between two closed combinatorial maps. We extend this definition to open combinatorial maps as follows.

Definition 9 (Map isomorphism). Two n-maps M = (D, β 1 , . . . , β n ) and M ′ = (D ′ , β ′ 1 , . . . , β ′ n ) are isomorphic if there exists a bijection f : D ∪ {∅} → D ′ ∪ {∅}, called isomorphism function, such that f (∅) = ∅ and ∀d ∈ D, ∀i : 1 ≤ i ≤ n, f (β i (d)) = β ′ i (f (d))
. The only difference with the definition of isomorphism between closed n-maps is that we have added that f (∅) = ∅. Indeed, if a dart is i-sewn with ∅, then the dart matched to it by f must also be i-sewn with ∅.

As already mentioned in [START_REF] Cori | Un code pour les graphes planaires et ses applications[END_REF] for 2D maps, an algorithm for deciding of the isomorphism of two maps can easily be derived from this definition. Indeed, consider Algorithm 1. We first fix a dart d 0 ∈ D and, for every dart d ′ 0 ∈ D ′ , we call Algorithm 2 to build a candidate matching function f and then we check whether f actually is an isomorphism function. Algorithm 2 basically performs a traversal of M , starting from d 0 and using the β i functions to discover new darts from darts that have already been discovered:

initially, f [d 0 ] is set to d ′ 0 whereas f [d] is set to nil for all other darts, thus stating that d has not yet been discovered; then, each time a dart d ∈ D is discovered, from another dart d k ∈ D such that d is i-sewn with d k , then f [d] is set to the dart d ′ ∈ D ′ which is i-sewn with f [d k ]. Algorithm 1: checkIsomorphism(M, M ′ ) Input: a connected n-map M = (D, β 1 , . . . , β n ), and an n-map M ′ = (D ′ , β ′ 1 , . . . , β ′ n ) Output: returns true iff M and M ′ are isomorphic choose d 0 ∈ D 1 foreach d ′ 0 ∈ D ′ do 2 f ← traverseAndBuildMatching(M, M ′ , d 0 , d ′ 0 ) 3 if f is an isomorphism function then 4 return True 5 return False 6 Algorithm 2: traverseAndBuildMatching(M, M ′ , d 0 , d ′ 0 ) Input: a connected n-map M = (D, β 1 , . . . , β n ), an n-map M ′ = (D ′ , β ′ 1 , . . . , β ′ n ) and an initial couple of darts (d 0 , d ′ 0 ) ∈ D × D ′ Output: returns an array f : D ∪ {∅} → D ′ ∪ {∅} foreach d ∈ D do f [d] ← nil 1 f [d 0 ] ← d ′ 0 2 let S be an empty stack; push d 0 in S 3 while S is not empty do 4 pop a dart d from S 5 foreach i ∈ {0, . . . , n} do 6 if d is not i-free and f [β i (d)] = nil then 7 f [β i (d)] ← β ′ i (f [d]) 8 push β i (d) in S 9 f [∅] ← ∅ 10 return f 11
We get the following result:

Theorem 1. A connected n-map M is isomorphic to a map M ′ iff checkIsomorphism(M, M ′ ) returns true.
Proof. This corresponds to proving that Algorithm 1 is correct.

β ′ i (f [d]) in line 8 and (2) f [d] = ϕ(d) (by induction hypothesis) and (3) ϕ(d) = d ′ ⇒ ϕ(β i (d)) = β ′ i (d ′ ) (

by definition of an isomorphism function).

• Claim 2: Every dart d ∈ D is pushed once in S. Indeed, M is connected, so that there exists at least one path of sewn darts (d 0 , .

(n • |D| • |D ′ |).
Note that Algorithm 1 may be optimized, without changing its worst-case complexity. In particular, we can detect failure while building matchings by checking between lines 7 and 8 of Algorithm 2 that there does not exist a dart d j ∈ D that has already been matched to

β ′ i (f [d]
): if this is the case, one can stop the current traversal as f will not be a bijection.

The condition that M is a connected map is necessary to ensure that all darts of M are discovered during the traversal, whatever the initial dart d 0 is. This condition is not necessary for the second map M ′ since the traversal is only guided by M (but of course if M is connected while M ′ not, Algorithm 1 return false).

Submap isomorphism

We now tackle the problem of submap isomorphism, the goal of which is to decide if there exists a copy of a pattern map in a target map.

Basically, a submap is obtained from a map by keeping only a subset X of its darts, and updating β i functions so that every dart of X that is i-sewn with a dart that does not belong to X becomes i-free.

Definition 10 (Submap). Given a combinatorial map M = (D, β 1 , . . . , β n ) and a subset of darts X ⊆ D, the submap of M induced by X, denoted M ↓X is the combinatorial map (X, γ 1 , . . . , γ n ) such that: ∀d ∈ X, ∀i :

1 ≤ i ≤ n, if β i (d) / ∈ X then γ i (d) = ∅; else γ i (d) = β i (d).
Note that, depending on X, the submap M ↓X may not satisfy condition 4 of Def. 5 so that it may not be a combinatorial map. Hence, we shall verify, when using Def. 10, that the subset X is such that M ↓X satisfies this condition.

For example, if we consider the map shown in Fig. 2, and X = D \ {1}. In this case, M ↓X is not a combinatorial map since the condition that β 1 • β 3 must be an involution is not satisfied for dart 5 (we have

β 1 • β 3 (5) = 4 and β 1 • β 3 (5) = ∅).
We can now define submap isomorphism as follows.

Definition 11 (Submap isomorphism).

Let M = (D, β 1 , . . . , β n ) and M ′ = (D ′ , β ′ 1 , . . . , β ′ n ) be two n- maps. M is isomorphic to a submap of M ′ if there exists a subset of darts X ⊆ D ′ such that M ′ ↓X is isomorphic to M .
The subset X obviously satisfies condition 4 of Def. 5 since M is a valid combinatorial map, and

M ′ ↓X is isomorphic to M .
The existency of a submap isomorphism implies the existency of a subisomorphism function which matches every dart of the pattern map to a different dart of the target map, so that pattern darts that are i-sewn are matched to target darts that are also i-sewn, like an isomorphism function. However, when a pattern dart d is i-free the target dart matched to d must either be i-free, or it must be i-sewn with a target dart which is not matched to another pattern dart (see example in Fig. 4). This is more formally stated in Theorem 2. M is a submap of M ′ as it is obtained from M ′ by deleting darts k to r. M ′′ is not isomorphic to a submap of M ′ as the injection f : X → D that respectively matches darts 1 to 10 to darts a to j does not verify Theorem 2: for example, dart 4 is 2-free and it is matched to dart d which is 2-sewn with a dart (b) which is itself

matched (i.e., f -1 (b) = 2).
Theorem 2. M is isomorphic to a submap of M ′ iff there exists an injection f : D ∪ {∅} → D ′ ∪ {∅}, called a subisomorphism function, such that:

1. f (∅) = ∅ and 2. ∀d ∈ D, ∀i : 1 ≤ i ≤ n, • if d is not i-free, then β ′ i (f (d)) = f (β i (d)); • otherwise, either f (d) is i-free, or ∀d k ∈ D, f (d k ) = β ′ i (f (d))).
Proof. (⇒) If M is isomorphic to a submap of M ′ , then there exists a subset X ⊆ D ′ such that M is isomorphic to M ′ ↓X . By Def. 9, there exists a bijection f :

D ∪ {∅} → X ∪ {∅} such that f (∅) = ∅ and ∀d ∈ D, ∀i : 1 ≤ i ≤ n, f (β i (d)) = β ′ i (f (d)). Let us define function g : D ∪ {∅} → D ′ ∪ {∅} such that ∀d ∈ D, g(d) = f (d) and g(∅) = ∅, and let us show that g is a subisomorphism function. Obviously, ∀i : 1 ≤ i ≤ n, if d is not i-free, then β ′ i (g(d)) = g(β i (d)). The key point is to show that if d is i-free, then either g(d) is i-free or ∀d k ∈ D, f (d k ) = β ′ i (f (d))
). Let us suppose that g(d) is not i-free and there exists

d k ∈ D such that g(d k ) = β ′ i (g(d)
). As f is an isomorphism function and g is the restriction of f to X, we have g(

d k ) = β ′ i (g(d)) = g(β i (d)) so that d k = β i (d)
which is in contradiction with the fact that d is i-free. (⇐) Let us suppose that there exists a subisomorphism function f : D ∪ {∅} → D ′ ∪ {∅}. We must show that M is isomorphic to a submap of M ′ , i.e., that there exists a subset X ⊆ D such that M is isomorphic to M ′ ↓X . Obviously, we define X = {f (d)|d ∈ D} and function g : D → X such that g(∅) = ∅ and ∀d ∈ D, g(d) = f (d).

✷ Algorithm 3 determines if there is a submap isomorphism between a connected map and a map. It is based on the same principle as Algorithm 1; the only difference is the test of line 4, which succeeds if f is a subisomorphism function instead of an isomorphism function. Correctness proofs and evidences given for isomorphism are still valid: we solve the submap isomorphism problem with the same method as before, except that function f is now an injection instead of a bijection. Also, one may optimize Algorithm 3 in a similar way as proposed for Algorithm 1, without changing its worst-case complexity, by checking between lines 7 and 8 of Algorithm 2 that there does not exist a dart d j ∈ D that has already been matched to

Algorithm 3: checkSubIsomorphism(M, M ′ ) Input: a connected map M = (D, β 1 , . . . , β n ), and a map M ′ = (D ′ , β ′ 1 , . . . , β ′ n ) Output: returns true iff M is isomorphic to a submap of M ′ choose d 0 ∈ D 1 foreach d ′ 0 ∈ D ′ do 2 f ← traverseAndBuildMatching(M, M ′ , d 0 , d ′ 0 ) 3 if f is a subisomorphism function then
β ′ i (f [d]
): if this is the case, one can stop the current traversal as f will not be an injection.

Constrained Isomorphisms

In 2D image processing, the type of maps one wishes to consider have the property that they are to be drawn on the plane, not on the sphere. We call this type of map a planar combinatorial map. To understand this point, let us consider the typical situation represented in Fig. 5. These two maps are isomorphic on the sphere, which corresponds to the definitions introduced in Section 3.1, but are not isomorphic in the plane. In other words, for these two maps, Algorithm 3 returns true, but that is probably not what is intended in an image processing task.

The property of being planar isomorphic is a geometrical property, i.e. it cannot be characterized for maps without geometry. Indeed, two maps are planar isomorphic when they are isomorphic and when the image of the exterior of the first map is equal to the exterior of the second map.

Let us consider, for example, the two maps displayed in Fig. 6(b) and Fig. 6(c). These maps are isomorphic but not planar isomorphic. Indeed, the image of the exterior darts of the map in Fig. 6(b) are not exterior darts in Fig. 6(c). This means that we have reversed the first map which is not a possible operation in the plane. This is similar for planar submap isomorphism. In our example, the map of Fig. 6(a) is a submap of the two maps of Fig. 6(b) and Fig. 6(c), but it is only a planar submap of the map of Fig. 6(b) since only in this case, the image of the exterior darts of Fig. 6(a) are still at the exterior of the second map.

In Section 4.1, we formally define planar maps by introducing the notion of exterior and infinite darts of a map. In Section 4.2, we extend (sub)map isomorphism to planar (sub)map isomorphism by adding constraints on exterior and infinite darts. In Section 4.3, we show how to compute exterior and infinite darts in the case of 1-closed combinatorial maps (i.e. when all faces are closed).

Planar maps

When considering a map drawn on the plane, a part of the plane corresponds to the exterior of the modeled object. There are 3 cases to consider:

• If there exists an infinite (or unbounded) face, and if this infinite face is closed, then the exterior is defined by the darts of this infinite face, as displayed in Fig. 7(a).

• If there exists an infinite face, but this face is open, then the exterior is defined by the darts of this open infinite face, plus the set of 2-free darts that border the exterior, as displayed in Fig. 7(b);

• If there does not exist an infinite face, then the exterior is defined by the set of 2-free darts that border the exterior, as displayed in Fig. 7(c).

Hence, a planar map is defined by a map, together with a set Ext of exterior darts, and a set Inf ⊆ Ext of darts that belong to the infinite face (called infinite darts).

The last consideration to take into account is face orientation. Indeed, there are two possible orientations of each planar combinatorial map: by taking β 1 such that faces are oriented clockwise (like Fig. 8(b)) or counterclockwise (like Fig. 8(a)). Note that all the faces of a map have the same orientation, except the infinite face which has a reversed orientation. This orientation is once again a geometrical property, and it is required to use the same orientation for all the considered planar maps. Thus, in this section, we suppose that the same orientation is chosen for all the planar maps.

Definition 12 (Planar map). A planar map is a triple P M = M, Ext, Inf such that (1) M = (D, β 1 , β 2 ) is a combinatorial map drawn on the plane with a given orientation; (2) Ext ⊆ D is the set of exterior darts;

(3) Inf ⊆ Ext is the set of infinite darts.

Note that when we consider a connected map, there is at most one infinite face. This is not the case for non-connected maps that may have several infinite faces (at most one for each connected component).

Planar map isomorphism

When comparing two planar maps in order to decide if they are isomorphic, one has to check that the isomorphism function actually matches exterior and infinite darts, as stated in Def. 13.

Definition 13 (Planar map isomorphism). Two planar maps P M = M, Ext, Inf and P M ′ = M ′ , Ext ′ , Inf ′ are planar isomorphic if there exists an isomorphism function f between M and M ′ such that f (Ext) = Ext ′ and f (Inf ) = Inf ′ . The test on exterior darts is not enough to process all the possible cases. Let us consider for example the maps of Fig. 8(b) and Fig. 8(c). These two maps are isomorphic and have the same set of exterior darts, but they are not planar isomorphic since the first one represents a square face while the second one represents the plane minus a square. The condition on the infinite face allows to distinguish these two cases since Inf = ∅ in the first map, whereas Inf = ∅ in the second map.

The definition of a submap is also extended to planar maps as follows.

Definition 14 (Planar submap). Given a planar map P M = M, Ext, Inf with M = (D, β 1 , β 2 ), and a subset of connected darts X ⊆ D. The planar submap of P M induced by X is the planar map P M ↓X = M ↓X , Ext ′ , Inf ′ such that M ↓X is the submap of M induced by X, Ext ′ is the set of exterior darts of M ↓X and Inf ′ is the set of infinite darts of M ↓X .

The way to compute Ext ′ and Inf ′ depends on how the combinatorial map is linked with some geometrical elements. In particular, we show in Section 4.3 how these sets can be computed when combinatorial maps are 1-closed.

Planar submap isomorphism is now defined in a straightforward way with respect to planar submap and planar map isomorphism.

Definition 15 (Planar submap isomorphism). A planar map P M is planar submap isomorphic to a planar map P M ′ if there exists a planar submap of P M ′ which is planar isomorphic to P M .

The case of 1-closed combinatorial maps

In the field of image processing, faces are either entirely represented or not at all. Technically, this means that β 1 should be a permutation and not a partial permutation. We use this property in this section to simplify handling of exterior and infinite darts, and to show how to compute Ext and Inf sets for the planar submap definition.

If a map is 1-closed, we have only two cases to consider: the infinite face is either present and closed or totally absent. Therefore, we have either Inf = ∅, or Inf = Ext. Thus, we do not have to explicitly list the set of infinite darts Inf , but we can simply use a boolean inf inite which is true if the infinite face is present and false otherwise.

For each of these two cases, the subset Ext may be defined by giving only one dart d ext of the set:

• When the infinite face is defined, given a dart d ext belonging to this face, the whole set of exterior darts corresponds to the orbit β 1 (d ext ). For example, in Fig. 7(a), Ext = β 1 (a) = {a, b, c, d, e}.

• When the infinite face is not defined, the exterior darts correspond to the set of 2-free darts that border the exterior of the map. In this case, given a 2-free dart d ext that borders the exterior of the map, the whole set of exterior darts may be computed by Algorithm 4. For example, in Fig. 7(c), Ext = buildExterior(M, a, f alse) = {a, b, c, d, e}.

Note that in both cases, there may exist 2-free darts that are not exterior darts. These 2-free darts border undefined parts of the map. Let us consider, for example, the map displayed in Fig. 6(a): the set of exterior darts is {d, g}; the other 2-free darts, i.e., {a, b, i, j}, border an undefined part inside the map. Proof. As the map is 1-closed, there are only two possible cases: the infinite face is present and thus Ext = Inf = β 1 (d ext ), or this face is not present and in this case, the exterior darts can all be reached starting from d ext , and keeping all the 2-free darts that border the exterior of the map. For that, given an exterior dart, we go to the next dart of the same face (line 5), then we jump over darts inside the map (i.e. which are not 2-free) by using β 21 (d curr ) as many time as necessary to reach a 2-free dart (lines 6-7). We are sure that such a dart exists because the map is connected and 1-closed. ✷ This algorithm has a linear time complexity with respect to the number of darts.

We can now simplify the notation of planar maps by P M = M, d ext , inf inite since we can retrieve Ext and Inf given d ext and inf inite, for 1-closed maps.

Note that two planar maps may be planar isomorphic only if the two sets of exterior darts have the same cardinality and either both correspond to an infinite face, or both correspond to a set of 2-free darts that border the exterior of the maps. If this is not the case, one can trivially conclude that the two planar maps are not isomorphic; otherwise, one has to search for an isomorphism function that matches Ext and Ext ′ . In this later case, one may use the fact that darts of Ext must be matched to darts of Ext ′ to boost the research, as described in Algorithm 5.

Algorithm 5: checkPlanarIsomorphism(P M, P M ′ )

Input: a planar connected map P M = M, d ext , inf inite , and a planar map Now let us re-consider the planar submap problem. By using the fact that maps are 1-closed, we are now able to compute combinatorially Ext ′ and Inf ′ in the submap definition. First, we need to add a constraint in the submap definition. Indeed, given a planar map P M = (M, Ext, Inf ), the subset of darts X ⊆ D must ensure that the submap P M ↓X is always 1-closed. For this reason, for each face f of the initial map, X must either contain all the darts of f , or no dart of f , but it cannot contain only some darts of f , otherwise some darts are 1-free.

P M ′ = M ′ , d ′ ext , inf inite ′ Output: returns true if and only if the maps are planar-isomorphic if inf inite = inf inite ′ then return false 1 Ext ← buildExterior(M, d ext , inf inite) 2 Ext ′ ← buildExterior(M ′ , d ′ ext , inf inite ′ ) 3 if |Ext| = |Ext ′ | then return false 4 foreach d ′ 0 ∈ Ext ′ do 5 f ← traverseAndBuildMatching(M, M ′ , d ext , d ′ 0 ) 6 if f is an isomorphism
If the submap is 1-closed, then the infinite face is either totally kept in the submap, or totally removed. This allows us to compute simply the new boolean inf inite ′ of the submap. Indeed, if inf inite is false, the initial map M does not have an infinite face, and thus the submap also. Otherwise, we have Ext = Inf and thus d ext ∈ Inf . Now there are again two cases: if d ext ∈ X, then the infinite face is totally selected and thus is present in the submap, otherwise the infinite face is not selected and thus the submap does not have an infinite face.

For d ′

ext , there are also two cases to consider. If d ext ∈ X, then this dart is present in the submap and thus it belongs to the exterior of the submap, so that d ′ ext = d ext . Otherwise, we need to find a new exterior dart of the submap. This can be achieved easily by searching a dart d ∈ X which can be reached from d ext by a path of darts that uses only darts that do not belong to X (except d of course). Indeed, such a dart belongs necessarily to the exterior of the submap induced from X due to the fact that the pattern map is connected. Such a path may be found by a simple traversal of the darts of D starting from d ext and avoiding darts of X. The key point is to ensure that we are always able to compute the dart d ′ ext by using such a path. Suppose it is not the case, then there is no path between d ext and one dart of X and this implies that the map is not connected.

More formally, we define planar submap for 1-closed maps as follows.

Definition 16 (1-closed planar submap). Given a 1-closed connected planar map P M = M, d ext , inf inite with M = (D, β 1 , β 2 ), and a subset of connected darts X ⊆ D. The planar submap of P M induced by X is the planar map P M ↓X = M ↓X , d ext ′ , inf inite ′ such that M ↓X is 1-closed, with:

• inf inite ′ = true if inf inite = true and d ext ∈ X; inf inite ′ = false otherwise; • d ′ ext = d ext if d ext ∈ X; d ′ ext = d ∈ X with a path (d ext , . . . , d) of darts / ∈ X (except d) otherwise.
Algorithm 6: checkPlanarSubIsomorphism(P M, P M ′ ) Input: a connected planar map P M = M, d ext , inf , and a planar map Algorithm 6 shows how to decide if a planar map is isomorphic to a submap of another planar map. The basic idea is to compute subisomorphism functions and check if they satisfy the additional planarity constraint. We may have to compute several subisomorphism functions since it is possible that there are different subisomorphisms, and that some of them are planar while others are not.

P M ′ = M ′ , d ′ ext , inf ′ Output: returns true iff P M is planar isomorphic to a submap of P M ′ foreach dart d ′ 0 of M ′ do 1 f ← traverseAndBuildMatching(M, M ′ , d ext , d ′ 0 ) 2 if f is a subisomorphism
Theorem 5. checkPlanarSubIsomorphism(P M, P M ′ ) returns true iff P M is planar isomorphic to a submap of P M ′ .

Proof. First, if P M is planar isomorphic to a submap of P M ′ , as we compute all the subisomorphism functions between M and M ′ , we are sure to find the one satisfying planarity constraints and thus the algorithm returns true. Second, if our algorithm returns true, there is a subisomorphism satisfying the planarity constraints and thus P M is planar isomorphic to a submap of P M ′ . ✷

The complexity of the planar subisomorphism algorithm is O(|D|

Experiments

In this section, we carry out two experiments that show the effectiveness of our algorithm to detect patterns in images. The first challenge consists in searching for a sub-image from a database of 2D segmented images -a typical "Where's Wally" challenge. The second one aims at retrieving a sub-mesh from a database of 3D objects. These experiments illustrate the interest of generic algorithms for submap isomorphism. Indeed, the same procedure is used whatever the dimension of the maps used to model objects (2D, 3D or more).

Description of the two databases

We have considered two different databases, the characteristics of which are summarized in table 9. The 2D database has been generated from 224 segmented images4 . For each of these 224 segmented images, we have computed a 2D-map, thus obtaining 224 target 2D-maps. We have used the algorithm of [START_REF] Damiand | Topological model for two-dimensional image representation: definition and optimal extraction algorithm[END_REF] to build 2D-maps from segmented images. The basic idea of this algorithm is to build the map in an incremental way: each pixel is considered iteratively and, for each pixel, a square face is created and sewn to the combinatorial map. Then, this square face is merged with faces which are adjacent to it and which belong to the same region as it. Finally, consecutive edges separating the same two regions are merged so that two adjacent regions are separated by exactly one edge (see [START_REF] Damiand | Topological model for two-dimensional image representation: definition and optimal extraction algorithm[END_REF] for more details). From each segmented image, we have randomly extracted a sub-image, thus obtaining 224 pattern maps. Figures 10 and 11 display five segmented images and the subimages which have been extracted from them. The 3D database has been generated from 800 objects5 represented in 3D, thus defining 800 target 3D-maps. From these 800 3D-maps, we have randomly extracted 62 pattern 3D-maps. Figures 12 and13 display four 3D objects and the sub-meshes which have been extracted from them.

Since the patterns we are searching for must be connected by definition, we have only considered connected pattern submaps for the 2D and 3D databases.

Submap vs subgraph isomorphism

We compare our submap algorithm with algorithms for solving subgraph isomorphism problems. For each 2D or 3D map M , we have generated a graph G = (V, E) such that V associates a vertex with every 0-cell of M and E associates an edge with every 1-cell of M , as illustrated in Fig. 14.

To search for patterns, we consider the partial subgraph isomorphism problem. Indeed, a pattern graph associated with a pattern map is not necessarily an induced subgraph of the target graph associated with the target map, as illustrated in Fig. 14. Hence, in the 2D (resp. 3D) database, 71 patterns (resp. 1) are not found in the corresponding target if we look for an induced subgraph instead of a partial subgraph.

Looking for partial subgraph isomorphisms allows us to find all submap isomorphisms. However, some of the subgraph isomorphisms may not correspond to submap isomorphisms as topological relationships are ignored, as illustrated in Fig. 14.

We have considered three different algorithms for solving subgraph isomorphism problems, i.e., Vflib [START_REF] Cordella | A (sub)graph isomorphism algorithm for matching large graphs[END_REF], ILF [START_REF] Zampelli | Solving subgraph isomorphism problems with constraint programming[END_REF], and LAD [START_REF] Solnon | Alldifferent-based filtering for subgraph isomorphism[END_REF]. All of them perform a systematic exploration of the search space 1: Experimental results: for each database, the first column (Map) gives results obtained with our submap isomorphism algorithm; the last three columns give results obtained with the subgraph isomorphism algorithms ILF, LAD, and Vflib; the first line (# fail) gives the number of patterns for which the CPU time limit of 1000 seconds has been exceeded for at least one target of the database; the last three lines give the average, minimum and maximum number of seconds spent to find all occurrences of a pattern in all the targets (only for the patterns for which the CPU time limit has not been exceeded).

composed of all possible injective matchings from the set of pattern vertices to the set of target vertices. To reduce the search space, this exhaustive exploration is combined with filtering techniques that aim at removing candidate couples of non matched pattern-target vertices. Vflib, ILF, and LAD consider different filtering techniques, and we refer the reader to [START_REF] Solnon | Alldifferent-based filtering for subgraph isomorphism[END_REF] for a detailed comparison of them. For Vflib, we have considered the Vflib2 variant, which obtained the best results on our benchmarks. For ILF, we have set the k parameter to 1.

Experimental results

Experimental settings.. All algorithms have been implemented in C or C++. All our experiments were made on a PC with a 2.26 GHz Intel Xeon E5520 processor. For each database, and for each pattern of the database, we have searched for all occurrences of this pattern in all the targets of the database. This corresponds to 224 × 224 + 62 × 800 = 99, 776 runs of Algorithm 3. As the subgraph isomorphism problem is NP-complete, we have limited the CPU time spent to search for all occurrences of a pattern in one target graph to 1000 seconds. Note that when the search for a pattern in one target has exceeded this CPU time limit of 1000 seconds for one algorithm, we have discarded all results for this pattern and this algorithm in table 1.

Comparison of CPU times.. Table 1 gives the CPU time spent to find all occurrences of a pattern in all the targets of the considered database. Our submap algorithm is very effective: on average, it is able to find all occurrences of a pattern in the 224 (resp. 800) targets in 38.98 (resp. 228.68) seconds for the 2D (resp. 3D) database. Actually, the number of darts visited during the search process is usually far below the theoretical bound: in the 2D (resp. 3D) database, the average number of darts visited to find all occurrences of a pattern in one target is 45 (resp. 119) whereas a pattern has 2, 175 (resp. 23, 413) darts on average and a target has 14, 509 (resp. 179, 540) darts on average. This comes from the fact that we consider an optimized version of the algorithm which checks that the matching f is an injection during the traversal, and which stops the traversal as soon as two different pattern darts are matched to a same target dart.

Table 1 also gives results for subgraph isomorphism. For the 2D database, our submap algorithm is 4.7 times as fast as ILF, which is the fastest of the three considered subgraph isomorphism algorithms. Moreover, if ILF has never exceeded the CPU time limit of 1000 seconds for a pattern/target couple, LAD and Vflib have exceeded this limit for 1 and 8 patterns respectively.

For the 3D database, our submap algorithm has never exceeded the CPU time limit whereas it has been exceeded by ILF, LAD, and Vflib for 6, 6, and 40 patterns respectively (among the 62 considered patterns). On average, our submap algorithm is slightly slower than ILF, but this comes from the fact that the 6 unsolved instances are harder instances which increase the average CPU time of our submap algorithm. Indeed, if we do not consider these 6 instances, our submap algorithm solves the 56 remaining instances in 135.58 seconds on average (minimum 16.73 and maximum 770.23). If we only consider the 22 instances solved by Vflib, the average time is 84.98 seconds (minimum 16.73 and maximum 144.95). Actually, the harder instances for our submap algorithm are also the harder ones for the subgraph isomorphism. However, if our algorithm is still able to solve these hard instances rather quickly6 , subgraph isomorphism algorithms are not able to solve them within a reasonable amount of time.

Of course, our submap algorithm does not solve the same problem: It exploits the topology to search for patterns in polynomial time. When ignoring this topology, the problem becomes NP-complete, and it is worth noting here the rather good performances of the three subgraph isomorphism algorithms with regard to the fact that they have exponential time complexities in the worst case together with the fact that graphs have thousands of vertices. In particular, ILF exhibits very good performances on some instances. This comes from the fact that it exploits structural properties to prune the search space. In particular, it checks that, for every pattern node u, there exists at least one target node v such that for every neighbor of u there exists a different neighbor of v which has a greater or equal degree (thus ensuring that every neighbor of u can be matched to a different neighbor of v). If this is not the case, then ILF can conclude that there is no subgraph isomorphism without any enumeration. Actually, this kind of structural heuristic could be very easily integrated in our submap isomorphism algorithm.

Comparison of the solutions found.. For all 2D patterns and for all 3D patterns but 5, our submap algorithm has found only one solution, corresponding to the target from which it has been extracted. However, 5 3Dpatterns have been found in more than one image: These patterns are classical patterns (such as the sphere displayed in Fig. 13(d)) which are building components of many meshes.

Subgraph isomorphism has always found at least as many solutions as submap isomorphism. However, as pointed out in Section 5.2, subgraph isomorphism may find more solutions than submap isomorphism as it ignores the topology. Hence, in the 2D (resp. 3D) database, 148 (resp. 10) patterns have been found more than once in the corresponding targets due to automorphisms. Like for submap isomorphism, 5 3D patterns have been found in more than one target. However, if submap isomorphism never found a same 2D pattern in more than one target, subgraph isomorphism has found 2 2D patterns in more than one target. These figures show us that, in practice, the time much more depends on the size of the target than on the size of the pattern. Actually, each traversal is stopped as soon as a pattern dart is matched to more than one target dart so that the number of darts visited during one traversal is usually far below the number of darts in the pattern map (this number is 45 in 2D and 119 in 3D, and it does not really depend on the number of darts of the pattern.). However, we must perform a new traversal for every dart of the target map so that the observed CPU time increases linearly with respect to the size of the target map.

Discussion

This paper is a first contribution to the problem of comparing combinatorial maps. We define the map and submap isomorphism problems, which may be used to decide if two maps are equivalent, or if a copy of a map is included in another map, and we describe polynomial algorithms for solving these problems. The proposed definitions and algorithms are generic and hold for any open nD combinatorial maps, which may be used to model nD objects with boundaries. We also introduce planar combinatorial maps, which may be used to model 2D objects that are embedded on a plane such as, for example, images, and we show how to extend our algorithms to decide if two planar maps are isomorphic. Experiments show that this work may be used to search for patterns in 2D images or 3D meshes with very challenging CPU times.

The problem of finding a pattern in an image is an important issue that has often been tackled by modeling images with graphs such as, for example, RAGs. If there exist rather efficient heuristics for solving the graph isomorphism problem7 [START_REF] Mckay | Practical graph isomorphism[END_REF][START_REF] Sorlin | A parametric filtering algorithm for the graph isomorphism problem[END_REF], this is not the case for the subgraph isomorphism problem which is computationally intractable in the general case (NP-complete), and therefore practically unsolvable for some instances. Hence, if subgraph isomorphism algorithms have been able to solve many instances with reasonable CPU times, they are usually longer than submap isomorphism and, for some instances, they have not been able to find solutions within a reasonable amount of time.

Interestingly, using combinatorial maps to model images allows us to have more relevant results -as combinatorial maps model information that cannot be modelled with classical RAGs such as multi-adjacency or the order of neighbor regions around a region-and these results are computed much more quickly -as the subisomorphism problem becomes polynomial. Some polynomial algorithms have been proposed to solve particular cases of the subgraph isomorphism problem. In particular, Jiang and Bunke have proposed polynomial algorithms solving the isomorphism [START_REF] Jiang | Optimal quadratic-time isomorphism of ordered graphs[END_REF] and subsiomorphism [START_REF] Jiang | Marked subgraph isomorphism of ordered graphs[END_REF] decision problems of ordered graphs, i.e., graphs such that, for each vertex, the edges incident to this vertex have a unique order. These algorithms are based on graph traversals and our algorithms for (sub)map isomorphism may be viewed as a generalization of this work to nD open combinatorial maps.

A number of perspectives are being looked into. In particular, (sub)map isomorphism is an exact decision problem which allows us to search for a pattern in a map. We plan to develop error-tolerant methods, which are able to quantify the similarity of two maps by means of the size of their largest common submap, or by means of the cost to transform a map into another by using the edit operations defined in [START_REF] Damiand | Removal and contraction for n-dimensional generalized maps[END_REF][START_REF] Baba-Ali | Insertion and expansion operations for n -dimensional generalized maps[END_REF]. We also plan to use our (sub)isomorphism algorithms to search for patterns that occur frequently in a database of images modelled by combinatorial maps, thus characterizing classes of images. We have proposed in [START_REF] Gosselin | Signatures of combinatorial maps[END_REF] a signature of combinatorial maps which is based on a map traversal similar to the one used in our isomorphism algorithm. This map signature may be used to decide in linear time if a new combinatorial map already belongs to a database of map signatures. We now plan to use this map signature and our submap algorithm in order to find frequent patterns in a database of maps.

Figure 2 :

 2 Figure 2: An example of a 3D combinatorial map. (a) A 3D object. (b) The corresponding 3D combinatorial map (external volume on the left; interior on the middle and the right). The graphical convention is the same as in 2D. β 3 is not drawn, but (partially) given in the array.

  (⇐) If checkIsomorphism(M, M ′ ) returns true, then M and M ′ are isomorphic since true is returned only if the test in line 4 succeeds. (⇒) Let us suppose that M and M ′ are isomorphic, so that there exists an isomorphism function ϕ : D → D ′ , and let us show that checkIsomorphism(M, M ′ ) returns true. Let d 0 ∈ D be the dart chosen at line 1 of Algorithm 1. As the loop lines 2-5 iterates on every dart d ′ 0 ∈ D ′ , there exists an iteration of this loop for which d ′ 0 = ϕ(d 0 ). Let us show that for this iteration traverseAndBuildMatching(M, M ′ , d 0 , d ′ 0 ) returns the array f such that ∀d ∈ D, f [d] = ϕ(d) so that true is returned line 5 of Algorithm 1: • Claim 1: When pushing a dart d in S, f [d] = ϕ(d). By induction. The claim holds for the push of line 3 as f [d 0 ] is set to d ′ 0 = ϕ(d 0 ) at line 2. The claim also holds for the push at line 9 as (1) f [β i (d)] is set to

Figure 4 :

 4 Figure4: Submap isomorphism example. M is a submap of M ′ as it is obtained from M ′ by deleting darts k to r. M ′′ is not isomorphic to a submap of M ′ as the injection f : X → D that respectively matches darts 1 to 10 to darts a to j does not verify Theorem 2: for example, dart 4 is 2-free and it is matched to dart d which is 2-sewn with a dart (b) which is itself matched (i.e., f -1 (b) = 2).

Figure 5 :

 5 Figure5: Two maps that are isomorphic but not planar-isomorphic.

Figure 6 :Figure 7 :

 67 Figure 6: Isomorphisms of maps with undefined parts on a sphere versus in the plane: on a sphere, (b) and (c) are isomorphic, and (a) is a submap of both (b) and (c). However, in the plane (b) and (c) are not isomorphic, and (a) is a submap of (b) but not of (c). Exterior darts are drawn in bold.

Figure 8 :

 8 Figure 8: Three maps which are isomorphic, but not planar isomorphic. (a) and (b) are two maps with different orientations. (b) and (c) have the same orientation but (b) has no infinite face while (c) has one.

Algorithm 4 :

 4 buildExterior(M, d ext , inf inite) Input: a connected map M = (D, β 1 , β 2 ), an initial exterior dart d ext ∈ D, and a boolean inf inite which is true if d ext belongs to the infinite face, false otherwise Output: the set of all exterior darts if infinite is true then return β 1 (d ext ) 1 Ext ← ∅; d curr ← d ext 2 repeat 3 Ext ← Ext ∪ {d curr } 4 d curr ← β 1 (d curr ) 5 while d cur is not 2-free do 6 d curr ← β 21 (d curr ) 7 until d curr = d ext ; Given (M, d ext , inf inite), buildExterior computes all the exterior darts of M .

return true 8 return false 9

 9 function between M and M ′ then 7 Theorem 4. checkPlanarIsomorphism(P M, P M ′ ) returns true iff P M and P M ′ are planar isomorphic. Proof. First, if P M and P M ′ are planar isomorphic, there is an isomorphism function f such that f (Ext) = Ext ′ and f (Inf ) = Inf ′ . Thus, we have necessarily inf inite = inf inite ′ and f (d ext ) = d ′ 0 ∈ Ext ′ . By testing all the darts d ′ 0 ∈ Ext ′ , we are sure to find this case and thus the algorithm will return true. Second, if our algorithm returns true, we have an isomorphism function between M and M ′ such that inf inite = inf inite ′ and f (d ext ) = d ′ 0 ∈ Ext ′ . Since we are in the case of 1-closed maps, this implies that f (Inf ) = Inf ′ and f (Ext) = Ext ′ and thus P M and P M ′ are planar isomorphic. ✷ Remember that we are able to decide of the isomorphism of 2-maps in O(|D| • |D ′ |) time. Having an information about the set of exterior darts and an efficient way to compute these darts allows us to reduce the complexity to O(|Ext ′ | • |D|). In many cases, |Ext ′ | is significantly smaller than |D ′ |. Typically, |Ext ′ | = O( |D ′ |) for the lattice Z 2 .

function then 3 PM

 3 ′′ = P M ′ ↓f (D) 4 if checkPlanarIsomorphism(P M, P M ′′ ) then

Figure 9 :Figure 10 :

 910 Figure 9: Characteristics of the two databases: the first two lines describe the 2D database, the last two lines describe the 3D database. For each line, we first give the number of maps and then the number of darts, vertices, edges and faces (average, minimum and maximum values).

Figure 11 :

 11 Figure 11: Some selected sub-images. (a) from arbogreens05, size 48 × 49 pixels. (b) from cherries14, size 193 × 129 pixels. (c) from football05, size 83 × 112 pixels. (d) from greenlake06, size 48 × 54 pixels. (e) from swissmountains22, size 82 × 48 pixels.

Figure 13 :

 13 Figure 12: Examples of 3D objects.

  Scale up property of the submap algorithm.. Figures 15 and 16 allow us to study the scale up property of the submap algorithm by showing the relation between the average time spent to search for a pattern map in the whole database (both in 2D and 3D) and the number of darts of the pattern (Figures 15(a) and 16(a)), or the target (Figures 15(b) and 16(b)).

Figure 15 :Figure 16 :

 1516 Figure 15: CPU time with respect to size for the 2D database. (a) each points corresponds to a different pattern map M ; the x-axis gives the number of darts of M and the y-axis gives the average time for finding all occurrences of M in all target maps. (a) each points corresponds to a different target map M ′ ; the x-axis gives the number of darts of M ′ and the y-axis gives the average time for finding all occurrences of every pattern map in M ′ .

  Figure 1: An example of 2D combinatorial map. Darts are represented by black arrows. Two 1-sewn darts are drawn consecutively, and two 2-sewn darts are concurrently drawn, in reverse orientation, with a little grey segment between them.

									6
							7	8	9	11	10	5
									12		4
												17
											13 16
							1	15
												18
									14			3
									2
	D	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18
	β1	2	3	4	5	6	7	1	9	10	11	8	13	14	15	12	17	18	16
	β2	15	14	18	17	10	9	8	7	6	5	12	11	16	2	1	13	4	3
										2

  . . , d k ) such that d k = d. Therefore, each time a dart d i of this path is popped from S (line 5), d i+1 is pushed in S (line 9) if it has not been pushed before (through another path). ✷ The time complexity of Algorithm 1 is O(n • |D| • |D ′ |) Let us first show that the time complexity of Algorithm 2 is O(n • |D|). Indeed, the for loop (lines 6-9) is iterated n times, and the while loop (lines 4-9) is iterated |D| times as (1) exactly one dart d is removed from the stack S at each iteration, and (2) each dart d ∈ D enters S at most once (it enters S only if f [d] = nil, and before entering S, f [d] is set to a dart of D ′ ). Let us then note that the test from line 4 of Algorithm 1 may be performed in O(n • |D|). As Algorithm 2 and the test of line 4 are performed at most |D ′ | times (once for each dart of M ′ ), the overall time complexity of Algorithm 1 is O

  2 • |D ′ |). One loop of this algorithm is done by using Algorithm 2, which complexity (in 2D) is O(|D|). The complexity of planar submap computation is O(|D ′ |), thanks to the efficient computation of inf inite ′′ and d ′′ ext . Finally the test of planar isomorphism is achieved by using Algorithm 5, the complexity of which is O(|Ext ′′ | • |D|). Since the number of darts in Ext ′′ is smaller than the number of darts in D ′′ , we can bound the overall complexity of one loop by O(|D| 2 ) since |D| = |D ′′ |.

		# maps		# darts		# vertices			# edges			# faces
			avg	min	max	avg min	max	avg min	max	avg min	max
	2D targets	224	14,509 1,768	35,896	4,789 594 11,811	7,255 884	17,948	2,598 336	6,231
	2D patterns	224	2,175	48	22,338	718	16	7,365	1,088	24	11,169	384	14	3,950
	3D targets	800 179,540	672 1,337,652 10,683	42 98,256 24,502	92 167,219 14,962	56 111,471
	3D patterns	62	23,413	456	175,584	1,704	40 14,848	5,033 114	44,119	3,326	76	29,264

Table

  Figure14: Example of graphs associated with 2D-maps: Gt (resp. Gp) is the graph generated from Mt (resp. Mp). Mp is a submap of Mt. There is only one submap isomorphism which matches faces A ′ , B ′ , and C ′ to faces A, B, and C respectively (we cannot exchange faces B ′ and C ′ without violating topological constraints). Gp is a partial subgraph of Gt; it is not an induced subgraph as edge (b ′ , g ′ ) does not belong to Gp whereas edge (b, g) belongs to Gt. There are two partial subgraph isomorphisms: the first one matches vertices a ′ , b ′ , d ′ , e ′ , f ′ , and g ′ , to vertices a, b, d, e, f , and g respectively; the second one is obtained from the first one by exchanging a ′ and b ′ with f ′ and g ′ .

		2D database: 224 patterns/224 targets	3D database: 62 patterns/800 targets
		Map	ILF	LAD	Vflib	Map	ILF	LAD	Vflib
	# fail	0	0	1	8	0	6	6	40
	avg time	38.98	184.04	4,580.14	1,197.58	228.68 190.36	419.41	603.05
	min time 19.11	29.40	99.05	64.50	16.75	32.34	9.38	175.87
	max time 56.75 1,975.71 15,501.44 25,648.42 2,983.09 816.12 4,348.94 2,575.84

A permutation on D is a one-to-one mapping from D to D.

An involution f on D is a one-to-one mapping from D to D such that f = f -1 .

A fixed point of a function f is an element e such that f (e) = e.

The database of free images for research purpose is available on Internet http://www.cs.washington.edu/research/imagedatabase/

These objects are available in the Shape Retrieval Contest web page http://www.aimatshape.net/event/SHREC/

The maximum time for searching for all occurrences of a pattern in all the targets of the 3D database is 3, 000 or so seconds, but this database contains 800 target maps so that the CPU time spent for each target is far below the time limit of 1000 seconds.

The theoretical complexity of graph isomorphism is an open question: If it clearly belongs to NP, it has not been proven to be NP-complete.

Acknowledgement

The authors acknowledge authors of [PABL07], specially Pascal Lienhardt, for all the fruitful discussions about open combinatorial maps. This work was done in the context of project Sattic ( Anr grant Blanc07-1 184534). Colin de la Higuera, Jean-Christophe Janodet and Émilie Samuel also acknowledge that this work was supported in part by the IST Programme of the European Community, under the Pascal 2 Network of Excellence, Ist-2006-216886.