Graphics Reference
In-Depth Information
3.2 Hilbert Scanned Image
Hilbert curve is one of the space filling curves, published by G. Peano in
1890. The Hilbert curve has a one-to-one mapping between an n-dimensional
space and a one dimensional space, which preserves point neighborhoods
as much as possible. There are many applications of this curve. A review
on the applications of Hilbert curve can be found in [137, 155]. Some of
the researchers have already used this curve in the area of image process-
ing. Reported works in the area of image compression can be found in
[5, 4, 45, 83, 84, 85, 86, 126, 154, 153].
Let
R
n
be an n-dimensional space. The Peano curve published in 1890
is a locus of points (
y
1
,y
2
,
R
n
···
y
n
)
∈
defined by continuous functions
R
1
) where 0
y
1
=
χ
1
(
ν
),
y
2
=
χ
2
(
ν
)
···
y
n
=
χ
n
(
ν
), (
ν
∈
≤
y
1
,y
2
,
···
y
n
<
1
ν<
1. It was an analytical solution of a space filling curve. In
1891, Hilbert drew a curve having the space filling property in
R
2
. Hilbert
found a one-to-one mapping between segments on the line and quadrants
on the square. Figure 3.1 shows the Hilbert curve with different resolutions.
Hilbert scan considers the positions on the square through which the curve
passes. Therefore, a Hilbert scanned image or simply a Hilbert image is a one
dimensional image with its pixels identical to those through which the curve
passes. Thus, it maintains the neighborhood property.
A Hilbert image or a Hilbert scanned image is a set of ordered pixels that
can be obtained by scanning the positions of pixels through which this curve
passes.
≤
and 0
3.2.1 Construction of Hilbert Curve
Construction of Hilbert curve, following Hilbert's ideas, considers a square
that is filled by the curve. Since our objective is to scan a gray tone image
and produce a Hilbert scanned image for the study of image compression,
we shall explain the basic philosophy behind construction of the curve and
provide a scheme through which real life images can be converted into Hilbert
scanned images. We also provide a scheme for inverse mapping to get back
gray tone images from the Hilbert scanned images.
First of all, we divide the square as shown in Figure 3.2 into four quarters.
The construction starts with a curve
H
0
, which connects the centers of the
quadrants by three line segments. Let us assume the size of the segments to
be 1. In the next step, we produce four copies (reduced by 1/2) of this initial
stage and place the copies into the quarters as shown. Thereby we rotate the
first copy clockwise and the last one counterclockwise by 90 degrees. Then we
connect the start and end points of these four curves using three line segments
(of size 1/2) as shown and call the resulting curve
H
1
. In the next step, we
scale
H
1
by 1/2 and place four copies into the quadrants of the square as in
step one. Again we connect using three line segments (now of size 1/4) and
obtain
H
2
. This curve contains 16 copies of
H
0
, each of size 1/4. As a general
Search WWH ::
Custom Search