Keywords

variable blocksize;quadtree segmentation; differential pulse code modulation (DPCM); double predictor estimation 
INTRODUCTION

The proposedquadtree segmented variable blocksize double predictor differential pulse code modulation (VBDP– DPCM) image coding system operates on an image that has been preprocessed into segments of variable size, square blocks. A double predictor DPCM (DP–DPCM) system is then applied to encode each image subblock separately. When transmitted over a noiseless channel, the distortion between the original signal and reconstructed signal is primarily due to quantization error provided that an optimal predictor is employed. Reconstructed signal degradation because of quantization error becomes severe at low bit rates due to the fact that large quantization errors are directly fed back into the predictor and to be used in subsequent estimation of future input signal [1]. The proposed VBDP– DPCM algorithm has been establishedto moderate the feedback loop quantization error effects in the vicinity at the expense of predictor optimality from a minimum meansquarederror (MMSE) point of view. This VBDP–DPCM scheme divides a given image into variable size image subblocks and attempts to balance between suboptimal predictor designs. The proposed scheme mayexpressively reduce feedback effects due to quantization errors locallywith the objective of maximizing reconstructed image quality for each test image entirely. 
When processing a given image frame, we initially apply the quadtree segmentation algorithm [2]–[4], [11]–[14] to divide a given test image into image subblocks having widely differing perceptual importance. The detail regions of a given image with more features activity will be segmented into blocks with smaller block size, and the background inactive regions of the image should be assigned larger block size for the areas. The blocksizes can vary from 128x128 to 8x8 in this study. The variable blocksize image segmentation processis to better meet the nonstationary mathematical description of realworld images. Having acomprehensive characterization of the underlying stochastic nature of a source signal generally results in a more efficient source encoder for that signal. After the quadtree image segmentation, the predicted differential values between the nearby pixels of an image block are reduced. Therefore, we can decrease the distribution range of prediction error and reduce the bit rate as well as quantization levels. We then applied the DP–DPCM [6]–[8] scheme to each image subblock. As in the case of conventional DPCM image coding system the emphasis of system design is focused on the prediction process which should reduce MMSE estimates of the input signals. Similarly, quantizer design is based on a match to the probability density function of a differential signal. The quadtree image segmentation method applied is to divide a given image according to the activity details within the image into variable size image subblocks. Each image subblock will be more stationary than the original image frame and the predicted differential values between the nearby pixels of an image subblock are condensed. The quantizer design employed in the encoder is locally optimal in the MMSE sense. Experimental results have been obtained by processing two test images named,“LENA” and “WALT”. Objective measurement of system performance shows that the SNR obtained using the VBDP–DPCM scheme is about 5 dB or greater compared to that of conventional DPCM employing a predictor of the same order for low bit rate (R? 3) image compression. 
In this paper, Section II describes the basic concepts regarding a conventional 2D DPCM image encoder scheme as well as a double predictor DPCM encoder algorithm proposed earlier. Section III focuses on the proposed quadtree variable blocksize image segmentation applied to a double predictor DPCM image compression applied in this study. The overall VBDP–DPCM image encoding system configuration and performance results are shown in Section IV. Finally, a summary and conclusions are presented in Section V. 
RELATED WORK

In a conventional 2D DPCM image encoder having a feedback loop around the quantizer, the prediction sequence values ij xˆ depend on the previously quantized error values ij x ~ rather than on past unquantized input data values xij. This ensures that the transmitter and receiver components of the DPCM system can track and reconstruct the input signal waveform in a stable fashion. For a given NxN image with pixel intensity values xij,i, j = 0, 1, …,N–1, a typical 2D causal image predictor having thirdorder support used to determine the estimation sequence is described by 

which can be compactly express as 

where bx, cx, and dx are the predictor coefficients of the DPCM predictor and b x ~ , c x ~ , and d x ~ are the data values input to the predictor filter corresponding to locations b, c, and d in the image field, as shown in Figure 1. 
Let P denote the onelag covariance where J = 2 for an image model with separable autocorrelation function and J = 2 for an isotropic image model [5]. The optimal thirdorder predictor is defined by the prediction coefficients: 


Performance for the conventional DPCM systemis shown that the quantization in the encoder loop is not adequately fine if the encoding rate is 3 bits/pixel or less, the quantization error is not small enough so as to be ignored in the design of the optimal linear predictor.In order to balance between suboptimal predictor designs and significantly reduce feedback effects due to quantization errors with the objective of maximizing reconstructed image quality, a double predictor DPCM algorithm has been proposed [6]. 
Figure 2 illustrates the block diagram of a DP–DPCM algorithm. The corresponding DPCM decoder consists of two cascaded filtering stages. The DP–DPCM scheme has an overall structure similar to that of a double differentiatorintegrator system[9]. Filter coefficient values are chosen under constraints that guarantee system stability. There are two predictor filters, H and F in this scheme, where Q is a PDFoptimal quantizer of either a uniform or nonuniform structure. The output of the first subtractor, e(n), is input to a second subtractor whose other input is a local estimate of the differential signal itself. The output signal ?(n) is the difference sequence e(n)–ê(n). The quantizer output sequence ?(n) is fed back into the adder along with the estimationê(n) of e(n) producing e~(n)which is the input to the filter F and to the primary prediction loop. Conceptually, e~(n)should be statistically closer to the prediction error e(n) rather than the quantizer output signal ?(n). 
The predictor coefficients can be written as 


We have assumed that the average value E[e(n)]=0, the onelag covariance of e(n), ? e is then defined as 

where a x ~ and b x ~ are defined as in eq. (2), 2 σe is the variance of the error sequence e(n)and E[eaeb] is the error correlation. For 2 σe ; is of the form as following [10] 

we can obtain the covariance ? e to be of the following equation 

We now are able to calculate the optimal filter coefficients of predictor F by substituting ρ e andρ e J into eq. (5) and eq. (6). The variance of the difference sequence appearing at the output of the second subtractor is given by 

where The variance of ξ(n) = e(n)–ê(n), denoted as 2 σ ξ , and the square root, σξ (standard deviation of ξ(n)) is the parameter adjusting the dynamic range of the locally optimal quantizerQ. 
PROPOSED ALGORITHM

To improve image data compression performance further, we have proposed a combined system based on variable blocksize quadtree image segmentation applied to double predictor differential pulse code modulation (DP–DPCM) image compressive algorithm. 
Ina variable blocksize image compression system, we segment the input image into variable size blocks, for which a “detail” region comprisingmore image features activity is partitioned into a smaller block size, each subimage blockcan be moresensibly described the appearances in the region, and a “background” region with less image variationis assigned a larger blocksize. We have espoused a topdown quadtree approach [2] to obtain the tractability of a variable blocksize segmentation procedure while eluding the excessive overhead needed to characterize more sophisticated image segmentation techniques. To segment a 256x256 image by using the quadtreeprocedure, we begin with dividing a given 256x256 input image into four 128x128 equal size blocks. Each 128x128 image block is set to be a root(initial node), from which the algorithm passes through the tree from level to level. At each node, a test is executed to determine whether the image blockrepresented by that node is a “background” region or a “detail” region. If the test agrees that the block is a “background” region, then the node becomes a leaf. If not, the segmentation proceeds to the next level and the four branches of the node are each examined consecutively. The final quadtree structure is represented by one bit of side information for each node, which indicates whether that node is a nonleaf or a leaf node. By adapting the predictor and quantizer structures for each variable size image block the statistical nonstationary inherent in realworld images is competentlyrevealed. Encoding efficiencies are realized by: (i) achieving better edge renovation in busy areas of an image; (ii) considerable rate reductions in areas of nearconstant gray level which is characteristic of the larger block size regions within an image. 
The segmentation test used in this study is implemented as follows: For kth image block xk mn, we first estimate the mean value, E[xk], and the variance, Var(k).Then, we compare the value ofVar(k) with?θE[xk], where ??is a preset threshold. The quadtree segmentation threshold value θ was first picked randomly large and should be reduced to deal with the anticipated distortion until a tolerable reconstructed image quality achieved. If Var(k)≥ θE[xk] for the examined image block, then the block is marks as a “detail” region and the segmentation course proceeds to the next level. The test procedure of the quadtree algorithm is illustrated in Figure3. 
Figure 4 presents the proposed variable blocksize double predictor DPCM image coding system,which improves the performance of DPCM by adapting the predictor and quantizer structures for each variable size image block. For the VBDP–DPCMimage coding, an NxN image with pixel intensity values xij,i, j = 0, 1, …,N–1, is segmented into blocks of size MkxMk, where the block size can vary from 128x128 to 8x8. The pixel values of thekthsubimage block is denoted by xk mn, m, n = 0, 1, …,Mk –1, and is expected to possess statistical stationary over the spatial domain. 
For each segmented image block, the firstorder and secondorder statistics are estimated over an entire subblock of image data. Hence, the complete image frame retains globally statistical nonstationary over the spatial domain. The local mean is determined and subtracted from the MkxMk image block to obtain a zeromean image block. To be simplified, quantizers with uniformly spaced output levels were designed on the basis of a Laplacian probability density function (PDF) describing the differential input sequences for each image block. A thirdorder predictor structure is used both for the prediction of xˆ(n) of the image signal based on ~x(n) and for the prediction of the difference signal ê(n) based on e~(n) . Follow the procedures delivered in [8], the design process is modified and outlined in the following steps. 
Step 1: For a given image, we apply the quadtree segmentation algorithm to divide the image into variable size image blocks having widely differing perceptual importance. Estimations of the local mean value, variance, and covariance coefficient ρ x for each image block are provided. 
Step 2: The local mean is deducted from the pixels’ value in each image block to obtain a zeromean image block. 
Step3: Determinethe optimal predictor coefficients,bx,opt,cx,opt,dx,optfrom eq. (3) and eq. (4). For the predictor coefficients values (bx,opt,cx,opt,dx,opt), compute the corresponding variance σ2e of the error sequence e(n)and E[eaeb], the error correlation for the secondstage filter F. 
Step 4: With the values of variance 2 e s and E[eaeb], we can calculate ρ e J =E[eaed]/ 2 e σ and ρ e. We then substitute ρ e J and ρe into eq. (5) and eq. (6) to solve the optimalprediction coefficients (be, ce, de) for the secondstage filter F. 
Step 5: The coefficients (be, ce, de) are substituted into eq. (10) to calculate the variance 2 σξand then the standard deviation, σξof ξ(n). σξ is the parameter to adjust the dynamic range of the locally optimal quantizerQ. 
Step 6: For each zeromean image block, we can determine the predictor coefficients based on the previous steps. The difference sequences after the secondstage predictor can be quantized with the stepsize determined in step 5 and then output to channel. 
SIMULATION RESULTS

