Using image content to facilitate navigation in panoramic image data

• US 9,632,659 B2
• Filed: 12/29/2014
• Issued: 04/25/2017
• Est. Priority Date: 02/27/2008
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Zhu, Jiajun, Filip, Daniel Joseph, Vincent, Luc
• Primary Examiner(s): Nguyen, Kimbinh T
• Application Number:
  US14/584,183
• Publication Number:
  US 20150116326A1
• Time in Patent Office: 848 Days
• Field of Search: 345419, 345426
• CPC Class Codes: G06F 3/04815 Interaction with a metaphor-based environment or interaction object displayed as three-dimensional, e.g. changing the user viewpoint with respect to the environment or object
• CPC Class Codes: G06T 15/06 Ray-tracing
• CPC Class Codes: G06T 17/00 Three dimensional [3D] modelling, e.g. data description of 3D objects
• CPC Class Codes: G06T 19/00 Manipulating 3D models or images for computer graphics
• CPC Class Codes: G06T 19/003 Navigation within 3D models or images
• CPC Class Codes: G06T 2200/32 involving image mosaicing
• CPC Class Codes: G06T 3/4038 Image mosaicing, e.g. composing plane images from plane sub-images

Abstract

The present invention relates to using image content to facilitate navigation in panoramic image data. In an embodiment, a computer-implemented method for navigating in panoramic image data includes: (1) determining an intersection of a ray and a virtual model, wherein the ray extends from a camera viewport of an image and the virtual model comprises a plurality of facade planes; (2) retrieving a panoramic image; (3) orienting the panoramic image to the intersection; and (4) displaying the oriented panoramic image.

Claims

1. A computer implemented method, comprising:

determining, using one or more computing devices, an intersection of a ray and a three-dimensional virtual model, wherein the ray extends from a camera viewpoint through a position of a first panoramic image and to the three-dimensional virtual model, the camera viewpoint being a focal point of a camera used to capture the first panoramic image;

determining, using the one or more computing devices, a second panoramic image that is within a pre-defined distance of the intersection;

retrieving, using the one or more computing devices, the second panoramic image;

orienting, using the one or more computing devices, the retrieved second panoramic image to a point on the three-dimensional virtual model; and

displaying, using the one or more computing devices, the oriented second panoramic image.

2. The method of claim 1, wherein the retrieving comprises retrieving the second panoramic image having a camera viewpoint with a user-selected location.

3. The method of claim 1, wherein the second panoramic image comprises a photographic image taken from a street level.

4. The method of claim 1, further comprising:

creating the three-dimensional virtual model, by one or more computer systems, from contents of a plurality of two-dimensional images, the three-dimensional virtual model including a plurality of facade planes.

5. The method of claim 4, wherein creating comprises:

identifying a first plurality of features of a first image and a second plurality of features of a second image;

determining a plurality of pairs of features, wherein each pair of the plurality of pairs of features includes a first feature from the first plurality of features and a second feature from the second plurality of features that matches the first feature;

determining a plurality of points corresponding to the plurality of pairs of features;

determining a facade plane based on the plurality of points;

determining a street plane corresponding to a location of a street; and

creating the three-dimensional virtual model corresponding to the facade plane and the street plane.

6. The method of claim 5, wherein determining the plurality of pairs of features comprises:

determining a spill tree for the first plurality of features;

searching the spill tree for an approximate nearest neighbor and an approximate second nearest neighbor of each feature in the second image; and

comparing a feature similarity ratio of the approximate nearest neighbor and the approximate second-nearest neighbor to a threshold.

7. The method of claim 5, wherein determining the plurality of points comprises:

determining, for each pair of features of the plurality of pairs of features, a first ray extending from a first camera viewpoint of a first panoramic image through the first feature from the pair and a second ray extending from a second camera viewpoint of the second panoramic image through the second feature from the pair; and

determining, for each pair of features of the plurality of pairs of features, a point corresponding to an intersection of the first ray and the second ray.

8. A system, comprising:

a memory; and

one or more processors, operatively coupled to the memory, configured to execute a navigation controller that;

determines an intersection of a ray and a three-dimensional virtual model, wherein the ray extends from a camera viewpoint through a position of a first panoramic image and to the three-dimensional virtual model, the camera viewpoint being a focal point of a camera used to capture the first panoramic image,

determines a second panoramic image that is within a pre-defined distance of the intersection of the ray and the three-dimensional virtual model,

retrieves the second panoramic image and orients the retrieved second panoramic image to a point on the three-dimensional model, and

provides the oriented second panoramic image for display.

9. The system of claim 8, wherein the navigation controller includes a switching lanes controller that determines a location of the camera viewpoint of the second panoramic image in a first lane different from a second lane, wherein the location of the camera viewpoint of the second panoramic image is in the second lane.

10. The system of claim 8, wherein the navigation controller comprises a click-and-go controller that retrieves a panoramic image closest to the intersection.

11. The system of claim 8, wherein the navigation controller comprises a walk around controller that retrieves a panoramic image closer to the intersection than a location of the image.

12. The system of claim 8, further comprising:

a processing pipeline server that creates a three-dimensional virtual model from a plurality of two-dimensional images.

13. The system of claim 12, wherein the processing pipeline server comprises:

a feature extractor that identifies a first plurality of features of a first panoramic image and a second plurality of features of a second panoramic image;

a feature matcher that determines a plurality of pairs of features, wherein each pair of features includes a first feature from the first plurality of features and a second feature from the second plurality of features, and wherein the first feature matches the second feature;

a point calculator that determines a plurality of points corresponding to the plurality of pairs of features; and

a surface estimator that creates the three-dimensional virtual model based on the plurality of points.

14. The system of claim 13, wherein the feature matcher determines a spill tree for the first plurality of features, searches the spill tree for an approximate nearest neighbor and an approximate second nearest neighbor of each feature in the second image, and determines whether a feature similarity ratio of the approximate nearest neighbor and the approximate second-nearest neighbor is below a threshold.

15. The system of claim 13, wherein for each pair of features in the plurality of pairs of features, the point calculator determines a first ray extending from a first camera viewpoint of the first panoramic image through the first feature from the pair and a second ray extending from a second camera viewpoint of the second panoramic image through the second feature from the pair and determines a point from the plurality of points as an intersection between the first ray and the second ray.

16. A non-transitory computer-readable medium storing computer program instructions, which, when executed by one or more processors, cause the processor to perform a method comprising:

determining an intersection of a ray and a three-dimensional virtual model, wherein the ray extends from a camera viewpoint through a position of a first panoramic image and to the three-dimensional virtual model, the camera viewpoint being a focal point of a camera used to capture the first panoramic image;

determining, based on the intersection, a second panoramic image that is within a pre-defined distance of the intersection;

retrieving the second panoramic image;

orienting the retrieved second panoramic image to a point on the three-dimensional virtual model; and

displaying the oriented second panoramic image.

17. The non-transitory computer-readable medium of claim 16, wherein the further comprises:

creating the three-dimensional virtual model, by one or more computer systems, from contents of a plurality of two-dimensional images, the three-dimensional virtual model including a plurality of facade planes.

18. The non-transitory computer-readable medium of claim 17, wherein creating comprises:

identifying a first plurality of features of a first image and a second plurality of features of a second image;

determining a plurality of pairs of features, wherein each pair of the plurality of pairs of features includes a first feature from the first plurality of features and a second feature from the second plurality of features that matches the first feature;

determining a plurality of points corresponding to the plurality of pairs of features;

determining a facade plane based on the plurality of points;

determining a street plane corresponding to a location of a street; and

creating the three-dimensional virtual model corresponding to the facade plane and the street plane.

19. The non-transitory computer readable medium of claim 18, wherein determining the plurality of pairs of features comprises:

determining a spill tree for the first plurality of features;

searching the spill tree for an approximate nearest neighbor and an approximate second nearest neighbor of each feature in the second image; and

comparing a feature similarity ratio of the approximate nearest neighbor and the approximate second-nearest neighbor to a threshold.

20. The non-transitory computer-readable medium of claim 18, wherein determining the plurality of points comprises:

determining, for each pair of features of the plurality of pairs of features, a first ray extending from a first camera viewpoint of a first panoramic image through the first feature from the pair and a second ray extending from a second camera viewpoint of the second panoramic image through the second feature from the pair; and

determining, for each pair of features of the plurality of pairs of features, a point corresponding to an intersection of the first ray and the second ray.