Locating objects using indicia

• US 8,724,848 B1
• Filed: 11/11/2010
• Issued: 05/13/2014
• Est. Priority Date: 11/11/2010
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Heath, Taliver Brooks, Mierle, Keir B.
• Primary Examiner(s): Repko, Jason M
• Assistant Examiner(s): FUJITA, KATRINA R
• Application Number:
  US12/944,597
• Time in Patent Office: 1,279 Days
• Field of Search: 382/103, 382/201, 382/291, 701/513, 348/169
• US Class Current: 382/103
• CPC Class Codes: G01C 21/025 with the use of startrackers
• CPC Class Codes: G01S 3/7867 Star trackers navigation using star trackers G01C21/025
• CPC Class Codes: G01S 5/16 using electromagnetic waves other than radio waves
• CPC Class Codes: G06T 2207/10016 Video; Image sequence
• CPC Class Codes: G06T 2207/30204 Marker
• CPC Class Codes: G06T 2207/30208 Marker matrix
• CPC Class Codes: G06T 7/73 using feature-based methods
• CPC Class Codes: G06V 10/245 by locating a pattern; Special marks for positioning
• CPC Class Codes: G06V 10/443 by matching or filtering

Abstract

This specification relates to locating objects using indicia. In general, one innovative aspect of the subject matter described in this specification can be embodied in methods that include the actions of obtaining an image captured from a camera in proximity of an object located in an indoor facility, the image being of a portion of a surface of the indoor facility comprising a plurality of visible indicia, the camera having an orientation generally pointed at the surface. A plurality of local indicia are identified within the image. The locations of the local indicia within the image and an index of the visible indicia of the surface are used to determine the location of the object relative to the surface.

Claims

1. A computer-implemented method comprising:

applying, by one or more computing devices, a plurality of visible indicia on a surface of an indoor facility such that a distance between any visible indicium of the plurality of visible indicia and a nearest visible indicium in the plurality of visible indicia is less than a threshold;

obtaining, by the one or more computing devices, a first image captured from a camera, the first image being of a first portion of the surface of the indoor facility comprising the plurality of visible indicia, the camera having an orientation generally pointed at the surface;

moving, by the one or more computing devices, the camera a specified distance;

obtaining, by the one or more computing devices, a second image captured from the camera of the indoor facility, the second image being of a second portion of the surface of the indoor facility comprising the plurality of visible indicia, the camera having an orientation generally pointed at the surface;

determining, by the one or more computing devices, a composite image based on the first image and the second image;

locating, by the one or more computing devices, a plurality of indicia within the composite image;

determining, by the one or more computing devices, an index of the visible indicia of the surface based on the plurality of indicia;

obtaining, by the one or more computing devices, a third image captured from the camera in proximity of an object located in an indoor facility, the third image being of a third portion of the surface of the indoor facility comprising the plurality of visible indicia, the camera having an orientation generally pointed at the surface;

identifying, by the one or more computing devices, a plurality of local indicia within the third image;

using the locations of the local indicia within the third image and the index of the visible indicia of the surface, determining, by the one or more computing devices, the location of the object relative to the surface, including;

determining, by the one or more computing devices, a plurality of locations of the local indicia within the third image;

determining, by the one or more computing devices, an object hash code using the locations of two most widely-separated local indicia and comparing the object hash code to a plurality of hash codes in the index of the visible indicia on the surface; and

based on the location of the local indicia on the surface, determining, by the one or more computing devices, the location of the object.

2. The method of claim 1, where the plurality of visible indicia are painted shapes or optically projected shapes.

3. The method of claim 1, where the visible indicia are distributed on the surface in a random pattern.

4. The method of claim 1, where the object is an equipment rack and the surface is a ceiling of the indoor facility.

5. The method of claim 1, where identifying the plurality of local indicia within the image includes detecting and removing features of the surface from the image.

6. The method of claim 5, where the features comprise lines.

7. The method of claim 1, where identifying the plurality of local indicia within the image includes adjusting the image for variations of the orientation of the camera towards the surface.

8. The method of claim 1, where determining the location of the object further comprises verifying one or more location hypotheses.

9. The method of claim 1, further comprising:

receiving a request for the location of the object.

