International Journal of Scientific & Engineering Research, Volume 4, Issue 12, December-2013 1170

ISSN 2229-5518

UMRT based Adaptive Block Size Transform

Coder for Images Using Quad-tree partitioning

Abstract

M S Anish Kumar1, Preetha Basu2, R Gopikakumari2

1.Department of Electronics, Cochin University of Science and Technology, Cochin, Kerala, India

Email: anishdoecus at@gmail.com , anishdoe@cus at.ac.in Phone: 00919447500698.

2.Division of Electronics Engineering, School of Engineering, Cochin University of Science and Technology, Cochin, Kerala, India

Variable block size (VBS) transform coding techniques have been proven to be capable of enhancing performance of a fixed size transform

coding system. However, the criterion of determining the block size used still remains to be devised. In this paper, a new criterion for quad-tree partitioning of images based on UMRT and a new UMRT based adaptive block size transform coder are proposed. The new criterion determines the block size suitable for coding a particular area of an image. The purpose of the algorithm is to take advantage of large uniform regions that can be coded as a single large unit instead of smaller units and to use smaller units to code fine details. It is shown that the variable block size UMRT based transform coding system using the proposed UMRT based decision criterion offers better performance for all images tested.

Keywords MRT, UMRT, Quad-tree, Adaptive Transform coding

1. Introduction

Transform-based image coding algorithms have been the object of intense research during the last three
In fixed block size image coding scheme, this has not taken into consideration that image statistics may be

IJSER

decades. Eventually they have been selected as the main
mechanism of data compression in the definition of digital
image and video coding standards. A transform-based
image coding method involves subdividing the original image into smaller N × N blocks of pixels and applying a unitary transform, such as the DCT, on each of these blocks. In general, once the value of N has been selected for a particular algorithm, it remains fixed. In JPEG, for instance, the value of N is 8, and thus the input image is divided into blocks of 8x8 pixels exclusively.

------------------------------------------------------------------------------------

M S Anish Kumar received M.Sc. degree in Electronics from the Cochin University of Science And Technology, Kochi, Kerala, India in 2003. He is currently pursuing PhD degree at the Cochin University of Science And Technology. His research interests include image compression, image filtering etc.

Preetha Basu received B.Tech (Electronics and communication) degree from Kerala University and M.Tech(Digital electronics) degree from Cochin University of Science And Technology in the year 1990 and 1997 respectively. She is working as Assistant professor in TKM College of Engineering, Kollam and presently is a research scholar in Division of Electronics, SOE, Cochin University of Science and Technology.

R. Gopikakumari received B. Sc (Engg.) degree from the Kerala University and M. Tech & PhD degree from the Cochin University of Science And Technology in the year 1984, 1987 & 1999 respectively. She is working in Cochin University of Science And technology since 1988 and currently she is the Head of the Division of Electronics Engineering. Her fields of interest are Digital Signal Processing, Image Processing, Neural Network etc..

inhomogeneous and vary from area to area in an image.
Some areas of an image may have only smooth changes and contain no high contrast edge. In these areas, higher compression can be obtained by using a larger block size.
However, in areas contain high activities and
contrast edges, a transform of a smaller block size should
be used to obtain better visual quality. In this paper an adaptive block-size transform coding scheme based on the UMRT algorithm is presented, and some results are presented showing the improvement of the compression efficiency with respect to the non-adaptive schemes.
Therefore, to truly adapt to the internal statistics of an image in different areas, a transform coding system should vary the block size to yield a better tradeoff between the bit rate and the quality of decoded image. Generally, if a segment of an image contains high activities, the segment should be partitioned into smaller areas. This process continues until the divided segments have homogeneous statistics or only smooth changes. In [1], an adaptive transform coding system using variable block size was proposed. The system uses a mean-difference based criterion to determine whether a block contains high contrast edges or not. If a block contains high contrast edges, the block is divided into four smaller blocks and the process repeats with the divided blocks until the four blocks contain no further high contrast edges or the smallest block size is reached.

International Journal of Scientific & Engineering Research, Volume 4, Issue 12, December-2013 1171

ISSN 2229-5518

