Journal Home > Volume 3 , Issue 2
Computational Visual Media 2017, 3(2): 107-129 https://doi.org/10.1007/s41095-016-0075-z
Research Article | Open Access | Issue | Published: 15 March 2017

Fast and accurate surface normal integration on non-rectangular domains

Show Author's Information Martin Bähr1,  Michael Breuß1( ),  Yvain Quéau2,  Ali Sharifi Boroujerdi1,  Jean-Denis Durou3
Brandenburg Technical University, Institute for Mathematics, Chair for Applied Mathematics, Platz der Deutschen Einheit 1, 03046 Cottbus, Germany.
Technical University Munich, 85748 Garching, Germany.
Université de Toulouse, IRIT, UMR CNRS 5505, Toulouse, France.
Keywords:
3D reconstruction, surface normal integration, Poisson integration, conjugate gradient method, preconditioning, fast marching method, Krylov subspace methods, photometric stereo
Cite this article:
Bähr M, Breuß M, Quéau Y, et al. Fast and accurate surface normal integration on non-rectangular domains. Computational Visual Media, 2017, 3(2): 107-129. https://doi.org/10.1007/s41095-016-0075-z
Download citation
EndNote(RIS)
BibTeX

640

Views

19

Downloads

Citations

20

Crossref

N/A

WoS

21

Scopus

0

CSCD

Abstract Full text About this article

The integration of surface normals for the purpose of computing the shape of a surface in 3D space is a classic problem in computer vision. However, even nowadays it is still a challenging task to devise a method that is flexible enough to work on non-trivial computational domains with high accuracy, robustness, and computational efficiency. By uniting a classic approach for surface normal integration with modern computational techniques, we construct a solver that fulfils these requirements. Building upon the Poisson integration model, we use an iterative Krylov subspace solver as a core step in tackling the task. While such a method can be very efficient, it may only show its full potential when combined with suitable numerical preconditioning and problem-specific initialisation. We perform a thorough numerical study in order to identify an appropriate preconditioner for this purpose. To provide suitable initialisation, we compute this initial state using a recently developed fast marching integrator. Detailed numerical experiments illustrate the benefits of this novel combination. In addition, we show on real-world photometric stereo datasets that the developed numerical framework is flexible enough to tackle modern computer vision applications.


menu
Abstract
Full text
Outline
About this article

Fast and accurate surface normal integration on non-rectangular domains

Show Author's information Martin Bähr1, Michael Breuß1( ), Yvain Quéau2, Ali Sharifi Boroujerdi1, Jean-Denis Durou3
Brandenburg Technical University, Institute for Mathematics, Chair for Applied Mathematics, Platz der Deutschen Einheit 1, 03046 Cottbus, Germany.
Technical University Munich, 85748 Garching, Germany.
Université de Toulouse, IRIT, UMR CNRS 5505, Toulouse, France.

Abstract

The integration of surface normals for the purpose of computing the shape of a surface in 3D space is a classic problem in computer vision. However, even nowadays it is still a challenging task to devise a method that is flexible enough to work on non-trivial computational domains with high accuracy, robustness, and computational efficiency. By uniting a classic approach for surface normal integration with modern computational techniques, we construct a solver that fulfils these requirements. Building upon the Poisson integration model, we use an iterative Krylov subspace solver as a core step in tackling the task. While such a method can be very efficient, it may only show its full potential when combined with suitable numerical preconditioning and problem-specific initialisation. We perform a thorough numerical study in order to identify an appropriate preconditioner for this purpose. To provide suitable initialisation, we compute this initial state using a recently developed fast marching integrator. Detailed numerical experiments illustrate the benefits of this novel combination. In addition, we show on real-world photometric stereo datasets that the developed numerical framework is flexible enough to tackle modern computer vision applications.

Keywords: 3D reconstruction, surface normal integration, Poisson integration, conjugate gradient method, preconditioning, fast marching method, Krylov subspace methods, photometric stereo

References(54)

[1]
P. Pérez,; M. Gangnet,; A. Blake, Poisson image editing. ACM Transactions on Graphics Vol. 22, No. 3, 313-318, 2003.
DOI Google Scholar
[2]
B. K. P. Horn,; M. J. Brooks, The variational approach to shape from shading. Computer Vision, Graphics and Image Processing Vol. 33, No. 2, 174-208, 1986.
DOI Google Scholar
[3]
R. J. Woodham, Photometric method for determining surface orientation from multiple images. Optical Engineering Vol. 19, No. 1, 191139, 1980.
DOI Google Scholar
[4]
S. Zafeiriou,; G. A. Atkinson,; M. F. Hansen,; W. A. P. Smith,; V. Argyriou,; M. Petrou,; M. L. Smith,; L. N. Smith, Face recognition and verification using photometric stereo: The photoface database and a comprehensive evaluation. IEEE Transactions on Information Forensics and Security Vol. 8, No. 1, 121-135, 2013.
DOI Google Scholar
[5]
M. L. Smith,; R. J. Stamp, Automated inspection of textured ceramic tiles. Computers in Industry Vol. 43, No. 1, 73-82, 2000.
DOI Google Scholar
[6]
C. H. Esteban,; G. Vogiatzis,; R. Cipolla, Multiview photometric stereo. IEEE Transactions on Pattern Analysis and Machine Intelligence Vol. 30, No. 3, 548-554, 2008.
DOI Google Scholar
[7]
S. M. Haque,; A. Chatterjee,; V. M. Govindu, High quality photometric reconstruction using a depth camera. In: Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, 2275-2282, 2014.
DOI
[8]
M. Harker,; P. O’Leary, Least squares surface reconstruction from measured gradient fields. In: Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, 1-7, 2008.
DOI
[9]
J.-D. Durou,; J.-F. Aujol,; F. Courteille, Integrating the normal field of a surface in the presence of discontinuities. In: Energy Minimization Methods in Computer Vision and Pattern Recognition. D. Cremers,; Y. Boykov,; A. Blake,; F. R. Schmidt, Eds. Springer Berlin Heidelberg, 261-273, 2009.
DOI
[10]
R. Klette,; K. Schlüns, Height data from gradient fields. In: Proceedings of SPIE 2908, Machine Vision Applications, Architectures, and Systems Integration V, 204-215, 1996.
[11]
E. N. Coleman Jr.,; R. Jain, Obtaining 3-dimensional shape of textured and specular surfaces using foursource photometry. Computer Graphics and Image Processing Vol. 18, No. 4, 309-328, 1982.
DOI Google Scholar
[12]
Z. Wu,; L. Li, A line-integration based method for depth recovery from surface normals. Computer Vision, Graphics and Image Processing Vol. 43, No. 1, 53-66, 1988.
DOI Google Scholar
[13]
A. Robles-Kelly,; E. R. Hancock, A graph-spectral method for surface height recovery. Pattern Recognition Vol. 38, No. 8, 1167-1186, 2005.
DOI Google Scholar
[14]
J. Ho,; J. Lim,; M. H. Yang,; D. Kriegmann, Integrating surface normal vectors using fast marching method. In: Computer Vision–ECCV 2006. A. Leonardis,; H. Bischof,; A. Pinz, Eds. Springer Berlin Heidelberg, 239-250, 2006.
DOI
[15]
S. Galliani,; M. Breuß,; Y. C. Ju, Fast and robust surface normal integration by a discrete eikonal equation. In: Proceedings of the 23rd British Machine Vision Conference, 2012.
DOI
[16]
M. Bähr,; M. Breuß, An improved eikonal method for surface normal integration. In: Pattern Recognition. J. Gall,; P. Gehler,; B. Leibe, Eds. Springer International Publishing, 274-284, 2015.
[17]
R. T. Frankot,; R. Chellappa, A method for enforcing integrability in shape from shading algorithms. IEEE Transactions on Pattern Analysis and Machine Intelligence Vol. 10, No. 4, 439-451, 1988.
DOI Google Scholar
[18]
T. Simchony,; R. Chellappa,; M. Shao, Direct analytical methods for solving Poisson equations in computer vision problems. IEEE Transactions on Pattern Analysis and Machine Intelligence Vol. 12, No. 5, 435-446, 1990.
DOI Google Scholar
[19]
T. Wei,; R. Klette, A wavelet-based algorithm for height from gradients. In: Robot Vision. R. Klette,; S. Peleg,; G. Sommer, Eds. Springer Berlin Heidelberg, 84-90, 2001.
DOI
[20]
P. Kovesi, Shapelets correlated with surface normals produce surfaces. In: Proceedings of the 10th IEEE International Conference on Computer Vision, Vol. 2, 994-1001, 2005.
DOI
[21]
T. Wei,; R. Klette, Depth recovery from noisy gradient vector fields using regularization. In: Computer Analysis of Images and Patterns. N. Petkov,; M. A. Westenberg, Eds. Springer Berlin Heidelberg, 116-123, 2003.
DOI
[22]
B. Karaçali,; W. Snyder, Noise reduction in surface reconstruction from a given gradient field. International Journal on Computer Vision Vol. 60, No. 1, 25-44, 2004.
DOI Google Scholar
[23]
A. Agrawal,; R. Raskar,; R. Chellappa, What is the range of surface reconstructions from a gradient field? In: Computer Vision–ECCV 2006. A. Leonardis,; H. Bischof,; A. Pinz, Eds. Springer Berlin Heidelberg, 578-591, 2006.
DOI
[24]
H. Badri,; H. M. Yahia,; D. Aboutajdine, Robust surface reconstruction via triple sparsity. In: Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, 2283-2290, 2014.
DOI
[25]
Z. Du,; A. Robles-Kelly,; F. Lu, Robust surface reconstruction from gradient field using the L1 norm. In: Proceedings of the 9th Biennial Conference of the Australian Pattern Recognition Society on Digital Image Computing Techniques and Applications, 203-209, 2007.
DOI
[26]
D. Reddy,; A. K. Agrawal,; R. Chellappa, Enforcing integrability by error correction using l1-minimization. In: Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, 2350-2357, 2009.
DOI
[27]
Y. Quéau,; J.-D. Durou, Edge-preserving integration of a normal field: Weighted least squares, TV and L1 approaches. In: Scale Space and Variational Methods in Computer Vision. J.-F. Aujol,; M. Nikolova,; N. Papadakis, Eds. Springer International Publishing 576–588, 2015.
[28]
M. Harker,; P. O’Leary, Regularized reconstruction of a surface from its measured gradient field. Journal of Mathematical Imaging and Vision Vol. 51, No. 1, 46-70, 2015.
DOI Google Scholar
[29]
M. Breuß,; Y. Quéau,; M. Bähr,; J.-D. Durou, Highly efficient surface normal integration. In: Proceedings of the 20th Conference on Scientific Computing, 204-213, 2016.
[30]
A. Meister, Comparison of different Krylov subspace methods embedded in an implicit finite volume scheme for the computation of viscous and inviscid flow fields on unstructured grids. Journal of Computational Physics Vol. 140, No. 2, 311-345, 1998.
DOI Google Scholar
[31]
Y. Saad, Iterative Methods for Sparse Linear Systems. Society for Industrial and Applied Mathematics, 2003.
DOI
[32]
J.-D. Durou,; F. Courteille, Integration of a normal field without boundary condition. In: Proceedings of the 1st International Workshop on Photometric Analysis for Computer Vision, 2007.
[33]
R. Kimmel,; J. A. Sethian, Optimal algorithm for shape from shading and path planning. Journal of Mathematical Imaging and Vision Vol. 14, No. 3, 237-244, 2001.
DOI Google Scholar
[34]
J. N. Tsitsiklis, Efficient algorithms for globally optimal trajectories. IEEE Transactions on Automatic Control Vol. 40, No. 9, 1528-1538, 1995.
DOI Google Scholar
[35]
J. A. Sethian, A fast marching level set method for monotonically advancing fronts. Proceedings of the National Academy of Sciences of the United States of America Vol. 93, No. 4, 1591-1595, 1996.
DOI Google Scholar
[36]
J. J. Helmsen,; E. G. Puckett,; P. Colella,; M. Dorr, Two new methods for simulating photolithography development in 3D. In: Proceedings of SPIE 2726, Optical Microlithography IX, 253-261, 1996.
DOI
[37]
J. A. Sethian, Level Set Methods and Fast Marching Methods: Evolving Interfaces in Computational Geometry, Fluid Mechanics, Computer Vision, and Materials Science. Cambridge University Press, 1999.
[38]
L. Yatziv,; A. Bartesaghi,; G. Sapiro, O(N) implementation of the fast marching algorithm. Journal of Computational Physics Vol. 212, No. 2, 393-399, 2006.
DOI Google Scholar
[39]
S. Cacace,; E. Cristiani,; M. Falcone, Can local single-pass methods solve any stationary Hamilton–Jacobi–Bellman equation? SIAM Journal on Scientific Computing Vol. 36, No. 2, A570-A587, 2014.
DOI Google Scholar
[40]
H. Zimmer,; A. Bruhn,; L. Valgaerts,; M. Breuß,; J. Weickert,; B. Rosenhahn,; H.-P. Seidel, PDE-based anisotropic disparity-driven stereo vision. In: Proceddings of the 13th International Fall Workshop Vision, Modeling, and Visualization, 263-272, 2008.
[41]
A. Meister, Numerik Linearer Gleichungssysteme. Eine Einführung in Moderne Verfahren. Springer Spektrum, 2014.
DOI
[42]
M. R. Hestenes,; E. Stiefel, Methods of conjugate gradients for solving linear systems. Journal of Research of the National Bureau of Standards Vol. 6, No. 49, 46-70, 1952.
DOI Google Scholar
[43]
G. Meurant, Computer Solution of Large Linear Systems. Elsevier Science, 1999.
[44]
G. Meurant, The Lanczos and Conjugate Gradient Algorithms: From Theory to Finite Precision Computations. Society for Industrial and Applied Mathematics, 2006.
DOI
[45]
G. H. Golub,; C. F. van Loan, Matrix Computation, 3rd edn. Johns Hopkins, 1996.
[46]
J. A. Meijerink,; H. A. van der Vorst, An iterative solution method for linear systems of which the coefficient matrix is a symmetric M-matrix. Mathematics of Computation Vol. 31, No. 137, 148-162, 1977.
DOI Google Scholar
[47]
D. S. Kershaw, The incomplete Cholesky-conjugate gradient method for the iterative solution of systems of linear equations. Journal of Computational Physics Vol. 26, No. 1, 43-65, 1978.
DOI Google Scholar
[48]
M. Benzi, Preconditioning techniques for large linear systems: A survey. Journal of Computational Physics Vol. 182, No. 2, 418-477, 2002.
DOI Google Scholar
[49]
E. F. Kaasschieter, Preconditioned conjugate gradients for solving singular systems. Journal of Computational and Applied Mathematics Vol. 24, Nos. 1–2, 265-275, 1988.
DOI Google Scholar
[50]
J. M. Tang,; C. Vuik, Acceleration of preconditioned Krylov solvers for bubbly flow problems. In: Parallel Processing and Applied Mathematics. R. Wyrzykowski,; J. Dongarra,; K. Karczewski,; J. Wasniewski, Eds. Springer Berlin Heidelberg, 1323-1332, 2008.
DOI
[51]
T. A. Manteuffel, An incomplete factorization technique for positive definite linear systems. Mathematics of Computation Vol. 34, No. 150, 473-497, 1980.
DOI Google Scholar
[52]
Z. Wang,; A. C. Bovik,; H. R. Sheikh,; E. P. Simoncelli, Image quality assessment: From error visibility to structural similarity. IEEE Transactions on Image Processing Vol. 13, No. 4, 600-612, 2004.
DOI Google Scholar
[53]
L. Noakes,; R. Kozera, Nonlinearities and noise reduction in 3-source photometric stereo. Journal of Mathematical Imaging and Vision Vol. 18, No. 2, 119-127, 2003.
DOI Google Scholar
[54]
J. Y. Chang,; K. M. Lee,; S. U. Lee, Multiview normal field integration using level set methods. In: Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, 1-8, 2007.
DOI
Publication history
Copyright
Rights and permissions

Publication history

Revised: 18 October 2016
Accepted: 21 December 2016
Published: 15 March 2017
Issue date: June 2017

Copyright

© The Author(s) 2016

Rights and permissions

This article is published with open access at Springerlink.com

The articles published in this journal are distributed under the terms of the Creative Commons Attribution 4.0 International License (http:// creativecommons.org/licenses/by/4.0/), which permits unrestricted use, distribution, and reproduction in any medium, provided you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license, and indicate if changes were made.

Other papers from this open access journal are available free of charge from http://www.springer.com/journal/41095. To submit a manuscript, please go to https://www. editorialmanager.com/cvmj.

Return