Abstract:
The present invention teaches a method of compressing still images in a multi-purpose compression system. The current invention teaches preprocessing of the images to a YUV 4:2:0 format and decomposing the images using two-dimensional Discrete Wavelet Transformation. The current invention teaches that filters may be selected based on image dimensions. After the image is decomposed, the frequency coefficients are quantized and the data is entropy encoded. The image is restored by reversing the compression process.

Description:
CROSS-REFERENCE TO RELATED APPLICATION 
     This application claims benefit from U.S. Provisional Patent Application No. 60/396,380, filed Jul. 16, 2002, entitled “Method Apparatus and System for Compressing Still Image in Multipurpose Compression System.” 
    
    
     FIELD OF THE INVENTION 
     The present invention relates to devices for the processing of images, and in particular for the compression of static images to a high degree and the obtaining of a restored image of high image quality. More specifically, the present invention teaches a method of pre-processing an image, decomposition of the image using wavelet transform, and quantizing the frequency coefficients such that images can be compressed to a high degree and be restored with minimal information loss. 
     BACKGROUND OF THE INVENTION 
     Still images are an effective means for describing various subjects. Information about the subject is accumulated in image databases. At the present time a great multitude of types of databases have been developed that are oriented to the applications of special methods of analysis and information processing. 
     Current digital transmitting systems have a number of advantages for image processing in comparison with analog systems. Recently developed techniques have led to improved methods to reduce image size. Such methods are extremely useful for digital data storing and processing or manipulating. So it may be said that data size reduction is a compression process. As to the architecture, it is possible now to put a complete compression process into a single chip. The main objective of a compression process is to achieve the highest compression ratio and in the same time to provide the minimum data loss that may lead to decompressed image quality degradation. 
     SUMMARY OF THE INVENTION 
     Systems for encoding and decoding still image of various dimensions currently exist. The methods described herein can be applied in these systems, and they may be used for Intra frame encoding as well. The current invention teaches encoding images in the following steps: 
     1. Image preprocessing (switch to original format), 
     2. Image decomposition by the wavelet transform according to features described herein (frequency block enumeration etc.), 
     3. Quantizing frequency coefficients using schemes described in detail herein, and 
     4. Restoring the image by performing the steps in reverse. 
     The method of the current invention has some significant features, which are extremely important for image processing and which can really improve restored image quality and raise the compression ratio relative to methods currently used. It has been found that compression using the method of the current invention yeilds results higher than well-known worldwide standards (such as JPEG2000). Comparative data is in Tables 1, 2, 3 below shows PSNR values for JPEG2000 and the method taught by this application. 
     The method taught herein allows the original image to be formatted during preprocessing, and the image decomposition and frequency coefficient quantizing taught herein allows the compression ration to be increased relative to currently known methods. 
     
       
         
               
               
               
             
               
               
               
               
             
           
               
                   
                 TABLE 1 
               
               
                   
                   
               
               
                   
                 Horse 
                 Landscape 
               
               
                   
                   
               
             
             
               
                   
               
             
          
           
               
                   
                 JPEG2000 
                 31.72 
                 25.03 
               
               
                   
                 Given method 
                 31.67 
                 26.43 
               
               
                   
                   
               
             
          
         
       
     
     
       
         
               
               
               
             
               
               
               
               
             
           
               
                   
                 TABLE 2 
               
               
                   
                   
               
               
                   
                 Fish 
                 Squirrel 
               
               
                   
                   
               
             
             
               
                   
               
             
          
           
               
                   
                 JPEG2000 
                 35.79 
                 29.61 
               
               
                   
                 Given method 
                 35.789 
                 30.17 
               
               
                   
                   
               
             
          
         
       
     
     
       
         
               
               
             
               
               
               
             
           
               
                   
                 TABLE 3 
               
               
                   
                   
               
               
                   
                 Robot 
               
               
                   
                   
               
             
             
               
                   
               
             
          
           
               
                   
                 JPEG2000 
                 32.06 
               
               
                   
                 Given method 
                 33.236 
               
               
                   
                   
               
             
          
         
       
     
    
    
     
       BRIEF DISCRIPTION OF THE DRAWINGS 
         FIG. 1  illustrates the joining of the U and V color planes together into a single plane. 
         FIG. 2  illustrates the Y plane after the first one-dimensional wavelet transform has been executed. 
         FIG. 3  illustrates the Y plane after the second one-dimensional wavelet transform has been executed. 
         FIG. 4  illustrates the enumeration of the Y plane. 
         FIG. 5  illustrates the enumeration of the combined UV plane. 
         FIG. 6  is an example of a pass for quantizing the frequency coefficients in the Y plane. 
         FIG. 7  is an example of a pass for quantizing the frequency coefficients in the combined UV plane. 
         FIG. 8  illustrates the construction of the Shift Array. 
     
    
    
     DETAILED DESCRIPTION OF THE INVENTION 
     The method of the current invention is executed according to the following steps: 
     Step 1: An image in RGB format is converted into an in image in YUV 4:4:4 format. Shown below is an example of four neighboring pixels in that format having different values for Y, U, and V. 
     
       
         
               
               
               
             
           
               
                   
                   
               
             
             
               
                   
                 Y 1 U 1 V 1   
                 Y 2 U 2 V 2   
               
               
                   
                 Y 3 U 3 V 3   
                 Y 4 U 4 V 4   
               
               
                   
                   
               
             
          
         
       
     
     Step 2: The image in YUV 4:4:4 is converted into an image in YUV 4:2:0. 
     Step 3: The U and V color planes are combined as illustrated in  FIG. 1 . 
     Step 4: A one-dimensional Discrete Wavelet Transform is then executed for every line of the Y plane. After the transform is executed, two blocks, with multiple rows and columns are formed such that on block (L) is for low frequencies and the other block (H) is for high frequencies ( FIG. 2 ). 
     Step 5: A one-dimensional Discrete Wavelet Transform is then executed for every column of the obtained plane. It is the second step of Discrete Wavelet Transform. Referring to  FIG. 3 , after the transform is executed, 4 blocks are formed as follows: (LL) low frequency across and up, (LH) low frequency across and high frequency up, (HL) high-frequency across and low-frequency up, (HH) high-frequency across and high-frequency up. 
     At this stage the first level of two-dimensional Wavelet Transform is complete. A two-dimensional Discrete Wavelet Transform is then executed for the LL block and for each subsequent LL block until five levels of Two-dimensional Wavelet Transform have been executed as shown in  FIG. 4 . 
     Step 6: A one-dimensional Discrete Wavelet Transform is then executed for every line of the UV plane. After the transform is executed, two blocks having multiple rows and columns are formed such that on block (L) is for low frequencies and the other block (H) is for high frequencies ( FIG. 2 ). 
     Step 7: A one-dimensional Discrete Wavelet Transform is then executed for every column of the obtained plane. It is the second step of Discrete Wavelet Transform. Referring to  FIG. 3 , after the transform is executed, 4 blocks are formed as follows: (LL) low frequency across and up, (LH) low frequency across and high frequency up, (HL) high-frequency across and low-frequency up, (HH) high-frequency across and high-frequency up. 
     At this stage the first level of two-dimensional Wavelet Transform is complete. A two-dimensional Discrete Wavelet Transform is then executed for the LL block and for each subsequent LL block until five levels of Two-dimensional Wavelet Transform have been executed as shown in  FIG. 5 . 
     The significant aspect of the current invention is that it is possible to select a filter according to image dimensions. For the SIF format a 22/14 filter is used, and for the R601 format a 5/3 filter is used. Filtering coefficients are shown in Table 4 below. 
     
       
         
               
             
               
               
               
               
             
               
               
               
               
             
           
               
                 TABLE 4 
               
             
             
               
                   
               
               
                 Filtering coefficients. 
               
             
          
           
               
                 22/14 
                   
                 5/3 
                   
               
             
          
           
               
                 G 
                 H 
                 G 
                 H 
               
               
                   
               
               
                   0.730018808 
                   
                 −1.7677669529e−01 
                   
               
               
                   0.078814418 
                   
                   3.5355339059e−01 
                 3.5355339059e−01 
               
               
                 −0.142800426 
                   
                   1.0606601717e+00 
                 7.0710678118e−01 
               
               
                   0.018097252 
                   
                   3.5355339059e−01 
                 3.5355339059e−01 
               
               
                   0.036833941 
                   0.648022975 
                 −1.7677669529e−01 
               
               
                 −0.0093268515 
                   0.162005743 
               
               
                 −0.0065812408 
                 −0.097203451 
               
               
                   0.001207186 
                 −0.02777241 
               
               
                   0.000975453 
                   0.021600768 
               
               
                 −0.000071375 
                   0.0029456 
               
               
                 −0.00006039 
                 −0.002492395 
               
               
                 −0.00006039 
                 −0.002492395 
               
               
                 −0.000071375 
                   0.0029456 
               
               
                   0.000975453 
                   0.021600768 
               
               
                   0.001207186 
                 −0.02777241 
               
               
                 −0.0065812408 
                 −0.097203451 
               
               
                 −0.0093268515 
                   0.162005743 
               
               
                   0.036833941 
                   0.648022975 
               
               
                   0.018097252 
               
               
                 −0.142800426 
               
               
                   0.078814418 
               
               
                   0.730018808 
               
               
                   
               
             
          
         
       
     
     Step 8: After five levels of DWT have been executed, the frequency blocks are enumerated as shown in  FIGS. 4 and 5 . Vertical passes for the frequency coefficients are then executed on the following blocks in order: 2, 3, 8, 9, 14, 15, 20, 21, 26, and 27. Horizontal passes are executed on the remaining blocks. Such passes allow for effective quantization, and examples are shown in  FIGS. 6 and 7 . 
     Step 9: Every frequency coefficient is quantized as follows:
 
