System and method for generating a map from activity data

• US 9,836,672 B2
• Filed: 03/16/2015
• Issued: 12/05/2017
• Est. Priority Date: 03/14/2014
• Status: Active Grant

• Current Assignee: Under Armour Incorporated
• Original Assignee: Under Armour Incorporated
• Inventors: Eastman, Kyler Maxwell
• Primary Examiner(s): Thompson, James A
• Application Number:
  US14/658,935
• Publication Number:
  US 20150262397A1
• Time in Patent Office: 995 Days
• Field of Search: None
• CPC Class Codes: G01C 21/3811 Point data, e.g. Point of Interest [POI]
• CPC Class Codes: G01C 21/3841 Data obtained from two or more sources, e.g. probe vehicles
• CPC Class Codes: G06F 18/23 Clustering techniques
• CPC Class Codes: G06F 18/23213 with fixed number of clusters, e.g. K-means clustering
• CPC Class Codes: G06F 18/2323 based on graph theory, e.g. minimum spanning trees [MST] or graph cuts
• CPC Class Codes: G06F 18/29 Graphical models, e.g. Bayesian networks

Abstract

A method for generating a graph includes receiving GPS data points for a plurality of GPS tracks. Thereafter, points of greater curvature in the GPS tracks are identified. The method further includes determining a plurality of nodes for the graph based on the identified points of greater curvature in the GPS tracks. Additionally, the method includes determining a plurality of connections between the nodes, the plurality of nodes and the plurality of connections defining the graph.

Claims

1. A method for generating a graph, the method comprising:

receiving GPS data points for a plurality of GPS tracks;

identifying points of greater curvature in the GPS tracks, wherein identifying the points of greater curvature includes simplifying the GPS tracks to provide GPS data for simplified GPS tracks;

clustering the identified points of greater curvature;

determining a plurality of nodes for the graph based on the clustered identified points of greater curvature in the GPS tracks;

determining a plurality of connections between the nodes, the nodes and the connections defining the graph; and

defining at least one primary connection and at least one secondary connection between a pair of nodes, wherein defining the at least one secondary connection between the pair of nodes comprises interpolating a same number of GPS points between the pair of nodes and clustering the GPS points in order to group the GPS points into distinct paths.

2. The method of claim 1 further comprising simplifying the GPS tracks by reducing the GPS data points for each of the GPS tracks.

3. The method of claim 1 wherein determining the connections between the nodes includes determining a sequence of closest nodes based on the received GPS data points for each of the GPS tracks.

4. The method of claim 3 wherein determining the connections between the nodes further includes removing redundant nodes from the sequence of closest nodes.

5. The method of claim 1 wherein the GPS data points for the GPS tracks are received over a network from a plurality of GPS-enabled devices during fitness activities.

6. The method of claim 1 wherein defining the at least one secondary connection between the pair of nodes comprises defining a plurality of intermediate nodes between the pair of nodes.

7. The method of claim 1 further comprising receiving additional GPS data points for an additional GPS track related to the defined graph, determining that at least one additional connection exists between the nodes of the graph based upon the additional GPS data points, and updating the graph to include the at least one additional connection.

8. A non-transitory computer readable medium containing instructions for generating a graph by:

receiving GPS data points for a plurality of GPS tracks;

identifying points of greater curvature in the GPS tracks;

clustering the identified points of greater curvature;

determining a plurality of nodes for the graph based on the clustered identified points of greater curvature in the GPS tracks;

determining a plurality of connections between the nodes, the nodes and the connections defining the graph; and

generating a graph by defining at least one primary connection and at least one secondary connection between a pair of nodes, wherein defining the at least one secondary connection between the pair of nodes comprises interpolating a same number of GPS points between the pair of nodes and clustering the GPS points in order to group the GPS points into distinct paths.

9. The computer readable medium of claim 8 further containing instructions for generating a graph by simplifying the GPS tracks by reducing the GPS data points for each of the GPS tracks.

10. The computer readable medium of claim 9 wherein identifying the points of greater curvature includes simplifying the GPS tracks to produce GPS data for simplified GPS tracks and clustering the GPS data for the simplified GPS tracks to identify the points of greater curvature.

11. The computer readable medium of claim 8 wherein determining the connections between the nodes includes determining a sequence of closest nodes based on the received GPS data points for each of the GPS tracks.

12. The computer readable medium of claim 11 wherein determining the connections between the nodes further includes removing redundant nodes from the sequence of closest nodes.

13. The computer readable medium of claim 8 wherein the GPS data points for the GPS tracks are received over a network from a plurality of GPS-enabled devices.

14. The computer readable medium of claim 8 wherein defining the at least one secondary connection between the pair of nodes comprises defining a plurality of intermediate nodes between the pair of nodes.

15. A method for generating a graph, the method comprising:

receiving GPS data points for a plurality of GPS tracks, the GPS data points for the GPS tracks received from a plurality of GPS-enabled devices during fitness activities;

identifying points of greater curvature for each of the plurality of GPS tracks and simplifying the GPS tracks to the identified points of greater curvature;

clustering the GPS data points identified as the points of greater curvature;

determining a plurality of nodes for the graph based on the clustered GPS data points;

determining a sequence of closest nodes for a plurality of GPS data points for each of the GPS tracks;

reducing the sequence of closest nodes for each of the GPS tracks by removing redundant nodes from the sequence;

determining a plurality of connections between the nodes based on the reduced sequence of closest nodes for each of the GPS tracks; and

defining at least one primary connection and at least one secondary connection between a pair of nodes, wherein defining the at least one secondary connection between the pair of nodes comprises interpolating a same number of GPS points between the pair of nodes and clustering the GPS points in order to group the GPS points into distinct paths.

16. The method of claim 15 wherein defining the at least one secondary connection between the pair of nodes comprises defining a plurality of intermediate nodes between the pair of nodes.