Ellipse-like curve recognition by calculation of distances of points on the curve from FOCI

• US 5,734,751 A
• Filed: 07/21/1995
• Issued: 03/31/1998
• Est. Priority Date: 07/22/1994
• Status: Expired due to Term

• Current Assignee: NEC Personal Computers, Ltd.
• Original Assignee: NEC Corporation
• Inventors: Saito, Shigeru
• Primary Examiner(s): JOHNS, ANDREW W
• Application Number:
  US08/505,537
• Time in Patent Office: 984 Days
• Field of Search: 382/181, 382/199, 382/203, 382/215, 382/242, 382/286, 382/288
• US Class Current: 382/203
• 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

After calculation of coordinates of points on a plane curve, a pattern recognition device calculates (S3) coordinates of foci and a major axis of a candidate ellipse and, (S4) until all points are used, (S5) a sum of distances between said point and the foci. After calculation of (S6) of the sum to the major axis, (S7) a variance of such ratios is calculated to judge (S8) whether or not the plane curve is a geometric ellipse. A mean value may be substituted for the variance. The variance may be calculated as regards sums calculated for all points. Preferably, the foci and the major axis are calculated by calculating (S1) an inscribed and subsequently (S2) a circumscribed rectangle. In this event, the candidate ellipse is inscribed in the circumscribed rectangle.

Claims

1. A pattern recognition method of recognizing an input pattern of a plane curve traced by an input device as an elliptic pattern, comprising the steps of:

calculating coordinates of points on said input pattern as a coordinate sequence;

calculating, by using said coordinate sequence, elliptic parameters including focus coordinates of foci of an ellipse;

calculating, by using said coordinate sequence and said focus coordinates, a sum of distances between each of said points and said foci;

subjecting said sum of distances to an algebraic calculation to calculate results of said algebraic calculation; and

evaluating an irregular distribution of said results as a similarity measure which said input pattern has relative to a geometric ellipse.

2. A pattern recognition method as claimed in claim 1, wherein said step of evaluating the irregular distribution comprises calculating a variance of said results in order to evaluate said irregular distribution.

3. A pattern recognition method as claimed in claim 2, wherein said step of evaluating the irregular distribution further comprises calculating an arithmetic mean value of the sums calculated by said step of calculating the said points the sum of distances, wherein each of said points are successively used one at a time.

4. A pattern recognition method as claimed in claim 3, wherein:

said step of calculating the elliptical parameters comprises calculating a length of a major axis;

said step of subjecting further comprises the steps of;

calculating a ratio of said sum of distances to said length of major axis; and

repeating said step of calculating the ratio until all of said points are used;

said pattern recognition method further comprising, between said step of calculating the ratio and said step of calculating the variance, the steps of;

checking whether said ratio is within a predetermined range;

suspending recognition of said input pattern when said ratio is outside said predetermined range; and

processing to said step of calculating the variance when said ratio is within said predetermined range.

5. A pattern recognition method as claimed in claim 4, wherein said predetermined range is between 0.85 and 1.15.

6. A pattern recognition method as claimed in claim 4, wherein said step of calculating elliptic parameters further comprises the steps of:

calculating, by using said coordinate sequence, an inscribed rectangle inscribed in said input pattern;

calculating, by using said coordinate sequence and said inscribed rectangle, a circumscribed rectangle circumscribing said input pattern; and

calculating, by using said coordinate sequence and said circumscribed rectangle, said focus coordinates and said length of major axis.

7. A pattern recognition method as claimed in claim 6, wherein said coordinates of points on said input pattern comprising x and y coordinates of each of said points in an orthogonal xy coordinate system, and wherein said step of calculating the inscribed rectangle further comprises the steps of:

calculating maximum and minimum x coordinates and maximum and minimum y coordinates among the x and y coordinates of said points;

calculating, as center x and y coordinates of a center of said inscribed rectangle, an x mean value of said maximum and said minimum x coordinates and a y mean value of said maximum and said minimum y coordinates;

