PaperlayerView exact revision on arXiv

Source-linked AI summary

A Probabilistic-Cost Algorithm for Large-Scale 2D Phase Unwrapping

Scott Staniewicz, Geoffrey Gunter, Sara Mirzaee, Marin Govorcin, Talib Oliver-Cabrera, Heresh Fattahi

arXiv:2609.36267v1eess.SP

TL;DR

Wide-area InSAR processing is strained by data volumes and the computation and memory demands of two-dimensional phase unwrapping. Whirlwind uses fixed probabilistic costs and a combinatorial minimum-cost-flow solver. Across tested data, it offers substantially faster runtime with comparable unwrapped solutions.

  • Problem

    Wide-area InSAR data volumes strain algorithms designed for individual scenes, and two-dimensional phase unwrapping is a persistent bottleneck with ambiguous integer-cycle solutions.

    Source: §I · p. 1

  • Method

    Whirlwind combines fixed directional likelihood-ratio costs that marginalize phase-gradient and coherence uncertainty with an all-integer parallel-augmenting minimum-cost-flow solver.

    Source: §I · p. 2

  • Results

    Across Sentinel-1, Capella, and more than 6,000 NISAR frames, Whirlwind may provide one to two orders of magnitude runtime improvement over single-tiled SNAPHU with comparable unwrapped phase solutions.

    Source: §V · p. 10

  • Takeaways & Limitations

    Whirlwind is available as an open-source library for local use and mission-scale production.

    Source: §V · p. 10

Abstract

from arXiv · show

Two-dimensional phase unwrapping can dominate computation and memory usage in wide-area Interferometric Synthetic Aperture Radar (InSAR) processing. Here we present Whirlwind, a minimum-cost-flow (MCF) unwrapper tailored for large interferograms of surface deformation. We derive fixed likelihood-ratio costs using multilook interferometric phase statistics, marginalizing uncertainty in the local phase-gradient and coherence estimates. A compact integer lookup table and parallel-augmenting successive-shortest-path solver with Dial bucket queues make the MCF solve efficient while avoiding flow-dependent cost relinearization. We test whether these improvements in speed and memory can be obtained without a loss of solution quality using multiple evaluation criteria for individual interferograms, at mission-production scale, and in end-to-end displacement time series solutions. On a 74-Mpixel Sentinel-1 interferogram of the 2019 Ridgecrest earthquakes, Whirlwind runs in 209 s, 28x faster than single-tile SNAPHU, while using 40% of the peak memory. Across 6,014 provisional NISAR geocoded unwrapped (GUNW) products, 93% agreed with the SNAPHU-derived results on more than 99% of valid pixels; on seven challenging 77-MHz Antarctic frames, Whirlwind ran a median 21x faster than SNAPHU while matching 99.4% of its integer-cycle assignments. Finally, in a complete Sentinel-1 time series experiment, Whirlwind improved the network-inversion consistency over SNAPHU, and in a high-resolution Capella time series of the Portuguese Bend landslide, it achieved the highest correlation with a dense GPS network among five unwrapping configurations. Whirlwind is provided as an open-source library capable of handling the growing volume of globally available InSAR data.

I. INTRODUCTION

Wide-area InSAR data volumes strain algorithms designed for individual scenes, while two-dimensional phase unwrapping remains a computational bottleneck with ambiguous integer-cycle solutions. Whirlwind addresses this challenge with probabilistic-cost minimum-cost-flow unwrapping and a faster combinatorial solver.

I. INTRODUCTION

  • Phase unwrapping reconstructs a spatially consistent phase field from measurements modulo 2π, but wrong corrections can shift image regions by multiple cycles.The problem is ill-posed, and the most general problem of minimizing unwrapped differences is NP-hard.Source: §I · p. 1
  • Existing unwrappers trade off statistical expressiveness, runtime, memory, and handling of poorly connected regions; this work targets regular-grid methods for large-scale missions.SNAPHU uses scene-dependent statistical costs and iterative network optimization, while other methods use branch cuts or parallel augmenting paths.Source: §I · p. 1
  • Whirlwind uses fixed directional likelihood-ratio costs that marginalize uncertainty in local phase-gradient and coherence estimates, paired with an all-integer parallel-augmenting solver.The solver combines parallel augmentation with Dial bucket queues, avoiding flow-dependent cost relinearization.Source: §I · p. 2
  • The evaluation compares runtime, memory, coverage, and ambiguity solutions across interferograms, 6,014 provisional NISAR products, and two end-to-end displacement time series.The time-series assessment uses inversion-residual consistency checks and independent GPS station velocities.Source: §I · p. 2

A. Phase Unwrapping as Minimum-Cost Flow

  • The minimum-cost-flow construction uses a dual graph where each 2×2 loop is a node, arcs cross pixel edges, and positive and negative residues supply and demand integer flow.Opposite arc directions are priced separately because positive and negative ambiguity corrections need not have equal statistical costs.Source: A. Phase Unwrapping as Minimum-Cost Flow · p. 2
  • Each pixel edge has at most a one-cycle net ambiguity change; correcting residues with 2π adjustments makes the gradients integrable into an unwrapped phase field.Interior arcs have unit capacity, while a zero-cost, unlimited-capacity outer ring and boundary residues balance the augmented graph.Source: A. Phase Unwrapping as Minimum-Cost Flow · p. 2

B. Probabilistic Arc Costs

Whirlwind assigns directional minimum-cost-flow arcs using likelihood ratios derived from multilook phase statistics. It marginalizes uncertainty in local slope and coherence estimates, then uses fixed costs that can be precomputed for efficient optimization.

B. Probabilistic Arc Costs

  • The model uses estimated slope, the minimum endpoint sample coherence, and effective looks as its three inputs.The slope is estimated by box-filtering wrapped phase differences; its estimate is bounded to [−π, π], though the true slope need not be.Source: B. Probabilistic Arc Costs · p. 2
  • Arc costs compare the probabilities of a one-cycle correction and no correction, conditioned on estimated slope, edge coherence, and effective looks.The cost is truncated at zero; the opposite correction is represented by the reverse arc with the opposite slope.Source: B. Probabilistic Arc Costs · p. 2
  • Marginalizing over uncertainty in sample coherence and true slope prevents noisy gradient estimates from being weighted too highly.The coherence estimate is marginalized over a uniform prior on [0, 1], and the unknown slope over a flat prior on the real line.Source: B. Probabilistic Arc Costs · p. 3
  • Correction costs are directional: near a high-coherence gradient of −π, negative corrections are cheaper, while near +π, positive corrections are cheaper.Gradients near zero are expensive to correct in either direction; low-coherence edges are cheaper routes for flow.Source: B. Probabilistic Arc Costs · p. 3
  • Precomputed likelihood values on a slope–coherence–looks grid are interpolated at runtime, with costs quantized as 16-bit integers.Because costs do not depend on flow and each interior arc carries at most one unit, the objective is linear in the flow variables.Source: B. Probabilistic Arc Costs · p. 3
  • For fast-motion edges whose unsmoothed phase gradient exceeds 1 radian, an empirical correction assigns zero cost to at most 3% of valid edges.This is intended to address misleading confidence near aliased gradients without broadly changing the likelihood model.Source: B. Probabilistic Arc Costs · p. 3

C. Integer Successive-Shortest-Path Solver

Whirlwind solves the fixed-cost MCF problem with successive shortest paths. Its integer-cost search uses Dial bucket queues and parallel augmentation to accelerate flow routing.

C. Integer Successive-Shortest-Path Solver

  • Dial bucket queues replace Dijkstra’s priority queue, extracting the minimum-distance node in amortized constant time for nonnegative integer costs.Node potentials keep residual-arc reduced costs nonnegative, enabling shortest-path searches even when residual arcs otherwise have negative costs.Source: C. Integer Successive-Shortest-Path… · p. 4
  • Each multi-source Dijkstra search grows a shortest-path forest from all positive residues and augments one unit along the nearest deficit path in each source tree.Potentials are updated using search distances; the approach resembles parallel augmentation without solving a maximum-flow subproblem at each iteration.Source: C. Integer Successive-Shortest-Path… · p. 4
  • After eight full multi-source passes by default, the solver uses single-source cleanup, resumes multi-source augmentation if needed, and finally balances any remaining pairs regardless of cost.It integrates gradients in integer cycle counts to avoid roundoff and preserve congruence with the wrapped input modulo 2π.Source: C. Integer Successive-Shortest-Path… · p. 4

D. Phase preprocessing, Connected Components, and Bridging

Whirlwind offers optional phase preprocessing, connected-component labeling, and bridging for disconnected valid regions. These steps respectively support ambiguity estimation, identify reliable regions, and set relative cycle offsets between regions.

D. Phase preprocessing, Connected Components, and Bridging

  • Optional spiral interpolation or adaptive powerspectrum filtering can preprocess strongly decorrelated interferograms, but integer solutions are transferred back to the original phase and mask.Spiral interpolation replaces low-weight pixels with distance-weighted averages of nearby high-weight unit phasors; the Goldstein filter smooths overlapping Fourier-domain patches.Source: D. Phase preprocessing, Connected… · p. 4
  • Connected-component labels mark self-contained regions of reliably unwrapped phase, grown across edges whose ±1-cycle perturbation would raise the MCF objective beyond a threshold.Labels are grown using breadth-first search.Source: D. Phase preprocessing, Connected… · p. 4
  • When masks disconnect valid regions, their relative 2π levels are undetermined from wrapped phase, so a default bridging step estimates integer offsets between regions.Regions are attached in decreasing size order using nearest boundary pixels; median phase differences from 65-pixel windows determine the offsets propagated through the spanning tree.Source: D. Phase preprocessing, Connected… · p. 4

III. RESULTS

The results section evaluates Whirlwind against other unwrappers at three scales: individual interferograms, a global NISAR product campaign, and end-to-end time series. The evaluations consider computational performance, agreement, consistency, and GPS-based accuracy.

III. RESULTS

  • Individual-interferogram comparisons measure runtime, memory, and integer-cycle agreement against SNAPHU and other common unwrappers.The evaluation covers Sections III-A and III-B.Source: §III · p. 4
  • A global comparison tests agreement with production SNAPHU settings across 6,014 provisional NISAR GUNW products, including challenging Antarctic coastal-gradient frames.This evaluation is described in Section III-C.Source: §III · p. 4
  • End-to-end time-series comparisons use inversion-residual consistency and accuracy against GPS velocities to assess multiple unwrappers.These evaluations are described in Sections III-E and III-F.Source: §III · p. 4

A. The July 2019 Ridgecrest Earthquakes

Whirlwind was compared with SNAPHU and other unwrappers on a Ridgecrest interferogram and NISAR Beta frames, with strong agreement and lower runtime and memory use in the reported benchmarks.

A. The July 2019 Ridgecrest Earthquakes

  • 209 s and 8.7 GB: Whirlwind processed the Ridgecrest frame, versus 5,823 s and 21.2 GB for single-tile SNAPHU.The 5×5 tiled SNAPHU configuration took 1,166 s and 10.2 GB.Source: A. The July 2019 Ridgecrest Earthquakes · p. 4
  • 99.7% of pixels matched single-tile SNAPHU after integer-cycle alignment; the 0.3% of differences occurred near the steepest surface-rupture gradient.The comparison used a 7825×9509-pixel Sentinel-1 interferogram spanning the M6.4 and M7.1 earthquakes.Source: A. The July 2019 Ridgecrest Earthquakes · pp. 4–5

B. NISAR Beta Benchmark

  • The Beta comparison re-wrapped production phase and compared integer-cycle matches against SNAPHU production results, not absolute accuracy.Thirteen frames were tested against four other configurations: single-tile and 3×3-tiled SNAPHU, ISCE3 PHASS, and ISCE2 ICU.Source: B. NISAR Beta Benchmark · p. 5
  • Whirlwind agreed with production at 98.8–100% on 12 of 13 Beta frames; on the other six frames, all tested unwrappers agreed at 90% or better.The seven frames shown were the 13 tested frames with the largest unwrapper differences.Source: B. NISAR Beta Benchmark · p. 5
  • Whirlwind ran 30–200× faster than single-tile SNAPHU (median 92×) and 6–21× faster than fully concurrent tiled SNAPHU, using under half the single-tile SNAPHU memory.Adding concurrency to tiled SNAPHU improved runtime but increased memory use by 1–6 GB.Source: B. NISAR Beta Benchmark · p. 5

C. Provisional NISAR Campaign

Across 6,014 provisional NISAR products, Whirlwind closely matched production SNAPHU on most frames and labeled a larger share of valid pixels. The largest disagreements often reflected challenging data conditions.

C. Provisional NISAR Campaign

  • Over 93% of 6,014 frames agreed with production SNAPHU on at least 99% of pixels; median agreement was 99.99%.The campaign included provisional GUNW products with at least 25% land coverage.Source: C. Provisional NISAR Campaign · p. 5
  • Whirlwind labeled a median 95% of valid pixels, versus 91% in production SNAPHU settings; median runtime was 47 seconds and median peak memory was 4.34 GB.The 95th-percentile runtime was 77 seconds and peak memory was 5.60 GB.Source: C. Provisional NISAR Campaign · p. 5
  • Many large disagreements reflected data challenges: high phase gradients and low correlation in Antarctica, or disconnected valid regions in fixed-PRF scenes over the US Midwest and India.Whirlwind's preprocessing and bridging steps appeared to handle the fixed-PRF regions better than the production configuration.Source: C. Provisional NISAR Campaign · p. 6

D. Antarctic Outlet Glaciers

Across seven challenging Antarctic frames, Whirlwind closely matched production SNAPHU while running substantially faster; South Florida time-series tests found fewer inversion residuals and shorter total runtime than tiled SNAPHU.

D. Antarctic Outlet Glaciers

E. Sentinel-1 Time Series over South Florida

  • Nonzero L1 inversion residuals indicate likely integer-unwrapping errors, although zero residuals do not establish that unwrapping is error-free.The South Florida test used 26 acquisitions spanning 2024, with 72 interferograms and no further filtering or atmospheric corrections.Source: E. Sentinel-1 Time Series over South… · p. 7
  • In the South Florida urban area, Whirlwind’s network inverted with zero residual, while SNAPHU accumulated about 30 cycles of misclosure.Across the Everglades coast, at least one cycle of total misclosure occurred in 43% of coherent pixels for Whirlwind versus 82% for SNAPHU.Source: E. Sentinel-1 Time Series over South… · pp. 7–8
  • Whirlwind unwrapped 72 phase-linked interferograms in 6 hours using 4 CPUs, compared with 26 hours for tiled SNAPHU using 10 CPUs.The stack used 26 Sentinel-1 acquisitions and identical L1 network inversion for both unwrappers.Source: E. Sentinel-1 Time Series over South… · pp. 7–8

F. Portuguese Bend Landslide

In the Portuguese Bend landslide time series, Whirlwind had the highest reported GPS correlation among the compared unwrappers and required less unwrapping time than SNAPHU. Its fixed-cost formulation narrows the problem to surface-deformation interferograms to enable efficient MCF solving.

F. Portuguese Bend Landslide

  • The comparison reran unwrapping on identical inputs for 150 interferograms and inverted each result into a 51-epoch displacement series.Statistics excluded locations masked or assigned zero connected-component labels in more than 100 interferograms; GPS comparisons used a 5-meter window around each station.Source: F. Portuguese Bend Landslide · p. 8
  • Whirlwind achieved GPS correlation r = 0.93 in 0.6 h, compared with SNAPHU’s r = 0.89 in 8.0 h.The comparison used 103 GPS stations; PHASS, ICU, and sparse 3D EMCF were also evaluated, with ICU covering only 52 stations and EMCF yielding r = 0.77 at 37 stations.Source: F. Portuguese Bend Landslide · p. 8, Table III · p. 8

A. Runtime improvements over SNAPHU

  • Whirlwind narrows SNAPHU’s general cost-model scope to surface-deformation interferograms, using costs linear in flow to exploit efficient MCF algorithms.SNAPHU’s smooth-mode costs depend on current edge flow and require iterative re-evaluation; Whirlwind does not provide specialized topography or discontinuous-deformation modes.Source: A. Runtime improvements over SNAPHU · pp. 8–9

B. Comparison to SNAPHU’s Deformation mode for coseismic rupture

On the Ridgecrest interferogram, SNAPHU’s deformation-cost mode produced only minor solution differences from its smooth mode near the rupture, but the best unwrap remains ambiguous in this noisy, complex region. The conclusion reports comparable solutions alongside substantial runtime improvements over single-tile SNAPHU.

B. Comparison to SNAPHU’s Deformation mode for coseismic rupture

  • Changing SNAPHU from smooth to deformation costs produced minor solution differences near the Ridgecrest rupture; deformation mode ran about 1.5× slower and labeled 95.5% of valid pixels, versus 96.5% for smooth mode.Both SNAPHU modes assigned zero connected-component labels near the low-coherence rupture area.Source: B. Comparison to SNAPHU’s Deformation… · p. 9, Figure 9 · p. 10
  • Near the noisy surface rupture, it is ambiguous which unwrapper or cost mode gives the best result, and some earthquake-source studies avoid unwrapping entirely.Alternatives include analyzing phase gradients, fitting geophysical models directly to wrapped phase, or pixel offset tracking.Source: B. Comparison to SNAPHU’s Deformation… · p. 10

V. CONCLUSION

  • Across Sentinel-1, Capella, and more than 6,000 NISAR frames, Whirlwind may run one to two orders of magnitude faster than single-tile SNAPHU with comparable unwrapped solutions.Whirlwind is provided as an open-source library for local use and mission-scale production.Source: §V · p. 10

APPENDIX A FURTHER WHIRLWIND–SNAPHU COMPARISONS FROM THE PROVISIONAL NISAR CAMPAIGN

The appendix presents selected provisional NISAR frames with the largest disagreements in a 6,014-product Whirlwind–SNAPHU comparison. It cautions that some apparent production problems may reflect configuration or bridging implementation rather than the underlying algorithms.

APPENDIX A FURTHER WHIRLWIND–SNAPHU COMPARISONS FROM THE PROVISIONAL NISAR CAMPAIGN

  • Figures S2–S12 show selected frames with the largest disagreements among 6,014 provisional NISAR GUNW comparisons, including phase, coherence, component coverage, and integer-cycle differences.The examples include frames with fixed-PRF transmit gaps and subswath gaps.Source: Appendix A · p. 13, Figure S1 · p. 14
  • Some apparent production-SNAPHU problems may reflect misconfiguration, while differences across expected fixed-PRF subswath gaps arise from bridging post-processing implementation.The appendix notes that the nonzero component label in empty subswaths in one frame was due to a misconfiguration fixed in later releases.Source: Appendix A · p. 13, Figure S2 · p. 14
Loading 2609.36267v1…