Image analysis – Image compression or coding – Pyramid – hierarchy – or tree structure
Reexamination Certificate
2000-09-14
2004-05-18
Johnson, Timothy M. (Department: 2625)
Image analysis
Image compression or coding
Pyramid, hierarchy, or tree structure
C382S234000, C382S233000, C382S248000, C375S240190, C375S240110, C348S398100
Reexamination Certificate
active
06738523
ABSTRACT:
FIELD OF THE INVENTION
The present invention generally relates to wavelet-based image compression systems and more particularly to an image compression system that performs inverse discrete wavelet transform processing in parallel to achieve higher processing speeds.
BACKGROUND OF THE INVENTION
Conventional wavelet-based image compression systems apply a two-dimensional forward wavelet transform to an image in order to transform the image into subbands. Each such subband is a band pass filtered and reduced resolution version of the original image. This permits the subbands to be amenable to compression by various means. Reconstruction of the original image requires that all such subbands must first be decompressed, followed by the application of an inverse discrete wavelet transform (IDWT) to transform these subbands back into the original image.
Although the present invention does not depend on lifting (described below), its utility is greatly enhanced by lifting. The invention also utilizes tiling to allow random and/or multiresolution access.
Tiling is described in detail in U.S. Pat. No. 5,710,835 (hereinafter '835) and the same is incorporated herein by reference. The invention described below is fundamentally different than the system described in '835 because the '835 system is designed to reduce the hardware necessary to perform the lifting/tiling operations. To the contrary, the present invention is designed to increase processing speed. In its operations, the present invention performs many actions in parallel, which actually increases the number of required hardware components (which is in direct contrast to the goal of reducing hardware components in '835). The '835 patent tiles the image with possibly overlapping tiles, so as to facilitate random access during reconstruction. This also is done to decrease the amount of processing hardware and to decrease the required processing speed. As discussed below, the invention tiles each subband with minimally overlapping tiles, with no concern towards random access. This is done to increase the amount of processing hardware in order to increase the net processing speed.
SUMMARY OF THE INVENTION
It is, therefore, an object of the present invention to provide a structure and method of processing signals, which includes transforming a signal into subbands by applying one or more forward discrete wavelet transforms (FDWT) to the signals as in the Mallat decomposition described in ISO/IEC 15444-1, partitioning the resulting subbands into overlapping subband subsets, inverse transforming the overlapping subband subsets into signal subsets by applying one or more inverse discrete wavelet transforms (IDWT) to the overlapping subband subsets, and combining the resulting signal subsets to reproduce the signal. The IDWT is applied to all of the subband subsets in parallel. The inverse transform operation includes performing lifting upon the subband subsets to minimize the required overlap between adjacent overlapping subband subsets. The partitioning is performed so as to minimize an overlap between adjacent overlapping subband subsets. The invention can further include discarding excess sample values that occur as a result of overlap between adjacent overlapping subband subsets.
The invention can thus comprise a method of image compression utilizing inverse discrete wavelet transforms (IDWT), including partitioning a set of forward discrete wavelet transform (FDWT) coefficients into two or more overlapping subband subsets, simultaneously performing an IDWT of each subset using lifting (such that an overlap between adjacent subband subsets is minimized), recombining the subband subsets, and discarding excess sample values that occur as a result of overlap between adjacent subband subsets.
ADVANTAGES OF THE INVENTION
One advantage of the invention lies in speeding up inverse discrete wavelet transformations (IDWT) of subband data. This is done by partitioning the data input to the IDWT in a specific and minimally overlapping manner, to allow multiple IDWT operations to be performed on these partitions in parallel. Another advantage of the invention lies in the reduction of the size required of memory elements used in storing intermediate values within a multi-dimensional IDWT. The invention allows such memory element reduction because the required lengths of these elements are proportional to the length of each subset that is being inverse transformed. Thus, by reducing the lengths of the subsets, the required length of the memory element is correspondingly reduced.
REFERENCES:
patent: 5412741 (1995-05-01), Shapiro
patent: 5481308 (1996-01-01), Hartung et al.
patent: 5546477 (1996-08-01), Knowles et al.
patent: 5657085 (1997-08-01), Katto
patent: 5710835 (1998-01-01), Bradley
patent: 5798794 (1998-08-01), Takahashi
patent: 5825935 (1998-10-01), Murakoshi
patent: 5875122 (1999-02-01), Acharya
patent: 5926791 (1999-07-01), Ogata et al.
patent: 5982434 (1999-11-01), Tong et al.
patent: 5995210 (1999-11-01), Acharya
patent: 6546143 (2003-04-01), Taubman et al.
patent: 6549673 (2003-04-01), Ammicht et al.
patent: 6553147 (2003-04-01), Chai et al.
patent: 6567081 (2003-05-01), Li et al.
Brown Mark D.
Small Jeffrey A.
Bayat Ali
Eastman Kodak Company
Johnson Timothy M.
Woods David M.
LandOfFree
Parallel inverse discrete wavelet 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 Parallel inverse discrete wavelet transform, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Parallel inverse discrete wavelet transform will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3243145