Kartic Subr

Sylvain Paris

Cyril Soler

Jan Kautz

Accurate Binary Image Selection from Inaccurate User Input

a) input image + scribbles (b) our result (c) using diffusion maps (d) using KNN matting Figure 1: We present a technique to make binary selections in images, such as to select the three penguins, using inaccurate scribbles to indicate foreground (blue) and background (red). Unlike existing approaches, our approach does not assume that the indications are 100% accurate. Since the related work, diffusion maps [FFL10] as well as KNN matting [CLT12], produce fuzzy selections, we manually thresholded their results to achieve the best possible selections.

Introduction

Marking specific pixels in an image as selected is an indispensable task, serving as the starting point for many imageediting operations such as background replacement, colour and tone manipulation, and copy-pasting. Obtaining a binary mask that is accurate at the pixel level by manual selection is an arduous task. Several techniques have been proposed to assist this process. For instance, the Magnetic Lasso [START_REF] Mortensen | Intelligent scissors for image composition[END_REF] "snaps" the user input to the closest edge as users delineate the object. However, this still imposes much tedium on users who have to carefully mark the object boundaries. Scribblebased approaches have been proposed to alleviate this dif-ficulty, e.g., [BJ01, ADA * 04, LSS09]. Users perform a few strokes over the object of interest, a.k.a. foreground, and a few more strokes to indicate the background. The system then solves a classification problem to mark each pixel as foreground or background. The advantage of this approach is that it requires a much simpler input from users. They do not have to carefully paint the selection or delineate its boundary. Instead, they only indicate a few regions on the foreground and background, such as in Fig. 1a, and the algorithm infers an accurate selection. However, most existing techniques assume that the user scribbles are perfectly accurate, that is, that they cover only foreground pixels or only background pixels. When this is not the case, i.e., if users introduce a scribble that crosses the foreground-background boundary, the quality of the produced selection degrades significantly (see Fig. 1c and1d). This imposes a strong constraint on the user input to be 100% accurate in order to get the best possible result. This can be a serious impediment in several cases. For instance, objects of interest with thin parts may be difficult to mark accurately; or touch interfaces and mobile devices can make it difficult to obtain accurate scribbles. To remedy this problem, we introduce an algorithm that generates accurate binary selections even from inaccurate user inputs, as in Fig. 1b.

Our approach consists of three main components. First, we remark that in many existing techniques, user scribbles are used as boundary conditions when solving the foreground-background classification problem [BJ01, ADA * 04,LSS09]. That is, the user-provided labels cannot be changed by the solver, which makes the process rely on the user ability to make perfectly accurate markings and gives it no chance to recover from erroneous scribbles. In contrast, our approach builds upon a dense conditional random field (CRF) that uses the user input as an initial guess while still allowing for corrections based on the image content ( § 2). Second, we observe that simple pixel-to-pixel color similarity only weakly discriminates between different regions. We address this shortcoming with improved similarity functions that consider pixels and their neighborhoods. We show that the latter are useful in discriminating regions of similar colors but different textures. However, because distance functions based on large pixel neighborhoods manipulate highdimensional data, they make solving a dense CRF problem impractical. Furthermore, some of these functions are not based on a Euclidean metric, e.g., the χ 2 test between patch histograms, which precludes the use of efficient algorithms [KK11]. We overcome this difficulty by efficiently embedding the pixel data into a low-dimensional Euclidean space with a metric that approximates the desired similarity functions ( § 2). We validate our approach on a variety of images ( § 3). We show that our algorithm consistently produces accurate selections even when the input scribbles are partly inaccurate. In comparison, the accuracy of the selections produced by previous work quickly degrades as soon as some regions are incorrectly labeled. We confirm this trend using ground truth data that allows us to quantify the impact of inaccurate scribbles on the output selection.

Contributions

The main contribution of this work is an algorithm to produce binary image selections that is robust to input accuracies. To achieve this goal, we make the following technical contributions:

• We characterize the use of user scribbles as hard constraints as the source of the inability of most existing techniques to cope with inaccurate input. We overcome this issue by solving a dense CRF.

• We study several similarity functions and show that the ones based on patches yield more accurate selections. • We enable the use of high-dimensional, non-Euclidean distance metrics by efficiently embedding them into a low-dimensional, Euclidean space.

The problem of generating binary selections is related to the matting problem that seeks to estimate the transparency of each pixel [RRW * 09]. In our result section, we show that even state-of-the-art matting algorithms perform poorly at binary selection when the input is not accurate. Conversely, we acknowledge that our approach, as all binary selection techniques, is not appropriate to select transparent objects.

Related Work

Several techniques have been proposed to improve over the simple brush and lasso. For instance, the magnetic lasso snaps the selection to the nearest edge [START_REF] Mortensen | Intelligent scissors for image composition[END_REF] and the edgeaware brush stops at color discontinuities [START_REF] Paris | Real-time edge-aware image processing with the bilateral grid[END_REF][START_REF] Olsen | Edge-respecting brushes[END_REF]. However, these tools still require tedious work from users to completely mark the selected region or its boundary. Selection techniques for multi-touch screens [START_REF] Benko | Precise selection techniques for multi-touch screens[END_REF] improve accuracy when clicking interface elements such as buttons and check-boxes are available.

An alternative workflow is to let users make a few discrete marks and have an algorithm interpolate these indications to infer a complete selection. For instance, GrabCut [RKB04] generates a selection from a user-provided bounding box. While such minimal input is sufficient in some cases, it is often useful to have users also indicate where the background is. This is typically done with scribbles, that is, users make strokes to mark a few foreground and background regions. Our paper focuses on this scenario. Among these techniques, we distinguish two categories. Most methods consider the user scribbles fully reliable and use them as hard constraints, e.g., [BJ01, ADA * 04, LSS09, LAA08], which is also commonly used in the context of tonal adjustments [LFUS06] or colorization [START_REF] Lischinski | Colorization using optimization[END_REF]. As we shall see, this strategy yields good results as long as the input scribbles are accurate but the selection quality degrades when it is not the case. In contrast, scribbles in AppProp [START_REF] Pellacini | AppProp: all-pairs appearancespace edit propagation[END_REF] and Instant Propagation [LJH10] are soft constraints and the optimization can override the user-specified labels, which allows it to correct input errors. However, these techniques target soft selections and do not perform as well in the binary case as we will see. In comparison, we formulate the problem as a dense CRF and uses the recent method developed by Krähenbühl and Koltun [KK11] to solve it efficiently, which produce significantly better selections as shown in our experiments.

A few techniques account for the possibility of errors. For instance, Tao et al. [TJP10] propose an algorithm for seamless compositing that is robust to erroneous selections. In comparison, our approach seeks to avoid such selection at the first place. Lazy Snapping [START_REF] Tang C.-K | Lazy snapping[END_REF] describes tools to correct the selection if the results from scribbles only is not accurate. This is complementary to our approach that focuses on producing a good selection from the scribbles even if they are not accurate.

Recent work by S ¸ener et al. [S ¸UA12

] proposes an error correction procedure and combines this with a dynamic and iterative graph-cut algorithm for interactive segmentation. Superpixels that do not conform to a dynamically-learned single Gaussian color model are removed from the graph.

The problem of accommodating inaccuracies in userindications shares some commonality with problems in background subtraction [START_REF] Sun | Background cut[END_REF]SJK09]. Although we share the need to handle an inaccurate data term, our scenario has its own specificities. We deal with static images, not video. We cannot observe what is behind the selected object. Also, our data term is sparse and user-provided and, for example, errors tend to be spatially coherent.

Robust and Accurate Selections

In this section, we describe the main components of our approach. We start by showing a selection model based on a dense CRF that is robust to scribble inaccuracies. Then, we show how to further improve the selection accuracy with patch-based similarity functions. Finally, we explain how to embed the data into an Euclidean space such that we can efficiently solve the dense CRF even for high-dimensional and possibly non-Euclidean distance functions.

Error-tolerant Scribble Expansion

Most previous work assume perfectly accurate user input. In this scenario, using the scribbles as hard constraints is a sensible choice. However, in our context where the scribbles may be partly inaccurate, such constraints are detrimental since any error in the scribbles becomes an error in the selection and in addition, because it is used as a hard constraint, it is likely to "contaminate" its neighborhood. We address this issue by using soft constraints instead. This gives the algorithm the ability to ignore the errors where there is sufficient evidence that the other label is more appropriate. Because inaccurate scribbles create spatially consistent errors, considering only a small neighborhood around a pixel, e.g., its 4 adjacent pixels [START_REF] Tang C.-K | Lazy snapping[END_REF], is unlikely to be enough to detect errors. In many cases, a compact group of pixels is mislabeled altogether and with such limited interactions, they would reinforce each other.

The solution is to have each pixel gather evidence from the entire image, i.e., from all other pixels [START_REF] Kohli | Robust higher order potentials for enforcing label consistency[END_REF]. In our work, we use the efficient dense CRF technique of Krähenbühl and Koltun [KK11] that minimizes the following functional:

E(x) ≡ ∑ i ψ u (x i ) + ∑ i< j ψ p (x i , x j ), (1)
with

ψ p (x i , x j ) = µ(x i , x j ) K ∑ m=1 k (m) (f i , f j ). (2)
Here, x i ∈ {foreground, background} is the output label at pixel i. ψ u (x i ) is the unary potential that is computed independently for each pixel; in our case it is a simple foreground/background classifier based on the pixel's feature vector f i (more details in next subsection). The term ψ p (x i , x j ) denotes the pair-wise term, where µ(x i , x j ) is a simple Potts model and introduces a penalty for pixels being assigned different labels (µ(x i , x j ) = 1 if x i = x j and 0 otherwise); k (m) (f i , f j ) is a kernel weighting how likely it is to have the same label x i and x j given their corresponding feature vectors.

