[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ Skip to main content
Springer Nature Link
Log in

A Gauss-Newton Method for the Integration of Spatial Normal Fields in Shape Space

  • Published:
Journal of Mathematical Imaging and Vision Aims and scope Submit manuscript

Abstract

We address the task of adjusting a surface to a vector field of desired surface normals in space. The described method is entirely geometric in the sense, that it does not depend on a particular parametrization of the surface in question. It amounts to solving a nonlinear least-squares problem in shape space. Previously, the corresponding minimization has been performed by gradient descent, which suffers from slow convergence and susceptibility to local minima. Newton-type methods, although significantly more robust and efficient, have not been attempted as they require second-order Hadamard differentials. These are difficult to compute for the problem of interest and in general fail to be positive-definite symmetric. We propose a novel approximation of the shape Hessian, which is not only rigorously justified but also leads to excellent numerical performance of the actual optimization. Moreover, a remarkable connection to Sobolev flows is exposed. Three other established algorithms from image and geometry processing turn out to be special cases of ours. Our numerical implementation founds on a fast finite-elements formulation on the minimizing sequence of triangulated shapes. A series of examples from a wide range of different applications is discussed to underline flexibility and efficiency of the approach.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
£29.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (United Kingdom)

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Balzer, J., Werling, S.: Principles of shape from specular reflection. Measurement 43, 1305–1317 (2010)

    Article  Google Scholar 

  2. Woodham, R.: Gradient and curvature from photometric stereo including local confidence estimation. J. Opt. Soc. Am. A 11, 3050–3068 (1994)

    Article  Google Scholar 

  3. Frankot, R., Chellappa, R.: A method for enforcing integrability to shape from shading. IEEE Trans. Pattern Anal. Mach. Intell. 10(4), 439–451 (1988)

    Article  MATH  Google Scholar 

  4. Simchony, T., Chellappa, R., Shao, M.: Direct analytical methods for solving Poisson equations in computer vision problems. IEEE Trans. Pattern Anal. Mach. Intell. 12(5), 435–446 (1990)

    Article  Google Scholar 

  5. Hicks, R.: Designing a mirror to realize a given projection. J. Opt. Soc. Am. A 22(2), 323–330 (2005)

    Article  Google Scholar 

  6. Ettl, S., Kaminski, J., Knauer, M., Häusler, G.: Shape reconstruction from gradient data. Appl. Opt. 47(12), 2091–2097 (2008)

    Article  Google Scholar 

  7. Durou, J.D., Aujol, J.F., Courteille, F.: Integrating the normal field of a surface in the presence of discontinuities. In: Lecture Notes in Computer Science, vol. 5681, pp. 261–273. Springer, Berlin (2009)

    Google Scholar 

  8. Zach, C., Pock, T., Bischof, H.: A globally optimal algorithm for robust TV-L 1 range image integration. IEEE Int. Conf. Comput. Vis. 1, 1–8 (2007)

    Google Scholar 

  9. Aubert, G., Barlaud, M., Faugeras, O., Besson, S.: Image segmentation using active contours: Calculus of variations or shape gradients? SIAM J. Appl. Math. 63(6), 2128–2154 (2003)

    Article  MathSciNet  MATH  Google Scholar 

  10. Younes, L.: Shapes and Diffeomorphisms. Applied Mathematical Sciences, vol. 171. Springer, Berlin (2010)

    Book  MATH  Google Scholar 

  11. Tasdizen, T., Whitaker, R., Burchard, P., Osher, S.: Geometric surface processing via normal maps. ACM Trans. Graph. 22(4), 1012–1033 (2003)

    Article  Google Scholar 

  12. Solem, J., Overgaard, N.: A gradient descent procedure for variational dynamic surface problems with constraints. In: IEEE Proceedings Workshop on Variational, Geometric, and Level Set Methods in Computer Vision, pp. 332–343 (2005)

    Chapter  Google Scholar 

  13. Chang, J., Lee, K., Lee, S.: Multiview normal field integration using level set methods. Proc. CVPR IEEE 1, 1–8 (2007)

    MathSciNet  Google Scholar 

  14. Goldlücke, B., Ihrke, I., Linz, C., Magnor, M.: Weighted minimal surface reconstruction. IEEE Trans. Pattern Anal. Mach. Intell. 29(7), 1194–1208 (2007)

    Article  Google Scholar 

  15. Bar, L., Sapiro, G.: Generalized Newton-type methods for energy formulations in image processing. SIAM J. Imaging Sci. 2(2), 508–531 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  16. Hintermüller, M., Ring, W.: A second order shape optimization approach for image segmentation. SIAM J. Appl. Math. 64(2), 442–467 (2003)

    Article  MathSciNet  MATH  Google Scholar 

  17. Balzer, J.: Second-order domain derivative of normal-dependent boundary integrals. J. Evol. Equ. 10, 551–570 (2010)

    Article  MathSciNet  Google Scholar 

  18. Sundaramoorthi, G., Yezzi, A., Mennucci, A.: Sobolev active contours. Int. J. Comput. Vis. 73(3), 345–366 (2007)

    Article  Google Scholar 

  19. Calder, J., Mansouri, A., Yezzi, A.: Image sharpening via Sobolev gradient flows. SIAM J. Imaging Sci. 3(4), 981–1014 (2010)

    Article  MathSciNet  MATH  Google Scholar 

  20. Horn, B.: Height and gradient from shading. Int. J. Comput. Vis. 5(1), 37–75 (1999)

    Article  Google Scholar 

  21. Pinkall, U., Polthier, K.: Computing discrete minimal surfaces and their conjugates. Exp. Math. 2(1), 15–36 (1993)

    Article  MathSciNet  MATH  Google Scholar 

  22. Yu, Y., Zhou, K., Xu, D., Shi, X., Bao, H., Guo, B., Shum, H.: Mesh editing with Poisson-based gradient field manipulation. ACM Trans. Graph. 23(3), 644–651 (2004)

    Article  Google Scholar 

  23. Xu, W.W., Zhou, K.: Gradient domain mesh deformation—a survey. J. Comput. Sci. Technol. 24(1), 6–18 (2009)

    Article  Google Scholar 

  24. Sethian, J.: Level Set Methods and Fast Marching Methods. Cambridge University Press, Cambridge (1999)

    MATH  Google Scholar 

  25. Kazhdan, M., Bolitho, M., Hoppe, H.: Poisson surface reconstruction. In: Polthier, K., Sheffer, A. (eds.) Eurographics Symposium on Geometry Processing (2006)

    Google Scholar 

  26. Delfour, M., Zolésio, J.P.: Shapes and Geometries. SIAM, Philadelphia (2001)

    MATH  Google Scholar 

  27. Nocedal, J., Wright, S.: Numerical Optimization, 2nd edn. Springer, Berlin (2006)

    MATH  Google Scholar 

  28. Morton, K., Mayers, D.: Numerical Solution of Partial Differential Equations. Oxford University Press, Oxford (2005)

    Book  MATH  Google Scholar 

  29. Eckstein, I., Pons, J., Tong, Y., Kuo, C., Desbrun, M.: In: Eurographics Symposium on Geometry Processing (2007)

    Google Scholar 

  30. Burger, M.: A framework for the construction of level set methods for shape optimization and reconstruction. Interfaces Free Bound. 5, 301–329 (2003)

    Article  MathSciNet  MATH  Google Scholar 

  31. Cantarella, J., DeTurck, D., Gluck, H.: Vector calculus and the topology of domains in 3-space. Am. Math. Mon. 109(5), 409–442 (2002)

    Article  MathSciNet  MATH  Google Scholar 

  32. Botsch, M., Steinberg, S., Bischoff, S., Kobbelt, L.: OpenMesh—a generic and efficient polygon mesh data structure. In: OpenSG Symposium (2002)

    Google Scholar 

  33. Davis, T., Hager, W.: Dynamic supernodes in sparse Cholesky update/downdate and triangular solves. ACM Trans. Math. Softw. 35(4), 1–27 (2009)

    Article  MathSciNet  Google Scholar 

  34. Geuzaine, C., Remacle, J.: Gmsh: a three-dimensional finite element mesh generator with built-in pre- and post-processing facilities. Int. J. Numer. Methods Eng. 79(11), 1309–1331 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  35. Taubin, G.: A signal processing approach to fair surface design. In: Proceedings of SIGGRAPH, pp. 351–358 (1995)

    Google Scholar 

  36. Elsey, M., Esedoglu, S.: Analogue of the total variation denoising model in the context of geometry processing. SIAM J. Multiscale Model. Simul. 7(4), 1549–1573 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  37. Snyder, W.: NC State University Image Analysis Laboratory Database (2002)

  38. Balzer, J., Höfer, S., Beyerer, J.: Multiview specular stereo reconstruction of large mirror surfaces. In: ICCV, vol. 1, pp. 2537–2544 (2011)

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Geometric Modeling and Scientific Visualization Center, King Abdullah University of Science and Technology, P.O. Box 2050, Thuwal, 23955-6900, Kingdom of Saudi Arabia

    Jonathan Balzer

Authors
  1. Jonathan Balzer
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Jonathan Balzer.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Balzer, J. A Gauss-Newton Method for the Integration of Spatial Normal Fields in Shape Space. J Math Imaging Vis 44, 65–79 (2012). https://doi.org/10.1007/s10851-011-0311-1

Download citation

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10851-011-0311-1

Keywords

Search

Navigation