Final Report

We have reached the end of the course and this is our final post on this blog. CALIC, a Context-Based, Adaptive, Lossless Image Coding is finally implemented!! For the implementation of this click here. You may go through the video explaining the project as well. Click here to go to the entire folder. You can view our GitHub repo here.

ABSTRACT:

As discussed, we have implemented the encoder of CALIC (Context-Based, Adaptive, Lossless Image Coding), which is a famous codec for compression of continuous-tone images.  The implementation of this codec as part of a coursework is solely targeted for research work & experimental purposes. Our implementation is driven towards a more comprehensible and an over-simplified implementation of an already existing and powerful lossless image compression codec. As discussed in the paper, 8-bit grayscale images form a good testing set since they are computer generated continuous-tone images.

IMPLEMENTATION:

To keep in touch with new features and algorithms for required manipulations of image and its properties, the scikit-image library of python was used along with the NumPy module. We also made use of the ‘arcode’ package for Arithmetic coding of the current pixel based on the values of its 6 neighboring pixels (n, w, nn, ww, nw, ne). Entropy coding in the paper refers to either Arithmetic Coding or Huffman coding, since the particular pixel is always coded till the entropy limit. We chose to perform Arithmetic encoding over Huffman coding as Huffman encoding always results in rounding errors because its code length is restricted to multiples of a bit. Arithmetic coding, on the other hand, achieves a value which actually corresponds to the values mentioned theoretically as opposed to Huffman coding.

Overall an improvement in our implementation would be better error remapping, histogram tail truncation (to increase coding efficiency), and certain error feedback mechanisms that were missed out during the context formation and error estimation. We haven’t coded the decoder as well.

RESULT:

The test images used are basically 8-bit greyscale images that includes well-known images like Lena, Cameraman, and pirate, among several others. The level of compression was, however, not significant, as can be seen from the below graph:

Untitled

As can be seen, some images have a lesser degree of compression, and some are compressed relatively more, the ‘Moon’ here being at the highest degree. This is because while entropy coding of prediction errors, the main parts encoded are the number of occurrences of errors of a given context and the accumulator of errors, and both of these CALIC components remain of the same size always irrespective of the size and the quality of the image. Due to this reason, bigger images (such as Moon) face more compression gains than those whose size is smaller (Ex. Lena).

Note:

If you’ve gone through our output files, here’s the explanation of the files present:

The files with .calic extension are the files that are finally compressed.

The files with .craw extension store the error accumulator as well as the error count respectively.

ROLE OF MEMBERS:

01FB14ECS212 – Sanjay SS – Research in encoding schemes + Providing arithmetic encoding implementation + Image collection

01FB14ECS233 – Shreyash S Sarnayak – Gradient Adjusted Prediction + Error Energy Estimator + Error and Context Quantizer + Error Feedback & Sign Flipping

01FB14ECS241 –  Siddharth Srinivasan – Textual Context + Final Context Formation + Entropy coding according to binary/continuous mode

Advertisements

Coding the Gradient Adjusted Predictor

We’ve decided to use the scikit package in python to code the CALIC-based compression technique. The GAP predictor employed in CALIC is a simple, adaptive and a non-linear predictor, and compared to other linear predictors, GAP is more robust simply because it weighs the neighboring pixels of a given pixel I[i,j] of the input image according to the estimated gradients of the image. The code is pretty much straightforward with respect to the algorithm of generating the GAP image, which is as follows:

algogap-min

An extra get function is used to check if the pixel value is valid or not. If it is, the value is returned, and if it isn’t, 0 is returned, since the values of pixels outside the image are assumed to be zero.

Original Image I:

cman.jpg

Differential image î - I:

diff.png

Code:

CODING CONTEXT SELECTION AND QUANTIZATION

Just estimating GAP does not completely remove the statistical redundancy in the image. It is observed that the variance of prediction errors e=I-î strongly correlates to the smoothness of the image around the predicted pixel I[i,j].

To model this correlation at a small computational cost, we define an error energy estimator

delta-min.png

