Systems and methods for image recognition using graph-based pattern matching

• US 8,452,108 B2
• Filed: 06/25/2009
• Issued: 05/28/2013
• Est. Priority Date: 06/25/2008
• Status: Expired due to Fees

• Current Assignee: Gannon Technologies Group, LLC
• Original Assignee: Gannon Technologies Group, LLC
• Inventors: Walch, Mark A.
• Primary Examiner(s): Werner, Brian P
• Application Number:
  US12/492,111
• Publication Number:
  US 20090324107A1
• Time in Patent Office: 1,433 Days
• Field of Search: None
• US Class Current: 382/203
• CPC Class Codes: G06V 30/10 Character recognition
• CPC Class Codes: G06V 30/18181 Graphical representation, e.g. directed attributed graph
• CPC Class Codes: G06V 30/2272 with lexical matching

Abstract

A method for creating a modeling structure for classifying objects in an image comprises converting an image into digital image data; using a processor, simplifying the digital image data; using the processor, isolating objects in the simplified digital image data; using the processor, creating graphs of the isolated objects, the graphs comprising vertices and edges; using the processor, converting the graphs into representative graph data structures, the graph data structures comprising a database key based on the vertices and edges.

Claims

1. A method for creating a modeling structure for classifying objects in an image, the method comprising:

generating a library by, using one or more hardware processors, for each of one or more training images,

converting the training image into digital image data,

simplifying the digital image data,

isolating one or more objects in the simplified digital image data, and,

for each of the isolated one or more objects,

creating a graph of the isolated object, the graph comprising vertices and edges,

converting the graph into a representative graph data structure,

generating an isomorphic key based on the vertices and edges of the graph, wherein the isomorphic key identifies a topology of the graph, and

storing the graph data structure such that it can be retrieved using the isomorphic key; and

facilitating a query comprising a search image by, using one or more hardware processors,

converting the search image into digital search image data,

simplifying the digital search image data,

isolating one or more search objects in the simplified digital search image data,

for each of the isolated one or more search objects,

creating a graph of the isolated object, the graph comprising vertices and edges,

generating an isomorphic key based on the vertices and edges of the graph, and

retrieving one or more stored graph data structures based on the isomorphic key,

identifying one or more stored graph data structures that match the isolated one or more search objects from the retrieved one or more stored graph data structures,

retrieving metadata associated with the identified one or more stored graph data structures, and,

based on the retrieved metadata, determining one or more keywords to use in a search.

2. The method of claim 1, wherein each graph data structure includes an object classification.

3. The method of claim 1, further comprising classifying the graph data structures based on a regression tree classifier model.

4. The method of claim 1, further comprising classifying the graph data structures based on a neural network classifier model.

5. The method of claim 1, further comprising classifying the graph data structures based on a discriminant analysis model.

6. The method of claim 1, wherein simplifying the digital image data comprises reducing the image complexity and segmenting one or more foreground objects from a background.

7. The method of claim 6, wherein reducing the image complexity comprises digital signal processing techniques including at least one of the following:

Wiener filtering, automatic brightness adjustment, and contrast stretching.

8. The method of claim 6, wherein segmenting includes at least one of the following methods:

adaptive thresholding, morphological reconstructions, and ridge detection.

9. The method of claim 6, wherein reducing the image complexity comprises accentuating sharp straight edges and suppressing amorphous objects within the image.

10. The method of claim 1, wherein isolating one or more objects in the simplified image data comprises isolating objects embedded in a larger, more complex image.

11. The method of claim 1, wherein the graph data structure includes intrinsic and extrinsic characteristics of the isolated object.

24. The method of claim 1, further comprising performing a search using the one or more keywords.

12. A system for creating a modeling structure for classifying objects in an image, the system comprising:

at least one database;

at least one image input interface configured to receive a digital image; and

one or more processors communicatively coupled with the at least one database and the at least one image input interface, the one or more processors configured to;

generate a library by, for each of one or more training images,

converting the training image into digital image data,

simplifying the digital image data,

isolating one or more objects in the simplified digital image data, and,

for each of the isolated one or more objects,

creating a graph of the isolated object, the graph comprising vertices and edges,

converting the graph into a representative graph data structure,

generating an isomorphic key based on the vertices and edges of the graph, wherein the isomorphic key identifies a topology of the graph, and

storing the graph data structure such that it can be retrieved using the isomorphic key, and

facilitate a query comprising a search image by

converting the search image into digital search image data,

simplifying the digital search image data,

isolating one or more search objects in the simplified digital search image data,

for each of the isolated one or more search objects,

creating a graph of the isolated object, the graph comprising vertices and edges,

generating an isomorphic key based on the vertices and edges of the graph, and

retrieving one or more stored graph data structures based on the isomorphic key,

identifying one or more stored graph data structures that match the isolated one or more search objects from the retrieved one or more stored graph data structures,

retrieving metadata associated with the identified one or more stored graph data structures, and,

based on the retrieved metadata, determining one or more keywords to use in a search.

13. The system of claim 12, wherein each graph data structure includes an object classification.

14. The system of claim 12, wherein the one or more processors are further configured to classify the graph data structures based on a regression tree classifier model.

15. The system of claim 12, wherein the one or more processors are further configured to classify the graph data structures based on a neural network classifier model.

16. The system of claim 12, wherein the one or more processors are further configured to classify the graph data structures based on a discriminant analysis model.

17. The system of claim 12, wherein the one or more processors are configured to simplify the digital image data by reducing the image complexity and segmenting one or more foreground objects from a background.

18. The system of claim 17, wherein reducing the image complexity comprises at least one of the following:

Wiener filtering, automatic brightness adjustment, and contrast stretching.

19. The system of claim 17, wherein segmenting includes at least one of the following:

adaptive thresholding, morphological reconstructions, and ridge detection.

20. The system of claim 17, wherein reducing the image complexity comprises accentuating sharp straight edges and suppressing amorphous objects within the image.

21. The system of claim 12, wherein isolating one or more objects in the simplified image data comprises isolating objects embedded in a larger more complex image.

22. The system of claim 12, wherein the graph data structure includes intrinsic and extrinsic characteristics of the isolated object.

23. The system of claim 12, wherein the one or more processors are further configured to perform a search using the one or more keywords.