Image Segmentation: Theories and Technology

Theoretical Concepts and Technical Aspects on Image Segmentation

Image segmentation is a very significant area in computer vision. Image segmentation, partitions an image into multiple regions based on certain similarity constraints. This acts as the pre-processing stage in several image analysis problems like image compression, image recognition etc. Segmentation is the vital part for the successful extraction of image features and classification. Image segmentation can be defined as the partition of an image into several regions or categories. These regions can be similar in any features like color, texture, intensity etc. Every pixel in an image is assigned to any one of the categorised region. Quality of segmentation is described as pixels in the same region are similar in some characteristics whereas pixels in different regions differ in the characteristics. The segmentation process includes restoration, enhancement, and representation of the image data in the required form.

Image Segmentation Techniques

Image segmentation techniques can be broadly classified based on certain characteristics. Basic classifications of image segmentation techniques include local and global image segmentation techniques. The segmentation method that is concerned with segmenting specific parts or region of image is known as local image segmentation. The segmentation method that is concerned with segmenting the whole image, consisting of very large number of pixels is known as global image segmentation.

The next category of image segmentation method is based on the properties of the images to be segmented. It is categorised as discontinuity detection based approach and similarity detection based approach. In discontinuity detection based approach, the segmentation is based on discontinuities in the images like edge based segmentation and similarity detection based approach is based on similarity of regions like Threshold based, Region growing, Region Splitting and Merging etc. The segmentation technique which is based on the information of the structure of required portion of the image is known as structural segmentation. Most of the segmentation methods are stochastic type, where the segmentation is completely depended upon the discrete pixel values of the image.

Threshold based segmentation method is the simplest method of segmentation. The image pixels are segmented based on the intensity level. This kind of segmentation is more applicable for images where the objects are lighter than the background. This method is based on prior knowledge of the image features. There are mainly three types of threshold based segmentation. Global Thresholding: This method is done using a proper threshold value. The threshold value will be constant for the whole image. Output of the image is based on this threshold value. Variable Thresholding: In this type of segmentation method the value of threshold can vary in a single image. Multiple Thresholding: In this kind of thresholding, the output of segmentation is based on multiple threshold values. Threshold values can be computed from image histograms. In [1], threshold based level set approach based on threshold based segmentation and fast marching method [2] for medical image segmentation is proposed. To improve the image acquisition process in computer vision, threshold based segmentation method based on entropy criteria and genetic algorithm is mentioned in [3].

Edge based segmentation method is based on the sudden change of intensity values in an image. In image processing, object boundaries are represented using edge. Edge based segmentation works by identifying the region of abrupt intensity change in an image [4]. Mainly there are two types of edge based segmentation methods. Grey Histogram Technique: In this method the foreground is separated from the background based on a threshold value. Choosing the correct threshold value creates a problem. Gradient Based Method: Gradient can be defined as the first derivate of the image near the edge. Higher change in the intensity values between two regions is depicted by the high value of gradient magnitude. In order to perform multi scale image segmentation an edge based auto threshold generating method is introduced in [5]. Another method for edge detection using variance filter is introduced in [6].

Theory based segmentation method uses derivatives from several fields. Several types of this kind of algorithm includes, Clustering based segmentation: In this method clusters are formed based on the similarity criteria (size, color, texture etc). Methods include k-means clustering, fuzzy clustering, hard clustering etc [7]. Artificial Neural Network: In this method the neuron represents the pixels and segmentation is performed with the help of trained images. Methods using Wavelet Decomposition and Self Organization Map of artificial neural networks are proposed [8].

Region based segmentation [13] methods are similar to edge based segmentation. The advantage of region based segmentation upon edge based is that, the former is more immune to noise. In this method, the region of an image is either splitted or merged into areas based on similarity. Region Growing: the collection of pixels is grouped into a region with similar properties [9]. Region Splitting and Merging: Here the image is further subdivided into several regions based on some pre-defined criteria. Graph cut image segmentation is a very significant technique of segmentation under region based segmentation. Several techniques of region growing methods include techniques that combine edge and region based information using morphological watershed algorithms [10]. In this method, initially a noise filter along with magnitude gradient is used and pre segmentation is performed through region merging. A region similarity graph is then produced and final segmentation is performed using Multi Class Normalized Cut. This technique overpowers the Spectral clustering method. As the method mentioned is a time consuming task, new method is presented [11]. For the purpose of detecting objects sharply, least square method is used for region based segmentation. Here the local information is also considered by calculating the weight matrix. This segmentation technique is optimum and fast.

