计算机科学与技术（参考文献）Image Completion based on Views of Large Displacement

Visual Comput (2007)23:833-841 D0110.1007/s00371-007-0137-4 ORIGINAL ARTICLE Chunxiao Liu Image completion based on views of large Yanwen Guo Liang Pan displacement Qunsheng Peng Fuyan Zhang Published online:19 June 2007 Abstract This paper presents an transformed PSRs,we develop a new Springer-Verlag 2007 algorithm for image completion image repairing algorithm,coupled based on the views of large displace- with graph cut based image stitch- ment.A distinct from most existing ing,texture synthesis based image image completion methods,which inpainting,and image fusion based exploit only the target image's own hole filling,to complete the missing information to complete the damaged regions seamlessly.Finally,the ghost regions,our algorithm makes full effect between the repaired region use of a large displacement view and its surroundings is eliminated (LDV)of the same scene,which by Poisson image blending.Our introduces enough information to algorithm effectively preserves the C.Liu(✉).Y.Guo-L.Pan·Q.Peng resolve the original ill-posed prob- structure information on the missing State Key Lab of CAD&CG. lem.To eliminate any perspective area of the target image and produces Zhejiang University,310027,Hangzhou, China distortion during the warping of the a repaired result comparable to its liuchunxiao.ywguo.panliang.peng} LDV image,we first decompose original appearance.Experiments @cad.zju.edu.cn the target image and the LDV one show the effectiveness of our method. Y.Guo.F.Zhang into several corresponding planar National Laboratory for Novel Software scene regions (PSRs)and transform Keywords Image completion. Technology,Nanjing University, the candidate PSRs on the LDV Large displacement view.Image 210093,Nanjing.China image onto their correspondences stitching.Texture synthesis ywguo,fyzhang@graphics.nju.edu.cn on the target image.Then using the 1 Introduction may run into the view of our camera.The problem is,there- fore,how to generate a visually pleasing result after removal Image completion is the task of filling in the missing or of the intruder from the image.It would be difficult to com- damaged regions of an image with the available informa- plete the target image by itself,especially for missing re- tion from the same or another image to generate a per- gions with complex structures.On the other hand,if we have ceptually satisfactory result.Due to the wide applications another view of the same scene with a large displacement in photo editing,rig removal and special effects produc- that reveals the previously occluded regions,we can faith- tion [6],image completion has received great attention in fully restore the occluded regions on the target image the past decade.Many methods have been brought for- Image completion based on views of large displace- ward so far [22].but most of them are mainly focused on ment is different from traditional image completion.Tra- single image based techniques. ditional methods only make use of the surrounding known Few methods address image completion based on views pixels on the target image to solve its unknown regions. of large displacement.In fact,this provides a feasible way which is in nature an ill-posed problem [21].However, for image completion in our lives.For instance,when we video completion bears a certain similarity to our problem take photos at some famous resorts,an undesired person in adopting other frames to repair the current frame,but

Visual Comput (2007) 23: 833–841 DOI 10.1007/s00371-007-0137-4 ORIGINAL ARTICLE Chunxiao Liu Yanwen Guo Liang Pan Qunsheng Peng Fuyan Zhang Image completion based on views of large displacement Published online: 19 June 2007 © Springer-Verlag 2007 C. Liu (✉)· Y. Guo · L. Pan · Q. Peng State Key Lab of CAD&CG, Zhejiang University, 310027, Hangzhou, China {liuchunxiao,ywguo,panliang,peng} @cad.zju.edu.cn Y. Guo · F. Zhang National Laboratory for Novel Software Technology, Nanjing University, 210093, Nanjing, China {ywguo,fyzhang}@graphics.nju.edu.cn Abstract This paper presents an algorithm for image completion based on the views of large displace￾ment. A distinct from most existing image completion methods, which exploit only the target image’s own information to complete the damaged regions, our algorithm makes full use of a large displacement view (LDV) of the same scene, which introduces enough information to resolve the original ill-posed prob￾lem. To eliminate any perspective distortion during the warping of the LDV image, we first decompose the target image and the LDV one into several corresponding planar scene regions (PSRs) and transform the candidate PSRs on the LDV image onto their correspondences on the target image. Then using the transformed PSRs, we develop a new image repairing algorithm, coupled with graph cut based image stitch￾ing, texture synthesis based image inpainting, and image fusion based hole filling, to complete the missing regions seamlessly. Finally, the ghost effect between the repaired region and its surroundings is eliminated by Poisson image blending. Our algorithm effectively preserves the structure information on the missing area of the target image and produces a repaired result comparable to its original appearance. Experiments show the effectiveness of our method. Keywords Image completion · Large displacement view · Image stitching · Texture synthesis 1 Introduction Image completion is the task of filling in the missing or damaged regions of an image with the available informa￾tion from the same or another image to generate a per￾ceptually satisfactory result. Due to the wide applications in photo editing, rig removal and special effects produc￾tion [6], image completion has received great attention in the past decade. Many methods have been brought for￾ward so far [22], but most of them are mainly focused on single image based techniques. Few methods address image completion based on views of large displacement. In fact, this provides a feasible way for image completion in our lives. For instance, when we take photos at some famous resorts, an undesired person may run into the view of our camera. The problem is, there￾fore, how to generate a visually pleasing result after removal of the intruder from the image. It would be difficult to com￾plete the target image by itself, especially for missing re￾gions with complex structures. On the other hand, ifwe have another view of the same scene with a large displacement that reveals the previously occluded regions, we can faith￾fully restore the occluded regions on the target image. Image completion based on views of large displace￾ment is different from traditional image completion. Tra￾ditional methods only make use of the surrounding known pixels on the target image to solve its unknown regions, which is in nature an ill-posed problem [21]. However, video completion bears a certain similarity to our problem in adopting other frames to repair the current frame, but

834 C.Liu et al. it normally exploits the adiacent frames to fulfil the task. gle image based and can be classified as partial differential taking no account of those frames with LDVs. equations(PDEs)based methods,texture synthesis based In this paper,we explore the problem of image com- methods.and statistics based ones pletion based on the view of large displacement.The first PDE based methods regard image completion as PDE challenge is how to convert the visible regions on the LDV solving [3]or variational problems [1,5]by specifying the image into usable information for repair.Images taken known pixels around the damaged regions as boundary from different views may present great distortion for the conditions.The image repairing process is,therefore,the same scene.Thus,it is unfeasible to repair the damaged diffusion of the known pixels into the missing regions. regions on the target image by globally warping the LDV Such methods work well for small regions,but may fail for image.Since the LDV image contains components with highly textured regions. different scene depths,we first need to segment it as well Texture synthesis based methods select the known re- as the target image into several corresponding planar scene gions on the target image as texture swatches,then per- regions(PSRs).We then transform the candidate PSRs on form texture synthesis with these swatches to generate the LDV image onto their counterparts on the target image new image fragments for the missing regions [8,9,13,15] by image matching and warping. These methods produce satisfactory results for the tex- After the transformation of the candidate PSRs on the tured regions,but cannot recover the precise structure in- LDV image,another challenge is how to repair the tar- formation in large missing regions.Under the guidance get image.Overlappings and gaps may occur between the of specified structure curves in the blank regions,remark- warped PSRs,as they are independently warped with dif- able repairing results are generated in [19,24].However, ferent homographies.Moreover,the missing regions on the this demands complicated user interaction for scenes with target image may consist of multiple PSRs.Thus,for each complex structures. pixel in the missing region,several candidate pixels or none Statistics based methods solve the problem of image may exist in the warped PSRs.No previous image com- completion by statistical analysis.Levin [17]obtained pletion methods have addressed such a repairing problem global statistical distribution based on the available part of We here propose a new image repairing algorithm to tackle the image by statistical learning and found the most prob- it.Coupled with graph cut based image stitching [25],tex- able image by loopy belief propagation.The EM based ture synthesis based image inpainting and image fusion method [10]treats the problem as the estimation of the based hole filling,the algorithm adaptively repairs the dif- missing or damaged regions and adopts an expectation ferent parts in the missing regions with different schemes. maximization(EM)algorithm for ML estimation based on In addition.due to luminance difference between the tar- sparse representation of image completion. get image and the LDV image,a ghost effect may appear on To the best of our knowledge,few methods focus on the repaired result.To eliminate it,we further adopt Poisson image completion based on views of large displacement. image blending [20]to generate a seamless result. Our main contribution lies in that we describe a novel 2.2 Video completion idea for image completion.i.e.completing the target image using the available information on the LDV image. Bertalmio et al.[2]extended fluid dynamics based image We also propose for the first time a preliminary framework completion to video sequences.This method is capable for effectively dealing with such a problem. of filling small textureless holes on each video frame, The rest of the paper is organized as follows.Section 2 but is unsuitable for completing large holes.Regarding reviews related work.Section 3 describes our approach of video completion as a global optimization problem on image completion in detail based on the view of large dis- texture synthesis,the methods in [26]and [23]recover placement.Experimental results and analysis are given in the missing information by directly sampling spatio- Sect.4.Section 5 concludes the whole paper and high- temporal patches of local structures or motion.Jia et al.'s lights future work method [14]searches for the optimal matched fragments in the video sequences to fill the hole boundary with the highest priority and imposes constraints on the selected 2 Related work patches to maintain temporal consistency.Motion peri- odicity is also utilized for texture synthesis based video Here we mainly review the relevant techniques on image repairing [12]. and video completion. As can be seen,most video completion techniques as- sume small camera motion between adjacent frames.They 2.1 Image completion just fetch the information in the adjacent frames for re- pairing.However,for the problem discussed in this paper, Since Bertalmio et al.[3]presented their work on image we cannot directly use the information on the LDV image inpainting for the first time in 2000,many methods have because of the severe distortion of the same scene under been brought forward.Nevertheless,most of them are sin- different views

834 C. Liu et al. it normally exploits the adjacent frames to fulfil the task, taking no account of those frames with LDVs. In this paper, we explore the problem of image com￾pletion based on the view of large displacement. The first challenge is how to convert the visible regions on the LDV image into usable information for repair. Images taken from different views may present great distortion for the same scene. Thus, it is unfeasible to repair the damaged regions on the target image by globally warping the LDV image. Since the LDV image contains components with different scene depths, we first need to segment it as well as the target image into several corresponding planar scene regions (PSRs). We then transform the candidate PSRs on the LDV image onto their counterparts on the target image by image matching and warping. After the transformation of the candidate PSRs on the LDV image, another challenge is how to repair the tar￾get image. Overlappings and gaps may occur between the warped PSRs, as they are independently warped with dif￾ferent homographies. Moreover, the missing regions on the target image may consist of multiple PSRs. Thus, for each pixel in the missing region, several candidate pixels or none may exist in the warped PSRs. No previous image com￾pletion methods have addressed such a repairing problem. We here propose a new image repairing algorithm to tackle it. Coupled with graph cut based image stitching [25], tex￾ture synthesis based image inpainting and image fusion based hole filling, the algorithm adaptively repairs the dif￾ferent parts in the missing regions with different schemes. In addition, due to luminance difference between the tar￾get image and the LDV image, a ghost effect may appear on the repaired result. To eliminate it, we further adopt Poisson image blending [20] to generate a seamless result. Our main contribution lies in that we describe a novel idea for image completion, i.e. completing the target image using the available information on the LDV image. We also propose for the first time a preliminary framework for effectively dealing with such a problem. The rest of the paper is organized as follows. Section 2 reviews related work. Section 3 describes our approach of image completion in detail based on the view of large dis￾placement. Experimental results and analysis are given in Sect. 4. Section 5 concludes the whole paper and high￾lights future work. 2 Related work Here we mainly review the relevant techniques on image and video completion. 2.1 Image completion Since Bertalmio et al. [3] presented their work on image inpainting for the first time in 2000, many methods have been brought forward. Nevertheless, most of them are sin￾gle image based and can be classified as partial differential equations (PDEs) based methods, texture synthesis based methods, and statistics based ones. PDE based methods regard image completion as PDE solving [3] or variational problems [1, 5] by specifying the known pixels around the damaged regions as boundary conditions. The image repairing process is, therefore, the diffusion of the known pixels into the missing regions. Such methods work well for small regions, but may fail for highly textured regions. Texture synthesis based methods select the known re￾gions on the target image as texture swatches, then per￾form texture synthesis with these swatches to generate new image fragments for the missing regions [8, 9, 13, 15]. These methods produce satisfactory results for the tex￾tured regions, but cannot recover the precise structure in￾formation in large missing regions. Under the guidance of specified structure curves in the blank regions, remark￾able repairing results are generated in [19, 24]. However, this demands complicated user interaction for scenes with complex structures. Statistics based methods solve the problem of image completion by statistical analysis. Levin [17] obtained global statistical distribution based on the available part of the image by statistical learning and found the most prob￾able image by loopy belief propagation. The EM based method [10] treats the problem as the estimation of the missing or damaged regions and adopts an expectation maximization (EM) algorithm for ML estimation based on sparse representation of image completion. To the best of our knowledge, few methods focus on image completion based on views of large displacement. 2.2 Video completion Bertalmio et al. [2] extended fluid dynamics based image completion to video sequences. This method is capable of filling small textureless holes on each video frame, but is unsuitable for completing large holes. Regarding video completion as a global optimization problem on texture synthesis, the methods in [26] and [23] recover the missing information by directly sampling spatio￾temporal patches of local structures or motion. Jia et al.’s method [14] searches for the optimal matched fragments in the video sequences to fill the hole boundary with the highest priority and imposes constraints on the selected patches to maintain temporal consistency. Motion peri￾odicity is also utilized for texture synthesis based video repairing [12]. As can be seen, most video completion techniques as￾sume small camera motion between adjacent frames. They just fetch the information in the adjacent frames for re￾pairing. However, for the problem discussed in this paper, we cannot directly use the information on the LDV image because of the severe distortion of the same scene under different views

