Abstract
The present work proposes a modified vector quantization algorithm to overcome the blocking artifacts problem of the conventional Vector Quantization (VQ) algorithm. Blocking artifacts affects visual appeal of the decompressed images. The Vector Quantization (VQ) algorithm is improvised where the blocking artifact does not appear in the decompressed image. The proposed algorithm is applied on luminance-chrominance color model where luminance channel is compressed using a novel approach. For the luminance channel, eight separate clusters are constructed using the k-means clustering algorithm then for each cluster, fuzzy intensification applied separately; next for each cluster training vectors are formed by taking sixteen consecutive elements from a cluster to form one vector, next sixteen elements for second vector and so on. For each group of these training vectors, vector quantization is applied to generate the code vectors. For chrominance channels the conventional VQ algorithm is applied. At the time of decompression the reverse process is followed. The modified VQ algorithm has been applied on standard UCID v.2 image database and standard images found in literature where blocking artifacts problem is effectively solved. Experimental result shows that the proposed algorithm successfully avoids the blocking artefacts and the quality of the decompressed image is improved in terms of PSNR and vSNR compared to the conventional VQ algorithm. This article focuses on retaining more original information of the image rather than restoration of the decompressed image where blocking artifacts exists.
Keywords
Introduction
Image compression algorithms reduce the amount of memory space required to represent a digital image while keeping the resolution and the visual quality of the reconstructed image as close as possible to the original image. It is a process which intends to yield a compact representation of an image and reduces the image storage/transmission requirements. Image compression techniques reduce the number of bits required to represent an image by taking advantage of the three basic data redundancies which are coding redundancy, inter-pixel redundancy and psycho visual redundancy. Coding redundancy is present when less optimal code words are used. Inter pixel redundancy results from correlations between the pixels of an image. Psycho visual redundancy is due to data that is ignored by the human visual system (i.e. visually non essential information). The image compression techniques are broadly classified into two categories depending on whether or not an exact replica of the original image could be reconstructed using the compressed image. These are: a) Lossless technique and b) Lossy technique. There are lots of works available in literature on both lossless and lossy image compression techniques [1–9].
Compression artifact is a particular class of data error that appears in the decompressed images as the consequence of quantization in lossy data compression. While compression algorithm cannot reproduce enough data in the compressed version to reproduce the originality then artifacts is introduced in the decompressed image resulting deterioration of image quality. Compression artifacts may be of different types namely blocking artifact, ringing artifact etc. The minimization of perceivable artifacts is a key goal in implementing a lossy compression algorithm. Artefacts appear in the decompressed images compressed using lossy compression algorithms like JPEG, Vector Quantization etc.
Vector quantization(VQ) algorithm is a lossy image compression technique where an image is divided into n × n image blocks. Hence, each block of the image forms a training vector which contains n × n values. Now clustering algorithm is applied on these entire training vectors to get the index matrix and code vectors. At the time of decompression, the code vector indicated by index matrix is placed as n × n sub-image in the image. VQ is a very effective compression algorithm with high compression ratio. But in the decompressed image, blocking artefacts appear as VQ does not take into consideration inter-block correlation. Blocking artefacts in the decompressed image becomes explicit and these seriously affect the quality of the decompressed image. In the literature, many attempts have been made [10–13] to reduce the VQ compression time and different algorithms for codebook generation of VQ are proposed to improve the quality of the decompressed image still VQ suffers from blocking artefacts. There are some algorithms to enhance the decompressed image where blocking artefacts appear as a post processing techniques i.e. Mei Yin Shen and C.C. Jay Kuo [14] gave review of post-processing techniques for compression artifact removal in 1998, George A. Triantafyllidis et al. [15] proposed another method compressed data in 2002, Wang and Porikli [16] proposed multiple dictionary learning for blocking artifacts reduction in 2012, In 2009, Basak Oztan et al. [17] proposed a method for removal of ringing and blocking artifacts from JPEG compressed document images. Recently, S.D. Thepade et al. [18] proposed a new clustering algorithm for Vector Quantization using Slant transform in 2013, Mahapatra and Jena [19] also proposed partitional k-means clustering based hybrid DCT-Vector Quantization for image compression in 2013. In 2016, Karri [20] proposed a method for fast vector quantization using a Bat algorithm which mainly focuses on faster computation. All these methods focus on better clustering process during compression or fast computation. Again, in 2014 Jonathan Quijas [21] proposed a post processing technique to remove blocking artifact from JPEG compressed and Recently in 2016 Zhangyang Wang et al. [22] proposed a method for fast restoration of JPEG compressed images which are mainly post processing technique to remove blocking artifact. But none of those work focuses on processing during compression so that blocking artefacts could be avoided in decompressed image.
But the present work, proposes fundamental modification of VQ algorithm which works on images of luminance-chrominance color model to overcome the blocking artifacts problem of compressed image using VQ. In this paper, luminance channel is compressed using the proposed algorithm which is new in the literature and chrominance channels are compressed using standard vector quantization algorithm. This methodology has been applied on various natural images collected from standard image database- i.e. UCID v.2 [23] database and on many standard images (i.e. –lena, pepper, mandrill etc. images). Experimental result shows that the proposed methodology successfully avoids the blocking artifact in 100% cases with higher PSNR. This article focuses on retaining more original information of the image rather than restoration of the decompressed image where blocking artifacts exists.
This paper is organized as follows: Section 2 explains the Vector Quantization algorithm and blocking artefacts in the decompressed image. In Section 3 proposed algorithm is discussed in details. Section 4 describes the experimental results and their analysis. Finally, Section 5 concludes and remarks about some of the aspects analyzed in this paper.
Vector Quantization algorithm
In the field of Image compression, Vector Quantization (VQ) technique is important approach and it is very simple to implement. The steps of the VQ algorithm are explained below.
So the code vector and the index array are stored as compressed image. In the decompression procedure, a sub image of p × p is formed using the code vector indicated by the index array. Thus combining all the sub-image the decompressed image is constructed.
At the time of codebook generation process one important objective is to minimize the distortion between original image and reconstructed image. Linde-Buzo-Gary (LBG) algorithm proposed by Linde et al. [8] in 1980 is widely used in VQ for code vector generation.
A training vector, x m = (xi,1, xi,2, xi,3, …… , xi,k) is a k dimensional matrix where m = 1, 2, 3, …… , M. Let N is the number of code vector in the codebook and a code vector c i ={ ci,1, ci,2, …… ci,k }; where i = 1, 2, 3 …… , N. Let T = (x1, x2, x3, …, x k ) be a training vector.
Let S
n
be the encoding region associated with the code vector c
n
. Let S = {S1, S2, S3, …… , S
N
} denotes the partition of the space if the source vector x
m
in the encoding region S
n
then approximation (Q (x
m
)) is c
n
given by Equation 1.
The average distortion is given by Equation 2.
Where . The design problem can be succinctly stated as follows: Given T, N, C & S such that Dave is minimized.
If C and S are a solution to the above minimization problem, then it must satisfy the following two criteria.
Nearest neighbor condition
This condition says that the encoding region S n should consists of all vectors that are closer to c n than any of the other code vectors.
Centroid Condition
This condition says that the code vector c n should be average of all those training vectors that are in encoding region S n . In implementation, one should ensure that at least one training vector belongs to each encoding region (so that the denominator in the above equation is never 0).
The LBG VQ design [8, 25] algorithm is an iterative algorithm which alternatively solves the above two optimality criteria. The algorithm requires an initial codebook C0 which is obtained by the splitting method. In this method, an initial code vector is set as the average of the entire training sequence. This code vector is then split into two. The iterative algorithm is run with these two vectors as the initial codebook. The final two code vectors are split into four and the process is repeated until the desired number of code vectors is obtained. The algorithm is summarized below. Given ɛ > 0 to be a small number. Let N = 1 and
Calculate
Splitting for i = 1, 2 … N set
Iteration
Let , Set iteration index i = 0 For m = 1, 2 … M find the minimum value of Overall i = 1, 2 … N. Let n* be the index which achieves the minimum.
For n = 1, 2 … N update the code vector
Set i = i + 1. Calculate
If go back to step I Set for n = 1, 2 … N set as final code vector. Repeat Steps III and VI until the desired number of code vectors are obtained.
Compressed image using standard Vector Quantization algorithm results to blocking artifacts in the decompressed image. The VQ scheme takes advantage of the local spatial correlation property of the images by dividing the image into blocks of n × n pixels, transforming each block from the spatial domain to vector of size n2. Since each vector pixels is treated as single entities and coded separately, correlation among spatially adjacent blocks is not taken into account in coding, which results in block boundaries being visible when the decoded image is reconstructed. For example, change in the border line between two blocks in the decompressed image is not smooth. Figure 1 (a and b) shows the original image and the decompressed image using VQ algorithm respectively.

