Hierarchical network flow phase unwrapping
The well-studied interferometric synthetic aperture radar (InSAR) problem for digital elevation map generation involves the derivation of topography from the radar phase. The topography is a function of the full phase, whereas the measured phase is known modulo 2/spl pi/, necessitating the process of recovering full phase values via phase unwrapping. This mathematical process becomes difficult through the presence of noise and phase discontinuities. This paper is motivated by research which models phase unwrapping as a network-flow minimization problem. A major limitation is that often a substantial computational effort is required to find solutions. Commonly, these phase images are huge (/spl Gt/10 million pixels), and obviously the sheer size of the problem itself makes phase unwrapping challenging. This paper addresses the development of a computationally efficient hierarchical algorithm, based on a "divide-and-conquer" approach. We have shown that the phase-unwrapping problem can first be partitioned into independent phase-unwrapping subproblems, which can further be recombined to produce the unwrapped phase. Interestingly, the recombination step itself can be interpreted as an unwrapping problem, for which a modified network-flow solution applies! In short, this paper develops a parallelization of the network-flow algorithm, allowing images of virtually unlimited size to be unwrapped and leading to dramatic decreases in the algorithm execution time.