Image completion based on views of large displacement 835 3 Image completion based on views of large image patches.Then we merge those patches belong- displacement ing to the same PSR interactively,and finally specify the counterparts between the PSRs on the LDV and the In this paper,we explore two key issues regarding image target image.This is the only step involving user inter- completion based on the view of large displacement.i.e. action in our algorithm. how to transform the visible parts on the LDV image to the (2)Feature extraction and matching.A robust feature ex- target image with less distortion and how to use the trans- traction method,i.e.,the scale invariant feature trans- formed pieces to repair the missing regions on the target form (S/FT)feature detector [181,is adopted to obtain image enough matched feature points for each corresponding We define a local region of a bounding box on the tar- PSRs pair. get image,which encloses the missing area.We refer to (3)Homography solving and image warping.There may this local region as the repairing window.Then,we de- exist some outliers among the matched feature points compose the two images into several corresponding PSRs under the influence of image noises.We reject those and refer to the PSRs on the LDV image whose projection outliers by the RANSAC algorithm and the Levenberg- on the target image covers or partially covers the miss- Marquardt algorithm[11],and obtain the homography ing area as the candidate PSRs.We warp the candidate H for each corresponding PSRs pair by solving PSRs on the LDV image to their counterparts on the tar- get image through image matching and warping.Thus the h visible information encoded in the warped PSRs can be X=HX', h3 ha directly adopted for repairing the target image.For the h6 second issue,by defining appropriate repairing and fu- sion priority functions,a new image repairing algorithm where X and X'are the homogeneous coordinates combining image stitching,texture synthesis and image of the matched feature points.A is a homogeneous fusion is proposed to restore the missing regions with the constant,and ho,...,h7 are the unknown parameters warped PSRs.We further adopt Poisson image blending of H. to eliminate ghost effects and generate a seamless result. By now,the candidate PSRs on the LDV image can The pipeline of our method is illustrated in Fig.1,and the be transformed into their counterparts on the view of the completion process is shown in Fig.2. target image to serve for repairing as shown in Fig.3. The following sections will elaborate on the individual stages and provide the details of our approach. 3.2 A new image repairing algorithm 3.1 Transformation of the visible information in LDV The repairing window on the target image may be covered by the projection of more than one warped candidate PSR We perform the following steps: and overlappings and gaps may exist among the warped PSRs as illustrated in Fig.3. (1)Image segmentation into PSRs.Interactive segmenta- We present a new image repairing algorithm as shown tion of the scene into accurate PSRs by the user is diffi-in Fig.4.Let the missing region on the target image be 22. cult.We use a mean shift algorithm [7]to segment the After transformation,the warped candidate PSRs fall onto target image and the LDV image initially into a set of the repairing window in Fig.4a.Some parts cover the Transformation of the Visible Information in LDV Input:The Target Image and The Image Merging Image Image LDV Image Segmentation Operation Matching Warping Poisson Image Fusion Texture Graph Cut Output:The Synthesis Repairing Result Image Based Hole Based Image Blending Filling Based Image Inpainting Stitching A New Image Repairing Algorithm. Fig.1.The pipeline of our method

Image completion based on views of large displacement 835 3 Image completion based on views of large displacement In this paper, we explore two key issues regarding image completion based on the view of large displacement, i.e., how to transform the visible parts on the LDV image to the target image with less distortion and how to use the trans￾formed pieces to repair the missing regions on the target image. We define a local region of a bounding box on the tar￾get image, which encloses the missing area. We refer to this local region as the repairing window. Then, we de￾compose the two images into several corresponding PSRs and refer to the PSRs on the LDV image whose projection on the target image covers or partially covers the miss￾ing area as the candidate PSRs. We warp the candidate PSRs on the LDV image to their counterparts on the tar￾get image through image matching and warping. Thus the visible information encoded in the warped PSRs can be directly adopted for repairing the target image. For the second issue, by defining appropriate repairing and fu￾sion priority functions, a new image repairing algorithm combining image stitching, texture synthesis and image fusion is proposed to restore the missing regions with the warped PSRs. We further adopt Poisson image blending to eliminate ghost effects and generate a seamless result. The pipeline of our method is illustrated in Fig. 1, and the completion process is shown in Fig. 2. The following sections will elaborate on the individual stages and provide the details of our approach. 3.1 Transformation of the visible information in LDV We perform the following steps: (1) Image segmentation into PSRs. Interactive segmenta￾tion of the scene into accurate PSRs by the user is diffi- cult. We use a mean shift algorithm [7] to segment the target image and the LDV image initially into a set of Fig. 1. The pipeline of our method image patches. Then we merge those patches belong￾ing to the same PSR interactively, and finally specify the counterparts between the PSRs on the LDV and the target image. This is the only step involving user inter￾action in our algorithm. (2) Feature extraction and matching. A robust feature ex￾traction method, i.e., the scale invariant feature trans￾form (SIFT) feature detector [18], is adopted to obtain enough matched feature points for each corresponding PSRs pair. (3) Homography solving and image warping. There may exist some outliers among the matched feature points under the influence of image noises. We reject those outliers by the RANSAC algorithm and the Levenberg– Marquardt algorithm [11], and obtain the homography H for each corresponding PSRs pair by solving X = HX
, i.e. λ
x y 1 = h0 h1 h2 h3 h4 h5 h6 h7 1 
x
y
1 , where X and X
are the homogeneous coordinates of the matched feature points. λ is a homogeneous constant, and h0,..., h7 are the unknown parameters of H. By now, the candidate PSRs on the LDV image can be transformed into their counterparts on the view of the target image to serve for repairing as shown in Fig. 3. 3.2 A new image repairing algorithm The repairing window on the target image may be covered by the projection of more than one warped candidate PSR, and overlappings and gaps may exist among the warped PSRs as illustrated in Fig. 3. We present a new image repairing algorithm as shown in Fig. 4. Let the missing region on the target image be Ω. After transformation, the warped candidate PSRs fall onto the repairing window Ωˆ in Fig. 4a. Some parts cover the

836 C.Liu et al. d 9 m 0 Fig.2a-p.Profile of the library.a The target image,b Repairing result obtained by a texture synthesis based method [8].c The LDV image.d The warped LDV image.e Removing the person from the target image.f Initial segmentation of the target image.g PSRs on the target image.h Initial segmentation of the LDV image.i PSRs on the LDV image.j.k Warped PSRs from the LDV image.I Optimal seam lines (contours of the green and yellow regions).m Intermediate repairing result by graph cut based image stitching.n Repairing result after texture synthesis based image inpainting with the residual missing pixels in red.o The final repairing result.p The original scene missing area,filling in the blank pixels;some parts over-in 22,we define a region of band along Lsb.Let 22a lap with the known pixels of the target image within 22.As denote the area outside the band within the repairing win- stated above,the warped PSRs may overlap with each other dow,i.e.,=n.22a is restored by graph cut based generating overlappings 20 along the common boundary image stitching.Let 22 denote the missing area inside the Lsb,or disconnect leaving gaps s2 between them.Except band and covered by the warped PSRs.2,is recovered by for s20 and 220,the rest of the missing pixels s2 hold one- texture synthesis based image inpainting.Note that there one correspondency in the warped PSRs. might be a few pixels in s2'that fail to be filled by texture Our algorithm divides the missing region on the synthesis due to the match constraints.We refer to these target image into three parts and repairs them with differ- pixels as 2c,which is finally filled by fusing the nearby ent schemes as illustrated in Fig.4b.Since the common known pixels on the target image. boundary Lsb of the PSRs usually contains significant fea- Our image repairing process can be briefly described tures,to ensure faithful restoration of these feature lines a as follows:

836 C. Liu et al. Fig. 2a–p. Profile of the library. a The target image, b Repairing result obtained by a texture synthesis based method [8], c The LDV image. d The warped LDV image. e Removing the person from the target image. f Initial segmentation of the target image. g PSRs on the target image. h Initial segmentation of the LDV image. i PSRs on the LDV image. j,k Warped PSRs from the LDV image. l Optimal seam lines (contours of the green and yellow regions). m Intermediate repairing result by graph cut based image stitching. n Repairing result after texture synthesis based image inpainting with the residual missing pixels in red. o The final repairing result. p The original scene missing area, filling in the blank pixels; some parts over￾lap with the known pixels of the target image within Ωˆ . As stated above, the warped PSRs may overlap with each other generating overlappings Ωo b along the common boundary Lsb, or disconnect leaving gaps Ωo c between them. Except for Ωo b and Ωo c , the rest of the missing pixels Ωo a hold one– one correspondency in the warped PSRs. Our algorithm divides the missing region Ω on the target image into three parts and repairs them with differ￾ent schemes as illustrated in Fig. 4b. Since the common boundary Lsb of the PSRs usually contains significant fea￾tures, to ensure faithful restoration of these feature lines in Ω, we define a region of band Ω
along Lsb. Let Ωa denote the area outside the band within the repairing win￾dow, i.e., Ωa = Ω ∩Ω˜
. Ωa is restored by graph cut based image stitching. Let Ωb denote the missing area inside the band and covered by the warped PSRs. Ωb is recovered by texture synthesis based image inpainting. Note that there might be a few pixels in Ω
that fail to be filled by texture synthesis due to the match constraints. We refer to these pixels as Ωc, which is finally filled by fusing the nearby known pixels on the target image. Our image repairing process can be briefly described as follows:

Image completion based on views of large displacement 837 Gaps Warped PSR】 Warped PSRI Warped PSRI Homographyl PSR PSRI Separate Transformation PSR2 PSR2 Homography2 2 Warped PSR2 Warped PSR2 PSR2 Warped PSR2 Overlappings The target region 6 The practical strategy Fig.3.Transformation of the visible information on the LDV Fig.4a,b.Our image repairing algorithm.The target image con- image.The candidate PSRs on the LDV image are independently sists of two PSRs with their common boundary Lsh.The warped warped onto their counterparts on the target image,hence several PSRs fall onto the repairing window 22,which encloses the missing overlappings and gaps appear among the warped candidate PSRs region s2 on I.a Circled by the blue lines,22 contains three parts. 1.e.,the missing pixels under the overlappings 222,the gaps 2 and the remainder 22.b Our algorithm divides 2 into three parts and Graph cut based image stitching stitches the warped repairs these with different schemes.The missing pixels in 2a out- candidate PSRs onto 2.. side the region of band are first recovered by graph cut based image stitching.Then those in 2 are restored by texture synthe- -Texture synthesis based image inpainting samples the sis based image inpainting.Finally,those in sc are completed by warped PSRs to synthesize 2 in terms of a defined image fusion based hole filling repairing priority function. -Image fusion based hole filling fuses the nearby known pixels to fill the gaps 2c under the control of a defined date matches for p are confined to the surrounding pixels fusion priority function. of the corresponding 3 x 3 patch in the warped candidate PSRs.The whole process is terminated when a certain We now discuss the details of our repairing algorithm. condition is satisfied. To ensure a faithful restoration of the potential feature 3.2.1 Graph cut based image stitching lines along the common boundary Lsb,it is important to select a good seed pixel to start the texture synthesis pro- In order to stitch the warped candidate PSRs onto a cess.An appropriate repairing priority function needs to seamlessly,we use a graph cut algorithm [4]to discover be defined.For a boundary pixel p in the missing region, the optimal seam lines in the overlapping regions of the we define its repairing priority as Pr(p)=Ci(p)*Si(p), warped PSRs and the known area on the target image where within 22.The graph cut algorithm works by expressing the problem as finding the min-cut in a weighted graph and minimizing the color gradient differences across the C(p)=〉w(pi)/8 seaminess.This has already been used in texture synthe- i=1 sis [16]and image stitching [25],and is well suited for this purpose. is the confidence term that represents the reliable informa- After finding the optimal seaminess,the warped PSRs tion contained in p's 8-neighborhood,thereinto w(pi)is are stitched onto the target image along the seaminess to the reliability weight of p's 8-neighborhood pixel pi.In fill the remaining pixels in 22a. implementation,we set a threshold t=3/8 for Ci(p)to qualify the boundary pixels with enough known neighbors 3.2.2 Texture synthesis based image inpainting and control the repairing process from the boundary pixels to the interior of 2'progressively. The remaining missing pixels in o are filled one by one with texture synthesis based image inpainting.It begins S(p)=(/L)*(7Ih·np/a) with a pixel on the boundary of 22',i.e.,022',and iter- atively selects the next pixel with the highest priority to is the structure term,in which is the number of PSRs re- proceed.For each pixel p to be filled,we define a 3x 3 ferred to by pixels in p's 8-neighborhood.L is the number patch centered at p.The existent pixels in the patch are of warped PSRs projecting into the repairing window.l/L used as the constraints for finding the best match m ac- can endow the pixels near Lsb with high repairing priority. cording to the SSD metric (the sum of squared differences VIp represents the color gradient at p,L denotes the orth- between the colors of their surrounding pixels).The candi- ogonal operator,np is the unit normal of p on as2'and a

Image completion based on views of large displacement 837 Fig. 3. Transformation of the visible information on the LDV image. The candidate PSRs on the LDV image are independently warped onto their counterparts on the target image, hence several overlappings and gaps appear among the warped candidate PSRs – Graph cut based image stitching stitches the warped candidate PSRs onto Ωa. – Texture synthesis based image inpainting samples the warped PSRs to synthesize Ωb in terms of a defined repairing priority function. – Image fusion based hole filling fuses the nearby known pixels to fill the gaps Ωc under the control of a defined fusion priority function. We now discuss the details of our repairing algorithm. 3.2.1 Graph cut based image stitching In order to stitch the warped candidate PSRs onto Ωa seamlessly, we use a graph cut algorithm [4] to discover the optimal seam lines in the overlapping regions of the warped PSRs and the known area on the target image within Ωˆ . The graph cut algorithm works by expressing the problem as finding the min-cut in a weighted graph and minimizing the color gradient differences across the seaminess. This has already been used in texture synthe￾sis [16] and image stitching [25], and is well suited for this purpose. After finding the optimal seaminess, the warped PSRs are stitched onto the target image along the seaminess to fill the remaining pixels in Ωa. 3.2.2 Texture synthesis based image inpainting The remaining missing pixels in Ωb are filled one by one with texture synthesis based image inpainting. It begins with a pixel on the boundary of Ω
, i.e., ∂Ω
, and iter￾atively selects the next pixel with the highest priority to proceed. For each pixel p to be filled, we define a 3×3 patch centered at p. The existent pixels in the patch are used as the constraints for finding the best match m ac￾cording to the SSD metric (the sum of squared differences between the colors of their surrounding pixels). The candi￾Fig. 4a,b. Our image repairing algorithm. The target image I con￾sists of two PSRs with their common boundary Lsb. The warped PSRs fall onto the repairing window Ωˆ , which encloses the missing region Ω on I. a Circled by the blue lines, Ω contains three parts, i.e., the missing pixels under the overlappings Ωo b , the gaps Ωo c and the remainder Ωo a . b Our algorithm divides Ω into three parts and repairs these with different schemes. The missing pixels in Ωa out￾side the region of band Ω
are first recovered by graph cut based image stitching. Then those in Ωb are restored by texture synthe￾sis based image inpainting. Finally, those in Ωc are completed by image fusion based hole filling date matches for p are confined to the surrounding pixels of the corresponding 3×3 patch in the warped candidate PSRs. The whole process is terminated when a certain condition is satisfied. To ensure a faithful restoration of the potential feature lines along the common boundary Lsb, it is important to select a good seed pixel to start the texture synthesis pro￾cess. An appropriate repairing priority function needs to be defined. For a boundary pixel p in the missing region, we define its repairing priority as PI(p) = CI(p) ∗ SI(p), where CI(p) = 8 i=1 w(pi)/8 is the confidence term that represents the reliable informa￾tion contained in p’s 8-neighborhood, thereinto w(pi) is the reliability weight of p’s 8-neighborhood pixel pi. In implementation, we set a threshold τ = 3/8 for CI(p) to qualify the boundary pixels with enough known neighbors and control the repairing process from the boundary pixels to the interior of Ω
progressively. SI(p) = (l/L) ∗ (∇I⊥ p · np/α) is the structure term, in which l is the number of PSRs re￾ferred to by pixels in p’s 8-neighborhood. L is the number of warped PSRs projecting into the repairing window. l/L can endow the pixels near Lsb with high repairing priority. ∇Ip represents the color gradient at p, ⊥ denotes the orth￾ogonal operator, np is the unit normal of p on ∂Ω
and α

838 C.Liu et al. is a normalization factor.V/a represents the inter- action strength of the image structure with the boundary of the missing region and boosts the priority of a patch where the structural interaction takes place [8]. Table 1 illustrates our inpainting algorithm based on texture synthesis.In the algorithm,two termination condi- tions are provided.If a'is empty,which indicates that all pixels in the missing region are repaired,the image repairing process terminates.Or else,if the highest re- pairing priority is 0 and the repairing cycle fails to repair Fig.5.The intermediate repairing result(from Fig.2n)after texture any pixels,which means that none of the remaining pix- synthesis based image inpainting.The red pixels within the zoom- els can be matched with a pixel in the warped PSRs,the in rectangle are those residual missing pixels in 22 that hold no algorithm also terminates this inpainting process.The re- matched pixels in the warped PSRs during texture synthesis based maining missing pixels,if any,are filled by the following image inpainting process hole filling process. priority for the pixel with less PSRs in its 4-neighborhood 3.2.3 Image fusion based hole filling and is the number of PSRs covering 22. With the above definition,all residual pixels are first After texture synthesis based image inpainting,some still sorted according to their fusion priorities.Then,the one missing pixels in 2c remain unrepaired.Normally,only a with the highest priority is filled with the average color of few of them exist as shown in Fig.5.We therefore take its 4 neighbors,and the priorities of relevant residual pix- the pixel-wise fusion operation to deal with such pixels. els are refreshed thereafter.The above process is repeated The basic idea is to fill in the residual pixels with the color until all residual pixels are filled. fused by those of its known neighbors. To make the result more reasonable,fusion operation 3.3 Poisson image blending should start from the residual pixel with more known pix- els and less PSRs in its neighborhood.For the pixel p,we Due to the luminance difference between the LDV image define the fusion priority function Pr(p)as and the target image,ghost effects may appear on the re- paired result as shown in Figs.6j and 7f.We tackle this PE(p)=CF(p)*SF(p). issue by Poisson image blending [20]. Let S be the domain of the target image.22 represents Here CF(p)=n/4 is the confidence term and SF(p)=1/I the repaired region in S with boundary a22=(p S\22: is the support term.CF(p)sets high priority for the re- Npn0),in which Np denotes p's 4-neighborhood. sidual pixel with more known pixels in its 4-neighborhood, Supposing that f*is the known color of all pixels in a22, n is the number of its known neighbors.SF(p)sets high we obtain the fusion color f of all pixels in 2 by solving the following linear equations: Table 1.Texture synthesis based image inpainting If-∑=∑信+∑ 8pq 1.Initialization. qENpn2 qENpna2 qENpn2 Initialize a2'and 2' 2.Weight setup. where pe22.gpg=cp-c is the color gradient between fpPi∈2，w(pi)=0:else w(p)=1.p:∈I. the repaired pixels p and g in 22.We can solve the above 3.Priority computation. large-scale sparse linear equations efficiently with the con- ·Compute C(p),Vp∈a2'.fC(p)]with m(pm), W(Pm）=0 5.Update a22'and 22' We implemented the proposed algorithm on an Intel Pen- tium IV 1.6 GHz PC with 256 MB main memory under the 6.Repairing cycles and termination conditions. .Cycle 1.Repeat steps 4 and 5 until no more pixel is repaired Windows XP operating system.Figures 2,6 and 7 demon- in two successive iterations.If as'=0,exit. strate the experimental results. Cycle 2.Repeat steps 2~5 until no more pixel is repaired Figure 2a presents the target image.We first adopt in two successive cycles. the traditional texture synthesis based image completion If a'0 &maxpeag'PI(p)=0. method [8]to repair the occluded area and get Fig.2b. go to the following hole filling process. Obviously,the missing part of the tree cannot be well re-

838 C. Liu et al. is a normalization factor. ∇I⊥ p · np/α represents the inter￾action strength of the image structure with the boundary of the missing region and boosts the priority of a patch where the structural interaction takes place [8]. Table 1 illustrates our inpainting algorithm based on texture synthesis. In the algorithm, two termination condi￾tions are provided. If ∂Ω
is empty, which indicates that all pixels in the missing region are repaired, the image repairing process terminates. Or else, if the highest re￾pairing priority is 0 and the repairing cycle fails to repair any pixels, which means that none of the remaining pix￾els can be matched with a pixel in the warped PSRs, the algorithm also terminates this inpainting process. The re￾maining missing pixels, if any, are filled by the following hole filling process. 3.2.3 Image fusion based hole filling After texture synthesis based image inpainting, some still missing pixels in Ωc remain unrepaired. Normally, only a few of them exist as shown in Fig. 5. We therefore take the pixel-wise fusion operation to deal with such pixels. The basic idea is to fill in the residual pixels with the color fused by those of its known neighbors. To make the result more reasonable, fusion operation should start from the residual pixel with more known pix￾els and less PSRs in its neighborhood. For the pixel p, we define the fusion priority function PF(p) as PF(p) = CF(p) ∗ SF(p). Here CF(p) = n/4 is the confidence term and SF(p) = 1/l is the support term. CF(p) sets high priority for the re￾sidual pixel with more known pixels in its 4-neighborhood, n is the number of its known neighbors. SF(p) sets high Table 1. Texture synthesis based image inpainting 1. Initialization. Initialize ∂Ω
and Ω
. 2. Weight setup. If pi ∈ Ω
, w(pi) = 0; else w(pi) = 1. ∀pi ∈ I. 3. Priority computation. • Compute CI(p), ∀p ∈ ∂Ω
. If CI(p) 0] with m(pm), w(pm) = 0. 5. Update ∂Ω
and Ω
. 6. Repairing cycles and termination conditions. • Cycle 1. Repeat steps 4 and 5 until no more pixel is repaired in two successive iterations. If ∂Ω
= ∅, exit. • Cycle 2. Repeat steps 2 ∼ 5 until no more pixel is repaired in two successive cycles. If ∂Ω
= ∅ && maxp∈∂Ω
PI(p) = 0, go to the following hole filling process. Fig. 5. The intermediate repairing result (from Fig. 2n) after texture synthesis based image inpainting. The red pixels within the zoom￾in rectangle are those residual missing pixels in Ωc that hold no matched pixels in the warped PSRs during texture synthesis based image inpainting process priority for the pixel with less PSRs in its 4-neighborhood and l is the number of PSRs covering Ω. With the above definition, all residual pixels are first sorted according to their fusion priorities. Then, the one with the highest priority is filled with the average color of its 4 neighbors, and the priorities of relevant residual pix￾els are refreshed thereafter. The above process is repeated until all residual pixels are filled. 3.3 Poisson image blending Due to the luminance difference between the LDV image and the target image, ghost effects may appear on the re￾paired result as shown in Figs. 6j and 7f. We tackle this issue by Poisson image blending [20]. Let S be the domain of the target image. Ω represents the repaired region in S with boundary ∂Ω = {p ∈ S \Ω : Np ∩ Ω = ∅}, in which Np denotes p’s 4-neighborhood. Supposing that f ∗ is the known color of all pixels in ∂Ω, we obtain the fusion color f of all pixels in Ω by solving the following linear equations: |Np| fp −  q∈Np∩Ω fq =  q∈Np∩∂Ω f ∗ q +  q∈Np∩Ω gpq, where p ∈ Ω. gpq = cp −cq is the color gradient between the repaired pixels p and q in Ω. We can solve the above large-scale sparse linear equations efficiently with the con￾jugate gradient method. 4 Results and discussion We implemented the proposed algorithm on an Intel Pen￾tium IV 1.6 GHz PC with 256 MB main memory under the Windows XP operating system. Figures 2, 6 and 7 demon￾strate the experimental results. Figure 2a presents the target image. We first adopt the traditional texture synthesis based image completion method [8] to repair the occluded area and get Fig. 2b. Obviously, the missing part of the tree cannot be well re-

