Image analysis – Image enhancement or restoration – Object boundary expansion or contraction
Reexamination Certificate
1999-06-29
2002-05-21
Boudreau, Leo (Department: 2621)
Image analysis
Image enhancement or restoration
Object boundary expansion or contraction
C382S181000, C382S203000, C382S204000, C382S206000, C382S241000, C382S256000, C382S257000, C382S308000, C345S420000, C345S423000
Reexamination Certificate
active
06393159
ABSTRACT:
BACKGROUND OF THE INVENTION
This invention generally relates to the automated analysis and characterization of geometric shapes, and, more particularly, to the invertible characterization of such shapes.
The notion of “shape” is intimately related to the notion of contour or boundary. Indeed, the description of a shape entails specification of its spatial extent; that is, the specification of the shape's “inside” and “outside”. This is equivalent to specifying its frontier or boundary. The boundary of a shape has, however, a continuum of points, and, as such, is not amenable to finite representation or computation.
Thus, in order to computationally characterize a shape, a discrete representation of its boundary in a morphologically faithful manner, i.e., preserving its structural integrity, is necessary. Next, the fundamental morphological attributes of the shape must be extracted from this representation. One of the important morphological descriptors of a shape is its “skeleton” (the “frame” over which the “meat” of the shape hangs).
For a shape with a continuous boundary, the medial axis (set of all interior points with two or more nearest points on the boundary) is the generally accepted definition of its skeleton. The formation of such a skeleton is described by H. Blum, A Transformation for Extracting New Descriptors of Shape,
Symposium on Models for Speech and Visual Form
, Weiant Whaten-Dunn (Ed.) (MIT Press, Cambridge, Mass., 1967), incorporated herein by reference. Though the medial axis transform (MAT) of a shape has been the generally accepted definition of its skeleton, it is widely acknowledged that the resulting skeleton is not ideal in most cases.
The MAT of a shape is the locus of the centers of all maximal discs contained in the shape. A maximal disc contained in the shape is any circle whose interior is contained completely inside the shape (i.e., has empty intersection with the exterior of the shape) such that the circle touches the boundary of the shape at two or more points. Equivalently, for every interior point of a shape, consider the set of boundary points nearest to it. The MAT of the shape is then defined by the set of all those interior points of the shape that have at least two nearest boundary points.
Strictly speaking, the locus of the centers of maximal discs is only the medial axis. The MAT includes the specification of the radii of the maximal discs along with their centers. This makes the MAT an invertible transform. Thus, the union of all discs with centers and corresponding radii specified by the MAT of a shape is the shape itself.
Further, while it is possible to obtain the MAT of a shape directly from its boundary, it is in general not possible to obtain the boundary of a shape directly by inverting its MAT; the boundary must be recovered by some other means after the shape has been reconstructed. It is important to note that the boundary of a shape is different from the shape itself, in that it is the frontier separating the shape's interior from its exterior.
The MAT is a non-local transform. This, in general, causes a small feature on the boundary of a shape to induce a skeletal feature in the MAT that is spatially far removed from the corresponding boundary feature. In addition, boundary features may be greatly exaggerated or underplayed by their skeletal counterparts. The MAT in a shape may have several small branches and spurs induced by minor undulations or noise present in the boundary. These features in the MAT do not contribute significantly to the overall structure of the shape. The MAT of a shape has information only about the distances of the boundary features of the shape and not about their “girths” or “sizes.” It is therefore hard to estimate the significance of a point in the MAT to the description of the overall shape. Thus, there is no natural way to “prune” the MAT to obtain a basic skeleton that captures the essence of a shape without regard to the insignificant local boundary features.
The MAT does not extend to a discretely represented shape (e.g., in raster format). Indeed, the set of interior points with two or more nearest boundary points for a discretized shape may be an empty set. The unavailability of the MAT for computing skeletons of discretized shapes has stood in the way of its use as a practical definition of the skeleton. Consequently, there is no generally accepted definition for the skeleton of a discretized shape. There have been attempts to extend the MAT to digitized shapes; for example, the well-known class of “thinning” algorithms in image processing (e.g., see U.S. Pat. No. 5,574,803, issued Nov. 13, 1996). These attempts, however, have been computationally expensive and the resulting skeletons fall short of the requirements of an ideal skeleton. Further, many of these algorithms leave behind undesirable artifacts, such as spurs and branches, which are sometimes eliminated by further elaborate post-processing. Thus, although the MAT of a shape is regarded as its primary morphological descriptor, it has not proved to be very useful in providing computationally viable information about the structure of the shape. In summary, the existing state-of-the-art in shape characterization/analysis is either inadequate, computationally expensive, or, frequently, both.
The invention described herein broadly provides a methodology for multiscale morphological characterization and analysis of connected planar shapes and their properties. It lays down a general purpose computational setting for scale-sensitive extraction, characterization and analysis of shape features. Various objects, advantages and novel features of this invention will be set forth in part in the description which follows, and in part will become apparent to those skilled in the art upon examination of the following or may be learned by practice of the invention. The objects and advantages of the invention may be realized and attained by means of the instrumentalities and combinations particularly pointed out in the appended claims.
SUMMARY OF THE INVENTION
In one aspect, the present invention is directed to a computer implemented method for determining the skeletonized representation of a shape having a boundary. A set of maximal discs is first formed within the boundary of the shape. The maximal chords of tangency are determined for each maximal disc in the set of maximal discs. The set of all ordered pairs (p,&dgr;) of the maximal chords of tangency are determined, where p and &dgr; are the midpoint and half the length, respectively, of each maximal chord of tangency of the maximal discs that are tangent to the shape at exactly two points. The set of unordered triples of ordered pairs of maximal chords of tangency of the maximal discs are determined that are tangent to the shape at exactly three points. The midpoints of adjacent maximal chords of tangency of the maximal discs are successively connected to form a skeletal feature that terminates at a terminal maximal chord of tangency of a maximal disc that is tangent to the shape at exactly three points. The skeletal features are connected by joining the midpoints of the maximal chords of a maximal disc with three maximal chords with the center of the maximal disc if the maximal chords form an acute angled triangle, or to the midpoint of the longest of the three chords otherwise so that a connected skeletal representation of the shape is formed.
In another aspect of the invention, a computer implemented method for determining the skeletonized representation of a shape having a boundary uses Constrained Delaunay Triangulation. A discretized multi-scale representation of a shape is first formed using a Haar wavaelet tranform. A Constrained Delaunay Triangulation (CDT) of the discretized representation is formed to define termination triangles (T-triangles) having two external edges, sleeve triangles (S-triangles) having one external edge, and junction triangles (J-triangles) having no external edges. For each S-triangle, a line segment is formed to connect the midpoints of its i
Prasad Lakshman
Rao Ramana
Boudreau Leo
Mariam Daniel G.
The Regents of the University of California
Wilson Ray G.
LandOfFree
Multiscale characterization and analysis of shapes does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Multiscale characterization and analysis of shapes, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Multiscale characterization and analysis of shapes will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2828768