Classification of cellular automata through texture analysis

Autor(es)

da Silva, Nubia Rosa ; Baetens, Jan M. ; da Silva Oliveira, Marcos William ; De Baets, Bernard ; Bruno, Odemir Martinez

• Tipo de documento: Artigo Científico
• Fonte: INFORMATION SCIENCES; v. 370, p. 33-49, NOV 20 2016.
• Citações Web of Science: 2

Resumo

The spatio-temporal dynamics of cellular automata (CAs) has attracted the attention of researchers from different fields, mainly mathematics, computer science and engineering, as a consequence of both the intriguing spatio-temporal patterns that these dynamical systems evolve and the fact that they enable the modelling of complex natural phenomena. Yet, to this day, there are only a few studies that focus on the automated classification of cellular automata on the basis of the space-time diagrams they evolve. Here, we present an innovative approach to classify CAs according to Wolfram's classification scheme in an automated way by relying on texture descriptors that capture the nature of the evolved space-time diagrams. More specifically, we propose the use of one of two well-known texture descriptors, namely Local Binary Pattern Variance and Fourier descriptors, to generate features grasping the diagrams' nature, followed by nearest neighbor classification. The performance of this approach is assessed through a cross-validation and by analysing the percentage of pre-classified rules that is required to arrive at an acceptable success rate. The experiments involve the family of elementary CAs and four families of totalistic CAs with neighborhood radii ranging from one to three, and a state space consisting of up to three states. The results show the potential of our proposal with success rates varying between 65% and 98% depending on the size of the training set, which ranges from 10% to 90% of the rules in the CA family at stake. For totalistic CAs, this training set should be classified manually to start the process of automated classification. (C) 2016 Published by Elsevier Inc. (AU)

• Processo FAPESP: 11/01523-1 - Métodos de visão computacional aplicados à identificação e análise de plantas
• Beneficiário: Odemir Martinez Bruno
• Modalidade de apoio: Auxílio à Pesquisa - Regular
• Processo FAPESP: 11/21467-9 - Reconhecimento de Padrões Heterogêneos e suas Aplicações em Biologia e Nanotecnologia.
• Beneficiário: Núbia Rosa da Silva
• Modalidade de apoio: Bolsas no Brasil - Doutorado
• Processo FAPESP: 14/06208-5 - Análise de imagem de lignocelulose
• Beneficiário: Núbia Rosa da Silva
• Modalidade de apoio: Bolsas no Exterior - Estágio de Pesquisa - Doutorado