Computing transitions between captured driving runs

• US 8,581,900 B2
• Filed: 06/10/2009
• Issued: 11/12/2013
• Est. Priority Date: 06/10/2009
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Chen, Billy P., Cohen, Michael F., Ofek, Eyal, Aguera y Arcas, Blaise H.
• Primary Examiner(s): Nguyen, Kimbinh T
• Application Number:
  US12/482,238
• Publication Number:
  US 20100315411A1
• Time in Patent Office: 1,616 Days
• Field of Search: 345/419, 345/420, 345/440, 345/473
• US Class Current: 345/419
• CPC Class Codes: G06T 15/205 Image-based rendering
• CPC Class Codes: G06T 17/05 Geographic models

Abstract

Various embodiments provide a global approach for computing transitions between captured runs through an intersection. In accordance with one or more embodiments, a transition algorithm receives as input various runs that have been captured through an intersection and an input path through the intersection. The transition algorithm processes its inputs and provides, as an output, a set of points and data such as a direction associated with each of the points. The set of points includes points from different captured runs. The output set of points and associated data indicate which images to obtain from a database and which field of view to create a simulated turn for the user.

Claims

1. A computer-implemented method comprising:

receiving, with a computing device, an input path comprising a computed path for navigating along one or more streets;

utilizing a transition algorithm to compute an output path associated with the input path, wherein the transition algorithm;

receives, as input, at least two different captured driving runs, the at least two different captured driving runs being stored in memory, each captured run including a plurality of nodes that represent capture events that were acquired at the plurality of nodes along and during the at least two different captured driving runs, and at least some adjacent nodes on each captured run are connected by weighted edges, and a description of an intersection associated with the input path and the driving runs;

computes the output path as a function of cost associated with a transition within the intersection between said at least two captured driving runs;

obtaining images associated with a selected output path; and

causing obtained images to be displayed for a user.

2. The computer-implemented method of claim 1, wherein each capture event represents a location where a 360°

panoramic view was captured.

3. The computer-implemented method of claim 1, wherein the transition algorithm is configured to compute the output path by considering costs associated with transition edges that connect nodes on different captured runs.

4. The computer-implemented method of claim 3, wherein the transition edges are defined between nodes within the intersection.

5. The computer-implemented method of claim 1, wherein the description of the intersection comprises a radius that describes an intersection size.

6. A computer-implemented method comprising:

receiving, with a computing device, a user-specified path comprising a computed path for navigating along one or more streets;

computing costs associated with making a transition between different captured driving runs, the different captured driving runs being stored in memory, each captured run including a plurality of nodes that represent capture events that were acquired at the plurality of nodes along and during the different captured driving runs, and at least some adjacent nodes on each captured run are connected by weighted edges, associated with the user-specified path;

selecting an output path having a lowest cost;

obtaining images associated with a selected output path; and

causing obtained images to be displayed for a user.

7. The computer-implemented method of claim 6, wherein said computing costs comprises computing a distance cost and a deviation cost for different transitions between the captured runs.

8. The computer-implemented method of claim 7, wherein:

said distance cost is computed by computing a distance between nodes on the different captured runs; and

said deviation cost is computed by computing an angle associated with individual transitions between nodes on the different captured runs.

9. The computer-implemented method of claim 8, wherein said distance comprises a Euclidean distance between the nodes on the different captured runs.

10. The computer-implemented method of claim 6, wherein said obtaining images comprises obtaining one or more 360°

panoramic images.

11. One or more computer-readable hardware storage media embodying computer-executable instructions which, when executed, implement a method comprising:

receiving an input path comprising a computed path for navigating along one or more streets;

building a weighted, edge-directed graph associated with the input path, the weighted, edge-directed graph comprising multiple captured driving runs, the multiple captured driving runs being stored in memory each of which includes multiple nodes that represent capture events that were acquired at the multiple nodes along and during the multiple captured driving runs;

computing transition costs associated with the weighted, edge-directed graph;

selecting an output path having a lowest computed transition cost;

obtaining 360°

panoramic view images associated with the output path; and

causing the 360°

panoramic view images to be displayed.

12. The one or more computer-readable hardware storage media of claim 11, wherein said computing transition costs comprises computing a distance cost associated with transition edges within the weighted, edge-directed graph.

13. The one or more computer-readable hardware storage media of claim 12, wherein at least some of the nodes occurring within an intersection;

and, wherein computing a distance cost comprises computing a Euclidian distance between nodes on different captured runs within the intersection.

14. The one or more computer-readable hardware storage media of claim 11, wherein said computing transition costs comprises computing a deviation cost associated with transition edges within the weighted, edge-directed graph.

15. The one or more computer-readable hardware storage media of claim 14, wherein the weighted, edge-directed graph comprises multiple captured runs each of which includes multiple nodes, at least some of the nodes occurring within an intersection;

and, wherein computing a deviation cost comprises computing an angle associated with each transition edge.

16. The one or more computer-readable hardware storage media of claim 11, wherein said computing transition costs comprises computing a distance cost and a deviation cost associated with transition edges within the weighted, edge-directed graph.

17. The one or more computer-readable hardware storage media of claim 16, wherein the weighted, edge-directed graph comprises multiple captured runs each of which includes multiple nodes, at least some of the nodes occurring within an intersection;

wherein computing a distance cost comprises computing a Euclidian distance between nodes on different captured runs within the intersection; and

, computing a deviation cost comprises computing an angle associated with each transition edge.

18. The one or more computer-readable hardware storage media of claim 17, wherein the obtaining 360°

panoramic view images comprises computing a heading for each 360°

panoramic view image along the output path.