This paper introduces a novel framework for labeling problems, particularly object segmentation, that combines multiple segmentations in a principled manner using higher-order conditional random fields (CRFs). The method uses potentials defined on sets of pixels (image segments) generated by unsupervised segmentation algorithms to enforce label consistency in image regions. These potentials are more general than the commonly used pairwise contrast-sensitive smoothness potentials and are based on the Robust \(P^n\) model. The paper proves that the optimal swap and expansion moves for energy functions composed of these potentials can be computed by solving a st-mincut problem, enabling the use of powerful graph cut-based move-making algorithms for inference. Experiments on challenging datasets show that integrating higher-order potentials significantly improves the results, leading to better-defined object boundaries. The method is applicable to various labeling problems and can handle multiple object classes.This paper introduces a novel framework for labeling problems, particularly object segmentation, that combines multiple segmentations in a principled manner using higher-order conditional random fields (CRFs). The method uses potentials defined on sets of pixels (image segments) generated by unsupervised segmentation algorithms to enforce label consistency in image regions. These potentials are more general than the commonly used pairwise contrast-sensitive smoothness potentials and are based on the Robust \(P^n\) model. The paper proves that the optimal swap and expansion moves for energy functions composed of these potentials can be computed by solving a st-mincut problem, enabling the use of powerful graph cut-based move-making algorithms for inference. Experiments on challenging datasets show that integrating higher-order potentials significantly improves the results, leading to better-defined object boundaries. The method is applicable to various labeling problems and can handle multiple object classes.