A Fast Continuous Max-Flow Approach to Non-Convex Multilabeling Problems
MetadataShow full item record
This work addresses a class of multilabeling problems over a spatially continuous image domain, where the data fidelity term can be any bounded function, not necessarily convex. Two total variation based regularization terms are considered, the first favoring a linear relationship between the labels and the second independent of the label values (Pott’s model). In the spatially discrete setting, Ishikawa  showed that the first of these labeling problems can be solved exactly by standard max-flow and min-cut algorithms over specially designed graphs. We will propose a continuous analogue of Ishikawa’s graph construction  by formulating continuous max-flow and min-cut models over a specially designed domain. These max-flow and min-cut models are equivalent under a primal-dual perspective. They can be seen as exact convex relaxations of the original problem and can be used to compute global solutions. Fast continuous max-flow based algorithms are proposed based on the max-flow models whose efficiency and reliability can be validated by both standard optimization theories and experiments. In comparison to previous work [53, 52] on continuous generalization of Ishikawa’s construction, our approach differs in the max-flow dual treatment which leads to the following main advantages: A new theoretical framework which embeds the label order constraints implicitly and naturally results in optimal labeling functions taking values in any predefined finite label set; A more general thresholding theorem which allows to produce a larger set of non-unique solutions to the original problem; Numerical experiments show the new max-flow algorithms converge faster than the fast primal-dual algorithm of [53, 52]. The speedup factor is especially significant at high precisions. In the end, our dual formulation and algorithms are extended to a recently proposed convex relaxation of Pott’s model , thereby avoiding expensive iterative computations of projections without closed form solution.