In this paper, a new UMRT based criterion function to determine whether a block should be divided into smaller ones is also proposed. Unique Mapped Real Transform (UMRT) [3], with its strong properties, is powerful to replace DCT in encoding images as the UMRT coefficients computation involves only simpler arithmetic. Transform coders based on 4x4 MRT[2] & 8x8 MRT are described in [4] and [5] respectively. The proposed adaptive transform coder utilizes UMRT coefficients as a criterion for image segmentation and UMRT as a tool for compressing images by converting the statistically

3. Unique Mapped Real Transform

(UMRT)

MRT [2] is an evolving transform that helps in frequency domain analysis of 2- dimensional signals without any complex operations but in terms of real additions alone. The MRT mapping is highly redundant. A compact unique MRT (UMRT)[3] representation is derived by eliminating the redundant elements present in the MRT representation [3].
The Equation (1) maps the N × N data matrix, Xn1,n2
, into M matrices of size N × N in the frequency domain

( p )

dependent image elements to independent coefficients.
using real additions only.

Yk1,k2

is the MRT matrices,
Irrelevancy reduction is done by applying simple threshold
and therefore simple algorithms can be used for the image coding and decoding. Simulation result has shown that the proposed algorithm yields better quality decompressed images at lower bit rates.

2. Mapped Real Transform (MRT)

where 0 ≤ k1,k 2 ≤ N − 1 and 0 ≤ p ≤ M-1, M=N/2,. The MRT representation shows a specific pattern of redundant elements in the MRT matrices. For a two-dimensional signal of size N × N, the total number of MRT coefficients is N 3 / 2 , however only N 2 coefficients are unique [3]. Thus the MRT mapping is highly redundant. The UMRT representation is derived by eliminating the redundant
elements present in the MRT representation. Different

IJSER

Both MRT and MRT based Image coding are
evolving subjects[2].

Let the data matrix be Xn1,n2 , 0 ≤ n1,n2 ≤ N − 1 and the

MRT be

Y ( p ) , 0 ≤ k ,k ≤ N − 1 and 0 ≤ p ≤ M-1, M=N/2,

k1,k2

where
algorithms are proposed for identifying and placing the N2
UMRT coefficients in a N × N matrix [6]-[8].

4. UMRT Based Criterion for Partitioning images

Transform coding has been proven to be a promising technique to achieve image data compression.

( p ) = ∑

n ,n − ∑

n ,n

As real images often have inhomogeneous statistics over

Yk1,k2

X 1 2

∀( n1,n2 ) z = p

X 1

∀( n1,n2 ) z = p + M

(1)
different areas, adaptivity has to be incorporated into a
transform coding system for the greatest benefit. Usually,

z = ((n1 k1 + n2 k2 ))N (2)

Equation (1) maps the N × N data matrix into M matrices of size N × N in the frequency domain using real additions only.
The inverse transform relation is as follows
there are several parameters in a transform coding system
which can be made adaptive to an image. For example,
quantizer step size, bit allocation, transform kernel, and the
block size used to partition an image can be adaptive. Here, a variable block size adaptive transform coding system is proposed.

X = 1

1 ( q )

∑ X

, 0 ≤ n1 , n2 ≤ N-1 (3)

The magnitude of the UMRT coefficients other

n1,n2

Where

( q )

n ,n

N 2 q = 0

n1,n2

∑

( p )

k ,k

( p )

k ,k

than the DC coefficient is a measure of the homogeneity of
the image block under consideration. If the magnitude of any of the MRT coefficients, other than the DC coefficient, of a particular N × N image block is higher than a threshold value t, then the image block under consideration contains

1 2 ∀( k1,k2 , p ) j = q 1 2

∀( k1,k2 , p ) j = q + M

1 2

(4)
edge or inhomogeneous area and therefore that image
block should be partitioned in to four N/2 × N/2 blocks. Experiments proved that 100 is a good value for the

j = ((((-((n 1 k1 + n 2 k2 )) N )) N + p)) N (5)

threshold t.
An example of a K-level quad-tree structure is
shown in Figure.1. A quad-tree is said to be a K-level quad-
tree if the lowest level allowed is K-1. It can be represented by assigning 0 to non-leaf nodes and 1 to leaf nodes. Each

International Journal of Scientific & Engineering Research, Volume 4, Issue 12, December-2013 1172

ISSN 2229-5518

node in a quad-tree represents a block. If the block can be split into four quadrants, then the node will generate four
children nodes. Otherwise the node becomes a leaf. Figure
2. is a quad-tree partitioned Lena image using the
proposed UMRT based criterion.

5. Adaptive Block Size Transform Coding

Technique

The proposed coding scheme is shown in Figure 3. In the proposed coder, initially, the block size is taken as the size of the image, N × N, itself and the minimum block size is taken as 2×2. All homogenous areas in the image are partitioned in to larger blocks and inhomogeneous areas are partitioned into smaller blocks by applying the UMRT based criterion described above. This process continues until the image is partitioned in to homogeneous blocks or up to the minimum block size is reached. In other words, the maximum and minimum size of partitioned blocks may vary up to N × N and 2×2 respectively. Ideally, if the criterion can make appropriate decision at boundary where there is a change in the image statistics, the divided blocks should have only uniform change within it.
Each partitioned block is then transformed by
UMRT of corresponding size. Threshold coding is then

applied to the UMRT coefficients of each block, other than the DC coefficients, to avoid irrelevant information. The coefficients overcoming the threshold and their
corresponding positions in the UMRT matrices are stored
in two separate linear arrays. Then coefficient coding is
applied to these two linear arrays to obtain the compressed data. To reconstruct the original image, the decoding algorithm has to know the block size used to encode

Figure 1. K level quad-tree

Figure 2. Partioned Lena Image

different part of an image. Thus, the hierarchical data
structure, quad-tree, is used. In the variable block size
transform coding system described, the number of levels in the quad-tree depends on the size of the image N × N, and the homogeneity of the image.

6. Simulation Results

A computer simulation is carried out to find the performance of the proposed technique. The input image has resolution of 8 bits per pixel and the image size is

512×512. The largest block sizes allowed is the size of the

image itself (512×512) and the smallest block sizes allowed is 2×2. The decision threshold t is 100. The quantized coefficients are arithmetic coded in a similar way as in [4]
& [5]. Table 1. Shows the simulation results for various
images. It can be seen that the adaptive block size
transform coding system using UMRT produces lesser bits per pixel with better reconstructed image quality for most of the images. Figure 4 - 6 show original and reconstructed versions of Lena, Baboon and Cameraman images.

International Journal of Scientific & Engineering Research, Volume 4, Issue 12, December-2013 1173

ISSN 2229-5518

IJFSigure 3. ProposeEd coding schemeR

Image	bpp	PSNR(dB)
Lena	0.31	30.27
Baboon	0.85	24.84
Barbara	0.61	27.08
Goldhill	0.42	28.96
Peppers	0.32	30.49
Couple	0.51	29.25
Elaine	0.31	29.93
Cameraman	0.30	31.03
Boat	0.49	28.75
Bridge and Stream	0.75	25.88

Table 1.

International Journal of Scientific & Engineering Research, Volume 4, Issue 12, December-2013 1174

ISSN 2229-5518

Figure 4. Lena (a) Original and (b) Reconstructed (bpp =0.31, PSNR =30.27 )

IJSER

Figure 5. Baboon (a) Original and (b) Reconstructed (bpp =0.85, PSNR = 24.84)

Figure 6. Cameraman (a) Original and (b) Reconstructed (bpp =0.30, PSNR = 31.03).

International Journal of Scientific & Engineering Research, Volume 4, Issue 12, December-2013 1175

ISSN 2229-5518

7. Performance comparison

Table 2 shows a comparison between the performances of the proposed adaptive block size coder using UMRT and fixed block size coders using 8x8 MRT [4] and 4x4 MRT [5]. It is evident that the proposed method gives better performances at all bit rates. At lower bit rate
(0.3 bpp), the PSNR values of the reconstructed images using the proposed coder are 2dB more than that of the

fixed block size methods.

PSNR(dB)

Image

0.3 bpp 0.5 bpp 0.75 bpp

8x8 4x4 Adaptive 8x8 4x4 Adaptive 8x8 4x4 Adaptive

