GPS and GIS: Enhanced Accuracy in Map Matching through Effective Filtering of Autonomous GPS Points
Carstensen, Laurence W., Jr., Cartography & Geographic Information Systems
ABSTRACT. The development of the Global Positioning System (GPS), along with ever more powerful geographic information systems (GIS), has spawned the development of public safety applications. One of the most noteworthy of these applications is the Mayday system in which a motorist can call for roadside assistance at any time, day or night, without knowing his location, so that a service center can send assistance to the site of the call. Some of today's Mayday systems provide national coverage which, while impressive in scope, can cause problems in assuring the reliability required to enlist the loyalty of customers and the cooperation of local emergency personnel. Customers whose calls for assistance are not answered promptly, or frequent calls that result in long searches by emergency personnel taking them away from their posts and endangering others who need them, are potential pitfalls of Mayday systems. This paper looks at the effects of filtering autonomous GPS points to enhance the reliability of positions when matched to maps in GIS databases.
KEYWORDS. GPS, GIS, map matching, Mayday systems
Technology and Travel Services
with advances in technology afforded by geographic information systems (GIS) and the Global Positioning System (GPS), new products are being developed for both consumers and specialized markets. A large number of these applications fall within the arena of transportation and intelligent highway systems. Vehicle tracking, fleet management, emergency vehicle routing, incident and accident notification, and motorist assistance have all been reported in recent literature. Three major United States trade publications, GIS Worm (Fort Collins, Colorado), GeoInfosystems (Eugene, Oregon), and GPS Worm (Eugene, Oregon) regularly devote column and feature space to these developments. Common to these applications is the requirement for precise to semi-precise location of vehicles using on-board GPS receivers. This study addresses one of the components of accuracy in a map-matching environment.
A specific transportation-related GPS/GIS operation known as a "Mayday" system utilizes GPS receivers carried in vehicles to identify the location of a disabled vehicle to a dispatch center, allowing the vehicle's occupants rapid automated access to help when needed. The initial Mayday system in the United States was developed in the Denver area in December 1994 by NAVSYS (Krakiwsky 1996a). The system marked the first reported public use of GPS and cellular telephone service to provide positioning information in a large-scale project. Under the Colorado Mayday system (Lacey and Cameron 1995), drivers send their positions to a central dispatch center and receive rapid assistance in emergencies. Other systems offering local coverage areas are also on line. Rockwell (Seal Beach, California) and ADT (Irving, Texas) have introduced the Micro Tracker system. Other systems include PuSHME in the Seattle area, the Tele Trac roadside assistance system in Los Angeles, Chicago, Detroit, and Dallas/Fort Worth, and the Mayday Plus system in Minneapolis (O'Brien and Balogh 1996).
The first national Mayday system was Ford's RESCU system which debuted in Lincoln Continental automobiles in January 1996. Under this system, motorists can, with the push of a button, notify the service center (Westinghouse Security Systems (WSS)--Irving, Texas) of an emergency or a need for roadside assistance. After an attempt to speak with the caller and verify the call via cellular telephone, WSS contacts appropriate local authorities, based on the call. This system was field tested across the United States by a team of researchers from Westinghouse Electric Corporation (Baltimore, Maryland), Westinghouse Security Systems (Irving, Texas), Ford Motor Company (Dearborn, Michigan), and Virginia Tech's Department of Geography (Blacksburg, Virginia) during 1995. Success rates in vehicle location were over 96 percent and times for local dispatch were generally under 11 minutes (Car-stensen 1995, Krakiwsky 1996a).
In February 1996, General Motors (Detroit, Michigan) announced its On Star system which is available on Cadillac models beginning with the 1997 model. Along with emergency and roadside assistance services, the On Star system assists in certain navigation tasks, in collision notification, and other useful services for motorists. General Motors offers this service nationwide. In addition to these there are numerous companies in the Mayday service arena in Europe and Japan (Krakiwsky 1996b). The potential market for such devices is enormous, and early demand is running well above that expected in the U.S. market.
Components of a National Mayday System
The basic operation of a Mayday system is fairly straightforward. A coordinated sequence of events passes a distress message from a disabled vehicle through a service center to a local authority which assists the driver of the vehicle to rectify the problem. The basic flow and pertinent accuracy issues that must be addressed in each step are described below.
1. A call is initiated by the driver of a vehicle needing assistance. For national coverage, this step is dependent on the cellular telephone system to make a connection from any location in the U.S. to the service center. Though a majority of the U.S. is covered by cellular service, expecting that every call will get through is overly optimistic. Some areas, especially those with irregular terrain that undulates out of sight of cellular transmission towers, have spotty service, some very rural areas have no service at all, and even well served urban areas have system overloads at times, making connection difficult. Mayday applications have little control of this factor, but areas of low or no service are rapidly diminishing.
2. As a part of the call, the on-board GPS receiver sends a location point (along with a variable amount of data on the customer and the vehicle) to the service center. To reduce transmission time and complexity, and hence the probability of transmission error, a single GPS location (the most recent "accurate" location) is sent. Currently, all of Earth has sufficient GPS satellite coverage that 95 percent of points computed by a receiver fall within 100 meters of their true positions under open sky conditions. However, positions computed while moving in or sitting amongst obstructions often yield less accurate locations. Success in this step is subject to an accurate computation by the GPS receiver which is dependent on many factors (see details below).
3. The service center receives the call, identifies the customer, and, with the aid of a GIS, matches the GPS data to a digital highway map to determine the caller's location. Using a reverse process to that in address geocoding, this step involves a translation from a geographic coordinate to a street link or even to a specific address. Successful translation from geographic coordinates to familiar location units is critical as the GPS-provided latitude and longitude angles may be unfamiliar to the local personnel who must find the vehicle and provide assistance. While many people are aware that positions on Earth can be measured in latitude and longitude, none of us use them in day-to-day navigation. The "map-matching" step translates the caller's position into a familiar unit, a street name, a cross street or perhaps an address. In this stage of the process, there are two critical concerns:
* If we assume an accurate GPS coordinate from stage 2, then an accurate digital map database is critical. With proper indexing, a geographic information system can quickly search a massive national highway map to display any latitude and longitude position and its surrounding streets, but if the map underlying the system is poor, then even the most accurate point from the GPS may not appear near the correct street, causing the translation to fail and the assistance personnel to be sent to the wrong location.
* If we further assume that the digital highway map is accurate, then translation from a geographic coordinate to a street location must rely either on the map-reading savvy of the service center personnel, or, more appropriately, on a map-matching algorithm in the GIS itself. Many algorithms are possible that allow the GIS to arrive at a position and report it to the service center operator as an address, a street, and a set of cross-streets (e.g. vehicle is at 407 S. Main Street, between 4th and 5th Avenues). Allowing the GIS to perform the "map-reading" step should prove superior as it is quicker than map interpretation by the operator, and as Mayday calls on a national scale come mainly from areas unfamiliar to the service center personnel, it reduces the chance of error in reading names and address ranges from a screen view. Different algorithms may match the same point to different street locations, thus study of these is important to successful Mayday systems.
4. The service center uses its computer database to locate the correct provider of assistance and places a land-based call to that provider. This step depends on the selection of emergency numbers from a database after the provider area from which the call was placed has been identified. (For more information on this aspect of emergency services, refer to the National Emergency Number Association, Coshocton, Ohio). With a good map of providership jurisdictions in the GIS database, this step is, for most locations, simply a point in polygon algorithm. However, some service "areas" are very small and fragmented, and some occur on linear features only, making this step a bit more complex than it appears at first glance. For instance, in some communities, interstate highways might be served by the state police while surface streets are served by the city police, creating thin linear corridors of service which could easily be missed by a point-in-polygon algorithm using an imperfect GPS point or highway map.
5. A local dispatcher sends an assisting vehicle to the described location. Depending on the type of call, the assistance might be an ambulance, a police cruiser, or a tow truck. The local personnel drive to the map-matched GPS location to seek the vehicle. This search may depend solely on the expert knowledge of the local personnel, or GIS routing algorithms can be used to assist the provider in locating the incident more efficiently.
All these steps must be carried out (and, hopefully, quickly) before the driver of the disabled vehicle gets help. Each step provides research opportunities toward the improvement of existing Mayday services. This paper looks at the factors affecting stage 2 of the process; thus let us return to stage 2 and expand our knowledge of GPS accuracy and ways to enhance reported positions.
Basic GPS Point Accuracy
Global Positioning System positions are computed by determining the distance (range) from the receiver to three or four satellites with precisely known orbital locations. These ranges are then processed through a set of simultaneous equations to determine a location that best approximates the known values. The accuracy of a single point computed by a single GPS receiver therefore depends on several factors. Simply put, GPS ranging has an error budget. Individually, none of the items are large, but they accumulate. When using the GPS with a typical moderately priced receiver, the expected range errors are approximately (Kennedy 1996, p. 122) as shown in Table 1.
Table 1. Type and range of errors in GPS occurring with a moderately priced receiver. Type Range of of Error Error (m) Satellite clock error < 1 Ephemeris error < 1 Receiver error < 2 Ionospheric error < 2 Tropospheric error < 2 Total error < 8
The error budget also includes (for now, but reports suggest that this may change in the next few years) the effects of selective availability, which is the intentional scrambling of the satellite signals by the U.S. military.
The current limit of selective availability is 33 meters, making a total error budget of less than 41 meters (i.e., the distance computed to each satellite used in the solution is within 41 meters of the correct distance). In practice, these range errors provide accuracy expectations for positioning under an open sky (Kennedy 1996, p. 122) as shown in Table 2.
Table 2. Expected accuracy for positioning under an open sky. Horizontal Location Proportion Error Level of Points More (m) Accurate (%) 40 50 100 95
Because computing a position in GPS is a geometric solution based on three to four known points, an additional concern is the dilution of precision caused by the relative positions of the known points when the computation is made. As each of the range measurements that leads to a computed position contains some error, the overall estimate of a position must create a best, not perfect, fit. Dilution of precision (DOP) occurs when the satellites from which the position is computed are not well aligned to minimize the effect of the range errors. The ideal orientation of satellites finds them as far apart as possible in the sky. This situation places one satellite directly overhead, with three around the horizon at 120o increments.
Measures of this effect include PDOP (Positional Dilution of Precision), used to estimate the accuracy of 3-D positions (latitude, longitude, and elevation), and HDOP (Horizontal Dilution of Precision), used to estimate the accuracy of 2-D positions (latitude and longitude only). These measures range upward from 1.0 for the ideal case described above. As a simple rule of thumb, a value of 1.0 suggests point accuracy equal to the sum of the errors in the error budget only. A higher value is less desirable as the geometry of the satellites is poorer, leading to less reliable computations and wider confidence limits on the computed point. Most GPS users require DOP values of 4.0 or less for accurate work, although they may allow up to 8.0 for less precise work.
All of Earth now receives signals from a constellation of 24 NAVSTAR GPS satellites which, under open sky conditions, yield a PDOP of 4.0 or less at all times. Ten to twelve satellites are above the horizon at all points on Earth at all times. As only four are required to fix a 3-D position (three for a 2-D position), a GPS receiver under an open sky has multiple choices of satellites to use in computing a position. The problem in practical use is that the signals from some of the available satellites are often blocked by local obstructions requiring the receiver to select a less than optimal geometric arrangement of satellites in computing a position. Overhanging trees, road cuts, overpasses, mountain valleys, tall buildings, and even large trucks obscure parts of the sky from a receiver as it travels along a highway. Most receivers today track more satellites than are needed to fix a position and automatically make use of those satellites that provide the lowest DOP value. When a signal from a desirable part of the sky is blocked, the receiver uses the best remaining combination to establish a point, but the DOP value increases and accuracy suffers.
Enhancing Accuracy in GPS Positioning
As accurate positions are important to Mayday applications, a brief review of possible methods for increasing point accuracy is in order. There are two common techniques to enhance accuracy in GPS. First, one can compute the average of a fixed set of points collected over a period of time. Averaging allows random selective availability range errors in the signals to cancel each other out, thus making the mean latitude and longitude values somewhat more accurate. While averaging is of some use in static surveys, and might prove useful in breakdown cases when a car has not moved for several minutes before a call is placed, it is not an option in tracking a moving vehicle as a meaningful average of hundreds of points would severely "drag behind" the current location (Figure 1).
[Figure 1 ILLUSTRATION OMITTED]
A second possibility is to provide differential correction to the signal either on-board the vehicle or at the service center. Put simply, differential correction computes error in the GPS signal at a "base-station" receiver sitting on a precisely known location. The receiver calculates a location from the satellite data, and compares the result to its known location. The difference forms a correction vector that may be applied to locations simultaneously sampled by roving receivers viewing the same satellites. Within limited areas (reliably up to about 150 miles from the base station), Mayday systems could provide differential correction at the service center by receiving the same satellite information as the GPS units in the vehicles of its clients. When a call is received, the vehicle's data message could be corrected by comparing the base station and call data, synchronized by the GPS time of the call. Differential data provide much greater accuracy (error <5 meters in 90 percent of the cases), but differential mode requires that a long data message be sent from the vehicle. Further, differential correction at the service center is impossible to implement for national systems because the base station must be viewing the same satellites as the customer when the call is placed.
Another possibility is to equip customers' vehicles with real-time differential capability. In this instance, the GPS in the vehicle is in radio contact with the base station transmitting corrections. The on-board GPS computes a location and corrects it in real-time. Any time a call is activated, a corrected point is transmitted. This solution can provide differential accuracy on a limited national basis. The drawbacks are heavy, however, as real-time differential adds at least a $600 annual expense to the Mayday client, and it invites problems in assuring radio reception of the corrections at all times and locations.
It is not clear that the improved accuracy of differential correction is worth the increased cost, or even necessary for the system to work effectively. Today's national Mayday systems transmit autonomous GPS positions by storing and transmitting the "last good point" computed by the on-board GPS receiver. It is therefore fruitful to look at autonomous GPS and analyze its reliability for Mayday systems. This study looks at the first accuracy component, a selection of basic filtering operations that may be applied after a GPS position has been computed to discriminate "good" points accurate enough to send to the service center from "bad" points that might send assistance personnel to an incorrect location.
Filtering Techniques for Improving GPS Point Reliability
Filtering selectively eliminates points from consideration as locations. It does not enhance the computational accuracy of GPS; individual point locations are no closer to the actual location of the GPS unit with filtering than without it. Filtering does, however, enhance the reliability of points from a GPS by discarding locations when their accuracy is suspect.
To be prepared for a call that could come at any time, the vehicle's GPS unit computes and updates its location (typically at a 1 second interval) while moving. The GPS unit may then use one of a variety of filtering algorithms to determine that point's probable accuracy. A point that passes the filtering algorithm is deemed a good point and is retained for potential transmission until an updated good point replaces it. Bad points can occur for any of the reasons described above: poor or weak reception of satellites, poor satellite geometry, or satellite signals that bounce off objects on their way to the receiver (multi-path errors). Filters that are typically applied to discard computed positions are:
* 3-D filter: too few (<4) satellites are visible to provide a 3-D position.
* DOP filter: DOP value is too high to anticipate a good result.
* Velocity filter: distance between successive locations is excessive, causing the apparent velocity of the vehicle to be unrealistic.
* Acceleration filter: point spacing changes dramatically, suggesting that the vehicle has accelerated or decelerated by an extreme amount.
The first two filters operate on single computations only. For instance, if a compact car pulls beside a tall truck on a multi-lane highway and the signal from a tracked satellite is temporarily lost, the GPS receiver automatically generates a point based on the "next best" constellation of four satellites. If no fourth satellite can be found, then a location must be computed based on data from only 3 satellites (a 2-D position with elevation omitted). The 3-D filter eliminates that point. If a substitute fourth satellite is found but its position in the sky produces a clustering with the other satellites, the PDOP value for that set is too high and the point is discarded by a DOP filter.
The other two filters compare a potential point with the last good point. If a truck is traveling along an interstate highway at 63 mph, and a potential location is computed so far away from the last as to suggest that the truck must have traveled at 140 mph, the potential point would be discarded by a velocity filter on the basis that a truck cannot travel above a user-defined threshold (perhaps 75 mph). Similarly, if at second t a bus is stationary and at second t+ 1 it is traveling at 40 mph, the acceleration would exceed the threshold and the point would be discarded by an acceleration filter. The acceleration filter is complementary to the velocity filter, because while the speed (40 mph) may be entirely legitimate for a bus; no bus goes from 0 to 40 mph in one second.
The Role of GPS Filtering in Map Matching
This research investigates the application of filters in providing more reliable estimates of a vehicle's position along a highway. To isolate the role of GPS accuracy and the potential improvement in map matching offered by filtering, the other components that affect the accuracy of a Mayday system--the digital highway map and the map-matching algorithm--are held constant. The map used is the TIGER 1994 file for Montgomery County, Virginia. TIGER data are available nationwide at little or no cost and provide recent (though not entirely current) street information in several road classes. TIGER data meet the National Map Accuracy Standard (NMAS) (Thompson 1978, p. 104) at 1:100,000 scale. Ninety percent of well defined points fall within 1/50" of true position, which sets accuracy expectations of 51 meters or 167 feet on the ground.
The matching algorithm selected is ARC/ INFO's NEAR command which locates the nearest linear feature in one coverage to each point in a second coverage (Figure 2). NEAR returns the name of the linear feature found and the distance of the point from that feature. While NEAR is a simple map-matching algorithm, it provides the information required for analysis of the filters.
[Figure 2 ILLUSTRATION OMITTED]
Equipment, Study Area, and Methodology
A Motorola LGT-1000 GPS receiver with GeoLink software was used in the study. This unit contains a six-channel receiver which tracks six satellites at once so as to select the optimal constellation for each point computation.
With an antenna mounted atop a test vehicle, data were logged at two-to-three-second intervals in one-hour sessions around Montgomery County, Virginia. Data were collected under normal driving conditions: moving at speeds of up to 65 miles per hour on an interstate highway; slow movement along paved county and gravel forest service roads; and when the vehicle stopped at traffic signals. All points were stored without filtering, though a 10 [degrees]
horizon mask was used due to the likelihood of multi-path signals when satellites are so close to the horizon (Note 1). Four routes were driven and 5,353 point samples collected. Though many Mayday calls occur from non-moving vehicles, the main concern of this study is to determine the ability of GPS filtering to select good points under moving conditions.
The region is in the folded Appalachian Mountains, and is primarily rural in nature with steep valleys, heavy forest cover, two moderate size towns with dense street patterns (Blacksburg and Christiansburg), and a variety of road classes ranging from Interstate 81 to small gravel roads in the national forests in the area (Figure 3). The majority of county roadways are narrow with two lanes, though there are four-lane divided highways and wider two-lane state highways as well.
[Figure 3 ILLUSTRATION OMITTED]
Data were downloaded from the GPS receiver to a PC and processed by Motorola's Post Point software (DOS version 3.1) to produce autonomous points with full-status information (DOP, DOP Type, heading, speed, etc.). All routes were then exported with GeoLink's Data Manager software in a user-defined format to provide ARC/INFO points using the GPS time stamp as the primary key (Figure 4). Output coordinates were projected to the Virginia State Plane Coordinate System, South zone (NAD83), in U.S. feet. Point coverages were built in ARC/INFO, and the four routes were kept separate for the matching process.
[Figure 4 ILLUSTRATION OMITTED]
The TIGER highway data were imported into ARC/INFO and projected to the Virginia State Plane Coordinate System, South zone (NAD83). Using ARCEDIT, links driven on each route were interactively extracted from the complete TIGER highway file and placed into separate coverages. The GPS points collected along each route were matched to that route's coverage using ARC/INFO's NEAR command. The results of the map matching from all four routes were then merged into a single file containing distance error values and GPS time stamps. Map matching error data were linked to the collection status variables using the GPS time stamp. The resulting file associated matching errors with collection status for all points. Of the 5,353 points collected, 218 (4.1 percent) collected over 10,000 feet from a driven link were unmatched and discarded from the data set. All results are thus based on 5,135 sample points.
The error data were analyzed in a variety of combinations to determine the beneficial effects of filtering. The status data were used to stratify collected points according to their passing of each filter tested. The four filters described above (with two different DOP levels) plus a combination filter (3-D and DOP <4.0) were studied giving a total of six filters (Table 3). Three concerns were addressed in the testing. The effect of:
* Filters on reducing the distance error measured by NEAR matching to the actual links driven;
* Filtering in the classification of good and bad points as measured by their matching errors; and
* Filters on causing time lapses in the good-point data stream.
Table 3. Filters applied to GPS data. Filter Type Parameters Used All matched points No filtering All matched points filtered by * <4.0 DOP class * <8.0 All matched points filtered by All 3-D positions (regardless of DOP type PDOP) All matched points filtered by * 35 ms velocity filter velocity or acceleration (speed <78 mph) * 17.9 mss acceleration filter (acceleration <40 mph/second) All matched points--combination 3-D positions and DOP <4.0 filter
Distance Error Analysis
Figure 5 illustrates that with no filtering, 90 percent of map-matching errors are less than 453 feet. While the terrain represented in Montgomery County is more mountainous than many areas around the U.S. and the values may improve somewhat in more open sky conditions, they are certainly representative expectations based on known GPS and map parameters. In clear-sky conditions, one would expect results within 100 meters (328 feet) in 95 percent of the cases. As the TIGER map data are also subject to 167 feet of error (for a compounded worst case potential of 495 feet), 453 feet seems appropriate. Given the lack of open sky along many routes, 453 feet may even be somewhat better than expected.
[Figure 5 ILLUSTRATION OMITTED]
Of the single-condition filtering techniques applied, the best at reducing distance error was to remove points with DOP values over 4.0. In 90 percent of the cases, errors of 250 feet or less were obtainable with this technique, 203 feet less than when all collected points were included. The second most effective filter was elimination of points that were not 3-D. This filter reduced the data set to those points having errors under 314 feet in 90 percent of the cases. The DOP filter that removed DOP values greater than 8 allowed larger errors in the data set (90 percent under 385 feet), followed by the velocity and acceleration filters, with 90 percent of the points showing errors less than 426 and 436 feet, respectively. The Boolean intersection of the 3-D and the DOP<4 filters provided excellent results, with 90 percent of the points matched to a driven road within 179 feet.
Classification of Filter Success
While more restrictive filters clearly lower the distance error in map matching, they also eliminate a high percentage of the points from the GPS, some or many of which are accurate enough to complete a successful Mayday call. For example, the Boolean intersection filter (3-D and DOP<4) passed only 1,812 of the total 5,135 points on the four routes (36 percent). If filtering is too conservative, the last good point sent to the service center could be excessively old and not indicate the true location of the vehicle any better than a less accurate, but more recent point. A vehicle might have driven a mile or more since the last good point was stored.
An analysis of classification error associated with the points filtered out and passed by the techniques mentioned above follows. Error values are stratified into good (error <85 feet) and bad (error >85 feet) categories. The value of 85 feet was derived from an analysis of the road network density in the study area to determine at what distance an error could be and still be nearer to the current road than any other 90 percent of the time.
A random line-intersection analysis was performed to compute the average distance between line features in the complete county roads coverage (technique suggested in DeMers 1997, p. 303). Fifteen random lines were placed over the county map and their intersections with the road network computed. The distance between adjacent intersections along each test line provided a sample of road spacing. As the desire was to provide a correct match to the nearest road in 90 percent of the cases, distances were sorted to locate the 10th percentile (90 percent of the distances were greater than 170 feet), and the value was then divided in half. While this value varies from location to location, and smaller values are needed to identify the correct street in an urban area than in a rural area, it is an overall estimate for Montgomery County.
The error classes were cross-tabulated for each of the six filters, such that the proportion of all matched points could be isolated into four groups:
1. Good points that passed the filter;
2. Bad points that failed the filter;
3. Good points that failed the filter; and
4. Bad points that passed the filter.
An ideal filter classifies GPS locations such that all good points pass and all bad points fail (groups 1 and 2 above). A filter that is too conservative fails too many good points (group 3), and a filter that is too liberal passes too many bad points (group 4). Cohen's KHAT statistic was used on the cross-tabulations to identify the degree to which each filter was correct in its classification of good and bad points. This statistic, which was first described in Cohen (1960) and later used by Carstensen (1987), measures the association among nominal categories in a manner that excludes the random association to be expected in a limited number of classes. KHAT values range from -1.0 for complete misclassification to +1.0 for a perfect classification, with 0.0 representing a random classification. KHAT provides a value for statistical significance as well. The resulting analysis is summed up in the charts of Figure 6.
[Figure 6 ILLUSTRATION OMITTED]
In the classification analysis, the true nature of each filter becomes much more evident. Requiring a good point to show less than an 85 toot error is a very stringent test for a moving GPS in autonomous mode yet, overall, 42 percent of all points (2,159) were in the good class, with the remaining 58 percent (2,976) in the bad class. A perfect filter should pass the correct 2,159 points and should fail the other 2,976. Below we discuss filters on the basis of the total number of points passed.
The most conservative of the filters is the compound requirement that a point be both 3-D and have a DOP<4. This filter passed only 1,869 points (36 percent) in deriving an excellent error of 178 feet in the distance test. However, of the 2,159 points classified as good, the filter passed only 1,138 (52 percent), disregarding 1,021 points (48 percent) that were accurate enough to snap to the correct street and aid in locating a caller. This filter received a KHAT score of +0.287, significantly better than random classification at the 0.05 level. Though the chart of this filter is the most precise of the six, it is considered rather conservative as it keeps only about 36 percent of the points collected.
The second most conservative is the DOP<4 filter which passed 3,739 of all points (70.4 percent). The filter passed 1,747 of the 2,159 good points (80.9 percent), but it failed overall by accepting 1,992 points that were actually bad. This filter is best characterized as doing a good job of accepting good points, but a bad job by accepting bad points as well. Its KHAT score is +0.127, which is also significantly better than for a random classification.
The third most conservative filter is the 3-D filter which passed 3,785 points. This filter distinguished 1,730 of the 2,159 good points (80.2 percent) as good, but it accepted 2,055 points that were classified as bad. Overall, the filter is less accurate than the DOP<4 filter, with a KHAT score of +0.100. The KHAT value is significant at the 0.05 level.
The least conservative is the DOP<8 filter which passed 4,595 points (89.5 percent). It passed 2,039 of the 2,159 good points (94.4 percent) but failed terribly in passing 2,556 bad points as well. Its KHAT score was a barely significant +0.074; clearly not useful for a Mayday operation.
The velocity and acceleration filters were more liberal, passing almost all of the points. The acceleration filter passed 4,977 points and the velocity filter passed 4,933 points. The filters made more errors by accepting bad points rather than rejecting good ones. The velocity filter identified 2,109 of the 2,159 points that were good (97.7 percent), but it accepted 2,868 bad points. The acceleration filter accepted 2,079 of the 2,159 good points (96.3 percent), but it accepted 2,854 bad points. The KHAT scores for these filters were the lowest, with the velocity filter receiving a score of +0.011 and the acceleration filter a +0.004 score. Both filters classified points only at a chance level of accuracy. In addition, these filters have the highest distance errors in the sample; they rejected virtually no points.
Filters and Lapses in Good Points
Point spacing over time and space is one more important way to look at the effect of GPS filters. While the most conservative filters practically eliminate truly egregious distance errors, they do remove a large percentage of the points, even many that are adequate for leading emergency personnel to a call site.
For instance, the 3-D and DOP<4 filter, in allowing only a few bad points to pass, accepted only 36 percent of the points. At this rate, a good point is stored approximately every three seconds, a time short enough that even at high speeds a vehicle would travel only 330 feet or so. However, the average is unrealistic.
Looking at route GPS data on the map (Figure 7), the spacing of good points (black flags) ranges somewhat, especially in extremes (Table 4 and Figure 8). With some filters, a vehicle could move a considerable distance past its latest GPS location. In the terrain of Montgomery County, the 3-D and DOP<4 filter provides points older than 10 seconds in 8 percent of the cases, with one period of nearly two minutes without a point update. The less restrictive filters ranged from fewer than 1 percent of the lapses being over 10 seconds to about 4 percent of the lapses being over 10 seconds. As expected, less conservative filters give fewer and shorter lapses between point updates, but, on average, less accurate points.
Figure 7 & 8 ILLUSTRATION OMITTED]
Table 4. Lapse times between good points under potentially useful filters. Filter Type Percent of Maximum Lapses >10 Lapse Seconds (sec) DOP <4 4 15 DOP <8 <1 58 3-D 4 59 3-D & DOP <4 8 15
The results of these analyses offer contradictory conclusions. Conservative filters such as the 3-D and DOP<4 provide greater accuracy and are better at discerning good from bad points numerically, but they do so at the expense of up to 40 percent of points that are statistically adequate for locating a call. The less restrictive filters suffer in accuracy and make more classification errors, but they provide data more often and are thus more up to date.
Clearly, filters make different types of errors. Knowing this it is advisable to consider the relative costs of making misclassification errors, i.e., rejection of good points or acceptance of bad points. Though in a cross-tabulation table the errors are commensurate, in a Mayday situation, they cannot be considered equivalent. An emergency requires quick response; an accurate and recent point is paramount in describing a position to emergency personnel. Both the users of a Mayday system and the emergency personnel who respond to it must have faith in its integrity for it to be useful.
Filters that pass too many bad points simply cannot be used in a Mayday system. It is also unreasonable to filter out too many good points, making the last good point too old to be relevant. None of the filters tested proved totally reliable, but the research does suggest that a fairly conservative filter is best for Mayday systems. For fleet tracking and other less critical applications in which receiving a bad point is less hazardous, more liberal filtering or even no filtering at all may prove optimal. This notwithstanding, further research is needed to develop other measurable effects that can be used in filtering.
(1.) Though no filtering was applied to the data during collection, a GPS unit cannot compute a position if fewer than three satellites are visible at a given moment. Therefore, some routes had no data recorded for short periods of time.
Carstensen, L. W. 1987. A measure of similarity for cellular maps. The American Cartographer 14(4): 345-58.
Carstensen, L. W. 1995. Field verification and validation of the FN-74 System Final Report. Unpublished (confidential) report produced for Ford Motor Company while under contract to Westinghouse Electric Corporation--Communication Services Division.
Cohen, J. 1960. A coefficient of agreement for nominal scales. Educational and psychological measurement 20: 37-46.
DeMers, M. N. 1997. Fundamentals of geographic information systems. New York: John Wiley & Sons.
Kennedy, M. 1996. The global positioning system and GIS. Chelsea, Mich.: Ann Arbor Press, Inc.
Krakiwsky, E.J. 1996a. Smart vehicles: Heading this way--Affordable security on the road. GPS Worm 7(4): 55-9.
Krakiwsky, E. J. 1996b. Smart vehicles: Driving its development--Technology and market forces. GPS Worm 7(10): 50-5.
Lacey, N., and M. Cameron. 1995. Mayday in the Rockies: Colorado's GPS-based emergency vehicle location system. GPS World 6(10): 40-7.
O'Brien, A. J., and M. Balogh. 1996. Mayday! Evaluating GPS-enabled emergency dispatch. GPS Worm 7(10): 34-42.
Thompson, M. M. 1978. Maps for America. Washington, D.C.: U.S. Government Printing Office.
Laurence Carstensen, Jr. is Associate Professor of Geography at Virginia Tech's Department of Geography, 115 Major Williams Hall, Blacksburg, VA 24061-0115. Tel: (540) 231-2600; Fax: (540) 231-2089. E-mail:
Questia, a part of Gale, Cengage Learning. www.questia.com
Publication information: Article title: GPS and GIS: Enhanced Accuracy in Map Matching through Effective Filtering of Autonomous GPS Points. Contributors: Carstensen, Laurence W., Jr. - Author. Journal title: Cartography & Geographic Information Systems. Volume: 25. Issue: 1 Publication date: January 1998. Page number: 51. © 1997 American Congress on Surveying & Mapping. COPYRIGHT 1998 Gale Group.
This material is protected by copyright and, with the exception of fair use, may not be further copied, distributed or transmitted in any form or by any means.