System and method for character presence detection

• US 4,173,015 A
• Filed: 08/16/1978
• Issued: 10/30/1979
• Est. Priority Date: 08/16/1978
• Status: Expired due to Term

• Current Assignee: Bantec Incorporated
• Original Assignee: Recognition Equipment Incorporated
• Inventors: Bourek, Leon H., Owens, Charles D., Sikes, Johnnie C. Jr.
• Primary Examiner(s): Boudreau, Leo H.
• Application Number:
  US05/934,232
• Time in Patent Office: 440 Days
• Field of Search: 340/146.3 H, 340/146.3 SG, 340/146.3 Y, 340/146.3 D
• US Class Current: 382/178
• CPC Class Codes: G06V 30/10 Character recognition
• CPC Class Codes: G06V 30/148 Segmentation of character regions

Abstract

A system and method for character presence detection having the capability of locating characters within a line of characters represented by a binary stream of data bits. The stream of binary data bits is divided into scans which correspond to scans of a photocell array. The system for character presence detection receives the binary stream. Each data bit has a unique position within its particular scan, which corresponds to the selection of a particular photocell of the photocell array as the output thereof, and, therefore, the binary stream of data bits comprises an image corresponding to alphanumeric characters disposed upon a written medium. That is, the data bits comprise an image of characters which form a line disposed along a written medium. Within the binary stream, some data bits represent character information and the remainder represents background information. The system compares each scan to a plurality of criterion, each criterion being unique, and forms a series of character segments and spaces based on the results of the comparison of each scan to each of the criterion. The character segments and spaces of one series formed by one of the criterion is selected based on the average number of data bits which contain character information per scan. A recycle number is calculated based on the average number of data bits containing character information per scan, the average scans per character segment, and the standard deviation of the scans comprising the character segments. The recycle number is compared against the character segment which form combined character segments by combining adjacent character segments and the space there between if the combined character is comprised of a number of scans which is less than the recycle number. A new recycle number is calculated based on the combined character segments and this new recycle number is utilized to form new combined character segments from the original character segments. This process continues until the recycle number newly calculated is the same as the prior recycle number calculated. The final combined character segments formed by application of the recycle number are tested against certain limits to detect character segments which were improperly combined. The standard deviation calculated which is based on the combined character segments and the average number of scans per combined character segment is utilized to calculate a suspect character width and minimum and maximum natural break numbers.

Claims

1. System for character presence detection locating characters within a line of characters represented by data bits in a binary stream which is divided into scans, at least some of said data bits corresponding to character information representing said characters, comprising:

a plurality of scan detectors receiving said binary stream and signalling when the data bits in one scan contain character information conforming to certain criteria, each scan detector having a different criterion;

a pluraity of segment generators, each segment generator in electrical communication with one of said scan detectors for storing into a memory as a series the number of consecutive scans meeting each criteria as a character segment (C) and the number of scans between said character segments as spaces (S) in said series;

an averaging means for selecting one series of said character segments stored within said memory as determined by the average number of data bits containing character information per scan for said line;

arithmetic means connected to said averaging means and to said memory for deriving a recycle number based on said average number (BAV) of data bits containing character information per scan, the average scans (ACW) per character segment, and the standard deviation (SD) of the number of scans in said character segments; and

combination means for receiving said recycle number combining adjacent character segments (CC) of the selected series and the spaces (CS) there between until the addition of another character segment exceeds said recycle number to form a series of combined character segments, said arithmetic means deriving other recycle numbers for use by said combination means utilizing said combined character segments until the recycle number derived is approximately equal to the prior recycled number derived by said arithmetic means.

2. System for character presence detection as set forth in claim 1 wherein at least four consecutive scans must meet certain criteria for said memory to store as a character segment within said storage.

3. System for character presence detection as set forth in claim 1 wherein said criteria are based on the distribution of data bits containing character information within said one scan.

4. System for character presence detection as set forth in claim 1 wherein said arithmetic means utilizes only character segments greater than eight scans to derive the recycle number.

5. System for character presence detection as set forth in claim 1 including a first detector connected to receive said binary stream for signalling the occurrence of scans without any data bits containing character information, and wherein each segment generator is operationally connected to said first detector for storing the number of scans without data bits containing character information for each space (S).

6. System for character presence detection as set forth in claim 1 wherein the recycle number (RC) is derived in accordance with the following formula:

space="preserve" listing-type="equation">RC=(10-BAV)+ACW+SD.

7. System for character presence detection as set forth in claim 1 wherein each data bit occupies a unique data bit position with its particular scan and including a sneak through means connected to receive said binary stream for signalling to each segment generator the absence of any data bit position containing character information for a predetermined number of consecutive scans.

