Process and apparatus for the automatic detection and extraction of features in images and displays

• US 4,906,940 A
• Filed: 02/13/1989
• Issued: 03/06/1990
• Est. Priority Date: 08/24/1987
• Status: Expired due to Term

• Current Assignee: Science Applications International Corporation
• Original Assignee: Science Applications International Corporation
• Inventors: Greene, Robert R., Weyker, Robert R., West, Karen F.
• Primary Examiner(s): Blum, Theodore M.
• Application Number:
  US07/310,490
• Time in Patent Office: 386 Days
• Field of Search: 382/16, 382/30, 382/33
• US Class Current: 382/100
• CPC Class Codes: G06T 2207/10044 Radar image
• CPC Class Codes: G06T 2207/10116 X-ray image
• CPC Class Codes: G06T 2207/20056 Discrete and fast Fourier transform, [DFT, FFT]
• CPC Class Codes: G06T 2207/30212 Military
• CPC Class Codes: G06T 7/12 Edge-based segmentation
• CPC Class Codes: G06V 10/443 by matching or filtering
• CPC Class Codes: G06V 10/754 involving a deformation of the sample pattern or of the reference pattern; Elastic matching
• CPC Class Codes: G06V 20/176 Urban or other man-made structures
• CPC Class Codes: G06V 20/588 Recognition of the road, e.g. of lane markings; Recognition of the vehicle driving pattern in relation to the road

Abstract

A pattern recognition process and apparatus automatically extracts features in displays, images, and complex signals. Complex signals are processed to two- or higher-dimensional displays or other imagery. The displays or other imagery are then processed to produce one or more visual fields in which regions with certain properties are enhanced. The enchanced regions are induced to produce attractive forces. Flexible templates placed in the visual fields are acted upon by the attractive forces, causing the templates to deform in such a way as to match features which are similar, but not identical to, the template. The deformed templates are then evaluated in order to identify or interpret the feature to which the template was attracted. Apparatus utilizing the process generates a display of the features extracted from the input signal. Desired information can be obtained from such a display, such as trajectories, the location of ridges, buildings, edges, or other boundaries. The extracted features can be used within a control system to automatically guide an object, such as a vehicle or airplane, along a desired course; or within a signal processing system to provide a display of the features in a way that aids in the interpretation of such features.

Claims

1. A method of extracting features from source signals, such as image signals, display signals, and similar complex signals, comprising the steps of:

(a) producing a display field of said source signal having two or more dimensions;

(b) generating a force field around areas of said display field having selected properties, such as those areas having a prescribed intensity;

(c) placing at least one movable and deformable template in the display field that is acted upon by said force field; and

(d) evaluating at least one characteristic of said template after said template has been acted upon by said force field, said force field causing said template to move and/or deform in response to the forces present within said force field, said at least one characteristic providing an indication of a feature present within said source signal.

2. The method of extracting features from source signals of claim 1 wherein the display-field production of step (a) comprises producing a visual display and enhancing selected features of the display.

3. The method of extracting features from source signals of claim 2 wherein the step of producing a visual display comprises generating an array of pixels, each pixel being assigned a brightness level as a function of the source signal being displayed.

4. The method of extracting features from source signals of claim 3 wherein the step of enhancing features of the display comprises enhancing edges appearing within the display to make them appear as highlighted linear tracks.

5. The method of extracting features from source signals of claim 4 wherein the step of enhancing features of the display further comprises enhancing boundaries of regions of homogeneous texture within said display.

6. The method of extracting features from source signals of claim 1 wherein the force-field generation of step (b) comprises generating an attractive force field around the selected features of the display field, whereby a movable object, such as a template, placed within said display field is attracted towards the selected features in accordance with the governing principles of the force field.

7. The method of extracting features from source signals of claim 6 wherein the step of generating an attractive force field comprises treating the display field as a field of compressible fluid or gas and assigning each selected feature within the display field as a low pressure region, whereby a movable object, such as a template, placed within the display field flows towards the selected feature according to known principles of fluid flow dynamics.

8. The method of extracting features from source signals of claim 6 wherein the step of generating an attractive force field comprises treating the display field as a potential field and assigning each selected feature within the display field a potential value, whereby movable objects, such as a template, placed within the display field are attracted to the selected feature according to known principles of potential fields.

9. The method extracting features from source signals of claim 8 wherein the step of treating the display field as a potential field comprises treating the display field as a distribution of mass field wherein each selected feature within the display field is assigned a mass value, whereby a movable object having an assigned mass value, placed in the display field, such as a template, is attracted towards the selected features in accordance with known principles of physical dynamics.

10. The method of extracting features from source signals of claim 8 wherein the step of treating the display field as a potential field comprises treating the display field as an electric field and assigning each selected feature within the display field an electric charge value of one polarity, whereby an object having an electric charge value of an opposite polarity, such as a template, placed within the display field is attracted towards the selected feature according to known principles of electric dynamics.

11. The method extracting features from source signals of claim 1 wherein step (c) of placing movable templates within said display field comprises:

defining a template having desired characteristics, including the ability to bend and deform to a desired degree;

placing at least one such defined template in the display field provided in step (a) so that it can be acted upon by at least one of the force fields generated in step (b), and

allowing the force field to act upon the placed template until the template is within a specified closeness of a match with the selected features of the source signal.

12. The method of extracting features from source signals of claim 11 wherein the step of allowing the force field to act upon the placed template comprises allowing the template to converge to an asymptotic state, said asymptotic state comprising a state wherein said template has been finally acted upon by said force field, said asymptotic state providing a hypothetical location, orientation, and shape of the feature in the display field towards which the template was attracted.

13. The method of extracting features from source signals of claim 12 wherein the step of defining the template to have desired characteristics includes assigning the template to have a desired dimensionality, such as a one dimensional line, a two dimensional rectangle, or a three dimensional sphere.

14. The method of extracting features from source signals of claim 12 wherein the step of defining the template to have desired characteristic includes assigning the template to have a desired topology, including the shape of the template, the number of holes in the template, and the number of separate pieces in the template.

15. The method of extracting features from source signals of claim 12 wherein the step of defining the template to have desired characteristics includes assigning the template to have a desired number of degrees of freedom.

16. The method of extracting features from source signals of claim 12 wherein the step of defining the template to have desired characteristics includes assigning the template to have desired dynamics, including the manner and degree to which the template can bend, deform, flex, and otherwise respond to forces applied thereto.

17. The method of extracting features from source signals of claim 1 wherein the evaluation of the template carried out in step (d) comprises:

considering the asymptotic state of each template as a hypothetical location, orientation, and shape for a feature within the display field, and

deciding whether to accept or reject said hypothetical location, orientation, and shape (the hypothesis) as the extracted feature of the source signal.

18. The method of extracting features from source signals of claim 17 wherein the step of accepting/rejecting the hypothesis comprises testing the parameters characterizing said template and rejecting the hypothesis if these parameters lie outside certain prescribed bounds.

19. The method of extracting features from source signals of claim 17 wherein the step of accepting/rejecting the hypothesis comprises testing the properties of the display field near at least one portion of the template and accepting the hypothesis if these properties lie within certain prescribed bounds.

20. The method of extracting features from source signals of claim 1 wherein step (c) comprises placing a prescribed number of templates in the force field and wherein step (d) comprises determining whether a prescribed number of said templates have clustered around a given point in the display field, and if so, accepting the presence of a feature at said point.

21. The method of extracting features from source signals of claim 1 wherein step (c) includes assigning a potential energy value to a template as it is placed in the display field at its initial position;

and step (d) comprises measuring the decrease in the potential energy after the template has moved within the display as a result of being acted upon by the force field, and accepting a hypothesis concerning the location, orientation and shape of a feature in the display field if the potential energy has fallen by more than a specified amount.

56. The method of claim 1 wherein the step of generating a force field comprises generating a second order force filed around areas of the display field having selected properties, said second order force field containing forces that are deformed by a second-order differential equation.

57. The method of claim 6 wherein the force-field generation of step (b) comprises generating a second order attractive force field around selected features of the display field, whereby a movable object, such as a template, placed within said display field is attracted towards the selected features in accordance with the governing second-order principles of the force field.

58. The method of extracting features from source signals of claim 57 wherein the step of generating a second order attractive force field comprises treating the display field as a field of compressible fluid or gas and assigning each selected feature within the display field as a low pressure region, whereby a movable object, such as a template, placed within the display field flows towards the selected feature according to known second order principles of fluid flow dynamics.

59. The method of extracting features from source signals of claim 57 wherein the step of generating a second order attractive force field comprises treating the display field as a potential field described by a second order differential equation and assigning each selected feature within the display field a potential value, whereby movable object, such as a template, placed within the display field are attracted to the selected feature according to known second order principles of potential fields.

