Abstract:
A method for compression includes applying a discrete cosine transform to said image data to obtain transform coefficients, quantizing the transform coefficients by applying a quantization level scaled through a gain value, adjusting the gain value as a function of desired image parameters by executing a first time said quantization operation applying a first gain value and obtaining first quantized data, estimating statistically a second gain value suitable to obtain the desired image parameters, and executing a second time said quantization operation applying said second gain value. The operation of statistical estimation of the second gain value includes evaluating a threshold value as a function of the desired image parameters and setting to zero a percentage of coefficients of the first quantized data as a function of the threshold value.

Description:
RELATED APPLICATION 
     The present application claims priority of Italian Patent Application No. TO2004A000863 filed 10 Dec. 2004, which is incorporated herein in its entirety by this reference. 
     FIELD OF THE INVENTION 
     The present invention relates to techniques for image compression, and has been developed with specific attention paid to its possible application in rate-control procedures in the context of the Joint Photographic Experts Group (JPEG) standard. 
     BACKGROUND OF THE INVENTION 
     Digital images are commonly used in several applications such as, for example, in digital still cameras (DSCs). 
     A digital image includes of a matrix of elements, commonly referred to as bitmap. Each element of the matrix, which represents an elementary area of the image (a pixel or pel); is formed by several digital values that indicate corresponding components of the pixel. 
     Digital images typically undergo to processes of compression in order to increase the number of digital images that can be stored simultaneously, for example in the memory of a DSC. Furthermore, this enables transmission of digital images in an easier way and in a shorter time. 
     A compression method commonly used in standard applications is the compression according to the so-called JPEG standard, which is described in the specification CCITT T.81, 1992. 
     In the JPEG algorithm, blocks of pixels of a size of 8×8 bits are extracted from the digital image. Then, coefficients of the discrete cosine transform (DCT) are calculated for the components of each pixel block. The DCT coefficients are then quantized using corresponding quantization tables. The quantized DCT coefficients are then coded in order to obtain a compressed digital image, from which it is possible to extract later, via a decompression procedure, the corresponding original digital image. 
     In some applications, it is necessary to have available a memory of a substantially constant size to store each compressed digital image. This problem is particularly serious, for example in digital still cameras. In fact, in this case, it must be ensured that a minimum number of compressed digital images will be stored in the memory of the camera in order to guarantee that a minimum number of photos can be taken. Control of the compression factor, or rate control, is rather difficult in algorithms, such as JPEG, where the size of the compressed digital image depends upon the contents of the corresponding original digital image. 
     The JPEG methods for image compression hence envisage adjustment of a gain factor, which multiplies the quantization levels, or quantizers, contained in the quantization tables. 
     In particular, the purpose of rate-control procedures is to find the gain factor that enables creation of a compressed image with a pre-set dimension of the output file via control of the value of bits per pixel (bpp). 
     JPEG rate-control procedures can be divided into two categories: iterative ones and statistical ones. 
     The iterative procedures regulate, through iterative steps, the value of the gain factor in order to achieve the desired value of bits per pixel. At each step the resulting value of bits per pixel produced by the compression operation is compared with the desired value of bits per pixel, and the gain factor is then modified accordingly. 
     The statistical procedures evaluate, instead, the required value of gain factor G, taking into account the statistical relations between the desired value of bits per pixel and measurements performed on the digital image. 
     JPEG rate-control procedures can be classified also on the basis of constant precision or constant number of cycles. 
     In the case of constant-precision procedures, the cycle is repeated until the bitrate lies outside a pre-set precision range. The advantage of constant-precision procedures is that the precision is always guaranteed, but neither the time nor the consumption required by the compression operation are predictable. 
     Instead, in the case of a constant number of cycles, the precision that will be achieved is not predictable, whilst the time and power consumption are fixed and limited. 
       FIG. 1  shows a block diagram of a JPEG compression chain. In  FIG. 1  the input image data, designated by the reference I, are supplied to a DCT block  10  and then to a quantization block  20 . The quantization block  20  receives and uses a scaled quantization level {tilde over (Q)} that is calculated as the product of a gain factor G and a quantization level Q, according to the relation shown in Equation 1:
     {tilde over (Q)} =G· Q     (1) 
     The quantization level Q is selected in a quantization table 60. 
     The output quantized by the quantization block  20  is then supplied at input to a zigzag-ordering block  30  and then to a Huffman-coding block. The Huffman-coding block  40  uses the output signal of the zigzag-ordering block  30  and a Huffman table  50  to generate a JPEG compressed image O. 
     From documents EP-A-1 179 004, EP-A-1 173 036, EP-A-1 179 026 and A. Bruna, M. Mancuso, “JPEG compression factor control: a new algorithm”, ICCE International Conference on Consumer Electronics, 19-21 Jun. 2001, pp. 206-207, a JPEG rate-control procedure is known based upon the statistical properties of JPEG compression. 
     Said procedure is based upon the statistical relation between the values of bits per pixel and the gain factor. In particular, the relation considered is that established between the gain factor and the factor of bits per pixel when the image is compressed with fixed quantization tables. 
     Said procedure is a constant-cycle procedure that includes only one cycle, but includes two steps: a first step of recovery, or retrieval, and a second step of rate control. The first, retrieval, step is used for evaluating the parameters necessary to solve the statistical model. 
     The function that links the gain factor to the value of bits per pixel obtained carrying out a compression of the image with a pre-set factor is approximated via a parabola or a quadratic relation. 
     The main steps of such a procedure can then be summarized as follows:
         calculating for all the images of the data base a gain factor (Gain*) that produces the desired value of bits per pixel (for example, through a bisection algorithm);   choosing an intermediate value of gain factor Int_G for performing a first compression, considering the value of gain factor that produces the minimum spreading of the pairs &lt;bpp, Gain&gt; on the set of images of the data base; and   using a parabolic function for interpolating the gain factor Gain* as a function of the value of bpp of the compressed-image data obtained applying the value of gain factor Int_G, according to the following equation:
 
 G=a·bp   2   +b·bp+c   (2)
 
where a, b, c indicate the coefficients of the parabolic function.
       

     The retrieval step supplies at an output the intermediate value of gain factor Int_G for the first compression and the coefficients of the parabola (a, b, c). These values are set in relation with the images of the data base, with the desired value of bits per pixel, and with the subsampling parameters of luminance and chrominance (YUV). When some of these parameters are changed, the values for the changed settings must be retrieved. 
     For applications for example in digital still cameras, all the cases handled are previously considered and the corresponding settings are retrieved. 
       FIG. 2  is a schematic illustration of the main processing steps executed in the step of rate control with a statistical procedure, which comprise: 
     compressing the image data I, using quantization tables pre-scaled according to the intermediate values of gain factor Int_G in a JPEG-compression block  70 ; 
     using the value of bits per pixel bpp of the image supplied at output by the JPEG-compression block  70  to estimate a gain factor defined as statistical gain G s  by means of the parabolic function shown in Equation 2; in  FIG. 2  said estimation step is represented by a graph  80  that represents the relation between the gain factor Gain* calculated on the image data base and the value of bits per pixel bpp; and 
     using the estimated gain factor G s  for a final JPEG-compression step similar to the step of compression of block  70 , but not shown in  FIG. 2 . 
     The issues considered previously form the subject of extensive technical literature as testified, for example, by: 
     CCITT-Recommendation T.81: “information technology—Digital compression and coding of continuous tone still images”—Requirements and guidelines (1992); 
     “Sensors, cameras and applications for digital photography”—Proceedings of SPIE (Vol. 3650, January 1999); 
     Blaskaran, Konstantinides, “Image and video compression standards”—(pp. 86-93); 
     Nakagawa et al., “DCT-based still image compression ICS with Bit-Rate Control”—IEEE Trans. on Consumer Electronics, Vol. 38, No. 3, August 1992; 
     Wook Joong Lim et al., “A bit allocation method based on picture activity for still image coding”—IEEE Trans. on Image Proc., Vol. 8, No. 7, July 1999; 
     A. Bruna, M. Mancuso, “JPEG compression factor control: a new algorithm”, Consumer Electronics, 2001. ICCE. International Conference on Consumer Electronics, 19-21 Jun.  2001 , Page(s): 206-207; and 
     Nakagawa et al.: DCT-based still image compression ICS with bit-rate control (IEEE 1992). 
     In applications where the desired value of bits per pixel is fixed at the moment of design or in any case pre-set, such as, for example, in digital still cameras in which usually a selector enables the quality of the image to be selected from among different levels of quality, with known systems it is, however, difficult to perform the compression with a single compression procedure performed just once, maintaining a good precision. The fact of having to re-apply the compression procedure a number of times entails a longer time for operation and higher power consumption. 
     SUMMARY OF THE INVENTION 
     The purpose of the present invention is to overcome drawback such as the one described above and to propose a solution that will enable a compression to be performed just once maintaining an acceptable level of precision. 
     According to the present invention, the above purpose is achieved by a method having the characteristics recalled in the ensuing claims, which form an integral part of the technical teaching regarding to the invention. 
     A method for the compression of image data according to the present invention includes applying a discrete cosine transform to said image data to obtain transform coefficients, quantizing said transform coefficients by applying a quantization level scaled through a gain value, adjusting said gain value as a function of desired image parameters, executing a first time said quantization operation by applying a first gain value and obtaining first quantized data, estimating statistically a second gain value suitable for obtaining said desired image parameters, executing a second time said quantization operation by applying said second gain value, and said operation of statistically estimating a second gain value comprises evaluating a threshold value as a function of said desired image parameters and setting to zero a percentage of coefficients of said first quantized data as a function of said threshold value. 
     The present invention also regards a corresponding compression apparatus, as well as a computer-program product that can be loaded into the memory of at least one computer and comprises portions of software code for implementing the aforesaid method. As used herein, reference to such a computer-program product is understood as being equivalent to reference to a computer-readable medium containing instructions for controlling a computer system in order to co-ordinate execution of the method according to the invention. Reference to “at least one computer” is intended to highlight the possibility for the present invention to be implemented in a distributed and/or modular way. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
       The invention will now be described, by way of non-limiting example, with reference to the figures of the annexed plate of drawings, in which: 
         FIG. 1  shows a block diagram of a JPEG compression chain according to the prior art; 
         FIG. 2  is a schematic illustration of the main processing steps executed in the step of rate control with a statistical procedure according to the prior art; 
         FIG. 3  shows a graph used by the image-compression method according to an embodiment of the invention; 
         FIG. 4  shows a histogram used by the image-compression method according to an embodiment of the invention; 
         FIG. 5  shows a block diagram representing a coding apparatus implementing the image-compression method according to an embodiment of the invention; 
         FIG. 6  is a schematic illustration of a detail of the coding apparatus of  FIG. 5 ; and 
         FIG. 7  and  FIG. 8  show error diagrams corresponding to tests of the method according to the invention. 
     
    
    
     DETAILED DESCRIPTION OF PREFERRED EMBODIMENTS 
     In brief, a block-compression method and a corresponding compression apparatus are proposed, which envisage execution of a JPEG compression with a pre-set or desired bitrate. The bitrate is obtained using a procedure of a statistical type and is based upon observation by the Applicant of a statistical fact: the value of bits per pixel bpp can be set, in fact, in relation to the number of zeros in the quantized coefficients obtained from the discrete cosine transform via a relation of a linear type. 
       FIG. 3  shows a graph that gives, as a function of a zero percentage ZP on the abscissa, the corresponding value of bits per pixel bpp on the ordinate. A dashed line RL represents a linear regression calculated on the values of bits per pixel bpp that can be assumed. According to the compression method proposed, it is envisaged to execute a retrieval step of a statistical type that enables identification of a mean interpolation point PMI given by the mean of the values of zero percentage ZP obtained at a constant value of bits per pixel bpp. Said mean interpolation point PMI depends upon a desired value of bits per pixel T and upon a size of the image S. For this reason, for each desired image size S and value of bits per pixel T, the zero percentage ZP that must contain the quantized coefficients is known. 
     Consequently, the method proposed substantially regulates the number of zeros of the quantized coefficients in order to satisfy the aforementioned constraint. 
     The method according to the invention hence envisages execution of the following steps. 
     Execution of a first mild quantization operation on DCT coefficients with a first gain value G 0  in order to obtain a granular histogram H, hence with a value sufficiently low to ensure the highest possible number of coefficients quantized with different values. 
     Construction of said histogram H collecting all the quantized coefficients of the image data; an example of said histogram H is shown in  FIG. 4 , where given on abscissa is an index “i” of the coefficients and on the ordinate a number NC of coefficients for each given index “i”. 
     Fixing of a zero-percentage point XP on the abscissa of the histogram H; all the coefficients falling under said zero-percentage point XP must be zeros. 
     Calculation of a new gain value G T  starting from the zero-percentage point XP. 
     Quantization of the DCT coefficients with the new gain value so as to obtain the desired value of bits per pixel T. 
       FIG. 5  shows a block diagram of a coding apparatus that implements the method according to the invention. In  FIG. 5 , the blocks having functions similar to those of the blocks of  FIG. 1  are designated by the same reference numbers. 
     In said apparatus, the image data I, already converted into the YCbCr form of representation deriving from the original RGB format, are then sent on to the DCT block  10 , which produces at output the transform coefficients I DCT . Said transform coefficients I DCT  are stored in a dynamic-memory element  90 , in particular a DRAM (Dynamic Random Access Memory) and are then supplied to the quantization block  20 . Said quantization block  20  receives and uses the scaled quantization level {tilde over (Q)}, which is calculated as the product of the gain factor G and a quantization level Q, produced by the quantization table  60  according to Equation 1 given above. Said quantization block  20  hence produces at output quantized data QD, which contain the quantized DCT coefficients. 
     According to one aspect of the invention, a rate-control block  100  is provided, which supplies to a multiplier  95  the gain value G to be multiplied by the value of quantization level Q in order to implement Equation 1 and to supply the scaled quantization level {tilde over (Q)} to the quantization block  20 . The rate-control block  100  receives at one input thereof a desired value of bits per pixel T and a desired value of size of the image S. 
     According to the invention, the coding apparatus illustrated in  FIG. 5  presents at least two distinct operating steps. 
     In a first operating step, the transformed signal I DCT  is written into the dynamic memory  90 , and then applied thereon in the quantization module  20  is a mild quantization, with an initial gain value G 0  described previously, to produce mildly quantized data QD 0 . Said mildly quantized data QD 0 , i.e., DCT quantized coefficients, are sent to a rate-control block  100  so as to populate the histogram H, already described with reference to  FIG. 4 , and evaluate the population of the histogram. As will be described in greater detail hereinafter, with reference to  FIG. 6 , a final gain value G T  is then calculated, which is used to quantize again, in the quantization block  20 , the transformed signal I DCT  stored in the dynamic memory  9  and produce at output final quantized data QD 1 , which are then supplied at input to the zigzag-ordering block  30  and to the subsequent Huffman-coding block  49  to generate the JPEG compressed image O. 
     It should be noted that, notwithstanding the two distinct operating steps, the method is configured as a one-pass method, i.e., a method executed just once, in so far as the main blocks involved in the JPEG compression are used just once. Only the quantization operation is performed twice. 
       FIG. 6  shows a detail of the rate-control block  100 . 
     In said rate-control block  100 , the mildly quantized data QD 0  are sent on to a module for population of the histogram  110 , which populates the histogram H of  FIG. 4 . 
     The desired value of bits per pixel T and the value of size of the image S are instead supplied as input data for a search in a pre-loaded look-up table  140 , which supplies at output a threshold value R 0 , which indicates heuristically the correct zero percentage ZP. Said threshold value R 0  is supplied, together with values of population D of the histogram, generated by the module for the population of the histogram  110 , to a block for determining the index  120 , which derives the index “i” of the coefficient. Said index “i” is supplied to a gain-calculation block  130 , which supplies at output the final gain value G T . Said final gain value G T  is sent on to one of the inputs of a multiplexer  15 , which receives at another input thereof the initial gain value G 0 , supplied by the pre-loaded look-up table  140 . 
     In the first operating step, the multiplexer  160  selects as gain G said initial gain value G 0 , which is chosen heuristically so as to enable a mild quantization to be carried out at block  20  that will ensure a histogram H with a fine granularity. Preferably, with 1024 coefficients in the quantized data QD, G 0  is set equal to 1/1024, in so far as the hardware implementation is simpler. 
     In the second operating step, the multiplexer  150  selects, instead, as gain G the final gain value G T . 
     The block for determining the index  120  at the end of the first operating step calculates the value of the index “i” according to the following relation: 
     
       
         
           
             
               
                 
                   
                     i 
                     ⁢ 
                     
                       : 
                     
                     ⁢ 
                     
                       
                         ∑ 
                         
                           j 
                           = 
                           0 
                         
                         i 
                       
                       ⁢ 
                       
                         D 
                         ⁡ 
                         
                           ( 
                           j 
                           ) 
                         
                       
                     
                   
                   ≤ 
                   
                     R 
                     o 
                   
                 
               
               
                 
                   ( 
                   3 
                   ) 
                 
               
             
           
         
       
     
     The gain-calculation block  130  implements, instead, the following relation: 
     
       
         
           
             
               
                 
                   G 
                   ⁢ 
                   
                      
                     
                       
                         round 
                         ⁡ 
                         
                           [ 
                           
                             i 
                             G 
                           
                           ] 
                         
                       
                       = 
                       
                         
                           0 
                           ⇒ 
                           
                             
                               i 
                               G 
                             
                             &lt; 
                             
                               0.5 
                               ⁢ 
                               
                                 
 
                               
                               ⁢ 
                               
                                 G 
                                 T 
                               
                             
                           
                         
                         = 
                         
                           
                             G 
                             · 
                             
                               G 
                               0 
                             
                           
                           = 
                           
                             
                               i 
                               0.49 
                             
                             · 
                             
                               G 
                               0 
                             
                           
                         
                       
                     
                   
                 
               
               
                 
                   ( 
                   4 
                   ) 
                 
               
             
           
         
       
     
     As may be inferred from Equations 4, the value 0.49 is a factor chosen from among all the ones that satisfy the condition of inequality (i/G&lt;0.5). 
     A better precision can be obtained using the following relation: 
     
       
         
           
             
               
                 
                   
                     
                       G 
                       T 
                     
                     = 
                     
                       
                         
                           i 
                           + 
                           ratio 
                         
                         0.49 
                       
                       · 
                       
                         G 
                         0 
                       
                     
                   
                   , 
                   
                     
 
                   
                   ⁢ 
                   
                     ratio 
                     = 
                     
                       
                         
                           R 
                           0 
                         
                         - 
                         
                           
                             ∑ 
                             
                               j 
                               = 
                               0 
                             
                             i 
                           
                           ⁢ 
                           
                             H 
                             ⁡ 
                             
                               ( 
                               j 
                               ) 
                             
                           
                         
                       
                       
                         H 
                         ⁡ 
                         
                           ( 
                           
                             j 
                             + 
                             1 
                           
                           ) 
                         
                       
                     
                   
                 
               
               
                 
                   ( 
                   5 
                   ) 
                 
               
             
           
         
       
     
     where with H(j) are the values of the histogram H defined previously. 
     The pre-loaded look-up table  140  contains data obtained heuristically. The parameters depend upon the size of the image S and upon the desired value of bits per pixel T. 
     The pre-loaded look-up table  140  contains the initial gain value G 0  and the threshold value R 0 . The initial gain value G 0  is the first multiplier of the quantizer Q that is used in the first step. The threshold value R 0  contains the zero percentage ZP used in the block for determining the index  120 . 
     Table 1 shows an example, corresponding to VGA and CIF images with 3.2 bpp, 1.6 bpp, 0.8 bpp of desired value of bits per pixel T, of values assumed by the initial gain value G 0  and by the threshold value R 0 . 
     
       
         
               
               
               
             
               
               
               
               
               
             
           
               
                   
                 TABLE 1 
               
             
             
               
                   
                   
               
               
                   
                 T 
                   
               
             
          
           
               
                   
                 S 
                 3.2 
                 1.6 
                 0.8 
               
               
                   
                   
               
               
                   
                 VGA 
                 R 0  = 446000 
                 R 0  = 530000 
                 R 0  = 575000 
               
               
                   
                 (640 × 480) 
                 1/G 0  = 1024 
                 1/G 0  = 1024 
                 1/G 0  = 1024 
               
               
                   
                 CIF 
                 R 0  = 149000 
                 R 0  = 175555 
                 R 0  = 190035 
               
               
                   
                 (352 × 288) 
                 1/G 0  = 1024 
                 1/G 0  = 1024 
                 1/G 0  = 1024 
               
               
                   
                   
               
             
          
         
       
     
       FIGS. 7 and 8  show histograms of error distribution corresponding to tests performed on the coding apparatus described with reference to  FIGS. 5 and 6 . The desired value of bits per pixel T is 3.2 and the resolution is VGA for the histogram of  FIG. 7  and CIF for the histogram of  FIG. 8 . For the tests, a database was used with a number of images IN equal to 110, captured with a CMOS-VGA sensor in an “STV6500-E01” Evaluation Kit equipped with a sensor “502 VGA”, as described in Colour Sensor Evaluation Kit VV6501, STMicroelectronics, Edinburgh, www.edb.st.com, 2003. The histograms give the percentage image number NI % as a function of the percentage deviation DEV %. 
     Consequently, without prejudice to the principle of the invention, the details of implementation and the embodiments may vary, even significantly, with respect to what is described and illustrated herein, purely by way of non-limiting example, without thereby departing from the scope of the invention, as defined in the ensuing claims.