Image analysis – Image compression or coding – Transform coding
Reexamination Certificate
2000-06-15
2001-08-14
Chang, Jon (Department: 2623)
Image analysis
Image compression or coding
Transform coding
C382S233000, C375S240190
Reexamination Certificate
active
06275619
ABSTRACT:
The present invention relates generally to systems and methods for processing digital data. In particular, it pertains to a system and method for performing wavelet and inverse wavelet transformations of digital data using semi-orthogonal wavelets.
BACKGROUND OF THE INVENTION
The use of IWTs (integral wavelet transforms) and inverse IWTs is well established in MRA (multi-resolution analysis) processing of 1-D (one dimensional) digital data, such as audio signals, and/or 2-D (two dimensional) digital data, such as image data. A special feature of IWTs and inverse IWTs is that they provide narrow windowing of short duration high frequency data while also providing wide windowing of long duration low frequency data. This is generally described in Chui, C. K., “An Introduction to Wavelets”, Academic Press, Boston, Mass., 1992, which is hereby incorporated by reference. The following discussion provides examples of how IWTs and inverse IWTs have been implemented in the past.
Wavelet Transform System Using Dual Wavelets {{tilde over (&psgr;)}
m,k
m
(x)} as Basic Wavelets
FIG. 1
shows a 1-D wavelet transform system
100
, which is an improved version of the wavelet transform system shown in “An Introduction to Wavelets.” This system
100
incorporates some aspects of the present invention, but first we will first explain the conventional aspects of this system. The wavelet transform system
100
implements a 1-D IWT that, for each resolution level m at which a decomposition is made, uses dual wavelets {{tilde over (&psgr;)}
m,k
m
(x)} to corresponding standard wavelets {&psgr;
m,k
m
(x)} as the basic wavelets in the 1-D IWT and uses dual scaling functions {{tilde over (&phgr;)}
m,k
m
(x)} to corresponding standard scaling functions {&phgr;
m,k
m
(x)} as the basic scaling functions in the 1-D IWT. Each standard wavelet &psgr;
m,k
m
(x) and standard scaling function &phgr;
m,k
m
(x) is given by:
&psgr;
m,k
m
(
x
)=2
m/2
&psgr;(2
m
x−k
m
)
&phgr;
m,k
m
(
x
)=2
m/2
&phgr;(2
m
x−k
m
) (1)
where k
m
is a corresponding index for the resolution level m and the normalization factor 2
m/2
will be suppressed hereafter for computational efficiency.
In performing the 1-D IWT, the wavelet transform system
100
decomposes a 1-D set of original data samples f
M
at an original resolution level m=M into a 1-D set of standard scaling function coefficients c
N
in an L (low) frequency band at the resolution level m=N and 1-D sets of standard wavelet coefficients d
M−1
to d
N
in H (high) frequency bands at respectively the resolution levels m=M−1 to N.
The set of original data samples f
M
={f
M,n
}=f
M
(2
−M
n) is given by a 1-D function f
M
(x), where x=2
−M
n. The 1-D function f
M
(x) approximates another 1-D function f(x) at the original resolution level M. The set of original data samples f
M
extends in one spatial dimension, namely the x direction, and is first pre-processed by a pre-decomposition filter
102
of the 1-D wavelet transform system
100
. The pre-decomposition filter has a transfer function &phgr;(z)
−1
for mapping (i.e., converts) the 1-D set of original data samples f
M
into a 1-D set of standard scaling function coefficients c
M
in an L frequency band at the original resolution level M.
The transfer function &phgr;(z)
−1
is obtained from the following relationship at the resolution level m between a 1-D function f
m
(x), the standard scaling functions {&phgr;
m,k
m
(x)} and the set of standard scaling function coefficients c
m
={c
m,k
m
}:
f
m
(
x
)
=
∑
k
m
c
m
,
k
m
φ
m
,
k
m
(
x
)
(
2
)
where the 1-D function f
m
(x) approximates the function f(x) at the resolution level m. The transfer function &phgr;(z)
−1
is the inverse of a transfer function &phgr;(z). The transfer function &phgr;(z) is a polynomial that has the sequence of mapping coefficients {&phgr;
n
}={&phgr;
0,0
(n)} as its coefficients while the transfer function &phgr;(z)
−1
is a rational function that has a corresponding sequence of mapping coefficients {⊖
n
} as its poles. Thus, the pre-decomposition filter
102
comprises a 1-D IIR (infinite impulse response) filter that applies the sequence of mapping coefficients {⊖
n
} to the set of original data samples f
M
={f
M,n
} to generate the set of standard scaling function coefficients c
M
={c
M,k
M
}.
Then, the decomposition filter
104
of the 1-D wavelet transform system
100
decomposes the set of standard scaling function coefficients c
M
into the sets of standard scaling function and wavelet coefficients c
N
and d
M−1
to d
N
. To do this, in the present invention the decomposition filter
104
has a corresponding decomposition filter stage
106
for each resolution level m=M to N+1 at which a decomposition is made. The decomposition filter stage
106
for each resolution level m decomposes a 1-D set of standard scaling function coefficients c
m
in an L frequency band at the higher resolution level m into a 1-D set of standard scaling function coefficients c
m−1
in an L frequency band and a 1-D set of wavelet coefficients d
m−1
in an H frequency band at the next lower resolution level m−1.
This is done by the decomposition filter stage
106
according to the function f
m
(x) given in Eq. (2). Here, for each resolution level m, the function f
m
(x) further provides the following relationship between the set of standard scaling function coefficients c
m
at each resolution level m and the sets of standard scaling function and wavelet coefficients c
m−1
={c
m−1,k
m−1
} and d
m−1
={d
m−1,k
m−1
} at the next lower resolution level m−1:
∑
k
m
c
m
,
k
m
φ
m
,
k
m
(
x
)
=
∑
k
m
-
1
d
m
-
1
,
k
m
-
1
ψ
m
-
1
,
k
m
-
1
(
x
)
+
c
m
-
1
,
k
m
-
1
φ
m
-
1
,
k
m
-
1
(
x
)
.
(
3
)
In Eq. (3), the set of standard scaling function coefficients {c
m−1,k
m−1
} has the indexes {k
m−1
}={(k
m
−1)/2} for odd indexes {k
m
} and the set of standard wavelet coefficients {d
m−1,k
m−1
} has the indexes {k
m−1
}={k
m
/2} for even indexes {k
m
}.
Furthermore, there exists two 1-D sequence of decomposition coefficients {a
n
} and {b
n
} such that each standard scaling function &phgr;
m,k
m
(x) at a higher resolution level m is related to and can be decomposed into the standard wavelets and scaling functions {&psgr;
m,k
m
(x)} and {&phgr;
m,k
m
(x)} at the next lower resolution level m−1. This decomposition relation is given as follows:
φ
m
,
k
m
(
x
)
=
∑
k
m
-
1
a
k
m
-
2
k
m
-
1
φ
m
-
1
,
k
m
-
1
(
x
)
+
b
k
m
-
2
k
m
-
1
ψ
m
-
1
,
k
m
-
1
(
x
)
.
(
4
)
In view of Eqs. (3) and (4), the sets of standard scaling function and wavelet coefficients {c
m−1,k
m−1
} and {d
m−1,k
m−1
} at the resolution level m−1 are obtained according to the decomposition sequences:
c
m
-
1
,
k
m
-
1
=
∑
k
m
a
k
m
-
2
k
m
-
1
c
m
,
k
m
d
m
-
1
,
k
m
-
1
=
∑
k
m
b
k
m
-
2
k
m
-
1
c
m
,
k
m
.
(
5
)
It must be noted here that the dual wavelets {{tilde over (&psgr;)}
m,k
m
(x)} and the dual scaling functions {{tilde over (&phgr;)}
m,k
m
(x)} are used respectively as the basic wavelets and scaling functions in the 1-D IWT since the 1-D IWT is defined by:
c
m
,
k
m
=
∫
-
∞
∞
f
(
x
)
φ
~
m
,
k
m
(
x
)
ⅆ
x
d
m
,
k
m
=
∫
-
∞
∞
&it
Chang Jon
Pennie & Edmonds LLP
TeraLogic, Inc.
Wu Jingge
LandOfFree
System and method for performing wavelet and inverse wavelet... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with System and method for performing wavelet and inverse wavelet..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System and method for performing wavelet and inverse wavelet... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2511302