Pattern recognition method

• US 4,961,231 A
• Filed: 12/31/1987
• Issued: 10/02/1990
• Est. Priority Date: 01/20/1987
• Status: Expired due to Fees

• Current Assignee: Ricoh Company Limited
• Original Assignee: Ricoh Company Limited
• Inventors: Nakayama, Hiroshi, Kojima, Keiji, Sato, Gen
• Primary Examiner(s): Moore, David K.
• Assistant Examiner(s): Couso, Jose L.
• Application Number:
  US07/140,131
• Time in Patent Office: 1,006 Days
• Field of Search: 382/21, 382/22, 382/25, 382/27, 382/30, 382/34, 382/48, 358/462, 358/464
• US Class Current: 382/197
• CPC Class Codes: G06T 9/20 Contour coding, e.g. using detection of edges
• CPC Class Codes: G06V 30/10 Character recognition
• CPC Class Codes: G06V 30/1823 using vector-coding

Abstract

A pattern recognition method comprises a contour tracing step of a contour of a binary image in a predetermined direction along a predetermined type of pixels. At this time, four adjacent pixels on upper, lower, left-hand and right-hand sides of a point of interest are sequentially checked. Then, one pixel of a predetermined type out of the four adjacent pixels which is the first pixel of the predetermined type found by the check is designated as a next trace point subsequent to the point of interest. In this process, a feature of each of the traced pixels is extracted. The feature is represented by a directional code which indicates a direction of motion from the point of interest to the next trace point. The features are successively registered in a one-dimensional form. Histogram is produced for each sub-region storing a part of the one-dimensional feature sequence. A histogram for each sub-region is compared with a related reference histogram for a known character.

Claims

1. A pattern recognition method comprising the steps of:

detecting a first change in type between two consecutive pixels in a direction of a raster-scan which is carried out for a binary image of an unknown pattern, one of said two consecutive pixels being designated as a start point from which a trace of a contour of said binary image starts;

tracing said contour of said binary image in a predetermined direction along a predetermined type of pixels in such a way that four adjacent pixels on upper, lower, left-hand and right-hand sides of a point of interest are checked in a direction starting from one pixel out of said four adjacent pixels which is positioned on a predetermined side at an angle of 90 degrees with respect to a moving direction in which the trace proceeded towards said point of interest and that one pixel of a predetermined type out of said four adjacent pixels which is first found by checking said four adjacent pixels in said direction is designated as a next trace point subsequent to said point of interest;

extracting a feature of each of the pixels at the traced points which form an image of said contour of said pattern; and

identifying said unknown pattern by comparing said features or said unknown pattern with features of a known pattern.

2. A pattern recognition method as claimed in claim 1, wherein said detecting step detects a first change in color from white to black and a white pixel of said two consecutive pixels is designated as said start point, and said tracing step traces said contour of said binary image in a counterclockwise direction along white pixels in such a way that four adjacent pixels on upper, lower, left-hand and right-hand sides of said point of interest are sequentially checked in the clockwise direction starting from said one pixel positioned on the left-hand side at an angle of 90°

with respect to said moving direction in which the trace proceeded towards said point of interest and that a white pixel which is one of said four adjacent pixels and which is the first white pixel found by the clockwise check is designated as the trace point subsequent to said point of interest.

3. A pattern recognition method as claimed in claim 1, wherein said detecting step detects a change of color from white to black and a white pixel of said two consecutive pixels is designated as the start point, and said tracing step traces said contour of said binary image in a clockwise direction along white pixels in such a way that four adjacent pixels on upper, lower, left-hand and right-hand sides of said point of interest are sequentially checked in the counterclockwise direction starting from said one pixel positioned on the right-hand side at an angle of 90°

with respect to said moving direction in which the trace proceeded towards said point of interest and that a white pixel which is one of said four adjacent pixels and which is the first white pixel found by the counterclockwise check is designated as the trace point subsequent to said point of interest.

4. A pattern recognition method as claimed in claim 1, wherein said detecting step detects a first change in color from white to black and a black pixel of said two consecutive pixels is designated as the start point, and said tracing step traces said contour of said binary image in a counterclockwise direction along black pixels in such a way that four adjacent pixels on upper, lower, left-hand and right-hand sides of said point of interest are sequentially checked in the counterclockwise direction starting from said one pixel positioned on the right-hand side at an angle of 90°

with respect to said moving direction in which the trace proceeded towards said point of interest and that a black pixel which is one of said four adjacent pixels and which is the first pixel found by the counterclockwise check is designated as the trace point subsequent to said point of interest.

