Image analysis – Image compression or coding – Pyramid – hierarchy – or tree structure
Reexamination Certificate
1998-12-31
2002-11-26
Chen, Wenpeng (Department: 2624)
Image analysis
Image compression or coding
Pyramid, hierarchy, or tree structure
C375S240110
Reexamination Certificate
active
06487318
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Technical field
The present invention relates to an image compression and transmission method, and particularly to a method of relocating a wavelet packet coefficient for a zerotree coding in order to optimize an encoder to be suitable for transmitting image off-line.
2. Description of the Prior Art
This invention is incorporated by the reference, “Image coding using wavelet transform”, IEEE Trans. Image Processing, vol.1, pp.205-220, April 1992, by M.Antonini, M.Barlaoud, P.Mathieu, and I.Daubechies; “Embedded image coding using zerotree of wavelets coefficients”, IEEE Trans. Signal Processing, vol.41, pp.3445-3462, December 1993, by J. M. Sharpiro; “A new fast and efficient image coding based on set partitioning in hierarchical trees”, IEEE Trans. Circuits Syst. Video Technol. vol.6, pp.243-250, June 1996, A.Said and W. A. Pearlman; “Best wavelet packet bases in a rate-distortion sense”, IEEE Trans. Image Processing, vol.2, pp.160-175, April 1993, by K.Ramchandran and M.Vetterli.
FIG. 1
shows a conventional image compression and transmission method. As shown in the figure, the conventional image compression and transmission method executes a wavelet transform process
10
for dividing image data into several frequency bands, so as to allow most energy to be focused on a few coefficients on the band. Then, the image data is compressed by executing a zerotree coding process
20
of coding the wavelet coefficients by forming a tree structure with the wavelet coefficients.
The image transformed by the wavelet transform process
10
is divided into several frequency bands, as shown in FIG.
2
. In the figure, it is indicated that a left and upper portion of the frequency band corresponds to a low frequency band and a right and lower portion also corresponds to a higher frequency band. Therefore, a smallest band, positioned leftmost and uppermost in the frequency band, shows a lowest frequency. Also a largest band, positioned rightmost and lowermost, shows a highest frequency. At this time, because most of the image data energy flock to the low frequency bands, most of the image data can be represented by using only the small frequency bands (low frequency bands). That is, because the energy gathers in a few coefficients, the image data can be compressed by coding only the coefficients.
As shown in
FIG. 3
, in the zerotree coding process
20
, the wavelet transformed coefficients are assembled in a tree structure. In the tree structure, a coefficient in a top position is called “patent”, and coefficients just under the top coefficient, or the parent, are named as “child”. And all coefficients, including the child, under the parent can be commonly designated as “descendant”.
Now, an operation of the above prior art is explained below.
In the wavelet transform process
10
, at first, the image is transformed in order to express with a few coefficients in the frequency band. Then in the zerotree coding process
20
, the wavelet coefficients are assembled into the tree structure, and a zerotree coding is executed, based on a specific threshold, so as to compress image.
For accomplishing the wavelet transform process
10
, a filtering and subsampling is used. The image data can be divided into a low frequency band and a high frequency band by a low frequency filtering and subsampling and a high frequency filtering and subsampling. At this time, because the low frequency band has room to be compressed, the filtering and subsampling is repeated to the low frequency band. As a result, the wavelet transformed image having several frequency bands as shown in
FIG. 2
can be obtained.
Then, the zerotree coding is carried out about the wavelet transformed image. In the zerotree coding process, when a magnitude of a coefficient is smaller than a threshold T, the coefficient is defined as “zero” or “insignificant coefficient”, while, when a magnitude of a coefficient is bigger than the threshold T, the coefficient is defined as “non-zero”, or “significant coefficient”. In case of the non-zero, the coefficient value is transmitted after executing quantization about the non-zero coefficient. However, in case of the coefficient defined in zero, the coefficient is defined as a “Zerotree Root” symbol when all of the children is zero. In the zero coefficient case, however, when there is non-zero child, the coefficient is defined as a “Isolated Zero” symbol. Then, the wavelet coefficients in the tree structure are scanned and transmitted from parent to child and from left to right in FIG.
3
. The wavelet coefficient of image data commonly has strong correlation with a position on a picture. So, when the parent coefficient is zero, the descendant coefficients are much probable to be zero. Therefore, defining that the all zero descendant coefficients as well as the zero parent coefficient are one symbol, that is, a zerotree root, it is permissible not to transmit coefficient values of the descendants in the zerotree root symbol, which gives a high compression effect.
Whole operation of the zerotree coding is accomplished as below. At first, after quantizing all the coefficients on Zerotree on the basis of the initial threshold T, the encoder transmits quantized values of the non-zero coefficients, the isolated zero symbols and the zerotree root symbols. At second, after quantizing all the coefficients on Zerotree on the basis of the second threshold T/2, the encoder transmits secondly calculated quantized values of the non-zero coefficients, the isolated zero symbols and the zerotree root symbols. Then, after repeating the above process successively, when it reaches a required bit rate, the coding is completed.
A decoder performs a reverse operation to the encoder for acquiring a reconstructed image.
It may be understood that the above zerotree coding is designed to be suitable for the wavelet transformed coefficient. As shown in
FIG. 2
, it is difficult that the tree structure for the zerotree coding is assembled in other form except the wavelet transform.
However, the zerotree coding can not be applied to a wavelet packet transform, which is generalized from the wavelet transform, and provides better performance than the wavelet transform in many kinds of image data. Therefore, there is need for an image compression and transmission technique for applying the zerotree coding to the wavelet packet coefficients.
SUMMARY OF THE INVENTION
Therefore, the present invention is designed to overcome the above problems. An object of the invention is to provide a method of relocating wavelet packet coefficients for a zerotree coding. The zerotree coding of the wave packet coefficients can be effectively accomplished by a method which is as follows; collecting coefficients at the same position of different frequency subbands and relocating them at the same position of integrating frequency band.
In order to accomplish the above object, the present invention provides a method for relocating wavelet packet coefficients from frequency subbands into the frequency band integrating the frequency subbands, comprising the steps of collecting coefficients in same locations of the subbands, and relocating the collected coefficients in a corresponding location in an integrating frequency band, formed by integrating the subbands.
Additionally, in another embodiment, the present invention provides a method for relocating wavelet packet coefficients comprising a wavelet packet transform process for executing a filtering and subsampling of image data and transforming the image data into wavelet packet coefficients having various frequency bands; and a coefficient relocating process for collecting coefficients corresponding to same locations on frequency subbands among the wavelet packet transformed coefficients, and relocating the coefficients in a corresponding location on an integrated frequency band so as to assemble a tree structure for a zerotree coding.
REFERENCES:
patent: 5724451 (1998-03-01), Shin et al.
patent: 5825935 (1998-10-01), Murakoshi
patent: 6157746 (2000-12-01), Sodagar e
Chen Wenpeng
McKenna Long & Aldridge LLP
LandOfFree
Method of relocating wavelet packet coefficient 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 of relocating wavelet packet coefficient, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method of relocating wavelet packet coefficient will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2986222