Bio

Marcela is a senior student in computer science at Faculdade Farias Brito in Brazil, her home country. Currently, she is an exchange undergraduate student at Arizona State University. She has worked on projects related to computer graphics and operational research. She worked on application development for Android devices and PC applications. During the initial years in her bachelor’s degree, she developed an interest in quantum computing and she has been writing a final paper about logic simplifications application as a tool for quantum states separability analysis.

Other interests include playing guitar, watching TV series, and studying astronomy.

Project: Analysis of Image Processing Using Cellular Automata

Cellular Automata and Image Processing

Cellular automata can be used to reproduce traditional image processing filters such as the Fourier filter, the Gaussian filter, or a borders detector, for example. The image’s pixels are considered as a two-dimensional cellular automaton: at each step in the evolution, the color of each pixel depends on the colors of its neighbors according to the selected rule. The rules can be simple, symmetric functions of the neighborhood median or mean, or customized rules. In case of multilevel image, each level is mapped to a different CA state. It has been proved that cellular automata can be more efficient than traditional implementations of algorithms to reduce the noise in an image.

Methodology

In this project, grayscale images are used as input in cellular automata. The new colors of the cells (the color that they will have in the next step of the automata evolution) are based on the gray level of the immediate neighbors. It increases considerably the number of rules since 256 colors produce 256^(255x+1), where x is the number of neighbors. To select the neighbors, the von Neumann neighborhood will be used, given x = 9. This produces (10^5529) possible rules. Since it is not possible go through all these rules, the image level must be compressed in a lower number of levels. Within this approximation, random rules will be analyzed. It is equivalent of creating custom filters and masks and applying them to different images. The new images that will be considered are those generated in the last step of a determined number of steps of a CA evolution. As a result, it is expected that some interesting behavior will appear—border detection, noise reduction, etc. In addition, an analysis of the 3D generated structures will be performed, since two-dimensional cellular automata evolution can be represented in a 3D space. The analysis of the 3D representation can detect some pattern in the evolution of the cellular automata. Some variations, such as the change in the number of neighborhoods considered as well as the weight of the neighboring cells, can be considered in order to diversify the test results during the project execution.

Example: A possible application example is improving an image with salt-pepper noise. Many cellular automata rules will be tested and it will be observed if some of them improve the image, decreasing the impact of the noise. The is an experiment to analyze if random rules can produce advanced results useful for image processing.

Favorite Outer Totalistic r=1, k=2 2D Cellular Automaton

Rule 6