System and method for fast template matching in 3D

• US 9,171,247 B1
• Filed: 01/23/2013
• Issued: 10/27/2015
• Est. Priority Date: 06/27/2011
• Status: Active Grant

• Current Assignee: HRL Laboratories LLC (The Boeing Co.)
• Original Assignee: HRL Laboratories LLC (The Boeing Co.)
• Inventors: Hoffmann, Heiko, Kazemi, Hooman
• Primary Examiner(s): Hill, Stanley K
• Application Number:
  US13/747,987
• Time in Patent Office: 1,007 Days
• Field of Search: 382155-161, 382181-231, 706/20
• US Class Current: 1/1
• CPC Class Codes: G06F 16/532 Query formulation, e.g. graphical querying
• CPC Class Codes: G06F 18/00 Pattern recognition
• CPC Class Codes: G06N 3/02 Neural networks
• CPC Class Codes: G06V 20/64 Three-dimensional objects

Abstract

Described is a pattern matching system for matching a test image with a 3D template. The system is initiated by generating a library of templates (each individual template is a three-dimensional array, with each pixel in the array representing a value at a particular x, y, and z coordinate). Each column of pixels along one axis (e.g., z) is converted into a neural input. Each neural input is fed through a neural network to establish a delayed connection between each neural input and output neuron and to generate a template neural network. Separately, a test image is converted into neural inputs. The neural inputs of the test image are input the template neural network to generate output neurons. The output neurons are evaluated to identify a location of the template in the test image.

Claims

1. A system for pattern matching, the system comprising:

one or more processors and a memory, the memory having instructions encoded thereon such that upon execution of the instructions, the one or more processors perform operations of;

converting a test array into neural inputs;

receiving the neural inputs into a template neural network to generate output neurons; and

evaluating the output neurons to identify a location of a template in the test array.

2. The system as set forth in claim 1, wherein the operations further comprise:

generating a library of templates, where each template is a three-dimensional array, with each pixel in the array representing a value at a particular x, y, and z coordinate along x, y, and z axes, such that the library of templates is composed of a plurality of three-dimensional templates;

converting each column of pixels along one axis into a neural input; and

establishing a delayed connection between each neural input and output neurons to generate the template neural network.

3. The system as set forth in claim 2, wherein establishing a delayed connection further comprises operations of:

converting each pixel of each three-dimensional array through all layers into a neural index;

converting an x-axis into a time axis such that pixels with different x-coordinates represent different events in time;

identifying an x-location of a pixel or set of pixels in the template with the largest x-value, wherein the x-location with the largest x-value is a reference point that corresponds to a latest time point when pixels of the template are entered into the template neural network; and

setting a connection delay between each input neuron and output neuron based on a time gap between the x-location of each input neuron and the reference point.

4. The system as set forth in claim 3, wherein evaluating the output neurons further comprises operations of:

comparing values of the output neurons against a threshold, such that if an output neuron reaches its threshold, the output neuron fires, indicating a match between the template and test array;

obtaining an x-axis location as a time-step in which the output neuron fired; and

obtaining a y-axis location from an index of the output neuron.

5. The system as set forth in claim 4, wherein in receiving the neural inputs into a template neural network to generate output neurons, the neural input is fed forward to the output neurons through delayed connections.

6. The system as set forth in claim 1, wherein evaluating the output neurons further comprises operations of:

comparing values of the output neurons against a threshold, such that if an output neuron reaches its threshold, the output neuron fires, indicating a match between the template and test array;

obtaining an x-axis location as a time-step in which the output neuron fired; and

obtaining a y-axis location from an index of the output neuron.

7. The system as set forth in claim 1, wherein in receiving the neural inputs into a template neural network to generate output neurons, the neural input is fed forward to the output neurons through delayed connections.

8. The system as set forth in claim 1, wherein the test array is a test image.

9. A computer implemented method for pattern matching using one or more processors, the method comprising acts of:

converting, with the one or more processors, a test array into neural inputs;

receiving the neural inputs into a template neural network to generate output neurons; and

evaluating, with the one or more processors, the output neurons to identify a location of a template in the test array.

10. The method as set forth in claim 9, further comprising acts of:

