Image analysis – Image compression or coding – Parallel coding architecture
Reexamination Certificate
1997-04-15
2001-09-04
Chen, Wenpeng (Department: 2624)
Image analysis
Image compression or coding
Parallel coding architecture
C382S244000, C358S426010
Reexamination Certificate
active
06285790
ABSTRACT:
BACKGROUND OF THE INVENTION
The present invention relates to the field of data compression, more specifically to compression of palletized image data.
Most research in image compression assumes a continuous-tone grayscale or color image is being compressed. With a continuous-tone image, a small error in the value of a pixel results in a small shift in color of that pixel. Palettized (or “indexed”) images differ from continuous-tone images in that a small error in a pixel value might result in a completely different color. This is because the color value of a pixel is an index into a table of colors (palette). In the printing industry, palettized images are often referred to as “spot color” images. As should be apparent, the problems of highly compressing palettized images losslessly is also a problem in the printing industry.
With palettized images, generally no information about the eventual color of a pixel can be determined by the pixel's color value, without reference to the table of colors. While this might appear to be a drawback, it is quite useful where more than one image is used in a system where the only difference is the color table. For example, the negative (inverse) image of a palettized image can be obtained by merely replacing the colors in the color table with their inverses.
One drawback of palettized images is that they cannot be compressed by a lossy compression process, but must be compressed losslessly. Lossy compression processes are generally favored for image compression, since they generally provide high compression for little effort. A palettized image comprises two parts, the two dimensional array of pixel color values and the table of colors used to translate the pixel color values into colors, however since the table of colors requires much less memory than the array of pixel color values, compression is often only applied to the array of pixel color values with the table of colors included uncompressed with the compressed image.
The Gormish/Boliek application shows one method for efficiently compressing palettized images at high compression rates. Highly compressed palettized images are needed in many applications, such as game cartridges, which need storage for the images used in a game (video game, hand-held player, computer game, etc.). Highly compressed palettized images are also desirable for use with on-line services and the “information superhighway.” The World Wide Web (WWW) is becoming an increasingly popular form for disseminating information over the Internet. In part, the popularity of the WWW stems from the fact that the basic units of the WWW are HyperText Mark Up Language (HTML) documents, which can include imbedded graphics with text. These documents often include images which are palettized. Many users of the World Wide Web access these documents using a personal computer to connect to the Internet via a modem over ordinary telephone lines. With this configuration, a user is limited to data rates of 14,400 bits/sec or 28,800 bits/sec.
Thus, for timely reception of complex palettized images, the ability to highly compress these images for transmission is key to the continued popularity of the WWW. Although faster modems are being designed, there is already a demand for more complex graphics, and therefore compression will be necessary in the foreseeable future. Many images used in the WWW are stored and transmitted as Graphical Interchange Format (GIF) files, which uses Ziv-Lempel compression. Ziv-Lempel compression treats the image as a one-dimensional sequence of index values, ignoring the two-dimensional nature of image data.
Therefore, what is needed is a compression apparatus and method which uses the nature of palettized image data to highly compress the image data, as well as a corresponding decompressor.
SUMMARY OF THE INVENTION
The present invention provides improved compression of palletized image data by compressing (coding) the image data by color (for two-dimensional images, this is also referred to as “coding by color plane”). A color plane for a nonbinary image is a binary image in which each pixel color value of the nonbinary image is replaced by a bit indicating whether or not that pixel is “in” that color plane. A pixel is in a color plane if the pixel's color value is equal to a color value associated with the color plane. According to the invention, a compressor codes a first color plane, then codes a second color plane, and continues coding each subsequent color plane, until all the color planes which have pixels in them are coded except for the “last” color plane. In coding each color plane, pixels which are in previous color planes are ignored since a pixel can only be in one color plane. Because each coded color plane is a binary array, it can be coded by a binary image coder.
In decoding, the color planes are decoded in the same order. The first color plane is decoded and indicates which pixels are in the first color plane, then the second color plane is decoded to indicate which pixels are in the second color plane and which are in subsequent color planes (the coded second color plane gives no indication of which pixels are in the first color plane, nor does it need to). Once all but one coded color plane has been decoded, a decompressor infers that any remaining pixels are of the last color.
Of course, color plane coding of nonbinary images requires more passes than other coding such as bit plane coding. For example, an 8-bit color image is coded in 8 passes with bit plane coding, but might require up to 255 passes for a given pixel with color plane coding. To minimize the number of passes required, the color planes are ordered by density and the densest color plane is coded first, where density refers to the density of pixels in a color plane relative to the total number of pixels in the image. As explained above, a pixel is coded by representing it by a binary indication of whether or not the pixel is in the color plane being coded. After the first color plane is coded, pixels which are known to have colors of previously coded color planes are not coded. By coding the densest color planes first, the total number of passes is reduced.
In an alternate embodiment, each pixel color value is represented by a vector, and the components of the vectors are separately coded by “subcolor” planes, where each subcolor plane contains all the pixels which have a vector component value equal to the value for that subcolor plane. In this way, an image can be easily compressed in parallel.
In another alternate embodiment, each color plane is coded until a threshold number of pixels coded is reached, and then the remaining pixels are coded by bit plane.
An entropy coder uses context information to improve compression a pixel by optimizing the code used to code that pixel based on the likelihood of that pixel occurring given the pixel's context. Typically, in an image, the context of a pixel might be determined in part by its neighboring pixels. Where the image data is a collection of smaller images, such as sprites, characters, or a graphical menu, some neighboring pixels might be independent of the pixel being coded, so the context information includes pixel position information to further improve compression.
Because a coder requires more passes with color plane coding than with other coding schemes, a fast entropy coder is used. One such fast coding system is that taught by U.S. Pat. No. 5,272,478 (issued to Allen, et al. and assigned to the assignee of the present invention), which teaches the use of a B-coder as the bit generator for the above compression process. Alternatively, the Q-coder developed by IBM of New York, or the high-speed binary entropy coder taught by U.S. Pat. No. 5,381,145 (issued to Allen, et. al. and also assigned to the assignee of the present invention).
The present invention also provides novel apparatus for performing parallel encoding and decoding. In one embodiment, an image is divided into bands, one per coder. Each coder operates independently of the others. If necessar
Albert Philip H.
Chen Wenpeng
Ricoh & Company, Ltd.
Townsend and Townsend / and Crew LLP
LandOfFree
Data compression for indexed color image 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 Data compression for indexed color image data, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Data compression for indexed color image data will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2520532