Landmark location determination

• US 10,415,978 B2
• Filed: 11/20/2015
• Issued: 09/17/2019
• Est. Priority Date: 11/20/2015
• Status: Active Grant

• Current Assignee: Samsung Electronics Co. Ltd.
• Original Assignee: Samsung Electronics Co. Ltd.
• Inventors: Yang, Jun, Zheng, Dongfang, Singh, Jasvinder, Mori, Koichi
• Primary Examiner(s): Olszewski, John
• Assistant Examiner(s): Foster, Gerrad A
• Application Number:
  US14/948,188
• Publication Number:
  US 20170146349A1
• Time in Patent Office: 1,397 Days
• Field of Search: None
• CPC Class Codes: G01C 21/005 with correlation of navigation data from several sources, e.g. map or contour matching G01C21/30 takes precedence
• CPC Class Codes: G01C 21/14 by recording the course traversed by the object G01C21/16 takes precedence
• CPC Class Codes: G01C 21/206 specially adapted for indoor navigation
• CPC Class Codes: G01C 21/30 Map- or contour-matching
• CPC Class Codes: H04W 4/026 using orientation information, e.g. compass
• CPC Class Codes: H04W 4/027 using movement velocity, acceleration information
• CPC Class Codes: H04W 4/33 for indoor environments, e.g. buildings

Abstract

In one aspect, a method for determining a location of a landmark using a map is described. Trajectory data is obtained indicating movement of a device at an area. The trajectory data indicates a landmark. A map is obtained of the area. At least a portion of the trajectory data is compared and/or matched with at least a portion of the map. Based on the matching, a location of the landmark is determined in the map. Various implementations involve system, devices and software relating to the above method.

Claims

1. A method performed by a server, comprising:

obtaining a first trajectory data indicating movement of a device at an area, the first trajectory data indicating a first landmark;

selecting a portion of the first trajectory data, the portion being less than an entirety of the first trajectory data;

selecting one or more segments from the portion of the first trajectory data, wherein the one or more segments from the portion of the first trajectory data are adjacent to the first landmark;

obtaining a map of the area, the map indicating a pathway layout defined by the one or more segments from the portion of the first trajectory data;

matching at least the portion of the first trajectory data with at least a portion of the pathway layout; and

based on the matching, determining a location of the first landmark in the map.

2. The method performed by the server of claim 1, further comprising:

obtaining a second trajectory data indicating a second landmark;

comparing the first and second landmarks based on distance and ambient signal fingerprint data of the first trajectory data and the second trajectory data respectively; and

based on the comparison, adjusting the location of the first landmark in the map.

3. The method performed by the server of claim 1, wherein a landmark is one of a point on the map and an area on the map.

4. The method performed by the server of claim 1, wherein the first landmark is one of a door, stairs, a shop and an elevator.

5. The method performed by the server of claim 1, further comprising:

identifying a portion of the first trajectory data indicating that the device changed direction beyond a predefined frequency threshold or moved at a speed that fell below a predefined speed threshold; and

determining that the identified portion of the first trajectory data corresponds to the first landmark.

6. The method performed by the server of claim 1, wherein the map is a first map and the first map does not indicate any landmarks prior to the matching and wherein after the matching the first landmark is added to the first map to form a second map.

7. The method performed by the server of claim 1, wherein the pathway layout is a part of the map that indicates locations of paths and intersections and the pathway layout is not adjusted based on the matching.

8. The method performed by the server of claim 1, further comprising:

matching the one or more segments with at least a portion of the pathway layout.

9. The method performed by the server of claim 1, wherein:

the first trajectory data includes a first sequence of points that extends from a start point of the first trajectory data to a start point of the first landmark and a second sequence of points that extends from an end point of the first trajectory data to an end point of the first landmark; and

matching the first sequence of points and second sequence of points with at least a portion of the pathway layout.

10. The method performed by the server of claim 1, wherein obtaining the map of the area further comprises:

obtaining a multiplicity of sets of trajectory data from one or more devices, each set of trajectory data indicating movement of a device at the area;

determining, for each set of trajectory data, whether the set of trajectory data includes a landmark;

based on the determination, selecting one or more of the sets of trajectory data that do not include the landmark; and

using the selected one or more sets of trajectory data to help form the map.

11. The method performed by the server of claim 1, wherein the first trajectory data includes a plurality of points, each point being associated with a timestamp and ambient signal fingerprint data.

12. The method performed by the server of claim 1, wherein the first landmark is a room.

13. A non-transitory computer readable medium including a plurality of instructions that, when executed by a processor, are configured to cause the processor to:

obtain a first trajectory data indicating movement of a device at an area, the first trajectory data indicating a first landmark;

select a portion of the first trajectory data, the portion being less than an entirety of the first trajectory data;

select one or more segments from the portion of the first trajectory data, wherein the one or more segments from the portion of the first trajectory data are adjacent to the first landmark;

obtain a map of the area, the map indicating a pathway layout defined by the one or more segments from the portion of the first trajectory data;

match at least the portion of the first trajectory data with at least a portion of the pathway layout; and

determine, based on the matching, a location of the first landmark in the map without changing the pathway layout.

14. The non-transitory computer readable medium of claim 13, wherein the plurality of instructions is further configured to cause the processor to:

obtain a second trajectory data indicating a second landmark;

compare the first and second landmarks based on distance and ambient signal fingerprint data of the first trajectory data and the second trajectory data respectively; and

adjust, based on the comparison, the location of the first landmark in the map.

15. The non-transitory computer readable medium of claim 13, wherein the plurality of instructions is further configured to cause the processor to:

identify a portion of the first trajectory data indicating that the device changed direction beyond a predefined frequency or moved at a speed that fell below a predefined speed; and

determine that the identified portion of the first trajectory data indicates the first landmark.

16. The non-transitory computer readable medium of claim 13, wherein the plurality of instructions is further configured to cause the processor to:

match the one or more segments with at least a portion of the pathway layout.

17. The non-transitory computer readable medium of claim 13, wherein the first trajectory data includes a first sequence of points that extends from a start point of the first trajectory data to a start point of the first landmark and a second sequence of points that extends from an end point of the first trajectory data to an end point of the first landmark wherein the plurality of instructions of the non-transitory computer readable medium is further configured to cause the processor to match the first sequence of points and second sequence of points with at least a portion of the pathway layout.

18. A device comprising:

at least one processor; and

at least one memory circuitry, the at least one memory circuitry including a non-transitory computer readable medium, including a plurality of instructions that, when executed by the at least one processor, causes the device to;

obtain a first trajectory data indicating movement of the device at an area, the first trajectory data indicating a first landmark,

select a portion of the first trajectory data, the portion being less than an entirety of the first trajectory data,

the portion of the first trajectory data, wherein one or more segments from the portion of the first trajectory data are adjacent to the first landmark,

obtain a map of the area, the map indicating a pathway layout defined by the one or more-segments from the portion of the first trajectory data,

match at least the portion of the first trajectory data with at least a portion of the pathway layout, and

determine, based on the matching, a location of the first landmark in the map without changing the pathway layout.

19. The device of claim 18, wherein the plurality of instructions is further configured to cause the at least one processor to:

obtain a second trajectory data indicating a second landmark;

compare the first and second landmarks based on distance and ambient signal fingerprint data of the first trajectory data and the second trajectory data respectively; and

adjust, based on the comparison, the location of the first landmark in the map.

20. The device of claim 18, wherein the plurality of instructions is further configured to cause the at least one processor to:

match the one or more segments with at least a portion of the pathway layout.

21. The device of claim 18, wherein:

the first trajectory data includes a first sequence of points that extends from a start point of the first trajectory data to a start point of the first landmark and a second sequence of points that extends from an end point of the first trajectory data to an end point of the first landmark wherein the plurality of instructions is further configured to cause the at least one processor to match the first sequence of points and second sequence of points.