A novel approach for Image segmentation is proposed based on mean shift algorithm and normalized cuts algorithm. The normalized cuts algorithm gives good accuracy and better segmentation compared to all most of the existing methods. But it requires high computational power, also it takes huge time. The reason for this is it takes entire image as one matrix and computes. By using Mean Shift algorithm on the original image to partition it into sub graphs we can create image matrices with lower dimensions. The proposed algorithm first applied Mean Shift algorithm to obtain sub graphs. The normalized cuts algorithm is applied on the sub graphs. The experimental results also show that the results obtained by the proposed algorithm are better than results obtained by individual algorithms of Mean shift, normalized cuts.
Keywords |
| Image segmentation, Normalized cuts, Mean shift, Graph partitioning |
INTRODUCTION |
| The process of subdividing an image into its constituent parts and objects is called image segmentation .More precisely
image segmentation is the process of assigning a label to every pixel in an image such that pixels with same label share
certain visual characteristics. The result of image segmentation is a set of segments that collectively cover the image.
There is a large amount of literature on Image segmentation. The various techniques include Thresholding, Edge
detection, Region growing, Split and merge methods, Partial Differential equation based methods, Histogram based
methods, Graphs Partitioning methods, Watershed Transformation, Model based segmentation, Multi Scale
Segmentation etc. |
| Among these techniques graph based techniques gained importance due to its easiness to implement on digital
computer. In these methods the image is treated as a weighted undirected graph. An image can be represented as a
graph which can be represented as G=(V ,E), where the nodes of the graph are the points in the feature space, and an
edge is formed between every pair of nodes. The weight on each edge, w(i,j), is a function of the similarity between
nodes i and j. In grouping, we seek to partition the set of vertices into disjoint sets V1,V2, . . .,Vm, where by some
measure the similarity among the vertices in a set Vi is high and, across different sets Vi, Vj is low. |
| A lot of Image segmentation algorithms based on graph theory were present. Among them the more popular
ones are Normalized Cuts algorithm proposed by Shi and Malik [3], Mean shift algorithm proposed by Comariciu and
Meer [4]. We propose an approach which consider the merits of the both algorithms and produce more efficient result. |
LITEARTURE SURVEY |
| The Image segmentation using graph theory is an emerging field in image processing. A graph can be used to represent
almost any physical situation involving discrete objects and a relationship between them. A graph with a finite number
of vertices as well as edges is called a finite graph, otherwise it is infinite graph. A graph is said to be connected if there
is at least on path between every pair of vertices in the graph. A tree is a connected graph without any circuits. A
spanning tree of a connected graph is a sub graph that contains all the vertices in the original graph. |
| There are many possible partitions of the domain I of an image into subsets, how do we pick the right one? There are
two aspects to be considered here. The first is that there may not be a single correct answer. A Bayesian view is
appropriate there are several possible interpretations in the context of prior world knowledge. The difficulty, of course,
is in specifying the prior world knowledge. Some of it is low level, such as coherence of brightness, color, texture, or
motion, but equally important is mid or high level knowledge about symmetries of objects or object models. The
second aspect is that the partitioning is inherently hierarchical. |
| Prior literature on the related problems of clustering, grouping and image segmentation is huge. The clustering
community has offered us agglomerative and divisive algorithms; in image segmentation, we have region-based merge
and split algorithms. The hierarchical divisive approach that we advocate produces a tree, the dendrogram. While most
of these ideas go back to the 1970s (and earlier), the 1980s brought in the use of Markov Random Fields and variational
formulations The MRF and variational formulations also exposed two basic questions What is the criterion that one
wants to optimize and Is there an efficient algorithm for carrying out the optimization. Many an attractive criterion has
been doomed by the inability to find an effective algorithm to find its minimum greedy or gradient descent type
approaches fail to find global optima for these high-dimensional, nonlinear problems. |
THE NORMALIZED CUT AND MEAN SHIFT ALGORITHM |
| A. The Normalized cut algorithm |
| A graph G(V,E) can be partitioned into two disjoint sets A,B, AUB=V. By simply removing edges connecting the two
parts. The degree of dissimilarity between these two pieces can be computed as total weight of the edges that have been
removed. In graph theoretic language, it is called the cut. |
 |
