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

• US 4,394,774 A
• Filed: 06/26/1981
• Issued: 07/19/1983
• 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): Psitos, Aristotelis M.
• Application Number:
  US06/277,981
• Time in Patent Office: 753 Days
• Field of Search: 358/12, 358/13, 358/133, 358/136, 358/138, 364/514, 364/515, 364/576, 364/582, 340/347 DD, 382/56, 375/31, 179/15.55 R
• US Class Current: 382/250
• 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/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 and expansion system and its methods for compressing and expanding 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 with a minimum redundancy coding scheme 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 in reverse 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 data compression method for adaptive coding, transferring, and decoding a stream of data coefficients in which some of said coefficients are of zero magnitude, said method comprising compression steps prior to transfer through a limited bandwidth medium and expansion steps following such transfer, said compression steps comprising:

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

minimum redundancy coding of the amplitude of said normalized coefficients and including run length coding of zero magnitude coefficients between coefficients greater than zero;

writing said minimum redundancy and run length coded coefficients into a compressor buffer memory at a high asynchronous rate, deriving said feedback control component which is a function of the instantaneous quantity of data in said memory in relation to the capacity thereof, and reading out to said limited bandwidth medium said coded coefficients at a predetermined low synchronous transmission rate,

said expansion steps comprising;

receiving said coder coefficients from said limited bandwidth medium at said low synchronous transmission rate;

writing said coded coefficients rate into an expander rate buffer memory, reading out of said memory said written coefficients at a high asynchronous rate and supplying an automatically variable feed forward control component which is a function of the instantaneous quantity of data in said expander buffer memory in relation to the capacity thereof;

decoding said minimum redundancy and run length coded coefficients;

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 putting out the product resulting therefrom as a stream of reconstituted data coefficients.

2. The method set forth in claim 1 wherein said step of deriving said feedback control component in said compression steps includes the further step of generating said rate buffer feedback control component nonlinearly in accordance with a predetermined capacity control damping factor so that said compressor buffer memory may be of less storage capacity than otherwise and not be subject to data overflow in accordance with said predetermined damping factor.

3. 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 rate buffer capacity control feedback component and a predetermined compression component and for putting out the product resulting therefrom;

encoder means connected to said normalization multiplier means including coding means for providing variable length, substantially derived, minimum redundancy coding of amplitude coefficients and run length coding of zero amplitude coefficients for further compression and transfer through said communications path to said expander,

compressor rate buffer memory means connected to said encoder means and having a feedback connection to said normalization mulitplier means, for writing said coded coefficients from said encoder means at a high asynchronous rate, for supplying said normalization multiplier means with said rate buffer capcity control feedback 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 cooled coefficients at a predetermined low synchronous transmission rate, said rate buffer memory means further including means for generating said rate buffer capacity control feedback component nonlinearly in accordance with a predetermined capacity control damping factor so that said rate buffer memory means may be of less capacity than otherwise and not be subjected to data overflow in accordance with said predetermined damping factor,

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 minimum redundance and zero run length coded coefficients in accordance with an inverse of said predetermined data coding scheme;

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.

4. A data compression system for coding, transferring through a limited bandwidth communications path and decoding color television broadcast signal in real time, including a compressor, and an expander, wherein said processor comprises:

audio encoding and compression means for compressing an audio component of said broadcast signals and for providing a compressed digital data stream thereof,

video separator means for separating a video component of said broadcast signals into chrominance and luminance portions,

chrominance encoder means connected to said separator means for encoding said chrominance portion to provide a digital data stream theoref;

transformer means connected to said separator means for performing predetermined transformations to the picture elements of said luminance portion to provide transform coefficients thereof,

normalization multiplier 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 coding means for providing a variable length, statistically derived, minimum redundancy coding of amplitude coefficients and run length coding of zero amplitude coefficients for further compression thereof,

rate buffer memory means connected to said encoder means for storing said coded coefficients asynchronously at a high data transfer rate, for putting out said coded coefficients at a slow data transfer rate capable of passing through said limited bandwith 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 multiplier 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,

multiplexer means connected to said audio encoding means, said chrominance encoder means, and said rate buffer memory means, for multiplexing said digital data streams of audio, chrominance portion, and compressed luminance portion into a single composite data stream for transmission through said limited bandwidth medium,

and wherein said expander comprises;

demultiplexer means for demultiplexing said composite data stream into said compressed luminance and chrominance portions and said audio component,

chrominance decoder means connected to said demultiplexer means for decoding said chrominance portion into a chrominance signal,

second rate buffer means connected to said demultiplexer means for receiving said coded coefficients at said slow 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 an inverse of said predetermined data coding scheme;

inverse normalization multiplexer means for inversely normalizing said coded transform coefficients by operation of an inverse normalization factor having a predetermined expansion ratio component, and said second 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 transformer means connected to said inverse normalization multiplier means for performing inverses of said predetermined transformations of said expanded transform coefficients, to provide reconstituted said luminance portion,

video combiner means connected to said inverse transformer means and to said chrominance decoder means for combining and putting out said expanded and decoded luminance portion and chrominance portion as a single composite color video signal, and

audio expander and decoder means connected to said demultiplexer means for expanding, decoding and putting out said audio component as an audio signal.

5. A data compression method for adaptive coding a stream of data coefficients in which some of said coefficients are of zero magnitude, and transferring said adaptively coded coefficients through a limited bandwidth medium, comprising the steps of:

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

