Wisdom Based Computing, Volume 1, Issue 1, April 2011

INTERNATIONAL JOURNAL OF WISDOM BASED COMPUTING, VOL. 1(1), 2011
50
WBMP Compression
R. Rajeswari, R. Rajesh
Abstract
Wireless Application Protocol Bitmap (WBMP) images are widely used in
Wireless Application Protocol devices. This paper presents an overview of various
lossless compression algorithms and discusses the compression of WBMP images
using these algorithms.
Index Terms
Image Compression, WBMP
I. INTROUCTION
The goal of digital image compression techniques is to reduce the space
necessary to encode, store or transmit digital images by changing the way those
images are represented. The image compression techniques are widely used in
teleconferencing [1], medical imaging [2], image archiving [3], remote sensing
[4], preservation of historical documents [5], etc. Image compression techniques
can be lossless or lossy. Lossless compression techniques like run-length coding
[6], Huffman coding [7], arithmetic coding [8], Limpel-Ziv-Welch (LZW) coding
[9] etc. are widely used in compressing medical and satellite images as they
retain all information from the original image. Lossy compression techniques like
Discrete Fourier Transform (DFT) [10], Discrete Cosine Transform (DCT) [11],
Discrete Wavelet Transform (DWT) [12] transform the image data to a different
domain and quantize the coefficients. These techniques give higher compression
ratios. They are used in compressing natural images where loss of image data is
not significant.
The above said compression algorithms are widely used in many applications
having medium and large size images. But considering the current scenario
of having small digital equipments there is a high necessity of compressing,
transmitting and displaying images in small sized windows. Wireless Application
Protocol Bitmap (WBMP) image file format is the one which is used most
popularly for wireless applications which contains only graphical information
which is used by a variety of handsets especially mobile phones [13]. This
paper deals with the compression of WBMP images using lossless compression
algorithms.
This paper is organized as follows. Section II gives a brief overview of various
lossless compression techniques. Section III discusses the compression of WBMP
images using these techniques. Section IV deals with conclusion.
II. COMPRESSION TECHNIQUES: A REVIEW
A two-state Markov model specified in [6] is the basis for run-length coding.
In run-length coding the length of 0's and 1's are coded instead of coding the
Dr. R. Rajesh and R. Rajeswari are with School of Computer Science and Engineering, Bharathiar
University

---

INTERNATIONAL JOURNAL OF WISDOM BASED COMPUTING, VOL. 1(1), 2011
51
color of each pixel. The color of a run can be determined either by specifying the
color of the first run or by assuming that the image starts with a white or black
run [14].
In Huffman coding [7], we order the probabilities of symbols and combine the
lowest probability symbols into a single symbol. This process is repeated until
we are left with two symbols. Then codes are assigned to symbols starting with 0
and 1 for the last two symbols. For the symbols which were combined to generate
one symbol, one is identified by appending 0 and the other by appending 1. This
is repeated until we have assigned codes to all the symbols.
In LZW coding [9], a dictionary is initialized with all the symbols of the source
alphabet. The encoder reads the input into a pattern p as long as the pattern is
in the dictionary. If reading a letter a gives a pattern p*a which is not in the
dictionary, the index of p is sent and the patter p*a is added to the dictionary.
Next pattern is started with the letter a.
The modified Huffman (MH) coding is a compression technique specified in
the Recommendation T.4 [15]. Separate tables containing code words for black
and white runs are used. The run-length r is expressed as 64 * m + t, where m
ranges from 1 to 27 and t ranges from 0 to 63. m is called the make-up code and
t is called the terminating code. Terminating code is used if the run-length is less
than 63. Both terminating code and make-up code are used for runs from 64 to
1728. The first run of every line is considered to be white. If first pixel is black
white run of length 0 is assumed [15, 17, 18, 20].
The modified READ (MR) coding scheme, is a two-dimensional scheme for
coding binary images [15]. In this technique instead of coding the run-lengths,
the location of changing pixel on the coding line is coded. The position of the
changing pixel is considered either with respect to previous line or with respect
to the preceding changing pixel on the same line [15, 17, 18, 19].
In the two-dimensional scheme encoding a line is done based on the previous
line, so error in one line can be propagated to all other lines. To restrict this
propagation of errors, T.4 recommends that after coding each line based on one-
dimensional coding remaining K-1 lines from a block of K lines must be coded
based on the previous line. This requirement reduces compression. To maximize
compression this requirement was removed in the recommendation T.6 [16]. The
modified version of MR is the modified modified READ (MMR) coding scheme
which does not have the one-dimensional coding scheme [16, 17, 18, 20].
III. ON THE COMPRESSION OF WBMP IMAGES
This section deals with the compression of WBMP images using lossless
compression algorithms like RLE, Huffman coding, LZW coding, MH coding,
MR coding and MMR coding. In this study we have used 12 WBMP images.
Table I shows the size in bytes for the above said images based on various
compression algorithms. Table II shows the corresponding compression ratios.
The plot of compression ratios of various compression algorithms for the WBMP
images are shown in Figure 1. This clearly indicates that MMR coding and MR
coding techniques perform much better than RLE, Huffman, LZW and MH coding
techniques.

---