5. A pattern recognition method as claimed in claim 1, wherein said detecting step detects a first change in color from a white pixel and a black pixel of said two consecutive pixels is designated as the start point, and said tracing step traces said contour of said binary image in a clockwise direction along black pixels in such a way that four adjacent pixels on upper, lower, left-hand and right-hand sides of said point of interest are sequentially checked in the clockwise direction starting from said one pixel positioned on the left-hand side at an angle of 90 degrees with respect to said moving direction in which the trace proceeded towards said point of interest and that a black pixel which is one of said four adjacent pixels and which is the first black pixel found by the clockwise check is designated as the trace point subsequent to said point of interest.

6. A pattern recognition method as claimed in claim 2, wherein at the commencement of said tracing steps, said start point is designated as the point of interest and said moving direction in which the trace proceeded towards said trace point is assigned to be a direction opposite to a direction of said raster scan.

7. A pattern recognition method as claimed in claim 3, wherein at the commencement of said tracing steps, said start point is designated as the point of interest and said moving direction in which the the trace proceeded towards said trace point is assumed to be a direction opposite to a direction of said raster scan.

8. A pattern recognition method as claimed in claim 4, wherein at the commencement of said tracing steps, said start point is designated as the point of interest and said moving direction in which the the trace proceeded towards said trace point is assumed to be a direction identical to a direction of said raster scan.

9. A pattern recognition method as claimed in claim 5, wherein at the commencement of said tracing steps, said start point is designated as the point of interest and said moving direction in which the the trace proceeded towards said trace point is assumed to be a direction identical to a direction of said raster scan.

10. A pattern recognition method as claimed in claim 2, wherein in said tracing step, when said white pixel is the fourth pixel in said clockwise check, said white pixel is concluded to be a noise and is neglected.

11. A pattern recognition method as claimed in claim 3, wherein in said tracing step, when said white pixel is the fourth pixel in said counterclockwise check said white pixel is concluded to be a noise and is neglected.

12. A pattern recognition method as claimed in claim 4, wherein in said tracing step, when said white pixel is the fourth pixel in said counterclockwise check, said black pixel is concluded to be a noise and is neglected.

13. A pattern recognition method as claimed in claim 5, wherein in said tracing step, when said white pixel is the fourth pixel in said clockwise check, said black pixel is concluded to be a noise and is neglected.

14. A pattern recognition method comprising the steps of:

detecting a change in type between two consecutive pixels in a direction of a raster-scan which is carried out for a binary image of an unknown pattern, one of said two consecutive pixels being designated as a start point from which trace of a contour of said binary image starts;

tracing said contour of said binary image in a predetermined direction along a predetermined type of pixels in such a way that four adjacent pixels on upper, lower, left-hand and right-hand sides of a point of interest are checked in a predetermined rotational direction starting from one pixel out of said four adjacent pixels which is positioned on a predetermined side at an angle of 90°

with respect to a moving direction in which the trace proceeded towards said point of interest and that one pixel of a predeterminted type out of said four adjacent pixels which is first found by said check is designated as a next trace point following said point of interest;

extracting a feature of each of the pixels at the traced points which form an image of said contour of said pattern, said feature being a directional code which indicates a moving direction from said point of interest to said next trace point; and

identifying said unknown pattern by comparing said features of said unknown pattern with features of a known pattern.

15. A pattern recognition method as claimed in claim 14, wherein said detecting step detects a first change in color from white to black and a white pixel of said two consecutive pixels is designated as said start point, and said tracing step traces said contour of said binary image in a counterclockwise direction along white pixels in such a way that four adjacent pixels on upper, lower, left-hand and right-hand sides of said point of interest are sequentially checked in the clockwise direction starting from said one pixel positioned on the left-hand side at an angle of 90°

with respect to said moving direction in which the trace proceeded towards said point of interest and that a white pixel which is one of said four adjacent pixels and which is the first white pixel found by the clockwise check is designated as the trace point subsequent to said point of interest.

16. A pattern recognition method as claimed in claim 14, wherein said detecting step detects a change of color from white to black and a white pixel of said two consecutive pixels is designated as the start point, and said tracing step traces said contour of said binary image in a clockwise direction along white pixels in such a way that four adjacent pixels on upper, lower, left-hand and right-hand sides of said point of interest are sequentially checked in the counterclockwise direction starting from said one pixel positioned on the right-hand side at an angle of 90°

with respect to said moving direction in which the trace proceeded towards said point of interest and that a white pixel which is one of said four adjacent pixels and which is the first white pixel found by the counterclockwise check is designated as the trace point subsequent to said point of interest.

17. A pattern recognition method as claimed in claim 14, wherein said detecting step detects a first change in color from white to black and a black pixel of said two consecutive pixels is designated as the start point, and said tracing step traces said contour of said binary image in a counterclockwise direction along black pixels in such a way that four adjacent pixels on upper, lower, left-hand and right-hand sides of said point of interest are sequentially checked in the counterclockwise direction starting from said one pixel positioned on the right-hand side at an angle of 90°

