The paper explores the use of evolutionary techniques in dealing with the image segmentation problem. An image is modeled as a weighted undirected graph, where nodes correspond to pixels, and edges connect similar pixels. A genetic algorithm that uses a fitness function based on an extension of the normalized cut criterion is proposed. The algorithm employs the locus-based representation of individuals, which allows for the partitioning of images without setting the number of segments beforehand. A new concept of nearest neighbor that takes into account not only the spatial location of a pixel, but also the affinity with the other pixels contained in the neighborhood, is also defined. Experimental results show that our approach is able to segment images in a number of regions that conform well to human visual perception. The visual perceptiveness is substantiated by objective evaluation methods based on uniformity of pixels inside a region, and comparison with ground-truth segmentations available for part of the used test images.
Keywords: Image segmentation; evolutionary computation; genetic algorithms; normalized cut.