dc.contributor.author | Bae, Egil | eng |
dc.contributor.author | Yuan, Jing | eng |
dc.contributor.author | Tai, Xue-Cheng | eng |
dc.contributor.author | Boykov, Yuri | eng |
dc.date.accessioned | 2011-09-19T11:24:42Z | |
dc.date.available | 2011-09-19T11:24:42Z | |
dc.date.issued | 2011 | eng |
dc.identifier.uri | https://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_US |
dc.language.iso | eng | eng |
dc.publisher | The authors | en_US |
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_US |
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_US |
dc.type | Working paper | |
dc.rights.holder | Copyright the authors. All rights reserved | en_US |
dc.subject.nsi | VDP::Mathematics and natural science: 400::Mathematics: 410 | en_US |
dc.subject.nsi | VDP::Mathematics and natural science: 400::Information and communication science: 420::Simulation, visualization, signal processing, image processing: 429 | en_US |