exploitant les connaissances acquises lors des étapes précédentes. Enfin, la performance des solutions proposées est soigneusement évaluée à travers plusieurs expérimentations, et ce au regard du jugement humain ainsi qu'en comparaison avec les méthodes existantes.

Three years of living away from home, away from family, away from friends to pursue a dream, PhD course. It is really not easy. The dream would not come true without support, advice, encouragement and sharing of many people during the research. In consonance with, there have been a lot of happiness, sadness and other emotions to be experienced.

Finally, now is the moment for me to express my sincere gratitude to: My supervisor, Prof. Azeddine BEGHDADI, for his generous support and intellectual guidance throughout my years as a graduate student; his insightful advice, clear vision, many suggestions, and endless efforts to be available for many educational discussions, were invaluable; my co-supervisor, Dr. Mohamed-Chaker LARABI, whose friendship and encouragement were helpful; and whose profound and concrete comments and suggestions on drafts of this thesis have enabled my deepened understanding of my work; my committee members, Dr. Frederic DUFAUX and Dr. Stefaina COLONNESE, for valuable insights and suggestions which have significantly improved this thesis in both structure and contents; my external examiners, Dr. Faouzi ALAYA-CHEIKH and Prof. Anissa MOKRAOUI, for their critical comments and constructive suggestions on this thesis; my beloved wife, PHAM Thi Mai Bao, and my small princess, DANG Mai Bao Linh, who shared with the pains and happiness during the course of this work; her endless support, sacrifice, and understanding kept me going through it all; my parents, DANG Van Duong and NGUYEN Thi Song A, who born me and first taught me the importance of education as well as raised me with a love of science and supported me in all my pursuits; all the other members of my family, parents in law, younger brothers and younger sisters who supports me in every possible ways at all times in life; my dear friends in Vietnam, especially PHUONG-LE-CUN, KIEN-THOA-TUAT, ... who persistently encouraged me as well as aided my family during the most difficult period when I am away from home; my dear friends in France, notably LOC-PHUONG, DUNG, NGHIA, TRANG BEO, NGUYEN-NGA, TUNG-DUNG, HOAN-LY, HOAN-NGA, BAO-CUC-LEO, BANG, PHAM NHUNG, ... (it is impossible to list all here but you know who you are!) who made days spent together feel like seconds and help me defeat the obstacles in adapting to lonely life here; and finally, my comrades, WALID, SAMEH, who shared together the ups and downs in mood in our ways of seeking the truth.

My gratitude is more than words that I can say.

Thank you all sincerely for everything which makes my dream come true.

ii

Abstract

Image inpainting technique has emerged as one of the efficient solutions for restoring degraded images and even video and 3D visual contents. It is essential for restoration and conservation of archeological objects. Indeed, during the excavation of historic sites, many valuable artifacts such as statues, buildings, wall paintings, etc., have been unearthed and recovered. Unfortunately, most of them have been damaged or fractured in ancient times. With the aim to learn from these objects, digital techniques are used to restore them using some a priori knowledge provided by archeologists and artists. This helps to reconstruct, preserve and maintain these valuable artistic works. Recently, advances of computer technology and image acquisition systems made possible the transition from traditional manual retouching methods to digital techniques. It has opened up a very new and interesting research field within image processing, namely digital image inpainting.

In this thesis, our work aims at analyzing and reviewing the state-of-the-art methods for image inpainting. Three groups of inpainting methods are identified. The advantages and drawbacks of each approach are analyzed using objective and subjective criteria. Based on this review, a new approach of image inpainting is introduced and compared to literature.

The proposed method provides good performance in terms of quality and computation efficiency. Another contribution lies in the proposal of a new quality metric dedicated to image inpainting. To the best of our knowledge the inpainted images are very often evaluated subjectively or by means of some objective metrics far from being adapted to the peculiarities of image inpainting criteria. The last contribution of this work is a less investigated problem related to inpainting detection. This is motivated by the fact that, due to extensive research and rapid growth of technology, the output quality of inpainting algorithms became more than ever realistic and sophisticated. The inpainted regions are hard to detect by viewers, even for experts. As a result, these inpainted images could be used for different purposes, including digital tampering. Therefore, the last topic of the work is devoted to inpainting detection, also seen as an inverse problem of inpainting.

Although, many papers have been introduced for forgery detection, there is almost no study about image inpainting forgery. Accordingly, a novel approach for inpainting detection is introduced based on the knowledge gathered in the previous steps of the thesis. Finally, the performance of proposed solutions is carefully evaluated with regards to human judgment as well as in comparison with the existing methods though a series of experimental studies. Ceci est motivé par les efforts importants de recherche sur la thématique ainsi que le développement rapide de la technologie. La conséquence est que la qualité des retouches par inpainting est devenue plus réaliste et sophistiquée que jamais. Les régions retouchées sont alors difficiles à détecter par les utilisateurs, même les experts. Ainsi, ces images pourraient être utilisées à différentes fins, légales comme illégales. Malgré l'importance du sujet, très peu de travaux l'ont adressés à cause de sa complexité. C'est sur cette base qu'une nouvelle approche pour la détection d'inpainting est proposée dans cette thèse, en Introduction "All truths are easy to understand once they are discovered.

The point is to discover them."

Problem statement

Pompeii and Herculaneum were once thriving towns in the Bay of Naples. Both towns have rich histories influenced by Greeks, Oscans, Etruscans, Samnites and finally the Romans. However, they were destroyed during an eruption of the volcano Mount Vesuvius in 79 AD.

The volcano erupted and covered completely the town and its inhabitants in many tons of pumice and volcanic ash.

The discovery of Pompeii is of great importance for our modern-day understanding of the ancient Roman-Italic world -partly because the more public and monumental ruins left behind by Imperial Rome have often been misleading. The excavations at Pompeii and Herculaneum offer an intact vision of daily life in a Roman society in all its aspects.

During the excavation, many valuable artifacts such as statues, buildings, wall paintings, etc., have been unearthed and recovered. Unfortunately, most of them have been damaged or fractured in ancient times. On way to preserve and maintain these valuable artistic works, they should be digitalized and restored by the art restoration artists, who could bring them back to the original or to close-to-original state.

In fact, it is impossible or unnecessary to restore these paintings to the original version because they are unique and there are no written documents to study. Thus, the main task of artists is filling in existent gaps in the paintings with visually pleasing content. On the other hand, it can be said that almost as old as art itself is the practice of making modifications to paintings, in such a way that if an observer would look at the modified work, without knowing the original one, he could not be able to perceive any alteration. This restoration is traditionally carried out by experts, such as museum art restorers, and it is commonly known as retouching or inpainting. Its desired outcome is to make a damaged artwork more discernible, while restoring its unity. Researcher working on different applications of inpainting have adopted different names though their own individual characteristics: "error concealment" in telecommunications; "image disocclusion" or "image interpolation" in image processing.

The objectives of inpainting are numerous. They have been employed in various applications such as medical and astronomical imaging, film restoration, image and video coding and many others [START_REF] Banham | Digital image restoration[END_REF][2][3]. Meanwhile, in computer science, much research similar to the inpainting problem has also been carried out in the context of image replacement, image interpolation, error concealment, digital restoration of ancient paintings for conservation purposes, disocclusion in vision research [4,5].

To illustrate the use of inpainting restoration in typical applications, an example of restoration is shown in Figure 1.3. In this figure, the original images with defects such as cracks and scratches are shown in Figure 1.3-a,c and the corresponding outputs are shown in Figure 1.3-b,d. The inpainting process is implemented in two different ways but with a common goal, i.e., an undetectable modification by viewers.

Thesis objectives

Firstly, our work aims to analysis and review state-of-the-art methods for inpainting problem. All three groups of inpainting are reviewed to analysis their advantages and disadvantages. Based on this background, a new proposal of inpainting is introduced with high-quality results and high performance computation.

In order to validate the performance of the proposed inpainting method, a comparison with existent approaches is implemented. Nevertheless, at our best knowledge the inpainted images are very often evaluated subjectively or by using some objective metrics not well adapted to the specificities of image inpainting criteria. In addition, subjective experiments are time consuming, complex and unpredictable due to some uncontrolled human factors such as fatigue, visual discomfort, background, etc. Thus, the second goal of our work is to propose an objective Image Inpainting Quality Assessment (IIQA) metric. The performance of the proposed metric is carefully assessed with regards to human judgement as well as comparison with some traditional image quality index and existing inpainting quality metrics.

Due to the extensive research and rapid technology advancements, the output quality of inpainting algorithms has become more realistic and sophisticated. The inpainted regions are hard to detect by viewers, even for experts. As a result, the inpainted images could be used for many different purposes, including digital tampering. Therefore, the last objective in our work is devoted to inpainting detection, an inverse problem of inpainting.

Although, many papers have been introduced for forgery detection, there is almost no study about image inpainting forgery. Consequently, a novel approach for inpainting detection is necessary and valuable in verifying the authenticity of the original image. The purpose of our work is then to introduce an efficient and reliable inpainting detection method.

Thesis contributions

Many inpainting algorithms have been reviewed and analysed in this thesis. It could be considered as the foundation for our work. Two other trends have been exploited such as inpainting quality assessment and inpainting forgery detection. For each issue, we have specific contribution for solving the corresponding problems. In summary, the significant contributions are summarized below:

• Inpainting problem: A novel framework for inpainting has been introduced. However, it has some limitations due to computational complexity and time running.

Some solutions are proposed to improve the performance of the proposed algorithm.

• Inpainting quality: Once the inpainted images are obtained, the most common method for evaluating the quality is observing and scoring by human viewers. In this dissertation, we present a new metric to estimate objectively the quality of the restored images.

• Inpainting detection: A new model is developed to detect whether a given image is edited by inpainting algorithms or not. The idea is to consider inpainting as a tampering process. This contribution is necessary and valuable in verifying the authenticity of the original image.

As a result, the ideas developed in this thesis have been published in international conferences and journal. Below is the list of publications:

Thesis outline

This report consists of six chapters. After the introductory chapter, four main chapters corresponding to our contributions are presented. The last chapter is devoted to conclusion and perspectives. The content of the chapters is briefly summarized below:

• Chapter 2 introduces the state-of-the-art inpainting algorithms. Starting from the one of the earliest work until the present one, a series of inpainting algorithms has been summarized to provide for reader a basic look on digital image inpainting methods that have been developed during the last decade.

• Chapter 3 discusses relevant work on inpainting and introduces our proposal for this problem. First, a novel framework of image completion is introduced using multi-resolution representation of the image. Second, an improvement is proposed to enhance the algorithm performance. A series of experimental studies is carried out in order to evaluate and compare our approach with the existing methods.

• Chapter 4 presents a new methodology for evaluating perceptual inpainting quality. Some image quality assessment metrics which can be applied for inpainting in some cases are investigated. A few existing inpainting quality metrics are analysed in details. From this analysis, some novel metrics for inpainting quality are proposed.

A subjective study is then launched to evaluate the proposed metrics in comparison with both the traditional image quality assessment metrics and existing inpainting quality metrics.

• Chapter 5 is related to a new trend of inpainting problem, inpainting forgery detection. Although, many current forgery detection techniques have been introduced, they cannot apply to detect inpainting forgery because of the fundamental difference between them. Based on the analysis of the current inpainting algorithms in conjunction with the survey of principles of existing forgery detection techniques, a novel forgery detection method is proposed for inpainting forgery in this chapter.

The performance of the proposed detection method is evaluated both subjectively and objectively on a series of experiments. This chapter aims to provide an introduction of inpainting problem as well as a classification for image inpainting techniques. In addition, a brief description for each method is also presented to help the readers have an overview of the current inpainting methods.

State-of-the-art

Image inpainting has become an active research topic in image processing field. It is not only art of modifying image but also a powerful technique for automatically restoring or removing undesired objects in an undetectable form to an observer not familiar with the original image and is as ancient as art itself. This work refers to the traditional practice of expert and professional artists in museums to restore manually the old pictures or paintings. The problem is extremely difficult and high time cost because they had to complete smoothly the damaged image as well as preserve the global content based on their skills and experiences. Digital image inpainting attempts to mimic the basic techniques of this process automatically. Since it does not refer to the original image and it is too hard to define mathematically "global content" term of image, the objective of digital image inapainting is only restoring the damage image so that it still looks natural, i.e., the restored parts are not easily detectable by viewers.

In the parlance of digital inpainting, the missing region is often referred to as blotch or scratch in the case of small or thin size regions; and referred to as hole or gap in case of large size regions. Very often, the blotch or hole of image is provided by the user in the form of binary mask or can be obtained by semi-automatic means.

Besides, the nomenclature is classified by this criterion. Namely, the removing blotch or scratch is called as inpainting but the filling in hole or gap is considered as image completion. The terminology of "inpainting" was invented by Bertalmío et al. [START_REF] Bertalmío | Image inpainting[END_REF] who were the first group to develop inpainting models with the motivation coming from the professional artists. This approach is suitable to remove blotches or scratches. When it is developed to filling in holes or gaps, it is called as image completion.

Despite the significant differences between the existent techniques, an image inpainting model is often composed of two stages:

1. identify the damaged regions (inpainting regions).

2. fill in the inpainting regions based on the known information in the same image.

Up to now, there has been no way or model to detect automatically the inpainting regions because of a lack of objective criteria or measures to identify and quantify the level of degradation. There are a few special applications in which the inpainting regions can be detected semi-automatically, for example blotch detection of old video. However, accuracy and performance of detection are still much debate. For the sake of simplicity, they are marked manually in form of binary mask by users. The digital inpainting focuses on the second stage in order to perform automatically the restoration using the input parameters.

The digital image completion consists of mathematically modeling and performing the restoration under constraints of local smoothness preservation, but without taking into account the global semantic of image or artistic expertise.

Overview of inpainting methods

Digital image inpainting is considered as an ill-posed inverse problem which has no welldefined unique solution [START_REF] Guillemot | Image inpainting: Overview and recent advances[END_REF]. To solve the problem, only input image including the known and unknown parts is given and the requirement of output in terms of quality is that the recovered region looks natural to the human eye.

Nowadays, computer technology facilitates a rapid development of digital inpainting techniques. There have been numerous and very different automatic inpainting algorithms in recent years. In general, most of them are categorized into three main groups as listed below [START_REF] Guillemot | Image inpainting: Overview and recent advances[END_REF][START_REF] Arias | A variational framework for exemplar-based image inpainting[END_REF]:

• Geometry-oriented methods

• Texture-oriented methods

• Hybrid inpainting methods

Basically, an overall assessment of existing methods is considered as an importance for next proposals in our research. In this chapter, some typical inpainting methods as shown in Table 2.1 will be introduced and analysed in the next section in order to build a foundation for our next research.

In Table 2.1 the first column, Year, indicates the year of the publication followed by Authors' names. Type column indicates the category to which the algorithm belongs. The last column H-type, short for 'hole type', determines the size of hole or damaged region for which the algorithm is more adapted. A detailed definition of the size of the hole will be given in the next section.

Notations

Before proceeding with a review of the inpainting methods , a note must be made on the notation that will be used. The image input is denoted by character I. The inpainting domain in the image is defined by the omega symbol, Ω, while δΩ stands for its boundary.

The source region, representing the area not covered by the mask, or the area complementary to the gap, will be denoted by Φ (Φ = I -Ω). This notation was first used in [START_REF] Bertalmío | Image inpainting[END_REF] and Hays and Efros [START_REF] Hays | Scene completion using millions of photographs[END_REF] Multi-source images Large Whyte et al. [START_REF] Whyte | Get out of my picture! internet-based inpainting[END_REF] Multi-source images Large adopted by the following works (see Figure 2.1). A window centred at pixel p is denoted as a patch, Ψ p .

The distinction of the inpainting region

The area of the damaged region plays an important role in analysing and designing the recovery methods. In addition, it is also the key criterion for classification of inpainting methods. Nevertheless, we agree with the fact that the notion of large missing regions used in the inpainting community is not a well/quantitatively defined criterion. For the small inpainting regions, such as scratches and blotches of reduced size, is not a challenging issue.

In contrast, in the case of large regions, it is uneasy to guarantee the spatial coherence and object continuity during the inpainting process.

The percentage of missing pixels cannot be the only criterion because an image may contain some thin scratches across the image. In that case the scratch could not be considered as large.

We can say that a missing region is large if it contains completely a square patch whose size length is greater than r pixels. In our experiments r is set to 5. It is worth noticing that this parameter does not depend on the image size but directly related to the inpainting approach. For example a size of 3 × 3 does not necessitate any sophisticated inpainting approach. A simple interpolation would work. A typical size of 5 × 5 represents the most adequate choice for the used inpainting approach. A large missing region, Ω, can be defined mathematically as follows:

Ω is a large inpainting region ⇔ {∃p ∈ Ω :

Ψ p ∩ Ω ≡ Ψ p } (2.1) (a) (b)

Geometry-oriented methods

The first group of inpainting approaches discussed here is geometry-oriented methods. In this group, the image is modelled as a function of smoothness and the restoration is solved by interpolating the geometric information within the adjacent regions into the target region. Several methods of this group have been proposed [5,[START_REF] Bertalmío | Image inpainting[END_REF][START_REF] Tschumperlé | Fast anisotropic smoothing of multi-valued images using curvaturepreserving PDE's[END_REF][START_REF] Pérez | Poisson image editing[END_REF]. Generally, partial differential equation (PDE) based methods are the most studied ones.

Linear interpolation for inpainting

An early interpolation method is introduced by Ogden et al. [START_REF] Ogden | Pyramid-based computer graphics[END_REF] based on a pyramidal representation of the input image. Starting from an initial image, a Gaussian filtering is applied to generate a pyramid representation with iterated convolution and subsampling.

The inpainting process starts at lowest resolution where the unknown region is shrunk to only one pixel and filled in by extrapolation. Continuing this process, the higher levels can be completed by successive linear interpolations using the pyramid operators such as downsampling and upsampling.

The experimental results show that this approach could produce reasonable output in some simple occlusion situations. The result is so natural looking that the flaw would not be detected except by close examination.

PDE based inpainting method

In context of image processing, the terminology inpainting has been coined first by Bertalmío et al. in [START_REF] Bertalmío | Image inpainting[END_REF]. This approach is inspired from real painting restoration in the museums. The underlying idea of this algorithm is to propagate the geometric and photometric information arriving at the boundary of the occluded area, δΩ, into the area Ω itself. The inpainting information is updated iteratively until a steady state is attained using the following equation:

I n+1 (i, j) = I n (i, j) + ∆tI n t (i, j) (2.2)
where I n+1 is the restored image at the iteration (n + 1)th and ∆t is a user-defined value and called as the rate of change and I n t is the improvement of the image I n . The multiplication of the latter two terms gives the improvement observed in image I n+1 as compared to the previous version of the image, I n . To preserve both the propagation information and direction, the improvement is defined by the following equation:

I n t (i, j) = --→ δL n (i, j) -→ N n (i, j) (2.3)
where --→ δL n (i, j) represents a measure of the change in the propagated information at iteration n and -→ N n = ∇ ⊥ .I n . Here, the gradient vector at iteration n, noted ∇I n , is called isophote direction and ∇ ⊥ .I n defines the orthogonal direction of gradient.

As mention before, this algorithm tries to complete the damaged area with a smooth propagation from source region, thus selecting smoothness estimator is very important.

In [START_REF] Bertalmío | Image inpainting[END_REF], authors proposed the use of a simple discrete implementation of the Laplacian for propagation: L n (i, j) = I n xx + I n yy . The subscripts in the latter equation represent second derivatives. The main idea behind the calculation of the isophote direction is mainly based on obtaining the gradient vector at pixel location (i, j). The discretized gradient vector, ∇I n , gives the direction of largest spatial change, while its 90 degrees rotation is the direction of smallest spatial change, so the vector ∇ ⊥ I n gives the isophote direction. The removed text images using approaches in (c) [START_REF] Bertalmío | Image inpainting[END_REF] and (d) [START_REF] Bertalmío | Navier-stokes, fluid dynamics, and image and video inpainting[END_REF].

In subsequent works, Bertalmío et al. [START_REF] Bertalmío | Navier-stokes, fluid dynamics, and image and video inpainting[END_REF] has introduced an improvement of the previous work by using the classical fluid dynamics and Navier-Stokes equations (describing the motion of fluid substances). The authors established a connection between inpainting problem and fluid dynamics theory. In this context, the image intensity is equivalent to the fluid's stream, whereas the level lines in the image define the stream lines of the flow. Furthermore, the isophote direction is an equivalent of the fluid's velocity, while the smoothness of the image is comparable, in fluid dynamics terms, to the curl of the fluid's velocity, called vorticity. Following this approach, inpainting resumes to solving a vorticity transport equation, instead of the transport equation given in (2.3). Although the anisotropic diffusion equation is not the exact counterpart of the viscous diffusion term used in the Navier-Stokes model for incompressible and Newtonian flows, yet a lot of the numerical knowledge on fluid mechanics seem to be adaptable to design stable and efficient schemes for inpainting. For more detailed specification on the implementation, the reader is referred to [START_REF] Bertalmío | Navier-stokes, fluid dynamics, and image and video inpainting[END_REF]. Some outputs of these approaches are shown in Figure 2.3. In the first approach, the climb rate ∆t is set to 0.05, and the inpainting steps is set to 20.

Total variation based inpainting method

Another perspective on this group is proposed by Chan and Shen in [5,[START_REF] Chan | Mathematical models for local nontexture inpaintings[END_REF], where a denoising/inpainting first-order model based on the joint minimization of a quadratic fidelity term outside Ω and a total variation criterion in Ω is proposed. In this approach, the inpainting problem is considered as the minimization problem as following:

u * = argmin u ( I |∇u|dx + λ 2 Φ |u -u 0 | 2 dx) (2.4)
where u(x) is the intensity of the grey level at point x and λ is a Lagrange multiplier.

The first term in equation (2.4) is known as the regularising term or regulariser. The minimization of this term is responsible for the filling-in process inside the inpainting domain. The second term of the energy function is a measure of fidelity. This is nonnegative and has the property that it is zero when u(x) = u 0 (x) for every x ∈ Φ. Since we desire the value of u to be close to u 0 , we would like to keep value of the fidelity term as small as possible. In [START_REF] Chan | Mathematical models for local nontexture inpaintings[END_REF], the fidelity term is chosen to be square of the L 2 norm of u -u 0 because this is convex and differentiable.

The existence of solutions to this problem follows easily from the properties of functions of bounded variation. As for the implementation, a Gauss-Jacobi iteration scheme for the linear system associated to an approximation of the Euler-Lagrange equation by finite differences is applied to calculate the critical points of the energy function. The advantage of total variation over harmonic inpainting is that it is able to preserve discontinuities inside the inpainting area. More details could be found in [START_REF] Chan | Mathematical models for local nontexture inpaintings[END_REF].

In the framework of total variation in [START_REF] Esedoglu | Digital inpainting based on the mumford-shah-euler image model[END_REF], Esedoglu and Shen introduced an improved model, combining the celebrated Mumford-Shah segmentation model for images and the Euler's elastica model for curves. The elastica model is used instead of the fidelity term.

The energy function is modified as follows:

u * = argmin u ( Γ (α + βκ 2 )ds + λ 2 I\Γ |∇| 2 dx) (2.5)
Two numerical implementations to the minimization of such criterion are discussed fully in [START_REF] Esedoglu | Digital inpainting based on the mumford-shah-euler image model[END_REF]. The first one is based on level set approach where Γ is considered as the zero-level set of a sequence of smooth functions, and the explicit derivation using finite differences of the Euler-Lagrange equations associated with the criterion. The second implementation addressed by Esedoglu and Shen is a Γ -convergence approach based on a result originally conjectured by De Giorgi [START_REF] Giorgi | Some remarks on Γ-convergence and least square methods[END_REF] and recently proved by Schatzle [START_REF] Röger | On a modified conjecture of de giorgi[END_REF]. A comparison of efficiency between the two approaches is illustrated in Figure 2.4. In both cases, the final system of discrete equations is of order four, facing again difficult issues of convergence and stability.

Vector-valued image regularization with PDEs

In [START_REF] Tschumperlé | Fast anisotropic smoothing of multi-valued images using curvaturepreserving PDE's[END_REF], Tschumperlé et al. introduced an efficient second-order anisotropic diffusion model for multi-valued image regularization and inpainting. The regularization of an image is the process through which specific image is simplified in such a way that interesting features are preserved and unimportant data is removed. Given a R N -valued image, I, with the damaged region, Ω, and starting from an initial rough inpainting obtained by straightforward advection of boundary values, the pixels in the inpainting area are iteratively updated according to a finite difference approximation of the equation:

∂I i ∂t = trace(∇ 2 I i ) (2.6)
Here, T is the tensor field defined as:

T = 1 (1 + λ + + λ -) p 1 θ -θ -T + 1 (1 + λ + + λ -) p 2 θ + θ +T (2.7)
with 0 < p 1 p 2 , and λ -, λ + , θ -, θ + are the eigenvalues and eigenvetors, respectively, of the smoothed structure tensor field, G σ :

G σ = G σ * n i=1   ∂I i ∂x 2 ∂I i ∂x ∂I i ∂y ∂I i ∂x ∂I i ∂y ∂I i ∂y 2   (2.8)
where σ depends on the noise scale. Based on image regularization, this method successfully fills in the gap by diffusing the boundary pixels until completion of the missing areas, in a structure preserving way. The main drawback of this problem is the introduction of blur effect which results in unsharp edges inherent to PDE-based methods. Thus, it can be inferred that this technique will fail in reproducing textured region, but will successfully fill in small and narrow scratches.

DCT induced wavelet regularization for inpainting

With the advent of sparse representation and compressed sensing, sparse priors have also been considered for solving the inpainting problem. In [START_REF] Li | Adaptive inpainting algorithm based on dct induced wavelet regularization[END_REF], Li et al. assumed the input image is sparse in a given basis, discrete cosine transform (DCT) where the known and unknown parts of the image share the same sparse representation. The inpainting problem is solved based on an optimization model whose objective function is a smoothed 1 norm of the coefficient of the underlying image under a given redundant system generated from the DCT matrix of second type [START_REF] Ahmed | Orthogonal transforms for digital signal processing[END_REF]. Then, the DCT-Haar wavelet system is used as a filter and yields a redundant system.

The inpainting model, in this case, is formulated as an optimization problem in which the variational objective function has a regularization term formed by a sparse representation of the underlying image. Let f o the original image to be defined on the domain Ω = 1, 2, ..., n and a non-empty proper subset D of Ω be given. The observed image g is modeled as

g[k] =    f o [k] k ∈ Ω\D h[k] k ∈ \D (2.9)
where h[k] with k ∈ D could represent any types of degradations to the original image.

Then, the inpainting problem with a redendant system, W , generated from the DCT-II is as follows:

min f,d 1 2 ||W f -d|| 2 2 + ||Γd|| 1 : P D f = P D g (2.10)
where Γ is a diagonal matrix with non-negative diagonal components and d is an auxiliary vector. P D denotes the n × n diagonal matrix whose k-th diagonal entry is 1 if

k ∈ Ω\D and 0 if k ∈ D.
The solution is obtained based on an adaptive algorithm with some input parameters.

Some experimental results could be found in [START_REF] Li | Adaptive inpainting algorithm based on dct induced wavelet regularization[END_REF] show that the proposed approach is suitable for inpainting problems such as impulsive noise removal and filling missing information over regions with small sizes.

Texture-oriented methods

The second class of inpainting algorithms corresponds to texture-oriented (or exemplarbased ) methods. These approaches stem from the texture synthesis techniques where texture is modeled through probability distribution of the pixel brightness values. The exemplar-based algorithms tend to be less computationally efficient than interpolation and they also overcome the problems associated with interpolation. In fact, the actual pixel values of the known regions are used instead of average values as in the interpolation. The blurring effect is generally removed completely. In addition, several of these algorithms favor edges when choosing pixels to replace, this helps in preserving the edges within the missing regions and make it continuous in the output.

This group could be further subdivided into two sub-groups: greedy strategy and global optimization strategy. In the former group, the authors in [START_REF] Efros | Texture synthesis by non-parametric sampling[END_REF] proposed a pixel by pixel completion based on the matching patch comparison. An extension of this version was presented in [START_REF] Efros | Image quilting for texture synthesis and transfer[END_REF] where textures were synthesized patch by patch. However, these approaches are too slow or the input image contains only pure textures. Some sophisticated methods have been introduced such as fragment-based [START_REF] Jia | Image repairing: robust image synthesis by adaptive nd tensor voting[END_REF], user guidance based [40], probabilistic graphical model based [24,[START_REF] Komodakis | Image completion using efficient belief propagation via priority scheduling and dynamic pruning[END_REF], different priorities of filling [17,18,[START_REF] Wu | Object removal by cross isophotes exemplar-based inpainting[END_REF][START_REF] Zhang | Exemplar-based image inpainting using color distribution analysis[END_REF], etc.

Notwithstanding, these approaches suffer from problems such as local optimization, patch section, etc. In the later one, the inpainting problem is considered as a global optimization problem and it can be solved by optimizing discrete Markov Random Fields, as in belief propagation (BP) [24,[START_REF] Komodakis | Image completion using efficient belief propagation via priority scheduling and dynamic pruning[END_REF] and graph cuts [START_REF] Pritch | Shift-map image editing[END_REF][START_REF] Agarwala | Interactive digital photomontage[END_REF] or minimizing the coherence measure as in [START_REF] Wexler | Space-time completion of video[END_REF]. Nevertheless, the global optimization strategies are often more computationally expensive and its complexity is too high. Compared with the first class, the approaches in the second class achieve impressive results in recovering the large damaged regions but the output results may be distorted when the number of patches is insufficient.

Greedy strategy 2.3.1.1 From texture synthesis to patch-based inpainting

One of the early works in this group is introduced by Efros and Leung [START_REF] Efros | Texture synthesis by non-parametric sampling[END_REF][START_REF] Efros | Image quilting for texture synthesis and transfer[END_REF]. The initial goal of this approach was intended for texture synthesis and it results in good outputs in some cases of inpainting. The main idea is to fill-in the unknown pixel with known pixels based on their known neighborhood. The hole is completed recursively, inwards from the inpainting boundary. Start with an unknown pixel p ∈ δΩ, a known pixel, q ∈ Φ is used to fill-in pixel p if the neighborhood Ψ q of q is the most similar one to the neighborhood Ψ p of p. The similarity is considered to only known pixels in both Ψ p and Ψ q and is defined using the sum of squared differences (SSD) as follows:

d(Ψ p , Ψ q ) = i j ||Ψ p (i, j) -Ψ q (i, j)|| 2 (2.11)
This process is repeated randomly for every unknown pixel in the inpainting boundary until no pixel is found, so it is also known as onion peel. The main shortcoming of this algorithm is its computational time. In fact, this approach is quite slow since it works on pixel by pixel basis. In addition, since the filling order is random, it may fail to smooth boundaries of some objects. The patch size defined as a global parameter in original paper may make the output slip into wrong part or get locked onto one place and produce verbatim copies. In fact, this approach produces poor results for image perspective because it was intended to synthesize frontal textures but not inpainting problem. based on the correlation between unknown pixels and its neighbors to generate the shifted candidates for searching. Instead of searching on the whole image, only some candidates of the neighbors of p in the source region are considered. The speed-up achieved with this simple technique is considerable, and also there is a very positive effect regarding the visual quality of the output. Figure 2.6 illustrates the main idea of this approach.

Exemplar-based inpainting

From the limitation of Efros' work [START_REF] Efros | Texture synthesis by non-parametric sampling[END_REF], Criminisi et al. [17] improved on this work with two remarks. Firstly, the filling order is changed from the original "onion peel" into a priority scheme where unknown pixels at boundary of a hole have higher priority than one on flat 6. An illustration of Ahikhmin's texture synthesis method [START_REF] Ashikhmin | Synthesizing natural textures[END_REF]. The candidate patches are considered based on the correlation between unknown pixel and its neighbors.

regions. Thus, the completion is able to correctly inpaint straight object boundaries which could have otherwise ended up disconnected with the original formulation. Secondly, the filling process is implemented by copying entire patches (or exemplars) instead of single pixels, so this method is considerably faster. The algorithm is briefly described as the following steps:

1. Initialization: Identify the target region, Ω, and its boundary, δΩ. If there is no pixel on the boundary, i.e., δΩ = ∅, the algorithm is terminated.

2. Priority estimation: Compute the priority, P (p), for all pixels on boundary, p ∈ Ω.

Select randomly a pixel p with the highest priority and define its patch, Ψ p .

3. Patch match: Find the patch Ψ q that is most similar to Ψ p , with mean squared error of the known pixels and select randomly one if there are more than two patches.

4.

Inpaint: Fill the missing information in patch Ψ p by copying the corresponding pixels from patch Ψ q .

5. Update: Update the status information and return to the step 1 for next iteration.

As an example, Figure 2.7 gives an illustration of the steps in Ciminisi 's approach. The most important contribution in Criminisi 's work is designing the filling priority P (p) for each pixel in the hole boundary. In the original paper, the priority is built based on the isophote direction as in [START_REF] Bertalmío | Image inpainting[END_REF] and the known information of the current patch. Equation (2.12) expresses the priority measure.

P (p) = C(p)D(p) (2.12)
Here, C(p) and D(p) are called confidence and data terms, respectively and are defined by:

C(p) = q∈Ψp∩Φ C(q) |Ψ p | ; D(p) = |∇I ⊥ p .n p | α (2.13)
where |Ψ p | denotes the area of Ψ p and α is a normalization factor (e.g., α = 255 for a typical grey-level image), and n p is a unit vector orthogonal to the front δΩ at the pixel p. Figure 2.8 shows a result using Criminisi 's approach [17]. Two maps of confidence and data terms in inpainting process are shown in Figure 2.9.

It is worth noticing that the patch-based methods using priority has proven to be efficient in solving inpainting problem with large damaged region in image. Many extensions have been published to improve the quality as well as performance of the algorithm. In the work of Wu et al. [START_REF] Wu | Object removal by cross isophotes exemplar-based inpainting[END_REF], the priority is built based on cross-isophotes. In [START_REF] Zhang | Exemplar-based image inpainting using color distribution analysis[END_REF], authors defined the priority based on an analysis of color distribution. In other way, Cheng et al.

[18] recombined the priority using a regularizing factor. They observed that the confidence term drops rapidly to zero as the filling process proceeds, which makes the computed priority values indistinguishable, and in turn, the results in incorrect filling orders. Thus the priority function is modified to an additive rather than multiplicative forms. For more detailed specifications on the analysis, the reader is referred to [18].

While most image inpainting methods attempt to be fully automatic (aside from the manual setting of some parameters), they are user-assisted methods that provide remarkable results with just a little input from user. One of the known methods in this group has been introduced by Sun et al. [40]. The user must specify curves in the unknown region before inpainting. The curves will guide the recovery process. Firstly, patch synthesis is performed along these curves inside the image hole. Then, structure propagation will restore the rest. Figure 2.10 shows some interesting results of this approach. As can be seen, two different outputs are obtained using two different user-defined curves.

Data-driven inpainting

Following the success of patch-based methods, it becomes clear that the patches of an image provide a good resource to image editing. Most previous methods are strongly model-driven and have little adaption data. Rather than building mathematical models from scratch, the input image is considered as a dictionary of patches which can be used to express other parts of the image. This idea has been successfully applied to other areas of image processing, e.g. denoising and segmentation [START_REF] Mairal | Sparse representation for color image restoration[END_REF][START_REF] Martin | A database of human segmented natural images and its application to evaluating segmentation algorithms and measuring ecological statistics[END_REF][START_REF] Mcauley | Learning high-order mrf priors of color images[END_REF].

Following this idea, Mairal et al. [START_REF] Mairal | Sparse representation for color image restoration[END_REF] developed a framework using dictionaries of patches to restore the unknown region. The input image is broken into a set of patches with size n = √ n × √ n, called dictionary D, and they are vectorized into columns of D, represented by a matrix of size n × k (k is number of patches extracted from input image).

If α ∈ R k is a vector of coefficients, then Dα represents the patch obtained by linear combination of the column of D. Given an image v, the purpose is to find a dictionary D, an image u and coefficients' vector α which minimize the energy:

{ α, D, u} = arg min α,D,u λ||v -u|| 2 + ij µ ij ||α ij || 0 + ij ||Dα ij -Ψ ij u|| 2 (2.14)
In this equation, Ψ ij u denotes the patch of u and µ ij are positive weights. The inpainting problem can be considered as a case of non-homogeneous noise. Each pixel to be inpainted is defined by a coefficient β ij = 0 in the mask image. Then, the inpainting problem is expressed as follows:

{ α, D, u} = arg min α,D,u λ||β ⊗ (v -u)|| 2 + ij µ ij ||α ij || 0 + ij ||(Ψ ij β) ⊗ (Dα ij -Ψ ij u)|| 2 (2.15)
With suitable adaptation, this model has been applied to inpainting problem of relatively small gaps.

In [START_REF] Mobahi | Data-driven image completion by image patch subspaces[END_REF], Mobahi et al. extended this approach with the degenerate Gaussian assumption which results in more accurate and robust completion. The hole is filled-in using novel patches synthesize from a limited dictionary of real patches. The novel patches are linear combination of the real patches in the original image. Thus, even if no patch in the dictionary matches a given missing region, it is still possible to fill in the region with an appropriate linear interpolation of patches. To avoid problem of over fitting, the novel patch has sparse representation. To find more detailed implementation of this approach, the reader can refer to [START_REF] Mobahi | Data-driven image completion by image patch subspaces[END_REF].

Global optimization strategy

Exemplar-based methods have proven their effectiveness to image completion. But, in this case, a major drawback of related approaches stems from their greedy fashion of filling image, which can often lead to visual inconsistencies. In order to avoid the occurrence of visually inconsistent results, some other methods are preferred. A more global approach where the problem is formulated in a way that a deterministic EM-like optimization scheme has to be used for image completion [START_REF] Wexler | Space-time completion of video[END_REF][START_REF] Kwatra | Texture optimization for examplebased synthesis[END_REF] or discrete global optimization via Belief Propagation (BP) optimization [24,[START_REF] Meur | Super-resolution-based inpainting[END_REF] or graph-cuts algorithm [START_REF] Pritch | Shift-map image editing[END_REF][START_REF] Liu | Exemplar-based image inpainting using multiscale graph cuts[END_REF][START_REF] Granados | How not to be seen -object removal from videos of crowded scenes[END_REF] is considered. In general, the global optimization strategies often provide better results than greedy strategies, but they have main shortcomings of computational complexity and time running.

Space-time video completion

In [START_REF] Wexler | Space-time completion of video[END_REF], Wexler et al. considered the completion as a global optimization and the inpainting problem is extended to the restoration of video sequence. To allow for a uniform treatment of dynamic and static information, the video sequence is treated as space-time volumes, i.e., each pixel (x, y) in frame t will be regarded as a space-time point p(x, y, t) and each patch Ψ p is defined as a fixed-size window around p both in space and in time. The main idea of this approach is preserving the global visual coherence. A video S has global visual coherence with some other video D if every local space-time in S can be found somewhere in the video D. In other words, a video S can be restored with small windows in D.

Let S be an input sequence with a hole H ⊆ S. The inpainting problem is to complete H such that the result video S * will have as much global visual coherence with the rest of the input sequence, T = S \ H. Mathematically, this could be formulated as searching procedure for the sequence S * maximizes the following objective function:

Coherence(S * |T ) = p∈S * max q∈T sim(Ψ p , Ψ q ) (2.16)
where p, q run over all space-time points in their respective sequences, and Ψ p , Ψ q denote small space-time patches centered at p, q, respectively; sim is a local similarity measure between two space-time patches and defined through distance between two patches, d(Ψ p , Ψ q ), as follows:

sim(Ψ p , Ψ q ) = e -d(Ψp,Ψq ) 2 * σ
(2.17)

The choice of σ parameter is important as it controls the smoothness of the induced error surface. Very often, the sum of square differences (SSD) of color information is widely used for image completion but it does not suffice in this case. The main reason for this is that the human visual system is very sensitive to motion. Maintaining motion continuity is more important than finding the exact spatial pattern match within an image of the video. Therefore, the motion information must be included in the similarity measurement.

Indeed, each space-time point is extended into 5D representation (R, G, B, αu, αv) (α = 5 as in the original paper). Two added components, u = Y t /Y x and v = Y t /Y y , represent the instantaneous motion in the x and y directions, respectively. Here, Y x , Y y , Y t are the spatial and temporal derivatives of gray level at each space-time point (x, y, t).

Texture-oriented methods

The solution of equation (2.16) is obtained based on an iterative scheme using the Mean-Shift algorithm [START_REF] Comaniciu | Mean shift: A robust approach toward feature space analysis[END_REF]. A pseudo-code of this approach is described particularly in [START_REF] Wexler | Space-time completion of video[END_REF].

To further enforce global consistency and to speed up convergence, the iterative process is performed in multiple scales using spatio-temporal pyramids. Each pyramid level contains half the resolution in the spatial and in the temporal dimensions. The optimization starts at the coarsest pyramid level and the solution is propagated to finer levels for further refinement.

Belief propagation for image completion

Markov Random Field (MRF) models provide a robust and unified framework for early vision problems such as stereo and image restoration. Inference algorithms based on belief propagation (BP) have been found to yield accurate results. These methods are good both in the sense that the local minima they find are minima over "large neighborhoods", and in the sense that they produce highly accurate results in practice.

The general framework of this approach considers the inpainting problem in a global optimization framework where the optimal function is obtained by minimizing an energy function. Developing this idea, Komodakis et al. [24] has developed a novel optimization scheme to complete image based on belief propagation algorithm. Given an input image I as well as a target region T and source region S (S = I -T ). The goal of inpainting problem is to fill in T in a visually plausible way by simply copying patches from S. The inpainting problem is turned into a discrete optimization problem and is modeled as discrete MRF.

A set of labels L of the MRF consists of all patches from the source region S. Each label represents a patch, while each node n i is a lattice point whose patch intersects the target region. The edges E of the MRF will make up a 4-neighborhood system on that lattice.

Based on this information, the inpainting problem becomes a labeling problem in which find a set of labels l i ∈ L for each node n i so that the total energy E( l i ) of the MRF is minimized:

E( l i ) = N i V i ( l i ) + (i,j)∈E V i,j ( l i , l j ) (2.
18)

The single node potential V i (l), called label cost hereafter, for placing patch l over node n i , encodes how well that patch agrees with the source region around n i and equal the sum of squared differences (SSD) like equation (2.19).

V i (l) = p∈Ψn i M (n i + p)(I(n i + p) -I(l + p)) 2 (2.19)
where M is a binary mask. In a similar fashion, the pairwise potential V ij (l i , l j ), due to placing patches l i , l j over neighbors n i , n j , measures how well these patches agree at the resulting region of overlap and is again given by the SSD over that region.

To minimize the energy function, belief propagation algorithm is applied [START_REF] Pearl | Probabilistic reasoning in intelligent systems: networks of plausible inference[END_REF]. However, the main drawback of this approach is computational cost of belief propagation. Therefore, two major improvements over standard belief propagation are introduced such as "dynamic label pruning" and "priority-based message scheduling". Together, they bring a dramatic reduction in the overall computational cost of BP which would otherwise be intolerable due to the huge number of existing labels. The detailed scheme of "Priority-BP" algorithm for image completion is presented in [24].

A different setting has been proposed by Le Meur et al. First, a non-parametric patch sampling methods used to fill in missing regions. The inpainting algorithm is preferably applied on a coarse version of the input picture. Regarding priority for filling order, two data terms have been used: tensor-based [START_REF] Zenzo | A note on the gradient of a multi-image[END_REF] and 2.3. Texture-oriented methods sparsity-based [START_REF] Xu | Image inpainting by patch propagation using patch sparsity[END_REF]. For texture synthesis, a similarity measurement as in [START_REF] Meur | Super-resolution-based inpainting[END_REF] is used under a coherence constraint in [START_REF] Wexler | Space-time completion of video[END_REF].

Second, the output is enhanced the resolution and the subjective quality of the inpainted areas. The high-resolution is recovered using a single-image super-resolution approach. To combine multiple inpainted images, a Loopy Belief Propagation is applied with the same energy function as equation 2.19. Experimental results on a wide variety of images have demonstrated the effectiveness of the proposed methods. As applied in the field of computer vision, graph cuts can be employed to efficiently solve a wide variety of low-level computer vision problems such as image smoothing, the stereo correspondence problem, and many other computer vision problems that can be formulated in terms of energy minimization.

Graph cuts for image completion

(a) (b) (c) (d) e
In [START_REF] Pritch | Shift-map image editing[END_REF][START_REF] Agarwala | Interactive digital photomontage[END_REF], Pritch et al. considered and solved the inpainting problem in a different form of graph cuts. The main idea of inpainting problem is to copy pixels from the known region into the unknown regions. Thus, it is stated as a graph labeling problem which defines a relationship between them. Based on this observation, a shift-map, sm(x, y) = ( x , y ), is defined mathematically for the relationship and the output O(x, y) can be derived from the input pixel I(x + x , y + y ). Then, the optimal shift-map sm minimizes the following energy function:

E(sm) = α p∈I E d (sm(p)) + (p,q)∈N E s (sm(p), sm(q)) (2.20)
where α is a user defined weight balancing the two terms. The energy function has two terms such as data term E d which indicates constraints such as the change in image size, object rearrangement, or a possible saliency map, etc., while the smoothness term, E s minimizing the new discontinuities in the output image caused by discontinuities in the shift-map. They are defined by following equations:

E d (sm(p)) =    0 (p i + ∇i, p j + ∇j) ∈ Ω ∞ (p i + ∇i, p j + ∇j) ∈ Ω (2.21) E s (sm(p), sm(q)) =    0 sm(p) = sm(q) δI(sm(p)) + βδ∇I(sm(p)) otherwise (2.22)
where I and ∇I are the magnitude and gradient. δI and δ∇I denote their differences.

Parameter β is a weight to combine these two terms. After defining a global objective function and its constraints, the graph-cuts algorithm [START_REF] Boykov | An experimental comparison of min-cut/max-flow algorithms for energy minimization in vision[END_REF][START_REF] Boykov | Fast approximate energy minimization via graph cuts[END_REF] is applied to solve it. However, finding the optimal graph labeling can be computationally infeasible, due to the very large number of nodes and labels. To overcome this limitation, a hierarchical approach is designed to reduce the memory and computational requirements of graph-cuts algorithm as in [START_REF] Wexler | Space-time completion of video[END_REF]. Although the hierarchical approach is not guaranteed to give the global optimum, the results are very good as can be seen in the examples (Figure 2.13).

The proposed approach may have unexpected bias, and their visual quality is very often unsatisfactory. In [START_REF] Liu | Exemplar-based image inpainting using multiscale graph cuts[END_REF], authors improve the data term by comparing the patches Ψ p and Ψ p+sm(p) for the pixels near boundary ∂Ω. The patches are compared only using their known pixels. This term ensures the continuity of the reconstruction on the boundary. An extension of this approach has been developed for video inpainting in [START_REF] Granados | How not to be seen -object removal from videos of crowded scenes[END_REF]. A 3D offset, spatio-temporal displacement sm(x, y, t), including temporal component is replaced for 2D offset. For further study, please refer to [START_REF] Granados | How not to be seen -object removal from videos of crowded scenes[END_REF].

E d (sm(p)) = p∈∂Ω D(Ψ p , Ψ p+sm(p) ) (2.

Hybrid inpainting methods

In general speaking, both texture synthesis and diffusion have their own advantages and drawbacks for image inpainting. Most inpainting methods in the first group presented so far perform well in case of small or thin damaged regions. However, they are unable to restore texture properly, and they introduce blur artifacts on large inpainting regions. Whereas, most inpainting methods in the second group are not able to handle sparse inpainting domains where no valid squared patch can be found that does not reduce to a point.

Indeed, natural images are composed of structures and textures. Structures refer to edges or contours and textures are image regions with homogeneous patterns or feature statistics. This is why pure texture synthesis techniques cannot be efficiently applied to missing regions/objects with composite textures and structures. To overcome the weakness of these methods, there have been several attempts to explicitly combine texture-based and geometry-based methods for completing the damaged regions, called hybrid methods.

The work of Bertamío et al. [START_REF] Bertalmío | Simultaneous structure and texture image inpainting[END_REF] used an additive decomposition of the image to be inpainted into a geometric component that contains all edges information, and a texture component. Then, the geometric image is interpolated with the method proposed in [START_REF] Bertalmío | Image inpainting[END_REF],

while the texture image is restored using the method introduced by Efros and Leung [START_REF] Efros | Texture synthesis by non-parametric sampling[END_REF].

The final image is obtained by addition of the restored texture and geometric components.

In a few situations where the additive decomposition makes sense, this approach does indeed improve the result and extends the applications domain of inpainting. A basic framework of such an approach is shown in Figure 2.14.

Figure 2.14. Basic scheme of the method in [START_REF] Bertalmío | Simultaneous structure and texture image inpainting[END_REF]. The input image is decomposed into the structure and texture images. These two images are reconstructed via inpainting [START_REF] Bertalmío | Image inpainting[END_REF] and texture synthesis [START_REF] Efros | Texture synthesis by non-parametric sampling[END_REF]. The output is obtained by adding back two reconstructed images.

In [START_REF] Sangeetha | Combined structure and texture image inpainting algorithm for natural scene image completion[END_REF], Bugeau et al. introduced a different combination of two kinds of inpainting methods. The original image is first inpainted with the anisotropic smoothing method from Tschumperlé [START_REF] Tschumperlé | Fast anisotropic smoothing of multi-valued images using curvaturepreserving PDE's[END_REF] before decomposing into two parts: a structure and a texture image using the texture-structure image decomposition in [START_REF] Vese | Modeling textures with total variation minimization and oscillating patterns in image processing[END_REF]. Because the diffusion algorithm is unable to restore the texture parts, the texture image is then reconstructed using the algorithm in [17]. For each pixel in the damaged regions, a texture synthesis is carried out if that pixel does not belong to a strong structure. On the other hand with diffusion method, we should keep the current intensity values on the important structures and only apply texture synthesis on the other pixels. The notion of strong structure depends on the force of the gradient which can be characterized by the tensor of structure eigenvalues as equation (2.24).

λ + (p) -λ -(p) < β (2.24)
where β is a threshold equal to mean:

β = q∈Φ λ + (p) -λ -(p) |Ω| (2.25)
Finally, the restored image is obtained by adding back the restored texture image into the diffused image.

Authors in [START_REF] Sairam | A unified framework for geometry and exemplar based image inpainting[END_REF] introduced a different process of unifying the geometric and exemplar approaches for image inpainting based on graph regularization. The advantages of using graph is that they can model well the interactions between data. The local or non-local regularization can be derived by the way the connections are made in the graph. Moreover, a novel data term for filling-order has been proposed based on the gradient of the current pixel as follows:

D(p) = |∇I(p)| + log(1 + |∇I(p)|) (2.26)
where ∇I(p) is the gradient of the image at pixel p. The detailed unification algorithm and illustrations are given in [START_REF] Sairam | A unified framework for geometry and exemplar based image inpainting[END_REF]. Unlike other works, the decision regarding exemplar or diffusion is made dynamically at each pixel based on texture information. Gabor filter responses at different orientations and scales are applied to automatically decide if diffusion or exemplar method to be used in the course of inpainting.

Beyond single image inpainting

All the methods mentioned above involve just a single image. On the other hand, the missing information is filled in based on the known information from the image itself.

Since the development of internet as well as the image retrieval techniques, searching a set of images similar to query image becomes easier. In this case, inpainting a single image using information from several images could be a valuable direction.

An idea of using large regions of other images for image completion was explored by

Hays and Efros [START_REF] Hays | Scene completion using millions of photographs[END_REF] who performed inpainting of a single image using information from a database with several millions of photographs. They used the gist scene descriptor [START_REF] Torralba | Context-based vision system for place and object recognition[END_REF][START_REF] Oliva | Building the gist of a scene: the role of global image features in recognition[END_REF] which has been shown to perform well at grouping semantically similar scenes (eg. city, tall buildings, office, fields, forest, beach) and for place recognition to reduce the search space from two million to two hundred images, those images from the database which are semantically closer to the image the user wants to inpaint. Using template matching, they align the two hundred best matching scenes to the local image around the region to inpaint.

Then, they composite into the target image each matching scene into the target using seam finding and image blending.

Conclusion

In this chapter, an overview of current inpainting algorithms is presented. Starting from the earliest work until the present, a series of inpainting algorithms has been summarized

to provide for reader a basic look of digital image inpainting developed during the last decade.

While many PDE/variational methods have been developed and considered as the first group of inpainting techniques, the experimental results indicated that most methods in the first group were particularly effective for the synthesis of long, thin regions. Since these methods focused on maintaining the structure of the inpainting area, they are less suitable for synthesize semantic textures or structures. First, the interpolation tends to produce a blurring effect on missing spots in the image. For scratches and thin markings, the blurring can produce a very acceptable output image. Second, the interpolation does not distinguish the structures and edges in the image. Namely, if a missing region intersects an edge in the image, typically the output will not connect the edge through the missing region and this can lead to very noticeable defects in the output image.

The second group is texture-oriented methods inspired from texture synthesis techniques. These methods tend to be less computationally efficient than interpolation and overcome the problem associated with interpolation. Since the actual pixel values of the known regions are used instead of average as in interpolation, the blurring effect is generally removed completely. This group could be further subdivided into two sub-groups:

greedy strategy and global optimization strategy. The greedy strategy have acceptable computation time and take into account human perception features (priority is designed based on the salient structures considered as important for human perception), but they

show some common problems such as local optimization, patch priority, patch selections, etc. Whereas, global optimization strategies often provide better results. Nevertheless, they are computationally expensive. This is mainly due to the fact that time complexity increases linearly both with the number of source pixels and unknown pixels.

Some other methods are categorized as the third group, hybrid methods which combine texture-based and geometry-based methods in order to complete properly the damaged regions. The original image is decomposed into two parts: a texture image and a geometry image. Each part is restored using methods in the corresponding group. The final result is reconstructed by adding back two restored parts. In a few situations where the additive decomposition makes sense, this approach does indeed improve result and extends the applications domain of inpainting.

Recently, beyond single image inpainting, a novel direction of inpainting problem has been introduced that is inpainting a single image using information from several similar images instead of that image itself. These approaches also have drawbacks of managing and operating a huge image database. Indeed, the completion is meaningful if it is performed blindly, i.e. without reference to original images or other images.

Although hundreds of publications have been introduced during the last decade, there is still room for developing other approaches to overcome the limitation of the existing methods as well as obtain better outputs. One promising direction for improving them is use of perceptual models which can result in more plausible outputs. In summary, we believe that perceptual-based approaches are more potential and promising. Image completion in the case of images with large missing regions is a very challenging problem. As summarized in the Chapter 2, several solutions have been developed to tackle this problem. In this chapter, we introduce a novel framework based on hierarchical representation which deals effectively with the case of filling in large missing areas. The following sections describe in detail the main stages of the proposed method. The performance of proposed methods is evaluated and discussed based on a series of experimental results.

A hierarchical approach for image completion

The exemplar-based methods consist of two key steps: the determination of filling order and the selection of the best matching patch. The crucial part of this model is the filling priority which is designed to preserve linear structure. The isophote-driven priority proposed in [17] generates pleasant outputs in many cases, but it still has many drawbacks. Many modified versions have been developed [18,[START_REF] Wu | Object removal by cross isophotes exemplar-based inpainting[END_REF][START_REF] Zhang | Exemplar-based image inpainting using color distribution analysis[END_REF]. However, the regions with high isophote strength, which may be certain high frequency components such as noise and complex textures, are not equivalent to the structural features e.g. edges, contours, etc.; therefore, it may lead to undesired results.

The second part in this model is patch selection. By using only the best match sample, the method runs the risk of choosing a sample that is corrupted, or not a perfect match.

Therefore, choosing the suitable patch for piecing also significantly affects to the inpainting quality of an image with redundant content where several samples could be combined to form a more robust estimate of the missing information. Some techniques [START_REF] Anupam | Fast and enhanced algorithm for exemplar based image inpainting[END_REF][START_REF] Wong | A nonlocal-means approach to exemplar-based inpainting[END_REF] have been introduced to improve for patch selection, but there still remain some issues such as introduction of blur artifacts because of interpolation or missing correct information for filling in a region when it is located far away from that region.

Our framework is designed to overcome the limitations of the current exemplar-based methods in both these steps. The proposed technique is inspired by the observation that the human visual system is sensitive to salient structures which are stable and repetitive at different scales. In other words, one can still see the main structural features when the resolution of the image is reduced to a given factor. Therefore, a hierarchical image inpainting scheme is developed in order to control and preserve salient features during the completion process. This scheme allows restoring the missing regions in a visually plausible way.

Algorithm overview

The proposed approach is composed of two main successive operations based on a greedy strategy. Firstly, a single resolution is restored as in the framework [17]. At low resolution the inpainting is less sensitive to local singularities and noise effect, but it may be affected by blur artifacts due to the reduction operation. Thus, in order to classify more logically image components, a novel priority definition is introduced. Secondly, the damaged region on the higher resolution image is completed by exploiting spatial information contained in the lower resolution image provided at previous step. At higher resolution, multiresolution patches are the best way to preserve the main features in the restoration process.

By applying window-based priority, the decision is more suitable to maintain the high frequency components in a visually plausible way. By estimating patches at different scales, the selected patch would be more consistent and faithful to the source patch than one in a single resolution. Furthermore, it is much less computationally demanding than when processing the original full resolution, and hence it copes well with the problem of large region inpainting.

At the beginning of the proposed algorithm, a Gaussian pyramid is constructed from the image to be inpainted. This step consists of low-pass filtering and downsampling images of the preceding level of the pyramid. According to the above idea, a set of images {G 0 , G 1 , ..., G N } with various levels of details is generated, where G 0 = I is the input or original image [START_REF] Burt | The laplacian pyramid as a compact image code[END_REF]. The number of pyramid levels is linked to the original size of the image and the smallest allowed resolution. The minimum size should be adjusted according to the width and height of the original image. In our experiments, to avoid missing relevant details, the following condition is used:

min(width(G N ); height(G N )) ≥ 32.
The inpainting regions are also reduced level by level. Then, an exemplar-based method for image completion with some modifications is applied at each level. An iterative process is completed gradually from the lowest resolution, G N , to the highest resolution, G 0 . The algorithm is fully described in Algorithm 3.1. Although different criteria for stopping the process can be used depending on application, we opted for a fixed number of iterations.

All the results shown in our thesis were computed with only 2 or 3 iterations.

Algorithm 3.1. The proposed framework.

G 0 = I; {G 1 , G 2 , ..., G N } = buildP yramid(G 0 );
Complete G N with the scheme in [17] using window-based priority in section 3.1.2.1; while (stop=false) do for detail level i = N -1 downto 0 do Complete G i with the scheme in [17] using using multi-resolution patch in section 3.1.2.2 and the window-based priority in section 3.

1.2.1; end {G 1 , G 2 , ..., G N } = buildP yramid(G 0 ); end Output = G 0 ;

Inpainting the lowest resolution image

In order to integrate some low-level features of the HVS and simulate its hierarchical perceptual properties, an exemplar-based method is applied to the lowest resolution image, G N . In the proposed scheme, an extension of [17] is developed to complete the coarse resolution. Generally, there are two main steps in this scheme: i) determination of the filling order and ii) selection of the best matching patch. Both steps are analyzed in details in the succeeding two subsections.

Window-based priority for filling order

Naturally, the exemplar-based algorithm is a greedy strategy, an acceptable computation load; however, it suffers from the common problems of the greedy algorithms, in which the filling order (namely priority) is very critical. An appropriate definition of the priority is essential since the decision, taken with it, is irreversible in the following stages. Otherwise, errors may accumulate continuously because no improvement is achieved on previous stages. Many formulations have been proposed for priority selection [17,18,[START_REF] Wu | Object removal by cross isophotes exemplar-based inpainting[END_REF][START_REF] Zhang | Exemplar-based image inpainting using color distribution analysis[END_REF]. In this work, we would like to introduce a new priority, called window-based priority, which is considered as more robust and efficient than others. Classically, a priority, P (p), is composed of two terms: i) confidence term and ii) data term [17]:

P (p) = C(p)D(p) (3.1)
In [18], the authors discovered that the confidence term in [17] decreased exponentially and proposed an additive form of priority which used weights to maintain a balance between the confidence term and the data term.

RP (p) = α((1 -ω)C(p) + ω) + βD(p) (3.2)
where ω ∈ [0, 1] is the regularizing factor for controlling the curve smoothness (in experiment, ω is often set to 0.7), the value range of C(p) is regularized to [ω, 1], and α, β are positive parameters with α + β = 1.

Here, we concentrate on the analysis of the data term which distinguishes the structures from the textures. The confidence term is not mentioned here since it does not provide any additional improvement. A data term with a high value indicates the presence of a structure or contour, while a low value introduces the presence of texture or flat region. In [17,[START_REF] Wu | Object removal by cross isophotes exemplar-based inpainting[END_REF], authors introduced a pixel-based data term, D(p), depending proportionally on the isophote direction or gradient of the known region. Thus, if the gradient at pixel p is large, the priority will be high. By the way of explanation, when the gradient values of the texture components are greater than those of the structure components or when the regions are affected by noise, the isophote-driven priority method may violate the requirement of an appropriate priority rule and yields bad results. To overcome this difficulty, a patchbased data term is introduced as in [START_REF] Zhang | Exemplar-based image inpainting using color distribution analysis[END_REF][START_REF] Xu | Image inpainting by patch propagation using patch sparsity[END_REF]. This solves to some extent the problem but at the cost of an increased running time and complexity.

Reasonably, the data term should be estimated from all neighborhood pixels in an exemplar centered on the current pixel, because the human vision is good at seeing the group of adjacent pixels rather than single pixel. Our first improvement focuses on a better definition of data term based on the local changes of pixel intensities in each window, W p , centered at pixel p(x, y) with shifted windows in different directions. The local change of intensity at each pixel p(x, y) is characterized by the following second-moment matrix or structure tensor [START_REF] Harris | A combined corner and edge detector[END_REF]:

M (p) = Wp G Wp (x, y)   ∂I ∂x 2 ∂I ∂x ∂I ∂y ∂I ∂x ∂I ∂y ∂I ∂y 2   (3.3)
where G Wp is a Gaussian window function. This structure tensor is a 2 × 2 symmetric and semi-positive matrix which captures the intensity structure of the local neighborhood.

The 2D structure tensor and its eigenvalues, λ 1 ≥ λ 2 ≥ 0, summarize the distribution of the gradient within the defined window. The two corresponding eigenvectors represent two orthogonal directions along the local maximum and minimum variation of image intensities.

Whereas, the eigenvalues measure the effective variations (strength of contours) of image intensities along these vectors. Consequently, our data term is defined as follows:

D(p) = λ 1 λ 2 + (3.4)
where is a very small positive value introduced to ensure computation stability (in our experiment, = 10 -10 ). This data term is related not only to geometric features, such as contours or edges but also texture features. There are three cases to be considered for each window as those defined by Beaudet [START_REF] Beaudet | Rotationally invariant image operators[END_REF] and illustrated in Figure 3.1:

• If the data term is much greater than one i.e. one eigenvalue is high (λ 1 is high) and the other is low (λ 2 is low), the local shifts in one direction cause little change and significant change in the orthogonal direction; the window contains strong edges;

• If the data term is close to one, i.e λ 1 is approximate to λ 2 , there are two possible cases:

-If both eigenvalues are high, the shift in any direction will result in a significant change. This indicates a texture or complex structure.

-If both eigenvalues are small, the shift in any direction will cause a little change.

The patch is of approximately constant intensity (flat region). Because both confidence and data terms are evaluated by contribution of all pixels in a window, our priority is called a window-based priority [61]. With this priority, the patches are classified in a more robust way and the computation time is acceptable. Table 3.1 illustrates some numerical values corresponding to subimages in Figure 3.2. In our opinion, the contours should be preserved, thus the priority of pixels on the contour should be higher than others. Obviously, the values in Table 3.1 demonstrate that our priority is more reasonable than the ones proposed in [17] and [START_REF] Wu | Object removal by cross isophotes exemplar-based inpainting[END_REF].

(a) (b) (c)

Patch

Priority in [17] Priority in [START_REF] Wu | Object removal by cross isophotes exemplar-based inpainting[END_REF] Proposed Priority (λ 1 , λ 2 ) Flat region 0.001 3.269 0 (Fig. 3

Patch selection

The second step of the proposed algorithm consists in finding the suitable patch for the filling process. The similarity measurement, computed based on all known pixels in the patch, should be consistent with human perception. When using only color information, it is insufficient to propagate accurate linear structures into the target region and leads to uncontrolled and incoherent increase. This is mainly due to the fact that the perceptual color appearance depends not only on the color of the observed patch but also on the surrounding and the context in which the patch is perceived. Consequently, to solve this problem, a similarity measure which takes into account the difference in colors and gradients is proposed below:

3.1. A hierarchical approach for image completion d(Ψ p , Ψ q ) = i (θ(I i p -I i q ) 2 + (1 -θ)(∇I i p -∇I i q ) 2 ) (3.5)
where I p and I q are the corresponding RGB vectors in patches Ψ p , Ψ q ; ∇I p and ∇I q represent the image gradient vectors; θ is a user defined weight balancing the two terms, here we set θ = 2/3 in the experiment. The image gradient is added as an additional weight to maintain the color intensity variation from the known region to unknown region.

The target patch with the minimal distance to the source one, Ψ p , is the one that should be selected. It is given by:

Ψ p = arg min Ψq∈Φ {d(Ψ p , Ψ q )} (3.6)
As noticed in [START_REF] Anupam | Fast and enhanced algorithm for exemplar based image inpainting[END_REF], a major problem of local neighborhood search is its tendency to get stuck at a particular place in the same image and to produce verbatim copying. This may also generate blocking artifacts around the inpainted regions. In order to address this problem, we propose an improvement for the patch selection step. The idea is based on the fact that patches in the neighborhood in the input image should remain neighbors in the output image. First, K most similar patches obtained by the local neighborhood search patches are used as candidates. Second, for each patch, Ψ p , a standard deviation describing the variability of neighboring source patches is formulated as follows:

V (Ψ p ) = E∈{R,G,B} (E(Ψ p ) -Ē(Ψ N (p) )) 2 |N (p)| (3.

Multi-resolution patch for higher resolution image completion

The second advantage of our method is the use of a multi-resolution patch-based scheme on the image pyramid [START_REF] Burt | The laplacian pyramid as a compact image code[END_REF]. A multi-resolution patch, Ψ p , consists of two consecutive scales: one at the current level l, Ψ l p , and one at its parent level l + 1, Ψ l+1 p . Figure 3.6 illustrates an example of multi-resolution patch Ψ p , that contains various single resolution patches with different sizes. The sizes of patches are global parameters and denoted as {(w 1 × w 1 ); (w 2 × w 2 )}, where the former is for current level and the later is for the higher level. w 1 is often greater than w 2 because of the image resolution. In our work, we set w 1 = 2w 2 because the ratio between two consecutive images in the pyramid representation is 2. Consequently, the similarity between two multi-resolution patches at higher resolution is measured by the sum of the squared distance of all known pixels in both adjacent levels and is reformulated as follows:

d(Ψ p , Ψ q ) = d 1 (Ψ l p , Ψ l q ) + d 2 (Ψ l+1 p , Ψ l+1 q ) (3.9)
where d 1 , d 2 are similarity of the known pixels in the current and higher level, respectively; they are computed by Equation (3.5) within the corresponding patches. 6 exhibits an example of multi-resolution patch which is being applied for image completion using multi-resolution representation. All pixels of multi-resolution patch at higher level l + 1 have been restored completely, while a part of current level l marked by white is needed to be restored. This example shows a relationship between the restoration of the current and higher level patches.

Experimental results

The proposed image completion framework was tested on a series of different natural images and the results are presented in this section. To compare the effectiveness of our algorithm and to do it in an equal footing, we apply our technique on both data provided by [17] and other real images. The performance is compared with the existing exemplar-based methods in terms of the inpainting quality.

In most experiments, all of the algorithms are implemented in the same programming framework, C/C++ language and Matlab. The parameters are fixed at constant values for all tested methods so as to avoid any bias in the comparison. Specifically, the patch sizes are set to {(9 × 9); (5 × 5)} for our approach and (9 × 9) for other exemplar-based methods. The size of window priority is set to (7 × 7). The missing regions are marked by the green color (R=0, G=255, B=0). In some applications, the visual quality of the outputs is the most important consideration. Therefore, in this work, we concentrate on only evaluating and comparing the outputs in terms of the visual quality. Five images, including three natural images and two real archaeological images (listed in Table 3.3), were presented to validate our algorithm in comparison with other approaches. The damage areas occupy 10.73%, 9.29%, 14.8%, 5.83% and 3.43% of the whole image, respectively. Although areas of holes account for small percentage of the area, they are still considered as large areas with respect to our definition in the section 1 of chapter 2.

The visual results in Figures 3.7 As we can observe from these figures, our method produces a better visual quality than the other methods. We should mention that for performance evaluation, we use only subjective criteria, i.e., visual appearance of the output because there is no efficient numerical estimation for outputs of inpainting methods.

A hybrid approach for high-quality fast image completion

In previous section, a greedy strategy has been introduced in conjunction with a hierarchical representation for image completion. This strategy is applied not only for the lowest resolution but also for higher resolution. The greedy strategies generally have computation time better than the global optimization strategies. In addition, they take into account the human vision features because the priority is designed based on the salient structures which are sensitive to human vision system. However, they suffer from the common problems of greedy algorithms, such as, local optimization, patch selection, patch search, etc. The global optimization strategies often have better results but they are more computationally expensive than the greedy ones because the time complexity increases linearly with the number of labels and the number of unknown pixels. In practice, image completion is often applied with user interaction and needs quick feedback.

In this section, we would like to propose a novel improvement of previous framework for high-quality and fast image completion by combining a greedy strategy and a global optimization strategy based on a pyramidal representation of the image. There are some reasons when applying the greedy strategy for lower resolution image.

• Firstly, the human visual system is sensitive to salient structures that are stable and persistent through different scales. In other words, the most relevant structural information of an image remains visible and attractive at different levels of resolution.

Therefore, this observation is exploited when performing image inpainting.

• Secondly, at low resolution the inpainting would be less sensitive to local singularities and noise effect.

• Finally, it is much less computationally demanding than when processing the original full resolution image and it copes with the problem of large regions inpainting.

The second operation consists of restoring the damaged region on the original high resolution image by exploiting spatial information contained in the lowest resolution image provided at the first step. At higher resolution, the inpainting problem is modelled as an optimal graph labeling where an offset-map represents the selected label for each unknown pixel. The offset map is initialized from an interpolation of lower resolution and refined for current resolution by optimizing an energy function using multi-label graph cut technique [START_REF] Boykov | An experimental comparison of min-cut/max-flow algorithms for energy minimization in vision[END_REF][START_REF] Boykov | Fast approximate energy minimization via graph cuts[END_REF]. Because each unknown pixel in the damaged region could originate from any pixel in the source region, the global optimization strategies can be computationally unfeasible.

Some existing global optimization methods consider possible assignment fairly but this does not fit the human perception criteria. In term of inpainting quality, fair assignments may lead to unexpected bias for optimization. In terms of speed, a huge label set requires high computational load.

A hybrid approach combining the greedy and global optimization strategies is the best solution to enhance not only inpainting quality but also computational time. A full description of our combination is given in the Algorithm 3.2 [START_REF] Dang | Archaeological image inpainting[END_REF].

Algorithm 3.2. The improved framework.

G 0 = I; {G 1 , G 2 , ..., G N } = buildP yramid(G 0 );
Complete G N with the scheme in [17] using window-based priority in section 3.1.2.1;

om N = generateShif tM ap(G N ) ; for detail level i = N -1 downto 0 do om i = interpolate(SM i+1 ) ; om i = optimize(om i , G i ) ; end G 0 = restore(om 0 , G 0 ); Output = G 0 ;
The main improvement of this algorithm is using an offset-map, om i , at higher levels (i > 0) instead of using directly the pyramidal images. At the lowest resolution, the image is completed by the same strategy as mentioned in previous section, an exemplarbased strategy. Then, a relationship map between the damaged pixels and source pixels, called offset-map, is generated as an initial guess map for next stage. In this situation, the inpainting problem is considered as an optimal graph labeling where the offset-map represents the selected label for each unknown pixel. This offset-map is then interpolated and refined for higher resolution image gradually to obtain the latest one which is the best solution for inpainting problem at original resolution. Because only a few labels relative to the initial guess are considered based on the optimized map instead of all possible labels, this implementation is much faster than the previous framework in which patch searching is performed on the whole image; furthermore, the quality of inpainted image will be significantly improved by a global optimization algorithm.

Offset operator

The nature of inpainting is filling in the hole by the known pixels. In other words, the intensities of unknown pixels are copied from the known pixels. This formed naturally a relationship between the unknown pixels, p(x p , y p ) ∈ Ω, and known pixels, q(x q , y q ) ∈ Φ.

And this relation is characterized by an offset-map which determines a shift from known pixel to unknown pixel for each coordinate in the image (see Figure 3.12-a). The map can be formulated by equation (3.10):

om(p) = ( x, y) p ∈ Ω (0, 0) otherwise (3.10)
Then the output pixel O(p) will be derived from the input pixel I(p + om(p)). Because the objective of inpainting is to restore the damaged regions so that it still looks natural, the offset-map must be determined to satisfy this criteria. Authors of [START_REF] Pritch | Shift-map image editing[END_REF] proposed a solution to evaluate the offset-map by designing energy function and optimizing it. The energy function is defined as follows:

EM = α p∈Ω E d (om(p)) + (1 -α) (p,q)∈N B E s (om(p), om(q)) (3.11)
where E d is the data term related to external constraints and E s is a smoothness term defined over a set of neighboring pixels, N B. The parameter α is a user defined weighting factor, which is set to α = 0.5 in our case to balance the two terms. Thereafter, EM is used to minimize the energy related to both data and smoothness terms. Several optimization approaches have been proposed in the literature. In our method an optimization scheme based on graph cuts technique [START_REF] Boykov | An experimental comparison of min-cut/max-flow algorithms for energy minimization in vision[END_REF][START_REF] Boykov | Fast approximate energy minimization via graph cuts[END_REF], known for its computational advantages, is used.

Data term

The data term, E d , linked to external constraints, measures how appropriate is a label or an offset. During the completion process, for each pixel in the target region, an offset is assigned to the pixel in the known regions. This offset is used in the computation of the data term to avoid including pixels from the missing regions. On the other hand, the data term dictates that no pixels in the hole are used in the output image. The detail of data term is given by equation (3.12):

E d (om(p)) = ∞ (x + x, y + y) ∈ Ω 0 otherwise (3.12)
In some cases, the specific pixels in the input image can be forced to appear or disappear in the output image by setting E d . For example, we can use saliency map to weigh the data term. Therefore, a pixel with a high saliency value will be kept; whereas, a pixel with a low saliency value is removed. Figure 3.12-c illustrates visually how to adapt the value of the data term.

Smoothness term

The second component of the energy function is the smoothness term representing the discontinuity between two neighboring pixels p(x p , y p ) and q(x q , y q ). In [START_REF] Agarwala | Interactive digital photomontage[END_REF], the authors proposed an effective formula, expressed in equation (3.12), for smoothness term taking into account both color differences and gradient differences between corresponding spatial neighbors in the output and input image to create a coherent stitching. where I and ∇I are the magnitude and gradient at these locations, p = p + om(p)

and q = q + om(q) are locations which are used to fill for pixels p and q, respectively, and n p and n q are two 4-connected neighbors of p and q , respectively. Figure 3.12-d depicts an intuitive way for evaluating the smoothness term. The main idea is based on the fact that if a pixel is used for filling, then its neighbors should be also filled as neighbors in the inpainted regions. Moreover, the difference between filled pixels and their neighbors in the target region and known region should be as small as possible.

Offset-map interpolation

A full offset map is first inferred from a completion at the lowest level of the pyramidal representation of the input image. Then, it is interpolated to higher resolutions using the nearest neighbor algorithm, and the offset-map values are upscaled by simply doubling each value to match the image at higher resolution.

In the higher level, only small shifts relative to the initial guess are examined. This means that only some neighbors of its parent is considered instead of all possible labels. In our implementation, the relative shift for each coordinate varies in range [-a, a], so it takes (2a + 1) 2 labels for both direction. It is important to note that the data and smoothness terms are always computed with respect to the actual shifts and not to the labels.

Experimental results

The efficiency of our improvement is illustrated through the experimental results. This section evaluates the results of our approach and compares it with the state-of-the-art methods. A series of natural images is selected for testing. The parameters of the algorithm are kept constant throughout the experiments.

Comparative study

Firstly, we would like to evaluate the performance of our proposal based on a comparison with some state-of-the-art methods belonging to the same category of inpainting method.

Four methods listed in Table 3 The obtained results, shown in Figure 3.15, demonstrate the efficiency of our method in terms of visual quality compared to the state-of-the-art.

Comparison with unoptimized version

Secondly, a comparison with unoptimized version has been performed in order to confirm the quality of our results. Our method is developed based on a previous idea presented in [61] but with the use of a multi-resolution patch matching instead of an offset-map optimization, called here unoptimized version.

Results obtained with the latter are compared to those of the proposed approach (see Figure 3.16). It is clearly shown that our method (Figure 3.16-c) is slightly better than the method proposed in [61]. However, the performance in term of computational complexity of our proposal is rather better than the unoptimized approach. This issue is discussed in more details in the next section.

Performance evaluation

The visual quality of the results obtained with the proposed approach has been discussed in the previous sections. In the following we focus on the performance evaluation in terms of computational efficiency. For the sake of completeness and clarity the performance of the method is evaluated at each stage at the global level. The benefits gained at each stage are demonstrated through the obtained results.

Local performance evaluation

In the following, the greedy strategy using window-based priority and path-match search procedure is analyzed in order to estimate the contribution of each stage in our algorithm.

The global optimization strategy adopted in the proposed method is also analyzed to confirm the outstanding performance in comparison with other approaches. The performance analysis of the proposed method at the different stages, expressed in percentage, is given in Table 3.5 for a set of nine images and illustrated visually in the chart Thus, the time complexity for this strategy is very low. There are two main sub-stages in this strategy: window-based priority and patch match search. From Figure 3.17, it is clearly shown that these steps account for a very small portion of the whole process (average time about 0.18% for window-based priority, 0.78% for patch-match searching and 1% for entire completion of the lowest resolution).

It is worth noting that the execution time is mainly due to global optimization at higher resolutions. The higher resolution levels are the most time-consuming as shown in Figure 3.17. The average time of global optimization strategy for the levels G 2 ; G 1 ; G 0 grows nonlinearly and corresponds to 3.68%, 14.2% and 58.53%, respectively. The greedy strategy takes less than 1% of the whole execution time, whereas the global optimization consumes nearly 76.4%. This analysis shows that combining the greedy strategy with the global optimization algorithm not only guarantees the perceptual quality of the inpainted image but also improves the computational performance of the whole process. Furthermore, the use of hierarchical representation also significantly reduces the execution time.

In order to evaluate the visual quality of each stage, two original images in Figure 3.18 are selected as input and the corresponding outputs of each stage in our algorithm are displayed immediately below. The lowest resolution G 3 (see Figure 3.18-b) is completed by a greedy strategy based on some characteristics of the human visual system in order to preserve the perceptual continuity of the structures. This feature is kept and refined for higher resolution in G 2 , G 1 , and G 0 using a global optimization strategy, namely graph-cut algorithm.

Global performance evaluation

To increase the reliability of our framework, we analyzed the global performance of the method and compare with other approaches. The performance is evaluated and compared with two groups of methods: methods of the second group and methods belonging to greedy and global optimization strategies. For the sake of fair comparison, all source codes of the compared methods have been written in C/C++ language and implemented on the same PC with an Intel Core i5 2.8GHz CPU and 4GB RAM.

Firstly, a number of approaches from the second group are chosen for evaluating the performance of our method as in Table 3.2 using four images of size 200 × 200 pixels, shown in Figure 3.15. The computation time obtained for the considered methods is given in Table 3.6 in seconds. Here, the bold values show the best performance respects to running time. for the unoptimized approach; and Pritch et al. [START_REF] Pritch | Shift-map image editing[END_REF] for global optimization strategy.

Figure 3.19 illustrates the results obtained with the proposed approach in comparison to the others. Figure 3.19-a gives images to be inpainted where inpainting areas cover respectively 12.6%, 5.83%, 7.74%, 10.73% and 14.87% of the whole image. As it can be seen from these results, the proposed method outperforms the other considered methods.

Indeed, our results look more natural and more coherent than those of other approaches.

Moreover, the values in Table 3.7 depicting the computational time in seconds for the selected methods show an outstanding performance of our approach in comparison with the others.

Conclusion

In this chapter, a novel framework of image completion is introduced using multi-resolution image representation. The multi-resolution patch ensures the texture and geometric structure with the fixed size patches instead of using different patches or dynamic size patches.

The chosen patches are more consistent and adaptive. A common problem to most exemplar-based methods is the effect of priority. In currently presented version, a windowbased priority which classifies patches in a more suitable way and leads to the pleasant results is introduced. In addition, patch selection step is improved by using a combination of color and gradient channel instead of using only color channels as other methods.

Although the current proposal results in acceptable outputs, it still has a low performance because of patch searching. An improvement for computational time performance in our framework is also introduced which combines a greedy strategy and a global opti- mization strategy, called hybrid approach. This approach is not guaranteed to give the global optimum, but the results are very good as can be seen in the examples and the computational time is acceptable for real applications.

Comparison with some new and old methods of the second group is carried out. A series of images including natural and real archaeological images was used for testing.

The experimental results show that our approach not only produces better quality output images but also implements much faster than current methods.

For future research, a perceptual patch similarity that is more stable and effective and a numerical estimation for quality of the restored color images will be investigated, and an extension of our framework to use multiple source images will be developed. In addition, a video completion is being studying.

What is inpainting quality?

Image inpainting has been become a very active field of research in many real world applications such as digital cinema, computational photography, archaeological image restoration and archival documents restoration [START_REF] Arias | A variational framework for exemplar-based image inpainting[END_REF]. A large amount of research has gone into the development of new inpainting algorithms. However, much less effort has been devoted to the development of objective image quality metrics dedicated to inpainting purpose.

Alternatively, image quality assessment (IQA) plays a prominent role for many applications, including video streaming monitoring, medical imaging and lossy compression control among others. IQA in its broad sense refers to the problem of evaluating the level of perceptual quality of an image. Many interesting methods for predicting the image quality have been proposed in the literature [START_REF] Wang | Modern image quality assessment[END_REF][START_REF] Daly | Digital images and human vision[END_REF][START_REF] Wang | Image quality assessment: from error visibility to structural similarity[END_REF][START_REF] Sheikh | Image information and visual quality[END_REF][START_REF] Shi | Structure and hue similarity for color image quality assessment[END_REF][START_REF] Bonnier | Evaluation of spatial gamut mapping algorithms[END_REF][START_REF] Chandler | Vsnr: A wavelet-based visual signal-to-noise ratio for natural images[END_REF]. In general, the subjective evaluation is still the most reliable solution, but it could not be used in real-time applications and are tedious and time consuming.

It is worth noticing that the objectives of IQA in the case of image inpainting problem are substantially different from the classical image quality evaluation problem. Indeed, in the case of inpainting problem, the intent is to evaluate the quality of the restored image. It is also worth understanding that inpainting could be considered as a special image restoration problem in its broad sense. In both problems, inpainting and classical image restoration, the existing IQA metrics could not be directly applied because of the specific needs. For example, in the case of image inpainting the recovered region is totally different from the original one.

The main objective of image inpainting aims at restoring the missing parts or replacing some parts of the image in a visually plausible way, i.e. make it difficult for Human Vision System (HVS) to detect that the image has been modified. Hence, the intent of Image Inpainting Quality Assessment (IIQA) metric is then to evaluate the visual quality of the inpainted regions in terms of spatial coherence with the other parts of the image and human attention.

Very often, the results of image inpainting are evaluated subjectively or by using some objective metrics not well adapted to the specificities of their criteria. However, the subjective evaluation experiments are time consuming, complex and unpredictable due to some uncontrolled human factors such as fatigue, visual discomfort, knowledge, etc. This chapter will discuss methods, listed in Table 4.1, that have been extensively used for the evaluation of inpainting quality, as well as more recently proposed methods having the same goal. An overview of general image quality metrics that could be applied for inpainting quality evaluation is given in more details in the next section.

Overview of image quality assessment

As mentioned earlier, objective metrics for image quality assessment provide a replacement for the resource-intensive perceptual experiments. It was proven that in the field of inpainting, the focus of research has not been put on the development of objective metrics, but on the development and improvement of inpainting methods. Thus, in the remainder of this section a number of objective metrics that have been more extensively used for general image quality evaluation will be discussed. These metrics will be further applied in some situations of inpainting in order to determine whether they can provide similar, or better results than inpainting-specific objective metrics.

MSE and PSNR

Perhaps the simplest and oldest objective image quality measure is the Mean Square Error (MSE) and its extension, the Peak Signal to Noise Ratio (PSNR). Unfortunately, they have been still widely used due to the fact that they are easy to implement thus convenient to use for optimization purposes [START_REF] Wang | Modern image quality assessment[END_REF].

Assume that x = {x i |i = 1, 2, ..., n} is an "original image" which has perfect quality, and that y = {y i |i = 1, 2, ..., n} is a "distorted image" whose quality is being evaluated.

Where n is the number of image samples (pixels) and x i and y i are the intensities of the i-th samples in images x and y, respectively. Note that this indexing arrangement does not account for the spatial positions of, or relationships between pixels, but rather, orders them as a one-dimensional (1-D) vector.

Since the MSE can be defined exactly using this 1-D representation, it is apparent that the MSE does not make use of any positional information in the image, which might be valuable in measuring image quality. Therefore, the MSE is defined as equation (4.1).

M SE = 1 n n i=1 (x i -y i ) 2 (4.1)
The PSNR computes the peak signal to noise ratio between two images and gives a value in decibels as a result. The higher the value obtained for PSNR, the better the quality of the reproduction. First step in computing the PSNR is to obtain the MSE value for the two images. Then, the PSNR is calculated as:

P SN R = 10log 10 L 2 M SE (4.2)
In equation (4.2), the parameter L is the dynamic range of allowable image pixel intensities. For images that have allocation of 8bits/pixel of gray-level, L = 255. Alternately, the MSE and PSNR were computed for color images by converting the images to the YCbCr or HSL color space, which separates the intensity (luma) channel from the color channels.

This choice was made because the human eye is more sensitive to intensity information.

Taken this into consideration, the MSE and PSNR are calculated on the Y or H channel [START_REF] Wang | Modern image quality assessment[END_REF].

VDP

A visible difference predictor (VDP) is an algorithm for the assessment of image fidelity which was proposed by Scott Daly in [START_REF] Daly | Digital images and human vision[END_REF], and which aims at quantifying the visual fidelity of distorted images. The VDP model interprets early vision behaviour, from retinal contrast sensitivity to spatial masking and pooling for decision stage. A use of the VDP consists of three main stages such as components for calibration of the input image, a human visual system (HVS) model, and a method for displaying the HVS predictions of the visible differences. The key element of the VDP is the human visual system model shown in Figure 4.2. It concentrates on the lower-order processing of the visual system such as the optics, retina, lateral geniculate nucleus, and striate cortex. The HVS model consists of a number of processes that limit visual sensitivity. Three main sensitivity variations are accounted for, namely, as a function of light level, spatial frequency, and signal content. Sensitivity, S, is defined as the inverse of the contrast required to produce a threshold response:

S = 1 C T (4.3)
where C T is generally referred to as simply the minimum contrast value for which the stimuli starts to be visible. The contrast is defined by:

C = L max -L mean L mean (4.4)
where L max and L mean refer to the maximum and mean luminance of the waveform. The variations in sensitivity as a function of light level are simulated by amplitude nonlinearity.

Each input luminance L ij is transformed by a simplified version of the retinal response to an "amplitude nonlinearity" value R ij defined as:

R ij = L ij L ij + (c 1 L ij ) b (4.5)
where the constants c 1 = 12.6 and b = 0.63 apply when luminance is expressed in cd/m 2 . For this model, the adaptation level for an image pixel is solely determined from that pixel.

The variation as a function of spatial frequency is modeled by the contrast sensitivity The VDP is a relative metric because it does not describe an absolute metric of image quality but instead address the problem of describing the visibility of differences between two images. As a result of the approach taken, the VDP can be used for all types of image distortions including blur, noise, banding, blocking, etc.; but the reference image is required.

SSIM and SSIM IPT

The SSIM shorting for Structural SIMilarity metric was introduced by Wang et al. [START_REF] Wang | Image quality assessment: from error visibility to structural similarity[END_REF] to overcome the limitation of traditional metrics such as M SE or P SM R while keeping the measure relatively simple in comparison with other fully HVS-based metrics. This is a full reference metric where the measuring of image quality based on an initial uncompressed or distortion-free image as reference. The SSIM is designed to improve on traditional methods like MSE and PSNR which have proven to be inconsistent with human eye perception.

The principal idea underlying the structural similarity approach is that the Human Visual System (HVS) is highly adapted to extract structural information from visual scenes, and therefore, a measurement of structural similarity (or distortion) should provide a good approximation to perceptual image quality [START_REF] Wang | Image quality assessment: from error visibility to structural similarity[END_REF]. The SSIM algorithm separates the task of image similarity measurement into three comparisons: luminance, contrast, and structure.

The overall SSIM metric for the whole image can be computed as the mean of local values using sliding window approach. In [START_REF] Wang | Modern image quality assessment[END_REF][START_REF] Wang | Image quality assessment: from error visibility to structural similarity[END_REF], an 11 × 11 circular-symmetric Gaussian window, w = {w i |i = 1, 2, ..., n}, with standard deviation of 1.5 samples, is used as a weighting function and normalized to unit sum ( n i=1 w i = 1). And the local comparison is then calculated within the local window.

First, the local luminance of each signal (from image patches taken from the same locations in x and y, respectively) is estimated by the mean intensity:

µ x = n i=1 w i x i (4.6)
The local luminance comparison function, l(x, y), is then constructed as a function of µ x and µ y :

l(x, y) = 2µ x µ y + C 1 µ 2 x + µ 2 y + C 1 (4.7)
where the constant C 1 is included to avoid instability for homogeneous or flat regions and set to C 1 = (K 1 L) 2 . L is the dynamic range of the pixel values (L = 255 for 8 bits/pixel gray level) and K 1 1 is a small positive constant.

Second, the local standard deviation (the square root of variance) is used as an estimate of the signal contrast. An unbiased estimate in discrete form is given by:

σ x = n i=1 w i (x i -µ x ) 2 1 2 (4.8)
The local contrast comparison, c(x, y), is then designed as a function of σ x and σ y :

c(x, y) = 2σ x σ y + C 2 σ 2 x + σ 2 y + C 2 (4.9)
where C 2 = (K 2 L) 2 and K 2 1 are constants to prevent the possible division by zero.

Third, the signal is normalized by its own mean and standard deviation. The structure comparison s(x, y) is then conducted on the resulting normalized signals. Notice that the correlation between (x -µ x )/σ x and (y -µ y )/σ y is equivalent to the correlation coefficient between x and y. Thus, we define the structure comparison function as follows:

s(x, y) = 2σ xy + C 3 σ x + σ y + C 3 (4.10)
In a discrete implementation, σ xy can be estimated as:

σ xy = n i=1 w i (x i -µ x )(y i -µ y ) (4.11)
Finally, three comparisons of equations (4.7), (4.9), (4.10) are combined into the overall SSIM Index between x and y:

S(x, y) = [l(x, y)] α [c(x, y)] β [s(x, y)] γ (4.12)
where α, β, γ are positive parameters that adjust the relative importance of the three components. To simplify the expression and reduce the number of parameters, we set

α = β = γ = 1 and C 3 = C 2 /2.
This results in a specific form of the SSIM index as in [START_REF] Wang | Image quality assessment: from error visibility to structural similarity[END_REF]:

S(x, y) = (2µ x µ y + C 1 )(2σ xy + C 2 ) (µ 2 x + µ 2 y + C 1 )(σ 2 x + σ 2 y + C 2 ) (4.13)
By applying such a sliding window approach across the image, an SSIM Index map is obtained. Finally, the SSIM Index map is combined into a single measurement that encapsulates the overall quality of the image:

M SSIM (X, Y ) = 1 m m j=1 SSIM (x j , y j ) (4.14)
where X and Y are the reference and the distorted images, respectively; x j and y j are the image contents at the j-th local window; and m is the number of local windows of the image. A system diagram of the proposed quality assessment system is shown in Figure 4.3. Signals x and y denote local windows for which the similarity measure is computed.

The SSIM IP T metric was introduced by Bonnier et al. in [START_REF] Bonnier | Evaluation of spatial gamut mapping algorithms[END_REF] and represents the color version of the Structural Similarity Index (SSIM). According to Bonnier et al., the SSIM index works with luminance only. Thus, it is adapted to color images by applying the SSIM index on each channel of the image in color space IPT [START_REF] Ebner | Development and testing of a color space (ipt) with improved hue uniformity[END_REF] as follows: Mutual information between C and E quantifies the information that the brain could ideally exact from the reference signal, whereas the mutual information between C and F quantifies the corresponding information that could be extracted from the distorted signal.

It is known that when images are filtered using oriented band-pass filters (eg. a wavelet transform), the distribution of resulting (marginal) coefficients are highly peaked around zeros and possess heavy tails. Such statistical descriptions of natural scenes are labeled as NSS and it has been an active area of research. The VIF scheme utilizes the Gaussian scale mixture (GSM) model for wavelet NSS [START_REF] Sheikh | A statistical evaluation of recent full reference image quality assessment algorithms[END_REF]. First, it performs a scale-space-orientation wavelet decomposition using steerable pyramid [START_REF] Simoncelli | Shiftable multiscale transforms[END_REF] and models each sub-band in the source as:

C = S.U (4.16)
where S is a random field of scalars and U is a Gaussian vector random field. The GSM

D = GC + V (4.17)
where G is a deterministic scalar gain field and V is a stationary additive Gaussian noise random field. This model captures important, and complementary, distortion types: blur, additive noise, and global or local contrast changes.

The VIF then assumes that the distorted and source images pass through the human visual system and the HVS uncertainty is modeled as visual noise: N and N for the source and distorted image respectively; where N and N are zero-mean uncorrelated multivariate Gaussians with the same dimensionality:

E = C + N (reference image) (4.18) F = D + N (test image) (4.19)
where E and F denote the visual signal at the output of the HVS model from the reference and the test images in one sub-band, respectively from which the brain extracts cognitive information (see Figure 4.3). With the source, distortion, and HVS models as described above, the VIF criterion is then evaluated as follows:

V IF = j∈allsubband I(C j ; F j |s j ) j∈allsubband I(C j ; E j |s j ) (4.20)
where I(X; Y |Z) is the conditional mutual information between X and Y , conditioned on Z; s j is a realization of S j for a particular image and the index j runs through all the sub bands in the decomposed image.

Moreover, the VIF is extended to video quality assessment [START_REF] Sheikh | A visual information fidelity approach to video quality assessment[END_REF]. The authors justified the use of VIF for video by first motivating the GSM model for the spatio-temporal natural scene statistics. The model for video VIF is then essentially the same as that for VIF with the exception being the application of the model to the spatio-temporal domain as opposed to the spatial domain.

VSNR

The VSNR denotes a wavelet-based Visual Signal-to-Noise Ratio [START_REF] Chandler | Vsnr: A wavelet-based visual signal-to-noise ratio for natural images[END_REF]. The VSNR aims to evaluate the effect of supra-threshold distortion by using parameters for the HVS model derived from experiments where the stimulus was an actual image as against sinusoidal gratings or Gabor patches. The metric takes into consideration low level as well as midlevel features of the HVS. The low level properties such as contrast sensitivity and visual masking are employed in the wavelet domain and compared to the detection threshold.

The VSNR first computes a difference image from the reference and distorted images.

This difference image is then subjected to a discrete wavelet transform. Within each subband, the VSNR then computes the visibility of distortions, by comparing the contrast of the distortion to the detection threshold and then computes the root-mean-squared (RMS) contrast of the error signal (d pc ):

d pc = 1 µ L(I) 1 N N i=1 [L(E i + µ I ) -µ L(E+µ I ) ] 2
d gp = M m=1 [C * (E fm ) -C(E fm )] 2 1 2 (4.22)
where C(E fm ) denotes the actual contrast of the distortions within the band centered at f m and C * (E fm ) is global-precedence preserving contrast. For more detailed specifications of these equations, the reader can be referred to [START_REF] Chandler | Vsnr: A wavelet-based visual signal-to-noise ratio for natural images[END_REF].

According to the above, the final VSNR metric, in decibels, corresponding to two images is given by a combination of perceived contrast of the distortions d pc and discontinuity of global precedence, d gp as following:

V SN R = 10log 10 C 2 (I) αd pc + (1 -α) dgp √ 2 (4.23)
where C(I) = σ L(I) /µ L(I) denotes the root mean square contrast of the original I; and parameter α ∈ [0, 1] determines the relative contribution of each distance.

Overview of inpainting quality assessment

Early inpainting algorithms have been specifically designed for filling in small missing or damaged regions in digital images and later in vintage films. Their main objective was, at that time, to reconstruct the image such that the result would appear to be as close to the original (undamaged) image as possible. Consequently, many researchers evaluated the quality of the images inpainted with their newly proposed method by employing simple objective metrics, such as MSE, PSNR, etc. or more complex metrics such as SSIM, VIF, VSNR, etc. [START_REF] Mahalingam | Digital inpainting algorithms and evaluation[END_REF].

As the domain of digital image inpainting spread, to include applications that require a larger area to be inpainted, the objective of the inpainting process also changed, from trying to achieve high fidelity with the original, not degraded, image, to making the inpainted area as visually pleasing as possible. In other words, the modifications brought to the original image through inpainting should not be discernible by human observers. Given this new objective of inpainting, it becomes obvious that evaluation methods previously used (i.e.

MSE, PSNR, SSIM) could no longer provide a good assessment of the inpainting quality.

Thus, new inpainting evaluation methods that would take into account the subjective nature of the human visual system were required.

At present, a few interesting works on objective IIQA have been published recently [START_REF] Wang | An evaluation index based on parameter weight for image inpainting quality[END_REF][START_REF] Ardis | Visual salience metric for image inpainting[END_REF][START_REF] Mahalingam | Digital inpainting algorithms and evaluation[END_REF][START_REF] Oncu | Evaluation of digital inpainting quality in the context of artwork restoration[END_REF]. These metrics will be described briefly in the next sub-section and applied to inpainted images in comparison with our proposal in order to evaluate the performance of image inpainting quality.

PWIIQ

Authors of [START_REF] Wang | An evaluation index based on parameter weight for image inpainting quality[END_REF] proposed a full-reference assessment for image inpainting quality based on parameter weight. This work was inspired from three observations:

1. Blur produced during inpainting.

2. Non-continuity of edge/margin structure.

3. Mottle appears in the monotone texture color region.

Taking into consideration these factors, a special definition of image evaluation index inspired from the SSIM metric [START_REF] Wang | Image quality assessment: from error visibility to structural similarity[END_REF], Q, on inpainting result is given by:

Q = [L(x, y)] α [C(x, y)] β [G(x, y)] γ (4.24)
where L, C, G stand for variance of image luminance, definition and gradient similarity; and α, β, γ are positive constants to adjust the important degree of each term. This metric has the same form as SSIM index but it is modified to apply for inpainting quality.

First, the luminance function, L(x, y), is derived from [START_REF] Wang | Image quality assessment: from error visibility to structural similarity[END_REF] and defined as follows:

L(x, y) = M j=1 l(x j , y j ) M (4.25)
where M is the number of patches in the original image; and l(x, y) is the local luminance comparison which is defined by equation (4.7).

Second, the definition function, C(x, y), is computed by estimating high-frequency parameter in the FFT result of the two images:

C(x, y) = m-1 i=0 n-1 j=0 |F F T y (i, j)| -|F F T y (0, 0)| m-1 i=0 n-1 j=0 |F F T x (i, j)| -|F F T x (0, 0)| (4.26)
where F F T (i, j) stands for all frequency parameter of the original image, and F F T (0, 0)

is the average gray value of image, that is the DC component, so the gap of the two is the high-frequency parameter of image. The larger the gap is, the more the high-frequency parameters are. This means that the corresponding image is clearer. Compare the highfrequency parameters of being tested image with original one, if the two are nearer, and then the being tested image is clearer and the image quality is better.

Third, the gradient similarity, G(x, y), is regarded as the similarity between the main structure information in two images and calculated by equation (4.27):

G(x, y) = 2 m-1 i=0 n-1 j=0 G x (i, j)G y (i, j) + C 2 m-1 i=0 n-1 j=0 [G x (i, j)] 2 + m-1 i=0 n-1 j=0 [G y (i, j)] 2 + C 2 (4.27)
where G x (i, j) and G y (i, j) are respectively the gradient range of x and y of the original image at the coordinates (i, j). C 2 is a positive number close to zero, which is brought in to avoid the case that denominator equates zero.

This metric is designed based on parameter weight through analyzing the reason for subjective distortion feeling after image inpainting. In practical applications of image inpainting algorithms, mostly there is no standard image as a reference, so how to deal with inpainting evaluation about non-reference image will be still a big challenge. Figure 4.6 shows some values of PWIIQ index in some cases of inpainting.

ASVS and DN

Two types of observable artifacting in an inpainted image, referred to as in-region and out-region, are defined in [START_REF] Ardis | Visual salience metric for image inpainting[END_REF]. These types of artifacts are evaluated by the variation and 2 center-surround channels (3,4). An example of saliency map is shown in Figure 4.7.

The lighter region shows more attention.

The first metric, ASVS, is a no-reference measure and it determines if inpainted pixels are relatively noticeable as compared to the remainder of the scene: ASVS metric takes into account only the inpainted area. Thus, this metric considers for in-region artifacting which occurs when the pixels in the inpainted region draw more attention than they are suppose to. As noted in [START_REF] Ardis | Visual salience metric for image inpainting[END_REF] the in-region artifacting is related to distinct coloration or structure, created after inpainting, that cannot be observed anywhere else in the image. Consequently, this newly introduced color or structure will result in high saliency values, and thus higher ASVS score. where S (p) is the saliency map corresponding to the inpainted image corresponding to pixel p. In order to be able to compare the values provided by these metrics on an equal footing with reference to the unmodified image, the gaze density is normalized as the following equations: In the original work, the saliency maps were obtained from the eye-tracking experiments [START_REF] Venkatesh | Eye tracking based perceptual image inpainting quality analysis[END_REF] based on the gaze density and the gaze pattern is recorded by the faceLAB eye tracker.

ASV S = Ω [S (p)] 2 |Ω| (4.
GD in = GD in GD unmod
Unfortunately, this way has the same disadvantages as the subjective evaluation methods.

However, since inpainting evaluation methods that are fully automatic are preferred to those that imply the participation of human observers. Thus, for the sake of similarity, in our experiment, the saliency maps were calculated with the SaliencyToolbox in iNVT toolkit [START_REF] Oncu | Evaluation of digital inpainting quality in the context of artwork restoration[END_REF]. This toolbox is more compact, easier to understand and experiment with.

BorSal and StructBorSal

The metrics introduced in previous section concentrated on considering the variation of saliency regions inside and outside the gap, respectively. A. I. Oncu et al in [START_REF] Oncu | Evaluation of digital inpainting quality in the context of artwork restoration[END_REF] showed that the saliency map values corresponding to a border region around the hole should be able to accurately capture the saliency change of attention flow, without the need of examining the saliency map of the whole image. The novelty here consists of considering only one border region around the gap that contains information from both the inpainting domain and its complementary area. Consequently, one full-reference metric, denoted by Border Saliency (BorSal), has been proposed and computed as a normalized gaze density measure, similar to the GD in and GD out metrics in [START_REF] Venkatesh | Eye tracking based perceptual image inpainting quality analysis[END_REF]:

BorSal = p∈Border S (p) p∈Border S(p) (4.33)
where S and S are the saliency maps of the inpainted and reference image, respectively and p is a pixel in the region corresponding to the Border region. In order to take into account information of both inside and outside the gap, the Border region is extended three pixels inside and outside. In other words, the size of the border region was chosen to be equal to six pixels and was obtained by applying morphological operations (i.e. erosion, dilation) to the inpainting domain.

Using the already defined BorSal metric, a second inpainting quality measure is proposed, by combining the BorSal metric with the SSIM IP T measure introduced by [START_REF] Bonnier | Evaluation of spatial gamut mapping algorithms[END_REF].

The later takes into account structural information in the whole image and thus can in-dicate the presence of artifacting due to poor structure reconstruction, while the BorSal metric accounts for changes in the flow of attention, post inpainting. The new metric will be denoted by StructBorSal and its value calculated for the entire image by adding up the value obtained according to equation (4.34) to evaluate color images:

StructBorSal = BorSal + SSIM IP T (4.34)

Visual coherence metric for inpainting quality

In some cases, the traditional IQA metrics can be extended and applied for inpainting.

However, these metrics are suitable only in case of thin or small damaged regions. Furthermore, they are full-reference metrics. It means that it is impractical to apply for inpainting, especially, in case of large inpainting region where the original image (reference image) might not be available or the inpainted region is total different from the original one.

For the mentioned IIQA, most of these metrics are based on the HVS features directly, the saliency map. However, they do ignore an important constraint of inpainting problem related to type of artifacts that have a great influence on the quality prediction.

Namely, they do not take into consideration the global visual appearance of the image that significantly affects the restoration quality.

Through the analysis of image inpainting results, we found that two main aspects need to be considered in image inpainting quality assessment. First, the completion is blindly performed without any cue from the original content of images, that is, the restored regions depend on only the rest of the image. Therefore, the new generated pixels should be consistent with the existing ones. This refers to perceptual coherence of inpainted regions that determines the new undesired visual artifacts. Second, the structures or contours often attract more the human gaze than other parts; hence more weight should be associated to these salient features.

In this thesis, a saliency map, representing an approximation of the human attention, is used as the weighting map for the evaluation. As a result, an efficient quality index for IIQA taking into account the mentioned factors is proposed. It is shown that it is possible to predict reasonably the inpainting image quality in many cases.

In the following, some notations used in previous chapters are recalled for completeness.

The whole image domain, I, is composed of two disjoint regions: the inpainting region, Ω, and the known region, Φ (Φ = I -Ω). The basic unit of synthesis at pixel p is a patch, Ψ p , centered at pixel p. The inpainted image quality index, Q, is defined through equation (4.35).

Q = Ω C(p) α S(p) β |Ω| (4.35)
where C(p), S(p) represent respectively the coherence and structure terms. The two positive parameters α and β are used to adjust the important degree of each part. In our implementation, we set α = β = 1 for simplicity and reduce the number of parameters. The impact of these parameters will be further discussed in next stage. Figure 4.8 demonstrates a scheme in order to calculate the proposed index.

The coherence term

An inpainted region, Ω, has a global visual coherence with the rest of the image, Φ, if every new generated pixel is consistent with existing ones in terms of a structural measure. On the other hand, a local patch, Ψ p , should be similar to the one within Φ. The coherence term for each pixel p(x, y) (p ∈ Ω) is then defined as follows:

C(p) = max{SIM (Ψ p , Ψ q ), ∀Ψ q ∈ Φ} (4.36)
where Ψ p and Ψ q denote small patches around p and q, respectively. SIM is an objective function to evaluate the similarity between two patches that measures a appropriateness degree of an inpainted pixel (p) based on existing pixels (Ψ q ) and its neighbors in Ψ p .

A good objective function needs to agree perceptually with a human observer. The M SE or P SN R are used widely for patch similarity but they are insufficient to provide the desired results. The main reason for this is that they do not take into account the human visual features.

In [START_REF] Wang | Image quality assessment: from error visibility to structural similarity[END_REF], a new similarity function based on the structural information of patches was proposed. The structural similarity is defined as follows [START_REF] Dang | Inpainted image quality assessment[END_REF]: where µ p , σ p and µ q , σ q denote the mean intensity and standard deviation set of patches Ψ p and Ψ q , respectively, while σ pq denotes their cross correlation. C 1 and C 2 are small positive constant values to avoid instability problem when the denominator is close to zero.

SIM (Ψ p , Ψ q ) = (2µ p µ q + C 1 )(2σ pq + C 2 ) (µ 2 p + µ 2 q + C 1 )(σ 2 p + σ 2 q + C 2 ) (4.37)
This definition is very easy to understand and takes into account the HVS features but it works with luminance only, while most of image in our context includes color information. Although, human eyes are more sensitive to structure than color of an image, color information also could influence human beings judgments and it is important for HVS in quality evaluating. From this observation, we exploit the idea developed in [START_REF] Shi | Structure and hue similarity for color image quality assessment[END_REF] where a similarity combining structure and color information is introduced in order to compute the coherence between patches. The detail of similarity function is then defined as follows [START_REF] Dang | Perceptual quality assessment for color image inpainting[END_REF]:

SIM (Ψ p , Ψ q ) = (1 -θ)SS(Ψ p , Ψ q ) + θHS(Ψ p , Ψ q ) (4.38)
where θ is a positive constant within the range [0, 1] defining the relative importance between structure similarity (SS) and hue similarity (HS), corresponding to color information. The structure and hue similarity indexes are defined by equations (4.39) and (4.40), respectively:

SS(Ψ p , Ψ q ) = (σ pq + C 1 ) (σ p + σ q + C 1 ) (4.39) HS(Ψ p , Ψ q ) = (2λ p λ q + C 2 ) (λ 2 p + λ 2 q + C 2 ) (4.40)
where (λ p , σ p ) and (λ q , σ q ) denote the mean hue and standard deviation set of patches Ψ p and Ψ q , respectively. C 1 and C 2 are small positive constant values to avoid computation instability in very dark or homogeneous regions.

Figure 4.9 illustrates the spatial coherence notion used in the design of the IIQA. Note that the output shown in Figure 4.9-c is more spatially coherent to that of Figure 4.9b. Indeed, some pixels in inpainted regions (the red patches) do not look coherent with the original patterns. In other terms, there are no similar patches in the source region.

The blue dashed patch representing a restored pixel is more reasonable than the red ones because it is similar to a blue solid patch in the known region.

The structure term

The second term affecting image inpainting quality is the structure factor. Given an image, human observer would pay more attention to perceptually relevant regions, which usually correspond to contours and details, but less attention to the rest of the image. Thus, the contours and other relevant structures in the inpainted regions attract more human gaze than the other components. For that reason, we may identify the structure term using the information provided by a saliency map as follows:

S(p) = SL(p) max I {SL} ∀p ∈ Ω (4.41)
where SL is the saliency map of the inpainted image. Several computational models have been proposed to simulate human's visual attention [START_REF] Itti | A model of saliency-based visual attention for rapid scene analysis[END_REF][START_REF] Hou | Saliency detection: A spectral residual approach[END_REF][START_REF] Guo | Spatio-temporal saliency detection using phase spectrum of quaternion fourier transform[END_REF]. However, the high computational cost and variable parameters are still the weaknesses of these models. Authors of [START_REF] Achanta | Frequency-tuned salient region detection[END_REF] proposed a simple and efficient method based on the idea that objects attracting the gaze of an observer should have characteristics that go beyond the average behavior of the image. A simple formulation of the aforementioned saliency map, SM , can be expressed by equation (4.42):

SL = ||I µ -I G || (4.

Psychophysical experiment for subjective quality assessment

Quality assessment dedicated to inpainting is rather a new field and the result of such a technique is often subject to critical evaluation from the end-user including the global homogeneity of the content and the coherence of added/suppressed regions. Therefore, the performance of a given metric, whatever its scheme is, should be assessed with regards to human judgment. However, to the best of our knowledge, there is no exhaustive inpainting database gathering state of-the-art methods and their associated subjective scores for a significant set of images. Based on this observation and for the sake of proposing an objective metric for the evaluation of digital image completion quality, a psychophysical experiment was performed as part of the work for this thesis and with the goal of subjective quality assessment of the inpainting results. Moreover, the subjective evaluation is of great significance for the current work, as the data thus obtained will be used further on for validating objective methods of quality assessment. The latter provide the means to ensure the correlation of the metrics with perceived quality. This section will discuss the experimental setup and the obtained psychophysical results.

Test setup

The experiment was setup in an uncontrolled environment, as a web-based experiment because of some reasons as follows:

• It is easy to acquire a large number of participants for achieving high statistical power making it thus possible to draw meaningful conclusions from the experiment.

• It is feasible to carry out the experiment around the clock and reach different categories of participants such as experts in image quality, professional restorers, naive observers, etc.

• The difference between results obtained from controlled and uncontrolled experiments is negligible. Thus, the scores recording in this experiment are reliable.

For image database, a set of ten input images were encoded into PNG format in two cases: small and large inpainted regions. In the former case, three images and five different inpainting algorithms are used. For the latter case, seven images are divided into two subcategories: greedy strategy or global optimization strategy. Figure 4.11 shows a snapshot of the used images. The damaged regions are marked by green or red color. The detailed specification of these images is given in Table 4.2. As mentioned in Chapter 1, the hole size is not able to used as the criterion for classifying the damaged regions. In this thesis, all damaged images were classified by the definition (equation 2.1). To try and cover all inpainting methods would be infeasible. Thus, this thesis looks at only a selection of algorithms that take different approaches in their shared goal of filling in missing parts of an image. In case of small inpainted regions, five inpainting algorithms have experiment the observers were informed and trained on the system on a set of test images, as follows:

• One image that corresponds to the original state of a damaged painting, with visible artifacts.

• A series of result images corresponding to the restored versions of the same image after repairing the artifacts. The top-left image shows the degraded image and the remaining images are the restored versions. The instructions also stated that this positioning between the original and restored images will be kept as such, throughout the entire experiment. In order to score for the test images, participants were asked to select a score in the combo box below each restored image. Scores were given on discrete scale ranging from 1 -Unacceptable to 5 -Perfect in the combo box and are described as in Table 4.4 Observers were allowed to change their vote within a same series of images until validation. This has been done to account for the unavailability of a real original image and availability of different versions of results. The inpainted images were randomly presented and shown without including the name of inpainting methods to avoid any bias or influence.

Evaluation methodology

The experimental method for the subjective quality assessment was chosen to be the Mean Opinion Score (MOS) [START_REF] Arajo | Methods for objective and subjective assessment of quality[END_REF]. This method was initially designed for audio quality evaluation, but it has been widely used for image quality evaluation. Historically, and implied by the word Opinion in its name, MOS was a subjective measurement whose values are scored from observers as they perceived it. Participants were presented with a group of inpainted images at a time. Given inpainted images, the participants were asked to judge the overall IQ of the inpainted image using the ITU-R five point quality scale, labelled with the adjectives [START_REF] Arajo | Methods for objective and subjective assessment of quality[END_REF] as previous section. In order to be able to analyse the subjective data obtained, each of the five adjectives in the descriptive quality scale had an equivalent numerical value. Accordingly, Unacceptable corresponded to a 1 score and Perfect to a 5 score. Once the score values are obtained from observers, the MOS associated Confidence Interval (CI) is then computed thanks to the following equation giving the average opinion of the observers regarding the submitted question.

u jk = i u i,j,k S.N (4.43)
where u jk is the mean score of the observer i for the inpainting method j and image k; N represents the number of observer; S is the dynamic range of the scores (S = 5) in order to normalize the MOS value in range [0, 1].

In order to evaluate as well as possible the reliability of the results, a confidence interval is associated to the MOS. It is commonly adopted that the 95% confidence interval is enough. This interval is designed as:

[u jk -δ jk , u jk + δ jk ] (4.44)
where

δ jkr = 1.95 σ jk √ N (4.45)
The standard deviation, σ jk , is defined as:

σ jk = N i=1 (u jk -u ijk ) 2 N -1 (4.46)
The second part of this study refers to the evaluation of objective quality assessment methods. For this set of test images, the scores given by quality metrics are calculated for each image, and compared with the subjective scores given by observers to the same image.

Consequently, the performance of the metrics is quantified by the correlation between these two scores. Correlation analysis shows the degree by which the objective values can be predicted, or be explained, by the subjective values. Higher correlation values indicate higher performance of the metrics.

There have been several tools on the correlation analysis in literature. In our research, two standard correlation measures as in the framework of the VQEG group [START_REF] Vqeg | Final report from the video quality experts group on the validation of objective models of video quality assessment[END_REF] have been used: Pearson's correlation coefficient (PCC) and Spearman rank order correlation (SCC).

1. Pearson's correlation coefficient [START_REF] Huck | Reading statistics and research[END_REF]: Pearsons correlation coefficient is used for data on the interval or ratio scales, and is based on the concept of covariance. The productmoment statistic is given by:

P CC = n i (X i -X)(Y i -Y ) n i (X i -X) 2 n i (Y i -Y ) 2 (4.47)
where P CC ∈ [-1, 1], n denote the number of samples in X and Y which are variables associated with subjective and objective results, respectively.

2. Spearman rank order correlation [START_REF] Huck | Reading statistics and research[END_REF]: The Spearman rank correlation coefficient (or Spearman's rho), is used with ordinal data and is based on ranked scores. The SCC is the nonparametric analog to PCC is defined as the PCC between the ranked variables. Accordingly, the process for Spearman's correlation first requires ranking the X and Y scores. The analysis is then performed on the ranks of the scores, and not the scores themselves. The paired ranks are then subtracted to get the differences,

d i = X i -Y i
, which are then squared to eliminate the minus sign. If there is a strong relationship between X and Y then paired values should have similar ranks. The test statistic is given by:

SCC = 1 - 6 n i d 2 i n(n 2 -1) (4.48)
Following the methodology above, the performance of the considered metrics is evaluated over the entire image database.

Psychophysical results

A total of forty-five observers participated in the psychophysical experiment for inpainting quality rating. Before proceeding with the interpretation of the obtained results and data analysis, in ITU-R 500-10 standard [START_REF] Bt | Methodology for the subjective assessment of the quality of television pictures[END_REF] a procedure for screening the observers is recommended. The results analysis is able to eliminate from the final calculation either a particular score or an observer. This rejection allows to correct influences induced by the observer's behavior, or bad choice of test images. The most obstructing effect is incoherence of the answers provided by an observer, which characterizes the non-reproductibility of a measurement. These average values are function of two variables: the presentations and the observers. Then, we check if this distribution is normal by using the β 2 test, where β 2 is the kurtosis coefficient, i.e. the ratio between the fourth-order moment and the square of the second-order moment, is given by: From the Figure 4.14, it is clearly possible to conclude about the visual performance of restored results. The MOSs obtained from this study are of a high importance since it will allow to study the performance of the proposed inpainting quality metric thanks to the evaluation of the precision and accuracy of the predicted scores with regards to human judgement.

Experimental results and discussion

Following the methodology presented in previous section, the performance of a set of quality metrics will be considered in this section. The set includes seven general image quality metrics in section 4.2 and seven inpainting quality metrics in section 4.3 and our proposed metrics in section 4.4.

Based on raw perceptual data, the Mean Opinion Score (MOS) is calculated for each image in the database. For each image and each metric, an objective score will be calculated, describing the quality of the reproduction. Then, the Pearson product-moment (PCC) [START_REF] Huck | Reading statistics and research[END_REF] coefficient and Spearman's rank correlation coefficient (SCC) [START_REF] Huck | Reading statistics and research[END_REF] between MOS and the objective scores are calculated in order to evaluate the performance of the metrics considered.

In order to achieve a fair evaluation of the metrics, the investigation of their performance was carried out in two cases: small inpainted regions and large inpainted regions.

Case 1: Small inpainted regions

Early inpainting algorithms have been tried to simulate the work of the restoration in the museums. Thus, the main function of the inpainting algorithms is to restore the small or thin damaged regions and to make the input image as close to the original image as possible.

Many publications have been introduced in this context. In this thesis, three images have been used (see Table 4.2) and restored by five approaches described in [START_REF] Bertalmío | Image inpainting[END_REF], [START_REF] Tschumperlé | Fast anisotropic smoothing of multi-valued images using curvaturepreserving PDE's[END_REF], [START_REF] Bugeau | Combining texture synthesis and diffusion for image inpainting[END_REF], [17] and [61]. Fifteen results were then obtained and used to evaluate the objective metrics.

In an attempt to compare with full-reference image quality metrics and existing inpainting quality metrics, the selected images are used as the ground-truth and the small or thin artifacts are added as the pseudo-inpainted regions for restoring. With the original goal of inpainting algorithms to bring the original degraded image to a state that is as close as possible to the state of the final restored image, the inpainting results will be compared with the reference image and evaluated using the metrics in previous sections. Figure 4.15 illustrates one of the obtained results using these algorithms and the pseudo-inpainted regions marking with green color occupy 4.52% of the total image.

Seven image quality metrics and five inpainting quality metrics have been applied and calculated in order to compare with our proposals. The corresponding PCC metrics and SCC metrics are calculated and presented in Table 4.5 and illustrated by Figure 4.16.

Where Q 1 and Q 2 are two proposed metrics for gray and color level versions, respectively.

The first metric Q 1 uses the coherence term with similarity measurement in equation (4.37), while the second metric Q 2 applies the similarity measurement in equation (4.38).

From these metrics, it could be found that in some cases, the P CC and SCC values of P W IIQ metrics, for example, are higher than the proposed metrics. This is caused by the fact that in these case, the P W IIQ metrics is a full-reference metric which could use both distorted and reference images for evaluation. Moreover, the interpolation-based inpainting methods sometimes work better than exemplar-based inpainting methods in case of small or thin degraded area. Whereas, our metrics are no-reference metrics which cannot work well without valid patches.

However, the obtained results indicate that most of the considered metrics have low P CC as well as low SCC. Thus, it can be concluded that, for the considered image database, they can not accurately predict perceived image quality. It could be noticed that ASV S, DN , GD in and GD out metrics determine the presence of inpainting artifacts, that is, they intend to produce lower values for better results. As we can see, our indexes is the most consistent with M OS values and produces the highest mean value for both P CC and SCC measures.

Case 2: Large inpainted regions

The main challenging case of inpainting quality assessment is the one corresponding to large inpainted regions. Because many published methods achieve impressive results in recovering the large damaged regions, there is no successful metric in order to evaluate the obtained results. Thus, it is really meaningful and valuable if it can assess quality of a large restored region. This section will investigate the performance of selected metrics in the case of large inpainted regions. As mentioned in previous sections, we can divide the inpainting methods in this case into two sub-groups such as greedy strategies and global optimization strategies. In our experiments, we selected the methods in [17], [START_REF] Zhang | Exemplar-based image inpainting using color distribution analysis[END_REF], [START_REF] Wu | Object removal by cross isophotes exemplar-based inpainting[END_REF], [61] and [START_REF] Dang | A hierarchical approach for highquality and fast image completion[END_REF] for greedy strategies and [START_REF] Wexler | Space-time completion of video[END_REF], [24] and [START_REF] Pritch | Shift-map image editing[END_REF] for global optimization strategies.

For test images, four images are used as inputs in case of greedy strategy and three images are selected as inputs in the other case (see Table 4.2). Figures 4.17 case. In the original work, the saliency maps used to calculate for the two metrics GD in and GD out were recorded using the Seeing Machines faceLAB eye tracker. However, since inpainting evaluation methods that are fully automatic are preferred to those that imply the participation of human observers. Thus, for the sake of similarity, in our experiment, the saliency maps were computed with the SaliencyToolbox in iNVT toolkit [START_REF] Oncu | Evaluation of digital inpainting quality in the context of artwork restoration[END_REF]. Similarly, two other metrics, ASV S and DN , were also computed using the saliency maps obtained

Conclusion

In this section, a novel approach for inpainted image quality evaluation has been proposed.

It is shown that the traditional image quality index could not be used for evaluating the inpainting results. By taking into account the specificities and objectives of image com- pletion problem and some characteristics of the humane visual system, such as perceptual saliency, two efficient metrics could be derived, the gray and color level versions.

An overview of existing image quality metrics and inpainting quality metrics has been discussed and compared with our proposals in some cases.

Eleven different digital inpainting algorithms were qualitatively evaluated by conducting a psychophysical experiment and a set of ten natural images were chosen in order to generate an inpainting database for evaluation. To avoid ranking bias, the inpainting algorithms were divided into two cases: the small and large damaged regions. The tested images were also classified into corresponding groups.

The proposed image inpainting quality indexes not only correlate with subjective evaluation but also could be applied to most of image inpainting approaches because they are no-reference inpainting quality metrics. The performed experimental results and comparison with some current metrics confirm the efficiency of the proposed indexes respect to both the Pearson's correlation, P CC, and the Spearman rank order correlation, SCC, coefficients.

Future work will include an expanded psychophysical experiment that will consider more recently natural images and current inpainting algorithms in order to reconfirm the efficiency of our proposals. An extensive research should be conducted with the aim of developing an IIQA metric for video or sequence images.

123

Inpainting Forgery Detection "It is not the strongest of the species that survives, nor the most intelligent that survives. It is the one that is the most adaptable to change." Today's technology allows users to manipulate digital media in ways that were simply impossible a decade ago. Tomorrow's technology will almost certainly allows us to manipulate digital media in ways that today seem unimaginable. These media are prone to several sources of accidental or intentional degradations. And as this technology continues to evolve, it will become increasingly important for the science of digital forensics to try to keep pace. As a result, there is a rapid increase of the digitally manipulated forgeries in mainstream media, on the Internet, especially on social network. Therefore, developing techniques to verify the integrity and the authenticity of the digital images became very important, especially considering the images presented as evidence in a court of law, as news items, as a part of a medical record or as a financial document, etc.

An image can become a forgery based on the context in which it is used. For instance, an image altered for fun or someone who has taken a bad photo, but has been altered to improve its appearance cannot be considered a forgery even though it has been altered from its original capture. In contrast, it is a forgery image if an altered image is used to Naturally, digital image forensics technology is a new research and it can be divided into active evidence and passive-blind evidence based on whether the additional information is embedded into digital images in advance or not. Alternatively, active evidence is mainly about digital watermark which has been proposed as a mean for fragile authentication, content authentication, detection of tampering, etc. While this approach can provide useful information about the image integrity and its processing history, the watermark has some drawbacks:

• The watermark must be inserted at the time of recoding before the tampering occurs.

• The watermark can be fragile and it is easy to be destroyed by an image processing operator such as compressing, rescaling, etc.

• The watermark cannot detect accurately areas where the image has been manipulated.

• The watermark cannot distinguish whether a manipulation is innocent, such as JPEG compression, sharpening from those which are malicious such as adding or removing parts of an image.

On the contrary, passive techniques for image forensics should operate in the absence of any watermark or signature. These techniques work on only the assumption that although digital forgeries may leave no visual clues that indicate tampering, they may alter the underlying statistics of an image. The set of image forensic tools can be roughly divided into five groups [START_REF] Farid | Image forgery detection[END_REF]:

1. Pixel-based methods that detect statistical anomalies introduced at the pixel level.

2. Format-based methods that leverage the statistical correlations introduced by a specific lossy compression.

3. Camera-based methods that exploit artifacts introduced by the camera lens, sensor, or on-chip processing.

4.

Physically-based methods that explicitly model and detect anomalies in the three dimensional interaction between physical objects, light and the camera.

5.

Geometric-based methods that make measurements of objects in the world and their positions relative to the camera.

Early tampering using powerful image processing tools such as Photoshop or Freehand, is not too big challenge for humans. However, the development of sophisticated algorithms in image processing field, such as image inpainting, which do not leave any obvious clues after manipulating image, make it relatively difficult to detect with human vision. Thus, image tampering detection is one of the primary objectives in image forensics.

In this chapter, we are considering a specific type of image forgery using inpainting algorithm to modify the context of image, namely inpainting detection. Since the main goal of inpainting is to remove or restore a part of the image based on the remaining parts of the same image such that the restored regions are undetectable by viewers, developing techniques to verify the integrity and the authenticity of the digital images became very important. Especially when the inpainting algorithms is more sophisticated and tampered images do not reveal any visual artifacts or anomalies, the detection algorithm can still work well based on the difference of underlying statistics between these images and the original one. To restore the large damaged regions, the main operation is copying and pasting pixels' intensity values from the known sources into the unknown regions. In principal, the inpainting detection is synonymous with copy-move forgery detection. However, there is a little difference between these two problems:

• The copy-move forgery techniques are used to detect the clone area using image processing tools. While the damaged regions in inpainting problem are restored from many distinguishing patches in the known source. These patches may not belong to the same area. Thus, the duplicated regions may not exist (for example, inpainting in previous section).

• The forged region decision has been made based on the amount of shift, the distance between the original and copied regions. However, the duplicated regions may not exist in inpainted image. Thus, it is impossible to confirm an inpainted image based on a shift counter as in copy-move detection.

• In some applications, the objective of inpainting algorithm is to remove or replace an object which may include the feature points with a homogeneous background which may not include any feature point. Thus, using image feature matching to detect the duplication region is not able to apply for inpainting detection in this sense.

Overview of forgery

To cover and summarize all forgery techniques would be hard and complex. Thus, this section only focuses on related forgery techniques that can be referred to compare and evaluate the performance of our proposal for inpainting detection purpose. Because we are interested in only large restored regions using inpainting algorithm with processing operations similar to copy-move methods, a brief evaluation of popular copy-move forgery detections will be considered in this section and listed in Table 5.1. As described before, the columns Year and Authors present the year of the publication and the name of the authors, respectively. The Type indicates the category of the algorithm. The two remaining columns describe for the used feature. Where F-type, short for 'Feature type', shows the kind of feature extracted from image or block, and the corresponding number of dimensions is given in column F-length, stand for 'Feature length'. The symbol '-' is used when the Although, a large number of copy-move detection algorithms have been published, most techniques follow a common scheme as shown in Figure 5.3. According to this scheme, the first step is pre-processing in which some operations are performed to normalize the input image. For instance, most methods require a grayscale image as input rather than color image. Thus, the color channels must be first merged to convert into gray level. Due to differences in the computational cost as well as the detected details, two processing alternatives such as block-based methods and keypoint-based methods [START_REF] Christlein | An evaluation of popular copy-move forgery detection approaches[END_REF] are used to extract the feature vectors. The matching step is to define the similarity between two feature descriptors which is interpreted as a cue for duplicated regions. Filtering schemes have been proposed to reduce the probability of false matches. Different distance criteria were also formulated in order to filter out weak matches. For example, most authors proposed the Euclidean distance between matched feature vectors. Bravo-Solorio and Nani [START_REF] Bravo-Solorio | Exposing duplicated regions affected by reflection, rotation and scaling[END_REF] proposed the correlation coefficient as a similarity criterion. Lastly, the postprocessing is only used to preserve matches that exhibit a common behavior. Consider a set of matches belonging to a copied region, they are expected to be spatially close to each other in both the source and the target blocks. Moreover, matches that originate from the same copy-move action should exhibit similar amounts of translation, scaling and rotation.

Block-based approaches

The key characteristic of the methods of this group is dividing the input image into overlapping blocks. The feature vector of each block is then extracted and used as input for block matching. The feature length depends on each extraction algorithm. Figure 5.4

shows a common illustration of the methods in this group.

There are many criteria to classify the methods of this group into sub-groups. For block matching, there are two sub-groups: exact match and fuzzy match. The difference between them is that the vector of block feature is identical or similar. Exact match only finds out exactly the same as the copy of image block and its robustness is limited. The fuzzy match is used more widely because of more practical value. For block feature extraction, most methods can be classified into four sub-groups:

• moment-based methods.

• dimensionality reduction-based methods.

• intensity-based methods.

• frequency domain-based methods. A notable constraint in this group is that the block size must be considerably smaller than the duplicated region to be detected. In this section, thirteen block-based methods covering all four groups are investigated.

Frequency-based methods

Methods in this group concentrate on transforming the pixel values within a block into spatial frequency space in order to extract and preserve high or low frequency features. In this group, there are three typical approaches based on Discrete Cosine Transform (DCT) [START_REF] Fridrich | Detection of copy move forgery in digital images[END_REF], Discrete Wavelet Transform (DWT) [START_REF] Bashar | Exploring duplicated regions in natural images[END_REF] and Fourier-Mellin Transform (FMT) [START_REF] Bayram | An efficient and robust method for detecting copy-move forgery[END_REF]. As one of the earliest methods, Fridrich et al. [START_REF] Fridrich | Detection of copy move forgery in digital images[END_REF] have proposed a simple and efficient algorithm to detect the duplicated region using block matching strategy. To avoid the influence of noise and compression, 256 DCT coefficients are used as features instead of the original pixel values. In addition, an extension of DCT for block size 16 × 16 is developed to prevent too many false matches instead of simply using the standard quantization matrix of JPEG (8 × 8 as in Figure 5.5). A detailed extension of the quantization matrix is given in [START_REF] Fridrich | Detection of copy move forgery in digital images[END_REF]. All feature vectors are then lexicographically sorted to reduce computational complexity. Finally, the forgery decision is made based on a 2D shift counter which accumulates the frequencies of relative distance of matching blocks.

The second frequency-based approach recalled in this section has been proposed by variant and feature vectors. Experimental results demonstrate the validity of the proposed approach to tampered images undergone some attacks like Gaussian blur filtering, Gaussian white noise contamination and lossy JPEG compression.

The third technique for reduction of dimensionality has been proposed by Bashar et al. [START_REF] Ryu | Detection of copy-rotate-move forgery using zernike moments[END_REF] as mentioned in previous subsection. In their work, an extension of traditional PCA, called Kernel Principal Component Analysis (KPCA) which achieves non-linear dimensionality reduction through the use of kernels, is applied to reduce the dimensionality of feature. A performance evaluation of this approach is described in more details in [START_REF] Ryu | Detection of copy-rotate-move forgery using zernike moments[END_REF].

Moment-based methods

In general, moments describe numeric quantities at some distance from a reference point or axis. In image processing, computer vision and related fields, an image moment is a certain particular weighted average (moment) of the image pixels' intensities, or a function of such moments, usually chosen to have some attractive property or interpretation. In this context, three kinds of image moments, such as blur moment [START_REF] Mahdian | Detection of copy-move forgery using a method based on blur moment invariants[END_REF], Hu moment [START_REF] Wang | Fast and robust forensics for image region-duplication forgery[END_REF] and Zernike moment [START_REF] Ryu | Detection of copy-rotate-move forgery using zernike moments[END_REF], have been proposed.

The first moment-based method was proposed by Mahdian and Saic [START_REF] Mahdian | Detection of copy-move forgery using a method based on blur moment invariants[END_REF] where blur moment invariants are developed as block feature. Here, each block is represented by blur invariants which are function of central moments. 24 blur invariant components up to the seventh order are extracted to create a 24D-feature vector. The detailed implementation of this invariant extraction is found in [START_REF] Mahdian | Detection of copy-move forgery using a method based on blur moment invariants[END_REF]. For color images, moment invariants of each block in each channel are computed separately, resulting in a 72D-feature vector. To reduce the dimension, a PCA is applied and the number of dimensionality is cut down to 9D. In addition, the KD-tree representation is constructed for searching nearest neighbors to improve the efficiency of finding neighboring blocks.

Following the same idea, Wang et al. [START_REF] Wang | Fast and robust forensics for image region-duplication forgery[END_REF] used first four Hu moments as features instead of blur invariants. The Hu moments are invariant with respect to scale, position, and orientation. The efficiency of this approach lies in the use of a Gaussian pyramid representation to reduce the dimension of input image as well as reduce the total number of blocks to narrow block-matching searching space. The Hu moment is applied to the fixed sized overlapping blocks of low-frequency image. Finally, similar eigenvectors are matched using a certain threshold value and some mathematical morphology operations are performed to locate the tampered parts.

The last method of this group has been recently proposed by Ryu et al. [START_REF] Ryu | Detection of copy-rotate-move forgery using zernike moments[END_REF] in which Zernike moments are used as features to detect the duplicated regions. Of various types of moments defined in the literature, Zernike moments have been proven to be superior to the others in terms of insensitivity to image noise, information content, and ability to provide faithful image representation. In particular, the magnitude of Zernike moments is algebraically invariant against rotation. So this method can detect a forged region even though it is rotated. Each block is represented by a feature vector of 12 Zernike moments.

For more details of the algorithm, the reader could refer to [START_REF] Ryu | Detection of copy-rotate-move forgery using zernike moments[END_REF].

Intensity-based methods

The last group of detection techniques presented in this thesis is intensity-based approach where the feature vectors are computed directly from the pixels' intensities instead of transforming into other orthogonal projections. Four detection techniques are considered.

The first detection technique was proposed by Luo et al. [START_REF] Luo | Robust detection of region-duplication forgery in digital image[END_REF]. For each block, seven characteristic features are calculated including three average components of the red, green and blue channels and four other directional information components of blocks. To calculate the last four features, the block is divided into 2 equal parts in 4 directions as The second technique in this group was introduced by Bravo-Solorio et al. [START_REF] Bravo-Solorio | Exposing duplicated regions affected by reflection, rotation and scaling[END_REF]. The authors considered the entropy of a block as a discriminating feature. Four color-dependent features are calculated considering only the pixels within a disc of diameter q, which just fits inside block. The first three features are independently computed as the average of the red, green and blue components of the pixels in the disc as in Luo's approach [START_REF] Luo | Robust detection of region-duplication forgery in digital image[END_REF], but the fourth feature is computed as the entropy of the luminance channel. The algorithm uses colour-dependent feature vectors to reduce the number of comparisons in the search stage.

While 1D descriptors, invariant to reflection and rotation, are used to perform an efficient search in terms of memory usage. To reduce the number of false matches, the correlation coefficient between two features is used instead of Euclidean as other methods.

The third approach was recommended by Lin et al. In this context, each keypoint is characterized by a feature vector that consists of a set of image statistics collected at the local neighborhood of the corresponding keypoint. Consequently, fewer feature vectors are estimated, resulting in reduced computational complexity of feature matching and post-processing. Two different kinds of keypoints are examined such as Scale Invariant Feature Transform (SIFT) [START_REF] Huang | Detection of copy-move forgery in digital images using sift algorithm[END_REF][START_REF] Pan | Region duplication detection using image feature matching[END_REF][START_REF] Amerini | A sift-based forensic method for copy-move attack detection and transformation recovery[END_REF] and Speeded Up Robust Features (SUFT) [START_REF] Bo | Image copy-move forgery detection based on surf[END_REF][START_REF] Shivakumar | Detection of region duplication forgery in digital images using surf[END_REF]. A drawback of keypoint methods is that copied regions exhibit little structure or contain the homogeneous regions, it may happen that the region is completely missed.

Keypoint-based approaches

SIFT-based methods

SIFT feature shorting for Scale Invariant Feature Transform has been proposed by D. G.

Lowe [START_REF] Lowe | Distinctive image features from scale-invariant keypoints[END_REF]. This feature is invariant to image scale, rotation and originally developed for object recognition. In fact, SIFT features are also a good solution for duplicated regions detection because of their robust performance and relatively low computational costs. There are four main steps of computation to generate the SIFT features: i) Scalespace extrema detection; ii) Keypoint localization; iii) Orientation assignment; iv) Keypoint descriptor generation. The detailed specification and source code can be found in [START_REF] Lowe | Distinctive image features from scale-invariant keypoints[END_REF].

At each keypoint, a 128 dimensional feature vector is generated from the histograms of local gradients in its neighborhood. To ensure the invariance of the obtained feature vector to rotation and scaling, the size of the neighborhood is determined by the dominant scale of the keypoint, and all gradients within are aligned with the keypoint's dominant orientation. Furthermore, the obtained histograms are normalized to unit length, which renders the feature vector invariant to local illumination changes.

In order to identify possible cloned areas, the detected SIFT keypoints are then tentatively matched based on their feature vector using the best-bin-first algorithm [START_REF] Huang | Detection of copy-move forgery in digital images using sift algorithm[END_REF][START_REF] Pan | Region duplication detection using image feature matching[END_REF] or agglomerative hierarchical clustering [START_REF] Amerini | A sift-based forensic method for copy-move attack detection and transformation recovery[END_REF]. To handle rotation and scaling, Pan and

Lyu [START_REF] Pan | Region duplication detection using image feature matching[END_REF] proposed to use RANSAC; while Amerini et al. [START_REF] Amerini | A sift-based forensic method for copy-move attack detection and transformation recovery[END_REF] applied a scheme to cluster the locations of detected features before using RANSAC to estimate the geometric transformation between the original area and its copy-moved verions.

SURF-based methods

The second kind of keypoint is used for detection of duplicated regions is SUFT feature.

SUFT feature known as Speeded Up Robust Feature has been recently published by Bay et al. [START_REF] Bay | Speeded-up robust features (surf)[END_REF]. Keypoints are found by using a so called Fast-Hessian Detector that is based on an approximation of the Hessian matrix for a given image point. The responses to Haar wavelets are used for orientation assignment, before the keypoint descriptor is formed from the wavelet responses in a certain surrounding of the keypoint. There are three main stages of computation used to generate the SIFT features: i) Integral image; ii) Hessian matrix-based interest point; iii) Interest point descriptors. The detailed specification can be referred to [START_REF] Bay | Speeded-up robust features (surf)[END_REF].

In contrast to SIFT feature, which approximates Laplacian of Gaussian (LoG) with Difference of Gaussians (DoG), SURF feature approximates second order Gaussian derivatives with box filters. Moreover, only 64 dimensions are used, reducing the time for feature computation and matching, and increasing simultaneously the robustness. The extracted SURF keypoints are then matched using divide and conquer algorithm [START_REF] Bo | Image copy-move forgery detection based on surf[END_REF] or KD-tree structure [START_REF] Shivakumar | Detection of region duplication forgery in digital images using surf[END_REF]. To verify the capacity of the copy-move detection techniques for inpainting forgery, a series experiments have been carried out on a set of inpainted images. Most of copymove detection techniques introduced in Section 5.2 have been applied. In this work, we developed the framework in [START_REF] Christlein | An evaluation of popular copy-move forgery detection approaches[END_REF] for this purpose. Figure 5.15 and 5.16 show an example of the results for our experiment. No detection has been found in the Figure 5.15. Figure 5.16-b detected a small copy-move part but it is uncompleted. This is certain because the forged region has been filled from many small and distinct parts. Surely, it cannot detect the forged region completely.

According to our observation, all outputs either cannot detect the forgery region or make a false detection. This confirms firmly that the copy-move detection methods is not suitable for detecting inpainting forgery. A different framework should be considered and developed for this special case.

In fact, to the best of our knowledge there is almost no study about image inpainting forgery. Thus, the purpose of our work is to introduce an efficient and reliable inpainting detection method. The proposed method is designed based on the common principle used by exemplar-based inpainting algorithms. It aims at detecting whether the input image has been edited following the aforementioned principle or not. The performance of the proposed method is evaluated on a set of various natural images. We also report its robustness with regards to different inpainting techniques.

As mentioned in Chapter 1, several approaches of image inpainting have been proposed in the literature. Most of them could be categorized into two types based on the purpose [START_REF] Arias | A variational framework for exemplar-based image inpainting[END_REF].

The first category is geometry-oriented approaches in which the missing regions are filled by diffusing the information from the known region into the missing one. These methods are suitable for filling narrow or small area like scratches but are less efficient for large area. The second category is the texture-oriented approaches. Inspired by texture synthesis methods, these methods produce an impressive output in recovering large damaged regions.

they could be further subdivided into two subgroups: exemplar-based completion methods [17,18,[START_REF] Wu | Object removal by cross isophotes exemplar-based inpainting[END_REF][START_REF] Zhang | Exemplar-based image inpainting using color distribution analysis[END_REF][START_REF] Wong | A nonlocal-means approach to exemplar-based inpainting[END_REF] and pixel-based completion methods [START_REF] Wexler | Space-time completion of video[END_REF][START_REF] Pritch | Shift-map image editing[END_REF]40].

In this study, we subscribe to the exemplar-based completion methods since it is more suited for large regions restoration or hiding a whole object. In inpainting methods, the missing information is restored based on the most similar patches under a pre-defined priority. In this sense, the inpainting is similar to a copy-paste operation regarding the notion of patches. Nevertheless, as described previously, in copy-paste approaches a continuous region is duplicated and pasted into the missing one instead of having small patches coming from different parts as in the case of inpainting methods. This is why copy-move detection cannot be applied for inpainted images.

Following this observation and by analyzing principles of image inpainting algorithms in the second group, we introduce a novel approach to detect inpainted regions. The proposed algorithm can be summarized through three main steps as described below. Let consider a window centered at pixel p denoted as a patch Ψ p . The patch size, three thresholds θ 1 , θ 2 and θ 3 are global parameters for the proposed algorithm. • The similarity between two patches, Sim(Ψ p , Ψ i ), should be less than a threshold, θ 1 . This threshold is used in order to reduce the probability of false matches while preserving suitable matches.

• The distance between two similar patches, Dist(Ψ p , Ψ i ), should be greater than a threshold, θ 2 . This criterion is applied to preclude nearby patches or identical patches.

• The number of the same pixels in two patches, Card(Ψ p ∩ Ψ i ), should be greater than a threshold, θ 3 . This constraint is introduced to ensure that at least θ 3 pixels are copied between two patches.

Figure 5.17. The detail scheme of our method.

Experimental results

In order to evaluate the performance of the proposed inpainting detection algorithm, a series of experiments are carried out and discussed in this section. The performance evaluation is considered comprehensively in two directions:

• many different inpainting algorithms for one image.

• one inpainting algorithm for many different images.

In addition, the ground truth images are used in comparison with the detection outputs.

In consequent, the obtained results confirm our proposal for inpainting detection with visual inspection and objective measurements. The detailed discussion is given as below.

Test for inpainting forgery

We implemented the proposed detection algorithm using C language and tested on a set of natural images with various contents. The output of the algorithm is a binary mask where white pixels correspond to detected inpainted regions and black pixels are non-inpainted areas. Green patch is added to identify the centroid of the inpainted region. In order to evaluate the visual performance of our detection, an experimental scheme is applied and described as follows.

First, an original image is used as ground truth with a binary mask image identifying an area need to be inpainted. An inpainting method is applied to the latter to generate an inpainted image. Finally, the inpainted image is used as input for our detection scheme to generate the detection mask. Figure 5.19 shows some results for our detection with the inpainting method in [18].

The parameters of our algorithm have been tuned as follows: patch size l = 5 and thresholds θ 1 = 0.1; θ 2 = l/2 and θ 3 = l 2 /3. It can be easily noticed that the proposed approach achieves good results by localizing quite precisely the inpainted object. The results yield to a direct conclusion about the presence of forgery or not. In order to evaluate the robustness of our method, we applied three different inpainting methods [17,[START_REF] Wu | Object removal by cross isophotes exemplar-based inpainting[END_REF][START_REF] Zhang | Exemplar-based image inpainting using color distribution analysis[END_REF] to modify the original images. This leads to a set of inpainted images for the same input image. Figure 5.20 depicts an example for one original image (a), inpainted images using respectively methods described in [17], [START_REF] Wu | Object removal by cross isophotes exemplar-based inpainting[END_REF] and [START_REF] Zhang | Exemplar-based image inpainting using color distribution analysis[END_REF] (b) and the obtained detection masks (c). Again, the proposed approach allows detecting the presence of inpainting forgery even with the use of different inpainting techniques.

Performance evaluation

In order to quantify the efficiency of our inpainting forgery detection, we used objective measures namely Precision, Recall and F 1 often used for information retrieval performance evaluation [START_REF] Manning | Introduction to information retrieval[END_REF].

Precision and Recall correspond to exactness and completeness of the results. In our perspective, the Precision is applied to estimate the probability that a detected region is correct. This probability is defined as follows: measure, the harmonic-mean of Precision and Recall is proposed and calculated as given in equation (5.4).

F 1 = 2P R P + R (5.4)
We tested the proposed method to fifteen images. The corresponding Precision, Recall and F 1 measurements are presented in Table 5. Experimental results supported that the proposed method was appropriate to identify and localize the inpainted region with high accuracy even though the image could be modified by many different inpainting methods.

Although having achieved promising performance in detecting inpainted region, our method still contains limitation in some images. One example is shown as the top image in Figure 5.16 where the unexpected matches have been detected in the homogeneous or flat regions. This is because there are always similar patches in these kinds of region with any thresholds. Thus, it could be considered as an important future work to improve the detection performance for such case. In addition, our method is suitable to detect for exemplar-based inpainting methods but not for pixel-based inpainiting methods. A further study should be conducted to deal with such cases.

Conclusion

The goal of the current research was to develop a framework for digital image inpainting.

Two related trends are exploited such as inpainting quality assessment and inpainting forgery detection. The main contributions of the thesis are related to these two trends.

A specific concept of inpainting problem and the related definitions was formulated in Chapter 2. Besides, a detailed classification of existing digital image inpainting algorithms was provided. Accordingly, most of current inpainting methods can be classified into three main groups. However, because of extensive researches, it is impossible to have a common criteria for classification. Thus, there are some inpainting methods that are not included in the above groups such as multi-source image completion.

A novel framework of the second group has been proposed in Chapter 3 based on a hierarchical representation. Additionally, a window-based priority which classifies patches in a more suitable way has been also introduced and combined with the multi-resolution patch in order to ensure for more pleasant results. A comparison with all three groups of inpainting methods has been carried out with a set of natural and real archaeological images. The experimental results show that the proposed approach outperforms the methods of the state-of-the-art in regard to visual quality.

However, the proposed method suffers from some limitation mainly on computational performance side. Although, this framework produces the acceptable results in most case, it is time consuming. This is mainly due to the patch searching process. Thus, an improvement has been proposed. An offset map defining the relationship between the known pixels and unknown pixels is used instead of the multi-resolution patch for completing higher level resolution. A global optimization strategy based on graph-cut algorithm has been introduced in order to optimize the offset map by considering only some neighbors They demonstrated impressive results in term of both visual quality and computational time.

Chapter 4 is devoted to the evaluation of inpainted images. Very often, the results of image inpainting are evaluated subjectively or by using some objective metrics not well adapted to the specificities of their criteria. However, the subjective evaluation experiments are time consuming, complex and unpredictable due to some uncontrolled human factors such as fatigue, visual discomfort, knowledge, etc. In this chapter, a series of traditional image quality assessment and a few existing inpainting quality assessment metrics have been investigated. Since the existing IQA metrics could not be directly applied because the specificities and goals of both image quality, in its broad sense, and image inpainting are different. Therefore, an inpainted image quality assessment is very meaningful in this case. This is the main content of this chapter. A novel approach for objective Image Inpainting Quality Assessment has been designed. The proposed metric is composed of two terms: coherence term which evaluates the consistency between the restored regions and source regions; and structure term which attracts the viewer attention. Two versions for graylevel and color image have been developed. The psychophysical experiments have been run

to confirm the performance of our metrics. The obtained results showed that none of the considered metrics correlated well with perceived overall inpainting quality. However, the scores obtained from our proposal indicate a better performance when compared to some of the other existent inpainting-specific quality metrics.

The last contribution was presented in Chapter 5. In this chapter, we first defined our problem and introduced some differences with the existing forgeries. An overview of current forgery detection has been reported and many results when using existing forgery detection to detect inpainted images were shown. The demonstration pointed out an inefficiency of this approach. Many experimental results supported that the proposed methods is appropriate to identify and localize the inpainted region with high accuracy even though the image could be modified with many different inpainting algorithms.

In conclusion, the current research has analysed, developed and evaluated objective methods for inpainting problem. This dissertation built a complete picture of inpainting problem along with the corresponding contributions to fully address each part. A series of experimental results and comparison with existing approaches coming from literature are performed. They all confirmed the outstanding results for our proposals.

Future works

In the course of the research carried out for this thesis a number of possible directions for further research have been identified. Relating to different parts of this thesis, they can be divided into three separate issues.

For inpainting algorithm, despite the extensive research carried out in the field of digital image inpainting, there is still room for improvements. In the current algorithms, the patch selection is an essential step to complete the image. A perceptual patch similarity that is more stable and effective should be carefully considered. An extension of our framework could be developed for multiple source images or videos. Experimenting with high resolution images should also be considered for further research. The main issue when dealing with high resolution images as input for inpainting algorithms is to a significant increase of running time (up to several hours). However, most of the existent algorithms were not designed for high resolution images. Thus, developing new algorithms, able to inpaint high resolution images would potentially increase the quality of the inpainting.

But, guaranteeing high inpainting quality would be a challenging issue.

For inpainting quality assessment, regarding the evaluation of inpainting quality, further work should be focused on finding a metric that does not depend on a reference image and that correlates better with perceived quality. Conducting a psychophysical experiment that considers more natural images and current inpainting algorithms, as well as quality metrics, could also significantly contribute to a better understanding of the deficiencies of current inpainting quality metrics. Identifying these deficiencies would make space for further improvements.

For inpainting forgery detection, although having achieved promising performance in detecting inpainted region, the detection technique could be improved further. Some parameters could be considered as threshold to reduce the unexpected matching patches in the special regions such as homogeneous or flat. Moreover, the proposed detection can apply only for inpainted images which had been edited by exemplar-based inpainting algorithms but not for pixel-based inpainting methods or interpolation-based methods. Therefore, some further studies could be developed with these directions. Finally, a forgery detection for inpainting video is also a potential and considerable direction of research.

Résumé

  La technique d'inpainting (retouche d'images) est considérée comme l'une des solutions efficaces pour la restauration dimages dégradées et, même la vidéo ou les contenus 3D stéréoscopiques. Il s'agit d'un outil essentiel pour la restauration et la conservation des objets archéologiques. En effet, lors de fouilles de sites historiques, de nombreux objets de valeur tels que des statues, des bâtiments, des peintures murales, etc., sont découverts et récupérés. Malheureusement, la plupart d'entre eux se retrouvent endommagés ou fracturés. Dans l'optique d'apprendre de ces objets, les techniques numériques sont utilisées pour les restaurer en utilisant des connaissances a priori fournies par les archéologues et les artistes. Cela permet de reconstruire, préserver et maintenir ces oeuvres artistiques de grande valeur. En effet, les progrès des technologies et des systèmes d'acquisition d'images ont permis la transition des méthodes traditionnelles de retouche manuelle vers des techniques numériques, ouvrant un nouveau domaine de recherche appelé inpainting d'images. Dans cette thèse, notre travail visait à analyser et examiner les méthodes de la littérature des techniques d'inpainting d'images qui se décomposent en trois groupes. Les avantages et les inconvénients de chaque approche sont analysés finement en utilisant des critères objectifs et subjectifs. Sur la base de cette étude, une nouvelle approche d'inpainting d'images est proposée et confrontée à la littérature. Elle offre de bonnes performances en termes de qualité de rendu et d'efficacité calculatoire. Une autre contribution réside dans la proposition d'une nouvelle métrique de qualité dédiée à l'évaluation des techniques d'inpainting. Au regard de l'état de l'art dans le domaine, les images ayant subi des retouches par inpainting sont très souvent évaluées subjectivement ou au moyen de quelques mesures objectives loin d'être adaptées aux particularités de cette technique. La métrique proposée offre à la fois de bonnes performances et une adaptabilité au domaine. La dernière contribution de ce travail est un problème moins étudié et lié à la détection d'inpainting.

1. 1 .

 1 Problem statement

Figure 1 . 1 .

 11 Figure 1.1. Some wall paintings in Villa of the Mysteries, Pompeii.

Figure 1 . 2 .

 12 Figure 1.2. Painting restoration work in the museum.

Figure 1 . 3 .

 13 Figure 1.3. Examples of image restoration. (a), (c) The damaged image; (b) Manually restored image; (d) Automatically restored image using an inpainting algorithm.

1 . 2 . 3 .

 123 T. T. Dang, M. C. Larabi, A. Beghdadi, "Multi-resolution patch and window-based priority for digital image inpainting problem", 3 rd International Conference on Image Processing Theory, Tools and Applications (IPTA2012), pp. 280-284, 2012, Istabul, Turkey. T. T. Dang, A. Beghdadi, M. C. Larabi, "Archaeological image inpainting", the 4 th European Workshop on Visual Information Processing (EUVIP2013), 2013, Paris, France. T. T. Dang, A. Beghdadi, M. C. Larabi, "Inpainted image quality assessment", the 4 th European Workshop on Visual Information Processing (EUVIP2013), pp. 76-81, 2013, Paris, France.1.4. Thesis outline 4. T. T. Dang, A. Beghdadi, M. C. Larabi, "Perceptual quality assessment for color image inpainting", IEEE International Conference on Image Processing (ICIP2013), 2013, Melbourne, Australia. 5. T. T. Dang, A. Beghdadi, M. C. Larabi, "Perceptual evaluation of digital image completion quality", 21 st European Signal Processing Conference (EUSIPCO2013), 2013, Marrakech, Morocco. 6. T. T. Dang, A. Beghdadi, M. C. Larabi, "Visual coherence metric for evaluation of color image restoration", the Colour and Visual Computing Symposium (CVCS2013), pp. 1-6, 2013, Gjvik, Norway. 7. T. T. Dang, A. Beghdadi, M. C. Larabi, "A hierarchical approach for high-quality and fast image completion", The Fifth International Conference on Knowledge and Systems Engineering (KSE2013), pp. 11-21, 2013, Hanoi, Vietnam. 8. T. T. Dang, A. Beghdadi, M. C. Larabi, "A perceptual image completion approach based on a hierarchical optimization scheme", Signal Processing, Volume 103, pp. 127-141, October 2014.

Figure 2 . 1 .

 21 Figure 2.1. Inpainting problem.

Figure 2 . 2 .

 22 Figure 2.2. An illustration of inpainting region classification based on the equation 2.1; (a) a small inpainting region; (b)a large inpainting region.

Figure 2 . 3 .

 23 Figure 2.3. An illustration for approaches of Bertalmío et al.. (a) An overimposed text image; (b) The corresponding masked image;The removed text images using approaches in (c)[START_REF] Bertalmío | Image inpainting[END_REF] and (d)[START_REF] Bertalmío | Navier-stokes, fluid dynamics, and image and video inpainting[END_REF].

Figure 2 . 4 .

 24 Figure 2.4. An illustration of comparison between elastica and total variation inpainting. In the case of large aspect ratios, the TV inpainting model fails to comply to the Connectivity Principle. (a) original image; (b) inpainting domain; the output when using (c) total variation and (d) elastica inpaintings

  Figure 2.5 gives an overview of the algorithm principle. The pixel in red patch will be filled-in by one of centers of candidate patches (blue patches).

Figure 2 . 5 .

 25 Figure 2.5. Overview of Efros' algorithm

Figure 2 .

 2 Figure 2.6. An illustration of Ahikhmin's texture synthesis method[START_REF] Ashikhmin | Synthesizing natural textures[END_REF]. The candidate patches are considered based on the correlation between unknown pixel and its neighbors.

Figure 2 . 7 -

 27 Figure 2.7-a shows a highest priority pixel p, belonging patch Ψ p , represented as a square

Figure 2 . 7 -Figure 2 . 7 .

 2727 Figure 2.7-b shows a candidate for filling in the patch determined by the pixel p and the inpaint step is exemplified in Figure 2.7-c.

Figure 2 . 8 .

 28 Figure 2.8. An output of Criminisi's approach [17]. (a) The original image; (b) The mask image; (c) The inpainted image.

Figure 2 . 9 .

 29 Figure 2.9. The maps of confidence and data terms in Criminisi's priority. (a) Confidence map; and (b) Data map.

Figure 2 . 10 .

 210 Figure 2.10. The curve-based outputs using Sun's method [40]. (a) The original image; (b) The mask image; two different curves are pre-defined in (c) and (d); (e) and (f) two corresponding outputs.

  [START_REF] Le Meur | Hierarchical super-resolution-based inpainting[END_REF]. Authors have applied Belief Propagation algorithm more effectively to restore the damaged region. The main novelty of proposed method is the combination of multiple inpainted version of input image.

Figure 2 .

 2 Figure 2.11 illustrates the main concept underlying of the proposed algorithm.

Figure 2 . 11 .

 211 Figure 2.11. The framework of Le Meur's approach.

Figure 2 . 12 .

 212 Figure 2.12. How to apply graph cuts for computer vision. (a) a given image; (b) nodes of graph; (c) edges of graph (n-link); (d) nodes with t-link and n-link; (e) a cut of graph.

  [START_REF] Mobahi | Data-driven image completion by image patch subspaces[END_REF] where D(Ψ p , Ψ p+sm(p) ) measures the similarity between two patches based on the Euclidean distance. To further enforce global consistency and to speed up convergence, a multiscale Gaussian pyramid is integrated to solve the energy function. Moreover, the use of a feature vector representation allows to compensate the loss information at low resolution levels. A series of experimental results and comparisons with existing inpainting methods show a good performance of the proposed algorithm.

Figure 2 . 13 .

 213 Figure 2.13. Inpainting based on the shift-map optimization [52]. From top to bottom: original image, black pixels need to be removed, and output.

  Whyte et al.[START_REF] Whyte | Get out of my picture! internet-based inpainting[END_REF] tackled the inpainting problem using images of the same scene retrieved from Internet using viewpoint-invariant image search. Only top 30 search results are used for completing the original image. The retrieved images are registered to the query image with multiple homographs allowing registration of multiple scene planes or images taken from the same viewpoint. Each registered image is applied to propose a solution, by combining it into the target region using Poisson blending, to minimize the effect of differences in lighting. In the final step, a MRF formulation allows the multiple proposals to be combined into a single result, selecting reliable regions of different proposals and concealing the boundaries between regions. Figure 2.15 shows an example of Whyte's system based on OxfordBuildings Database.The common shortcoming of these methods is that it relies on managing and operating a huge image database. When the algorithm fails, it can be due to a lack of good scene matches (if the target image is atypical), or because of semantic violations (e.g. failure to recognize people hence copying only part of them), or in the case of uniformly textured backgrounds (where this algorithm might not find the precise same texture in another picture of the database).

Figure 2 . 15 .

 215 Figure 2.15. An example query (left image) and the first 9 results returned by the viewpoint invariant image search engine.

Figure 3 . 1 .

 31 Figure 3.1. Classification of patches via eigenvalues

Figure 3 . 2 .

 32 Figure 3.2. The window-based priority of different regions. (a) Flat region; (b) Texture region; (c) Edge or contour.

  3.2-c) (0.025, 0.006 )

Figure 3 . 3 .

 33 Figure 3.3. A restoration of the Kanizsa triangle using inappropriate and appropriate patch selection. (a) & (d) image to be inpainted; (b) & (e) a patch selection respectively with and without improvement; (c) & (f) Final results.

Figure 3 .

 3 Figure 3.4 illustrates priority of pixels on the boundary of inpainting regions where the red color refers to highest value and the blue color refers to lowest one. One can notice that higher values can be observed on contours as explained previously.

Figure 3 . 4 .

 34 Figure 3.4. Illustration of the proposed priority focusing on edge preservation.

Figure 3 .Figure 3 . 5 .

 335 Figure 3.5 illustrates the performance of the proposed method on various low-resolution images. These images are downsampled versions of the original ones (the down sampling factor is set to 4 in both directions). Four inpainting methods, namely Criminisi et al.[17], Wu et al.[START_REF] Wu | Object removal by cross isophotes exemplar-based inpainting[END_REF], Zhang et al.[START_REF] Zhang | Exemplar-based image inpainting using color distribution analysis[END_REF] and Cheng et al.[18], belonging to the second group of approaches, are implemented with the same patch size for a fair comparison. Visual inspection of the results given in Figure3.5 shows that the proposed approach achieves good results in most cases compared to the others.

Figure 3 . 6 .

 36 Figure 3.6. A multi-resolution patch composed of pixels on different scales

  , 3.8 and 3.9 confirm the effectiveness of our algorithm in compare with existing methods in case of natural images, while the visual results in Figures 3.10 and 3.11 give an outstanding quality of our algorithm in case of archaeological images.

Figure 3 . 7 .Figure 3 . 8 .Figure 3 . 9 .Figure 3 . 10 .Figure 3 . 11 .

 373839310311 Figure 3.7. Visual comparison of 'boat' image across all five algorithms: (a) The image to be inpainted; The ouputs using approach of (b) Criminisi et al. [17]; (c) Wu and Ruan [20]; (d) Zhang and Lin [21]; (e) Cheng et al. [18]; and (f) our proposal.

Figure 3 . 12 .

 312 Figure 3.12. The operators in global optimization algorithm. (a) An original image; (b) An offset; (c) Data term; (d) Smoothness term.

E

  s (om(p), om(q)) = 0 om(p) = om(q) βδM (om(p)) + γδG(om(p)) otherwise (3.13) where β and γ are weighting factors balancing these two terms, and are set to β = 1, γ = 2 in our experiment. The terms δM and δG denote the differences of magnitude and gradient, respectively. They are defined as follows: δM (om(p)) = ||I(n p ) -I(q )|| + ||I(n q ) -I(p )|| (3.14) δG(om(p)) = ||∇I(n p ) -∇I(q )|| + ||∇I(n q ) -∇I(p )|| (3.15)

Figure 3 .Figure 3 . 13 .

 3313 Figure 3.13 illustrates an example of the offset map at the original resolution image after optimization by the graph-cuts algorithm. Each offset is the 2-D coordinates including horizontal and vertical relationships. The output generated by two corresponding offset maps is shown in Figure 3.13-b.

Figure 3 . 14 .

 314 Figure 3.14. Interpolation of Offset-map. (a) Image gaussian pyramid; (b) Interpolation between two adjacent levels.

Figure 3 .

 3 Figure 3.14-a illustrates an example of the Gaussian pyramidal decomposition and the associated reconstruction scheme (Figure 3.14-b).

Figure 3 . 15 .Figure 3 . 16 .

 315316 Figure 3.15. Inpainting results for four commonly used images: a) the original images; results when using method of b) Criminisi et al. [17]; c) Wu and Ruan[START_REF] Wu | Object removal by cross isophotes exemplar-based inpainting[END_REF]; d) Zhang and Lin[START_REF] Zhang | Exemplar-based image inpainting using color distribution analysis[END_REF]; e) Cheng et al.[18]; and f) Our proposal.[START_REF] Bonnier | Evaluation of spatial gamut mapping algorithms[END_REF]

