Brian Graff

Inferring Bridges from Digital Cartographic Sources Using ArcInfo

The location of bridges is of great importance to military planners on both a strategic and tactical level. Given the importance of bridges, it is crucial to have both the locations and attributes of bridges in a Geographic Information System (GIS) to facilitate military planning and operations. However, global digital data on bridges is either very sparse or nonexistent. This paper will present a methodology for inferring bridges from digital cartographic sources using ArcInfo.

1. INTRODUCTION

The transportation layer in a Geographic Information System (GIS) is one of the most important thematic layers for military planning. The transportation network is significant to military operations because it facilitates communications and the movement of troop units and supplies. Maneuverability is difficult in close terrain, such as forests, swamps, hills, and mountains. In such terrain, troop and supply movement is highly restricted to the road network. Thus, roads are even more significant in close terrain than in more open types of terrain (FMFRP 0-51, 1990). Another location where troop movement is restricted or concentrated is where a road crosses a significant body of water - i.e. a bridge.

Bridges played a significant role in many military campaigns throughout history. In the U.S. Civil War, the Union Army sustained heavy casualties at Burnside Bridge during the battle at Antietam (Sears, 1983). In World War II, Allied airborne units were sent into Normandy the night before the June 6, 1944 invasion to capture and hold bridges that the Allies would need in order to push forward their beachhead. In an attempt to delay Axis reinforcements from reaching the Normandy beachhead, the U.S. Army Air Force targeted and destroyed bridges behind enemy lines (D'Este, 1983). In the Persian Gulf War, the Coalition air force targeted bridges within the first 48 hours of the air campaign (Department of Defense, 1992).

Thus, bridges are highly significant to military operations. However, global digital data on bridges is either very sparse or non-existent. There are currently several digital cartographic data sets that contain bridge information. On a global scale, the 1:1 million Digital Chart of the World (DCW) contains road bridges as both point and line features. However, due to the small scale, only the most significant bridges are in the DCW. The Defense Mapping Agency (DMA) also produces a 1:50,000 digital product called Interim Terrain Data (ITD), which stores bridges as point and line features. However, the ITD does not exist for large portions of the world.

2. OBJECTIVES

The problem, therefore, is how to quickly build a GIS database that contains bridges over an area of interest. The U.S. Army Corps of Engineers Topographic Engineering Center (TEC) is working on this problem as part of the Advanced Research Projects Agency's sponsored Terrain Feature Generator (TFG) Program and TEC's internal Digital Terrain Data Generation (DTDG) work. The traditional approach is to manually digitize and attribute bridges from existing hardcopy maps or imagery. However, this is a time-consuming task.

The option that TEC has pursued is to use a variety of digital cartographic sources to infer the location of bridges. According to Webster's New Collegiate Dictionary, to infer is "to pass from one proposition, statement, or judgment considered as true to another whose truth is believed to follow from that of the former." For example, if it is true that the average rainfall over a given region is less than 5 inches a year, it may be inferred that the region is a desert. This may or may not be correct, but it is one of several possible inferences. As more facts are established for the region, the inference can be strengthened or changed.

An analyst could infer the location of bridges by using the following methodology. Assume that the analyst is given a map that contains only two thematic layers: 1) transportation and 2) surface drainage. Also assume that bridges are not identified on the map. If asked to infer the potential locations of bridges, the analyst would point to locations where roads crossed drainage. If a road crosses a river, it can be inferred that a bridge should exist at that location. How strongly does the analyst feel that the bridge really exists? The inference is stronger if a 4-lane highway crosses a major river, than if a foot trail crossed an intermittent stream. Thus, the strength of the inference is based on the type of road and river. The location of the bridge would be as accurate as the spatial accuracy of the transportation and drainage network.

It is TEC's goal to automate the bridge-inferencing paradigm described above by using a GIS. ArcInfo is used to analyze existing digital cartographic sources in much the same way as the analyst does.

3. METHODOLOGY

To automate the bridge-inferencing process using ArcInfo, it is necessary to have a digital road coverage and a digital surface drainage coverage. For the purposes of this prototype, the assumption was made that the ITD does not exist. If the ITD exists, there is no reason to infer the locations of bridges since the ITD contains ample information about bridges. Thus, the ITD road and surface drainage layers were not used in the bridge extraction process. The ITD was used to assist in the verification portion of the prototypes.

The digital data sets used for the study include the road network for DCW, drainage extracted from DMA Digital Terrain Elevation Data (DTED) Level 1, and a road network created by semi-automated map parsing of a 1:50,000 Arc Digitized Raster Graphic (ADRG). The procedures used to extract the drainage network from DTED and to extract the roads from the ADRG are described later in this paper.

TEC tested two combinations of road and surface drainage coverages:

Case 1. DCW roads with drainage automatically extracted from DTED Level I; and

Case 2. Roads extracted from map parsing a 1:50,000 DMA ADRG with drainage automatically extracted from DTED Level I.

3.1 Rationales for Cases 1 and 2

Case 1 Rationale

The justification for using the DCW is that worldwide coverage of roads exists. The mere availability of worldwide coverage of digital roads is a compelling reason for using the DCW roads in order to get a rough estimate of bridge locations. The argument for using drainage automatically extracted from DTED Level 1 is that the drainage network will be much more dense than the drainage network in the DCW. The automated drainage extraction process is straightforward, quick, and well established in the literature. Additionally, there is almost worldwide coverage of DTED Level 1, so that drainage networks can be extracted for almost any location.

Case 2 Rationale

Despite the advantages of worldwide coverage of the DCW, there are some limitations. First, due to the small scale of the DCW, only the most significant roads are maintained - i.e. the road network is sparse for larger scale applications. Also, while the coordinate accuracy of the DCW is fine at a small scale, it is crude at larger scales. The roads are quite generalized. Thus, a digital vector road source that is denser and spatially more accurate than the DCW is desirable.

DMA 1:50,000 Topographic Line Maps (TLM) are rich in road information. It would be desirable to have vector representation of these roads to use for bridge inferencing. The traditional approach is to digitize the roads manually and then attribute the resulting vectors. However, digitizing is labor intensive and time consuming. Another option is to scan the TLMs or to gain access to DMA ADRGs and then try semi-automated map-parsing techniques to extract the roads. Automated or semi-automated map parsing is difficult if the goal is to extract and attribute every single feature on a hardcopy map. However, if the goal is limited to extracting a small subset of distinctive features (in terms of color and geometry) with minimal attribution, then map parsing may be more desirable than digitizing. A particular advantage of map parsing from an ADRG is that the resulting roads will already be georeferenced.

3.2 Steps for Automated Extraction of a Drainage Network from a Digital Elevation Model

A full description of how a drainage network can be extracted from a DEM is beyond the scope of this paper. ArcInfo's GRID package provides this capability and detailed steps are fully described in the GRID documentation. Although GRID was not used to extract drainage for this study, the steps TEC used were the same. Briefly, the steps for extracting a drainage network from a DEM are as follows:

1. Create a flow direction grid from the Digital Elevation Grid.

2. Detect and fill artificial sinks.

3. Create Flow Accumulation Grid.

4. Threshold the Drainage Network.

5. Calculate Shreve Stream Order for Thresholded Drainage Network.

6. Perform Raster-to-Vector Conversion of Drainage Network and store drainage network as an ArcInfo coverage. The Shreve Stream Order will be an attribute for each arc in the drainage network coverage.

The following diagram shows a portion of a drainage network with the Shreve stream order as an attribute:

All links with no tributaries are assigned a link of magnitude 1. Magnitudes are additive downslope. When two links intersect, their magnitudes are added and then assigned to the downslope link. Because the orders are additive, they are sometimes referred to as magnitudes instead of orders. The magnitude of a link is the number of upstream links (Esri, 1994).

3.3 Semi-automated Map Parsing from an ADRG

TEC used Loral's Autographics commercial off-the-shelf software in order to extract the roads from the ADRG. Autographics is an automated feature extraction system for preparing raster geographic databases from hardcopy map sources. Autographics accepts as input a raster file produced by scanning a hardcopy map. The most common input raster files are 24 bits per pixel (RGB), and the specific image file format used by Autographics is SunRaster. Once the Sun Raster file is imported, the user proceeds to train the software's neural network to recognize the various thematic categories. Once the training is over, the image is classified automatically. The output raster files are always 8 bit. These raster files can contain multiple thematic layers, or layers can be broken apart and stored as separate raster files. For example, it is possible to output the roads separately from contours (Autographics User's Guide, 1995).

Training the neural network for roads took approximately 15 minutes. Only the roads colored in red were selected for training, since they were the major roads and the only bright red features on the map. The output raster file was loaded into ArcInfo GRID and minor raster editing was performed on the road grid using the ARCSCAN tools. Noise was removed using the Clump removal tool. Small gaps in the roads were closed manually. Total cleanup time was a little less than one hour. ArcInfo's GRIDLINE command was used to perform the raster-to-vector conversion. A field was added to the AAT called RDLNTYPE and filled with the value 1. For this study, all roads were weighted the same.

3.4 Process for Extracting Bridges from Combined Road and Drainage Coverages

TEC has prototyped bridge extraction for both Case 1 and Case 2. Using ArcInfo topology and terrain knowledge, TEC has written an ArcInfo Arc Macro Language (AML) program together with an INFO program to determine where drainage and roads cross. The locations where these crossings occur are tagged as potential bridges.

Figure 1 shows a portion of a combined road/drainage coverage where a DCW road crosses drainage extracted from DTED Level 1. This combined coverage is named INTERS. The arcs are labeled with their INTERS-IDs and the nodes are labeled with their NODE-IDs. In this diagram, the road crosses the drainage at NODE-ID 100. The arrows on the arcs indicate the from node-to node orientation of the arcs. For example, the arc with INTERS-ID 2000 has a #FNODE of 101 and a #TNODE of 100. NODE-ID 100 is the #FNODE of the drainage segment INTERS-ID 60.

Table 1 shows the Arc Attribute Table (AAT) for the INTERS coverage. The AAT contains the records for the four arcs shown in Figure 1. Every arc has a unique ID. The #FNODE and #TNODE IDS are also shown in the AAT. INTERS.AAT has two attributes: RDLNTYPE and SHREVE. RDLNTYPE is a field from the DCW road coverage. A value of 1 indicates that the arc is a road. SHREVE is the Shreve Order Number. If SHREVE is not equal to 0, then the arc is a drainage arc. In our specific case, INTERS-ID 1000 and INTERS-ID 2000 are roads and INTERS-ID 50 and INTERS-ID 60 are drains.

Table 2 shows the Node Attribute Table (NAT) for the INTERS coverage. The NAT corresponding to this diagram contains just one record - NODE-ID = 100. The NODE-ID field is redefined to be also named #FNODE and #TNODE. Thus, it is possible to link INTERS.AAT and INTERS.NAT by NODE-ID. Four additional fields have been added to the NAT:

1) NUM_ROAD - will contain a count of the number of road arcs that pass through that specific node.

2) NUM_DRAIN - will contain a count of the number of drainage arcs that pass through that specific node.

3) HIGH_SHREVE - will contain the highest SHREVE code of an arc to pass through that specific node.

4) BRIDGE - will contain a code indicating whether or not that specific node is tagged as a bridge.

Pseudocode for INFO Bridge Extraction Program

The actual procedure to locate and attribute the bridges is programmed in INFO (which runs inside an AML). The INFO code will not be given in this paper. Rather, a pseudocode description of the approach is provided.

 

For every node in the INTERS.NAT, set NUM_ROAD, NUM_DRAIN, 
BRIDGE, and HIGH_SHREVE to 0

