optimisation of 2- and 4-level BTCs, an optimised
3-level BTC is derived and explained in Section 5.
Extensive testing of the complete multi-level BTC
scheme has been carried out on 30 images and the
results are given in Section 6. Finally, a conclusion
is drawn.
2. Integrated multi-level BTC
As will be described in the next three sections,
development and optimisation of 2-, 3- and 4-level
BTCs are carried out separately. Various optimised
BTCs are combined to form an adaptive multi-level
BTC scheme for high-quality image coding. The
output can be switched automatically from 1- to
4-level by some pre-set thresholds of variance. The
1-level output is simply the sample mean of the
block. DRT#MGS without iteration is adopted
for 2-level output. Equal space partition (ESP) with
1-iteration, and DRT with 1-iteration are adopted
for 3- and 4-level outputs, respectively. For direct
comparison, the "nal bit-rate is set at 2 bpp, which
is the same as standard BTC.
3. Optimisation of 2-level BTC
In BTC, the sample mean of a block is used as the
threshold. It is optimal in terms of mean absolute
error but not mean square error (MSE). By study-
ing some high error sub-image patterns, we "nd
that many of them have biased intensity distribu-
tion. It is expected that the optimal threshold
should also be biased } towards the mean of dy-
namic range. Through close investigation, the DRT
and MGS algorithms which outperform known
optimisation techniques are derived. DRT is also
applicable to 3- and 4-level BTCs, as will be de-
scribed in Sections 4 and 5.
3.1. Standard BTC
In the standard 2-level BTC, there are three para-
meters to be coded: the sample means of lower and
upper regions, and the bitplane. The "rst two para-
meters preserve the block sample mean and the "rst
absolute moment. The former contains information
about the central tendency of the block, while the
latter contains dispersion information around the
sample mean and is a good indication of signal
activity, or degree of variation within a block. The
bitplane is an accurate bit map for the intensity
distribution of the block. The sample mean (s) and
absolute moment (a) are
s"
1
m
K\
G
x
G
, (1)
a"
1
m
K\
G
"x
G
!s", (2)
where m is the number of pixels in a block and x
G
is
the pixel intensity. By taking s as the threshold, the
two output values (a, b) are
a"s!
ma
2p
, (3a)
b"s#
ma
2q
, (3b)
where p is the number of pixels with intensity smaller
than s and q is the complement. It is also note-
worthy that BTC is a minimum mean square error
(MMSE) quantiser provided that the threshold is
set equal to s. In view of MMSE, a and b become
a"
1
p
V
G
Q
x
G
, (4a)
b"
1
q
V
G
V
Q
x
G
. (4b)
Refer to Eqs. (4a) and (4b), the computation in BTC
is very simple. Only comparisons and additions,
together with three averaging (1 for sample mean)
per block are required. The decoding is even
simpler. There is no calculation at all. It consists of
pattern "ll to either a or b, as determined by the
corresponding bit value in the bitplane.
3.2. ESR of 2-level BTC
In pixel classi"cation, it seems equally likely to
classify those pixels with intensity exactly equal to
the threshold to either lower or upper half. How-
ever, we "nd that the settlement of these pixels is
not immaterial. A simple but e!ective modi"cation
K.W. Chan, K.L. Chan / Signal Processing: Image Communication 16 (2001) 445}459 447