It is important to note that the method of Krähenbühl and Koltun only supports Euclidean distances between features, as the operand to their Gaussian kernel. This is often insufficient for clean selections (see Fig. 2b) for an example). Although we also use a Gaussian kernel k (m) over the (weighted) L 2 norm between the feature vectors, we can accommodate other similarity measures based on non-Euclidean distances by first computing an approximate Euclidean embedding of the pixels. That is, rather than packing a sophisticated similarity metric into the kernel, we use a simple Gaussian kernel and, instead, automatically adjust the feature space using to approximate the given similarity measure.

Even though the energy functional E(x) depends on all pairs of pixels, i.e., each pixel i is connected to all other pixels j via the pair-wise term ψ p , it can be solved very efficiently as shown by Krähenbühl and Koltun. In the following subsections, we detail the unary term and explain how to obtain the feature vectors f given a similarity measure.

Scribble Input & Per-Pixel Classifier

The user supplies foreground and background scribbles as input. We use these to define probabilities, for each pixel being labeled foreground (p f ≡ P(x i = foregound)), background (p b ≡ P(x i = background)) and void (p v ≡ P(xi = void)). That is, each pixel is assigned a 3-tuple of probabilities, p f , p b , p v so that the three sum to one. We set these tuples to be 0.5, 0.25, 0.25 for pixels under the foreground scribble, 0.25, 0.5, 0.25 for pixels under the background scribble and 0.33, 0.33, 0.33 for all other pixels. This choice assumes an equal possibility of inaccuracies over the three labels, in the absence of extra information (besides the scribbles). For example, changing one of the 0.5 values to 0.6 will make it less robust to the corresponding input inaccuracy. Although we experimented with more sophisticated assignments, such as using distances to the foreground and background scribbles to derive the probabilities, they did not impact the results sufficiently enough to justify their complexity. We then compute the corresponding unary potentials from the probabilities, as the logarithms of the respective reciprocals. We rely on the fully connected CRF to propagate the label assignment across the rest of the image.

Pixel Similarity Functions

As discussed, the result of the dense CRF depends on how we compare pixels. In this section, we focus specifically on how to evaluate pixel similarity. We discuss how to incorporate it in the dense CRF model in the next subsection.

A simple option is to compare pixels using their colors, that is, for two pixels i and j, we estimate their similarity using the L 2 norm in a color space such as RGB or CIE Luv. As we shall see in the result section, this works well for images in which the foreground and background have different colors. However, this may not always be the case. When color is not sufficiently discriminative, a solution is to also observe the neighborhood around each pixel to account for the local texture. These patches can be compared in several ways. First, one can unroll the patches into large vectors and use the L 2 norm on these vectors. Standard options that compare the cross-bin distances between the histograms of the patches are more robust, yet discriminative. We experimented with two standard choices: the earth mover's distance (EMD) [START_REF] Rubner | A metric for distributions with applications to image databases[END_REF] and the χ 2 distance, which is de-rived from the statistical χ 2 test to compare two distributions [START_REF] Greenwood | A guide to chi-squared testing[END_REF]. EMD is a common choice for vision applications [START_REF] Rubner | A metric for distributions with applications to image databases[END_REF]. It interprets histograms as piles of dirt and estimates their differences as the amount of work needed to transform one pile into the other by moving dirt. Doing so takes into account how different the density peaks are as well as how distant they are in color space. We refer to [START_REF] Rubner | A metric for distributions with applications to image databases[END_REF] for a formal definition. χ 2 distance is another common choice that normalizes the density differences by their amplitude to account for statistical variation [START_REF] Greenwood | A guide to chi-squared testing[END_REF]. For two histograms h 1 and h 2 with bins indexed by ℓ, we compute the distance as ∑ ℓ (h 1ℓh 2ℓ ) 2 /(h 1ℓ + h 2ℓ ).

Manifold Embedding

The technique that we use to solve the dense CRF [KK11] requires the similarity between pixels to be expressed as the L 2 norm between feature vectors f. Further, to obtain interactive running times, the f vectors need to be low-dimensional. Comparing the color of a single pixel is straightforward to use with this solver by using the 3 color channels of a pixel to define a 3D f vector. However, the patch-based similarity functions cannot be used as is. For the L 2 norm on patches, since it operates on a vector space, we could use PCA to reduce the dimensionality of the feature vectors to get an optimal approximation of the similarity function. However, it does not apply to the χ 2 and EMD functions that do not correspond to a Euclidean distance in a vector space. We overcome this problem by embedding the data in a space with a metric that approximates a given distance function.

We experimented with several variants. While nonlinear embeddings such as Isomaps [TdL00] and LLE [START_REF] Roweis | Nonlinear dimensionality reduction by locally linear embedding[END_REF] can represent more complex structures, they are also more computationally intensive and we did not see an improvement in performance that would warrant such additional cost. Instead, we opted for a linear embedding using Multi-Dimensional Scaling (MDS) [CC00] to estimate a linear embedding. We use the Landmark MDS algorithm [START_REF] De | Global versus local methods in nonlinear dimensionality reduction[END_REF] that achieves interactive performances by computing the embedding for a few points while taking into account the distances between all the data points. This is a type of Nyström method since it approximates the structure in a large matrix by sampling a small set of rows in the matrix. When the input metric is Euclidean, the result is equivalent to PCA, i.e., it produces an optimal embedding. We refer to [START_REF] De | Global versus local methods in nonlinear dimensionality reduction[END_REF] for the details of the Landmark MDS algorithm. The result is a set of lowdimensional feature vectors f that represent the image pixels, which pairwise L 2 distances is as close as possible to the input distance constraints. We feed these low-dimensional points into the pairwise term ψ p . In practice, for the distances that we experimented with, we observed that threedimensional vectors f were sufficient.

Synthetic Experiments

To find which option works best in our context, we use a synthetic experiment that allows us to control amount of er-Figure 3: Evaluation of the quality of the binary classifier by plotting the average Matthews correlation coefficient over many runs against percentage error in the input scribbles. A value of 1 on the Y-axis is achieved when the selection matches ground truth perfectly. For PAT (L2 distance between local patches), χ 2 , and EMD, we use 5 × 5 patches. All distances are embedded in a 3-dimensional Euclidean space (even the RGB center pixel similarity, which is equivalent to PCA). rors in the input scribbles. We manually create ground-truth selections for a few images. For each image, we randomly pick 50 pixels in the foreground and 50 pixels in the background, and assign them the ground-truth label. We also define an "error zone" that comprises the background pixels that are less than a distance D from the foreground. In practice, we set D equal to 5% of the image diagonal. We randomly sample between 0 and 50 pixels in this region and assign them a foreground label, which is erroneous. This experiment represents the case where users have difficulties to mark the main object and their foreground marks "bleeds over the background". While this is clearly an approximation, it matches our own experience, i.e., we found the foreground often harder to label than the background -and most importantly, it allows us to study the impact of the amount of input error on the produced selection. We used this experiment to evaluate several factors:

• the color space: RGB or CIE Luv, • the size of the patches: 3 × 3 and 5 × 5 (larger sizes were too time consuming). • the similarity functions: L 2 norm on a single pixel, L 2 norm on patches, EMD, and χ 2 .

Figure 3 shows sample plots. For the sake of clarity, we only report the best color space and patch size for each similarity function. We use Matthews correlation coefficient (MCC) to evaluate the quality of binary selections [Pow11]. It is defined as follows: (p np n)/ (p + p)(p + n)(n + p)(n + n) with p, n, p, n, the numbers of true positives, true negatives, false positives, and false negatives. A value of 1 means a perfect segmentation and the score decreases as there are more errors in the selection. A random allocation of labels results in a value of 0 and a perfectly inverted classification yields a value of -1. For binary selection, we only expect values in [0, 1].

Two options stand out: the CIE Luv L 2 norm on a single pixel performs well on colorful images while χ 2 on the CIE Luv histograms of 5 × 5 patches yields satisfying results on challenging images with little color information for which texture differences are critical. By default, we use the L 2 norm on a single pixel, and users can switch to the "texture mode" that corresponds to χ 2 on 5×5 patch histograms.

Results

We validate our approach by comparing it to representative existing techniques. Diffusion Maps [FFL10] also use an embedding to better differentiate the pixels. It then applies the Matting Laplacian technique [LLW08], which assumes accurate scribbles; an assumption, as we shall see, that has a major impact on the produced selections. Hence, we regard this method as representative of all the methods that use the scribbles as hard constraints, e.g., [ADA * 04]. We also compare to KNN Matting [CLT12] because it produces stateof-the-art mattes. Furthermore, we compare against Instant Propagation [LJH10], an efficient edit propagation method, which can tolerate some inaccuracies in the scribbles. All techniques generate soft selections. To compare them to our approach, we threshold their results to get binary selections. To make this step fair, we use an oracle to find the best possible threshold. For quantitative experiments, for each run, we test 10 regularly spaced threshold values and select the one that yields the closest result to ground truth. For visual results, we manually set the threshold to obtain the best looking selection.

For our results, we evaluate both the "center pixel" option where we compare pixels using the L 2 norm on their colors, and the χ 2 test on patch histograms. Both are computed on a 3D feature space obtained with Landmark MDS. For the center pixel option, this aligns the color space axes with the color distribution, which produces better results in our tests. With χ 2 , this generates a 3D space with a metric that approximates the test value. The CRF solver classifies pixels as "foreground", "background", and "unclassified". In most cases, there are no "unclassified" pixels but when there are, we count them as false positives or false negatives in our quantitative measure, i.e., we apply the worst scenario to prevent bias in our favor.

On an Intel Core i7-2630QM CPU @ 2.00GHz, our algorithm runs in about 2 seconds for χ 2 using 5 × 5 patches on images of size 800 × 600. Of this, about 35% is typical for computing the pairwise distances, about 50% for the embedding, and the rest for the dense CRF propagation. For central pixel only, our algorithm runs in under 1 second for the same image. The embedding is only performed once, while loading the image. For each set of scribbles, only the classification (using dense CRF) needs to be performed, which is at near-interactive rates.

Quantitative Results

We proceed as in Section 2.4, i.e., we use random pixels as scribbles with a controlled number of errors and compare the results to manually created ground truth. In this test, in addition to Diffusion Maps and KNN Matting, we include the pixel similarity function based on the feature vectors f proposed by An and Pellacini [START_REF] Pellacini | AppProp: all-pairs appearancespace edit propagation[END_REF]: they augment the pixel color with average and standard deviation of the colors in a 3 × 3 neighborhood. We use these f vectors in the same dense CRF as our approach. We also compare our approach to nearest-neighbor classifiers based on the pixel colors and the χ 2 distance between patch histograms.

The plots in Figure 5 show that when there is no error, all methods perform well. But as soon as inaccuracies corrupt the input scribbles, the accuracy of other techniques decreases quickly. For images where colors discriminate well the foreground from the background as in the palm example, the decrease is slower; whereas it is sharper with challenging images such as the manga. In comparison, with our approach, the selection quality is almost not impacted until high levels of errors, typically beyond 50%. Error values measured for partly inaccurate scribbles made by hand confirm that our approach performs better (Fig. 4).

Figure 3 compares four embedding dimensionalities with respect to selection accuracy for decreasingly accurate input. The data shown is for the palm leaf image, with the χ 2 distance between local histograms. Although there is a notable improvement in accuracy (for input errors of < 50%), this comes at the cost of performance.

Qualitative Results

Figure 6 shows actual selection produced by our approach and existing techniques. We manually created scribbles with various degrees of error. The results show that for moderate levels of error as in the palm and ostrich images, all methods produce usable selections. However, for more challenging cases, existing techniques generate inaccurate outputs. In all cases, the errors come directly from the input scribbles, that is, input errors appear in the output and often expand into their vicinity. In comparison, the result of our approach contain far fewer errors and are usable.

Figure 7 shows two examples using GrabCut [RKB04]. While it requires different user input (bounding box), the input does not need to be accurate, similar to our method. GrabCut works well on some images but tends to have difficulties in cases where the bounding box is not expressive enough. method They only accept foreground scribbles. Their results also depend on the order in which pixels are marked as foreground.

The authors kindly shared their results. Note that their implementation has modified the aspect ratios. Their results were obtained by user scribbles as close to ours (in fig. 6) as possible, while maintaining an order favorable to their algorithm.

Discussion and Limitation

Parameters We experimented with various choices for the similarity measure, along with its associated parameters such as patch size and color space, Nyström sampling rate, output dimension and the width of the CRF Gaussian kernel. All results in this paper were generated with 3D embeddings and a constant set of parameters. As mentioned earlier, we found that using the distance between RGB center pixels or χ 2 distances between the CIE Luv values of 5 × 5 patches mutually work well for a variety of images. For the Nyström approximation, we used 0.0025% of the number of pixels in the image, or 25 samples for a 1 megapixel image. We use a standard deviation of 1 for the CRF Gaussian kernel when using the patch-based similarities and 0.1 when using the center pixel comparison.

The Effect of Scribbles If one class of indications, say background scribbles, are accurate our selection is more robust to errors in the foreground scribbles. For instance, the wind turbines in Figure 10 are selected although the foreground scribbles actually cover more non-selected pixels than desired ones. Intuitively, our simple assignment of probabilities for computing the unary potential leads to a voting scheme. Since the background scribbles cover the sky sufficiently, the sky pixels in the foreground stroke are "outnumbered" and are less likely to confuse the classifier. Our algorithm still produces an accurate result despite the highly inaccurate foreground scribble. In our experiments, we observed that dense scribbles tend to overly constrain the CRF, leading to less accurate results. However, users typically make sparse scribbles, as in Figure 6, with which our approach works well.

Similarity measures In this paper, we have used centerpixel distances and χ 2 distances between local histograms since they compared favorably among the few similarity measures that we explored. Experimenting with more powerful similarity measures is an exciting avenue for future work. For example, the pixel position may be included in the computation of dissimilarities. We found that often, the objective is to select the main object in an image. In that case, pixel position does not help much but adds 2 dimensions to the feature vectors, which slows the process down without an evident improvement in accuracy. In general, a variety Limitations We currently rely on users to identify textured images and switch to χ 2 distances. An interesting direction would be to build an extension to make this choice automatically. Also, our method is designed for binary selections and would not perform as well on objects with transparent regions and/or thin features that are a few pixels wide or less. For instance, the spokes of the bike in Figure 11 are missing. Objects with similar color and texture as the background like the starfish are also challenging and the produced selection may require manual editing before being usable. Nonetheless, our approach provides a good starting point that is significantly more accurate than the output of other techniques. More intelligent image descriptors might help in this case, and are an interesting avenue of future research.

Conclusion

We have presented a method to produce accuracte image selections even when the user input is inaccurate. Our experiments show that our results are on par with existing techniques when there is no error in the input and that it performs significantly better when inaccuracies are present. We hope that our approach will lead to easier-to-use editing tools that tolerate some errors from users. We believe that this can be particularly useful with mobile devices that have small screens.

input image input scribbles diffusion maps KNN matting ours: center pixel ours: χ 2

Figure 11: The top example is an extremely challenging case because of the camouflage of the starfish. Although our result would need to be cleaned, it is more accurate than other techniques. The bottom example shows that, similar to other methods, our approach is not good at identifying thin features such as the spokes.

  (a) Input (b) CRF with RGB distance (c) nearest neighbor with χ 2 (d) CRF with χ 2

Figure 2 :

 2 Figure 2: Inaccurate foreground (blue) and background (red) user-scribbles in the input image (a) pose a challenge for selection.Applying an efficient and powerful segmentation technique such as with a dense CRF [KK11] with Euclidean distance in space (location) and color (RGB) works well (b) but is often insufficient. Using a sophisticated similarity measure to provide a distance, with simple classification such as a nearest-neighbor approach fails when the scribbles are inaccurate (c). Our approach is to enable a combination of both. A combination of the χ 2 distance, a cross-bin histogram similarity measure, with a dense conditional random field (CRF) binary classifier yields a clean solution (c) .

Figure 8 Figure 4 :

 84 Figure8shows the results of error tolerant interactive segmentation using dynamic and iterated graph-cuts [S ¸UA12].

Figure 7 :

 7 Figure 7: A few examples showing results using Grab-Cut [RKB04]. Compare to our selections in Figure 6.

Figure 9 :

 9 Figure 9: Increasing the dimensionality of the embedded space improves selection accuracy at the cost of speed. The plot compares selection accuracy for embedding dimensionalities 3D, 6D, 9D and 15D on the palm leaf image.

Figure 8 :

 8 Figure 8: A few examples showing results using error-tolerant interactive image segmentation using dynamic and iterated graph-cuts [S ¸UA12]. This method only accepts foreground indications from the user. Compare to our selections in Figure 6.

Figure 10 :

 10 Figure10: Our approach relies on relative accuracy of foreground and background. For highly inaccurate scribbles, such as the blue one, the other (red) scribble is compensatory. Since the red scribble covers ample regions of the sky and ground, the classifier is reinforced about the background pixels and is less likely to be confused by an inaccurate foreground scribble.

c 2013 The Author(s) c 2013 The Eurographics Association and Blackwell Publishing Ltd.

Acknowledgements

We thank the anonymous reviewers for their suggestions. We also thank the authors of [S ¸UA12] for providing the input scribbles and segmentation results shown in fig. 8. Kartic Subr is supported by the Royal Society's Newton International Fellowship.


Diana Pocaznoi
email: diana.pocaznoi@ensiacet.fr

Benjamin Erable

Luc Etcheverry

Marie-Line Delia

Alain Bergel

Forming microbial anodes under delayed polarisation modifies the electron transfer network and decreases the polarisation time required

Keywords:

Microbial anodes were formed from compost leachate on carbon cloth electrodes. The biofilms formed at the surface of electrodes kept at open circuit contained microorganisms that switched their metabolism towards electrode respiration in response to a few minutes of polarisation. When polarisation at À0.2 V/SCE (+0.04 V/SHE) was applied to a pre-established biofilm formed at open circuit (delayed polarisation), the bacteria developed an extracellular electron transport network that showed multiple redox systems, reaching 9.4 A/m 2 after only 3-9 days of polarisation. In contrast, when polarisation was applied from the beginning, bacteria developed a well-tuned extracellular electron transfer network concomitantly with their growth, but 36 days of polarisation were required to get current of the same order (6-8 A/m 2 ). The difference in performance was attributed to the thinner, more heterogeneous structure of the biofilms obtained by delayed polarisation compared to the thick uniform structure obtained by full polarisation.

Introduction

Electro-active (EA) biofilms have been widely exploited to design microbial fuel cells (MFCs) [START_REF] Lefebvre | Microbial fuel cells for energy self-sufficient domestic wastewater treatment -a review and discussion from energetic consideration[END_REF][START_REF] Logan | Scaling up microbial fuel cells and other bioelectrochemical systems[END_REF] microbial electrolysis cells [START_REF] Geelhoed | Electricity-mediated biological hydrogen production[END_REF][START_REF] Logan | Microbial electrolysis cells for high yield hydrogen gas production from organic matter[END_REF] and other related technologies. Numerous studies have identified EA bacteria [START_REF] Logan | Exoelectrogenic bacteria that power microbial fuel cells[END_REF] and deciphered the different electron transfer pathways that can be used inside microbial biofilms [START_REF] Rabaey | Microbial ecology meets electrochemistry: electricitydriven and driving communities[END_REF][START_REF] Reguera | Extracellular electron transfer via microbial nanowires[END_REF][START_REF] Schaetzle | Bacteria and yeasts as catalysts in microbial fuel cells: electron transfer from micro-organisms to electrodes for green electricity[END_REF]. In contrast, the mechanisms of formation, structuring and ageing of the EA biofilms have rarely been investigated. [START_REF] Wang | Accelerated start-up of two-chambered microbial fuel cells: effect of anodic positive poised potential[END_REF] have observed that the start-up time of an MFC was significantly decreased when a constant potential was applied to the anode, in comparison with the same MFC implemented without applied potential. They postulated that the applied potential increased the positive charge on the anode surface and thus favoured the primary adhesion of negatively charged bacteria. The adhesion of EA species on anodes might consequently depend on the surface charge of the electrode as it has sometimes been suggested [START_REF] Busalmen | Whole cell electrochemistry of electricity-producing microorganisms evidence an adaptation for optimal exocellular electron transport[END_REF][START_REF] Cheng | Ammonia treatment of carbon cloth anodes to enhance power generation of microbial fuel cells[END_REF]. In contrast, [START_REF] Aelterman | The anode potential regulates bacterial activity in microbial fuel cells[END_REF] did not observe significant difference in start-up time with applied potentials in the range from À0.4 to 0 V vs. Ag/AgCl. Actually [START_REF] Wang | Accelerated start-up of two-chambered microbial fuel cells: effect of anodic positive poised potential[END_REF] have inoculated their MFCs with domestic wastewater, while [START_REF] Aelterman | The anode potential regulates bacterial activity in microbial fuel cells[END_REF] have taken their inoculum from an operating MFC, which means that the microbial community was already adapted to generating electricity. Comparing the two studies suggests that the time necessary for wild microbial communities to adapt to electrochemical conditions depends on the applied potential, while the time necessary for already-adapted bacteria to form EA biofilms does not. When using wild communities as inoculum, the adaptation phase necessary for the cells to develop their EA capacity may consequently be an essential parameter in controlling the formation of EA biofilms, rather than electrostatic interactions between bacteria and electrode surface. The occurrence of an initial phase during which the cells must optimize attachment or the electron transfer chain to the surface has also been observed with pure cultures of Geobacter sulfurreducens [START_REF] Marsili | Voltammetry and growth physiology of Geobacter sulfurreducens biofilms as a function of growth stage and imposed electrode potential[END_REF]. Nevertheless, little is known so far about the way a clean electrode surface catches microbial species from a natural environment and how they shift from the conventional respiration mechanism to an anode respiring mechanism.

The purpose of this work was to give some insights into EA biofilm construction with the practical target of improving the performance of microbial anodes. Garden compost was used as the source of the inoculum. Soils are a very rich source of microorganisms [START_REF] Liu | A review of methods for studying microbial diversity in soils[END_REF][START_REF] Torsvik | Total bacterial diversity in soil and sediment communities -a review[END_REF] and garden compost has proved its excellent capacity to form EA biofilms. Microbial anodes can be formed by simply embedding polarised electrodes in a soil [START_REF] Parot | Forming electrochemically active biofilms from garden compost under chronoamperometry[END_REF], but it is then difficult to use the resulting anodes out of their initial medium. A new procedure has been proposed recently, which consists of producing a leachate by percolating the garden compost with an ionic solution and then using the leachate obtained as the inoculum. This procedure has given promising results for the treatment of dairy wastes [START_REF] Cercado-Quezada | Electrochemical microstructuring of graphite felt electrodes for accelerated formation of electroactive biofilms on microbial anodes[END_REF], 2010a). The same procedure has led to current density so high as 66 A/m 2 for acetate oxidation when the biofilms were formed around ultra-microelectrodes [START_REF] Pocaznoi | Ultra microelectrodes increase the current density provided by electroactive biofilms by improving their electron transport ability[END_REF]. Obviously this result has been reached with particular laboratory electrodes, but it demonstrates the promising potential of the inoculum source.

The present study used compost leachate as inoculum and acetate as substrate. Comparing biofilms formed at open circuit and biofilms formed under constant polarisation showed very different structures and allowed the phases of biofilm formation and of development of the extracellular electron transfer network to be distinguished. These observations were exploited to define an optimal procedure for the formation of microbial anodes.

Methods

Soil biofilm

One litre of Garden compost (Cultura, Lombricompost) was mixed with a 60 mM KCl solution and left for 24 h under stirring at room temperature. The mix was then centrifuged and the resulting leachate, supplemented with 10 mM acetate, was used for the formation of EA biofilms.

Electrochemical instrumentation and set-up

Electrochemical experiments were carried out in closed vessels that contained 150 mL leachate. Carbon cloth (supplied by PaxiTech SAS, France) of 2 cm 2 projected surface area was used for the working electrodes and a platinum grid for the auxiliary electrode. All potentials were controlled via a conventional 3electrode set-up vs. a saturated calomel reference electrode (SCE, Radiometer, +0.241 V vs. SHE) by means of a VMP potentiostat (Bio-logic SA). Polarisations were performed at À0.2 V vs. SCE because this potential was around the most negative value that could provide the maximum current density (Cercado-Quezada et al., 2010b). Cyclic voltammetries were performed at 1 mV s À1 . Electrochemical experiments were carried out at room temperature, around 22 °C.

Microscopy and image analysis

For scanning electron microscopy, the microbial structures were stabilised on the electrode surfaces by fixation in phosphate buffer (400 mM, pH 7.0) with 4% glutaraldehyde. The electrodes were then rinsed in phosphate buffer with saccharose (0.4 M), treated with 2% osmium tetroxide in phosphate buffer and saccharose for 1 h, dehydrated in an ascending series of acetone solutions (50%, 70%, 100%), then in acetone and hexamethyldisilazane (50:50) and, finally, in 100% hexamethyldisilazane. Anodes were examined with an LEO 435 VP scanning electron microscope.

Results and discussion

Biofilm formed at open circuit

Five 2 cm 2 carbon cloth electrodes were left at room temperature in separate bioelectrochemical reactors containing 150 mL of the same compost leachate supplemented with 10 mM acetate, for 0 (control), 8, 12, 15 and 19 days. No polarisation was applied and the open circuit potential (OCP) was recorded as a function of time (Fig. 1A). The OCP exhibited similar evolution for each electrode, with initial values around +0.05 V vs. SCE and a fast decrease during a 4-day period, followed by a stabilisation at close to À0.5 V vs. SCE at day 5.

The OCP values are the result of the delicate balance between electron exchanges that are spontaneously established between the electrodes and the species from the bulk environment. For instance, cathodic currents (electrons lost by the material) may be due to the natural slow reduction of dissolved oxygen on the electrode surface, and anodic currents (electrons gained by the material) may result from the slow oxidation of the electrode surface itself. With graphite and carbon electrodes, the presence of functional groups like phenol, carbonyl, carboxyl and quinine on the surface [START_REF] Cabaniss | Electrocatalysis of proton-coupled electron-transfer reactions at glassy-carbon electrodes[END_REF][START_REF] Nagaoka | Surface-properties of electrochemically pretreated glassy-carbon[END_REF]) makes the anodic process complex. Moreover, in a solution such as compost leachate, which contains a large diversity of dissolved organic compounds, anodic currents can also be due to the slow spontaneous oxidation of some of them. For instance, OCP recording is commonly exploited to measure the redox potential of solutions. In this case, a platinum electrode is used because no significant oxides form on its surface.

From a general point of view, OCP decrease is due to vanishing of the reduction current and/or to an increasing of the anodic current.

For instance, in redox potential measurements with a platinum electrode, it is generally postulated that OCP decrease is mainly due to vanishing of the cathodic current because of oxygen depletion. Here OCP decrease can be due to both the oxygen depletion in the closed electrochemical reactor and the increase of the anodic current resulting from the catalysis of acetate oxidation. Actually, it should be borne in mind that OCP values are controlled by the very low exchange currents due to spontaneous reactions only.

In this framework, the adhesion of only a few EA bacteria is sufficient to catalyse low acetate oxidation and to cause OCP decreases observed here. To check this assumption, two experiments were performed with, in each reactor, one electrode dipping in the leachate and another hanging in the gas free space. In both experiments, the OCP of the immersed electrodes followed the same evolution as previously recorded, with an initial OCP around +0.1 V vs. SCE which decreased to À0.65 V vs. SCE after 20 days of immersion. At day 20, the hung clean electrodes were plunged into the solutions. The OCPs of the clean electrodes were in the range of À0.1 to À0.2 V vs. SCE in both experiments, i.e. around 0.2 mV less than the initial OCP value. The difference between the initial OCP value (+0.1 V vs. SCE) and OCP measured at day 20 with the clean electrode can only be attributed to changes in the solution composition, and most probably to the consumption of oxygen by the aerobic microorganisms during the first few days of the experiment. The final stable OCP values being around À0.65 V vs. SCE, it can be concluded that oxygen depletion was responsible for around one third of the whole OCP decrease, while the catalysis of the oxidation reaction supported around two thirds. These experiments confirmed that a major part of OCP decrease was due to the primary settlement of EA microbial cells that started to catalyse acetate oxidation.

Going back to the five-electrode experiment, each electrode was polarised at À0.2 V vs. SCE for 3 h at the end of its open circuit phase (Fig. 1B). The control electrode that was polarised immediately upon immersion in the compost leachate did not produce any current during the 3 h of polarisation. In contrast, every other electrode gave an oxidation current density of about 50 mA/m 2 after only 30 min of polarisation. This time was too short for the current increase to be attributed to the growth of EA microbial species. It indicated an activation phase of the EA cells that were already present on the anode surface and switched their metabolism towards an electrode-respiring mechanism in response to the polarisation.

In conclusion, the microbial communities that adhered to the surface of non-polarised electrodes contained some microbial species with EA ability, which contributed to OCP decrease. These EA species activated their capability to use the electrode as final electron acceptor after a few tens of minutes of polarisation.

Biofilm formation at open circuit followed by short-term (3-day) polarisation

Six new reactors (150 mL compost leachate, 10 mM acetate) were started with six 2-cm 2 carbon cloth electrodes kept at open circuit for different times: 1, 5, 9, 12, 15 and 19 days. At the end of the open circuit time, a new 10 mM acetate addition was made and each electrode was polarised for 3 days at À0.2 V vs. SCE. The final biofilm ages were respectively 4, 8, 12, 15, 18 and 22 days. The current densities measured at the end of the 3 days of polarisation increased from 0.2 to 2.7 A/m 2 with the biofilm ages (Fig. 2A). This experiment was reproduced with a leachate formed from a different brand of compost. After 3 days of polarisation the biofilms with final ages 4, 7, 10 and 12 days gave 0.1, 0.4, 0.9 and 2.2 A/m 2 , respectively. This second compost led more quickly to efficient biofilms, but the general behaviour was the same: the biofilms obtained after 3 days of polarisation always showed more efficient EA capabilities when the preliminary open-circuit time was longer.

Cyclic voltammetry (CV) was performed at the end of the 3-day polarisation (Fig. 2B). The current densities measured at À0.2 V vs. SCE on the CV curves were identical to the values recorded at the end of the polarisation, this showed that the CV scan rate was low enough to represent the stationary behaviour of the microbial electrodes.

CV curves detected a variety of different electrochemical characteristics. Some electrodes exhibited a conventional sigmoid shape (4-and 18-day-old biofilms), while others showed one or several peaks (12-and 22-day biofilms). Peaks observed with the 12-day-old biofilm revealed the presence of different electron transfer pathways in comparison to the other biofilms. The variety of different CV shapes revealed differences of the biofilms in terms of EA capabilities. Compost is a microbiologically-rich medium and the spontaneous formation of biofilms without any particular selection pressure during the open circuit phase logically led to different biofilms in terms of EA capabilities. Moreover, after 3 days of polarisation, biofilms were at the crossroads of their development, tipping over from an open-circuit way of development to polarisation-supported growth. Actually, EA and non-EA species that had spontaneously colonised the electrode surface during the open-circuit phase were still present in the biofilm, while the 3-day polarisation started to exert a selection pressure. CVs recorded at this crucial period consequently detected diverse EA capabilities. Nevertheless, whatever the differences in the intrinsic characteristics of each biofilm, it was observed that a longer preliminary open-circuit phase favoured the emergence of EA properties. The older biofilms (18 and 22 days old) produced significant current density (1 and 2.8 A/m 2 , respectively) after only 3 days of polarisation. The 22-day-old biofilm exhibited a characteristic shape that has been reported in a recent theoretical study [START_REF] Strycharz | Application of cyclic voltammetry to investigate enhanced catalytic current generation by biofilm-modified anodes of Geobacter sulfurreducens strain DL1 vs. variant strain KN400[END_REF]. This study described the electron transfer (ET) pathway from acetate to the electrode in 5 steps:

(i) mass transport of acetate and products, (ii) reduction of the microbial cells by acetate, (iii) reduction of (an) electron transport mediator(s) by the reduced microbial cells, (iv) electron transport by mediator diffusion (for diffusing mediators) or by a series of sequential redox reactions between adjacent molecules of mediators (for bound mediators), (v) oxidation of the mediator(s) at the electrode surface.

Theoretical CV curves were derived assuming for each that one of the five different steps was rate-limiting. Some numerical CV curves showed the same shape as that observed here with the 22-day biofilm, with an oxidation peak superimposed on the conventional sigmoid curve. Such curves were obtained only when the ET rate was assumed to be limited by step (iii) i.e. by ET from the microbial cell to the mediator. The numerical model never led to a similar peaked curve when the other steps were assumed to be rate-limiting. This hypothesis makes sense here. The biofilms that were formed without polarisation during the first 19 days did not develop an extracellular ET network. After 3 days of polarisation, the cells that had potential EA capability had shifted their metabolism to the anode-respiring pathway, they had probably started to multiply, but they had not yet produced an efficient extracellular ET network. They needed more time to develop an efficient ET network through the initial biofilm that had formed during the 19 days at open circuit. The ET rate can consequently be limited by step iii, i.e. by electron transfer from the microbial cells to the still poorly developed ET network. The younger biofilms did not show this limiting step because the initial open-circuit biofilm was less developed. Comparing the CV curves obtained here with the theoretical model led to the conclusion that applying the polarisation on a pre-established biofilm formed at open circuit induced two successive development phases: the EA cells present in the biofilm firstly turned their metabolism to the anode-respiring pathway and then they developed the extracellular ET network in a second phase.

At the end of the 3-day polarisation, the biofilms (final ages 4, 8, 12, 15 and 18 days) were imaged by scanning electron microscopy (SEM). For each microbial electrode, the surface of the weft of the woven carbon cloth was always visible at low magnification (Fig. E1A to E1E). The surfaces exhibited poor colonisation by scattered bacterial colonies. The lower magnification showed visible coating only with the 18-day old biofilm (Fig. E1E), which was consistent with the currents obtained during 3-day polarisation. Significant currents started to be obtained with the 18-day biofilm (final age), while no significant current was provided by the younger biofilms (Fig. 2A). Higher magnification showed that the microbial colonies were locally more important on biofilms aged of more than 8 days. Cells with flagella were observed in 12and 15-day old biofilms (Fig. E1C-D). Planktonic cells use flagella to move in solution, to approach solid surfaces and to fix onto them but the flagella disappear rapidly when the cells are embedded into a biofilm. The presence of flagella observed here revealed an early stage of biofilm formation [START_REF] Monroe | Looking for chinks in the armor of bacterial biofilms[END_REF]. As discussed above, these biofilms were at the crossroads of their development. The 3 days of polarisation had not yet erased the differences in colonisation that resulted from the different open circuit durations, and the EA bacteria that were able to multiply during the 3 days of polarisation were not yet predominant enough to mask the biofilm development by the uptake of planktonic cells with flagella.

''Delayed polarisation'' vs. conventional ''full polarisation''

The 22-day-old biofilm, which supplied 2.7 A/m 2 after the 3 days' polarisation, continued to be polarised for a total of 20 days. When the current dropped off because of acetate depletion, 10 mM acetate was added and the current rapidly increased again. A current density of 9.4 A/m 2 was reached at day 28, i.e. after only 9 days of polarisation (Fig. 3A, biofilm 1). The 3rd acetate addition confirmed an identical maximum current density. A replicate with a first period of 20 days at open circuit gave a maximum current density of 9.4 A/m 2 from the first current peak, i.e. after only 3 days of polarisation (Fig. 3A, biofilm 2). These biofilms were said to be obtained by ''delayed polarisation''. This new strategy was attempted here with the objective of producing high performance microbial anodes. It consisted of keeping the working electrode at open circuit for several days (here 19-20 days) before applying polarisation at À0.2 V vs. SCE.

In parallel, microbial anodes were developed following the conventional ''full polarisation'' procedure, which consists of polarising the electrode at À0.2 V vs. SCE as soon as it is immersed in the compost leachate. The current, which was initially nil, started to increase after several days due to the formation of the EA biofilm. The successive additions of 10 mM acetate improved the current (Fig. 3B, biofilm 3). A maximum current density of 6.0 A/m 2 was observed at the 4th acetate addition, i.e. after 36 days of polarisation. This experiment was duplicated (Fig. 3B, biofilm 4) and gave 8 A/m 2 after 35 days of polarisation and four acetate additions.

A preliminary conclusion is that delayed polarisation allowed maximum current density up to 9.4 A/m 2 to be reached after only 3 days of polarisation, while conventional full polarisation required 35 days of continuous polarisation to obtain 6-8 A/m 2 . Waiting several days at open circuit before applying the potential had a positive effect on the performance of the microbial anode. The increase in current density was not high, but the decrease in the required polarisation duration was drastic.

3.4. Catalytic (i.e. in the presence of acetate) and non-turnover (i.e. in acetate depleted conditions) cyclic voltammetry of biofilms prepared by delayed and full polarisation

During the experiments described in Fig. 3A and B the polarisation was interrupted from time to time to record cyclic voltammetry (CV) curves at different steps of biofilm development. Catalytic CVs were plotted when the electrode provided maximum current density, days 22 and 35 for the biofilm obtained by delayed polarisation (Fig. 4A) and days 12, 30 and 36 for the biofilm obtained by full polarisation (Fig. 4B). Once again, the current densities measured at À0.2 V vs. SCE on the CV curves were identical to the values recorded during polarisation, which means that CV gave a correct representation of the stationary behaviour of the electrodes. The anodes showed excellent electrochemical characteristics, with low OCP around À0.50 V vs. SCE and high current densities. The higher current densities provided by the microbial anodes formed by delayed polarisation were confirmed.

All CVs recorded on the full-polarisation biofilm exhibited a conventional sigmoid shape, similar to those already reported in the literature, for instance for Geobacter sulfurreducens biofilms [START_REF] Fricke | On the use of cyclic voltammetry for the study of anodic electron transfer in microbial fuel cells[END_REF] or for microbial anodes obtained from domestic wastewater [START_REF] Liu | The study of electrochemically active microbial biofilms on different carbon-based anode materials in microbial fuel cells[END_REF]. These biofilms did not show the peak system characteristic of the step iii) rate-limiting effect. CVs did consequently not detect a rate-limitation by electron transfer from the reduced cells to the ET mediator(s). Under constant polarisation the EA cells grew by using the electrode as final electron acceptor and they consequently developed concomitantly with their growth an extracellular ET network that perfectly matches their needs. In contrast, when applying polarisation to a preestablished biofilm formed by 19 days at open circuit, CVs showed a superimposed oxidation peak that indicated a step (iii) rate limitation. The superimposed oxidation peak was observed after 3 days of polarisation (Fig. 4A, day 22) and was less marked but still present after 13 more days of polarisation (Fig. 4A, day 35). The rate-limiting effect of electron transfer from the microbial cells to the ET network slightly diminished during polarisation, but it durably marked microbial anodes obtained by the delayed polarisation procedure.

Non-turnover CVs were recorded in acetate-depleted conditions to gain information about the redox species contained in the biofilms. Actually a small amount of acetate was still present in solution and weak catalytic currents were always visible on the CV curves. Nevertheless, the small currents due to the catalytic oxidation of acetate did no longer mask the currents due to the single turnover oxidation and reduction of the redox species of the biofilm. During the delayed polarisation procedure, the non-turnover CVs recorded just at the end of the open circuit phase (Fig. 5A -day 19) showed the absence of any significant redox couple. In contrast, after 20 days of polarisation the biofilm exhibited multiple redox systems (Fig. 5A -day 39): two clear reduction peaks and three barely defined oxidation peaks were detected, which gave redox systems with midpoint potentials close to À0.24 and À0.15 V vs. SHE. Similar patterns have already been reported in the literature for non-turnover CVs, even pure cultures have revealed complex behaviour with multiple redox systems [START_REF] Fricke | On the use of cyclic voltammetry for the study of anodic electron transfer in microbial fuel cells[END_REF]. For instance, CV at 1 mV/s on Geobacter sulfurreducens biofilm formed on graphite electrode shown four redox systems with potential midpoints at À0.32, À0.18, À0.10 and +0.25 V vs. SHE [START_REF] Strycharz | Application of cyclic voltammetry to investigate enhanced catalytic current generation by biofilm-modified anodes of Geobacter sulfurreducens strain DL1 vs. variant strain KN400[END_REF]. It would not make sense to compare CVs performed in different solutions, with different electrode materials and different microbial cultures, but the potential range in which the redox systems were observed here remains close to the value reported for Geobacter sulfurreducens. Clearly, the non-turnover CVs indicated that the biofilm gained rich redox content during the polarisation time. The 20-day polarisation enriched the biofilm in redox species remarkably. Nevertheless, the catalytic CVs performed just before acetate depletion (Fig. 4A, day 35) showed a remaining rate-limitation by electron transfer from the cells to the ET network. It must be concluded that the ET network developed during delayed polarisation was composed of multiple redox systems that did not perfectly match the requirements of the cells.

For comparison, biofilm 3 developed under 40 days of full polarisation showed only two redox systems, the midpoint potential of one being around À0.13 V vs. SHE (Fig. 5B) and the currents were very much lower than those recorded with the delayed-polarisation biofilm of the same final age (19 days open circuit +20 days polarisation, Fig. 5A). The charge exchanged, which is proportional to the concentration of the redox species involved in the redox reaction, was drastically lower. The biofilm formed by 40 full days of polarisation showed, at the same final age, less intense electron transfer capabilities than the biofilm formed by delayed polarisation, but no limiting effect due to step (iii). This difference shows that the ET network was less rich for the biofilms formed under full polarisation but better suited to the EA cells that formed the biofilm.

Biofilms formed by delayed polarisation provided high current densities (up to 9.4 A/m 2 ) using an abundant ET network that was not optimally tuned to the microbial cells making up the biofilm, while the biofilm formed by the conventional full polarisation gave slightly lower current density (6-8 A/m 2 ) by using a less rich ET network well-suited to the microbial cells. Polarisation applied to a pre-established biofilm favours the development of different microbial species that develop different ET strategies. Nevertheless, the greater diversity does not ensure an optimal link between microbial cells and mediators. Applying the potential from the beginning of biofilm formation results in better tuned EA biofilms, but which provide lower current density.

SEM imaging of biofilms prepared by delayed and full polarisation

At the end of the 19 days' open circuit and 20 days' polarisation, the biofilm prepared under delayed polarisation showed a heterogeneous structure with clumps of bacteria but also many isolated single cells (Fig. E2A in Electronic Annex). The carbon fibres that made up the cloth electrode were still easily visible. Contrarily, the biofilm prepared under 40 days' full polarisation fully masked the fibre structure of the electrode, which was no longer visible (Fig. E2B in Electronic Annex). The biofilm was thick, uniform and covered the whole electrode surface area. Higher magnification confirmed its compactness.

SEM images showed that full polarisation drove the formation of a more compact and uniform biofilm than delayed polarisation. The biofilms obtained by delayed polarisation presented a globally thinner structure with heterogeneous coating. It can be thought that during the initial 19 days at open circuit non-EA bacteria settled the electrode surface and subsequently these bacteria hindered the access of EA bacteria to the electrode surface. The presence of non-EA bacteria resulted in a less dense and compact biofilm structure that gave higher current density. A mixed biofilm composted of EA and non-EA bacteria would thus be more efficient because of a more appropriate morphology.

Final scenarios

These differences in biofilm structures between delayed and full polarisation complete the assumptions derived from the electrochemical analyses. Polarising from the beginning favoured the growth of sessile EA cells that were able to use the electrode as final electron acceptor. They grew fast, formed a compact biofilm with an ET network that closely matched their need. The compact structure that was evidenced by SEM suggested that mass transfer of substrate and products inside the biofilm could become a ratelimiting step for these electrodes. For instance, it is known that slow extraction of protons produced by substrate oxidation can limit the current provided by microbial anodes [START_REF] Torres | Proton transport inside the biofilm limits electrical current generation by anode-respiring bacteria[END_REF]. The theoretical model discussed above [START_REF] Strycharz | Application of cyclic voltammetry to investigate enhanced catalytic current generation by biofilm-modified anodes of Geobacter sulfurreducens strain DL1 vs. variant strain KN400[END_REF] has demonstrated that, in case of mass transfer rate-limitation, CV curves exhibit a purely sigmoid shape. The assumption of mass transfer rate-limitation is consequently consistent with the CV curves recorded here with the full-polarisation biofilms (Fig. 4B).

In the absence of polarisation, the microbial development led to heterogeneously scattered colonies, which were far from forming complete coverage of the surface. Both potentially-EA cells and non-EA cells grew in the absence of any significant electrochemical reaction, except the very low currents that control the OCP value. Open-circuit biofilms resulted from the slow multiplication of the sessile cells and they could also benefit from the integration of planktonic cells. Applying the polarisation to such pre-established biofilms made the potentially EA-bacteria shift rapidly to anode-respiring metabolism and grew by using the electrode as electron acceptor. The ET network contained multiple redox systems but was undersized with respect to the number of cells that rapidly turned towards the anode-respiring metabolism. The ET network then developed during polarisation but the multiple redox systems did not optimally match the cell requirements, electron transfer from the cells to the mediators was rate limiting. The structure of the biofilm remained deeply marked by the structure of the initially open-circuited biofilm, probably because the development of the EA cells was hindered by the presence of well-settled non-EA cells.

The delayed-polarisation biofilms provided slightly higher current densities than biofilms formed under full polarisation. The better performance may be due to their less compact structure, which did not limit mass transfers inside them. It has already been observed that small microbial scattered colonies on a cathode surface provide higher currents than biofilms formed by larger colonies [START_REF] Pons | Effect of surface roughness, biofilm coverage and biofilm structure on the electrochemical efficiency of microbial cathodes[END_REF]. Moreover, the full polarisation biofilms made a uniform layer that completely masked the fibres of the cloth electrodes, while delayed polarisation led to microbial settlement around the fibres. A recent study [START_REF] Pocaznoi | Ultra microelectrodes increase the current density provided by electroactive biofilms by improving their electron transport ability[END_REF] shown that biofilms formed around ultra-microelectrodes (diameter less than 50 lm) give higher current density than biofilms formed on conventional macro-sized electrodes. This positive effect has been attributed to the densification of the electron transfer network due to the particular properties of ultramicroelectrodes [START_REF] Bard | Electrochemical Methods[END_REF]. Such an ultramicroelectrode effect could also explain the high current density that has been recently reported with fibre electrodes [START_REF] Chen | Electrospun and solution blown three-dimensional carbon fiber nonwovens for application as electrodes in microbial fuel cells[END_REF][START_REF] He | Effect of fiber diameter on the behavior of biofilm and anodic performance of fiber electrodes in microbial fuel cells[END_REF][START_REF] Wei | Recent progress in electrodes for microbial fuel cells[END_REF]. Here the fibres of the cloth electrode were around 8 lm in diameter. The biofilms formed under delayed polarisation may have benefited from an ultra-microelectrode effect when they formed around the fibres and kept a micro-structure. In contrast, the thick uniform biofilm prepared by full polarisation was not able of exploiting this positive effect. The two basic explanations (mass transfer limitation and possible ultra-microelectrode effect) converge to identify the biofilm structure as the cause of the higher currents provided by the delayed-polarisation biofilms. The rare studies that have addressed the relationship between the electrochemical performance of a microbial anode and the spatial structure of the biofilm have opened promising tracks. For instance, it has been demonstrated that co-cultures of gram-positive and gramnegative bacteria showed synergistic or mutualistic effect, which corresponded to particular spatial organisation of the mixed biofilms [START_REF] Read | Initial development and structure of biofilms on microbial fuel cell anodes[END_REF]. The co-cultures have resulted in currents two times higher than the single cultures. Controlling biofilm structure to improve the current of microbial anodes should deserve more attention in the future.

This work confirmed the occurrence of an adaptation phase necessary for the cells to develop their EA capacity in response to polarisation as evoked in the introduction section. It also showed the short-time required for the potentially-EA cells to shift to anode-respiring metabolism and distinguished this process from the development of the ET network, which can be longer when polarisation is applied to already formed biofilms.

Conclusions

Waiting several days at open circuit before applying polarisation allowed the polarisation duration to be drastically reduced to reach similar current densities. The delayed polarisation gave current density of 9.4 A/m 2 after only 3-9 days of polarisation, while conventional full polarisation required 36 days of continuous polarisation to obtain 6-8 A/m 2 . For the first time, this work has shown that applying the polarisation to an established biofilm formed at open circuit may be a promising way to improve the performance of microbial anodes prepared in a natural environment.

Fig. 1 .

 1 Fig. 1. Biofilms formed at open circuit. (A) Evolution of open circuit potential (OCP) of carbon cloth electrodes immersed in compost leachate for 8, 12, 15, and 19 days. (B) Current densities obtained during 3 h polarisation at À0.2 V vs. SCE on the 8-, 12-, 15-and 19-day old biofilms.

Fig. 2 .

 2 Fig. 2. Biofilms formed at open circuit followed by 3 days of polarisation at À0.2 V vs. SCE. (A) Current densities obtained during 3 days of polarisation on biofilms formed at open circuit. The final ages 4, 12, 15, 18 and 22 days given on the figure include the 3 days of polarisation. For clarity, the current provided by the 8-day old biofilm located between 4-and 12-day old biofilms have not been plotted. (B) Cyclic voltammograms (1 mV s À1 ) recorded at the end of the 3-day polarisation.

Fig. 3 .

 3 Fig. 3. Current densities under polarisation at À0.2 V vs. SCE. (A) Delayed polarisation after 19 or 20 days let at open circuit, (B) Conventional full polarisation.

Fig. 4 .

 4 Fig. 4. Cyclic voltammograms (1 mV s À1 ) recorded at different days around maximal current production on: (A) biofilm formed by delayed polarisation (Fig. 3A, Biofilm 1), (B) biofilm formed by full polarisation (Fig. 3B, Biofilm 3). Days of CV recording are indicated on the figures.

Fig. 5 .

 5 Fig. 5. Cyclic voltammograms (1 mV s À1 ) recorded in acetate depleted conditions on (A) biofilm formed by delayed polarisation (Fig. 3A, Biofilm 1), (B) biofilm formed by full polarisation (Fig. 3B, Biofilm 3). Days of CV recording are indicated on the figures.

Acknowledgements

This work was part of the ''Agri-Elec (ANR-08-BioE-001)'' project supported by the Bio-Energies programme of the French ANR. The authors thank Marie-Line de Solan for SEM imaging, Luc Etcheverry for technical support and Amandine Calmet for experimental help.

Appendix A. Supplementary data

Supplementary data associated with this article can be found, in the online version, at doi:10.1016/j.biortech.2012.03.042.


D Duhamel
email: denis.duhamel@enpc.fr

R Meftah

J Cesbron

H.-P Yin

A fast algorithm for computing dynamic tyre road contact forces

Tire/road contact is the principal source of car noise at speeds greater than 50 km/h. In this context, we have developed a new approach for modelling the tire vibrations and the contact with the rigid road surfaces during rolling. For the tire, a periodic model is used to compute Green's functions. The response of the tire can thus be modelled over a large frequency range. Then a fast convolution and contact model is developed and examples of computations of contact forces are given for real road textures. Spectra of forces for different tire velocities are also computed.

Introduction

The computation of tire road noise needs first a model for the tire vibration and then a method for computing contact forces between a tire and a road. For the tire vibrations, the simplest approach is the circular ring model as in [START_REF] Huang | Response of rotating rings to harmonic and periodic loading and comparison with the inverted problem[END_REF]. However for complex geometrical or material properties of the tire a finite element model is much more appropriate. To avoid the heavy three-dimensional computations of [START_REF] Brinkmeier | A finite element approach for the simulation of tire rolling noise[END_REF], several efficient models have been proposed such as the wave finite element approach in [START_REF] Waki | Free and forced vibrations of a tyre using a wave/finite element approach[END_REF] or the recursive method presented in [START_REF] Duhamel | A recursive approach for the finite element computation of waveguides[END_REF][START_REF] Duhamel | A recursive finite element method for computing tyre vibrations[END_REF].

Here the dynamic response of the tire is calculated by convolution of the contact forces with the Green's functions of the tire. For orthotropic plates such Green's functions were analytically found in [6], but here they are found from the recursive model [START_REF] Duhamel | A recursive approach for the finite element computation of waveguides[END_REF]. However the computation of the convolution can be time consuming. In this work we have used a new method. First it consists in the modal expansion of the pre-calculated Green's functions. The modal parameters are then used to construct a new convolution which allows quicker calculations than the traditional convolution. The modal convolution is adapted to dynamic contact problems by using a kinematic contact condition. The outline of the paper is thus the following. In section 2, the tire model is first presented. Then in section 3, the contact model, including the fast convolution and the kinematic contact condition is described. Finally, section 4 gives numerical results of displacements and contact forces for two road textures.

Tire model

Tire section

The first step is to have a model for the vibrations of the tire. Here a periodic model has been developed. It consists in modelling a short cell of the tire as in Figure 1 and using calculations on this cell for computing Green's functions as described below. Stiffness and mass matrices of a cell are obtained from commercial finite element software. In a first step they are obtained in a cartesian coordinate system and then they are transformed in a cylindrical coordinate system in which the whole structure is periodic.

The tire is also inflated with an internal pressure P. So its vibrations are considered as a small perturbation of the prestressed static state shown in Figure 1. This prestress generates an additional stiffness matrix denoted K P . So, the full dynamic stiffness matrix is given by:

D(ω) = K + K P + jωC -ω 2 M (1)
The tire studied here is of type Michelin 165/65/R13 77T. Its geometric properties are given in Table 1. The mechanical properties of the different parts of the tire are given in Table 2.

Equivalent matrix

The aim of the periodic model is to built the global dynamic stiffness matrix of the structure from the dynamic stiffness matrix of a single period. It is obtained by recursively eliminating the internal degrees of freedom between adjacent cells. Consider the dynamic stiffness matrices D 1 and D 2 of two neighbouring cells:

D 1 = ⎡ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎣ D 1 LL D 1 LR D 1 RL D 1 RR ⎤ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎦ ; D 2 = ⎡ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎣ D 2 LL D 2 LR D 2 RL D 2 RR ⎤ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎦ (2)
The equivalent matrix of the two cells structure is obtained by eliminating the internal degrees of freedom by:

D eq = ⎡ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎣ D 1 LL -D 1 LR D * D 1 RL -D 1 LR D * D 2 LR -D 2 RL D * D 1 RL D 2 RR -D 2 RL D * D 2 LR ⎤ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎦ (3)
with:

D * = D 1 RR + D 2 LL -1
This operation is repeated n times with n such that:

N = n i=1 2 p i ; p 1 > p 2 ... > p n ( 4
)
with p i the position of the i th figure in the binary representation of the number N of cells in the tire.

Green's functions

Consider the domain Ω of the tire. It can be separated into two subdomains Ω l et Ω c . The number of cells in the domain Ω c where the contact occurs, is denoted by N c . The other free part Ω l of the tire has N l cells, see Figures 2 and3 The dynamic stiffness matrix of domain Ω l , denoted D eq , is computed by the method presented in section 2.2. Then the full dynamic stiffness matrix of the tire is computed by a standard finite element assembling between D eq and the matrices of the N c cells of Ω c , see Figure 3 and Eq. ( 5). The matrix of Green's functions is obtained by solving a linear system with Eq. ( 5) and different load cases associated to different points in the contact zone. The number of load cases is limited to the number of dofs in a section of the tire. 3 Contact model

