Image analysis – Image compression or coding – Shape – icon – or feature-based compression
Reexamination Certificate
1997-12-15
2003-03-04
Johnson, Timothy M. (Department: 2623)
Image analysis
Image compression or coding
Shape, icon, or feature-based compression
C382S199000, C382S253000
Reexamination Certificate
active
06529635
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates to the field of image processing, and more particularly to a method and apparatus for image compression.
BACKGROUND OF THE INVENTION
Modern computer systems are often required to transmit large amounts of image data across relatively low bandwidth communication channels. Consequently, to reduce the amount of bandwidth consumed per image transmission, images are often compressed using one of a number of compression techniques.
In one image compression technique, called “vector quantization”, digitized imaged are resolved into small blocks of pixels represented by vectors. Vectors are values that convey color and intensity information. For example, a common type of vector is an RGB vector (i.e., red, green, blue) that indicates the average intensities of red, green and blue colors in a pixel block. In a vector quantization system, each vector of an image is replaced by an index to a table called a codebook. A codebook is a table containing a relatively small number of vectors that can be used to represent vectors in an input image. For each vector in the input image, the codebook is searched to find a representative vector and the address of the representative vector, i.e., a code book index, is transmitted in place of the input vector. Because the codebook indices are smaller than the image vectors, substituting the indices for the image vectors effectively compresses the representation of the image and reduces the bandwidth required to transmit the image. In a receiving device, the codebook indices are used to look up representative vectors in another codebook that is the same as or similar to the codebook used to compress the original image. The representative vectors are then used to construct an output image.
FIG. 1
is a block diagram of a prior art system that performs vector quantization. The system includes an encoder
11
that encodes (i.e., compresses) an input image
12
, then transmits the encoded image to a decoder
21
. The decoder
21
decodes the encoded image to generate an output image
26
. In many cases, the encoder
11
and the decoder
21
are realized by computers programmed to implement corresponding compression and decompression algorithms.
The encoder
11
typically contains a preprocessor
16
, a vector quantizer
18
, a codebook
17
and a transmitter
19
. The preprocessor
16
is used to reduce the amount of image data that is processed by the vector quantizer
18
, for example, by filtering high frequency components from the input image
12
. The preprocessed image is supplied to the vector quantizer
18
which identifies representative vectors in the codebook
17
that, by some measure, are a best match for vectors in the preprocessed image. Because the codebook
23
in the decoder
21
is typically the same as or similar to the codebook
17
in the encoder
11
, addresses of the representative vectors in the codebook
17
, i.e., codebook indices, may be transmitted to the decoder
21
and used to look up the representative vectors in the codebook
23
. The representative vectors are then used to generate the output image
26
. In some implementations, a post processor
25
may perform additional processing (e.g., pixel-block up-sampling, dithering, etc.) to produce the output image
26
.
Because the number of representative vectors in the codebook
17
is usually small relative to the total number of possible input vectors, the bit size of each codebook index is correspondingly smaller than the bit size of the input vectors. For example, if each input vector is a 24-bit value (e.g., a “true color” value in which red, green and blue intensities are each represented by a respective one of three bytes) and the codebooks (
17
and
23
) each contain 256 representative vectors, then a one-byte codebook index can be used to represent each of the three-byte input vectors. This is a 3:1 reduction of the amount of data used to represent the preprocessed image.
One disadvantage of the above-described image compression technique is that the overall compression that can be achieved is limited by the vector-based approach. More specifically, because input images are decomposed into pixel blocks for vector quantization, patterns within the images that could otherwise be exploited for compression purposes may not be recognized. As a result, the overall compression achieved by the above described compression technique may be less than the compression possible with a non-vector-based approach.
SUMMARY OF THE INVENTION
A method and apparatus for compressing a digitized image are disclosed. Boundaries of regions within a digitized image are identified and shapes are selected from a bank of shapes to represent the regions based on the identified boundaries. Position and size information is associated with the selected shapes based on the position and size of the regions within the digitized image. Values indicating the selected shapes and the associated position and size information are transmitted as a representation of the digitized image.
Other features and advantages of the invention will be apparent from the accompanying drawings and from the detailed description that follows below.
REFERENCES:
patent: 4783841 (1988-11-01), Crayson
patent: 4868653 (1989-09-01), Golin et al.
patent: 4922545 (1990-05-01), Endoh et al.
patent: 5008748 (1991-04-01), Carr et al.
patent: 5014334 (1991-05-01), Fukuhara et al.
patent: 5111392 (1992-05-01), Malin
patent: 5204899 (1993-04-01), Israelsen et al.
patent: 5225904 (1993-07-01), Golin et al.
patent: 5408542 (1995-04-01), Callahan
patent: 5455680 (1995-10-01), Shin
patent: 5487116 (1996-01-01), Nakano et al.
patent: 5506937 (1996-04-01), Ford et al.
patent: 5526295 (1996-06-01), Astle
patent: 5539841 (1996-07-01), Huttenlocher et al.
patent: 5740281 (1998-04-01), Makato Hirai
patent: 5751852 (1998-05-01), Marimont et al.
patent: 5805221 (1998-09-01), Min-Sup Lee
patent: 5809179 (1998-09-01), Marimont et al.
patent: 5933535 (1999-08-01), Lee et al.
patent: 6072910 (2000-06-01), Maeda et al.
Corwin Susan Julia
Fletcher Thomas D.
LandOfFree
Shape-based image compression/decompression using pattern... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Shape-based image compression/decompression using pattern..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Shape-based image compression/decompression using pattern... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3032294