Method of Finding Columns in Tabular Documents

1. Field of the Invention

This invention relates to improvements in finding the columns in a tabular document. More particular, this invention searches for column separations and only processes the line-intervals separating the word fragments in the table.

2. Description of the Related Art

A tabular document is a systematic arrangement of logically related entities that are mapped onto a layout structure based on simple linear constraints. By controlling the placement and format of each entity, these constraints provide the visual cues that help to identify the organization of a table content, i.e., its logical structure. The primary geometrical constraint imposed on a table is a linear placement of related entities. Other constraints include alignment and use of monospaced fonts in typesetting the table.

In documents containing a large number of similar records, entities of the same logical identity are typically placed along columns of a grid structure. To determine the locations of the columns, a conventional technique histograms the bitmap and searches the histogram for peaks. This method requires processing the characters and other artifacts into a bitmap.

The invention recognizes that the column structure of these types of documents can be determined without decoding the bitmap. The invention searches for column separations by examining the line-intervals separating the word fragments in the table. This method is more reliable and computationally efficient. It produces and maintains an ordered closure of a set of line intervals (word fragments separation intervals) under the operation of the line intersection. A column separation interval, which is the intersect of many word fragment separation intervals, is easily identified by this technique.

The invention is illustrated in the accompanying drawings, in which like reference numerals are used to denote like or similar parts, wherein:

FIG. 1 is an apparatus which uses the method of the invention;

FIG. 2 is an example of a tabular document which has various column alignments;

FIG. 3 is the skeleton of the tabular document of FIG. 2 represented by word fragment bounding boxes;

FIG. 4 is a simple table with two columns showing the word fragment separation intervals and the column separation interval;

FIG. 5 is a bin structure for a simple set of line intervals;

FIG. 6 is the simple set of line intervals stored in the bin structure of FIG. 5;

FIG. 7a-7b show an example of the intersection of an interval with intervals in a bin;

FIG. 8 is a flowchart of the method of the invention; and

FIGS. 9-16 show an example using the method of the invention.

Referring now to the drawings, the drawings are for the purpose of describing preferred embodiments of the invention and not for limiting the same. The invention provides a method for finding columns in tabular documents without decoding the characters into bitmap. After the columns are located, a pattern matcher can be used to estimate the syntax of each logical field and an OCR (optical character recognition) module can read each character in the document.

FIG. 1 shows a typical set-up that uses the method of the invention. A document scanner 10 is used to process the image. If the document is already coded, it can be input directly into the computer 12. Input may also be a PDL (Page Description Language) such as Postscript where character bounding boxes are readily available. The computer 12 locates the intervals separating the table entries by using the method of the invention. The location of the columns in the table can be displayed on the monitor 14 or printed using the printer 16. It can also be used for further processing by the computer 12, as is the case here.

Referring to FIG. 2, a telephone toll record is an example of the above type of document that has monospace type fonts (this is not a necessity for the method to be applicable) and exhibits various column alignments. Other examples include insurance forms, financial spreadsheets, bank statements, tax forms, and diagnostic manuals. For identifying the column structure of these documents, the visual cues are the blank spaces and/or lines that separate the columns. Ruled tables can be recognized by finding the line structures, and therefore, are not processed by the method of this invention. Ruled tables can be processed by this technique if the rules are removed. The remaining white spacing can be used to apply the algorithm.

FIG. 3 shows a skeleton of the document in FIG. 2 where the text has been replaced with word fragment bounding boxes. A computer can extract the word fragment bounding boxes from either a bitmap or a PDL. Many of the tables layout attributes can be easily identified by concentrating on the white space that forms the borders of the columns in the table. The method finds a column structure of a table by identifying its column boundaries.

Conventionally, the column boundaries of a table can be found by projecting the image onto the horizontal axis and searching for intervals of low density along this projection. These intervals, which correspond to the column separation intervals, have a length that corresponds to the width of the column boundaries. In this invention, column separation intervals can be computed from the intervals representing the extent of the white spacing between consecutive word fragments. The method of the invention finds column separation intervals based on word fragment separation intervals. Considering that acquisition of word fragments is free in the document recognition application, this method is computationally less expensive than a method that projects and searches at the bitmap level. Furthermore, this method is more reliable for finding columns because the boundaries occupy less space and are more uniformly laid in a typical tabular document.