⎡ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎣ D 11 +
⎤ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎦ D T (5)

Fast convolution

The computation of the response of the tire by a standard convolution requires a large number of coefficients. Here we try to reduce the computing time by simplifying the Green's function which can be approximated by a linear combination of modes (not necessarily the true modes) as:

G(ω) = k=N m k=1 A k -ω 2 + 2 jξ k ωω k + ω 2 k (6)
Knowing G(ω) by a finite element model or by measurements, we must identify the residues A k , the dampings ξ k and the resonance frequencies ω k . There are several methods to solve this problem. In this study the LSCE (Least Squares Complex Exponential) is used.

The Green's function of the tire is first computed with the periodic model, then the modal parameters are identified by the precedent method. For each coefficient of the Green's matrix an optimal number of coefficient N m is chosen to get the best approximation. The error is low, generally below 5%. In Figure 4, a Green's function and its approximation are presented for the coefficient with the maximal error (6.5%). One can see that the approximation is very good. By taking the inverse Fourrier transform, the Green's function in the time domain can be found by:

g(t) = k=N m k=1 A k ω d k e -ξ k ω k t sin(ω d k t)H(t) ( 7 )
with:

ω k d = ω k 1 -ξ 2 k
The displacement u(t) is obtained from the contact force q(t) by the convolution:

u(t) = t 0 g(τ)q(t -τ)dτ = t 0 g(t -τ)q(τ)dτ (8)
Inserting the expression (7) for g(t) in Eq. (8) yields:

u(t) = t 0 k=N m k=1 A k ω d k e -ξ k ω k (t-τ) sin ω d k (t -τ) q(τ)dτ (9)
Separating the t and τ variables and rearranging, the displacement can be written as:

u(t) = k=N m k=1 A k ω d k e -ξ k ω k t sin ω d k t α k (t) -cos ω d k t β k (t)
(10) where α k (t) and β k (t) are computed by:

α k (t) = t 0 e ξ k ω k τ cos(ω d k τ)q(τ)dτ β k (t) = t 0 e ξ k ω k τ sin(ω d k τ)q(τ)dτ (11)
The parameters α k (t + Δt) and β k (t + Δt) can be computed by the discrete versions of Eq. (11) as:

α k ((n + 1)Δt) = α k (nΔt) + e ξ k ω k nΔt cos(ω d k nΔt)q(nΔt)Δt β k ((n + 1)Δt) = β k (nΔt) + e ξ k ω k nΔt sin(ω d k nΔt)q(nΔt)Δt (12)

Kinematic contact conditions

When there is no contact, the contact force equals zero and the displacement can be computed by the fast convolution. When there is contact, conditions must be written to find the contact force. We propose here to write two conditions, one for the displacement and the other for the velocity.

Eq. ( 8) can be separated into a term depending on the past history of forces u h (t) and another term depending only on the present time step:

u(t) = t-Δt 0 g(t -τ)q(τ)dτ u h (t) + Δt 0 g(τ)q(t -τ)dτ (13)
In the same way taking the derivative of Eq. ( 13) leads to an equation in term of the velocity:

v(t) = t-Δt 0 g (t -τ)q(τ)dτ v h (t) + Δt 0 g (τ)q(t -τ)dτ (14) Denoting Y = [u(t) v(t)] T and Y h = [u h (t) v h (t)] T leads to: Y = Y h + Ψ(q) ( 15
)
where Ψ is an integral operator giving the influence of the contact force at present time on the displacement and the velocity. So the contact conditions are:

Y = Y r = [u r (t) du r (t) dt ] T (16)
where u r (t) and du r (t) dt are the position of the road and its velocity as seen in the tire reference system. Using the modal decompositions for the displacement and the velocity yields:

u(t) = k=N k=1 A k ω d k e -ξ k ω k t sin ω d k t α k (t) -cos ω d k t β k (t) (17)
and

v(t) = - k=N k=1 A k ξ k ω k ω d k e -ξ k ω k t sin ω d k t α k (t) -cos ω d k t β k (t) + k=N k=1 A k e -ξ k ω k t cos ω d k t α k (t) + sin ω d k t β k (t) (18)
The u h (t) and v h (t) values are obtained from Eq. ( 17) and (18) by computing α and β with q = 0 at the present time. The real value of this force q(t) at present time is such that:

ΔY = Y r -Y h = ⎡ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎣ Δt 0 g(τ)q(t -τ)dτ Δt 0 g (τ)q(t -τ)dτ ⎤ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎦
The integrals can be computed by Gauss quadratures with two points. The values of the forces at these two Gauss points are obtained by:

q = q 1 q 2 = Ψ -1 (t 1 , t 2 )ΔY (19)
with Ψ defined by:

Ψ = ⎡ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎣ g(t 1 ) g(t 2 ) g (t 1 ) g (t 2 ) ⎤ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎦ Δt 2 (20)
and

t 1 = t + 1 - 1 √ (3)
Δt 2

t 2 = t + 1 + 1 √ (3) Δt 2 (21)
From the knowledge of the contact forces at times t 1 and t 2 , the parameters α k (t + Δt) and β k (t + Δt) can be computed by Eq. ( 12). This method can be easily generalised for a surface with several contact points. In this case the number of contact points can change with time. The contact occurs when u h (t) ≤ u r (t) for each point in the contact zone. Then the generalization of Eq. ( 16) for the points where the contact happens allows to determine the contact forces at these points.

4 Road contact

Road texture

We assume that the roads are perfectly rigid and that the contact area is constant with time. We consider two road textures obtained during the French-German project DEUFRAKO P2RN. The measured area is L = 2m long and b = 0.35m width with a sampling of dx = dy = 384 μm. We want to compute the displacements and forces in the contact zones. The Green's functions of the tire are computed as in section 2 in the frequency range [0 4000 Hz]. The contact zone is changing as the tire is moving during the rolling process. The contact points are moving in the fixed coordinate system as:

x = x 0 + V 0 t y = y 0 z = u r (x, y) (22)
where (x 0 , y 0 , z 0 ) are the coordinates in the system moving at constant velocity V 0 with the tire. The maximal contact area is constant with time while the real contact area and the number of contact points can change.

Numerical results

All the simulations are made for a contact length L c = 6 cm and a width l c = 8 cm. The number of points is N x = 10 along X and N y = 12 along Y. The tire is rolling over a length of L = 2m. The tread is discretized with steps of dX ≈ dY ≈ 5 mm with an interpolation of the tire height between two tread points. Figures 6 and7 present the displacements and forces for the two road surfaces of Figure 5. The displacements have shapes similar to road textures. Losses of contact and high forces are seen at the maximal heights of asperities. Road (A) generates higher forces than road (B).

The force level, denoted L f and computed in decibels relatively to a reference value of F 0 c = 10 -4 N, is obtained by:

L f = 20 log 10 |F c (ω)| F 0 c ( 23
)
Figures 8 and9 present the third octave force spectra for roads (A) and (B) and for different velocities. When the velocity increases the spectra are shifted towards higher frequencies and the maximal level is also increased. The force

Conclusion

The periodic tire model allows to compute tire vibrations in a contact zone of size 6×8 cm 2 with 120 points over a large frequency range. The displacements and forces are obtained for a road length of L = 2m and for two road surfaces. Results show that the force levels are highly dependant on the texture levels and the tire velocities. Increasing the tire velocity clearly shifts the force levels towards higher frequencies and increases the global level. Force levels are also significant between 500 Hz and 5000 Hz.

Figure 1 :

 1 Figure 1: Section of the tire and displacements for an inflation pressure of 2 bars.

  .

Figure 2 :

 2 Figure 2: Contact zone with the road.

Figure 3 :

 3 Figure 3: Dofs of the global matrix.

Figure 4 :

 4 Figure 4: Comparison between a Green's functionand its approximation -+-in the least favourable case.

  Figure 5 presents the samples of two different roads of sizes 0.1 m by 0.1 m, see [7] for other examples.

Figure 5 :

 5 Figure 5: 3D texture of the two roads: (A) upper figure and (B) lower figure.

Figure 6 :

 6 Figure 6: Displacements and forces for road (A) and for points such that x 0 = 0 with V 0 = 90 km/h.

Figure 7 :

 7 Figure 7: Displacements and forces for road (B) and for points such that x 0 = 0 with V 0 = 90 km/h.

Table 1 :

 1 Properties of tire Michelin 165/65/R13 77T.

	Part	Material	Property	Value
	Tread pattern	Rubber	ρ E ν	1000 kg/m 3 7 MPa 0,49
			ρ	7850 kg/m 3
	Bead	Steel	E	162, 6 GPa
			ν	0,33
		Rubber	ρ	1000 kg/m 3
	Sidewall	+nylon belt	E	109 MPa
			ν	0, 48
			ρ	2014 kg/m 3
			E r	663 MPa
	Tread	Rubber	E x	624 MPa
		+steel belt	ν ry	0,4
			G ry	330 MPa

Table 2 :

 2 Mechanical properties of the tire.

[6] J. F. Hamet. Tire/road noise: time domain green's function for the orthotropic plate model. Acta acoustica united with Acustica, 87:470-474, 2001.

[7] Prediction and propagation of rolling noise. Technical report, Deufrako P2RN project, March 2009.

[8] R. Meftah. Une approche par formalisme de Green réduit pour le calcul des structures en contact dynamique: application au contact pneumatique chaussée. PhD thesis, Université Paris-Est, 2011.