Elsevier

Pattern Recognition Letters

Volume 29, Issue 2, 15 January 2008, Pages 161-172
Pattern Recognition Letters

Non-supervised image segmentation based on multiobjective optimization

https://doi.org/10.1016/j.patrec.2007.09.008Get rights and content

Abstract

The segmentation process based on the optimization of one criterion only does not work well for a lot of images. In many cases, even when equipped with the optimal value of the threshold of its single criterion, the segmentation program does not produce a satisfactory result. In this paper, we propose to use the multiobjective optimization approach to find the optimal thresholds of two criteria: the within-class criterion and the overall probability of error criterion. In addition we develop a new variant of Simulated Annealing adapted to continuous problems to solve the histogram Gaussian curve fitting problem. Six examples of test images are presented to compare the efficiency of our segmentation method, called Combination of Segmentation Objectives (CSO), based on the multiobjective optimization approach, with that of two classical competing methods: Otsu method and Gaussian curve fitting method. From the viewpoints of visualization, object size and image contrast, our experimental results show that the segmentation method based on multiobjective optimization performs better than the Otsu method and the method based on Gaussian curve fitting.

Introduction

Image segmentation process is defined as the extraction of the important objects from an input image. Since the segmentation is considered by many authors to be an essential component of any image analysis system, that problem has received a great deal of attention; thus any attempt to completely survey the literature in this paper would be too space-consuming. However, surveys of most segmentation methods may be found in (Pitas, 2000, Lee et al., 1990, Sahoo et al., 1988).

Image thresholding is definitely one of the most popular segmentation approaches to extract objects from images, and more particularly in infrared images (e.g. Pitas, 2000, Gonzales and Woods, 2002), for the reason that it is simple to implement. It is based on the assumption that the objects can be distinguished by their gray levels. The optimal threshold is the one that permits to separate different objects from each other or different objects from the background (e.g. Gonzales and Woods, 2002, Otsu, 1979). The automatic fitting of this threshold is one of the main challenges of image segmentation.

Segmentation methods can be classified into parametric and non-parametric approaches. In the parametric methods the basic idea is to fit the histogram with a sum of Gaussian distributions, then find the optimal thresholds at the intersections of these Gaussians. However, when the histogram is unimodal these methods are not able to provide a threshold, and if the optimal threshold is not located at the histogram valleys these methods fail. In the non-parametric methods the goal is to be able to find the optimal thresholds without any parameter fitting (i.e. Otsu, 1979, Abutaleb, 1989, Tao et al., 2004, Zahara et al., 2004); these methods are based on discriminant analysis or entropy concept, and maximize the separability of the resultant classes. However, in the multilevel case, the thresholds provided by these methods are less credible, as the number of regions (classes) increases and their performances depend on the objects sizes. In this paper, we present a new hybrid segmentation technique, called Combination of Segmentation Objectives (CSO), that allows to segment multimodal and unimodal image histograms, by optimizing a combination of parametric and non-parametric methods.

Multiobjective optimization (MO) (also known as multicriterion, or Pareto optimization) extends the optimization theory by permitting several design objectives to be optimized simultaneously. Several methods have been devised for MO problems, including hierarchical optimization, weighting objectives, distance functions, goal programming, constraint methods, min–max optimization, and many others (e.g. Boychuk and Ovchinnikov, 1973, Eschenauer et al., 1986, Osyczka, 1984, Collette and Siarry, 2004).

The motivation of using multiobjective optimization is to design a new image segmentation technique, that combines the flexibility of multiple fitness functions with the power of SA for searching vast combinatorial state spaces, in order to find the optimal thresholds. In this paper, we improved SA and used it for both histogram Gaussian curve fitting and optimizing the image segmentation multiobjective criterion. To solve the continuous optimization problem of histogram Gaussian curve fitting, we improved an adaptation of SA to continuous optimization problems, called Enhanced Simulated Annealing (ESA) (Siarry et al., 1997).

The outline of the paper is as follows. We start in the next section by formulating image segmentation as a multiobjective problem and giving the principle of the plain aggregating approach to solve a multiobjective problem. In Section 3, a method to calculate the number of classes (regions) in an image based on a peak detection algorithm is presented. The multiobjective optimization model for image segmentation is presented in the fourth Section. In Section 5, the optimization algorithms that we used are detailed. In Section 6, we start by discussing the fitting of our optimization algorithms; afterwards the results of the Gaussian curve fitting algorithm and the obtained segmented images are presented. The paper ends with a brief concluding section.

Section snippets

Image segmentation problem

In almost all cases the segmentation process, based on the optimization of one criterion only, does not work very well for many images. Frequently, the optimal value of the threshold for each criterion does not produce a satisfactory image segmentation. The segmentation methods are divided into two groups: the parametric methods and the non-parametric methods. In order to overcome the weaknesses of these methods, a hybrid method, based on the combination of a parametric method and a

Detection of the number of pixels classes

The proposed segmentation method is non-supervised, what implies no expert intervention for segmenting images even for determining the number of regions in the image.

In this section, we present an algorithm to calculate automatically the initial number of the regions in the image, based on a new peak-finding algorithm, that identifies the most significant peaks of the histogram. The number of these peaks corresponds to the number of pixels classes (regions) in the image.

In the literature,

Multiobjective optimization model for image segmentation

In this subsection we present the different criteria that we will minimize later for the process of image segmentation. The two-objective functions (criteria) that we chose are the modified within-class variance and the overall probability of error.

Adaptive simulated annealing

As previously mentioned, the combinatorial nature of the problem does not permit an exhaustive enumeration of every possible combination in order to identify the optimal solution. While for simple cost functions several very effective greedy algorithms can be employed (Collette and Siarry, 2004, Dréo et al., 2006), arbitrary functions show unpredictable surfaces with many local minima, and require a stochastic approach that is, in principle, suitable for identifying global minima. The method

Results and discussions

In this section, we present the results obtained via the application of our method to different test images, shown in Fig. 4a–f, that have three kinds of image histograms, shown in Fig. 5a–f, respectively. This section is divided into three subsections: in the first subsection, the fitting of the used optimization algorithms, improved ESA and SA, is presented. In the second subsection, we discuss the result of GCF algorithm over unimodal and multimodal image histograms. In the last subsection,

Conclusion

In this paper, we proposed a new approach to find the optimal image segmentation thresholds, based on multiobjective optimization. In the first phase, a new peak-finding algorithm is used to identify the most significant peaks in the histogram. In the second phase, we fit the histogram of the image to a sum of Gaussian curves to compute the first segmentation criterion. In the second criterion considered, the homogeneity is calculated for each image pixel; both local and global information are

References (21)

There are more references available in the full text version of this article.

Cited by (33)

  • Efficient quantum inspired meta-heuristics for multi-level true colour image thresholding

    2017, Applied Soft Computing Journal
    Citation Excerpt :

    They have used 2D Otsu method in images having low contrast. Tang et al. have presented another algorithm based on SA and improved Snake model for image segmentation [40]. Nakib et al. have proposed a different work on non-supervised image segmentation for multi-objective optimization [40].

  • Multi-level thresholding using quantum inspired meta-heuristics

    2014, Knowledge-Based Systems
    Citation Excerpt :

    In addition to this they have developed another alternative of SA that can able to resolve the histogram Gaussian curve fitting problem. The details are given in [48]. Yufei et al. have worked on image segmentation.

  • A simulated annealing-based optimal threshold determining method in edge-based segmentation of grayscale images

    2011, Applied Soft Computing Journal
    Citation Excerpt :

    We also used Entropy and SA method in bi-level and edge-based segmentation, but Snake method is only used in edge-based segmentation. The method of SA is a local optimization method used in solving problems of difficult combinatorial optimization [14–16,32–34,38,39]. Cerny [4] extended Kirkpatrick et al. [3] study.

  • Robust threshold estimation for images with unimodal histograms

    2010, Pattern Recognition Letters
    Citation Excerpt :

    Setting thresholds is a non-trivial problem. Ideally, each coherent set of pixels of the image is characterized by its gray-level and the histogram presents several corresponding maxima (modes): the threshold can simply be placed at the local minima between the peaks of the histograms, detected either directly or indirectly, or it can be placed by analyzing the statistics of the classes to minimize (Otsu, 1979; Hou et al., 2006; Nakib et al., 2008). However, in many cases, when the sets are not clearly distinguished, the histogram becomes unimodal.

View all citing articles on Scopus
View full text