encoding said normalized transform coefficients in accordance with said predetermined data coding scheme including variable length, statistically derived, minimum redundancy coding of amplitude coefficients and including run length coding of zero amplitude coefficients for further compression and transfer through said limited bandwidth medium

writing said minimum redundancy and run length coded coefficients into a compressor buffer memory at a high asynchronous rate and deriving said feedback control component as a function of the instantaneous quantity of data in said memory in relation to the capacity thereof; and

,

reading out to said limited bandwidth medium said coded coefficients at a predetermined low synchronous transmission rate.

6. A method for one pass compression and transfer at a slow synchronous rate through a limited bandwidth medium of digitalized television images in real time, including the steps of:

performing predetermined transformations of the picture elements of said images to provide transform coefficients thereof,

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

encoding said normalized transform coefficients in accordance with said predetermined data coding scheme including variable length, statistically derived, minimum redundancy coding of amplitude coefficients and including run length coding of zero amplitude coefficients for further compression and transfer through said limited bandwidth medium,

storing said coded coefficients in a rate buffer memory asynchronously at a high data transfer rate and adaptively determining said rate buffer capacity control feedback component in relation to the instantaneous data content of said rate buffer memory in further relation to its data storage capacity, thereby for controlling at said normalization step the absolute quantity of data resulting therefrom so that said rate buffer memory is never completely emptied and is never completely filled, and

putting out to said limited bandwidth medium said coded coefficients at a slow data transfer rate capable of passing through said medium.

7. A data expansion method for adaptive decoding of a stream of data coefficients which have been compressed in accordance with a predetermined compression component which includes minimum redundancy coding of amplitude coefficients and run length coding of zero amplitude coefficients and which have been received from a limited bandwidth medium at a low synchronous transmission rate, comprising the steps of:

writing said compressed data coefficients into an expander rate buffer memory and generating an automatically variable feed forward control component which is a function of the instantaneous quantity of data in said expander rate buffer memory in relation to the capacity thereof;

reading out of said memory said written coefficients at a high asynchronous data rate;

decoding said minimum redundancy and run length coded coefficients;

multiplying said decoded coefficients by a predetermined expansion normalization factor which includes said feed forward control component and an inverse of said predetermined compression component, and putting out the product resulting therefrom as a stream of reconstituted data coefficients.

8. A data compression system for coding a stream of dat coefficients in which some of said coefficients are of zero magnitude and transferring said coded coefficients through a communications path, said compression system 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 encoding said normalized coefficients including coding means for providing variable length, statistically derived, minimum redundancy coding of amplitude coefficients and run length coding of said zero amplitude coefficients for further compression and transfer through said communications path,

compressor rate buffer memory means connected to said encoder means and having a feedback connection to said normalization multiplier meand, for writing said coded coefficients from said encoder means at a high asynchronous rate, for generating and supplying said normalization multiplier means with said feedback control component as 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.

9. A system for one pass expansion of digitalized video images in which picture elements have been transformed pursuant to a predetermined transformation and then compressed to data coefficients in accordance with a predetermined data coding scheme which includes variable length, statistically derived minimum redundancy coding of amplitude coefficients and run length coding of zero amplitude coefficients, said transformed and compressed data coefficients being received from a limited bandwidth medium, said system comprising:

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

decoder means connected to said expansion rate buffer memory means for decoding said data coefficients in accordance with an inverse of said predetermined data coding scheme,

inverse normalization multiplier means for inversely normalizing said decoded data coefficients by operation of an inverse normalization factor having a predetermined expansion ratio component and said expansion 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 expansion rate buffer memory means;

inverse transformer means connected to said inverse normalization multiplier means for performing inverses of said predetermined transformations of said expanded transform coefficients, to provide reconstituted picture elements of digitalized video images.

10. In a one pass digitalized video compression 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;

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 transformer means connected to receive said read coefficients from said 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 means;

first diagonalization memory means connected to said second transformer means for writing descrete 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;

ecoder means connected to said normalization mulitplier means for encoding said normalized coefficients by providing a variable length, statistically derived minimum redundancy coding of amplitude coefficients and run length coding of zero amplitude 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 as a function of the instantaneous quantity of data in said rate buffer memory means 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; and

,

an output connecting said rate buffer memory means to said limited bandwidth medium.

11. In a one pass digitalized video expansion system for data corresponding to subframes of video which has been subjected to discrete cosine transformation in two spatial dimensions and further subjected to predetermined data compression including a predetermined compression component and further including variable length, minimum redundancy coding of amplitude coefficients and run length coding of zero amplitude coefficients lying between said amplitude coefficients and which has then passed through a limited bandwidth medium, an expander comprising:

an expander input connected to said limited bandwidth medium for receiving said coefficients at a predetermined low synchronous data rate to said medium,

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 data storage capacity thereof,

decoder means connected to said expander rate buffer memory means for decoding said minimum redundancy coded amplitude coefficients and said run length encoded zero amplitude 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 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,

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

first inverse discrete cosine transformer means connected to said diagonalization memory means for computing the inverse discrete cosine transform of said coefficients in a third pattern,

second buffer memory means connected to said first inverse discrete cosine transformer means for writing said inversely tranformed coefficients in a fourth 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 a fifth pattern and for putting out reconstituted digitalized data of each subframe in line scan format.