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.Rk ® 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
