Wavelet transform coding technique

Abstract

A wavelet transform coding technique is provided, which may be part of TROBIC or may be used independently in a wide variety of compression applications. The wavelet coding technique is carried out by a simple block codec with wavelets (SBCW) that uses wavelet filters to transform 32×2 image blocks into subband coefficients organized in a tree structure. These coefficients are then encoded using a novel entropy coding technique with precise rate control. The Two Row Buffer Image Compression (TROBIC) technique operates on 32×2 blocks of pixels and uses a block-based coding scheme to provide alternative coding modes for image blocks containing different types of image data. The TROBIC algorithm automatically evaluates the image presented to determine regions containing text, graphics, synthetic images and natural images along with determining the most effective combination of global-index coding, local-index coding, lossless coding and wavelet coding to use to guarantee the desired compression ratio and high quality.

What is claimed is:  
     
       1. A method of compressing a digitized image, comprising the steps of: 
       segmenting the image into a plurality of blocks of data, each block of data being defined by a plurality of columns of data and a plurality of rows of data;  
       transforming each of the plurality of blocks of data into a corresponding block of subband coefficients, said transforming step including applying a first filter to each of the columns of data in each of the plurality of blocks and applying a second filter, different from the first filter, to each of the rows of data in each of the plurality of blocks;  
       quantizing the subband coefficients; and  
       coding the quantized subband coefficients.  
     
     
       2. The method of  claim 1 , wherein said segmenting step comprises segmenting the image into 32×2 blocks of pixel data. 
     
     
       3. The method of  claim 1 , wherein the first filter comprises a Haar filter and the second filter comprises a 2-6 wavelet filter. 
     
     
       4. The method of  claim 1 , wherein said transforming step comprises repeatedly applying the second filter on a top row of data in each block to obtain a low pass coefficient for each block. 
     
     
       5. The method of  claim 1 , wherein said quantizing step comprises organizing the subband coefficients together into a plurality of different groups using a tree structure in which each level of the tree structure corresponds to a particular level of resolution and determining a number of right shifts to be applied to all the subband coefficients. 
     
     
       6. The method of  claim 5 , wherein said coding step comprises coding each of the plurality of different groups of subband coefficients using the same number of bits per coefficient, wherein the number of bits per coefficient is determined together with the number of right shifts so that the total number of bits used for a block is no more than a given budget. 
     
     
       7. An encoder/decoder system for compressing and decompressing a digitized image, comprising: 
       an encoder comprising:  
       means for transforming each of a plurality of blocks of pixel data into a corresponding block of subband coefficients, each block of pixel data being defined by a plurality of columns of data and a plurality of rows of data, the transforming including applying a first filter to each of the columns of data in each of the plurality of blocks and applying a second filter, different from the first filter, to each of the rows of data in each of the plurality of blocks;  
       a quantizer for quantizing the subband coefficients;  
       an entropy-encoder for coding the quantized subband coefficients and generating a bit stream of coded data;  
       a decoder comprising:  
       an entropy decoder for decoding the bit stream of coded data and generating a plurality of blocks of coefficients;  
       a dequantizer for dequantizing the coefficients; and  
       means for inverse transforming each of the plurality of blocks of dequantized coefficients into a corresponding block of pixel data.  
     
     
       8. An encoder for compressing a digitized image, comprising: 
       means for transforming each of a plurality of blocks of pixel data into a corresponding block of subband coefficients, each block of pixel data being defined by a plurality of columns of data and a plurality of rows of data, the transforming including applying a first filter to each of the columns of data in each of the plurality of blocks and applying a second filter, different from the first filter, to each of the rows of data in each of the plurality of blocks;  
       a quantizer for quantizing the subband coefficients; and  
       an entropy-encoder for coding the quantized subband coefficients and generating a bit stream of coded data.  
     
     
       9. A decoder for decompressing a compressed image represented by a bit stream of coded data, comprising: 
       an entropy decoder for decoding the bit stream of coded data and generating a plurality of blocks of coefficients;  
       a dequantizer for dequantizing the coefficients; and  
       means for inverse transforming each of the plurality of blocks of dequantized coefficients into a corresponding block of pixel data, the inverse transforming including applying a first filter to each of a plurality of columns of dequantized coefficients in each of the plurality of blocks and applying a second filter, different from the first filter, to each of a plurality of rows of dequantized coefficients in each of the plurality of blocks to recover the corresponding blocks of pixel data.  
     
     
       10. A article of manufacture having embodying a program of instructions executable by a device for performing a method of compressing a digitized image, said program of instructions comprising: 
       instructions for segmenting the image into a plurality of blocks of data, each block of data being defined by a plurality of columns of data and a plurality of rows of data;  
       instructions for transforming each of the plurality of blocks of data into a corresponding block of subband coefficients, said transforming instructions including instructions for applying a first filter to each of the columns of data in each of the plurality of blocks and applying a second filter, different from the first filter, to each of the rows of data in each of the plurality of blocks;  
       instructions for quantizing the subband coefficients; and  
       instructions for coding the quantized subband coefficients.  
     
     
       11. The article of manufacture of  claim 10 , wherein said segmenting instructions includes instructions for segmenting the image into 32×2 blocks of pixel data. 
     
     
       12. The article of manufacture of  claim 10 , wherein the first filter comprises a Haar filter and the second filter comprises a 2-6 wavelet filter. 
     
     
       13. The article of manufacture of  claim 10 , wherein said transforming instructions includes instructions for repeatedly applying the second filter on a top row of data in each block to obtain a low pass coefficient for each block. 
     
     
       14. The article of manufacture of  claim 10 , wherein said quantizing instructions includes instructions for organizing the subband coefficients together into a plurality of different groups using a tree structure in which each level of the tree structure corresponds to a particular level of resolution. 
     
     
       15. The article of manufacture of  claim 14 , wherein said coding instructions includes instructions for coding each of the plurality of different groups of subband coefficients using the same number of bits per coefficient, wherein the number of bits per coefficient is determined so that the total number of bits used for a block is no more than a given budget.