Character and pattern recognition machine and method

• US 4,837,842 A
• Filed: 09/19/1986
• Issued: 06/06/1989
• Est. Priority Date: 09/19/1986
• Status: Expired due to Fees

• Current Assignee: Arthur W. Holt
• Original Assignee: Arthur W. Holt
• Inventors: Holt, Arthur W.
• Primary Examiner(s): Groody, James J.
• Assistant Examiner(s): NOT, DEFINED
• Application Number:
  US06/909,388
• Time in Patent Office: 991 Days
• Field of Search: 382/7, 382/9, 382/14, 382/15, 382/18, 382/21, 382/25, 382/26, 382/30, 382/34, 382/36, 382/22, 382/19, 235/379
• US Class Current: 382/204
• CPC Class Codes: G06F 18/00 Pattern recognition
• CPC Class Codes: G06V 30/191 Design or setup of recognition systems or techniques; Extraction of features in feature space; Clustering techniques; Blind source separation

Abstract

A pattern recognition system, particularly a handprint character recognition system in which electrical binary black/white "image" of one or more handprinted characters is formed and a plurality of centers of recognition (CORs) within said binary black/white images are selected as reference points for measuring the characteristic enclave of the black/white image immediately surrounding the CORs. A library of templates of said measurements around the CORs for a plurality of known exemplary character images is stored in a memory for comparison with corresponding measurements made around the CORs of images whose class is unknown to produce "template scores" proportional to the similarity of the enclaves of the known image to the enclaves measured by templates. The generic shape of a character is expressed as a "character equation" involving template scores developed on an unknown image, and each character equation is evaluated including comparing the values of such equations, and selecting the best value to determine the generic name of the unknown character.

Claims

1. In a hand print character recognition system comprising,

(a) means for creating an electrical binary black/white "image" of one or more hand printed characters,

(b) means for selecting a plurality of centers of recognition (CORs) within said binary black/white image as reference points and measuring the characteristic enclave of the black/white image immediately surrounding the CORs,

(c) means for storing a library of templates of said measurements around the CORs for a plurality of known exemplary character images,

(d) means for comparing said library of templates to corresponding measurements made around the CORs of images whose class is unknown to produce "template scores" proportional to the similarity of the enclaves of the known image to the enclaves measured by templates,

(e) means for expressing the generic shape of a character as being a "character equation" involving template scores developed on an unknown image, and

(f) means for evaluating each character equation, including comparing the values of such equations, and selecting the best value to determine the generic name of the unknown character.

2. The handprint character recognition system defined in claim 1 wherein said (b) means for selecting includes means for measuring the enclosure characteristic of each pixel within an enclave which is roughly related to the COR so each pixel has its own enclosure descriptions in four quadrants.

3. The handprint character recognition system defined in claim 1 wherein said handprint characters include one or more overlapping characters and said (c) means for storing a library of templates includes templates corresponding to said one or more overlapping characters.

4. The handprint character recognition system defined in claim 1, including means for choosing and manipulating measurement parameters such that very important characteristics, including the degree of black enclosure around the COR are normalized to be independent of relatively unimportant characteristics, such as size and distance of the black enclosure from the pixel or COR under consideration in the enclaves.

5. The handprint character recognition system defined in claim 4, including logic means for determining the boundedness of a white pixel in each of four quadrants (NE, NW, SE and SW) of said enclave, wherein the boundedness of a white pixel has a plurality of possible descriptions, including one or more of the following:

the presence or absence of a black pixel on a vertical axis of said white pixel, the presence or absence of a black pixel on a selected diagonal of said wite pixel, and the presence or absence of a black pixel on a horizontal axis of said white pixel, the black pixel on the vertical axis being required to be above said white pixel for boundedness descriptions of a white pixel in said NE or NW quadrants, respectively, but being required to be below a white pixel in said SE or SW quadrants, the black pixel on said selected diagonal axis being required to be above and to the right of said white pixel for boundedness descriptions of a white pixel in said NE quadrant, below and to the right for said white pixel in said SE quadrant, below and to the left for said white pixel in said SW quadrant, above and to the left for said white pixel in said NW quadrant, the presence or absence of a black pixel on the horizontal axis of said white pixel, the black pixel being required to be to the right of said white pixel in said NE and SE quadrants, but being required to be to the left of said white pixel in said SW and NW quadrants.

