SKELETONS FROM 4-CONNECTED CONTOURS
Date
1988-07-01
Authors
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