The source coding performance of the proposed variable blocksizeDP–DPCM system presented in this study is generally about 5 dB or greater than that of a conventionally design DPCM system when operating at low bit rates (bit rate R≤3 bits/pixel). Noteworthy improvement in performance can be denoted for values of coding rateR greater than 3. Simulation results obtained in this study are summarized in Tables I and II. The output signaltonoise ratio (SNR) is defined as SNR=10log( 2 x σ / 2 e σ )in dB, where 2 x σ is the input image variance and 2 e σ is the reconstructed error variance. Shown in TablesI and II are the image coding results for the VBDP–DPCM system for 256x256 “LENA” and “WALT” images, respectively. The source coding performance of the VBDPDPCM system has higher SNR compared to a conventional stationarybased DPCM system in general. The reconstructed images using the scheme in Figure 4 are mostly of higher quality both subjectively and objectively. Values of SNR equal to 12.68 dB, 17.57 dB, and 22.71 dB are obtained for the 256x256 “LENA” image at the rates of 1, 2 and 3 bits/pixel, respectively, for threshold θ = 5. Values of SNR equal to 16.23 dB, 20.62 dB, and 24.81 dB areachieved for the “WALT” image at the rates of 1, 2 and 3 bits/pixel, respectively, for threshold θ = 5. These results are better than those found using a conventional, stationary DPCM encoder/decoder system. 
Figure 5 compares the subjective quality of reconstructed “LENA” images obtained with the VBDP–DPCM system (θ = 5) to the quality obtained with a stationary, conventionally designed DPCM encoder at transmission bit rates R = 1 bit/pixel. The reconstructed image shown in Figure 5(d) faithfully reproduce graylevel variations in regions of high spatial activity, e.g., the feathers in the “LENA” image are sharper as compared to the blurring present in Figure 5(a), the results for the conventional DPCM encoder. Figure 6 and Figure 7show the visual quality of the reconstructedVBDPDPCM“LENA” and “WALT”images at different coding rates of 1, 2, and 3 bits/pixel, respectively. The decoded imagesnormally have slightly sharper image details, dueto the AR predictionsadapted to local statistics, as well asthe filtering operation to moderate the venomous effects of quantization errors being fed back into the prediction loop of the DPCM code as shown in Figure 2(a). 
CONCLUSION AND FUTURE WORK

