Genetic Programming for Supervised Figure-ground Image Segmentation

Figure-ground segmentation is a process of separating regions of interest from unimportant backgrounds. It is essential to various applications in computer vi- sion and image processing, e.g. object tracking and image editing, as they are only interested in certain regions of an image and use figure-ground segmenta- tion as a pre-processing step. Traditional figure-ground segmentation methods often require heavy human workload (e.g. ground truth labeling), and/or rely heavily on human guidance (e.g. locating an initial model), accordingly cannot easily adapt to diverse image domains. Evolutionary computation (EC) is a family of algorithms for global optimi- sation, which are inspired by biological evolution. As an EC technique, genetic programming (GP) can evolve algorithms automatically for complex problems without pre-defining solution models. Compared with other EC techniques, GP is more flexible as it can utilise complex and variable-length representations (e.g. trees) of candidate solutions. It is hypothesised that this flexibility of GP makes it possible to evolve better solutions than those designed by experts. However, there have been limited attempts at applying GP to figure-ground segmentation. In this thesis, GP is enabled to successfully address figure-ground segmentation through evolving well-performing segmentors and generating effective features. The objectives are to investigate various image features as inputs of GP, develop multi-objective approaches, develop feature selection/construction methods, and conduct further evaluations of the proposed GP methods. The following new methods have been developed. Effective terminal sets of GP are investigated for figure-ground segmentation, covering three general types of image features, i.e. colour/brightness, texture and shape features. Results show that texture features are more effective than intensities and shape features as they are discriminative for different materials that foreground and background regions normally belong to (e.g. metal or wood). Two new multi-objective GP methods are proposed to evolve figure-ground segmentors, aiming at producing solutions balanced between the segmentation performance and solution complexity. Compared with a reference method that does not consider complexity and a parsimony pressure based method (a popular bloat control technique), the proposed methods can significantly reduce the solution size while achieving similar segmentation performance based on the Mann- Whitney U-Test at the significance level 5%. GP is introduced for the first time to conduct feature selection for figure- ground segmentation tasks, aiming to maximise the segmentation performance and minimise the number of selected features. The proposed methods produce feature subsets that lead to solutions achieving better segmentation performance with lower features than those of two benchmark methods (i.e. sequential forward selection and sequential backward selection) and the original full feature set. This is due to GP’s high search ability and higher likelihood of finding the global optima. GP is introduced for the first time to construct high-level features from primitive image features, which aims to improve the image segmentation performance, especially on complex images. By considering linear/non-linear interactions of the original features, the proposed methods construct fewer features that achieve better segmentation performance than the original full feature set. This investigation has shown that GP is suited for figure-ground image segmentation for the following reasons. Firstly, the proposed methods can evolve segmentors with useful class characteristic patterns to segment various types of objects. Secondly, the segmentors evolved from one type of foreground object can generalise well on similar objects. Thirdly, both the selected and constructed features of the proposed GP methods are more effective than original features, with the selected/constructed features being better for subsequent tasks. Finally, compared with other segmentation techniques, the major strengths of GP are that it does not require pre-defined problem models, and can be easily adapted to diverse image domains without major parameter tuning or human intervention