A survey of graph theoretical approaches to image segmentation

Bo Peng, Lei Zhang, Dapeng Zhang

Research output: Journal article publicationReview articleAcademic researchpeer-review

300 Citations (Scopus)


Image segmentation is a fundamental problem in computer vision. Despite many years of research, general purpose image segmentation is still a very challenging task because segmentation is inherently ill-posed. Among different segmentation schemes, graph theoretical ones have several good features in practical applications. It explicitly organizes the image elements into mathematically sound structures, and makes the formulation of the problem more flexible and the computation more efficient. In this paper, we conduct a systematic survey of graph theoretical methods for image segmentation, where the problem is modeled in terms of partitioning a graph into several sub-graphs such that each of them represents a meaningful object of interest in the image. These methods are categorized into five classes under a uniform notation: the minimal spanning tree based methods, graph cut based methods with cost functions, graph cut based methods on Markov random field models, the shortest path based methods and the other methods that do not belong to any of these classes. We present motivations and detailed technical descriptions for each category of methods. The quantitative evaluation is carried by using five indices - Probabilistic Rand (PR) index, Normalized Probabilistic Rand (NPR) index, Variation of Information (VI), Global Consistency Error (GCE) and Boundary Displacement Error (BDE) - on some representative automatic and interactive segmentation methods.
Original languageEnglish
Pages (from-to)1020-1038
Number of pages19
JournalPattern Recognition
Issue number3
Publication statusPublished - 1 Mar 2013


  • Graph cut
  • Graph theoretical methods
  • Image segmentation
  • Minimal spanning tree

ASJC Scopus subject areas

  • Software
  • Signal Processing
  • Computer Vision and Pattern Recognition
  • Artificial Intelligence


Dive into the research topics of 'A survey of graph theoretical approaches to image segmentation'. Together they form a unique fingerprint.

Cite this