The new double predictor DPCM coding system with variable blocksize investigated in this study results in improved source coding performance when compared to a conventionally designed DPCM image encoding scheme for bit rate R≤ 3 bits/pixel. Objective SNR results demonstrate that the new VBDP–DPCM encoding scheme yields better reconstructed image quality visavis conventional, stationary DPCM image encoding system. Performance improvements are the results summarized as: 
• Image segmentation results in the statistical nonstationary inherent in realworld images being better exploited; 
• The DP–DPCM encoding scheme is applied to each segmented subimage block. We are able to adapt the predictor and quantizer structures for each variable size image block; 
• The balance in design of suboptimal difference signal predictors and a filtering operation to reduce the deleterious effects of large quantization errors being fed back into the prediction loop for small values of R. 
The source coding performance of the variable blocksize DP–DPCM algorithm is generally about 5 dB or greater than that of a conventionally designed DPCM coding system when operating a low bitrates. The improved DPCM system provides better edge reproduction that is perceptually important to the viewer. 

Tables at a glance



Table 1 
Table 2 


Figures at a glance




Figure 1 
Figure 2 
Figure 3 



Figure 4 
Figure 5 
Figure 6 


References

 Jain, A. K., “Image Data Compressiona Review,” Proceedings of IEEE, Vol. 69, no. 3, pp. 349389, March 1981.
 Vaisey, J. and Gersho, A., “Image Compression with Variable Block Size Segmentation,” IEEE Transactions on Signal Processing, Vol.40, No.8, pp. 20402060, Aug. 1992.
 Chen, C. T., “Adaptive Transform Coding via QuadtreeBased Variable Blocksize DCT,” Proceedings of ICASSP, Vol.3, pp. 18541857, May 1989.
 Wu, J.C.andDaut, D. G., “Adaptive Nonstationary DPCM Image Coding with Variable Blocksize,”Proceedings of the SPIE Visual Communications and Image Processing (VCIP) 1997, Vol.3024, pp. 447458, San Jose, CA, February 1997.
 Sakrison, D. J., “Image Coding Applications of Vision Models,” Advances in Electronics and Electron Physics, Vol.12, pp. 2171, 1979.
 Daut, D. G., Zhao, D.M., and Wu, J.C., “Double Predictor Differential Pulse Code Modulation Algorithm for Image Data Compression,” Optical Engineering, Vol.32, No.7, pp. 15141523, July1993.
 Chen, H.B.,“Advanced Double Predictor Differential Pulse Code Modulation Image Transmission System,” Master’s thesis, EE dept., Dayeh University, ChangHua, Taiwan, July 1998.
 Wu, J.C.,Chen,H.B., and Liu, R.J.,“Variable BlockSize Double Predictor DPCM Image Coding”, Proceedings of SPIE Visual Communications and Image Processing (VCIP) 2000,Vol.4067,pp. 838847, May 2000.
 Nasseri, Z. and Kanefsky, M., “Doubly Adaptive DPCM,” IEEE Transactions on Information Theory, Vol.36, No.2, pp. 414420, March 1990.
 Tekalp, A. M., Kaufman, H., and Woods, J. W., “Fast Recursive Estimation of the Parameters of a SpaceVarying Autoregressive Image Model,” IEEE Transactions on Acoustic Speech Signal Processing, Vol.ASSP33, pp. 469472, April 1985.
 Hunter, G. M. and Stieglitz,K., “Operations on Images Using Quad Trees,” IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol.PAMI1, No.2, pp. 145153, April 1979.
 Markas, T. and Reif, J., “Quad Tree Structures for Image Compression Applications,” Information Processing & Management, Vol.28, No.6, pp. 707721, 1992.
 Dhanalakshmi, S. andRavichandran, T., “A New Method for Image Segmentation,” International Journal of Advanced Research in Computer Science and Software Engineering, Vol.2, No.9, pp. 293299, 2012.
 Chen, W.L.,Hu, Y.C., Liu, K.Y.,Lo, C.C., and Wen, C.H.,“VariableRate Quadtreesegmented Block Truncation Coding forColor Image Compression,” International Journal of Signal Proc., Image Proc. and Pattern Recognition, Vol.7, No.1, pp.6576, 2014.
