Kamal Nasreddine
email: nasreddine@enib.fr

Abdesslam Benzinou
email: benzinou@enib.fr

Variational Shape Matching For Shape Classification and Retrieval

Keywords: Shape classification, shape retrieval, contour matching, shape geodesics, multi-scale analysis, robustness

published or not. The documents may come

Introduction and related work

This work addresses the definition of a robust distance between shapes based on shape geodesics. The proposed distance is applied to shape classification and shape retrieval. Recently, computer vision has extensively studied object recognition and known significant progress, but current techniques do not provide entirely significant solutions [START_REF] Daliri | Robust symbolic representation for shape recognition and retrieval[END_REF][START_REF] Veltkamp | State of the art in shape matching[END_REF].

Regarding shape analysis and classification, similarity measures may be defined from information extracted from the whole area of the object (regionbased techniques) [START_REF] Kim | A region-based shape descriptor using zernike moments[END_REF], or from some features which describe only the object boundary (boundary-based techniques) [START_REF] Costa | Shape analysis and classification, theory and practice[END_REF]. The latter category may also comprise skeleton description [START_REF] Lin | Coding and comparison of dag's as a novel neural structure with applications to on-line handwriting recognition[END_REF][START_REF] Sebastian | Curves vs. skeletons in object recognition[END_REF]. Skeleton description of shapes has a lower sensitivity to articulation compared with boundary and region descriptions, but it is with the cost of higher degree of computational complexity due to tree or graph matching [START_REF] Sebastian | Curves vs. skeletons in object recognition[END_REF][START_REF] Sebastian | On aligning curves[END_REF]. On the other hand, boundary-based object description is considered more important than region-description because an object's shape is mainly discriminated by the boundary. In most cases, the central part of object contributes little to shape recognition.

The boundary-based approach described in this paper is established on a comparison between matched contours. Contour matching has been already widely applied to object recognition based on shape boundary [START_REF] Diplaros | Matching and retrieval of distorted and occluded shapes using dynamic programming[END_REF]. Two major classes of techniques can be distinguished: those based on rigid transformations, and those based on non-rigid deformations [START_REF] Veltkamp | State of the art in shape matching[END_REF]. Methods of the first type search optimal parameters which align feature points assuming that the transformation is composed of translation, rotation and scaling only. They may lack accuracy.

Methods based on elastic deformations rely on the minimization of some appropriate matching criterion. They may present the drawback of asymmetric treatment of the two curves and in many cases lack of rotation and scaling invariance [START_REF] Veltkamp | State of the art in shape matching[END_REF]. Existing techniques typically take advantage of constraints specific to the applications or use shape landmarks.

These points are generally defined as minimal or maximal shape curvature [START_REF] Del Bimbo | Shape indexing by multiscale representation[END_REF][START_REF] Super | Retrieval from shape databases using chance probabil-ity functions and fixed correspondence[END_REF], as zero curvature [START_REF] Mokhtarian | Curvature scale space representation: theory, applications, and MPEG-7 standardization[END_REF], at a distance from specific points [START_REF] Zhang | Object representation and recognition in shape spaces[END_REF], on convex or concave segments [START_REF] Diplaros | Matching and retrieval of distorted and occluded shapes using dynamic programming[END_REF], or any other criteria suitable to involved shapes. Shape analysis from geodesics in shape space has emerged as a powerful tool to develop geometrically invariant shape comparison methods [START_REF] Younes | Optimal matching between shapes via elastic deformations[END_REF]. Using shape geodesics, we can state the contour matching as a variational non rigid formulation ensuring a symmetric treatment of curves. The resulting similarity measure is invariant to translation, rotation and scaling independently on constraints or landmarks, but constraints can be added to the approach formulation when available. This paper is an extension of the work presented in [START_REF] Younes | Optimal matching between shapes via elastic deformations[END_REF] to the task of shape classification and the task of shape retrieval.

The following is a summary list of the contributions of our work:

-Geodesics in shape space have been introduced to develop efficient shape warping methods [START_REF] Younes | Optimal matching between shapes via elastic deformations[END_REF]. Recently, we have exploited the corresponding similarity measure to define a new distance for shape classification and applied it to marine biological archives [Nasreddine et al., 2009a,b]. This distance takes advantage of local shape features while ensuring invariance to geometric transformations (e.g. translation, rotation and scaling). To deal with local and global variabilities, we derive here a new multi-scale approach proposed for shape classification and shape retrieval.