Δ i   =q   i ·(20+0.5 ·bpp ),  i =0, . . . , 31.
 
Where: i is the number of a frequency block, q i  is a value from Table 5 or Table 6 chosen according to i, and bpp is a parameter which is set in dependence of the compression ration 0&lt;bpp&lt;255.
 
     
       
         
               
               
               
             
           
               
                   
                 TABLE 5 
               
               
                   
                   
               
               
                   
                 Serial number of the frequency block 
                   
               
               
                   
                 (even numbers - Y frequency blocks) 
               
               
                   
                 i 
                 Corresponding value q i   
               
               
                   
                   
               
             
             
               
                   
                  0 
                 0.040000 
               
               
                   
                  2 
                 0.056568 
               
               
                   
                  4 
                 0.056568 
               
               
                   
                  6 
                 0.080000 
               
               
                   
                  8 
                 0.113137 
               
               
                   
                 10 
                 0.113137 
               
               
                   
                 12 
                 0.160000 
               
               
                   
                 14 
                 0.226274 
               
               
                   
                 16 
                 0.226274 
               
               
                   
                 18 
                 0.320000 
               
               
                   
                 20 
                 0.452544 
               
               
                   
                 22 
                 0.452544 
               
               
                   
                 24 
                 0.640000 
               
               
                   
                 26 
                 0.905097 
               
               
                   
                 28 
                 0.905097 
               
               
                   
                 30 
                 1.280000 
               
               
                   
                   
               
             
          
         
       
     
     
       
         
               
               
               
             
           
               
                   
                 TABLE 6 
               
               
                   
                   
               
               
                   
                 Serial number of the frequency block 
                   
               
               
                   
                 (odd numbers - UV frequency 
               
               
                   
                 blocks) 
                 Corresponding value 
               
               
                   
                 i 
                 q i   
               
               
                   
                   
               
             
             
               
                   
                  1 
                 0.000100 
               
               
                   
                  3 
                 0.000100 
               
               
                   
                  5 
                 0.000100 
               
               
                   
                  7 
                 0.080000 
               
               
                   
                  9 
                 0.113137 
               
               
                   
                 11 
                 0.113137 
               
               
                   
                 13 
                 0.160000 
               
               
                   
                 15 
                 0.226274 
               
               
                   
                 17 
                 0.226274 
               
               
                   
                 19 
                 0.320000 
               
               
                   
                 21 
                 0.452544 
               
               
                   
                 23 
                 0.452544 
               
               
                   
                 25 
                 0.640000 
               
               
                   
                 27 
                 0.905097 
               
               
                   
                 29 
                 0.905097 
               
               
                   
                 31 
                 1.280000 
               
               
                   
                   
               
             
          
         
       
     
     Step 9.1: Every coefficient is multiplied by Δ i .
 
