Location determination, mapping, and data management through crowdsourcing

• US 9,510,154 B2
• Filed: 03/04/2015
• Issued: 11/29/2016
• Est. Priority Date: 04/28/2014
• Status: Active Grant

• Current Assignee: Samsung Electronics Co. Ltd. (Samsung Group)
• Original Assignee: Samsung Electronics Co. Ltd. (Samsung Group)
• Inventors: Bennett, Danny, Mori, Koichi, Sudarsan, Satheesh, Jiang, Yifei, Pellet, Yannick, Singh, Jasvinder, Sidhu, Shalinder
• Primary Examiner(s): TAYLOR, NATHAN SCOTT
• Application Number:
  US14/639,076
• Publication Number:
  US 20150312722A1
• Time in Patent Office: 636 Days
• Field of Search: 455/436
• US Class Current: 1/1
• CPC Class Codes: G01C 21/206 specially adapted for indoor navigation
• CPC Class Codes: G01C 21/34 Route searching; Route guidance
• CPC Class Codes: G01S 11/06 using intensity measurements
• CPC Class Codes: G01S 19/05 providing aiding data
• CPC Class Codes: G01S 5/013 Identifying areas in a building
• CPC Class Codes: G01S 5/0244 Accuracy or reliability of position solution or of measurements contributing thereto
• CPC Class Codes: G01S 5/02526 using non-dedicated equipment, e.g. user equipment or crowd-sourcing
• CPC Class Codes: G01S 5/0294 Trajectory determination or predictive filtering, e.g. target tracking or Kalman filtering
• CPC Class Codes: H04W 4/023 using mutual or relative location information between multiple location based services [LBS] targets or of distance thresholds
• CPC Class Codes: H04W 4/029 Location-based management or tracking services
• CPC Class Codes: H04W 84/12 WLAN [Wireless Local Area Networks]

Abstract

Mapping through crowdsourcing includes determining, using a processor, segments for a plurality of trajectories, wherein each trajectory includes radio frequency (RF) data from a communication device, determining, using the processor, RF features for the segments, and forming, using the processor, clusters of the segments according to the RF features. One or more routes of a map are generated from the clusters using the processor.

Claims

1. A method, comprising:

determining, using a processor, segments for a plurality of trajectories, wherein each trajectory comprises radio frequency (RF) data from a communication device;

determining, using the processor, RF features for the segments;

forming, using the processor, clusters of the segments according to the RF features; and

generating, using the processor, routes for a map using the clusters;

wherein;

the RF data comprises Wi-Fi data;

the RF features comprise Wi-Fi features; and

each Wi-Fi feature comprises a wireless access point identifier and a trend for the wireless access point identifier located at a particular distance along one of the segments.

2. The method of claim 1, wherein generating the routes further comprises:

generating segment trees from the clusters; and

generating the map using the segment trees.

3. The method of claim 1, wherein:

the RF data comprises magnetic field data; and

the RF features comprise magnetic field features.

4. The method of claim 3, wherein each magnetic field feature comprises a magnetic field magnitude exceeding a threshold magnetic field magnitude located at a particular distance along one of the segments.

5. The method of claim 1, wherein:

the RF data comprises Wi-Fi data and magnetic field data; and

the RF features comprise Wi-Fi features and magnetic field features.

6. The method of claim 1, further comprising:

correlating the RF data with regions of the map;

adjusting validity scores of units of RF data over time according to a data density of the region correlated with each respective unit of RF data; and

using only selected units of the RF data having a validity score exceeding a minimum validity score when determining segments for the plurality of trajectories.

7. The method of claim 6, further comprising:

determining data invalidity rates for the regions according to the data densities of the regions;

wherein adjusting validity scores comprises decrementing the validity scores of the units of RF data over time using the data invalidity rate of the region of the map correlated with each respective unit of RF data.

8. A system, comprising:

a processor programmed to initiate executable operations comprising;

determining segments for a plurality of trajectories, wherein each trajectory comprises radio frequency (RF) data from a communication device;

determining RF features for the segments;

forming clusters of the segments according to the RF features; and

generating routes for a map using the clusters;

wherein;

the RF data comprises Wi-Fi data;

the RF features comprise Wi-Fi features; and

each Wi-Fi feature comprises a wireless access point identifier and a trend for the wireless access point identifier located at a particular distance along one of the segments.

9. The system of claim 8, wherein generating the routes further comprises:

generating segment trees from the clusters; and

generating the map using the segment trees.

10. The system of claim 8, wherein:

the RF data comprises magnetic field data; and

the RF features comprise magnetic field features.

11. The system of claim 10, wherein each magnetic field feature comprises a magnetic field magnitude exceeding a threshold magnetic field magnitude located at a particular distance along one of the segments.

12. The system of claim 8, wherein:

the RF data comprises Wi-Fi data and magnetic field data; and

the RF features comprise Wi-Fi features and magnetic field features.

13. The system of claim 8, wherein the processor is further programmed to initiate executable operations comprising:

correlating the RF data with regions of the map;

adjusting validity scores of units of RF data over time according to a data density of the region correlated with each respective unit of RF data; and

using only selected units of the RF data having a validity score exceeding a minimum validity score when determining segments for the plurality of trajectories.

14. The system of claim 13, wherein the processor is further programmed to initiate executable operations comprising:

determining data invalidity rates for the regions of the map according to the data densities of the regions;

wherein adjusting validity scores comprises decrementing the validity scores of the units of RF data over time using the data invalidity rate of the region of the map correlated with each respective unit of RF data.

15. A non-transitory computer-readable storage medium having instructions stored thereon which, when executed by a processor, perform a method comprising:

determining segments for a plurality of trajectories, wherein each trajectory comprises radio frequency (RF) data from a communication device;

determining RF features for the segments;

forming clusters of the segments according to the RF features; and

generating routes for a map using the clusters;

wherein;

the RF data comprises Wi-Fi data;

the RF features comprise Wi-Fi features; and

each Wi-Fi feature comprises a wireless access point identifier and a trend for the wireless access point identifier located at a particular distance along one of the segments.

16. The non-transitory computer-readable storage medium of claim 15, wherein generating the routes further comprises:

generating segment trees from the clusters; and

generating the map using the segment trees.

17. The non-transitory computer-readable storage medium of claim 15, wherein:

the RF data comprises magnetic field data; and

the RF features comprise magnetic field features.

18. The non-transitory computer-readable storage medium of claim 17, wherein each magnetic field feature comprises a magnetic field magnitude exceeding a threshold magnetic field magnitude located at a particular distance along one of the segments.

19. The non-transitory computer-readable storage medium of claim 15, wherein:

the RF data comprises Wi-Fi data and magnetic field data; and

the RF features comprise Wi-Fi features and magnetic field features.

20. The non-transitory computer-readable storage medium of claim 15, further comprising:

correlating the RF data with regions of the map;

adjusting validity scores of units of RF data over time according to a data density of the region correlated with each respective unit of RF data; and

using only selected units of RF data having a validity score exceeding a minimum validity score when determining segments for the plurality of trajectories.

21. The non-transitory computer-readable storage medium of claim 20, further comprising:

determining data invalidity rates for the regions of the map according to the data densities of the regions;

wherein adjusting validity scores comprises decrementing the validity scores of the units of RF data over time using the data invalidity rate of the region of the map correlated with each respective unit of RF data.

22. A method, comprising:

determining, using a processor, segments for a plurality of trajectories, wherein each trajectory comprises radio frequency (RF) data from a communication device;

determining, using the processor, RF features for the segments;

forming, using the processor, clusters of the segments according to the RF features; and

generating, using the processor, routes for a map using the clusters;

wherein;

the RF data comprises magnetic field data;

the RF features comprise magnetic field features; and

each magnetic field feature comprises a magnetic field magnitude exceeding a threshold magnetic field magnitude located at a particular distance along one of the segments.

23. The method of claim 22, wherein generating the routes further comprises:

generating segment trees from the clusters; and

generating the map using the segment trees.

24. The method of claim 22, wherein:

the RF data comprises Wi-Fi data; and

the RF features comprise Wi-Fi features.

25. The method of claim 24, wherein each Wi-Fi feature comprises a wireless access point identifier and a trend for the wireless access point identifier located at a particular distance along one of the segments.

26. The method of claim 22, wherein:

the RF data comprises Wi-Fi data and magnetic field data; and

