Cellular Automata Evolution for Pattern Recognition
Jadavpur University, 2005.
Supervisor Prof. Parimal Pal Chaudhuri,
Professor Emeritus
Department of Computer Science and Technology
Bengal Engineering College, Shibpur, Howrah, INDIA
Co-Supervisor
Prof. Debesh K. Das, Professor
Department of Computer Science and Engineering
Jadavpur University, Kolkata, INDIA
Abstract
Study of Cellular Automata (CA) as a modeling tool has
received considerable attention in
recent years. Researchers from different fields -
image processing, language recognition,
pattern recognition, VLSI testing etc - have proposed CA
based models for different applications.
However, the research community from diverse disciplines
looks forward for a versatile and robust
CA based modeling tool to study physical systems observed in nature
around us or designed artificially.
Following two objectives need due consideration to build such a tool.
1. The analytical framework to derive
the global dynamics of the CA from the local rules; and
2. inversely, to derive the local rules of the desired CA
simulating the global behavior of the system to be modeled.
The thesis realizes these two objectives for a specific application
domain. It presents
analysis and synthesis framework of
a special class of linear CA termed as
Multiple Attractor CA (MACA). This class of CA employs only
XOR logic as the next state function of a cell.
The thesis addresses a number of open problems associated with MACA
characterization.
The new characterization has provided the foundation for MACA synthesis
in O(n) time complexity where n is the number of CA cells.
The synthesis framework is supported
with genetic evolution
to arrive at the desired local rules of a CA modeling a global function.
The versatility
of the proposed model has been derived from
three basic frameworks - analysis, synthesis, and genetic evolution.
The MACA based modeling tool
is next employed to address pattern recognition problem.
The thesis presents the design and application of MACA based
pattern classifier in diverse fields like
data mining, image compression, fault diagnosis, etc.
The evolution
scheme is next extended for non-linear CA synthesis.
Such a CA employs all types of next state
function (linear/additive/non-linear) for a CA cell.
The non-linear CA is explored
for modeling associative memory.
An in-depth study of non-linear
CA state space is also reported.
Solutions of many real life problems display
fuzzy characteristics. In this context,
the last section of the thesis introduces Fuzzy CA (FCA) -
the CA that employs fuzzy logic as next state function.
The application of FCA has been demonstrated
in the field of pattern recognition/classification.