Digital video compression system and methods utilizing scene adaptive coding with rate buffer feedback

• US 4,302,775 A
• Filed: 12/15/1978
• Issued: 11/24/1981
• Est. Priority Date: 12/15/1978
• Status: Expired due to Term

• Current Assignee: Magnitude Compression Systems Incorporated
• Original Assignee: Compression Labs Incorporated (Asure Software)
• Inventors: Widergren, Robert D., Chen, Wen-Hsiung, Tescher, Andrew G., Fralick, Stanley C.
• Primary Examiner(s): Moffitt, James W.
• Assistant Examiner(s): PSITOS, ARISTOTELIS
• Application Number:
  US05/969,991
• Time in Patent Office: 1,075 Days
• Field of Search: 364/514, 364/515, 364/576, 364/582, 358/12, 358/13, 358/133, 358/138, 358/260, 358/261, 340/347 DD
• US Class Current: 375/240.06
• CPC Class Codes: G06F 7/785 having a sequence of storage locations each being individually accessible for both enqueue and dequeue operations, e.g. using a RAM
• CPC Class Codes: H04N 11/044 involving transform coding
• 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/152 by measuring the fullness of the transmission buffer
• 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/196 being specially adapted for the computation of encoding parameters, e.g. by averaging previously computed encoding parameters processing of motion vectors H04N19/513
• CPC Class Codes: H04N 19/197 including determination of the initial value of an encoding parameter H04N19/56 takes precedence
• CPC Class Codes: H04N 19/30 using hierarchical techniques, e.g. scalability H04N19/63 takes precedence
• CPC Class Codes: H04N 19/423 characterised by memory arrangements H04N19/433 takes precedence
• CPC Class Codes: H04N 19/50 using predictive coding H04N19/61 takes precedence
• CPC Class Codes: H04N 19/60 using transform coding
• 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

A digital video compression system and its methods for compressing digitalized video signals in real time at rates up to NTSC color broadcast rates are disclosed. The system compressor receives digitalized video frames divided into subframes, performs in a single pass a spatial domain to transform domain transformation in two dimensions of the picture elements of each subframe, normalizes the resultant coefficients by a normalization factor having a predetermined compression ratio component and an adaptive rate buffer capacity control feedback component, to provide compression, encodes the coefficients and stores them in a first rate buffer memory asynchronously at a high data transfer rate from which they are put out at a slower, synchronous rate. The compressor adaptively determines the rate buffer capacity control feedback component in relation to instantaneous data content of the rate buffer memory in relation to its capacity, and it controls the absolute quantity of data resulting from the normalization step so that the buffer memory is never completely emptied and never completely filled. In expansion, the system essentially mirrors the steps performed during compression. An efficient, high speed decoder forms an important aspect of the present invention. The compression system forms an important element of a disclosed color broadcast compression system.

Claims

1. A method for one pass compressing, transferring through a medium and expanding in real time digitalized television video frames, the compression steps comprising:

(a) dividing each digitalized frame into a predetermined matrix of sub-frames;

(b) performing a predetermined spatial domain to transform domain transformation in two dimensions of the picture elements of each sub-frame to provide transform coefficients thereof;

(c) storing said transform coefficients in a memory at a rate related to the video frame rate;

(d) normalizing said transform coefficients by operation of a normalization factor having a predetermined compression ratio component to perform threshold coding of said transform coefficients and an adaptive rate buffer capacity control feedback component, to provide compression and to provide normalized transform coefficients compatible with a predetermined data coding scheme including Huffman coding of amplitude coefficients and run length coding of zero amplitude coefficients following coefficient normalization;

(e) coding said normalized transform coefficients in accordance with said predetermined data coding scheme for further compression and transfer through said limited bandwidth medium;

(f) loading said coded coefficients into an encode rate first in, first out buffer memory asynchronously at a high data transfer rate;

(g) unloading said coded coefficients from said encode rate buffer memory at a slow data transfer rate capable of passing through said limited bandwidth medium; and

(h) adaptively determining said rate buffer capacity control feedback component in relation to the instantaneous data content of said rate buffer memory in relation to its capacity, to control at said normalization step the absolute quantity of data resulting therefrom so that said rate buffer memory is never completely emptied and never completely filled, and combining said feedback component with said compression ratio component to provide said normalization factor; and

,

the expansion steps comprising;

(i) loading said coded coefficients into a decode rate first in, first out buffer memory at said slow synchronous data transfer rate;

(j) unloading said coded coefficients from said decode rate buffer memory asynchronously at a high data transfer rate;

(k) decoding said coded coefficients in accordance with an inverse of said predetermined data coding scheme;

(l) inversely normalizing said decoded transform coefficients by operation of an inverse normalization factor having a predetermined expansion ratio component and an adaptive decode rate buffer capacity control feed forward component, to provide expansion of said transform coefficients;

(m) adaptively determining said rate buffer capacity control feed forward component in relation to said instantaneous data content of said decode rate buffer memory in further relation to its capacity so as to control at said inverse normalization step the absolute quantity of data resulting therefrom and thus the rate at which said coded coefficients are unloaded asynchronously from said decode rate buffer memory so that it is never completely emptied and never completely filled, and combining said feed forward component with said expansion ratio component to provide said inverse normalization factor;

(n) performing the inverse of said predetermined transformation of said expanded transform coefficients to provide reconstituted picture elements of each sub-frame;

(o) assembling said sub-frames into said predetermined matrix and putting them out at said video frame rate so as to reconstruct digitalized picture frames closely approximating the corresponding original video frames.

2. A system for one pass compression and expansion of digitalized video sub-frames in the line scan format in real time including a compressor and an expander,

said compressor comprising:

two dimensional spatial domain to transform domain transformer means for performing a predetermined transformation of the picture elements of each sub-frame which will provide two dimensional transform coefficients thereof,

normalization means connected to said transformer means for multiplying said transform coefficients by a normalization factor having a predetermined compression component and an adaptive rate buffer capacity control feedback component to provide compression and to provide normalized transform coefficients compatible with a predetermined data coding scheme,

encoder means for encoding said normalized transform coefficients in accordance with said predetermined data coding scheme including Huffman coding of amplitude of coefficients and run length coding of zero amplitude coefficients for further compression and transfer through a limited bandwidth medium to said expander,

rate buffer memory means connected to said encoder means for storing said coded coefficients in said memory means asynchronously at a high data transfer rate, for putting out said coded coefficients at a slow synchronous data transfer rate capable of passing through said limited bandwidth medium, and for adaptively determining said rate buffer capacity control feedback component in relation to the instantaneous data content of said rate buffer memory means, in further relation to its capacity, to control at said normalization means the absolute quantity of data resulting from the operation thereof so that said rate buffer memory means is never completely emptied and is never completely filled;

said expander comprising;

second rate buffer means connected to said limited bandwidth medium to receive said coded coefficients at said slow synchronous data transfer rate, for putting out said coded coefficients at an asynchronous high data transfer rate, and for determining a rate buffer capacity control feed forward component in relation to said instantaneous data content of said second rate buffer memory means in further relation to its capacity so as to control the absolute quantity of data contained therein,

decoder means connected to said second rate buffer memory means for decoding said coded coefficients in accordance with the inverse of said predetermined data coding scheme;

inverse normalization multiplier means for inversely normalizing said coded transform coefficients by operation of an inverse normalization factor having a predetermined expansion ratio component, and said rate buffer capacity control feed forward component to provide expansion of said transform coefficients in relation to the instantaneous absolute quantity of data contained in said second rate buffer memory means;

inverse discrete two dimensional transformer means connected to said inverse normalization multiplier means for performing the inverse of said predetermined transformation of said expanded transform coefficients, to provide reconstituted picture elements of each subframe in line scan format.

3. In a one pass digitalized video compression and expansion system enabling digitalized video to be passed through a limited bandwidth communications path,

a compressor comprising:

a compressor input connected to receive digitalized data in line scan format and at a synchronous rate related to the video sync, said data corresponding to subframes of each frame of a television picture;

a first discrete cosine transformer means for computing the discrete cosine transform in one dimension of each said subframe;

first buffer memory means connected to said first transformer means for writing discrete cosine transform coefficients of each said subframe in a predetermined writing pattern and for reading said written coefficients in a second predetermined pattern which differs from said first predetermined writing pattern;

second discrete cosine transformer means connected to receive said read coefficients from said first buffer memory means, for computing the discrete cosine transform of each said subframe in a second dimension relative to the dimension followed by said first cosine transformer;

first diagonalization memory means connected to said second transformer means for writing discrete cosine transform coefficients put out by said second transformer means in a third predetermined pattern and for reading said written coefficients in a fourth predetermined pattern;

normalization multiplier means connected to said diagonalization memory means for multiplying the coefficients read in said fourth pattern therefrom by a normalization factor which includes an automatically variable feedback control component and a predetermined compression component and for putting out the product resulting therefrom;

encoder means connected to said normalization multiplier means for Huffman encoding the amplitude of said normalized coefficients of said product and for run length encoding of zero magnitude coefficients between coefficients greater than zero;