Image completion based on views of large displacement 839 j k Fig.6a-1.A corner of a building.a Target image.b PSRs on the target image.c LDV image.d PSRs on the LDV image. e.f Warped PSRs from the LDV image.g Optimal seam lines produced by graph cut (contours of the green and vellow areas). h Intermediate repairing result by graph cut based image stitching.i Repairing result after texture synthesis based image inpainting with the residual missing pixels in red.j Repairing result without Poisson image blending.k The final repairing result.I The original scene constructed due to its insufficient condition [21].Sun et and k are the warped candidate PSRs on their counter- al.'s method [24]can achieve remarkable image repair- parts on the target image.We then carry out graph cut ing results for the missing regions with strong structure based image stitching.Figure 21 shows the optimal seam information.However,their method requires that struc-lines produced by graph cut.Figure 2m is the result of ture curves be carefully specified,which is impossible for image stitching along the optimal seam lines.Figure 2n a missing area with such a complex structure in our case.is the intermediate repairing result after texture synthesis By exploiting the information from an LDV image of the based image inpainting.We obtain the final repairing re- same scene,our method can obtain the more natural re- sult Fig.20 after image fusion based hole filling on the pairing result as shown in Fig.20. residual missing pixels (shown in red in Fig.2n).It took Figure 2c is an LDV image,and Fig.2d is its glob- less than I min to repair about 10000 missing pixels on the ally warped image with respect to Fig.2a.Compared target image with a size of 461 x 361 besides the time for with Fig.2a,distinct distortion is exhibited in the wall of interaction. Fig.2d.Repairing the occluded region with Fig.2d di- Figures 6 and 7 demonstrate the other two experi- rectly will lead to a poor result. ments.Figures 6j and 7f show the repairing result without Figures 2e-o illustrate the process of our algorithm. Poisson image blending.An obvious ghost effect exists The red mask in Fig.2e is the specified target region.Fig- due to the illuminance difference between the target image ure 2f presents the initial segmentation of the target image and the LDV image.In comparison,Figs.6k and 7g show with mean shift,and Fig.2g shows its PSRs after interac-the seamless repairing results with Poisson image blend- tively merging the fragments that belong to the same scene ing,which are comparable to the original scene in Figs.61 plane.Similarly,Fig.2h presents the initial segmentation and 7h.As can be seen,our algorithm works well even for of the LDV image,and Fig.2i shows its PSRs.Figures 2j large missing regions with complex structure information

