Skew Detector for Digital Image Processing System

Optical character recognition systems and image processing systems generally are well-known in the art. One problem with such systems is that the printed material in a document being read in the system may be skewed at an angle with respect to the optical character recognition system orientation. This problem is called skew. It is not cost effective to rotate the document in the system scanner to eliminate the skew. The preferred method is to process the video data generated from viewing the document in such a manner as to remove the skew prior to image processing. One such data processing method is disclosed in U.S. Pat. No. 3,967,243, in which the skew is removed by normalizing vertical and horizontal second moments computed from the video data. This sort of computation is fairly sophisticated and potentially burdensome.

A simpler method is to organize the lines (rows) of video data generated by the document reader into successive columns of predetermined positions. In this method, disclosed in U.S. Pat. No. 4,558,461, whenever there is a sufficient number (e.g., one) of black pixels in a particular column in a given line of data, that entire column in that line (only) is then transformed to all black pixels. As a result, if the video data is skewed, a smeared staircase pattern appears. The skew angle may be easily computed from the shape of the staircase.

This latter method suffers from the disadvantage that the start position of each step in the staircase is fixed by the predetermined positions of the columns into which the rows of video data are organized and then smeared. This introduces a type of error which heuristically may be thought of as "quantization" error. More specifically, the edge of each step in the staircase pattern coincides with a boundary of one of the columns, the location of which is predetermined without regard to the contents of the video data. The accuracy of this process is limited by the minimum width of the columns into which the rows of video data may be organized. This is analogous to the quantization error typically encountered in analog-to-digital conversion, in which the accuracy is limited by the minimum step size of the digital quantization.

The problem is how to determine and subsequently remove skew in video data representing printed information before the data is fed to an image processing system without complex computations (such as the computation of second moments as in U.S. Pat. No. 3,967,243) and without introducing the types of errors encountered in the simpler processing techniques, such as the "quantization" error introduced by the simple technique of U.S. Pat. No. 4,558,461.

Video data representing the image of a printed document is de-skewed before being processed by an optical character recognition system. The skew detection and subsequent de-skewing is performed in accordance with the process of the invention by first organizing each row of the succession of rows of video data into run lengths of white ("off") pixels. A run length is defined by a succession of adjacent pixels, all of which are "off" or white. All of the white run lengths in each row of video data are compared against a threshold white run length. The pixels within only those white run lengths shorter than the threshold white run length are transformed to black pixels.

The next step is to organize the rows of video data anew, this time into run lengths of black pixels. For each row of video data, the longest black run length is selected, and its start location in the row is noted. Significantly, the start location of the selected black run length is determined by the contents of the image represented by the video data, and not by any arbitrary predetermination as in U.S. Pat. No. 4,558,461 discussed above. This guards against "quantization" error, as will be discussed below. The offset distances between successive run length start locations are also noted.

If the printed image represented by the video data is skewed about an angle, the pattern of selected black run lengths will correspond to a staircase pattern. The offset distance between each pair of adjacent steps in the staircase pattern provides a measure of the skew angle. (The angle is the tangent of the ratio of the step height to the offset distance.) Depending upon the number of steps in the staircase pattern, there is a statistical ensemble of offset distances (and corresponding individual skew angles) characterized by a standard deviation.

One feature of the invention is to compute the "mean" skew angle from the ensemble of offset distances (or individual skew angles) in the staircase pattern. In accordance with this feature of the invention, the number of successive offset distances or individual skew angles need only be sufficient to minimize the standard deviation of the ensemble below a threshold corresponding to a desired statistical confidence level.

Accordingly, before the average skew angle is computed from the ensemble of offset distances or individual skew angles, the following steps are taken to filter out unreliable data and to ensure that the remaining data corresponds to a true staircase pattern of black run lengths:

Offset distances between successive run lengths which fall outside of a specified range are discarded. Then, only continuous successions of run lengths are considered, in which none of the individual "steps" or run lengths in the pattern have been discarded for being out of range or for other reasons.

Next, the largest continuous succession of run lengths in the frame is inspected for reliability as follows: First, the sum of all of the differences between successive run lengths start positions is determined. This sum should either be a large negative number or a large positive number (depending upon the direction of the skew) whose absolute value exceeds a threshold magnitude. If this sum of differences does not exceed the threshold magnitude, this indicates that there are not enough samples and more video data is required to provide a reliable measure of the skew angle (or else the skew angle is negligible). Otherwise, the ensemble of offset distances (or individual skew angles) is inspected for reliability by computing its standard deviation. If the standard deviation is not below a threshold value corresponding to a selected statistical confidence level, then, again, more video data is required to provide a reliable computation of the skew angle. Otherwise, the data present in deemed sufficient to provide a reliable measure of the skew angle.

The skew angle is computed from the mean of the succession of skew angles (or offset distances) remaining after all of the foregoing filtering steps.

The foregoing processing requires no computation of geometric moments or second moments of the video data (thus minimizing the amount of memory required, a significant advantage). Furthermore, the process of the invention minimizes or virtually eliminates quantization error in setting up a smeared staircase pattern from the video data. This is because the starting location of each step in the smeared staircase pattern is virtually exclusively a function of the content of the video data representing the printed image, and is not affected by an artifact of the data processing such as the type of "quantization" error discussed above. In fact, in the preferred embodiment of the invention, the accuracy of the individual start locations of the steps or individual black run lengths in the staircase pattern is limited only by the resolution or pixel size of the video data. This represents a significant advance in the art and overcomes the trade-off between accuracy or reliability vs. process simplicity.

The invention may be understood by reference to the accompanying drawings of which:

FIGS. 1a and 1b illustrate the run-length processing of the present invention;

FIG. 2 illustrates the system of the invention;

FIGS. 3a and 3b illustrate examplary results of the run length processing of the invention.

Referring to FIG. 1a, a printed image represented by successive horizontal lines of video data may correspond to a straight line 10 having a thickness h subtended at a skew angle .phi. across the printed document or frame of video data. A reader scans the document to generate successive rows of video data. FIG. 1 illustrates the video data for rows J-2, j-1, j, j+1, J+2 (it being understood j begins at zero and ends at n, wherein n is the number of rows in the entire video frame representing the scanned document).

Due to uncertainties in the conversion of the printed image to video data, or due to imperfections in the original printed image itself from which the video data was created, the straight line 10 may not be represented by a perfectly contiguous area of black pixels (corresponding to the shaded regions in FIG. 1a). In fact, various "white" regions 12 may exist, as illustrated in FIG. 1a. These white regions are attributable to noise or other imperfections, but are not truly representative of the straight line 10, particularly if each of the regions 12 is of a width less than some threshold w.

In order to smear the image, the invention organizes each horizontal line of video data illustrated in FIG. 1a into white run lengths. Each run length corresponds to one of the white areas 12 in FIG. 1a. The white pixels comprising each of those white run lengths 12 whose length is less than the threshold width w are all transformed to black pixels, in accordance with the process of the invention. This smearing process therefore "fills in" the white or blank areas 12 within the horizontal line 10 to produce the "smeared" staircase pattern of FIG. 1b. The next step of the invention is to organize each horizontal line of the smeared video data of FIG. 1b into black run lengths. The longest black run length in each horizontal line is then selected. In the case of FIG. 1b, the longest run length in each horizontal line corresponds to one of the individual steps 16 in the staircase pattern of black (shaded) pixels. The start location x.sub.j of the j.sup.th step, for example, is noted.

The process of the invention now ensures that the ensemble of run length start locations x.sub.j obey the following reliability criteria:

1. The offset distance x.sub.j -x.sub.j-1 between each pair of adjacent run lengths falls within an acceptable band.

2. There is a continuous succession of run length start locations, or, equivalently, there is no missing step in the staircase pattern of FIG. 1b.

3. The absolute value of the sum of all of the offset distances between adjacent steps in the staircase pattern of FIG. 1b exceeds a threshold magnitude.

4. The standard deviation of the ensemble of offset distances is less than a threshold value corresponding to a desired (previously selected) statistical confidence level.

In the presently preferred embodiment of the invention, the standard deviation determination of criteria 4 above is replaced by the much simpler process of monitoring the differences between successive mean values of the offset distances. (As each new offset distance is added to the ensemble of individual offset distances, a new mean value must be computed.) Once the difference between successive mean values falls below a predetermined threshold (signifying a stabilizing convergence of the mean values), the ensemble of individual differences between successive offset distances is sufficiently large to enable computation of the skew angle from the mean offset distance.

