Name
Abstract | ||
|---|---|---|
Recently, unsupervised image segmentation has become increasingly popular. Starting from a superpixel segmentation, an edge-weighted region adjacency graph is constructed. Amongst all segmentations of the graph, the one which best conforms to the given image evidence, as measured by the sum of cut edge weights, is chosen. Since this problem is NP-hard, we propose a new approximate solver based on the move-making paradigm: first, the graph is recursively partitioned into small regions (cut phase). Then, for any two adjacent regions, we consider alternative cuts of these two regions defining possible moves (glue & cut phase). For planar problems, the optimal move can be found, whereas for non-planar problems, efficient approximations exist. We evaluate our algorithm on published and new benchmark datasets, which we make available here. The proposed algorithm finds segmentations that, as measured by a loss function, are as close to the ground-truth as the global optimum found by exact solvers. It does so significantly faster then existing approximate methods, which is important for large-scale problems. |
Year | DOI | Venue |
|---|---|---|
2014 | 10.1109/CVPR.2014.17 | Computer Vision and Pattern Recognition |
Keywords | Field | DocType |
approximation theory,computational complexity,graph theory,image segmentation,optimisation,np-hard problem,approximate solver,cut edge weights,edge-weighted region adjacency graph,ground-truth,loss function,move-making paradigm,multicut partitioning,planar problems,superpixel segmentation,unsupervised image segmentation,correlation clustering,move-making algorithms,multicut,optimization,np hard problem,approximation algorithms,benchmark testing,ground truth,labeling | Adjacency list,Mathematical optimization,Scale-space segmentation,Correlation clustering,Computer science,Segmentation-based object categorization,Image segmentation,Solver,Recursion,Maximum cut | Conference |
ISSN | Citations | PageRank |
1063-6919 | 4 | 0.40 |
References | Authors | |
0 | 5 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Thorsten Beier | 1 | 69 | 5.79 |
| Thorben Kroeger | 2 | 129 | 6.37 |
| Jörg H. Kappes | 3 | 202 | 12.16 |
| Ullrich Koethe | 4 | 249 | 22.37 |
| Fred A. Hamprecht | 5 | 962 | 76.24 |