Alex Reche

Ignacio Martin
email: ignacio.martin@udg.es

George Drettakis
email: alex.reche|george.drettakis@sophia.inria.fr

Volumetric Reconstruction and Interactive Rendering of Trees from Photographs

Keywords: CR Categories: I.3.7 [Computer Graphics]: Three-Dimensional Graphics and Realism 3D reconstruction, interactive rendering, visibility estimation

Figure 1: Our method captures and renders existing trees from photographs, by estimating opacity in a volume, then generating and displaying view-dependent textures attached to cells of the volume. (a) One of the original photographs of an oak. (b) The α mask used for the opacity estimation. Two cross slices of the resulting opacity are shown in (c). A synthetic image of the original view, using our view-dependent rendering, is shown in (d). Textures are attached to billboards in cells of the volume and are generated based on estimated opacity.

Introduction

Capturing real-world trees for subsequent rendering in virtual environments is an interesting and challenging task. Existing digital capture techniques such as laser range finders, stereo or modelling from images have been extensively developed for solid objects which have a well-defined opaque surface. Once the object is captured, standard computer graphics methods are used for rendering. Trees, and vegetation in general, are a special case. The complex geometric structure of leaves and branches means that traditional scanning methods cannot usually be applied. In particular capturing depth information of such objects is a very difficult task because of the high frequencies implied by the complex, small geometries of the leaves and twigs. Procedural models for trees can be guided by images [START_REF] Shlyakhter | Reconstructing 3D tree models from instrumented photographs[END_REF]], but result in models with very high polygon counts (hundreds of thousands or even millions of polygons per tree).

Our goals are i) to capture real trees from a small number of photographs, using a relatively simple and fast procedure, without the need for specialized equipment or setup; ii) to create a low polygon count tree model which permits realistic interactive renderings of the captured tree.

To achieve these goals we make a key observation: at a reasonable distance, each pixel in a photograph of a tree is typically the blended projection of a number of leaves/branches and the background. This can be seen as a transparency effect, in which the pixel value corresponds to a mixture of tree/leaf colors and background modulated by the opacity of the "tree volume" along the pyramid defined by the camera and the pixel.

Based on this observation, we adopt a volumetric model for the rendering of trees. We cast the problem in a direct volumetric rendering context [START_REF] Max | Rendering trees from precomputed Z-buffer views[END_REF]; we consider the tree as a volume, with opacity and color values. We estimate opacity based on a small set of calibrated digital photographs of a tree. We first estimate opacity of the tree volume, by optimizing over a recursive grid of opac-ity values. Our optimization uses alpha-mattes extracted from the photographs as estimates of cumulative opacity at the pixels (see Fig. 1(b)). Once the recursive grid of opacity values has been estimated, we assign a billboard to each grid cell. For each billboard, a view-dependent texture is generated for each view, using the original image, the number of billboards projected to the image and the opacity of each cell. These textures capture the high frequency detail and are rendered with a view-dependent texturing algorithm.

The main contributions of our approach are:

• The efficient estimation of the opacities for a tree volume on a recursive grid, using the alpha-mattes computed from a small set of calibrated images around a tree.

• The generation of view-dependent textures for each cell of the recursive grid, which allows high-quality view-dependent rendering of the resulting, low polygon tree model using billboards.

This entire process is efficient and compact, creates satisfactory reconstructions of trees, and is particularly suited to those with relatively sparse foliage (see Fig. 1), which are not well handled by previous methods.

Related Work

Modelling and rendering of trees has interested computer graphics researchers over the last decades. A large part of previous work concentrated on the generation and rendering of entirely synthetic trees based on procedural methods such as grammars (L-systems) (e.g., [START_REF] Prusinkiewicz | The algorithmic beauty of plants[END_REF][START_REF] Deussen | Realistic modeling and rendering of plant ecosystems[END_REF]]), or on rule-based plant growing systems based on codified botanical knowledge such as the AMAP system [START_REF] De Reffye | Plant models faithful to botanical structure and development[END_REF]]. Such approaches have been used to generate stunning images of forests and trees in general, with a high degree of realism. However, they do not capture the aspect of existing, real trees. The multi-layer z-buffer method uses precomputed synthetic images of trees for rendering [START_REF] Max | Rendering trees from precomputed Z-buffer views[END_REF][START_REF] Max | Hierarchical rendering of trees from precomputed multi-layer z-buffers[END_REF]. Volumetric texture approaches have been used to model and render trees; the complex geometry is represented as an approximation of the reflectance at a distance [START_REF] Neyret | Modeling animating and rendering complex scenes using volumetric textures[END_REF]]. An adaptation of this approach to hardware was developed later, using textured slices for interactive rendering [START_REF] Meyer | Interactive volumetric textures[END_REF]]. [START_REF] Meyer | Interactive rendering of trees with shading and shadows[END_REF], presented a hierarchical bidirectional texture solution for trees at different levels of detail, i.e., leaves, branches, up to the entire tree. This results in very efficient levelof-detail rendering for trees. Efficient rendering of trees can also be achieved using point-based methods [START_REF] Deussen | Interactive visualization of complex plant ecosystems[END_REF]. A more recent approach has been developed by [START_REF] Qin | Fast photo-realistic rendering of trees in daylight[END_REF], in which a volumetric approach effects an implicit level-of-detail mechanism, for lighting (both sun and sky) and shadowing, using shadow maps.

With the emergence of augmented reality applications, as well as the generation of virtual objects from real sources, the need for capture of existing trees has become more evident. A simple approach using two textures based on photos has been developed [START_REF] Katsumi | A display method of trees by using photo images[END_REF]; rendering is achieved using horizontal slices through the tree, the emphasis being on shading and shadowing. A different approach to capturing and rendering trees was presented by [START_REF] Shlyakhter | Reconstructing 3D tree models from instrumented photographs[END_REF]. This approach first creates a visual hull-like representation of the shape of the tree and then fits an L-system to the resulting model. The photographs are reprojected onto the resulting polygons of the L-system, resulting in very realistic representations of real trees, at the price of high polygon counts for the resulting models.

Image-based methods have also been developed which can handle objects with semi-transparent silhouettes. These include opacity hulls [START_REF] Matusik | Image-based 3D photography using opacity hulls[END_REF], surface light fields [START_REF] Wood | Surface light fields for 3D photography[END_REF]] and microfacet billboards [START_REF] Yamazaki | Microfacet billboarding[END_REF]. In all of the above cases, a large part of the object is opaque, defining an overall opaque geometric shape, which is recovered. This shape is required since these approaches use either pure standard "surface textures", or, in the case of microfacet billboards, require the underlying geometry to place and cull the billboards used.

In the approach presented here, we have been inspired by volume rendering methods. The rendering model we have adopted is based on the original direct volume rendering approaches (e.g., [START_REF] Blinn | Light reflection functions for simulation of clouds and dusty surfaces[END_REF][START_REF] Levoy | Display of surfaces from volume data[END_REF][START_REF] Drebin | Volume rendering[END_REF][START_REF] Max | Rendering trees from precomputed Z-buffer views[END_REF]). Although our method is closer to image-based rendering than volume rendering, our approach is related to polygon-rendering solutions for volumes (e.g., [START_REF] Westover | Footprint evaluation for volume rendering[END_REF][START_REF] Shirley | A polygonal approximation to direct scalar volume rendering[END_REF]).

