System and method for determining position of a device

• US 9,965,682 B1
• Filed: 06/22/2015
• Issued: 05/08/2018
• Est. Priority Date: 03/12/2010
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google LLC (Alphabet Inc.)
• Inventors: Rivlin, Ehud, McClendon, Brian, Bouguet, Jean-Yves
• Primary Examiner(s): Jebari, Mohammed
• Assistant Examiner(s): Colon, Maria Vazquez
• Application Number:
  US14/745,981
• Time in Patent Office: 1,051 Days
• 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 comprising:

receiving a first image captured by a camera;

accessing a visual characteristic associated with a first object, the first object having an object location;

determining, with one or more processors, whether the first image captured the first object by determining whether a portion of the first image includes the visual characteristic;

determining, with the one or more processors, a location of the camera relative to the object location based on a size and shape associated with an object portion of the first image by;

comparing the size of the object portion of the first image with a size of the first image, and

comparing the shape of the object portion of the first image with a shape of a reference object;

receiving a second image captured by the camera, the second image having at least one portion associated with a second object, wherein the second object has a same visual characteristic as the first object but differing in surface area than the first object;

refining, by the one or more processors, the determined location of the camera to be a more precise location based at least on visual information contained within the at least one portion of the second image; and

displaying, on an electronic display, information based on the refined determined location of the camera.

2. The method of claim 1 wherein the first object contains visual indicia comprising an identifier associated with the reference object having a reference location, wherein an association between the identifier and the reference location is stored in an electronic memory.

3. The method of claim 2 wherein the method further comprises:

extracting the identifier from the object portion of the first image; and

determining, based on the extracted identifier, the object location relative to the reference location.

4. The method of claim 1 wherein comparing the shape of the object portion of the first image with the shape of the reference object comprises determining a size and shape of a first portion of the object portion of the first image relative to a size and shape of a second portion of the object portion of the first image.

5. The method of claim 1 wherein comparing the shape of the object portion of the first image with the shape of the reference object comprises determining a length of a first edge of the object portion of the first image relative to a length of a corresponding edge on the reference object.

6. The method of claim 1 further comprising determining a distance between the camera and the first object according to the comparison of the size of the object portion of the first image to the size of the first image.

7. The method of claim 1 further comprising determining an orientation of the camera relative to the object location based on the size and shape associated with the object portion of the first image.

8. The method of claim 1 wherein the first object is located within a space, wherein commercial products are disposed within the space, and wherein displaying information comprises displaying the determined location of the camera and at least one product location on a map.

9. The method of claim 8 wherein displaying information further comprises a recommended path from to the at least one product location on a map.

10. The method of claim 1 wherein the visual characteristic is a checkerboard pattern.

11. The method of claim 1 further comprising:

detecting, with the one or more processors, a three-dimensional signature having a three-dimensional signature location in the first image; and

wherein the determined location of the camera is further determined relative to the three-dimensional signature location.

12. A system comprising:

an electronic display;

a plurality of objects disposed within an interior space, each object including visual indicia from which a reference object may be determined;

a memory storing data identifying one or more visual characteristics associated with at least one of the plurality of objects; and

one or more processors configured to;

receive a first image captured by a camera;

determine whether the first image captured a first object by determining whether a portion of the first image includes one or more of the visual characteristics associated with the first object in the memory, the first object having an object location;

determine a location of the camera relative to the object location based on a size and shape associated with an object portion of the first image by;

comparing the size of the object portion of the first image with a size of the first image, and

comparing the shape of the object portion of the first image with a shape of a reference object;

receive a second image captured by the camera, the second image having at least one portion associated with a second object, wherein the second object has a same one or more of the visual characteristics as the first object but differing in surface area than the first object;

refine the determined location of the camera to be a more precise location based at least on visual information contained within the at least one portion of the second image; and

display, on the electronic display, information based on the refined determined location of the camera.

13. The system of claim 12 wherein the camera is stored in a wireless phone.

14. The system of claim 12 further comprising a server, wherein the server provides visual characteristic data to the processor in response to a request from the processor.

15. The system of claim 14 wherein the visual characteristic data is provided wirelessly to the processor.

16. The system of claim 12 further comprising a server, wherein the server provides, to the processor, the reference object and a reference location determined using the visual indicia of the object.

17. The system of claim 12 wherein the one or more processors is configured to determine a size and shape of a first portion of the object portion of the first image relative to a size and shape of a second portion of the object portion of the first image.

18. The system of claim 12 wherein the one or more processors is configured to determine a length of a first edge of the object portion of the first image relative to a length of a corresponding edge on the reference object.

19. The system of claim 12 wherein the one or more processors is configured to determine a distance between the camera and the first object according to the comparison of the size of the object portion of the first image to the size of the first image.

20. The system of claim 12 wherein the one or more processors is configured to determine an orientation of the camera relative to the object location based on the size and shape associated with the object portion of the first image.