Browse Prior Art Database

Parallel Algorithm for Determining Line Connectivity of Scanned Line Drawings

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

Publishing Venue

IBM

Related People

Evangelisti, CJ: AUTHOR [+2]

Abstract

A common image processing problem is to determine which end points of lines in an image are connected. Line following is often used to solve these problems. The line in the image may be produced by scanning engineering drawings or maps. Disclosed is a method for following many lines in parallel in a line image. The line following is performed by near neighbor transformations acting in parallel. Many lines are followed from each end until the middles of the lines are reached. The lines are shortened from each end and the ends move along the line toward the middle of the line. Each end carries a unique id along with it as it moves towards the middle. The unique id, called a color, is used to determine the connectivity of the lines.

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

Parallel Algorithm for Determining Line Connectivity of Scanned Line
Drawings

      A common image processing problem is to determine which
end points of lines in an image are connected.  Line following is
often used to solve these problems.  The line in the image may be
produced by scanning engineering drawings or maps.  Disclosed is a
method for following many lines in parallel in a line image.  The
line following is performed by near neighbor transformations acting
in parallel.  Many lines are followed from each end until the middles
of the lines are reached.  The lines are shortened from each end and
the ends move along the line toward the middle of the line.  Each end
carries a unique id along with it as it moves towards the middle.
The unique id, called a color, is used to determine the connectivity
of the lines.  When the middle is reached, a host computer is invoked
to pair the colors which determines the connectivity.

      The method follows many lines in an image in parallel. During
each pixel processing time a new bit of an image is fed to a circuit.
Many lines are followed from their endpoints one bit closer toward a
pair of midpoints (one corresponding to each endpoint).  The circuit
contains transforms which run in parallel and, in effect, shorten all
the lines until the endpoints meet.  The transforms are pipelined
with the output of one feeding the input of another.  These
transforms, which are called morphological transforms, map a
two-dimensional (2-D) binary image into another 2-D output image.
The output pixel is an arbitrary boolean function of the nine pixels
in the 3 by 3 neighborhood of the corresponding input pixel.  In
addition, two 2-D binary images may be combined into one image by
boolean functions.

      The method passes an image as a bit stream to special hardware
called MITE (*).  MITE is a programmable, reconfigurable, parallel-
pipelined system which processes the stream.  The phrase "bit stream"
and "image" are used interchangeably.  A host computer (in particular
the application program) receives the xy locations of pixels in
special generated images.  This process is called enumeration.  The
host uses this data in applications that require knowing the
connectivity of lines.

      Fig. 1 shows the steps in processing an image.  MITE receives
an image as a bit stream.  The image contains wide lines.  In the
circuit called "thin image" a new image is generated.  This image is
an 8-connected skeletal line.  In the circuit "delete junctions" the
places where a line branches, the connectivity is broken and the
modified image is passed on.  The locations of these junctions are
passed to the host computer.  If a line is a closed polygon and has
no lines coming into it or crossing it, the line will not be
processed by the algorithm.  The reason is that it has no junctions
and no line ends.  In the circuit "initialize line shortening" a
number of other images are gener...