System for determining the location of entrances and areas of interest

• US 9,541,404 B2
• Filed: 11/20/2014
• Issued: 01/10/2017
• Est. Priority Date: 08/29/2014
• Status: Active Grant

• Current Assignee: Samsung Electronics Co. Ltd.
• Original Assignee: Samsung Electronics Co. Ltd.
• Inventors: Sidhu, Shalinder S., Yang, Jun, Jiang, Yifei, Mori, Koichi
• Primary Examiner(s): To, Tuan C.
• Application Number:
  US14/549,054
• Publication Number:
  US 20160061607A1
• Time in Patent Office: 782 Days
• US Class Current: 1/1
• CPC Class Codes: G01C 21/206 specially adapted for indoor navigation
• CPC Class Codes: G01C 21/383 Indoor data
• CPC Class Codes: G01C 21/3844 Data obtained from position sensors only, e.g. from inertial navigation
• CPC Class Codes: G01S 19/03 Cooperating elements; Interaction or communication between different cooperating elements or between cooperating elements and receivers
• CPC Class Codes: G01S 5/015 between indoor and outdoor environments
• CPC Class Codes: H04W 64/00 Locating users or terminals or network equipment for network management purposes, e.g. mobility management

Abstract

In one aspect, GPS data, ambient signal data, radio frequency data and/or other types of data are used to determine the location of an entrance to an area or a building. In another aspect, sequential trajectory data is collected and the data is analyzed and/or processed to determine the location of an area of interest.

Claims

1. A method for determining a location of a first area, the method comprising:

obtaining sequential trajectory data that forms one or more clusters, wherein the sequential trajectory data is collected by one or more sensors of a computing system;

filtering the one or more clusters based on motion or speed associated with the sequential trajectory data; and

determining, by a communication system comprising the computing system, a location of a first area based at least in part on the remaining, unfiltered one or more clusters.

2. The method of claim 1 wherein:

the sequential trajectory data is obtained using at least one of pedestrian dead reckoning (PDR) and GPS by the computing system; and

the first area is at least one of an indoor room, a landmark, a store and an outdoor area.

3. The method of claim 1 wherein:

the sequential trajectory data indicates a movement of the computing system over time; and

the sequential trajectory data forms a trace made of a plurality of points, each point being associated with a time and a position of the computing system.

4. The method of claim 1 further comprising:

forming the plurality of clusters from the sequential trajectory data based on distance and duration.

5. The method of claim 4 wherein:

the sequential trajectory data indicates a plurality of points, each point representing a particular location of the computing system at a particular time; and

the method further comprising;

forming the plurality of clusters from some but not all of the points, wherein each cluster indicates that movement of the computing system did not extend beyond a specified radius during a specified period of time; and

not clustering a portion of the sequential trajectory data, wherein the unclustered portion indicates that in that portion movement of the computing system did extend beyond the specified radius during the specified period of time.

6. The method of claim 1, wherein the computing system comprises a sensor unit, the method further comprising:

obtaining accelerometer data from the sensor unit that indicates an amount of motion associated with one of the clusters;

determining whether the amount of motion exceeds a specified threshold; and

when it is determined that the amount of motion exceeds the threshold, filtering out the one of the clusters.

7. The method of claim 1 further comprising:

analyzing timestamps and positions associated with points of a trace in one of the clusters to determine a speed associated with the one of the clusters;

determining whether the speed exceeds a specified threshold; and

when it is determined that the speed exceeds the threshold, filtering out the one of the clusters.

8. The method of claim 1 wherein:

the sequential trajectory data is obtained at a server of the communication system from a plurality of devices of the communication system, the sequential trajectory data forming a plurality of crowdsourced traces and a plurality of clusters; and

the filtering and determining operations are performed by the server.

9. The method of claim 1 wherein there is a second area and the first area is within the second area, the method further comprising:

collecting GPS data;

collecting ambient signal data; and

determining a location of an entrance to the second area based on a combination of the GPS data and the ambient signal data.

10. The method of claim 9 wherein the first area is an indoor room and the second area is a building that includes the indoor room.

