Cryptography – Video cryptography – Video electric signal modification
Reexamination Certificate
1998-09-29
2001-07-24
Couso, Jose L. (Department: 2724)
Cryptography
Video cryptography
Video electric signal modification
C382S232000, C382S248000
Reexamination Certificate
active
06266414
ABSTRACT:
FIELD OF INVENTION
The present invention relates to the field of digital compression with particular application to digital image compression. More particularly, the present invention discloses a digital image compression method utilizing adaptive wavelet packet decomposition.
BACKGROUND OF INVENTION
The field of digital data compression and in particular digital image compression has attracted great interest for some time.
In the field of digital image compression, many different techniques have been utilised. In particular, one popular technique is the JPEG standard which utilises the discrete cosine transform (DCT) to transform standard size blocks of an image into corresponding cosine components. In this respect, the higher frequency cosine components are heavily quantised so as to assist in obtaining substantial compression factors. The heavy quantisation is an example of a “lossy” technique of image compression. The JPEG standard also provides for the subsequent lossless compression of the transformed coefficients.
Recently, the field of wavelet transforms has gained great attention as an alternative form of data compression. The wavelet transform has been found to be highly suitable in representing data having discontinuities such as sharp edges. Such discontinuities are often present in image data or the like.
Although the preferred embodiments of the present invention will be described with reference to the compression of image data, it will be readily evident that the preferred embodiment is not limited thereto. For examples of the many different applications of Wavelet analysis to signals, reference is made to a survey article entitled “Wavelet Analysis” by Bruce et. al. appearing in IEEE Spectrum, October 1996 page 26-35. For a discussion of the different applications of wavelets in computer graphics, reference is made to “Wavelets for Computer Graphics”, I. Stollinitz et. al. published 1996 by Morgan Kaufmann Publishers, Inc.
A number of image coding techniques are known which utilise a linear transformation of the input image to reduce both inter-pixel correlation and coefficient coding overhead. These techniques include the JPEG image compression standard and the federal bureau of investigation (FBI) fingerprint image compression standard. As noted previously, the JPEG standard utilises a discrete cosine transform (DCT) of the image data, while the FBI standard uses a discrete wavelet transform (DWT).
Previous techniques for encoding the coefficients of a DWT include the embedded zerotree wavelet (EZW) method (U.S. Pat. Nos. 5,412,741, 5,315,670, 5,321,776) and set partitioning in hierarchical trees (SPIHT). These techniques first apply a conventional DWT to the source image data to produce the small low frequency representation of the image (called the LL subband) and a number of high frequency, or detail, subbands (called HL, LH and HH subbands). The techniques then utilise the correlation between different frequency subbands, at the same orientation, to predict zero coefficients down the wavelet tree. These methods have been developed for natural images that are assumed to have a 1/f frequency spectrum. They use a conventional DWT decomposition that continually decomposes the low frequency image subbands. Therefore, they often do not efficiently handle images, such as fingerprint images, that do not conform to the 1/f model.
The FBI image compression standard was specifically designed to compress fingerprint images and so uses a non-conventional DWT, decomposing subbands other than the LL subband. However, the subbands decomposed are predefined and can not adapt to either fingerprints with different statistics or to new image types.
ASPECTS OF INVENTION
It is an object of the present invention to ameliorate one or more disadvantages of the prior art.
According to a first aspect of the present invention, there is provided a method of creating a wavelet decomposition of a collection of data values including the steps of: (a) performing an initial decomposition of the data values into a series of components having low frequency components, high frequency components and components having a mixture of high and low frequencies; (b) determining a first number of coefficients of each of said components having a magnitude exceeding a predetermined component threshold; (c) creating a decomposition of each of said components into a series of sub components having low frequency sub-components, high frequency sub-components and sub-components having a mixture of high and low frequencies; (d) determining a second number of coefficients of each of said sub-components having a magnitude exceeding a predetermined sub -component threshold; (e) utilizing said first number and said second number to determine if said component should be decomposed into sub-components; and (f) where said decomposition proceeds, applying said steps (a) to (e) to each of the sub-components to a predetermined level of decomposition.
According to a second aspect of the present invention, there is provided a method of creating a wavelet decomposition of an image including the steps of: (a) performing an initial decomposition of the image into a series of components having low frequency components, high frequency components and components having a mixture of high and low frequencies; (b) determining the number of coefficients of each of said components having a magnitude exceeding a predetermined threshold; where the number of coefficients exceeds a component specific threshold, decomposing said component into a number of sub-components and recursively applying said method to said sub-components.
According to a third aspect of the present invention, there is provided an apparatus for creating a wavelet decomposition of a collection of data values, the apparatus including: first performance means for performing an initial decomposition of the data values into a series of components having low frequency components, high frequency components and components having a mixture of high and low frequencies; first determination means for determining a first number of coefficients of each of said components having a magnitude exceeding a predetermined component threshold; creation means for creating a decomposition of each of said components into a series of sub components having low frequency sub-components, high frequency sub-components and sub-components having a mixture of high and low frequencies; second determinination means for determining a second number of coefficients of each of said sub-components having a magnitude exceeding a predetermined sub-component threshold; utilization means for utilizing said first number and said second number to determine if said component should be decomposed into sub-components; and second performance means for, where said decomposition proceeds, performing the operations of the first performance means, first determination means, creation means, second determination means, and utilization means to each of the sub-components to a predetermined level of decomposition.
According to a fourth aspect of the present invention, there is provided an apparatus for creating a wavelet decomposition of an image, the apparatus including: performance means for performing an initial decomposition of the image into a series of components having low frequency components, high frequency components and components having a mixture of high and low frequencies; determination means for determining the number of coefficients of each of said components having a magnitude exceeding a predetermined threshold; decomposition means for decomposing, where the number of coefficients exceeds a component specific threshold, said component into a number of sub-components; and repetition means for repeating the operations of the determination and decomposition means to said sub-components.
According with a fifth aspect of the present invention, there is provided a computer program product including a computer readable medium having recorded thereon a computer program for creating a wavelet decomposition of a
Andrew James Philip
Bradley Andrew Peter
Canon Kabushiki Kaisha
Couso Jose L.
Do Anh Hong
Fitzpatrick ,Cella, Harper & Scinto
LandOfFree
Method for digital data compression 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 for digital data compression, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method for digital data compression will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2512856