“Solving trigonometric moment problems for fast transient imaging”
Conference:
Type(s):
Title:
- Solving trigonometric moment problems for fast transient imaging
Session/Category Title: Tracking and Transients
Presenter(s)/Author(s):
Abstract:
Transient images help to analyze light transport in scenes. Besides two spatial dimensions, they are resolved in time of flight. Cost-efficient approaches for their capture use amplitude modulated continuous wave lidar systems but typically take more than a minute of capture time. We propose new techniques for measurement and reconstruction of transient images, which drastically reduce this capture time. To this end, we pose the problem of reconstruction as a trigonometric moment problem. A vast body of mathematical literature provides powerful solutions to such problems. In particular, the maximum entropy spectral estimate and the Pisarenko estimate provide two closed-form solutions for reconstruction using continuous densities or sparse distributions, respectively. Both methods can separate m distinct returns using measurements at m modulation frequencies. For m = 3 our experiments with measured data confirm this. Our GPU-accelerated implementation can reconstruct more than 100000 frames of a transient image per second. Additionally, we propose modifications of the capture routine to achieve the required sinusoidal modulation without increasing the capture time. This allows us to capture up to 18.6 transient images per second, leading to transient video. An important byproduct is a method for removal of multipath interference in range imaging.
References:
1. Ammar, G. S., and Gragg, W. B. 1988. Superfast solution of real positive definite Toeplitz systems. SIAM Journal on Matrix Analysis and Applications 9, 1, 61–76.
2. Bhandari, A., Feigin, M., Izadi, S., Rhemann, C., Schmidt, M., and Raskar, R. 2014. Resolving multipath interference in Kinect: An inverse problem approach. In SENSORS, 2014 IEEE, 614–617.
3. Bhandari, A., Kadambi, A., Whyte, R., Barsi, C., Feigin, M., Dorrington, A., and Raskar, R. 2014. Resolving multipath interference in time-of-flight imaging via modulation frequency diversity and sparse regularization. Opt. Lett. 39, 6 (Mar), 1705–1708.
4. Burg, J. P. 1975. Maximum Entropy Spectral Analysis. Ph.d. dissertation, Stanford University, Department of Geophysics.
5. Cybenko, G., and Loan, C. V. 1986. Computing the minimum eigenvalue of a symmetric positive definite Toeplitz matrix. SIAM Journal on Scientific and Statistical Computing 7, 1, 123–131.
6. Dorrington, A. A., Godbaz, J. P., Cree, M. J., Payne, A. D., and Streeter, L. V. 2011. Separating true range measurements from multi-path and scattering interference in commercial range cameras. Proc. SPIE 7864, 786404-1-786404-10.
7. Freedman, D., Smolin, Y., Krupka, E., Leichter, I., and Schmidt, M. 2014. SRA: Fast removal of general multipath for ToF sensors. In Computer Vision – ECCV 2014, vol. 8689 of Lecture Notes in Computer Science. Springer International Publishing, 234–249.
8. Fuchs, S. 2010. Multipath interference compensation in time-of-flight camera images. In Pattern Recognition (ICPR), 2010 20th International Conference on, 3583–3586.
9. Gao, L., Liang, J., Li, C., and Wang, L. V. 2014. Single-shot compressed ultrafast photography at one hundred billion frames per second. Nature 516 (April).
10. Gkioulekas, I., Levin, A., Durand, F., and Zickler, T. 2015. Micron-scale light transport decomposition using interferometry. ACM Trans. Graph. (Proc. SIGGRAPH 2015) 34, 4 (July), 37:1–37:14.
11. Godbaz, J. P., Cree, M. J., and Dorrington, A. A. 2012. Closed-form inverses for the mixed pixel/multipath interference problem in AMCW lidar. Proc. SPIE 8296, 829618-1-829618-15.
12. Gupta, M., Nayar, S. K., Hullin, M. B., and Martín, J. 2015. Phasor imaging: A generalization of correlation-based time-of-flight imaging. ACM Trans. Graph. (to appear).
13. Heide, F., Hullin, M. B., Gregson, J., and Heidrich, W. 2013. Low-budget transient imaging using photonic mixer devices. ACM Trans. Graph. (Proc. SIGGRAPH 2013) 32, 4 (July), 45:1–45:10.
14. Heide, F., Xiao, L., Kolb, A., Hullin, M. B., and Heidrich, W. 2014. Imaging in scattering media using correlation image sensors and sparse convolutional coding. Opt. Express 22, 21 (Oct), 26338–26350.
15. Jarabo, A., Marco, J., Muñoz, A., Buisan, R., Jarosz, W., and Gutierrez, D. 2014. A framework for transient rendering. ACM Trans. Graph. (Proc. Siggraph Asia 2014) 33, 6 (Nov.), 177:1–177:10.
16. Jimenez, D., Pizarro, D., Mazo, M., and Palazuelos, S. 2012. Modelling and correction of multipath interference in time of flight cameras. In Computer Vision and Pattern Recognition (CVPR), 2012 IEEE Conference on, 893–900.
17. Kadambi, A., Whyte, R., Bhandari, A., Streeter, L., Barsi, C., Dorrington, A., and Raskar, R. 2013. Coded time of flight cameras: Sparse deconvolution to address multipath interference and recover time profiles. ACM Trans. Graph. (Proc. SIGGRAPH Asia 2013) 32, 6 (Nov.), 167:1–167:10.
18. Kadambi, A., Taamazyan, V., Jayasuriya, S., and Raskar, R. 2015. Frequency domain ToF: encoding object depth in modulation frequency. CoRR abs/1503.01804.
19. Karlin, S., and Studden, W. J. 1966. Tchebycheff systems: with applications in analysis and statistics. Pure and applied mathematics. Interscience Publishers.
20. Karlsson, J., and Georgiou, T. 2013. Uncertainty bounds for spectral estimation. Automatic Control, IEEE Transactions on 58, 7 (July), 1659–1673.
21. Kirmani, A., Benedetti, A., and Chou, P. 2013. SPUMIC: Simultaneous phase unwrapping and multipath interference cancellation in time-of-flight cameras using spectral methods. In Multimedia and Expo (ICME), 2013 IEEE International Conference on, 1–6.
22. Krein, M. G., and Nudel’man, A. A. 1977. The Markov Moment Problem and Extremal Problems, vol. 50 of Translations of Mathematical Monographs. American Mathematical Society.
23. Lin, J., Liu, Y., Hullin, M. B., and Dai, Q. 2014. Fourier analysis on transient imaging with a multifrequency time-of-flight camera. In Computer Vision and Pattern Recognition (CVPR), 2014 IEEE Conference on, 3230–3237.
24. Naik, N., Zhao, S., Velten, A., Raskar, R., and Bala, K. 2011. Single view reflectance capture using multiplexed scattering and time-of-flight imaging. ACM Trans. Graph. (Proc. SIGGRAPH Asia 2011) 30, 6 (Dec.), 171:1–171:10.
25. Payne, A. D., Dorrington, A. A., Cree, M. J., and Carnegie, D. A. 2010. Improved measurement linearity and precision for AMCW time-of-flight range imaging cameras. Appl. Opt. 49, 23 (Aug), 4392–4403.
26. Qiao, H., Lin, J., Liu, Y., Hullin, M. B., and Dai, Q. 2015. Resolving transient time profile in ToF imaging via log-sum sparse regularization. Opt. Lett. 40, 6 (Mar), 918–921.
27. Velten, A., Lawson, E., Bardagjy, A., Bawendi, M., and Raskar, R. 2011. Slow art with a trillion frames per second camera. In ACM SIGGRAPH 2011 Posters, 13:1–13:1.
28. Velten, A., Willwacher, T., Gupta, O., Veeraraghavan, A., Bawendi, M. G., and Raskar, R. 2012. Recovering three-dimensional shape around a corner using ultrafast time-of-flight imaging. Nature Communications 3 (March).
29. Velten, A., Wu, D., Jarabo, A., Masia, B., Barsi, C., Joshi, C., Lawson, E., Bawendi, M., Gutierrez, D., and Raskar, R. 2013. Femto-photography: Capturing and visualizing the propagation of light. ACM Trans. Graph. (Proc. SIGGRAPH 2013) 32, 4 (July), 44:1–44:8.
30. Wu, D., Velten, A., O’Toole, M., Masia, B., Agrawal, A., Dai, Q., and Raskar, R. 2014. Decomposing global light transport using time of flight imaging. International Journal of Computer Vision 107, 2, 123–138.