11. The method of claim 9 wherein the ambient signal data indicates at least one of (1) a change in a radiofrequency (RF) signal, (2) a change in ambient light, (3) a change in sound, (4) a temperature change;

(5) a magnetic field change;

(6) a change detected images; and

(7) a change in the number of RF signal transmitting devices that the computing system receives RF signals from.

12. The method of claim 9 wherein the determination of the location of the entrance to the second area is based on a pattern found in the GPS data and in the collected RF data wherein the pattern indicates an increase in RF signal quality and a decrease in GPS signal accuracy.

13. The method of claim 9 further comprising:

receiving the GPS data and ambient signal data at a server of the communication system from the computing system, wherein the determination step is performed by the server.

14. The method of claim 9 further comprising:

obtaining a plurality of candidate first area locations from a plurality of devices of the communication system;

selecting a subset of the candidate first area locations based at least in part on a trajectory distance between each candidate first area location and the determined entrance to the second area; and

estimating a location of the first area based at least in part on the selected subset of the clusters.

15. The method of claim 14 wherein:

the determination of the location of the first area is performed by one of the plurality of devices of the communication system;

the determined location of the first area is one of the candidate first area locations; and

the method further comprises receiving the determined location of the first area at a server of the communication system from the one of the devices of the communication system.

16. The method of claim 14 further comprising:

assigning weights to each of the selected subset of candidate first area locations wherein the weights are calculated based on a density of the sequential trajectory data at a region around each candidate first area location wherein the estimation of the location of the first area is based at least in part on the assigned weights.

17. A computer readable storage medium, wherein the computer readable storage medium that includes executable computer code embodied in a tangible form operable to determine a location of an area of interest wherein the computer readable storage medium includes:

executable computer code executable by at least one processor and operable to obtain sequential trajectory data of a computing system that forms one or more clusters;

executable computer code executable by at least one processor and operable to filter the one or more clusters based on motion or speed associated with the sequential trajectory data of the computing system; and

executable computer code executable by at least one processor and operable to determine a location of a first area based at least in part on the remaining, unfiltered one or more clusters.

18. The computer readable medium of claim 17 wherein there is a second area and the first area is within the second area, the computer readable medium further comprising:

executable computer code executable by the at least one processor and operable to collect GPS data;

executable computer code executable by the at least one processor and operable to collect ambient signal data; and

executable computer code executable by the at least one processor and operable to determine a location of an entrance to the second area based on a combination of the GPS data and the ambient signal data;

executable computer code executable by the at least one processor and operable to form the one or more clusters from the sequential trajectory data based on distance and duration; and

executable computer code executable by the at least one processor and operable to determine a location of the first area based on one of the remaining, unfiltered one or more clusters.

19. A system for determining a location of an entrance to a second area and a location of a first area that is within the second area, the system comprising:

a device comprising;

at least one processor;

at least one memory including a computer readable storage medium that includes device computer code stored in a tangible form wherein the device computer code, when executed by the at least one processor of the device, causes the device to;

collect GPS data;

collect ambient signal data; and

determine the location of the entrance to the second area based on a combination of the GPS data and the ambient signal data;

collect sequential trajectory data that forms a trace extending from the entrance to the second area;

cluster the collected sequential trajectory data based on distance and duration, thereby forming one or more clusters from the collected sequential trajectory data;

filter the one or more clusters based on speed and motion; and

determine a candidate location of a first area based on one of the one or more remaining, unfiltered clusters; and

a server comprising;

at least one memory including a computer readable storage medium that includes server computer code stored in a tangible form wherein the server computer code, when executed by the at least one processor of the server, causes the server to;

obtain a plurality of candidate first area locations from a plurality of devices;

receive the candidate location of the first area determined by the device, which is one of the plurality of candidate first area locations;

select a subset of the candidate first area locations based at least in part on a trajectory distance between each candidate first area location and the determined location of the entrance to the second area; and

estimate the location of the first area based at least in part on the selected subset.

20. The system of claim 19 wherein:

the server computer code, when executed by the at least one processor of the server, further causes the server to transmit the estimated location of the first area to the device; and

the device computer code, when executed by the at least one processor of the device, further causes the device to;

receive the estimated location of the first area from the server; and

display an indication of the estimated location of the first area on the device.