Thi-Hoa-Hue Nguyen
email: nguyenth@i3s.unice.fr

Nhan Le-Thanh
email: nhan.le-thanh@unice.fr

Ensuring the Semantic Correctness of Workflow Processes: An Ontological Approach

Keywords: Ensuring, Ontology, Semantic Constraint, Semantic Correctness, SPARQL query, Workflow Process

Workflow verification has been known as an important aspect of workflow management systems. Many existing approaches concentrate on ensuring the correctness of workflow processes at the syntactic level. However, these approaches are not sufficient to detect errors at the semantic level. This paper contributes to ensure the semantic correctness of workflow processes. First, we propose a formal definition of semantic constraints and an O(n 3 )-time algorithm for detecting redundant and conflicting constraints. Second, by relying on the CPN Ontology (a representation of Coloured Petri Nets with OWL DL ontology) and sets of semantic constraints, workflow processes are semantically created. And third, we show how to check the semantic correctness of workflow processes with the SPARQL query language.

Introduction

Workflows have drawn an enormous amount of attention from the research community and the industry. Over the years, workflow technology has been applied extensively to the business area. So far, various researchers have focused on process specification techniques [START_REF] Ellis | Modeling and enactment of workflow systems[END_REF], [START_REF] Van Der Aalst | The application of petri nets to workflow management[END_REF] and on conceptual models of workflow [START_REF] Barros | Essential principles for workflow modelling effectiveness[END_REF], [START_REF] Koschmider | Ontology based business process description[END_REF]. However, specifying a real-world business process is mostly manual and is thus prone to human error, resulting in a considerable number of failed projects. Therefore, model quality, correctness and re-usability become very important issues. Although numerous approaches have been already developed to ensure workflow correctness at the syntactic level (e.g., avoiding deadlocks, infinite cycles, etc.). At the semantic level there may exist errors. Recently, few researches focus on checking the semantic conformance of workflow processes.

To check the semantic correctness of a model, we consider semantic constraints as domain specific restrictions on a business process which need to be conformed during the process is executed. Let us take an example: In a process for the Order Management activity, when an order is accepted, an order confirmation must be sent out later; If no order confirmation is scheduled to be sent, or this activity is not done in the right position, a semantic error occurs.

The work in [START_REF] Fellmann | A query-driven approach for checking the semantic correctness of ontology-based process representations[END_REF] provides a very useful inspiration for our work, but it does not discuss how to formulate semantic constraints and also does not mention about the control-flow perspective in process models. Our objective is to support workflow designers in generating semantically rich workflow processes which allow syntactic and semantic verification. In this paper, we restrict ourselves to ensure the semantic correctness of workflow processes. Our contributions are:

-Giving a formal method to describe a variety of semantic constraints; -Proposing an algorithm to check redundant and conflicting semantic constraints; -Developing an ontology for annotating semantic constraints and representing control flow-based business workflow processes based on that ontology; -Showing how to use the SPARQL query language [6] to check the semantic correctness of workflow processes.

This paper is organized as follows: in Section 2, we discuss related work. A short introduction to the CPN Ontology, which is defined to represent Coloured Petri Nets (CPNs) with OWL DL, is given in Section 3. Section 4 proposes a formal definition of semantic constraints for business processes. An algorithm used for checking redundant and conflicting semantic constraints is presented. We then develop a semantic conformance-oriented ontology. In Section 5, we present the creation of correspondences between those two ontologies to develop workflow processes. These workflows enable designers to check their semantic correctness. Five semantic verification issues of a workflow process are introduced in Section 6. Finally, Section 7 concludes the paper with an outlook on the future research.

Related Work

Today, software systems that automate business processes have become more and more advanced. Various researchers have paid attention to the problem of ensuring the correctness of process models. Many methods have been done in workflow verification. Most of them focus on the control-flow perspective, such as [START_REF] Van Der Aalst | Verification of workflow nets[END_REF], [START_REF] Verbeek | Diagnosing workflow processes using woflan[END_REF], [START_REF] Bi | Applying propositional logic to workflow verification[END_REF], [START_REF] Wainer | Logic representation of processes in work activity coordination[END_REF], [START_REF] Sadiq | Analyzing process models using graph reduction techniques[END_REF] to prevent errors (e.g., avoiding deadlocks, infinite cycles) at the syntactic level. Nevertheless, they check mainly the conformance of a workflow process based on the principle that if the constraints on data and control flow are met during execution, the workflow is correct.

Recently, a number of researches have grown beyond the scope of pure control-flow verification. Some approaches analyze the final state of the whole workflow [START_REF] Lu | Automatic workflow verification and generation[END_REF] or consider running processes [START_REF] Ly | Integration and verification of semantic constraints in adaptive process management systems[END_REF], [START_REF] Kumar | Ensuring compliance with semantic constraints in process adaptation with rule-based event processing[END_REF], [START_REF] Ly | On enabling integrated process compliance with semantic constraints in process management systems -requirements, challenges, solutions[END_REF]. In [START_REF] Ly | Integration and verification of semantic constraints in adaptive process management systems[END_REF], semantic constraints are defined over processes which are used to detect semantic conflicts caused by violation only of dependency and mutual exclusion constraints. They presented techniques to ensure semantic correctness for single and concurrent changes at process instance level. With regard to ontological approaches, aspects of semantic correctness are considered in few researches, such as [START_REF] Fellmann | A query-driven approach for checking the semantic correctness of ontology-based process representations[END_REF], [START_REF] Thomas | Semantic process modeling -design and implementation of an ontology-based representation of business processes[END_REF], [START_REF] Weber | Beyond soundness: on the verification of semantic business process models[END_REF]. The approach of [START_REF] Weber | Beyond soundness: on the verification of semantic business process models[END_REF] requires both the annotation of preconditions and effects to ensure the models are semantically correct. In [START_REF] Fellmann | A query-driven approach for checking the semantic correctness of ontology-based process representations[END_REF], the SPARQL query language is used to check the semantic correctness of ontology-based process representations. Individual model elements were annotated with concepts of a formal ontology, and constraints were formalized as SPARQL queries. However, these approaches depend on the availability of an ontology and a bulky annotation of process models.

We know that the ontology-based approach for modelling business process is not a new idea. There are some works made efforts to build business workflow ontologies, such as [START_REF] Gasevic | Interoperable petri net models via ontology[END_REF], [START_REF] Koschmider | Ontology based business process description[END_REF], [START_REF] Sebastian | Customizable workflow support for collaborative ontology development[END_REF] to support (semi-)automatic system collaboration, provide machine-readable definitions of concepts and interpretable format. However, the issue that relates to workflow verification at the syntactic level is not mentioned. By extending the state-of-the-art, we use the Web Ontology Language to define the CPN Ontology for representing CPNs with OWL DL ontology and the semantic conformance-oriented ontology. Our ontological approach enables to create high quality and semantically rich workflow processes.

Representation of Coloured Petri Nets with OWL DL ontology

In this Section, we introduce the CPN Ontology [START_REF] Nguyen | An ontology-enabled approach for modelling business processes[END_REF] defined for business processes modelled with CPNs. The purpose is to ensure the syntactic correctness of workflow processes and to facilitate business process models easy to be shared and reused. On one hand, Coloured Petri Nets (CPNs) [START_REF] Kristensen | The practitioner's guide to coloured petri nets[END_REF] have been developed into a full-fledged language for the design, specification, simulation, validation and implementation of large software systems. Consequently, modelling business processes with CPNs supports workflow designers easy to verify the syntactic correctness of workflow processes [START_REF] Verbeek | Diagnosing workflow processes using woflan[END_REF]. On the other hand, OWL DL [START_REF]W3C: Owl web ontology language reference[END_REF], which stands for OWL Description Logic, is equivalent to Description Logic SHOIN (D). OWL DL supports all OWL language constructs with restrictions (e.g., type separation) and provides maximum expressiveness while keeping always computational completeness and decidability. Therefore, we choose OWL DL language to represent the CPN Ontology. We believe that the combination of CPNs and OWL DL provides not only semantically rich business process definitions but also machine-processable ones. Figure 1 depicts the core concepts of the CPN ontology.

The CPN Ontology comprises the concepts: CPNOnt defined for all possible CPNs; Place defined for all places; Transition defined for all transitions; InputArc defined for all directed arcs from places to transitions; OutputArc defined for all directed arcs from transitions to places; Token defined for all tokens inside places (We consider the case of one place containing no more than one token at one time); GuardFunction defined for all transition expressions; CtrlNode defined for occurrence condition in control nodes; ActNode defined for occurrence activity in activity nodes, Delete and Insert defined for all expressions in input arcs and output arcs, respectively; Attribute defined for all Properties between the concepts in the CPN Ontology are also specified in Figure 1. For example, the concept CP N Ont is defined with three properties, including hasP lace, hasT rans and hasArc. It can be glossed as 'The class CP N Ont is defined as the intersection of: (i) any class having at least one property hasP lace whose value is restricted to the class P lace and; (ii) any class having at least one property hasT ransition whose value is restricted to the class T ransition and; (iii) any class having at least one property hasArc whose value is either restricted to the class InputArc or the class OutputArc'.

Semantic Constraints for Business Processes

As mentioned previously, our work aims at representing workflow processes modelled with CPNs in a knowledge base. Therefore, in this Section, we focus on ensuring their quality by guaranteeing their semantic correctness.

Definition of Semantic Constraints

By taking account domain experts in support of modellers at build time, a set of semantic constraints is specified, which then is used to develop a corresponding workflow. According to [START_REF] Ly | Integration and verification of semantic constraints in adaptive process management systems[END_REF], there are two fundamental kinds of semantic constraints, including mutual exclusion constraints and dependency constraints. For interdependent tasks, e.g., the presence of task A indicates that task B must be included, however, task B can be executed while task A is absence. In fact, there may exist tasks that are coexistent. This refers to the coexistence constraints. Consequently, we propose three basic types: mutual exclusion constraints, dependency constraints and coexistence constraints.

Definition 1 (Semantic Constraint).

Let T be a set of tasks. A semantic constraint: c = (constraintT ype, appliedT ask, relatedT ask, order, description, [Equivalence]) where:

• constraintT ype ∈ {mExclusion, dependency, coexistence};

• appliedT ask ∈ T ;

• relatedT ask ∈ T ;

• order ∈ {bef ore, af ter, concurrence, notSpecif ied} ; • description is an annotation of the constraint; • Equivalence is a set of tasks which are equivalent to task appliedT ask.

In Definition 1, the first parameter constraintT ype denotes the type of a semantic constraint. Each value of constraintT ype refers to the relationship between the executions of the source task denoted by the second parameter appliedT ask and the target task denoted by the third parameter relatedT ask. Parameter order specifies the order between the source and target tasks in a process model. The first four parameters are very important when defining a semantic constraint. The fifth parameter, description, is used for describing the constraint. Equivalence is an optional parameter, which contains a set of tasks (if any) being equivalent to the source task. Let us continue the example of a process for the Order Management activity. The process is determined as follows: After receiving an order, two tasks have to do in parallel are authenticate client and check availability. If both of these tasks result "true", the order is accepted and an order confirmation is sent out. Otherwise, an order refusal is sent out. Some semantic constraints of the process are formed as follows: c1 = (dependency, authenticate client, receive request, before, receiving an order has to be performed before authenticating client, {authenticate purchaser}); c2 = (dependency, check availability, receive request, before, receiving an order has to be performed before checking availability); c3 = (coexistence, authenticate client, check availability, concurrence, client authentication and checking availability are performed in parallel); c4 = (dependency, evaluate results, authenticate client, before, evaluating the results obtained from the relevant departments); c5 = (dependency, evaluate results, receive request, before, receiving an order has to be performed before evaluating results related to the order)

Checking implicit, redundant and conflicting semantic constraints

A workflow process is designed based upon the specified semantic constraints. However, when defining those constraints, there may occur implicit, redundant or conflicting semantic constraints. Note that a combination of two or more constraints can constitute some new constraints. This is demonstrated by the order parameter in Definition 1. As mentioned above, this parameter indicates the execution order of a source task and a target task. Consider T 1 , T 2 , T 3 , instances of tasks, we identify the following properties which are associative, symmetric, transitive and/or commutative presented in Table 1. These properties are used for inferring implicit semantic constraints. As a result, detecting implicit constraints plays a crucial role in the elimination of redundant constraints. In addition, conflicting constraints will lead to undesirable results. Therefore, it is necessary to resolve them before they can be applied.

Let us consider three constraints presented in Subsection 4.1, including c1, c4 and c5. According to transitivity property (1) in Table 1, a new constraint, named c1 -4, can be inferred from constraints c1 and c4, where: c1_4=(dependency, evaluate results, receive request, before, receiving an order has to be performed before authenticating client and evaluating the results obtained from the relevant departments)

Comparing constraint c1 -4 to constraint c5, their first four values are the same, hence constraint c5 is redundant. As a result, constraint c5 has to be removed.

Because of the different complexity of each semantic constraint set, we need an algorithm to resolve issues related to redundancy and conflict semantic constraints. The procedure for validating the constraint set will stop as soon as it detects a couple of conflicting constraints and a message is generated to notify the user. In addition, if there exist any redundant constraints, they will be removed. In our algorithm in Figure 2, the boolean function conf lict is used for checking the conflict between two constraints, e.g., it returns true if they are conflicting, otherwise, it returns f alse. The function inf er is used for inferring implicit constraints. The time complexity of the algorithm is O(n 3 ) where n is the number of semantic constraints. To provide a representation of semantic constraints related to process elements, in next Subsection, we will describe an approach for constructing a semantic conformance-oriented ontology.

Development of a Semantic conformance-oriented Ontology

Our work aims at representing processes modelled with CPNs in a knowledge base. Therefore, to provide a representation of semantic constraints related to process elements, we develop an approach for constructing a new ontology. This ontology is oriented to semantic conformity checking in workflow processes. We focus on formalizing the concepts/relations corresponding to the knowledge that is required by model elements.

The following keystones to transform a set of semantic constraints into an OWL DL ontology:

• Each semantic constraint c is mapped to an instance of owl : Class.

• appliedT ask and relatedT ask are mapped to two instances of owl : Class.

The rdf s : subClassOf property is used to state that these classes is a subclass of the constraint class. • Each value of constraitT ype or order is defined as an instance of the built-in OWL class owl : ObjectP roperty. • description is defined as an instance of the built-in OWL class owl : Datatype P roperty; • Each value in the set Equivalence is mapped to an instance of owl : Class.

The built-in property owl : equivalentClass is used to link every class description of these classes to the class description of appliedT ask.

In the upcoming Section, we will discuss about the integration of a semantic conformance-oriented ontology (domain knowledge) and the CPN Ontology to create workflow processes.

Creation of Correspondences Between Ontologies

We rely on ontology mapping techniques for matching semantics between ontologies, i.e., the CPN Ontology and Domain Ontology (a semantic conformanceoriented ontology). In our case, the articulation of two ontologies are used not only for creating semantically workflow processes, but also for verifying their correctness.

We now define our use of the term "mapping": Consider two ontologies, O 1 and O 2 . Mapping of one ontology with another is defined as bringing ontologies into mutual agreement in order to make them consistent and coherent. It means that for a concept or a relation in ontology O 1 , we try to find the same intended meaning in ontology O 2 ; For an instance in ontology O 1 , we find the same instance in ontology O 2 .

Definition 2 (Mapping related to the bef ore property).

We define a mapping for all instances I C of a semantic constraint in which the order between the instance of class appliedT ask, named task a , and the instance of class relatedT ask, named task b , is indicated by the object property bef ore. The type of instance I C is either dependency or coexistence. A set of correspondences is determined as follows:

• Each instance of class appliedT ask or relatedT ask is mapped into an instance of class T ransition (expressing activity node). • There exists a firing sequence t 1 t 2 . . . t n , where t 1 , t n are the instances of class T ransition corresponding to instances task a and t b respectively,

t a = t 1 , t b = t n n ≥ 2.
Definition 3 (Mapping related to the concurrence property).

We define a mapping for all instances I C of a semantic constraint in which the order between the instance of class appliedT ask, named task a , and the instance of class relatedT ask, named task b , is indicated by the object property concurrence. The type of instance I C is coexistence. A set of correspondences is determined as follows:

• Each instance of class appliedT ask or relatedT ask is mapped into an instance of class T ransition (expressing activity node). • Two instances of class transitions which correspond to instance task a and instance task b can be enabled at the same time.

It is important to underline that object property bef ore is the symmetrical property of object property af ter. Consequently, we do not define a mapping related to the af ter property. By continuing the process schema for the order management activity in Section 4, Figure 3 shows the mapping of some instances between two onotologies, CPN Ontology and Semantic Conformance-oriented Ontology. We have introduced the formal definition of semantic constraints and illustrated how to model a workflow process with CPNs based on specified semantic constraints. Note that concrete workflow processes are represented in RDF syntax. Moreover, to develop or modify a workflow process, manipulation operations [START_REF] Nguyen | An ontology-enabled approach for modelling business processes[END_REF] (e.g., inserting a new element) are required. Therefore, it is necessary to verify workflow processes at design time before they are put into use.

Semantic Verification Issues

By using the algorithm presented in Section 4, the sets of specified semantic constraints are checked redundant and conflicting. Hence, we here pay attention to the research question relating to semantic verification: Is the behavior of the individual activities satisfied and conformed with the control flow? To answer this question, we address the following semantic verification issues:

• Are there activities whose occurrences are mutual exclusion, but that may be executed in parallel or in sequence? • Are there activities whose executions are interdependent, but that may be carried out in choice or in parallel? • Are there activities whose occurrences are coexistent, but that may be executed in choice? • Are there any couples of activities whose order executions are defined as one before the other, but that may be executed in the opposite? • Are there any couples of activities whose order executions are defined as one after the other, but that may be executed in the opposite order?

Because concrete workflows are stored in RDF syntax, we rely on the CORESE [START_REF] Corby | Corese/kgram[END_REF] semantic search engine for answering SPARQL queries asked against an RDF knowledge base. We initiate SPARQL queries to verify whether workflow processes contain semantic errors or not. SELECT query form is chosen for this work. After a SELECT keyword, the variables are listed that contain the return values. And in the WHERE clause, one or more graph patterns can be specified to describe the desired result.

The following query1 relating to the third verification issue is used to query if the model contains 'any pairs of activities whose occurrences are coexistence but that may be executed in choice'. The properties h : coexistence and h : concurrence defined in the first ontology indicate the semantic constraint between activities ?t1 and ?t2. On the other hand, the other properties defined in the second ontology which represent these activities restricted to the control flow perspective. By applying this query to the workflow example depicted in Figure 3, the result is empty.

The sample query does not only demonstrate that the SPARQL query language is able to check the semantic correctness of workflow processes, but also the usage of terminological background knowledge provided by the semantic conformance-oriented ontology and CPN Ontology. Moreover, by representing CPNs-based business processes with OWL DL ontology we can also verify the soundness of models. This means that we can check syntactic errors (for example, deadlocks, infinite cycles and missing synchronization, etc.) by the SPARQL query language.

SELECT ?t1 ?t2 WHERE { ?t1 rdf:type h:Transition ?t2 rdf:type h:Transition ?t3 rdf:type h:Xor-split ?t4 rdf:type h:Xor-join ?t1 h:coexistence ?t2 ?t2 h:concurrence ?t1 ?t3 h:connectsPlace/h:connectsTrans ?t1 ?t3 h:connectsPlace/h:connectsTrans ?t2 ?t1 h:connectsPlace/h:connectsTrans ?t4 ?t2 h:connectsPlace/h:connectsTrans ?t4 FILTER (?t1!=?t2) }

Conclusion

This paper presents a formal method for describing semantic constraints that are used to generate workflow processes. First, we propose a formal definition of semantic constraints. Then we describe an algorithm for detecting redundant and conflicting semantic constraints. To integrate the domain knowledge used for annotating the process elements, we develop a semantic conformance-oriented ontology. This ontology is then matched with the CPN Ontology (a representation of CPNs with OWL DL). The mapping is to enable workflow processes which can be verified at the semantic level and also syntactic level. Furthermore, we demonstrate that the SPARQL query language is able to check the correctness of concrete workflow processes represented in RDF syntax. This ensures error-free workflow processes at build-time.

We know that verifying workflow processes at build-time is not enough to guarantee workflows can be executed correctly. The correctness of workflow execution must also be checked. Therefore, in future work, we plan to develop a run-time environment for validating concrete workflows.

  Fig. 1: CPN ontology expressed in a description logic

