Databases Reference
In-Depth Information
F I GU R E 18 . 17
Final reconstructed Elif image.
where
D
is ameasure of the distortion, and
R
represents the number of bits required to represent
the block. We could then either subdivide or not depending on the value of
J
.
We can also start out with range blocks that have the minimum size (also called the
atomic
blocks
) and obtain larger blocks via merging smaller blocks.
There are a number of ways in which we can perform the subdivision. The most commonly
known approach is
quadtree partitioning
, initially introduced by Samet [
249
]. In quadtree
partitioning we start by dividing up the image into the maximum-size range blocks. If a
particular block does not have a satisfactory reconstruction, we can divide it up into four
blocks. These blocks in turn can also, if needed, be divided into four blocks. An example
of quadtree partitioning can be seen in Figure
18.18
. In this particular case there are three
possible sizes for the range blocks. Generally, we would like to keep the minimum size of the
range block small if fine detail in the image is of greater importance [
250
]. Since we have
multiple sizes for the range blocks, we also need multiple sizes for the domain blocks.
Quadtree partitioning is not the only method of partitioning available. Another popular
method of partitioning is the HV method. In this method we allow the use of rectangular
regions. Instead of dividing a square region into four more square regions, rectangular regions
are divided either vertically or horizontally in order to generate more homogeneous regions.
In particular, if there are vertical or horizontal edges in a block, it is partitioned along these
edges. One way to obtain the locations of partitions for a given
M
×
N
range block is to
calculate the biased vertical and horizontal differences:
⎛
⎝
j
⎞
min
(
i
,
N
−
i
−
1
)
⎠
v
i
=
I
i
,
j
−
I
i
+
1
,
j
N
−
1
j
⎛
⎝
j
⎞
min
(
j
,
M
−
j
−
1
)
⎠
h
j
=
I
i
,
j
−
I
i
,
j
+
1
M
−
1
j
