- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

NOTE: Do to the large number of E-Mail requests I received for the following
code, I am posting this to the Net News system, instead of individual
E-Mail. Thank You!
 

- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

To all those interested in this algorithm:

I wrote this algorithm in 1980, for a mechanism to follow free-form paths.
Its original purpose was for an animation system, but it has since been
implemented in auto-vectorizing algorithms for CAD and Paint.

I have placed the code in the PUBLIC DOMAIN. It is free for you to use and
modify. However, I retain original rights to the methods. If you read the
code and use it, I would appreciate it if you would credit the original
algorithm to me, in both the code and the documentation.

The algorithm is extremely simple. The description enclosed here was
written up for Graphics Gems III, but was rejected because, among other reasons,
they believed that "it couldn't possibly work" (sigh). It works perfectly.

I do not guarantee the 'C' code snippet at the bottom of the article. My
implementations are all in Assembly Language, but I did test the snippet with
a small array and it appeared to work fine. It is best to follow the theory,
and not the snippet (though the snippet may indeed be flawless... I don't have
the time to double check it now).

There is an accompanying GEM (also rejected) that describes a 'best' edge
detector to use as a pre-processing step to Path Following. Basically, you can
use any Edge Detector you desire. If you want a copy of my edge detector
article, please let me know.

The original article had three 'figures' attached, which helped clarify the
use of the table. These areas have been rewritten to try to clarify that it
the text itself. Note that the test 'C' code appears at the end of the
article.

Finally, to all those interested in taking the information in this post, and
producing efficient line and/or spline information, consider the following:

Producing Efficient Lines:

This is really easy, as the algorithm presented here
produces a list of connected points which make up the
path. The simplist way to produce polylines is to
merely consider every other point, and then check the
'middle' point to see if it lies on the line between
the first and third point, if it does (eg., has a 'like'
slope), delete it. Continue itterating the path until
you don't delete any more points.

Producing Efficient Splines:

