Road Map Accuracy Evaluation: Road Map Accuracy Evaluation Shashi Shekhar Max Donath Pi-Ming Cheng Weili Wu Research Project Team Meeting (A New Approach to Assessing Road User Charges) Nov. 7th, 2001


Motivation: Motivation Evaluation of digital road map databases To meet requirements of road user charge system: accuracy, coverage Recommend a cost-effective approach Develop the content and quality requirements For digital GIS road maps Each GIS dataset can contain various errors Failure to control and manage error Limit or invalidate GIS applications


Example Requirements: Example Requirements TIGER Accuracy Improvement Project (11/2/2001) Target Date - 2010 Goals: Correctly place a mobile GPS-equipped computer On correct side of street 100 percent of the time In correct relationship to legal boundaries 100 percent of time


Example Requirement 2: Example Requirement 2 Source: Forkenbrock, Hanley, Tech. Paper 4 (Nov. 2001), GPS Accuracy Isues Related to the New Approach to Assessing Road User Charges Applications: Assessing road user charges Congestion pricing, lane pricing Roadmap wish list Positions - lanes, roads Attributes - classification, political jurisdiction Accuracy wish-list Positional accuracy - 1-2 meter for lanes, 30 meter for roads Assumes - Road separation less than 30 m is rare. “Can current GPS ... and GIS road files promise 30 m accuracy?”


Understanding Requirements: Understanding Requirements Which map accuracy? Positional accuracy - horizontal, vertical Other - attribute accuracy - not specified What is positional accuracy (e.g. 30m) ? Worst case => error is always < 30m Statistical, e.g. median, 90th-percentile What is the positional accuracy budget for roadmaps? = Total positional accuracy budget - GPS accuracy budget Less than 30 m GPS accuracy depends on location, weather, … Roadmap accuracy should be higher where GPS accuracy is lower!


Close Road Pair : Close Road Pair Separation may be << 30 meter


Outline: Outline Motivation Background Accuracy of Spatial Database Related Work Map accuracy standards Accuracy Assessment Methodologies Our Approach Framework Preliminary results Challenges


Roadmap Sources: Roadmap Sources Sources for navigable digital road maps Public sector State: e.g., State DOT base map Federal: TIGER file, USGS Private Navigable maps: Tele Atlas, NavTek, GDT, PC Miler Cartographic: AAA, Rand McNally


Road Map Components: Road Map Components Position latitude, longitude, altitude for intersections, shape points center line for road segments Attributes Route attribute (name, type) Topology Route segment (direction, type, restrictions) Routing attributes (intersections, turn restrictions) Not widely available position of lanes, political jurisdiction


Definitions: Definitions Accuracy Closeness of estimates to true values (or values accepted to be true) the accuracy of the database may have little relationship to the accuracy of products computed from the database Precision number of decimal places (significant digits) in a measurement Common practice: round down 1 decimal place below measurement precision


Components of Map Accuracy: Components of Map Accuracy Source: Chrisman “Spatial data are of limited accuracy, inaccurate to some degree, the important questions are: How to measure accuracy? How to track the way errors are propagated through GIS operations?” Components of Data Quality: positional accuracy attribute accuracy logical consistency completeness lineage


Positional Accuracy - Definition: Positional Accuracy - Definition The closeness of location (coordinates) information to the true position Measures of positional accuracy Paper map - one line width or 0.5 mm About 12 m on 1:24,000, or 125 m on 1:250,000 maps RMS error 90th percentile, 95th percentile Components of positional accuracy Horizontal, Vertical


Framework to test positional accuracy: Framework to test positional accuracy Compare with a reference of higher accuracy source find a larger scale map use the Global Positioning System (GPS) use raw survey data Use internal evidence Indications of inaccuracy: Unclosed polygons, lines which overshoot or undershoot junctions A measure of positional accuracy: The sizes of gaps, overshoots and undershoots Compute accuracy from knowledge of the errors By different sources, e.g 1 mm in source document 0.5 mm in map registration for digitizing 0.2 mm in digitizing


Attribute Accuracy: Attribute Accuracy The closeness of attribute values to their true value Measures depend on nature of the data measurement error for continuous attributes (surfaces) e.g. elevation accurate to 1 m categorical attributes such as classified polygons gross errors, such as a polygon classified as A when it should have been B, e.g. land use is shopping center instead of golf course Framework to test attribute accuracy Create a a misclassification matrix: Ideally, all points lie on the diagonal of the matrix


Logical Consistency: Logical Consistency Internal consistency of the data structure Particularly applies to topological consistency Examples: Is the database consistent with its definitions? If there are polygons, do they close? Is there exactly one label within each polygon? Are there nodes wherever arcs cross, or do arcs sometimes cross w/o forming nodes? Do road-segments meet at intersections?


