Browse Prior Art Database

Binary Morphology Algorithm for Edge Smoothing to Improve Skeletonization

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

Publishing Venue

IBM

Related People

Evangelisti, CJ: AUTHOR [+2]

Abstract

Disclosed is an algorithm for thinning a binary image using morphological transforms. Conventional thinning algorithms for scanned line drawings either shorten the lines or produce bumpy thinned lines (1,2,3). This algorithm shapes the scanned image before thinning it. The resulting skeletons are not shortened and are smooth.

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

Binary Morphology Algorithm for Edge Smoothing to Improve Skeletonization

      Disclosed is an algorithm for thinning a binary image
using morphological transforms.  Conventional thinning algorithms for
scanned line drawings either shorten the lines or produce bumpy
thinned lines (1,2,3).  This algorithm shapes the scanned image
before thinning it.  The resulting skeletons are not shortened and
are smooth.

      The algorithm is designed to run on special-purpose hardware
called MITE (Morphic Image Transformation Engine) (4).  MITE is a
parallel-pipelined MIMD architecture and system that runs
morphological binary image computations in the form of Operation Flow
Graphs (OFGs).  An OFG is a directed graph or network of primitive
operations upon images.  The OFG may be thought of as a program flow
description of an algorithm for image processing which can be done by
a connected set of hardware primitives or by simulation of the
primitives.  The primitives which make up an OFG are:
 .  Processing Element (PE) - a Boolean function of a center bit and
the eight neighborhood bits of an image. A PE processes a two-
dimensional image into an output two-dimensional image as the center
bit moves across the input image.
 .    Boolean Combiner - an operator on two or more images which
logically combines the images on a pixel by pixel basis.
 .  Enumerator - an operator on an image which converts each on pixel
into an X Y coordinate pair for that pixel's position in the image.
This is the means by which MITE communicates with a host computer.

      The problem to be solved is to skeletonize a scanned image
using morphological transforms.  The state of the art methods have
two serious defects.  The lines in the resulting skeleton are
shortened or the lines contain spurs giving them a hairy appearance.
The proposed method first removes local black or white noise.  Then,
the image is enhanced without changing the connectivity of the black
bits.  The enhancement is to smooth the edges of the scanned lines so
that fewer spurs will occur when the image is skeletonized.  Then,
the image is thinned without shortening lines.

      The algorithm uses two conventional OFGs for thinning: thincyc
and thinnos.  Both OFGs consist an iteration of four PEs which
cyclically trim bits from the top of an image followed by trimming
from the right, bottom and left side of an image.  Thincyc reduces a
line to a minimally 8-connected line (no other bits may be removed
and retain connectivity). But thincyc removes the end points of a
thinned line each time it is applied.  Thinnos when it is applied to
the ends of a shortened line does not continue to shorten the line.
However, when a scanned image has lines which are uneven, then the
spurs mentioned above appear along the line during thinning.

      The algorithm is an OFG called skel.  Skel consists of three
OFGs which, in turn, remove noise from an image, smooth the image and
th...