Browse Prior Art Database

Racing Horses Method to Find Skeleton of a Curve

IP.com Disclosure Number: IPCOM000105501D
Original Publication Date: 1993-Aug-01
Included in the Prior Art Database: 2005-Mar-20
Document File: 4 page(s) / 123K

Publishing Venue

IBM

Related People

Appel, A: AUTHOR

Abstract

The skeleton of a curve for relatively long shapes of approximately the same thickness is a series of connected pixels that fall along the middle of the shape. The racing horses method uses two outline followers, a clockwise outline follower and a counterclockwise outline follower. The midpoint of a line connecting these two outline followers can be taken as the skeleton of the curve if they stay in synchronization as they move around the shape.

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 52% of the total text.

Racing Horses Method to Find Skeleton of a Curve

      The skeleton of a curve for relatively long shapes of
approximately the same thickness is a series of connected pixels that
fall along the middle of the shape.  The racing horses method uses
two outline followers, a clockwise outline follower and a
counterclockwise outline follower.  The midpoint of a line connecting
these two outline followers can be taken as the skeleton of the curve
if they stay in synchronization as they move around the shape.

      Small image array, I, in Fig.  1, shows point A on the outside
of a shape.  The task of an outline follower is to find a point on
the outside of the shape next to A. Image array J shows the search
order of a clockwise outline follower as image pixels are examined to
find a white pixel i that is next to a black pixel with the index
i-1.  The image array, K, in Figure 1, shows the search order of a
counterclockwise outline follower as image pixels are are examined to
find a white pixel i that is next to a black pixel with the index
i-1.

      Small image L, in Fig. 1, shows point B which the clockwise
outline follower will choose as the next point from A. Small image M,
in Fig. 1, shows point C which the counterclockwise outline follower
will choose as the next point from A. The outline followers can now
update the center of the search pattern to the new location and
continue to search for the next point on the outline.  For smooth
shapes either outline follower will eventually go completely around a
shape.

      A section of a long shape is shown in Fig.  2 as both a
clockwise and counterclockwise outline follower operate on the left,
R, and right side, S, of a shape.  The point M on the midpoint of a
line connecting R and S can be taken to be a point on the skeleton.
The outline followers operate sequentially so it can be expected that
af...