Browse Prior Art Database

Convex Decomposition of Multi-Dimentional Images

IP.com Disclosure Number: IPCOM000106877D
Original Publication Date: 1993-Sep-01
Included in the Prior Art Database: 2005-Mar-21
Document File: 4 page(s) / 55K

Publishing Venue

IBM

Related People

Hanson, WA: AUTHOR

Abstract

An algorithm is disclosed for decomposing binary images into a hierarchical tree structure. The decomposition is such that the images at every node in the tree are convex.

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

Convex Decomposition of Multi-Dimentional Images

      An algorithm is disclosed for decomposing binary images into a
hierarchical tree structure.  The decomposition is such that the
images at every node in the tree are convex.

      Methods for decomposing a binary image are desirable in order
to solve problems that arise in situations such as robotic vision,
parts inspection, or scene analysis.  The proposed algorithm performs
a decomposition based on convex hulls.  The method has two
significant properties:

1.  The decomposition is independent of the scene orientation - no
    explicit coordinate system is employed.

2.    The resulting decomposition is expressed in terms of convex
    sets - sets that have nice mathematical properties.

      The method recursively decomposes the scene using two major
processing functions: the convex hull C and the connected components
labeling N.  The convex hull generates that minimum convex set that
includes the source.  The connected components labeling assigns a
distinct integer label to each point based on its neighborhood.  The
result of the labeling is such that all spatially isolated objects
have a unique label.  Given the two operations described, the
decomposition is performed based on the tree spawning operation
doubleS shown in the figure.  The construction of the sets is:

A hat = ch(A) = convex hull of A
B = A hat - A = (union) B sub i
Reversing the decomposition,
A = A hat - B
  = A hat - (u...