Character pattern normalization method and apparatus for optical character recognition system

• US 3,967,243 A
• Filed: 07/05/1974
• Issued: 06/29/1976
• Est. Priority Date: 07/09/1973
• Status: Expired due to Term

• Current Assignee: Kabushiki Kaisha Ricoh
• Original Assignee: Kabushiki Kaisha Ricoh
• Inventors: Kawa, Ryuichi
• Primary Examiner(s): Boudreau, Leo H.
• Application Number:
  US05/486,246
• Time in Patent Office: 725 Days
• Field of Search: 340/146.3 H, 340/146.3 AE, 340/146.3 MA, 340/172.5, 340/146.3 AH, 340/146.3 R
• US Class Current: 382/290
• CPC Class Codes: D01B 7/04 Reeling silk
• CPC Class Codes: G06V 10/10 Image acquisition document image scanning and transmission H04N1/00; control of digital cameras H04N23/60
• CPC Class Codes: G06V 10/20 Image preprocessing
• CPC Class Codes: G06V 10/32 Normalisation of the pattern dimensions
• CPC Class Codes: G06V 30/10 Character recognition
• CPC Class Codes: G06V 30/1478 of characters or characters lines
• CPC Class Codes: G06V 30/166 Normalisation of pattern dimensions

Abstract

The character pattern from the scanner is stored in its original form in an auxiliary memory and in compressed form in a main memory. The slant and the horizontal and vertical second-order moments of the character pattern are sensed in the main memory, and normalized as the character pattern is shifted from the auxiliary memory to the main memory.

Claims

1. A method of normalizing a character pattern in the form of electrical signals constituting a quantized representation of a character, comprising the steps of:

a. storing the character pattern in both a main memory and an auxiliary memory;

b. sensing the value of at least one spatial parameter of the character pattern in the main memory; and

c. normalizing the at least one spatial parameter while transferring the character pattern from the auxiliary memory to the main memory in accordance with the sensed value;

the at least one spatial parameter including the slant of the character pattern, said main and auxiliary memories comprising rectangular arrays of memory elements corresponding to respective points of the character pattern;

step (c) comprising, for each respective column of memory elements of the main and auxiliary memories;

gating electrical signals from memory elements of the auxiliary memory to memory elements of the main memory, said memory elements of the main memory to which the electrical signals are gated being said respective column of memory elements, said memory elements of said auxiliary memory from which the electrical signals are gated being spaced to the left of said respective column of memory elements to normalize leftward slant and being spaced to the right of said respective column of memory elements to normalize rightward slant, a spacing of said memory elements of said auxiliary memory from which the electrical signals are gated progressively increasing from a bottom of said auxiliary memory relative to a top of said auxiliary memory.

2. A method of normalizing a character pattern in the form of electrical signals constituting a quantized representation of a character, comprising the steps of:

a. storing the character pattern in both a main memory and an auxiliary memory;

b. sensing the value of at least one spatial parameter of the character pattern in the main memory; and

c. normalizing the at least one spatial parameter while transferring the character pattern from the auxiliary memory to the main memory in accordance with the sensed value;

said main and auxiliary memories comprising rectangular arrays of memory elements corresponding to respective points of the character pattern and being divided into upper portions and lower portions;

step (c) comprising;

gating an electrical signal from a first memory element of the upper portion of the auxiliary memory to a second memory element of the upper portion of the main memory, the first memory element being spaced in a first direction from a third memory element of the auxiliary memory corresponding to the second memory element of the main memory; and

gating an electrical signal from a fourth memory element of the lower portion of the auxiliary memory to a fifth memory element of the lower portion of the main memory, the fourth memroy element being spaced in a second direction from a sixth memory element of auxiliary memory corresponding to the fifth memory element of the main memory and the second direction being opposite to the first direction.

3. The method according to claim 2, in which the at least one spatial parameter of the character pattern includes the vertical size of the character pattern, the first direction being from the lower portions toward the upper portions of the main and auxiliary memories to increase the vertical size and from the upper portions toward the lower portions of the main and auxiliary memories to decrease the vertical size;

