Adaptive Tiling for Least-Squares Phase Unwrapping: Runtime and Accuracy

1 Motivation and scope

• Adaptive tiling is tested against a grid because its time savings depend on the costs of identifying and reconstructing regions as well as the boundaries removed.The study compares complete reconstruction time and reference agreement, then examines alternative refinement criteria and tile budgets.Source: §1 · p. 2

2 Reconstruction with a common solver

• A spatial tree sets tile boundaries while a separate reliability tree joins reconstructed tiles, allowing all partition types to share the same solver and joining rule.The common pipeline includes preparation, reconstruction, reconciliation, and cleanup in its complete-call timing.Source: §2 · p. 3, Figure 2 · p. 3

2.1 Residues and subdivision

• A cell residue is its signed principal-difference circulation in multiples of 2π; quadtree refinement splits eligible positive-score leaves, with residue-free tiles retained.The unrestricted runtime comparison splits every eligible tile containing a residue; internal residue tests do not guarantee the true phase or detect inconsistencies across tile boundaries.Source: §2.1 · pp. 3–4

2.2 Binary alternatives to the quadtree

• The kd-tree makes horizontal or vertical cuts, allowing one direction to refine without the other; midpoint and dyadic rules use the same residue stopping test as the quadtree.Dyadic cuts favor dimensions supported by fast transforms but do not guarantee power-of-two tile dimensions.Source: §2.2 · p. 4

2.3 Local reconstruction and boundary reconciliation

• Within each tile, a DCT solves the local Poisson system; neighboring tiles are aligned using seam-offset estimates and a reliability-weighted spanning tree.The seam median estimates the offset difference, while MAD measures disagreement; the seam-length weight is heuristic rather than calibrated uncertainty.Source: §2.3 · pp. 4–5

2.4 Partition and reconstruction algorithms

• The partition algorithm scores and splits eligible leaves, while reconstruction solves tiles, estimates seam offsets, joins them, and assembles the output without using ground truth.Ground-truth phase is used only for subsequent accuracy evaluation.Source: §2.4 · p. 5

3.1 Inputs, controls, and measurements

• The 208-entry dataset uses ten inputs to guide implementation choices and the other 198 for comparison; timings use one thread and accuracy is evaluated against references.Non-square inputs are padded to a square for reconstruction, and output is cropped before evaluation.Source: §3.1 · pp. 6–7, Table 1 · p. 7

3.2 Optimizations shared with the grid

• Implementation changes reduce median paired quadtree runtime by about 51% at s = 8 and 42% at s = 16 versus a reference quadtree, but do not establish an advantage over the grid.Transferable changes are also applied to the grid baseline.Source: §3.2 · p. 8

3.3 Measured outcome

• Quadtree reconstruction takes 24% longer in median paired time at s = 8 and 53% longer at s = 16; no tested adaptive configuration beats the optimized grid’s per-image median time.Neither kd-tree reverses the result across the 198 main-comparison entries.Source: §3.3 · p. 8, Table 2 · p. 8
• At s = 8, binary variants are close to the quadtree in median runtime; at s = 16, neither improves that statistic, though dyadic cuts reduce summed time on expensive shapes.Binary subdivision requires L −1 splits for L leaves, versus (L −1)/3 for a full quadtree.Source: §3.3 · p. 8
• Residue-balanced cuts take about 1.53 and 1.85 times midpoint kd-tree runtime at s = 8 and s = 16, respectively, and reduce mean success at both sizes.The broader comparison therefore retains the simpler midpoint and dyadic rules.Source: §3.3 · p. 8
• Mean RMSE increases for all three adaptive configurations, and two related shear-field entries fall from full grid success to zero adaptive success.The shear failures also occur with the reference quadtree, so they are not introduced by the faster construction routine.Source: §3.3 · p. 9

3.4 Why fewer tiles do not save time

• Partition construction accounts for about 24–25% of summed quadtree time and local reconstruction for 47–54%; every pixel still contributes to a local solve.A fast transform costs approximately O(nt log nt) for a tile of nt pixels, so replacing several small tiles with one larger tile does not necessarily reduce transform work.Source: §3.4 · p. 9
• Faster DCTs change only part of local-solve time, and the same improvement is available to the grid, so kernel speedups alone do not establish a complete-runtime advantage.The local-solve stage also includes input extraction and right-hand-side construction.Source: §3.4 · p. 10

4.2 Criterion and budget evaluation

• The comparison crosses nine criteria with two minimum tile sizes and two leaf-budget targets on 208 entries, measuring tile allocation and reference error rather than imposing an error tolerance.The 7488 reconstructions use the same double-precision DCT solver, quantization, and reliability-tree reconciliation; Table 3 reports median tile counts and paired changes in success and RMSE against residue count at matching size and budget.Source: §4 · p. 10, §4.2 · pp. 12–13, Table 3 · p. 12

4.1 Stopping rules and priority scores

• The nine scores span residue inconsistency, local net charge, paired residue paths, rapid phase edges, gradient variance, slope changes, near-π edges, raw phase jumps, and image-independent tile size.A score of zero stops refinement; positive scores prioritize splits under a tile budget, so different scores can alter allocation even when they leave zero-score tiles the same.Source: §4.1 · pp. 10–12

4.2 Criterion and budget evaluation

• At s = 8 and budget B1, residue count yields 302.5 median tiles, versus 1024 for gradient variance, Laplacian magnitude, and uniform control; those dense criteria have mean success about 1.50–1.53 percentage points lower and mean RMSE about 0.36 radians higher.The near-π criterion has a median of one tile but loses 5.50 percentage points of success.Source: §4.2 · p. 13
• At s = 8 and budget B1/2, fringe density improves mean success by 0.37 percentage points and reduces mean RMSE by 0.23 radians, while median tiles rise from 302.5 to 514.At s = 16 with the same budget fraction, fringe density also improves both error measures, although both median counts are 130.Source: §4.2 · p. 13

4.3 Relaxed stopping and runtime

• Density-based relaxed stopping takes 1.6–12.4% longer and reduces mean success by 0.78–5.93 percentage points; the perimeter cutoff is about 0.9% faster at s = 8 but 2.3% slower at s = 16, with higher mean RMSE at both sizes.The tests compare these stopping rules with an unrestricted residue-count quadtree using the same solver and joining procedure.Source: §4.3 · p. 13

4.4 Computational shortcuts and retained configuration

• Direct integration is about 1–4% slower than the DCT-based control, while early-exit residue searches take about 3–4% longer; the retained implementation uses fused residue tables and DCT solves.Integration checks every remaining edge before skipping a DCT; early-exit scans can revisit cells before falling back to a summed-area table.Source: §4.4 · pp. 13–14
• Residue count remains an interpretable, economical baseline, but the optimized quadtree is still slower than the grid, and speed at a specified error tolerance remains unresolved.A proper comparison would identify the fastest configurations meeting each tolerance, rather than comparing tile counts alone.Source: §4.2 · p. 13, §4.4 · p. 14

5 Discussion and conclusions

• The optimized grid remains faster than tested quadtree and kd-tree configurations because residue preprocessing and larger local solves outweigh savings at tile boundaries.The criterion study also finds that more refinement need not improve reference agreement, and occasional accuracy gains depend on score and budget.Source: §5 · p. 14
• The runtime conclusion is limited to single-threaded encoded-input reconstruction on one machine, with unrestricted residue refinement and the evaluated padding, quantization, and reconciliation pipeline.Related dataset entries and different reference types also limit generalization to independent physical acquisitions; this is not a universal ranking of adaptive methods.Source: §5 · p. 14
• Whether limited refinement can yield a faster approximate reconstruction remains open; the proposed study would find the fastest grid, quadtree, or kd-tree setting at each allowed error level.It would vary adaptive criterion, tile budget, and minimum tile size, as well as grid tile size, while measuring complete reconstruction time and reference error.Source: §5 · p. 14
• Further engineering targets include shared gradient preparation, grouping equal-shaped tiles, and avoiding unnecessary solver initialization; these are candidates, not demonstrated speedups.The practical conclusion is to retain the grid as the runtime baseline and judge adaptive changes by complete reconstruction comparison.Source: §5 · p. 14

Data and code availability

• Public source collections are identified in Table 1, and photograph-derived inputs include images attributed to the USC-SIPI collection.Source: Data and code availability · p. 15
• The authors retain the assembled derived arrays, case lists, preprocessing scripts, experiment code, and outputs, which are not currently publicly available.Source: Data and code availability · p. 15
• Some locally prepared inputs lack a complete generation recipe, so source-collection citations do not reproduce the exact benchmark.Source: Data and code availability · p. 15

Document information

• The supplement lists Antoine Moevus and Max Mignotte as authors and September 2026 as its date.Source: Runtime and Accuracy — Supplementary… · p. 16

Supplement scope

• The supplement collects detailed input descriptions, additional method analysis, score maps, and supporting measurements.The accompanying technical report contains the primary complete-reconstruction comparison in Table 2.Source: Runtime and Accuracy — Supplementary… · p. 16

Comparison scope

• The baseline DCT-library comparison evaluates a different implementation and is reported separately from the primary result.The primary result is the complete-reconstruction comparison using BRiDCT in the main report’s Table 2.Source: Runtime and Accuracy — Supplementary… · p. 16

Data

• The 208-entry dataset combines 158 entries with known generating references, 30 real radar-interferometry entries with terrain-model references, and 20 experimental holographic entries with algorithmic references.Agreement with an algorithmic reference is not independent physical ground truth.Source: S1 Data and measurement details · p. 16

Input preparation

• Reconstruction-time inputs are encoded at 256 intensity levels per cycle, and non-square arrays are zero-padded to a square working domain before output is cropped for evaluation.Reconstruction covers the padded square, including pixels outside evaluation masks; MRI inputs use cropped QSM simulations and supplied brain masks.Source: S1 Data and measurement details · p. 16

Measurements

• Success measures the fraction within tolerance, whereas RMSE is sensitive to large errors; the main report gives paired success changes in percentage points and RMSE changes in radians.The median runtime statistic summarizes paired ratios, while summed-time is a ratio of summed case times.Source: S1 Data and measurement details · p. 16

S2.1 Local fitting and residues

• A tile’s local fit uses observed principal differences on within-tile edges to form a discrete Poisson system, with the DCT solving it and the zero-frequency coefficient fixed to remove the undetermined constant.The local fit excludes edges outside the tile, and local and final values are quantized using 256 intensity units per cycle.Source: S2.1 Local fitting and residues · p. 16
• Residue count sums absolute cell residues over cells wholly inside a tile; zero residues imply consistent observed differences on a hole-free rectangle, not recovery of the true phase.Wrapped slopes of 3π/2 and −π/2 per pixel can have identical observations and zero residues, while tile-boundary cells are omitted from the local count.Source: S2.1 Local fitting and residues · p. 17

S2.2 Budget conventions

• The size-based criterion budget is B1 = max(1, ⌊H/s⌋⌊W/s⌋), while the restricted budget is B1/2 = max(1, ⌊B1/2⌋); regular grids include partial edge tiles.On non-dyadic images, bisection need not reproduce the regular grid.Source: S2.2 Budget conventions · p. 17

S2.3 Complexity of the measured implementation

• Local transform work scales with tile dimensions, while direct separable fallback can dominate aggregate speedups on unusual shapes; pixel extraction and output assembly still require linear work.Binary trees perform L −1 splits, and residue-balanced cuts add binary-search work.Source: S2.3 Complexity of the measured… · pp. 18–19
• Residue evaluation and summed-area queries cost O(N), priority refinement uses O(L log L) queue operations, and seam collection, sorting, and reconciliation add costs driven by boundary samples and adjacent tile pairs.Weighted union–find takes O(Eα(L)) amortized work; spatial and reconciliation storage is O(N + E + L), excluding reusable transform plans.Source: S2.3 Complexity of the measured… · p. 18

S2.4 Exact candidate score definitions

• The nine criteria include residue and fringe measures, phase-variation measures, edge thresholds, and a uniform control; Figure S1 displays their independently normalized spatial support without ranking runtime or accuracy.The definitions include paired cut length, gradient variance, Laplacian magnitude, near-π edge, and raw phase jump.Source: S2.4 Exact candidate score definitions · p. 19

