Abstract:
A method for decomposing a digital image at resolution R and MR into a set of spatial sub-bands of resolution R and MR where MR&gt;R and where the high-band at resolution MR is calculated by subtracting the filtered and up-sampled image at resolution R from the image at resolution MR and where the spatial low-band at resolution R is calculated by adding the filtered and down-sampled spatial high-band to the image at resolution R and where a rational factor for up-and down-sampling M is determined by the resolution ratio.

Description:
PRIORITY STATEMENT  
       [0001]     This application claims the benefit of U.S. Provisional Patent Application No. 60/634,114, filed on Dec. 8, 2004, in the U.S. Patent and Trademark Office, the disclosure of which is incorporated herein in its entirety by reference. 
     
    
       [0002]     The invention relates to a method for encoding a sequence of images to generate a spatially scalable representation of that sequence. A representation for a sequence of images is spatially scalable if a subset of this representation is decodable and where the output of this decoding is a sequence of images with lower spatial resolution when compared to the spatial resolution of the original sequence. Given a set of sequences which comprises of the sequence at original spatial resolution and of desired sequences at lower spatial resolution, the present invention permits spatially scalable representations of the original sequence by means of spatial sub-band decompositions.  
         [0003]     The invention relates to the inter-resolution decomposition as well as to the inter-resolution composition. The inter-resolution decomposition is employed to pairs of images at different resolutions. The decomposition generates a spatial low-band at lower resolution and a spatial high-band at higher resolution. The inter-resolution composition reverses this process.  
         [0004]     For video coding, these spatial sub-bands are coded either directly or indirectly with further decomposition. In any case, lossy coding causes quantization noise in the spatial sub-bands. The inter-resolution decomposition and the corresponding inter-resolution composition are such that the quantization noise in the spatial sub-bands has the least impact on the reconstructed high-resolution image sequence while permitting a coding scheme with perfect reconstruction.  
       BACKGROUND ART  
       [0005]     Spatial scalability of video signals can be achieved with critically sampled spatial wavelet schemes but also with overcomplete spatial representations. Critically sampled schemes struggle with the problem that critically sampled high-bands are shift-variant. Therefore, efficient motion compensation is challenging. On the other hand, overcomplete representations can be shift-invariant, thus permitting efficient motion compensation in the spatial sub-bands, but they have to be designed carefully to achieve high compression efficiency. This invention proposes an image processing method for decomposing two different spatial scales of the same image. The method is such that it minimizes the impact of the quantization noise on the reconstructed high-resolution video signal at the decoder.  
         [0006]     Rate-distortion efficient coding of image sequences can be accomplished with motion-compensated temporal transforms as proposed in the U.S. Pat. No. 6,381,276 and the corresponding academic publication “Three-dimensional lifting schemes for motion compensated video compression”, in “Proceedings of the IEEE International Conference on Acoustics, Speech and Signal Processing, Salt Lake City, Utah, May 2001, vol. 3, pp. 1793-1796. Employing the temporal transform directly to the images of the sequence may be too limiting for targeted scalability properties of video representations. In particular, desirable video coding schemes should provide efficient spatial scalability of the video signal. If a motion-compensated temporal transform is utilized, it is favorable to employ this transform to the spatial sub-bands of the input images. Such architectures achieve good spatial scalability but are burdened by degradation in rate-distortion performance. This burden is rooted in the fact that spatial decompositions utilize either critically sampled representations or overcomplete representations of the spatial sub-bands. Critically sampled representations lack the property of shift-invariance which seems to be crucial for efficient motion compensation. On the other hand, overcomplete representations can be shift-invariant, but rate-distortion efficient encoding is challenging.  
         [0007]     This invention proposes a video coding scheme with spatial scalability properties that can be interpreted as an extension of the spatial scalability concept as it is known from, e.g., the video coding standard ITU-T Recommendation H.263: The pictures of the spatial base layer are spatially up-sampled in order to obtain pictures with the same spatial resolution as the pictures of the next spatial enhancement layer. These up-sampled pictures are used to predict the pictures of the next spatial enhancement layer. But this spatial prediction is just one step in our inter-resolution decomposition which requires also a spatial update step. The spatial update step will provide the desired property that spatial prediction is not capable of.  
         [0008]     The invented multiresolution representation for images is related to the Laplacian pyramid as proposed in the academic publication by P. J. Burt and E. H. Adelson, “The Laplacian pyramid as a compact image code,”  IEEE Transactions on Communications , vol. 31, no. 4, pp. 532-540, April 1983. The basic idea of the Laplacian pyramid is the following: First, a coarse approximation of the original image is derived by low-pass filtering and down-sampling. Based on this coarse version, the original is predicted by up-sampling and filtering, and the difference is calculated as the prediction error. For the reconstruction, the signal is obtained by simply adding back the difference to the prediction from the coarse signal.  
       SUMMARY OF THE INVENTION  
       [0009]     This invention relates to a method for encoding a sequence of images to generate a spatially scalable representation of that sequence. The invention comprises the inter-resolution decomposition as well as the inter-resolution composition.  
         [0010]     Given a set of sequences containing both the one at original resolution and the desired at lower spatial resolution, the inter-resolution decomposition decomposes an image at two different resolutions into a spatial sub-band which is of lower spatial resolution and a spatial high-band which is of higher spatial resolution. The spatial high-band is calculated by subtracting the filtered and up-sampled image at lower resolution from the image at higher resolution. This is called the prediction step. The spatial low-band is calculated by adding the filtered and down-sampled spatial high-band to the image at lower resolution. This is called the update step. Note that the rational factor for up- and down-sampling is determined by the resolution ratio between the low- and high-resolution images.  
         [0011]     The inter-resolution composition reverses this process. The low-resolution image is calculated by subtracting the filtered and down-sampled spatial high-band from the spatial low-band. This is the corresponding update step. The high-resolution image is calculated by adding the filtered and up-sampled low-resolution image to the spatial high-band. This is the corresponding prediction step.  
         [0012]     The inter-resolution decomposition is an extension of the Laplacian pyramid which uses only the prediction step which is up-sampling and filtering a coarse version of the image to predict a finer version of the image. This spatial prediction is just one step in the present invention which requires also the spatial update step. This spatial update step provides the desired decomposition and composition that the classic Laplacian pyramid is not capable of.  
         [0013]     Only with this additional spatial update step, the inter-resolution decomposition and the corresponding inter-resolution composition are such that the quantization noise due to coding of the spatial sub-bands has the least impact on the reconstructed high-resolution image sequence while permitting a coding scheme with perfect reconstruction. 
     
    
     BRIEF DESCRIPTION OF THE DRAWINGS  
       [0014]     The present invention will now be described, by way of examples, with reference, if necessary, to the accompanying drawings in which:  
         [0015]      FIG. 1  illustrates the prior art, also known as the Laplacian pyramid.  
         [0016]      FIG. 2  illustrates the inter-resolution decomposition for the high-resolution image S k   (1)  and the low-resolution image {tilde over (S)} k   (0)  which is generated with the low-pass filter L(ω). The resulting low-band image is denoted by {tilde over (y)} k   (0) , the resulting high-band image by y k   (1) .  
         [0017]      FIG. 3  depicts the inter-resolution composition for the high-band image y k   (1)  and the low-band image {tilde over (y)} k   (0) .  
         [0018]      FIG. 4  depicts the decomposition of 3 resolution levels.  
         [0019]      FIG. 5  illustrates the coding system with a model for quantization noise due to lossy coding. 
     
    
     DETAILED DESCRIPTION OF THE INVENTION  
       [0020]     The invented multiresolution representation for images is related to the Laplacian pyramid as depicted in  FIG. 1 . In this prior art, a coarse approximation of the original image is derived by low-pass filtering and down-sampling. Based on this coarse version, the original is predicted by up-sampling and filtering, and the difference is calculated as the prediction error. For the reconstruction, the signal is obtained by simply adding back the difference to the prediction from the coarse signal.  
         [0021]     Now, assume that we have the k-th pictures of an image sequence in CIF resolution S k   (1) . (CIF is “Common Intermediate Format”.) For the lower resolution, we target a sequence of QCIF images and select the sampling factor M=2. (QCIF is “Quarter CIF”.) The pictures {tilde over (S)} k   (0)  in QCIF resolution are obtained by sub-sampling the corresponding ones in CIF resolution by 2. Before sub-sampling, we employ the low-pass filter L(ω). Given these pictures in QCIF and CIF resolution, we employ the inter-resolution decomposition as depicted in  FIG. 2  to obtain the spatial low-band {tilde over (y)} k   (0)  in QCIF resolution and the spatial high-band y k   (1)  in CIF resolution. A lifting implementation is used for the scheme where the prediction step uses up-sampling with factor M and filtering with P(ω), and the update step filtering with U(ω) and down-sampling with factor M. ω denotes the spatial frequency of the filter transfer function.  
         [0022]     A preferred embodiment of the method utilizes filters U that are orthogonal to P with respect to the sampling factor M. Another preferred embodiment of the method uses filters U(ω) that are orthogonal to P(ω) for spatial frequencies of the image at lower resolution, i.e.,  
           U   ⁡     (   ω   )       =       P   ⋆     (   ω   )                P   ⁡     (   ω   )            2         ,       
 
 where P*(ω) denotes the complex conjugate of P(ω). 
 
         [0023]     Depending on the filters P(ω) and U(ω), we achieve only approximately perfect de-correlation with the decomposition. We design the inter-resolution decomposition to minimize the impact of the quantization noise on the reconstructed images in CIF resolution. At the decoder, we utilize the inter-resolution composition as depicted in  FIG. 3 . Note that the images {tilde over (y)} k   (0)  in QCIF resolution (see  FIG. 2 ) are chosen to represent the spatial base layer. With that, the spatial high-band can be dropped without degrading the spatial base layer. This is a desirable feature for spatially scalable video coding. The up-sampling filter P(ω) and the down-sampling filter U(ω) correspond to the filters in  FIG. 2 . The inter-resolution composition scheme utilizes the same rational sampling factor M than the corresponding decomposition scheme.  
         [0024]     This inter-resolution decomposition is an extension of “upward prediction” as it is used in ITU-T Recommendation H.263 to achieve spatial scalability. Upward prediction only does not provide the proper decomposition. The advantages of the inter-resolution decomposition are as follows: First, additional quantization noise due to SNR scalability has the least impact on the reconstructed high-resolution video as the composition is able to suppress quantization noise efficiently. Second, the features of spatial scalability can be carefully chosen at the encoder such that the decoder is able to reconstruct efficiently the desired spatial sub-resolutions. Third, accurate motion compensation is possible in all sub-bands as we use a shift-invariant representation.  
         [0025]     The invented video coding scheme decomposes spatially the input pictures of various sizes into spatial sub-bands. This spatial decomposition is accomplished with the inter-resolution decomposition scheme. Depending on the chosen filters P(ω) and U(ω), the decorrelation properties of the inter-resolution decomposition can be close to optimal permitting an efficient rate-distortion performance. This decomposition assures an efficient embedded representation of the image sequence at various resolutions. The spatial low-band can be critically sampled to reduce the encoding/decoding complexity of the spatial base layer. On the other hand, the spatial high-bands keep their shift-invariance property and permit efficient motion compensation.  
         [0026]     The spatial decomposition of 3 resolution levels is depicted in  FIG. 4 . For example, {tilde over (s)} (0)  corresponds to the signal in QCIF resolution, {tilde over (s)} (1)  to the signal in CIF resolution, and s (2)  to the signal in 4CIF resolution while the sampling factors are M 1 =M 2 =2. {tilde over (y)} (0)  is the low-band which can be represented in QCIF resolution, {tilde over (y)} (1)  is the first high-band which can be represented in CIF resolution, and {tilde over (y)} (2)  is the second high-band which is represented in 4CIF resolution. (4CIF is “Four CIF”.) The filters in the decomposition T 1  and T 2  have to be selected such that the 3-resolution composition is able to suppress efficiently the quantization noise in the reconstructed high-resolution images. Note that the images {tilde over (y)} (0)  in QCIF resolution as well as the “I-band” images in CIF resolution are chosen to represent the spatial base layer and the first spatial enhancement layer, respectively. With that, spatial high-bands can be dropped without degrading the retained spatial sub-layers.  
         [0027]     The coding system with a model for quantization noise is illustrated in  FIG. 5  for 2 resolution levels. Assume that the quantization noise is additive, has the same variance for both low-and high-band, and is statistically independent from the image signal. With our method, the reconstructed high-resolution image may not be affected by the total sum of the quantization noise energies. If the update step with filter U(ω) is omitted (as in the case of the Laplacian pyramid), this property cannot be achieved.  
         [0028]     The sampling factor M of the scheme is not limited to the factor 2 as described so far. Preferred embodiments of the method utilize integer values larger than 1 for the sampling rate factor M. Other preferred embodiments of the method use a rational fraction M&gt;1 for the sampling rate. For that, well known methods for rational re-sampling may be employed.