Wave-Based Non-Line-of-Sight Imaging Using Fast f–k Migration | SIGGRAPH 2019

We introduce a wave-based image formation model for the problem of non-line-of-sight (NLOS) imaging. Inspired by inverse methods used in seismology, we adapt a frequency-domain method, f-k migration, for solving the inverse NLOS problem.

1. Wave-Based Non-Line-of-Sight Imaging Using Fast f–k Migration David B. Lindell, Gordon Wetzstein , Matthew O’Toole Stanford University Carnegie Mellon University 08/2019

2. detector pulsed laser scanning mirrors occluder hidden object wall

3. 40 cm (2.7 ns) 24 cm (4.3 ns – 2.7 ns)

4. occluder NLOS imaging system hidden scene wall

5. laser detector scanning mirrors

6. resolution: 128 x 128 area: 2 m 2 m  

7. x y t measurements scene photo

8. x y z Dimensions: 2 m x 2 m x 1.5 m scene photo reconstruction

9. contributions fast wave-based image formation model for NLOS imaging complex surface reflectances , more robust to noise new hardware prototype: room-sized scenes, interactive scanning

10. NLOS imaging for autonomous cars

11. LIDAR (light detection and ranging) Velodyne VLS-128 NLOS imaging for autonomous cars

12. NLOS image formation and related work hardware prototype outline wave-based model

13. picosecond laser SPAD sensor * timestamp of photon event Time-to-Digital Converter (TDC) scene Num. Detections Time of Flight single-photon avalanche diodes (SPADs)

14. sensor light source occluder histogram timestamp (nanoseconds) photons detected direct reflection indirect reflection direct reflection indirect reflection

15. wall hidden object laser detector histogram timestamp (nanoseconds) non-confocal sampling

16. wall hidden object laser and detector focus on this point confocal sampling histogram timestamp (nanoseconds) APJarvis [CC BY-SA 4.0] lasers and detectors illuminate and image same points

17. wall hidden object confocal sampling same path to the object and back

18. wall hidden object confocal sampling simplified NLOS mathematical model enables efficient NLOS reconstruction equivalent to one-way propagation at half-speed

19. object detector position O’Toole et al. 2018

20. sensor light source occluder histogram timestamp (nanoseconds) photons detected

21. sensor light source occluder histogram timestamp (nanoseconds) photons detected imaging area

22. sensor light source occluder imaging area 3D measurements

23. NLOS image formation model: measurements unknown volume transport matrix Backprojection [ Velten 12, Buttafava 15] Flops: Memory: Runtime: Approx. 10 min. Iterative Inversion [Gupta 12, Wu 12, Heide 13] Flops: Memory: per iter . Runtime: > 1 hour Problem: extremely large in practice for n=100, has 1 trillion elements for n=1000, sparse needs petabytes of memory even matrix-free is computationally intractable

24. NLOS image formation model: measurements unknown volume transport matrix Backprojection [ Velten 12, Buttafava 15] Flops: Memory: Runtime: Approx. 10 min. Iterative Inversion [Gupta 12, Wu 12, Heide 13] Flops: Memory: per iter . Runtime: > 1 hour Computationally Intractable

25. NLOS image formation model: measurements unknown volume transport matrix Backprojection [ Velten 12, Buttafava 15] Flops: Memory: Runtime: Approx. 10 min. Iterative Inversion [Gupta 12, Wu 12, Heide 13] Flops: Memory: per iter . Runtime: > 1 hour 3D Deconvolution (with Light-Cone Transform) [O’Toole et al. 2018] Flops: Memory: Runtime: < 1 second measurements unknown volume blur kernel Confocal scanning and Light-Cone Transform: Computationally Intractable

26. NLOS image formation model: measurements unknown volume transport matrix Backprojection [ Velten 12, Buttafava 15] Flops: Memory: Runtime: Approx. 10 min. Iterative Inversion [Gupta 12, Wu 12, Heide 13] Flops: Memory: per iter . Runtime: > 1 hour 3D Deconvolution (with Light-Cone Transform) [O’Toole et al. 2018] Flops: Memory: Runtime: < 1 second measurements unknown volume blur kernel Confocal scanning and Light-Cone Transform: Computationally Intractable Limited Scenes (only diffuse or retroreflective objects)

27. NLOS image formation and related work hardware prototype outline wave-based model

28. Shockwave Receiver Earth’s surface Underground Structure seismic imaging

29. NLOS imaging

30. z x confocal measurements x wavefield wall (z = 0) hidden object t image formation model

31. z x x t general solution (time reversal) wall (z = 0) hidden object wavefield confocal measurements

32. general solution (time reversal) 1. approximate wave equation with finite differences 2. solve for previous timestep 3. repeatedly update at all grid cells finite-difference time-domain method

33. general solution (time reversal) 1. approximate wave equation with finite differences 2. solve for previous timestep 3. repeatedly update at all grid cells finite-difference time-domain method Slow to get t=0 at high-resolution!

34. phasor fields [Liu et al. 19] convolve captured measurements in time with a virtual wave function (e.g. wavelet packet) reverse-propagate the resulting wavefield using RSD integral or Fresnel propagation can directly propagate to arbitrary “t” uses propagation integral or backprojection to  

35. z x x t frequency–wavenumber ( f–k ) Migration wall (z = 0) hidden object wavefield confocal measurements FLOPS:  

36. x y t Captured Measurements

37. x y t

38. f-k Migration Measurements (z=0) Spectrum Hidden Volume (t=0) Interpolated Spectrum Resample

39. f-k Migration Express wavefield as function of measurement spectrum (plane wave decomposition) wavefield Fourier transform of measurements Set t=0 to get migrated solution Almost an inverse Fourier Transform!

40. f-k Migration Set t=0 to get migrated solution Almost an inverse Fourier Transform! Use dispersion relation 1 to perform substitution of variables 1 Georgi, Howard.  The physics of waves . Englewood Cliffs, NJ: Prentice Hall, 1993.

41. Use dispersion relation 1 to perform substitution of variables

42. Use dispersion relation 1 to perform substitution of variables

43. Use dispersion relation 1 to perform substitution of variables

44. Use dispersion relation 1 to perform substitution of variables

45. Use dispersion relation 1 to perform substitution of variables

46. Use dispersion relation 1 to perform substitution of variables The migrated solution is an inverse Fourier Transform! Resample

47. f-k Migration x y z Dimensions: 2 x 2 m Exposure: 180 min Reconstruction time: ~1 min (CPU)

48. Reconstruction Comparison

49. NLOS image formation and related work hardware prototype outline wave-based model

50. hardware prototype

51. hardware prototype

52. Hardware Prototype

53. real-time scanning Framerate: 4 Hz Resolution: 32 x 32 Dimensions: 2 m x 2 m x 2 m Reconstruction time: ~1 s per frame

54. noise sensitivity LCT f-k Migration 15 sec 1 min 2 min 15 min 2 m x y z