generating a library of templates, where each template is a three-dimensional array, with each pixel in the array representing a value at a particular x, y, and z coordinate along x, y, and z axes, such that the library of templates is composed of a plurality of three-dimensional templates;

converting each column of pixels along one axis into a neural input; and

establishing a delayed connection between each neural input and output neurons to generate the template neural network.

11. The method as set forth in claim 10, wherein establishing a delayed connection further comprises acts of:

converting each pixel of each three-dimensional array through all layers into a neural index;

converting an x-axis into a time axis such that pixels with different x-coordinates represent different events in time;

identifying an x-location of a pixel or set of pixels in the template with the largest x-value, wherein the x-location with the largest x-value is a reference point that corresponds to a latest time point when pixels of the template are entered into the template neural network; and

setting a connection delay between each input neuron and output neuron based on a time gap between the x-location of each input neuron and the reference point.

12. The method as set forth in claim 11, wherein evaluating the output neurons further comprises acts of:

comparing values of the output neurons against a threshold, such that if an output neuron reaches its threshold, the output neuron fires, indicating a match between the template and test array;

obtaining an x-axis location as a time-step in which the output neuron fired; and

obtaining a y-axis location from an index of the output neuron.

13. The method as set forth in claim 12, wherein in receiving the neural inputs into a template neural network to generate output neurons, the neural input is fed forward to the output neurons through delayed connections.

14. The method as set forth in claim 9, wherein evaluating the output neurons further comprises acts of:

comparing values of the output neurons against a threshold, such that if an output neuron reaches its threshold, the output neuron fires, indicating a match between the template and test array;

obtaining an x-axis location as a time-step in which the output neuron fired; and

obtaining a y-axis location from an index of the output neuron.

15. The method as set forth in claim 9, wherein in receiving the neural inputs into a template neural network to generate output neurons, the neural input is fed forward to the output neurons through delayed connections.

16. The method as set forth in claim 9, wherein the test array is a test image.

17. A computer program product for pattern matching, the computer program product comprising computer-readable instructions stored on a non-transitory computer-readable medium that are executable by a computer having a processor for causing the processor to perform operations of:

converting a test array into neural inputs;

receiving the neural inputs into a template neural network to generate output neurons; and

evaluating the output neurons to identify a location of a template in the test array.

18. The computer program product as set forth in claim 17, further comprising instructions for causing the processor to perform operations of:

generating a library of templates, where each template is a three-dimensional array, with each pixel in the array representing a value at a particular x, y, and z coordinate along x, y, and z axes, such that the library of templates is composed of a plurality of three-dimensional templates;

converting each column of pixels along one axis into a neural input; and

establishing a delayed connection between each neural input and output neurons to generate the template neural network.

19. The computer program product as set forth in claim 18, wherein establishing a delayed connection further comprises operations of:

converting each pixel of each three-dimensional array through all layers into a neural index;

converting an x-axis into a time axis such that pixels with different x-coordinates represent different events in time;

identifying an x-location of a pixel or set of pixels in the template with the largest x-value, wherein the x-location with the largest x-value is a reference point that corresponds to a latest time point when pixels of the template are entered into the template neural network; and

setting a connection delay between each input neuron and output neuron based on a time gap between the x-location of each input neuron and the reference point.

20. The computer program product as set forth in claim 19, wherein evaluating the output neurons further comprises operations of:

comparing values of the output neurons against a threshold, such that if an output neuron reaches its threshold, the output neuron fires, indicating a match between the template and test array;

obtaining an x-axis location as a time-step in which the output neuron fired; and

obtaining a y-axis location from an index of the output neuron.

21. The computer program product as set forth in claim 20, wherein in receiving the neural inputs into a template neural network to generate output neurons, the neural input is fed forward to the output neurons through delayed connections.

22. The computer program product as set forth in claim 17, wherein evaluating the output neurons further comprises operations of:

comparing values of the output neurons against a threshold, such that if an output neuron reaches its threshold, the output neuron fires, indicating a match between the template and test array;

obtaining an x-axis location as a time-step in which the output neuron fired; and

obtaining a y-axis location from an index of the output neuron.

23. The computer program product as set firth in claim 17, wherein in receiving the neural inputs into a template neural network to generate output neurons, the neural input is fed forward to the output neurons through delayed connections.

24. The computer program product as set forth in claim 17, wherein the test array is a test image.