Image completion based on views of large displacement 839 Fig. 6a–l. A corner of a building. a Target image. b PSRs on the target image. c LDV image. d PSRs on the LDV image. e,f Warped PSRs from the LDV image. g Optimal seam lines produced by graph cut (contours of the green and yellow areas). h Intermediate repairing result by graph cut based image stitching. i Repairing result after texture synthesis based image inpainting with the residual missing pixels in red. j Repairing result without Poisson image blending. k The final repairing result. l The original scene constructed due to its insufficient condition [21]. Sun et al.’s method [24] can achieve remarkable image repair￾ing results for the missing regions with strong structure information. However, their method requires that struc￾ture curves be carefully specified, which is impossible for a missing area with such a complex structure in our case. By exploiting the information from an LDV image of the same scene, our method can obtain the more natural re￾pairing result as shown in Fig. 2o. Figure 2c is an LDV image, and Fig. 2d is its glob￾ally warped image with respect to Fig. 2a. Compared with Fig. 2a, distinct distortion is exhibited in the wall of Fig. 2d. Repairing the occluded region with Fig. 2d di￾rectly will lead to a poor result. Figures 2e–o illustrate the process of our algorithm. The red mask in Fig. 2e is the specified target region. Fig￾ure 2f presents the initial segmentation of the target image with mean shift, and Fig. 2g shows its PSRs after interac￾tively merging the fragments that belong to the same scene plane. Similarly, Fig. 2h presents the initial segmentation of the LDV image, and Fig. 2i shows its PSRs. Figures 2j and k are the warped candidate PSRs on their counter￾parts on the target image. We then carry out graph cut based image stitching. Figure 2l shows the optimal seam lines produced by graph cut. Figure 2m is the result of image stitching along the optimal seam lines. Figure 2n is the intermediate repairing result after texture synthesis based image inpainting. We obtain the final repairing re￾sult Fig. 2o after image fusion based hole filling on the residual missing pixels (shown in red in Fig. 2n). It took less than 1 min to repair about 10 000 missing pixels on the target image with a size of 461×361 besides the time for interaction. Figures 6 and 7 demonstrate the other two experi￾ments. Figures 6j and 7f show the repairing result without Poisson image blending. An obvious ghost effect exists due to the illuminance difference between the target image and the LDV image. In comparison, Figs. 6k and 7g show the seamless repairing results with Poisson image blend￾ing, which are comparable to the original scene in Figs. 6l and 7h. As can be seen, our algorithm works well even for large missing regions with complex structure information