Benchmark setup

• The benchmark times a normalized forward/inverse DCT pair and a Poisson spectral solve on one thread in single precision, with setup, allocation, and right-hand-side construction excluded.It uses an Apple M3 Max, power-of-two square sides 8–256, and nine randomly ordered batches; all 225 numerical checks pass with relative error below 4 × 10−7 on nonconstant cases.Source: S3 Baseline DCT-library comparison · p. 19, Table S3 · p. 21

Kernel benchmark results

• At sides 8–64, the baseline Shao–Johnson implementation is fastest for both benchmark tasks; at 16 × 16 its spectral solve takes 0.189 µs versus 0.489 µs for specialized Ooura.At sides 128 and 256, it ranks second to Accelerate and takes about 1.5–1.6 times as long.Source: S3 Baseline DCT-library comparison · p. 20, Table S3 · p. 21

Scope of comparison

• The small-tile baseline measurements support Shao–Johnson’s factorization choice for small tiles, but do not measure BRiDCT’s performance in complete reconstruction.Final reconstruction experiments use BRiDCT with the FFTW fallback.Source: S3 Baseline DCT-library comparison · p. 20

• The ten-input tests select configurations rather than rank criteria B–I, and their exploratory component timings are not pooled with primary measurements.The primary reconstruction timer includes temporary-buffer destruction.Source: S4 Additional implementation tests · p. 21
• At s = 8 and s = 16, density and low-charge stopping did not consistently improve both measured time and reference agreement.These rules can retain inconsistent tiles, unlike zero-residue stopping.Source: S4 Additional implementation tests · p. 21
• Verified direct integration did not consistently reduce reconstruction time, so the selected pipeline keeps the DCT solve on every tile.The grid received the same integration option.Source: S4 Additional implementation tests · p. 21
• Table S4 reports paired time ratios and mean changes in Sπ and RMSE across ten inputs, with ratios above one indicating slower runtime.Its controls differ by test, and rows from separate timing sessions do not establish a cross-variant ranking.Source: S4 Additional implementation tests · p. 21, Table S4 · p. 22
• Limits of N, 2N, and 4N inspected cells preserved tested partitions and outputs but were slower overall.The main implementation computes the fused residue table once.Source: S4 Additional implementation tests · p. 22
• Residue-balanced cuts added search cost and could produce less favorable transform shapes, with no consistent exploratory benefit.The main comparison therefore uses geometric midpoint or power-of-two-biased cuts.Source: S4 Additional implementation tests · p. 22

• The complete reconstruction comparison used a frozen BRiDCT version and identical encoded, padded arrays across the grid and both tree geometries.BRiDCT uses single precision, while phase preparation and boundary statistics use double precision.Source: S5 Implementation and numerical checks · p. 22
• The main timing comparison comprised 13,860 timed calls across 198 entries, five methods, two minimum sizes, and seven repetitions.Numerical checks separately compared residue maps, partitions, and outputs for optimizations intended to preserve semantics.Source: S5 Implementation and numerical checks · p. 22
• 15 entries at s = 8 and eight at s = 16 differed in final rounding after replacing a transform fallback, while success fractions stayed unchanged.The largest absolute RMSE change was below 5.1 × 10^-4 radians.Source: S5 Implementation and numerical checks · p. 23
• A diagnostic found no disagreement between residue zero/nonzero tests and integer local-gradient circulation on 256 constructed cells, but it was not a proof for arbitrary observations.Source: S5 Implementation and numerical checks · p. 23

S6 First-call latency

• The first-call study used 180 fresh processes, and all 1,260 warm outputs matched their process’s first-call output.First-call times were summarized across three processes per image/configuration; warm times used within-process medians before across-process summaries.Source: S6 First-call latency · p. 23

Availability and interpretation

• Benchmark arrays, implementations, and outputs are not currently publicly available, limiting independent reproduction of the numerical results.Some photograph metadata lack an exact public filename, and some generated fields lack a complete retained recipe.Source: Availability and interpretation · p. 23