Patent Publication Number: US-5629737-A

Title: Method and apparatus for subband coding video signals

Description:
This is a continuation of Ser. No. 08/028,871, filed on Mar. 10, 1993, now abandoned. 
    
    
     TECHNICAL BACKGROUND 
     The invention relates to a method for efficiently coding video signals and is more particularly directed to a method for performing said coding using Subband Coding (SBC) techniques and to a device for implementing said method. 
     PRIOR ART 
     Today one of the major goals in the world of telecommunications is the realization of a single world-wide, high speed integrated broadband communication (IBC) network. Most of recent efforts are being made to develop multimedia digital networks wherein voice, images and data, at different rates, are to be transmitted together, using common facilities. This could be achieved using convenient and efficient digital coding techniques. 
     Therefore, efficient methods for digitally coding video signals are obviously of increasing interest in a world wherein communication is a key item. 
     One of the basic problems to be solved lies in the tremendous flow of bits generated through the coding of image or video signals. Methods have been proposed for &#34;compressing&#34; said bit flow, without impairing, on the image quality obtained at the decoding of the coded video signals. But cost efficiency is also a key item, and improved methods for achieving efficient coding at reasonable cost are of particular interest. This goal may be achieved by reducing the image signal processing complexity. 
     Subband Coding (SBC) is a powerful coding technique that presents some interesting properties like its continuous frequency analysis and its ability to be used in progressive and multirate schemes. 
     First applied to speech compression, Sub Band Coding (SBC) is now quite a popular technique for image compression (&#34;Subband Coding of Images&#34; by John W. Woods, in IEEE Transactions on Acoustics, Speech and Signal Processing, Vol. ASSP-34, N-5, October 1986) and video compression (&#34;Three-dimensional Sub-band Coding of Video&#34; by G. Karlsson and M. Vetterli, in IEEE ICASSP 1988). 
     SBC consists in splitting up the frequency bandwidth of the original signal into sub-sampled subband signals, that are subsequently separately quantized. 
     Several methods have been proposed for encoding each subband signal, which are sub-optimal in terms of efficiency. 
     Actually, these methods do not take into account differential image properties. In fact, a time prediction error picture is representative of motion between time t and t+1. So, if the scene is not completely different, the image contains two types of areas: 
     Areas with no motion which are uniform (currently named background). 
     Areas with activity (currently named active areas). 
     However, a simple observation of subband signals shows that active areas are prevailing in high frequency subbands. Low frequencies (i.e. the lowest subband) contain information about uniform or slowly varying areas, while high frequencies (i.e. other subbands) represent contours. Thus, uniform subband encoding reveals to be a sub-optimal technique regarding the coder bit-rate and quality. It is easy to understand that one should encode as precisely as possible contours appearing in high frequency subbands and less precisely--or, in some cases, not at all--background. 
     A second observation that can be made on subband decomposed images is that there is some correlation between subband signals. For example, within the same spectral direction and considering a scale factor, the following subbands are highly correlated: 
     subband 2 with subband 5 
     subband 4 with subband 7 
     subband 3 with subband 6 
     This leads to use the same coding scheme for these subbands. 
     According to the observation on subband signals, one can think that the SBC coding scheme can be improved using somehow multiresolution quantization. Such a technique allows to suit quantization to the subband model which is defined. 
     OBJECTS OF THE INVENTION 
     One object of the invention is to provide an improved and efficient method for coding video signals, based on SBC coding techniques. 
     Another object of the invention is to provide an improved video subband coding method whereby individual subband signals are conveniently processed prior to being submitted to quantizing, to enable reducing the number of required quantizing levels while keeping a very good visual quality coding scheme. 
     SUMMARY OF INVENTION 
     Briefly stated, processing complexity and cost efficiency are achieved through submitting the individual subband signals to convenient activity detection prior to performing subband quantizing operations. The method is based on SBC decomposition and active blocks detection with subsequent allocation of binary resources to the different subbands according to the detected activity and to the subband. Moreover, correlation between subbands is used to reduce the computational complexity due to activity detection. 
     This and other objects, characteristics and advantages of the invention will be more readily described with reference to attached figures of a preferred embodiment. 
    
    
     BRIEF DESCRIPTION OF THE FIGURES 
     FIG. 1 is a functional representation of the overall structure of the subband coding scheme of the invention. 
     FIG. 2 is a block diagram of the subband decomposition. 
     FIG. 3 is a flow chart representing the coding scheme of the invention. 
     FIG. 4 to 6 are flow charts representing the principal operations of the coding scheme of the invention. 
    
    
     DETAILED DESCRIPTION OF PREFERRED EMBODIMENT 
     Represented in FIG. 1 is a simplified functional representation of the overall structure of the subband coding scheme of this invention. 
     Each input image frame S(t) is first split into several frequency subbands through a tree structured filter bank (1). Then in order to remove interframe time redundancy, a Differential Pulse Code Modulation (DPCM) loop is used and the predicted subband images are subtracted from the incoming subband images to give the current prediction error images (2). Activity is detected in each error prediction image (3) and active blocks are separated from background and quantized separately (4a, 4b). Quantized signals are then transmitted (5) and simultaneously submitted to inverse quantization and active blocks and background merging (6). Frame buffer (7) provides a one image delay, which is used to generate the predicted subband images, at time t-1, that are subtracted from the incoming subband images to give the prediction image errors. 
     The method for subband coding video signals will now be described in a more detailed manner. 
     Assume the original signal obtained by scanning the input image is a two-dimensional array of pixels each coded with 8 bits (value between zero and 255) arranged into X columns and Y rows (or lines). Filtering is performed as follows, for the subband splitting. 
     Each low-pass filtered component Lp(i,j) is computed for subband splitting, for instance: ##EQU1## Wherein: i and j are respectively row and column indexes. 
     CoefL are low-pass filter coefficients 
     m+1 is the number of filter coefficients 
     Image(i,j) is the value of the (i,j) located image sample (pixel) 
     NormL is a so-called low-pass scaling factor operating a level normalizing operation. 
     and * stands for the multiplication symbol. 
     In a preferred embodiment, the following values have been selected: 
     m=1 
     NormL=2 
     CoefL (0,1)=1,1 
     High-pass components Hp(i,j) are similarly computed according to the following expression: ##EQU2## Wherein: CoefH are high-pass filter coefficients 
     n+1 is the number of filter coefficients 
     Image(i,j) is the pixel at location (i,j) 
     NormH is a scaling factor operating a normalizing operation on high-pass filtered signal components. 
     In a preferred embodiment: 
     n=1 
     NormH=2 
     CoefH(0,1)=1, -1 
     For a more detailed definition of the filter coefficients, one may refer to an article by A. Croisier, D. Esteban and C. Galand, entitled: &#34;Perfect channel splitting by use of interpolation, decimation, tree decomposition techniques&#34;, Int. Conf. on Information Sciences/Systems, Patras, August 1976. 
     A more detailed description of the filtering operations, explaining the vertical and horizontal filtering, is represented in the block diagram of FIG. 2. Let us assume first that the original frame is scanned. The resulting signal is horizontally filtered through both a high-pass filter (22) and a low-pass filter (24). Each filtered signal is sub-sampled by dropping one out of two samples of each filter output to keep even the overall amount of information throughout the filtering. The low-pass filtered signal is stored in a storage location SB1(a), while the high-pass filtered signal is stored in SB2(a). One has now two subband images SB1(a) and SB2(a) herein referred to as sub-images SB1(a) and SB2(a). At the next stage of the tree structured filter bank, the two sub-images SB1(a) and SB2(a) are each split vertically into two subbands, one low-frequency band and one high-frequency band. The sub-image SB1(a) is split into two new sub-images, a low-pass filtered sub-image stored into SB1(b) and a high-pass filtered sub-image stored into SB3(b). Same operations applied to SB2(a) lead to a low-pass filtered sub-image SB2(b) and a high-pass filtered sub-image SB4(b). Accordingly, the resulting frame (b) is a four subband frame. The tree structured filtering may go on and lead to the 7 subbands SB1(c)-SB7(c). 
     Each estimated subband image is then subtracted from each subband image (DPCM loop), thereby providing a plurality of subband error prediction images. 
     Baseband (subband1) error prediction image is divided into 2×2 blocks. Each block is said to be active if it contains at least N1 pixels greater than a first threshold TRSH1. Inactive blocks are considered as background. 
     A graded activity detection is performed on subbands 2 to 4. These subbands are, once again, divided into 2×2 blocks. Two levels of activity are defined: 
     For a given position, if a block contains at least N2 pixels greater than a second threshold TRSH2 in at least one of the 3 subbands, it is said to be class 2. 
     For a given position, if a block contains at least N3 pixels greater than a third threshold TRSH3 in at least one of the 3 subbands, it is said to be class 3. 
     For a given position, if a block is not active it is said to be class 0. 
     In order to obtain an hierarchical activity detection, the thresholds are chosen so that the activity of the block increases with its class. 
     All active blocks (class 2 &amp; 3) are considered as active for subbands 2 to 4. Class 0 blocks are considered as background. 
     For subbands 5 and 6, 4×4 blocks are considered. Correlation with subbands 2 to 4 is used with a block location scale factor (2) to determine blocks activity according to the following algorithm: 
     Class 0 and 2 blocks are considered as background for these subbands. 
     Class 3 blocks are considered active and are transposed using a scale factor. 
     For each subband, active blocks and background are quantized separately. Different quantization schemes may be used: 
     all scalar quantization; 
     mixed quantization (using different quantization method according to the subband, e.g. scalar and vectorial). 
     In the first case all the blocks are quantized with a Laplacian scalar quantizer. As shown in Table I, subband 1 contains the highest amount of information so it has to be encoded precisely. Subbands 2 to 4 contain less information so quantization is less precise. In subbands 5 and 6 background is not encoded. The bit allocation of Table I gives good results. 
     
                       TABLE I                                                     
______________________________________                                    
Subband  Active Blocks     Background                                     
______________________________________                                    
1        5 Bits            1 Bit                                          
2        4 Bits            1 Bit                                          
3        4 Bits            1 Bit                                          
4        4 Bits            1 Bit                                          
5        3 Bits            Not encoded                                    
6        3 Bits            Not encoded                                    
______________________________________                                    
 
    
     Referring to FIG. 3 and to Table II, the general coder structure can be described as follows: 
     TABLE II 
     S(t,n) Input image of n pixels at time t 
     S i  (t,n i ) Subband image i of n i  pixels at time t 
     E i  (t,n i ) Error subband image i of n i  pixels at time t 
     S i  (t,n i ) Estimated subband image i of n i  pixels at time t 
     E i   a  (t,n i ) Set of active blocks detected into E i  (t,n i ) 
     E i   b  (t,n i ) Set of background blocks detected into E i  (t,n i ) 
     E i   a  (t,n i ) Set of coded active blocks detected into E i  (t,n i ) 
     E i   b  (t,n i ) Set of coded background blocks detected into E i  (t,n i ) 
     E i   a  (t,n i ) Set of decoded active blocks detected into E i  (t,n i ) 
     E i   b  (t,n i ) Set of decoded background blocks detected into E i  (t,n i ) 
     E i  (t,n i ) Reconstructed error subband image i of n i  pixels at time t after coding and decoding of active and background blocks 
     b i ,u,v (m) Mth pixel in block b of position u, v into subband error image E i  (t,n i ) (u=1 . . . 32, v=1 . . . 32, blocks size is 2×2 for subbands 1 to 4 (so m=1 . . . 4) and 4×4 for subbands 5 to 6 (so m=1 . . . 16)). 
     P(t,u,v) Table of block classes for each position u, v in subband images at time t. 
     b i ,u,v a  Active block corresponding to position u, v into subband error image E i  (t,n i ) 
     b i ,u,v b  Background block corresponding to position u, v into subband error image E i  (t,n i ) 
     nba1 Counter of number of active blocks in subband 1 
     nba2 Counter for number of active blocks in subband 2 to 4 
     nba3 Counter for number of active blocks in subband 5 to 6 
     N1,N2,N3 Fixed values for active blocks detection (minimum numbers of pixels for activity state consideration 
     TRSHx Fixed values for active blocks detection (Thresholds) 
     Initialization: (30) The estimated subband image at time 0, S i  (0, n i ) is initialized with the 7 decomposed subbands of input image at time 0, S(0,n). 
     Subband decomposition of input image: (31). The input image S(t,n) is decomposed into seven subbands using QMF filters. The result is stored in S i  (t,n i ). 
     Prediction error computation: (32). The result is stored in E i  (t,n i ). 
     Activity detection: (33). A graded activity detection is performed on subbands 1 to 4 of the prediction error subband image. The result is stored in table P(t,u,v). 
     Background and active blocks separation: (34). According to the results given by the activity detection algorithm active blocks and background are separated for each subband. 
     Quantization: (35a) and (35b). Active blocks and background are separately quantized with a given method (e.g. scalar or vectorial). The number of levels applied depends on the activity (background or active block) and on the subband number. 
     Transmission: (36). The quantized samples and the block class array are transmitted to the decoder. 
     Inverse quantization: (37a) and (37b). This is exactly the inverse of the quantization step. 
     Background and active blocks merging: (38). According to the results given by the activity detection algorithm, the decoded active blocks and background are merged for each subband. 
     Estimated subband image computation: (39). 
     Referring now to FIG. 4, the activity detection algorithm will be described. The subbands 1 to 4 of the prediction error image split into 7 subbands are input. 
     The block class table P(t,.,.) is initialized to 0 (40). 
     The first class block detection is performed (41). Therefore, for each block of subband 1, the number of pixels having values greater then TRSH1 is counted. If the current block contains at least N1 pixels greater then said threshold this block is set to class 1. 
     Then classes 2 and 3 block detection is achieved (42). For each block and for each pixel of the current block, the algorithm (420) increments by 1: 
     counter nba2 if the current pixel is greater then TRSH2 in at least one of the subbands 2 to 4. 
     counter nba3 if the current pixel is greater then TRSH3 in at least one of the subbands 2 to 4. 
     If nba2 is greater then N2 then the current block is set to class 2. If nba3 is greater then N3 then the current block is set to class 3. 
     The output data of the activity detection algorithm is the block class array, namely P(t,u,v). 
     Referring now to FIG. 5, the separation algorithm will be described. The prediction error image split into 7 subbands and the block class array computed by the activity detection algorithm are input. 
     For each block: 
     if the current block is class 0, said block is copied for all subbands into E i   b  (t,n i ), i=1 . . . 6 (50). 
     if the current block is class 1, said block is copied into E i   a  (t,n i ) for subband 1 and into E i   b  (t,n i ) i=2 . . . 6 for subbands 2 to 6 (51). 
     if the current block is class 2, said block is copied into E i   a  (t,n i ), i=1 . . . 4 for subbands 1 to 4 and into E i   b  (t,n i ) i=5, 6 for subbands 5 and 6 (52). 
     if the current block is class 3, said block is copied for all subbands into E i   a  (t,n i ), i=1 . . . 6. (53). 
     Notice that, due to the fact that subband 7 is discarded, this subband&#39;s blocks are never copied. 
     The output data of the active blocks and background separation algorithm are the sets containing active and background blocks. 
     FIG. 6 represents the merging algorithm. It has for input the set of decoded active and background blocks and the block class array computed by the activity detection algorithm. 
     First, subband 7 of the reconstructed error subband image is set to 0 as this subband was discarded by separation algorithm (60). 
     The continuation of the algorithm is exactly the inverse of the separation algorithm. 
     The output data of the active blocks and background merging algorithm is the reconstructed error subband image. 
     For the reconstruction filters at the receiver, the low-pass and high-pass components of the estimated subband image at time t are computed respectively, according to: ##EQU3## wherein: RNormL=1 
     RCoefL(0,1)=1, 1 
      (i,j) reconstructed estimated image at time t, based on Lp (i,j) original image subband and: ##EQU4## wherein:  (i,j) reconstructed estimated image at time t based on Mp (i,j) original image subband 
     RNormH=1 
     RCoefH(0,1)=1,-1 
     Repeating the subband recombining through the inverse tree-shaped arrangement as shown in FIG. 1, leads to getting back the full bandwidth original image, or more precisely a synthesized image. 
     Although the description of the preferred embodiment was performed by placing subband decomposition outside the DPCM loop, the proposed method can also be applied by placing subband decomposition inside the DPCM loop.