-We establish the gain of the proposed method over state-of-art methods for shape classification and shape retrieval. The test is carried out on a complex shape database, the part B of the MPEG-7 Core Experiment CE-Shape-1 data set [START_REF] Jeannin | Description of Core Experiments for MPEG-7 Motion/Shape[END_REF]. This database is the largest and the most widely tested among available test shape databases [START_REF] Daliri | Robust symbolic representation for shape recognition and retrieval[END_REF].

The subsequent is organized as follows. In Section 2 is detailed the proposed framework for shape matching in the shape space, from where a robust similarity measure between two shapes is taken. We discuss in Section 3 the benefit of the proposed similarity measure on shape matching performances.

Sections 4 and 5 derive a multi-scale distance proposed for shape classification and shape retrieval. In Section 6 we evaluate the proposed distance for shape classification and shape retrieval for part B of the MPEG-7 shape database and we compare results to other state-of-art schemes.

Proposed contour matching

In this paper a boundary-based approach is considered. The comparison between shapes is based on a similarity measure using shape geodesics. The proposed similarity measure is applied to shape classification and retrieval.

A multi-scale analysis is performed to take into account both local and global differences in the shapes.

Shape geodesics

There are various ways to solve for shape matching problem, and many similarity measures have been proposed in the case of planar shapes [START_REF] Veltkamp | Shape matching: similarity measures and algorithms[END_REF]. Shape geodesics have emerged as a powerful tool to develop geometrically invariant shape comparison methods [START_REF] Younes | Optimal matching between shapes via elastic deformations[END_REF]. Shapes are considered as points on an infinite-dimensional Riemannian manifold and distances between shapes as minimal length geodesic paths. Retrieving the geodesic path between any two closed shapes resorts to a matching issue with respect to the considered metric. Let us consider two shapes Γ and Γ locally characterized by the angle between the tangent to the curve and the horizontal axis (θ and θ respectively). Following [START_REF] Younes | Optimal matching between shapes via elastic deformations[END_REF], the matching issue is stated as the minimization of a shape similarity measure given by :

SM Γ, Γ(φ) = 2 arccos s∈[0,1] φ s (s) cos θ(s) -θ(φ(s)) 2 ds (1)
where s refers to the normalized curvilinear abscissa defined on [0, 1], φ is a mapping function that maps the curvilinear abscissa on Γ to the curvilinear abscissa on Γ and φ s = dφ ds . The similarity measure considered here includes a measure of the difference between the two orientations θ and θ, cos θ(s)-θ(φ(s))

Curve parametrization via angle function θ(s) naturally leads to a representation which complies with the expected invariance properties (translation and scaling). A translation of the curve has no effect on θ, and an homothety has no effect on the normalized parameter s. Thus curves modulo translation and homothety will be represented by the same angle function over all choices for the origins of the curve parameterizations is considered.

Robust variational formulation

Given two shapes Γ and Γ respectively encoded by θ(s) and θ(s), the matching problem comes to the registration of two 1D signals [Nasreddine et al., 2009a,b]. The registration consists in retrieving the transformation that best matches points of similar characteristics. Formally, it resorts to determining the transformation function φ(s) such that θ(s) = θ(φ(s)). Here, this issue is stated as the minimization of an energy E Γ, Γ(φ) involving a datadriven term, E Γ, Γ D , that evaluates the similarity between the reference and aligned signals and a regularization term1 , E R .

E Γ, Γ(φ) = (1 -α)E Γ, Γ D (φ) + αE R (φ) (2) E R (φ(s)) = s∈[0,1] |φ s (s)| 2 ds (3)
where α is a variable that controls the regularity. From time causality, the minimization of E Γ, Γ(φ) has to be carried out under the constraint φ s > 0.

To ensure more robustness against outliers, we have introduced a robust criterion as a modification of the similarity measure issued from shape geodesics [START_REF] Nasreddine | Variational 1d signal registration and shape geodesics for shape classification: Application to marine biological archives[END_REF]. Using a robust estimator ρ, the shape registration issue resorts then to minimizing:

E Γ, Γ(φ) = (1 -α)E Γ, Γ D (φ) + α s∈[0,1] |φ s (s)| 2 ds E Γ, Γ D (φ) = arccos s∈[0,1] φ s (s) cos ρ(r(s)) 2 ds (4)
where r(s) = θ(s) -θ(φ(s)). Several forms of the robust estimator ρ were proposed [START_REF] Black | On the unification of line processes, outlier rejection and robust statistics with applications in early vision[END_REF]]. We will use the Leclerc estimator given by:

ρ(r) = 1 -exp(-r 2 /(2σ 2 )) (5)
with σ is the standard deviation of data errors r.

Numerical implementation

To solve for the minimization of E Γ, Γ(φ), two methods are considered: dynamic programming and an incremental scheme.

A dynamic programming algorithm is applied as follows. Given a discretisation step and the discretized vectors θ(s i ) i=1..N and θ(s j ) j=1..M , the algorithm considers in the plane [s 1 , s N ] × [s 1 , sM ] the grid G which contains the points p = (x, y) such that either x = s i and y ∈ [s 1 , sM ], or y = sj and

x ∈ [s 1 , s N ].
We fetch a continuous and increasing matching function that is linear on each portion that does not cut the grid. The value of the energy E Γ, Γ(φ) is calculated at each point of the grid depending on the values at previous points, and the minimum is chosen. This procedure is iterated over all choices for the origins of the curves. This algorithm is more detailed in [START_REF] Trouvé | Diffeomorphic matching problems in one dimension: Designing and minimizing matching functionals[END_REF].

As an alternative, we have proposed an incremental iterative minimization [START_REF] Nasreddine | Variational 1d signal registration and shape geodesics for shape classification: Application to marine biological archives[END_REF], which is shown to be computationally more efficient than the dynamic technique in the case of registration without landmarks (see section 3 for comparison). At iteration k, given current estimate φ k we solve for an incremental update:

φ k+1 = φ k + δφ k such that δφ k = argmin δφ E Γ, Γ(φ k + δφ).
The initialization of the algorithm is given by the identity function taken in turn for all choices for the origins of the curves.

For each of these initializations, the algorithm iterates two steps:

1. the computation of the robust weights ω k i issued from the linearization of the Leclerc estimator as [START_REF] Black | On the unification of line processes, outlier rejection and robust statistics with applications in early vision[END_REF],

ω k i = 2 σ 2 exp( -r 2 (s i ) σ 2 )
2. the estimation of δφ k = {δφ k (s i )} as successive solutions of the lin-

earized minimization δφ k = argmin δφ i E k i .
The key approximation of this linearization is: θ(φ k+1 ) = θ(φ k + δφ k ) ≈ θ(φ k ) + θs (φ k ) • δφ k . For α = 0, the equation we obtain does not have a unique solution. The resulting δφ k (s i ) for α = 0 is given by:

δφ k (s i ) = N (s i ) D(s i ) (6) g(s i ) = (1 -α) sin ω k i r(s i ) 2 [ θ(φ k (s i )) -θ(φ k (s i-1 ))] N (s i ) = -φ k (s i+1 ) -φ k (s i-1 )g(s i )cos ω k i r(s i ) 2 +2α[2φ k (s i ) -φ k (s i-1 ) -φ k (s i+1 ) -δφ k (s i-1 ) -δφ k-1 (s i+1 )] D(s i ) = 1 2 φ k (s i+1 ) -φ k (s i-1 )g 2 (s i ) -4α

Shape matching performances

To study the influence of the robust criterion and of the regularization term, we evaluate here the matching process for synthetic contours (one contour is obtained by applying a known transformation to the other one). Some examples of these synthetic shapes are given in Figure 1 {Figure 3 goes here}

In Figure 3, we report another test for a synthetic shape obtained by applying an occlusion on the shape given in Figure 1(c). The results of its matching to the reference shape given in Figure 1(a) are reported in Figures 4 and5. We see that the robust algorithm is more robust against the occlusion, it is still able to align the curves and to retrieve the applied transformation {Figure 4 goes here} {Figure 5 goes here}