the second direction being from the lower portions toward the upper portions to decrease the vertical size and from the upper portions toward the lower portions to increase the vertical size.

4. The method according to claim 2, in which the at least one spatial parameter includes the slant of the character pattern, the first direction being from left to right in the main and auxiliary memories to normalize leftward slant and from right to left in the main and auxiliary memories to normalize rightward slant and the second direction being from left to right to normalize rightward slant and from right to left to normalize rightward slant.

5. The method according to claim 2, in which the main memory has a capacity smaller than a capacity of the auxiliary memory, the character pattern being stored in the main memory in a compressed form relative to a form in which the character pattern is stored in the auxiliary memory in step (a), the character pattern being compressed in step (c).

6. The method according to claim 2, further comprising the step of:

d. uniformly thickening the line thickness of the character pattern before step (a).

7. The method according to claim 2, in which the at least one spatial parameter includes the horizontal size of the character pattern, and in which step (c) includes applying first and second shift pulse trains to rows of the auxiliary memory and the main memory respectively over a predetermined time period in such a manner that a frequency of the second pulse train is greater than a frequency of the first pulse train to increase the horizontal size of the character pattern, and a frequency of the second pulse train is smaller than a frequency of the first pulse train to decrease the horizontal size of the character pattern.

8. In a system having a two-dimensional memory consisting of shift registers to store a quantized character pattern in the form of electrical signals, each shift register being shiftable independently in one dimension, apparatus to change the slant of the character pattern within the memory, said apparatus comprising:

a slant shift register having a number of stages equal to the number of shift registers of the memory;

a plurality of AND gates in a number equal to the number of shift registers of the memory, the outputs of said AND gates being connected to the shift inputs of the shift registers of the main memory respectively, the outputs of the stages of said slant shift register being sequentially connected to first inputs of said AND gates respectively; and

a shift pulse generator having a first shift pulse output connected to the shift input of said slant shift register and a second shift pulse output connected to second inputs of all of said AND gates;

said shift pulse generator being arranged so that with the set input of the first stage of said slant shift register maintained logically positive, in response to first shift pulses from the first shift pulse output of said shift pulse generator, the stages of said slant shift register will progressively become logically positive, and in response to second shift pulses from the second shift pulse output of said shift pulse generator, shift registers of the memory having shift inputs connected through said AND gates to the outputs of stages of said slant shift register which are logically positive will shift so that the slant of the character pattern is changed, the degree of change being dependent on the ratio of the frequency of said first shift pulses to the frequency of said second shift pulses.

9. In an optical character recognition system in which a document is scanned by scanning means to produce a character pattern in the form of electrical signals constituting a quantized representation of a character printed on the document, a character pattern normalization system comprising:

a main memory in which the character pattern is stored from the scanning means;

an auxiliary memory in which the character pattern is also stored from the scanning means;

sensing means arranged to sense the value of at least one spatial parameter of the character pattern in said main memory and generate at least one electrical normalization signal in response thereto;

normalization means operatively connected to said main memory and said auxiliary memory and responsive to said at least one normalization signal, said normalization means being operative to shift the character pattern from said auxiliary memory to said main memory and normalize said at least one spatial parameter in accordance with said at least one normalization signal as the character pattern is being shifted; and

thickening means connected between the scanning means and said main and auxiliary memories to thicken the line thickness of the character pattern, said thickening means comprising;

a first shift register having a capacity equal to a number of rows of said auxiliary memory;

a second shift register having a capacity equal to the number of rows of said auxiliary memory and having its input connected to the output of said first shift register, the scanning means being operative to store the electrical signals resulting from two successive main scans of the document in said second and first shift registers respectively; and

a plurality of OR gates having inputs connected to said first and second shift registers so that each OR gate has one input connected to a first selected point in said second shift register and another input connected to a second selected point in said first shift register corresponding to a point in the character pattern diagonally adjacent to said first selected point, the outputs of said OR gates being connected to the inputs of corresponding rows of said main and auxiliary memories.

10. In an optical character recognition system in which a document is scanned by scanning means to produce a character pattern in the form of electrical signals constituting a quantized representation of a character printed on the document, a character pattern normalization system comprising:

a main memory in which the character pattern is stored from the scanning means;

an auxiliary memory in which the character pattern is also stored from the scanning means;

sensing means arranged to sense the value of at least one spatial parameter of the character pattern in said main memory and generate at least one electrical normalization signal in response thereto; and

normalization means operatively connected to said main memory and said auxiliary memory and responsive to said at least one normalization signal, said normalization means being operative to shift the character pattern from said auxiliary memory to said main memory and normalize said at least one spatial parameter in accordance with said at least one normalization signal as the character pattern is being shifted;

and at least one spatial parameter including the slant of the character pattern;

said sensing means comprising;

a resistor weighting network;

an operational amplifier having an input connected to a plurality of points in said main memory through said resistor weighting network, said operational amplifier being arranged to produce at its output an electrical slant signal corresponding to a weighted function of the value of the slant of the character pattern; and

a quantizer having its input connected to the output of said operational amplifier and a plurality of outputs corresponding to the sub-ranges of the range of said electrical slant signal, the output of said quantizer energized in accordance with the sensed slant of the character pattern constituting one of said at least one normalization signals.

11. A system according to claim 10, in which said quantizer has three outputs corresponding respectively to zero slant, leftward slant and rightward slant, and in which said normalization means includes a slant normalization unit which comprises:

a plurality of OR gates in a number equal to a number of rows of said auxiliary memory, the outputs of said OR gates constituting the output of said slant normalization unit, each OR gate being associated with a respective row of said auxiliary memory;

a plurality of AND gates in a number equal to 3 times the number of said OR gates and being arranged in groups of 3, the outputs of each group of 3 AND gates being connected to the inputs of a respective OR gate;

first inputs of each group of 3 AND gates being connected to points in the respective row of said auxiliary memory so that for the upper portion of said auxiliary memory, the first input of a first AND gate of each group is connected to a selected point in the respective row, the first input of a second AND gate of each group is connected to a point to the left of the selected point in the respective row and the first input of a third AND gate of each group is connected to a point to the right of the selected point in the respective row;

second inputs of each group of 3 AND gates being connected to said quantizer so that the second input of the first AND gate of each group is connected to the zero slant output of said quantizer, the second input of the second AND gate of each group is connected to the leftward slant output of the quantizer and the second input of the third AND gate of each group is connected to the rightward slant output of said quantizer; and

for the lower portion of said auxiliary memory;

the first input of the first AND gate of each group is connected to a selected point in the respective row, the first input of the second AND gate of each group is connected to a point to the right of the selected point in the respective row and the first input of the third AND gate of each group is connected to a point to the left of the selected point in the respective row;

second inputs of each group of 3 AND gates being connected to said quantizer so that the second input of the first AND gate of each group is connected to the zero slant output of said quantizer, the second input of the second AND gate of each group is connected to the leftward slant output of said quantizer and the second input of the third AND gate of each group is connected to the rightward slant output of said quantizer.

12. In an optical character recognition system in which a document is scanned by scanning means to produce a character pattern in the form of electrical signals constituting a quantized representation of a character printed on the document, a character pattern normalization system comprising:

a main memory in which the character pattern is stored from the scanning means;

an auxiliary memory in which the character pattern is also stored from the scanning means;

sensing means arranged to sense the value of at least one spatial parameter of the character pattern in said main memory and generate at least one electrical normalization signal in response thereto; and

normalization means operatively connected to said main memory and responsive to said at least one normalization signal, said normalization means being operative to shift the character pattern from said auxiliary memory to said main memory and normalize said at least one spatial parameter in accordance with said at least one normalization signal as the character pattern is being shifted;

said at least one spatial parameter including at least one of the vertical and horizontal second-order moments of the character pattern about horizontal and vertical axes respectively intersecting at the centroid of the character pattern, said sensing means having three outputs corresponding to a normal vertical second-order moment of the character pattern, an excessive vertical second-order moment of the character pattern and an insufficient vertical second-order moment of the character pattern respectively, one of said outputs being energized in accordance with the sensed vertical second-order moment of the character pattern to constitute one of said at least one normalization signals;

said normalization means including a vertical normalization unit which comprises;

a plurality of OR gates in a number equal to a number of rows of said main memory, the outputs of said OR gates constituting the output of said vertical normalization unit and being connected respectively to the inputs of the rows of said main memory, said OR gates being connected to a selected column of said auxiliary memory;

a plurality of AND gates in a number equal to 3 times the number of said OR gates and being arranged in groups of 3, the outputs of each group of 3 AND gates being connected to the inputs of a respective OR gate;

first inputs of each group of 3 AND gates being connected to rows in the selected column of said auxiliary memory so that for the upper portion of said auxiliary memory the first input of a first AND gate of each group is connected to a selected row of said auxiliary memory corresponding to the equivalent row in said main memory to which the OR gate associated with the group is connected, the first input of a second AND gate of each group is connected to a row above the respective selected row and the first input of a third AND gate of each group is connected to a row below the respective selected row;

second inputs of each group of 3 AND gates being connected to the outputs of said sensing means so that the second input of the first AND gate of each group is connected to the normal vertical moment output, the second input of each second AND gate of each group is connected to the excessive vertical moment output and the second input of the third AND gate of each group is connected to the insufficient vertical moment output; and

for the lower portion of said auxiliary memory;

the first input of the first AND gate of each group is connected to a selected row of said auxiliary memory corresponding to the equivalent row in said main memory to which the OR gate associated with the group is connected, the first input of the second AND gate of each group is connected to a row below the respective selected row and the first input of the third AND gate of each group is connected to a row above the respective selected row; and

second inputs of each group of 3 AND gates being connected to the outputs of said sensing means so that the second input of the first AND gate of each group is connected to the normal vertical moment output, the second input of each second AND gate of each group is connected to the excessive vertical moment output and the second input of the third AND gate of each group is connected to the insufficient vertical moment output.

13. In an optical character recognition system in which a document is scanned by scanning means to produce a character pattern in the form of electrical signals constituting a quantized representation of a character printed on the document, a character pattern normalization system comprising:

a main memory in which the character pattern is stored from the scanning means;

an auxiliary memory in which the character pattern is also stored from the scanning means;

sensing means arranged to sense the value of at least one spatial parameter of the character pattern in said main memory and generate at least one electrical normalization signal in response thereto; and

normalization means operatively connected to said main memory and said auxiliary memory and responsive to said at least one normalization signal, said normalization means being operative to shift the character pattern from said auxiliary memory to said main memory and normalize said at least one spatial parameter in accordance with said at least one normalization signal as the character pattern is being shifted;

said main memory having a capacity smaller than a capacity of said auxiliary memory and the character pattern being stored in said main memory in a compressed form relative to a form in which the character pattern is stored in said auxiliary memory, said normalization means being further operative to compress the character pattern as the character pattern is being shifted from said auxiliary memory to said main memory;

said at least one spatial parameter including the horizontal second-order moment of the character pattern about a vertical axis passing through the centroid of the character pattern, and in which said sensing means has three outputs corresponding to a normal horizontal second-order moment of the character pattern, an excessive horizontal second-order moment and an insufficient horizontal moment respectively, one of said outputs being energized in accordance with the sensed horizontal second-order moment of the character pattern to constitute one of said at least one normalization signals,

said normalization means including a horizontal normalization unit which comprises;

a shift register having a shift input responsive to shift pulses generated by said normalization means for said auxiliary memory;

an AND gate having an output connected to the shift input of said main memory, one input responsive to said auxiliary memory shift pulses and another input connected to the serial output of said shift register; and

an encoder having inputs connected to the outputs of said sensing means and outputs connected to set inputs of the stages of said shift register, said encoder being arranged to set predetermined stages of said shift register in accordance with the energized output of said sensing means so that in response to the auxiliary memory shift pulses, the output pulse frequency of said shift register and thereby said horizontal normalizating unit will be equal to, less or greater respectively than the frequency of the auxiliary memory shift pulses multiplied by the ratio of the number of rows of said main memory to the number of rows of said auxiliary memory when the normal, excessive and insufficient horizontal moment output respectively of said sensing means is energized in response to the sensed horizontal second-order moment of the character pattern.