Our opacity estimation approach is inspired by the approaches used in medical imaging. Our method has similarities to algebraic methods used for computed tomography, such as the SART algorithm (e.g., [START_REF] Andersen | Simultaneous algebraic reconstruction technique (SART): A superior implementation of the art algorithm[END_REF]). The construction of a voxel representation for the tree has similarities with the voxel coloring [START_REF] Seitz | Photorealistic scene reconstruction by voxel coloring[END_REF] or space carving [START_REF] Kutulakos | A theory of shape by space carving[END_REF] approaches. However, these approaches do not currently treat semi-transparent volumes such as those we construct for trees. The Roxel algorithm [START_REF] Bonet | Roxels: Responsibility weighted 3d volume reconstruction[END_REF] extends space carving to treat opacity using techniques for opacity estimation [START_REF] Szeliski | Stereo matching with transparency and matting[END_REF]. A related approach, using a hierarchy of cells for fast rendering of complex scenes was presented by [START_REF] Chamberlain | Faster rendering of complex environments using a spatial hierarchy[END_REF]]. Compared to medical imaging or the Roxel approaches, we need to represent high frequency detail with low storage cost, which we achieve using the recursive structure combined with the view-dependent texturing technique.

A Volumetric Rendering Approach for Trees

As mentioned in the introduction, we have chosen a volumetric rendering model to represent and render trees, given the fact that we are dealing with photographs containing many semi-transparent pixels.

Consider the tree shown in Fig. 2(a); we create a recursive grid enclosing the tree which is surrounded by the cameras. For a large number of pixels in these photographs, each pixel is semitransparent, and we estimate an alpha value corresponding to the cumulative opacity αp for each pixel (see Section 4). In typical volume rendering applications (e.g., [START_REF] Levoy | Display of surfaces from volume data[END_REF][START_REF] Drebin | Volume rendering[END_REF]), a sampled opacity field is given at vertices of a grid, typically coming from a scanning device (X-rays etc.). In our case, we will need to estimate the opacity in the grid, based on the alpha values extracted from the photographs. We assign the value α i to each cell i of the grid. We show how to do this in Section 5.

Given the opacity and color, we can adopt a standard volume rendering equation to generate images of our trees. Consider a ray emanating from a pixel p, which traverses n grid cells which have opacity values α i (see Fig. 2). For now, we assume that for a given pixel we have assigned a color c i for each cell. The intensity Figure 3: Three photographs of typical trees we captured using our method. In each photograph the background color is significantly different from the colors of the leaves, trunk and branches.

I at a pixel is defined using standard volume rendering equations (e.g., [START_REF] Levoy | Display of surfaces from volume data[END_REF]):

I = n ∑ i=0 α i c i Π n m=i+1 (1 -αm) (1)
which expands to the standard compositing equation for rendering:

I = αncn + (1 -αn)(α n-1 c n-1 + (1 -α n-1 )(..(1 -α 1 )α 0 c 0 )..)
(2) To render the tree volume, we will develop a rendering algorithm which approximates Eq. 2. We first need to estimate the α i values, and we then need to approximate the color.

In reality, both the opacity and color values are anisotropic and inhomogeneous; estimating and storing them accurately would clearly be intractable, except in the simplest cases. We choose the following simplifications: we will estimate inhomogeneous but isotropic discrete opacity values defined on a recursive grid. For color, we will not perform an estimation, but we will partially preserve the anisotropic quality of the color by using a view-dependent texturing approach, with textures generated based on the opacities and the original photographs of the tree (see Section 6). We use billboards centered at the cells for the actual rendering.

Our capture method has three main steps. The first step is image capture and alpha matting. In the second step, these alpha values are used to estimate the opacity values in a grid. In the third step, we used estimated opacities to generate billboards for each cell and each image. Rendering is achieved with view-dependent texturing on the billboards to efficiently display the trees. These three steps are described in detail in the following sections.

Image Capture and Alpha Matting

The first step in our algorithm requires photographing the tree and generating the alpha maps. The tree chosen for reconstruction currently needs to be in a suitable position so that it can be photographed with a relatively distinct background (see for example Fig. 3, in which we can photograph the tree in a full circle with a sky background). Trees in urban environments often have this property, at least for the majority of views.

Photographs are then taken while moving around the tree. Our experiments have shown that approximately 20-30 photographs are required. We then need to calibrate the cameras of these photos. We accomplish this step using REALVIZ ImageModeler (www.realviz.com), but any standard algorithm can be applied for this step [START_REF] Faugeras | Three-Dimensional Computer Vision: A Geometric Viewpoint[END_REF]]. The calibrated cameras will be used in subsequent steps. By adding a few markers in the scene (we use sticks with colored play-doh on the top), calibration takes less than 10 minutes for about 20 images.

Next, we extract alpha masks for each photograph, using the algorithm of Ruzon and Tomasi [START_REF] Ruzon | Alpha estimation in natural images[END_REF]. This algorithm requires user intervention, in which zones of background and foreground are specified. Consider for example the tree shown in Fig. 4. The user specifies foreground and background, and we can see that the alpha-mask algorithm succeeds in finding semitransparent regions in the image. The area of the pixel contains a mix of leaves/branches and background. The alpha-mask calculates this visibility coverage using colors. Alpha-masks of 0 correspond to background regions and alpha-masks of 1 to completely opaque regions.

The intuition behind the alpha-masking approach is simple. The pixels in the image are transformed into LAB color space and clustered by color distribution. For each pixel, its color can be seen as a best fit interpolation between the distributions of the clusters for the foreground and background colors. The value of this interpolant is the alpha value of the pixel

We thus consider that for pixels with an alpha mask strictly between 0 and 1, the color of the pixel Cp is a linear interpolation in LAB color space of the background color C b and the foreground color C f :

Cp = αpC f + (1 -αp)C b (3)
C f and C b are computed as weighted sums of background and foreground, and perturbed accordingly. We create an alpha-image containing the values αp for each pixel and an image of "pure foreground" C f values used later for rendering (see Section 6).

Reconstruction

To achieve volumetric rendering of trees, we need to estimate opacities in each grid cell. We clearly do not have enough information inside the volume to be able to estimate both color and opacity, since we only have photographs without any depth information.

Even if the depth information were available, it could not be precise enough to be useful. For this reason, we will restrict estimation only to opacity, treating color in the rendering process as will be discussed in Section 6.

A complete iteration of the reconstruction process will loop through each pixel of each image. For each pixel, we cast the pyramid defined by the camera and the pixel square into the grid. The cells touched by this pyramid are treated. The algorithm performs an optimization step, trying to choose the best values for the opacities of these cells based on the corresponding opacity value αp of the pixel. Note that empty (transparent) cells are ignored for all steps of our approach.

Before the first iteration, we initialize the opacity values α i in each cell, by projecting each cell into each alpha-image, and using the minimum of the average opacity values in the respective images as the value of α i . Given that the images are the only data we have available, this minimum is the closest we can get to the final solution.

At each iteration, an initial opacity value α i (or transparency t i = 1 -α i ) is stored at each cell, together with a δ t i , which is initialized to 0 at each cell. We will use the δ t i values to accumulate the movement of transparencies due to the minimization for each pixel in each image. In particular, we accumulate intermediate transparency optimizations for each pixel and cell in δ t i , and update all cell transparency values simultaneously at the end of each iteration.

For each pixel of each image we approximate the pyramid by casting a ray through the grid. For each ray we collect the grid cells hit, with initial opacity values α i , i = 1...n. We experimented with a larger number of rays, but the resulting increase in accuracy did not justify the additional expense. Using the same reasoning as for the volume rendering equation (Eq. 2), and considering an absorption only model [START_REF] Max | Rendering trees from precomputed Z-buffer views[END_REF], we assume that the pixel opacity value αp should be:

