Image restoration using 2D autoregressive texture model and structure curve construction

Статья опубликована в журнале «Mobile Multimedia/Image Processing, Security, and Applications 2015» №9497 21.05.2015

V.V. Voronin^*a, V.I. Marchuk^a, S.P. Petrosov^a, I. Svirin^b, S. Agaian^c and K. Egiazarian^d

^aDept. of Radio-Electronics Systems, Don State Technical University, Shakhty,  Russian Federation
^bCJSC Nordavind, Moscov, Russian Federation
^cDept. of Electrical & Computer Engineering, University of Texas at San Antonio, San Antonio
^dDept. of Signal Processing, Tampere University of Technology, Tampere, Finland

ABSTRACT

In this paper an image inpainting approach based on the construction of a composite curve for the restoration of the edges of objects in an image using the concepts of parametric and geometric continuity is presented. It is shown that this approach allows to restore the curved edges and provide more flexibility for curve design in damaged image by interpolating the boundaries of objects by cubic splines. After edge restoration stage, a texture restoration using 2D autoregressive texture model is carried out. The image intensity is locally modeled by a first spatial autoregressive  model with support in a strongly causal prediction region on the plane. Model parameters are estimated by Yule-Walker method. Several examples considered in this paper show the effectiveness of the proposed approach for large objects removal as well as recovery of small regions on several test images.

Keywords: image inpainting, edge reconstruction, spline interpolation, texture synthesis, autoregressive model.

1. INTRODUCTION

Image inpainting or image reconstruction is an important topic in image processing. The main goal of image inpainting is to restore missing area of “empty” pixels using an information from the outside of the damaged domain. Digital inpainting serves a wide range of applications, such as removing text and logos from still images or videos, reconstructing scans of deteriorated images by removing scratches or stains, or creating artistic effects. This problem is also especially valuable in computer vision systems for image editing and recovery of missing blocks in image coding.

Most of image reconstruction methods can be classified into the following groups based on geometry [1-6], statistics [6-9], sparsity [10-12], exemplars [13-17] and edges [18-21] methods. The following models of images are used in image inpainting: bounded variation image model, local inpainting, total variation models, curvature-driven diffusions model and Markov random fields model. All these models are used in the methods which compute an optimal solution based on partial differential equations (PDE). In these methods, also called as diffusion-based, missing pixels are restored by a smooth propagation of information from the neighborhood of the holes by a diffusion process [1-6]. These techniques often introduces a blur in sharp transitions in image and image contours, and need a priori information to select parameters of the method. They are suitable for removal of scratches and small defects on the structure of images, but often fail to restore the texture image and curved contours.

A second group of image inpainting methods uses the frequency domain processing and sparse representation model. It should be noted that these methods often tend to blur textures and structures in a recovery of large areas of missing pixels. These iterative methods are also highly computationally expensive.

A third group of image inpainting methods is based on non-parametric sampling model and texture synthesis. Criminisi et al. [13] have proposed a patch-based method based on searching for similar patches and coping them from the true image. These methods are limited to inpaint linear structures and often fail to recover curvy boundary edges.

Recently there have been developed various image inpainting methods based on combinational structure and texture propagation. These techniques are more suitable for structure and texture reconstruction, but requires significant computational time to inpaint large missing regions.

The main drawbacks of the known methods come from the fact that the most of them are unable to recover the curved edges and applicable only for scratches and small defects removal. It should be also noted that these methods often blur image in the recovery of large areas with missing pixels. Most of these methods are computationally very demanding and inappropriate for implementation on modern mobile platforms.
In this paper we introduce a novel algorithm for automatic image inpainting based on 2D autoregressive texture model, exemplar-based and structure curve construction. An approach of the construction of a composite curve for the restoration of the edges of objects in an image using the concepts of parametric and geometric continuity is presented. It is shown that this approach allows to restore the curved edges and provide more flexibility for curve design in damaged image by interpolating the boundaries of objects by cubic splines.

The rest of the paper is organized as follows. Section 2 describes the proposed method. This is followed by a description of the basic idea of the proposed image inpainting approach based on texture model and structure curve construction. Section 3 presents key steps of the proposed algorithm. Experimental results are given in Section 4, followed by the Conclusion section.

2. THE PROPOSED METHOD

2.1. Image model

In this work we use geometric image model [21]. Any image can be divided into several areas such as texture regions, non texture and edges on the local geometric features. In an image there are texture areas, separated by boundaries, which may have a thickness of several pixels and have a different spatial configuration. In this case, we assume that the boundaries are smooth in the sense that they can be approximated by polynomials of low orders. Thus, the region with a missing pixel values ​​may be surrounded by one or more regions, separated by edges.