840 C.Liu et al. d 9 h Fig.7a-h.Profile of a teaching building.a Target image.b LDV image.c,d Warped PSRs from the LDV image.e Optimal seam lines shown as the contours of the green and yellow regions.f Repairing result without Poisson image blending.g The final repairing result. h The original scene 5 Conclusion and future work user interaction,which is time-consuming.We wish to employ the information of color distribution and rela- Image completion based on views of large displacement tive location of the initially segmented image patches fills in occluded or damaged regions of a target image ex- to automatize this process. ploiting the visible information of the LDV images.In this At present,we only verify our method with a single paper,we propose an effective solution for this problem. LDV image.However,image completion from multi- By employing the techniques of image segmentation and ple images with different views will be more useful image matching,we transform the LDV image into us- for photo editing and completion.We shall further test able information,and then repair the missing region with the cases of several LDV images with complex occlu- a new image repairing algorithm.Experiments show that sions. our method works well even for large missing regions with complex structure,and achieves superior repairing results to previous image completion techniques Acknowledgement This work was supported by the Natural Sci- The following topics are to be investigated in future: ence Foundation of China (grant nos.60403038 and 60603076) and the National Basic Research Project of China (grant no. PSRs on the target image and the LDV image one as 2002CB312101).The authors are grateful for the stimulating dis- well as their counterparts are currently specified by cussions with Drs.Jin Wang,Wei Chen and Changbo Wang. References 1.Ballester,C..Caselles,V..Verdera.J.. 4.Boykov,Y..Kolmogorov.V.:An 8.Criminisi,A..Perez.P..Toyama,K.: Bertalmio.M..Sapiro.G.:A variational experimental comparison of min-cut/max- Region filling and object removal by model for filling-in gray level and color flow algorithms for energy minimization in exemplar-based image inpainting.IEEE images.In:Proceedings of the IEEE ICCV vision.IEEE Trans.Patter Anal.Mach. Trans.Image Processing 13(9),1200-1212 2001.vol.1,Pp.10-16(2001) ntell.269).1124-1137(2004) (2004) 2.Bertalmio,M..Bertozzi A.L.,Sapiro,G.: 5.Chan,T.,Shen,J.H.:Variational image 9.Drori,I.,Cohen-Or,D..Yeshurum,H.: Navier-Stokes,fluid dynamics,and image inpainting.Commun.Pure Appl.Math. Fragment-based image completion.ACM and video inpainting.In:Proceedings of the 58(5).579-619(2005) Trans.Graph.22(3).303-312 IEEE CVPR 2001,vol.I,pp.355-362 6.Collis,B..Kokaram.A.:Filling in the (2003) (2001) gaps.IEE Electron.Systems Software 2(4). 10.Fadili,M.J.,Starck,J.L.:EM algorithm for 3.Bertalmio,M.,Sapiro.G.,Caselles,V.. 22-28(2004) sparse representation-based image Ballester,C.:Image inpainting.In: 7.Comaniciu,D.,Meer,P.:Mean Shift: inpainting.In:Proceedings of the IEEE Proceedings of ACM SIGGRAPH 2000 A robust approach toward feature space ICP2005,vol.2,pp.61-64(2005) pp.417-424.New Orleans,Louisiana analysis.IEEE Trans.Pattem Anal.Mach. 11.Hartley,R.,Zisserman,A.:Multiple view (2000) Intell.245),603-619(2002) geometry in computer vision.Cambridge

