Abstract:
An N-level wavelet transform is executed on an image signal representing an image having a first dimension and a second dimension. First, an N-level one-dimensional wavelet transform is executed in the first dimension, thereby generating an intermediate signal which is temporarily stored in a memory device; then an N-level one-dimensional wavelet transform is executed on the intermediate signal in the second dimension. The image signal may be accompanied by shape information describing the shape of the image, in which case each N-level one-dimensional wavelet transform is executed by a series of N one-level wavelet transforms, with alteration of the shape information when each one-level wavelet transform is performed.

Description:
BACKGROUND OF THE INVENTION 
     The present invention relates to a method and apparatus for executing a wavelet transform on an image signal. 
     The wavelet transform is a mathematical tool for characterizing the local properties of a signal at a variety of resolutions. In recent years, this has been found to be an effective way to compress digitized image signals. 
     When the wavelet transform is applied to an image signal by the pyramid method of the prior art, which will be described in more detail later, the image signal passes in succession through a plurality of stages. In each stage, the signal is filtered horizontally and vertically, and the resolution of the signal is reduced by half in each dimension. 
     One problem with this method is the repeated need for temporary storage of the image signal. Signal storage is necessary between the horizontal filtering and vertical filtering operations in each stage of the transform, and is also necessary between the different stages. A filtering operation cannot begin until the signal has been stored, so besides consuming memory space, the repeated storage operations impair the speed of the transform. 
     Another problem is that in the final output signal of the transform, high and low spatial frequencies are mixed in a way that is not advantageous for compression. This problem will be described in more detail later. 
     A further problem is that the prior-art method works only with rectangular images. If an image is not rectangular, it must be embedded in a rectangle, and the non-image parts of the rectangle must be filled in with, for example, the average value of the image signal, or with signal values copied from the border of the image. Efficient compression of the resulting rectangular image tends to be impaired by high-frequency artifacts generated by the abrupt transitions between the image area and the filled-in area. 
     SUMMARY OF THE INVENTION 
     It is accordingly an object of the present invention to execute a wavelet transform on a two-dimensional image signal without requiring a repeated storing of the image signal. 
     Another object of the present invention is to produce a wavelet transform output signal that can be highly compressed by further encoding. 
     Yet another object is to execute a wavelet transform on a two-dimensional image signal representing an image with an arbitrary shape, without generating artifacts. 
     According to a first aspect of the invention, an N-level wavelet transform is executed on an image signal, where N is an integer greater than one. The image signal represents an image having a first dimension and a second dimension. First, an N-level one-dimensional wavelet transform is executed on the image signal in the first dimension, generating an intermediate signal which is temporarily stored in a memory device. Then an N-level one-dimensional thereby wavelet transform is executed on the intermediate signal in the second dimension. Each N-level one-dimensional wavelet transform is preferably executed by a single matrix operation. 
     According to a second aspect of the invention, an N-level wavelet transform is executed on an image signal, where N is an integer greater than zero. The image signal represents an image having a first dimension and a second dimension, and having an arbitrary shape. The image signal is accompanied by shape information describing the shape of the image. First, N single-level one-dimensional wavelet transforms are executed on the image signal in a cascaded series in the first dimension, thereby generating an intermediate signal which is temporarily stored in a memory device. When each single-level one-dimensional wavelet transform is executed, the shape information is altered to describe the shapes of the component signals resulting from the transform. Next, N single-level one-dimensional wavelet transforms are executed on the intermediate signal in a cascaded series in the second dimension, accompanied by further similar alterations of the shape information. 
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS 
     FIG. 1 is a block diagram illustrating a first embodiment of the invention; 
     FIG. 2 illustrates the decomposition of an image signal into high-frequency and low-frequency components by the first embodiment; 
     FIG. 3 mathematically illustrates the operation of the N-level vertical wavelet filter in the first embodiment; 
     FIG. 4 is a block diagram illustrating a second embodiment; 
     FIG. 5 mathematically illustrates the operation of the N-level vertical wavelet filter in the second embodiment; 
     FIG. 6 is a block diagram illustrating a third embodiment; 
     FIG. 7 is a block diagram illustrating a fourth embodiment; 
     FIG. 8 is a block diagram illustrating a single-level one-dimensional wavelet filter; 
     FIG. 9 is a block diagram illustrating the prior art; and 
     FIG. 10 illustrates the decomposition of an image signal into high-frequency and low-frequency components in the prior art. 
    
    
     DETAILED DESCRIPTION OF THE INVENTION 
     Embodiments of the invention will be described with reference to the attached drawings, but first, it will be useful to give some general information and describe the prior art in more detail. 
     Referring to FIG. 8, a single-level one-dimensional wavelet filter comprises a low-pass filter  2  and a high-pass filter  4 , both of which receive the same input signal S. If S L  is the output of the low-pass filter  2  and S H  is the output of the high-pass filter  4 , the operation of the wavelet filter can be described by the equations shown below, in which m is a positive integer, n is a non-negative integer, h(k) are the filter coefficients of the low-pass filter  2 , and g(k) are the filter coefficients of the high-pass filter  4  (k=−n, . . . , m).                  S   L          (   i   )       =       ∑     k   =     -   n         k   =   m                         S        (       2      i     +   k     )            h        (   k   )                           S   H          (   i   )       =       ∑     k   =     -   n         k   =   m                         S        (       2      i     +   k     )            g        (   k   )                                        
     The two output signals S L  and S H  each have half the resolution of the input signal S. Resolution can be expressed as the number of signal samples. For integers N greater than unity, an N-level one-dimensional wavelet transform is carried out by iterating this process on the low-frequency component S L . 
     When the input signal represents a two-dimensional image, wavelet filtering is performed separately in each dimension. FIG. 9 shows an apparatus for performing a three-level wavelet transform on a two-dimensional image signal by the pyramid method of the prior art. 
     In the first stage  6  of the apparatus, a horizontal wavelet filter  8  executes a single-level one-dimensional wavelet transform on each horizontal row of picture elements, thereby obtaining a low-frequency component signal S L3  which is temporarily stored in a memory device  10 , and a high-frequency component signal S H3  which is temporarily stored in a memory device  12 . Then a first vertical wavelet filter  14  performs a single-level one-dimensional wavelet transform on each vertical column of picture elements in S L3 , thereby obtaining a low-frequency component signal S LL3  and a high-frequency component signal S LH3 , and a second vertical wavelet filter  14  performs a single-level one-dimensional wavelet transform on each vertical column of picture elements in S H3 , thereby obtaining a low-frequency component signal S HL3  and a high-frequency component signal S HH3 . Of these four signals, the purely low-frequency component signal S LL3  is temporarily stored in a memory device  18 , while S LH3 , S HL3 , and S HH3 , which contain high-frequency components, are output without further processing. 
     The internal memory devices  10  and  12  are necessary because the horizontal wavelet filter  8  generates the picture elements of the S L3  and S H3  signals in one order, working horizontally one row at a time, but the vertical wavelet filters  14  and  16  process the same S L3  and S H3  signals in a different order, working vertically one column at a time. 
     The second stage  20  has the same internal configuration as the first stage  6 , and operates in similar fashion on the signal S LL3  stored in memory device  18  to obtain four more signals, denoted S LL2 , S LH2 , S HL2 , and S HH2 . Of these signals, S LL2  is stored in a memory device  22 , and S LH2 , S HL2 , and S HH2  are output without further processing. 
     The third stage  24  has the same internal configuration, and operates in a similar fashion on the signal S LL2  stored in memory device  22 , obtaining four more output signals S LL1 , S LH1 , S HL1 , and S HH1 . It can be seen that five temporary storage operations are needed to obtain each of these signals, including one storage operation in each of the three stages  6 ,  22 , and  24 , and two more storage operations between the stages, in memory devices  18  and  22 . 
     FIG. 10 locates the ten resulting output signals in the two-dimensional plane. The plane is iteratively decomposed by dividing lines, each separating a low spatial frequency component (above or to the left of the dividing line) from a high spatial frequency component (below or to the right of the dividing line). The signal S HL3 , for example, represents a high horizontal spatial frequency component and a low vertical spatial frequency component. 
     The presence of this low vertical spatial frequency component means that the S HL3  signal possesses a strong residual correlation in the vertical dimension, which limits the amount by which this signal can be compressed by further encoding. Compression of S LH3 , S HL2 , and S LH2  is similarly limited by residual correlation. 
     First Embodiment 
     Referring to FIG. 1, a first novel wavelet transform apparatus comprises an N-level horizontal wavelet filter  26 , a memory device  28 , and an N-level vertical wavelet filter  30 . In this embodiment N is equal to three. Filter  26  comprises three cascaded single-level horizontal wavelet filters  32 ,  34 , and  36 , while filter  30  comprises three cascaded single-level vertical wavelet filters  38 ,  40 , and  42 . The memory device  28  stores the output of the N-level horizontal wavelet filter  26  as an intermediate signal X, which is provided as input to the N-level vertical wavelet filter  30 . 
     The wavelet transform performed by the first embodiment will be referred to as a separable wavelet transform, because it can be separated into a horizontal one-dimensional wavelet transform followed by a vertical one-dimensional wavelet transform. 
     The individual wavelet filters  32 ,  24 ,  36 ,  38 ,  40 , and  42  comprise well-known electronic computing circuits, descriptions of which will be omitted to avoid obscuring the invention with unnecessary detail. 
     In the N-level horizontal wavelet filter  26 , horizontal wavelet filter  32  decomposes the input two-dimensional image signal S into a low-frequency component S L3  and a high-frequency component S H3  by applying the equations given above to each horizontal row of picture elements in S. In the same way, horizontal wavelet filter  34  decomposes S L3  into a low-frequency component S L2  and a high-frequency component S H2 , and horizontal wavelet filter  36  decomposes S L2  into a low-frequency component S L1  and a high-frequency component S H1 . 
     The three single-level horizontal wavelet filters  32 ,  34 , and  36  are thus cascaded by transmitting the low-frequency component from one filter to the next. In this process, it is not necessary to store the entire S L3  component signal between filters  32  and  34 , because filter  34  processes the S L3  signal values in the same order as the order of output from horizontal wavelet filter  32 , working horizontally one row at a time. Similarly, it is not necessary to store the entire S L2  signal between filters  34  and  36 . 
     The memory device  28  stores the four signals S L1 , S H1 , S H2 , and S H3 . Vertical wavelet filter  38  decomposes each of these four signals into a low-frequency component and a high-frequency component. Vertical wavelet filter  40  then decomposes each of the four low-frequency components output by vertical wavelet filter  38  into a further low-frequency component and a high-frequency component, and vertical wavelet filter  42  decomposes each of the four low-frequency components output by vertical wavelet filter  38  into a still further low-frequency component and a high-frequency component. The output Y of the first embodiment comprises the high-frequency components output by vertical wavelet filters  38 ,  40 , and  42 , and the low-frequency component output by vertical wavelet filter  42 . 
     FIG. 2 exhibits the output of the first embodiment in the two-dimensional plane, the dividing lines representing the separation of low-frequency from high-frequency components as in FIG.  10 . First the N-level horizontal wavelet filter  26  divides the plane into four areas delimited by vertical lines in FIG. 2, representing the four signals S L1 , S H1 , S H2 , and S H3 . Then the N-level vertical wavelet filter  30  divides each of these four areas into four sub-areas, representing sixteen separate component signals in all. 
     Of these sixteen signals, S LL1 , S LH1 , S HL1 , S HH1 , S HH2 , and S HH3  are identical to the corresponding signals in FIG.  10 . The area that produced one signal component S HL3  in FIG. 10, however, is divided into three components S HL30 , S HL31 , and S HL32  in FIG.  2 . When S HL32  is compressed by further encoding, a higher compression ratio can be achieved than the ratio achievable for S HL3  in FIG. 10, because the lowest vertical spatial frequencies are eliminated and the residual correlation is less. Similar gains in compression are obtained in S LH23  and in several other components in FIG. 2, so the overall compression ratio is significantly improved. 
     The operation of the N-level vertical wavelet filter  30  will next be described mathematically as a triple matrix operation, for the case of an image with a height of eight picture elements. The operation is partly shown in FIG.  3 . The column vector at the right represents one column in the image after filtering by the N-level horizontal wavelet filter  26 . In the notation given above, x 0  to x 7  are elements of one of the four signals S L1 , S H1 , S H2 , and S H3 . 
     In this case, the high-pass and low-pass filters in each single-level wavelet filter have only two non-zero coefficients each. The coefficients of the low-pass filter are h 1  and h 2 . The coefficients of the high-pass filter are g 1 , and g 2 . The vertical wavelet filter  38  is mathematically represented by the matrix M 38 . The vertical wavelet filters  40  and  42  are similarly represented by matrices M 40  and M 42 . 
     The column vector at the right is multiplied in turn by matrices M 38 , M 40 , and M 42 , producing the output column vector at the left. In the notation of FIG. 2, if x 0  to x 7  are elements of S L1 , for example, then y 0  is an element of S LL1 , y 1  is an element of S LH1 , y 2  and y 3  are elements of S LH02 , and y 4 , y 5 , Y 6 , and Y 7  are elements of S LH03 . 
     The operation of the N-level horizontal wavelet filter  26  can be similarly described as a triple matrix operation in which a row vector is successively multiplied by three matrices M 32 , M 34 , and M 36 . If the input signal S is represented as a rectangular row-column matrix of picture elements, the entire operation of the first embodiment can be described in matrix form as follows: 
     
       
         
           X=SM 
           32 
           M 
           34 
           M 
           36 
         
       
     
     
       
         
           Y=M 
           42 
           M 
           40 
           M 
           38 
           X 
         
       
     
     As noted above, the output signal Y is more compressible, by well-known techniques such as quantization, run-length encoding, and entropy encoding, than the output obtained in the prior art. In addition, during the transform process, the image signal has to be temporarily stored only once, instead of five times as in the prior art, so less memory space is required, and less time is taken up by memory access operations. 
     Second Embodiment 
     The second embodiment performs a separable wavelet transform by replacing the triple matrix operations described above with single matrix operations. 
     Referring to FIG. 4, the second embodiment comprises a matrix-type horizontal wavelet filter  44  that performs a single matrix operation on the input signal S, producing the intermediate signal X that is stored in the memory device  28 . A matrix-type vertical wavelet filter  46  then completes the wavelet transform by performing a single matrix operation on the intermediate signal X. 
     The filters  44  and  46  are matrix processors. If the single matrix operation performed by the horizontal wavelet filter  44  is represented by a matrix M 44 , and the single matrix performed by the vertical wavelet filter  46  by a single matrix M 46 , then the operation of the second embodiment can be described mathematically as follows: 
     
       
         
           X=SM 
           44 
         
       
     
     
       
         
           Y=M 
           46 
           X 
         
       
     
     The matrices M 44  and M 46  are the products of the corresponding matrices in the first embodiment: 
     
       
         
           M 
           44 
           =M 
           32 
           M 
           34 
           M 
           36 
         
       
     
     
       
         
           M 
           46 
           =M 
           42 
           M 
           40 
           M 
           38 
         
       
     
     FIG. 5 partially depicts the operation of the vertical wavelet filter  46 , showing a column vector being multiplied by matrix M 46 . In effect, the second embodiment performs the matrix multiplication operation M 42 M 40 M 38  ahead of time, instead of performing this operation each time the wavelet transform is carried out. The second embodiment therefore operates faster than the first embodiment. 
     Third Embodiment 
     The third embodiment carries out a separable wavelet transform on images with arbitrary shapes. 
     Referring to FIG. 6, the third embodiment comprises an N-level horizontal wavelet filter  48 , a pair of memory devices  50  and  52 , and an N-level vertical wavelet filter  54 . N is again equal to three. 
     The input to the third embodiment comprises two signals: an image signal S giving the values of picture elements in the image, and shape information R describing the shape of the image. The image is treated as being embedded in a rectangular area. The shape information R indicates which parts of the rectangular area belong to the image. The shape information R comprises, for example, a rectangular bit mask, or a run-length encoding of such a bit mask. 
     In the N-level horizontal wavelet filter  48 , a first single-level horizontal wavelet filter  56  performs a wavelet filtering operation on the input signal S according to the shape information R. If, for example, the rectangular area has a width of m picture elements, but only the first n picture elements in a certain horizontal row belong to the image (where m and n are positive integers and m is greater than n), then if n is an even number, horizontal wavelet filter  56  operates on all of these n picture elements, producing component signals S L3  and S H3  with n/2 elements each. if n is an odd number, horizontal wavelet filter  56  operates on the first n−1 picture elements, and appends the n−th picture element to the resulting low-frequency component signal S L3 , so that S L3  has (n−1)/2+1 elements, and component signal S H3  has (n−1)/2 elements. 
     A first reshaper  58  then alters the shape information R to describe the shape of the component signals S L3  and S H3 . These component signals can be treated as being embedded in the left and right halves of a rectangular area with the same width m. 
     The altered shape information R 3  is supplied to a second single-level horizontal wavelet filter  60 , which filters S L3  according to R 3 , and to a second horizontal reshaper  62 . Reshaper  62  further alters R 3  to obtain shape information R 2  describing the shape of the low-frequency and high-frequency component signals S L2  and S H2  output by filter  60 . Shape signal R 2  also retains information describing the shape of the high-frequency component signal S H3  output by the first single-level horizontal wavelet filter  56 . 
     Continuing in the same way, a third single-level horizontal wavelet filter  64  filters S L2  according to R 2 , and a third horizontal reshaper  66  alters R 2  to obtain shape information R 1  describing the shapes of the component signals S L1  and S H1  output by filter  64 , as well as the shapes of S H2  and S H3 . Component signals S L1 , S H1 , S H2 , and S H3  are stored in memory device  50  as the intermediate signal X, while shape information R 1  is stored in memory device  52 . 
     The N-level vertical wavelet filter  64  comprises a first single-level vertical wavelet filter  68  and vertical reshaper  70 , a second single-level vertical wavelet filter  72  and vertical reshaper  74 , and a third single-level vertical wavelet filter  76  and vertical reshaper  78 , which operate on the intermediate signal X and shape information R 1  in the same way that the N-level horizontal wavelet filter  48  operated on S and R, although in the vertical dimension. Shape signal R 1  is successively altered by reshapers  70 ,  74 , and  78  to obtain shape informations R 13 , R 12 , and R 11 . The final outputs of the third embodiment are a wavelet transform signal Y and shape information R 11  describing the shapes of the various components of Y. 
     By altering the shape information as described above, the third embodiment is able to confine operations to the image area at every stage and level of the wavelet transform. No artifacts are introduced by transitions between image and non-image areas, and the output signal Y is free of spurious high-frequency components that would impede compression of the transformed image signal. 
     A further advantage of the third embodiment is that there is no need to generate dummy signal values to fill in non-image parts of the rectangular area. 
     Fourth Embodiment 
     The fourth embodiment applies the reshaping technique or the third embodiment to the pyramid method of the prior art. 
     FIG. 7 illustrates the fourth embodiment for a three-level wavelet transform. In the first stage  80 , a single-level horizontal wavelet filter  82  filters the image signal S according to the shape information R, and a horizontal reshaper  84  alters R to obtain shape information R 3 . The low-frequency and high-frequency components S L3  and S H3  generated by a filter  82  are stored in memory devices  86  and  88 , and the altered shape information R 3  is stored in a memory device  90 . The two single-level vertical wavelet filters  92  and  94  then filter S L3  and S H3  according to shape information R 3 , obtaining component signals S LL3 , S LH3 , S HL3 , and S HH3 , and a vertical reshaper  96  alters R 3  to obtain shape information R 33  describing the shapes of these component signals. 
     Of the first-stage output signals, the low-frequency component signal S LL3  and shape information R 33  are stored in a pair of memory devices  98  and are  100  and furnished to a second stage  102 , which operates in the same manner as the first stage. The low-frequency component S LL2  and shape information R 22  output from the second stage are stored in a pair of memory devices  104  and  106  and are furnished to a third stage  108 , which also operates in the same manner. The final output of the wavelet transform comprises ten component signals S LL1 , S LH1 , S HL1 , S HH1 , S LH2 , S HL2 , S HH2 , S LH3 , S HL3 , and S HH3 , and shape information R 11  describing the shapes of these components. 
     The third and fourth embodiments both enable a wavelet transform of any number of levels to be performed on an image with an arbitrary shape, without generating high-frequency artifacts. The third embodiment is preferable to the fourth embodiment for the same reasons that the first embodiment is preferable to the prior art: less memory is required, operation is faster, and the output signal is more compressible because of being more finely divided in the two-dimensional plane. 
     Although horizontal filtering was performed before vertical filtering in the preceding embodiments, the order could be switched around. The second embodiment, for example, could be performed according to the following equations, without changing the final result Y. 
     
       
         
           X=M 
           46 
           S 
         
       
     
     
       
         
           Y=XM 
           44 
         
       
     
     The individual single-level wavelet filters in the invention need not be separate electronic computing circuits. The invention can also be practiced by means of a suitably programmed general-purpose computing device such as a digital signal processor. 
     Those skilled in the art will recognize that other variations are possible within the scope claimed below.