Detecting line segments and predetermined patterns in an optically scanned document

Claim 3

The method of claim 1 wherein the step of detecting line elements includes determining if adjacent line elements are separated and, if so, determining if the separation is less than a predetermined amount δd; and linking the line elements separated by less than δd to form a detected line element.

Claim 4

The method of claim 2 wherein the stored picture data comprises pixels and wherein the step of detecting line elements further includes the step of detecting pixels which extend generally along a predetermined axis.

Claim 5

The method of claim 1 wherein said step of determining a connecting relationship further comprises determining if said one and other line elements having vertical separation less than δV exhibit a predetermined horizontal relationship.

Claim 6

The method of claim 4 wherein each line element includes starting and ending points having horizontal and vertical locations; and wherein said predetermined horizontal relationship comprises the horizontal location of the starting point of one line element being disposed at or between the horizontal locations of the starting and ending points of the other line element.

Claim 9

The method of claim 6, further comprising the step of deleting from the stored picture data that data therein corresponding to the enlarged line segment.

Claim 10

The method of claim 6, wherein the identified line segment is comprised of more than two line elements, each line element being adjacent to at least one other line element, vertically separated therefrom by less than δV and having a starting or ending point disposed at or between the horizontal locations of the starting and ending points of those line elements adjacent thereto.

Claim 11

The method of claim 1, further comprising the step of enlarging the identified line segment to have an expanded area.

Claim 12

The method of claim 9, further comprising the step of deleting from the stored picture data the line indicia corresponding to the enlarged line segment.

Claim 17

The method of claim 12 wherein said step of determining an adjoining relationship comprises determining if the horizontal and vertical line segments cross; and wherein said step of identifying a particular pattern comprises identifying the crossing line segments as a table pattern.

Claim 18

The method of claim 12 wherein said step of determining an adjoining relationship comprises determining if the horizontal and vertical line segments connect; and wherein said step of identifying a particular pattern comprises identifying the connecting line segments as a table pattern.

Claim 19

The method of claim 12 wherein said step of determining an adjoining relationship comprises determining if the horizontal and vertical line segments form a corner; and wherein said step of identifying a particular pattern comprises identifying the corner-forming line segments as a block pattern.

Claim 20

The method of claim 12 wherein said step of determining an adjoining relationship comprises determining if the horizontal and vertical line segments cross or connect or form a corner; and wherein said step of identifying a particular pattern comprises identifying the line segments as part of a table pattern if said line segments cross, identifying the line segments as part of a table pattern if said line segments connect, and identifying the line segments as part of a block pattern if said line segments form a corner.

Claim 21

The method of claim 16 wherein said step of identifying a particular pattern further comprises identifying one of the horizontal and vertical line segments as a line segment if it does not cross, connect with or form a corner with another line segment.

Claim 22

The method of claim 17 further comprising the steps of determining if several horizontal and vertical line segments cross or connect or form corners; identifying plural table patterns each formed of several crossing or connecting horizontal and vertical line segments; identifying plural block patterns each formed of several corner-forming horizontal and vertical line segments; identifying plural line segments each formed of a non-crossing, non-connecting and non-corner-forming line segment; and determining size and location of each table, block and line segment in said scanned document.

Claim 23

Apparatus for detecting line segments in stored picture data representing line and character indicia derived from an optically scanned document, comprising: optical scanning means for scanning a document and producing picture data corresponding to said document; storage means for storing said picture data; and processing means programmed to process the stored picture data to identify line segments therein by (a) detecting line elements from said picture data; (b) determining if the length of a line element is greater than a threshold length l th ; (c) determining a connecting relationship of one line element of greater than threshold length to another line element of greater than threshold length extending in substantially the same direction as and overlapping said one line element by determining if a vertical relationship between said one and other line elements is less than a preselected amount δV; and (d) identifying a line segment as being comprised of said one and other line elements in accordance with the connecting relationship of the line elements.

Claim 24

Apparatus for detecting line segments in stored picture data representing line and character indicia derived from an optically scanned document, comprising: optical scanning means for scanning a document and producing picture data corresponding to said document; storage means for storing said picture data; and processing means programmed to process the stored picture data to identify line segments therein by (a) detecting line elements from said picture data; (b) determining if the length of a line element is greater than a threshold length l th ; (c) determining a connecting relationship of one line element of greater than threshold length to another line element of greater than threshold length extending in substantially the same direction as and overlapping said one line element by determining if a vertical relationship between said one and other line elements is less than a preselected amount δV; and (d) identifying a line segment as being comprised of said one and other line elements in accordance with the connecting relationship of the line elements.

Claim 25

The apparatus of claim 19 wherein said processing means is programmed to detect line elements by determining if adjacent line elements are separated and, if so, determining if the separation is less than a predetermined amount δd, and linking the line elements separated by less than δd to form a detected line element.

Claim 26

The apparatus of claim 20 wherein said processing means is programmed to determine the separation between line elements extending generally along a predetermined axis.

Claim 27

The apparatus of claim 20 wherein said picture data comprises pixels and said storage means comprises means for storing a bit-mapped representation of pixels derived from the scanned document.

Claim 28

The apparatus of claim 19 wherein said processing means is further programmed to determine a connecting relationship by determining if said one and other line elements having vertical separation less than δV exhibit a predetermined horizontal relationship.

Claim 29

The apparatus of claim 23 wherein each line element includes starting and ending points having coordinate locations, and wherein said processing means is programmed to detect said predetermined horizontal relationship by determining if the coordinate location of the starting point of one line element is aligned with or between the coordinate locations of the starting and ending points of the other line element.

Claim 30

Apparatus for detecting line segments in stored picture data representing line and character indicia derived from an optically scanned document, comprising: optical scanning means for scanning a document and producing picture data corresponding to said document; storage means for storing said picture data; and processing means programmed to process the stored picture data to identify and enlarge areas of said stored picture data representing line segments by (a) detecting line elements from said picture data; (b) determining if the length of a line element is greater than a threshold length l th ; (c) determining a connecting relationship of one line element of greater than threshold length to another line element of greater than threshold length, each of the one and other line elements including starting and ending points having coordinate locations, where a coordinate location of the starting point of one line element is aligned with or between the coordinate locations of the starting and ending points of the other line element; (d) identifying a line segment occupying an area of said stored picture data in accordance with the connecting relationship of the line elements; and enlarging said area by expanding the horizontal coordinate location of the starting point of said one line element to be substantially equal to the horizontal coordinate location of said other line element and by expanding the horizontal coordinate location of the ending point of said other line element to be substantially equal to the horizontal coordinate location of the ending point of said one line element.

Claim 31

Apparatus for detecting line segments in stored picture data representing line and character indicia derived from an optically scanned document, comprising: optical scanning means for scanning a document and producing picture data corresponding to said document; storage means for storing said picture data; and processing means programmed to process the stored picture data to identify and enlarge areas of said stored picture data representing line segments by (a) detecting line elements from said picture data; (b) determining if the length of a line element is greater than a threshold length l th ; (c) determining a connecting relationship of one line element of greater than threshold length to another line element of greater than threshold length, each of the one and other line elements including starting and ending points having coordinate locations, where a coordinate location of the starting point of one line element is aligned with or between the coordinate locations of the starting and ending points of the other line element; (d) identifying a line segment occupying an area of said stored picture data in accordance with the connecting relationship of the line elements; and enlarging said area by expanding the horizontal coordinate location of the starting point of said one line element to be substantially equal to the horizontal coordinate location of said other line element and by expanding the horizontal coordinate location of the ending point of said other line element to be substantially equal to the horizontal coordinate location of the ending point of said one line element.

Claim 32

The apparatus of claim 25 wherein the processing means is further programmed to delete from said stored picture data the data corresponding to the enlarged area of the line segment.

Claim 33

The apparatus of claim 25 wherein the identified line segment is comprised of more than two line elements, each line element being adjacent to at least one other line element and vertically separated therefrom by less than a preselected amount δV; and wherein said processing means is further programmed to detect tilt in said line segment by sensing a starting or ending point of one line element at or between the horizontal coordinate locations of the starting and ending points of those line elements adjacent thereto.

Claim 34

The apparatus of claim 19 wherein the identified line segment occupies an area of said stored picture data; and said processing means is further programmed to enlarge the area occupied by said identified line segment.

Claim 35

The apparatus of claim 28 wherein the processing means is further programmed to delete from the stored picture data the data corresponding to the enlarged area of said identified line segment.

Claim 36

Apparatus for detecting lines segments in stored picture data representing line and character indicia derived from an optically scanned document, comprising: optical scanning means for scanning a document and producing picture data corresponding to said document; storage means for storing said picture data; and processing means programmed to process the stored picture data to identify line segments therein by (a) detecting line elements from said picture data; (b) determining if the length of a line element is greater than a threshold length l th ; (c) determining a connecting relationship of one line element of greater than threshold length to another line element of greater than threshold length exhibiting a predetermined horizontal relationship with said one line element; (d) identifying a line segment in accordance with the connecting relationship of the line elements; and (e) effectively rotating said stored picture data by approximately 90° and re-executing operations (a) through (d), thereby identifying at least one horizontal line segment ad at least one vertical line segment.

