Planar Ultrametrics for Image Segmentation
We study the problem of hierarchical clustering on planar graphs. We formulate this in terms of finding the closest ultrametric to a specified set of distances and solve it using an LP relaxation that leverages minimum cost perfect matching as a subroutine to efficiently explore the space of planar partitions. We apply our algorithm to the problem of hierarchical image segmentation.
The paper generalizes the LP-relaxation approach to correlation clustering (multicut) to produce hierarchical clustering/segmentation. This can also be understood as fitting an ultrametric into the input distance data (which is called, sligtly confusingly, ultrametric rounding). The additional constraint is that at a higher level of the hierarchy, edges can be only removed from the multicuts and not added.The main contribution is a formulation of a suitable LP relaxation for this problem. The paper considers only planar graphs, which enables to employ column generation (detecting violated cutting planes) by planar max-cut / perfect matching (using Blossom 5). Besides that, the LP uses a number of tricks, using experience gained in past research on correlation clustering [6,16]. The LP is solved by CPLEX with Blossom5 plugged in.The experiments are done on the Berkeley segmentation dataset, using superpixels as the graph vertices. The appendix/supplement gives a thorough and detailed comparison with one other algorithm (UCM, reference [2] in the supplement), which is a version of algglomerative clustering.The experiments show that the method works well, which is not self-evident given several non-self-evident features in the LP formulation. On the practical side, the experiments suggest that the method is marginally better than UCM (slight refinements of contours that do not much contribute to evaluation statistics but can be visible) but notably slower - see e.g. Figure 3b in the main paper.Clarity of the text is not great but acceptable. One objection is that it often refers to non-trivial results from previous works, which makes it hard to read for a reader not completely familiar with the topic.I have one theoretical question. You write (paragraph starting at line 095) that the relaxation CC of MC is the convex hull (ie, the integral hull) of MC. That means, the relaxation of (1) alone is exact (ie, the optimal value of linear optimization over MC and CC are equal). But at the same time you seem to suggest (line 097) that the relaxation of (4) is proper (ie, not tight). That should mean that adding the hierarchy constraint X^l\ge X^{l+1} spoils this exactness - ie, linear optimization over \Omega_L is not the same as that over \bar{\Omega}_L. If so, this is theoretically interesting. Or did I miss something?Minor comment: the term "ultrametric rounding" is confusing because it clashes with "rounding schemes" in combinatorial optimization (see, eg, https://en.wikipedia.org/wiki/Randomized_rounding). Note that the paper [1] uses the term in this sense, while your paper uses it for "fitting an ultrametric". Is the term used in enough other works, preferably in theoretical computer science? If not, please do not promote wrong terminology and consider changing the title.