System and method for determining position of a device

• US 9,098,905 B2
• Filed: 03/12/2010
• Issued: 08/04/2015
• Est. Priority Date: 03/12/2010
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Rivlin, Ehud, McClendon, Brian, Bouguet, Jean-Yves
• Primary Examiner(s): Senfi, Behrooz
• Assistant Examiner(s): VAZQUEZ COLON, MARIA E
• Application Number:
  US12/722,939
• Publication Number:
  US 20150178565A1
• Time in Patent Office: 1,971 Days
• Field of Search: 348/169, 348/116, 348/135
• US Class Current: 1/1
• CPC Class Codes: G06K 2019/06243 concentric-code
• CPC Class Codes: G06T 2207/10004 Still image; Photographic image
• CPC Class Codes: G06T 2207/30204 Marker
• CPC Class Codes: G06T 2207/30244 Camera pose
• CPC Class Codes: G06T 7/246 using feature-based methods, e.g. the tracking of corners or segments
• CPC Class Codes: G06T 7/285 using a sequence of stereo image pairs
• CPC Class Codes: G06T 7/73 using feature-based methods
• CPC Class Codes: G06V 20/10 Terrestrial scenes scenes under surveillance with static cameras G06V20/52; scenes perceived from the exterior of a vehicle G06V20/56; scenes perceived from the interior of a vehicle G06V20/59

Abstract

A system and method is provided for determining the location of a device based on image of objects captured by the device. In one aspect, an interior space includes a plurality of objects having discernable visual characteristics disposed throughout the space. The device captures an image containing one or more of the objects and identifies the portions of the image associated with the objects based on the visual characteristics. The visual appearance of the objects may also be used to determine the distance of the object to other objects or relative to a reference point. Based on the foregoing and the size and shape of the image portion occupied by the object, such as the height of an edge or its surface area, relative to another object or a reference, the device may calculate its location.

Claims

1. A method of determining a location of a camera within an interior space comprising:

receiving, by one or more processors, a first image captured by the camera;

identifying, by the one or more processors, two different portions of the first image associated with a first object and a second object within the space, wherein the first object defines a first contiguous surface extending to a first edge and the second object defines a second contiguous surface extending to a second edge, and wherein the portions are identified by comparing visual characteristics of the portions with visual characteristics known to be associated with each of the first and second objects;

identifying, by the one or more processors, based on visual information contained within the portions of the first image displaying the first and second objects, a distance between the first edge of the first object and the second edge of the second object;

determining, by the one or more processors, a first location of the camera based on a comparison of the sizes and shapes of the portions of the first image associated with the first and second objects and the distance between the first edge of the first object and the second edge of the second object;

providing, by the one or more processors, information based on the first location of the camera;

receiving, by the one or more processors, a second image captured by the camera, the second image having at least one portion associated with at least one object, wherein the at least one object is smaller in size than the first and second objects;

determining, by the one or more processors, a second location of the camera based at least on visual information contained within the at least one portion, the second location being more precise than the first location; and

providing, by the one or more processors, information based on the second location of the camera.

2. The method of claim 1, wherein the visual information contained within the portions of the image displaying the first and second objects comprises visual information that distinguishes the first object from the second object.

3. The method of claim 1, wherein the visual information comprises a unique identifier for each of the first and second object, and wherein identifying the distance between the first edge of the first object and the second edge of the second object comprises accessing distance information associated with the identifiers.

4. The method of claim 2, wherein accessing distance information comprises accessing locations of the first object and the second object within the space based on the identifiers, and calculating the distance between the first edge of the first object and the second edge of the second object based on the accessed locations.

5. The method of claim 1, wherein the first edge of the first object and the second edge of the second object are opposing edges.

6. The method of claim 1, wherein the determined first location of the camera is further based on a visual angle between the first edge and the second edge.

7. The method of claim 1, wherein the provided information includes a location of the camera on a map relative to the first object and the second object.

8. An apparatus for determining a location of a camera within an interior space comprising:

one or more processors; and

