Image analysis – Image compression or coding – Predictive coding
Reexamination Certificate
2000-08-22
2004-06-08
Couso, Jose L. (Department: 2621)
Image analysis
Image compression or coding
Predictive coding
Reexamination Certificate
active
06748116
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates generally to the field of signal processing. More specifically, the present invention relates to an apparatus and method for compressing and decompressing digital image files.
2. The Background Art
Various image compression/decompression systems are well known to those of ordinary skill in the art.
FIG. 1
is a top-level block diagram depicting an exemplary image compression/decompression system
100
in the context of the present invention. As shown in
FIG. 1
, exemplary image compression/decompression system
100
comprises an encoder
110
, a decoder
120
, and a channel
130
. Exemplary hardware architecture for an image compression computer system suitable for implementing an encoder
110
as shown in
FIG. 1
will be described later in this document with reference to FIG.
2
A. From a functional standpoint, encoder
110
comprises an input file
112
, which is processed by an image compressor
115
. Further details regarding various aspects of image compressor
115
will be provided throughout this document.
Still referring to
FIG. 1
, image compressor
115
produces a compressed file
135
that is transmitted via a channel
130
to an image decompressor
125
at a decoder
120
. The channel
130
may comprise a switched backbone such as the network commonly referred to as the Internet, any local or wide area network, or may simply comprise storage of the compressed file
135
into any suitable medium such as a hard drive, flash memory, CD-ROM disk, and/or floppy disk. From a functional standpoint, image decompressor
125
attempts to recreate the original input file
112
and produces an output image file
127
which may be stored on any suitable medium and/or displayed (e.g., on a screen, printer, etc.). Exemplary hardware architecture for an image decompression computer system suitable for implementing a decoder
120
as shown in
FIG. 1
will be described later in this document with reference to FIG.
2
B. Further details regarding various aspects of image decompressor
125
will be provided throughout this document.
As will be recognized by those of ordinary skill in the art, when the output file generated by image decompressor
125
is identical (or essentially identical, within the tolerances of each particular implementation) to the original input file
112
, the image compression system
100
is said to be “lossless.” On the other hand, when the output file generated by image decompressor
125
is different from (e.g., contains less information or detail than) the original input file
112
, the image compression system
100
is said to be “lossy.” As will also be recognized by those of ordinary skill in the art, without limitation, lossiness may be due to transmission of fewer pixels than the number of pixels present in the original image, to transmission of less spatial frequency information than is present in the original image, to quantization of intensity and/or color levels to fewer intensities and/or colors than are present in the original image, or to various combinations of the above factors. As will be described in more detail later in this document, embodiments of the present invention may implement either lossless or lossy image compression.
Currently, various types of wireless communication devices such as Personal Digital Assistants (“PDAs”) and cellular telephone handsets are beginning to support the transmission and reception of graphic images via data communication networks (such as the Internet). Data communication networks used to transmit such graphic images typically have significant bandwidth limitations, and such wireless communication devices typically exhibit significant limitations in terms of available processing power and memory. Moreover, current “standard” image compression/decompression systems known to those of ordinary skill in the art (e.g., JPEG, GIF, PNG) either exhibit a relatively low compression ratio or require relatively high processing power and/or memory at the image compressor and/or decompressor. Similarly, current “non-standard” image compression/decompression systems known to those of ordinary skill in the art (e.g., Binary Tree Predictive Coding, or “BTPC”) require high processing power and/or memory at the image compressor while its compression ratio is typically comparable to JPEG for natural Images and typically worse than GIF or PNG for graphics. Finally, image compression/decompression systems known to those of ordinary skill in the art typically exhibit good performance for a particular general class of image files (e.g., bilevel, grayscale, or color files), but exhibit relatively poor performance for one or more of the other general classes of image files.
Thus, there exists a need for an image compression/decompression apparatus and method which exhibits a high compression ratio while conserving transmission bandwidth, as well as conserving processing power and memory at the image compressor and/or decompressor, and which exhibits good performance across a broad spectrum of general image file classes. The present invention addresses this need. These and other features and advantages of the present invention will be presented in more detail in the following specification of the invention and in the associated figures.
SUMMARY OF THE INVENTION
An apparatus and method for compressing and decompressing digital image files is described. At the image encoder/compressor, an input image file, which may be of bilevel, grayscale, or color file type, is subdivided into one or more sub-images. Each sub-image may be separately compressed. In the case of grayscale or color input images, the input image may be pre-processed using a threshold parameter to quantize the intensity and/or color vectors into a compressed palette of intensities and/or color vectors. A forward transform is performed on each pre-processed sub-image, based on a binary quincunx image pyramid and a set of pixel value prediction equations. The output of the forward transform comprises a set of prediction error signals and a coarse low-band signal. Each of the prediction error signals and the coarse low-band signal are run length and/or tree encoded, and all of the outputs of the run length and/or tree encoders are combined into a single array, which is encoded using a Huffman coding algorithm or arithmetic coding algorithm. The output of the Huffman encoder or arithmetic encoder is written to a compressed output file in a format conducive to image reconstruction at the image decompressor. The compressed output file is stored and/or transmitted to an image decoder/decompressor. At the image decoder/decompressor, the encoding/compression process is reversed to generate a decompressed image file, which may be stored and/or displayed as appropriate. Embodiments of the system may implement either lossless compression or lossy compression, where lossiness may be due to transmission of fewer pixels than those present in the original image and/or by quantization of the pixel intensities and/or color vectors into fewer intensity/color levels than those present in the original image.
REFERENCES:
patent: 4222076 (1980-09-01), Knowlton
patent: 4654484 (1987-03-01), Reiffel et al.
patent: 5128791 (1992-07-01), LeGall et al.
patent: 5280343 (1994-01-01), Sullivan
patent: 5339368 (1994-08-01), Higgins-Luthman et al.
patent: 5798795 (1998-08-01), Glenn et al.
patent: 5930390 (1999-07-01), Coelho
patent: 5978517 (1999-11-01), Henry et al.
patent: 6125201 (2000-09-01), Zador
patent: 6233358 (2001-05-01), Acharya
patent: 0 535 571 (1993-04-01), None
patent: 0 535 571 (1993-04-01), None
patent: 1 005 231 (2000-05-01), None
patent: 00/03347 (2000-01-01), None
“Progressive Transmission of Grey-Scale and Binary Pictures by Simple, Efficient, and Lossless Encoding Schemes”, Ken Knowlton, Proceedings of the IEEE, vol. 68, No. 7, Jul. 1980, pp. 885-896.
“Reversible Intraframe Compression of Medical Images”, P. Roos, M.A. Viergever, M.C.A. Van Duke, and J. H. Peters, IEEE Transactions on Me
AirZip, Inc.
Couso Jose L.
Ritchie David B.
Thelen Reid & Priest LLP
LandOfFree
Apparatus and method for compressing and decompressing image... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Apparatus and method for compressing and decompressing image..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Apparatus and method for compressing and decompressing image... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3348290