Bioinspired metaheuristics for image segmentation

Abstract

PhD thesis defended on 2nd December, 2013.

In general, the purpose of Global Optimization (GO) is to find the global optimum of an objective function defined inside a search space, and it has applications in many areas of science, engineering, economics, among other, where mathematical modeling is used. GO algorithms are divided into two groups: deterministic and evolutionary. Since deterministic methods only provide a theoretical guarantee of locating local minimums of the objective function, they often face great difficulties in solving GO problems. On the other hand, evolutionary methods are usually faster in locating a global optimum than deterministic ones, because they operate on a population of candidate solutions, so they have a bigger likelihood of finding the global optimum, and even they have a better adaptation to black box formulations or complicated function’ forms.

Even though during the last decade has had an important increasing in the area of metaheuristics applied to optimization, still is considered the searching of such methods as an open problem in research, due mainly to the fact that they still present difficulties, such as premature convergence and difficulty to overcome local optimums. Therefore, in this work it is proposed a bio inspired algorithm, who takes as inspiration the mechanism of allostasis.

Allostasis is a biological term which explains how the modifications of specialized organ conditions inside the body allow achieving stability when an unbalance health condition is presented. If a body decompensation happens, according to the allostatic mechanisms, several body conditions compound by blood pressure, oxygen tension and others indexes are proved in order to get a stability state in health.

By using the allostatic mechanisms as a metaphor, it is that we propose a metaheuristic algorithm, which we called Allostatic Optimization (AO). Such algorithm provides a searching procedure that is population-based, under which all the individuals, seen as body conditions, are defined in a multidimensional search space; aforementioned agents are either generated or modified by mean of several evolutionary operators who emulate the various operations used by the allostatic process, whereas an objective function evaluates the individual's capacity (body condition) to reach a steady health state (good solution).

AO is compared against DE, ABC and PSO and, different to them, the proposed algorithm favors the exploration process and eliminates some flaws related with premature convergence. By making such a comparison, it was found that in 57% of the functions the diversity maintained by AO helps the convergence of the algorithm, due to the fact that introduces operators that avoid particle concentration on some regions of the search space, favoring exploration. It was also found that maintaining a high diversity in the population does not guarantee the proper convergence of AO in all the benchmark functions, so a possible future work in this part of the investigation could be a more complete study of the relations among properties of functions, diversity and their relations with adequate convergence of the algorithm.

AO was also used in image segmentation by using a mixture of functions; with the purpose of demonstrate the utility of the algorithm in a particular family of problems. One way to achieve segmentation is by mean of threshold selection, where each pixel that belongs to a determined class is labeled according to the selected threshold, giving as a result pixel groups that share visual characteristics in the image. In this work we use a method based of a mixture of Cauchy functions to approximate 1D histograms of gray level images, and it was found that AO improves the segmentation quality in about 14% when it was compared with Otsu’s method over known image benchmarks.

Moreover, the metaheuristic algorithms DE, ABC and PSO were compared when they were applied to image segmentation by using a method that uses a mixture of Gaussian functions to approximate 1D histograms, because an analysis of such kind was not found in literature; the empirical results were that DE gives the best results in terms of convergence speed as well as quality of segmentation when compared against ground-truth images.