Research Institute of Visual Computing

Select a project of interest using the advanced search:

Fast Rule Identification and Neighborhood Selection for Cellular Automata

Authors:  Xianfang Sun,  Rosin, P.L.,  Martin, R.R.

DOI: 10.1109/TSMCB.2010.2091271

Abstract:

Cellular automata (CA) with given evolution rules have been widely investigated, but the inverse problem of extracting CA rules from observed data is less studied. Current CA rule extraction approaches are both time consuming and inefficient when selecting neighborhoods. We give a novel approach to identifying CA rules from observed data and selecting CA neighborhoods based on the identified CA model. Our identification algorithm uses a model linear in its parameters and gives a unified framework for representing the identification problem for both deterministic and probabilistic CA. Parameters are estimated based on a minimum variance criterion. An incremental procedure is applied during CA identification to select an initial coarse neighborhood. Redundant cells in the neighborhood are then removed based on parameter estimates, and the neighborhood size is determined using the Bayesian information criterion. Experimental results show the effectiveness of our algorithm and that it outperforms other leading CA identification algorithms.

Link to Paper

Authors

Dr Xianfang Sun

Dr Xianfang Sun

Graphics, image processing, computer vision, and pattern recognition. Seek to apply advanced control theory and methodology in visual computing.

Prof. Paul Rosin

Prof. Paul Rosin

Various aspects of computer vision, including 2D and 3D facial analysis and synthesis.

Prof. Ralph Martin

Prof. Ralph Martin

Polygon mesh processing including registration, noise removal, segmentation and surface fitting.