System and method for performing wavelet and inverse wavelet transformations of digital data using semi-orthogonal wavelets

• US 6,600,838 B2
• Filed: 06/11/2001
• Issued: 07/29/2003
• Est. Priority Date: 08/29/1997
• Status: Expired due to Term

• Current Assignee: Qualcomm, Inc.
• Original Assignee: Oak Technology Partners (Qualcomm, Inc.)
• Inventors: Chui, Charles K.
• Primary Examiner(s): Wu, Jingge
• Application Number:
  US09/878,986
• Publication Number:
  US 20010036323A1
• Time in Patent Office: 778 Days
• Field of Search: 382/232-250, 375/240-8-2
• US Class Current: 382/249
• CPC Class Codes: G06F 17/148 Wavelet transforms

Abstract

A wavelet transform system and an inverse wavelet transform system are disclosed that respectively implement a wavelet transform and an inverse wavelet transform. Semi-orthogonal standard wavelets are used as the basic wavelets in the wavelet transform and the inverse wavelet transform. As a result, two finite sequences of decomposition coefficients are used for decomposition in the wavelet transform. Furthermore, two finite sequences of reconstruction coefficients that are derived from the two finite sequences of decomposition coefficients are used for reconstruction in the inverse wavelet transform. The finite sequences of decomposition and reconstruction coefficients are not infinite sequences of coefficients that have been truncated. Furthermore, in one embodiment, downsampling is not used in the wavelet transform and upsampling is not used in the inverse wavelet transform.

Claims

1. A pre-decomposition filter of a wavelet transform system for mapping a set of original data samples into a set of dual scaling function coefficients for decomposition by the wavelet transform system, the sets of original data samples and dual scaling function coefficients being related to a set of scaling function coefficients, to scaling functions that correspond to the set of scaling function coefficients, and to dual scaling functions that are dual to the scaling functions and correspond to the set of dual scaling function coefficients, the pre-decomposition filter comprising:

a first filter stage that filters the set of original data samples to generate a first set of intermediate coefficients;

a second filter stage that is parallel to the first filter and filters the set of original data samples to generate a second set of intermediate coefficients; and

a summing stage that sums the first and second sets of intermediate data samples to generate the set of dual scaling function coefficients.

2. The pre-decomposition filter of claim 1 wherein:

the first filter stage has a first transfer function for mapping the set of original data samples to the first set of intermediate coefficients;

the second filter stage has a second transfer function for mapping the set of original data samples to the second set of intermediate coefficients;

the set of original data samples is capable of being mapped to the set of scaling function coefficients by a third transfer function;

the set of scaling function coefficients is capable of being mapped to the set of dual scaling function coefficients by a fourth transfer function;

the combined transfer function of the first and second filter stages and the summing stage is the sum of the first and second transfer functions and is equivalent to the product of the third and fourth transfer functions.

3. The pre-decomposition filter of claim 2 wherein:

the second filter stage comprises an FIR filter and the fourth transfer function is capable of being performed with an FIR filter such that the degree of the second transfer function is less than the degree of the fourth transfer function; and

the first filter stage comprises an IIR filter and the third transfer function is capable of being performed with an IIR filter such that the first and third transfer functions are proportional to each other.

4. A method in a wavelet transform system for mapping a set of original data samples into a set of dual scaling function coefficients for decomposition by the wavelet transform system, the sets of original data samples and dual scaling function coefficients being related to a set of scaling function coefficients, to scaling functions that correspond to the set of scaling function coefficients, and to dual scaling functions that are dual to the scaling functions and correspond to the set of dual scaling function coefficients, the method comprising the steps of:

filtering the set of original data samples to generate a first set of intermediate coefficients;

filtering the set of original data samples to generate a second set of intermediate coefficients; and

summing the first and second sets of intermediate data samples to generate the set of dual scaling function coefficients.

5. The method of claim 4 wherein:

the first filtering step has a first transfer function for mapping the set of original data samples to the first set of intermediate coefficients;

