Abstract
We extend the concept of generalized roof duality from pseudo- boolean functions to real-valued functions over multi-label variables. In partic- ular, we prove that an analogue of the persistency property holds for energies of any order with any number of linearly ordered labels. Moreover, we show how the optimal submodular relaxation can be constructed in the first-order case.