In a resolution scalable image coding algorithm, a multiresolution representation of the data is often obtained using a linear filter bank. Reversible cellular automata have been recently proposed as simpler, nonlinear filter banks that produce a similar representation. The original image is decomposed into four subbands, such that one of them retains most of the features of the original image at a reduced scale. In this paper, we discuss the utilization of reversible cellular automata and arithmetic coding for scalable compression of binary and grayscale images. In the binary case, the proposed algorithm that uses simple local rules compares well with the JBIG compression standard, in particular for images where the foreground is made of a simple connected region. For complex images, more efficient local rules based upon the lifting principle have been designed. They provide compression performances very close to or even better than JBIG, depending upon the image characteristics. In the grayscale case, and in particular for smooth images such as depth maps, the proposed algorithm outperforms both the JBIG and the JPEG2000 standards under most coding conditions.

Spatially scalable image coding algorithms are mostly based on linear filtering techniques that give a multi-resolution representation of the data. Reversible cellular automata can be instead used as simpler, non-linear filter banks that give similar performance. In this paper, we investigate the use of reversible cellular automata for lossy to lossless and spatially scalable coding of smooth multi-level images, such as depth maps. In a few cases, the compression performance of the proposed coding method is comparable to that of the JBIG standard, but, under most test conditions, we show better compression performances than those obtained with the JBIG or the JPEG2000 standards. The results stimulate further investigation into cellular automata-based methods for multi-level image compression.

In this work, we have designed an efficient arithmetic coder for the non-linear bi-level image coder based on reversible cellular automata transform reported in the work of Cruz-Reyes and Kari (2008). The proposed approach relies on non-linear transform operations based on RmbCA, decomposing the image into four subimages (named LL, LH, HL, HH in lexicographic order) in such a way that the LL subimage represents a low resolution version of the original image. Performing an edge detection on this subimage, it is possible to identify the coordinates where there is a high probability that the other subimages present a black pixels. In this way it is possible to minimize the amount of data that have to be processed reducing the coded bit stream. In order to increase the probability that black pixels lie in the selected region, the coding algorithm enlarges the identified region according to the values of Sobel operators computed on the LL subimage.