Browse Prior Art Database

Fast Method to Compute Medial Axis and Related Transforms

IP.com Disclosure Number: IPCOM000122637D
Original Publication Date: 1991-Dec-01
Included in the Prior Art Database: 2005-Apr-04
Document File: 3 page(s) / 102K

Publishing Venue

IBM

Related People

Niblack, W: AUTHOR

Abstract

An algorithm is disclosed that provides a fast technique for computing the medial axis transform (1,2) and related operations on a binary image (e.g., finding nonwitness (3) and saddle (4) pixels). The technique uses a contour-based or spiral-in technique (5) both to compute the distance transform and to identify the desired types of pixels, such as local maxima, nonwitness, or saddle points.

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

Fast Method to Compute Medial Axis and Related Transforms

      An algorithm is disclosed that provides a fast technique
for computing the medial axis transform (1,2) and related operations
on a binary image (e.g., finding nonwitness (3) and saddle (4)
pixels).  The technique uses a contour-based or spiral-in technique
(5) both to compute the distance transform and to identify the
desired types of pixels, such as local maxima, nonwitness, or saddle
points.

      The following description uses the "2-3" metric, one of several
standard choices for a pseudo-Euclidean metric. Other metrics can be
used.  Let a D-neighbor be a direct- or 4-neighbor, let an I-neighbor
be an indirect- or diagonal-neighbor (an 8-neighbor that is not a
4-neighbor), for p an 8-neighbor of q, and let the "opposite pixels"
of p be the three pixels r, s, and t as shown below in step
7 (a)-(b).

      Initially build a list of the addresses of all background
pixels that have a D-neighbor in the object. Call this LIST_0.  Build
two additional lists:  LIST_1 is a list of pairs (p,d) where p is the
address of an object pixel that is a D-neighbor of a pixel q on
LIST_0, and d is the direction of q relative to p (d can be top,
bottom, left, right); and LIST_2 is a list of pairs (p,q) where p is
the address of an object pixel that is an I-neighbor of a pixel q on
LIST_0, and d is the direction of q relative to p (d can be top-left,
top-right, bottom- right, bottom-left). As LIST_1 and LIST_2 are
being built, erase the corresponding pixels in the object (i.e., set
to 0), and set the corresponding pixels in the distance transform
array to 2 and 3, respectively.  With i initally set to 1 and v to
3, do:
      1.   Increment v.
      2.   For each pair (p,d) on LIST_i, if q, the D-neighbor of p
opposite the pixel in direction d, is an object pixel, add (q,d) to
LIST_(i+2).  Erase q from the object, and set its distance transform
value to v.
      3.   For each pair (p,d) on LIST_i, if q, an I-neighbor of p
opposite the pixel in direction d, is an object pixel, add (q,d) to
LIST_(i+3).  Erase q from the object, and set its distance transform
value to v+1.
      4.   Increment v.
      5.   For each pair (p,d) on LIST_(i+1), if q, the D-neighbor of
p opposite the pixel in direction d, is an object pixel, add (q,d) to
LIST_(i+3).  Erase q from the object, and set its distance transform
value to v.
      6.   For each pair (p,d) on LIST_(i+1), if q, an I-neighbor of
p opposite the pixel in direction d, is an object pixel, add (q,d) to
LIST_(i+4).  Erase q from the object, and set its distance transform
value to v+1.
      7.   Identify the appropriate pixels.

      For the MAT:...