Image analysis – Image compression or coding – Pyramid – hierarchy – or tree structure
Reexamination Certificate
1999-03-12
2003-04-08
Mehta, Bhavesh M. (Department: 2625)
Image analysis
Image compression or coding
Pyramid, hierarchy, or tree structure
C375S240190
Reexamination Certificate
active
06546143
ABSTRACT:
BACKGROUND OF THE INVENTION
The invention relates to data compression. More specifically, the invention relates to subband decomposition of images.
Data compression is often used for reducing the cost of storing large data files on computers as well as reducing the time for transmitting large data files between computers. In the so-called “transform methods” data is transformed into coefficients that represent the data in a frequency domain. Coefficients may be quantized (lossy compression) without significantly affecting the quality of data that is eventually reconstructed from the quantized coefficients. Redundancy in the coefficients may then be reduced or eliminated (lossless compression) without affecting quality of the reconstructed data.
One well known class of transforms are Wavelet transforms. The Wavelet transforms may be used to perform subband decomposition and produce coefficients that describe the data in a hierarchical multiscale representation. Wavelet transforms have proven useful for the compression of images and the analysis of signals. They have been proposed as the transforms for the emerging “JPEG-2000” standard.
A subband decomposition is typically performed by storing an entire image in memory, performing high pass and low pass filtering on the entire image in one direction (e.g., the vertical direction), and then performing high and low pass filtering on the entire filtered image in another direction (e.g., the horizontal direction).
Among the advantages of the Wavelet transforms, the transform coefficients can be ordered in a hierarchical structure and transmitted in an “embedded bitstream.” The embedded bitstream has a property whereby prefixes of the bitstream yield a continuum of lower rate descriptions of the data at the highest possible levels of quality. If the embedded bitstream is truncated during transmission of image data, for instance, the information already transmitted allows an entire image to be reconstructed. The quality of the reconstructed image is dependent upon the amount of information transmitted. If an embedded bitstream is truncated, a complete image of reduced quality can be reconstructed from the transmitted bits. In contrast, truncation of a non-embedded transmission might only allow several rows of an image to be reconstructed.
As additional information is transmitted, the quality of the reconstructed image is improved. If the entire bitstream is transmitted without truncation, a lossless or near-lossless image can be reconstructed.
The transmission just described is often referred to as a “progressive-by-quality” image transmission. The coefficients are described by bit-planes, and the most significant coefficient bits (that is, the coefficient bits conveying the most important information) are transmitted first.
Another type of transmission is often referred to as a “progressive-by-resolution” transmission. The progressive-by-resolution transmission involves ordering the coefficients according to different levels of image resolution. The different levels are identified by markers in the embedded bitstream. A computer may use the markers to parse the bitstream and transmit the data for the coefficients corresponding to a resolution that is specified by the receiving computer. The receiving computer can reconstruct an image according to the specified resolution.
Filters and encoders for compressing the image may be fabricated on a single Application-Specific Integrated Circuit (“ASIC”) or “chip.” A small cache of memory may also be fabricated on the chip.
The entire image, prior to filtering, is typically stored in off-chip memory such as DRAM. The entire image could be stored in the faster on-chip memory such as SRAM; however, the on-chip memory is typically much more expensive than off-chip memory. Moreover, if the image was to be stored entirely in on-chip memory, the usage of the chip would be restricted to images of certain sizes.
However, storing the entire image in off-chip memory can still be problematic. Here too, the memory would have to be large enough to store an entire image. Moreover, off-chip memory is expensive relative to the cost of the ASIC. As the size of memory is increased, the cost of performing the subband decomposition is also increased. This is true for image compression and image reconstruction.
For instance, printing applications at 1200 dot per inch (“dpi”) and 24 bits per pixel use about 380 MB for storing an entire page (uncompressed). In the near future, resolution will be increased to 2400 dpi with 24 bits per pixel. This will require far more memory for storing an entire page. The cost of increasing the memory might seem trivial, but for high volume, low profit margin items such as printers, the cost increase can become quite significant.
Another problem with off-chip memory is I/O bandwidth. Increasing the size and resolution of an image will place higher constraints on computational complexity and memory I/O bandwidth. Increasing the I/O bandwidth to accommodate the greater number of I/O transactions will be expensive, but maintaining the I/O bandwidth (given the increase in image size and resolution) might produce unacceptable waiting times for various applications, such as printing images and displaying images on video monitors.
There is a need to reduce the size off-chip memory. There is also a need to reduce the number of I/O operations between the chip and off-chip memory. These needs will become greater as image resolution and image size are increased.
Moreover, it would be desirable to have a chip that can be used for different applications without being limited by the size of the image. It would also be desirable for the chip to generate an embedded bitstream or reconstruct an image from an embedded bitstream.
SUMMARY OF THE INVENTION
These needs and desires are met by various aspects of the present invention. According to one aspect of the present invention, an image is decomposed into a plurality of subbands. A progression of N line windows of the image is provided, where N is a positive integer, where 1<N<<K and where N is independent of K. In a first filter stage, vertical high and low pass filtering are performed on each N line window that is provided. Consequently, N lines of the image are filtered at a time until the entire image has been decomposed into the plurality of subbands.
According to another aspect of the present invention, transform coefficients of the subbands are coded into an embedded bitstream. The embedded bitstream represents the image in compressed form.
According to yet another aspect of the present invention, the image can be reconstructed from the embedded bitstream by decoding the embedded bitstream into a plurality of lines; forming chunks of N lines for each of the subbands of a given decomposition level; performing inverse horizontal filtering on each chunk of N lines; and performing inverse vertical filtering on the horizontally filtered chunks.
REFERENCES:
patent: 4943855 (1990-07-01), Bheda et al.
patent: 5048111 (1991-09-01), Jones et al.
patent: 5754793 (1998-05-01), Eom et al.
patent: 5883978 (1999-03-01), Ono
patent: 5926791 (1999-07-01), Ogata et al.
patent: 6144773 (2000-11-01), Kolarov et al.
patent: 6195465 (2001-02-01), Zandi et al.
patent: 6229927 (2001-05-01), Schwartz
patent: 6259735 (2001-07-01), Aono et al.
patent: 6292168 (2001-09-01), Venable et al.
patent: 6298167 (2001-10-01), Martucci et al.
patent: 6356665 (2002-03-01), Lie et al.
patent: 6381280 (2002-04-01), Lynch et al.
Chrysafis Christos
Ordentlich Erik
Taubman David S.
Hewlett-Packard Development Company
Mehta Bhavesh M.
Patel Kanji
LandOfFree
Efficient wavelet-based compression of large images does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Efficient wavelet-based compression of large images, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Efficient wavelet-based compression of large images will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3066694