840 C. Liu et al. Fig. 7a–h. Profile of a teaching building. a Target image. b LDV image. c,d Warped PSRs from the LDV image. e Optimal seam lines shown as the contours of the green and yellow regions. f Repairing result without Poisson image blending. g The final repairing result. h The original scene 5 Conclusion and future work Image completion based on views of large displacement fills in occluded or damaged regions of a target image ex￾ploiting the visible information of the LDV images. In this paper, we propose an effective solution for this problem. By employing the techniques of image segmentation and image matching, we transform the LDV image into us￾able information, and then repair the missing region with a new image repairing algorithm. Experiments show that our method works well even for large missing regions with complex structure, and achieves superior repairing results to previous image completion techniques. The following topics are to be investigated in future: – PSRs on the target image and the LDV image one as well as their counterparts are currently specified by user interaction, which is time-consuming. We wish to employ the information of color distribution and rela￾tive location of the initially segmented image patches to automatize this process. – At present, we only verify our method with a single LDV image. However, image completion from multi￾ple images with different views will be more useful for photo editing and completion. We shall further test the cases of several LDV images with complex occlu￾sions. Acknowledgement This work was supported by the Natural Sci￾ence Foundation of China (grant nos. 60403038 and 60603076) and the National Basic Research Project of China (grant no. 2002CB312101). The authors are grateful for the stimulating dis￾cussions with Drs. Jin Wang, Wei Chen and Changbo Wang. References 1. Ballester, C., Caselles, V., Verdera, J., Bertalmio, M., Sapiro, G.: A variational model for filling-in gray level and color images. In: Proceedings of the IEEE ICCV 2001. vol. 1, pp. 10–16 (2001) 2. Bertalmio, M., Bertozzi A.L., Sapiro, G.: Navier–Stokes, fluid dynamics, and image and video inpainting. In: Proceedings of the IEEE CVPR 2001, vol. I, pp. 355–362 (2001) 3. Bertalmio, M., Sapiro, G., Caselles, V., Ballester, C.: Image inpainting. In: Proceedings of ACM SIGGRAPH 2000, pp. 417–424. New Orleans, Louisiana (2000) 4. Boykov, Y., Kolmogorov, V.: An experimental comparison of min-cut/max- flow algorithms for energy minimization in vision. IEEE Trans. Pattern Anal. Mach. Intell. 26(9), 1124–1137 (2004) 5. Chan, T., Shen, J.H.: Variational image inpainting. Commun. Pure Appl. Math. 58(5), 579–619 (2005) 6. Collis, B., Kokaram, A.: Filling in the gaps. IEE Electron. Systems Software 2(4), 22–28 (2004) 7. Comaniciu, D., Meer, P.: Mean Shift: A robust approach toward feature space analysis. IEEE Trans. Pattern Anal. Mach. Intell. 24(5), 603–619 (2002) 8. Criminisi, A., Perez, P., Toyama, K.: ´ Region filling and object removal by exemplar-based image inpainting. IEEE Trans. Image Processing 13(9), 1200–1212 (2004) 9. Drori, I., Cohen-Or, D., Yeshurum, H.: Fragment-based image completion. ACM Trans. Graph. 22(3), 303–312 (2003) 10. Fadili, M.J., Starck, J.L.: EM algorithm for sparse representation-based image inpainting. In: Proceedings of the IEEE ICIP 2005, vol. 2, pp. 61–64 (2005) 11. Hartley, R., Zisserman, A.: Multiple view geometry in computer vision. Cambridge

