Kernel Cuts: Kernel and Spectral Clustering Meet Regularization

Meng Tang, Dmitrii Marin, Ismail Ben Ayed, Yuri Boykov

In International Journal of Computer Vision (IJCV), vol. 127, no. 5, pp. 477-511, May 2019.


This work bridges the gap between two popular methodologies for data partitioning: kernel clustering and regularization-based segmentation. While addressing closely related practical problems, these general methodologies may seem very different based on how they are covered in the literature. The differences may show up in motivation, formulation, and optimization, e.g. spectral relaxation vs max-flow. We explain how regularization and kernel clustering can work together and why this is useful. Our joint energy combines standard regularization, e.g. MRF potentials, and kernel clustering criteria like normalized cut. Complementarity of such terms is demonstrated in many applications using our bound optimization Kernel Cut algorithm for the joint energy (code is publicly available). While detailing combinatorial move-making, our main focus are new linear kernel and spectral bounds for kernel clustering criteria allowing their integration with any regularization objectives with existing discrete or continuous solvers.

WHOLE PAPER: pdf file (18Mb)
RELATED PAPER: Kernel clustering: density biases and solutions (PAMI 2019)
CONFERENCE VERSIONS: Normalized Cut meets MRF (ECCV 2016), Sectrects of Grabcut and kernel K-means (ICCV 2016)

[an error occurred while processing this directive]