Patent Publication Number: US-8526759-B2

Title: Method of filling a hole in a virtual view image warped from a two-dimensional image

Description:
CROSS-REFERENCE TO RELATED APPLICATION 
     This application claims priority to Taiwanese Application No. 100107730, filed on Mar. 8, 2011. 
     BACKGROUND OF THE INVENTION 
     1. Field of the Invention 
     The invention relates to an image compensating method, and more particularly to a method for filling a hole in a virtual view image warped from a two-dimensional image. 
     2. Description of the Related Art 
       FIG. 1  illustrates the Depth-Image-Based Rendering (DIBR) technology capable of generating a three-dimensional image by using a two-dimensional image, and a depth map generated by a depth detector (not shown) and corresponding to the two-dimensional image. In the DIRB technology, the two-dimensional image is processed based on the depth map using image warping to generate various virtual view images, such as left virtual view images. For example,  FIG. 2  shows an example of the two-dimensional image,  FIG. 3  shows an example of the depth map corresponding to a foreground image region of the two-dimensional image of  FIG. 2 , and  FIG. 4  shows an example of the left virtual view image warped from the two-dimensional image of  FIG. 2 . However, the DIBR technology has intrinsic limitations. Holes caused by insufficient pixel values in the two-dimensional image appear in the warped virtual view images because the holes do not have correspondence to the two-dimensional image. For example, in  FIG. 4 , a plurality of holes  11  are generally formed in boundaries between a foreground image region (A) and a background image region (B) of the two-dimensional image. Thus, the holes in each warped virtual view image would be filled using hole-filling technology. Finally, the filled virtual view images are combined together to form the three-dimensional image. 
     A conventional hole-filling method (hereinafter referred to as the first conventional method) has been proposed in an article by Criminisi et al., entitled “Region Filling and Object Removal by Exemplar-Based Image Inpainting”, IEEE Transaction on Image Processing, vol. 13, No. 9, September 2004. In the first hole-filling method, an original image is searched to select an image region most similar to a target image region containing holes as a candidate image region for filling the holes within the target image region. Such method requires a lot of effort and takes a great deal of time, thereby resulting in an inferior efficiency. In addition, because the candidate image region is selected from the whole original image, the candidate image region may be selected from a foreground image region of the original image. Therefore, distortions may occur in the filled image. 
     Another conventional hole-filling method (hereinafter referred to as the second conventional method) has been proposed in an article by Lou et at., entitled “Depth-aided Inpainting for Restoration of Multi-view Images Using Depth-Image-Based Rendering”, Journal of Zhejiang University SCIENCE A, pp. 1738-1749, 2009 10(12). In the second hole-filling method, a candidate image region for filling holes in an original image would not be selected from a foreground image region of the original image. In order to save processing time, searching range is reduced to a range around the holes. However, improvements may be made to the second hole-filling method. 
     SUMMARY OF THE INVENTION 
     Therefore, an object of the present invention is to provide a method of filling a hole in a virtual view image warped from a two-dimensional image that can overcome the aforesaid drawbacks of the prior art. 
     According to the present invention, there is provided a method of filling a hole in a virtual view image warped from a two-dimensional image. The virtual view image includes a foreground image region and a background image region. The method comprises the steps of: 
     a) detecting the hole to determine the number (N) of pixels in the hole, where N≧1, and to obtain position information corresponding to the number (N) of the pixels in the hole; 
     b) for each of the number (N) of the pixels in the hole, selecting, from the virtual view image, a target image block that contains at least a corresponding one of the pixels in the hole; 
     c) selecting, from the virtual view image, a number (P) of search image blocks, each of which has a central pixel that is disposed on one of the upside, downside, right and left of a central pixel of the target image block, and detecting whether each of the number (P) of the search image blocks is available so as to determine which ones out of the number (P) of the search image blocks are available; 
     d) upon determining in step c) that a number (Q) of the search image blocks are available, where 1≦Q≦P, estimating each of the number (Q) of the search image blocks using a predetermined estimation manner to generate an estimating value for each corresponding one of the number (Q) of the search image blocks; and 
     e) selecting, based on the estimating values generated in step d), one of the number (Q) of the search image blocks as a candidate image block, and filling each of all pixels in the target image block with a corresponding pixel value in the candidate image block. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
       Other features and advantages of the present invention will become apparent in the following detailed description of the preferred embodiments with reference to the accompanying drawings, of which: 
         FIG. 1  is a flow chart illustrating how a two-dimensional image is converted into a three-dimensional image using the DIBR technology; 
         FIG. 2  is a picture showing an example of the two-dimensional image used in the DIBR technology; 
         FIG. 3  is a picture showing a depth map corresponding to a foreground image region of the two-dimensional image of  FIG. 2 ; 
         FIG. 4  is a picture showing a left virtual view image warped from the two-dimensional image of  FIG. 2 ; 
         FIG. 5  is a flow chart illustrating the first preferred embodiment of a method of filling a hole in a virtual view image warped from a two-dimensional image according to the present invention; 
         FIG. 6  is a fragmentary schematic view showing a virtual view image having various holes; 
         FIG. 7  is a schematic view illustrating how the first preferred embodiment selects search image blocks corresponding to a target image block; 
         FIG. 8  shows various two-dimensional test images; and 
         FIG. 9  is a flow chart illustrating the second preferred embodiment of a method of filling a hole in a virtual view image warped from a two-dimensional image according to the present invention. 
     
    
    
     DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS 
       FIG. 5  shows a flow chart illustrating the first preferred embodiment of a method of filling a hole in a virtual view image warped from a two-dimensional image according to the present invention. The virtual view image is generated from the two-dimensional image based on a depth map (not shown) corresponding to the two-dimensional image. 
     In step S 51 , the hole is detected to determine the number (N) of pixels in the hole, where N≧1, and to obtain position information corresponding to the number (N) of the pixels in the hole. In this embodiment, the position of each pixel in the hole can be detected according to the following Function (1): 
                             buffer   ⁡     (     x   ,   y     )       =       ⁢       ±       t   x     2       ⁢     f   Z         ,     non   ⁢     -     ⁢   hole   ⁢           ⁢   pixel                   =       ⁢   null     ,     hold   ⁢           ⁢   pixel                   Function   ⁢           ⁢     (   1   )                 
where t x  is a distance between human eyes, f is a focal distance of human eyes, and Z is a gray-level value of a pixel in the depth map located at a position (x, y). As such, if the function value of buffer (x, y) is null, the pixel in the virtual view image located at the position (x, y) is regarded as a hole-pixel and is labeled.
 
     In step S 52 , it is determined based on the position information obtained in step S 51  whether the hole is a small-sized hole. If the result is negative, the flow goes to step S 53 . Otherwise, the flow proceeds to step S 62 . In this embodiment, the small-size hole is in the form of one of a 1×1 array region and a 1×2 array region. For example, in  FIG. 6 , holes  112  are classified as small-sized holes while holes  111  are not classified as small-sized holes. 
     In step S 53 , initially, a parameter (i) is set to 1. 
     In step S 54 , for an i th  one of the number (N) of the pixels in the hole, where 1≦i≦N, a target image block is selected from the virtual view image. The target image block contains at least the i th  one of the pixels in the hole. In this embodiment, the i th  pixel in the hole is a central pixel of the target image block. In addition, initially, the first pixel (i.e., i=1) in the hole is located at an uppermost and leftmost position in the virtual view image. The target image block is a square block that is preferably in the form of one of a 5×5 array region, a 7×7 array region, and a 9×9 array region. For example, referring to  FIG. 7 , a target image block  14  is a 7×7 array region, and the central pixel  141  of the target image block  14  is the i th  pixel in the hole. 
     In step S 55 , a number (P) of search image blocks are selected from the virtual view image. Each of the number (P) of the search image blocks has a central pixel that is disposed on one of the upside, downside, right, and left of the central pixel of the target image block. In this embodiment, the search image blocks are square blocks, and have the same size as that of the target image block. The target image block overlaps each of the number (P) of the search image blocks. Preferably, the number of the search image blocks, the central pixels of which are disposed on each of the upside, downside, left and right of the central pixel of the target image block, is equal to two or three. In addition, the search image blocks, the central pixels of which are disposed on each of the upside, downside, left and right of the central pixel of the target image block, overlap each other. The number (P) of the search image blocks are selected in order so that centers of the number (P) of the search image blocks are arranged along a helical-like line. The central pixel of a first one of the number (P) of the search image blocks is a nearmost neighbor of the central pixel of the target image block. More specifically, the number (P) is a multiple of 4, i.e., P=4M, where M≧1. As such, (4j−3) th , (4j−2) th , (4j−1) th  and (4j) th  search image blocks are arranged along a j th  circle portion of the helical-like line, where 1≦j≦M. 
     In the example shown in  FIG. 7 , there are eight search image blocks ( 15   a ,  15   b ,  15   c ,  15   d ,  15   a ′,  14   b ′,  15   c ′,  15   d ′) that are selected in order, i.e., P=8=4×2 and M=2. The target image block  14  overlaps each of the search image blocks ( 15   a ,  15   b ,  15   c ,  15   d ,  15   a ′,  14   b ′,  15   c ′,  15   d ′). The search image blocks ( 15   a ,  15   a ′) overlap each other by a 7×6 array region, and have central pixels disposed on the upside of the central pixel  141  of the target image block  14 . The search image blocks ( 15   b ,  15   b ′) overlap each other by a 6×7 array region, and have central pixels disposed on the left of the central pixel  141  of the target image block  14 . The search image blocks ( 15   c ,  15   c ′) overlap each other by a 7×6 array region and have central pixels disposed on the downside of the central pixel  141  of the target image block  14 . The search image blocks ( 15   d ,  15   d ′) overlap each other by a 6×7 array region and have central pixels disposed on the right of the central pixel  141  of the target image block  14 . The search image block ( 15   a ) is first selected, and its central pixel is disposed on the upside of the central pixel  141  of the target image block  14  and is a nearmost neighbor of the central pixel  141  of the target image block  14 . As such, centers (C a , C b , C c , C d , C a ′, C b ′, C c ′, C d ′) of the search image blocks ( 15   a ,  15   b ,  15   c ,  15   d ,  15   a ′,  14   b ′,  15   c ′,  15   d ′) are arranged along a two-circle counterclockwise helical-like line (L). The search image blocks ( 15   a ,  15   b ,  15   c ,  15   d ) are arranged along a first circle portion of the helical-like line (L). The search image blocks ( 15   a ′,  15   b ′,  15   c ′,  15   d ′) are arranged along a second circle portion of the helical-like line (L). 
     In addition, in step S 55 , it is detected whether each of the number (P) of the search image blocks is available or not so as to determine which ones of the number (P) of the search image blocks are available. In this embodiment, any one of the search image blocks containing any hole-pixel or any pixel in the foreground image region of the virtual view is regarded as an unavailable search image block. 
     In step S 56 , it is determined whether none of the search image blocks is available. If the result is affirmative, the flow goes to step S 58 . Otherwise, the flow proceeds to step S 57 . 
     In step S 57 , upon determining in step S 56  that a number (Q) of the search image blocks are available, where 1≦Q≦P, each of the number (Q) of the search image blocks is estimated using a predetermined estimation manner to generate an estimating value for each corresponding one of the number (Q) of the search image blocks. In this embodiment, the predetermined estimation manner is configured to calculate an absolute difference between each of pixel values in the target image region and a corresponding one of pixel values in each of the number (Q) of the search image blocks to obtain a sum of the absolute differences that serves as the estimating value corresponding to a corresponding one of the number (Q) of the search image blocks. 
     In step S 58 , upon determining in step S 56  that none of the number (P) of the search image blocks is available, pixels in the target image block without any pixel value is filled using an average filter. Thereafter, the flow goes to step S 60 . 
     In step S 59 , one of the number (Q) of the search image blocks is selected as a candidate image block based on the estimating values corresponding to the number (Q) of the search image blocks. Each of all pixels in the target image block is filled with a corresponding one of all pixel values in the candidate image block. In this embodiment, the estimating value corresponding to the candidate image block is smallest. 
     In step S 60 , it is determined whether the parameter (i) is equal to N. If the result is affirmative, the flow ends. Otherwise, the flow goes to step S 61 . 
     In step S 61 , the parameter (i) is set to i+1. Then, the flow goes back to step S 54 . That is, the flow is performed for an (i+1) th  pixel in the hole. In this embodiment, the (i+1) th  pixel is disposed on the right or the downside of the i th  pixel. 
     In step S 62 , when the hole is the small-sized hole, the hole is filled using an average filter. Then, the flow ends. 
       FIG. 8  illustrates six two-dimensional test images (P 1 , P 2 , P 3 , P 4 , P 5 , P 6 ) provided from “The Middlebury Computer Vision Pages” (http://vision.middlebury.edu/). In an experiment for filling all holes in a left virtual view image warped from each of the test two-dimensional images (P 1 , P 2 , P 3 , P 4 , P 5 , P 6 ) using the conventional first and second methods, and the first preferred embodiment, the experimental results related to processing time required by each of the conventional first and second methods and the first preferred embodiment, and peak signal-to-noise ratio (PSNR) for the filled left virtual view image generated using each of the conventional first and second methods and the first preferred embodiment are shown in Table 1 below. In this experiment, the target image block is a 7×7 array region, and the number (P) of the search image blocks is 8. 
     
       
         
           
               
               
               
               
             
               
                 TABLE 1 
               
               
                   
               
               
                   
                   
                 Processing 
                   
               
               
                 Image 
                 Method 
                 time (sec) 
                 PSNR(dB) 
               
               
                   
               
             
            
               
                   
               
            
           
           
               
               
               
               
            
               
                 P1 
                 First conventional method 
                 1025.17 
                 21.02 
               
               
                   
                 Second Conventional method 
                 155.98 
                 21.23 
               
               
                   
                 First preferred embodiment 
                 0.4 
                 20.86 
               
               
                 P2 
                 First conventional method 
                 554.87 
                 23.36 
               
               
                   
                 Second Conventional method 
                 154.14 
                 23.36 
               
               
                   
                 First preferred embodiment 
                 0.32 
                 22.69 
               
               
                 P3 
                 First conventional method 
                 1155.87 
                 25.89 
               
               
                   
                 Second conventional method 
                 239.15 
                 24.17 
               
               
                   
                 First preferred embodiment 
                 0.69 
                 24.3 
               
               
                 P4 
                 First conventional method 
                 104.25 
                 16.06 
               
               
                   
                 Second conventional method 
                 28.68 
                 16.23 
               
               
                   
                 First preferred embodiment 
                 0.21 
                 16.07 
               
               
                 P5 
                 First conventional method 
                 397.78 
                 21.49 
               
               
                   
                 Second conventional method 
                 206.12 
                 21.73 
               
               
                   
                 First preferred embodiment 
                 0.78 
                 21.38 
               
               
                 P6 
                 First conventional method 
                 179.86 
                 19.71 
               
               
                   
                 Second conventional method 
                 48.72 
                 19.72 
               
               
                   
                 First preferred embodiment 
                 0.42 
                 19.71 
               
               
                   
               
            
           
         
       
     
     As shown in Table 1, the first preferred embodiment can provide PSNR similar to that of the conventional first and second methods. Particularly, the first preferred embodiment can reduce processing time by over 90% as compared to the conventional first and second methods. It is noted that, in this experiment, the first preferred embodiment first processes the small-sized holes in the left virtual view image warped from each of the test two-dimensional images (P 1 , P 2 , P 3 , P 4 , P 5 , P 6 ), and then processes the remaining holes in the same. Alternatively, the holes in the left virtual view image warped from each of the test two-dimensional images (P 1 , P 2 , P 3 , P 4 , P 5 , P 6 ) can be processed in order. 
     Furthermore, in this embodiment, processing time depends on the size of the target image block selected in step S 54 . In another experiment for filling all holes in a left virtual view image warped from each of the test two-dimensional images (P 1 , P 2 , P 3 , P 4 , P 5 , P 6 ) using the first preferred embodiment based on different sizes of the target image block, such as 11×11, 9×9, 7×7, 5×5 and 3×3 array regions, the experimental results related to processing time are shown in Table 2 below. In this experiment, the number (P) of the search image blocks is 8. 
     
       
         
           
               
               
               
               
               
               
               
             
               
                 TABLE 2 
               
               
                   
               
               
                 Image 
                   
                 11 × 11 
                 9 × 9 
                 7 × 7 
                 5 × 5 
                 3 × 3 
               
               
                   
               
             
            
               
                   
               
            
           
           
               
               
               
               
               
               
               
            
               
                 P1 
                 Processing 
                 0.79 
                 0.83 
                 0.4 
                 0.31 
                 0.25 
               
               
                 P2 
                 Time 
                 0.74 
                 0.46 
                 0.33 
                 0.26 
                 0.22 
               
               
                 P3 
                 (sec) 
                 1.55 
                 1.03 
                 0.69 
                 0.53 
                 0.42 
               
               
                 P4 
                   
                 0.32 
                 0.24 
                 0.22 
                 0.21 
                 0.19 
               
               
                 P5 
                   
                 2.90 
                 1.60 
                 0.82 
                 0.41 
                 0.24 
               
               
                 P6 
                   
                 1.14 
                 0.69 
                 0.41 
                 0.27 
                 0.22 
               
               
                   
               
            
           
         
       
     
     As shown in Table 2, for the target image block with the 11×11 or 9×9 array region, processing time increases. However, for the target image block with the 3×3 array region, processing time is shortest but PSNR will be worst. 
     Furthermore, in this embodiment, processing time also depends on the number (P) of the search image blocks selected in step S 55 , where P=4M, and M is the number of circle portions of the helical-like line. In a further experiment for filling all holes in a left virtual view image warped from each of the test two-dimensional images (P 1 , P 2 , P 3 , P 4 , P 5 , P 6 ) using the first preferred embodiment based on p=4, 8, 12, 16 and 20, the experimental results related to processing time are shown in Table 3 below. 
     
       
         
           
               
               
               
               
               
               
               
               
             
               
                 TABLE 3 
               
               
                   
               
               
                 P 
                   
                 P1 
                 P2 
                 P3 
                 P4 
                 P5 
                 P6 
               
               
                   
               
             
            
               
                   
               
            
           
           
               
               
               
               
               
               
               
               
            
               
                 4 
                 Processing 
                 0.27 
                 0.29 
                 0.66 
                 0.21 
                 0.42 
                 0.26 
               
               
                 8 
                 Time 
                 0.4 
                 0.32 
                 0.69 
                 0.22 
                 0.78 
                 0.42 
               
               
                 12 
                 (sec) 
                 0.59 
                 0.44 
                 0.89 
                 0.27 
                 1.3 
                 0.59 
               
               
                 16 
                   
                 0.87 
                 0.71 
                 1.14 
                 0.33 
                 1.95 
                 0.83 
               
               
                 20 
                   
                 1.28 
                 0.84 
                 1.43 
                 0.35 
                 2.76 
                 1.17 
               
               
                   
               
            
           
         
       
     
     As shown in Table 3, the processing time increases very much when P=16 or 20. Although the processing time is shortest when p=4, PSNR under the same conditions is poor. As a result, P is preferably 8 or 12. 
       FIG. 9  shows a flow chart illustrating the second preferred embodiment of a method of filling a hole in a virtual view image warped from a two-dimensional image according to the present invention, which is a modification of the first preferred embodiment. In this embodiment, steps S 52  and S 62  of the first preferred embodiment are omitted. In other words, the second preferred embodiment does not detect whether the hole is a small-sized hole. Steps S 91  to S 100  correspond respectively to steps S 51 , and S 53  to S 61 . 
     In a further experiment for filling all holes in a left virtual view image warped from each of the above test two-dimensional images (P 1 , P 2 , P 3 , P 4 , P 5 , P 6 ) using the first and second preferred embodiments, the experimental results related to processing time required by each of the first and second preferred embodiments, and peak signal to noise ratio (PSNR) for the filled left virtual view image generated using each of the first and second preferred embodiments are shown in Table 1 below. In this experiment, the target image block is a 7×7 array region, and the number (P) of the search image blocks is 8. 
     
       
         
           
               
               
               
               
             
               
                 TABLE 4 
               
               
                   
               
               
                   
                   
                 Processing 
                   
               
               
                 Image 
                 Method 
                 time (sec) 
                 PSNR(dB) 
               
               
                   
               
             
            
               
                   
               
            
           
           
               
               
               
               
            
               
                 P1 
                 First preferred embodiment 
                 0.4 
                 20.86 
               
               
                   
                 Second preferred embodiment 
                 1.06 
                 20.87 
               
               
                 P2 
                 First preferred embodiment 
                 0.32 
                 22.69 
               
               
                   
                 Second preferred embodiment 
                 1.33 
                 22.72 
               
               
                 P3 
                 First preferred embodiment 
                 0.69 
                 24.3 
               
               
                   
                 Second preferred embodiment 
                 2.0 
                 24.32 
               
               
                 P4 
                 First preferred embodiment 
                 0.21 
                 16.07 
               
               
                   
                 Second preferred embodiment 
                 0.3 
                 16.09 
               
               
                 P5 
                 First preferred embodiment 
                 0.78 
                 21.38 
               
               
                   
                 Second preferred embodiment 
                 2.72 
                 21.4 
               
               
                 P6 
                 First preferred embodiment 
                 0.42 
                 19.71 
               
               
                   
                 Second preferred embodiment 
                 0.97 
                 19.71 
               
               
                   
               
            
           
         
       
     
     As shown in Table 4, the second preferred embodiment can provide PSNR similar to that of the first preferred embodiment. However, the second preferred embodiment has relatively longer processing time as compared to the first preferred embodiment. 
     In sum, the method of this invention can ensure certain quality (PNSR) of the filled virtual view image, while effectively reducing processing time compared to the prior art. 
     While the present invention has been described in connection with what is considered the most practical and preferred embodiments, it is understood that this invention is not limited to the disclosed embodiments but is intended to cover various arrangements included within the spirit and scope of the broadest interpretation so as to encompass all such modifications and equivalent arrangements.