The relevance of the robust solution is even more visible when we analyze the evolution of the incremental algorithm through the initializations in turn 2 defined as:

M SE N onRobust θ -M SE Robust θ M SE N onRobust θ × 100
for all choices for the origins of the curves. We report in Table 1 matching results for initialization far from the correct solution, we notice that with the robust criterion M SE θ decreases through iterations to attain the optimum.

In contrast M SE θ values remain greater when the non robust criterion is used and only a local minimum is reached. These experiments show that this criterion is robust to the initialization of the choice of the origins of the curves. Hence, only one arbitrary initialization may be considered in practice.

Regarding computational complexity, the incremental method is also more efficient when shape matching with no landmarks is addressed. The dynamic programming needs a relatively longer time. For example, for the synthetic contours considered in Figure 1, this time reaches 9.7 times that required by the robust iterative scheme.

{Table 1 goes here}

Distance-based shape classification

In this section, we exploit shape geodesics for shape classification. The alignment cost used in Eq. 4 is taken as the similarity between any two shapes.

On the basis of a general algebraic and variational framework, [START_REF] Younes | Optimal matching between shapes via elastic deformations[END_REF] has proved that the constructed cost function meets all the conditions necessary for a true distance between planar curves.

Formally, the distance between two shapes S 1 and S 2 is defined as:

d(S 1 , S 2 ) = E S 1 ,S 2 D (φ * ) where φ * = argmin φ E S 1 ,S 2 (φ) (7)
In this work, a multi-scale characterization is issued from the combination of shape matching costs at different scales. Here, the scale is defined as the resolution of shape sampling, as in [START_REF] Attalla | Robust shape similarity retrieval based on contour segmentation polygonal multiresolution and elastic matching[END_REF].

In order to exploit local and global variabilities, the distance used for shape comparison is a combination of distances measured at different scales.

Formally, the distance between shapes S 1 and S 2 is defined as follows:

d(S 1 , S 2 ) = 1 N N k=1 d k (S 1 , S 2 ) (8)
where d k is the distance defined in Equation 7between the same shapes at the k th scale and N the number of considered scales.

Assuming we are provided with a set of categorized shapes, (S l , C l ), where S l is the shape of the l th sample in the database and C l its class, the classification of a new shape S may be issued from a nearest neighbor criterion.

Distance-based shape retrieval

In addition to shape classification performance, we also address shape retrieval [START_REF] Del Bimbo | Shape indexing by multiscale representation[END_REF]. A retrieval problem consists in determining which shapes in the considered database are the most similar to a query shape. The classification accuracy of a shape descriptor does not necessarily give a relevant guess of the retrieval efficiency [START_REF] Kunttu | Multiscale fourier descriptors for defect image retrieval[END_REF]. As for classification, the distance used for shape retrieval is the distance defined in Equation 8.

Comparison to other schemes

To compare the proposed approach to the state-of-the-art shape recognition approaches, we proceed to an evaluation of shape classification and retrieval performances on the part B of the MPEG-7 shape database [START_REF] Jeannin | Description of Core Experiments for MPEG-7 Motion/Shape[END_REF]. This database is composed of a large number of different types of shapes: 70 classes of shapes with 20 examples of each class, for a total of 1400 shapes. The classes include natural and artificial objects. The shape recognition on this database is not simple because elements present outliers so that some samples are visually dissimilar from other members of their own class (Figure 6). Furthermore, there are shapes that are highly similar to examples of other classes (Figure 7).

{Figure 6 goes here} {Figure 7 goes here}

We do not discuss edge detection here; it is an obvious step in image analysis. The dataset of shape outlines are issued from an automated extraction of the outlines using the Matlab image processing toolbox 3 .

With a view to being invariant to flip transformation, the optimal matching between two shapes results from Equation 4where matching costs are computed between the first shape and the second one flipped or not.

Shape representation is given by points equally sampled along the boundary. Shape sampling at different scales with 32, 48, 64 and 192 points is considered.

Classification rates are issued from the leaving one out method where

3 Website: http://www.mathworks.com/products/image/ each shape in turn is left out of the training set and used as a query image.

