Unsupervised and Supervised Image Segmentation Using Graph Partitioning

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.

Image Into Graph Conversion

The very first step of image segmentation based on graph partitioning is to convert images into graphs.

In this chapter, we formally define a graph G as a pair (V,E), where V is a finite set of elements called vertices, and is a set of pairs of vertices called edges. Two vertices v and v’ are said to be adjacent if their pair is an edge, i.e. there exist an edge We also say that the vertices v and v’ are incident to the edge e. The degree of a vertex is the number of edges incident to the vertex. Assuming any ranking sorting function, a vertex v can be referred by its ranked number I in V, and an edge (v,v’) by its vertices ranked numbers, (i,j).

A graph is called regular when each vertex has the same number of neighbors, i.e. when every vertex has the same degree.