Regularized Reconstruction of a Surface from its Measured Gradient Field

详细信息    查看全文

• 作者：Matthew Harker ; Paul O’Leary
• 关键词：Gradient field ; Inverse problems ; Sylvester Equation ; Spectral methods ; Discrete orthogonal basis functions ; Tikhonov regularization ; Boundary conditions ; Weighted least squares
• 刊名：Journal of Mathematical Imaging and Vision
• 出版年：2015
• 出版时间：January 2015
• 年：2015
• 卷：51
• 期：1
• 页码：46-70
• 全文大小：4,389 KB
• 参考文献：1. Agrawal, A., Raskar, R., Chellappa, R.: What is the range of surface reconstruction from a gradient field? In: ECCV 2006, pp. 578-91. LNCS, Graz, Austria (2006)
  2. Balzer, J.: A Gauss–Newton method for the integration of spatial normal fields in shape space. J. Math. Imaging Vis. 44(1), 65-9 (2011) CrossRef
  3. Balzer, J., M?rwald, T.: Isogeometric finite-elements methods and variational reconstruction tasks in vision: a perfect match. In: CVPR 2012, pp. 1624-631. IEEE, Providence, RI (2012)
  4. Bartels, R., Stewart, G.: Algorithm 432: solution of the matrix equation AX + XB = C. Commun. ACM 15, 820-26 (1972) CrossRef
  5. Belge, M., Kilmer, M., Miller, E.: Efficient determination of multiple regularization parameters in a generalized L-curve framework. Inverse Prob. 18, 1161-183 (2002) CrossRef
  6. Bracewell, R.: The Fourier Transform and Its Applications, 2nd edn. McGraw-Hill, New York (1986)
  7. Burden, R., Faires, J.: Numerical Analysis, 8th edn. Thomson Learning, Inc., Belmont (2005)
  8. Dorr, F.: The direct solution of the discrete Poisson equation on a rectangle. SIAM Rev. 12(2), 248-63 (1970) CrossRef
  9. Durou, J.D., Courteille, F.: Integration of a normal field without boundary condition. In: Proc. 1st Workshop on PACV. Rio de Janeiro, Brazil (2007)
  10. Engl, H., Hanke, M., Neubauer, A.: Regularization of Inverse Problems. Kluwer Academic Publishers, Dordrecht (2000)
  11. Frankot, R., Chellappa, R.: A method for enforcing integrability in shape from shading algorithms. IEEE PAMI 10(4), 439-51 (1988) CrossRef
  12. Galliani, S., Breu?, M., Ju, Y.: Fast and robust surface normal integration by a discrete eikonal equation. In: BMVC. BMVA, Guildford, UK (2012)
  13. Golub, G., Meurant, G.: Matrices, Moments and Quadrature with Applications. Princeton University Press, Princeton (2010)
  14. Golub, G., Nash, S., Van Loan, C.: A Hessenberg–Schur method for the problem AX+XB = C. IEEE Trans. Autom. Control 24(6), 909-13 (1979) CrossRef
  15. Golub, G., Van Loan, C.: Matrix Computations, 3rd edn. The Johns Hopkins University Press, Baltimore (1996)
  16. Gram, J.: Ueber die Entwickelung reeller Functionen in Reihen mittelst der Methode der kleinsten Quadrate. Journal für die reine und angewandte Mathematik 94(1), 41-3 (1883)
  17. Haar, A.: Zur theorie der orthogonalen funktionensysteme (erste mitteilung). Mathematische Annalen 69, 331-71 (1910) CrossRef
  18. Hansen, P.: Discrete inverse problems: insight and algorithms. In: Fundamentals of Algorithms. SIAM, Philadelphia (2010)
  19. Hansen, P., O’Leary, D.: The use of the L-curve in the regularization of discrete ill-posed problems. SIAM J. Sci. Comput. 14(6), 1487-503 (1993) CrossRef
  20. Harker, M., O’Leary, P.: Least squares surface reconstruction from measured gradient fields. In: CVPR 2008, pp. 1-. IEEE, Anchorage, AK (2008)
  21. Harker, M., O’Leary, P.: Least squares surface reconstruction from gradients: direct algebraic methods with spectral, Tikhonov, and constrained regularization. In: IEEE CVPR, pp. 2529-536. IEEE, Colorado Springs, CO (2011)
  22. Higham, N.: Accuracy and Stability of Numerical Algorithms, 2nd edn. SIAM, Philadelphia (2002) CrossRef
  23. Higham, N.: Computing the nearest correlation matrix: a problem from finance. IMA J. Numer. Anal. 22, 329-43 (2002) CrossRef
  24. Horn, B., Brooks, M.: The variational approach
• 刊物类别：Computer Science
• 刊物主题：Computer Imaging, Vision, Pattern Recognition and Graphics
  Image Processing and Computer Vision
  Artificial Intelligence and Robotics
  Automation and Robotics
  
• 出版者：Springer Netherlands
• ISSN：1573-7683

文摘

This paper presents several new algorithms for the regularized reconstruction of a surface from its measured gradient field. By taking a matrix-algebraic approach, we establish general framework for the regularized reconstruction problem based on the Sylvester Matrix Equation. Specifically, Spectral Regularization via Generalized Fourier Series (e.g., Discrete Cosine Functions, Gram Polynomials, Haar Functions, etc.), Tikhonov regularization, Constrained Regularization by imposing boundary conditions, and regularization via Weighted least squares can all be solved expediently in the context of the Sylvester Equation framework. State-of-the-art solutions to this problem are based on sparse matrix methods, which are no better than \(\mathcal {O}\!\left( n^6\right) \) algorithms for an \(m\times n\) surface with \(m \sim n\) . In contrast, the newly proposed methods are based on the global least squares cost function and are all \(\mathcal {O}\!\left( n^3\right) \) algorithms. In fact, the new algorithms have the same computational complexity as an SVD of the same size. The new algorithms are several orders of magnitude faster than the state-of-the-art; we therefore present, for the first time, Monte-Carlo simulations demonstrating the statistical behaviour of the algorithms when subject to various forms of noise. We establish methods that yield the lower bound of their respective cost functions, and therefore represent the “Gold-Standard-benchmark solutions for the various forms of noise. The new methods are the first algorithms for regularized reconstruction on the order of megapixels, which is essential to methods such as Photometric Stereo.