Figure 3 . 17 .

 317 Figure 3.17. Analysis of local performance of our method.

Figure 3 . 18 .

 318 Figure 3.18. An example of outputs for each stage in our algorithm.

Figure 3 . 19 .

 319 Figure 3.19. Performance evaluation. (a) Image to be inpainted; Outputs when using methods of (b) Criminisi et al. [17]; (c) Pritch et al. [61]; (d) Dang et al. [27]; and (e) our proposal.

  (a) Original uncompressed image (b) Q = 90, PSNR = 45.53dB (c) Q=30, PSNR = 36.81dB (d) Q=10, PSNR = 31.45dB

Figure 4 . 1 .

 41 Figure 4.1. An example of PSNR values for jpeg compressed images at various quality levels.

Figure 4 .

 4 Figure 4.1 lists some PSNR values corresponding the compressed images at various quality levels (Q = 90, 30, 10). Although, it has been proven that these two metrics do not correlate well with perceived image quality, these measures are easy to compute and extensively used throughout the literature of image processing, communication, and many other signal processing fields.

Figure 4 . 2 .

 42 Figure 4.2. Block diagram of the Visible Differences Predictor.

  function (CSF), implemented as a filtering process. A Fast Fourier transform is applied to the value R ij . The resulting magnitudes f uv (R ij ) are filtered by a CSF which is a function of the image size in degrees and light adaptation level L m . The variation in sensitivity due to signal content is referred to as masking. Masking effects are modeled by the detection mechanism, which is the most complicated element of the VDP. It consists of four sub-components: image channel decomposition, spatial masking, psychometric function, and probability summation. During the image channeling stage, the input image is fanned out from one channel to 31 channels or bands. Each channel is associated with one cortex filter which consists of a radial filter (dom, difference of mesa filter) and an orientation filter (fan filter). The total number of radial filters is six resulting in five frequency bands and one base band for a typical image of standard size. Each of these bands except for the base band is further fanned out into six channels of different orientation. Thus, five frequency bands times six orientations per bands plus one base band results in 31 channels.