αp = αn + (1 -αn)(α n-1 + (1 -α n-1 )(...(1 -α 1 )α 0 )..) (4)
where α i is the opacity in each cell i. If we recast Eq. 4 as a recursive function f n , we get:

f 0 = α 0
(5)

f n = αn + (1 -αn) f n-1 (6)
It can easily be seen by induction, that:

f n = 1 -Π n i=0 (1 -α i ) (7)
If we substitute t i = 1 -α i (which are the transparency values of the cell), we need to find the values t i which best fit the equation:

tp = Π n i=0 t i ( 8
)
where tp = 1 -αp. Clearly, we have an under-constrained problem, since we need to satisfy a system of equations ( 8). The number of these equations is equal to the number of pixels in all images.

Our goal is to obtain a best-fit solution for the t i values in the cells. One approach would be to use Eq. 8 directly with a standard iterative minimization technique such as a conjugate gradient method.

For reasons of efficiency however, we choose to transform Eq. 8 into a sum by taking logarithms:

logtp = log Π n i=0 t i = n ∑ i=0 logt i (9)
Eq. 9 can be seen as an n-dimensional plane, and desirable values for logt i should satisfy this plane equation. Interestingly, the logarithms have a physical interpretation. Transparency t(s) is defined as [START_REF] Max | Rendering trees from precomputed Z-buffer views[END_REF]]:

t(s) = e s 0 -τ(t)dt (10)
where τ is the extinction coefficient of the volume. If we approximate the integral using a Riemann sum at intervals ∆x, the discrete transparency t i can be defined as [START_REF] Max | Rendering trees from precomputed Z-buffer views[END_REF]:

t i = e -τ(i∆x)∆x (11) Q = (q 1 ,q 2 ...q n ) q p Q'= (q' 1 ,q' 2 ...q' n ) N=(1,1,...1)
Figure 5: Illustration of the projection step for the optimization of the t i (or respectively q i values). The illustration is in 2-D for simplicity, but is actually performed in N-d, where N is the number of cells intersected by the ray.

Taking the logarithms gives:

logt i = -τ(i∆x)∆x (12)
Thus the logt i values can be seen as a discrete approximation of the extinction coefficients. In what follows we use q i = logt i , where q i is the analog of the discrete extinction coefficient, and logtp = qp. We also define the vector Q = (q 1 , q 2 , ..., qn).

Recall that the goal is to find a best fit of the t i values for the cells for the given tp of the alpha image. The transformation via the logarithm allows us to perform this step by a direct projection onto the n-dimensional plane P, which has normal N = (1, 1, ...1) and with intercept qp on one of the axes (see Fig. 5). We can thus simply find the projection Q = (q 1 , q 2 ...q n ) of Q onto P.

We then revert to the space of transparencies by taking the exponent t i = e q i . We will weight this projection by the relative coverage of the ray and the voxels being considered. The exact calculation of the weight is illustrated in Appendix A. The weighting can be seen as a linear interpolation between the component values of Q and Q . Thus, for a given cell i, we have:

δ i = w i (t i -t i ) (13)
The stored δ t i value of the cell is then incremented with the δ i value, representing the optimization of t i due to this ray.

To complete an iteration we perform this estimation for each pixel of each image.

When the iteration is complete, for each cell we add the δ t i values, normalized by the sum w of the weights w i , into the transparency values t i to initialize them for the following iteration. We iterate until convergence, which is defined when the values of t i change less than a threshold in a single iteration. The result is an estimate of transparencies (and thus opacities) for each grid cell. We try and do a "best-fit" for all input images; this approach will tend towards a local minimum. Note that in practice we recover and store the transparency values t i from the estimated discrete extinction coefficients q i , passing through the exponential.

Finally, if t i becomes greater than a transparency cutoff threshold when adding in δ t i 's, we set t i to 1; the cell thus becomes transparent and is subsequently ignored. The reconstruction process is summarized as follows: A visualization of slices of opacity values are shown in Fig. 6. The process typically takes 3-5 minutes on the models we tested on a Pentium IV 2.7 Ghz PC, and 3-4 iterations are sufficient to achieve convergence.

Texture Generation and View-Dependent Rendering

At this stage, we have a recursive grid with opacity values which represents the tree. Rendering the tree is a complex task, since we want to preserve high-frequency information existing in the photographs, but at the same time we do not have any additional 3D information other than the low-frequency opacity estimate per cell.

Given our goal of low-polygon count for the final representation, we cannot subdivide the recursive grid too deeply, since this would lead to an explosion in the number of primitives required.

Our solution is to attach a billboard (a small polygon which is always oriented towards to viewer) to each cell. A naive approach to rendering would be to project a view-dependent texture from the input images onto each billboard, potentially blending between the n closest cameras, in the spirit of [START_REF] Debevec | Modeling and rendering architecture from photographs: A hybrid geometry-and image-based approach[END_REF] or the Unstructured Lumigraph [START_REF] Buehler | Unstructured lumigraph rendering[END_REF]]. Our tests with this approach gave severe blurring artifacts, since texture is repeated across the billboards corresponding to a given pixel (see Fig. 7). We present a heuristic solution where we use a billboard for each cell and we generate an appropriate texture for each image.

Generation of the billboard textures

We generate billboard textures in a preprocessing step by looping through input images and all cells. For each image i and for each cell c we construct an M × M billboard texture T . We typically set M = 8 or M = 4, which is a good compromise; smaller sizes would require higher subdivision. Note that we use the images containing the "pure foreground" values C f (Eq. 3). The intuition behind this process is illustrated with an artificial ideal case, shown in Fig. 8(a). Three cells in a row project onto a region of the image containing the three leaves. If all information were available, we could generate the three separate textures with each leaf, one for each cell. To do this, we would visit the cells front to back. For each cell, we would project the cell to the image, extract the texture, mask out only the part corresponding to this cell and assign this as a texture for the cell. We would then update the image and proceed to the following cell (Fig. 8(b)). The resulting billboards would avoid the blurring problem mentioned above.

In what follows, we use the term pixels for the values in the RGB and alpha images, and texels for pixels of the billboard textures. We project from billboard to image space and vice-versa using appropriate resampling for all values. We use a copy C i of the (RGBA) image since we modify pixel values.

For a given image and a given cell, we have estimated transparencies tc for each cell, and the αp (or transparency tp = 1 -αp) value for each pixel. We also compute the total number of billboards rendered at each pixel using the stencil buffer, and keep track of the remaining number Ncurr of cells not yet rendered as we process alpha image pixels.

We introduce a heuristic approximation to the ideal case given the minimal information at our disposal, i.e., alpha image pixel values, cell transparencies, and the current number of cells (or billboards) rendered at each pixel.

As in the ideal case, for each image, we render cells front-toback, and find the region R in the image corresponding to the projection of the cell. For each texel, we decide whether it should be selected using the corresponding image pixels. Our metric for selecting these texels is based on an appropriate comparison of cell and pixel transparencies. Our heuristic assumes that coherent pixel/cell transparencies indicate a higher probability that the pixels correspond to geometry in this cell. We will thus prefer pixels with cell/pixel values which are close according to the metric. To complete the method, we update the pixel color and transparency values after treating each cell.

