Mohamed Chaouch
email: mohamed.chaouch@inria.fr

Anne Verroust-Blondet

Alignment of 3D models

Keywords: 3D alignment, Principal Component Analysis, Symmetry detection, 3D shape retrieval

In this paper we present a new method for alignment of 3D models. This approach is based on two types of symmetries of the models: the reflective symmetry and the local translational symmetry along a direction. Finding all reflective symmetries of a shape is much more difficult than simply checking whether a given set of symmetries exists. Inspired by the work on the Principal Component analysis (PCA), we select the best optimal alignment axes within the PCA axes, the plane reflection symmetry being used as a selection criterion. This pre-processing transforms the alignment problem into an indexing scheme based on the number of the retained PCA-axes. In order to capture the local translational symmetry of a shape along a direction, we introduce a new measure we call the local translational invariance cost (LT IC). The mirror planes of a model are also used to reduce the number of candidate coordinate frames when looking for the one which corresponds to the user's perception. Experimental results show that the proposed method finds the rotation that best aligns a 3D mesh.

Introduction

Normalization of 3D models is a common pre-processing stage in many applications in computer graphics, such as, visualization, 3D object recognition, 3D shape matching and retrieval [START_REF] Bustos | An experimental comparison of featurebased 3D retrieval methods[END_REF][START_REF] Shilane | The Princeton shape benchmark[END_REF][START_REF] Tangelder | A survey of content based 3D shape retrieval methods[END_REF][START_REF] Zaharia | 3D versus 2D/3D shape descriptors: A comparative study[END_REF]. 3D models are generally given in arbitrary scale, position and orientation in 3D-space. Most of the methods do not satisfy geometrical invariance; hence it is important to normalize the models into a canonical coordinate frame before any processing. The normalization consists of two steps: the alignment to determine the pose-invariant and the scaling to make the scaleinvariant. The alignment is the most difficult point in the normalization process.

To perform an alignment, a concatenation of isometries in 3D-space (translation, rotation and reflection) must be selected to determine the canonical coordinate system. In most of the methods, the center of gravity of the model is chosen as the origin to secure the translation invariance. However, the choice of a suitable rotation is still a well discussed topic [START_REF] Bustos | An experimental comparison of featurebased 3D retrieval methods[END_REF][START_REF] Chen | A 3D model alignment and retrieval system[END_REF][START_REF] Kazhdan | An approximate and efficient method for optimal rotation alignment of 3D models[END_REF][START_REF] Paquet | Description of shape information for 2-D and 3-D objects[END_REF][START_REF] Shilane | The Princeton shape benchmark[END_REF][START_REF] Vranic | Tools for 3D-object retrieval: Karhunen-Loeve transform and spherical harmonics[END_REF][START_REF] Zaharia | 3D versus 2D/3D shape descriptors: A comparative study[END_REF]. Note that the alignment problem addressed in this paper is different from the alignment approaches of [START_REF] Chen | A 3D model alignment and retrieval system[END_REF][START_REF] Kazhdan | An approximate and efficient method for optimal rotation alignment of 3D models[END_REF], where the purpose is to find the best alignment between two given 3D models. Here, we want to compute an intrinsic global coordinate system for each 3D object.

Alignments of 3D models with CPCA.

Alignments of 3D models with our method.

Fig. 1. Comparing CPCA based alignment and our alignment. In each case, green, blue and red arrows represent the principal axes (CPCA) and the suitable axes (our method).

When looking at a 3D model, one can say whether it is well aligned or not and knows, in most of the cases, how to find its good alignment. When the 3D model has symmetries, it is aligned with particular axes or symmetry planes. This is confirmed by Ferguson [START_REF] Ferguson | Modeling orientation effects in symmetry detection: The role of visual structure[END_REF] who noticed that symmetry detection is a key part of human perception and this fact has guided Podolak et al. [START_REF] Podolak | A planarreflective symmetry transform for 3D shapes[END_REF] when introducing principal symmetry axes. Our goal is to find a method that best aligns any 3D model (an alignment similar to what a human would select -see left part of Figure 1) and will consequently align two similar 3D models in the same way. In this paper, we show that by detecting the planar reflection symmetries we can select a set of good alignment axes. However, this method is guaranteed to give the correct alignment for only some cases and keeping only this type of symmetry is insufficient for computing the best alignment for any 3D model. An alternative method is to detect also the local translational symmetry that has an interesting semantic meaning: the object has the same geometrical properties in different parts along a given direction.

To build our general alignment algorithm, we first focus on discrete detection of plane reflection symmetries and classify a model in terms of its symmetry group and the number of its mirror planes. This classification is used to select the good alignment axes among those found by the principal components analysis (PCA).

Then we introduce local translational invariance cost (LT IC) that measures the invariance of a model with respect to local translation along a given direction. This measure is used to compute the remaining alignment axes when the model has at most one good alignment axis given by the PCA. This paper is an extension of [START_REF] Chaouch | A novel method for alignment of 3D models[END_REF]: it gives more details on our alignment algorithm and discuss on methods computing reference frames from our alignment axes.

We first review related work on alignment and symmetry detection for 3D models in section 2. Then we present our selection of the best alignment axes within the PCA-eigenvectors by analyzing the plane reflection symmetries (Section 3), and we describe our alignment method (Section 4). Experimental results evaluating our method are presented in section 5. Finally, we discuss on the ordering and the orientation of the alignment axes in section 6 and we conclude in section 7.

Related Work