Figure 4 . 3 .Figure 4 . 4 .

 4344 Figure 4.3. SSIM flowchart for a local window

4. 2 . 4 VIF

 24 Sheikh et al.[START_REF] Sheikh | Image information and visual quality[END_REF] have adopted a new paradigm for image quality assessment, the visual information fidelity (VIF) paradigm which is an information theoretic framework based on Natural Scene Statistics (NSS) modeling in concert with an image degradation model and an HVS model.

Figure 4 . 5 .

 45 Figure 4.5.Mutual information between C and E quantifies the information that the brain could ideally exact from the reference signal, whereas the mutual information between C and F quantifies the corresponding information that could be extracted from the distorted signal.

  model has been shown to capture key statistical features of natural images. The distortion model describes how the statistics of an image are distributed by a generic distortion operator. The distortion model chosen for VIF provides important functionality while being mathematically tractable and computationally simple. It is a signal attenuation and additive noise model in the wavelet domain:

  µ I = (1/N ) N i=1 I i and µ L(I) = (1/N ) N i=1 L(I i ) denote the average pixel value and average luminance of I, respectively; and µ L(E+µ I ) = (1/N ) N i=1 L(E i + µ I ) denotes the average luminance of the mean-offset distortions E + µ I . Finally, using a strategy inspired from what is termed as global precedence in the HVS, VSNR computes a global precedence preserving contrast (d gp ).