To implement this approach we first create a quantity from the cell transparency tc which is comparable to the corresponding alpha-image tp values. This is done by raising tc to the power of Ncurr of billboards not yet rendered at this pixel. This approximates the influence of the current cell on the cumulative transparency of all cells projecting to this pixel: We note this value t Ncurr c . For each pixel we also store a value tcurr, which is initialized to tp.

For each texel we thus compute the importance, Ht , which gives higher values for texels with tcurr close to t Ncurr c :

Ht = 1 tcurr -t Ncurr c ( 14
)
To complete the approach we update the value of tcurr as follows: tcurr = tcurr/tc, thus "removing" the influence of the current cell as estimated previously using the power computation.

We store an age field with all pixels which is initially 0; recall that texels resample this value. Texels are ordered by age and importance, and the first αc * M * M texels are selected to be used on this billboard. For the remaining texels, the age of their corresponding pixels is incremented, thus increasing their chance of being selected later, and spreading out the choice of texels. Some pixels of the image may remain unselected, but this does not appear to cause significant artifacts.

As seen above, we base the number of texels selected for each billboard on the opacity of the cells. Initially, we tried a random choice of texels given this number, and the results were unsatisfactory. Use of these heuristics clearly improved the result.

The pixels used on the billboard are removed from the copy of the original image, and are filled by interpolating neighboring pixels. A more sophisticated texture generation process could be used for this step, e.g., in the spirit of [START_REF] Efros | Texture synthesis by non-parametric sampling[END_REF].

The final texture for this cell billboard and this image is thus an M × M RGBA texture, for which the pixels chosen as valid are assigned the RGB values of the (potentially modified) copy of the original image, and the A value is the value of the α image. This process is summarized in the following pseudo-code: The uncompressed textures require a significant amount of memory. To reduce the required texture memory, we dissociate alpha from RGB, and pack two RGB textures if their alphas do not intersect. The resulting memory requirements are about 45% of that originally required. For a typical uncompressed tree of 100Mb, the resulting compressed version requires 45Mb.

View-Dependent Rendering

Once an RGBA texture has been generated for each cell and each original camera, we can render in a straightforward manner. We traverse the cells back-to-front, and render the billboard for each cell with multi-texturing, using the appropriately weighted textures corresponding to the two closest cameras [START_REF] Debevec | Modeling and rendering architecture from photographs: A hybrid geometry-and image-based approach[END_REF]]. The RGBA billboard textures are simply blended for each cell visited in back-to-front order, in the sense of the over operator [START_REF] Porter | Compositing digital images[END_REF].

Implementation and Results

Our current implementation uses a recursive grid, which subdivides into 3x3x3 subcells (an octree could also be used). Currently, we subdivide all non-empty cells down to the maximum subdivision level. Empty interior cells are not subdivided.

We present two examples of real captured trees. Our approach is however better appreciated in an animation or walkthrough. Please see the accompanying video, available on the ACM SIGGRAPH 2004 Full Conference DVD-ROM, to better appreciate the results. The video also shows sequences of trees inserted in virtual scenes. All timings are on a Pentium IV 2.7 Ghz PC.

The first tree we have captured is an oak, shown in Fig. 1. We took 22 pictures of the tree, and generated an equivalent set of masks. The estimation took about 15 mins for a 4-level subdivision of our grid, resulting in 51,000 cells with 8x8 billboards, using a cuttoff transparency threshold of 0.94. The texture generation phase took 30 minutes, and resulted in 150Mb of texture, which after packing (which took 31 min), reduces to 56Mb. We show two new (non input) views of the oak in Fig. 9 (rightmost images); a synthetic rendering of an input view is shown in Fig. 1(d).

The second tree we have captured is a pine, shown in Fig. 9. We took 18 pictures of the tree; estimation took 15 minutes for a level 5 subdivision of our grid, resulting in 110,000 cells, with a cutoff transparency threshold of 0.9. The texture generation for 4x4 billboards took 15 minutes, resulting in 58Mb of texture. After a 17 minute packing process, the final compressed tree requires 22Mb. We show two new (non input) views of the pine in Fig. 9 (left).

Use of the transparency cutoff threshold greatly reduces the number of cells (by a factor of 2 and 8 respectively for the oak and pine), making the resulting trees smaller in memory and faster to display. Initially, some cells incorrectly receive non-zero opacity due to missing information such as the small number of cameras, or occlusion in the images. Use of the threshold makes some of these transparent during reconstruction, improving the visual quality.

Discussion

Our method gives very promising results, and we believe that it will be useful as a fast way to capture existing trees and to produce high quality interactive renderings of trees with low polygon count models.

One current difficulty is the need to have a good background to be able to acquire satisfactory alpha mattes. We currently add a uniform color background (a sheet in our case), where possible to help the alpha matte algorithm (see Fig. 4(left)). This helps, but is not always a practical solution. Using the Bayesian approach of [START_REF] Chuang | A Bayesian approach to digital matting[END_REF]] may improve the mattes extracted, and we hope that other researchers will develop a more stable alpha extraction approach, perhaps specifically adapted to the case of trees. Currently, the generated textures partially contain the original lighting information. However, since we manipulate the textures in the generation stage, it is clearly possible to develop some approximations which would permit relighting. In particular, the existence of opacity information should probably allow us to approximate light distribution, and perform approximate lighting or relighting calculations. A stochastic approach to shadow removal and normal estimation [START_REF] Katsumi | A display method of trees by using photo images[END_REF] could probably be applied. The relatively random nature of the tree leaf distribution should make this easier to achieve than for more structured objects. Exact shadow shapes are harder to identify, and thus the error should be less perceptually evident.

Using a low cutoff threshold makes some cells transparent, but reduces blurring significantly. This is a tradeoff, since depending on the level of subdivision and the number of cameras, existing branches or leaves may be removed. This effect is illustrated in Fig. 10 and in the video. Even when features are removed, for example with threshold 0.9, the tree remains very realistic and remains very similar to the input photographs; however blurring is almost completely eliminated. Investigating heuristics to find the best compromise is a promising avenue of research.

Finally, our approach is best suited for viewing the captured tree at a distance no closer than that of the cameras of the input photographs. Closer viewing would require additional processing. Conversely, when viewing from a distance, multi-level rendering could be used, by computing levels-of-detail for the billboards in the hierarchy.

Conclusion

We have presented an approach which allows efficient capture of trees from photographs in three steps. First photographs are taken and alpha-mattes generated; this step also generates the appropriate foreground color to be used for rendering and requires limited user intervention. An automatic reconstruction step creates a recursive grid which contains the opacity values for each cell. We then generate view-dependent textures for each cell, corresponding to the input views, which are attached to billboards placed at the centers of the cells. Rendering is performed using view-dependent texture mapping.

We have presented interactive renderings of captured trees, including the example of a pine tree, which is a particularly hard case to capture and render using other methods, due to the numerous, very fine pine-tree needles.

We believe that this approach, which combines a volumetric opacity estimation with view-dependent texturing will be a promising avenue for future research. Volume rendering solutions for shadows, lighting and relighting will probably be very useful for the development of lighting solutions for our captured trees. We will also develop ways to create varying instances of trees, by modifying certain characteristics, as well as ways to manipulate the resulting models (motion in the wind, scaling etc.). We plan to work actively on investigating the need and methods to improve opacity estimation, as well as improving texture generation techniques.

Figure 2 :

 2 Figure 2: (a) A recursive grid is placed around the tree. (b) A ray emanating at pixel p traverses the grid; a set of cells are collected.

Figure 4 :

 4 Figure 4: Left: the original image. Middle: the regions specified roughly by the user as foreground and background. Right: the computed alpha-mask (note that we used black for opaque for clarity of the figure).

Figure 6 :

 6 Figure 6: Illustration of slices of opacity values at the initialization step (left) and after the end of the reconstruction process (right).

Figure 7 :

 7 Figure 7: An illustration of the problems of naive rendering using view-dependent texturing: texture repetition results in blurring.

Figure 8 :

 8 Figure 8: (a) Illustration of the ideal case; (b) Texture generation for the first cell, and update of the image.

foreach

  RGBα image i make a copy Ci of image i render billboards to initialize Ncurr at each pixel foreach cell c front-to-back find projected region R of cell c in image Ci create resampled M × M texture T from Ci sort texels of T by age and by Ht select αc * M * M first texels for pixels in R corresponding to selected texels tcurr = tcurr tc replace pixels using texture generation for remaining pixels in R, increment age for all pixels in R, Ncurr = Ncurr -1; endfor endfor

Figure 9 :

 9 Figure 9: From left to right: two new (non-input) views of the captured pine tree and two new views of the captured oak tree.

Figure 10 :

 10 Figure 10: Side by side images of the reconstructed oak tree (synthetic view) using thresholds of 0.9, 0.94, 1.0 (left to right).

Acknowledgments

Thanks to Frédo Durand for important input on an early version, and Pierre Poulin for comments. This research was supported in part by the CREATE RTD project funded by the 5th Framework Information Society Technologies (IST) Programme of the European Union (IST-2001-34231), http://www.cs.ucl.ac.uk/create/ and by the French Ministry of Research grant ACI MD SHOW. We thank Alias|Wavefront for the generous donation of Maya, and Alexandre Olivier for modeling and capture. Thanks to Audrey Bzeznik for supporting the first author and for feeding the troops.

The four corners of the pixel define a pyramid, which we intersect with the near plane (see Fig. 11,illustrated in 2D for simplicity). This intersection has area An; the distance to the near plane is dn. We shoot N rays through a given pixel. A given ray will intersect cell i at a distance de, and the length from the entry to the exit point of the ray in the cell is l. It is assigned an area of As = An/N at the near plane. We compute the area A s of the slice of the pyramid corresponding to the ray using similar triangles: A s /d 2 n = As/d 2 e giving A s = As(d 2 e /d 2 n ). We then estimate the volume of the ray/cell intersection as V = lA s . The weight of the ray will be w i = V /Vc where Vc is the volume of the cell.


This paper studies various priority metrics that can be used to progressively select sub-parts of a number of audio signals for realtime processing. In particular, five level-related metrics were examined: RMS level, A-weighted level, Zwicker and Moore loudness models and a masking threshold-based model. We conducted a pilot subjective evaluation study aimed at evaluating which metric would perform best at reconstructing mixtures of various types (speech, ambient and music) using only a budget amount of original audio data. Our results suggest that A-weighting performs the worst while results obtained with loudness metrics appear to depend on the type of signals. RMS level offers a good compromise for all cases. Our results also show that significant sub-parts of the original audio data can be omitted in most cases, without noticeable degradation in the generated mixtures, which validates the usability of our selective processing approach for real-time applications. In this context, we successfully implemented a prototype 3D audio rendering pipeline using our selective approach.

PRIORITIZING SIGNALS FOR SELECTIVE REAL-TIME AUDIO PROCESSING

Emmanuel Gallo 1,2 , Guillaume Lemaitre 1 and Nicolas Tsingos 1

INTRODUCTION

Many applications ranging from video games to virtual reality or visualization/sonification require processing large number of audio signals in real-time. For instance, modern video games must render a large number of 3D sound sources using some form of spatial audio processing. Furthermore, each source's audio signal may itself be generated as a mixture of a number of sub-signals (e.g., a car-noise is a composite of engine and tire/surface noise) driven from real-time simulated physical parameters. The number of audio signals to process may often exceed hardware capabilities. Priority schemes that select the sounds to process according to a preset importance value are a common way of using hardware more efficiently, for instance by managing the limited number of hardware channels on a dedicated sound card. Usually, this value is determined by the sound designer at production time and might further be modulated by additional effects at run-time, such as attenuation of the sound due to distance or occlusion.

This paper is focused on the problem of automatically prioritizing audio signals according to an importance metric, in order to selectively process these signals. Such a metric can then be used to tune the processing "bit-rate" in order to fit a given computational budget: for instance, allocating a budget number of arithmetic operations to a complex signal processing task (e.g., a combination of mixing, filtering, etc.) involving a large number of source signals. Figure 1 shows a basic example application where four speech signals have been prioritized according to a loudness metric and a mix has been generated simply by playing back the single most- important signal per processing frame (highlighted in yellow). Such an approach could typically be used for hardware voice management in video games. This paper presents a comparative study of several metrics that can be used to prioritize signals for selective real-time processing of audio signals. In section 2, we start by reviewing previous work related to scalable and progressive audio processing. A coarse-grain selective processing algorithm is described in section 3. In particular, several metrics that can be used to prioritize the audio signals and selectively allocate the required operations are discussed in section 3.1. Our selective processing algorithm is demonstrated in the context of a time-domain pipeline comprising mixing and simple filtering operations in section 3.2. Results of a pilot subjective study are presented in section 4 that support the applicability of our technique. We finally discuss our approach and outline other possible applications of our prioritization scheme before concluding.

RELATED WORK

While parametric, progressive and scalable codecs are a key research topic in the audio coding community [START_REF] Vercoe | Structured audio: Creation, transmission, and rendering of parametric sound representations[END_REF][START_REF] Purnhagen | Advances in parametric audio coding[END_REF][START_REF] Herre | Audio coding -an all-round entertainment technology[END_REF], few attempts to date have been made to design scalable or selective approaches for real-time signal processing.

Fouad et al. [START_REF] Fouad | Perceptually based scheduling algorithms for real-time synthesis of complex sonic environments[END_REF] propose a level-of-detail rendering approach for spatialized audio where the sound samples are progressively generated based on a perceptual metric in order to respect a budgeted computing time. When it is elapsed, missing samples are interpolated from the calculated ones. As they prioritize signals according to their overall energy, such a scheme will fail at capturing large energy variations through time within the signal itself.

Wand and Straßer [START_REF] Straßer | Multi-resolution sound rendering[END_REF] proposed a multi-resolution approach to 3D audio rendering. At each frame of their simulation, they use an importance sampling strategy to randomly select a sub-set of all sound sources to render. However, their importance sampling strategy also does not account for the variations in signal intensity. Such effects might be much more significant (factors of 10 or more can be easily observed on speech signals for instance) than variations in the control parameters such as distance attenuation, etc. since the latter usually vary smoothly and slowly through time (except for very near-field sources).

In a previous work [START_REF] Tsingos | Perceptual audio rendering of complex virtual environments[END_REF], we proposed a framework for 3D audio rendering of complex virtual environments in which sound sources are first sorted by an importance metric, in our case the loudness level of the sound signals. We use pre-computed descriptors of the input audio signals (e.g., energy in several frequency bands through time) to efficiently re-evaluate the importance of each sound source according to its location relative to the listener. Hence, loudness variations within the signals are properly accounted for. The priority metric was used to determine inaudible sources in the environment due to auditory masking and group sound sources to optimize spatialization. This paper extends this approach by comparing several priority metrics and their subjective effect on selective processing of audio signals even for cases where removed sub-parts of the signals are above masking threshold.