Retrieval accuracy is measured by the so-called Bull's eye test [START_REF] Jeannin | Description of Core Experiments for MPEG-7 Motion/Shape[END_REF]: for every image in the database, the top 40 most similar shapes are retrieved. At most 20 of the 40 retrieved shapes are correct hits. The retrieval accuracy is measured as the ratio of the number of correct hits of all images to the highest possible number of hits which is 20 × 1400.

As mentioned in Section 3, the best shape matching in term of mean square error is obtained for α = 0.1. The results of shape classification carried out on this database do not change significantly (±0.01%) by taking α in the range [0.05, 0.2]. Note that the value of α intervenes in the process of convergence of the shape matching and not in the expression of the distance of Equation 8. In Figure 8 we report the variation of the correct shape classification rate with respect to α.

{Figure 8 goes here} {Table 2 goes here}

The proposed approach based on shape geodesics has been compared to state-of-the-art schemes for part B of the MPEG-7 dataset as reported in Table 2. Methods are categorized according to single-scale versus multi-scale and local versus global approaches. By global, we refer here to methods such that the shape descriptors hold information from all points along the shape (e.g., Fourier methods, Zernike moments) in contrast to techniques exploiting local shape features such as matching-based or wavelet-based schemes.

The proposed multi-scale approach outperforms reported schemes with a correct classification rate of 98.86% corresponding to a gain in term of correct classification rate between 0.3% and 17%. Regarding the bull's eye, a score of 89.05% is reached. This is greater by 1.35% than the best result reported previously. The highest scores of previous works are those of methods based on shape matching and/or with hierarchical analysis (shape tree, hierarchical procruste matching, string of symbols, IDSC, fixed correspondance with chance probability functions); this fact justifies the choices operated to develop the proposed approach which relies on shape matching coupled with a multi-scale analysis.

From the results reported in Table 2, one may analyze the performances of the different categories of techniques. Performances comparison between the single-scale and the multi-scale approaches shows clearly that multi-scale analysis is very relevant. The single-scale approches reach an average rate of correct classification of 94.04% and an average retrieval rate of 77.62% to be compared respectively to 97.16% and 81.91% for the multi-scale approaches.

The performances of the method presented in this paper are improved by 3.81% in correct classification rate and by 3.35% in retrieval score when considering a multi-scale analysis instead of its single-scale form. The gain both in classification and retrieval performances clearly state the relevance of the multi-scale approach for shape analysis.

Global methods are greatly outperformed by local schemes: for instance for a single-scale analysis, 86% versus 96.73% and 66.85% versus 80.85%

for the mean correct classification and retrieval rates respectively for the global techniques and local ones. The later can be argued to provide more flexibility to exploit local shape differences. As expected, a similar conclusion holds when comparing multi-scale global and local schemes. It may also be noted that matching-based schemes also depict greater performances than other local approaches (e.g., for multi-scale ones, 97.1% and 87.26% versus 95.5% and 74.77% for the mean correct classification rate and mean retrieval rate respectively).

Compared to the other matching-based approaches, the gain reported for our approach may be associated with two main features. Before all, these results stress the relevance of the chosen shape similarity measure encoding geometric invariance to translation, rotation and scaling. The second important property, often not fulfilled by matching-based schemes, is the symmetry of the similarity measure, i.e. the measure of the similarity between shape 1 and shape 2 is the same than between shape 2 and shape 1. This property is guaranteed by the fact that the matching is stated as a minimal path issue in the shape space. Regarding our multi-scale strategy, we proceed similarly to [START_REF] Daliri | Robust symbolic representation for shape recognition and retrieval[END_REF], the multi-scale similarity measure is a mean over several scales. In previous works [START_REF] Felzenszwalb | Hierarchical matching of deformable shapes[END_REF][START_REF] Mcneill | Hierarchical procrustes matching for shape retrieval[END_REF], the multi-scale analysis comes up through the shape matching process where the shape matching at a given resolution depends on all matchings performed at lower resolutions.

