Method for automatic correction of character skew in the acquisition of a text original in the form of digital scan results

• US 4,723,297 A
• Filed: 08/19/1985
• Issued: 02/02/1988
• Est. Priority Date: 09/27/1984
• Status: Expired due to Fees

• Current Assignee: Siemens AG
• Original Assignee: Siemens AG
• Inventors: Postl, Wolfgang
• Primary Examiner(s): Boudreau, Leo H.
• Application Number:
  US06/766,594
• Time in Patent Office: 897 Days
• Field of Search: 382/43, 382/46, 250/557, 356/400, 356/138, 358/285, 340/727
• US Class Current: 382/289
• CPC Class Codes: G06V 30/10 Character recognition
• CPC Class Codes: G06V 30/1478 of characters or characters lines

Abstract

A method for automatic skewed position correction in acquisition of a text original in the form of digital scan results to be used for further processing. Before their further processing, the scan results are subjected to a skewed position identification in a first step and are subjected to an electronic rotation in a second step. The angle of the skewed position is identified according to a prescribed optimization method by generating a sequence of systematically selected search angles and directional criteria allocated to these search angles, and employing the angle for the electronic rotation. An interval nesting is preferably employed as the optimization method.

Claims

1. A method for automatic skewed position correction in acquisition of a text original in a form of digital scan values used for further processing, comprising the steps of:

before the further processing, subjecting the scan values to a skewed position identification and identifying an angle of the skewed position according to a prescribed optimization method by generating a sequence of systematically selected search angles α

_i and directional criteria K_i allocated to these search angles, and employing the identified angle for an electronic rotation of the scan values;

allocating the generation of the directional criterion K_i to a search angle α

_i such that a line-by-line search scan is simulated for every search angle α

_i in a direction which describes the search angle with a preferred direction and corresponds to a rotation by this search angle;

generating and storing at least an approximate value of a sum of scan values along the respective search line for each of the search lines thereby scanned;

before the respective storage of a succeeding one of these sums and every following sum of these sums, storing and adding an even, non-decreasing function of a squared difference between the succeeding one sum and the most recently stored sum to a content of a register which was set to a value 0 before a beginning of the search scan;

using a content of the register after conclusion of the search scan as a desired value of the directional criterion K; and

generating the sum by identifying sequences of black lengths in a form of digital data words for every search line with assistance of a run length detector, and supplying these data words to an adder.

2. A method according to claim 1 including the step of employing an interval nesting as an optimization method.

3. A method according to claim 1 including the steps of allocating the generation of the directional criterion K_i to a search angle α

_i such that a line-by-line search scan is simulated for every search angle α

_i in a direction which describes the search angle with a preferred direction and corresponds to a shearing based on this search angle;

generating and storing at least an approximate value of a sum of the scan values along the respective search line for each of the search lines thereby scanned;

before respective storage of a succeeding one of these sums and every following sum of these sums, storing and adding an even, non-decreasing function of a squared difference between the one succeeding sum and the most recently stored sum to a content of a register which was set to a value 0 before a beginning of the search scan; and

using a content of the register after conclusion of the search scan as a desired value of the directional criterion K_i.

4. A method according to claim 1 including the steps of providing the identification of the directional criterion K_i allocated to a search angle α

_i by determining coefficients of the scan values, forming complex Fourier coefficients therefrom, generating coefficients of a Fourier power spectrum from the complex Fourier coefficients, and integrating the coefficients of the Fourier power spectrum for every search angle α

_i within a search sweep which encloses the angle α

_i, the search sweep being defined by limit angles α

_min and α

_max.

5. A method according to claim 4 including the step of limiting the step of integrating to one or more sub-regions of the search sweep.

6. A method according to claim 4 including the step of acquiring the coefficients of the Fourier power spectrum before determination of a first search angle by identifying the Fourier coefficients by a two-dimensional, fast Fourier transformation, and storing squares of the coefficients.

7. A method according to claim 1 including the step of identifying scan values to be summed by interpolation.

8. A method according to claim 1 including the step of replacing scan values to be summed by values which are based on rounded coordinates.

9. A method according to claim 1 including the step of employing horizontal as a preferred direction for analysis.

10. A method according to claim 1 including the step of employing vertical as a preferred direction for analysis.

11. A method according to claim 1 including the step of employing both horizontal as well as vertical as a preferred direction for analysis, whereby the directional criterion allocated to a specific search angle is acquired from a combination of the directional criteria identified for the respective, preferred directions.

12. An apparatus, comprising:

an image repetition memory connected for readout with a picture element clock and having a first and a second address input and a parallel-to-serial converter connected to an output;

a monitor connected to an output of the parallel-to-serial converter;

the output of the image repetition memory also connecting to a point integrator means for forming a sum based on binary signals which are present at an input thereof, this sum being output to an input of a word sum memory;

a point divider means connected to the picture element clock for deriving a word clock which is connected to an X-word counting register;

an output of the X-word counting register being connected to a first address input of the picture repetition memory;

the word clock also being connected to an oblique scan register means designed as an adder, and in a normal picture output mode, a significant part of a content of the scan register means being connected via a change-over S to a Y-register for reading thereof;

the Y-register being incremented with a line clock output from a connected word divider connected to the word clock;

means for incrementing during a search scan a content of the oblique scan register means by the content of a Y-increment register with every clock pulse output by the point divider means;

an input of said Y-increment register being connected to an output of a scan controller to whose first input a picture clock derived by a line divider from the line clock is supplied and whose second input is connected to an output of a sum register whose input is connected to a squaring unit means;

said squaring unit means forming a square of a difference of contents of the word sum memory and of a further memory and adds it to a content of the sum register with the line clock;

means for transferring after every picture line or square formation a content of the word sum memory into the further memory;

means for subsequently resetting the X-word counting register as well as the word sum memory to a prescribed initial reading; and

means for erasing the sum register after a picture pass.