Pattern recognition apparatus utilizing area linking and region growth techniques

• US 5,093,869 A
• Filed: 12/26/1990
• Issued: 03/03/1992
• Est. Priority Date: 12/26/1990
• Status: Expired due to Term

• Current Assignee: Raytheon Company (Rtx Corporation)
• Original Assignee: Hughes Aircraft Company (Rtx Corporation)
• Inventors: Alves, James F., Daniels, Michele K., Berger, Bruce A., Birdsall, Brian J., Tackett, Walter W., Gor, Victoria, Reinhart, Craig C., Burman, Jerry A.
• Primary Examiner(s): Boudreau, Leo H.
• Assistant Examiner(s): Stellrecht, Barry
• Application Number:
  US07/633,833
• Time in Patent Office: 433 Days
• Field of Search: 382/5, 382/22, 382/37
• US Class Current: 382/199
• CPC Class Codes: G06V 10/426 Graphical representations

Abstract

Image data is processed by a low level feature detection processor that extracts low level features from an image. This is accomplished by converting a matrix of image data into a matrix of orthogonal icons that symbolically represent the image scene using a predetermined set of attributes. The orthogonal icons serve as the basis of processing by means of a high level graph matching processor which employs symbolic scene segmentation, description, and recognition processing that is performed subsequent to the low level feature detection. This processing generates attribute graphs representative of target objects present in the image scene. High level graph matching compares predetermined attributed reference graphs to the sensed graphs to produce a best common subgraph between the two based on the degree of similarity between the two graphs. The high level graph matching generates a recognition decision based on the value of the degree of similarity and a predetermined threshold. The output of the high level graph matching provides data from which a target aimpoint is determined, and this aimpoint is coupled as an input to a missile guidance system that tracks identified targets.

Claims

1. A scene recognition system employing low and high level detection to identify and track targets located in an image scene and a missile guidance system adapted to steer a missile toward a desired target, said system comprising:

low level feature detection processor means for processing image data derived from and representative of an imaged scene, and for extracting features from the imaged scene by converting the image data into a matrix of orthogonal icons that symbolically represent the image using a predetermined set of attributes, said low level feature detection processor means comprising;

a) flat linking processing means for forming groups of orthogonal icons having homogeneous intensity regions to generate a set of regions having a block resolution boundary and that are comprised of homogeneous intensity icons described by their area, comprising the number of constituent icons having homogeneous intensity, the intensity, comprising the average intensity of the constituent homogeneous intensity icons, and a list of the constituent homogeneous intensity icons; and

b) region growth processing means coupled to the flat linking processing means for appending adjacent orthogonal icons having an intensity gradient thereacross to provide a feature-resolution boundary;

graph synthesis processor means coupled to the low level feature detection processing means for processing the orthogonal icons to generate predetermined objects representative of objects that are in the scene, and for computing relational descriptions between the objects to form an attributed sensed graph from the objects and their relationships as described by their attributes, and whereupon the objects are placed at graph nodes, one object per node, along with their descriptive attributes, and wherein the relationships between object pairs are placed at graph links along with their attributes, and whereupon a fully connected attributed graph is formulated which symbolically represents the image scene;

reference graph storage means coupled to the graph synthesis processing means for storing predetermined reference graphs representative of identifiable targets of interest that are expected to be present in the data comprising the image; and

graph matching processing means coupled to the graph synthesis processing means for comparing predetermined attributed reference graphs to the sensed graphs to produce an object recognition decision based on the value of the degree of similarity between the attributed reference graphs to the sensed graphs and a predetermined threshold, and for providing an output signal that is determinative of a target aimpoint, which output signal is coupled as an input to the missile guidance system to provide a guidance signal that is adapted to steer the missile toward the identified target.

2. The system of claim 1 wherein the low level feature detection processing means further comprises:

boundary formation and linear feature extraction processing means coupled to the region growth processing means for (1) traversing the gradient boundaries of each region to form a gradient chain around each region, (2) analyzing the gradient chains for each region for linear segments by means of pointers inserted into the chains at the beginning and end of each linear segment, and (3) analyzing the linear segments for the joining of segments related to two or more regions to form linear segments, which generates boundary descriptions for each of the regions formulated by the flat linking and region growth processing means and linear segments represented by length, orientation, and end point coordinates.

3. The system of claim 2 wherein the low level feature detection processing means further comprises:

object formation processing means coupled to the boundary formation and linear feature extraction processing means for forming ribbon objects from the linear features provided by the gradient boundary and linear feature extraction processing means and for creating symbolic descriptions of these objects, by creating symbolic descriptions of the regions provided by the flat linking and region growing processing means to produce region objects that define nodes of an attributed sensed graph, and whose symbolic descriptions comprise the attributes;

whereby for region objects, the object formation processing means computes the area, perimeter, and convex hull attributes, and for the ribbon objects, the object formation processing means searches through a line table looking for pairs of lines that;

(1) differ in orientation by 180 degrees, (2) are in close proximity to each other, (3) are flanked by similar intensities, (4) do not enclose another line segment that is parallel to either line, and when a pair of lines fitting these constraints is found the ribbon attributes for them are computed, and wherein the attributes for ribbon objects include;

(1) intensity of the ribbon, (2) polarity of the ribbon, meaning light on dark or dark on light, (3) the width of the ribbon, meaning the distance between the two lines, and (4) the orientation of the ribbon.

4. The system of claim 3 wherein the graph matching processing means compares predetermined attributed reference graphs to the sensed graphs to produce a best common subgraph between the two based on the degree of similarity between the two graphs, and generates a recognition decision based on the value of the degree of similarity and a predetermined threshold.

5. The system of claim 4 wherein the graph matching processing means utilizes a heuristically directed depth-first search technique to evaluate feasible matches between nodes and arc attributes of the attributed reference and sensed graphs.

6. The system of claim 5 wherein the graph matching processing means determines feasibility by the degree of match between the node and arc attributes of each of the graphs, and a heuristic procedure is included to ignore paths that cannot produce a degree of similarity larger than the predetermined threshold.

7. The system of claim 6 wherein the paths which lead to ambiguous solutions, comprising solutions that match a single object in one graph to multiple objects in the other, are ignored, and wherein paths that do not preserve the spatial relationships between the objects as they appeared in the image are ignored.

8. A scene recognition system employing low and high level feature detection to identify and track targets located in an imaged scene and a missile guidance system adapted to steer the missile toward a desired target, said system comprising:

low level feature detection processing means adapted to process image data derived from and representative of an image scene, for extracting low level features from the image by converting the image data into a matrix of orthogonal icons that symbolically represent the image scene using a predetermined set of attributes;

graph synthesis processing means coupled to the low level feature detection processing means processing the orthogonal icons and for computing relational descriptions between the region and ribbon objects provided by the object formation processing means to form the attributed sensed graph from the region and ribbon objects and their relationships, and whereupon the region and ribbon objects are placed at graph nodes, one object per node, along with their descriptive attributes, the relationships between each pair of objects are placed at the graph links along with their attributes, whereupon, a fully connected attributed graph is formulated which symbolically represents the image;

reference graph storage means coupled to the graph synthesis processing means for storing predetermined reference graphs representative of identifiable targets of interest that are expected to be present in the data comprising the image; and

graph matching processing means coupled to the graph synthesis processing means for comparing predetermined attributed reference graphs to the sensed graphs to produce an object recognition decision, which produces a best common subgraph between the two based on the degree of similarity between the two graphs, for generating a recognition decision based on the value of the degree of similarity and a predetermined threshold, and for providing an output signal that is determinative of a target aimpoint, which output signal is coupled as an input to the missile guidance system to provide a guidance signal that is adapted to steer the missile toward the identified target.

9. A scene recognition system employing low and high level feature detection to identify and track targets located in an image scene, said system comprising:

low level feature detection processing means adapted to process image data derived from and representative of an image scene, for extracting low level features from the image scene by converting the image data into a matrix of orthogonal icons that symbolically represent the image using a predetermined set of attributes;

flat linking processing means coupled to the low level feature detection processing means for forming groups of orthogonal icons having homogeneous intensity regions by means of a relaxation-based algorithm to generate a set of regions having a block resolution boundary and that are comprised of homogeneous intensity icons described by their area, comprising the number of constituent icons having homogeneous intensity, the intensity, comprising the average intensity of the constituent homogeneous intensity icons, and a list of the constituent homogeneous intensity icons;

region growth processing means coupled to the flat linking processing means for appending adjacent orthogonal icons having an intensity gradient thereacross to provide a feature-resolution boundary;

boundary formation and linear feature extraction processing means coupled to the region growth processing means for (1) traversing the gradient boundaries of each region to form a gradient chain around each region, (2) analyzing the gradient chains for each region for linear segments by means of pointers inserted into the chains at the beginning and end of each linear segment, and (3) analyzing the linear segments for the joining of segments related to two or more regions to form linear segments, which generates boundary descriptions for each of the regions formulated by the flat linking and region growth processing means and linear segments represented by length, orientation, and end point coordinates;

object formation processing means coupled to the boundary formation and linear feature extraction processing means for forming ribbon objects from the linear features provided by the gradient boundary and linear feature extraction processing means and for creating symbolic descriptions of these objects, by creating symbolic descriptions of the regions provided by the flat linking and region growing processing means to produce region objects that define nodes of an attributed sensed graph, and whose symbolic desctiptions comprise the attributes;

whereby for region objects, the object formation processing means computes the area, perimeter, and convex hull attributes, and for the ribbon objects, the object formation processing means searches through a line table looking for pairs of lines that;

(1) differ in orientation by 180 degrees, (2) are in close proximity to each other, (3) are flanked by similar intensities, (4) do not enclose another line segment that is parallel to either line, and when a pair of lines fitting these constraints is found the ribbon attributes for them are computed, and wherein the attributes for ribbon objects include;

(1) intensity of the ribbon, (2) polarity of the ribbon, meaning light on dark or dark on light, (3) the width of the ribbon, meaning the distance between the two lines, and (4) the orientation of the ribbon;

