Cyber Journals: Multidisciplinary Journals in Science and Technology, Journal of Selected Areas in Telecommunications (JSAT), February Edition, 2011

Image Compression Using

Block Truncation Coding
Doaa Mohammed, Fatma Abou-Chadi (Senior Member, IEEE.)

image quality than image compression using BTC. Moreover,

Abstract—The present work investigates image compression the AMBTC is quite faster compared to BTC this paper
using block truncation coding. Two algorithms were selected represents comparative study between BTC and AMBTC
namely, the original block truncation coding (BTC) and Absolute .This paper is organized as follows: Section II explains BTC
Moment block truncation coding (AMBTC) and a comparative algorithm. Section III explains algorithm of AMBTC. Section
study was performed. Both of two techniques rely on applying
IV explains image characteristic Section V briefly explains the
divided image into non overlapping blocks. They differ in the
way of selecting the quantization level in order to remove
performance evaluation criteria. Section VI introduces the
redundancy. Objectives measures were used to evaluate the experimental results and Section VII gives the concluding
image quality such as: Peak Signal to Noise Ratio (PSNR), remarks.
Weighted Peak Signal to Noise Ratio (WPSNR), Bit Rate (BR)
and Structural Similarity Index (SSIM).The results have shown II. BTC ALGORITHM
that the ATBTC algorithm outperforms the BTC. It has been
show that the image compression using AMBTC provides better Block Truncation Coding (BTC) is a well-known
image quality than image compression using BTC at the same bit
compression scheme proposed in 1979 for the grayscale
rate. Moreover, the AMBTC is quite faster compared to BTC
images. It was also called the moment-preserving block
Index Terms—BTC, AMBTC, WPSNR, SSIM. truncation [4]-[5] because it preserves the first and second
moments of each image block. The BTC algorithm involves
I. INTRODUCTION the following steps:
• Step1: The given image is divided into non overlapping
T he amount of image data grows day by day. Large storage
and bandwidth are needed to store and transmit the
images, which is quite costly. Hence methods to compress
rectangular regions. For the sake of simplicity the
blocks were let to be square regions of size m x m.
• Step 2: For a two level (1 bit) quantizer, the idea is to select
the image data are essentially now-a-days. The image
two luminance values to represent each pixel in the
compression techniques are categorized into two main
classifications namely Lossy compression techniques and block. These values are the mean x and standard
Lossless compression techniques [1]. Lossless compression deviation σ .
ratio gives good quality of compressed images, but yields only
1 n
less compression whereas the lossy compression techniques
[2] lead to loss of data with higher compression ratio. JPEG
x =
n
∑ i =1
xi (1)
[1] and Block Truncation Coding [3] is a lossy image 1 n
compression techniques .It is a simple technique which σ =
n
∑ ( xi − xi ) 2 (2)
involves less computational complexity. BTC is a recent i =1

technique used for compression of monochrome image data. It

is one-bit adaptive moment-preserving quantizer that Where xi represents the ith pixel value of the image
preserves certain statistical moments of small blocks of the block and n is the total number of pixels in that
input image in the quantized output. The original algorithm of block.
BTC preserves the standard mean and the standard deviation
[9]. The statistical overheads Mean and the Standard deviation
are to be coded as part of the block. The truncated block of the • Step3: The two values x and σ are termed as quantizers of
BTC is the one-bit output of the quantizer for every pixel in BTC. Taking x as the threshold value a two-level
the block .Various methods have been proposed during last bit plane is obtained by comparing each pixel value
twenty years for image compression such BTC and Absolute xi with the threshold. A binary block, denoted by
Moment Block Truncation Coding AMBTC [6].AMBTC B, is also used to represent the pixels. We can use
preserves the higher mean and lower mean of the blocks and “1” to represent a pixel whose gray level is grater
use this quantity to quantize output. AMBTC provides better than or equal to x and “0” to represent a pixel
whose gray level is less than
⎧1 xi ≥ x
B=⎨ (3)
⎩0 xi p x
9
 By this process each block is reduced to a bit
