Segmentation and Tracking Techniques An Overview分割与跟踪技术综述.ppt

Image SegmentationJianbo ShiRobotics InstituteCarnegie Mellon University Taxonomy of Vision Problems Reconstruction: estimate parameters of external 3D world. Visual Control: visually guided locomotion and manipulation. Segmentation: partition I(x,y,t) into subsets of separate objects. Recognition: classes: face vs. non-face, activities: gesture, expression. We see Objects Outline Problem formulation Normalized Cut criterion algorithm The Markov random walks view of Normalized Cut Combining pair-wise attraction repulsion Conclusions Edge-based image segmentation Edge detection by gradient operators Linking by dynamic programming, voting, relaxation, … Montanari 71, ParentZucker 89, GuyMedioni 96, ShaashuaUllman 88 WilliamsJacobs 95, GeigerKumaran 96, Heitgervon der Heydt 93 - Natural for encoding curvilinear grouping - Hard decisions often made prematurely Region-based image segmentation Region growing, split-and-merge, etc... - Regions provide closure for free, however, approaches are ad-hoc. Global criterion for image segmentation Bottom line: It is hard, nothing worked well, use edge detection, or just avoid it. Global good, local bad. Global decision good, local bad Formulate as hierarchical graph partitioning Efficient computation Draw on ideas from spectral graph theory to define an eigenvalue problem which can be solved for finding segmentation. Develop suitable encoding of visual cues in terms of graph weights. Image segmentation by pairwise similarities Image = { pixels } Segmentation = partition of image into segments Similarity between pixels i and j Sij = Sji 0 Segmentation as weighted graph partitioning Pixels i I = vertices of graph G Edges ij = pixel pairs with Sij 0 Similarity matrix S = [ Sij ] is generalized adjacency matrix di = Sj Sij degree of i vol A = Si A di volume of A I Cuts in a graph (edge) cut = set of edges whose removal makes a graph disconnect