Graphical system for automated segmentation and recognition for image recognition systems

• US 5,487,117 A
• Filed: 10/11/1994
• Issued: 01/23/1996
• Est. Priority Date: 12/31/1991
• Status: Expired due to Fees

• Current Assignee: AT&T Corporation (AT&T, Inc.)
• Original Assignee: AT&T Corporation (AT&T, Inc.)
• Inventors: Burges, Christopher J., Matan, Ofer, Le Cun, Yann A.
• Primary Examiner(s): Couso, Jose L.
• Application Number:
  US08/327,339
• Time in Patent Office: 469 Days
• Field of Search: 382/14, 382/15, 382/21, 382/33, 382/36, 382/37, 382/38, 382/39, 382/40, 382/45, 382/54, 382/56, 395/21
• US Class Current: 382/173
• CPC Class Codes: G06V 30/10 Character recognition
• CPC Class Codes: G06V 30/153 using recognition of characters or words

Abstract

Apparatus and processes are described for the automatic recognition of alphanumeric images. A set of cuts are made to the image which include incorrect segmentations. The resulting "cells" comprising in their totality the created segments of the image are then analyzed to determine which cells are legal neighbors and which are not. All cells which are legal neighbors are then presented as connected nodes. A pruning of nodes which are related to certain predetermined image cuts is effected. Each set of remaining connected nodes is then presented to a recognizer which identifies the image and assigns a specified probability to the output. Many cells which are not legal neighbors are thereby not presented to the recognizer, thus saving substantially on computations per recognized image.

Claims

1. In symbol recognition apparatus comprising an image sensor, an image segmenter, a memory, a recognizer including a library of known images and a comparison means for generating a measure of probability that a sensed image is a one of said known images, the improvement in recognizing one or more unknown alphanumeric symbols, comprising:

means for sensing an image of said symbol string with said image sensor;

means for segmenting the image of said symbol string with said segmenter to construct candidate cuts through said string, thereby creating a multiplicity of image segments potentially greater in number than the symbols present in said string and sufficient in number to include the correct segmentation;

means for arranging in said memory said segments as a sequence of nodes, the nodes at the beginning point of said sequence corresponding to the left-hand side of said string, and the nodes at the end-point in said sequence corresponding to the right-hand side of said string;

means for identifying all nodes corresponding to segments which are legal neighbors and connecting with arcs from left to right all such nodes, thereby creating multiple paths across said sensed image, each said path corresponding to a particular legal segmentation of said image;

means for comparing said segments to predetermined data in a definite cut database thereby to identify all nodes which straddle a definite cut;

means for eliminating from said memory said last-named nodes as well as all arcs connected to each said node;

means for identifying nodes which because of the preceding step no longer have a parent-child connection, and recursively eliminating all said nodes and associated arcs from said memory;

means for generating in said recognizer a measure of probability for each remaining node returning said measure to said memory for association with the respective node; and

means for combining said probability measures associated with all of the nodes in each said remaining node path, thereby to produce outputs consisting of a symbol identification and a total probability measure associated with each particular node path.

2. Apparatus in accordance with claim 1, further comprising:

means in said generating means for converting said probability measure to a negative log number.

3. Apparatus in accordance with claim 2, wherein said combining means further comprises:

means for adding said negative log numbers to find the shortest path which traverses remaining nodes;

means for examining each node along the path and determining which segment it corresponds to; and

means for determining the highest score associated with the recognizer outputs for each such node.

4. Apparatus in accordance with claim 1, 2, or 3, wherein legal neighbors are those nodes which correspond to adjoining segments where the right-hand edge of the left-hand segment is the same as the left-hand edge of the right-hand segment.

5. Apparatus in accordance with claim 1, 2, or 3, wherein legal neighbors are those nodes which correspond to adjoining segments which overlap by one or more cells.

6. Apparatus in accordance with claim 1, 2, or 3, wherein legal neighbors are those nodes which correspond to nearby segments which have one or more cells between them which is not included in either one of said nearby segments.

7. In symbol recognition apparatus comprising an image sensor, an image segmenter, a memory, a neural network recognizer including a library of known images and a comparison means for generating a measure of probability that a sensed image is a one of said known images, the improvement in recognizing one or more unknown alphanumeric symbols, comprising:

means for sensing an image of said one or more symbols with said image sensor and converting said sensed image to pixel format;

means for segmenting said pixel image of said symbols with said segmenter to construct candidate cuts through said symbols, thereby creating a multiplicity of image cells greater in number than the symbols present, and sufficient in number to include the correct segmentation;