calculating, by using said coordinate sequence and said maximum and said minimum x coordinates, y coordinates of two of four vertexes of said inscribed rectangle having said maximum and said minimum x coordinates as x coordinates of said two of four vertexes; and

calculating, by using said coordinate sequence and said maximum and said minimum y coordinates, x coordinates of two others of said four vertexes having said maximum and said minimum y coordinates as y coordinates of said two others of four vertexes;

whereby said inscribed rectangle is defined by the x and the y coordinates of said four vertexes.

8. A pattern recognition method as claimed in claim 7, wherein said step of calculating the circumscribed rectangle further comprises the steps of:

calculating, by using said center x and y coordinates and the x and the y coordinates of said four vertexes, orthogonal lines passing through said center of said inscribed rectangle parallel to inscribed sides, each inscribed side passing through two adjacent ones of said four vertexes; and

calculating, by using said coordinate sequence and said orthogonal lines, four points of intersection of said input pattern with said orthogonal lines;

whereby said circumscribed rectangle is defined by said orthogonal lines and said four points.

9. A pattern recognition method as claimed in claim 7, wherein said step of calculating the elliptic parameters further comprises the steps of:

calculating, by using said four points of intersection, a longer intercept and a shorter intercept of said input pattern with said orthogonal lines to use said longer intercept as said major axis; and

calculating said focus coordinates by using said orthogonal lines and said longer and said shorter intercepts;

whereby said elliptic parameters are defined by said focus coordinates and said longer and said shorter intercepts.

10. A pattern recognition method as claimed in claim 2, wherein:

said step of calculating elliptic parameters comprises calculating said focus coordinates and a length of a major axis of the ellipse having said foci;

said step of subjecting comprises calculating ratios as said results of algebraic calculation, each ratio being said sum of distances to said length of major axis.

11. A pattern recognition method as claimed in claim 10, wherein said step of calculating elliptic parameters further comprises the steps of:

calculating, by using said coordinate sequence, an inscribed rectangle inscribed in said input pattern;

calculating, by using said coordinate sequence and said inscribed rectangle, a circumscribed rectangle circumscribing said input pattern; and

calculating, by using said coordinate sequence and said circumscribed rectangle, said focus coordinates and said length of major axis.

12. A pattern recognition method as claimed in claim 11, wherein said coordinates of points on said input pattern comprising x and y coordinates of each of said points in an orthogonal x and y coordinate system, and wherein said step of calculating the inscribed rectangle further comprises the steps of:

calculating maximum and minimum x coordinates and maximum and minimum y coordinates among the x and y coordinates of said points;

calculating, as center x and y coordinates of a center of said inscribed rectangle, an x means value of said maximum and said minimum x coordinates and a y mean value of said maximum and said minimum y coordinates;

calculating, by using said coordinate sequence and said maximum and said minimum x coordinates, y coordinates of two of four vertexes of said inscribed rectangle having said maximum and said minimum x coordinates as x coordinates of said two of four vertexes; and

calculating, by using said coordinate sequence and said maximum and said minimum y coordinates, x coordinates of two others of said four vertexes having said maximum and said minimum y coordinates as y coordinates of said two others of four vertexes;

whereby said inscribed rectangle is defined by the x and the y coordinates of said four vertexes.

13. A pattern recognition method as claimed in claim 12, wherein said step of calculating the circumscribed rectangle further comprises the steps of:

calculating, by using said center x and y coordinates and the x and the y coordinates of each four vertexes, orthogonal lines passing through said center of said inscribed rectangle parallel to inscribed sides, each inscribed side passing through two adjacent ones of said four vertexes; and

calculating, by using said coordinate sequence and said orthogonal lines, four points of intersection of said input pattern with said orthogonal lines;

whereby said circumscribed rectangle is defined by said orthogonal lines and said four points.

14. A pattern recognition method as claimed in claim 13, wherein said step of calculating elliptic parameters further comprises the steps of:

calculating, by using said four points of intersection, a longer intercept and a shorter intercept of said input pattern with said orthogonal lines to use said longer intercept as said major axis; and

calculating said focus coordinates by using said orthogonal lines and said longer and said shorter intercepts;