Other scalable approaches based, for instance, on modal synthesis, have also been proposed for real-time rendering of multiple contact sounds in virtual environments [START_REF] Lagrange | Real-time additive synthesis of sound by taking advantage of psychoacoustics[END_REF][START_REF] Van Den Doel | Measurements of perceptual quality of contact sound models[END_REF][START_REF] Van Den Doel | Interactive simulation of complex audio-visual scenes[END_REF]. Similar parametric audio representations [START_REF] Vercoe | Structured audio: Creation, transmission, and rendering of parametric sound representations[END_REF][START_REF] Purnhagen | Advances in parametric audio coding[END_REF] also allow for scalable audio processing (e.g. pitch shifting or time-stretching, frequency content alteration, etc.) at limited additional processing cost, since only a limited number of parameters are processed rather than the full Pulse Code Modulation (PCM) audio data. However, this approach might imply real-time coding and decoding of the sound representations. As parametric representations are not widely standardized and commonly used in interactive applications, available standard hardware decoders do not usually give access to the coded representation in a convenient form for the user to further manipulate. Eventhough processing in coded domain might be achieved through modified software implementation of standard audio codecs (e.g. MPEG-1 layer 3, MPEG-2 AAC) [START_REF] Touimi | A generic framework for filtering in subbanddomain[END_REF], the overhead due to partial decoding would probably be overwhelming for a real-time application handling many signals.

SELECTIVE AUDIO PROCESSING

We propose a coarse-grain selective audio processing framework that can be separated into two steps : 1) we assign a priority to each frame of the input signals and 2) we select the frames to process by decreasing priority order until our pre-specified budget is reached. Remaining frames are simply discarded from the final result. Both steps are applied at each processing frame to produce a frame of processed output signal. The following sections detail both steps.

Priority metrics

In our approach, as well as others we described in section 2, processing management is driven by a given importance metric. The choice of this metric is then a crucial step: the audibility of the time (samples) artefacts introduced by any processing optimizations will depend on its quality. Loudness seems a good candidate since it has been shown to be closely related to masking phenomena [START_REF] Zwicker | Dependence of post-masking on masker duration and its relation to temporal effects in loudness[END_REF][START_REF] Baumgarte | A physiological ear model for auditory masking applicable to perceptual coding[END_REF]. Using loudness as an importance metric might hence allow important maskers to be processed first. But one can imagine that weighting may be more efficiently performed on the basis of more cognitive aspects. For instance, in the context of a collision avoidance experimental setup, Robert Graham [START_REF] Graham | Use of auditory icons as emergency warnings: evaluation within a vehicle collision avoidance application[END_REF] noticed that faster braking reaction times were measured when drivers were warned by car horns sounds, even if they were less loud than other tested sounds. There is a vast literature aiming at building psychoacoustic relationships between acoustic parameters of a sound and its so-called urgency (see Stanton and Edworthy [START_REF] Stanton | Auditory warnings and displays: an overview[END_REF] and [START_REF]Human Factors in Auditory Warnings[END_REF] for an overview). Derivations of these urgency metrics may form a more cognitive-founded importance metric. As a starting point, this paper examines the ability of several levelrelated metrics to optimize audio processing. In particular, we evaluated the following importance metrics:

1. RMS level, expressed in dB SPL, 2. A-weighted level, expressed in dBA [START_REF]Acoustics FAQ Section 8.1[END_REF],

3. Moore, Glasberg & Baer's loudness level [START_REF] Moore | A model for the prediction of thresholds, loudness and partial loudness[END_REF], expressed in phons, calculated assuming a stimulus is a band-limited noise.

4. Zwicker's loudness [START_REF] Zwicker | Program for calculating loudness according to din 45631 (iso 532b)[END_REF], expressed in sones,

5

. "Masking level" model defined as the level of the source minus a masking-threshold offset, expressed in relative dB (a masking threshold of -3 dB indicates that sounds with a energy weaker than half the energy of the masking sound will be masked), predicted from the tonality index of the signal [START_REF] Painter | A review of algorithms for perceptual coding of digital audio signals[END_REF][START_REF] Brandenburg | mp3 and AAC explained[END_REF]. Tonality index is typically derived from a spectral flatness measure and indicates the tonal or noisy nature of the signal [START_REF] Zwicker | Psychoacoustics: Facts and Models[END_REF].

Each metric is evaluated for short processing frames along our test signals, typically every 3 to 23 ms (i.e., 128 to 1024 samples at 44.1kHz). Results were not significantly different for the various frame sizes. Smaller frames give better time-resolution and can result in more optimal interleaving of the signals during the processing step. However, frames too short can result in highly degraded audio information since interleaved signals will no longer be recognizable, a problem closely related to the illusion of continuity [START_REF] Mcadams | Auditory continuity and loudness computation[END_REF]. Figure 2 shows a comparison of several loudness metrics evaluated on a fragment of speech signal.

Table 1 shows the average rank correlation obtained with various metrics on three different mixtures of speech, ambient and music signals. Rank correlation measures how correlated the orderings obtained with the various metrics are. As can be seen in this table, results appear to be dependent on the type of signals. For speech and ambient sounds, metrics are correlated although not strongly. For the musical mixture, results are more pronounced showing stronger correlation between Zwicker's and Moore's loudness models and very low correlation between loudness models and all the others. [START_REF] Howell | Statistical methods for psychology[END_REF] and averaged over all frames of the mixture. Its variance across frames is also given in brackets.

Selective processing algorithm

Our budget allocation algorithm is designed for real-time streaming applications. Hence, it has to be efficient and has to find a solution locally at each processing frame. To do this, the importance of each frame of the signal is evaluated and until our computational budget is reached, the algorithm selects which sub-parts of the signals should be processed, by decreasing priority value, using a greedy approach (i.e, taking the best immediate, or local, solution). An example is shown in Figure 1. The result is thus constructed as an interleaved mixture of the most important frames in all signals. To avoid artefacts during the reconstruction step, an overlap-add method (3ms frames with 10% overlap) was used. Another example is shown in Figure 3. Selected frames for different budgets are highlighted. As can be seen in the figure, our approach directly accounts for any sparseness in the mix by removing input frames below audibility threshold from the final mix. This might already result in a significant gain. For the various mixtures we used (ambient sounds, music and speech), we estimated that 0.7% to 33% of the input frames could be trivially removed (0.7% for ambient sounds, 24.5% for music and 33% for speech).

To improve the frequency resolution of our approach, we can further evaluate the priority metric for a number of sub-bands of the signals. In our experiments, we used four sub-bands corresponding to 0-500 Hz, 500-2000 Hz, 2000-8000 Hz, 8000-22000 Hz and treated each sub-band as if it were an additional input sound signal to prioritize. This would be typically useful for applications performing some kind of sub-band correction of the audio signal (e.g., equalizers). The required band-pass filtering can then be performed only on the selected sub-parts of the signal.

Integration within a real-time processing framework

Although most of the level-related priority metrics we used cannot be directly evaluated in real-time for large numbers of audio streams, they can be efficiently computed from additional descriptors stored with the audio data, in a manner similar to [START_REF] Tsingos | Perceptual audio rendering of complex virtual environments[END_REF]. Loudness information, in particular, can be retrieved from precomputed loudness tables, energy levels and tonality indices stored with each corresponding frame of input audio data. This information may also be stored for several sub-bands of the signal. Such an approach allows us to further modulate the importance value in real-time depending on various other effects affecting the signal during the simulation. This necessary information is quite compact (typically about 1 to 4 Kb/sec of input audio data) and can be interleaved with standard PCM audio data for streaming or kept resident in memory for random access while the PCM data is streamed on-demand.

