Abstract:
An original image is up-sampled to a final image by constructing at least two sub-banded filtered images of the original image with 2D wavelet-based decomposition filters, each filtered image being of the same resolution as the original image. Each sub-banded filtered image is then mapped into a larger filtered image of the same size as the final image. Pixels in each larger filtered image which were not mapped in from the sub-banded filtered images are interpolated or left blank. The larger filtered images are then filtered with 2D reconstruction filters and combined to form the final up-sampled image. The invention has the advantage that high quality up-sampled images can be created in real time suitable for high definition video.

Description:
FIELD OF THE INVENTION 
       [0001]    This invention relates to the field of image processing, and more particularly to a method of up-sampling images, and in particular video images. The method is suitable for converting standard video to high definition video especially in real time applications such as video conferencing. 
       BACKGROUND OF THE INVENTION 
       [0002]    In image processing, up-sampling is used to magnify an entire image or to zoom into a part of an image. Up-sampling involves using some technique to fill in empty pixels when an image of a given resolution is displayed at a higher resolution. When the image is a video frame, the up-sampling must be performed in real-time. The term “real-time” typically means being capable of up-sampling an image with resolution of 960×540 to 1920×1080 (full high definition), with frame rate of 30 fr/sec. 
         [0003]    Currently, the most commonly used up-sampling methods are nearest neighbor, bilinear interpolation, and bicubic interpolation (applied directly to the original image). Among these three methods, the nearest neighbor gives the coarsest visual quality with grid effects along edges (especially along diagonal edges). Bilinear and bicubic interpolations give images with more natural edges, but with blurred visual quality. 
         [0004]    Another more advanced up-sampling method utilizes the Lanczos filter. See, for example, Claude E. Duchon (August 1979). “ Lanczos Filtering in One and Two Dimensions”. Journal of Applied Meteorology  18 (8): pp. 1016-1022. Usually, at the level of up-sample-by-2, the visual quality of the up-sampled image using Lanczos filter is better than that of bilinear and bicubic interpolation, but is still noticeably blurred compared to the original image. 
         [0005]    There are even more advanced and complex algorithms for image up-sampling, e.g., the level set-based algorithm, which iteratively controls the contour evolution in the up-sampling process. However, such methods usually require a very long time to up-sample an image (for given computing power), and therefore are not suitable for real-time applications. 
         [0006]    There is an up-sample-by-2 method, which is based on one-dimensional (1D) wavelet filter bank, which is suitable for real-time applications under current hardware/software conditions. The method is described in paper: Image Up-Sampling Using Discrete Wavelet Transform, Ping-Sing Tsai and Tinku Acharya, Proceedings of Joint Conference on Imformation Sciences, 2006. It is also described in U.S. Pat. No. 6,377,280. 
         [0007]    This method is briefly described with reference to  FIG. 1  and in a way that parallels the description of the present invention. As shown in  FIG. 1 , an original image I with resolution W×H is put through a wavelet decomposition process, in which a low-pass filter L 1  and a high-pass filter H 1  are applied to each ROW of the image followed by down-sample-by-2 in each ROW. Then, with two intermediate images from above operations, the low-pass filter L 1  and the high-pass filter H 1  are applied to each COLUMN of the two intermediate images respectively, followed by down-sample-by-2 in each COLUMN. Thus, after these filtering and down-sampling operations in ROW and COLUMN directions, there are four sub-band images LL (low-pass—low-pass), LH (low-pass—high-pass), HL (high-pass—low-pass), and HH (high-pass—high-pass), each with resolution 
         [0000]    
       
         
           
             
               1 
               2 
             
              
             W 
             × 
             
               1 
               2 
             
              
             
               H 
               . 
             
           
         
       
     
         [0000]    Up until now, these operations are the same as in a standard 1D wavelet filter bank decomposition (known at the time of the invention). Tsai and Acharya modified the structure of the four sub-bands for the purpose of up-sampling by 2. For the two sub-bands LH, HL, they increase their resolution by 2, i.e. from 
         [0000]    
       
         
           
             
               
                 
                   1 
                   2 
                 
                  
                 W 
                 × 
                 
                   1 
                   2 
                 
                  
                 H 
               
                
               
                 W 
                 × 
                 H 
               
             
             , 
           
         
       
     
         [0000]    and put each pixel in the original sub-bands to the upper-left pixel location of the corresponding 2×2 pixel group in the up-sampled sub-bands. For sub-band LL, Tsai and Acharya discard the LL from the decomposition filter and replace it with the original image after applying a scaling factor to it, and therefore the resolution of LL also increased from 
         [0000]    
       
         
           
             
               
                 1 
                 2 
               
                
               W 
               × 
               
                 1 
                 2 
               
                
               H 
             
              
             
               W 
               × 
               
                 H 
                 . 
               
             
           
         
       
     
         [0000]    For sub-band HH, Tsai and Acharya just replaced it using an all zero image with resolution W×H. 
         [0008]    Now, the four modified sub-bands (LL 2 , LH 2 , HL 2  and HH 2 ) with resolution W×H are put through a standard reconstruction process using wavelet filter bank, as shown in  FIG. 1 , in which each sub-band is up-sampled-by-2 for each COLUMN. Then, the up-sampled LL 2  and LH 2  (HL 2  and HH 2 ) are filtered with a low-pass filter L 2  and a high-pass filter H 2  respectively, for each COLUMN, and the filtering results are summed together, resulting in two intermediate images with resolution W×2H. These two intermediate images are up-sampled-by-2 for each ROW, and put through the low-pass filter L 2  and the high-pass filter H 2  respectively, and summed together as the final up-sampled image I x2  with resolution 2W×2H. 
         [0009]    While this method is capable of working in real-time, there are noticeable artifacts along edges. 
         [0010]    Another wavelet-based up-sampling method is described in the paper Edge-preservation resolution enhancement with oriented wavelets, V. Velisavljevic, Proceedings of IEEE Int. Conf. on Image Proc. (ICIP), 2008. This method applies a 1D wavelet filter to five directions in the image, and estimates a directional map by comparing the filtering results on five directions for each pixel. The up-sampling process is based on this estimated directional map. The algorithm works well in preserving the original shape of the edges, but at the expense of higher complexity. It is therefore not suitable for real-time applications of HD video under current hardware/software conditions. 
       SUMMARY OF THE INVENTION 
       [0011]    An object of the invention is to up-sample an image in real-time with very good visual quality so that the invention can be used for up-sampling a standard definition video to high definition video. The term “very good visual quality” means the up-sampled image should have a degree of crispness similar to the original image without adding obvious artifacts. 
         [0012]    According to the present invention there is provided a method of up-sampling an original image to a final up-sampled image, comprising: constructing at least two sub-banded filtered images of the original image with 2D wavelet-based decomposition filters, each filter image being of the same resolution as the original image; mapping each of the sub-banded filtered images into a larger filtered image of the same size as the final image, wherein pixels in each larger filtered image that were not mapped in from the sub-banded filtered images are interpolated or left blank; filtering the larger filtered images with 2D reconstruction filters; and combining the outputs of the 2D reconstruction filters to form the final up-sampled image. 
         [0013]    In one embodiment the invention provides a method of up-sampling, i.e. zooming in, a digital image by first building at least two filtered images of the original image using decomposition filters. Each of the filtered images, which are the same size as the original, is then mapped into a larger filtered image. The larger filtered images are each equal in size to the final image size. Pixels in each larger filtered image which were not mapped in are interpolated from mapped pixels or left blank. Finally the larger filtered images are filtered again using reconstruction filters and combined to form the up-sampled image. All filters are different and are based on the theory of perfect reconstruction wavelet filter banks. In one embodiment quincunx filters are used. 
         [0014]    The invention is wavelet-based. Unlike prior art wavelet-based up-sampling methods in which 1D wavelet filters are used with at least four sub-bands involved, the invention uses non-separable 2D wavelet filters (quincunx filter bank) and in one embodiment only has two sub-bands involved. 
         [0015]    Unlike the method of Tsai and Acharya, embodiments of the invention do not discard sub-band pixel values in the wavelet decomposition stage. One diagonal pixel is interpolated for the two sub-bands before reconstruction. For the up-sampling of the low-pass filtered sub-band, the invention does not require the use any scaled pixel values of the original image. 
         [0016]    Unlike the above two wavelet-based up-sampling methods in which the same wavelet reconstruction filters are used compared to the standard wavelet filter bank, embodiments of the invention adjust the reconstruction wavelet filters in order to bring more crisp up-sampled images. 
         [0017]    In another aspect the invention provides an apparatus for up-sampling an original image to a final up-sampled image, comprising: a plurality of 2D wavelet-based decomposition filters for constructing at least two sub-banded filtered images of the original image with, each filter image being of the same resolution as the original image; up-sampling units for mapping each of the sub-banded filtered images into a larger filtered image of the same size as the final image, wherein pixels in each larger filtered image that were not mapped in from the sub-banded filtered images are interpolated or left blank; 2D reconstruction filters for processing the larger filtered images; and a combiner to form the final up-sampled image from the filtered images output by the 2D reconstruction filters. 
     
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         [0018]    The invention will now be described in more detail, by way of example only, with reference to the accompanying drawings, in which:— 
           [0019]      FIG. 1  is a block diagram of a prior art up-sampling system; 
           [0020]      FIG. 2  is a block diagram of an up-sampling system in accordance with an embodiment of the invention; 
           [0021]      FIG. 3  is a block diagram of a video display system; 
           [0022]      FIGS. 4   a  to  4   d  show the filter coefficients for various filters; 
           [0023]      FIGS. 5   a  and  5   b  shows the filtered image and the up-sampled filter image respectively; and 
           [0024]      FIGS. 6   a  and  6   b  show the reconstruction filter coefficients; and 
       
    
    
     DETAILED DESCRIPTION OF THE INVENTION 
       [0025]    One embodiment of the invention will now be described. A typical video display system is illustrated in  FIG. 3 . Video endpoint  304  comprises a processor  306 , memory  314  and display subsystem  308 . Video Source  302 , typically a distant video endpoint, transmits video signal  320  via network interface  312  to endpoint  302  where each video frame is temporarily stored in memory  314 . The frame is subsequently retrieved from memory  314  and displayed by display system  308 , after which it is discarded. In applying the invention each received frame is first processed to produce a larger image, e.g. twice the size, before it is displayed. 
         [0026]    The basic structure of the invention is shown in  FIG. 2 . The input image I  202  with resolution W×H is filtered by low-pass 2D filter F 0   204  and high-pass 2D filter G 0   220 , resulting in intermediate images I F0    206  and I G0    222 , both with resolution W×H, the same as the input image  202 . 
         [0027]    Both filters  204  and  220  are non-separable 2D wavelet quincunx filters. The theory behind the quincunx filter is described in “Perfect reconstruction filter banks for HDTV representation and coding” by M. Vetterli, J. Kova{hacek over (c)}ević and D. J. LeGall published in Image Comm. Journal, special issue on HDTV, vol. 2, no. 3, October 1990, pp. 349-364, the contents of which are herein incorporated by reference. The coefficients used in filter  204  are shown in  FIG. 4   a , and for filter  220  are shown in  FIG. 4   b .  FIGS. 4   c  and  4   d  show corresponding reconstruction filter masks as described in the paper. These reconstruction filter masks are modified for use in the invention as will be described later. 
         [0028]    Returning to  FIG. 2 , without down-sampling or discarding any pixels, the two sub-bands I F0    206  and I G0    222  are each put through a 2D up-sampling and interpolation process. 
         [0029]    The up-sampling and interpolation process is described with reference to  FIG. 5 , where  FIG. 5   a  illustrates a filtered image, either  206  or  204 , W pixels wide and H pixels high.  FIG. 5   b  illustrates the corresponding up-sampled interpolated image, either  210  or  226  respectively. It is twice the size, i.e. 2W pixels wide and 2H pixels high. The interpolation process determines the value of pixels on the diagonal not mapped from the filtered image. 
         [0030]    By way of example,  FIG. 5   a  shows any 2×2 group of pixels in I F0  (or I G0 ), with labels and coordinates as p 1 ( x,y ), p 2 ( x+ 1,y), p 3 ( x,y+ 1), p 4 ( x+ 1,y+1). In the up-sampled images I F0     —     up  and I G0     —     up , p 1 , p 2 , p 3  and p 4  are mapped into coordinates at (2*x−1, 2*y−1), (2*x+1, 2*y−1), (2*x−1, 2*y+1) and (2*x+1, 2*y+1) respectively. That is to say the value of p 1  in  FIG. 5   b  is the same as the value of p 1  in  FIG. 5   a . Then, for the diagonal pixel p 5  at coordinates (2*x, 2*y), we interpolate it based on the values of p 1 , p 2 , p 3  and p 4  using the following method: 
         [0031]    calculate dif 1 =|p 1 −p 4 |, and dif 2 =|p 2 −p 3 | 
         [0032]    if (dif  1 &gt;dif  2 ) 
         [0033]    then 
         [0000]    
       
         
           
             
               p 
                
               
                   
               
                
               5 
             
             = 
             
               
                 
                   p 
                    
                   
                       
                   
                    
                   2 
                 
                 + 
                 
                   p 
                    
                   
                       
                   
                    
                   3 
                 
               
               2 
             
           
         
       
     
         [0034]    else if (dif  1 &lt;dif  2 ) 
         [0035]    then 
         [0000]    
       
         
           
             
               p 
                
               
                   
               
                
               5 
             
             = 
             
               
                 
                   p 
                    
                   
                       
                   
                    
                   1 
                 
                 + 
                 
                   p 
                    
                   
                       
                   
                    
                   4 
                 
               
               2 
             
           
         
       
     
         [0036]    else 
         [0000]    
       
         
           
             
               p 
                
               
                   
               
                
               5 
             
             = 
             
               
                 
                   p 
                    
                   
                       
                   
                    
                   1 
                 
                 + 
                 
                   p 
                    
                   
                       
                   
                    
                   2 
                 
                 + 
                 
                   p 
                    
                   
                       
                   
                    
                   3 
                 
                 + 
                 
                   p 
                    
                   
                       
                   
                    
                   4 
                 
               
               4 
             
           
         
       
     
         [0037]    The above up-sampling and interpolation procedure is iteratively applied to each pixel on the diagonal. The remaining pixels in the rows and columns containing the directly mapped pixels from the filtered image remain zero in value in the preferred embodiment of the invention. We now have two adjusted sub-bands I F0     —     up    210  and I G0     —     up    226  each with resolution 2W×2H. 
         [0038]    This process is referred to as up-sampling and interpolate diagonal element, and is illustrated in  FIG. 2  by blocks  208  and  224 . 
         [0039]    In the final stage each adjusted sub-band  210  and  226  is processed through reconstruction filters  212  and  228  respectively and then additively mixed in adder  214  (i.e. the value of each pixel p 212 (x,y) resulting from 212 is added to the value of the corresponding pixel p 228 (x,y) resulting from 228 to yield the corresponding pixel p(x,y) in the up-sampled image  216 . 
         [0040]    The reconstruction filter masks used in the embodiment of the invention are extended versions of the 2D reconstruction filter masks illustrated in  FIGS. 4   c  and  4   d . The extended filter masks are illustrated in  FIG. 6 . The mask shown in  FIG. 6   a  is used in filter F 1 _ext  212  and the mask shown in  FIG. 6   b  is used in filter G 1 _ext  228 . Certain values are shown in the accompanying table in  FIG. 6   b  for clarity. 
         [0041]    The need for extended filter masks and how they are created follows. 
         [0042]    Filter masks F 1 _ext and G 1 _ext are up-sample-by-2 and interpolated versions of F 1  and G 1  respectively (note that the up-sample and interpolation method used to create F 1 _ext and G 1 _ext are different from what we described above for the up-sample of the image itself). 
         [0043]    The theory of perfect reconstruction teaches how to precisely reproduce an image of the same size (i.e. same number of pixels) as the original after first down-sampling into sub-bands and then subsequently up-sampling and merging the sub-bands. Since it is an object of the invention to produce an image of larger size (i.e. more pixels) than the original, this underlying theory must be adapted. This embodiment does not down-sample nor does it discard any pixels from the two sub-bands I F0  and I G0 . Therefore, in the reconstruction stage, in order to keep the correspondences between the sub-band pixels and filter coefficients as in the original reconstruction filter bank (not for up-sampling purposes), the 2D reconstruction filters F 1  and G 1  are extended, and the empty filter coefficient locations are filled using bicubic spline interpolation. 
         [0044]    Based on lab tests and subjective opinions bicubic spline interpolation increases the degree of crispness of the resulting up-sampled-by-2 images. The values of a, b, c, d, e, g, h etc. are not restricted to the values shown in  FIG. 6  but reflect the best embodiment of the invention known at this time. Other values could be used if better results can be obtained particularly if up-sampling by ratio other than two. 
         [0045]    The invention might be further developed for higher up-sampling ratio, by changing the structure of the filter bank, e.g., adding more filters which are based on M-channel wavelet filter bank. 
         [0046]    It should be appreciated by those skilled in the art that any block diagrams herein represent conceptual views of illustrative circuitry embodying the principles of the invention. For example, a processor may be provided through the use of dedicated hardware as well as hardware capable of executing software in association with appropriate software. When provided by a processor, the functions may be provided by a single dedicated processor, by a single shared processor, or by a plurality of individual processors, some of which may be shared. Moreover, explicit use of the term “processor” should not be construed to refer exclusively to hardware capable of executing software, and may implicitly include, without limitation, digital signal processor (DSP) hardware, network processor, application specific integrated circuit (ASIC), field programmable gate array (FPGA), read only memory (ROM) for storing software, random access memory (RAM), and non volatile storage. Other hardware, conventional and/or custom, may also be included.