Algorithm for the segmentation of printed fixed pitch documents
First Claim
1. A method for segmenting data in an OCR device, said method comprising the following steps:
- generating a video stream of data representative of the information contents of a line of data to be segmented;
generating a horizontal histogram for the video stream of data;
determining a baseline for the video stream of data;
generating a vertical histogram for the video data;
first generating the coordinates for each word in the video stream of data; and
second generating the coordinate for each character associated with a word.
0 Assignments
0 Petitions
Accused Products
Abstract
An apparatus and method is provided for segmenting characters generated by an optical scanner. The apparatus also identifies underscores. The underscores are then masked and subsequent processing devices are informed of the existence of said underscores. Input video raster scans representative of a portion of a line of textual material are loaded into a video buffer. The video raster scans are broken up into a plurality of sections. The horizontal histogram (number of black pixel counts) associated with each section is determined. The baseline, vertical histogram and word location for each line of data to be segmented is determined. A find character unit finds the boundaries for each character. The character is sequentially transferred from the video buffer to a character output buffer.
78 Citations
18 Claims
-
1. A method for segmenting data in an OCR device, said method comprising the following steps:
-
generating a video stream of data representative of the information contents of a line of data to be segmented; generating a horizontal histogram for the video stream of data; determining a baseline for the video stream of data; generating a vertical histogram for the video data; first generating the coordinates for each word in the video stream of data; and second generating the coordinate for each character associated with a word.
-
-
2. 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. - View Dependent Claims (3)
-
-
4. 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. - View Dependent Claims (5)
-
-
6. 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.
-
-
7. 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.
-
-
8. 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. - View Dependent Claims (9, 10)
-
-
11. 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.
-
-
12. 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. - View Dependent Claims (13, 14, 15, 16, 17, 18)
-
Specification