François Cluzel
email: francois.cluzel@ecp.fr

Dominique Millet

Yann Leroy

Bernard Yannou

Relative Contribution of a Subsystem to the Environmental Impact of a Complex System: Application to Aluminium Electrolysis Conversion Substations

Keywords: Environmental evaluation, Life cycle assessment, Complex system, Subsystem, Aluminium electrolysis conversion substation

We focus in this paper on the contribution of a subsystem to the environmental impact of a system. In this way we propose to explore some limits related to Life Cycle Assessment (LCA), in particular the consideration of the use phase specificities (for example lifetime, technology or energy mix). Two cases studies concerning AREVA T&D's aluminium electrolysis conversion substations are proposed to illustrate these problems. The first one considers the environmental contribution of a transformer to the electrical substation, whereas the second one studies the contribution of the substation to primary aluminium production. We show that the context specificities of a product should be taken into account in order to assess its real environmental impacts. To ignore them can lead to false conclusions, what is essential to avoid when a company wants to define its eco-design strategy.

1-Introduction

Environmental issues have become a major concern in companies. The environment is now often integrated into product design and completes the economic or technical aspects. It clearly appears like a key-driver to innovation. Tools like Life Cycle Assessment (LCA) allow evaluating the environmental impacts of a product or service to identify improvement ways. Although LCA has been standardized in the 90s [I1], numerous limits have appeared [START_REF] Reap | A survey of unresolved problems in life cycle assessment -Part 2: impact assessment and interpretation[END_REF][START_REF] Reap | A survey of unresolved problems in life cycle assessment -Part 1: goal and scope and inventory analysis[END_REF], in particular when considering complex systems. They concern all the four phases (Goal and scope, Life Cycle Inventory, Life Cycle Impact Assessment and Interpretation) and are responsible for potential mistakes, uncertainties or inaccuracies. As Reap et al. says, LCA is still "a tool in need of improvement" [START_REF] Reap | A survey of unresolved problems in life cycle assessment -Part 2: impact assessment and interpretation[END_REF].

Moreover, from an industrial point of view, knowing the exact contribution of a product to its environment or location site becomes essential. Some works have already highlighted the need to include a specific usage (consumer habits) or exploitation parameters (location, energy, transports…) into LCA [C1], because a generic approach can lead to false results.

We propose in this paper to focus on the relations between a system and its subsystems in terms of environmental impacts in a specific context. It means that great uncertainties can exist on the lifetime of a subsystem because of economic aspects at the system level for example. It means also that the same product can be implemented in different location with different specificities.

An application has been made on AREVA T&D conversion substations in two case studies. The first one assesses the contribution of one element of the substation to the substation, so it deals with AREVA T&D internal design considerations. The second one studies the contribution of the substation to primary aluminium production, so it includes more shareholders, in particular AREVA T&D's customers.

We expose in Section 2 the different problems that will be considered. Section 3 is dedicated to the methodology and it presents the two case studies that will be detailed in Section 4 and 5. We conclude on some remarks and perspectives in Section 6.

2-Problem setting

-LCA, complexity and specific context

Life Cycle Assessment (LCA) becomes really heavy to implement with limited resources face to complex systems. Reap et al. summarize in [RR1] and [START_REF] Reap | A survey of unresolved problems in life cycle assessment -Part 1: goal and scope and inventory analysis[END_REF] the main current problems in LCA (see Table 1.). These topics become particularly problematic when the complexity of the studied system increases.

-Problem definition

Actually in a specific context the environmental impact of a system can be extremely different from the theoretical one. We focus in this paper on several reasons:

 For a same subsystem the technology used at the system level can be different from an application to another, or can be changed during the subsystem use phase. This could have great repercussions on the environmental impact of the system, and so on the environmental contribution of the subsystems. As said in [START_REF] Reap | A survey of unresolved problems in life cycle assessment -Part 2: impact assessment and interpretation[END_REF], it is hard to "predict with confidence the future".  The lifetime is not always clearly known, particularly for industrial systems with a long use phase (>20 years). This is extremely important in order to quantify the environmental impact of electrical and electronic products, where the use phase is often predominant. This problem is in particular highlighted by Cooper [C1] and Günther and Langowski [START_REF] Günther | Life cycle assessment study on resilient floor coverings[END_REF]. Furthermore the lifetime notion is sometimes hard to define (is the system at its end of life when changing a key subsystem?).  The energy mix that supplies the system could be really different from an implementation of the system to another. In the primary aluminium industry for example, this could radically change the environmental impact of the system [L1], and the relative contributions of the subsystem to the system.

The fact is that these elements can be extremely important to orient the eco-design strategy of a company towards its customers and shareholders (towards the macro system) and suppliers (towards subsystems).

So our research question is formulated as: how to measure the contribution of a subsystem to the environmental impact of a complex system in a specific context?

We propose to study the relationship between the environmental impact of a subsystem and its system in a changing context. This will be performed thanks to two case studies with AREVA T&D. We have measured the contribution of a subsystem to the environmental impact of a complex system through a classical LCA approach described in ISO 14040 [I1] and two related case studies.

3-Methodology

-Overview of the methodology

In the first case, all the data were available in the company, so the LCA study has been focused on the subsystem and its contribution to the impact of the system.

In the second case, the data concerning the subsystem (which is the system of the first case study) were available in the company, but not the data concerning the system. A study from the literature that offers us a complete set of eco-indicators results was identified. Thus the LCA is performed by referring at each step to this previous paper, as shown on Figure 1.

We propose a short screening of this approach with two industrial case studies about AREVA T&D's conversion substations.

-Application

AREVA T&D PEM (Power Electronics Massy) designs, assembles and sells in the whole world conversion substations for the electrolysis of aluminium (see Figure 2). As part of the aluminium smelter, AREVA T&D wishes to identify:

 the contribution of an electrolysis substation to the environmental impact of primary aluminium production to orient its future eco-design actions with customers. Even if environmental assessments have already been performed on primary aluminium production, the detail level is never sufficient to distinguish the substation from the smelter.  the contribution of the substation subsystems to the environmental performance of the substation to orient internal eco-design actions.

These studies will permit to progress towards more eco-friendly products in accordance with the AREVA T&D environmental policy and previous works [B1, D1].

The next sections present in more details the two case studies.

4-Application -Scope of the study 4.1 -Systems description

Primary aluminium production is based on the Hall-Héroult process discovered in 1886, using aluminium electrolysis. This process follows different steps identified on Figure 3. We focus in this section on the aluminium electrolysis stage.

An aluminium smelter includes the aluminium electrolysis and casting steps of the primary aluminium production. It is particularly energy-intensivethe amount of energy consumed by a recent primary aluminium plant is comparable to the amount of energy delivered by a nuclear plant unit (about 1 GW) and it is then located where energy is relatively inexpensive and always available. That is why electricity is generally produced from hydropower, gas or coal. The smelter is moreover often located near consequent transportation ways to import alumina and export aluminium (harbors, roads or rail tracks).

A generic smelter consists in:

 potrooms that contains hundreds of electrolysis pots (commonly between 200 and 400 in a one-kilometer long building),  a casthouse,  an electrode plant that produces anodes for the electrolysis process,  an AC to DC conversion substation that supplies energy to the potlines from the grid (Figure 2),  some other elements such as storage and auxiliaries buildings, silos or transportation facilities. The conversion substation is a key element of an aluminium smelter, as it permits to convert energy from the high voltage network to energy that can be used for aluminium electrolysis.