Alternatively, instead of collecting an ensemble of offset distances and computing their mean value, an individual skew angle may be computed for each offset distance to generate an ensemble of skew angles whose mean value is then computed and monitored.

In the example of FIG. 1b, the foregoing criteria are all met, and the offset angle .theta. is computed by first computing the individual offset angles .theta..sub.j defined at each step of the staircase of FIG. 1a. Then, the average of all .theta..sub.j 's is taken, and it is this average which is output as the skew angle. (Alternatively, the skew angle is determined from the average of all offset distances (x.sub.j -x.sub.j-1).)

The system of the invention is illustrated in FIG. 2. Incoming video data is temporarily stored in a buffer memory 90 before being sent to an image rotation device 92. The image rotation device 92 is of the type well-known in the art, and, in response to a known skew angle, rotates the image represented by the video data so as to remove the objectionable skew present in the original image. The problem is to detect and measure the precise skew angle and furnish this information to the image rotation device 92.

For this purpose, the incoming video data stored in the buffer memory 90 is simultaneously admitted through a gate 94 to a skew detector 100. The skew detector includes a run length processor 104, a run length counter 106, a run position counter, a memory 108, a run position counter 110 and a run position processor 112.

The run length processor 104 monitors white run lengths in each line of the incoming video data and transforms all white pixels in any white run length below a predetermined threshold length to black pixels. This smears the data. Next, the run length processor 104 monitors black run lengths in each line of incoming video data and furnishes their locations to the run length counter 106. The run length counter 106 determines the starting pixel position of the longest black run length in each video line. All starting positions thus determined are stored in the memory 108. Until the memory 108 stores a predetermined number of such start positions, it continues to direct the gate 90 via a control line 109 to admit additional lines of incoming video data.

The run position counter 110 accumulates the differences (both positive and negative) between successive run length starting positions stored in the memory 108. The run position counter continues to direct the gate 90 via the control line 109 to admit successive lines of the incoming video data until the total accumulated difference exceeds a predetermined threshold, indicating that there is enough data to detect a skew angle.

The run position processor 112 monitors the standard deviation (or an equivalent parameter) of the ensemble of individual differences between successive run start positions received from the run position counter 110. Until the standard deviation (or equivalent parameter) indicates that a predetermined statistical level of confidence has been reached in the ensemble of individual differences, the run position processor 112 continues to direct the gate 90 via the control line 109 to admit successive lines of the incoming video data. As soon as the predetermined level of confidence has been reached, the run position processor 112 computes the mean value of the ensemble of individual differences between successive black run length start locations. The run position processor 112 then determines the skew angle by computing the arc-tangent of the ratio of the distance between adjacent horizontal lines in the incoming video data to the mean value of the ensemble of individual start locations. The skew angle thus determined is transmitted along with an indication of the skew direction (+ or -) to the image rotation device 92. The system of FIG. 2 performs this process at least once in each frame of incoming video data (assuming that all of the video data in a given frame is characterized by the same skew angle). It may perform the process more or less often, depending upon the user's requirements or the nature of the incoming video data.

Preferably, the run position processor 112 determines whether the ensemble of differences furnished by the run position counter 110 meet the criteria 1-4 given above. If the criteria are not met, the processor 112 causes the gate 90 to admit additional video data so that additional black run length start locations may be computed. Once the criteria 1-4 have been met, the black run length start locations are processed by a skew computing processor 28 so as to compute the average skew angle from the individual start locations, or start location differences or individual skew angles .theta..sub.j, as described above.

An actual example of the staircase pattern achieved using the run length processing of the invention is illustrated by comparing the input image of FIG. 3a with the processed image of FIG. 3b (which was computed from the input image of FIG. 3a in accordance with the foregoing described process). Note that the slanted printing, "for administrative use only" in FIG. 3a results in a spurious staircase pattern in the corresponding location of FIG. 3b. However, since each of the black run lengths resulting therefrom are not the longest black run lengths in each horizontal video line, this spurious staircase pattern is ignored, in accordance with the invention.

In the preferred embodiment of the invention, the algorithm executed by the system of FIG. 2 is as follows:

1. Load the next block of n lines of video data.

2. Do for j=1 through n:

3. Receive data of video line j.

4. Organize into white run lengths.

5. Transform pixels in white run lengths of length less than w to black pixels.

6. Organize video data lines into black run lengths.

7. Select the longest black run length r.sub.j in line j.

8. Determine the start location x.sub.j of r.sub.j.

9. Determine the number D.sub.j of black pixels in line j.

10. Determine x.sub.j -x.sub.j-1 and .theta..sub.j =tangent (y.sub.h /(x.sub.j -x.sub.j-1)).

11. If j<n, then j=j+1 and go to 3.

otherwise:

12. Do for j=1 through n:

13. If x.sub.j -x.sub.j-1 is greater than x.sub.max or less than x.sub.min discard all data from video line j.

14. If D.sub.j <D.sub.min, disregard all data corresponding to video data line j.

15. If j<n, j=j+1 and go to 13.

Otherwise:

16. Do for j=1 through n:

17. If r.sub.j-1 and r.sub.j+1 have been discarded in any previous step, discard all video data corresponding to video line j.

18. If j<n, j=j+1 and go to 17.

Otherwise:

19. For all j's not discarded so far, compute the following: ##EQU1## and .sigma.(.theta..sub.j)=standard deviation of all .theta..sub.j 's. 20. If d<d.sub.t or if .sigma.(.theta..sub.j)>.sigma..sub.t, go to 1.

Otherwise:

21. Count the number m of .theta..sub.j not discarded thus far.

22. Compute ##EQU2## 23. If .theta. is greater than .theta..sub.max or is less than .theta..sub.min stop. Flag error.

Otherwise:

24. Output .theta. and the polarity (+ or -) of d.

In the foregoing skew correction algorithm, the following limits on each of the quantities specified therein are selected as follows:

In step 13, the offset distance x.sub.j -x.sub.j-1 had to be greater than x.sub.min .multidot.x.sub.min corresponds to the minimum skew angle which the system can recognize. Ideally, this is only limited by the minimum pixel resolution size of the video system, and may be determined readily by the skilled worker. Furthermore, the offset distance x.sub.j -x.sub.j-1 had to be smaller than x.sub.max .multidot.x.sub.max corresponds to the maximum skew angle which the optical character recognition system can handle and correct. This is determined in accordance with the optical character recognition system requirements. In one example, the minimum angle x.sub.min is 0.08.degree. and the maximum angle x.sub.max is 4.0.degree..

Step 14 of the invention required that the number D.sub.j of black pixels in a given horizontal video line (j) had to be greater than a threshold number D.sub.min. This threshold number may be selected by the skilled worker in such a manner as to ignore a "spurious" staircase pattern such as that illustrated in FIGS. 3a and 3b corresponding to the slanted label "for administrative use only" in the otherwise unskewed printed image of FIG. 3a.

Step 20 required that the absolute value of the sum d of the offset distances be greater than a threshold magnitude d.sub.t. This threshold magnitude may be selected to be the number m of individual offset distances comprising the sum d multiplied by the arc cotangent of the minimum correctable angle (e.g., 0.08.degree.). The skilled worker may select any other suitable criteria for d.sub.t.

Finally, the standard deviation .sigma.(.theta..sub.j) of the ensemble of individual skew angles .theta..sub.j was required in step 20 to be less than a threshold standard deviation .sigma..sub.t. .sigma..sub.t is computed from the number m of samples in the ensemble and a statistical confidence level and probability value selected by the user. Assuming that the ensemble of individual skew angles .theta..sub.j obey Gaussian statistics, .sigma..sub.t is easily determined in accordance with well-known principles or by simply looking up in a table which correlates probability values, confidence levels and number of samples.

Step 23 required that the average skew angle .theta. be no greater than .theta..sub.max and no less than .theta..sub.min. Again, .theta..sub.max and .theta..sub.min may, in one example, be selected to correspond to 0.08.degree. and 4.0.degree., respectively.

The skew correction algorithm of steps 1 through 23 above is just one of many possible examples for implementing the invention. It may be readily modified. For example, the roles of the white pixels and black pixels may be reversed in the first two steps of the run-length processing, so that a "white" staircase is formed, rather than the "black" staircase of FIG. 1b. Accordingly, it is understood that, while the invention has been described in detail with particular reference to preferred embodiments thereof, variations and modifications may be made without departing from the spirit and scope of the invention.