6. The handprint character recognition system defined in claim 5, including means for counting pixels with similar boundedness and for normalizing their number by computing ratos of their number to the total number of white pixels in the enclave with which it is associated.

7. The handprint character recognition system defined in claim 5, including means for using said measurement parameters to choose the location for the centers of recognition, to locate templates themselves to recognize useful CORs.

8. The handprint character recognition system defined in claim 5, including means for relaxing said measurement parameters so as to use them to select centers of recognition which are less narrowly defined than the measurement parameters needed in the character equations.

16. The handprint recognition system defined in claim 1 including means for determining whether a selected pixel is a member of a selected enclave.

9. In a hand print character recognition system comprising, means for transporting media bearing hand print characters, a photosensitive device, an optical system for focusing images of said hand print characters upon said photosensitive device, scanning means for converting the optical signals focused on said device to electrical signals, analog-to-digital converters for changing electrical grey scale levels associated with each individual small picture elements (pixels) in said image to digital values, and decision means for quantizing said pixels to be either black or white and creating a binary black/white "image" of a character or group of characters, the improvement comprising

(a) means for selecting a plurality of centers of recognition (CORs) within said binary black/white image as reference points for measurement of the characteristic enclave of the black/white image immediately surrounding the CORs,

(b) means for storing a library of templates of said measurements around the CORs for a plurality of known exemplary character images,

(c) means for comparing said library of templates to corresponding measurements made around the CORs of images whose class is unknown for producing "template scores" proportional to the similarity of the enclaves of the unknown image to the enclaves measured by the templates,

(d) means for expressing the generic shape of a character as being a "character equation" involving template scores developed on an unknown image, and

(e) means for evaluating each character equation, including comparing the values of such equations and selecting the character equation which matches the shape of the unknown image to determine the generic name of the unknown character.

10. The handprint character recognition system defined in claim 9 wherein said means for selecting includes means for measuring the enclosure characteristic of each pixel within an enclave .

11. The handprint character recognition system defined in claim 9 including means for choosing and manipulating measurement parameters such that very important characteristics, including the degree of black enclosure around the COR are normalized to be independent of relatively unimportant characteristics, such as size and distance of the black enclosure from the pixel or COR under consideration of the enclaves.

12. The handprint character recognition system defined in claim 11 including logic means for determining the boundedness of a white pixel in each of four quadrants (NE, NW, SE and SW) of said enclave, respectively, wherein the boundedness of a white pixel has a plurality of possible descriptions, including one or more of the following:

the presence or absence of a black pixel on a vertical axis of said white pixel, the presence or absence of a black pixel on a selected diagonal of said white pixel, and the presence or absence of a black pixel on a horizontal axis of said white pixel, the black pixel on the vertical axis being required to be above said white pixel for boundedness descriptions of a white pixel in said NE or NW quadrants, respectively, but being required to be below a white pixel in said SE or SW quadrants, the black pixel on said selected diagonal axis being required to be above and the right of said white pixel for boundedness descriptions of a white pixel in said NE quadrant, below and to the right for a white pixel in said SE quadrant, below and to the left for a white pixel in said SW quadrant, above and to the left for a white pixel in said NW quadrant, the presence or absence of a black pixel on the horizontal axis of said white pixel, the black pixel being required to be to the right of said white pixel in said NE and SE quadrants, but being required to be to the left of said white pixel in said SW and NW quadrants.

13. The handprint character recognition system defined in claim 12 including means for counting pixels with similar boundedness and for normalizing their number by computing ratios of their number to the total number of white pixels in the enclave with which it is associated.

