Image analysis – Image compression or coding – Lossless compression
Reexamination Certificate
1998-09-25
2002-05-28
Tran, Phuoc (Department: 2621)
Image analysis
Image compression or coding
Lossless compression
C382S232000
Reexamination Certificate
active
06396958
ABSTRACT:
BACKGROUND
The present invention relates generally to communication systems and methods, and more particularly, to an image compression technique for use with image transmission or communication systems and methods that employs low entropy coding of images and error correction.
Image compression techniques have used several schemes to reduce the number of bits required to store or transfer images. When the images are sent over a communication link there is a possibility of introducing errors.
One technique for compressing images is a transform compression scheme. One transform used in many applications is a discrete cosine transform. Another transform that is used is a wavelet transform. The compression process begins by organizing an image into blocks that are convenient for the transform. For JPEG images, the transform is an 8×8 discrete cosine transform. The result of the image transformation is that most of the energy in the image is captured in low frequency elements of the transform.
The quantization of the transform values introduces errors in the reconstructed image and reduces the information in the image. The amount of the quantization and the technique for quantizing establishes many parameters of the compression. A typical technique involves weighting the transform values according to the frequency, then rounding the transform values to form integers. While truncation may be used, good practice uses rounding since it reduces the amount of the error.
Entropy encoding attempts to use long code words for rare image transform values and very short code words for image transform values that occur often. If the transform matches the image well, the bulk of the energy of the image is captured in a few of the coefficients in a block. The remainder of the coefficients are zero or nearly zero. Since so many quantized coefficients are zero or nearly zero, these coefficients are assigned code values that are very short.
The entropy coded coefficients are typically ordered by the “frequency” associated with the coefficient. For JPEG lossy compression, the ordering from low frequency to high frequency selects the coefficients in a zigzag pattern over a rectangular array of coefficients that are the output of the transform. The ordering is important, since it organizes the low frequency coefficients where much of the information of the image is concentrated first and leaves the low information, or “low entropy”, coefficients until last.
The low entropy portion of the image is a part of the image where many of the values of the quantized transform are the same or nearly the same. The higher frequency coefficients of the quantized transform have many values that are zero or nearly zero, corresponding to the low entropy portion of the image. If the entropy encoding is restricted to encoding the coefficients one at a time, the smallest number of bits per pixel is one.
The number of bits for the low entropy portion of the quantized transform can be strongly reduced by using “run length encoding”. When there are many values in a row that are zero, the run of zeroes may be replaced by a special code word followed by the number of zeroes in the string. In this way, a few bits may be used to represent large numbers of pixels in the low entropy part of the image.
With run length encoding, the number of bits per pixel may be reduced to less than one on the average. An image that uses 10 bits per pixel for the image values may be compressed 20:1 to one half bit per pixel on the average. For a large class of images, 20:1 compression yields very pleasing restored images.
An alternative scheme for entropy encoding was suggested by Said and Pearlman in “A new, fast, and efficient image codec based on set partitioning in hierarchical trees,” IEEE Trans on Circuits and Systems for Video Technology, Vol. 6, No. 3, June 1996, page 243-250. The quantized transform is first organized by “zero tree” association of the transform values. This association starts with the lowest frequency coefficient and for each coefficient associates the higher frequency coefficients for that location on the image. Since the wavelet transform usually has a 2:1 downsample between levels, each coefficient at the lowest frequency has four coefficients in each of the three next higher frequency set of coefficients associated with the same point. The zero tree ordering of the coefficients results in a natural ordering of the coefficients by frequency. The ordering is important for the Said and Pearlman approach to compression. An alternative for the wavelet transform is to transmit each of the blocks of frequency coefficients independently, starting with the lowest frequency block.
The quantized transform is organized by bit planes. The most significant bit of each quantized transform coefficient in a block is encoded first. In an area where there is much energy, many of the bits may be ones. If the quantized transformed values are organized by frequency, this area is the low frequency parts of the quantized transform.
The higher frequency areas of the high order bits are almost all zero. The result is an ideal application of run length coding. The bit plane for the block is transmitted by sending the first part of the block, then sending the end of the block using run length coding when there are no more ones in the bit plane. The next bit plane is similarly encoded by sending the bits of the bit plane ordered by frequency until there are no more ones in the bit plane, then sending a run length coded string of zeroes.
This technique can be controlled to achieve a given signal-to-noise ratio or a given compression ratio for each block by terminating the bit plane compression at a convenient point depending on the attribute desired. The remainder of the bits are not sent, corresponding to an effective quantization of the image.
When the image is sent through a communication channel, bit errors may be introduced. Bit errors cause the entropy decoder to lose synchronization with the data stream. Until synchronization is reestablished, there are a large number of pixels that are decoded in error. The decoder is typically re-synchronized by adding special markers to the beginning of a line or the beginning of a block. Many fewer lines or blocks will be in error if the transmission scheme reduces the number of transmission errors to a small value. This is achieved by the present invention. At the same time, it would also be desirable to use error correction to improve the image compression by improving the low entropy coding.
From the above, it can be seen that previous techniques use a relatively inefficient run length coding technique for low entropy coding that has minimal resistance to errors in communication. Therefore, it would be an improvement to have image transmission system and method comprising an image compression technique that uses error correction to reduce errors in communication over a communication channel while improving the compression of the image.
SUMMARY OF THE INVENTION
To meet the above and other objectives, the present invention provides for a system and method that introduces intentional errors into a compression scheme for images. The intentional errors along with error correction processing enable much improved low entropy encoding of the images. The error correction also serves to reduce the errors in transmission over a communication channel. Furthermore, the present invention uses error correction to improve the compression by improving the low entropy coding.
The system and method compresses images and performs error correction on images that are transmitted through the communication channel that introduces errors into the transmitted data. The present invention thus provides for a technique that improves low entropy coding of images by using an error-correction encoding.
More particularly, the present invention provides for an image transmission system and method. In the system and method an image is blocked to create a plurality of image blocks. The image blocks are transform coded to prod
Alavi Amir
Float Kenneth W.
Lockheed Martin Corporation
Tran Phuoc
LandOfFree
Image transmission system and method employing compression... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Image transmission system and method employing compression..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Image transmission system and method employing compression... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2872945