Databases Reference
In-Depth Information
of the quantization region should cover the output space of the source. In other words, the
quantization region should
tile
space. A two-dimensional region can be tiled by squares, but it
cannot be tiled by circles. If we tried to tile the space with circles, we would either get overlaps
or holes.
Apart from squares, other shapes that tile space include rectangles and hexagons. It turns
out that the best shape to pick for a quantization region in two dimensions is a hexagon [
149
].
In two dimensions, it is relatively easy to find the shapes that tile space, then select the one
that gives the smallest amount of granular error. However, when we start looking at higher
dimensions, it is difficult, if not impossible, to visualize different shapes, let alone find which
ones tile space. An easy way out of this dilemma is to remember that a quantizer can be
completely defined by its output points. In order for this quantizer to possess structure, these
points should be spaced in some regular manner.
Regular arrangements of output points in space are called
lattices
. Mathematically, we can
define a lattice as follows:
Let
{
a
1
,
a
2
,...,
a
L
}
be
L
independent
L
-dimensional vectors. Then the set
x
L
L
=
:
x
=
u
i
a
i
(10)
i
=
1
are all integers.
When a subset of lattice points is used as the output points of a vector quantizer, the quantizer
is known as a
lattice vector quantizer
. From this definition, the pyramid vector quantizer
described earlier can be viewed as a lattice vector quantizer. Basing a quantizer on a lattice
solves the storage problem. As any lattice point can be regenerated if we know the basis set,
there is no need to store the output points. Further, the highly structured nature of lattices
makes finding the closest output point to an input relatively simple. Note that what we give
up when we use lattice vector quantizers is the clustering property of LBG quantizers.
Let's take a look at a few examples of lattices in two dimensions. If we pick
a
1
=
(
is a lattice if
{
u
i
}
,
)
1
0
and
a
2
=
(
, we obtain the integer lattice—the lattice that contains all points in two dimensions
whose coordinates are integers.
If we pick
a
1
0
,
1
)
, we get the lattice shown in
Figure
10.24
. This lattice has a rather interesting property. Any point in the lattice is given by
na
1
+
=
(
1
,
1
)
and
a
2
=
(
1
,
−
1
)
ma
2
, where
n
and
m
are integers. But
n
+
m
na
1
+
ma
2
=
n
−
m
and the sum of the coefficients is
n
2
n
, which is even for all
n
. Therefore, all
points in this lattice have an even coordinate sum. Lattices with these properties are called
D
lattices
.
Finally, if
a
1
+
m
+
n
−
m
=
2
, we get the hexagonal lattice shown in
Figure
10.25
. This is an example of an
A lattice
.
There are a large number of lattices that can be used to obtain lattice vector quantizers.
In fact, given a dimension
L
, there are an infinite number of possible sets of
L
independent
vectors. Among these, we would like to pick the lattice that produces the greatest reduction in
√
3
1
=
(
,
)
=
−
2
,
1
0
and
a
2
