Browse Prior Art Database

Extraction of the Vector Basis of a Binary Image by Run End Pairing

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

Publishing Venue

IBM

Related People

Evangelisti, CJ: AUTHOR [+2]

Abstract

Disclosed is an algorithm which transforms or encodes a bit image into an equivalent set of straight runs or vectors which "almost exactly" represent the input image. Every connected straight run on the square grid (in the horizontal, vertical, and the two diagonal directions) of two or more bits is replaced by a single straight line. When drawn on a vector display or plotted, such a straight line will have a (temporal) beginning and an end and hence is directed. Thus, these straight line segments or runs are called vectors. Single isolated bits are not in any run, which agrees with the notion from geometry that two points define a line. Thus, isolated single bits in a bit image will not appear in the decoded image drawn with the set of vectors produced by this algorithm. Otherwise the rendering is exact.

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

Extraction of the Vector Basis of a Binary Image by Run End Pairing

      Disclosed is an algorithm which transforms or encodes a
bit image into an equivalent set of straight runs or vectors which
"almost exactly" represent the input image.  Every connected straight
run on the square grid (in the horizontal, vertical, and the two
diagonal directions) of two or more bits is replaced by a single
straight line. When drawn on a vector display or plotted, such a
straight line will have a (temporal) beginning and an end and hence
is directed.  Thus, these straight line segments or runs are called
vectors.  Single isolated bits are not in any run, which agrees with
the notion from geometry that two points define a line.  Thus,
isolated single bits in a bit image will not appear in the decoded
image drawn with the set of vectors produced by this algorithm.
Otherwise the rendering is exact.

      This algorithm works on almost any binary image. Examples are
the skeleton of an image, the outline of an image, and images
composed primarily of (wide) lines and or large areas of black.
Excluded are half-tone images which can have many isolated single
bits.  For images with wide lines or large black areas, the
vectorization is not particularly useful, since there is a high
degree of redundancy among the set of vectors which cover an area.
On thinned images this approach yields fewer runs than horizontal run
encoding.  It also has an advantage over chain coding because the
image is processed serially in raster order.

      In an image on a square grid, each black pixel (except single
isolated pixels) belongs to one or more of four possible straight
patterns of (at least two) adjacent black pixels.  These straight
(line) patterns are called runs and can lie in four (horizontal,
vertical, and the two diagonal) directions.  Note that on a
rectangular (as opposed to square) grid the two types of diagonal
runs will not lie exactly at 45 or 135 degrees, but the method
described here still applies.  Similarly, on a hexagonal pixel
pattern, there will only be three types of runs of physically
adjacent pixels.  A run has two distinct ends, called the starting
and ending ends. The starting end is the end seen first as the image
is scanned in raster order.

      The algorithm sweeps through the image in raster order to find
the location of all run ends.  For each occurrence of each end type,
the location (X,Y address) in the image is recorded along with an
identifier for each different end type.  As each run end is detected
it is paired with its starting end partner from the same run.  This
is easy to do since the mate can only lie exactly along the direction
of the run type of the starting end.

      For square and rectangular grids there are eight run end types,
and four run directions.  Neighborhood transform operations or
Processing Elements (PEs) locate the eight run end patterns.  These
PEs are named, respectively, wend for...