Chapter 1 Executive Summary

This document describes texture analysis tools developed in the framework of the PERSEE project to be used both for prediction in 2D and 3D video codecs as well as in the rendering step of the 3D coding/transmission/rendering chain. Texture synthesis and image inpainting techniques have shown remarkable progresses over the past years and appear to be promising directions for a number of image processing problems: compression, loss concealment, and hanlding of disocclusions in the context of virtual view synthesis for free viewpoint navigation.

Existing methods include parametric techniques based on a parameterized texture model, non parametric methods, or graph-cut techniques which aim at preserving structural continuity. In parametric and non-parametric synthesis techniques, the Probability Density Function (PDF) of a given texture example is approximated and sampled to generate similar texture samples. Parametric synthesis approaches approximate the PDF of the texture using a compact model. Non-parametric approaches typically formulate the texture synthesis problem based on Markov Random Fields (MRF). Another family of techniques based on sparse approximations has also apperaed recently for texture synthesis in contexts of prediction and inpainting.

In this deliverable, new methods of prediction and inpainting inspired from examplarbased techniques which have been developed in the PERSEE project are described. The key contributions underlying these new methods concern the introduction of new priority terms for processing the patches to be completed as well as the approximation methods which are based on neighbor embedding techniques rather than simple template matching. These methods have been used both for prediction and inpainting. The resulting prediction technique (described in Chapter 2) has been integrated and evaluated in a still image codec. A solution based on a particular neighbor embedding, which can be seen as an average of template mathcing, has also been integrated as in an HEVC-based video codec, and assessed in this context. A new examplar-based inpainting method has been developed and is presented in Chapter 3.

These solutions have then been used for handling disocclusions which occur when extrapolating virtual view from one single 2D+depth input view or when interpolating virtual views from multiple input video plus depth views. Towards this goal, the priority computation has been extended in prder to take into account the depth information available in a 3D (multi-view plus depth) application. The resulting depth-aided inpainting technique, with the renedering results obtained, is described in Chapter 3Dinpainting.

In virtual view synthesis, these methods for disocclusion handling in general follow a step which consists in projecting the input view unto the virtual view point. Both processesinpainting and projection -can thus benefit from a coupling of the two steps. This was the scope of another direction axis of the project. This led to the introduction of a joint projection/inpainting technique which is described in Chapter 5.

These results have been published in international journals [START_REF] Turkan | Image prediction based on neighbor embedding methods[END_REF], [START_REF] Jantet | Joint projection filling method for occlusion handling in depth-image-based rendering[END_REF] and in international conferences [START_REF] Gautier | DEPTH-BASED IMAGE COMPLETION FOR VIEW SYNTHESIS[END_REF], [START_REF] Le Meur | EXAMPLAR-BASED INPAINTING BASED ON LOCAL GEOMETRY[END_REF], [START_REF] Turkan | Image prediction based on non-negative matrix factorization[END_REF].

Chapter 2

Texture synthesis for image prediction

Closed-loop intra prediction is a key component of image compression algorithms. For example, in H.264/AVC, there are two intra-frame prediction types called Intra-16x16 and Intra-4x4 [START_REF] Wiegand | Overview of the H.264/AVC video coding standard[END_REF]. Each 4x4 block is predicted from prior encoded pixels of spatially neighboring blocks. In addition to the so-called "DC" mode which consists in predicting the entire 4x4 block from the mean of neighboring pixels, eight directional prediction modes have been specified. The prediction is done by simply "propagating (interpolating)" the pixel values along the specified direction. This approach is suitable in the presence of contours when the directional mode chosen corresponds to the orientation of the contour. However, it fails in more complex textured areas.

An alternative spatial prediction algorithm based on template matching (TM) has been described in [START_REF] Tan | Intra prediction by template matching[END_REF]. A so-called template is formed by previously encoded pixels in the close neighborhood of the block to be predicted. The best match between the template of the block to be predicted and candidate texture patches of same shape as the template, within a causal search window, allows finding the predictor of the block to be predicted. The approach in [START_REF] Tan | Intra prediction by template matching[END_REF] has later been improved in [START_REF]Intra prediction by averaged template matching predictors[END_REF] by averaging multiple template matching predictors, including larger and directional templates, resulting in up to 15% rate saving when included into H.264/AVC intra-prediction.

A prediction algorithm based on sparse approximation techniques has been introduced in [START_REF] Martin | Sparse representation for image prediction[END_REF]. The goal of sparse approximation techniques (e.g., matching pursuit (MP) [START_REF] Mallat | Matching pursuit with time-frequency dictionaries[END_REF] or orthogonal matching pursuit (OMP) [START_REF] Pati | Orthogonal matching pursuit: Recursive function approximation with applications to wavelet decomposition[END_REF]) is to look for a linear expansion approximating the analyzed signal in terms of functions chosen from a large and redundant set (dictionary). In [START_REF] Martin | Sparse representation for image prediction[END_REF], image prediction is regarded as a problem of signal extension from noisy data taken from a causal neighborhood. The sparse signal approximation is run with a set of masked basis functions, the masked samples correspond to the location of the pixels to be predicted. The basic principle of the approach is to first search for a linear combination of masked basis functions which best approximates known sample values in a causal neighborhood (template), and keep the same linear combination of basis functions to approximate the unknown sample values in the block to be predicted. The stopping criterion (which is the energy of the residue signal) is computed on the known region. To compute it on the causal neighborhood would lead to a residue of small energy, however, this residue might take large values in the block to be predicted. The number of atoms (basis functions) selected in order to minimize a given criterion (i.e., the energy of the residue or a rate-distortion cost function) on the block to be predicted is transmitted to the decoder. The decoder similarly runs the algorithm with the masked basis functions by taking the previously decoded neighborhood as the known support. The number of atoms selected by the encoder can thus be used by the decoder as a stopping criterion.

Dictionaries formed by pre-defined DCT or DFT waveforms are used in [START_REF] Martin | Sparse representation for image prediction[END_REF]. These dictionaries are particularly well suited for predicting periodic texture patches. However, the prediction fails for more complex non-periodic structures with discontinuities. The authors in [START_REF] Turkan | Sparse approximation with adaptive dictionary for image prediction[END_REF] have considered instead dynamic and locally adaptive dictionaries formed by atoms derived from texture patches present in a causal neighborhood of the block to be predicted. The principle of the approach is thus to first search for a linear combination of image patches (stacked as columns in a matrix A called the dictionary) which best approximates the template, and then keep the same linear combination of co-locoted pixel values to approximate the unknown sample values in the block to be predicted. The use of several templates selected by the prediction or compression algorithm according to either a mean squared error (MSE) or a rate-distorion (RD) criterion allows improving the prediction or compression performance. This method can be seen as a generalization of template matching. The TM is indeed a special case when only one iteration is used with a weighting coefficient equal to 1. This method is referred to here as sparse prediction (SP).