Figure 4 . 6 .

 46 Figure 4.6. An evaluation of PWIIQ index for inpainting algorithms; (a) the original image with the white hole; The results of (b) Total variation model; (c) Criminisi et al. [17] and (d) Chen et al. [78].

Figure 4 . 7 .

 47 Figure 4.7. An example of saliency map is used for approach in [71]. The saliency map (b) of the original image (a) is generated by iNVT tool.

  Another class of artifacting specific to inpainting applications is represented by the outregion artifacting. As its name suggests, this class encompasses cases where the inpainting process modifies the flow of attention outside the inpainting region. The latter usually happens when an inpainting algorithm cannot successfully continue a locally repeating color or structure, from outside the gap, inside it. The discontinuation thus introduced indirectly draws the attention towards the inpainted area, by decreasing the flow of attention drawn by otherwise salient areas and increasing the attention in the neighbourhood area of the inpainting domain.In order to account for out-region artifacting, Ardis et al. [71] proposed another metric, namely the Degree of Noticeability (DN), which takes into consideration both classes of artifacting, being calculated as: IN-REGION(I) = ASV S and OUT-REGION can be computed by using the following equation: OUT-REGION = 1 |Φ| p∈Φ [S (p) -S(p)] 2 (4.30) where S (p) and S(p) are the saliency map values corresponding to a pixel p belonging to the inpainting domain before and after inpainting, respectively. As the authors' suggestion, higher scores for ASV S and DN can be interpreted as an indicator of highly visible artifacts and thus a poor inpainting performance. Although these metrics are correlated well to subjective scores, they needed to be confirmed by further experiments because in the current experiment, only five observers are considered. 4.3.3 GD in and GD out Other two saliency-based metrics have been proposed by Mahalingam [72], resembling the approach presented earlier by Ardis et al. Authors have defined a normalized gaze density measure in the saliency map corresponding to the inpainted and original images and introduced two metrics, GD in and GD out . These metrics show that if there is any change in the saliency maps corresponding to the inpainted and original image, this change is related to the perceptual quality of the inpainting. By comparing the gaze density within and outside the hole region of images inpainted by both the techniques, the perceptual image inpainting quality can be quantitatively analyzed. The gaze density of an image inside and outside the hole is given in equation (4.31) as following: GD in = p∈Ω S (p) and GD out = p∈Φ

  in and GD out = GD out GD unmod out (4.32) where GD unmod in and GD unmod out are gaze density measures of original image before inpainting and calculated similarly to equation (4.31) by replacing S (p) with S(p), where S is the saliency map of the original, unmodified image.