INTERNATIONAL JOURNAL OF WISDOM BASED COMPUTING, VOL. 1(1), 2011
52
TABLE I
COMPRESSED SIZES OF THE IMAGES FOR RLE, HUFFMAN, LZW, MH, MR AND MMR
CODING SCHEMES
Original
RLE
Huffman
LZW
MH
MR
MMR
medcom1
406
272
440
254
329
218
183
elm26
361
288
378
224
349
169
114
cartpop38
361
182
400
220
229
122
95
cartwild58
316
310
322
232
344
230
192
cartwild6
225
202
226
152
230
150
118
cartobj42
496
272
536
273
322
234
206
birds8
271
234
276
209
282
186
151
eyes
126
58
126
83
99
60
47
finger
93
78
104
75
102
74
66
grump
139
240
168
169
299
160
117
cartobj3
271
280
288
232
331
230
199
birds25
181
326
204
202
356
261
234
TABLE II
COMPRESSION RATIOS FOR RLE, HUFFMAN, LZW, MH, MR AND MMR CODING SCHEMES
RLE
Huffman
LZW
MH
MR
MMR
medcom1
1.49
0.92
1.60
1.23
1.86
2.22
elm26
1.25
0.96
1.61
1.03
2.14
3.17
cartpop38
1.98
0.90
1.64
1.58
2.96
3.80
cartwild58
1.02
0.98
1.36
0.92
1.38
1.65
cartwild6
1.11
0.99
1.48
0.98
1.50
1.91
cartobj42
1.82
0.93
1.82
1.54
2.12
2.41
birds8
1.16
0.98
1.30
0.96
1.46
1.79
eyes
2.17
1.00
1.52
1.27
2.10
2.68
finger
1.19
0.89
1.24
0.91
1.26
1.41
grump
0.58
0.82
0.82
0.46
0.87
1.19
cartobj3
0.97
0.94
1.17
0.82
1.18
1.36
birds25
0.56
0.88
0.90
0.51
0.69
0.77
IV. CONCLUSION
This paper has discussed about various lossless compression techniques like
RLE, Huffman coding, LZW coding, MH coding, MR coding and MMR coding.
These compression algorithms have been applied to WBMP images and the results
show that MMR and MR coding performs much better than RLE, Huffman, LZW
and MH coding techniques.
REFERENCES
[1] Arya V., Mittal A., Joshi R. C., "An Efficient Coding Method for Teleconferencing and Medical Image
Sequences", Proceedings of Third International Conference on Intelligent Sensing and Information
2005, pp. 8-13, 14-17 December 2005.
[2] Wen-Jyi Hwang, Ching-Fung Chine, Kuo-Jung Li, "Scalable Medical Data Compression and Trans-
mission using Wavelet Transform for Telemedicine Applications", IEEE Transactions on Information
Technology in Biomedicine, Vol. 7, No. 1, pp. 54-63, March 2003.
[3] Benedettli A., Scarabottolo N., "Towards a Dedicated Compression Pipeline for Document Image
Archicing", Proceedings of Workshop on Document Image Analysis 1997, pp. 40-43, 20th January
1997.
[4] Yi Sun, Yi-Jin Yang, Phing Zhou, "Wavelet-Based Compression of Terrains", Proceedings of IEEE
International Geoscience and Remote Sensing Symposium 2003, Vol. 3, pp. 2030-2032, 21-25 July
2003.

---

INTERNATIONAL JOURNAL OF WISDOM BASED COMPUTING, VOL. 1(1), 2011
53
Fig. 1.
Compression Ratio
[5] Mello C. A B., "Synthesis of Images of Historical Documents for Web Visualization", Proceedings
of 10th International Multimedia Mdelling Conference 2004, pp. 220-226, January 2004.
[6] Capon J., "A Probabilistic Model for Run-Length Coding of Pictures", IRE Transactions on Information
Theory, pp. 157-163, 1959.
[7] Huffman D. A., "A Method for the Construction of Minimum Redundancy Codes", Proceedings of
IRE, Vol. 40, No. 10, pp. 1098-1101, 1952.
[8] Abramson N., "Information Theory and Coding", McGraw-Hill, New York, 1963.
[9] Welch T. A., "A Technique for High-Performance Data Compression", IEEE Computer, pp. 8-19, 1984.
[10] Freeman A. (translator), Fourier J., "The Analytical Theory of Heat", Cambridge University Press,
1878.
[11] Jayant N. S. and Noll P., "Digital Coding of Waveforms", Prentice Hall, 1984.
[12] Antionini M., Barlaud M., Mathieu P. and Daubechies I., "Image Coding using Wavelet Transform",
IEEE Trans. on Image Proc., Vol. 1, No. 2, pp. 205-220, April 1992.
[13] WAP Forum Ltd., "WAP WAE Specification - Version 1.1", May 1999.
[14] Gonzalez C., Woods E., "Digital Image Processing", Second Edition, Pearson Education Inc., 2002.
[15] International Telegraph and Telephone Consultative Committee (CCITT), "Standardization of Group 3
Facsimile Apparatus for Document Transmission", Recommendation T.4, 1980.
[16] International Telegraph and Telephone Consultative Committee (CCITT),, "Facsimile Coding Schemes
and Coding Control Functions for Group 4 Facsimile Apparatus", Recommendation T.6, 1984.
[17] Hunter R. and Robinson A. H., "International Digital Facsimile Coding Standards", Proceedings of
IEEE, Vol. 68, No. 7, pp. 854-867, July 1980.
[18] Ronald B. Arps and Thomas K. Truong, "Comparison of International Standards for Lossless Still
Image Compression", Proceedings of IEEE, Vol. 82, No. 6, pp. 889-899, June 1994.
[19] Yasuda Y., "Overview of Digital Facsimile Coding Techniques in Japan", Proceedings of IEEE, Vol.
68, pp. 830-845, July 1980.
[20] Khalid Sayood, "Introduction to Data Compression", Second Edition, Elsevier, 2000.

---