Abstract:
Provided are a method of and an system for coding a grouped zerotree wavelet image having high coding efficiency regardless of the scale of a wavelet transform. According to an embodiment of the present invention, a method of coding an input image to a bitstream by using a zerotree wavelet transform, the method comprises merging a plurality of adjacent zerotrees, and coding the merged zerotrees to one symbol and outputting the symbol. The method further comprises transforming the input image to a wavelet domain having a plurality of wavelet coefficients via the zerotree wavelet transform, and generating the plurality of adjacent zerotrees each having the plurality of wavelet coefficients.

Description:
BACKGROUND OF THE INVENTION  
         [0001]    1. Field of the Invention  
           [0002]    The present invention relates to a method of and an apparatus for compressing a digital video signal, and more particularly, to a method of and an apparatus for coding a zerotree wavelet image based on a zero tree wavelet transform.  
           [0003]    2. Description of Related Art  
           [0004]    Image transmission and storage are important for Internet and multimedia services. However, since image transmission and storage systems have limited bandwidths and memories, image coding is important to the efficiency, speed, and costs of image transmission and storage systems.  
           [0005]    Image coding standard H.263 shows reliable coding efficiency. The moving picture experts group (MPEG)-4 and joint photographic experts group (JPEG)-2000 have also introduced various coding techniques for improved coding efficiency.  
           [0006]    In particular, in the MPEG-4 and the JPEG-2000, to achieve coding efficiency, wavelet transforms have been considered as a replacement for existing discrete cosine transforms (DCT).  
           [0007]    In MPEG-4, coding employing the wavelet transform (hereinafter, referred to as wavelet coding) has been used in texture coding to achieve scalability. Also, in the JPEG-2000, the wavelet coding is used to maximize the coding efficiency by preventing images of various sizes, particularly, very large images, from being blocked. Blocking refers to artificial frontiers in images coding by discrete cosine transforms, such as MPEG-4 and H.263.  
           [0008]    Embedded Zerotree Wavelet (EZW) coding (J. M. Shapiro) and Set Partitioning in Hierarchical Trees (SPIHT) coding (A. Said and W. A. Pearlman) are efficient image coding techniques that attempt to eliminate blocking.  
           [0009]    These coding techniques can organize a plurality of wavelet coefficients into one symbol, i.e., a zerotree, using a spatial location and orientation of a wavelet coefficient shown in FIG. 1 to improve compression efficiency.  
           [0010]    However, in general, MPEG-4 and JPEG-2000 systems, which are based on a discrete wavelet transform, are limited and the number of wavelet decompositions is fixed. Thus, when the size of an image varies, or the number of wavelet decompositions varies depending on the characteristics of the image, the coding efficiencies of the MPEG-4 and JPEG-2000 systems are compromised.  
           [0011]    Therefore, a need exists for a method and apparatus for coding a grouped zerotree wavelet image having high coding efficiency irrespective of the scale of a wavelet transform.  
         SUMMARY OF THE INVENTION  
         [0012]    Preferred embodiments of the present invention will be described below in more detail, with reference to the accompanying drawings:  
           [0013]    According to an embodiment of the present invention, a method of coding an input image to a bitstream by using a zerotree wavelet transform, the method comprises merging a plurality of adjacent zerotrees, and coding the merged zerotrees to one symbol and outputting the symbol.  
           [0014]    The method further comprises transforming the input image to a wavelet domain having a plurality of wavelet coefficients via the zerotree wavelet transform, and generating the plurality of adjacent zerotrees each having the plurality of wavelet coefficients.  
           [0015]    According to an embodiment of the present invention, a method of coding an input image to a bitstream by using a wavelet transform for generating a plurality of wavelet trees each having a plurality of wavelet coefficients comprises (a) determining whether each of the wavelet trees is a zero tree, (b) determining adjacent zerotrees, (c) merging the adjacent zerotrees, and (d) coding merged zerotrees to one symbol and outputting the symbol.  
           [0016]    If it is determined in step (a) that each of the wavelet trees is not a zero tree, wavelet coefficients belonging to the each of the wavelet trees are separately coded and output.  
           [0017]    If it is determined in step (a) that one zero tree exists, the zerotree is coded and output.  
           [0018]    According to an embodiment of the present invention, a computer-readable recording medium is provided in which a program for executing a method of coding an input image to a bitstream by using a zerotree wavelet transform is recorded. The method comprises merging a plurality of adjacent zerotrees, and coding the merged zerotrees to one symbol and outputting the symbol.  
           [0019]    According to another embodiment of the present invention, a computer-readable recording medium is provided in which a program for executing a method of coding an input image to a bitstream by using a wavelet transform for generating a plurality of wavelet trees each having a plurality of wavelet coefficients is recorded. The method comprises (a) determining whether each of the wavelet trees is a zerotree, (b) determining adjacent zerotrees, (c) merging the adjacent zerotress, and (d) coding merged zerotrees to one symbol and outputting the symbol.  
           [0020]    If it is determined in step (a) that each of the wavelet trees is not a zerotree, wavelet coefficients belonging to each of the wavelet tree are separately coded and output.  
           [0021]    If it is determined in step (a) that one zerotree exists, the zerotree is coded and output.  
           [0022]    According to an embodiment of the present invention, an encoder of coding a zerotree wavelet-image, the encoder comprises a discrete wavelet transform circuit which wavelet-transforms an input image to a wavelet domain having a plurality of wavelet coefficients, a zerotree generator which generates a plurality of zerotrees corresponding to spatial locations and orientations of the plurality of wavelet coefficients, and a zerotree coder which merges a plurality of adjacent zerotrees, codes merged zerotrees to one symbol, and outputting the symbol.  
           [0023]    According to another embodiment of the present invention, an encoder of coding a zerotree wavelet image, the encoder comprises a discrete wavelet transform circuit which wavelet-transforms an input image to a wavelet domain having a plurality of wavelet coefficients, and a zerotree coder which if a wavelet tree corresponding to spatial locations and orientations of the plurality of wavelet coefficients is a zerotree, merges predetermined wavelet zerotrees adjacent to the zerotree, codes merged wavelet zerotrees to one symbol, and outputs the symbol. 
       
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS  
       [0024]    The above object and advantages of the present invention will become more apparent by describing in detail preferred embodiments thereof with reference to the attached drawings in which:  
         [0025]    [0025]FIG. 1 is a view showing a tree of general wavelet coefficients;  
         [0026]    [0026]FIG. 2 is a view showing a tree and symbols of wavelet coefficients according to an embodiment of the present invention;  
         [0027]    [0027]FIG. 3 is a block diagram of an encoder according to an embodiment of the present invention;  
         [0028]    [0028]FIG. 4 is a detailed block diagram of an optimum zerotree generator of FIG. 3;  
         [0029]    [0029]FIGS. 5A through 5C are views showing examples of a zerotree group generated by the optimum zero tree generator of FIG. 3;  
         [0030]    [0030]FIG. 6 is a flowchart of a method of coding an input image to a bit stream using a zerotree wavelet transform according to an embodiment of the present invention;  
         [0031]    [0031]FIG. 7 is a graph showing bit per pixel (BPP) and peak signal to noise ratio (PSNR) for comparing a prior art method and a method according to an embodiment of the present invention when transforming a lena image to three levels;  
         [0032]    [0032]FIG. 8 is a graph showing BPP and PSNR for comparing a prior art method and a method according to an embodiment of the present invention when transforming a lena image to four levels;  
         [0033]    [0033]FIG. 9 is a graph showing coding efficiency when coding a barbara image using the prior art method; and  
         [0034]    [0034]FIG. 10 is a graph showing coding efficiency when coding a barbara image using a method according to an embodiment of the present invention. 
     
    
     DETAILED DESCRIPTION OF PREFERRED EMBODIMENTS  
       [0035]    Hereinafter, the present invention will be described in detail by explaining a preferred embodiment of the present invention with reference to the attached drawings. Like reference numerals in the drawings denote the same elements.  
         [0036]    [0036]FIG. 2 is a view showing a tree and symbols of wavelet coefficients for explaining a method according to an embodiment of the present invention. For the convenient explanation, symbols used in this specification will be now defined with reference to FIG. 2. n 1  and n 2  denotes the size of an image, and D(i, j) denotes a set of coefficients of all descendants of nodes or wavelet coefficients (i, j), {all descendants of c ij }. O(i, j) denotes a set of coefficients of offspring of a node (i, j), {the four offspring of c ij }, and L(i, j) denotes a set of coefficients D(i, j) minus O(i, j), D(i, j)-O(i, j). Here, (i, j) are coordinates of pixels.  
         [0037]    A set partitioning rule will now be described. Initial partitioning is achieved for sets {(i, j)} and D(i, j) for {(i, j)∈H}. If the set D(i, j) is significant, the set D(i, j) is partitioned into four sets which are L(i, j) and {(k, 1)∈0(i, j)}. If the set L(i, j) is significant, the set L(i, j) is partitioned into four sets D(k, 1) which are {(k, 1)∈0(i, j)}.  
         [0038]    H represents a set of coordinates of initial tree roots. In other words, H is a set of coordinates of spatial orientation tree roots.  
         [0039]    A list of insignificant sets (LIS) represents a list of sets of coefficients smaller than a threshold value. In other words, the LIS is a list of coordinates of zerotrees.  
         [0040]    Here, type A denotes a case where coefficients belonging to the set D(i, j) are smaller than the threshold value. Also, depth_x and depth_y is a number of zerotrees splitting a subband along each direction.  
         [0041]    Type B denotes a case where coefficients belonging to the set L(i, j) are smaller than the threshold value.  
         [0042]    Accordingly, referring to FIG. 2, depth_x=0 and depth_y=0 indicates that one zerotree root exists in each of HL 3 , LH 3 , and HH 3 . depth_x=1 or depth_y=1 means that two zerotree roots exist in each of HL 3 , LH 3 , and HH 3 . depth_x=1 and depth_y=1 mean that four zerotree roots exist in each of HL 3 , LH 3 , and HH 3 .  
         [0043]    A list of insignificant pixels (LIP) is a list of coefficients smaller than the threshold value, i.e., a list of coordinates of all wavelet coefficients.  
         [0044]    A list of significant pixels (LSP) is a list of coefficients larger than the threshold value. Levels denote wavelet transform levels.  
               Hx   =     n1     2   level              
          Hy   =     n2     2   level              
          Sx   =     n1     2     level   +   depth_x                
          Sx   =     n2     2     level   +   depth_y                   (   1   )                               
 
         [0045]    wherein, Hx represents a lengthwise size x of the highest subband, Hy represents a widthwise size y of the highest subband, Sx represents a search range along a lengthwise direction x in a list, and Sy represents a search range along a widthwise direction y in the list.  
                       Sn        (     x   ,   y     )       =   1     ,             max     x   +   Sxy   +   Sy           i   =   x     ,     j   =   y                              {          C     (     i   ,   j     )            }     ≥     2   n                                0   ,                         otherwise   ,                 (   2   )                               
 
         [0046]    wherein, Sn(x, y) is a set of separate pixels.  
         [0047]    Hereinafter, a method according to an embodiment of the present invention will be described in detail. A method according to an embodiment of the present invention is based on set partitioning in hierarchical trees (SPIHT).  
         [0048]    1. Initialization  
         [0049]    Equation 3 is output from an initialisation process.  
           n=└log   2 ( max   (i,j)   {|C   (i,j) |}┘  (3)  
         [0050]    wherein, └ ┘ represents the maximum integer not larger than {|C (i,j) |}.  
         [0051]    The LSP is set to an empty list, { }, depth_x is set to zero, depth_y is set to zero, and each coordinate {(i, j)∈H} is added to the LIP. For depth_x is zero and depth_y is zero, each coordinate in the set {(i, j)∈H} of type A is added to the LSP.  
         [0052]    2. Sorting Pass  
         [0053]    2.1. The following methods are performed for each pixel or entry (i, j) in the LIP.  
         [0054]    2.1.1. Sn(i, j) is output;  
         [0055]    2.1.2. If Sn(i, j)=1, Sx=1, and Sy=1, coordinates (i, j) move to the LSP and signs of C i,j  are output.  
         [0056]    If Sn(i, j)=1, Sx=1, and Sy≠1,  
         [0057]    depth_y is increased by 1;  
         [0058]    Coordinates (i, j) and  
       (     i   ,     (     j   +       H                 y       2   depth_y         )       )                         
 
         [0059]    are added to the end of the LIP;  
         [0060]    Coordinates (i, j) are removed from the LIP;  
         [0061]    If Sn(i, j)=1, Sx≠1, and Sy=1,  
         [0062]    depth_x is increased by 1;  
         [0063]    Coordinates (i, j) and  
       (       (     i   +       H                 x       2   depth_x         )     ,   j     )                         
 
         [0064]    are added to the end of the LIP;  
         [0065]    Coordinates (i, j) are removed from the LIP;  
         [0066]    If Sn(i, j)=1, Sx≠1, and Sy≠1,  
         [0067]    depth_x and depth 13  y are each increased by 1;  
         [0068]    Coordinates (i, j),  
         (     i   ,     (     j   +       H                 y       2   depth_y         )       )     ,     (       (     i   +       H                 x       2   depth_x         )     ,   j     )     ,     and                   (       (     i   +       H                 x       2   depth_x         )     ,     (     j   +       H                 y       2   depth_y         )       )                             
 
         [0069]    are added to the end of the LIP;  
         [0070]    Coordinates (i, j) are removed from the LIP;  
         [0071]    2.2. The following methods are performed for each pixel or entry (i, j) in the LIS.  
         [0072]    2.2.1. If the entry (i, j) is type A,  
         [0073]    Sn(D(i, j)) is output;  
         [0074]    If Sn(D(i, j))=1, Sx=1, and Sy=1,  
         [0075]    The following methods are performed for each of coordinates (k, 1)∈0(i, j).  
         [0076]    depth_x=log(n1/2)−level;  
         [0077]    depth_y=log(n2/2)−level;  
         [0078]    Sn(k, l) is output;  
         [0079]    If Sn(k, l)=1, coordinates (k, l) are added to the LSP and signs of C k,j  are output;  
         [0080]    If Sn(k, l)=0, coordinates (k, l) having depth_x and depth_y are added to the LIP;  
         [0081]    If L(i, j) is not empty, coordinates (i, j) move as an entry of type B to the end of the LIS, and go to 2.2.2;  
         [0082]    If not, the entry (i, j) is removed from the LIS.  
         [0083]    If Sn(D(i, j)=1, Sx=1, and Sy≠1,  
         [0084]    depth_y is increased by 1;  
         [0085]    coordinates (i, j) and  
       (     i   ,     (     j   +       H                 y       2   depth_y         )       )                         
 
         [0086]    are added as an entry of type A to the end of the LIS;  
         [0087]    Coordinates (i, j) are removed from the LIS;  
         [0088]    If Sn(D(i, j))=1, Sx≠1, and Sy=1,  
         [0089]    Depth_x is increased by 1;  
         [0090]    Coordinates (i, j) and  
       (     i   ,     (     j   +       H                 y       2   depth_y         )       )                         
 
         [0091]    are added as the entry of type A to the end of the LIS;  
         [0092]    Coordinates (i, j) are removed from the LIS;  
         [0093]    If Sn(D(i, j))=1, Sx≠1, and Sy≠1,  
         [0094]    depth_x and depth_y are each increased by 1;  
         [0095]    Coordinates (i, j) and  
         (     i   ,     (     j   +       H                 y       2   depth_y         )       )     ,     (       (     i   +       H                 x       2   depth_x         )     ,   j     )     ,     and                   (       (     i   +       H                 x       2   depth_x         )     ,     (     j   +       H                 y       2   depth_y         )       )                             
 
         [0096]    are added as the entry of type A to the end of the LIP;  
         [0097]    Coordinates (i, j) are removed from the LIS;  
         [0098]    2.2.2. If the entry is type B,  
         [0099]    Sn(L(i, j)) is output;  
         [0100]    If Sn(L,(i, j))=1,  
         [0101]    depth_x=log(n1/2)−level;  
         [0102]    depth_y=log(n2/2)−level;  
         [0103]    Each of coordinates {(k, 1) ∈0(i, j) is added as the entry depth_x and depth_y of type A to the end of the LIS;  
         [0104]    Coordinates (i, j) are removed from the LIS;  
         [0105]    3. Refinement Pass  
         [0106]    n th  bit of |C i,j | is output for each entry (i, j) added to the LSP before a current n.  
         [0107]    4. Quantization-step Update  
         [0108]    After n is reduced by 1, the sorting pass is performed.  
         [0109]    [0109]FIG. 3 is a block diagram of an encoder according to an embodiment of the present invention. Referring to FIG. 3, an encoder  40  includes a wavelet transform circuit  41 , an optimum zerotree generator  43 , a zerotree coder  45 , and an entropy coder  47 .  
         [0110]    The wavelet transform circuit  41  wavelet-transforms an input image to a wavelet domain having a plurality of wavelet coefficients or nodes. FIG. 2 shows a wavelet domain. In other words, the wavelet transform circuit  41  wavelet-transforms the input image to a predetermined level or scale.  
         [0111]    The optimum zerotree generator  43  generates a plurality of zerotrees corresponding to the same spatial locations and orientations of the plurality of wavelet coefficients in response to signals output from the zerotree coder  45  and the wavelet transform circuit  41 . In other words, the optimum zerotree generator  43  organizes an optimum zerotree using spatial correlations among the wavelet coefficients.  
         [0112]    The zerotree coder  45  merges a plurality of adjacent zero trees, and codes the merged zerotrees to one symbol, and outputs the symbol to the entropy coder  47  and the optimum zerotree generator  43 .  
         [0113]    If a wavelet tree corresponding to the same spatial locations and orientations of a plurality of wavelet coefficients output from the wavelet transform circuit  41  is a zerotree, the optimum zerotree generator  43  or the zerotree coder  45  may merge predetermined wavelet zerotrees adjacent to the zero tree, and code a plurality of merged wavelet zerotrees to one symbol, and output the symbol. Thus, the optimum zerotree generator  43  and the zerotree coder  45  may be constructed as a single circuit.  
         [0114]    Also, the optimum zerotree generator  43  or the zerotree coder  45  may separately code wavelet coefficients that do not constitute zerotrees. The entropy coder  47  receives a signal output from the zerotree coder  45  and creates a bitstream. Thus, the encoder according to an embodiment of the present invention codes an input image to a bitstream using a zerotree wavelet transform.  
         [0115]    [0115]FIG. 4 is a detailed block diagram of the optimum zerotree generator  43  shown in FIG. 3. FIGS. 5A through 5C show examples of a zerotree group generated by the optimum zerotree generator  43  shown in FIG. 3.  
         [0116]    Referring to FIGS. 4 and 5A through  5 C, the optimum zerotree generator  43  includes an initial spatial orientation tree generator  431 , a threshold generator  433 , and a zerotree splitter  435 .  
         [0117]    The initial spatial orientation tree generator  431  constitutes initial zerotree groups. In other words, initialized subbands constitute zerotrees. FIG. 5A, in the initial stage, three zerotree groups exist. Here, the same numbers denote zerotrees corresponding to the same spatial locations and orientations of wavelet coefficients.  
         [0118]    The threshold generator  433  is connected to the initial spatial orientation tree generator  431  and sets a threshold value for quantization. The threshold generator  433  initially outputs n represented by equation 3, reduces the n by 1 while executing a method according to an embodiment of the present invention, and outputs the reduced result value. When the threshold value is determined from the threshold generator  433 , zerotree groups, with respect to the determined threshold value, are split as shown in FIG. 5B.  
         [0119]    The zerotree splitter  435  receives a quantization threshold value output from the threshold generator  433 , compares wavelet coefficients with the quantization threshold value, and if there are wavelet coefficients larger than the quantization threshold value, split zerotree groups using the wavelet coefficients.  
         [0120]    Referring to FIG. 5C, the same numbers belong to the same zerotree groups. As n decreases, the zerotree splitter  435  splits the zerotree groups to increase depth_x and depth_y.  
         [0121]    [0121]FIG. 6 is a flowchart illustrating a method of coding an input image to a bitstream using a zerotree wavelet transform for generating a plurality of wavelet trees each having a plurality of wavelet coefficients.  
         [0122]    According to FIGS. 3 through 6, in block  71 , the optimum zerotree generator  43  determines whether current wavelet coefficients constitute at least one or more zerotrees. In other words, in block  71 , it is determined whether each wavelet tree is a zerotree.  
         [0123]    If the current wavelet coefficients do not constitute at least one or more zerotrees, in block  79 , the zerotree coder  45  separately codes the current wavelet coefficients. In other words, if each wavelet tree is not a zerotree, the zerotree coder  45  separately codes and outputs each wavelet coefficient belonging to each wavelet tree.  
         [0124]    If the current wavelet coefficients constitute at least one zerotree, in block  73 , the optimum zerotree generator  43  determines the number of zerotree roots. If there is one zerotree root, in block  78 , the zerotree coder  45  codes one zerotree root.  
         [0125]    However, if there are two or more zerotree roots, in block  75 , the optimum zerotree generator  43  searches the ranges of adjacent zerotree roots. The zerotree coder  45  merges a plurality of adjacent zerotrees, i.e., zerotree groups, codes the merged zerotrees to one symbol, and outputs the symbol to the entropy coder  47 .  
         [0126]    [0126]FIG. 7 shows bit per pixel (BPP) and peak signal to noise ratio (PSNR) according to the prior art SPIHT algorithm and a grouped set partitioning in hierarchical trees (GSPIHT) method according to an embodiment of the present invention when a lena image is transformed to three levels. FIG. 8 shows BPP and PSNR according to the prior art SPIHT algorithm and a GSPIHT method according to an embodiment of the present invention when a lena image is transformed to four levels.  
         [0127]    Equations 4 and 5 represent evaluation measures PSNR shown in FIGS. 7 through 10.  
             RMSE   =         1   NM            ∑     i   =   0       N   -   1                         ∑     j   =   0       M   -   1              [       Y        (     i   ,   j     )       -     X        (     i   -   j     )         ]     2                     (   4   )                               
 
         [0128]    wherein, X(i, j) and Y(i, j) represent an original image and a reconstructed image, respectively. Here, an objective efficiency evaluation measure is a root mean square error (RMSE).  
             PSNR   =     20                     log   10          (     255   RMSE     )                 (   5   )                               
 
         [0129]    Referring to FIGS. 7 and 8, an encoder implementing a method according to an embodiment of the present invention shows more efficient coding than an encoder using the prior art algorithm regardless of a wavelet transform level.  
         [0130]    [0130]FIG. 9 shows an efficiency of coding a barbara image using the prior art SPIHT algorithm. FIG. 10 shows an efficiency of coding a barbara image using a GSPIHT method according to an embodiment of the present invention . Referring to FIGS. 9 and 10, it can be seen that coding efficiency of an encoder using a GSPIHT method is more improved and stabilized than coding efficiency of an encoder using the prior art SPIHT algorithm.  
         [0131]    According to an embodiment of the present invention, an encoder using a zerotree wavelet image coding algorithm and the SPIHT algorithm merges a plurality of adjacent zerotrees, and codes the merged zerotrees to one symbol and outputs the symbol.  
         [0132]    As described above, in method of and an system for coding grouped zerotree wavelet image according to the present invention, coding efficiency can be improved.  
         [0133]    While this invention has been particularly shown and described with reference to preferred embodiments thereof, it will be understood by those skilled in the art that various changes in form and details may be made therein without departing from the spirit and scope of the invention as defined by the appended claims.