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

used for the usual synthesis steps. The same code may be used for FPGA designs as
well as for dedicated VLSI chips. The CA-description module inputs a description
of the CA (neighborhood size, rule, mask, number of cells, etc.) in a user-friendly
manner and generates VHDL modules to be used in various hardware implementa-
tions of the above mentioned algorithms. The key issue in generating the most im-
portant part of the VHDL code is the very good correspondence between the ANF
description and the possibility to express it in a few VHDL line codes. A particular
example is give next: A one-dimensional CA is defined as having 7 cells, a certain
mask vector (1100010) and ID=101. The resulting VHDL line describing the entire
HCA is:
REG<= “1111111” xor c xor a xor (b and a) xor mask;
The above corresponds to the following particular form of the ANF representa-
tion:

y = 1 ↕ u 3 ↕ u 1 ↕ u 2 u 1 (1.5)

The above variable REG represents the entire CA array and the variables a,b,c
are constructed to represent shifted versions of REG according to specific neighbor-
hood to be implemented.
So far the CA-description module can implement either 3-cell neighborhoods or
5-cell neighborhoods for the HCA model (the traditional, homogeneous CA model
is a particular case of HCA with all 0 elements in the mask vector). Various FPGA
target devices were considered and in all cases the resulted implementation was
found to be very efficient. For instance, in the case of Xilinx FPGA's 1 LUT was
assigned for HCA designs with up to 3 inputs and mask vector while 2 LUTs suf-
fice to implement an entire cell (including its local memory) in the maximal case
considered so far of 5 cell neighborhoods. Similarly, for FPGA devices from Altera
(Cyclone II EP2C35F672C6 device on the DE2 board provided by the University
Program) one basic computational unit (LE - logic element) is assigned for 3-inputs
HCA cells and 2 times more for the case of 5-inputs. Note the very efficient allo-
cation of one cell per FPGA logic register. The above results confirm that cellular
automata with very large number of cells ( n 33216 in the case of the chip on the

DE2 board) can be easily realized in low cost series FPGA. The same VHDL de-
scription may be used to generate part of specialized sensor chips (e.g. in addition
to low power image sensors e.g. [22]) using an ASIC design flow.

=

References

1. Baraniuk, R., Cevher, V., Duarte, M., Hedge, C.: Model-based compressive sensing.
IEEE Trans. Inform. Theory 56, 1982-2001 (2010)
2. Baron, D., Sarvotham, S., Baraniuk, R.G.: Bayesian compressive sensing via belief prop-
agation. IEEE Trans. Signal Process. 58, 269-280 (2010)
3. Bruckstein, A.M., Holt, R.J., Netravali, A.N.: Holographic representation of images.
IEEE Trans. Image Processing 7, 1583-1597 (1998)
4. Candes, E., Romberg, J.: Practical signal recovery from random projections. In: Proc.
SPIE Conf., Wavelet Applications in Signal and Image Processing XI (2005)