the RF features comprise Wi-Fi features and magnetic field features.

27. The method of claim 22, further comprising:

correlating the RF data with regions of the map;

adjusting validity scores of units of RF data over time according to a data density of the region correlated with each respective unit of RF data; and

using only selected units of the RF data having a validity score exceeding a minimum validity score when determining segments for the plurality of trajectories.

28. The method of claim 27, further comprising:

determining data invalidity rates for the regions according to the data densities of the regions;

wherein adjusting validity scores comprises decrementing the validity scores of the units of RF data over time using the data invalidity rate of the region of the map correlated with each respective unit of RF data.

29. A system, comprising:

a processor programmed to initiate executable operations comprising;

determining segments for a plurality of trajectories, wherein each trajectory comprises radio frequency (RF) data from a communication device;

determining RF features for the segments;

forming clusters of the segments according to the RF features; and

generating routes for a map using the clusters;

wherein;

the RF data comprises magnetic field data;

the RF features comprise magnetic field features; and

each magnetic field feature comprises a magnetic field magnitude exceeding a threshold magnetic field magnitude located at a particular distance along one of the segments.

30. The system of claim 29, wherein generating the routes further comprises:

generating segment trees from the clusters; and

generating the map using the segment trees.

31. The system of claim 29, wherein:

the RF data comprises Wi-Fi data; and

the RF features comprise Wi-Fi features.

32. The system of claim 31, wherein each Wi-Fi feature comprises a wireless access point identifier and a trend for the wireless access point identifier located at a particular distance along one of the segments.

33. The system of claim 29, wherein:

the RF data comprises Wi-Fi data and magnetic field data; and

the RF features comprise Wi-Fi features and magnetic field features.

34. The system of claim 29, wherein the processor is further programmed to initiate executable operations comprising:

correlating the RF data with regions of the map;

adjusting validity scores of units of RF data over time according to a data density of the region correlated with each respective unit of RF data; and

using only selected units of the RF data having a validity score exceeding a minimum validity score when determining segments for the plurality of trajectories.

35. The system of claim 34, wherein the processor is further programmed to initiate executable operations comprising:

determining data invalidity rates for the regions of the map according to the data densities of the regions;

wherein adjusting validity scores comprises decrementing the validity scores of the units of RF data over time using the data invalidity rate of the region of the map correlated with each respective unit of RF data.

36. A non-transitory computer-readable storage medium having instructions stored thereon which, when executed by a processor, perform a method comprising:

determining segments for a plurality of trajectories, wherein each trajectory comprises radio frequency (RF) data from a communication device;

determining RF features for the segments;

forming clusters of the segments according to the RF features; and

generating routes for a map using the clusters;

wherein;

the RF data comprises magnetic field data;

the RF features comprise magnetic field features; and

each magnetic field feature comprises a magnetic field magnitude exceeding a threshold magnetic field magnitude located at a particular distance along one of the segments.

37. The non-transitory computer-readable storage medium of claim 36, wherein generating the routes further comprises:

generating segment trees from the clusters; and

generating the map using the segment trees.

38. The non-transitory computer-readable storage medium of claim 36, wherein:

the RF data comprises Wi-Fi data; and

the RF features comprise Wi-Fi features.

39. The non-transitory computer-readable storage medium of claim 38, wherein each Wi-Fi feature comprises a wireless access point identifier and a trend for the wireless access point identifier located at a particular distance along one of the segments.

40. The non-transitory computer-readable storage medium of claim 36, wherein:

the RF data comprises Wi-Fi data and magnetic field data; and

the RF features comprise Wi-Fi features and magnetic field features.

41. The non-transitory computer-readable storage medium of claim 36, further comprising:

correlating the RF data with regions of the map;

adjusting validity scores of units of RF data over time according to a data density of the region correlated with each respective unit of RF data; and

using only selected units of RF data having a validity score exceeding a minimum validity score when determining segments for the plurality of trajectories.

42. The non-transitory computer-readable storage medium of claim 41, further comprising:

determining data invalidity rates for the regions of the map according to the data densities of the regions;

wherein adjusting validity scores comprises decrementing the validity scores of the units of RF data over time using the data invalidity rate of the region of the map correlated with each respective unit of RF data.