14. In an optical character recognition system in which a document is scanned by scanning means to produce a character pattern in the form of electrical signals constituting a quantized representation of a character printed on the document, a character pattern normalization system comprising:

a main memory in which the character pattern is stored from the scanning means;

an auxiliary memory in which the character pattern is also stored from the scanning means;

sensing means arranged to sense the value of at least one spatial parameter of the character pattern in said main memory and generate at least one electrical normalization signal in response thereto; and

normalization means operatively connected to said main memory and said auxiliary memory and responsive to said at least one normalization means being operative to shift the character pattern from said auxiliary memory to said main memory and normalize said at least one spatial parameter in accordance with said at least one normalization signal as the character pattern is being shifted;

said at least one spatial parameter including at least one of the vertical and horizontal second-order moments of the character pattern about horizontal and vertical axes respectively intersecting at the centroid of the character pattern;

said normalization means comprising a vertical normalization unit which comprises gate means operative to normalize the vertical second-order moment of the character pattern by gating an electrical signal from a memory element of said auxiliary memory representing a point above a first selected point in an upper portion of the character pattern to a memory element of said main memory representing the first selected point and gating an electrical signal from a memory element of said auxiliary memory representing a point in the character pattern below a second selected point in a lower portion of the character pattern to a memory element of said main memory representing the second selected point to decrease the vertical second-order moment; and

said gate means being operative to gate an electrical signal from a memory element of said auxiliary memory representing a point below the first selected point in the upper portion of the character pattern to the memory element of the main memory representing the first selected point and gate an electrical signal from a memory element of said auxiliary memory representing a point in the character pattern above the second selected point in the lower portion of the character pattern to the memory element of the main memory representing the second selected point to increase the vertical second-order moment.

15. The system according to claim 14, in which said normalization means is operative to normalize the slant of the character pattern by applying shift pulses to rows of said memory in such a manner that a number of shift pulses progressively increases from a top to a bottom of the auxiliary memory to normalize rightward slant and progressively increases from the bottom to the top of the auxiliary memory to normalize leftward slant.

16. The system according to claim 14, in which said normalization means comprises a horizontal normalization unit operative to normalize the horizontal second-order moment of the character pattern by generating and applying first and second pulse trains to rows of said auxiliary memory and said main memory respectively over a predetermined time period, a frequency of the second pulse train being greater than a frequency of the first pulse train to increase the horizontal second-order moment of the character pattern, a frequency of the second pulse train being smaller than a frequency of the first pulse train to decrease the horizontal second-order moment of the character pattern.

17. In an optical character recognition system in which a document is scanned by scanning means to produce a character pattern in the form of electrical signals constituting a quantized representation of a character printed on the document, a character pattern normalization system comprising:

a main memory in which the character pattern is stored from the scanning means;

an auxiliary memory in which the character pattern is also stored from the scanning means;

sensing means arranged to sense the value of at least one spatial parameter of the character pattern in said main memory and generate at least one electrical normalization signal in response thereto; and

normalization means operatively connected to said main memory and said auxiliary memory and responsive to said at least one normalization signal, said normalization means being operative to shift the character pattern from said auxiliary memory to said main memory and normalize said at least one spatial parameter in accordance with said at least one normalization signal as the character pattern is being shifted, said at least one spatial parameter including the slant of the character pattern;

said normalization means comprises a slant normalization unit which comprises gate means operative to normalize the slant of the character pattern by gating an electrical signal from a memory element of said auxiliary memory representing a point to the left of a first selected point in an upper portion of the character pattern to a memory element of said main memory representing the first selected point and gating an electrical signal from a memory element of said auxiliary memory representing a point in the character pattern to the right of a second selected point in a lower portion of the character pattern to a memory element of said memory representing the second selected point to normalize left ward slant; and

said gate means being operative to gate an electrical signal from a memory element of said auxiliary memory representing a point to the right of the first selected point in the upper portion of the character pattern to the memory element of the main memory representing the first selected point and gate an electrical signal from a memory element of said auxiliary memory representing a point in the character pattern to the left of the second selected point in the lower portion of the character pattern to the memory element of the main memory representing the second selected point to normalize right ward slant.