Data Compression using Vector Quantization and Huffman Coding for Satellite Imagery

Data Compression using Vector Quantization and Huffman Coding for Satellite Imagery

F. Chevasuvit, K. Dejhan, S. Mitatha and S. Wongkharn
Faculty of Engineering, King Mongkut's Institute of Technology
Ladkrabang, Bangkok 10520, Thailand

Abstract
The transmission of satellite image data from an organization to another through public communication network is used for change detection task such as a detection of illegal deforestation. It is necessary to transmit frequently an enormous amount of data. This will cause a high cost and need a huge transmission bandwidth. This paper presents a satellite image data compression technique via vector quantization and Huffman coding before transmission. The proposed technique will give a high compression rate the cost and transmission bandwidth will be reduced.

(1) Introduction
An important problem in satellite imagery data communication system of an organization is transmission an enormous amount of data. Although there are many techniques in data compression [1, 2] to solve this problem it is difficult for a small organization to perform. At present, a microcomputer trends to be decreased in price because of the higher micro-electronics technology. So a small organization possibly provides a microcomputer to use itself. An image compression using vector quantization is an efficiency technique which results a high compression rate. It can easily perform on a microcomputer. However, this technique will give some distortions. So it is proposed for change detection task, which does not need high quality in detail. A Huffman coding will also be applied to this vector quantized imagery to increase compression rate with preserved distortion. The advantage in this high compression rate reduces expenditure of a small organization.

2) Image compression using vector quantization
Image compression using vector quantization (VQ) [3] is a lossy compression technique. It is defined as mapping Q of K-dimensional Euclidean space R k into a finite subset Y of Rk Thus

Q.R^k ® Y
where y=(x_i; i=1,2,...,N) is the set of reproduction vectors and N is the number of vectors in Y.

A vector quantizer is composed of two parts, encoder and decoder. An encoder will compare each input vector with every codevector in the codebook and generate index which represent the minimum distortion codevector from the input vector. A decoder takes the indexs to locate the codevector in codebook and generate the output vectors.

Figure 1: Block diagram of VQ
A codebook is the set of finite codevector for representing the input vector. The popular technique in codebook design is the Linde-Buzo-Gray (LBG) algorithm [4]. The whole image a partitioned into subblocks and all subblocks are used training this codebook.

3) Huffman coding
A Huffman coding [1,2] is an error free (lossless) compression technique. The principle method of this technique is to encode the more probility data by the less bit code. It can be summarized as following algorithm.

Find the probability of each data and sort them.
Generate new node by combination the two smallest probability together then sort the probability of new node with the remainder probabilities.
Define 1 for a brach of new node and 0 for another.
Repeat (2) and (3) until the final probability is 1.0

An example of Huffman coding can be shown as follows:

Figure 2: An example of Huffman coding
4) Experiment result
The two days, 246 x 256 pixels, Landsat MOS-I MESSR imageries were used for this experiment.The block diagram of this experiment is shown in fig. 3. The 256 codevectors in the codebook were generated by using LBG algorithm. The training sequence was the sequence of 4 x 4 subblocks of the first day imagery (Fig.4). A vector quantization and Huffman coding were applied to the first day imagery. The result of decoded imagery is shown in Fig. 5. The the same processing and codebook were applied to the second day imagery (Fig.6). The result of decoded imagery is shown in Fig. 7.

Figure 3: Block diagram of the experiment

Figure 4: Landsat MOS-I MESSR imagery on the first day (8 bpp)

Figure 5: Decoded imagery (MSE=89.43, Rate=0.5 bpp)

Figure 6: Landsat MOS-I MESSR imagery on the second day (8 bpp)
5) Conclusion
The compressed image using vector quntization and Huffman coding in Fig. 5 has mean square error (MSE)= 89.43 with rate = 0.5 bits per pixels (bpp). Another one in Fig. 7 has MSE = 130.66 wiyth rate= 0.5 bpp. These images can be detected the change of cloud in two days. This is an example of change detection task. Because of the distortion of this technique, the detection should be used with big regions of an imagery such as forest, big river, cloud etc. The height compression rate of this technique is a benefit. Hence, the small organization can easily and economically perform this task by only using a microcomputer.

Figure 7: Decoded imagery (MSE=130.66, Rate=0.5 bpp)
Reference

R.C. Gonzales and R.E. Woods, "Digital Image Processing, Addison-Wesley Publsishing Company, Inc., 1992.
M. Rabbani and P. W. Jones, "Digital Image Compression Techniques, "SPIE Optical Engineering Press, 1991.
N.M. Nasrabadi and R.A. King. "Image coding using vvector quantization: A Review, "IEEE Trans. Common., vol. COM-36, pp. 957-971, Aug 1980.
Y. Linde, A. Buzo, and R.M. Gray, "An algorithm for vector quantizer design," IEEE Trans. Commun., vol COM-28 pp. 84-95, Jan 1980.