14. The handprint character recognition system defined in claim 12 including means for using said measurement parameters to choose the location for the centers of recognition, to locate templates themselves to recognize useful CORs.

15. The handprint character recognition system defined in claim 12 including means for relaxing said measurement parameters so as to use them to select centers of recognition which are less narrowly defined than the measurement parameters needed in the character equations.

17. In a hand print character recognition method wherein an image of a character is converted to an electrical binary black/white "image" of a character or group of characters is the improvement comprising,

(a) selecting a plurality of centers of recognition (CORs) within said binary black/white image as reference points and measuring the characteristic enclave of the black/white image immediately surrounding the CORs,

(b) storing a library of templates of said measurements around the CORs for a plurality of known exemplary character images,

(c) comparing said library of templates to corresponding measurements made around the CORs of images whose class is unknown to produce "template scores" proportional to the similarity of the enclaves of the known image to the enclaves measured by templates,

(d) expressing the generic shape of a character as being a "character equation" involving template scores developed on an unknown image, and

(e) evaluating each character equation, including comparing the values of such equations, and selecting the best value to determine the generic name of the unknown character.

18. The handprint character recognition method defined in claim 17 wherein said step (a) selecting includes measuring the enclosure characteristic of each pixel within an encalve so each pixel has its own enclosured descriptions in four quadrants.

19. The handprint character recognition method defined in claim 17, including choosing and manipulating measurement parameters such that very important characteristics, including the degree of black enclosure around the COR are normalized to be independent of relatively unimportant characteristics, such as size and distance of the black enclosure from the pixel or COR under consideration of the enclaves.

20. The handprint character recognition method defined in claim 19, including logic means for determining the boundedness of a white pixel in each of four quadrants (NE, NW, SE and SW) of said enclave, wherein the boundedness of a white pixel has a plurality of possible descriptions, including one or more of the following:

the presence or absence of a black pixel on a vertical axis of said white pixel, the presence or absence of a black pixel on a selected diagonal of said white pixel, and the presence or absence of a black pixel on a horizontal axis of said white pixel, the black pixel on the vertical axis being required to be above said white pixel for boundedness descriptions of a white pixel in said NE or NW quadrants, respectively, but being required to be below a white pixel in said SE or SW quadrants, the black pixel on said selected diagonal axis being required to be above and to the right of said white pixel for boundedness descriptions of a white pixel in said NE quadrant, below and to the right for said white pixel in said SE quadrant, below and to the left for said white pixel in said SW quadrant, above and to the left for said white pixel in said NW quadrant, the presence or absence of a black pixel on the horizontal axis of said white pixel, the black pixel being required to be to the right of said white pixel in said NE and SE quadrants, but being required to be to the left of said white pixel in said SW and NW quadrants.

21. The handprint character recognition method defined in claim 20, including the steps of counting pixels with similar boundedness and normalizing their number by computing ratios of their number to the total number of white pixels in the enclave with which it is associated.

22. The handprint character recognition method defined in claim 20, including the steps of using said measurement parameters to choose the location for the centers of recognition, to locate templates themselves to recognize useful CORs.

23. The handprint character recognition method defined in claim 20, including the step of relaxing said measurement parameters so as to use them to select centers of recognition which are less narrowly defined than the measurement parameters needed in the character equations.

24. The handprint character recognition method defined in claim 17 including the steps of determining whether a selected pixel is a member of a selected enclave.

25. In a hand print character recognition method in which a document bearing handprinted characters to be recognized, said documents are transported through a reading station having a photosensitive device, an system for impressing images of said hand print characters upon said photosensitive device, scanning means for converting the optical signals impressed on said device to electrical signals, analog-to-digital converters for changing electrical grey scale levels associated with each individual small picture elements (pixels) in said image to digital values, and decision means for quantizing said pixels to be either black or white and creating a binary black/white "image" of a character or group of characters, the improvement comprising the steps of:

(a) selecting a plurality of centers of recognition (CORs) within said binary black/white image as reference points for measurement of the characteristic enclave of the black/white image immediately surrounding the CORs,

(b) storing a library of templates of said measurements around the CORs for a plurality of known exemplary character images,

(c) comparing said library of templates to corresponding measurements made around the CORs of images whose class is unknown to producing "template scores" proportional to the similarity of the enclaves of the unknown image to the enclaves measured by the templates,

(d) expressing the generic shape of a character as being a "character equation" involving template scores developed on an unknown image, and

(e) evaluating each character equation, including comparing the values of such equations and selecting the character equation which matches the shape of the unknown image to determine the generic name of the unknown character.

26. The handprint character recognition method defined in claim 25 wherein said step (a) includes means for measuring the enclosure characteristic of each pixel within an enclave.

27. The handprint character recognition method defined in claim 25 including the step of choosing and manipulating measurement parameters such that very important characteristics, including the degree of black enclosure around the COR are normalized to be independent of relatively unimportant characteristics, such as size and distance of the black enclosure from the pixel or COR under consideration of the enclaves.

28. The handprint character recognition method defined in claim 27 including means determining the boundedness of a white pixel in each of four quadrants (NE, NW, SE and SW) of said enclave, wherein the boundedness of a white pixel has a plurality of possible descriptions, including one or more of the following:

the presence or absence of a black pixel on a vertical axis of said white pixel, the presence or absence of a black pixel on a selected diagonal of said white pixel, and the presence or absence of a black pixel on a horizontal axis of said white pixel, the black pixel on the vertical axis being required to be above said white pixel for boundedness descriptions of a white pixel in said NE or NW quadrants, respectively, but being required to be below a white pixel in said SE or SW quadrants, the black pixel on said selected diagonal axis being required to be above and to the right of said white pixel for boundedness descriptions of a white pixel in said NE quadrant, below and to the right for said white pixel in said SE quadrant, below and to the left for said white pixel in said SW quadrant, above and to the left for said white pixel in said NW quadrant, the presence or absence of a black pixel on the horizontal axis of said white pixel, the black pixel being required to be to the right of said white pixel in said NE and SE quadrants, but being required to be to the left of said white pixel in said SW and NW quadrants.

29. The handprint character recognition method defined in claim 28 including the step of counting pixels with similar boundedness and for normalizing their number by computing ratios of their number to the total number of white pixels in the enclave with which it is associated.

30. The handprint character recognition method defined in claim 28 including the step of using said measurement parameters to choose the location for the centers of recognition, to locate templates themselves to recognize useful CORs.

31. The handprint character recognition method defined in claim 28 including the step of relaxing said measurement parameters so as to use them to select centers of recognition which are less narrowly defined than the measurement parameters needed in the character equations.

32. A pattern recognition system in which an array of cells store information in two or more levels representing two or more changes of values of each parameters defining a pattern to be recognized,

means for examining cells in said array to locate a center of recognition cell,

means for determining the boundedness of other cells having specific relationship to said center of recognition cell and producing boundedness measurements to recognize said pattern.

33. The pattern recognition system defined in claim 32 including classification means for each recognized pattern.

34. A pattern recognition method in which information in two or more levels representing two or more changes of values of each parameters defining a pattern to be recognized is stored in an array of information storage cells,

examining cells in said array to locate a center of recognition cell,

determining the boundedness of other cells having specific relationship to said center of recognition cell, and

producing boundedness measurements to recognize said pattern.

35. An artificial fovea comprising,

an array of storage cells,

loading means for loading an image information which has one or more enclaves, in black/white pixel format, into said storage cells, one pixel per storage cell,

means for selecting one of said white pixels as a center of recognition (COR) to constitute a test COR location and initiate propagation of enclave membership measurement,

logic means for determining whether each white pixel in said image is bounded in predetermined directions by a black pixel in said array of storage cells,