Our coarse-grain selective algorithm integrates well within standard time-domain audio processing pipelines. We evaluated it in the context of a 3D audio processing application for virtual reality. In this case, the signals of each virtual sound source undergo filtering and resampling operations to simulate propagation effects (atmospheric scattering, occlusion, Doppler shift, etc.) and binaural hearing (e.g., HRTF filtering) before being combined to produce the final mix. We implemented a scalable 3D audio processing pipeline implementing these effects using time-domain resampling and attenuation over several sub-bands of each source signal, computed using second-order biquad filters. Using our selective pipeline, we were able to process the signals using a budget number of operations resulting in a computing speed-up directly proportional to the selected budget. As sources of decreasing priority are processed, a complementary solution is to simplify the operations (for instance, using linear resampling instead of better quality spline-based resampling) rather than maintain high-quality processing for all selected frames and simply drop low priority frames. Example movie files demonstrating the approach are available at: http://www-sop.inria.fr/reves/projects/scalableAudio/.

PILOT SUBJECTIVE EVALUATION

In order to evaluate subjective differences between the various metrics we ran a pilot evaluation study described in the following sections.

Experimental conditions

Subjects: 18 subjects (10 women and 8 men, 19 to 48 years old) volunteered as listeners. All reported normal hearing. Most of them were computer scientists, very few with any experience in acoustics or music practice. None of them was familiar with audio Apparatus: We ran the test on a laptop computer using an inhouse test program (see Figure 4). It was conducted using headphone presentation in a quiet office room. Sennheiser HD600 headphones were used (diotic listening), calibrated to a reference listening level at eardrum (100 dB SPL). The sounds were stored on the computer hard drive and played through the SigmaTel C-Major integrated sound-board. They were played back at a comfortable level. Procedure: The subjects were given written instructions explaining the task. They were asked to rate the 45 resulting output mixtures relative to the corresponding reference mix. We used the ITU-R 2 recommended triple stimulus, double blind with hidden reference technique, previously used for quality assessment of low bit-rate audio codecs [START_REF] Grewin | Methods for quality assessment of low bit-rate audio codecs[END_REF]. Subjects were presented with three stimuli, R, A and B, corresponding to the reference, the test stimulus and a hidden reference stimulus (the hidden reference was the reference itself, without any alteration) 3 . Test stimuli were presented to each subject in a different (random) order. The hidden reference was randomly assigned to button A or B. Our test program automatically kept track in an output log file of the presentation order and the marks given respectively to the stimulus and the hidden reference signal for each test. The output of the procedure was then two scores: one for the hidden reference, and one the for the test stimulus. After the ITU-R standard, the judgment value used for further analysis was the difference between the scores of the hidden reference and test stimulus. Hence, a value of zero indi- 1 The stimuli used for the tests can be found at: http://www-sop.inria.fr/reves/projects/scalableAudio/ 2 International Telecommunication Union 3 i.e., the subjects did not know which of A or B was the actual test or the reference. cates than no difference was perceived between the reference and the test sound. A positive score indicates that an annoying difference was heard between the test sound and the reference sound, and a negative score indicates that the test sound was better rated than the reference sound. Subjects could switch between the three stimuli at any time during playback by pressing the corresponding buttons on the interface (see Figure 4). They were asked to rate differences between each test stimuli (A and B) and the Reference from "imperceptible" to "very annoying", using a scale ranging from 5.0 to 1.0 (with one decimal) [START_REF] Itu-R | Methods for subjective assessment of small impairments in audio systems including multichannel sound systems[END_REF]. After the test, subjects were invited, during a semi-guided interview, to describe the differences that they heard between the processed and the original sounds.

Analysis

Correlations between the subjects: All subjects raw judgments were significantly correlated (p < 0.01) except for one who was removed from further analysis. After removing this subject, the correlation coefficients ranged from 0.38 to 0.92. Analysis of variance: A three-way analysis of variance was performed over the judgments (repeated design). Results are given in Table 2. The experimental factors affecting the judgments are: S: subjects, R : resolution , M : metric and T : type of signals.

All principal effects are significant (resolution: F(2,32)=195.0, p corrected < 0.01; metric: F(4,64)=16.3, p corrected < 0.01; type of signal: F(2,32)=41.1, p corrected < 0.00). Only the interactions between between metric and type of signals is significant at the lower threshold (F(8,128)=8.6 p corrected < 0.01). The principal effects of the experimental factors are depicted in Figure 5 Source The bottom graph in this figure clearly shows the effect of the resolution on the average judgments: when 50% of the data are kept, average judgments lay between 0 and 1, almost meeting the requirement for transparency (i.e., no judgment above 1). At 25% resolution, average judgments rise to values between 1 and 2.5, and slide up to more than 3.5 for a resolution of 12.5%. The top graph in the figure indicates that musical signals were, on average, better ranked than the other type of signals (subjects freely mentioned during post-experimental interviews that differences were harder to notice for musical sounds). This indicates that the alterations of the signal produced by the algorithm are less perceptible for musical sounds. The middle graph in the figure represents the effect of the metric on the average judgments. Results were not quite as pronounced, but a first conclusion is that the A-weighting metric leads to the most audible difference between the processed and original sounds. Further understanding is obtained by studying the significant interaction between metric and type of signal, depicted in Figure 6.

The patterns of effects for the metrics are qualitatively identical for both musical and speech signals: A-weighting leads to the worst results, RMS level and Zwicker's loudness model result in the best judgments, Moore's loudness yields to slightly weaker judgments. On the other hand, for ambient sounds, Zwicker's loudness model results in the worst judgments, whereas Moore's loudness model leads the processed sounds to be better evaluated with reference to the original ones. Although, our evaluation was aimed at a totally different purpose, our results share some similarities with the recent paper by Skovenborg and Nielsen [START_REF] Skovenborg | Evaluation of different loudness models with music and speech material[END_REF] that classified twelve loudness models (including several RMS-level metrics, Zwicker loudness and A-weighted level) into four categories. In their experiments, A-weighting was found to perform worst as a loudness metric while no clear advantage was found for the Zwicker loudness model over RMS-level related metrics. However, we could not test their two new loudness models, which seem to perform best. This would be an interesting future study to conduct.

DISCUSSION

Several conclusions can be drawn from this study. First of all, when only 50 % of the original data are used, subjects are almost unable to hear any difference between processed and original mixtures. When only 25 % of the sounds are preserved, average judgments lay between 2.5 and 1 (respectively "slightly annoying" and "perceptible but not annoying"). This indicates that our algorithm can reduce the required number of operations by more than 50 % without dramatically distorting the resulting mixtures (see Figure 7). Another conclusion is that the judgments seem to be strongly influenced by the type of signal. However, as this variable also integrates several other effects (numbers of signals in the mix, sparseness of the mix, energy distribution in the mix, etc.) it would require further testing. Nevertheless, differences between original and processed sounds were more difficult to detect for musical sounds. Two hypothesis can be formulated to explain this phenomenon: first of all, due to their nature, musical sounds are more sparse than other sounds. Energy peaks occur at regular rhythmic patterns, and there might a significant amount of low energy frames between these rhythmic accents. In our example, we estimated the sparseness (ratio between silence and signal) of our musical mix to be about 25%, which would make it well suited to our algorithm. However, the speech mixture was found to be much sparser that the ambient mixture (33% vs. less than 1%) although the results for these two cases were rather similar.

