Highly Efficient Surface Normal Integration
Main Article Content
Abstract
The integration of surface normals for the computation of a surface in 3D space is a classic problem in computer vision. However, even nowadays it is still a challenging task to device a method that combines the flexibility to deal with non-trivial computational domains with high accuracy, robustness and computational efficiency. In this paper we propose to use for the first time in the literature Krylov subspace solvers as a main step in tackling the task. While these methods can be very efficient, they may only show their full potential when combined with a numerical preconditioning and even more importantly, a suitable initialization. To address the latter issue we propose to compute this initial state via a recently developed fast marching integrator. Numerical experiments prove the benefits of this novel combination.
Article Details
How to Cite
Breuß, M., Quéau, Y., Bähr, M., & Durou, J.
(2016).
Highly Efficient Surface Normal Integration.
Proceedings Of The Conference Algoritmy, , 204-213.
Retrieved from http://www.iam.fmph.uniba.sk/amuc/ojs/index.php/algoritmy/article/view/409/326
Section
Articles
References
[1] G. Barles. Solutions de viscosit ́ e des ́ equations de Hamilton Jacobi. Springer, 1994.
[2] J. D. Durou, J. F. Aujol, and F. Courteille. Integrating the normal field of a surface in the presence of discontinuities. Energy Minimization Methods in Computer Vision and Pattern Recognition, 5681:261–273, 2009.
[3] J. D. Durou and F. Courteille. Integration of a normal field without boundary condition. Proc. of the First International Workshop on Photometric Analysis For Computer Vision, 2007.
[4] R. T. Frankot and R. Chellappa. A method for enforcing integrability in shape from shading algorithms. IEEE Transactions on Pattern Analysis And Machine Intelligence, 10(4):439– 451, 1988.
[5] S. Galliani, M. Breuß, and Y. C. Ju. Fast and robust surface normal integration by a discrete eikonal equation. Proc. British Machine Vision Conference, pages 1–11, 2012.
[6] M. Harker and P. O’ Leary. Least squares surface reconstruction from measured gradient fields. In Proc. of the IEEE Conference on Computer Vision and Pattern Recognition, 2008.
[7] M. Harker and P. O’Leary. Regularized reconstruction of a surface from its measured gradient field. Journal of Mathematical Imaging and Vision, 51(1):46–70, 2015.
[8] J. J. Helmsen, E. G. Puckett, P. Colella, and M. Dorr. Two new methods for simulating photolithography development in 3d. Optical Microlithography IX, 2726:253–261, 1996.
[9] M.R. Hestenes and E. Stiefel. Methods of conjugate gradients for solving linear systems. NBS Journal of Research, 49:409–436, 1952.
[10] J. Ho, J. Lim, M. H. Yang, and D. Kriegmann. Integrating surface normal vectors using fast marching method. In Proc. European Conference on Computer Vision, 3953:239–250, 2006.
[11] B. K. P. Horn and M. J. Brooks. The variational approach to shape from shading. Computer Vision, Graphics and Image Processing, 33(2):174–208, 1986.
[12] I. Horowitz and N. Kiryati. Depth from gradient fields and control points: bias correction in photometric stereo. Image and Vision Computing, 22:681–694, 2004.
[13] R. Klette and K. Schl ̈ uns. Height data from gradient fields. Proc. International Society for Optical Engineering, 2908:204–215, 1996.
[14] I. Koutis, G. L. Miller, and R. Peng. A Nearly-m log n Time Solver for SDD Linear Systems. In IEEE Annual Symposium on Foundations of Computer Science (FOCS), pages 590–598, Palm Springs, Etats-Unis, ́ 2011.
[15] 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, 140:311–345, 1998.
[16] C. Paige and M. Saunders. Lsqr: An algorithm for sparse linear equations and sparse least squares. ACM Transactions on Mathematical Software, 8(1):43–71, 1982.
[17] Y. Qu ́ eau and J.-D. Durou. Edge-preserving integration of a normal field: Weighted least squares, tv and l1 approaches. In J. F. Aujol, M. Nikolova, and N. Papadakis, editors, Scale Space and Variational Methods in Computer Vision, volume 2749 of Lecture Notes in Computer Science, pages 576–588. Springer International Publishing, 2015.
[18] E. Rouy and A. Tourin. A viscosity solutions approach to shape-from-shading. SIAM Journal on Numerical Analysis, 29(3):867–884, 1992.
[19] Y. Saad. Iterative Methods For Sparse Linear Systems. Society for Industrial and Applied Mathematics, 2nd Edition, 2003.
[20] J. A. Sethian. A fast marching level set method for monotonically advancing fronts. Proc. of the National Academy of Sciences of the United States of America, 93(4):1591–1595, 1996.
[21] J. A. Sethian. Level Set Methods and Fast Marching Methods. Cambridge University Press, 2nd Edition, 1996.
[22] T. Simchony, R. Chellappa, and M. Shao. Direct analytical methods for solving Poisson equations in computer vision problems. IEEE Transactions on Pattern Analysis and Machine Intelligence, 12(5):435–446, 1990.
[23] J. N. Tsitsiklis. Efficient algorithms for globally optimal trajectories. IEEE Transactions on Automatic Control, 40(9):1528–1538, 1995.
[24] R.J. ̃ Woodham. Photometric method for determining surface orientation from multiple images. Optical Engineering, 19(1):134–144, 1980.
[25] Z. Wu and L. Li. A line-integration based method for depth recovery from surface normals. Computer Vision, Graphics and Image Processing, 43(1):53–66, 1988.
[2] J. D. Durou, J. F. Aujol, and F. Courteille. Integrating the normal field of a surface in the presence of discontinuities. Energy Minimization Methods in Computer Vision and Pattern Recognition, 5681:261–273, 2009.
[3] J. D. Durou and F. Courteille. Integration of a normal field without boundary condition. Proc. of the First International Workshop on Photometric Analysis For Computer Vision, 2007.
[4] R. T. Frankot and R. Chellappa. A method for enforcing integrability in shape from shading algorithms. IEEE Transactions on Pattern Analysis And Machine Intelligence, 10(4):439– 451, 1988.
[5] S. Galliani, M. Breuß, and Y. C. Ju. Fast and robust surface normal integration by a discrete eikonal equation. Proc. British Machine Vision Conference, pages 1–11, 2012.
[6] M. Harker and P. O’ Leary. Least squares surface reconstruction from measured gradient fields. In Proc. of the IEEE Conference on Computer Vision and Pattern Recognition, 2008.
[7] M. Harker and P. O’Leary. Regularized reconstruction of a surface from its measured gradient field. Journal of Mathematical Imaging and Vision, 51(1):46–70, 2015.
[8] J. J. Helmsen, E. G. Puckett, P. Colella, and M. Dorr. Two new methods for simulating photolithography development in 3d. Optical Microlithography IX, 2726:253–261, 1996.
[9] M.R. Hestenes and E. Stiefel. Methods of conjugate gradients for solving linear systems. NBS Journal of Research, 49:409–436, 1952.
[10] J. Ho, J. Lim, M. H. Yang, and D. Kriegmann. Integrating surface normal vectors using fast marching method. In Proc. European Conference on Computer Vision, 3953:239–250, 2006.
[11] B. K. P. Horn and M. J. Brooks. The variational approach to shape from shading. Computer Vision, Graphics and Image Processing, 33(2):174–208, 1986.
[12] I. Horowitz and N. Kiryati. Depth from gradient fields and control points: bias correction in photometric stereo. Image and Vision Computing, 22:681–694, 2004.
[13] R. Klette and K. Schl ̈ uns. Height data from gradient fields. Proc. International Society for Optical Engineering, 2908:204–215, 1996.
[14] I. Koutis, G. L. Miller, and R. Peng. A Nearly-m log n Time Solver for SDD Linear Systems. In IEEE Annual Symposium on Foundations of Computer Science (FOCS), pages 590–598, Palm Springs, Etats-Unis, ́ 2011.
[15] 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, 140:311–345, 1998.
[16] C. Paige and M. Saunders. Lsqr: An algorithm for sparse linear equations and sparse least squares. ACM Transactions on Mathematical Software, 8(1):43–71, 1982.
[17] Y. Qu ́ eau and J.-D. Durou. Edge-preserving integration of a normal field: Weighted least squares, tv and l1 approaches. In J. F. Aujol, M. Nikolova, and N. Papadakis, editors, Scale Space and Variational Methods in Computer Vision, volume 2749 of Lecture Notes in Computer Science, pages 576–588. Springer International Publishing, 2015.
[18] E. Rouy and A. Tourin. A viscosity solutions approach to shape-from-shading. SIAM Journal on Numerical Analysis, 29(3):867–884, 1992.
[19] Y. Saad. Iterative Methods For Sparse Linear Systems. Society for Industrial and Applied Mathematics, 2nd Edition, 2003.
[20] J. A. Sethian. A fast marching level set method for monotonically advancing fronts. Proc. of the National Academy of Sciences of the United States of America, 93(4):1591–1595, 1996.
[21] J. A. Sethian. Level Set Methods and Fast Marching Methods. Cambridge University Press, 2nd Edition, 1996.
[22] T. Simchony, R. Chellappa, and M. Shao. Direct analytical methods for solving Poisson equations in computer vision problems. IEEE Transactions on Pattern Analysis and Machine Intelligence, 12(5):435–446, 1990.
[23] J. N. Tsitsiklis. Efficient algorithms for globally optimal trajectories. IEEE Transactions on Automatic Control, 40(9):1528–1538, 1995.
[24] R.J. ̃ Woodham. Photometric method for determining surface orientation from multiple images. Optical Engineering, 19(1):134–144, 1980.
[25] Z. Wu and L. Li. A line-integration based method for depth recovery from surface normals. Computer Vision, Graphics and Image Processing, 43(1):53–66, 1988.