jmlr jmlr2011 jmlr2011-41 jmlr2011-41-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: M. Pawan Kumar, Olga Veksler, Philip H.S. Torr
Abstract: We consider the problem of obtaining an approximate maximum a posteriori estimate of a discrete random field characterized by pairwise potentials that form a truncated convex model. For this problem, we propose two st-MINCUT based move making algorithms that we call Range Swap and Range Expansion. Our algorithms can be thought of as extensions of αβ-Swap and α-Expansion respectively that fully exploit the form of the pairwise potentials. Specifically, instead of dealing with one or two labels at each iteration, our methods explore a large search space by considering a range of labels (that is, an interval of consecutive labels). Furthermore, we show that Range Expansion provides the same multiplicative bounds as the standard linear programming (LP) relaxation in polynomial time. Compared to previous approaches based on the LP relaxation, for example interior-point algorithms or tree-reweighted message passing (TRW), our methods are faster as they use only the efficient st-MINCUT algorithm in their design. We demonstrate the usefulness of the proposed approaches on both synthetic and standard real data problems. Keywords: truncated convex models, move making algorithms, range moves, multiplicative bounds, linear programming relaxation
K. Alahari, P. Kohli, and P. H. S. Torr. Reduce, reuse & recycle: Efficiently solving multi-label MRFs. In CVPR, 2008. 64 I MPROVED M OVES FOR T RUNCATED C ONVEX M ODELS J. Besag. On the statistical analysis of dirty pictures. Journal of the Royal Statistical Society, Series B, 48:259–302, 1986. S. Birchfield and C. Tomasi. Depth discontinuities by pixel-to-pixel stereo. In ICCV, pages 1073– 1080, 1998. S. Boyd and L. Vandenberghe. Convex Optimization. Cambridge University Press, 2004. Y. Boykov and V. Kolmogorov. An experimental comparison of min-cut/max-flow algorithms for energy minimization in vision. PAMI, 26(9):1124–1137, 2004. Y. Boykov, O. Veksler, and R. Zabih. Fast approximate energy minimization via graph cuts. PAMI, 23(11):1222–1239, 2001. C. Chekuri, S. Khanna, J. Naor, and L. Zosin. A linear programming formulation and approximation algorithms for the metric labelling problem. SIAM Journal on Discrete Mathematics, 18(3):606– 635, 2005. E. Dinic. Algorithm for solution of a problem of maximum flow in networks with power estimation. Soviet Math. Dokl., 11:1277–1280, 1970. P. Felzenszwalb and D. Huttenlocher. Efficient matching of pictorial structures. In CVPR, pages II: 66–73, 2000. P. Felzenszwalb and D. Huttenlocher. Efficient belief propagation for early vision. In CVPR, pages I: 261–268, 2004. A. Globerson and T. Jaakkola. Fixing max-product: Convergent message passing for MAP LPrelaxations. In NIPS, 2007. A. Goldberg and R. Tarjan. A new approach to the maximum-flow problem. Journal of ACM, 35 (4):921–940, 1988. S. Gould, F. Amat, and D. Koller. Alphabet SOUP: A framework for approximate energy minimization. In CVPR, 2009. A. Gupta and E. Tardos. A constant factor approximation algorithm for a class of classification problems. In STOC, 2000. H. Ishikawa. Exact optimization for Markov random fields with convex priors. PAMI, 25(10): 1333–1336, October 2003. J. Kleinberg and E. Tardos. Approximation algorithms for classification problems with pairwise relationships: Metric labeling and Markov random fields. In STOC, pages 14–23, 1999. V. Kolmogorov. Convergent tree-reweighted message passing for energy minimization. PAMI, 28 (10):1568–1583, 2006. V. Kolmogorov and A. Shioura. New algorithms for the dual of the convex cost network flow problem with applications to computer vision. Technical report, University College London, 2007. 65 K UMAR , V EKSLER AND T ORR N. Komodakis and G. Tziritas. Approximate labeling via graph-cuts based on linear programming. PAMI, 2007. N. Komodakis, N. Paragios, and G. Tziritas. MRF optimization via dual decomposition: Messagepassing revisited. In ICCV, 2007. A. Koster, C. van Hoesel, and A. Kolen. The partial constraint satisfaction problem: Facets and lifting theorems. Operations Research Letters, 23(3-5):89–97, 1998. M. P. Kumar and D. Koller. MAP estimation of semi-metric MRFs via hierarchical graph cuts. In UAI, 2009. M. P. Kumar and P. H. S. Torr. Improved moves for truncated convex models. In NIPS, 2008. M. P. Kumar, V. Kolmogorov, and P. H. S. Torr. An analysis of convex relaxations for MAP estimation. In NIPS, 2007. J. Lafferty, A. McCallum, and F. Pereira. Conditional random fields: Probabilistic models for segmenting and labelling sequence data. In ICML, 2001. T. Meltzer, C. Yanover, and Y. Weiss. Globally optimal solutions for energy minimization in stereo vision using reweighted belief propagation. In ICCV, 2005. J. Pearl. Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference. Morgan Kauffman, 1988. P. Ravikumar, A. Agarwal, and M. Wainwright. Message-passing for graph-structured linear programs: Proximal projections, convergence and rounding schemes. In ICML, 2008. D. Schlesinger and B. Flach. Transforming an arbitrary minsum problem into a binary one. Technical Report TUD-F106-01, Dresden University of Technology, 2006. M. Schlesinger. Sintaksicheskiy analiz dvumernykh zritelnikh singnalov v usloviyakh pomekh (syntactic analysis of two-dimensional visual signals in noisy conditions). Kibernetika, 4:113–130, 1976. M. Schlesinger and V. Giginyak. Solution to structural recognition (MAX,+)-problems by their equivalent transformations. Part 1. Control Systems and Computers, 1:3–15, 2007a. M. Schlesinger and V. Giginyak. Solution to structural recognition (MAX,+)-problems by their equivalent transformations. Part 2. Control Systems and Computers, 2:3–18, 2007b. J. Shotton, J. Winn, C. Rother, and A. Criminisi. TextonBoost: Joint appearance, shape and context modeling for multi-class object recognition and segmentation. In ECCV, pages I: 1–15, 2006. D. Sontag and T. Jaakkola. New outer bounds on the marginal polytope. In NIPS, 2007. R. Szeliski, R. Zabih, D. Scharstein, O. Veksler, V. Kolmogorov, A. Agarwala, M. Tappen, and C. Rother. A comparative study of energy minimization methods for Markov random fields with smoothness-based priors. PAMI, 2008. 66 I MPROVED M OVES FOR T RUNCATED C ONVEX M ODELS V. Vazirani. Approximation Algorithms. Springer-Verlag, 2001. O. Veksler. Efficient Graph-Based Energy Minimization Methods in Computer Vision. PhD thesis, Cornell University, 1999. O. Veksler. Graph cut based optimization for MRFs with truncated convex priors. In CVPR, 2007. M. Wainwright, T. Jaakkola, and A. Willsky. MAP estimation via agreement on trees: Message passing and linear programming. IEEE Trans. on Information Theory, 51(11):3697–3717, 2005. 67