Abstract

We consider labeling an image with multiple tiers. Tiers, one on top of another, enforce a strict vertical order among ob jects (e.g. sky is above the ground). Two new ideas are explored: First, under a sim- plification of the general tiered labeling framework proposed by Felzen- szwalb and Veksler [1], we design an efficient O(KN ) algorithm for the approximate optimal labeling of an image of N pixels with K tiers. Our algorithm runs in over 100 frames per second on images of VGA resolu- tions when K is less than 6. When K = 3, our solution overlaps with the globally optimal one by Felzenszwalb and Veksler in over 99% of all pix- els but runs 1000 times faster. Second, we define a topological prior that specifies the number of local extrema in the tier boundaries, and give an O(N M ) algorithm to find a single, optimal tier boundary with exactly M local maxima and minima. These two extensions enrich the general tiered labeling framework and enable fast computation. The proposed topological prior further improves the accuracy in labeling details.