In [START_REF]Image prediction based on non-negative matrix factorization[END_REF], the image prediction problem is placed in a context of data dimensionality reduction using the non-negative matrix factorization (NMF) [START_REF] Lee | Algorithms for non-negative matrix factorization[END_REF] algorithm. Given a fixed nonnegative dictionary (or basis functions), the underlying main idea is to first obtain an NMF representation of the support region (template) and keep the same representation parameters to approximate the unknown pixel values in the block to be predicted. This approach leads to very good compression performance (a PSNR gain of up to 3 dB when compared with the TM and the SP methods). Furthermore, it does not require sending extra information (as the iteration number in the SP method) but on the other hand, its high computational complexity, because of the update equations and the size of the fixed dictionary, makes difficult the use of several candidate templates.

In PERSEE, we have pushed further the study of image prediction based on dimensionality reduction algorithms by considering the two methods: NMF and locally linear embedding (LLE) [START_REF] Roweis | Nonlinear dimensionality reduction by locally linear embedding[END_REF]. We first introduce a sparsity constraint, which has already been included in the LLE algorithm implicitly, into the NMF based prediction method. In the classical method [START_REF] Hoyer | Non-negative matrix factorization with sparseness constraints[END_REF], the sparseness constraints in the NMF algorithm has been achieved by keeping the 2 norm unchanged and setting the corresponding 1 norm to the desired sparsity. Here, we propose an 0 norm sparsity constraint by initially selecting k, k = 1...K, patches to be used in the prediction algorithm. The main idea explored here is again to search for a linear combination to approximate the known pixel values in the template, and then keep the same weighting coefficient to estimate the pixels to be predicted as a linear combination of the co-located pixels in the k neareast neigbouring (k-NN) patches (for both the NMF and the LLE based methods). The parameter k controls the sparsity of the data approximation.

The proposed image prediction methods have been evaluated in a complete image codec, both strict and relaxed sparsity constraints (controlled by the parameter k). A detailed analysis has been carried out on the prediction quality and the encoding efficiency in comparison to the sparse approximation based method [START_REF] Turkan | Sparse approximation with adaptive dictionary for image prediction[END_REF] and also H.264/AVC intra image prediction. The results obtained show a significant improvement in terms of the rate-distotion gain of the reconstructed image, after coding and decoding the prediction residue (up to 2 dB and up to 1 dB) when compared to H.264/AVC intra prediction and to the sparse prediction respectively. Further RD Figure 2.1: C is the approximation support, B is the current block to be predicted, W is the window from which texture patches are taken to construct the dictionary to be used for the prediction of B, and S C ∪ B.

gains have been achieved with LLE based prediction method by relaxing the sparsity constraints and setting the parameter k to 100, or more, at the expense however of extra complexity.

Neighbor embedding techniques

Let S denote a region in the image containing a block B of n×n pixels and its causal neighborhood C used as approximation support (template) as shown in Fig. 2.1. In Fig. 2.1, the region S contains 4 blocks, hence is of size N = 4n 2 pixels, for running the prediction algorithm. However, we will see later (see Fig. 2.2) that different forms of template C can be considered. In any case, in the region S, there are known samples (the template C) and unknown samples (the values of the pixels of the block B to be predicted). The principle of the prediction approach is to first search for a good approximation for the known pixels in C and keep the same procedure to approximate the unknown pixel values in B.

Let A denote a so-called dictionary represented by a matrix of dimension N × M, where N ≤ M. In all prediction methods presented below (template matching, sparse prediction, NMF, and LLE), the dictionary A is constructed by stacking the luminance values of all patches (having the same geometric shape as S) in a given causal search window W in the reconstructed image region as shown in Fig. 2.1. The use of a causal window guarantees that the decoder can construct exactly the same dictionary.

We denote A c as the compacted dictionary matrix obtained by masking the rows of the matrix A which correspond to the spatial location of the pixels of the area B. The compacted matrix A c is of size 3n 2 × M. The N sample values of the region S are stacked in a vector b (by assuming the unknown values in B are equal to zero). The vector b is also compacted in the vector b c of 3n 2 values, the vector b c thus corresponds to the support region (template) C organized in a vector form. Let us define another matrix A t (of size n 2 × M) as the corresponding spatial dictionary obtained by masking the rows of A with respect to the spatial location of the pixels of the area C, and assume that b t and bt represent the actual and the predicted pixel values of the block B respectively.

Template Matching

The TM algorithm searches for the best match between the template b c and possible candidate patches (of the same shape as the template) stored in the columns of A c which are taken from the causal search window. The problem of template matching can thus be formulated as the search for the index j of the atom a c j in the dictionary A c (i.e., that is stacked in the j th column of the matrix A c ) which will minimize the distance d j as

j opt = arg min j∈{1...M} {d j } where d j = ||b c -a c j || 2 2 , j = 1...M. (2.1)
The signal b t is then simply predicted by copying the pixel values of the candidate a t j opt (i.e., that is stacked in the j th column of the matrix A t ) as bt = a t j opt .

Sparse Prediction (SP)

The principle of the sparse prediction approach is to first search for a linear combination of basis functions (atoms, or texture patches) taken from the compacted dictionary A c , which best approximates the template C, and then keep the same linear combination (the same indexes of atoms a t j in A t and the same weights) to approximate the unknown pixel values in B. Sparse representation algorithm aims at solving the approximate minimization as

x opt = min x b c -A c x 2 2 subject to min x 0 . (2.2)
In practice, one actually seeks an approximate solution which satisfies

min x 0 : b c -A c x 2 2 ≤ ρ , (2.3)
for some ρ ≥ 0 characterizing an admissible reconstruction error. Matching pursuit (MP) [START_REF] Mallat | Matching pursuit with time-frequency dictionaries[END_REF] and orthogonal matching pursuit (OMP) [START_REF] Pati | Orthogonal matching pursuit: Recursive function approximation with applications to wavelet decomposition[END_REF] algorithms have been introduced as heuristic methods to find approximate solutions to the above problem with tractable complexity.

In the sequel, the OMP algorithm is used and it proceeds as follows. At the first iteration x 0 = 0 and an initial residual vector r 0 = b c -A c x 0 = b c is computed. At iteration k, the algorithm identifies the atom a c j k in A c having the maximum correlation with the approximation error. Let A k c denote the compacted matrix containing all the atoms selected in the previous iterations. One then projects b c onto the subspace spanned by the columns of A k c , i.e., one solves min

x k b c -A k c x k 2 2 , (2.4)
and the coefficient vector at the k th iteration is given as

x k = (A k c T A k c ) -1 A k c T b c = A k c + b c , (2.5)
where A k c + represents the pseudo-inverse of A k c . Notice that here x k is a vector of coefficients. All the coefficients assigned to the selected atoms are recomputed at each iteration.

The algorithm at the encoder runs until a pre-specified iteration number K is reached by keeping track of the MSE or the RD cost function values obtained for the block to be predicted b t , and finally selects the number of atoms (i.e., image patches used) which minimizes the considered criterion, leading to an "optimum" sparse vector denoted x opt . The value of the number of atoms

: k = 0, x 0 = 0, r 0 = b c , A 0 c = [ ], A 0 t = [ ] do until k = K k = k + 1; j k = arg max j A T c r k-1 ; A k c = A k-1 c ∪ {a c j k } and A k t = A k-1 t ∪ {a t j k }; x k = A k c + b c ; r k = b c -A k c x k ; p k = A k t x k ; end do
Select the optimum k * minimizing the selected criterion; Set bt = p k * used is then transmitted to the decoder which can similarly search for the sparse approximation of the template (support region) with the signalled number of atoms. Note that template matching can be seen as a particular case of the sparse approximation where only one iteration is used and the weighting coefficient is equal to 1.

The prediction signal bt is then calculated by multiplying the matrix A t by x opt as bt = A t x opt . Note here that the columns (atoms) of A t are first to be normalized with the norm of corresponding columns of A c , i.e., a tm = a tm / a cm 2 ∀m, and then the atoms of A c are normalized in 2 norm. The complete sparse approximaton based image prediction algorithm is summarized in Table 2.1.

Average Template Matching (ATM)

ATM can be seen as a simple extension of TM where several patches are combined with uniform weights. The patch selection process generally proceeds by choosing K number of most similar patches to the template in the source image. After obtaining K nearest neighboring patches Ψ qk , k = 1...K, one uniformly combines colocated pixels of these patches in order to estimate the fill-in region values as follows

Ψ u p = 1 K K k=1 Ψ u qk .
(2.6)

Locally Linear Embedding

LLE [START_REF] Roweis | Nonlinear dimensionality reduction by locally linear embedding[END_REF] is a constrained optimization algorithm which solves the nonlinear data dimensionality reduction problem. LLE tries to find a global transformation of the high-dimensional coordinates into low-dimensional ones by exploiting the locally-linear characteristics of the high-dimensional data. It aims at preserving the local linear structure of the high-dimensional data in the lowerdimensional space.

Formally, given M high-dimansional data points consisting of N-real valued vectors X i , the LLE method consists of the following steps:

1. It first identifies K nearest neighbors X j per data point X i for all i, i = j. The usual measure is the Euclidean distance;

2. It then searches for the weights W i,j , so that each data point is approximated by its neighbors. The algorithm thus aims at minimizing the cost function,

E (W) = i X i - j W i,j X j 2 2
.

(2.7)

The weights W i,j represent the contribution of the j th data point to the reconstruction of the i th point, and they are constrained to sum to one, i.e., j W i,j = 1, ∀i. Each data point X i can only be reconstructed from its neighbors (i.e., W i,j = 0 if the data point X j does not belong to the neighbors of X i ). The optimal weights satisfying these constraints are obtained by solving the constrained least squares problem per data point X i as

E i (W j ) = j W j (X i -X j ) 2 2 subject to j W j = 1;
(2.8)

3. Finally, an embedding cost function is minimized in order to obtain the low-dimensional global internal coordinates Y i by fixing the weights W i,j as

ζ (Y) = i Y i - j W i,j Y j 2 2 .
(2.9)

Please see [START_REF] Roweis | Nonlinear dimensionality reduction by locally linear embedding[END_REF] for more information.

The LLE method (steps 1 and 2) is here first applied on the template C. One thus searches for an approximation of the template by a linear combination of its k-NN (k = 1...K) patches within the search window and then keeps the same weighting coefficients in the linear combination of the co-located pixels in order to estimate the unknown values of the block to be predicted. In terms of LLE based method, (2.2) can be re-written as

x opt = min x b c -A c x 2
2 subject to m x m = 1 and min x 0 .

(2.10)

A sparsity constraint has been imposed (also implicitly by the LLE) onto the problem by choosing k closest patches to b c in Euclidean space. At iteration k, suppose that A k c denotes the submatrix which contains the selected k atoms (texture patches) in A c . The algorithm thus tries to solve the constrained minimization as min .11) and the optimal weighting coefficients in x k are computed as

