CALIFORNIA CENTER FOR INNOVATIVE TRANSPORTATION
INSTITUTE OF TRANSPORTATION STUDIES
UNIVERSITY OF CALIFORNIA, BERKELEY
Differential GPS Evaluation for Enhanced Probe Vehicles
California Center for Innovative Transportation MOU- 6681 Final Report
Matthew Barth, Jie Du, and Jason Masters
University of California, Riverside
College of Engineering- Center for Environmental Research and Technology
March, 2005
This work was performed as part of the California Center for Innovative Transportation ( CCIT) Program of the University of California, in cooperation with the State of California Business, Transportation, and Housing Agency, Department of Transportation; and the United States Department of Transportation, Federal Highway Administration.
The contents of this report reflect the views of the authors who are responsible for the facts and the accuracy of the data presented herein. The contents do not necessarily reflect the official views or policies of the State of California. This report does not constitute a standard, specification, or regulation. CCIT Research Report: Differential GPS Evaluation for Enhanced Probe Vehicles
Summary
The majority of today’s in- vehicle navigation systems as well as Automated Vehicle Location ( AVL) systems use GPS ( Global Positioning System) technology that can provide position information with an accuracy of approximately 10- 20 meters. Recently, low- cost Differential GPS ( DGPS) receivers have now become available which have positioning accuracy of approximate 1- 3 meters. With this accuracy, it is possible to develop navigation and AVL systems that can determine vehicle lane positions. Lane- level positioning opens up the door for a number of new applications such as better fleet management, lane- based traffic measurements from probe vehicles, and lane- level navigation. In this project, we describe a low- cost, real- time DGPS system coupled with a developed map- matching algorithm, which is capable of performing lane- determination on today’s roadways. A prototype system has been designed and developed, described in detail in this report. Further, it has been demonstrated at two distinct locations, both in southern and northern California. The developed prototype system underwent a variety of tests, correctly determining the lane positions for a test vehicle 97% of the time, based on over 100,000 seconds of testing.
As a major part of this project, two methods have been developed to construct lane- level roadway network data. To date, lane- level roadway network data are not commercially available. One method that has been developed is based on an in- situ driving process and the other uses high- resolution aerial images. Overall, the aerial image technique is quicker and more accurate for constructing the lane data structures; however it requires that high- resolution imagery be available. For areas without aerial images, the ground- based in- situ driving technique also is effective but requires that all the roadways be driven and coded to create the lane data structures. It is a bit more tedious and prone to greater error.
With the advent of this lane- level positioning capability, a number of future research projects can be pursued, including using this system for a fleet of vehicles to conduct long term testing and data collection. The resulting lane- based trajectory data can then be used not only for real- time monitoring purposes, but also for analyzing lane- based vehicle activity ( e. g., lane speed and flow measurements). The data can also be compared and combined with macroscopic traffic data, e. g., that which comes from an embedded- loop- sensor- based traffic performance monitoring system ( PeMS).
i
CCIT Research Report: Differential GPS Evaluation for Enhanced Probe Vehicles
Contents
1. INTRODUCTION................................................................................................................... 1
2. BACKGROUND..................................................................................................................... 4
2.1. GLOBAL POSITIONING SYSTEM OVERVIEW........................................................................ 4
2.1.1. Position Processing of Standalone GPS....................................................................... 4
2.1.2. Performance of Standalone GPS.................................................................................. 6
2.2. DIFFERENTIAL GPS............................................................................................................. 7
2.3. GEOGRAPHICAL INFORMATION SYSTEMS ( GIS)................................................................ 8
2.3.1. Roadway Surveying Methods...................................................................................... 9
2.3.2. Roadway Data Structures........................................................................................... 12
2.3.3. Map Matching Algorithms......................................................................................... 18
3. SYSTEM DESIGN & METHODOLOGY............................................................................. 25
3.1. OVERALL SYSTEM LAYOUT.............................................................................................. 25
3.2. ON- BOARD HARDWARE AND FIRMWARE......................................................................... 26
3.3. SYSTEM SERVER................................................................................................................ 30
3.3.1. Differential GPS Correction Signal Generation......................................................... 30
3.3.2. Data Logging Program............................................................................................... 33
3.3.3. Real- Time Mapping Program..................................................................................... 33
4. LANE- LEVEL ROADWAY NETWORK DATA ESTABLISHMENT............................... 37
4.1. IN- SITU SURVEYING TECHNIQUE...................................................................................... 37
4.1.1. The Surveyor.............................................................................................................. 39
4.1.2. The Linker.................................................................................................................. 44
4.1.3. The Visualizer............................................................................................................ 47
4.2. AERIAL IMAGERY TECHNIQUE.......................................................................................... 56
4.2.1. Aerial Image Database............................................................................................... 56
4.2.2. Geo- rectification Procedure and Evaluation.............................................................. 57
4.2.3. Lane Determination Procedure................................................................................... 61
5. MAP MATCHING ALGORITHM........................................................................................ 63
6. EVALUATION RESULTS.................................................................................................... 66
6.1. DGPS SYSTEM EVALUATION............................................................................................ 66
6.1.1. DGPS Accuracy Evaluation....................................................................................... 66
6.1.2. Accuracy Degradation with Variable RTCM Correction Delays.............................. 67
6.1.3. Summary Results........................................................................................................ 68
6.2. LANE- LEVEL ROADWAY NETWORK DATA ACQUISITION EVALUATION......................... 69
6.2.1. Varying Data Trim and Curve Fit Parameters............................................................ 70
6.2.2. Erratic Lane Sections.................................................................................................. 73
6.2.3. Validation of Accuracy.............................................................................................. 75
6.2.4. Evaluation of Aerial Image Surveying Technique..................................................... 76
6.3. MAP- MATCHING RESULTS................................................................................................ 77
6.3.1. Comparison of Z- 12 and A12 Map- Matched Trajectories......................................... 77
6.3.2. Constant Number of Integration Points...................................................................... 79
6.3.3. Variable Number of Integration Points...................................................................... 80
6.4. SYSTEM RESULTS.............................................................................................................. 81
7. CONCLUSIONS AND FUTURE WORK............................................................................. 86
8. REFERENCES..................................................................................................................... . 88
i i
CCIT Research Report: Differential GPS Evaluation for Enhanced Probe Vehicles
1. Introduction
In the last decade there has been a significant amount of progress in developing in- vehicle navigation systems that help drivers efficiently reach their intended destinations. These systems rely on electronic maps in conjunction with sensor systems ( e. g., Global Positioning System ( GPS) receivers) and associated navigation algorithms. In- vehicle navigation systems began as a novelty offered only in rental cars and high- end luxury vehicles. However, the technology has improved and associated costs have fallen, resulting in a wide range of vehicle navigation systems that can be purchased separately, or part of an option package that are increasingly available to new car buyers. Similar progress has been made in the transit and fleet management arena, where many Automated Vehicle Location ( AVL) systems are employed to track and manage fleets such as buses, taxis, and delivery vehicles.
In general, vehicle navigation and AVL tasks can be broken down into three scales: 1) macroscale, 2) microscale, and 3) mesoscale.
Macroscale— the macroscale level generally considers a large roadway network as consisting of links ( roadways) and nodes ( e. g., intersections). Specific link and node attributes define how the network is connected together and what the general features are of the different links/ nodes ( e. g., position, length, number of lanes, capacity, speed limit, etc.). Macroscale navigation usually consists of finding a particular path between two nodes in the network. This path is usually based on some optimality such as shortest distance or shortest traverse time. Dijkstra’s algorithm [ Chabini and Lan, 2002] is a prime example of a solution to the macroscale route- planning problem.
Microscale— the microscale level typically considers navigation at the vehicle level and is concerned with tasks such as lane- keeping, as well as detecting and avoiding obstacles. At this level, there is no consideration of the ultimate or intermediate goal on the route. These tasks are generally carried out by the driver, however there has been a significant amount of research in automating many of the navigational tasks at this level, such as the work carried out for automated highway systems ( see, e. g., [ Connolly & Hedrick, 1999; Hatipoglu et al., 2003; and Lu & Tomizuka, 2002]).
Mesoscale— the mesoscale level is a level in- between the micro- and macro- scales and considers vehicle operation at the link- level. A particular link may have a variety of features: multiple lanes, turn pockets, off- ramps, etc. From a navigation point of view, mesoscale route planning is generally concerned with vehicle maneuvers such as passing, pulling off to the side of the roadway, moving out of the way of emergency vehicles, merging in and out of specialty lanes ( e. g., high occupancy toll lanes), and choosing the correct lane to exit. A link- based planning algorithm may be concerned with when, where, and how lane changes are made with respect to a planned course change ( e. g. turn, freeway exit) or the current traffic situation.
Most of the navigation and AVL research to date has been at the macroscale and the microscale. For in- vehicle navigation and AVL at the macroscale, sensors with positional accuracy of approximately 10- 20 meters is sufficient. For automated microscale operations, higher resolution sensors and actuators currently exist, but they are costly and have only been proven in controlled
1
CCIT Research Report: Differential GPS Evaluation for Enhanced Probe Vehicles
environments ( see, e. g., automated highway systems [ Hedrick et al., 1994; Horowitz & Varaiya, 2000]).
To date, very little research has been carried out on mesoscale navigation tasks. Two of the primary reasons for this are:
1) only recently have low- cost sensor technology become available with positional accuracy to 1- 3 meters ( e. g., differential GPS ( DGPS) receivers); and
2) today’s digital road network data have sufficient accuracy and features for macroscale navigation, however, they are insufficient for many mesoscale navigation tasks.
Now that it is possible to obtain sensors that have improved spatial resolution ( e. g., 1- 3 meters using DGPS) at a reasonable cost for a vehicle, it makes sense to develop and utilize digital road network data of matching accuracy ( i. e., lane- level detail). With both of these in place, it would be possible to determine which lane a vehicle is traveling in at any one time. With this capability, a large number of transportation research applications would benefit. For example, in terms of fleet management, operators would be able to determine whether a vehicle was pulled off to the shoulder as opposed to traveling in any particular lane. This can be important issue for monitoring freeway service patrol vehicles when they are deployed in the field. Further, transit managers could determine dwell times of when a bus is pulled into a specific bus bulb ( specialized bus zone at bus stop). Using probe vehicles, transportation officials and researchers could determine differences in traffic conditions for different lanes of the freeways ( including HOV lanes). This is particularly important when understanding the efficiency of weaving sections that may unnecessarily cause recurrent congestion. Lastly, a wide range of lane- based navigation algorithms ( maneuvers) could be developed to assist drivers in complicated roadway networks, particularly during congested conditions.
In 2004, a project was initiated to develop a low- cost system to determine vehicle positioning at the lane- level ( i. e. mesoscale level), targeted for future probe vehicle applications. The project was sponsored by the California Department of Transportation through the California Center for Innovative Transportation ( CCIT) and the California Partners for Advanced Transit and Highways ( PATH) program. The overall project goals were to:
1) develop the hardware that could be placed in a vehicle and report lane- level position information in real- time to a monitoring center;
2) develop a real- time monitoring application ( i. e. server) that could identify the lane position of the probe vehicle( s); and
3) demonstrate the system and evaluate the overall reliability.
Specific project tasks were carried out to accomplish these goals:
Task 1: A review was conducted of available hardware and AVL systems to understand their positioning capabilities and characteristics ( positioning accuracy, data rate, latency, additional parameters, etc.);
2
CCIT Research Report: Differential GPS Evaluation for Enhanced Probe Vehicles
Task 2: Based on the results of Task 1, a new low- cost on- board positioning/ communication hardware system was designed and developed specifically for lane- level positioning;
Task 3: A review was conducted of existing roadway network data that could be used for lane- level positioning;
Task 4: Based on the results of Task 3, two roadway lane- level surveying techniques were developed to create a sufficiently accurate digital roadway networks;
Task 5: A review was made of existing map- matching techniques that could be used for matching a vehicle’s position with the lane- level digital roadway network;
Task 6: Based on the results of Task 5, a base station system application was developed to display probe vehicle positions, determine the vehicle’s lanes ( via map- matching), and log the data into a database.
Task 7: The system was then evaluated and demonstrated in multiple locations.
This report describes these various tasks and the corresponding results. In Chapter 2, background information is provided on differential GPS technology, associated geographical information systems ( GIS), roadway surveying methods, roadway data structures, and map- matching algorithms. Chapter 3 describes the overall system design and methodology used for the project. In this chapter, specifics are given on both the on- board hardware and the real- time server program. Chapter 4 describes two different techniques that were developed and used for establishing lane- level roadway networks. Chapter 5 provides details on the map- matching techniques that were used. Chapter 6 describes the system’s overall results followed by conclusions and future work that is discussed in Chapter 7.
3
CCIT Research Report: Differential GPS Evaluation for Enhanced Probe Vehicles
2. Background
In this chapter, background information is provided on global positioning systems and techniques ( Sections 2.1 and 2.2), associated geographical information systems with a focus on roadway surveying techniques ( Section 2.3.1), roadway data structures ( Section 2.3.2), and map- matching algorithms ( 2.3.3). All of this material lays the groundwork for the developed system’s hardware and software described in subsequent chapters.
2.1. GLOBAL POSITIONING SYSTEM OVERVIEW
The U. S. global positioning system ( GPS) is one of the most convenient and accurate methods for determining vehicle position in a global coordinate system [ Farrell & Givargis, 2000]. A detailed but concise description of GPS is provided in [ Farrell & Barth, 1999]. The system is built around a set of 24 satellites that orbit the earth. The orbits are designed in a manner that allows the signals from at least four satellites to be received simultaneously at any point on the surface of the earth ( neglecting obstacles such as tunnels). A GPS receiver on the surface of the earth can use the signals from at least four satellites to determine its own ( x, y, z) antenna position according to various measurements of the pseudorange between the satellite and the receiver antenna. The standard deviation of standard GPS position estimates is on the order of 10- 20 meters. Increased accuracy better than 3 meters can be achieved through the use of code- range based differential DGPS techniques such as those described in [ Farrell & Barth, 1999; Blomenhofer et al., 1994; Kee & Parkinson, 1994; and Navstar, 1991].
Furthermore, a DGPS system that uses carrier phase based range observations can provide accuracy down to 1- 3 centimeters; however these receivers require dual frequency reception and additional algorithms to solve integer ambiguity issues, resulting in higher cost ( see, e. g., [ Navstar, 1991; and Farrell et al., 2000]). In this research project, this 1- 3 centimeter accurate DGPS technique was used as a tool to survey and built a lane- level detailed digital map as the proposed lane- level positioning system reference map. In the next section, the basic algorithms of GPS and DGPS are described.
2.1.1. Position Processing of Standalone GPS
Generally, most low- cost GPS receivers are single frequency ( L1) receivers. A receiver measures pseudorange L1 frequency signals from available satellites using a specific C/ A code. This pseudorange measurement by the receiver from satellite i is modeled as:
)()()()( 12)( 5.02)( 2)( 2)()())()()((~ iiiiaisvriiiiMPEIfftctczZyYxXνρ++++ Δ+ Δ+ −+−+−= ( 2.1)
where )(~ iρis the pseudorange measurement from a receiver antenna center to the ith satellite. The right hand side of equation ( 2.1) is a model of the pseudorange signal. is the earth- center earth- fixed ( ECEF) position coordinate of satellite i, calculated from ephemeris parameters that are transmitted in the navigation message. There are ),,( zyx),,( ZYX ( i) ( i) ( i)
4
CCIT Research Report: Differential GPS Evaluation for Enhanced Probe Vehicles
several biases that are part of the model: rtΔ is the receiver clock bias, is the satellite clock bias, represents the atmospheric delay,
( i)
( i) ( i )
svtΔaIE is error in the broadcast ephemeris data, ( i) MP is the multi- path error on the civilian range signal ( C/ A code), and is the receiver range tracking noise error. The notation refers to the quantity in parenthesis to the ith satellite.
( i)
( i)
ν)(
This pseudorange is referred to as a “ pseudo” range since it is not a pure range signal. It is composed of the actual range
( 2.2) 5.02)( 2)( 2)()())()()(()( zZyYxXiiii−+−+−= xρ
( where ), the receiver clock bias, and the contributions from common mode noise errors: ),,( zyx= x
)()( 12)( iiaisvEIfftc++ Δ= χ ( 2.3)
and non- common- mode noise errors:
( 2.4) )()( iiMPνη+=
formed by multipath and receiver noise. In the stationary mode, linearization of a set of pseudorange measurement equations ( 2.1) of m available satellites at a known point with augmented gives 0 x
),,,( rtczyxΔ= x
)()(~ xηχxHxρδδδhot+++= ( 2.5)
where
)()(~)(~ 0xρxρxρ−= δ,
, Tm)](~...,),(~[)(~)() 1( xxxρρρ=
, Tm)](...,),([)()() 1( xxxρρρ=
0xxx−= δ,
and the measurement matrix is: 01)()()( 1)()()( )()()( ) 1() 1() 1( xxxxxxxxH=⎥⎥⎥⎥⎥⎥⎥⎥ ⎦ ⎤ ⎢⎢⎢⎢⎢⎢⎢⎢ ⎣ ⎡ ∂ ∂ ∂ ∂ ∂ ∂ ∂ ∂ ∂ ∂ ∂ ∂ = zyxzyxmmmρρρρρρMMMM 5
CCIT Research Report: Differential GPS Evaluation for Enhanced Probe Vehicles
With the above linearization and neglecting the high order terms of the linearization, the receiver position and clock bias can be estimated with Eq. ( 2.6). Since there are four unknowns in the pseudorange equation, it is necessary to have at least four satellite pseudorange measurements to estimate the position and receiver clock bias at each epoch. When we have m satellite pseudorange measurements, the unbiased error estimate of position and clock bias is given by:
≥ 4
ρHHHx~)( ˆ 1δδTT−= ( 2.6)
With knowledge of the position error estimate x ˆ δ, the actual position estimate is determined as:
xxx ˆ ˆ 0δ+= ( 2.7)
2.1.2. Performance of Standalone GPS
To evaluate whether a stand- alone GPS receiver could satisfy the lane- level determination requirements of our application, it is necessary to calculate the variance of the estimated position and receiver clock bias. Each pseudorange measurement has common- mode noise with a variance and non- common- mode noise with variance. Note that 2 2
xσησχ and η are uncorrelated in the pseudorange measurements at each epoch. They can be considered as composite noise with variance , and zero cross- covariance between satellite pseudorange measurements. As a result, the covariance matrix of the pseudorange measurement noise becomes a scaled identity matrix . Accordingly, the covariance matrix of estimate based on a set of simultaneous pseudorange measurements can be written as:
σ 2 = σ 2 + σ 2
+ + T
σ 2
x ˆ
ηχ]))([( EηχηχI
1211( ]())[( ]) ˆ )( ˆ [( ) ˆ ( Cov ) ˆ Cov( − −− = ++= −−= == H) HH) HHη( χη( χHH) HxxxxxxPTTTTTTTEEσδ ( 2.8)
If V is defined as , then dilution of precision ( DOP) factors can be defined based on the components of V. It is assumed that H includes a rotation matrix so that the first three states of x represent horizontal position and altitude. Given the horizontal DOP ( HDOP), defined as 1)(−= HHVT2211VV+ ( usually greater than one), the standard deviation of a horizontal position estimate is:
HDOP) ˆ Var() ˆ Var( 21σσ=+= xxhp ( 2.9)
Given the range standard deviations of common- mode noise on the order of 25.47 m [ Farrell & Barth, 1999] and non- common- mode noise at order 0.1 to 4.0 m [ Farrell & Barth, 1999; Farrell & Girvargis, 2000], according to Eq. ( 2.9), the standalone GPS receiver has a horizontal position error standard deviation at the order greater than 20m. Such a position error standard deviation makes it impossible for a standalone GPS receiver to differentiate a vehicle’s lane, with a lane
6
CCIT Research Report: Differential GPS Evaluation for Enhanced Probe Vehicles
being approximately 3 meters wide. In order to get higher position accuracy, it is best to remove the common- mode error from the measurements to make the error standard deviation small enough to satisfy lane- level accuracy requirements. This can be accomplished using differential GPS ( DGPS) techniques, described in the following section.
2.2. DIFFERENTIAL GPS
In general, differential GPS techniques increase positional accuracy by reducing common mode errors. The technique usually involves the cooperation of two receivers, one that is stationary and another that is moving ( i. e., the rover), making position measurements. The stationary receiver is the key: it ties all the satellite measurements into a solid local reference. As previously described, a GPS receiver uses timing signals from at least four satellites to establish a position. Each of those timing signals is going to have some error or delay depending on factors such as atmospheric conditions, multipath, etc. ( see [ Farrell & Barth, 1999]). Since each of the timing signals that go into a position calculation has some error, the calculation is going to compound those errors. However, because the satellites are so far out in space compared to relative distances between two receivers ( e. g., within 50 kilometers) in a DGPS setup, the signals that reach both of them will have traveled through virtually the same slice of atmosphere, and so will have virtually the same errors. Thus with DGPS, we have one receiver measure the timing errors and then provide correction information to the other receiver( s) that are roving around. In this way, the common mode errors can nearly be eliminated from the measurement process. This was initially devised primarily to combat the Selective Availability error that the Department of Defense purposefully designed to degrade common GPS accuracy ( see [ Farrell & Barth]). Currently, Selective Availability error is turned off.
DGPS requires that the reference receiver be on a point that has been accurately surveyed. This reference station receives the same GPS signals as the roving receivers but instead of working like a normal GPS receiver, it uses its known position to calculate timing corrections. It figures out what the travel time of the GPS signals should be, and compares it with what they actually are. The difference is an “ error correction” factor. The reference receiver can then transmit this error information to the roving receivers so they can use it to correct their measurements. Since the reference receiver has no way of knowing which of the many available satellites a roving receiver might be using to calculate its position, the reference receiver quickly runs through all the visible satellites and computes each of their errors. The roving receivers get the error corrections and apply them for the particular satellites they are using.
In the early days of GPS, reference stations were established by private companies who had big projects demanding high accuracy; e. g., surveyors or oil drilling operations. This is still a common approach, but now there are several public agencies transmitting corrections. The United States Coast Guard, for example, and other international agencies have established reference stations all over the place, especially around popular harbors and waterways. These stations often transmit as radio beacons. Any receiver in the area capable of receiving these corrections can radically improve the accuracy of its GPS measurements. The Federal Aviation Administration ( FAA) has also developed a Wide Area Augmentation System ( WAAS) as a safety- critical navigation system, providing positioning correction information that allows for a high degree of positioning accuracy for the aviation community. The WAAS is based on approximately 25 ground reference stations that cover very large service areas in North America. Each of these reference stations is precisely surveyed. Correction messages are prepared and
7
CCIT Research Report: Differential GPS Evaluation for Enhanced Probe Vehicles
uplinked to a geo- stationary satellite via a ground uplink system. The message is then broadcast on the same frequency ( L1) as GPS to receivers capable of receiving these signals. The wide area of coverage for this system includes the entire United States and some outlying areas such as Canada and Mexico ( for further details, see [ FAA, 2002]).
Similar to the WAAS, a second augmentation to the GPS signal is being developed, called the Local Area Augmentation System ( LAAS). The LAAS is intended to complement the WAAS and function together to supply users with seamless satellite based navigation for all phases of avionic flight. In practical terms, this means that at locations where the WAAS is unable to meet existing navigation and landing requirements ( such as availability), the LAAS will be used to fulfill those requirements. In addition, the LAAS will meet the more stringent Category II/ III requirements that exist at selected locations throughout the U. S. ( see [ FAA, 2002]).
In order to accomplish lane- level positioning determination, it is clear that DGPS needs to be used. However, there is still the question on whether a WAAS- enabled GPS receiver is sufficient, or whether a dedicated DGPS system is required. This question is explored in Section 6 of this report.
2.3. GEOGRAPHICAL INFORMATION SYSTEMS ( GIS)
To map geographic data with software, geographic information systems ( GIS) are often used. A GIS represents information about a specific place using layers, with each layer containing a specific form of data [ GIS, 2003]. For example, Figure 2.1 illustrates the representation of an urban area with three discrete layers: customers, buildings, and streets. To organize the layers, a GIS divides data into three basic forms ( with each layer representing only one form of data). The aforementioned example’s layers can each be uniquely classified with these three basic types of data: spatial data, tabular data, image data.
Spatial data are then characterized by points, lines, and areas. Points are any objects which can be described in terms of their ( x, y) location on the earth’s surface. Lines are any objects with length, and areas are those objects having boundaries, such as countries or lakes. The spatial data type is further subdivided into two data models: the raster model and the vector model. The vector model, which the street layer of Figure 2.1 uses, represents discrete data such as object locations, and data that can be summarized by area such as average annual income per county. The raster model divides a mapped area into a matrix of cells, with each cell given a continuous numeric value or category value representing some feature such as elevation, vegetation type, or soil type. In the raster model, points are defined as single cells, lines are defined as a continuous row of cells, and areas are defined as any set of adjacent touching cells.
8
CCIT Research Report: Differential GPS Evaluation for Enhanced Probe Vehicles
Figure 2.1. Layered Representation of Sample Urban Area
The second data type used by a GIS is tabular data. Tabular data is any information which describes a map feature. For example, each street can be assigned a value representing its average travel time, and these values can be associated with the spatial data. In Figure 2.1, the customer layer could represent the average number of customers per building, and thus the customer layer would contain data describing a map feature ( buildings), i. e. tabular data.
The third type of data utilized by GIS is image data. Image data are acquired through many sources, including aerial photographs and digitally scanned pictures. Image Data can also be an attribute of an existing map feature ( e. g. a picture of a building). In Figure 2.1, the building layer could contain image data if the buildings themselves are images, or if by clicking on the buildings an actual image of the building is summoned. Image data is most useful for quick visual reference or for acquiring spatial data quickly, but its disadvantage lies in the fact that it is a single file, and that it can not be broken down into layers of pertinent information.
2.3.1. Roadway Surveying Methods
Statistical Mapping
As the quality and affordability of GPS receivers increase, vehicles equipped with GPS navigation systems have become more and more common. Also, with the advance of the wireless communications industry, wireless communication devices are being integrated into more and more vehicles. As a result, it should be possible to have these vehicles carry out very precise navigation using digital roadway maps. However, nearly all digital roadway maps available today have accuracy of approximately 20- 50 meters. An example of this accuracy is shown in Figure 2.2, where a typical digital roadway map is overlaid on top of a geo- rectified aerial image. It can be seen that for some sections of the roadway, the blue representation of the roadway network is fairly close to the actual road. However, in other locations, the blue representation of the roadway is significantly off. It is clear that this commercially available digital roadway map data is insufficient for lane- level navigation. Therefore, new techniques for creating lane- level digital roadway networks are required.
9
CCIT Research Report: Differential GPS Evaluation for Enhanced Probe Vehicles
Figure 2.2: Typical commercial digital roadway network ( in blue) overlaid on top of a geo- rectified aerial image.
In order to obtain high- accuracy roadway data, several techniques exist to acquire this information. Obtaining roadway as- built survey documentation is a difficult process. It is also cumbersome to manually survey roadways when there is traffic. Another method of acquiring lane- based roadway network data is to use DGPS surveying techniques. A probe vehicle can be equipped with carrier- phase DGPS instrumentation and subsequently driven on roadways of interest. This vehicle can travel down different lanes in the roadway. Multiple vehicle trajectories in each lane will produce multiple refinements of the centerline. The resulting data can then be statistically analyzed to create lane- level accuracy in digital street maps.
There are some drawbacks to using only the information acquired from statistical analysis on raw GPS trajectory data. Driver variations within lanes and lane changes present two significant error sources in the method used in [ Rogers & Schroedl, 2003]. Another drawback is that lane boundary demarcations cannot be accurately determined. It cannot always be assumed that a lane boundary occurs at the midpoint between two lane centerlines, and lane boundaries on the outermost edges of roads cannot be determined accurately from raw trajectory data. A refinement of the method used in [ Rogers & Schroedl, 2003] is introduced in [ Zhang & Taliwal, 2004] where computer vision is used to provide distances from the left and right lane boundaries of the vehicle’s current lane of occupation at any given instant. Utilization of the left and right offset data complements the method of [ Rogers & Schroedl, 2003] to produce increasingly accurate results.
In [ AST, 2003] a relatively straight 250- meter section of road in Hammond, Indiana, USA was chosen for experimental analysis. The road chosen is a two- lane road where lane changes are relatively frequent. The particular section chosen was also the site of an earlier study, the Rollover Stability Advisor project, in which a large portion ( 250 truck traversals) of GPS and
10
CCIT Research Report: Differential GPS Evaluation for Enhanced Probe Vehicles
vision data were collected. Using the pre- collected GPS data alone, it was difficult to accurately determine the lane centerlines because of the frequency of lane changes. But using digital analysis on the accompanying archive of images, it was possible to determine the left and right lane boundary offsets at each GPS coordinate. Using this offset information, the existing trajectories were shifted by the appropriate amounts and new measures of the lane centerlines as well as the lane boundaries were determined. The vision- aided method was a significant improvement over previous methods.
Several drawbacks are associated with these techniques, including things such as driver variations within lanes and lane changes, as well as the fact that lane boundary demarcations cannot be accurately determined. To overcome many of these issues, we have developed a technique to capture roadway feature data ( based on human or computer visual processing) at the same time of traveling down the center lane of any roadway. The visual data can then be post- processed, resulting in a fairly accurate lane- based roadway representation. This technique is described in detail in Section 4.1.
Photogrammetry
Other roadway mapping techniques include using photogrammetry. The science of photogrammetry is concerned with the measurement of two or three dimensional objects from images. The results of photogrammetry can produce rectified images or maps in reference to a desired coordinate system. When mapping large areas, photogrammetry is concerned with rectifying ( correcting for curvature of the earth and obliqueness of photograph) aerial photographs and matching them to two- dimensional coordinate systems.
When taking aerial photographs, the tilt of the camera lens with respect to the horizon is referred to as the depression angle [ Aber, 2003]. Depending on the depression angle, an aerial photograph can be classified as oblique or vertical. A depression angle between 85 and 90 degrees usually classifies an aerial photograph as vertical; any other angles will describe an oblique photograph. In transforming an aerial photograph, oblique or vertical, to a two- dimensional coordinate system, the photograph must be rectified to correct for the geometry of the camera lens, the depression angle, and various other distorting factors. The process of rectification, along with the resolution of the photograph, will determine the accuracy of the corrected aerial photograph in reference to a geo- coordinate system.
Various techniques of photogrammetric mapping exist, each with their own methods of rectification. Single photograph mapping requires numerical rectification, monoplotting, or digital rectification to transform the photographs into geo- referenced maps. Numerical rectification transforms photographs into 2D coordinate systems while monoplotting transforms photographs into 3D coordinate systems. Digital rectification transforms digital ( scanned) images pixel by pixel into a corrected photograph. A second method of photogrammetric mapping, stereophotogrammetry, utilizes two different photographs ( with vertical depression angles) of the same area taken at slightly different positions to produce a 3D model of the given area. The effect is similar to watching television with special “ 3D glasses”, which fool the stereo- optical depth perception of human vision so that two separate flat images are perceived as a single image having depth. A third method of photogrammetric mapping, mapping with several photographs ( of the same object), uses digital and analytic techniques to intersect the object
11
CCIT Research Report: Differential GPS Evaluation for Enhanced Probe Vehicles
points on multiple photographs with each other and produce a fully three dimensional object model.
Once a vertical aerial image is geo- rectified, it is usually straightforward to obtain roadway network data, by identifying pixels in the image that are roadways, and converting this pixel information to roadway data structures. Details of this technique are provided in Section 4.2 of this report.
2.3.2. Roadway Data Structures
In this section, roadway data structures are briefly introduced to provide background on the development of lane- level roadway network data structures, described in Section 4.
Standard Planar Model
To represent a simple planar database of streets, a basic node- link structure is sufficient in most cases. An example of this basic node- link structure is presented in [ Noronha, 2003]. This structure is comprised of a node table, a link table, a node attribute table, and a link attribute table, shown respectively in Tables 2.1, 2.2, 2.3, and 2.4. These tables represent the attributes of all nodes and links in the database.
Table 2.1 displays the node table, which lists each node ID ( a number in this case) and its corresponding coordinates. Table 2.2 then displays the link table which lists each link ID ( a letter in this case), and a corresponding from- node and to- node. Each link has an implicit direction which is indicated in this table. All existing links are not referenced in this table. For links with the same endpoints but different direction, a simple negative sign is affixed to the link ID when it is referenced in the link attribute table ( Table 2.4).
Table 2.1: Node Table
NODE
X coordinate
Y coordinate
1
58
100
2
0
- 7
3
150
2
Table 2.2: Link Table
LINK
From node
To node
a
2
3
b
1
3
c
4
5
Table 2.3 displays the valency of all nodes in the network. Valency refers to incident links ( or nodes) forming intersections. This table can be inferred from the link table, but to facilitate quicker network analysis it can be included in the network description. Other attributes of the
12
CCIT Research Report: Differential GPS Evaluation for Enhanced Probe Vehicles
nodes, such as elevation or average traffic through the node, can be recorded as well. Table 2.4 displays multiple features of the links, such as address ranges and lane numbers.
Table 2.3: Node Attribute Table
NODE
VALENCY
LIST OF NODES
LIST OF LINKS
3
3
1,2,5
- b,- a, d
5
5
3,4,6,10,11
- d,- c, e, f, g
12
4
7,11,13,18
- h,- m, n, s
Table 2.4: Link Attribute Table
LINK
Street Name
Addresses( L)
Addresses( R)
Class
Length( km)
Lanes
Speed Limit
c
Hwy101
-
-
Freeway
1.42
3
100
- c
Hwy101
-
-
Freeway
1.44
3
100
m
Elm St
1201- 1299
1200- 1298
Arterial
0.23
2
80
t
Pine Ave
598- 200
599- 201
Residential
0.68
1
45
With these Tables 2.1, 2.2, 2.3, and 2.4, the basic descriptive features of the map can be recorded. This standard planar model does have limitations which make it difficult to maintain in some applications. Any time a single link attribute ( e. g. number of lanes, speed limit) changes, a link must be broken down into smaller segments. This increases the size of the database, which in itself is not a big problem. The big problem occurs in database maintenance and compatibility with other databases. A solution to this problem would be dynamic segmentation, which stores features and attributes as offsets from a defined starting point. A data structure utilizing dynamic segmentation is discussed in the next section. Table 2.5 describes the lane features of the links in the database. The link is segmented with respect to its multiple features, but it is still stored as a coherent unit. As can be seen, it is relatively simple to update a link’s features with this system. There is limited support for dynamic segmentation in current GIS systems. An update would require a complete overhaul of standard internal data models.
Further, the standard planar model does not describe the topographical relationship between links. This information is often necessary for traffic analysis, and is also helpful in map- matching. The addition of turn tables, which describe the transitional dynamics between links, would provide the navigational information necessary for traffic analysis. The lane- based data model described in the last section employs turn tables.
Table 2.5: Lane Feature Table
LINK
LANES
From Offset ( km)
To Offset ( km)
c
3
0.0
0.6
c
2
0.6
1.8
c
3
1.8
3.4 13
CCIT Research Report: Differential GPS Evaluation for Enhanced Probe Vehicles
The standard planar street model used by the Topologically Integrated Geographic Encoding and Reference System ( TIGER) and the Dual Independent Map Encoding System ( DIME) builds a network of streets based on the basic node- link structure [ Noronha, 2003]. The DIME and TIGER structures though were mainly concerned with encapsulating information relative to each city block, or ‘ urban polygon’. The streets were only considered as boundaries of the urban polygons. Important features, such as number of lanes and pavement conditions, would often change along a single street. Streets then had to be segmented anytime just one of these attributes would change. This segmentation adds more records to the database and results in a file that becomes unnecessarily large and difficult to maintain. Much better suited is a link- node structure built on the concept of dynamic segmentation. Several digital roadway networks now use dynamic segmentation, an example of which is given in the following section.
The Ontario Standard Labeled Road Network
In the early 1990s, the Emergency Health Services ( EHS) branch of the Ontario Ministry of Health decided to investigate the possibility of creating a comprehensive roadway network for the entire province of Ontario, Canada. EHS is responsible for providing emergency ambulance service to the entire province of Ontario ( outside of Metro Toronto). To provide equitable service to all areas of Ontario, a descriptive roadway network was needed. Many large roadway networks had been created before, such as the DIME and TIGER archives. The Ontario Road Network was targeted for navigation purposes, unlike the DIME and TIGER files ( for more details on the Ontario Standard Labeled Road Network, see [ Noronha, 2003]).
The Ontario Standard Labeled Road Network ( SLRN) is structured with four basic information levels: positional coordinates, street names, address ranges, and topological information. These four information levels were designed to correspond to what were considered to be the four principal applications of roadway network data. These four principal applications ( listed in order respective to the information levels above) are cartography, basic reckoning and navigation, address matching, and routing. Figure 2.3 illustrates the use of all four levels of information.
The first level of information records the coordinate points which characterize a given street link. This is the most basic and necessary form of information for describing the map’s link features. The SLRN model allows for flexibility in the definition of the beginning and end of a given street link. For example, in Figure 2.3, Toronto’s Yonge Street runs from Queen’s Quay to Steeles Avenue. In reference to map sheet or civic ward boundaries though, it may be preferable to define Yonge Street as two separate entities, one from Queen’s Quay to Eglinton and one from Eglinton to Steeles. Both definitions are valid in the SLRN model. Excessive fragmentation in the definition of a street link would defeat the purpose of this SLRN model though, as the dynamic segmentation principle allows a single street link with varying feature attributes along its length to be defined as a single entity.
The second information level represents the name or label feature of a street. In the SLRN model, any given street or segment of a street may have multiple names. Each stretch of a SLRN road is defined by a starting offset and an ending offset with respect to the beginning point of the street. The Level 2 information does not explicitly provide for a road class ( highway, urban street) feature, as the assignment of road class is in many cases subjective. Road class may be implied though in the name of a roadway ( King’s Highway) without violating the character of the SLRN model. If road class is defined in association with a variable feature of the road, such
14
CCIT Research Report: Differential GPS Evaluation for Enhanced Probe Vehicles
as lane number or average traffic flow, then that information would be best represented in an Extended Object, which is an entity associated with a section of one or more roads.
Figure 2.3: SLRN representation of Yonge Street, Toronto
Level three information refers to address data, or correspondences, as they are referred to in this model. A correspondence is defined as a mapping of any random offset to a known address or civic number. Without dynamic segmentation, addresses are defined as ranges between the starting point of a street link and the ending point. Addresses that fall within the range are located using linear interpolation, which was not always reliable. Many addresses, especially in rural areas, were not at evenly spaced intervals along the address range. Dynamic segmentation allows the definition of known addresses at arbitrary points to increase the accuracy of interpolation.
The previous three levels of information are useful in themselves for many applications, but for navigation applications, connectivity information between street links is needed. This is the type of information stored at the fourth level. This information must be stored explicitly due to non- grade crossings such as bridges and overpasses, where an intersection of coordinate chains does not necessarily imply a physical connection. To store connectivity information, intersections are recorded as attribute features of links. Over the course of a road ( the primary road), each time an intersection is encountered the offset and the identifier of the intersecting road ( the secondary road) are recorded. In some cases two roads may intersect at more than one point, so the offset of the secondary road is also recorded. The intersecting road identifier and the two offsets completely characterize an intersection feature. The intersection information alone is often sufficient for most routing applications, but sometimes, especially in urban areas, the impedance
15
CCIT Research Report: Differential GPS Evaluation for Enhanced Probe Vehicles
of links needs to be explicitly recorded as traffic flow has a significant effect on routing times. Impedance can be calculated as a function of offset, or in some cases explicitly recorded in an attribute field.
The SLRN model was created reactively, as a response to the way roadway networks are used in real- world applications. The dynamic segmentation principle upon which the model is founded minimizes database size and facilitates database updates. This principle though requires the acquisition of positional information for the beginning coordinates of a given street when that street is being added to the database. This is due to the fact that all features are recorded with respect to offsets from the beginning position. This is often inconvenient for applications that are not recording roadway network data on the macro scale. The beginning coordinates of the street being added to the database may be many miles from the segment of the street that is being recorded. It would be convenient if the data model used to record roadway features within small areas did not use dynamic segmentation, but could be converted to that format easily if an adequate number of street segments were available. This is the strategy used to create the roadway network used in this project.
UCSB Non- Planar Lane- Based Format
As another example of an advanced roadway network data structure, the National Center for Geographic Information and Analysis ( NCGIA) located at the University of California, Santa Barbara has proposed a non- planar lane- based data structure in the interest of improving the quality and usefulness of current roadway networks ( see [ Fohl et al., 2003]). The terminology ‘ non- planar’ introduced here represents a concept identical to the connectivity scheme ( level 4 information) used in the SLRN of the previous section. A non- planar roadway network is one where intersections between roadway elements are defined explicitly, and not assumed to exist simply where links cross. The UCSB data structure was designed utilizing this non- planar scheme in conjunction with the dynamic segmentation concept, and introducing the lane as the basic roadway element.
The lane table is the foundation of this lane- based network, and the structure of a basic lane table can be seen in Table 2.6. The ‘ lane_ id’ field records the unique alphanumeric identification for the lane. The ‘ street_ id’ field records the street that contains the lane. The ‘ from’ field and the ‘ to’ field represent the beginning and ending points of the lane as linear offsets from the beginning of the street which contains the lane. As defined in [ Fohl et al., 2003], the lanes are not intended to be stored as individual polylines but rather as segments of the street centerline. The lanes are defined individually only for the purposes of network analysis and are not intended to be display features. The main impetus for this definition of the lane entity was the assumption that GPS accuracy was limited to 10 meters and defining lanes as individual polylines would be useless*.
The lane table in itself describes the physical structure of the entire lane- based network, but connectivity between lanes is still undefined. To record this connectivity information, turn tables are employed. A ‘ turn’ is defined as a transition from one lane to another, such as turning at an intersection, traveling straight through an intersection, or changing lanes. There is a difference in
* In this project, the UCSB assumption of GPS inaccuracy is unwarranted and thus the modified data structure used in this project record lanes as separate polyline entities.
16
CCIT Research Report: Differential GPS Evaluation for Enhanced Probe Vehicles
the information needed for recording transitions between parallel lanes ( lane changes) and the information needed for recording transitions between lanes at intersections. Two different tables are therefore used to record two different types of turns. The first table, a point- turn table, records turn availability at points on a lane. The second table, a linear- turn table, records turn availability at segments along the lane. Impedance points are also introduced into this model to represent locations of slower traffic flow or stop sign restrictions where point turns and linear turns are not defined. Impedance points are considered as a third type of turn together with point turns and linear turns, and are easily recorded in the point- turn table without any additions to the table’s attributes.
Table 2.6: Lane Table
FIELD
TYPE
DESCRIPTION
Lane_ id
Alpha- numeric
Unique Lane Identifier
Street_ id
Alpha- numeric
Street Identifier
From
Real Number
Start position of lane
To
Real Number
End position of lane
The point- turn table records points on a lane where turns become available. The six fields of the point- turn table are lane_ id, turn_ id, position, to_ lane, to_ position, and impedance. The ‘ lane_ id’ field records the identifier of the lane, and the ‘ turn_ id’ field records the identifier of a turn unique to that lane. The ‘ lane_ id’ together with the ‘ turn_ id’ form a composite key for the point- turn table. The ‘ position’ field records the position on the lane where the turn is being made from, the ‘ to_ lane’ field records the destination lane, and the ‘ to_ position’ field records the position on the lane where the turn is being made to. The ‘ position’ field and ‘ to_ position’ field record positions as linear offsets from the starting point of the origin lane and the destination lane, respectively. The ‘ impedance’ field represents the impedance of the turn. Assigning a negative value to the impedance indicates the turn is impossible. Table 2.7 illustrates the structure of the point- turn table.
Table 2.7: Point- Turn Table
FIELD
TYPE
DESCRIPTION
Lane_ id
Alphanumeric
Unique lane identifier
Turn_ id
Alphanumeric
Unique ( to the lane) turn identifier
Position
Real numbers
Start position on origin lane
To_ lane
Alphanumeric
Destination lane
To_ position
Real numbers
End position on destination lane
Impedance
Real numbers
Impedance of the turn
Linear turns represent segments ( instead of points) along lanes where transitions between lanes can be made. The most common and intuitive example of a linear turn is a lane change. The structure of the linear- turn table is slightly altered from that of the point- turn table, but the fields are analogous to each other. Table 2.8 illustrates the replacement of the ‘ position’ field with the ‘ start’ and ‘ end’ fields, and the replacement of the ‘ to_ position’ field with the ‘ to_ offset’ and ‘ distance’ fields. The remaining fields represent the same information as in the point- turn table. A linear turn defines turn availability along a section of a lane, not a point, which explains the ‘ start’ and ‘ end’ fields. The ‘ start’ field represents the beginning of turn availability along the
17
CCIT Research Report: Differential GPS Evaluation for Enhanced Probe Vehicles
lane, and the ‘ end’ field represents the end of turn availability along the lane. The ‘ start’ and ‘ end’ fields record positions as linear offsets from the beginning of the origin lane. It should be noted that the lane may be curved, and the term ‘ linear offset’ refers to the linear distance along the lane centerline. The ‘ to_ offset’ field represents the location ( recorded as an offset) along the destination lane that is longitudinally equivalent to ‘ start’. Recall that the ‘ start’ position is recorded in reference to origin lane; the ‘ to_ offset’ field records the same information as the ‘ start’ field, but the ‘ to_ offset’ records the information relative to the destination lane. The ‘ distance’ field records the linear distance required to complete the turn. The final destination point along to_ lane ( again as an offset) can be calculated with the following formula:
Destination Pt. Location = turn location + to_ offset – start + distance ( 2.10)
Table 2.8: Linear- Turn Table
FIELD
TYPE
DESCRIPTION
Lane_ id
Alphanumeric
Lane on which the turn occurs
Turn_ id
Alphanumeric
Unique turn identifier
Start
Real number
Location of the beginning of the turn on the lane
End
Real number
Location of the end of the turn on the lane
To_ lane
Alphanumeric
Destination lane of the turn
To_ offset
Real number
Location on the to_ lane corresponding to the start_ position of the turn
Distance
Real number
Linear distance required to complete the turn
impedance
Real number
Impedance of the turn
Impedance Points are used to represent impedance to normal traffic flow at points along lanes where no turns are made. This impedance could be the result of merging traffic, construction, or other legal barriers to traffic flow. The only fields required to record an impedance point are ‘ position’ and ‘ impedance,’ along with an ID field. Luckily, these fields are present in the point- turn table. The fields which are not used to record an impedance point, namely ‘ to_ position’ and ‘ to_ lane’, can simply be set to NULL when recording an impedance point to differentiate it from a point- turn. Impedance points now complete the structure of the lane- based network, and it can be seen that the relatively simple structure along with dynamic segmentation facilitates network analysis and database memory savings.
2.3.3. Map Matching Algorithms
Another critical component of this project is to perform map- matching between the GPS data points and the underlying roadway network data map. This section briefly introduces and describes map- matching algorithms as a preamble to the developed map matching technique used in this project.
As described previously, a network of linearly approximated curves ( links) connected at certain points ( nodes) can be used to represent a street map ( lane- based or centerline- based). In many navigation applications, it is often necessary to match a series of points representing a trajectory path to the lanes or streets of a map network. The points often represent GPS position measurements and are therefore subject to different sources of error, which can vary in magnitude. The method of matching the trajectory points to the map network is called map matching. Different techniques exist for map matching, and they vary in complexity and
18
CCIT Research Report: Differential GPS Evaluation for Enhanced Probe Vehicles
appropriateness for certain applications. Some basic techniques are described here and analyzed with respect to their usefulness for the application to lane- level navigation.
To formally define the problem, let us consider a vehicle moving along a system of streets ( or lanes for this project), N. At each of a finite number ( T) of discrete points in time, denoted by { 0, 1,… T}, we have estimates of the position of the vehicle. The vehicle’s true position at time t will be denoted by t P, and the estimate of the position at time t will be denoted by t P. The goal is to match each estimated position t P to a lane in N. In other words, we need to determine what lane ( link) the vehicle is on at time t.
The lane system N is not known exactly; a network representation N is used to represent this system. The network N consists of a set of curves in ℜ , each of which is referred to as an arc. The set of arcs in N is assumed to be piecewise linear. Figure 2.4 illustrates the approximation of an actual street by a piecewise linear curve. Because of this linear approximation, each arc can be completely characterized by a finite sequence of points (), each of which is in [ Bernstein & Kornhauser, 1996]. The beginning and ending points of this sequence, and , are defined as nodes, while the intermittent points, (, are defined as shape points [ Bernstein & Kornhauser, 1996].
2
0 1 na
2
0 na 1 2 na − 1
NA∈ AAA,...,, ℜ AA),...,, AAA
Figure 2.4: The Map Matching Problem
The map matching problem is to first match the estimated location, tP with an arc in the network representation of lanes, N, and then determine the actual lane in N that corresponds to the vehicle’s true position, t P. For purposes of simplification, it will be assumed that there is a one- to- one correspondence between the curves in N and the lanes in N. The complexity of the problem, though, does not increase significantly if this assumption is relaxed.
19
CCIT Research Report: Differential GPS Evaluation for Enhanced Probe Vehicles
Many algorithms exist for matching position data to node- link networks. For the purposes of this project though, map matching algorithms which make use only of geometric information will be considered. These algorithms only consider the shapes of the arcs and do not take into account the way they are connected. Three basic geometric methods, point- to- point, point- to- curve, and curve- to- curve, are examined here.
Geometric Point- to- Point Matching
Point- to- point map matching methods are perhaps the simplest way to match a set of position points to a set of curves. Each point is considered individually, and is simply matched to the ‘ closest’ curve point. The definition of ‘ closest’ depends on the metric used to measure distance, and in this case the standard Euclidean metric is often used. The Euclidean metric defines the distance between two points x and y as:
222211)()( yxyxyx−+−=− ( 2.11)
In the point- to- point matching algorithm, the distance between an estimated position tP and every node point and shape point in the network is calculated [ Bernstein & Kornhauser, 1996]. The closest point p in the network to t P is the point that the trajectory is matched to. The curve in N which contains p is then matched to t P. Of course, finding the distance between t P and all points of the network consumes unnecessary processing time. It would be t P more efficient to first find all points within a reasonable distance ( some multiple of the GPS standard deviation error) of t P and then find the distances to these points. There are currently many known algorithms which can implement this process ( called a range query) efficiently.
There are many drawbacks to using this simplistic type of algorithm for map- matching, one of which is illustrated in Figure 2.5. In this figure, the point t P is closer to 1 B than it is to either or , and thus it would be matched to the arc B. Intuitively though it can be seen that the point
0 1
t
AAP should be matched to arc A. The cause of this particular mismatch can be attributed to the fact that one arc has more points than the other. Hence, it would be natural to assume that including more points in every arc would fix the problem. This though would greatly increase the size of the database used to store the lane network N, and would not necessarily guarantee a lower mismatch rate.
Figure 2.5: One Problem With Point- to- Point Matching
20
CCIT Research Report: Differential GPS Evaluation for Enhanced Probe Vehicles
Geometric Point- to- Curve Matching
The Point- to- Curve matching algorithm proceeds analogously to the Point- to- Point matching algorithm, finding the ‘ closest’ curve to a given estimated location t P. Again the attribute of ‘ closeness’ must be defined with a given metric. To find the Euclidean distance between t P and every point of a given curve and then taking the minimum of those distances as the distance between t P and the curve would be identical to the Point- to- Point algorithm. So the distance between t P and every line segment of the curve must be found. The distance between a point and a line is defined here as the standard Euclidean perpendicular distance.
Suppose the line A containing the two points a and b is parameterized as follows:
{ λ + − λ λ ∈ ℜ } ,) 1( ba. The minimum distance [ Bernstein & Kornhauser, 1996] between A and a given point c is then:
21122222111211122)()( )]()()[(),( abbaabbacabcbaAcd−+− −+−+− = ( 2.12)
Figure 2.6 shows that finding the distance between a point and a line segment is not as straightforward as finding the distance between a point and a line. In this figure, the perpendicular distance between the point p and the line through points and is identical to the distance between the point p and the line segment with endpoints and .
0 1
0 1
AAAA
Figure 2.6: Distance Between a Point and a Segment
21
CCIT Research Report: Differential GPS Evaluation for Enhanced Probe Vehicles
The same cannot be said though for the point q. The perpendicular from the line containing and to the point q intersects the line at a point which is not on the line segment. The distance between q and each of the endpoints and must therefore be calculated, and the minimum of these two distances will be the distance from q to the line segment. Formally defined then, the distance between a point 0A
1
0 1
t
AAAP and an arc A involves finding the distance between t P and each of the line segments:
{}] 1,0[,) 1( 10∈−+ λλλAA,
{}] 1,0[,) 1( 21∈−+ λλλAA,…,
{}] 1,0[,) 1( 1∈−+− λλλAAnnAA
and taking the smallest distance.
As before with the Point- to- Point algorithm, finding the distance between tP and every arc in the network would be unnecessary. Therefore, a set of ‘ candidate’ arcs which are within a reasonable distance of t P must first be found. Even as a general improvement over the Point- to- Point algorithm, the Point- to- Curve algorithm still has faults that make it inappropriate for most practical applications.
Figure 2.7 illustrates one problem that occurs when a point is equidistant to two arcs. In this figure the point 2 P is equally close to arcs A and B, so a routine application of the Point- to- Curve algorithm would have ambiguous results as to the true location of 2 P. It can be seen though that given the previous two locations 0 P and 1 P and the assumption that the distance between 2 P and 1 P is approximately the same as the distance between 1 P and 0 P, the most likely match for the point 2 P would be curve A.
Figure 2.7: One Problem with Point- to- Curve Matching
Another common problem with Point- to- Curve Matching is the ‘ oscillation’ problem, which occurs when consecutive points in a position trajectory are matched to different arcs repeatedly. Figure 2.8 illustrates this phenomenon. Points 0 P and 2 P are slightly closer to arc A than they
22
CCIT Research Report: Differential GPS Evaluation for Enhanced Probe Vehicles
are to arc B, and point 1 P is slightly closer to arc B than it is to arc A. Therefore the curve which is matched to the trajectory points oscillates between A and B.
Figure 2.8: Another Problem with Point- to- Curve Matching
Geometric Curve- to- Curve Matching
If it can be assumed that m points { 0P, 1P,…, 1− mP} are all contained on one curve P, then a Curve- to- Curve map matching method may be used. As before, the distance between two curves must be defined. One natural definition of the distance between two curves, A and B, would be the minimum of the Euclidean distances between every possible pair of points:
baBABbAa−− ∈∈ min, mina ( 2.13)
There are some practical applications for which this metric produces reliable results, but the application of this project is not one of them. This metric is very sensitive to outlying points, which are common when GPS is used. Figure 2.9 illustrates a mismatch that can occur when this metric is used. The outlying point on P causes the curve P to be matched to arc A rather than arc B.
Figure 2.9: A problem with one metric for Curve- to- Curve Matching
A better metric should incorporate some measure of the ‘ average distance’ between two curves. It would seem to be appropriate to utilize the absolute area between two curves as a measure of the distance between them. Recalling from calculus, that the standard formula for the area between two curves f( x) and g( x) requires these two curves to be functions, and functions of the
23
CCIT Research Report: Differential GPS Evaluation for Enhanced Probe Vehicles
same variable. In general the curves that are dealt with in ℜ can be functions of x or y, and in some cases not functions at all. So the curves must be parameterized, and the distance between their corresponding points integrated over all values of the given parameter.
2
→
Suppose then that the curve A is parameterized by the function a:[ 0,1] A. Similarly the curve B is parameterized by the function b:[ 0,1] B. Then one possible measure of the distance between the curves A and B would be defined as: →
∫−=− 102)()( dttbtaBA ( 2.14)
The only problem with this measure is that it is not accurate for curves of different lengths. One solution to this problem would be to take the shortest curve and find the corresponding segment on the other curve of the same length. This is the solution employed in the map- matching algorithm develop for this project, described in Chapter 5.
24
CCIT Research Report: Differential GPS Evaluation for Enhanced Probe Vehicles
3. System Design & Methodology
With the goal of developing an automated vehicle location system that is capable of determining vehicle lane position, a number of tasks were carried out. Initially, an extensive literature search was made, evaluating whether existing commercial systems existed with this lane- level determination capability. At the time of this evaluation, no commercial systems were available. As a result, a new system was designed and developed as part of this project. This system is described in this Chapter. In Section 3.1, the overall design is described. The on- board hardware and firmware are then described in Section 3.2. The system server and the associated algorithms are described in Section 3.3.
3.1. OVERALL SYSTEM LAYOUT
The overall system design is shown in Figure 3.1. This system architecture consists of two major components: a local reference system and a rover system. The local reference system and system server are shown in a dashed box on the left and the rover system is shown in the dashed box on the right. These two components interact via a wireless communication link. On the base station computer, several tasks are carried out:
1) the base station computer receives GPS satellite data via a GPS base station receiver and subsequently sends out correction signals to the rover( s) via wireless communications;
2) the base station obtains position information from the rover unit( s) and subsequently calculates the lane position through map- matching techniques, referencing a lane- level roadway network database;
3) the base station computer also logs the position and lane parameter for each rover into a database for subsequent analysis; and:
4) the base station takes the rover position and lane information and displays the data in real- time on a map display.
These tasks are described in more detail in Section 3.3.
The rover unit contains on- board electronics that performs the following tasks:
1) the rover receives periodic GPS correction signals from the base station, allowing for approximately 2- meter level positioning accuracy; and
2) the rover sends its position data back to the base station on a periodic basis ( typically at 1 Hz). In addition, other variables can be sent, such as velocity and altitude.
The on- board electronic hardware and its tasks are described in more detail on Section 3.2.
25
CCIT Research Report: Differential GPS Evaluation for Enhanced Probe Vehicles
Wireless NetworkCloudGPSSatellitesGPS SatellitesDGPS Base Station ReceiverGPRS WirelessService CenterRTCMBroadcastingMap and ImageRenderingRT TrajectoryDatabase GenerationLane Center ReferenceGenerationLane- Level RTVehicle Tracking( Map Matching) Rover GPRS and GPSGPRSDGPSMicroprocessorUDP/ PPPRS232RS232InternetRoverBase Station Computer
Figure 3.1. Overall System Architecture of Lane- Level AVL System.
This architecture was chosen to best meet the requirements of the lane- level positioning, while remaining at a low cost. It is important to note that the GPS corrections could be acquired through the use of GPS receivers that can receive WAAS ( wide area augmentation system) signals, thereby eliminating the need for sending our own correction signals from the base station. However, through extensive experimentation, it was found that the positional accuracy using WAAS was not quite as good as with our own corrections ( approximately 3 meters instead of < 2 meters), and that the WAAS- based positioning method is inconsistent depending on the location of the system. For these reasons, it was determined to calculate our own correction signals and use them for consistent positional accuracy of approximately 2 meters.
3.2. ON- BOARD HARDWARE AND FIRMWARE
Researchers at the University of California- Riverside College of Engineering- Center for Environmental Research and Technology ( CE- CERT) have had a long history for developing custom- designed telematics units for transferring information to and from vehicles and monitoring base stations. In particular, they have developed several generations of hardware that allow for enhanced carsharing. In this application, on- board telematics hardware is used for
26
CCIT Research Report: Differential GPS Evaluation for Enhanced Probe Vehicles
vehicle access control, vehicle position monitoring, and two- way messaging between a monitoring system and the vehicles. Further details on this is provided in [ Barth et al., 2000; Barth & Todd, 2000; and Barth et al., 2001]. Further, similar hardware has been used for tracking fuel cell vehicles and sending real- time fuel cell vehicle performance data [ Todd et al., 2005]
Similar on- board hardware has been developed for this enhanced AVL project. The overall on- board hardware block diagram is shown in Figure 3.2. The three primary components are: 1) a microcontroller; 2) a GPRS ( General Packet Radio System) wireless modem; and 3) a differential GPS receiver. A picture of the on- board hardware and the connecting components are shown in Figure 3.3. Rover GPRS and GPSGPRSDGPSMicroprocessorUDP/ PPPRover PPP
Figure 3.2. On- Board Hardware Block Diagram
In this picture, several of the components are shown. The key components are as follows:
HC12 Microcontroller:
The heart of the on- board system is a multi- purpose microcontroller based on the Motorola HC- 12 architecture. The actual microcontroller is the Motorola 9S12DP256 that has 256 kbytes of flash memory, two serial ports, a CAN- bus interface, and several other functions. The microcontroller operates at a speed of 40MHz with a 20MHz bus speed. The firmware for the microcontroller program is directly flashed to memory. The firmware for this application is very straightforward. It initializes the GPS receiver to provide position and velocity information at 1 Hz., generating an interrupt when the data are available. It also initializes the GPRS modem with a set of AT commands. If the GPRS signal is lost, the microcontroller detects this and initiates a reacquire process. During normal operation, the microcontroller simply waits for interrupts from either the GPRS modem or the GPS receiver. If the interrupt comes from the GPS receiver, then the data are collected and sent out to the GPRS modem. If an RTCM message ( see below) arrives from the GPRS modem, then the corrections are processed and send on to the GPS receiver. The program continually loops until it is powered off. GPS data ( UTC time, latitude/ longitude, velocity) are sent at 1 Hz. RTCM messages are acquired approximate once
27
CCIT Research Report: Differential GPS Evaluation for Enhanced Probe Vehicles
per 30 seconds. The bandwidth requirements of this application are fairly low, well below the GPRS practical bandwidth of 20 to 50 kbps.
GPRS Modem:
The GPRS modem module is capable of wide- area cellular data communications. Cellular data communications, considered as a wireless IP network, is now a widely accepted available in North America. It primarily provides packet data service for mobile users by automatically utilizing idle cellular phone channels to send packet data traffic. As such, this service provides the largest wireless data network in North America and has been the primary target of ITS applications that require wide- area data communications. A mobile end system communicates with the wide- area cellular network via a raw duplex wireless link which is shared by several mobile end systems. Packets from network to end systems are broadcasted, thus establish a connectionless downlink. For the reverse direction or uplink, the GPRS service follows traditional slotted, non- persistent Carrier Sense Multiple Access/ Collision Detection protocol ( CSMA/ CD). Additional intelligent wireless techniques such as frequency hopping, RS code, roaming, and dynamic channel relocation are used to provide a fairly robust data channel. The primary benefit of the cellular data service is its wide area coverage at a reasonable cost.
The G20 OEM GPRS modem has a TCP/ IP stack that connects with the microcontroller through a serial port. The G20 module is controlled through a suite of AT commands. Once the board powers up, the software will automatically set up a GPRS wireless data session with pre- configured parameters like server IP address, port etc. The modem is usually set up to send UDP packets, but TCP/ IP packets are also possible.
GPS Receiver:
The GPS receiver used in this project is an Ashtech A12 OEM module, capable of tracking 12 GPS satellites simultaneously. The A12 module is extremely power efficient, and is capable of differential operations. It accepts the Radio Technical Marine Service standard ( RTCM 104) for differential corrections. This standard encapsulates the pseudorange correction, which the A12 can interpret. Similar to the GPRS modem, the GPS OEM module communicates with the microcontroller through a standard serial port. The GPS receiver is configured via commands that are sent to it from the microcontroller. The GPS module is set up to accept RTCM corrections which are received from the GPRS module and sent to the GPS receiver via the microcontroller. Under best conditions, the positional accuracy of the receiver is approximately 2 meters for a 90% CEP. In addition to position ( latitude, longitude, and altitude), the GPS unit reports on velocity using Doppler signal processing. The GPS unit also reports time which is used as a timetag with the data.
Ancillary Components:
The entire on- board unit is approximately 6 inches by 6 inches by 2 inches in size. It requires 12 volts from the vehicle, and on- board power management circuitry conditions the voltage for the on- board components. There is also a programming port for the unit, which can be used to reprogram the microcontroller program.
28
CCIT Research Report: Differential GPS Evaluation for Enhanced Probe Vehicles
For the antennae, a separate magnetic antenna is available which can simply be attached to the metallic roof of the vehicle. The GPRS modem also needs a small whip antenna ( like most cell phones). Both of these antennae can be handled with a single dual- antenna unit which is shown in Figure 3.4. GPS AntennaDifferential GPS receiverGPRS modem12v powerHC12 Microcontroller
Figure 3.3. On- Board electronics and ancillary components. Dual GPRS/ GPS antenna
Figure 3.4. Dual antenna for the GPRS modem and GPS receiver.
29
CCIT Research Report: Differential GPS Evaluation for Enhanced Probe Vehicles
3.3. SYSTEM SERVER
The overall system server block diagram is shown in Figure 3.5. There are four major programs that are carried out by the system server: 1) differential GPS correction signal generation; 2) map- matching; 3) datalogging; and 4) real- time display of data. The differential GPS correction signals and their generation are described in Section 3.3.1. The map matching algorithm developed for this project is described in Chapter 5. The data logging program is described in Section 3.3.2, and the mapping program is described in Section 3.3.3. DGPS Base Station ReceiverGPRS WirelessService CenterRTCMBroadcastingMap and ImageRenderingRT TrajectoryDatabase GenerationLane Center ReferenceGenerationLane- Level RTVehicle Tracking ( map matching) RS232RS232InternetDGPS RS232RS232Internet
Figure 3.5. Block Diagram for System Server.
3.3.1. Differential GPS Correction Signal Generation
As described earlier, it was necessary to generate our own differential GPS correction signals in order to achieve the consistent accuracy required for lane- level determination. As shown in Figure 3.5, the system server is connected to a base station GPS receiver, a DG12 manufactured by Ashtech ( Thales Navigation). This device is a 12- channel code and carrier receiver that has integrated mulitpath mitigation and employs strobe correlator digital signal processing to produce RTCM SC- 104 ( Radio Technical Marine Service) differential messages of type 1, 2, 3, 6, 16, and raw data output of code and carrier at an update rate of up to 20Hz. The receiver is attached to the base station computer via a standard RS- 232 serial connection. A separate program has been written to simply obtain the differential messages from the serial port, package
30
CCIT Research Report: Differential GPS Evaluation for Enhanced Probe Vehicles
them in data packets according to either the TCP/ IP or UDP protocols, and send them to the wireless IP address associated with the rover.
In order to send the proper differential correction signals, the antenna position of the base station receiver must be accurately surveyed. This was accomplished using a pair of carrier- phase differential GPS receivers capable of centimeter- level accuracy. Using the pair of receivers, one is placed at a known survey mark and the other is placed at the antenna location. After taking measurements, both sets of data are post- processed and a relative distance is calculated between the two points, again with centimeter- level accuracy.
The overall set up of our differential GPS system is based on a range- space double difference GPS implementation. In this implementation, common- mode errors are isolated and correction signals are broadcast. It assumes that all receivers in the general area have the same common- mode errors, which is a safe assumption as long as the receivers are within approximately 80 kilometers of each other.
In terms of the mathematical equations, consider a set of measurements for satellite , mi,..., 1=
)()()()()(~ ibibbibiηχtc)( ρ++ Δ+= xxρ ( 3.1)
)()()()()(~ iririiηχtc)( ρ++ Δ+= xxρ ( 3.2)
at the base station receiver and the rover receiver respectively. If the pseudoranges for the same set of satellites are measured at both locations, then a pseudorange correction can be determined at the known base- station location for use by the receiver at other locations. Given the base station measurements, the differential pseudorange correction is calculated as: bx
)()( )()()()(~ ibibbibiiηχtc)( ρ++ Δ= −= Δxxρρ ( 3.3)
Additionally, each GPS measurement is corrupted by errors due to the receiver’s clock. At a given time, the receiver clock errors are identical for all satellites. Double differencing is the process of subtracting the differentially corrected measurements of one satellite from the differentially corrected measurements of all the other satellites, to eliminate the common- mode error and clock errors. The advantage of double differential GPS is that the base and rover clock bias and drift rates are removed. Therefore, these terms need not be estimated. However, the multipath errors and the receiver noise between different measurements are correlated. At the rover, given pseudorange corrections , the double difference linearized measurements between satellite i and j are calculated ( left) and modeled ( right) as mi,..., 1,= Δρ i
( )
( 3.4) )()( 0)()()( ijijijijηRρδδ+=∇− Δ∇ xhx
where
))(~())(~()()()()()( jjiiijρρρρρΔ−− Δ−= Δ∇ xx 31
CCIT Research Report: Differential GPS Evaluation for Enhanced Probe Vehicles
)()( 0)( 0)()( xxjiijRρρ−=∇
)()()()()( jbjribirijηηηηη+−−= δ
)()()( iiijhhh−= .
Tzyx],,[= x
and
0)()()( )( xxh= ⎥⎦ ⎤ ⎢⎣ ⎡ ∂ ∂ ∂ ∂ ∂ ∂ = zyxiiiiρρρ
is a unit vector from the satellite to receiver linearization point . 0x
Given a set of differential range corrections available at the rover for the satellites of interest, the estimates of the rover DGPS position error and position are estimated as: )( iρΔ
( 3.5) ) ( ˆ ) ˆ ˆ ( ˆ 1RρHHHx∇− Δ∇=− TTδ
xxx ˆ ˆ 0δ+= ( 3.6)
where forms as corresponding row component of measurement . )( ijhH ˆ
Once the common- mode errors are essentially removed from the rover’s position estimate, only the non- common- mode errors remain, providing position estimates with a standard deviation between 0.1 and 4.0 meters, depending on receiver design and multipath mitigation techniques. Based on our experimentation, we have consistently gotten measurements with approximately 2 meters precision.
As described above, the corrections are sent out from the base station computer in the form of RTCM messages. These messages are sent via the GPRS wireless cellular data channel in the form of UDP data packets. The packets are then received and processed by the rover ( see Section 3.3.1). In terms of data latency, there will be delays caused by the server, Internet traffic, and the wireless network. The common- mode noise sources are continuous and slowly time varying and have significant short- term correlation [ Farrell & Barth, 1999]. The effect of latency between the time of calculation and the time of use can be accommodated through a first– order polynomial:
)( )( )( )( DGPS0DGPS0DGPS0tttttttt− ∂ Δ∂ + Δ= = ( 3.7) 32
CCIT Research Report: Differential GPS Evaluation for Enhanced Probe Vehicles
where is a reference time defined by the base, 0t)( 0DGPStΔand 0)( DGPStttt=∂ Δ∂ are the values of the correction and the correction rate both valid at time , and t is the time at which the correction will be applied. According to Eq. ( 3.7), the rover compensates the latency effect on the differential corrections before they are being applied to the Eq. ( 3.4) to remove the common- mode error in the pseudorange measurements. Through experimentation, it was found that the differential GPS measurements do not lose significant precision with latency less than 30 seconds. 0 t
3.3.2. Data Logging Program
The base station computer also receives data packets from the rovers, containing the following rover information:
• UTC time stamp;
• Latitude;
• Longitude;
• Altitude; and
• Vehicle velocity;
This information is then sent to the map matching process ( described in detail in Chapter 5) that is also running on the base station computer, whose result is a lane determination for that particular rover. The rover’s ID and the lane number are then added to the received data. The data are then formed as single line entries in a MS Access database, as shown in Figure 3.6. The MS Access database is a convenient database format, it can be read from a number of other analysis tools. Further, we use MS Access since it can be used as a real- time accessible database, meaning that other processes can access the database at the same time that data are being written to it. We take advantage of this characteristic with our real- time mapping program, described in the next section.
3.3.3. Real- Time Mapping Program
As the rover position data are recorded into the MS Access database, a real- time mapping program has been created to display these positions in real- time. This program ( called LaneMatcher) was written in Visual C++ for a Windows- based personal computer. The program makes use of ESRI’s MapObjects toolset [ ESRI, 2005]. MapObjects is an ActiveX control library which can be used with multiple programming environments to display points, lines, rectangles, ellipses, and polygons onscreen. The MapObjects control allows for multiple functionalities, such as zooming, panning, tracking, coordinate transforms, and many more. MapObjects allows for the creation and editing of shapefiles, which in turns allows for the creation and editing of lane- based data structures. For further details on MapObjects, see [ ESRI, 2005].
33
CCIT Research Report: Differential GPS Evaluation for Enhanced Probe Vehicles
Figure 3.6. Example MS Access database table of the recorded rover data.
The LaneMatcher program is shown in Figure 3.7. It consists of a mapping area, menus and icons near the top, and status data on the bottom. In the mapping area of the program, various standard map objects can be opened and displayed. This includes standard shapefiles ( e. g., lines, polygons, etc.) as well as images. In Figure 3.7, several items are visible in the mapping display:
1) a geo- rectified aerial image of the roadway and its surroundings;
2) the lane- based data structure as a shapefile ( green lines);
3) the rover vehicle current position indicated by a red circle; and
4) the vehicle “ trail”, i. e., the last few data points of the vehicle: the longer the tail, the faster the vehicle is traveling.
Near the bottom of the program, various data items and check boxes can be observed:
1) the database position data field given in latitude, longitude, time stamp, and speed;
2) the lane position, as determined by the lane matching algorithm; 34
CCIT Research Report: Differential GPS Evaluation for Enhanced Probe Vehicles
3) a check box to enable real- time vehicle tracking ( from a “ live” MS Access database of real- time positions; and
4) a check box to enable the display of a pre- recorded database.
Figure 3.7. LaneMatcher Program.
Near the top of the program, various menu items and icons can be observed. These are as follows:
1) File menu: this allow the user to open various data items including shapefiles, images, etc. A user can also create a new database and save to a standard format;
2) Edit menu: this menu allows for standard editing commands, such as undo, cut, copy, paste, etc.;
3) View menu: this menu allows for the display of the toolbar ( i. e., icons) and status bar ( shown at the bottom of Figure 3.7). In addition, “ Options” can be selected from the View menu. The options that are available are shown in Figure 3.8 and described below.
4) Help menu: this is a standard help menu that provides ( brief) instructions to the user.
35
CCIT Research Report: Differential GPS Evaluation for Enhanced Probe Vehicles
The options screen is shown in Figure 3.8. From this screen, the user can:
1) select which logged database to display;
2) select the location of the real- time datalog;
3) select the color of the lane drawings;
4) select various options such as recentering the display with each new data point;
5) select the number of tail points the user wants to see; and
6) adjust the parameters of the map matching algorithm, as described in further detail in Chapter 5.
Figure 3.8. LaneMatcher Program Options.
36
CCIT Research Report: Differential GPS Evaluation for Enhanced Probe Vehicles
4. Lane- Level Roadway Network Data Establishment
As described in Chapter 2, commercially- available lane- level roadway network data are not readily available. Therefore in this project, two lane- level roadway network acquisition techniques were developed. The first is based on an in- situ surveying technique, where data are collected while driving on the roadway of interest, described in Section 4.1. The second technique is based on aerial imagery ( photogrammetry) and subsequently processing, described in Section 4.2.
4.1. IN- SITU SURVEYING TECHNIQUE
A new method for acquiring lane- level roadway network data was developed as part of this project. This method is based on using a vehicle equipped with high- precision carrier- phase DGPS instrumentation and subsequently driving on roadways of interest. Simultaneously, it is necessary to also capture roadway feature data ( based on human or computer visual processing) at the same time of traveling down the center lane of any roadway. The visual data can then be post- processed, resulting in a fairly accurate lane- based roadway representation. Much of this work was accomplished as part of a Master’s dissertation with further details provided in [ Masters, 2003].
The overall method of acquiring the lane- based roadway network data is split between three software programs due to the fact that there are three distinct and unique functions in the data acquisition process. The first of these programs is a roadway- surveying program ( the Surveyor), the second is a data format conversion program ( the Linker), and the third ( the Visualizer) filters, displays, and allows manual editing of the lane- based network data. The Linker and the Visualizer could actually be combined into a single program, but for the purposes of programming simplicity they were programmed separately. There is also a fourth program ( the LaneMatcher), described in Section 3.3.3, which has the sole responsibility of matching trajectory data to the lane- based roadway networks. These four programs comprise the lane- based network data acquisition and analysis system. The entire process is illustrated in Figure 4.1.
The initial step in acquiring data for a lane- based roadway network is to record position information describing the location of the lanes. For this purpose, a carrier- phase DGPS system capable of centimeter- level accuracy is utilized in which one GPS receiver is situated in a moving vehicle ( the rover) while the vehicle travels along the street and another GPS receiver records positional information at a fixed location ( the base). The GPS receiver within the vehicle provides UTC ( Coordinated Universal Time) information to the Surveyor running on a laptop computer, while a user enters lane- relative information ( lane occupied, number of lanes, intersections, etc.) into the same program. Simultaneously on the same laptop computer another DOS- based program ( DataLogr. exe) records individual satellite information along with carrier phase information, which is used later in the post- processing program ( PNAV) to obtain the final centimeter- accurate data. The UTC timestamps that the Surveyor records are later synchronized and merged to the output of this post- processing program.
Figure 4.2 illustrates the setup of the surveying vehicle. The GPS antenna is held in place on the roof of the car by a powerful suction cup. The GPS receiver used in the rover vehicle, as well as
37
CCIT Research Report: Differential GPS Evaluation for Enhanced Probe Vehicles
at the base station, is an Ashtech Z- 12. Both receivers record satellite orbit ( ephemeris) and carrier phase information through a DOS- based program ( DataLogr. exe) which runs on a computer connected to the receiver through an RS- 232 DB9 serial interface. The Z- 12 receiver used in the rover vehicle also outputs a simple NMEA ( National Marine Electronics Association) message through a second serial port ( on the GPS receiver), which connects to a second serial port on the laptop computer. The NMEA message is parsed by the surveying program, which extracts the UTC time and records it along with the user- entered lane information. The laptop computer and the GPS receiver are powered by the car battery through the vehicle’s power port.
Figure 4.1. Acquisition and Analysis System
Figure 4.2. Surveying Vehicle Setup
38
CCIT Research Report: Differential GPS Evaluation for Enhanced Probe Vehicles
4.1.1. The Surveyor
The Surveyor was written in the Microsoft Visual Basic 6.0 programming language. The program has a simple dialog interface, which is designed to take input from the keyboard rather than the mouse, as it is often necessary to input new information quickly. Figure 4.3 illustrates the user interface. The interface is divided into three main sections. The top section (‘ upcoming data’) displays upcoming data, and is used to make transitions from one street to another. The middle section (‘ current data’) displays information concerning the current position in text boxes and circular “ bubbles” which represent the lanes. The bottom section displays miscellaneous information such as the UTC time, the most recent GPS NMEA message received, and key codes for the various commands. The key code “ shift + a” denotes the depression of the ‘ a’ key while the shift key is being held down. Table 4.1 gives a list of all key code commands which the Surveyor interprets. When the key code shift + enter is pushed, the program will open a spreadsheet file and begin recording data into it. Data will be recorded at a default interval of once every second. The output format of this spreadsheet file is discussed later in this section.
The surveying process outlined here requires that a surveyor travel in both directions along a street to record all necessary information. One of the main problems with this surveying process is that left- hand turn lanes are recorded twice. The method for eliminating duplicate left- hand turn lanes is outlined in detail later in this section.
Table 4.1. Keycodes
Keycode
Function
shift + enter
Transfer data from ‘ upcoming’ section to ‘ current’ section and begin recording into spreadsheet
shift + b
Change street name in ‘ upcoming’ section
shift + up, down arrows
Change number of lanes in ‘ upcoming’ section
shift + 1- 9
Change lane occupied in ‘ upcoming’ section
shift + w
Change lane width in ‘ upcoming’ section
shift + z
Check or un- check ltl ( left hand turn lane) box in ‘ upcoming’ section
shift + a- l
Begin new lanes or end existing lanes in ‘ current’ section
shift + left, right arrows
Change lane occupied in ‘ current’ section
shift + c
Check or un- check ltl ( left hand turn lane) box in ‘ current’ section
shift + m
Change lane width in ‘ current’ section
shift + i
Begin or end an intersection in ‘ current’ section; essentially ends and resumes recording of data in ‘ current’ section
shift + x
End current set of lanes
shift + q
Change directory of output spreadsheet file
shift + u
Close current file open for recording
shift + r
End or resume recording
shift + p
Bring up port settings dialog
shift + y
Re- center the ‘ bubbles’ which represent the current lanes
39
CCIT Research Report: Differential GPS Evaluation for Enhanced Probe Vehicles
Figure 4.3. Surveying Program Interface
Upcoming Data
The ‘ upcoming data’ section is used to enter the information for an upcoming street before actually arriving at that street. The information in the upcoming data section is transferred to the corresponding sections in the current data section when the user presses shift + enter. The upcoming data section has five inputs: street name, lanes (# of lanes not including the left hand turn lane if present), ltl ( checked if left hand turn lane present), width ( lane width in meters), and laneocc ( lane occupied, numbered from left to right starting at one; zero indicates occupation of the left hand turn lane). The corresponding key codes which can alter these inputs are shift + b, shift + up & down arrow, shift + z, shift + w, and shift + 1- 9, respectively. The width field can be left blank, in which case a default value for the lane width will be used. As an example, consider a car traveling down lane # 3 of the 3- lane wide Palm Avenue and coming up on a right turn onto the 2- lane wide Beech Avenue. In the ‘ upcoming data’ section the user would enter ‘ Beech Ave’ for the street name, ‘ 2’ in the lanes box, and ‘ 2’ in the laneocc box ( if the driver is going to stay in the outside lane after the turn). As soon as the vehicle entered lane # 2 on Beech Ave, the user would hold down ‘ shift’ and press the ‘ enter’ key. Before this though, the user would end the lanes of the previous street be holding down ‘ shift’ and pressing the ‘ x’ key, described later.
40
CCIT Research Report: Differential GPS Evaluation for Enhanced Probe Vehicles
Current Data and User Input Methods
The ‘ current data’ section displays current lane information in five text boxes, a check box, and a set of nine bubbles which represent the lanes. The first four text boxes ( street name, lanes, width, and laneocc) display the same information as their counterparts in the ‘ upcoming data’ section, except they display the current data as opposed to the upcoming data. The fifth text box, lanes altered, displays information about the most recent lane that was added or ended. The text in the lanes altered text box can be any one the following: ‘ in1’, ‘ in2’, ‘ in3’, ‘ out1’, ‘ out2’, or ‘ out3’. These text strings indicate which lanes were ended or added to the current set of lanes. For example, ‘ in1’ indicates either one lane was added to the left of the current set of lanes, or the inside lane ( lane # 1) were ended. This text is used in later processing and is not directly accessible by the user. The ‘ ltl’ check box, as before, indicates the presence of a left hand turn lane with a check, and the key code which alters the check state of this box is shift + c. To change the current lane width, the key code used is shift + m.
The nine bubbles located beneath the text boxes in the ‘ current data’ section correspond to the lanes on the street as well as to the keys a, s, d, f, g, h, j, k, and l on the keyboard. These keys are chosen because they are in a horizontal row on the keyboard. Different colors filling the bubbles indicate the presence of a lane ( green), or the occupation of a lane ( red or yellow). A yellow bubble indicates occupation of the left hand turn lane, which is only possible if the ltl check box is checked. Left hand turn lanes are not indicated in green. The bubble which would normally be green when a left hand turn lane is present is left white, but can become yellow if the left hand turn lane is occupied.
In Figure 4.3, there are currently three lanes, and the vehicle is occupying the center lane ( lane # 2). Holding down shift and pressing any of the keys a, s, d, f, g, h, j, k, or l will end any of the current lanes which are associated with those letters ( the bubbles under the letters in green). However, it is not possible to end a lane which is currently occupied ( a red or yellow bubble), or a lane which is bounded on the left and right by other lanes. Lanes must be ended one by one, from the outside. For example, in order to end the center lane ‘ g’ in Figure 4.3 the user would first have to end either lane ‘ f’ or lane ‘ h’, the two outside lanes. To change the lane occupied, the user can press shift + left & right arrow keys. In Figure 3.3, if the user held down shift and pressed the left arrow key, the ‘ F’ bubble would become red and the ‘ G’ bubble would become green, and the text in the laneocc text box would change to ‘ 1’. The information in the text boxes will change automatically with any changes in the bubbles. The user only has to worry about maintaining the state of the bubbles and the ltl check box. This type of intuitive ‘ bubble design’ was found to be the easiest to use in actual field tests, as quick changes in the lanes required quick user input.
Ending Lanes and Intersections
As described previously, the information in the ‘ upcoming data’ section is transferred to the ‘ current data’ section when the user presses shift + enter. To indicate a discrete break between different sets of lanes though, the user must end the current set of lanes by pressing shift + x, which ends all lanes ( changes all bubbles to white) and causes the program to stop recording data to the excel spreadsheet. When traffic light ( or 4 way stop) intersections are encountered, the user presses shift + i at the point where the vehicle enters the intersection ( recording is stopped) and the user again presses shift + i at the point where the vehicle leaves the intersection
41
CCIT Research Report: Differential GPS Evaluation for Enhanced Probe Vehicles
( recording starts again). During this interval when the vehicle is in the intersection ( and recording has stopped), the user can alter the number of lanes or the lane occupied just as when the program is recording data. This happens often in practice, when left and right turn pockets do not continue on across the intersection, and the user must often be quick to end these lanes before reaching the end of the intersection.
Miscellaneous Display and Input
The bottom section of the surveying program interface displays GPS NMEA messages, UTC times, recording times, recording status, and file open status. In this section there are also two check boxes, one which forces the program to synchronize with the UTC time being output by the receiver when checked, and one which records the NMEA messages in a text file when checked. The ‘ reset gps’ button clears the input buffer and resets the cycle which decodes the GPS NMEA message. The ‘ Set Rec Interval(. ss)’ button sets the recording interval to 20, 25, 50, or 100 milliseconds. The ‘ Rec Time’ box displays the time whenever any new data is recorded. The default recording interval is 1000 milliseconds ( 1 second). The ‘ recording’ bubble indicates recording status ( green = recording, white = not recording), and the ‘ file open’ bubble indicates whether or not a spreadsheet file is open for input ( green = open, white = not open). In this section there is also a quick- reference list of key code commands for user input.
The ‘ UTC Time’ box displays the current UTC time output of the GPS receiver. Upon program initialization, the UTC time display will start counting from zero, and will switch to UTC time when a message is received from the GPS receiver. If the GPS receiver stops sending messages ( which happens when the antenna loses satellite signals), the UTC time of the program will still continue counting, as an internal timer synchronizes with UTC time once the UTC time has been acquired. This internal timer synchronization would usually mean that the UTC time would only have to be synchronized once, and the program could then be disconnected from the GPS receiver and run independently. This was not possible in practice though, as it was found that the clock that Visual Basic uses is inaccurate. Even if an accurate replacement could be found for the Visual Basic Timer, other processes running on the operating system of the lap top computer could possibly interfere with the accuracy of the clock. It is best just to use the UTC time from the GPS receiver.
The key code shift + y re- centers the bubbles if they are grouped unevenly toward one side or the other. The key code shift + r toggles the recording state of the program, and can be used when stopped at an intersection or in traffic. This toggling of the recording state would be useful in situations where a large output file is undesirable. The key code shift + q changes the path and name of the output spreadsheet file, and the key code shift + u closes the current spreadsheet file open for recording.
42
CCIT Research Report: Differential GPS Evaluation for Enhanced Probe Vehicles
Figure 4.4. Port Settings Dialog
The key code shift + p brings up an options dialog ( the port settings dialog) which opens and closes the serial port and allows the user to edit the port settings. The serial port must be opened before the NMEA message can be received from the GPS receiver. The program is set to decode only one type of NMEA message, the “ GPGXP” message. The GPS receiver must be set to output this message. The port settings dialog also allows for sending individual messages to the GPS receiver, and responses are displayed as they are received. Figure 4.4 displays the port settings dialog.
Output Format
As mentioned before, pressing shift + enter initiates the recording of the lane data. When this key code is pressed, a spreadsheet is opened in the application directory with the default title “ LaneData#”, where ‘#’ is an integer starting from zero indicating how many spreadsheet files have been opened for output. A blank spreadsheet file titled ‘ ProductsTemplate’ must be present in the application directory, as this file is used as a template for creating new output files. The name and directory of the output file can be changed prior to pressing shift + enter by pressing shift + q. A new sheet titled ‘ LaneData’ will be created in the spreadsheet workbook upon initiation of recording. The output data will be stored in this sheet.
The format of data in the output spreadsheet file is illustrated in Table 4.2. There are seven columns which store data: street name, nolanes ( number of lanes), laneocc ( lane occupied), ltl ( left hand turn lane), lwidth ( lane width in meters), lanesalt ( lanes altered), and utctime. When recording begins, an exact ( 0.05 second resolution) UTC time is recorded in the utctime column, and the remaining columns are filled with the corresponding values in the ‘ current data’ section of the user interface. A ‘ 0’ in the ltl column indicates no left hand turn lane, while a ‘ 1’ indicates the presence of a left hand turn lane. A ‘ 0’ in the lwidth column indicates that no lane width was specified, so a default value will be used.
43
CCIT Research Report: Differential GPS Evaluation for Enhanced Probe Vehicles
Table 4.2. Example Surveying Output Table
Street name
Nolanes
Laneocc
Ltl
Lwidth
Lanesalt
utctime
Elm
3
2
0
0
None
7.15
Elm
3
2
0
0
None
8
Elm
3
2
0
0
None
9
Elm
2
2
0
0
Out1
9.85
Elm
2
2
0
0
None
10
Elm
2
2
0
0
None
11
ENDALL
11.2
After the first record, data will be recorded at every recording interval, which is one second by default. A one second recording interval indicates that data is recorded at every integer UTC second; a 0.25 second recording interval indicates data is recorded at every quarter UTC second ( e. g. 345.00, 345.25, 345.5, 345.75, etc.). When any change is made in the lane information, such as a change in the lane occupied or number of lanes, the exact ( 0.05 second resolution) UTC time is recorded. In Table 4.2, it is seen that when recording is initialized the exact UTC time is recorded ( 7.15 seconds). Also, when the outside lane ended the exact time was recorded as well ( 9.85 seconds). When all lanes ended, the exact time was also recorded ( 11.2 seconds). Whenever all lanes are ended ( shift + x) is pressed, or an intersection is reached ( shift + i is pressed) the text “ ENDALL” is inserted in the streetname column to indicate the end of a group of lanes. Though the GPS receiver used in this project only provides positions at integer UTC times, the positions at other times can be calculated with linear interpolation. Greater time resolution is necessary as the vehicle can travel up to 20 meters in a single second.
4.1.2. The Linker
As described previously, ephemeris and carrier phase data collected from two GPS receivers are used as input to a post- processing program called PNAV ( Precise Differential GPS Navigation and Surveying Software). The PNAV program is specifically designed to process the outputs of the Ashtech Z- 12 receivers to achieve centimeter- level accuracy for the positions of the rover. The PNAV file will output a spreadsheet value with UTC times, latitude, and longitude of the rover ( along with other information). The raw PNAV output file is edited first before being input into the data conversion program. The Linker, written in the Microsoft Visual C++ programming language, will take two spreadsheet files as input: an edited ( as described below) version of the PNAV output file, and the spreadsheet output file of the surveying program. The Linker then adds two new columns to the output spreadsheet of the surveying program: one for latitude, and one for longitude. Attaching position information to the surveying output spreadsheet file is not as simple as just matching UTC times though. The PNAV output file may have gaps, which have to be filled with a suitable interpolation algorithm. Also, the output spreadsheet file of the Surveyor contains non- integer UTC times; the positions at these times will also have to be estimated.
The PNAV file is not imported in raw form to the data conversion program. Three columns, representing the UTC time, latitude, and longitude, are extracted from the PNAV file and placed in a new spreadsheet. In the PNAV file, the UTC time is recorded in the standard time format ( HH: MM: SS). This format is converted to integer seconds in the new spreadsheet using the standard spreadsheet time functions HOUR, MINUTE, and SECOND. Assuming that the UTC
44
CCIT Research Report: Differential GPS Evaluation for Enhanced Probe Vehicles
times are placed in the ‘ A’ column, a formula would be entered in the D1 cell ( or any arbitrary free cell) as follows:
3600* HOUR( A1) + 60* MINUTE( A1) + SECOND( A1) ( 4.1)
This formula would then be pasted to the corresponding cells of the ‘ D’ column ( the ‘ A1’ in the formula above will change automatically corresponding to the cell it is pasted into). The ‘ D’ column would then display integer seconds, but when input into the data conversion program, the actual results of the formula would not be read; the literal text of the formula itself would be read instead. The results in the ‘ D’ column must again be pasted to a free column ( e. g. the ‘ E’ column) using the ‘ paste as special’ function of the spreadsheet editor. The heading of this column then should read ‘ UTCTime’ in order to be understood by the data conversion program. The headings of the latitude and longitude columns should read ‘ Lat’ and ‘ Lon’.
In summary, the data conversion program takes two spreadsheet files as input. One input file will contain three columns with the headings ‘ UTCTime’, ‘ Lat’, and ‘ Lon’; this spreadsheet file will henceforth be referred to as the ‘ edited PNAV’ file. The other input file will be the exact output of the surveying program, as illustrated in Table 4.2. The data conversion program will then output a single spreadsheet file, which is simply a copy of the output of the surveying program with two new appended columns: one for latitude (‘ Lat’) and one for longitude (‘ Lon’).
Creating Monotonic Survey Files
The UTC times recorded by the surveying program are recorded in the HHMMSS. ss format ( without colons). This format is converted to integer seconds by the data conversion program. During the process of converting the UTC times of the surveying spreadsheet file to integer seconds, the sequence of times is also made to be monotonic, if necessary. If a surveying run is made during the transition from 23: 59: 59 to 00: 00: 00 ( Greenwich Mean Time), the UTC times will not be monotonic. The UTC times of the edited PNAV spreadsheet file are also made to be monotonic. This is for the purpose of some preliminary time checks and ‘ gap filling’, which will be described in the next section.
Filling in Gaps in Survey Times
The edited PNAV spreadsheet file is run through some initial checks before gap filling is initiated. The first recorded UTC time of the edited PNAV file must be less than or equal to the first recorded time of the survey file, and the last recorded UTC time of the survey file must be less than or equal to the last recorded time of the edited PNAV file. If any of these conditions are not met, the program will terminate with an appropriate status message. Then the edited PNAV file is searched for a UTC time which matches the first recorded UTC time of the survey file. If no such time is found, then there is a gap in the UTC time sequence of the edited PNAV file which must be filled. After this ‘ initial gap’ is filled, the UTC times of the edited PNAV file are checked for any other gaps. Any gaps found are filled. This process is continued until the UTC time in the edited PNAV file corresponding to the last recorded UTC time of the survey file is reached. A formal statement of the ‘ gap filling’ problem is given below.
Let denote the position at time t, where x( t) = longitude and y( t) = latitude, and t is a non- negative integer. Given two positions, and, where , the goal ))(),(()( tytxtP=
P( t ) P( t ) t − t > 1 abab
45
CCIT Research Report: Differential GPS Evaluation for Enhanced Probe Vehicles
is to approximate all positions where t ) ( t P t t ibia < < . To approximate all such positions, a least squares algorithm is employed ( See Appendix A for more details).
The problem must be decoupled, and the gaps in the latitude and longitude will be found separately. The method for finding gaps in longitude will be illustrated here; for latitude the method is analogous. Two longitude positions are given: and . A given amount m of longitudinal positions are taken before t and after t. Let T
x( t ) x( t )
{ t , t ,...., t , t } − − + −
abab11aamamas = and denote two sets of times taken immediately before and immediately after the time gap, respectively. If there is a time gap in Tand/ or , or the edited PNAV file does not have the specified times, then the next largest set of continuous times which include t and t will be taken as a subset from Tand/ or T.
T = { t , t ,......, t , t }
T
T ( t , x( t )) t ∈ T ∪ T
11mbmbbbe+−++ seabse
Assume then that the continuous time sets are given, and that for simplicity no time gaps were found in the sets Tand . We then have ( 2m+ 2) coordinate pairs (, ) which we will apply a curve fit to. A third order curve fit will be applied to the data, as illustrated below: seiiesi
x ≅ Ar ⎥⎥⎥⎥ ⎦ ⎤ ⎢⎢⎢⎢ ⎣ ⎡ ⎥⎥⎥⎥⎥⎥⎥⎥ ⎦ ⎤ ⎢⎢⎢⎢⎢⎢⎢⎢ ⎣ ⎡ ≅ ⎥⎥⎥⎥⎥⎥⎥⎥ ⎦ ⎤ ⎢⎢⎢⎢⎢⎢⎢⎢ ⎣ ⎡ ≡ +++ −−− + − 3210323232321:::: 11:::: 1)( : )( )( : )( rrrrtttttttttttttxtxtxtxmbmbmbbbbaaamamamambbama ( 4.2)
A third order fit is used to allow flexibility ( an inflection) in the curve between the two sets of points. The solution for r which minimizes the least squares error is given as:
r = ( ATA)- 1ATx ( 4.3)
We then have a third order equation which approximates the longitudinal coordinates in the time gap:
( 4.4) 012233)( rtrtrtrtx+++≈
Then for all times , where itbiattt<<, the longitude can be calculated with equation 4.4. This method will approximate all longitudinal positions within the time gap. The method for finding latitudinal positions is analogous. The goal of approximating all positions , where , has then been accomplished. )( itPbiattt < <
46
CCIT Research Report: Differential GPS Evaluation for Enhanced Probe Vehicles
Merging the Files
After the gaps in the edited PNAV file are filled, the positions are added to the survey file. First, a copy is made of the survey file. Then two columns are added to this copy representing latitude and longitude, and titled ‘ Lat’ and ‘ Lon’. The structure of the final output table is illustrated in Table 4.3. For every UTC time t recorded in the survey file, the corresponding latitude and longitude are placed into the new columns. As illustrated earlier, the survey file will have decimal UTC times, for which the positions will need to be calculated. The latitudinal and longitudinal positions can be assumed to be linear functions of time within a one second interval. Linear interpolation is therefore used to approximate the positions at decimal UTC times. i ) ( t x
y( t )
ii
Table 4.3. Linker Output Structure
Street Name
Nolanes
Laneocc
Ltl
lwidth
Lanesalt
Utctime
Lat
Lon
Palm
3
2
1
0
None
34.35
33.9995677
117.3244129
Etc….
4.1.3. The Visualizer
At this point of the lane- based roadway network data acquisition process, all necessary data have been acquired. The next task is to store these data in a lane- based structure, and display it with a visualization program. For visualization purposes, MapObjects by ESRI is used in the Microsoft Visual C++ programming environment [ ESRI, 2003]. The lane- based data structure used to store the lane information is a non- planar structure derived from the UCSB non- planar lane- based format describe in Chapter 2. The structure used here does not use dynamic segmentation, but instead stores the data in a format that can be easily converted to a structure using dynamic segmentation later.
The lane- based data is stored as a shapefile, which is a binary file whose structure is outlined in [ ESRI, 1998]. A shapefile stores its data in a recordset, which is a table where columns are referred to as fields. Each shapefile can store only one type of shape data ( i. e. points, lines, rectangles, ellipses, or polygons), and every row of a shapefile’s recordset refers to a specific shape. The properties ( position, street name, etc.) of that specific shape are stored in the fields. The fields of the shapefile’s recordset will therefore comprise the lane- based data structure used here. MapObjects allows for the creation and editing of shapefiles, which in turns allows for the creation and editing of lane- based data structures.
The Visualizer is a Single Document Interface, which means that only one file ( document) may be opened at a time. It should be made clear here the difference between a file and a shapefile. The file is a geographic information system ( GIS), and a shapefile is a layer, as described in Chapter 2. In other words, many different shapefiles can be opened within the same file.
47
CCIT Research Report: Differential GPS Evaluation for Enhanced Probe Vehicles
Figure 4.5. Mapping Program Interface
The Visualizer is supplied with the basic functionalities as well as some specialized ones. This Visualizer can open an existing shapefile ( which will be added as a layer to the current file), save new data to a new shapefile, and append new data to an existing shapefile. The Visualizer can also zoom in, zoom out, and pan on any open shapefile. Some of the specialized abilities of the program include importing spreadsheets, adding and deleting lanes, searching for specific lanes, and manually editing the fields of a specific lane. All functions can be selected from the menu or from the toolbar. Figure 4.5 shows the user interface, with a zoomed- in view of some street lanes.
Importing Spreadsheets
The output of the Linker described in Section 4.1.2 can be directly imported into the Visualizer. The Visualizer must decode the information in the spreadsheet file to create a set of polygons ( lanes). A polygon is completely described by a set of points which represent the boundary of the polygon. The import function will record the position data from each row in the spreadsheet and use the information in the other columns to determine where each lane should be positioned. It is important here to denote the difference between importing a spreadsheet and saving a set of
48
CCIT Research Report: Differential GPS Evaluation for Enhanced Probe Vehicles
polygons to a shapefile. Importing a spreadsheet simply displays the polygons onscreen on what is called the tracking layer; if the result is satisfactory the