Pattern recognition system

• US 4,817,171 A
• Filed: 04/09/1985
• Issued: 03/28/1989
• Est. Priority Date: 04/10/1984
• Status: Expired due to Term

• Current Assignee: British Telecommunications (BT Group Plc) (BT Group PLC)
• Original Assignee: British Telecommunications PLC (BT Group PLC)
• Inventors: Stentiford, Frederick W. M.
• Primary Examiner(s): Boudreau, Leo H.
• Assistant Examiner(s): Couso, Jose L.
• Application Number:
  US06/721,402
• Time in Patent Office: 1,449 Days
• Field of Search: 382/19, 382/23, 382/25, 382/30, 382/34, 382/14, 382/15, 382/16, 382/36, 382/38, 358/263
• US Class Current: 382/195
• CPC Class Codes: G06V 10/7515 Shifting the patterns to accommodate for positional errors

Abstract

A pattern recognition system comprising pattern scanning data input means (1), a dichotomizing device (3), a feature matching device (5), a label assignment circuit (7) and a syntactic decision processing device (9). The label assignment circuit assigns labels and confidence measures to data corresponding to successive areas of the pattern. The syntactic decision processing device (9) comprises a buffer for storing area values comprising positional information, corresponding labels and confidence measures for adjacent areas in the pattern forming a two dimensional array and also comprises decision means for outputting labels and positional information for those areas whose confidence measures form two dimensional maxima with respect to those for neighboring areas in the array. The system may operate continuously as area values corresponding to successive portions of input data are added to the buffer.

Claims

1. A pattern recognition system for recognizing plural determined two-dimensional patterns located at different unknown positions within a larger two dimensional image area, said system comprising:

means for the input of electronic data representing a two-dimensional area of digitized pixel areas, each of said pixel areas having a plurality of contiguous pixels corresponding to a portion of said image area which remains unsegmented with respect to the positions of the plural patterns included therewithin to be recognized;

analysis means for analyzing successive potential character-occupying portions of said data associated with each of successive pixel areas of said unsegmented image area and for assigning to each of said pixel areas, in dependence on the corresponding said portion of data, a corresponding one label of a reference set of labels representing one of said predetermined patterns and a corresponding confidence measure indicating a degree of confidence in the assignment of said corresponding one label;

buffer means for storing area values, said area value corresponding to a plurality of said successive overlapping pixel areas forming a two dimensional array of pixel areas, said area values comprising, for each of said neighboring pixel areas, positional information defining the position of the associated pixel area in said two dimensional image and said assigned label and a corresponding confidence measure assigned to the area by said analysis means, and

decision means for outputting as electronic signals, labels and positional information corresponding to those pixel areas in said two dimensional array whose corresponding confidence measures indicate a confidence in the correctness of assignment of their corresponding labels which is in a predetermined relationship with that indicated by each of the confidence measures of other members of a two-dimensional overlapping sub-array of neighboring pixel areas within said two-dimensional array, the said relationship being such that the said labels and positional information correspond to those pixel areas whose confidence measures are maxima within each said two-dimensional sub-array.

2. A pattern recognition system according to claim 1 wherein said decision means outputs as electronic signals, labels and positional information corresponding to those areas in said two dimensional array of neighboring areas whose corresponding confidence measures indicate a confidence in assignment of their corresponding labels which is greater than or equal to that indicated by each of the confidence measured corresponding to labels assigned to some members of a two dimensional sub-array of neighboring areas in said array and greater than that indicated by each of the confidence measures corresponding to labels assigned to other members of said two dimensional sub-array of neighboring areas in said two dimensional array.

3. A pattern recognition system according to claim 1 wherein said decision means outputs as electronic signals, labels and positional information corresponding to those areas in said two dimensional array of neighboring areas whose corresponding confidence measures indicate a confidence in the correct assignment of their corresponding labels which is greater than that indicated by each of the confidence measures corresponding to labels assigned to a two dimensional sub-array of neighboring areas in said array.

4. A pattern recognition system according to claim 1 wherein said decision means outputs as electronic signals, labels and positional information corresponding to those areas in said two dimensional array of neighboring areas whose corresponding confidence measures indicate a confidence in the correct assignment of their corresponding labels which is greater than or equal to that indicated by each of the confidence measures corresponding to labels assigned to a two dimensional sub-array of neighboring areas in said array.

5. A pattern recognition system according to any one of the preceding claims wherein said two dimensional sub-array of neighboring areas in said array comprises immediately adjacent overlapping areas in said array of neighboring areas.

6. A pattern recognition system according to claim 1 wherein said two dimensional pattern comprises layers of said areas and said buffer is capable of containing area values corresponding to at least three of said layers of said areas and wherein said positional information specifying the position of said areas in said two dimensional pattern comprises an X coordinate and a Y coordinate for each area.

7. A pattern recognition system according to claim 6 wherein said decision means outputs a label and positional information (X,Y) corresponding to an area if the corresponding confidence measure indicates a confidence in the correct assignment of the label which is greater than that indicated by the confidence measures corresponding to labels assigned to the areas having positions (X-1,Y+1) (X,Y+1) (X+1,Y+1) (X+1,Y) (X+1,Y-1) and which is greater than or equal to that indicated by the confidence measures corresponding to labels assigned to the areas having positions (X-1,Y-1) (X-1,Y) (X,Y-1).

8. A pattern recognition system according to claim 6 or 7 wherein the system is capable of being operated continuously by decisions being made by said decision means in respect of an area (X,Y) in said array immediately area values for adjacent area (X+1,Y+1) have been entered into the buffer by the analysis means;

area values for layers Y and Y-1 already being in the buffer.

9. A pattern recognition system according to claim 6 wherein said buffer is capable of containing area values corresponding to at least five of said layers of said areas.

10. A pattern recognition system according to claim 9 wherein said area having corresponding positional information (X,Y) is first chosen by said decision means as being that member of a column of five immediately adjacent areas having the same X coordinate which has the confidence measure indicating the greatest confidence in the correct assignment of its corresponding label, and wherein the next column of five areas to be studied by the decision means following a decision about output in respect of area (X,Y) is centered on area (X+1,Y).

11. A pattern recognition system according to claim 6 wherein said buffer is capable of containing area values corresponding to at least five of said layers of areas and wherein for an area having positional information (X,Y) said sub-array of neighboring areas in said array comprises the areas having positional information (X±

1,Y±

1) (X±

2,Y±

2) (X±

1,Y) (X±

1,Y±

2) (X±

2,Y±

1) (X±

2Y) (X,Y±

1) (X,Y±

2).

12. A pattern recognition system according to claim 11 wherein the system is capable of being operated continuously by decisions being made by said decision means in respect of an area (X,Y) in said array immediately area values for the area (X+2, Y+2) have been entered into the buffer by the analysis means;

area values for layers (Y+1), Y, (Y-1) and (Y-2) already being in the buffer.

13. A pattern recognition system according to claim 1 wherein said analysis means comprises:

a shift register having a plurality of cells through which said data for said image area is continuously step-wise fed pixel-by-pixel;

a plurality of feature detectors each for detecting the data content of a set of said register cells;

means for reading the feature detectors simultaneously at each step of said data through said register; and

means for comparing the simultaneous readings from each of said feature detectors with predetermined reference vectors each corresponding to a label and assigning that label whose reference vector most closely matches said simultaneous readings together with a corresponding confidence measure to the area corresponding to the data in said register which produced said simultaneous readings.

14. A pattern recognition system according to claim 13 wherein said sets of register cells to which said feature detectors are connected are arranged in said shift register such that said features are detected in a portion of data passing through said shift register at a plurality of different times and wherein said system further comprises time delay circuits connected to the outputs of said feature detectors enabling said feature detectors to be read simultaneously in respect of each portion of data passing through said shift register and wherein said shift register contains a greater number of cells than would be required if said features were detected simultaneously without said delay circuits.

15. An optical character recognition system according to claim 1 wherein optical scanning means provide said electronic data input and any area not assigned a label corresponding to a reference character class is assigned the label "space" and a confidence measure corresponding to the least confident assignment possible.

16. An optical character recognition system according to claim 1 in which all areas having confidence measures indicating less confidence in the assignment of the correct corresponding label than a predetermined threshold confidence level are assigned the label "space".

17. A pattern recognition system in which the relative positions of plural patterns to be recognized within input data are automatically determined as a part of a pattern recognition analysis procedure thereby avoiding the need to preprocess and/or segment the incoming data to initially determine such positions prior to pattern recognition analysis, said system comprising:

data input means for supplying a continuous stream of digitized binary-valued data representing successive data values of a raster-scanned array of data values containing plural of predetermined patterns therein and with said data values defining a two-dimensional grid of x,y coordinates overlaying said array;

feature matching means connected to receive said continuous data and to continuously identify the existence of any of N predetermined features located within an area of P×

Q data values located at successive X,Y coordinates within said array and to produce an N-dimensional feature vector for each such X,Y coordinate;

label assignment means connected to continuously receive said N-dimensional feature vectors and to continuously assign one of a predetermined set of M pattern labels to each such feature vector together with an accompanying confidence factor for each such X,Y coordinate; and

syntactic processing means connected to continuously receive said assigned pattern labels and accompanying confidence factors for each such X,Y coordinate and, by comparing such assigned labels and confidence factors for one X,Y coordinates so as to locate local maxima of confidence factors therein, to output recognized pattern data representing the sequence of predetermined patterns recognized in said array together with their relative position therewithin.

18. A pattern recognition method in which the relative positions of plural patterns to be recognized within input data are automatically determined as a part of a pattern recognition analysis procedure thereby avoiding the need to preprocess and/or segment the incoming data to initially determine such positions prior to pattern recognition analysis, said method comprising the steps of:

supplying a continuous stream of digitized binary-valued data representing successive data values of a raster-scanned array of data values containing plural of predetermined patterns therein with said data values defining a two-dimensional grid of x,y coordinated overlaying said array;

continuously identifying the existence of any of N predetermined features located within an area of P×

Q data values located at successive X,Y coordinates within said array and producing an N-dimensional feature vector for each such X,Y coordinate;

continuously assigning one of a predetermined set of M pattern labels to each such feature vector together with an accompanying confidence factor for each such X,Y coordinate; and

continuously receiving said assigned pattern labels and accompanying confidence factors for each such X,Y coordinate and, by comparing such assigned labels and confidence factors for one X,Y coordinate to those associated with neighboring X,Y coordinates so as to locate local maxima of confidence factors, outputting recognized pattern data representing the sequence of predetermined patterns recognized in said array together with their relative positions therewithin.