Patent GB-1106972-A (GB)
Title: Improvements in or relating to character recognition systems
Inventor: WEAVER JOHN ANTHONY
IPC: G06V30/192
Filed: 1964-01-30
Abstract: 1,106,972. Automatic character reading. MULLARD Ltd. 23 April, 1965 [30 Jan., 1964], No. 4084/64. Heading G4R. Character reading apparatus comprises means for exploring a character, means for detecting ends and loops as features of the character and means for forming a coded word representing a list of character features including all ends and loops detected together with their positions in the character. An end is the end of a line (excluding serifs) where the outer edge of the character, which is followed by a scanning arrangement, changes direction by 180 degrees in a short distance. A loop is a part having an inner edge forming a closed path enclosed within the outer edge of the character. In the form described, curves and junctions of lines are also detected and included in the feature list. The character is scanned by a flying spot scanner and the results are punched on paper tape. The data from the tape is entered into a computer as shown diagrammatically in Fig. 2. The characters sensed are reconstituted as binary patterns in the matrix store of the computer. A character may occupy 63 x 63 positions. The character signals are then subject to a noise reduction programme which in effect looks at each sub-matrix of 3 x 3 positions and designates the centre position " 1 " or " 0 " according to predetermined rules. Three possible programmes are described for doing this, one being described in Specification 1,106,974. The resulting character patterns are stored in matrix 1 in which it thus subjected to an outline tracing process. This is programmed to fill gaps in lines and to extract certain sub-features: loops, curves, angles and ends of lines. The programme begins by scanning through matrix 1 until it finds a large area of black. It then traces round the outside edge of this area detecting sub-features on the way. When it comes across a line end it goes into the gap-filling routine, Fig. 14 (not shown), to see if it is a genuine line end or merely a gap. In the latter case it is bridged and the trace continues beyond the gap and black points are inserted in matrix 1 to fill the gap. In the former case the attempt to bridge the gap is abandoned and tracing begins again from the point it had reached, until it returns to the original position. The path actually followed by the trace is entered as a pattern of dots in matrix 2 and coded representations of any subfeatures found are also entered in matrix 2. If a gap was filled matrix 2 is cleared and the process is repeated on the filled pattern of matrix 1. The tracing procedure progress round the edge of a character by jumping to an adjacent point in one of eight directions (Fig. 12, not shown). The programme is guided by a " permanent " direction signal which attempts to move the trace in one of these directions. This is the direction of the last successful jump. If the trace having jumped in the same direction again finds no black point, the other directions are tried in a predetermined sequence until a black point is found. This then becomes the new " permanent " direction. After each successful jump the point to which the jump has been made is entered in matrix 2 so that eventually the outline of the character is stored. Also a count is kept of the X and Y excursions and the total number of jumps required to go round the character. The character is rejected if this exceeds a preset maximum. Also a record is kept of the successive directions averaged over a number of jumps. This is called the " trend " direction. The size of the character in matrix 2 is compared with the size of another character (the largest to date) which is stored in matrix 3. If the matrix 2 character is larger, it and the sub-feature list are put in matrix 3 and the character from matrix 3 is put in matrix 4. If the matrix 3 character is larger then the character in matrix 2 goes to matrix 4, the sub-features being discarded. Matrix 2 is then cleared. This process is repeated for all the characters in matrix 1 and at the end of the process the outline of the largest character is in matrix 3 and the outside edges of all the smaller characters will be in matrix 4. If the largest character in matrix 3 is not sufficiently large it is rejected. Matrix 1 is then scanned again looking for the inside contours and these patterns are passed from matrix 2 of matrix 5 (which stores only the largest). Sub-features.-The test for line ends is that the trend direction reverses in a small number of jumps. Angles are indicated when more than a certain change of trend direction occurs within a given number of jumps. At the end of the trace any angles which have also been indicated as ends are rejected. The remaining angles with their X and Y positions are entered in the sub-feature list. For a curve to be indicated the line must be more than a certain length, that is, it must involve more than a given number of jumps. There must be a sufficient change in trend direction and the direction of change of trend must be constant. A curve can end in a line-end, an angle or a curve of opposite direction (as in " S "). Matrix 5 contains the inside contour, if any, of the largest character, i.e. the character of which the outside profile in matrix 3. If there is a pattern in matrix 5, a loop is indicated since a loop is defined as a closed edge totally enclosed within another closed edge. Sorting and testing sub-features.-In the next block functions are detected from the presence of more than one angle in a similar position. Serifs are suppressed in certain cases, and inner and outer curve indications are condensed to a single curve feature. The output is a list of features with the X, Y co-ordinates of their positions. Coding.-This list of features and positions is then coded as described in Specification 1,106,973. The list is first rearranged in clockwise order of occurrence. After coding, the features represent the description of the character in the form of a binary word. The list may be repeatedly recycled, the first item being placed last and so on. This corresponds to an orientation of the original character. The character may be recognized by a switching network controlled by these features or the feature list may be compared with lists for all characters in a dictionary store. Learning.-For the purpose of filling the dictionary store initially the character signals entered on the tape may have a label identifying the character. This identification is added to the features in the coder and entered in the dictionary. A comparison takes place with all the stored lists in turn and the coded list is entered as a new word only if it is not already there. The process is similar for recognition, the coded list is compared with the stored lists and agreement identifies the character.