Method of extracting feature from line pattern and line pattern recognition method using the same

A method of extracting a feature from a line pattern comprising the steps of:

• (a) extracting a thinned line from the line pattern, said thinned line being represented by branches which are partitioned from each other by vertices;
• (b) finding one or a plurality of singular points which are formed on said thinned line, each of said singular points being defined as a vertex to which three or more branches are connected;
• (c) decomposing each of said singular points into a number of vertices that is the same as the number of branches connected thereto, based on a presumption that each of said singular points is included in all the branches connected to each of said singular points, wherein each of said vertices has the same coordinate as a corresponding singular point;
• (d) selecting vertices regarded as being identical to each other from the vertices obtained in said step (c), based on conditions in which the branches are connected to each of said singular points, wherein branches including the selected vertices are connected to each other, so that strokes are generated, each stroke having branches successively connected to each other;
• (e) converting each of the strokes into a primitive sequence obtained by a concatenation of primitives, each of which is a monotone curve, said monotone curve being a curve which is either non-increasing or non-decreasing;
• and
• (f) generating a binary relation between each two primitive sequences obtained by said step (e);
• wherein the line pattern is characterized by a combination of primitive sequences obtained by said step (e) and said binary relation between each of the primitive sequences.

A line pattern recognition method comprising the steps of:

• (a) extracting a thinned line from the line pattern, said thinned line being represented by branches which are partitioned from each other by vertices;
• (b) finding one or a plurality of singular points which are formed on said thinned line, each of said singular points being defined as a vertex to which three or more branches are connected;
• (c) decomposing each of said singular points into a number of vertices that is the same as the number of branches connected thereto, based on a presumption that each of said singular points is included in all the branches connected to each of said singular points, wherein each of said vertices has the same coordinate as a corresponding singular point;
• (d) selecting vertices regarded as being identical to each other form the vertices obtained in said step (c), based on conditions in which the branches are connected to each of said singular points, wherein branches include the selected vertices are connected to each other, so that strokes are generated, each stroke having branches successively connected to each other;
• (e) converting each of the strokes into a primitive sequence obtained by a concatenation of primitives, each of which is a monotone curve, said monotone curve being a curve which is either non-increasing or non-decreasing;
• (f) generating a binary relation between each two primitive sequences obtained by said step (e), so that the line pattern is featured by a combination of primitive sequences obtained by said step (e) and said binary relation between each of the primitive sequences;
• and
• (g) comparing a line pattern featured by a combination of primitive sequences obtained by said step (e) and said binary relation between each of the primitive sequences obtained by said step (f), with each of the standard models describing primitive sequences and the binary relation between each two primitive sequences, so that a matching of said line pattern and said standard models is performed on the basis of structural matching;
• wherein a result of said matching is a result of a recognition of said line pattern.