Abstract:
A method and apparatus for controlling the rate of compression in video/image compression environments is provided. The method includes determining a scaling factor that results in a compressed file size as close to a target file size as possible. In determining the scaling factor, tolerance limits of the current file size as compared with a predetermined tolerance is made, and when the tolerance is not met, the current scaling factor is interpolated to generate a new scaling factor, and consideration of a ratio of file sizes is made to determine if a new down-sampling factor is needed for the interpolated scaling factor.

Description:
CROSS REFERENCE TO RELATED APPLICATIONS 
       [0001]    This application claims the benefit of U.S. Provisional Application Ser. No. 61/203,799 filed Dec. 29, 2008, which is incorporated by reference herein in its entirety. 
     
    
     TECHNICAL FIELD 
       [0002]    The present principles relate to video compression. More particularly, it relates to methods for achieving a target file size for compressed video. 
       BACKGROUND 
       [0003]    One of the ways of achieving a target file size for compressed video is to use a scaled version of a fixed quantization table for compressing frames in the sequence. The quantization table is usually designed by taking the properties of the human visual system into account. But, the compressed file size can not be accurately predicted from the quantization table and the scaling factor. In some applications, it is necessary to achieve a compressed file size that is within a specified tolerance of the target file size. We propose a method and apparatus for finding a scaling factor to achieve the target file size within a specified tolerance in a computationally efficient manner. 
         [0004]    In many applications, there is a requirement that the overall file size of the compressed video is within a specified tolerance interval of a target file size. 
       SUMMARY 
       [0005]    According to an implementation, the method for rate control for compression of video frames includes specifying a target compressed file size and file size tolerance, compressing a subset of a total number of video frames to obtain an estimate of compressed file size for all frames in a sequence, determining if an overall compressed files size is within a tolerance limit, iteratively performing a scaling factor determination when the overall compressed file size is not within the tolerance limit, and selecting a scaling factor that results in a compressed file size as close to a target file size as possible. 
         [0006]    The compressing of a subset of a total number of video frames to obtain an estimate of compressed file size for all frames in a sequence may further include initially electing a quantization table, a current scaling factor and a current downsampling factor for use in during the compressing. 
         [0007]    The interative scaling factor determination may further include updating a current scaling factor using interpolation, and setting a new downsampling factor based on a predetermined ratio of file sizes when the ratio leads to a lower downsampling factor. 
         [0008]    In accordance with another implementation, the apparatus for rate control for compression of video frames includes a system having a processor and one or more memory devices. The processor and at least one memory device is configured to perform the steps for rate control for compression of video frame as described above. 
         [0009]    These and other aspects, features and advantages of the present principles will become apparent from the following detailed description of exemplary embodiments, which is to be read in connection with the accompanying drawings. 
     
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         [0010]    The present principles may be better understood in accordance with the following exemplary figures, in which: 
           [0011]      FIG. 1  is flow chart of the method for determining a scaling factor according to an implementation of the present invention; 
           [0012]      FIG. 2  is a flow chart of the scaling factor iteration according to an implementation of the present invention; 
           [0013]      FIG. 3  is a flow chart of the finding a lower bound in the scaling factor determination according to an implementation of the present invention; 
           [0014]      FIG. 4  is a flow chart of the finding of an upper bound in the scaling factor determination according to an implementation of the present invention; and 
           [0015]      FIG. 5  is a block diagram of an exemplary system within which the present invention can be implemented 
       
    
    
     DETAILED DESCRIPTION 
       [0016]    The present principles are directed to video/image compression techniques. 
         [0017]    The present description illustrates the present principles. It will thus be appreciated that those skilled in the art will be able to devise various arrangements that, although not explicitly described or shown herein, embody the present principles and are included within its spirit and scope. 
         [0018]    All examples and conditional language recited herein are intended for pedagogical purposes to aid the reader in understanding the present principles and the concepts contributed by the inventor(s) to furthering the art, and are to be construed as being without limitation to such specifically recited examples and conditions. 
         [0019]    Moreover, all statements herein reciting principles, aspects, and embodiments of the present principles, as well as specific examples thereof, are intended to encompass both structural and functional equivalents thereof. Additionally, it is intended that such equivalents include both currently known equivalents as well as equivalents developed in the future, i.e., any elements developed that perform the same function, regardless of structure. 
         [0020]    Thus, for example, it will be appreciated by those skilled in the art that the block diagrams presented herein represent conceptual views of illustrative circuitry embodying the present principles. Similarly, it will be appreciated that any flow charts, flow diagrams, state transition diagrams, pseudocode, and the like represent various processes which may be substantially represented in computer readable media and so executed by a computer or processor, whether or not such computer or processor is explicitly shown. 
         [0021]    The functions of the various elements shown in the figures may be provided through the use of dedicated hardware as well as hardware capable of executing software in association with appropriate software. When provided by a processor, the functions may be provided by a single dedicated processor, by a single shared processor, or by a plurality of individual processors, some of which may be shared. Moreover, explicit use of the term “processor” or “controller” should not be construed to refer exclusively to hardware capable of executing software, and may implicitly include, without limitation, digital signal processor (“DSP”) hardware, read-only memory (“ROM”) for storing software, random access memory (“RAM”), and non-volatile storage. 
         [0022]    Other hardware, conventional and/or custom, may also be included. Similarly, any switches shown in the figures are conceptual only. Their function may be carried out through the operation of program logic, through dedicated logic, through the interaction of program control and dedicated logic, or even manually, the particular technique being selectable by the implementer as more specifically understood from the context. 
         [0023]    In the claims hereof, any element expressed as a means for performing a specified function is intended to encompass any way of performing that function including, for example, a) a combination of circuit elements that performs that function or b) software in any form, including, therefore, firmware, microcode or the like, combined with appropriate circuitry for executing that software to perform the function. The present principles as defined by such claims reside in the fact that the functionalities provided by the various recited means are combined and brought together in the manner which the claims call for. It is thus regarded that any means that can provide those functionalities are equivalent to those shown herein. 
         [0024]    Reference in the specification to “one embodiment” or “an embodiment” of the present principles, as well as other variations thereof, means that a particular feature, structure, characteristic, and so forth described in connection with the embodiment is included in at least one embodiment of the present principles. Thus, the appearances of the phrase “in one embodiment” or “in an embodiment”, as well any other variations, appearing in various places throughout the specification are not necessarily all referring to the same embodiment. 
         [0025]    In many applications, there is a requirement that the overall file size of the compressed video is within a specified tolerance interval of a target file size. In the JPEG2000 standard (Information Technology—JPEG2000 Image Coding System, ISO/IEC International Standard 15444-1, ITU Recommendation T.800) many different approaches are possible for achieving this goal. Some representative examples of these approaches are:
       1. Use a constant number of bits to compress each frame so that the target file size is almost exactly achieved;   2. Use external bit allocation based on human visual system, feature maps, complexity, etc., to allocate bits to different frames and to different areas within a frame so that the target file size is achieved with a specified tolerance;   3. Choose a quantization table to be used for compressing each frame; and then determine a scaling factor for the quantization table, such that the target file size is achieved within a specified tolerance. In the JPEG2000 context, the quantization table refers to the individual quantizer step-sizes used to quantize each subband; and   4. Determine a rate-distortion slope parameter for discarding coding passes such that the target file size is achieved with a specified tolerance.       
 
         [0030]    The exact method chosen depends on the specific application and requirements. The quantization table in approach 3 can be chosen based on the properties of the human visual system (HVS). Experience suggests that approach 3 results in roughly similar visual quality for different frames in the video sequence, and hence, is used in one exemplary embodiment. When approach 3 is used, it is desirable to determine a scaling factor such that the overall compressed file size is equal to the target file size within a specified tolerance. Each quantization table entry is multiplied by the scaling factor to derive the actual quantization table. Determining the exact scaling factor needed analytically is difficult, as there is no direct relationship between the scaling factor and the compressed file size. The present invention proposes a computationally efficient method to determine this scaling factor. 
         [0031]    Throughout the following description of the exemplary implementation of the invention, it is assumed that each frame is compressed independently using JPEG2000 or any other compression algorithm. Thus, the overall compressed file size refers to the sum of the compressed file sizes for individual frames. Those skilled in the art will recognize that it may be possible to concatenate individual compressed frames into a single compressed file for the entire video. This is especially true at the final iteration and at any other instance when each frame from the video sequence is being compressed. 
         [0032]      FIG. 1  shows a flowchart  10  for determining the scaling factor according to an implementation of the present invention. The total number of video frames=L. The target compressed file size=FS t  and the file size tolerance=±δ%. The values of FS t  and δ are user-specified. In the initialization step  12 , a quantization table (Q), current scaling factor (SC c ), and a current downsampling factor (ds c ) is chosen. The quantization table Q is typically chosen based on a contrast sensitivity model of the human visual system (HVS), but it can also be user-specified. The “quantization (compression) step  14  compresses up to L video frames using the quantization table Q, scaled by the scaling factor SC c . The overall compressed file size after this step ( 14 )=FS c . At step  16 , it is determined if FS c  is within the tolerance limit, that is, if |FS t −FS c |≦δ. If yes, an “end condition” step  18  is executed. In this step  18 , every video frame that was not compressed in the previous compression step is compressed using the quantization table Q, scaled by the current scaling factor SC c  and the process is stopped. The resulting final overall compressed file size is FS f . If at step  16 , FS c  is not within the tolerance limit, a subsequent determination is made at step  20 , as to whether FS t +δ&lt;FS c ? If yes, FS h  is set to FS c  and SC l  is set to SC c . Then, values of FS l  and SC h  are found in the “find lower bound” step  24 . FS h , FS l , SC l , and SC h  represent “file size high”, “file size lower”, “scaling factor lower”, and “scaling factor high.” It is important to recognize that lower values of SC correspond to less aggressive quantization and hence higher compressed file sizes. Otherwise, if (FS t −δ)&gt;FS c  (i.e., no at step  20 ), FS l  is set FS c  and SC h  is set to SC c  (at step  26 ). Then, values of FS h  and SC l  are found in “find upper bound” step  28 . The values, FS l , FS h , SC l  and SC h  are input to a “scaling factor iteration” step  30 . 
         [0033]    The details of the “scaling factor iteration” step  30  are shown in  FIG. 2 . In this step, SC c  is updated ( 32 ) using linear interpolation, although other interpolation methods are possible based on the modeling of the dependence of overall compressed file size on the scaling factor. In a preferred embodiment, SC c  is updated as 
         [0000]    
       
         
           
             
               SC 
               c 
             
             = 
             
               
                 SC 
                 l 
               
               + 
               
                 
                   
                     ( 
                     
                       
                         SC 
                         h 
                       
                       - 
                       
                         SC 
                         l 
                       
                     
                     ) 
                   
                   
                     ( 
                     
                       
                         FS 
                         h 
                       
                       - 
                       
                         FS 
                         l 
                       
                     
                     ) 
                   
                 
                  
                 
                   
                     ( 
                     
                       
                         FS 
                         l 
                       
                       - 
                       
                         FS 
                         l 
                       
                     
                     ) 
                   
                   . 
                 
               
             
           
         
       
     
         [0000]    A new value for downsampling factor ds c  is also set ( 34 ) based on the ratio (FS h −FS l )/FS t , only if it leads to a lower downsampling factor. Those of skill in the art will recognize that the basic idea is that initially, the downsampling factor can be large, resulting in very few frames being compressed. But as the above ratio decreases, i.e. the gap between FS l  and FS h  narrows, the downsampling factor becomes smaller, resulting in more frames being encoded. Then, the quantization table Q, the updated parameters scaling factor SC c , and the downsampling factor ds c  are input to the compression (quantization) step ( 36 ). The compression step produces a new estimated compressed file size. If FS c  is within the tolerance limit, the flow control passes to the “end condition” step  40 . Otherwise in the “update bounds” step ( 39 ), FS c  is compared with FS t . If FS c &lt;FS t , FS l  is set to FS c  and SC h  is set to SC c . Otherwise, if FS c &gt;FS t  (i.e., is not within the tolerance limit), FS h  is set to FS c  and SC l  is set to SC c . Then, the flow control is returned to the beginning of the “scaling factor iteration” step  32 . In rare cases, FS c  may fall outside the interval [FS l , FS h ] resulting in a widening of the interval after the update. This can happen only when the downsampling factor has been updated. In practice, if this condition occurs, it gets corrected quickly in the subsequent scaling factor iterations 
         [0034]    The quantization (compression) step (i.e., step  36 ) is now described in greater detail. The input to the quantization step are L video frames, ds c , Q, SC c . The remainder after dividing L by ds c =r. Then, an offset is chosen at random such that 0≦offset&lt;r. The video frames are be indexed from 0 to L−1. Then, the number of frames that are compressed in the compression step is calculated as 
         [0000]    
       
         
           
             
               L 
               c 
             
             = 
             
               
                 ⌊ 
                 
                   
                     L 
                     - 
                     offset 
                     - 
                     1 
                   
                   
                     ds 
                     c 
                   
                 
                 ⌋ 
               
               + 
               1. 
             
           
         
       
     
         [0000]    The indices of the frames that are compressed are given by n×ds c +offset, where 0≦n&lt;L c . Each such frame is compressed using quantizer table Q scaled by the updated SC c . The sum of the file sizes of the compressed frames is set to be FS ds . Then, the overall compressed file size is estimated to be FS c =FS ds ×(L/L c ). Instead of choosing the offset at random, it is possible to choose a fixed value such as 0. 
         [0035]    The “find lower bound” step  24  is now described in greater detail. The flow diagram for this step is shown in  FIG. 3 . When executing this step, FS h  and SC l  are already set and we are trying to determine FS l  and the corresponding SC h  such that FS l &lt;FS t . First, scaling factor SC c  is initialized to SC l  and a multiplication factor MF l  is chosen (step  50 ). This is greater than 1.0 and can be user-specified or a function of (FS h −FS t )/FS t . In one exemplary embodiment, a multiplication factor of 1.5 can be used. Then, SC c  is set to SC c ×MF l  (step  52 ). Compression is performed using the compression step  54  with quantization table Q, scaling factor SC c , and downsampling factor ds c  to produce an estimate FS c  for the overall compressed file size. At step  56 , a determination is made whether FS c  is within the tolerance limit. If yes, the flow control passes to the “end condition” step  58 . If not within the tolerance limit, a subsequent determination is made as to whether or not FS c &lt;FS t ? If FS c &gt;FS t , flow control is returned to the beginning of the “find lower bound” step  24 . If FS c &lt;FS t , FS l  is set to FS c  and SC h  is set to SC c  (step  60 ) and the flow control is passed to the “scaling factor iteration” step  30  with parameters FS l , FS h , SC l  and SC h . 
         [0036]    The “find upper bound” step  28  is now described in greater detail. The flow diagram for this step is shown in  FIG. 4 . When executing this step, FS l  and SC h  are already set and we are trying to determine FS h  and the corresponding SC l  such that FS t &lt;FS h . First, scaling factor SC c  is initialized to SC h  and a division factor DF h  is chosen (step  70 ). This is between 0 and 1 and can be user-specified or a function of (FS t −FS l )/FS t . In a preferred embodiment, a division factor of 1/1.5 is used. Then, SC c  is set to SC c /DF h  (step  72 ). Compression is performed using the compression step  74  with quantization table Q, scaling factor SC c , and downsampling factor ds c  to produce an estimate FS c  for the overall compressed file size. A determination is then made (step  76 ) as to whether FS c  is within the tolerance limit. If yes, the flow control passes to the “end condition” step  78 . If no, a subsequent determination is made (step  80 ) whether FS t &gt;FS c ? If no, flow control is returned to the beginning of the “find upper bound” step. If yes, FS h  is set to FS c  and SC l  is set to SC c  (step  82 ) and the flow control is passed to the “scaling factor iteration” step  30  with parameters FS l , FS h , SC l  and SC h . 
         [0037]    It should be noted that the flow control can terminate only through the “end condition” step. Also, it is not guaranteed that the final compressed file size is within the tolerance interval. This is because the stop decision may be arrived at based on a downsampling factor that is greater than 1, whereas the final compression step compresses all the frames (ds=1). 
         [0038]    If ds=1 and offset=0 is used as the initial value, then the downsampling factor remains constant throughout. In that case, the algorithm is much simplified and is guaranteed to produce an overall compressed file size within the tolerance limits of the target file size. 
         [0039]    In JPEG2000 it is common to use a rate-distortion parameter to determine the compressed coding pass data that is included in the final code-stream (“JPEG2000: Image Compression Fundamentals, Standards and Practice,” David S. Taubman and Michael W. Marcellin, Springer 2002). In that case, instead of finding a scaling factor that achieves the target compressed file size, we are trying to find a rate-distortion slope parameter that produces the target compressed file size. Those skilled in the art will realize that instead of iterating on the scaling factor, it would be possible to iterate on the rate-distortion slope parameter to achieve the overall target compressed file size. 
         [0040]    It is possible to apply this method to the rate-control of AVC H.264 intra-only bit-streams (ISO/IEC 14496-10:2003, “Coding of Audiovisual Objects—Part 10: Advanced Video Coding,” 2003, also ITU-T Recommendation H.264 “Advanced video coding for generic audiovisual services). Some profiles in H.264 offer an option to use custom Q-tables. Additionally, AVC H.264 offers the flexibility of choosing a quantization parameter QP that can be varied from one macroblock to another. But it may be desirable to maintain the value of QP constant throughout the video. In such a case, those skilled in the art will recognize that the present method can be applied for performing rate-control. This scenario is more restrictive, since only QP can take only integer values. 
         [0041]      FIG. 5  shows a basic block diagram of a system  90  implementing the above described method of the invention. The system  90  includes a processor  92 , and one or more ROM memories  94  and one or more RAM like memories  96 . The ROM memory  94  can be pre-programmed to enable the processor  92  to perform the rate control of the present invention, or alternatively, the RAM memory  96  can be loaded with such instructions upon initialization. According to the preferred implementation, the input to system  90  is raw uncompressed frame (e.g. YUV frames), and the output is the compressed data in accordance with the above-described methods. Those of ordinary skill in the art will appreciate that the system  90  may also include a user input interface  98  of any known type (e.g., keyboard, mouse, touch screen, etc.) and a display device (not shown in  FIG. 5 ) to enable user input for required parameters such as, for example, the initial specification of a target compressed file size and file size tolerance, in addition to selecting a quantization table, the current scaling factor and current down sampling factor. 
         [0042]    These and other features and advantages of the present principles may be readily ascertained by one of ordinary skill in the pertinent art based on the teachings herein. It is to be understood that the teachings of the present principles may be implemented in various forms of hardware, software, firmware, special purpose processors, or combinations thereof. 
         [0043]    Most preferably, the teachings of the present principles are implemented as a combination of hardware and software. Moreover, the software may be implemented as an application program tangibly embodied on a program storage unit. The application program may be uploaded to, and executed by, a machine comprising any suitable architecture. Preferably, the machine is implemented on a computer platform having hardware such as one or more central processing units (“CPU”), a random access memory (“RAM”), and input/output (“I/O”) interfaces. The computer platform may also include an operating system and microinstruction code. The various processes and functions described herein may be either part of the microinstruction code or part of the application program, or any combination thereof, which may be executed by a CPU. In addition, various other peripheral units may be connected to the computer platform such as an additional data storage unit and a printing unit. 
         [0044]    It is to be further understood that, because some of the constituent system components and methods depicted in the accompanying drawings are preferably implemented in software, the actual connections between the system components or the process function blocks may differ depending upon the manner in which the present principles are programmed. Given the teachings herein, one of ordinary skill in the pertinent art will be able to contemplate these and similar implementations or configurations of the present principles. 
         [0045]    Although the illustrative embodiments have been described herein with reference to the accompanying drawings, it is to be understood that the present principles is not limited to those precise embodiments, and that various changes and modifications may be effected therein by one of ordinary skill in the pertinent art without departing from the scope or spirit of the present principles. All such changes and modifications are intended to be included within the scope of the present principles as set forth in the appended claims.