One-Pass Adaptive Bit Rate Control

This application is related to an application entitled "Random Access Audio/Video Processor with Multiple Outputs," to David Rossmere, Robert Glenn, Jr., William Brown, John Carluci and Robert Duffy, Ser. No. 08.196.018, filed Feb. 14. 1994; and to an application entitled Random Access Audio/Video Processor with Compressed Video Resampling to allow Higher Bandwidth Throughput," by David Rossmere, Robert Glenn, Jr., William Brown, John Carluci and Robert Duffy, Ser. No. 08/196,038, filed Feb. 14, 1994. Both of these applications are hereby incorporated by reference.

1. Field of the Invention

This invention relates generally to the field of data compression. More particularly, this invention relates to a method and apparatus for data compression using adaptive bit rate control which is particularly well suited for compression of video data which should be maintained at an approximately constant compressed data size.

2. Background of the Invention

Referring to FIG. 1, a typical field-based video data compression system 10, such as a JPEG (Joint Pictures Expert Group) style system, includes a source data memory 12 which provides data to a video compressor 16. A compressed data counter 20 makes a determination of the size of the compressed data and provides this information to a bit rate controller 24. The bit rate controller makes a determination of a quantizer scale factor and provides this information to the video compressor 16. The compressed data from the video compressor 16 is provided to a compressed data memory 28 which is ultimately used as the source of data for a transport medium 32 (or storage medium).

The source data memory 12 contains the uncompressed video data. The video compressor 16 processes data from the source data memory, reduces its data volume, and stores the compressed video data into the compressed data memory 28. The compressed data counter 20 counts the number of compressed data bytes output by the video compressor 16 during each field. The bit rate controller 24 adjusts the compression parameters to control the volume of data output by the video compressor 16. Compressed video data is moved via the transport medium 32 to other locations.

In a JPEG style video compressor such as 16, compression takes place in three stages: transform 40, quantization 44, and entropy coding 48. In the transform stage, video data is transformed from time domain information into a frequency domain representation using, for example, a discrete cosine transform or fast Fourier transform or the like. This frequency domain information is represented as a matrix. In the quantization stage 44, transformed data is divided by a value from scaled quantizer matrix produced by quantization matrix scaler 52. A large quantizer scale factor at 56 creates larger values in the scaled quantizer matrix at 60, and causes more information to be discarded in the quantization operation of quantizer 44. The compression ratio, defined to be the size of the source video data divided by the size of the compressed video data, is primarily determined by the value of the quantizer scale factor at 56.

Many video compression techniques, such as the JPEG compression standard, produce a compressed data stream that varies in volume depending on the complexity of the source video image. However, in many cases the compressed data stream must then be carried by some medium which has limited data carrying capacity. To prevent overflow of the transport medium, the volume of data produced by the compression technique must be controlled.

Typically, a buffer memory such as 28 is inserted between the output of the variable bit rate video compression circuitry and the input of the constant bit rate transport medium. The buffer memory is used to smooth out variations in the volume of data output by the compression circuitry. Because the buffer memory size is limited, the volume of data produced by the video compression circuitry must still be controlled to prevent buffer overflow.

For most field,based video compression systems, the amount of compression is primarily controlled by the quantization process. In this process, a matrix of transformed video data is divided by a quantization matrix at 44. Because the remainder of the division operation is discarded, information is lost and the number of bits required to represent the source data is reduced. The compressed data volume is controlled at quantization matrix scaler 52 by multiplying the quantization matrix by the quantizer scaling factor at 56. A large quantizer scaling factor increases all of the values in the quantization matrix, which results in more data being discarded in the division operation, and consequently a lower output data volume.

