Abstract:
An encoder ( 1600 ) and decoder ( 1700 ) for improving bit rate efficiency in a wavelet based codec includes an analysis filter bank ( 1601 ) for decorrelating the input data signal. A set of decimators ( 1701 ) are used to down sample the filtered input data signal and a predictor ( 1705 ) is used to extract cross subband dependence. The predictors ( 804, 904, 1104, 1204, 1304 ) are used in order to reduce the number of bytes of an encoded input data signal X(Z). The predictors exploit existing correlation amongst the subbands resulting from a multi-level analysis wavelet transformation or filter bank processing. Decimation required by the analysis filter bank is placed around the predictor on the basis of spatial location variance minimization to further facilitate subband prediction, and on computational complexity of the overall system.

Description:
CROSS REFERENCE TO RELATED APPLICATIONS  
       [0001]     This application is related to U.S. Pat. No. 6,278,753 by Jose Suarez et al., entitled “Method and Apparatus for Creating and Implementing Wavelet Filters in a Digital System,” U.S. Pat. No. 6,128,346 by Suarez et al., entitled “Method and Apparatus for Quantizing a Signal in a Digital System”, and U.S. Pat. No. 6,661,927 by Suarez et al., entitled “System and Method for Efficiently Encoding an Image by Prioritizing Groups of Spatially Correlated Coefficients Based on an Activity Measure” previously filed and all assigned to Motorola, Inc. 
     
    
     TECHNICAL FIELD  
       [0002]     This invention pertains in general to encoding data to reduce its required byte count by reducing the amount of bits required per pixel and more particularly to a bandwidth limited system for improved bit rate efficiency that utilizes spatially correlated subbands in a subband coding system.  
       BACKGROUND  
       [0003]     With the advent of technologies and services related to teleconferencing and digital image storage, considerable progress has been made in the field of digital signal processing. As will be appreciated by those skilled in the art, one example of digital signal processing relates to systems, devices, and methodologies for generating a sampled data signal, compressing the signal for storage and/or transmission, and thereafter reconstructing the original data from the compressed signal. Critical to any highly efficient, cost effective, and bandwidth limited digital signal processing system is the methodology used for achieving compression and bit rate efficiency.  
         [0004]     As is known in the art, data compression refers to the steps performed to map an original data signal into a bit stream suitable for communication over a channel or storage in a suitable medium. Methodologies capable of minimizing the amount of information necessary to represent and recover an original data are desirable in order to lower computational complexity, system bandwidth, and cost. In addition to these factors, simplicity of hardware and software implementations capable of providing high quality data reproduction with minimal bits per pixel (bpp) is likewise desirable.  
         [0005]     Various prior art schemes exist for encoding data. A key objective of encoding data is to ‘compress’ the data, i.e., to reduce the byte size of the data. This is desirable in order to reduce memory space required to store the data, and reduce the time required to transmit data through a communication channel having a certain finite bandwidth. The byte size is typically expressed as bits per sample, or as is conventional in the case of image data, as bits per pixel (bpp). The two classes of encoding methods typically include both lossless encoding and lossy encoding. The former, more conservative approach endeavors to preserve every detail of the input data in the encoded form. Ideally, the decoded version would be an indistinguishable replica of the input data. In the case of lossy data encoding, the level to which the detail of the image is preserved can be selected where there is a tradeoff between the level of detail preserved and the byte size of the resulting encoded data.  
         [0006]     Often when using lossy data encoding, the goal is to obtain a level of detail preservation such that the differences between a decoded version and the original image are imperceptible. Judgments about the design and configuration of the lossy encoder to achieve imperceptible differences will be made in consideration of human perception models (e.g., hearing, or visual). A good lossy encoder and corresponding decoder will yield a decoded data set which may be distinguished from the original data set by rigorous scientific analysis but is indistinguishable to a human observer when presented in an intended format.  
         [0007]     One step in the process of data encoding methods applicable to image data is referred to as transform coding. Generally, transform coding utilizes an ordered data set that is projected onto an orthogonal set of basis functions to obtain a set of transformed data coefficients inner products. The traditional type of transform coding derives from Fourier analysis. In Fourier based techniques, a data set is projected onto a function set derived from sinusoidal functions. The outdated JPEG standard (ISO/IEC 10928-1) is an example of a transform encoding method based on Fourier analysis. This older JPEG standard specifies a set of transform matrices which are discrete representations of products of a cosine function with a horizontal coordinate dependent argument and a cosine function with a vertical coordinate dependent argument. These basis functions are applied to analyze 8 by 8 pixel blocks of an input image.  
         [0008]     A shortcoming of these Fourier based techniques, which prompted the industry to take up other methods, is the fact that the sinusoidal function repeat indefinitely out to plus and minus infinity, whereas data sets which are encoded are localized in the time (or spatial) domain and have features which are further localized within the data set. Given the unbounded domain of Fourier bases functions and the periodic nature of data sets to be encoded over long intervals or spans one is led to segment the signal (e.g., into the aforementioned 8 by 8 blocks) in order to obtain a more efficient encoding.  
         [0009]     Unfortunately, this leads to abrupt jumps in the decoded version of the signal at edges between the segments. Those skilled in the image processing art will recognize this as a “blocking effect.” With regard to lossy encoding, whether it be Fourier, wavelet or otherwise based, the manner in which the reduction in the byte size with the associated loss of detail is achieved, according to the common prior art approach, is by quantizing and or coding the transformed data coefficients. Quantizing and or coding involve adjusting downward the resolution with which the value of the transformed data coefficients are recorded, so that they can be recorded using fewer bits.  
         [0010]     In the case of image data, transformed data coefficients associated with basis function that depend on finer details, i.e., higher frequency subbands, in the data may be quantized or coded with less resolution or fewer bits. Alternatively, these higher frequency subbands will be predicted from their spatially correlated lower frequency subbands. In narrow band systems and others in which there is a need in reducing the amount of information to be transmitted, it becomes important to reduce the number of data bits to be coded even prior to the quantization step. Because systems that implement discrete wavelet transforms involve decimation of the samples, spatial location variance is introduced.  
         [0011]     Newer classes of transform methods employ basis functions which are inherently localized in the spatial domain. Mathematically these are compactly supported. One example of the newer type of transform method is the wavelet based technique. Wavelet based techniques employ a set of basis functions comprising a mother wavelet and a set of child wavelets derived from the mother wavelet by applying different time or spatial domain shifts and dilations to the mother wavelet. A wavelet basis set comprising a set of functions with localized features at different characteristic scales, is better suited to encode data sets such as image or audio data sets which have fine, coarse and intermediate features at different locations (times). At present, there are various systems employing wavelets as means of decomposing the signal with the purpose of decorrelating the input image data. One such example is the Joint Photographic Experts Group system (JPEG 2000 standard) for still images proposes algorithms which use multilevel wavelets to achieve decomposition of an input signal. As will be recognized by those skilled in the art, multilevel wavelet decomposition is an iterative process, namely multi-resolutional decomposition. At each iteration a lower frequency set of transformed data coefficients generated by a prior iteration is again refined to produce a substitute set of transformed data coefficients including a lower spatial frequency group and a higher spatial frequency group, called subbands.  
         [0012]     In other signal processing literature, several authors have also explored the relationship between wavelets and multirate filter banks. For example in tutorials by Rioul and Vetterli [1991], Vetterli and Herley [1992], Akansu and Liu [1991], in the books  Multiresolutional Signal Decomposition, Transforms, Subbands, and Wavelets  by Ali N. Akansu and Richard A. Haddad, Academic Press, [1992],  Wavelets and Filter Banks  authored by Gilbert Strang and Truong Nguyen, Wellesley-Cambridge Press, [1996]. Tree structured filter banks are used in various applications, both in one-dimensional and two-dimensional processing.  
         [0013]     Prior art  FIG. 1  illustrates a four-channel, three level system with equal decimation ratios, where H 0 (z) and H 1 (z) in the analysis bank represent a high-pass pair, respectively. One attractive property of wavelets is their ability to adjust the lengths of basis functions. The three level wavelet decomposition shown in  FIG. 1  contains a lowest frequency basis function, denoted by a resulting filter H 4 (z) in Equation 1, which is a cascade of interpolated versions of the filter H 0 (z). Its effective length is large. 
 
 H   4 ( z )= H   0 ( z ) H   0 ( z   2 ) H   0 ( z   4 )  eq. (1) 
 
         [0014]      FIG. 2  shows the equivalent four-channel system of  FIG. 1 , where H 4 (z) is given by equation (1). Similarly  
                   H   3     ⁡     (   z   )       =         H   0     ⁡     (   z   )       ⁢       H   0     ⁡     (     z   2     )       ⁢       H   1     ⁡     (     z   4     )       ⁢           ⁢   and       ⁢                   eq   .           ⁢     (   2   )                     H   2     ⁡     (   z   )       =         H   0     ⁡     (   z   )       ⁢       H   1     ⁡     (     z   2     )       ⁢           ⁢   and             eq   .           ⁢     (   3   )                       H   1     ⁡     (   z   )         (     FIG   .           ⁢   2     )       =         H   1     ⁡     (   z   )         (     FIG   .           ⁢   1     )               eq   .           ⁢     (   4   )               
 
         [0015]     The corresponding synthesis filter bank is shown in  FIG. 3 , where G 0 (z) and G 1 (z) represent the low-pass and high-pass synthesis filters, respectively. The design of the analysis and synthesis filters depends on the application. Of special interest are systems requiring perfect reconstruction (PR) of the input signal; that is, systems where the output signal, {tilde over (X)}(z) and input signal X(z) may only differ by a delay. The relationship between the analysis low-pass and high-pass filters and the synthesis filters (low-pass and high-pass) in PR systems can be found in the book  Multirate Systems and Filter Banks  by P. P. Vaidyanathan, Prentice Hall Signal Processing Series.  
         [0016]      FIG. 4  shows the equivalent system to the four-channel synthesis filter bank of  FIG. 3 . Subbands Y 0 (z), Y 1 (z), Y 2 (z), and Y 3 (z) in both  FIGS. 3 and 4  are the inputs to the synthesis filter bank which correspond accordingly to the outputs of the analysis filter bank shown in  FIGS. 1 and 2 . This feed-through type of connection assumes a system where only wavelet filter bank processing takes place; such a system assumes no quantization and no coding. However, the invention here detailed is not limited to systems where only wavelet filter processing is performed, rather it also applies to lossy systems where quantization and coding take place between the analysis and synthesis filter banks.  
         [0017]     Subband coding using wavelets, i.e. tree structured filter banks have basis functions of variable lengths. Long basis functions represent the low frequency such as the flat background in images, whereas short basis functions represent higher frequencies such as the regions with texture. In the case of one-dimensional processing, referring to  FIGS. 1-4 , subband Y 0 (z) represents the higher frequency subband, while Y 3 (z) represents the lowest frequency subband resulting from the 3 rd  level processing. Similarly in the case of processing a two-dimensional input signal such as an image, Y 0 (z) would represent the three high frequency subbands obtained after processing the wavelet filter bank in two dimensions.  
         [0018]      FIG. 5  illustrates tree structured filter banks of the prior art that give rise to non-uniform filter bandwidths and shows typical and ideal magnitude responses of the filters in the analysis and synthesis filter banks shown in previous figures. Higher frequencies are iterated less, thus the basis functions become shorter. After three or more levels, most of the signal energy is in the lowest pass subband that is the LLLLLL subband for a three level wavelet decomposition as best seen in  FIG. 7 . It is well known in the art that there is a relationship between the wavelet transform and multirate filter banks. P. P. Vaidyanathan in Chapter 11 of  Multirate Systems and Filter Banks , Prentice Hall, presents this theoretical analysis. Here, Vaidyanathan also mentions that Daubechies developed a systematic technique for generating finite-duration orthonormal wavelets establishing the connection between continuous time orthonormal wavelets and the digital filter bank. Moreover, this publication further illustrates that wavelet transforms are closely related to the structured digital filter bank, and hence to the multi-resolutional analysis.  
         [0019]     In  FIG. 6 , the subbands in a one-level, two-channel discrete wavelet decomposition are shown after the analysis bank is processed two-dimensionally. The upper left sub-image is obtained by low-pass filtering in both the horizontal and vertical directions (2-dimensional), indicated by the LL subband. The other three images, HH, HL, and LH subbands have details involving higher frequencies.  
         [0020]     Finally  FIG. 7  shows a three-level discrete wavelet decomposition after applying the analysis filter bank of  FIG. 1  as a separable transform in both the horizontal and vertical directions. In the book  Wavelets and Filter Banks , Strang and Nguyen show that subbands  2 ,  5 , and  8  are highly correlated since  2  is the coarse approximation of  5 , and  5  is the coarse approximation of 8. For example, if the input image were applied to the three-level analysis filter bank of  FIG. 1 , the transformed pixel value that is spatially located in the upper left corner of subband  2  is zero, then it is very likely that the spatially correlated pixels corresponding in the 2×2 area of the upper left corner of subband  5  are also zero. Similarly, the pixels in the 4×4 area of subband  8 , which are spatially correlated to those in subbands  2 , and  5  are most likely zero.  
         [0021]     Thus, the need exists to provide a method to exploit cross-band correlation in wavelet based codecs even in the presence of a spatial variance introduced by the decimator in order to improve bit rate efficiency.  
       SUMMARY OF THE INVENTION  
       [0022]     This invention proposes various solutions to improve bit rate efficiency of signals in encoding and decoding systems involving subband coding. The process of applying a wavelet transform signal decomposition typically involves the steps of filtering and decimation to yield subbands that have spatial correlation amongst them. However, due to the spatial location variance introduced by decimation, the spatial correlation amongst the subbands becomes less obvious and more difficult to exploit. The present invention uses various systems to overcome this difficulty while using subband correlation to minimize the amount of data that needs to be transmitted. Predictors are used to extract cross-subband dependence allowing the large amount of data in the higher frequency subbands to be derived from corresponding lower resolutional bandwidth subbands, thus reducing the amount of processing and coding. 
     
    
     BRIEF DESCRIPTION OF THE FIGURES  
       [0023]      FIG. 1  illustrates a prior art four-channel, three-level analysis filter bank, where H 0 (z) and H 1 (z) are low-pass and high-pass filters, respectively.  
         [0024]      FIG. 2  depicts a prior art four-channel system equivalent to three-level analysis filter bank shown in  FIG. 1 .  
         [0025]      FIG. 3  illustrates a prior art four-channel, three-level synthesis filter bank corresponding to the analysis filter bank shown in  FIG. 1 .  
         [0026]      FIG. 4  illustrates a prior art four-channel system equivalent to the three-level synthesis filter bank shown in  FIG. 3 .  
         [0027]      FIG. 5  depicts a prior art typical and ideal magnitude response of the filters shown in  FIGS. 2 and 4 .  
         [0028]      FIG. 6  illustrates a prior art one-level discrete wavelet transform applied in the horizontal and vertical directions.  
         [0029]      FIG. 7  illustrates a prior art three-level discrete wavelet transform applied in the horizontal and vertical directions where arrows indicate subband correlation, shaded area in subbands show effect of decimation in the three levels of decomposition.  
         [0030]      FIG. 8  illustrates an encoding system consisting of an analysis filter bank and a compressor which comprises a quantizer and coder to provide a compressed output.  
         [0031]      FIG. 9  illustrates a decoding system consisting of a decompressor which comprises an inverse coder and inverse quantizer, a synthesis filter bank, a subband predictor, and signal formatter to provide a recovered signal.  
         [0032]      FIG. 10  illustrates a wired or wireless system consisting of an encoder, a means for transmitting the encoded or compressed data, a decoder to decompress the received signal from the encoder, and a conveyor as means to convey the recovered output signal.  
         [0033]      FIG. 11  illustrates a three-channel, two-level analysis filter bank with prediction block at output of the higher frequency subbands where all decimation occurs prior to the prediction block.  
         [0034]      FIG. 12  depicts the equivalent representation of filter bank in  FIG. 11  where decimation occurs at output of prediction block.  
         [0035]      FIG. 13  illustrates the well-known noble identities for multi-rate systems (from P. P. Vaidyanathan,  Multirate Systems and Filter Banks , Prentice-Hall, 1993).  
         [0036]      FIG. 14  illustrates a three-channel, two-level analysis filter bank, with distributed decimation around prediction block.  
         [0037]      FIG. 15  illustrates a three-channel, two-level analysis filter bank predicting the higher frequency subbands where the second level and high-pass filters, H′ 0 (z) and H′ 1 (z), respectively, are different having a lesser number of taps than those used in the first level.  
         [0038]      FIG. 16  illustrates the two-level analysis filter bank shown in  FIG. 15  with distributed decimation around prediction block.  
         [0039]      FIG. 17  illustrates analysis-by-synthesis predictions of the first level high-pass subband, Y 0 (z) to obtain the predicted subband (Ŷ 0 (z)) where H 0 (z) and H 1 (z) are part of the analysis filter bank and G 0 (z) and G 1 (z) correspond to the synthesis inverse discrete wavelet transform, IDWT.  
         [0040]      FIG. 18  illustrates analysis-by-synthesis prediction of the first-level, high-pass subband, Y 0 (z) to obtain the predicted subband Ŷ 0 (z) which is the system in  FIG. 17  using only partial interpolation. 
     
    
     DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENT  
       [0041]     The features of the present invention, which are believed to be novel, are set forth with particularly in the appended claims. The invention, together with further objects and advantages thereof, may best be understood with reference to the following description, taken in conjunction with the accompanying drawings, in the several figures of which like reference numerals identify like elements, and in which:  
         [0042]      FIG. 8  illustrates an encoding system  800  consisting of input signal X(z) to an analysis filter bank  801  which can either take a form of any as that shown in  FIGS. 11, 12 ,  14 ,  15 ,  16 ,  17 ,  18 , and a compressor  802 . The compressor  802  comprises a quantizer  803  to compress or quantize the subbands generated by the analysis filter bank, and coder  804  to further compress and format the data appropriately to provide a bit rate efficient compressed data output C(z).  
         [0043]      FIG. 9  illustrates a decoding system  900  consisting of an input compressed data signal C(z) to a decompressor  901 . The decompressor  901  comprises an inverse coder  902  to decompress and un-format the data with the purpose of packing the data bytes in a form that facilitates subband correlation extraction during synthesis (inverse wavelet transformation, IDWT). An inverse quantizer  903  is used to further decompress the data. A synthesis filter bank  904  may take the form as that shown in  FIGS. 17, 18 , while a subband predictor  905  is used to extract those subbands that were not encoded or transmitted and which at the decoder are predicted from other spatially correlated subbands. The subband predictor  905  is used to improve the signal quality of the recovered signal. A signal formatter  906  is further used to arrange the data bytes of the recovered signal {tilde over (X)}(z). In the case where the arranged data is 2-dimensional, it may be ready to be displayed. It is highly desirable that the design of the encoding and decoding systems shown in  FIGS. 8 and 9 , respectively be such that the recovered signal {tilde over (X)}(z) shown at the output of  FIG. 9  be as similar in quality as signal X(z) shown as input to  FIG. 8 .  
         [0044]      FIG. 10  illustrates a wired or wireless system consisting of a transmitter  1000  comprising an encoder  1001  optionally having the form of the encoder shown in  FIG. 8 . The transmitter  1000  wirelessly transmits the signal from encoder  1001  in compressed output. A receiver  1002  comprising a decoder  1003  has a form as shown in  FIG. 9  to decompress the received signal from the encoder. A converter  1004  such as a display is then used to allow viewing of the recovered and uncompressed signal.  
         [0045]     It has been observed that the image subbands obtained from discrete wavelet transformation (DWT) processing of a two-dimension signal, such as an image, exhibit large magnitudes in contour lines which follow similar paths on the spatially correlated subbands. These contours contain the image edges, object outlines. The system proposed by this invention exploits the correlation that exists between certain subbands to reduce the number of bits necessary to code the discrete wavelet transformed image. The process of applying a wavelet transform signal decomposition stage in a subband coding system, such as the three-level analysis filter bank shown in  FIG. 1 , involves decimation of the samples (represented herein as “↓”) at the low-pass and high-pass filter outputs. Decimation introduces spatial location variance, which causes the spatial subband correlation among the subbands to be less obvious. This means decimation makes it more difficult to exploit the subband correlation. This invention proposes various systems to overcome the difficulty imposed by the decimation steps.  
         [0046]      FIG. 11  shows decimation at the output of each filter  1100  as it is customarily seen in filter banks. Prediction block  1104  uses signal Y 1 (z) to predict the higher frequency subbands  8 ,  9  and  10  corresponding to the subbands generated by a first-level discrete 2-D wavelet transformation (DWT). This predicted signal is denoted by Ŷ 0 (z). As well known in the art, decimation reduces the amount of data. Therefore, decimation by 2, denoted by ↓2, causes the number of samples at the output of each filter (H 0 (z) and H 1 (z)) for the first level to be reduced by two. Therefore, for the case where X(z) is a 2-D input signal, the number of samples output of the first level DWT after horizontal and vertical processing is reduced by two along each dimension. In most analysis bank applications, the decimator is preceded by the filter to ensure that the signal being decimated is band-limited. The process of decimation, which is a linear but time-varying system, introduces spatial location variance, making cross-subband correlation much more difficult to exploit. A solution that lowers the number of computations from one level of the discrete-wavelet transformation (DWT) to the next DWT level is sought while minimizing the spatial location variance introduced by the decimation process.  
         [0047]     As seen in  FIG. 11 , a one-dimensional or a two-dimensional signal processed separately is inputted to a two-level analysis filter bank  1100 ,  1101  in a subband coding system. All signals and filters are to be in the z-domain, the networks being considered in this embodiment are two level. However, it should be evident to those skilled in the art that such networks in the analysis of synthesis filter banks can easily be expanded to higher level systems. Signal X(n) is inputted to a quadrature mirror filter bank consisting of filter H 0 (z)  1100  and high-pass filter H 1 (z)  1101 . The design of these FIR filters as well as the low-pass and high-pass synthesis filters H 0 (z) and H 1 (z), respectively, may be such as to guarantee perfect reconstruction of the entire encoding (analysis bank) and decoding (synthesis bank) system. Their number of terms and coefficient values are determined in the design process, whose procedure and imposed design criteria and requirements fall outside the scope of this invention.  
         [0048]     It should also be noted that at the output of each filter, the signal is decimated by a factor of 2. Prediction block  1104  is added at the output of the higher frequency subbands after applying the first level wavelet filter bank  1101  and the bandpass subbands outputted by the second level wavelet filter bank  1100 ,  1101 . All unpredicted subbands pass through unpredicted subband filter  1105 . The low frequency subbands from this first level decomposition are again passed through the low-pass and high-pass analysis filters  1102 ,  1103  to obtain the output band-pass subbands Y 1 (z) and the lowest frequency subband Y 2 (z). Thus, the two-level analysis bank is applied as a separable transform to an input image signal X(z) yields a signal Y 1 (z) which corresponds to band-pass subbands  5 ,  6 , and  7  as shown in  FIG. 7 . Similarly, signal Y 0 (z) corresponds to subbands  8 ,  9  and  10  also as shown in  FIG. 7 . Subbands  1 ,  2 ,  3 , and  4 , represented by Y 2 (z) at the output of filter ( 1102 ) in  FIG. 11 , correspond spatially to the low-frequency subband region obtained after applying the two-level analysis bank of  FIG. 11  horizontally and vertically as a separable transform to input signal X(z). Prediction block  1104  is used to predict subbands Y 0 (z) from subbands Y 1 (z) to yield Y 0 (z). X(z) is a two-dimensional (2-D) input signal.  
         [0049]      FIG. 12  shows an equivalent representation of the two-level analysis filter bank presented in  FIG. 11 , where the filters yielding the lowest frequency and bandpass subbands, Y 2 (z) and Y 1 (z), respectively, are expressed using the noble identities (from P. P. Vaidyanathan,  Multirate Systems and Filter Banks , Prentice-Hall, 1993) illustrated in  FIG. 13 . If the functions representing filters H 0 (z) and H 1 (z) are rational, that is, polynominals in Z or Z −1 , then by using these noble-identities, one can easily arrive at the representation shown in  FIG. 12 . Prediction block  1204  is immediately placed after the filters H 1 (z) ( 1202 ) and H 0 (z)H 1 (z 2 ) 1201 and prior decimation with the purpose to eliminate any spatial location variance and allow optimal subband prediction. Unpredicted subbands are filtered using unpredicted subband filter  1203 . However, the improved extraction of cross-band dependence is achieved at the expense of increased computational cost due to filtering. The lowest frequency subband from the two-level wavelet decomposition in  FIG. 12  is Y 2 (z) in the output path of filter  1200 .  
         [0050]      FIG. 14  illustrates a three-channel, two-level analysis filter bank, with distributed decimation around prediction block. This implementation differs from  FIG. 12  in that a reduction in data size and computations can be achieved by performing partial decimation prior to the prediction block  1401 . This scheme yields more computational cost at the predictor but less at the filtering step. This system provides a compromise between computational intensity and subband prediction effectiveness.  
         [0051]      FIG. 15  illustrates a method to further reduce the amount of computations at the filtering step. The method illustrates a three-channel, two-level analysis filter bank with prediction of the higher frequency subbands Y 0 (z) from the band-pass subbands Y 1 (z) outputted after applying the second level wavelet transformation. Second level, and high-pass filters, H′ 0 (z)  1502  and H′ 1 (z)  1503 , respectively, are different from those used in the first level wavelet transformation. These analysis filters have less number of taps than those used in the first level  1500  and  1501 . This solution optimizes subband prediction while lowering the number of computations required at filtering by reducing the number of FIR filter taps or terms. By using shorter finite impulse response (FIR) filters for low-pass H′ 0 (z)  1502  and high-pass H′ 1 (z)  1503  filters in the second level of the discrete wavelet transformation, the computational cost is reduced without requiring partial decimation prior prediction. Again, by having the decimators in the band-pass subbands Y 1 (z) and in the high-frequency subbands Y 0 (z) at the output of prediction block  1504 , spatial localization variance is minimized, allowing best prediction to be achieved for the high-frequency subbands. In systems where the wavelet transformation is followed by quantization and coding, such that perfect reconstruction is not a sought condition, using shorter FIR filters, H′ 0 (z)  1502  and H′ 1 (z)  1503  for the high-pass at the second and higher levels in a two-dimensional filter bank is a highly considerable approach for reducing the number of computations.  
         [0052]      FIG. 16  shows a one-dimensional analysis filter bank, which can be used in a two-dimensional system as a separable transform by first applying the filter bank in one dimension (for example along y) then in the other dimension (for example along x). In this system the second level low-frequency subbands Y 2 (z) are at the output of H 0 (z)H 0   1 (z 2 )  1600 . Similarly, the band-pass subbands Y 1 (z) are obtained from H 0 (z)H′ 1 (z 2 )  1601  output path.  FIG. 16  shows a system where the computational intensity at the filtering stages is reduced by using shorter FIR filters in the second stage, H′ 0 (z) and H′ 1 (z)  1602 , and further by splitting the decimators in the band-pass subbands around the predictor block  1604 . While this scheme offers less computations at filtering compared to that required in  FIG. 15 , it introduces certain spatial localization variance prior prediction due to decimation being split.  
         [0053]      FIG. 17  illustrates analysis-by-synthesis prediction of the first level high-pass subbands Y 0 (z) to obtain the predictor parameters Ŷ 0 (z). H 0 (z) and H 1 (z), as denoted previously are part of the analysis filter bank, are represented in this two-level wavelet decomposition ( 1710 ) by filters H 0 (z) H 0 (z 2 ) 1700, H 0 (z) H 1 (z 2 ) 1701 and H 1 (z) to yield in their output paths the lowest frequency subband Y 2 (z), band-pass subbands Y 1 (z) and highest frequency subbands Y 0 (z), respectively. Similarly, G 1 (z) and G 0 (z) correspond to the synthesis inverse discrete wavelet transform, IDWT, represented by block  1711 . Full interpolation (↑) illustrates that there is no distribution of the decimators around the predictor  1707 . Only the output of V 1 (z)  1706 , in the inverse discrete wavelet transformation, IDWT, section of system  1711  is used by the predictor to extract the highest frequency subbands Y 0 (z), from the synthesized signal V 1 (z)  1706 . In  FIG. 17 , this predicted subband is represented by signal V′ 0 (z). Thus, the output recovered signal {tilde over (X)}(z) is obtained by processing the lowest frequency subbands V 2 (z)  1705 , the bandpass subbands V 1 (z) and the predicted subbands V′ 0  (z), which must be filtered by the synthesis lowpass filter G 1 (z)  1709  to yield V 0 (z). It is then the summation  1708  of signals V 2 (z), V 1 (z), and V 0 (z) which give the recovered input signal X(z) represented by {tilde over (X)}(z). It should be noted that {tilde over (X)}(z)=X(z) in a perfectly reconstructed system. However, in  FIG. 17 , {tilde over (X)}(z) illustrates a best approximation of the input signal X(z).  
         [0054]     To completely avoid the spatial location variance due to decimation,  FIG. 17  illustrates where the highest frequency subband, Y 0 (z) is predicted to obtain the predictor parameters Ŷ 0 (z) from the synthesized signal V 1 (z)  1706 . Again, V 1 (z) is obtained by applying the inverse discrete wavelet transformation by using synthesis filters G 0 (z) and G 1 (z) to the second level band-pass filter output signal, Y 1 (z). In the case of a two-dimensional input, such as an image, the channels, Y 0 (z), Y 1 (z) and Y 2 (z) correspond to subbands [ 8 ,  9 ,  10 ] for signal Y 0 (z), subbands [ 5 ,  6 ,  7 ] for Y 1 (z) and [ 1 ,  2 ,  3 ,  4 ] for signal Y 2 (z) where subbands [ 1 ,  2 ,  3 ,  4 ,  5 ,  6 ,  7 ,  8 ,  9 ,  10 ] are as shown in  FIG. 7 .  
         [0055]     Again referring to  FIG. 17 , output signal {tilde over (X)}(z) is the sum of the synthesized subbands V 2 (z)  1705  V 1 (z)  1706  and V 0 (z)  1710 . The synthesis bank processes the outputs from the analysis bank at the encoder by performing the inverse discrete wavelet transformation. This process begins be interpolating by  4  the lowest frequency subband Y 2 (z) and also interpolating by  4  the band-pass subband Y 1 (z). The interpolated Y 2 (z) signal is filtered by the filters G 0 (z 2 )G 0 (z) to obtain the synthesized signal V 2  (z) corresponding to the lowest frequency subbands of the recovered signal. Similarly, the interpolated Y 1 (z) signal is filtered by G 1 (z 2 )G 0 (z) to obtain the synthesized signal V 1 (z). V 1 (z) from the synthesis bank and Y 0 (z) from the analysis bank are inputted to the predictor to obtain the predictor parameters, denoted by Ŷ 0 (z) and V′ 0 (z). Signal V′ 0 (z) is then filtered by the synthesis high-pass filter G 1 (z) to obtain V 0 (z).  
         [0056]     The following equations, written in matrix form, show the relationship between the signals of  FIG. 17 . Inputs, outputs, and filters are all in the Z-domain. However, to simplify the expressions Z is omitted, for example, 
 
Y (1) (z)≡Y (1) , H 0 (z)≡H 0 , H 0 (z)X(z)H 0   t (z)≡H 0 XH 0   t  . . . and so on  eq. (5) 
 
         [0057]     Consider the two-dimensional case as an extension of the one-dimensional case. Let X(z)≡X be the input image of size N×N. At the analysis bank, the forward discrete wavelet transforms (DWT) in  FIG. 17  is represented as a two-dimensional two-level filter bank. Applying this analysis bank along both dimensions of input image X(z), the first-level DWT, Y (1)  is expressed as:  
                     Y     (   1   )       =       ⁢       [           H   0               H   1           ]     ⁢     X   ⁡     [           H   0   t           H   1   t           ]                     =       ⁢     [             H   0     ⁢     XH   0   t               H   0     ⁢     XH   1   t                   H   1     ⁢     XH   0   t               H   1     ⁢     XH   1   t             ]                 =       ⁢     [           Y   LL           Y   LH               Y   HL           Y   HH           ]                   eq   .           ⁢     (   6   )               
 
 where H 0   t  represents the transpose of the matrix representation of analysis H 0 (z)≡H 0 . Similarly H 1   t  represents transpose of the matrix representation of analysis high-pass H 1 (z)≡H 1 . 
 
         [0058]     Y LL , Y LH , Y HL , and Y HH  are the four subbands obtained after applying the first level forward discrete wavelet transform, DWT. Y LL  represents the low-frequency subband, Y LH  and Y HL  are band-pass vertically oriented subband and band-pass horizontally oriented subband, respectively. Y HH  is the high frequency (diagonal) subband. Referring to  FIG. 17 , Y 0 (z) corresponds to Y HL , Y LH  and Y HH  when processing the analysis band two-dimensionally. Again considering the case where the input signal is two-dimensional, the second level forward discrete wavelet transformation, DWT, uses the decimated subband Y LL  from the first level as the input to the second level, in order to obtain signal Y (2)  in eq. (7). In eq. (7) signal Y (2)  contains subbands Y HL , Y LH , and Y HH , which are the first level decomposition subbands related to signal Y 0 (z) shown in  FIG. 17 . Matrix Y (2)  will also contain the elements obtained by applying the second level DWT to Y LL  of eq. (6) to give the two-dimensional representation of signals Y 1 (z) and Y 2 (z). It can also be easily observed that Y 2 (z) in  FIG. 17  corresponds to subband Y LLLL  in eqs. (7) and (8) and similarly Y 1 (z) corresponds to subbands Y LLLH , Y HLLL , and Y HHHH  also from eq. (7), eq. (9), eq. (10) and eq. (11).  
                     Y     (   2   )       =       ⁢     [             [           H   0   ′               H   1   ′           ]     ⁢       Y   LL     ⁡     [           H   0     ′   ⁢           ⁢   t             H   1     ′   ⁢           ⁢   t             ]               Y   LH               Y   HL           Y   HH           ]                 =       ⁢     [           [             H   0   ′     ⁢     Y   LL     ⁢     H   0     ′   ⁢           ⁢   t                 H   0   ′     ⁢     Y   LL     ⁢     H   1     ′   ⁢           ⁢   t                     H   1   ′     ⁢     Y   LL     ⁢     H   0     ′   ⁢           ⁢   t                 H   1   ′     ⁢     Y   LL     ⁢     H   1     ′   ⁢           ⁢   t               ]           Y   LH               Y   HL           Y   HH           ]                 =       ⁢     [           [           Y   LLLL           Y   LLLH               Y   HLLL           Y   HHHH           ]           Y   LH               Y   HL           Y   HH           ]                   eq   .           ⁢     (   7   )               
 
 where the second-level discrete wavelet transformation (DWT) processing is expressed with “primed” matrices shown in eq. (7) and ‘t’ denotes transpose. From equation (7) we derive: 
 
