Computer-based video compression system

• US 4,897,717 A
• Filed: 03/30/1988
• Issued: 01/30/1990
• Est. Priority Date: 03/30/1988
• Status: Expired due to Fees

• Current Assignee: Starsignal Incorporated
• Original Assignee: Starsignal Incorporated
• Inventors: Douglas, John L., Hamilton, Eric R., Widergren, Jeffrey B.
• Primary Examiner(s): Groody, James J.
• Assistant Examiner(s): Kostak, Victor R.
• Application Number:
  US07/175,074
• Time in Patent Office: 671 Days
• Field of Search: 358/133, 358/135, 358/136, 325/27, 325/122, 382/56, 364/514
• US Class Current: 375/240.07
• CPC Class Codes: H04N 11/044 involving transform coding
• 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 7/12 Systems in which the television signal is transmitted via one channel or a plurality of parallel channels, the bandwidth of each channel being less than the bandwidth of the television signal H04N7/24 takes precedence

Abstract

A computer-based video compression system for processing natural information signals, such as video signals or audio signals, for the purpose of forming a compact data file of compressed signals which can be expanded to produce the original information signals is provided by a unique subsystem in a host computer which uses a high speed signal processor to compress video images and to expand video images. The unique compression process uses segmentation and predictive techniques in conjunction with a discrete sine transform, quantization and Huffman coding to provide optimal compression. Further the segmentation and predictive techniques in conjunction with the discrete sine transform diminish the magnitude of correlated errors generated by the compression process. The compression system of this invention is further enhanced by a special circuit which transfers data between the host computer and the compression subsystem at rates greater than were previously possible.

Claims

1. A system for compression and expansion of a frame of analog information comprising:

a first subsystem comprised of an analog to digital processor and a first random access memory (RAM);

a second subsystem for compression and expansion of digital data comprising;

a second random access memory (RAM);

means for compressing data operatively connected to said second RAM;

means for expanding data operatively connected to a said second RAM;

a third RAM for storing said compressed data;

means for data management operatively connected to said first RAM, to said second RAM, and to said third RAM;

means for processing said frame of analog information;

wherein said means for processing said frame of analog information generates an analog signal representing information in said frame;

said means for processing said frame of analog information being operatively connected to said analog to digital processor so that said analog signal is an input signal to said analog to digital processor;

said analog to digital processor converting said analog signal to a frame of digital data;

said first RAM being operatively connected to said analog to digital processor so that said frame of digital data is stored in said first RAM;

said system having a first mode of operation wherein;

said means for data management transfers a selected portion of said stored digital data from said first RAM to said second RAM;

said means for compressing data retrieves said selected portion of digital data from said second RAM;

compresses said selected portion, and stores said compressed data in said second RAM;

said means for data management transfers said compressed data from said second RAM to said third RAM;

said system having a second mode of operation wherein;

said means for data management transfers a selected portion of said compressed data from said third RAM to said second RAM;

said means for expanding data retrieves said selected portion of said compressed data from said second RAM;

expands said selected portion; and

stores said expanded data in said second RAM; and

said means for data management transfers said expanded data from said second RAM to said first RAM.

2. A system as in claim 1 wherein said means for compressing data comprises:

means for retrieving a selected number N of lines comprised of discrete points from said second RAM wherein N is a selected integer.

3. A system as in claim 2 wherein said means for compressing data further comprises:

means for filtering and sampling, operatively connected to said means for retrieving said selected number of lines, to reduce the number of said selected lines and the length of said selected number of lines.

4. A system as in claim 3 wherein said means for compressing data further comprises:

means for storing said filtered and sampled lines operatively connected to said means for filtering and sampling.

5. A system as in claim 4 wherein said means for compressing data further comprises:

means for retrieving said filtered and sampled lines, operatively connected to said means for storing said filtered and sampled lines, wherein said filtered and sampled lines are retrieved from said means for storing said filtered and sampled lines upon the number of said sampled and filtered lines in said means for storing said lines being equal to N.

6. A system as in claim 5 wherein said means for compressing data further comprises:

