Method and system for navigating in panoramic images using voxel maps

• US 9,754,413 B1
• Filed: 03/26/2015
• Issued: 09/05/2017
• Est. Priority Date: 03/26/2015
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Gray, Christopher
• Primary Examiner(s): Hoang, Peter
• Application Number:
  US14/669,603
• Time in Patent Office: 894 Days
• CPC Class Codes: G06T 17/005 Tree description, e.g. octree, quadtree
• CPC Class Codes: G06T 17/05 Geographic models
• CPC Class Codes: G06T 19/00 Manipulating 3D models or images for computer graphics
• CPC Class Codes: H04N 23/698 for achieving an enlarged field of view, e.g. panoramic image capture

Abstract

The present disclosure describes a system and method that includes receiving a user selection of a portion of a first image. In response to the user-selection, a first identifier of three-dimensional space associated with the user-selection is determined and a second image is selected based on a portion of the second image being associated with the first identifier. The second image may be provided to the user to be displayed. The present disclosure also provides for mapping a portion of a first image to an identifier of three-dimensional space.

Claims

1. A system comprising:

one or more computing devices,

memory storing data and instructions, the data comprising;

an octree associated with a three-dimensional model of a geographic space, the octree having a lower level having a first set of cubes and a higher level having a second set of cubes, the first set of cubes being larger in number than the second set of cubes, and the second set of cubes being larger in size than the first set of cubes, wherein a given cube of the first set of cubes has a spatial identifier that identifies the given cube and another cube in the second set of cubes that contains the given cube, and

a plurality of images, wherein at least a portion of each image shows an object, and wherein such portion is associated with a first spatial identifier of a first cube in the first set of cubes that contains at least a portion of the surface of such object;

the one or more computing devices, configured to access to the memory, programmed to;

receive a user selection of a first portion of a first image of the plurality of images;

determine that the first portion is associated with the first spatial identifier of the first cube;

determine that a second portion of a second image from the plurality of images is associated with the first spatial identifier; and

providing the second image for display to the user.

2. The system of claim 1, wherein the user selection includes clicking on the first portion of the first image.

3. The system of claim 1, wherein the first portion of the first image is a pixel of the first image.

4. The system of claim 1, wherein the one or more computing devices is programmed to:

create a scored listing of the plurality of images associated with the first spatial identifier.

5. The system of claim 4, wherein the one or more computing devices is programmed to:

select the second image from the scored listing of the plurality of images for display.

6. The system of claim 1, wherein the octree has a root cube that encompasses the Earth, the root cube having a side length on the order of 2²³ meters.

7. The system of claim 1, wherein the first set of cubes have a side length of about ⅛

meter.

8. A method comprising:

receiving, by one or more computing devices, a user selection of a portion of a first image;

determining, by the one or more computing devices, a first spatial identifier associated with the user-selected portion of the first image, the first spatial identifier identifying a first cube in a lower level and a second cube in a higher level of an octree associated with a three-dimensional model of geographic space, wherein the first cube is contained within the second cube;

determining, by the one or more computing devices, that a portion of a second image from a plurality of images is associated with the first spatial identifier; and

providing, by the one or more computing devices, the second image for display to the user.

9. The method of claim 8, wherein the user selection includes clicking on the first portion of the first image.

10. The method of claim 8, wherein the first portion of the first image is a pixel of the first image.

11. The method of claim 8, further comprising:

creating a scored listing of the plurality of images associated with the first spatial identifier.

12. The method of claim 10, further comprising:

selecting the second image from the scored listing of the plurality of images for display.

13. The method claim 8, wherein the octree has a root cube that encompasses the Earth, the root cube having a side length on the order of 2²³ meters.

14. The method of claim 8, wherein the first set of cubes have a side length of about ⅛

meter.

15. A system for mapping a portion of a first image to a spatial identifier of three-dimensional space comprising:

at least one memory storing data and instructions, the data comprising a plurality of images and

one or more computing devices, communicatively coupled to the at least one memory, programmed to;

generate an octree associated with a three-dimensional model of a geographic space, the octree having a lower level having a first set of cubes and a higher level having a second set of cubes, the first set of cubes being larger in number than the second set of cubes, and the second set of cubes being larger in size than the first set of cubes, wherein a given cube of the first set of cubes has a spatial identifier that identifies the given cube and another cube in the second set of cubes that contains the given cube, wherein a surface portion of an object represented in the three-dimensional model is within a first cube in the first set of cubes having a first spatial identifier;

determine, for a first image captured from a first location, a first ray extending in three-dimensional space from the first location through a first portion of the first image, the first portion of the first image capturing at least a portion of the object;

determine the first ray intersects with the object in the three-dimensional model at the surface portion of the object; and

associate the first portion of the first image with the first spatial identifier.

16. The system of claim 15, wherein the one or more computing devices is further programmed to:

determine, for a second image captured from a second location, a second ray extending in three-dimensional space from the second location through a second portion of a second image, the second portion of the second image capturing at least a portion of the object;

determine the second ray intersects with the object in the three-dimensional model at the surface portion of the object; and

associate the second portion of the second image with the first spatial identifier.

17. The system of claim 16, wherein the octree has a root cube that encompasses the Earth, the root cube having a side length on the order of 2²³ meters.

18. The system of claim 15, wherein the first set of cubes have a side length of about ⅛

meter.

19. A method for mapping a portion of a first image to a spatial identifier of three-dimensional space comprising:

generating, by one or more computing devices, an octree associated with a three-dimensional model of a geographic space, the octree having a lower level having a first set of cubes and a higher level having a second set of cubes, the first set of cubes being larger in number than the second set of cubes, and the second set of cubes being larger in size than the first set of cubes, wherein a given cube of the first set of cubes has a spatial identifier that identifies the given cube and another cube in the second set of cubes that contains the given cube, wherein a surface portion of an object represented in the three-dimensional model is within a first cube in the first set of cubes having a first spatial identifier;

determining, by the one or more computing devices, for a first image captured from a first location, a first ray extending in three-dimensional space from the first location through a first portion of the first image the first portion of the first image capturing at least a portion of the object;

determining, by the one or more computing devices, the first ray intersects with the object in the three-dimensional model at the surface portion of the object; and

associating, by the one or more computing devices, the first portion of the first image with the first spatial identifier.

20. The method of claim 19, further comprising:

determining, by the one or more computing devices, for a second image captured from a second location, a second ray extending in three-dimensional space from the second location through a second portion of the second image, the second portion of the second image capturing at least a portion of the object;

determining, by one or more computing devices, second ray intersects with the object in the three-dimensional model at the surface portion of the object; and

associating, by one or more computing devices, the second portion of the second image with the first spatial identifier.