Image analysis – Color image processing – Compression of color images
Reexamination Certificate
1998-10-27
2003-07-15
Johnson, Timothy M. (Department: 2625)
Image analysis
Color image processing
Compression of color images
C358S001150
Reexamination Certificate
active
06594385
ABSTRACT:
CROSS REFERENCE TO RELATED APPLICATIONS
This application includes subject matter related to co-pending application entitled: “System For Compression Of Digital Images Comprising Low Detail Areas”, having U.S. Pat. No. 6,130,630, and the co-pending patent application entitled: “Apparatus And Method For Compressing Huffman Encoded Data”, having U.S. Ser. No. 09/179,925, each of which are incorporated by reference herein, assigned to the same assignee as this application, and filed on even date herewith.
FIELD OF THE INVENTION
This invention relates to the compression of digital images, and more particularly to the compression of a digital image comprising a background.
BACKGROUND OF THE INVENTION
A digital image is typically displayed or printed in the form of a rectangular array of “picture elements” or “print elements”. For purposes of this application, both “picture elements” and “print elements” are referred to herein as “pixels”. Digital images are typically represented in a computer by one or more arrays of binary numbers. For example, a monochrome digital image can be represented in a computer by a single array of binary numbers. Each binary number in the array defines a gray-level value for an associated pixel. The position of the binary number in the array describes the spatial location of the pixel.
A color digital image can be represented in a computer by three arrays of binary numbers. Each array (alternatively referred to herein as an “image plane”) representing an axis of a suitable color coordinate system in accordance with the well known trichromatic theory. The color of a pixel in the digital image is defined by an associated binary number (defining one of three color components from the color coordinate system) from each array. It is noted that there are many color coordinate systems that can be used to represent the color of a pixel. These color coordinate systems include a “Red-Green-Blue” (RGB) coordinate system and a cyan-magenta-yellow (CMY) coordinate system. The former is commonly used in monitor display applications, the latter is commonly used in printing applications. For purposes of this application, each binary number representing a pixel is referred to herein as a “pixel component” or alternatively as a “pixel component value”. In addition, the phrase “pixel value” refers to the value of the number or numbers defining the pixel. It is noted that a pixel value can be defined with reference to the color of the pixel. Thus, a pixel can be said to have a value corresponding to the color or gray-scale level of white. This indicates that the binary number or numbers associated with the pixel has a total value that define the pixel as white.
The amount of data used to represent a digital image can be extremely large. Consider, for example, a color digital image consisting of 1024×1024 pixels. If the pixels are represented in the computer by three image planes of 8-bit numbers, the digital image would occupy over 1 megabyte of storage space.
The large amount of data required to represent a digital image in a computer can result in significant costs that are associated both with increased storage capacity requirements, and the computing resources and time required to transmit the data to another computing device. In order to reduce these costs, digital image compression techniques have been and are continuing to be developed.
Digital image compression techniques can generally be divided into two classes: lossless and lossy. In lossless compression, the digital image reconstructed after compression is identical, pixel by pixel, to the original image. A common lossless compression technique is the well known Lempel-Ziv-Welch (LZW) compression scheme. See, for example, U.S. Pat. No. 5,479,587. That Patent is incorporated herein by reference. Another lossless compression technique is described by the “Joint Bi-level Image Experts Group Compression standard” (JBIG).
In lossy compression, the reconstructed digital image may be somewhat degraded with respect to the original digital image in order to attain higher compression ratios than those of lossless procedures. One popular lossy compression scheme is referred to as “transform coding”. See Baxes, G. A.,
Digital image Processing, Principles and Applications
, pp 198-211, ISBN 0-471-00949-0 (1994). Those pages are incorporated herein by reference.
In general, transform encoding is accomplished by decomposing each image plane of a digital image into a set of two-dimensional blocks of pixel component values that define a sub-array of pixels. These blocks are typically small, such as 4×4 or 8×8 blocks of component values. Each block is then transformed into the frequency domain by use of a frequency transform. This reduces the block into a series of basis functions. It is noted that typically the first basis function is a constant scalar value. This is sometimes referred to as the “DC” component or alternatively as the “DC coefficient” for the transform. While in the frequency domain, the amount of data required to represent the block can be reduced by quantization. This is often accomplished by using criteria based on the visibility of each basis functions. After quantization, the amount of data representing the block can be even further reduced by using an entropy encoding (e.g., Huffman coding) technique.
A number of transform coding schemes have been developed. One widely used transform coding scheme has been standardized by the published and generally available works of the Joint Photographic Experts Group (JPEG). See generally, Pennebaker, W. B., and Mitchell, J. L.,
JPEG: Still Image Compression Standard
, ISBN 0-442-01272-1 (1993). The JPEG compression standard in lossy mode makes use of the Discrete Cosine Transform (DCT). Like many transform coding schemes, the JPEG compression scheme is adjustable. That is to say that the number of frequency components discarded during quantization can be varied to produce variable compression ratios. Unfortunately, however, as the level of quantization increases to achieve higher compression ratios, image quality can be degraded significantly.
As just discussed, digital image compression techniques can be used to reduce the amount of data required to represent a digital image in a computer. These techniques can reduce the computing costs associated with storing and transmitting digital images. There are, however, significant costs that can be incurred in using these compression techniques. For example, there can be substantial system overhead and time required to perform the compression and decompression operations. In addition, there is a trade off between the use of lossy compression techniques and lossless compression techniques. In general, lossy compression can be used to achieve high compression ratios. Image quality, however, can be significantly degraded. Lossless compression, on the other hand, does not degrade image quality but usually results in relatively low compression ratios.
SUMMARY OF THE INVENTION
An apparatus for compressing a digital image comprising pixels having a first value and comprising a means for decomposing said digital image into a set of tiles; and a means for compressing each tile from said set of tiles, wherein said compressing means responsive to a binary tile from said set of tiles, said binary tile comprising pixels having a background value and pixels having one other value, to generate a first and an associated second set of data, said first set of data comprising spatial location information for substantially all pixels in said binary tile having said background value and said second set of data comprising data representative of a compressed second tile, each pixel in said second tile having said one other value.
REFERENCES:
patent: 4366505 (1982-12-01), Tsuda et al.
patent: 5014198 (1991-05-01), Umemura
patent: 5552898 (1996-09-01), Deschuytere
patent: 5661570 (1997-08-01), Nomura
patent: 5673370 (1997-09-01), Laney
patent: 5706368 (1998-01-01), Mita
patent: 5742704 (1998-04-01), Suzuki et al.
patent: 575474
Bradburn Brent M.
Grohs Randall E.
Hewlett--Packard Development Company, L.P.
Johnson Timothy M.
Wade Matthew L.
LandOfFree
Image compression of background and text tiles 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 compression of background and text tiles, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Image compression of background and text tiles will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3062774