Data compression using a feedforward quantization estimator

• US 5,146,324 A
• Filed: 07/31/1990
• Issued: 09/08/1992
• Est. Priority Date: 07/31/1990
• Status: Expired due to Term

• Current Assignee: Ampex Corporation (Delta Information Systems, Inc.)
• Original Assignee: Ampex Corporation (Delta Information Systems, Inc.)
• Inventors: Miller, Sidney D., Smidth, Peter, Coleman, Charles H.
• Primary Examiner(s): Kostak, Victor R.
• Application Number:
  US07/560,606
• Time in Patent Office: 770 Days
• Field of Search: 358/135, 358/133, 358/12, 375/122
• US Class Current: 375/240.03
• CPC Class Codes: H04N 19/124 Quantisation
• CPC Class Codes: H04N 19/126 Details of normalisation or weighting functions, e.g. normalisation matrices or variable uniform quantisers
• CPC Class Codes: H04N 19/146 Data rate or code amount at the encoder output
• CPC Class Codes: H04N 19/149 by estimating the code amount by means of a model, e.g. mathematical model or statistical model
• CPC Class Codes: H04N 19/172 the region being a picture, frame or field
• CPC Class Codes: H04N 19/176 the region being a block, e.g. a macroblock
• CPC Class Codes: H04N 19/186 the unit being a colour or a chrominance component
• CPC Class Codes: H04N 19/192 the adaptation method, adaptation tool or adaptation type being iterative or recursive
• CPC Class Codes: H04N 19/42 characterised by implementation details or hardware specially adapted for video compression or decompression, e.g. dedicated software implementation H04N19/635 takes precedence
• CPC Class Codes: H04N 19/46 Embedding additional information in the video signal during the compression process H04N19/517, H04N19/68, H04N19/70 take precedence
• CPC Class Codes: H04N 19/60 using transform coding
• CPC Class Codes: H04N 19/85 using pre-processing or post-processing specially adapted for video compression
• CPC Class Codes: H04N 19/88 involving rearrangement of data among different coding units, e.g. shuffling, interleaving, scrambling or permutation of pixel data or permutation of transform coefficient data among different blocks

Abstract

An image data compression technique is described which utilizes calculating means and a selected series of bit calculating stages having delays, to estimate one or more quantization parameters for such data. The estimation process preferably is iterated a number of times, with the values found through each estimation being used as the trial values for subsequent estimations. In addition, an initial trial value is selected by a data look ahead technique, which assures that its value is within range of the final quantization parameter used to quantize the data. The final quantization parameter insures that the compressed data fits within a predetermined number of encoded data bits to be transmitted or recorded, for example, in a recording medium.

Claims

1. A method of preparing a digital video signal, having a data rate, D_in, for transmission as an encoded output signal, said encoded output signal to be transmitted over a channel having a preselected constant data rate capacity, D_out, which is less than the data rate D_in, said method comprising the steps of:

(a) transforming said video signal to a spatial-frequency domain digital signal formatted in groups of transform coefficients of generally varying information content;

(a1) estimating trial quantizing parameters from one of the groups;

(b) selecting in response to said trial quantizing parameters values of final quantizing parameters Q_f for the groups of transform coefficients in accordance with their respective generally varying information content, which parameters Q_f when applied to quantize the coefficients would generate respective encoded output signals with a predetermined number of encoded bits corresponding to said constant data rate D_out ;

(c) quantizing said groups of transform coefficients of generally varying information content to integral values in response to respective said quantizing parameters, Q_f, to generate therewith groups of quantized coefficients of essentially constant information content; and

(d) encoding said groups of quantized coefficients of essentially constant information content to produce said encoded output signal of said predetermined number of encoded bits corresponding to said constant data rate D_out.

2. The method of claim 1 wherein said selecting step further comprises the steps of:

(e) delaying, subsequent to said transforming step, said transform coefficients for a first predetermined period of time;

(f) selecting, while delaying said transform coefficients, a trial quantizing parameter Q_t and counting the number of encoded bits that would be produced by said encoding step during said first predetermined period of time if Q_t was used as the quantizing parameter Q_f ;

(g) determining the difference between said counted number of encoded bits and the number of bits corresponding to the data rate D_out ;

(h) applying, if said difference is 0, said trial quantizing parameter Q_t in said step (c) for use as said quantizing parameter Q_f ; and

,

(i) computing, if said difference is other than 0, an updated value for said trial quantizing parameter Q_t so as to reduce said difference, and repeating steps (e)-(i) N times, N>

1.

3. The method of claim 2 wherein said transforming step (a) further comprises transforming said video signal using a discrete cosine transform.

4. The method of claim 2 further comprising at the beginning of each field of said digital video signal the step of:

(j) delaying, prior to said first delaying step, said groups of transform coefficients for a second predetermined period of time equal to

(N) (said first predetermined period of time),

while also performing steps (e)-(i) N times on the same set of transform coefficients; and