plane. For example, a block of 4 x 4 pixels will • Step 5: In the decoder, an image block is reconstructed by
give a 32 bit compressed data, amounting to 2 bit replacing the `1’ s with XH and the ’0’'s by XL In
per pixel (bpp). the AMBTC, we need 16 bits to code the bit plane
• Step 4: In the decoder an image block is reconstructed by which is same as in the BTC. But, AMBTC
replacing ‘1’s in the bit plane with H and the ‘0’s requires less computation than BTC
with L, which are given by:
⎧X B=0
X =⎨ L (9)
p ⎩X H B =1
H = x +σ (4)
q AMBTC has several advantages over BTC one
advantage is in the case that the quantizer is used
q to transmit an image from transmitter to a receiver,
L = x −σ (5) it is necessary to compute at the transmitter the two
p quantities, the sample mean and the sample
standard deviation for BTC and sample first
Where p and q are the number of 0’s and 1’s in the absolute central moment for AMBTC. When we
compressed bit plane respectively. compare the necessary computation for deviation
information, we will see that in case of standard
III. ALGORITHM OF AMBTC BTC it is necessary to compute a sum of m values
and each of them will be squared while in case of
Lema and Mitchell [7] presented a simple and fast variant AMBTC it is only necessary to compute the sum of
of BTC, named Absolute Moment BTC (AMBTC) [8] that these m values. Since the multiplication time is
preserves the higher mean and lower mean of a block. The several times greater than the addition time in most
AMBTC algorithm involves the following steps: digital processors, thus using AMBTC the total
• Step 1: An image is divided into non-overlapping blocks. calculation time at the transmitter is significantly
The size of a block could be (4 x 4) or (8 x 8), etc. reduced.
• Step 2: Calculate the average gray level of the block (4x4) VI. IMAGE CHARACTERISTICS
as equations(6):
• Step 3: Pixels in the image block are then classified into The spatial frequency measurement (SFM) [9] indicates the
two ranges of values. The upper range is those overall activity level in an image. SFM is defined as follow:
gray levels which are greater than the block
average gray level ( x ) and the remaining brought (10)
SFM = ( R ) 2 + (C ) 2
into the lower range. The mean of higher range XH
and the lower range XL are calculated as :
1 N ,M
1 n
(6
C= ∑ [x(m, n) − x(m −1, n)]2 (11)
xH =
K
∑
xi f x
xi )
MN n=1,m=2

1 n
1 M ,N
∑ ∑[x(m, n) − x(m, n −1)]
2
xL = xi R= (12)
16 − K xi p x (7 MN m=1n=2

Where R is row frequency, C is column frequency, x (m, n)

Here k is the number of pixels whose gray level is denotes the samples of image, M and N are number of pixels
greater than x . in row and column directions, respectively. The large value of
• Step 4: Binary block, denoted by B, is also used to represent SFM means that image contains components in high
the pixels. We can use “1” to represent a pixel frequency area. It returns that low redundant image, which is
whose gray level is grater than or equal to x and difficult for compression. Small value of SFM means that
“0” to represent a pixel whose gray level is less image contains components in low frequency area. It returns
than x . The encoder writes XH , XL. Then the that high redundant image, which is easy for compression.
total number of bits required for a block is 8+8+16
=32 bits. Thus, the bit rate for the AMBTC V. IMAGE QUALITY MEASUREMENTS
algorithm is 2 bpp .
Image quality measures play important roles in various
images processing application .Once image compression
⎧1 xi ≥ x
B=⎨ (8
⎩0 xi p x
10
system has been designed and implemented, it is important to C. Bit Rate (BR)
be able to evaluate its performance. This evaluation should be
The performance of image compression schemes can be
done in such a way to be able to compare results against other
specified in terms of compression efficiency. Compression
image compression techniques. The image quality metrics can
efficiency is measured by the compression ratio or by the bit
be broadly classified into two categories, subjective and
rate. Compression ratio is the ratio of the size of original
objective. Subjective image quality is a method of evaluation
image to the size of the compressed image; the bit rate is the
of images by the viewers read images directly to determine
number of bits per pixel required by the compressed image
their quality. In objective measures of image quality metrics,
some statistical indices are calculated to indicate the image CR = size of original image / size of the compressed image
quality. In our work we will focus in objective[9]-[10]
measures such as Peak Signal to Noise Ratio (PSNR), The compression ratio and bit rate are related. Let b be the
Weighted Peak Signal to Noise Ratio (WPSNR), Bit Rate number of bits per pixel (bit depth) of the uncompressed
(BR) and Structural Similarity Index (SSIM). image, CR the compression ratio, and BR the bit rate. The bit
rate ratio is given by
A. Peak Signal to Noise Ratio (PSNR)
b (19)
    The PSNR is most commonly used as a measure of quality BR =
CR
of reconstruction of lossy compression It is an attractive  

measure for the loss of image quality due to its simplicity and
mathematical convenience .Peak signal-to-noise ratio (PSNR) D. Structural Similarity Index (SSIM).
is a qualitative measure based on the mean-square-error of the Another category of image quality measures is based on
reconstructed imageَ .If the reconstructed image is close to the the assumption that the human visual system is highly adapted
original image, then MSE is small and PSNR takes a large to extract structural information from the viewing field [12].
The error sensitivity approach estimates perceived errors to
value .PSNR is dimensionless and is expressed in decibel .
quantify image degradations, while this approach considers
Peak Signal-to-Noise Ratio (PSNR) avoids this problem by image degradations as perceived structural information
scaling the MSE according to the image range .PSNR is variation. The structural Similarity (SSIM) index can be
defined as follow: calculated as a function of three components: luminance,
contrast and structure.
1 M N
(13)
∑ ∑ [y ( i , j ) − x (i, j )]
2
=
SSIM ( x, y) = [l ( x, y)] ⋅ [c( x, y)] ⋅ [s( x, y)]
MSE α β γ
(20)
MN i =1 j =1

⎛ L2 ⎞ (14) This results in a specific form of the SSIM index:

PSNR = 10 log ⎜⎜ ⎟⎟
⎝ MSE ⎠ (2 µµ y + C1 )(2σ xy + C 2 ) (21)
SSIM ( x , y ) =
x

Where L is the dynamic range of the pixel values (255 for 8- (µ + µ y2 + C1 )(σ x2 + σ y2 + C 2 )
2
x

bit grayscale images).

Where C1= (K1 L)2, K1<<1 and C2= (K2 L)2, K2<<1.
B. Weighted Peak Signal to Noise Ratio (WPSNR)
The weighted PSNR (WPSNR) has been defined as an
VI. EXPERIMENTAL RESULTS
extension of the traditional PSNR. It weights each term of the
PSNR by local "activity" factor (linked to the local Five test images (512×512, 8 bits per pixel) with
variance)[11].weighted PSNR (WPSNR) take into account the different spatial and frequency characteristics, as shown in
local human visual system (HVS) sensitivity, it is a measure Fig.1: Lena, Baboon, peppers, Goldhill and Barb are used.
criteria which hold account of the neighbors of the studied Characteristics of test images are evaluated in spatial domain
pixels. using spatial frequency measure (SFM) [9].

⎛ L2 ⎞ (15)
WPSNR = 10 log ⎜ ⎟ A. Measuring Spatial Frequency (SFM)
⎜
⎝ ( y − x ). NVF 2
⎟
⎠ The Spatial frequencies (SFM) and values computed for the
Where NVF = 1 (16) above set of images are given in Table 1 (16)
(1 + θ σ ( i , j ))
2
x
1 L L TABLE 1 spatial frequency measure of images
(17)
2 ∑ ∑
σ x2 (i, j ) = ( x(i + m, j + n) − x (i, j ))2
(2 L + 1) m = − L n = − L
D Lena Baboon Peppers Goldhill Barb
θ = (18)
σ 2
x max

Where ó2xmax is the maximum local variance of a given image SFM 14.0421 36.5146 15.8446 16.1666 29.4567
and D ∈ [50 ,150 ] is a determined parameter.

11
 The above tables assure that the image compression using
AMBTC provides better image quality than image compression
using BTC at the same bit rate. Moreover, the AMBTC is quite
faster compared to BTC. Figure 2,3,4,5 and Figure6 shows the
original and compressed images using BTC and AMBTC.

Lena Baboon Peppers

Goldhill Barb
Figure 1. Image Database (size of 512×512 pixels). (a) (b) (c)
Figure 2. (a)Original image, (b), (c) compressed images
Test image Baboon has a lot of details and consequently large using BTC and AMBTC respectively
SFM. Large value of SFM means that image contains
components in high frequency area. It returns that Baboon
presents low redundant image, which is difficult for
compression. Test image Lena are images has low details and
consequently small SFM. Small value of SFM means that
image contains components in low frequency area. It returns
that Lena presents high redundant image, which is easy for
compression than Baboon.

B. Evaluating Perceptual Quality

(a) (b) (c)
Figure 3. (a)Original image, (b), (c) compressed images
To compare between the used compression methods, four using BTC and AMBTC respectively
parameters were calculated. These are BR, PSNR, wPSNR,
and SSIM when a block size is 8*8. These values are listed in
Table 2.
Table 2 BTC and AMBTC parameters

BR PSNR WPSNR SSIM

BTC 1.25 29.5552 34.6005 0.8741
Lena
AMBTC 1.25 29.9419 34.9786 0.8821
(a) (b) (c)
BTC 1.25 24.7720 33.0637 0.8264 Figure 4. (a)Original image, (b), (c) compressed images
Babbon using BTC and AMBTC respectively
AMBTC 1.25 25.1861 33.7929 0.8277

BTC 1.25 29.0598 34.1210 0.8628

Peppers
AMBTC 1.25 29.4614 34.6366 0.8718

BTC 1.25 29.5163 33.5522 0.8459

Goldhill
AMBTC 1.25 29.9311 34.0911 0.8529

BTC 1.25 28.2149 33.7120 0.8613 (a) (b) (c)

Barb Figure 5. (a)Original image, (b), (c) compressed images
using BTC and AMBTC respectively
AMBTC 1.25 28.5985 34.0669 0.8667

12
 [8] W. J. Chen and S. C. Tai, “Postprocessing Techniques for Absolute
Moment Block Truncation Coding“ Proc. of ICS'98, Workshop on
Image Processing and Character Recognition, pp. 125-130, Dec. 17-19,
1998, Tainan, Taiwan.
[9] A. M. Eskicioglu and P.S. Fisher, “Image quality measures and their
performance,” IEEE Trans. Communications, vol. 34, pp. 2959-2965,
Dec. 1995.
(a) (b) (c) [10] N. Yamsang and S. Udomhunsakul,”Image Quality Scale (IQS) for
Figure 6. (a)Original image, (b), (c) compressed images compressed images quality measurement”, Proceedings of the
using BTC and AMBTC respectively
International Multiconference of Engineers and Computer Scientists,

VII. CONCLUSIONS vol. 1, pp. 789- 794, 2009.

In this paper, image compression using block [11] S. Voloshynovskiy, S. Pereira, A. Herrigel, N. Baumgartner, T. Pun, “A
truncation coding has been investigated. Two algorithms were Stochastic Approach to Content Adaptive Digital Image Watermarking”,
selected namely, the original block truncation coding (BTC) Proceedings of the Third International Workshop on Information Hiding,
and Absolute Moment block truncation coding (AMBTC). pp.211-236, 1999.
The two algorithms are based on dividing the image into non
[12] Z. Wang, A. C. Bovik, H. R. Sheikh, and E. P. Simoncelli, "Image
overlapping blocks and uses a two-level quantize. The two
techniques were applied to different grey level test image quality assessment: From error measurement to structural similarity"
each contains 512×512 pixels with 8 bits/pixel (256 grey IEEE Transactions on Image Processing, vol. 13, No. 1, January 2004.
levels). The reconstructed images have a bit rate of 1.25
bit/pixel. This corresponds to 85% compression. Objectives
measures were used to evaluate the image quality such as:
Peak Signal to Noise Ratio (PSNR), Weighted Peak Signal to Doaa Mohammed received the B.S. in
Noise Ratio (WPSNR), Bit Rate (BR) and Structural Electronics and Communications
Similarity Index (SSIM).The results have shown that the Engineering from Faculty of
ATBTC algorithm outperforms the BTC. It has been show Engineering, Mansoura University,
that the image compression using AMBTC provides better Egypt in 2004. She is now preparing for
image quality than image compression using BTC at the same M.S. degree in Electrical Engineering.
bit rate. Moreover, the AMBTC is quite faster compared to Her interests include signal processing,
BTC. image processing and information
security.
References
[1]   Rafael C. Gonzalez, Richard Eugene; “Digital image processing”,
Fatma El-Zahraa Abou-Chadi is
Edition 3, 2008, page 466
currently a professor and head of
[2] M. Ghanbari "Standard Codecs: Image Compression to Advanced
department of Electronics and
Video Coding" Institution Electrical Engineers , ISBN: 0852967101, Communications Engineering
2003 , CHM , 430 pages. Department, Faculty of Engineering,
[3] Delp, E. J., Saenz, M., and Salama, P., 2000, Block Truncation Coding Mansoura University, Egypt. Her
research interests focus on digital
(BTC), Handbook of Image and Video Processing, edited by
signal processing, image processing
Bovik A. C., Academic Press, pp. 176-181. and biomedical engineering.
[4] Franti P, Nevalainen O, Kaukoranta T. Compression of Digital Images
by Block Truncation Coding: A Survey, The Computer Journal, Vol. 37,
No. 4, 1994.
[5] C. C. Tsou, S. H. Wu, Y. C. Hu, "Fast Pixel Grouping Technique for
Block Truncation Coding," 2005 Workshop on Consumer Electronics
and Signal Processing (WCEsp 2005), Yunlin, Nov. 17-18, 2005.
[6] M.D.Lema, O.R.Mitchell, “Absolute Moment Block Truncation Coding
and its Application to Color Image”, IEEE Trans. Coomun., Vol.
COM-32, No. 10, pp. 1148-1157, Oct. 1984.
[7] Somasundaram, K.and I. Kaspar Raj. “Low Computational Image
Compression Scheme based on Absolute Moment Block Truncation
Coding“. May 2006. Vol. 13.

13