Dismiss
InnovationQ will be updated on Sunday, Oct. 22, from 10am ET - noon. You may experience brief service interruptions during that time.
Browse Prior Art Database

Parallel Binary Morphology Algorithm for Raster to Vector Conversion of Line Images

IP.com Disclosure Number: IPCOM000120208D
Original Publication Date: 1991-Apr-01
Included in the Prior Art Database: 2005-Apr-02
Document File: 6 page(s) / 337K

Publishing Venue

IBM

Related People

Evangelisti, CJ: AUTHOR [+2]

Abstract

Disclosed is an algorithm for raster to vector (R to V) conversion of binary images which accomplishes all image domain processing by binary morphology . R to V conversion is often used for automated processing of line drawings. For an overview of processing line drawing images see (1). Many researchers, such as those of (2,3,4,5), have addressed some aspects of this problem. Most researchers in the field opt for a software implementation. But general-purpose computers are extremely slow for most image processing, especially for image transforms such as those of binary morphology or neighborhood processing which is often proposed for fast skeletonization of images, but not for a complete R to V conversion.

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

Parallel Binary Morphology Algorithm for Raster to Vector Conversion
of Line Images

      Disclosed is an algorithm for raster to vector (R to V)
conversion of binary images which accomplishes all image domain
processing by binary morphology .  R to V conversion is often used
for automated processing of line drawings. For an overview of
processing line drawing images see (1). Many researchers, such as
those of (2,3,4,5), have addressed some aspects of this problem.
Most researchers in the field opt for a software implementation.  But
general-purpose computers are extremely slow for most image
processing, especially for image transforms such as those of binary
morphology or neighborhood processing which is often proposed for
fast skeletonization of images, but not for a complete R to V
conversion.  This algorithm in contrast uses morphology exclusively
for image processing and is implemented on parallel pipelined
systems.  Such systems, of which MITE (6,7) is typical, can execute
the image processing portions of this algorithm at image scanning
rates. This gives a tremendous performance advantage over present R
to V conversion algorithms.

      The algorithm computes on images as streams and can be
expressed entirely as a pipelined network of image primitives called
an OFG (Operation Flow Graph).  Primitives acceptable in an OFG are
constrained to be those of the MITE (6,7), a synchronous
reconfigurable parallel pipelined hardware system.  Any algorithm
which can be expressed in a fixed, countable number of the image
primitives of MITE can be executed at image scanning rates on a
suitably sized MITE or similar system.  The primitives of MITE are
the three-by-three binary neighborhood operation or transform;
pixel-wise combination of two or more images; and conversion of an
image to an X,Y address for every ON pixel.  These are implemented in
MITE by the processing element (PE), the image or Boolean combination
(BC), and enumeration (ENUM), respectively.  These primitives, their
implementation, and considerations for reconfiguring the MITE with
software into an OFG network, specifically implementing the algorithm
of choice, are discussed in (6,7).

      An overview of the algorithm and its major steps are shown in
the figure.  A description of each step follows.

      Skeletonization or outline extraction provides a thinned image
which represents the input image with lines which are single pixels
in width.  If the central skeleton of each line is required, the
image should be skeletonized. To preserve information about the line
width and length, a thinned outline image can be obtained.  And,
finally, large areas can be separated from lines by first removing
the area interiors (thus outlining the areas) and then skeletonizing
the new image.  These three approaches all result in thinned or
skeletonized image, the image form most suitable for the
vectorization methods discussed later.

      Skeletonization mus...