Databases Reference
In-Depth Information
Operational rate-distortion curve
Convex hull
Distortion
F I GU R E 13 . 8
Operational rate-distortion function.
assign an additional bit to the coefficient contributing the highest distortion. The reduction
in distortion can then be obtained using the operational rate-distortion function or through a
simulation process using a training set. This process can be repeated until the bit budget is
exhausted. This is a greedy approach in that at each step we try to maximize the impact of
one bit—the bit that is being allocated. However, that might not be the best use for the bit
when we look at the overall impact. Maybe it would have been better in terms of reducing the
overall distortion if instead of assigning one bit to the coefficient with the highest distortion
we assigned two bits to the coefficient with the next highest distortion. Exploring all the
possibilities available can be computationally expensive. To obtain a computationally tractable
solution, the problem of bit allocation can be posed as a dynamic programming problem.
A different approach was pioneered in the work of Shoham and Gersho [
197
]. Suppose
we have a bit allocation
B
, the corresponding average distortion
D
.The
problem of bit allocation can then be posed as that of finding the allocation
B
∗
that minimizes
D
(
B
)
, and rate
R
(
B
)
R
b
. Shoham and Gersho examined the
simpler unconstrained minimization of a function of the form
(
B
)
while satisfying the constraint that
R
(
B
)
J
=
D
(
B
)
+
λ
R
(
B
)
where the minimization is over all
B
in a specified set
S
. They noted that for any
λ
0,
the solution
B
∗
(λ)
to the unconstrained problem of minimizing
J
over all
B
∈
S
is also the
solution of the problem of minimizing
D
(
B
)
over all
B
∈
S
while satisfying the constraint that
B
∗
(λ))
. This latter constrained problem seems to be exactly the problem we are
interested in solving if we take
B
to be bit allocation,
D
R
(
B
)
R
(
(
B
)
and
R
(
B
)
to be the corresponding
B
∗
(λ))
distortion and rate, and
R
(
to be our rate constraint
R
b
. Of course, there is no indication
B
∗
(λ))
that for a given value of
λ
,
R
(
is equal to, or even close to,
R
b
. However, if we can find
