Map Matching I

Problem Statment:
In general , Global Positioning System (GPS) has been widely used in Vehicle Navigation Systems. It helps the users to determine the vehicle position or provides users with proper maneuver instruction .Because of some biases, such as SA effect, buildings canyon around cities , thus those affect and block GPS signals .In addition , the road network of the digital Map is not accurate enough. These cause vehicle position not to locate precisely on the road network of the digital map. Therefore a map-matching algorithm is necessary. An optimal algorithm is developed through the analysis of some driving conditions (such as turning. U-turn or drive to parking lots).The algorithm is presented.

How the algorithm works:
Assuming that GPS point is G1 with coordinate (XG1, YG1), from-node of
road is S1 with coordinate (XS1, YS1), to-node of road is E1 with coordinate (EE1, YE1).
The value of K can be determined.

where θ is the angle between vector S1G1 and S1E1

1) if 0<= K <=1 then the prependicular distance between G1 and the road is:

( (XG1-XN)^2+(YG1-YN)^2)^1/2

The (Xn, Yn) are the coordinates of the projected point of the road:
XN=K*(XE1-XS1)+ X S1
YN=K*(YE1-YS1)+ YS1

2) If K <>

3) If K > 1, then the vehicle location is not on the candidate road, and the location is away from the to-note E1

in case like the following:

the candidate road of G1 is either line1 or line2. The possibility of making wrong decision is very high. To solve this problem we consider the vehicle traveling direction. In digital road map database the true azimuth (which is a mathematical concept defined as the angle)of road is recorded, and NMEA data also includes the vehicle direction. Therefore, we can compare these two any try to select the candidate road.

After selection of the candidate road, We assume current vehicle location is in G1, next vehicle location is G2, if the distance between G1, and E1, (end-node of road segment) are close to a pre-set value, the next turning candidate road will be Line1, Line2 and Line3. G1E, is the azimuth of traveling direction from G1, to E1, point, G2E, is the azimuth from E1, to G2, point. These values of azimuth will be used for judging which road is the candidate. If driver has a U-turn, the from-node and to-node of road segment must be switched. Assuming current vehicle location is at G1, point, the location of former epoch is G0, endnode of road segment is E1,

ΔHEADING = G1a - G0a

G1a: azimuth of G1E1,G0a : azimuth of G0E1

If ΔDISTANCE is negative and larger then a tolerant value and
ΔHEADING > Tolerance, we presume, we presume vehicle has a U-Turn.

Vector Maps

Vector Map (VMAP), AKA Vector Smart Map, is a vector-based collection of GIS data covering the earth at various detail levels. Level 0 (low resolution) coverage is global, and is entirely in the public domain. Level 1 (global coverage at medium resolution) is only partly in the public domain.

Description

• Coordinate reference system: Geographic coordinates stored in decimal degrees with southern and western hemispheres using a negative latitude and longitude

Thematic data layers

Features and data attributes are tagged utilizing the international Feature and Attribute Coding Catalogue (FACC).

1. major road networks
2. railroad networks
3. hydrologic drainage systems
4. utility networks (cross-country pipelines and communication lines)
5. major airports
6. elevation contours
7. coastlines
8. international boundaries
9. populated places
10. index of geographical names

Levels of resolution

The vector map product comes in three flavors: low resolution (level 0), medium resolution (level 1) and high resolution (level 2).

Level Zero (VMAP0)

Level 0 provides worldwide coverage of geo-spatial data and is equivalent to a small scale (1:1,000,000). The data are offered either on CD-ROM or as direct download, as they have been moved to the public domain. Data are structured following the Vector Product Format (VPF).

Data sets

The entire coverage has been divided into four data sets:

1. North America (NOAMER)
2. Europe and North Asia (EURNASIA)
3. South America, Africa, and Antarctica (SOAMAFR)
4. South Asia and Australia (SASAUS).

Level One (VMAP1)

Level 1 data are equivalent to a medium scale resolution.

• Horizontal accuracy: 125-500m
• Vertical accuracy: 0.5-2m

Data sets

VMAP Level 1 is divided in 234 geographical tiles. Only 57 of them are currently (2006) available for download from NGA. Amongst the available datasets, coverage can be found for parts of:

• Costa Rica
• Libya
• United States
• Mexico
• Iraq
• Russia
• Panama
• Colombia
• Japan

Level Two (VMAP2)

Level 2 data are equivalent to a large scale resolution.

Debate about availability of data

The U.S.A. Freedom of Information Act and the Electronic Freedom of Information Act guarantee access to virtually all GIS data created by the US government. Following the trend of the United States, much of the VMAP data has been offered to the public domain.

Still many countries consider mapping and cartography a state monopoly; for such countries, the VMAP Level1 data are kept out of the public domain. With the privatization of public agencies, some data are sold for a profit.

Efforts are being made by various public groups towards moving all VMAP1 data to the public domain.

Further steps have been taken (by the Free World Maps Foundation among others) to licence the data under the GNU General Public License while remaining copyrighted, as an alternative to the public domain. This is an ongoing debate (as of 2006), of which the outcome is yet to be seen.

Tools to read and convert VMAP data

• VPFView (V2.1) - developed by NIMA, is available from NGA or USGS (as part of the NIMAMUSE package); this tool can render simple plots and export GIS data to other GIS file formats
• "OGR with OGDI driver": this free software tool can convert VMAP format to standard GIS file formats such as SHAPE, PostGIS etc.

References

Main Reference

http://en.wikipedia.org/wiki/Vector_Map

NGA Home Page

http://www.nga.mil

Good Article about vector product format

http://www.nga.mil/portal/site/nga01/index.jsp?epi-content=GENERIC&itemID=a2986591e1b3af00VgnVCMServer23727a95RCRD&beanID=1629630080&viewID=Article

Vector product format standards

http://www.nga.mil/NGASiteContent/StaticFiles/OCR/vpf_main.pdf

Connecting to the sattellites !!

As GPS units become more common and less expensive, a whole new set of location-aware applications and services are popping up to take advantage of its capabilities. If you are one of the thousands of software developers tasked with adding GPS capability to an application, you have probably come across the NMEA 0183 standard, the protocol by which GPS units communicate with other devices. Since decoding the NMEA 0183 standard is the key to integrating GPS data in your VB, C# or C++ project, let's examine some strategies for handling NMEA 0183 output.

The Big Picture

Before we dive into the guts of the NMEA 0183 standard, let's take a step back and examine how the NMEA 0183 data stream fits into the larger structure of our application. There are three hurdles that we must first overcome before we can begin decoding the NMEA 0183 stream and using the data in our application:

1) Getting the hardware connection right

GPS hardware connections come in three common varieties: serial port, USB, or Bluetooth. To read NMEA 0183 data from a GPS, we must make these connections look like COM ports to the PC. If the GPS connects to the PC through a serial port, we're in luck since this is already done. If we have a USB GPS, we must either install the USB drivers that came with the GPS, or purchase a USB to serial port converter. If using a Bluetooth GPS, the OS bluetooth manager (device pairing wizard) or the manufacturer's driver software can map it to any COM port.

2) Reading from the COM port in your application

Now that we have the COM port set up, how can we read from it in our application? This is, without a doubt, the most challenging part of reading NMEA 0183 data. In fact, reading from a COM port in a Windows application can be so difficult. So if you have some time on your hands, you can learn to read from the COM port yourself, otherwise it might be worth looking into a good, multithreaded 3rd party control.

3) GPS portability

some GPS devices don't send the complete NMEA 0183 sentance, instead they chose only part of it !! so if you want to design a protable software that will work with all kinds of GPS devices, you may want to put this into consideration and make your code generic.

Parsing the NMEA 0183 Stream

The NMEA 0183 data stream consists of a series of "sentences" delimited by a newline character. Each sentence begins with a six character identifier, the first character of which is always "$".

The most useful sentences include:

$GPAAM - Waypoint Arrival Alarm
$GPBOD - Bearing, Origin to Destination
$GPBWW - Bearing, Waypoint to Waypoint
$GPGGA - Global Positioning System Fix Data
$GPGLL - Geographic Position, Latitude/Longitude
$GPGSA - GPS DOP and Active Satellites
$GPGST - GPS Pseudorange Noise Statistics
$GPGSV - GPS Satellites in View
$GPHDG - Heading, Deviation & Variation
$GPHDT - Heading, True
$GPRMB - Recommended Minimum Navigation Information
$GPRMC - Recommended Minimum Specific GPS/TRANSIT Data
$GPRTE - Routes
$GPVTG - Track Made Good and Ground Speed
$GPWCV - Waypoint Closure Velocity
$GPWNC - Distance, Waypoint to Waypoint
$GPWPL - Waypoint Location
$GPXTE - Cross-Track Error, Measured
$GPXTR - Cross-Track Error, Dead Reckoning
$GPZDA - UTC Date/Time and Local Time Zone Offset
$GPZFO - UTC and Time from Origin Waypoint
$GPZTG - UTC and Time to Destination Waypoint

(A complete reference with detailed examples can be found at Glenn Baddeley NMEA sentence information page and at Peter Bennett's GPS and NMEA site)

For the sake of simplicity, let's will assume that we are only interested in position, speed, and course data. Looking at the available NMEA 0183 sentences, we see that the $GPRMC sentence contains all the information we need.

The format of the $GPRMC sentence is:

$GPRMC,aaaaaa,b,cccc.cc,d,eeeee.ee,f,ggg.g,hhh.h,jjjjjj,kkk.k,l*mm

Where:

aaaaaa is the time of the fix UTC in hhmmss format
b is the validity of the fix ("A" = valid, "V" = invalid)
cccc.cc is the current latitude in ddmm.mm format
d is the latitude hemisphere ("N" = northern, "S" = southern)
eeeee.ee is the current longitude in dddmm.mm format
f is the longitude hemisphere ("E" = eastern, "W" = western)
ggg.g is the speed in knots
hhh.h is the true course in degrees
jjjjjj is the date in DDMMYY format
kkk.k is the magnetic variation in degrees
l is the direction of magnetic variation ("E" = east, "W" = west)
mm is the checksum

Getting the position, speed, and course data in which we are interested now just becomes a matter of reading the $GPRMC sentence into a string, parsing the string to extract the pertinent data, and converting the data into the proper units.

-------------------------------------

refrence : http://www.scientificcomponent.com/nmea0183.htm