Graphical system for automated segmentation and recognition for image recognition systems

Claim 2

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.

Claim 3

Apparatus in accordance with claim 1, further comprising: means in said generating means for converting said probability measure to a negative log number.

Claim 4

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.

Claim 5

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.

Claim 6

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.

Claim 7

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.

Claim 8

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.

Claim 9

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.

Claim 10

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

Claim 11

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.

Claim 12

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.

Claim 13

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.

Claim 14

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.

Claim 15

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.

Claim 16

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.

Claim 17

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.

Claim 18

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

Claim 19

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.

Claim 20

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

Claim 21

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.

Claim 24

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.

Claim 25

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.

Claim 26

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.

Claim 27

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

Claim 28

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.

Claim 31

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

Claim 32

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.

Claim 33

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

Claim 34

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.