Lena 27.68 27.05 30.27 30.18 30.27 31.01 32.03 32.72 33.08
Peppers 27.43 26.52 30.49 29.86 30.41 31.88 31.55 32.71 33.40
Goldhill 27.25 26.68 27.42 29.04 29.16 29.73 30.34 31.13 31.20
Couple 26.47 25.87 25.94 28.82 29.16 29.25 30.86 31.70 31.90
Cameraman 28.55 26.79 31.03 31.20 31.47 32.45 33.35 34.25 34.85
Boat I25.94 J25.19 S25.79 27.88E28.29 28R.76 29.48 30.39 30.55
Elaine 28.46 28.37 29.93 29.93 30.60 30.71 31.15 31.57 31.60

Table 2

The Table.3 shows a comparison of the proposed coder with the DCT and DWT based transform coding
schemes [9]. The table shows that the proposed coder also produces almost the same PSNR for a compression ratio of
10:1. Here the advantage of the proposed coder is that the UMRT can be computed using real additions only, compared to additions and multiplications required for DCT and DWT.

Image	Compression Ratio	PSNR(dB)
Image	Compression Ratio	DCT	DWT	MRT
Lena	10:1	32.90	32.51	33.24
Peppers	10:1	34.30	34.43	33.82
Baboon	10:1	25.30	24.91	24.84

Table 3

8. Conclusion

The limitation of conventional fixed block size transform coding system has been discussed. A UMRT based adaptive variable block size transform coding
system is proposed and compared with the non-adaptive versions. Simulations have been carried out on various
gray scale images. The results show that the proposed technique results in a variable block size coding system with higher PSNR and image visual quality.

References

[1] Cheng-Tie CHEN, 'Adaptive Transform Coding Via Quadtree-Based Variable Blocksize DCT', International Conference on ASSP, pp.1854-1857,
1989.
[2] Rajesh Cherian Roy, and R. Gopikakumari A new
transform for 2-D signal representation (MRT) and
some of its properties, 2004 IEEE Int. Conf. on Signal Processing and Communications (SPCOM) Dec. 2004, Bangalore, India, pp. 363- 367. http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&ar number=1458423&isnumber=31229
[3] Preetha Basu, Bhadran. V, R. Gopikakumari A New Algorithm to Compute Forward and Inverse
2-D UMRT for N - a power of 2., 2012 Int. Conf. on Power, Signals, Controls and Computation

International Journal of Scientific & Engineering Research, Volume 4, Issue 12, December-2013 1176

ISSN 2229-5518

(EPSCICON), Jan. 2012, Kerala, India pp. 1- 5. http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&ar
number=6175226&isnumber=6175222
[4] M. S. Anish Kumar, R. C. Roy, R. Gopikakumari,
A new image compression and decompression technique based on 8 x 8 MRT, ICGST Int. J. Graphics, Vision and Image Process., vol. 6, no. 1, pp. 51-53, Jul. 2006.
[5] M. S. Anish Kumar, R. C. Roy and R.
Gopikakumari, A new transform coder for gray scale images using 4x4 MRT, AEU, Int. J. Electronics and Commun., vol. 62, no. 8, pp. 627-
630, September 2008.
[6] Rajesh Cherian Roy, “Development of a new
transform MRT”, Ph. D Dissertation, Cochin
University of Science & Technology, Kochi, 2009.
[7] Bhadran V, “Development and implementation of
visual approach and parallel distributed Architecture for 2D DFT and UMRT computation” Ph. D Dissertation, CUSAT, 2009
[8] Roy, R.C., Anish Kumar. M.S., Gopikakumari, R.
An invertible transform for image representation
and its application to image compression," 2007.
9th Int. Symp. on Signal Processing and Its
Applications, (ISSPA) Feb. 2007, Sharjah, pp.1-4, http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&ar number=4555504&isnumber=4555273
[9] Sonja Grgic, Mislav Grgic, Member, IEEE, and Branka Zovko-Cihlar, Member, IEEE, Performance Analysis of Image Compression Using Wavelets, IEEE TRANSACTIONS ON INDUSTRIAL ELECTRONICS, VOL. 48, NO. 3, pp. 682-695, JUNE 2001.