3.2.2 Quantization

           Here we studied the characteristics of the wavelet transformed image coefficients and explored a new quantization technique. The new technique has a semi-uniform structure, which makes it less complex compared to non-uniform techniques and more accurate than uniform techniques.

3.2.2.1  Quantization Techniques

           In the literature there are three quantization techniques; uniform, non-uniform and semi-uniform. All these methods use image histogram to choose the quantization regions.

           Uniform quantization is the simplest and fastest method but the quality of quantized image is not optimal. Firstly, minimum and maximum of used colors are determined. Afterwards, between min. and max. values histogram is equally divided into sub-regions. Then, center value of each sub-region is used to quantize the image.

           Non-uniform quantization algorithms generally search histogram to find optimal sub-regions that minimum visual distortion occurs. So these methods are slower than uniform quant. methods because they try to minimize pixel-by-pixel mean square error (MSE), whose calculation contains many multiplications and divisions. One of the most known non-uniform techniques is Lloyd-Max [5]. In this method sub-regions are not equal sized.

           Semi-uniform techniques are same as uniform quantizers. However, the reconstruction levels are the centroids of the sub-region. The centroids lie at the center of the mass of the probability density enclosed by the two adjacent sub-regions. The centroids are determined by the sub-regions and the pixel values based on the number of pixels[6].

3.2.2.2 A Semi-Uniform Quantization with Dead-Zero Around and Binary Clustering

           In this study a new semi-uniform quantization technique has been developed. Looking at each subband, histogram of a wavelet transformed image shows that there are Gaussian-like curves. It can be seen in Figure 6. that only lowest subband LL doesn’t obey this rule.

Figure 6. Histogram of each subband.

           In wavelet domain zero around coefficients represent the minimum details. Erasing them makes les visual changes than bigger coefficients. Once threshold T is calculated, all coefficients between –T and +T is replaced with zero for quantization purposes. As coefficient values increase, the importance of existence in wavelet domain increases. Here we used a binary-clustering technique to find sub-regions. We don’t choose center of the sub-region as quantized coefficient but calculate the centroid.  

           Threshold T is calculated by quality factor QL, which is supplied by Quality Control section of encoder. If QL = 0.9 = 90%, 10 percent of coefficients from positive and negative sides are erased. To do so, we need to know how many positive and negative coefficients are there in the histogram. For positive part 10 percent of the coefficients are erased and this process is repeated for negative part.

           Binary clustering technique calculates the sub-region starting from threshold T. Suppose there are 100 coefficients in positive part. First 10 coefficients are erased by T. Remaining 90 coefficients are divided into regions 2⁰=1, 2¹=2, 2² =4, 2³,=8, 2⁴=16, 2⁵=32, 2⁶=64 respectively. 2³ mean sub-region will be 8 coefficients long. These coefficients get together to form a sub-region. In negative part reverse order of above technique is used. Figure 7 shows this process.
 

 Figure 7. Selected sub-regions in the histogram of a subband.

           Centroids are calculated in two steps. Firstly, average of coefficients (AOC) and center average number of repeats (centerANOR) is calculated. Then, two new ANOR ‘s are calculated from left and right side of AOC. Whose ANOR is nearest to centerANOR, new AOC is calculated for that part using old AOC for start or end point. newAOC is the representer of this sub-region.

           Suppose sub-region size is 2³ = 8 coefficients long, as in Figure 8. From (8), (9) and (10) it can be seen that centerANOR  = 117 is near to leftANOR = 138. So newAOC is calculated from left part. The number 69 represents this sub-region. When a coefficient comes in this ragion, newAOC will be used instead.

                                                   (7)
 

                         (8)
 

                                  (9)
 

                                                  (10)
 

                                                   (11)

 Figure 8. Sample positive sub-region.

           Quantization results are in Table 1. Because of the successive quantization, quantized PSNR is 35 dB for 80 %, which is quite acceptable and has little visual distortions. 

Table 1. PSNR Results for Akiyo 279th Frame.
 

(a)                                                                  (b)

Figure 9. Akiyo 279^th frame (a) original, (b) 70% semi-uniform quantized.