Graph-cut Image Segmentation

As mentioned in the above methods, the techniques either use the region information or use the boundary information [12]. This results in limited segmentation. In graph cut segmentation optimal result for energy function is computed and segmentation is based on that result.

Basics of Graph-Cut

An undirected graph, set of vertices and a set of edges, are considered. Vertex represents the pixels in an image and edges denote the connection between the adjacent pixels. There exists a source and sink node which holds the foreground and background respectively. In graph cut method, each edge is assigned with a non-negative weight which coins the term cost. [12] A graph cut is actually the partitioning of the edge set into several component sets. Graph cut method can be either min cut or max cut. Min cut can be defined as cut through minimum cost and max cut can be defined as the cut through maximum cost. That is after the cut performed, the vertices are divided into two sets, source and sink, which holds the foreground and background pixels respectively.

Implementing graph cut method assigns value 1 to the pixels in the foreground and 0 to the pixels in the background. This is achieved through minimum graph cut method by minimizing the energy function.

Types of Graph Cut Based Algorithm

The graph cut based segmentation can be mainly divided into three types. They are Speed-up based graph cut, Interactive based graph cut and Shape prior based graph cut. The speed up based graph cut method is used to improve the speed of the graph cut method through parallel computing. Earlier implementation was based on CUDA code [14]. The best way to speed up the computational time is to reduce the number of graph nodes while reconstructing the graph [15] [16]. Another method used for speed up based graph cut method is clustering based graph cut. Clustering based graph cut is based on reducing the number of nodes by grouping similar pixels into a single cluster and treating a cluster as a node. Watershed based method is another important speed up based approach where, gradient images are considered and the concept of catchment basins are used [15].

Interactive based graph cut plays a very important role in segmentation of natural images and the situations where the segmentation requires high precision. In this kind of methods the seed points are selected and then segmentation is performed based on these points. Several methods are performed using the concept of bounding box, where the centre portion of the bounding box corresponds to the object and histogram is constructed. The area outside the bounding box is considered as the background region [17] [18]. Certain interactive segmentation is performed by choosing both the foreground and background region together. Iterative interactive graph cut segmentation is also performed.

Shape prior based graph cut segmentation finds its importance where the image to be segmented is affected by noise, diffuse edge, obstructed objects etc. In this kind of segmentation, the shape information is included as the energy function [19] [20].

Case Study

In this chapter a graph based image segmentation method is explained. The efficient graph based image segmentation method initially considers the input image as a graph. The pixel values are considered as the nodes of the graph and edge is drawn between the adjacent pixels. The edge weight is represented by the difference between adjacent pixels. Initially, the considered edge set is sorted in the increasing order of edge weight. The segmentation process actually segments the entire vertices set into disjoint sets based on some similarity function. The vertex set is initially randomly partitioned into several component sets. This is considered as the initial segmentation.

The vertices producing the largest edge weight is considered first. Let the two vertices be v₁ and v₂. Then check whether these two vertices belong to disjoint component sets in the previous segmentation (initial segmentation). If the two vertices are in disjoint component sets then compare the edge weight connecting these vertices to the internal difference of these two component sets. If the weight of the edge connecting these vertices is smaller when compared to the internal difference, then these two components are merged. Otherwise, it is neglected. On continuing these steps till the smallest edge weight, a final segmentation of the input image is obtained.

Expected Outcome

In the proposed chapter, an exhaustive review on image segmentation such as threshold based, edge based, graph based and region based segmentation will be included. The various approaches employed for graph cut segmentation include interactive graph cut, efficient graph cut, shape based graph cut and speed up based graph cut. The chapter would conclude with results on a list of benchmark images. At the enclosure of the chapter, open research problems will be discussed.