SKELETONS FROM 4-CONNECTED CONTOURS

Date
1988-07-01
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
A fast serial algorithm of obtaining 4-connected skeletons from binary images is presented. The algorithm is based on the method of contour generation using chain codes where the new contours are computed as old ones are eroded. When a binary image is given, a set of 4-connected contours describing the boundaries of 2-D objects and the associated chain codes are obtained and an iterative procedure is set up where the points on the contour are visited one after the other in every iteration. For any given point on the contour, a window of two chain codes is used to determine the section of the new contour. The new section will include the contour point itself if it is a safe point. Otherwise it is made up of points exposed to the bacground when the contour point is removed. The algorithm makes use of the idea of a safe point count to determine whether a contour pixel is a safe point or not. As the new contour is generated, the safe point count of every point generated is incremented. At the end of an iteration, the chain code for the new boundary is in place for processing in the next iteration. Iteration terminates when all the points in the new contour are either break points or end points. The last contour generated becomes the skeleton. This is the basic algorithm for thinning 4-connected contours. The method is much faster than other serial or parallel algorithms, sequential or otherwise. The method is less immune to noise configurations when applied to 4-connected contours than to 8-connected contours. A more elaborate algorithm is also presented and incorprates a look ahead step to uncover and delete noise configurations.
Description
Keywords
Computer Science
Citation