A Fast Continuous Max-Flow Approach to Non-convex Multi-labeling Problems
This paper studies continuous image labeling problems with an arbitrary data term and a total variation regularizer, where the labels are constrained to a finite set of real numbers. Inspired by Ishikawa’s multi-layered graph construction for the same lab
- PDF / 618,890 Bytes
- 21 Pages / 439.37 x 666.142 pts Page_size
- 13 Downloads / 194 Views
Department of Mathematics, University of California, Los Angeles, USA [email protected] 2 Computer Science Department, Middlesex College, University of Western Ontario, London, ON, Canada [email protected], [email protected] 3 Department of Mathematics, University of Bergen, Bergen, Norway [email protected]
Abstract. This paper studies continuous image labeling problems with an arbitrary data term and a total variation regularizer, where the labels are constrained to a finite set of real numbers. Inspired by Ishikawa’s multi-layered graph construction for the same labeling problem over a discrete image domain, we propose a novel continuous max-flow model and build up its duality to a convex relaxed formulation of image labeling under a new variational perspective. Via such continuous max-flow formulations, we show that exact and global optimizers can be obtained to the original non-convex labeling problem. We also extend the studies to problems with continuous-valued labels and introduce a new theory to this problem. Finally, we show the proposed continuous max-flow models directly lead to new fast flow-maximization algorithmic schemes which outperform previous approaches in terms of efficiency. Such continuous max-flow based algorithms can be validated by convex optimization theories and accelerated by modern parallel computational hardware.
1
Introduction
Many practical problems in image processing and computer vision can be modeled as multilabel problems, where the task is to optimally assign the unknown variable l, chosen from some finite set {l1 , . . . , ln }, at each point of the image domain Ω. It has become an important paradigm to formulate such labeling problems as the optimization of an energy function/functional which mathematically encodes all the information needed for the specified imaging and vision task. Such optimization problems can be formulated by either regarding the image domain as discrete or continuous. In the spatially discrete setting, graph cut has become one of the most important and efficient techniques to tackle such problems, by computing max-flow or min-cut on appropriately constructed graphs. Applications of max-flow/mincut in computer vision range from image segmentation or labeling [1,2], stereo [3,4], 3D reconstruction [5] etc. Unfortunately, most minimization problems A. Bruhn et al. (Eds.): Global Optimization Methods, LNCS 8293, pp. 134–154, 2014. c Springer-Verlag Berlin Heidelberg 2014 DOI: 10.1007/978-3-642-54774-4 7,
A Fast Continuous Max-Flow Approach for Multi-labeling Problems
135
involving more than two labels are NP-hard, therefore only approximate algorithms are available [1,4]. However, for a particular set of multilabeling problems with convex interaction penalty, Ishikawa [6] showed that exact solutions can be computed by max-flow and min-cut. Such energy functions are important in e.g. stereo reconstruction. Despite the efficiencies of graph-based methods, their computation results are often comparatively rough and biased by the discrete graph setting, i.e. metricati
Data Loading...
