Quoc-Viet Dang
email: quocviet.dang@enseeiht.fr

Sandrine Mouysset
email: sandrine.mouysset@irit.fr

Géraldine Morin
email: geraldine.morin@enseeiht.fr

Symmetry-Based Alignment for 3D Model Retrieval

This paper presents an original method for aligning 3D shapes modeled as NURBS based B-rep models, exploiting partial symmetries of the shape. Aligning 3D shapes is an important pre-processing step in 3D shape retrieval and indexation: a reliable alignment of the shapes is necessary. Given a 3D model, three canonical planes define the normalized pose. We characterize the first canonical plane by an efficient computation of the dominant partial symmetry, using an efficient face matching approach. An algorithm based on minimizing the projection area determines the two relative remaining planes. To evaluate the robustness and the effectiveness of the alignment, this technique is applied to 3D shape retrieval within a repository of NURBS based B-Rep models.

I. INTRODUCTION

With the development of 3D applications in multiple fields of science, the number of 3D objects is growing rapidly. As a consequence, more and more 3D objects are available for sharing. Reusing models is common way to increase the efficiency of the product development process. Thus, 3D objects repositories require efficient and robust techniques to support the 3D object matching and retrieval. 3D shape indexing takes the three consecutive steps: (1) object normalization, (2) feature extraction and (3) object comparison [START_REF] Tedjokusumo | Normalization and Alignment of 3D Objects Based on Bilateral Symmetry Planes[END_REF]. The first step is very important as its quality strongly affects the final result. In fact, 3D objects are generated in arbitrary orientations, scales and positions. Without normalization, it is not feasible to get a reliable 3D objects comparison. Generally, an alignment process consists in finding an orthogonal frame, i.e, a canonical frame relative to the object. Classically, a Principal Component Analysis (PCA) is used for aligning mesh models, e.g. Vranić [START_REF] Vranić | 3D model retrieval[END_REF] aligns models along the three principal axes. The PCA is fairly simple and efficient, but it is sensitive to points distributions. As alignment techniques are derived for mesh models, applying them to parametric models requires a pre-processing sampling step in which case the sampling is a saddle issue. Further techniques, like Continuous PCA or Normal PCA [START_REF] Paquet | Description of shape information for 2-D and 3-D objects[END_REF], [START_REF] Papadakis | Efficient 3D shape matching and retrieval using a concrete radialized spherical projection representation[END_REF] avoid the dependence to sampling. Even though, the principal axes are not always the good references to align models. As shown by the alignment results in Figure 1, the irregular forms of the plane and the cup affect the correctness of principal axes orientations. On these models, the PCA is not a good candidate for 3D models alignment.

In [START_REF] Ferguson | Modeling orientation effects in symmetry detection: The role of visual structure[END_REF], Ferguson et al. show that 2D vertical symmetries corroborates the orientation based on human perception; based on global symmetry of an object, they adjust the alternate frame of reference. In addition, Minovic [START_REF] Minovic | Symmetry identification of a 3-D object represented by octree[END_REF] et al. shows that a plane of symmetry of a 3D body is always perpendicular to one of the principal axis. Thus, symmetry information within a given 3D object can help us identify an associated canonical frame of alignment. Fortunately, similarity within a 3D shape is a common phenomenon [START_REF] Dang | Similarity detection for free-form surfaces[END_REF]. Many objects are composed by similar parts up to a rotation, a translation or a symmetry. Therefore, it is obvious that canonical frame of a 3D model can be extracted from its partial symmetry information. It is the main idea followed by our technique.

In our work, we are interested in parametric surfaces, in particular Non-Uniform Rational B-Spline (NURBS) surfaces. They provide a powerful tool for the academic and industrial communities concerned with the design and analysis of objects [START_REF] Dimas | 3D geometric modelling based on NURBS: a review[END_REF]. Boundary Representations (B-Reps) are industrial standards and NURBS-BReps are widely used in different domains such as molecular chemistry [START_REF] Bajaj | NURBS based B-rep models for macromolecules and their properties[END_REF], 3D geographical information systems [START_REF] Caumon | Constrained Modifications of Non-manifold B-reps[END_REF] and mechanical components design [START_REF] Chu | Similarity assessment of 3D mechanical components for design reuse[END_REF]. We present a novel technique of aligning NURBS-BRep models by determining three canonical planes and a canonical orientation. By detecting the dominant partial symmetry of a given NURBS-BRep model, the symmetry plane is defined as the first canonical plane from which the remaining planes are identified based on an area projection approach. Our contributions are two-fold: we propose a robust algorithm to detect partial symmetries within a NURBS-BRep model, and deduce an alignment of NURBS-BRep models algorithm based on their dominant partial symmetries.

The rest of this article is organized as follows. Section II reviews related works on model alignment and symmetry detection. Section III resumes the basic idea of our alignment method. Section IV and V details the two algorithms of our method. Section VI follows with experimental results in shape retrieval to evaluate the proposed technique.

(a) A plane (b) A cup Fig. 1: PCA based alignment. The canonical frame is defined by three orthogonal planes (blue, green, red), corresponding to the principal axes in descending order. For the plane, the blue plane is deviated due to the plane tail (1a) and for the cup, the handle prevents the green plane from being vertical (1b).

II. RELATED WORK

There exists different approaches for aligning 3D mesh models. These methods can be classified into three categories: PCA-based, Symmetry-based and Projection area-based. As shown in the introduction, PCA has some drawbacks for 3D object alignment. Variants have been developed to improve the accuracy such as Continuous PCA [START_REF] Vranić | 3D model retrieval[END_REF] and Normal PCA [START_REF] Zaharia | Shape-based retrieval of 3D mesh models[END_REF]. Despite some relevant improvements, they are still not reliable for all types of 3D objects [START_REF] Papadakis | Efficient 3D shape matching and retrieval using a concrete radialized spherical projection representation[END_REF]. An alternative technique is to used the Minimum Volume Bounding Box (MBB) [START_REF] Barequet | Efficiently approximating the minimumvolume bounding box of a point set in three dimensions[END_REF] which is less sensitive to the points distribution. But it is only good for objects whose MBB axes are aligned with the bilateral symmetry plane [START_REF] Tedjokusumo | Normalization and Alignment of 3D Objects Based on Bilateral Symmetry Planes[END_REF]. In an other approach, Podolak et al. [START_REF] Podolak | A Planar Reflective Symmetry Transform for 3D Shapes[END_REF] propose a planar-reflective symmetry transform in estimating all possible planes of symmetry from which the normalized coordinate system is extracted. However, they consider only global symmetries (on the entire object) and ignore the partial ones which may also give relevant information for alignment. Chaouch et al. [START_REF] Chaouch | A Novel Method for Alignment of 3D Models[END_REF] estimate the normalized coordinate system by testing the symmetry plane of a given 3D model based on Continuous PCA associated with the local translational invariance properties. Tedjokusumo et al. [START_REF] Tedjokusumo | Normalization and Alignment of 3D Objects Based on Bilateral Symmetry Planes[END_REF] developed an alignment algorithm based on bilateral symmetry plane in association with a 2D PCA. Again, they consider only the symmetry of the whole object and the algorithm fails for non-symmetric models. Recently, a new approach based on the projection area was proposed. Lian et al. [START_REF] Lian | Rectilinearity of 3D meshes[END_REF] use the PCA and a rectilinearity metric to find out sets of candidate axes. The final set is one that minimizes the projected area of silhouettes. Napoléon et al. [START_REF] Napoléon | From 2D silhouettes to 3D object retrieval: contributions and benchmarking[END_REF] define the minimum visual hull to identify the principal axes from a set of candidates brought by a PCA approach. Johan et al. [START_REF] Johan | 3D model alignment based on minimum projection area[END_REF] proposed a method that selects two axes with minimum projection areas but does not rely on the PCA approach. Despite these interesting insights and encouraging results, the proposed algorithms do not consistently provide results coherent with the human perception for all types of objects; semantic information of the objects is missing.

From these works, we can see that considering only global symmetries or the projection areas of 3D models is in general not enough to align all objects. Here, we propose to investigate the use of partial symmetries of 3D models in association with 2D area of the orthographic projection to develop a robust alignment algorithm.