the second filtering step has a second transfer function for mapping the set of original data samples to the second set of intermediate coefficients;

the set of original data samples is capable of being mapped to the set of scaling function coefficients with a third transfer function;

the set of scaling function coefficients is capable of being mapped to the set of dual scaling function coefficients with a fourth transfer function;

the combined transfer function of the first and second filtering steps and the summing step is the sum of the first and second transfer functions and is equivalent to the product of the third and fourth transfer functions.

6. The method of claim 5 wherein:

the second filter step is performed with an FIR filter and the fourth transfer function is capable of being performed with an FIR filter such that the degree of the second transfer function is less than the degree of the fourth transfer function; and

the first filtering step is performed with an IIR filter and the third transfer function is capable of being performed with an IIR filter such that the first and third transfer functions are proportional to each other.

7. A pre-decomposition filter of a wavelet transform system for mapping a set of original data samples into a set of dual scaling function coefficients at an original resolution level for decomposition by the wavelet transform system, the set of original data samples being given by a first function that approximates a second function at the original resolution level, the pre-decomposition filter applying a set of mapping coefficients to the set of original data samples to map the set of original data samples to the set of dual scaling function coefficients, the set of mapping coefficients being selected by performing an orthogonal projection of the first function to the second function.

8. The pre-decomposition filter of claim 7 wherein:

the set of original data samples {f_M,n} is given by the first function f_M(x) and is related at the original resolution level M to a set of scaling function coefficients {c_M,kM}, a set of scaling functions {φ

_M,kM(x)}, the set of dual scaling functions {{overscore (c)}_M,kM}, and a set of dual scaling functions {{overscore (φ

)}_M,kM(x)} that is dual to the set of scaling functions {φ

_M,kM(x)} according to;

$f_m<br><br>\left(x\right)=\underset{k_m}{\sum <br><br>}<br><br>c_{m,k_m}<br><br>{\mathrm{\phi <br><br>}}_{m,k_m}<br><br>\left(x\right)=\underset{k_m}{\sum <br><br>}<br><br>{\tilde{c}}_{m,k_m}<br><br>{\widetilde{\mathrm{\phi <br><br>}}}_{m,k_m}<br><br>\left(x\right)$

for m=M, x=2<sup>−

M</sup>n, and {f_M,n}={f_M(2<sup>−

M</sup>n)};

the orthogonal projection of the second function f(x) to the first function f_M(x) is given by;

${\int <br><br>}_{-\mathrm{\infty <br><br>}}^{\mathrm{\infty <br><br>}}<br><br>f<br><br>\left(x\right)<br><br>{\mathrm{\phi <br><br>}}_{m,k_m}<br><br>\left(x\right)<br><br><br><br>x={\int <br><br>}_{-\mathrm{\infty <br><br>}}^{\mathrm{\infty <br><br>}}<br><br>f_m<br><br>\left(x\right)<br><br>{\mathrm{\phi <br><br>}}_{m,k_m}<br><br>\left(x\right)<br><br><br><br>x$

where;

${\tilde{c}}_{m,k_m}={\int <br><br>}_{-\mathrm{\infty <br><br>}}^{\mathrm{\infty <br><br>}}<br><br>f<br><br>\left(x\right)<br><br>{\mathrm{\phi <br><br>}}_{m,k_m}<br><br>\left(x\right)<br><br><br><br>x$

for m=M;

the set of mapping coefficients {λ

_nφ

_n} are selected by obtaining the set of coefficients {φ

_n}={φ

_0,0(n)} given by the scaling function φ

_0,0(x), where x=2<sup>−

M</sup>n, and by selecting the set of coefficients {λ

_n} for the highest degree that the second function f(x) can have for which;

${\int <br><br>}_{-\mathrm{\infty <br><br>}}^{\mathrm{\infty <br><br>}}<br><br>f<br><br>\left(x\right)<br><br>{\mathrm{\phi <br><br>}}_{m,k_m}<br><br>\left(x\right)<br><br><br><br>x=\underset{n}{\sum <br><br>}<br><br>{\mathrm{\lambda <br><br>}}_n<br><br>{\mathrm{\phi <br><br>}}_n<br><br>f_{m,k_m-n}$

is exact, form m=M.

9. The pre-decomposition filter of claim 7 wherein the pre-decomposition filter comprises an FIR filter that applies the set of mapping coefficients in a moving average operation.

10. A method for mapping a set of original data samples into a set of dual scaling function coefficients at an original resolution level for decomposition in wavelet transform system, the set of original data samples being given by a first function that approximates a second function at the original resolution level, the method comprising:

selecting a set of mapping coefficients by performing an orthogonal projection of the first function to the second function; and

applying the set of mapping coefficients to the set of original data samples to map the set of original data samples to the set of dual scaling function coefficients.

11. The method of claim 10 wherein:

the set of original data samples {f_M,n} is given by the first function f_M(x) and is related at the original resolution level M to a set of scaling function coefficients {c_M,kM}, a set of scaling functions {φ

_M,kM(x)}, the set of dual scaling functions {{overscore (c)}_M,kM}, and a set of dual scaling functions {{overscore (φ

)}_M,kM(x)} that is dual to the set of scaling functions {φ

_M,kM(x)} according to;

$f_m<br><br>\left(x\right)=\underset{k_m}{\sum <br><br>}<br><br>c_{m,k_m}<br><br>{\mathrm{\phi <br><br>}}_{m,k_m}<br><br>\left(x\right)=\underset{k_m}{\sum <br><br>}<br><br>{\tilde{c}}_{m,k_m}<br><br>{\widetilde{\mathrm{\phi <br><br>}}}_{m,k_m}<br><br>\left(x\right)$

for m=M, x=2<sup>−

M</sup>n, and {f_M,n}={f_M(2<sup>−

M</sup>n)};

the orthogonal projection of the second function f(x) to the first function f_M(x) is given by;

${\int <br><br>}_{-\mathrm{\infty <br><br>}}^{\mathrm{\infty <br><br>}}<br><br>f<br><br>\left(x\right)<br><br>{\mathrm{\phi <br><br>}}_{m,k_m}<br><br>\left(x\right)<br><br><br><br>x={\int <br><br>}_{-\mathrm{\infty <br><br>}}^{\mathrm{\infty <br><br>}}<br><br>f_m<br><br>\left(x\right)<br><br>{\mathrm{\phi <br><br>}}_{m,k_m}<br><br>\left(x\right)<br><br><br><br>x$

where;

${\tilde{c}}_{m,k_m}={\int <br><br>}_{-\mathrm{\infty <br><br>}}^{\mathrm{\infty <br><br>}}<br><br>f<br><br>\left(x\right)<br><br>{\mathrm{\phi <br><br>}}_{m,k_m}<br><br>\left(x\right)<br><br><br><br>x$

for m=M;

the set of mapping coefficients {λ

_nφ

_n} are selected by obtaining the set of coefficients {φ

_n}={φ

_0,0(n)} given by the scaling function (φ

_0,0(x), where x=2<sup>−

M</sup>n, and by selecting the set of coefficients {λ

_n} for the highest degree that the second function f(x) can have for which;

${\int <br><br>}_{-\mathrm{\infty <br><br>}}^{\mathrm{\infty <br><br>}}<br><br>f<br><br>\left(x\right)<br><br>{\mathrm{\phi <br><br>}}_{m,k_m}<br><br>\left(x\right)<br><br><br><br>x=\underset{n}{\sum <br><br>}<br><br>{\mathrm{\lambda <br><br>}}_n<br><br>{\mathrm{\phi <br><br>}}_n<br><br>f_{m,k_m-n}$

is exact, for m=M.

12. The method of claim 10 wherein the applying step includes applying the set of mapping coefficients in a moving average operation.