Image analysis – Image compression or coding – Pyramid – hierarchy – or tree structure
Reexamination Certificate
2000-10-12
2003-04-15
Johnson, Timothy M. (Department: 2621)
Image analysis
Image compression or coding
Pyramid, hierarchy, or tree structure
C382S239000, C382S251000, C382S264000
Reexamination Certificate
active
06549674
ABSTRACT:
The present invention relates generally to the processing, compression, communication and storage of images in computer systems, personal digital assistants, digital cameras and other devices, and particularly to an image management system and method in which digitally encoded images can be viewed in any specified window size and at a number of resolutions, and can be printed, cropped, and otherwise manipulated.
BACKGROUND OF THE INVENTION
An image may be stored at a number of resolution levels. The encoded image data for a lower resolution level is smaller, and thus takes less bandwidth to communicate and less memory to store than the data for a higher resolution level. When an image is stored for multi-resolution use, it would be desirable for the image data to be segregated into an ordered group of sets or subfiles, where each additional subfile provides the additional data needed to increase the resolution of the image from one level to the next. Further, it would be desirable for the quantity of image data in each subfile, for increasing the image resolution by a particular factor (such as 4), to be approximately proportional to the associated increase in resolution. For instance, if each resolution level differs from its neighboring resolution levels by a factor of 4 (e.g., level 0: 32×32, level 1: 64×64, level 2: 128×128, and so on), then the quantity of encoded image data for each resolution level should be approximately 25% as much as the quantity of encoded image data for the next higher resolution level. From another viewpoint, the quantity of data in the subfile(s) used to increase the image resolution from a first level to the next should, ideally, be approximately three times as much as the quantity of data in the subfile(s) for the first level.
It is well known that wavelet compression of images automatically generates several resolution levels. In particular, if N “layers” of wavelet transforms are applied to an image, then N+1 resolution levels of data are generated, with the last LL subband of data comprising the lowest resolution level and all the subbands of data together forming the highest resolution level. For convenience, the “layers” of wavelet transforms will sometimes be called “levels”. Each of these resolution levels differs from its neighbors by a factor of two in each spatial dimension. We may label these resolution levels as Level 0 for the lowest, thumbnail level to Level N for the highest resolution level, which is the resolution of the final or base image.
A first aspect of the present invention is based on two observations. The first such observation is that, when using conventional as well as most proprietary data compression and encoding methods, the quantity of data in the N levels generated by wavelet compression tends to decrease in a geometric progression. For instance, the quantity of data for resolution Level 0 is typically about 80% of the quantity of data for resolution Level 1, whereas ideally it should about 25% of the quantity of data for resolution Level 1. As a result, the data for Level 0 contains significantly more data than is needed to display the Level 0 image. Alternately stated, the data for Level 0 gives unnecessarily high quality for the low resolution display at Level 0, and therefore gives less compression than could potentially be obtained by providing only the information needed for displaying the image at the Level 0 resolution level.
The second observation is that the low resolution image data coefficients are quantized for full resolution display, not for low resolution display, because these data coefficients are used not only for generating a low resolution representation of the image, but are also used when generating the higher resolution representations of the image.
In accordance with this first aspect of the present invention, as already indicated above, it would be desirable for the quantity of image data in the subarray or subfile for each resolution level to be approximately proportional to the increase in resolution associated with that resolution level.
A second aspect of the present invention is based on the observation that wavelet transforms are conventionally applied across tile or block boundaries of an image to avoid tile or block boundary artifacts in the regenerated image. A wavelet transform may be implemented as a FIR (finite impulse response) filter having an associated length. The “length” indicates the number of data samples that are used to generate each coefficient. Wavelet transforms are generally symmetric about their center, and when the filter that implements the wavelet transform is at the edge of a tile or block, typically half or almost half of the filter will extend into a neighboring block or tile. As a result it is usually necessary to keep not only part of the neighboring tiles in memory while wavelet transforming a tile of an image, it also necessary to keep in memory the edge coefficients of the neighboring tiles for each level of the wavelet transform. Thus, avoiding tiling effects (also called tile border effects or artifacts or edge artifacts) typically increases the memory requirements of the computer or device performing the wavelet transforms on an image, and may also increase the complexity of the transform procedure because of the need to keep track of the memory locations of edge data and coefficients from the neighboring tiles or blocks. In accordance with the second aspect of the present invention, it would be highly desirable to have a wavelet or wavelet-like transform that can be applied to just the data for the image block being processed, without having to also apply the transform to data from neighboring blocks, and without creating noticeable edge artifacts. Having such a transform would decrease memory requirements and might simplify the wavelet compression of images.
It is well known in the prior art that digital images can be processed a portion at a time, instead of all at once, thereby reducing memory requirements. For instance, the DCT transform used for JPEG compression and encoding of images is traditionally used on tiles of 8×8 pixels. However, a well known problem with tiling an image for processing is that the tiling produces undesirable tile border effects. The border effects of DCT tiling in JPEG images are considered to be acceptable because the very small size of the tiles makes the tiling effect relatively unnoticeable to the human eye.
However, using very small tiles such as 8×8 pixels is not practical when using wavelet or wavelet-like transforms in place of the DCT transform. Wavelet-like transforms have been shown to provide significantly better data compression than the DCT transform, and therefore using wavelet-like transforms would be desirable if the tiling effect can be avoided while using a moderate amount of working memory.
It would therefore be desirable to provide an image processing system and method that process images using a moderate amount of working memory, such as 8 to 20 KB, by transforming the image data using a wavelet-like transform with moderately sized tiles, such as tiles of 64×64, or 32×32, or 64×32 pixels, while at the same time avoiding the generation of undesirable tiling (tile border) effects.
A third aspect of the present invention is based on the observation that the optimal quantization level to be applied to wavelet coefficients not only varies from one transform subband to another, but also varies from one region of an image to another. In particular, regions of an image that contain many “features” (typically characterized by horizontal or vertical lines or edges) are harder to compress than regions with fewer features. That is, such densely featured image regions cannot be compressed as much as less densely featured regions without causing degradation in the quality of the image regions regenerated from the compressed data. It would therefore be desirable to provide an image compression and encoding system with a quantization procedure that uses sm
Chui Charles K.
Gao Hong-Ye
Zhong Lefan
Johnson Timothy M.
Pennie & Edmonds LLP
Picsurf, Inc.
LandOfFree
Image compression based on tiled wavelet-like transform... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Image compression based on tiled wavelet-like transform..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Image compression based on tiled wavelet-like transform... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3044405