Kernel Nyström method for light transport

ABSTRACT

We propose a kernel Nyström method for reconstructing the light transport matrix from a relatively small number of acquired images. Our work is based on the generalized Nyström method for low rank matrices. We introduce the light transport kernel and incorporate it into the Nyström method to exploit the nonlinear coherence of the light transport matrix. We also develop an adaptive scheme for efficiently capturing the sparsely sampled images from the scene. Our experiments indicate that the kernel Nyström method can achieve good reconstruction of the light transport matrix with a few hundred images and produce high quality relighting results. The kernel Nyström method is effective for modeling scenes with complex lighting effects and occlusions which have been challenging for existing techniques.

REFERENCES

• 1: Xiaobo An , Fabio Pellacini, AppProp: all-pairs appearance-space edit propagation, ACM Transactions on Graphics (TOG), v.27 n.3, August 2008
• 2: Yung-Yu Chuang , Douglas E. Zongker , Joel Hindorff , Brian Curless , David H. Salesin , Richard Szeliski, Environment matting extensions: towards higher accuracy and real-time capture, Proceedings of the 27th annual conference on Computer graphics and interactive techniques, p.121-130, July 2000 [doi>10.1145/344779.344844]
• 3: Nello Cristianini , John Shawe-Taylor, An introduction to support Vector Machines: and other kernel-based learning methods, Cambridge University Press, New York, NY, 1999
• 4: Paul E. Debevec , Jitendra Malik, Recovering high dynamic range radiance maps from photographs, Proceedings of the 24th annual conference on Computer graphics and interactive techniques, p.369-378, August 1997 [doi>10.1145/258734.258884]
• 5: Paul Debevec , Tim Hawkins , Chris Tchou , Haarm-Pieter Duiker , Westley Sarokin , Mark Sagar, Acquiring the reflectance field of a human face, Proceedings of the 27th annual conference on Computer graphics and interactive techniques, p.145-156, July 2000 [doi>10.1145/344779.344855]
• 6: Fazel, M. 2002. Matrix rank minimization with applications. PhD thesis, Stanford University.
• 7: Martin Fuchs , Volker Blanz , Hendrik P.A. Lensch , Hans-Peter Seidel, Adaptive sampling of reflectance fields, ACM Transactions on Graphics (TOG), v.26 n.2, p.10-es, June 07 [doi>10.1145/1243980.1243984]
• 8: Garg, G., Talvala, E.-V., Levoy, M., and Lensch, H. P. A. 2006. Symmetric photography: Exploiting data-sparseness in reflectance fields. In Rendering Techniques 2006: 17th Eurographics Workshop on Rendering, 251--262.
• 9: Michael Goesele , Hendrik P. A. Lensch , Jochen Lang , Christian Fuchs , Hans-Peter Seidel, DISCO: acquisition of translucent objects, ACM Transactions on Graphics (TOG), v.23 n.3, August 2004
• 10: Goreinov, S., Tyrtyshnikov, E. E., and Zamarashkin, N. L. 1997. A theory of pseudo-skeleton approximations. Linear Algeabra and Applications 261, 1--21.
• 11: Miloš Hašan , Fabio Pellacini , Kavita Bala, Matrix row-column sampling for the many-light problem, ACM Transactions on Graphics (TOG), v.26 n.3, July 2007
• 12: Hašan, M., Velazquez-Armendariz, E., Pellacini, F., and Bala, K. 2008. Tensor clustering for rendering manylight animations. Computer Graphics Forum (Proc. Eurographics Rendering 2008) 27, 4, 1105--1114.
• 13: Hawkins, T., Einarsson, P., and Debevec, P. 2005. A dual light stage. In Rendering Techniques 2005: 16th Eurographics Workshop on Rendering, 91--98.
• 14: Marc Levoy , Pat Hanrahan, Light field rendering, Proceedings of the 23rd annual conference on Computer graphics and interactive techniques, p.31-42, August 1996 [doi>10.1145/237170.237199]
• 15: Zhouchen Lin , Tien-Tsin Wong , Heung-Yeung Shum, Relighting with the Reflected Irradiance Field: Representation, Sampling and Reconstruction, International Journal of Computer Vision, v.49 n.2-3, p.229-246, September-October 2002 [doi>10.1023/A:1020153824351]
• 16: Dhruv Mahajan , Ira Kemelmacher Shlizerman , Ravi Ramamoorthi , Peter Belhumeur, A theory of locally low dimensional light transport, ACM Transactions on Graphics (TOG), v.26 n.3, July 2007
• 17: Vincent Masselus , Pieter Peers , Philip Dutré , Yves D. Willems, Relighting with 4D incident light fields, ACM Transactions on Graphics (TOG), v.22 n.3, July 2003
• 18: Masselus, V., Peers, P., Dutr0108, P., and Willems, Y. D. 2004. Smooth reconstruction and compact representation of reflectance functions for image-based relighting. In Rendering Techniques 2004: 15th Eurographics Workshop on Rendering, 287--298.
• 19: Wojciech Matusik , Hanspeter Pfister , Addy Ngan , Paul Beardsley , Remo Ziegler , Leonard McMillan, Image-based 3D photography using opacity hulls, ACM Transactions on Graphics (TOG), v.21 n.3, July 2002
• 20: Matusik, W., Loper, M., and Pfister, H. 2004. Progressively-refined reflectance functions from natural illumination. In Rendering Techniques 2004: 15th Eurographics Workshop on Rendering, 299--308.
• 21: Ren Ng , Ravi Ramamoorthi , Pat Hanrahan, All-frequency shadows using non-linear wavelet lighting approximation, ACM Transactions on Graphics (TOG), v.22 n.3, July 2003
• 22: Peers, P., and Dutré, P. 2005. Inferring reflectance functions from wavelet noise. In Rendering Techniques 2005: 16th Eurographics Workshop on Rendering, 173--182.
• 23: Pieter Peers , Karl vom Berge , Wojciech Matusik , Ravi Ramamoorthi , Jason Lawrence , Szymon Rusinkiewicz , Philip Dutré, A compact factored representation of heterogeneous subsurface scattering, ACM Transactions on Graphics (TOG), v.25 n.3, July 2006
• 24: Pieter Peers , Dhruv K. Mahajan , Bruce Lamond , Abhijeet Ghosh , Wojciech Matusik , Ravi Ramamoorthi , Paul Debevec, Compressive light transport sensing, ACM Transactions on Graphics (TOG), v.28 n.1, p.1-18, January 2009 [doi>10.1145/1477926.1477929]
• 25: Platt, J. C. 2005. Fastmap, metricmap, and landmark mds are all nyström algorithms. In 10th International Workshop on Artificial Intelligence and Statistics, 261--268.
• 26: William H. Press , Saul A. Teukolsky , William T. Vetterling , Brian P. Flannery, Numerical Recipes in C: The Art of Scientific Computing, Cambridge University Press, New York, NY, 1992
• 27: Sen, P., and Darabi, S. 2009. Compressive Dual Photography. Computer Graphics Forum 28, 2, 609--618.
• 28: Pradeep Sen , Billy Chen , Gaurav Garg , Stephen R. Marschner , Mark Horowitz , Marc Levoy , Hendrik P. A. Lensch, Dual photography, ACM Transactions on Graphics (TOG), v.24 n.3, July 2005
• 29: Andreas Wenger , Andrew Gardner , Chris Tchou , Jonas Unger , Tim Hawkins , Paul Debevec, Performance relighting and reflectance transformation with time-multiplexed illumination, ACM Transactions on Graphics (TOG), v.24 n.3, July 2005
• 30: Williams, C., and Seeger, M. 2000. Using the nyström method to speed up kernel machines. Advances in Neural Information Processing Systems 13, 682--688.
• 31: Douglas E. Zongker , Dawn M. Werner , Brian Curless , David H. Salesin, Environment matting and compositing, Proceedings of the 26th annual conference on Computer graphics and interactive techniques, p.205-214, July 1999 [doi>10.1145/311535.311558]

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.4 IMAGE PROCESSING AND COMPUTER VISION
      I.4.1 Digitization and Image Capture

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.1 Numerical Algorithms and Problems
          Subjects: Computations on matrices

  I. Computing Methodologies
  I.4 IMAGE PROCESSING AND COMPUTER VISION
      I.4.5 Reconstruction
  I.6 SIMULATION AND MODELING
      I.6.5 Model Development
          Subjects: Modeling methodologies

General Terms:
Algorithms, Design, Theory