On shrinking binary picture patterns

ABSTRACT

A parallel processing algorithm for shrinking binary patterns to obtain single isolated elements, one for each pattern, is presented. This procedure may be used for counting patterns on a matrix, and a hardware implementation of the algorithm using large scale integrated tecnology is envisioned. The principal features of this method are the very small window employed (two-by-two elements), the parallel nature of the process, and the possibility of shrinking any pattern, regardless of the complexity of its configuration. Problems regarding merging and disconnection of patterns during the process as well as the determination of the maximum number of steps necessary to obtain a single isolated element from a pattern, are reviewed and discussed. An analogy with a neural network description, in terms of McCulloch-pitts “neurons” is presented.

REFERENCES

• 1: Izzo, N.F., and Coles, W. Blood cell scanner identifies rare cells. Electronics 35, 27 (Apr. 1962), 52-57.
• 2: Preston, K. Jr. The CELLSCAN system--A leucocyte pattern analyzer. Proc. Western Joint Comput. Conf., Vol. 19, May 1961, Spartan Books, New York, p. 175.
• 3: Perkin-Elmer Engineering Rep. 5489A (unpublished).
• 4: Weston, P. Photocell field counts random objects. Electronics 34, 22 (Sept. 1961), 46-47.
• 5: Heath, F.G. Large scale integration in electronics. Scientific American 222 (Feb. 1970), 22-31.
• 6: Unger, S.H. Pattern detection and recognition. Proc. IRE, Vol. 47, 1959, pp. 1737-1752.
• 7: McCormick, Bruce H. The Illinois pattern recognition computer, llliac III. IEEE Trans. Electronic Computers, (Dec. 1963), 791-813.
• 8: Perceptrons: An Introduction to Computational Geometry, The MIT Press, 1969
• 9: Azriel Rosenfeld, Connectivity in Digital Pictures, Journal of the ACM (JACM), v.17 n.1, p.146-160, Jan. 1970 [doi>10.1145/321556.321570]
• 10: Rosenfeld, A., and Pfaltz, J.L. Distance functions on digital pictures. Pattern Recognition. 1, 1 (July 1968), 33-61.
• 11: Levialdi, S. Parallel counting of binary patterns, Electronics Letters 6, (1970) 798-800.
• 12: McCulloch, W. S., and Pitts, W. A logical calculus of ideas immanent in nervous activity. Bull. Math. Biophys. 5 (1943), 115-137.
• 13: Caianiello, E.R. Outline of a theory of thought processes and thinking machines, J. Theoret. Biol. 1 (1961), 204-235.

INDEX TERMS

Keywords:
counting binary patterns, multiple connected pictures, parallel processing, shrinking