compressor rate buffer memory means connected to said encoder means and having a feedback connection to said normalization multiplier means, for writing said coded coefficients from said encoder means at a high asynchronous rate, for supplying said normalization multiplier means with said feedback control component which is a function of the instantaneous quantity of data in said rate buffer memory in relation to the capacity thereof, and for reading out said coded coefficients at a predetermined lower synchronous rate than as asynchronously received from said encoder means and written therein,

an output connected to said compressor rate buffer memory means and to said limited bandwidth medium; and

an expander comprising;

an expander input connected to said limited bandwidth medium to receive said synchronously sent coded coefficients;

expander rate buffer memory means connected to said expander input for writing said synchronously received coded coefficients at said predetermined transmission rate, for reading out said written coefficients at a higher asynchronous rate and for supplying an automatically variable feed forward control component which is a function of the instantaneous quantity of data in said memory in relation to the capacity thereof;

decoder means connected to said expander rate buffer memory means for decoding said Huffman and run length coded coefficients;

inverse normalization multiplier means connected to said decoder means and to said expander rate buffer memory means for multiplying said decoded coefficients by an inverse of said normalization factor which includes said automatically variable feed forward control component and the inverse of said predetermined compression component, and for putting out the product resulting therefrom;

second diagonalization memory means connected to said inverse normalization multiplier means for writing said coefficients received therefrom in a fifth predetermined pattern and for reading out said coefficients in a sixth predetermined pattern;

first inverse discrete cosine transformer means connected to said second diagonalization memory means for computing the inverse discrete cosine transform of said coefficients in said sixth pattern;

second buffer memory means connected to said first inverse cosine transformer means for writing said inversely transformed coefficients in a seventh predetermined pattern;

second inverse discrete cosine transformer means connected to said second buffer memory means for computing the inverse cosine transform for said coefficients read in said eighth pattern and for putting out reconstituted digitalized data of each subframe in the same line scan format as received at the input of said compressor.

4. A data compression system for coding, transferring, and decoding a stream of data coefficients in which some of said coefficients are of zero magnitude, said system comprising a compressor and an expander connected to the compressor through a communications path,

said compressor including:

normalization multiplier means for multiplying said data coefficients by a normalization factor which includes an automatically variable feedback control component and a predetermined compression component and for putting out the product resulting therefrom;

encoder means connected to said normalization multiplier means for Huffman coding the amplitude of said normalized coefficients of said product and for run length coding zero magnitude coefficients between coefficients greater than zero;

compressor rate buffer memory means connected to said encoder means and having a feedback connection to said normalization multiplier means, for writing said coded coefficients from said encoder means at a high asynchronous rate, for supplying said normalization multiplier means with said feedback control component which is a function of the instantaneous quantity of data in said memory in relation to the capacity thereof, and for reading out to said communications path said coded coefficients at a predetermined low synchronous transmission rate,

said expander including;

expander rate buffer memory means having an input connected to said communications path, for writing said synchronously sent coded coefficients at said predetermined rate, for reading out said written coefficients at a high asynchronous rate and for supplying an automatically variable feed forward control component which is a function of the instantaneous quantity of data in said memory in relation to the capacity thereof;

decoder means connected to said expander rate buffer memory means for decoding said Huffman and run length coded coefficients;

inverse normalization multiplier means connected to said decoder means and to said expander rate buffer memory means for multiplying said decoded coefficients by a predetermined inverse normalization factor which includes said automatically variable feed forward control component and an inverse of said predetermined compression component, and for putting out the product resulting therefrom as a stream of reconstituted data coefficients.

5. The data compression system for coding and decoding data coefficients set forth in claim 4 wherein said decoder means comprises a finite instantaneous decoder which determines each finite state from its last state and the new bit received, until a terminal state corresponding to a Huffman code is detected whereupon said Huffman code is decoded.

6. The data compression system for coding and decoding data coefficients set forth in claim 5 wherein said decoder comprises:

a serial data input,

read only memory means connected to said input, for implementing a predetermined series of finite states, some of which are terminal states reachable only through other intermediate states,

data latch means connected to said read only memory means, for latching the state put out by said read only memory means and for feeding said latched state output back to said read only memory means as a partial address to the next state, said next state address being completed with the next data bit received at said input,

first in first out buffer memory means connected to said read only memory means, for storing each said terminal state reached in said read only memory means, and for putting out said stored terminal states as decoded coefficients at a predetermined data rate.

7. The data compression system set forth in claim 6 wherein said decoder further comprises

zero run length code decoder means for decoding run length of zero coefficients,

zero coefficient generation means connected to said zero run length code decoder means for generating zero value coefficients,

output selector means connected to said first in first out buffer memory means and to said zero coefficient generator means for selecting real value coefficients and zero value coefficients to provide decoding of said coefficients.