US6393159B1
Expired / Lapsed
US
⏱️ 0.0 years remaining
Multiscale characterization and analysis of shapes
Assignee: University of California, San Diego
•
Filing: 1999-06-29
•
Granted: 2002-05-21
•
Expires: 2019-06-29
Abstract
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.
Inventors
- 👤 Lakshman Prasad
- 👤 Ramana Rao
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-09 21:56
CPC Classifications
G; G06; G06T; G06T17/00; G06T17/20; G06V; G06V10/00; G06V10/20; G06V10/34; G06V30/00; G06V30/10; G06V30/24; G06V30/248; G06V30/2504
Claims Analysis
Total Claims: 8
Claim 1
Independent Claim
222 words
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.
Claim 2
Dependent Claim
222 words
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.
Claim 3
Dependent Claim
36 words
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.
Claim 4
Dependent Claim
150 words
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.
Claim 5
Dependent Claim
150 words
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.
Claim 6
Dependent Claim
30 words
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.
Claim 7
Dependent Claim
80 words
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.
Claim 8
Dependent Claim
80 words
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.
References Cited (Backward Citations)
US5086482A
Cited
US5023920A
Cited
US5050229A
Cited
US5574803A
Cited
US5748865A
Cited
US6133921A
Cited
US6134353A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2005-05-20 | 2005-11-19 | 2006-05-21 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2009-05-20 | 2009-11-19 | 2010-05-21 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2013-05-20 | 2013-11-19 | 2014-05-21 | $7700.00 | Window Closed / Lapsed |