60. The method of extracting features from source signals of claim 58 wherein the step of treating the display field as a potential field comprises treating the display field as a distribution of mass field wherein each selected feature within the display field is assigned a mass value, whereby a movable object having as assigned mass value, placed in the display field, such as a template, is attracted towards the selected features in accordance with known second-order principles of physical dynamics.

61. The method of extracting features from source signals of claim 8 wherein the step of treating the dislay field as a potential field comprises treating the display field as an electric field and assigning each selected feature within the display field an electric charge value of one polarity, whereby an object having an electric charge value of an opposite polarity, such as a template, placed within the display field is attracted toward the selected feature according to known second order principles of electric dynamics.

22. A method for classifying features from a display having two or more dimensions comprising the steps of:

(a) generating a force field around areas within said display field having selected properties;

(b) defining a movable and deformable template having desired initial characteristics;

(c) placing said template within said display field;

(d) allowing said template to move and deform within said display in response to being acted upon by said force field; and

(e) evaluating at least one final characteristic of said template after said template has moved to a final state and assumed a final shape as a result of being acted upon by said force field; and

(f) classifying a feature present in the display field as a function of the evaluated final characteristic of said template.

62. The method for classifying features of claim 22 wherein step (a) comprises generating a second order force field around areas within said display field having selected properties, said second-order force field having forces defined by a second order differential equation.

23. A method of identifying features in a display field, said display field comprising a two or more dimensional array of a complex signal, said method comprising the steps of:

(a) generating a force field around areas within said display field having selected characteristics;

(b) placing a movable and flexible template within said display field that moves and flexes in response to said force field; and

(c) evaluating at least one characteristic of said template after it has moved and flexed as a result of being acted upon by said force field, said evaluated characteristic providing an indication of the identity of selected features within said display field.

63. The method of identifying features of claim 23 wherein step (a) comprises generating a second order force field around areas within said display field having selected characteristics, said second order force field having forces that are defined by a second order differential equation.

24. A method of interpreting a complex signal comprising the steps of:

(a) generating at least one display field of two or more dimensions that display said complex signal;

(b) enhancing selected portions of said display field;

(c) generating a force field around said selected enhanced portions;

(d) defining at least one movable template having desired characteristics, such as a flexible stick, and placing said template within said display field so that it is acted upon by said force field for a prescribed time period; and

(e) evaluating at least one characteristic of said template at the conclusion of said time period, said evaluated characteristic providing information relative to the interpretation of said complex signal.

25. The interpretation method of claim 24 wherein the prescribed time period of step (d) is determined by waiting until after the template has settled to a final state as a result of being acted upon by said force field.

64. The interpretation method of claim 24 wherein step (c) comprises generating a second order force field around said selected enhanced portions, said second order force field having forces therein that are defined by at least a second order differential equation.

26. A control system comprising:

an element to be controlled that is responsive to a control signal;

receiving means for receiving at least one input signal;

feature-extraction means for extracting at least one specified feature from said input signal, said feature extraction means including

display-field generating means for generating at least one display field of at least two dimensions of said input signal,

force-field generating means for generating a force field surrounding selected portions of said display field,

template means for placing at least one movable and deformable template in said display field that is acted upon by said force field, and

evaluating means for evaluating said at least one movable and deformable template after it has been acted upon by said force field, the location, orientation and shape of said template providing an indication that a feature is present within said display field having a similar location, orientation and shape, said identified feature being extracted from said display field; and

control means responsive to the feature extracted by said feature extraction means for generating said control signal;

whereby the element of said control system that is controlled in response to said control signal is controlled as a function of the extracted feature from said input signal.

27. The control system of claim 26 wherein said control system comprises a wheeled vehicle, said receiving means includes a video camera attached to said vehicle that generates a video signal as a result of an optical image presented thereto, said feature-extraction means comprises a computer on-board said vehicle that extracts the edges of a road from the video signal generated by said video camera, and said control means includes means for moving and steering said vehicle so that it follows said road.

28. The control system of claim 27 wherein said control means includes:

means for calculating the center of the road as half-way between the edges of the road;

means for moving the vehicle forward along the center of the road; and

means for adjusting the video camera so that it is pointed at the center of the road in front of the vehicle.

29. The control system of claim 27 wherein the display-field generating means of said feature-extraction means includes:

means for processing the video signal using a Sobel edge detector;

means for normalizing the Sobel-processed image; and

means for calculating a visual field display from the normalized Sobel image.

30. The control system of claim 29 wherein said visual field display comprises a matrix of pixels, each pixel having an intensity level associated therewith that varies as a function of the received video signal;

and further wherein the force-field generating means of said feature-extraction means includes means for treating said matrix of pixels as a fluid flow field wherein pixels having a prescribed intensity within said display field are assigned a low pressure value; and

still further wherein said template means includes means for allowing a template placed in said fluid-flow field to move within said fluid-flow field in response to forces created by said low pressure values.

31. The control system of claim 30 wherein said template placed in said fluid-flow field by said template means comprises a non-rigid template that can flex and deform in response to the flow forces created within said fluid-flow field.

32. The control system of claim 31 wherein said template comprises a pair of flexible rods.

33. The control system of claim 32 wherein each of the flexible rods of said pair of flexible rods includes repeller means for repelling each of said rods from the other of said rods as said rods are moved by said force field within said visual field display, thereby preventing said rods from converging to the same location within said visual display field.

34. The control system of claim 26 wherein said control system comprises an aircraft;

said receiving means includes sensing means mounted on said aircraft for receiving an input signal from the area in front of and below said aircraft and for generating a sensor signal in response thereto;

said feature-extraction means includes signal processing means on-board said aircraft for extracting linear features, such as roads and rivers, from said sensor signal; and

said control means includes means for guiding said aircraft so that it follows said linear features.

35. The control system of claim 34 wherein said receiving means further includes means for photographing and recording optical images observed from said aircraft;

and wherein said signal processing means further includes means for extracting rectangular features, such as buildings, from the optical images photographed and recorded by said receiving means.

65. The control system of claim 26 wherein said force-field generating means of said feature-extraction means comprises means for generating a second order force field surrounding selected portions of said display field, the forces generated by said second order force field being defined by at least one second order differential equation.

36. A signal processing system for interpreting an input signal comprising:

receiving means for receiving at least one input signal;

feature-extraction means for extracting desired features from said input signal, said feature extraction means including;

display-field generating means responsive to said input signal for generating at least one display field of said input signal having at least two dimensions,

force-field generating means for generating a force field surrounding selected properties of said display field,

template means for placing at least one movable template in said display field and for allowing said template to move within said display field in response to said force field, and

evaluating means for identifying those features within said input signal that are to be extracted, said evaluating means including means for determining at least the position of said movable template after said template has been acted upon by said force field, said determined position providing an indication of those features within said display field that are to be extracted; and

display means for extracting the identified features from the display field and for displaying said extracted features, said display of extracted features providing an interpretation of said signal.

37. The signal processing system of claim 36 wherein said receiving means includes a plurality of sensors for receiving input signals from a moving noise source, said feature-extraction means comprises processing means that includes said display-field generating means, force-field generating means, template means, and evaluating means;

and wherein said display means includes a detection display whereon a trajectory of the moving noise source is displayed;

said signal processing system thereby comprising a multichannel warped signal correlator system.

38. The signal processing system of claim 37 wherein said display-field generating means includes:

(1) means for dividing the input signals from each sensor into n sub-series, (2) means for generating a preliminary visual field by calculating the cross correlation of corresponding pairs of sub-series from the divided signals from each sensor, (3) means for normalizing the preliminary visual field thus formed, and (4) means for calculating the display field from said normalized preliminary visual field.

39. The signal processing system of claim 38 wherein said display field comprises a matrix of pixels, each pixel having an intensity level associated therewith that varies as a function of the received input signal;

and further wherein the force-field generating means of said feature-extraction means includes means for treating said matrix of pixels as a fluid-flow field wherein pixels having a prescribed intensity within said display field are assigned a low pressure value; and

still further wherein said template means includes means for allowing a template placed in said fluid-flow field to move within said fluid-flow field in response to forces created by said assigned low pressure values.

40. The signal processing system of claim 39 wherein said template placed in said fluid-flow field comprises a flexible rod having prescribed characteristics.

41. The signal processing system of claim 40 wherein said template comprises a pair of flexible rods, each of said flexible rods having repeller means for repelling each flexible rod from the other flexible rod, thereby preventing said rods from converging to the same location within said display field.

