Monday, April 26, 2010
4:00pm

5130 Upson Hall

Abstract:

In the metric labeling problem we want to find an optimal assignment of labels to objects taking into account pairwise relationships among the objects. There is an assignment cost for giving each label to each object and there is a separation cost for giving different labels for certain pairs of objects.

We consider a special case of the problem where both the assignment and separation costs are defined by a tree-metric on the space of labels. In this case there is an "ideal label" for each object, and the assignment cost reflects distance from this label. Such problems arise in feature-space analysis with a very large label set, for instance in color image sgmentation.

We provide fast algorithms that use graph cuts to exactly solve problems of this type. Our work substantially improves a facility location algorithm of Kolen, which is impractical for large label sets L since it requires O(|L|) min cuts on large graphs. Our main contribution is an alternative method that reduces the running time to the equivalent of O(log(|L|)) min cuts. As a result, we can handle realistic-sized color images in a few seconds.