A conversion substation is made of several groups (4 on Figure 2) which are composed of a regulating transformer, a rectifier transformer and a rectifier. The groups are connected on one side to the high voltage network through a high voltage substation (air or gas insulated, AC current). On the other side they are connected to a busbar that is directly connected to the electrolysis potline (DC current). Filters are also added to the assembly to protect the network against harmonics and to improve the power factor. All the groups are supervised by control elements which are also connected to the electrolysis pots control system to regulate the process.

-Data collection

As no internal data were available to model the primary aluminium production process, results from the literature were used.

Aluminium data in LCA databases are often based on reports from EAA (European Aluminium Association) [E1] or IAI (International Aluminium Institute) [I2] which are representative of the aluminium industry. These two organisms regularly update the data dedicated to LCA databases. They include mass, energy and emissions overview related to the different aluminium processes.

Other literature references have also been identified on the subject. Tan and Khoo [START_REF] Tan | An LCA study of a primary aluminum supply chain[END_REF] perform an LCA of primary aluminium production on an Australian case study, whereas Koch and Harnisch [KH1] focus on greenhouse gases for the European aluminium industry. Norgate et al. [N1] propose as well environmental indicators for different metal production including primary aluminium. Finally, Leroy [L1] offers very useful and complete environmental data for the European aluminium industry.

However, one very interesting study about the environmental assessment of primary aluminium production, based on a real case is the LCA conducted by Schmidt and Thrane commissioned by ALCOA [START_REF] Schmidt | Life cycle assessment of aluminium production in new Alcoa smelter in Greenland[END_REF]. Its goal is to quantify the environmental impact of a project of a new aluminium smelter in Greenland. It takes into account almost all the previous studies and proposes numerous different scenarios with different energy mixes and two types of pot technology ("existing" and "new").

However none of these papers distinguish the substation from the other capital goods (the smelter in particular). Our life cycle inventory data are mainly based on a substation for a 360,000 tons per year smelter (same capacity as the ALCOA Greenland project in [START_REF] Schmidt | Life cycle assessment of aluminium production in new Alcoa smelter in Greenland[END_REF]). For different reasons (time, data availability…) the substation modeling has been simplified. The only following equipments are considered: regulating transformers, rectifier transformers, rectifiers, busbars and civil engineering.

The LCI includes specific data concerning masses, distribution, energy and end of life. The other data (materials extraction and production, energy production and distribution, end of life) are generic data from the Ecoinvent 2007 and IDEMAT 2001 databases.

-Modeling

We choose to focus on three main scenarios from the Schmidt and Thrane study [START_REF] Schmidt | Life cycle assessment of aluminium production in new Alcoa smelter in Greenland[END_REF]: Schmidt & Thrane's functional unit is "1kg of virgin aluminium (ingots) supplied at a plant (100% aluminium, 0% alloying metals)" [START_REF] Schmidt | Life cycle assessment of aluminium production in new Alcoa smelter in Greenland[END_REF]. This functional unit is kept to obtain comparable results. As the substation is designed for a 360,000 tons per year smelter and is assumed to have a life time of n years, 1/(360,000,000*n) of the substation is allocated to 1kg of virgin aluminium. Three values are considered for n: 30, 40 and 50 years.



5-Application -Case studies

-Case study 1: Regulating transformers/Substation

We study in this first case study the environmental contribution of the regulating transformers to the electrolysis substation. A simplified mass balance is given for the modeled substation in These figures show that the five regulating transformers account for 12% of the total substation mass. On energetic aspects, they are responsible of about 31% of the electrical losses of the substation.

The LCA simulations give us the results presented in Table 3. In this table the contribution of the regulating transformers materials to the transformer is first evaluated, and then we assess the whole life cycle (including materials, fabrication, distribution, use and end of life) for each of the three scenarios described in Section 4.3. The LCIA of the substation is also given in Figure 4. It shows in particular that the distribution phase is negligible.

Figure 4. Example of life cycle impact assessment for Scenario C with a lifetime of 30 years

The regulating transformers are a major environmental contributor to the impact of the substation for all the Stepwise indicators. In terms of materials (including civil engineering), except for the mineral extraction criteria, they contribute to more than 50% to the substation impact. It could seem strange because the rectifier transformers are heavier than the regulating transformers. In fact this result is due to the mass of insulating oil which is more important for the regulating transformers than the rectifier transformers.

When including the other life cycle phases (in particular the electrical losses during 40 years), the contribution of the regulating transformers is lower. Scenario B (100% coal in China) and C (coal 62%, gas 9% and hydropower 29%, in Russia) are quite identical. The contribution in Scenario A (100% hydropower in Greenland) is about half the contribution in Scenarios B and C.

We can also notice that the variation of the indicators values is never higher than 1% by changing the lifetime to 30 or 50 years instead of 40 years, as it impact at once the transformers and the substation in the same magnitude.

-Case

Materials

This second case study considered the contribution of the substation to the environmental impact of primary aluminium production. So it includes the aluminium electrolysis stage, but also bauxite mining, alumina production as well as transports.

Concerning the smelter itself, Schmidt and Thrane [START_REF] Schmidt | Life cycle assessment of aluminium production in new Alcoa smelter in Greenland[END_REF] consider in 2009 that the electrolysis process needs 13.3 kWh (respectively 15.3 kWh) to produce 1 kg of liquid aluminium with a new pot technology (respectively an existing pot technology). In our study we consider that the substation is the same for the two types of technology. A calculation indicates that the substation electrical losses account to 1.5% (respectively 1.3%) of the energy necessary to electrolysis.

The results of the LCA simulations presented in Table 4 show the contribution of the whole substation life cycle to the primary aluminium production as described in [START_REF] Schmidt | Life cycle assessment of aluminium production in new Alcoa smelter in Greenland[END_REF]. The three scenarios are taking into account as well as two alternatives with existing technology instead of new technology (Scenarios A1 and C1).

Almost all the indicators are under 1% (or even 0,1%) except one (ecotoxicity, aquatic) for Scenario A and Scenario A1. For scenarios B, C and C1, most of the indicators are between 1 and 4% (which is not negligible), except ionizing radiation and ozone layer depletion which are lower, respiratory organics that accounts between 12 and 16% of the aluminium production, and ecotoxicity, aquatic, which shows problematic values (much more than 100%). These last values are mainly due to the transformer oil. One possible explanation is that oil is not taken into account in [START_REF] Schmidt | Life cycle assessment of aluminium production in new Alcoa smelter in Greenland[END_REF] when evaluating the capital goods impact from the USA IO-LCA database. It shows that those results have to be processed with attention. Further work will focus on this point.

Finally, changing the substation lifetime has a great impact for Scenario A. A lifetime of 30 years (respectively 50 years) instead 40 years causes a increasing (respectively decreasing) of all indicators of about 35% (respectively 20%). For Scenarios B and C, it concerns only some indicators, with equal or lower differences than Scenario A. As the smelter lifetime is a priori not correlated with the substation lifetime, it means that the relative contribution of the substation can be clearly modified. Those two case studies show that great dependences can appear when key parameters like lifetime or energy mix are changed, even if it is not always true. It is then useful to study in details these aspects in order to obtain valid conclusions.

-Discussion

Concerning the lifetime, which directly influences the environmental impacts of the use phase, the study shows that it does not influence the relative contribution of the substation elements to the substation, as their lifetime is correlated. But it clearly affects the substation contribution to the macro system (primary aluminium production). The technology choice (new or existing) has only minor effects on the results regarding the contribution of the substation on primary aluminium production.

