Image analysis – Image compression or coding – Pyramid – hierarchy – or tree structure
Reexamination Certificate
2000-02-28
2003-07-01
Do, Anh Hong (Department: 2624)
Image analysis
Image compression or coding
Pyramid, hierarchy, or tree structure
C382S232000, C382S248000
Reexamination Certificate
active
06587589
ABSTRACT:
FIELD OF THE INVENTION
The present invention is generally related to two-dimensional discrete wavelet transform (2-D DWT), and more particularly to an architecture for performing the two-dimensional discrete wavelet transform.
BACKGROUND OF THE INVENTION
Recently, a wide variety of microprocessors aimed on having the capabilities for simultaneously processing audio signals and video images are brought out due to the mushroom development in the very-large-scaled integration (VLSI) circuit. The technique of the two-dimensional discrete wavelet transform (2-D DWT) is the crux of the image compression standard of new generation, such as JPEG-2000 still image compression standard. Thus, the technique of the two-dimensional discrete wavelet transform will play a decisive role in the image compression/decompression system. Nowadays the research of the two-dimensional discrete wavelet transform in many applications such as audio signal processing, computer graphics, numerical analysis, radar target identification, is in progress. In general, the basic architecture of the two-dimensional discrete wavelet transform is composed of multirate filters. Because the quantity of processing data in practical applications, e.g. digital camera, is extraordinarily enormous, it is desirable to develop a high-efficient, low-cost architecture for performing the two-dimensional discrete wavelet transform.
The mathematical formulas of the 2-D DWT using the separable FIR filters for implementation are represented in the following equations:
x
LL
J
(
n
1
,
n
2
)
=
∑
i
1
=
0
K
-
1
∑
i
2
=
0
K
-
1
g
(
i
1
)
·
g
(
i
2
)
·
x
LL
J
-
1
(
2
n
1
-
i
1
)
(
2
n
2
-
i
2
)
(
1
)
x
LH
J
(
n
1
,
n
2
)
=
∑
i
1
=
0
K
-
1
∑
i
2
=
0
K
-
1
g
(
i
1
)
·
h
(
i
2
)
·
x
LL
J
-
1
(
2
n
1
-
i
1
)
(
2
n
2
-
i
2
)
(
2
)
x
HL
J
(
n
1
,
n
2
)
=
∑
i
1
=
0
K
-
1
∑
i
2
=
0
K
-
1
h
(
i
1
)
·
g
(
i
2
)
·
x
LL
J
-
1
(
2
n
1
-
i
1
)
(
2
n
2
-
i
2
)
(
3
)
x
HH
J
(
n
1
,
n
2
)
=
∑
i
1
=
0
K
-
1
∑
i
2
=
0
K
-
1
h
(
i
1
)
·
h
(
i
2
)
·
x
LL
J
-
1
(
2
n
1
-
i
1
)
(
2
n
2
-
i
2
)
(
4
)
where the J is the number of decomposition level, k is the filter length, g(n) and h(n) are the impulse response of the low pass filter G(z) and high pass filter H(z) respectively. x
LL
0
(n
1
, n
2
) represents the input image.
Please refer to
FIG. 1
which illustrates a three-level architecture for performing the two-dimensional discrete wavelet transform. Each decomposition level includes two stages, wherein the firs stage performs the horizontal filtering operation and the second stage performs the vertical filter operation. In the first level decomposition, the size of the input image is N×N, the outputs are three decomposed subbands LH, HL, and HH all having a size of N/
2
×N/
2
. In the second level decomposition, the input is the LL band, the outputs are three decomposed subbands LLLH, LLHL, and LLHH all having a size of N/
4
×N/
4
. In the third level decomposition, the input image is the LLLL band, and the outputs are four decomposed subbands (LL)
2
LL, (LL)
2
LH, (LL)
2
HL, and (LL)
2
HH all having a size of N/
8
×N/
8
. The result of decomposition operation for level above three can be deduced by analogy.
Among the present architectures for performing the two-dimensional discrete wavelet transform, the most common and well-known architecture is the parallel filter architecture. The design of the parallel filter architecture is based on the modified recursive pyramid algorithm (MRPA) to dispersively interpolate the computations of the second and the subsequent levels in the computation of the first level. In the beginning, the MRPA is applied to the one-dimensional discrete wavelet transform (1-D DWT). The quantity of processing data in each level is half of that in the previous level due to decimation operation, and thus the total quantity of processing data is:
∑
L
=
1
J
N
2
L
-
1
=
N
+
N
2
+
N
2
2
+
N
2
3
+
…
+
N
2
J
-
1
=
2
(
1
-
2
-
J
)
N
(
5
)
where J is the number of level, N is the quantity of the processing data in the first level, N/
2
is the quantity of processing data in the second level, . . . and N/
2
J−1
is the quantity of processing data in the J
th
level. When the number of the level J is large enough, Eq. (5) can be simplified to Eq. (6):
2(1−2
−J
)N≈2N=N+N (6)
Because the quantity of processing data in the first level is identical to that in the second and the subsequent levels, the computing time of the first level can be filled up as shown in FIG.
2
. In the mean time, the hardware will be fully utilized, and thus the MRPA is suitable for the one-dimensional discrete wavelet transform.
Nonetheless, we found that the MRPA is not suitable for the two-dimensional discrete wavelet transform. Please refer to
FIG. 3
showing the two-dimensional discrete wavelet transform employing modified recursive pyramid algorithm (MRPA). Because the quantity of processing data in each level is one-fourth of that in the previous level, the total quantity of the processing data is:
∑
L
=
1
J
N
2
4
L
-
1
=
N
2
+
N
2
4
+
N
2
4
2
+
N
2
4
3
+
…
+
N
2
4
J
-
1
=
4
3
(
1
-
4
-
J
)
N
2
(
7
)
where J is the number of level, N
2
is the quantity of processing data in the first level, N
2
/
4
is the quantity of processing data in the second level, . . . , and N
2
/
4
J−1
is the quantity of processing data in the J
th
level. When the number of level J is large enough, Eq. (7) can be simplified to Eq. (8):
4
3
(
1
-
4
-
J
)
N
2
≈
4
3
N
2
=
N
2
+
1
3
N
2
(
8
)
Because the quantity of processing data in the second and the subsequent levels (N
2
/
3
) is one-third of that in the first level (N
2
) the computing time of the first decomposition level will not be filled up and then the hardware will enter into idle state. That renders the hardware utilization low, and it requires a complex control circuit to process the interleading data flow among the levels.
Please refer to
FIG. 4
which is a schematic diagram illustrating the parallel filter architecture. The parallel filter architecture includes four filters: Hor
1
, Hor
2
, Ver
1
, and Ver
2
. The transpose memories Storage
1
and Storage
2
are used to perform transpose operation. The Hor
1
performs horizontal filtering operation of the first level, Hor
2
performs the horizontal filtering operation of the second and the subsequent levels, and Ver
1
and Ver
2
performs the overall vertical filtering operation.
Please refer to
FIG. 5
which illustrates the operating configuration of the architecture of FIG.
4
. The individual hardware utilization of the four filters and average hardware utilization can be evaluated as the following equations, where J is the number of level:
Hor1: 1 (9)
Ver1
:
∑
L
=
1
J
1
2
·
4
L
-
1
=
1
2
+
1
8
+
1
32
+
…
+
1
2
·
4
J
-
1
=
2
3
(
1
-
4
-
J
)
(
10
)
Ver2
:
∑
L
=
1
J
1
2
·
4
L
-
1
=
1
2
+
1
8
+
1
32
+
…
+
1
2
·
4
J
-
1
=
2
3
(
1
-
4
-
J
)
(
11
)
Hor2
:
∑
L
=
2
J
1
4
L
-
1
=
0
+
1
4
+
1
16
+
1
64
+
…
+
1
4
J
-
1
=
1
3
(
1
-
4
-
(
J
-
1
)
)
(
12
)
Average
:
1
4
(
Hor1
+
Ver1
+
Ver2
+
Hor2
)
=
2
3
(
1
-
4
-
J
)
(
13
)
Table 1 lists the hardware utilization of the parallel filter architecture in different level:
TABLE 1
2-D DWT
Hardware Utilization
Level
Hor 1
Ver 1
Ver 2
Hor 2
Average
1
1 = 100%
1/2 = 50%
1/2 = 50%
0
50%
2
1 = 100%
5/8 = 62.5%
5/8 = 62.5%
1/4 = 25%
62
Chen Liang-Gee
Lai Yeong-Kang
Liu Yuan-Chen
Wu Po-Cheng
Do Anh Hong
Michael Best & Friedrich LLC
National Science Council
LandOfFree
Architecture for performing two-dimensional discrete 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 Architecture for performing two-dimensional discrete wavelet..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Architecture for performing two-dimensional discrete wavelet... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3108216