means for dividing said filtered and sampled lines into blocks, operatively connected to said means for retrieving said filtered and sampled lines, wherein each block is comprised of N lines and each line in said block is comprised of M points.

7. A system as in claim 6 wherein said means for compressing data further comprises:

means for dividing each of said blocks into a selected point, a first one dimensional (1-D) vector, a second one dimensional (1-D) vector, and a two dimensional (2-D) vector operatively connected to said means for dividing said filtered and sampled lines so that each generated block is sequentially processed.

8. A system as in claim 7 wherein said means for compressing data further comprises:

means for compressing said selected point, operatively connected to said means for dividing each of said blocks.

9. A system as in claim 8 wherein said means for compressing data further comprises:

means for compressing said first 1-D vector and said second 1-D vector operatively connected to said means for dividing each of said blocks.

10. A system as in claim 9 wherein said means for compressing data further comprises:

means for compressing said 2-D vector operatively connected to said means for dividing each of said blocks.

11. A system as in claim 10 wherein said means for compressing said selected point comprises:

means for dividing said selected point by a first selected number and generating a second number representing the quotient of said division; and

means for coding a number in a fixed number of bits operatively connected to said means for dividing by said first selected number so that said second number is an input signal to said means for coding a number.

12. A system as in claim 11 wherein said means for dividing each of said blocks into a first 1-D vector, a second 1-D vector, a 2-D vector, and a selected point further comprises:

means for defining said first 1-D vector so that said first 1-D vector has point in said first vector is adjacent to a first selected point from a first block adjacent to said block containing said first 1-D vector; and

the last point in said first 1-D vector is adjacent to the selected point of said block containing said first 1-D vector;

means for defining said second 1-D vector so that said second 1-D vector has M-1 points wherein the first point in said second vector, is adjacent to a second selected point from a second block adjacent to said block containing said second 1-D vector and the last point in said second vector is adjacent to the selected point of said block containing said second vector; and

means for defining said 2-D vector so that said 2-D vector has N-1 points in a first direction and M-1 points in a second direction arranged in M-1 columns and N-1 rows wherein said M-1 column is adjacent to said first 1-D vector of said block containing said 2-D vector;

said N-1 row is adjacent to said second 1-D vector of said block containing said 2-D vectors, said first column is adjacent to the first 1-D vector of a second block adjacent to the block containing said 2-D vector; and

said first row is adjacent to the second 1-D vector of a first block adjacent to the block containing said 2-D vector.

13. A system as in claim 12 wherein said means for compressing said first 1-D vector and said second 1-D vector comprises:

means for generating a predicted 1-D vector, operatively connected to said means for defining said first 1-D vector, said second 1-D vector and said second RAM, wherein each point in said predicted vector is a linear estimate, calculated using said adjacent selected points, of each point in said 1-D vector and further wherein said predicted 1-D vector is stored in said second RAM;

means for generating an error vector of the difference between said 1-D vector and said predicted 1-D vector operatively connected to both said means for generating a predicted vector and said means for dividing said blocks;

means for generating a discrete sine transform vector of said error vector operatively connected to said means for forming an error vector;

means for quantization operatively connected to said means for performing a discrete sine transform wherein said vector of transform coefficients is quantized using nonuniform quantization;

means for Huffman coding of each point in said quantized vector operatively connected to said means for quantization; and

means for forming a reconstructed 1-D vector operatively connected to said means for quantization wherein said quantized vector of transform coefficients is transformed into said reconstructed 1-D vector.

14. A system as in claim 13 wherein said means for forming a reconstructed 1-D vector comprises:

means for inverse quantization operatively connected to said means for quantization wherein said vector of quantized transform coefficients is inverse quantized using a nonuniform inverse quantization so that a vector of transform coefficients is formed;

means for generating an inverse discrete sine transform operatively connected to said means for inverse quantization wherein said vector of transform coefficients is transformed to generate a reconstructed 1-D error vector;

means for retrieving a stored predicted 1-D vector, operatively connected to said second RAM; and

