Abstract
The continuation method is a popular heuristic in computer vision for nonconvex optimization. The idea is to start from a simplified problem and gradually deform it to the actual task while tracking the solution. It was first used in computer vision under the name of graduated nonconvexity. Since then, it has been utilized explicitly or implicitly in various applications. In fact, state-of-the-art optical flow and shape estimation rely on a form of continuation. Despite its empirical success, there is little theoretical understanding of this method. This work provides some novel insights into this technique. Specifically, there are many ways to choose the initial problem and many ways to progressively deform it to the original task. However, here we show that when this process is constructed by Gaussian smoothing, it is optimal in a specific sense. In fact, we prove that Gaussian smoothing emerges from the best affine approximation to Vese’s nonlinear PDE. The latter PDE evolves any function to its convex envelope, hence providing the optimal convexification.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
References
Balzer, J., Mörwald, T.: Isogeometric finite-elements methods and variational reconstruction tasks in vision - a perfect match. In: CVPR (2012)
Barron, J.: Shapes, Paint, and Light. Ph.D. thesis, EECS Department, University of California, Berkeley (August 2013)
Bengio, Y., Louradour, J., Collobert, R., Weston, J.: Curriculum learning. In: ICML (2009)
Bengio, Y.: Learning Deep Architectures for AI. Now Publishers Inc. (2009)
Black, M.J., Rangarajan, A.: On the unification of line processes, outlier rejection, and robust statistics with applications in early vision. International Journal of Computer Vision 19(1), 57–91 (1996)
Blake, A., Zisserman, A.: Visual Reconstruction. MIT Press (1987)
Blake, A.: Comparison of the efficiency of deterministic and stochastic algorithms for visual reconstruction. IEEE PAMI 11(1), 2–12 (1989)
Boccuto, A., Discepoli, M., Gerace, I., Pucci, P.: A gnc algorithm for deblurring images with interacting discontinuities (2002)
Brox, T.: From pixels to regions: partial differential equations in image analysis. Ph.D. thesis, Saarland University, Germany (April 2005)
Brox, T., Malik, J.: Large displacement optical flow: Descriptor matching in variational motion estimation. IEEE Trans. Pattern Anal. Mach. Intell. 33(3), 500–513 (2011)
Burgers, J.M.: The nonlinear diffusion equation: asymptotic solutions and statistical problems. D. Reidel Pub. Co. (1974)
Chapelle, O., Chi, M., Zien, A.: A continuation method for semi-supervised svms. pp. 185–192. ICML 2006 (2006)
Chapelle, O., Sindhwani, V., Keerthi, S.S.: Optimization techniques for semi-supervised support vector machines. J. Mach. Learn. Res. 9, 203–233 (2008)
Chapelle, O., Wu, M.: Gradient descent optimization of smoothed information retrieval metrics. Inf. Retr. 13(3), 216–235 (2010)
Chaudhuri, S., Clochard, M., Solar-Lezama, A.: Bridging boolean and quantitative synthesis using smoothed proof search. SIGPLAN Not 49(1), 207–220 (2014)
Chaudhuri, S., Solar-Lezama, A.: Smooth interpretation. In: PLDI. pp. 279–291. ACM (2010)
Chaudhuri, S., Solar-Lezama, A.: Smoothing a program soundly and robustly. In: Gopalakrishnan, G., Qadeer, S. (eds.) CAV 2011. LNCS, vol. 6806, pp. 277–292. Springer, Heidelberg (2011)
Cohen, L.D., Gorre, A.: Snakes: Sur la convexite de la fonctionnelle denergie (1995)
Coupé, P., Manjón, J.V., Chamberland, M., Descoteaux, M., Hiba, B.: Collaborative patch-based super-resolution for diffusion-weighted images. NeuroImage 83, 245–261 (2013)
Dai, Z., Lücke, J.: Unsupervised learning of translation invariant occlusive components. In: CVPR, pp. 2400–2407 (2012)
Dhillon, P.S., Keerthi, S.S., Bellare, K., Chapelle, O., Sundararajan, S.: Deterministic annealing for semi-supervised structured output learning. In: AISTATS 2012, vol. 15 (2012)
Dufour, R.M., Miller, E.L., Galatsanos, N.P.: Template matching based object recognition with unknown geometric parameters. IEEE Transactions on Image Processing 11(12), 1385–1396 (2002)
Dvijotham, K., Fazel, M., Todorov, E.: Universal convexification via risk-aversion. In: UAI (2014)
Erhan, D., Manzagol, P.A., Bengio, Y., Bengio, S., Vincent, P.: The difficulty of training deep architectures and the effect of unsupervised pre-training. In: AISTATS, pp. 153–160 (2009)
Felzenszwalb, P.F., Girshick, R.B., McAllester, D.A., Ramanan, D.: Object detection with discriminatively trained part-based models. IEEE Trans. Pattern Anal. Mach. Intell. 32(9), 1627–1645 (2010)
Frank, M., Streich, A.P., Basin, D., Buhmann, J.M.: Multi-assignment clustering for boolean data. J. Mach. Learn. Res. 13(1), 459–489 (2012)
Fua, P., Leclerc, Y.: Object-centered surface reconstruction: combining multi-image stereo shading. International Journal on Computer Vision 16(1), 35–56 (1995)
Gehler, P., Chapelle, O.: Deterministic annealing for multiple-instance learning. In: AISTATS 2007, pp. 123–130. Microtome, Brookline (2007)
Geiger, D., Girosi, F.: Coupled markov random fields and mean field theory. In: NIPS, pp. 660–667. Morgan Kaufmann (1989)
Geiger, D., Yuille, A.L.: A common framework for image segmentation. International Journal of Computer Vision 6(3), 227–243 (1991)
Gold, S., Rangarajan, A.: A graduated assignment algorithm for graph matching. IEEE PAMI 18, 377–388 (1996)
Gold, S., Rangarajan, A., Mjolsness, E.: Learning with preknowledge: Clustering with point and graph matching distance measures. In: NIPS, pp. 713–720 (1994)
Held, D., Levinson, J., Thrun, S., Savarese, S.: Combining 3d shape, color, and motion for robust anytime tracking. In: RSS, Berkeley, USA (July 2014)
Hinton, G.E., Osindero, S., Teh, Y.W.: A fast learning algorithm for deep belief networks. Neural Computation 18(7), 1527–1554 (2006)
Hong, B.W., Lu, Z., Sundaramoorthi, G.: A new model and simple algorithms for multi-label mumford-shah problems. In: CVPR (June 2013)
Kim, J., Liu, C., Sha, F., Grauman, K.: Deformable spatial pyramid matching for fast dense correspondences. In: CVPR, pp. 2307–2314. IEEE (2013)
Kim, M., Torre, F.D.: Gaussian processes multiple instance learning, pp. 535–542 (2010)
Kosowsky, J.J., Yuille, A.L.: The invisible hand algorithm: Solving the assignment problem with statistical physics. Neural Networks 7(3), 477–490 (1994)
Leich, A., Junghans, M., Jentschel, H.J.: Hough transform with GNC. 12th European Signal Processing Conference (EUSIPCO, 2004)
Leordeanu, M., Hebert, M.: Smoothing-based optimization. In: CVPR (2008)
Li, X.: Fine-granularity and spatially-adaptive regularization for projection-based image deblurring. IEEE Transactions on Image Processing 20(4), 971–983 (2011)
Liu, Z., Qiao, H., Xu, L.: An extended path following algorithm for graph-matching problem. IEEE Trans. Pattern Anal. Mach. Intell. 34(7), 1451–1456 (2012)
Loog, M., Duistermaat, J.J., Florack, L.M.J.: On the behavior of spatial critical points under gaussian blurring (A folklore theorem and scale-space constraints). In: Kerckhove, M. (ed.) Scale-Space 2001. LNCS, vol. 2106, pp. 183–192. Springer, Heidelberg (2001)
Mairal, J., Bach, F., Ponce, J., Sapiro, G.: ICML, vol. 382, p. 87. ACM (2009)
Malek-Mohammadi, M., Babaie-Zadeh, M., Amini, A., Jutten, C.: Recovery of low-rank matrices under affine constraints via a smoothed rank function. IEEE Transactions on Signal Processing 62(4), 981–992 (2014)
Mobahi, H., Rao, S., Ma, Y.: Data-driven image completion by image patch subspaces. In: Picture Coding Symposium (2009)
Mobahi, H., Ma, Y., Zitnick, L.: Seeing through the Blur. In: CVPR (2012)
Mohimani, G.H., Babaie-Zadeh, M., Gorodnitsky, I., Jutten, C.: Sparse recovery using smoothed ℓ0 (sl0): Convergence analysis. CoRR abs/1001.5073 (2010)
Mumford, D., Shah, J.: Optimal approximations by piecewise smooth functions and associated variational problems. Comm. Pure Appl. Math. 42(5), 577–685 (1989)
Nielsen, M.: Graduated non-convexity by smoothness focusing. In: Proceedings of the British Machine Vision Conference, pp. 60.1–60.10. BMVA Press (1993)
Nikolova, M., Ng, M.K., Tam, C.P.: Fast nonconvex nonsmooth minimization methods for image restoration and reconstruction. Trans. Img. Proc. 19(12), 3073–3088 (2010)
Pretto, A., Soatto, S., Menegatti, E.: Scalable dense large-scale mapping and navigation. In: Proc. of: Workshop on Omnidirectional Robot Vision, ICRA (2010)
Price, B.L., Morse, B.S., Cohen, S.: Simultaneous foreground, background, and alpha estimation for image matting. In: CVPR, pp. 2157–2164. IEEE (2010)
Rangarajan, A., Chellappa, R.: Generalized graduated nonconvexity algorithm for maximum a posteriori image estimation, pp. II:127–II:133 (1990)
Rose, K., Gurewitz, E., Fox, G.: A deterministic annealing approach to clustering. Pattern Recognition Letters 11(9), 589–594 (1990)
Rossi, F., Villa-Vialaneix, N.: Optimizing an organized modularity measure for topographic graph clustering: A deterministic annealing approach. Neurocomputing 73(7-9), 1142–1163 (2010)
Saragih, J.: Deformable face alignment via local measurements and global constraints, pp. 187–207. Springer, Heidelberg (2013)
Shroff, N., Turaga, P.K., Chellappa, R.: Manifold precis: An annealing technique for diverse sampling of manifolds. In: NIPS, pp. 154–162 (2011)
Sindhwani, V., Keerthi, S.S., Chapelle, O.: Deterministic annealing for semi-supervised kernel machines. In: ICML 2006, pp. 841–848. ACM, New York (2006)
Smith, N.A., Eisner, J.: Annealing techniques for unsupervised statistical language learning. In: ACL, Barcelona, Spain, pp. 486–493 (July 2004)
Stoll, M., Volz, S., Bruhn, A.: Joint trilateral filtering for multiframe optical flow. In: ICIP, pp. 3845–3849 (2013)
Sun, D., Roth, S., Black, M.J.: Secrets of optical flow estimation and their principles. In: CVPR, pp. 2432–2439. IEEE (2010)
Terzopoulos, D.: The computation of visible-surface representations. IEEE Trans. Pattern Anal. Mach. Intell. 10(4), 417–438 (1988)
Tirthapura, S., Sharvit, D., Klein, P., Kimia, B.: Indexing based on edit-distance matching of shape graphs. In: SPIE International Symposium on Voice, Video, and Data Communications, pp. 25–36 (1998)
Trzasko, J., Manduca, A.: Highly undersampled magnetic resonance image reconstruction via homotopic ℓ0 -minimization. IEEE Trans. Med. Imaging 28(1), 106–121 (2009)
Vese, L.: A method to convexify functions via curve evolution. Commun. Partial Differ. Equations 24(9-10), 1573–1591 (1999)
Vural, E., Frossard, P.: Analysis of descent-based image registration. SIAM J. Imaging Sciences 6(4), 2310–2349 (2013)
Widder, D.V.: The Heat Equation. Academic Press (1975)
Wright, J., Yang, A.Y., Ganesh, A., Sastry, S.S., Ma, Y.: Robust face recognition via sparse representation. IEEE Trans. Pattern Anal. Mach. Intell. 31(2), 210–227 (2009)
Wu, Z., Tan, P.: Calibrating photometric stereo by holistic reflectance symmetry analysis, pp. 1498–1505. IEEE (2013)
Wu, Z.: The Effective Energy Transformation Scheme as a Special Continuation Approach to Global Optimization with Application to Molecular Conformation. SIAM J. on Optimization 6, 748–768 (1996)
Yuille, A.: Energy Functions for Early Vision and Analog Networks. A.I. memo, Defense Technical Information Center (1987)
Yuille, A.L.: Generalized deformable models, statistical physics, and matching problems. Neural Computation 2, 1–24 (1990)
Yuille, A., Geiger, D., Bulthoff, H.: Stereo integration, mean field theory and psychophysics. In: Faugeras, O. (ed.) ECCV 1990. LNCS, vol. 427, pp. 71–82. Springer, Heidelberg (1990)
Yuille, A.L., Peterson, C., Honda, K.: Deformable templates, robust statistics, and hough transforms, San Diego, CA, pp. 166–174. International Society for Optics and Photonics (1991)
Yuille, A.L., Stolorz, P.E., Utans, J.: Statistical physics, mixtures of distributions, and the em algorithm. Neural Computation 6(2), 334–340 (1994)
Zaslavskiy, M., Bach, F., Vert, J.P.: A path following algorithm for the graph matching problem. IEEE PAMI (2009)
Zerubia, J., Chellappa, R.: Mean field annealing using compound gauss-markov random fields for edge detection and image estimation. IEEE Transactions on Neural Networks 4(4), 703–709 (1993)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2015 Springer International Publishing Switzerland
About this paper
Cite this paper
Mobahi, H., Fisher, J.W. (2015). On the Link between Gaussian Homotopy Continuation and Convex Envelopes. In: Tai, XC., Bae, E., Chan, T.F., Lysaker, M. (eds) Energy Minimization Methods in Computer Vision and Pattern Recognition. EMMCVPR 2015. Lecture Notes in Computer Science, vol 8932. Springer, Cham. https://doi.org/10.1007/978-3-319-14612-6_4
Download citation
DOI: https://doi.org/10.1007/978-3-319-14612-6_4
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-14611-9
Online ISBN: 978-3-319-14612-6
eBook Packages: Computer ScienceComputer Science (R0)