Image analysis – Image compression or coding – Pyramid – hierarchy – or tree structure
Reexamination Certificate
2000-10-09
2004-01-13
Chen, Wenpeng (Department: 2624)
Image analysis
Image compression or coding
Pyramid, hierarchy, or tree structure
C382S248000, C382S238000
Reexamination Certificate
active
06678421
ABSTRACT:
TECHNICAL FIELD
The present invention relates to a subband encoding and predictive decoding method and apparatus. More specifically, it relates to an encoding and predictive decoding method and apparatus wherein data signals are encoded and decoded by estimating the higher frequency subband coefficient from the low frequency information in a subband multiresolution data decomposition.
BACKGROUND OF THE INVENTION
Existing subband coefficient prediction systems generally provide an algorithm that utilizes the coefficients in one level (level n−1) to predict the coefficients in the next level (level n), which requires a one to four up-sampling of the information. Some existing prediction techniques rely on a joint probability distribution between coefficients in adjacent bands. The main disadvantage of the techniques is their inability to predict the sign of the estimated coefficients. Existing systems use linear estimation techniques and are prone to inaccuracies because in many situations the data does not follow a linear pattern. Another drawback of existing techniques is that they require the estimation of four coefficients from a single set of joint probabilities. A third drawback found in existing systems pertains to the manner in which the coefficient estimates are made. Specifically, the coefficient estimates rely on correlations between adjacent levels in a subband decomposition. Such correlations are diminutive as compared to correlations between subbands of the same level. Further, existing techniques require an additional embedded algorithm, such as the zerotree algorithm, to distinguish between significant and insignificant coefficients. The distinction between significant and insignificant information is often important for applications of subband coefficient prediction, such as Very Low Bit Rate Coding. Finally, existing techniques are not very conducive to data encryption because the joint probability distribution between coefficients in the wavelet domain can be readily acquired.
SUMMARY OF THE INVENTION
The present invention provides a data compression method and apparatus that is more robust and more efficient than previous, comparable systems. One embodiment of the invention provides a means for predicting the values of upper subband frequency coefficients in a subband decomposition pyramid. According to this embodiment the decomposition pyramid has n decomposition levels, where n is the highest level in the pyramid, and each level in the decomposition has a plurality of subbands. Further each subband has a plurality of coefficients and each coefficient has a sign, magnitude and significance or an insignificance. Additionally, the plurality of subbands includes at least one vertical subband. The vertical subband includes a plurality of low frequency coefficients from the vertical data components from within the highest level of the decomposition pyramid and at least one horizontal subband. The horizontal subband includes a plurality of low frequency coefficients from the horizontal data components within the n level of the decomposition pyramid and a plurality of high frequency coefficients from the vertical data components within the n level of said decomposition pyramid and at least one diagonal subband comprising a plurality of high frequency coefficients from both the vertical and horizontal data components within the n level of said decomposition pyramid. Further, the coefficients for the vertical and horizontal subbands are predicted from information contained in a low pass subband of level n, and the coefficients for the diagonal subband are predicted from information in the vertical and horizontal subbands. Finally the prediction process is carried out recursively setting n equal to n−1 for each level of the decomposition until n equals 0 and the original image size has been reconstructed.
Another embodiment of the present invention provides a means for predicting coefficients in the n
th
level of an n-level multiresolution decomposition pyramid. The pyramid has a plurality of subbands including a low-pass subband, a vertical subband, a horizontal subband and a diagonal subband, wherein a plurality of the subbands have higher and lower frequency coefficients. The predicted coefficients are used to predict upper frequency coefficients for the vertical, horizontal and diagonal subbands in the multiresolution decomposition pyramid for levels at and below n. This is achieved by defining n as the number of levels in the multiresolution decomposition pyramid, estimating the coefficient properties of the vertical, horizontal and diagonal subbands, reconstructing the low frequency subband of level n−1 with the aid of a conventional analysis/synthesis filter bank. In a subsequent step n is replaced with n−1 and the sequence is repeated until n is equal to zero. When n is equal to zero the data has been fully re-composed.
In yet another embodiment of the present invention, a conventional analysis filter array is used to decompose an image having rectangular dimensions. This analysis filter or bank of filters produces a multiresolution decomposition, wherein the multiresolution decomposition comprises a low pass subband, and a plurality of upper subbands, wherein said upper subbands include a vertical subband, a horizontal subband and a diagonal subband and wherein each subband has a plurality of coefficients. The rectangular dimensions are then encoded and transmitted to the decoder to allow for the dimensionally correct reconstruction of the final image. Next, the low pass subband is encoded. Care is taken to minimize the risk of distortion, as this subband will serve as the basis for the reconstructed image. The next step is to determine an optimal threshold for the other subbands, namely the horizontal, vertical, and diagonal subbands. For this, a Bayesian Classifier is used, and all of the upper subband coefficients labeled as significant or insignificant based on the optimal threshold. Next, significance map errors and other misclassifications are stored for transmission. A neural network makes use of data from the multiresolution decomposition and stores errors made in the sign of the predicted value as well as the errors made in predicting the magnitude. Both magnitude and sign errors are defined as:
error term=|true value|−|predicted value|.
When the data is received at the decoder, the x and y dimensions for the final image, as well as the coding methods selected for the binary strings denoting the significance map and sign flip errors, are decoded. Then the low frequency subband is decoded. The next step includes operating the Bayesian Classifier and labeling all of the upper subband coefficients as significant or insignificant based on the decoded threshold value, decoding the significance map errors and correcting any misclassifications, operating the neural network and extracting values, both sign and magnitude, for all the significant coefficients and decoding the magnitude and sign flip errors, and computing the coefficient's predicted value by the following equation,
reconstructed value=(|predicted value|+error term)*sign flip error*sign value
The final step employs conventional subband synthesis filters compatible with the subband analysis filters to reconstruct the original image.
Yet another embodiment of the present invention provides an apparatus for predicting upper frequency band coefficients from low frequency information in a multiresolution subband decomposition having an n-level multiresolution decomposition pyramid. This pyramid includes a plurality of subbands including a low-pass subband, a vertical subband, a horizontal subband and a diagonal subband. Wherein a plurality of the subbands have higher and lower frequency subband coefficients. The predicted coefficients are used to predict upper frequency coefficients for the vertical, horizontal and diagonal subbands in the multiresolution decomposition pyramid for levels at and below n w
Daniell Cindy
Matic Roy
Chen Wenpeng
HRL Laboratories LLC
Tope-McKay & Associates
LandOfFree
Subband coefficient prediction with pattern recognition... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Subband coefficient prediction with pattern recognition..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Subband coefficient prediction with pattern recognition... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3229978