PROPOSED ALGORITHM BASED ON NCUTS AND MEAN SHIFT ALGORITHMS |
| Normalized cut is proved to be NP-hard problem, when the nodes of graph increases, the solution of the
problem becomes extremely complex, and the calculation of the problem becomes large. Therefore, by incorporating the advantages of the mean shift segmentation and the normalized cut (Ncut) partitioning methods, the proposed
method preprocesses an image by using the mean shift algorithm to form segmented regions, we use region nodes
instead of these regions, then use the Ncut method for region nodes clustering. In many literatures, the Ncut method is
applied directly to image pixels. |
| So for some large images, the weight matrix W is large, which brings huge computational complexity. However, the
proposed method offers a considerable reduction of computational complexity, because the number of image region
nodes is much smaller than that of the pixels, the size of the weight matrix W is significantly reduced. Moreover, the
mean shift algorithm not only removes noise, which limits the accuracy of graph partitioning in the Ncut method, but
also achieves improved segmentation performance. Nonetheless, it will produce the phenomenon of over-segmentation.
The Ncut algorithm is a global clustering method, it can compensate for the phenomenon of over-segmentation, but it is
very dependent on the selection of classification parameter K. however, mean shift is a non-supervised clustering
segmentation method, it is a good solution for solving the drawback of the Nuct. This shows that the combination of the
two methods is also feasible. The proposed method consists of the following steps: |
| 1) An image is preprocessed into multiple separated regions using the mean shift algorithm. |
| 2) These regions are much smaller than the image pixels, so we extracted each region, and use one region node
instead of one region. The information of the region nodes includes features vector information and spatial location. |
| 3) According to the step 2, these region nodes are represented as a weighted undirected graph, the graph as the
Ncut algorithm input, and use these region nodes to construct the weight matrix W, and then use the Ncut method for
region nodes clustering. |
RESULT AND ANALYSIS |
| In this paper, we demonstrate the superiority of the proposed method by comparing the performance of the proposed
approach to existing methods using two images. The weight W(i, j) between regions i and j is defined as |
 (5) |
| where F(i)={ R(i) ,G(i) ,B(i)} is the color vector of region i, if the image is the gray-level image, then F(i) is the gray
value. and X(i) is the spatial location of region node i. in this paper, we defined the F(i) is the average gray of the
region i, and the X(i) is the center of the region i. in this case, the select of F(i) and X(i) are more representative. |
 |
| |
 |
| The fig 2 shows the results of normalized cuts algorithm and mean shift algorithm separately and the result obtained
when both the algorithms are combined to form the proposed algorithm. |
 |
 |
| Table 1 gives the edge weights corresponding to the image 2(a). To calculate the edge weights we have used the
standard formula. Table 2 gives the comparisons between Normalized cuts algorithm, Mean shift algorithm and the
proposed algorithm. |
CONCLUSION |
| In this paper a novel image segmentation algorithm has been proposed and designed based on the conventional mean
shift algorithm and Ncut algorithm. The effectiveness and robustness of the proposed algorithm have verified by some
experimental results to express an improved performance compared to the Ncut algorithm. Also the significant
reduction to the computational cost of the proposed algorithm in the experiments is favourable for practical
applications. |
References |
- R.Balakrishnan, K.Ranganathan, âÃâ¬ÃÅA Text Book of Graph TheoryâÃâ¬ÃÂ, second edition springer
- Rafael C.Gonzalaez, Richard E.Woods, âÃâ¬ÃÅDigital Image Processing âÃâ¬ÃÂ, second edition pearson
- J. Shi and J. Malik, âÃâ¬ÃÅNormalized cuts and image segmentation,âÃâ¬Ã IEEE Trans. on PAMI, vol. 22, no. 8, pp. 888-905, 2000
- D. Comariciu and P. Meer, âÃâ¬ÃÅMean shift: a robust approach toward feature space analysis,âÃâ¬Ã IEEE Trans. on PAMI, vol. 24, no. 5, pp. 603-619, 2002.
- J. Carballido-Gamio, S. J. Belongie, and S. Majumdar, âÃâ¬ÃÅNormalized cuts in 3-D for spinal MRI segmentation,âÃâ¬Ã IEEE Trans. on Medical Imaging, vol. 23, no. 1, pp. 36-44, 2004.
- Y. Cheng, âÃâ¬ÃÅMean shift, mode seeking, and clustering,âÃâ¬Ã IEEE Trans. on Pattern Analysis and Machine Intelligence, vol. 17, no. 8, pp. 790- 799,1995.
- J. Shi and J. Malik, âÃâ¬ÃÅMotion segmentation and tracking using normalized cuts,âÃâ¬Ã Proceedings of the Sixth International Conference on Computer Vision (ICCV), Bombay, India, pp. 1154-1160, 1998.
|
Menu