Algorithm for the segmentation of printed fixed pitch documents

A method for segmenting characters in a row of characters comprising the following steps:

• generating a row of video data representative of the row of characters;
• generating a segmentation template for segmenting said characters, said template being characterized by a matrix of values displaced a predetermined distance within a range of picture elements with a weighted average being assigned to each value;
• overlaying said segmentation template on the row of video data;
• shifting the template within a predetermined distance;
• generating a table of weighted conflict scores and a corresponding table of probable segmentation coordinates for each shift;
• and
• selecting the segmentation coordinate with the lowest weighted conflict scores as the final segmentation coordinates.

Segmentation method for character recognition comprising:

• generating a row of video data representative of the row of characters;
• generating a segmentation template for segmenting said characters, said template being characterized by a plurality of vertical lines with each vertical line being assigned a weight which reduces away from a selected vertical line;
• overlaying said segmentation template on the row of video data to identify columns of the data;
• summing the products of the weight of each line with a vertical histogram of the associated data column to give a total figure of merit for the column represented by the central line;
• and
• shifting the template within a predetermined distance and repeating the process wherein a column coinciding with the selected vertical line having the best figure of merit is the point of segmentation.

An apparatus for finding a baseline associated with a row of characters comprising:

• a storage means operable to store video data representative of the horizontal histogram for a plurality of sectored video scans;
• a means to access the storage means and to generate values representative of the baseline associated with each sector;
• a means for interrogating the values and to eliminate values which deviate from adjoining values;
• and
• arithmetic means to concatenate the remaining values and to generate a single baseline therefrom.

A device for segmenting a line of characters into words comprising:

• first means for storing a row of characters;
• means to access the stored characters and to generate "white" and "black" projections therefrom;
• second means to store the projections;
• and
• arithmetic means for manipulating the projections so that black projections are being forced to be multiple of pitch width and the multiple pitch width black projections are being selectively concatenated, thereby removing intercharacter white projections.

An apparatus for determining the underscore associated with a document comprising:

• a first means for generating a first set of data representative of a baseline for each row of data in said document;
• a horizontal histogram means for generating a second set of data representative of a horizontal histogram for the row;
• a first control logic means for correlating the first set of data with the second set of data and to generate a third set of data representative of a datum zone;
• and
• a second control logic means for defining a window of search below said datum zone and to interrogate the window of search at the internal boundaries to determine underscore.

An apparatus for segmenting a stream of video data into characters comprising:

• means for segmenting the stream of video data into word boundaries;
• means for identifying beginning and ending coordinates of a word;
• means for identifying the pitch of said video data;
• means for summing the pitch with the beginning of word coordinates to identify a probable segmentation coordinate;
• and
• means for correlating the probable segmentation coordinate with a vertical histogram to define a final segmentation point.

A segmentation apparatus adaptable for use with an Optical Character Recognition (OCR) device including a scanner for scanning a document and generating a video stream of data representative of the information contents of said document, said segmentation apparatus comprising in combination:

• a storage means coupled to the scanner and operable to store the video data;
• a horizontal histogram means coupled to the storage means, said horizontal histogram means being operable for generating horizontal histograms for the video data in said storage means;
• a find baseline unit means coupled to the horizontal histogram means and operable for finding a baseline for data in said storage means;
• a vertical histogram means coupled to the storage means and the find baseline unit means and operable for generating a vertical histogram for data in the storage means;
• a find word unit means coupled to the vertical histogram means and operable for finding the coordinates for each word location for a line of data in said storage means;
• a character segmentation means connected to the find word unit means and operable for segmenting the words into characters;
• shift means connected to the character segmentation means and operable to shift a character from the storage means;
• and
• a controller for enabling the operation of said segmentation apparatus.