Y LLL =H 0 ′Y LL H 0 ′ t   eq. (8) 
 
Y LLLH =H 0 ′Y LL H 1 ′ t   eq. (9) 
 
Y HLLL =H 1 ′Y LL H 0 ′ t   eq. (10) 
 
Y HHHH =H 1 ′Y LL H 1 ′ t   eq. (11) 
 
 Again, ‘t’ denoting the transpose of the matrix and ‘primed’ representing the second-level discrete wavelet transformation. 
 
 Applying now synthesis to subbands Y LLLL , Y LLLH , Y HLLL , Y HHHH , we have:  
               Y   LL     =         [           G   0     ′   ⁢           ⁢   t             G   1     ′   ⁢           ⁢   t             ]     ⁡     [             H   0   ′     ⁢     Y   LL     ⁢     H   0     ′   ⁢           ⁢   t                 H   0   ′     ⁢     Y   LL     ⁢     H   1     ′   ⁢           ⁢   t                                                 H   1   ′     ⁢     Y   LL     ⁢     H   0     ′   ⁢           ⁢   t                 H   1   ′     ⁢     Y   LL     ⁢     H   1     ′   ⁢           ⁢   t               ]       ⁡     [           G   0   ′               G   1   ′           ]               eq   .           ⁢     (   12   )               
 
 where G 0 ′, and G 1 ′ are the and high-pass synthesis filters in matrix form. t denotes the transpose of the matrix, such that G 0 ′ t  is the matrix transposed of G 0 ′ matrix filter and G 1 ′ t  is the matrix transposed of the high-pass filter G 1 ′ also represented in matrix form. 
 
 With invertibility conditions 
 
 I=. G   0 ′ t   H   0   ′+G   1 ′ t   H   1 ′  eq. (13) 
 
 I=H   0 ′ t   G   0   ′+H   1 ′ t   G   1 ′  eq. (14) 
 
 where I is the Identity matrix. 
 
 Therefore from eq. (12) the synthesized LL subband is the sum of four parts, of which the ones of interest are: 
 
