Abstract

Pixel labeling problems are pervasive in computer vision research. In this talk, we discuss optimization approaches for labeling problems which have some structure imposed on the layout of the labels. In other words, the relationships between labels is not arbitrary but has a well defined spatial structure. We will describe two approaches for structured layout scenes. The first approach is for a more restrictive type of scenes, for which 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 the popular expansion algorithm, and, therefore, escape local minima more easily. The second approach is for a more general type of structured layout scenes and it is based on dynamic programming. In the second case, the exact minimum can be found efficiently. This is very rare for a 2D labeling problem to have an efficient and global optimizer. For both approaches, our applications include geometric class labeling and segmentation with a shape prior.