The energy mix appears as extremely important in the two case studies. In the first one, the materials highly supplant the use phase for Scenario A (100% hydropower), whereas the contrary is observed in Scenarios B and C (dominated by coal). It means that environmental improvement ways could not be the same from a substation to another. This system is highly context-dependent.

As an illustration, some improvement actions (see Table 5.) can be proposed to minimize the environmental contribution of the subsystem to the system, depending of the energy mix.

6-Conclusions and perspectives

The two case studies exposed in this paper have shown that the environmental impact of a subsystem can be extremely dependent of the context of the macro system. It can clearly influence the LCA results, and thus the conclusions of the studies. We have in particular highlighted the great influence of the lifetime and the energy mix to the contribution of AREVA T&D's conversion substations to primary aluminium production. According to the context, LCAs will lead to different actions, which would not be identified in a generic assessment.

Concerning the lifetime, the problem is that the functional unit, described in ISO 14040 [I1], does not permit to include a more sophisticated model into LCA. Maintenance, which has not been taken into account in our study, and lifetime are key-elements to model the real life cycle of a product. They are necessary to assess the real environmental impact of a product in a usage context. When considering industrial systems, the lifetime is sometimes linked to political and economic choices (including ROI).

Then it appears necessary to build a model that consider life cycle costs, technological choices, performances, obsolescence and maintenance together. For example, a subsystem like the substation will be updated after some years, when the technology pot will be changed to increase the smelter capacity. Such a model would permit to optimize choices in a system perspective and a changing context. Further works will exploit those aspects.

7-Acknowledgment

We would like to thank gratefully Joël Devautour, François Puchar from AREVA T&D, as well as Anthony Rolland from Supmeca, Dominique Pareau from Ecole Centrale Paris and Daniel Afonso from CUBIK Partners.

Figure 1 .

 1 Figure 1. Articulation of the second case study

Figure 2 .

 2 Figure 2. Example of AREVA T&D conversion substation (ALUAR smelter, Argentina)

Figure 3 .

 3 Figure 3. Process flow of primary aluminium production

Table 1 . LCA problems by phase (from [RR1])

 1

	Phase	Problem
	Goal and scope	 Functional unit definition
	definition	 Boundary selection
		 Social and economic impacts
		 Alternative scenario considerations
	Life cycle	 Allocation
	inventory analysis	 Negligible contribution ('cutoff')
		criteria
		 Local technical uniqueness
	Life cycle impact	 Impact category and methodology
	assessment	selection
		 Spatial variation
		 Local environmental uniqueness
		 Dynamics of the environment
		 Time horizons
	Life cycle	 Weighting and valuation
	interpretation	 Uncertainty in the decision process
	All	 Data availability and quality
	Some aspects of these problems concern specific environmental contexts: functional unit definition,
	alternative scenario consideration, local technical or environmental uniqueness, spatial variation, and
	dynamics of the environment or time horizons.

Table 2

 2

. Figures are voluntary rounded off for confidentiality reasons.

Table 2 . Simplified mass balance for the substation

 2

	Regulating transformers	5*217 tons
	Rectifier transformers	5*245 tons
	Rectifiers	5*18 tons
	Busbars	600 tons
	Total mass (without civil engineering)	3000 tons
	Civil engineering	6240 tons
	Total mass	9240 tons

Table 3 . Relative contribution of the regulating transformers to the substation for the characterized Stepwise indicators Substation life cycle (lifetime of 40 years) Impact category

 3

		Materials	Scenario A	Scenario B	Scenario C
	Human toxicity, carcinogens	52.18%	10,37%	30,80%	30,71%
	Human toxicity, non-carc.	52.24%	10,18%	30,99%	30,98%
	Respiratory inorganics	55.61%	13,62%	31,01%	31,00%
	Ionizing radiation	52.95%	14,13%	27,06%	25,94%
	Ozone layer depletion	56.82%	11,65%	19,52%	18,75%
	Ecotoxicity, aquatic	56.10%	10,74%	30,16%	29,68%
	Ecotoxicity, terrestrial	52.62%	11,87%	30,63%	30,41%
	Nature occupation	51.29%	14,57%	30,92%	30,86%
	Global warming	54.91%	14,30%	30,93%	30,89%
	Acidification	56.04%	11,94%	30,96%	30,93%
	Eutrophication, aquatic	55.95%	13,33%	30,88%	30,80%
	Eutrophication, terrestrial	55.77%	14,61%	30,93%	30,88%
	Respiratory organics	54.80%	13,24%	30,90%	30,83%
	Photochemical ozone, vegetat.	55.07%	13,61%	30,91%	30,85%
	Non-renewable energy	56.70%	11,71%	30,29%	29,89%
	Mineral extraction	26.34%	12,14%	28,03%	26,60%

Table 4 . Relative contribution of the substation to the primary aluminium production for the characterized Stepwise indicators with a lifetime of 40 years

 4

		Scenario A	Scenario A1	Scenario B	Scenario C	Scenario C1
	Impact category	(new	(existing	(new	(new	(existing
		technology)	technology)	technology)	technology)	technology)
	Human toxicity, carcinogens	0,04%	0,02%	2,10%	1,56%	1,00%
	Human toxicity, non-carc.	0,01%	0,01%	2,92%	1,96%	1,96%
	Respiratory inorganics	0,07%	0,06%	15,89%	14,99%	12,79%
	Ionizing radiation	0,23%	0,23%	0,88%	0,71%	0,69%
	Ozone layer depletion	0,07%	0,07%	0,13%	0,11%	0,11%
	Ecotoxicity, aquatic	16,31%	16,18%	371,40%	240,05%	237,36%
	Ecotoxicity, terrestrial	0,14%	0,14%	2,54%	2,11%	1,94%
	Nature occupation	0,03%	0,03%	2,11%	1,68%	1,57%
	Global warming	0,07%	0,06%	2,80%	2,66%	2,31%
	Acidification	0,07%	0,06%	3,89%	3,64%	3,17%
	Eutrophication, aquatic	0,03%	0,03%	1,91%	1,55%	1,44%
	Eutrophication, terrestrial	0,08%	0,07%	2,76%	2,57%	2,28%
	Respiratory organics	0,03%	0,03%	2,09%	1,76%	1,59%
	Photochemical ozone, vegetat.	0,04%	0,04%	2,29%	1,92%	1,77%
	Non-renewable energy	0,35%	0,33%	2,82%	2,39%	2,16%
	Mineral extraction	0,84%	0,79%	4,29%	3,20%	3,04%

Table 5 . Example of eco-design actions according to the energy mix

 5

	System	Configuration	Improvement actions
	Regulating	100%	 Vegetal oil instead of mineral oil
	transformers	hydropower	 Mass decreasing
			 End of life improvement
	Regulating	100% coal	 Electrical losses decreasing
	transformers		 End of life improvement
	Substation	100%	Eco-design actions to improve the intrinsic substation performance
		hydropower
	Substation	100% coal	Collaboration with customer on eco-design


Olivier Teytaud

Sébastien Flory

Upper Confidence Trees with Short Term Partial Information

We show some mathematical links between partially observable (PO) games in which information is regularly revealed, and simultaneous actions games. Using this, we study the extension of Monte-Carlo Tree Search algorithms to PO games and to games with simultaneous actions. We apply the results to Urban Rivals, a free PO internet card game with more than 10 millions of registered users.

