Home
Patent Search
IMT Blog
REGISTER
|
SIGN IN
United States Patent
4951139
Hamilton , ; et al.
August 21, 1990
Title
Computer-based video compression system
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.
Inventors:
Hamilton; Eric R.
(Cupertino,
CA
)
, Douglas; John L.
(Santa Cruz,
CA
)
, Widergren; Jeffrey B.
(Saratoga,
CA
)
Assignee:
StarSignal, Inc.
(San Jose,
CA
)
Appl. No.:
430748
Filed:
November 1, 1989
Current U.S. Class:
375/240.07
375/245
Field of Search:
358/135,136,133,13 375/25,27,122
U.S. Patent Documents
4774574
September 1988
Daly et al.
4816913
March 1989
Harney et al.
Other References
Paul Farrelle et al., "Recursive Block Coding-A New Approach To Transform Coding", IEEE, vol. Com-34, No. 2, Feb. 1986, pp. 161-179. .
P. Yip et al., "A Fast Computational Algorithm for the Discrete Sine Transform", IEEE, vol. Com-28, No. 2, Feb. 1980, pp. 305-307..~
Primary Examiner:
Groody; James J.
Assistant Examiner:
Kostak; Victor R.
Attorney, Agent or Firm:
Lyon & Lyon
Parent Case Text
CROSS REFERENCE TO RELATED APPLICATION
This application is a continuation application of U.S. Patent Application Ser. No. 07/175,074 entitled "Computer-Based Video Compression System ", filed on March 30, 1988 which issued as U.S. Pat. No. 4,897,717 on 1/30/90.
Claims
We claim:
1. A system for compression and expansion of digital data, said digital data consisting of lines of discrete points, comprising:
random access memory means (RAM);
means, operatively coupled to said RAM, for compressing data; and
means, operatively coupled to said RAM, for expanding compressed data;
wherein said means for compressing data further comprises:
means for retrieving a selected portion of N of said lines comprised of discrete points from said RAM wherein N is a selected integer;
means, operatively coupled to said retrieving means, for generating an error vector for a portion of N lines;
means, operatively coupled to said error vector generating means, for transforming data thereby forming a vector of transform coefficients;
means, operatively coupled to said compression means, for variable quantization of each point in a vector of transform coefficients thereby forming a vector of quantized transform coefficients;
means, operatively coupled to said variable quantizing means, for encoding each point in a vector of quantized transform coefficients thereby forming a vector of compressed data; and
means, operatively coupled to said encoding means, for storing compressed data in said RAM.
2. A system as in claim 1 wherein said retrieving means further comprises:
means for filtering and sampling to reduce the number of said selected lines and the length of said selected number of lines.
3. A system as in claim 2 wherein said retrieving means further comprises:
means, operatively coupled to said means for filtering and sampling, for storing said filtered and sampled lines.
4. A system as in claim 3 wherein said retrieving means further comprises:
means, operatively coupled to said means for storing said filtered and sampled lines, for retrieving 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.
5. A system as in claim 4 wherein said retrieving means further comprises:
means, operatively coupled to said means for retrieving said filtered and sampled lines, for dividing said filtered and sampled lines into blocks wherein each block is comprised of N lines, each line in said block is comprised of M points and each block is sequentially compressed.
6. A system as in claim 5 wherein said error vector generating means further comprises:
means, operatively coupled to said means for dividing said filtered and sampled lines, 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 wherein said selected point, said first and second 1-D vectors, and said 2-D vector are each a different portion of said N lines.
7. A system as in claim 6 wherein said transform means further comprises:
means, operatively coupled to said block dividing means, for dividing a selected point by a first selected number and generating a second number representing the quotient of said division.
8. A system as in claim 7 wherein said encoding means further comprises:
means, operatively coupled to said means for dividing by a first selected number, for coding a number in a fixed number of bits wherein said second number is coded in said fixed number of bits.
9. A system as in claim 6 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 N-1 points wherein the first 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.
10. A system as in claim 6 wherein said error vector generating means further comprises:
means, operatively coupled to block dividing means and to said RAM, for generating a predicted 1-D vector wherein for each 1-D vector processed, each point in said predicted vector is a linear estimate of each point in said 1-D vector and further wherein said predicted 1-D vector is stored in said RAM.
11. A system as in claim 10 wherein said error vector generating means further comprises:
means, operatively coupled to both said means for generating a predicted 1-D vector and said means for dividing said blocks, for forming the difference between a 1-D vector and a predicted 1-D vector thereby forming said error vector for said 1-D vector.
12. A system as in claim 11 wherein said said data transforming means further comprises:
means for generating a discrete 1-D sine transform of a 1-D error vector thereby generating a 1-D vector of transform coefficients.
13. A system as in claim 12 wherein said variable quantization means further comprises:
means, operatively coupled to said means for generating a discrete 1-D sine transform, for nonuniform quantization of a 1-D vector of transform coefficients thereby forming a 1-D vector of nonuniformly quantized transform coefficients.
14. A system as in claim 13 wherein said encoding means further comprises:
means, operatively coupled to said means for nonuniform quantization, for Huffman coding of each point in a quantized vector thereby forming a compressed vector of nonuniformly quantized transform coefficients.
15. A system as in claim 14 wherein said error vector generating means further comprises:
means, operatively coupled to said nonuniform quantization means, for forming a reconstructed 1-D vector wherein said vector of nonuniformly quantized transform coefficients is transformed into a reconstructed 1-D vector.
16. A system as in claim 15 wherein said means for forming a reconstructed 1-D vector further comprises:
means for inverse quantization wherein a vector of nonuniformly quantized transform coefficients is inverse quantized using a nonuniform inverse quantization so that a vector of transform coefficients is formed;
means, operatively coupled to said means for inverse quantization, for generating an inverse discrete 1-D sine transform wherein said vector of transform coefficients is transformed to generate a reconstructed 1-D error vector;
means, operatively coupled to said RAM, for retrieving a stored predicted 1-D vector wherein said retrieving means retrieves the stored predicted 1-D vector corresponding to the 1-D vector being processed; and
means, operatively coupled to both said means for generating a predicted vector and said means for performing an inverse discrete 1-D sine transform, for vector addition wherein said reconstructed 1-D error vector is added to said predicted 1-D vector to form said reconstructed 1-D vector.
17. A system as in claim 6 wherein said error vector generating means further comprises:
means, operatively coupled to block dividing means and to said RAM, for generating a predicted 2-D vector wherein for each 2-D vector processed, each point in said predicted vector is a bi-linear estimate of each point in said 2-D vector;
means, operatively coupled to both said means for generating a predicted 2-D vector and said means for dividing said blocks, for forming the difference between a 2-D vector and a predicted 2-D vector thereby forming said error vector for said 2-D vector.
18. A system as in claim 17 wherein said said data transforming means further comprises:
means for generating a discrete 2-D sine transform of a 2-D error vector thereby generating a 2-D vector of transform coefficients.
19. A system as in one claim 18 wherein said variable quantization means further comprises:
means, operatively coupled to said means for generating a discrete 2-D sine transform, for nonuniform quantization of a 2-D vector of transform coefficients thereby forming a 2-D vector of nonuniformly quantized transform coefficients.
20. A system as in claim 19 wherein said encoding means further comprises:
means, operatively coupled to said means for nonuniform quantization, for ordering wherein said 2-D vector of nonuniformly quantized transform coefficients is ordered as a 1-D vector and
means, operatively coupled to said means for ordering, for Huffman coding of each point in a 1-D vector of nonuniformly quantized transform coefficients thereby forming a compressed 1-D vector representing said 2-D vector.
21. A system as in claim 1 wherein said means for expanding compressed data further comprises:
means, operatively coupled to said RAM, for retrieving compressed data in said RAM wherein said means retrieves compressed selected points, and compressed 1-D vectors of coded nonuniformly quantized transform coefficients;
means, operatively coupled to said retrieving means, for decoding compressed data wherein each point in said compressed 1-D vector is decoded thereby forming a vector of quantized transform coefficients;
means, operatively coupled to said decoding means, for inverse variable quantization wherein each point in said vector of quantized transform coefficients is inverse quantized thereby forming a vector of transform coefficients;
means, operatively coupled to said inverse variable quantization means, for inverse transformation of data wherein said vector of transform coefficients is transformed into an error vector; and
means, operatively coupled to said inverse transform means, for generating reconstructed data wherein said error vector is converted to a vector of reconstructed data.
22. A system as in claim 21 wherein said decoding means further comprises:
means for decoding a number stored in a fixed number of bits wherein said compressed selected point is decoded.
23. A system as in claim 22 wherein said inverse transform means further comprises:
means, operatively coupled to number decoding means, for multiplying said decoded number by a first selected number and generating a second number representing the product of said multiplication wherein said decoded selected point is processed and said second number represents a reconstructed selected point.
24. A system as in claim 23 wherein said decoding means further comprises:
means for Huffman decoding of each point in a compressed 1-D vector wherein said compressed 1-D vector of coded nonuniformly quantized transform coefficients is converted to a 1-D vector of nonuniformly transform coefficients.
25. A system as in claim 24 wherein said inverse variable quantization means further comprises:
means, operatively coupled to said Huffman decoding means, for nonuniform inverse quantization of a 1-D vector of nonuniformly quantized transform coefficients wherein said 1-D vector of nonuniformly quantized transform coefficients is converted to a 1-D vector of transform coefficients.
26. A system as in claim 25 wherein said inverse transformation means further comprises:
means, operatively coupled to said nonuniformly inverse quantization means, for generating an inverse discrete 1-D sine transform wherein said 1-D vector of transform coefficients is transformed into a 1-D error vector.
27. A system as in claim 26 wherein said reconstructed data generating means further comprises:
means, operatively coupled to said RAM, for generating a predicted 1-D vector wherein for each 1-D vector processed, each point in said predicted vector is a linear estimate of each point in said 1-D vector;
means, operatively coupled to both said means for generating a predicted 1-D vector and said inverse transform means, for forming the sum of said 1-D error vector and said predicted 1-D vector thereby forming a 1-D reconstructed vector.
28. A system as in claim 21 wherein said decoding means further comprises:
means for Huffman decoding of each point in said 1-D vector of coded nonuniformly quantized transform coefficients representing a 2-D vector, thereby forming a 1-D vector of nonuniformly quantized transform coefficients; and
means, operatively coupled to said Huffman decoding means, for reverse ordering wherein said 1-D vector of nonuniformly quantized transform coefficients is ordered as a 2-D vector.
29. A system as in claim 28 wherein said inverse variable quantization means further comprises:
means, operatively coupled to said reverse ordering means, for inverse nonuniform quantization wherein said 2-D vector of nonuniformly quantized transform coefficients is converted to a 2-D vector of transform coefficients.
30. A system as in claim 29 wherein said inverse transformation means further comprises:
means, operatively coupled to said inverse nonuniformly quantization means, for performing an inverse discrete 2-D sine transform wherein said 2-D vector of transform coefficients is transformed to a 2-D error vector.
31. A system as in claim 30 wherein said error vector generating means further comprises:
means, operatively coupled to said RAM, for generating a predicted 2-D vector wherein for each 2-D vector processed, each point in said predicted vector is a bilinear estimate of each point in said 2-D vector;
means, operatively coupled to both said means for generating a predicted 2-D vector and said inverse transform means, for forming the sum of a 2-D error vector and a predicted 2-D vector thereby forming a reconstructed 2-D vector.
Description
BACKGROUND OF THE INVENTION
1. Field of the Invention
This invention relates to information signal processing in general and in particular to the field of 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 reproduce the information in the original information signals.
2. Description of the Prior Art
Video data compression in recent years has achieved increasing importance because of the advances in communications and the general increase in transfer of information. Typically, video data is comprised of video images and each video image is a frame comprised of individual picture elements, pixels. The pixels form lines, sometimes called rows, in the horizontal direction and columns in the vertical direction. The number of pixels per line and the number of lines per frame depends upon both the video format used to represent the frame and the rate at which the frame was digitized.
To digitize a frame containing a black-and-white image, each pixel in the frame is normally assigned a number between 0 and 255, for example, where 0 would mean the pixel was completely black, and 255 would mean that the pixel was completely white. Numbers between 0 and 255 represent the various shades of gray. Thus, to digitally represent such an image, each pixel requires eight bits to represent the number corresponding to the gray-level of the pixel.
For a color image where each pixel has a red component (R), a green component (G), and a blue component (B) and each component has an intensity that varies from 0 to 255, three times more information is required to represent the color image than a black-and-white image having the same number of pixels. Accordingly, any system, which utilizes numerous digitized colored pictures or numerous digitized black-and-white pictures, processes formidable amounts of data. For example, in the transmission of a black-and-white television picture, data rates for unprocessed digitized television signals typically require a communications channel with a bandwidth greater than 40 megabytes per second.
Several processes have been developed for reducing the quantity of data required to represent a video image. These processes compress the data representing the image. The compressed data is usually transmitted over a data channel and when the compressed data is received it is expanded to recreate a likeness of the original image.
Two general methods have been developed for compression of video data, (1) spatial or time domain compression, and (2) transform domain compression. Transform domain compression, sometimes called transform domain coding, typically results in better compression performance but is considerably more difficult to implement in real-time hardware. In transform domain coding, the original set of binary data representing the pixels is processed by an invertible mathematical transform so that the original data, which are correlated in the space domain or time domain, are mapped into a new coordinate system, called the transform or generalized frequency domain, where the data are much less correlated.
The mathematical transforms are chosen so that they preserve the signal energy of the original image in the transform domain, but the energy is concentrated in a relatively few samples which are usually the lower frequency samples. Accordingly, compression can be achieved by considering these high energy samples to be sufficient for reconstruction after transmission storage or processing. Alternatively, as described below, the transform coefficients are encoded using methods developed in information theory so that data representing the original picture is first compressed by the transform which concentrates the data in fewer points and then the transformed data are further compressed by quantization and encoding of the transform coefficients. To recreate the original image, the encoded transform coefficients are decoded, inverse quantized, and inverse transformed. The quality of the reconstructed image is directly dependent on the errors introduced by the transform, quantization, and the encoding-decoding processes.
The Karhunen-Loeve (KL) transform is usually identified as the optimal transform for decorrelating the data in the transform domain and packing a maximum energy in a given number of samples. However, there are two generally recognized problems with the KL transform. One, the KL transform is unique for only one class of signals, and two, a fast KL transform algorithm is not known. Accordingly, alternative mathematical transforms have been investigated. The discrete cosine transform is generally used for transform domain coding of video images because a fast discrete cosine transform algorithm exists and the cosine transform has been shown to be virtually identical to the KL transform for numerous practical conditions.
In the traditional discrete cosine transform compression methods, the video frame is divided into a series of nonoverlapping blocks. Typically, a block is sixteen pixels wide and sixteen pixels high. The discrete cosine transform of a two dimensional block is implemented by transforming the digital data for the pixels in a first direction and then transforming in the second direction. The resulting cosine transform coefficients include a single term which represents the average signal energy in the block, sometimes referred to as the DC term, and a series of terms, sometimes referred to as the AC terms, which represent the variation of the signal energy about the DC component for the block.
A quantizer is used to reduce the range of the cosine transform coefficients. A quantizer is a mapping from the continuous variable domain of transform coefficients into the domain of integers. Commonly used is the uniform quantizer, which may be specified by a number. The number is divided into each transform coefficient with the resulting quotient rounded to the nearest integer. The quantized cosine transform coefficients are then encoded for transmission over a data channel.
There are two basic coding techniques, adaptive coding techniques and nonadaptive coding techniques. With an adaptive coding technique, the transform, quantization, and coding of the video image produce compressed data at a variable rate, but the transmission of the compressed data representing the video image over a communication channel is at a fixed rate. Therefore, the adaptive compression system employs a buffer which interfaces the variable rate compression system with the fixed rate communication channel. The buffer is typically designed to provide variable feedback of compression parameters so that the coding of the transform coefficients is adapted to the conditions in the buffer. This form of adaptive coding limits the quality of the compression because the process is governed by the state of the buffer and not by considerations which provide optimal compression.
Irrespective of either the coding scheme for the discrete cosine transform coefficients or the quantization method, the methods or processes which utilize a discrete cosine transform generally suffer from a common problem. For each block compressed and reconstructed, utilization of the cosine transform results in greater pixel error at the edges of the block with the error decreasing towards the center of the block. Since each of the blocks is coded independently, the distortion introduced by the compression scheme using the cosine transform is discontinuous at each block boundary. Highly correlated errors, that is one error on top of the other such as those introduced by the cosine transform at the block boundaries, stand out and are highly visible to the human eye.
Farrelle and Jain suggested in "Recursive Block Coding --A New Approach to Transform Coding," IEEE Transactions on Communications, Vol. COM-34, No. 2, pp. 161-179, Feb. 1986, a new method for compression of image data which is designed to minimize the highly correlated errors which occur at block edges using conventional cosine transform coding. In this method, referred to as Recursive Block Coding, each block is further subdivided into corner, edge and interior elements which are coded separately. Previously coded elements within the block are combined with elements from adjacent blocks to form a prediction of all pixels in the next block element to be coded. This prediction is used to reduce the complexity of the data to be compressed and to reduce error at the edge pixels. Farrelle and Jain show that the theoretical and practical performance of the recursive block coding is superior to the conventional block by block discrete cosine transform methods and the block effect distortion is substantially reduced. In recursive block coding, the use of previously coded block elements for prediction yields a residual signal which has relatively small correlated errors at block boundaries. Farrelle and Jain, using computer simulation, developed their method using a discrete sine transform with uniform quantizers and nonadaptive zonal transform coefficient coding techniques. Thus, while the Recursive Block Coding technique combined with the discrete sine transform minimizes the correlated boundary error problems of the prior art discrete cosine transform methods, the method of Farrelle and Jain is limited by the use of uniform quantizers and nonadaptive coding techniques. Further, demonstration of the method does not establish that the method is suitable for a video compression system that must operate with constraints on the time, memory and storage space available for compression.
The present invention overcomes the problems of the prior art by providing a system for developing data bases of compressed video images, as well as data bases of other analog data that are amenable to digitization, which eliminates the boundary errors of the discrete cosine transform methods and utilizes both nonuniform quantization and adaptive coding techniques to achieve optimal compression while maintaining image quality. The compression system provides a fast means of data compression that can be implemented in a wide variety of applications.
SUMMARY OF THE INVENTION
A computer-based video compression system incorporating the principles of the present invention includes a unique subsystem, a compression/expansion system, which uses a high speed signal processor to compress video images and to expand compressed video images. The compression process and the expansion process used by the high speed signal processor provide optimal compression and expansion of the video image. In the compression/expansion system (compression system) of the present invention, a color video camera generates analog signals that represent a color video image. The analog signals are provided to a frame grabber subsystem of the computer-based video compression system which filters the analog signals and generates a frame of digital data which represents a still image. The frame of digital data is made up of lines of discrete pixels. The frame is stored in a random access memory (RAM) of the frame grabber subsystem.
A selected portion of the digital data in the RAM of the frame grabber subsystem is moved by a computer program, running in the computer containing both the frame grabber subsystem and the compression subsystem, to a data RAM of the compression system. After the data is loaded in the data RAM of the compression system, the signal processor of the compression subsystem compresses the data and stores the compressed data back in the data RAM of the compression system. The processed data in the data RAM of the compression system is moved by the program in the host computer to a storage area in the memory of the host computer.
In an alternative mode of operation, compressed data is expanded by the signal processor and the reconstructed data is stored in the RAM of the frame grabber system. The reconstructed data in the RAM of the frame grabber is subsequently displayed on a video monitor.
The function performed by the signal processor of the compression system is determined by the computer program in the host computer. The computer program loads either the compression process program code or the expansion process program code from the memory of the host computer into the program RAM of the compression system and then initializes the compression system so that it is ready to either perform the expansion or the compression process. After initialization of the compression system and the transfer of the first portion of the frame from the RAM of the frame grabber to the data RAM of the compression system, the program in the host computer issues a command to the compression system which directs the compression system to process the data in the data RAM of the compression system.
After each portion of data representing the video image in the data RAM of the compression system is compressed, the host computer moves the compressed data from the data RAM of the compression system to the memory of the host computer. The compression process is applied on each subsequent portion of data transferred to the data RAM of the compression system from the data RAM of the frame grabber until the entire frame is compressed and stored in the memory of the host computer.
In an expansion process, after each portion of data is expanded, the host computer program moves the expanded data from the data RAM of the compression system to the RAM of the frame grabber system. When a complete frame of reconstructed data is present in the frame grabber subsystem, the frame is transferred to a digital-to-analog converter which changes the frame of reconstructed digital data to analog signals which are then supplied to a video display device.
The compression process implemented by the signal processor in the compression system first converts the red, green and blue pixel data from the frame grabber to luminance pixel data (Y) and chrominance component pixel data (I,Q). The luminance data is processed by a quality retention process which first divides the portion of luminance data in the RAM of the compression system into blocks 16 pixels wide and 16 lines high. Each block is further subdivided into an interior block vector, a right edge vector, a lower edge vector and a corner pixel. The corner pixel for each block is coded with a specific number of bits and stored in the memory of the compression system.
Next the quality retention process forms a linear estimate of the right edge vector using linear interpolation between the corner pixel of the block being processed and the corner pixel of the block immediately above the block being processed. The predicted right edge vector is then subtracted from the right edge vector to form a right edge error vector. The right edge error vector is processed by a discrete sine transform and the resulting vector of transform coefficients is quantized using a nonuniform quantizer. The nonuniform quantizer was selected such that quantized coefficients are peaked about zero because this quantization improves the coding efficiency. The vector of quantized transform coefficients is coded using an adaptive vector coder, described below.
The quantized coefficients are then reconstructed (inverse quantized), processed by an inverse discrete sine transform, added to the predicted right edge vector, and stored back in the data RAM of the compression system, overwriting the original right edge vector.
The lower edge vector of the block is processed in a manner similar to that of the right edge vector. However, to form the linear estimate for the predicted lower edge vector, the corner pixel of the block being processed and the corner pixel of the block immediately to the left of the block being processed are used to form the linear estimate. As with the right edge vector, the lower edge vector is inverse processed and the reconstructed values are stored in RAM such that the original values are overwritten.
The predicted interior block vector is generated using the reconstructed lower edge vector of the block being processed, the reconstructed lower edge vector of the block immediately above the block being processed, the reconstructed right edge vector of the block being processed, and the reconstructed right edge vector of the block immediately to the left of the block being processed. The four edge vectors are used to form a bilinear prediction of each pixel in the interior block vector. Again, the predicted value for each pixel in the predicted interior block vector is subtracted from each point in the interior block vector to form an interior error block vector. The interior error block vector is processed using a two-dimensional discrete sine transform and then quantized. The two-dimensional vector of quantized transform coefficients is compressed by the same process used for the lower edge vector and the right edge vector except that a table is employed to designate the order in which the transform coefficients are coded, effectively reordering the block into a one-dimensional vector.
After the corner pixel, the right edge vector, the lower edge vector and the interior block vector are compressed for each block in the luminance strip of data, the compressed luminance data for the strip is moved from the data memory of the compression system by the program in the host computer to a temporary buffer in the memory of the host computer.
The two chrominance components in the first strip of data are each filtered and sampled using a low-pass (sin X)/X finite impulse response filter in both directions on a 4:1 basis so that the sixteen line strip of data is reduced to a four line strip of data. The filtered and sampled data are stored in the data memory of the compression system.
The compression of the luminance data and filtering and sampling of the chrominance data continues until four strips of data have been processed. After the fourth strip of luminance data is processed and moved to the temporary buffer in the memory of the host computer, the memory of the compression system contains a 16 line strip of data for each of the chrominance components. Thus, each of the chrominance components are compressed in the same manner as the luminance component, and after compression are moved to permanent compressed image storage in the memory of the host computer. When both chrominance components are stored in the memory of the host computer, the host computer moves the four strips of coded luminance data from the temporary buffer to the permanent compressed image storage area. This process is repeated until all lines in the memory of the frame grabber have been processed.
The adaptive vector coder of this invention, which is used to code all the vectors in a block, uses six empirically generated Huffman coding tables to code each one-dimensional vector of quantized transform coefficients. For each coefficient in the vector, a predicted mean is calculated. The predicted mean is used to select a Huffman code table. A table of predicted mean thresholds is employed to designate the Huffman code table used for a particular predicted mean value. These thresholds are chosen such that for a typical distribution of predicted mean values there is an equal probability of selecting any one of the six Huffman tables.
The expansion process of the present invention is the inverse process of each of the steps of the compression process. To initiate the expansion, the host computer moves a strip of data from the permanent compressed image storage to the data RAM of the compression system. For each block of data the corner pixel is first decoded, then the right edge vector, the lower edge vector and the interior block vector are sequentially decoded. This is necessary because the corner pixel is used with the corner pixel of adjacent blocks to form the predicted right edge vector and the predicted lower edge vector, as previously described. The predicted vector is used to generate the associated reconstructed vector. The reconstructed right edge vectors and lower edge vectors are used, as previously described, to form the predicted interior block vector which in turn is used in reconstruction of the interior block vector.
In the first step of the expansion process the adaptive vector decoder decodes each of the coded quantized transform coefficients. The adaptive vector decoder uses six decoding tables, which are based on the six empirically generated Huffman coding tables, and again a predicted mean is used to select the table for decoding of each coefficient. After a vector is decoded, an inverse quantization process generates a vector of sine transform coefficients. Then an inverse discrete sine transform operates upon the vector of sine transform coefficients to generate an error vector.
The predicted vector for the vector being decoded is formed in the same manner as in the quality retention process and the error vector and the predicted vector are added together to form the reconstructed vector. After each of the blocks in a strip is reconstructed and stored in data memory of the compression system, bilinear interpolation is used to generate any points removed by filtering and sampling in the compression process.
After the strip of data is reconstructed in the memory of the compression system, the strip is passed through a YIQ to RGB converter to generate the red, green and blue pixel data. The red, green and blue pixel data are then transferred from the data memory of the compression system to the memory of the frame grabber.
To enhance the speed of the compression and expansion process in the IBM PC XT and IBM PC XT compatible computers, a special circuit was developed which causes the IBM PC XT to transfer data at rates of approximately 900K bytes per second. This transfer rate is more than twice the normal IBM PC XT transfer rate.
While the preferred embodiment of this invention compresses and expands color video images, the compression system and the compression/expansion process of this invention can be used for any information data source such as audio or video signals.
The compression/expansion process of this invention provides greater and better compression than the prior art methods. The segmentation and predictive techniques in conjunction with a discrete sine transform diminish the effect of correlated errors which occur at block boundaries. The method of this invention was optimized for fixed quality compression which provides superior compression over prior art methods which use feedback from a buffer to facilitate fixed rate data transmission over a communication channel.
DESCRIPTION OF THE DRAWINGS
FIG. 1 is a general block diagram of the computer-based information compression system of this invention.
FIG. 2 illustrates a block diagram of the preferred embodiment of the compression subsystem of this invention.
FIGS. 3a through 3c illustrate the implementation of block coding of the quality retention process in this invention.
FIG. 4 is a detailed block diagram of the quality retention process of this invention.
FIG. 5 is a trellis diagram used to implement the discrete sine transform and the discrete inverse sine transform in this invention.
FIG. 6 is a block diagram of the adaptive vector coder of this invention.
FIG. 7 illustrates the diagonal ordering of the two-dimensional interior block error vector.
FIG. 8 is a block diagram of the adaptive vector decoder of this invention.
FIG. 9 is a general block diagram of the circuit of this invention as used in a computer having an 8-bit or 16-bit data bus.
FIG. 10 through FIG. 21 are the schematic drawings of the circuit of this invention.
FIG. 22 illustrates the timing of the direct memory access of this invention.
FIG. 23 illustrates the timing for a normal IBM PC XT direct memory access transfer of 5 bytes.
FIG. 24 is a timing diagram for the read and write operations during a direct memory access.
FIG. 25 is a timing diagram for the I/O data transfer when the compression system is used in an IBM PC AT computer.
FIG. 26 is a wait-state data memory access timing diagram for the signal processor used in this invention.
FIG. 27 is a program memory read and memory write timing diagram for the signal processor used in this invention.
DETAILED DESCRIPTION
A functional block diagram of the computer-based information compression system of this invention is provided by FIG. 1. An analog processor 1 receives signals from an information source, for example a video image, and generates analog signals which are provided to a analog to digital converter 11. The analog to digital converter 11 performs necessary pre-filtering of the analog signal, performs analog to digital conversion, and creates in a first memory 12 a digital representation of the information received by analog processor 1. The analog to digital converter 11 and memory 12 are part of a frame grabber 10 which is incorporated in a host computer system. For a video image, the digitized information is stored in memory 12 as lines of discrete pixels.
After the image is stored in memory 12 of frame grabber 10, the host computer in conjunction with the compression/expansion subsystem 20, which is also incorporated in the host computer, performs a block transfer 21 which provides a strip of 16
lines of data from the digitized frame in memory 12 to a memory 22 in compression/expansion subsystem 20 (compression system). In FIG. 1, several different memories are illustrated in the block diagram of compression system 20. This indicates that data in memory is processed by compression system 20 and then stored in the memory. Hence, there are not multiple data memory units in compression system 20, but rather a single data memory that is used repeatedly.
The filter and sample system 23 defines the resolution of the digitized data that is passed to a quality retention process 24 and if the resolution is reduced, the filter and sample system 23 pre-filters the data to prevent aliasing. The quality retention process 24, as described more completely below, initially processes the data from filter and sample system 23 so as to optimize the compression of the data while maintaining the characteristics of the information so that a quality reconstruction of the compressed data can be performed to yield data equivalent to the initial digital data generated by frame grabber 10.
The quality retention process 24, after initial processing of the data supplies data to a discrete sine transform 25. The coefficients produced by the discrete sine transform 25 are quantized by quantizer 26 and passed to the adaptive vector coder 27. The adaptive vector coder 27 compresses the transform coefficients by assigning Huffman codes to the quantized transform coefficients. The Huffman coded information is written into memory 28 and subsequently transferred to data storage 50. Subsequent 16 line strips of data of the frame are processed in the same manner until all the lines in memory 12 of frame grabber 10 have been compressed and transferred to data storage 50.
The compression system 20 of this invention also includes means to form the original information, e.g. the image, by reconstruction of the information from the Huffman coded data stored in data storage 50. To reconstruct the image a portion of the compressed data is retrieved from data storage 50 and stored in memory 38 of compression system 20 by a fast transfer 39. The adaptive vector decoder 37 recreates the quantized discrete sine transform coefficients. The transform coefficients are reconstructed by the inverse quantizer 36. Then, the inverse discrete sine transform 35 operates on the transform coefficients to produce the data originally generated by quality retention process 24. Data are further processed by inverse quality retention process 34 to reconstruct the signals that were originally supplied by the filter and sample system 23. Finally, interpolation 33 is used to approximate the data removed by filtering end sampling in the compression process. If the resolution of the original image was reduced by the compression process, linear interpolation is used with the reconstructed data points to generate an image having the same resolution as that of the original image. After the strip of data is reconstructed, a fast transfer 31 is used to move the reconstructed data from memory 32 to memory 12 of frame grabber 10.
Again, the expansion process is repeated until all the compressed data for a frame in data storage 50 has been expanded and moved to memory 12. After the entire reconstructed digital data is in memory 12, the digital to analog converter 13
recreates the original analog signals which are sent to output analog processor 2 which generates the original video image.
While a video image has been used as an example, the compression system of this invention may be used for any information data source such as audio or video signals. However, an analog processor and an analog to digital processor that can reduce the analog signals to a known digital format is necessary. The novel compression system of this invention may be modified by one skilled in the art to compress stored digital data using the features of this invention.
In the preferred embodiment, the input analog processor 1 comprises a color television camera, which provides analog representations of color images to the analog to digital processor and the output analog processor 2 comprises a color television monitor. Accordingly, the invention is described in terms of a color video still image. However, this description is for illustrative purposes only and is not intended to limit the scope of the invention. For example, this invention can compress data generated by an audio digitizer for music, voice or other sounds or digitized black and white video images.
For a color still image, additional processing means are added to the general system of FIG. 1. The analog processor, the color television camera, generates a red analog signal, a green analog signal, and a blue analog signal. The analog to digital converter 11 changes the three analog signals to a frame having a specified number of pixels wherein each pixel has three numbers which vary between 0 and 255. The three numbers for each pixel represent the intensity of the red, green, and blue image components for that pixel. Accordingly, each line of the frame is stored in the memory 12 of frame grabber 10 (FIG. 1) as three N data points where N is the number of pixels for the line. Compression of the color digital frame requires compression of each of the three sets of data wherein each set corresponds to one of the colors red, green and blue (RGB).
In another embodiment, the analog to digital converter converts the analog video signal from the color television camera to luminance, Y, and to chrominance components, I, Q. Each pixel is represented in memory 12 of frame grabber 10 by the three components Y, I, Q. The preferred embodiment is to use a frame grabber which provides the Y, I and Q components for the video image, but most of the currently available color frame grabbers provide only the red, green and blue information for each pixel.
Since the compression system of this invention operates on luminance and chrominance components, a RGB to YIQ converter was added to coding system 20b of compression system 20a in FIG. 2. The block transfer 21 passes the data from memory 12 of frame grabber 10 sixteen lines at a time to RGB to YIQ converter 40 which translates the RGB components to YIQ components. If the frame grabber generates the YIQ components directly, the RGB to YIQ converter 40 is not utilized.
The RGB to YIQ converter 10 also separates the luminance component Y from the chrominance components I, Q. The luminance component Y, which corresponds to the black and white component of the color picture, is more critical to reconstruction of the image after compression than the chrominance components I, Q, because the human eye is more sensitive to errors in the luminance than errors in the chrominance components. Hence, the luminance Y and the chrominance components I, Q are filtered and sampled separately as shown in FIG. 2, but the remainder of coding system 20b is the same as described with respect to FIG. 1. The filtering and sampling is described more completely below.
The decoding system, i.e., the expansion system 20c of compression system 20a in FIG. 2 also has additional components to interpolate the luminance and chrominance data 33a, 33b, and to recombine the luminance and chrominance components and to convert the YIQ data to RGB data 43.
The data compression system of this invention processes a frame of data comprised of lines with each line having pixels. The system operates at normal VCR resolution, 256 lines per frame; TV resolution, 512 lines per frame; or high resolution of
1024 lines per frame. To initiate the compression, the lines of pixel data are moved into the compression system using a fast block transfer 21 as shown in FIG. 2. There are two basic ways to perform a fast block transfer, the direct memory access block transfer and programmed block input/output transfer, which are described in further detail below. The method used depends upon the characteristics of the host computer. In either case, sixteen lines of up to 512 pixels per line are normally transferred from the memory of the frame grabber 10 to the data memory of the compression system in each fast block transfer. If the frame has more than 512 pixels per line, the fast block transfer divides the line into smaller units so that the number of pixels per line is within the capability of compression system 20a.
As explained above, in the preferred embodiment, the color data for each pixel is luminance Y and chrominance I, Q. However, most of the commercially available color digitizers generate RGB data for the pixels, and so the compression system includes a means to transform RGB data to YIQ data. For example, compression system 20a of this invention is compatible with the following frame grabbers: (1) Truevision TARGA 8/16/24/32; (2) Truevision VISTA; (3) Atronics PIB; (4) Chorus PC-EYE; (5) Everex Vision 16; and (6) Matrox MVP-AT. All of these frame grabbers generate RGB data.
There are several transformations which are used to transform the red, green, blue (RGB) data to luminance Y and chrominance I, Q data. The following relationship was used in RGB to YIQ converter 40 to translate the RGB values for each pixel to the YIQ values for the pixel. ##EQU1##
After the transformation into Y, I, Q components the luminance component Y is separated from the chrominance components I, Q. The luminance Y is passed through a first filter and sample means 23a while the chrominance components I, Q are subsequently passed through a second filter and sample means 23b. Both filter and sample means simultaneously define the resolution of the components and filter the digital data to prevent aliasing. Each of the components after processing by the filter and sample means is compressed.
The functions performed by the filter and sample system for the luminance component Y and the chrominance components I, Q are performed separately, but the function of the two systems are directly related. The filter and sample system operates in two modes. In the first mode, the resolution of the luminance Y is not changed. The luminance data bypasses the filter and sample system 23a as shown by the dashed line 44 in FIG. 2. The chrominance components I, Q are each sampled at a 4:1 ratio in each dimension. Thus, the chrominance sampling provides an initial compression on the total amount of data retained.
The sampling of the chrominance components reduces the sixteen lines of chrominance component I to four lines and the sixteen lines of chrominance component Q to four lines. Further, each line of chrominance data contains only one-fourth the original number of pixels. The filtered and sampled chrominance data are not passed directly to quality retention process 24, but instead the data are temporarily stored in compression system memory 41.
After the compression of the first strip of luminance data, the coded luminance data is stored in data memory 28 of the compression system 20a and then transferred to a temporary buffer in data storage 50 by fast transfer 29. Next, a fast block transfer 21 loads a second strip of 16 lines into the compression system and the luminance is processed in the same manner as the first strip and stored in a temporary buffer in data storage 50. The chrominance components for the second strip are filtered and sampled. The resulting four lines for each chrominance component are also stored in memory 41.
The third and fourth strips of data are processed in a manner similar to the first and second strips. However, after the fourth set of luminance data are stored in the temporary buffer in data storage 50, there are sixteen lines of filtered and sampled chrominance component I and sixteen lines of filtered and sampled chrominance component Q in memory 41. Thus, the sixteen lines of chrominance component I are compressed and stored in memory 28. The coded chrominance component I in memory 28 is then transferred to compressed image data storage in data storage 50. The sixteen lines of chrominance component Q are similarly processed and transferred to compressed image data storage in data storage 50. After the coded chrominance components I, Q are moved to compressed image data storage in data storage 50, the four coded strips of luminance data in the temporary buffer are moved into the compressed image data storage in data storage 50 so that the compressed image data storage contains a 16
line strip of coded chrominance component I data, a 16 line strip of coded chrominance component Q data, and four 16 line strips of coded luminance component Y data. The coding process is then repeated for subsequent 16 line strips of the frame until the entire frame of data is coded and stored in compressed image data storage.
In the second mode of operation of the filter and sample system, the resolution in the initial frame is higher than desired, e.g., the initial frame has 512 lines and only 256 lines are desired. To lower the resolution both the luminance data and the chrominance data are filtered and sampled. The luminance data are sampled on a 2:1 basis in both dimensions. The chrominance components are again sampled on a 4:1 basis relative to the sampled luminance data which means that chrominance components are reduced in resolution by a factor of eight in each dimension.
After filtering and sampling, each of the resulting components are stored in memory 41 and a component is processed only when a sixteen strip line of the component is formed in memory 41. Hence, two strips of luminance data are filtered and sampled and then the resulting data are compressed and stored in the temporary buffer of data storage 50. Eight strips of 16 lines are processed before the chrominance components are coded, stored in memory 28, and transferred to compressed data storage in data storage 50. Finally, the four strips of coded luminance data are again moved from the temporary buffer to compressed data storage.
In both the chrominance sampling 23a and the luminance sampling 23b, the subsampling is performed in combination with low pass filtering of the digital signals. The low pass filtering prevents aliasing. For luminance filtering and sampling, the filter is a (sin X)/X filter with a cut off frequency of one half pi, which is implemented as a seven tap finite impulse response filter. The luminance filter employed in each dimension is: ##EQU2##
This filter is implemented by applying the center tap to every other pixel first in the horizontal direction and second in the vertical direction. However, this filter may not work near the beginning or end of a line in the horizontal direction or near the beginning or end of a column in the vertical direction because all the luminance terms required by the filter may not be defined. In such cases, the undefined luminance values are set to the value of the pixel which is immediately adjacent to the undefined values. For example, when the center tap is located on the first pixel in a line, so that i=1, the value of the first pixel is used for the Y.sub.-2, Y.sub.-1, Y.sub.0 terms in the filter. Similarly, the first line of filtered luminance data is repeated three times so as to generate the Y.sub.-2, Y.sub.-1, Y.sub.0 terms for each column filtered in the vertical direction.
Chrominance subsampling in combination with low pass filtering is performed for all images. The low pass filtering again prevents aliasing. The chrominance filter is a (sin X)/X filter with a cut off frequency of 1/2, 1/4, or 1/8 pi. The preferred embodiment is a filter with a cutoff frequency of 1/4 pi in each dimension for each chrominance component I and Q and is given by the following expression: ##EQU3## An identical expression is applied to the chrominance component Q. Again, the filter is applied in a first direction and then the filter is applied in a second direction to the filtered data.
To implement the chrominance filtering when the luminance resolution is not changed and the chrominance resolution is filtered on a 4:1 ratio. The center tap of the filter, i.e., the tap which operates on the I.sub.i data point in Equation 2, is first centered on the first pixel in the line and the three undefined chrominance values are set equal to the value of the first pixel as described above for the luminance filtering. The center tap of the filter is then moved to the fifth pixel and the filter is again applied, to the ninth pixel where it is again applied, and so forth. This process is repeated in the second direction where again the first line of filtered chrominance data is used three times to generate the terms I.sub.-2, I.sub.-1, I.sub.0 for each column.
When the luminance resolution is reduced, the filter in Equation 1 is applied so that the center tap is located at every other pixel in the line, and the luminance data points are reduced by one half in both directions. In this situation, the center tap of the chrominance filter is located at every eighth pixel of the chrominance data.
After the initial processing, each filtered and sampled chrominance component and the luminance Y are processed by a quality retention process 24 which is designed to process a 16 line strip of data. Thus, the quality retention process operates in the same manner independent of the particular data being processed.
The quality retention process 24 (FIG. 2) first divides each 16 line strip into blocks 24a (FIG. 4) wherein each block contains 16 rows of 16 pixels. Next, the quality retention process works with each block and further subdivides the block into four regions 24b. The interior block B(1,1), . . . , B(15,15), a two dimensional vector, is 15 pixels wide and 15 pixels high. The 1,1 point, which defines the first pixel in the first row of the block and the first pixel in the first column of the block, is the upper left hand corner of the block. The interior block contains all the pixels in the block except the pixels in the right hand column of the block, i.e., the sixteenth column of the block, and those in the lowest row of the block, i.e., the sixteenth row of the block. The right edge vector R(1), . . . , R(15) is comprised of all the pixels in the right hand column of the block except the pixel in the lower right hand corner, i.e., the 16,16 point. Similarly, the lower edge vector L(1), . . . , L(15) is comprised of all the pixels in the lowest row of the block except for the pixel in the lower right hand corner. The lower right hand corner pixel is called the corner pixel CP.
The quality retention process is first described in terms of a general block which is surrounded by blocks on all sides as illustrated in FIG. 3a. The block being processed is the J, K block, and the vector B.sub.J,K represents the pixels in the interior block of the J,K block, as described previously. The vector R.sub.J,K represents the fifteen pixels in the right edge vector of the J,K block as described previously, and the vector L.sub.J,K represents the lower edge vector of the J,K block. The corner pixel for the J,K block is represented by CP.sub.J,K.
Initially, corner pixel CP.sub.J,K is quantized 24c using a uniform quantizer Q0. This step is stage 1 in FIG. 4. In the preferred embodiment, the value of the uniform quantizer Q0 is 1 so that the value of the corner pixel is not changed by the quantization. A fixed number of bits are used to code the quantized value of the corner pixel CP.sub.J,K. Since the value is unchanged by the quantization step and the value may range between 0 and 255, eight bits are required to code the quantized CP.sub.J,K in the preferred embodiment.
If a quantizer Q0 other than 1 is used, CP.sub.J,K is quantized by dividing CP.sub.J,K by Q0 and rounding the quotient. The quantized value of CP.sub.J,K is coded, as described above, using a fixed number of bits consistent with the quantized value and stored in memory 28. The coded value of CP.sub.J,K is moved from memory 28 to data storage 50 with the first transfer of a coded sixteen line strip.
To reconstruct the value of CP.sub.J,K 24d, the quantized value of CP.sub.J,K is retrieved from memory and multiplied by quantizer Q0. The reconstructed value of CP.sub.J,K is returned to the original image position in memory 41a of the compression system because CP.sub.J,K is used in the quality retention process for the block J,K+1 and the block J+1,K.
The next step in the quality retention process is the compression of the right edge vector R.sub.J,K using stage 2 in FIG. 4. The first step 24e is to form a predicted right edge vector PR.sub.J,K (1), . . . , PR.sub.J,K (15). Each element of the predicted right edge vector is a weighted average estimate of the corresponding pixel in the right edge vector R.sub.J,K. The ith element of the predicted right edge vector is given by: ##EQU4## Hence, the predicted right edge vector is formed using the values of the corner pixel for the J,K block and the corner pixel for the subblock immediately above the J,K block, i.e., the J-1,K block (FIG. 3a).
Next, the right edge error vector 24f, which is comprised of the difference between corresponding values of each pixel in the right edge vector and the predicted right edge vector, is formed as shown in Equation 4. ##EQU5##
After formation of the right edge error vector, the vector is transformed using a one dimensional discrete sine transform 25a. The calculation of the discrete sine transform coefficients is described more completely below. The coefficients of the discrete sine transform are then quantized by quantizer 26a and coded using adaptive vector coder 27a. In FIG. 4, the one dimensional discrete sine transforms 25a, 25b, 25c, the quantizers 26a, 26b and the adaptive vector coders 27a, 27b are discrete sine transform 25, quantizer 26 and adaptive vector coder 27, respectively, of FIG. 2. The letter suffix is added to the identification number of these elements only to differentiate the steps in the compression process and is not intended to limit the invention to the specific number of elements illustrated.
The quantized transform coefficients are also stored in memory 28a. Again, as previously described, the various memory elements 41, 41a, 28, 28a as shown in FIG. 4 are the same memory and the various elements are shown to illustrate the compression process and not to limit the process by specifying multiple memory elements. The quantized transform coefficients are retrieved from memory 28a and each of the quantized coefficients is reconstructed using the inverse quantizer 36. The inverse discrete sine transform 35 is performed on the reconstructed coefficients. The resulting reconstructed error pixels are added to the predicted vector PR.sub.J,K 24.sub.g to form a reconstructed right edge vector 24h which is stored in the original image location 41a. This operation is necessary because the right edge vector is used in processing the interior block vector.
The next step in the quality retention process 24 is to form the predicted lower edge vector PL.sub.J,K (1)-PL.sub.J,K (15) using stage 2 in FIG. 4 again. Each element of the predicted lower edge vector 24a is also a weighted average estimate for the corresponding pixel in the lower edge vector L.sub.J,K. The ith element for the predicted lower edge vector is given by: ##EQU6## Hence, the predicted lower edge vector is formed using the values of the corner pixel for the J,K block and the corner pixel for the block immediately to the left of the J,K block, i.e., the J,K-1 block (FIG. 3a).
Next, the lower edge error vector 24f, which is comprised of the difference between corresponding values of each pixel in the lower edge vector and the predicted lower edge vector, is formed as shown in Equation 6. ##EQU7## After formation of the lower edge error vector, the vector is transformed using a one-dimensional discrete sine transform 25a. Again, the coefficients of the discrete sine transform are quantized by quantizer 26a and coded using the adaptive vector coder 27a. As in the reconstruction of the right hand edge vector, the quantized coefficients for the lower edge error vector are retrieved from memory 28a and the values for the original image reconstructed in a manner totally equivalent to that described above for the right edge vector.
The final step in the quality retention process 24 is the compression of the interior block as shown in stage 3 of FIG. 4. As for the lower edge vector and the right edge vector, a predicted interior block vector is formed 24i. Each element of the predicted block vector is a two-dimensional weighted average for the corresponding pixel in the interior block vector. The i,j element of the predicted block vector is formed using bilinear interpolation as shown in Equation 7. ##EQU8## Hence, the predicted interior block vector is formed using the values of the lower edge vector for the J-1,K block and the lower edge vector for the J,K block as well as the right edge vector for the J,K-1 block and the right edge vector for the J,K block.
The error vector 24j for the interior block is comprised of the difference between the corresponding values of each pixel in the interior block vector and the predicted interior block vector. The error terms are formed as shown in Equation 8. ##EQU9##
After formation of the interior block error vector 24j, the interior block error vector is transformed using a two-dimensional discrete sine transform. The two-dimensional discrete sine transform is performed by using a one-dimensional discrete sine transform in a first direction 25b. The transform coefficients generated by the sine transform in the first direction are then transformed in the second direction using the same one-dimensional discrete sine transform 25c. The quantization of the transformed coefficients for the interior block error vector by quantizer 26b, the ordering of the two dimensional interior block error vector to a one dimensional vector 46 and the coding of the quantized transform coefficients using the adaptive vector coder 27b are described in more detail below.
The formation of the error vectors for the block J,K utilized the values of the pixels in the line immediately above the first line of the block J,K, but the fast block transfer 21 (FIG. 2) to the compression system only provides sixteen lines and not seventeen lines. Accordingly, as the processing of each sixteen line strip is completed, the data for the sixteenth line is retained in memory for use with the next sixteen line strip. Hence, the error vectors for each block are defined using information from adjacent blocks. Therefore, the coded information for each block is not independent of the information in the adjacent blocks. In the prior art methods, each block was coded independently from the other blocks.
The quality retention process is used for all blocks in the frame. However, for the first sixteen line strip analyzed, there is no line above the first strip, i.e., a zeroth line, to provide the values of the lower edge vector and the right corner pixel in the interpolations described above. Thus, for the first sixteen lines in the frame, the lower edge vector and the right corner pixel for the zeroth line are estimated using the values of selected pixels in the first line of data.
Using the block 1,K in FIG. 3b as an example of a typical block in the first strip analyzed by the quality retention process, the corner pixel corresponding to CP.sub.0,K in FIG. 3a is set equal to the upper right hand piece of the block 1,K, i.e. the first pixel in right edge vector R.sub.J,K. This estimate of CP.sub.0,K is used in Equation 3 to generate the predicted right edge vector for block 1,K.
The corner pixel corresponding to CP.sub.0,K-1 in FIG. 3a is set equal to the upper right hand pixel of the block 1,K-1, i.e., the first pixel in right edge vector R.sub.1,K-1. The lower edge vector L.sub.0,K for the 0,K block is then created using these values for CP.sub.0,K and CP.sub.0,K-1 in the following equation: ##EQU10## Hence, to process the first strip of data in the quality retention process the lower edge vector for the block immediately above the block being processed in the first strip is estimated using pixels in the first line of the block to estimate the corner pixels for the zeroth line.
For blocks along the left hand edge of the frame, the corner pixels CP.sub.J-1,0 and CP.sub.J,0 as well as the right edge vector R.sub.J,0 of the block J,0 must be estimated where the block J,1 in FIG. 3c is the left most block in a strip. The corner pixel CP.sub.J-1,0 for the block J-1,0 is estimated by using the lower left hand pixel in the block J-1,1, i.e., the first pixel in the lower edge vector for block J-1,1. The corner pixel CP.sub.J,0 for the block J,0 is similarly estimated by using the first pixel in the lower edge vector L.sub.J,1 of block J,1, i.e., the pixel in the lower left hand corner of the block. The pixels in the right edge vector of block J,0 are estimated using ##EQU11## The estimated value for CP.sub.J,0 is used in Equation 5 to form predictions of the lower edge vector for block J,1.
The above estimates must be further defined for the first block in each frame (FIG. 3c) because for this block both the lower edge vector L.sub.0,1 for block 0,1 and the right edge vector R.sub.1,0 for block 1,0 must be estimated. For these estimates the corner pixel CP.sub.0,0 is set equal to the first pixel, i.e., the 1,1 pixel in the block, and then the estimates for the lower edge vector L.sub.0,1 for block 0,1 and the estimates for the right edge vector R.sub.1,0 for block 1,0 are formed using Eq. 9 and Eq. 10 respectively.
The estimated corner pixels are each coded with 8 bits and stored in memory 28 prior to compression of the first 16 line strip.
The method described above for interpolating along the upper edge of the frame and the left hand edge of the frame has been shown to provide superior results to methods which simply use an average value for each pixel, say 128, along the upper and lower edge and perform the interpolations based upon these values.
In the preferred embodiment, implementation of the discrete sine transform is based upon a discrete sine transform algorithm suggested by P. Yip and K. R. Rao in a paper entitled "A Fast Computational Algorithm For the Discrete Sine Transform," published in IEEE Transactions on Communications, Vol. Com-28, No. 2, pp. 305-307, Feb. 1980. As explained in that paper, the discrete sine transform is faster and requires less multiplications and additions than the discrete cosine transform used in the prior art. Accordingly, not only does the present invention provide a new and better way to compress video still images which results in improved image quality upon reconstruction, but the advantages of the fast discrete sine transform enhance the performance over a similar system which uses the discrete cosine transform.
The discrete sine transform coefficients X(j) are given by ##EQU12##
The trellis diagram in FIG. 5 was used to implement the 15 point one dimensional transform. Computation of the transform coefficient is grouped into eight sets of fifteen operations as shown in FIG. 5.
The discrete sine transformation changes the fifteen values in an error vector x(i) into a vector of fifteen transform coefficients X(j). The vector of transform coefficients is quantized using quantizer 26 and coded using the adaptive vector coder 27 (FIG. 2) to provide the data compression. Each transformed vector is coded by the same method.
The transformed vector is quantized 26 using a variable Q for the particular vector and the quantizer threshold QTHR as shown in Equation 12. ##EQU13## The variable Q is given by Q1 for the transform coefficients of the right edge vector and the lower edge vector and by Q2 for transform coefficients generated by the two dimensional discrete sine transform of the interior block.
The actual values of the variables Q1 and Q2 are related to a number which is specified by the user. The user chooses a quality factor which varies between 1 and 100. The value of 1 gives the greatest compression and provides a somewhat lower quality reconstructed image while a value of 100 gives the least compression but a higher overall quality reconstruction of the original image. Accordingly, the user must balance the need for quality in the reconstructed image against the available storage space for the compressed data base. The variable Q2 is defined as:
The variable Q1 defaults to:
unless the value of Q.sub.2 equals one. If Q.sub.2 equals one, then Q.sub.1 is also taken as one.
In a preferred embodiment, the quantizer threshold QTHR is the variable Q divided by 4 so that Equation 12 becomes ##EQU14## Using Equation 15, it is easy to see that the quantization is variable because coefficients having an absolute value between 0 and 0.74 Q are assigned the coefficient 0, numbers between 0.75 Q and 1.74 Q are assigned the coefficient 1, numbers between -0.75 Q and -1.74 Q are assigned the coefficient -1, numbers between 1.75 Q and 2.74 Q are assigned the coefficient 2, and so forth. The sign of the coefficient is retained for all non-zero coefficients and thus the quantization interval around zero is 1.5 Q wide and all other intervals are Q wide.
This quantization was chosen to produce more zero coefficients which in turn improves coding efficiency. In the preferred embodiment, each of the quantized sine transform coefficients comprises a sixteen bit character having 1 sign bit and 15
bits of magnitude.
After the quantization of the coefficients, the quantized coefficients are coded. However, the coding process is designed for a one dimensional vector. While the quantized transform coefficients for the right edge error vector and the lower edge error vector are one dimensional, the quantized transform coefficients for the interior block error vector are two dimensional. Hence, the quantized two dimensional transform coefficients are ordered to form a one dimensional vector. The ordering is accomplished by following the diagonal path illustrated in FIG. 7.
The one dimensional vector of quantized transform coefficients is coded using multiple Huffman code tables. A predicted mean PM.sub.K for the K+1 term in the vector is calculated, as described below, using the Kth term of the vector and the predicted mean PM.sub.K-1 for the Kth term in the vector. The predicted mean is used to select one of the six Huffman code tables as shown in Microfiche Appendix B, which are incorporated herein by reference. In general, the calculated predicted mean PM.sub.K is used to select the Huffman code table for quantized coefficient K+1, PM.sub.K+1 is used to select the Huffman code table for quantized coefficient K+2, and so forth.
The six Huffman code tables of Microfiche Appendix B were calculated using empirical methods. A group of color video images were processed using the compression process of this invention. Each image was processed using the quality retention process above, a discrete sine transform was performed and the quantized sine transform coefficients were coded using the predicted mean calculated for each coefficient. Predicted mean thresholds used for table selection were adjusted so that the probability of selecting any given table was one sixth, i.e. there is an equal probability of choosing any one of the tables.
Since the distribution of quantized transform coefficients are peaked near zero, the initial boundaries for the six tables had a logarithmic distribution. The boundaries were adjusted by trial-and-error until the specified boundaries were achieved. Hence, the procedure to determine the distributions for each Huffman code table and the probabilities of falling within a given range of the distribution were determined using the compression scheme of this invention to generate a large number of predicted means and then grouping the means into six equal probability groups.
The first step in coding a one dimensional vector of quantized transform coefficients is to compute the initial value of the predicted mean PM.sub.0 27a (FIG. 6) that is used to select the Huffman code table 27b for the first member in the vector. The initial value of the predicted mean PM.sub.0 is calculated using: ##EQU15##
In a preferred embodiment, PMINIT is taken as 512. Conceptually, PMINIT is a constant which is approximately equal to the mean value of the first quantized coefficient amplitude QCOEF.sub.0 when Q=1. This constant was also determined empirically. To determine the value of PMINIT, approximately 25 video images were digitized as described above and the mean amplitude of the first coefficient QCOEF.sub.0 was determined. Actually, each block has three values of QCOEF.sub.0 associated with each of the three components which are generated in the compression of the block. The images were chosen to represent a cross section of the images that are typically encountered in digitization. After the coefficients QCOEF.sub.0 were determined for the selected images, the total number of coefficients were added together and divided to define PMINIT.
After calculation of PM.sub.0, the Huffman code table is selected by determining which table has boundaries that include the calculated value of PM.sub.0. If the first coefficient is zero, the zero run count is incremented 27c. If the first coefficient is not zero, the selected Huffman code table is used to code the first coefficient amplitude 27d and the sign for the first coefficient is coded with an additional bit.
After the coding of the first coefficient in the vector, the predicted mean is calculated 27e using the following relationship: ##EQU16## The Huffman code table 27f having boundary thresholds which bracket the calculated predicted mean is selected for coding the next coefficient in the vector.
If the next quantized coefficient QCOEF.sub.K is zero the run count, i.e. the count of the number of consecutive zeros, is incremented 27i and the value of the predicted mean 27e for the next coefficient is calculated.
If the quantized coefficient QCOEF.sub.K is non-zero and the run count is also non-zero, the repeat code is coded 27.sub.j using the selected Huffman code table 27f and the run count is set to zero 25k. The amplitude of the quantized coefficient is then coded 27m using the selected Huffman code table 27f as previously described. However, if the amplitude is too large to have a corresponding code in the selected code table 27n, then an escape ESC is coded followed by a fixed number of bits which represents the amplitude of the quantized coefficient. For any non-zero coefficient, an additional bit is coded to represent the coefficient sign. Finally, the new predicted mean 27e is calculated using Equation 17 for the next coefficient.
If the quantized coefficient is not the last one in the vector this process is repeated until the final term in the vector is reached. If the final coefficient is zero, then a EOV is coded 27g using the code table selected using the predicted mean.
After a 16 line strip is coded, the coded strip is moved by a fast block transfer, as previously described, to data storage 50.
The compression system of this invention also includes means for retrieving a compressed image from the compressed image data storage 50 (FIG. 2) and reconstructing the data so that it may be moved into the memory of frame grabber 10, shown in FIG. 1. The process is the expansion, sometimes called decoding, of the compressed data. The precise calculation performed in each of the expansion steps is simply the inverse of the operation described in the coding of the compressed data. In the block transfer from data storage 50, one strip of coded quantized chrominance component I data, one strip of coded quantized chrominance component Q data and one strip of coded quantized luminance data are sequentially moved into data memory 38 (FIG. 2) of the compression system 20 and then expanded. For each block of compressed data within a strip, the coded corner pixel, the coded quantized transform coefficients in the right edge error vector, in the left edge error vector, in the interior block error vector are sequentially processed in the order given. For each of the vectors the decoding process is similar.
The adaptive vector decoder 37 (FIG. 2 and FIG. 8) uses the predicted mean to select a Huffman decoding tree for decoding each term of a vector. The Huffman decoding trees which correspond to the six Huffman coding tables are also shown in Microfiche Appendix B and are incorporated herein by reference. The boundaries for the decoding trees are the same as those for the coding tables. Thus the value of PM.sub.0, as previously defined in Eq. 16, is used to select the first Huffman decoding tree and the first coefficient in the vector is decoded using the first value of the selected Huffman decoding tree. Then the decoded coefficient and the value of PM.sub.0 are used to form the next value of the predicted mean using Equation 17
and the next Huffman coded coefficient is decoded using the Huffman decoding tree selected by the predicted mean. If a zero run count is decoded, then the specified number of zeroes are added to the vector and the predicted mean is calculated using each of the zeroes so that the value of the predicted mean remains in phase with the term being decoded. This process is continued until all the quantized coded coefficients have been decoded using the Huffman decoding trees.
After the quantized coded vectors are decoded the inverse quantization process 36 is performed. The inverse quantization is given by:
where the terms in this equation are defined as in Equation 12. In Equation 12 and in Equation 18, the constant, 0.5, has been added for rounding prior to converting the calculated number to integer. The decoded sign bit for the inverse quantized coefficient is then applied to the coefficient generated by Equation (18) to complete the inverse quantization process. After the inverse quantization process 36, a vector has been generated containing the discrete sine transform coefficients. Accordingly, an inverse discrete sine transform 35 is performed. The inverse discrete sine transform is given as: ##EQU17## where the terms in Eq. 19 have the same definitions as the terms in Eq. 11. The trellis diagram in FIG. 5 is again used to implement the inverse sine transform.
The inverse sine transform generates a reconstructed error vector. Prior to processing the coded right edge error vector, the coded lower edge error vector, or the coded interior block error vector, the coded corner pixel was retrieved from memory 38, decoded and placed in memory 47. Thus, the appropriate decoded corner pixels are retrieved from memory 47 and the appropriate one-dimensional predicted vector is formed using Equation 3 if the right edge vector is being decoded and Equation 5
if the lower edge vector is being decoded. If the block being decoded is in the first strip or the first column of blocks, then the required corner pixels are estimated in a manner identical to that previously described in the coding process. After formation of the predicted vector, the predicted vector is added to the reconstructed error vector to create the reconstructed one-dimensional vector.
After reconstruction of the right edge vector and the lower edge vector using the above process, the coded interior error block is decoded using a similar process. Since the coded interior error block vector was a one-dimensional vector, the vector is decoded 37 (FIG. 2) in a manner identical to that for the lower edge vector and the right edge vector and the inverse quantization process 36 is similarly performed.
However, prior to performing the inverse discrete sine transforms 35, the one-dimensional vector is converted to a two-dimensional vector using the path shown in FIG. 7. After the two-dimensional vector is formed a one-dimensional inverse sine transform is performed in the second direction and a one-dimensional inverse sine transform is performed in the first direction.
Next, the reconstructed right edge vector and the reconstructed lower edge vector, along with the reconstructed right edge vector for the block preceding the current block, the reconstructed lower edge vector for the block above the current block, which was retained in the memory just as in the original coding process, are used to form the predicted interior block vector using Equation 7. After the predicted vector is formed, the reconstructed error vector is added to the predicted interior block vector to form the reconstructed interior block vector.
The reconstruction process proceeds somewhat differently from the coding process, because the chrominance data for a 16 line strip are decoded first and then the luminance component for that strip is decoded.
As the data for each 16 line strip is reconstructed, the reconstructed data is stored in memory 47. The reconstructed chrominance components I, Q for each 16 line strip are passed through chrominance interpolator 33b which uses bilinear interpolation to replace the pixels that were removed in filter and sample step 23b during coding of the data. The interpolation used is given by Equation 20 in the vertical direction and then equation 21 in the horizontal direction. ##EQU18##
If the resolution of the luminance was not changed in the coding process, then the reconstructed luminance strip is passed directly to memory 42 as shown by dotted line 45 in FIG. 2. However, if luminance filter and sample process 23a was used in coding the compressed data and the original luminance resolution is desired, the reconstructed luminance data is processed by luminance interpolation 33a. Luminance interpolation 33a also used Equations 20 and 21 to generate the values for the additional pixels.
After the luminance and chrominance components are defined for each of the pixels in the final frame, the pixels in the chrominance and luminance data for each pixel in the strip are combined and the data is passed through a YIQ and RGB converter
43 to change the luminance and chrominance data into red, green and blue data. The YIQ to RGB transformation is given in Equation 22. ##EQU19##
The compression/expansion process of this invention provides greater and better compression than the prior art methods. The segmentation and predictive techniques in conjunction with the discrete sine transform diminish the effect of correlated errors which occur at block boundaries. The errors are moved into the center of the blocks where they are less detectable. Further, since the method is not designed for real time data transmission, the quantized value may be fixed for a given image. This provides superior compression over prior art methods which used feedback from a buffer to control the compression and the problem of interfacing asynchronous compression with a synchronous real-time data transmission channel is not relevant. Therefore, the method of this invention was optimized for fixed-quality compression rather than compression that facilitates fixed-rate data transmission over a communications channel.
In the prior art, video compression systems have implemented the compression process using hardware. Hardware was selected for the implementation because the signal processors available were slow compared to the processing time of a hardware based system. However, with new signal processors, which can multiply and accumulate in approximately 100 nanoseconds, a hardware implementation of the compression process is unnecessarily restrictive. A hardware compression system is limited to compression via the process implemented in the hardware, but a compression system which uses software can be modified by changing only the software when or if changes to the compression process are necessary. Accordingly, the compression system of this invention is implemented using circuitry for interfacing with a host computer and for providing data to a signal processor which uses the assembly language program in Microfiche Appendix A, which is incorporated herein by reference, to perform the compression of the data.
More specifically, FIG. 9 illustrates a block diagram of the compression system of this invention which can be used in an IBM PC XT or compatible computer. In FIG. 9, the program which implements the compression process is stored in the program memory 101, which is an 8K.times.16 static RAM. The host computer provides signals on a I/O data bus 102c, an I/O address bus 102b, and an I/O control bus 102a. These busses are interfaced to the control bus 103a, the address bus 103b and the data bus
103c of the compression system. While data bus 103c, as shown in FIG. 9, carries eight bits, the compression system includes means 103d, 115, 116 for interfacing with a 16 bit data bus which is described later. The signals provided by the host computer over the I/O control bus and the I/O address bus are processed by a control logic system 104 which in turn provides signals to a memory control circuit 105, to an address generation circuit 106 to a 8-bit low byte latch 110, to a 8-bit high byte buffer
111, to a 16-bit LO byte Tx data 115, to a 16-bit HI byte Tx data 116 and to signal processor 108.
The host computer initiates a data transfer to and from the compression system, while the signal processor 108 of the compression system interfaces only with data memory 109, and the program memory 101. When the host computer transfers data to or from the compression system, the signal processor 108 address, data and control busses are tri-stated.
To initiate a data transfer to or from the compression system, the host computer initializes the compression system by providing signals on the I/O address and data bus of the host computer. The host computer provides over the data bus 103c an initial address in the memory 109 of the compression system for storing or retrieving the first byte of data. The host computer also generates signals over the control bus 103a, and the address bus 103b which control operation of logic circuit 104. In response to the signals from the host computer, the control logic circuit 104 generates signals to the address generation circuit 106 which cause the address circuit to latch the initial address. When the host processor accesses signal processor memory, the control logic circuit 104 generates signals which cause the signal processor 108 to go tri-state.
After the initialization of the address generation circuit 106 the host computer starts the data transfer over the data bus. For host computers which have an 8 bit data bus, the data must be configured for the 16 bit structure of the compression system. Hence, the control logic circuit 104 controls the address generation circuit 106 and the memory control circuit 105 using signals provided over the control bus 103a so that the data is alternatively supplied or taken from the memory 109 through the high byte buffer 111 and the low byte latch 110. Simultaneously with alternating between latch 110 and buffer 111, the memory control circuit 105 enables the appropriate section of memory so that valid data is written into memory 109 or taken from memory 109 and the address generation circuit 106 increments the address for memory 109. While a transfer to and from data memory 109 was described here, a similar process is used to load either the compression process or expansion process into program memory 101.
The control logic circuit 104 provide signals which the host computer can interrogate to determine the status of the transfer to or from the compression system. When the transfer is complete, the control logic circuit 104 generates signals, which cause the host computer to release control of the busses.
After the data transfer, the signal processor 108 takes control and expands or compresses the data in memory 109 using Huffman coding or decoding tables in memory 109 and the process, described previously, which is stored in program memory 101. The processed data is stored in memory 109 for subsequent transfer by the host computer. After a compression or expansion has been completed, the signal processor raises a flag which can be read through the status register indicating that the current process is completed and the signal processor is again available for either compression or expansion.
The interface of the host computer and the compression/expansion system is controlled by a program in the host computer. The C language program used in this invention is given in Appendix C and is incorporated herein by reference. As described above, the primary purpose of the program is to transfer data from the frame grabber board 10 as shown in FIG. 1 to the compression system 20. In addition, the program provides a user interface with the compression system and a means for initializing and configuring the compression system to perform either a compression or an expansion. The size of the program memory in compression/expansion system 20 prevents simultaneously loading both the process for compression of the data and the process for expansion of the data. Thus, the compression process or the expansion process is loaded into program memory 101 and the system is initialized for the appropriate function.
The initial step in the compression process is for the program in the host computer to load the compression program, the expansion program, the Huffman code tables, the decoding tables, and the table used to order the two dimensional interior block vector as a one dimensional vector into the memory of the host computer. Next, the program interfaces with the user so that the user can specify the quality, as defined previously. The user specified quality is used to calculate the quantization factors Q.sub.1, and Q.sub.2, as defined above. After calculating the quantization factors, the host computer program loads the compression program code into the program memory of the compression system, and the 2D to 1D ordering table. The Huffman code tables are loaded into the data memory of the compression system.
Then the parameters which describe the data in the memory of the frame grabber, the filtering and subsampling of the luminance and chrominance data and the quantization factors are loaded into pre-defined locations within the data memory of the compression system by the program in the host computer. Thus, the host computer program has initialized the compression system so that it is ready to receive data by a fast transfer and start the compression of each 16 line strip.
However, prior to initiating the compression of the frame, the compression system requires further initialization. First, as described above, the filtering of the chrominance data requires the generation of three lines of data above the first line of the first strip so that the terms in the seven tap finite impulse response filter are defined when the filter is applied on the first line of the data. Therefore, the program in the host system loads four lines of data into the data memory of the compression system so that the vertical filter can be preloaded. Also at this time the compression parameters are written as a header of compressed image storage in data storage 50. After the compression system preloads the vertical filter, the compression system is ready to perform the compression process as previously described, and the host computer program transfers sixteen lines of RGB data from the frame grabber board to the data memory of the compression system and issues a compress command.
The compression system then takes control and compresses the sixteen lines of luminance data and subsamples and filters the chrominance components using the process previously described. After the compression of the luminance data, the host computer program again takes control and transfers the compressed luminance data from the data memory of the compression system to a temporary buffer in the data storage 50 as previously described. This cycle is repeated three more times, i.e., the host computer program supplies sixteen lines of RGB data from the frame grabber board, issues another compress command and after compression moves the 16 line strip of compressed luminance data to the temporary buffer in data storage 50.
After the fourth strip of compressed luminance data is transferred to the temporary buffer, the host computer issues a compress-no data command and the compression system then processes the filtered and subsampled chrominance component I data, which now comprises a sixteen line strip. After compression, the host computer program transfers the compressed chrominance component I data to the compressed image buffer. The computer program then issues another compress-no data command and the compression system processes the sixteen line strip of filtered and subsampled chrominance component Q data. After the data is compressed, the host computer program transfers the compressed chrominance Q data to the compressed image buffer. The host computer program then moves the four sixteen line strips of compressed luminance data from the temporary buffer to the compressed image storage in data storage 50 so that the luminance data is located after the compressed I and Q data.
The host computer program repeats this cycle, i.e., initiates the transfer and compression of four more strips of sixteen lines from the frame grabber memory and issues two compress-no data commands and stores the compressed data, as described previously, until the entire frame of data in the memory of the frame grabber has been compressed.
The frame in the frame grabber memory has 480 lines which is divisible by 16 so that the luminance data are completely processed by the above method. However, 64 lines of data, i.e. 4 strips, are required to generate one 16 line strip of chrominance data. Thus, when the 480 lines are processed, the strips of chrominance data in the data memory of the compression system contain only 8 lines because 480 is not divisible by 64. To complete the processing of the chrominance data, the program in the host computer generates two strips of grey RGB data which are processed by the compression system. Thus, after filtering and sampling, the chrominance components have the 16 lines necessary for processing by the compression process and all the data from the frame grabber memory is processed by the compression system.
As explained above, both the compression process and the expansion process cannot be loaded in the compression/expansion system at the same time. Accordingly, to perform an expansion, the expansion process, the Huffman decoding trees, and the table to convert the one dimensional interior block vector into a two dimensional vector are loaded into the compression/expansion system by the host computer program. Next, the host computer program obtains the compression/expansion parameters from the compressed image storage where they were stored in the compression process. The compression/expansion parameters are then transferred to the compression system and the first sixteen line strip of compressed chrominance component I is moved into the data memory of the compression system. The program in the host computer then issues an expand initialization command which resets the internal variable s of the signal processor in the compression system, expands the compressed chrominance component I data, and stores the reconstructed data in the internal I buffer in the data memory of the compression system.
Next, the host computer program transfers the compressed chrominance component Q data from the compressed image storage into the data memory of the compression system and issues an expand command. Accordingly, the compression system expands the chrominance component Q data and stores the expanded chrominance also in the internal buffer in the data memory of the compression system.
After the expansion of the chrominance data, the host computer program loads a sixteen line strip of the compressed luminance data into the compression system and issues an expand command. When the expansion is completed, sixteen lines of RGB data are transferred from the data memory of the compression system to the memory of the frame grabber by the host computer program. This process, the loading of sixteen lines of compressed luminance data Y, the expansion and the transfer of sixteen lines of RGB data from the compression system to the frame grabber, is repeated for a second sixteen line strip and a third sixteen line strip. A fourth sixteen line strip of compressed luminance data Y is moved into the compression system, the expand command is given by the host computer program, and the expansion is completed by the signal processor, but only twelve lines of red, green and blue image data are moved from the data memory of the compression system to the memory of the frame grabber.
Next, a sixteen line strip of compressed chrominance component I data is moved to the compression system and the expand command is given and no lines of data are moved from the data memory of the compression system to the memory of the frame grabber. The compressed chrominance component Q data is moved into the data memory of the compression system, an expand command is given by the host computer, and the chrominance component data Q is expanded by the compression system. After the expansion is complete, four lines of red, green, blue, four lines of RGB data are moved from the data memory of the compression system to the memory of the frame grabber. The four expansions of the compressed luminance data with a 16 line, 16 line, 16
line and 12 line transfer of reconstructed data, the expansion of the compressed I with no transfer of reconstructed data and the expansion of compressed Q data with the transfer of 4 lines of reconstructed data are repeated by the host computer program until the 480 lines of compressed image data are processed and moved to the memory of the frame grabber.
The above description of the program in the host computer describes the preferred embodiment wherein the frame has 512 pixels per line, 480 lines are stored in the compressed frame, the chrominance data is filtered and subsampled on a 4:1 basis, and the resolution of the luminance data is not reduced. However, the compression process has the ability, as described above, to further reduce the resolution of the luminance and the chrominance components. The data transfers and the commands necessary to either expand or compress the image for these other modes are included in the program given in Appendix C.
The schematic drawings for the system illustrated in FIG. 9 are given in FIG. 10 through FIG. 21. Each of the integrated circuits or logic gates in FIG. 10 through FIG. 21 is represented by a number, the first letter of which is an alphanumeric character and the second letter of which is an arabic numeral. The alphanumeric character and arabic number identify a specific integrated circuit which is identified in the parts list given in Table 1.
TABLE 1 __________________________________________________________________________ ITEM QUAN PART NUMBER DESCRIPTION REF DES __________________________________________________________________________ 1 1 320C25 - TI Digital Signal Processor E1 2 4 43256 - 32K .times. 8 Static RAM (200 NS) - 10L H3, H5, K3, K5 3 2 SSM7164-35 8K .times. 8 Static RAM H1, K1 4 1 74F00 - Fast TTL Quad Two Input NAND A4 5 1 74ALS04 - ALS TTL Hex Inverter D1 6 1 74ALS08 - ALS TTL Quad 2 Input and Gate C5 7 2 74LS08 - LS TTL Quad 2 Input and Gate A3, C2 8 1 74LS14 - LS TTL Hex Inverter with Schmitt Trigger B4 9 1 74S22 - Schottky TTL DuaI 4-Input NAND, OC Output B3 10 3 74F32 - Fast TTL Quad 2 Input OR Gate B6, F6, F7 11 3 74LS32 - LS TTL Quad 2
Input OR Gate B5, C1, C3 12 3 74LS74 - LS TTL Dual D Flip-Flop A2, B2, C4 13 1 74LS138 - LS TTL 3/8 Decoder C6 14 5 74LS161 - LS TTL /16 Sync Counter, Direct CLEAR D3, D4, D5, D6, E6 15 1 74LS175 - LS TTL Hex D Flip-Flops With CLEAR E7 16 2
74F244 - Fast TTL Octal Buffer C7, H6 17 3 74LS244 - LS TTL Octal Buffer A5, E4, E5 18 3 74F245 - Fast TTL Octal Bus Transceiver A7, D7, K7 19 1 74LS245 - LS TTL Octal Bus Transceiver K6 20 1 74LS273 - LS TTL Octal D Flip-Flop With CLEAR A6 21
1 74LS374 - LS TTL Octal Flip-Flop H7 22 1 74LS688 - 8 Bit Comparator B7 23 29 Capacitor, .1MFD, Ceramic +80, -50% C51, C53-C80 50-150v Aux SR275 = 104ZAA (Radial 0.3") 24 2 Capacitor, 22MFD Electrolytic +/- 25% C52, C81 25V (Radial 0.2") SPR
513D226M025JA4 25 1 DIP Switch, 8 Switches, 16 pin Dip, P/N ADP-08 A1 26 1 40 MHZ Oscillator D2 27 1 Resistor Pak, 1K Ohm, 16 Pin Dip, P/N 898-1-RIK B1 28 2 Board Mount Pins (2 Pin) J1, J2 29 2 Jumper J1, J2 30 1 68 Pin IC socket, McKenzie P/N P6M068-IA1133-DC E1 31 2 28 Pin IC socket, Solder 0.3", Augat 528-AG11D H1, K1, OR- 4 14 Pin IC socket, solder 0.3", Augat 514-AG11D H1, K1 32 1 PC Board P/N 88-100002-00 __________________________________________________________________________
If the integrated circuit contains more than one logic gate, the individual gates are identified by another alphanumeric character after the first two characters. For example, OR gate B5A in FIG. 10 is the first OR gate in integrated circuit B5
which in turn is identified in Table 1 as a 74LS32-LS TTL QUAD 2 input OR gate. Individual terminals of an integrated circuit are identified in the figures by using the identifiers for the integrated circuit or the component in the integrated circuit followed by a dash and the number of the integrated circuit pin which corresponds to the terminal.
In FIGS. 10 through 21, lines which perform a specific function are given a name and the complement of the signal is shown by a slash prior to the name. Similarly named lines on the different figures are directly connected. Further, the number or numbers in square brackets are the numbers of the figures where the line is continued.
In Table 2, a wire list for the compression system of this invention is given. The wire list describes the various interconnections in the compression system. For example, the ninth entry in Table 2 is
______________________________________ 9 /DSPHOLDA D1-5 E1-E10 ______________________________________
This means that the line carrying the complement of the DSPHOLDA signal goes from the fifth pin of the circuit element D1, which appears in FIG. 19, to the pin E10 of circuit element E1, which is the signal processor in FIG. 15. Thus, the first column in Table 2 give the signal on the line which interconnects the points given in the next four columns.
TABLE 2 __________________________________________________________________________ 1 +5 A2-14 A3-14 A4-14 A5-20 A6-20 A7-20 B03-EDGE B29-EDGE C53-T C99-T C73-T C52-T B2-14 B3-14 B4-14 B5-14 B6-14 B7-20 C1-14 C2-14 C3-14 C4-14 C5-14 C6-16 C7-20 D1-14 D3-16 D4-16 D5-16 D6-16 D7-20 E1-A10 E1-B10 E1-H2 E1-L6 E4-20 E5-20 E6-16 E7-16 F6-14 F7-14 H1-28 H2-28 H3-28 H5-28 H6-20 H7-20 K1-28 K2-28 K3-28 K5-28 K6-20 K7-20 2 /BT16 A5-6 C4-4 F6-10 A4-12 A4-13 B1-6 J2-2 3 /DACK1 B4-1 C5-4
C5-2 B17-EDGE 4 /DATA B4-11 B4-3 B6-10 B6-4 B6-12 C3-1 C3-4 C5-6 5 /DMASTART B2-13 A3-9 B5-3 6 /DSPDSO F6-3 H5-20 K5-20 7 /DSPDS1 F6-6 K3-20 H3-20 8 /DSPDS C7-7 E1-K10 F6-1 F6-4 F7-1 9 /DSPHOLDA D1-5 E1-E10 10 /DSPPS C7-9 D1-11 H2-20 El-J10 B1-8 K2-20 11 /DSPRD F7-8 H1-22 H2-22 H5-22 H3-22 K3-22 K5-22 K2-22 K1-22 12 /DSPSTRB C7-5 E1-H10 B1-2 F7-10 F7-5 13 /DSPWR F7-6 H1-27 H2-27 H5-27 K5-27 H3-27 K3-27 K1-27 K2-27 14 /HOLDA B3-4 C1-10 C1-12 C7-19 D1-8 E4-19 E4-1 E5-1 E5-19
15 /HOLD A2-5 E1-A7 16 /IOR A4-1 B14-EDGE C7-2 17 /IOW A4-2 B13-EDGE C7-4 18 /LDCTRHB C6-12 D4-9 D3-9 19 /LDCTRLB B5-5 C6-13 D6-9 D5-9 20 /MSC E1-C10 F7-2 21 /RDSTATUS A5-1 A5-19 B5-11 22 /RD A7-1 B5-13 D7-1 K6-1 K7-1 C7-18 B6-13 23 /RESETDSP A6-2 C2-12 24 /RESET A2-4 A3-10 A3-1 A6-1 B4-8 C2-13 D3-1 D4-1 D6-1 C2-4 D5-1 E7-1 E6-1 25 /RWDATA A3-4 C3-6 C4-3 C5-10 26 /RW A4-6 C3-5 C7-15 D5-2 D6-2 D3-2 D4-2 27 /WRCTRLB B5-6 C2-5 28 /WRMODE A6-11 B5-8 29 /WR B5-1 B5-4
B5-10 C7-16 C3-2 30 ADDHI C1-11 C1-1 C3-12 F6-9 31 BDO A5-3 A6-3 A7-18 D5-3 D4-3 H6-18 K7-2 H7-3 K6-2 32 BD1 A5-18 A6-18 A7-17 D4-4 D5-4 H6-16 K7-3 H7-4 K6-3 33 BD2 A5-5 A6-4 A7-16 D4-5 D5-5 K6-4 K7-4 H7-7 H6-14 34 BD3 A5-16 A6-17 A7-15
D5-6 D4-6 H6-12 H7-8 K7-5 K6-5 35 BD4 A5-7 A6-7 A7-14 D3-3 D6-3 H7-13 K7-6 H6-9 K6-6 36 BD5 A5-14 A6-14 A7-13 D6-4 D3-4 H6-7 K7-7 H7-14 K6-7 37 BD6 A5-9 A6-8 A7-12 D3-5 D6-5 H7-17 K7-8 H6-5 K6-8 38 BD7 A5-12 A6-13 A7-11 D3-6 D6-6 H6-3
H7-18 K7-9 K6-9 39 CLKOUT1 A2-3 E1-C11 40 DEN C1-3 C7-17 C3-10 41 DMAENA A2-12 A6-9 42 DMA --IN --PROG A5-8 B2-9 43 DRQEN B2-5 C2-9 44 DSPAO E1-K1 E5-18 H1-21 H2-21 H3-10 H5-10 K1-21 K2-21 K3-10 K5-10 45 DSPA10 E1-K7 E4-14 H1-8 H2-8 H3-21 H5-21 K1-8 K2-8 K3-21 K5-21 46 DSPA11 E1-L8 E4-12 H1-9 H2-9 H3-23 H5-23 K1-9 K2-9 K3-23 K5-23 47 DSPA12 E1-K8 E4-9 H1-10 H2-10 H3-2 H5-2 K1-10 K2-10 K3-2 K5-2 48 DSPA13 E1-L9 E4-7 H1-20 H2-26 H3-26 H5-26 K2-26 K1-20 K3-26 K5-26 49 DSPA14 E1-K9 E4-5 H3-1 H5-1 K3-1 K5-1 50 DSPA15 D1-13 F6-2 E1-L10 E4-3 51 DSPA1 E1-K2 E5-16 H1-23 H2-23 H3-9 H5-9 K1-23 K2-23 K3-9 K5-9 52 DSPA2 E1-L3 E5-14 H1-24 H2-24 H3-8 H5-8 K1-24 K2-24 K3-8 K5-8 53 DSPA3 E1-K3 E5-12 H1-25 H2-25 H3-7
H5-7 K1-25 K2-25 K3-7 K5-7 54 DSPA4 E1-L4 E5-9 H1-2 H2-2 H3-6 H5-6 K1-2 K2-2 K3-6 K5-6 55 DSPA5 E1-K4 E5-7 H1-3 H2-3 H3-5 H5-5 K1-3 K2-3 K3-5 K5-5 56 DSPA6 E1-L5 E5-5 H1-4 H2-4 H3-4 H5-4 K1-4 K2-4 K3-4 K5-4 57 DSPA7 E1-K5 E5-3 H1-5 H2-5 H3-3 H5-3 K1-5 K2-5 K3-3 K5-3 58 DSPA8 E1-K6 E4-18 H1-6 H2-6 H3-25 H5-25 K1-6 K2-6 K3-25 K5-25 59 DSPA9 E1-L7 E4-16 H1-7 H2-7 H3-24 H5-24 K1-7 K2-7 K3-24 K5-24 60 DSPDO E1-F1 H1-11 H2-11 H3-11 H5-11 H7-2 H6-2 K6-18 61 DSPD10 D7-16 E1-A3
K1-13 K2-13 K3-13 K5-13 K7-16 62 DSPD11 D7-15 E1-B4 K1-15 K2-15 K3-15 K5-15 K7-15 63 DSPD12 D7-14 E1-A4 K1-16 K2-16 K3-16 K5-16 K7-14 64 DSPD13 D7-13 E1-B5 K1-17 K2-17 K3-17 K5-17 K7-13 65 DSPD14 D7-12 E1-A5 K1-18 K2-18 K3-18 K5-18 K7-12 66 DSPD15 D7-11 E1-B6 K1-19 K2-19 K3-19 K5-19 K7-11 67 DSPD1 E1-E2 H1-12 H2-12 H3-12 H5-12 H7-5 H6-4 K6-17 68 DSPD2 E1-E1 H1-13 H2-13 H3-13 H5-13 H7-6 H6-6 K6-16 69 DSPD3 E1-D2 H1-15 H2-15 H3-15 H5-15 H7-9 H6-8 K6-15 70 DSPD4 E1-D1 H1-16 H2-16
H3-16 H5-16 H7-12 H6-11 K6-14 71 DSPD5 E1-C2 H1-17 H2-17 H3-17 H5-17 H7-15 H6-13 K6-13 72 DSPD6 E1-C1 H1-18 H2-18 H3-18 H5-18 H7-16 H6-15 K6-12 73 DSPD7 E1-B2 H1-19 H2-19 H3-19 H5-19 H7-19 H6-17 K6-11 74 DSPD8 D7-18 E1-A2 K1-11 K2-11 K3-11
K5-11 K7-18 75 DSPD9 D7-17 E1-B3 K1-12 K2-12 K3-12 K5-12 K7-17 76 DSPPS D1-10 H1-26 K1-26 77 DSPR/W B1-6 E1-H11 C7-3 D1-3 F7-4 78 DSPSTAT A5-11 C56-T E1-D11 79 ENSPHI2 C3-11 K7-19 80 ENSPHI C3-8 H7-1 81
GND A1-9 A1-10 A1-11 A1-12 A1-13 A1-14 A1-15 A1-16 A2-7 A3-7 A4-7 A5-10 A5-13 A5-17 A5-2 A5-15 A5-4 A6-10 A7-10 B01-EDGE B31-EDGE B10-EDGE C73-B C52-B C99-B C53-B B2-7 B3-7 B4-7 B5-7 B6-7 B7-10 B7-1 B7-2 C1-7 C101-L C100-L C2-7 C3-7
C4-7 C5-7 C56-B C6-8 C6-5 C7-10 C7-1 C7-6 C7-8 D1-7 D2-7 D3-8 D4-8 D5-8 D6-8 D7-10 E1-B1 E1-K11 E1-L2 E4-10 E5-10 E6-8 E6-3 E6-5 E7-8 F6-7 F7-7 H1-14 H2-14 H3-14 H5-14 H6-10 H7-10 K1-14 K2-14 K3-14 K5-14 K6-10 K7-10 82 HOLDA B2-3 D1-6 D1-9
83 LB/HB B4-13 C1-9 D5-10 C4-5 84 MP/MC B1-5 A1-1 E1-A6 85 PROG/DATA A6-19 B6-9 B4-5 86 PUP1 B2-4 B2-10 B2-12 A2-1 B1-3 A2-10 C6-6 E1-H1 E1-B7 E1-G2 E1-F2 E1-G1 87 READY E1-B8 F7-3 88 SW1 B1-15 A1-2 B7-4 89 SW2 A1-3 B1-14 B7-6 90 SW3
A1-4 B1-13 B7-8 91 SW4 A1-5 B1-12 B7-11 92 SW5 A1-6 B1-11 B7-13 93 SW6 A1-7 B1-10 B7-15 94 SW7 B1-9 A1-8 B7-17 95 $A02-XEDGE/01 A02-EDGE A7-9 96 $A03-XEDGE/01 A03-EDGE A7-8 97 $A04-XEDGE/01 A04-EDGE A7-7 98 $A07-XEDGE/01 A07-EDGE A7-4 99 $A10-XEDGE/01 A10-EDGE B3-6 100 $A2-I2/02 A2-2 A3-6 101 $A2-08/02 A2-8 A3-5 102 $A2-09/02 A2-9 B2-2 103 $A22-XEDGE/01 A22-EDGE B7-18 104 $A23-XEDGE/01 A23-EDGE B7-16 105 $A24-XEDGE/01 A24-EDGE B7-14 106 $A25-XEDGE/01 A25-EDGE B7-12 107 $A27-XEDGE/01 A27-EDGE B7-7 108 $A29-XEDGE/01 A29-EDGE C6-3 109 $A3-I13/02 A3-13 B27-EDGE 110 $A3-I2/02 A3-2 B2-8 111 $A3-011/02 A3-11 B2-11 112 $A3-03/02 A3-3 B2-1 A2-13 113 $A3-08/02 A3-8 A2-11 114 $A31-XEDGE/01 A31-EDGE C6-1 115 $A4-I5/01 A4-5 A4-4 B3-5 A4-3 116 $A4-I9/01 A4-9 A4-10 C5-5 C6-15 117 $A4-011/11 A4-11 C3-9 C3-13 118 $A4-08/01 A4-8 B3-2 B3-1 119 $A7-B2/01 A7-2 A09-EDGE 120 $A7-B3/01 A7-3 A08-EDGE 121 $A7-B5/01 A7-5
A06-EDGE 122 $A7-B6/01 A7-6 A05-EOGE 123 $B1-T1/12 B1-1 E6-6 E6-7 E6-10 E6-4 124 $B3-I13/11 B3-13 B3-12 B3-10 B3-9 B4-10 125 $B4-I9/03 B4-9 B02-EDGE 126 $B4-012/05 B4-12 C1-13 127 $B4-02/02 B4-2 A3-12 128 $B4-04/04 B4-4 D4-7 D3-7 D6-7 D5-7 129 $B5-I12/01 B5-12 B5-9 C6-14 130 $B5-I2/01 B5-2 C6-7 131 $B6-I2/05 B6-2 B6-11 132 $B6-I5/05 B6-5 B4-6 133 $B6-03/05 B6-3 H6-19 H6-1 134 $B7-I3/01 B7-3 A11-EDGE 135 $B7-I5/01 B7-5 A28-EDG