summing means for summing the number of pixels which are bounded in each said predetermined direction, respectively, and producing enclave measurements proportional to each respective percentage of the total number of white cells in said array, and

means for transmitting said enclave measurement to a utilization device.

36. The artificial fovea defined in claim 35 wherein said utilization device includes,

means for selecting and storing a plurality of sets of said enclave measurements, each selected enclave measurement constituting a template,

means for comparing a subsequent said enclave measurement with said plurality of templates and producing a set of ordered values bases on the results of comparing said subsequent enclave measurements with said plurality of sets of templates, and

means for storing said ordered set of values.

37. The artificial fovea defined in claim 36 wherein said means for selecting includes means for causing each white pixel in an enclave to be said test COR.

38. The artificial fovea defined in claim 37 including means for selecting the best scoring test CORs, and means for transmitting the selected test CORs to said utilization device.

39. The artificial fovea defined in claim 38 including means for preventing use of all white pixels in the highest scoring enclave in subsequent scoring of test CORs for remaining enclaves.

40. The artificial fovea defined in claim 35 wherein said logic means includes means for limiting the boundedness determination in diagonal directions from the selected CORs.

41. The artificial fovea defined in claim 35 including terminating propogation of membership.

42. The artificial fovea defined in claim 35 including means for detecting when a column of white pixels is not bounded to the north and south and excluding said column of pixels from being deemed a part of the enclave.

43. The artificial fovea defined in claim 35 including means for detecting when a column of white pixels is not bounded east and west and excluding said column of pixels from being deemed a part of the enclave.

44. A pattern recognition system comprising,

an array of storage cells,

loading means for loading image information containing a pattern to be recognized which has one or more enclaves, in black/white pixel format, into said storage cells, one pixel per storage cell,

means for selecting one of said white pixels as a center of recognition (COR) to constitute a test COR location, logic means for determining whether each white pixel in said image is bounded in predetermined directions by a black pixel in said array of storage cells,

summing means for summing the number of white pixels which are bounded in each said predetermined direction, respectively, and producing enclave measurements proportional to each respective percentage of the total number of white cells in said array,

means for receiving said enclave measurements and reconizing said patterns therefor, and

means for transmitting said enclave measurement to a utilization device.

45. The pattern recognition system defined in claim 44 wherein said utilization device includes,

means for selecting and storing a plurality of sets of said enclave measurements, each selected enclave measurement constituting a template,

means for comparing a subsequent said enclave measurement with said plurality of templates and producing a set of ordered values based on the results of comparing said subsequent enclave measurements with said plurality of sets of templates, and

means for storing said ordered set of values.

46. The pattern recognition system defined in claim 45 wherein said means for selecting one of said white pixels includes means for causing each white pixel in an enclave to be said test COR.

47. The pattern recognition system defined in claim 46 including means for selecting the best scoring test CORs, and means for transmitting the selected test CORs to said utilization device.

48. The pattern recognition system defined in claim 47 including means for preventing use of all white pixels in the highest scoring enclave in subsequent scoring of test CORs for remaining enclaves.

49. The pattern recognition system defined in claim 44 wherein said logic means includes means for limiting the boundedness determination in diagonal directions from the selected CORs.

50. The pattern recognition system defined in claim 44 including means for detecting when a column of white pixels is not bounded to the north and south.

51. The pattern recognition system defined in claim 44 including means for detecting when a column of white pixels is not bounded east and west.

52. The pattern recognition system defined in claim 44 including means for initiating the propagation enclave membership.

53. The pattern recognition system defined in claim 52 including means for terminating the propagation of said enclave membership upon detecting a predetermined configuration of black/white pixels.

54. The pattern recognition system defined in claim 50 including means for excluding said column of pixels from being deemed a part of the enclave.

55. The pattern recognition system defined in claim 51 including means for excluding said column of pixels from being deemed a part of the enclave.

56. Character recognition apparatus comprising,

