Method and apparatus for automatic determination of text line, word and character cell spatial features

• US 5,384,864 A
• Filed: 04/19/1993
• Issued: 01/24/1995
• Est. Priority Date: 04/19/1993
• Status: Expired due to Term

• Current Assignee: Fuji Xerox Company Limited (Xerox Holdings Corp.), Xerox Corporation (Xerox Holdings Corp.)
• Original Assignee: Fuji Xerox Company Limited (Xerox Holdings Corp.), Xerox Corporation (Xerox Holdings Corp.)
• Inventors: Spitz, A. Lawrence
• Primary Examiner(s): Mancuso, Joseph
• Application Number:
  US08/047,514
• Time in Patent Office: 645 Days
• Field of Search: 382/9, 382/48, 382/18, 382/27, 382/41, 382/44, 382/45
• US Class Current: 382/174
• CPC Class Codes: G06V 30/10 Character recognition
• CPC Class Codes: G06V 30/158 using character size, text spacings or pitch estimation

Abstract

An automatic character cell determining apparatus automatically determines the character cells within the text image of a document. A connected component generating means generates connected components from the pixels comprising the text image. A bounding box generating means generates a bounding box surrounding each connected component. A character cell determining means for locating character cells comprising one or more connected components comprises a vertical splaying means and a horizontal splaying means for ensuring white spaces between lines and connected components, a vertical profile means for determining the vertical positions of a line, means for splitting ligatures of two or more connected components and means for generating character cells grouping together one or more connected components.

Claims

1. An automatic text feature determining system for determining a text feature of an unsplayed text portion of an image of a document, the unsplayed text portion having at least two text lines separated by a first distance, comprising:

input means for inputting a digital data signal representative of the unsplayed text portion, the digital data signal comprising a plurality of signal portions, each signal portion corresponding to one of a plurality of pixels of the image;

connected component generating means for generating a plurality of connected components from the plurality of signal portions;

bounding box generating means for generating a plurality of bounding boxes, each bounding box surrounding a corresponding one of the plurality of connected components; and

line spatial feature determining means for determining spatial features of each line of text of the unsplayed text portion, each line of text comprising at least one of the plurality of connected components, the line spatial feature determining means comprising;

vertical splaying means for vertically splaying the unsplayed text into a vertically splayed text portion, wherein the vertically splayed text portion has the at least two text lines separated by a second distance, the second distance being greater than the first distance, and

vertical profile means for generating a vertical profile of the vertically splayed text portion.

2. The automatic text feature determining system of claim 1, wherein the line spatial feature determining means further comprises line content determining means for determining which ones of the plurality of connected components correspond to each line of the splayed text portion.

3. The automatic text feature determining system of claim 2, wherein the vertical profile means further comprises vertical position determining means for determining a top position and a bottom position and at least one of a baseline position and an x-line position based on the corresponding ones of the plurality of connected components for each line of the unsplayed text portion.

4. The automatic text feature determining system of claim 3, wherein the vertical position determining means determines the top and bottom positions of each at least one line based on transitions from zero to non-zero values, of the vertical profile corresponding to each line.

5. The automatic text feature determining system of claim 3, wherein the vertical profile means further comprises vertical profile generating means for generating a top position vertical profile of the top positions of the corresponding ones of the plurality of connected components and a bottom position vertical profile of the bottom positions of the corresponding ones of the plurality of connected components.

6. The automatic text feature determining system of claim 5, wherein the vertical profile means determines the x-line and baseline positions of each line of the unsplayed text from a peak of the top position and bottom position vertical profiles, respectively corresponding to each line.

7. An automatic text feature determining system for determining a text feature of an unsplayed text portion of an image of a document, comprising:

input means for inputting a digital data signal representative of the unsplayed text portion, the digital data signal comprising a plurality of signal portions, each signal portion corresponding to one of a plurality of pixels of the image;

connected component generating means for generating a plurality of connected components from the plurality of signal portions;

bounding box generating means for generating a plurality of bounding boxes, each bounding box surrounding a corresponding one of the plurality of connected components; and

line spatial feature determining means for determining spatial features of each line of text of the unsplayed text portion, each line of text comprising at least one of the plurality of connected components, the line spatial feature determining means comprising;

horizontal splaying means for horizontally splaying each line of the unsplayed text portion by horizontally separating the corresponding bounding boxes of each line of the unsplayed text portion to form a horizontally splayed text portion, horizontal overlaps of the bounding boxes in the unsplayed text portion being eliminated in the horizontally splayed text portion; and

character cell generating means for generating at least one character cell within each line of the unsplayed text portion based on the horizontally splayed text portion, each character cell comprising a group of at least one vertically aligned connected component of the horizontally splayed text portion.

8. The automatic text feature determining system of claim 7, wherein the character cell generating means determines, for each character cell, a leftmost position of the corresponding group of at least one vertically aligned connected component and a rightmost position of the corresponding at least one vertically aligned connected component, wherein boundaries of each character cell of each line comprises the leftmost position and the rightmost position of the corresponding group of vertically aligned connected components and the top and bottom positions of the corresponding line.

9. The automatic text feature determining system of claim 7, wherein the line spatial feature determining means further comprises word spacing determining means for determining intraword and interword spacing, the word spacing determining means comprising:

means for determining a line beginning position and a line ending position;

means for determining sizes of spaces between connected components of each line of the splayed text;

means for determining a distribution of space sizes; and

means for locating at least one peak in the space size distribution.

10. The automatic text feature determining system of claim 9, wherein the word spacing determining means further comprises:

means for determining whether each at least one peak for each line represents one of an interword space and an intraword space; and

means for determining whether each at least one space in each line represents one of an interword space and intraword space, based on the corresponding peak determination.

11. An automatic text feature determining system for determining a text feature of an unsplayed text portion of an image of a document, comprising:

input means for inputting a digital data signal representative of the unsplayed text portion, the digital data signal comprising a plurality of signal portions, each signal portion corresponding to one of a plurality of pixels of the image;

connected component generating means for generating a plurality of connected components from the plurality of signal portions;

bounding box generating means for generating a plurality of bounding boxes,each bounding box surrounding a corresponding one of the plurality of connected components; and

line spatial feature determining means for determining spatial features of each line of text of the unsplayed text portion., each line of text comprising at least one of the plurality of connected components, wherein the line spatial feature determining means further comprises;

stroke width determining means for determining a modal stroke width for each at least one line of text;

means for locating wide connected components having widths greater than a predetermined multiple of the modal stroke width for the corresponding line;

means for generating a cost distribution for each wide connected component;

means for locating minima within the cost distributions, each cost distribution corresponding to a predetermined portion of one of the wide connected components; and

means for splitting each wide connected component for which at least one minimum is located into two independent connected components of the unsplayed text portion.

12. The automatic text feature determining system of claim 11, wherein the predetermined multiple is 3.

13. The automatic text feature determining system of claim 11, wherein the predetermined portion of each wide connected component extends from a first point to a second point, wherein the first point is located by adding a second predetermined multiple of the modal stroke width to a leftmost position of the wide connected component and the second point is located by subtracting the second predetermined multiple of the average stroke width from a rightmost position of the wide connected component.

14. The automatic text feature determining system of claim 13, wherein the second predetermined multiple is 1.5.

15. The automatic text feature determining system of claim 11, wherein the minimum is less than a predetermined value.

16. The automatic text feature determining system of claim 15, wherein the predetermined value is equal to the modal stroke width.

17. The automatic text feature determining system of claim 11, wherein the horizontal splaying means generates the cost distribution by ANDing adjacent columns of the bounding box corresponding to the wide connected component.

18. A method for automatically determining text features of an unsplayed text portion of an image of a document, the unsplayed text portion having at least two text lines separated by a first distance, comprising the steps of:

inputting a digital data signal representative of the unsplayed text portion, the digital data signal comprising a plurality of signal portions, each signal portion corresponding to one of a plurality of pixels of the image;

generating a plurality of connected components from the plurality of signal portions;

generating a plurality of bounding boxes, each bounding box surrounding a corresponding one of the plurality of connected components;

determining spatial features of each line of text of the unsplayed text portion, each line of text comprising at least one of the plurality of connected components;

vertically splaying the unsplayed text portion into a vertically splayed text portion, wherein the vertically splayed text portion has the at least two text lines separated by a second distance, the second distance being greater than the first distance; and

generating a vertical profile of the vertically splayed text portion.

19. The method for automatically determining text features of claim 18, wherein the step of vertical splaying comprises the step of determining which ones of the plurality of connected components correspond to each line of the text portion.

20. The method for automatically determining text features of claim 19, wherein the step of generating the vertical profile comprises the step of determining, for the text portion, a top position and a bottom position and at least one of a baseline position and an x-line position based on the corresponding ones of the plurality of connected components for each line.

