An Approach to Polygonal Approximation of Digital Curves Based on Discrete Particle Swarm Algorithm

Fangmin Dong, Renbin Xiao, Zhong Yi-fang, Yong LiuZenodo 2020 · DOI

TL;DR

This paper proposes a novel approach to polygonal approximation of digital curves using a discrete Particle Swarm Optimization (PSO) algorithm. By incorporating a more sophisticated fitness function that considers centroid error and segment variance, and by dynamically adjusting PSO's acceleration factors using a sigmoid function, the algorithm achieves better preservation of original curve features, especially for symmetric shapes.

What Problem Does This Paper Address?

Polygonal approximation is a fundamental problem in computer graphics, image processing, and computer vision. It involves simplifying complex digital curves into a series of connected line segments (a polygon) while minimizing approximation error and the number of vertices. The challenge lies in finding an optimal balance between these two objectives, especially for curves with intricate shapes or symmetries, where preserving key features is crucial. Existing methods often struggle with either computational complexity, convergence to suboptimal solutions, or a lack of feature preservation.

Methods

The core of this paper is an adaptation of the Particle Swarm Optimization (PSO) algorithm for polygonal approximation. Here's a breakdown of their approach:

  • Discrete PSO: Unlike standard PSO which operates on continuous spaces, this paper uses a discrete PSO. Each "particle" in the swarm represents a potential polygonal approximation. A particle's "position" is encoded as a binary vector, where a '1' indicates a vertex from the original curve is selected as a vertex for the approximation polygon, and a '0' indicates it's not.
  • Enhanced Fitness Function: The fitness function is crucial for guiding the PSO. The authors introduce a more comprehensive fitness function that goes beyond simple distance errors. It includes:
  • Total Error (Ed): The sum of errors for each line segment of the approximation polygon.
  • Variance of Error (Es): The variance of errors across all line segments, aiming for more uniform approximation.
  • Centroid Error (Eg): The quadratic distance between the centroid of the original curve and the centroid of the approximated polygon. This is particularly important for preserving shape characteristics, especially for symmetric curves.
  • Sigmoid-based Acceleration Factors: Standard PSO uses constant acceleration factors (c1 and c2) that control the influence of personal best and global best positions. This paper proposes using a sigmoid function that varies these factors based on the current iteration number. This allows the algorithm to have a broader global search in the early stages and a more focused local search in later stages, helping to avoid premature convergence to local optima.

Datasets

The paper evaluates its approach on two types of digital curves:

  • Leaf and Chromosome Digital Curves: These are standard examples used in polygon simplification algorithms.
  • Three-dimensional Mesh Model Contour Curves: These represent more complex, regular curves derived from 3D models.

The paper does not introduce new benchmark datasets.

Key Insights and Ideas

  • Centroid Error is Key for Shape Preservation: The inclusion of centroid error in the fitness function is a significant contribution. It directly addresses the challenge of preserving the overall shape and symmetry of the original curve, which is often overlooked by methods solely focused on minimizing segment-wise errors.
  • Dynamic Acceleration Factors Improve Search: Using a sigmoid function to dynamically adjust acceleration factors is a clever way to balance global exploration and local exploitation in PSO. This helps the algorithm escape local minima and converge more effectively to a better overall solution.
  • Discrete PSO for Vertex Selection: Representing vertex selection as a binary problem and using discrete PSO is a natural fit for this type of combinatorial optimization problem.

Key Results

The experimental results demonstrate the effectiveness of the proposed approach:

  • Improved Approximation Accuracy: The proposed algorithm consistently achieved lower approximation errors (measured by Ed) compared to existing methods, particularly for preserving features.
  • Better Feature Preservation: Visual comparisons show that the approximations generated by the new algorithm retain the characteristic shapes of the original curves, especially for symmetric examples, better than other methods.
  • Faster Convergence (in some aspects): While the sigmoid function might slightly reduce overall convergence speed in some scenarios, it leads to a more robust convergence to a better final solution, avoiding premature convergence to suboptimal results. The paper shows that the algorithm converges to its best solution faster than some of the compared methods.

Limitations and Future Work

  • Automated Weighting of Fitness Components: The authors acknowledge that the automated selection of weighted values for each error component (c4, c5, c6) in the fitness function needs further research. Currently, these weights are set empirically.
  • Control of Acceleration Factor Change Rate: Similarly, the precise control over the change rate of the acceleration factor (parameter 'a' in the sigmoid function) could be a subject for future investigation.
  • Generalization to Free Curves: While the paper focuses on regular curves and mentions potential for free curves, further research might be needed to fully optimize for arbitrary, non-regular shapes.

Summary updated

Abstract

An approach to polygonal approximation of regular digital curves based on PSO algorithm is presented. In this paper, each particle corresponds to a candidate solution to the polygonal approximation problem, which is represented as a binary vector. The offset error of centroid between the original curve and the approximation polygon, and the variance of distance error for each approximation segment are adopted in the fitness function to evaluate the feasibility degree of the candidate solution. The sigmoid function of iteration times is used as the acceleration factors instead of the constant factors to improve the global searching characteristics. Experimental results show that the proposed approach can get suitable approximation results for preserving the features of original curves.
BibTeX
@inproceedings{dong2020approach,
  author = {Fangmin Dong and Renbin Xiao and Zhong Yi-fang and Yong Liu},
  title = {{An Approach to Polygonal Approximation of Digital Curves Based on Discrete Particle Swarm Algorithm}},
  booktitle = {Zenodo},
  year = {2020},
  doi = {10.3217/jucs-013-10-1449},
}
Figure