Planar graph
A planar graph is a graph that can be drawn on a plane in such a way that its edges intersect only at their end point, i.e, its edges do not cross each other. In the context of this package, we assume that planar graphs are connected and all cycles in a planar graph are of the same length. Planar graphs satisfy Euler's formula
where \(v\) is the number of vertices, \(e\) is the number of edges and \(f\) is the number of faces in the graph.
We implement a generic interface for a planar graph via spurt.graph.PlanarGraphInterface. We support the following types of planar graphs in spurt.
Regular 2D grid graph
This corresponds to a regular 2D grid underlying the classical Minimum Cost Flow (MCF) problem [Costantini, 1998]. Each cycle in this planar graph is of length 4. We can create a regular grid 2D graph using
g = spurt.graph.Reg2DGraph((nlines, npixels))
Irregular 2D grid graph
This corresponds to an irregular 2D grid underlying the sparse MCF problem [Costantini and Rosen, 1999]. A Delaunay triangulation for a sparse grid can be created as follows
g = spurt.graph.DelaunayGraph(coords)
where coords is a Npts x 2 numpy array.
Hop3 graph
This is a graph that is primarily used with phase-linked stacks of narrow baseline SAR sensors like Sentinel-1 and NISAR during temporal unwrapping. It is meant to be a replacement to the Delaunay graph used in the temporal dimension in the original EMCF method [Pepe and Lanari, 2006]. In a Hop3 graph each SAR image is connected to three acquisitions before and after it in time.
The Figure below shows how such a connected network of interferograms can always be generated by placing the node corresponding to acquisition \(t_i\) inside the triangle represented by nodes \(t_{i-3}\), \(t_{i-2}\) and \(t_{i-1}\) on a plane.
| Costantini, 1998 | Costantini M., 1998. A novel phase unwrapping method based on network programming. IEEE Transactions on Geoscience and Remote Sensing. 36, pp.813-821. 10.1109/36.673674 |
| Costantini and Rosen, 1999 | Costantini M. and Rosen P., 1999. A generalized phase unwrapping approach for sparse data. 10.1109/IGARSS.1999.773467 |
| Pepe and Lanari, 2006 | Pepe A. and Lanari R., 2006. On the Extension of the Minimum Cost Flow Algorithm for Phase Unwrapping of Multitemporal Differential SAR Interferograms. IEEE Transactions on Geoscience and Remote Sensing. 44, pp.2374--2383. 10.1109/TGRS.2006.873207 |