NASTY NASTY NASTY. Again, the structure of the data
provided by this algorithm lends itself to many implementations.
There are many text books with spline-convertors, arc-convertors
and other methods. All methods to date (that I've seen)
have two major problems... #1 They are SLOW, #2 They are only
approximations, and for my uses are not accurate enough (for
the amount of time they take). Any help here would be
greatly appreciated!!!!!

Any correspondence may be addressed, faxed or phoned to:

Name: David Cook
Affiliation: cookware
Address: RR #1, Box 351
Whitestown, Indiana 46075

Telephone: (317) 769-5049 Fax: (317) 769-6513

E-Mail: nstar!npal!dcook -or- dcook@npal.rn.com
 
 

Here is the text - enjoy:
 

- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

--------------------------
INTELLIGENT PATH FOLLOWING
--------------------------
 

This gem concentrates on a problem of image processing. It is often desirable
to take an arbitrary set of continuous pixels and create a list which describes
the pixels as a 'path' or 'stroke'. The uses for such an algorithm vary from
pattern recognition to animation and the graphic arts. This particular gem
devotes itself to creating a consecutive set of connected points from a random
raster image. This gem does not address the further conversion of the point
list to a 'known' vector object, though for non-spline shapes, this is a
trivial extension.

Consider an arbitrary path on a raster image, where the path consists of white
pixels on a black pixel background. Such a path may be of any complexity and
may even cross itself. The algorithm presented in this article gives a method
by which the pixels in the path may be returned to you, in a list, such that
the list represents a serues of connected pixels that indicate the path. The
path is represented in a very similar way to how a human may have originally
made the path. The algorithm handles most types of loops and crossovers, hence
the name "Intelligent" path following. This algorithm differs from other
algorithms in that it handles the path following without any sorting of the
data. The algorithm naturally produces an efficient path with the pixels
occurring in the proper order from an arbitrary raster image. Furthermore, the
algorithm is extremely efficient, both in speed and size. Assembly language
implementations have been accomplished in as little as 40 lines of code.
 

The Algorithm:

It is assumed that the incoming raster image is full color, or at the very
least monochromatic. Before any path following can be accomplished, the image
must be reduced to edges only. Any edge detection algorithm can be used, but a
ramping edge detector is the most desirable with something like a Roberts
Gradient being the next best choice. You will want to avoid edge detectors like
'shift and xor' or Laplacian filter detectors as they produce unwanted
artifacts which can often affect performance. The edge detector must be tuned
to produce only single pixel wide edges.

Assuming an edge detected raster image the program main begins by scanning
the raster image from upper left to lower right. (You can modify the main to
scan the image in any manner you want.) As you scan the image, each time you
encounter a non-black pixel you will call the routine path_follow. In other
words, your main should appear as:

/* Note, lower left of screen is 0,0 */
for (y = screen_height - 1; y >= 0; y--) {
for (x = 0; x < screen_width; x++) {

if (read_pixel(x,y) != 0) {
/* Found a pixel, FOLLOW THE PATH */
path_follow(x,y,&points,&count);

/* Do something with the path here */

}
}
}

The path_follow routine itself takes a current x and y screen coordinate as
input, and produces an array (points) containing 'consecutive' X and Y points
and a count of the number of points as output.

The path following routine 'knows' how to find the path by simply 'following'
the path using a last-direction-traveled algorithm. The heart of this
algorithm is a small data table which describes to the algorithm the best pixel
to choose next, in determining the path, based on the direction of travel. The
critical data arrays are described as follows:

ptable[9][16] = { {-1,-1, 0,-1,-1, 0, 1,-1,-1, 1, 1, 0, 0, 1, 1, 1},
{ 0,-1, 1,-1,-1,-1, 1, 0,-1, 0, 1, 1,-1, 1, 0, 1},
{ 1,-1, 1, 0, 0,-1, 1, 1,-1,-1, 0, 1,-1, 0,-1, 1},
{-1, 0,-1,-1,-1, 1, 0,-1, 0, 1, 1,-1, 1, 1, 1, 0},
{ 0,-1, 1,-1,-1,-1, 1, 0,-1, 0, 1, 1,-1, 1, 0, 1},
{ 1, 0, 1, 1, 1,-1, 0, 1, 0,-1,-1, 1,-1,-1,-1, 0},
{-1, 1,-1, 0, 0, 1,-1,-1, 1, 1, 0,-1, 1, 0, 1,-1},
{ 0, 1,-1, 1, 1, 1,-1, 0, 1, 0,-1,-1, 1,-1, 0,-1},
{ 1, 1, 0, 1, 1, 0,-1, 1, 1,-1,-1, 0, 0,-1,-1,-1}
};

This array contains nine lists of 16 values where each set of two values
indicate a X,Y relative pair (eg., 16 values makes 8 coordinate pairs of
x,y,x,y,x,y...). Each of the nine lists indicate a search vector based on
the previous pixel traversed. Note that in the array above, the middle list
(Index = 4) is identical to the second list (Index = 1). This array index is
only encountered on the first pixel of each path, when no previous direction is
known. The choice of duplicating the second index was made to facilitate a
main which scanned down, looking for the first pixel. Any other list could
have been used instead (eg., it does not matter what the order of search is
for Index = 4).

To determine the index (0 - 8, eg., which list of 16 values to use), simply
calculate the following formula:

Index = ((cy - ly + 1) * 3) + (cx - lx + 1);

The values cx and cy indicate the Current X and Y locations for the pixel under
consideration. The values lx and ly indicate the Last X and Y location (eg.,
the previous cx and cy). The algorithm begins by initializing cx and lx to 'x'
in the original path_follow parameter list. Likewise, cy and ly are also
initialized to the 'y' in the path_follow parameter list. The value Index is
used as the primary index to ptable (eg., ptable[Index][n]).

The list of 16 numbers found in ptable[index] will contain relative X and Y
values to search from the current position, which is always considered to be
the center of the 3 x 3 grid. Each of the eight surrounding positions is
searched, in turn, to determine where the 'next' pixel is. In order to move to
the next position, path_follow simply adds the relative X and Y value found in
the ptable list, to the absolute X and Y value specified by cx and cy. The
order of the numbers found in ptable is important, and has been geared to be
the most logical order to search, based on the current direction of travel.
Therefore, the first pixel you search (eg., cx+ptable[index][0],
cy+ptable[index][1]) will be the most likely pixel to be set, based on the
current direction of travel.

If the first pixel chosen is not set, then the next best location from the list
is checked (eg., cx+ptable[index][2], cy+ptable[index][3]). This continues
until one of the pixels is found to be set. The pixel is erased in the image,
and the coordinates are entered on the paths endpoint list (points). This
point now becomes the new center point of the next 3 x 3 grid (eg., the new
cx,cy). The process repeats.

If no pixel is found to be set within the 3 x 3 neighborhood, the algorithm is
extended in the current direction of travel, one more pixel (neighborhood).
This 3 x 3 is again checked. If a pixel is found, the original x and y, along
with the current x and y are entered on the list (eg., both points, since we
skipped one). If no point is found within this additional 3 x 3, the path is
considered 'found' and path_follow returns to the caller.

The purpose of the additional 3 x 3 is to allow crossovers, and to compensate
small breaks in the input image. If a line crosses itself, as the algorithm
iterates and removes the pixels along the path, it will delete a one-pixel-wide
path from the line at the cross point. By extending an additional 3 x 3, the
path will still traverse and jump the gap. If desired, this step can be made
more general by extending the search more than once, for larger gap detection,
or by extending the grid size, from the original center point, to 5 x 5, 7 x 7
etc.., allowing disjointed but nearby lines to be joined.

After path_follow returns, the calling main simply iterates to the next pixel
in the horizontal scan. Since the path has been removed from the original
image, it will not be detected again. After the main's nested loops have
finished, the image is completely converted with each call to path_follow
returning a unique path from the screen.

Each path, returned by path_follow, will be a list of numbers which indicate
the absolute x and y positions within the path of each pixel, in the order
dictated by the path. Note that every pixel in the path will be represented
in the list. Prefiltering may be desirable as a prelude to auto-vectorizing.
This may be accomplished as easily as removing every other point, to more
complex algorithms that examine spans in the list for slope coherence (removing
all points on a like slope).

Finally, two notes of caution. Since the main is responsible for finding the
'start' of a path, the one presented here has the unfortunate byproduct in that
it often splits a path into two paths. Any path which has a non-endpoint as the
top most point in the shape will be split into two paths. This can be avoided
by first traversing to the end of the path (instead of deleting pixels, set
them to some secondary color) and then traversing the path (look for both set
and secondary color pixels). A second solution is to examine the paths after
the entire scan is fished, and join any paths with beginning or ending
endpoints within some specified range from each other.

The second caution is to be wary of clipping errors. The 'C' code presented
with this gem does not check for values that are out of range. Values which
are out of the frame buffers range should be ignored in the algorithm.
 
 

/* Routine Name: path_follow
Copyright: 1980 - 1992 David Cook - all rights reserved
Status: This algorithm is hereby in the public domain.
Please acknowledge David Cook as the author, in
the code and any documentation regarding the code.

Given a starting X and Y point, which is known to be some point on
a path with a width of one pixel, this routine will create a list
which specifies the points along the path, in a contiguous order.

The algorithm handles crossovers (paths which cross themselves)
and produces the proper order naturally, without sorting of the
data points.

Entry: path_follow (x,y,&points,&count)

Where: x = Path start screen X coordinate
y = Path start screen Y coordinate
points = An array of MAX_POINTS * 2 in size
count = Returns the number of x,y points found

Returns: points = Returns containing found point list
count = Returns the number of x,y points found

Declarations: long x,y,count,points[MAX_POINTS][2]

Notes: (1) Note that this routine is generalized, and
will not return a path larger than MAX_POINTS
in size. It is assumed that points has been
declared to be twice MAX_POINTS in size.

(2) points[n][0] will contain X values and
points[n][1] will contain Y values.

(3) The routine assumes the incoming raster image is
already edge detected such that only a one pixel
wide raster edge exists for all objects.

(4) The read_pixel routine returns the color of a
pixel at a given X and Y location (eg.,
read_pixel(x,y)).

(5) The write_pixel routine writes a color at a
given X and Y location (eg., write_pixel(x,y,
color)).

(6) Note that this routine merely returns the
current path as a list of contiguous points.
What you do with them after this point is up
to you -- be creative!

(7) Note that this routine does NOT check for
clipping, in case the relative X and Y values,
when added to the absolute cx,cy values, are
not out of range!

*/
#define X 0
#define Y 1
#define BLACK 0
#define MAX_POINTS 1000

long ptable[9][16] = { {-1,-1,0,-1,-1,0,1,-1,-1,1,1,0,0,1,1,1},
{0,-1,1,-1,-1,-1,1,0,-1,0,1,1,-1,1,0,1},
{1,-1,1,0,0,-1,1,1,-1,-1,0,1,-1,0,-1,1},
{-1,0,-1,-1,-1,1,0,-1,0,1,1,-1,1,1,1,0},
{0,-1,1,-1,-1,-1,1,0,-1,0,1,1,-1,1,0,1},
{1,0,1,1,1,-1,0,1,0,-1,-1,1,-1,-1,-1,0},
{-1,1,-1,0,0,1,-1,-1,1,1,0,-1,1,0,1,-1},
{0,1,-1,1,1,1,-1,0,1,0,-1,-1,1,-1,0,-1},
{1,1,0,1,1,0,-1,1,1,-1,-1,0,0,-1,-1,-1}
};

void path_follow (x,y,points,count)
long x,y,points[MAX_POINTS][2],*count;
{
long i,index,lx,ly,cx,cy,color,last_chance,p;

/* Initialize the first point */
points[0][X] = lx = cx = x;
points[0][Y] = ly = cy = y;

*count = 1;
last_chance = FALSE;

/* Erase the first point */
write_pixel(cx,cy,BLACK);

/* First point is found, find the rest of the path now */
do {
/* Calculate which direction cell to use */
index = ((cy - ly + 1) * 3) + (cx - lx + 1);

/* Search this neighborhood, in most likely order */
p = -1; /* Set a little flag */
for (i = 0; i < 16; i+=2) {
color = read_pixel(cx+ptable[index][i+X],cy+ptable[index][i+Y]);
if (color != BLACK) {
/* Found the next pixel along this path!!!! */
p = i; /* Set which index */
break; /* break the for loop */
}
}

/* Update the last point to be the current point */
lx = cx;
ly = cy;

/* Is this the end? */
if (p != -1) {
/* Not the end! Enter this pixel and do it again */
cx += ptable[index][p+X]; /* move to the next pixel */
cy += ptable[index][p+Y]; /* move to the next pixel */
points[*count][X] = cx; /* enter the point */
points[*count][Y] = cy; /* enter the point */
(*count)++; /* count the point */
write_pixel(cx,cy,BLACK); /* erase the pixel */
last_chance = FALSE; /* let's do another one! */
} else {
if (!last_chance) {
/* Nothing found, try one cell further along */
cx += ptable[index][X]; /* position 0 is best x */
cy += ptable[index][Y]; /* position 1 is best y */
points[*count][X] = cx; /* enter the point, in case */
points[*count][Y] = cy; /* enter the point, in case */
(*count)++; /* count the point, in case */
last_chance = TRUE; /* just do one more! */
} else {
/* Done! - last chance failed too! */
(*count)--; /* last point was bogus */
break; /* kill the do loop */
}
}
} while (*count < MAX_POINTS);

/* Return to the user */
return;
}
 

- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -