Paper Info
Title
Reducing graphs in graph cut segmentation
Abstract
In few years, graph cuts have become a leading method for solving a wide range of problems in computer vision. Howe- ver, graph cuts involve the construction of huge graphs which sometimes do not fit in memory. Currently, most of the max- flow algorithms are impracticable to solve such large scale problems. In the image segmentation context, some authors have proposed heuristics (1, 2, 3, 4) to get round this problem. In this paper, we introduce a new strategy for reducing graphs. During the creation of the graph, before creating a new node, we test if the node is really useful to the max-flow compu- tation. The nodes of the reduced graph are typically located in a narrow band surrounding the object edges. Empirically, solutions obtained on the reduced graphs are identical to the solutions on the complete graphs. A parameter of the algo- rithm can be tuned to obtain smaller graphs when an exact solution is not needed. The test is quickly computed and the time required by the test is often compensated by the time that would be needed to create the removed nodes and the additio- nal time required by the computation of the cut on the larger graph. As a consequence, we sometimes even save time on small scale problems.
Year
DOI
Venue
2010
10.1109/ICIP.2010.5654046
Image Processing
Keywords
Field
DocType
computer vision,graph theory,image segmentation,computer vision,graph cut segmentation,image segmentation context,max-flow algorithms,reduced graph,graph cut,reduction,segmentation
Graph operations,Computer vision,Comparability graph,Indifference graph,Modular decomposition,Computer science,Chordal graph,Theoretical computer science,Artificial intelligence,Graph product,Pathwidth,1-planar graph
Conference
ISSN
ISBN
Citations 
1522-4880 E-ISBN : 978-1-4244-7993-1
978-1-4244-7993-1
6
PageRank 
References 
Authors
0.46
6
3
Name
Order
Citations
PageRank
Lermé, N.160.46
François Malgouyres2204.41
Lucas Létocart311512.37