Symmetry detection for 3D meshes is a well known subject with several approaches as geometric hashing, transformation space voting, planar reflective symmetry transform, graph based [START_REF] Mitra | Symmetry in 3D Geometry: Extraction and Applications[END_REF]. For free-form surfaces, Cuillière et al. [START_REF] Cuillière | Automatic comparison and remeshing applied to {CAD} model modification[END_REF] present a method to detect the similarity and the dissimilarity between NURBS-BRep models based on the inertia tensor and the control points net of NURBS surfaces. But they do not estimate the transformation between similar surfaces and they consider only the underlying surface that depends on the parameterization. Thus, they do not identify the symmetric parts within a model. Li [START_REF] Li | Shape Analysis of B-Rep CAD Models to Extract Partial and Global Symmetries[END_REF] also proposes in his thesis an algorithm to detect the symmetry between simple primitive surfaces within a B-Rep model, their approach does not apply to free form. Recently, by exploiting the isometry analysis, Dang et al. [START_REF] Dang | Similarity detection for free-form surfaces[END_REF] introduces a Hough-style algorithm to detect partial similarities within a NURBS-BRep model. Whereas the results are interesting, this algorithm may be time consuming when applied to complex models. Here, we propose a face pairing approach which leads to a more robust and more efficient algorithm. In addition to considering partial symmetries of 3D models, our approach offers a low complexity compared to considering sampling of the parametric model in order to apply mesh models alignment methods.

III. METHOD OVERVIEW

A. Basic Idea

Our method of 3D model alignment aims at aligning NURBS-BRep models in a way consistent with human perception. Given a model, it consists in first aligning with an axis perpendicular to the partial dominant symmetry plane. The remaining axes are identified according to the idea of Projection Area-based alignment [16]- [START_REF] Johan | 3D model alignment based on minimum projection area[END_REF], i.e., the canonical views are ones that contain the minimum 2D area under an orthographic projection of the object. We only need to consider projection plane containing the first axis. The process of our method is divided in two separate algorithms:

• Symmetry detection identifies the dominant symmetry plane (section IV).

• Axes generation estimates the three canonical axes based on orthographic projection (section V).

B. Structure of NURBS based B-Rep Models

In the context of our research, a B-Rep object is composed of multiple faces and a B-Rep model is composed of multiple B-Rep objects. The violin model in Figure 2 is composed of numerous B-Reps objects plotted in different colors (figure 2a). Similarly, the B-Rep object of the violin body (figure 2b) contains multiple faces. A face, as in figure 2c, is a NURBS surface (violet) bounded by some edges (green) and some vertices (red). In other words, a model contains numerous faces. The symmetry detection problem within a B-Rep model is then reduced to the detection of symmetric faces within this model. To ease the notation for the next sections, we denote M = {F i }, i ∈ [0, n F ), the NURBS based B-Rep model that composed of n F faces. Each face is defined by F i = {S i , V i }, where S i is the NURBS surface used by this face and V i = {v i 0 , ..., v i n-1 } is the set of n vertices that bound F i . We call the vertices V i the corners of face F i .

IV. SYMMETRY DETECTION

In this section, we present our algorithm for detecting the similarities within a NURBS-BRep model. Our algorithm does not only identify automatically repeated faces in the model but also estimates the transformation between them. That is, if two patches P i , P j are similar, there exists a transformation T ij such that:

P j = T ij (P i ). (1)
By benefiting from the loop closed form within B-Rep objects, we propose a method for detecting similarity between faces based on the vertices that bound these faces. Moreover, loops in a B-Rep object must not intersect each other to maintain the validity of the trimmed face. Generally, a B-Rep object has an outer loop that may contain embedded inner loops. In our work, we only take into account vertices lying on the outer loop of the B-Rep faces. In addition, as we are interested in symmetries, we can consider isometries such that transformations that preserve the distances are kept. Also, depending on the dimension of the space of fixed points, symmetries may be characterized among isometries. The following sections present the details of our approach.

A. Algorithm overview

Before entering into the algorithm details, let us introduce a definition of similar faces based on their entities objects. Let F i = {S i , V i } and F j = {S j , V j } two different faces with the same number of corners. Definition 4.1: we say that F i and F j are similar up to a transformation T ij iff their corners and their underlying surfaces are similar up to this transformation.

