Planar Ultrametric Rounding for Image Segmentation
This addresses hierarchical image segmentation for computer vision applications, but appears incremental as it builds on existing ultrametric rounding and LP methods.
The paper tackles hierarchical clustering on planar graphs by formulating it as an LP relaxation of ultrametric rounding and introduces a dual cutting plane scheme using minimum cost perfect matching for efficient solving, applying it to hierarchical image segmentation.
We study the problem of hierarchical clustering on planar graphs. We formulate this in terms of an LP relaxation of ultrametric rounding. To solve this LP efficiently we introduce a dual cutting plane scheme that uses minimum cost perfect matching as a subroutine in order to efficiently explore the space of planar partitions. We apply our algorithm to the problem of hierarchical image segmentation.