Image segmentation is an important research area in computer vision and its applications in different disciplines, such as medicine, are of great importance. It is often one of the very first steps of computer vision or pattern recognition methods. This is because segmentation helps to locate objects and boundaries into images. The objective of segmenting an image is to partition it into disjoint and homogeneous sets of pixels. When segmenting an image it is natural to try to use graph partitioning, because segmentation and partitioning share the same high-level objective, to partition a set into disjoints subsets. However, when using graph partitioning for segmenting an image, several big questions remain: What is the best way to convert an image into a graph? Or to convert image segmentation objectives into graph partitioning objectives (not to mention what are image segmentation objectives)? What are the best graph partitioning methods and algorithms for segmenting an image? In this chapter, the author tries to answer these questions, both for unsupervised and supervised image segmentation approach, by presenting methods and algorithms and by comparing them.
Top1. Introduction
Image segmentation aims to partition an image into a set of regions which should be at the same time visually distinct and uniform regarding some properties such as gray level, color, shape or texture. Segmentation is the very first step and a key issue in many computer vision domains such as object recognition, event detection, video tracking, image restoration or scene reconstruction. Image segmentation is used in many applications such as medicine, robotic, industry, etc, where the quality of the final result greatly depends on the quality of the first step: image segmentation.
Image segmentation problems can be modeled by graphs and then, graph partitioning algorithms may be used to find the desired image regions. This modeling can be made either trough an unsupervised approach or trough a supervised one. In the latter, the user has to seed the parts of the image to be segmented, on the other the user had at most to know the number of parts in which the image should be segmented. The graph partitioning image segmentation process is divided into three main steps:
- 1.
Image into graph conversion
- 2.
Graph partitioning optimization
- 3.
Partition projection to the image
The first step converts an image, which is either in color or black and weight, textured or not, small or huge, into a graph. The objectives of this first step are to translate both local and global image information into the graph, like grayscale differences, texture information, patterns, etc. The second steps partitions the resulted graph by optimizing an objective function. The third and last step projects the partition of the graph directly onto the original image. Of course, the partitioning step is very sensitive to the image into graph conversion. A poor graph weighting and structure results to a poor segmentation even if the partition is optimal regarding the objective function. Moreover, it should be noticed that the objective function can not reflect perfectly the image segmentation problem.
What constitutes a good image segmentation? Haralick and Shapiro propose four criteria which have become a classical standard for image segmentation evaluation (Haralick & Shapiro, 1985):
- 1.
Intra-Region Uniformity: Regions should be uniform and homogeneous with respect to some characteristic(s).
- 2.
Inter-Region Disparity: Adjacent regions should have significant differences with respect to the characteristic on which they are uniform.
- 3.
Region interiors should be simple and without holes.
- 4.
Boundaries should be simple, not ragged, and be spatially accurate.
Criteria 3 and 4 measure semantic cues of objects, such as shape.
Image segmentation objective functions often refer to one or more of these criteria. Those objective functions combined in some arrangement intra-region uniformity and inter-region disparity either by making a weighted sum of them or by dividing them.
This chapter is composed of four sections: This first introductive section; the second section, which explains how to convert an image into a graph. It also presents the classical methods for doing this conversion, and what can be done to improve them. The third section details the unsupervised image segmentation approach based on graph partitioning. It details two main graph partitioning methods: spectral and multilevel methods. The fourth section presents the supervised image segmentation approach based on graph partitioning and shows several methods to solve it. The last section provides discussions, perspectives and concluding remarks.
Top2. Image Into Graph Conversion
The very first step of image segmentation based on graph partitioning is to convert images into graphs.