V j = T ij (V i ), S j = T ij (S i ).
(

) 2
From this definition, given a B-Rep model M = {F i }, i ∈ [0, n F ), the algorithm tries to get as many symmetric faces pairs as possible. It is divided in several steps: 1) Faces matching. Couples of faces are matched if there exists an isometry between their corners. Let Λ = {P k } be the set of faces pairs where

P k = {F i k , F j k }.
2) Extracting isometries. For each pair P k , estimate the least squared solution R k and t k so that

V j k = R k * V i k + t k .
3) Selecting symmetries. For each P k , classify the isometry I k corresponding to R k and t k based on their fixed points and keep only P k representing a symmetry. Validate P k on the underlying surfaces to decide whether two corresponding faces are symmetric. Let ∆ = {Q k } be the set of symmetric faces pairs where

Q k = {F i k , F j k , I k }. 4) Extending symmetries. Merge equal symmetries in ∆.
For each group, relevant isometry and similar patch pairs are extracted. To have the final result for each group, single faces intersecting the symmetry plane are also tested.

B. Matching Face Pairs

In this part, we assume that similar parts of the model are partitioned into faces in the same way. However, our similarity detection algorithm does not assume the same parameterization for similar patches. Given two faces F i = {S i , V i } and F j = {S j , V j }, where V i = {v i 0 , . . . , v i n-1 } and V j = {v j 0 , . . . , v j m-1 }. We first map "one-to-one" the corners of V i into the matching corners of V j where an isometric mapping may exist. For almost all cases, similar faces share the same number of corners. However, depending on the software used for creating the model, similar faces may have extra corners in the face loop. First, we only keep corners of the trim surface where the left and right tangent direction are different enough. This filtering allows to consider only relevant corners. Then, if faces still have a different number of corners suppose that n ≤ m. We seek V o = {v o 0 , . . . , v o n-1 } ⊂ V j and the mapping T ij canceling the expression:

n-1 k=0 v i k -v i k+1 -v o n±k[n] -v o n±(k+1)[n] (3)
where • denotes the L 2 -norm of Euclidean distance.

As the mapping between face corners is just a necessary condition, a validation on the surfaces will be performed to identify actual mapping.

C. Extracting isometries

Given two sets V i and V o whose corners are mapped according to equation (3), i.e.

v i 0 → v o 0 , . . . , v i n-1 → v o n-1
, we want to find out the transformation parameters R (rotation) and t (translation) that minimizes the mean squared error of these two point sets:

e 2 (R, t) = 1 n n-1 k=0 v o k -(R * v i k + t) 2 . ( 4
)
For simple cases, we solve the linear system A -→ x = -→ b by using the pseudo inverse, where A and -→ b are matrix and vector composed by ordering coordinates of the two set V i and V o , -→ x is the solution representing the transformation parameters.

But this method fails when the corners of V i and V o are coplanar. Lorusso et al. [START_REF] Lorusso | Estimating 3-D rigid body transformations: a comparison of four major algorithms[END_REF] compare four algorithms to estimate the transformation for this case. From their comparisons, the singular value decomposition (SVD) of a matrix is the most efficient and robust method. Arun et al. [START_REF] Arun | Least Squares Fitting of two 3D Point Sets[END_REF] propose an algorithm based on the SVD of a 3 × 3 matrix, Umeyama [START_REF] Umeyama | Least-squares estimation of transformation parameters between two point patterns[END_REF] refines this algorithm to resolve special cases. We follow the algorithm in [START_REF] Umeyama | Least-squares estimation of transformation parameters between two point patterns[END_REF] to estimate the transformations. Note that, this algorithm estimates a unique direct isometry and/or a unique indirect isometry if the corners number of each set is more than two, i.e. n > 2, and the corners in V i (and V o ) are not colinear. If V i and V o are not coplanar, there exists only one transformation between them. Otherwise, there exists two different transformations: a direct and an indirect one. From (3), the estimated transformations preserve the length and their associated linear parts are orthogonal, they are then the isometries. In short, this step gives at most two isometries that transform V i to V o . Every isometry is defined as:

T ij = R ij t 0 1 . ( 5
)

D. Selecting symmetries

