Patent Publication Number: US-6668089-B1

Title: Process for controlling the compression ratio of digital images

Description:
TECHNICAL FIELD 
     The present invention relates to a process for controlling the compression ratio of digital images. 
     BACKGROUND ART 
     The amount of digital images increases each year as new applications are found for them. However, an enormous amount of data is needed to represent a single digital image. Speaking generally, this amount of data is so large that storing and transmitting the images in their original representation is too costly and thus impractical, both from the point of view of the digital processing of the images and the economic point of view. 
     At present various image compression algorithms have been developed. A joint effort between the ITU (International Telecommunication Union) and the ISO (International Organisation for Standardization) has resulted in the creation of the compression standard for still images known under the name JPEG (Joint Photographic Expert Group). This algorithm is defined in “ITU-T Recommendation T.81, Digital Compression and Coding of Continuous-tone Still Images” (September 1992) and is fully illustrated in W. B. Pennebaker and J. L. Mitchell, “JPEG Still Image Compression Standard”, Van Nostrand Reinhold, New York, N.Y., USA, 1993. 
     When using the JPEG algorithm the compression ratio, i.e. the number of bits in the un-compressed image divided by the number of bits in the compressed image varies as a function of the complexity of the image. Thus, for example, the compression ratio of an image of a sky with few clouds is twice or three times, even more, the compression ratio of an image of a crowd in a stadium, for a substantially identical quality of restitution. 
     In many applications it is desirable or necessary for the user and/or the system to be able to control the compression ratio of the acquired images. In an apparatus for recording digital views, such as a photographic apparatus, it is important to be able to foresee the size of the compressed images, in order to keep the allocation of the memory of the apparatus under control. 
     Controlling the compression ratio is also important in networks which transmit still images or sequences of images. In these networks the time specified for transmitting a compressed image is fixed, or restricted at least, and cannot exceed a certain value, which rules out use of coding schemes which do not have control over the compression ratio. 
     The present invention seeks to provide an image compression process in which it is possible to choose the compression ratio with excellent precision. 
     SUMMARY OF THE INVENTION 
     In order to achieve this object, the process according to the invention is characterized in that it comprises the steps of: 
     compressing a digital image by means of conventional process having at least one parameter allowing the compression ratio to be modified, i.e. the ratio of the size of the un-compressed image to the size of the compressed image, 
     determining the compression ratio of the said conventional process, 
     verifying whether the compression ratio lies in a range of tolerance of a value of a specified compression ratio, 
     modifying said parameter if the compression ratio does not lie in the range of tolerance, and 
     repeating the compression of the image until the compression ratio lies in the range of tolerance. 
     According to a preferred embodiment, the conventional compression process is the JPEG process and the parameter which is acted upon is a scale factor serving to modify the values of the normalization matrix used by the algorithm of the JPEG process. 
     In the process according to the invention an initial scale factor is advantageously defined, the JPEG process is applied a first time using the initial scale factor and said process is applied again with the scale factor being modified if the actual compression ratio does not lie in the range of tolerance of the specified compression ratio. 
     According to an advantageous implementation of the process, the scale factor is increased when the actual compression ratio is lower than the specified compression ratio and is decreased when the actual compression ratio is greater than the specified compression ratio. 
     The scale factor is advantageously modified as a function of an at least partially linear model representing the compression ratio as a function of the scale factor. 
     Preferably the actual compression ratio is determined using said initial scale factor, the curve representing the compression ratio as a function of the scale factor is approximated by a straight line having predetermined slope m 0  and passing through a point having the initial scale factor as abscissa and the actual compression ratio obtained by applying the JPEG process with the initial scale factor as ordinate, a scale factor is determined on the basis of the straight line approximation and of the specified compression ratio, the JPEG process is applied again using this new scale factor, it is verified whether the actual compression ratio lies in the range of tolerance of the specified compression ratio, the process is terminated if the actual compression ratio lies within this range, otherwise a new scale factor is determined on the basis of a straight line approximation to the curve of the actual compression ratio as a function of the scale factor. 
     According to a variant embodiment, the curve representing the actual compression ratio as a function of the scale factor is advantageously approximated by straight line segments having different slopes and forming a continuous curve. 
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS 
     The present invention will be better understood with reference to two non-limiting embodiments of the invention and to the accompanying drawings, in which: 
     FIG. 1 is a block diagram illustrating a first embodiment of the process according to the invention; 
     FIGS. 2 a  to  2   d  represent the compression ratio schematically at different steps of the process of FIG. 1; 
     FIG. 3 is a block diagram of a second embodiment of the process according to the invention and 
     FIGS. 4 a  to  4   d  represent the compression ratio at different steps of the process of FIG.  3 . 
    
    
     PREFERRED EMBODIMENTS 
     The process according to the present invention is based on the JPEG algorithm and is entirely compatible therewith. The principle steps of this algorithm are defined below. 
     The image to be compressed is separated into blocks of 8×8 pixels. Each block is then processed separately in the identical way, in sequential manner. The steps of the process are described hereafter for one block of 8×8 pixels. 
     Each block is associated with a matrix of eight rows and eight columns, called the “matrix of a block” in the following. 
     This matrix is multiplied by the core of a linear transform known under the abbreviation 2D-DCT (2 dimension—Discrete Cosine Transform), such as is defined in the JPEG algorithm. This discrete cosine transform (DCT) converts the 8×8 pixels of the spatial domain into 8×8 coefficients in the frequency domain. The object of this transformation is to de-correlate the original data and redistribute the energy of the signal between a small number of coefficients, in the part of the low frequencies of the spectrum of the transformed data. 
     This transformation produces a resultant matrix containing relatively large values in a zone located towards the upper left part of the matrix and relatively small values elsewhere. The size of the zone containing the large values depends on the complexity of the image. 
     A normalization matrix is defined, based on a psycho-visual analysis. This matrix is used to quantize the DCT coefficients which are significant from the visual point of view with a small quantization step, while a larger quantization step is used for the rest of the coefficients. 
     The quantization of the DCT coefficients is the principle mechanism of compression, but also of loss of information. The system increases the level of compression by effecting entropy coding of the output of the quantizer. 
     The normalization matrix can be scaled by means of a factor called the scale factor, which can take any real value whatsoever greater than zero. By modifying the value of this factor it is possible to modify the compression ratio given by the JPEG method. The larger the value of the scale factor, the greater becomes the compression ratio and vice versa. 
     The present invention defines an efficient way of finding this scale factor while making the minimum number of iterations, with a method which does not degrade the quality of the compressed image in any way. 
     The proposed process is based on the demonstration by the inventors that the relationship between the scale factor and the compression ratio obtained with the JPEG compression is of quasi-linear nature. 
     A first embodiment of the process is described below with reference to FIGS. 1 and 2. 
     As already mentioned, the invention relies on the discovery that it is possible to define a relation between the scale factor and the compression ratio of the image. This relationship can be represented graphically by putting the scale factor SF on the axis of the abscissae and the compression ratio CR on the axis of the ordinates. 
     This first embodiment of the process is based on a strictly linear model of the compression ratio as a function of the scale factor. 
     In a first step  10  of the process, the compression ratio finally to be attained is fixed. This ratio is called the specified compression ratio and is abbreviated to CR T . It is represented by a straight line referenced  110  in FIGS. 2 a  to  2   d.  This ratio can be fixed either for good in the control system of the compression ratio, or by the user, in particular as function of the desired image quality, the number of images to be stored in a given memory or the capacity of a transmission channel. 
     In this same step  10  of the process, an initial scale factor SF 1  is defined. This initial scale factor is generally defined once and for all. According to the described embodiment of the process, the initial scale factor is fixed at 1. 
     The JPEG algorithm is used in a second step  11  to compress an input image, the actual compression ratio CR 1  being calculated in this same step. 
     In step  12  of the process, the relative error between the actually obtained compression ratio CR 1  and the specified compression ratio CR T  is determined. If this relative error is lower than a predetermined threshold value, ±5% for example, the process is terminated and the image is stored or transmitted. This corresponds to the step  30  in FIG.  1 . The difference between the specified compression ratio and the actual compression ratio is denoted ΔCR in FIG. 2 d.    
     In the converse case, step  13  consists in defining a straight line representing the compression ratio as a function of the scale factor, this straight line modelling the actual curve of the compression ratio as a function of the scale factor. The straight line passes through a point P 1  having SF 1 =1 as abscissa and CR 1  as ordinate. Its slope m 0  is defined in the control system for the compression ratio. This slope is determined as the mean slope of a set of test images. 
     The straight line can be written in the following manner: 
     
       
         
           CR=m 
           0 
           ·SF+b 
           0 
         
       
     
     where CR is the compression ratio, SF the scale factor and b 0  is the ordinate at the origin. This straight line has the reference  111  in FIGS. 2 b,    2   c  and  2   d.    
     The value of b 0  is given by: 
     
       
         
           b 
           0 
           =CR 
           1 
           −m 
           0 
           ·SF 
           1 
         
       
     
     The value of the scale factor corresponding to the compression ratio to be obtained is then determined in step  14  of the process, using the straight line defined above. 
     At the specified compression ratio we have: 
     
       
         
           CR 
           T 
           =m 
           0 
           ·SF 
           2 
           +b 
           0 
         
       
     
     from which 
     
       
           SF   2 =( CR   T   −b   0 )/ m   0   
       
     
     This allows a new scale factor to be calculated as a function of the specified compression ratio and the actual compression ratio obtained in the first approximation. 
     At this stage of the process, the JPEG algorithm is used again with the scale factor SF 2 . This corresponds to step  15  of FIG.  1 . The actual compression ratio CR 2  is determined in this same step. This corresponds to FIG. 2 c.  A point P 2  having the coordinates SF 2  and CR 2  is illustrated in FIG. 2 c.    
     In step  16 , the value CR 2  obtained is compared with the value of the compression ratio CR T . If their difference is less than 5% the process is terminated. 
     In the converse case, a model straight line passing through the point P 1  with SF 1 =1 as abscissa and CR 1  as ordinate and through the point P 2  having SF 2  for abscissa and CR 2  for ordinate is used. This is effected in step  17 . This straight line has the reference  112  in FIG. 2 d.  It has a slope m 1  given by: 
     
       
           m   1 =( CR   2   −CR   1 )/( SF   2   −SF   1 ) 
       
     
     As above, a new model is defined: 
     
       
         
           CR=m 
           1 
           ·SF+b 
           1 
         
       
     
     in which: 
     
       
           b   1   =CR   1 −( m   1   ·SF   1 )= CR   2 −( m   1   ·SF   2 ) 
       
     
     At the specified point of the compression ratio CR T , we have: 
     
       
         
           CR 
           T 
           =m 
           1 
           ·SF 
           3 
           +b 
           1 
         
       
     
     from which 
       SF   3 =( CR   T   −b   1 )/ m   1   
     The determination of this value SF 3  is effected in step  18  of the process. The JPEG algorithm is used once again to obtain the actual compression ratio CR 3 . This corresponds to step  19  in FIG.  1 . 
     This actual compression ratio CR 3  is compared in step  20  with the specified compression ratio CR T  and the process is terminated if these two levels have a difference less than a predetermined value. 
     In the converse case, the process is carried out using as a straight line approximation the straight line passing through the two last points having the calculated pairs of coordinates SF and CR. 
     The process is followed until the value of the actual compression ratio is within the acceptable limits for the specified compression ratio. This condition is generally realised after one to three iterations when the relative difference between the actual compression ratio and the specified compression ratio should be less than or equal to 5%. FIG. 2 d  further illustrates the actual curve of the compression ratio as a function of the scale factor. This curve has the reference  113 . 
     FIGS. 3 and 4 illustrate a second embodiment of the process according to the present invention, in which the number of iterations can be reduced. This objective is attained by starting the process as described above using an initial scale factor SF 1 =2 and using a better approximation to the curve representing the compression ratio as a function of the scale factor. 
     In the embodiment illustrated by FIGS. 1 and 2, the compression ratio as a function of the scale factor is approximated by a straight line while in the embodiment illustrated by FIGS. 3 and 4 the compression ratio is approximated by straight line segments forming a continuous curve, the slope of each segment being different in the various zones of the scale factor as a function of the actual compression ratio obtained after an iteration using SF 1  as the scale factor. 
     The specified compression ratio CR T  is introduced in a step  40 . 
     In step  41  the actual compression ratio CR 1  is determined by applying the JPEG process with a given scale factor SF 1 , equal to 2 for example. 
     In step  42  the value of CR 1  is compared with the specified value CR T . If the relative error of these two values is lower than a predetermined threshold value, 5% for example, the process is terminated and the image is stored or transmitted. This corresponds to step  50 . In the converse case, the process continues with the step described below. 
     The approximation to the curve of the compression ratio as a function of the scale factor allows zones with different slopes to be defined. Each zone is formed by a segment having a given slope. The value of the slope for each zone is selected as a function of the value of CR 1 , in accordance with the equations m=f(CR 1 ) of the table below, in which six zones forming six straight line segments are defined by way of example of a concrete implementation. 
     
       
         
           
               
               
               
             
               
                   
               
               
                 Zone No. 
                 Scale factor 
                 Slope 
               
               
                   
               
             
            
               
                 1 
                 sfSF &lt; 1.0 
                 m 1  = 0.4939 CR 1  − 0.7964 
               
               
                 2 
                 1.0 ≦ sfSF &lt; 1.5 
                 m 2  = 0.3947 CR 1  − 0.3122 
               
               
                 3 
                 1.5 ≦ sfSF &lt; 2.0 
                 m 3  = 0.2894 CR 1  + 0.6244 
               
               
                 4 
                 2.0 ≦ sfSF ≦ 5.0 
                 m 4  = 0.1565 CR 1  + 1.6517 
               
               
                 5 
                 5.0 &lt; sfSF ≦ 10.0 
                 m 5  = 0 CR 1  + 3.0175 
               
               
                 6 
                 sfSF &gt; 10 
                 m 6  = −0.1098 CR 1  +3.8832 
               
               
                   
               
            
           
         
       
     
     The straight line which is the best adapted, i.e. that which best approximates the actual curve of the compression ratio as a function of the scale factor, is chosen as a function of the actual value of CR 1 . This is effected in step  43  of the process illustrated in FIG.  3 . 
     In step  44  the scale factor SF 2  which should correspond to the specified compression ratio CR T  is then estimated, using the model of the segment given by the appropriate slope m and by the point (CR 1 , SF 1 ). The JPEG process is applied again using SF 2 , which gives the compression ratio CR 2  as result. 
     According to step  45 , if the relative error between the calculated ratio CR 2  and the specified compression ratio CR T  is lower than a predetermined threshold level, for example ±5%, the process is terminated. In the converse case, a supplementary iteration of the process is effected. 
     The number of iterations depends on the desired precision. The process is terminated when the specified compression ratio is attained, within a limit dependent on this desired precision. 
     One particular embodiment is described with reference to FIGS. 4 a  to  4   d.  In this embodiment it is assumed that the scale factor being sought lies between 5 and 10. 
     The steps of the process are described below. 
     The specified compression ratio, abbreviated CR T  as illustrated in FIG. 4 a  is given. This Figure also comprises a curve  200  representing the compression ratio as a function of the scale factor. 
     The input image is compressed using a scale factor equal to 2. The resultant compression ratio is called CR 1  (see FIG. 4 a ). 
     If the absolute value of the relative error between CR T  and CR 1  is smaller that a predetermined threshold value, for example 5%, the process is terminated. In the converse case, it proceeds. 
     The slope of the straight line approximating the compression ratio as a function of the scale factor is then determined using the above table. In the above example, the desired scale factor corresponds to the zone No. 5 in which 5&lt;SF&lt;10. However, starting from the point (2, CR 1 ) the zone No. 4 of the table is used at first. With the value of m 4  and the point (SF 1 =2, CR 1 ), the ordinate at the origin b 4  is implicitly defined, as with a linear model CR−m 4 ·SF+b 4  with the reference  201 . This linear model is then used to find the scale factor which corresponds to a compression ratio CR=CR T . This scale factor is called SF 2  (see FIG. 4 a ). 
     In the illustrated case, SF 2 &gt;5. The linear model  201  is then used, CR=m 4 ·SF+b 4  to find the compression ratio CR which corresponds to a scale factor SF=5. This step determines the point (5, CR v )—(see FIG. 4 b ). 
     The value of CR 1  is then inserted in the zone No. 5 of the table above to find the slope m 5  of the linear model for the region 5&lt;SF&lt;10. This model has the reference  202  in FIG. 4 b.  Given the value of m 5  and the point (5, CR v ), the value of b 5  is implicitly defined, as in the linear model CR=m 5 ·SF+b 5 . 
     This model is then used to find the scale factor which corresponds to a compression ratio CR=CR T . This scale factor is called SF 2 . The preceding value of SF 2  becomes SF 2 ′. 
     The input image is then compressed using the normalization matrix scaled by the value SF 2 . CR 2  is called the resultant compression ratio (see FIG. 4 c ). 
     If the absolute value of the relative error between CR T  and CR 2  is smaller than a predetermined threshold value, for example 5%, the process is terminated. Otherwise it is continued. 
     In order to approximate more precisely to the value of CR T , an adjustment of the ordinate at the origin b 5  is then necessary. The slope m 5  and the point (SF 2 , CR 2 ) implicitly define a more accurate model CR=m 5 ·SF+b 5 ′ of the characteristic of the compression ratio as a function of the scale factor of the input image. The scale factor which corresponds to a compression ratio CR=CR T  is determined with this new model. This scale factor is called SF 3 . 
     Finally, using SF 3  as the scale factor for the normalization matrix, the input image is compressed. CR 3  is called the resultant compression ratio (see FIG. 4 d ). If the relative error between CR 3  and CR T  is lower than a predetermined threshold value, the process is terminated. In the converse case, the process is continues in a similar fashion to what has been described above. 
     Although the basic principle used in this variant is equivalent to the principle of the process explained above, the specified value CR T  of the compression ratio is attained more rapidly than in the preceding embodiment. 
     The process according to the invention allows the compression ratio to be chosen and thus to select the memory space necessary for storing an image, or the transmission time required. 
     This choice of the compression ratio can be effected by the user or be predefined during the design of the coding system for several values of the compression ratio, in such a way that it cannot be modified. 
     The present invention is not limited to the described embodiments but extends to all variants obvious to the man skilled in the art. In particular, the initial scale factor can be modified in such a way as to arrive at the desired result as rapidly as possible. Equally, the modelling of the curve of the compression ratio as a function of the scale factor can be refined. Moreover, the tolerance for the value of the compression ratio can be chosen as a function of the required precision. 
     More particularly, the description of the invention which has been given refers to the case in which the specified compression ratio can be chosen within a range of values corresponding to the largest number of possible applications of the system. However, if the specified compression ratio is restricted to some previously defined and constant values, the relationships of the scale factor to the compression ratio can be optimised, while remaining within the scope of the invention, so as to reduce to 2 the number of iterations which the system requires to converge on the specified compression ratio.