Vincent Jantet

Christine Guillemot

Luce Morin

Joint Projection Filling method for occlusion handling in Depth-Image-Based Rendering

This paper addresses the disocclusion problem which may occur when using Depth-Image-Based Rendering (DIBR) techniques in 3DTV and Free-Viewpoint TV applications. A new DIBR technique is proposed, which combines three methods: a Joint Projection Filling (JPF) method to handle disocclusions in synthesized depth maps; a backward projection to synthesize virtual views; and a full-Z depth-aided inpainting to fill in disoccluded areas in textures. The JPF method performs the pixels warping for virtual depth map synthesis while making use of an occlusion-compatible pixel ordering strategy, to detect cracks and disocclusions, and to select the pixels to be propagated in the occlusion areas filling process. The full-Z depth-aided inpainting method fills in disocclusions with textures at the correct depth, preserving the boundaries of the objects.

Ghosting artifacts, which might otherwise result from pixel projections, are here avoided by introducing a confidence measure on background pixels to be used in the JPF process.

Introduction

One classical problem in computer vision applications is the synthesis of virtual views from a single video sequence, accompanied by the corresponding depth map. This problem is encountered in applications such as robot navigation, object recognition, intermediate view rendering in free-viewpoint navigation, or scene visualization with stereoscopic or auto-stereoscopic displays for 3DTV. Many rendering algorithms have been developed First, the input depth map is projected onto the virtual viewpoint. Second, the resulting depth map is filtered to avoid cracks and ghosting artifacts. Third, the filtered depth map is projected back onto the reference viewpoint to find the color of each pixel. Fourth, the depth map is inpainted to fill in disocclusions. Finally, the inpainted depth map is used to conduct disocclusions filling of the color map (synthesized view).

and are classified rather as Image-Based Rendering (IBR) techniques or Geometry-Based Rendering (GBR)

techniques, according to the amount of 3D information they use. IBR techniques use multi-view video sequences and some limited geometric information to synthesize intermediate views. These methods allow the generation of photo-realistic virtual views at the expense of virtual camera freedom [START_REF]Image-based rendering and synthesis[END_REF]Chan, Shum, and Ng].

GBR techniques require detailed 3D models of the scene to synthesize arbitrary viewpoints (points of view).

GBR techniques are sensitive to the accuracy of the 3D model, which is difficult to estimate from real multi-view videos. GBR techniques are thus more suitable for rendering synthetic data.

Depth-Image-Based Rendering (DIBR) techniques [START_REF] Shum | A review of image-based rendering techniques[END_REF], [START_REF] Zhang | A survey on image-based rendering-representation, sampling and compression[END_REF]] include hybrid rendering methods between IBR and GBR techniques. DIBR methods are based on warping equations, which project a reference view onto a virtual viewpoint. Each input view is defined by a "color" (or "texture") map and a "depth" map, which associate a depth value to each image pixel. These depth maps are assumed to be known, or can be estimated from multi-video sequences by using a disparity estimation algorithm [START_REF] Hartley | Multiple View Geometry in Computer Vision[END_REF], Sourimant(2010)].

This paper describes a novel DIBR technique, which is designed to handle disocclusions in virtual view synthesis, from one or many inputs view plus depth video sequences.

The classical DIBR scheme for virtual view extrapolation from single input view plus depth video sequences is shown in figure 1. The process is divided in several distinct steps, each one designed to solve a specific problem.

First, the input depth map is warped onto the virtual viewpoint. The obtained warped depth map contains disocclusions, cracks and ghosting artifacts (these artifacts are detailed in section 2). Second, this virtual depth map is filtered a first time with a median filter, in order to remove the cracks, then a second time to dilate disocclusion areas on the background side, in order to avoid ghosting artifacts during view synthesis. Third, the Fourth, this resulting depth map is inpainted, to fill in disocclusion areas. Finally, this complete depth map is used by a depth-aided inpainting algorithm to fill in disocclusions in the color map.

All these steps are inter-dependent, and errors introduced by each one are amplified by the following one.

Connectivity information is lost during the first projection step, as shown in figure 2. Without this connectivity information, every inpainting method fails to fill in background disocclusions if the disoccluded area is surrounded by foreground objects. This case may happen each time a foreground object is not convex, and contains holes, as shown in figure 2(a). As a result, depth-aided inpainting uses wrong foreground patches to fill in background disocclusions, producing annoying artifacts, as shown in figure 2(b). This paper describes two DIBR techniques, both based on a novel forward projection technique, called the Joint Projection Filling (JPF) method. The JPF method performs forward projection, using connectivity information to fill in disocclusions in a single step, as shown in figure 2(c).

The first proposed DIBR method, shown in figure 3, is designed to extrapolate virtual views from a single input view plus depth video sequence. The method differs from the classical scheme, presented in figure 1, by two points: the virtual depth map is synthesized by the JPF method, avoiding the use of dedicated filtering and inpainting processes; the depth-aided inpainting method is revised to take into account the high quality of the synthesized depth map.

The second proposed DIBR method is designed to interpolate intermediate views from multiple input view plus depth sequences. The method uses the Floating Texture approach to register multiple inputs view plus Figure 3: Proposed scheme for virtual view extrapolation from single input view plus depth sequence. First, the Joint Projection Filling (JPF) method handles cracks and disocclusions during the depth map warping. Then, the backward projection method synthesizes the virtual view. Finally, the depth-aided inpainting takes into account the high quality of the computed depth map to fill disoccluded areas in texture.

depth sequences before blending.

The JPF method fills in disocclusion areas during the projection, to ensure that geometrical structures are well preserved. The method uses the occlusion-compatible ordering presented by McMillan in [McMillan(1995)],

which uses epipolar geometry to select a pixel scanning order. The algorithm was initially introduced to perform the painter's algorithm during the projection without the need of a Z-buffer. Here, not using a Z-buffer is not our purpose (by the way, the constructed depth map is a Z-buffer). The occlusion-compatible ordering is instead used to handle disocclusions gracefully. Cracks are filled in by interpolation of neighboring pixels, whereas disocclusions are only filled in by background pixels. This technique can be used with non-rectified views, avoiding prior creation of parallax maps as done in [START_REF] Kauff | Depth map creation and image-based rendering for advanced 3dtv services providing interoperability and scalability[END_REF].

In summary, the technique described here improves upon state-of-the-art DIBR methods as described in [Müller et al(2008b)Müller, Smolic, Dix, Merkle, Kauff, and Wiegand], by introducing the following key contributions:

• A novel forward projection method for DIBR, using occlusion compatible ordering [McMillan(1995)] for detecting cracks and disocclusions, for which the unknown depth values are estimated while performing the warping. The resulting projection method thus allows us to handle both depth maps warping and disocclusion filling simultaneously. Small cracks and large disocclusions are handled gracefully, with similar computational cost as simple forward projection, avoiding the use of the filtering step as done in the classical approach.

• A ghost removal method to avoid ghosting artifacts in the rendered views, relying on a depth-based pixel confidence measure.

• A depth-aided inpainting method which takes into account all information given by the depth map to fill in disocclusions with textures at the correct depth.

• A method to handle inaccuracies of cameras calibration and depth map estimation by the use of the Floating Texture approach.

The rest of the paper is organized as follows. Section 2 details some state-of-the-art solutions for each one of the three types of artifacts generated by the warping process, which are ghosting, cracks and disocclusions.

Section 3 introduces the Joint Projection Filling (JPF) method, which simultaneously handles projection and disocclusion filling. Section 4 describes the two DIBR techniques, designed for synthesizing virtual views from one or many input views.

Background work

DIBR methods are based on warping techniques which project a reference view onto a virtual viewpoint. Directly applying warping equations may cause some visual artifacts in the synthesized view, like disocclusions, cracks and ghosting artifacts. Disocclusions are areas occluded in the reference viewpoint and which become visible in the virtual viewpoint, due to parallax effect. Cracks are small disocclusions, mostly due to texture re-sampling.

Ghosts are artifacts due to projection of pixels that have background depth and mixed foreground/background color. Various methods have been proposed in the literature to avoid these artifacts. This section presents state-of-the-art solutions to avoid each one of these three usual artifacts.

Ghosting artifacts are often avoided by detecting depth discontinuities on the depth map, in order to separate the boundary layer (containing pixels near a boundary) from the main layer (containing pixels far from a boundary) [START_REF] Zitnick | High-quality video view interpolation using a layered representation[END_REF]. The main layer is first projected into the virtual viewpoint, then the boundary layer is added everywhere it is visible (i.e. where its depth value is smaller than the main layer's one). In [Müller et al(2008b)Müller, Smolic, Dix, Merkle, Kauff, and Wiegand],

the authors propose to split again the boundary layer into foreground and background boundary layers. The main layer is first projected, the foreground boundaries layer is then added everywhere it is visible, and the background boundaries layer is finally used to fill in remaining holes. Ghosting artifacts can be further avoided by estimating the background and foreground contributions in the rendered view with the help of advanced matting techniques [START_REF] Hasinoff | Boundary matting for view synthesis[END_REF])Hasinoff, Kang, and Szeliski, Sarim et al(2009)Sarim, Hilton, and Guillemaut, Wang and Cohen(2007)].

Cracks and other sampling artifacts are frequently avoided by performing a backward projection [START_REF] Mori | View generation with 3d warping using depth information for ftv[END_REF]Mori, Fukushima, Yendo, Fujii, and Tanimoto], which works in three steps. At first, the depth map is warped with a forward projection, resulting in some cracks and disocclusions. Then, this virtual depth map is median filtered to fill cracks, and bilateral filtered to smoothen the depth map while preserving edges.

Finally, the filtered depth map is warped back into the reference viewpoint to find the color of the synthesized views.

In [START_REF] Do | Quality improving techniques in dibr for free-viewpoint video[END_REF], the authors propose to reduce the complexity by performing backward projection only for pixels labeled as cracks, i.e. pixels whose depth values are significantly modified by the filtering step. In [START_REF] Nguyen | Depth image-based rendering from multiple cameras with 3d propagation algorithm[END_REF], the authors propose an improved occlusion removal algorithm, followed by a depth-color bilateral filtering, in order to handle disocclusions on the depth map.

Other improved rendering methods based on surface splatting have been proposed for avoiding cracks and texture re-sampling artifacts [START_REF] Rusinkiewicz | Qsplat: a multiresolution point rendering system for large meshes[END_REF], [START_REF] Pfister | Surfels-surface elements as rendering primitives[END_REF]Pfister, Zwicker, van Baar, and Gross, [START_REF] Zwicker | Ewa splatting. Visualization and Computer Graphics[END_REF].

Disocclusions are often filled in with information from some extra views, when they are available. The classical scheme is to synthesize the virtual view from each input view independently, then to blend the resulting synthesized views.

In [START_REF] Eisemann | Floating textures[END_REF] When extra views are not available, the frequent solution for disocclusion handling is image interpolation with inpainting techniques.

Unfortunately, most inpainting techniques use neighboring pixels solely based upon colorimetric distance, while a disocclusion hole should be filled in with background pixels, rather than foreground ones [START_REF] Bertalmío | Navierstokes, fluid dynamics, and image and video inpainting[END_REF]Sapiro, Telea(2004), [START_REF] Criminisi | Object removal by exemplar-based inpainting[END_REF].

A good review on the use of inpainting for image-based rendering can be found in [START_REF] Tauber | Review and preview: Disocclusion by inpainting for image-based rendering[END_REF].

In [START_REF] Do | Quality improving techniques in dibr for free-viewpoint video[END_REF]Do, Zinger, Morvan, and de With], the authors estimate each pixel value inside a disocclusion area from nearest known pixels along the eight cardinal directions, after nullifying the weight of foreground pixels. In [START_REF] Oh | Hole filling method using depth based in-painting for view synthesis in free viewpoint television and 3-d video[END_REF]Oh, Yea, and Ho], the authors temporarily replace foreground textures by background texture before inpainting, so that disocclusions are filled in only with background texture.

Advanced depth-aided inpainting methods assume that the depth map of the virtual viewpoint to be rendered is available.

In [START_REF] Daribo | Depth-aided image inpainting for novel view synthesis[END_REF]], the authors enhance the inpainting method in [START_REF] Criminisi | Object removal by exemplar-based inpainting[END_REF]Criminisi, Pérez, and Toyama] by reducing the priority of patches containing a depth discontinuity, and by adding a depth comparison in the search for best matches.

In [START_REF] Gautier | Depth-based image completion for view synthesis[END_REF]Gautier, Le Meur, and Guillemot], the authors use a similar approach but estimate isophotes directions with a more robust tensor computation and constrain the propagation in the direction of the epipole.

The full depth map from the virtual view is most of the time not available, and must be estimated from the input depth map. In [START_REF] Daribo | Depth-aided image inpainting for novel view synthesis[END_REF]], the authors perform a diffusion-based inpainting [START_REF] Bertalmío | Navierstokes, fluid dynamics, and image and video inpainting[END_REF]Bertalmío, Bertozzi, and Sapiro] on the projected depth map, but both foreground and background are diffused to fill disocclusions. In [START_REF] Nguyen | Depth image-based rendering from multiple cameras with 3d propagation algorithm[END_REF]Nguyen, Do, and Patel], the authors constrain the depth map inpainting in the direction of the epipole, in order that only the background is diffused, but this method fails when a disocclusion is surrounded by foreground depth, as shown in figure 2(b).

As a conclusion, state-of-the-art DIBR methods need a complete depth map at the rendered viewpoint (for backward projection and depth-aided inpainting). However, no fully satisfying method yet exists to obtain a complete and correct depth map, avoiding artifacts generation when used for DIBR. Moreover, most of disocclusions handling methods proposed in the literature work as a post treatment on the projected view.

Connectivity information is not preserved during the projection, and inpainting methods fail to fill in background disocclusions when they are surrounded by foreground objects. The proposed JPF method aims at suppressing such drawbacks. As shown in figure 2, the JPF method enables to recover correct depth information in critical areas. We also propose a full-Z depth-aided inpainting technique which takes into account the high quality of the computed depth map to fill disocclusions with texture from the correct depth.

Projection-based disocclusion handling

This section introduces the Joint Projection Filling (JPF) method, which simultaneously handles warping and disocclusion filling, in order to preserve connectivity and fill in disocclusions with background textures.

During warping, there might happen overlapping (several pixels projected at the same position) or disocclusion (no pixels projected at a position). In [McMillan(1995)], a pixel scanning order is introduced to perform the painter's algorithm during the projection. In case of overlapping, this pixel scanning order ensures the pixel just projected at a position to be the foreground pixel so that the z-buffer is not needed. A second property, resulting from the first one, is more helpful to handle disocclusions. If two successive pixels are not adjacent, there is a disocclusion, and the pixel just projected is the background pixel. This second property is exploited to ensure only background pixels are used to fill in disocclusion areas.

The JPF algorithm is described in section 3.1. It is first introduced for rectified cameras and then generalized for non-rectified cameras. Section 3.2 presents a ghosting removal method, based on pixels confidence measure.

Finally, section 3.3 presents some synthesized textures and depth map, obtained by the JPF method.

Disocclusion detection

In the following, we assume that the epipolar geometry is such that the pixels from the reference image are processed sequentially, from top-left to bottom-right, according to McMillan scanning order [McMillan(1995)].

Figure 4(b) presents the principle of the Joint Projection Filling (JPF) method, in the particular case of rectified cameras. Each row is thus independent of the others, reducing the problem to one dimension. Consider a row of pixels from the reference view, and a pixel p = (p x , p y ) on that row. The pixel p is projected on position p = (p x , p y ) in the synthesized view. After having processed pixel p, the next pixel to be processed is q = (p x + 1, p y ). Its projected position q = (q x , p y ) verifies one out of the three following equations:

              
q x = p x + 1 Pixels p and q are adjacent. q x < p x + 1 There is an overlap.

q x > p x + 1
There is a crack or a disocclusion.

(1)

The first and the second cases do not generate artifacts. In the last case, p and q are in same order as p and q, but there is a gap between them. In the proposed method, contrary to classical point-based projection, this gap

Reference viewpoint

Virtual viewpoint (a) Projection.

Process direction

Overlap Disocclusion p q (b) Details of a single row of pixels in the synthesized view for a rectified projection.

Process direction Disocclusion

P q q p (c) Details of some rows of pixels in the synthesized view for a non rectified projection.

Figure 4: JPF method scheme for rectified 4(b) and non rectified 4(c) cameras. q is a background pixel which is used to fill in the highlighted disocclusion.

is filled in immediately, before processing the projection of the next pixel. The method to fill the gap is adapted to its size. If the gap is small enough, it is considered as a crack. p and q are thus assumed to be on same layer, and the gap is filled in by interpolating the two pixels p and q . If the gap is too large, it is considered as a disocclusion. p and q are thus assumed to be on two distinct depth layer and the gap is filled in by background pixel. The McMillan pixel ordering ensures that q is the background pixel, which is stretched from position p to q . The value of each pixel m between p and q is thus estimated as follows:

m =        (1 -α)p + αq if d ≤ K q if d > K where        d = q x -p x α = 1 d (m x -p x ) (2)
In the simulation results reported in the paper, the threshold K has been fixed to 5 pixels, to handle cracks and small disocclusions.

The algorithm is generalized for non-rectified cameras, as illustrated in figure 4(c). Pixels p and q may no longer be on the same row, thus we define pixel P q as the last pixel projected on row q y . Equation ( 1) is revised, replacing p with P q , thus q and P q are on the same row.

(a) (b) (c) (d)
       q x ≤ P q
x + 1 There is no artifact.

q x > P q x + 1 There is a disocclusion.

(3)

As previously, the disocclusion handling method depends on the distance between q x and P q x . The value of each pixel m between P q and q is thus estimated as follows:

m =        (1 -α)P q + αq if d ≤ K q if d > K where        d = q x -P q x α = 1 d (m x -P q x ) (4)
Figure 5 presents the synthesized depth maps obtained with the JPF method, without any ghosting removal technique. Our JPF method has removed all cracks and has filled in the disocclusions with only background pixels. Depth maps from the "Ballet" sequence contain sharp discontinuities, which are preserved by the JPF method (figure 5(a)). Depth maps from other sequences contain some blur along depth discontinuities, due to DCT-based compression. This blur produces some sparse pixels inside the disocclusion area, which are stretched to fill the disocclusion, resulting in an annoying ghosting artifact.

This occlusion-compatible ordering is helpful to detect cracks and disocclusions. Next section explains how to fill in disocclusions while preserving edges sharpness and avoiding ghosting artifacts.

Disocclusion filling

Pixels along objects boundaries are considered unreliable, because they often contain mixed foreground/background information for texture and depth value. Their projection may thus create ghosting artifacts in the synthesized views. The JPF method as described in section 3.1 fills in each row of a disoccluded region using a single pixel. When applied on such a "blended" boundary pixel, this method may result in annoying pixel stretching artifacts, as can be seen in figure 5. However, these artifacts can be minimized by adapting the pixel stretching length, according to a pixel confidence measure. The algorithm used to avoid stretching and ghosting artifacts thus proceeds with the following two steps:

In a first step, a confidence measure λ q ∈ [0; 1] is computed for each pixel q by convolving the depth map (Z)

with a Difference-Of-Gaussians (DOG) operator as follows:

λ q = 1 -(DOG * Z)(q) (5)
The DOG operator is built as the difference of two gaussians: the gaussian G of variance σ 2 , and the 2D Dirac

delta function δ 2 . DOG = G -δ 2 G(u, v) = 1 σ 2 • φ u σ • φ v σ ( 6
)
where φ is the standard normal distribution. The value of σ, in the experiments described below, has been fixed to 3.

In a second step, the confidence measure is used during the JPF method, to confine pixel stretching. Reusing the notations introduced in section 3.1, suppose that a wide disocclusion is discovered during the projection of pixel q. Instead of filling the whole gap between P q and q , with color and depth values of q , only a part of the gap is filled in. The rest will be filled with the next pixel which will be projected on that same row j.

Assume M is a point between P q and q , defined with the following equation:

M = (1 -λ 2 q )P q + λ 2 q q (7)
The gap between P q and M is filled in by pixel q , thus pixels on foreground/background boundaries which have low confidence measures are used to fill the disocclusion only for a couple of pixels next to the foreground, where blended pixels are expected to be in the synthesized view.

Results

This confidence-based interpolation method shifts back unreliable pixels near the discontinuities and only uses reliable pixels to fill in disocclusions. Figure 6 presents the rendering results of the JPF method with confidence-based interpolation. The projected depth maps, shown on the first row, are to be compared with those presented in figure 5. One can see that depth discontinuities are sharpened, producing realistic depth maps.

The second row presents the results obtained with the same algorithm applied on texture. Disocclusions are gracefully filled in when the background is uniform, but annoying stretching artifacts appear in case of textured background. This JPF method can be used as a part of a virtual view synthesis algorithm, depending on the

Virtual view rendering

The JPF method is designed to synthesize virtual views from one or many input view plus depth video sequences, depending on the final application. Section 4.1 describes a virtual view extrapolation algorithm, which is used when only one input view plus depth video sequence is available. Section 4.2 presents an interpolation algorithm to synthesize intermediate views when multiple video plus depth video sequences are available.

View extrapolation with full-Z depth-aided inpainting

In order to synthesize a virtual view from only one input view plus depth sequence, the classical rendering scheme, introduced in figure 1, is replaced by the one presented in figure 3. First, the depth map for the virtual view is synthesized by our JPF method, handling ghosting, cracks and disocclusions. Then, the texture of the virtual view is obtained by a classical backward warping followed by the proposed full-Z depth-aided inpainting algorithm.

Our proposed full-Z depth-aided inpainting algorithm is a modification of the depth-aided inpainting method described in [START_REF] Daribo | Depth-aided image inpainting for novel view synthesis[END_REF]], itself based on the exemplar-based inpainting approach, introduced Given the block Ψ p , n p is the normal to the contour δΩ of the hole region Ω. Φ is the non-hole region. ∆I ⊥ p is the isophote at point p.

Exemplar-based inpainting approach [Criminisi et al(2003)Criminisi, Pérez, and Toyama]

The inpainting algorithm introduced by Criminisi et al. in [START_REF] Criminisi | Object removal by exemplar-based inpainting[END_REF] Criminisi, Pérez, and Toyama] is an exemplar-based inpainting technique. The authors noted that exemplar-based inpainting techniques can replicate both texture and structure, and they demonstrate that the quality of the output image synthesis is highly influenced by the order in which the inpainting is processed. Based on these observations, they describe in [START_REF] Criminisi | Object removal by exemplar-based inpainting[END_REF] Criminisi, Pérez, and Toyama] an inpainting algorithm which iterates the following two steps until all missing pixels have been filled in. First, a priority term is computed, in order to determine the next patch of the image to be filled in. Second, this selected patch is filled in by copying a patch chosen as the best match for the known pixels of the patch to be filled in. These two steps are iterated until all missing pixels have been filled in.

Considering an input image I, and a missing region Ω, the source region Φ is defined as Φ = I -Ω (see figure 7). For each pixel p along the frontier δΩ, they define the patch Ψ p centered in point p.

The priority P (p) of the patch Ψ p is computed as the product of the Confidence term C(p) and the Data term D(p).

P (p) = C(p) • D(p) (8)
The Confidence term C(p) indicates the reliability of the current patch. It is nearly the ratio between the number of know pixels in the patch, compared to the size of the patch. C(p) is initialized to 0 if p ∈ Ω or 1 if p ∈ Φ, and then it is computed as follows:

C(p) = 1 |Ψ p | q∈Ψp∩Φ C(q) (9)
where |Ψ p | is the number of pixels within the patch Ψ p .

The Data term D(p) is computed as the scalar product of the isophote direction ∆I ⊥ p , and the unit vector n p , orthogonal to δΩ at point p.

D(p) = |∆I ⊥ p , n p | α ( 10
)
where α is a normalization factor (e.g. α = 255 for a typical gray-level image).

Once all priorities on δΩ are computed, the patch Ψ p with the highest priority is selected to be filled in.

Then, a template matching algorithm search for the best exemplar Ψ q to fill in missing pixels under Ψ p, as follows:

Ψ q = arg min Ψq∈Φ {SSD Φ (Ψ p, Ψ q )} (11)
where SSD Φ (•, •) is the distance between two patches, defined as the Sum of Squared Differences and only computed on pixels from the non-hole region Φ.