We further analyze the proposed multi-scale matching-based scheme for object classes depicted in Figure 9 for which a lower retrieval accuracy is reported. These shapes within these classes are highly similar, the local curvature differs in a small number of points only. Experimentally we notice that the use of the robust criterion leads to consider these data points as outliers. For example, if we focus on the nearest 20 neighbors of the samples of the class spoon, more than 50% are elements of the classes watch, pencil, key and bottle; if we use the similarity measure without the robust weights, 95% of the nearest 20 neighbors are of the same class, spoon. Using robust weights, the average retreival accuracy is penalized due to the low accuracies obtained for these 6 classes, but overall it remains greater than without the use of the robust weights.

{Figure 9 goes here} Future work will explore the combination of the proposed approach to kernel-based statistical-learning. Recently, in [START_REF] Yang | Improving shape retrieval by learning graph transduction[END_REF] authors propose to combine classical metrics to learning through graph transduction. It has been shown that this approach yields significant improvements on retrieval accuracies. For example, the retrieval rate using the IDSC [START_REF] Ling | Shape classification using the inner-distance[END_REF] is improved by 5.6% when combined to the learning graph transduction. We will focus on the combination of machine learning techniques such as random forest and SVMs to the proposed multi-scale matching-based similarity measure. Table 1: Optima M SE θ obtained by the robust and the non robust algorithms with the gain due to the robust solution for initializations of φ at points which are far from the correct solution from different angles. This experiment is carried out on synthetic shapes

  θ(s). A rotation of angle c transforms the function θ(s) into the function θ(s) + c modulo 2π. For rotation invariance, the minimization of SM Γ, Γ(φ)

  with a representation of the used transformation function φ. {Figure 1 goes here} In Figure 2 we report the mean square error M SE θ = E θ -θ(φ) 2 obtained for different values of α ∈ [0, 1]. This result is issued from the dynamic programming algorithm. For high values of α, the regularity term is favored over the similarity measure and the alignment results in high M SE θ values. For small values of α, the robust algorithm ensures solutions with smaller errors (M SE θ = 0.085) corresponding to M SE φ = E |φ applied -φ estimated | 2 ≈ 0.001. The gain 2 due to the robust solution is represented in Figure 2(b); this gain is optimum for α = 0 and reaches 90%. The aligned shapes given in Figures 2(c) and 2(d) show the superiority of the robust solution. The consistency of this result has been verified by testing many transformation functions with different shapes.{Figure 2 goes here} Using the incremental iterative scheme, the minimization leads to the same optimum as the dynamic programming except for α = 0. For the iterative scheme the regularity term is necessary, α should have a nonzero value to lead to a unique solution. Experimentally, a value of α in the range [0.1, 0.2] is optimal.

  with minor errors. The transformation estimated by the non robust algorithm (Figure 4(b)) is in contrast far from the real one (Figure 1(b)).

Figure 1 :

 1 Figure 1: Test on synthetic shapes. We have applied a known transformation (1(b)) on the shape of 1(a) to get the shape 1(c). s and s are the normalized curvilinear abscissas on the curves.

, and a term that penalizes the torsion and stretching along the curve, ( φ s (s)).

The regularization term is considered in order to obtain a smooth transformation function.

Acknowledgement

The authors would like to thank Jean Le Bihan for fruitful discussions.

 [START_REF] Belongie | Shape matching and object recognition using shape contexts[END_REF]Parts correspondence 76.45% N A [START_REF] Latecki | Application of planar shape comparison to object retrieval in image databases[END_REF] Curve edit distance 78.17% N A [START_REF] Sebastian | On aligning curves[END_REF] Inner-distance shape context (IDSC) 85.40% N A [START_REF] Ling | Shape classification using the inner-distance[END_REF] Racer 79.09% 96.8% [START_REF] Super | Improving object recognition accuracy and speed through nonuniform sampling[END_REF] Normalized squared distance 79.36% 96.9% [START_REF] Super | Improving object recognition accuracy and speed through nonuniform sampling[END_REF] Fixed correspondence 80.78% 97% [START_REF] Super | Retrieval from shape databases using chance probabil-ity functions and fixed correspondence[END_REF] Fixed correspondence + Chance 83.04% 97.2%

probability functions [START_REF] Super | Retrieval from shape databases using chance probabil-ity functions and fixed correspondence[END_REF] Fixed correspondence + aggregated-pose 84% 97.4%

chance probability functions [START_REF] Super | Retrieval from shape databases using chance probabil-ity functions and fixed correspondence[END_REF] Proposed