A first preferred embodiment will be described with reference to FIGS. 4-6. Referring to FIG. 4, a word fragment bounding box is a small rectangular box which encloses a word fragment. A word fragment separation interval is defined as a large interval along the x-axis which separates two consecutive word fragment bounding boxes on the same line. FIG. 4 shows word fragment boxes 30 and the word fragment separation intervals I.sub.1 -I.sub.5 for a simple two-column table. For example, a column bounding boxes 32 is the smallest rectangle which encloses all the entries in a column. The column separation interval is the smallest interval J along the x-axis which separates two consecutive column bounding boxes 32.

For interval J to be a column separation interval as shown in FIG. 4, it is necessary that interval J be a subset of every word fragment separation interval which separates the same line entries from two consecutive columns. Thus, interval J has to be included in their intersection. Therefore, the method finds all line intervals that can be candidates for column separation intervals by creating a closure of the set of line intervals (e.g., word fragment separation intervals) under the operation of line intersection. A set of line intervals is a closure if for any two elements in that set, their intersection is also in that set. Interval I is defined as I=[a,b]; where a<b and "a" represents the left-end point of the interval and "b" represents the right-end point of the interval. The length of the interval is I.sub.length =(b-a). The intersection of I.sub.j .andgate.I.sub.k, which represents the interval of the overlap between the two intervals I.sub.j and I.sub.k, may be of length zero. For each element of the closure, an associated ranking, which is the number of word fragment pairs separated by that interval, is determined. In FIG. 4, interval J has a ranking of R(J)=5. The ranking of 5 states that J can be used as a column separator for 5 rows in the table.

Thus, the method defines a process of finding column separation intervals by three tasks: first, finding the closure of the set of word fragment separation intervals; second, ranking each element of the closure based on the number of word fragment pairs that it separates; and third, searching the closure for the smallest intervals which have the highest rankings.

To find the closure G of the set of word fragment separation intervals, the closure G is iteratively updated by adding to the closure a newly found word fragment separation interval and its intersection with all the previous members of the closure. Next, each interval in the closure G is ranked. This may be accomplished by comparing every interval I of the set of word fragment separation intervals with every element g of its closure G. If g I, the rank of g may be increased by one since it implies that g may be used as a separation interval instead of I. A duplicate interval increases the ranking of the interval in the closure G without adding new elements to the closure.

Alternatively, these two steps could be incorporated into a single step. For each new interval I.sub.i+1, an intersection is determined with all elements g.epsilon.G.sub.i, where G.sub.i is a closure obtained after processing the first i intervals. If g I.sub.i+1, then increment the rank of g. If I.sub.i+1 is unique, then add I.sub.i+1 to the closure G.sub.i. Its rank can be determined by adding one to the rank of the smallest element G, that contains I.sub.i+1. (Notice that if I.sub.i+1 is contained in n intervals, it is also contained in their intersection. This intersection is the smallest interval in the closure that contains I.sub.i+1, because if there was a smaller interval in the closure that had contained I.sub.i+1, it would have been the intersection of the n intervals.) Also, if I.sub.i+1 intersects some interval g, that intersection should be added to closure G only if it is unique. The rank of this intersection is also found by adding one to the rank of the smallest element that contains it.

At each iteration of the above method, a search is required in order to avoid adding duplicate intervals to the closure. A search is also required for ranking. The complexity of these searches increases when the size of the closure increases. In addition, every iteration goes through the entire closure. However, due to the nature of the intervals in finding columns, the intervals are typically clustered in regions. Thus, only a search of a subset of the closure may be needed.

In the invention, an unstructured closure is grouped into sets of intervals using the following scheme. Referring to FIG. 5, a hash table 40 that contains the addresses of the right-end of all the intervals is created. The hash table 40 is used in order to index into a bin structure 42. The bin structure 42 consists of many storage bins which are linked together in a sorted increasing order. Each key-value pair in the hash table 40 is associated with a storage bin in the bin structure 42. The bin holds the left-end address of all the intervals that have the same right-end address. Associated with each left-end address is an interval ranking. Each bin is also assigned a right-most address which represents the right-end address of the right-most interval that contains the address of the hash table. The left-end addresses in each bin are maintained in a right-to-left order, i.e., the smallest interval to the largest interval.

The purpose of the hash table is to provide FAST indexing into an appropriate bin storage. An array structure could replace both the hash table and the linked list. Then, the intervals with the same right end point will be stored in the array element indexed by the value of the right end point. Of course many array elements will be empty).

An example of a storage using a hash table is shown in FIG. 5 for a small set of intervals shown in FIG. 6. In FIG. 6, interval A has a right-end address of eight; intervals B and D have right-end addresses of twelve; and interval E has a right-end address of twenty-two. Therefore, the bin structure 42 must contain these three addresses as a minimum (address fifteen is shown for clarification of the example.) Referring to FIG. 5, interval A is stored in the storage bin eight with a rank of one. Interval C intersects with interval A, therefore the right-end address of the right-most interval which contains address eight is address twelve.

Address twelve in the bin structure 42 has two entries. First, interval B, which is unique, is added to the bin with rank one. This will initially be represented by (10.1) in the bin. Then, interval C, which is also unique, is added to the bin. It is represented by a new element (4.1), which has ranking of one. The intersection of intervals B and C is performed, which results in interval B. Since interval B is already in the bin, only its rank will increase. Thus, (10.1) will be changed to (10.2). Consequently, the ranking of interval B is increased by one. Next, interval D is processed. Since interval D is not unique. i.e., it replicates interval B, the rank of those intervals in the closure that contain interval D are increased. The only one that contains interval D is interval B; so its rank is increased to three. Thus, (10.2) is modified to (10.3). The right-most address of bin twelve is zero because there are no intervals with a right end to its right that contain the address twelve.

Interval E is processed. This interval does not intersect with any other intervals, therefore it is put into the storage bin twenty-two with a rank of one.

Some tabular documents may contain several columns. A second preferred embodiment of the invention eliminates the need to check each interval in the closure G.sub.i. Finding the set of intervals that intersect a given interval I is performed by beginning the search at the bin containing the left-end address of interval I. This bin address includes all intervals g whose right-end addresses are greater than or equal to the left-end address of interval I:

This relationship of intervals g and I must exist for any interval g that intersects interval I.

The search for intersecting intervals continues by consecutively processing each bin to the right. The search could continue to the last bin; but, in the alternative, the search can cease when the last bin processed satisfies the following condition: its bin address is the same as the right-most address of the storage bin corresponding to the right-end of interval I. In other words, this bin holds the right-most interval that intersects interval I.

At each bin, the intervals that intersect interval I are found by walking down the sorted list of the left-ends in the bin, i.e. smallest to largest interval, and only considering those intervals g such that the following condition is satisfied:

where right(I) is the right-end address of interval I and left (g) is the left-end address of interval g.

Although all the bins may be searched in the worst case, the search length is typically proportional to the number of bins that fall in an interval. It is important to notice that during the search, a storage bin may be discarded instantly if: (1) its addresses does not correspond to any interval's right-end point, i.e. it is empty; or (2) all the elements in it are to the right of the selected interval I, i.e. the left end of the last element in the bin (the largest) is greater than the right end of interval I.

When a new interval I.sub.i+1 intersects an interval g of the closure G.sub.i, which is arranged according to the aforementioned structure, the rank of the non-empty intersection I.sub.g, which was formed by the intersection I.sub.i+1 .andgate.g, is simply determined by adding one to the rank of the interval g. This occurs because the interval g that causes the intersection is the smallest element which contains the intersection I.sub.g. This is purely a consequence of the way the intervals are stored and searched.

There are two possible cases that occur when a new intersection is formed. FIG. 7a shows the first case. Interval I.sub.i+1 is intersected with the members of bin x starting from g.sub.1 to g.sub.4. Interval I.sub.g results from the intersection of I.sub.i+1 .andgate.g.sub.2. Interval I.sub.g has the right-end of the interval g.sub.2, i.e. the interval causing the intersection, and the left-end of interval I.sub.i+1. Thus, the smallest interval containing interval I.sub.g and having the same right-end would be in the same bin as interval I.sub.g2. Because the intervals in bin x are sorted right-to-left, i.e., left-end address of interval g.sub.2 is greater than the left-end address of interval g.sub.3, the smallest interval with a left-end address to the left of left-end address of interval I.sub.g is the one that produces the intersection. Furthermore, there are no intervals I.sub.s containing I.sub.g that satisfy the following two conditions:

If an interval I.sub.s existed, then its intersection with the interval g.sub.2 would have added another element to the bin. This can not occur because G.sub.i is a closure and must have contained it.

FIG. 7b shows the second case. Any interval containing I.sub.g must contain the left-end of g.sub.5 and right-end of I.sub.i+1. But no such interval I.sub.s satisfies the following conditions:

If an interval satisfied these conditions, then the interval would have caused the intersection while processing was at a previous bin. This can not occur because interval I.sub.g is a new intersection.

Referring to FIG. 8, a flow diagram of the method of the first preferred embodiment is shown. In step 100, the word bounding boxes are accessed. This can be performed by the computer program. Flow proceeds to step 102 where the space intervals between the bounding boxes is determined. These intervals are stored in memory.

In step 104, memory is checked to verify that all the intervals have been processed. If any stored interval has not been processed, the next interval (current interval) is selected from memory in step 106. Flow proceeds to step 108 to determine if all the bin elements have been processed with the current interval.

If step 108 determines that there are more bin elements to process with the current interval, then flow proceeds to step 110 to select the next bin element. Step 112 checks if the selected bin element is contained in the current interval. If the selected bin element is contained in the current interval, then the rank of the selected bin element is increased by one in step 114. Flow now returns to step 108.

If step 112 determines that the selected bin element is not contained in the current interval, then the intersection of the selected bin element and the current interval is determined in step 116. Step 118 determines if the non-empty intersection is a bin element. If the intersection is not a bin element, then the intersection is added to the bin structure and its rank is equal to the rank of the selected bin element plus one. If either the intersection is the selected bin element in step 122 or execution of step 124 is complete, flow returns to step 108.

After all the bin elements are processed in step 108, then flow proceeds to step 122 to check if the current interval is unique. If the current interval is unique, then step 124 is executed to add the current interval to the bin structure with a rank of one. If the current interval is not unique or the execution of step 124 is complete, flow proceeds to step 104 to determine if there is another interval in memory to process. After all the intervals are processed, flow proceeds to step 126 to select the bins with the highest ranks.

It is not necessary to perform steps 100 and 102 before performing step 104. In the alternative, step 104 could determine the next space interval between the next set of bounding boxes. For each iteration to fill the bin structure, the modified step would perform the function of determining if another space interval exists and locating that space interval.

Referring to FIGS. 9-16, an example using this method will be described. FIG. 9 displays a skeleton of a document where only the word fragment bounding boxes are shown. As can be seen by this figure, there are three different columns ranging from 0 to 3, 5 to 9, and 11 to 15. There are six rows of data each having varying widths of text which are within the bounding boxes. FIG. 10 shows the six rows with the intervals between the bounding boxes marked from I.sub.0 to I.sub.20. As can be seen in the figure, row 1 has four separate intervals which do not contain text.

Row 1 is processed first. Referring to FIG. 13, a bin structure is created using an array with fifteen locations. In the alternative, a hash table could be used with new addresses added when necessary. Each of the four intervals is placed in the appropriate bin. The interval I.sub.0 has address locations between 0 and 1. Therefore, interval I.sub.0 is represented in bin 1 with the digit left of the decimal point indicating the left-end point of the interval. The number to the right of the decimal point indicates the ranking of that interval. Therefore, interval I.sub.0 is located in bin 1 with the notation (0.1). Similarly, I.sub.1 ranges from address location 2 to 5. Therefore, interval I.sub.1 is put into bin 5 with the notation (2.1). Similarly, interval I.sub.2, which has address locations from 7 to 12, is placed into bin 12 with the notation (7.1). The interval I.sub.3 is placed into bin 15 with the notation (13.1). None of these intervals intersect with each other, and therefore, this row is complete.

Row 2 is next processed. Interval I.sub.4 is located between 3 and 6. An intersection is determined between interval I.sub.4 and all the intervals which are already in the bin structure. It is clear from FIG. 10 that interval I.sub.4 is not a duplicate of any previous interval and it intersects only with interval I.sub.1. The intersection of intervals I.sub.1 and I.sub.4 is not a bin element. Therefore, a new interval I.sub.21 is created using the following equation:

Referring to FIG. 14, bin 5 now contains the notation (3.2), which represents interval I.sub.21. The rank of the interval is 2 because the rank is a sum of ranks of two intervals causing the intersection, i.e., intervals I.sub.1 and I.sub.4. Interval I.sub.4 is also added to bin 6 with the notation (3.1). Bin 5 now has two elements in it with the highest rank on top.

Next, interval I.sub.5 is processed. Referring to FIG. 10, interval I.sub.5 intersects both intervals I.sub.2 and I.sub.3. These intersections create two new intervals I.sub.22 and I.sub.23, which are determined from the following equations:

The ranking of each interval I.sub.22 and I.sub.23 is determined as before so that their rank is two. Now that this row is complete, the bin structure is updated and shown in FIG. 14. As can be seen, bin 12 now contains the notation (9.2) for new interval I.sub.22 and new interval I.sub.23 is located in bin 14 with the notation (13.2). Interval I.sub.5 is also added to bin 14 with rank one and is represented by the notation (9.1).

Referring to FIG. 11, the intervals in the bins are drawn. Rank 2 intervals are I.sub.21, I.sub.22 and I.sub.23 and rank 1 intervals are I.sub.1 -I.sub.5. Also, row 3 has been drawn with intervals I.sub.6 -I.sub.9.

As can be seen by FIG. 11, interval I.sub.6 does not intersect with any other intervals. Therefore, it is added to bin 2 as shown in FIG. 15.

Interval I.sub.7 intersects with three intervals: I.sub.21, I.sub.1 and I.sub.4. The intersection of each of these intervals with interval I.sub.7 is determined by the following equations:

The intersection of equation 10 is simply interval I.sub.4. Thus interval I.sub.4 is contained in interval I.sub.7. Therefore, no new interval is added to the bin structure, but the ranking of interval I.sub.4 is increased by one. Referring to FIG. 15, interval I.sub.4, which is located in bin 6, has the updated notation (3.2). Accordingly, Equation 11 does not add a new element to the bin structure, but increases the rank of interval I.sub.21 to three. Intersection of intervals I.sub.7 and I.sub.1 is interval I.sub.21 which is already in the bin structure, so nothing is done. Interval I.sub.7 is added to bin 7 with a rank of one.

Referring to FIG. 11, interval I.sub.8 intersects intervals I.sub.22, I.sub.2 and I.sub.5. These intersections generate the following intervals:

The first intersection, equation 13, adds interval I.sub.8 to the bin structure with a rank of three because one is added to the rank of interval I.sub.22, which is two. The intersections in equations 14 and 15 will not have any effects since interval I.sub.8 has already been added to the bin structure.

Referring to FIG. 11, interval I.sub.9 intersects with intervals I.sub.23, I.sub.3 and I.sub.5. The following equations are determined by these intersection:

The ranking of intervals I.sub.23 and I.sub.3 is increased by one since each is contained in interval I.sub.9. Equation 18 has no effect since interval I.sub.23 is already in the bin structure. FIG. 15 shows the bin structure after row 3 has been processed.

Rows 4-6 are processed in the same manner to form the final bin structure shown in FIG. 16. Notice that bin 5 has notation (3.6) and bin 11 has notation (9.6). Therefore, the highest ranking intervals have the rank of six. Thus, the column separating interval using this process is determined to be the intervals with the length of [3,5] and [9,11]. As can be seen in FIG. 9, this would be smallest interval between the columns which range from interval 0 to 3, 5 to 9 and 11 to 15.

If equalities are allowed while determining intersections using equation (1) and (2), the method can establish column separations of width zero. For example, the storage bin thirteen in FIG. 16 will have an element (13.6). This corresponds to a column separation of width zero between column locations 13 and 14 in FIG. 9.

A computer program does not "visualize" the current interval intersecting other intervals in the bin structure. Therefore, the method includes a way to eliminate processing bin intervals that do not intersect with the current interval.

For example, to find all the elements that intersect I.sub.7 in FIG. 11, the left-end of interval I.sub.7 is three. The processing to determine intersections with interval I.sub.7 begins with bin three and continues with the bins to the right. Processing continues to the bin which contains the right-end of the right-most interval that intersects with interval I.sub.7. For example, the right-most interval associated with interval I.sub.7, which is located in bin 7, is interval I.sub.2. The right-end of interval I.sub.2 is twelve. Therefore, processing continues from bin 3 to bin 12.

A sample program which uses the method of the invention is shown below. Let G.sub.i be the closure of the first i intervals and I.sub.i+1 be a new interval.

This program is only a sample, other programs can be used to accomplish the steps of the invention.

Other variations to the preferred embodiments can be made. For example, the left-end addresses can be stored in the hash table. Therefore, searches would be done from right-to-left in the same manner as described above.

Another variation can occur when the tabular document is skewed. If the skewing of the columns is measured, then the previous preferred embodiments is modified by determining the bounding boxes and then deskewing only these bounding boxes. This method is preferable to processing the entire bitmap. The rest of the processing can be performed as previously described.

Although the invention has been described and illustrated with particularity, it is intended to be illustrative of preferred embodiments. It is understood that the disclosure has been made by way of example only. Numerous changes in the combination and arrangements of the parts, steps, and features can be made by those skilled in the art without departing from the spirit and scope of the invention, as hereinafter claimed.