S P Q R + Sicilia

Team Leader Luca Iocchi

Daniele Nardi

Andrea Cherubini

Pier Luca Marchetti

Vittorio Amos Ziparo

Simone Elviretti

Francesca Giannone

Stefano La Cesa

Francesco Macrì

Francesco Palamara

Maria Sciannelli

Sicilia

Team Leader Rosario Sorbello

Team Leader Antonio Chella

Salvatore Maria Anzalone

Giuseppe Balistreri

Rosamaria Elisa Barone

Dario Cacca

Alessandro Cimino

Francesco Cinquegrani

Francesco Di Paola

Ivan Di Paola

Laura Mancuso

Luca Maria Benedetto Martorana

Sergio Orlando

Marco Palermo

Giovanni Reina

Carmelo Scozzola

2005 Report

This paper presents the main development efforts of the team in 2005. In the following sections, before addressing the specific issues that have been developed during this year, we will briefly describe the features of the software architecture. Moreover, specific issues regarding the challenges will be reported in the last section.

Software Architecture

The main focus of our research group is the realization of a team of cognitive soccer robots. Past experiences at RoboCup has shown the need of an effective software framework for integrating in a modular way the different components that realize the functionalities of the robots.

However, general robot development frameworks are not easy to be ported on the Sony AIBOs, that have an operating system with different concepts with respect to other systems (e.g. Linux) used on other platforms. Moreover, software architectures for AIBO robots that have the required characteristics have been developed and successfully experimented: German Team Architecture and the CMU's Tekkotsu.

Our choice for development of 2005 team has been to adopt the German Team Architecture [START_REF] Röfer | German team robocup[END_REF]. This choice has been motivated not only by considering that it has been successfully used by several teams, but also by the fact that its high modularity allows for developing modules that can be shared with RoboCup Four-Legged community in a more effective way.

Our work in the development of 2005 team has been divided in two parts: 1) porting of some of our previously developed modules into the GT architecture; 2) realizing and experimenting new solutions for some other functionalities. More specifically, we adapted the modules developed in the past regarding Deliberation and Coordination, for which we have realized a porting in the new architecture, and realized and experimented new solutions for other modules, in particular for localization and perception.

The overall goal of our development was thus to integrate our previous achievements and current research in a new robust and effective software architecture.

In the rest of this report we will describe the main components that we developped. From a functional point of view, there are five main functional modules: Perception, Localization, Deliberation, Control, and Coordination. In the next sections we address these components, by describing the solutions we developped.

Perception

Image processing is implemented by both using standard techniques for color segmentation, blob formation, and object recognition and developing new modules that are described in the rest of this section.

Dynamic color segmentation

In order to improve robustness of color segmentation and to avoid long and tedious calibration processes, we have developed a dynamic color segmentation method that is able to provide a non-parametric color segmentation, that thus does not require any kind of calibration. A detailed description of the algorithm can be found in [START_REF] Iocchi | Dynamic color segmentation for the robocup environment[END_REF]. Figure 1 shows an example of segmentation. From the original image, we compute the color distribution in two mono-dimensional spaces: the Y component of the color space YUV and the H component of the color space HSV. We process each color distribution by applying a clustering algorithm that aims at grouping color components. Middle part of Figure 1 shows an example of such clustering for the H component: the X axis represents H values, the Y axis the number of pixels with that value of H, the color of the bar represents the main color that has been associated to each value of H. Since this process is executed on-line the method is very robust in two different situations: 1) variable lights; 2) unknown lighting conditions. Although an extensive evaluation of the method has not been performed yet, we have experimented that is significantly robust on different fields with typical but different RoboCup illumination (i.e. our lab, San Francisco RoboGames, German Open, RoboCup 2005 at Osaka).

The computational resources of the AIBO robots do not allow for a real-time implementation of the described method, i.e. to apply the method at each frame. Nonetheless, it is possible to use the method by computing the color distribution on half-resolution images and by computing a color table every about 15 frames, and then using it for the remaining frames. In this way we obtain an average frame rate of 15 fps, that is suitable for robot play.

Finally, it is important to highlight that a manual well defined color table provides better results with respect to our method. However, we experienced that segmentation obtained by our method is sufficient for object recognition, thus identifying the same elements than a manual color table does.

During RoboCup 2005, we have tested the method not only during the variable lighting chanllenge, but also in some games (test matches). We check and set parameters the first day, mainly because some colors (carpet and pink colors on markers) were different with respect to the ones in our lab, and never needed to change them during the competition.

Localization

Localization on the RoboCup 2005 field is significantly more challenging than in the previous editions. For the last edition of RoboCup, we have devoloped a method based on Monte Carlo localization, and used it during our match.

Monte Carlo Localization

Particle Filters such as SIR (Sample Importance Resampling) have been shown to be robust and efficient methods for estimating the state of a dynamic system [START_REF] Gordon | A novell approach to nonlinear nongaussian bayesian estimation[END_REF]. Our approach follows the widely used Monte Carlo Localization method [START_REF] Fox | Monte carlo localization: Efficient position estimation for mobile robots[END_REF], which is supervised by a sensor resetting mechanism such as [START_REF] Lenser | Sensor resetting localization for poorly modelled mobile robots[END_REF].

The algorithm devoloped runs in two stage, as usual. In the predict stage of the filter the samples are drawn from the robot motion model. We use the last set of particles and update it using the motion model as proposal distribution.

In the second stage we use the observation to compute the likelihood of samples. In our implementation (see Figure 2) the only eteroceptive sensor used is the built in camera of the robot, so we consider the following features: lines of the field, landmarks, goals.

For all of them we developed an observation model, and we delegate it the evaluation of likelihood. For markers, we consider the angle between it and robot, and the estimated distance from robot. The calculate likelihood can be expressed by:

likelihood marker = exp(-( δ 2 angular σ angular ))exp( δ 2 linear σ linear measuredDistance ) (1)
where δ angular is the difference between calculated and measured angle, δ linear is the linear difference and σ angular and σ linear are the respective covariance.

The observation model of the goals use the post as marker and don't use the distance. Due to its shape, the posts of a goal can't be detected precisely, so the sigma for the model is more relaxed. The likelihood for single post is:

likelihood goal = exp(-( δ 2 σ )) ( 2
)
where δ is the difference between calculated and measured angle, and σ is the relative covariance. The lines are extracted in the camera image using the Hough transform. Subsequently, by using the camera transformation and the information provided by the robot joints, we compute the lines local projection. The likelihood of a particular pose depends on the expected set of observations that a robot should see in that particular pose and the percepted items. The likelihood for single line is:

likelihood line = exp(-( δ 2 θ σ theta + δ 2 ρ σ ρ )) (3)
where δ θ and δ ρ are the difference on parameters between the observed line and the one from the table. The final likelihood is:

likelihood = likelihood marker likelihood goal likelihood line ( 4
)
The method is robust and extensible with respect to the kind of observations considered by the likelihood function. Clearly, its robustness grows with the number of observable items.

Sensor Resetting

The particle filtering technique has one major drawback: the so called kidnapping problem. When a robot is penalized by the referee, or collides with another robot, the particles evolve inconsistently respect the real pose. A method to resolve this problem was first exposed in [START_REF] Lenser | Sensor resetting localization for poorly modelled mobile robots[END_REF].

In our implementation we consider the sensor resetting replacing a small amount of particles with low probability with new particles taken from the observation distribution. We calculate the new set of particles using up to three marker observations: with just one marker we calculate a donut-shape distribution, with two or more markers we use triangulation.

For all pose calculated we insert a random gaussian noise to give more chance to new pose to be the correct one.

Deliberation

The Deliberation Module aims at driving the decisions of the robot about the actions to be executed, by considering both the current state of the world and the information coming from the Coordination Module. At a higher level the Coordination Module decides which goals should be pursued, while a Plan Executor Module selects (from a library) an appropriate plan for execution. Plans represent the means of obtaining goals and are specified in terms of actions that contain commands to be delivered to the motion level for effective execution.

Plan representation and execution through Petri Nets

The behavior of the robot is represented by plans that require a high representation power in order to express the capabilities of the robots.

The structure of AIBO robots allows the execution of concurrent actions, since many mechanical parts of the robots can be controlled independently, e.g. the robots can move their legs and their head at the same time neglecting (from a control standpoint) what other parts are doing. On the other hand it must be taken into account (in a deliberative perspective) the fact that the activity each part is performing will contribute to world evolution by involving its own state transition. Thus, action synchronization is also required. More specifically, it is important to model the following features: 1) sensing actions implementing if-then-else or while constructs able to determine the behavior of the robot according to the evaluation of a specific property at run-time; 2) concurrency of actions (e.g. moving the head while going to a position); 3) interrupts (e.g. aborting a go-to-ball action if the robot can not see the ball); 4) action synchronization between two or more robots. In order to represent the above mentioned features, transition graphs are not adequate, since, for example, concurrency and interrupts can not easily be modeled. Therefore, we adopted a formalism, based on Petri Nets, which is enough expressive to describe plans with concurrent actions (see [START_REF] Vittorio | Representation and execution of plans based on petri nets[END_REF] for further details). Moreover, we developed a plan execution module that can cope with plans described with this formalism. The key idea is to introduce a new execution state between the start and end states of an action. The execution state is labeled with execution conditions, that must be valid during action execution. Transitions are allowed into and out of this state providing for the capabilities of simply defining action synchronization and recovery from failures. Action concurrency is simply implemented by allowing multiple edges to come out from the same state.

As a difference with other approaches based on extensions of transition graphs, such as XABSL [START_REF] Röfer | German team robocup[END_REF], we clearly distinguish action specification and implementation, obtaining a framework which permits easier debugging: first, the semantic is well defined and easily verifiable by automated verification programs; second, we have a high granularity of actions which are grouped by functional properties and physical resources used.

Plans can be generated by an off-line planner or edited by hand. In the latter case we use available open-source tools which can generate an appropriate standard XML format (PNML). If transitions and places are correctly labeled to meet the specification of the Petri Plan the PNML code can be parsed to produce executable representation on the robot (PET files).

Moreover, the tool Jarp1 has been extended in order to debug existing plans. During plan execution, the robot can produce a log containing the information regarding the deliberative process. This log can be parsed by our tool to view the evolution of the Petri Net Plans, allowing for easily identifying loops or wrong behaviors, and providing a quick and user friendly plan debugging interface.

Control

The control module is responsible for implementing all motion commands generated by the Deliberation module. This involves computing and managing lowlevel motor commands for the robot's 20 joints. This issue mainly concerns with walking control, static actions control (i.e. kicks and goalkeeper blocks) and head control.

The walking control issue has been thoroughly addressed by the RoboCup community in recent years, and little improvement can be done as long as optimal speed is concerned. However, we have seen the necessity of developing a different walking pose for the goalkeeper. In fact on the RoboCup 2005 field, where the goal width has increased by 200 mm, the goalkeeper is extremely important. Therefore, our approach is to use a set of parameters (a pose) for the goalkeeper walk which optimizes stability and makes ball-blocking easier, instead of aiming at maximum gait speed. For example, if the goalkeeper walks with the front legs in a wider and lower position than the other robots, it can protect a larger part of the goal with its body.

Since kicks and blocks are also an important element in RoboCup, we developed of new static actions. Our approach is to consider a small and effective set of kicks, addressing real game situations. These kicks are designed in order to optimize power and precision, but also to improve the safety of the robots.

Coordination

Coordination through dynamic role assignment

The Coordination Module is responsible for implementing a distributed coordination protocol for dynamic task assignment according to the current situation of the environment [START_REF] Iocchi | Distributed coordination in heterogeneous multi-robot systems[END_REF]. The approach relies on the definition of a set of roles, that are ordered with respect to importance in the domain, and a set of utility functions, one for each role, expressing the capability of a robot to play this role. The values of the utility functions are computed by all the robots in the team for all the roles and these data are exchanged broadcast through the wireless network. A coordination algorithm is then executed by each robot in order to determine robot-role assignment. This algorithm ensures that every role is assigned to one robot and that the robots assigned to the most important roles are those that are in the best situation (according to the values of the utility functions).

Challenges

Variable Lighting Challenge

The Variable Light challenge was performed by using the dynamic color segmentation method described in Section 3.1. As already mentioned the method not only is robust to variable light conditions, but also allows for being used without any knowledge of the environment (i.e. without any kind of calibration).

Fig. 1 .

 1 Fig. 1. Dynamic Color Segmentation

Fig. 2 .

 2 Fig. 2. Monte Carlo based Localization

http://jarp.sourceforge.net/


Franc ¸ois Ingelrest David Simplot-Ryl
email: david.simplot@lifl.fr

Maximizing the Probability of Delivery of Multipoint Relay Broadcast Protocol in Wireless Ad Hoc Networks with a Realistic Physical Layer

It is now commonly accepted that the unit disk graph used to model the physical layer in wireless networks does not reflect real radio transmissions, and that the lognormal shadowing model better suits to experimental simulations. Previous work on realistic scenarios focused on unicast, while broadcast requirements are fundamentally different and cannot be derived from unicast case. Therefore, broadcast protocols must be adapted in order to still be efficient under realistic assumptions. In this paper, we study the well-known multipoint relay protocol (MPR). In the latter, each node has to choose a set of neighbors to act as relays in order to cover the whole 2-hop neighborhood. We give experimental results showing that the original method provided to select the set of relays does not give good results with the realistic model. We also provide three new heuristics in replacement and their performances which demonstrate that they better suit to the considered model. The first one maximizes the probability of correct reception between the node and the considered relays multiplied by their coverage in the 2-hop neighborhood. The second one replaces the coverage by the average of the probabilities of correct reception between the considered neighbor and the 2hop neighbors it covers. Finally, the third heuristic keeps the same concept as the second one, but tries to maximize the coverage level of the 2-hop neighborhood: 2-hop neighbors are still being considered as uncovered while their coverage level is not higher than a given coverage threshold, many neighbors may thus be selected to cover the same 2-hop neighbors.

Introduction

Nowadays, wireless networking has become an indispensable technology. However, the most deployed technology, known as WiFi, is too restrictive, as users must stay near to fixed access points. Therefore, the latter must be sufficiently deployed and correctly configured to offer a good quality of service. Moreover, there exists some more unusual situations where an infrastructure may be unavailable (e.g., rescue areas). The future of this technology probably lies in wireless ad hoc networks, which are designed to be functional without any infrastructure. They are defined to be composed of a set of mobile or static hosts operating in a self-organized and decentralized manner, which communicate together thanks to radio interfaces. Hosts may be either terminals or routers, depending on the needs of the system, leading to a cooperative multi-hop routing.

Broadcasting is one of the most important communication task in those networks, as it is used for many purposes such as route discovery (e.g., OLSR [START_REF] Jacquet | Optimized link state routing protocol for ad hoc networks[END_REF]) or synchronization. In a straightforward solution to broadcasting, hosts blindly relay packets upon first reception to their neighborhood in order to fully cover the network. However, due to known physical phenomena, this leads to the broadcast storm problem [START_REF] Ni | The broadcast storm problem in a mobile ad hoc network[END_REF]. Moreover, this is a totally inefficient algorithm, because most of the retransmissions are not needed to ensure the global delivery of the packet, and a huge amount of energy is thus unnecessarily wasted. Many other algorithms have been proposed in replacement. Some of them are centralized (a global knowledge of the network is needed), while the others are localized (hosts only need to know their local neighborhood to take decisions). Obviously, the latter better fit to ad hoc networks and their decentralized architecture.

All the proposed broadcast schemes have always been studied under ideal scenario, where the unit disk graph is used to model communications between hosts. In this model, two hosts can communicate together if the distance between them is no more than a given communication radius, and packets are always received without any error. Recently, this model has been highly criticized as it does not correctly reflect the behavior of transmissions in a real environment [START_REF] Stojmenović | Design guidelines for routing protocols in ad hoc and sensor networks with a realistic physical layer[END_REF]. Indeed, signal strength fluctuations have a significant impact on performance, and thus cannot be ignored when designing communication protocols for ad hoc and sensor networks. Unfortunately, this has been the case until now for broadcast protocols.

In this paper, we consider the well-known multipoint relay protocol (MPR) [START_REF] Qayyum | Multipoint relaying for flooding broadcast messages in mobile wireless networks[END_REF], used for broadcasting in ad hoc networks, under a more realistic scenario where the probability of correct reception of a packet smoothly decreases with the distance between the emitter and the receiver(s). We thus replace the unit disk graph model by the lognormal shadowing model [START_REF] Quin | On-demand routing in MANETs: The impact of a realistic physical layer model[END_REF] to simulate a more realistic physical layer, and provide experimental results. As they demonstrate the need for a more suitable algorithm, we also propose several modifications to MPR in order to maximize the delivery ratio of the broadcast packet, while minimizing the number of needed retransmissions. By experimentation, we show that these new versions are much more efficient than the original one under the considered realistic scenario.

The remainder of this paper is organized as follows: we first provide the definitions needed by our models, while in Sec. 3 a detailed description of MPR is proposed. In Sec. 4, we provide an analysis of the behavior of the original algorithm used in MPR with the realistic physical layer. We then describe in Sec. 5 new algorithms that better fit the latter. We finally conclude in Sec. 6 and give some directions for future work.

Preliminaries

