Image segmentation techniques using graph theory has become a thriving research area in computer vision community in recent years. This chapter mainly focuses on the most up-to-date research achievements in graph-based image segmentation published in top journals and conferences in computer vision community. The representative graph-based image segmentation methods included in this chapter are classified into six categories: minimum-cut/maximum-flow model (called graph-cut in some literatures), random walk model, minimum spanning tree model, normalized cut model and isoperimetric graph partitioning. The basic rationales of these models are presented, and the image segmentation methods based on these graph-based models are discussed as the main concern of this chapter. Several performance evaluation methods for image segmentation are given. Some public databases for testing image segmentation algorithms are introduced and the future work on graph-based image segmentation is discussed at the end of this chapter.
TopIntroduction
In computer vision applications, image segmentation is to separate an image into several regions, of which each has certain properties in terms of predefined rules. These regions can represent objects, parts of an object, or background. The aim of image segmentation is to find the regions of interest (ROI) in an image according to a particular application.
As a very important technique in computer vision, image segmentation has been found in a wide variety of practical applications, such as medical image processing, satellite image analysis, biometric recognition (e.g. human face recognition, fingerprint recognition and palm recognition), traffic control systems (e.g. vehicle number plate recognition, vehicle counting), digital photo editing, robotic vision and so on. Image segmentation approaches include clustering methods (Mignotte, 2008), compression-based methods (Rao, 2009), histogram-based methods (Otsu, 1979), edge detection methods (Senthilkumaran, 2009), region growing methods (Fan, 2005), partial differential equation-based methods (Zhang, 2010), graph-based methods (Boykov, 2001), watershed transformation methods (Grau, 2004) and so on. Among these image segmentation methods, the graph-based approach has attracted many attentions and become one of the most thriving research areas in computer vision in recent years. Meanwhile, many high quality papers on graph-based image segmentation techniques have been published in top journals and conferences in the field of image processing and computer vision. Therefore, this chapter is to gather the information on the most up-to-date graph-based image segmentation research together and give a clear overview of research work on this topic.
The remaining parts of this chapter are arranged as follows. Firstly, the background mathematical knowledge of graph theory is given. We then present the five most representative graph-based models used for image segmentation and classify them into two major groups based on whether interactions of users are involved. The summary of the reviewed methods are illustrated in Table 1. Then, methods used for evaluating segmentation performance are discussed. Some benchmark image segmentation datasets are introduced. Conclusions are given in the end.
Table 1. Summary of the five reviewed graph-based image segmentation methods
| Min-Cut/Max-Flow | Random Walker | MST-Based | Normalized Cut | Isoperimetric Graph Partitioning |
| Applications | Psychological vision, Photo/video editing and medical image segmentation | Medical image segmentation and object/background segmentation | Object segmentation and image segmentation | Natural scene image segmentation | Natural scene image segmentation, medical image and psychological vision |
| Testing Dataset | Gestalt example, medical image and video sequence | 2D/3D medical image and Berkeley dataset | Natural scene image, Columbia COIL image database | Natural scene image, weather radar image | Gestalt example, natural scene image |
| Performance | Less than a second for most 2D images (up to 512*512) | Around 3 seconds on a 256*256 image for an Intel Xeon 2.40GHz with 3GB RAM | None | 2 mins on Intel Pentium 200MHz machines for 100*120 test image | 0.5863 seconds are required on a 1.4GHz AMD Athlon with 512k RAM |
| Time Complexity |  in worst case,  is the number of nodes and  is the number of edges |   is the number of nodes in the graph |  for  graph edges |   is the number of pixels and  is the number of steps for convergence |   is the number of nodes and  is the number of edges |