Source-linked AI summary
A Comparison of Nature Inspired Algorithms for Multi-threshold Image Segmentation
Valentín Osuna-Enciso, Erik Cuevas, Humberto Sossa
TL;DR
Image segmentation requires threshold selection to group pixels into classes, and this paper evaluates evolutionary algorithms for that task. It compares three nature-inspired algorithms and reports superior performance for DE in minimizing histogram distance, while identifying other distance measures as future work.
Problem
Image segmentation depends on threshold selection to assign pixels to visually distinct classes, including scenes containing multiple objects.
Method
The paper uses evolutionary algorithms to compute threshold selection for image segmentation, with each modeled pixel class corresponding to a threshold point.
Results
DE achieved superior performance in minimizing the Hellinger distance between original and candidate histograms, while ABC, DE, PSO, and Otsu formed the reported performance ordering.
Takeaways & Limitations
The study provides an empirical comparison of three state-of-the-art nature-inspired algorithms for multi-threshold image segmentation.
Takeaways & Limitations
Future work will compare other distance measures with the best meta-heuristic to assess convergence using a computationally cheaper distance.
Abstract
from arXiv · showhide
In the field of image analysis, segmentation is one of the most important preprocessing steps. One way to achieve segmentation is by mean of threshold selection, where each pixel that belongs to a determined class islabeled according to the selected threshold, giving as a result pixel groups that share visual characteristics in the image. Several methods have been proposed in order to solve threshold selectionproblems; in this work, it is used the method based on the mixture of Gaussian functions to approximate the 1D histogram of a gray level image and whose parameters are calculated using three nature inspired algorithms (Particle Swarm Optimization, Artificial Bee Colony Optimization and Differential Evolution). Each Gaussian function approximates thehistogram, representing a pixel class and therefore a threshold point. Experimental results are shown, comparing in quantitative and qualitative fashion as well as the main advantages and drawbacks of each algorithm, applied to multi-threshold problem.
1. Introduction
Image segmentation is a foundational preprocessing step, and multi-thresholding is needed when scenes contain multiple objects. This paper formulates multi-threshold segmentation as Gaussian-mixture histogram approximation and compares DE, PSO, and ABC algorithms.
- Segmentation motivation: Image segmentation divides pixels into related regions and supports subsequent image-understanding tasks such as feature extraction and recognition.Thresholding is popular because it produces smaller storage requirements, faster processing, and easier manipulation.
- Threshold selection: Multi-level thresholding selects multiple threshold values to segment scenes containing distinct objects.It extends bi-level thresholding, which separates an image into object and background classes using one limit value.
- Threshold selection: Multilevel segmentation can lack a systematic solution as classes increase, while also suffering slow convergence or high computational cost.These drawbacks motivate optimization-based approaches for difficult threshold-selection problems.
- Proposed formulation: The proposed approach approximates a grayscale image’s 1-D histogram with a Gaussian mixture whose parameters are optimized using DE, PSO, and ABC.Each Gaussian function represents a pixel class and therefore a threshold point; Hellinger distance compares the candidate mixture with the original histogram.
- Experimental comparison: The study compares the three algorithms experimentally on multi-threshold segmentation to identify their advantages and drawbacks.The comparison addresses image processing rather than only synthetic benchmark functions, where previous studies had focused.
2. Gaussian Approximation
The method approximates a normalized gray-level histogram with a mixture of Gaussian functions, whose parameters represent image classes and whose intersections determine thresholds. The three nature-inspired algorithms optimize the mixture fit using a Hellinger-distance fitness function, while adjacent-class error determines each threshold.
- Histogram representation: A normalized histogram h(x) is treated as the probability distribution of gray levels in an image with L levels.The gray-level domain is given as [0,1,…,L−1].
- Gaussian mixture model: The candidate histogram is a mixture of K Gaussian probability functions, with each Gaussian representing one pixel class.The parameters include class prior probabilities, means, and standard deviations.
- Parameter estimation: The Hellinger distance compares the Gaussian-mixture candidate histogram with the experimental histogram and serves as the fitness function for all three algorithms.The formulation is stated to require no extra parameters.
- Threshold determination: For ordered class means, thresholds are obtained by minimizing the classification error between each pair of adjacent Gaussian classes.The error combines the probabilities of misclassifying pixels in either direction across the threshold.
- Threshold determination: The threshold process is repeated for every adjacent class pair, retaining the feasible positive solution of the resulting quadratic equation.Figure 1 illustrates the threshold-point determination process.
- Motivation: The section motivates nature-inspired optimization because conventional thresholding methods can be computationally expensive as the number of threshold combinations increases.The text presents evolutionary approaches as an option for addressing computational cost in image-processing problems.
3. Differential Evolution
Differential Evolution is presented as a population-based optimizer for the Gaussian-mixture thresholding problem. It generates candidate solutions through mutation and crossover, then selects improved solutions until a stopping criterion is reached.
- Mutation: Mutation is the central Differential Evolution operation and uses a weighted difference between randomly selected parent vectors.The algorithm is described as simple, robust, and convergent.
- Initialization: Differential Evolution initializes a uniformly distributed population of parent vectors within predefined lower and upper bounds.Each parent is represented by a D-dimensional vector.
- Mutation and crossover: A scaling mutation factor and crossover parameter combine mutant-vector components with parent information to form a trial vector.The crossover constant controls how much of the mutant vector enters the trial vector.
- Selection and stopping: A selection operator retains improved solutions, with iterations continuing until a maximum-iteration or minimum-distance criterion is met.The cost function used in selection is the fitness function defined earlier.
4. Particle Swarm Optimization
The study uses a modified Clerc Particle Swarm Optimization algorithm with a constriction parameter to optimize thresholding solutions. Particles update their positions and velocities using individual and global best solutions within bounded limits.
- Background: PSO was developed as a general-purpose optimizer inspired by synchronized swarm behavior and has been applied to image segmentation and other tasks.The paper places the method within the broader development of swarm-based optimization.
- Particle updates: Each particle update combines its current velocity with attraction toward its personal best and the population’s global best.The personal best is the best particle found at a given position, while the global best is the best in the population.
- Initialization: Particle Swarm Optimization models collective search through a population of particles whose positions and velocities are initialized randomly.The particle coordinates and velocities are bounded by specified lower and upper limits.
- Modified PSO: The implementation modifies Clerc’s PSO by using a constriction parameter, including a dynamic form that changes with iteration.The text distinguishes this dynamic parameter from the original static constriction value.
5. Artificial Bee Colony Optimization
Artificial Bee Colony Optimization searches thresholding solutions by representing candidate solutions as food sources managed by employed, onlooker, and scout bees. The cycle evaluates neighboring sources, preserves good solutions, replaces abandoned sources, and repeats until a stopping criterion is reached.
- Algorithm cycle: The employed-bee, onlooker-bee, and scout phases repeat until a minimum-distance or maximum-iteration criterion is reached.The pseudocode summarizes this cycle after initialization and source evaluation.
- Scout phase: Scout bees replace abandoned food sources with newly discovered sources to support exploration.The algorithm records the best food source found through the current iteration.
- Initialization: Artificial Bee Colony initializes food sources randomly within the lower and upper bounds of the optimization problem.The number of sources, dimensions, and current iteration are specified in the initialization description.
- Employed bees: Employed bees modify memorized food sources using randomly selected neighbors and retain the better evaluated position.Out-of-bounds modifications are clipped to the appropriate limit.
- Onlooker bees: Onlooker bees select food sources according to a fitness-based probability and evaluate neighboring modifications.The selected and modified sources are compared, and the better one is memorized.
6. Experimental Results
Experiments compare DE, PSO, ABC, and Otsu for multi-threshold segmentation using optimization and segmentation-quality criteria. DE performs best on iteration efficiency, while ABC provides the strongest segmentation quality under the Hausdorff measure.
- Experimental setup: 295 ALL-IDB blood-smear images were selected because their three classes were sufficiently well defined for the proposed segmentation.The classes correspond to nuclei, red blood cells, and background.
- Optimization results: ABC and DE are more consistent in minimizing Hellinger distance, with DE slightly outperforming ABC; PSO has larger mean distance and standard deviation.Table 3 reports optimization statistics over the ALL-IDB database.
- Optimization results: DE requires the fewest iterations, averaging 76, followed by ABC, PSO, and Otsu.Function evaluations and execution times follow the same ordering because they depend directly on iteration count.
- Optimization results: The best algorithm evaluates almost 90% fewer objective functions than Otsu, making the meta-heuristic techniques computationally cheaper in this comparison.Otsu is used as the reference for objective-function evaluation.
- Segmentation-quality results: The quality assessment is limited because segmentation uses only pixel gray level, which is insufficient by itself to qualify the results.A second experiment therefore evaluates quality using Hausdorff distance and manually segmented ground truths.
- Segmentation-quality results: ABC achieves the best mean Hausdorff-distance segmentation quality, followed by DE, PSO, and Otsu, although segmented images still contain artifacts.DE is strongest in optimization, whereas ABC is strongest in segmentation quality because the resulting Gaussian mixtures differ across algorithms.
7. Conclusions
The study compares three nature-inspired algorithms for multi-threshold segmentation using Gaussian-mixture histogram modeling, under a Gaussian intensity-distribution assumption. Differential Evolution minimized Hellinger distance more effectively and with fewer cost-function evaluations, while Artificial Bee Colony achieved the best segmentation quality; further distance measures remain for future comparison.
- Conclusions: The paper empirically compares PSO, ABC, and DE for image thresholding by a mixture of Gaussian functions.Experiments used a database of smear blood images.
- Conclusions: DE showed superior performance in minimizing the Hellinger distance between the original and candidate histograms.The statistical analysis identifies DE as the strongest optimizer for this objective.
- Conclusions: DE performed the Hellinger-distance minimization with fewer evaluations of the distance-based cost function.
- Conclusions: ABC achieved the best segmentation quality, followed by DE, PSO, and Otsu.Otsu was exhaustive but did not provide the best segmentation quality in these experiments.
- Conclusions: Future work will compare other distance measures with the best computationally cheaper meta-heuristic to assess convergence under different cost functions.