Completeness: Completeness The degree to which the data exhausts the universe of possible items Up to date Vs. Complete Examples: Are all possible objects included within the database? Does the digital map cover all new developed area?


Lineage: Lineage A record of the data sources and of the operations which created the database Examples: How was it digitized, from what documents? When was the data collected? What agency collected the data? What steps were used to process the data?


Problem Definition: : Problem Definition: Given: A GIS roadmap dataset and a Gold Standard Definition of accuracy Find: Spatial Accuracy of the given GIS dataset Objectives: Fair, reliable, tamper-proof, low cost Constraints: Gold-standard accuracy is better than GIS dataset accuracy


Outline: Outline Motivation Background Accuracy of Spatial Database Related Work Map accuracy standards Accuracy Assessment Methodologies Our Approach Framework Preliminary results Challenges


Related Work: Related Work Standards Interpreting Reported Accuracies Tools and Methodologies


Accuracy Standards: Accuracy Standards 1947 US National Map Accuracy Standards (NMAS) 90% of the tested points have errors 1:20,000 Threshold = 1/50 inch for scale < 1:20,000 Q? "How far out are the 10%?" "Where are the 10%?" e.g. all of the 10% point off by several inches and are in one road Am. Soc. for Photogram. And Remote Sensing (ASPRS) 3 different thresholds (class A, B, C) for each scales Dozen scales or so US National Standard for Spatial Data Accuracy (NSSDA) 95 percent of points have errors < threshold Relates to RMS error for normal distribution British Standard RMS error


Etak Accuracy Assessment: Etak Accuracy Assessment June 1999 Announcement (www.etak.com/News/newmap.html) Claims: Conforms to National Map Accuracy Standards (NMAS) 70% of US Population (1.6 Million miles) at 1:24,000 scale Another 25% of US Population at 1:100,000 scale Geo-coding - 98% match rate Interpretation 1 NMAS requires 90th percentile of error = 1/50 inch 40 feet (12.2 meters) at 1:24,000 scale 166 feet (51 meters) at 1:100,000 scale Interpretation 2 70% population = Metropolitan areas Another 25% population = Small towns TIGER has 8.5 Million miles of roads Roads corrected are about 1/5th of TIGER roads!


TIGER file Accuracy Assessment: TIGER file Accuracy Assessment http://www.census.gov/geo/www/tiger/ Report: John S. Liadis, TIGER Operations Branch , Geography Division Findings: Tested 6800 points across 8 sites, multiple sources Mean error = 281 feet (about 90 meters) Median error = 166 feet (about 50 meters) Errors vary across locations (median from 30m to 160m) Errors vary across sources (median from 32m to 350m) 90th percentile errors (NMAS) are much worse! 110m - 400m across different sources


GPS TIGER Accuracy Assessment Tool: GPS TIGER Accuracy Assessment Tool GPS TIGER Accuracy Analysis Tools (GTAAT) Calculates the distance and azimuth difference Between the GPS collected point and the equivalent TIGER point Indicated Accuracy of some Popular Digital Map Statistics approach Visualization approach Goals for TIGER Accuracy Improvement Project (11/2/2001) Correctly place a mobile GPS-equipped computer On correct side of street 100 percent of the time In correct relationship to legal boundaries 100 percent of time


GPS Tracks Vs. Road Maps: GPS Tracks Vs. Road Maps Visualization Approach Tiger-based Map USGS Digital Map


GTAAT Workflow Diagram: GTAAT Workflow Diagram


GTAAT Process Diagram: GTAAT Process Diagram


GTAAT Report: GPS Data Cleaning: GTAAT Report: GPS Data Cleaning Post process collected GPS coordinates Selective availability of the GPS signal GPS satellite clock error Ephemeris data error Tropospheric delay Unmodeled ionospheric delay Differential corrections in post processing Remove common error Both the reference and remote receivers Do not correct multi-path or receiver noise Trimble’s Pathfinder Office 2.51 Software used Require downloading data from a GPS base station A local station is available


GTAAT: GPS Source/Operation: GTAAT: GPS Source/Operation (Red number: source code not used in the source-by-source analysis) Collected GPS anchor points by Sources or Update Operation


GTAAT: Ranking of road map quality: GTAAT: Ranking of road map quality Median variance by source: median distance difference of operations(or source) of GPS and TIGER feature


Accuracy Assessment in Road Map: GTAAT Statistics Approach Test site: Windham County, VT (50025) Result of distance by census Accuracy Assessment in Road Map


Accuracy Assessment in Road Map (2): GTAAT Statistics Analysis: Site-by-Site Comparison Test site: Maricopa County, AZ (04013) Result of distance by tract Accuracy Assessment in Road Map (2)


