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

Morphological Techniques for Determining Bounding Rectangles and Octagons

IP.com Disclosure Number: IPCOM000105058D
Original Publication Date: 1993-Jun-01
Included in the Prior Art Database: 2005-Mar-19
Document File: 6 page(s) / 180K

Publishing Venue

IBM

Related People

Lavin, MA: AUTHOR [+2]

Abstract

This disclosure describes several techniques based on morphological transformations [1,2], for determining the position and size of approximately circular regions in binary images; such techniques can be used as a first stage in applications such as inspection of drilled printed circuit board panels (to find missing or misplaced holes). The techniques, which determine the position and size of regions by determining their bounding rectangles or bounding octagons, have the following advantages:

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

Morphological Techniques for Determining Bounding Rectangles and Octagons

      This disclosure describes several techniques based on
morphological transformations [1,2], for determining the position and
size of approximately circular regions in binary images; such
techniques can be used as a first stage in applications such as
inspection of drilled printed circuit board panels (to find missing
or misplaced holes).  The techniques, which determine the position
and size of regions by determining their bounding rectangles or
bounding octagons, have the following advantages:

1.  They can be implemented efficiently using image processing
    systems such as MITE [3];
2.  They require relatively few morphological operations (and the
    number grows logarithmically with the diameter of the largest
    region to be detected).
3.  They do not require a separate "pre-rounding" operation.
4.  They can handle concave regions (and even regions that are not
    completely connected).
5.  Boundary points are marked in a way that simplifies the
    computation for grouping.

The bounding rectangle technique consists of the following stages:

1.  Transform the binary input image so that every contiguous region
    of 1-valued pixels is replaced by its bounding rectangle; in
    fact, the technique can handle noncontiguous regions, having
    breaks or cracks, provided that the components are not too large
    nor too widely separated.
2.  Extract a list of the (corner) vertex coordinates of the
    resulting image.
3.  Group coordinates corresponding to the same rectangles.
4.  Compute position and size from the centroid, length, and width of
    the rectangles based on their vertex coordinates.

These steps are next described in greater detail:

      Generating the Bounding Rectangle Image

1.  Start with the input image
    I sub in
    , shown in Fig. 1a
2.  "Smear"
    I sub in
      in the vertical direction, to produce intermediate image
    I sub vert
    , shown in Fig. 1b
3.  "Smear"
    I sub in
      in the horizontal direction, to produce intermediate image
    I sub 'hor'
    , shown in Fig. 1c
4.  Intersect
    I sub vert
      and
    I sub 'hor'
      to produce
    I sub rect
    , shown in Fig. 1d

      A key aspect of this disclosure is that the "smearing"
operations used to form the bounding rectangle (and octagon) can be
decomposed into a "logarithmic series" of non-immediate-neighborhood
operations, as shown in Fig. 2.

      Identifying Vertex Points

      Bounding rectangles give rise to four types of vertex points:
NW (northwest), NE (northeast), SE (southeast) and SW (southwest).
All can be detected locally using
3 times 3
template matching, which which can be performed in systems such as
_________________
MITE by using
3 times 3
  neighborhood transformations followed by enumeration to produce
  ____________...