means for vector addition operatively connected to both said means for generating a predicted vector and said means for performing an inverse discrete sine transform vector, wherein said reconstructed 1-D error vector is added to said predicted 1-D vector to form said reconstructed 1-D vector.

15. A system as in claim 13 wherein said means for compressing said 2-D vector comprises:

means for generating a predicted 2-D vector, operatively connected to said means for defining said 2-D vector, wherein each point in said predicted vector is a bi-linear estimate, calculated using said adjacent reconstructed 1-D vectors, of each point in said 2-D vector;

means for generating an error vector of the difference between said 2-D vector and said predicted 2-D vector operatively connected to both said means for generating a predicted vector and said means for dividing said blocks;

means for generating a discrete sine transform vector of said 2-D error vector operatively connected to said means for forming an error vector;

means for quantization operatively connected to said means for performing a discrete sine transform wherein said vector of transform coefficients is quantized using nonuniform quantization;

means for ordering operatively connected to said means for quantization wherein said 2-D quantized vector of transform coefficients is ordered as a 1-D quantized vector of transform coefficients;

means for Huffman coding of each point in said 1-D quantized vector of transform coefficients operatively connected to said means for ordering.

16. A system as in claim 15 wherein said means for expanding data comprises:

means for expanding said selected point;

means for expanding said compressed first 1-D vector and compressed second 1-D vector; and

means for expanding said compressed 1-D vector representing said 2-D vector.

17. A system as in claim 16 wherein said means for expanding said selected point comprises:

means for decoding a number stored in a fixed number of bits operatively connected to said second RAM; and

means for multiplying said decoded number by said first selected number, operatively connected to said means for decoding a number, generating a third number representing the product of said multiplication.

18. A system as in claim 17 wherein said means for expanding said first 1-D vector and said second 1-D vector comprises:

means for Huffman decoding of each point of said vector, so as to generate a vector of decoded quantized transform coefficients;

means for inverse quantization operatively connected to said means for Huffman decoding wherein said vector of decoded quantized transform coefficients is inverse quantized using a nonuniform inverse quantization so that a vector of transform coefficients is formed;

means for generating an inverse discrete sine transform operatively connected to said means for inverse quantization wherein said vector of transform coefficients is transformed to generate a reconstructed 1-D error vector;

means for generating a predicted 1-D vector, operatively connected to said second RAM, wherein each point in said predicted vector is a linear estimate, calculated using said adjacent selected points of each point in said 1-D vector; and

means for generating a reconstructed 1-D vector operatively connected to both said means for generating a predicted vector and said means for performing an inverse discrete sine transform vector, wherein said reconstructed 1-D vector is the sum of said reconstructed 1-D error vector and said predicted 1-D vector.

19. A system as in claim 18 wherein said means for expanding said compressed 1-D vector, representing said 2-D vector, comprises:

means for Huffman decoding of each point of said compressed vector, so as to generate a vector of decoded quantized transform coefficient;

means for ordering said 1-D vector of decoded quantized transform coefficients as a 2-D decoded quantized transform coefficient vector operatively connected to said means for Huffman decoding;

means for inverse quantization operatively connected to said means for ordering wherein said 2-D vector of decoded quantized transform coefficient is inverse quantization using a nonuniform quantization so that a vector of transform coefficients is formed;

means for performing an inverse discrete sine transform of said vector of transform coefficients, operatively connected to said means for inverse quantization so as to generate a reconstructed 2-D error vector;

means for generating a predicted 2-D vector, operatively connected to said second RAM, wherein each point in said predicted vector is a linear estimate, calculated using said adjacent reconstructed 1-D vectors, of each point in said 2-D vector; and

means for generating a reconstructed 2-D vector operatively connected to both said means for generating a predicted vector, and said means for performing an inverse discrete sine transform wherein said reconstructed 2-D vector is the sum of said reconstructed 2-D error vector and said predicted 2-D vector.

20. A method for compressing and expanding a digitized information frame having digital points comprising:

(a) dividing said digitized information into blocks;

(b) dividing each of said blocks into a selected point, a first one-dimensional (1-D) vector, a second one-dimensional vector and a two-dimensional (2-D) vector;

(c) quantizing said selected point and storing said quantized point with a specified number of 1538 bits;

(d) using selected combinations of said selected points to form a prediction for the digital value of each point of said 1-D vectors;

(e) using selected combinations of said 1-D vectors to form a prediction for the value of each point of the 2-D vector;

(f) subtracting the predicted value of each point in a vector from the associated value for that point thereby forming an error vector for that vector;

(g) sequentially performing an invertible discrete transform on each error vector thereby forming a vector of transform coefficients;

(h) quantizing said vector of transform coefficients using a variable quantizer;

(i) ordering said 2-D vector of quantized transform coefficients as a 1-D vector;

(j) encoding each of said vectors of quantized transform coefficients for subsequent use including the steps of providing a plurality of coding tables, calculating the predicted mean value of each quantized transform coefficient, selecting a code table based upon said mean value and generating a code representing said quantized coefficient from said selected code table; and

the expansion steps comprising;

(k) inverse quantizing said selected points;

(1) decoding each 1-D vector of coded quantized transform coefficients to form a vector of quantized transform coefficients;

(m) ordering said 1-D vector representing said 2-D vector as a 2-D vector;

(n) performing an inverse quantization on each of said vectors of quantized transform coefficients thereby forming a vector of transform coefficients for each vector of quantized transform coefficient;

(o) performing an inverse discrete transform on each of said vectors of transform coefficients thereby forming an error vector for each of said vectors of transform coefficient;

(p) using selected combinations of said selected points to form a prediction for the digital value of each point of the 1-D vectors;

(q) using selected combinations of said 1-D vectors to form a prediction for the value of each point of the 2-D vector; and

(r) adding the error vector for each of the vectors to the associated predicted vector to create a reconstructed vector.

21. A method for compressing and expanding a digitized information frame having digital points comprising:

(a) sampling and filtering said digitized information to reduce the number of points in said frame;

(b) dividing said sampled and filtered digitized information into blocks;

(c) dividing each of said blocks into a selected point, a first one-dimensional (1-D) vector, a second one-dimensional vector and a two-dimensional (2-D) vector;

(d) quantizing said selected point and storing said quantized point with a specified number of bits;

(e) using selected combinations of said selected points to form a prediction for the sampled and filtered digital value of each point of said 1-D vectors;

(f) using selected combinations of said 1-D vectors to form a prediction for the sampled and filtered value to each point of the 2-D vector;

(g) subtracting the predicted value of each point in a vector from the associated sampled and filtered value for that point thereby forming an error vector for that vector;

(h) sequentially performing an invertible discrete transform on each error vector thereby forming a vector of transform coefficients;

(i) quantizing said vector of transform coefficients using a variable quantizer;

(j) ordering said 2-D vector of quantized transform coefficients as a 1-D vector;

(k) encoding each of said vectors of quantized transform coefficients for subsequent use including the steps of providing a plurality of coding tables, calculating the predicted mean value of each quantized transform coefficient, selecting a code table based upon said mean value and generating a code representing said quantized coefficient from said selected code table; and

the expansion steps comprising;

(l) inverse quantizing said selected points;

(m) decoding each 1-D vector of coded quantized transform coefficients to form a vector of quantized transform coefficients;

(n) ordering said 1-D vector representing said 2-D vector as a 2-D vector;

(o) performing an inverse quantization on each of said vectors of quantized transform coefficients thereby forming a vector of transform coefficients for each vector of quantized transform coefficients;

(p) performing an inverse discrete transform on each of said vectors of transform coefficients thereby forming an error vector for each of said vectors of transform coefficients;

(q) using selected combinations of said selected points to form a prediction for the sampled and filtered digital value of each point of the 1-D vectors;

(r) using selected combinations of said 1-D vectors to form a prediction for the sampled and filtered value of each point of the 2-D vector;

(s) adding the error vector for each of the vectors to the associated predicted vector to create a reconstructed vector; and

(t) interpolating among the digital points in said reconstructed vectors so as to form a frame having a selected number of points.