Context-based adaptive lossless image codec (CALIC) is one of the most efficient lossless encoding techniques for both continuous-tone and binary images. This Paper includes a research on how to modify CALIC algorithm in continuous-tone mode by truncating tails of the error histogram and using an escape mechanism to code the errors beyond the truncated code range, if they occur which improve CALIC compression performance.
Also, we are going to propose a modification to CALIC in binary mode by eliminating error feedback mechanism. This minor modification should improve CALIC performance in binary images.

Extrait

IMPROVING CALIC COMPRESSION PERFORMANCE ON BOTH CONTINUOUS-TONE AND BINARY IMAGES

Mohamed El-Ghoboushi*, Amin Nassar**

*Post graduate student, **Professor

Electronics and Electrical Communications Department

Cairo University, Faculty of Engineering, Giza, Egypt

mgobushi@yahoo.com

ملخص البحث:

ضغط الصور يعمل على تصغير أحجام الصور الرقمية مع الحفاظ على جـودة الصورة. ويتحقق ذلك من خلال تطبيق أساليب ضغط البيانات. فعند تقليل حجم الصـــورة يكون هناك فقدان فى جودة الصورة أو لا. العمل المقدم هنا يبين ضغط الصور مع الحفاظ على جودتها باستخدام الترميز عـلى أساس النمذجة بالقرائن الغير مؤثرة على جودة الصور (الكاليك) وقـــد أظهرت النتائج أن ضغط الصور باستخدام الكاليك يوفر أعلى نسبة انضغاط من التقنيات الاخرى عند التجربة على الصور الطبيعية فى وقت قصير. فى هذا البحث نوضح كيف يمكن تعديل الكاليك للحصول على نسبة انضغاط أعلى مع الحفاظ على مساحة الذاكرة المستخدمة اذا كنا نتعامل مع الصور الطبيعية وكذلك تحسين نسبة الانظغاط بمتوسط 6,208 % فى حالة الصور الثنائية.

ABSTRACT

Context-based adaptive lossless image codec (CALIC) is one of the most efficient lossless encoding techniques for both continuous-tone and binary images. This Paper includes a research on how to modify CALIC algorithm in continuous-tone mode by truncating tails of the error histogram and using an escape mechanism to code the errors beyond the truncated code range, if they occur which improve CALIC compression performance. Also, we are going to propose a modification to CALIC in binary mode by eliminating error feedback mechanism. This minor modification should improve CALIC performance in binary images .

Keywords : CALIC, Lossless Image Compression, Compression Ratio, Error Feedback, Binary mode, Continuous-tone Mode.

. INTRODUCTION

The assignment of compression is to code the image data into a compact form, minimizing both the number of bits in the representation, and the distortion caused by the compression.

There are two major approaches in the image compression field, which are lossless and lossy. A compression algorithm is “lossless” (or reversible) if the decompressed image is identical with the original. Respectively, a compression method is “lossy” (or irreversible) if the reconstructed image is only an approximation of the original one [2, 7]. The compression scheme presented in this Paper is a Lossless.

Predictive encoding is a major class of encoding scheme that is utilized in lossless compression. Context-based predictive [1] is a kind of adaptive predictive encoding, In which pixels are classified into different classes (a.k.m contexts) based on pixel neighborhood characteristics [8-14].

A suitable predictor for each context is adaptively selected and utilized for each context. As adaptive model changes the symbol probabilities during the compression process in order to adapt the statistics during the process [1]. Initially the compression process starts with an initial model, then during the process, the model adapts by the symbols, which have been transmitted already. Also, the decoder needs to be able to adapt the model in the same way later at the decompression process.

CALIC [1-3, 5-6][9-12] is an efficient context-based lossless image encoding technique. But it actually utilizes different size of entropy coding model to encode the prediction error ε based on different context error energies δ. Hence, even after error remapping, an alphabet size of 2z is still unnecessarily large.

Large errors occur with diminishing frequency or not at all. But they still occupy spots in code space. If an error histogram of size 2z is used, it will significantly reduce efficiency of entropy coding by distorting the underlying error statistics.

Hence, In this Paper we propose a modification by truncating the tails of the error histogram that is used to estimate the probability p (e | δ), and using an escape mechanism to code the errors beyond the truncated code range, if they occur should improve CALIC performance in continuous-tone mode.