Introduction

The impact of partial observability in games and planning is studied in several papers, showing in particular that -Just one player and a random part makes the problem undecidable, even with a finite state space with reachability criteria [START_REF] Madani | On the undecidability of probabilistic planning and related stochastic optimization problems[END_REF]. -With two players with or without random parts, the problem is EXP, EXPSPACE, 2EXP (i.e. exponential time, exponential space, doublyexponential time) for the fully observable, no observation, and partially observable case respectivelly for the criterion of deciding whether a 100% winning strategy exists 3 . With exponential horizon, the complexities decrease to EXP, NEXP, EXPSPACE respectively [START_REF] Mundhenk | Complexity of finitehorizon markov decision process problems[END_REF]. -With two players without random part, the problem of approximating the best winning probability that can be achieved regardless of the opponent strategy is undecidable [START_REF] Teytaud | Decidability and complexity in partially observable antagonist coevolution[END_REF] by reduction to the one-player randomized case above in the no observation case; the best complexity upper bounds for bounded horizon are 3EXP (for exponential horizon) and 2EXP (for polynomial horizon).

Section 2 presents the frameworks used in this paper: games, acyclic games, games with simultaneous actions, games with hidden information. Section 3 presents a brief overview of computational complexity in games, and provides some new results around the framework of short term hidden information and games with simultaneous actions. Section 4 presents a variant of the Upper Confidence Tree algorithm for games with simultaneous actions. Section 5 presents experimental results on Urban Rivals, a free and widely played game with partial information.

We consider finite games, represented by finite directed graphs. Each node, also termed a state, is equipped with an observation for player 1, and an observation for player 2. Each state is either of the form P 1 (meaning that player 1 chooses the next state as a function of his previous observations), or of the form P 2 (meaning that player 2 chooses the next state as a function of his previous observations), or randomized (the next state is randomly drawn among the states proposed by the directed graph), or simultaneous (both players choose an action as a function of their previous observations and the next state is chosen as a function of these two actions). All actions are chosen from finite sets. A node is fully observable if there's no other node with the same observation for player 1 and no other node with the same observation for player 2. There are leafs which are a win for player 1, leafs which are a win for player 2, leafs which are a draw, and infinite loops are a priori possible. Nodes which are a draw or a win for a player are all leaf nodes; these nodes are fully observable. A game is turn-based if there's no simultaneous actions in it. Examples: (i) The rock-paper-scissor game has one node with simultaneous actions, and leafs. (ii) Chess, Draughts, Go, are games with no simultaneous actions. (iii) Bridge, Poker, Scrabble, are games with no simultaneous actions and partial observation. (iv) Urban Rivals is a turn-based game with hidden information; it can be rewritten as a game with no partial information but with simultaneous action (this will be detailed in this paper). (v) The strategies of American football are simultaneously chosen and kept private some time. (vi) In the Pokemon card game (as well as in many similar card games), both players choose their deck simultaneously.

It is known that with no restriction, this setting is undecidable (even if the graph is finite). For example, [START_REF] Madani | On the undecidability of probabilistic planning and related stochastic optimization problems[END_REF] has shown that with one player only, no observation, random nodes, the probability of winning, when starting in a given node, and for an optimal strategy, is not computable, and even not approximable. [START_REF] Teytaud | Decidability and complexity in partially observable antagonist coevolution[END_REF] has shown that this also holds for two players and no random node. Some important restrictions simplifying the analysis of games are as follows:

-Looking for strategies winning with probability 1 is much easier.

The existence of strategies winning with probability 1, independently of the opponent, is decidable for 2 players, even in partially observable environments (see [START_REF] Hearn | Games, Puzzles, and Computation[END_REF], showing that this is not true if we have a team of 2 players against a third player). -The fully observable setting is always decidable, with complexity reduced by far in the case of limited horizon; see [START_REF] Rintanen | Complexity of Planning with Partial Observability[END_REF][START_REF] Mundhenk | Complexity of finitehorizon markov decision process problems[END_REF] for more on this for the case in which we consider the existence of strategies winning with probability 1 and [START_REF] Teytaud | Decidability and complexity in partially observable antagonist coevolution[END_REF] for the choice of optimal moves.

In this paper we will investigate the effect of two other possible assumptions: (i) no partial observability, but simultaneous actions; (ii) partial observability, but with hidden information which becomes visible after a bounded number of time steps; these two conditions will be shown nearly equivalent and we will also show that with limited horizon these assumptions have a big impact.

Bounded Horizon Hidden Information Games (BHHIG)

We define games in BHHIG(H) as games (in the sense above) verifying the following assumptions: (i) the graph is finite; (ii) each node is visited at most once (acyclic graph); (iii) there's no random node and no node with simultaneous actions; (iv) there's no string of length H in the graph containing no fully observable node. The crucial assumption here is the last one.

Remark: We here forbid random nodes. This is in fact not necessary in our analysis and in our algorithms, but it will simplify the discussion.

Games with Simultaneous Actions (GSA)

We define games in GSA as games (in the sense above) verifying the following assumptions: (i) there's no random node; (ii) there's no partially observable node; (iii) but nodes with simultaneous actions are allowed. The crucial assumption is here the presence of nodes with simultaneous actions. Without such nodes, the solving of such games is well known (see [START_REF] Mundhenk | Complexity of finitehorizon markov decision process problems[END_REF][START_REF] Rintanen | Complexity of Planning with Partial Observability[END_REF][START_REF] Papadimitriou | The complexity of markov decision processses[END_REF] for more on this).

Remark: We here forbid random nodes. This is in fact not necessary in our analysis and in our algorithms (and random nodes can be simulated by nodes with simultaneous actions), but it will simplify the discussion.

Representing BHHIG as GSA and GSA as BHHIG

In this section, we show a correspondence between GSA and BHHIG(H).

A BHHIG(H) is a GSA. We consider a game G in BHHIG(H), and show how to rewrite it as a game in GSA.

We consider a fully observable node n of G. By the crucial assumption on BHHIG(H), all paths starting at G reach another fully observable node after a length at most H. Let G ′ be the subset of G covered by these paths (the root is n and leafs are fully observable nodes). Let -S 1 be the finite set of deterministic strategies that can be chosen by player 1 before reaching another fully observable node and let -S 2 be the finite set of deterministic strategies that can be chosen by player 2 before reaching another fully observable node.

Then, the subgraph G ′ can be replaced by a simultaneous node (player 1 chooses a strategy in S 1 and player 2 chooses a strategy in S 2 ), and the leafs of G ′ ; we then get a node with simultaneous actions. We can do this for all fully observable nodes, and then all partially observable nodes will be removed; this concludes the proof.

A GSA is a BHHIG(H). We consider a game G in GSA, we show that it can be encoded as a BHHIG(H). For this, we just have to encode a node with simultaneous actions as two turns with partial observability, before reaching, again, a node with full observability (therefore the game is BHHIG(2), i.e. H = 2). The idea is that one player chooses his action a 1 ; this action a 1 is not seen by the other player who then chooses a 2 ; and then both players observe the two actions. This concludes the proof. An example is given in Fig. 1: Rock-Paper-Scissor is classically understood as a player game with simultaneous play, and is here presented as a partially observable turn-based game.

Complexity of games with simultaneous actions

We have seen how to rewrite a BHHIG(H) as a GSA; we here discuss the complexity of GSA. In order to formalize this complexity, we will consider any representation of a game such that for a polynom p(.); -A state is described with size p(n); -For each player, there are at most p(n) legal actions in a given state, and they can be all computed in time p(n); -The transition from a state and a pair of actions to a new state takes time at most p(n); -The number of possibles states is O(exp(p(n))).

The class GSA depends on the chosen polynom p.

Then we claim the following: Theorem: Consider a GSA with acyclic graph. Then, the optimal move can be computed in time EXP.

Proof: The sketch of the proof is as follows. We can sort the nodes in reverse topological order. Then each Bellman value (Nash value, if you prefer) of a node is computed by solving the matrix game associated to actions in that node, if all Bellman values of later nodes are already known. As the number of nodes is exponential and each matrix game can be solved in polynomial time by linear programming, the overall algorithm solves the problem in time EXP.

Upper Confidence Trees for games with simultaneous actions

We assume in this section that the reader is familiar with the Monte-Carlo Tree Search (MCTS) and Upper Confidence Tree (UCT) literature [START_REF] Coulom | Efficient Selectivity and Backup Operators in Monte-Carlo Tree Search[END_REF][START_REF] Kocsis | Bandit based Monte-Carlo planning[END_REF][START_REF] Lee | The Computational Intelligence of MoGo Revealed in Taiwan's Computer Go Tournaments[END_REF]. We here focus on the experimental application of MCTS to acyclic GSA games.

The Upper Confidence Tree algorithm

We briefly recall the UCT algorithm in Algo. 1.

Algorithm 1

The UCT algorithm in short.

UCT algorithm.

Input: a game, a state S, a time budget.

Output: an action a.

while Time not elapsed do s = S. // starting a simulation. while s is not a terminal state do Define the score of a legal action a in s as the sum of:

• its exploitation score: the average reward of past simulations using action a in state s;

• its exploration score:

log(n(s)+2)
n(s,a)+1 , where • n(s) is the number of past simulations crossing state s; • n(s, a) is the number of past simulations applying action a in state s. Choose the action a which has maximum score. Let s ′ be the state reached from s when choosing action a. s = s ′ end while // the simulation is over; it starts at S and reaches a final state. Get a reward r = Reward(s) // s is a final state, it has a reward. For all states s in the simulation above, let r nbV isits(s) (s) = r. end while Return the action which was simulated most often from S.

The reader is referred to [START_REF] Kocsis | Bandit based Monte-Carlo planning[END_REF] for more information on UCT; we here focus on the extension of UCT to games with nodes with simultaneous actions, i.e. GSA, in the acyclic case.

Adapting UCT to the GSA acyclic case

We adapt UCT to acyclic GSA as follows. We use the EXP3 algorithm for GSA nodes (variant of the Grigoriadis-Khachiyan algorithm[5, 2, 1, 3]), leading to a probability of choosing an action of the form η + exp(ǫs)/C where η and ǫ are Algorithm 2 Adapting the UCT algorithm for GSA cases.

UCT algorithm for GSA problems. Input: a game, a state S, a time budget. Output: an action a (for each player if the root is in P12, for the player to play otherwise). Initialize s1 and s2 at the null function (equal to 0 everywhere). while Time not elapsed do // starting a simulation. s = S. while s is not a terminal state do if s is a P1 or P2 node then Define the score of a legal action a in s as in UCT.

Choose the action a which has maximum score. Let s ′ be the state reached from s when choosing action a. else Choose action a1 for player 1 randomly, with action a chosen with probability p1(a1, s) = η + exp(ǫs1(a1, s))/C1. (C is a normalization so that the sum is 1) Choose action a2 for player 2 randomly, with action a chosen with probability p2(a2, s) = η + exp(ǫs2(a2, s))/C2. (C is a normalization so that the sum is 1) Let s ′ be the state reached from s when choosing actions a1, a2. end if s = s ′ end while // the simulation is over; it starts at S and reaches a final state. Get a reward r = Reward(s) // s is a final state, it has a reward. For all states s in the simulation above, let: s1(a1, s) = s1(a1, s) + r/p1(a1, s), s2(a2, s) = s2(a2, s) + r/p2(a2, s).

end while if The root is in 1P or 2P then

Return the action which was simulated most often from S. else Choose action a with probability proportional to its number of simulations. end if parameters, s is the estimated sum of rewards for the considered action, and C is the normalization constant. The algorithm is presented in Alg. 2.

We'll see later how to choose ǫ and η; C 1 , C 2 are normalization constants (so that the sum of the probabilities of the actions is 1). We did not consider random nodes here, but they could easily be included as well. We do not write explicitly a proof of the consistency of these algorithms, but we guess that the proof is a consequence of properties in [START_REF] Grigoriadis | A sublinear-time randomized approximation algorithm for matrix games[END_REF][START_REF] Lai | Asymptotically efficient adaptive allocation rules[END_REF][START_REF] Auer | Gambling in a rigged casino: the adversarial multi-armed bandit problem[END_REF][START_REF] Audibert | Minimax policies for adversarial and stochastic bandits[END_REF]. We'll see the choice of constants below.

Experiments

We discuss below various experiments we performed for validating or improving our implementation. We compared EXP3 to simpler formulas. We then tested the scalability of the implementation (Section 5.2).

The program was then launched on the website, for playing against humans (Section 5.3). Please keep in mind, in all this section, that for a game like Urban Rivals, based on guessing the opponent's strategy, results on one single game are noisy; as well as in Poker, it does not make sense to have 80 % of winning rate (as we can see in Go). The numbers we get (average results for one game) are therefore always close to 50%; nonetheless, when considering reasonably long sequences of games, they provide very significant improvements.

The EXP3 algorithm

We refer to [START_REF] Audibert | Minimax policies for adversarial and stochastic bandits[END_REF] for an introduction to the EXP3 algorithm and variants.

EXP3 vs an ǫ-greedy algorithm. We compared EXP3 as in [START_REF] Audibert | Minimax policies for adversarial and stochastic bandits[END_REF] to a simple η-greedy algorithm, choosing any move, randomly and uniformly, with probability η = min(1, 1.2 K/t) with K the number of possible actions. -the move with highest average reward otherwise (when the move is not simulated, it has an infinite average reward). EXP3+UCT vs UCT alone. Our algorithm is based on using EXP3 in nodes with simultaneous actions and UCT in other nodes; this dichotomy is intuitively quite reasonable. However, what happens if we just consider UCT-like formulas everywhere ? We first tested what happens if we replace EXP3 by a simple UCT algorithm for each player, even in nodes with simultaneous actions. We just used the UCT formula with constants as used in nodes with no simultaneous actions. We got 45.8% ± 1.4% as a success rate against the EXP3 version with 10 000 simulations per move, after having added some random exploration with a fixed probability (otherwise results were very poor) -so with random exploration, UCT is not so far from EXP3 (yet, EXP3 has the advantage, with a speed-up around 2 if we trust the scalability analysis below, and results with UCT could only be obtained at the price of the tuning of a random exploration whereas EXP3 is tuned according to [START_REF] Audibert | Minimax policies for adversarial and stochastic bandits[END_REF]).

Pruning the exploration in EXP3. In UCT-like algorithms, the optimal moves are chosen exponentially more often than other moves. As a consequence, a bandit in UCT can recommend, when all simulations are over, any move with maximal number of simulations -this is clearly consistent. EXP3 has a different goal; as it considers an adversarial case (for us, nodes with simultaneous actions), it must not outputs a single move as a decision, but several moves with their associated probabilities -this is (in the general case) a mixed strategy, and, unless the game has the particularity of having pure Nash equilibria, there's no good recommendation strategy outputting deterministically a single move. The standard property of EXP3 is that the Nash is approximated by the empirical frequency; action i should be played with probability proportional to the number of simulations of action i. However, a part of the simulations are pure random exploration (this is the η parameter); could we remove this from the result, before extracting the Nash approximation ? Asymptotically, this effect is negligible, but is there something to win, non-asymptotically ?

In order to test this, we designed a formula sublinear in the maximum number max of simulations of the actions in the root, namely t ′ = t 0.95 , and kept only actions with a number of simulations at least t ′ . Results were as follows: Results are significant as we here have doubled standard deviations and not standard deviations. The choice of the 0.95 exponent was our first random guess, maybe we can have improvements by a careful tuning. A subtle point must be pointed out, here. These experiments are conducted against our EXP3+UCT algorithm; this is an algorithm which tries to play the Nash equilibrium. Playing against a "Nash" opponent has the advantage that the opponent can not "learn" our weaknesses; therefore, the good results above might hide the fact that our player is less randomized than the original one, and therefore maybe it is possible for a non-Nash opponent to "learn" our (non-asymptotic) lack of randomization. Testing this is difficult however, and we did not see a tendency in this direction from the games we have seen.

Conclusion.

We have seen that, on Urban-Rivals, the combination EXP3+UCT works better than UCT+ǫ-greedy algorithms, and significantly better than UCT alone. We could slightly improve the AI by implementing some ideas, and a bit more by brute-force tuning.

Scalability

We tested the scalability, i. The crucial points is how many "pilz" you use per turn: "more pilz" implies a better probability of winning; the key point is that the choice is the number of pilz is made privately until the end of the turn. At the end of each turn all the hidden information is revealed.

Games against humans

Urban Rivals (Fig. 2) has 11 millions of registered users. It's a Card Game, related to games like Pokemon or Magic, with Partial Observability, a small number of turns leading to fast games (often less than a minute) 4 . First, each player chooses a deck, which contains four cards (see Fig. 2 for a few examples).

The decks are chosen privately, but then shown to the opponent. Each card is equipped with a default strength (a stronger card is more likely to win a fight) and a default power (a card with more power makes more damages to the opponent). At each turn (out of four), one of the players (alternatively) chooses (publicly) one of his four cards, and then chooses (privately) the strength of the attack; the other player chooses publicly one of his cards and the strength. The strength does not come for free -each point is taken from a finite quantity. There is a strong bluff component in Urban Rivals, similarly to Poker: one might use a card with little strength so that the opponent wastes strength. With 200 000 simulations per move, the program reached 1240 ELO the 30th of November, i.e. the top 1.5%, but then decreased to 1144 ELO, i.e. the top 9% ; the precise rank is probably between these two values. A second run after technical improvements the 13th of December is ranked 84 th on 8030 players (top 1%) and is still improving.

Conclusion

UCT is a major breakthrough in Markov Decision Processes, and PO games are a great challenge. The general case of PO games is undecidable but we here propose a sound extension of UCT to an important subclass of PO games, including games with bounded horizon and simultaneous actions. The resulting algorithm outperformed UCT at Urban-Rivals, and was well ranked on the ELO scale. A further work is the analysis of the parametric complexity (function of H) in BHHIG(H); Urban-Rivals is a nice case thanks to a small H.

On the application side, we have not yet a clear understanding of how many games are BHHIG(H) for a reasonnable value of H; "mister X" is a natural other examples. Also, as using a complete memory of observations is probably not that useful, we might consider to which extent usual PO games can be approximate by BHHIG(H) games.

Fig. 1 .

 1 Fig. 1. The Rock-Paper-Scissors game, presented as a partially observable turn-based game: A=rock, B=scissors, C=paper. Here, Min does not see the action chosen by Max; this is clearly equivalent to the classical formulation by simultaneous actions.

Fig. 2 .

 2 Fig.2. Examples of Urban Rivals characters. Characters have different abilities: strong attack (better probability of winning the turn); better strength (more damages in case of won turn). The crucial points is how many "pilz" you use per turn: "more pilz" implies a better probability of winning; the key point is that the choice is the number of pilz is made privately until the end of the turn. At the end of each turn all the hidden information is revealed.

The random part has no impact because we look for a strategy winning with probability 100 %.

A few options are removed from this short description, but they are taken into account in the implementation and do not change the principle.

Acknowledgements

The authors are grateful to Grid5000 for providing computational resources around the parallelization of MCTS, and to Dagstuhl and Birs for fruitful seminars. We are also grateful to ANR for funding, through the EXPLO-RA project.


Mohamed Daoudi
email: mohamed.daoudi@lifl.fr

Tarik Filali Ansary

Julien Tierny
email: julien.tierny@lifl.fr

Jean-Philippe Vandeborre
email: jean-philippe.vandeborre@lifl.fr

3D-mesh models: view-based indexing and structural analysis

Keywords: 3D-model, 3D-mesh, indexing, view based approach, Bayesian indexing, topological analysis, Reeb graph

3D-mesh models are widely used to represent real objects in synthesized scenes for multimedia or cultural heritage applications, medical or military simulations, video games and so on. Indexing and analyzing these 3D data is a key issue to enable an effective usage of 3D-mesh model for designers and even for final users. The researches of our group mainly focus on these problems. In this paper, we present the work of our group for the DELOS NoE during the year 2006. We have worked on two approaches for 3D-model indexing and analyzing: view-based approach and structural approach. View-based approaches for 3D-model indexing are a very intuitive way to retrieve 3Dmodels among wide collections by using 2D natural views (as a human uses to represent 3D-objects). Structural analysis of a 3D-mesh model gives a structural decomposition of the object from a raw boundary representation of it, then this decomposition can be used to segment or index 3D-models.

Introduction

Exploiting the information contents of digital collections poses several problems. In order to create added-value out of these collections, users need to find information that match certain expectations -a notoriously hard problem due to the inherent difficulties of describing visual information content.

In recent years, as a solution to these problems, many systems have been proposed that enable effective information retrieval from digital collections of images and videos. However, solutions proposed so far to support retrieval of images and videos -which are intrinsically bidimensional -are not always effective in application contexts where the information is intrinsically three-dimensional.

To satisfy this need, a variety of retrieval methods have been proposed that enable the efficient querying of model repositories for a desired 3D shape, many of which use a 3D-model as a query and attempt to retrieve models with matching shape from the database.

In our group, we have worked on two approaches: view based approach and structural approach. This paper presents, in the next two sections, these approaches, achieved work of our group for the DELOS NoE during the year 2006.

View-based Approach

The human visual system has an uncanny ability to recognize objects from single views, even when presented monocularly under a fixed viewing condition. The issue of whether 3D-object recognition should rely on internal representations that are inherently three-dimensional or on collections of two-dimensional views has been explored by Risenhuber and Poggio [START_REF] Riesenhuber | Models of object recognition[END_REF]. They show that, in a human vision system, a 3D-object is represented by a set of 2D-views.

The process of comparing two 3D-objects using their views can be separated into two main steps: 3D-model indexing (also known as the off-line step) and 3D-model retrieval (the on-line step). In the 3D-model indexing step, each 3Dobject is characterized by a set of 2D views. For each view, a 2D descriptor is calculated. In the 3D-model retrieval step, the same descriptor is applied to the 2D request views. A matching process is then started to match the request 2D views to the views from the 3D-objects of the database.

