Introduction
Phase unwrapping is a fundamental challenge in coherent signal processing, critical for applications such as Synthetic Aperture Radar (SAR), Magnetic Resonance Imaging (MRI), and X-ray crystallography. These technologies typically measure phase values "wrapped" within the $(-\pi, \pi]$ interval. To reconstruct the original continuous signal, these values must be "unwrapped" by adding or subtracting appropriate multiples of $2\pi$.
The Phase Unwrapping Problem
In ideal, noise-free conditions, phase unwrapping is straightforward. However, real-world data is often corrupted by noise and discontinuities, leading to "residues" or singularities. If an integration path encircles an unbalanced number of positive and negative residues, the result becomes path-dependent, meaning different paths yield different unwrapped values.
To resolve this, researchers employ "branch-cuts" to connect residues and neutralize their charges. The objective is to minimize the $L^0$-norm—the total length or number of these cuts. This is an NP-hard combinatorial problem that has historically forced researchers to rely on sub-optimal, ad-hoc heuristics.
Methodology: Balanced Spanning Forests
This research reformulates the problem as a Minimum Spanning Forest with Balance Constraints (MSFBCP). The authors represent residues as vertices in a graph with polarities of $+1$ or $-1$. The goal is to find a set of trees (a forest) where each tree is balanced (the sum of its vertex polarities is zero) while minimizing total edge cost.
Exact and Metaheuristic Approaches
- Branch-and-Cut: An exact mathematical programming approach using a directed cut formulation. A key innovation is a dual ascent heuristic used in pre-processing to fix variables, which reduced the problem size by an average of 78.3%.
- Hybrid Iterated Local Search (HILS): For larger instances where exact methods fail, this metaheuristic combines traditional local search moves with an integer programming "set partitioning" routine to recombine high-quality components found during the search.
Experimental Results
The methods were evaluated on synthetic benchmarks and classical real-world datasets, including Long’s Peak (steep terrain SAR), Isola’s Peak (complex terrain SAR), and a Head MRI scan.
The branch-and-cut algorithm successfully solved instances with up to 128 residues to proven optimality in less than an hour. For larger problems, the HILS metaheuristic found the optimal solution for 80 out of 90 known optima and maintained an average deviation of only 0.29% across all benchmarks. Notably, on the "Long’s Peak" dataset, the MSFBCP approach produced 32.15% fewer discontinuity points than the classic Goldstein’s algorithm and 9.30% fewer than the Minimum Cost Matching (MCM) approach.
Conclusion
By importing advanced Operations Research techniques into signal processing, this work achieves high-quality $L^0$-norm solutions previously considered computationally unattainable. The proposed balanced forest model effectively neutralizes singularities, significantly reducing "isolated regions" and improving the overall integrity of the reconstructed image. Future work will explore integrating MCM as a starting point and developing more efficient separation procedures for the branch-and-cut algorithm to handle even larger residue counts.
Summary updated