Image analysis – Color image processing – Compression of color images
Reexamination Certificate
2000-07-28
2004-01-27
Patel, Jayanti K. (Department: 2625)
Image analysis
Color image processing
Compression of color images
C382S246000, C341S067000, C375S240230
Reexamination Certificate
active
06683980
ABSTRACT:
CROSS-REFERENCE TO RELATED APPLICATIONS
This application is related to commonly owned, co-pending application no. 09/628,658, filed on even data herewith, titled “System and Method for Storing Compressed Data onto a Storage Medium,” the full text of which is incorporated herein by reference as if reproduced below.
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates generally to the storage of data and, more particularly, to the compression, recording and playing of video data.
2. Related Art
Compression is the process of encoding an image such that it requires less space for storage. There are two fundamental ways to compress image data: lossy compression and lossless compression. Examples of lossy compression schemes include JPEG and MPEG. Lossy compression can provide a very high compression ratio. However, during the encoding process some data will be irreversibly lost. Consequently, a lossy encoded image will have some degradation of visual quality when expanded. Lempel-Ziv and Welch (LZW) encoding and Rice encoding are two well known lossless compression algorithms. Lossless compression usually results in compression ratios lower than those obtained with lossy compression. However, the benefit of compressing an image using a lossless compression scheme is that once expanded, the resulting image will be exactly as it was prior to being compressed.
Traditionally, with any compression algorithm, the compression ratio is data dependent. Accordingly, the compression ratio cannot be predicted. However, in certain instances, control of the compression ratio is desired. For example, a video cassette recorder (VCR) tape has a constant bandwidth capacity. Likewise, a hard disk array has a maximum data storage capacity; therefore, when recording data onto either storage device, it is highly desirable to control the compression ratio of the data. The importance of this control is even more evident when one considers the recent developments in the area of high definition television (HDTV).
As compared with conventional TV, HDTV signals have higher resolution and require more bandwidth for storage. For example, an HDTV image presented in 1080i format with 444 sampling and 8 bit resolution has a bandwidth of 1.5 Gbits/s. Present VCR tapes are unable to meet such storage demands. While recording devices and media (e.g., tapes, ROM cartridges, magnetic or optical disks) capable of recording HDTV images will be developed, compression will still be desirable, if not necessary.
A feature of HDTV is the high quality resolution of the images produced. Thus, any compromising of the visual image is not desirable. As already mentioned, lossy compression results in diminished video quality. Likewise, as one considers the bandwidth constraints imposed by storage media, it is evident that the use of a lossless compression scheme can also create problems. Consider the following explanation. The compressed bit streams of image sequences produced by lossless compression schemes often include bandwidth peaks. Bandwidth peaks are the result of producing a number of successive frames with a very low compression ratio. If the storage media, a VCR tape for example, lacked the capacity to store the bandwidth peak portions of the bit stream then the data would be lost. Buffering is used to avoid this scenario. Buffering, however, raises the potential for two additional problems: latency and buffer overflow, both of which result in lost data and/or diminished visual quality. Therefore, what is needed is a method for compressing data, in particular, high definition television image data, such that the resulting bit stream bandwidth is kept relatively constant and the image quality is not compromised. These results allow the bit streams to be recorded on a storage medium and viewed without diminished visual quality.
SUMMARY OF THE INVENTION
The present invention provides a system and method for recording data onto a storage medium such that it can be replayed to provide either a lossy quality or lossless quality presentation. Because there is some loss of visual integrity associated with a lossy presentation, this option is acceptable when the user intends to only preview the image or video sequence. The benefit of presenting a lossless quality presentation is that the decompressed image will be exactly the same as the original uncompressed image.
In order to view either lossy or lossless quality presentations, the compressed data must first be recorded onto a storage medium. Each image of a video sequence is processed by an encoder. The output of the encoder is a fixed length primary bit stream and a variable length supplemental bit stream. The size of the fixed length bit stream is chosen according to the write-bandwidth of the storage medium. As each of the primary bit streams are received, they are recorded directly onto the storage medium in real time. As each of the supplemental bit streams are received, they are written into temporary memory in real time. Once all of the primary bit streams are received and subsequently written onto the storage medium, the supplemental bit streams will be retrieved from the temporary memory and written onto the storage medium. After all of the bit stream data has been written onto the storage medium, a user can be prompted as to the mode of desired playback.
The viewing choices include either lossy quality or lossless quality. If the desired data presentation quality level is lossy then the primary bit stream of the saved compressed data is retrieved from the storage medium. The primary bit stream includes variable length portions and possibly fixed length portions of encoded data. The primary bit stream is provided to a decoder for decoding. If the desired data presentation quality level is lossless, then the supplemental bit stream will be retrieved first. The supplemental bit stream, which includes fixed length and possibly variable length data, is retrieved from the storage medium and written into temporary memory. Once all of the supplemental bit stream data has been written into temporary memory then both the primary bit stream data and the supplemental bit stream data is input into a decoder for decompression into lossless data.
Thus, the output from the decoder is either a presentation of the original image in lossy quality or lossless quality. The ability to choose the decoding quality makes this scheme a progressive image compression scheme.
The method for image compression (i.e., producing the primary and supplemental bit streams) comprises the steps of dividing the image into a plurality of regions. For each region, a plurality of adjacent pixels corresponding to one color component are selected and identified as a pixel sample set. Corresponding pixel sample sets from the plurality of regions are associated into a group.
For each selected pixel, a pixel value of the selected pixel is encoded to generate a fixed length token and a variable length token. The variable length tokens for each pixel value in the set are arranged to form a variable length token vector. Further, each of the fixed length tokens are arranged to associate each bit of a pixel value with corresponding bits of other pixel values within the set. A fixed length token vector is then formed from the corresponding bits of the plurality of fixed length tokens.
For each group, a first bit stream that includes the variable length token vector from each of the plurality of regions is formed. A second bit stream is also formed. This second bit stream includes the fixed length token vectors from each of the plurality of regions. Additionally, a primary bit stream of constant length is formed. If required, a supplemental bit stream of variable length will also be formed. Both the primary bit stream and the supplemental bit stream may include data from the first and second bit streams corresponding to each of the groups.
At a minimum, the primary bit stream will contain a portion of the variable length token vectors from each group. The variable length token vectors cor
Bernard Francis S.
Meier Fabian W.
Lee & Hayes PLLC
Microsoft Corporation
Patel Jayanti K.
Sukhaphadhana Christopher
LandOfFree
System and method for compressing data does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with System and method for compressing data, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System and method for compressing data will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3240882