Figure 4 . 8 .

 48 Figure 4.8. An overview scheme of local quality map.

Figure 4 . 9 .

 49 Figure 4.9. An example of corherence term. (a) An image to be inpainted with green mask; The output using algorithm of (b) Criminisi et al. [17] is less coherent than those of Dang's algorithm in (c) [61].

  [START_REF] Agarwala | Interactive digital photomontage[END_REF] where I µ and I G are the arithmetic mean pixel value and the Gaussian blurred version of the original image, respectively. The operation is performed in the CIEL * a * b * color space.

Figure 4 .Figure 4 . 10 .

 4410 Figure 4.10 illustrates an example of coherence and structure maps by pseudo-colored mask images where the red refers to higher value and the blue refers to lower value.

Figure 4 . 11 .

 411 Figure 4.11. Sets of images used for the subjective evaluation. Images (a), (b), (c) are used in the small inpainted regions; In the case of the large inpainted region, images are divided into two sub-group such as images (d), (e), (f) for greedy strategy; and images (g), (h), (i) for gloabl optimization strategy.

Figure 4 . 12 .

 412 Figure 4.12. An example of images presented during the experiment.

Figure 4 .

 4 Figure 4.12 shows an example of such a test group presented during the experiment.

Figure 4 .

 4 Figure 4.13. A subjective judgment based on the web-based experiment.

