Cellular Automata Evolution for Pattern Recognition

Jadavpur University, 2005.

Prof. Parimal Pal Chaudhuri, Professor Emeritus
Department of Computer Science and Technology
Bengal Engineering College, Shibpur, Howrah, INDIA

Prof. Debesh K. Das, Professor
Department of Computer Science and Engineering
Jadavpur University, Kolkata, INDIA

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.


  Home | Publication | Awards | BIB Lab