Cellular Automata for Efficient Image and Video Compression - Cellular Automata in Image Processing and Geometry - page 19

Fig. 1.14 Generating a CA codebook via a learning mechanism and its use in a CA-VQ
compression scheme

As seen in Fig. 1.14, for a particular choice of the codebook size D = 16

= × ×

and block size m 16 (4 4 window) the running of the 16 16 CA with

= =

ID 4276938880 for T 10 iterations would reveal the codebook. A zoom of both

×

the original image (512 512 pixels) and the recovered one using this codebook

for the most significant 4 bit-planes shows the typical losses of this compression
scheme. The PSNR is about 25 dB and the quality of the image is acceptable given
the rate of 1 bit per pixel. Further optimization of performance is still possible, for
instance the use of different, optimized codebooks, for each bit-plane, or a different
learning scheme.
In terms of computational complexity, the CA-VQ approach requires more com-
putational effort in the encoding stage and less effort in the decoding stage. It is an
opposite situation from the case of chaotic scan compression. For a message with
N bits and a particular bit rate (codebook size D and block size m ) assuming that
the codebook is calculated and stored, the compression process requires compar-
isons (between blocks and code-words in the codebook) being more effective for
large block sizes and small dictionaries (also ensuring highest compression but low-
est reconstruction quality). The above compares not so favorably to simply reading
K N samples in the chaotic scan method. But on the other hand, the complexity of

the CA-VQ compression process still remains linear in the number of pixels, being
much lower than for traditional compression methods. The decompression stage in
CA-VQ is m times faster (i.e. N

<

/ m operations of reading the codebook) and involves