21. The method for automatically determining text features of claim 20, wherein the step of determining determines the top and bottom positions of each line from a maximum peak and a minimum peak, respectively of the vertical profile corresponding to each line.

22. The method for automatically determining text features of claim 20, wherein the step of generating the vertical profile further comprises the step of generating a top position vertical profile of the top positions of the corresponding ones of the plurality of connected components and a bottom position vertical profile of the bottom positions of the corresponding ones of the plurality of connected components.

23. The method for automatically determining text features of claim 20, wherein the step of determining determines the x-line and baseline positions of each line from a peak of the top position and bottom position vertical profiles, respectively corresponding to each line.

24. A method for automatically determining text features of an unsplayed text portion of an image of a document, comprising the steps of:

inputting a digital data signal representative of the unsplayed text portion, the digital data signal comprising a plurality of signal portions, each signal portion corresponding to one of a plurality of pixels of the image;

generating a plurality of connected components from the plurality of signal portions;

generating a plurality of bounding boxes, each bounding box surrounding a corresponding one of the plurality of connected components;

determining spatial features of each line of text of the unsplayed text portion, each line of text comprising at least one of the plurality of connected components;

horizontally splaying each line of the unsplayed text portion by horizontally separating the corresponding bounding boxes of each line of the unsplayed text portion to form a horizontally splayed text portion, horizontal overlaps of the bounding boxes in the unsplayed text portion being eliminated in the horizontally splayed text portion; and

generating at least one character cell of each line of the unsplayed text portion based on the horizontally splayed text portion, each character cell comprising a group of at least one vertically aligned connected component of the horizontally splayed text portion.

25. The method for automatically determining text features of claim 24, wherein the step of generating character cells comprises the step of determining, for each character cell. a leftmost position of the corresponding group of at least one vertically aligned connected component and a rightmost position of the corresponding at least one vertically aligned connected component, wherein boundaries of each character cell of each line comprises the leftmost position and the rightmost position and the top and bottom positions of the corresponding line.

26. The method for automatically determining text features of claim 24, wherein the step of determining space widths comprises the steps of:

determining a line beginning position and a line ending position;

determining sizes of spaces between connected components of each line of the splayed text;

determining a distribution of space sizes; and

locating at least one peak in the space size distribution.

27. The method for automatically determining text features of claim 26, wherein the step of determining space widths further comprises the steps of:

determining whether each at least one peak for each line represents one of an interword space and an intraword space; and

determining whether each at least one space in each line represents one of an interword space and intraword space, based on the corresponding peak determination.

28. A method for automatically determining text features of an unsplayed text portion of an image of a document, comprising the steps of:

inputting a digital data signal representative of the unsplayed text portion, the digital data signal comprising a plurality of signal portions, each signal portion corresponding to one of a plurality of pixels of the image;

generating a plurality of connected components from the plurality of signal portion;

generating a plurality of bounding boxes, each bounding box surrounding a corresponding one of the plurality of connected components;

determining spatial features of each line of text of the unsplayed text portion, each line of text comprising at least one of the plurality of connected components;

determining a modal stroke width for each at least one line of text;

locating wide connected components having widths greater than a predetermined multiple of the modal stroke width for the corresponding line;

generating a cost distribution for each wide connected component;

locating cost minima within the cost distributions, each cost distribution corresponding to a predetermined portion of one of the wide connected components; and

splitting each wide connected component for which at least one cost minimum is located into two independent connected components.

29. The method for automatically determining text features of claim 28, wherein the predetermined multiple is 3.

30. The method for automatically determining text features of claim 29, wherein the predetermined portion of each wide connected component extends from a first point to a second point, wherein the first point is located by adding a second predetermined multiple of the modal stroke width to a leftmost position of the wide connected component and the second point is located by subtracting the second predetermined multiple of the average stroke width from a rightmost position of the wide connected component.

31. The method for automatically determining text features of claim 30, wherein the second predetermined multiple is 1.5.

32. The method for automatically determining text features of claim 28, wherein the minimum is less than a predetermined value.

33. The method for automatically determining text features of claim 32, wherein the predetermined value is equal to the modal stroke width.

34. The method for automatically determining text features of claim 28, wherein the step of generating the cost distribution comprises ANDing adjacent columns of the bounding box corresponding to the wide connected component.