if Δ i ·max( f   i )&gt;63
 
     or
 
if Δ i ·min( f ) i &lt;−63
 
so Δ i  is corrected to satisfy following conditions:
 
Δ i ·max( f   i )&lt;63
 
Δ i ·min( f ) i &gt;−63.
 
     Step 9.2: The obtained values are rounded to the closest integer value and recorded in one-dimensional array according to the order of the vertical and horizontal passes. 
     Step 10: The sequence of coefficients is quantized by the modified RLE method such that two arrays, a Data Array and Length Array, are obtained. 
     Step 11: Values are read from the Data Array and replaced by the corresponding value from Table 7 below. 
     
       
         
               
             
               
               
               
             
           
               
                 TABLE 7 
               
             
             
               
                   
               
               
                 Replaced values. 
               
             
          
           
               
                   
                 Three-byte replaced values 
                 One-byte replacing values 
               
               
                   
                   
               
               
                   
                 0xc140bf 
                 0x01 
               
               
                   
                 0xbf40c1 
                 0x02 
               
               
                   
                 0xc140c1 
                 0x03 
               
               
                   
                 0xbf40bf 
                 0x04 
               
               
                   
                 0xc1c0c0 
                 0x05 
               
               
                   
                 0xc0c0bf 
                 0x06 
               
               
                   
                 0xc0c0c1 
                 0x07 
               
               
                   
                 0xbfc0c0 
                 0x08 
               
               
                   
                 0xc1c0bf 
                 0x09 
               
               
                   
                 0xc1c0c1 
                 0x0a 
               
               
                   
                 0xbfc0c1 
                 0x0b 
               
               
                   
                 0xbfc0bf 
                 0x0c 
               
               
                   
                 0xbfc1bf 
                 0x0d 
               
               
                   
                 0xc1bfc1 
                 0x0e 
               
               
                   
                 0x400040 
                 0x0f 
               
               
                   
                   
               
             
          
         
       
     
     Step 11.1: If a replacement value cannot be found in Table 7, a one-element shift is executed and Table 7 is rechecked for a replacement value. 
     Step 12: The relative displacement for values in the Length Array that are higher than 225 are placed in an additional array (Shift Array) we write the relative displacement for the values from Length Array which are higher than 255. The Shift Array is shown in  FIG. 8  and its formation is discussed below. 
     The element with the highest value above 255 is located and its displacement relative to the first element of the Length Array is recorded in the shift array. The displacement, relative to the previous high value element, of remaining elements with values higher than 255 are then recorded in the Shift Array in order of the value. 
     Step 13: The Shift array is written to the end of the Length Array. 
     Step 14: The Length Array and Data Array values are then encoded by entropy encoding methods. 
     For block numbers 30 and 31 the forgoing steps are not applied. Instead, these blocks are simply entropy encoded if this is reasonable. 
     Step 15: The image is restored by reversing the steps above. Three byte restoration values are shown in Table 8 . 
     
       
         
               
             
               
               
               
             
           
               
                 TABLE 8 
               
             
             
               
                   
               
               
                 Replacing values. 
               
             
          
           
               
                   
                   
                 Three-byte replacing 
               
               
                   
                 One-byte replaced values 
                 values 
               
               
                   
                   
               
               
                   
                 0x01 
                 0xc140bf 
               
               
                   
                 0x02 
                 0xbf40c1 
               
               
                   
                 0x03 
                 0xc140c1 
               
               
                   
                 0x04 
                 0xbf40bf 
               
               
                   
                 0x05 
                 0xc1c0c0 
               
               
                   
                 0x06 
                 0xc0c0bf 
               
               
                   
                 0x07 
                 0xc0c0c1 
               
               
                   
                 0x08 
                 0xbfc0c0 
               
               
                   
                 0x09 
                 0xc1c0bf 
               
               
                   
                 0x0a 
                 0xc1c0c1 
               
               
                   
                 0x0b 
                 0xbfc0c1 
               
               
                   
                 0x0c 
                 0xbfc0bf 
               
               
                   
                 0x0d 
                 0xbfc1bf 
               
               
                   
                 0x0e 
                 0xc1bfc1 
               
               
                   
                 0x0f 
                 0x400040 
               
               
                   
                   
               
             
          
         
       
     
     The current invention discloses methods and procedures for compressing still images in multi-purpose compression systems. The methods and procedures disclosed in the current application can be executed or preformed in a computer, other microprocessors, programmable electronic devices or other electronic circuitry that are used for encoding images. They can be loaded into the above devices as software, hardware, or firmware. They can be implemented and programmed as discrete operations or as a part of a larger image compression strategy. 
     INDUSTRIAL APPLICABILITY 
     In compliance with the statute, the invention has been described in language more or less specific as to structural features. It is to be understood, however, that the invention is not limited to the specific features shown or described, since the means and construction shown or described comprise preferred forms of putting the invention into effect. Additionally, while this invention is described in terms of being used to provide a method of compressing still images in multi-purpose compression systems, it will be readily apparent to those skilled in the art that the invention can be adapted to other uses as well. The invention should not be construed as being limited to image compression and is therefore, claimed in any of its forms or modifications within the legitimate and valid scope of the appended claims, appropriately interpreted in accordance with the doctrine of equivalents.