Using image content to facilitate navigation in panoramic image data

• US 8,525,825 B2
• Filed: 02/27/2008
• Issued: 09/03/2013
• Est. Priority Date: 02/27/2008
• Status: Active Grant

• Current Assignee: DigitalOptics Corporation Europe Limited (Adeia, Inc.), 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:
  US12/038,325
• Publication Number:
  US 20090213112A1
• Time in Patent Office: 2,015 Days
• Field of Search: 345/419, 345/427, 345/582, 382/154, 382/284, 382/294, 348/36, 348/47
• 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:

(1) creating a 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 faç

ade planes, the creating comprising;

(a) determining a plurality of pairs of matching features, including a first feature in a first image and a second feature in a second image, such that the first feature matches the second feature, wherein the first and second images are selected from the plurality of two-dimensional images, and

(b) using the plurality of pairs of matching features to create at least a portion of the three-dimensional model;

(2) determining an intersection of a ray, extended from a position on a camera viewport of the first image, and the three-dimensional virtual model created in step (1), wherein the position is selected by a user;

(3) retrieving a panoramic image located according to a location of the intersection determined in step (2);

(4) orienting the panoramic image retrieved in step (3) to face the intersection; and

(5) displaying the oriented panoramic image oriented in step (4) to the user.

2. The method of claim 1, wherein (1) further comprises:

(a) identifying a first plurality of features of the first image and a second plurality of features of the second image;

(b) determining 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, that matches the first feature;

(c) determining a plurality of points corresponding to the plurality of pairs of features; and

(d) determining a facade plane based on the plurality of points;

(e) determining a street plane corresponding to a location of a street; and

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

3. The method of claim 2, wherein (a) comprises using a Speeded Up Robust Features (SURF) algorithm.

4. The method of claim 3, wherein (b) comprises:

(i) determining a spill tree for the first plurality of features;

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

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

5. The method of claim 4, wherein (iii) 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.

6. The method of claim 2, wherein (c) comprises:

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

(ii) 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.

7. The method of claim 2, wherein (d) comprises using a best fit or adaptive optimization algorithm.

8. 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;

a processing pipeline server that creates a three-dimensional virtual model from a plurality of two-dimensional images, wherein the processing pipeline server comprises;

a feature matcher that determines a plurality of pairs of matching features, including a first feature in a first image and a second feature in a second image, such that the first feature matches the second feature, wherein the first and second images are selected from the plurality of two-dimensional images, and

a surface estimator that uses the plurality of pairs of matching features to create at least a portion of the three-dimensional model;

a server, implemented on the computing device, that includes a navigation controller that determines an intersection of a ray, extended from a position on a camera viewport of the first image, and the three-dimensional virtual model created by the processing pipeline server, wherein the three-dimensional virtual model comprises a plurality of facade planes and the position is selected by a user, retrieves a panoramic image located according to a position of the determined intersection and orients the retrieved panoramic image to face the intersection.

9. The system of claim 8, wherein the navigation controller comprises a switching lanes controller that determines a location of the camera viewport of the panoramic image in a first lane different from a second lane, wherein the location of the camera viewport of the 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, wherein the processing pipeline server further comprises:

a feature extractor that identifies a first plurality of features of the first image and a second plurality of features of the second image,

wherein the feature matcher determines a plurality of pairs of matching features, wherein each pair of matching 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; and

a point calculator that determines a plurality of points corresponding to the plurality of pairs of matching features, wherein the surface estimator creates the three-dimensional virtual model based on the plurality of points.

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

14. The system of claim 12, 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 14, wherein the threshold is between 0.5 and 0.95 inclusive.

16. The system of claim 12, 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 a first image through the first feature from the pair and a second ray extending from a second camera viewpoint of 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.