Bergen Open Research Archive

A Fast Continuous Max-Flow Approach to Non-Convex Multilabeling Problems

Bergen Open Research Archive

Show simple item record Bae, Egil eng Yuan, Jing eng Tai, Xue-Cheng eng Boykov, Yuri eng 2011-09-19T11:24:42Z 2011-09-19T11:24:42Z 2011 eng
dc.description.abstract 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 [33] 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 [33] 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 [50], thereby avoiding expensive iterative computations of projections without closed form solution. en
dc.language.iso eng eng
dc.publisher The authors en
dc.relation.ispartof <a href="" target="blank">Efficient global minimization methods for variational problems in imaging and vision</a> en
dc.rights Copyright the authors. All rights reserved. eng
dc.subject Image processing and segmentation eng
dc.subject Continuous max-flow/min-cut eng
dc.subject Optimization eng
dc.title A Fast Continuous Max-Flow Approach to Non-Convex Multilabeling Problems en
dc.type Preprint eng
dc.subject.nsi VDP::Mathematics and natural science: 400::Mathematics: 410 eng
dc.subject.nsi VDP::Mathematics and natural science: 400::Information and communication science: 420::Simulation, visualization, signal processing, image processing: 429 eng
dc.type.version submittedVersion eng

Files in this item


This item appears in the following Collection(s)

Show simple item record

Search BORA


My Account