The common representation of a wireless network is a graph G = (V, E), where V is the set of vertices (the hosts, or nodes) and E ⊆ V 2 the set of edges which represents the available communications: there exists an ordered pair (u, v) ∈ E if the node v is able to physically receive packets sent by u (in a single-hop fashion). The neighborhood set N(u) of the node u is defined as {v : (u, v) ∈ E ∨ (v, u) ∈ E}. The density of the network is equal to the average number of nodes in a given communication area. Each node u is assigned a unique identifier (this can simply be, for instance, an IP or a MAC address).

We assume that nodes are aware of the existence of each neighboring node within a distance of 2 hops (we call this a 2-hop knowledge). In ad hoc networks, the neighborhood discovery is generally done thanks to small control (HELLO) messages which are regularly sent by each host. A 2-hop knowledge can easily be acquired thanks to two rounds of HELLO exchanges: nodes can indeed insert the identifiers of their neighbors in their own beacon messages.

In our mathematical model, the existence of a pair (u, v) ∈ E is determined by the considered physical layer model and depends on several conditions, the most obvious one being the distance between u and v. In the most commonly used model, known as the unit disk graph model, a bidirectional edge exists between two nodes if the distance between them is not greater than a given communication radius R (it is assumed that all nodes have the same communication radius). In this model, the set E is then simply defined by:

E = {(u, v) ∈ V 2 | u = v ∧ dist(u, v) ≤ R}, (1)
dist(u, v) being the Euclidean distance between nodes u and v. This model, while being well spread, cannot be considered as realistic. Indeed, it is assumed that packets are always received without any error, as long as the distance between the emitter and the receiver is smaller than the communication radius. This totally ignores random variations in the received signal strength, while it was demonstrated that their impact is really significant.

These fluctuations generate erroneous bits in the transmitted packets. If the error rate is sufficiently low, these bits can be repaired thanks to correction codes. However, if it is too high, then the packet must be dropped and a new emission must be done. This supposes the existence of an acknowledgement mechanism (ACK packets) that cannot be used in broadcasting tasks due to the really high number of emitters. Our work thus only relies upon the probability of correct reception, which is influenced by a lot of factors (e.g., power of emission, distance with the receiver(s), presence of obstacles). We suppose that all nodes have the same transmitting radius, so the power of emission does not have to be taken into account here.

To consider the signal fluctuations, we change G into a weighted graph where each edge (u, v) ∈ E holds the probability p(u, v) of correct reception between the two nodes u and v. To determine these probabilities, we chose to consider the lognormal shadowing model [START_REF] Stojmenović | Design guidelines for routing protocols in ad hoc and sensor networks with a realistic physical layer[END_REF] in our simulations. We used an approximated function P(x) described in [START_REF] Kuruvila | Hop count optimal position based packet routing algorithms for ad hoc wireless networks with a realistic physical layer[END_REF]: We assume that each node u is able to determine the probability p(u, v) of correct reception of a packet that would be sent to a neighbor v. The gain of this knowledge may be simply achieved thanks to beacon messages: based on the quantity of correctly received HELLO packets, v is able to determine an approximated value of p(u, v). Node v may then include this value in its own beacon messages.

P(x) =              1 - ( x R ) 2α 2 if 0 < x ≤ R, ( 2R-x R ) 2α 2 if R < x ≤ 2R, 0 otherwise, (2)
One of the major criticisms of the unit disk graph model is that it does not model the presence of obstacles between nodes. The lognormal shadowing model neither considers them, but we argue that it is sufficient enough for simulations. The most important factor is the weighting of edges by reception probabilities, the method used to distribute the latter is not important to compare protocols in general cases. A realistic model would be mandatory to simulate existing situations and to extract exact values. But in real cases, an obstacle would decrease the probability held by the corresponding edge and would thus be detected by nodes when counting HELLO messages (if such a method is used). This means that in those cases, the broadcast algorithm would use 'real' probabilities and its behavior would be adapted to the situation.

The two previous physical models introduce two different behaviors:

-In the unit disk graph model, one has to maximize the length of each hop so that a single emission is able to reach as many mobiles as possible. The quantity of needed emitters is thus greatly reduced. -In the lognormal shadowing model, maximizing the length of each hop leads to smaller probabilities of correct reception, but minimizing them leads to a lot of spent energy. Some papers have already been published about routing in a realistic environment. Amongst them, DeCouto et al. [START_REF] Decouto | A high-throughput path metric for multi-hop wireless routing[END_REF] and Draves et al. [START_REF] Draves | Routing in multi-radio, multi-hop wireless mesh networks[END_REF] investigate the question of routing metrics for unicast protocols in wireless networks with a realistic physical layer: the key insight in most of this work is that hop-count based shortest-path routing protocols result in transmissions over long links. While this reduces the hop-count of routes, it also decreases the received signal strength at the receiver of these links, leading to very high loss rates and low end-to-end throughput. These papers also propose other routing metrics which incorporate link-quality (e.g., in terms of error, congestion).

To the best of our knowledge, this paper is the first one to consider broadcasting over a realistic physical layer. Broadcast fundamentally differs from unicast, and leads to a different tradeoff between the length of each hop and the number of relays. Indeed, in a broadcast process, a node can rely on the redundancy introduced by other emitters. Further relays may thus be selected without decreasing the final delivery ratio. This is not possible in routing, as a given emitter is the only one able to transmit the packet to the next hop. The redundancy of broadcasting must be fully considered in order to improve the performance of the underlying protocol.

Related Work

As stated in Sec. 1, the easiest method for broadcasting a packet is to have all nodes forward it at least once to their neighborhood: this method is known as blind flooding. However, such a simple behavior has huge drawbacks: too many packets are lost due to collisions between neighboring nodes (this can lead to a partial coverage of the network) and far too much energy is consumed. Many other solutions have been proposed to replace it, and an extensive review of them can be found in [START_REF] Ingelrest | 17 -'Energy-Efficient Broadcasting in Wireless Mobile Ad Hoc Networks[END_REF]. Among all these solutions, we have chosen to focus on the multipoint relay protocol (MPR) described in [START_REF] Qayyum | Multipoint relaying for flooding broadcast messages in mobile wireless networks[END_REF] for several reasons:

-It is efficient using the unit disk graph model.

-It is used in the well-known standardized routing protocol OLSR [START_REF] Jacquet | Optimized link state routing protocol for ad hoc networks[END_REF].

-It can be used for other miscellaneous purposes (e.g., computing connected dominating sets [START_REF] Adjih | Computing connected dominated sets with multipoint relays[END_REF]).

In this algorithm, it is assumed that nodes have a 2-hop knowledge: they are aware of their neighbors (1-hop distance), and the neighbors of these neighbors (2-hop distance). Its principle is as follows. Each node u that has to relay the message must first elect some of its 1-hop neighbors to act themselves as relays in order to reach the 2-hop neighbors of u. The selection is then forwarded within the packet and receivers can thus determine if they have been selected or not: each node that receives the message for the first time checks if it is designated as a relay node by the sender, and if it is the case, the message is forwarded after the selection of a new relaying set of neighbors. A variant exists where nodes proactively select their relays before having to broadcast a packet, and selection is sent within HELLO messages.

Obviously, the tricky part of this protocol lies in the selection of the set of relays MPR(u) within the 1-hop neighbors of a node u: the smaller this set is, the smaller the number of retransmissions is and the more efficient the broadcast is. Unfortunately, finding such a set so that it is the smallest possible one is a NP-complete problem, so a greedy heuristic is proposed by Qayyum et al., which can be found in [START_REF] Lovasz | On the ratio of optimal integral and fractional covers[END_REF]. Considering a node u, it can be described as follows:

1. Place all 2-hop neighbors (considering only outgoing links) in a set MPR ′ (u) of uncovered 2-hop neighbors. 2. While there exists a 1-hop neighbor v which is the only common neighbor of u and some nodes in MPR ′ (u): add v to MPR(u), remove its neighbors from MPR ′ (u). 3. While the set MPR ′ (u) is not empty, repeatedly choose the 1-hop neighbor v not present in MPR(u) that covers the greatest number of nodes in MPR ′ (u). Each time a new node is added to MPR(u), remove its neighbors from MPR ′ (u). In case of tie, choose the node with the highest degree.

An example of this heuristic is given in Fig. 2, starting with MPR(u) = / 0. The node v 1 is the only one able to reach w 1 , so it is added to MPR(u) and nodes w 1 and w 2 are removed from MPR ′ (u). No other mandatory 1-hop neighbor of u exists, so other relays are selected according to the number of nodes in MPR ′ (u) they cover. Nodes v 2 and v 4 cover only one node in MPR ′ (u) , while node v 3 covers at the same time w 3 and w 4 , so v 3 is chosen and added to MPR(u). The set MPR ′ (u) being empty, no other nodes are selected. We finally have MPR(u) = {v 1 , v 3 }.

Being the broadcast protocol used in OLSR, MPR has been the subject of miscellaneous studies since its publication. For example in [START_REF] Busson | An analysis of the multi-point relays selection in OLSR[END_REF], authors analyze how relays are selected and conclude that almost 75% of them are selected in the first step of the greedy heuristic, so that improving the second step is not really useful. This conclusion seems correct, as long as the unit disk graph model is used.

Original Greedy Heuristic

Graphs generation

In this section, we provide results about the performance of MPR over our considered realistic physical layer, the lognormal shadowing model. We chose not to use a general purpose simulator in order to focus on the area of our study: we thus implemented algorithms and models in our own simulator, so that we had to decide how to generate 'realistic' graphs considering the realistic model.

We chose to consider the method cited in Sec. 2, which is based on HELLO messages. Neighborhood information is stored in a table which is regularly cleaned in order to remove too old entries. An entry is too old when the corresponding host has not signaled itself since a given amount of time, that we denote by x. Beacon messages are regularly sent by each host to signal itself. Let us denote by y the time between two HELLO messages (we have x > y). A node u sees a neighbor v if it has received at least one HELLO message during the last y seconds. The probability p n (u, v) for this event to occur is equal to:

p n (u, v) = 1 -p(u, v) x y . (3)
For each directional edge, a random number is thus drawn to determine if it exists. This way, when a node u is aware of the existence of a neighbor v, it can decide to send messages to the latter. Of course, u cannot be ensured that its messages will reach v. We can easily conclude that long edges have a high probability to be unidirectional while short edges have a high probability to be bidirectional.

All the results were obtained with the following parameters. The network is static and always composed of 500 nodes randomly distributed in a uniform manner over a square area whose size is computed in order to obtain a given average density. Edges are created using the method previously described, and for each measure, we took the average value obtained after 500 iterations. We fixed the communication radius to be equal to 75 in both physical models. An ideal MAC layer is considered to isolate the intrinsic properties of the selected relays: collisions of packets could skew both results and analyses.

Experimental results

We provide in Fig. 3(a) the delivery ratio of MPR using the two considered physical layers. When using the unit disk graph model, a total coverage of the network is achieved as MPR is a deterministic algorithm. However, this is no more the case with the lognormal shadowing model due to the multiple errors of transmission: the delivery ratio is under 70% for each considered density, and is as low as 55% for a density d = 15.

This poor performance can be explained by the fact that, as highlighted by Busson et al. in [START_REF] Busson | An analysis of the multi-point relays selection in OLSR[END_REF], the chosen relays are located at the limit of the communication range, where the probability of correct reception is low. This is confirmed in our experiments, as illustrated by Fig. 4: the average distance between a node and its multipoint relays is almost equal to 68, while the maximal communication range is 75. Moreover, [START_REF] Busson | An analysis of the multi-point relays selection in OLSR[END_REF] also states that 75% of the relays are chosen during the first step: this means that, when a relay does not correctly receive the message, there is a risk of 75% that this relay was the only one able to reach an isolated node, which will thus not receive the message, potentially leading to a partition of the network. We also provide in Fig. 3(b) the percentage of nodes which correctly received and then relayed the message. It is interesting to note that this percentage is different with the two models. Indeed, as only nodes which received the message are taken into account, one would have expected to observe the same values in both cases. This means that the needed number of relaying nodes does not linearly vary with the number of covered nodes: obviously, only a few relays are needed to cover a high number of different nodes, but a larger number is needed to cover the last few remaining ones.

New Heuristics for MPR

As illustrated in the previous section, the original greedy heuristic used by Quayyum et al. in [START_REF] Qayyum | Multipoint relaying for flooding broadcast messages in mobile wireless networks[END_REF] is not suitable for a realistic physical layer. An average delivery of 70% is indeed not sufficient for most of applications, and an alternative solution must thus be used.

In this section, we propose miscellaneous replacement heuristics in order to improve the performance of MPR. They aim at maximizing the average coverage, while minimizing the number of needed relays (and thus the energy consumption). In all our proposals, the first step of the original heuristic which allows isolated 2-hop neighbors to be covered is kept (it is mandatory), only the second step is replaced.

We keep notations introduced in Sec. 3. Thus, considering a node u, the set MPR(u) contains the multipoint relays chosen by u, while the set MPR ′ (u) contains 2-hop neighbors of u not yet covered.

First proposal: Straightforward approach

As previously explained, the low delivery ratio of MPR is caused by the too high distance between a node and its relays. The latter having little chance to correctly receive u v v¡ w w ¢ w¡ Fig. 5. A case where the node u has to select its multipoint relays between its neighbors

