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

(next abbreviated “Rx”) or storage medium with an efficient use of the bandwidth
or storage memory. In addition, in order to maintain data security certain encryption
algorithms may be also used. The problem as stated above is usually approached by
various methods form the mature areas of image and video compression and cryp-
tography. Yet, some applications require low power consumption and consequently
a simple mechanism is needed for encoding and decoding processes.
Cellular automata (CA) hold the promise [25] [6] [5] of a very convenient way
to achieve both compression and encryption with the benefit of using simple cir-
cuit models leading to low power consumption, as often desired when the source of
signal is a stand-alone sensor unit powered by battery or/and solar energy. In cryp-
tology, cellular automata are widely used [8], patents on cellular-automata random
number generators being among the first associated with CA applications [31].
In this chapter recent research results in this area are summarized, within a gen-
eral compression framework depicted in Figure 1.1. The particularity of our ap-
proach is to exploit complex dynamics emerging in Boolean cellular automata for
various tasks in compression and encryption, usually approached with computa-
tionally intensive algorithms using various arithmetic operations such as cosine and
other kind of transforms, multiplications etc. Locating useful emergent behaviors in
CA and their potential applications are topics described in more detail in [12] and
in a series of recent papers [13] [17].
The use of cellular automata in various stages of the compression and decom-
pression phases allows the avoidance of arithmetic operators such as multiplication,
summation etc. with a dramatic impact on the architectural complexity of the al-
gorithms implementation. Within this paper only the case of lossy compression is
considered, which is effective for image and video content associated to the mes-
sage. Also the focus is on algorithms that would lower the complexity of the Tx unit
(often a stand alone smart sensor with critical power consumption requirements).
As seen in Figure 1.1, in order to compress the string x t two stages (depicted here
as A and B) will be considered. As detailed next, they can be applied independently
(i.e. A only, or B only) or consecutively. In stage A, the redundancy present in the
original message is exploited to reduce the number N of original samples (i.e. im-
age pixels) into a smaller K number of representative samples. In the corresponding
A-stage of the receiver (Rx), the missing samples are recovered (with a certain loss)
using various interpolation schemes. Stage A is reminiscent of the compressive sam-
pling approach but the similarity is only at the functional level; while compressive
sampling approaches produce the K

− sized vector s k as the result of multiplying the

message with an N K matrix with random (non-binary) elements, our approach

dubbed “chaotic scan” [19] simply picks some samples from the original message
without performing any arithmetic operation at all. It is the role of a cellular automa-
ton to select (by addressing) the K samples from the original message, as it will be
detailed in Section 1.2. Consequently, a highly intensive computational algorithm
(usually embedded into a sensor with low power consumption requirements) is re-
placed now with a much simpler implementation of a CA with n

×

log 2 N cells
addressing the selection of K samples. In terms of FPGA implementation each CA
cell is allocated to one single LUT (basic computational unit in FPGA), a far more

=