Characterization of corners of curvilinear segment

• US 6,072,502 A
• Filed: 06/25/1997
• Issued: 06/06/2000
• Est. Priority Date: 06/25/1997
• Status: Expired due to Term

• Current Assignee: Adobe Systems Incorporated (Adobe Inc.)
• Original Assignee: Adobe Systems Incorporated (Adobe Inc.)
• Inventors: Gupta, Naresh C.
• Primary Examiner(s): Powell, Mark R.
• Assistant Examiner(s): Harrison, Chante E.
• Application Number:
  US08/882,695
• Time in Patent Office: 1,077 Days
• Field of Search: 345/442, 345/441, 345/443
• US Class Current: 345/442
• CPC Class Codes: G06V 10/44 Local feature extraction by analysis of parts of the pattern, e.g. by detecting edges, contours, loops, corners, strokes or intersections; Connectivity analysis, e.g. of connected components

Abstract

A system determines discontinuities on a drawn curve. Local tangent values for a curvilinear segment are generated by determining the most likely tangent value for all points on the segment and by acting on a sampling of points around the current point whose tangent is to be determined. A robust statistical estimator is then applied to all angle values generated for the sample set to determine the likely intended tangent direction of the current focal point. The system then selects points with significant changes in tangent values to determine curve discontinuities such that the corners of the segment can be derived.

Claims

1. A computer-implemented method for characterizing data points in a two-dimensional space, comprising:

selecting a sequence of focal points from the data points and for each focal point calculating a local tangent value by;

selecting for the focal point a neighborhood of data points including the focal point,

selecting multiple pairs of points from among the points in the neighborhood and for each pair of points, calculating a component tangent value defined by the slope of a line defined by the pair of points, thereby calculating multiple component tangent values for the focal point,

estimating a local tangent value at the focal point based on the component tangents calculated for the neighborhood of the focal point.

2. The method of claim 1, wherein the data points are defined by a drawn curve, the drawn curve defining a sequence order for the data points.

3. The method of claim 1, wherein the component tangent value from point j to point k in the neighborhood is calculated in accordance with the expression:

space="preserve" listing-type="equation">arctan ((Y.sub.k- Y.sub.j)(X.sub.k- X.sub.j))

where X and Y are coordinates of points j and k.

4. The method of claim 1, wherein the estimating step generates a mode.

5. The method of claim 1, wherein the estimating step generates a mean.

6. The method of claim 1, wherein the estimating step generates a median.

7. The method of claim 2, further comprising:

identifying an edge of a corner in the drawn curve where a change in the local tangent angle at focal points along the drawn curve surpasses a predetermined threshold.

8. The method of claim 2, wherein the drawn is generated by a user gesture.

21. The method of claim 1, further comprising generating a tangent curve from the local tangent values calculated at the focal points in the sequence of focal points.

22. The method of claim 1, further comprising using the local tangent values to identify any corner points among the focal points.

23. The method of claim 2, further comprising using the local tangent values to identify any corner points among the focal points.

9. A memory device storing computer-readable instructions for aiding a computer to characterize a drawn segment defined by a plurality of points on a two-dimensional space, comprising instructions for:

selecting a focal point, the focal point having a local tangent value;

determining a plurality of tangent values around the focal point by forming a line between selected ones of the plurality of points that is spaced within a determined window of the focal point;

determining the local tangent value from the plurality of tangent values; and

determining likely transition points on the segment based on changes in the local tangent values of the focal points.

10. The memory device of claim 9, wherein the drawn segment is a curve.

11. The memory device of claim 9, wherein the component tangent value from point j to point k in the neighborhood is calculated in accordance with the expression:

space="preserve" listing-type="equation">arctan ((Y.sub.k- Y.sub.j)/(X.sub.k- X.sub.j))

where X and Y are coordinates of points j and k.

12. The memory device of claim 9, wherein the estimating instruction generates a mode.

13. The memory device of claim 9, wherein the estimating instruction generates a median.

14. The memory device of claim 9, wherein the estimating instruction generates a mean.

15. The memory device of claim 9, wherein the transition point identifying instruction determines the edge of a corner of the segment.

16. The memory device of claim 9, wherein the input sampling instruction samples user gestures.

17. A computer system for characterizing a drawn segment defined by a sequence of points on a two-dimensional space, comprising:

a display;

a user input device for receiving user input; and

a processor with instructions for;

selecting a sequence of focal points from the data points and for each focal point calculating a local tangent value by;

selecting for the focal point a neighborhood of data points including the focal point,

selecting multiple pairs of points from among the points in the neighborhood and for each pair of points, calculating a component tangent value defined by the slope of a line defined by the pair of points, thereby calculating multiple component target values for the focal point,

estimating a local tangent value at the focal point based on the component tangents calculated for the neighborhood of the focal point.

18. The computer system of claim 17, wherein the drawn segment is a curve.

19. The computer system of claim 18, wherein the estimating instruction generates a maximized mode.

20. The computer system of claim 18, wherein the component tangent value between points I and j is generated using the formula:

space="preserve" listing-type="equation">arctan ((Y.sub.k- Y.sub.j)/(X.sub.k- X.sub.j))

where X and Y are coordinates of points j and k.