x k b c -A k c x k 2 2 subject to m x km = 1. ( 2
x k = D -1 k 1 1 T D -1 k 1 (2.12)
: k = 0, A 0 c = [ ], A 0 t = [ ] do until k = K k = k + 1; j k = arg min j {d j } where d j = b c -a c j 2 2 ; A k c = A k-1 c ∪ {a c j k } and A k t = A k-1 t ∪ {a t j k }; A c ← A c \{a c j k } and A t ← A t \{a t j k }; Calculate local covariance matrix D k of A k c ; Solve D k x k = 1 for x k ; x k = x k /sum(x k ); p k = A k t x k ; end do Select the optimum k * minimizing the selected criterion; Set bt = p k *
where D k denotes the local covariance matrix (i.e., in reference to b c ) of the selected k patches in A k c , and 1 is the column vector of ones. In practice, instead of an explicit inversion of the matrix D k , the linear system of equations D k x k = 1 is solved, then the weights are rescaled so that they sum to one.

Here also, the algorithm at the encoder keeps track of the MSE or the RD cost function values obtained for the block to be predicted and finally selects the number k of used patches which minimizes the considered criterion, leading to an "optimum" sparse vector denoted x opt . The value of the number k is then transmitted to the decoder which can similarly search for the same LLE approximation of the template with the signalled number. The predicted signal bt is then calculated by multiplying the dictionary A t by x opt as bt = A t x opt . The complete LLE based image prediction algorithm is summarized in Table 2.2.

Non-negative Matrix Factorization

NMF is a subspace approximation algorithm which finds a suitable low-rank representation of the high-dimensional data. In many data analysis tasks the data to be analysed is non-negative, and classical tools, e.g., principle component analysis (PCA) [START_REF] Jolliffe | Principle Component Analysis[END_REF], can not guarantee to maintain the non-negativity property of the original data in the low-dimensional space. NMF is a recent method for obtaining such a non-negative representation, which is indeed helpful for physical interpretation of the results in many data analysis tools such as dimensionality reduction, data mining, and noise removal.

Formally, given a non-negative matrix Φ ∈ R N×L and a positive integer M < min {N, L}, the aim is to find non-negative matrix factors A ∈ R N×M and Ψ ∈ R M×L , such that Φ ≈ AΨ where the reconstruction error between Φ and AΨ is minimized. The most widely used cost function is the squared Euclidean distance, i.e., min

A,Ψ 1 2 Φ -AΨ 2 F subject to A ≥ 0 and Ψ ≥ 0, (2.13)
and NMF algorithm is optimized with the multiplicative update equations as

Ψ aµ ← Ψ aµ A T Φ aµ (A T AΨ) aµ + ε , A ia ← A ia ΦΨ T ia (AΨΨ T ) ia + ε , (2.14)
where ε is a small constant equal to 10 -9 to avoid divide by zero in the update equations. Here, aµ (or ia) represents the a th (or i th ) row and µ th (or a th ) column elements of the corresponding matrices respectively. In the standard algorithm, the matrices A and Ψ are initialized with random non-negative values, and the Euclidean distance ||Φ -AΨ|| 2 F is decreasing under the above alternating update rules as proven in [START_REF] Lee | Algorithms for non-negative matrix factorization[END_REF].

The product AΨ is called an NMF of Φ, and the underlying features of Φ are extracted as basis vectors in A, which can then be used in data analysis tools instead of Φ. Note that Φ ≈ AΨ can be rewritten as b ≈ Ax where b and x represent the corresponding columns of Φ and Ψ respectively. One can interpret that a column vector b of Φ is approximated by a linear combination of the columns of dictionary A, weighted by the column vector x of Ψ.

Let us now come back to the problem of image prediction. Given a fixed non-negative dictionary A ∈ R N×M formed by texture patches as explained above, and the (non-negative) data vector b ∈ R N , the underlying basic idea is to first obtain an NMF representation x of the support region C and keep the same representation parameters (i.e., weighting coefficients in x) to approximate the unknown pixel values in the block to be predicted B. The non-negativity constraints are satisfied for both A and b, similarly for A c and b c , since the values in the spatial domain range between 0 and 255.

Assuming the compacted dictionary A c is fixed for the data vector b c , the NMF formulation for the representation vector x of b c can be written as

min x 1 2 b c -A c x 2 2 subject to x ≥ 0, (2.15)
and the multiplicative update equation for x becomes

x a ← x a A T c b c a (A T c A c x) a + ε , a = 1...M. (2.16)
Here again, a sparsity constraint can be imposed onto the prediction problem as in (2.2) by limiting the number of non-zero coefficients in x as

x opt = min x 1 2 b c -A c x 2 2
subject to x ≥ 0 and min x 0 .

(2.17)

The selection is done by choosing k-NN (k = 1...K) patches which are close to b c in Euclidean distance. At iteration k, the algorithm identifies k atoms a c j 1 , ..., a c j k in A c which are close to b c , and let A k c denote the compacted matrix containing all the atoms selected in the k th iteration. One then solves, min

x k 1 2 b c -A k c x k 2 2 subject to x k ≥ 0 (2.18)
by updating the non-negative and randomly initialized elements of x k as

x ka ← x ka A k c T b c a A k c T A k c x k a + ε , a = 1...k. (2.19)
Table 2.3: Non-negative Matrix Factorization based Image Prediction. The algorithm at the encoder, as in the prediction approach based on sparse approximations, keeps track of the MSE or the RD cost function values obtained for the block to be predicted and finally selects the number k of texture patches which minimizes the considered criterion, leading to an "optimum" sparse vector denoted x opt . The value of the number k is then transmitted to the decoder which can similarly search for the same NMF approximation of the template with the signalled number of atoms. In order to obtain the optimum weighting vector x opt , the update equation is iterated until a pre-defined iteration number T is reached, or the total change in the elements of the vector x is very small between two consecutive iterations t -1 and t, t = 1...T . The predicted signal bt is then calculated by multiplying the dictionary A t by x opt as bt = A t x opt . The complete NMF based image prediction algorithm is summarized in Table 2.3.

Input: A c , A t , b c , b t , K, T Output: Predicted values of unknowns bt Initialization: k = 0, A 0 c = [ ], A 0 t = [ ] do until k = K k = k + 1; j k = arg min j {d j } where d j = b c -a c j 2 2 ; A k c = A k-1 c ∪ {a c j k } and A k t = A k-1 t ∪ {a t j k }; A c ← A c \{a c j k } and A t ← A t \{a t j k }; initialize x k and t = 0; iterate until t = T , or change in x k is small t = t + 1; x k ← x k ⊗ A k c T b c A k c T A k c x k + 10 -9 ; end iterate p k = A k t x k ; end do Select the optimum k * minimizing the selected criterion; Set bt = p k *

Performance illustration for still image coding 2.2.1 Encoder Structure

The proposed NMF and LLE based spatial image prediction methods have been assessed in a still image (or intra frame) coding/compression scheme by comparing it to the TM and sparse prediction, on one hand as well as to the intra prediction approach based on H.264/AVC on the other hand. The performance assessment is done both in terms of prediction quality and PSNR/bit-rate efficiency.

In order to initialize the prediction process, the top 4 rows and left 4 columns of blocks of size 4x4 are predicted with H.264/AVC intra modes. Once a block has been predicted with the respective prediction method, the DCT transformed residue is quantized, zig-zag scanned, and encoded with an algorithm similar to JPEG. In this coding structure, a uniform quantization matrix with ∆ = 16 is weighted by a quality factor. The quality factor (q f ) is increased from 10 to 90 with a step size of 10, and the corresponding weight w q f is calculated by means of the following equation

w q f = 50/q f if q f ≤ 50 2 -0.02q f if q f > 50 . (2.20)
Image blocks are processed in a raster scan order, and the reconstructed image is obtained by adding the quantized residue to the prediction. A skip mode (the corresponding flag is arithmetically encoded) has also been included to the encoder to avoid coding the blocks of prediction residue in which all the transformed and quantized coefficients are zero.

Several forms of support regions (templates) are considered as shown in Fig. 2.2. The optimum template is selected among nine possible modes. The best mode, as well as the iteration number k for SP, and the number of used patches (also referred to here as k) for LLE and NMF, is selected according to two criteria:

• Minimization of the prediction MSE on the unknown block b t in order to observe the impact on the prediction quality;

• Minimization of an RD cost function of the form J RD = D + λR when the prediction is used in the coding scheme in order to observe the impact on the encoding efficiency. Here, D is the distortion (i.e., the sum of squared error (SSE)) of the reconstructed block (after adding the quantized residue to the prediction), and R is the residue encoding cost which is estimated as R = γ 0 M for low bit-rate compression [START_REF] Mallat | Analysis of low bit rate image transform coding[END_REF] with M being defined as the number of non-zero quantized DCT coefficients, and for DCT basis γ 0 = 6.5. By considering a uniform scalar quantizer with a quantization step ∆ (where the deadzone is equal to 2∆), the relation between the optimum Lagrange multiplier λ opt and the quantization step ∆ is given by [START_REF] Pennec | Sparse geometric image representations with bandelets[END_REF]

λ opt = 3∆ 2 4γ 0 . (2.21)
The optimization is done in two steps, i.e., first for the selection of iteration number k in the case of SP, or the optimal number of used patches, k, in the case of the NMF and LLE method, and then for the selection of template mode type. In terms of encoding, one needs to add the coding cost of side information, here it is the k value and the template type. This information is signalled to the decoder using Huffman codes.

Impact of Sparsity Constraint and Quantization Noise

In the prediction methods decsribed above, the dictionary A is constructed by stacking the luminance values of all patches (having the same geometric shape as S) in a given causal search region W in the reconstructed image region. When using those methods which are mainly based on the approximations of a template, a good approximation of the template does not necessarily lead to a good approximation of the unknown pixel values as the template and the unknown region pixels may have different characteristics. Furthermore, in an image coding context, at the decoder side the template information C, as well as the patches stored in the dictionary A, may not be clean depending on the prediction quality and the residue signal quantization. Therefore, it is crucial to analyse and to optimize the prediction quality of the unknown pixel values as a function of sparsity and the quantization noise. This sub-section briefly analyses the effect of the sparsity constraint on SP, LLE, and NMF based prediction methods in the case where the image signals are corrupted by various levels of quantization noise. Fig. 2.3 shows the mean prediction PSNR obtained for Barbara (512x512) and Foreman (CIF) images with varying sparsity contraints in the case where the image signals (i.e., blocks) are simply corrupted by a low (q f = 90), a medium (q f = 50), and a high (q f = 10) quantization noise with the quantization scheme as described in Sec. 2.2.1. The quality of predicted signal, in terms of mean PSNR, is significantly improved (up to 1.3 dB) with the NMF based prediction method when compared to TM and SP, even in the presence of a high quantization noise. In the LLE and SP based prediction methods, the mean prediction PSNR has its maximum when k ∈ [START_REF] Turkan | Image prediction based on neighbor embedding methods[END_REF][START_REF] Mallat | Matching pursuit with time-frequency dictionaries[END_REF] whereas NMF based prediction has its maximum PSNR when k ∈ [START_REF] Turkan | Image prediction based on neighbor embedding methods[END_REF][START_REF] Bertalmio | Image inpainting[END_REF]. Note here that the mean performance curves of NMF based method look noisy because of the randomization of the weighting coefficients. For each simulation point k, k = 1...50, the vector x k is initialized with the same seed of Mersenne twister random number generator.

Another interesting point might be further relaxing the sparsity constraint, which will increase the computational complexity however, for the sake of a complete analysis of the proposed prediction methods' global characteristics as a function of sparsity and the quantization noise. Fig. 2.4 shows the mean prediction PSNR obtained for Barbara and Foreman images for k ∈ [START_REF] Müller | View synthesis for advanced 3d video systems[END_REF]100]. The mean prediction performance for the LLE based method increases with the number of atoms (patches) used in the algorithm. However, adding more elements into the NMF model has negative effect on the performance as in the SP method. Here SP based method stops iterating for k > 48 since the template mode 1 has 48 known pixels in C for 4x4 block size. At iteration k = 48, the OMP algorithm constructs a complete orthogonal basis for the known values in C and the algorithm stops.

Experimental Setup

Three test images are chosen for the simulations as shown in Fig. 2.5. Foreman (the first frame in the CIF sequence) can be seen as the image which has mainly diagonal edges and smooth regions. Barbara (512 × 512) contains a combination of smooth and textural regions as well as the edges. Finally, Roof (512 × 512) contains highly textural regions. Two sets of tests have been carried out. The first one makes use of approximations with sparsity constraints. The number of iterations k, or equally the number of used patches considered in the k-NN search, is varied from 1 to 8, i.e., K = 8. The optimal k value in terms of the selected criterion (i.e., either the MSE or the RD) is then signalled to the decoder. The second set of experiments relax the sparsity constraint and take k = K = 100.

In the NMF based prediction method, the maximum iteration number for update equation (2. [START_REF] Pennec | Sparse geometric image representations with bandelets[END_REF]) is set to 100, i.e., T = 100, (see also Table 2.3). However, we have experimentally observed that the total change in the elements of x k gets very small for t > 5 in the smooth areas, and for t > 50 in the edgel areas. In the highly textural areas the algorithm iterates upto 100 iterations. Fig. 2.6 shows the configuration of the search window for 4x4 block size that is used in the simulations reported in this paper. All possible unique image patches in the search region are extracted to construct the dictionary matrix A.

Prediction performance with MSE criterion

Fig. 2.7 and Fig. 2.8 demonstrate visually the prediction performance for the test images, a textural region in Barbara and an edgel region in Foreman images respectively. The optimization criterion is the minimization of the prediction MSE, and q f = 10 (i.e., at low bit-rates). The sparsity constraint has been used for these experiments, k is varied from 1 to 8 for SP, NMF and based intra prediction especially for the image regions which contain complex textural structures and edges. Note here that the performance images shown here do not take the encoding cost of residue and the side information into account but only the prediction quality in terms of MSE. Therefore, it is informative rather than conclusive in terms of rate-distortion performance.

Compression performance with RD criterion

Fig. 2.9 shows the total encoding PSNR/bit-rate performance for the test images where the optimization criterion is the minimization of the RD cost function. One can observe that the proposed prediciton methods with NMF and LLE improve the encoding performance of the images especially containing textural regions when compared to the SP and H.264/AVC intra prediction. A gain up to 2 dB has been achieved by the NMF based method when compared to H.264/AVC, and up to 1 dB in comparison with the sparse prediction method. Furthermore, Texture synthesis for 2D/3D image inpainting Image inpainting refers to methods which consist in filling-in missing regions (holes) in an image [START_REF] Bertalmio | Image inpainting[END_REF]. Inpainting techniques find applications in a number of image processing problems: image editing (e.g. object removal), image restoration, object disocclusion in image based rendering, image coding, loss concealment after impaired transmission. Existing methods can be classified into two main categories. The first category concerns diffusion-based approaches which propagate level lines or linear structures (so-called isophotes) via diffusion based on partial differential equations [START_REF] Bertalmio | Image inpainting[END_REF], [START_REF] Bertalmio | Navier-stokes, fluid dynamics, and image and video inpainting[END_REF] and variational methods [START_REF] Chan | Local inpainting models and tv inpainting[END_REF]. In other words, they tend to prolong isophotes arriving at the border of the region to be filled. The diffusion-based methods tend to introduce some blur when the hole to be filled in is large.

The second type of approach concerns examplar-based methods which sample and copy best match texture patches from the known image neighborhood [START_REF] Bornard | Missing data correction in still images and image sequences[END_REF], [START_REF] Criminisi | Region filling and object removal by examplar(based image inpainting[END_REF], [START_REF] Drori | Fragment-based image completion[END_REF], [START_REF] Harrison | A non-hierarchical procedure for re-synthesis of complex texture[END_REF], [START_REF] Jia | Image repairing: Robust image synthesis by adaptive tensor voting[END_REF], [START_REF] Zhang | Region completion in a single image[END_REF], [START_REF] Sun | Image completion with structure propagation[END_REF]. These methods have been inspired from texture synthesis techniques [START_REF] Efros | Texture synthesis by non-parametric sampling[END_REF] and are known to work well in cases of regular textures. The first attempt to use exemplar-based techniques for object removal has been reported in [START_REF] Harrison | A non-hierarchical procedure for re-synthesis of complex texture[END_REF]. The authors in [START_REF] Drori | Fragment-based image completion[END_REF], improve the search for similar patches by introducing an a priori rough estimate of the inpainted values using a multi-scale approach which then results in an iterative approximation of the missing regions from coarse to fine levels. In addition, the candidate patches for the match also include rotated, scaled and mirrored version of texture patches taken from the image.

In this section, we describe novel inpainting algorithms based on the examplar-based solution of [START_REF] Criminisi | Region filling and object removal by examplar(based image inpainting[END_REF]. The approach is extended along two directions: the first one consists in proposing new methods for defining the patch filling order. Indeed, as in [START_REF] Criminisi | Region filling and object removal by examplar(based image inpainting[END_REF], the proposed methods involve two steps: first, a filling order is defined to favor the propagation of structure contained in the patch to be filled in. Second, an approximation of the known samples in the patch to be filled is performed via template matching or with the help of more elaborate approaches (using neighbor embedding techniques) is performed in order to find the best candidates to fill in the hole.

Overview of examplar-based inpainting

Let I be the image and Ω the region to be filled in. Let δOmega be the border of the region to be filled in. 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 three terms: P(p) = C(p)D(p)E(p). The first term, called confidenece term is given by [START_REF] Criminisi | Region filling and object removal by examplar(based image inpainting[END_REF]:

C(p) = q∈Ψp∩(I-Ω) C(q) |Ψ p | (3.1)
It gives the ratio between the number of known pixels with respect to the total number of pixels in the patch to be filled in. The term D(p), called the data term, is given by [START_REF] Criminisi | Region filling and object removal by examplar(based image inpainting[END_REF]

D(p) = |∇I ⊥ p n p | α (3.2)
where n p is a unit vector orthogonal (⊥) to the filling front δΩ in the point p. This second term increases the priority of the patch having isophotes perpendicular to the filling front. However, it does not really reflect the predominance of an edge within the patch. Therefore, we introduce here a third term E(p) which is the ratio of the amount of kwown pixels of the patch which belong to an edge with respect to the total number of pixels in the patch. Thus E(p) is given by

E(p) = q∈Ψp∩(I-Ω) δ(q ∈ E) |Ψ p | (3.3)
where delta() is a binary function which returns 1 when its argument if true and 0 otherwise. E is the set of edge pixels which is determined by using a canny edge detector. Figure 3.1 compares the inpainted images with simple template matching (as in [START_REF] Criminisi | Region filling and object removal by examplar(based image inpainting[END_REF]) when using the priority function augmented with the "edge" term with respect to the original priority function.

New Priority computation

Two new approaches for computing the priority of the patches to be filled have been conceived.

Tensor-based priority computation

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 | (3.4)
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 curvaturepreserving 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 = n i=1 ∇I i ∇I T i (3.5)
J is the sum of the scalar structure tensors ∇I i ∇I T i of each image channel I i (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 v 1,2 (v i ∈ R n ) define an oriented orthogonal basis and its eigenvalues λ 1,2 define the amount of structure variation. v 1 is the orientation with the highest fluctuations (orthogonal to the image contours), and v 2 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]:

D(p) = α + (1 -α)exp(- C (λ 1 -λ 2 ) 2 ) (3.6)
where C is a positive value and α ∈ [0, 1] (C = 8 and α = 0.01). On flat regions (λ 1 ≈ λ 2 ), any direction is favored for the propagation (isotropic filling order). The data term is important in presence of edges (λ 1 >> λ 2 ). Figure 3.2 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.

Hierarchical tensor-based priority computation

The computation of the gradient ∇I as explained above to define the structure tensor presents some limitations. 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 undermine 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 L 0 , the algorithm described in the previous section is applied. For a next pyramid level L n , a linear combination between the structure tensors of level L n and L n-1 (after upsampling) is performed:

J Ln h = ν × J Ln + (1 -ν)× ↑ 2(J L n-1 ) (3.7)
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. 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.

Edge-based priority computation

Given a patch Ψ p centered at the point p (known pixel) located near the front line, the filling order (also called priority) is defined as the product of three terms: P (p) = C(p)D(p)E(p). The first term, called confidence term is given by [START_REF] Criminisi | Region filling and object removal by examplar(based image inpainting[END_REF]:

C(p) = q∈Ψp∩(I-Ω) C(q) |Ψ p | (3.8)
It gives the ratio between the number of known pixels with respect to the total number of pixels in the patch to be filled-in. The term D(p), called the data term, is given by [START_REF] Criminisi | Region filling and object removal by examplar(based image inpainting[END_REF] as

D(p) = |∇I ⊥ p n p | α (3.9)
where α is a normalization factor and n p is a unit vector orthogonal (⊥) to the filling front δΩ in the point p. This second term increases the priority of the patch having isophotes perpendicular to the filling front. However, it does not really reflect the predominance of an edge within the patch. Therefore, we introduce here a third term E(p): this is the ratio of the amount of known pixels of the patch which belong to an edge with respect to the total number of known pixels in the patch. Thus E(p) is defined as

E(p) = q∈Ψp∩(I-Ω) δ(q ∈ E) |Ψ p ∩ (I -Ω)| (3.10)
where δ() is a binary function which returns 1 when its argument is true and 0 otherwise. E is the set of edge pixels which is determined by using a Canny edge detector. Figure 3.2.3 compares the inpainted images with simple template matching (as in [START_REF] Criminisi | Region filling and object removal by examplar(based image inpainting[END_REF]) when using the priority function augmented with the "edge" term with respect to the original priority function. The proposed priority function with edge term changes the filling order by giving more priority to structural blocks containing edge information. As it can also be seen from Figure 3.2.3, after 100 iteration steps, the shape of the mask is different from the original priority function. Thus, the structures are propagated first to prevent introducing any annoying visible artifacts in the continuation of the edgel areas in the image.

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 prioritybased 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]. Figure 3.3: Effect of the edge term in the priority function. From left-to-right: The mask for the inpainting algorithm; the inpainting process after 100 patches with priority function of [START_REF] Criminisi | Region filling and object removal by examplar(based image inpainting[END_REF] and the final inpainted image; the inpainting process after 100 patches with the augmented priority function and the final inpainted image.

Template Matching along the Isophote direction

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 ) (3.11)
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) (3.12)
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. On flat areas, this term tends to 0. The function f (p, q) is given by:

f (p, q) = 1 + |v 2 •vpq| vpq (3.13)
where v pq 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 v pq is not collinear to the isophote direction (assessed by computing the scalar product v 2 • v pq ), this candidate is penalized. 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.

Hole filling based on neighbor embedding techniques

A K nearest neighbour search algorithm can also be 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 (c i are the pixels of the selected candidates):

c = i s i c i i s i (3.14)
where s i is the similarity measure deduced from the distance (see equation 2 of [START_REF] Wexler | Space-time completion of video[END_REF]). 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 window search. K is given by the function a + b 1+σ 2 W /T (in our implementation we use a = 1, b = 9 and T = 100. It means that we can use up to 10 candidates to fill in the holes). Figure 3.2 (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.

Once the K-NN patches are found, the embedding which essentially searches for the best linear combination of these K-NN patches can be done in different ways.

Locally Linear Embedding

A method called locally linear embedding has been introduced in [START_REF] Roweis | Nonlinear dimensionality reduction by locally linear embedding[END_REF] for data dimensionality reduction. It aims at preserving the local linear structure of the high-dimensional data in the lower-dimensional space. The LLE method consists of the following steps:

1. It first identifies K nearest neighbors X j per data point X i . The usual measure is the Euclidean distance;

2. It then searches for the weights W i,j , so that each data point is approximated by its neighbors. The algorithm thus aims at minimizing the cost function,

E(W ) = i |X i - j W i,j X j | 2 . (3.15)
The weights W i,j represent the contribution of the j th data point to the reconstruction of the i th point and are constrained to sum to one ( j W i,j = 1). Each data point X i can only be reconstructed from its neighbors (i.e., W i,j = 0 if the data point X j does not belong to the neighbors of X i ). The optimal weights satisfying these constraints are obtained by solving a standard least square problem;

3. Finally, an embedding cost function is minimized in order to obtain the low-dimensional global internal coordinates by fixing the weights W i,j calculated in the previous step.

(Please see [START_REF] Roweis | Nonlinear dimensionality reduction by locally linear embedding[END_REF] for more information.)

The LLE method (steps 1 and 2) is here directly applied on texture patches. One thus searches to approximate the known pixels of the patch Ψ p to be filled-in by a linear combination of the colocated pixels in the K-NN patches Ψ j , j = 1 . . . K, and keep the same linear combination to inpaint the unknown pixels of the patch.

Figure 3 compares the inpainting results obtained by using an LLE based approximation of the patch to be filled-in rather than using a simple template matching with both the priority function of [START_REF] Criminisi | Region filling and object removal by examplar(based image inpainting[END_REF] and the augmented priority function with E(p). The LLE based approach using K patches instead of one (as in template matching) leads to a more realistic inpainted image. E.g., in Figure 3, one can see that the bushes are propagated into the sea with template matching whereas the LLE based method prevents this propagation. Furthermore, the quality of the inpainting of the roof is also improved visually. (K is fixed to 10, and patch size is 9 × 9.)

Performance illustration of tensor-based priority and isophote constrained TM

Figures 3.5 and 3.6 show the performance of the proposed method. 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 but the apparition of blur is annoying when filling large areas. Regarding Criminisi's approach, results of both approaches are similar on the first picture. 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 a considerable gain. Figure 3.6 shows 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]. Compared to previous assessment, these pictures have a smaller resolution (200 × 200 pixels) than those used previously (512 × 384). 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. Next studies 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 synthesise such texture by using stochastic-based texture models.

Performance illustration of the neighbor embedding techniques

The performance of the entire inpainting algorithm using the new patch priority computation, LLE and the learned mapping has been assessed on several test images, and compared with stateof-the-art diffusion-based approaches [START_REF] Telea | An image inpainting technique based on the fast marching method[END_REF][START_REF] Tschumperlé | Fast anisotropic smoothing of multi-valued images using curvaturepreserving pde's[END_REF] and exemplar-based methods [START_REF] Criminisi | Region filling and object removal by examplar(based image inpainting[END_REF][START_REF] Barnes | Patchmatch: A randomized correspondence algorithm for structural image editing[END_REF]. Figure 3.5 illustrates some of the results obtained for the test images. We selected natural images with large holes to be filled-in in order to test our proposed inpainting algorithm for object removal.

Since the holes to be filled-in are quite large, diffusion-based approaches introduce blur into the image. When we compare our method with the other exemplar-based methods including [START_REF] Criminisi | Region filling and object removal by examplar(based image inpainting[END_REF] and [START_REF] Barnes | Patchmatch: A randomized correspondence algorithm for structural image editing[END_REF], we see the natural looking and structure preserving capacity of the proposed method in this paper. Inpainting mask, our method, method in [START_REF] Criminisi | Region filling and object removal by examplar(based image inpainting[END_REF], method in [START_REF] Barnes | Patchmatch: A randomized correspondence algorithm for structural image editing[END_REF], method in [START_REF] Telea | An image inpainting technique based on the fast marching method[END_REF], and method in [START_REF] Tschumperlé | Fast anisotropic smoothing of multi-valued images using curvaturepreserving pde's[END_REF]. 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 (Figure 4.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.

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 classical structure tensor defined in section 3.2.1 is extended with the depth map taken as an additional image component Z:

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

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 Figure 4.1a). We then want to prevent structure propagation from foreground by supporting the directional background propagation, as illustrated in Figure 4.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-of-field 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 Video-plus-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-and-color 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

Figure 4.2 illustrates the results obtained with the proposed method, comparatively with methods from the literature [START_REF] Criminisi | Region filling and object removal by examplar(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 examplar(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 webpage1 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].

Joint projection/inpainting method

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 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] Chan | Image-based rendering and synthesis[END_REF]. 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] 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][START_REF] Sourimant | Depth maps estimation and use for 3dtv[END_REF].

The classical DIBR scheme for virtual view extrapolation from single input view plus depth video sequences is shown in Figure 5.1. The process in classical DIBR schemes 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 5.1). 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 filtered depth map is involved in a backward warping to compute the color of each pixel of the virtual view. 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 Figure 5.1: 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). Figure 5.2: Virtual depth map synthesized by three forward projection methods. The point-based projection method generates cracks and disocclusions (left). Median filtering and directional inpainting [START_REF] Nguyen | Depth image-based rendering from multiple cameras with 3d propagation algorithm[END_REF] fills some holes with foreground depth (middle). The proposed JPF method fills cracks and disocclusions with realistic background (right). in figure 5.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 5.2. As a result, depth-aided inpainting uses wrong foreground patches to fill in background disocclusions, producing annoying artifacts, as shown in figure 5.2.

This chapter describes a new DIBR technique 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. The JPF method is designed to handle disocclusions in virtual view synthesis, from one or many inputs view plus depth video sequences. The proposed DIBR method, depicted in Fig. 5.3 is designed to extrapolate virtual views from a single input view plus depth video sequence. The method differs from the classical scheme 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 JPF method fills in disocclusion areas during the projection, to ensure that geomet- rical structures are well preserved. The method uses the occlusion-compatible ordering presented by McMillan in [START_REF] Mcmillan | A list-priority rendering algorithm for redisplaying projected surfaces[END_REF], 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 [START_REF] Müller | View synthesis for advanced 3d video systems[END_REF], by introducing the following key contributions:

• A novel forward projection method for DIBR, using occlusion compatible ordering [START_REF] Mcmillan | A list-priority rendering algorithm for redisplaying projected surfaces[END_REF] 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.

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 [START_REF] Müller | View synthesis for advanced 3d video systems[END_REF], 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][START_REF] Sarim | Wide-baseline matte propagation for indoor scenes[END_REF][START_REF] Wang | Image and video matting: a survey[END_REF].

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], 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] Zwicker | Ewa splatting[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], 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][START_REF] Yoon | A framework for representation and processing of multi-view video using the concept of layered depth image[END_REF][START_REF] Müller | Reliability-based generation and view synthesis in layered depth video[END_REF][START_REF] Jantet | Incremental-ldi for multi-view coding[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] Bertalmio | Navier-stokes, fluid dynamics, and image and video inpainting[END_REF][START_REF] Telea | An image inpainting technique based on the fast marching method[END_REF][START_REF] Criminisi | Region filling and object removal by examplar(based image inpainting[END_REF]. In [START_REF] Do | Quality improving techniques in dibr for free-viewpoint video[END_REF], 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], 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 | Region filling and object removal by examplar(based image inpainting[END_REF] 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], 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] Bertalmio | Navier-stokes, fluid dynamics, and image and video inpainting[END_REF] 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], 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 5.2.

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 5.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 [START_REF] Mcmillan | A list-priority rendering algorithm for redisplaying projected surfaces[END_REF], 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 5.2.1. It is first introduced for rectified cameras and then generalized for non-rectified cameras. Section 5.2.2 presents a ghosting removal method, based on pixels confidence measure. Finally, section 5.2.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 [START_REF] Mcmillan | A list-priority rendering algorithm for redisplaying projected surfaces[END_REF].

Figure 5.6 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.

(5.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 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 ) (5.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 5.6. 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 (5.1) is revised, replacing p with P q , thus q and P q are on the same row. q x ≤ P q

x + 1 There is no artifact. q x > P q

x + 1 There is a disocclusion.

(5.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 )
(5.4) Figure 5.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.5). 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.

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

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 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.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.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 σ (5.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 5.2.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 (5.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 5.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.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 application. Two use cases are addressed in section 5.3, either for virtual view extrapolation when only one input view is available, or for intermediate view interpolation when multiple input views are available.

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 5.3.1 describes a virtual view extrapolation algorithm, which is used when only one input view plus depth video sequence is available. Section 5.3.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 developed algorithm proceeds as follows. 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 in [START_REF] Criminisi | Region filling and object removal by examplar(based image inpainting[END_REF]. Section 5.3.2 describes our proposed modification which takes into account the high quality of the virtual depth map. The importance of the synthesized depth map quality is discussed in section 5.4, for three different depth-aided inpainting methods.

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, i.e., the distance between patches is computed as follows:

Ψ q = arg min Ψq∈Φ {SSD Φ (Ψ p, Ψ q ) + α SSD Φ∪Ω (Z p, Z q )} (5.8)

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 5.1, or by the JPF method. Figure 5.7 shows inpainting results of the algorithm presented in [START_REF] Daribo | Depth-aided image inpainting for novel view synthesis[END_REF]. Figure 5.8 shows inpainting results of the algorithm presented in [START_REF] Gautier | Depth-based image completion for view synthesis[END_REF]. Figure 5.9 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] Bertalmio | Navier-stokes, 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 5.7 and 5.8 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.

Figure 2 . 2 :

 22 Figure 2.2: Nine possible modes for the MSE/RD optimized support (template) selection.

Figure 2 . 3 :

 23 Figure 2.3: Mean approximation PSNR versus sparsity performance of (left) low (q f = 90), (middle) medium (q f = 50), and (right) high (q f = 10) quantization noise corrupted (top-row) Barbara (512x512) and (bottom-row) Foreman (CIF) images using SP, NMF, and LLE based image prediction algorithms with 4x4 block size. Template mode 1 is used as shown in Fig. 2.2 and k ∈ [1, 50].

Figure 2 . 4 :

 24 Figure 2.4: Mean approximation PSNR versus sparsity performance of (left) low (q f = 90), (middle) medium (q f = 50), and (right) high (q f = 10) quantization noise corrupted (top-row) Barbara (512x512) and (bottom-row) Foreman (CIF) images using SP, NMF, and LLE based image prediction algorithms with 4x4 block size. Template mode 1 is used as shown in Fig. 2.2 and k ∈ [51, 100].

Figure 2 . 5 :

 25 Figure 2.5: The test images. (a) Foreman (CIF), (b) Barbara (512x512), and (c) Roof (512x512).

Figure 2 . 7 :

 27 Figure 2.7: Prediction results for a textural region of Barbara image at low bit-rates (q f = 10). (a) Original image, (b) H.264 intra modes, (c) SP, (d) LLE, and (e) NMF based prediction methods with MSE criterion and sparsity constraints (k ∈ [1, 8]).

Figure 2 . 8 :

 28 Figure 2.8: Prediction results for an edgel region of Foreman image at low bit-rates (q f = 10). (a) Original image, (b) H.264 intra modes, (c) SP, (d) LLE, and (e) NMF based prediction methods with MSE criterion and sparsity constraints (k ∈ [1, 8]).

Figure 2 . 9 :

 29 Figure 2.9: PSNR/bit-rate performance for (a) Barbara, (b) Roof, and (c) Foreman images.

Figure 3 . 1 :

 31 Figure 3.1: Effect of the edge term in the priority function: Mask of the inpainted region (left); Inpainting with priority function of [24](middle); Inpainting with the augmented priority function (right).

Figure 3 . 2 :

 32 Figure 3.2: (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.

Figure 3 . 4 :

 34 Figure 3.4: Inpainting with template matching as in [24] (left-top row); Inpainting with template matching with augmented priority (right-top row); Inpainting with LLE without edge-based priority (left-bottom row); Inpainting with LLE with edge-based priority (right-bottom row).

Figure 3 . 5 :

 35 Figure 3.5: Comparison of the proposed approach with the approaches [36, 24].

Figure 3 . 6 :

 36 Figure 3.6: Results of the proposed approach on pictures proposed by [37].

Figure 3 . 7 :

 37 Figure 3.7: Inpainting results for natural test images. From left-to-right top-to-bottom per image:Inpainting mask, our method, method in[START_REF] Criminisi | Region filling and object removal by examplar(based image inpainting[END_REF], method in[START_REF] Barnes | Patchmatch: A randomized correspondence algorithm for structural image editing[END_REF], method in[START_REF] Telea | An image inpainting technique based on the fast marching method[END_REF], and method in[START_REF] Tschumperlé | Fast anisotropic smoothing of multi-valued images using curvaturepreserving pde's[END_REF].

Figure 4 . 1 :

 41 Figure 4.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) V5→4 after warping and background antighosting (b) V5→2 after warping and background antighosting (c) V5→4 inpainted with Criminisi's method (d) V5→2 inpainted with Criminisi's method (e) V5→4 inpainted with Daribo's method (f) V5→2 inpainted with Daribo's method (g) V5→4 inpainted with our method (h) V5→2 inpainted with our method

Figure 4 . 2 :

 42 Figure 4.2: Illustration of different methods of inpainting. Our approach relying on 3D tensor and directional prioritization shows efficient filling.

Figure 5 . 3 :

 53 Figure 5.3: Virtual depth map synthesized by three forward projection methods. The point-based projection method generates cracks and disocclusions (left). Median filtering and directional inpainting [48] fills some holes with foreground depth (middle). The proposed JPF method fills cracks and disocclusions with realistic background (right).

Figure 5 . 5 :

 55 Figure 5.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.

Figure 5 . 6 :

 56 Figure 5.6: Warping results with the JPF method.

Figure 5 . 7 :

 57 Figure 5.7: Results for Daribo depth-aided inpainting [64]. 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 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 5 . 8 :

 58 Figure 5.8: Results for Gautier depth-aided inpainting [65]. 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 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 5 . 9 :

 59 Figure 5.9: 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 Navier-strokes inpainting algorithm 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.

Table 2 .

 2 1: Sparse Approximation based Image Prediction using OMP. Input: A c , A t , b c , b t , K Output: Predicted values of unknowns bt Initialization

Table 2 .

 2 2: Locally Linear Embedding based Image Prediction. Input: A c , A t , b c , b t , K Output: Predicted values of unknowns bt Initialization

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

 Chapter 4Texture synthesis for 3D inpainting in virtual view synthesis 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) 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 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 examplar(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.

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. 4.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