Halim Benhabiles

Guillaume Lavoué

Jean-Philippe Vandeborre

Mohamed Daoudi

Kinematic skeleton extraction based on motion boundaries for 3D dynamic meshes

Keywords: (according to ACM CCS): I.3.5 [Computer Graphics]: Computational Geometry and Object Modeling -Curve, surface, solid, and object representations

This paper presents a precise kinematic skeleton extraction method for 3D dynamic meshes. Contrary to previous methods, our method is based on the computation of motion boundaries instead of detecting object parts characterized by rigid transformations. Thanks to a learned boundary edge function, we are able to compute efficiently a set of motion boundaries which in fact correspond to all possible articulations of the 3D object. Moreover, the boundaries are detected even if the parts linked to an object's articulation are immobile over time. The different boundaries are then used to extract the kinematic skeleton. Experiments show that our algorithm produces more precise skeletons compared to previous methods.

Introduction

With the recent progress of acquisition systems, and the increasing of the processor calculation power, the use of dynamic surfaces in the multimedia domain has become important. This kind of data can be created by a designer using animation softwares, or obtained from a scanner, or a scientific simulation. Generally, the dynamic surface is represented as a sequence of 3D meshes (ie. a sequence of frames) with constant connectivity, and time-varying geometry (the position of vertices changes over time). Similarly to static meshes, dynamic meshes require to be pre-processed before being used in a given application. They mainly need a structural representation such as a skeleton which is a key ingredient for their modeling and editing. Few existing works in the literature propose to extract a kinematic skeleton for these dynamic meshes [dATTS08, SY07, AKcPT04]. They basically make use of motion-based geometric segmentation methods [ABH * 10,LWC06]. These methods seek to decompose the dynamic mesh into rigid parts by exploiting the temporal information. They assume that the vertices of such parts are characterized by a uniform motion with a single rigid transformation along the sequence. Once the parts are determined, an articulated skeleton is computed.

The main drawback of this kind of methods is the fact that they are limited to exploit only the temporal information for extracting the different parts of the shape. Indeed, such method cannot be suited to detect the relevant (ie. functional) parts of the shape which are immobile along the sequence of meshes. Thus, using the resulting computed skeleton from this kind of methods will not allow to apply any deformation on these latter parts for instance. Tierny et al. [TVD08] proposed to represent the 3D object by a set of level lines (or contours) and then keep only those that maximize an edge-length deviation function over time. This latter function allows to capture the articulations of the object. Indeed, the edges located at these articulations undergo a significant variation (edges are stretched) during the movement of the parts linked to them. However, once again this function fails to capture the articulations when the parts linked to them are immobile over time.

In this paper we propose a precise kinematic skeleton extraction method for dynamic meshes. The method is based on computing a set of motion boundaries, that correspond to the articulations of the object, for the whole sequence of meshes. To this end, a set of interest regions is computed independently for each frame of the sequence. The calcu- lation of these regions is based on the geometry. Then, all the regions computed over the sequence are gathered into one single set to create a unique segmentation for the whole dynamic mesh. To summarize, we obtain a unique segmentation for the whole dynamic mesh that is based both on motion and geometric features. Finally, the skeleton is extracted from this latter segmentation. The main contribution of this work is the following. We present a hybrid technique which combines both static and dynamic information to identify all possible articulations of the object even if its parts are immobile along the sequence of meshes. Moreover, with this approach, the computed motion boundaries (and thus the skeleton nodes) are very precise.

Overview of the approach

Given an input dynamic mesh, our method begins by extracting a set of interest regions along the different frames (in red, in figure 1(a,b,c)) and then merging them (figure 1(d)). This step is described in section 3. The set of extracted interest regions along the sequence provides an information about all possible articulations of the object. Next, the interest regions are transformed into thin, closed and smooth contours (figure 1(e)) using a post-processing pipeline described in section 4. Finally, these contours are used to compute the skeleton (figure 1(f)). This latter step is described in section 5.

Extracting and merging interest regions

To extract the set of interest regions on a given frame of the sequence, we use a boundary edge function defined in [BLVD11]. This function is a weighted combination of a set of geometric criteria, which is learned in an offline step with the AdaBoost [FS97] classifier using a ground-truth of manually segmented models. This framework was recently introduced in [BLVD11] for segmentation of static meshes. The classifier takes as input a training dataset (we used the princeton segmentation benchmark [START_REF] Golovinskiy | A benchmark for 3d mesh segmentation[END_REF]) and generates the boundary edge function. The training dataset is composed of a set of feature vectors F E computed for each edge of the ground-truth of static meshes. A feature vector F E of a given edge contains a set of 33 geometric criteria such as curvature [KvD92], shape diameter function [START_REF] Shapira | Consistent mesh partitioning and skeletonisation using the shape diameter function[END_REF], and is associated with its proper class label L so that L = +1 if the edge is a boundary (according to the manual segmentations of the mesh containing this edge) and L = -1 if the edge is not a boundary. Once the learning is done, the classifier produces the boundary edge function. This function is a weighted combination of the set of geometric criteria. It takes as input a feature vector from any given edge and outputs a signed scalar value whose sign will provide the estimated classification of the edge (positive for boundary and negative for non-boundary). Figure 2 illustrates the learning step for the edge function construction.

The use of the boundary edge function on each frame of the dynamic mesh leads to produce a set of regions (figure 1(a,b,c)), each of which is represented by a set of connected edges of the mesh. These regions, only computed using geometry, all correspond to possible articulations of the object. This result was expected since the boundary function is learned from human manual segmentations. Indeed people tend to segment an object by defining boundaries that separate its different functional parts [HS97]. However, if we consider only one given frame, we can notice that we never detect all possible articulations, indeed it depends on the pose of the animated object on the frame. Hence, we propose to merge all regions along the sequence, in order to cover all possible articulations that appear over time. In other words, this merging allows to exploit the temporal information. Note that the merging operation makes use of the OR operator applied on the boundary edge function from the different frames, and does not require any processing since the dynamic mesh is represented by a sequence of meshes with constant connectivity (vertex to vertex correspondence).

Post-processing pipeline

The extracted interest regions cannot be used directly for computing the skeleton. Consequently, they need to be processed. To this end, we use the processing pipeline introduced for static mesh segmentation in [BLVD11] that comprises three stages. In the first stage, for each interest region (a set of connected edges), a thinning algorithm is applied. This latter algorithm allows to thin the interest region to a piecewise linear contour. Next, each open contour is completed to form a closed boundary around a specific part of the object (figure 1(e)). The principle is to find the weighted shortest path between the two endpoints of the contour while minimizing a cost function based on the boundary edge function. At this step we have created a set of closed contours. Finally, each contour is optimized, in term of smoothness and precision, using a snake movement based also on the boundary edge function. In other terms the contours are enforced to be closed as much as possible to the articulations of the object.

Skeleton computation

To compute the skeleton, we use a simple algorithm which takes as input the dynamic mesh together with the set of closed boundaries and gives as output a structure composed of a set of edges and points that represents the kinematic skeleton (figure 1(f)).

The algorithm begins by computing the centroids of both boundaries and segments (ie. regions separated by the boundaries), then it connects each boundary centroid (red points in figure 1(f)) with its two adjacent segment centroids (blue points in figure 1(f)). Two segments are adjacent if they share the same boundary edges or a part of them. However, it is possible that a part of a given boundary be shared between more than two segments. Figure 3(a) illustrates an example in which three segments are adjacent since they share a common part of their boundaries (see the magenta part in the figure). In this latter case, each boundary is connected with the two segments that share its maximum common part as illustrated in figure 3(b).

Experiments and results

Figure 4 shows some dynamic surfaces and their extracted kinematic skeletons. One can notice that the obtained skeletons describe efficiently the dynamic meshes thanks to the motion boundaries (in red). Indeed, each boundary correspond to an articulation of the object. Moreover, the rigid parts are easily captured since they are limited by motion boundaries. Consequently, these rigid parts can undergo motions by simple rotations, and thus edit the dynamic shape without any difficulty. [TVD08] and our algorithm are better since they detect both kinds of articulations (mobile and immobile). However, our skeleton is slightly more accurate in terms of position of motion nodes (red points) thanks to the boundary edge function.

The whole process for computing the kinematic skeleton runs at reasonable time (in seconds, and only few minutes in the worst case). Table 1 summarizes the running time for all models presented in this paper. The experiments were carried out on a 3 GHz Intel(R) Core(TM) 2 Duo CPU with 4 Gb memory. One can notice that the running time is more important when the number of frames increases. This is due to the fact that the edge function is computed for all edges of each frame. However, the computation process is done independently from a frame to another. Moreover, it is done independently from an edge to another. Thus, the process can be easily parallelized which will decrease the running time considerably.

Dynamic-mesh

Conclusion

In this paper, we presented an automatic method that allows to extract kinematic skeletons for dynamic surfaces. The method is based on motion boundary extraction. We have shown through some experiments that our method allows to extract precise skeleton represented by a set of motion nodes that correspond to all articulations of the object. Morover, the skeleton includes rigid nodes which correspond to object's parts characterized by uniform motion. Hence the dynamic object can be edited easily by applying simple rotations on these latter nodes.

For future work, we would like to generalize our method for dynamic shapes with variable connectivity. In this latter case, merging the interest regions extracted along the sequence of a given shape is not obvious. Indeed, we need to pre-process the sequence in such way that each frame has a vertex to vertex correspondence with the next one.

Figure 1 :

 1 Figure 1: Overview of our kinematic skeleton extraction method: extracting interest regions for each frame (a,b,c), merging the regions (d), computing boundaries (e), computing skeleton (f).

Figure 2 :

 2 Figure 2: Learning the boundary edge function.

Figure 3 :

 3 Figure 3: Example of three adjacent segments (a), and the resulting skeleton (b).

Figure 5

 5 Figure 5 shows a visual comparison between our algorithm and those from the state-of-the-art applied on the horse model. The figure clearly shows that the algorithm from Lee et al. [LWC06] fails to detect the different articulations of the legs although these latter ones are characterized by motions. The algorithm from Aguira et al. [dATTS08] overcomes this

Figure 4 :

 4 Figure 4: For each row, dynamic surfaces and their corresponding kinematic skeletons. c The Eurographics Association 2012.

Figure 5 :

 5 Figure 5: From left to right: segmentation obtained by Lee et al. [LWC06], skeleton obtained by: Aguira et al. [dATTS08], Tierny et al. [TVD08], and our algorithm.

  drawback, but it fails to detect the articulations of immobile parts of the model such as the ears. The results obtained by the algorithm from Tierny et al.

Table 1 :

 1 Computation time for kinematic skeleton extraction of some dynamic meshes.

		Vertices Frames Skeleton (s.)
	Cat	7207	10	37
	Dance	7061	201	411
	Horse	8431	49	204
	Lion	7207	10	28

c The Eurographics Association 2012.

ACKNOWLEDGMENTS

This work has been supported by the ANR (Agence Nationale de la Recherche, France) through MADRAS project (ANR-07-MDCO-015).


Olivier Bouba-Olga

CRIEF Marie Ferru

Does Geographical Proximity Still Matter? An Empirical Analysis of Two Long-Term Relational Databases

Keywords: geographical proximity, collaborations, research, science-industry JEL Codes: O31, R12, O39

The purpose of this article is to provide possible answers, at an empirical level, to the question "Does geographical proximity still matter in collaborations for innovation?", since the lack of available data has made it impossible to provide real answers up to now. Relying on two real longterm relational databases relating to science-industry collaborations in France, and on two complementary indicators of geographical proximity, we will show that proximity continues to count (number of significant intradepartmental collaborations and low average distance between the partners). However, this dynamic analysis does allow us to state that the closest partnerships and the most distant ones increase the most over the study period. We shall also show that the role of geographical proximity and its evolution over the course of time differ according to the type of science-industry contract and the sectoral specialisation of the partners.

Introduction

As Morgan (2004, p.3) stressed, "Globalization and digitilization have been presented as ineluctable forces which signal the death of geography."" The development of CIT and the means of transport will lead to a global economic world in which distance no longer matters [START_REF] Castells | The Rise of the Network Society[END_REF][START_REF] Cairncross | The Death of Distance: How the Communications Revolution will Change Our Lives[END_REF]. Innovation activities would seem to be an exception to this process in the view of many authors. Their strong polarisation seen since the late 1990s [START_REF] Puga | The rise and fall of regional inequalities[END_REF]Caniëls, 1997;Lallement et al., 2007, etc.) and the persistence of the effects of geographical proximity deriving from it are said to come from the tacit nature of the knowledge exchanged, from the existence of social networks among partners developed locally, from the intervention of policies, etc.

From an empirical standpoint, "the death of distance hypothesis has not been proven" (Frenken et al., 2010) in research collaborations and the studies done suffer from important limitations, given the poor availability of data. Indeed, not only is it the case that "most of the existing contributions on this matter lack data at the individual level" [START_REF] Giuri | Inventors and the geographical breadth of knowledge spillovers, druid working paper[END_REF], but also and most especially "many studies on proximity and innovation have been analysed from a static perspective" [START_REF] Boschma R | Proximity and innovation: a critical assessment[END_REF]. Hence, although the question of geographical proximity in research collaborations has already been raised by many studies (see in particular [START_REF] Oinas | Distance and learning: does proximity matter? In s[END_REF][START_REF] Lublinski | Does geographic proximity matter? Evidence from clustered and non-clustered aeronautic firms in Germany[END_REF], none really provides an answer to the question "Does geographical proximity still matter?"

In this article, we try to provide possible answers to this question through an empirical study based on an exploration of two real long-term relational databases. These databases include substantial information relating to more than 30,000 science-industry collaborations carried out in France between 1986 and 2005, such as the location of the scientific and technical partners, their specialisation and the date of the project. These data enable us to analyse the importance and evolution of geographical proximity for two types of collaborations, with part of the partnerships studied involving CIFRE contracts, and the other part CNRS contracts (see below for more information about these two types of contracts). This comparative analysis appears all the more interesting in that we can expect results that differ according to the nature of the contract: the need for geographical proximity could be greater in CIFRE collaborations, since these contracts rely on the research work of a doctoral candidate alternating time at the firm and time in the laboratory.

We propose to conduct an empirical analysis of these two databases by adopting complementary strategies for defining geographical proximity: i) we measure it first using a relative-distance indicator, the travel time by train between the two capitals of the regions where the two partners are located, ii) we then formulate a typology of the spatial scales of collaboration making it possible to define different degrees of geographical proximity. More specifically, we distinguish collaborations within the same department (DEP), those between departments in the same region (REG), collaborations between adjoining regions (LIMITROPHE), those with the capital region (ICAP) and finally those between nonadjoining regions outside the capital region (IREG).

Initially in our empirical analysis we measure the evolution over the period of the time-distances and each category of our typology and test the existence of a trend, relying on nonparametric tests (Kendall's tau), making distinctions according to the nature of the contract (CIFRE vs. CNRS). Then we test the influence of various potential determinants (the year the contract was made, the firm's business sector or the laboratory's research domain) on the effects of geographical proximity using complementary econometric models: the first model (multinomial logit) measures the effects of proximity through the spatial scales typology, whereas the second (sample selection model, Heckman two-step) measures the influence of the same determinants on the time-distance between the partners.

The rest of the article is organised as follows. We conduct a review of the literature in the second section, stressing the limitations inherent in the empirical work done to that point. In the third section, we present the data before specifying the methodology applied to exploring our two databases. In the fourth section, we give the first descriptive statistics and the key results from the econometric processing done. We then conclude and discuss these results in the final section.

Review of the literature

For many years there has been an ongoing debate over the importance of proximity in research collaborations: "The relevance of proximity is one of the most controversially discussed topics in the context of innovative linkages and networks" (Sternberg, 1999, p.553). [START_REF] Knoben | Proximity and inter-organizational collaboration: a literature review[END_REF], in a review of the literature on the subject underscore the especially significant value attached to geographical proximity ("geographical proximity (…) is the most frequently used dimension of proximity in the literature" (p.74)) and inventory 19 works linking geographical proximity and collaborations This debate is based essentially on the evolutionist theory developed in the 1980s, according to which the tacit knowledge exchanged during the collaboration process is by definition not codifiable and therefore cannot be distributed easily in space. This led some authors [START_REF] Verspagen | Europe: one or several systems of innovation[END_REF]Patel and Pavitt, 1994 in particular) to consider that only face-to-face relationships make it possible to benefit from it. For example, [START_REF] Foray | Distribution et expansion de la base de connaissances scientifiques et technologiques[END_REF] states that "the aptitude to assimilate and transfer scientific and technological knowledge that is not completely codified is largely dependent on opportunities for direct personal contact between the concerned parties"(p. 19). Even though it has thus been commonly accepted that geographical proximity promotes the development of collaborations (by reducing all of the transaction costs), "popular belief holds that geography no longer matters in scientific collaborations with the arrival of cheap air travel, English as a global language and the internet" [START_REF] Frenken | The citation impact of research collaboration in science-based industries: a spatial-institutional analysis[END_REF]. Geographical proximity would then constitute less and less a necessary or sufficient condition for the realisation of research partnerships [START_REF] Boschma R | Proximity and innovation: a critical assessment[END_REF][START_REF]Dynamique de proximité[END_REF][START_REF] Bunnell | Spaces and scales of innovation[END_REF][START_REF] Breschi | Mobility and social networks: Localized knowledge spillovers revisited[END_REF][START_REF] Gertler | Tacit knowledge and the economic geography of context, or the undefinable tacitness of being (there)[END_REF].

At an empirical level, despite the development of studies seeking to measure the importance of geographical proximity, "little is known about the role of geographical proximity in science collaborations" [START_REF] Ponds R | The geographical and institutional proximity of research collaboration[END_REF] and "the death of distance hypothesis has not been proven" [START_REF] Frenken | The citation impact of research collaboration in science-based industries: a spatial-institutional analysis[END_REF]. The results obtained vary greatly from study to study: whereas some attest to an increase over time in long-distance partnerships [START_REF] Frenken | Spatial scientometrics: towards a cumulative research program[END_REF][START_REF] Narin | Scientific cooperation in europe and the citation of multinationally authored papers[END_REF][START_REF] Luukkonen | The measurement of international scientific collaboration[END_REF][START_REF] Frenken | A new indicator of european integration and an application to collaboration in scientific research[END_REF]Magioni and Uberti, 2007;[START_REF] Wagner | Network structure, self-organization, and the growth of international collaboration in science[END_REF], others on the contrary show that geographic distance still plays a significant role still today in the creation of European research collaborations [START_REF] Bibliography | Social distance versus spatial distance in R&D cooperation: empirical evidence from European collaboration choices in micro and nanotechnologies[END_REF][START_REF] Maggioni | Knowledge networks across europe: which distance matters?[END_REF]Scherngell and Barber 2009). Likewise, and above all, the existing empirical studies suffer from three major limitations.

1) The first limitation comes from the quality of the data, and more especially of the collaboration indicators applied. The econometric models pertaining to the "geography of innovation" [START_REF] Feldman | The geography of innovation[END_REF] -and particularly those that initially took into account the strong polarisation of innovation activities -rely on aggregate data such as patents, volume of expenditures, number of employees in R&D, etc. In these studies, interactions between actors are therefore not really observed but merely assumed, and the models thus account for the co-presence of actors and not true collaborations. Other, more recent studies measure collaborations through citations or participation in joint projects [START_REF] Bibliography | Social distance versus spatial distance in R&D cooperation: empirical evidence from European collaboration choices in micro and nanotechnologies[END_REF]Scherngell and Barber, 2009;[START_REF] Iammarino S | The spatial profile of university-business research partnerships[END_REF]. Although these data make it possible to better understand interactions between actors than the previous data, the realisation of a true collaboration between partners is merely assumed: in some types of collaborations, as is the case with European partnerships in particular (EU Framework Program), the number of partners is such that it is not possible for all of the partners to have really collaborated during the project. It seems that "very few papers use data on direct collaborative agreements on R&D" [START_REF] Massard | Proximity and innovation through an "accessibility to knowledge" lens[END_REF]. Only studies based on data on co-patents (Maggioni et al., 2007) or co-publications [START_REF] Katz | Geographic proximity and scientific collaboration[END_REF][START_REF] Ponds R | The geographical and institutional proximity of research collaboration[END_REF][START_REF] Frenken | The citation impact of research collaboration in science-based industries: a spatial-institutional analysis[END_REF][START_REF] Hoekman | Research collaboration at a distance: changing spatial patterns of scientific collaboration within Europe[END_REF][START_REF] Scherngell | Collaborative Knowledge Production in China: Regional Evidence from a Gravity Model Approach[END_REF] or even more so those bearing on dyadic collaboration relationships [START_REF] Laursen | Exploring the Effect of Geographical Proximity and University Quality on University-Industry Collaboration in the United Kingdom[END_REF][START_REF] Levy R | Study of science-industry collaborative patterns in a large european university[END_REF][START_REF] Grossetti | La structure spatiale des relations science-industrie en france: l'exemple des contrats entre les entreprises et les laboratoires CNRS[END_REF] can truly account for a collaboration relationship between the actors and in our view constitute true relational databases.

2) A second problem appears as to the indicator of geographical proximity applied. "The definition of this dimension of proximity differs slightly between different authors (…) with regard to the scale at which geographical proximity is defined" (Knoben and Oerlemans, 2006, p.74). Some authors evaluate proximity using a binary variable distinguishing national collaborations from international collaborations [START_REF] Ponds R | The geographical and institutional proximity of research collaboration[END_REF]; others consider that geographical proximity exists beyond regional borders and evaluate it at the NUTS 2 level (Scherngell and Barber, 2009;[START_REF] Hoekman | Research collaboration at a distance: changing spatial patterns of scientific collaboration within Europe[END_REF]) or using an ordinal measurement (for example, [START_REF] Drejer | Searching Near and Far: Determinants of Innovative Firms' Propensity to Collaborate Across Geographical Distance[END_REF] distinguish intraregional, intra-national and international collaborations). Understood as such, geographical proximity seems too broad to be able to verify the hypothesis according to which proximity makes face-to-face interactions easier. The regional level (NUTS 3 level) as well as the use of a maximum kilometric distance indicator (under 100 miles for [START_REF] Laursen | Exploring the Effect of Geographical Proximity and University Quality on University-Industry Collaboration in the United Kingdom[END_REF], for example) seem more relevant, even though they may prove too broad for certain territories. Yet to our knowledge there are few studies that allow a proximity analysis at a more refined level (department, town). In the same way, some studies have shown the importance of geographical proximity in testing the role of administrative boundaries [START_REF] Hoekman | Research collaboration at a distance: changing spatial patterns of scientific collaboration within Europe[END_REF], but very few have considered the specificities relating to the studied territories such as "capital effects" or "adjacent-regions effects" with the exception of [START_REF] Grossetti | La structure spatiale des relations science-industrie en france: l'exemple des contrats entre les entreprises et les laboratoires CNRS[END_REF] who underscore the hypertrophy of the Ile-de-France region in French collaborations. In short, and especially, considering the development of the means of transport, it seems to us important to test relative-distance indicators, by taking into account, for example, transport time or cost. Finally, it appears that "the geographical dimension is in complex ways related to other mechanisms that are still barely identified and that take place at different geographical levels" (cf. [START_REF] Bibliography | Social distance versus spatial distance in R&D cooperation: empirical evidence from European collaboration choices in micro and nanotechnologies[END_REF], showing the need to compare different indicators of geographical proximity.

3) In short, and especially, "many studies on proximity and innovation have been analysed from a static perspective" [START_REF] Boschma R | Proximity and innovation: a critical assessment[END_REF]. Very few studies are based on longitudinal data and therefore do not generally take into account the evolution of geographical proximity, with the exception of [START_REF] Hoekman | Research collaboration at a distance: changing spatial patterns of scientific collaboration within Europe[END_REF] and [START_REF] Grossetti | La structure spatiale des relations science-industrie en france: l'exemple des contrats entre les entreprises et les laboratoires CNRS[END_REF]. For 33 European countries, the former underscore the persistence of local collaborations (taken at the NUTS 2 level) "and collaborations within territorial borders did decrease" between 2000 and 2007; the latter show the increase in local collaborations between 1986 and 1998 for France.

On the basis of these various studies and the limitations inherent in them, we seek to complement the existing literature through an exploration of two genuine long-term relational databases and a comparison of various indicators of geographical proximity.

Data and method

Data

In this article, we make use of two complementary databases: the CIFRE base and the CNRS base. The former brings together all of the science-industry contracts carried out as part of Conventions Industrielles de Formation par la Recherche [Industrial Agreements for Training through Research] -CIFRE-between 1981 and 2005. Since 1981, the CIFRE system has been subsidising any company under French law that hires a doctoral candidate and places him or her in a research collaboration with a public laboratory. These research contracts are in large part funded by the Ministry of Higher Education and Research. The second database brings together various types of information relating to research contracts carried out between 1986 and 2006 between French firms and laboratories under the Centre National de la Recherche Scientifique [National Scientific Research Centre] -CNRS -the main government research agency in France.

[TABLE 1]

For each base, we have information for the year the contract was signed (ANNEE), the regional location of the laboratory involved (REGLAB), the regional location of the company (REGETAB), the company's sector (SECTEUR) and the laboratory's scientific domain (DOMAINE). In the case of these last two variables, a major problem arises, since the nomenclatures used by the ANRT is not the same as that ordinarily used. We therefore had to aggregate the categories available in the CNRS base and construct a transfer matrix between the ANRT and CNRS nomenclatures. In the end, we were able to divide up the contracts into three sectors and six scientific domains. We have an aggregate base of 32,764 observations completely filled in, including 23,954 CNRS contracts and 8,810 CIFRE contracts, for the period 1985-2006. Table 1 shows the qualitative variables available in the two databases used.

Method

In order to analyse the evolution of the geographical proximity of the collaborators, we propose adopting two complementary strategies.

The first strategy consists of defining a typology (TYPO) of the spatial scales used, composed of five categories: *TYPO=DEP when the contract concerns two partners located in the same department; *TYPO=REG when the two partners are located in two different departments in the same region, *TYPO=LIMITROPHE if the two partners are located in two adjoining regions, *TYPO=ICAP when one of the partners is located in the capital region (Ile-de-France) and the other partner is located in another region, *TYPO=IREG when the two partners are located in two different regions outside the Ile-de-France.

In our view, this typology provides a better understanding of geographical proximity than is generally achieved in empirical studies. Four of the five categories define decreasing degrees of geographical proximity measured in terms of physical distance: the relationships within the same department are the closest geographically (DEP), followed by those in the same region (REG), then those between adjoining regions (LIMITROPHE) and, finally, those between different regions outside the capital (IREG). The last category in the typology (ICAP) takes into account the specific nature of French geography, the capital region being at the heart of the country's network of transport infrastructure, whether the road, rail or air networks.

The second, more classic strategy consists of using a relative measurement of geographical proximity between actors, namely, travel time by train between the two capitals of the regions where the actors are located (TRAIN variable). This measurement seems to us more satisfactory than the kilometric distance between regional capitals, which is often used. An even more satisfactory alternative would certainly have been to measure the distance not between the regional capitals but between the actors' precise locations. Unfortunately, the data used are not geo-localised, which prevents us from taking that approach.

Methodologically, we propose presenting, first, various descriptive statistics that capture that temporal evolution of geographical proximity by distinguishing all CNRS contracts from the CIFRE contracts. We seek to verify the existence or absence of temporal trends by conducting nonparametric tests (Kendall's tau) between each variable and the time t. We then propose estimating two complementary econometric models. The first model is a multinomial logit, with the TYPO variable as the explained variable. The second model is a Heckman model with selection equation: the first equation (selection equation) estimates the likelihood that the collaboration between two actors is interregional (INTER=1) rather than infraregional (INTER=0); the second equation (output equation) estimates the time-distance by train between the two collaborators.

In both models, the explanatory variables are the same: i) the year of the contract (ANNEE), ii) the nature of the contract (CIFRE vs. CNRS), iii) the company's sector (INDUSTRY, SERVICES, OTHERS), iv) the laboratory's scientific domain (PHYSICS-MATHEMATICS, CHEMISTRY, ASTROPHYSICAL SCIENCES, LIFE SCIENCES, HUMAN AND SOCIAL SCIENCES, ENGINEERING SCIENCES, INFORMATION).

Results

Descriptive statistics

