Different graph theoretic approaches are prevalent in the field of image analysis. Graphs provide a natural representation of image pixels exploring their pairwise interactions among themselves. Graph theoretic approaches have been used for problem like image segmentation, object representation, matching for different kinds of data. In this chapter, we mainly aim at highlighting the applicability of graph clustering techniques for the purpose of image segmentation. We describe different spectral clustering techniques, minimum spanning tree based data clustering, Markov Random Field (MRF) model for image segmentation in this respect.
TopIntroduction
Image analysis broadly refers to the techniques for extracting meaningful high level visual information from images. For example, given an image with several blob-like structures (Figure 1), the following questions are likely to arise:
Figure 1.
A typical image with multiple blobs
- •
How many blobs are present in the image?
- •
What are the boundary pixels of each blob?
- •
Are the blobs of same kind?
- •
Do the blobs represent any natural clustering?
And the questions go on. However, in order to answer most of such questions, the first and foremost operation that needs to be performed on the image is undoubtedly image segmentation. Loosely speaking, segmentation is performed on an image to group the spatially consistent and spectrally or texturally homogeneous pixels together. The literature for image segmentation is very rich (Pal & Pal, 1993). There are hundreds of techniques for image segmentation involving thresholding, region merging, clustering jointly in the spatial-spectral domain etc. The main topic of the chapter, which is graph based image analysis provides an easy way of segmenting the image by exploiting the strengths of all the aforementioned techniques conveniently. This is one of the examples of the application of graphs in image analysis, which is arguably the most important one.
Apart from the domain of image analysis, graph based algorithms are very popular in all brunches of machine learning including:
- •
Classification (Goldberg, Zhu, & Wright, 2007),
- •
Manifold ranking (Yang, Zhang, Lu, Ruan, & Yang, 2013; Singer, 2006),
- •
Domain adaptation (Banerjee, Bovolo, Bhattacharya, Bruzzone, Chaudhuri, & Buddhiraju, 2015),
- •
Text summarization (Patil, Pharande, Nale, & Agrawal, 2015; Erkan & Radev, 2004) to name a few.
In image analysis, graphs are used for image filtering (Bougleux, Elmoataz, & Melkemi, 2007; Awate & Whitaker, 2006), morphology (Ta, Elmoataz, & Lézoray, 2011) in addition to the problem of image segmentation.
Going by the rich application domains and mathematical foundation, the highlight of the chapter will primarily be on the graph based algorithms for image segmentation. We have selected image segmentation as the task of segmentation is very important in computer vision as it bridges the semantic gap between low level pixels and high level semantic image objects. It is also one of the key stages towards visual scene understanding. Even after so many years from the inception of the topic, segmentation is still considered to be an open problem. Graph based image segmentation techniques allow joint spectral-spatial modeling of the images and pose the segmentation problem as an optimization problem. The main advantage of such methods over other image segmentation techniques is that the graph based segmentation methods are capable of preserving the image discontinuities while producing a smooth segmentation result. There are sophisticated graph algorithms which allow to model the segmentation problem from different perspectives. For example: