INSTRUCTION

Block Truncation Coding (BTC) method is applied in the field of image compression of its simple coding method, fast calculation, image restoration quality and the channel BER is not sensitive. After 1979, researchers proposed block truncation coding algorithm a number of improved algorithms appeared and these methods were used in many field such as image transmission (Chang et al., 2001), digital Rights Management (Tu and Hsu, 2005), limited-color display (Pei and Cheng, 2006) and data hiding (Chang et al., 2008). But the disadvantage of the block truncation coding method was that there was blocking effect on the edge because the single two-block coding can cause the value jump on the edge and the compression ratio was lower than the other compression methods. So, there were many improved methods in order to reduce the error on the edge and improve the compression quality (Skarbek and Pietrowcew, 2006; Wang and Neuvo, 2005; Heng-fu et al., 2009; Guofang and Wang, 1999). In order to improve the quality of decoding image restoration, it may be based on changes of the value of the image pixel intensity automatically adjust the number of quantization levels to improve the quality of compressed image reconstruction. This paper proposed an auto-block coding method. Experiments show that this method can improve the quality of decoding image restoration.

AUTO-BLOCK TRUNCATION CODING

Encoding principles:

(1)

After coding, the sending order of tag-bit, quantization level and quantization bitmap are shown in Fig. 1.

Decoding principles: The receiver judge the type of encoding block according to the received flag, If the received tag-bit is 00, the received block is considered to be mean-quantization block, using the received mean value instead of the whole image pixel value to restore the pixel block; If the received tag-bit is 01, the received block is considered to be two-level quantization block, according to the position of 0 and 1 in binary bitmap, replace the Fig. 1 location with high level and replace the value 0 position with the low-level. If the received tag-bit is 10, the received block is considered to be four-level quantization block, the position 00, 01, 10, 11 will be restored with four quantization levels according to the four-level bitmap in the bitmap.

Design of two-level quantizer: Set threshold T₀, divide the pixel in the block into two groups, the pixel in one group are all higher than T₀, the pixel in another group are lower than T₀. Using a binary bitmap P(i, j) to represent the output bit of two-level block truncation coding, which X(i, j) represent the gray value in the position of (i, j) in the block X. Finally, the calculate two gray value a and b(a≤b ) in each block, when P(i, j) = L, the pixel X(i, j) is quantified as b, otherwise is quantified as a:

(2)

(3)

Fig. 1:	The order of the sending message

(4)

(5)

where, X_L represent the pixels which are lower than threshold in the block, N₀ is the number of X_L. X_H represent the pixels which are higher than threshold in the block, N₁ is the number of X_H.

Design of four-level quantizer: Set dynamic threshold T_L, T_M and T_H and four quantified level values. The pixels in the block X are divided into four groups by three dynamic threshold and using P(i, j) to represent the output bit of four-level block truncation coding, such as Eq. 6 shown. μ1, μ2, μ3, μ4 respectively represent the decoding values of the four quantization levels:

(6)

Three dynamic threshold of the strike is divided into three steps, as shown in Fig. 2.

Firstly, the method to seek the threshold values T₁ and the two-level quantizer threshold value T₀ are in the same way, such as Eq. 2. The whole pixels in the block are divided into two parts by T₁, secondly, using formula of the two-level quantizer again to seek two dynamic threshold T_L and T_H in the two groups respectively, the whole block is divided into three groups by two dynamic threshold. Finally, using formula of the two-level quantizer again to seek dynamic threshold T_M in the middle area where values are higher than T_L and lower than T_H.

Fig. 2:	The step of calculating threshold

The block is divided into four groups G₁, G₂, G₃, G₄ by three dynamic thresholds. The quantitative level μ_i in each part is mean pixel value for each group.

(7)

When Q(i, j)) = 00, X(i, j) is quantified as μ1, when Q(i, j) = 01, X(i, j) ) is quantified as μ₂, when Q(i, j) = 10, X(i, j) is quantified as μ₃, when Q(i, j) = 11, X(i, j) is quantified as μ₄.

SIMULATION EXPERIMENT

Here, the image contrast results of traditional block truncation coding and auto-block image coding method of coding are given.

Mean Square Error (MSE): {f(m, n)} indicates the original image, indicates the decoding image. Assume the size of the two images is MxN, the mean square error between them is:

(8)

Peak Signal to Noise Ratio (PSNR)

(9)

Two dimensions of the Tree image are selected to do the simulation experiment which is separate two-level block truncation coding and auto-block coding. Figure 3 is the original image of 512x512 dimension, Figure 4a and b show the decoded image of the separately two-level block truncation coding and the decoded image of auto-block Coding with the two thresholds of (8, 30).

Fig. 3:	The original image before coding

Table 1 show the peak signal to noise ratio comparison result of two different sizes images of the two images with the two-level block truncation coding and auto-block coding.

Experimental results show that the peak signal to noise ratio of auto-block coding quantization recovery image is better than two-level quantization recovery image and can reflect the real information in details better. And the value of the peak signal to noise ratio increase with the decreasing of λ₁ and λ₂. Especially the decrease of λ₂ will increase the number of the four-level quantization block, the peak signal to noise ratio is even greater. But it will also affect the compression rate and increase the number of bits.

Table 1:	PSNR comparison result of the two methods

Fig. 4:	(a, b) The decoding images after two-block coding and auto-block coding

Fig. 5:	Compression ratio comparison

The compression ratio of two-level block truncation coding method is generally 1:4. Auto-block coding method sacrifices a certain amount of compression ratio to achieving a better visual effect.

Figure 5 shows the results that the two-level block truncation coding compared with three kinds of auto-block coding compression. Our experiments selected 512x512 and 256x256 two-sized Tree images, which calculated compression ratio of four encoding methods.

The data in Fig. 5 show that the compression rate of the auto-block coding has slightly less than the one of the two-level block truncation coding. However, it doesn’t have little lower in values of λ1 and λ2 which are respectively 10 and 40, the compression rate in 512x512 Tree image is close to two-level block truncation coding compression ratio.

CONCLUSION

This study presents an auto-block coding method. Experimental results showed that auto-block coding method has better image compression than the two-level block truncation coding method, which has improved in peak signal to noise ratio. But it doesn’t have much effect on the right compression ration and the compression ratio of the improved method is lower then four. It could be observed that the compression ratio can be changed when the values of λ₁ and λ₂, so how to improve the compression is another problem we can work on to perfect the method.

ACKNOWLEDGMENT

This research was supported by the National Natural Science Foundation of China (60572030) and the Chun Hui Program of Chinese Education Department (Z2007-1-15014).