iccv iccv2013 iccv2013-324 iccv2013-324-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Igor Gridchyn, Vladimir Kolmogorov
Abstract: The problem of minimizing the Potts energy function frequently occurs in computer vision applications. One way to tackle this NP-hard problem was proposed by Kovtun [20, 21]. It identifies a part of an optimal solution by running k maxflow computations, where k is the number of labels. The number of “labeled” pixels can be significant in some applications, e.g. 50-93% in our tests for stereo. We show how to reduce the runtime to O(log k) maxflow computations (or one parametric maxflow computation). Furthermore, the output of our algorithm allows to speed-up the subsequent alpha expansion for the unlabeled part, or can be used as it is for time-critical applications. To derive our technique, we generalize the algorithm of Felzenszwalb et al. [7] for Tree Metrics. We also show a connection to k-submodular functions from combinatorial optimization, and discuss k-submodular relaxations for general energy functions.
[1] K. Alahari, P. Kohli, and P. H. S. Torr. Dynamic hybrid algorithms for MAP inference in discrete MRFs. PAMI, 32(10):1846–1857, 2010. 1, 6, 7, 8
[2] M. Babenko, J. Derryberry, A. Goldberg, R. Tarjan, and Y. Zhou. Experimental evaluation of parametric max-flow algorithms. In 6th Int’l conference on Experimental Algorithms (WEA), pages 256–269, 2007. 6
[3] Y. Boykov and V. Kolmogorov. An experimental comparison of mincut/max-flow algorithms for energy minimization in vision. PAMI, 26(9), September 2004. 5
[4] Y. Boykov, O. Veksler, and R. Zabih. Fast approximate energy minimization via graph cuts. PAMI, 23(1 1), 2001. 1
[5] A. Chambolle. Total variation minimization and a class of binary MRF models. In EMMCVPR, pages 136–152, November 2005. 2, 4
[6] J. Darbon and M. Sigelle. Image restoration with discrete constrained total variation part I: Fast and exact optimization. J. of Math. Imaging and Vision, 26(3):261–276, 2006. 2, 4
[7] P. Felzenszwalb, G. Pap, E. Tardos, and R. Zabih. Globally optimal pixel labeling algorithms for tree metrics. In CVPR, 2010. 1, 2, 3
[8] G. Gallo, M. D. Grigoriadis, and R. E. Tarjan. A fast parametric maximum flow algorithm and applications. SIAM J. Computing, 18:30– 55, 1989. 4, 6
[9] I. Gridchyn and V. Kolmogorov. Potts model, parametric maxflow and k-submodular functions. CoRR, abs/13 10. 1771, 2013. 4, 5, 7, 8
[10] P. L. Hammer, P. Hansen, and B. Simeone. Roof duality, complementation and persistency in quadratic 0-1 optimization. Math. Programming, 28: 121–155, 1984. 6
[11] H. Hirschm u¨ller. Evaluation of cost functions for stereo matching. In CVPR, 2007. 7
[12] D. S. Hochbaum. An efficient algorithm for image segmentation, Markov Random Fields and related problems. J. ACM, 48:2:686– 701, July 2001. 2, 4
[13] A. Huber and V. Kolmogorov. Towards minimizing k-submodular functions. In International Symposium on Combinatorial Optimiza-
[14]
[15]
[16]
[17]
[18]
[19] tion (ISCO), Apr. 2012. 6 P. Kohli and P. H. S. Torr. Efficiently solving dynamic Markov random fields using graph cuts. In ICCV, 2005. 5 A. J. W. Kolen. Tree Network and Planar Rectilinear Location Theory. Vol. 25 of CWI Tracts. CWI, 1986. 2, 3 V. Kolmogorov. Submodularity on a tree: Unifying L?-convex and bisubmodular functions. In 36th Int’l Symposium on Math. Foundations of Comp. Science, Aug. 2011. 6 V. Kolmogorov. Generalized roof duality and bisubmodular functions. Discrete Applied Mathematics, 160(4-5):416–426, March 2012. 6 N. Komodakis and G. Tziritas. Approximate labeling via graph cuts based on linear programming. PAMI, 29(8): 1436–1453, 2007. 1, 7 N. Komodakis, G. Tziritas, and N. Paragios. Performance vs computational efficiency for optimizing single and dynamic MRFs: Setting the state of the art with primal-dual strategies. CVIU, 112(1): 14 29, 2008. 1, 7 I. Kovtun. Partial optimal labeling search for a NP-hard subclass of (max,+) problems. In DAGM, pages 402–409, 2003. 1, 2 I. V. Kovtun. Image segmentation based on sufficient conditions of optimality in NP-complete classes of structural labelling problems. PhD thesis, IRTC ITS National Academy ofSciences, Ukraine, 2004. (In Ukranian). 1, 2 D. Scharstein and R. Szeliski. A taxonomy and evaluation of dense two-frame stereo correspondence algorithms. IJCV, 47(1-3):7–42, Apr. 2002. 7 D. Scharstein and R. Szeliski. High-accuracy stereo depth maps using structured light. In CVPR, pages 195–202, 2003. 7 A. Shekhovtsov. Efficient graph-based energy minimization methods in computer vision. PhD thesis, Czech Technical University, CMP, Prague, 2013. 1 A. Shekhovtsov and V. Hlavac. On partial opimality by auxiliary submodular problems. Control Systems and Computers, 2:71–78, 2012. 1, 2 J. Thapper and S. The power of linear programming for valued CSPs. In FOCS, 2012. 6 –
[20]
[21]
[22]
[23]
[24]
[25]
[26] Zˇivn ´y.
[27] T. Werner. A linear programming approach to max-sum problem: A review. PAMI, 29(7): 1165–1 179, 2007. 6
[28] B. A. Zalesky. Network flow optimization for restoration of images. J. Appl. Math., 2(4):199–218, 2002. 4 22332277