Characteristic view selection

The main idea of view-based similarity methods is that two 3D-models are similar, if they look similar from all viewing angles. This paradigm leads to the implementation of query interfaces based on defining a query by one or more views, sketches, photos showing the query from different points of view.

A point which will have an impact on the effectiveness and the speed of the view based methods is the number and the position of views used to describe a 3D-object. This number is directly related to the performances of the system. It is necessary to decrease to the number of views to have a fast method, all in preserving the descriptive capacity of the views. Two approaches can be used to choose the number of characteristic views: using a fixed and restricted number of views; or using a dynamic number of views, that correspond the number of views to the geometrical complexity of views.

In the Adaptive Views Clustering (AVC) method, presented by our group [START_REF] Filali Ansary | A bayesian search engine using adaptive views clustering[END_REF], we use an initial set of 320 views to select positions for the views, which must be equally spaced, we use a two-unit icosahedron centered on the origin. We subdivide the icosahedron twice by using the Loop-subdivision schema to obtain a 320 faceted polyhedron. To generate the initial set of views, we place the camera on each of the face-centers of the polyhedron looking at the coordinate origin. To represent each of these 2D views, we use 49 coefficients of Zernike moment descriptor [START_REF] Khotanzad | Invariant image recognition by Zernike moments[END_REF]. Finally, the initial set of views has to be reduced as we want from the method to adapt the number of characteristic views to the geometrical complexity of the 3D-model.

As every 2D view is represented by 49 Zernike moment coefficients, choosing a set of characteristic views that best characterise the 3D-models (320 views) is equivalent to choose a subset of points that represent a set of 320 points in a 49-dimension space. Choosing X characteristic views which best represent a set of N = 320 views is well known as a clustering problem.

This kind of problem is generally solved by using K-means algorithm [START_REF] Duda | Pattern classification and scene analysis[END_REF]. Its attractiveness lies in its simplicity and in its local-minimum convergence properties. However, it has one main shortcoming: the number of clusters K, no a priori known in our problem, has to be supplied by the user. To avoid this problem, we adapted a method derived from K-means -called X-means [START_REF] Pelleg | X-means: Extending k-means with efficient estimation of the number of clusters[END_REF] -, and we also used a Bayesian Information Criteria (BIC) [START_REF] Schwarz | Estimating the dimension of a model[END_REF], which scores how likely the representation model fits the data. More details about this process can be found in [START_REF] Filali Ansary | A bayesian search engine using adaptive views clustering[END_REF].

Probabilistic approach for 3D-model indexing

The main idea of our probabilistic approach is that not all views of a 3D-model have the same importance. There are views which represent the 3D-model better than others. On the other hand, simple objects (e.g. cube, sphere) can be at the root of more complex objects, so they have a higher probability to be relevant. In this section, we present a probabilistic approach that takes into account that views do not have the same importance, and that simple objects have higher probability to appear than more complex one.

According to the previous step (characteristic view selection), each 3D-model of the collection is represented by a set of characteristic views V = {V 1 , V 2 , . . . , V C }, with C the number of characteristic views. Moreover, to each characteristic view corresponds a set of represented views called V r .

We want to find the 3D-models that corresponds to one or more request photos -which could also be the characteristic views of a 3D-model given as a query. We assume that in a query Q = {I 1 , I 2 , . . . , I K } all K images represent the same object.

Considering a query Q, we wish to find the 3D-model M i from the collection which is the closest to the query Q. This model is the one that has the highest probability P (M i |Q). A query is composed of one or more images, then this probability can be written:

P (M i |Q) = K k=1 1 K P (M i |I k ),
with K the number of images in the query Q.

The Bayesian retrieval framework we developed, takes into account the number of characteristic views of the 3D-models and the importance (amount of information) of their views. More details about our probabilistic approach can be found in [START_REF] Filali Ansary | A bayesian search engine using adaptive views clustering[END_REF] for a general explanation of our Bayesian framework, and [START_REF] Filali Ansary | On 3D retrieval from photos[END_REF] especially for 3D-model retrieval system with photo-oriented queries.

Experimental results

In this section, we present the experimental process and the results we obtained. The algorithms we described in the previous sections have been implemented using C++ and the TGS Open-Inventor libraries. The system consists of an off-line characteristic view extraction algorithm and an on-line retrieval process.

To experiment our algorithms, we also developed an on-line 3D search engine1 . Our search engine can be reached from any device having compatible web browser (PC, PDA, SmartPhone, etc.). Depending on the web access device he/she is using, the user face two different kind of web interfaces : a rich web interface for full-featured web browsers, and a simpler interface for PDA web browsers. In both cases, the results returned by the 3D search engine are the same. The only difference lies in the design of the results presentation. Figure 1 shows three screenshots of our 3D retrieval system in its rich web interface version. Request could be expressed as a 3D-model, a 2D-sketch or one or more photos.

To evaluate our method, we used the Princeton Shape Benchmark database2 (known as PSB), a standard shape benchmark widely used in shape retrieval community. PSB appeared in 2004 and is one of the most exhaustive benchmarks for 3D shape retrieval. It contains a database of 1814 classified 3D-models collected from 293 different Web domains. There are many classifications given to the objects in the database. During our experiments we used the finest granularity classification, composed of 161 classes. Most classes contain objects with a particular function (e.g cars). Yet, there are also cases where objects with the same function are partitioned in different classes based on their shapes (e.g, round tables versus rectangular tables). The mean number of views for the PSB is 23 views per model. The mean size for a 3D-model descriptor is 1,113 bytes.

Our method provides more accurate results with the use of Bayesian probabilistic indexing. The experiment shows that our method Adaptive Views Clustering (AVC) gives better performance than 3D harmonics, Radialized Spherical Extent Function, and Gaussian Euclidean Distance Transform on the Princeton 3D Shape Benchmark database. Light Field Descriptor gives better results than our method but uses 100 views, does not adapt the number of views to the geometrical complexity, and uses two descriptors for each view (Zernike moments and Fourier descriptor), which makes it a slower and more memory consuming compared to the method we have presented.

Overall, we conclude that AVC gives a good compromise between quality (relevance) and cost (memory and on-line comparison time) for the 3D-models of the Princeton 3D Shape Benchmark.

To evaluate the algorithms in the case of 3D retrieval by a set of photos, we have selected 50 images from the Internet. The images correspond to 10 classes of the Princeton Shape Benchmark (five images per class): Airplanes, Bicycles, Chairs, Dogs, Guns, Hammers, Humans arms out, Helicopters, Pots and Swords. The images are composed of six sketches, six synthesized images and 38 real photos of different sizes. Figure 1 shows the results of a query using (from left to right) one, two and three images of a bicycle. The left side of the figures represent the queries and the right side represent the 16 top retrieved 3D-models. From the seven 3D-models representing a bicycle in the database, three are in the fifteen top retrieved 3Dmodels when using only one photo. This number raises to four out of seven when two photos are used. Using three images, we retrieved five out of seven in the top sixteen retrieved 3D-models. The recall/precision curves obtained in [START_REF] Filali Ansary | On 3D retrieval from photos[END_REF], show that two or three photos makes a good compromise between time-effort and accuracy.

