计算机科学与技术（参考文献）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 α