BORA - UiB

Bergen Open Research Archive

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

Bergen Open Research Archive

Show simple item record

dc.contributor.author Bae, Egil
dc.contributor.author Yuan, Jing
dc.contributor.author Tai, Xue-Cheng
dc.contributor.author Boykov, Yuri
dc.date.accessioned 2011-09-19T11:24:42Z
dc.date.available 2011-09-19T11:24:42Z
dc.date.issued 2011
dc.identifier.uri http://hdl.handle.net/1956/5021
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 en
dc.publisher The authors en
dc.relation.ispartof <a href="http://hdl.handle.net/1956/5017" target="blank">Efficient global minimization methods for variational problems in imaging and vision</a> en
dc.rights Copyright the authors. All rights reserved. en
dc.subject Image processing and segmentation en
dc.subject Continuous max-flow/min-cut en
dc.subject Optimization en
dc.title A Fast Continuous Max-Flow Approach to Non-Convex Multilabeling Problems en
dc.type Preprint en
dc.subject.nsi VDP::Mathematics and natural science: 400::Mathematics: 410 en
dc.subject.nsi VDP::Mathematics and natural science: 400::Information and communication science: 420::Simulation, visualization, signal processing, image processing: 429 en
dc.type.version submittedVersion en


Files in this item

 

This item appears in the following Collection(s)

Show simple item record

Search BORA


Browse

My Account