8. System for character presence detection as set forth in claim 7 wherein said predetermined number of consecutive scans includes the scan currently being received, and said predetermined number of consecutive scans is four.

9. System for character presence detection as set forth in claim 1 including means calculating a suspect character width (SCW) based on the average width (ACS) of the series of combined character segments, the standard deviation (SD) of the combined character segments, and the number (P) of combined character segments greater than ACS+SD.

10. System for character presence detection as set forth in claim 9 including means calculation, a natural break maximum (NBMAX) and minimum (NBMIN) based on the number (P), SD and ACS.

11. System for character presence detection as set forth in claim 10 wherein NBMAX and NBMIN are derived in accordance with the following formula:

space="preserve" listing-type="equation">NBMAX=(2×

ACS)=SD-P, and

space="preserve" listing-type="equation">NBMIN=(2×

ACS)+5-P.

12. System for character presence detection as set forth in claim 11 including recovery means connected to receive SCW, NBMAX and NBMIN for forming a series of combined recovery character segments (CRC) and spaces (CRS) by determining if at least one combined character segment (CC) is greater than SCW to sum said one combined character segment with one adjacent combined character segment and the CS there between forming two CRC having approximately equal widths if the sum is within the inclusive range of NBMIN and NBMAX.

13. System for character presence detection as set forth in claim 11 wherein each combined character segment greater than NBMIN is adjusted to form two CRC of equal widths with a one scan space there between if the adjusted character is comprised of an odd number of scans.

14. System for character presence detection as set forth in claim 11 including delimiter means for declaring each space greater than a delimiter value (D) as a void between words in said line rather than gaps between characters within the same word.

15. System for character presence detection as set forth in claim 14 wherein said delimiter value (D) is in accordance with the following formula:

space="preserve" listing-type="equation">D=2×

AVS+T,

where AVS is the average space width and T is the standard deviation of the spaces, excluding spaces greater than 25 scans.

16. A system for character presence detection receiving a binary data stream comprised of data bits and divided into scans, at least some of said data bits contain character information representing a plurality of characters disposed along the line, said system forming at least one series of character (C) segments with spaces (S) there between, each scan of said character segments (C) meeting certain predetermined criteria and based on the relationships between data bits within said scan, said system forming a series of combined character segments (CC) including each of said character segments and each of said spaces (CS) there between by combining any adjacent character segments (C) and the spaces (S) there between meeting preselected conditions, comprising:

means for calculating a suspect character width (SCW) from said combined character segments (CC) in accordance with the formula;

SCW=ACW+(ACW÷

SD), where ACW is the average combined character width and SD is the standard deviation excluding those less than 8, means for calculating an inclusive natural break range having a minimum (NBMIN), and maximum (NBMAX) values in accordance with the following formulas;

NBMAX=2×

ACW+5-P, NBMIN=2×

ACW-SD-P, where P represents the number of combined character segments greater than ACW+SD,

means for comparing each combined character segment to the SCW to determine if any combined character segments exceed the SCW,

summing means connecting to said means for comparing forming the sum of said combined character segments exceeding the SCW, one combined segment adjacent thereto, and the space there between,

means for adjusting widths of the combined character segments and the spaces there between to form two combined recovery character segments of equal widths if the said sum is within the inclusive range of NBMAX and NBMIN, the total of said equal widths being approximately equal to the said sum.

17. System for character presence detection as set forth in claim 16 wherein said summing means which utilizes a prior combined character segment in said series as said one combined character segment, and wherein said summing means in response to said means for adjusting, if said sum is outside the inclusive range of NBMAX and NBMIN, to utilize a subsequent combined character segment in said series as said one combined character segment.

18. System for character presence detection as set forth in claim 16 wherein said means for adjusting forms a series of combined recovery character segments (CRC) and combined recovery spaces (CRS) which includes each combined character segment less than and equal to the suspect character width and outside the range of NBMAX and NBMIN and including means for determining spaces representing voids between words and spaces representing gaps between characters within the same word by declaring all spaces greater than 14 scans and also greater than a delimiter value D as voids in accordance with the formula:

D=2×

AVS+T, where AVS is the average width of the CRS and T is the standard deviation of the CRS, excluding spaces greater than 25.

19. System for character presence detection as set forth in claim 16 including means for comparing each of said combined character segments to determine if any of said combined character segments are greater than NBMIN for adjusting the combined character segment to form a pair of combined character segments having a width of approximately 1/2 of the width of the combined character segment.