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

Fig. 1.1 A general framework for message compression and recovery

effective solution than implementing the matrix multiplication required by the com-
pressive sampling approach. It was shown [19] that using a ratio K

5% ensures
a decent recovery of the original signal, while preserving the most important features
of the image (or video sequence). Consequently a compression of up to 20 times can
be achieved in the A-stage of the encoder with very little computational effort. More
computational effort is required in the A-stage of the Rx unit [19] [16] but in most
applications of interest the Rx is usually implemented on a desktop computer with
no critical requirementes, while the Tx is often an autonomous low-power sensor
where the issue of low complexity is critical.
An identical CA structure as the one used to scan the original message is required
in the Rx unit. In order to ensure the correct recovery of information, the CA in the
Rx unit must evolve (as a dynamic system) in synchrony with the CA used in the
Tx unit. This property is supported, as recently was demonstrated [14] by a proper
choice of particular CA rules. Such CA rules ensure both binary synchronization
and longest cycle properties . Binary synchronization means that the entire state of
the CA ( n bits addressing the t sample of the original message) can be recovered
from one single bit per clock received from the Tx CA. Among various chaos syn-
chronization schemes [24] [27] presented in the literature this one is the most robust
and requires the less synchronization information. The longest cycle property means
that eventually all (or almost all, with an insignificant loss of samples) N samples
of the original message are addressed (much like a counting automaton, except the
pseudo-random ordering or scan) ensuring that, if desired, all information from the

/ N =