According to [START_REF] Tisseron | Géométries Affine, Projective et Euclidienne[END_REF], [START_REF] Fresnel | Méthodes modernes en géométrie[END_REF], depending on the nature of its fixed points, an isometry T ij can be classified into several classes: translation, rotation, symmetry or combinations of them. We characterize the symmetries as the isometries with a plane of fixed points, in our case, such that the eigenspace of R ij associated with the eigenvalue 1 has dimension 2. Now, the estimated symmetries are only valid for faces pair corners. It requires to validate the corresponding symmetries on the underlying surfaces bounded by these corners. For each surface, the samples are uniformly taken in term of relative distance [START_REF] Dang | Similarity detection for free-form surfaces[END_REF], the distance is defined globally for the actual model. Next, the samples of F i are transformed by applying T ij to see if the transformed points are the same as the samples of F j . There is a challenge in this validation since samples on F i do not necessarily map "one-to-one" on samples of F j . This can be done by using the references defined by the corners of F i and F j . If the parameterization of the two faces correspond, samples on the faces could be expressed relatively to the corners. However, this approach fails in the general setting. We propose then a stochastic validation based on the shape distribution presented in [START_REF] Osada | Shape Distributions[END_REF]. The shape distribution is popular due to its efficiency and simplicity.

For a set of candidate symmetric face pairs {F i k , F j k , S k }, we define a shape function that measures the distance between a point on the surface and the symmetry plane of S k . To construct the shape distribution histogram of a face, we define a B fixed size bins and evaluate the distances of all the taken samples to the symmetry plane. We next count the number of samples that fall into each bin. Let H i and H j be the histograms equivalent to the shape distribution of F i and F j , we use a correlation metric to measure the similarity between the histograms:

d H (H i , H j ) = B k=1 (H i (k) -H i ))(H j (k) -H j )) B k=1 (H i (k) -H i )) 2 B k=1 (H j (k) -H j )) 2 , (6) where
H k = 1 B B l=1 H k (l).
If the distance between two histograms is under a threshold defined in term of the bounding box diagonal of the actual model, the two faces are said similar.

E. Extending Isometries

Now, ∆ = {F i k , F j k , S k } k
has a set of face pairs that can share some symmetry planes. These groups of face pairs have to be merged to form the dominant symmetry of the actual model. For that, we define a distance between two isometries as:

d(I, I ′ ) = 1 -- → n , - → n ′ + dist(m, P ′ ) D BBox + dist(m ′ , P ) D BBox . (7)
where -→ n (resp.

-→ n ′ ), P (resp. P ′ ) are normal vector and a point of the symmetry plane corresponding to the isometry I (resp. I ′ ), D BBox is the bounding box diagonal of the actual model, The dominant symmetry of the model is the one having the maximum volume of bounding boxes of its symmetric faces. Moreover, there might exist single faces that are not similar to any other faces but that intersect the dominant symmetry plane. The local symmetry within these faces may contribute to the dominant symmetry. We filter these faces by testing the intersection between the symmetry plane and their bounding boxes and perform a validation based on the shape distribution of the two sets of points that are located in the left and the right of the symmetry plane.

The figure 3 presents some of our results of the detection of (global or partial) dominant symmetries existing in several NURBS based B-Rep models. The blue and red patches are symmetric through the dominant symmetry plane.

In conclusion, the main idea of our algorithm is to consider the transformation between the faces corners in order to efficiently filter transformations. If an isometry exists and is a symmetry, it is validated on the faces bounded by the corresponding corners. The validated symmetries are merged and an expansion process is performed to get the final results. The symmetry plane of the dominant symmetry are used as a first reference to evaluate the canonical frame of aligning the model.

V. DETERMINING THE TWO REMAINING PLANES

In this section, we show how our algorithm can extract the two remaining planes, or two remaining axis direction, for aligning our models. As mentioned above, the first axis is defined as the normal of the dominant partial symmetry and is called the reference axis. Then, to define the two remaining planes, identifying a second plane is sufficient, as the third one is then determined as being orthogonal to the two first planes. The second axis is perpendicular to the reference axis and defines a plane orthogonal to the symmetry plane. We perform an orthographic projection of the model into candidate planes (Figure 4). For the performance of the algorithm, from an arbitrary starting orientation, the second axis is generated by rotating a plane containing the reference axis, around the reference axis with angle increment of an angle of 1 • . We only need to consider 90 different orientations of the second axis that is 90 different planes. For each plane, the area of the orthographic projection is estimated by counting the number of pixels within the 2D projection shape. The chosen axis is the one whose associated plane has the minimum projection area. Figure 5 shows the results of our alignment technique applied on different models. In this figure, the normal of the symmetry plane (red) defined the reference axis, the normal of the blue plane minimizes the orthographic projection areas, the third is determined by the laters. Comparing with the results shown in figure 1, our method rectifies the direction compared to PCA based approaches, and therefore is more coherent with human perception. The result (5d) shows that our technique works well even if the model has a partial symmetry.