Also, CALIC attempts to solve binary image performance problem by incorporating a binary mode to deal with image regions with no more than two distinct grey levels. Unfortunately, when any pixel to be encoded has a different grey level than any of neighboring pixels, CALIC switches the algorithm to continuous-tone mode. This leads to downgrade the performance due to the error feedback step.

This paper is organized as follows: Section 2 gives an overview of CALIC algorithm and how it works, and discussing our proposed modifications of CALIC, Section 3 discusses our experimental work and results, respectively, and finally Section 4 offers our conclusion.

2. OVERVIEW OF CALIC

CALIC is a one pass context-based adaptive predictor scheme [2, 5]. CALIC operates in two modes: binary and continuous tone modes. The system selects one of the two modes on the fly during the coding process, depending on the context of the current pixel [9].

2.1 Continuous-tone mode

In continuous-tone mode, the neighborhood of the pixel to be encoded has more than two distinct grey levels. In this mode CALIC algorithm performs four operations [2, 5]:

a) Initial prediction,
b) Context classification [12],
c) Error feedback, and
d) Entropy encoding.

The initial prediction is obtained for the pixel to be encoded using Gradient Adjusted Predictor (GAP). GAP is a simple non-linear predictor that utilizes gradients at pixel neighborhood.

In context classification, each pixel is classified to one of the 576 predefined contexts. The context selection is based on comparing the value of the initial prediction with the pixel neighborhood’s values.

For each context, CALIC assumes that the GAP predictor [2,4][5] is consistently repeating a similar prediction error. To compensate for this error, CALIC incorporates an error feedback stage [9], at which a bias value is added to the initial prediction. This bias value is the expectation of the prediction errors at the pixel’s context.

Prediction errors are entropy encoded [11] using arithmetic encoder that utilizes context conditional probabilities, i.e., P(error|context) [9,15][16].

Unfortunately, CALIC utilizes different size of entropy coding model to encode the prediction error ε based on different context error energies δ. Hence, even after error remapping, an alphabet size of 2z is still unnecessarily large.

Large errors occur with diminishing frequency or not at all. But they still occupy spots in code space. If an error histogram of size 2z (where z is No. bits) is used, it will significantly reduce efficiency of entropy coding by distorting the underlying error statistics.

2.1.1 Proposed Modification of continuous-tone mode

Truncating the tails of the error histogram that is used to estimate the probability p (e | δ), and using an escape mechanism to code the errors beyond the truncated code range, if they occur should improve CALIC performance in continuous-tone mode.

- First we limit the size of each conditional error histogram to some value N δ based on the error energy level 1≤ δ < L.

Where, L is error energy level

- Second, For a given coding context δ, a symbol (remapped prediction error) x ≤ N δ is encoded first to be N δ -1, followed by the codeword for the new symbol x - (N δ -1), but being encoded under the coding context δ + 1.

- The whole idea actually is similar to the post office will use different boxes to contain different parcels. And since we don't know the parcel size for time being, so we first classify them by their estimated weight. Then if the parcel is oversize for the prescribed box of its estimate weight level, a larger box will be used.

2.2 Binary Mode

This mode is considered when a pixel's neighborhood has no more than two distinct grey levels [13]. It encodes the pixel's value directly from neighboring pixel values giving the code stream.

Unfortunately, when any pixel to be encoded has a different grey level than any of the neighboring pixels, CALIC triggers an escape sequence that switches the algorithm to continuous-tone mode. Hence, in this case the pixel will be treated as if it was in a continuous-tone region and then it will be encoded using GAP initial predictor and error feedback scheme.

2.2.1 Proposed Modification of binary mode

Using feedback mechanism in case of entering the continuous-tone mode as a result of an escape sequence triggered in binary mode may lead to decreasing the compression ratio.

Hence, we suppose to eliminate the positive feedback mechanism in this case only. This minor modification should improve CALIC performance in binary images. So we can use a conditional feedback in the overall system that allow using feedback mechanism in a continuous-tone mode and eliminate the feedback mechanism in case of entering the continuous -tone mode as a result of an escape sequence triggered in binary mode as shown in Fig. 1.

If the binary image has a different grey level than the two distinct levels of the neighboring pixels (i.e. T=2 where T is called symbolization.) the algorithm will eliminate feedback mechanism and code the error through the entropy coder directly. Otherwise, activate the continuous-tone mode with feedback mechanism.