a non-transitory computer-readable medium storing computer-executable instructions that, when executed by the one or more processors, cause the one or more processors to perform the steps of;

receiving an image captured by the camera;

identifying two different portions of the image associated with a first object and a second object within the space, wherein the first object defines a first contiguous surface extending to a first edge and the second object defines a second contiguous surface extending to a second edge, and wherein the portions are identified by comparing visual characteristics of the portions with visual characteristics known to be associated with each of the first and second objects;

identifying, based on visual information contained within the portions of the image displaying the first and second objects, a distance between the first edge of the first object and the second edge of the second object;

determining a first location of the camera based on a comparison of the sizes and shapes of the portions of the image associated with the first and second objects and the distance between the first edge of the first object and the second edge of the second object;

providing information based on the first location of the camera;

receiving a second image captured by the camera, the second image having at least one portion associated with at least one object, wherein the at least one object is smaller in size than the first and second objects;

determining a second location of the camera based at least on visual information contained within the at least one portion; and

providing information based on the second location of the camera.

9. The apparatus of claim 8, wherein the visual information contained within the portions of the image displaying the first and second objects comprises visual information that distinguishes the first object from the second object.

10. The apparatus of claim 9, wherein the visual information comprises a unique identifier for each of the first and second object, and wherein identifying the distance between the first edge of the first object and the second edge of the second object comprises accessing distance information associated with the identifiers.

11. The apparatus of claim 10, wherein accessing distance information comprises accessing locations of the first object and the second object within the space based on the identifiers, and calculating the distance between the first edge of the first object and the second edge of the second object based on the accessed locations.

12. The apparatus of claim 8, wherein the first edge of the first object and the second edge of the second object are opposing edges.

13. The apparatus of claim 8, wherein the determined first location of the camera is further based on a visual angle between the first edge and the second edge.

14. The apparatus of claim 8,

wherein the provided information includes a location of the camera on a map relative to the first object and the second object.

15. A non-transitory, computer-readable medium storing computer-executable instructions that, when executed by one or more processors, cause the one or more processors to perform a method, the method comprising:

receiving, by the one or more processors, an image captured by a camera;

identifying, by the one or more processors, two different portions of the image associated with a first object and a second object within an interior space, wherein the first object defines a first contiguous surface extending to a first edge and the second object defines a second contiguous surface extending to a second edge, and wherein the portions are identified by comparing visual characteristics of the portions with visual characteristics known to be associated with each of the first and second objects;

identifying, by the one or more processors, based on visual information contained within the portions of the image displaying the first and second objects, a distance between the first edge of the first object and the second edge of the second object;

determining, by the one or more processors, a first location of the camera based on a comparison of the sizes and shapes of the portion of the image associated with the first and second objects and the distance between the first edge of the first object and the second edge of the second object;

providing, by the one or more processors, information based on the first location of the camera;

receiving, by the one or more processors, a second image captured by the camera, the second image having at least one portion associated with at least one object, wherein the at least one object is smaller in size than the first and second objects;

determining, by the one or more processors, a second location of the camera based at least on visual information contained within the at least one portion; and

providing, by the one or more processors, information based on the second location of the camera.

16. The non-transitory, computer-readable medium of claim 15, wherein the visual information contained within the portions of the image displaying the first and second objects comprises visual information that distinguishes the first object from the second object.

17. The non-transitory, computer-readable medium of claim 16, wherein the visual information comprises a unique identifier for each of the first and second object, and wherein identifying the distance between the first edge of the first object and the second edge of the second object comprises accessing distance information associated with the identifiers.

18. The non-transitory, computer-readable medium of claim 17, wherein accessing distance information comprises accessing locations of the first object and the second object within the space based on the identifiers, and calculating the distance between the first edge of the first object and the second edge of the second object based on the accessed locations.

19. The non-transitory, computer-readable medium of claim 15, wherein the first edge of the first object and the second edge of the second object are opposing edges.

20. The non-transitory, computer-readable medium of claim 15, wherein the determined first location of the camera is further based on a visual angle between the first edge and the second edge.