DOC PREVIEW
SWARTHMORE CS 97 - Bridge Detection from Elevation Data Using a Classifier Cascade

This preview shows page 1 out of 4 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 4 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 4 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

Bridge Detection from Elevation DataUsing a Classifier CascadeAnthony [email protected] [email protected] and similar non-obstructing featuresinhibit correct flow routing on high-resolutiondigital elevation models because their apparentelevation does not reflect the elevation at whichwater may pass underneath them. Our goal is toidentify such features using the elevation dataso that flow-routing algorithms may find pathsunder them correctly. We use an algorithmbased on Viola and Jones’ object-recognitionsystem. Simple filters are applied in sequenceto efficiently narrow the search space down toa final set of likely candidate features. This pa-per presents a successful system for identifyingbridges that can be fairly easily integrated intoexisting GIS systems.1 IntroductionNew hi-res terrain scanning techniques such as laser al-timetry (lidar) have greatly expanded the accuracy ofGIS. The improved resolution has introduced many newdetails into digital elevation maps; many such features,however, hinder analysis of the underlying bare-earthterrain. One of the most important problem featuresare bridges. From the air, a bridge appears as a solidridge, but, in reality, water can pass beneath it. Whilea raw data dump may contain some points that are visi-ble underneath a bridge, current preprocessing techniqueswill tend to remove these, leaving a solid obstacle onthe processed digital elevation model (DEM). This con-fuses flow-routing algorithms, which must flood terrainor search for convoluted detours to escape the local min-imum created by the presence of the false ridge. Ourgoal is to identify bridges and similar features, such asdrainage tunnels, on digital elevation models, so that wa-ter flow can be routed through them. Appropriate flowrouting can be accomplished with minimal modificationof existing algorithms by simply cutting through a bridgeonce it is marked out.1.1 Related WorkSithole and Vosselman (Sithole and Vosselman, 2006) de-scribe a system for the geometric recognition of bridgesas part of a general system for creating bare-earth datafrom raw lidar input. Their system looks for features thatdrop off sharply on two sides and fade smoothly into thesurrounding terrain on the others. Calculating and ana-lyzing bounding polygons for terrain features, however,is computationally intensive.Our algorithm is inspired by computer vision researchby Viola and Jones (Viola and Jones, 2002). Their sys-tem utilizes a “cascade” of simple filters, each of whichis sensitive to a specific pattern. The algorithm reliablyrecognizes faces in real-time video. They also suggest atechnique for fast computation of rectangle sums, calledthe integral image method. Each pixel in the integral im-age is the sum of the values of the pixels above and tothe left of its location in the original image, which allowsany rectangle sum to be computed with only four addi-tion operations if the integral image already exists. Thistechnique allows us to quickly calculate statistics for sub-sections of the map. For example, finding the average el-evation in a ten-by-ten square area conventionally wouldrequire adding together one hundred values; with the inte-gral image method, we need only access four values (thecorners of the box) to get the area sum.2 Methods2.1 AlgorithmOur system is an implementation of the cascade conceptof Viola and Jones in a novel domain. A sliding win-dow moves over the map, examining small sections ofthe terrain in sequence. The window may move one orseveral pixels at a time: this is the step size of the win-dow. A larger step size decreases runtime significantlybut also decreases accuracy. Empirically we determinedthat a step size of 2 pixels did not result in a significantdecrease in accuracy.Each window is passed through a series of filters. Afilter is a function that evaluates the pixels within the win-dow statistically or geometrically and decides to accept orreject the slice. To save storage space, the algorithm ap-plies all the filters to each window in order before mov-ing on to the next; this way, no intermediate candidatelists (which could be quite large) are stored in memory.If any filter rejects the slice, it ceases to be relevant andthe window moves to the next target. Like in the Viola-Jones algorithm, the collective action of the filters makesup for their individual inaccuracy. It is important for eachindividual filter to have a very low rate of false negatives,so that they do not reject good candidates prematurely.In order to accommodate bridges of varying sizes, wemake several passes over the map, changing the scaleof the window each time. One can reasonably expectbridges to be at least one car lane and no more than adozen lanes wide, and filters must take in some of the sur-rounding area for comparison as well. We are currentlyusing window sizes of 100, 150, 200, 250, 300, and 400feet in an attempt to accommodate all reasonably-sizedbridges.2.2 FiltersWe have implemented several filters to detect bridge-likefeatures. Since the overall goal is to aid hydrologicalmodeling, we focus on discovering terrain elements thathave a strong effect on existing flow-routing algorithmsand trying to identify them as bridges.1. The high gradient filter accepts an image if at leastten percent of the pixels in the filter window havea gradient above a certain threshold. Currently thisthreshold is 2.4 feet of elevation per 10 feet of trans-lation (empirically determined), but we may adjustit in the future and analyze how it affects our re-sults. This filter is designed to find the steep edgesof bridges.2. The flood fill filter accepts an image if at least thirtypercent of the pixels in the filter window were flood-filled by a flow-routing algorithm. This filter is de-signed to capitalize on the fact that bridges in gen-eral, and particularly the bridges that we want to re-move to do correct flow routing, cause flood fillingalong their length.3. The minimum fill depth accepts an image if there isat least one pixel in the window that was flood-filledhigher than 8 feet. This filter is designed to focus onareas that are significantly problematic for hydrolog-ical modeling.4. The low gradient filter accepts an image if at leasttwenty percent of the window area is low gradientpixels, where the low gradient threshold is 0.5 feetof elevation per 10 feet of translation. This filter isdesigned to look for the flat area of the bridge


View Full Document

SWARTHMORE CS 97 - Bridge Detection from Elevation Data Using a Classifier Cascade

Documents in this Course
Load more
Download Bridge Detection from Elevation Data Using a Classifier Cascade
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Bridge Detection from Elevation Data Using a Classifier Cascade and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Bridge Detection from Elevation Data Using a Classifier Cascade 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?