17-05-2014, 01:07 PM
Simple Fast and Adaptive Lossless Image Compression Algorithm
Simple Fast and Adaptive.pdf (Size: 772.72 KB / Downloads: 21)
Abstract
In this paper we present a new lossless image compression algorithm. To achieve
the high compression speed we use a linear prediction, modified Golomb–Rice code
family, and a very fast prediction error modeling method. We compare the algo-
rithm experimentally with others for medical and natural continuous tone grayscale
images of depths of up to 16 bits. Its results are especially good for big images, for
natural images of high bit depths, and for noisy images. The average compression
speed on Intel Xeon 3.06 GHz CPU is 47 MB/s. For big images the speed is over
60 MB/s, i.e., the algorithm needs less than 50 CPU cycles per byte of image.
Introduction
Lossless image compression algorithms are generally used for images that are documents
and when lossy compression is not applicable. Lossless algorithms are especially impor-
tant for systems transmitting and archiving medical data, because lossy compression of
medical images used for diagnostic purposes is, in many countries, forbidden by law.
Furthermore, we have to use lossless image compression when we are unsure whether dis-
carding information contained in the image is applicable or not. The latter case happens
frequently while transmitting images by the system not being aware of the images’ use,
e.g., while transmitting them directly from the acquisition device or transmitting over the
network images to be processed further. The use of image compression algorithms could
improve the transmission throughput provided that the compression algorithm complex-
ities are low enough for a specific system.
METHOD DESCRIPTION
Overview
Our algorithm is predictive and adaptive; it compresses continuous tone grayscale images.
The image is processed in a raster-scan order. Firstly, we perform prediction using a
predictor selected from a fixed set of 9 simple linear predictors. Prediction errors are
reordered to obtain probability distribution expected by the data model and the entropy
coder, and then output as a sequence of residuum symbols. For encoding residuum
symbols we use a family of prefix codes based on the Golomb–Rice family. For fast and
adaptive modeling we use a simple context data model based on a model of the FELICS
algorithm [19] and the method of reduced model update frequency [20]. The algorithm
was designed to be simple and fast. We do not employ methods such as detection of
smooth regions or bias cancellation. Decompression is a simple reversal of the compression
process. With respect to both time and memory complexity the algorithm is symmetric.
The algorithm described herein originates from an algorithm designed for images of
8-bit depth, which obtained high compression speed but could not be just simply extended
to higher bit depths [20]. The most significant differences between these algorithms are
reported in Section 2.6.
Prediction
To predict the intensity of a specific pixel X, we employ fast linear predictors that use
up to 3 neighboring pixels: the left-hand neighbor (A), the upper neighbor (B), and the
upper-left neighbor ©. We use 8 predictors of the Lossless JPEG algorithm (Table 1,
Pred0–Pred7) [9], and one a bit more complex predictor Pred8, that actually returns an
average of Pred4 and Pred7. Predictors are calculated using integer arithmetic. We select
a single predictor for the whole image, however for pixels of the first row and the first
column some predictors cannot be calculated—in this case we use simpler predictors (e.g.,
Pred2 for the first column).
The code family
The code family used is based on the Golomb–Rice (GR) family, i.e., on the infinite family
of prefix codes, that is a subset of a family described by Golomb [13] (Golomb family),
rediscovered independently by Rice [14]. GR codes are optimal for encoding symbols
from an infinite alphabet of exponential symbol probability distribution. Each code in
the GR family is characterized by a nonnegative integer rank k. In order to encode the
nonnegative integer i using the GR code of rank k we firstly encode the codeword prefix:
i/2k using a unary code, then the suffix: imod2k using a fixed length k-bit natural
binary code.
The data model
The modified data model known from the FELICS algorithm invented by Howard and
Vitter [19] is used. For prediction errors of pixels in the first column of an image a
prediction error of the above pixel is used as a context, for prediction errors of the
remaining pixels the preceding residuum symbol, i.e., a prediction error of pixel’s left-
hand neighbor, is used as a context.
The method of selecting code rank in the data model of the FELICS algorithm is fast
and simple. For each context we maintain an array of N counters, one counter for each
code rank k. Each counter stores the code length we would have if we used code of rank k
to encode all symbols encountered in the context so far. To encode a specific symbol in a
specific context we simply use the rank that in that context would give the shortest code
so far. After coding the symbol we update the counters in the current context. For each
code rank we increase its counter by the length of the codeword assigned to the encoded
symbol by code of this rank. Periodically, when the smallest counter in a specific context
reaches a certain threshold all the counters in this context are halved, causing the model
to assign more importance to the more recently processed data.
Although one symbol only is used to determine the context we use collective context
buckets. In the FELICS algorithm data model, for each context, at least one symbol has
to be encoded before we are able to estimate the code rank based on actual image data.
The first symbol in a given context, or a few first symbols, may be encoded using an
improper code rank. Since we deal with alphabet sizes up to 216 , the number of pixels
encoded in a non-optimal way may worsen the overall compression ratio. Furthermore,
due to an exponential prediction error probability distribution, some contexts may appear
in the whole image a couple of times only. For the above reasons we group contexts of
higher values in collective context buckets. In our case we maintain a single array of
counters for all the contexts contained in the bucket. The number of contexts contained
in the bucket grows exponentially in respect to the bucket number, starting with the
bucket containing the single context. This way we reduce the FELICS model memory
complexity of O(2N +1 ) to O(N 2 ).
Procedure
An HP Proliant ML350G3 computer equipped with two Intel Xeon 3.06 GHz (512 KB
cache memory) processors and Windows 2003 operating system was used to measure the
performance of algorithm implementations. Single-threaded application executables of
the described algorithm, and other algorithms used for comparisons, were compiled using
Intel C++ Compiler, version 8.1. To minimize effects of the system load and the input-
output subsystem performance on obtained results the executable was run several times.
The time of the first run was ignored and the collective time of other runs (executed for
at least one second, and at least 5 times) was measured and then averaged. The time
measured was a sum of time spent by the processor in an application code and in kernel
functions called by the application, as reported by the operating system after application
execution. Since we measure the execution time externally we actually include the time
of initializing the program by the operating system into our calculations; this time may
be significant for the smallest images.
Parameter selection for the algorithm
The parameter selection was based on the average compression speed and the average
compression ratio for images from the normal group. The threshold, that triggers dividing
all the counters in a certain context when the smallest counter reaches it, was selected
for each update frequency and for each number of buckets individually as the average
best value for predictors 1 to 8. This way we do not favor any specific update frequency,
predictor, or model structure. Knowing these parameters, however, we could simply use
a fixed threshold for all the update frequencies. Using for all the update frequencies the
threshold selected for the update frequency and the number of buckets of the default
parameter set listed below, would simplify the algorithm and change the compression
ratio, for some image groups only, by less than 0.1%. The remaining algorithm parameters
were selected by examining results of compression using combinations of all p values,
all numbers of buckets, all predictors, some values of d, and some code length limits
lmax . Parameter combinations which, compared to some other combination, resulted in
worsening of both the compression speed and the compression ratio, were rejected. One
of the remaining combinations was selected as the default parameter set, its use results in
the compression speed 20% less than the fastest one obtained and the compression ratio
worse by about 0.5%, compared to the best ratio.
CONCLUSIONS
The presented predictive and adaptive lossless image compression algorithm was designed
to achieve high compression speed. The prediction errors obtained using simple linear
predictor are encoded using codes adaptively selected from the modified Golomb–Rice
code family. As opposed to the unmodified Golomb–Rice codes, this family limits the
codeword length and allows coding of incompressible data without expansion. Code se-
lection is performed using a simple data model based on the model known from FELICS
algorithm. Since updating the data model, although fast as compared to many other
modeling methods, is the most complex element of the algorithm, we apply the reduced
model update frequency method that increases the compression speed by a couple of hun-
dred percent at the cost of worsening the compression ratio by about 0.5%. This method
could probably be used for improving speed of other algorithms, in which data modeling
is a considerable factor in the overall algorithm time complexity. The memory complexity
is low—algorithm’s data structures fit into contemporary CPUs’ cache memory.
The presented algorithm was compared experimentally to several others. For continu-
ous tone natural and medical images, on average, its compression ratio is by 5.8% worse,
compared to the best ratio obtained by CALIC. Its compression speed is over 2.5 times
higher than the speed of JPEG-LS. Compared to the CCSDS SZIP, i.e., to the algorithm
that does not employ adaptive data model, the presented algorithm obtains similar com-
pression speed, and by 4.5% better compression ratio.