Character Segmentation Using an Associative Memory for Optical Character Recognition

1. Technical Field

The invention is related to character segmentation performed in an optical character recognition system prior to character identification, and in particular to character segmentation employing an associative memory or neural network.

2. Background Art

The problem in optical character recognition of segmenting individual character images from one another in a bit-map image of a document prior to identifying the individual character images is well-known. In many cases, adjacent individual characters may actually appear to be joined, either because of overlapping or kerning or because of noise in the image. Character segmentation is an essential preparatory step for character identification to be carried out reliably.

While many techniques have been proposed for performing character segmentation, they are for the most part very complex. It would be a great advantage if one could simply step a movable window of a size corresponding to an individual character across a document image pixel-by-pixel and reliably determine for each position of the window whether or not it has captured an individual character. If so, the image captured within the window would be transmitted to a down-stream character identification device. Otherwise, the captured image would not be transmitted. Such a procedure would enjoy the significant advantage of simplicity. However, no way of implementing such a procedure reliably has been found.

For example, U.S. Pat. No. 4,932,065 to Feldgajer describes a technique (illustrated in FIGS. 1a and 1b herein) for segmenting characters 10, 12 (FIG. 1a) for optical character recognition using a movable examining window 14 (FIG. 1b) corresponding in size to a single character, and moving the window pixel-by-pixel through the entire bit-map image 16 of the document. At each step, the image captured inside the window 14 is processed to determine whether the image within the window corresponds to an individual character. However, the processing employed is not sufficiently reliable. Specifically, the contents of the image captured within the window 14 at each position thereof is multiplied pixel-by-pixel with respective elements of a kernel 18 identical in size to the movable window 14, and the sum of all products is used as a "score" to determine whether the current window position is centered on one of the known characters. The elements of the kernel 18 correspond to a probability for each pixel in the window whether that pixel is "on" whenever the window is centered over any one of the characters in a known character set. Thus, each kernel element is a probability density function across all characters in the known character set. The magnitude of the kernel elements or individual probability density functions is indicated within the kernel 18 of FIG. 1a by tone, the darker areas of the kernel 18 containing elements or probability density functions of higher amplitude. The kernel 18 is produced in a straightforward manner by totalling for each pixel in the movable window the number of times it is "on" as each character in the known character set is centered in the movable window, as depicted in FIG. 1a.

Such a technique is not reliable: The computation of the score is not particularly immune to "false" high scores attributable to portions of adjacent characters simultaneously captured within the window when the window is NOT centered over one individual character. Depending upon the character font, such a non-character captured image (i.e., an image straddling two adjacent characters) frequently may have a high correlation to many of the large amplitude elements in the mask of probability density functions, and thus produce a false "high" score, leading the system to the incorrect conclusion that the captured image is that of an individual character.

Depending upon its frequency of occurrence, such an error is unacceptable in commercially marketed optical character recognition systems. Thus, it has not seemed possible to reliably perform character segmentation by simply stepping an intelligent window or kernel across the bit-map image of a document. Accordingly, the art must currently turn to far more complex techniques for reliable character segmentation, a significant burden.

Therefore, it is an object of the present invention to provide a reliable process for segmenting characters by stepping a window or intelligent kernel pixel-by-pixel across the bit-map image of a document, thereby achieving simplicity without sacrificing reliability.

It is a further object of the invention to provide such a process with a strong immunity against falsely identifying portions of adjacent characters captured within the window at a given position as an individual character.

In accordance with the invention, the image captured at each pixel-by-pixel step within the movable window is processed by an associative memory or neural network which has been trained with knowledge of a complete training set of character images. The invention senses whether the associative memory or neural network associates the window's captured image with one of the characters of the training set. Typically, the associative memory or neural network is of the type which actually produces the correct character of the training set in response to a captured image centered on the corresponding character in the bit-map image of the document. In this case, the invention senses whether the associative memory or neural network actually produces one of the characters of the training set. If so, the captured image is immediately identified as being the image of a segmented or individual character, and it is transmitted on to a downstream character identifier.

In the preferred embodiment, immunity to falsely identifying a particular window position as being centered on a character is dramatically increased by training the neural network or associative memory with two sets of training images: (1) "character" images of the known character set, and (2) "non-character" images of all possible intersections and combinations of the known character set corresponding to window positions straddling adjacent characters. The latter set of training images necessarily includes the type of window-captured images which in the prior art led to false identification of a window position as being centered on a character --i.e., false character segmentation. In this preferred embodiment, the invention senses which one of the two sets of training images the captured image falls within. In other words, the invention classifies the character identified by the neural network or associative memory as being either within set (1) or set (2). Provided that all possible non-character images have been included in set (2), the invention provides virtually flawless character segmentation. Such reliability and immunity to failure was unattainable in the prior art.

In general, some types of associative memories or neural networks do not have the ability to classify their output as falling within one of two (or more types) of training sets with which the neural network or associative memory has been trained. In particular, the Hopfield neural network (FIGS. 2a and 2b) does not have the ability to so classify its output. It merely produces a member of a training set in response to an input. Thus, the only way to classify a captured image using this type of associative memory or neural network would be to try to recognize the character produced by the neural network, by using the character identifier of the downstream optical character recognition system. This would lead to an anomalous result whenever the output of the neural network or associative memory is a non-character (falling within training image set (2)), since the downstream character identifier would simply fail, which is just the situation that character segmentation is supposed to prevent.

The foregoing problem is overcome for such neural networks or associative memories by appending to each training image an extra pixel row or column outside the field of the movable window. Thus, if the movable window consists of m horizontal rows and n vertical columns of pixels, then each individual training image consists of m+1 rows and n columns of pixels, so as to provide an extra or m+1.sup.st pixel row, for example. The m+1.sup.st row contains a bit pattern classifying the image as a character (set 1) or a non-character (set 2). As the captured (unknown) image is transmitted from the movable window to the neural network, an extra row of all zeroes is added to it as the m+1.sup.st row so that its dimensionality corresponds to that of the neural network's training set. The neural network will then produce the corresponding training character image, including the extra row containing the correct classification of the unknown image captured within the current position of the movable window in the document image. The contents of the extra or m+1.sup.st row is included in the output image generated by the neural network and determines whether the captured image is to be transmitted to the downstream character identifier.

Another aspect of the invention is that it provides an improvement in that type of neural network or associative memory which, in the prior art, could not classify its output as falling within a certain one of two (or more) training sets with which the neural network or associative memory has been trained. The invention invests such a neural network or associative memory with the ability to internally classify its output as falling within a certain one of two (or more) training sets of inputs with which the neural network or associative memory has been trained. One example of this aspect of the invention is described in detail below with respect to a Hopfield neural network. Thus, the invention provides a significant advance in the field of neural networks and associative memories.

FIG. 1a is a simplified flow diagram depicting the construction of a probability density function kernel for use in character segmentation with a movable window, in accordance with the prior art.

FIG. 1b is a diagram depicting the operation of the movable window with reference to the kernel of FIG. 1a in accordance with the prior art.

FIG. 2a is a diagram of a Hopfield neural network in accordance with the prior art.

FIG. 2b is a diagram of a matrix implementation of the Hopfield network of FIG. 2a in accordance with the prior art

FIG. 3 is a simplified block diagram of a character segmenting system embodying the present invention.

FIG. 4 is a block diagram of the associative memory function employed in system of FIG. 3 in accordance with the invention.

FIGS. 5a and 5b are schematic block diagrams of a preferred embodiment of the system of FIG. 3.

FIG. 6 is a simplified block diagram of an alternative embodiment of the associative memory function of FIG. 4.

Referring to FIG. 3, an associative memory function 300 receives a sub-image 302 captured within a movable window 304 in the bit-map image 306 of a document. The window 304 is moved to a succession of positions in the bit-map image 306 pixel-by-pixel to capture a succession of different sub-images, each of which is transmitted in turn to the associative memory function 300.

The associative memory function 300 has been trained with at least a set of training characters of the type expected to be found in the document represented by the bit-map image 306. If the associative memory function 300 can recall one of the training characters in response to the sub-image 302, then a controller 308 responds by forwarding the sub-image 302 to a downstream character identifier of an optical character recognition system 310.

