HALFTONE IMAGE DATA COMPRESSION USING KFCG VECTOR QUANTIZATION ALGORITHM FOR VIDEO CONFERENCING

KEKRE H.B.¹*, SARODE T.K.²*, SANGE S.R.³*, RAGHWANI B.⁴, MERLIN VERGIS^5
1Department of Computer Engineering, SVKM’s NMIMS University Mumbai, India
²Department of Computer Engineering, SVKM’s NMIMS University Mumbai, India
³Department of Information Technology, SVKM’s NMIMS University Mumbai, India
⁴SVKM’s NMIMS University Mumbai, India
⁵SVKM’s NMIMS University Mumbai, India
* Corresponding Author : sanjay.sange@rdiffmail.com

Received : 13-09-2011     Accepted : 01-12-2011     Published : 05-12-2011
Volume : 2     Issue : 2       Pages : 42 - 49
J Signal Image Process 2.2 (2011):42-49

In this paper, we have used Jarvis halftone operator to convert continuous tone image into halftone. For further compression of image data KFCG technique is applied on halftone image. Half toning is the technique that converts continuous tone image into halftone image i.e. 8-bit plane image into 1-bit plane, mostly used in printing media. The objective is to prove that red plane in color image, contents most significant information and is less prone to error during the processing of image. Each pixel in color image in BMP file is represented by 24-bits. The red plane consists of the most significant byte, carrying maximum information of the image. The experimental results show the plane-wise average intensity value and measuring parameters like Mean Square Error (MSE) and Structure Similarity Index (SSIM) between individual planes of input and output images. Applications like video-conferencing where data compression and decompression process is to be carried out on real time basis. Finite time is required to achieve compression and decompression of image data. Some of the frames are required to be skipped for real time application. So, if the adequate image information is represented by red planes then green and blue plane of the image can be skipped to achieve time compensation. For experimental results different seven bitmap (.BMP) images are used.

Halftone, Code Vector, Codebook, Quantization, Kekre’s Fast Codebook Generation (KFCG), Index, Mean Square Error (MSE), Structure Similarity Index (SSIM)

In this paper, for compression of image data halftone and vector quantization techniques are used [1] . Half toning is the lossy compression technique that leads to some distortion. Codec using vector quantization technique is also lossy technique. Standard half toning operators like Floyd-Steinberg and Jarvis half toning operators are explained in [2] that preserves the artifacts in image. Few operators are presented and compared their results in terms of computation and space complexity with Floyd-Steinberg and Jarvis half toning operators [3] . Different Vector Quantization algorithms are presented in [4-9] . Time complexity of Euclidian distance for codebook generation is presented in [8] and [9] . In this paper Kekre’s Fast Code Book Generation (KFCG) algorithm is used because it drastically reduces time and computational complexity. For compression of image data Run Length Encoding with halftone [3] and Huffman Encoding with halftone are presented [10] . Separable Finite Impulse Response filter is used for reconstruction of image. Fast inverse half toning algorithm reduces the heavy use of floating-point and arithmetic operations as compared to other inverse algorithms presented in [11] . In this paper the analysis of pixel average intensity of each plane and Mean Square Error is calculated.

Halftone technique converts continuous tone image into binary image. Halftone technique prominently used in printing industry for making Advertising boards, Flex board and News papers. To achieve halftone image from continuous tone image neighborhood processing of halftone operator on continuous tone image is performed, then quantization process is applied on it to obtained binary image. As shown in block diagram color image is split into three basic red, green and blue color planes [1] . Therefore, the number of gray levels in each plane is represented by 2n levels, where ‘n’ indicates the number of bits required to represent pixel intensity value. After splitting 24-bit color image into individual plane, each pixel intensity in each plane is represented by 8-bit. In quantization process half of the gray levels in each plane is treated as logic zero (0) and rest of the gray levels treated as logic one (1). In this way, half toning method loses some data and converts 8-bit image into 1-bit image so as to obtain 8:1 compression ratio. Different half toning operators are presented in [3] and [15] . From performance point of view different half toning operators are compared with small operators [3] in terms of computational complexity and memory space. Jarvis half toning operator is shown in [Fig-1] where X indicates the central pixel. In the mask neighborhood process, it takes 12-tap, effectively 10-tap operation. Because in neighborhood process, multiplication of pixel intensity value with 1 is not considered as computation.

