“Wave-based non-line-of-sight imaging using fast f-k migration” by Lindell, Wetzstein and O’Toole

  • ©David B. Lindell, Gordon Wetzstein, and Matthew O’Toole



Session Title:

    Computational Imaging


    Wave-based non-line-of-sight imaging using fast f-k migration



    Imaging objects outside a camera’s direct line of sight has important applications in robotic vision, remote sensing, and many other domains. Time-of-flight-based non-line-of-sight (NLOS) imaging systems have recently demonstrated impressive results, but several challenges remain. Image formation and inversion models have been slow or limited by the types of hidden surfaces that can be imaged. Moreover, non-planar sampling surfaces and non-confocal scanning methods have not been supported by efficient NLOS algorithms. With this work, we introduce a wave-based image formation model for the problem of NLOS imaging. Inspired by inverse methods used in seismology, we adapt a frequency-domain method, f-k migration, for solving the inverse NLOS problem. Unlike existing NLOS algorithms, f-k migration is both fast and memory efficient, it is robust to specular and other complex reflectance properties, and we show how it can be used with non-confocally scanned measurements as well as for non-planar sampling surfaces. f-k migration is more robust to measurement noise than alternative methods, generally produces better quality reconstructions, and is easy to implement. We experimentally validate our algorithms with a new NLOS imaging system that records room-sized scenes outdoors under indirect sunlight, and scans persons wearing retroreflective clothing at interactive rates.


    1. Fadel Adib, Chen-Yu Hsu, Hongzi Mao, Dina Katabi, and Frédo Durand. 2015. Capturing the human figure through a wall. ACM Trans. Graph. 34, 6 (2015), 219. Google ScholarDigital Library
    2. Fadel Adib and Dina Katabi. 2013. See through walls with WiFi!. In ACM SIGCOMM. Google ScholarDigital Library
    3. Yoann Altmann, Stephen McLaughlin, Miles J. Padgett, Vivek K. Goyal, Alfred O. Hero, and Daniele Faccio. 2018. Quantum-inspired computational imaging. Science 361, 6403 (2018).Google Scholar
    4. Victor Arellano, Diego Gutierrez, and Adrian Jarabo. 2017. Fast back-projection for non-line of sight reconstruction. Optics Express 25, 10 (2017), 11574–11583.Google ScholarCross Ref
    5. Manel Baradad, Vickie Ye, Adam B. Yedidia, Frédo Durand, William T Freeman, Gregory W Wornell, and Antonio Torralba. 2018. Inferring Light Fields From Shadows. In Proc. CVPR.Google ScholarCross Ref
    6. Jacopo Bertolotti, Elbert G. van Putten, Christian Blum, Ad Lagendijk, Willem L. Vos, and Allard P. Mosk. 2012. Non-invasive imaging through opaque scattering layers. Nature 491, 7423 (2012), 232.Google Scholar
    7. Jeremy Boger-Lombard and Ori Katz. 2018. Non line-of-sight localization by passive optical time-of-flight. arXiv preprint arXiv:1808.01000 (2018).Google Scholar
    8. Katherine L. Bouman, Vickie Ye, Adam B. Yedidia, Frédo Durand, Gregory W Wornell, Antonio Torralba, and William T Freeman. 2017. Turning corners into cameras: Principles and methods. In Proc. ICCV.Google ScholarCross Ref
    9. Mauro Buttafava, Jessica Zeman, Alberto Tosi, Kevin Eliceiri, and Andreas Velten. 2015. Non-line-of-sight imaging using a time-gated single photon avalanche diode. Optics Express 23, 16 (2015), 20997–21011.Google ScholarCross Ref
    10. Ciro Cafforio, Claudio Prati, and Fabio Rocca. 1991. SAR data focusing using seismic migration techniques. IEEE Trans. Aerosp. Electron. Syst. 27, 2 (1991), 194–207.Google ScholarCross Ref
    11. Hayden J. Callow. 2003. Signal processing for synthetic aperture sonar image enhancement. Ph.D. Dissertation. University of Canterbury.Google Scholar
    12. Susan Chan, Ryan E Warburton, Genevieve Gariepy, Jonathan Leach, and Daniele Faccio. 2017. Non-line-of-sight tracking of people at long range. Optics Express 25, 9 (2017), 10109–10117.Google ScholarCross Ref
    13. Philippe De Heering. 1984. Alternate schemes in synthetic aperture sonar processing. IEEE J. Ocean. Eng. 9, 4 (1984), 277–280.Google ScholarCross Ref
    14. James R Fienup. 1982. Phase retrieval algorithms: a comparison. Applied optics 21, 15 (1982), 2758–2769.Google Scholar
    15. Kae Yeet Foo. 2004. Incoherent processing of synthetic aperture sonar. Ph.D. Dissertation. University of Birmingham.Google Scholar
    16. Damien Garcia, Louis Le Tarnec, Stéphan Muth, Emmanuel Montagnon, Jonathan Porée, and Guy Cloutier. 2013. Stolt’s fk migration for plane wave ultrasound imaging. IEEE Trans. Ultrason., Ferroelectr., Freq. Control 60, 9 (2013), 1853–1867.Google ScholarCross Ref
    17. Genevieve Gariepy, Francesco Tonolini, Robert Henderson, Jonathan Leach, and Daniele Faccio. 2016. Detection and tracking of moving objects hidden from view. Nature Photonics 10, 1 (2016), 23–26.Google ScholarCross Ref
    18. Ioannis Gkioulekas, Anat Levin, Frédo Durand, and Todd Zickler. 2015. Micron-scale light transport decomposition using interferometry. ACM Trans. Graph. 34, 4 (2015), 37. Google ScholarDigital Library
    19. Otkrist Gupta, Thomas Willwacher, Andreas Velten, Ashok Veeraraghavan, and Ramesh Raskar. 2012. Reconstruction of hidden 3D shapes using diffuse reflections. Optics Express 20, 17 (2012), 19096–19108.Google ScholarCross Ref
    20. Felix Heide, Matthew O’Toole, Kai Zhang, David B. Lindell, Steven Diamond, and Gordon Wetzstein. 2019. Non-line-of-sight imaging with partial occluders and surface normals. ACM Trans. Graph. (2019). Google ScholarDigital Library
    21. Felix Heide, Lei Xiao, Wolfgang Heidrich, and Matthias B. Hullin. 2014. Diffuse mirrors: 3D reconstruction from diffuse indirect illumination using inexpensive time-of-flight sensors. In Proc. CVPR. Google ScholarDigital Library
    22. Julian Iseringhausen and Matthias B. Hullin. 2018. Non-line-of-sight reconstruction using efficient transient rendering. arXiv preprint arXiv:1809.08044 (2018).Google Scholar
    23. Wenzel Jakob and Steve Marschner. 2012. Manifold exploration: a Markov Chain Monte Carlo technique for rendering scenes with difficult specular transport. ACM Trans. Graph. 31, 4 (2012), 58. Google ScholarDigital Library
    24. Adrian Jarabo, Julio Marco, Adolfo Munoz, Raul Buisan, Wojciech Jarosz, and Diego Gutierrez. 2014. A Framework for Transient Rendering. ACM Trans. Graph. 33, 6 (2014). Google ScholarDigital Library
    25. Adrian Jarabo, Belen Masia, Julio Marco, and Diego Gutierrez. 2017. Recent advances in transient imaging: A computer graphics and vision perspective. Visual Informatics 1, 1 (2017), 65–79.Google ScholarCross Ref
    26. Adrian Jarabo, Belen Masia, Andreas Velten, Christopher Barsi, Ramesh Raskar, and Diego Gutierrez. 2015. Relativistic effects for time-resolved light transport. In Computer Graphics Forum, Vol. 34. Google ScholarDigital Library
    27. Achuta Kadambi, Hang Zhao, Boxin Shi, and Ramesh Raskar. 2016. Occluded imaging with time-of-flight sensors. ACM Trans. Graph. 35, 2 (2016), 15. Google ScholarDigital Library
    28. Ori Katz, Pierre Heidmann, Mathias Fink, and Sylvain Gigan. 2014. Non-invasive single-shot imaging through scattering layers and around corners via speckle correlations. Nature Photonics 8, 10 (2014), 784.Google ScholarCross Ref
    29. Ahmed Kirmani, Tyler Hutchison, James Davis, and Ramesh Raskar. 2009. Looking around the corner using transient imaging. In Proc. ICCV.Google ScholarCross Ref
    30. Jonathan Klein, Martin Laurenzis, Dominik L. Michels, and Matthias B. Hullin. 2018. A quantitative platform for non-line-of-sight imaging problems. In Proc. BMVC.Google Scholar
    31. Jonathan Klein, Christoph Peters, Jaime Martín, Martin Laurenzis, and Matthias B. Hullin. 2016. Tracking objects outside the line of sight using 2D intensity images. Scientific Reports 6 (2016), 32491.Google ScholarCross Ref
    32. Marco La Manna, Fiona Kine, Eric Breitbach, Jonathan Jackson, Talha Sultan, and Andreas Velten. 2018. Error backprojection algorithms for non-line-of-sight imaging. IEEE Trans. Pattern Anal. Mach. Intell. (2018).Google Scholar
    33. David B Lindell, Matthew O’Toole, and Gordon Wetzstein. 2018. Towards transient imaging at interactive rates with single-photon detectors. In Proc. ICCP.Google ScholarCross Ref
    34. David B. Lindell, Gordon Wetzstein, and Vladlen Koltun. 2019. Acoustic non-line-of-sight imaging. In Proc. CVPR.Google ScholarCross Ref
    35. Xiaochun Liu, Sebastian Bauer, and Andreas Velten. 2019. Analysis of feature visibility in non-line-of-sight measurements. In Proc. CVPR.Google ScholarCross Ref
    36. Xiaochun Liu, Ibón Guillén, Marco La Manna, Ji Hyun Nam, Syed Azer Reza, Toan Huu Le, Diego Gutierrez, Adrian Jarabo, and Andreas Velten. 2018. Virtual wave optics for non-line-of-sight imaging. arXiv preprint arXiv:1810.07535 (2018).Google Scholar
    37. Julio Marco, Ibón Guillén, Wojciech Jarosz, Diego Gutierrez, and Adrian Jarabo. 2019. Progressive transient photon beams. Computer Graphics Forum 38, 1 (2019).Google Scholar
    38. Gary F. Margrave and Michael P. Lamoureux. 2018. Numerical Methods of Exploration Seismology: With Algorithms in MATLAB®. Cambridge University Press.Google Scholar
    39. Nikhil Naik, Shuang Zhao, Andreas Velten, Ramesh Raskar, and Kavita Bala. 2011. Single view reflectance capture using multiplexed scattering and time-of-flight imaging. 30, 6 (2011), 171. Google ScholarDigital Library
    40. Stephen J Norton. 1980. Reconstruction of a reflectivity field from line integrals over circular paths. The Journal of the Acoustical Society of America 67, 3 (1980), 853–863.Google ScholarCross Ref
    41. Matthew O’Toole, Felix Heide, David B. Lindell, Kai Zang, Steven Diamond, and Gordon Wetzstein. 2017. Reconstructing transient images from single-photon sensors. In Proc. CVPR.Google ScholarCross Ref
    42. Matthew O’Toole, David B. Lindell, and Gordon Wetzstein. 2018a. Confocal non-line-of-sight imaging based on the light-cone transform. Nature 555, 7696 (2018), 338.Google Scholar
    43. Matthew O’Toole, David B. Lindell, and Gordon Wetzstein. 2018b. Real-time non-line-of-sight imaging. In ACM SIGGRAPH Emerging Technologies. Google ScholarDigital Library
    44. Adithya Kumar Pediredla, Mauro Buttafava, Alberto Tosi, Oliver Cossairt, and Ashok Veeraraghavan. 2017a. Reconstructing rooms using photon echoes: A plane based model and reconstruction algorithm for looking around the corner. In Proc. ICCP.Google ScholarCross Ref
    45. Adithya Kumar Pediredla, Nathan Matsuda, Oliver Cossairt, and Ashok Veeraraghavan. 2017b. Linear systems approach to identifying performance bounds in indirect imaging. In Proc. ICASSP.Google ScholarCross Ref
    46. Eric F Pettersen, Thomas D Goddard, Conrad C Huang, Gregory S Couch, Daniel M Greenblatt, Elaine C Meng, and Thomas E Ferrin. 2004. UCSF Chimera—a visualization system for exploratory research and analysis. Journal of computational chemistry 25, 13 (2004), 1605–1612.Google ScholarCross Ref
    47. Matt Pharr, Wenzel Jakob, and Greg Humphreys. 2016. Physically based rendering: From theory to implementation. Morgan Kaufmann. Google ScholarDigital Library
    48. Albert Redo-Sanchez, Barmak Heshmat, Alireza Aghasi, Salman Naqvi, Mingjie Zhang, Justin Romberg, and Ramesh Raskar. 2016. Terahertz time-gated spectral imaging for content extraction through layered structures. Nature communications 7 (2016), 12665.Google Scholar
    49. Syed Azer Reza, Marco La Manna, and Andreas Velten. 2018a. Imaging with phasor fields for non-line-of sight applications. In Computational Optical Sensing and Imaging.Google Scholar
    50. Syed Azer Reza, Marco La Manna, and Andreas Velten. 2018b. A physical light transport model for non-line-of-sight imaging applications. arXiv preprint arXiv:1802.01823 (2018).Google Scholar
    51. Charles Saunders, John Murray-Bruce, and Vivek K Goyal. 2019. Computational periscopy with an ordinary digital camera. Nature 565, 7740 (2019), 472.Google Scholar
    52. Robert W. Sheriff. 1992. Synthetic aperture beamforming with automatic phase compensation for high frequency sonars. In Proc. AUV.Google ScholarCross Ref
    53. Brandon M. Smith, Matthew O’Toole, and Mohit Gupta. 2018. Tracking multiple objects outside the line of sight using speckle imaging. In Proc. CVPR.Google ScholarCross Ref
    54. Robert H. Stolt. 1978. Migration by Fourier transform. Geophysics 43, 1 (1978), 23–48.Google ScholarCross Ref
    55. Christos Thrampoulidis, Gal Shulkind, Feihu Xu, William T Freeman, Jeffrey H Shapiro, Antonio Torralba, Franco NC Wong, and Gregory W Wornell. 2018. Exploiting occlusion in non-line-of-sight active imaging. IEEE Trans. Comput. Imag. 4, 3 (2018), 419–431.Google ScholarCross Ref
    56. Antonio Torralba and William T. Freeman. 2012. Accidental pinhole and pinspeck cameras: Revealing the scene outside the picture. In Proc. CVPR. Google ScholarDigital Library
    57. Chia-Yin Tsai, Kiriakos N. Kutulakos, Srinivasa G. Narasimhan, and Aswin C. Sankaranarayanan. 2017. The geometry of first-returning photons for non-line-of-sight imaging. In Proc. CVPR.Google Scholar
    58. Chia-Yin Tsai, Aswin Sankaranarayanan, and Ioannis Gkioulekas. 2019. Beyond volumetric albedo—A surface optimization framework for non-line-of-sight imaging. In Proc. CVPR.Google ScholarCross Ref
    59. Andreas Velten, Thomas Willwacher, Otkrist Gupta, Ashok Veeraraghavan, Moungi G. Bawendi, and Ramesh Raskar. 2012. Recovering three-dimensional shape around a corner using ultrafast time-of-flight imaging. Nature communications 3 (2012), 745.Google Scholar
    60. Andreas Velten, Di Wu, Adrian Jarabo, Belen Masia, Christopher Barsi, Chinmaya Joshi, Everett Lawson, Moungi Bawendi, Diego Gutierrez, and Ramesh Raskar. 2013. Femto-photography: capturing and visualizing the propagation of light. ACM Trans. Graph. 32, 4 (2013), 44. Google ScholarDigital Library
    61. Shumian Xin, Sotiris Nousias, Kyros Kutulakos, Aswin Sankaranarayanan, Srinivasa Narasimhan, and Ioannis Gkioulekas. 2019. A theory of Fermat paths for non-line-of-sight shape reconstruction. In Proc. CVPR.Google ScholarCross Ref
    62. Feihu Xu, Gal Shulkind, Christos Thrampoulidis, Jeffrey H Shapiro, Antonio Torralba, Franco NC Wong, and Gregory W Wornell. 2018. Revealing hidden scenes by photon-efficient occlusion-based opportunistic active imaging. Optics express 26, 8 (2018), 9945–9962.Google Scholar
    63. Öz Yilmaz. 2001. Seismic data analysis: Processing, inversion, and interpretation of seismic data. Society of Exploration Geophysicists.Google Scholar
    64. Mingmin Zhao, Tianhong Li, Mohammad Abu Alsheikh, Yonglong Tian, Hang Zhao, Antonio Torralba, and Dina Katabi. 2018. Through-wall human pose estimation using radio signals. In Proc. CVPR.Google ScholarCross Ref

ACM Digital Library Publication:

Overview Page: