Method and apparatus for automatic shape recognition

DETAILED DESCRIPTION The present invention provides a generalized method for determining whether a shape or pattern exists anywhere in a particular image frame.
This method, based upon basic set theory and image algebra, treats images and shapes as point sets in n-dimensional cartesion space.
The problem of shape or pattern recognition is thus converted to the problem of detecting the occurrences of specific subsets of points within an a larger set (the image).
As will be shown, this problem may be solved for any shapes by utilizing the simple set operations of union, intersection, complement and reflection, and the image algebra operations of dilation and erosion.
According to one aspect of the present invention, a machine implementable method is provided for detecting the existence of one or more preselected shapes and/or patterns in a first image represented by a matrix of digital data signals including the steps of (a) computing the complement of the first image matrix; (b) creating a first structuring element, representative of the shape to be recognized, as a matrix of digital data signals slightly larger in dimension than the shape; (c) creating a second structuring element equal to the window complement of the first structuring element; (d) eroding the first image matrix with the first structuring element to form a first transformation matrix; (e) eroding the complement image matrix with the second structuring element to form a second transformation matrix; and (g) combining the corresponding points of the first and second transformation matrices to form a result matrix wherein each non-zero point identifies an origin point where the shape has been recognized in the first image matrix.
The above-described method is preferably implemented on a special purpose computer comprising one or more substantially identical, programmable neighborhood transformation stages which operate on a serial stream of digital electrical signals corresponding to a matrix of points in the image as the serial stream is passed through the stage