with respect to said moving direction in which the trace proceeded towards said point of interest and that a black pixel which is one of said four adjacent pixels and which is the first pixel found by the counterclockwise check is designated as the trace point subsequent to said point of interest.

18. A pattern recognition method as claimed in claim 14, wherein said detecting step detects a first change in color from white to pixel and a black pixel of said two consecutive pixels is designated as the start point, and said tracing step traces said contour of said binary image in a clockwise direction along black pixels in such a way that four adjacent pixels on upper, lower, left-hand and right-hand sides of said point of interest are sequentially checked in the clockwise direction starting from said one pixel positioned on the left-hand side at an angle of 90°

with respect to said moving direction in which the trace proceeded towards said point of interest and that a black pixel which is one of said four adjacent pixels and which is the first black pixel found by the clockwise check is designated as the trace point subsequent to said point of interest.

19. A pattern recognition method as claimed in claim 15, wherein at the commencement of said tracing steps, said start point is designated as the point of interest and said moving direction in which the trace proceeded towards said trace point is assigned to be a direction opposite to a direction of said raster scan.

20. A pattern recognition method as claimed in claim 16, wherein at the commencement of said tracing steps, said start point is designated as the point of interest and said moving direction in which the the trace proceeded towards said trace point is assumed to be a direction opposite to a direction of said raster scan.

21. A pattern recognition method as claimed in claim 17, wherein at the commencement of said tracing steps, said start point is designated as the point of interest and said moving direction in which the the trace proceeded towards said trace point is assumed to be a direction identical to a direction of said raster scan.

22. A pattern recognition method as claimed in claim 18, wherein at the commencement of said tracing steps, said start point is designated as the point of interest and said moving direction in which the the trace proceeded towards said trace point is assumed to be a direction identical to a direction of said raster scan.

23. A pattern recognition method as claimed in claim 15, wherein in said tracing step, when said white pixel is the fourth pixel in said clockwise check, said white pixel is concluded to be a noise and is neglected.

24. A pattern recognition method as claimed in claim 16, wherein in said tracing step, when said white pixel is the fourth in said counterclockwise check, said white pixel is concluded to be a noise and is neglected.

25. A pattern recognition method as claimed in claim 17, wherein in said tracing step, when said white pixel is the fourth in said counterclockwise check, said white pixel is concluded to be a noise and is neglected.

26. A pattern recognition method as claimed in claim 18, wherein in said tracing step, when said white pixel is the fourth in said clockwise check, said white pixel is concluded to be a noise and is neglected.

27. A pattern recognition method comprising the steps of:

tracing a contour of a binary image of an unknown pattern which is obtained by a raster-scan;

extracting a feature of each of pixels at said contour which form an image of said contour of said unknown pattern;

registering said feature of each of pixels in a memory region in order of appearance of said feature, so that a one-dimensional code sequence is registered in said memory region;

dividing said memory region which stores said one-dimensional code sequence into a plurality of one-dimensional sub-regions, each including a plurality of partial code sequences;

calculating a feature quantity for each of sub-regions; and

identifying said unknown pattern by comparing said feature quantity for each sub-region of said unknown pattern with a feature quantity for each respective sub-region of a known pattern.

28. A pattern recognition method as claimed in claim 27, wherein at said dividing step, said memory region which stores said one-dimensional code sequence is equally divided into the plurality of one-dimensional sub-regions.

29. A pattern recognition method as claimed in claim 27, wherein at said dividing step, the one-dimensional code sequence is divided into partial code sequences and forms sub-regions in which there are combined at least m (m is an integer equal to 3 or over) consecutive partial code sequences in such a way that partial directional codes at the beginning and end thereof are commonly owned by the mutually adjacent sub-regions.

30. A pattern recognition method as claimed in claim 27, wherein said feature quantity is a histogram indicating a total number for each respective directional code for each sub-region.

31. A pattern recognition method as claimed in claim 27, wherein said tracing step comprises

a first step of detecting a first scanned pixel immediately followed by a pixel of a type opposing a type of said first scanned pixel in a direction of a raster-scan which is carried out for a binary image of an unknown pattern, said first scanned pixel being designated as a start point from which trace of a contour of said binary image starts;

and

a second step of tracing said contour of said binary image in a predetermined direction along a predetermined type of pixels in such a way that four adjacent pixels on upper, lower, left-hand and right-hand sides of a point of interest are checked in a predetermined rotational direction starting from one pixel out of said four adjacent pixels which is positioned on a predetermined side at an angle of 90 degrees with respect to a moving direction in which the trace proceeded towards said point of interest and that one pixel of a predetermined type out of said four adjacent pixels which is first obtained by checking said four adjacent pixels in said predetermined rotational check is designated as a next trace point subsequent to said point of interest.