Image Compression Back
to main page

Bit Allocation
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 RateDistortion 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 RateDistortion theory is given in
[1], 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
calculated.
 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 [1] 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. 400402, Mar. 1991
 Liangjin Lin, Antonio Ortega, "BitRate
Control Using Piecewise Approximated
RateDistortion Characteristics",
IEEE Transactions on Circuits and Systems for
Video Technology, vol. 8, No. 4, pp. 446459
, Aug. 1998
 A. Ortega, "Optimal rate allocation under
multiple rate constraints'',
Data Compression Conference'96, Snowbird, UT,
Mar. 1996
Copyright (c) Satish Kumar. S 20012003. Last Modified  22 Oct 2001
Suggestions/Broken links/queries? Write to satish@debugmode.com