v 1 and v 2 (MPR(u) = / 0, MPR ′ (u) = {w 1 , w 2 , w 3 }.
the broadcast packet, they also have little chance to be able to relay this packet and thus to cover the 2-hop neighbors of the emitter. A first and straightforward idea could be, when choosing a relay, to balance the coverage it offers and its probability to correctly receive the packet. Thus, at each step considering a node u, a score can be computed for each potential relay v. The node with the highest score is selected and placed in MPR(u). We denote by c u (v) the additional coverage offered by v to u:

c u (v) = |MPR ′ (u) ∩ N(v)|. (4)
The score obtained by v at a given iteration for a node u, denoted by s u (v), is thus defined by:

s u (v) = c u (v) × p(u, v).
(

In simple terms, the additional coverage offered by v is weighted by its probability to correctly receive the broadcast packet. In Fig. 5, the score s u (v 1 ) of v 1 is equal to 3 × p(u, v 1 ).

Second proposal: Clever approach

The previous heuristic, while being more suitable for a realistic environment than the original one, still has an obvious flaw: it still takes into account additional coverage in a too simple way. One can thus easily imagine a situation where a very distant 1-hop neighbor would offer an additional coverage such that the latter would compensate a low probability of correct reception. In this case, this neighbor would be selected as relay while its probability to correctly receive the packet, and thus to be able to relay it, would be very low. One can also imagine a situation where the distance between the relay and the 2-hop neighbors it covers would be very high, such that the re-emission of this relay would have little chance to reach these 2-hop neighbors.

We propose to extend the concept used in the first proposal, by taking into account the probabilities of correct reception between the potential relay and the 2-hop neigh- bors it covers. We thus replace the additional coverage offered by a relay by the average probability of correct reception by 2-hop neighbors. We thus obtain:

s u (v) = p(u, v) × i=|c u (v)| ∑ i=1 ( p(v, w i ) / |c u (v)| ). (6)
This way, multipoint relays offering a low coverage in terms of probabilities have little chance to be selected. In Fig. 5, the score s u (v 1 ) of v 1 is now equal to p(u, v1) × ((p(v 1 , w 1 ) + p(v 1 , w 2 ) + p(v 1 , w 3 ))/3).

Third proposal: Robustness approach

In the previous proposals, as soon as a 2-hop neighbor has a non-null probability to be covered, it is removed from MPR ′ (u). This removal is done even with a very low probability, which in this case may be meaningless. It can be more interesting to consider a 2-hop neighbor as covered when its probability to correctly receive the broadcast packet is over a given threshold, in order to increase the delivery ratio.

We thus propose to keep the score computation used in the previous heuristic, while modifying how 2-hop neighbors are removed from MPR ′ (u). For such a 2-hop neighbor w of u, its removal from MPR ′ (u) is done only if its coverage level t u (w) is over a given threshold. The value of t u (w) is given by:

t u (w) = 1 - i=|MPR(u)| ∏ i=1 p(v i , w), (7)
p(v i , w) being equal to 1p(v i , w). In simpler terms, the coverage level of a 2-hop neighbor is equal to its probability to correctly receive the packet from at least one of the chosen relays. Still considering Fig. 5, if the nodes v 1 and v 2 are selected as relays, then the coverage level t u (w 3 ) of w 3 is equal to 1-(p(v 1 , w 3 )×p(v 2 , w 3 )). Several relays can thus now be selected to cover the same set of 2-hop neighbors, in order to increase the delivery ratio.

Performance

We provide in Fig. 6 the performance of the new heuristics presented in this section, considering the lognormal shadowing model. We use the same parameters as in Sec. 4.

Not surprisingly, we observe in Fig. 6(a) that the new heuristics lead to a far better delivery ratio than the original algorithm. This improvement is of course due to the use of the probabilities of correct reception given by the physical model. As expected, the second heuristic offers a higher percentage of covered nodes simply because it prevents too far neighbors to be selected as relays. Considering the density d = 30, the original heuristic only covers 67% of nodes, against 81%, 85% and 98% for our three proposals. The delivery ratio has thus been greatly improved, as aimed by our heuristics.

As illustrated by Fig. 6(b), the third heuristic, used with a threshold equal to 0.5, requires the participation of 28% of the receiving nodes for the density d = 30 to provide a delivery ratio of 98%. This may seem a high value compared to other curves, but considering the results given in Fig. 3 with the unit disk graph model, one can observe that values are almost the same for the original heuristic. This means that the number of chosen multipoint relays for a given node is approximately the same, but their choice is of better quality.

We finally provide in Fig. 7 the performance of the third heuristic for different values of the threshold parameter, considering a density d = 30. As expected, the delivery ratio is proportional to the value of the threshold while the number of relays is inversely proportional to it. Choosing a threshold equal to 1 is almost useless as a total coverage can nearly be achieved with a value between 0.4 and 0.5 with far less relaying nodes. Using a threshold of 0 does not lead to a null delivery ratio, because the first step is still applied to cover isolated nodes.

From the variety of results presented, we can observe that a realistic physical layer leads to miscellaneous problems while broadcasting. The MPR protocol is a good example: while being very efficient with the unit disk graph, its delivery ratio is not sufficient for most applications with a realistic model. While this study focused on MPR, we believe that other main broadcasting methods, such as dominating sets, will exhibit the same flaws. However, some small modifications, which takes into account probabilities of correct reception, may correct these flaws. Thus, the new heuristics we presented for MPR keep the principle of the protocol, only the selection process of multipoint relays is modified. The latter, while being approximately as many as in the original heuristic, are generally better chosen and provide a higher delivery ratio.

More generally, a huge amount of work is left to be done about this subject. As previously stated, other well-known algorithms will probably need to be modified in order to provide correct performance. Other mechanisms, such as the neighbor elimination scheme [START_REF] Stojmenović | Broadcasting algorithms in wireless networks[END_REF], may be of prime importance in the quest for the optimal tradeoff between robustness and efficiency. Other aspects of communications, such as neighborhood discovery protocols must also be studied and probably adapted to realistic environments.

Fig. 1 .

 1 Fig. 1. Unit disk graph and lognormal shadowing models (R = 100, α = 4).

Fig. 2 .

 2 Fig. 2. Applying MPR at node u: MPR(u) = {v 1 , v 3 }.

Fig. 3 .

 3 Fig. 3. Performance of MPR with the two considered physical models.

Fig. 4 .

 4 Fig. 4. Average distance between a node and its relays.

Fig. 6 .

 6 Fig.6. Performance of the different heuristics using the lognormal shadowing model.

Fig. 7 .

 7 Fig. 7. Performance of the third heuristic for varying thresholds and a density d = 30.

⋆ This work was partially supported by a grant from CPER Nord-Pas-de-Calais/FEDER TAC COM'DOM, INRIA research action IRAMUS and CNRS national platform RECAP.


Arnaud Dessein

William A P Smith

Richard C Wilson

Edwin R Hancock

Example-Based Modeling of Facial Texture from Deficient Data

We present an approach to modeling ear-to-ear, highquality texture from one or more partial views of a face with possibly poor resolution and noise. Our approach is example-based in that we reconstruct texture with patches from a database composed of previously seen faces. A 3D morphable model is used to establish shape correspondence between the observed data across views and training faces. The database is built on the mesh surface by segmenting it into uniform overlapping patches. Texture patches are selected by belief propagation so as to be consistent with neighbors and with observations in an appropriate image formation model. We also develop a variant that is insensitive to light and camera parameters, and incorporate soft symmetry constraints. We obtain textures of higher quality for degraded views as small as 10 pixels wide, than a standard model fitted to non-degraded data. We further show applications to super-resolution where we substantially improve quality compared to a state-of-the-art algorithm, and to texture completion where we fill in missing regions and remove facial clutter in a photorealistic manner.

Introduction

The problem of modeling complete and high-quality facial texture from input data that is "deficient" (i.e., lowresolution, noisy and/or incomplete) has many potential applications. These include facial super-resolution, face texture completion, pre-processing for manual or automatic face recognition, creation of fully textured avatars from a single low-quality view, estimation of high-resolution frontal views from low-resolution CCTV images of nonfrontal faces, or prediction of clean-shaven appearance.

Besides typical noise sources, deficient data arise in a number of ways. The complete ear-to-ear texture of a face is never fully visible in a single image. This is particularly problematic for images in a non-frontal pose where as much as half of the texture may be missing. A similar problem occurs when parts of a face are occluded by scene clutter, other people, glasses or facial hair. When a face image is captured by a cheap sensor, at large distance, or with heavy compression, then the resolution may be insufficient for further processing. These deficiencies make many face processing problems more difficult when dealing with real-world data.

The predominant approach to face modeling problems has been statistical [START_REF] Blanz | A morphable model for the synthesis of 3D faces[END_REF]8,[START_REF] Cootes | View-based active appearance models[END_REF]20]. Namely, learning the common modes of variation in face appearance from training data. Such models can be used to constrain many face processing problems. However, in the context of deficient data, statistical models suffer from a number of drawbacks (see Fig. 1). The state-of-the-art in face capture [4,[START_REF] Ma | Rapid acquisition of specular and diffuse normal maps from polarized spherical gradient illumination[END_REF] allows measurement of very high-resolution texture and shape information that can be used for photorealistic rendering (left). On the other hand, face modeling has failed to keep pace with the quality of data that can be captured from real faces (middle). The most critical weakness of existing statistical face models is their inability to accurately approximate unseen faces. This leads to models that fail to capture distinguishing, fine-scale details of a face. This situation is exacerbated further when such models are fitted to 2D images. Here, not only local details but global properties of identity such as gender and ethnicity are lost, even when the input data is of relatively high quality (right).

We address the issues caused by deficient data with a novel example-based approach to face texture modeling. We fit a 3D morphable model for shape correspondence between training faces and input images. The 3D model is segmented into uniform overlapping patches via farthestpoint sampling. We build a database for texture on the segmented model, and estimate the optimal patch combination by loopy belief propagation so that the reconstructed textures best explain the data whilst ensuring local consistency.

To assemble these known ingredients in a unified framework, we also introduce several technical contributions. First, farthest-point sampling is enhanced with an original patch growing scheme based on geodesic projections, so as to create uniform patches that overlap. Second, loopy belief propagation is formulated on the 3D mesh rather than 2D images via an appropriate model of image formation, where we explicitly simulate how vertices project to the observed pixel grid. Third, we propose a texture normalization step to make our methods insensitive to camera and lighting parameters, show the coherence of this step with our image formation model, and derive new updates of normalized patch compatibilities for tractability. Fourth, we incorporate soft symmetry constraints on the model, which requires revisiting both segmentation and loopy belief propagation.

In addition, our methods have a number of appealing properties. First, the pipeline is fully intrinsic to the 3D model, so that we avoid undesired distortions due to extrinsic processing such as 2D flattening or 3D Euclidean operations. Second, the patch database is independent of the degradation factor, just needs to be trained once, and can be updated incrementally with any new data. Third, we explicitly account for issues of occlusions and of pose changes between multiple views. Fourth, we can handle varying appearance caused by changes in camera or illumination between training and testing, or even between input images.

We assume that the morphable model parameters for each input image are provided by a separate algorithm. It is not the topic of this paper to estimate these parameters, and there are many algorithms for fitting a 3D morphable model to 2D images [START_REF] Aldrian | Inverse rendering of faces with a 3D morphable model[END_REF]2,[START_REF] Blanz | A statistical method for robust 3D surface reconstruction from sparse data[END_REF][START_REF] Blanz | A morphable model for the synthesis of 3D faces[END_REF]20,[START_REF] Romdhani | Estimating 3D shape and texture using pixel intensity, edges, specular highlights, texture constraints and a prior[END_REF]28], including low-resolution input [START_REF] Mortazavian | 3D morphable model fitting for low-resolution facial images[END_REF]. We here use the well-known model [20] fitted to ground-truth data. This gives an oracle upper bound on texture reconstruction performance, since it is likely that shape will be less accurate when estimated on degraded images. We thus also evaluate the effect of perturbations in the parameters to simulate fitting errors or spatial noise, by considering the extreme case of the mean shape only as a rough estimate. This way, we obtain an oracle lower bound on performance since shape is then the worst possible. Pose is also not perfect because we do not reestimate it based on the mean shape, meaning only the gross positioning and orientation of the face are correct. This is relevant since the gross pose can be estimated relatively well given a couple of manually or automatically detected keypoints (e.g., eye centers, mouth corners, nose tip).

Related Work

Face modeling Statistical face models such as active appearance models [8, 9] and 3D morphable models [START_REF] Blanz | A morphable model for the synthesis of 3D faces[END_REF]20] assume that there is a dense correspondence between any pair of faces, which transforms faces into a vector space where any convex combination yields a valid face. Specifically, a 3D morphable model is a deformable mesh M(α) = (K, S(α)). The connectivity is given by the simplicial complex K, a set whose elements can be vertices {i}, edges {i, j} or faces {i, j, k}, with indices i, j, k ∈ {1, . . . , N }. The shape S(α) of the N vertices depends on a vector α ∈ R S which contains the parameters of a low-dimensional, linear model learned from training data via PCA:

S(α) = S + S m=1 α m S m , (1)
where S ∈ R 3×N is the mean shape, and S m ∈ R 3×N are S shape modes. Texture is also commonly described similarly, and since PCA implicitly acts as a low-pass filter, these models fail to capture high-frequency detail. Mohammed et al. [START_REF] Mohammed | Visio-lization: Generating novel facial images[END_REF] tackle this problem for 2D morphable models in the context of 2D face synthesis. Instead of fitting to image data, they randomly generate parameters of a statistical face model before adding high-frequency detail by importing real patches with local consistency and that agree with the global face image. Patches are selected in raster scan order using a greedy algorithm with partiallystochastic decisions to improve variation in the synthesis.

Our model can be viewed as a 3D extension of [START_REF] Mohammed | Visio-lization: Generating novel facial images[END_REF], with some important differences. First, our model and patch database are built on a deformable 3D mesh rather than in 2D image space. Second, we require a model of image formation to relate appearance. Third, we use belief propagation for a better approximation to the optimal choice of patches. Fourth, we account for color transformations between the model and images, enabling a wider range of images to be analyzed. Fifth, we do not use a global statistical texture model but condition results on observed data only.

Super-resolution Facial texture modeling from images of poor resolution shares similarities with super-resolution problems [START_REF] Borman | Super-resolution from image sequences -a review[END_REF][START_REF] Park | Super-resolution image reconstruction: a technical overview[END_REF]22,[START_REF] Tipping | Bayesian image superresolution[END_REF]. However, unlike classical 2D super-resolution, multiple images of a face are unlikely to differ only by sub-pixel translations and rotations in the image plane. Hence, the majority of face-specific approaches to super-resolution work with a single image and are more accurately described as face hallucination (aka recogstruction as a neologism for reconstruction by recognition).

A pioneering work in this context was done by Baker and Kanade [START_REF] Baker | Limits on super-resolution and how to break them[END_REF]. They incorporated a database for a class of objects (text or faces) into previous probabilistic frameworks for super-resolution. Freeman et al. [START_REF] Freeman | Example-based super-resolution[END_REF] also used a database (generic though can be restricted to faces) of corresponding high-and low-resolution texture patches. They form a Markov random field over the pixel lattice, and apply belief propagation to select high-resolution patches whose low frequencies match those observed, while ensuring local consistency via neighboring patch compatibilities. They also perform color normalization in local contrast, though this lacks of a physical interpretation compared to our texture normalization. Liu et al. [START_REF] Liu | Neighbor combination and transformation for hallucinating faces[END_REF] developed a face-specific version of this by using a non-stationary patch database and a global statistical model trained on face images. Mortazavian et al. [START_REF] Mortazavian | A 3-D assisted generative model for facial texture super-resolution[END_REF] further extended the example-based approach by exploiting a 3D morphable face model. However, the 3D model is used solely to establish correspondence between a single input image and the training data. Superresolution is then performed in a flattened texture space, at the cost of distortions inherent to the parameterization, with the frequency-domain approach of previous 2D works. Hence, they have no explicit model of image formation.

We emphasize that our face texture modeling approach is more general than super-resolution. Indeed, we reconstruct a full texture on a 3D model that can be rendered in any pose, whereas classical super-resolution methods reconstruct a partial texture on a 2D image in the exact same pose as observed. When applied to super-resolution problems, our approach is also the first to handle multiple views with complex 3D pose changes involving possibly large outof-plane rotations and translations as well as occlusions.

Moreover, existing example-based methods to superresolution suffer from a number of limitations. First, they consider a fixed degradation factor (often a power of 2), either because they build a specific dictionary for a given degradation factor, or because the frequency decomposition makes assumptions about the frequency range that has been lost and must be reconstructed. Second, there is no obvious way to integrate information from multiple images, particularly when the 3D pose changes. Third, they assume that the model and image can be directly compared without accounting for appearance variation due to camera or lighting. Our proposed model overcomes each of these weaknesses. Lastly, we handle faces as small as 10 pixels wide whereas typical super-resolution algorithms require over 30 pixels.

Texture completion Statistical models can be used to explain missing data by fitting a complete model to partial data. In 2D, view-based active appearance models [START_REF] Cootes | View-based active appearance models[END_REF] can predict frontal appearance from a profile view. Similarly, a multilinear model with a mode for pose variation, such as [26], can also predict any viewpoint given a single view.

Lüthi et al.

[13] proposed a 3D extension, with a prob-abilistic approach for fitting to partial data which provides the subspace of all solutions consistent with the observed data. Like 2D methods, it suffers however from the fundamental limitation of statistical approaches. They can only describe a face in terms of its most common aspects of appearance. This leads to a loss of detail and an inability to meaningfully reconstruct deficient data.

Overlapping Mesh Segmentation

In this section, we discuss the segmentation of the mean face shape into uniform overlapping patches. We first sample the mesh uniformly to create patches via the underlying tessellation. We then grow the patches so that they overlap.

Uniform Sampling

We process sampling with a greedy farthest-point strategy similar to [START_REF] Peyré | Geodesic remeshing using front propagation[END_REF]. We denote by I l = {i 1 , . . . , i l } ⊂ K the set of first l selected samples. We also define D l as the geodesic distance map to I l . The next sample i l+1 is selected as the vertex which is the farthest from all samples:

i l+1 = arg max i∈K D l (i) .
(

For the next iteration, D l+1 is updated as the minimum between D l and the distance map to the new sample:

D l+1 (i) = min D l (i), D(i, i l+1 ) . (3)
We continue the process until the desired number M of vertices are sampled. In the end, patches P 1 , . . . , P M are obtained via the geodesic Voronoi tessellation:

P m = i ∈ K : D(i, i m ) = min i ∈I M D(i, i ) . (4)

Patch Growing

We denote by E the set of pairs (m, n) such that patches P m and P n share an edge {i, j} ∈ K. To grow patch P m , we consider separately each of its neighbors P n with (m, n) ∈ E, and define thresholds d mn as follows:

d mn = ρ × D(i m , i n ) , (5)
where ρ ≥ 0 is an overlap ratio set by the user. The overlap O mn of P m onto P n is then constructed by projections:

O mn = i ∈ P n : min j∈Pm D(i, j) ≤ d mn . (6)
Eventually, a grown patch Q m is obtained by concatenation:

Q m = P m ∪ n|(m,n)∈E O mn . (7)
Figure 2. Segmentation results. The mean face (left) is segmented by first sampling the mesh uniformly to create patches (middle), and then growing the patches so that they overlap (right).

Segmentation Results

We segmented the mean face of the morphable model into M = 200 patches, so that they are about the size of the eyes. We visualize the obtained patches by assigning different colors and averaging them in overlaps (see Fig. 2). Geodesic distances were computed by fast marching as in [START_REF] Peyré | Geodesic remeshing using front propagation[END_REF]. Sampling was seeded with eye centers to avoid stochastic indeterminacy due to random initialization. Patches were grown using a small overlap ratio ρ = 0.2 to keep results visually interpretable. In subsequent experiments, this ratio was increased to ρ = 0.5 for a better merging of solutions, which corresponds to a natural overlap of about half the patch size. The whole process took a couple of minutes on a standard computer, but needs only to be computed once beforehand and can then be stored.

Overall, the results show that the segmentation produces roughly uniform patches over the face, and hence transfers the notion of a regular overlapping patch structure from 2D images to 3D meshes. We also notice that the seeding allows single patches to span the eyes, which might be desirable to avoid that different parts of the iris are assigned different colors during texture reconstruction.

Texture Patch Selection

In this section, we present our methods to select texture patches from the training database. We define observation error functions and patch overlap compatibilities on the mesh via an image formation model. The optimal patch combination is then estimated by loopy belief propagation.

Image Formation Model

It is not straightforward to measure plausibility between an observed image and training textures that have supposedly produced this image. Doing it in the image domain does not seem relevant for two main reasons. Indeed, this requires rendering all training faces on the observed image grid, which gets demanding as the database size increases. Moreover, errors computed in the image domain are not directly related and scaled to compatibilities of training texture patches pasted on the mesh for reconstruction.

We thus compute errors directly on the mesh after texture sampling. When the observed images are not degraded, we simply sample them on the mesh by back-projection of color and bilinear interpolation in the pixel grid. Textures at visibility boundaries are filled in by nearest-neighbor interpolation instead, and missing data are left untextured. However, since back-projection requires a sufficiently fine grid, this model reveals insufficient in case of poor resolution.

To overcome this, we simulate the formation of a lowresolution image with pixel colors c r as produced by a mesh with high-resolution textures t + i . We assume that the mesh vertices are uniformly and finely sampled compared to the low-resolution pixel size. The first assumption is reasonable since the fitted shape involves local deformations of the mean shape which is almost uniformly sampled. The second one holds too since we consider degraded images of 10 to 40 pixels wide which is negligible compared to more than 50,000 vertices in the model.

Hence, the color c r of a given pixel r can be approximated by averaging the contributions of the visible vertices that project onto that pixel:

c r = 1 |V r | i∈Vr t + i , (8)
where V r is the set of visible vertices that project onto pixel r. This partitions the visible vertices via an equivalence relation where i and j belong to the same class if they are in the same set V r . We denote the equivalence class of a visible vertex i as V i , and by r(i) the index of the pixel onto which i is projected. We can thus compute errors on the mesh by sampling a low-resolution observed texture via nearestneighbor interpolation t - i = c r(i) , while resampling the high-resolution training textures t + ip into low-resolution textures t - ip by local averaging in projected pixels:

t - ip = 1 V i j∈Vi t + jp . (9)
Finally, to prevent from sampling incorrect textures because of background corruption along the projected outline, we exclude border pixels from sampling so that vertices falling in such pixels are considered as occluded. This can be done together with vertex visibility testing and texture sampling, by using a depth-buffer on a refined pixel grid. Typically, this grid is obtained by simply rescaling the coarse grid by the super-resolution factor, which allows the buffer to be reused when rendering the reconstructed image.

Observation Error Function

We model the likelihood of training patches given the low-resolution observed textures via a Gaussian potential:

φ mp = exp - E mp 2σ 2 E , (10)
where σ 2 E is a variance parameter, and E mp is the Euclidean error in patch Q m between observed and training textures:

E mp = i∈Qm t - ip -t - i 2 2 . ( 11
)
This implicitly accounts for a color degradation by Gaussian noise, though other kinds of noise (e.g., Poisson, saltand-pepper) could be handled as well by plugging other discrepancy measures. To account for missing data, occluded vertices can simply be assigned a null error. When having multiple input images, we sum up the errors across views.

Patch Overlap Compatibility

We model the plausibility of high-resolution training patches given their neighbors through a Gaussian potential:

ψ mnpq = exp - C mnpq 2σ 2 C , ( 12
)
where σ 2 C is another variance parameter, and C mnpq is the Euclidean error in overlap O mn between training textures of neighbor patches:

C mnpq = i∈Omn t + ip -t + iq 2 2 . (13)
Practically, some neighbor patches may not overlap, either because of using a too small overlap ratio ρ or of the patch before growing being composed of its center only (which happens for big triangles filling the interior of the mouth). Such neighbors can simply be ignored and removed from the edge structure E since they would always be fully compatible. Compatibilities are also multiplied by the number of views to maintain a similar influence compared to errors.

Loopy Belief Propagation

The underlying probabilistic model can be cast into a graphical model, as a factor graph where nodes represent patches P m , P n , . . . and edges represent neighboring relations between overlapping patches. This network has a structure of Markov random field where dependencies reduce to pairwise interactions only (see Fig 3).

Solving for the most likely realization of patches from training faces t + ip , t + iq , . . . in this model is an expensive combinatorial problem. Indeed, the probability of training patches not only depends on their similarity with observed data t - i , but also on the neighboring compatibility between selected patches. An exact brute-force approach rapidly becomes intractable as the database size grows. Instead, we follow an iterative algorithm for approximate inference known as loopy belief propagation [START_REF] Murphy | Loopy belief propagation for approximate inference: an empirical study[END_REF], which is quadratic in the number of training faces. Specifically, we employ the min-sum variant which rather works on the log-likelihood ip , t + iq , . . . are selected per patch to be consistent with observations t - i and with neighbors according to potentials φmp, ψmnpq.

for better numerical stability, due to the high number of vertices involved in exponentiated sums of φ mp , ψ mnpq . Once patches are selected, the final texture is obtained by averaging the textures in overlap regions. We could also employ Poisson blending here, but it is quite demanding and did not seem to improve systematically results in our experiments, certainly because of patch overlap compatibilities ensuring local consistency. The whole process of error computations and belief propagation takes a couple of seconds. The patch compatibilities can be precomputed once for the whole database, which rather takes several minutes.

As a final remark, the algorithm, apart from the number of iterations I, depends on a single parameter, the ratio α = σ 2 E /σ 2 C of the two variance parameters. This variance ratio controls the trade-off between reconstructing the observations as faithfully as possible and ensuring that neighbor patches are as compatible as possible. In all our experiments, we fixed α = 1 to intuitively give the same influence between error and compatibility terms. A number of iterations I = 10 was also found sufficient for convergence.

Texture Normalization

In this section, we describe a variant to perform texture patch selection in a normalized space that is insensitive to camera and lighting parameters. We notably introduce a texture appearance model, and modify observation errors as well as patch compatibilities accordingly.

Texture Appearance Model

We assume that the color channels are independent, and thus consider a single channel while omitting its index in the sequel. We account for illumination with ambient light plus a directed light source. The ambient lighting simply multiplies the intrinsic texture ti . The directed lighting can be modeled according to the well-known dichromatic model of reflectance [START_REF] Zickler | Color subspaces as photometric invariants[END_REF]. Hence, it comprises additive diffuse and specular terms that apply an affine transform to the intrinsic texture (aka albedo). We also account for acquisition settings via a basic camera model with unknown color gain and offset per color channel when recording appearance.

We thus obtain an affine model for texture appearance:

t i = a i ti + b i , (14)
where a i encodes the camera gain, ambient lighting and diffusion, while b i encodes the camera offset and specularity. We note that only diffusion and specularity, due to directed lighting, actually depend on vertex i, via angles between local surface normals and light source or viewer directions.

Normalized Observation Error Function

We normalize textures before computing the observation errors according to the above model for texture appearance. Since the high-resolution observations are hidden, we do so in the low-resolution domain, by normalizing observed textures t - i via statistical standardization in mean and variance as ti = (t - i -µ)/σ, where we use the mean µ and standard deviation σ for textures t - i of visible vertices. Similarly, we normalize the training textures as tip = (t - ip -µ p )/σ p , where we use now the mean µ p and standard deviation σ p for the textures t - ip corresponding to observed vertices. We use these exact same parameters to normalize the high-resolution training textures as t+ ip = (t + ip -µ p )/σ p . To compare training texture patches with observed textures, we now compute the error function in the lowresolution space after normalization:

e mp = i∈Qm ( t- ip -t- i ) 2 . ( 15
)
This allows training patches to be used for reconstruction even if they were captured with another camera and under a different pose or illumination. In more detail, the error function is now invariant under affine transformations of textures, and hence under arbitrary changes in camera calibration via color gain and offset, as well as arbitrary scalings of ambient and directed light intensities. Going further, we may assume that the training database samples a fine enough subset of all possible angles between the light source and viewer directions, or at least the angles we expect to observe. Hence, the process is also robust, if not invariant, against changes in such angles up to neglecting deviations of local surface normals between the observed face and training faces.

Reconstructed Patch Overlap Compatibility

On the contrary to observation errors, compatibilities need to be computed based on the effective appearance in the final reconstructed space. In other words, we must simulate how neighbor patches would interact in overlaps if they were chosen for reconstruction. When normalized training textures are selected, we need to insert back the normalization parameters from the observed textures for reconstruction. It leads to reconstruction as ť+ ip = σ t+ ip + µ, and ťip = σ tip + µ, in the high-and low-resolution spaces respectively. For coherence of our methods, we would expect the degradation of the high-resolution reconstruction to equal the low-resolution reconstruction under our models for texture degradation, normalization and reconstruction:

ť- ip = 1 V i j∈Vi ť+ ip . (16)
This is indeed true as shown in the supplementary material.

The patch overlap compatibilities are thus now defined in the reconstructed high-resolution space:

c mnpq = i∈Omn ( ť+ ip -ť+ iq ) 2 . ( 17
)
These compatibilities cannot, unfortunately, be precomputed since we do not know the reconstructed textures ť+ ip , ť+ iq in advance. Given the computational burden of calculating these compatibilities, it is unrealistic to compute them again from scratch for each new observed face. Nonetheless, it is possible to precompute several related quantities so as to update the compatibilities on the fly. Even if still quadratic in the number of training faces, this makes the computation much faster during testing, typically a couple of seconds instead of several minutes. These updates are developed in the supplementary material.

Experimental Results

We now present experiments. We explain how the patch database is built, show texture modeling results as well as applications to super-resolution and texture completion.

Patch Database

We build a patch database with images from the CMU PIE face database [START_REF] Sim | The CMU Pose, Illumination, and Expression (PIE) database[END_REF]. The coefficients of the fitted morphable model and camera parameters provide a 3D model for each subject and a dense correspondence to each image. To obtain a complete texture over the face, we combine the 3 available views of the same subject under the same illumination by stitching them and filling unobserved data with Poisson blending [START_REF] Dessein | Seamless texture stitching on a 3D mesh by Poisson blending in patches[END_REF]. We sample 5 different lighting conditions, ambient light only, and ambient plus one flash light among front, top, left and right. As the morphable model does not account for glasses, beards or mustaches, we exclude corresponding subjects from the database, leading to a total of 175 face models representing 35 different subjects under 5 lighting conditions. We also exclude temporarily the subject under testing for a fair out-of-sample evaluation.

Texture Modeling

We here assess our methods for facial texture modeling from several incomplete poses. To account for possibly varying illumination conditions and acquisition settings, we employ the normalized variant of our algorithm.

In Fig. 4, we show results on reconstructing a complete face model for a given subject. Three reference views (Col. 1) are fitted to a state-of-the-art morphable model [20]. Even with high-quality input, the model is incapable of generalizing to the fine details of the face and unseen lighting conditions (Col. 2). Low-quality input images are obtained after downsampling by a factor of 16 to produce partial views of about 12 pixels wide (Col. 3). In the second and third rows, a color transformation is also applied to the input. We solve for a single high-quality model that can be rendered in any pose and color space (Col. 4). Since we solve for normalization parameters per image, we are able to correct the significant color differences between views.

Super-Resolution

We now apply our approach to classical super-resolution. This can easily be done by rendering the output of our face model in the same pose as observed. For visualization, we also display the non-modeled parts of the image after simple bicubic interpolation to match the output resolution.

In Fig. 5, we show super-resolution results for four subjects in nearly frontal poses. The high-resolution images (Col. 1) are artificially degraded, so that we have a groundtruth to compute error metrics, and then reconstructed. The state-of-the-art morphable model [20] fitted to the original images is again incapable of generalizing to the fine details (Col. 2). The images are obtained after downsampling by a factor of 16 (Col. 3). From this deficient input, our method yields faces with a high level of plausible detail, matching the ground-truth well (Col. 4). On the other hand, a stateof-the-art example-based super-resolution algorithm [START_REF] Yang | Image superresolution via sparse representation[END_REF], trained with exactly the same images as our model, fails to reconstruct any meaningful detail (Col. 5).

In Table 1, we present results of a leave-one-out evaluation on the full database. We use the root mean square normalized by the number of rendered pixels as an error metric (scores are given in percentage error). We consider degradations δ of 4, 8, 16, 32, the 5 illumination conditions, and average results across subjects. Given the poor visual results and computational burden (about an hour per image) of [START_REF] Yang | Image superresolution via sparse representation[END_REF], we exclude it from this quantitative evaluation.

Overall, applying our methods with the same shape fit as the morphable model provides a better texture, independently of lighting conditions, and even for the coarsest degradation (Rows 2 to 5). Although using a rough shape fit via the mean shape degrades results, our methods are still competitive with the morphable model fit to high-resolution input, and compare favorably except for the coarsest degradation (Rows 6 to 9). This is thanks to the image formation model, which allows to cope with misalignment of up to one low-resolution pixel because of averaging contributions regardless of their distance to the pixel center. The results also reveal that the normalized variant systematically outperforms the basic version. This is because normalization allows more expressiveness in the reconstruction process by adapting patch textures according to the input texture parameters. As we would expect, the reconstruction errors also increase with the degradation factor. They are also greater when directed light is present compared to ambient lighting only. We believe this results from both variants being unable to cope fully with nonlinearities in appearance due to shadowing and specularity.

Texture Completion

We finally consider texture completion problems. We set the degradation factor to 1, and discard the pixel aggregation step from the image formation model. We also reinsert the observed data in the reconstructed texture by Poisson blending at boundaries. Lastly, we constrain the face model with soft symmetry to ensure the plausibility of important symmetric features such as the eyes. Details on soft symmetry constraints are given in the supplementary material.

In Fig. 6, we demonstrate an example of texture completion for a face in a non-frontal pose. The non-frontal input only shows part of the face texture (Col. 1), which is clearly visible when sampling the view to texture the morphable model fit and rotate it to a frontal pose (Col. 2). Our methods reconstruct a complete and photorealistic texture (Col. 3) which, when projected into a frontal image (Col. 4), closely matches a real frontal view of the face (Col. 5).

In Fig. 7, we show an example of removing extraneous features, or clutter. The input images contain respectively a mustache and glasses (Col. 1). Such features are not modeled by the morphable model so that a pixel-wise binary outlier mask can be calculated via the fitting error (Col. 2). The morphable model fit is then textured by sampling the masked image (Col. 3). Performing texture completion over the occluded regions and blending with the original textures provides an ear-to-ear, high-quality texture (Col. 4). By rendering in the original image, we obtain photorealistic results where the extraneous features are removed (Col. 5).

Conclusion

We presented an example-based approach to face texture modeling from deficient views. We obtained promising results which are encouraging for further developments.

Firstly, dense correspondence restricts synthesis to examples of features in the same location as previously observed. Allowing patches to move onto the mesh surface is, however, not easy to deal with and should be investigated.

Another direction is to improve the texture appearance model with a full mixing matrix to capture spectral overlaps between light contents and between camera responses. We could also normalize per patch to account for multiple light sources or nonlinearities due to shadowing and specularity.

Lastly, we would like to build a model using intrinsic texture rather than appearance under representative lighting conditions. This way, much less training data would be needed. Nonetheless, error functions would require a model of illumination and patch selection would be more complex.

As for applications, we plan to evaluate our approach for face recognition in the wild. However, this requires designing our own shape fitting algorithm. Finally, tuning the three main design parameters (patch number, overlap factor, variance ratio) beyond the intuitive values used here might improve performance depending on the task at hand.

Figure 1 .

 1 Figure 1. There is a dramatic gap between the realism afforded by state-of-the-art face capture [4] (left) and face modeling [20] (middle). This gap is larger still when a model like [20] is fitted to an image, even if the image is of relatively high quality (right). Zoom in for detail.

Figure 3 .

 3 Figure 3. Network structure. The probabilistic model is a Markov random field over patches Pm, Pn, . . . where the training data t +ip , t + iq , . . . are selected per patch to be consistent with observations t - i and with neighbors according to potentials φmp, ψmnpq.

Figure 4 .

 4 Figure 4. Texture modeling from multiple low-quality. Col. 1: High-quality ground-truth. 2: Morphable model fit to high-quality ground-truth [20]. 3: Low-quality, color-transformed input images. 4: High-quality output of our method.

Figure 5 .

 5 Figure 5. Super-resolution. Col. 1: High-resolution ground-truth. 2: Morphable model fit to high-resolution ground-truth [20]. 3: Low-resolution input. 4: High-resolution output of our method. 5: Face-trained example-based super-resolution [27].

Figure 6 .

 6 Figure 6. Texture completion for a non-frontal pose. Col. 1: Nonfrontal input. 2: Morphable model fit with sampled texture. 3: Completed texture. 4: Frontal output. 5: Frontal ground-truth.

Figure 7 .

 7 Figure 7. Texture completion for removal of extraneous features. Col 1: Cluttered input. 2: Outlier mask. 3:. Morphable model fit with sampled texture. 4:. Completed texture. 5: Cleaned output.

Table 1 .

 1 Super-resolution evaluation (basic/normalized variants). Fit 4 04.8/04.0 12.1/09.9 09.8/08.4 10.5/08.6 12.1/10.0 8 05.1/04.3 12.5/10.4 10.2/08.9 10.9/09.1 12.5/10.6 16 05.3/04.7 13.5/11.7 10.8/10.0 11.6/10.1 13.5/12.0 32 05.9/05.5 15.5/14.9 12.6/12.6 13.7/12.6 16.0/15.5 Mean 4 05.9/05.1 13.1/10.8 09.8/09.4 11.6/09.7 13.2/11.0 8 06.2/05.4 13.5/11.4 11.2/09.9 12.0/10.2 13.6/11.7 16 06.5/06.0 14.7/13.0 12.1/11.2 12.8/11.4 14.8/13.3 32 07.2/06.9 16.9/16.4 14.0/14.1 14.8/14.0 17.3/16.9

	δ Ambient	Front	Left	Right	Top
	[20] 1	06.0	16.9	12.9	13.7	17.0

Acknowledgment

This work was supported by grant DSTLX1000070369 from the Defence Science & Technology Laboratory.