A discrete image defined on a IxJ rectangular grid is denote . When each element  is a random variable,  is called a discrete random field. A simplified mathematical model of the original image can be represented as follows: , where  are the true image pixels;  is a binary mask of the distorted values of pixels (1 - corresponds to the missing pixels, 0 - corresponds to the true pixels);  are missing pixels; I is the number of rows, and J is the number of columns.

Figure 1 shows the image model, where the region Y is schematically presented in the form of three sub-regions,  representing several types of texture regions,  are  the boundaries of the image with a first texture,  are the boundaries of the image with a second texture, R are missing pixels intersecting with the boundaries  и .

Figure 1. The image model

2.2. The proposed method

In [21] we have proposed the algorithm which allows to restore both large and small regions with missing pixel values with a high accuracy. This is achieved by a separate reconstruction of the structure and texture regions in images. For each class of regions we apply an approach that provides the best possible result. This algorithm has some disadvantages. First, a limitation of segmentation based of a structure tensor, which is particularly manifested in the textures with similar statistical characteristics. Second, searching patches in the texture restoration requires significant computational complexity to restore large texture areas. The exemplar-based methods use a non-parametric sampling model and texture synthesis. Often an image has not enough patches to copy from because the patch size is large or the mask is placed on a singular location on the image where cannot be found similar patches. The problem of choosing similar exemplar using only part of patch is a common one for all exemplar-based inpainting methods. We will tackle this problem by first stage restoration using AR model for prediction lost pixels in the patch.

The purpose of this work is to modify our previous algorithm in order to overcome all above mentioned drawbacks. We introduce a novel algorithm for automatic image inpainting based on 2D autoregressive texture model and structure curve construction. In this case any image can be divided into several areas such as texture regions and edges on the local geometric features and different spatial configuration. An image inpainting approach based on the construction of a composite curve for the restoration of the edges of objects in an image using the concepts of parametric and geometric continuity is presented. It is shown that this approach allows to restore the curved edges and provide more flexibility for curve design in damaged image by interpolating the boundaries of objects by cubic splines. After edge restoration stage, a texture restoration using 2D autoregressive texture model and exemplar-based method are carried out. In this paper we propose an algorithm to represent and reproduce texture regions based on the estimation of spatial autoregressive processes. The image intensity is locally modeled by a first spatial autoregressive model with support in a strongly causal prediction region on the plane. Model parameters are estimated by Yule-Walker method.

2.3. Segmentation and structure curve construction

One of the most important and ubiquitous tasks in image analysis is segmentation. This is a critical intermediate step in all high level object-recognition tasks. In this paper we used a method for segmenting images that was developed by Chan and Vese in [22]. This is a powerful, flexible method that can successfully segment many types of images, including some that would be difficult or impossible to segment with classical thresholding or gradient-based methods. The Chan-Vese algorithm is an example of a geometric active contour model. Such models begin with a contour in the image plane defining an initial segmentation, and then we evolve this contour according to some evolution equation. The goal is to evolve the contour in such a way that it stops on the boundaries of the foreground region. There are various ways to define the evolution equation; for example, the contour might move with a velocity that depends on the local curvature at a given point or the image gradient at that point.

However, CV model still has some intrinsic limitations. First, CV model generally works for images with intensity homogeneity since it assumes that the intensities in each region always maintain constant. Thus, it often leads to poor segmentation results for images with intensity inhomogeneity due to wrong movement of evolving curves guided by global image information. Second, the segmentation of CV model is usually dependent on the placement of the initial contour, especially for the complicated images. Sometimes, the different results will be obtained on the same image by using different initial contours. Thus, the placement of initial contour is still an important issue for CV model to get successful segmentation in complicated images. To solve the limitations of CV model, many efficient implementation schemes have been proposed [23]. For example, in [23], Vese and Chan extended their original model in [22] by using a multiphase level set formulation.

The Chan–Vese (CV) model is an alternative solution to the Mumford–Shah problem which solves the minimization of by minimizing the following energy functional:

, (1)

where  and  are positive constant, usually fixing  and  are the intensity averages of  inside C and outside C, respectively.

For CV model using the intensity average only, texture image segmentation is another difficult issue since intensity averages cannot represent the texture information inside and outside the target objects. In many texture images, due to the difference of the intensity averages of neighboring textures, the small textures in objects will be segmented while the desirable whole objects will be not separated. Therefore, other information should be introduced for texture image segmentation. Chan and Vese suggested using texture information or features extracted from the original image, such as the curvature or the orientation of level sets, to overcome the difficulty [22].

In Figure 2 examples of image segmentation using CV methods for different images are given.

a)	b)	c)

d)	e)	f)

Figure 2. Segmentation of the test images

The first step is to find a correspondence between the boundaries that are crossing regions with missing pixels . In Fig. 3a an example of segmenting  into three clusters (₁ - the first cluster, ₃ - the second cluster, ₃ и ₄ - the third cluster) is shown. The pixels around the damaged image regions are clustered using boundaries, which allow to define the correspondence between the pixels from different patches.
In the next step of the algorithm we analyze the edges  (Fig. 3b) crossing the area with a missing pixels Rand their correlation to the same boundary. For example, in Figure 3b,  are parts of the first boundary   and are parts of the second boundary .

For the cubic spline interpolation of each of the pairs of parts of the curves the concepts of parametric and geometric continuity are used. For the resulting pairs of the points P_k and P_l  on the edges in the true image and non-zero tangent vectors Q_k and Q_l, the cubic Hermite curve is determined with the vector equation in following form [21]:

a)	b)

Figure 3. Edges detection and analysis

A matrix form of parametric equations describing the elementary cubic Hermite curve is given below:

where M is a basis matrix of the cubic Hermite curve, G is a geometric matrix.

For a recovery procedure of edges on the basis of spline interpolation, see in more details [21]. In Figure 4 examples of structure curve construction are given.

a)	b)

Figure 4. Examples of structure curve construction

2.4. Texture restoration

The Fast Marching method is used in order to select a restored pixel in the area R, based on the solution of Eikonal equation  in the R and T=0 on the border , where the solution of the equation T is the distance map of  pixels  to the boundary  [24]. Thus, the selected pixel is the closest pixel to the boundary . After the restoration of the pixel value, the boundary changes, the values T ​​are recalculated, and again a pixel to be restored is selected.

The texture restoration algorithm is a modification of the example-based image inpainting algorithm proposed by Criminisi et al. [13]. The main drawbacks of EBM include: visible boundaries on the reconstructed image between similar patches; an incorrect restoration in absence of similar blocks; a dependence of reconstruction error on a block size.

One of the major problems in original inpainting method is a process of searching the patch with the maximum similarity to a selected patch using mean squared error metric. In Figure 5 we draw an example when the patch is closer to the patch (in mean squared sense)  than . As a result, the algorithm will produce visually poor result (the metric defined only for the true pixel in ). Thus, the criterion to search the best match using only part of patch may lead for some images to uncorrected reconstruction since a searching method using small part of the patches.

Figure 5. The incorrect restoration

The purpose of this work is to modify an exemplar-based method in order to overcome above mentioned drawbacks.

The pixels belonging to the boundary of the recovery region will be denoted by , where: .
At the first step of the algorithm, for each pixel boundary  we choose a square block  in order to find the most similar patch. In most cases in such block many pixels are absent what leads to significant error in searching a similar patch. We will tackle this problem by first stage restoration using AR model for prediction lost pixels in the patch.

Most of the images of interest, for example, the images of cultivated fields and concentration of population are naturally rich in texture, level of  gray, etc. During  the  past  decades,  image  representation  and  image texture  recovery  have  been  important  and  challenging topic. The spatial autoregressive model (2D-AR model) has been  extensively  used  to  represent  images  [25, 26].

The  2D-AR  model  does  not  require  a  large  number  of  parameters  to represent  different  real  scenarios  [27]. In particular, the first-order 2D-AR model is able to represent a wide range of  texture  images,  as  is  shown  in  Figure 6.

We represent a patch as 2D Random fIeld [28]:

(2)

where  and  denotes, respectively the autoregressive and moving average parameters with , and  denotes a sequence of distributed centered random variables with variance .
Similarly if the process is called spatial autoregressive random field, and it is defined as:

(3)

In case first-order AR model  and the model is of the form:

(4)

For finite order AR model the parameters can be estimated by using a 2D extension of the Yule-Walker equations [29].

Figure 6. Synthesized textures

After a texture restoration using 2D autoregressive texture model the exemplar-based method are carried out for every . On the true image S we find patch , for which the Euclidean distance is minimal (Fig. 7): (5)

The pixels in a missing area R is restored by copying the corresponding pixels of the block  found within the restored boundaries.

Figure 7. Texture restoration

3. ALGORITHM

We summarize the algorithm in the following scheme (Fig. 8).

1. Segmentation using Chan–Vese (CV) model

The image around missing area in our scheme is segmented by the Chan–Vese (CV) model which solves the minimization of the energy functional.

2. Edges analysis and restoration using cubic splines

