Abstract

We propose a theoretical construct coined nested pictorial structure to represent an ob ject by parts that are recursively nested. Three innovative ideas are proposed: First, the nested pictorial structure finds a part configuration that is allowed to be deformed in geometric arrangement, while being confined to be topologically nested. Second, we define nested features which lend themselves to better, more detailed accounting of pixel data cost and describe occlusion in a principled way. Third, we develop the concept of constrained distance transform, a vari- ation of the generalized distance transform, to guarantee the topological nesting relations and to further enforce that parts have no overlap with each other. We show that matching an optimal nested pictorial structure of K parts on an image of N pixels takes O(N K ) time using dynamic pro- gramming and constrained distance transform. In our MATLAB/C++ implementation, it takes less than 0.1 seconds to do the global optimal matching when K = 10 and N = 400 ?400. We demonstrate the useful- ness of nested pictorial structures in the matching of ob jects of nested patterns, ob jects in occlusion, and ob jects that live in a context.