Source-linked AI summary
Fast Back-Projection for Non-Line of Sight Reconstruction
Victor Arellano, Diego Gutierrez, Adrian Jarabo
TL;DR
NLOS reconstruction uses time-resolved measurements of multiply scattered light to recover occluded objects, but its computation remains a bottleneck. This paper voxelizes ellipsoid constraints to reduce back-projection complexity; it reports speed-ups of up to three orders of magnitude alongside low error and added cost.
Problem
NLOS reconstruction from multiply scattered time-resolved light remains computationally burdensome, with existing optimization and back-projection approaches taking several hours.
Source: §1 · p. 2Method
The method constructs a hidden-geometry probability map from intersecting measurement-defined ellipsoids and voxelizes them for efficient GPU implementation.
Source: §1 · p. 2Results
Takeaways & Limitations
The method targets the reconstruction computation identified as limiting the applicability of NLOS imaging.
Source: §1 · p. 2The probability model assumes Lambertian surfaces, ignores albedo, and attributes sensor light to third-bounce reflection, which may cause errors where higher-order scattering dominates, such as concavities.
Source: §4.2 · p. 8
Abstract
from arXiv · showhide
Recent works have demonstrated non-line of sight (NLOS) reconstruction by using the time-resolved signal frommultiply scattered light. These works combine ultrafast imaging systems with computation, which back-projects the recorded space-time signal to build a probabilistic map of the hidden geometry. Unfortunately, this computation is slow, becoming a bottleneck as the imaging technology improves. In this work, we propose a new back-projection technique for NLOS reconstruction, which is up to a thousand times faster than previous work, with almost no quality loss. We base on the observation that the hidden geometry probability map can be built as the intersection of the three-bounce space-time manifolds defined by the light illuminating the hidden geometry and the visible point receiving the scattered light from such hidden geometry. This allows us to pose the reconstruction of the hidden geometry as the voxelization of these space-time manifolds, which has lower theoretic complexity and is easily implementable in the GPU. We demonstrate the efficiency and quality of our technique compared against previous methods in both captured and synthetic data
1. Introduction
Time-resolved imaging extends geometry reconstruction to occluded objects by analyzing multiply scattered light, but reconstruction computation remains a bottleneck. The paper proposes ellipsoid-based back-projection that reduces redundancy and reports substantial speed and quality benefits.
1. Introduction
- Time-resolved imaging hardware ranges from femtosecond-laser and streak-camera systems to more portable options that sacrifice time resolution.The broader application is recovering depth from photon arrival times and reconstructing occluded objects from multiply scattered light.Source: §1 · p. 2
- Existing NLOS reconstruction remains a computational bottleneck, with approaches based on optimization or back-projection taking several hours.Back-projection avoids non-convex optimization and has lower memory cost and noise robustness, but scales poorly with voxel resolution.Source: §1 · p. 2
- The method builds a hidden-geometry probability map by intersecting measurement-defined ellipsoids, reducing theoretical complexity and enabling GPU-suitable voxelization.Each ellipsoid is defined by a light source and observed point; the formulation avoids redundancy in the measurements.Source: §1 · p. 2, Figure 1 · p. 3
- Large datasets can be processed in seconds with a minimum increase in error, while higher-resolution reconstructions add negligible cost.The method is evaluated on synthetic and captured data against existing approaches.Source: §1 · p. 2
2. Back-projection for NLOS reconstruction
The section describes how time-resolved measurements relate hidden points to observed light, then explains how back-projection uses multiple measurements to estimate hidden geometry. Its probability-map computation is costly in the straightforward voxel-by-voxel formulation.
2. Back-projection for NLOS reconstruction
- The captured signal is indexed by pixel and time, and the model relates it to hidden-point radiance, path delay, geometric attenuation, and visibility.The formulation assumes third-bounce reflection and illumination from the virtual point light; source and camera flight-time offsets do not change ellipsoid shape but are included in calculations.Source: §2 · pp. 3–4
2.1. NLOS by back-projection
- A single space-time measurement leaves infinitely many candidate hidden points, so back-projection combines multiple measurements to recover a discrete scene.The section introduces a Lambertian-reflectance probability model for whether a point belongs to the occluded geometry.Source: §2.1 · p. 4
- The probability map corrects the measured signal by estimated path attenuation and is later used with a voxel-space operator, typically a 3D Laplacian filter, to reconstruct geometry.The model uses a delta function centered at zero.Source: §2.1 · p. 4
- The straightforward method evaluates the probability for every voxel at cost O(P̄ × S × X̄), while the proposed formulation reduces theoretical complexity and supports efficient commodity-hardware implementation.The stated cost grows linearly with pixel count, light positions, and voxel count.Source: §2.1 · p. 4
3. Our method
The method accumulates voxel intersections with light-path ellipsoids, then recasts reconstruction as GPU-friendly voxelization; its mannequin comparison reports two orders of magnitude faster reconstruction at similar quality.
3. Our method
- The method treats each light-path ellipsoid as evidence for hidden geometry, assigning higher probability where more ellipsoids intersect.It poses the probability map as ellipsoid intersections with a voxelized scene.Source: §3 · p. 4
- The voxel–ellipsoid test omits geometric attenuation to avoid possible numerical singularities and overflow, without affecting the final result after Laplacian filtering.The authors report that the geometry term has almost no effect between neighboring voxels.Source: §3 · p. 4
- Projecting captured data into the voxelized scene yields theoretical complexity O(P × S × T), independent of voxelization resolution and lower in practice for sparse signals.The formulation is equivalent to voxelizing ellipsoids defined by pixel, lighting position, and time tuples.Source: §3 · p. 5
3.1. Fast back-projection
- Hardware voxelization requires many ellipsoids to be created and tessellated, so the method uses instanced rendering and adaptively selected tessellation levels.The tessellation error threshold is set to the voxel size.Source: §3.1 · p. 5
3.2. Cost analysis
- Setting the tessellation threshold so each triangle covers about one voxel gives the best reported quality-cost trade-off.Ellipsoid voxelization cost depends on the number of triangles and the voxels each triangle covers.Source: §3.2 · p. 5
- The mannequin reconstruction is two orders of magnitude faster with similar quality than traditional back-projection.The figure compares traditional back-projection on the left with the proposed method on the right.Source: Figure 2 · p. 6
4. Results
Across captured and synthetic evaluations, the method reconstructs scenes faster than traditional back-projection with comparable quality. The analysis also identifies tessellation, input-resolution, and signal-sparsity limits.
4. Results
- 96.7× speed-up reduced the captured mannequin reconstruction to under 20 seconds, versus more than half an hour for traditional back-projection.The reconstruction used 59 measurements and a 162^3-voxel grid.Source: §4 · p. 6
- The SPAD scene took 1.8 s to reconstruct, versus 14.8 s for traditional back-projection, despite high noise and large temporal resolution.The figure reports almost identical reconstruction quality; its main images use filtered data, while insets show unfiltered data.Source: §4 · p. 6, Figure 3 · p. 7
4.1. Analysis
- Across synthetic parameter sweeps, speed-ups reached 10,000× at large voxel resolutions, while error remained comparable to traditional back-projection.At 10^4 temporal frames, the method remained two orders of magnitude faster, although its cost scales linearly with frame count.Source: §4.1 · p. 7, Figure 5 · p. 8
- Triangle size near a voxel is a cost-quality sweet spot: finer tessellation eventually stops improving resolution-bounded error while increasing runtime.The number of triangles controls ellipsoid tessellation during voxelization and affects both cost and reconstruction quality.Source: §4.1 · pp. 7–8, Figure 7 · p. 9
4.2. Discussion and limitations
- Dense, non-sparse signals are the worst case, particularly with participating media; at the stated resolution, runtime was 12.51 s versus 475.78 s.The comparison is for 128^2 input pixels, 1,024 frames, and a 256^3-voxel grid.Source: §4.2 · p. 8
- The probabilistic model assumes Lambertian surfaces, ignores albedo, and attributes sensor light to third-bounce reflection, which may cause errors in concavities dominated by higher-order scattering.Source: §4.2 · p. 8
- 1,300× speed-up with reconstruction quality comparable to traditional back-projection was achieved in the final reconstruction.The comparison uses the final tessellation setting.Source: §4.1 · p. 8, Figure 6 · p. 9
- Achievable reconstruction resolution is bounded by input coverage; insufficient input resolution can leave voxel gaps, while upsampling increases computational cost.The result is similar to upsampling a lower-resolution reconstructed voxel space.Source: §4.2 · p. 9
5. Conclusions
The method frames NLOS reconstruction as voxelizing ellipsoids whose intersection forms the hidden-geometry probability map, enabling much faster GPU computation. The authors report speedups up to three orders of magnitude and make their code publicly available.
5. Conclusions
- The method reduces NLOS reconstruction cost and achieves speedups up to three orders of magnitude.The probability map is built from intersecting ellipsoids defined by light source, observed point, and photon time of flight.Source: §5 · p. 9
- Voxelizing the ellipsoids provides an approach that can be efficiently implemented on the GPU.Source: §5 · pp. 9–10
- The authors make their code publicly available to support use in practical real-world setups.Source: §5 · p. 10
A. Implementation details
The implementation stores the probability map in a 3D UINT32 texture and voxelizes ellipsoids through GPU rendering operations. It also addresses intensity overflow, rasterization gaps, and write coherency.
A. Implementation details
- A 3D single-channel UINT32 texture stores the voxel map, with depth testing disabled so all ellipsoids are rendered.The geometry shader selects a projection for tessellation, and the fragment shader updates voxel probability with an atomic add.Source: A. Implementation details · p. 10
- Intensity values are normalized to 255 to prevent worst-case overflow when intersecting more than 224 ellipsoids.The implementation assumes signal intensity fits this range; separate bounce computations are suggested to accommodate large intensity differences.Source: A. Implementation details · p. 10
- Normal swizzling leaves possible probability-map gaps, while conservative voxelization is avoided because repeated triangle rasterization may overestimate probability.Source: A. Implementation details · p. 10
- The implementation manually maintains GPU memory coherency by waiting for write operations to finish before filtering or rendering additional batches.Source: A. Implementation details · p. 10
Funding
The work acknowledges support from US, European, and Spanish research funding programs.
Funding
- The work was supported by DARPA, the European Research Council, and Spain’s Ministerio de Economía y Competitividad.The listed awards are HR0011-16-C-0025, ERC Consolidator Grant 682080, TIN2016-78753-P, and TIN2014-61696-EXP.Source: Funding · p. 10