Blocking artifact in VQ compression a) Original house image b) VQ decompressed image where blocking artifacts appears.
The main focus of the proposed color image compression algorithm is a modified Vector Quantization algorithm to overcome the blocking artifacts problem of conventional VQ. As the luminance chrominance color model carries the image information in luminance channel and contain the color information of the pixel in chrominance channels, so the proposed algorithm focuses on retaining more information of the luminance channel. That is why a different approach is applied here to compress the luminance channel and for chrominance channels conventional VQ algorithm is followed. Initially, image is converted into YCbCr model where Y channel is the luminance channel and Cb and Cr are chrominance channels.
Apply fuzzy intensification on each of the clusters, Y i ; i = 1, 2, … 8. The fuzzy intensification process is shown in Fig. 2.

Flowchart of fuzzy intensification process.
The intensification operation acts in a combination of concentration and dilation [26]. It increases the degree of membership of those elements in the set with original membership value greater than 0.5 and it decreases the degree of membership of those elements in the set with the original membership value less than 0.5. This has the effect of making the boundaries of the membership function steeper. Intensification is done using Equation 6.
Intensification increases the contrast between the elements of the set that have more than half- membership and those that have less than half-membership. It is applied in the compression process to remap luminance values concentrated near MAX and MIN values to minimize information loss during compression process. These fuzzy intensified luminance values are remapped in the range [MIN MAX] using Equation 7.
PSNR between the original and the decompressed image using the proposed algorithm applied on different color model
PSNR ratio between original and compressed images using different algorithms
Hence the compression algorithm gives run length code for index matrix, k1, k2, k3, … k8 number of code vectors and its respective index array of size n1, n2, n3, … n8 for 1st, 2nd, 3rd.. 8th group of training vectors respectively for luminance channel. For chrominance channels, code vectors and its respective index matrix are found using conventional VQ compression algorithm. All these values are stored as compressed image. The flowchart of the modified VQ algorithm is shown in Fig. 3.

Flowchart of the proposed compression algorithm.
The decompression process is just reverse process of compression. The steps for decompression is shown below-

Flowchart of the proposed decompression algorithm.

Fuzzy de-intensification process.
Initially, using the index matrix, eight clusters/groups of decompressed luminance values are formed. For each of the decompressed luminance clusters, suppose minimum decompressed value of cluster is MIN and maximum value is MAX, then luminance values are normalized in the range [0,1] using Equation 5. Now normalized luminance values are de-intensified [26] using Equation 8.
These de-intensified luminance values of each cluster again remapped in the range of [MIN MAX] using Equation 7. Thus all the clusters are formed. Using Index matrix and these remapped clusters, luminance channel is reconstructed. The luminance channel is combined with decompressed chrominance channels Cb, Cr to construct the final de-compressed image.
The proposed compression algorithm mainly focuses to overcome the blocking artifacts problem in the compressed images using VQ algorithm. This method successfully overcomes the blocking artefacts problem in the decompressed images. The proposed algorithm for image compression has been applied on several images collected from different standard image database i.e. UCID.V2 [23] of standard natural images.
The proposed algorithm is applied on luminance-chrominance (de-correlated) color model (image and color information is separated) instead of RGB model (where image and color information are carried by all channels). The proposed algorithm shows a significant improvement in terms of image quality. Figure 6(a-c) shows the original image, the decompressed image on RGB model and the decompressed image using proposed algorithm (initially RGB image converted YCbCr) respectively.

Result of decompressed images using the proposed algorithm in different color models (a) Decompressed image using the proposed algorithm applied on RGB image (b) Decompressed image using the proposed algorithm applied on YCbCr image.
The PSNR between the original image and the decompressed images of different color models are shown in Table 1. The PSNR ratio clearly shows that the decompressed image using the proposed algorithm retains more original image information on YCbCr (de-correlated) color model.
Figure 7(a-c) shows the original image, decompressed image using VQ algorithms, decompressed images using proposed algorithm respectively. The Fig. 7(c) clearly shows that the blocking artefacts are not present in the images compressed using proposed algorithm. For all the images, codebook size of luminance channel is taken 256 and in case of chrominance channels, for each chrominance channel codebook size is taken 128. But for standard vector quantization algorithm codebook size for each channel is taken 256.

