Abstract

Current techniques for energy-based image segmentation are not well suited to the incorporation of topological information about image regions, such as their connectedness or holefreeness. Even in the simplest conceivable cases, the inclusion of topological side constraints turns the necessary energy minimization steps into NP hard optimization problems. In my talk I will present a different approach to enforce topological properties in energy-based image segmentation. Instead of formulating side constraints one searches a minimal pertubation of the unary potentials such that unconstrained optimization leads to a segmentation with the intended properties. When measuring similarity by the L^{1 norm, this setup is equivalent to the constraint-based setup (and therefore again NP-hard). However, when using an L}infinity-norm, the problem becomes efficiently solvable using tools from computational topology. Based on this observation, I will present an efficient iterative segmentation algorithm that allows image segmentation with specified topological properties even for large images. The algorithm can also easily be extended, e.g. to recent models with higher order potentials, because incorporating topological constraints through modified unary potentials makes the method independent of the actual algorithm used for energy minimization.