US5485566A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method of finding columns in tabular documents
Assignee: Xerox Corp
•
Filing: 1993-10-29
•
Granted: 1996-01-16
•
Expires: 2013-10-29
Abstract
Abstract Tabular documents have column structures that can be determined without decoding the bitmap. The method searches for separation intervals that separate word fragments in the table. These separation intervals are processed by intersecting them with other intervals and ranking the resulting intervals. A structured closure of separation intervals are maintained in bins. The intervals in the bins are sorted and used to determine new intersections when the next separation interval is processed. The intervals with the highest ranking are selected as the column separation intervals. The columns are easily identified with the method without first decoding the bitmap.
Inventors
- 👤 M. Armon Rahgozar
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-29 08:51
CPC Classifications
G; G06; G06T; G06T7/00; G06T7/70; G06V; G06V30/00; G06V30/40; G06V30/41; G06V30/414
Claims Analysis
Total Claims: 37
Claim 1
Independent Claim
74 words
A method locating columns in a tabular document comprising the steps of: determining space intervals between word fragments; intersecting the space intervals to form intersection intervals, the space intervals also intersecting with previously formed intersection intervals to form additional intersection intervals; ranking the space intervals and the intersection intervals according to a frequency of intersection between the space intervals and the intersection intervals; and selecting space intervals and intersection intervals based on the ranking.
Claim 2
Independent Claim
74 words
A method locating columns in a tabular document comprising the steps of: determining space intervals between word fragments; intersecting the space intervals to form intersection intervals, the space intervals also intersecting with previously formed intersection intervals to form additional intersection intervals; ranking the space intervals and the intersection intervals according to a frequency of intersection between the space intervals and the intersection intervals; and selecting space intervals and intersection intervals based on the ranking.
Claim 3
Dependent Claim
19 words
The method of claim 1, wherein the word fragments are one of connected letters, numbers, symbols, pictures and graphics.
Claim 4
Dependent Claim
18 words
The method of claim 1, wherein the determining step is performed without decoding characters of the tabular document.
Claim 5
Dependent Claim
21 words
The method of claim 1, wherein the word fragments are represented as a single box by using a bounding box method.
Claim 6
Dependent Claim
18 words
The method of claim 1, wherein the space intervals are a white space between two adjacent word fragments.
Claim 7
Dependent Claim
20 words
The method of claim 1, wherein skewed columns in the tabular document are processed by first deskewing the word fragments.
Claim 8
Dependent Claim
19 words
The method of claim 1, wherein the intersection intervals and the space intervals are stored in a bin structure.
Claim 9
Dependent Claim
27 words
The method of claim 7, wherein a duplicate interval is eliminated from the bin structure and the rank of the duplicate interval remaining is increased by one.
Claim 10
Dependent Claim
36 words
The method of claim 7, wherein the ranking of intervals in the bin structure depend on how often an intersection between a specific interval and an interval in the bin structure results in a duplicate interval.
Claim 11
Dependent Claim
23 words
The method of claim 7, wherein the highest ranking bin intervals represent the location of the space between columns in the tabular document.
Claim 12
Dependent Claim
22 words
The method of claim 1, wherein the intersection intervals can have a zero width representing two adjacent columns without a space interval.
Claim 13
Independent Claim
118 words
A method of locating columns in a tabular document comprising the steps of: (a) extracting a current interval located between image fragments; (b) intersecting the current interval with a bin structure interval to form intersection intervals, the bin structure interval being stored in a bin structure that contains previously extracted intervals and prior intersection intervals; (c) updating the bin structure to include the current interval and any new intersection intervals; (d) ranking the intervals in the bin structure according to a frequency of intersection between bin structure intervals; (e) repeating steps (a) through (d) until all of the intervals are extracted from the tabular document; and (f) selecting the intervals in the bin structure based on the ranking.
Claim 14
Independent Claim
118 words
A method of locating columns in a tabular document comprising the steps of: (a) extracting a current interval located between image fragments; (b) intersecting the current interval with a bin structure interval to form intersection intervals, the bin structure interval being stored in a bin structure that contains previously extracted intervals and prior intersection intervals; (c) updating the bin structure to include the current interval and any new intersection intervals; (d) ranking the intervals in the bin structure according to a frequency of intersection between bin structure intervals; (e) repeating steps (a) through (d) until all of the intervals are extracted from the tabular document; and (f) selecting the intervals in the bin structure based on the ranking.
Claim 15
Dependent Claim
18 words
The method of claim 12, wherein word fragments are one of connected letters, numbers, symbols, pictures and graphics.
Claim 16
Dependent Claim
18 words
The method of claim 12, wherein the extracting step is performed without decoding characters of the tabular document.
Claim 17
Dependent Claim
19 words
The method of claim 12, wherein the extracting step is performed without decoding a bitmap of the tabular document.
Claim 18
Dependent Claim
21 words
The method of claim 12, wherein each word fragment is represented as a single box by using a bounding box method.
Claim 19
Dependent Claim
18 words
The method of claim 12, wherein the current interval is a white space between two adjacent word fragments.
Claim 20
Dependent Claim
23 words
The method of claim 12, wherein the extracting step further includes first deskewing the word fragments when the tabular document has skewed columns.
Claim 21
Dependent Claim
39 words
The method of claim 12, wherein the updating step increases the rank of a specific interval in the bin structure when the intersection of the current interval and a bin structure interval forms a duplicate of the specific interval.
Claim 22
Dependent Claim
34 words
The method of claim 12, wherein the ranking of intervals in the bin structure depend on how often an intersection between a specific interval and the bin structure interval results in a duplicate interval.
Claim 23
Dependent Claim
25 words
The method of claim 12, wherein the selecting step selects the intervals which represent the location of the space between columns in the tabular document.
Claim 24
Dependent Claim
27 words
The method of claim 12, wherein the bin structure groups each bin structure interval into a bin based on the right-end address of the bin structure interval.
Claim 25
Dependent Claim
28 words
The method of claim 22, wherein the bin structure intervals in each bin are stored based on the location of a left-end address of the bin structure interval.
Claim 26
Dependent Claim
105 words
The method of claim 22, wherein the intersecting step further comprises the steps of: locating a first bin having the address of the left-end address of the current interval; locating a last bin having a right-most interval in the bin structure, the right-most interval having both a left-end address at most equal to a right-end address of the current interval and a right-end address larger than any other interval; and intersecting the current interval with each interval contained in all the bins having an address between the address of an interval in the first bin and the address of an interval in the last bin.
Claim 27
Dependent Claim
22 words
The method of claim 12, wherein the intersection intervals can have a zero width representing two adjacent columns without a space interval.
Claim 28
Independent Claim
122 words
An apparatus for locating columns in a tabular document comprising: a coder for coding the tabular document into word fragments; a computer for locating the columns in the tabular document, the computer including: a determinator for determining space intervals between word fragments; an intersector for intersecting the space intervals to form intersection intervals, the space intervals also intersecting with previously formed intersection intervals to form additional intersecting intervals; a ranker for ranking the space intervals and the intersection intervals according to a frequency of intersection between the space intervals and the intersection intervals; and a selector for selecting space intervals and intersection intervals based on the ranking; and an output means for outputting the locations of the columns in the tabular document.
Claim 29
Independent Claim
122 words
An apparatus for locating columns in a tabular document comprising: a coder for coding the tabular document into word fragments; a computer for locating the columns in the tabular document, the computer including: a determinator for determining space intervals between word fragments; an intersector for intersecting the space intervals to form intersection intervals, the space intervals also intersecting with previously formed intersection intervals to form additional intersecting intervals; a ranker for ranking the space intervals and the intersection intervals according to a frequency of intersection between the space intervals and the intersection intervals; and a selector for selecting space intervals and intersection intervals based on the ranking; and an output means for outputting the locations of the columns in the tabular document.
Claim 30
Dependent Claim
18 words
The apparatus of claim 26, wherein word fragments are one of connected letters, numbers, symbols, pictures and graphics.
Claim 31
Dependent Claim
20 words
The apparatus of claim 26, wherein the coder codes the tabular document into a bitmap and identifies the word fragments.
Claim 32
Dependent Claim
20 words
The apparatus of claim 26, wherein the coder forms bounding boxes around word fragments by using a bounding box method.
Claim 33
Dependent Claim
17 words
The apparatus of claim 26, wherein the output means is one of a printer and a monitor.
Claim 34
Dependent Claim
18 words
The apparatus of claim 26, wherein the space intervals are a white space between two adjacent word fragments.
Claim 35
Dependent Claim
19 words
The apparatus of claim 26, wherein the intersection intervals and the space intervals are stored in a bin structure.
Claim 36
Dependent Claim
36 words
The apparatus of claim 32, wherein the ranking of intervals in the bin structure depend on how often an intersection between a specific interval and an interval in the bin structure results in a duplicate interval.
Claim 37
Dependent Claim
23 words
The apparatus of claim 32, wherein the highest ranking bin intervals represent the location of the space between columns in the tabular document.
References Cited (Backward Citations)
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1999-01-15 | 1999-07-17 | 2000-01-16 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2003-01-15 | 2003-07-17 | 2004-01-16 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2007-01-15 | 2007-07-17 | 2008-01-16 | $7700.00 | Window Closed / Lapsed |