(k) applying the quantizing parameter Q_t selected on the N^th selecting step in (j) as the trial quantizing parameter Q_t for the first selecting step for all subsequent trial quantizing parameters Q_t '"'"'s related to a particular field of said digital video signal.

5. The method of claim 1 further comprising the steps of:

(l) formatting subsequent to said encoding step (d) said encoded output signal into the format of said channel; and

(m) interleaving with said formatted encoded output signals said quantizing parameter Q_f with each encoded group of quantized coefficients to which said quantizing parameter Q_f relates.

6. The method of claim 1 wherein the step of selecting includes:

examining in advance one of said groups prior to supplying all of the groups;

estimating a trial quantizing parameter, Q_t, from said pre-examined one of the groups; and

determining, in response to said trial quantizing parameter, Q_t, for all the groups, the quantizing parameter, Q_f, which provides the encoded output signal with the predetermined number of encoded bits corresponding to said constant data rate D_out.

7. Apparatus for compressing a data signal defining a video image into a data space of a predetermined number of bits, comprising:

means for transforming said data signal to a digital signal formatted in groups of transform coefficients of generally varying information content;

means responsive to said groups of transform coefficients of generally varying information content for first estimating trial numerical processing parameters from a first of the groups, and then in response to the trial numerical processing parameters estimating the values of final numerical processing parameters which will quantize said transform coefficients into said data space of a predetermined number of bits; and

means for applying said estimated parameters subsequently to the same said groups of transform coefficients which were used to estimate the parameters, to compress said groups of transform coefficients into respective data spaces of said predetermined number of bits.

8. Apparatus for compressing a data signal defining a video image, comprising:

means for transforming said data signal to a digital signal formatted in predetermined groups of transform coefficients;

means responsive to said predetermined groups of transform coefficients for estimating the value of a numerical processing parameter for quantizing said transform coefficients;

means for applying said estimate subsequently to said predetermined groups of transform coefficients which were used to estimate said numerical processing parameter; and

wherein said means for estimating includes parameter estimator means having a plurality of bit calculating stages for estimating said numerical processing parameter which is to be applied to the same predetermined groups of transform coefficients.

9. The apparatus of claim 8 wherein the parameter estimator means includes:

calculating means for determining successive estimates of the processing parameter for the respective stages; and

bit counter means in said stages for supplying to said calculating means the number of encoded bits which would be produced by a respective stage in response to the respective processing parameter estimate determined by the calculating means for that stage.

10. The apparatus of claim 9 including:

means for encoding said transform coefficients to provide said compressed data signal as a desired number of bits; and

wherein said calculating means determines, for a final one of the stages, a final processing parameter which would cause said encoding means to produce said compressed data signal with substantially the desired number of bits.

11. The apparatus of claim 8 wherein said parameter estimator means includes:

first means for delaying said transform coefficients for a first time period during which the parameter estimator means estimates the processing parameter and supplies same to the means for applying.

12. The apparatus of claim 11 wherein the means for estimating further includes:

second means for delaying said transform coefficients for a second time period prior to said first time period delay;

means for bypassing a first portion of the transform coefficients around the second means for delaying; and

calculating means responsive to said first portion of the transform coefficients for estimating an initial trial processing parameter for subsequent use by the calculating means when estimating said processing parameter which is to be applied to the predetermined groups of transform coefficients.

13. The apparatus of claim 12 wherein:

said first means for delaying includes a delay in each of the plurality of bit calculating stages; and

said second means for delaying includes a delay having a time delay substantially equal to the plurality of delays in the stages.

14. A method of preparing a digital signal for transmission as an encoded output signal formed of data blocks having a predetermined number of bits, comprising the steps of:

transforming said digital signal to a spatial-frequency domain digital signal formatted in groups of transform coefficients of generally varying information content;

selecting via a plurality of previous trial bit calculating steps, final quantizing parameters to be applied to the same said groups of transform coefficients, which final quantizing parameters, when applied to said groups of transform coefficients of generally varying information content, will provide substantially said predetermined number of bits in each of said data blocks;

quantizing said groups of transform coefficients in response to said final quantizing parameters to generate integral values of groups of quantized coefficients having substantially the same information content; and

encoding said quantized coefficients to produce said encoded output signal of data blocks, with said substantially predetermined number of bits in each data block.

15. The method of claim 14 wherein said step of selecting includes the steps of:

delaying said transform coefficients a first time period;

selecting a trial quantizing parameter during said first time period delay;

determining if the number of encoded bits that would be produced by said encoding step in response to said trial quantizing parameter is substantially the same as said predetermined number of bits in each of said data blocks;

applying said trial quantizing parameter for use as said final quantizing parameter if the number is substantially the same;

estimating an updated trial quantizing parameter if the number is not the same; and

repeating the steps of determining, applying and estimating until said number is substantially the same.

16. The method of claim 15 wherein the step of selecting a trial quantizing parameter further includes the steps of:

selecting said trial quantizing parameter from an undelayed group of said transform coefficients prior to supplying all of the transform coefficients; and

using the trial quantizing parameter derived from said undelayed group in said step of determining, for all the transform coefficients.