Irrefutably Normalized Cuts (Ncut) Algorithms

Abstract: Irrefutably Normalized Cuts (Ncut) is one of the most popular segmentation algorithms in computer vision. Inspite of its computational complexity, it has been applied to a wide range of segmentation tasks in computer vision for achieving good segmentation results. The difficulty in Ncut algorithm lies in handling images with high resolution and predefined number of segments which results in increasing the complexity of the algorithm. In this paper, the drawbacks of Ncut algorithm are studied and an efficient methodology for image segmentation is proposed using grid based Ncut segmentation and merging algorithm. The proposed algorithm is successful in two aspects, one in reducing the time complexity and second in automatically determining the number of image segments. The proposed methodology is implemented in three phases which includes preprocessing, segmentation and merging phases. Experimental results done on images of varying sizes proved to be efficient in reducing the computational complexity and thus increasing the performance of segmentation when compared to standard Ncut algorithms.

Keywords: Image segmentation, normalized cuts, grid clustering, color identification.

1 Introduction

Image segmentation, dividing the image into meaningful segments, is often an essential first step to many computer vision problems and the results of many of these problems rely on the quality of the segmentation. Image segmentation is therefore an important topic that has received much attention and a great variety of segmentation methods has been proposed by the researchers. The goal of segmentation is to simplify and/or change the representation of an image into something that is more meaningful and easier to analyze. Image segmentation is typically used to locate objects and boundaries in images. More precisely, image segmentation is the process of assigning a label to every pixel in an image such that pixels with the same label share certain visual characteristics. The result of image segmentation is a set of segments that collectively cover the entire image, or a set of contours extracted from the image. Each of the pixels in a region is similar with respect to some characteristic or computed property, such as color, intensity, or texture. Adjacent regions are significantly different with respect to the same characteristics. Some of the practical applications of image segmentation are Medical imaging, Study of anatomical structure, Locate objects in satellite images, Face recognition, Fingerprint recognition, Traffic control systems, image retrieval, image annotation, object recognition, blobs and so on.

Some popular methods for image segmentation are clustering methods, histogram-based or thresholding methods, edge detection, partial differential Equation (PDE) methods, region growing methods, artificial neural networks and graph-based methods [1,2,3]. Mostly used algorithms based on these methods [4,5,6,7,8,9] are Histogram based threshold, Region splitting and merging, Color based segmentation, Fast segmentation, K ' means clustering, EM algorithm, CLUST algorithm, Hierarchical clustering, Partitional clustering, Watershed segmentation, graph cut based segmentation, Normalized cut ,EDISON and so on. Among these different approaches, graph-based segmentation methods provide an intuitive framework for image segmentation. Graph-based segmentation methods [1,10,11,12] are normalized cuts, random walker, minimum cut, isoperimetric partitioning and minimum spanning tree-based segmentation, spectral min cut, total variation etc. In these methods, the image is modeled as a weighted, undirected graph. Usually a pixel or a group of pixels are associated with nodes and edge weights define the similarity between the neighborhood pixels. The graph (image) is then partitioned according to a criterion designed to model "good" clusters. Each partition of the nodes (pixels) output from these algorithms are considered an object segment in the image.

In this paper, we will explore improving the Normalized Cut Algorithm, a commonly used graph-based image segmentation algorithm. The Normalized Cut Algorithm uses a global criterion, the normalized cut, to segment global features of a graph-based image. First, we introduce the Normalized Cut algorithm and briefly discuss its theory and implementation. Second, we propose a methodology to overcome the drawbacks of Ncut algorithm that will add flexibility to the Ncut algorithm. Third, we evaluate the segmentation results of the modified Normalized Cut algorithm. Fourth, we will assess the robustness of both the original and our proposed modified Normalized Cut algorithms on high resolution images. Last, we will discuss our results and close with future work.

2 Normalized Cut

We assume G = (V, E) as an undirected graph where V is the set of nodes and E is the set of edges (i, j). Two nodes i, j are adjacent, represented by i j, if there exists an edge linking i and j, and the weight associated to each edge (i, j) is represented by w (i, j). The mathematical representation for this graph [13] is given as follows:

Similarity matrix: A similarity matrix A is a representation for an undirected weighted graph where each entry value a (i, j) is the edge weight w (i, j) linking a pair of nodes. The weights are given by a function that maximize the similarity between nodes i and j.

Weighted degree matrix: Let d (i) = ' w (i, j) be the total connection from node i to all its neighbor nodes. Then the weighted degree matrix D is the diagonal matrix with d on its diagonal.

Laplacian matrix: The laplacian matrix of a graph G is computed from L (G) = (D ' A), where D is the weighted degree matrix and A is the similarity matrix.

The Ncut approach uses the algebraic properties of the laplacian matrix to separate the nodes according to the dissimilarity between them which is called cut:

cut (G_1,G_2 )= '_(i'G_(1,) j'G_2)''wij ' (1)

where G1 and G2 are two disjoint sets in a graph. Instead of using the total edge weight connection, this method computes the cut cost as a fraction of the total edge connections to all the nodes in the graph: NCut(G1,G2)=(cut(G1,G2))/(vol(G1,V)) + (cut(G1,G2))/(vol(G2,V)) (2)

where vol(G, V ) is the total connection from nodes in the set G with all nodes in V . Expanding this equation the following equation can be found:

'min'_x NCut(x)= 'min'_y (y^T (D-A)y)/(y^T Dy) (3)

This equation, called Rayleigh quotient, has a property that it can be minimized by the smallest eigenvector x0 of the Rayleigh quotients matrix (in this case, the Laplacian matrix) and its minimum value is the corresponding eigen value ??0

So, the Normalized cut can be minimized by solving a generalized eigenvalue system as shown below.

(D ' A)y = ??Dy (4)

Because of the 'rst Laplacians matrix smallest eigenvalue is 0, the second smallest eigenvalue is the real valued solution to the normalized cut problem and its corresponding eigenvector can tell exactly how to partition the graph just by separating the nodes represented by the positive values in the eigenvector from the negative ones. Normalized cuts implementation in image segmentation has a generic framework that can be used with many different features and affinity formulations which provides regular segments. But this framework has certain disadvantages in choosing the fixed number of regions prior segmentation and also in its computation. An image [14] that has a size of m ?? n pixels will require the normalized cuts algorithm to form the A matrix with a size of (m ?? n) ?? (m ?? n). For example, an image with a size of 120 ?? 90 will end up computing a 10800 ?? 10800 adjacency matrix, which is considered a very large matrix for a computer to solve for eigenvalues. This indicates the size of A is proportionally to the square of the image size. With the current digital camera that can produce an image with image size more than 10 mega pixels, doing image segmentation using normalized cuts algorithm in this image size would be impractical.

To address these problems, we propose the normalized parameter that replaces k (number of regions) and works for all images without having to be changed and an algorithm that enables it to run efficiently in O(NlogN) time (N represents the number of pixels in the image), without compromising on the performance. Experiments on a wide variety of images demonstrate the ability of the algorithm to achieve accurate results in an efficient manner.

3 Proposed Methodology

In order to reduce the computational complexity and to achieve efficiency, a three phase approach is adapted. In the first phase, a whole image is considered as grids and computes the number of regions to be segmented with the help of color identification algorithm. In the second phase, Ncut algorithm is computed on selected grids. And in the final phase, merges all the regions using merging algorithm to produce good segmentation. The method has been tested on real data showing good performance and improvements compared to standard normalized cuts.

3.1 Phase 1- Image Grids and computing number of regions:

In today's scenario the high definition images are chosen for more clarity and quality. Considering such high resolution images in real time computing it is very difficult. Resizing the image is a bad idea as it loses many properties. In order to reduce computational complexity, the part of an image is considered rather than a whole image. Computing the eigenvalues and similarity matrices on the whole image is burdensome. Therefore we divide the image into equal grids (Ii, Ii+1 .......... In). Each grid (Ii) is considered as an image and applied Ncut algorithm on each of them individually. Not all the grids require segmentation. So, first the algorithm determines whether the grid requires segmentation or not. If it doesn't require segmentation it is considered as region (Ri) and the same continues it with neighbor grids. Suppose if the grid requires segmentation, compute the number of regions (k clusters) to be segmented with the color based threshold.

3.2 Phase 2 ' Normalized cut segmentation:

Consider only the grids which require segmentation with k clusters. Normalized cuts algorithm is then performed to segment out k number of clusters for the particular grid. Applying normalized cut on grids rather than whole image reduces the complexity of calculating eigenvalues. In this segmentation phase, all the regions may be not closed regions, some might be occluded due to preliminary grid segmentation. Even though they are either occluded or completed regions, all the regions are considered and labeled as Ri to Rn.

3.3 Phase 3 ' Merging algorithm:

For each region Ri take its neighbor regions Ri+1 and check the similarity between the regions. If the regions are similar merge the two similar regions and check to its neighboring region and repeat until it finds the dissimilar region. Finally, merging all the similar regions in an image completes the image segmentation.

3.3.1 Similarity Criterion:


J. Shi and J. Malik, 'Normalized Cuts and Image Segmentation' IEEE Transactions on Pattern Analysis and Machine Intelligence, volume 22(8), 2000

D.L. Pham, C. Xu, and J.L. Prince, 'Current Methods in Medical Image Segmentation", Annual Review Biomedical Engineering, vol. 2, pp. 315-317, 2000.

T. Zuva, O.O. Olugbara, S.O. Ojo, and S.M. Ngwira, 'Image Segmentation, Available Techniques, Development and Open Issues", Canadian Journal on Image Processing and Computer Vision, vol .2, no. 3, March 2011.

Yu-Hsiang Wang, 'Tutorial: Image Segmentation',

Hanan Al-Jubouri, Hongbo Du, Harin Sellahewa, 'Adaptive Clustering based Segmentation for Image Classification', 2013 5th CEEC, university of ESSEX, UK, IEEE, pages 128 -133.

Francisco J. Estrada ' Allan D. Jepson, 'Benchmarking Image Segmentation Algorithms', Int J Comput Vis (2009) 85: 167'181 DOI 10.1007/s11263-009-0251-z, Springer Science Business Media, LLC 2009.

Martin, D., & Fowlkes, C. (2001). The Berkeley segmentation database and benchmark. Computer Science Department, Berkeley University.

H. Al-Jubouri, H. Du, and H. Sellahewa, "Applying Gaussian Mixture Model on discrete cosine features for image segmentation and classification," Computer Science and Electronic Engineering Conference (CEEC), 2012 4th, pp. 194-199, 2012.

C. Pantofaru, M. Hebert, 'A comparison of image segmentation algorithms', Tech. Rep. CMU-RI-TR-05-40, CMU (2005). 2, 14.

Leo Grady (2006): "Random Walks for Image Segmentation", IEEE Transactions on Pattern Analysis and Machine Intelligence, pp. 1768'1783, Vol. 28, No. 11

Z. Wu and R. Leahy (1993): "An optimal graph theoretic approach to data clustering: Theory and its application to image segmentation", IEEE Transactions on Pattern Analysis and Machine Intelligence, pp. 1101'1113, Vol. 15, No. 11

Leo Grady and Eric L. Schwartz (2006): "Isoperimetric Graph Partitioning for Image Segmentation", IEEE Transactions on Pattern Analysis and Machine Intelligence, pp. 469'475, Vol. 28, No. 3

Marco and Roberto, 'Image Segmentation Using Watershed and Normalized Cut',

Wei Yeang Kow, Wei Leong Khong, Chung Fan Liau, 'An Image Segmentation using Normalized Cuts in Multistage Approach', IJSSST, Vol. 13, No.3B.

Source: Essay UK -

Not what you're looking for?


About this resource

This Information Technology essay was submitted to us by a student in order to help you with your studies.


No ratings yet!

Word count:

This page has approximately words.



If you use part of this page in your own work, you need to provide a citation, as follows:

Essay UK, Irrefutably Normalized Cuts (Ncut) Algorithms. Available from: <> [22-02-19].

More information:

If you are the original author of this content and no longer wish to have it published on our website then please click on the link below to request removal:

Essay and dissertation help