Decompressed images a) Original image b) Decompressed image using VQ algorithm c) Decompressed image using proposed algorithm.(Difference between the decompressed images is more prominent in actual images, Here images are resized for space constraint).
Generally performance of an image compression algorithm is measured using two parameters- required memory space reduction and quality of the decompressed image. PSNR [18, 19] is commonly used to measure the quality of reconstruction using lossy compression codes (e.g., for image compression). The signal in this case is the original data, and the noise is the error introduced by compression. While comparing compression algorithms, a higher PSNR generally indicates that the reconstruction is of higher quality. Peak signal-to-noise ratio (PSNR) is computed between luminance channel of the original color image and decompressed image using the proposed algorithm. When comparing quality of the decompressed image, a higher PSNR generally indicates better the compression algorithm.
PSNR is easily defined by Mean Squared Error (MSE) using Equation 9.
Where Mean Squared Error (MSE) is defined using Equation 10.
Where I, I c represents the matrix data of original image and the decompressed image respectively. m, n represents number of rows of and number of columns respectively in the images. MAXf is the maximum signal value that exists in original image.
Table 2 shows the of PSNR between the original image and decompressed image using the standard VQ algorithm and proposed algorithm. For conventional VQ algorithm code vector size is considered as 256 for each of the Y, Cb, Cr channels whereas in the proposed algorithm code vector size is considered as 256, 128 and 128 for Y, Cb and Cr channels respectively.
It is evident in Table 2, that the PSNR between the original image and compressed image using VQ is considerably less than the PSNR between the original image and compressed image using the proposed algorithm. So the compressed images using the proposed algorithm retain more original information than the conventional VQ compressed image. PSNR ratio of chrominance channels in both of the algorithm is more or less same.
Also, visible signal-to-noise ratio (vSNR) [27, 28] is computed to assess the performance of the algorithms further. vSNR used to analyze how noise influence visibility in uniform areas of an image. vSNR is defined as the inverse of the standard deviation of the SCIELAB [28] representation of a uniform field; its units are 1/ΔE. The vSNR metric is used in simulations to predict how imaging system components affect noise visibility. High vSNR [28] signifies less noise. In this study, vSNR is calculated for the decompressed image using Vector Quantization algorithm and the proposed method. Table 3 shows the calculated vSNR values. The calculated vSNR shows that in 80% cases the proposed algorithm performs better than Vector Quantization algorithm.
vSNR ratio of the decompressed images using Vector Quantization and the proposed method
Memory space reduction percentage is calculated using Equation 11.
Where S = space required to store the uncompressed image, S c = space requirement to store the compressed image.
Table 4 shows the percentage of space requirement reduced by the standard vector quantization algorithm and the modified algorithm for the images shown in Fig. 7. The space requirement for compressed image using the proposed algorithm is slightly higher than VQ algorithm for the most of the images but the proposed algorithm successfully avoids all the blocking artefacts in the decompressed image. Also the PSNR between the original image and compressed image using proposed algorithm is considerably higher than that of VQ.
Space requirement reduction for the compressed images using VQ and proposed algorithm (*Size is in bytes)
Experimental result shows that the proposed algorithm successfully avoids the blocking artefacts and the quality of the decompressed image using proposed algorithm is far better than that of the VQ algorithm. But for some images the size of the decompressed image using the proposed algorithm is more than the compressed image using the VQ algorithm. Therefore the proposed algorithm retains more original information of the image compared to conventional VQ algorithm.
Present work proposes a modified vector quantization algorithm to overcome the blocking artifacts problem of the conventional Vector Quantization (VQ) algorithm. Blocking artifacts affects visual appeal of the decompressed images. The Vector Quantization (VQ) algorithm is improvised where the blocking artifact does not appear in the decompressed image. The proposed algorithm is applied on luminance-chrominance color model where luminance channel is compressed using a novel approach. For the luminance channel, eight separate clusters are constructed using the k-means clustering algorithm then for each cluster, fuzzy intensification applied separately; next for each cluster training vectors are formed by taking sixteen consecutive elements from a cluster to form one vector, next sixteen elements for second vector and so on. For each group of these training vectors, vector quantization is applied to generate the code vectors. For chrominance channels the conventional VQ algorithm is applied. At the time of decompression the reverse process is followed. The modified VQ algorithm has been applied on standard UCID v.2 image database and standard images found in literature where blocking artifacts problem is effectively solved. Experimental result shows that the proposed algorithm successfully avoids the blocking artefacts and the quality of the decompressed image is improved in terms of PSNR and vSNR compared to the conventional VQ algorithm.
Footnotes
Acknowledgments
Authors are thankful to the “Center for Microprocessor Application for Training Education and Research”, “Project on Storage Retrieval and Understanding of Video for Multimedia” at Computer Science & Engineering Department, Jadavpur University, for providing infrastructural facilities during progress of the work. Abul Hasnat and Dibyendu Barman are thankful to Government College of Engineering and Textile Technology, Berhampore, for kindly permitting them to carry on the researchwork.
