Colour Palette Compression via Vector Quantization for Colour Image Transmission

Colour Palette Compression via Vector Quantization for Colour Image Transmission

A. Somboonkaew, F. Cheevasuvit, k.Dehan, S.Mitatha and S.Wongkharn
Faculty of Engineering,
king Mongkut's Institute of Technology Ladkrabang
Bangkok 10520, Thailand

Abstract
Satellite colour image is obtained by combining of red, green and blue colour. For full colour dynamic range, each colour is encoded with 8 bits for 256 different shades. So , the real time transmission of colour image with 24 bits pr pixel is almost impossible for the public telephone line. However, all 16 million colour shades form 24 bits data are rarely appeared in each satellite image. Also the human perceptibility needs only a few different colour shades to distinguish the objects in image. To overcome the mensioned problem, this paper proposes a method of colour palette compression via vector qunatization for colour image transmission. The three colour shades from 24 bits of satellite colour image is trained for implementing a certain number of codes vector such as 256 codes. After vector quantization encoding process, each pixel of colour image will be encoded with 8 bits instead of 24 bits. Each colour palette of 256 codes will be represented a group of colour shades with the minimization of error constraint.

1. introduction
In general, the colur satellite image is performed by combining three colour which are red, green and blue. Each colour is encoded with 8 bits for 256 difference colour shades. So, each colour pixel is used 24 bits of data. This will cause a huge of memory for storing a colour image. It's almost impossible to send this colour image for remote monitoring the internet system.

Therefore, data compression technique is brought to defeat the mentioned problem. One if the welknown and powerful technique is vector quantization. This paper proposes the vector quntization technique for compressing the data. The 24 bits of each colour shades form image is used simultaneously for training and implementing a codebook of vector quantization. The proposed technique is different from the previews researches since each colour uses its codebook. From this proposed technique, the compressed colure image can be obtained with less colour distant when compared with the mean square error.

2. Data compression by vector quantization
A colour satellite images is composed at less three band images. Each image is assigned for red, green and blue colour for 256 colour shades. Therefore, a pixel of colour image needs 24 bits for colour palette. It consumes a huge of memory storage and also the transmission time.

A vector quantization is applied to the 24 bits of colour palette for colour palette compression . the 24 bits of colour palette from three colour are trained together for generating a certain number of code vectors such as 64, 128 or 256 . for 256 code vectors, the compression ration about 3 times will be obtained. It means each colour pixels will be4 represented by 256 different alpha numerics . if less code vectors is used the more compression ration will be obtained. In general, each colour shade needs one colour index for pointing the palette. So, the 24 bits of colour data need about 16 million index. By using vector quantization for compressing the colour palette, the number of bits will be reduced in the order of 8 bits for 256 code vectors. It needs only 256 index for pointing 256 different colour shades. The compression process will be described as following paragraph.

Data compression by vector quantizatin [1,2] is a lossy compression technique. This compression technique [3] this to define a mapping Q of K-dimensionsal Euclidean space Rk into a finite set Y containing N_c output or reproduction points, called code vectors, Thus

Q= R^k ® Y
For Y=(x^{^}_i ; I=1,2,…..N_c ). The set y is called the codebook with size Nc or Nc difference code vectors. The vector quantizaiton has two acting function. The first one is an encoder, which tires to generate and assignees the address of reproduction vector in the codebook for the input vector x. the second case is an decoder, which used other assigned address to generate the representation vector x.. for the encoder procedure, the criterion of least minimum distortion is used to generate the codebook. The distortion is measured by the square error distortion as shown in the following equation.

The block diagram of encoder is shown in figure 2, where the input vector x is entered to the vector quantizaiton encoder. The encoder tried to search the code vector form the codebook which gives the minimum distortion for representing the input vector. The output of the encoder is the address of searched vector. Therefore, the selected size of codebook is given directly the compression ratio.

Figure 1. Block diagram of encoder
In the receiving end, the reproduction vector in codebook will be extracted to represent the input vector, so the compression image can be performed from the reproduction vectors.

3. Experiments
The proposed method is applied to the three band images. The result are shown in figure 2. it is clearly that the proposed technique gives a higher colour quality comparing with the method of colour ration by 3:3:2 of red, green and blue colour. The table of mean square error confirms the results.

Table of mean square error from each band

Inage Band	Proposed method	Colour ratio
Red	7.4425	173.3916
Green	7.9714	173.77069
Blue	7.994	276.4466
Average	7.8029	207.8697

Figure 2. Colour palette compression via Vector Quantization

Figure 3. Error of proposed method of red green and blue band

Figure 4. Error of RGB type 3:3:2 of red green and blue band
4.Conclusion
For [MxN] pixels of colour image , the proposed method provides only nx[MxN] bits instead of 24x[MxN] bits of original colour image. n is the selected number of binary bit for 2n different code vectors. However, the proposed techniques needs 2nx24 bits for representing the palette of 2n different colour. Therefore, the total number of bits for this proposed method is nx[MxN]+2nx 24 bits.

Acknowledgement
The Authors would like to thank the National Research Council of Thailand providing the satellite images.

Reference:

N.M.Nasrabadi and R.A.King , " Image coding using vector quantization; A Recview , " IEEE Trans. Commun., Vol . COM-36, pp. 957-971, Aug. 1980
Y.Linde, A . Buzo , and R.M.Gray, " An algorithm for vector quanitzer design ," IEEE Trans. Commun., vol.COM-28, pp. 84-95, Jan 1980.
A.Gersho and R.M. Gray, " Vector Quantizaiton and Signal compression ", Kluwer Academic Publishers, Boston , London, 1991.