Image analysis – Image compression or coding – Including details of decompression
Reexamination Certificate
1999-12-30
2003-01-21
Tran, Phuoc (Department: 2621)
Image analysis
Image compression or coding
Including details of decompression
C382S245000, C341S059000
Reexamination Certificate
active
06510248
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates to an improved apparatus and method, for real-time decoding, or decompressing, a sequence of compressed words which are structured to have non-uniform lengths. More specifically, the present invention relates to a so-called run-length decoder with an improved structure, so as to effectively contain a corrupted code word within its own length and thus keeping it from further propagation during the real-time decoding process. The method disclosed in the present invention is most advantageous for decompressing multimedia data, which are typically vast in size but have become an important everyday item in today's digital age. Another advantage of the present invention is that the error containment is achieved during the decoding process without requiring major additional computational efforts, and thus can be implemented with low-end machines in a very cost-effective manner.
BACKGROUND OF THE INVENTION
Multimedia, or image, data such as those used in CD, DVD, MP3, and eventually digital TV, have become increasingly popular in today's computer and communication systems. Because of the vast amount of data involved, which create a very heavy burden to the memory storage space and/or the transmission bandwidth, data compression is typically required so as to reduce the memory storage and/or bandwidth requirement. As a result, multimedia data are typically compressed before they are stored in the memory or transferred into the communication channel. These compressed data must be de-compressed, or decoded, before they can be put is use. In order to achieve real-time or near-real-time decoding, the decoding algorithm must be relatively simple, and must be done on a sequential basis. Batch programs such as MPEG, JPEG, etc. require relatively large buffer space, and may not be adaptable for a wide variety of machines.
In order to maximize the data compression efficiency, the compressed codes typically do not have a uniform length. This can cause problems in that if one coded (compressed) word is corrupted due to noise in the storage media or communication channel, the decoding of the entire data can be affected rendering it useless. One of the ways to ameliorate this problem is to implement a line-based compression rule, which compresses the image data on a line-by-line basis, and inserts a line_end_code at the end of each line of codes. Thus, if a code is corrupted, it will be contained in the line containing the same. The entire line will be ignored, but the rest of the image data is designed to remain unaffected.
One of the most frequently used line-based compression methods is called run-length compression method. Basically with this method the compressed code comprises three portions: (1) the range of number of pixels (or bits) having the same value; (2) the exact number of the pixels contained in the un-compressed code; (3) the pixel data. Both portions (1) and (2) are of variable lengths. Portion (1), which also provides information regarding the total length of the code word, typically contains an even number of zeros, and Portion (2) contains the exact number of bits required to represent the number of pixels within the range indicated in Portion (1) which have the same value. Portion (1) can be omitted if the number of same value pixels is very small (typically from 1 to 3). An example of the run-length compression method is described below. This example is based on a maximum 16-bit compressed code, which is also the length of the data stream being processed by the decoder.
(A) The Compressed Code Represents 1 to 3 Pixels with the Same Pixel Value (Code Word 0)
These pixels are represented by the following code word:
bit position
d0
d1
d2
d3
content
# of total
pixel data
pixels
(B) The Compressed Code Represents 4 to 15 Pixels with the Same Pixel Value (Code Word 1)
These pixels are represented by the following code word:
bit position
d0
d1
d2
d3
d4
d5
d6
d7
content
0
0
# of total pixels
pixel data
(C) The Compressed Code Represents 16 to 63 Pixels with the Same Pixel Value (Code Word 2)
These pixels are represented by the following code word:
bit
position
d0
d1
d2
d3
d4
d5
d6
d7
d8
d9
d10
d11
content
0
0
0
0
# of total pixels
pixel data
(D) The Compressed Code Represents 64 to 255 Pixels with the Same Pixel Value (Code Word 3)
These pixels are represented by the following code word:
bit position
d0
d1
d2
d3
d4
d5
d6
d7
d8
d9
d10
d11
d12
d13
d14
d15
content
0
0
0
0
0
0
# of total pixels
pixel data
(E) The Compressed Code Represents Same Pixels to the End of Line (Code Word 4)
These pixels are represented by the following code word:
bit position
d0
d1
d2
d3
d4
d5
d6
d7
d8
d9
d10
d11
d12
d13
d14
d15
content
0
0
0
0
0
0
0
0
0
0
0
0
0
0
pixel data
Code Word 4 is also considered as the line_end-code.
If the byte alignment is not accomplished when the description of pixels on one line is completed, a dummy data of 4 bits 0000b is inserted for adjustment.
When the image data are coded according to the above-mentioned example, the decoder typically comprises a shifter, a code word comparator, a shift_number generator, and a code interpreter. Because this method implements a 16-bit decoding operation, the shifter requests and receives 16-bit data stream from a data bus, typically a 32-bit data bus. The code word comparator checks the number of leading even-numbered zeros in the first portion of the code word to determine the number of bits in the second portion, i.e., after the leading zeros in the first portion. Since the bit number in the third portion is fixed, i.e., always two bits, the total number of bits in the code word being compared in the comparator can be determined. The comparator then sends the bit count data to the shift_number generator, which sends a new_shift_number (which is the same as the bit count of the code word being compared) to the shifter. The shifter then shifts the data stream stored therein according the new_shift_number, and a new 16-bit data stream is sent to the code word comparator from the shifter. The shifter also sends a request for a new 32-bit image data when the data stored therein is about to be exhausted due to the bit shifting.
The length of each code word according to the run-length method is not fixed. Different repeat pixel patterns will result in different lengths of the resulting code words. Each line is terminated with a line_end_code, this compression rule is line-based, i.e., it compresses the image date on a line by line basis. Due to noise that may be present in the storage medium or communication channel, the code word may be corrupted. If the corruption occurs in the first portion, i.e., the portion which contains leading zeros to determine the length of the code word, not only this particular code word will not be interpreted correctly, all the image data that follow will also be affected.
SUMMARY OF THE INVENTION
The primary object of the present invention is to develop an improved decoding method and device to decompress image data that have been compressed according to the run-length technique. More specifically, the primary object of the present invention is to develop an improved run-length based decoding method which will prevent the propagation of a corrupted code word into the rest of the image data by containing the error within the length of the code.
According to the run-length compression method an image data is compressed by grouping pixels with the same value into a compressed code word. Each compressed code word comprises three portions:
(1) 0 to N-m bits to indicate the number of bits corresponding to the range of the number of pixels having the same value (in the uncompressed image data), where N is the number of bits of the data stream being decoded and m is the number of bits taken up by the pixel data. The range of the number of repeat pixels, as represented by the bit number of portion (1) also tells the number of bits reserved for Portion (2), which is dictated by the maximum possible number of repeat pixels within the range indicat
Liauh W. Wayne
Tran Phuoc
Winbond Electronics Corp.
LandOfFree
Run-length decoder with error concealment capability does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Run-length decoder with error concealment capability, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Run-length decoder with error concealment capability will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3035522