means for arranging in said memory said segments as a graphical array of several node sequences, the nodes at the beginning point of said sequence corresponding to the left-hand side of said graph, and the nodes at the end-point in said sequence corresponding to the right-hand side of said graph;

means for identifying all nodes corresponding to segments which are legal neighbors and connecting with graphed arcs from left to right all such nodes, thereby creating multiple paths across said sensed image, each said path corresponding to a particular legal segmentation of said image;

means for providing a predetermined database of definite cuts information and comparing said cuts to said database information thereby to identify all nodes which straddle a definite cut;

means for eliminating from said memory said last-named nodes as well as all arcs connected to each said node;

means for generating in said neural network recognizer a said measure of probability for each remaining node returning said measure to said memory for association with the respective node; and

means for combining said probability measures associated with all of the nodes in each said remaining node path, thereby to produce outputs consisting of a symbol identification and a total probability measure associated with each particular node path.

8. Apparatus in accordance with claim 7, wherein said generating means further comprises means for converting said probability measures to a negative log number.

9. Apparatus in accordance with claim 8, wherein said combining means further comprises means for adding said negative log numbers to find the shortest path which traverses remaining nodes;

means for examining each node along the path and determining which segment it corresponds to; and

means for determining the highest score associated with the recognizer outputs for each such node.

10. Apparatus in accordance with claim 7, 8, or 9 further comprising means for identifying nodes which because of said elimination step no longer have a parent-child connection, and means for recursively eliminating all said nodes and associated arcs from said memory.

11. Apparatus in accordance with claims 7, 8, or 9, wherein legal neighbors are those nodes which correspond to adjoining segments where the right-hand edge of the left-hand segment is the same as the left-hand edge of the right-hand segment.

12. Apparatus in accordance with claims 7, 8, or 9, wherein legal neighbors are those nodes which correspond to adjoining segments which overlap by one or more cells.

13. Apparatus in accordance with claims 7, 8, or 9, wherein legal neighbors are those nodes which correspond to nearby segments which have one or more cells between them which is not included in either one of said nearby segments.

14. In an alphanumeric symbol recognition engine comprising an image sensor, an image segmenter, a memory, a neural network recognizer including a library for receiving known images and a comparison means for generating multiple measures of probability for a known inputted image with respect to all possible alphanumeric members of the class to which said inputted image belongs, apparatus for automatically generating individual character training images using input images and their corresponding "truth" information, comprising:

means for sensing one or more images of said known alphanumeric symbols with said image sensor and converting said sensed images to pixel format;

means for segmenting said pixel images of said alphanumeric symbols with said segmenter to construct candidate cuts through said images, thereby creating a multiplicity of sequential image cells possibly greater in number than the alphanumeric symbols presented, and sufficient in number to include the correct segmentation of each said image;

means for arranging in said memory said cells as a graphical array of several node sequences, the nodes at the beginning point of said sequence corresponding to the left-hand side of said graph, and the nodes at the end-point in said sequence corresponding to the right-hand side of said graph;

means for identifying all nodes corresponding to segments which are legal neighbors and connecting with graphed arcs from left to right all such nodes, thereby creating multiple paths across said sensed images, each said path corresponding to a particular legal segmentation of said images in one-to-one correspondence;

means for providing a predetermined database of definite cuts information and comparing said cuts to said database information thereby to identify all nodes which straddle a definite cut;

means for eliminating from said memory said last-named nodes as well as all arcs connected to each said node;

means for generating in said neural network recognizer a said measure of probability for each remaining node and returning said measure to said memory for association with the respective node; and

means for combining and storing all said probability measures associated with all of the nodes in all said remaining node paths, thereby to produce alphanumeric identification data for said library consisting of a symbol identification and a total probability measure associated with all particular node paths;

whereby segmentation of said image is substantially automatic.

15. Apparatus in accordance with claim 14, wherein said generating means further comprises means for converting said probability measure to a negative log number.

16. Apparatus in accordance with claim 15, wherein legal neighbors are those nodes which correspond to adjoining segments where the right-hand edge of the left-hand segment is the same as the left-hand edge of the right-hand segment.

17. Apparatus in accordance with claim 15, wherein legal neighbors are those nodes which correspond to adjoining segments which overlap by one or more cells.

18. Apparatus in accordance with claim 15, wherein legal neighbors are those nodes which correspond to nearby segments which have one or more cells between them which is not included in either one of said nearby segments.

19. A method for machine-reading a string of unknown alphanumeric symbols on a graphical record, comprising

a) with an image sensor, scanning the graphical record, thereby to produce a pixel image of the symbol string;

b) segmenting the pixel image into a plurality of cells equal in number to at least the expected number of alphanumeric symbols in the string;

c) storing each resulting cell in a memory device;

d) selecting at least some of the cells;

e) recalling each of the selected cells from the memory device and presenting said cell as input to a recognition engine; and

f) receiving from the recognition engine a probability measure which indicates the likelihood that the cell belongs to the same class as some member of a library of known images, wherein;

g) the storing step comprises arranging in said memory said cells, or combinations thereof, as a sequence of nodes, the nodes at the beginning point of said sequence corresponding to the left-hand side of said string, and the nodes at the end-point in said sequence corresponding to the right-hand side of said string;

h) the selecting step comprises identifying all nodes corresponding to segments which are legal neighbors and connecting with arcs from left to right all such nodes, thereby creating multiple paths across said sensed image, each said path corresponding to a particular legal segmentation of said image;

i) the selecting step further comprises comparing said segments to predetermined data in a definite cut database thereby to identify all nodes which straddle a definite cut of said string image;

j) the selecting step further comprises eliminating from said memory said last-named nodes as well as all arcs leading from or terminating on each said node;

k) the receiving step is performed such that a probability measure is thereby associated with each of the nodes that remain after step (j); and

l) the method further comprises combining said probability measures associated with all of the nodes in each said remaining node path, thereby to produce outputs consisting of a symbol identification and a total probability measure associated with each particular node path.

20. The method of claim 19, further comprising, after the eliminating step, the step of identifying nodes which because of said elimination step no longer have a parent-child connection, and recursively eliminating all said nodes and associated arcs from said memory.

21. The method of claim 19, further comprising the step of expressing each probability measure as a negative log number, and wherein the combining step comprises:

adding said negative log numbers to find the shortest path which traverses remaining nodes;

examining each node along the path and determining which segment it corresponds to; and

determining the highest scoring symbol associated with the recognizer outputs for each such node.

22. The method of claim 19, wherein legal neighbors are those nodes which correspond to adjoining segments where the right-hand edge of the left-hand segment is the same as the left-hand edge of the right-hand segment.

23. The method of claim 19, wherein legal neighbors are those nodes which correspond to adjoining segments which overlap by one or more cells.

24. The method of claim 19, wherein legal neighbors are those nodes which correspond to nearby segments which have one or more cells between them which is not included in either one of said nearby segments.

25. A method for training a neural network recognition engine, including a reference library for recording therein known images, to recognize alphanumeric symbols, the method comprising:

a) with an image sensor, scanning at least one graphical record, thereby to produce a pixel image of a symbol string borne by said record;

b) segmenting the pixel image into a plurality of cells equal in number to at least the expected number of alphanumeric symbols in the string;

c) storing each resulting cell in a memory device;

d) selecting at least some of the cells;

e) recalling each of the selected cells from the memory device and presenting said cell as input to the recognition engine; and

f) receiving from the recognition engine a probability measure which indicates the likelihood that the cell belongs to the same class as some member of a library of known images, wherein;

g) the storing step comprises arranging in said memory said cells, or combinations thereof, as a sequence of nodes, the nodes at the beginning point of said sequence corresponding to the left-hand side of said string, and the nodes at the end-point in said sequence corresponding to the right-hand side of said string;

h) the selecting step comprises identifying all nodes corresponding to segments which are legal neighbors and connecting with arcs from left to right all such nodes, thereby creating multiple paths across said sensed image, each said path corresponding to a particular legal segmentation of said image;

i) the selecting step further comprises comparing said segments to predetermined data in a definite cut database thereby to identify all nodes which straddle a definite cut of said string image;

j) the selecting step further comprises eliminating from said memory said last-named nodes as well as all arcs leading from or terminating on each said node;

k) the receiving step is performed such that a probability measure is thereby associated with each of the nodes that remain after the eliminating step;

l) the method further comprises combining said probability measures associated with all of the nodes in each said remaining node path, thereby to produce alphanumeric identification dam comprising a symbol identification and a total probability measure associated with each particular node path; and

m) recording said alphanumeric identification data in the library.

26. The method of claim 25, wherein said generating step comprises converting said probability measure to a negative log number.

27. The method of claim 25, wherein legal neighbors are those nodes which correspond to adjoining segments where the right-hand edge of the left-hand segment is the same as the left-hand edge of the right-hand segment.

28. The method of claim 25, wherein legal neighbors are those nodes which correspond to adjoining segments which overlap by one or more cells.

29. The method of claim 25, wherein legal neighbors are those nodes corresponding to nearby segments which have one or more cells between them which are not included in either one of said nearby segments.