Modified vector quantization algorithm to overcome the blocking artefact problem of vector quantization algorithm

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

Lossy image compression blocking artifacts Vector Quantization LBG luminance Kmeans clustering fuzzy intensification PSNR vSNR

1 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.

2 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.

Step 1. VQ divides an image in many p × p blocks which form one training vector X of size k where k = p × p. Thus m numbers of training vectors are formed for the entire image which is the training vector set.

Step 2. Generate a codebook containing N number of codeword where each codeword vector is of size k using a standard codebook generation algorithm. Let the code vectors CB = {C₁, C₂, C₃, … C_N} in R^k; where R^k is the k-dimension Euclidean space. This generated codebook is the representative of all the training vectors. So each training vector is mapped to one of the code vectors. Thus there is an index array indicating specific training vector mapping to a specific code vector.

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 = (x_i,1, x_i,2, x_i,3, …… , x_i,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 ={ c_i,1, c_i,2, …… c_i,k }; where i = 1, 2, 3 …… , N. Let T = (x₁, x₂, x₃, …, x_k) be a training vector.

Let S_n be the encoding region associated with the code vector c_n. Let S = {S₁, S₂, S₃, …… , 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. $(Q (x_{m})) = c_{n} if x_{m} \in S_{n}$ (1)

The average distortion is given by Equation 2. $D_{avg} = \frac{1}{M_{k}} \sum_{m = 1}^{m} {∥ x_{m} - Q (x_{m}) ∥}^{2}$ (2)

Where ${∥ e ∥}^{2} = e_{1}^{2} + e_{2}^{2} + e_{3}^{2} + \dots \dots + e_{k}^{2}$ . The design problem can be succinctly stated as follows: Given T, N, C & S such that D_ave 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

$S_{n} = {{x : ‖ x - c_{n} ‖}^{2} \leq {‖ x - c_{n^{'}} ‖}^{2}; \forall n^{'} = 1, 2, \dots \dots, N}$ (3)

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 $c_{n} = \frac{\sum_{x_{m} \in S_{n}} x_{m}}{\sum_{x_{m} \in S_{n}} 1}; n = 1, 2, \dots N$ (4)

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).

LBG Design algorithm

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 C⁰ 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 $c_{1}^{*} = \frac{1}{M} \sum_{m = 1}^{M} x_{m}$

Calculate $D_{ave}^{*} = \frac{1}{Mk} \sum_{m = 1}^{M} {∥ x_{m} - c_{1}^{*} ∥}^{2}$

Splitting for i = 1, 2 … N set $\begin{matrix} c_{i}^{(0)} & = & (1 + ɛ {) c}_{i}^{*} \\ c_{N + i}^{(0)} & = & (1 - ɛ) c_{i}^{*} \end{matrix}$ Set N = 2 * N.

Iteration

Let $D_{ave}^{*} = D_{ave}^{0}$ , Set iteration index i = 0

For m = 1, 2 … M find the minimum value of ${∥ x_{m} - c_{i}^{n} ∥}^{2}$ Overall i = 1, 2 … N. Let n^* be the index which achieves the minimum. $Set Q (x_{m}) = c_{n^{*}}^{(i)}$

For n = 1, 2 … N update the code vector $c_{n}^{(i + 1)} = \frac{\sum_{Q (x_{m}) = c_{n}^{(i)} x_{m}}}{\sum_{Q (x_{m}) = c_{n}^{(i)} 1}}$

Set i = i + 1.

Calculate $D_{ave}^{(i)} = \frac{1}{Mk} \sum_{m = 1}^{M} {∥ x_{m} - Q (x_{m}) ∥}^{2}$

If $(D_{ave}^{(i - 1)} - D_{ave}^{i}) / - D_{ave}^{(i - 1)} > \in$ go back to step I

Set $D_{ave}^{*} = D_{ave}^{(i)}$ for n = 1, 2 … N set $c_{n}^{*} = c_{n}^{(i)}$ 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 n². 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.

Fig.1

Blocking artifact in VQ compression a) Original house image b) VQ decompressed image where blocking artifacts appears.

3 Proposed algorithm

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.

Step 1. Apply k-means clustering algorithm on all the luminance values to produce one index matrix and eight clusters of luminance values Y₁, Y₂, Y₃, Y₄, Y₅, Y₆, Y₇, Y₈. It is observed from experimental result that dividing the Y channel into eight clusters gives the optimized result for the decompressed image in terms of space requirement and PSNR.

Step 2. Then luminance values are normalized in the range [0, 1]. Suppose a cluster has minimum luminance value, MIN and maximum value, MAX, then the normalized value is calculated using Equation 5. $y = \frac{x - MIN}{MAX - MIN}$ (5)

Apply fuzzy intensification on each of the clusters, Y_i ; i = 1, 2, … 8. The fuzzy intensification process is shown in Fig. 2.

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.

$\begin{matrix} α & = & {2 μ_{α}^{2} (y) for 0 \leq μ_{α} (y) \leq 0.5; \\ = & 1 - 2 {[1 - μ_{α} (y)]}^{2} for 0.5 \leq μ_{α} (y) \leq 1 \end{matrix}$ (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. $y^{'} = α * (MAX - MIN) + MIN$ (7)

Step 3. Divide the index matrix into 8 × 8 matrices. For each 8 × 8 index sub-matrix, traverse it in zigzag pattern and form an array of 64 elements. Apply run length compression on this array and form RLE IDXs. The 8 × 8 sub matrix produces optimized space requirement for run-length compression in this work.

Step 5. For each luminance cluster, training vectors are formed by taking first consecutive sixteen elements, next vector is formed by taking next sixteen element and so on. Thus the training vector set is formed for each luminance cluster. This process gives n₁, n₂, n₃, n₄, n₅, n₆, n₇, n₈ number of training vectors for 1st, 2nd, 3rd.. and 8th group of luminance values respectively.

Step 6. Apply LBG clustering algorithm for each group of training vectors and generate the code vectors. It produces code vectors and index array as output. Suppose this process gives k₁, k₂, k₃, k₄, k₅, k₆, k₇, k₈ (where k₁ + k₂ + k₃ + k₄ + k₅ + k₆ + k₇ + k₈ ≤ 256) number of code vectors for 1st, 2nd, 3rd.. and 8th group of training vectors. Store these eight index array and code vectors.

Step 7. For Cb and Cr channels, apply conventional VQ compression algorithm where number of clusters are 128 instead of 256. It is observed in the experimental result shown in Table 2 that taking 128 clusters for each of the Cb and Cr channels instead of 256 does not affect the image quality.

Table 1

PSNR between the original and the decompressed image using the proposed algorithm applied on different color model

Image Name	Image	Color Model	PSNR
lena_color_256.tiff		RGB	31.4200	32.4000	30.0900
		YCbCr	34.9800	38.1800	38.2900
4.2.07.tif		RGB	28.9300	31.3300	28.3700
		YCbCr	30.8300	30.4400	31.0000

Table 2

PSNR ratio between original and compressed images using different algorithms

Image Name	Image	PSNR using VQ			PSNR using proposed algorithm
		Y	Cb	Cr	Y	Cb	Cr
4.1.01.tiff		33.5000	38.4300	36.9800	35.6200	38.5000	36.9500
4.1.04.tiff		35.2500	37.6500	35.8300	36.4600	37.6000	35.7600
4.1.05.tiff		34.4400	37.0800	35.5300	37.4500	37.1100	35.5000
4.1.06.tiff		28.6900	36.8400	33.5400	32.9300	36.8100	33.4900
4.1.08.tiff		35.3700	38.0300	37.1300	37.7300	37.9300	37.0700
4.2.01.tiff		37.1600	38.8800	36.4400	37.9100	38.8100	36.3900
4.2.02.tiff		34.1100	34.9000	36.7400	36.4900	34.8200	36.7600
4.2.06.tiff		29.6800	34.3800	32.4400	33.2800	34.3200	32.3900
4.2.07.tiff		32.7000	35.2000	34.7200	35.1400	35.2000	34.6100
house.tiff		30.2200	36.4200	33.4700	34.7100	36.3600	33.4100
lena_color_256.tif		31.3100	38.2300	38.2700	35.1300	38.1800	38.2900
mandril_color.tif		25.0500	30.4300	31.0400	30.8900	30.4400	31.0000
ucid00006.tif		25.0200	36.8700	38.3600	30.8100	36.8900	36.3500
ucid00069.tif		29.0600	37.0900	40.9900	33.7700	37.1300	40.9500
ucid00075.tif		26.4400	40.3100	38.7100	31.9400	40.2800	38.6800
ucid00100.tif		26.2800	37.0500	34.7100	31.8400	37.0200	34.7000

Hence the compression algorithm gives run length code for index matrix, k₁, k₂, k₃, … k₈ number of code vectors and its respective index array of size n₁, n₂, n₃, … n₈ 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.

Fig.3

Flowchart of the proposed compression algorithm.

The decompression process is just reverse process of compression. The steps for decompression is shown below-

Step 1. Cb and Cr channel are retrieved using the code vectors and index matrix of respectivechannel.

Step 2. For each RLE IDXs, decode the run length code and form the array of 64 elements. Order these values 8 × 8 sub index matrics and place into proper postion in the index matrix. Thus index matric is reconstructed.

Step 3. Using Y1 index and Y1 code vectors Y1 array is contructed. Y2, Y3,.. Y8 arrays are constructed in same way.

Step 4. Using index matric and Yi matrix (Y1, Y2, Y3, ... Y8), the luminance matrix is reconstructed. The luminance channel and Cb, Cr channel reconstruction process shown in Fig. 4.

Fig.4

Flowchart of the proposed decompression algorithm.

Step 5. Finally decompressed luminance values are again separated into eight clusters using the index matrix and each cluster are de-intensified separately. De-intensification process is again reverse process of fuzzy intensification. Flowchart of de-intensification process of retrieved luminance channel is shown in Fig. 5.

Fig.5

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.

$\begin{matrix} f (y_{dd}^{'}) & = & \sqrt{\frac{f (y^{'})}{2}} iff (y^{'}) \leq 0.5 \\ = & \sqrt{\frac{(1 - f (y^{'}))}{2}} if 0.5 < f (y^{'}) \leq 1 \end{matrix}$ (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.

4 Experimental result and analysis

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.

Fig.6

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.

Fig.7

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. $PSNR = 20 {log}_{10} (\frac{{MAX}_{f}}{\sqrt{MSE}})$ (9)

Where Mean Squared Error (MSE) is defined using Equation 10. $MSE = \frac{1}{mn} \sum_{1}^{m} {\sum_{1}^{n} ∥ I (i, j) - I_{c} (i, j) ∥}^{2}$ (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. MAX_f 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.

Table 3

vSNR ratio of the decompressed images using Vector Quantization and the proposed method

Image Name	Image	vSNR using VQ			vSNR using proposed algorithm
		X	Y	Z	X	Y	Z
4.1.01.tiff		2.3978	3.2151	0.8212	2.0778	2.6685	0.8277
4.1.04.tiff		2.1429	3.9279	1.0228	1.2296	1.7332	0.6878
4.1.05.tiff		4.9187	5.0563	1.7408	6.0391	5.3427	1.6722
4.1.06.tiff		1.8999	5.5364	1.1979	2.2332	7.4138	1.7141
4.1.08.tiff		2.7923	4.2070	1.0418	3.1514	5.1293	1.0470
4.2.01.tiff		2.9467	3.7806	1.1832	2.6689	3.3268	1.1742
4.2.02.tiff		2.5869	3.0198	0.6677	2.4682	4.1119	0.8673
4.2.06.tiff		2.6751	3.2788	1.2774	3.6702	4.9395	1.3636
4.2.07.tiff		4.1702	6.1328	1.8285	4.5899	6.3559	2.0148
house.tiff		2.6015	3.3843	0.7943	4.2526	5.9625	1.1347
lena_color_256.tif		2.8693	4.1677	1.1375	4.2515	4.1245	1.6113
mandril_color.tif		3.8383	3.7413	0.8675	3.3036	6.2745	1.0802
ucid00006.tif		1.1558	1.6746	0.4970	1.7089	2.4674	0.6972
ucid00069.tif		3.3160	3.3774	0.9137	4.0176	4.0020	1.2321
ucid00075.tif		1.3655	1.9760	0.6285	2.0453	2.7658	0.9628
ucid00100.tif		1.0325	1.6241	0.5707	1.7790	2.8976	0.8036

Memory space reduction percentage is calculated using Equation 11. $M_{R} = \frac{S - S_{c}}{S} \times 100$ (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.

Table 4

Space requirement reduction for the compressed images using VQ and proposed algorithm (*Size is in bytes)

Image Name	Image	Space required	Space required	Space reduction %	Space required for	Space reduction %
		for uncompressed	for VQ compressed	using VQ	compressed image	using proposed
		image*	image		using proposed algo.*	algo.
4.1.01.tiff		196608	14783	92.4809	22464	88.5742
4.1.04.tiff		196608	14644	92.5516	20439	89.6041
4.1.05.tiff		196608	13020	93.3776	18234	90.7257
4.1.06.tiff		196608	13221	93.2754	22248	88.6840
4.1.08.tiff		196608	11580	94.1101	16743	91.4840
4.2.01.tiff		786432	42213	96.6323	74839	90.4837
4.2.02.tiff		786432	45905	94.1628	91646	88.3466
4.2.06.tiff		786432	47130	94.0071	90765	88.4586
4.2.07.tiff		786432	45040	94.2728	83502	89.3821
house.tiff		786432	37566	95.2232	82481	89.5119
lena_color_256.tif		196608	14951	92.3955	21176	89.2293
mandril_color.tif		786432	50108	93.6284	105712	86.5580
ucid00006.tif		589824	33955	94.2431	71174	87.9330
ucid00069.tif		589824	33483	94.3249	69163	88.2739
ucid00075.tif		589824	33483	94.3232	69612	88.1963
ucid00100.tif		589824	36307	93.8444	73193	87.5907

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.

5 Conclusion

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.

References

Gonzalez

R.C.

, Woods

R.E.

and Eddins

S.L.

, Digital Image processing using MATLB, Mc-Graw Hill, 2011.

Yang

and Bourbakis

, An Overview of Lossless Digital Image Compression Techniques, 48th IEEE Midwest Symposium on Circuits & Systems, University of Cincinnati, Covington, KY, USA, 2005.

Klima

and Fliegel

, Image Compression Techniques in the field of security Technology: Examples and Discussion, 38th Annual International Carnahan Conference Security Technology, Alubuquereque, New Mexico, 2004, pp. 278–284.

Avcibas

, Memon

, Sankur

and Sayood

, A progressive lossless/near lossless image compression algorithm, IEEE Signal Processing Letters9(10) (2002), 312–314.

C.K.

and Yuen

, A high performance image compression technique for multimedia applications, IEEE Transactions on Consumer Electronics42(2) (1996), 239–243.

Kil

D.H.

and Shin

F.B.

, Reduced Dimension Image Compression And its Applications, Proceedings of International Conference Image Processing, 3, 1995, pp. 500–503.

Halder

, Bhattacharjee

, Nasipuri

and Basu

D.K.

, A low space bit plane slicing based image storage method using extended JPEG format, IJETAE2(4) (2012), 694–699, ISSN 2250-2459.

Linde

, Buzo

and Gray

R.M.

, An algorithm for vector quantizer design, IEEE Transactions on CommunicationsCOM-28(1) (1980), 84–95.

Gray

R.M.

, Vector quantization, IEEE ASSP Magazine1(2) (1984), 4–29.

10.

and Salari

, A fast vector quantization encoding method for image compression, IEEE Transactions on Circuits and Systems for Video Technology5(2) (1995), 119–223.

11.

Chen

W.S.

, Yang

and Zhang

, A new efficient image compression technique with index-matching vector quantization, IEEE Transactions Consumer Electronics43(2) (1997), 173–182.

12.

T.C.

and Chang

C.Y.

, A survey of VQ codebook generation, Journal of Information Hiding and Multimedia Signal Processing1(3) (2010), 190–203. ISSN 2073-4212.

13.

Shen

J.J.

and Lo

Y.H.

, A New Approach of Image Compression Based on Difference Vector Quantization, 7th International Conference on (IIH-MSP), Dalian, China, 2011.

14.

Shen

M.Y.

and Kuo

C.C.J.

, Review of postprocessing techniques for compression artifact removal, Journal of visual Communication and Image Representation9(1) (1998), 2–14.

15.

Triantafyllidis

G.A.

, Tzovaras

and Strintzis

M.G.

, Blocking artifact detection and reduction in compressed data, IEEE Transaction on Circuits and System for Video Technology12(10) (2002), 877–890.

16.

Wang

and Porikli

, Multiple Dictionary Learning for Blocking Artifacts Reduction, Proc of IEEE ICASSP, Kyoto International Conference Center, Kyoto, Japan, 2012. doi:10.1109/ICASSP.2012.6288086

17.

Oztan

, Malik

, Fan

and Eschbach

, Removing ringing and blocking artifacts from JPEG compressed document images, US patent: US7634150 B2, 2009.

18.

Thepade

S.D.

, Mhaske

and Kurhade

, New clustering algorithm for Vector Quantization using Slant transform, ICETACS, St. Anthony’s College, Shillong, India, 2013, doi:10.1109/ICETACS.2013.6691415

19.

Mahapatra

D.K.

and Jena

U.R.

, Partitional k-means clustering based hybrid DCT-Vector Quantization for imagecompression, IEEE Conference on ICT, Noorul Islam University Thuckalay, Tamil Nadu, India, 2013. doi:10.1109/CICT.2013.6558278

20.

Karri

and Jena

, Fast vector quantization using a bat algorithm for image compression, Engineering Science and Technology an International Journal19(2) (2016), 769–781.

21.

Quijas

and Fuentes

, Removing JPEG blocking artifacts using machine learning, IEEE Conference on Image Analysis and Interpretation, San Diego, CA, 2014, pp. 77–80. doi: 10.1109/SSIAI.2014.6806033

22.

Wang

, Liu

, Chang

, Ling

, Yang

and Huang

T.S.

, Deep Dual-Domain Based Fast Restoration of JPEG-Compressed Images, arXiv:1601.04149v3 [cs. CV] 9 April2016.

23.

Schaefer

and Stich

, UCID- An Uncompressed Colour Image Database, SPIE Storage and Retrieval Methods and Applications for Multimedia, San Jose, USA, 2004.

24.

Jain

A.K.

and Dubes

R.C.

, Algorithms for Clustering Data, Prentice-Hall, NJ, USA, 2004.

25.

Gan

, Ma

and Wu

, Data Clustering Theory, Algorithms and Applications, SIAM, 2007.

26.

Ross

T.J.

, Fuzzy Logic with Engineering Applications, WILEY, New Delhi, 2012.

27.

Zhang

and Wandell

B.A.

, A spatial extension of CIELAB for digital color-image reproduction, Journal of the Society for Information Display5(1) (1997), 61–63.

28.

Farrell

, Okincha

, Parmar

and Wandell

, Using Visible SNR (vSNR) to Compare the Image Quality of Pixel Binning and Digital Resizing, Proceedings of SPIE, 2010, pp. 75370C-75370C-75379.