Abstract

Multi-label segmentation and high-order constraints

Yuri Boykov
University of Western Ontario

This lecture discusses multi-labeling problems with pair-wise and higher-order energies focusing on discrete formulations/optimization in the context of segmentation, restoration, stereo, etc. Basic pair-wise regularization models (Quadratic, L1, Metric, Potts, Robust, Truncated models). Submodular pair-wise energies and graph cuts. Approximation algorithms based on large moves (expansion, swap). Other approximations (relaxations, message passing). Multi-label segmentation with geometric constraints (scene labeling, biomedical image segmentation). Higher-order models: boundary (Pn_Potts, curvature) and region (cardinality constraints, non-linear appearance, entropy, grabcut, color-separation, etc). Submodularity (general high-order case), reductions to pairwise, label elevation, block-coordinate descent, trust-region.