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

Fig. 1.5 General structure of a nonlinear map or automaton in a digital implementation
(discrete-time, finite precision of n bits). In the case of cellular automaton, each bit is as-
sociated with a cell. The nonlinear mapping F induces a structure of the state space which is
partitioned in attractors, each attractor may also collect “transient states” associated with its
basin of attraction. The complexity of attractors is proportional with their length (maximal
length is L =

2 n ) and average distance between consecutive states.

Good chaotic counters must rely on:

i) The existence of a dominant long attractor cycle with a length L as close
as possible to the maximal length i.e. N 2 n ; This property ensures that almost

all pixels in the original image are addressed. The existence of transients and of
many shorter cycles, imply some loss of pixels (samples) from the original message.
Recently, considering CA as a nonlinear dynamical systems [7] defined conservative
CA (definition applies to any automaton model as depicted in Fig. 1.5) as those
having the property that no state is a transient (or ephemeral) state . Both LFSR and
NLFSR (Linear or Non Linear Feedback Shift Register) used for long as pseudo-
random sequence generators have this property as well. The cellular automata in
this paper are conservative and consequently they have no transients;
ii) A “chaotic” character of the dominant longest cycle ; A very long cycle is
not necessarily a random one. A good counter-example is the counting automaton
used in the traditional raster scan of images. It has a maximal cycle length L

=

N but
the transition from one state to the consecutive one is rather smooth, often only one
bit is changing. As discussed above we are interested in pseudo-random counting
automata ensuring consecutive distant “jumps” between the coordinates of pixels.
To characterize such behaviours, in [18] we introduced a randomness measure that
may be conveniently computed. We are in particular interested on the randomness
of the dominant cycle . The measure of randomness was defined observing that in
a “chaotic” automata the average Hamming distance between consecutive binary
vector states (as given by the n cell outputs) becomes n/2 instead of 1 for counters.

=