In most applications, the volume of data produced by the video compression circuitry must very closely match the data carrying capacity of the transport medium. To produce this precise control over data volume, an iterative process is used to pick the optimal quantizer scale factor. This iterative process requires each field of data to be compressed multiple times. For a particular field of video data, typically an initial quantizer scale factor is selected, and compression is performed. The volume of data produced is compared to the desired data volume, and the quantizer scale factor is adjusted. If the target data volume was exceeded, the quantizer scale factor is increased, and vice versa. This process is repeated several times until an optimal quantizer scale factor is found for a particular field. The object is to closely match the capacity of the transport medium so that the best quality picture is obtained consistent with the limitations of the transport medium.

Iteration to produce an optimal quantizer scale factor provides precise control over compressed data volume, but can become impractical in real-time systems. In a real-time system, every field must be compressed in a time no longer than one field time. If iteration is used, then a particular field must be compressed several times during one field time, or several compression circuits must be used in parallel. In either case, the system cost can be high due to the need for extremely high speed processing or multiple processors (compressors) are needed to implement the compression.

It is an object of the present invention to provide an improved compression method suitable for use in real time video to produce an approximately constant data rate.

It is a feature that the present invention is simple to implement.

It is an advantage that the present invention provides approximately constant rate output data.

It is a further advantage that one embodiment of the present invention provides detection of scene changes.

These and other objects, advantages and features of the invention will become apparent to those skilled in the art upon consideration of the following description of the invention.

The present invention relates to a one pass adaptive bit rate control method particularly useful for video data. Data from a previous video field is used to calculate a quantizer scale factor for use in compressing a current video field. Large changes in compressed data size is used to detect scene changes. When a scene change is detected, a marker is inserted into the compressed data stream in place of the compressed field. An interpolated field is substituted during decompression for the scene change marker.

To avoid confusion in terminology, for purposes of this discussion:

F.sub.n refers to the current frame (number n) being processed;

S.sub.n refers to the size of the compressed field F.sub.n ;

Q.sub.n refers to the quantization factor computed from and used to compress field F.sub.n.

In one aspect of the present invention, a method for compressing a sequence of fields of video data F.sub.n where n is a field counting number, includes the steps of: (a) establishing a desired data size S.sub.desired for fields of compressed data; (b) calculating a quantization factor Q.sub.n from the size S.sub.n-1 resulting when a field of data F.sub.n-1 was compressed; (c) compressing a field of data F.sub.n using the quantization factor Q.sub.n ; and (d) repeating steps (b) and (c) for each value of n for the sequence of fields of video.

In another aspect of the invention, a method for compressing a sequence of fields of video data F.sub.n where n is a field counting number, includes the steps of: establishing a desired data size S.sub.desired for fields of compressed data; calculating an initial quantization factor Q.sub.1 as: ##EQU1##

where k is a constant; compressing the field F.sub.1 using an initial quantization factor Q.sub.1 ; for each n>1, calculating a quantization factor Q.sub.n using ##EQU2##

and; for n>1, compressing each field of data F.sub.n using the quantization factor Q.sub.n.

In another aspect of the present invention, a method for compressing a sequence of fields of video data F.sub.n where n is a field counting number, includes the steps of: establishing a desired data size S.sub.desired for fields of compressed data; calculating an initial quantization factor Q.sub.1 for compressing field F.sub.1 as: ##EQU3##

where k is a constant; compressing the field F.sub.1 using the quantization factor Q.sub.1 ; for n>1, calculating a quantization factor Q.sub.n for each field of data F.sub.n using ##EQU4##

where c is a constant; and for n>1 , compressing each field of data F.sub.n using the quantization factor Q.sub.n.

In yet another aspect of the invention, a method for compressing a sequence of fields of video data F.sub.n where n is a field counting number, includes the steps of: establishing a desired data size S.sub.desired for fields of compressed data; establishing an initial quantization factor Q.sub.1 for compressing field F.sub.1 ; compressing the field F.sub.1 using the quantization factor Q.sub.1 ; for n>1, establishing a quantization factor Q.sub.n for each field of data F.sub.n ; and for n>1, compressing each field of data F.sub.n using the quantization factor Q.sub.n calculated using the actual data size S.sub.n-1 obtained when field F.sub.n-1 was compressed.

A method, according to the invention, for compressing a sequence of fields of video data F.sub.n where n is a field counting number, includes the steps of: establishing a desired data size S.sub.desired for fields of compressed data; establishing an initial quantization factor Q.sub.1 for compressing field F.sub.1 ; compressing the field F.sub.1 using the quantization factor Q.sub.1 ; for n>1, establishing a quantization factor Q.sub.n for each field of data F.sub.n ; for n>1, compressing each field of data F.sub.n using the quantization factor Q.sub.n calculated using an actual data size S.sub.n-1 obtained when field F.sub.n-1 was compressed; and for n>1, each field's compressed data size S.sub.n is compared with the previous field's compressed data size S.sub.n-1 and if the difference between S.sub.n and S.sub.n-1 is greater than a predetermined threshold, then a substitute field or scene change marker is substituted for field F.sub.n.

With the present invention, precise control of compressed data volume is not needed because a large buffer memory can absorb data volume fluctuations. This invention uses data from the previous field to calculate a quantizer scale factor for the current field. The calculation is computationally simple, and can be performed very quickly. Adequate control of compressed data volume is achieved with minimum complexity and in a manner suitable for use in a real time system.

The features of the invention believed to be novel are set forth with particularity in the appended claims. The invention itself however, both as to organization and method of operation, together with further objects and advantages thereof, may be best understood by reference to the following description taken in conjunction with the accompanying drawing.

FIG. 1 is a block diagram of a compression system.

FIG. 2 is a block diagram of a JPEG style compressor.

FIG. 3 is a flow chart of the compression process used in the present invention.

FIG. 4 is a flow chart describing a compression process using scene change detection.

FIG. 5 is a flow chart of a decompression process according to the present invention.

While this invention is susceptible of embodiment in many different forms, there is shown in the drawings and will herein be described in detail specific embodiments, with the understanding that the present disclosure is to be considered as an example of the principles of the invention and not intended to limit the invention to the specific embodiments shown and described. In the description below, like reference numerals are used to describe the same, similar or corresponding parts in the several views of the drawing.

Referring to FIG. 1, the present invention utilizes a new method of bit rate control within bit rate controller 24. Otherwise, the basic block diagram is similar to that described above. The value of the quantizer scale factor at 56 is set by the bit rate controller 24. While each field is being compressed, the compressed data counter 20 counts the number of bytes of compressed video data that are generated. After the field has been compressed, the bit rate controller 24 uses the field's quantizer scale factor, the compressed video data size generated by using that scale factor, and the desired compressed video data size to calculate a new quantizer scale factor. This new quantizer scale factor is used by the compressor to create a new scaled quantizer matrix in the standard manner, which is used for the next field. That is, the scale factor used for compressing the current field is that calculated from the scale factor which is required for the preceding field. All of this processing is performed in the interval between two fields. Of course, the quantization information may be encoded for transmission to the receiving end to permit proper decoding if the particular compression technique requires such.

The process used in this invention is described with reference to FIG. 3 starting at step 100. In this method of bit rate control, the value of desired data size variable S.sub.desired is initially set at step 104 to the desired field compressed data size. Then, an initial value of the quantizer scale factor Q' is calculated at 108, and this value is stored in the compressor at 112. After the entire field has been compressed as determined at step 116, the value of previous field quantizer scale factor variable Q is set to the current value of Q' , and the compressed data size S is retrieved from the compressed data counter at 118. Using these values, a new quantizer scale factor Q' is calculated at 122, and this value is stored into the compressor at 128 and used to compress the next field. The current field is stored at 130 in compressed data memory 28 or otherwise processed. This process repeats indefinitely.

After every field has been compressed, the previous quantizer scale factor and the resulting compressed data size are used to calculate a new quantizer scale factor. The algorithm used for this calculation is very easy to calculate, yet provides good control of compressed data size. This algorithm was empirically derived from observations of the relationship between quantizer scale factor and resulting compressed data size for many different fields of video.

The initial quantization factor used to compress the first field of data is derived empirically. In the preferred embodiment, the formula for initial quantizer scale factor is shown in Equation 1, ##EQU5## where Q' is the initial quantizer scale factor used to compress the first field of data, and S.sub.desired is the desired compressed data size. Other initial quantization factors may also be selected if desired or if a good factor is known for the initial field.

The general formula for subsequent quantizer scale factors is shown in Equation 2, ##EQU6## where Q' is the new quantizer scale factor, S.sub.desired is the desired compressed data size, Q is the previous quantizer scale factor, and S is the resulting compressed data size.

As a practical matter, it is desirable to limit changes in the quantizer scale factor. For example, a flat black video image contains almost no information, and will naturally result in a very small compressed data size. When compressing a sequence of flat black images, because S.sub.desired is larger than S, the value of Q' will become very small. This is not only wasteful of transport medium bandwidth, but will result in an extremely large compressed data size if the scene changes to a complicated image. Therefore, Equation 1 and Equation 2 should, as a practical matter, be modified so that Q' has a floor value, as shown in Equation 3 and Equation 4, ##EQU7## where C is a constant. The value of C depends on the value of S.sub.desired. To prevent Q' from becoming too small, we can use Equation 1 to develop a (fairly arbitrary) value for C. The equation shown as Equation 5 has been found suitable for a wide range of images. ##EQU8##

Thus, for a sequence of video fields F.sub.n, where n is a field number, the quantization factor Q.sub.n which is used for compression of the current field of data F.sub.n is calculated as follows to obtain a data size of approximately S.sub.desired : ##EQU9## and where S.sub.n-1 is the actual size obtained after compression of the previous field of video data F.sub.n-1 using quantization factor Q.sub.n-1. The initial field F.sub.1, is compressed using quantization factor Q.sub.1 as follows: ##EQU10## which could be generalized to: ##EQU11## where k is a constant.

In the case where the bounds are not needed for the quantization factor values, the quantization factor for field F.sub.n can be calculated as in EQUATION 2, which would become: ##EQU12##

Note that each field is compressed using a quantizer scale factor calculated from the compressed data size of the previous field of data. Thus, the quantization factor is continuously adjusted to provide a good approximation of the quantization factor needed for the current video information. For video images that are either unchanging or only changing slightly in complexity, this technique provides good compression performance, and approximates the desired compressed data size. This bit rate control method takes advantage of the fact that most video fields are very similar to the temporally previous video field. The present one-pass non-iterative method of bit rate control is advantageous because parallel compressors are unnecessary and compression does not have to be performed faster than real time.

However, a one-pass .bit rate control mechanism cannot generally perfectly control compressed data size if the complexity of consecutive video fields is radically different, such as at scene changes. Because every field is compressed using a quantizer scale factor calculated from the compressed data size of the previous field, the first field of a scene change can be overcompressed or undercompressed. Therefore, this bit rate control mechanism preferably uses a compressed data buffer that is large enough to prohibit a single undercompressed video field from causing a buffer overflow. If a single overcompressed or undercompressed video field is visually objectionable, then corrective measures, such as field replication as discussed below, can be taken to reduce the problem.

This invention uses the compression results from the previous field to calculate a quantizer scale factor for the current field. The desired data volume is achieved because, in general, consecutive fields of video data are similar in complexity. However, consecutive fields of video data can be very different at a "scene change." If the complexity of the current field's video image is higher than that of the previous field, then the volume of compressed data created will be higher than the desired amount. Conversely, if the complexity of the current field's video image is lower than that of the previous field, then the volume of compressed data will be lower than the desired amount. In either case, because this field's compression results will be used to calculate the quantizer scale factor, the volume of compressed data output for the next field will be close to the desired size.