The most well-known approach computing the alignment of 3D objects is the principle component analysis method (PCA) [START_REF] Bustos | An experimental comparison of featurebased 3D retrieval methods[END_REF][START_REF] Paquet | Description of shape information for 2-D and 3-D objects[END_REF][START_REF] Shilane | The Princeton shape benchmark[END_REF][START_REF] Vranic | Tools for 3D-object retrieval: Karhunen-Loeve transform and spherical harmonics[END_REF][START_REF] Zaharia | 3D versus 2D/3D shape descriptors: A comparative study[END_REF], which is based on the computation of moments of 3D models. After a translation of the center of mass to the origin of the coordinate system, three principal axes computed with PCA are used to determine the orientation. Experiences show that PCA-alignment has two disadvantages: (i) It is often imprecise and can produce poor alignments; (ii) The principal axes are not always good at aligning orientations of different models within the same semantic class (as noticed by Chen et al. [START_REF] Chen | On visual similarity based 3D model retrieval[END_REF] on the mug example). Podolak et al. [START_REF] Podolak | A planarreflective symmetry transform for 3D shapes[END_REF] introduce a planar reflective symmetry transform (PRST) that computes a measure of the reflectional symmetry of a 3D shape with respect to all possible planes. They use it to define two new concepts for the global coordinate system, the center of symmetry and the principal symmetry axes. The principal symmetry axes are the normals of the orthogonal set of planes with maximal symmetry, and the center of symmetry is the intersection of those three planes. This approach has been improved by Rustamov with the augmented symmetry transform [START_REF] Rustamov | Augmented symmetry transforms[END_REF]. Other methods finding symmetries in 3D models have been presented. These include Minovic et al. [START_REF] Minovic | Symmetry identification of a 3-D object represented by octree[END_REF], who compute symmetries of a 3D object represented by an octree. Their method is based on the computation of a principal octree aligned with the principal axes. Then they compute a measure of symmetry, the symmetry degree, reasoning with the number of distinct eigenvalues associated to the principal axes. Furthermore, Sun and Sherrah [START_REF] Sun | 3D symmetry detection using the extended gaussian image[END_REF] convert the symmetry detection problem to the correlation of the Gaussian image. Then rotational and reflectional symmetry directions are determined using the statistics of the orientation histogram. Finally, Martinet et al. [START_REF] Martinet | Accurate detection of symmetries in 3D shapes[END_REF] use generalized moments to detect perfect symmetries in 3D shapes and Mitra et al. [START_REF] Mitra | Partial and approximate symmetry detection for 3D geometry[END_REF] and Simari et al. [START_REF] Simari | Folding meshes: Hierarchical mesh segmentation based on planar symmetry[END_REF] compute partial and approximate symmetries in 3D objects.

Our goal is to align 3D models using their planar symmetry properties. Our method must be such that similar objects (i.e., objects belonging to the same semantic class) have similar alignments. As noticed in [START_REF] Minovic | Symmetry identification of a 3-D object represented by octree[END_REF], any plane of symmetry of a body is perpendicular to a principal axis. As a result, for models that have plane reflection symmetries, some PCA-coordinate planes coincide with some mirror planes. Therefore, we have chosen to use the PCA, not for global alignment, but for selection of robust partial alignment features of a model (i.e., only the principal axes that we consider good for a perfect alignment).

Given a 3D model, the first key idea is to test the reflection symmetry of the PCAcoordinate planes. According to the result of this test, we select a set of principal axes and use them in our alignment method. When the model has at least two orthogonal mirror symmetries, the PCA gives the good alignment. In the other cases we use the local translational invariance cost along a direction to compute the good alignment axes. Before describing our alignment procedure, let us classify the 3D polygonal models with respect to their plane reflection symmetry and select classes of objects where PCA gives a good alignment.

Symmetry & 3D Objects

In what follows M denotes a 3D polygonal model represented by its surface S composed of a set of triangular facets T = {T 1 , ..., T N T }. We study the reflection planes in the symmetry groups [START_REF] Dubrovin | Modern geometry, methods and applications. Part I. , The Geometry od surfaces, transformation groups, and fields[END_REF], and use them to discriminate different classes of mirror symmetry. Then, we discuss for each class when the PCA alignment has good properties w.r.t. the planar reflective symmetry.

Plane Reflection Symmetry Analysis

A plane reflection symmetry is defined by a mirror plane π that can be parameterized by its unit normal n and its scalar distance δ from the origin. This symmetry associates to each point p of S a mirror reflection point q on S defined by:

q = p -2 (n T • p -δ ) n.
According to Dubrovin et al. [START_REF] Dubrovin | Modern geometry, methods and applications. Part I. , The Geometry od surfaces, transformation groups, and fields[END_REF], studying the plane reflection symmetries of a 3D polyhedral model and the types of symmetry groups, we can distinguish five classes of 3D polyhedral models (see examples in Figure 2):

(1) G C : 3D models that have cyclic symmetry. (4) G U : 3D models that have only one plane reflection symmetry. This is the case for many natural and man-made objects such as airplanes, animals, humans, chairs, cars, etc. (5) G Z : 3D models that don't have any plane reflection symmetry, such as plants and trees.

This classification is valid for perfect plane reflection symmetries. We will extend it to approximate mirror reflections (see section 4.1).

Principal Components & Plane Reflection Symmetry Analysis

In this section, we explore the relation between the principal components analysis (PCA) and the plane reflection symmetry analysis. In our proofs, we have retained the "Continuous principal components analysis" (CPCA) [START_REF] Vranic | Tools for 3D-object retrieval: Karhunen-Loeve transform and spherical harmonics[END_REF] because it appears to be more complete and the most stable of all the PCA-approaches we have studied. CPCA computes three orthogonal eigenvectors of the covariance matrix C. As noticed in [START_REF] Minovic | Symmetry identification of a 3-D object represented by octree[END_REF], when π is a mirror plane of S and n is the unit normal of π, then π passes through the center of gravity of S and n is an eigenvector of the covariance matrix C that is a principal component axis of S (see in appendix a proof for the continuous case). If S has n mirror planes that pass through a fixed axis (as in the cases G C , G D , G R of section 3.1), then n different eigenvectors are associated to the same eigenvalue: in this case, S has a discrete rotational symmetry of order n (n > 1) with respect to the same axis.

