The cellular automaton is an abstract model of computation. Investing the capabilities of cellular automata in image processing has proved to be promising. This paper presents a method for edge detection of images based on two dimensional cellular automata with extended Moore neighborhood model. This method uses ant colony optimization (ACO) to find the best linear rules of CA that produce satisfactory edge detection in one-time iteration. The performance of this approach is compared with some existing edge detection techniques. This comparison shows that the proposed method to be very promising for edge detection on various images with good quality and significantly low execution time.
In the contemporary era, there is a wealth of data available, and a significant portion of this data comes in the form of images. These can include things like DNA microarrays, satellite maps, astronomy observations, and many others. Image processing has played a critical role in the technological advancements of recent years and has become a valuable tool in a variety of scientific research fields, including health, industry, and astronomy. This type of processing is primarily concerned with enabling machines to interpret and analyze images, extracting important information in the process. Among these preprossecing operations, segmentation represents a crucial process in image processing, and it involves various techniques, one of which is edge detection. One of the primary objectives of edge detection is to reduce the data size to be processed in subsequent stages of image processing. Although there are many edge detectors available in literature, none of them are perfect, and achieving optimal edge detection that produces high-quality edges while minimizing processing time is an area that requires ongoing research and development. The present work is a contribution to this ongoing quest for improved edge detection techniques. Many research works focus on finding increasingly eficient segmentation techniques to optimize the quality of contours and reduce computation time.In this study, our focus is on modeling an image with a powerful and complex system, the cellular automaton, which we combine with the metaheuristic ACO to extract transition rules that enable good contour segmentation. The present paper is organised as follows: In the first section, we introduce the working context and the domains of interest that we focus on. In the second section, we provide some fundamental concepts about cellular automata. In the third section, we explain the concept of ant colony algorithm. In the fourth section, we cite some related works. In the fifth section, we detail how we used the ACO algorithm to optimize a CA for the task of edge detection. In the sixth section, we explain the execution of ACO algorithm. In section seven, experimental results are shown, both visual and numerical, and a comparison is done. In section eight, we conclude with a summury and future prospects.
The popularity of cellular automata can be attributed to their simplicity and their ability to model complex systems, despite the fact that they are simple. Essentially, cellular automata can be considered a basic model of a decentralized extended system composed of numerous individual components, or cells. The interactions between these cells are limited to local interactions, and each cell has a specific state that evolves over time based on the states of its neighboring cells. Overall, this structure can be regarded as a parallel processing mechanism. Remarkably, even though the structure of cellular automata is straight-forward, when iterated numerous times, it can generate intricate patterns that have the potential to simulate a plethora of complex natural phenomena. A cellular automaton is a dynamic system comprising of a grid pattern, with each cell within this pattern being assigned a state from a finite pool of states. The system evolves in discrete time steps, with the state of a cell at time ’t+1’ being dependent on the states of a limited number of neighboring cells, as dictated by a specified transition rule. Every iteration of the system operates through the application of the same set of rules to every cell in the grid, thus generating a new ’generation’ of cells entirely based on the prior one [1].
In the early 1990’s, Marco Dorigo and his team introduced the pioneering Ant Colony Optimization (ACO) algorithm, inspired by the behavior of ant colonies [2]. Ants are social insects that operate with the objective of advancing the survival of their colonies instead of focusing solely on the survival of individual ants. The ACO algorithm takes inspiration from the pervasive foraging behavior exhibited by ants to achieve their colony’s goals. At the crux of their behavior lies indirect communication among the ants via chemical pheromone trails, which function to guide them toward the shortest paths between food sources and their nest. When ants forage for food, they initially move in random directions, leaving a trail of chemical pheromone behind. The pheromones attract other ants who, in turn, select paths with strong pheromone concentrations. Once an ant finds food, it evaluates its quality and quantity before carrying it back to the nest, leaving pheromones behind that reflect the quality and quantity of the food found. These pheromone trails attract other ants towards the food source, thus enabling the ants to discover the shortest paths between their nest and the food source. The success of ACO algorithms lies in their ability to operate eficiently on large problem instances with multiple solutions that require optimization. By exploiting the characteristics of real ant colonies, ACO algorithms ofer unique and efective solutions to various discrete optimization problems. The collective behavior exhibited by real ant colonies has inspired the development of swarm intelligence techniques, such as the successful strand of ACO algorithms. These algorithms mimic the behavior of real ant colonies in their search for optimal solutions to discrete optimization problems. The utilization of real ant colony characteristics has enabled the development of efective and eficient multi-agent systems. Nonetheless, further research may be required to address the challenges of ACO algorithms to achieve optimal solutions for complex optimization problems.
The general steps of ACO algorithm are as follows [2] :
* On each iteration or epoch, all ants build a path to the destiny node (the food source). For the next
node selection, the probabilistic equation (
⎧ ()
() = ⎨ ∑︀∈ ( () ∈
⎩ 0ℎ
(
Informally, an ACO algorithm can be imagined as the interplay of three procedures [17]: ConstructAntsSolutions, UpdatePheromones, and DaemonActions. • ConstructAntsSolutions manages a colony of ants that concurrently and asynchronously visit adjacent states of the considered problem by moving through neighbor nodes of the problem’s construction graph. They move by applying a stochastic local decision policy that makes use of pheromone trails and heuristic information. In this way, ants incrementally build solutions to the optimization problem. Once an ant has built a solution, or while the solution is being built, the ant evaluates the partial solution that will be used by the UpdatePheromones procedure to decide how much pheromone to deposit. • UpdatePheromones is the process by which the pheromone trails are modified. The trails value can either increase, as ants deposit pheromone on the components or connections they use, or decrease, due to pheromone evaporation. From a practical point of view, the deposit of new pheromone increases the probability that those connections that were either used by many ants or that were used by at least one ant and which produced a very good solution will be used again by future ants. Diferently, pheromone evaporation implements a useful form of forgetting: it avoids a too rapid convergence of the algorithm toward a suboptimal region, therefore favoring the exploration of new areas of the search space. • Finally, the DaemonActions procedure is used to implement centralized actions which cannot be performed by single ants. Examples of daemon actions are the activation of a local optimization procedure, or the collection of global information that can be used to decide whether it is useful or not to deposit additional pheromone to bias the search process from a nonlocal perspective. As a practical example, the daemon can observe the path found by each ant in the colony and select one or a few ants (e.g., those that built the best solutions in the algorithm iteration) which are then allowed to deposit additional pheromone on the components/connections they used.
ACO was first proposed as a solution to the travelling salesman problem (TSP) [ 2], [4]. Since then, it has been successfully applied to numerous discrete optimization problems. Initially, it was used to tackle classical optimization issues, such as graph coloring, quadratic assignment [5], the maximum clique, vehicle routing [6], temperature controller [7] and scheduling [9]. More recently, ACO has been applied to diverse optimization scenarios, such as intelligent scheduling, design of communication networks, bioinformatics, circuit design-related cell placement, and machine learning[8]. In addition, some researchers have explored the applicability of ACO algorithms towards dynamic or stochastic problems, as well as towards solving multi-objective optimization problems[10], and real-world engineering optimization challenges [11]. In the literature, we found a few research articles that discuss the combination of ant colony algorithms and cellular automata: In [12], the authors propose an ACObased approach to optimize the parameters of a cellular automata-based trafic simulation model. The algorithm is applied to a real-world trafic simulation problem, and the results demonstrate significant improvements in the model’s accuracy. The article [13] presents a hybrid approach combining ACO algorithms and cellular automata to improve the optimization of trafic flow in urban areas. The proposed approach is evaluated on a simulated trafic network and compared to traditional trafic control methods, demonstrating superior performance in terms of reducing congestion and improving trafic flow. In the paper[ 14] the authors propose a hybrid approach combining cellular automata and ACO algorithms to address the dynamic network trafic assignment problem. The proposed approach is evaluated on a collection of real-world urban trafic scenarios, demonstrating superior performance compared to other optimization approaches. These papers showcase the efectiveness of combining ant colony optimization algorithms and cellular automata for a variety of optimization challenges, highlighting advancements in transportation simulation, urban trafic control, and dynamic network trafic assignment. In the present work, we hope to merge cellular automata with ACO approach for image processing, specifically edge detection. Cellular automata’s computational talents and capabilities, along with ACO’s metaheuristic ability, have promising possibilities for generating high-quality outputs.
Our CA has 25 neighbor cells (extended Moore neighborhood), so the number of possible neighbor
configurations is 225 = 33554432. The possible number of CA that can be conceived using combination
of these configurations is 233554432. The problem is to find the rules that perform edge detection the
best within this large number of CA. A choice is established to only use CA with linear rules (only one
neighbor configuration rule for each CA) which is beneficial in terms of computational performance
of the CA and the substantial reduction in the search space to 33554432. The rule convention used to
designate rules is shown in figure (
The number within each box represents the rule number associated with a neighbor configuration that only has that particular neighbor. So, if the next state of a cell depends only on its present state, it is represented as Rule 1. Similarly, if the next state of a cell is dependent only on its bottom neighbor, then it is represented as Rule 8 and so on. These twenty-five rules are known as fundamental/basic rules. All linear rules are derived using these basic rules which are expressed as the sum of the basic rules. For example, Rule 130 can be expressed as follows: Rule 130 = Rule 128 ⊕ Rule 2 ACO is used to optimize our search for CA rules that perform better edge detection. The idea is having a 5×5 space and ants occupy cells of this space and move around while generating pheromones in discrete time iterations. Pheromones value on every cell might increase if ants generate pheromones and decrease on each iteration by evaporation.
The number of ants, the pheromone evaporation rate, and the randomness parameter are experimentation parameters of our implementation of ACO.
This process creates the population of ants and put them in random positions of the 5×5 cells space. It also initiates the pheromone values in every cell to zero.
The reason for using a 5×5 cells space in ACO is to project the ants to the CA neighbor model. The
occupied cells in the ACO cells space define the current explored CA rule, an example of this is illustrated
in figure (
Quantifying the quality of edge produced by CA rule represents the amount of pheromone generated
{︃BestFitness if fitness ≤ BestFitness
iftness
otherwise
The pheromone values are updated in all the occupied cells by the equation (
Phero(, )+1 = Phero(, ) + max(0, fitness −
In every time iteration, an ant can move from the cell it occupies to any cell within a two-cell
radius (horizontally, vertically or diagonally) without going out of the moving space. Figure (
In this step the pheromone values increase in the cells occupied by at least one ant. The value increase is the same in these cells no matter how many ants in the cell. The increase in pheromones depends on the computed fitness.
In order to prevent the ACO from getting in local optimums, where pheromone values keep increasing
in only select cells, a mechanism is set in place to push the optimization to explore more rules, by
letting the ants generate pheromones only when significant fitness values are discovered. This is
implemented by creating MinFitness variable, which is initiated by zero (0), and keeping track of the
best fitness value (BestFitness). Whenever a discovered rule has greater fitness value than the best
iftness, the BestFitness is updated using equation (
The pheromone values in every cell are updated using equation (7): ℎ(, )+1 = (1 − ) * ℎ(, ) (7) p is the evaporation rate.
The initial parameters are set to: twenty-five (25) ants, evaporation rate of 5%, randomness parameter of 5. 500 cycles of the ACO algorithm have been run. After 300 iterations, we found that the best rules started to emerge. Some of the best rules identified in Moore neighborhood model (r=1) are: 153, 46, 394, 226, 184, 47, 395, some others in extended Moore neighborhood model (r=2): 262271, 1343, 4194767, 262643, 16637.
The testing dataset consisted of a collection of images from the Berkeley University database that had well-defined ground truth edges [ 18]. The dataset comprised images captured in indoor and outdoor settings, encompassing a broad variety of edge types and complexities. This diverse collection of images enabled us to draw pertinent insights from the data, supporting the validity and usefulness of our ifndings.
In order to evaluate the quality of edges produced by a CA rule, we need a function that measures how close are the results produced by this CA to the ground truth. Irrespective of the chosen optimization technique, the outcome greatly depends on the objective function employed, as it plays a critical role in determining the final results. As part of our study, we utilized two fitness functions, namely the Structural Similarity Index (SSIM) and Root-Mean-Square Error (RMSE), to assess the quality diference between the resulting image from cellular automata and the reference image. When dealing with images containing numerous intensity values, the RMSE can serve as a direct measure for assessing the similarity between the input and target image. However, it is widely recognized that the RMSE metric has certain limitations, as it fails to account for inter-pixel relationships, and may inadequately capture perceptual similarity. SSIM measures the image similarity taking into account three independent channels including luminance, contrast and structure [15]. It is the well suited measure for gray level images. The SSIM metric between two images and is defined by equation (8) : (, ) =
(2 + 1)(2 + 2) ( 2 + 2 + 1)( 2 + 2 + 2) where , , 2, 2, are the mean of , the mean of , the variance of , the variance of , and the covariance of and , respectively. Following [16], 1 is set to (0.01 * 255)2 and 2 = (0.03 * 255)2. The RMSE is calculated according to equation (9):
⎸⎯ 1 ∑−︁1 ∑− ︁1[(, ) − (, )]2 = ⎷⎸ =0 =0 (8) (9) where (, ) is the original image (in our case, the ground-truth image) and (, ) is the reconstructed image.
In this section, we present the results of application of our hybrid ACO-CA algorithm to a set of
images from Berkeley dataset. Among the numerous results collected, we have chosen to showcase
three images. We demonstrate the execution of the rules 1343, 16637, 262271 and 262643, on the Boat,
Reindeer and Castle images. It is essential to highlight that once the optimal rules have been identified,
they can be directly applied to an image, thereby expediting the process and delivering the intended
output eficiently. The findings presented in figures (
We illustrate the real-time edge detection process of the proposed method and compare it with established
algorithms like Canny, Laplacian, among others, to carry out a comprehensive assessment. Table (
This research introduces a novel technique for edge detection implementation via cellular automata utilizing an extended Moore neighborhood and optimization of the process of rules extraction with ACO algorithm. Even though this approach requires a larger rule space, our work employs a metaheuristic to uncover the optimal set of rules providing the best possible results. This strategy enables the identification of a subset of rules capable of producing high-quality edges within a single iteration. Experimental analysis performed on multiple images shows that these rules yield image outputs with enhanced contrast levels, while efectively smoothing the object edges present in the image. Comparisons between the resultant edges and the ground truth edges, alongside established edge detection techniques such as Canny, Roberts, Laplacian, and Scharr, are made using SSIM and RMSE iftness values, which confirm the robust performance of our approach. Notably, our rules demonstrate faster runtime compared to the aforementioned techniques.
As a future outlook for this study, we aim to investigate other metaheuristics for optimizing the set of rules in the cellular automata, such as grey wolf algorithm, bee algorithm, dolphin algorithm, and their quantum version. Additionally, we plan to introduce new principles of Deep Learning and utilize their robust learning capabilities to accelerate the optimization process and facilitate the attainment of optimal edge detection in the shortest possible time.
[6] B. Bullnheimer, R.F. Hartl, C. Strauss Applying the ant system to the vehicle routing problem, In: Voss S., Martello S., Osman I.H., Roucairol C. (eds.) Meta- Heuristics: Advances and Trends in Local Search Paradigms for Optimization, Kluwer, Boston, pp 285-296, 1999. [7] S. Katiyar, A. Mittal, A. Q. Ansari, T. K. Saxena, "Ant Colony Algorithm Based Adaptive PID Temperature Controller," Proc. 7th Int. Conf. on Trends in Industrial Measurements and Automation (TIMA 2011), CSIR, Chennai, January 2011. [8] Y. Sun, S. Wang, Y. Shen, X. Li, A. T. Ernst, M. Kirley "Boosting Ant Colony Optimization via Solution Prediction and Machine Learning", Computers and Operations Research, vol. 143, p. 105769, 2022. [9] W. Deng, J. Xu and H. Zhao, "An Improved Ant Colony Optimization Algorithm Based on Hybrid
Strategies for Scheduling Problem," in IEEE Access, vol. 7, pp. 20281-20292, 2019. [10] L. Yongbo, H. Soleimani, M. Zohal. "An improved ant colony optimization algorithm for the multidepot green vehicle routing problem with multiple objectives." Journal of cleaner production 227: 1161-1172, 2019. [11] O. Mahamed GH, S. Al-Sharhan. "Improved continuous ant colony optimization algorithms for real-world engineering optimization problems." Engineering Applications of Artificial Intelligence 85: 818-829, 2019. [12] X. Yang, J. Han, and Y. He . "Ant colony optimization for cellular automata parameter determination in transportation simulation." Journal of Transportation Engineering, Vol. 132, No. 11, pp. 853-862, 2006. [13] R.B. Anggraini and D. Arini. "Ant colony optimization and cellular automata for urban trafic control system." 2014 International Conference on Control, Electronics, Renewable Energy and Communications (ICCEREC), pp. 96-100, 2014. [14] T.Q. Dai, S. Yang, and C.F. Cai. "A cellular automaton-ant colony optimization hybrid approach to the dynamic network trafic assignment problem." Journal of Advanced Transportation, Vol. 44, No. 3, pp. 193-209, 2010. [15] Z. Wang, E.P. Simoncelli, A.C. Bovic, “Multi-scale structural similarity for image quality assessment”, in Proc. 37th IEEE Asilomar Conf. On Signals, Systems and Computers, Pacific Grove, CA, 2002. [16] Z. Wang, A.C. Bovik, H.R. Sheikh, E.P. Simoncelli, "Image quality assessment: from error visibility to structural similarity," IEEE Transactions on Image Processing, vol. 13, no. 4, pp. 600-612,2004. [17] M.Dorigo, T. Stützle. ""Ant colony optimization: overview and recent advances". Springer International Publishing, 2019. [18] P. Arbelaez, M. Maire, C. Fowlkes and J. Malik, "Contour Detection and Image Segmentation Resources," [Online]. Available: https://www2.eecs.berkeley.edu/Research/Projects/CS/vision/grouping/ resources.html