10. The method of claim 1, further comprising:

presenting a graphical display including an indication of the location of the object.

11. The method of claim 10, where:

the request is received from a user using a mobile device; and

presenting a graphical display comprises sending location information to the mobile device.

12. A system comprising:

one or more processors configured to interact with a computer storage medium in order to perform operations comprising;

applying a plurality of visible indicia on a surface of an indoor facility such that a distance between any visible indicium of the plurality of visible indicia and a nearest visible indicium in the plurality of visible indicia is less than a threshold;

obtaining a first image captured from a camera, the first image being of a first portion of the surface of the indoor facility comprising the plurality of visible indicia, the camera having an orientation generally pointed at the surface;

moving the camera a specified distance;

obtaining a second image captured from the camera of the indoor facility, the second image being of a second portion of the surface of the indoor facility comprising the plurality of visible indicia, the camera having an orientation generally pointed at the surface;

determining a composite image based on the first image and the second image;

locating a plurality of indicia within the composite image;

determining an index of the visible indicia of the surface based on the plurality of indicia;

obtaining a third image captured from the camera in proximity of an object located in an indoor facility, the third image being of a third portion of the surface of the indoor facility comprising the plurality of visible indicia, the camera having an orientation generally pointed at the surface;

identifying a plurality of local indicia within the third image;

using the locations of the local indicia within the third image and the index of the visible indicia of the surface, determining the location of the object relative to the surface, including;

determining a plurality of locations of the local indicia within the third image;

determining an object hash code using the locations of two most widely-separated local indicia and comparing the object hash code to a plurality of hash codes in the index of the visible indicia on the surface; and

based on the location of the local indicia on the surface, determining the location of the object.

13. The system of claim 12, where the plurality of visible indicia are painted shapes or optically projected shapes.

14. The system of claim 12, where the visible indicia are distributed on the surface in a random pattern.

15. The system of claim 12, where the object is an equipment rack and the surface is a ceiling of the indoor facility.

16. The system of claim 12, where identifying the plurality of local indicia within the image includes detecting and removing features of the surface from the image.

17. The system of claim 16, where the features comprise lines.

18. The system of claim 12, where identifying the plurality of local indicia within the image includes adjusting the image for variations of the orientation of the camera towards the surface.

19. The system of claim 12, where determining the location of the object further comprises verifying one or more location hypotheses.

20. The system of claim 12, the operations further comprising:

receiving a request for the location of the object.

21. The system of claim 12, the operations further comprising:

presenting a graphical display including an indication of the location of the object.

22. The system of claim 21, where:

the request is received from a user using a mobile device; and

presenting a graphical display comprises sending location information to the mobile device.

23. A non-transitory computer storage medium encoded with a computer program, the program comprising instructions that when executed by data processing apparatus cause the data processing apparatus to perform operations comprising:

applying a plurality of visible indicia on a surface of an indoor facility such that a distance between any visible indicium of the plurality of visible indicia and a nearest visible indicium in the plurality of visible indicia is less than a threshold;

obtaining a first image captured from a camera, the first image being of a first portion of the surface of the indoor facility comprising the plurality of visible indicia, the camera having an orientation generally pointed at the surface;

moving the camera a specified distance;

obtaining a second image captured from the camera of the indoor facility, the second image being of a second portion of the surface of the indoor facility comprising the plurality of visible indicia, the camera having an orientation generally pointed at the surface;

determining a composite image based on the first image and the second image;

locating a plurality of indicia within the composite image;

determining an index of the visible indicia of the surface based on the plurality of indicia;

obtaining a third image captured from the camera in proximity of an object located in an indoor facility, the third image being of a third portion of the surface of the indoor facility comprising the plurality of visible indicia, the camera having an orientation generally pointed at the surface;

identifying a plurality of local indicia within the third image;

using the locations of the local indicia within the third image and the index of the visible indicia of the surface, determining the location of the object relative to the surface, including;

determining a plurality of locations of the local indicia within the third image;

determining an object hash code using the locations of two most widely-separated local indicia and comparing the object hash code to a plurality of hash codes in the index of the visible indicia on the surface; and

based on the location of the local indicia on the surface, determining the location of the object.