Databases Reference
In-Depth Information
Stuart Lloyd [
129
] used this approach to generate the
pdf
-optimized scalar quantizer, except
that instead of using a training set, he assumed that the source distribution
f
X
(
x
)
was known.
The Lloyd algorithm functions as follows:
1.
Start with an initial set of reconstruction values
y
(
1
)
i
M
D
(
0
)
=
. Set
k
=
1
,
0. Select
i
=
1
.
2.
Find decision boundaries
threshold
y
(
k
)
y
(
k
)
j
j
+
1
+
b
(
k
)
j
=
j
=
1
,
2
,...,
M
−
1
2
3.
Compute the distortion
b
(
k
)
i
b
(
k
)
i
−
M
D
(
k
)
=
2
f
X
(
1
(
x
−
y
i
)
x
)
dx
i
=
1
4.
If
D
(
k
)
−
D
(
k
−
1
)
<
, stop; otherwise, continue.
5.
k
=
k
+
1. Compute new reconstruction values
b
(
k
−
1
)
j
b
(
k
−
1
)
j
−
xf
X
(
x
)
dx
y
(
k
)
j
1
=
b
(
k
−
1
)
j
b
(
k
−
1
)
j
−
1
f
X
(
x
)
dx
Go to Step 2.
Linde, Buzo, and Gray generalized this algorithm to the case where the inputs are no longer
scalars [
137
]. For the case where the distribution is known, the algorithm looks very much
like the Lloyd algorithm described above.
1.
Start with an initial set of reconstruction values
y
(
1
)
i
M
D
(
0
)
=
=
,
. Set
k
1
0. Select
i
=
1
.
2.
Find quantization regions
threshold
V
(
k
)
i
={
x
:
d
(
x
,
y
i
)<
d
(
x
,
y
j
)
∀
j
=
i
}
j
=
1
,
2
,...,
M
3.
Compute the distortion
M
2
y
(
k
)
i
D
(
k
)
=
x
−
f
X
(
x
)
d
x
V
(
k
)
i
i
=
1
D
(
k
)
−
D
(
k
−
1
)
)
D
(
k
)
(
4.
If
<
, stop; otherwise, continue.
1. Find new reconstruction values
y
(
k
)
i
M
i
that are the centroids of
V
(
k
−
1
)
i
.
5.
k
=
k
+
=
1
Go to Step 2.
