22 Linear Skeletons from Square Cupboards C. Judith Hilditch

INTRODUCTION The problem of reducing the line-like elements of a digitized picture to idealized thin lines is of general interest in pattern recognition. As early as 1957 the idea of obtaining a thin-line representation of certain patterns was suggested (Kirsch et al. 1957); recently McCormick (1963) and Narasimhan (1964) have described computer programs for doing this (for use in particular on bubble chamber photographs), and similar work has been done in character recognition, for example by Deutsch (1967). Blum (1964) has put forward an approach for dealing with more general shapes. In this the boundary of a shape is considered as being the source of a wavefront. The points at which wavefronts originating at different parts of the boundary first meet form a'skeleton' which, with a function giving the time taken for the wavefront to reach each point of the skeleton, completely defines the original shape. Programs for generating this skeleton for digitized pictures have been described by Rosenfeld and Pfaltz (1966), and also by Philbrick (1966).