Method of tracing contour and a system therefor

• US 4,956,869 A
• Filed: 02/10/1988
• Issued: 09/11/1990
• Est. Priority Date: 02/20/1987
• Status: Expired due to Term

• Current Assignee: Hitachi, Ltd.
• Original Assignee: Hitachi, Ltd.
• Inventors: Matsushima, Hitoshi, Miyatake, Takafumi
• Primary Examiner(s): Moore, David K.
• Assistant Examiner(s): Razavi, Michael
• Application Number:
  US07/154,378
• Time in Patent Office: 944 Days
• Field of Search: 382/21, 382/22, 382/26, 382/60, 358/101, 358/106
• US Class Current: 382/242
• CPC Class Codes: G06T 2207/10008 from scanner, fax or copier
• CPC Class Codes: G06T 2207/30176 Document
• CPC Class Codes: G06T 7/12 Edge-based segmentation
• CPC Class Codes: G06T 9/20 Contour coding, e.g. using detection of edges
• CPC Class Codes: G06V 10/46 Descriptors for shape, contour or point-related descriptors, e.g. scale invariant feature transform [SIFT] or bags of words [BoW]; Salient regional features colour feature extraction G06V10/56

Abstract

A system for tracing contour to prepare contour coordinates by tracing contour lines of a figure from an image that consists of a set of a plurality of lines, comprising a memory stored in advance from a basic pattern related to figure contour lines of positions of image transistion points between the neighboring two lines. An image transition point of a line is detected and another image transition point of a line that precedes the above line is detected, too. A pattern of image transistion points of the above two lines is extracted based upon the basic pattern. The thus extracted basic patterns are then integrated and are converted into contour coordinates.

Claims

1. A method of tracing a contour to obtain contour coordinates by extracting segments of a contour of a figure from a sampled image, comprising the steps of:

scanning said figure along sequential scanning lines in a single scanning direction;

detecting at least one image transition point for each sequential scanning line through said figure;

extracting segments of the contour of the figure by comparing a detected relationship between the position of an image transition point of each scanning line and the position of an image transition point of the adjacent preceding scanning line to a plurality of basic patterns representing different positional relationship and selecting a basic pattern corresponding to each detected relationship along the contour of the figure;

combining selected basic patterns into a basic pattern sequence on the basis of the positions of the detected image transition points; and

converting said basic pattern sequence into a sequence of contour coordinates.

2. A method of tracing a contour according to claim 1, wherein said plurality of basic patterns comprise ten basic patterns which represent the different possible image transition point positional relationships to be found in the contour of any figure.

3. A method of tracing a contour according to claim 2, wherein each of said basic patterns consists of at least one of three vectors of which at least the first and third vectors have a direction crossing the direction of the scanning line.

4. A method of tracing a contour according to claim 3, wherein the direction crossing the direction of said scanning line is almost perpendicular to said scanning line.

5. A method of tracing a contour according to claim 3, wherein said first and third vectors having a fixed unit length and said second vector in the direction of the scanning line has a variable length.

6. A method of tracing a contour according to claim 5, wherein the direction of said second vector is almost horizontal and the direction of said first and third vectors is almost vertical.

7. A system for tracing a contour to obtain contour coordinates by extracting segments of a contour of a figure from a sampled image, comprising:

means for scanning said figure along sequential scanning lines in a single scanning direction;

means for detecting at least one image transition point for each sequential scanning line through said figure;

means for extracting segments of the contour of the figure by comparing a detected relationship between the position of an image transition point of each scanning line and the position of an image transition point of the adjacent preceding scanning line to a plurality of basic patterns representing different positional relationships and for selecting a basic pattern corresponding to each detected relationship along the contour of the figure;

means for combining selected basic patterns into a basic pattern sequence on the basis of the positions of the detected image transition points; and

means for converting said basic pattern sequence into a sequence of contour coordinates.

8. A system for tracing a contour according to claim 7, wherein said extracting means is an automaton responsive to signals from said adjacent scanning lines.