For the cubic spline interpolation of each of the pairs of parts of the curves the concepts of parametric and geometric continuity are used. For the resulting pairs of points P_k and P_l   on the edge in the true image and non-zero tangent vectors Q_k and Q_l,, the cubic Hermite curve is determined.

3. The choice of the boundary pixel by fast marching method

The fast marching method is used in order to select a restored pixel in the area R, based on the solution of Eikonal equation  in  R and T=0 on the border , where the solution of the equation T is the distance map of  pixels  to the boundary .

4. Texture restoration using 2D autoregressive texture model

After edge restoration stage, a patch  restoration using 2D autoregressive texture model is carried out. The image intensity is locally modeled by a first spatial autoregressive  model with support in a strongly causal prediction region on the plane.

5. Modified exemplar-based method

The texture in our scheme is restored by an exemplar-based method. Around the pixel P selected by fast marching method, a patch  is defined. In the next step, on the true image S the patches  are found for which the Euclidean distance is minimal.

Figure 8. The proposed inpainting algorithm

4. EXPERIMENTAL RESULTS

The effectiveness of the presented scheme is verified on the test images with missing pixels, which are on the borders with the intensity changes in brightness. For evaluation purposes we use database of 100 images. After applying the missing mask, all images have been inpainted by four different methods. In Figures 9-10 examples of image restoration (a - the original image, b - the image with a missing pixels, c - the image reconstructed by the Navier-Stockes [1], d - the image reconstructed by the Telea [30], e - the image reconstructed by the EBM [13], f - the image reconstructed by the proposed method) are shown.

a)	b)	c)

d)	e)	f)

Figure 9. Examples of image restoration

a)	b)	c)

d)	e)	f)

Figure 10. Examples of image restoration

A main feature of the test images is the fact that the regions with missing pixels are located at the intersection of the curve boundaries that need to be extrapolated. The test images have several texture and structure regions with different geometrical characteristics. The TM and Navier-Stockes method blurs same regions and the EBM is fail in restoration in the absence of similar blocks. The results show that the proposed method can correctly restore the structure and texture regions. It's worth noting that the method does not smear during the restoration of large areas of missing pixels.

To compare the reconstruction images objective quality criteria  have been used. Table 1 shows numerical comparison of methods, in terms of quality metric . It is worth noting that the error values confirm the visual analysis. The proposed method provides smaller reconstruction errors, on average 90% less than the processing of other techniques.
 
Table 1. Comparison of RMSE for test images.

Navier-Stockes [1]	Telea [30]	EBM [13]	Proposed method
0,1239	0,1232	0,1014	0,0654

5. CONCLUSION

The paper presents an image inpainting algorithm based on the texture and structure reconstruction of images. This is achieved due to a separate reconstruction of a composite curve for the restoration of the edges of objects in an image and texture synthesis using 2D autoregressive texture model. The image intensity is locally modeled by a first spatial autoregressive model with support in a strongly causal prediction region on the plane. Several examples presented in this paper demonstrate the effectiveness of the algorithm in restoration of different areas of the test images having different geometrical characteristics.

6. ACKNOWLEGEMENT

This work was supported by Russian Ministry of  Education and Science in frame of the Federal Program "Research and development on priority directions of scientific-technological complex of Russian Federation in 2014-2020" (contract №14.576.21.0080).

REFERENCES

1. Bertalmio, M., Bertozzi, A., Sapiro, G., "Navier-Stokes, fluid dynamics, and image and video inpainting," Hawaii: Proc. IEEE Computer Vision and Pattern Recognition (CVPR), pp. 213-226 (2001).
2. Chan, T.F., Shen, J., "Mathematical models of local non-texture inpaintings," SIAM J. Appl. Math, vol. 62(3), pp. 1019-1043 (2002).
3. Perez, P., "Markov random fields and images," CWI Quarterly, vol. 11, no. 4, pp. 413-437 (1998).
4. Perona, P., Malik, J., "Scale-space and edge detection using anisotropic diffusion," IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 12, pp. 629-639 (1990).
5. Mumford, D., Shah, J., "Optimal approximations by piecewise smooth functions and associated variational problems," Commun. Pure Appl. Math, vol. 42, pp. 577-685 (1989).
6. Ballester, C, Bertalmio, M., Caselles, V., Sapiro, G., Verdera,  J., "Filling-in by joint interpolation of vector fields and gray levers," IEEE Trans. On Image Processing, vol. 10, pp. 1200-1211 (2001).
7. Bertalmio, M., Sapiro, G., Caselles, V., Ballester, C., "Image inpainting," Computer Graphics Proceedings, K. Akeley, Ed. ACM Press, ACM SIGGRAPH, Addison Wesley Longman, pp. 417-424 (2000).
8. Shirani, S.,  Kossentini, F., Ward, R., "Reconstruction of baseline JPEG coded images in error prone environments,"  IEEE Trans. Image Process, vol. 9(7), pp. 1292-1299 (2000).
9. Guleryuz,  O.G. , "Nonlinear approximation based image recovery using adaptive sparse reconstructions and iterated denoising," Part I: theory IEEE transactions on image processing, vol. 15(3), (2006).
10. Mairal, J., Elad, M. and Sapiro, G., "Sparse representation for color image restoration," IEEE Trans. Image Processing, vol. 17, pp. 53-69 (2008).
11. Fadili, M., Starck,  J.-L. and Murtagh, F., "Inpainting and zooming using sparse representations," Computer Journal, vol. 52(1), pp. 64-79 (2009).
12. Zongben, Xu, Jian, Sun, "Image inpainting by patch propagation using patch sparsity," IEEE transactions on image processing, vol. 19(5), pp. 78-88 (2010).
13. Criminisi, A., Perez, P., Toyama, K., "Region filling and object removal by exemplar-based image inpainting," IEEE Trans. Image Process, vol. 13(9), pp. 28-34 (2004).
14. Aujol, J.-F., Ladjal, S. and Masnou, S., "Exemplar-based inpainting from a variational point of view," SIAM J. Math. Anal., vol. 44, pp. 1246–1285 (2010).
15. Ružić, T., and Pižurica, A., "Texture and color descriptors as a tool for context-aware patch-based image inpainting," in Proc.SPIE Electronic Imaging, vol. 8295 (2012).
16. Voronin, V.V., Marchuk, V.I. and Egiazarian, K.O., "Images reconstruction using modified exemplar based method," Proceedings of SPIE, vol. 7870 (2011).
17. Bugeau, A. and Bertalmio, M., "Combining texture synthesis and diffusion for image inpainting," in International Conference on Computer Vision Theory and Applications, vol. 123-132 (2009).
18. Cao, F.,  Gousseau, Y., Masnou, S.,  Pérez, P., "Geometrically Guided Exemplar-Based Inpainting", SIAM J. Imaging Sci., vol. 4(4), pp. 1143–1179 (2011).
19. Bertalmio, M., Vese, L., Sapiro, G., Osher, S., "Simultaneous texture and structure image inpainting," Proceedings of the International Conference on Computer Vision and Pattern Recognition, pp. 707-712 (2003).
20. Barnes, C., Shechtman, E., Finkelstein, A. and Goldman, D.B., "Patch Match: A Randomized Correspondence Algorithm for Structural Image Editing," ACM Transactions on Graphics (Proc. SIGGRAPH), (2009).
21. Voronin, V., Marchuk, V., Sherstobitov, A. and Egiazarian, K., "Image inpainting using cubic spline-based edge reconstruction," Proceedings of SPIE, vol. 8295 (2012).
22. Chan, T. F., & Vese, L.A., "Active contours without edges," IEEE Transactions on Image Processing, vol.10(2), pp. 266‐277 (2001).
23. Chan, T. F., Vese, L.A., "A Multiphase level set framework for image segmentation using the Mumford and Shah model," International Journal of Computer Vision, vol. 50(3), pp. 271–293, (2002).
24. Sethian, J.A., "Level Set Methods and Fast Marching Methods, Second edition," Cambridge, UK: Cambridge Univ. Press (1999).
25. Bennet, J. and Khotanzad, A., "Maximum likelihood estimation methods for multispectral random field image models," IEEE Transaction Pattern Analysis and Machine Intelligence, vol. 21, pp. 537-543 (1999).
26. Kashyap, R.and Eomm K., "Robust images techniques with an image restoration application," IEEE Trans. Acoust. Speech Signal Process, vol. 36(8), pp. 1313-1325 (1988).
27. Bustos, O., Ojeda, S. and Vallejos, R., "Spatial ARMA models and its applications to image filtering," Brazilian Journal of Probability and Statistics, vol. 23 (2), pp. 141-165 (2009).
28. Ojeda, S.M., Britos, G.M., "A New Algorithm to Represent Texture Images," International Journal of Advanced Computer Science & Application,  vol. 4(6), pp. 106-111 (2013).
29. Vaishali, D., Ramesh, R., Christaline, J.A., "2D autoregressive model for texture analysis and synthesis," International Conference on Communications and Signal Processing (ICCSP),  pp. 1135 – 1139 (2014).
30. Telea, A., "An image inpainting technique based on the fast marching method,"  Journal of Graphics Tools, vol. 9, no. 1, ACM Press, pp. 25-36 (2004).