(1) means for generating an electrical binary black/white pixel image of one or more characters to be recognized,

(2) means for analyzing selected white pixel areas of said black/white pixel image and producing a set of measurements indicative of the boundedness of each said selected white pixel areas, respectively, and

(3) means for utilizing said set of measurements indicative of the boundedness of said selected white pixel areas to recognize said characters.

57. Character recognition apparatus as defined in claim 56 wherein said means for analyzing selected white pixels includes means for counting the white pixels which are bounded in predetermined directions, and producing signals corresponding thereto, and means utilizing said signals to produce said measurements indicative of the boundedness of said selected white pixel areas.

58. Character recognition apparatus as defined in claim 56 wherein said (3) means for utilizing includes means for locating the centroid of each of said selected white pixel areas and means for including relative locations of said centroide to recognize said characters.

59. Character recognition apparatus as defined in claim 56 wherein said (3) means for utilizing includes means for determining whether a loop shaped enclave is present in the character, the white pixels in a maximum size pointyness triangle within said loop shaped enclave and the ratio of the total number of white pixels in the loop shaped enclave to the number of to the number of white pixels in said pointyness triangle.

60. Character recognition apparatus as defined in claim 56 wherein said (3) means for utilizing includes means for locating loops in said character and determining the number of white pixels in each loop and determining the relative number of white pixels in each loop for use in recognizing the character.

61. Character recognition apparatus as defined in claim 56 including means for determining whether a cluster of black pixels constitutes a portion of a character being read.

62. Character recognition apparatus as defined in claim 61 including means for inverting pixels in one or more selected areas of a character or a line of characters to determine whether said cluster of black pixels is a period.

63. Character recognition apparatus as defined in claim 56 wherein said (2) means for analyzing reduces the effect of random black pixels in said selected white pixel areas in producing said set of measurements indicative of boundedness.

64. Character recognition apparatus as defined in claim 56 wherein said (2) means for analyzing reduces the effect of random white pixels which are bounded in a predetermined manner by two or more black pixels.

65. Character recognition apparatus as defined in claim 56, said white pixel areas have four quadrants (NE, NW, SE and SW) and said means for analyzing selected white pixel areas include logic means for determining the boundedness of a white pixel in each of the four quadrants of said white pixel area, the boundedness of a selected white pixel has a plurality of possible descriptions, selected from the following:

the presence or absence of a black pixel on the vertical axis of said white pixel, the presence or absence of a black pixel on a selected diagonal of said selected white pixel, and the presence or absence of a black pixel on the horizontal axis of said selected white pixel, the black pixel on the vertical axis being required to be above said white pixel for boundedness descriptions of said selected white pixel in said NE or NW quadrants, but being required to be below a white pixel in said SE or SW quadrants, the black pixel on said selected diagonal axis being required to be above and to the right of said selected white pixel for boundedness descriptions of said selected white pixel in said NE quadrant, below and to the right for a selected white pixel in said SE quadrant, below and to the left for a selected white pixel in said SW quadrant, above and to the left for a selected white pixel in said NW quadrant, the presence or absence of a black pixel on the horizontal axis of said selected white pixel, the black pixel being required to be to the right of said selected white pixel in said NE and SE quadrants, but being required to be to the left of said selected white pixel in said SW and NW quadrants.

66. Character recognition apparatus as defined in claim 56 wherein said electrical binary black/white image includes one or more pairs of characters which overlap but do not touch each other, and said (2) means for analyzing include means for detecting segmentation between said pair of characters, including logic means for detecting a continuous sequence of white pixels extending between top and bottom edges of the overlapping but not touching pairs of characters.

67. Character recognition apparatus as defined in claim 66 including means for establishing a predetermined time period for said logic means to determine the presence of said line of white pixels between said pair of characters which overlap.

68. Character recognition apparatus as defined in claim 66 wherein there are a plurality of said (2) means for analyzing and means connecting said plurality of (3) means for analyzing in parallel.