Abstract | ||
---|---|---|
In the last decade, graph-cut optimization has been popular for a variety of labeling problems. Typically, graph-cut methods are used to incorporate smoothness constraints on a labeling, encouraging most nearby pixels to have equal or similar labels. In addition to smoothness, ordering constraints on labels are also useful. For example, in object segmentation, a pixel with a "car wheel" label may be prohibited above a pixel with a "car roof" label. We observe that the commonly used graph-cut \alpha-expansion move algorithm is more likely to get stuck in a local minimum when ordering constraints are used. For a certain model with ordering constraints, we develop new graph-cut moves which we call order-preserving. The advantage of order-preserving moves is that they act on all labels simultaneously, unlike \alpha-expansion. More importantly, for most labels \alpha, the set of \alpha-expansion moves is strictly smaller than the set of order-preserving moves. This helps to explain why in practice optimization with order-preserving moves performs significantly better than \alpha-expansion in the presence of ordering constraints. We evaluate order-preserving moves for the geometric class scene labeling (introduced by Hoiem et al.) where the goal is to assign each pixel a label such as "sky," "ground," etc., so ordering constraints arise naturally. In addition, we use order-preserving moves for certain simple shape priors in graph-cut segmentation, which is a novel contribution in itself. |
Year | DOI | Venue |
---|---|---|
2010 | 10.1109/TPAMI.2009.120 | IEEE Trans. Pattern Anal. Mach. Intell. |
Keywords | Field | DocType |
nearby pixel,graph-cut optimization,similar label,car roof,order-preserving move,graph-cut segmentation,alpha-expansion move,alpha-expansion move algorithm,graph-cut method,new graph-cut move,graph-cut-based optimization,order-preserving moves,max flow,energy minimization,layout,support vector machines,constraint optimization,labeling,graph cut,computer vision,svm,image segmentation,stereo vision,graph cuts,shape,pixel | Cut,Flow network,Computer vision,Local optimum,Computer science,Segmentation,Image segmentation,Minification,Artificial intelligence,Pixel,Constrained optimization | Journal |
Volume | Issue | ISSN |
32 | 7 | 1939-3539 |
Citations | PageRank | References |
12 | 0.95 | 31 |
Authors | ||
3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Xiaoqing Liu | 1 | 54 | 5.18 |
Olga Veksler | 2 | 5653 | 356.54 |
Jagath Samarabandu | 3 | 133 | 20.50 |