Navigation Using Portable Reading Machine

• US 20100049431A1
• Filed: 04/30/2009
• Published: 02/25/2010
• Est. Priority Date: 04/30/2008
• Status: Active Grant

• Current Assignee: National Federation of the Blind
• Original Assignee: K-NFB Reading Technology Inc.
• Inventors: Zetune, Rafael Maya
• Granted Patent: US 8,554,464 B2
• Time in Patent Office: Days
• US Class Current: 701/200
• CPC Class Codes: G01C 21/20 Instruments for performing navigational calculations G01C21/24, G01C21/26 take precedence
• CPC Class Codes: G01C 21/206 specially adapted for indoor navigation
• CPC Class Codes: G01C 21/3878 Hierarchical structures, e.g. layering
• 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
• CPC Class Codes: G06V 30/10 Character recognition
• CPC Class Codes: G06V 30/18181 Graphical representation, e.g. directed attributed graph

Abstract

Navigation techniques including map based and object recognition based and especially adapted for use in a portable reading machine are described.

Claims

1. A device comprising:

one or more processing devices;

memory to store instructions that are executable by the one or more processing devices to;

capture images of physical scenes containing at least one or more of objects, landmarks, and signs;

associate the objects, landmarks and/or signs contained in the images to nodes that correspond to the objects landmarks and/or signs;

associate, with the nodes, parameters relating to the objects; and

generate a construct relating the objects to each another, the objects being related based, at least in part, on the parameters.

2. The device of claim 1, wherein to generate a construct comprises generating an edge between the nodes representing relationships between the corresponding objects.

3. The device of claim 1, wherein to generate a construct comprises generating an edge between the nodes containing information about connectedness of the corresponding objects.

4. The device of claim 1, wherein to generate a construct comprises generating an edge between the nodes containing information about proximity of the corresponding objects.

5. The device of claim 1, wherein the nodes and the construct relating objects to each another are incorporated in a map for use in navigation.

6. The device of claim 1, wherein the construct comprises an un-directed edge between the nodes and the nodes and the corresponding un-directed edge are incorporated in an un-directed map.

7. The device of claim 1, wherein the construct comprises an edge between the nodes and the nodes and the corresponding edge are incorporated in a directed map.

8. The device of claim 1, wherein the construct comprises edges having different directions between one pair of nodes.

9. The device of claim 1, wherein the construct comprises navigation instructions.

10. The device of claim 1, wherein the construct comprises description of the objects.

11. The device of claim 1, wherein at least some of the nodes each comprises more than one edge connected to another node.

12. The device of claim 1, wherein the objects comprise first and second sets, the second set objects each is accessible only from one of the second set of objects.

13. The device of claim 1, wherein each of the objects in the second set corresponds to a node that is connected to a node representing a corresponding object in the first set using one edge.

14. The device of claim 1, wherein the first set of objects are incorporated in a first layer of a map and the second set of objects are incorporated in a second layer of the map.

15. The device of claim 1, wherein the construct comprises a list that associates at least one node to one or more other nodes to which the at least one node is connected.

16. The device of claim 1, wherein the construct comprises a matrix that associates at least one node to one or more other nodes to which the at least one node is connected.

17. The device of claim 1, wherein the matrix stores the parameters, the parameters corresponding to distances between nodes.

18. The device of claim 1, wherein the parameters comprise distances between adjacent nodes.

19. The device of claim 1, wherein the construct comprises one of an incidence list, or an adjacency list, or an incidence matrix, or an adjacency matrix, or a distance matrix.

20. The device of claim 1, further comprising using the construct to generate searchable paths each from any node to any other node.

21. The device of claim 1, further comprising using the construct to generate a route among the objects.

22. The device of claim 1, further comprising instructions that are executable by the one or more processing devices to:

perform a process to identify the route among the objects, the process identifying a path among the objects, the path having a predefined characteristic.

23. The device of claim 1, wherein the process comprises a shortest path algorithm, and wherein the predefined characteristic comprises a length of the path.

24. The device of claim 1, wherein the parameters relate to objects that are encountered along the route.

25. The device of claim 1, further comprising providing a user navigation instructions to reach an object in the first layer of the map and providing to the user information about objects in the second layer of the map and each corresponding to a node having connectedness to a node corresponding to the object in the first layer.

26. The device of claim 1, further comprising upon receiving starting and ending positions, processing information about the nodes and construct to select correct paths or sub paths between the starting and ending positions.

27. The device of claim 1, further comprising instructions that are executable by the one or more processing devices to:

capture an image of an object (physical object, landmark, sign, etc);

extract features from the image;

produce an array of n features having values for the n features, with the values representing the object;

represent the array as a point in n-dimensional space, where n corresponds to the number of features in the array; and

compare the point in n-dimensional space to a centroid that represents a cluster of points in the n-dimensional space corresponding to a class of objects to determine whether the point belongs in the class of objects corresponding to the centroid.

28. The device of claim 1, further comprising instructions that are executable by the one or more processing devices to:

use the class to identify the object; and

communicate an identity of the object when the object is encountered along the route.

29. A computer program product tangibly embodied on a computer readable medium for navigation of a physical environment, comprises instructions for causing a computer device to:

capture images of physical scenes containing at least one or more of objects, landmarks, and signs;

associate the objects, landmarks and/or signs contained in the images to nodes that correspond to the objects landmarks and/or signs;

associate, with the nodes, parameters relating to the objects; and

generate a construct relating the objects to each another, the objects being related based, at least in part, on the parameter.

30. A computer implement method for navigation of a physical environment, comprises:

capture images of physical scenes using an image input device, the physical scene containing at least one or more of objects, landmarks, and signs;

associate in a computing device the objects, landmarks and/or signs contained in the images to nodes that correspond to the objects landmarks and/or signs;

associate with the nodes in the computing device, parameters relating to the objects; and

generate in the computing device a construct relating the objects to each another, the objects being related based, at least in part, on the parameter.