A lossless compression with low complexity transform
Kobchai Dejhan,Sompong Wisetphanichkij
Fusak Cheevasuvit,Somsak Mitatha
Faculty of Engineering and Research Center
for Communications and Information Technology,
King Mongkut's Institute of Technology Ladkrabang
Bangkok 10520, Thailand
Tel : 66-2-326 4238, 66-2-326 4242
Fax : 66-2-326 4554
Email : kobchai@telecom.kmitl.ac.th
Winai Vorrawat
National Research Council of Thailand, Phaholyothin Road, Jatachuk
Bangkok 10900, Thailand
Chatcharin Soonyeekan
Aeronautical Radio of Thailand, 102 Ngamduplee, Tungmahamek
Bangkok 10120, Thailand
Abstract
This paper proposes a new lossy image compression scheme that utilizes the advantage of both
transformation and context-based compressions. The interpixel and coding redundancy reduction can be
achieved by this proposed method. Discrete Cosine Transform (DCT) is used to decorrelate the interpixel
relation, while Rice-Golomb coding as the high performance of context-based lossy compression with
remapping of DCT coefficients. The results show the higher compression ratio of the proposed method
when compared with both context-based and JPEG-baseline, especially for low continuous tone image.
Introduction
The term data compression refers to the process of reduction the amounts of data require to represent a
given quantity of information. In digital image compression, three basic data redundancies can be
identified and exploited as follows:
- Coding redundancy
- Interpixel redundancy
- Psycho visual redundancy.
Fig 1 shows a compression system, it consists of two distinct structural blocks: encoder and decoder.
The encoder is source encoder, which removes input redundancies and a channel encoder, which
increases the noise immunity of the source encoder’s output. The decoder includes a channel decoder
and followed by a source decoder.
Figure 1 General compression system model
The principle of the error-free compression strategies, it normally provides the compression ratio of 2 to
10. Moreover, they are equally applicable to both binary and gray-scale image. The error-free
compression techniques generally composes of two relatively independent operations: (1) modeling,
assign an alternative representation of the image in which its interpixel redundancies are reduced; and
(2) coding, encode the representation to eliminate coding redundancies. These steps correspond with
the mapping and symbol coding operation of the source coding model.
The simplest approach of error-free image compression is to reduce only coding redundancy. Coding
redundancy normally presents in any natural binary encoding of the gray levels in an image and it can be
eliminated by construction of a variable-length code that assigns the possible shortest code words to the
most probable gray levels so that the average length of the code words is minimized.
where
L is the number of gray levels.
rkrepresents the gray levels of an image.
l(r
k) the number of bits used to represent each value of r
k.
p
r(r
k) probability of r
k occurring.
The modeling part can be formulated as an inductive inference problem. Having scanned past data
ix=x1x2x3… x
i, one wishes to make inference on next pixel value x
i+1 by assigning a condition probability
distribution p(.|x
i) to it. Ideally, the code length contributed by x
i+1 is –log p(x
i+1|X
i
) bit, which averages to
the entropy of the probabilistic model. Assigns a high probability value to the next pixel with skewed (low-
entropy) probability distribution is desirable. It can be obtained through the larger conditioning regions or
context and generally broken into the following components:
- A prediction step, in which a deterministic value xis guessed for the next pixel xi+1 based on
past sequence xi(a causal template)
- The determination of a context in which xi+1 occurs.
- A probabilistic model for the prediction residual (error signal) conditioned
on the context of xi+1.