Figure 4 . 14 .

 414 Figure 4.14. Mean Opinion Score for (a) small inpainted regions; and the large inpainted regions completed with (b) greedy strategy or (c) global optimization strategy.

Figure 4 . 15 .Figure 4 . 16 .

 415416 Figure 4.15. The inpainting results (image 2). (a) The original image; (b) A pseudoinpainted image; The outputs when using the methods of (c) Bertamío et al. [6]; (d) Tschumperlé [12]; (e) Bugeau et al. [86]; (f) Criminisi et al. [17] and (g) Dang et al. [61].

  and 4.18 give an example of restoration in each case. Consequently, twenty restored images are used to evaluate in case of greedy strategy and nine other restored images are used to evaluate in

Figure 4 . 17 .

 417 Figure 4.17. The inpainting results for greedy strategies. (a). Image to be inpainted; The outputs when using the approaches of (b) Criminisi et al. [17]; (c) Wu and Ruan[21]; (d) Zhang and Lin [20]; (e) Dang et al. [61] and (f) Dang et al. [91].

Figure 4 . 18 .

 418 Figure 4.18. The inpainting results for global optimization strategies. (a) Image to be inpainted; The outputs when using the approaches of (b) Wexler et al. [26]; (c) Komodakis [24] and (d) Pritch et al. [27].

Figure 4 . 19 .

 419 Figure 4.19. Performance of the quality metrics in case of large inpainted region for greedy strategy. (a) Pearson correlations (PCC); (b) Spearman correlations (SCC).

Figure 4 . 20 .

 420 Figure 4.20. Performance of the quality metrics in case of large inpainted region for global optimization strategy. (a) Pearson correlations (PCC); (b) Spearman correlations (SCC).

5. 1 .Figure 5 . 1 .

 151 Figure 5.1. An example of very realistic-looking forgeries. The image in (a) is forgery because of illustration in a newspaper [92]; but two edited photos of a wedding album in (b) are not forgery.

Figure 5 . 2 .

 52 Figure 5.2. The difference between inpainting and copy-move problems. (a) inpainted region is copied from many different sources; while (b) a forged region is copied from another isoform.

Figure 3 .

 3 Figure 3.13 illustrates an example of inpainting result in which the inpainted region is filled in by many distinguish small regions. Figure5.2 indicates the differences between these two problems. In this context, the existing copy-move detection techniques often fail to detect the inpainting regions.

Figure 5 . 3 .

 53 Figure 5.3. Common processing pipeline for the copy-move detection.

Figure 5 . 4 .

 54 Figure 5.4. A common illustration of block-based approaches.

Figure 5 . 5 .

 55 Figure 5.5. Basis functions of the Discrete Cosine Transformation with corresponding coefficients.

Figure 5 . 6 .

 56 Figure 5.6. An illustration of PCA dimensionality reduction. (a) A data set given as 3-dimensional points; (b) The three orthogonal Principal Components (PCs) for the data, ordered by variance; (c) The projection of the data set into the first two PCs, discarding the third one.

Figure 5 . 7 .

 57 Figure 5.7. A set of complex Zernike polynomials.

Figure 5 .

 5 Figure 5.8 and these components are computed on Y channel. The detailed implementation can be found in [102]. These characteristics features do not change significantly after some common processing operations such as Gaussian noise, Gaussian bluring, JPEG compression.

Figure 5 . 8 .

 58 Figure 5.8. Four directions for calculation of the last four features in Luo's approach [102].

  [START_REF] Lin | Fast copy-move forgery detection[END_REF]. The 9-dimensional feature vectors are extracted based on the average gray-scale intensities of a block and its subblocks. Firstly, each block is divided into four equal-sized sub-blocks (Figure??). Then, the first dimension is calculated from the average intensity of whole block. The next four dimensions denote the ratios of the average intensities of four sub-blocks to the first dimension. The last four dimensions stand for the differences of the average intensities of the four sub-blocks from the first dimension. Finally, all components of feature vector are normalized to integers ranging in [0, 255]. Although these 9 entities contain duplicated information, they together possess higher capability of resistance against some modifications, such as JPEG compression and Gaussian noise. There is a slight difference with the Popescu's approach in sorting feature vectors. Because elements of feature vectors are integers, it is possible to use the efficient radix sort algorithm to perform lexicographical sorting over those vectors.

Figure 5 . 9 .

 59 Figure 5.9. A block is divided into four equal-size sub-blosks in Lin feature [104].

  Unlike block-based algorithms in which the image is divided into overlapping blocks, keypoint-based methods rely on the identification and selection of high-entropy image regions. Nowadays, local visual features (e.g. SIFT, SURF) have been widely used for image

Figure 5 . 10 .

 510 Figure 5.10. A block is divided into four concentric circles in Wang feature [105].

Figure 5 . 11 .

 511 Figure 5.11. A common illustration of keypoint-based approaches.

Figure 5 . 13 .

 513 Figure 5.13. An illustration of false detection results using keypoint-based method. The images are known untampered but are detected to have duplicated regions

Figure 5 . 14 .

 514 Figure 5.14. An example of an inpainting forgery. (a) The original image; an inpainted image using (b) Wu's approach[START_REF] Wu | Object removal by cross isophotes exemplar-based inpainting[END_REF] and (c) Zhang's approach[START_REF] Zhang | Exemplar-based image inpainting using color distribution analysis[END_REF].

Figure 5 . 15 .

 515 Figure 5.15. The detection using the copy-move forgery detection for inpainting forgery. The results when using the methods of (a) Fridrich et al. [94]; (b) Ryu et al. [101]; (c) Mahdian et al. [99]; (d) Wang et al. [100]; (e) Amerini et al. [108] and (f) Shivakumar et al. [110].

1 .Figure 5 . 16 .

 1516 Figure 5.16. The detection using the copy-move forgery detection for inpainting forgery. The results when using the methods of (a) Fridrich et al. [94]; (b) Ryu et al. [101]; (c) Luo et al. [102]; (d) Bravo et al. [103]; (e) Amerini et al. [108] and (f) Shivakumar et al. [110].

Figure 5 . 18 .

 518 Figure 5.18. An example for each step in our algorithm. (a) original image using Criminisi's method [17]; (b) inpainted image; (c) and (d) mask images before and after filtering patches.

Figure 5 . 19 .

 519 Figure 5.19. Inpainting detection results of our proposal for a set of inpainted images. (a) original images; (b) inpainted images using Criminisi's method [17]; (c) detected masks.

Figure 5 . 20 .

 520 Figure 5.20. Inpainting detection results of our proposal for a set of inpainted images. (a) original images; (b) inpainted images using Criminisi's method[17], Wu's method [20] and Zhang's method [21] (top to bottom) ; (c) detected masks.

  I I and I D denote the inpainted region and detected region, respectively. The operator |Ω| counts the number of pixels in the region, Ω. Alternatively, Recall is used to measure the probability that a corrected region is detected. It is defined as follows: R = |I I ∩ I D | |I I | × 100% (5.3) However, there is a trade-off between Precision and Recall. Greater Precision might decrease Recall and vice versa. To consider both Precision and Recall together, the F 1

  2 and visually shown in Figure 5.20. Where, the first column shows identification of input images with the corresponding sizes in the next column, labelled with Size. Column IA defines the size of original inpainted area respecting to percentage of the whole input image. The columns of P , R and F 1 indicate the values of corresponding metrics. The average rates of Precision, Recall and F 1 are 78.68%, 84.49% and 80.73%, respectively. These values are nearly the same and relativelyhigh. This shows that the detected region is not only correct but also quite complete. On the other hand, the obtained output demonstrates the important ability of the proposed method to detect inpainting forgery in the digital images. It thus confirms that our proposal is efficient for inpainting forgery detection.

Figure 5 . 21 .

 521 Figure 5.21. A chart of performance respect to detection rates.

Contents 6 . 1

 61 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 158 6.2 Future works . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 160

6. 1 .

 1 Conclusioninstead of an exhaustive search. The computational time of implementation has been significantly reduced. Many comparisons and analysis have been performed and discussed.

  Linear interpolation for inpainting . . . . . . . . . . . . . . . . . 15 2.2.2 PDE based inpainting method . . . . . . . . . . . . . . . . . . . 16 2.2.3 Total variation based inpainting method . . . . . . . . . . . . . 18 2.2.4 Vector-valued image regularization with PDEs . . . . . . . . . . 19 2.2.5 DCT induced wavelet regularization for inpainting . . . . . . . 20

	C h a p t e r	2
	Overview of Digital Image Inpainting

• Chapter 6 summarizes the results of the current research and points out several lines of future work. The list of tables, list of figures and bibliography are given at last. "To know that we know what we know, and to know that we do not know what we do not know, that is true knowledge." Contents 2.1 State-of-the-art . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 2.2 Geometry-oriented methods . . . . . . . . . . . . . . . . . . . . . . . . . 15 2.2.1 2.3 Texture-oriented methods . . . . . . . . . . . . . . . . . . . . . . . . . . 21 2.3.1 Greedy strategy . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 2.3.2 Global optimization strategy . . . . . . . . . . . . . . . . . . . . 29 2.4 Hybrid inpainting methods . . . . . . . . . . . . . . . . . . . . . . . . . 36 2.5 Beyond single image inpainting . . . . . . . . . . . . . . . . . . . . . . . 38 2.6 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39

Table 2 .

 2 1. Some typical inpainting methods.

	Year Authors	Group	H-type
	Ogden et al. [9]	Geometry	Small
	Bertalmío et al. [6, 10]	Geometry	Small
	Chan and Shen [5]	Geometry	Small
	Esedoglu and Shen [11]	Geometry	Small
	Tschumperlé [12]	Geometry	Small
	Li et al. [13]	Geometry	Small
	Efros and Leung [14]	Texture	Large
	Efros and Freeman [15]	Texture	Large
	Ashikhmin [16]	Texture	Large
	Criminisi et al. [17]	Texture	Large
	Cheng et al. [18]	Texture	Large
	Sun et al. [19]	Texture	Large
	Wu and Ruan [20]	Texture	Large
	Zhang and Lin [21]	Texture	Large
	Mairal et al. [22]	Texture	Small
	Mobahi et al. [23]	Texture	Small
	Komodakis et al. [24]	Texture	Large
	Le Meur et al. [25]	Texture	Large
	Wexler et al. [26]	Texture	Large
	Pritch et al. [27]	Texture	Large
	Liu and Caselles [28]	Texture	Large
	Bertalmío et al. [29]	Hybrid	Small
	Bugeau and Bertalmío [30]	Hybrid	Small
	Sairam et al. [31]	Hybrid	Small

  Inpainting the lowest resolution image . . . . . . . . . . . . . . 45 3.1.3 Multi-resolution patch for higher resolution image completion . 52 3.1.4 Experimental results . . . . . . . . . . . . . . . . . . . . . . . . 53 3.2 A hybrid approach for high-quality fast image completion . . . . . . . . 60 3.2.1 Offset operator . . . . . . . . . . . . . . . . . . . . . . . . . . . 63

Contents 3.1 A hierarchical approach for image completion . . . . . . . . . . . . . . . 42 3.1.1 Algorithm overview . . . . . . . . . . . . . . . . . . . . . . . . . 43 3.1.2 3.2.2 Data term . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63 3.2.3 Smoothness term . . . . . . . . . . . . . . . . . . . . . . . . . . 64 3.2.4 Offset-map interpolation . . . . . . . . . . . . . . . . . . . . . . 66 3.2.5 Experimental results . . . . . . . . . . . . . . . . . . . . . . . . 66 3.2.6 Performance evaluation . . . . . . . . . . . . . . . . . . . . . . . 70 3.3 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74

Table 3 .

 3

1. Priority of the different regions.

Table 3 .

 3 Criminisi et al. [17], Wu et al.[START_REF] Wu | Object removal by cross isophotes exemplar-based inpainting[END_REF], Zhang et al.[START_REF] Zhang | Exemplar-based image inpainting using color distribution analysis[END_REF] and Cheng et al.[18] for a fair comparison. Table3.2 lists the details of inpainting techniques used in this section.

	2. Tested inpainting algorithms
	Year Authors	Group H-type
	2004 Criminisi et al. [17] Texture	Large
	2005 Cheng et al. [18]	Texture	Large
	2006 Wu and Ruan [20]	Texture	Large
	2011 Zhang and Lin [21] Texture	Large
	Since our proposal belongs to the second group, we selected the methods corresponding
	to the approaches of

Table 3 . 3 .

 33 Selected testing images

	Image	Name	Size	Hole size Type
		boat	300 × 225	10.73%	natural
		horse	300 × 225	9.29%	natural
		wall	256 × 256	14.8%	natural
		angle	300 × 252	5.83%	archaeological
		affresco 726 × 373	3.43%	archaeological

Table 3 . 4 .

 34 .2 are selected for this evaluation. Four input images, commonly used for inpainting evaluation, of size 200 × 200 respectively yokoya, kidstatue, cameraman and student are chosen for the experiments, see Table 3.4. Selected testing images

	Image Name	Size	Hole size Type
	yokoya	200 × 200	6.53%	natural
	kidstatue	200 × 200	19.86%	natural
	cameraman 200 × 200	12.78%	natural
	student	200 × 200	7.8%	natural

Table 3 .

 3 5. Time performance of each stage in percentage (%).

		The lowest resolution, G 3	Higher resolutions
	Image ID	priority	patch	total	G 2	G 1	G 0
		calculation	selection
	yokoya	0.06	0.44	0.60	1.98	6.46	66.50
	cameramen	0.41	0.80	1.22	2.85	19.99	43.33
	kidstatus	0.20	0.78	0.99	5.02	9.57	57.12
	student	0.05	0.44	0.49	5.69	17.45	59.31
	bungee	0.38	1.04	1.42	4.65	15.57	55.42
	angle	0.03	0.37	0.41	3.17	8.02	66.91
	silenus	0.19	0.77	0.96	3.75	7.07	73.48
	boat	0.09	0.99	1.09	1.30	19.01	59.82
	seaman	0.24	1.43	1.68	4.75	24.68	44.90
	AVG	0.18	0.78	0.98	3.68	14.20 58.53

Table 3 .

 3

	Image	yokoya kidstatue cameraman student
	Hole size	6.53%	19.86%	12.78%	7.8%
	Criminisi et al. [17] 3.22	10.09	5.75	4.74
	Wu and Ruan [20]	3.64	10.29	6.05	5.98
	Cheng et al. [18]	3.58	11.60	6.91	5.64
	Zhang and Lin [21]	38.38	251.74	111.84	59.52
	Our proposal	3.71	4.53	3.29	3.84
	Secondly, the comparison is extended to other inpainting methods corresponding to
	algorithms proposed by Criminisi et al. [17] representing greedy strategy; Dang et al. [61]

[START_REF] Bertalmío | Image inpainting[END_REF]

. Computational time (in seconds) in comparison with the state-of-the-art methods of the second group

Table 3 .

 3 7. Computational time (in second) in comparison with both greedy and global optimization strategies.

	Image	bungee	angle	silenus	boat	seaman	pumpkin
	Size	206 × 308 300 × 252 256 × 480 300 × 225 300 × 218 473 × 332
	Hole size	12.6%	5.83%	7.74%	10.73%	14.87%	5.1%
	Criminisi et al. [17]	16.30	8.20	38.29	24.54	27.31	28.98
	Dang et al. [27]	15.92	16.36	63.18	50.18	55.16	54.57
	Pritch et al. [61]	35.39	13.24	57.68	21.18	15.50	37.35
	Our proposal	3.32	5.81	7.53	7.25	5.97	6.31

Table 4 .

 4 1. The selected IQA and IIQA metrics.

	Year Authors	Name	Type Reference
	-	-	MSE and PSNR	IQA	Full
	1993 Daly [64]	VDP	IQA	Full
	2004 Wang et al. [65]	SSIM	IQA	Full
	2006 Bonnier et al. [68]	SSIM IP T	IQA	Full
	2006 Sheikh et al. [66]	VIF	IQA	Full
	2007 Chandler and Hemami [69]	VSNR	IQA	Full
	2008 Wang et al. [70]	PWIIQ	IIQA	Full
	2009 Ardis and Singhal [71]	ASVS and DN	IIQA	No
	2010 Mahalingam and Cheung [72]	GD in and GD out	IIQA	No
	2012 Oncu et al. [73]	BorSal and StructBorSal IIQA	Full

Table 4 . 2 .

 42 The parameters of images considered for inpainting algorithm evaluation.

	Image Name Resolution	Size	Hole size H-type
	soldier	96	142 × 179	4.52%	Small
	square	72	422 × 295	1.98%	Small
	church	72	300 × 200	3.6%	Small
	boat	96	300 × 225	10.73%	Large
	seaman	96	300 × 218	14.87%	Large
	horse	96	300 × 225	14.47%	Large
	bungee	72	206 × 308	12.60%	Large
	lady	72	375 × 500	11.55%	Large
	house	72	400 × 265	21.21%	Large
	pumpkin	96	372 × 332	5.1%	Large

Table 4 .

 4 4. Mean opinion score (MOS).

	Score Quality	Impairment
	1	Unacceptable Too many artifacts and very annoying to viewers.
	2	Bad	Many artifacts are easy to detect.
	3	Acceptable	Some artifacts but not affecting image interpretation.
	4	Good	A few artifacts but difficult to detect.
	5	Perfect	Almost no artifact.

Table 4 .

 4 5. The PCC and SCC indexes in case of small inpainting regions.

			PCC			SCC
	Image ID	1	2	3	1	2	3
	M SE	0.1949 -0.5413 -0.6301 0.50 -0.65 -0.50
	P SN R	-0.1733 0.5508 0.5385 -0.50 0.35 0.50
	V DP	-0.8640 -0.6179 -0.4814 -0.60 -0.65 0.10
	M SSIM	0.4745 0.5836 0.1360 0.70 0.05 -0.25
	M SSIM IP T -0.5557 0.5540 -0.9838 -0.50 0.05 -0.90
	V IF	-0.0998 0.6222 0.2167 -0.35 0.35 0.50
	V SN R	-0.1678 0.7706 -0.9416 -0.30 0.55 -0.90
	P W IIQ	0.9220 -0.0918 0.9830 0.70 0.25 0.90
	ASV S	0.8614 0.9235 0.3103 0.60 0.85 0.50
	DN	0.9157 0.8046 0.6971 0.85 0.80 0.70

Table 4 .

 4 [START_REF] Bertalmío | Image inpainting[END_REF]. The PCC and SCC indexes for greedy strategies.

			PCC					SCC
	Image ID	4	5	6	7	4	5	6	7
	ASV S	0.1946 -0.4651 -0.7154 0.7891 0.1 -0.8 0.8 -0.55
	DN	0.6870 -0.4790 -0.8379 0.8793 -0.9 -0.9 0.9 -0.65
	GD in	-0.6571 0.7918 -0.9132 0.3815 0.5 0.4 0.9 -0.25
	GD out	0.0111 -0.9129 0.3777 -0.4756	0	-0.4 -0.1 0.65
	Q 1	0.6339 0.6250 0.7516 0.7185 0.7 0.6 0.9 0.65
	Q 2	0.7807 0.4999 0.1497 0.5429	1	0.6 0.6 0.65

Table 4 .

 4 [START_REF] Guillemot | Image inpainting: Overview and recent advances[END_REF]. The PCC and SCC indexes for global optimization strategies.

			PCC			SCC
	Image ID	8	9	10	8	9	10
	ASV S	0.7135 0.7135 0.4242 -0.5 -1 -0.5
	DN	0.9073 0.9921 -0.9885 -1	-1	1
	GD in	-0.7203 0.9954 0.9989	-1	-1	-1
	GD out	0.2970 -0.8869 -0.8638 -1 0.5 0.5
	Q 1	0.5140 0.8446 0.9894 0.5	1	1
	Q 2	0.4941 0.8515 0.9989	1	1	1
	from this toolkit. The output results are also subjectively evaluated and M OS are available
	for studying the performance of the considered metrics.
	The P CC and SCC values given in Tables 4.6 and 4.7 clearly confirm the efficiency

  Contents 5.1 Why could inpainting be considered as forgery tool? . . . . . . . . . . . 126 5.2 Overview of forgery . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 130 5.2.1 Block-based approaches . . . . . . . . . . . . . . . . . . . . . . 133 5.2.2 Keypoint-based approaches . . . . . . . . . . . . . . . . . . . . 139 5.3 A proposal for inpainting detection . . . . . . . . . . . . . . . . . . . . 142 5.4 Experimental results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 148 5.4.1 Test for inpainting forgery . . . . . . . . . . . . . . . . . . . . . 149 5.4.2 Performance evaluation . . . . . . . . . . . . . . . . . . . . . . . 150 5.5 Summary and conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . 154

	5.1 Why could inpainting be considered as forgery
	tool?

Table 5 .

 5 2. Detection rates for inpainting forgery. Summary and conclusion inpainted regions by similar patches and located it by the centroid connected component.

	Image ID Size (px) IA (%) P (%) R (%) F 1 (%)
	1	300 × 255	10.73	87.0401 86.85	86.94
	2	300 × 255	10.73	90.80	98.47	94.48
	3	300 × 255	10.73	92.28	98.77	95.41
	4	206 × 308	12.60	78.02	76.93	77.47
	5	206 × 308	12.60	75.90	85.58	80.45
	6	206 × 308	12.60	79.10	65.09	74.87
	7	300 × 255	14.47	82.51	91.93	86.97
	8	300 × 255	14.47	83.80	80.08	81.90
	9	300 × 255	14.47	92.34	77.80	84.45
	10	300 × 218	14.87	58.11	84.14	68.74
	11	300 × 218	14.87	57.50	80.49	67.08
	12	300 × 218	14.87	50.71	82.79	62.89
	13	480 × 320	12.97	96.59	98.52	97.55
	14	481 × 321	12.56	58.91	91.43	71.66
	15	480 × 320	17.19	96.57	68.43	80.10
	Average			78.68	84.49	80.73

Acknowledgments

C h a p t e r

3

A Hierarchical Approach for High-Quality Fast Image Completion "Nothing takes place in the world whose meaning is not that of some maximum or minimum."

C h a p t e r 4 Inpainted Image Quality Assessment "I have found a very great number of exceedingly beautiful theorems."

been selected for evaluation. For the large inpainted regions, eight inpaintig algorithms including both greedy and global optimization strategies are applied for restoring. All algorithms were programmed with C/C++ programming language and implemented on the same computer with an Intel Core i5, 2.80 GHz CPU and 4GB RAM. The Table 4.3 lists these algorithms, where the Year of publication, Authors' name are provide in first two columns; Type column indicates the category the algorithm belongs to, depending on the approach it takes; and H-type, as mentioned before, shorts for 'Hole type' determining for which type algorithm provides the best results.

Global optimization Large

A panel of forty-five observers, having a normal acuity and no color blindness, participated to the subjective experiment. The observers were given clear instructions, focused on the overall quality rating of the inpainted images. Accordingly, before commencing the

If β 2jk is between 2 and 4, we can consider that the distribution is normal. In order, to compute P i and Q i values that will allow to take the final decision regarding the outliers, the observations u ijk for each observer i, each degradation j, and each image k, is compared thanks to a combination of the MOS and the associated standard deviation. The different steps of the algorithm are summarized below, while the reader is referred to [START_REF] Bt | Methodology for the subjective assessment of the quality of television pictures[END_REF] for more details:

Algorithm 4.1. Algorithm for outliers rejection. where J is the total number of degradations and K is the total number of images.

Consequently, from a total of 38, results of 11 participants were rejected and only 27 considered for further evaluation. A demographic distribution of the observers is shown in Figure 4.13, while the Figure 4.14 shows the charts of MOS calculated from the raw data. number of dimension is undefined or not mentioned in the publication. Some results of this approach can be found in [START_REF] Ryu | Detection of copy-rotate-move forgery using zernike moments[END_REF].

The last frequency-based approach has been introduced by Bayram et al. [START_REF] Bayram | An efficient and robust method for detecting copy-move forgery[END_REF]. The authors recommended the use of the FMT for generating feature vectors. Essentially, these features would not be only robust to lossy JPEG compression, blurring, or noise addition, but also known to be scaling and translation invariant but sensitive to rotation.

Furthermore, the counting boom filters are used, instead of lexicographic sorting, to reduce the detection time. Some outputs of this approach are available in [START_REF] Bayram | An efficient and robust method for detecting copy-move forgery[END_REF].

Dimensionality reduction-based methods

The main idea of the methods in this group is to reduce the number of dimensionality of feature vector which can significantly affect the performance of similar block search. Here, we recall three typical techniques for converting and reducing the number of correlated dimensionality, such as Principal Component Analysis (PCA), Singular Value Decomposition (SVD) and Kernel Principal Component Analysis (KPCA).

In [START_REF] Popescu | Exposing digital forgeries by detecting duplicated image regions[END_REF], Popescu et al. proposed to perform PCA to derive an alternative representation of the blocks instead of quantized DCT coefficients. For this purpose, a new linear basis was obtained by finding the eigenvectors of the covariance matrix and the projection of each block onto these basis vectors with higher eigenvalues was used as new representation to reduce dimensionality. In their paper, the method was shown to be robust to compression up to JPEG quality level 50 and to additive noise with SNR 36dB and 29dB, but not to re-sampling (scaling, rotation).

Kang et al. [START_REF] Kang | Identifying tampered regions using singular value decomposition in digital image forensics[END_REF] computed the singular values of a reduced rank approximation (SVD).

In the proposed passive techniques, SVD served to produce algebraic and geometric in-Besides achieving promising performance in detecting sophisticated forgeries with duplicated regions, the keypoint-based methods may have a limitation for some cases. One example is shown as the Figure 5.12 where an obvious duplicated square cannot be detected by this kind of method. The reason is the SIFT or SURF algorithms cannot find reliable keypoints in regions with little visual structures. Similarly, as smaller regions have fewer keypoints, they are also hard to detect. Another case of false detection is illustrated in the Figure 5.13 where the input images have intrinsically identical areas that cannot be differentiated from intentionally inserted duplicated regions. Thus, as the future work, these methods could be improved by incorporating other features or histograms of oriented gradients, or combining with other detection schemes based on intrinsic signal statistics/patterns to provide strong cues when image keypoints and features are insufficient.

A proposal for inpainting detection

In this work, we focus on detecting a specific type of digital image forgery, namely image inpainting. The intent of this operation is to modify the content of an image in the most visually plausible way. This yields to what we call inpainting forgery. This technique is more sophisticated and complex than copy-move forgery because the source of copied information could be non-continuous. This means that an object may be filled by a set of multiple small parts located at different places in the same image and not a single

A selection of values for these parameters is given in the next chapter depending on the patch size. A further discussion of parameter influence is being studied and will be published in the future.

Besides, another big challenge in this step is related to minimizing the computational cost. It could take hours or even days to search similar patches satisfying equation (5.1) by brute force procedure. This is infeasible and impractical. In our algorithm, we used a very effective algorithm, the kd -tree [START_REF] Beis | Shape indexing using approximate nearest-neighbour search in high-dimensional spaces[END_REF], to get approximate nearest neighbors. Typically, the Euclidean distance is used as a similarity measure as in the inpainting methods [17,[START_REF] Wu | Object removal by cross isophotes exemplar-based inpainting[END_REF][START_REF] Zhang | Exemplar-based image inpainting using color distribution analysis[END_REF].

In prior work [START_REF] Christlein | An evaluation of popular copy-move forgery detection approaches[END_REF], it has been shown that the use of kd -tree matching leads, in general, to better results than lexicographic sorting as in [START_REF] Fridrich | Detection of copy move forgery in digital images[END_REF][START_REF] Popescu | Exposing digital forgeries by detecting duplicated image regions[END_REF].

Mask generation :

A binary mask, in which pixels belonging to candidate patches are labelled as "1" and the others as "0", is generated for detecting inpainted regions. This mask is a collection of connected regions composed of pixels labelled "1" on a background of pixels labelled "0". In our experiment, we assume that only one region has been restored in the input image. In such a way, we evaluated only the largest connected area. Logically, this region is characterized by its centroid. The centroid of the largest connected region, as a result, is located based on position of all pixels belonging to this region.

Patch filtering :

A filtering scheme is applied to reduce the false detected patches.

Indeed, for each couple of matches, one of the two patches is an original and the other is the inpainted version that should be marked as forged patch. The filtering is implemented for all matches based on their distance to the calculated centroid. The patch closer to the centroid is kept and the remaining patch is discarded. The morphological operation, such as opening, could be applied to connect nearby regions. Finally, the largest connected region is considered as the latest output.

The detail scheme of our method is shown in Figure 5.17. As a result, an example for each step is illustrated in Figure 5.18. More experimental results will be presented in the next section.

is dependent on each image's characteristics and especially on the thresholds. Please note that the computational time of an image containing large uniform or very similar areas is higher. This is caused by the fact that the most time consumption is associated with the analysis of patch similarities and neighborhoods. Logically, having a high number of similar blocks causes expensive computation. The hierarchical structure, kd -tree, allows us to make efficient range queries in multidimensional data. Consequently, the proposed algorithm has a low computational cost in most cases. The chart 5.22 shows the time consumption in milisecond (ms) for the set of test images.

Summary and conclusion

In this chapter, a notation of digital forgery was introduced. Within this field, copy-move forgery detection is probably the most actively investigated subtopic and has a particularly close connection with our problem, digital inpainting forgery. The overview of common copy-move forgery detection has been summarized and the main difference between these two problems, copy-move and inpainting forgery detections, has been indicated. Generally, the inpainting forgery detection is more difficult and sophisticated.

In this study we addressed the problem of inpainting forgery detection by proposing a novel approach relying on the behavior of most known inpainting algorithms. Therefore, based on the analysis of many exemplar-based inpainting methods, we have predicted the