Method and apparatus for describing a character image based on its contours, and for classifying the character image for character recognition based on a resulting contour-based description of the character image

• US 5,426,712 A
• Filed: 04/19/1993
• Issued: 06/20/1995
• Est. Priority Date: 04/20/1992
• Status: Expired due to Term

• Current Assignee: Ricoh Company Limited
• Original Assignee: Ricoh Company Limited
• Inventors: Nakajima, Yuh
• Primary Examiner(s): Couso, Jose L.
• Application Number:
  US08/047,411
• Time in Patent Office: 792 Days
• Field of Search: 382/22, 382/25, 382/48, 382/56
• US Class Current: 382/199
• CPC Class Codes: G06V 30/10 Character recognition
• CPC Class Codes: G06V 30/182 by coding the contour of the pattern

Abstract

A code set includes a first type of code for indicating a maximal point of a contour of an image, and a second type of code for indicating a minimal point of the contour of the image. The code set may include a third type of code for indicating a state of a switching pair which is a pair of a maximal point and a minimal point on the contours. Each of contours of are described by arrangement of the first type code and the second type of code or a combination of the third code and the arrangement of the first type of code and the second type of code. Each of the first and second types of codes may comprises a convex type of code and a concave type of code, the convex type of code indicating the maximal point on the contour of a convex part of the image, and the concave type of code indicating the maximal point on the contour of a concave part of the image.

Claims

1. A method for describing a character image based on its contours, to classify the character image for character recognition based on a resulting contour-based description of the character image, the method carried out by an apparatus having (1) a read-write memory and (2) a central processing unit (CPU) which controls how binary image data representing the character image is written to and read from the read-write memory, the method comprising the steps of:

(a) extracting one or more contours of the image by reading into the CPU, binary image data previously written into the read-write memory, so as to arrive at contour data;

(b) tracing each of the contours in a predetermined direction by using the CPU to process the contour data;

(c) detecting a maximal point and a minimal point from the contour data, by using the CPU;

wherein;

c1) the maximal point is defined as a domain A formed of one or more points on the contour C of the image on an X-Y coordinate system satisfying the conditions;

space="preserve" listing-type="equation"> pε

A, y(p)=a

     1)

space="preserve" listing-type="equation"> N(A), pε

N(A)∩

A.sup.C ∩

C, y(p)<

a;

     2)

c2) the minimal point is defined as a domain A formed of one or more points on the contour C of the image on the X-Y coordinate system satisfying the conditions;

space="preserve" listing-type="equation"> pε

A, y(p)=a

     3)

space="preserve" listing-type="equation"> N(A), pε

N(A)∩

A.sup.C ∩

C, y(p)>

a;

     4)

c3) p indicates a point on the contour,

c4) a is a constant,

c5) y(p) is a y-coordinate value of the point p,

c6) N(A) indicates a neighborhood of the domain A, and

c7) A^C indicates a complementary set of the domain A;

(d) using the CPU, arranging codes according to an order detected in the detecting step, to arrive at an ordered arrangement of the codes including a first type of code indicating the maximal point and a second type of code indicating the minimal point, so that each contour of the image is described by the ordered arrangement; and

(e) carrying out a classification of the character image by using the CPU to process the ordered arrangement, to arrive at a character recognition result based on the classification.

2. The method as claimed in claim 1, wherein a convex type of code and a concave type of code both of which belong to said first type of code are distinguished from each other in the arrangement of said first type of code in said step (d), said convex type of code indicating the maximal point on the contour of a convex part of the image, and said concave type of code indicating the maximal point on the contour of a concave part of the image.

3. The method as claimed in claim 2, wherein a convex type of code and a concave type of code both of which belong to said second type of code are distinguished from each other in the arrangement of said second type of code in said step (d), said convex type of code indicating the minimal point on the contour of a convex part of the image, and said concave type of code indicating the minimal point on the contour of a concave part of the image.

4. The method as claimed in claim 3, further comprising a step of:

(e) computing a third type of code indicating for indicating a state of a switching pair which is a pair of a maximal point and a minimal point on the contours, the maximal point and the minimal point satisfying conditions (1) and (2);

space="preserve" listing-type="equation">N.sub.+ (a;

b)=±

2 (either +2 or -2) (1)

space="preserve" listing-type="equation">N.sub.- (a;

b)=±

2 (either +2 or -2) (2)

where a indicating the minimal point and b indicating the maximal point and N₊ (a;

b) and N_- (a;

b) are defined as,

space="preserve" listing-type="equation">N.sub.+ (a;

b)=N.sub.+1 -N.sub.+2

space="preserve" listing-type="equation">N.sub.- (a;

b)=N.sub.-1 -N.sub.-2

where N₊₁ is a number of points belonging to the convex type of code which points are obtained when the contour is traced from the minimal point a to the maximal point b in a first direction, N₊₂ is a number of points belonging to the concave type of code which points are obtained when the contour is traced from the minimal point a to the maximal point b in the first direction, N_-1 is a number of points belonging to the convex type of code which points are obtained when the contour is traced from the minimal point a from the maximal point in a second direction opposite to the first direction, and N_- is a number of points belonging to the concave type of code which points are obtained when the contour is traced from the minimal point a from the maximal point b in the second direction, whereby each contour of the image is described by the first, second and third types of code.

5. A system for describing a character image based on its contours, to classify the character image for character recognition based on a resulting contour-based description of the character image, the system comprising:

A) a read-write memory; and

B) a central processing unit (CPU) which controls how binary image data representing the character image is written to and read from the read-write memory, the CPU including;

(a) means for extracting one or more contours of the image by reading into the CPU, binary image data previously written into the read-write memory, so as to arrive at contour data;

(b) means for tracing each of the contours in a predetermined direction by using the CPU to process the contour data;

(c) means for detecting a maximal point and a minimal point from the contour data, by using the CPU;

wherein;

c1) the maximal point is defined as a domain A formed of one or more points on the contour C of the image on an X-Y coordinate system satisfying the conditions;

space="preserve" listing-type="equation"> pε

A, y(p)=a

     1)

space="preserve" listing-type="equation"> N(A), pε

N(A)∩

A.sup.C ∩

C, y(p)<

a;

     2)

c2) the minimal point is defined as a domain A formed of one or more points on the contour C of the image on the X-Y coordinate system satisfying the conditions;

space="preserve" listing-type="equation"> pε

A, y(p)=a

     1)

space="preserve" listing-type="equation"> N(A), pε

N(A)∩

A.sup.C ∩

C, y(p)>

a;

     2)

c3) p indicates a point on the contour,

c4) a is a constant,

c5) y(p) is a y-coordinate value of the point p,

c6) N(A) indicates a neighborhood of the domain A, and

c7) A^C indicates a complementary set of the domain A;

(d) means for arranging codes according to an order detected in the detecting means, to arrive at an ordered arrangement of the codes including a first type of code indicating the maximal point and a second type of code indicating the minimal point, so that each contour of the image is described by the ordered arrangement; and

(e) means for carrying out a classification of the character image by using the CPU to process the ordered arrangement, to arrive at a character recognition result based on the classification.

6. The method as claimed in claim 5, wherein said first type of code comprises a convex type of code and a concave type of code, said convex type of code indicating the maximal point on the contour of a convex part of the image, and said concave type of code indicating the maximal point on the contour of a concave part of the image.

7. The method as claimed in claim 6, wherein said second type of code comprises a convex type of code and a concave type of code, said convex type of code indicating the minimal point on the contour of a convex part of the image, and said concave type of code indicating the minimal point on the contour of a concave part of the image.

8. The method as claimed in claim 7, further comprising a step of:

computing means for computing a third type of code indicating for indicating a state of a switching pair which is a pair of a maximal point and a minimal point on the contours, the maximal point and the minimal point satisfying conditions (1) and (2);

space="preserve" listing-type="equation">N.sub.+ (a;

b)=±

2 (either +2 or -2) (1)

space="preserve" listing-type="equation">N.sub.- (a;

b)=±

2 (either +2 or -2) (2)

where a indicating the minimal point and b indicating the maximal point and N₊ (a;

b) and N_- (a;

b) are defined as,

space="preserve" listing-type="equation">N.sub.+ (a;

b)=N.sub.+1 -N.sub.+2

space="preserve" listing-type="equation">N.sub.- (a;

b)=N.sub.-1 -N.sub.-2

where N₊₁ is a number of points belonging to the convex type of code which points are obtained when the contour is traced from the minimal point a to the maximal point b in a first direction, N₊₂ is a number of points belonging to the concave type of code which points are obtained when the contour is traced from the minimal point a to the maximal point b in the first direction, N_-1 is a number of points belonging to the convex type of code which points are obtained when the contour is traced from the minimal point a from the maximal point in a second direction opposite to the first direction, and N_- is a number of points belonging to the concave type of code which points are obtained when the contour is traced from the minimal point a to the maximal point b in the second direction, whereby each contour of the image is described by the first, second and third types of code.