Image analysis – Image compression or coding – Pyramid – hierarchy – or tree structure
Reexamination Certificate
2000-08-30
2004-01-13
Couso, Jose L. (Department: 2621)
Image analysis
Image compression or coding
Pyramid, hierarchy, or tree structure
Reexamination Certificate
active
06678422
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates to methods and apparatus for performing compression on image data, by wavelet transformation of the image data followed by quantization and encoding. In preferred embodiments, the invention is a method and apparatus for performing compression on image data (e.g., image data generated by a document scanner) in a manner allowing fast decompression, by wavelet transformation of the image data (in a manner imposing low memory requirements) followed by quantization and encoding.
BACKGROUND OF THE INVENTION
It is well known to perform image compression on digital image data to generate a reduced set of compressed data from which each original image (determined by the uncompressed data) can be reconstructed without loss of essential features. An inverse transformation (decompression) can be applied to compressed image data (e.g., following transmission or storage of the compressed image data) to recover data indicative of each image determined by the original data (or a reasonable facsimile of each such image).
In color imaging devices, each pixel of an image is determined by three color component values (e.g., red, green, and blue values). The three sets of color component values that determine an image are typically processed separately. Digital data that determines a pixel of a color image comprises three color component words, each of which is a multi-bit digital word determining a color component sample (e.g., a red, green, or blue sample of an analog image representation).
Throughout the specification, including in the claims, “block” denotes an array of N×M samples (N columns and M rows of samples, where N and M are integers) of a given color component, and “word” denotes a multi-bit digital word that determines a color component sample (e.g., a blue sample of an analog image representation) or a coefficient generated by performing a transform on a set of color component samples (e.g., one of the coefficients generated by performing a discrete cosine transform or wavelet transform on a row or column of blue samples of an analog image representation).
It should be appreciated that throughout this disclosure, the orthogonal dimensions of a block of data are arbitrarily denoted as “rows” and “columns.” Thus, the rows and columns of a block can equally well be denoted as “columns” and “rows,” respectively, Similarly, a method in which a “horizontal” filtering operation is performed on rows of a block (to generate filtered data) and a “vertical” filtering operation is then performed on columns of the filtered data can equivalently be described as a method in which a “vertical” filtering operation is performed on columns of the same block (if the rows are relabeled as columns) to generate the same filtered data and a “horizontal” filtering operation is then performed on rows of the filtered data. Thus, a method comprising sequential horizontal and vertical filtering operations (each vertical filtering operation following a horizontal filtering operation) can equivalently be described as a method comprising sequential vertical and horizontal filtering operations (each horizontal filtering operation following a vertical filtering operation).
Typical methods for performing lossy image compression on image data include three steps: an image transform step which generates transform coefficients by performing a transform on the image data (e.g., a discrete cosine transform or wavelet transform); followed by a quantization step which replaces each transform coefficient with a quantized coefficient comprising fewer bits on the average (e.g., a scalar quantization step in which each of the coefficients is divided by the quantization step size); and finally an entropy encoding step in which the quantized coefficients are replaced by code words (e.g., a Huffman encoding or arithmetic encoding operation, in which the quantized coefficients that occur more frequently are replaced by relatively small code words and the quantized coefficients that occur less frequently are replaced by relatively large code words).
Decompression of compressed image data is the inverse of compression, and includes an initial decoding step (in which the entropy encoded code words that comprise the compressed data are decoded); followed by an inverse quantization step (in which inverse quantization is performed on the decoded data); and finally an inverse transform step (performed on the data resulting from the inverse quantization) which reconstructs the original image data.
With reference to
FIG. 1
, in a conventional three-stage wavelet transform, a “horizontal” wavelet transform is initially performed on each row (sometimes referred to as a “line”) of a block (typically an M×M block) of input image data (block
1
of
FIG. 1
) to convert each row into two vectors, z
L
and z
H
, each comprising M/2 coefficients (coefficient words). All the vectors z
L
together define coefficient block “L” (having M rows and M/2 columns of coefficients) which is indicative of relatively low spatial frequency information, and the vectors z
H
together define a coefficient block “H” (having M rows and M/2 columns of coefficients) which is indicative of relatively high spatial frequency information. This horizontal wavelet transform is equivalent to passing the input block
1
through a “high pass” transform filter
2
and a “low pass” transform filter
4
, passing the output of filter
2
through decimation filter
3
(in which it undergoes decimation which reduces its sampling frequency by a factor of two) to generate block “H”, and passing the output of filter
4
through decimation filter
5
(in which it undergoes decimation which reduces its sampling frequency by a factor of two) to generate block “L.”
Then, another wavelet transform (a “vertical” wavelet transform) is performed on each column of block “L” (each column comprising M coefficients indicative of relatively low spatial frequency information). Since the “vertical” wavelet transform filters columns rather than rows, it requires that block “L” has been stored in a memory and read out from the memory on a column by column basis to perform the vertical transform. Each column of block “L” (sometimes referred to as a “line”) is converted into two vectors, z
LL
and z
LH
, each comprising M/2 coefficients. All the vectors z
LL
together define coefficient block “LL” (having M/2 rows and M/2 columns of coefficients, and indicative of the relatively low spatial frequency information of block “L”), and the vectors z
LH
together define coefficient block “LH” (having M/2 rows and M/2 columns of coefficients, and indicative of the relatively high spatial frequency information of block “L”) . This vertical wavelet transform is equivalent to passing block “L” through a “high pass” transform filter
6
and a “low pass” transform filter
8
, passing the output of filter
6
through decimation filter
7
(in which it undergoes decimation which reduces its sampling frequency by a factor of two) to generate block “LH”, and passing the output of filter
8
through decimation filter
9
(in which it undergoes decimation which reduces its sampling frequency by a factor of two) to generate block “LL.”
Then, another wavelet transform (a second “horizontal” wavelet transform) is performed on each row of block LL. Since this horizontal wavelet transform filters rows rather than columns, it requires that block LL has been stored in memory and read out from memory on a row by row basis to perform the filtering. Each row of block LL is converted into two vectors, z
LLL
and z
LLH
, each comprising M/4 coefficients. All the vectors z
LLL
together define coefficient block “LLL” (having M/4 rows and M/2 columns of coefficients, and indicative of the relatively low spatial frequency information of block LL), and the vectors z
LLH
together define coefficient block “LLH” (having M/4 rows and M/2 columns of coefficients, and indicative of the relatively high spatial frequency information of block LL). This horizontal wavelet transform
Meyer Bernd
Sharma Chandan Dev
Couso Jose L.
Girard & Equitz LLP
National Semiconductor Corporation
LandOfFree
Method and apparatus for image data compression with low... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for image data compression with low..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for image data compression with low... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3266330