SRA: Fast Removal of General Multipath for ToF Sensors

1 Introduction

• Multipath lets a pixel receive light originally sent for other pixels, and it is significant in scenes with shiny or specular-like floors.ToF measurements use the phase shift of light returning from surfaces.Source: §1 · p. 1
• Multipath corrupts measurements in ways unlike ordinary noise and can cause large errors in depth estimates.Figure 1 illustrates the effect and the proposed removal.Source: §1 · p. 1, Figure 1 · p. 2

1.1 Contributions

• The paper frames its contributions as improvements in two areas of the state of the art.Source: §1.1 · p. 2

1. More General Multipath

• SRA handles general multipath, including combinations of diffuse and specular multipath and specular multipath with three or more paths.The paper says simple scene geometries can produce these combinations.Source: §1 · p. 2
• Prior work is grouped into methods for diffuse multipath from Lambertian surfaces and methods for two-path multipath from specular surfaces.Source: §1 · p. 2
• SRA is presented as the first algorithm, to the authors’ knowledge, that handles diffuse multipath while running at 30 fps.The paper contrasts this with prior diffuse-multipath methods that typically take a few minutes per frame.Source: §1 · p. 2

1. More General Multipath

• SRA models a rich class of multipath phenomena using sparse or compressible backscattering and formulates estimation as an L1 optimization problem.Source: §1 · p. 2
• Prior work targeting two-path specular multipath already runs in real time, qualifying the paper’s speed novelty claim.Source: §1 · p. 2
• The optimization is posed to admit a global optimum, which the paper identifies as crucial for robust cancellation of general multipath under considerable measurement noise.Source: §1 · p. 3

2. Speed

• Direct per-pixel SRA optimization is relatively fast but still too slow for real-time performance.Source: §2 · p. 3
• A novel dimension reduction enables a lookup-table-based approach to accelerate SRA.Source: §2 · p. 3
• The lookup-table approach gives extremely fast performance in practice.Source: §2 · p. 3

• SRA reconstructs accurate depth in scenes with more than two specular paths and combined diffuse and specular multipath, unlike competing methods.Source: §3 · p. 3
• For standard two-path multipath, SRA outperforms the state-of-the-art.Source: §3 · p. 3
• The authors also demonstrate SRA on challenging images from Microsoft’s Xbox One sensor.Source: §3 · p. 3

• Structured-light approaches remove multipath using additional sensors.Source: §2 · p. 3
• Diffuse-only methods use ray tracing or iterative optimization and take 1–10 minutes per frame.The cited works model diffuse multipath from Lambertian surfaces.Source: §2 · p. 3
• Two-path methods operate per pixel and may be near real time, but some require four or five modulation frequencies.Source: §2 · pp. 3–4
• The three-frequency method in is the nearest competitor because it runs in or near real time.Source: §2 · p. 4

3.1 The Multipath Representation

• The backscattering model represents measurements as frequency-dependent returns, extending from two paths to diffuse and more general multipath.Diffuse multipath is represented by a continuum of contributions beginning at d1+∆; the model is discretized over candidate distances.Source: §3.1 · pp. 4–5

A Characterization of the Backscattering

• Backscattering is nonnegative and compressible: sparse two-path returns and rapidly decaying diffuse returns fit this characterization.Compressibility is described by power-law decay in the sorted coefficients.Source: A Characterization of the Backscattering · pp. 5–6

3.2 The SRA Algorithm

• Because measurements are underdetermined, SRA uses nonnegativity and compressibility to restrict candidate backscatterings.Source: A Characterization of the Backscattering · pp. 5–6, §3.2 · p. 6
• The method models sensor noise as Gaussian with zero mean and known covariance, while noting that shot noise is often present and can be accommodated.Source: §3.2 · p. 6
• L1 optimization replaces the NP-hard sparse L0 formulation with a convex alternative, though the matrix generally lacks conditions such as the Restricted Isometry Property.The authors therefore note that certain theoretical guarantees do not hold for their matrix.Source: §3.2 · pp. 6–7
• Replacing the L2 residual constraint with an L1 constraint recasts the optimization as a linear program that can be solved considerably faster.Source: §3.2 · p. 7
• The resulting backscattering yields depth at its first nonzero index, using a relative threshold in practice to handle numerical residuals.The typical threshold is 0.01 times the largest coefficient.Source: §3.2 · pp. 7–8
• With a noise model, SRA can invalidate a pixel when no return has enough probability of being the true return.The example probability threshold is 0.9.Source: §3.2 · p. 8

4 Fast Computation

• Solving the original optimization takes about 50 ms per instance on a standard CPU, which the paper says would require at least an hour per frame for several hundred thousand pixels.The proposed method is intended to run at 30 Hz on ordinary hardware for 424 × 512 images.Source: §4 · p. 8
• Reducing the lookup-table dimension by two cuts its memory by a factor of L^2 when each dimension is discretized into L cells.The paper presents this reduction as making the lookup-table approach feasible in practice.Source: §4 · p. 8

A Useful Transformation

• The transformation preserves the backscattering when applied to both the measurement and sensing matrix, assuming diagonal covariance with paired equal entries.It shifts the represented distance range by −∆, so ∆ must be added when extracting depth; the theorem applies to optimization (7), while practice uses its stated approximation (8).Source: A Useful Transformation · p. 9
• The canonical transformation makes one complex measurement component redundant, reducing the lookup-table input from 2m to 2m −2 real dimensions.The redundant component is completely determined by the others, so it can be removed without losing information.Source: A Useful Transformation · p. 9

5.1 Running Time

• SRA runs in 31.2 ms per 424 × 512 frame, meeting 30 fps on an Intel Core i7 using largely unoptimized Matlab and CPU parallelization.The reported speed comes from the lookup-table approach.Source: §5.1 · p. 10

5.2 General Multipath: Examples

• For three specular paths at SNR 5, SRA estimates depths of 97, 200, and 306 cm instead of 100, 200, and 300 cm, yielding 3 cm depth error.The interfering returns together are five times stronger than the initial return; extracted peak amplitudes change by less than 20%.Source: §5.2 · p. 10
• SRA outperforms Godbaz and maximum-likelihood two-path alternatives for three-path interference, with a wide margin once noise is added; Godbaz fails at SNR 20, while ML remains less accurate.In the hardest configuration, with multipath six times stronger than the original path and closely spaced returns, SRA’s error is still considerably lower except at SNR 5, where it is similar to ML.Source: §5.2 · p. 11
• In combined diffuse and specular multipath, SRA yields the lowest depth-estimation error, while Godbaz has fairly large errors and maximum likelihood performs better but remains less accurate.The simulated backscattering is compressible but not sparse.Source: §5.2 · p. 11, Figure 5 · p. 12

5.3 Comprehensive Two-Path Evaluation

• MAE stays below 2.6 cm in every tested square and averages 1.4 cm for SNRs from ∞ to 8.5 and multipath strengths from 0.6 to 2.2.Even at multipath strength 5 and SNR 3.2, MAE is 7.9 cm; errors increase gradually as multipath strengthens and SNR falls.Source: §5.3 · pp. 12–13

5.4 Real Images

• The real-image comparison uses Opt-Single rather than competing real-time methods because their frequency requirements or modulation-frequency constraints do not match the Xbox One sensor.The sensor uses three modulation frequencies.Source: §5.4 · p. 13
• On real scenes, SRA recovers a clean, nearly flat floor, table surfaces, a wall-floor corner, and much of a chair wheel that Opt-Single misses or misestimates.Low reflectivity causes SRA to invalidate some pixels on a patterned wall-hanging.Source: §5.4 · p. 14

• SRA removes multipath interference from ToF images.Source: §6 · p. 15
• The method handles many types of multipath and is fast.Source: §6 · p. 15
• Experiments on synthetic data and challenging real images validate SRA, demonstrating superior performance.Source: §6 · p. 15