The priority computation step and the best matches duplication step are iterated until all missing pixels have been filled in. The exemplar-based inpainting method produces good results for object removal and image restoration, but is not well suited to address the problem of disocclusions handling, because disocclusions should be filled in with background texture only.

Extension to depth-aided inpainting [Daribo and Pesquet(2010)]

The Criminisi's inpainting method has been adapted in [START_REF] Daribo | Depth-aided image inpainting for novel view synthesis[END_REF]], to address the specific problem of disocclusion handling. The authors propose two major modifications, which are the addition of a new term L(p) into the priority function evaluation, and the consideration of the depth into the SSD computation.

The first modification consists in introducing the Level regularity term L(p) as a third term into the priority function P (p).

P (p) = C(p) • D(p) • L(p) (12)
The Level regularity term L(p) is defined as the inverse variance of the depth patch Z p :

L(p) = |Z p | |Z p | + q∈Zp∩Φ Z p (q) -Zp 2 (13)
where |Z p | is the area (in terms of number of pixels) of depth patch Z p centered in p, Z p (q) is the depth value at pixel location q under Z p , and Zp the mean value.

The second modification consists in adding depth into SSD computation, computed during the best match search. Equation 11 is thus modified as follows:

Ψ q = arg min Ψq∈Φ {SSD Φ (Ψ p, Ψ q ) + α SSD Φ (Z p, Z q )} ( 14
)
where the parameter α controls the importance given to the depth distance minimization.

The Level regularity term L(p) gives more priority to patches with a constant depth level, which is expected to favor background pixels over foreground ones. Considering depth into the SSD computation favors patches which are at the same depth as the patch to be copied.

Z B G R Z B G R (a) (b)
Figure 8: Part of the patch Ψ p which is involved in SSD computation. In [START_REF] Daribo | Depth-aided image inpainting for novel view synthesis[END_REF]], authors compute SSD with color (RGB) and depth (Z) information only from the known part of the patch Ψ p ∩ φ, as shown in figure 8(a). Instead, we use the depth of the full patch to compute SSD, as shown in figure 8(b).

Proposed full-Z depth-aided inpainting

The synthesized depth map does not contain holes, thanks to the JPF method which projects the input depth map onto the virtual viewpoint while filling cracks and disocclusions. The patch Ψp to be filled in contains thus a depth value for each pixel, even for pixels in the hole region Ω. These depth values are close to the ground truth, because disocclusions are only filled in with background depth. The proposed modification is to use the depth value of all pixels in the patch, including those whose color is not known. Equation 14 is thus modified as follows:

Ψ q = arg min Ψq∈Φ {SSD Φ (Ψ p, Ψ q ) + α SSD Φ∪Ω (Z p, Z q )} (15)
Figure 8 shows the part of patch Ψp which is involved in SSD computation.

Results of the proposed full-Z depth-aided inpainting method are analyzed in section 5, and compared with results from the two other depth-aided inpainting methods.

Intermediate view interpolation with Floating Texture

Intermediate view rendering methods fill in disocclusions with texture information from many input views. The classical scheme works as follows: Intermediate views are first synthesized by projecting each input view onto the virtual viewpoint, using the backward projection described in figure 1 Colors represent directions, and luminosities represent norms.

Rendering Results

This section compares virtual view synthesis results obtained when using three depth-aided inpainting techniques for occlusion handling. For each inpainting techniques, the virtual depth maps are synthesized either by the classical scheme, shown in figure 1, or by the JPF method.

Figure 11 shows inpainting results of the algorithm presented in [START_REF] Daribo | Depth-aided image inpainting for novel view synthesis[END_REF]]. Figure 12 shows inpainting results of the algorithm presented in [START_REF] Gautier | Depth-based image completion for view synthesis[END_REF].

Figure 13 shows inpainting results of the proposed full-Z depth-aided inpainting algorithm. In each figure, the first column shows a virtual view synthesized by the backward projection, where disocclusions appear in white.

The second column shows the virtual depth map where disocclusions are filled in with a Navier-strokes inpainting algorithm [START_REF] Bertalmío | Navierstokes, fluid dynamics, and image and video inpainting[END_REF], whereas the fourth column shows the depth map synthesized with our JPF method. The third and the fifth columns show the results of the depth-aided inpainting method, led by the depth map respectively presented in column 2 and 4.

One can observe that the depth maps shown in column 2 are not realistic because depth discontinuities do not fit with object boundaries. This is due to the depth map inpainting method, which fills disocclusions with both background and foreground values. On the contrary, depth maps presented in column 4 are closer to the ground truth, thanks to the JPF method. Small details are well preserved by the projection, as fingers on row 3 or blades of grass on row 4.

The influence of the virtual depth map can be observed by comparing column 3 and 5 of each figure. Errors in depth map from column 2 are amplified by every depth-aided inpainting method, because some foreground patches are selected to fill in disocclusions. The resulting images, shown in column 3, contain more artifacts than the ones obtained with a correct depth map.

Depth-aided inpainting methods can be compared with each other by analyzing the fifth column of each figure. Rendering results shown in figures 11 and 12 still contains blur artifacts along boundaries, even if the correct depth map is used to conduct the inpainting process. The proposed full-Z depth-aided inpainting method preserves small details, as fingers on row 3 or blades of grass on row 4.

As a conclusion, the quality of the rendered view is strongly dependent on the quality of the virtual depth map, no matter the depth-aided inpainting method. Synthesizing high quality virtual depth map is thus an interesting challenge for DIBR techniques. The JPF method is well suited for this purpose, because connectivity information is used during the forward projection. Moreover, the proposed full-Z depth-aided inpainting method improves upon state-of-the-art methods by taking into account the correctness of the synthesized depth map.

Conclusion

This article describes two DIBR techniques, relying on the Joint Projection Filling (JPF) method to improve the rendering quality. The first DIBR technique is a virtual view extrapolation, based on a depth-aided inpainting technique. The JPF method is used here to synthesize the depth map of the virtual view without errors, in order to conduct the depth-aided inpainting. The depth-aided inpainting takes into account the high quality of the generated depth map to select correct patches to be duplicated.

The second DIBR technique is an virtual view interpolation method, which uses the Floating Texture algorithm [START_REF] Eisemann | Floating textures[END_REF] to sharpen the final view. The JPF method is used here to produce intermediate views without cracks nor disocclusions, in order to process the optical flow estimation. Columns 2 and 4 present the synthesized depth maps, obtained respectively with a Navier-strokes inpainting algorithm [START_REF] Bertalmío | Navierstokes, fluid dynamics, and image and video inpainting[END_REF]Bertalmío, Bertozzi, and Sapiro] and with our JPF method.

Columns 3 and 5 exhibit the results of the inpainting of the texture shown in column 1, guided by the depth map respectively presented in columns 2 and 4.

Figure 1 :

 1 Figure1: Classical scheme for virtual view extrapolation from a single input view plus depth video sequence. First, the input depth map is projected onto the virtual viewpoint. Second, the resulting depth map is filtered to avoid cracks and ghosting artifacts. Third, the filtered depth map is projected back onto the reference viewpoint to find the color of each pixel. Fourth, the depth map is inpainted to fill in disocclusions. Finally, the inpainted depth map is used to conduct disocclusions filling of the color map (synthesized view).

  (a) Forward Projection (FP). (b) FP + Directional inpaint.(c) Proposed JPF method.

Figure 2 :

 2 Figure 2: Virtual depth map synthesized by three forward projection methods. The point-based projection method generates cracks and disocclusions 2(a). Median filtering and directional inpainting [Nguyen et al(2009)Nguyen, Do, and Patel] fills some holes with foreground depth 2(b). The proposed JPF method fills cracks and disocclusions with realistic background 2(c).

  Eisemann, De Decker, Magnor, Bekaert, de Aguiar, Ahmed, Theobalt, and Sellent], the authors propose to compute an optical flow on intermediate rendered views, and then, with the help of the optical flow, to perform a registration step before the blending step, in order to avoid blurring in the final view due to blending mis-registered views. Note that specific representations such as Layered Depth Videos (LDV) can also be helpful for addressing the problem of occlusion handling since they allow storing texture information seen by other cameras[START_REF] Shade | Layered depth images[END_REF]Shade, Gortler, He, and Szeliski, Yoon et al(2007)[START_REF] Yoon | A framework for representation and processing of multi-view video using the concept of layered depth image[END_REF] Ho, Müller et al(2008a)Müller, Smolic, Dix, Kauff, and Wiegand, Jantet et al(2009)Jantet, Morin, and Guillemot].

Figure 5 :

 5 Figure 5: Comparison between synthesized depth maps from a forward point-based projection (first row) and from the JPF method (second row). Blurred depth discontinuities in the original depth map produces stretching effects on the synthesized depth maps. Note that McMillan scanning order is from right to left in figures 5(a) and 5(b), whereas it is from left to right in figures 5(c) and 5(d), due to epipole location for input images pairs.

Figure 6 :

 6 Figure 6: Warping results of the JPF method.

Figure 7 :

 7 Figure 7: Notation diagram, introduced by Criminisi et al. [Criminisi et al(2003)Criminisi, Pérez, and Toyama].Given the block Ψ p , n p is the normal to the contour δΩ of the hole region Ω. Φ is the non-hole region. ∆I ⊥ p is the isophote at point p.

Figure 9 :

 9 Figure 9: Floating Texture scheme for intermediate view synthesis. Each input view is projected onto the virtual viewpoint, using the Joint Projection Filling (JPF) method to fill in disocclusions and preserve contours. Projected views are realigned with the Floating Texture algorithm, then blended together with a weighting based on the virtual view position and confidence score.

  et al(2007)Zach, Pock, and Bischof].

Figure 10 :

 10 Figure 10: Results of Floating Texture algorithm for view synthesis from multiple views.

Figure 10

 10 Figure 10 presents an intermediate view, rendered by our proposed method. Blending intermediate views together, weighted by the confidence score, allows us to fill in disocclusions with real texture. Blurring artifacts may appear if intermediate views are misaligned, as shown in figure 10(a). Applying the Floating Texture approach removes blur on contours and texture details are enhanced, as shown in figure 10(b). One of the flow fields estimated with the method proposed in [Zach et al(2007)Zach, Pock, and Bischof] is shown in figure 10(c).

  The JPF method is based onMcMillan's occlusion-compatible ordering introduced in [McMillan(1995)].It allows cracks handling and disocclusions filling by ensuring that only background pixels are used during interpolation. The confidence-based pixels shifting avoids ghosting artifacts and texture stretching while sharpening discontinuities. In terms of computational complexity, this JPF method is equivalent to classical point-based projection and can be used with non-rectified views. Synthesized depth maps are very similar to ground truth depth maps.

Figure 11 :

 11 Figure 11: Results for Daribo depth-aided inpainting[START_REF] Daribo | Depth-aided image inpainting for novel view synthesis[END_REF]]. The first column shows a synthesized view with disocclusions. Columns 2 and 4 present the synthesized depth maps, obtained respectively with a Navier-strokes inpainting algorithm[START_REF] Bertalmío | Navierstokes, fluid dynamics, and image and video inpainting[END_REF]Bertalmío, Bertozzi, and Sapiro] and with our JPF method. Columns 3 and 5 exhibit the results of the inpainting of the texture shown in column 1, guided by the depth map respectively presented in columns 2 and 4.

Figure 12 :

 12 Figure 12: Results for Gautier depth-aided inpainting [Gautier et al(2011)Gautier, Le Meur, and Guillemot]. The first column shows a synthesized view with disocclusions.Columns 2 and 4 present the synthesized depth maps, obtained respectively with a Navier-strokes inpainting algorithm[START_REF] Bertalmío | Navierstokes, fluid dynamics, and image and video inpainting[END_REF]Bertalmío, Bertozzi, and Sapiro] and with our JPF method.Columns 3 and 5 exhibit the results of the inpainting of the texture shown in column 1, guided by the depth map respectively presented in columns 2 and 4.

Figure 13 :

 13 Figure 13: Results for proposed full-Z depth-aided inpainting. The first column shows a synthesized view with disocclusions. Columns 2 and 4 present the synthesized depth maps, obtained respectively with a Navierstrokes inpainting algorithm [Bertalmío et al(2001)Bertalmío, Bertozzi, and Sapiro] and with our JPF method. Columns 3 and 5 exhibit the results of the inpainting of the texture shown in column 1, guided by the depth map respectively presented in columns 2 and 4.


Olivier Le Meur

Josselin Gautier

Christine Guillemot

EXAMPLAR-BASED INPAINTING BASED ON LOCAL GEOMETRY

Keywords: inpainting, tensor, examplar-based

In this paper, we propose a novel inpainting algorithm combining the advantages of PDE-based schemes and examplar-based approaches. The proposed algorithm relies on the use of structure tensors to define the filling order priority and template matching. The structure tensors are computed in a hierarchic manner whereas the template matching is based on a K-nearest neighbor algorithm. The value K is adaptively set in function of the local texture information. Compared to two state of the art approaches, the proposed method provides more coherent results.

INTRODUCTION

Inpainting methods play an important role in a wide range of applications. Removing text and advertisements (such as logos), removing undesired objects, noise reduction [START_REF] Weickert | An anisotropic diffusion algorithm with optimized rotation invariance[END_REF] and image reconstruction from incomplete data are the key applications of inpainting methods. There are two algorithm categories: PDE (Partial Derivative Equation)-based schemes [START_REF] Tschumperlé | Vector-valued image regularization with pdes: a common framework for different applications[END_REF] and examplar-based schemes [START_REF] Criminisi | Region filling and object removal by examplar(based image inpainting[END_REF]. The former uses diffusion schemes in order to propagate structures in a given direction. The drawback is the introduction of blur due to diffusion. The latter relies on the sampling and the copying of texture from the known parts of the picture. In this paper, we propose a novel inpainting algorithm combining the advantages of both aforementioned methods. As in [START_REF] Criminisi | Region filling and object removal by examplar(based image inpainting[END_REF], the proposed method involves two steps: first, a filling order is defined to favor the propagation of structure in the isophote direction. Second, a template matching is performed in order to find the best candidates to fill in the hole. Compared to previous approaches, the main contributions are fourfold: the first one concerns the use of structure tensors to define the filling order instead of field gradients. Second is to use a hierarchical approach to be less dependent on the singularities of local orientations. Third is related to constraining the template matching to search for best candidates in the isophote directions. Fourth is a K-nearest neighbor approach to compute the final candidate. The number K depends on the local context centered on the patch to be filled in. The paper is organized as follows. Section 2 describes the proposed method. Section 3 presents the performance of the method and a comparison with existing approaches. Section 4 concludes the paper.

ALGORITHM DESCRIPTION

The goal of the proposed approach is to fill in the unknown areas of a picture I by using a patch-based method. As in [START_REF] Criminisi | Region filling and object removal by examplar(based image inpainting[END_REF], the inpainting is carried out in two steps: (i) determining the filling order; (ii) propagating the texture. We use almost the same notations as in [START_REF] Criminisi | Region filling and object removal by examplar(based image inpainting[END_REF]. They are briefly summarized below:

• the input picture noted I. Let I : Ω → R n be a vector-valued data set and Ii represents its i-th component;

• the region to be filled noted Ω;

• the source region noted φ, (φ = I -Ω);

• a square block noted ψp, centered at the point p located near the front line.

The differences between the approach in [START_REF] Criminisi | Region filling and object removal by examplar(based image inpainting[END_REF] and the proposed one are on one hand the use of structure tensors and on the other hand the use of a hierarchical approach. In the following, we first describe the algorithm for a unique level of hierarchical decomposition and then we describe how the hierarchical approach is used.

For one level of the hierarchical decomposition

As previously mentioned, the proposed approach follows the approach in [START_REF] Criminisi | Region filling and object removal by examplar(based image inpainting[END_REF] in the way that the inpainting is made in two steps. In a first step, a filling priority is computed for each patch to be filled. The second step consists in looking for the best candidate to fill in the unknown areas in decreasing order of priority. These two steps are described in the following sections.

Computing patch priorities

Given a patch ψp centered at the point p (unknown pixel) located near the front line, the filling order (also called priority) is defined as the product of two terms:

P (p) = C(p)D(p).
The first term, called the confidence, is the same as in [START_REF] Criminisi | Region filling and object removal by examplar(based image inpainting[END_REF]. It is given by:

C(p) = q∈ψp∩(I-Ω) C(q) |ψp| ( 1
)
where |ψp| is the area of ψp. This term is used to favor patches having the highest number of known pixels (At the first iteration,

C(p) = 1 ∀p ∈ Ω and C(p) = 0 ∀p ∈ I -Ω).
The second term, called the data term, is different from [START_REF] Criminisi | Region filling and object removal by examplar(based image inpainting[END_REF]. The definition of this term is inspired by PDE regularization methods acting on multivalued images [START_REF] Tschumperlé | Fast anisotropic smoothing of multi-valued images using curvature-preserving pde's[END_REF]. The most efficient PDE-based schemes rely on the use of a structure tensor from which the local geometry can be computed. As the input is a multivalued image, the structure tensor, also called Di Zenzo matrix [START_REF] Zenzo | A note on the gradient of a multi-image[END_REF], is given by: J is the sum of the scalar structure tensors ∇Ii∇I T i of each image channel Ii (R,G,B). The structure tensor gives information on orientation and magnitudes of structures of the image, as the gradient would do. However, as stated by Brox et al. [START_REF] Brox | Nonlinear structure tensors[END_REF], there are several advantages to use a structure tensor field rather than a gradient field. The tensor can be smoothed without cancellation effects : J σ = J * Gσ where Gσ = 1 2πσ 2 exp(-x 2 +y 2 2σ 2 ), with standard deviation σ. In this paper, the standard deviation of the Gaussian distribution is equal to 1.0. The Gaussian convolution of the structure tensor provides more coherent local vector geometry. This smoothing improves the robustness to noise and local orientation singularities. Another benefit of using a structure tensor is that a structure coherence indicator can be deduced from its eigenvalues. Based on the discrepancy of the eigenvalues, this kind of measure indicates the degree of anisotropy of a local region. The local vector geometry is computed from the structure tensor J σ . Its eigenvectors v1,2 (vi ∈ R n ) define an oriented orthogonal basis and its eigenvalues λ1,2 define the amount of structure variation. v1 is the orientation with the highest fluctuations (orthogonal to the image contours), and v2 gives the preferred local orientation. This eigenvector (having the smallest eigenvalue) indicates the isophote orientation. A data term D is then defined as [START_REF] Weickert | Coherence-enhancing diffusion filtering[END_REF]:

J = n i=1 ∇Ii∇I T i ( 2
) (a) (b) (c) (d)
D(p) = α + (1 -α)exp - η (λ1 -λ2) 2 (3)
where η is a positive value and α ∈ [0, 1] (η = 8 and α = 0.01). On flat regions (λ1 ≈ λ2), any direction is favored for the propagation (isotropic filling order). When λ1 >> λ2 indicating the presence of a structure, the data term is important.

Figure 1 shows the isophote directions (a) and the value of the coherence norm ( λ 1 -λ 2 λ 1 +λ 2 ) 2 (b). Black areas correspond to areas for which there is no dominant direction.

Propagating texture and structure information

Once the priority P has been computed for all unknown pixels p located near the front line, pixels are processed in decreasing order of priority. This filling order is called percentile priority-based concentric filling (PPCF). PPCF order is different from Criminisi's approach. Criminisi et al. [START_REF] Criminisi | Region filling and object removal by examplar(based image inpainting[END_REF] updated the priority term after filling a patch and systematically used the pixel having the highest priority. The advantage is to propagate the structure throughout the hole to fill. However, this advantage is in a number of cases a weakness. Indeed, the risk, especially when the hole to fill is rather big, is to propagate too much the image structures. The PPCF approach allows us to start filling by the L% pixels having the highest priority. The propagation of image structures in the isophote direction is still preserved but to a lesser extent than in [START_REF] Criminisi | Region filling and object removal by examplar(based image inpainting[END_REF]. Once the pixel having the highest priority is found, a template matching based on the sum of squared differences (SSD) is applied to find a plausible candidate. SSD is computed between this candidate (entirely contained in φ) and the already filled or known pixels of ψp. Finally, the best candidate is chosen by the following formula:

ψ q = arg min ψq ∈W d(ψ p , ψq) (4)
where d(., .) is the SSD. Note that a search window W centered on p is used to perform the matching.

Finding the best candidate is fundamental for different reasons. The filling process must ensure that there is a good matching between the known parts of ψp and a similar patch in φ in order to fill the unknown parts of ψp. The metric used to evaluate the similarity between patches is then important to propagate the texture and the structure in a coherent manner. Moreover, as the algorithm is iterative, the chosen candidate will influence significantly the result that will be obtained at the next iteration. An error leading to the apparition of a new structure can be propagated throughout the image.

In order to improve the search for the best candidate, the previous strategy is modified as follows:

ψ q = arg min ψq ∈φ d(ψ p , ψq) + ( λ1 -λ2 λ1 + λ2 ) 2 × f (p, q) (5)
where the first term d(., .) is still the SSD and the second term is used to favor candidates in the isophote direction, if any. Indeed, the term ( λ 1 -λ 2 λ 1 +λ 2 ) 2 is a measure of the anisotropy at a given position (as explained in section 2.1.1). On flat areas, this term tends to 0. The function f (p, q) is given by:

f (p, q) = 1 + |v2•vpq| vpq ( 6
)
where vpq is the vector between the centre p of patch ψp and the centre q of a candidate patch ψq. is a small constant value, set to 0.001. If the vector vpq is not collinear to the isophote direction (line of constant intensity), this candidate is penalized by computing the scalar product v2 • vpq. In the worst case (the two vectors are orthogonal), the penalization is equal to 1/ . When the two directions are collinear, the function f (p, q) tends to one. A K nearest neighbour search algorithm is also used to compute the final candidate to improve the robustness. We follow Wexler et al.'s proposition [START_REF] Wexler | Space-time completion of video[END_REF] by taking into account that all candidate patches are not equally reliable (see equation 3 of [START_REF] Wexler | Space-time completion of video[END_REF]). An inpainting pixel c is given by (ci are the pixels of the selected candidates): where si is the similarity measure between the current patch and a candidate i (see equation 2 of [START_REF] Wexler | Space-time completion of video[END_REF]). The Euclidean distance is used. Most of the time, the number of candidates K is fixed. This solution is not well adapted. Indeed, on stochastic or fine textured regions, as soon as K is greater than one, the linear combination systematically induces blur. One solution to deal with that is to locally adapt the value K. In this approach we compute the variance σ2 W on the search window. K is given by the function a + b 1+σ 2 W /T (in our implementation we use a = 1, b = 9 and T = 300. It means that we can use up to 10 candidates to fill in the holes). Figure 1 (c) and (b) shows the rendering of a fine texture with the best and the best ten candidates. For this example, good rendering quality is achieved by taking into account only the best candidate.

c = i sici i si (7)

Hierarchical decomposition

Previous sections described the proposed approach for a given pyramid level. One limitation concerns the computation of the gradient ∇I used to define the structure tensor. Indeed, as the pixels belonging to the hole to fill are initialized to a given value (0 for instance), it is required to compute the gradient only on the known part of the patch ψp. This constraint can have a negative effect on the final quality. To overcome this limitation, a hierarchical decomposition is used in order to propagate throughout the pyramid levels an approximation of the structure tensor. A Gaussian pyramid is then built with successive low-pass filtering and downsampling by 2 in each dimension leading to nL levels. At the coarsest level L0, the algorithm described in the previous section is applied. For a next pyramid level Ln, a linear combination between the structure tensors of level Ln and Ln-1(after upsampling) is performed:

J Ln h = ν × J Ln + (1 -ν)× ↑ 2(J L n-1 ) (8)
where J h is a structure tensor computed from a hierarchical approach. ↑ 2 is the upsampling operator. In our implementation, ν is fixed and set to 0.6. This hierarchical approach makes the inpainting algorithm more robust to local orientation singularities. At the coarsest level, the local structure tensor is a good approximation of the local dominant direction. Propagating such information throughout the pyramid decreases the sensitivity to local orientation singularities and noise. By default, nL is set to 3.

RESULTS

Figures 2 and4 show the performance of the proposed method. A comparison with Criminisi et al.'s1 and Tschumperlé et al.'s approach [START_REF] Tschumperlé | Vector-valued image regularization with pdes: a common framework for different applications[END_REF] is performed. Figure 2 depicts the results. The approach in [START_REF] Tschumperlé | Vector-valued image regularization with pdes: a common framework for different applications[END_REF] preserves quite well the images structures (except for the picture (c) of the second row) but the apparition of blur is annoying when filling large areas. On the first picture, results of the proposed and Criminisi's approach are similar. On the latter two, the proposed approach outperforms it. For instance, the roof as well as the steps of the third picture are much more natural than those obtained by Criminisi's method. The use of tensor and hierarchical approach brings an interesting visual gain 2 . For instance figure 3 shows the inpainted pictures with and without the hierarchical method. The same setting than the previous one is used. As illustrated by the figure, the unknown regions have been coherently reconstructed.

Except for the last picture, structures are well propagated without loss of texture information. A video clip showing how the proposed approach works is available on the author's web site.

CONCLUSION

In this paper, a novel inpainting approach is proposed. The novelties rely on the combination of advantages of PDE-based and examplarbased schemes. Structure tensors are computed in a hierarchic manner providing coherent information of local orientation as well as robustness to local orientation singularities. The filling process is based on a K-nearest neighbor approach for which the number of candidates used to fill in the hole is adaptively chosen in function of the local context. Compared to state-of-the-art methods, the proposed approach gives promising results. To enhance the robustness, local and dominant orientations (stemming from the structure tensors for the finest and the coarsest pyramid levels) might be used. Another point is related to the tuning of the proposed approach. For instance, the threshold T used to determine the number of candidate to use in the K-nearest neighbor approach is fundamental. Rather than using the local variance, it would be interesting to evaluate other criterion. Another improvement will focus on stochastic or inhomogeneous textures, for which repetitions of structure are absent. In this case, template matching fails to replicate this kind of texture in a coherent manner. Instead of using an exemplar-based method, it would be probably better to synthesize such texture by using stochastic-based texture models. It will be also required to compare the performance of the proposed approach to very recent methods such as [START_REF] Xu | Image inpainting by patch propagation using patch sparsity[END_REF]. Pictures used in this paper as well as software are available on http://www.irisa.fr/temics/staff/lemeur/publi/ 2011_ICIP/1/index.php .

ACKNOWLEDGEMENT

This work is supported by the French national program CONTINT through the project entitled PERSEE.

Fig. 1 .

 1 Fig. 1. (a) direction of the isophotes;(b) coherence norm: black areas correspond to areas for which there is no dominant direction; (c) Filling with the best candidate (K=1); (d) Filling with the best 10 candidates.

Fig. 2 .

 2 Fig. 2. Comparison of the proposed approach with the approaches [2, 3].

Figure 4 shows

 4 Figures2 and 4show the performance of the proposed method. A comparison with Criminisi et al.'s 1 and Tschumperlé et al.'s approach[START_REF] Tschumperlé | Vector-valued image regularization with pdes: a common framework for different applications[END_REF] is performed. Figure2depicts the results. The approach in[START_REF] Tschumperlé | Vector-valued image regularization with pdes: a common framework for different applications[END_REF] preserves quite well the images structures (except for the picture (c) of the second row) but the apparition of blur is annoying when filling large areas. On the first picture, results of the proposed and Criminisi's approach are similar. On the latter two, the proposed approach outperforms it. For instance, the roof as well as the steps of the third picture are much more natural than those obtained by Criminisi's method. The use of tensor and hierarchical approach brings an interesting visual gain 2 . For instance figure3shows the inpainted pictures with and without the hierarchical method. Figure4shows results on pictures belonging to Kawai et al.'s database[START_REF] Kawai | Image inpainting considering brightness change and spatial locality of textures and its evaluation[END_REF] 3 . Compared to previous assessment, these pictures have a smaller resolution (200 × 200 pixels) than those used previously (512 × 384).

Fig. 4 .Fig. 3 .

 43 Fig.4. Results of the proposed approach on pictures proposed by[START_REF] Kawai | Image inpainting considering brightness change and spatial locality of textures and its evaluation[END_REF].

Matlab implementation available on http://www.cc. gatech.edu/ ˜sooraj/inpainting/.

see http://www.irisa.fr/temics/staff/lemeur/ to have more results.

http://yokoya.naist.jp/research/ inpainting/.


Josselin Gautier

Olivier Le Meur

Christine Guillemot

DEPTH-BASED IMAGE COMPLETION FOR VIEW SYNTHESIS

Keywords: DIBR, FTV, 3DTV, view synthesis, image completion, exemplar-based inpainting

This paper describes a depth-based inpainting algorithm which efficiently handles disocclusion occurring on virtual viewpoint rendering. A single reference view and a set of depth maps are used in the proposed approach. The method not only deals with small disocclusion filling related to small camera baseline, but also manages to fill in larger disocclusions in distant synthesized views. This relies on a coherent tensor-based color and geometry structure propagation. The depth is used to drive the filling order, while enforcing the structure diffusion from similar candidate-patches. By acting on patch prioritization, selection and combination, the completion of distant synthesized views allows a consistent and realistic rendering of virtual viewpoints.

INTRODUCTION

3DTV and FTV are promising technologies for the next generation of home and entertainment services. Depth Image Based Rendering (DIBR) are key-solutions for virtual view synthesis on multistereoscopic display from any subset of stereo or multiview plus depth (MVD) videos. Classical methods use depth image based representations (MVD, LDV [START_REF] Shade | Layered depth images[END_REF]) to synthesize intermediate views by mutual projection of two views. Then, disoccluded areas due to the projection of the first view to the new one could be filled in with the remaining one.

However, in freeviewpoint video (FVV) applications, larger baseline (distance or angle between cameras) involves larger disoccluded areas. Traditional inpainting methods are not sufficient to complete these gaps. To face this issue the depth information can help to guide the completion process.

The use of depth to aid the inpainting process has already been considered in the literature. Oh et al. [START_REF] Oh | Hole filling method using depth based in-painting for view synthesis in free viewpoint television and 3-d video[END_REF] based their method on depth thresholds and boundary region inversion. The foreground boundaries are replaced by the background one located on the opposite side of the hole. Despite the use of two image projections, their algorithm relies on an assumption of connexity between disoccluded and foreground regions, which may not be verified for high camera baseline 978-1-61284-162-5/11/$26.00 c 2011 IEEE configurations. Indeed, upon a certain angle and depth, the foreground object does not border the disoccluded part anymore. Daribo et al. [START_REF] Daribo | Depth-aided image inpainting for novel view synthesis[END_REF] proposed an extension to the Criminisi's [START_REF] Criminisi | Region filling and object removal by exemplar-based image inpainting[END_REF] algorithm by including the depth in a regularization term for priority and patch distance calculation. A prior inpainting of the depth map was performed.

Our approach relies on the same idea. However, our contributions are threefold. The relevance of patch prioritization is improved by first using the depth as a coherence cue through a 3D tensor, and then by using a directional term preventing the propagation from the foreground. A combination of the K-nearest neighbor candidates is finally performed to fill in the target patch.

We present in Section 2 contributions to this priority calculation, based on tensor and then on depth, before describing depth-based patch matching. Section 3 describes the implementation of the method in a MVD context. Results are given in Section 4, as well as a comparison with existing approaches. Conclusions are drawn in Section 5.

ALGORITHM

The motivation to use a Criminisi-based algorithm resides in its capacity to organize the filling process in a deterministic way. As seen in fig. 1, this technique propagates similar texture elements Ψ q to complete patches Ψ p along the structure directions, namely the isophotes. Their algorithm basically works in two steps. The first step defines the higher order patch priorities along the borders δΩ. The idea is to start from where the structure is the strongest (in term of local intensity, with D(p)) and from patches containing the highest number of known pixels, C(p). The priority is then expressed as P (p) = D(p) × C(p). The second step consists in searching for the best candidate in the remaining known image in decreasing priority order.

In the context of view synthesis, some constraints can be added to perform the inpainting and improve the natural aspect of the final rendering. The projection in one view will be along the horizontal direction. For a toward-right camera movement the disoccluded parts will appear on the right of their previously occluding foreground (Fig. 1a), and oppositely for a toward-left camera movement. Whatever camera's movement, these disoccluded areas should always be filled in with pixels from the background rather than the foreground. Based on this a priori knowledge, we propose a depth-based image completion method for view synthesis based on robust structure propagation. In the following, D(p) is described.

Tensor-based priority

First, the data term D(p) of the inpainting method proposed by [START_REF] Criminisi | Region filling and object removal by exemplar-based image inpainting[END_REF] involving the color structure gradient is replaced with a more robust structure tensor. This term is inspired by partial differential equation (PDE) regularization methods on multivalued images and provides a more coherent local vector orientation [START_REF] Tschumperlé | Fast anisotropic smoothing of multi-valued images using curvature-preserving pde's[END_REF]. The Di Zenzo matrix [START_REF] Zenzo | A note on the gradient of a multi-image[END_REF] is given by:

J = l=R,G,B ∇I l ∇I T l = l=R,G,B ∂I l ∂x 2 ∂I l ∂x ∂I l ∂y ∂I l ∂x ∂I l ∂y ∂I l ∂y 2
with ∇I l the local spatial gradient over a 3x3 window. This tensor can also be smoothed with a gaussian kernel G σ to give robustness to outliers, without suffering from cancellation effects. We call it J σ = J * G σ . Finally, the local vector orientation is computed from the structure tensor J σ . Its eigenvalues λ 1,2 reflect the amount of structure variation, while its eigenvectors v 1,2 define an oriented orthogonal basis. Of particular interest is v 2 the preferred local orientation and its "force" λ 2 . Based on the coherence norm proposed in [START_REF] Weickert | Coherence-enhancing diffusion filtering[END_REF], the data term D(p) is then defined as:

D(p) = α + (1 -α)exp -C (λ1 -λ2) 2
with C a constant positive value and α ∈ [0, 1]. Flat regions (when λ 1 ≈ λ 2 ) do not favor any direction, it is isotropic, while with strong edges (λ 1 >> λ 2 ) the propagation begins along the isophote.

Depth-aided and direction-aided priority

The priority computation has been further improved by exploiting the depth information, first by defining a 3D tensor product, secondly by constraining the side from where to start inpainting.

3D tensor

The 3D tensor allows the diffusion of structure not only along color but also along depth information. It is critical to jointly favor color structure as well as geometric structure. The depthaided structure tensor is extended with the depth map taken as an additional image component Z:

J = l=R,G,B,Z ∇I l ∇I T l 2.2.

One side only priority

The second improvement calculates the traditional priority term along the contour in only one direction. Intuitively, for a camera moving to the right, the disocclusion holes will appear to the right of foreground objects, while out-of-field area will be on the left of the former left border (in orange in Fig. 1a). We then want to prevent structure propagation from foreground by supporting the directional background propagation, as illustrated in Fig. 1b with the blue arrows.

The patch priority is calculated along this border, the rest of the top, bottom and left patches being set to zero. Then for disocclused areas, the left border possibly connex to foreground will be filled at the very end of the process. For out-offield areas, even if left borders are unknown, we will ensure to begin from the right border rather than possible top and bottom ones.

These two proposals have been included in the prioritization step.

Patch matching

Once we precisely know from where to start in a given projected image, it is important to favor the best matching candidates in the background only. Nevertheless, starting from a non-foreground patch does not prevent it from choosing a candidate among the foreground, whatever the distance metric used. Thus, it is crucial to restrict the search to the same depth level in a local window: the background. We simply favor candidates in the same depth range by integrating the depth information in the commonly used similarity metric, the SSD (Square Sum of Differences):

Ψ q = arg min Ψq∈Φ d(Ψ p, Ψ q ) with d = p,q∈Ψp,q∩Φ α l Ψ p -Ψ q 2
The depth channel is chosen to be as important as the color one (l ∈ R, G, B, Z with α R,G,B = 1 and α Z = 3). Then it will not prevent the search in foreground patches, but will seriously penalize and unrank the ones having a depth difference above, i.e in front of the background target patch.

As proposed by [START_REF] Wexler | Space-time completion of video[END_REF], a combination of the best candidates to fill in the target patch shows more robustness than just duplicating one. We use a weighted combination of the K-best patches depending on their exponential SSD distances to the original patch. (K = 5 in our experiments).

IMPLEMENTATION

Experiments are performed on an unrectified Multiview Videoplus-Depth (MVD) sequence "Ballet" from Microsoft [START_REF] Zitnick | High-quality video view interpolation using a layered representation[END_REF]. The depth maps are estimated through a color segmentation algorithm [START_REF] Zitnick | High-quality video view interpolation using a layered representation[END_REF] and are supplied with their camera parameters. The choice of this sequence is motivated by the wide baseline unrectified camera configuration as well as its highly depth-andcolor contrast resulting in distinct foreground-background.This makes the completion even more visible and the issue even more challenging.

First, the central view 5 is warped in different views. Standard cracks (unique vacant pixels) are filled in with an average filter. We then suppress certain ghosting effects present on the borders of disoccluded area in the background: the background ghosting. Indeed, as we start the filling process by searching from the border, it is of importance to delete ghostings containing inadequate foreground color values. A Canny edge detection on the original depth map, followed by a deletion of color pixels located behind that dilated border successfully removes this ghosting.

Finally, our inpainting method is applied on each warped image, using the depth of the final view. The depth inpainting issue is out of the scope of this paper, but encouraging methods are proposed in the literature [START_REF] Daribo | Depth-aided image inpainting for novel view synthesis[END_REF]. In the context of MVD applications, it is realistic to consider a separate transmission of depth information through geometric representation (currently under investigation).

RESULTS

Fig. 2 illustrates the results obtained with the proposed method, comparatively with methods from the literature [START_REF] Criminisi | Region filling and object removal by exemplar-based image inpainting[END_REF], [START_REF] Daribo | Depth-aided image inpainting for novel view synthesis[END_REF], when rendering views located at varying distances from the reference viewpoint. The three versions take in input the same color and depth information, except for the approach in [START_REF] Criminisi | Region filling and object removal by exemplar-based image inpainting[END_REF] using color only. Our method not only preserves the contour of foreground persons, but also successfully reconstructs the structure of missing elements of the disoccluded area (i.e. edges of the curtains and bars behind the person on the right, background wall behind the left one).

Thanks to our combination term, we can even extend the synthesis to very distant views, without suffering of aliasing effects. As illustrated, the view 5 is projected to view 2 (V 5→2 ) and the out-of-field blank areas occupying one quarter width of the warped image are reconstructed. The counterpart of the patch combination is the smoothing effect appearing on the bottom part of this area. By taking different numbers of patches for combination, it is possible to limit this effect. We encourage people to refer to additional results available on our webpage 1 with videos illustrating the priority-based progressive inpainting principle. The results can indeed be essentially address visually, as argued by [START_REF] Kawai | Image inpainting considering brightness change and spatial locality of textures[END_REF].

1 http://www.irisa.fr/temics/staff/gautier/inpainting

CONCLUSION AND PERSPECTIVES

A robust depth based completion method for view synthesis has been presented. We address the disocclusion issue by going beyond the limitations of scene warping. To start inpainting, coherent depth and color structures are favored along contour through a robust tensor-based isophote calculation while directional inhibition prevents to start from foreground borders. For target patch propagation, a combination of closest geometric and photoconsistent candidates manages effective natural filling. Future works will focus on completion of synthesized views extremely far from the reference view. The natural aspect of this filling in situation, i.e for video, will also be investigated. (e) V 5→4 inpainted with Daribo's method (f) V 5→2 inpainted with Daribo's method (g) V 5→4 inpainted with our method (h) V 5→2 inpainted with our method Fig. 2. Illustration of different methods of inpainting. Our approach relying on 3D tensor and directional prioritization shows efficient filling.

Fig. 1 .

 1 Fig. 1. Illustration of principle. On (a) a warped view, (b) a zoom on the disoccluded area behind the person on the right, with the different elements overlaid.

  (a) V 5→4 after warping and background antighosting (b) V 5→2 after warping and background antighosting (c) V 5→4 inpainted with Criminisi's method (d) V 5→2 inpainted with Criminisi's method

ACKNOWLEDGMENT

The authors would like to thank I. Daribo and B. Pesquet for providing their source code, and P. Pérez for inspiring discussions. This work was supported by ANR through the Persée project.