Recent Advances on Graph-Based Image Segmentation Techniques

Recent Advances on Graph-Based Image Segmentation Techniques

Chao Zeng (University of Technology-Sydney, Australia), Wenjing Jia (University of Technology-Sydney, Australia), Xiangjian He (University of Technology-Sydney, Australia) and Min Xu (University of Technology-Sydney, Australia)
Copyright: © 2013 |Pages: 15
DOI: 10.4018/978-1-4666-3994-2.ch065
OnDemand PDF Download:


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.
Chapter Preview


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-FlowRandom WalkerMST-BasedNormalized CutIsoperimetric Graph Partitioning
ApplicationsPsychological vision, Photo/video editing and medical image segmentationMedical image segmentation and object/background segmentationObject segmentation and image segmentationNatural scene image segmentationNatural scene image segmentation, medical image and psychological vision
Testing DatasetGestalt example, medical image and video sequence2D/3D medical image and Berkeley datasetNatural scene image, Columbia COIL image databaseNatural scene image, weather radar imageGestalt example, natural scene image
PerformanceLess 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 RAMNone2 mins on Intel Pentium 200MHz machines for 100*120 test image0.5863 seconds are required on a 1.4GHz AMD Athlon with 512k RAM
Time ComplexityO(mn2) in worst case, n is the number of nodes and m is the number of edgesO(n), n is the number of nodes in the graphO(mlogm) for m graph edgesO(mn), n is the number of pixels and m is the number of steps for convergenceO(m+nlogn), n is the number of nodes and m is the number of edges

Complete Chapter List

Search this Book: