PROCESSING SPATIAL FEATURES

Abstract

There is disclosed a method of updating a database of spatial features, said spatial features being associated with a region, and the method comprising: receiving positioning data that has been collected at a plurality of locations within the region; processing the collected positioning data to identify at least one candidate spatial feature associated with the region; identifying at least one other spatial feature corresponding to said at least one candidate spatial feature, said at least one other spatial feature and said at least one candidate spatial feature as a whole constituting matching spatial features; processing said matching spatial features; and updating the database of spatial features in dependence on the processing of said matching spatial features.

Claims

1. A method of updating a database of spatial features, said spatial features being associated with a region, and the method comprising: receiving positioning data that has been collected at a plurality of locations within the region; processing the collected positioning data to identify at least one candidate spatial feature associated with the region; identifying at least one other spatial feature corresponding to said at least one candidate spatial feature, said at least one other spatial feature and said at least one candidate spatial feature as a whole constituting matching spatial features; processing said matching spatial features; and updating the database of spatial features in dependence on the processing of said matching spatial features.

2. A method according to claim 1, wherein identifying at least one other spatial feature comprises deriving at least one spatial feature from additional positioning data collected within the region.

3. A method according to claim 1, wherein identifying at least one other spatial feature comprises accessing the database to identify within the database at least one stored spatial feature corresponding to said at least one candidate spatial feature.

4. A method according to claim 1, further comprising receiving geographical data relating to a geographical region in the vicinity of the region, and wherein identifying at least one other spatial feature comprises deriving said at least one other spatial feature from the geographical data.

5. A method according to claim 4, wherein processing said matching spatial features comprises comparing the position of said at least one candidate spatial feature with the position of said at least one spatial feature.

6. A method according to claim 4, wherein the geographical data defines at least one spatial feature corresponding to an access point of a building.

7. A method according to claim 4, wherein at least some of said at least one candidate spatial features are inside a building and the geographical data defines at least one spatial feature outside the building.

8. A method according to claim 4, wherein processing said matching spatial features comprises using the geographical data to validate or adjust said matching spatial features.

9. A method according to claim 4, wherein the geographical data includes at least one recorded path, and processing said matching spatial features comprises validating or adjusting said matching spatial features in dependence on said at least one recorded path.

10. A method according to claim 9, further comprising correlating said matching spatial features with at least one position in said at least one recorded path to determine a quality measure associated with said matching spatial features.

11. A method according to claim 10, further comprising revising said matching spatial features in dependence on said at least one position in said at least one recorded path.

12. A method according to claim 1, wherein processing said matching spatial features further comprises generating at least one composite spatial feature in dependence on said matching spatial features, and updating the database of spatial features includes storing said composite spatial feature in the database.

13. A method according to claim 1, further comprising assigning each candidate spatial feature to at least one of a plurality of groups of candidate spatial features.

14. A method according to claim 13, wherein each candidate spatial feature is assigned to a respective one of said groups of candidate spatial features in dependence on its similarity to other candidate spatial features in the same group.

15. A method according to claim 13, wherein each group corresponds to a geographical sub-division of the region.

16. A method according to claim 1, wherein processing the collected positioning data comprises identifying a plurality of said locations as node locations, and generating node spatial features corresponding to said node locations.

17. A method according to claim 16, wherein processing the collected positioning data further comprises identifying locations intermediate node locations as path locations, and generating path spatial features corresponding to said path locations.

18. A method according to claim 17, wherein all path locations intermediate two node locations are transformed into a single path spatial feature.

19. A method according to claim 1, further comprising normalizing the candidate spatial features based on at least one of: travel time, speed of movement, distance, starting position, end position, a turning point; and a floor change point or region.

20. A method according to claim 1, further comprising normalising one or more candidate spatial features by one or more of: rotating a said candidate spatial feature; scaling a said candidate spatial feature; splitting positioning data which relates to relatively long journeys into smaller data portions relating to shorter journeys and deriving one or more candidate spatial features from the said smaller data portions; combining positioning data which relates to a plurality of relatively shorter journeys to form a larger data portion relating to a longer journey and deriving one or more candidate spatial features from the said larger data portion; and normalising a said candidate spatial feature in dependence on a signal measurement profile associated with the said candidate spatial feature.

21. A method according to claim 13, wherein the method further comprises generating at least one path estimate in dependence on said at least one candidate spatial feature, and selecting said at least one other spatial feature matching said at least one path estimate.

22. A method according to claim 1, further comprising determining a quality assessment for each candidate spatial feature, and processing said matching spatial features in dependence on said quality assessment.

23. A method according to claim 1, wherein a plurality of said at least one candidate spatial features correspond to a single spatial feature.

24. A method according to claim 1, wherein updating the database of spatial features comprises storing at least one hypothesis of at least one spatial feature.

25. A method according to claim 24, further comprising assigning each hypothesis in the database to at least one of a plurality of groups of hypotheses.

26. A method according to claim 25, wherein each hypothesis is assigned to a respective one of said groups of hypotheses in dependence on its similarity to other hypotheses in the same group.

27. A method according to claim 25, wherein each group corresponds to a geographical sub-division of the region.

28. A method according to claim 1, wherein a signal measurement profile is associated with each candidate spatial feature.

29. A method according to claim 28, wherein the signal measurement profile includes at least one of: electromagnetic signal strength measurements, identifiers associated with electromagnetic signal sources, environmental mapping, distance measurements, image data, acoustic data, data quality assessments, propagation model parameters, and path loss parameters.

30. A method according to claim 13, wherein the method further comprises processing said matching spatial features in the form of a plurality of node spatial features and at least one path spatial feature.

31. A method according to claim 30, wherein processing said matching spatial features comprises identifying matching node spatial features in said matching spatial features, and combining said matching node spatial features into a single node.

32. A method according to claim 31, further comprising adjusting path spatial features in said matching spatial features to conform to the changed node spatial features.

33. A method according to claim 1, wherein the database of spatial features includes stored positioning data associated with said at least one other spatial feature, and processing said matching features includes processing said stored positioning data.

34. A method according to claim 33, further comprising storing at least a portion of the collected positioning data in the database of spatial features.

35. A method according to claim 1, wherein the positioning data is received from at least one positioning module associated with at least one mobile device.

36. A method according to claim 1, further comprising synchronizing with another device, wholly or in part, at least one of: the collected positioning data, said at least one candidate spatial feature, and said at least one other spatial feature.

37. A method according to claim 1, further comprising accessing the database of spatial features to assist a location service for a mobile device.

38. A data processing system including a processor and associated memory, said data processing system being operable to update a database of spatial features, said spatial features being associated with a region, and said data processing system being programmed to perform a method of: receiving positioning data that has been collected at a plurality of locations within the region; processing the collected positioning data to identify at least one candidate spatial feature associated with the region; identifying at least one other spatial feature corresponding to said at least one candidate spatial feature, said at least one other spatial feature and said at least one candidate spatial feature as a whole constituting matching spatial features; processing said matching spatial features; and updating the database of spatial features in dependence on the processing of said matching spatial features.

39. A non-transitory computer readable carrier storing computer program code for causing a data processing system to update a database of spatial features, said spatial features being associated with a region, said data processing system including a processor and associated memory, and the computer program code, when stored in said memory and executed by said processor, causing said data processing system to perform a method of: receiving positioning data that has been collected at a plurality of locations within the region; processing the collected positioning data to identify at least one candidate spatial feature associated with the region; identifying at least one other spatial feature corresponding to said at least one candidate spatial feature, said at least one other spatial feature and said at least one candidate spatial feature as a whole constituting matching spatial features; processing said matching spatial features; and updating the database of spatial features in dependence on the processing of said matching spatial features.

Description

DESCRIPTION OF THE DRAWINGS

[0070] An example embodiment of the present invention will now be illustrated with reference to the following figures in which:

[0071] FIG. 1 is a table of typical positioning data;

[0072] FIG. 2 is a flowchart of a method of updating a database of spatial features;

[0073] FIG. 3 is a flowchart showing the method of FIG. 2 in more detail;

[0074] FIG. 4 is a flowchart showing the pre-processing step of FIG. 3 in more detail;

[0075] FIG. 5 is a flowchart of a method of synchronising spatial features updated in accordance with the method of FIG. 2;

[0076] FIG. 6 is a schematic of a device for use with the method of FIG. 2;

[0077] FIG. 7 is a schematic of a central controller for use with the method of FIG. 5;

[0078] FIG. 8 is a schematic of a first embodiment of a system in accordance with the method of FIG. 2;

[0079] FIG. 9 is a schematic of a second embodiment of a system in accordance with the method of FIG. 2;

[0080] FIG. 10 is a schematic of a third embodiment of a system in accordance with the method of FIG. 2;

[0081] FIGS. 11a and 11b are example floor plans from a building showing an example navigation path through the building;

[0082] FIGS. 12a and 12b are a plan view and isometric view of the example navigation path of FIGS. 11a and 11b;

[0083] FIGS. 13a and 13b are illustrations of the decomposition of the navigation path of FIGS. 12a and 12b into different groups of spatial features;

[0084] FIGS. 14a and 14b are illustrations of the simplification of the groups of FIG. 13b into separate spatial features;

[0085] FIG. 15 is an illustration of a stored path relating to the building of FIGS. 11a and 11b;

[0086] FIG. 16 is an illustration of the simplification of the stored path of FIG. 15 into separate spatial features;

[0087] FIGS. 17a and 17b illustrate the combination of multiple estimated nodes into a single node;

[0088] FIG. 18 illustrates a composite path formed by combining nodes according to the process shown in FIGS. 17a and 17b;

[0089] FIGS. 19a and 19b illustrate the decomposition of the composite path of FIG. 18 into a minimum number of true paths;

[0090] FIGS. 20a, 20b and 20c illustrate the decomposition of the composite path of FIG. 18 into a minimum number of non-overlapping true paths; and

[0091] FIGS. 21a and 21b illustrate the use of electromagnetic signals profiles in an embodiment of the method of FIG. 2.

DETAILED DESCRIPTION OF AN EXAMPLE EMBODIMENT

[0092] One real life example of indoor spatial features crowd-sourcing involves a navigation session relating to step by step navigation points followed by a mobile user carrying a smart phone. For every navigation session, the phone would store all coordinates associated with universal time stamps and the correlated motion vector. The motion vector is an estimation of pedestrian movement as distance and bearing from the last coordinates.

[0093] The table of FIG. 1 provides an example of input data, where [0094] Position type: represents the method used in obtaining the coordinates; [0095] Universal time: UTC time in Unix format; [0096] Lat/Ing/alt: The 3D coordinates defining the location of the phone at this time; [0097] Estimated error: An indication of possible error in meters; [0098] Floor: An indication to the floor number in multi-storey building if applicable; [0099] Quality Index: An indication to the confidence in the data and the quality of the information sources such as GPS, WiFi, Bluetooth®, Accelerometer and digital compass; [0100] Speed: an estimation of the walking or movement speed in meter per second; [0101] Distance: An estimation of how many meters the phone moved since last entry; and [0102] Bearing: An estimation of the phone bearing, movement direction, during this time.

[0103] Once the user decides to end the navigation session, the input data mentioned above will be pre-processed and inserted into the pool of spatial features. This initial pre-processing comprises one or more or all of the following steps: [0104] Split the data into floors and generate one more floor changing spatial feature as a polygon containing consecutive data points with different floor values; [0105] Streaming each group of floor data into a filter to identify the turning points coordinates as a polygon containing consecutive data points with bearing exceeding the filter threshold; and [0106] Process every set of data points between (every) consecutive turning points to generate a path line in a form of a line or arc associated with two references to either turning points polygons or floor changing polygons or combination of both.

[0107] As a result of processing the input data for one navigation session, a set of spatial features will be added to a local or central pool of spatial features.

[0108] The next step comprises post processing all the data in the pool to update the spatial features database. The post processing method comprises one or more or all of the following steps: [0109] Initial correlation check of all data in pool to group them into multiple matches; [0110] For each group: [0111] Perform a normalization based on travel time, speed and distance and modify the start point, end point as well as any turning points or floor changing points; [0112] Feed all possibilities into a spatial filter that will output multiple estimations of a true path, each associated with time stamp, statistical measures and uncertainty values; [0113] Fetch from the spatial database all possible matches to the estimated true path; [0114] Break all estimated true path into path lines and nodes (nodes being turning points or floor switching points); [0115] Combine every matching group of nodes into one node and adjust the path lines to follow the combined nodes; [0116] Update the spatial features database with the combined nodes, path lines and the new ones with no matches.

[0117] If the spatial features database is hosted locally, or shared between limited numbers of mobile devices, the method may also involve a step of synchronizing these data to a central database where it can be shared with larger number of users or mobile devices.

[0118] The synchronization process may comprise one or more or all of the following steps: [0119] Select from the local database all spatial features that have been updated after the last synchronization run; [0120] Send the selected data to the central controller over any means of data transferring; [0121] On receiving the data the controller fetches from the central database all possible matching features; [0122] Run every matching pair into combining filter (same steps as post processing method described above) in respect to the time stamp, statistical measures and uncertainty values; [0123] Update the central database [0124] Send the updates to the local controller to update the local database.

[0125] The spatial features may comprise any of the following or any other suitable spatial features: areas (or spaces) within the indoor region (such as rooms or corridors), linear features (e.g. walls), gaps in features (e.g. portals such as doors), floor-change features such as elevators, escalators or staircases, turning points, ends of corridors and so on.

[0126] The methods and systems mentioned above will now be described in more detail, with reference to FIGS. 2 to 20.

[0127] FIG. 2 is a flowchart of a method of updating a database of spatial features according to one embodiment.

[0128] In step S200 positioning data, collected at a plurality of locations, is received. The data may be in the form of the data shown in FIG. 1, for example. The positioning data is typically compiled by one or more mobile devices, each having one or more positioning modules including Global Navigation Satellite Systems (GNSS), Wi-Fi rangefinder systems, pedometer dead reckoning (PDR) systems, and so on, though typically the areas of interest are indoors and therefore the available data is a mixture of low accuracy absolute positioning data (for example from the Wi-Fi rangefinding) and low- to high-accuracy relative positioning data (from the PDR systems, for example).

[0129] In Step S202 candidate spatial features are identified, as explained in more detail below (and above). In Step S204, other spatial features (for example from a pool of features or from the same or a further spatial features database) corresponding to the candidate spatial features are identified, both sets of features together constituting ‘matching spatial features’. The database of spatial features may be a local or remote database, for example used by a positioning service. In step S206, all the matching spatial features are processed, typically to create improved estimates of spatial features, and the spatial features database is updated (S208) as a consequence of the processing, typically by storing (at least) the improved estimates.

[0130] FIG. 3 is a flowchart showing the method of FIG. 2 in more detail. The flowchart covers the updating of existing features in a spatial features database. However, with appropriate modification (for example to step S308 below, if it refers instead to spatial features within a pool of collected data, rather than to data in an existing spatial features database) a method of creating new entries in the database is described.

[0131] In step S300, positioning data is received as before. In step S302, the positioning data is pre-processed, as will be explained below. While beneficial, this step can be omitted if necessary and/or appropriate.

[0132] In step S304 the positioning data is normalised. The positioning data is adjusted to take into account factors such as travel time, speed and distance, with start point, end points and any relevant turning points and floor-changing points being modified as necessary as a consequence. While beneficial, this step can be omitted if necessary and/or appropriate.

[0133] In step S306, the (if appropriate, pre-processed and normalised) positioning data is processed with a spatial filter to generate multiple estimations of ‘true’ path. As part of Step S306 (or otherwise), a quality measure (or multiple measures) may be applied to the generated estimates, based for example on the type of positioning and any other relevant factors.

[0134] In step S308, all possible matches to the estimated true path(s) are retrieved from the database of spatial features. The matches may be limited by any appropriate means, for example geographically limited, or limited to a particular number or quality of match. As mentioned above, the described process may be adapted, by search a raw pool of collected spatial features data (rather than an existing spatial features database) to create new data in a spatial features database. Where appropriate, references herein to selecting from a spatial feature database (and/or updating existing data in the database) can be applied alternatively or additionally to selecting from a different (local or other) pool of collected spatial features data (and/or creating new data in the database).

[0135] In step S310 the estimated true path(s), including the candidate true path(s) generated by the spatial filter and the true path(s) retrieved from the database are converted into path lines and nodes. (The processing of the candidate and stored spatial features may as appropriate be divided into separate processing steps at different times.)

[0136] In step S312 matching nodes are grouped into a single node. Nodes which do not match any other may result in new spatial features being generated. In step S314 path lines are adjusted to conform to the amended nodes. In step S316, the spatial features database is updated with the combined nodes and updated path lines, any new spatial features arising from the processing in step S314, and (optionally, though usefully) additional positioning data used to create the new estimates, so that subsequent processing steps can take the positioning data into account when creating estimates, and so on.

[0137] FIG. 4 is a flowchart showing the pre-processing step of FIG. 3 in more detail.

[0138] In step S400, the data is divided into different floors (or other geographical regions/sub-regions, as appropriate, including divisions within the same floor or vertical height). In step S402, floor-changing spatial features are converted into polygons (‘floor-changing polygons’) containing consecutive data points with different floor values, although other data structures and formats are of course possible.

[0139] In step S404, each group of floor data is processed by a filter (or other appropriate means) to identify turning points, and in step S406 ‘turning-point polygons’ are generated, consisting of polygons containing consecutive data points with bearing exceeding a relevant threshold.

[0140] In step S408 every set of data points between consecutive turning points are processed to generate path lines in the form of a line or arc, and each path line is associated with two references, each reference being either to a turning-point polygon or a floor-changing polygon.

[0141] Thus, the positioning data has been simplified into a floor-changing spatial features, turning-point spatial features, and a series of paths linking them together.

[0142] FIG. 5 is a flowchart of a method of synchronising spatial features updated in accordance with the method of FIG. 2. This synchronising method relates to a particular embodiment (see below) in which at least one device carries out local processing and storage, and a central controller maintains a central registry of spatial features data, and the two carry out a synchronisation process to ensure that both data stores are up to date. The synchronising method may be executed at any appropriate moment, either on demand by a user, in accordance with a schedule, after a certain amount of data has been updated, acquired or processed, or on request from the central controller, for example.

[0143] In step S500, a local device (having its own local spatial features database) selects from its spatial features database all spatial features which have been updated after the last synchronisation process. In step S502, the device sends the selected data to a central server/controller. In step S504, the central server fetches from its own central spatial features database all possible spatial features matching the spatial features data received from the device. In Step S506, the central server runs every matching pair of spatial features into a combining filter, mirroring the processing carried out at the local device (including steps shown in FIG. 3 and described above, for example). The central database is then updated. Because the central server may have received additional data from other devices, or may apply different (for example more sophisticated) processing, the result of the processing may differ from that carried out originally at the device. Accordingly, in step S510, any updated data (with reference to what is known or inferred to be stored at the device, which may for the reasons mentioned above go beyond the data modified in step S508) is sent back to the device. The device then inserts the data received from the central server into its local spatial features database, but in a variant of the present embodiment the local device may as appropriate reprocess the data received from the central server before updating its own database (for example if new data has been received in the meantime).

[0144] FIG. 6 is a schematic of a device for use with the method of FIG. 2. The device 600, which may be a handheld, mobile or other device, contains a processor 602, data storage 604 (which may include the above-mentioned local database of spatial features), (optional) user interface 606, (optional) network (or other communications) interface 608, and one or more positioning modules 610, 612.

[0145] FIG. 7 is a schematic of an optional central controller for use with the method of FIG. 5. The central controller contains, for example, a processor 702, data storage 704 (which may include the above-mentioned central database of spatial features) and network interface 706.

[0146] FIG. 8 is a schematic of a first embodiment of a system in accordance with the method of FIG. 2. In this embodiment, a single device 800 is provided, with a corresponding database 810 of spatial features.

[0147] FIG. 9 is a schematic of a second embodiment of a system in accordance with the method of FIG. 2. In this embodiment, a central server/controller 910 has an associated database of spatial features 912, connected to a plurality of devices 930, 932, 934 via a network 920 or other communications link. The devices are typically autonomous (for example handheld devices such as smartphones) but do not contain a local spatial features database (though they may have local caches of various sorts). In one mode of operation, the devices 930, 932, 934 used the server 910 as a database server, carrying out spatial features processing locally but using the server database 912 as a repository of the data. In another mode of operation, the processing is carried out partly or wholly at the server 910, which receives positioning data from the devices 930, 932, 934 and transmits back further positioning data, such as an estimated current position of the relevant device, for example.

[0148] FIG. 10 is a schematic of a third embodiment of a system in accordance with the method of FIG. 2. In this embodiment, a central server 1010 as before is associated with a central repository (database) 1012 of spatial features, and in communication with a plurality of devices 1030, 1032, 1034 via a network (or other communications link) 1020. In this embodiment, however, each device 1030, 1032, 1034 is associated with its own local database 1040, 1042, 1044 of spatial features. A method identical to, or similar to, that described above in relation to FIG. 5 is used to synchronise data across all the databases 1012, 1040, 1042, 1044. Other arrangements, for example incorporating a mix of the system of FIGS. 9 and 10, are of course possible.

[0149] A worked example, representing a simplified and abstracted version of a real life example for the sake of ease of explanation, will now be described with reference to FIGS. 11 to 20.

[0150] FIGS. 11a and 11b are example floor plans from a building showing an example navigation path through the building, as might be taken by a user of a mobile device corresponding for example to the device of FIG. 6 in any one of the systems as shown in FIGS. 8 to 10. A lower floor 1100 and a higher floor 1102 are shown, connected by elevators 1120 and a stairwell 1122. The present example relates to consecutive floors, but the same principles may apply, for example, to a journey taken from one floor to another floor several storeys above or below (for example by elevator), or to a journey within one floor or many floors, or in areas limited geographically in other ways (for example in different buildings on the same or on different levels), or wholly or partially outdoors, and so on. The path taken 1110 is shown as a dashed line overlaid on the floor plans, which omit details of offices and so on for simplicity, and is broken in the region of the stairwell 1122, which (like the elevator 1120) constitutes a floor-changing zone as described above. Data (or sampling) points, corresponding to locations where positioning data is collected from at least one positioning module associated with the device, are shown with small solid circles 1112. For ease of illustration, the ‘true path’ taken by a user of the device is shown. In a real life example, there may be more or fewer data points 1112, and the accuracy will typically be lower, especially indoors where a satellite signal is not available for use with GNSS systems. Examples of these inaccuracies, and systems for compensating for them and providing appropriate estimates and quality indices are given in the co-pending applications referred to above.

[0151] FIGS. 12a and 12b are a plan view and isometric view of the example navigation path of FIGS. 11a and 11b. Here the unbroken (true) navigation path 1200 is shown, as well as planes 1210, 1212 representing the two different floors. The landings of the stairwell area are also shown for ease of interpretation.

[0152] FIGS. 13a and 13b are illustrations of the decomposition of the navigation path of FIGS. 12a and 12b into different groups of spatial features. FIG. 13a shows a region 1302 of the navigation path 1300 which is assessed (from prior processing and/or by consideration of the positioning data, e.g. the height) as relating to a floor-changing spatial feature. The navigation path is decomposed into two groups 1310, 1320 corresponding to navigation paths 1312, 1322 within two different floors. The portion of the navigation path relating to the floor-changing spatial feature is simplified, as described above, into a polygon 1332 having one data point per floor. The path 1312 corresponds to the navigation path taken on the lower floor, and the path 1322 corresponds to the navigation path taken on the upper floor.

[0153] FIGS. 14a and 14b are illustrations of the simplification of the groups of FIG. 13b into separate ‘candidate’ (C) spatial features. Here, the two paths 1312, 1322 of FIG. 13b are divided into nodes and ‘simple’ paths C.sub.1 to C.sub.11, which are shown in exploded form for ease of explanation. The path 1312 on the lower floor is decomposed into path C.sub.1, C.sub.2 and a variety of paths C.sub.3, C.sub.4, C.sub.5′ and C.sub.5″ corresponding to different true path estimations 1400 of the same element of the path 1312. In more detail, the true path estimates 1400 include one solution C.sub.3 with two nodes joined by one arcing path (passing through the data point shown with a dashed line, which has been eliminated as part of the process), one solution C.sub.4 with two nodes joined by one straight path, and a further solution C.sub.5′, C.sub.5″ with three nodes (corresponding essentially to the original data points) and two straight paths inbetween. Each of the solutions C.sub.3, C.sub.4, C.sub.5′, C.sub.5″ is attributed a quality measure indicating the quality of the estimate. In a real world example there may be more solutions outputted than as shown in FIGS. 14a and 14b; the set of solutions 1400 are merely indicative.

[0154] The navigation path 1322 from FIG. 13b of the upper floor is decomposed in this example more simply into elements C.sub.6, C.sub.7, C.sub.8, C.sub.9, C.sub.10, C.sub.11, again shown in exploded form in FIG. 14b for ease of illustration. The nodes shown at intersection 1402 will be discussed further below by way of an example of the processing method described above. In FIG. 14b, various data points have been eliminated because they failed to meet the threshold for a turning point, for example because the change in bearing was below a threshold (or, put another way, the angle subtended at the intersection did not fall sufficiently below 180 degrees to be considered to represent a substantial change in direction).

[0155] As a result of the processing illustrated in FIGS. 13 and 14, it will be appreciated that the number of data points has been reduced, and the structure of the spatial features greatly simplified.

[0156] FIG. 15 is an illustration of a stored path relating to the building of FIGS. 11a and 11b, and in particular relating to the lower floor and navigation path 1322 of FIG. 13b. The path is a model (M) of spatial features, and may be stored and/or defined in any appropriate way. In this example the model M defines a particular path through the floor in question. The deviation of the navigated path 1322 from the model path M is illustrated with a dotted line.

[0157] FIG. 16 is an illustration of the simplification of the stored path of FIG. 15 into separate spatial features M.sub.1 to M.sub.7. The process corresponds essentially to that undertaken in FIGS. 14a and 14b. As a result of the process, the model path M is simplified into simple nodes and paths, for ease of comparison with and joint processing with the candidate spatial features in FIGS. 14a and 14b. In one embodiment, spatial features are stored in the database in the form shown in FIG. 16, obviating the need for the present step of processing. The nodes shown at 1600 coincide approximately (geographically) to the nodes shown at 1402 in FIG. 14b.

[0158] FIGS. 17a and 17b illustrate the combination of multiple estimated nodes into a single node N. When the data derived from the model path M is combined with the data derived from the navigation path (in accordance with the method described above), the paths C.sub.10, C.sub.11, M.sub.5, M.sub.6 meet approximately within the area 1700 corresponding to the areas 1402 and 1600 above. As part of the node combining process mentioned earlier, the estimates for the four nodes are combined to form a single node N. The weighting/quality indices associated with the four nodes are taken into account, so that the node N is not necessarily at the geographical centre of the pre-combined nodes. After the node combination, paths are adjusted to conform to the adjusted node positions and the data is simplified. FIG. 17b shows pre-existing path elements M.sub.5, M.sub.6 and a new path element M.sub.8 derived from the (new) positioning data.

[0159] FIG. 18 illustrates a composite path formed by combining nodes according to the process shown in FIGS. 17a and 17b. This shows the effect of combining the path elements M.sub.1 to M.sub.8 resulting from the node combining and re-pathing process mentioned above. The path elements will normally need to be further processed in an appropriate fashion in order to update the database of spatial features.

[0160] FIGS. 19a and 19b illustrate the decomposition of the composite path of FIG. 18 into a minimum number of true paths. Here, paths M.sub.A and M.sub.B represent all possible traversals of the composite path in FIG. 18.

[0161] FIGS. 20a, 20b and 20c illustrate the decomposition of the composite path of FIG. 18 into a minimum number of non-overlapping true paths. Here, paths M.sub.A, M.sub.B and M.sub.C can be reassembled to form the composite path in FIG. 18. This form of spatial features can have benefits for path-finding, for example, but any appropriate storage format can be used.

[0162] FIGS. 21a and 21b illustrate the use of electromagnetic signal profiles in an embodiment of the method of FIG. 2.

[0163] In this embodiment (as also in embodiments described above) the spatial features processing system detects sudden changes in GPS quality metrics to flag an entrance (or exit) and any major change in heading.

[0164] Away from entrances and exits, typically the positioning data received from different mobile devices following a particular path between two nodes (or the same device retracing the same route) is not identical, for example if two or more mobile devices collecting PDR (pedometer dead reckoning) positioning data are oriented differently from each other (if they were in a pocket, in a hand, in a calling position, and so on). In these cases, the direction reported by the compass (and therefore the estimated positions along the path or at the nodes) will look very different in each case. Due to these differences in the collected positioning data, positioning data which relates to the same spatial feature (such as a node or a path) may not be correctly correlated (that is, the correlation algorithm may not in the first instance correctly determine that the positioning data relates to the same spatial feature).

[0165] To assist with this problem, an electromagnetic signal profile (for example, relating to Bluetooth® and/or Wifi signals received by the mobile device as it follows the path in question) can be generated in respect of each candidate spatial feature which is taken into account during the correlation stage (that is, the stage which identifies matching spatial features). Thus, even when the positioning data is not sufficiently similar for the correlation algorithm to identify that it relates to the same spatial feature, the electromagnetic signal profile will provide a secondary indicator which the algorithm can use to determine that the positioning data does indeed relate to the same spatial feature. This can also prevent the identification of false nodes and paths. Ordinarily, the electromagnetic signal profile cannot be used without the positioning data to identify spatial features.

[0166] By way of example, FIG. 21a shows an interior space 2100 and a simplified version of the (actual) path 2102 taken through the space by a user participating in the data collection, and the (actual) nodes 2104, 2106, 2108, 2110 through which the simplified path passes, from entry point 2104 to exit point 2110.

[0167] As mentioned above, when the received data is processed, each of the reported points (nodes) 2104, 2106, 2108, 2110 is associated with an electromagnetic signals profile and may possibly include other profiles such as magnetic field measure. These profiles are then used for matching all submissions from different users to the same group, if they belong to the same node. One example of an electromagnetic signals profile could be represented as a fingerprint array such as:

[0168] {(BSSID, μ.sub.RSSi, σ.sub.RSSi), . . . }

where BSSID is the identifier of the signal source, μ.sub.RSSi is the median of RSSi (received signal strength) values for all submissions that matches this node, and σ.sub.RSSi is the standard deviation of RSSi values for all submissions that matches this node.

[0169] On the other hand, all position data recorded between two nodes are used to create a path line (the individual portions of line 2102) defined by travel distance and covariance matrix indicating if any transformation had to be made in order to fit the path line between nodes. Similar to the nodes each path line would also hold radio profile and other profiles. An example of path line radio profile is explained below:

[0170] {(BSSID, (X, Y), μ.sub.RSSi, σ.sub.RSSi, RSS0, N), . . . }

where x/y are coordinates of the central propagation point on the path line, usually the point with strongest RSSi; and μ.sub.RSSi and σ.sub.RSSi are the statistical values for the central propagation point signal strength. This is required when combining multiple submissions or when there is a range of strong signals in one submission. RSS0 and N are the propagation parameters for a particular path loss model (which describes the propagation between the signal source and the path). Different propagation parameters may be specified for either side of the central propagation point on the path (for example first propagation parameters may be specified for where the path extends between first and second nodes, and second propagation parameters for between the central propagation point and the second node).

[0171] The profile should have multiple entries for all signal sources which were visible throughout the transit on the relevant path line and might have duplicates if the same WAP was seen in two segregated regions of the same path. The signal profile for a path may have duplicated entries for a particular signal source if, for example, that signal source was visible with a first set of parameters over a first portion of the path, visible with a second set of parameters over a second portion of path, and invisible to the mobile device over a third portion of the path. The electromagnetic signal profiles may take any other suitable form.

[0172] As a crowd based solution, each spatial feature would typically have many submissions that will either agree or disagree on certain parameters including location. Therefore, each feature is associated with a quality measure or covariance matrix (see for example the matrix-algebra/covariance-matrix.aspx page at stattrek.com) describing the variance between different submissions of all parameters. An example of such parameters is shown below:

[0173] Node (turning point): {Number of valid submissions, Average location error, Average compass error, Distance from entrance, Accuracy}

[0174] This matrix is created for each group of submissions sharing a similar radio profile, such as 80% matching WAPs and signal strength. Then the matrix is used to cluster such submissions into multiple hypotheses, mainly based on distance but optionally based on any combination of thresholds. A probability is then assigned to each one. Finally the overall data can be plotted as in FIG. 21b, showing multiple hypothesis (unfilled circles) surrounding the favoured hypothesis or actual values (filled circles) in respect of a single path element (shown in dotted line).

[0175] Multiple hypotheses are kept in the database to ensure a smoother switch if further submissions have boosted the probability for any of them. A range of candidates may be selected and tested to determine whether they are over a certain probability threshold, to try and fit combination of multiple features together, such as path lines and nodes. A selected node may be validated against neighbouring path lines, and vice versa.

[0176] Typically the correlation stage is performed on a server, but may alternatively be performed by the mobile device or by a device intermediate the mobile device and the server. The types of electromagnetic signal sources being used are typically terrestrial radio-frequency electromagnetic signal sources, such as (but not limited to) Bluetooth® beacons, Wi-Fi access points and 5G (or other) short range mobile towers and/or transceivers (sometimes referred to as ‘nanocells’ or ‘microcells’).

[0177] With regard to any of the foregoing embodiments and variants, spatial features may be nested and/or abstracted, such that a floor/storey may be considered a single spatial feature, containing within it sub-features such as portals, corridors, and so on. The spatial features database may include or be associated with a database of electromagnetic signal sources (such as wireless access points, Bluetooth® beacons, mobile phone base stations, and so on) available in the vicinity of the region being modelled, so as to assist in the provision of a mobile device location service.

[0178] It will be appreciated that the method described above is also applicable to outdoor regions. Spatial features outdoors may for example include paths, roads, bridges, crossing points, building entrances, and so on. Navigation sessions may partly or wholly extend into outdoor regions. Part of a pre- or post-processing step may include dividing a navigation session into indoor and outdoor portions, for example based on positional data received at a relevant device (for example a poor performance of satellite-based positioning modules, a detection of light levels, or comparison of estimated location with geographical data, and so on). The pre-processing may for example eliminate outdoor portions so as to selectively process only the indoor portions.

[0179] Although the present invention has been described above with reference to specific embodiments, it will be apparent to a skilled person in the art that modifications lie within the spirit and scope of the present invention.