Simultaneous Structure and Texture Image Inpainting M.Bertalmio,L.Ve,G.Sapiro,and S.Osher University Pompeu Fabra,University of Minnesota,UCLA
guille@ece.umn.edu
Abstract
An algorithm for the simultaneousfilling-in of texture and structure in regions of missing image information is pre-nted in this paper.The basic idea is tofirst decompo the image into the sum of two functions with different ba-sic characteristics,and then reconstruct each one of the functions parately with structure and texturefilling-in al-gorithms.Thefirst function ud in the decomposition is of bounded variation,reprenting the underlying image struc-ture,while the cond function captures the texture and possible noi.The region of missing information in the bounded variation image is reconstructed using image in-painting algorithms,while the same region in the texture image isfilled-in with texture synthesis techniques.The original image is then reconstructed adding back the two sub-images.The novel contribution of this paper is then in the combination of the three previously developed com-ponents,image decomposition with inpainting and texture synthesis,which permits the simultaneous u offilling-in algorithms that are suited for different image characteris-tics.Examples on real images show the advantages of this propod approach.
Keywords:Inpainting,filling-in,structure,texture,texture synthesis,bounded variation,image decomposition.
1Introduction
Thefilling-in of missing information is a very important topic in image processing,with applications including im-age coding and wireless image ,recover-ing lost blocks),special ,removal of objects), and image ,scratch removal).The basic idea behind the algorithms that have been propod in the literature is tofill-in the regions with available informa-tion from their surroundings.This information can be au-tomatically detected as in[4,8],or hinted by the ur as in more classical texturefilling techniques[7,12,27].
The algorithms reported in the literature best perform for pure texture,[8,12,27],or pure structure,[2,3,4](e also early work in[23],which shows the u of the Burt-Adelson pyramid for the reconstruction of smooth regions).This means that for ordinary images such as the one in Fig-ure1,different techniques work better for different parts. In[25],it was shown how to automatically switch between the pure texture and pure structurefilling-in process.This is done by analyzing the area surrounding the region to be filled-in(inspired by[15]),and lecting either a texture synthesis or
a structure inpainting technique.Since most image areas are not pure texture or pure structure,this ap-proach provides just afirst attempt in the direction of simul-taneous texture and structurefilling-in(attempt which was found sufficient for the particular application of transmis-sion and coding prented in the paper).It is the goal of this paper to advance in this direction and propo a new tech-nique that will perform both texture synthesis and structure inpainting in all regions to befilled-in.
The basic idea of our algorithm is prented in Figure 3,which shows a real result from our approach.The orig-inal image(first row,left)isfirst decompod into the sum of two images,one capturing the basic image structure and one capturing the texture(and random noi),cond row. This follows the recent work by Ve and Osher reported in[28].Thefirst image is inpainted following the work by Bertalmio-Sapiro-Calles-Ballester described in[4],while the cond one isfilled-in with a texture synthesis algorithm following the work by Efros and Leung in[8],third row. The two reconstructed images are then added back together to obtain the reconstruction of the original data,first row, right.In other words,the general idea is to perform struc-ture inpainting and texture synthesis not on the original im-age,but on a t of images with very different character-istics that are obtained from decomposing the given data. The decomposition is such that it produces images suited for the two reconstruction algorithms.We will show how this approach outperforms both image inpainting and tex-ture synthesis when applied parately.
The propod algorithm has then three main building blocks:Image decomposition,image(structure)inpaint-ing,and texture synthesis.In the next three ctions we briefly describe the particular techniques ud for each one of them.As we show in the experimental ction,the par-ticular lections,which have been shown to produce state-of-the-art results in each one of their particular applications, outperform previously available techniques when combined
as propod in this paper.In the concluding remarks ction
we discuss the possible u of other approaches to address each one of the building blocks in order to further improve
on the results here reported.
2Image decomposition
In this ction we review the image decomposition approach
propod in[28],which is one of the three key ingredients of the simultaneous texture and structure image inpainting
algorithm.As explained in the introduction,this decompo-sition produces images that are very well suited for the im-
age inpainting and texture synthesis techniques described
in the next ctions.The description below is adapted from [28],where the technique wasfirst introduced.The inter-
ested readers are referred to this work for more details,ex-
amples,and theoretical results.
The two main ingredients of the decomposition devel-
oped in[28]are the total variation minimization of[26]for image denoising and restoration,and the space of oscillat-
ing functions introduced in[21]to model texture or noi.
Let I R I R be a given obrved image,I R. could be just a noisy version of a true underlying image, or could be a textured image,then being a simple sketchy女生齐肩发型
approximation or a cartoon image of(with sharp edges).
A simple relation between and can be expresd by
a linear model,introducing another function,such that
In[26],the problem of recon-structing from is pod as a minimization problem in the space of functions of bounded variation I R,[10], allowing for edges:
(1)
where is a tuning parameter.The cond term in the energy is afidelity term,while thefirst term is a regular-izing term,to remove noi or small details,while keeping important features and sharp edges.
In[21],Meyer proved that for small the model will remove the texture.To extract both the and the component as an oscillating function(texture or noi)from ,Meyer propod the u of a different space of functions, which is in some n the dual of the space.He intro-duced the following definition,and also proved a number of results showing the explicit relationship between the norm below and the model in[26](e[21,28]for details): Definition1.Let denote the Banach space consistin
g of all generalized functions which can be written as
莫言txt下载
I R(2) induced by the norm defined as the lower bound of all norms of the functions where,
and where the infimum
is computed over all decompositions(2)of.
Meyer showed that if the component reprents texture
or noi,then,and propod the following new image restoration model:artisan
(3)
In[28],the authors devid and solved a variant of this model,making u only of simple partial differential equa-tions.This new model leads us to the decomposition we need for simultaneous structure and texturefilling-in.
The following minimization problem is the one propod
in[28],inspired by(3):
(4) where are tuning parameters,and.Theupskirt
first term ensures that I R,the cond term en-sures that div,while the third term is a penalty on the norm in of div.
For,as ud in this paper,the corresponding Euler-Lagrange equations are[28]
div(5)
(6)
(7)
As can be en from the examples in[28]and the images
in this paper,the minimization model(5)allows to extract from a given real textured image the components and, such that is a sketchy(cartoon)approximation of,and
reprents the texture or the noi(note that this is not just a low/high frequency decomposition).For some theoretical results and the detailed mi-implicit nu-merical implementation of the above Euler-Lagrange equa-tions,e[28].
3Texture synthesis
We now describe the cond key component of our scheme, the basic algorithm ud tofill-in the region of missing in-formation in,the texture image.While for the examples
机械设计制造及其自动化考研
in this paper,we u the algorithm developed in[8],this is not crucial and other texture synthesis techniques could be
tested for this task.Note however that modulo the lec-
tion of a few parameters,this algorithm is fully automatic and produces very good texture synthesis results.Moreover,
this algorithm is very well suited to natural images when
the regions to be inpainted cover a large variety of textures. The are the basic reasons that lead us to the lection of
this particular technique from the vast literature on texture synthesis.
Let the region to befilled be denoted by.will be filled,pixel by pixel,proceeding from the border in-
wards.Let be a reprentative template,with known pix-els,touching the pixel to befilled-in next.We
proceed tofind a t of from the available neighborhood,
such that a given distance is below a pre-defined threshold.As per[8],is the normalized sum of squared
differences(SSD)metric.Once such a t of’s is found,
we randomly cho one of the pixels who location with respect to corresponds to the same position of with respect to.We thenfill with the value of this pixel.
The template can be a simple ed-block of33 pixels as shown in Fig2.Then,of all blocks with fully available data in the image,we look at tho clor than a pre-defined threshold to,and randomly pick one. We then replace the current pixel beingfilled-in in the lost block by the value of the corresponding pixel next to the lected block.This algorithm is considerably faster when using the improvements in[11,30].
4Image inpainting
We now describe the third key component of our propod scheme,the algorithm ud tofill-in the region of missing information in the bounded variation image.For the ex-amples in this paper we u the technique developed in[4]. Other image inpainting algorithms such as as[2,3]could be tested for this application as well.
Once again let be the region to befilled in(inpainted) and be its boundary.The basic idea in inpainting is to smoothly propagate the information surrounding in the direction of the isophotes entering.Both gray values and isophote directions are propagated inside the region. Denoting by the image,this propagation is achieved by numerically solving the partial differential equation(is an artificial time marching parameter)
(8)
where,,and stand for the gradient,Laplacian,and orthogonal-gradient(isophote direction)respectively.This equation is solved only inside,with proper boundary con-ditions in for the gray values and isophote directions[4].
Note that at steady state,,and. This means that is constant in the direction of the isophotes,thereby achieving a smooth continuation of the Laplacian inside the region to be inpainted.
For details on the numerical implementation of this in-painting technique,which follows the techniques intro-duced in[19,26],as well as numerous examples and appli-cations,e[4].Note in particular that at every numerical step of(8),a step of anisotropic diffusion,[1,24],is ap-plied[4].Multiresolution can also be applied to speed-up the convergence[4].sandman
For image inpainting alternatives to this approach,e [2,3].In particular,[3]shows the relationship of the above equation with classicalfluid dynamics,and prents a dif-ferentflow to achieve the steady state
.The work in[2]prents a formal variational ap-proach that leads to a system of coupled cond order differential equations.All the works were in part in-spired by[20,22].Full details can also be found umn.edu/guille/inpainting.htm.Additional related work is described in[6,13,14,17,18],while [5,9,16,29]provides literature on inpainting as done by professional restorators.Comments on the contributions and comparisons with the work just described are provided in[4].
5Experimental results
We now prent additional experimental results and com-pare with the ca when the image is not d
ecompod prior tofilling-in,and just one algorithm,either image inpainting or texture synthesis,is applied.Color is treated similarly to[4,8](with additional vectorial operations).While each of the three components of the algorithm here propod has a number of parameters,all but two of them were left un-changed for all the examples in this paper.The only pa-rameters that vary are and the number of steps in inpaint-ing,although the results were found to be very stable to the parameters as well.Figure4shows an example of object removal.Additionalfigures,in color,can be found umn.edu/guille/inpainting.htm
6Conclusions and future directions
In this paper we have shown the combination of image de-composition with image inpainting and texture synthesis.
For all the images we have ud,the number of numeri-cal steps of the decomposition is equal to,and the texture synthesis algorithm us a square template.Regarding the varying parame-ters,forfigure3and for the others,while the number of inpainting steps(with a discrete time step of)are200forfigure3 and2000for the others(almost identical images were obtained when2000 steps were ud for Figure3).小学英语单词汇总
tpm管理
The basic idea is tofirst decompo the image into the sum of two functions,one that can be efficiently reconstructed via inpainting and one that can be efficiently reconstructed via texture synthesis.This permits the simultaneous u of the reconstruction techniques in the image domain they were designed for.In contrast with previous approaches, both image inpainting and texture synthesis are applied to the region of missing information,only that they are applied not to the original image reprentation but to the images obtained from the decomposition.The obtained results out-perform tho obtained when only one of the reconstruction algorithms is applied to each image region.
Further experiments are to be carried out to obtain the best combination of image decomposition,image inpaint-ing,and texture synthesis.Since a number of algorithms exist for each one of the three key components,the com-bination that provides the best visual results is an interesting experimental and theoretical rearch topic. Acknowledgments
This work was partially supported by the Office of Naval Rearch,the National Science Foundation,the National In-stitute of Health,the Office of Naval Rearch Young Inves-tigator Award to GS,the Presidential Early Career Awards for Scientists and Engineers(PECASE)to GS,a National Science Foundation CAREER Award to GS,by the National Science Foundation Learning and Intellig
ent Systems Pro-gram(LIS),and by the Programa Ramon y Cajal(Minis-terio de Ciencia y Tecnologia,Spain).MB and GS thank Prof.Vicent Calles,with whom all this work on image inpainting started.He is a constant source of intellectual and personal inspiration.
References
[1]L.Alvarez,P.L.Lions,and J.M.Morel,“Image lec-
tive smoothing and edge detection by nonlinear diffu-sion,”SIAM J.Numer.Anal.29,pp.845-866,1992. [2]C.Ballester,M.Bertalmio,V.Calles,G.Sapiro,and
J.Verdera,“Filling-in by joint interpolation of vector fields and grey levels,”IEEE Trans.Image Processing 10,pp.1200-1211,August2001.
[3]M.Bertalmio,A.L.Bertozzi,and G.Sapiro,“Navier-
Stokes,fluid dynamics,and image and video inpaint-ing,”Proc.IEEE Computer Vision and Pattern Recog-nition(CVPR),Hawaii,December2001.
[4]M.Bertalmio,G.Sapiro,V.Calles,and C.Ballester,
“Image inpainting,”Computer Graphics(SIGGRAPH 2000),pp.417–424,July2000.[5]C.Braverman,Photoshop retouching handbook,IDG
Books Worlwide,1998.
[6]T.Chan and J.Shen,“Local inpainting models and TV
inpainting,”SIAM J.Appl.Math.62:3,pp.1019-1043, 2001.
[7]J.S.De Bonet,“Multiresolution sampling procedure
for analysis and synthesis of texture images,”Proceed-ings of ACM SIGGRAPH,July1997.
[8]A.A.Efros and T.K.Leung,“Texture synthesis by non-
parametric sampling,”IEEE International Conference on Computer Vision,Corfu,Greece,pp.1033–1038, Sept.1999.
[9]G.Emile-Male,The Restorer’s Handbook of Eal
Painting,Van Nostrand Reinhold,New York,1976. [10]L.C.Evans and R.F.Gariepy,Measure Theory an
d
Fine Properties of Functions,CRC Press,London, 1992.
[11]G.Gorla,V.Interrante,and G.Sapiro,“Growingfit-
ted textures,”IEEE Trans.Visualization and Computer Graphics,to appear.
[12]D.Heeger and J.Bergen,“Pyramid bad texture
analysis/synthesis,”Computer Graphics(SIGGRAPH 1995),pp.229–238,July1995.
[13]A.Hirani and T.Totsuka,“Combining frequency and
spatial domain information for fast interactive image noi removal,”Computer Graphics,pp.269-276,SIG-GRAPH96,1996.
[14]L.Joyeux,O.Buisson,B.Besrer,and S.Boukir,
“Detection and removal of line scratches in motion picturefilms,”Proceedings of CVPR’99,IEEE Int.
< Computer Vision and Pattern Recognition, Fort Collins,Colorado,USA,June1999.
[15]K.Karu, A.K.Jain,and R.M.Bolle,“Is there
any texture in the image?,”Pattern Recognition29:9, pp.1437–1446,1996.
一眨眼
[16]D.King,The Commissar Vanishes,Henry Holt and
Company,1997.
[17]A.C.Kokaram,R.D.Morris,W.J.Fitzgerald,and
P.J.W.Rayner,“Detection of missing data in image quences,”IEEE Transactions on Image Processing 11:4,pp.1496-1508,1995.
[18]A.C.Kokaram,R.D.Morris,W.J.Fitzgerald,and
P.J.W.Rayner,“Interpolation of missing data in image quences,”IEEE Transactions on Image Processing 11:4,pp.1509-1519,1995.
[19]A.Marquina and S.Osher,“Explicit algorithms for a
new time dependent model bad on level t motion for nonlinear debluring and noi removal,”SIA
M J.Sci.
Comput.,22,pp.387-405,2000.
[20]S.Masnou and J.Morel,“Level-lines bad disocclu-
sion,”IEEE Int.Conf.Image Processing,October1998.
[21]Y.Meyer,Oscillating Patterns in Image Processing
and Nonlinear Evolution Equations,AMS University Lecture Series22,2002.
[22]M.Nitzberg, D.Mumford,and T.Shiota,Filter-
ing,Segmentation,and Depth,Springer-Verlag,Berlin, 1993.
[23]J.M.Ogden,E.H.Adelson,J.R.Bergen,and P.J.
Burt,“Pyramid-bad computer graphics,”RCA Engi-neer30(5),pp.4-15,1985.
[24]P.Perona and J.Malik“Scale-space and edge detec-
tion using anisotropic diffusion,”IEEE-PAMI12,pp.
629-639,1990.
[25]S.Rane,G.Sapiro,and M.Bertalmio,“Structure
and texturefilling-in of missing image blocks in wire-less transmission and compression applications,”IEEE Trans.Image Processing,to appear.
[26]L.Rudin,S.Osher,and E.Fatemi,“Nonlinear total
variation bad noi removal algorithms,”Physica D, no.60,pp.259–268,1992.
[27]E.Simoncelli and J.Portilla,“Texture characterization
via joint statistics of wavelet coefficient magnitudes,”
Proc.5th IEEE Int’ Image Processing,1998.
[28]L.Ve and S.Osher,“Modeling textures with total
variation minimization and oscillating patterns in image processing,”Journal of Scientific Computing,to appear.
[29]S.Walden,The Ravished Image,St.Martin’s Press,
supreme中文叫什么
New York,1985.
[30]L.Y.Wei and M.Levoy,“Fast texture synthesis using
tree-structured vector quantization,”Computer Graph-ics(SIGGRAPH2000),July
2000.Figure1:Example of image with both texture and
structure.
Figure2:Basic texture synthesis procedure