42. The signal processing system of claim 36 wherein said receiving means comprises means for providing a digital imagery signal, said input signal comprising an optical signal from which said digital imagery signal is derived, and said feature extraction means comprises digital processing means for extracting rectangles from said digital imagery signal;

said display means thereby displaying the extracted rectangles.

43. The signal processing system of claim 42 wherein the display-field generating means of said feature extraction means comprises means for producing first and second visual fields from the initial digital imagery signal, said first visual field being produced so as to enhance regions of uniform intensity, and said second visual field being produced from said first visual field so as to enhance the edges around the regions of uniform intensity.

44. The signal processing system of claim 43 wherein the force-field generating means of said feature-extraction means includes means for calculating an attractive force field within each of said first and second visual fields, said calculation being based on the solution of the equations for a compressible fluid flow.

45. The signal processing system of claim 44 wherein the calculating means carries out the solution of the fluid flow equations using a two-step finite difference solution technique.

46. The signal processing system of claim 44 wherein the template means of said feature-extraction means comprises means for placing a plurality of rectangular templates within said first and second visual fields and allowing said templates to change shape, orientation, and size within said first and second visual fields as said templates are acted upon by the forces of said attractive force field.

47. The signal processing system of claim 46 further including repeller means for repelling each of said plurality of rectangular templates from the others of said rectangular templates as said rectangular templates are acted upon by the forces of said attractive force field, thereby preventing said templates from converging to the same location within said display field.

48. The signal processing system of claim 46 wherein the evaluating means of said feature extraction means includes means for testing the regions within said first visual field that are surrounded by said templates, after said templates have reached an asymptotic state, to determine if said regions are homogeneous, said asymptotic state comprising that state wherein said templates have finished moving in response to said attractive force field;

and by further testing the pixels within the second visual field that are close to the edges of the rectangular templates that have also reached an asymptotic state to determine if a prescribed percentage of said pixels are edged enhanced pixles.

49. The signal processing system of claim 36 wherein said receiving means receives an input signal comprising seismic data and includes means for forming a common depth point display therefrom;

and said feature-extraction means extracts features from said seismic data signal representative of the shape of the curves formed by the locus of reflections in the common depth point display, said signal processing system thereby serving as a common depth point interpretation station.

50. The signal processing system of claim 36 wherein said receiving means receives an input signal comprising a zero offset signal obtained from seismic data, and said feature extraction means extracts features from said zero offset signal indicative of the locus of reflections from a given reflecting interface, said signal processing system thereby functioning as a seismic trace interpretation station.

51. The signal processing system of claim 36 wherein said receiving means receives a reflected input signal from a moving target, such as occurs in a radar system, and said feature-extraction means extracts the trajectory of the reflected signals over time based on a collection of input signals, and further wherein said display means displays said trajectory in a multi-dimensional display, said signal processing system thereby functioning as a multi-screen track detection system.

52. The signal processing system of claim 36 wherein said receiving means receives a voice signal from a person to be identified, said feature-extraction means includes means for extracting features, if any, from said voice signal that are unique to a particular individual, and said display means includes means for signaling whether any unique features for said particular individual were extracted from said voice signal.

66. The signal processing system of claim 36 wherein the force-field generating means of said feature-extraction means comprises means for generating a second order force field that surrounds selected properties of the display field, said second order force field having forces associated therewith that are defined at least one second order differential equation.

53. A system for interpeting a complex signal comprising:

means for receiving said complex signal;

means for displaying said complex signal in a display field having at least two dimensions;

means for enhancing areas of said display field having prescribed properties;

means for generating a force field around at least one of said enhanced areas;

means for placing a template having desired characteristics within said display field so that it is acted upon by said force field until a prescribed event occurs;

means for determining the occurrence of said prescribed event;

means for evaluating said template to determine its location orientation, and shape within said display field after the occurence of said prescribed event, which information provides an indication of the location, orientation and shape of a feature within said display field, and hence within said complex signal;

the presence of said feature within said complex signal providing an aid to the interpretation of said complex signal.

54. The complex signal interpreting system of claim 53 wherein said prescribed event comprises the convergence of said template to a final position within said display field as a result of being acted upon by said force field.

55. The complex signal interpreting system of claim 53 wherein said prescribed event comprises the elapse of a prescribed time period.

67. The complex signal interpreting system of claim 53 wherein said means for generating a force field around at least one of said enhanced areas comprises means for generating a second order force field that generates forces as defined by at least a second order differential equation.