Kekre’s Fast Codebook Generation algorithm requires no multiplications resulting in less number of computations of Euclidean distance hence reduces the processing time [19] . As shown in [Fig-3] all the individual red, green and blue planes are required to combine to form 24-bit color halftone image and it can be treated as input to KFCG algorithm for further image data compression. Various approaches for Vector Quantization are given in [8] , [20] , [24] .
An image with size NxN is divided into 2x2 pixel non-overlapping blocks. In color image each pixel value is represented by 3 bytes. Therefore, for 2X2 block forms 12-byte input vector. Entire image is having ‘m’ number of blocks, hence we get V1, V2,….,Vm number of input vectors called as cluster-1 or training set. Centriod or code vector can be calculated by taking column wise average in cluster-1. In the first iteration cluster-1 is split into two clusters in which by comparing first element of training vector with first element of code vector C1 as shown in [Fig-2a] . The vector Xi is grouped into the cluster-1 if xi1< c11 otherwise vector Xi is grouped into cluster-2. In second iteration, the cluster-1 is split into two by comparing second element xi2 of vector Xi belonging to cluster-1 with that of the second element of the code vector. Cluster-2 is split into two by comparing the second element xi2 of vector Xi belonging to cluster-2 with that of the second element of the code vector [19] as shown in [Fig-2b] . In this way, cluster-1 can be further split to the desired codebook size. Total number of code vectors generated is 2n, where n is the number of bits used as a code vector index. Hence, codebook is in the encoded form and having code vector with its index. This encoded form gives the highest compression ratio. For transmission of encoded data, instead of transmitting code vector only index with n bit is transmitted. Image is decoded from index by taking corresponding code vector from the codebook.

Fast Inverse Half toning Algorithm is explained in detail [11] . Other image reconstruction algorithms are presented in [12] to [14] .
Following steps are performed to reconstruct image from halftone image as it is shown in block diagram in [Fig-3]
1) Input color image is split into primary three R-G-B colors as 8-bit individual plane.
2) Each plane is processed separately to convert individual plane into halftone image.
3) On each plane Kekre’s Fast Codebook Generation algorithm is applied for further image data compression [1] .
4) Only vector indices are used to decode the vector quantized image in decompression process.
5) Vector quantized image is nothing but the halftone image.
6) Vertical and horizontal edges are traced from halftone image.
7) Separable FIR Filter is used to convert halftone image to continuous image [11] .
8) All the three plane concatenated so as to obtain reconstructed color 24-bit continuous image.

The Image quality degrades in image processing operations like compression, storage, transmission and reconstruction. The traditional ways are used to measure image quality in terms of error sensitivity like Mean Square Error (MSE) and Peak Signal-to-noise Ratio (PSNR) has its own limitations [16] . SSIM is the quality measure on the degradation of structural information [16] . For calculation of Structural Similarity Index the measurement system is presented in [16] . Some quality measuring approaches are presented in [17] . Consider x is the original image having perfect quality and y is the processed degraded image. Luminance on both images is compared and it is estimated as mean intensity-



Luminance function l(x,y) is comparison function on µx and µy. Where µx and µy are sample means of x and y respectively.
Another contrast comparison c(x,y) is then the comparison of σx and σy. Where σx and σy are variance of x and y respectively.



The third function s(x,y) for normalization by its own standard deviation.
The overall measure of SSIM is the combination of three functions.



Where l(x,y) compares the luminance of image, c(x,y) compares the contrast of the image and s(x,y) measures the structural correlation of the images.
The complete expression is explained in [22] as-

[Fig-4a] is the original image on which Jarvis halftone operator is applied. [Fig-4b] is the halftone image and on this halftone image Kekre’s Fast Codebook vector quantization technique is applied. [Fig-4c] is the decoded vector quantized image and [Fig-4d] is the inverse image as a result of Fast Inverse Half toning algorithm. Different seven test images are considered in experimentation shown in [Fig-6] . Table-1 shows the average of pixel values between individual planes of input and output image. As shown in Table-1 the average pixel value of red plane is higher as compared to green and blue planes. Table-2 shows the image quality measuring parameter calculation of Mean Square Error (MSE) between red plane (r) of input image and the red plane of reconstructed image (r’) is comparatively less than green and blue plane in most of the images. Table-2 shows average MSE between corresponding red planes is lowest to that of green and blue plane. In the same way MSE is measured for green and blue plane. Table-3 shows the image quality measuring parameter SSIM and MSE between input image and output image. Table-3 shows the in most of the cases SSIM value approaches to one, it means that structure point of view both input and output images are almost same. For identical input and output image the value of SSIM is one. [Fig-5a] is the graphical presentation of average of pixel values between individual planes of input and output image. [Fig-5b] shows the graphical presentation of MSE. [Fig-5c] and [Fig-5d] represents SSIM and MSE between input and output image conclude that both the parameters are inverse to each other. [Fig-5a] shows red plane has maximum average pixel value as compared to green and blue plane as it poses most significant information as compared to green and blue. [Fig-5b] shows red plane has minimum error as compared to green and blue plane. All test images used in experiments are shown in [Fig-6] .

In general, in the natural images, most significant information is represented by red plane. If the image itself is overall greenish or bluish in shade then information is represented by respective planes. Color image pixel is represented by 24-bits. First byte of color image is red plane that any way it represents most significant information. Experimental results show that red plane average value is greater than green and blue plane also Mean Square Error is less comparatively. Future scope in vector quantization KFCG technique is that the block size can vary from 2x2 to 3x3, 4x4 and so on as well as the codebook size to 512, 1024 and so on. As well as different half toning operators can be used result comparison. The same technique can be used for image compensation in real time video processing just by processing red plane of the color image that contents prominent image information.

[1] Kekre H.B., Tanuja K. Sarode, Sanjay R. Sange, Shachi Natu, and Prachi Natu (2011) ICTSM 2011, CCIS 145, pp. 34–42 .  
» CrossRef   » Google Scholar   » PubMed   » DOAJ   » CAS   » Scopus  

[2] Floyd R. W. and Steinberg L. (1976) Proc. SID, vol. 17/2, pp. 75—77.  
» CrossRef   » Google Scholar   » PubMed   » DOAJ   » CAS   » Scopus  

[3] Sanjay R. Sange (2010) 1st International Conference Thinkquest 2010. Published in Springer Explorer and Springer CS Digital Library, pg-224—230.  
» CrossRef   » Google Scholar   » PubMed   » DOAJ   » CAS   » Scopus  

[4] Kekre H.B., Tanuja K. Sarode (2008) Proc. of Int. Conf. CETAETS, Saurashtra University, Gujarat (India), 13–14.  
» CrossRef   » Google Scholar   » PubMed   » DOAJ   » CAS   » Scopus  

[5] Gray R. M. (1984) IEEE ASSP Magazine, pp. 4--29.  
» CrossRef   » Google Scholar   » PubMed   » DOAJ   » CAS   » Scopus  

[6] Momotaz Begum et.al, (2003) WSCG 2003.  
» CrossRef   » Google Scholar   » PubMed   » DOAJ   » CAS   » Scopus  

[7] Vasuki A., Vanathi P.T. (2009) ICGST International Journal on Graphics, Vision and Image Processing (GVIP), Special Issue on Image Compression, Vol. 7 pp. 73—81.  
» CrossRef   » Google Scholar   » PubMed   » DOAJ   » CAS   » Scopus  

[8] Noha A. Hikal and Roumen Kountchev (2009) ICGST International Journal on Graphics, Vision and Image Processing (GVIP), Special Issue on Image Compression, Vol.7, pp.32—42  
» CrossRef   » Google Scholar   » PubMed   » DOAJ   » CAS   » Scopus  

[9] Kekre H.B., Tanuja K. Sarode(2008) International Journal of Engg. & Tech., Vol.1, No.1, pp. 67—77.  
» CrossRef   » Google Scholar   » PubMed   » DOAJ   » CAS   » Scopus  

[10] Kekre H.B., Sanjay R. Sange, Gauri S. Sawant, and Ankit A. Lahoty(2011) ICTSM 2011, CCIS 145, pp. 221–226, 2011.  
» CrossRef   » Google Scholar   » PubMed   » DOAJ   » CAS   » Scopus  

[11] Kekre H.B., Sanjay R.Sange (2009) IEEE, DOI 10.1109/ARTCom.2009.36, pg .650—655,Oct.(2009)  
» CrossRef   » Google Scholar   » PubMed   » DOAJ   » CAS   » Scopus  

[12] Wong P. (1995) IEEE Trans. Image Processing, vol.4, pp. 486-498.  
» CrossRef   » Google Scholar   » PubMed   » DOAJ   » CAS   » Scopus  

[13] Hein S. and Zakhor A. (1995) IEEE Trans. Images Processing, vol.4, pp.208—216.  
» CrossRef   » Google Scholar   » PubMed   » DOAJ   » CAS   » Scopus  

[14] Thomas D. Kite, Brian L. Evans and Alan C. Bovik (2000) IEEE Transaction on Image Processing, vol.9.No.5.  
» CrossRef   » Google Scholar   » PubMed   » DOAJ   » CAS   » Scopus  

[15] Sanjay Sange (2009) Journal of science, Engineering & Technology Management ISSN: 0975-525X Techno-Path Vol.1 No.2, pg. no.7—17.  
» CrossRef   » Google Scholar   » PubMed   » DOAJ   » CAS   » Scopus  

[16] Zhou Wang, Alan Conarad Bovik, Hamid Rahim Sheikh (2004) IEEE Transactions on Image Processing, Vol.13, No. 4.  
» CrossRef   » Google Scholar   » PubMed   » DOAJ   » CAS   » Scopus  

[17] Wang Z. (2001) Ph.D dissertation, Dept. Elect. Computer Engg., Univ. Texas at Austin, Austin, TX, Dec. 2001  
» CrossRef   » Google Scholar   » PubMed   » DOAJ   » CAS   » Scopus  

[18] Zhou Wang, Bovik A.C. (1984) IEEE Signal Processing Letters, vol.9, pp. 81-84, Mar. 2002. April 1984, pp. 4—29  
» CrossRef   » Google Scholar   » PubMed   » DOAJ   » CAS   » Scopus  

[19] Kekre H.B., Tanuja K. Sarode, Sanjay R. Sange (2011) ICTSM 2011, CCIS 145, pp. 34–42.  
» CrossRef   » Google Scholar   » PubMed   » DOAJ   » CAS   » Scopus  

[20] Kekre H.B., Kamal Shah, Tanuja K. Sarode, Sudeep D. Thepade (2009) International Journal of Information Retrieval, Vol. 2, Suppl. Issue 1, 2009, pp. 64-71  
» CrossRef   » Google Scholar   » PubMed   » DOAJ   » CAS   » Scopus  

[21] Momotaz Begum, et.al.(2003) WSCG 2003, February 3-7.  
» CrossRef   » Google Scholar   » PubMed   » DOAJ   » CAS   » Scopus  

[22] Vasuki A., Vanathi P.T. (2009) Vision and Image Processing (GVIP) , Special Issue on Image Compression, Vol. 7 pp. 73—81.  
» CrossRef   » Google Scholar   » PubMed   » DOAJ   » CAS   » Scopus  

[23] Kekre H.B., Tanuja K. Sarode(2009) Int. Journal of Computer Sci. and Information Technology, Vol. 1, No. 1, pp.: 7—12.  
» CrossRef   » Google Scholar   » PubMed   » DOAJ   » CAS   » Scopus  

[24] Kekre H.B., Tanuja K. Sarode (2008) First International Conference on Emerging Trends in Engineering and Technlogy, at G. H. Raisoni College of Engineering, Nagpur on 16-18.  
» CrossRef   » Google Scholar   » PubMed   » DOAJ   » CAS   » Scopus  

	Fig. 1- Jarvis Halftone operator
	Fig. 2a- Iteration1, Cluster 2
	Fig. 2b- Iteration 2, Cluster 4
	Fig. 3- Block diagram
	Fig. 4a- Original Image: Rohit
	Fig. 4b- Halftone Image
	Fig. 4c- Decoded Vector Quantization Image
	Fig. 4d- Inverse mage
	Fig. 5a- Average pixel value in each plane of input and output image. X-axis represents different images and Y-axis represents Average pixel value. Letters ‘I’ and ‘O’ represents input and output image respectively
	Fig. 5b- MSE between corresponding planes of image
	Fig. 5c- SSIM between input and output image
	Fig. 5d- MSE between input and output image
	Fig. 6- Test-Images
	Table 1- Pixel average in each plane of input and output image The average of pixel average value for red plane of both input and output image is highest.
	Table 2- Mean Square Error between corresponding planes of input and output image The red plane of image LataMangeshkar shows highest SSIM and lowest plane MSE as well as overall MSE.
	Table 3- Structure Similarity and Mean Square between input and output image Image LataMangeshkar has highest SSIM and lowest MSE.