Kernel Cuts: MRF meets Kernel & Spectral Clustering
This work addresses a gap in machine learning and computer vision by enabling the combination of MRF and clustering models, which is incremental as it builds on existing techniques but introduces a novel integration approach.
The paper tackles the problem of combining Markov Random Field (MRF) segmentation energies with pairwise clustering criteria like Normalized Cut, which were previously not integrated due to optimization differences, and proposes Kernel Cut algorithms to efficiently address joint energies, resulting in a method that benefits both segmentation and clustering applications.
We propose a new segmentation model combining common regularization energies, e.g. Markov Random Field (MRF) potentials, and standard pairwise clustering criteria like Normalized Cut (NC), average association (AA), etc. These clustering and regularization models are widely used in machine learning and computer vision, but they were not combined before due to significant differences in the corresponding optimization, e.g. spectral relaxation and combinatorial max-flow techniques. On the one hand, we show that many common applications using MRF segmentation energies can benefit from a high-order NC term, e.g. enforcing balanced clustering of arbitrary high-dimensional image features combining color, texture, location, depth, motion, etc. On the other hand, standard clustering applications can benefit from an inclusion of common pairwise or higher-order MRF constraints, e.g. edge alignment, bin-consistency, label cost, etc. To address joint energies like NC+MRF, we propose efficient Kernel Cut algorithms based on bound optimization. While focusing on graph cut and move-making techniques, our new unary (linear) kernel and spectral bound formulations for common pairwise clustering criteria allow to integrate them with any regularization functionals with existing discrete or continuous solvers.