where dh & dv are scaling estimates of GAP and ew = I[i-1,j] - î[i-1,j] is the previous prediction error. We may include en = I[i,j-1] - î[i,j-2] in Δ. This makes Δ a slightly better error energy estimator, however a main disadvantage is with respect to memory, i.e. it requires buffering of an extra row of errors. Hence en is not recommended to be used. The coefficients a,b & c can be determined by standard linear regression so that Δ is the least squares estimator of error strength ‘e’. For algorithm efficiency, it is recommended to use a=b=1 and c=2.

Now Δ is quantized to a fixed number of levels, sayL , for better time & space efficiency. In practice, L=8 is found to be sufficient. We denote the Quantizer as a mapping (Q), where

Q: Δ -> {0,1,2,3,4,5,6,7}

The quantization criterion is to minimize the conditional entropy of the errors. In particular, the expression to be minimized is

min-min.png

where q1,q2…qn partitions Δ into ‘n’ levels.

Gradient Adjusted Prediction

Gradient Adjusted Prediction (GAP) is one of the main components that drives the CALIC image compression technique. It predicts the value at a pixel non-linearly by using its neighbouring pixels.

pix-min.png

It predicts the value at ? by using all the other 7 pixels in the image namely NN (North-North), NNE (North-NorthEast), NW (North-West), N (North), NE (North-East), WW (West-West), W (West).

Assuming

i1-min.png

Now we find the vertical and horizontal gradient dv and dh respectively like

Screenshot from 2017-03-11 17-41-25-min.png

Now based on these 2 factors we obtain what is known as a Gradient Adjusted Prediction (GAP) of the initial image I and this is denoted by I^. The procedure to calculate the GAP is as follows:

algogap-min.png

The predictor coefficients and thresholds given above were empirically chosen. Most coefficients are powers of 2 so that multiplications/divisions can be performed by shifting.

General Overview of CALIC

We’ve decided on taking up image compression so as to reduce the amount of redundant data stored by the image. We will be implementing image based compression based on this paper and we will commonly refer to this approach as “Context-Based, Adaptive, Lossless Image Codec”, or simply CALIC, as it is fondly called.

The codec seems to perform well as it guarantees a higher degree of lossless compression of continuous-tone images than other lossless image coding techniques. CALIC puts heavy emphasis on image data modeling, and it makes use of a large number of modeling contexts to condition a nonlinear predictor (gradient-adjusted predictor) and adapt the predictor to varying source statistics. As of 2000 CALIC is considered as a benchmark for lossless compression for continuous-tone images.

CALIC is a sequential coding scheme that encodes and decodes in order with a single pass through the image. The coding process uses prediction and context templates that involve only the two previous scan lines of coded pixels. Consequently, the encoding and decoding algorithms require a simple two-line buffer that holds the two rows of pixels that immediately precede the current pixel. CALIC operates in two modes: binary and continuous tone. Binary mode is for situations in which the current locality of the input image has no more than two distinct intensity values, hence it is designed for a more general class of images than the traditional class of black and white images. The system selects one of the two modes on the fly during the coding process, depending on the context of the current pixel. In the continuous-tone mode, the system has four major integrated components: gradient-adjusted prediction (GAP), context selection and quantization, context modeling of prediction errors, and entropy coding of prediction errors. A gradient-adjusted prediction Î of I is made, and the predicted value is further adjusted via an error feedback loop of one-step delay, which results in an adaptive, context-based, nonlinear prediction Ĩ.

calic
Schematic description of CALIC’s encoder

The residue of the predictor Ĩ is entropy-coded based on eight estimated conditional probabilities in eight different contexts called “coding contexts”. These contexts are formed by quantizing a random variable “error energy estimator” into 8 bins which act as classifiers for the range of expected magnitude of error (The procedures are identified by the blocks “Context Quantization” & “Conditional Probabilities Estimation” in the previous figure depicting a schematic view of the encoder).

calica-min-1
Broad overview of CALIC coding procedure

We will continue to add more posts to explain various components of the CALIC codec, i.e, Gradient Adjusted Prediction (GAP), Coding Context Selection, Context Modelling of Prediction Errors, Error Feedback, etc.

First Post

Hi! This blog is maintained by 3 peeps, and we ensure that we finish off our Image Compression Project as smoothly as possible. We are still on the verge of choosing a suitable standard for image compression. Any suggestions are welcome. Please post your suggestions on the comments section below.

Edit:- The comments section is not available as of now. Sorry for the inconvenience.