Robust object recognition by dynamic modeling in augmented reality

• US 8,866,845 B2
• Filed: 03/10/2010
• Issued: 10/21/2014
• Est. Priority Date: 03/10/2010
• Status: Active Grant

• Current Assignee: Empire Technology Development LLC (Allied Inventors Management, LLC)
• Original Assignee: Empire Technology Development LLC (Allied Inventors Management, LLC)
• Inventors: Leung, Henry, Chen, Siyue
• Primary Examiner(s): Tung, Kee M
• Assistant Examiner(s): Du, Haixia
• Application Number:
  US12/720,858
• Publication Number:
  US 20110221769A1
• Time in Patent Office: 1,686 Days
• Field of Search: 345/633
• US Class Current: 345/633
• CPC Class Codes: G06V 10/426 Graphical representations
• CPC Class Codes: G06V 30/1988 Graph matching graphical image representation G06V30/18181

Abstract

Technologies are generally described for providing a robust object recognition scheme based on dynamic modeling. Correlations in fine scale temporal structure of cellular regions may be employed to group the regions together into higher-order entities. The entities represent a rich structure and may be used to code high level objects. Object recognition may be formatted as elastic graph matching.

Claims

1. A method for performing object recognition in Augmented Reality (AR) systems, the method comprising:

converting a two dimensional image of an object to an image domain representation;

defining an attributed graph in the image domain based on links between nodes of the image domain representation;

defining another attributed graph in a model domain, wherein one or more attributed graphs in the model domain act as a prototype graph database;

selecting a prototype graph from the prototype graph database by creating one or more prototype sets from a training graph set in the model domain, wherein an initial set is constructed by selecting graphs randomly from the training set;

decomposing the attributed graph in the image and model domains into a combination of subsets from the prototype graph with respect to each domain to simplify a structure of the attributed graph in the image domain and the other attributed graph in the model domain;

estimating actual attribute values for nodes in the model domain by applying time-averaging to a set of fluctuating images with respect to each node in the model domain; and

matching the attributed graphs in the image and model domains by identifying and activating links between corresponding nodes of the attributed graphs.

2. The method according to claim 1, further comprising

reducing a number connections between the attributed graphs in the image and model domains;

and

back-labeling a model domain representation of the two dimensional image with patterns based on the reduced connections.

3. The method according to claim 2, further comprising

rendering a composite image by overlaying the two dimensional image with the model domain representation.

4. The method according to claim 1, further comprising

determining features associated with each node in the image domain representation;

and

obtaining vertex labels representing activity vectors of local features for each node in the image domain representation by applying the features to pixels of the two dimensional image.

5. The method according to claim 4, further comprising

obtaining edge labels that represent connectivity between the nodes of the image domain representation by establishing links between the nodes of the image domain representation.

6. The method according to claim 5, wherein the attributed graph in the image domain is defined as a collection of the nodes in the image domain representation and associated vertex and edge labels.

7. The method according to claim 1, further comprising

encoding bindings between nodes in the model domain as temporal correlations.

8. The method according to claim 7, further comprising

computing and assigning weights to links between the nodes in the model domain based on the encoded bindings.

9. An apparatus to perform object recognition in Augmented Reality (AR) systems, the apparatus comprising:

a memory adapted to store image data and graph data;

a first processing unit adapted to execute a dynamic modeling module, wherein the dynamic modeling module is adapted to;

transform a two dimensional (2D) image from the stored image data to an image domain representation comprising a 2 D array of linked nodes with each node encoding at least one distinct feature in image domain, wherein one or more links between the nodes are excitatory connections having a positive weight;

determine vertex labels representing activity vectors of the at least one feature for each node in the image domain;

determine edge labels representing connectivity between the nodes of the image domain;

define an attributed graph in model domain based on one or more of the vertex labels and/or the edge labels, the attributed graph being stored in the memory as part of the graph data, wherein the attributed graph and one or more other attributed graphs defined in the model domain act as a prototype graph database; and

select a prototype graph from the prototype graph database by creating one or more prototype sets from a training graph set in the model domain to decompose the attributed graph in the model domain into a combination of subsets from the prototype graph with respect to each domain to simplify a structure of the attributed graph in the model domain, wherein an initial set is constructed by selecting graphs randomly from the training set; and

a second processing unit adapted to execute a graph matching module, wherein the graph matching module is adapted to;

estimate actual attribute values for nodes in the model domain by applying time-averaging to a set of fluctuating images with respect to each node in the model domain;

identify and activate the one or more links between the nodes in the image domain and corresponding nodes in the model domain to preserve the at least one distinct feature; and

reduce a number of connections between nodes with similar features.

10. The apparatus according to claim 9, wherein the dynamic modeling module is further adapted to

group and selectively activate the nodes in the image domain.

11. The apparatus according to claim 10, wherein the dynamic modeling module is further adapted to group the nodes in the image domain by binding nodes in the image domain with similar feature vectors together.

12. The apparatus according to claim 9, wherein the graph matching module is further adapted to identify and activate the links between the nodes in the image domain and in the model domain by

retrieving a connection pattern from the memory;

and

performing a search for vertex positions with the connection pattern retrieved from the memory.

13. The apparatus according to claim 12, wherein the graph matching module is further adapted to

match the vertex labels and the edge labels according to a predefined cost function.

14. The apparatus according to claim 9, further comprising

a third processing unit adapted to execute a rendering module, wherein the rendering module is adapted to render a composite image by overlaying the two dimensional image with an model domain representation of the image based on the reduced connections.

15. The apparatus according to claim 14, wherein the first, second, and third processing units are integrated into a first computing device, a second computing device, and a third computing device, respectively, and wherein the first, the second, and the third computing devices are communicative over a network.

16. The apparatus according to claim 14, wherein the first, second, and third processing units are part of the same processor.

17. A method for performing object recognition in Augmented Reality (AR) systems, the method comprising:

converting a two dimensional image of an object to an image domain representation comprising a plurality of linked nodes, each node including a set of feature detectors bundled to act as a composite feature detector;

determining vertex labels that represent activity vectors of the feature detectors by applying the feature detectors to each pixel of the two dimensional image;

determining edge labels that represent connectivity between the nodes by detecting links between each node;

generating an attributed graph in the image domain based on the vertex and edge labels;

providing the composite feature detector to a model domain;

defining an attributed graph in the model domain, wherein the attributed graph in the model domain is an idealized copy of the attributed graph in the image domain established from the provided composite feature detector, and wherein one or more attributed graphs in the model domain act as a prototype graph database with which graph matching is implemented;

selecting a prototype graph from the prototype graph database by;

creating one or more prototype sets from a training graph set in the model domain, wherein an initial set is constructed by selecting graphs randomly from the training set, and wherein the initial set includes graph models in the image domain and the model domain;

scanning the training graph set in the model domain to find the prototype graph corresponding to the initial set; and

outputting the prototype graph;

decomposing the attributed graphs in the image domain and the model domain into a combination of subsets from the prototype graph with respect to each domain to simplify a structure of the attributed graphs in the image domain and the model domain;

determining connections between the attributed graphs in the image domain and the model domain based on matching vertex labels and edge labels of the attributed graphs; and

reducing the connections to a topology-preserving mapping between the image domain and the model domain.

18. The method according to claim 17, comprising:

recognizing patterns based on the mapped connections;

generating a virtual image based on the recognized patterns; and

generating a composite image based on overlaying the two dimensional image and the virtual image.

19. The method according to claim 17, further comprising:

determining the connections between the attributed graphs in the image domain and the model domain by searching for vertex positions and optimizing a match between vertex labels and edge labels for each vertex position according to a predefined cost function.

20. The method according to claim 17, further comprising:

binding nodes in the image domain with similar feature vectors without reference to the model domain.

21. The method according to claim 17, further comprising:

determining connections for an attributed graph pair in the image domain and the model domain, respectively, if an approximate neighborhood preserving and feature type preserving mapping exists between substantially all nodes of the attributed graphs.

22. The method according to claim 17, further comprising:

determining connections for an attributed graph pair in the image domain and the model domain, respectively, based on assigned weights to links between nodes in the image domain.

23. The method according to claim 17, wherein generating the attributed graph in the image domain, defining the attributed graph in the model domain, and determining connections between the attributed graphs in the image domain and the model domain are performed in an interlaced fashion.

24. The method according to claim 17, wherein each node is associated with one or more features including:

a local light intensity, a reflectance property, an object pose, an occlusion, and/or a background variation.

25. A system to perform object recognition in Augmented Reality (AR) systems, comprising:

at least one sensor adapted to capture a two dimensional (2D) image of a real scene;

an image processing server adapted to convert the 2 D image to an image domain representation comprising a 2 D array of linked nodes in the image domain, each node including a set of feature detectors, wherein one or more links between the nodes are excitatory connections having a positive weight;

a reality server adapted to;

determine vertex labels representing activity vectors of the at least one feature for each node in the image domain;

determine edge labels representing connectivity between the nodes of the image domain;

define an attributed graph in the image domain and another attributed graph in model domain based on the vertex and edge labels, wherein one or more attributed graphs in the model domain act as a prototype graph database;

select a prototype graph from the prototype graph database by creating one or more prototype sets from a training graph set in the model domain, wherein an initial set is constructed by selecting graphs randomly from the training set;

decompose the attributed graph in the image domain and the other attributed graph in the model domain into a combination of subsets from the prototype graph with respect to each domain to simplify a structure of the attributed graph in the image domain and the other attributed graph in the model domain;

estimate actual attribute values for nodes in the model domain by applying

time-averaging to a set of fluctuating images with respect to each node in the model domain;

identify and activate links between the nodes in the image domain and corresponding nodes in the model domain;

reduce a number of connections between nodes with similar features; and

an image generation server adapted to generate an augmented scene by overlaying the 2 D image and a virtual image rendered based on the reduced connections between the attributed graph in the image domain and the other attributed graph in the image domain, wherein the augmented scene generation is performed through luminance keying.

26. The system according to claim 25, wherein the reality server is further adapted to

store the attributed graph in the model domain in an associative data store.

27. The system according to claim 25, wherein the reality server is further adapted to

identify and activate links between the nodes in the image domain and corresponding nodes in the model domain by determining an approximate neighborhood preserving and feature type preserving mapping between substantially all nodes of the attributed graphs;

and

reduce the connections to topology preserving connections.

28. The system according to claim 25, wherein the image processing server, reality server, and image generation server are part of one of:

a centralized AR system and a distributed AR system.

29. The system according to claim 25, further comprising a visualization system adapted to visualize the augmented scene, wherein the visualization system includes one or more of a head-mounted display, a virtual retinal display, and/or a monitor.