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

Claim 2

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.

Claim 3

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.

Claim 4

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.

Claim 5

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.

Claim 6

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.

Claim 7

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.

Claim 8

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.

Claim 9

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.

Claim 10

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.

Claim 11

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.

Claim 12

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.

Claim 13

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.

Claim 14

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.

Claim 15

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

Claim 16

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.

Claim 17

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

Claim 18

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

Claim 19

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

Claim 20

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.

Claim 23

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.

Claim 24

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.

Claim 25

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.

Claim 26

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.

Claim 27

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.

Claim 30

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.

Claim 31

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.

Claim 32

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.

Claim 35

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

Claim 36

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.

Claim 37

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

Claim 38

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

Claim 39

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

Claim 40

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.