A systolic algorithm and architecture for image thinning

In this paper, we describe a new special purpose VLSI architecture for image thinning. The architecture is systolic and is based on an algorithm that achieves a high degree of parallelism. The proposed algorithm computes the skeleton of multiple objects in an image in linear time by making 2 scans over the 4-distance transform of the image. The algorithm is mapped onto a linear systolic array of simple processing elements (PEs) and for an N×N image, the architecture requires N PE´s. The entire array can be realized in a single VLSI chip. The proposed hardware can perform thinning on a 512×512 image in 2.59 msec and on a 256×256 image in 0.327 msec. Currently, a prototype CMOS VLSI chip implementing the proposed architecture is being designed and built at the University of South Florida