Method and apparatus for vectorizing documents and symbol recognition

Claim 1

An apparatus for coding a graphic image from raster digital signals defining light intensities of the graphic image along sequential scan lines, such apparatus comprising: data compression means for extracting coordinates of a run of like-valued signals along a scan line; correlating means for correlating coordinates for a given run from the data compression means with a new or previously scanned vector; vector memory means for storing data pertaining to each vector with respect to which the correlating means has correlated run data; processing means, operative on coordinates of the given run and on data read from the vector memory means related to a correlated vector, for determining whether the given run's coordinates define a continuation of the correlated vector to within a prescribed degree of accuracy; and means for clearing the data related to the correlated vector from the vector memory means when the procssing means determines that the given run's coordinates do not represent a continuation of the vector to within the Prescribed degree of accuracy and for causing data corresponding to the correlated vector to be given as an output.

Claim 2

An apparatus for coding a graphic image from raster digital signals defining light intensities of the graphic image along sequential scan lines, such apparatus comprising: data compression means for extracting coordinates of a run of like-valued signals along a scan line; correlating means for correlating coordinates for a given run from the data compression means with a new or previously scanned vector; vector memory means for storing data pertaining to each vector with respect to which the correlating means has correlated run data; processing means, operative on coordinates of the given run and on data read from the vector memory means related to a correlated vector, for determining whether the given run's coordinates define a continuation of the correlated vector to within a prescribed degree of accuracy; and means for clearing the data related to the correlated vector from the vector memory means when the procssing means determines that the given run's coordinates do not represent a continuation of the vector to within the Prescribed degree of accuracy and for causing data corresponding to the correlated vector to be given as an output.

Claim 11

An apparatus for coding binary data representing sequential scan line signals indicative of portions of an image field, such apparatus comprising: data compression means for extracting from such data coordinates descriptive of each run of consecutive like-valued signals in a scan line, such coordinates being indicative of the width and location on such scan line of the runs; and processing means operative on the coordinates for representing the scanned image field invariably and entirely as a piecewise trapezoidal approximation, wherein (i) each of the two parallel sides of each trapezoid in the approximation is coincident with a scan line; (ii) the other two sides of each trapezoid are not necessarily parallel to one another; and (iii) the number of scan line lines between the two parallel sides of each trapezoid is determined directly from processing the coordinate data and is not necessarily an integral multiple of a fixed integer greater than one.

Claim 12

An apparatus for coding binary data representing sequential scan line signals indicative of portions of an image field, such apparatus comprising: data compression means for extracting from such data coordinates descriptive of each run of consecutive like-valued signals in a scan line, such coordinates being indicative of the width and location on such scan line of the runs; and processing means operative on the coordinates for representing the scanned image field invariably and entirely as a piecewise trapezoidal approximation, wherein (i) each of the two parallel sides of each trapezoid in the approximation is coincident with a scan line; (ii) the other two sides of each trapezoid are not necessarily parallel to one another; and (iii) the number of scan line lines between the two parallel sides of each trapezoid is determined directly from processing the coordinate data and is not necessarily an integral multiple of a fixed integer greater than one.

Claim 16

An apparatus for coding data representing sequential scan line signals defining light intensities of a graphic image, such apparatus comprising: data compression means for extracting coordinates of a run of consecutive like-valued signals along a scan line, such coordinates being indicative of the width and location on such scan line of the run; memory means for storing at a given time blocks of processed data, each block related to a single vector which has been previously scanned, and such data including for each vector, a coordinate pair descriptive of the width and location of the vector at an initial scan line on which the vector first occurs and a coordinate pair descriptive of the width and location of the vector at the scan line on which data pertaining to the vector was last obtained; slope calculation means, for calculating, on a recurring basis, the average rate of change per scan line of each of the coordinate pairs over the length of the vector; prediction means, using data from the slope calculation means, for predicting the coordinates descriptive of the width and location of a run of like-valued signals applicable to a vector on a current scan line; and connectivity means for determining whether the coordinates descriptive of a given run are predicted, within a prescribed measure of accuracy, by the prediction means using data from the slope calculation means applicable to a given vector in the memory means, and, in the event of a prediction within the prescribed measure of accuracy, for updating the data for the given vector in the memory means.