whereby said elliptic parameters are defined by said focus coordinates and said longer and said shorter intercepts.

15. A pattern recognition method as claimed in claim 2, wherein said step of evaluating the irregular distribution patterns further comprises calculating as said results, sums calculated by said step of calculating the sum of distances, wherein each of said point is successively used one at a time.

16. A pattern recognition method as claimed in claim 1, wherein said input device comprisies one of the mouse and a pen input.

17. A pattern recognition device for recognizing an input pattern of a plane curve traced by an input device as an elliptic pattern, comprising:

means for calculating coordinates of points on said input pattern as a coordinate sequence;

means for using said coordinate sequence in calculating elliptic parameters including focus coordinates of foci of an ellipse;

means for using said coordinate sequence and said focus coordinates in calculating a sum of distances between each of said points and said foci;

means for subjecting said sum of distances to an algebraic calculation to calculate results of said algebraic calculation; and

means for evaluating an irregular distribution of said results as a similarity measure of said input pattern relative to a geometric ellipse.

18. A pattern recognition device as claimed in claim 17, wherein said means for evaluating calculates an arithmetic mean value of said results for use in evaluating said irregular distribution.

19. A pattern recognition device as claimed in claim 18, wherein said means for subjecting calculates as said results, sums calculated by said means for calculating the sum of distances, wherein each of said points is successively used one at a time.

20. A pattern recognition device as claimed in claim 17, wherein said means for evaluating the irregular distribution comprises means for calculating a variance of said results for use in evaluating said irregular distribution.

21. A pattern recognition device as claimed in claim 20, wherein:

said means for calculating elliptic parameters further comprises means for calculating said focus coordinates and a length of a major axis of the ellipse having said foci;

said means for subjecting being for calculating ratios as said results of algebraic calculation, each ratio being said sum of distances to said length of major axis.

22. A pattern recognition device as claimed in claim 21, wherein said means for calculating elliptic parameters further comprises:

means for using said coordinate sequence in calculating an inscribed rectangle inscribed in said input pattern;

means for using said coordinate sequence and said inscribed rectangle in calculating a circumscribed rectangle circumscribing said input pattern; and

means for using said coordinate sequence and said circumscribed rectangle in calculating said focus coordinates and said length of major axis.

23. A pattern recognition device as claimed in claim 22, wherein said coordinates of points comprising x and y coordinates of each of said points in an orthogonal xy coordinate system, and wherein said means for calculating the inscribed rectangle further comprises:

means for calculating maximum and minimum x coordinates and maximum and minimum y coordinates among the x and y coordinates of said points;

means for calculating, as center x and y coordinates of a center of said inscribed rectangle, an x mean value of said maximum and said minimum x coordinates and a y mean value of said maximum and said minimum y coordinates;

means for using said coordinate sequence and said maximum and said minimum x coordinates in calculating y coordinates of two of four vertexes of said inscribed rectangle having said maximum and said minimum x coordinates as x coordinates of said two of four vertexes; and

means for using said coordinate sequence and said y coordinates in calculating x coordinates of two others of said four vertexes having said maximum and said minimum y coordinates as y coordinates of said two others of said four vertexes;

whereby said inscribed rectangle is defined by the x and y coordinates of said four vertexes.

24. A pattern recognition device as claimed in claim 23, wherein said means for calculating the circumscribed rectangle further comprises:

means for using said center x and y coordinates and the x and the y coordinates of said four vertexes in calculating orthogonal lines passing through said center of said inscribed rectangle parallel to inscribed sides, each inscribed side passing through two adjacent ones of said four vertexes; and

means for using said coordinate sequence and said orthogonal lines in calculating four points of intersection of said input pattern with said orthogonal lines;

whereby said circumscribed rectangle is defined by said orthogonal lines and said four points.

25. A pattern recognition device as claimed in claim 24, wherein said means for calculating elliptic parameters further comprises:

means for using said four points of intersection in calculating a longer intercept and a shorter intercept of said input pattern with said orthogonal lines to use said longer intercept as said length of major axis; and

means for using said orthogonal lines and said longer and shorter intercepts in calculating said focus coordinates;

whereby said elliptic parameters are defined by said focus coordinates and said longer and shorter intercepts.

26. A pattern recognition device as claimed in claim 21, wherein:

said means for subjecting comprises;

means for calculating a ratio of said sum of distances to said length of major axis; and

means for repeatedly activating said ratio calculating means until all of said points are calculated;

said pattern recognition device further comprising, between said means for calculating the ratio and said means for calculating the variance

means for checking whether said ratio is within a predetermined range;

means for suspending operation of said means for subjecting and said means for evaluating when said ratio is outside said predetermined range; and

means for continuing operation of said means for subjecting and said means for evaluating when each of said ratios is within said predetermined range.

27. A pattern recognition device as claimed in claim 26, wherein said predetermined range is between 0.85 and 1.15.

28. A pattern recognition device as claimed in claim 26, wherein said means for calculating elliptic parameters further comprises:

means for using said coordinate sequence in calculating an inscribed rectangle inscribed in said input pattern;

means for using said coordinate sequence and said inscribed rectangle in calculating a circumscribed rectangle circumscribing said input pattern; and

means for using said coordinate sequence and said circumscribed rectangle in calculating said focus coordinates and said length of major axis.

29. A pattern recognition device as claimed in claim 26, wherein said coordinates of points on said input pattern comprising x and y coordinates of each of said points in an orthogonal xy coordinate system, and wherein said means for calculating the inscribed rectangle further comprises:

means for calculating maximum and minimum x coordinates and maximum and minimum y coordinates among the x and y coordinates of said points;

means for calculating, as center x and y coordinates of a center of said inscribed rectangle, an x mean value of said maximum and said minimum x coordinates and a y mean value of said maximum and said minimum y coordinates;

means for using said coordinate sequence and said maximum and said minimum x coordinates in calculating y coordinates of two of four vertexes of said inscribed rectangle having said maximum and said minimum x coordinates as x coordinates of said two of four vertexes; and

means for using said coordinate sequence and said maximum and said minimum y coordinates in calculating x coordinates of two others of said four vertexes having said maximum and said minimum y coordinates as y coordinates of said two others of said four vertexes;

whereby said inscribed rectangle is defined by the x and y coordinates of said four vertexes.

30. A pattern recognition device as claimed in claim 29, wherein said means for calculating the circumscribed rectangle further comprises:

means for using said center x and y coordinates and the x and the y coordinates of said four vertexes in calculating orthogonal lines passing through said center of said inscribed rectangle parallel to inscribed sides, each inscribed side passing through two adjacent ones of said four vertexes; and

means for using said coordinate sequence and said orthogonal lines in calculating four points of intersection of said input pattern with said orthogonal lines;

whereby said circumscribed rectangle is defined by said orthogonal lines and said four points.

31. A pattern recognition device as claimed in claim 30, wherein said means for calculating elliptic parameters further comprises:

means for using said four points of intersection in calculating a longer intercept and a shorter intercept of said input pattern with said orthogonal lines to use said longer intercept as said length of major axis; and

means for using said orthogonal lines and said longer and shorter intercepts in calculating said focus coordinates;

whereby said elliptic parameters are defined by said focus coordinates and said longer and shorter intercepts.

32. A pattern recognition device as claimed in claim 17, wherein said input device comprises one of a mouse and a pen input.

33. A programmed processor configured to perform pattern recognition of a traced input pattern of a plane curve as an elliptic pattern, comprising the steps of:

(a) calculating coordinates of points on said input pattern as a coordinate sequence;

(b) calculating elliptic parameters including focus coordinates and a major axis by using said coordinate sequence;

(c) calculating a sum of distances between one of said points on said traced input pattern and each of said focus coordinates by using said coordinate sequence and said focus coordinates;

(c) calculating a ratio of the sum of distances to the major axis;

(d) returning to step (c) until all of said points on said traced input pattern have been used as said one of said points on said traced input pattern;

(e) calculating a variance of said ratios; and

(f) using said variance to perform pattern recognition of said elliptic pattern.