Besides that, we note that if S has a set of dual orthogonal reflection planes, the CPCA detects at least two orthogonal normals associated to one dual orthogonal mirror plane of this set. In what follows, for each class described in section 3.1 we discuss the position of these vectors with the reflection symmetries:

-If M ∈ G C and n is even (M ∈ G even C ), then the CPCA detects two orthogonal normals associated to two orthogonal reflection planes and the axis of the axial symmetry (the intersection of the mirror planes). When M ∈ G C and n is odd (M ∈ G odd C ), the CPCA gives only one normal associated to one mirror plane. -If M ∈ G D , then the CPCA gives at least two orthogonal normals; the first is associated to one of the n mirror planes and the second is the axis of the axial symmetry. If, furthermore, n is even, then the CPCA detects the third axis associated to the mirror plane that is orthogonal to the first given mirror.

-If M ∈ G O , then the CPCA detects three orthogonal normals associated to three orthogonal reflection planes, contrarily to the cases of G T and G I , where the CPCA gives only one normal associated to one mirror plane.

-If M ∈ G U , then the CPCA gives only one normal associated to its mirror plane.

n with n > 1 2 symmetry G odd C n with n > 1 1 Dihedral G even D n + 1 with n > 1 3 symmetry G odd C n + 1 with n > 1 2 Rotational G T 6 1 symmetry G O 9 3
G I 15 1
One plane reflection

G U 1 1
No plane reflection G Z 0 0

Table 1 Plane reflection symmetry types and Principal Components Analysis Thus, when M ∈ G even C G D G O , the CPCA detects at least two good alignment axes and when M ∈ G odd C G T G I G U , the CPCA gives only one good alignment axis. Finally, when M ∈ G Z , the CPCA doesn't detect any good alignment axis. We summarize our discussion using the function N GA (M ), which accounts the number of the good alignment axis computed by the CPCA. Given the symmetry class of the model M , N GA (M ) is defined as follows:

N GA (M ) =          2 + i f M ∈ G even C G D G O 1 i f M ∈ G odd C G T G I G U 0 i f M ∈ G Z
N GA (M ) will guide the computation inside our alignment algorithm.

Alignment of 3D Objects

Given a 3D model M , we aim to develop a general algorithm that computes N GA (M ) and selects the set of good alignment axes given by the CPCA, and, if necessary, computes the rest of alignment axes in order to complete the pose coordinate system. We describe here the main steps of our alignment algorithm and detail them in the next subsections (see on Figure 3 an illustration of the algorithm applied to four models of different N GA -values).

Algorithm: Compute good alignment axes

(1) Translate the input 3D model M from its center of gravity to the origin of world coordinate system. (2) Compute the three CPCA eigenvectors v 1 , v 2 , v 3 of the covariance matrix C and rotate the translated model in the new CPCA-coordinate system R (v 1 ; v 2 ; v 3 ) which has the eigenvectors as rows.

(3) Test the reflection symmetry for each coordinate plane normal to a CPCAaxis, (xy-, yz-, zx-coordinate plane) and deduce N GA (M ). We elaborate on this step in section 4.1.1. (4) Select the good alignment axis/axes according to the value of N GA (M ):

(i f N GA (M ) = 2 + ) Return the three good alignment axes R ga (n 1 ; n

2 ; n 3 ) = (v 1 ; v 2 ; v 3 ). (i f N GA (M ) = 1) Return n 1 ∈ {v 1 , v 2 , v 3 }
the normal of the unique mirror plane as the first good alignment axis and rotate the 3D model in the new coordinate system R (n 1 ; v

2 ; v 3 ) if n 1 = v 1 , in R (n 1 ; v 3 ; v 1 ) if n 1 = v 2 , in R (n 1 ; v 1 ; v 2 ) if n 1 = v 3 . (i f N GA (M ) = 0)
Return n 1 the normal of the plane with maximal reflection symmetry (see section 4.1.2) as the first good alignment axis and rotate the 3D model in a new coordinate system R (n 1 ; v 2 ; v 3 ). (5) If N GA (M ) ∈ {0, 1}, Compute the direction vector with maximal local translational invariance cost as will be shown in the algorithm of section 4.2.3 and return the three good alignment axes R ga (n 1 ; n 2 ; n 3 ).

Remark: without loss of generality, we suppose that, when the CPCA computes exactly two normals associated to two mirror planes (i.e. N GA (M ) = 2), the two corresponding axes are n 1 and n 2 .

Plane Reflection Symmetry

There are two approaches for measuring imperfect symmetry:

-The symmetry distance of a shape with respect to a given symmetry is the minimum mean squared distance from the given shape to its perfectly symmetric shape. This measure estimates the symmetry in 3D surface points. While this distance is precise and robust for measuring symmetry, it is expensive for large models.

-The symmetry descriptor similarity of a shape with respect to a given symmetry is the distance between a shape descriptor of the given shape and that of its perfectly symmetric shape. This measure has been proven useful in order to approximate the symmetry distance. The efficiency of the symmetry description in 3D space enables a fast comparison of the amount of reflection symmetries with respect to several planes.

Continuous Symmetry Distance

Let S γ be the reflective surface of S with respect to a plane γ. It has N T triangular facets as S. Following previous works on distance estimation between 3D surfaces [START_REF] Aspert | MESH: Measuring errors between surfaces using the Hausdorff distance[END_REF][START_REF] Cignoni | Metro: Measuring error on simplified surfaces[END_REF] and on symmetry distance [START_REF] Zabrodsky | Symmetry as a continuous feature[END_REF], we define the continuous symmetry distance CSD γ of S with respect to a plane reflection γ as:

CSD γ (S) = 1 A p∈S d(p, S γ ) ds, (1)
where A denotes the area of S and d is the distance between a point p of S and S γ , such that d(p, S γ ) = min p ∈S γ pp 2 , . 2 being the usual Euclidean norm. The integral of the symmetry error over S is computed by summing the contributions of the triangular facets of S. We obtain a more precise result by taking into account all points of S. The computation of these integrals is slightly more expensive than the discrete case as stated by Zabrodsky et al. [START_REF] Zabrodsky | Symmetry as a continuous feature[END_REF]. However, in order to obtain correct point-S γ distances, each triangular facet is sampled uniformly and S is represented by N S sampling points. The integral over each triangular facet T i of S is then approximately done with sums of integrals over triangles obtained by sampling T i . In fact, for each vertex v of each sample triangle T of T i , it is necessary to calculate the distance from v to all facets of S γ in order to find the minimum distance. This leads to a complexity O(N T N S ), which is expensive for large models. This complexity has been reduced in [START_REF] Cignoni | Metro: Measuring error on simplified surfaces[END_REF] by using a local search processing in order to decrease the number of point-triangle distance evaluations. The idea is to partition the bounding box into cubic cells and use them in an indexing scheme for the fast search of the nearest triangle of S γ to the sampling point.

If γ is a perfect mirror plane of S, then CSD γ (S) is null. As we want to retain the quasi-perfect mirror planes, we will approximate this definition. Then we say that γ is a mirror plane of S when SD γ (S) < ε (ε 0). This test will be used in step 3 of the algorithm described in section 4 in order to select the mirror planes among the coordinate planes normal to a CPCA-axis.

Symmetry Descriptors

The symmetry descriptor represents the symmetries of a given model with respect to several planes in 3D space. It is generally associated to a given shape descriptor that represents a model with a spherical function or a 3D function that rotates with the model. Kazhdan et al. [START_REF] Kazhdan | Symmetry descriptors and 3D shape matching[END_REF] define a symmetry descriptor using the planes through its center of gravity. Podolak et al. [START_REF] Podolak | A planarreflective symmetry transform for 3D shapes[END_REF] extend this work by considering symmetries with respect to all possible planes through a model's bounding volume. Following Kazhdan et al. [START_REF] Kazhdan | Symmetry descriptors and 3D shape matching[END_REF] and using the fact that mirror planes are orthogonal to CPCA axes when they exist, we consider a symmetry descriptor that represents the symmetries of a 3D model with respect to planes passing through its center of gravity and in the angular neighborhood of the planes normal to the CPCA-axes.

Measuring imperfect symmetry is used in step 4 (N GA (M ) = 0) of the algorithm described in section 4. Specifically, given the symmetry descriptor values, we select the good axis by finding the plane with maximal symmetry.

Local Translational Invariance

Traditionally, in geometry, the translational symmetry is the invariance of an infinite object with respect to a particular translation. We extend this definition to a finite object, in particular, to a 3D model. We define here the local translational symmetry that will be used in this section. This symmetry implies that a 3D model has the same geometrical properties in different parts along a given direction. Appropriate shape descriptions of the model will be introduced to evaluate the invariance of geometrical properties.

Finding the direction that maximizes the local translational invariance is the last step in our general alignment scheme (when N GA (M ) ∈ {0, 1}). More precisely, we look for local translational symmetries with respect to all directions perpendicular to the first good alignment axis n 1 computed in step 4 of the algorithm of section 4 (see Figure 4). For that purpose, we need to compute a shape descriptor f defined over a one-dimensional interval that represents a 3D model along a given direction and to define a measure of symmetry for f with respect to local translation along this direction. First of all, we describe a method selecting the direction with maximal translational invariance.

Shape Description over 1-D Space

Let d ∈ R 3 be a unit direction vector and π d (ρ), ρ ∈ R, be a family of planes perpendicular to d and at the signed distance ρ from the center of the coordinate system. We represent S as follows, I d being the interval defined by the limits of the 3D surface S in the direction d:

S =
LT IC( f d ) = ∑ I i ∈I L (I i ) , (2)
where L (I i ) is the length of I i and I = {I i ⊂ I d |I i maximum; f d has local translational invariance along d in I i }.

LTIC for Alignment

In this section, we investigate the use of the LTIC in 3D to compute a good alignment axis with respect to translational symmetry. More precisely, we want to select the second alignment axis by finding the direction with maximal local translational invariance cost among the directions perpendicular to the first axis n 1 computed in step 4 of the algorithm of section 4.

In order to evaluate the LTIC, K direction vectors perpendicular to the first good alignment axis n 1 , are obtained by rotating the coordinate system about n 1 as illustrated in Figure 4.

Let R K n be the set generated by the transformation R k which is the rotation about n 1 by the angle θ k = πk K where 0 ≤ k < K:

R k = R θ k (1,0,0) • R , with R θ k (1,0,0) =      1 0 0 0 cos(θ k ) -sin(θ k ) 0 sin(θ k ) cos(θ k )     
and R (see section 4) is the matrix that contains n 1 in the first row.

In what follows, we associate to each R k ∈ R K n one unit direction vector d k equal to the second row of R k . For each d k , a shape descriptor f k is computed. Now, the problem of computing the good alignment axis is to find the direction d ga or its associated rotation R ga , that maximizes the LT IC( f k ):

R ga = argmax R k ∈R K n LT IC( f k ). (3)
Our algorithm for computing the good alignment axes (given the first one) can be summarized as follows:

Algorithm: Compute direction with maximal LT IC (3) Return R ga associated to f ga with maximal LT IC.

Given a matrix R , this algorithm finds the direction vector with maximal local translational invariance cost. The second good alignment axis n 2 is the direction vector d ga that is the second row of R ga and is perpendicular to the first axis n 1 . The third good alignment axis n 3 is naturally the third row of R ga .

Three shape descriptor models for f k

Suppose the surface S k is positioned in the coordinate system defined by (n 1 , d k , n 1 ∧ d k ), and S k (ρ) and I k are defined as in section 4.2.1 with d = d k . Three shape descriptors models G k , E k and F k (see Figure 5) are introduced to represent S k . They use only one coordinate (along the axis n 1 ∧ d k ) as the axis n 1 is already selected in the good coordinate system and d k -coordinate is fixed in S k (ρ).

-Global average description G k . It can be viewed as a curve given by the projections of the centers of gravity of the sub-shapes S k (ρ) along the direction

n 1 ∧ d k ) T . G k (ρ) = 1 A k (ρ) p∈S k (ρ) (n 1 ∧ d k ) T • p ds,
where A k (ρ) = p∈S k (ρ) ds denotes the area of S k (ρ).

Using this descriptor, we measure the local invariance of the gravity along the direction n 1 ∧ d k .

-Global extremum description E k . It represents two independent curves given respectively by the minimal and the maximal projections of the n 1 ∧ d k coordinates of the sub-shapes S k (ρ).

E k (ρ) =   min p∈S k (ρ) ((n 1 ∧ d k ) T • p) max p∈S k (ρ) ((n 1 ∧ d k ) T • p)  
Here, we measure the local invariance of the couple formed by the minimal and maximal coordinates of the surface along the direction n 1 ∧ d k .

-Vector shape description F k : This descriptor evaluates more precisely the local invariance of the shape along the direction n 1 ∧ d k .

Let J k be the interval defined by the limits of the 3D surface S k in the direction n 1 ∧ d k . The bounding box of mesh S k is partitioned into M k cells along the direction n 1 ∧ d k according to a regular sampling of J k . Then, S j k (ρ) is the intersection of the shape S k (ρ) and the j th cell.

S k (ρ) = M k j=1 S j k (ρ).
This descriptor represents S k (ρ) with a collection of areas and averages associated to the shapes

S j k (ρ), 1 ≤ j ≤ M k : F k (ρ) = a j k (ρ), g j k (ρ) M k
, where

a j k (ρ) =    p∈S j k (ρ) ds if S j k (ρ) = / 0, / 0 otherwise. g j k (ρ) =    1 a j k (ρ) p∈S j k (ρ) (n 1 ∧ d k ) T • p ds if S j k (ρ) = / 0, / 0 otherwise.

Discrete computation

With the introduced definitions, we deduce a discrete version of the function f k represented on N k points regularly sampled on I k . To define f k at the same scale in any direction d k , the number of samples N k is such that the interval L (I k ) N k has a fixed length 2δ (see section 4.2.1) for any orientation k. A unit of measurement N = scale 2δ should be fixed for all 3D models. In our case, N = 1 2δ (N = 32, 64, 128) because M is scaled (see the first step of the algorithm in section 4.2.3).

N k = N L (I k ) . (4)
Similarly, we take M k = N L (J k ) when computing F k . Finally, for each shape descriptor proposed here, we use a distance dist( f k (i), f k (i )) (where f k (i), 1 ≤ i ≤ N k ) in order to apply definition 1, choose a normalized error ε N 0 fixed for all 3D models and consider that

f k (i) = f k (i ) if dist( f k (i), f k (i )) < ε N .
In our implementation, dist(, ) is the usual Euclidean norm . 1 for the global average description and the global extremum description. It is defined as follows for the vector shape description:

dist(F k (i), F k (i )) = d F k (i, i ) + d F k (i , i) A k (i) + A k (i )
, where

d F k (i, i ) = g j k (i) = / 0 ∑ 1≤ j≤M k a j k (i) g j k (i ) = / 0 min 1≤ j ≤M k g j k (i) -g j k (i ) 1 .
The distance d F k (i, i ) leads to a complexity O(M k M k ). In order to reduce the computing time, we reduce the number of distance evaluations

g j k (i) -g j k (i ) 1 , 1 ≤ j, j ≤ M k .
We make an a priori coherence assumption: we suppose that the index j m = argmin 1≤ j ≤M k g j k (i)g j k (i ) 1 is not far from the index j. Thus, we first test the sparsity of g j k (i ) and we stop if g j k (i ) = / 0. Otherwise, the adjacent points are processed, in order of increasing distance from g j k (i) and we stop when we find g j m k (i ) = / 0. We stress that all non-tested points are farther than the found point.

Experimental Results

In order to evaluate our alignment algorithm, we ran the experiments with the Test Princeton 3D Shape Benchmark database [START_REF] Shilane | The Princeton shape benchmark[END_REF] consisted of 907 polygonal models categorized into 92 distinct classes. Our alignment method computes three lines of support which are arbitrarily oriented and given in arbitrary order. Two alignment frames are said similar when their sets of three lines are the same.

Fig. 6. Alignments of models from different classes using our method.

We found that our approach produces coordinate frames that are robust and semantically correct for most of the models. Figure 6 shows a number of models from different classes aligned by our method. Moreover, our approach gives more precise results than CPCA, as illustrated in Figure 7, and provides similar alignments for models belonging to the same class, see for example the alignments of the mailbox class in Figure 8. We measured the performance of our alignment method by generating a test set of 33 distinct classes which generally are not well aligned by CPCA. Table 2 gives, for each class, the percentage of perfect alignment (i.e., accurately similar to what a human would select) and compares the results of the CPCA method to our method using the shape descriptors G, E and F introduced in section 4.2.4. To compute the percentages, we asked three individual, expert in 3D modeling, to group the models of each class into two sub-classes "well aligned" and "poorly aligned" objects. For example, all the models shown in Figure 6 (belonging to this test set) have been considered "well aligned". The percentages appearing in the Table 2 indicate the average ratio of "well aligned" models inside each class. By examining Table 2, we note that for the three descriptors (G, E and F), our general scheme provides better alignment performance, with perfect-alignment percentages that are generally close to 100%. When using the shape descriptor F, our method provides more accurate alignment results than using G and E. Table 2 Perfect alignment percentages for some classes (311 models). Comparing the Accuracy of CPCA and our method with the shape descriptors G, E and F.

To evaluate the effectiveness of our alignment algorithm in shape retrieval tasks, we applied it as a normalization step in a general retrieval process. As 3D retrieval approaches based on 2D projections (2D/3D approaches) are very sensitive to the 3D model orientation, we have chosen to test our alignment on one of these meth-ods. We used the shape descriptor DLA [START_REF] Chaouch | 3D model retrieval based on depth line descriptor[END_REF] that represents each model by a set of depth lines transformed into sequences and the dynamic programming distance DPD that measures the similarity between the depth line descriptors. To compare objectively the retrieval effectiveness, for both types of alignment methods, we computed Precision-Recall diagrams commonly used in information search (the query is not counted in the answer as in [START_REF] Vranic | 3D model retrieval[END_REF]) and four quantitative measures, Nearest Neighbor (NN), First Tier (FT), Second Tier (ST), and Discounted Cumulative Gain (DCG), for evaluating query results (see [START_REF] Shilane | The Princeton shape benchmark[END_REF] for a description of this measures). Fig. 9. Average Precision-recall curves using the CPCA and our alignment followed by the depth line-based approach DLA (with dynamic programming distance DPD, 6 depth images of size 32x32). The mean NN, FT, ST and DCG values are given in the legends.

Comparing the curves as well as the NN, FT, ST and DCG values in Figure 9, we conclude that our alignment method clearly outperforms the CPCA. In particular, these results confirm that our approach is better than CPCA for aligning similar models in the same way.

Efficiency:

The O(N T ) complexity of the CPCA algorithm makes our approach clearly faster than the existing alignment approaches based on symmetry in 3D rotation space.

As one can see in Table 3, the CPCA provides, in our general algorithm applied to the Test PSB database, a quick alignment for 28.5% of the models (N GA = 2 + ) that have at least two good alignment axes. The most time-consuming stage is the symmetry descriptor algorithm for finding the plane with maximal symmetry. This descriptor was computed on 20% of the models (N GA = 0) that don't have any good alignment axis within CPCA-axes.

Ordering and orientation of the axes of the alignment frame

As we noticed before, the three alignment axes n 1 , n 2 , n 3 of R ga computed by the algorithm of section 4 are given in an arbitrary orientation and order. Thus, 48 coordinate systems can be built by performing permutations and inversions of the alignment axes.

In our tests, we used the method based on moments, which is described in section 6.1, to compute a coordinate system. This method is guaranteed to give the same order and orientations of the alignment axes for similar models in most of the cases. However, the solution is generally different from the natural pose that a human would select. In section 6.2 we introduce the perspective of this work: an alternative method where the symmetry properties of the model are used to position the model according to the human perception. A unique coordinate system cannot be computed in all the cases but a set of coordinate system candidates can be proposed.

Method based on moments

In this section, we follow Vranic's approach [START_REF] Vranic | 3D model retrieval[END_REF] used to order the CPCA axes and to fix their orientation. Let S ga be the surface of the model in the frame R ga . We calculate the average projections of the points of S ga in the new coordinate planes through the center of gravity of the model. We sort the values of c x , c y and c z in decreasing order and form the rotation matrix A which has the three corresponding unit vectors as rows. We rotate the vertices of S ga using A and obtain a new surface S ga .

To ensure the reflection invariance, vertices of S ga are multiplied by a diagonal matrix F = diag(sign( f x ), sign( f y ), sign( f z )), with The chair B has been scaled in depth by a factor 1.1, the chair D has been scaled in width by a factor 1.9 and the chair C has been scaled in width and depth by a factor 2. The method based on moments computes four different reference frames for these four chairs. Moreover, by changing the proportions of the back of the chair, as in case E and by enlarging the front legs of the chair as in case F, the orientations of the axes are different from the original ones.

f x = 1 A

Alternative method

In this section, we discuss the positions of the alignment axes with respect to the natural pose (a vertical direction and two horizontal ones that a human perceives).

To do this, we use the value of N GA and the type of symmetry group of a 3D model detailed in section 3.1. Note that the order and the orientations cannot be found in all the cases but this approach will reduce human interaction. Our work will be guided by the following observation: when considering human perception, Fergu-son [START_REF] Ferguson | Modeling orientation effects in symmetry detection: The role of visual structure[END_REF] observed that the best known orientation effect is the preference for vertical symmetry. It is confirmed when examining the 3D models of the Princeton Shape Benchmark: for example, the models of Figure 6 having a planar symmetry have a mirror plane in vertical position. Thus two assumptions are used when computing the reference frames from the alignment axes:

-When the 3D model has a cyclic or a dihedral symmetry, the axis of cyclic or dihedral symmetry is vertical.

-When the object has a reflection plane and when its associated normal n is not the axis of a dihedral symmetry, n is horizontal.

In the following, we need a process that detect and compute the order of a cyclic symmetry along a given axis n i for a 3D model. This can be carried out by using the symmetry descriptor of Podolak et al. [START_REF] Podolak | A planarreflective symmetry transform for 3D shapes[END_REF] on a distribution of planes rotated around n i .

Considering the number of principal axes retained by our method, we now discuss the ordering and orientation of the alignment directions. Let M be a 3D model with N GA good alignment axes detected by the CPCA and R ga = (n 1 ; n 2 ; n 3 ) its reference frame computed by the algorithm of section 4. We want to compute the reference frames R ga = (w 1 ; w 2 ; w 3 ), where w 3 is in the vertical direction and w 1 = ±n i , w 2 = ±n j and w 3 = ±n k ,with {i, j, k} = {1, 2, 3}. According to sections 3.1 and 3.2, we have: -If the order of the cyclic symmetries around two principal axes is 2 and if the order n of cyclic symmetry around the third axis is greater than 2, then M ∈ G even D with n > 2. Moreover, if n is a multiple of 4, then the two horizontal axes play the same role and we have one coordinate system (case (a) of Figure 11), otherwise we obtain two different coordinate systems.

• If N GA = 3,
-If the order of the cyclic symmetry around each principal axis is 4, then M ∈ G O and any ordering and orientation of the three axes computed by the CPCA will lead to the same coordinate system for M . This is summarized in table 4. Table 5 Coordinate system candidates when N GA ≤ 1.

• If N GA = 2, then M ∈ G even C G odd D . Following the remark of section 4, the two mirror planes detected by the CPCA are given by n 1 and n 2 . We test the cyclic symmetry around these axes. If one of these axes has a cyclic symmetry, then M ∈ G odd D and the axis is vertical (case (b) of Figure 11) and four coordinate systems are computed. In the other case, M ∈ G even C and n 3 , the axis of cyclic symmetry of order n, is vertical. Moreover, if n is a multiple of 4, then n 1 and n 2 play the same role and we obtain two different coordinate systems, as in the case (c) of Figure 11. Otherwise, we obtain four coordinate systems, as resumed in table 4 and illustrated in case (d) of Figure 11.

• If N GA = 1, then M ∈ G odd C G T G I G U
The eigenvector n 1 computed by the CPCA will be horizontal and the user has to choose among 16 coordinate systems given in table 5.

• If N GA = 0, then M ∈ G Z .
The normal n 1 of the plane with maximal reflection symmetry computed by the algorithm of section 4 will be horizontal and 32 coordinate systems are proposed to the user, resumed in table 5. We are currently developing an interactive tool that proposes to a user a set of coordinate system candidates based on this discussion. It can also be used to reduce the number of cases to consider when computing the similarity between two 3D models in shape retrieval methods.

Reference frame and upright orientation

Fu et al. [START_REF] Fu | Upright orientation of man-made objects[END_REF] deal with a close but slightly different problem: given a training set of models with their prescribed upright orientations, they propose a method computing the upright orientation of new objects but they don't compute the object's reference frames. They focus on "standing man-made models", that is models which usually stand on flat surfaces and which "have well-defined upright orientations". For that purpose, a supervised learning algorithm selects the best orientation from a small set of orientation candidates extracted by analyzing the object's convex hull.

A set of attributes are associated to each candidate base. Their values are computed evaluating geometric properties such as static stability, symmetry, parallelism and visibility of the 3D objects w.r.t. the base.

Our alignment method could replace the convex hull process to find candidate upright orientations: it would lead to at most 6 possible upright orientations associated to the alignment axes. Moreover, following the process summarized in table 4, we would compute upright orientations of models belonging to G even D (except when there are exactly three mirror planes, which corresponds to the first line of table 4), G odd D and G O , cases where the coordinate systems proposed to the user gives only one vertical axis with the same orientation. Conversely, if we use a property such as static stability when looking for a reference frame, we can reduce the number of coordinate system candidates proposed to the user but we may eliminate the user's solution as for the case of the gun and of the street light in Figure 8. Parallelism and visibility properties may also be fragile if we consider that the user's choice is primordial. Anyway, the symmetry properties seem to be the most important ones for both upright orientations and reference frames: in fact, the examples of correct upright orientations given in Figure 6 of [START_REF] Fu | Upright orientation of man-made objects[END_REF] have, for most of them, one or more vertical reflective planes.

Conclusion

We have presented a new alignment method for 3D models. It retains the principal axes of the CPCA with respect to the approximate reflection plane symmetry. We have introduced a new notion of cost (LT IC) that measures the invariance of a model with respect to local translation along a given direction. This measure is used to compute the remaining alignment axes. To obtain the ordering and orientation of the resulting alignment axes, we have proposed a method that reduces the number of coordinate systems to a set of candidates containing the optimal solution. Our experiments show that our approach consistently aligns the 3D objects: we obtain 100% in 24 classes among the 33 classes tested and the others never exceed less than 75% of correct alignment. Moreover, our alignment method provides more accurate results than the CPCA when it is used as a normalization step in a 3D shape retrieval method.

Fig. 2 .

 2 Fig. 2. Models belonging to different classes of mirror symmetry: Tetrahedron ∈ G T , Octahedron ∈ G O , Icosahedron ∈ G I , Table ∈ G even C , Street-light lamp ∈ G odd C , Hourglass ∈ G even D , 5-prism ∈ G odd D , Chair ∈ G U , Plant ∈ G Z .

Fig. 3 .

 3 Fig. 3. Alignments of models with different N GA using our method: Hot air balloon and Hourglass models N GA = 2 + , Chair model N GA = 1, Tree model N GA = 0. Row 1: CPCA Alignments, Row 2: Testing the reflection symmetry for CPCA-coordinate planes, Row 3: Computing the direction with maximal local translational invariance, Row 4: Our Alignment results.

