Method and apparatus for pattern recognition and detection

• US 4,395,699 A
• Filed: 05/29/1981
• Issued: 07/26/1983
• Est. Priority Date: 09/10/1979
• Status: Expired due to Term

• Current Assignee: Environmental Research Institute of Michigan
• Original Assignee: Environmental Research Institute of Michigan
• Inventors: Sternberg, Stanley R.
• Primary Examiner(s): Boudreau, Leo H.
• Application Number:
  US06/268,607
• Time in Patent Office: 788 Days
• Field of Search: 364/101, 364/107, 364/515, 364/725, 364/108, 340/146.3 H, 340/146.3 MA, 340/146.3 Q, 358/260-262
• US Class Current: 382/257
• CPC Class Codes: G06T 5/20 using local operators
• 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

An image analyzer system employs at least one neighborhood transformation stage for analyzing groups of neighborhood pixel values and selectively transforming the pixel values as a result of the analysis. In one embodiment, the center pixel in the neighborhood is changed to a programmable transformation value if it and its neighboring pixels have particular values. Preferably, the stage includes a programmable memory loaded by a central controller which is utilized to determine whether neighboring pixels of particular values are configured in a preselected pattern. The stage may also include another programmable memory for assigning selected values to the digital signals depending upon their original values as they enter the stage.

Claims

1. A neighborhood transformation circuit stage for analyzing an image represented by a serial stream of digital data signals corresponding to a matrix of points constituting the image, said stage circuitry comprising:

a data input for receiving said stream of digital data signals;

neighborhood extraction means including a plurality of digital storage devices for temporarily storing digital signals associated with a neighborhood in the matrix comprised of a central data point and its surrounding points in the matrix;

means for loading the signals into the storage devices to sequentially access substantially all of the neighborhoods in the matrix;

neighborhood configuration detector means for detecting a particular configuration of data signals having given values in each extracted neighborhood and providing a given output signal when the particular configuration is detected;

center detection means coupled to the storage device in the neighborhood extraction means containing the central data point, operative to provide a given output signal when a data signal having particular values for the central data point is contained therein;

comparison means having a plurality of inputs coupled to the outputs of said neighborhood configuration detector means and said center detection means, operative to provide an output signal upon receipt of both of said given signals; and

multiplexor means having at least two inputs and a control input for selectively coupling one of the inputs to its output, one of said inputs being coupled to the storage device in the neighborhood extraction means containing the central data point, the other input being coupled to a value generator means for providing a signal of a selected value, with said control input being coupled to the output of the comparison means such that the output of said multiplexor means provides the transformation output for the stage and is dependent upon the output of said comparison means.

2. The stage circuitry of claim 1 wherein the output of said value generator means is coupled to the output of said multiplexor means upon receipt of the output signal from the comparison means, with the central data point value being coupled to the output of said multiplexor means when said output signal is not received from the comparison means.

3. The stage circuitry of claim 1 which further comprises:

subfield detection means for providing a given output signal when the central data point in the extracted neighborhood is associated with a given subfield in the image matrix; and

means for coupling the output of said subfield detection means to another input of said comparison means so that the transformation output is a function thereof.

4. The stage circuitry of claim 1 wherein said comparison means includes at least one AND gate.

5. The stage circuitry of claim 1 which further comprises means for coupling said neighborhood configuration detection means and said center detection means to a central controller means for altering the image analysis in the stage.

6. A neighborhood transformation circuit stage for analyzing an image represented by a serial stream of digital data signals having values corresponding to points in a matrix constituting the image, said circuitry comprising:

a data input for receiving said stream of digital data signals;

neighborhood extraction means including a plurality of digital storage devices for temporarily storing digital signals associated with a neighborhood in the matrix comprised of a central data point and its surrounding points in the matrix;

means for loading the signals into the storage devices to sequentially access substantially all of the neighborhoods in the matrix;

analysis means coupled to the neighborhood extraction means for analyzing each neighborhood as it is presented to the storage devices and providing an output signal depending upon the analysis; and

alterable memory means coupled between said data input and the neighborhood extraction means for assigning selected values to the digital electrical signals depending upon their original values in the incoming data stream.

7. The circuitry of claim 6 wherein said alterable memory means includes a random access memory, operative to change the value assignment to the incoming signals depending upon the contents of the memory.

8. The circuitry of claim 7 wherein the values of the digital electrical signals in the incoming data stream are represented by a plurality of bits, with the bits forming an address for accessing the contents of the memory.

9. The circuitry of claim 8 which further includes selector means interposed between the memory and the data input for the incoming data stream, operative to select particular memory locations of the memory depending upon the values of the digital signals in the incoming data stream.

10. The circuitry of claim 9 wherein the incoming digital signals are supplied on N lines thereby providing 2^N possible values, and wherein said memory assigns a value of less than 2^N to selected ones of said signals to simplify the stage circuitry.

11. The circuitry of claim 10 wherein said stage is one in a series of substantially identical stages formed in a chain, with each stage being coupled to a central controller means for selectively altering the analysis of the neighborhood of points in each stage, said central programmable means operative to selectively load the contents of the memory in each stage to thereby select different data point values to be analyzed in each particular stage.

12. The circuitry of claim 11 wherein said central controller means is coupled to said selector means for loading particular values into selected locations in said memory.

13. A neighborhood transformation circuit stage for analyzing an image represented by a serial stream of digital data signals having values corresponding to points in a matrix constituting the image, said stage circuitry comprising:

a data input for receiving said serial stream of data signals;

neighborhood extraction means coupled to the data input, said neighborhood extraction means including a plurality of digital storage devices for temporarily storing digital signals associated with a neighborhood in the matrix comprised of a central data point and its surrounding points in the matrix;

means for loading the signals in the storage devices to sequentially access substantially all of the neighborhoods in the matrix; and

neighborhood configuration detection means for detecting whether data signals having particular values in each neighborhood are configured in a preselected pattern.

14. The circuitry of claim 13 wherein said neighborhood detection means comprises:

random access memory (RAM) means for storing a given value at a particular address, said RAM having an input coupled to the digital storage devices in the neighborhood extraction means, said RAM providing an output signal of said given value when the digital signals having particular values are configured in said preselected pattern.

15. The circuitry of claim 14 which further comprises:

address selector means having an input coupled to the storage devices containing the surrounding points and an output coupled to said RAM, operative to access said given value from the RAM when the combination of the outputs from the storage devices forms the particular address at which the given value is stored.

16. The circuit of claim 15 wherein said stage is part of a chain of substantially identical stages, with each stage being coupled to a central controller means for selectively altering the analysis carried out in each stage, and wherein said central controller means is operative to load the given value at different addresses in the respective RAM'"'"'s to thereby alter the pattern configurations to be detected in each stage.

17. A method of detecting a particular neighborhood configuration in an image represented by a serial stream of digital data signals having values corresponding to points in a matrix constituting the image, said method comprising:

sequentially loading said digital data signals into an array of latches arranged to store a central data point and its surrounding points in the matrix;

loading a given value into a particular address in a memory;

combining the outputs of the latches containing the surrounding points to form an address for accessing said memory; and

repetitively addressing said memory with each new address from the latches as each neighborhood of points is sequentially loaded into the latches to extract substantially all of the neighborhoods in the matrix whereby said memory provides an output of said given value when the address formed by the latches corresponds to the address at which said given value is stored thereby signifying that particular data values for the surrounding points in the neighborhood are configured in a preselected pattern.