Image analysis – Image compression or coding – Pyramid – hierarchy – or tree structure
Reexamination Certificate
1999-12-16
2003-07-01
Mehta, Bhavesh M. (Department: 2625)
Image analysis
Image compression or coding
Pyramid, hierarchy, or tree structure
C382S248000, C382S233000, C375S240110
Reexamination Certificate
active
06587588
ABSTRACT:
BACKGROUND OF INVENTION
(1) Field of Invention
This invention relates to progressive image transmission and methods of operation. More particularly, the invention relates to progressive image decoders for wavelet encoded images in compressed files and methods of operation.
(2) Description of Prior Art
Multi-resolution wavelet decomposition is one of the most efficient schemes for the compression of grayscale and color images. Reference 1—[Mallat1989]. Decoding a compressed file consists of two essential operations, which usually are performed in sequence:
Decoding the wavelet coefficients. The compressed data is transformed into wavelet coefficients according to a predefined wavelet coefficient decoding scheme. This decoding scheme often relies on a context based statistical decoder such as the Z-Coder. Reference 2—[Bottou, Howard and Bengio1998].
Reconstructing the image. The wavelet coefficients are combined according to a predefined rule which produces the image pixels. This predefined rule usually consists of applying an inverse wavelet transform and a color space conversion.
Progressive decoders are useful when compressed data comes out of a slow transmission channel. The compressed data must be organized as a sequence of slices describing how to update the wavelet coefficients resulting from the previous slices. The first slices describe the coefficients with very little accuracy. Subsequent slices increase the accuracy of the wavelet coefficients. The image can be reconstructed at any time using the current approximation of the true wavelet coefficients.
Therefore a wavelet image viewer can quickly display a low quality image and refine it when more data is available. A Progressive Decoder can be viewed as composed of a Wavelet Decoder and an Image Renderer operating in parallel (See FIG.
1
). The two units communicate via a shared array of wavelet coefficients.
The Wavelet Decoder processes the slices as soon as they are available and updates the values stored in the shared array of wavelet coefficients.
The Image Renderer combines the values stored in a shared array of wavelet coefficients and computes the pixel values on demand. A wavelet image viewer, for instance, may redisplay the complete image whenever sufficient additional data is available. The user may also use scrollbars and uncover new parts of the image. The Image Renderer computes the corresponding pixel values on demand.
Processing large images with such architecture creates many problems. The size of the wavelet coefficient array may exceed the available memory in the system. The Image Renderer is usually triggered by an action from the user and therefore should complete the computation without noticeable delay. A need exists in progressive image transmission to overcome the problems of memory requirements and delay in displaying large images.
Prior art related to progressive image transmission and decoding include the following:
U.S. Pat. No. 5,880,856 entitled “Progressive Image Transmission Using Discrete Wavelet Transform” by P. Ferriere, issued Mar. 9, 1999, filed Dec. 5, 1994 discloses transforming a still image into a plurality of decomposition levels using a discrete wavelet transform. Each decomposition level comprises a plurality of subimages which allow reconstruction of an image representation of the still image. The decomposition levels are transmitted beginning with a base decomposition level providing a low level of image resolution and then proceeding with decomposition levels providing increasingly higher levels of image resolution. Within each decomposition level, rows of the various sub-images are arranged or interlaced together in contiguous blocks so that all data for a single row, at a single decomposition level is transmitted together. At the receiving end the row blocks are reconstructed and displayed as they are received.
U.S. Pat. No. 5,602,589 entitled “Video Image Compression Using Weighted Wavelet Hierarchical Vector Quantization” by M. Vishwanath et al, issued Feb. 11, 1997 discloses a method and apparatus for compressing and decompressing a video image. Input data representing an image is successively subjected to (i) levels of a first table lookup to obtain compressed data representing a sub-band of a discrete wavelet transform followed by vector quantization. The compressed data is transmitted to a receiver. The compressed data is subjected to multiple stages of a second table lookup operation to selectively obtain decompressed data representing at least a partial inverse sub-band transform of the compressed data. The table lookups simplify decoder hardware and provide efficient encoding and decoding.
None of the prior art addresses the problem of decreasing memory requirement for a wavelet decoder and speeding the display of fragments of progressively encoded images.
SUMMARY OF THE INVENTION
A progressive image display decoder and method of operation for wavelet encoded images achieves reduced memory storage requirements for wavelet transform coefficients and reduced execution time in displaying the image thereby overcoming the limitations of the prior art. Conveniently, a wavelet encoded image format, typically DjVu IW44 facilitates progressive rendering and smooth scrolling of large color or gray level images with limited memory requirements. The progressive wavelet decoder is composed of two components. The first component decodes the incoming image data in compressed files and updates an array of wavelet coefficients stored in a memory. The second component applies an inverse wavelet transform to the array of wavelet coefficients for the purpose of reconstructing the image. The operation of the first component (the decoder) is triggered by the incoming compressed image data. The received data is decoded and is used to apply updates to the array of wavelet coefficients stored in the memory. Each update improves the accuracy of the coefficients and therefor improves the fidelity of the reconstructed image. The coefficient array is composed of several two-dimensional arrays (one for each of the color components) having one entry corresponding to each 32×32 blocks in the image. Each entry contains 1024 wavelet coefficients organized as a sparse array with two levels of indirection. The operation of the second component (the renderer) is typically triggered when enough data has been received to display an updated version of the image, or when the user performs an action which requires displaying a new part of the image. In the latter case, the renderer only reconstructs the pixel values for the parts of the image, which are needed. A further reduction of the computation time is obtained by using “lifting” for implementing a fast inverse wavelet transform.
REFERENCES:
patent: 6130911 (2000-10-01), Lei
patent: 6246798 (2001-06-01), Andrew et al.
patent: 6347157 (2002-02-01), Chui
patent: 6356666 (2002-03-01), Atsumi et al.
patent: 6392692 (2002-05-01), Monroe
patent: 6421464 (2002-07-01), Tran et al.
Bottou Leon
Howard Paul Glor
AT&T Corp.
Bayat Ali
Mehta Bhavesh M.
LandOfFree
Progressive image decoder for wavelet encoded images in... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Progressive image decoder for wavelet encoded images in..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Progressive image decoder for wavelet encoded images in... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3041582