Each of a certain number of sequences of binary pixels chosen according to some prescribed rules from m.times.n matrix of pixcels is referred to vector v.sub.i. A standard character k is represented with m.times.n matrix of binary pixels, from which the vectors g.sub.ki are derived. The reference vectors G.sub.ki are comprised of the vectors g.sub.ki and g.sub.ki which are generated by modification of g.sub.ki. A recognition object is captured to yield m.times.n matrix of binary pixels, from which the vectors v.sub.i are derived for comparison with the reference vectors G.sub.ki. Matching of v.sub.i with one of the reference vectors G.sub.ki adds a count to the standard pattern k corresponding to G.sub.ki. The standard character k with the maximum score of the matching count is recognized as the recognition object.
The invention provides a technique for pattern recognition that employs a state machine that incorporates a sequence of table-look-up operations. A sequence of input parameters, derived according to an application-specific algorithm, generates a corresponding sequence of memory addresses for these operations. The memory tables are organized in a hierarchical structure that corresponds to the input sequence. Table data is designed to recognize a specific library of input patterns. An input sequence traces an input-specific path through the memory tables until one of the patterns in the library is recognized or until it is determined that the input sequence is inconsistent with f the library patterns. For each library pattern, the table data is designed to accommodate the variations in the input values that are specific to the application (e.g., variations due to noise and/or tolerances). Table data can be derived by analysis, simulation, learning or a combination of these methods. The invention can replace neural networks or DSP correlation techniques in real-time applications. It achieves very high performance by comparing the input sequence to all of the patterns in the library simultaneously. The invention can be employed to improve the image quality of a caligraphic display system that uses flat-panel display technology. A method for improving the performance of display systems that employ image memories.
The invention provides a technique for pattern recognition that employs a state machine that incorporates a sequence of table-look-up operations. A sequence of input parameters, derived according to an application-specific algorithm, generates a corresponding sequence of memory addresses for these operations. The memory tables are organized in a hierarchical structure that corresponds to the input sequence. Table data is designed to recognize a specific library of input patterns. An input sequence traces an input-specific path through the memory tables until one of the patterns in the library is recognized or until it is determined that the input sequence is inconsistent with any of the library patterns. For each library pattern, the table data is designed to accommodate the variations in the input values that are specific to the application (e.g., variations due to noise and/or tolerances). Table data can be derived by analysis, simulation, learning or a combination of these methods. The invention can replace neural networks or DSP correlation techniques in real-time applications. It achieves very high performance by comparing the input sequence to all of the patterns in the library simultaneously. The invention can be employed to improve the image quality of a caligraphic display system that uses flat-panel display technology. A method for improving the performance of display systems that employ image memories to refresh a computer generated image is also disclosed.
A computer system and method for generating probability tables for use in recognizing handwritten characters. The system receives handwritten characters as a sequence of strokes. The system characterizes each stroke by its shape and position. The position is represented as a pair of coordinates specifying the starting and ending points of the stroke. The system represents an input handwritten character by a string representing the shapes of the strokes and by a string of the pairs of coordinates of the strokes. The strings are ordered by the sequence in which the strokes are written. The system compares all possible pairs of a large sample of handwritten characters one to another by comparing the shape and position of each stroke in one character with those of the corresponding stroke of the other character. When comparing the two strokes, the system generates a pair of shapes and the sum of the squared distances between the starting points and the ending points of the two strokes. Based on these comparisons, the system generates the probabilities that any two handwritten characters that have the same number of strokes and that have a certain pair of shapes in the same relative place in their strings will represent the same character and that any two handwritten characters that have the same number of strokes and that have a pair of positions in the same relative place in their corresponding strings such that the sum of distances between the pair of positions is a certain distance, will represent the same character.
A method and apparatus are provided for identifying differences between a stored pattern and a matching image subset, where variations in pattern position, orientation, and size do not give rise to false differences. The invention is also a system for analyzing an object image with respect to a model pattern so as to detect flaws in the object image. The system includes extracting pattern features from the model pattern; generating a vector-valued function using the pattern features to provide a pattern field; extracting image features from the object image; evaluating each image feature, using the pattern field and an n-dimensional transformation that associates image features with pattern features, so as to determine at least one associated feature characteristic; and using at least one feature characteristic to identify at least one flaw in the object image. The invention can find at least two distinct kinds of flaws: missing features, and extra features. The invention provides pattern inspection that is faster and more accurate than any known prior art method by using a stored pattern that represents an ideal example of the object to be found and inspected, and that can be translated, rotated, and scaled to arbitrary precision much faster than digital image re-sampling, and without pixel grid quantization errors. Furthermore, since the invention does not use digital image re-sampling, there are no pixel quantization errors to cause false differences between the pattern and image that can limit inspection performance.
A method is provided for finding a whole pattern in an image, where at least a portion of the whole pattern falls outside the boundary of the image. The method includes, for each candidate pose of a search model of the whole pattern that results in a transformed search model that may extend beyond the boundary of the image, applying a match-quality metric to only a subset of search model features and corresponding image features, the subset being uniquely determined by the pose. The features which do not overlap the image at that pose of the model are completely excluded from the metric computation. All the relevant available information is used, using no arbitrarily hypothesized information. The higher-level strategy of the search procedure is free to consider poses where the model extends partially outside the image, and the results of each metric computation will be the most true value possible.
