to main page
The first step in compressing an image is to segregate
the image data into different classes. Depending on the
importance of the data it contains, each class is
allocated a portion of the total bit budget, such that
the compressed image has the minimum possible distortion.
This procedure is called Bit Allocation.
The Rate-Distortion theory is often used for solving
the problem of allocating bits to a set of classes, or
for bitrate control in general. The theory aims at
reducing the distortion for a given target bitrate, by
optimally allocating bits to the various classes of data.
One approach to solve the problem of Optimal Bit
Allocation using the Rate-Distortion theory is given in
, which is explained below.
- Initially, all classes are allocated a predefined
maximum number of bits.
- For each class, one bit is reduced from its quota
of allocated bits, and the distortion due to the
reduction of that 1 bit is calculated.
- Of all the classes, the class with mininum
distortion for a reduction of 1 bit is noted, and
1 bit is reduced from its quota of bits.
- The total distortion for all classes D is
- The total rate for all the classes is calculated
as R = p(i) * B(i), where p is the probability
and B is the bit allocation for each class.
- Compare the target rate and distortion
specifications with the values obtained above. If
not optimal, go to step 2.
In the approach explained above, we keep on reducing
one bit at a time till we achieve optimality either in
distortion or target rate, or both. An alternate approach
which is also mentioned in  is to initially start with
zero bits allocated for all classes, and to find the
class which is most 'benefitted' by getting an additional
bit. The 'benefit' of a class is defined as the decrease
in distortion for that class.
Fig 1. 'Benefit' of a bit is the
decrease in distortion due to receiving that bit.
As shown above, the benefit of a bit is a decreasing
function of the number of bits allocated previously to
the same class. Both approaches mentioned above can be
used to the Bit Allocation problem.
Resources related to Bit Allocation
- E. A. Riskin, "Optimum bit allocation via
the generalized BFOS algorithm,''
IEEE Transactions on Information Theory,
vol. 37, pp. 400-402, Mar. 1991
- Liang-jin Lin, Antonio Ortega, "Bit-Rate
Control Using Piecewise Approximated
IEEE Transactions on Circuits and Systems for
Video Technology, vol. 8, No. 4, pp. 446-459
, Aug. 1998
- A. Ortega, "Optimal rate allocation under
multiple rate constraints'',
Data Compression Conference'96, Snowbird, UT,
Copyright (c) Satish Kumar. S 2001-2003. Last Modified - 22 Oct 2001
Suggestions/Broken links/queries? Write to firstname.lastname@example.org