iccv iccv2013 iccv2013-309 iccv2013-309-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Carl Olsson, Johannes Ulén, Yuri Boykov, Vladimir Kolmogorov
Abstract: Energies with high-order non-submodular interactions have been shown to be very useful in vision due to their high modeling power. Optimization of such energies, however, is generally NP-hard. A naive approach that works for small problem instances is exhaustive search, that is, enumeration of all possible labelings of the underlying graph. We propose a general minimization approach for large graphs based on enumeration of labelings of certain small patches. This partial enumeration technique reduces complex highorder energy formulations to pairwise Constraint Satisfaction Problems with unary costs (uCSP), which can be efficiently solved using standard methods like TRW-S. Our approach outperforms a number of existing state-of-the-art algorithms on well known difficult problems (e.g. curvature regularization, stereo, deconvolution); it gives near global minimum and better speed. Our main application of interest is curvature regularization. In the context of segmentation, our partial enumeration technique allows to evaluate curvature directly on small patches using a novel integral geometry approach. 1
[1] F. Bacchus, X. Chen, P. van Beek, and T. Walsh. Binary vs. nonbinary constraints. Artificial Intelligence, 140(1/2): 1–37, 2002. 4
[2] Y. Boykov and V. Kolmogorov. Computing geodesics and minimal surfaces via graph cuts. In International Conference on Computer Vision (ICCV), 2003. 2
[3] Y. Boykov, O. Veksler, and R. Zabih. Fast approximate energy minimization via graph cuts. IEEE Transations on Pattern Analysis and Machine Intelligence, 23(1 1): 1222–1239, 2001 . 1
[4] K. Bredies, T. Pock, and B. Wirth. Convex relaxation of a class of vertex penalizing functionals. J. Math. Imaging and Vision, 47(3):278–302, 2013. 1, 2 2942 (a) Noisy image (b) RD (379.44) (c) MPLP (324.07) (d) TRW-S (36.44) (e) TRW-S patches (12.1 1) Figure 12: Binary deconvolution results (with energy). (a) Noisy image. (b) Gray pixels are unlabeled. Duality gap: 477.78 (unlabeled set to 0) (c) Duality gap: 422.40, maximum 10,000 clusterings. (d) Duality gap: 134.77. (e) Duality gap: 10−14. Energy Lower bound Relative gap 1.4558 · 1010 1.4558 · 1010 1.4471 · 10−14 315.3342 Our RD 11..44565387 ·· 1 10010 Our/RD1 603.799 ·5 180 11..44551588 ·· 110010 151.0801 ·9 10 19.4.3467914 ·· 1 100−3 49.3.3862954 · 1 100−13 1.9216 180.6859 Our 4.3825 · Time (s) 10 Energy Lower bound Relative gap Time (s) 1.3594 · 1010 1.3594 · 1010 2.0394 · 10−14 428.2557 RD 11..35156954 ·· 1 10010 Our/RD1. 06.950 ·9 120 11..30458944 ·· 110010 148.1465 ·2 10 09.547 ·5 160 6.0910 · 10−15 4.6479 111.8597 6.0910 · 10 (a) ?1 regularization. (b) ?2 regularization. Table 3: Averaged stereo results on Cones sequence. Relative gap is defined as (Energy-Lower bound)/Lower bound. (a) For ?1 regularization RD left 24% of the variables unlabeled. ”Improve” lowered the average energy for RD to 1.4609 · 1010. (b) For ?2 regularization R RDD le leftf t6 24%4% %o fo tfh teh vear viaarbialebsl eusnul anblaelbeedle. ”Improve” vloe”we lorewde trehed average energy feorrg yR fDo tro R 1D.4 t3o92 1 · 41600190.
[5] T. Chan and J. Shen. Nontexture inpainting by curvature driven diffusion (cdd). Journal of Visual Communication and Image Representation, 12:436–449, 2001. 1
[6] M. Droske and M. Rumpf. A level set formulation for Willmore flow. Interfaces and Free Boundaries, 6:361–378, 2004. 1
[7] N. El-Zehiry and L. Grady. Fast global optimization of curvature. In Conf. Computer Vision and Pattern Recognition, 2010. 1, 2, 4, 5
[8] S. Geman and D. Geman. Stochastic relaxation, gibbs distributions, and the bayesian restoration of images. IEEE Transations on Pattern Analysis and Machine Intelligence, 6(6):721–741, 1984. 1, 2
[9] A. Globerson and T. Jaakkola. Fixing max-product: Convergent message passing algorithms for MAP LP-relaxations. In NIPS, 2007. 3
[10] H. Ishikawa. Exact optimization for markov random fields with convex priors. IEEE Trans on Pattern Analysis and Machine Intelligence, 25(10): 1333 1336, 2003. 1
[11] F. Kahl and P. Strandmark. Generalized roof duality. Discrete Applied Mathematics, 160(16-17):2419–2434, 2012. 3, 4, 5 –
[12] M. Kass, A. Witkin, and D. Terzolpoulos. Snakes: Active contour models. Int. Journal of Computer Vision, 1(4):321–33 1, 1988. 1
[13] V. Kolmogorov. Convergent tree-reweighted message passing for energy minimization. IEEE Transanctions on Pattern Analysis and Machine. Intelligence., 28: 1568–1583, October 2006. 3, 5
[14] V. Kolmogorov and T. Schoenemann. Generalized sequential treereweighted message passing. arXiv:1205.6352, 2012. 3, 6
[15] N. Komodakis and N. Paragios. Beyond pairwise energies: Efficient optimization for higher-order mrfs. In Conf. on Computer Vision and Pattern Recognition, 2009. 3, 4
[16] J. Lellmann and C. Schnorr. Continuous multiclass labeling approaches and algorithms. SIAM Journal on Imaging Sciences, 4: 1049–1096, 2011. 1
[17] V. S. Lempitsky, C. Rother, S. Roth, and A. Blake. Fusion moves for markov random field optimization. IEEE Trans. Pattern Anal. Mach. Intell., 32(8): 1392–1405, 2010. 7
[18] S. Masnou and J. Morel. Level-lines based disocclusion. In International Conference on Image Processing (ICIP), 1998. 1
[19] T. Meltzer, A. Globerson, and Y. Weiss. Convergent message passing algorithms - a unifying view. In Conf. on Uncertainty in Artificial Intelligence, 2009. 3
[20] M. Nikolova, S. Esedoglu, and T. Chan. Algorithms for finding global minimizers of image segmentation and denoising models. SIAM Journal of Applied Mathematics, 66: 1632–1648, 2006. 1
[21] C. Olsson and Y. Boykov. Curvature-based regularization for surface approximation. In Conf. Computer Vision and Pattern Recognition, 2012. 2
[22] C. Olsson, J. Ul´ en, Y. Boykov, and V. Kolmogorov. Simplifying energy optimization using partial enumeration. Technical report, arXiv:1303.1749v2, 2013. 3, 4, 6
[23] T. Pock, D. Cremers, H. Bischof, and A. Chambolle. Global solutions of variational models with convex regularization. SIAM Journal on Imaging Sciences, 3: 1122–1 145, 2010. 1
[24] A. Raj and R. Zabih. A graph cut algorithm for generalized image deconvolution. In International Conference of Computer vision (ICCV), 2005. 7
[25] C. Rother, V. Kolmogorov, V. S. Lempitsky, and M. Szummer. Optimizing binary mrfs via extended roof duality. In Conf. Computer Vision and Pattern Recognition, 2007. 5, 7
[26] D. Scharstein and R. Szeliski. High-accuracy stereo depth maps using structured light. In Conf. Computer Vision and Pattern Recognition, 2003. 7
[27] T. Schoenemann, F. Kahl, S. Masnou, and D. Cremers. A linear framework for region-based image segmentation and inpainting involving curvature penalization. Int. Journal of Computer Vision, 2012. 1, 2, 4
[28] A. Shekhovtsov, P. Kohli, and C. Rother. Curvature prior for MRFbased segmentation and shape inpaint. In arXiv: 1109.1480v1, 2011, also DAGM, 2012. 3
[29] D. Sontag, T. Meltzer, A. Globerson, T. Jaakkola, and Y. Weiss. Tightening lp relaxations for map using message passing. In UAI, 2008. 3, 6, 7
[30] P. Strandmark and F. Kahl. Curvature regularization for curves and surfaces in a global optimization framework. In EMMCVPR, pages 205–218, 2011. 1, 2, 4
[31] J. Sullivan. A crystalline approximation theorem for hypersurfaces, phd thesis. 1992. 2
[32] D. Tarlow, I. Givoni, and R. Zemel. HOP-MAP: efficient message passing with higher order potentials. In AISTATS, 2010. 4
[33] T. Werner. Revisiting the linear programming relaxation approach to Gibbs energy minimization and weighted constraint satisfaction. IEEE Transations on Pattern Analysis and Machine Intelligence, 32(8): 1474–1488, 2010. 3
[34] O. Woodford, P. Torr, I. Reid, and A. Fitzgibbon. Global stereo reconstruction under second order smoothness priors. IEEE Transactions on Pattern Analysis and Machine Intelligence, 3 1(12):21 15– 2128, 2009. 1, 7
[35] J. Yuan, E. Bae, X.-C. Tai, and Y. Boykov. A continuous max-flow approach to potts model. In European Conference on Computer Vision (ECCV), 2010. 1 2943