graph synthesis processing means coupled to the low level feature detection processing means processing the orthogonal icons and for computing relational descriptions between the region and ribbon objects provided by the object formation processing means to form the attributed sensed graph from the region and ribbon objects and their relationships, and whereupon the region and ribbon objects are placed at graph nodes, one object per node, along with their descriptive attributes, the relationships between each pair of objects are placed at the graph links along with their attributes, whereupon, a fully connected attributed graph is formulated which symbolically represents the imaged scene;

reference graph storage means coupled to the graph synthesis processing means for storing predetermined reference graphs representative of identifiable targets of interest that are expected to be present in the data comprising the image scene; and

graph matching processing means coupled to the graph synthesis processing means for comparing predetermined attributed reference graphs to the sensed graphs to produce a best common subgraph between the two based on the degree of similarity between the two graphs, and for generating a recognition decision based on the value of the degree of similarity and a predetermined threshold, and wherein the graph matching processing means utilizes a heuristically directed depth-first search technique to evaluate feasible matches between the nodes and arcs of the attributed reference and sensed graphs, wherein feasibility is determined by the degree of match between the node and arc attributes of each of the graphs, and a heuristic procedure is included to ignore paths of the tree that cannot possibly produce a degree of similarity larger than the predetermined threshold, and wherein the paths of the tree which lead to ambiguous solutions, wherein solutions that match a single object in one graph to multiple objects in the other, are ignored, and wherein paths of the tree that do not preserve the spatial relationships between the objects as they appeared in the original scene are ignored.

10. A method for use with a missile guidance system to track targets located in an imaged scene, said method comprising the steps of:

processing image data derived from and representative of an imaged scene to form groups of orthogonal icons, having homogeneous intensity regions, by means of a relaxation-based algorithm to generate a set of regions having a block resolution boundary and that are comprised of homogeneous intensity icons described by their area, comprising the number of constituent icons having homogeneous intensity, the intensity comprising the average intensity of the constituent homogeneous intensity icons, and a list of the constituent homogeneous intensity icons;

appending adjacent orthogonal icons having an intensity gradient thereacross to provide a feature-resolution boundary;

processing the orthogonal icons to form an attributed sensed graph from region and ribbon objects comprising the orthogonal icons and their relationships, and whereupon the region and ribbon objects are placed at graph nodes, one object per node, along with their descriptive attributes, the relationships between each pair of objects are placed at the graph links along with their attributes, whereupon, a fully connected attributed graph is formulated which symbolically represents the image scene;

storing predetermined reference graphs representative of identifiable targets of interest that are expected to be present in the data comprising the image scene; and

comparing predetermined reference graphs to the attributed sensed graphs to produce an object recognition decision, and providing an output signal that is determinative of a target aimpoint, which output signal is coupled as an input to the missile guidance system to provide a guidance signal that is adapted to steer a missile toward the identified target.

11. The method of claim 10 wherein the step of processing image data comprises:

forming regions by (1) traversing the gradient boundaries of each region to form a gradient chain around each region, (2) analyzing the gradient chains for each region for linear segments by means of pointers inserted into the chains at the beginning and end of each linear segment, and (3) analyzing the linear segments for the joining of segments related to two or more regions to form linear segments, which generates boudary descriptions for each of the regions formulated by the flat linking and region growth processing means and linear segments represented by length, orientation, and end point coordinates.

12. The method of claim 11 wherein the step of processing image data comprises:

forming ribbon objects from the linear features provided by the gradient boundary and linear feature extraction processing step and for creating symbolic descriptions of these objects, by creating symbolic descriptions of the regions provided by the flat linking and region growing processing means to produce region objects that define nodes of an attributed sensed graph, and whose symbolic descriptions comprise the attributes;

whereby for region objects, the area, perimeter, and convex hull attributes are determined, and for the ribbon objects, a line table is searched looking for pairs of lines that;

(1) differ in orientation by 180 degrees, (2) are in close proximity to each other, (3) are flanked by similar intensities, (4) do not enclose another line segment that is parallel to either line, and when a pair of lines fitting these constraints is found the ribbon attributes for then are computed, and wherein the attributes for ribbon objects include;

(1) intensity of the ribbon, (2) polarity of the Ribbon, meaning light on dark or dark on light, (3) the width of the ribbon, meaning the distance between the two lines, and (4) the orientation of the ribbon.

13. The method of claim 12 wherein the comparing step comprises comparing predetermined reference graphs to the attributed sensed graphs based on the value that is a function of the difference between the degree of similarity between the reference and sensed graphs, and a predetermined threshold.

14. The method of claim 13 wherein the comparing step utilizes a heuristically directed depth-first search technique to evaluate feasible matches between nodes and arcs of the attributed reference and sensed graphs.

15. The method of claim 14 wherein the comparing step determines feasibility by the degree of match between the node and arc attributes of each of the graphs, and a heuristic procedure is included to ignore paths that cannot produce a degree of similarity larger than the predetermined threshold.

16. The method of claim 15 wherein the paths which lead to ambiguous solutions, comprising solutions that match a single object in one graph to multiple objects in the other, are ignored, and wherein paths that do not preserve the spatial relationships between the objects as they appeared in the image scene are ignored.