Graph Based Segmentation of Digital Images

Graph Based Segmentation of Digital Images

B.K. Tripathy (VIT University, India) and P.V.S.S.R. Chandra Mouli (VIT University, India)
DOI: 10.4018/978-1-4666-2518-1.ch007


Image Segmentation is the process of dividing an image into semantically relevant regions. The problem is still an active area due to wide applications in object detection and recognition, image retrieval, image classification, et cetera. The problem is challenging due to its subjective nature. Many researchers addressed this problem by exploring graph theoretic principles. The key idea is the transformation of segmentation problem into graph partitioning problem by representing the image as a graph. The aim of this chapter is to study various graph based segmentation algorithms.
Chapter Preview


In machine vision, image processing is usually a costly operation that should nevertheless perform in real time. An efficient segmentation algorithm can help to reduce the amount of visual information that needs to be processed. Human brain is capable of simultaneously analyzing and processing many tasks and this aid in segmenting or dividing the visual image into related objects. The same task over an image by an algorithm is extremely difficult. Image segmentation, as a computational problem, is interesting for at least three reasons: First, there are large numbers of potential applications. Second, image segmentation is interesting because it serves as a test bed for ideas from other fields like machine learning, pattern recognition, physics and engineering. For instance, in its simplest form, image segmentation can be regarded as a clustering problem. Clustering algorithms can often be used in an image segmentation framework, and, conversely, algorithms developed for image processing can be very successful in clustering problems as well. Finally, image segmentation is domain specific. This adds to the challenge because the algorithms which are highly successful for a particular theme may not work properly for other domains. In other words, no common algorithm exists for all types of images.

Key Terms in this Chapter

Cut: set of edges removal of which partitions a graph into two or more components

Graph Partitioning: Dividing a graph into several sub-graphs such that they are disjoint and their union generates the original graph.

Unsupervised: A process which does not depend upon any parameter to be specified for its functioning

A Priori Information: Some information required before a process being carried out

Threshold: A small limiting value with in which the difference can be ignored such that the final analysis is not affected.

Predicate: An expression whose truth value depends upon the specification of the values of the parameters involved.

Domain Specific: Heavily depending upon the application areas

Complete Chapter List

Search this Book: