Method and apparatus for symbol recognition using multidimensional preprocessing at multiple resolutions

• US 5,337,372 A
• Filed: 10/13/1992
• Issued: 08/09/1994
• Est. Priority Date: 10/13/1992
• Status: Expired due to Fees

• Current Assignee: American Telephone & Telegraph Company (AT&T, Inc.), Telecommunication Laboratories
• Original Assignee: AT&T, Inc.
• Inventors: Wu, Quen-Zong, LeCun, Yann A.
• Primary Examiner(s): Boudreau, Leo H.
• Application Number:
  US07/959,895
• Time in Patent Office: 665 Days
• Field of Search: 382/36, 382/37, 382/38, 382/14, 382/27, 382/49
• US Class Current: 382/205
• CPC Class Codes: G06V 30/2504 Coarse or fine approaches, e.g. resolution of ambiguities or multiscale approaches

Abstract

Data samples describing a plurality of micro-segments that compose a symbol to be recognized are received from a device such as an electronic pad. Preprocessors map the micro-segments into cells of a plurality of feature arrays with different resolutions. Preprocessors assign values to the cells based on the length of a micro-segment associated with the cell, and how well the features of the associated micro-segment correspond to the feature label of the cell. The cell values are used as inputs to comparators that compare the feature arrays with reference arrays. The results of comparisons involving lower resolution feature arrays and reference arrays, are used to limit the number of comparisons involving higher resolution feature arrays and reference arrays. The highest resolution comparison selects the reference array that identifies the symbol to be recognized.

Claims

1. An apparatus for recognizing symbols, comprising:

first preprocessor means responsive to an applied plurality of micro-segments which describes a symbol, for associating a micro-segment with a first plurality of cells of a first feature cellular array, where each of said cells has a first associated feature label, and

for assigning a cell value to a cell, using a micro-segment value that is related to how well a feature of said micro-segment associated with said cell corresponds to said cell'"'"'s feature label;

means for selecting a subset of reference cellular arrays from a first plurality of reference cellular arrays based on a similarity between each of the subset reference cellular arrays and said first plurality of cells;

second preprocessor means for associating said micro-segment with a second plurality of cells of a second feature cellular array where each of said cells has a second associated feature label; and

comparator means for recognizing said symbol based on a similarity between said second plurality of cells and a reference cellular array in a second plurality of reference cellular arrays identified by said subset of reference cellular arrays.

2. The apparatus of claim 1, further comprising means for delimiting said plurality of applied micro-segments from an incoming stream of micro-segments that define a plurality of symbols.

3. The apparatus of claim 1, further comprising means for decreasing a number of reference cellular arrays in said first plurality of reference cellular arrays based on an initial examination of said symbol'"'"'s features.

4. The apparatus of claim 1, wherein said first plurality of cells comprise less cells than said second plurality of cells.

5. The apparatus of claim 1, wherein said first preprocessor means assigns said cell value using a sum of micro-segment values from a plurality of micro-segments associated with said cell.

6. The apparatus of claim 1, wherein said first preprocessor means assigns said cell value using said micro-segment value that is also related to a length of said micro-segment associated with said cell.

7. The apparatus of claim 1, wherein said first preprocessor means assigns said cell value based on a micro-segment associated with another cell.

8. An apparatus for recognizing symbols, comprising:

first preprocessor means responsive to an applied plurality of micro-segments which describes a symbol, for associating a micro-segment with a first plurality of cells of a first feature cellular array, where each of said cells has a first associated feature label;

means for selecting a subset of reference cellular arrays from a first plurality of reference cellular arrays based on a similarity between each of the subset reference cellular arrays and said first plurality of cells;

second preprocessor means for associating said micro-segment with a second plurality of cells of a second feature cellular array where each of said cells has a second associated feature label, and

for assigning a cell value to a cell in said second plurality of cells, using a micro-segment value that is related to how well a feature of said micro-segment associated with said cell corresponds to said cell'"'"'s feature label; and

comparator means for recognizing said symbol based on a similarity between said second plurality of cells and a reference cellular array in a second plurality of reference cellular arrays identified by said subset of reference cellular arrays.

9. The apparatus of claim 8, further comprising means for delimiting said plurality of applied micro-segments from an incoming stream of micro-segments that define a plurality of symbols.

10. The apparatus of claim 8, further comprising means for decreasing a number of reference cellular arrays in said first plurality of reference cellular arrays based on an initial examination of said symbol'"'"'s features.

11. The apparatus of claim 8, wherein said first plurality of cells comprise less cells than said second plurality of cells.

12. The apparatus of claim 8, wherein said second preprocessor means assigns said cell value using a sum of micro-segment values from a plurality of micro-segments associated with said cell.

13. The apparatus of claim 8, wherein said second preprocessor means assigns said cell value using said micro-segment value that is also related to a length of said micro-segment associated with said cell.

14. The apparatus of claim 8, wherein said second preprocessor means assigns said cell value based on a micro-segment associated with another cell.

15. An apparatus for recognizing symbols, comprising:

first preprocessor means responsive to an applied plurality of micro-segments which describes a symbol, for associating a micro-segment with a first plurality of cells of a first feature cellular array, where each of said cells has a first associated feature label, and

for assigning a cell value to a cell in said first plurality of cells, using a first micro-segment value that is related to how well a feature of said micro-segment associated with said cell corresponds to said cell'"'"'s feature label;

means for selecting a subset of reference cellular arrays from a first plurality of reference cellular arrays based on a similarity between each of the subset reference cellular arrays and said first plurality of cells;

second preprocessor means for associating said micro-segment with a second plurality of cells of a second feature cellular array where each of said cells has a second associated feature label, and

for assigning a cell value to a cell in said second plurality of cells, using a second micro-segment value that is related to how well a feature of said micro-segment associated with said cell corresponds to said cell'"'"'s feature label; and

means for recognizing said symbol based on a similarity between said second plurality of cells and a reference cellular array in a second plurality of reference cellular arrays identified by said subset of reference cellular arrays.

16. The apparatus of claim 15, further comprising means for delimiting said plurality of applied micro-segments from an incoming stream of micro-segments that define a plurality of symbols.

17. The apparatus of claim 15, further comprising means for decreasing a number of reference cellular arrays in said first plurality of reference cellular arrays based on an initial examination of said symbol'"'"'s features.

18. The apparatus of claim 15, wherein said first plurality of cells comprise less cells than said second plurality of cells.

19. The apparatus of claim 15, wherein said first and second preprocessor means assign said cell values using a sum of micro-segment values from a plurality of micro-segments associated with said cells.

20. The apparatus of claim 15, wherein said first and second preprocessor means assign said cell values using said micro-segment values that are also related to a length of said micro-segments associated with said cells.

21. The apparatus of claim 15, wherein said first and second preprocessor means assign said cell values based on a micro-segment associated with another cell.