Matching segmentation hierarchies

When matching regions from "similar" images, one typically has the problem of missing counterparts due to local or even global variations of segmentation fineness. Matching segmentation hierarchies, however, not only increases the chances of finding counterparts, but also allows us to exploit the manifold constraints coming from the topological relations between any two regions in a hierarchy. To define the topological relations we represent a plane image I by a plane attributed graph G and derive a finite topology O from G. In particular, segmenting I corresponds to taking a topological minor of G which, in turn, is equivalent to coarsening O. Moreover, each finite topology involved is a coarsening of the standard topology on R-2. Then, we construct a weighted association graph G(A), the nodes of which represent potential matches and the edges of which indicate topological consistency with respect to O. Specifically, a maximal weight clique of G(A) corresponds to a topologically consistent mapping with maximal total similarity. To find "heavy" cliques, we extend a greedy pivoting-based heuristic to the weighted case. Experiments on pairs of stereo images, on a video sequence of a cluttered outdoor scene, and on a sequence of panoramic images demonstrate the effectiveness of our method.