VI. EXPERIMENTAL RESULTS

In recent work, image based approaches have been used for 3D models retrieval; the shape contours of 3D models are extracted and converted into 2D images supplying silhouette features to the indexing and searching process [START_REF] Liu | User-Adaptive Sketch-Based 3-D CAD Model Retrieval[END_REF], [START_REF] Eitz | Sketch-based shape retrieval[END_REF]. In fact, the silhouette feature reflects the visual perception while human tries to describe a 3D object within a specific view. Benefiting from our results on 3D model alignment, we use three planes defined by the canonical frame of a given 3D model to extract three silhouettes from different views. Three corresponding feature vectors are then extracted and used for the comparison between models. As the normalized Fourier descriptor associated with centroid distance computation is invariant to translation and scaling [START_REF] Zhang | A comparative study on shape retrieval using Fourier descriptors with different shape signatures[END_REF], it is appropriated to use it with the proposed alignment frame without needing to scale 3D models. Every model is characterized by three normalized Fourier descriptor vectors V F D1 , V F D2 and V F D3 . The similarity measurement between two NURBS-BRep models M 1 and M 2 is defined by:

Sim(M 1 , M 2 ) = 3 i=1 D(V 1 F Di , V 2 F Di ). (8)
where D(•, •) denotes the Euclidean distance.

Our database contains approximately 100 NURBS-Brep models that are downloaded from http://www.grabcad.com. Our models fall into several categories including 22 air planes, 12 vehicles, 9 instruments, 9 boats, 9 animals, 4 sunglasses, 12 machinery components, 15 household objects and 5 guns. Figure 7 shows the results of three queries from our database. While the air planes and the cars are perfectly matched, there exists an ambiguity between the cups and the helmet. In fact, when projecting from the upper, the circular silhouettes of the cup and the helmet are rather similar. For other categories, the retrieval gives acceptable results. The graph in figure 6 presents the Recall-Precision curves of the shape retrieval within our database when aligning models following our approach and the PCA approach. As shown in this graph, the precision of our approach is higher than the PCA.

VII. CONCLUSION

In this paper, we have proposed an original approach for aligning 3D NURBS-BRep models. This paper proposes two main contributions: first, we derive a method for 3D parametric model retrieval avoiding to sample points on the surface in order to adapt classical 3D mesh retrieval techniques. Our approach determines the dominant partial symmetry of the model. Whereas using global symmetry has been proposed for 3D mesh models, and shown to be efficient in previous work, using a partial symmetry is novel. Moreover, the proposed method for identifying the partial symmetry is efficient, even for complex models, since it is based on matching of trimming loops corners, and the parameterization of symmetric surfaces to match is not required to be the same. From the dominant symmetry, the remaining alignment axes are determined by finding a plane, orthogonal to the symmetry plane, giving 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0. the minimal projected area. The effectiveness of our approach has been proved when applying to the NURBS-BRep models retrieval.

  (a) (b) (c) Fig. 2: B-Rep model decomposition. (a) B-Rep objects in a violin model. (b) B-Rep object representing a violin body. (c) B-Rep entities within a face of the violin body.

3 :

 3 Results of symmetry detection. and m (resp. m ′ ) is the barycenter of the two faces corners associated to the isometry I (resp. I ′ ).

  (a) A Cup (b) A Plane Fig. 4: The projection areas of 3D models on different planes containing and rotating around the reference axis.

  (a) A second plane (b) A cup (c) A car (d) A first plane Fig. 5: Aligment results.

Fig. 6 :

 6 Fig.6: Evaluation of the two alignment approaches through the precision rates of the model retrieval within our database.

Fig. 7 :

 7 Fig. 7: Top 4 results of 3 queries for models. The queried models are on the left side, models in the database are on the right side. For each query, the responded models are highlighted the same color as the queried model.