An edge detection method using outer Totalistic Cellular Automata

Sebastian Amrogowicz, Yitian Zhao, Yifan ZhaoNeurocomputing 2016 · DOI

TL;DR

This paper introduces a novel edge detection method using Outer Totalistic Cellular Automata (OTCA), a type of computational model known for its simplicity and potential for noise reduction. The authors demonstrate that their OTCA-based approach outperforms existing Cellular Automata (CA) methods and conventional edge detectors in terms of accuracy and robustness to noise, particularly salt-and-pepper noise.

What Problem Does This Paper Address?

Edge detection is a fundamental task in image processing, crucial for various computer vision applications like object recognition and medical diagnosis. While many edge detection methods exist, they often struggle with noise, leading to fragmented or spurious edges. Traditional methods like Sobel and Prewitt are sensitive to noise, and even more advanced techniques like Canny require careful parameter tuning. Cellular Automata (CA) offer a promising alternative due to their inherent noise-filtering capabilities and parallel processing potential. However, existing CA-based edge detectors have limitations, and the application of Outer Totalistic Cellular Automata (OTCA) to edge detection, a more complex variant of TCA, remained largely unexplored. This paper aims to fill this gap by proposing and evaluating an OTCA-based edge detection method, specifically addressing its performance against various noise types and levels compared to other CA and classical methods.

Methods

The core of this paper is the development and evaluation of an edge detection method based on Outer Totalistic Cellular Automata (OTCA).

  • Cellular Automata (CA) Basics: The paper starts by defining CA as a grid of cells, each with a state, that updates based on its neighbors and a transition rule. They highlight the complexity of defining optimal rules, especially for grayscale images.
  • Totalistic vs. Outer Totalistic CA:
    • Totalistic CA (TCA): The next state of a cell depends on the sum of its neighbors including the central cell.
  • Outer Totalistic CA (OTCA): The next state of a cell depends on the sum of its neighbors excluding the central cell, and the state of the central cell itself. This added dependency on the central cell's state makes OTCA more complex and potentially more powerful.
  • Rule Space and Selection: The paper acknowledges the vastness of the rule space for OTCA (2^18 = 262,144 possible rules for binary images with Moore neighborhood). To manage this, they employ a heuristic approach:
  • They reduce the search space by fixing certain rule bits that correspond to uniform or noisy states.
  • They evaluate rules using the Figure of Merit (FoM) metric on a dataset.
  • They select the top-performing rules (top 5%) and then identify the 100 most common rules for visual inspection.
  • Finally, they select four representative OTCA rules (832, 960, 1856, 1984) for detailed analysis.
  • Quality Metric: The Figure of Merit (FoM) is used to quantitatively evaluate edge detection performance. It considers both the accuracy of edge localization and the number of detected edge points compared to a ground truth.

Datasets

The paper uses a publicly available dataset from the University of South Florida (USF) for evaluation. This dataset consists of:

  • 50 real-life images
  • 10 aerial images The images contain single objects in various indoor and outdoor scenes, offering a diverse range of edge types. The dataset also includes manually specified Ground Truth (GT) edge maps, where pixels are classified as edge, no-edge, or "don't care."

Key Insights and Ideas

  • OTCA's Potential for Edge Detection: The research demonstrates that OTCA, despite its complexity, can be effectively applied to edge detection and offers advantages over simpler CA variants and traditional methods.
  • Noise Robustness is Key: A significant focus is on how different edge detectors perform under various noise conditions (salt-and-pepper and Gaussian). The OTCA method shows a notable ability to attenuate noise while preserving edge continuity.
  • Trade-offs in CA Rules: The paper highlights that different CA rules have distinct behaviors, leading to variations in edge thickness, continuity, and noise handling. This underscores the importance of careful rule selection.
  • OTCA vs. TCA: While both TCA and OTCA generally perform well, OTCA shows a slight advantage in low-noise conditions, whereas TCA can sometimes outperform OTCA at higher noise levels.
  • Parallelism Advantage: The inherent nature of CA makes them "trivially parallel," suggesting their suitability for efficient implementation on modern multi-core processors and GPUs.

Key Results

  • Superior Performance: The proposed OTCA-based edge detection method consistently achieved high Figure of Merit (FoM) values, outperforming other CA-based methods (LCA, WCA, UCA, TCA) and classical methods (Sobel, Prewitt, Canny, SUSAN, Kovesi) across various noise levels.
  • Noise Resilience:
    • Salt & Pepper Noise: OTCA demonstrated the highest quality up to 5% noise. At higher levels, TCA showed better performance, but OTCA rules generally provided thinner, more continuous edges with better noise attenuation.
  • Gaussian Noise: OTCA showed high similarity at lower variance levels. At higher variances, UCA with a packet of rules performed best, but OTCA and TCA rules generally produced the best visual quality, with OTCA resulting in more isolated pixels and fewer clustered noise areas.
  • Edge Quality: OTCA rules produced thin and continuous edges, offering good smoothing capabilities and clearer edges on noised borders.
  • Computational Complexity: The running times for the proposed OTCA method were comparable to other CA-based methods, indicating potential for real-time applications.

Limitations and Future Work

  • Grayscale Images: The current method is primarily demonstrated for binary images. The authors acknowledge that extending it to grayscale images is a significant future direction. However, the vast rule space for grayscale images presents a challenge, necessitating research into rule reduction methods.
  • Neighborhood Size: Considering a larger neighborhood size might offer further performance improvements.
  • Rule Selection Complexity: While the paper addresses rule selection, the sheer number of possible rules for OTCA remains a challenge, and further optimization of selection strategies could be beneficial.

Summary updated

BibTeX
@article{amrogowicz2016edge,
  author = {Sebastian Amrogowicz and Yitian Zhao and Yifan Zhao},
  title = {{An edge detection method using outer Totalistic Cellular Automata}},
  journal = {Neurocomputing},
  year = {2016},
  doi = {10.1016/j.neucom.2016.05.092},
}
Figure