The chapter describes a brief history of the emergence of the theory of cellular automata, their main properties, and methods for constructing. The image skeletonization methods based on the Euler zero differential are described. The advantages of using hexagonal coverage for detecting moving objects in the image are shown. The software and hardware implementation of the developed methods are presented. Based on the obtained results, a hexagonal-coated cellular automata was developed to identify images of objects based on the Radon transform. The method and mathematical model of the selection of characteristic features for the selection of the skeleton and implementation on cellular automata with a hexagonal coating are described. The Radon transform allowed to effectively extract the characteristic features of images with a large percentage of noise. An experiment for different images with different noises was conducted. Experimental analysis showed the advantages of the proposed methods of image processing and extraction of characteristic features.
TopThe Historical Development Of The Parallel Computing Paradigm Of Ca
Due to the fact that the CA were repeatedly invented under different names, in many countries by people working in different fields of science, the terms “iterative arrays”, “computing spaces,” “homogeneous structures” and “cellular automata” are practically synonymous. At the same time, under one term (“cellular automaton”), there were different concepts. In pure mathematics, they can be found as one of the sections of topological dynamics, in electrical engineering they are sometimes called iterative arrays.
It is generally accepted that the concept of “cellular automata” (CA) was introduced in the late 40s of the last century by John von Neumann from Stanislaw Ulam works as formal models of the self-reproduction of organisms.
When Stanislaw Ulam began his research (Ulam, 1952), he could hardly imagine that, based on his ideas, an outstanding American scientist John von Neumann would introduce the concept of “cellular automaton”.
Despite the fact that von Neumann was a mathematician and a physicist, the idea came to him when constructing an explanation of certain objects of biology. He used cellular automata that to create the more plausible models of spatially extended systems. Indeed, the mechanisms of self-reproduction structures on the cellular automaton that were proposed by them strongly resemble the regularities discovered in the next decade in biological systems are observed. The results of von Neumann's research are given, in particular, in the fundamental work (Neumann, 1951, Neumann, 1966). Its first edition appeared in 1966, while the author died in 1957. His student Arthur Burks, who became a famous specialist in the field of cellular automata, completed the book.
However, much earlier, at the end of the Second World War, while von Neumann was creating one of the first electronic computers, German engineer Konrad Zuse proposed a number of ideas that would make him one of the founders of the theory of parallel computing. His ideas at once became widely known.
Among other things, Zuse came up with “computational spaces” - CA (Zuse, 1969). His special interest was caused by the application of these systems to problems of numerical modeling in mechanics. Unfortunately, the situation in the world prevented the work of the scientist from obtaining propagation, while the work of von Neumann was watched by the entire scientific world.
Mathematicians came to cellular automata, considering iterative transformations of spatially-distributed structures with a discrete set of states (Hedlung, 1969). So there were appear “iterative arrays”.
Immediately began to arise solutions to important theoretical problems in this area, for example, issues of reversibility, computability, attainability, etc.
In the group of computer logic at the University of Michigan, John Holland first used cellular automata to solve problems of adaptation and optimization (Holland, 1966).
Unfortunately, lack of discussions and of the common terminology led to a significant duplication of works. So the important characteristics of cellular automata, proved by Richardson [6] on twenty pages in the continuum substitution in the topology of Cantor sets, could be written in two lines as a consequence of the previous work of Hedlund (Hedlung, 1969).
The concept of “homogeneous structures” (Wolfram, 1986; Adamatzky, 1994; Adamatzky, 2010; Twelfth International Conference on Cellular Automata for Research and Industry, [ACRI 2016]) is extremely close to “cellular automata” in its origin and designates their hardware implementation, in which the key property of these systems is their homogeneity.