Claim 17

An apparatus for coding data representing sequential scan line signals defining light intensities of a graphic image, such apparatus comprising: data compression means for extracting coordinates of a run of consecutive like-valued signals along a scan line, such coordinates being indicative of the width and location on such scan line of the run; memory means for storing at a given time blocks of processed data, each block related to a single vector which has been previously scanned, and such data including for each vector, a coordinate pair descriptive of the width and location of the vector at an initial scan line on which the vector first occurs and a coordinate pair descriptive of the width and location of the vector at the scan line on which data pertaining to the vector was last obtained; slope calculation means, for calculating, on a recurring basis, the average rate of change per scan line of each of the coordinate pairs over the length of the vector; prediction means, using data from the slope calculation means, for predicting the coordinates descriptive of the width and location of a run of like-valued signals applicable to a vector on a current scan line; and connectivity means for determining whether the coordinates descriptive of a given run are predicted, within a prescribed measure of accuracy, by the prediction means using data from the slope calculation means applicable to a given vector in the memory means, and, in the event of a prediction within the prescribed measure of accuracy, for updating the data for the given vector in the memory means.

Claim 21

An apparatus, operative on input signal samples representative of light intensities of a two-dimensional image along a series of successive scan lines, for encoding graphic information therein by generation of a series of output records representative of significant graphic data, the apparatus comprising: (a) data compression means for extracting, from such input signal samples, two coordinates descriptive of each run of consecutive like-valued signals in a scan line, such coordinates being indicative of the width and location on such scan line of the run; (b) graphic element memory means, for storing a plurality or records of graphic elements, each graphic element constituting a run of substantially consecutive like-valued signals in each of a plurality of substantially consecutive scan lines, the run satisfying a continuity requirement that the coordinates indicative of the width and location of substantially each run, occurring in any scan after the first in which one of such runs occurs, be within a prescribed measure of accuracy of the coordinates predicted therefor on the basis of a specified algorithm utilizing coordinate data of a run from at least one preceding scan line; (c) predicting means, for predicting, in accordance with the algorithm, the coordinates indicative of the width and location of a run on each of a number M, M≧1, of consecutive scan lines attributable to a first graphic element, based on data for such graphic element stored in the graphic element memory means; (d) processing means, in communication with the predicting means and the data compression means, for determining whether a run has in fact occurred within M scan lines having coordinates that have been predicted by the prediction means within the prescribed measure of accuracy, and for updating the graphic element memory means in the event of a prediction of a run within the prescribed measure of accuracy, and in the event that there has not been a prediction within the prescribed measure of accuracy, for providing an output from the graphic element memory means of data pertaining to the first graphic element.

Claim 22

An apparatus, operative on input signal samples representative of light intensities of a two-dimensional image along a series of successive scan lines, for encoding graphic information therein by generation of a series of output records representative of significant graphic data, the apparatus comprising: (a) data compression means for extracting, from such input signal samples, two coordinates descriptive of each run of consecutive like-valued signals in a scan line, such coordinates being indicative of the width and location on such scan line of the run; (b) graphic element memory means, for storing a plurality or records of graphic elements, each graphic element constituting a run of substantially consecutive like-valued signals in each of a plurality of substantially consecutive scan lines, the run satisfying a continuity requirement that the coordinates indicative of the width and location of substantially each run, occurring in any scan after the first in which one of such runs occurs, be within a prescribed measure of accuracy of the coordinates predicted therefor on the basis of a specified algorithm utilizing coordinate data of a run from at least one preceding scan line; (c) predicting means, for predicting, in accordance with the algorithm, the coordinates indicative of the width and location of a run on each of a number M, M≧1, of consecutive scan lines attributable to a first graphic element, based on data for such graphic element stored in the graphic element memory means; (d) processing means, in communication with the predicting means and the data compression means, for determining whether a run has in fact occurred within M scan lines having coordinates that have been predicted by the prediction means within the prescribed measure of accuracy, and for updating the graphic element memory means in the event of a prediction of a run within the prescribed measure of accuracy, and in the event that there has not been a prediction within the prescribed measure of accuracy, for providing an output from the graphic element memory means of data pertaining to the first graphic element.