In many video applications, it is desirable to automatically find scene changes. The large deviations of the actual compressed data volume from the expected compressed data volume can be used to detect scene changes as illustrated in FIG. 4. In this figure, which constitutes a modification of FIG. 3, the change in compressed field size is examined at step 138. For every field, the actual compressed data volume is compared to the expected compressed data volume. The expected size is that of the previous compressed field. Thus, if S.sub.n, the size of the current field, is much larger or smaller than the previous field S.sub.n-1, so that the absolute value of the difference in size is greater than some threshold value .increment..sub.max, then it can be assumed that the video complexity suddenly changed, and that a scene change has been encountered. When this threshold is exceeded, the process goes to step 144 in which a marker indicating that a scene change has taken place is stored in the compressed data memory 28 in place of the compressed field. When the threshold .increment..sub.max is not exceeded, control passes to step 130 where the compressed field is stored in memory 28.

In FIG. 4, at step 138, the size of the resulting compressed data is compared with the size of the previous data field by subtracting S.sub.n-1 from S.sub.n and comparing the absolute value of the result with a maximum difference value .increment..sub.max. If the difference is greater than .increment..sub.max, then it can be presumed that a scene change has taken place and the quantization factor for field F.sub.n-1 is not appropriate to provide suitable compression. Corrective action is taken in the decoding of the compressed data as shown in FIG. 5.

Referring to FIG. 5, the decoding process for compressed data generated as illustrated above is described. In this arrangement, compressed data is examined at step 200 to see if a scene change marker is present. If not, the data is decompressed in a normal fashion at step 210 to produce output decompressed data. In the event a scene change marker is found at step 200, a substitute field of data is generated at step 220 and provided as an output.

The substitute field of data can be generated in a number of ways. In one embodiment, the previous field of decompressed video can be repeated at step 220. In another embodiment, field interpolation can be used to generate the substitute field. Field interpolation can create an "odd" field from an "even" field or vice versa. It can also be used to reduce image bounce in slow-speed play, and to double vertical resolution under certain circumstances. In the present invention, a vertical averaging filter is used to carry out the interpolation using the following equations: ##EQU13## These equations calculate a synthetic pixel which is spatially midway between the two existing pixels in actual video fields. EQUATION 11 above calculates the spatially higher line while EQUATION 12 above calculates the spatially lower line. Other techniques could also be used to generate the substitute field, including deletion of the field.

The present invention can be implemented in any number of ways without departing from the present invention. For example, a programmed processor can be used to carry out all of the processing described. Alternatively, a hardware implementation using lookup ROMs to store values of the quantization factor corresponding to particular sizes of the compressed data be used. Of course, a hardware implementation using two multipliers and a divider can also be considered.

The invention is preferably implemented using a combination of both hardware and software. All of the compression processing, including quantizer scaling and quantization, is preferably implemented using an application-specific integrated circuit. The quantizer scale factor calculation is preferably performed by a programmed processor such as a microprocessor. The buffer memory is implemented in hardware. Of course, in the alternative, the quantizer scale factor calculation can be performed in hardware, using either special purpose multipliers and dividers, or using lookup tables as suggested above. Other variations will occur to those skilled in the art after consideration of the present invention. Those skilled in the art will also appreciate that a wide range of constants k and c can be expected to be functional in the present invention and that those constant values presented are merely illustrative of values which have been experimentally determined to function reasonably well over a wide range of video input.

Thus it is apparent that in accordance with the present invention, an apparatus that fully satisfies the objectives, aims and advantages is set forth above. While the invention has been described in conjunction with specific embodiments, it is evident that many alternatives, modifications, permutations and variations will become apparent to those skilled in the art in light of the foregoing description. Accordingly, it is intended that the present invention embrace all such alternatives, modifications and variations as fall within the scope of the appended claims.