Multiscale characterization and analysis of shapes

• US 6,393,159 B1
• Filed: 06/29/1999
• Issued: 05/21/2002
• Est. Priority Date: 06/29/1998
• Status: Expired due to Fees

• Current Assignee: Regents of the University of California (University of California)
• Original Assignee: Regents of the University of California (University of California)
• Inventors: Prasad, Lakshman, Rao, Ramana
• Primary Examiner(s): Boudreau, Leo
• Assistant Examiner(s): Mariam, Daniel G.
• Application Number:
  US09/345,599
• Time in Patent Office: 1,057 Days
• Field of Search: 382/181, 382/195, 382/203, 382/204, 382/206, 382/241, 382/254, 382/256, 382/257, 382/258, 382/259, 382/266, 382/308, 345/418, 345/419, 345/420, 345/423
• US Class Current: 382/259
• CPC Class Codes: G06T 17/20 Finite element generation, e.g. wire-frame surface description, tesselation
• CPC Class Codes: G06V 10/34 Smoothing or thinning of the pattern; Morphological operations; Skeletonisation
• CPC Class Codes: G06V 30/2504 Coarse or fine approaches, e.g. resolution of ambiguities or multiscale approaches

Abstract

An adaptive multiscale method approximates shapes with continuous or uniformly and densely sampled contours, with the purpose of sparsely and nonuniformly discretizing the boundaries of shapes at any prescribed resolution, while at the same time retaining the salient shape features at that resolution. In another aspect, a fundamental geometric filtering scheme using the Constrained Delaunay Triangulation (CDT) of polygonized shapes creates an efficient parsing of shapes into components that have semantic significance dependent only on the shapes'"'"' structure and not on their representations per se. A shape skeletonization process generalizes to sparsely discretized shapes, with the additional benefit of prunability to filter out irrelevant and morphologically insignificant features. The skeletal representation of characters of varying thickness and the elimination of insignificant and noisy spurs and branches from the skeleton greatly increases the robustness, reliability and recognition rates of character recognition algorithms.

Claims

1. A computer implemented method for determining a skeletonized representation of a shape having a boundary comprising the steps of:

forming a set of maximal discs within the boundary of the shape;

determining maximal chords of tangency for each maximal disc in the set of maximal discs;

determining a set of all ordered pairs (p,δ

) of the maximal chords of tangency, where p and δ

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;

determining a set of unordered triples of the ordered pairs of maximal chords of tangency of the maximal discs that are tangent to the shape at exactly three points;

successively connecting the midpoints of adjacent maximal chords of tangency of the maximal discs 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; and

connecting the skeletal features 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 so that a connected skeletal representation of the shape is formed.

2. A computer implemented method according to claim 1, further including the step of pruning the skeletal representation by not connecting the midpoint of a terminal maximal chord of tangency to eliminate an associated shape feature.

3. A computer implemented method for determining a skeletonized representation of a shape having a boundary comprising the steps of:

forming a discretized multi-scale representation of a shape using a Haar wavaelet tranform;

forming a Constrained Delaunay Triangulation (CDT) of the discretized representation to define termination triangles (T-triangles) having two external edges and one internal edge, sleeve triangles (S-triangles) having one external edge and two external edges, and junction triangles (J-triangles) having no external edges and three internal edges;

for each S-triangle, form a line segment connecting midpoints of its two internal edges, wherein the line segments of adjacent S-triangles form a continuous chain of line segments that terminate at an internal edge of a T-triangle or a J-triangle;

for each J-triangle, form line segments connecting a midpoint of each smaller triangle side to a midpoint of the longest side so that a connected skeletal representation of the shape is obtained.

4. A computer implemented method according to claim 3, further including the step of pruning the connected skeletal representation to delete limbs having a morphological significance below a threshold value.

5. A computer implemented method for characterizing a shape comprising the steps of:

forming a Constrained Delauney Triangulation (CDT) polygonal representation of the shape having morphological features;

characterizing each triangle of the CDT as a termination triangle (T-triangle) having two external edges, a sleeve triangle (S-triangle) having two external edges, or a junction triangle (J-triangle) having no external edges; and

counting the number of T-triangles and the number of S-triangles to completely characterize the morphological features of the CDT polygonal representation.