Another hypothesis is that the metrics were, in general, better suited to musical sounds. Comparing loudness models, Zwicker's model leads to better results for speech and musical sounds, while Moore's loudness model performs best for ambient sounds. This is consistent with our implementation of Moore's loudness model for noisy signals (it can be reasonably assumed that ambient sounds are noisier than musical sounds). These conclusions were confirmed during the interviews of the subjects. Many subjects reported that they used different criteria for the different types of signals. For speech signals, they reported to produce favorable judgments as long as the intelligibility was preserved, although most of the mixture was foreign language to them. For musical sounds, they did not hear any difference until the sounds were drastically distorted. Finally, for ambient sounds, they seem to have performed some kind of "spectral listening"; a typical remark being: "I tried to notice if there was more or less bass/treble". Hence, we can conclude that no metric seems to perform best in all cases but, rather, that the importance metric has to be adapted to the type of signal.

CONCLUSIONS

We have presented an approach for coarse-grain selective processing of audio signals. Several level-related metrics that can be used to drive the selection process were compared showing significant difference between the various metrics in terms of the ordering induced on the signals. A pilot subjective evaluation study suggests that A-weighting does not perform as well as the other metrics at prioritizing the sound signals. While RMS level appears as a good compromise, other metrics, loudness in particular, can yield to better results depending on the type of signals. Our selective processing approach integrates well within standard audio processing pipelines and can be used to reduce the necessary operations by 50% while remaining near-transparent or 75% with an acceptable degradation of the perceived quality.

As future work, we would like to explore extensions to finergrain processing by combining our selection scheme with parametric audio coders or alternate representations for audio signals.

We believe that proposing and evaluating more sophisticated priority metrics is of primary interest for a wide range of applications including memory/resource management (e.g. 3D hardware voices, streaming from main storage space), real-time masking evaluation [START_REF] Tsingos | Perceptual audio rendering of complex virtual environments[END_REF], on-the-fly multi-track mixing [START_REF] Pachet | On-the-fly multi track mixing[END_REF], dynamic coding and transmission of spatial audio content and more generally for computational auditory scene analysis.

Figure 1 :

 1 Figure 1: Four speech signals prioritized according to a loudness metric computed over successive short time-frames. The single most important frame across time is highlighted in yellow.

Figure 2 :

 2 Figure 2: Several priority metrics calculated for an example speech signal using 3 ms-long frames.

Figure 3 :

 3 Figure 3: (a) Loudness values (using Zwicker's loudness model) through time for the 17 tracks of a musical mix. Each track was selectively filtered and processed into 4 frequency sub-bands resulting in 68 signals to prioritize. (b) Priority map showing the first 12.5% most important frames highlighted in red. (c) First 25% most important frames and (d) first 50% most important frames.

Figure 4 :

 4 Figure 4: Snapshot of the interface designed for our listening tests.

Figure 5 :

 5 Figure 5: Principal effects of the experimental factors. Vertical bars represent standard deviation. The average judgment represents an annoyance level (hidden reference minus stimulus).

Figure 6 :

 6 Figure 6: Interactions between the effects of the metric and the type of signal on the average judgments. The average judgment represents an annoyance level (hidden reference minus stimulus).

Figure 7 :

 7 Figure7: Averaged judgments for the three test mixtures and for three levels of detail. When only 50% of the input audio data was used, the resulting mixture was highly rated regardless of the stimuli.

Table 1 :

 1

	speech	Zwicker	mask.	Moore	RMS	A-weight.
		loud.	thr.	loud.	level
	Zwicker loud.	1 (0)	0.37 (0.22)	0.57 (0.29)	0.40 (0.22)	0.35(0.23)
	mask thr.	0.37 (0.22)	1 (0)	0.54 (0.22)	0.73 (0.22)	0.56 (0.31)
	Moore loud.	0.57 (0.29)	0.54 (0.22)	1 (0)	0.54 (0.23)	0.36 (0.21)
	RMS level	0.40 (0.23)	0.73 (0.22)	0.54 (0.23)	1 (0)	0.54 (0.31)
	A-weight.	0.35 (0.23)	0.56 (0.31)	0.36 (0.21)	0.54 (0.31)	1 (0)
	ambient	Zwicker	mask.	Moore	RMS	A-weight.
		loud.	thr.	loud.	level
	Zwicker loud.	1 (0)	0.40 (0.18)	0.44 (0.18)	0.42 (0.19)	0.37 (0.17)
	mask thr.	0.40 (0.18)	1 (0)	0.48 (0.17)	0.51 (0.18)	0.35 (0.18)
	Moore loud.	0.44 (0.18)	0.48 (0.17)	1 (0)	0.47 (0.17)	0.37 (0.17)
	RMS level	0.42 (0.19)	0.51 (0.17)	0.47 (0.17)	1 (0)	0.33 (0.18)
	A-weight.	0.37 (0.17)	0.35 (0.17)	0.37 (0.17)	0.33 (0.18)	1 (0)
	music	Zwicker	mask.	Moore	RMS	A-weight.
		loud.	thr.	loud.	level
	Zwicker loud.	1 (0)	0.05 (0.12)	0.42 (0.12)	0.04 (0.11)	0.03 (0.10)
	mask thr.	0.05 (0.11)	1 (0)	0.04 (0.11)	0.42 (0.09)	0.40 (0.10)
	Moore loud.	0.42 (0.12)	0.04 (0.11)	1 (0)	0.02 (0.10)	0 (0.10)
	RMS level	0.04 (0.11)	0.42 (0.10)	0.02 (0.10)	1 (0)	0.36 (0.10)
	A-weight.	0.03 (0.10)	0.40 (0.10)	0 (0.10)	0.36 (0.10)	1 (0)

Rank correlation matrices for three test mixtures of speech, ambient and musical signals. Rank correlation was calculated using Spearman's formula

Table 2 :

 2 Anova table for the subjective evaluation (vertical bars represent the standard deviation).

		df	Sum of Mean	F-value p cor.
			squares squares
	S	16	139.8	8.7
	R	2	967.7	483.2	195.0	0.000(**)
	S*R	32	79.4	2.5
	M	4	23.4	5.8	16.3	0.001(**)
	S*M	64	23.0	0.3
	R *M	8	5.6	0.7	1.9	0.191 (ns)
	S*R *M	128 48.2	0.4
	T	2	112.7	56.3	41.1	0.000 (**)
	S*T	32	43.8	1.4
	R *T	4	27.5	6.9	6.8	0.0191(*)
	S*R *T	64	64.7	1.0
	M *T	8	24.5	3.0	8.6	0.010(**)
	S*M *T	128 45.5	0.4
	R *M *T	16	17.2	1.07	2.8	0.115(ns)
	S*R *M *T 256 99.1	0.4
	Total		1722.0	2.2
	df: degree of freedom
	p cor.: corrected probability (conservative F-test)
	* p<0.05; ** p<0.01; ns: not significant

Proceedings of ICAD 05-Eleventh Meeting of the International Conference on Auditory Display, Limerick, Ireland,July 6-9, 2005

ACKNOWLEDGEMENTS

The authors would like to thank the anonymous reviewers for their useful comments. This research was supported in part by the 2year RNTL project OPERA, co-funded by the French Ministry of Research and Ministry of Industry. http://www-sop.inria.fr/reves/OPERA.