Table 1 : 1 )Commutativity ( 1 )

 111 Algebra properties of the order parameterName ExpressionAssociation (1) (T1 concurrence T2) concurrence T3 = T1 concurrence (T2 concurrence T3) (2) (T1 notSpecif ied T2) notSpecif ied T3 = T1 notSpecif ied (T2 notSpecif ied T3) Symmetrization (1)T1 bef ore T2 = T2 af ter T1 Transitivity (T1 bef ore T2, T2 bef ore T3 → T1 bef ore T3(2) T1 af ter T2, T2 af ter T3 → T1 af ter T3 (3) T1 concurrence T2, T2 concurrence T3 → T1 concurrence T3 (4)T1 concurrence T2, T1 bef ore T3 → T2 bef ore T3 (5)T1 concurrence T2, T1 af ter T3 → T2 af ter T3 T1 concurrence T2 = T2 concurrence T1 (2)T1 notSpecif ied T2 = T2 notSpecif ied T1

Fig. 2 :

 2 Fig. 2: Algorithm for validating the semantic constraint set

Fig. 3 :

 3 Fig. 3: An example of ontology mapping (excerpt)

The prefix is assumed as: P REF IXh :< http : //www.semanticweb.org/CP N W F # >


Esma Elghoul

Anne Verroust-Blondet

Mohamed Chaouch

A Segmentation Transfer

Keywords: segmentation transfer, 3D alignment, Random walks, graph partitioning

  L'archive ouverte pluridisciplinaire

INTRODUCTION

Mesh segmentation partitions the surface into a set of patches under some criteria. Comparative studies and surveys on segmentation techniques [START_REF] Attene | Mesh segmentation -a comparative study[END_REF][START_REF] Shamir | A survey on mesh segmentation techniques[END_REF][START_REF] Chen | A benchmark for 3D mesh segmentation[END_REF][START_REF] Benhabiles | A framework for the objective evaluation of segmentation algorithms using a ground-truth of human segmented 3D-models[END_REF] clearly distinguish between geometric and semantic-oriented approaches. We are interested here in retaining the semantic information during the segmentation. Our aim is to address the challenging task of automatically identifying the semantically meaningful parts of a 3D model, which can be hard to achieve when only the shape geometry is considered. We propose a novel segmentation transfer approach for rigid models. The user provides the desired semantic information by segmenting one model into meaningful parts. Then, given this model as an example, a similar segmentation is carried out on each model of the same class.

Achieving meaningful segmentations of single shapes by exploring geometric properties of the mesh is in continuous progress. Recent works include the use of heat walk [START_REF] Benjamin | Heat walk: robust salient segmentation of non-rigid shapes[END_REF], minimum slice perimeter [START_REF] Ho | Volume based mesh segmentation[END_REF] and intrinsic primitive decomposition [START_REF] Solomon | Discovery of intrinsic primitives on triangle meshes[END_REF]. To overcome the limitations related to the low-level geometric segmentations of single shapes, researches have turned to partitioning the surfaces of a family of models in a similar way [11-14, 20, 22, 24, 26, 27]. Their goal may be slightly different from ours, as in most cases it is restricted to obtaining consistent mesh partitions. In [START_REF] Kalogerakis | Learning 3D Mesh Segmentation and Labeling[END_REF][START_REF] Luo | Co-segmentation of 3D shapes via multi-view spectral clustering[END_REF][START_REF] Meng | Unsupervised co-segmentation for 3d shapes using iterative multilabel optimization[END_REF][START_REF] Shapira | Consistent mesh partitioning and skeletonisation using the shape diameter function[END_REF][START_REF] Sidi | Unsupervised co-segmentation of a set of shapes via descriptor-space spectral clustering[END_REF] the meshes are divided into parts that may be non-connected (group the four legs of chairs in one region of the surface, for example), which is not what we want to achieve. The unsupervised technique of Huang et al. [START_REF] Huang | Joint shape segmentation with linear programming[END_REF] jointly segment shapes using linear programming. This approach works well for non-rigid models as it is robust to shape variations but it does not guarantee a consistent segmentation of an entire set. Likewise, the skeleton based approaches of [START_REF] Elghoul | A Segmentation Transfer Method for Artic lated Models[END_REF][START_REF] Wong | A Skeleton-Based Approach for Consistent Segmentation Transfer[END_REF] work better on articulated models as they map a segmentation of a source mesh to a target mesh based on the skeleton correspondence between meshes. On the other hand, the co-segmentation method of [START_REF] Golovinskiy | Consistent segmentation of 3D models[END_REF] is extended to a technique that transfers a segmentation from an example to a set of models. They base their approach on a rigid alignment of shapes and resolve a graph clustering problem in order to compute an unsupervised co-segmentation of a set of shapes. We differ from their work in that we perform a model-to-model segmentation that is rapid and parameter-free.

2

Our approach is based on two key hypotheses.

[H1] First we assume that the example segmentation decomposes the model into meaningful parts that could be identically produced by a random walk segmentation algorithm [START_REF] Lai | Rapid and effective segmentation of 3D models using random walks[END_REF], i.e., these parts could have been computed from a set of pseudo seeds appropriately chosen on the 3D mesh. The choice of the random walk algorithm was motivated by the evaluation results of [START_REF] Chen | A benchmark for 3D mesh segmentation[END_REF], which show that the random walk method outperforms the K-means approach [START_REF] Shlafman | Metamorphosis of polyhedral surfaces using decomposition[END_REF] in producing close-to-human segmentations.

[H2] If we focus our attention on rigid models, we can notice that the models belonging to the same class can be consistently aligned in order to obtain a similar organization of their meaningful parts. For example, any chair has a natural decomposition into the following parts: a "back", a "seat" and its "legs". These parts are respectively located at the top, in the middle and at the bottom, when the chair is in an upright position. Moreover, when two chairs are aligned together, the locations of their corresponding parts may differ only by a small local translation, a local rotation or difference in size.

As our objective is to reproduce the desired segmentation on the target model, a flexible segmentation process is necessary. Thus, we develop a derived approach from the random walk segmentation method [START_REF] Lai | Rapid and effective segmentation of 3D models using random walks[END_REF] and transform the problem of segmentation transfer into a problem of locating seed faces on the target model, given the pre-segmented example model. To perform this localization we introduce a method that aligns each model of the same class w.r.t. the example model.

METHOD OVERVIEW

In what follows, will denote the segmented model given as example, with

1 .. its N segments, C its class of models and any model of C. The segments that will be computed for are denoted by 1 .. , where is associated with the segment . All the models are triangulated 2-manifold meshes.

Our segmentation transfer method consists of the following steps, which are summarized in Figure 1: -First of all, each mesh of C is aligned with in such a way that the distances between the main parts of and are minimized.

-In a second stage, a rough localization of pseudo seeds and a seed placement strategy on is performed. In order to avoid some errors related to the model meshing, several seeds per segments are introduced. The basic random walk algorithm [START_REF] Lai | Rapid and effective segmentation of 3D models using random walks[END_REF], which computes the resulting segmentation of , has been extended for this purpose.

Our contributions are the following: • A straightforward method to align one object to another from the same class is presented. The method associates the functional parts of the two 3D models.

• A robust and automatic seed localization algorithm is described. The set of localized seeds, when used as input to the random walk method, results in a meaningful segmentation of the target model. In addition, this algorithm yields the correct matching of the computed segments with the example model segments.

• An extension of the random walk method accepting more than one seed per segment as input is proposed. Consequent improvements are studied. In particular, we show that it resolves many problems due to the model shape and meshing.

• An original boundary smoothing process constrained by the adjacencies of the segments of . The organization of this paper is as follows: Section 3 describes the multi-seed random walk algorithm used in the second step; Section 4 details the three steps of our alignment process; Section 5 presents the seed placement strategy and the segmentation of the target model; improvements achieved by the multi-seed per segment approach and segmentation transfer results are presented in Section 6.

MULTI-SEED RANDOM WALK SEGMENTATION METHOD

The random walk mesh segmentation method introduced in [START_REF] Lai | Rapid and effective segmentation of 3D models using random walks[END_REF] builds segmentations of any 2-manifold triangulated model M. It splits M into N meaningful pieces using N faces 1 ... of M given as seeds. The segmentation is computed by assigning a value i, i = 1, ..,N to each non-seed face , l = 1, ..,m of M, where i is the index of the seed face that has the highest probability ( ) of being reached first by a random walk from on the dual graph of M, i.e., ( )> ( ) for ≠ . Probabilities introduced in [START_REF] Lai | Rapid and effective segmentation of 3D models using random walks[END_REF] lead to the creation of segment boundaries on edges of high negative curvature and ensure that each segment is a contiguous region of the surface. They satisfy:

� ( ) = ∑ , � , � 3 =1 , = 1, … , ( ) = 1 ( ) = 0 when ≠ (1)
where , , j =1..3 are the three faces adjacent to and , are crossing probabilities computed following [START_REF] Lai | Rapid and effective segmentation of 3D models using random walks[END_REF]:

, = � , � �- � , , � ���� � (2)
with such that ,1 + ,2 + ,3 = 1, � , � is the length of the edge common to and , , and is based on the dihedral angle measure between faces and , : � , , � = �1cos �ℎ� , , ���

gives priority to the concave edges: = 1 for concave edges and = 0.1 for convex edges.

is normalized by the average over all edges ��� .

Let be the vector of the m probabilities ( ), for i = 1, .., N. As explained in [START_REF] Lai | Rapid and effective segmentation of 3D models using random walks[END_REF], the problem can be written in matrix form through N independent linear systems:

× = (4)
Each row of × contains at most four non-zero values and has at most three non-zero values, corresponding to the three faces adjacent to the seed face . The N linear systems form a sparse system, which makes the fast computation of the ( ) possible and allows the segmentation of M to be done within a reasonable time. This overall scheme is extended here to accept multiple seeds per segment. Its use for segmentation transfer will be discussed later. Consider the case of doubling the number of seed faces to obtain the same number of segments N in the final result. We start by assigning the same index i to two different seed faces 1 and 2 for each i = 1,2, ..,N. While the number of non-seed faces is reduced by N (m′ = m -N), the number of random walk probabilities to be computed for a non seed face stays unchanged and equals N. In fact, instead of computing the probability that a random walk starting at first reaches one seed face from the set provided, we compute the probability that this random walk first reaches any of the two seed faces 1 and 2 to decide if belongs to the region indexed by i. The probabilities of seed faces are now defined as:

� � � = 1 ∈ {1,2} � � = 0 ∈ {1,2} ≠ (5)
A slight modification to the linear system of Equation ( 4) enables us to describe the multi-seed approach by N linear systems of the form:

′×′ = ′ (6)
Note that the size of ′×′ is inferior here and that ′×′ always has four non-zero values by row at most. The number of zeros also decreases in ′ because ′ can contain up to six non-zero values corresponding to the faces adjacent to 1 or to 2 .

The process can be adapted to hold an arbitrary number of seed faces per segment when necessary. Nevertheless, as the complexity of a sparse system is also proportional to the number of non-zero elements, the overall number of seeds should be limited to avoid a significant slow-down of the segmentation process. Moreover, particular attention should be paid to the placement of the additional seeds. It is indeed not guaranteed that each region produced by the multi-seed segmentation process is connected. A strategy for the placement of two seeds on a region surface is described in Section 5.2.

ALIGNMENT PROCESS

The input to our algorithm is a pair of arbitrary oriented 3D meshes, and , belonging to the same class C of models and representing the example and the target models respectively. The alignment process is performed in three steps.

We first calculate three orthogonal alignment axes, following [START_REF] Chaouch | Alignment of 3D models[END_REF], for each model: this method computes three axes that consistently align the 3D objects within the same semantic class of models and obtains good results on rigid models. These axes are given in arbitrary order and orientation. Thus, for each model, 48 coordinate systems can be built by performing permutations and inversions of the axes. This number can be reduced to 24 if we consider only direct orthonormal systems. The second step consists in fixing the orientations and the order of the alignment axes. To avoid comparing the 3D meshes, we normalize the models to their axis aligned unit cubes and use these cube faces, considering that the two models are correctly aligned when the silhouette images of their projections on the cube faces are similar. For each model, the silhouette images on the cube faces correspond to, at most, three different shapes, up to a rotation (a quarter, half or three quarter turn) and/or a flip. In order to compare the appropriate faces, we choose a direct orthonormal reference system(, , , ), where �����⃗ = �����⃗ ˄ �����⃗ and compute the projections of on the three faces orthogonal to �����⃗ , �����⃗ and �����⃗ (see Figure 2). From the canonical unit cube of , we compute eight sets of three silhouette images corresponding to the projections of on the faces associated to the eight candidate orthonormal systems (, , , ) , (, , ′, ′),(, , , ′ ),(, , ′, ), (, ′, , ′) , (, ′, ′, ) , (, ′, , ) and (, ′, ′, ). Each set of three silhouette images is associated to three triplets obtained by a circular permutation of the oriented axes, i.e. (, , , ), (, , , ) and (, , , ) for the first set of images in Figure 2. Then, 24 triplets of silhouette images corresponding to the 24 candidate reference systems for are compared with the triplets of silhouette images built from . The contours of the silhouettes are extracted and a rigid ICP algorithm compares the fixed alignment provided by the three contour images of with the 24 triplets of contour images of . The triplet of contours that has the minimum ICP error defines the ordering and the orientation of the axes that best align to . At the end of this stage, and are aligned together.

A closer alignment of w.r.t. is needed in order to establish correct matchings between the segments of and parts of . This is done during the last step of the alignment process. Our goal here is different from [START_REF] Kazhdan | An approximate and efficient method for optimal rotation alignment of 3D models[END_REF][START_REF] Martinek | Optimal rotation alignment of 3D objects using a GPU-based similarity function[END_REF] where the purpose is to find the best rotation to align globally two models together. As we want to align the main parts of and , this step may involve both translations and rotations: our refinement consists in applying to a rigid transformation computed through a global 3D ICP algorithm [START_REF] Besl | A method for registration of 3-D shapes[END_REF] performed on and together. Since the two models are already globally aligned, the use of such an approach is suitable. At the end of this process, the main parts of and are accurately aligned and the two models are defined in a common coordinate system R.

One should note that this alignment process could have been replaced by the extrinsic alignment of Kim et al. (step 3a of [START_REF] Kim | Exploring collections of 3D models using fuzzy correspondences[END_REF]): it would generally give similar alignment results and the two methods have a similar complexity. Nevertheless, our two first steps compute the reference frames that align consistently a set of rigid models belonging to a same class of models and can be used alone for this purpose.

SEED LOCALIZATION STRATEGY AND SEGMENTATION OF M T

We now need to define an appropriate set of seed faces on in order to use the random walk approach to transfer the segmentation of on . As the segments of and the parts of corresponding to them are close in space, the computation of the seed faces on uses a rough localization of seed faces associated to the segments of . The cuts obtained by the random walk segmentation are refined in a last step using a graph cut algorithm.

Localization of M E Pseudo Seeds

The segmentation given for provides a decomposition of into meaningful parts. Thus, using hypothesis [H1], a similar segmentation can be performed on by the random walk method, with an appropriate set of seed faces of . As we don't want to compute them here, we denote them pseudo seeds. The random walk algorithm is robust with respect to the location of the seeds and creates segment boundaries around edges of high negative curvature. However we should avoid estimating the pseudo seed locations near the segment borders, which are often of high concavity. The central region of the segment is therefore a more appropriate position for pseudo seeds. Let be the centroid, with respect to Euclidean distance, of the subpart of corresponding to segment . The point gives a rough estimation of the pseudo seed location of : the set of mesh faces belonging to and close to should contain the pseudo seed of .

Seed Placement Strategy on M T

In order to transfer the segmentation of the model onto the unsegmented model , one intuitive approach is to select the face of closest to the centroid of as the seed face for the region corresponding to the segment and use random walks to segment . Although seed-based algorithms are traditionally initialized with one seed per surface region, such a mono-seed approach may fail to detect boundaries that are not clearly defined. Moreover, the random walk method may lead to an incorrect segment if the seed face belongs to a concave region. Thus we extend the initialization of the segmentation algorithm by setting a couple of seeds per segment instead of a singleton, as input to the random walk algorithm. The first seed face 1 of is assigned to the face of that is closest to the centroid of , where ( , ) is the Euclidean distance between and the centroid of a face f of the polygonal mesh of : splits the surface region in two parts separating the closed boundaries across two different sides which makes it more suitable than P i,2 for the placement of 2 , thus P' i is parallel to P i,1 .

1 = min ∈ �( , )� (7)
While the localization of the first seed face is straightforward, the selection of the second one requires more attention. An incorrect selection of the second seed may directly affect the segment connectivity property, ensured a priori by the use of a single seed per segment. To overcome this problem, we use local principal planes computed from . to guide the placement of the second seed face. These planes are defined through a continuous principle component analysis (CPCA) [START_REF] Vranic | 3D model retrieval[END_REF] performed on the example segment . In fact, the CPCA appears to be more complete and the most stable of all the PCA-approaches we have studied. It computes three orthogonal eigenvectors of the covariance matrix for the surface part of , working with sums of integrals over mesh triangles instead of sums over vertices [START_REF] Vranic | 3D model retrieval[END_REF]. The local alignment of is thus provided through three local principal vectors ,1 ������⃗, ,2 ������⃗ and ,3 ������⃗. Note that the example segment and its corresponding target segment on are assumed to have almost the same pose in the global model alignment. Thus, we expect the local principal vectors of to be close to those computed for . The local principal plane used for the localization of the second seed 2 of is denoted by P i and is the one of the 3 candidate planes (i) which contains , (ii) normal to one of the vec- tors , ������⃗ (P i,k = ( , , ������⃗ ) with k = 1..3) and (iii) not intersecting the set of edges composing the boundaries of , if it exists. When more than one plane satisfies (i), (ii) and (iii), we give priority to the one which splits in two parts separating the distinct closed boundaries (P i,1 in Figure 3(b)). When none of the three planes satisfies the three given conditions, we keep only one seed for this segment.

The role of P i is to guide the localization of the second seed 2 to ensure that it will remain near the central zone of the target segment region and far from its boundaries. The second seed face 2 is chosen from the faces of that intersect the plane P' i , parallel to P i and containing the centroid of 1 as follows: an oriented half line D i from the centroid of the first seed face 1 , directed by the inward-pointing normal to

1 is computed. This half line is projected on P' i into an oriented half line D′ i . The second seed 2 corresponds to the face of that first intersects D′ i (see Figure 3). The first intersection of D′ i with encounters a face that normally belongs to the same part of the model, but opposite 1 . Setting a couple of seeds per segment implies that we assign the same segment label to two seed faces in the initialization stage. Thus we use the multi-seed random walk segmentation method described in Section 3 to perform the segmentation of , with 2N seed faces 1 and 2 , 1 ≤ i ≤ N. Sometimes the boundaries of the computed segments may need a refinement step in order to adhere to the natural contours of the shape parts. Thus we introduced a second partitioning algorithm that uses the alpha-beta swap (α-β swap) algorithm for graph cuts of Boykov et al. [START_REF] Boykov | Fast approximate energy minimization via graph cuts[END_REF]. In fact, this method improves our previous approach in two ways: it smooths the segments boundaries and it also enforces the boundary creation between segments whose corresponding segments in M E are adjacent. The algorithm minimizes an energy function E(L) over the mesh M T , taking into account the probabilities computed by the random walk algorithm, the boundaries between adjacent segments of M T and the adjacency graph built from the segments of M E . The new labeling L, computed with the α-β swap algorithm, assigns a segment label L f ϵ {1,..,N} to each face f of M T such that all the cuts between these newly computed segments are refined. Let N a be the set of pairs (f, g) of adjacent faces of M T . E(L) is composed of a data energy E d (L) and a smoothness energy E s (L), E(L) =λ E d (L)+ E s (L) with:

Boundary smoothing

() = ∑ -� () + �, () = ∑ (, ). ( , ) (,) (8)
where λ is a weighting parameter (here λ = 0.2 to give higher priority to E s (L)), the values () are derived from the probabilities computed by the random walk algorithm and the capacity function cap(f, g) is defined on the arc that links adjacent faces f and g as in [START_REF] Katz | Mesh segmentation using feature point and core extraction[END_REF] to enforce the creation of segment boundaries through concave short edges. The interaction potential is a semi-metric used to penalize pairs of different labels (L f , L g ) = (j, k),with j ≠ k:

(, ) = � 1 � , � = � , � 1 > 1 � , � = 1 � , � = 0 2 < 1 � , � = 0 � , � = 1 (9)
where A(S, S') = 1 when the two segments S and S' are distinct and adjacent, and A(S, S') = 0 in the other cases. If j=k, then V(j,k) = 0. Note that the value u 1 heavily penalizes the cut between segments that are adjacent in the random walk segmentation S T while their corresponding segments are not adjacent in M E and the value u 2 favors the boundary creation of a cut between disconnected segments of S T corresponding to adjacent segment in M E . We obtained good segmentation results on the evaluated model sets with u 1 = 5 and u 2 = 1/5. This process improves the quality of the boundaries and rectifies, whenever possible, incoherent segment adjacencies as illustrated in Figure 4.

EXPERIMENTS AND RESULTS

We evaluated our example-based segmentation on man-made objects extracted from two datasets. The method was tested on the whole sets of irons and goblets from the COSEG Dataset [START_REF] Wang | Active co-analysis of a set of shapes[END_REF] by using each provided ground-truth segmentation as an example for all the class meshes. We also chose three rigid categories (chairs, airplanes and tables) from the Princeton Segmentation Benchmark [START_REF] Chen | A benchmark for 3D mesh segmentation[END_REF]. In each category, the human segmentations are not consistent and present slightly different styles and numbers of segments. Thus, we fixed the number of segments and the style that is the most typical in the category. Then for each model, we selected one ground-truth segmentation from the benchmark that possesses the chosen style and number of segments. If that style did not exist in the data provided, we created it manually for the model. We also adjusted the segment indexes manually to obtain the segmentation consistency needed for our tests. When applying the multi-seed and the mono-seed approaches, each model took the role of the example once for all the models of its class. Figure 7 show some segmentation transfer results using our approach for different classes of models. For the chair sets, different example models are shown with various styles of exemplar segmentation. mono-seed, double-seed without planes P i and double-seed using planes P i ; (e) and (f) left: , right: im- provements produced on the multi-seed segmentation of in comparison to its mono-seed segmentation.

The Recognition Rate scores, as defined in [START_REF] Kalogerakis | Learning 3D Mesh Segmentation and Labeling[END_REF], are reported for the different categories in Figure 6. The measure gives the percentage of identically labeled surface area of the mesh across two segmentations of the same model: the segmentation created by transfer and the ground-truth. The histogram shows that the multi-seed approach outperforms the mono-seed approach on all the test data. Table 1 reports segmentation errors using the evaluation metrics proposed in [START_REF] Chen | A benchmark for 3D mesh segmentation[END_REF]. The Cut Discrepancy considers boundary matching by measuring the distance between matching cuts, whereas the Rand Index compares pairwise label relationships in two segmentations. Again, the multi-seed segmentation obtains better results than the mono-seed one. Fig. 6. Comparison between the multi-seed approach after boundary smoothing and the mono-seed approach through Recognition Rate scores evaluated for different classes of rigid 3D models.

Multi-seed VS mono-seed results. Let us first comment on the examples presented in Figure 5.

For models (b) and (e), the geometric information about concavities varies considerably and can be very poor. This leads to incorrect propagation of the segmentation if a single seed defines the segment. For the wings of the airplane in (b), segmented by the model in (a) with a mono-seed approach, the seed locations are unfavorable and only the side near strong concavities is detected.

The other flat side is mixed up with the neighboring central segment with which the wings share unclear long borders. Positioning opposing seeds near less concave borders of the wings considerably improves the segmentation result. It also fixes the matchings between the segmented parts of the target and the example models. Other cases of better border detection with the double-seed approach are shown for the "back" segment of the chair in (e) and the upper segment of the goblet in (f). The airplane in (c), segmented by the model in (a), shows in its rightmost segmentation how the use of locally computed planes P i helps to guide the positioning of the second seed inside the region surface, compared to the middle segmentation where these planes were not used.

Table 1. Comparison of the mono-seed and the multi-seed created segmentations (with the boundary smoothing process) according to the ground-truth co-segmentation. Chair 6S (resp., Chair 8S) corresponds to a 6 segment (resp., 8 segment) ground-truth for chairs. Comparison to related work. A comparison to individual segmentation methods is provided in Figure The Rand Index is computed this time against all human generated segmentations of the Princeton Benchmark [START_REF] Chen | A benchmark for 3D mesh segmentation[END_REF] for the classes concerned. We show the scores of the random walk method of Lai et al. [START_REF] Lai | Rapid and effective segmentation of 3D models using random walks[END_REF], the shape diameter [START_REF] Shapira | Consistent mesh partitioning and skeletonisation using the shape diameter function[END_REF] and the randomized cuts [START_REF] Golovinskiy | Randomized cuts for 3D mesh analysis[END_REF], the leading method on the benchmark [START_REF] Chen | A benchmark for 3D mesh segmentation[END_REF]. We achieve better scores than all the segmentations evaluated in [START_REF] Chen | A benchmark for 3D mesh segmentation[END_REF]. We can deduce that the use of an example model to create consistent segmentations improves the partitioning of the shape and consequently the individual segmentation result. Moreover, on rigid models our Rand Index scores are similar to the supervised approach of Kalogerakis et al. [START_REF] Kalogerakis | Learning 3D Mesh Segmentation and Labeling[END_REF] with 3 training models and to the unsupervised approach of Huang et al. [START_REF] Huang | Joint shape segmentation with linear programming[END_REF] in the JointAll condition in which they obtained their better scores. To perform a direct comparison with the supervised approach of Kalogerakis et al. [START_REF] Kalogerakis | Learning 3D Mesh Segmentation and Labeling[END_REF], we associated the same labels to all similar part types in our example segmentations (i.e. one label for the legs of the chair models) and performed a segmentation transfer for three classes of the benchmark [START_REF] Chen | A benchmark for 3D mesh segmentation[END_REF] (20 segmentations for each model). Table 2 shows the Recognition Rate scores obtained by our approach with these exemplar models and those obtained by the learning method of Kalogerakis et al. [START_REF] Kalogerakis | Learning 3D Mesh Segmentation and Labeling[END_REF], with three models per training set. The performances of the two approaches on these classes of models are very close. Note that in [START_REF] Kalogerakis | Learning 3D Mesh Segmentation and Labeling[END_REF], the more training models are added, the better the results are. Therefore, such supervised approach would be advantageous for large sets of shapes and less adapted to smaller sets, for which our method proved to be effective and more efficient. Let us examine the segmentation results on the chairs in Figure 7. The segmented example of the second row corresponds to one of the four chairs belonging to the learniing set of Kalogerakis' method in Figure 3 of [START_REF] Kalogerakis | Learning 3D Mesh Segmentation and Labeling[END_REF]. We see that the segments created by our approach on the same target models resemble those of Kalogerakis et al. (chairs (a) in Figure 3 of [START_REF] Kalogerakis | Learning 3D Mesh Segmentation and Labeling[END_REF]) and are visually better than those obtained by Golowinskiy and Funkhouser's method [START_REF] Golovinskiy | Consistent segmentation of 3D models[END_REF] (chairs (c) in Figure 3 of [START_REF] Kalogerakis | Learning 3D Mesh Segmentation and Labeling[END_REF]), where the boundaries are not always correctly detected.

Rand Index Cut Discrepancy

MultiS

The last row of Figure 7 shows that our method can work on sets of objects that have very similar shapes and parts, as airplanes and birds, even though they do not belong to the same class of models.

Validation of [H1] hypothesis. We consider here the segmentation built on each model using its own ground truth segmentation. The average Recognition Rate score obtained over the three evaluated rigid classes (60 models) is 96.45%. This high score confirms that a random walk segmentation algorithm can compute segmentations similar to the meaningful exemplar ones, as assumed in [H1] in section 1. This result also validates our seed placement strategy. Fig. 8. Rand Index scores. MultiS corresponds to our method. Ex, SB3 and JointAll correspond respectively to our exemplar pre-segmented models, the supervised approach of Kalogerakis et al. [START_REF] Kalogerakis | Learning 3D Mesh Segmentation and Labeling[END_REF] with 3 training models and the unsupervised approach of Huang et al. [START_REF] Huang | Joint shape segmentation with linear programming[END_REF]. Lower values of the Rand Index indicate better similarity to human-generated ground truth.

Performance. It was previously demonstrated in [START_REF] Chen | A benchmark for 3D mesh segmentation[END_REF] and [START_REF] Lai | Rapid and effective segmentation of 3D models using random walks[END_REF] that the interactive response time is the greatest benefit of the random walk segmentation method. As for our approach, the whole process usually took less than one minute for a couple of arbitrary oriented input models composed of less than 20K triangles. The experiments were carried out on an Intel Core i7 2.8GHz PC. The running time of the alignment step took a few seconds, equivalently to the second and the last steps of computing a consistent segmentation. The approximate complexity of the linear sparse system is O(m′N), with m′ the number of non-seed faces and N the number of segments. We used a c++ iterative solver for sparse systems of linear equations to compute the random walk probabilities. For the α-β swap algorithm, we used the implementation provided by [START_REF] Boykov | Fast approximate energy minimization via graph cuts[END_REF][START_REF] Chen | A benchmark for 3D mesh segmentation[END_REF][START_REF] Boykov | An Experimental Comparison of Min-Cut/Max-Flow Algorithms for Energy Minimization in Vision[END_REF]. Default values of control parameters involved in probability computation, convergence error and the α-β swap algorithm were set once for all the experiments. We conclude that our approach is parameter-free as it depends only on the exemplar model, and it achieves the best running time compared with existing approaches, e.g., the required off-line training process on pre-labeled models in [START_REF] Kalogerakis | Learning 3D Mesh Segmentation and Labeling[END_REF] may take hours and their on-line segmentation of one mesh may take some minutes.

Extension of the method. In order to make segmentation transfer more flexible, a number of interactive tools are proposed to the user: he can insert or delete segments and design the style of the desired exemplar segmentation by combining existing styles. For instance, it is not possible to create a meaningful partitioning of the four-legged chair on the left of Figure 9 using the one-legged example chair alone. Also it is useless to have this chair's "back" decomposed into three regions as in the middle four-legged model. A user-defined combination between the two exemplar segmentations is possible as the overlapping indexes correspond to semantically similar parts (e.g., the green "seat" for these chairs). This leads to a more consistent segmentation for the target model, as shown on the right of Figure 9.

Limitations. As our method is based on alignment hypothesis, the use of a good alignment process is of great importance in order to get a good initial seeding of the target regions. Moreover, when a class presents large shape variability, such as the vase class of Figure 7, it may be insufficient to use only one model to consistently segment the others.

On the other hand, our method, in its automatic version, always computes the same number of segments as in the example and doesn't detect outliers segments on models (see the rightmost table segmentations in Figure 7 for example). To deal with these issues, we can use the symmetries of the input shapes, since the design of man-made objects is commonly based on symmetry attributes. A possible approach would be to capture the symmetries of the example and target models in order to compare them, after processing the alignment step and before positioning seeds. These symmetries can be reflective, rotational or translational along a direction. Also they can be examined locally or globally. Inconsistent segments can be avoided by detecting their absence on and eliminating their corresponding seeds. Likewise, extra parts of can be identified and additional seeds can be created for them by symmetry. We also believe that such an approach may dramatically reduce errors due to intra-class geometric variabilities. This method is not adapted to non-rigid models as our hypothesis [H2] cannot always be satisfied: the objects may present a large variability in shape inside a same class of models. Thus the skeleton-based approaches [START_REF] Elghoul | A Segmentation Transfer Method for Artic lated Models[END_REF][START_REF] Wong | A Skeleton-Based Approach for Consistent Segmentation Transfer[END_REF] are more appropriate in this case.

CONCLUSION

We have presented a fast and efficient method that takes a segmented rigid model and transfers meaningful and consistent segmentations on unsegmented models from the same class. The algorithm produces individual segmentations that are more meaningful and improves upon techniques that segment objects separately. In addition, as the approach is fairly fast, it is particularly well-suited to addressing the needs of interactive applications. Experiments conducted on various sets of rigid models showed the effectiveness of our segmentation transfer approach and the soundness of our two key hypotheses [H1] and [H2] presented in section 1.

Fig. 1 .

 1 Fig. 1. The whole segmentation process. (a): the segmented example model ; (b): the target model ; (c), (d) and (e): the three steps of the alignment process; (f): localization of pseudo seeds on ; (g): multiple seeds on and (h): resulting segmentation on .

Fig. 2 .

 2 Fig. 2. Top to bottom: 8 triplets of silhouette images built from the projection of on the unit cube faces, with their corresponding candidate coordinate systems and, in the last row, the silhouettes built from the projection of on the three faces orthogonal to �����⃗ , �����⃗ and �����⃗ . Here the triplet (, , , ) aligns the best and .

Fig. 3 .

 3 Fig. 3. Seed placement strategy on : (a) The plane P i,2 is computed using . In , D′ i is the projection

Fig. 4 .

 4 Fig. 4. Boundary smoothing: (a) two example models, (b) their two respective target segmentations using the multi-seed random walk algorithm and (c) boundary smoothing and correction of segment adjacency graph using the graph cut algorithm with non uniform interaction potentials.

Fig. 5 .

 5 Fig. 5. Improvements of segmentation transfer results through the multi-seed approach (before boundary smoothing): (a) the airplane model used to segment the models in (b), (c) and (d); (b) mono-seed segmentation of a target airplane, computed positions of seeds are shown on two opposing views of the model; (d) segmentation transfer using couples of seeds and better detection of the wing borders; (c) from left to right :

Fig. 7 .

 7 Fig. 7. Segmentation by transfer presented for a variety of example models. is always on the left of the line and segmented target models are on the right. Our method produces good results, even when changing the segmentation styles and as shown for the sets of chairs.

Fig. 9 .

 9 Fig. 9. A combined use of two different style exemplar segmentations (middle) to obtain the desired result on the target model (right).

Table 2 .

 2 Recognition Rate scores on 3 classes. Comparison with the supervised approach of Kalogerakis et al.: SB3 corresponds to the scores of Table 1 in [14] with 3 models used as training set.

			Recognition Rate
		Chair Airplane Table Average
	SB3 [14]	97.1	91.2	99.0	95.7
	MultiS	96.2	92.8	91.7	93.5