Digital Signal Processing Reference
In-Depth Information
5.4.1.2 Digital Implementation
It seems that the starlet transform, or isotropic a trous wavelet transform (see Sec-
tion 3.5), is especially well adapted to the needs of the digital curvelet transform.
The algorithm decomposes a discrete
N
×
N
image
f
[
k
,
l
] as a superposition of the
form
j
=
1
w
j
[
k
J
f
[
k
,
l
]
=
c
J
[
k
,
l
]
+
,
l
]
,
where
c
J
is the coarse or smooth version of the original image
f
and
w
j
represents
the details of
f
at resolution level
j
. Thus the algorithm outputs
J
+
1 subband
arrays each of size
N
N
.
A sketch of the DCTG1 algorithm is as follows:
×
Algorithm 14
First-Generation Discrete Curvelet Transform
Task:
Compute the DCTG1 of an
N
×
N
image
f
, using one of the DRT imple-
mentations of Section 5.3.2.
Parameters:
Number of resolution levels
J
, minimum block size
B
min
.
Apply the starlet transform to
f
and get the set
W ={
w
1
,...,w
J
,
c
J
}
.
Set
B
1
=
B
min
.
for
j
=
1
,...,
J
do
1. Partition the subband
w
j
with a block size
B
j
and apply the DRT to each
block: we get the curvelet coefficients
α
j
.
2.
if
j
modulo 2
=
1
then
B
j
+
1
=
2
B
j
,
3.
else
B
j
+
1
=
B
j
.
4.
end if
Output:
C ={
α
1
,α
2
,α
3
,...,α
J
,
c
J
}
,theDCTG1of
f
.
The side length of the localizing windows is doubled
at every other
dyadic sub-
band, hence maintaining the fundamental property of the curvelet transform, which
says that elements of length about 2
−
j
/
2
serve for the analysis and synthesis of the
j
th subband [2
j
2
j
+
1
]. Note also that the coarse description of the image
c
J
is left
intact. In the results shown in this chapter, we used the default value
B
min
=
,
16 pix-
els in our implementation. Figure 5.11 gives an overview of the organization of the
DCTG1 algorithm.
This implementation of the DCTG1 is also redundant. The redundancy factor
is equal to 16
J
+
1 whenever
J
scales are employed. The DCTG1 algorithm enjoys
exact reconstruction and stability as each step of the analysis transform in Algorithm
is itself invertible. We leave as a simple exercise to show that the computational
complexity of the DCTG1 algorithmwe described here based on the DRT of Fig. 5.4
is
O
(
N
2
(log
N
)
2
) for an
N
N
image. Figure 5.12 shows a few curvelets at different
scales, orientations, and locations.
×
