Energy minimization of discrete functions with higher-order potentials for depth map generation

Minimization of discrete energy functions considering higher-order potentials is a challenging yet an important problem. In this work, a three-step procedure will be presented and exemplified on a general problem related to the dense depth map computation from multi-view configurations: Achieving a joint reconstruction of structure and semantics with piecewise planarity constraints. The three steps of the procedure are binarization, quadratization, and energy minimization. While the first and the third step are accomplished using procedures based on alpha-expansion and max-flow algorithms, respectively, we propose for the quadratization step a fast and simple module to reformulate the higher-order problem as a quadratic one. This module is based on edge statistics and is particularly useful for regular graphs and for third- or fourth-order potentials.