Abstract:
The present invention provides systems and methods for improving the accuracy of location data, such as GPS data. In an embodiment, the present invention adjusts coordinates by receiving a sequence of coordinates corresponding to a plurality of locations; identifying in a map database, for each location, polyline features within a distance from the coordinates for the location; calculating emission probabilities for the polyline features; calculating transition probabilities for the polyline feature; and adjusting the coordinates for the plurality of locations so that the adjusted coordinates correspond to polyline features belonging to a sequence of polyline features selected, based on the emission probabilities and the transition probabilities, to be the most likely sequence of polyline features that correspond to the sequence of coordinates. Besides improving accuracy, embodiments of this invention enable novel geospatial applications and user interfaces by adding a large amount of meta-information to a location.

Description:
FIELD OF THE INVENTION 
     The present invention relates to satellite-based positioning systems. More particularly, it relates to registration of location data to street maps. 
     BACKGROUND OF THE INVENTION 
     Global Positioning System (GPS) devices generate location data. The generated location data (e.g., latitude and longitude values), however, are not completely accurate. Particle filtering and Kalman filtering have both been used in an attempt to improve the accuracy of GPS location data. While these filtering techniques can be advantageous, both techniques have limitations. For example, both particle filtering and Kalman filtering do not give globally optimal solutions. Furthermore, both particle filtering and Kalman filtering typically require significant computing resources such as memory and processing time. Accordingly, there is a current need for new devices and techniques that overcome these and other deficiencies. 
     BRIEF SUMMARY OF THE INVENTION 
     The present invention provides systems and methods for improving the accuracy of location data generated, for example, using a satellite-based positioning device, and applications thereof. In an embodiment, a system according to the present invention includes a spatial indexer, an emission probability calculator, a transition probability calculator, and a pose optimizer. The spatial indexer receives a sequence of location data corresponding to a plurality of locations. For each location, the spatial indexer identifies in a map database polyline features within a distance D from the location. The emission probability calculator calculates emission probabilities for the polyline features identified by the spatial indexer. Each emission probability E ij  represents the probability that a street on the map represented by a polyline feature P j  emitted the observed location C i . The transition probability calculator calculates transition probabilities for the polyline features identified by the spatial indexer. Each transition probability T xy  represents the probability of a transition from a polyline feature P x  to a polyline feature P y . The pose optimizer adjusts the location data for the plurality of locations so that the adjusted location data correspond to polyline features belonging to a sequence of polyline features selected based on the emission probabilities calculated by the emission probability calculator and the transition probabilities calculated by the transition probability calculator. 
     In an embodiment, the present invention adjusts coordinates obtained using a satellite-based positioning device by (1) receiving a sequence of coordinates corresponding to a plurality of locations; (2) identifying in a map database, for each location, polyline features within a certain distance from the coordinates for the location; (3) calculating emission probabilities for the polyline features; (4) calculating transition probabilities for the polyline features; and (5) adjusting the coordinates for the plurality of locations so that the adjusted coordinates correspond to polyline features belonging to a sequence of polyline features selected based on the emission probabilities and the transition probabilities. 
     Besides improving accuracy, snapping GPS locations to street locations on a map enables novel geospatial applications and user interfaces by adding a large amount of meta-information to a location, such as the street address, navigation information (connected streets and intersections), nearby business information, etc. 
     Further embodiments, features, and advantages of the invention, as well as the structure and operation of the various embodiments of the invention are described in detail below with reference to accompanying drawings. 
    
    
     
       BRIEF DESCRIPTION OF THE FIGURES 
       Embodiments of the invention are described with reference to the accompanying drawings. In the drawings, like reference numbers may indicate identical or functionally similar elements. 
         FIG. 1  is a diagram that illustrates an example street map with a sequence of location data adjusted to a location of polyline features on a map. 
         FIG. 2  is a diagram that illustrates a system according to an embodiment of the present invention that adjusts a sequence of location data to the location of polyline features on a map and that displays the adjusted data to a user. 
         FIG. 3  is a diagram that illustrates the system of  FIG. 2  in more detail. 
         FIG. 4  is a flowchart that illustrates a method for adjusting location data to the location of polyline features on a map according to an embodiment of the present invention. 
         FIGS. 5A and 5B  are diagrams that illustrate an example of how features are recalled for a particular location according to an embodiment of the present invention. 
         FIG. 6A  is a diagram that illustrates an example of how transition probabilities are calculated according to an embodiment of the present invention. 
         FIG. 6B  is a diagram that illustrates an example of how emission probabilities are calculated according to an embodiment of the present invention. 
         FIG. 6C  is a diagram that illustrates an example of how location data is snapped to points on a street according to an embodiment of the present invention. 
     
    
    
     DETAILED DESCRIPTION OF EMBODIMENTS 
     The present invention provides systems and methods for improving the accuracy of location data generated, for example, using a satellite-based positioning device, and applications thereof. While the present invention is described herein with reference to illustrative embodiments for particular applications, it should be understood that the invention is not limited thereto. Those skilled in the art with access to the teachings provided herein will recognize additional modifications, applications, and embodiments within the scope thereof and additional fields in which the invention would be of significant utility. 
       FIG. 1  is a diagram that illustrates an example street map  100 . In map  100 , streets such as street  104  are represented by polyline features. Each polyline feature includes information such as, for example, geometry information, a street name, an address, turn restrictions, number of street lanes, intersection information, identification of other polyline features to which it connects, etc. 
       FIG. 1  also illustrates how a sequence of location data  106  (e.g., generated using a satellite-based positioning device carried in a vehicle) is adjusted to form a sequence of adjusted location data  108  that corresponds to a set of polyline features used to represent street  104  of map  100 . In  FIG. 1 , both the sequence of location data  106  and the sequence of adjusted location data  108  are represented by solid lines. In actuality, however, the sequence of location data and the sequence of adjusted location data can be sequences of non-continuous locations (e.g., non-continuous coordinates and headings). Such non-continuous locations (e.g., non-continuous coordinates and headings) are represented by locations  110 A- 110 N and adjusted locations  112 A- 112 N. 
     In an embodiment, each location  110 A- 110 N includes both coordinate and heading information. The coordinate information can be, for example, latitude and longitude information. As noted herein, the location data can be generated using a satellite-based positioning system device, such as a GPS receiver, carried in a vehicle. The invention is not limited, however, to using just a GPS receiver. For example, the location data can be generated using other devices and/or sensors such as a vehicle wheel encoder. A vehicle wheel encoder estimates where a vehicle is located based on wheel movements. Using the present invention, it is possible to improve the accuracy of noisy measurements obtained using such devices and/or sensors and to correctly snap location data obtained using these devices and/or sensors to a street. 
     As illustrated in  FIG. 1 , the sequence of location data  106  (e.g., locations  110 A- 110 N) is adjusted to form the sequence of adjusted location data  108  (e.g., adjusted locations  112 A- 112 N). The sequence of adjusted location data  108  corresponds to the set of polyline features that represent street  104  in map  100 . Thus, each adjusted location  112 A- 112 N corresponds to a coordinate that lies along street  104  and has a heading corresponding to that associated with street  104 . 
     As discussed earlier, conventional methods of snapping location data to a street include Kalman and particle filtering. Kalman and particle filtering snap location data on a point-by-point basis. For example, Kalman and particle filtering would snap a point (e.g., location  110 A) to a new point (e.g., location  112 A) without necessarily using information from all the other points (e.g., locations  110 B-N) optimally. Embodiments of the present invention, however, optimally snap entire sequences of locations to sequences of polyline features that represent a street. These embodiments take advantage, for example, of the connectivity and heading information about the street. In other words, these embodiments take into consideration that a GPS receiver carried in a vehicle can not easily move from one street to another, unless the streets are connected. Taking into consideration this additional information enables embodiments of the present invention to adjust/snap correctly sequences of location data. 
       FIG. 2  is a diagram of a system  200  according to an embodiment of the present invention. System  200  can adjust a sequence of location data to the location of polyline features on a map and display the adjusted data to a user. 
     In an embodiment, system  200  includes a GPS track database  202 , a map database  204 , a processing pipeline server  210 , and a street track database  220 . Data stored in street track database  220  is viewed, for example, using a street track server  230  and a street track client  250  that communicates with street track server  230  over a network  240  or using a viewer  260  coupled to street track database  220 . Each of the elements shown in  FIG. 2  can be any type of computing device. Example computing devices include, but are not limited to, a computer, a workstation, a distributed computing system, an embedded system, a stand-alone electronic device, a networked device, a mobile device, a rack server, a portable GPS device, a television, etc. 
     GPS track database  202  stores sequences of location data. The sequences of location data can be collected, e.g., using vehicles with GPS receivers and/or other sensors. Each location in a sequence of location data can include a coordinate and a heading. Each coordinate can include, for example, a latitude and a longitude. 
     Map database  204  stores information for one or more maps. These map(s) includes polyline features that represent, for example, a portion of a road, an intersection, an overpass, a bridge, a tunnel, etc. Each polyline feature typically has a unique identifier called a feature ID. 
     In an embodiment, map database  204  includes a feature index. The feature index maps the feature ID of a polyline feature to feature data. In the example of a road, feature data can include a road name, road geometry, road connectivity, whether the road is one-way or two-way, turn restrictions (e.g., no U-turns allowed), etc. Intersection features can contain feature IDs of roads terminating at the intersection. In this way, the feature index maintains, for example, information on the connectivity of the features. 
     In an embodiment, each polyline feature is accessible using a spatial index. A spatial index organizes polyline features into geographic areas called bins. In an embodiment, bins have a standard size (e.g., 50 meters by 50 meters), and each bin has a unique geographic ID (e.g., an s2cellID). Bins contain a list of feature IDs that lie within their associated geographical areas. 
     Processing pipeline server  210  processes data from the GPS track database, map database and possibly other databases (not shown). In an embodiment, processing pipeline server  210  receives a sequence of location data from GPS track database  202 . Processing pipeline server  210  adjusts the location data to correspond with polyline features in map database  204 . Processing pipeline server  210  writes the sequence of adjusted location data to street track database  220 . Street track database  220  stores the sequence of adjusted location data. In this way, processing pipeline server  210  snaps sequences of location data, as opposed to snapping individual locations. This allows processing pipeline server  210 , for example, to take into consideration knowledge of the continuity of polyline features such as streets and to correctly snap sequences of location data. 
     Processing pipeline server  210  contains a spatial indexer  212  and a pose optimizer  214 . Spatial indexer  212  and pose optimizer  214  can be implemented as hardware, software, firmware or any combination thereof. Spatial indexer  212  looks up features corresponding to particular locations from GPS track database  220 . Spatial indexer  212  gathers polyline features surrounding a location. For each polyline feature surrounding a location, spatial indexer  212  calculates the distance between the location and the polyline feature. Optionally, spatial indexer  212  also calculates a heading differential between the location and the polyline feature. The operation of spatial indexer  212  is described in more detail below. Spatial indexer  212  sends its information to pose optimizer  214 . 
     Pose optimizer  214  adjusts and/or snaps each location for a sequence of location data to correspond to a location of a polyline feature stored in map database  204 . Pose optimizer  214  uses surrounding polyline features and distances determined by spatial indexer  212  to adjust a sequence of location data. In an embodiment, pose optimizer  214  accomplishes this by treating the adjusted points as hidden states in a hidden Markov model. Pose optimizer  214  uses the Viterbi algorithm to decode the sequence of adjusted location data. The operation of pose optimizer  214  is described in more detail below. 
     Processing pipeline server  210  outputs sequences of adjusted location data determined by pose optimizer  214  to street track database  220 . In an embodiment, street track database  220  stores information such as image panoramas that correspond to locations in sequences of adjusted location data. 
     In an embodiment, data stored in street track database  220  is viewed using street track server  230  and a street track client  250  that communicates with street track server  230  over a network  240 . In an embodiment, street track client  250  includes a web browser that is used to view the data. The web browser can display, for example, an adjusted location data sequence as a line overlaying a map. When a user selects a point on a line, a photographic image taken from that location can be displayed. This example is merely illustrative and is not meant to limit the present invention. 
     In an embodiment, street track client  250  communicates with street track server  230  over a network  240  or a group of networks that together comprise the network  240  illustrated in  FIG. 2 . Network  240  can be any network or combination of networks that facilitate data communication. In embodiments, network  240  can include, but is not limited to, a local area network, a medium area network, and/or a wide area network such as the Internet. Network  240  can support protocols and technology including, but not limited to, World Wide Web protocols and/or services. Intermediate web servers, gateways, or other servers may be provided between street track server  230  and street track client  250 . 
     Street track client  250  may request adjusted location data sequence from street track server  230 . Street track server  230  retrieves adjusted location data from street track database  220 . Street track server  230  formats the adjusted location data, and as an example, street track server  230  may overlay the adjusted location data on a map. Street track server  230  may include a web server. A web server is a software component that responds to a hypertext transfer protocol (HTTP) request with an HTTP reply. As illustrative examples, the web server may be, without limitation, an Apache HTTP Server, an Apache Tomcat, a Microsoft Internet Information Server, a JBoss Application Server, a WebLogic Application Server, or a Sun Java System Web Server. The web server may serve content such as hypertext markup language (HTML), extendable markup language (XML), documents, videos, images, multimedia features, or any combination thereof. This example is strictly illustrative and does not limit the present invention. 
       FIG. 3  is a diagram that illustrates various elements of system  200  in more detail. As shown in  FIG. 3 , in an embodiment, spatial indexer  212  includes a feature finder  312  and a distance calculator  314 . Pose optimizer  214  includes, in an embodiment, an emission probability calculator  322 , a transition probability calculator  324 , a prior probability calculator  328 , and a Viterbi decoder  326 . 
     As illustrated in  FIG. 3 , spatial indexer  212  receives a sequence of location data  302  from GPS street track database  202 . Sequence of location data  302  may be collected, for example, by one or more vehicles with GPS receivers and/or other sensors (e.g., wheel encoders). Each location in the sequence of location data can include coordinate and/or heading values. In an embodiment, each location in sequence of location data  302  may be collected at regular time and/or distance intervals. In an embodiment, the sequence of location data  302  may be received in real-time or near real-time. This means that the most recently collected location data in the sequence of location data was received by spatial indexer  212  soon after it was collected. 
     For each location in sequence of location data  302 , feature finder  312  of spatial indexer  212  identifies polyline features within a radius R stored in map database  204 . The radius R should be large enough to cover all possible polyline features to which the location could map. Therefore, the radius R should be larger, for example, than the error range, at a particular confidence interval, of the GPS receiver used to determine the location. 
     In an embodiment, feature finder  312  identifies features by recalling the s2cellID for each bin within radius R. Feature finder  312  uses the spatial index to get a list of all polyline features and corresponding feature information associated with bins within radius R. As shown in  FIG. 3 , the retrieved polyline features are identified as map features  308 . Map features  308  include, for example, information such as geometry information, street name information, address information, turn restriction information, connectivity information, etc. 
     In certain situations, the bins may cover more area than the circle of radius R. As a result, polyline features may be recalled from map a database  204  that are outside the area of interest (e.g., the circle of radius R). Thus, in an embodiment, feature finder  312  includes logic that selects only features that lie within the area of interest. An example of this is described below. 
     After feature finder  312  recalls map features  308  for each location in the sequence of location data  302 , distance calculator  314  calculates a distance between each location and each feature within radius R of that location. Optionally, spatial indexer  212  may also calculate a heading differential. Each of the polyline features has an associated geometry. A heading can be determined from the geometry. As an example, if the polyline feature is a portion of a curved road, a heading can be determined by taking the derivative of the curve. A heading difference may be calculated by taking the difference between the heading associated with the polyline feature and the heading associated with the location. 
     Spatial indexer  212  sends features and corresponding distances  306  to pose optimizer  214 . Pose optimizer  214  uses this information to adjust location data  302  and to generate adjusted/snapped location data  304 . 
     In an embodiment, emission probability calculator  322  of pose optimizer  214  calculates an emission probability. The emission probability is a function of a feature and a location. The emission probability is a probability of obtaining the location, for example, from the GPS receiver given that the GPS receiver is actually at a location associated with a particular map feature. For each location, emission probability calculator  322  calculates an emission probability for each feature within radius R of the location. How to calculate emission probabilities is described in more detail below. 
     Transition probability calculator  324  calculates transition probabilities. A transition probability is a probability of transitioning to one feature, for example, given that the GPS receiver is at another feature. If a transition is allowed, for example, from one road to another road (e.g., the roads meet at an intersection and there are no turn restrictions), the transition probability is assessed to be high. If a transition is disallowed (e.g., a transition between two roads that are not connected), the transition probability is assessed to be low. In an embodiment, disallowed transitions are not completely disallowed, they are just given a relatively low likelihood of occurring. How transition probabilities can be calculated is described in more detail below. 
     Prior probability calculator  328  of pose optimizer  214  calculates prior probabilities. A prior probability is a probability that the start of a sequence of location data was measured at a particular feature. In an embodiment, prior probability calculator  328  calculates prior probabilities for each feature in a radius R of an initial location to be equally likely. 
     Viterbi decoder  326  of pose optimizer  214  adjusts the sequence of location data  302  to correspond with the locations of polyline features. In an embodiment, Viterbi decoder  326  models the sequence of adjusted location data as hidden states in a hidden Markov model. In the hidden Markov model, the sequence of location data are observable emissions from the hidden states that are given off with the calculated emission probability calculated by emission probability calculator  328 . The probability of transitioning to a second hidden state (a second polyline feature), for example, given that the GPS receiver is at a first hidden state (a first polyline feature) is defined by the transition probabilities calculated by transition probability calculator  328 . The probability of the sequence of adjusted location data starting at a particular polyline feature is defined by prior probability calculator  328 . Viterbi decoder  326  uses the Viterbi algorithm to decode the most likely sequence hidden states (the sequence of adjusted location data). 
     The Viterbi algorithm is fast and memory efficient. By using the Viterbi algorithm, Viterbi decoder  326  saves computing resources, such as memory and processor time. In embodiments, pose optimizer  214  may also use Kalman or particle filtering in conjunction with hidden Markov models. This approach is discussed in more detail below. In an embodiment, pose optimizer  214  may model a sequence of polyline features as a probabilistic context-free grammar. 
     Once the Viterbi decoder  326  determines the sequence of adjusted location data, processing pipeline server  210  writes the sequence of adjusted location data to street track database  220 . In  FIG. 3 , the adjusted location data is represented by snapped location data  304 . Snapped location data  304  is the sequence of location data that has been adjusted to correspond to features stored in map database  204 . 
     Each of feature finder  312 , distance calculator  314 , emission probability calculator  322 , transition probability calculator  324 , prior probability calculator  328 , and Viterbi decoder  326  may be implemented in hardware, software, firmware, or any combination thereof. 
       FIG. 4  is a flowchart of a method  400 . Method  400  is used, for example, to adjust location data so that it corresponds to polyline features of a map. Method  400  begins at step  402 . 
     In step  402 , a sequence of location data is received, for example using a satellite-based positioning system device (e.g. a GPS receiver). Each location can include coordinate and heading values. The coordinate values can be latitude and longitude values. In an embodiment, the location data is generated/received, for example, by one or more GPS receivers in a vehicle and/or other sensors such as wheel encoders. In embodiments, the location data may be received in real-time or near real-time. 
     In step  404 , for each location in the sequence of location data, polyline features within a radius R are found. In an embodiment, polyline features may be organized into bins, and finding polyline features may include using a map spatial index to get a list of all polyline features. The polyline features may include information such as geometry information, street name information, address information, turn restriction information, intersection information, connectivity information, etc. In an embodiment, the radius R is selected and/or adjusted based on the accuracy/error associated with the location data and/or satellite-based positioning system device used to obtain the location data (e.g., the radius R used if the locations are known to be within 100 feet of the coordinates that are obtained should be larger than the radius R used if locations are known to be within 10 feet of the coordinates that are obtained). 
     In step  406 , for each location in the sequence of location data, distances between the locations and features found in step  404  are calculated. 
     In step  408 , for each location in the sequence of location data, emission probabilities are calculated. An emission probability is calculated for each polyline feature within radius R of a location. The emission probability is a function of a feature and a location. The emission probability is a probability of obtaining the location, for example, from a GPS receiver given that the GPS receiver is actually at a location associated with a particular polyline feature. For each location, emission probability calculator  322  calculates an emission probability for each polyline feature within radius R of the location data. 
     In step  410 , transition probabilities are calculated. A transition probability is a probability of transitioning to a location of a feature given that the GPS receiver is at another feature. In an example, if a transition is allowed from one road to another (e.g., the roads meet at an intersection, and there are no turn restrictions), the transition is associated with a high probability. A disallowed transition (e.g., a transition between two roads that are not connected), is associated with low probability. How transition probabilities are calculated is described in more detail below. 
     In step  412 , prior probabilities are calculated. A prior probability is a probability that the start of the sequence of location data was measured at a particular polyline feature. In an embodiment, prior probabilities are calculated for each feature within the radius R of an initial location to be equally likely. However, in the presence of other inputs, the prior probabilities may be skewed to favor a certain feature (or features). 
     In step  414 , a sequence of adjusted/snapped location data is decoded. In embodiments of this invention, the sequence of adjusted location data are modeled as hidden states in a hidden Markov model. In the hidden Markov model, the sequence of location data are observable emissions from the hidden states that are given off with the calculated emission probability calculated in step  408 . The probability of transitioning to a first hidden state (e.g., a first polyline feature) given, for example, that a GPS receiver is at a second hidden state (e.g., a second polyline feature) is defined by the transition probabilities calculated in step  410 . The probability of the sequence of adjusted location data starting at a particular polyline feature is determined in step  412 . Step  414  uses the Viterbi algorithm to decode the most likely sequence of hidden states (e.g., the sequence of adjusted location data). The Viterbi algorithm is fast and efficient. By using the Viterbi algorithm, method  400  saves resources, such as space and computational time. 
     In step  416 , the sequence of adjusted/snapped location data is outputted. In an example embodiment, the adjusted/snapped location data may be written to a database. A server may retrieve the adjusted/snapped location data from the database. The server may format it for viewing by a user using a client. This example is illustrative and is not intended to limit the invention. 
     As show in the above embodiment, an entire sequence of location data is adjusted/snapped to the location of a sequences of polyline features. By snapping an entire sequence, as opposed to just individual locations, this embodiment takes into account, for example, the continuity of streets. This constraint enables embodiments of the present invention to correctly adjust/snap location data. 
     In embodiments, method  400  may include an additional step to use Kalman or particle filtering in conjunction with a hidden Markov model. As an example, Kalman or particle filtering may be used to refine/adjust the accuracy of the hidden Markov model. In that example, the Kalman or particle filtering are applied after the snapped location data are determined using the hidden Markov model. 
     In an embodiment, method  400  may use a probabilistic context-free grammar to model the sequence of polyline features. 
       FIGS. 5A and 5B  are diagrams that illustrate examples of how features within a radius R are recalled for a particular location. The examples show how to recall features for a particular location data. In practice, features are recalled for each location in a sequence of location data. 
       FIG. 5A  shows four bins. One such bin is bin  502 . Each bin represents an area on a map. In an embodiment, each bin represents an area 50 meters by 50 meters square. 
     In embodiments, each bin contains polyline features. A polyline feature may be, for example, a portion of a street or an intersection. Polyline feature  508  is an example polyline feature. Polyline feature  508  may be associated with data such as, for example, a road name, road geometry, whether the roads is one-way or two-way, etc. 
     As shown in  FIG. 5A , a location  506  (Y 1 ) can be represented by a set of coordinates and a heading. Each coordinate may include a latitude value and a longitude value. As an example, location data  506  may be obtained using a GPS receiver or other sensors, such as wheel encoders. 
     Referring to  FIG. 4  again, recall that in step  404 , polyline features within a radius R are found. To recall features within radius R, the bins containing the polyline features must first be identified. In the example in  FIG. 5A , the area within radius R is shown as circle  504 . Portions of all four bins lie within circle  504 . Accordingly, all four bins are recalled so that the subset of the features within circle  504  can be determined. 
       FIG. 5B  is a diagram that illustrates polyline features within circle  504 . In  FIG. 5B , two polyline features are shown within circle  504 . The polyline features are labeled  508  and  510 . Referring to  FIG. 4 , the distances between GPS coordinates and polyline features are calculated in step  406 . Accordingly,  FIG. 5B  shows an example distance d 11  between location Y 1  and the nearest point Z 1  on polyline feature  510 . Although only one distance is shown in the example, the distance between each of the polyline features  508 ,  510  and the location Y 1  are calculated in practice. 
     As described herein, a heading differential may also be calculated. In an embodiment, each of polyline features  508 ,  510  has a geometry that includes a heading. Heading differences may be calculated by taking the difference between the heading of the polyline features at the adjusted location (e.g., location Z 1  on feature  510 ) and the heading of location  506  (Y 1 ). In the example shown, the difference between the heading of location  506  and the heading of polyline feature  510  is shown by h 11 . Although only one heading difference is shown in the example, heading differential between each of the polyline features  508 ,  510  and the location Y 1  are calculated in practice. 
     The distances and headings described above are determined for use in calculating emission probabilities. Calculating emission probability is discussed in more detail below with reference to  FIG. 6B . 
       FIG. 6A  is a diagram that illustrates an example of how transition probabilities are calculated according to an embodiment of the present invention. As shown in  FIG. 6A , streets are represented in embodiments by various polyline features (e.g., polyline features X 0  to X 9 ). Note that each side of the street is independently represented. As an example, there is a high transition probability between X 0  and X 2  (represented by line  602 ) because those features are connected at intersection I 1 . “Connected” means that feature X 0  terminates at intersection I 1  and feature X 2  starts at intersection I 1 . As another example, there is a lower probability of transition between X 0  and X 6  because those features are not directly connected. In other words, a vehicle carrying a GPS receiver could drive directly from X 0  to X 2 , so there is a high transition probability. But, a vehicle carrying a GPS receiver could not jump directly from X 0  to X 6 , so there is a lower transition probability (represented by line  604 ). Note that there is also a transition probability for transitioning from X 0  onto itself (represented by line  608 ). 
     In embodiments, transition probabilities can vary based on feature information. For example, if a U-turn is allowed from X 0  to X 1 , the transition probability (represented by line  610 ) would be high, but if the U-turn is forbidden (i.e., it is a turn restriction), the transition probability would be low. Similarly, if the street is a one-way street, there may be a low probability of transitioning in a particular direction. For example, the transition probability for a transition from X 0  to X 4  (represented by line  606 ) is low since the vehicle cannot turn right from X 0  to X 4  since the latter is a one-way street and one cannot travel on it in the wrong direction. 
     In an embodiment, the function to adapt transition probabilities contains parameters. The parameters are selected using adaptive optimization. Examples of adaptive optimization algorithms include, but are not limited to, a hill-climbing algorithm, a stochastic hill-climbing algorithm, an A-star algorithm, and a genetic algorithm. 
       FIG. 6B  is a diagram that illustrates an example of how emission probabilities can be calculated according to an embodiment of the present invention. An emission probability is a function of a feature and a location. In an embodiment, the emission probability is a probability of obtaining the location, for example, from a GPS receiver given that the GPS receiver is actually at a location associated with a feature. 
       FIG. 6B  shows polyline features X 1 , X 2 , X 3 , and X 4  and a sequence of location data Y 1 , Y 2 , Y 3 , Y 4  and Y 5 . For each location Y 1 , Y 2 , Y 3 , Y 4 , and Y 5 , an emission probability is calculated for each polyline feature X 1 , X 2 , X 3 , and X 4 . In an embodiment, an emission probability may be a function of the distance between the polyline feature and the location and the heading differential between the polyline feature and the location. In an embodiment, the emission probability is calculated using a Gaussian function. An example Gaussian function is: 
                 P   ⁡     (       Y   m     ❘     X   n       )       =       (     Ae         -     d   nm   2       /   2     ⁢     σ   D   2         )     ·     (     Be         -     h   nm   2       /   2     ⁢     σ   H   2         )         ,         
where Y m  is a location; X n  is a polyline feature; d mn  is the distance between location Y m  and polyline feature X n ; h mn  is the heading differential between location Y m  and polyline feature X n ; and A, B, σ D , and σ H  are parameters. Parameters A and B control the relative weight of distance and heading respectively. Parameter σ D  controls how quickly the emission probability decreases as the distance increases. Parameter σ H  controls how quickly the emission probability decreases as the heading differential increases.
 
     In an embodiment, an emission probability contains parameters. The parameters may be selected using adaptive optimization. Examples of an adaptive optimization algorithms are noted above. In the example shown in  FIG. 6B , the emission probability of receiving location Y 2  while the receiver is at X 1  is: 
     
       
         
           
             
               P 
               ⁡ 
               
                 ( 
                 
                   
                     Y 
                     2 
                   
                   ❘ 
                   
                     X 
                     1 
                   
                 
                 ) 
               
             
             = 
             
               
                 ( 
                 
                   Ae 
                   
                     
                       
                         - 
                         
                           d 
                           12 
                           2 
                         
                       
                       / 
                       2 
                     
                     ⁢ 
                     
                       σ 
                       D 
                       2 
                     
                   
                 
                 ) 
               
               · 
               
                 
                   ( 
                   
                     Be 
                     
                       
                         
                           - 
                           
                             h 
                             12 
                             2 
                           
                         
                         / 
                         2 
                       
                       ⁢ 
                       
                         σ 
                         H 
                         2 
                       
                     
                   
                   ) 
                 
                 . 
               
             
           
         
       
     
     In the example shown in  FIG. 6B , the emission probability of receiving location Y 2  while the receiver is at X 3  is: 
     
       
         
           
             
               P 
               ⁡ 
               
                 ( 
                 
                   
                     Y 
                     2 
                   
                   ❘ 
                   
                     X 
                     3 
                   
                 
                 ) 
               
             
             = 
             
               
                 ( 
                 
                   Ae 
                   
                     
                       
                         - 
                         
                           d 
                           32 
                           2 
                         
                       
                       / 
                       2 
                     
                     ⁢ 
                     
                       σ 
                       D 
                       2 
                     
                   
                 
                 ) 
               
               · 
               
                 
                   ( 
                   
                     Be 
                     
                       
                         
                           - 
                           
                             h 
                             32 
                             2 
                           
                         
                         / 
                         2 
                       
                       ⁢ 
                       
                         σ 
                         H 
                         2 
                       
                     
                   
                   ) 
                 
                 . 
               
             
           
         
       
     
     Distance d 32  is larger than distance d 12 , and heading differential h 32  is larger than heading differential h 12 . Because d 32  is larger than d 12  and h 32  is higher than h 12 , the resulting probability P(Y 2 |X 1 ) is going to be larger than the probability P(Y 2 |X 1 ). As a result, the location Y 2  is more likely to be adjusted/snapped to a location on X 1  than to a location on X 3 . 
       FIG. 6C  is a diagram that illustrates an example of how location data may be snapped to points on a street. In an embodiment, once the transition probabilities, emission probabilities, and prior probabilities are calculated for a sequence of locations, the adjusted locations are determined using the Viterbi algorithm to decode the most likely sequence of hidden states (e.g., the sequence of adjusted location data). 
     In the example shown in  FIG. 6C , the sequence of location data Y 1 , Y 2 , Y 3 , Y 4 , and Y 5  is adjusted to locations Z 1 , Z 2 , Z 3 , Z 4 , and Z 5  respectively, each of which lies on a polyline feature. Note that in this example, two locations Y 1  and Y 2  are adjusted to positions Z 1  and Z 2  respectively, both of which lie on the same polyline feature, X 1 . This is possible because self-transitions between polyline features are allowed. Y 3  is snapped to point Z 3  which lies at the intersection. As discussed earlier, the polyline features X 1 , X 2 , X 3 , and X 4  may be modeled as hidden states in a hidden Markov model. As described herein, the entire sequence of locations Y 0 , Y 1 , Y 2 , Y 3 , and Y 4  is optimally snapped to the sequence of locations Z 1 , Z 2 , Z 3 , Z 4 , and Z 5  respectively, which lie on the polyline features in the map. This is based on information about the geometry and connectivity of the street network. This additional constraint results in more accurate adjustment/snapping of location data. 
     In an example, not intended to limit the present invention, Z 1 , Z 2 , Z 3 , Z 4 , and Z 5  may be the closest points to the locations Y 0 , Y 1 , Y 2 , Y 3 , and Y 4  on the corresponding polyline features X 1 , X 2 , X 3 , and X 4 . 
     It is to be appreciated that the detailed description section, and not the summary and abstract sections, is intended to be used to interpret the claims. The summary and abstract sections may set forth one or more but not all exemplary embodiments of the present invention as contemplated by the inventor(s), and thus, are not intended to limit the present invention and the appended claims in any way. 
     The present invention has been described above with the aid of functional building blocks illustrating the implementation of specified functions and relationships thereof. The boundaries of these functional building blocks have been arbitrarily defined herein for the convenience of the description. Alternate boundaries can be defined so long as the specified functions and relationships thereof are appropriately performed. 
     The foregoing description of the specific embodiments will so fully reveal the general nature of the invention that others can, by applying knowledge within the skill of the art, readily modify and/or adapt for various applications such specific embodiments, without undue experimentation, without departing from the general concept of the present invention. Therefore, such adaptations and modifications are intended to be within the meaning and range of equivalents of the disclosed embodiments, based on the teaching and guidance presented herein. It is to be understood that the phraseology or terminology herein is for the purpose of description and not of limitation, such that the terminology or phraseology of the present specification is to be interpreted by the skilled artisan in light of the teachings and guidance. 
     The breadth and scope of the present invention should not be limited by any of the above-described exemplary embodiments, but should be defined only in accordance with the following claims and their equivalents.