Method and apparatus for pattern recognition and detection

• US 4,414,685 A
• Filed: 05/29/1981
• Issued: 11/08/1983
• Est. Priority Date: 09/10/1979
• Status: Expired due to Term

• Current Assignee: Stanley R. Sternberg
• Original Assignee: Stanley R. Sternberg
• Inventors: Sternberg, Stanley R.
• Primary Examiner(s): Boudreau, Leo H.
• Application Number:
  US06/268,608
• Time in Patent Office: 893 Days
• Field of Search: 340/146.3 MA, 340/146.3 H, 340/146.3 AC, 340/146.3 AG, 340/146.3 Y, 340/146.3 R, 364/515, 364/725, 382/27, 382/49
• US Class Current: 382/257
• CPC Class Codes: G06T 5/20 using local operators
• CPC Class Codes: G06V 10/34 Smoothing or thinning of the pattern; Morphological operations; Skeletonisation
• CPC Class Codes: G06V 10/36 Applying a local operator, i.e. means to operate on image points situated in the vicinity of a given point; Non-linear local filtering operations, e.g. median filtering

Abstract

Image analyzing apparatus and methods are disclosed for analyzing 3-dimensional as well as 2-dimensional images. The pixels of the 3-D images may be represented by multivalued digital data signals which are analyzed in one or more programmable neighborhood transformation stages. In the preferred embodiment, each stage is programmed with selected contribution values associated with each pixel in the neighborhood. The values of the data signals for each pixel are modified by these contribution values and the maximum value thereof is selected as the transformation output of the stage. A series of dilation/erosion transformations may be used to transform the original image matrix in such a manner so as to locate the position and/or identify the shape of particular objects contained in the original image.

Claims

1. A method of detecting patterns in an image consisting of a matrix of multivalued digital data signals, said method comprising:

(a) electronically eroding the image matrix with a structuring element of a particular configuration to form a first transformation matrix;

(b) electronically dilating the first transformation matrix by the same structuring element used in step (a) to form a second transformation matrix; and

(c) comparing said first and second transformation matrices to detect patterns in the original image matrix.

2. A method of detecting patterns in an image consisting of a matrix of multivalued digital data signals, said method comprising:

(a) electronically dilating the image matrix with a structuring element of a particular configuration to form a first transformation matrix;

(b) electronically eroding the first transformation matrix by the same structuring element used in step (a) to form a second transformation matrix; and

(c) comparing said first and second transformation matrices to detect patterns in the original image matrix.

3. A method of detecting patterns of a particular configuration in a three-dimensionally sensed scene represented by a matrix of data points in the form of multivalued digital data signals having values corresponding to the relative distances between points in the scene and a sensor, said method comprising:

(a) electronically eroding the original scene matrix with a structuring element of a particular configuration to form an erosion transformation matrix;

(b) electronically dilating the erosion transformation matrix by the same structuring element used in step (a) to form a ground plane estimated transformation matrix; and

(c) comparing said ground plane estimated matrix with the original scene matrix to form a ground plane normalized matrix to detect the location of the desired object in the original scene.

4. The method of claim 3 which further comprises before the step (a), the further steps of:

forming said structuring element by a series of dilation steps using elemental structuring elements to form a structuring element of the particular configuration; and

storing the elemental structuring elements.

5. The method of claim 4 wherein the erosion step of step (a) is carried out in a chain of substantially identical transformation stages, with each stage eroding the digital data signals of the original matrix with one of the stored elemental structuring elements.

6. The method of claim 5 in which step (b) is carried out in a chian of substantially identical transformation stages, with the digital data signals of the eroded matrix being dilated in each stage by one of the stored elemental structuring elements.

7. The method of claim 6 wherein steps (a) and (b) are performed sequentially in a series chain of substantially identical neighborhood transformation modules utilizing the same sequence of structuring elements except that the logical compliment of the data signals are formed in the stages performing step (b).

8. The method of claim 7 wherein said digital data signals are sequentially loaded into a series of digital storage devices for sequentially accessing substantially all of the neighborhoods in the matrix, each neighborhood comprising a central point and its surrounding points in the matrix, and wherein steps (a) and (b) are performed by operating on the values of the points contained in said storage devices to modify them with contribution values supplied by a central controller and selecting the maximum value thereof for the output of each stage.

9. A method of detecting pattern configurations in a three-dimensional scene represented by stream of multivalued digital data signals having values corresponding to points in a matrix constituting the scene, said method comprising:

(a) repetitively loading said signals into a plurality of storage devices in a transformation stage to sequentially access substantially each neighborhood of points in the matrix, said neighborhood including a central data point and its surrounding points in the matrix;

(b) modifying the values of selected data points in the storage devices to provide new values for particular data points;

(c) comparing the modified data point values to select the maximum value thereof;

(d) supplying said maximum value to a chain of subsequent substantially identical stages;

(e) repeating steps (a)-(d) in said subsequent stages to form a transformed ground plane estimated matrix devoid of the pattern to be detected; and

(f) subtracting in a digital circuit network each data point of the ground plane estimated matrix from each data point in the original scene matrix, with the remaining data points representing the location of the desired pattern configuration in the original scene.

10. A method of analyzing an image having points therein represented by digital data signals, said method comprising:

(a) serially feeding said digital data signals to an input of at least one programmable neighborhood transformation stage;

(b) sequentially accessing a plurality of said signals corresponding to a neighborhood of points in the image, with said neighborhood including a central point and its surrounding points in the image;

(c) programming the stage with contribution values, each contribution value being associated with a point in the neighborhood;

(d) selectively modifying the values of the data signals in the neighborhood with their associated contribution value to form modified digital data signals;

(e) comparing the values of the modified digital data signals; and

(f) providing the maximum value of the signals associated with the neighborhood of points as a transformation output signal for each of the neighborhood of points in the image.

11. The method of claim 10 wherein said digital data signals are provided by measuring the distance between points in a scene from which the image is derived and a reference point, with the value of the signals corresponding to the measured distance.

12. The method of claim 11 wherein said digital data signals are provided from a scanner mounted in aircraft flying over the scene.

13. The method of claim 11 wherein said signals represent 3-dimensional data having values in the range of zero to a value greater than one.

14. The method of claim 13 wherein said digital electrical signals have up to 256 different values.

15. The method of claim 10 which further includes the steps of:

repeating the steps (b)-(f) in a plurality of substantially identical series connected stages, with subsequent stages operating on transformation output signals from preceeding stages.

16. Apparatus for analyzing an image represented by digitial data signals whose values represent characteristics of particular points in the image, said apparatus comprising:

a digital controller, and at least one programmable transformation stage coupled to the controller, said stage including;

neighborhood extraction means for sequentially accessing a plurality of said signals corresponding to a neighborhood including a central point and its surrounding points in the image;

programmable contribution circuit means having means for receiving contribution values from the controller, each contribution value being associated with a given point in the neighborhood, said circuit means further including means for selectively modifying the values of the signals associated with the neighborhood of points with their associated contribution value to form modified digital data signals; and

transformation generator means for comparing the values of the modified digital data signals and selecting extreme values thereof as an output signal of the stage.

17. The apparatus of claim 16 wherein said transformation means selects the highest value of the modified signals.

18. The apparatus of claim 16 which further includes sensor means for measuring the distance between points in a scene from which the image is derived and a reference point, with the digital data signals having more than two permissible values corresponding to the measured distance.

19. The apparatus of claim 18 wherein said sensor means is mounted in an aircraft and provides 8-bit values for the digital data signals.

20. The apparatus of claim 16 wherein said neighborhood extraction means comprises a plurality of series connected latches.

21. The apparatus of claim 20 wherein said contribution means further comprises:

a plurality of adder means, one each coupled to a latch in the neighborhood extraction means; and

means for coupling each adder means to said programmable controller which selectively increments or decrements the neighborhood point values by one.

22. The apparatus of claim 21 wherein said transformation generator means further includes means for coupling the output thereof to the input of another substantially identical stage.

23. Apparatus for analyzing an image represented by multivalued digital data signals having values associated with points in a matrix constituting the image, said apparatus comprising:

a chain of substantially identical neighborhood transformation stages, each stage having a data input for receiving the digital data signals from a preliminary stage, neighborhood extraction means including a plurality of storage devices for temporarily storing values of said data signals associated with a neighborhood in the matrix comprised of a central point and its surrounding points in the matrix, means for loading the data signals into the storage devices to sequentially access substantially all of the neighborhoods in the matrix, a transformation generator portion including neighborhood contribution circuit means coupled to the neighborhood extraction means for operating on the values of the data signals associated with the points in the neighborhood when they are loaded into the storage devices, operative to modify the values of the data signals associated with the accessed neighborhood and maximum value selection means coupled to said neighborhood contribution circuit means for selecting the maximum value associated with the modified values and providing said maximum value as the transformation output signal to the next stage; and

central controller means coupled to the neighborhood contribution circuit means of each stage for selectively altering the operation on the neighborhood of points in each stage.

24. The apparatus of claim 23 which further comprises:

inversion means coupled between the data input and said neighborhood extraction means, operative to selectively form the logical compliment of the incoming stream of digital signals.

25. The apparatus of claim 24 wherein said inversion means comprises exclusive OR gate means having at least two inputs, one input receiving the incoming data signals and the other input coupled to said central controller means which supplies a command signal for enabling the inversion of the data signals.

26. The appatus of claim 23 wherein said neighborhood contribution circuit means further comprises a plurality of adder means, each coupled to one of the storage devices in the neighborhood extraction means, operative to modify the values stored therein by a contribution factor supplied by said central controller means.

27. The apparatus of claim 26 wherein said maximum value selection means further comprises a logical tree network including comparison means coupled to the adder means for comparing the output values thereof and selecting the highest value.