Relate INTERS.AAT and INTERS.NAT by #FNODE
(This means that the INTERS.AAT is linked to the INTERS.NAT
by #FNODE; Remember that NODE-ID in INTERS.NAT has been REDEFINED
to #FNODE)


Begin Loop
        Read arc record from INTERS.AAT
        IF arc is ROAD
                Increment NUM_ROAD in INTERS.NAT
        ENDIF
        IF arc is DRAINAGE
                Increment NUM_DRAIN in INTERS.NAT
        ENDIF
        IF arc has a SHREVE Stream Order
                IF SHREVE for the arc is GT HIGH_SHREVE for the #FNODE
                        set HIGH_SHREVE eq to SHREVE in INTERS.NAT
                ENDIF
        ENDIF
End loop when last record from INTERS.AAT is read

Relate INTERS.AAT and INTERS.NAT by #TNODE
(This means that the INTERS.AAT is linked to the INTERS.NAT
by #TNODE; Remember that NODE-ID in INTERS.NAT has been REDEFINED
to #TNODE)


Begin Loop
        Read arc record from INTERS.AAT
        IF arc is ROAD
                Increment NUM_ROAD in INTERS.NAT
        ENDIF
        IF arc is DRAINAGE
                Increment NUM_DRAIN in INTERS.NAT
        ENDIF
        IF arc has a SHREVE Stream Order
                IF SHREVE for the arc is GT HIGH_SHREVE for #TNODE
                        set HIGH_SHREVE eq to SHREVE in INTERS.NAT
                ENDIF
        ENDIF

End loop when last record from INTERS.AAT is read

SELECT INTERS.NAT
RESELECT NODES WHERE NUM_DRAIN GE 2 and NUM_RD GE 2
SET BRIDGE = 1     (Tag as Lower Order Bridge) 
RESELECT NODES WHERE HIGH_SHREVE GE 5
SET BRIDGE = 2     (Tag as Higher Order Bridge since road
                        crosses a stream of  Shreve > 5)

4. TEST AREA

The choice for a suitable test area was based on several criteria:

a) The existence of DTED Level I (post spacing of 3 arc seconds).

b) The existence of ADRG (1:50,000 DMA Topographic Line Map).

c) The existence of DCW roads.

d) The existence of ITD (to verify the results).

The test area for the prototype covers a single 1:50,000 DMA Topographic Map Sheet in South Korea. The sheet number is 3319-II from Map Series L752. This sheet spans approximately 27 kilometers in the east/west direction and approximately 28 kilometers in the north/south direction. Thus, the total square kilometers covered by the test area is roughly 756 square kilometers. The lower left coordinate is 36 degrees 30 Minutes N, 128 degrees 6 minutes E and the upper right coordinate is 36 degrees 45 minutes N, 128 degrees 24 minutes E.

This map sheet was selected due to the ample network of: a) 1- and 2-lane all weather, hard surface roads; b) 1- and 2-lane all weather, loose surface roads; and c) 1- and 2-lane dry weather, loose surface roads.

The hydrology represented in this area is quite distinct also. Several moderate size rivers are located on this sheet. The largest river, the Naktong Gang, is 600 meters wide at its widest point. There are several other minor rivers that range from 100 - 400 meters in width. The topographic relief in the area is such that numerous small tributaries flow into the larger rivers.

5. RESULTS

The results from Case1 and Case 2 were verified against the point and line bridges found in the ITD. Point coverages were created from the nodes tagged as bridges. A 1/2-mile radius buffer was placed around each inferred bridge, and the ITD bridges that fell within this radius were considered a match. The results for both cases were favorable.

Case 1 results: Table 3 shows the results for Case 1. It is interesting to note that the DCW has no bridges over this area at all. In all of South Korea there are 23 linear bridges and 5 point bridges in the DCW. On this sheet alone, the ArcInfo procedure inferred 19 bridges. One inferred bridge did not have an ITD match. The hardcopy map was inspected and the map, in fact, had the bridge. The bridge was missing from the ITD.

                A. Total Number of DCW Bridges on Sheet 3319-2:         0 
                B. Total Number of Inferred Bridges:                    19
                C. Total Number of Higher Order Bridges:                4
                D. Total Number of Bridges with ITD Match:              18
                E. Percent Inferred Bridges with ITD Match:             94%
                F. Percent Inferred Bridges with 1:50,000 Map Match:    100%

