Order Preserving Moves for Graph Cut based Optimization
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 graphcut
expansion 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 graphcut
moves which we call order-preserving. The advantage of orderpreserving
moves is that they act on all labels simultaneously,
unlike expansion.
Main Idea
Our model consists of 5 parts: B,L,R,C,T, with ordering constraints between them.
A vertical order preserving move is illustrated
in Figure 1, top. Labeling is divided into three rectangles with
two vertical lines, one passing through the border of the T
and C regions (blue and cyan) and the other passing through
the border of C and B (cyan and green) regions. In a vertical
order-preserving move, pixels in the left rectangle can switch their
labels to T, L or B. Pixels in the middle rectangle can switch their
labels to T, C or B, and finally pixels in the bottom rectangle can
switch their labels to T, R or B. The name “vertical” reflects
that the C region, if present after the move, can change in the
vertical direction. A vertical order preserving move is illustrated
in Figure 1, bottom. It is a rotated version of a horizontal
order preserving move.
Figure 1
Applications
Geometric Scene Labeling
Figure 2: Rough geometric surface orientation labeling from a single image. Results on indoor scenes.
The resulting rough 3D reconstruction from a single image can be used for virtual scene walk-through.
Binary Segmentation with a Simple Shape Prior
Figure 3: Segmentation with a simple "trapezoid" shape prior. We look for a trapezoid like shape with
a high edge contrast on the boundary.
Publications