Using image content to facilitate navigation in panoramic image data

• US 8,963,915 B2
• Filed: 09/06/2012
• Issued: 02/24/2015
• 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, Vincent, Luc
• Primary Examiner(s): Nguyen, Kimbinh T
• Application Number:
  US13/605,635
• Publication Number:
  US 20120327184A1
• Time in Patent Office: 901 Days
• Field of Search: 345/419, 345/427, 348/36
• US Class Current: 345/419
• 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 for navigating in panoramic image data, comprising:

determining, by one or more computing devices, an intersection of a ray, extended from a camera viewport through a position of a first panoramic image, and a three-dimensional virtual model, wherein the position is selected by a user;

determining, by one or more computing devices and based on the intersection, a second panoramic image such that the second panoramic image is located according to the intersection of the ray and the three-dimensional virtual model;

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

orienting, by one or more computing devices, the retrieved second panoramic image to face the intersection; and

displaying, by one or more computing devices, the oriented second panoramic image to the user to navigate from the first panoramic image to the 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 retrieving comprises retrieving the second panoramic image within a selected distance of the intersection.

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

5. 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.

6. The method of claim 5, wherein the 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.

7. The method of claim 6, wherein the identifying comprises using a Speeded Up Robust Features (SURF) algorithm.

8. The method of claim 7, wherein the determining a 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.

9. The method of claim 8, wherein the comparing comprises comparing a feature similarity ratio of the approximate nearest neighbor and the approximate second-nearest neighbor to a threshold between 0.5 and 0.95, inclusive.

10. The method of claim 6, wherein the determining a 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.

11. The method of claim 6, wherein the determining a facade plane comprises using a best fit or adaptive optimization algorithm.

12. A system for navigating in panoramic image data using a three-dimensional virtual model, wherein the three-dimensional virtual model was created from a plurality of two-dimensional images, comprising:

a computing device; and

server, implemented by one or more computing devices, that includes a navigation controller that determines an intersection of a ray, extended from a camera viewport through a position of a first panoramic image, and the three-dimensional virtual model, wherein the three-dimensional virtual model comprises a plurality of facade planes and the position is selected by a user, and determines a second panoramic image such that the second panoramic image is located according to the intersection of the ray and the three-dimensional virtual model, retrieves the second panoramic image and orients the retrieved second panoramic image to face the intersection, and provides the retrieved and oriented second panoramic image for display to the user,

whereby the navigation controller enables navigation from the first to the second panorama.

13. The system of claim 12, wherein the navigation controller comprises a switching lanes controller that determines a location of the camera viewport of the second panoramic image in a first lane different from a second lane, wherein the location of the camera viewport of the second panoramic image is in the second lane.

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

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

16. The system of claim 12, further comprising:

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

17. 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.

18. The system of claim 17, wherein the feature extractor uses a Speeded Up Robust Features (SURF) algorithm.

19. The system of claim 17, 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.

20. The system of claim 17, 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.