Bridge Detection in Grid Terrains and Improved Drainage Enforcement

Ryan Carlson and Andy Danner

One application of Geographic Information System (GIS) data is the hydrologic analysis of gridded Digital Elevation Models (DEMs). Using Light Detection and Ranging (LIDAR) technology, large, hi-resolution elevation data can be collected. In addition to terrain, the data might include smaller features like trees, buildings, and bridges. This summer's goal was to automate detection of bridges, which impede watershed analysis, and to alter the terrain to yield hydrologically correct DEMs.

A machine learning algorithm called AdaBoost was used to combine sets of simple filters that detect local bridge-like features. It takes features describing hand-labeled positive and negative training samples as input. The algorithm combines these features into a powerful bridge classifier. This classifier is then used on unlabeled test data and outputs a grid that assigns to each likely bridge location a numerical coincidence score. Using a training set of about 400 hand-tagged positive and negative samples, the classifier correctly classifies bridges over 95% of the time. Once bridges are classified, a two-pass conditioning approach is used to remove the bridges from the terrain data. The first pass makes large cuts that result in hydrologically correct but blocky terrain. Using the flow models made available by the first pass, a carving algorithm is implemented that makes smaller, more precise cuts in the original terrain.

The river networks extracted from the minimally conditioned terrain show marked improvement over the original terrain. Future work may involve parallelizing the algorithm, which relies on independent classified regions making it an excellent candidate for parallelization.