More Web Proxy on the site http://driver.im/

research-article

Solving trigonometric moment problems for fast transient imaging

Authors:

Christoph Peters,

Jonathan Klein,

Matthias B. Hullin,

Reinhard KleinAuthors Info & Claims

ACM Transactions on Graphics (TOG), Volume 34, Issue 6

Article No.: 220, Pages 1 - 11

https://doi.org/10.1145/2816795.2818103

Published: 02 November 2015 Publication History

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.

Supplementary Material

ZIP File (a220-peters.zip)

Supplemental files.

Download
71.95 MB

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.

Digital Library

[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.

Digital Library

[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.

Digital Library

[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.

Digital Library

[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).

Digital Library

[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.

Digital Library

[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.

Digital Library

[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.

Digital Library

[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.

Digital Library

[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.

Digital Library

[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.

Digital Library

[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.

Digital Library

[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.

Digital Library

[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.

Digital Library

Cited By

Shahandashti PLópez PBrea VGarcía-Lesta DConde M(2024)Simultaneous Multifrequency Demodulation for Single-Shot Multiple-Path ToF ImagingIEEE Transactions on Computational Imaging10.1109/TCI.2023.334875810(54-68)Online publication date: 2024
https://doi.org/10.1109/TCI.2023.3348758
JARABO AFunatomi TOkabe T(2024)Transient ImagingComputational Imaging for Scene Understanding10.1002/9781394284436.ch1(1-27)Online publication date: 19-Apr-2024
https://doi.org/10.1002/9781394284436.ch1
Wang TAo LZheng JSun Z(2023)Reconstructing Depth Images for Time-of-Flight Cameras Based on Second-Order Correlation FunctionsPhotonics10.3390/photonics1011122310:11(1223)Online publication date: 31-Oct-2023
https://doi.org/10.3390/photonics10111223
Show More Cited By

Index Terms

Solving trigonometric moment problems for fast transient imaging
1. Applied computing
  1. Document management and text processing
    1. Document capture
      1. Document scanning
      2. Graphics recognition and interpretation
2. Computing methodologies
  1. Computer graphics
    1. Image manipulation

Recommendations

Low-budget transient imaging using photonic mixer devices

Transient imaging is an exciting a new imaging modality that can be used to understand light propagation in complex environments, and to capture and analyze scene properties such as the shape of hidden objects or the reflectance properties of surfaces.

...
Frequency-Domain Transient Imaging

A transient image is the optical impulse response of a scene, which also visualizes the propagation of light during an ultra-short time interval. In contrast to the previous transient imaging which samples in the time domain using an ultra-fast imaging ...
Fourier Analysis on Transient Imaging with a Multifrequency Time-of-Flight Camera
CVPR '14: Proceedings of the 2014 IEEE Conference on Computer Vision and Pattern Recognition

A transient image is the optical impulse response of a scene which visualizes light propagation during an ultra-short time interval. In this paper we discover that the data captured by a multifrequency time-of-flight (ToF) camera is the Fourier transform ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Graphics

ACM Transactions on Graphics Volume 34, Issue 6

November 2015

944 pages

ISSN:0730-0301

EISSN:1557-7368

DOI:10.1145/2816795

Issue’s Table of Contents

Copyright © 2015 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 02 November 2015

Published in TOG Volume 34, Issue 6

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

Deutsche Forschungsgemeinschaft

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

39
Total Citations
View Citations
424
Total Downloads

Downloads (Last 12 months)28
Downloads (Last 6 weeks)6

Reflects downloads up to 15 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Shahandashti PLópez PBrea VGarcía-Lesta DConde M(2024)Simultaneous Multifrequency Demodulation for Single-Shot Multiple-Path ToF ImagingIEEE Transactions on Computational Imaging10.1109/TCI.2023.334875810(54-68)Online publication date: 2024
https://doi.org/10.1109/TCI.2023.3348758
JARABO AFunatomi TOkabe T(2024)Transient ImagingComputational Imaging for Scene Understanding10.1002/9781394284436.ch1(1-27)Online publication date: 19-Apr-2024
https://doi.org/10.1002/9781394284436.ch1
Wang TAo LZheng JSun Z(2023)Reconstructing Depth Images for Time-of-Flight Cameras Based on Second-Order Correlation FunctionsPhotonics10.3390/photonics1011122310:11(1223)Online publication date: 31-Oct-2023
https://doi.org/10.3390/photonics10111223
Royo DHuang ZLiang YSong BMuñoz AGutierrez DMarco J(2022)Structure-aware parametric representations for time-resolved light transportOptics Letters10.1364/OL.46531647:19(5212)Online publication date: 30-Sep-2022
https://doi.org/10.1364/OL.465316
Rapp TPeters CDachsbacher C(2022)Image-based Visualization of Large Volumetric Data Using MomentsIEEE Transactions on Visualization and Computer Graphics10.1109/TVCG.2022.3165346(1-1)Online publication date: 2022
https://doi.org/10.1109/TVCG.2022.3165346
Pei CZhang ADeng YXu FWu JLi DQiao HFang LDai Q(2021)Dynamic non-line-of-sight imaging system based on the optimization of point spread functionsOptics Express10.1364/OE.43937229:20(32349)Online publication date: 23-Sep-2021
https://doi.org/10.1364/OE.439372
Valle-Pérez GHenter GBeskow JHolzapfel AOudeyer PAlexanderson S(2021)TransflowerACM Transactions on Graphics10.1145/3478513.348057040:6(1-14)Online publication date: 10-Dec-2021
https://dl.acm.org/doi/10.1145/3478513.3480570
Albahar BLu JYang JShu ZShechtman EHuang J(2021)Pose with styleACM Transactions on Graphics10.1145/3478513.348055940:6(1-11)Online publication date: 10-Dec-2021
https://dl.acm.org/doi/10.1145/3478513.3480559
Baek SHeide F(2021)Polarimetric spatio-temporal light transport probingACM Transactions on Graphics10.1145/3478513.348051740:6(1-18)Online publication date: 10-Dec-2021
https://dl.acm.org/doi/10.1145/3478513.3480517
Pillwein SMusialski P(2021)Generalized deployable elastic geodesic gridsACM Transactions on Graphics10.1145/3478513.348051640:6(1-15)Online publication date: 10-Dec-2021
https://dl.acm.org/doi/10.1145/3478513.3480516
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents