P3 & Beyond: Solving Energies with Higher Order Cliques

In this paper we extend the class of energy functions for which the optimal alpha-expansion and alphabeta-swap moves can be computed in polynomial time. Specifically, we introduce a class of higher order clique potentials and show that the expansion and swap moves for any energy function composed of these potentials can be found by minimizing a submodular function. We also show that for a subset of these potentials, the optimal move can be found by solving an st-mincut problem. We refer to this subset as the P³ Potts model. Our results enable the use of powerful move making algorithms i.e. alpha-expansion and alphabeta-swap for minimization of energy functions involving higher order cliques. Such functions have the capability of modelling the rich statistics of natural scenes and can be used for many applications in computer vision. We demonstrate their use on one such application i.e. the texture based video segmentation problem.

1. Introduction

In recent years discrete optimization has emerged as an important tool in solving Computer Vision problems. This has primarily been the result of the increasing use of energy minimization algorithms such as graph cuts [4], [11], tree-reweighted message passing [10], [25] and variants of belief propagation (BP) [17], [26]. These algorithms allow us to perform approximate inference (i.e. obtain the MAP estimate) on graphical models such as Markov Random Fields (MRF) and Conditional Random Fields (CRF) [14].