SDefinition 1 . 2 .

 12 d (ρ), where S d (ρ) is the 3D sub-shape of S limited by the planes π d (ρ -δ ) and π d (ρ + δ ), δ ∈ R. In this representation, S is viewed as the union of bands of surface of width 2δ and limited by planar curves belonging to planes perpendicular to d. In what follows, f d denotes a function defined on the interval I d and having values on a scalar, or vector space, such that f d (ρ) is a shape descriptor of S d (ρ) for any ρ ∈ I d . Methods computing the shape descriptor f d of S are given in section 4.2.4. 4.2.2 Local Translational Invariance Cost Given a shape descriptor f d of Sdefined over an interval I d and a unit vector d, we say that f d has local translational invariance along d in an interval I ⊂ I d if for all ρ, ρ ∈ I, f d (ρ) = f d (ρ ). In order to measure the local translational symmetry of a shape descriptor f d , we detect the maximal sub-intervals I i of I d such that f d has local translational invariance along d in I i . The cost of this symmetry is defined as follows: Definition Given a shape descriptor f d defined over I d , the local translational invariance cost (LT IC) of f d along d is the sum of the lengths of the maximal intervals I i of I d where f d has local translational invariance along d in I i :

Fig. 4 .

 4 Fig. 4. Computing the good alignment axes (given the first one n 1 ) for the chair model N GA (M ) = 1. Row 1: Return n 1 the normal of the unique mirror plane as the first alignment axis, Row 2: Rotate the model about n 1 in order to find the rotation with maximal local translational invariance, Row 3: Align chair model in the coordinate system R ga .

( 1 )

 1 Translate the input 3D model M from its center of gravity to the origin, and scale the translated model such that the average distance of a point on the surface to the new coordinate origin is 1. (2) Given a matrix R , for each θ k , (a) Compute the transformation R k and the associated direction vector d k . (b) Rotate the transformed model (step 1) in the coordinate system R k in order to obtain S k . (c) Compute the interval I k of length L I k and the shape descriptor f k defined over I k . (d) Measure the LT IC( f k ).

Fig. 5 .

 5 Fig. 5. The three shape descriptors G, E and F corresponding to the chair model are computed along the vertical direction d k . For this case, the three descriptors lead to the same direction with maximal LT IC. Surface positions associated to intervals of local translational invariance are colored in blue while the others are colored in red.

Fig. 7 .Fig. 8 .

 78 Fig. 7. Comparing the precision of CPCA (left) and our alignment of mailbox model.

  Descriptor -Test Princeton Database Our Alignment [71.34 42.94 55.27 68.77] CPCA [66.70 39.49 50.21 65.31]

  p x ds, c y = 1 A p∈S ga p y .p y ds, c z = 1 A p∈S ga p z .p z ds, with p = (p x , p y , p z ).

  p∈S ga sign(p x )|p x | 2 ds , p = (p x , p y , p z ) and f y , f z similar.

Fig. 10 .

 10 Fig. 10. The different coordinate frames obtained with the method based on moments after deformations of a chair. This method is not robust w.r.t. small deformations of a model. Let us consider the chairs of Figure 10. The chair A has been transformed in chairs B, C, D, E and F.The chair B has been scaled in depth by a factor 1.1, the chair D has been scaled in width by a factor 1.9 and the chair C has been scaled in width and depth by a factor 2. The method based on moments computes four different reference frames for these four chairs. Moreover, by changing the proportions of the back of the chair, as in case E and by enlarging the front legs of the chair as in case F, the orientations of the axes are different from the original ones.

  then M ∈ G even D G O As we don't know whether M is in G even D or in G O , we study first the case M ∈ G even D and explain how to proceed in all the cases. When M ∈ G even D , M has an even number n of mirror planes and has another mirror plane P 3 which is perpendicular to the previous ones. In this case, M has a dihedral symmetry around the intersection of the n mirror planes. When n > 2, this axis has to be the vertical axis w 3 of our reference frame. To differentiate the three cases ( G even D with n = 2, G even D with n > 2 and G O ), we test the cyclic symmetry around each principal axis: -If the order of the cyclic symmetry around each principal axis is 2, then M ∈ G even D with n = 2 and six reference frames can be computed from the principal axes.

Fig. 11 .

 11 Fig. 11. The coordinate systems corresponding to the following cases: (a) N GA = 3, M ∈ G even D with n = 4, (b) N GA = 2, M ∈ G odd C , with n = 3, (c) N GA = 2, M ∈ G even C

Table 3

 3 Repartition of 3D models of the Test Princeton Shape Benchmark database with respect to N GA

	N GA	0	1	2 +
	Number of 3D models	181	467	259
	Distribution (N GA )	20.0% 51.5% 28.5%

Table 4

 4 Coordinate system candidates when N GA > 1.

	N GA	Class	Horizontal	Vertical	Coordinate systems
			axis	axis	proposed to the user
	1	G U	n 1	n 2 or n 3
	0	G Z	n 1	n 2 or n 3

(n 1 ; ±n 2 ; ±n 3 ) (n 1 ; ±n 3 ; ±n 2 ) (±n 3 ; n 1 ; ±n 2 ) (±n 2 ; n 1 ; ±n 3 ) (±n 1 ; ±n 2 ; ±n 3 ) (±n 1 ; ±n 3 ; ±n 2 ) (±n 3 ; ±n 1 ; ±n 2 ) (±n 2 ; ±n 1 ; ±n 3 )

Appendix

Lemma 3. Let π be a mirror plane of S and g be the center of gravity of S. Then g ∈ π . Lemma 4. Let π be a mirror plane of S and n be the unit normal of π. Then n is an eigenvector of S.

Proof. The vector n is an eigenvector of the covariance matrix

Suppose g is the the center of gravity of S. We first construct the covariance matrix of S.

By previous Lemma g ∈ π and by orthogonal projection for all v onto π i.e., v π ∈ π, we get

here n is unit vector, thus we have n T • n = 1 Combining the three equations, we obtain

Therefore, the unit normal n of the mirror plane π is the eigenvector of S and 1 S v d 2 v is the corresponding eigenvalue.