S LH =G 1 ′ t H 1 ′Y LL H 0 ′ t   G   0 ′ (vertical subband)  eq. (15) 
 
S HL =G 1 ′ t H 1 ′Y LL H 0 ′ t G 0 ′ (horizontal subband)  eq. (16) 
 
S HH =G 1 ′ t H 1 ′Y LL H 1 ′ t G 1 ′ (diagonal subband)  eq. (17) 
 
 The vertical, horizontal, and diagonal subbands of eq. (15), (16), and (18), respectively, correspond to signal V 1 (z) of  FIG. 17  assuming two-dimensional processing. Therefore, these are the signals of interest to be applied to the predictor block of  FIG. 17 . 
 
         [0059]     Several known methods or models of prediction such as auto-regressive-moving,-average (ARMA), moving average (MA), auto-regressive (AR), linear, may be used to predict the desired subbands. For example, the process of predicting the vertical subband, Y LH , resulting from a first-level discrete wavelet transformation after applying a first-level analysis filter bank, from a synthesized S LH  subband expressed accordingly in equation (15), may be expressed by the general equation (18) as follows: 
 
Predicted vertical subband≡Predicted  Y   LH   ≡Ŷ   LH   =P ( Y   LH   , S   LH )  eq. (18) 
 
 Similarly, 
 
Predicted horizontal subband≡Predicted  Y   HL   ≡Ŷ   HL   =P ( Y   HL   , S   HL )  eq. (19) 
 
 and 
 
Predicted diagonal subband≡Predicted  Y   HH   ≡Ŷ   HH   =P ( Y   HH   , S   HL )  eq. (20) 
 
 Where Ŷ denotes predicted subband, S LH , S HL , and S HH  are the synthesized subband from the second-level inverse wavelet transformation as given by equations (15), (16), and (17), respectively. 
 
         [0060]      FIG. 18  illustrates analysis-by-synthesis prediction of the first-level, high-pass subband, Y 0 (z) to obtain the predicted subband Ŷ 0 (z). H 0 (z) and H 1 (z) are the low and high-pass filters, respectively, corresponding to the analysis filter bank. G 0 (z) and G 1 (z) are the low-pass and high-pass synthesis filters, respectively, corresponding to the inverse discrete wavelet filter bank (IDWT).  FIG. 18  shows the system in  FIG. 17  with partial interpolation in front of synthesis.  
         [0061]     Thus, in summary, the invention includes an encoder and decoder that utilizes a filter bank to decorrelate an input data signal; decimators to down sample the filtered input data signal and a predictor to extract cross-subband dependence. A decoder then recovers the received data signal and includes interpolators to upsample the received compressed data signal, multilevel filter bank to perform an inverse wavelet transformation and a predictor to extract cross-subband correlations.  
         [0062]     While the preferred embodiments of the invention have been illustrated and described, it will be clear that the invention is not so limited. Numerous modifications, changes, variations, substitutions and equivalents will occur to those skilled in the art without departing from the spirit and scope of the present invention as defined by the appended claims.