Identification of Hybrid Cellular Automata Using Image Segmentation Methods
Y. Zhao, H.M. Guo and S.A. Billings
When given a complex cellular automata (CA) system, especially a real system, the transition rule over the whole evolution is often not uniform, which means that different spatial positions may have different rules at the same time. Currently, most methods for the identification of CA are only suitable for systems with uniform rules. Therefore, it is necessary to develop an algorithm which can detect the region with a specific rule or partition each region with different rules for a hybrid CA system. Current methods of identification could then be applied to each region to identify the CA model. By mapping the realistic CA pattern to a virtual image, this paper first introduces two popular image segmentation algorithms to aid the identification of hybrid CA.A popular nonlinear filter in image processing, the median filter, is then proposed to remove noise in the segmented image to avoid over-estimation. Two examples, including a one-dimensional and a two-dimensional CA system are then employed to demonstrate the algorithms. It is shown that the results are encouraging by comparing the original rule distribution graph and the detected rule distribution graph, and comparing the reconstructed patterns and the observed patterns.
Keywords: cellular automata, hybrid, image segmentation, identification, region growing, spatio-temporal