After measuring the evolution of geographical proximity over the study period, we first constructed three complementary graphs (cf. graph 1a, 1b, 1c). The first one shows the evolution for all CNRS contracts of the share of each mode in our typology. The second graph does the same for all CIFRE contracts. The third measures the evolution of the average time-distance between the two regional capitals where the partners are located. [GRAPH 1a,1b,1c] Several of the results are worth highlighting.

In the case of CNRS contracts (graph 1a), the most noteworthy result is the significant drop in the share of interregional contracts involving the capital region (ICAP): for the period, it goes from nearly 60% to around 40%, a drop of twenty points in about twenty years. How can this significant drop be explained? One possible hypothesis, in our view, has to do with the spatial dispersal of CNRS researchers, which led to a rebalancing in favour of the provincial regions and to the detriment of the capital region. Unfortunately, we do not have the data necessary to confirm this hypothesis, but it does correspond to the results obtained at the start of our period of observation by [START_REF] Grossetti | La structure spatiale des relations science-industrie en france: l'exemple des contrats entre les entreprises et les laboratoires CNRS[END_REF]. We also see an increase in the share of CNRS contracts within the same department (DEP), from around 10% to more than 20%. The typology's other modes seem more stable.

Comparatively speaking, the evolution observed for CIFRE contracts (graph 1b) shows a very strong inertia in the geography of the collaborations, with the share of each mode seeming especially stable. A comparison of the two graphs (1a and 1b) thus shows that the evolution of the geography of collaborations differs greatly according to the nature of the science-industry contracts (CIFRE vs. CNRS). However, if we focus on the end-of-period data, we see that the classification of the various typology modes is the same for both types of contracts: these are interregional relationships, with the capital region dominating, followed by intradepartmental relationships and then by infraregional relationships between departments.

The graph (1c) illustrating the evolution of the average time-distances also provides interesting clarifications. If we focus first on all contracts (CIFRE_TOTAL and CNRS_TOTAL curves), we observe that CIFRE contracts are implemented with partners who are geographically closer than the CMRS contracts. This can be viewed as a confirmation of the hypothesis formulated in our introduction: under CIFRE contracts, the doctoral candidate must alternate periods with the firm and periods at the laboratory; greater geographical proximity between actors may be sought in order to reduce travel costs -and more generally all the transaction costs -that the doctoral candidate has to bear. In the case of the subset of interregional contracts, the average distances differ only slightly between the two types of contracts. However, we do note one important difference: the average distance appears stable for CIFRE contracts, whereas it increases for CNRS contracts.

To test the validity of these evolutions, we tried to identify the existence of increasing or decreasing trends. Considering the small number of points in our sample (20 years), we opted for nonparametric rank-correlation tests (Kendall's tau).

[TABLE 2]

The results observed confirm the reading of the graphs. We see a strong inertia for CIFRE contracts, since only the REG mode shows a rather insignificant trend. In the case of CNRS contracts, all modes present significant trends. The strongest coefficients are seen for intradepartmental relationships (increasing trend) and for relationships with the capital region (decreasing trend). An analysis of the time-distances over the study period also shows an increasing trend for interregional relationships in CNRS partnerships. The nonparametric rank-correlation tests thus confirm the existence of a special dynamic that differs according to the nature of the contract: a relative stability in the geography of CIFRE contracts vs. a significant evolution for CNRS contracts.

Estimate of econometric models

To confirm or invalidate these initial results by including any sectoral effects (business sectors on the company side and scientific domains on the laboratory side), we proceeded to estimate the two econometric models presented above. The first model is a multinomial logit, with the TYPO variable as the explained variable. The multinomial logit's reference mode is the DEP variable, which takes the value 1 if the contract is interdepartmental and the value 0 otherwise.

[TABLE 3]

For the evolution of the geography of collaborations, we find that the ANNEE [year] variable is significant for three of the spatial scales (REG, ICAP and IREG), with a negative coefficient for the first two and positive for the last. This confirms the dual evolution of the geography of collaborations: increase in the share of local collaborations and increase in the share of the most distant interregional collaborations. As for the nature of the collaborations, hen CIFREW variable is still significant, and the coefficients are systematically negative. These results demonstrate the far more local nature of the CIFRE contracts, which can be explained, as we have said, by the constraint on the doctoral candidate to alternate periods at the firm and periods in the laboratory.

We also observe sectoral effects. In the case of scientific domains, the astrophysical sciences have systematically negative and significant coefficients, which means that this is a domain with which we can associate far more local contracts than for the reference domain (mathematics and physics). In contrast, the chemical sciences have positive coefficients for three of the four modalities, which indicates a less local geography. Another finding: the human and social sciences have a very significant negative coefficient for the IREG and ICAP modes -in other words, for the more distant collaborations. This scientific domain is therefore favourable to more local collaborations, at the level of departments, region or adjacent regions. For the life sciences, the results are more contrasting: negative coefficients for REG and ICAP, positive coefficients for IREG and LIMITROPHE, signs of contradictory tendencies in terms of evolution of the geography of collaborations for this scientific domain. The last two domains (engineering sciences and information sciences) present few significant coefficients.

In terms of business sectors, the main result concerns the services sector, compared to the reference sector (industry). In fact, the services sector presents systematically significant (at the 1% threshold) and negative coefficients. In relation to industry, this sector therefore has a very strong influence on the likelihood that the contract is local (at the department level). For the more heterogeneous set of other sectors, the coefficients are also significant; three are negative (REG, IREG, LIMITROPHE) and one is positive (ICAP).

The second model is a sample selection model (Heckman two-step), with, as variable, the interregional vs. infraregional nature of the collaboration in the selection equation and time-distance by train between the capitals of the regions where the actors are located in the output equation.

[TABLE 4]

First of all, the model appears to be satisfactory overall. We should also note that the Mills ratio is significant, which confirms the choice of the econometric model adopted. Several interesting, more specific results need to be underscored. In the case of temporal effects, first, we see a negative effect of the ANNEE [year] variable on the likelihood that the contract is interregional, proof of the tendency toward reinforcement of the role of geographical proximity over the period, which we have already reported. However, at the same time, with this model we see that this variable exerts a positive effect on the distance between the partners for interregional contracts. Hence we again find one essential result running through our article: the evolution of the geography of collaborations seems to take the form of a reinforcement of both the most local relationships and the most distant relationships.

The CIFRE variable exerts the same influence as the ANNEE [year] variable: a very significant negative influence on the likelihood that the contract is interregional and at the same time a positive but rather insignificant influence on the distance between the interregional partners.

In the case of sectoral effects, there are not very many of them, and they are not very significant in the output equation, with the exception of the "Others" business sector, which result is, however, difficult to interpret. On the other hand, several very negative effects are to be noted in the selection equation: the human and social sciences, on the scientific domain side, and the services on the business sector side, exert a very significant negative influence on the likelihood that the contract is interregional; chemistry and the engineering sciences, in contrast, exert a very significant positive influence on this same likelihood.

Conclusion

The goal of this article was to contribute new empirical results on the role of geographical proximity in science-industry collaborations and on the evolution of its role over time. Based on two long-term relational databases, and the construction of two complementary indicators of geographical proximity, we were able to conduct a comparative and dynamic analysis of science-industry collaborations.

We were also able to answer the question, "Does geographical proximity still matter?" and contribute a truly new result: the econometric tests conducted in fact show that proximity continues to count still today, which in particular is translated by the not-insignificant weight of intradepartmental collaborations (over 20%), stable for CIFRE contracts and increasing for CNRS contracts. The dynamic perspective enables us to clarify this result and reveals that, at the same time, the most distant interregional collaborations increase over the study period. Therefore, we arrive at a combination of reinforcement of the most local and the most distant collaborations. Such a spatial dynamic in collaborations, with evolutions in a priori antagonistic directions, had already been observed by [START_REF] Hoekman | Research collaboration at a distance: changing spatial patterns of scientific collaboration within Europe[END_REF] at the European level.

A second important result appears: we see significantly different evolutions depending on the nature of the contracts; the role of geographical proximity seems more stable and more significant in CIFRE contracts than for CNRS contracts. This result shows the necessity of distinguishing collaborations according to their characteristics. Not only does the role of geographical proximity differ according to the nature (science-industry vs. intercompany) of the collaboration, as [START_REF] Ponds R | The geographical and institutional proximity of research collaboration[END_REF] showed, but also, within science-industry collaborations, depending on the type of contract (CIFRE vs. CNRS). Finally, our work confirms the existence of sectoral differences, already observed by [START_REF] Ponds R | The geographical and institutional proximity of research collaboration[END_REF] for the scientific domains.

In the end, the analysis of geographical proximity over a long period reveals more contrasting evolutions than is generally imagined. This has strong implications for public policies: these policies generally tend to be based on assumed transversal regularity, which is not the case. Therefore these policies need to be especially fine-tuned, since their results depend on the precise characteristics of the collaborations, as we have been able to show. However, it should be recalled that the results obtained concern France, and that, obviously, they need to be reproduced for other countries in order to assess how general they are.

Figure 1a :

 1a Figure 1a: Evolution in the share of the various spatial scales (CNRS contracts)

Table : available data

 :

	Variable	Modes	number of people share
	Nature of the contract	CNRS	23954 73.1%
		CIFRE	8810 26.9%
		Total	32764 100.0%
	Scientific domain	Physics, maths (pnc)	3330 10.2%
		chemistry (sch)	8588 26.2%
		Astrophysical sciences ((sdu)	2122	6.5%
		Life sciences (sdv)	5512 16.8%
		Human and social sciences (shs)	2179	6.7%
		Engineering sciences (spi)	6334 19.3%
		Information sciences (sti)	4699 14.3%
		Total	32764 100.0%
	Business sector	Industry	16142 49.3%
		Services	11816 36.1%
		Others	4806 14.7%
		Total	32764 100.0%
	Typology of spatial scales intradepartmental contracts (DEP)	7277 22.2%
		infraregional contracts (REG)	6302 19.2%
		Contracts between adjacent regions (LIMITROPHE)	1846	5.6%
		Contracts with the capital region (CAP)	13576 41.4%
		Other interregional contracts (IREG)	3763 11.5%
		total	32764 100.0%

Table 2 : identification of temporal trends

 2

	Variable	Level	Kendall's tau
	CNRS	DEP	0.842 ***
	CNRS	REG	-0.358 **
	CNRS	LIMITROPHE	0.653 ***
	CNRS	ICAP	-0.821 ***
	CNRS	IREG	0.726 ***
	CIFRE	DEP	-0.147
	CIFRE	REG	0.295 *
	CIFRE	LIMITROPHE	-0.174
	CIFRE	ICAP	-0.021
	CIFRE	IREG	0.111
	CNRS (total) Train time	-0.095
	CIFRE (total) Train time	-0.126
	CNRS (inter) Train time	0.832 ***
	CIFRE (inter) Train time	0.105

Table 2 : results of the multinomial logit (base outcome: DEP

 2

	Coef. Std. Err.	z	p>|z| signif.

Table 1 : result of the sample selection model (Heckman two-step)

 1

		Coef.	Std. Err.	z	p>|z| Signif.
		Output equation (explained variable: train)
	annee	0.065	0.021	3.030	0.002 ***
	cifre	1.945	1.008	1.930	0.054 *
	sch	-0.609	0.336	-1.810	0.070 *
	sdu	0.289	0.233	1.240	0.215
	sdv	0.266	0.211	1.260	0.207
	shs	0.606	0.487	1.240	0.213
	spi	-0.720	0.474	-1.520	0.129
	sti	-0.364	0.203	-1.790	0.073 *
	services	0.930	0.499	1.860	0.062 *
	others	-1.107	0.417	-2.650	0.008 ***
	_cons	-121.817	40.673	-3.000	0.003 ***
		Selection equation (explained binary variable: inter)
	annee	-0.009	0.001	-6.570	0.000 ***
	cifre	-0.452	0.018	-25.800	0.000 ***
	sch	0.133	0.027	4.900	0.000 ***
	sdu	-0.004	0.037	-0.110	0.915
	sdv	0.044	0.029	1.520	0.128
	shs	-0.168	0.036	-4.670	0.000 ***
	spi	0.205	0.028	7.420	0.000 ***
	sti	0.035	0.029	1.210	0.226
	services	-0.224	0.017	-13.320	0.000 ***
	others	0.200	0.022	9.180	0.000 ***
	_cons	18.915	2.831	6.680	0.000 ***
	mills ratio	-7.073	3.735	-1.890	0.058 *
	Number of obs.	32764		Wald chi2(10)	49.190
	Censored obs.	13579		Prob > chi2	0.000 ***
	uncensored obs.	19185


Guillaume Lavoué

Jean-Philippe Vandeborre

Halim Benhabiles

Mohamed Daoudi

Kai Huebner

Michela Mortara

Michela Spagnuolo

M Bronstein

A Bronstein

A Ferreira

J-P Vandeborre

SHREC'12 Track: 3D mesh segmentation

Keywords: (according to ACM CCS): I, 3, 5 [Computer Graphics]: Computational Geometry and Object Modeling-I, 2, 10 [Artificial intelligence]: Vision and Scene Understanding-Shape

de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

Three-dimensional models are mostly represented as polygonal meshes; this kind of representation has the advantage of being perfectly adapted to 3D display with the help of modern 3D accelerated hardware. But the main drawback of this representation is the lack of a structure or a hierarchical description that could be very useful for many applications. Hence, the automatic segmentation of 3D mesh models is very often a necessary pre-processing tool for applications such as compression, texture mapping, animation and particularly shape retrieval. Mesh segmentation consists in subdividing a polygonal surface into patches of uniform properties either from a strictly geometrical point of view or from a perceptual / semantic point of view. According to recent states-of-the-art [START_REF] Shamir | A survey on Mesh Segmentation Techniques[END_REF], mesh segmentation techniques can be classified into two categories: surface-type (or geometric) methods and part-type (or semantic) methods. In the first case, the algorithms are based on low level geometric information (e.g. curvature) in order to define segments (i.e. regions) with respect to geometric homogeneity, while in the latter case, the algorithms aim at distinguishing segments that correspond to relevant features of the shape, by following higher level notions such as defined in human perception theory. This kind of approach is particularly suited for object animation/ deformation and shape retrieval applications, where the decomposition has to be meaningful. The recent creation of ground-truth databases for the segmentation of 3D meshes [CGF09, [START_REF] Benhabiles | A framework for the objective evaluation of segmentation algorithms using a ground-truth of human segmented 3D-models[END_REF][START_REF] Benhabiles | A comparative study of existing metrics for 3D-mesh segmentation evaluation[END_REF], has given to the computer graphics community the opportunity to quantitatively evaluate the segmentation algorithms; however, in spite of the success of these benchmarks, only few results from a limited number of algorithms are currently publicly available whereas such quantitative performance data are crucial for the emulation of this field of research. In that context, the objective of this SHREC 2012 segmentation track is to provide researchers with the opportunity to directly compare their methods with their counterparts, offering the community a fair evaluation and comparison.

Data

For this track we use the grund-truth corpus from [START_REF] Benhabiles | A comparative study of existing metrics for 3D-mesh segmentation evaluation[END_REF]; it contains 28 3D models (as triangle meshes) grouped in five classes, namely animal, furniture, hand, human and bust. Each 3D model of the corpus is associated with 4 manual segmentations which give a total of 112 ground-truth segmentations done by 36 volunteers. Figure 1 illustrates the models of the corpus with one manual segc The Eurographics Association 2012. mentation per model. All the selected models are manifold, connected, and do not have intersecting faces; hence they are supported as an input by any segmentation algorithm. The volunteers have freely segmented the models and no condition was imposed on the manner with which they have segmented them.

Evaluation methodology

For a given segmentation algorithm to evaluate, the evaluation protocol is the following:

1. The algorithm is launched on the 28 models of the database, thus producing 28 segmentations. 2. For each model, the segmentations Sa from the algorithm is compared to the 4 ground-truth segmentations S k using a mesh segmentation similarity metric. 3. We obtain a segmentation quality score for each model; these 28 scores can then be averaged over all models, all categories or presented in increasing order in the form of a performance curve.

To provide a relevant evaluation of the performance, it is critical to choose an accurate mesh segmentation similarity metric (see step 2 above); several metrics have been proposed so far, they have been extensively studied and compared in [START_REF] Benhabiles | A comparative study of existing metrics for 3D-mesh segmentation evaluation[END_REF] and the 3D-NPRI metric has shown to provide the best results (in term of correlation with the human opinion). This metric is derived from the Rand Index (RI) also used in [START_REF] Golovinskiy | A benchmark for 3D mesh segmentation[END_REF], it was introduced in [BVLD10] by transposing the 2D image version of Unnikrishnan et al. [START_REF] Unnikrishnan R | Toward objective evaluation of image segmentation algorithms[END_REF].

Let Sa be the automatic segmentation to be compared to a set of ground-truth segmentations S k ; we denote the corresponding label of a vertex i (label of the region which the vertex belongs to) by l Sa i in segmentation Sa and by l S k i in a ground-truth segmentation S k . The 3D Probabilistic Rand Index (3D-PRI) is defined as:

3DPRI(Sa, {S k }) = 1 N 2 ∑ i, j i < j e i j p i j + (1 -e i j )(1 -p i j ) (1)
where e i j is a binary number which denotes the event of a pair of vertices i and j belonging to the same region in the automatic segmentation:

e i j = I(l Sa i = l Sa j ) (2)
and p i j is the probability of the vertices i and j belonging to the same region in the ground-truth segmentations {S k }:

p i j = 1 K ∑ k I(l S k i = l S k j ) (3)
This 3D-PRI takes values ranged in [0,1], where 0 indicates no similarity between Sa and S k , and 1 indicates a perfect match. To provide more meaningful results and increase the dynamic range of the metric, the authors [START_REF] Benhabiles | A comparative study of existing metrics for 3D-mesh segmentation evaluation[END_REF] provided also a version normalized by a baseline of random segmentations: the 3D-NPRI, which takes values in [-1,1] with 0 standing for an average similarity as a random segmentation could produce and 1 for a perfect similarity. These algorithms are detailed in the next subsection. We have also launched four algorithms from the state of the art on our dataset to strengthen the results. They are quickly described in subsection 4.2.

Methods

Three

Registered methods

Box Approximation and Decomposition

This method [START_REF] Huebner | BADGr -A Toolbox for Box-based Approximation, Decomposition and GRasping[END_REF] is proposed by Kai Huebner from the Computer Vision & Active Perception Lab, KTH, Stockholm, Sweden.

The aim of this segmentation algorithm is to iteratively split an oriented bounding box (starting from one root box) in such a way that the new point sets yield a better box approximation of the shape. Iterative splitting of a root box corresponds to the build-up of a hierarchy of non-axis aligned minimum volume bounding boxes (MVBBs). As the motivation of the algorithm originates from our research in robot grasping of arbitrary object, we want to conveniently approximate a shape with as few boxes as possible. Though the internal fitting algorithm [START_REF] Barequet | Efficiently approximating the minimum-volume bounding box of a point set in three dimensions[END_REF] is efficient, a fitting step after each splitting consumes valuable computation time. A heuristic to find a good split of the point cloud is needed. In our case, we define a good split by consulting the relation of the box volume before and after performing a split. A split of the parent box is the better, the less volume the two child MVBBs include. Intuitively, this is clear, as shape approximation is better with highly tight-fitting boxes. To efficiently split the point set in a box, we project the points to the 6 box surfaces and compare the best 2D splits. According to the best split, the original point cloud is divided into two subsets of the data points. Using these as new inputs to the fitting algorithm represents the complete iterative fit-and-split technique. As an iteration breaking criterion, we subsequently test the real 3D volume gain θ of the resulting best 2D split. Therefore, we compute the gain in volume defining:

θ = (volume(C 1 )+volume(C 2 )+volume(A \P ))/volume(A)
(4) where A is the overall set of boxes in the current hierarchy, P is the current (parent) box, C 1 ,C 2 are the two child boxes that will be produced by the selected split, and volume being a volume function. θ is the main parameter of the algorithm, controlling depth of the splitting hierarchy and granularity of the produced segments. As mentioned, the algorithm has been developed for decomposition of object models into intuitive parts for generating robot grasp hypotheses [START_REF] Huebner | BADGr -A Toolbox for Box-based Approximation, Decomposition and GRasping[END_REF], i.e. to be robust towards noise, outliers, and incomplete models as they appear in real sensor settings. In this context it also has to mentioned that the algorithm takes only the vertices into consideration, but does not need any polygonal surface representation. Also, a random subset selection may result in different decomposition when re-processing a model. Though grasp evaluation was evaluated by the authors, the segmentation result itself has never been evaluated before. Minor changes had to be made to let the original open source code (available at http: //www.csc.kth.se/~khubner/badgr/) to provide the output data needed for the SHREC 2012 dataset. Some results with boxes are shown in figure 2.

Plumber

This method [MPS * 04] was registered for the track by Michela Mortara and Michela Spagnuolo from the CNR- IMATI Genova, Italy. Plumber is a specialized shape segmentation method for detecting tubular features of 3D objects represented by triangle meshes. The Plumber algorithm segments a surface into connected components that are either body parts or elongated features, that is, handle-like and protrusion-like features, together with their concave counterparts, i.e. narrow tunnels and wells (more details in [MPS * 04]). Thus, Plumber identifies primitives of the object with a specific structure, i.e. generalized cones and cylinders, and not only related to a curvature and concavity analysis [MPS * 03, KT03]. The segmentation can be done at single or multi-scale, and produces a shape graph which codes how the tubular components are attached to the main body parts.

Intuitively, tubes are identified by parts of the shape whose intersection with a sphere of appropriate radius produces two intersection curves. The section of the tube and its axis can be arbitrarily shaped; however, chosen a level of detail R i , tubes of diameter R i or smaller will be identified. Small radii determine details, while bigger ones are used to analyse the global characteristics of the model.

Chosen a level of detail R i , Plumber performs the following steps:

1. identify limb-regions composed by vertices generating two intersection curves by the sphere centred on them, and check that the limb-regions have two boundaries on the object surface (so that the same topology of a cylinder is guaranteed); 2. shrink each of the two selected boundary components along the surface to its medial-loop, whose points are nearly equidistant from the two border loops; 3. expand-back the medial-loop by sweeping the extent of the shape in both directions. More precisely, at each iteration we place a sphere of radius R in the barycentre of the new medial loops. If the intersection between the sphere and the surface generates two loops, mesh vertices inside the sphere are marked as visited; 4. the procedure is iterated in both directions until:

• no more loops are found, or more than one loop is found on not-visited regions; • the new loop lies on triangles that are already part of another tube, or the length of the new loop exceeds a pre-defined threshold.

c The Eurographics Association 2012.

5. the tube skeleton may be extracted by joining the loops' barycentres.

For this track, we have run Plumber at 8 increasing radii, determined by the the average edge length over the input mesh multiplied by even factors from 2 to 16.

For some models, the sampling density on the radius values was not sufficiently fine to capture all the tubular features, or the maximum radius value was not big enough to detect very thick tubes. Moreover, thick tubes need large spheres to be detected, and the corresponding tube growing step makes intersections with other tubes frequently occurr, which makes the sweeping stop prematurely (this is the case for the Homer legs), whereas the method performs very well on thin and elongated features even in complex configurations (e.g. the furniture models). Being targeted to tubular shaped primitives, the method is not suitable for certain shape classes without any elongated features, like the busts.

Boundary Learning

This method [START_REF] Benhabiles | Learning Boundary Edges for 3D-Mesh Segmentation[END_REF] is proposed by Halim Benhabiles, Guillaume Lavoué, Jean-Philippe Vandeborre and Mohamed Daoudi from LIFL, Université de Lille and LIRIS, Université de Lyon, France.

The algorithm is carried out using two main steps: the offline step in which an objective boundary function is learned using a set of manually segmented models (ground-truths), and the on-line step in which the learned function is used to segment the input mesh. The problem of learning the boundary edge function is formulated as a classification problem, resolved with the Adaboost classifier. This classifier takes as input a training dataset (we used the Princeton segmentation benchmark [START_REF] Golovinskiy | A benchmark for 3D mesh segmentation[END_REF] as training set) and generates the boundary edge function. The training dataset is composed of a set of feature vectors Fe computed for each edge of the ground-truth meshes. A feature vector Fe of a given edge contains a set of geometric criteria and is associated with its proper class label L so that L = +1 if the edge is a boundary (according to the manual segmentations of the mesh containing this edge) and L = -1 if the edge is not a boundary. Once the learning is done, the classifier produces the boundary edge function. This function is a weighted combination of the set of geometric criteria. It takes as input a feature vector from any given edge and outputs a signed scalar value whose sign will provide the estimated classification of the edge. The use of the boundary edge function on a given mesh leads to produce a set of interest regions (see figure 3.a), each of which is represented by a set of connected edges of the mesh. Hence it is not possible to directly consider these regions as the final segment boundaries of the mesh. To overcome this problem we propose a processing pipeline that transforms these non-connected fuzzy regions into thin, closed and smooth contours, by using the edge function. This processing pipeline comprises three stages. In the first stage of the process, for each interest region, a thinning algorithm [START_REF] Hubeli | Multiresolution feature extraction for unstructured meshes[END_REF] is applied. This latter algorithm gives as output a set of open linear contours (figure 3.b). Next, each open contour is completed using an improved version of the algorithm proposed by Lee et al. [LLS * 05] using the edge function (figure 3.c). At this step we have created a set of closed contours which represent a first version of the segmentation boundaries. However, these boundaries are often not smooth nor precise since in the thinning stage we do not consider any geometric information. To overcome this drawback, we apply an improved version of the snake movement algorithm proposed in [START_REF] Kim | 12th Pacific Conference on Computer Graphics and Applications[END_REF] based also on the learned edge function. The snake movement allows to improve the quality of the boundaries in term of smoothness and precision without changing the mesh connectivity (figure 3.d). This set of improved boundaries defines the final segmentation (figure 3.e).

State-of-the-art methods

To strengthen the evaluation we have also launched the following algorithms on the dataset, using authors' implementations:

• Curvature Classification. Lavoué et al. [LDB05] propose
a segmentation algorithm based on curvature classification and then region growing and merging. It extracts connected regions associated with similar curvature. This algorithm is especially suited for CAD models. • Fitting Primitives. Attene et al. [START_REF] Attene | Hierarchical mesh segmentation based on fitting primitives[END_REF] base their algorithm on an iterative hierarchical face clustering. Starting with one cluster per face, clusters are then iteratively merged into larger patches that best fit some predefined primitives like plane, sphere or cylinders. • Topology Driven. Tierny et al. [START_REF] Tierny | Topology driven 3D mesh hierarchical segmentation[END_REF] have proposed a hierarchical segmentation mostly based on the topology of the model. They first extract an enhanced topological skeleton using Reeb graph and constriction detection.

Then this skeleton is used to extract the core of the object and to identify the junction areas. The result of this operation is a fine segmentation which can then be simplified by merging the nodes of the skeleton. • Shape Diameter. Shapira et al. [SSCO08] compute a highly relevant scalar field over the mesh vertices: the Shape Diameter Function. Their algorithm classifies this scalar field into several clusters and then uses graph-cut to provide a smooth partition of the 3D mesh.

Evaluation results

Tables 1 and 2 present respectively the 3D-NPRI values and ranking for all methods, averaged for each category and for the whole corpus; several remarks can be drawn regarding these results:

• The best method is the Boundary Learning one 4). • Certain classes are easier to segment than others; for instance all methods produce good results on the animal class (see figure 5), whereas the bust class seems much more difficult to segment by any automatic method (see figure 6). This is probably due to the high semantic aspect carried by a face, this semantic aspect influences the manual segmentations, and is difficult to capture using simple local geometric criteria.

Figure 7 represents 3D-NPRI indices for each model of the corpus, these indices are plotted in increasing order for each algorithm, hence i th index does not refer to the same 3D model for each algorithm. These curves provide a good overview of the performances of the algorithms among the models of the corpus.

Conclusions

In this paper, we have presented the database, evaluation protocol, involved methods and results of the 3D mesh segmentation track of the SHREC 2012 contest. The Boundary Learning method has logically demonstrated superior results; however there is still room for improvements since some classes remain difficult to segment. All results from this track are available through our online 3D Mesh segmentation benchmark http://www-rech. telecom-lille1.eu/3dsegbenchmark/ which allows an online evaluation of segmentation algorithms.

Figure 1 :

 1 Figure 1: Models of our corpus associated with one groundtruth.

  segmentation methods have been registered to the track: • Box Approximation and Decomposition [Hue12] from the Computer Vision & Active Perception Lab, KTH, Stockholm, Sweden. • Plumber [MPS * 04] from the CNR-IMATI, Genova, Italy. • Boundary Learning [BLVD11] from LIFL, Université de Lille and LIRIS, Université de Lyon, France.

Figure 2 :

 2 Figure 2: Some examples of segmentations / box decompositions from [Hue12].

  [START_REF] Benhabiles | Learning Boundary Edges for 3D-Mesh Segmentation[END_REF]. This appears logical since this algorithm has c The Eurographics Association 2012.

Figure 3 :

 3 Figure 3: Post processing pipeline; interest regions (a), thinning (b), contour completion (c), snake movement (d), final segmentation (e).

Figure 4 :

 4 Figure 4: Segmentation results for one object from the furniture class.

Figure 7 :

 7 Figure 7: 3D-NPRI indices of the 28 models sorted in increasing order for all algorithms.

Figure 5 :

 5 Figure 5: Segmentation results for some objects from the animal class.

Figure 6 :

 6 Figure 6: Segmentation results for two objects from the bust class. Results from the Plumber method are not presented since this algorithm creates only one region for the objects of this class.

Table 1 :

 1 3D-NPRI results for all tested methods.

	Method Name	Animal	Bust	Furniture Hand Human Global Rank
	Box Approximation and Decomposition [Hue12]	0.52	-0.08	0.08	-0.09	0.37	0.16
	Plumber [MPS * 04]	0.36	0.00	0.54	0.27	0.33	0.30
	Boundary Learning [BLVD11]	0.68	0.41	0.79	0.68	0.69	0.65
	Curvature Classification [LDB05]	0.43	0.10	0.38	0.45	0.29	0.33
	Fitting Primitives [AF06]	0.45	0.09	0.56	0.52	0.61	0.45
	Topology Driven [TVD07]	0.51	-0.07	0.36	0.78	0.50	0.41
	Shape Diameter [SSCO08]	0.62	0.24	0.85	0.19	0.66	0.51
	learned how people segment 3D models and thus pro-
	duces results very close to the ground-truth; moreover it
	integrates several different features (including curvature,
	shape diameter function, dihedral angles, etc.) whereas
	most of other methods rely on only one type of fea-
	ture. However we can notice that the method relying only
	on the Shape Diameter function [SSCO08] still produces
	very good results, which attests the power of this feature.
	• We can notice that the peformance of the methods is
	highly class-dependent, indeed no method owns the same
	rank for all classes. The performance actually depends
	on the features used by each method. For instance, the
	Plumber algorithm [MPS * 04] detects tubular parts, hence
	it provides good results for the furniture class; on this lat-
	ter class, the Box Approximation and Decomposition ap-
	proach [Hue12] behaves poorly since chairs or tables are
	not adapted to such decomposition (see figure

Table 2 :

 2 3D-NPRI ranking for all tested methods.

	Method Name	Animal Bust Furniture Hand Human Global Mean
	Box Approximation and Decomposition [Hue12]	3	5	7	7	5	7
	Plumber [MPS * 04]	7	5	4	5	6	6
	Boundary Learning [BLVD11]	1	1	2	2	1	1
	Curvature Classification [LDB05]	6	3	5	4	7	5
	Fitting Primitives [AF06]	5	4	3	3	3	3
	Topology Driven [TVD07]	4	5	6	1	4	4
	Shape Diameter [SSCO08]	2	2	1	6	2	2

c The Eurographics Association 2012.

Acknowledgements

We would like to thank Marco Attene, Ariel Shamir, Shy Shalom, and Julien Tierny for providing us with their source code or the binary of their segmentation algorithms.


Julien Tierny
email: tierny@lifl.fr

Jean-Philippe Vandeborre
email: vandeborre@lifl.fr

Mohamed Daoudi
email: daoudi@lifl.fr

Reeb chart unfolding based 3D shape signatures

Keywords: Shape analysis, shape signature, Reeb graph, surface parameterization

This paper presents a novel surface parameterization based technique that addresses the pose insensitive shape signature problem for surface models of arbitrary genus. It is based on the key idea that two surface models are similar if the canonical mappings of their sub-parts introduce similar distortions. First, a Reeb graph of the shape is computed so as to segment it into charts of controlled topology, denoted as Reeb charts, that have either disk or annulus topology. Next, we define for each Reeb chart a straightforward mapping to the canonical planar domain. Then, we compute a stretching signature of the canonical mapping based on an area distortion evaluation. Finally, the input shape is represented by the set of the stretching signatures. An application to pose-insensitive shape similarity is proposed by comparing the signatures of the different Reeb charts. Promising experimental results are presented and compared to state-of-the-art techniques. The gain provided by this new signature as well as its interest for partial shape similarity are demonstrated.

Introduction

Shape signatures are compact representations that encode most of the shape characteristics. They are the key ingredient of content-based shape retrieval systems. Such systems take advantage of the signature conciseness to speed up the shape similarity estimation process, benefiting many applications like interactive modeling by example [FKS * 04]. A fundamental feature of a shape signature is its stability against transformations of the represented shape, enabling shape retrieval systems to match similar shapes modulo these transformations.

A challenging open issue is the definition of efficient 3D shape signatures that are robust to rigid and non-rigid transformations, such as character articulation or shape bending. Structural based signatures [START_REF] Hilaga | Topology matching for fully automatic similarity estimation of 3D shapes[END_REF] are interesting candidates, particularly because they represent the shape as a set of distinctive sub-parts and thus can address an additional challenging issue, which is partial shape retrieval [START_REF] Biasotti | Sub-part correspondence by structural descriptors of 3D shapes[END_REF]. However, in that kind of approach, an appropriate signature still has to be defined for each of the identified sub-parts. Among the other existing pose insensitive 3D shape signatures (based on geodesic distance distributions [START_REF] Gal R | Pose oblivious shape signature[END_REF], topological point rings [START_REF] Tam | Deformable model retrieval based on topological and geometric signatures[END_REF] or spectral analysis), surface parameterization based techniques sound particularly promising as they already gave excellent results for face recognition [WWJ * 06]. They aim at describing the intrinsic 2D information carried by the underlying surface model independently from its 3D spatial embedding (or its pose). However, a major drawback of these techniques is that the topology of the surfaces to compare must be fully controlled (the surfaces must be topology equivalent).

In this paper, we propose a novel surface parameterization based technique that addresses the pose insensitive shape signature problem. This work makes the following contributions. It improves previous parameterization based techniques by being able to handle surfaces of arbitrary genus. It also improves previous decomposition based techniques by proposing more efficient sub-part signatures. It is based on the key idea that two surface models are similar if their sub-parts, or Reeb charts, are similar (in particular, if their mappings to the canonical planar domain introduce similar distortions).

After a brief method overview, we define the so-called Reeb charts and introduce the Reeb chart unfolding signatures. Finally, we propose an application to pose-insensitive shape similarity estimation. We present experimental results that demonstrate the gain of the proposed signature for global shape retrieval and we give early results showing its interest for partial shape retrieval.

Φ ✲ C 1 C 2 ❍ ❍ ❍ ❍ • ✟ ✟ ✟ ✟ ✙ D φ 1 , λ φ 1 φ 2 , λ φ 2

Method overview

Let M be a closed 2-manifold of arbitrary genus embedded in R 3 . First, we compute the Reeb graph of M to segment it into a set of charts C i of controlled topology, that we call Reeb charts, that have either disk or annulus topology.

To evaluate the similarity between two charts C 1 and C 2 of equivalent topology, we try to characterize a map Φ : C 1 → C 2 . However, in this paper, we focus on signature computation. Hence, we characterize Φ using the transition mappings φ 1 and φ 2 to the canonical planar domain D (either the unit disk or the unit annulus) as shown in figure 1:

Φ := φ -1 2 • φ 1 .
Then, the similarity between C 1 and C 2 is evaluated by comparing the mappings φ 1 and φ 2 . In particular, we characterize φ 1 and φ 2 by their stretching signature (λ φ1 and λ φ2 ), a function of the area distortion they introduce.

Then, for shape similarity estimation purposes, we introduce a distance between the stretching signatures λ φ1 and λ φ2 . Finally, the distance between two closed 2-manifolds of arbitrary genus is a function of the stretching signature distances associated to their different Reeb charts.

Reeb chart segmentation

To deal with surfaces of arbitrary genus, we use a divideand-conquer strategy based on Reeb graphs (see definition 1), as proposed within the framework of triangulation remeshing [START_REF] Patanè | Paragraph: Graph-based parameterization of triangle meshes with arbitrary genus[END_REF] or texture mapping [START_REF] Zhang | Featurebased surface parametrization and texture mapping[END_REF].

Definition 1 (Reeb graph) Let f : M → R be a Morse func- tion defined on a compact manifold M. The Reeb graph R( f ) is the quotient space on M × R by the equivalence relation (p 1 , f (p 1 )) ∼ (p 2 , f (p 2 )), which holds if f (p 1 ) = f (p 2 ) and p 1 , p 2 belong to the same connected component of f -1 ( f (p 1 )).
To deal with invariance to rigid transformations and robustness to non-rigid ones, we compute the Reeb graph of the input 2-manifold (represented by a triangulation noted T ) Statement 1 (Reeb chart topology) Reeb charts of a compact closed orientable 2-manifold have either disk or annulus topology whatever the genus of the manifold is. This statement can be briefly argued as follows. By definition, an edge E i has two extremities, whose pre-images by Ψ are circles which form the boundaries of the chart C i (C i has genus zero). Hence, charts have two boundaries and thus annulus topology. However, for charts adjacent to a local extremum of f , the related boundary collapses to a point (the extremum). Thus that kind of chart is given disk topology.

C i = Ψ -1 (E i ) is defined as a Reeb chart.
In fig. 2(d Let ρ(p) ∈ ]0, 1] be the normalized absolute difference of f values between O and a point p ∈ C i , as shown in figure 3. Consequently to the Reeb chart definition, the sub-level sets of ρ have also disk topology, as illustrated by the white sublevel set in figure 3. In particular, as ρ increases, the shape of the sub-level sets varies. Thus it induces an evolution in the distortion introduced by their mapping to D. Consequently, to capture the evolution of the chart's shape variation, we propose to introduce the stretching signature λ φi of φ i as follows:

λ φi (ρ) = A Ci (ρ) A D (ρ) = A Ci (ρ) πρ 2 (1)
where A Ci (ρ) stands for the area of the sub-level set for parameter ρ on C i and A D (ρ) stands for the area of the sub-level set on D. A Ci (ρ) is computed by summing the areas of the related triangles of T (after having normalized edge length by f , similarly to ρ). Roughly, λ φi (ρ) depicts the stretch one has to apply on the chart to map it to a disk as ρ increases.

Figure 4 shows some examples of stretching signatures for various disk-like primitives. As f is based on geodesic distances, it is invariant to rigid transformations and robust to non-rigid transformations, as shown in figure 4(b), where the signature of a bent version of the thumb gives a signature nearly identical to the original. Moreover, it is also robust to surface noise, as shown in figure 4(a).

The close relationship between the stretching signature and the represented shape can be underlined by the following remarks. In figure 4(d),C i is planar until ρ = 0.65, thus λ φi (ρ) tends to 1 until ρ = 0.65. For a cone, λ φi (ρ) = sin(α) where α = atan( r h ) where r and h stand for the radius and the height of the cone. Hence, λ φi (ρ) tends to a constant term, as shown in figure 4(c). Finally, when a bottleneck is present on the chart (figure 4(f)), the signature describes an inflection.

Annulus-like Reeb chart unfolding

An analog reasoning can be applied for annulus-like charts. Let B 1 be the boundary of shortest perimeter of an annuluslike chart C j and B 2 the other one. In this case, we let φ j map B 1 to the inner boundary of the unit planar annulus and B 2 to its outer boundary, as shown in figure 5. By defining the ρ parameter similarly to the previous paragraph, we can state that the sub-level sets of ρ have also annulus topology, as illustrated by the white sub-level set in figure 5. Hence, we introduce the stretching signature λ φ j of φ j as follows, (1 is the inner radius of the unit annulus):

λ φ j (ρ) = A Cj (ρ) A D (ρ) = A Cj (ρ) π(ρ + 1) 2 -π (2)
Notice that in figure 5, the chart is based on a truncated version of a cone; thus its signature is similar to figure 4(c).

Application to pose-insensitive shape similarity

To assess the efficiency of the proposed signature, we use it for shape similarity estimation on the ISDB dataset from Tel-Aviv University, which is composed of articulated characters (106 surface models, 9 classes: cats, dinos, dogs, frogs, hands, horses, humans, lions and wolves).

Global shape similarity

First, for the comparison of two chart signatures, we use an L 1 distance, normalized by the number of samples in the signatures (typically 64). Then, to compute the distance between two models, we run a bipartite matching algorithm [START_REF] Tam | Deformable model retrieval based on topological and geometric signatures[END_REF] that matches pairs of topology equivalent charts that minimize their distance, minimizing the overall sum of distances, noted d. Finally, the distance between two models is given by d. Thanks to the conciseness of the signatures, once the Reeb graph of the query has been computed, the shape comparison between the query and the whole dataset is achieved in about 100 milliseconds (with a P4-CPU PC). Figure 6 shows a typical query and the results retrieved by the system. Charts that have been matched together have been displayed with the same color. Notice that, except in one case, the tail of the horse query model has been matched with the tail of each retrieved result. Similar comments can be made for the legs, or the neck, which demonstrates the efficiency of the proposed signature. Moreover, this figure shows that the proposed signature is clearly pose-insensitive since horses in different poses have been retrieved as the top results. Table 1 gives a more quantitative evaluation of the system, with comparison to other techniques (the higher the scores are the better they are, see [START_REF] Shilane | The Princeton shape benchmark[END_REF]). The first line reports the scores of our comparison algorithm, using Reeb chart unfolding signatures. The second one reports the scores of the same algorithm, using the sub-part attributes proposed in [START_REF] Hilaga | Topology matching for fully automatic similarity estimation of 3D shapes[END_REF] (area ratio and Morse interval length). For example, with 1 st Tier score, the gain provided by Reeb chart unfolding signatures is about 9 %. Notice that scores from [START_REF] Gal R | Pose oblivious shape signature[END_REF] could not be reported as they were obtained on an unspecified subset of 80 models of the ISDB dataset.

Partial shape similarity

Figure 7 zooms in the chart matchings between a hand and a human surface model, displaying in color some of the charts that have been matched together. Notice that the thumb has been matched with the correct thumb of the humanoid and that the remaining fingers have been matched with fingers, despite their pose difference. In the future, based on this encouraging result, we would like to design a graph-based matching algorithm so that, for example, the hand model can be matched with its corresponding hand in the humanoid, achieving partial shape similarity [FKS * 04].

Conclusion and future work

In this paper we proposed a novel surface parameterization based technique for pose-insensitive 3D shape signature, based on Reeb chart unfolding. It improves previous parameterization methods by being able to handle surfaces of arbitrary genus, using a divide-and-conquer strategy based on Reeb graphs. It also improves previous decomposition techniques, by providing a more efficient sub-part signature, resulting in better scores on the ISDB dataset (see table 1). However, when performing signature similarity evaluation, we did not take advantage of the intrinsic structural information brought by the Reeb graph, so as to underline the gain of the signatures only. In the future, we will focus on sub-graph matching algorithms to address the partial shape retrieval problem, benefiting from the efficient part matching proposed by Reeb chart unfolding signatures (fig. 7).

Figure 1 :Figure 2 :

 12 Figure 1: Reeb chart similarity estimation process: each chart C i is mapped under φ i to the canonical planar domain D and its stretching signature λ φi is computed with regard to the area distortion introduced by φ i .

Figure 3 :

 3 Figure 3: Disk-like chart unfolding signature computation. using a Morse function based on geodesic distances. In particular, to introduce some visual semantic in the decomposition, we automatically extract feature points [KLT05] (vertices located on the extremity of prominent components). For each vertex v ∈ T , f (v) = δ(v, v f ) where δ stands for the geodesic distance and v f for the closest feature point from v.Figure 2(a) shows the level lines of f and the feature points of T (in green). For further details about the Reeb graph construction algorithm, we refer the reader to [TVD06]. Definition 2 (Reeb chart) Let Ψ : M → R( f ) map each point p of M to its equivalence class in R( f ). Let E = {E 0 , . . . En} be the edges (maximally connected unions of equivalence classes containing only regular points) of the Reeb graph R( f ).C i = Ψ -1 (E i ) is defined as a Reeb chart.Figure 2(b) shows a dual Reeb graph (where each edge E i is collapsed in a colored node). Figures 2(c) and 2(d) show the segmentation of the hand model into its Reeb charts. Basically, Reeb charts are the partitions of the surface that correspond to the nodes of the dual Reeb graph.

  Figure 2(b) shows a dual Reeb graph (where each edge E i is collapsed in a colored node). Figures 2(c) and 2(d) show the segmentation of the hand model into its Reeb charts. Basically, Reeb charts are the partitions of the surface that correspond to the nodes of the dual Reeb graph.

  ), disk-like Reeb charts have been colored in blue and annulus-like ones in red. Notice that the proposed decomposition brings a certain visual semantic: each of the fingers of the hand model forms a distinct chart.4. Reeb chart unfolding signatures 4.1. Disk-like Reeb chart unfoldingGiven the segmentation provided by the Reeb graph, a straightforward and natural mapping to the canonical planar domain is used, without further computation cost, based on the Morse function represented by the Reeb graph. Indeed, for a disk-like Reeb chart C i , let O be the local extremum of f it contains and B its boundary. We let φ i map O to the center of the unit planar disk, B to its boundary and f level lines to concentric circles, as shown in fig.3where the thumb of the hand of fig.2has been mapped to the planar domain D.

Figure 4 :

 4 Figure 4: Example of stretching signatures for altered versions of the thumb chart and other primitive charts.

Figure 5 :

 5 Figure 5: Annulus-like chart unfolding signature.

Figure 6 :

 6 Figure 6: Chart similarity matchings between a horse query model and retrieved results.

Figure 7 :

 7 Figure 7: Chart similarity matchings between a hand and a human model.

Table 1 :

 1 Similarity estimation scores on the ISDB dataset.

	Methods	NN	1 st T.	2 nd T.	E-M	DCG
	RCU	94.3 % 79.2 % 89.4 % 59.1 % 92.1 %
	HBA	88.7 %	70.6%	85.7 %	54.0 %	89.1 %
	[FMK * 03]	67.9 %	44.0 %	60.6 %	39.4 %	71.7 %

c The Eurographics Association 2007.

Acknowledgements

The authors would like to thank Ran Gal from Tel-Aviv University for providing the ISDB dataset. This work is partially supported by the European NoE Delos No. 507618.