Knowledge of complete river networks is essential to a number of geographical and environmental applications, like designing shortest routes for ships, locating forthcoming affected areas of flooding and pollutant leaks, and identifying possible migrations of aquatic organisms. However, that information is usually not immediately available with conventional airborne surveying techniques like standard photogrammetric and multi/hyper-spectral imaging. Clouds and tree canopies often occlude parts of the river network (Asante and Maidment 1999), leaving us disconnected fiver segments. We may perform ground surveys as supplements, but they are much more costly Worse still, sometimes we cannot afford the long time they take, or we simply cannot do them due to harsh ground conditions, as in emergency surveys during or immediately after natural disasters like earthquakes, hurricanes and flooding. This leads to a need to connect the broken segments together to form a complete river network. That complete fiver network usually consists of a number of tree branching structures. Every fiver location is expected to have a single way for the water to flow out to a terrain edge or a sink within the terrain (Asante and Maidment 1999; Arge et. al. 2003a). The width of the river branches may be large, but very often we aim at the respective "central lines" where water accumulation is a maximum among its immediate neighbors except the one towards which its water flows.
Intuitively, if we have the fragmentary river observations only but not anything else, the best thing that we can do is to join the segments together as if they are typical line pieces (Asante and Maidment 1999). If the gaps are as small as a few pixels wide, we may use the dilation morphological operation to extend the line pieces gradually until their ends meet (Noble 1996). When we want to conserve the collinearity of the segments, the Hough transform (Hough 1962) provides a voting process to make sure that only collinear pixels can be extended. For curves of arbitrary shapes, we may adopt a more compficated technique like the axis-oriented linking (Zhang 2000). Note that they are all assuming line behaviors that we generalize from typical river segments, like shortest routes and segment curvature preservation, in the reconnection process. However, if we also know the set of ground elevations in addition, we may eliminate any possibilities that violate the height constraint, namely that water flows from a higher location to a lower location. This potentially improves the realism of the reconnection results, as we are using information that directly affects drainage. As a critical example, suppose that a hill is sitting in between two river segments. Then even though the end points of these two segments are very close, it is highly likely that the flow from one segment does not go to the other one.
To date, Light Detection and Ranging (LiDAR) provides the most promising survey results on ground elevations. It works by emitting laser pulse energy from a plane travelling across a terrain and collecting the backscatters from the ground. The time elapse between a laser pulse emission and the return of the corresponding backscatter tells the distance between the ground and the plane. Together with a georeferenced record on where those pulses are emitted, we can derive the elevation field of the terrain. However, cloud and canopy covers continue to be the major obstacles. The laser cannot pass through the clouds (National Oceanic and Atmospheric Administration Coastal Services Center 2008). For canopies, LiDAR may "see through" the forest as long as we can detect sufficient backscatters of the small footprint laser pulses that propagate through small canopy openings to the ground. If we fail, we may overestimate the ground heights as we identify no data points that are from the ground, or we mistreat the reflections from an above-ground …