Compressive light transport sensing

ABSTRACT

In this article we propose a new framework for capturing light transport data of a real scene, based on the recently developed theory of compressive sensing. Compressive sensing offers a solid mathematical framework to infer a sparse signal from a limited number of nonadaptive measurements. Besides introducing compressive sensing for fast acquisition of light transport to computer graphics, we develop several innovations that address specific challenges for image-based relighting, and which may have broader implications. We develop a novel hierarchical decoding algorithm that improves reconstruction quality by exploiting interpixel coherency relations. Additionally, we design new nonadaptive illumination patterns that minimize measurement noise and further improve reconstruction quality. We illustrate our framework by capturing detailed high-resolution reflectance fields for image-based relighting.

REFERENCES

• 1: Baraniuk, R., Davenport, M., DeVore, R., and Wakin, M. 2008. A simple proof of the restricted isometry property for random matrices. Constructive Approx.
• 2: Candès, E., and Tao, T. 2006. Near optimal signal recovery from random projections: Universal encoding strategies? IEEE Trans. Inform. Theory 52, 12, 5406--5425.
• 3: Candès, E., Romberg, J., and Tao, T. 2006. Stable signal recovery from incomplete and inaccurate measurements. Comm. Pure Appl. Math. 59, 8, 1207--1223.
• 4: Candès, E. 2006. Compressive sampling. Int. Congress Math., 3, 1433--1452.
• 5: Scott Shaobing Chen , David L. Donoho , Michael A. Saunders, Atomic Decomposition by Basis Pursuit, SIAM Review, v.43 n.1, p.129-159, 2001 [doi>10.1137/S003614450037906X]
• 6: 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]
• 7: Cotter, S. F., Rao, B. D., Engan, K., and Kreutz-Delgado, K. 2005. Sparse solutions to linear inverse problems with multiple measurement vectors. IEEE Trans. Signal Proces. 53, 7.
• 8: CSR 2009. Compressive sensing resources. http://www.dsp.ece.rice.edu/cs/.
• 9: Dantzig, G. 1963. Linear Programming and Extensions. Princeton University Press.
• 10: 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]
• 11: Yaakov Tsaig , David L. Donoho, Extensions of compressed sensing, Signal Processing, v.86 n.3, p.549-571, March 2006 [doi>10.1016/j.sigpro.2005.05.029]
• 12: Donoho, D. 2006. Compressed sensing. IEEE Trans. Inform. Theory 52, 4, 1289--1306.
• 13: Elad, M. 2007. Optimized projections for compressed sensing. IEEE Trans. Signal Process. 55, 12, 5695--5702.
• 14: 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]
• 15: Garg, G., Talvala, E.-V., Levoy, M., and Lensch, H. P. A. 2006. Symmetric photography: Exploiting data-sparseness in reflectance fields. In Proceedings of the 17th Eurographics Workshop on Rendering, 251--262.
• 16: Ji, S., Dunson, D., and Carin, L. 2008. Multi-Task compressive sensing. IEEE Trans. Signal. Process. To appear.
• 17: Ji, S., Xue, Y., and Carin, L. 2007. Bayesian compressive sensing. IEEE Trans. Signal Process.
• 18: Liu, X., Sloan, P.-P., Shum, H.-Y., and Snyder, J. 2004. All-Frequency precomputed radiance transfer for glossy objects. In Proceedings of the 15th Eurographics Workshop on Rendering, 337--344.
• 19: 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
• 20: Masselus, V., Peers, P., Dutré, P., and Willems, Y. D. 2004. Smooth reconstruction and compact representation of reflectance functions for image-based relighting. In Proceedings of the 15th Eurographics Workshop on Rendering, 287--298.
• 21: Matusik, W., Loper, M., and Pfister, H. 2004. Progressively-Refined reflectance functions from natural illumination. In Proceedings of the 15th Eurographics Workshop on Rendering, 299--308.
• 22: Needell, D. and Vershynin, R. 2007a. Uniform uncertainty principle and signal recovery via regularized orthogonal matching pursuit. Found. Comput. Math. To appear.
• 23: Needell, D. and Vershynin, R. 2007b. Signal recovery from incomplete and inaccurate measurements via regularized orthogonal matching pursuit. http://www.math.ucdavis.edu/~dneedell/papers/ROMP-stability.pdf.
• 24: 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
• 25: Pieter Peers , Philip Dutré, Wavelet environment matting, Proceedings of the 14th Eurographics workshop on Rendering, June 25-27, 2003, Leuven, Belgium
• 26: Peers, P. and Dutré, P. 2005. Inferring reflectance functions from wavelet noise. In Proceedings of the 16th Eurographics Workshop on Rendering, 173--182.
• 27: Peers, P., Hawkins, T., and Debevec, P. 2007. A reflective light stage. Tech. rep., ICT-USC, ICT-TR-04.2006.
• 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: Tropp, J. and Gilbert, A. 2007. Signal recovery from partial information via orthogonal matching pursuit. IEEE Trans. Inform. Theory 53, 12, 4655--4666.
• 30: Joel A. Tropp , Anna C. Gilbert , Martin J. Strauss, Algorithms for simultaneous sparse approximation: part I: Greedy pursuit, Signal Processing, v.86 n.3, p.572-588, March 2006 [doi>10.1016/j.sigpro.2005.05.030]
• 31: Weiss, Y., Chang, H. S., and Freeman, W. T. 2007. Learning compressed sensing. In Allerton Conference on Communication, Control, and Computing.
• 32: 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
• 33: Stephen J. Wright, Primal-dual interior-point methods, Society for Industrial and Applied Mathematics, Philadelphia, PA, 1997
• 34: 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.3 COMPUTER GRAPHICS
      I.3.7 Three-Dimensional Graphics and Realism
          Subjects: Color, shading, shadowing, and texture

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

General Terms:
Algorithms, Measurement, Theory

Keywords:
Image-based relighting, compressive sensing