Bridge Detection By Road DetectionJeff [email protected] IntroductionIt is useful to be able to determine water flowpatterns over terrain. The raw data for this taskis usually collected via airborne laser range find-ing, or LIDAR. This yields a point cloud rep-resenting the uppermost surface of the terrain.This cloud is interpolated onto a grid whereeach grid cell represents a square portion of theearth’s surface and it’s value is the average hightof that portion. Water flow patterns can then becalculated by looking at the direction of greatestdescent from each cell.There is a problem, however, with local min-ima: cells from which there is no direction ofdescent. A common cause of this is bridges.The area over which a bridge passes shows up inthe digital elevation as being of a height greaterthan the surrounding terrain, but for the pur-poses of water flow it is not there. A water flowsimulation model will treat those grid cells asindicating a barrier, then, when there is in factno impediment to water flow. The goal of thisproject is to identify bridges to aid in the accu-rate determination of water flow patterns2 Past Attempts and Related WorkA common method for dealing with local min-ima is flooding. In this all grid cells, exclud-ing those at the edges of the grid, where thereis no lower adjacent cell are raised up to theheight of their lowest neighbor. Rep eating thiswill eventually rid the map of local minima.Identical results to this naive method can beachieved efficiently with a plane sweep algorithmusing topological persistence. (Edelsbrunner etal., 2000) Unfortunately, as Soille et. al. (Soilleet al., 2003) recognize, this loses information.Large flat areas, a common result of flooding,retain no information about their original lowpoints and do not provide information actualflow patterns. One can still determine a pos-sible flow pattern through it, but that patternmay be totally different from the true one.Soille et. al. were working with a very lowresolution (250m) grid elevation model to de-termine the water flow pattern for Europe andthe problems they ran into are somewhat dif-ferent from those encountered with higher res-olution data. When they encountered a localminimum, specifically, it was usually becausesome small stream or channel went undetectedwith the coarse sampling. Their replacement offlooding, carving paths from local minima to thenearest lower area, makes sense for dealing withthe missing channels but can of course get thingswrong. As the local minima in higher resolutiondata are much more likely to be products of hu-man terrain manipulation, generally in the cre-ation of roads, a system that tags and removesbridges ought to come closer to true water flowpaths than either flooding or carving.For last year’s senior conference, Manfrediand Pshenichkin (Manfredi and Pshenichkin,2006) used a series of classifiers to tag bridges.They had a series of simple criteria that a win-dow had to match to be tagged a bridge. Theywere able to detect many of the larger bridgesbut missed some smaller ones, as well as complexstructures such as highway interchanges. Theirsystem also had a large number of false positives,detecting vegetation and other small artifacts asbridges. They rightly point out, however, thatthere is not too much harm in removing themalong with bridges as they are also not reallythere from the perspective of water flow.One feature that they did not take advan-tage of is the tendency of bridges to be partof the road network. All of their classificationwork considered only the window that poten-tially contained the bridge. There has been somework on detection of of roads from LIDAR data(Clode et al., 2005), and while the final detectedroads may not be completely accurate, for thistask we don’t need perfection. Instead we justneed a rough idea of how likely a region is tobe part of the road network, which can then beinput to the bridge detection system.3 Bridge Detection via RoadDetectionFor this project I locate bridges in two stages.In the first I determine an approximate map ofthe road network, a map that should generallybe best in areas where the roads are in high re-lief. These areas correspond well to those wherebridges are likely, so it should be a well suitedmap for the task. Second I identify local min-ima that are near the computed roads in orderto tag road sections as bridges. Input consists ofa digital elevation model in the form of a grid offloats indicating hight. Output consists of fivesimilar models with floats indicating likelihoodof being a bridge, with calibration required forthe particular data set.3.1 Road DetectionRoads are places in the terrain that are flat. Anyflat area could be part of a road. Areas that arelinearly flat, however, are much more likely to beroads. These would be areas where lines in onedirection are flat while in other directions arenot. Finally, roads tend not to bend sharply,so if there is a road in a direction we treat gridcells in that direction as being more likely to bea road.This yields four indicators of bridge-likeness.All are computed on a series of cells represent-ing a potential road. For every cell c in the gridwe calculate 32 potential roads of a configurablelength running through that point. We then findwhich of those series of cells has the lowest av-erage change in steepness and call that the ‘b e stroad’ centered on that cell. We also find theset of cells representing a line perpendicular tothe best road and call that the ‘perpendicular’.Each indicator acts on one of these two roadsand yields a value attributed to c.1. Maximum gradient. For the best road, thelikelihood of it being actually a road is in-versely proportional to the greatest differ-ence between adjacent cells in the road.2. Average gradient. Like the previous, exceptthe average absolute difference is calculatedinstead of the maximum one.3. Maximum gradient of perpendicular. Thelikelihood of the best road being a road in-stead of just a cornfield is indicated by theunroadlikeness of the perpendicular. Thisis calculated as for the maximum gradient.4. Standard deviation of gradient. Even whennot level, roads tend to be flat. That is,while they might sometimes have high gra-dients the (root mean square) standard de-viation should be low.3.2 Local MinimaA maximally simple algorithm for determinationof local minima turns out to be quite effectiveas the data is not very noisy. For every gridcell, if no