Fast Planar Correlation Clustering for Image Segmentation

2012/08/02 by Yarkony, Julian, Ihler, Alexander T., Fowlkes, Charless C. · 1 citation
#Computer Vision and Pattern Recognition (cs.CV) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning (stat.ML)

paper · doi:10.48550/arxiv.1208.0378

Abstract

We describe a new optimization scheme for finding high-quality correlation clusterings in planar graphs that uses weighted perfect matching as a subroutine. Our method provides lower-bounds on the energy of the optimal correlation clustering that are typically fast to compute and tight in practice. We demonstrate our algorithm on the problem of image segmentation where this approach outperforms existing global optimization techniques in minimizing the objective and is competitive with the state of the art in producing high-quality segmentations.

Cited by

• A Simple and Fast (3+ε)-approximation for Constrained Correlation Clustering

Related

• Massively Parallel Benders Decomposition for Correlation Clustering
• Fast Combinatorial Algorithms for Min Max Correlation Clustering
• Large Scale Correlation Clustering Optimization
• Revisiting Graph Construction for Fast Image Segmentation
• Pruned Pivot: Correlation Clustering Algorithm for Dynamic, Parallel, and Local Computation Models