To extend his/her search, the user can click on a 3D-model from the result window. This 3D-model is then sent to the search engine and used as a query. In this case, the whole set of characteristic views of the 3D-model is considered as the set of query photos. So, the retrieval principle is exactly the same as the one described in the previous section.

At last, to give an idea of our framework performance, in the off-line process, the characteristic view selection takes about 18 seconds per model on a PC with a Pentium IV 2.4 GHZ CPU. In the on-line process, the comparison takes less than 1 second for 1814 3D-models from the PSB.

Structural Approaches

Structural indexing of 3D shapes is an interesting direction of research. It enables to retrieve similar 3D shapes that have different postures [START_REF] Hilaga | Topology matching for fully automatic similarity estimation of 3D shapes[END_REF] and provides a promising framework for partial shape retrieval [START_REF] Funkhouser | Modeling by example[END_REF]. Our group focuses on the development of 3D mesh structural description algorithms based on topological skeletons [START_REF] Biasotti | An overview on properties and efficacy of topological skeletons in shape modelling[END_REF].

These approaches study the properties of real valued functions computed over triangulated surfaces. Most of the time, those functions are provided by the application context, such as scientific data analysis. When dealing with topological skeletons, it is necessary to define an invariant and visually interesting mapping function, which remains an open issue [START_REF] Biasotti | An overview on properties and efficacy of topological skeletons in shape modelling[END_REF]. Moreover, traditional topological graph construction algorithms assume that all the information brought by the mapping function is pertinent, while in practice, this can lead to large graphs, encoding noisy details.

Finally, topological approaches cannot discriminate visually interesting subparts of identified connected components, like the phalanxes of a finger. This is detrimental to certain applications, such as mesh deformation.

Our group proposed a novel and unified method which addresses the above issues [START_REF] Tierny | 3D mesh skeleton extraction using topological and geometrical analyses[END_REF][START_REF] Tierny | Invariant high-level reeb graphs of 3D polygonal meshes[END_REF].

Method overview

Given a connected triangulated surface T , we propose a unified method to decompose T into visually meaningful sub-parts, connected components, considering the topological and geometrical characteristics of discrete contours. The algorithm proceeds in three stages. Firstly, mesh feature points are extracted (fig. 2(a)) in order to compute an invariant and visually interesting mapping function (fig. 2(b)), denoted f m in the rest of the paper, revealing the most relevant parts of the mesh. Secondly, for each vertex in the mesh, we compute its discrete contour, a closed curve traversing it which is carried by the edges of T , and approximating f m continuous contour. Thirdly, as the set of discrete contours recovers the entire mesh, it is possible to analyze each contour characteristics, either to detect topological changes (enabling a pertinent Reeb graph construction, fig. 2(c)) or to detect geometrical transitions (enabling an approximation of constrictions, fig. 2(d)). The constriction approximation enables the refinement of Reeb graphs into enhanced topological skeletons (fig. 2(e)). The enhanced topological skeleton could then be used in different ways: 3D-mesh deformation (fig. 2(f)), indexing, etc.

Detailed methods and algorithm as well as extended results can be found in [START_REF] Tierny | 3D mesh skeleton extraction using topological and geometrical analyses[END_REF][START_REF] Tierny | Invariant high-level reeb graphs of 3D polygonal meshes[END_REF].

Results

Our scientific contribution resides in three points. Figure 3 shows several dual Reeb graphs obtained with the very first steps of our method, without any refinement, with regard to f m . Connected components are represented by the nodes located at their barycenter. Figure 4 shows several enhanced topological skeleton thanks to the constriction detection process. The enhanced topological skeleton is refined compared to classical Reeb graphs and shows more details in sub-parts.

A video demonstration of this work is available in http://www.telecom-lille1. eu/people/tierny/stuff/videos/tierny_pacific06.avi

Applications of enhanced topological skeletons

Each node of the extracted skeleton references a surface patch on the mesh. This link between the surface and the skeleton enables applications like hierarchical semantic-oriented segmentation [START_REF] Tierny | Topology driven 3D mesh hierarchical segmentation[END_REF] or shape retrieval by part [START_REF] Tierny | Reeb chart unfolding based 3D shape signatures[END_REF]. This is the next step of our work we are currently investigating.

Based on our previous work [START_REF] Tierny | 3D mesh skeleton extraction using topological and geometrical analyses[END_REF], we address the semantic-oriented 3D-mesh hierarchical segmentation problem using enhanced topological skeletons [START_REF] Tierny | Topology driven 3D mesh hierarchical segmentation[END_REF]. This high level information drives both the feature boundary computation as well as the feature hierarchy definition. Proposed hierarchical scheme is based on the key idea that the topology of a feature is a more important decomposition criterion than its geometry. First, the enhanced topological skeleton of the input triangulated surface is constructed. Then it is used to delimit the core of the object and to identify junction areas. This second step results in a fine segmentation of the object. Finally, a fine to coarse strategy enables a semanticoriented hierarchical composition of features, subdividing human limbs into arms and hands for example. An example of such a multi-level segmentation is shown in figure 5. Reeb graph based segmentation can also be employed for the problem of arbitrary genus surface comparison [START_REF] Tierny | Reeb chart unfolding based 3D shape signatures[END_REF]. In this work, a novel surface parameterization based technique that addresses the pose insensitive shape signature problem for surface models of arbitrary genus, is presented. 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. The gain provided by this new signature as well as its interest for partial shape similarity are demonstrated in [START_REF] Tierny | Reeb chart unfolding based 3D shape signatures[END_REF].

Conclusion

This paper briefly presents two of the main research interests of our group: view-based 3D-model indexing and 3D-mesh structural analysis.

In the first topic, we proposed a entire framework for the indexing of 3Dmodels: a dynamic characteristic view selection process that adapts the number of characteristic view to the complexity of the 3D-model, and a Bayesian approach to 3D-model indexing based on the characteristic views. The framework is capable to manage 2D-view queries (one or more photos) and 3D-model queries.

In the second topic, we presented our method to topologically analyze 3Dmesh model and obtain a structural decomposition named enhanced topological skeleton. This method uses a novel approach to feature point extraction as well as mapping function computation. Moreover, the enhancement of Reeb graphs is obtained with a constriction evaluation process. The resulting enhanced topological skeleton is a major tool for our future works on 3D-model segmentation and 3D partial shape retrieval that already give promising results.

Fig. 1 .

 1 Fig.1. 3D retrieval results using (from left to right) one, two and three photos.

Fig. 2 .

 2 Fig. 2. Main steps of the decomposition on a standard model.

  (i) We propose an original and straightforward algorithm for feature point extraction. It can resolve extraction on constant curvature areas -such as spheres -and it is robust against variations in mesh sampling and model pose. (ii) We show that a discrete contour formulation enables, without re-meshing and without any input parameter, a pertinent Reeb graph construction providing visually meaningful graphs, affine-invariant and robust to variations in mesh sampling. (iii) We show that the geometrical information brought by discrete contours enables the approximation of constrictions on prominent components providing enhanced topological skeletons, and consequently Reeb graph refinement.

Fig. 3 .

 3 Fig. 3. Dual Reeb graphs of primitive and complex shapes (fm function).

Fig. 4 .

 4 Fig. 4. Constriction approximations and enhanced topological skeletons of standard models.

Fig. 5 .

 5 Fig. 5. Hierachical mesh segmentation based on skeleton extraction.

http://www-rech.telecom-lille1.eu/3dretrieval/

http://shape.cs.princeton.edu/benchmark/