WO2018182528A1

WO2018182528A1 - Trajectory estimation system and method

Info

Publication number: WO2018182528A1
Application number: PCT/SG2018/050157
Authority: WO
Inventors: Lei Wang; Jaya Shankar Pathmasuntharam; Chee Wei Ang
Original assignee: Agency for Science Technology and Research Singapore
Current assignee: Agency for Science Technology and Research Singapore
Priority date: 2017-03-31
Filing date: 2018-03-29
Publication date: 2018-10-04
Anticipated expiration: 2019-09-30
Also published as: SG11201909042QA

Abstract

A trajectory estimation system for a vehicle and a method for estimating a trajectory of a vehicle are provided, the system comprises, a map feature module comprising one or more map features, each map feature being an instance of a deviation from a substantially straight path on a map; a vehicle movement data module comprising one or more travel features, each travel feature being an instance of a deviation from a substantially straight path, the one or more travel features being obtained from movement data of the vehicle; a processing module configured to match each travel feature with the one or more map features and to generate one or more trajectory candidates based on the one or more travel features; and wherein the processing module is further configured to identify a final trajectory candidate from the generated one or more trajectory candidates.

Description

TRAJECTORY ESTIMATION SYSTEM AND METHOD

TECHNICAL FIELD

The present disclosure relates broadly to a trajectory estimation system for a vehicle and to a method for estimating a trajectory of a vehicle.

BACKGROUND

GNSS (Global Navigation Satellite System), e.g. GPS (Global Positioning System), is a satellite-based system which is commonly used in vehicles for tracking, locating, routing, and other important tasks.

The inventors have recognized that in GNSS-based systems, there may be instances of a blockage of signals or deliberate jamming or spoofing of signals. Thus, in such GNSS- based systems, vehicle trajectory information may not be available. One problem that may arise is that road-toll systems using GNSS may therefore be unreliable.

Thus, there is a need for a trajectory estimation system for a vehicle and a method for estimating a trajectory of a vehicle that seeks to address at least one of the above problems.

SUMMARY

In accordance with a first aspect of the present disclosure, there is provided a trajectory estimation system for a vehicle, the system comprising, a map feature module comprising one or more map features, each map feature being an instance of a deviation from a substantially straight path on a map; a vehicle movement data module comprising one or more travel features, each travel feature being an instance of a deviation from a substantially straight path, the one or more travel features being obtained from movement data of the vehicle; a processing module configured to match each travel feature with the one or more map features and to generate one or more trajectory candidates based on the one or more travel features; and wherein the processing module is further configured to identify a final trajectory candidate from the generated one or more trajectory candidates. The generation of the one or more trajectory candidates may be based on a known sequence of the one or more travel features.

The generation of the one or more trajectory candidates may comprise the processing module being configured to sample each of the generated one or more trajectory candidates and to sample the movement data; and further being configured to evaluate the sampled one or more trajectory candidates and the sampled movement data.

The system may further comprise a map feature extraction module configured to extract the one or more map features from the map to form a map feature list.

The map feature extraction module may be further configured to extract new map features from an updated map to update the map feature list.

The movement data may comprise data measured by a microelectromechanical sensors (MEMS) based accelerometer and gyroscope device.

The movement data may comprise speed and angular data.

The vehicle movement data module may be configured to extract the one or more travel features from the movement data.

The processing module may be further configured to calculate a degree of confidence for each of the one or more trajectory candidates. In accordance with a second aspect of the present disclosure, there is provided a method for estimating a trajectory of a vehicle, the method comprising, providing one or more map features, each map feature being an instance of a deviation from a substantially straight path on a map; providing one or more travel features, each travel feature being an instance of a deviation from a substantially straight path, the one or more travel features being obtained from movement data of the vehicle; matching each travel feature with the one or more map features; generating one or more trajectory candidates based on the one or more travel features; and identifying a final trajectory candidate from the generated one or more trajectory candidates.

The step of generating one or more trajectory candidates may comprise using a known sequence of the one or more travel features.

The step of generating one or more trajectory candidates may comprise sampling each of the generated one or more trajectory candidates and sampling the movement data; and evaluating the sampled one or more trajectory candidates and the sampled movement data.

The method may further comprise a step of extracting the one or more map features from the map to form a map feature list. The method may further comprise a step of extracting new map features from an updated map to update the map feature list.

The method may further comprise obtaining the movement data from data measured by a microelectromechanical sensors (MEMS) based accelerometer and gyroscope device.

The method may further comprise processing the movement data to obtain speed and angular data.

The method may further comprise extracting the one or more travel features from the movement data.

The method may further comprise calculating a degree of confidence for each of the one or more trajectory candidates. In accordance with a third aspect of the present disclosure, there is provided a non- transitory computer readable storage medium having stored thereon instructions for instructing a processing unit of a system to execute a method for estimating a trajectory of a vehicle, the method comprising, providing one or more map features, each map feature being an instance of a deviation from a substantially straight path on a map; providing one or more travel features, each travel feature being an instance of a deviation from a substantially straight path, the one or more travel features being obtained from movement data of the vehicle; matching each travel feature with the one or more map features; generating one or more trajectory candidates based on the one or more travel features; and identifying a final trajectory candidate from the generated one or more trajectory candidates.

BRIEF DESCRIPTION OF THE DRAWINGS

Exemplary embodiments of the disclosure will be better understood and readily apparent to one of ordinary skill in the art from the following written description, by way of example only, and in conjunction with the drawings, in which:

FIG. 1 is a schematic block diagram of a system for estimating a trajectory of a vehicle in an exemplary embodiment. FIG. 2 is a schematic process flow for a vehicle trajectory estimation system in an exemplary embodiment.

FIG. 3 is a schematic illustration of examples of map features in an exemplary embodiment.

FIG. 4 is a schematic flowchart for illustrating a process of extracting one or more map features in an exemplary embodiment.

FIG. 5 shows exemplary map features in a map of the CBD (Central Business District) area of Singapore in an exemplary embodiment.

FIG. 6 is an exemplary list of map feature data fields for a map feature in an exemplary embodiment. FIG. 7 is a graph showing change in speed over time of a vehicle in an exemplary embodiment.

FIG. 8 is a schematic flowchart for illustrating a process of extracting one or more travel features in an exemplary embodiment. FIG. 9 is a schematic illustration showing locations of travel features extracted from inertial measurement unit (IMU) data in an exemplary embodiment.

FIG. 10 is a schematic flowchart for illustrating a process of generating trajectory candidates in an exemplary embodiment.

FIG. 1 1 is a chart showing the numbers of map feature candidates generated for a sequence of travel/IMU features in an exemplary embodiment. FIG. 12 is a schematic diagram illustrating processing of accumulative angle turned

(AAT) in a candidate trajectory in an exemplary embodiment.

FIG. 13 is a series of candidate trajectories super-imposed on a map in an exemplary embodiment.

FIG. 14 is a comparison between the best match trajectory (top) and a GNSS e.g. GPS trajectory (bottom) of a same map area in an exemplary embodiment.

FIG. 15 is a schematic flowchart for illustrating a method of estimating a trajectory of a vehicle in an exemplary embodiment.

FIG. 16 is a schematic drawing of a computer system suitable for implementing the described exemplary embodiments.

DETAILED DESCRIPTION

Exemplary, non-limiting embodiments may provide a system and a method for estimating a trajectory of a vehicle.

The term "trajectory" as used in this description may refer to a path that a moving object e.g. vehicle follows through space as a function of time.

FIG. 1 is a schematic block diagram of a system 100 for estimating a trajectory of a vehicle in an exemplary embodiment. The system 100 comprises a map feature module 102 and a vehicle movement data module 104, each coupled to a processing module 106. The processing module 106 is further coupled to an output module 108.

The map feature module 102 comprises one or more map features. The map feature module 102 may comprise or be coupled to a map feature extraction module that may implement a process of map feature extraction. For example, the one or more map features may belong to an area of interest e.g. from a map of the whole of Singapore. Each map feature is an instance of a deviation from a substantially straight path on a map. In the exemplary embodiment, a map feature may be a unique instance of a turn from a map. For example, the map feature may be a turn along a road at a particular geographical location, said geographical location having a defined set of geographical coordinates on a map. For example, a turn may be a left turn, a right turn, a U-turn, or a round-about.

The map feature module 102 functions to provide a database of information such as map features which characterize a particular geographical area. The map may be in electronic format and may be obtained from any source. For example, one source may be OpenStreetMap (OSM) which provides free and open sourced maps.

The vehicle movement data module 104 comprises one or more travel features. The vehicle movement data module 104 may comprise or be coupled to a travel feature extraction module that may implement a process of travel feature extraction. Each travel feature is an instance of a deviation from a substantially straight path of a vehicle. For example, the travel feature may be a turn traversed by a vehicle along a road. For example, a turn may be a left turn, a right turn, a U-turn, or a round-about. The vehicle movement data module 104 functions to provide a record or history of movement data of the vehicle during its course of travel, comprising instances where the vehicle deviated from a substantially straight path. The one or more travel features are obtained from movement data of the vehicle. For example, the movement data may be acceleration and angular data recorded by a measurement device on board the vehicle.

The processing module 106 functions to process information of the map feature module 102 and the vehicle movement data module 104. The processing module 106 is configured to match each travel feature with the one or more map features based on one or more criteria and to generate one or more trajectory candidates based on the one or more travel features. The processing module 106 is further configured to identify a final or best trajectory candidate from the generated one or more trajectory candidates. Once the final trajectory candidate is identified, the final trajectory candidate is provided at the output module 108. The output module 108 may be a visual display using a map based on the one or more map features. FIG. 2 is a schematic process flow 200 for a vehicle trajectory estimation system in an exemplary embodiment. The vehicle trajectory estimation system functions substantially similarly to the system 100 of FIG. 1 . In the exemplary embodiment, the process of vehicle trajectory estimation comprises a map preparation phase 202 and a trajectory estimation phase 204.

The map preparation phase 202 is performed by a map feature extraction module 206 which extracts a list of map features and stores the map features in a database. The map feature extraction module may be coupled to or may be a part of a map feature module (compare 102 of FIG. 1 ).

In the exemplary embodiment, a map source 208 from OpenStreetMap (OSM) is used by the map feature extraction module 206 for extracting map features and generating a map feature list 210 which comprises a list of extracted map features. The map preparation phase 202 is performed in an initial stage when a new map is provided and whenever there is a map update. Otherwise, if the map feature list 210 is maintained, the map feature extraction module 206 may not be used. During a map update, new map features are extracted from an updated map to add/update the map feature list 210. It would be appreciated that the map source is not limited to OpenStreetMap (OSM) and other map sources may be used.

The trajectory estimation phase 204 is performed by first extracting raw vehicle movement data 212, e.g. raw IMU (inertial measurement unit) data from a device that records vehicle movement e.g. a low-precision inertial measurement unit (IMU) that is installed in the vehicle. An example of a IMU is a microelectromechanical sensors (MEMS) based accelerometer and gyroscope device. The raw IMU data is processed by a travel feature extraction module 214 which extracts travel features (or IMU features) from the raw IMU data. The travel feature extraction module 214 may be coupled to or may be a part of a vehicle movement data module (compare 104 of FIG. 1 ). During the trajectory estimation phase 204, once the IMU features are extracted, a processing module (compare 106 of FIG. 1 ) generates trajectory candidates through matching between the IMU features and the map features in the map feature list. See numeral 216. Thereafter, the system measures the distance between the IMU data and trajectory candidates through a detailed evaluation algorithm using a e.g. dynamic time warping (DTW) calculation, to evaluate and rank the trajectory candidates. See numeral 218. It would be appreciated that other evaluation algorithms may be used in place of DTW. The system then provides the best trajectory candidate e.g. to an output module.

In the exemplary embodiment, it would be appreciated that the process flow 200 may broadly comprise four parts, namely map feature extraction from a map source, travel/IMU feature extraction from IMU data, generation of trajectory candidates based on feature matching, and trajectory estimation e.g. based on DTW evaluation.

In the exemplary embodiment, the system and process flow 200 is advantageously capable of providing trajectory estimation based on data from e.g. a low-precision inertial measurement unit (IMU) on a vehicle, i.e. Micro Electro Mechanical Sensors (MEMS) based accelerometer and gyroscope device. By leveraging the map information, the system and process flow 200 may be capable of performing trajectory estimation through matching a sequence of IMU data to the map in feature space. FIG. 3 to FIG. 6 describe a process of extracting map features from a map, e.g.

OpenStreetMap (OSM).

FIG. 3 is a schematic illustration of examples of map features in an exemplary embodiment. A map feature is defined as an instance of a deviation from a substantially straight path on a map, i.e. a turn. In the exemplary embodiment, a map feature may be a unique instance of a turn from a map. In the exemplary embodiment, two map features are shown on the map. A black asterisk indicates a location and beginning of a map feature. There is one left turn shown as a full black line 302 and one right turn shown as a dashed black line 304. Both roads intersecting at the intersection are one-way links.

The map features may be obtained through a process of feature extraction from map data of a map. In the exemplary embodiment, OpenStreetMap (OSM) is used. The map data comprises a list of links; and each link is a straight line and comprises at least one attribute.

The attributes of each link may comprise identity (ID) of a link (link id), ID of a starting node of the link (node_id_from), ID of an ending node of the link (node_id_to), coordinates of the starting node (latitudejrom, longitudejrom), coordinates of the ending node (latitude_to, longitude_to), and length of the link (link length).

In the exemplary embodiment, a map feature is described as a turning which satisfies some or all of the following conditions to qualify as a map feature. Firstly, a map feature comprises two or more concatenated links (i.e. linked together in series). Secondly, any two concatenated links form an angle therebetween and the angle between any two concatenated links have the same sign, e.g. either positive (turning in a clockwise manner) or negative (turning in an anti-clockwise manner). Thirdly, the length of each link, except the starting and ending link, is equal or below a pre-determined threshold value. Fourthly, the absolute accumulative angle of the concatenated links is equal or above a pre-determined threshold value, and this is defined as angle of turn. Fifthly, the cumulative length of all links is equal or below a pre-determined threshold value. For example, the length of each link (excluding the starting and ending link) may be set at a threshold value of 20 meters, the threshold angle for the absolute accumulative angle may be set at 75 degrees, and the cumulative length of all links may be set at 500 meters.

The inventors have recognized that the first condition of having at least two concatenated links provides that there is at least one angle formed in a map feature. The second condition of an angle between any two concatenated links having the same sign provides that the angle change along the concatenated links is monotonic, i.e. it turns either clockwise or anti-clockwise monotonically.

For the more variable conditions, the inventors have recognized that the third condition of each link having a threshold maximum length provides that a map feature does not contain long links. The fourth condition of an absolute accumulative angle of the concatenated links above a minimum threshold value provides that the turning described by the concatenated links is significant. The fifth condition of the cumulative length of all links below a threshold value provides that the overall length is within a pre-determined limit.

In the exemplary embodiment, a link, in most open sourced maps, refers to a straight line. Such a link may have a length as low as 1 meter or as large as several kilometers. An absolute accumulative angle is set to be larger than a pre-defined threshold, e.g. 75 degrees so that a turning can be recognized as a feature. The absolute accumulative angle may even be as large as 360 degrees (e.g. a round-about) or 720 degrees (e.g. a multiple layered circular road to enter certain highways/expressways). Therefore, it has been recognized that the absolute accumulative angle may not have an upper limit.

As for the cumulative length, the cumulative length is chosen to have an upper limit so as to avoid a long feature, i.e. the length of a feature may not be desired to be too long for a particular area of interest. For example, having an upper limit that is generally large e.g. 500 meters, this limit is able to cover the use cases using a map of Singapore. However, it has been recognized that the upper limit may be increased to include other special features when used with other maps. In any event, it has been recognized that the cumulative length may be maintained smaller than 1 kilometer because even if the length of a special feature is larger than 1 kilometer, that special feature may be "captured" as two or more features.

It would be appreciated that the threshold value for the length of each link, the threshold angle for the absolute accumulative angle of the concatenated links, and the cumulative length of all links may be varied/adjusted.

FIG. 4 is a schematic flowchart 400 for illustrating a process of extracting one or more map features in an exemplary embodiment. The process cycles through the list of links provided by the map data being used.

At step 402, one link of a map is selected as the start link.

At step 404, candidate map features are generated. For example, this is accomplished by starting with the selected link and traversing to the next connected link/links recursively until one or more of the following conditions are satisfied: (1 ) a new angle generated by a newly added link has a different sign from an angle formed by a preceding link (compare second condition described above); (2) a length of a newly added link is longer than e.g. 20 meters (compare third condition described above); and/or (3) a cumulative length of all links is longer than e.g. 500 meters (compare fifth condition described above). It would be appreciated that one link may have one or more connected links, so that one or more candidate map features may be generated with an arbitrary start link.

At step 406, each candidate map feature is verified. For example, this is accomplished by checking the candidate map feature based one or more of the following criteria: (a) an accumulative angle is at least e.g. 75 degrees (compare fourth condition described above); and/or (b) the candidate map feature is not a subset of an existing map feature. For example, the candidate map feature is removed if the accumulative angle is smaller than 75 degrees; and/or the candidate map feature is removed if it is a subset of one existing map feature, e.g. if a candidate map feature contains two concatenated links and their link IDs are, 5032 and 5019, while there exists another map feature, with four concatenated links, 5012-5032-5019-5084.

At step 408, the candidate map feature is inserted into a map feature list, and any existing map features that are a subset of the candidate map feature are removed. Steps 402 to 408 are then looped/reiterated for all the links of the map.

At step 410, attributes for each map feature are calculated and stored in the map feature list. The attributes may comprise map feature ID, angle of turn (accumulative angle), accumulative length, number of links, starting link ID, and ending link ID.

FIG. 5 shows exemplary map features in a map of the CBD (Central Business District) area of Singapore in an exemplary embodiment. The map features are obtained from a map feature extraction process on the map of the CBD area of Singapore. A black asterisk indicates a location of a map feature e.g. a turning. It has been recognized that as an open sourced map was used for this example, some links were not provided by the source. A more comprehensive map may be helpful for the performance of a better trajectory estimation.

In the exemplary embodiment, after the process of FIG. 4, after the map feature list is created, the map features in the map feature list are connected to form a map feature graph. For example, a map feature graph may be illustrated with FIG. 6. The criterion to determine whether two map features are connected is if the shortest path between them does not contain any other map features. The map feature graph introduces two more attributes for each map feature, namely IDs of one or more connected map features and distances to those connected map features.

FIG. 6 is an exemplary list 600 of map feature data fields 602 for a map feature in an exemplary embodiment. The map feature data fields 602 comprise attributes of a map feature in a map feature list. The attributes comprise a map feature ID which provides each map feature with a unique ID number; angle of turn (accumulative angle) which is summed up from individual angles formed between any two links in the map feature, accumulative length of all the links, number of links, starting link ID, ending link ID, IDs of connected map features, and distances to connected map features.

FIG. 7 to FIG. 9 describe a process of extracting travel features from movement data, e.g. IMU data of a vehicle. The examples below utilize accelerometer and gyroscope measurements. The extraction process is divided into 2 steps, i.e. speed estimation and feature identification. The examples illustrate a process to obtain travel features, e.g. turns data, from recorded or known IMU data but it will be appreciated that the examples are not limited as such. That is, any other suitable ways of obtaining travel features, e.g. turns data, of a vehicle may also be used. For example, data obtained directly from a vehicle engine may be used to obtain travel features.

In the example, for speed estimation, the vehicle speed is estimated based on the acceleration data as measured by an accelerometer.

In the example, a bias mitigation algorithm is incorporated into the speed estimation to enhance the performance of the speed estimation process. The bias mitigation algorithm comprises two steps, namely stop detection and bias estimation. For stop detection, the timestamps that the vehicle stopped are detected based on the statistics of the acceleration data. For bias estimation, acceleration bias is estimated by assuming the bias is constant and the time integration of linear acceleration (i.e. without gravity) is zero between any two nearby stop points. To elaborate more, the time integration of linear acceleration is the speed difference from one point to another. If the two points are zero speed, the time integration of linear acceleration is zero. Hence, by using the raw acceleration data, the time integration of linear acceleration is normally non-zero. As a bias may typically exist in a MEMS sensor, this non-zero value divided by time is the bias of the acceleration data by assuming the bias to be constant throughout the period. It is recognized that the bias may change over time due to one or more factors, e.g. temperature change. FIG. 7 is a graph showing change in speed over time of a vehicle in an exemplary embodiment. The solid line represents estimated speed of the vehicle as calculated using the bias mitigation algorithm using data measured by an inertial measurement unit (IMU). The dashed line represents reference speed of the vehicle as measured from GNSS, e.g. GPS (Global Positioning System) data to show that the estimated speed is substantially close to the reference speed. The dots (or at the flat portions) represent stop points obtained from the stop detection algorithm. An example of a stop interval on the graph is pointed by reference numeral 702.

FIG. 8 is a schematic flowchart 800 for illustrating a process of extracting one or more travel features in an exemplary embodiment. The travel features in this example are from IMU data and are termed IMU features. At step 802, a current angle of turn is set to be zero (0) at a first arbitrary timestamp A and the angle of turn is accumulated with time based on the IMU data until timestamp B. This angular data may be obtained from a gyroscope device. The angle of turn is accumulated until the following two conditions are satisfied at timestamp B: (1 ) overall distance is larger than a pre-determined threshold value, e.g. 30 meters; and (2) turn direction (i.e. clockwise or anti-clockwise) is opposite of previous one or the speed of angle turned is less than a pre-determined threshold value, e.g. 1 degree/second. At step 804, the current angle of turn is defined as T. Timestamp A is moved forward step by step to timestamp RA. The timestamp A is moved until the angle of turn from RA to B is just equal or below a pre-determined threshold, e.g. 0.99^*T, and the angle is defined as T. Timestamp B is moved backwards step by step to timestamp RB until the angle of turn from RA to RB is equal or below a pre-determined threshold, e.g. 0.99*T, and the angle is defined as RT (or refined angle of turn). This refinement is implemented as it is able to make sure that the IMU feature identified contains a major turn only, e.g. the IMU feature does not include a long head or tail, which may be adverse for the trajectory candidate generation and selection. For example, from the arbitrary timestamp A to timestamp B, the IMU feature may contain a straight line and followed by a right turn. This straight line may be relatively long, e.g. 500 meters, and is not part of the actual turn, and may degrade the performance of following processes. Hence, the refinement process has been introduced to make the IMU feature more refined or clean. The threshold is set to be 99% of the turn, based on two considerations. Firstly, 99% is recognized by the inventors to be sufficient to remove a straight line portion of a IMU feature based on experimental data. Secondly, it has been recognized by the inventors that the IMU feature still contains the major turn, i.e. 99%^*99% of the total turn after refinement. Therefore, the IMU feature after refinement is recognized not to affect the performance of the following processes significantly as it has been noted that the angle/turn estimated typically has a 10% to 20% deviation from the true turn. At step 806, the refined angle of turn RT is checked. If RT is equal or above a predetermined threshold, e.g. 75 degrees (the threshold is maintained consistent with the map feature extraction consideration), then a IMU feature is calculated and defined. The IMU feature comprises a list of attributes, e.g. index of feature, angle of turn, distance travelled from RA to RB, starting timestamp RA, ending timestamp RB, and distance to a previous IMU feature. It is appreciated that the distance to a previous IMU feature refers to the distance between the two middle points of both IMU features.

At step 808, the process step 802 is repeated with timestamp RB to extract the next IMU feature until the end of the IMU data. FIG. 9 is a schematic illustration showing locations of travel features extracted from

IMU data in an exemplary embodiment. The travel features are shown on a map. Circles represent start points of travel/IMU features. Stars represent end points of travel/IMU features. Each pair of black circle and black star represent the starting and ending point of a travel feature/IMU feature respectively. The black lines are super-imposed and represent a corresponding GNSS e.g. GPS trajectory for reference only. It would be appreciated from FIG. 9 that the GPS data is not accurate, i.e. the GPS trajectory is not perfectly aligned with the roads on the map. From FIG. 9, it is observed that using the process of FIG. 8, the major turns are labelled correctly as IMU features, and in total there are 9 IMU features in this exemplary embodiment.

After obtaining map features and travel features, a processing module is configured to perform feature matching to generate one or more trajectory candidates based on the one or more travel features. The processing module is further configured to identify a best/final trajectory candidate from the one or more generated trajectory candidates.

FIG. 10 is a schematic flowchart 1000 for illustrating a process of generating trajectory candidates in an exemplary embodiment. Trajectory candidates are possible routes that a vehicle travelled based on the matching of travel/IMU features and map features. The travel features in this example are from IMU data and are termed IMU features. At step 1002, a first IMU feature is set as a current IMU feature, and all map features are set as current map features.

At step 1004, the current IMU feature is used as reference and a subset of map features is selected from among the current map features by the following criteria: (1 ) skip this criterion if the current IMU feature is the first feature, otherwise the ratio between the IMU attribute, distance to previous feature, and distance recorded for a map feature should be within a pre-determined window (inclusive), e.g. 0.8-1 .2 (this is a range of a ratio. For this exemplary range, it is allowed a -20% to 20% error margin for distance estimation. This 20% error margin is defined by the inventors based on experimental data) ; and (2) the absolute difference of attribute, angle of turn between the current IMU feature (reference) and map features, are equal or below a pre-determined threshold, e.g. 15 degrees. This threshold is chosen by the inventors based on experimental data from a low-precision and relatively cheap IMU (MEMS based device), as typically an error of the angle estimated is found to be smaller than 15 degrees. A user may further lower this threshold if e.g. a high-end IMU is used, as high-end IMU data may be better in terms of error and may eventually improve the speed and accuracy of the trajectory candidate estimation.

At step 1006, the subset of map features filtered by step 1004 is used to obtain a new set of map features through a combination of their attributes, e.g. IDs of connected map features, and the distances to the connected features are recorded. The new subset of map features is used in a next iteration of step 1004. See step 1008.

At step 1008, the new set of map features of step 1006 is used as current map features, and a next IMU feature is set as a new current IMU feature, and step 1004 is repeated until the last IMU feature is processed. Hence, for each IMU feature, a set of map feature candidates is generated. The trajectory candidates may be generated by using the connected feature lists.

FIG. 1 1 is a chart 1 100 showing the numbers of map feature candidates generated for a sequence of travel/IMU features in an exemplary embodiment. The travel features in this example are from IMU data and are termed IMU features. The data in FIG. 1 1 is based on feature matching of IMU features and map features. As shown in FIG. 1 1 , there are nine IMU features in the exemplary embodiment, and for each IMU feature, there are tens of map feature candidates, ranging from 20 to 120. For example, for IMU feature number 9 or the last IMU feature 1 102 in the sequence, there are about 20 to 30 possible map feature candidates. There is a total of 517 trajectory candidates which are obtained through connecting the 9 sets of map features (corresponding to the 9 IMU features).

The trajectory candidates are next ranked to find out the best/final matched trajectory. In the examples below, trajectory estimation is based on an evaluation algorithm e.g.

Dynamic Time Warping. FIG. 12 is a schematic diagram illustrating processing of accumulative angle turned (AAT) in a candidate trajectory in an exemplary embodiment. A candidate trajectory is sampled uniformly along a number of sample points, e.g. 201 sample points, and each sample point is a location coordinate, e.g. longitude, and latitude. A feature termed as accumulative angle turned (AAT) is extracted sample by sample. In the exemplary embodiment, there are 4 sample points, P1 to P4. The AAT for P1 is zero by definition (starting point), the AAT for P2 is 40 degrees (assuming a right turn is positive), and the AAT for P3 is zero (40+-40 = 0) degree. That is, it is assumed that a left turn of 40 degrees is negative. If there is no more sample point after P4, the AAT for P4 is the same as that of P3. Hence, a list of AATs is obtained after performing basic geometry calculation.

Next, or concurrently, travel/IMU data is also sampled uniformly based on distance travelled. For example, if the estimated distance travelled is 2000 meters, the number of sample points is set to be, as an example, 201 (including the initial point). Thus, the data is sampled one point every 10 meters. The AATs is also calculated for every sample point based on the IMU data e.g. based on angular data of the path travelled. Hence, a list of AATs from IMU data is obtained. The IMU AATs are refined through a bias compensation algorithm to have an improved performance. This bias compensation algorithm estimates the bias by dividing the difference of the last map trajectory AAT and IMU AAT, by the time period of the data (with seconds as the unit). The angular data from a gyroscope device (of the MEMS based device) typically has some bias, and this may result in a large difference between the last IMU AAT and map trajectory AAT, i.e. the difference is proportional to the period. If the candidate map trajectory is correct, the gyroscope bias (for 1 second) may be calculated based on the following formula: (last trajectory AAT - last IMU AAT) / period (unit: second). Hence, it is possible to calculate and compensate the gyroscope bias if the trajectory candidate is a true one, the gyroscope bias estimation is correct and therefore, the matching is further improved in terms of score. If the trajectory candidate is not the true one, the gyroscope bias estimation may not be correct, and in fact, there is no need for it to be correct as the trajectory candidate is not the true trajectory. Hence, by doing so, the performance of the system and method may be improved.

Next, a comparison is performed between the IMU AATs and trajectory (from the map) AATs (e.g. as illustrated in FIG. 12) through an end to end dynamic time warping (DTW) technique, to obtain a score. The score is normalized by the number of samples, e.g. 201 , and the normalized score is used to rank the trajectory candidates. The inventors recognize that DTW calculates the difference between the IMU AATs and trajectory AATs, and hence, the smaller the score, the higher the rank. There is a window parameter in DTW calculations, and this parameter is set based the confidence of distance estimation. A heuristic approach is used in that if the distance estimation is expected to differ by 20% from the true distance, the window parameter is set to be equal or above 20% of the number of samples. This DTW may be a typical DTW technique, with two same length sequences, and the window size is set to be 20% of samples in this case, as the distance estimation is typically within +/-20% of a true one for a low-precision IMU (MEMS based device). If a better IMU is used, this window size may be reduced to give a better separation of the true trajectory and other trajectory candidates. The DTW is used to try to find a mapping path such that the distance on the mapping path is minimized.

Overall, after the evaluation of the exemplary embodiment, a list of scores for each trajectory candidate is obtained.

FIG. 13 is a series of candidate trajectories super-imposed on a map in an exemplary embodiment. The scores are shown in FIG. 13, e.g. at numeral 1302. The best 4 candidates are shown in this figure, and their scores are 6.15, 8.74, 8.74, and 8.90. It is clear that the most likely trajectory is the first trajectory of numeral 1302. Indeed, this candidate is the actual trajectory travelled in this example and a comparison with GNSS e.g. GPS trajectory is shown in FIG. 14.

FIG. 14 is a comparison between the best match trajectory 1402 (top) and a GNSS e.g. GPS trajectory 1404 (bottom) of a same map area in an exemplary embodiment. In the exemplary embodiment, the best/final trajectory candidate may be output to an output module (e.g. 108 of FIG. 1 ).

Having determined the more likely trajectory candidates, a heuristic approach is designed to calculate the degree of confidence about the trajectory candidates based on their scores. First, the score of the first (best) candidate is used as reference, and denoted as b. A raw degree of confidence (rdoc) is calculated based on the formula, rdoc = log( - (x/b) * 18 + 28). The base of the logarithmic in the formula is 10. The score is inputted as x. This heuristic formula is designed based on two aspects. First, the rdoc decreases monotonically, i.e. the larger the rated score (x/b), the lower the degree of confidence. Second, the rdoc decreases faster when the rated score gets larger, since the number of trajectory candidates increases faster when the rated score gets larger and therefore, the possibility of being the true trajectory decreases faster as well. The inventors recognize that there is a cut-off rated score, which is e.g. 1 .5, i.e. the trajectory candidate is ignored (the rdoc is set to be 0) when the rated score is larger than 1 .5 (the parameter inside the log function is smaller than 1 ). This cut-off rated score may be adjusted based on the application scenario requirements.

The rdoc is normalized through dividing by the summation of all rdocs, so that the summation of all normalized degree of confidence {ndoc) is 1 . For example, taking the scores obtained in the example, there are 4 ranked scores, 6.15, 8.74, 8.74, and 8.90 (with the assumption that all the rated scores of all other candidates are above 1 .5). Their rdocs are 1 .00, 0.38, 0.38, and 0.29 respectively after calculation. Their ndocs are 0.49, 0.185, 0.185, and 0.14 after normalization. The ndoc determination is introduced to indicate the confidence level of all trajectory candidates, because a user may want to know the confidence level when the system of the exemplary embodiment derives a best-matched candidate as the true trajectory though the best-matched candidate has the largest possibility to be the true trajectory. In this case, the ndocs values representing the possibilities of a candidate trajectory being the true trajectory are 0.49, 0.185, 0.185, and 0.14 respectively. It has been recognized by the inventors that the ndoc determination may be optional but may be useful for, for example, the solution to the problem mentioned in the Background section. For example, the ndoc determination may give all the trajectory candidates whose possibility of being the true trajectory is larger than 20%. Alternatively, the ndoc determination may simply be, e.g. to give a degree of confidence of the best-matched trajectory.

FIG. 15 is a schematic flowchart 1500 for illustrating a method for estimating a trajectory of a vehicle in an exemplary embodiment. At step 1502, one or more map features are provided, each map feature being an instance of a deviation from a substantially straight path on a map. At step 1504, one or more travel features are provided, each travel feature being an instance of a deviation from a substantially straight path, the one or more travel features being obtained from movement data of the vehicle. At step 1506, each travel feature is matched with the one or more map features. At step 1508, one or more trajectory candidates are generated based on the one or more travel features. At step 1510, a final trajectory candidate is identified from the generated one or more trajectory candidates. For step 1502, the one or more map features may be a provision of all the map features of an area of interest. For an exemplary scenario of 15 minutes of IMU data of vehicle movement, a user may wish to know what kind of trajectory is possible in e.g. Singapore. In such a scenario, the area of interest is Singapore and all the map features of Singapore is then provided.

In an exemplary embodiment, there is provided an extraction of turns data from a map source and of turns data from a path travelled by a vehicle. There is also provided a matching of the turns data from the map source to the turns data from the vehicle to identify one or more candidates for the path travelled by the vehicle on the map. There is further provided an identification of the best trajectory candidate from the one or more candidates, the identification arising from a scoring process.

In the described exemplary embodiments, a system and a method for estimating a trajectory of a vehicle are disclosed. The system and method for estimating a trajectory of a vehicle may provide a non-GNSS-based tracking of a vehicle for use with e.g. a GNSS- based road-toll system. The system and method for estimating a trajectory of a vehicle may address issues encountered by a GNSS-based system. The inventors have recognized that a non-GNSS-based tracking of a vehicle through a road network may be used as a check against blocking, jamming and spoofing attempts on a GNSS-based system. The system and method for estimating a trajectory of a vehicle may provide such a non-GNSS-based tracking. For example, if a trajectory derived from a GNSS device does not corroborate with a trajectory derived from the described exemplary embodiments (of a non-GNSS-based tracking), then the GNSS-derived trajectory may be deemed unreliable. A GNSS-based trajectory may be deemed unreliable due to a faulty GNSS device, or due to GNSS blocking, jamming or spoofing of signals. In such instances, further investigations may then be conducted to ascertain the unreliability and actual cause of the event. The inventors have also recognized that in addition to being able to flag such events, the described exemplary embodiments (of non-GNSS-based tracking) may also provide a trajectory in which the vehicle may have actually travelled. This non-GNSS-derived trajectory information may also be used in an investigation, e.g. providing evidence on the intent of the driver in avoiding toll- road charges in a GNSS-based road-toll system.

In the described exemplary embodiments, a method for vehicle trajectory estimation based on IMU and map data may be provided and it may comprise: (a) map feature extraction; (b) IMU feature extraction; (c) generation of trajectory candidates by matching features derived from IMU data (b) to features derived from map data (a); and (d) calculation of the degree of confidence for each trajectory candidate (c).

In part (a), map feature extraction, a term "map feature" is defined and used for map feature extraction. A process of map feature extraction has been described for obtaining a list of map features, which may be used as reference during the matching process of part (c). In part (b), a process to perform IMU features extraction from raw IMU data has been described. These IMU features are used to generate a list of trajectory candidates during the matching process of part (c). In part (c), a process to generate a list of trajectory candidates through matching IMU features with map features has been described. In part (d), a feature, "accumulative angle turned (AAT)", is proposed and used in a dynamic time warping (DTW) algorithm to compute the scores of trajectory candidates. In part (d), a formula is also proposed to calculate the degree of confidence for the trajectory candidates based on their DTW evaluated scores.

The terms "coupled" or "connected" as used in this description are intended to cover both directly connected or connected through one or more intermediate means, unless otherwise stated. The description herein may be, in certain portions, explicitly or implicitly described as algorithms and/or functional operations that operate on data within a computer memory or an electronic circuit. These algorithmic descriptions and/or functional operations are usually used by those skilled in the information/data processing arts for efficient description. An algorithm is generally relating to a self-consistent sequence of steps leading to a desired result. The algorithmic steps can include physical manipulations of physical quantities, such as electrical, magnetic or optical signals capable of being stored, transmitted, transferred, combined, compared, and otherwise manipulated.

Further, unless specifically stated otherwise, and would ordinarily be apparent from the following, a person skilled in the art will appreciate that throughout the present specification, discussions utilizing terms such as "scanning", "calculating", "determining", "replacing", "generating", "initializing", "outputting", and the like, refer to action and processes of an instructing processor/computer system, or similar electronic circuit/device/component, that manipulates/processes and transforms data represented as physical quantities within the described system into other data similarly represented as physical quantities within the system or other information storage, transmission or display devices etc. The description also discloses relevant device/apparatus for performing the steps of the described methods. Such apparatus may be specifically constructed for the purposes of the methods, or may comprise a general purpose computer/processor or other device selectively activated or reconfigured by a computer program stored in a storage member. The algorithms and displays described herein are not inherently related to any particular computer or other apparatus. It is understood that general purpose devices/machines may be used in accordance with the teachings herein. Alternatively, the construction of a specialized device/apparatus to perform the method steps may be desired.

In addition, it is submitted that the description also implicitly covers a computer program, in that it would be clear that the steps of the methods described herein may be put into effect by computer code. It will be appreciated that a large variety of programming languages and coding can be used to implement the teachings of the description herein. Moreover, the computer program if applicable is not limited to any particular control flow and can use different control flows without departing from the scope of the invention.

Furthermore, one or more of the steps of the computer program if applicable may be performed in parallel and/or sequentially. Such a computer program if applicable may be stored on any computer readable medium. The computer readable medium may include storage devices such as magnetic or optical disks, memory chips, or other storage devices suitable for interfacing with a suitable reader/general purpose computer. In such instances, the computer readable storage medium is non-transitory. Such storage medium also covers all computer-readable media e.g. medium that stores data only for short periods of time and/or only in the presence of power, such as register memory, processor cache and Random Access Memory (RAM) and the like. The computer readable medium may even include a wired medium such as exemplified in the Internet system, or wireless medium such as exemplified in bluetooth technology. The computer program when loaded and executed on a suitable reader effectively results in an apparatus that can implement the steps of the described methods.

The exemplary embodiments may also be implemented as hardware modules. A module is a functional hardware unit designed for use with other components or modules. For example, a module may be implemented using digital or discrete electronic components, or it can form a portion of an entire electronic circuit such as an Application Specific Integrated Circuit (ASIC). A person skilled in the art will understand that the exemplary embodiments can also be implemented as a combination of hardware and software modules.

Additionally, when describing some embodiments, the disclosure may have disclosed a method and/or process as a particular sequence of steps. However, unless otherwise required, it will be appreciated the method or process should not be limited to the particular sequence of steps disclosed. Other sequences of steps may be possible. The particular order of the steps disclosed herein should not be construed as undue limitations. Unless otherwise required, a method and/or process disclosed herein should not be limited to the steps being carried out in the order written. The sequence of steps may be varied and still remain within the scope of the disclosure.

Further, in the description herein, the word "substantially" whenever used is understood to include, but not restricted to, "entirely" or "completely" and the like. In addition, terms such as "comprising", "comprise", and the like whenever used, are intended to be non- restricting descriptive language in that they broadly include elements/components recited after such terms, in addition to other components not explicitly recited. Further, terms such as "about", "approximately" and the like whenever used, typically means a reasonable variation, for example a variation of +/- 5% of the disclosed value, or a variance of 4% of the disclosed value, or a variance of 3% of the disclosed value, a variance of 2% of the disclosed value or a variance of 1 % of the disclosed value.

Furthermore, in the description herein, certain values may be disclosed in a range. The values showing the end points of a range are intended to illustrate a preferred range. Whenever a range has been described, it is intended that the range covers and teaches all possible sub-ranges as well as individual numerical values within that range. That is, the end points of a range should not be interpreted as inflexible limitations. For example, a description of a range of 1 % to 5% is intended to have specifically disclosed sub-ranges 1 % to 2%, 1 % to 3%, 1 % to 4%, 2% to 3% etc., as well as individually, values within that range such as 1 %, 2%, 3%, 4% and 5%. The intention of the above specific disclosure is applicable to any depth/breadth of a range.

Different exemplary embodiments can be implemented in the context of data structure, program modules, program and computer instructions executed in a computer implemented environment. A general purpose computing environment is briefly disclosed herein. One or more exemplary embodiments may be embodied in one or more computer systems, such as is schematically illustrated in FIG.16.

One or more exemplary embodiments may be implemented as software, such as a computer program being executed within a computer system 1600, and instructing the computer system 1600 to conduct a method of an exemplary embodiment.

The computer system 1600 comprises a computer unit 1602, input modules such as a keyboard 1604 and a pointing device 1606 and a plurality of output devices such as a display 1608, and printer 1610. A user can interact with the computer unit 1602 using the above devices. The pointing device can be implemented with a mouse, track ball, pen device or any similar device. One or more other input devices (not shown) such as a joystick, game pad, satellite dish, scanner, touch sensitive screen or the like can also be connected to the computer unit 1602. The display 1608 may include a cathode ray tube (CRT), liquid crystal display (LCD), field emission display (FED), plasma display or any other device that produces an image that is viewable by the user.

The computer unit 1602 can be connected to a computer network 1612 via a suitable transceiver device 1614, to enable access to e.g. the Internet or other network systems such as Local Area Network (LAN) or Wide Area Network (WAN) or a personal network. The network 1612 can comprise a server, a router, a network personal computer, a peer device or other common network node, a wireless telephone or wireless personal digital assistant. Networking environments may be found in offices, enterprise-wide computer networks and home computer systems etc. The transceiver device 1614 can be a modem/router unit located within or external to the computer unit 1602, and may be any type of modem/router such as a cable modem or a satellite modem.

It will be appreciated that network connections shown are exemplary and other ways of establishing a communications link between computers can be used. The existence of any of various protocols, such as TCP/IP, Frame Relay, Ethernet, FTP, HTTP and the like, is presumed, and the computer unit 1602 can be operated in a client-server configuration to permit a user to retrieve web pages from a web-based server. Furthermore, any of various web browsers can be used to display and manipulate data on web pages. The computer unit 1602 in the example comprises a processor 1618, a Random

Access Memory (RAM) 1620 and a Read Only Memory (ROM) 1622. The ROM 1622 can be a system memory storing basic input/ output system (BIOS) information. The RAM 1620 can store one or more program modules such as operating systems, application programs and program data. The computer unit 1602 further comprises a number of Input/Output (I/O) interface units, for example I/O interface unit 1624 to the display 1608, and I/O interface unit 1626 to the keyboard 1604. The components of the computer unit 1602 typically communicate and interface/couple connectedly via an interconnected system bus 1628 and in a manner known to the person skilled in the relevant art. The bus 1628 can be any of several types of bus structures including a memory bus or memory controller, a peripheral bus, and a local bus using any of a variety of bus architectures.

It will be appreciated that other devices can also be connected to the system bus 1628. For example, a universal serial bus (USB) interface can be used for coupling a video or digital camera to the system bus 1628. An IEEE 1394 interface may be used to couple additional devices to the computer unit 1602. Other manufacturer interfaces are also possible such as FireWire developed by Apple Computer and i.Link developed by Sony. Coupling of devices to the system bus 1628 can also be via a parallel port, a game port, a PCI board or any other interface used to couple an input device to a computer. It will also be appreciated that, while the components are not shown in the figure, sound/audio can be recorded and reproduced with a microphone and a speaker. A sound card may be used to couple a microphone and a speaker to the system bus 1628. It will be appreciated that several peripheral devices can be coupled to the system bus 1628 via alternative interfaces simultaneously.

An application program can be supplied to the user of the computer system 1600 being encoded/stored on a data storage medium such as a CD-ROM or flash memory carrier. The application program can be read using a corresponding data storage medium drive of a data storage device 1630. The data storage medium is not limited to being portable and can include instances of being embedded in the computer unit 1602. The data storage device 1630 can comprise a hard disk interface unit and/or a removable memory interface unit (both not shown in detail) respectively coupling a hard disk drive and/or a removable memory drive to the system bus 1628. This can enable reading/writing of data. Examples of removable memory drives include magnetic disk drives and optical disk drives. The drives and their associated computer-readable media, such as a floppy disk provide nonvolatile storage of computer readable instructions, data structures, program modules and other data for the computer unit 1602. It will be appreciated that the computer unit 1602 may include several of such drives. Furthermore, the computer unit 1602 may include drives for interfacing with other types of computer readable media. The application program is read and controlled in its execution by the processor 1618.

Intermediate storage of program data may be accomplished using RAM 1620. The method(s) of the exemplary embodiments can be implemented as computer readable instructions, computer executable components, or software modules. One or more software modules may alternatively be used. These can include an executable program, a data link library, a configuration file, a database, a graphical image, a binary data file, a text data file, an object file, a source code file, or the like. When one or more computer processors execute one or more of the software modules, the software modules interact to cause one or more computer systems to perform according to the teachings herein. The operation of the computer unit 1602 can be controlled by a variety of different program modules. Examples of program modules are routines, programs, objects, components, data structures, libraries, etc. that perform particular tasks or implement particular abstract data types. The exemplary embodiments may also be practiced with other computer system configurations, including handheld devices, multiprocessor systems, microprocessor-based or programmable consumer electronics, network PCs, minicomputers, mainframe computers, personal digital assistants, mobile telephones and the like. Furthermore, the exemplary embodiments may also be practiced in distributed computing environments where tasks are performed by remote processing devices that are linked through a wireless or wired communications network. In a distributed computing environment, program modules may be located in both local and remote memory storage devices.

Described exemplary embodiments of the system and method for estimating a trajectory of a vehicle may also be implemented using a wireless and/or portable communications device such as, but not limited to, a smartphone, a tablet computer etc.

In the described exemplary embodiments, the system and method for estimating a trajectory are described for vehicles. However, the system and method for estimating a trajectory are not limited as such, and may be used for estimating the trajectory of other moving animate/inanimate bodies e.g. human or animal. The human/animal may be carrying/wearing a device, e.g. smartphone, which is capable of measuring and/or recording movement data suitable for use by the system and method for estimating a trajectory. In the described exemplary embodiments, the system and method for estimating a trajectory are described for outdoor applications e.g. estimating a trajectory of a vehicle in the CDB area of Singapore. However, the system and method for estimating a trajectory are not limited as such, and may be used for indoor applications such as inside a building e.g. shopping mall, underground network of tunnels etc.

In the described exemplary embodiments, the movement data is described to be measured by a microelectromechanical sensors (MEMS) based accelerometer and gyroscope device. However, measurement of movement data is not limited as such, and may be measured using any other instruments such as position sensors, speed sensors and the like.

In the described exemplary embodiments, sets of conditions and criteria for qualifying map features, travel features and trajectory candidates have been described. It would be appreciated that the conditions and criteria described herein may be changed, varied or adjusted, added or subtracted from the sets described herein.

In the described exemplary embodiments, a dynamic time warping (DTW) technique is used for evaluating the trajectory candidates. However, evaluation of trajectory candidates is not limited as such, and other suitable evaluation techniques may be used. For example, usage of Euclidean distance may also be used. It has been recognized by the inventors that DTW is currently a robust and suitable evaluation technique. It will be appreciated by a person skilled in the art that other variations and/or modifications may be made to the specific embodiments without departing from the scope of the invention as broadly described. The present embodiments are, therefore, to be considered in all respects to be illustrative and not restrictive.

Claims

1 . A trajectory estimation system for a vehicle, the system comprising, a map feature module comprising one or more map features, each map feature being an instance of a deviation from a substantially straight path on a map;

a vehicle movement data module comprising one or more travel features, each travel feature being an instance of a deviation from a substantially straight path, the one or more travel features being obtained from movement data of the vehicle;

a processing module configured to match each travel feature with the one or more map features and to generate one or more trajectory candidates based on the one or more travel features; and

wherein the processing module is further configured to identify a final trajectory candidate from the generated one or more trajectory candidates.

2. The system of claim 1 , wherein the generation of the one or more trajectory candidates is based on a known sequence of the one or more travel features.

3. The system of claim 1 or 2, wherein the generation of the one or more trajectory candidates comprises the processing module being configured to sample each of the generated one or more trajectory candidates and to sample the movement data; and further being configured to evaluate the sampled one or more trajectory candidates and the sampled movement data.

4. The system of any one of claims 1 to 3, further comprising a map feature extraction module configured to extract the one or more map features from the map to form a map feature list.

5. The system of claim 4, wherein the map feature extraction module is further configured to extract new map features from an updated map to update the map feature list.

6. The system of any one of claims 1 to 5, wherein the movement data comprises data measured by a microelectromechanical sensors (MEMS) based accelerometer and gyroscope device.

7. The system of any one of claims 1 to 6, wherein the movement data comprises speed and angular data.

8. The system of any one of claims 1 to 7, wherein the vehicle movement data module is configured to extract the one or more travel features from the movement data.

9. The system of any one of claims 1 to 8, wherein the processing module is further configured to calculate a degree of confidence for each of the one or more trajectory candidates.

10. A method for estimating a trajectory of a vehicle, the method comprising, providing one or more map features, each map feature being an instance of a deviation from a substantially straight path on a map;

providing one or more travel features, each travel feature being an instance of a deviation from a substantially straight path, the one or more travel features being obtained from movement data of the vehicle;

matching each travel feature with the one or more map features;

generating one or more trajectory candidates based on the one or more travel features; and

identifying a final trajectory candidate from the generated one or more trajectory candidates.

1 1 . The method of claim 10, wherein the step of generating one or more trajectory candidates comprises using a known sequence of the one or more travel features.

12. The method of claim 10 or 1 1 , wherein the step of generating one or more trajectory candidates comprises sampling each of the generated one or more trajectory candidates and sampling the movement data; and evaluating the sampled one or more trajectory candidates and the sampled movement data.

13. The method of any one of claims 10 to 12, further comprising a step of extracting the one or more map features from the map to form a map feature list.

14. The method of claim 13, further comprising a step of extracting new map features from an updated map to update the map feature list.

15. The method of any one of claims 10 to 14, further comprising obtaining the movement data from data measured by a microelectromechanical sensors (MEMS) based accelerometer and gyroscope device.

16. The method of any one of claims 10 to 15, further comprising processing the movement data to obtain speed and angular data.

17. The method of any one of claims 10 to 16, further comprising extracting the one or more travel features from the movement data.

18. The method of any one of claims 10 to 17, further comprising calculating a degree of confidence for each of the one or more trajectory candidates.

19. A non-transitory computer readable storage medium having stored thereon instructions for instructing a processing unit of a system to execute a method for estimating a trajectory of a vehicle, the method comprising,

providing one or more map features, each map feature being an instance of a deviation from a substantially straight path on a map;

matching each travel feature with the one or more map features;