Image completion based on views of large displacement 841 University Press,(2000) video synthesis using graph cuts.ACM algorithms.In:Proceedings of ICITA 2005, 1SBN:0521623049) Trans.Graph.22(3),277-286(2003) pp.15-24(2005) 12.Jia,J.,Tai,Y.W.,Wu,T.P.Tang.C.K.: 17.Levin,A.,Zomet,A.,Weiss,Y.:Learning 23.Shiratori,T.,Matsushita,Y.,Kang.S.B., Video repairing under variable illumination how to inpaint from global image statistics Tang,X.:Video completion by motion field using cyclic motions.IEEE Trans.Pattern In:Proceedings of the IEEE ICCV 2003. transfer.In:Proceedings of the IEEE Anal.Mach.Intell.28(5).832-839 pp.305-312.Nice,France(2003) CVPR2006,vol.1,Pp.411-418(2006 (2006 18.Lowe.D.G.:Distinctive image features 24.Sun,J.,Lu,Y.,Jia,J.Y.,Shum,H.Y.:Image 13.Jia,J.Y..Tang.C.K.:Image repairing: from scale-invariant interest points.Int.J. completion with structure propagation. robust image synthesis by adaptive ND Comput..Vision602),91-110(2004) ACM Trans.Graph.24(3),861-868 tensor voting.In:Proceedings of the IEEE 19.Pavic.D..Schonefeld.V..Kobbelt.L. (2005) CVPR2003.vol.1,PP.643-650(2003) Interactive image completion with 25.Szeliski,R.:Image alignment and stitching 14.Jia.Y.T.,Hu.S.M.,Martin,R.R.:Video perspective correction.Visual Comput.(PG a tutorial.In:Microsoft Research Technical completion using tracking and fragment 200622(9-11).671-681(2006 Reports. merging.Visual Comput.(PG 2005) 20.Perez,P..Gangnet,M..Blake,A.:Poisson http://research.microsoft.com/vision/ 21(8-10).601-610(2005) image editing.ACM Trans.Graph.22(3), visionbasedmodeling/publications/MSR- 15.Komodakis,N..Tziritas.G.:Image 313-318(2003) TR-2004-92-Jan26.pdf. completion using global optimization.In: 21.Shen,J.H.:Inpainting and the fundamental (2004) Proceedings of the IEEE CVPR 2006. problem of image processing.SIAM News 26.Wexler,Y.,Shechtman,E.,Irani,M.: vol1,Pp.442-452(2006 365).1-4(2003) Space-time video completion.In: 16.Kwatra.V.,Schodl.A.,Essa.I..Turk,G.. 22.Shih,T.K..Chang.R.C.:Digital inpainting Proceedings of the IEEE CVPR 2004. Bobick,A.:Graphcut textures:image and -survey and multilayer image inpainting vol.1,Pp.120-127(2004) CHUNXIAO LIU was born in 1979 and is a PhD search interests include texture synthesis and sity,P.R.China.His research interests include candidate at the State Key Lab.of CAD&CG, mapping.image video editing and synthesis. virtual reality,realistic image synthesis,infrared Zhejiang University,P.R.China.His research image synthesis,computer animation,and scien- interests include image and video completion, LIANG PAN received his MSc degree in ap- tific data visualization. image and video based rendering and virtual re- plied mathematics from Zhejiang University in ality 2006.His main research interests lie in image FUYAN ZHANG is a professor at the Na- completion and computer graphics. tional Laboratory for Novel Software Technol- YANWEN GUo is an assistant professor at ogy,Nanjing University,P.R.China.His re- the National Laboratory for Novel Software QUNSHENG PENG was born in 1947.He re- search interests include computer graphics,dig- Technology,Nanjing University,P.R.China.He ceived a PhD from the University of East An- ital library,multimedia computing and systems received his PhD at the State Key Lab of glia in 1983 and is currently a professor at the CAD&CG,Zhejiang University in 2006.His re- State Key Lab.of CAD&CG.Zhejiang Univer-

Image completion based on views of large displacement 841 University Press, (2000) (ISBN: 0521623049) 12. Jia, J., Tai, Y.W., Wu, T.P., Tang, C.K.: Video repairing under variable illumination using cyclic motions. IEEE Trans. Pattern Anal. Mach. Intell. 28(5), 832–839 (2006) 13. Jia, J.Y., Tang, C.K.: Image repairing: robust image synthesis by adaptive ND tensor voting. In: Proceedings of the IEEE CVPR 2003. vol. 1, pp. 643–650 (2003) 14. Jia, Y.T., Hu, S.M., Martin, R.R.: Video completion using tracking and fragment merging. Visual Comput. (PG 2005) 21(8–10), 601–610 (2005) 15. Komodakis, N., Tziritas, G.: Image completion using global optimization. In: Proceedings of the IEEE CVPR 2006, vol. 1, pp. 442–452 (2006) 16. Kwatra, V., Schödl, A., Essa, I., Turk, G., Bobick, A.: Graphcut textures: image and video synthesis using graph cuts. ACM Trans. Graph. 22(3), 277–286 (2003) 17. Levin, A., Zomet, A., Weiss, Y.: Learning how to inpaint from global image statistics. In: Proceedings of the IEEE ICCV 2003, pp. 305–312. Nice, France (2003) 18. Lowe, D.G.: Distinctive image features from scale-invariant interest points. Int. J. Comput. Vision 60(2), 91–110 (2004) 19. Pavic, D., Schönefeld, V., Kobbelt, L.: ´ Interactive image completion with perspective correction. Visual Comput. (PG 2006) 22(9–11), 671–681 (2006) 20. Perez, P., Gangnet, M., Blake, A.: Poisson ´ image editing. ACM Trans. Graph. 22(3), 313–318 (2003) 21. Shen, J.H.: Inpainting and the fundamental problem of image processing. SIAM News 36(5), 1–4 (2003) 22. Shih, T.K., Chang, R.C.: Digital inpainting – survey and multilayer image inpainting algorithms. In: Proceedings of ICITA 2005, pp. 15–24 (2005) 23. Shiratori, T., Matsushita, Y., Kang, S.B., Tang, X.: Video completion by motion field transfer. In: Proceedings of the IEEE CVPR 2006, vol. 1, pp. 411–418 (2006) 24. Sun, J., Lu, Y., Jia, J.Y., Shum, H.Y.: Image completion with structure propagation. ACM Trans. Graph. 24(3), 861–868 (2005) 25. Szeliski, R.: Image alignment and stitching: a tutorial. In: Microsoft Research Technical Reports, http://research.microsoft.com/vision/ visionbasedmodeling/publications/MSR￾TR-2004-92-Jan26.pdf. (2004) 26. Wexler, Y., Shechtman, E., Irani, M.: Space-time video completion. In: Proceedings of the IEEE CVPR 2004, vol. 1, pp. 120–127 (2004) CHUNXIAO LIU was born in 1979 and is a PhD candidate at the State Key Lab. of CAD&CG, Zhejiang University, P.R. China. His research interests include image and video completion, image and video based rendering and virtual re￾ality. YANWEN GUO is an assistant professor at the National Laboratory for Novel Software Technology, Nanjing University, P.R. China. He received his PhD at the State Key Lab of CAD&CG, Zhejiang University in 2006. His re￾search interests include texture synthesis and mapping, image video editing and synthesis. LIANG PAN received his MSc degree in ap￾plied mathematics from Zhejiang University in 2006. His main research interests lie in image completion and computer graphics. QUNSHENG PENG was born in 1947. He re￾ceived a PhD from the University of East An￾glia in 1983 and is currently a professor at the State Key Lab. of CAD&CG, Zhejiang Univer￾sity, P.R. China. His research interests include virtual reality, realistic image synthesis, infrared image synthesis, computer animation, and scien￾tific data visualization. FUYAN ZHANG is a professor at the Na￾tional Laboratory for Novel Software Technol￾ogy, Nanjing University, P.R. China. His re￾search interests include computer graphics, dig￾ital library, multimedia computing and systems