Claim 37

Apparatus for detecting lines segments in stored picture data representing line and character indicia derived from an optically scanned document, comprising: optical scanning means for scanning a document and producing picture data corresponding to said document; storage means for storing said picture data; and processing means programmed to process the stored picture data to identify line segments therein by (a) detecting line elements from said picture data; (b) determining if the length of a line element is greater than a threshold length l th ; (c) determining a connecting relationship of one line element of greater than threshold length to another line element of greater than threshold length exhibiting a predetermined horizontal relationship with said one line element; (d) identifying a line segment in accordance with the connecting relationship of the line elements; and (e) effectively rotating said stored picture data by approximately 90° and re-executing operations (a) through (d), thereby identifying at least one horizontal line segment ad at least one vertical line segment.

Claim 38

Apparatus for detecting line segments in stored picture data representing line and character indicia derived from an optically scanned document, comprising: optical scanning means for scanning a document and producing picture data corresponding to said document; storage means for storing said picture data; and processing means programmed to process the stored picture data to identify line segments therein by (a) detecting line elements from said picture data; (b) determining if the length of a line element is greater than a threshold length l th ; (c) determining a connecting relationship of one line element of greater than threshold length to another line element of greater than threshold length exhibiting a predetermined horizontal relationship with said one line element; (d) identifying a line segment in accordance with the connecting relationship of the line elements; (e) effectively rotating said stored picture data by approximately 90°; (f) re-executing operations (a) through (d), thereby identifying at least one horizontal line segment and at least one vertical line segment; (g) detecting if a horizontal line segment adjoins a vertical line segment; (h) determining an adjoining relationship between the horizontal and vertical line segments; and (i) identifying a particular pattern of line segments as a function of said adjoining relationship.

Claim 39

Apparatus for detecting line segments in stored picture data representing line and character indicia derived from an optically scanned document, comprising: optical scanning means for scanning a document and producing picture data corresponding to said document; storage means for storing said picture data; and processing means programmed to process the stored picture data to identify line segments therein by (a) detecting line elements from said picture data; (b) determining if the length of a line element is greater than a threshold length l th ; (c) determining a connecting relationship of one line element of greater than threshold length to another line element of greater than threshold length exhibiting a predetermined horizontal relationship with said one line element; (d) identifying a line segment in accordance with the connecting relationship of the line elements; (e) effectively rotating said stored picture data by approximately 90°; (f) re-executing operations (a) through (d), thereby identifying at least one horizontal line segment and at least one vertical line segment; (g) detecting if a horizontal line segment adjoins a vertical line segment; (h) determining an adjoining relationship between the horizontal and vertical line segments; and (i) identifying a particular pattern of line segments as a function of said adjoining relationship.

Claim 40

The apparatus of claim 31 wherein said processing means is programmed to determine an adjoining relationship by determining if the horizontal and vertical line segments cross and, if so, to identify the particular pattern as a table pattern.

Claim 41

The apparatus of claim 31 wherein said processing means is programmed to determine an adjoining relationship by determining if the horizontal and vertical line segments connect and, if so, to identify the particular pattern as a table pattern.

Claim 42

The apparatus of claim 31 wherein said processing means is programmed to determine an adjoining relationship by determining if the horizontal and vertical line segments form a corner and, if so, to identify the particular pattern as a block pattern.

Claim 43

The apparatus of claim 31 wherein said processing means is programmed to determine an adjoining relationship by determining if the horizontal and vertical line segments cross or connect or form a corner and to identify the particular pattern as part of a table pattern if said line segments cross, as part of a table pattern if said line segments connect, and as part of a block pattern if said line segments form a corner.

Claim 44

The apparatus of claim 35 wherein said processing means is further programmed to identify one of the horizontal and vertical line segments as a line segment if it does not cross, connect with or form a corner with another line segment.

Claim 45

The apparatus of claim 36 wherein said processing means is further programmed to determine if several horizontal and vertical line segments cross or connect or form corners, to identify plural table patterns each formed of several crossing or connecting horizontal and vertical line segments, to identify plural block patterns each formed of several corner-forming horizontal and vertical line segments, to identify plural line segments each formed of a non-crossing, non-connecting and non-corner-forming line segment, and to determine size and location of each table, block and line segment in said scanned document.