Referring to FIG. 4, the associative memory function 300 includes a neural function 400 reflecting the knowledge of a set of training vectors. The training vectors are formed from a complete set of characters appearing in the document. Each training image is obtained by centering the window 304 over a known character. If, for example, the size of the window 304 is m pixel rows and n pixel columns, then each training character image captured in the window 304 is converted to a single column vector having m.times.n elements. This process is performed for each character in the font in order to complete the training set. Any unknown image of m pixel rows and n pixel columns captured in the window 304 is similarly converted to vector form and applied to the neural function input 400a. If the captured image is one of an individual character (so that the window 304 is centered on one individual character in the bit-map image 306), the neural function 400 immediately produces the corresponding training vector at its output 400b. A detector 404 senses whether the neural function 400 has produced a training vector at its output 400 b. If so, the detector 404 transmits a YES indication to the controller 308. Otherwise, a NO or NULL indication is transmitted to the controller 308.

A significant advantage of the invention is that it provides immunity against erroneous character segmentation. In the preferred embodiment, this is accomplished by training the associative memory function 300 of FIG. 3 with two different training vector sets 312, 314. The first training vector set 312 comprises a vector for each character in the font with which the document represented by the bit-map image 306 was printed. The second training vector set 314 comprises a vector for each possible "non-character" image which the window 304 might capture as a result of straddling two characters or otherwise being un-centered with respect to an individual character in the bit-map image 306. These non-character vectors of the second set 314 are formed in a manner similar to that described above with reference to the character training vectors of the first set 312, with the exception that during formation of the second set 314, the window 304 is not centered over a single character. Instead, the window 304 is moved to all other positions in the document image 306 (or at least many of the other positions) so that all possible non-character images (or at least many thereof) are included in the second training set 314. Thus, the associative memory function 300 will always find a corresponding training vector in response to any image captured by the window 304: either a character training vector from the first training set 312 or a non-character training vector from the second training set 314. As a result, there is no ambivalence in the character segmenting decision made at each position of the movable window 304. The vector produced by the associative memory function 300 will fall into one of the two types, thereby determining unambiguously whether the sub-image 302 is a character or a non-character.

In an alternative embodiment of the invention, the emergent behavior of the associative memory function 300 is used to deduce whether the sub-image captured within the window 304 is a true character. In this alternative embodiment, the associative memory function 300 is trained with only the first (true character) training set. If a particular sub-image 302 captured in the window 304 is a true character, the associative memory function 300 will very quickly if not immediately produce the corresponding training vector. On the other hand, if the particular sub-image 302 is not a true character (because, for example, the window 304 is straddling two adjacent characters), then the emergent behavior of the associative memory function 300 will result in a much longer time being consumed (more computational iterations being performed) in attempting to arrive at a stable result. In this alternative embodiment, the time consumed by the associative memory function 300 (or the number of iterations performed thereby) is sensed by the detector 404 and controls the decision of whether the sub-image 302 represents a segmented character.

The neural function 400 may be any suitable associative memory or neural network, such as the Hopfield neural network of FIG. 2a, for example. The Hopfield network of FIG. 2a has a set of neurons 420 connected to a respective set of input/output nodes 422 and a set of feedback connections 424 connecting the output of each individual neuron 420 to the inputs of all neurons 420. Each neuron represents a different coupling strength or weight. The ensemble of all weights represented by all the neurons 420 represents the knowledge of a training set. An input vector is applied to the nodes 422. The feedback connections 424 cause the neurons 420 to generate a new vector at the nodes 422, which through a subsequent feedback cycle generates yet another revision of the vector. Through emergent behavior, the vector generated at the nodes 422 undergoes successive changes until it stabilizes at a state at which it is identical with a corresponding training vector, although in infrequent cases of spurious recall the vector may not be identical with a training vector.

A matrix implementation of the foregoing is illustrated in FIG. 2b. N training vectors (Vector 1, Vector 2, . . . , Vector N), such as column vectors each having m.times.n elements (corresponding to the number of pixels in the movable window 304), are applied successively to an outer product generator 426 which computes the outer product matrices, Matrix 1, Matrix 2, . . . , Matrix N of the respective training vectors. The outer product matrix of a vector is one whose matrix element in the i.sup.th row and j.sup.th column is the product of the i.sup.th and j.sup.th elements of the vector. An adder 428 superimposes all of the outer product matrices together to produce a square Hopfield matrix M having m.times.n rows and m.times.n columns. A matrix multiplier 432 receives an unknown m.times.n element vector at its input 432a and multiplies it by the transformed Hopfield matrix M to produce a revised vector. An activation function 433 transforms the revised vector by taking the hyperbolic tangent (for example) of each element of the revised vector to produce a transformed vector at the output 433a of the activation function 433.

A difference sensor 436 determines whether the difference between the transformed vector at the activation function output 433a and the vector at the matrix multiplier input 432a exceeds a predetermined threshold (such as zero, for example). If so, the transformed vector at the activation function output 433a is fed back to the matrix multiplier input 432a via a feedback connection 434 to produce a new transformed vector at the activation function output 433a. The foregoing process is iteratively repeated as long as the difference sensed by the difference sensor 436 at the conclusion of each iteration exceeds the predetermined threshold. This iterative feedback process continues until the difference is less than the threshold. At this point, the vector at the activation function output 433a is one of the training vectors (e.g., Vector i), except in infrequent cases in which spurious recall occurs. The difference sensor 436 responds to the sensed difference being less than the predetermined threshold by permitting the vector at the activation function output 433a to be transmitted via a switch 438 as the final result.

To summarize thus far, in the preferred embodiment of the invention the neural network 400 is trained with two different training sets (namely, a character set and a non-character set), and the sensor 404 determines which set the produced vector belongs. In the alternative embodiment the neural network 400 is trained with a single training set (namely, the character set), and the sensor 404 counts the number of iterations performed by the neural network and compares this number with a predetermined threshold to determine whether the unknown image is a character. In yet another alternative embodiment not mentioned previously herein, the neural function 400 comprises two separate associative memories or neural networks, each one trained with a different one of the two training sets. The sensor 404 detects which one of the two associative memories required fewer iterations to reach a stable result, and classifies the unknown input image accordingly.

In the preferred embodiment, even if the Hopfield matrix M has been produced ("trained") with two different classes of training vectors (i.e., a set of vectors corresponding to all characters and a set of vectors corresponding to all possible non-characters), the Hopfield network of FIG. 2a and 2b cannot classify the output vector (e.g., Vector i) as such. It only produces a vector after a requisite number of iterations of the feedback loop 432a, 433a, 434 without indicating the training class to which the produced vector belongs.

FIGS. 5a and 5b illustrate how the invention improves neural networks of the type having no classification ability, such as the Hopfield network, to provide within the neural network itself the internal capability of classifying an output vector as belonging to a particular one of two (or more) classes of training vectors with which the neural network has been trained. The training process for such an improved neural network will first be described.

Each one of a complete set of character images 501 (FIG. 5a) corresponding to sub-images 302 (FIG. 3) captured by the window 304 whenever it is centered over individual characters in the bit-map image 306 comprises a first training set of images. Each one of a complete set of non-character images 503 (FIG. 5a) corresponding to at least nearly all possible sub-images 302 which the window 304 may capture whenever it is not centered over a single character comprises a second "non-character" training set of images. Each of the images in the two training sets is taken as an individual image 500 (FIG. 5a) of some predetermined number of m pixel rows and n pixel columns, and is supplemented by an extra pixel row 502, to transform the image to an m+1 by n image. The bits in the extra row 502 reflect the training class of the vector. For example, if image 500 is that of a character, the extra row 502 consists of all binary ones, while if the image 500 is that of a non-character, then the extra row 502 consists of all zeros. Thus, the extra pixel row 502 is a "tag" row classifying the training vector as a character or a non-character. From the resulting m+1 by n image 500, 502, a column vector 504 having n.times.(m+1) elements is formed by placing all pixels in the m+1 by n image 500, 502 in a line in a predetermined order. (This predetermined order may be arbitrary but remains consistent throughout the remainder of this description.)

The outer product matrix 506 of the vector 504 is then computed by defining each element in the i.sup.th row and the j.sup.th column of the matrix 506 as the product of the i.sup.th and j.sup.th elements of the vector 504. The outer product matrix 506 consists of (m+1).times.n rows and (m+1).times.n columns of elements. The sum 508 of the outer product matrices corresponding to all training vectors is then obtained to generate a Hopfield matrix.

Referring now to FIG. 5b, during operation, each unknown sub-image 302 captured by the window 302 of FIG. 3 has m pixel rows and n pixel columns and is supplemented with an extra row of 512 zero bits or zero-valued pixels. The supplemented m+1 by n pixel image 302, 512 is then transformed to a column vector 514 of (m+1).times.n elements in the manner described previously with reference to the column vector 504. A matrix multiplier 516 multiplies the vector 514 received at its input 516a by the Hopfield matrix M to produce a revised vector. An activation function 517 transforms the revised vector by taking the hyperbolic tangent of each element of the revised vector to produce a transformed vector at the activation function output 517a. A difference sensor 518 determines whether the difference between the vectors at the matrix multiplier input 516a and the activation function output 517a exceeds a predetermined threshold amount. If so, the vector at the activation function output 517a is fed back to the matrix multiplier input 516a to produce a next revised vector at the output 517a. This feedback process is iteratively repeated until an iteration is performed in which the difference sensor 518 senses a difference less than the threshold. At this point, the vector at the output 517a is one of the training vectors (except in infrequent cases of spurious recall), and the difference sensor 518 causes it to be transmitted as a final result. The next step is for an inspector device 520 to inspect the tag row 512 of the vector produced by the matrix multiplier 516 to determine whether the current position of the window 304 corresponds to a character or a non-character. If the tag row contents indicate a character, the current window location (or the current sub-image captured within the window) is transmitted to a downstream optical character recognition system 522.

As previously mentioned herein, in one alternative embodiment of the invention, the associative memory function 300 of FIG. 3 is trained with only the set of character images, and the conventional Hopfield network of FIG. 2b is employed as the neural function 400 of FIG. 4. In this embodiment, the sensor 404 of FIG. 4 simply counts the number of iterations in which the revised vector at the activation function output 433a of FIG. 2a is fed back to the matrix multiplier input 432a (i.e., the number of iterations in which the difference sensor detects a difference exceeding a threshold difference). For this purpose, the sensor 404 may be connected directly to the difference sensor 436 of FIG. 2b. In accordance with the emergent behavior properties of the neural network of FIG. 2b, if the number of such iterations exceeds a predetermined count (such as zero or one, for example), it is highly unlikely that the unknown image corresponds to any of the character training images, and therefore a "non-character" signal is transmitted by the sensor 404. Otherwise, a "character" signal is transmitted.

In yet another embodiment of the invention illustrated in FIG. 6, the neural function 400 of FIG. 4 is actually two separate neural networks 400a, 400b each identical to the neural network of FIG. 2b. Each of the two neural networks 400a, 400b is trained with a respective one of the two training sets, 312, 314, namely the character training set and the non-character training set. The unknown image captured within the movable window 304 is transmitted to the inputs of both neural networks 400a, 400b. Simultaneously, each of the two neural networks attempts to match the unknown image with a member of its own training set. The sensor 404 includes a pair of iteration counters 600, 602 which count the number of iterations performed by respective ones of the two neural networks 400a, 400b. A compare device 604 determines which of the two counts is less, and classifies the unknown image accordingly. For example, if the neural network 400a which was trained with true characters performed less iterations in reaching a stable result than the neural network 400b trained with-non characters, then the unknown image would be classified by the compare device 604 as a true character.

The concept in FIG. 5 of adding "tag" information to each training image so as to invest the neural network with the internal capability of outputting the classification of a vector produced in response to an unknown input vector has wide applications across a broad spectrum of industrial uses including fields other than optical character recognition. In such applications, the number of classes may equal the number of training images or training vectors, so that each training vector is uniquely identified by its tag row, the tag row of each training image differing from the tag rows of all other training images. One application in the field of optical character recognition would be character identification in the downstream OCR system of FIG. 5b. Specifically, if there are 26 training images corresponding to the 26 letters of the alphabet, the tag row would comprise at least log.sub.2 26 binary bits (for example) and each training image's tag row would containing a binary bit pattern uniquely identifying that image as a specific one of the 26 letters of the alphabet. The identification function 520 would inspect the tag row of each image output by the neural network to determine the letter identification of the unknown image received by the network. In other applications requiring a vast number K of training images or vectors, more than one tag row could be used to provide at least log.sub.2 K binary tag row bits.

While the invention has been described in detail by specific reference to preferred embodiments thereof, it is understood that variations and modifications may be made without departing from the true spirit and scope of the invention.