A SURVEY ON MOVING OBJECT TRACKING IN VIDEO <s> A.Graph cut: <s> We propose a novel approach for solving the perceptual grouping problem in vision. Rather than focusing on local features and their consistencies in the image data, our approach aims at extracting the global impression of an image. We treat image segmentation as a graph partitioning problem and propose a novel global criterion, the normalized cut, for segmenting the graph. The normalized cut criterion measures both the total dissimilarity between the different groups as well as the total similarity within the groups. We show that an efficient computational technique based on a generalized eigenvalue problem can be used to optimize this criterion. We have applied this approach to segmenting static images and found results very encouraging. <s> BIB001 </s> A SURVEY ON MOVING OBJECT TRACKING IN VIDEO <s> A.Graph cut: <s> As a preprocessing step, image segmentation, which can do partition of an image into different regions, plays an important role in computer vision, objects recognition, tracking and image analysis. Till today, there are a large number of methods present that can extract the required foreground from the background. However, most of these methods are solely based on boundary or regional information which has limited the segmentation result to a large extent. Since the graph cut based segmentation method was proposed, it has obtained a lot of attention because this method utilizes both boundary and regional information. Furthermore, graph cut based method is efficient and accepted world-wide since it can achieve globally optimal result for the energy function. It is not only promising to specific image with known information but also effective to the natural image without any pre-known information. For the segmentation of N-dimensional image, graph cut based methods are also applicable. Due to the advantages of graph cut, various methods have been proposed. In this paper, the main aim is to help researcher to easily understand the graph cut based segmentation approach. We also classify this method into three categories. They are speed up-based graph cut, interactive-based graph cut and shape prior-based graph cut. This paper will be helpful to those who want to apply graph cut method into their research. <s> BIB002
In graph cut method the input image is considered as a graph. The segmentation of the objects in the image is co n si d er ed as the graph partitioning problem. For a graph G (image), the vertices (i.e. pixels), V = {u, v, ….. }, are partitioned into N disjoint sub-graphs (regions),A i , A i =V, A i ∩ A j =null , i ≠ j , by pruning the weighted edges of the graph. Based on the similarity of color, brightness and texture, weight between the nodes is computed. The minimum cut criterion for partitioning an image proposed by Wu and Leahy uses color similarity for weight calculation but their method suffers from over segmentation. Yi and Moon BIB002 considered graph cut image segmentation as pixel labeling problems. The label of the foreground object (s-node) is set to be 1 and the background (t-node) is set to be 0. By minimizing the energy-function with the help of minimum graph cut the process of pixel labeling can be done. BIB002 Shi and Malik BIB001 propose the normalized cut to overcome the over segmentation problem. The 'cut 'of their method depends on the sum of weights of the edges in the cut and on the ratio of the total connection weights of nodes in each partition to all nodes of the graph. For imagebased segmentation, the product of the spatial proximity and color similarity defines the weights between the nodes.