Case 2 results: Table 4 shows the results for Case 2. The number of bridges found using the map-parsed roads from the ADRG instead of the DCW roads has increased from 19 to 95. This was expected since the road network extracted from the ADRG was much denser than that from the DCW. Even though more bridges were found, the percentage that matched the ITD is down from 94% to 87%. Twelve inferred bridges did not match the ITD. In most cases, this is where a drain and a road parallel each other very closely and sometimes cross over each other - thus creating false bridges. This problem may be due in part to differences in the registration of the DTED and the ADRG. Also, the cartographic generalization of the ADRG could be a factor as well.

                A. Total Number of DCW Bridges on Sheet 3319-2:         0
                B. Total Number of Inferred Bridges:                    95
                C. Total Number of Higher Order Bridges:                25
                D. Total Number of Bridges with ITD Match:              83
                E. Percent Inferred Bridges with ITD Match:             87%

6. CONCLUSIONS AND RECOMMENDATIONS FOR FUTURE RESEARCH

The success of the ArcInfo prototypes for inferring the locations of bridges provided a proof of concept. The test cases showed that it is possible to reasonably infer the locations of bridges from a digital road coverage and a digital surface drainage coverage. Further work needs to be done to improve the inferencing process. Areas for future research include:

1. Developing better methodologies to attribute the inferred bridges. Currently the aml program attributes an inferred bridge as either a higher order bridge or a lower order bridge. A bridge is classified as lower order if it crosses a stream with a Shreve Stream Order less than 5. A bridge is classified as higher order if it crosses a stream with a Shreve Stream Order greater than or equal to 5. The selection of Shreve Stream Order of 5 as a breakpoint is rather subjective. Thus, work needs to be done to determine how the Shreve Stream Order affects the classification of a bridge as a major or minor bridge. It may be possible to use Shreve Stream Order to determine other attributes for the bridge - i.e. length. Higher order bridges are expected to be longer than lower order bridges. For example, a bridge crossing a river with Shreve Stream Order of 30, will probably be significantly longer than a bridge crossing a river with Shreve Stream Order of 1. Also, if the road coverage has attribute information, such as number of lanes, perhaps the width of the bridge can be inferred .

2. Developing a methodology to identify false bridges. In some cases, there were false bridges identified due to the close proximity of the road and drainage networks. A method needs to be found to detect these cases. The road and drainage network would meander back and forth across each other. In those situations false hits would occur. A method needs to be found to detect them. Perhaps a check of minimum distance between bridges could be performed. Checking the lengths of the arcs between bridges may be another possibility.

3. Calculating a measure of certainty about the inferred bridge (metadata): both spatially and thematically.

REFERENCES

Autographics User's Guide (Loral,1995), pp. 3-4

Cell-based Modeling with GRID (Esri, 1994), pp. 310-328

D'Este, Carlo, 1983. Decision in Normandy. (First Harper Perennial Edition, 1983), pp. 213-214.

Sears, Stephen, 1983. Landscape Turned Red: The Battle of Antietam. (Popular Library Edition, 1983), pp. 285-296.

U.S. Department of Defense, Final Report to Congress, Conduct of the Persian Gulf War, April 1992, pp. 124-126.

U.S. Department of the Navy, Fleet Marine Force Reference Publication (FMFRP 0-51), Small-Unit Leader's Guide to Weather and Terrain, 1990, pp. 3-27, 3-28

Webster's New Collegiate Dictionary, 1979, s.v. "infer."

Brian Graff, Cartographer
U.S. Army Topographic Engineering Center
ATTN: CETEC-TD-TD
7701 Telegraph Road
Alexandria, VA 22315-3864
Telephone: (703) 428-6071
FAX: (703) 428-6176
E-mail: bgraff@tec.army.mil