Limitation of Related Works: Limitation of Related Works Limited to positional accuracy and lineage Did not evaluate attribute accuracy, completeness Position accuracy measure is limited No separation of lateral and longitudinal error lateral error affect road determination longitudinal error may be administrative zone determination Not scalabile to road network Point to point comparison is limited and slow Did not model GPS accuracy GPS accuracy = f (location, weather)


Outline: Outline Motivation Background Accuracy of Spatial Database Related Work Map accuracy standards Accuracy Assessment Methodologies Our Approach Framework Preliminary results Challenges


Our Approach: Our Approach Evaluate total system (GPS + roadmap) Road classification accuracy Evaluate road map component Positional accuracy Attribute accuracy


Road Classification : Road Classification Garmin error circle on USA toposheet maps (Source: Garmin) Risk of incorrect map matching


Road Classification Accuracy: Road Classification Accuracy Road classification depends on: Positional accuracy, Attribute accuracy, Completeness Road Classification Accuracy Measures: Miles – misclassification Number of road pair closer than threshold (30m) Probability of mis-classifying road for a GPS reading


Methodology: Methodology Digital road map data Site selection for mis-classification accuracy Gather gold Standard value (e.g., site field Survey, Aerial images) Statistical analysis Visualization tool Assess mis- classification accuracy


Positional Accuracy: Positional Accuracy Lateral accuracy Definition: Perpendicular (RMS) distance from GPS reading to center line of road in road map. Longitudinal accuracy Definition: horizontal distance from GPS reading to corresponding Geodetic point. Comment: Lateral error is more important when closest road is parallel Longitudinal error is important for other case


Positional Accuracy Measures: Positional Accuracy Measures Point-based: Input – pairs of corresponding points on road map and gold standard Output – RMS (distance between pairs) Comment – scalability to large road networks; - need to stop GPS vehicles at geodetic points - expensive and dangerous Line-string based: Lateral error – RMS (shortest distance of GPS reading to center line of corresponding roads)


Methodology: Methodology Digital road map data Site selection 1 Gather GPS track by driving vehicle Subsets of road maps GPS logs Assess positional accuracy Statistical analysis Visualization tools Overlay of road map and gold standard


Attribute Accuracy & Completeness: Attribute Accuracy & Completeness Interesting Attributes: Economic attributes - administration zone(s), congestion zones Route attribute - name, type, time restrictions Route segment - direction, type (e.g. bridge), restrictions Routing attributes - intersections, turn restrictions Definition of Attribute Accuracy: Pr[Value of an attribute for given road segment is correct] Definition of Completeness: Pr[a road’s segment is in digital map] Pr[attribute value is not defined for a road segment] Scope: Small sample


Methodology: Methodology Digital road map data Site selection for Attribute accuracy Site selection for completeness Gather Gold Standard values (e.g., site field Survey, aerial image) Assess attribute accuracy and completeness Statistical And visualization


Core Activities: Core Activities Acquire digital road maps Select test sites Gather gold standard data for test site GPS tracks, Surveys, etc. Complete subsets of road maps for test sites Compute accuracy measures Statistical analysis Visualization


Progress: Progress Acquire digital road maps Obtain Basemap (1997, 1999) from Mn/DOT Purchasing two counties (Hennepin and St. Louis) from Etak/Tele Atlas Gather gold standard data for test site Acquired a sample GPS track from field survey Visualization Develop Java based map access software Read digital map sources and GPS data Display overlay of these two sources Visualize error


Map Acquisition: Map Acquisition Etak/Tele Atlas map for Twin Cities (7 county metropolitan area)


Example Test Site: Example Test Site Blue line = Highway 7 Red Square = area of interest in next few slides Western suburbs south of lake Minnetonka


JRG GPS tracks Vs. Roadmap: JRG GPS tracks Vs. Roadmap GPS Track for Hwy 7 West Bound GPS Track for Hwy 7 East Bound


Trimble GPS tracks Vs. Roadmap: Trimble GPS tracks Vs. Roadmap GPS Track for Hwy 7 West Bound GPS Track for Hwy 7 East Bound


Comparing GPS tracks: Comparing GPS tracks GPS Tracks for Hwy 7 West Bound GPS Tracks for Hwy 7 East Bound


Outline: Outline Motivation Background Accuracy of Spatial Database Related Work Map accuracy standards Accuracy Assessment Methodologies Our Approach Framework Preliminary results Challenges


Other Challenges: Other Challenges Center-line representation of roads Two-dimensional maps Multi-level roads Altitude issues Map matching


Challenge Due to Road Representation: Challenge Due to Road Representation Center-line is a common representation of roads Closest center-line used to map GPS reading to a road in the road-map This may be wrong even for perfect roadmap, perfect GPS


Two Dimensional Maps: Two Dimensional Maps Road Separation Map Separation


Map Matching: Map Matching Integration of GPS/GIS: