Method and Apparatus for Identifying Table Areas in Documents

1. Field of the Invention

The present invention relates to an image processing method and apparatus which can identify ruled lines which construct a table from image data of a table area and can also discriminate a cell area.

2. Related Background Art

Hitherto, in order to identify ruled lines of a table having an irregular construction from inputted image data and to decide a cell area, irregularity could not be recognized by histograms obtained in both the horizontal and vertical directions from a whole table area. Hence, continuity of the ruled lines is found by tracing an outline, whereby a connecting state of the ruled lines is judged and an intersection is identified.

The conventional technique mentioned above requires a long processing time and, when a part of the ruled lines of the table in an original image is blurred, continuity of the ruled lines in such a portion is lost. Also, there is a problem when a cell area in the table cannot correctly be determined by the outline tracing.

In the present invention, an intersection can be correctly detected from a table having an irregular construction by obtaining a histogram of a small area and by identifying the intersection.

According to the present invention, since an intersection of the table is discriminated by the histogram, processing time can be reduced. Further, after the histogram of a whole table area is obtained, the position of the small area histogram is determined. Therefore, an irrelevant small area is not used as a target for identification and processing time can be reduced.

Moreover, since the intersection is detected by obtaining, at two stages, the large and small area histograms, construction of the table can be identified even when image data is blurred.

FIG. 1 is a block constructional diagram of an image processing apparatus of an embodiment;

FIG. 2 is a first flowchart showing a processing procedure of the operation of the embodiment;

FIG. 3 is a diagram showing an example in which histograms are obtained in both the horizontal and vertical directions for a certain table area;

FIG. 4 is a diagram showing an example in which intersection coordinates are obtained from peak position coordinates in a small scale histogram;

FIG. 5 is a diagram of a procedure in which a cell area is designated from the obtained intersection coordinates;

FIGS. 6A and 6B are diagrams showing examples of deformed tables;

FIG. 7 is a diagram showing an example in which intersection coordinates are obtained by providing an imaginary frame for the deformed table;

FIG. 8 is a second flowchart showing a processing procedure of the operation of the embodiment;

FIGS. 9A to 9S are diagrams showing examples of an intersection pattern dictionary to be formed;

FIGS. 10A to 10C are diagrams showing a first example of an intersection pattern dictionary and an intersection pattern extracted from an original image;

FIG. 11 is a diagram of a procedure in which a cell area is designated from the intersection coordinates included in the obtained intersection pattern;

FIG. 12 is a diagram showing an example in which an imaginary frame is attached to the deformed table;

FIGS. 13A to 13D are diagrams showing examples of intersection patterns to which dictionaries should be added for deformed tables;

FIG. 14 is a third flowchart showing a processing procedure of the operation of the embodiment; and

FIGS. 15A to 15C are diagrams showing a second example of an intersection pattern dictionary and a normalized intersection pattern extracted from the original image.

Embodiments of the invention will be explained in detail hereinbelow with reference to the drawings.

FIG. 1 shows a schematic construction of an image processing apparatus of an embodiment of the invention. In FIG. 1, reference numeral 101 denotes an input unit of image data; 102 denotes an arithmetic operation processing unit (CPU) which performs an arithmetic operation on processes of each unit in accordance with a control program stored in a memory unit 103; and 103 denotes the memory unit (MEM) which stores various kinds of data such as control programs of flowcharts (described hereinafter) and intersection pattern forming information (explained hereinlater). The memory unit 103 includes a ROM and a RAM.

Reference numeral 107 denotes an output unit which outputs the result of the arithmetic operating process, the result of the image process, and image data and which executes transmission to a host computer for printing by a printer. Reference numeral 104 denotes a display, for example, a CRT to display the data; 105 denotes an area divider which analyzes image data inputted from the input unit 101 and executes a whole area dividing process for detecting an area in which character, table, or diagram exists; and 106 denotes a table cell designator to designate a cell area in a table extracted by the area divider 105.

Reference numeral 108 denotes a normalizer for making uniform the size of the intersection pattern for extracting an intersection portion of the table from the image data; and 109 denotes a feature extractor to extract a feature vector from the image pattern of the extracted intersection pattern. Reference numeral 110 denotes a pattern identifier which calculates a distance between the feature vector obtained from the image pattern inputted by the input unit 101 and a study vector stored in the dictionary and which identifies the inputted image pattern. Reference numeral 111 denotes a dictionary which stores various dictionaries of study vectors and the like to be calculated by the pattern identifier 110.

The process for designating a cell area using a small scale histogram by the table cell designator is shown in the flowchart of FIG. 2.

A table area A, shown by a broken line in FIG. 3, is an area judged to be an area in which a table image exists by the area divider provided in the image processing apparatus. In FIG. 3, a histogram of pixels is obtained within a range of the table area A by using one point in area A as a reference point (step 201). Reference numeral 301 schematically shows a histogram in the horizontal direction and 302 schematically shows a histogram in the vertical direction. In the histograms, it is assumed that, for example, (m) peaks equal to or larger than a threshold value Ha of the height determined in the horizontal direction appear in the horizontal direction; and (n) peaks equal to or larger than a threshold value Hb of the height determined in the vertical direction appear in the vertical direction. On the above assumption, peak position coordinates a (a.sub.1, a.sub.2, . . . , a.sub.m) and b (b.sub.1, b.sub.2, . . . , b.sub.n,) of the above peaks, and peak widths Wa and Wb, determined by the averages of the peak widths, are stored in the memory unit 103 (step 202) as peak data.

When the peak positions are located at regular intervals and have the same height in each of the horizontal and vertical directions, intersections of the ruled lines in the table can be obtained by calculations. However, in general, a number of tables having irregular constructions as shown in FIG. 3 exist. A cell area Cl in the table is the cell area which was divided into four regions in the vertical direction for determining the intersections of the peaks in the horizontal and vertical directions. Therefore, the correct cell area cannot be determined.

First, the average of the peak widths Wa and Wb obtained in FIG. 3 is calculated, thereby obtaining an average line width W (step 203). A value M is determined by adding a certain value to the obtained average line width W. Since M>W, the value of M can be determined by the ratio with W, or it can be set to exceed the maximum width in consideration of values of Wa.sub.1 to Wa.sub.m and values of Wb.sub.1 to Wb.sub.n, or it can be determined by adding a predetermined value. As shown in FIG. 4, the peak position coordinates a and b in the horizontal and vertical directions, stored in the memory unit 103, are used as references and image data is extracted in a band shape having a width of M (M>W) dots, thereby forming partial histograms of pixels in the horizontal and vertical directions (step 204).

In FIG. 4, the peak position coordinates a and b stored in the memory unit 103 have been set as references, and the band area having the width of M dots has been determined in the positive direction from the reference point of table area A. However, the invention is not limited to the above method. The width of M dots can be also set in the negative direction. The band area with respect to the peak position coordinates a and b as centers can be also determined, so that even when a construction of the table is not clear intersections can be accurately detected.

A histogram of pixels in the band area determined as mentioned above is obtained. For instance, in FIG. 4, a histogram in a band area determined by using the peak position coordinates b.sub.2 as a reference, namely, a band Bb.sub.2 (band area of a hatched pattern) is a histogram Hb.sub.2. In FIG. 4, in order to avoid complication of the diagram, a reference line position of the histogram is shown by deviating from the peak position coordinates.

From the peak positions (Ya.sub.1, Ya.sub.2, . . . , Ya.sub.m) detected by the histogram Hb.sub.2 and the position (b.sub.2) of the reference line of the histogram Hb.sub.2, intersections detected by the histogram are set to b,.sub.12 (b.sub.2, Ya.sub.1), b.sub.22 (b.sub.2, Ya.sub.2), . . . and Y.sub.m2 (b.sub.2, Ya.sub.m) (step 205). Intersections are detected in each small scale area by setting the peak position coordinates a (a.sub.1, a.sub.2, . . . a.sub.m) and b (b.sub.1, b.sub.2, . . . , b.sub.n) as references and are stored in the memory unit 103. When obtaining such intersections, it is also possible to predetermine areas Z.sub.a and Z.sub.b of intersection coordinates predicted from the peak position coordinates a and b or threshold values h.sub.a and h.sub.b of proper heights in the small area histogram and to obtain intersections a.sub.ij and b.sub.ij within those ranges. Subsequently, with respect to the intersections in which the combinations of suffixes i and j are equal (in FIG. 4, a.sub.22 and b.sub.22), a distance I 5 between them is calculated. When the distance I is smaller than a predetermined threshold value L (>0), namely, when

it is considered that a.sub.ij =b.sub.ij. The average position A.sub.ij ((Xa+Xb)/2, (Ya+Yb)/2) is decided as intersection coordinates in the table (step 206). In this instance, a check is made to see if the peak positions exist in both of the areas (whether the position coordinates .apprxeq.0) or not (step 207). For the area in which no peak position (position coordinates =0) exists in one of the two areas, there is no intersection. Therefore, 0 is substituted to A.sub.ij (step 209). For the area having an intersection, A.sub.ij (X, Y) is stored in the memory unit 103 (step 208).

FIG. 5 shows examples of the intersection coordinates A11 to A54 obtained as mentioned above. The obtained intersection coordinates are stored in the memory unit 103 as data of the table area A. Subsequently, the small number in the column in the obtained intersection coordinates A.sub.ij is used as a reference, as shown in FIG. 5. Adjacent points in the horizontal and vertical directions, for example, the smallest A11 in the first column, are A12 and A51. (Since points A21 to A41 have no intersection and thus are stored as 0, they are ignored.) Therefore, a rectangle surrounded by the intersections A11, A12, and A51 is set to one cell area C1 in the table. Since A51 of the first column indicates the final point, the cell area is determined by setting the area surrounded by A14 and A22 as cell area C2, using A12 of the second column as a reference. The area surrounded by A23 and A32 is set as cell area C3, . . . (step 210). These cell areas are stored in the memory unit 103 along with the intersection coordinate data and the cell numbers.

Processes with respect to tables which are not closed as shown in FIGS. 6A and 6B, will now be described.

In an actual document image, not only the closed table shown in FIG. 3 but also many deformed tables exist. Typical examples are shown in FIGS. 6A and 6B.

In FIG. 6A, histograms are obtained by projecting in the horizontal and vertical directions for a table area B. Coordinates and widths of peaks are obtained as (a.sub.1, Wa.sub.1), (a.sub.2, Wa.sub.2), (a.sub.3, Wa.sub.3), . . . in the vertical direction and as (b.sub.1, Wb.sub.1), (b.sub.2, Wb.sub.2), (b.sub.3, Wb.sub.3) . . . in the horizontal direction in a manner similar to the processes of the table in FIG. 3 (steps 201 and 202). A distance S between the first peak positions a.sub.1 and b.sub.1 in each of the horizontal and vertical directions is calculated. When the resultant value is smaller than a threshold value S (>0), it is regarded that the peak positions a.sub.1 and b.sub.1 are the same point. That is, at that time point, it is determined that there is a corner in the table. If there is no corner in the table, it is determined that the table is deformed. To judge more precisely, it is necessary to check for the presence or absence of a corner at all four corners (steps 211 and 212).

When it is determined that the table is deformed (step 214), corners C11, C14, C41, and C44 are obtained from the start points and final points (Ps, Pe, Qs, and Qe in FIG. 6A) of the histograms in the vertical and horizontal directions as shown in FIG. 7 and an imaginary frame as shown by a broken line is set (step 215). Then, in a manner similar to the above embodiment, C11, a12, a13, and C14 are used as references in the horizontal direction, and C11, b21, b31, and C41 are used as references in the vertical direction. Each histogram is obtained as a band having a proper width M calculated from the line width, and average intersection coordinates C.sub.ij are obtained. In the case of a deformed table, C1 to C44 are used as coordinates of the corner and, when a partner for obtaining the average does not exist at a point of the outer frame, a1 or b1 is substituted as an average intersection. In a manner similar to that mentioned above, the range surrounded by neighboring points in the horizontal and vertical directions is sequentially determined as a cell area in accordance with the small column from C11.

FIG. 8 shows a flowchart of the processes for designating a cell area by extracting the pattern from the intersection by the table cell designator 106 and comparing it with the dictionary.

Generally, in a table constructed of horizontal, vertical, and diagonal lines, the number of kinds of intersection patterns are limited. The size of a pattern extracted at the intersection is determined on the basis of the obtained average line width W (803). As shown in FIGS. 9A to 9S, several intersection patterns are formed at a size of d.times.g dots with respect to the intersection pattern forming information stored in the intersection pattern dictionary in the memory unit 103 (804). Subsequently, the intersection coordinates positions C.sub.ij (i=1, 2, 3, . . . as row, j=1, 2, 3, . . . as column; refer to FIG. 11) predicted by the peak positions a and b in the horizontal and vertical directions stored in the memory unit 103 are calculated. The obtained intersections are used as reference points and the intersection pattern of d.times.g dots is extracted from the image data and compared with the intersection pattern dictionary (in step 805). Specifically, as shown in FIGS. 10A to 10C, the inclusive OR is obtained for like positions of the intersection pattern dictionary (FIG. 10A) and the actual intersection pattern (FIG. 10B). The number of total dots is divided by the number of black pixels which finally remain in d.times.g dots, thereby obtaining an overlap degree D. That is, ##EQU1## For one intersection pattern, a comparison is made with the dictionary patterns and the pattern of largest overlap degree is set to the intersection pattern (806). The cell area in the table is now determined by using the intersection coordinates and the intersection pattern determined so far.

First, the intersection pattern of the neighboring points in the horizontal direction is sequentially observed using the small column as a reference (807). When the pattern actually has an intersection, the point is used as a reference and the neighboring points in the vertical direction are subsequently observed. (The pattern having the intersection is shown in FIGS. 9A to 9P.) A check is made to determine whether or not the intersection pattern at the point corresponding to the diagonal point, when it is seen from the first point, can be the intersection pattern at the diagonal point of the intersection pattern at the initial point (809). That is, when the intersection pattern at the initial point is determined, the diagonal pattern on the diagonal line is unconditionally determined. For example, the pattern of FIG. 9F can exist as a diagonal pattern for FIG. 9A; however, the pattern of FIG. 9E cannot. Such information is stored in the memory unit and judged.

An actual example will now be explained with reference to FIG. 11. First, the intersection pattern of point C12 in the horizontal direction is observed using C11 as a reference. From such an intersection pattern, neighboring point C22 in the vertical direction is seen. Since this can be the intersection pattern at the initial point C11, the area enclosed by C11, C12, and C22 is set to one cell area (811). Subsequently, adjacent point C22 in the horizontal direction is seen using C21 as a reference. Since it includes the intersection, adjacent point C32 in the vertical direction is seen. However, since C32 cannot be the intersection pattern on the diagonal line of initial point C21, point C32 is ignored and point C42 follows (810). Since the pattern at this point can be the intersection pattern for C21, the area enclosed by C21, C22, and C42 is set to one cell area.

Thus far, the processes have been executed up to the final fourth row. Therefore, C12 of the second column will be subsequently used as a reference. No intersection is included in the intersection pattern of adjacent point C13 in the horizontal direction for C12 (808), so point C13 is ignored and the process advances to the next point C14. Since an intersection is included in point C14, adjacent point C24 in the vertical direction from point C14 is seen. Since point C24 can be an intersection pattern on the diagonal line of C12, the area enclosed by C12, C14, and C22 is set to a cell area. In a manner similar to the above method, the area enclosed by C22, C23 and C33, the area enclosed by C32, C33, and C43, etc. are sequentially designated as cell areas. The cell areas determined as mentioned above are stored in the memory unit 103 with the intersection coordinates data and the sequentially determined cell management numbers.

Processes for obtaining the cell areas in deformed tables as shown in FIGS. 6A and 6B will now be described. In FIG. 7, histograms are first formed by projecting in the horizontal and vertical directions for table area B and the coordinates and widths of the peaks are obtained as (a.sub.1, Wa.sub.1), (a.sub.2, Wa.sub.2), (a.sub.3 .sub.1, Wa.sub.3), . . . in the vertical direction and (b.sub.1, Wb.sub.1), (b.sub.2, Wb.sub.2), (b.sub.3, Wb.sub.3), . . . in the horizontal direction in a manner similar to that mentioned above (201, 202). The distance a between the first peak positions a.sub.1 and b.sub.1 is calculated. When the value of S is equal to or less than the threshold value S (>0), it is regarded that those positions are located at the same point. That is, it is judged such that there is a corner in this table. If no corner exists in this table, it is judged that the table is a deformed table. When judging more precisely, it will be understood that it is necessary to discriminate the presence or absence of four corners (811, 812).

By checking the corners in a manner similar to the processing steps (211, 212) in the flowchart of FIG. 2, when the table is deformed (214), the corners C11, C14, C41, and C44 are obtained as shown in FIG. 12 from the initial and end points (Ps, Pe, Qs, Qe in FIG. 6A) of the histograms in the vertical and horizontal directions. An imaginary frame as shown by broken lines is set (816). Then, in a manner similar to the foregoing embodiment, C11, a.sub.1, a.sub.1, and C14 are used as references in the horizontal direction, C11, b.sub.1, b.sub.1, and C41 are used as references in the vertical direction, and the position of the intersection coordinates is obtained by the calculations. The pattern of d.times.g dots while setting the points as centers is compared with the intersection pattern dictionaries, thereby finding the actual intersection pattern. On the basis of the actual intersection pattern, the cell area in the table is designated. In order to designate the cell areas in the table while also including the deformed tables as shown in FIGS. 6A and 6B, intersection patterns as shown in FIGS. 13A to 13D must be further formed and added to the intersection pattern dictionary.

The procedure for normalizing the pattern extracted from the intersections by the table cell designator 106 will be explained with reference to the flowchart of FIG. 14.

The intersection coordinates positions C.sub.ij (i=1, 2, 3, . . . as a row, j=1, 2, 3, . . . as a column; refer to FIG. 11) predicted by the peak positions a and b in the horizontal and vertical directions are calculated. The intersection is used as a reference point and the intersection pattern of d.times.g dots is extracted. To compare the extracted intersection pattern with the dictionary, d.times.g dots are normalized to the size of D.times.G dots by the normalizer 108 (404). Subsequently, a feature vector is obtained by the feature extractor 109 (405). Various kinds of well-known methods have been proposed as a feature extracting method. In this case, a method is used whereby a direction index histogram in the N direction is obtained for the outline of an original image extracted and this is used as a feature vector. Finally, the distances between the above feature vector and the feature vectors in the intersection pattern dictionary are calculated by the pattern identifier 110. The smallest distance is determined as an intersection pattern of the point (406 to 407). The following equation is used to calculate the distances.

d=.SIGMA.(X.sub.i -M.sub.i).sup.2

n: the number of dimensions

X.sub.i : input vector

M.sub.i : study vector

A method of obtaining cell areas by using the intersection coordinates C.sub.ij and the obtained intersection patterns will now be described. First, the column is used as a reference and intersection patterns of the neighboring points in the horizontal direction are seen in accordance with the order from the small column (408). When the pattern has an intersection, the point is used as a reference and the neighboring point in the vertical direction is seen. (The pattern having the intersection denotes a pattern on which an intersection actually exists, as shown in FIGS. 9A to 9P.) A check is made to determine whether or not the intersection pattern at this point, corresponding to the diagonal point as seen from the first point, can be the intersection pattern at the diagonal point of the intersection pattern at the initial point. That is, when the intersection pattern at the initial point is determined, the intersection pattern on the diagonal line is unconditionally limited. For instance, although the pattern of FIG. 9F can exist as a diagonal pattern for the pattern of FIG. 9A, the pattern of FIG. 9E cannot so exist. Such information is stored in the intersection pattern dictionary and judged.

An actual example will now be described with reference to FIG. 11. First, the intersection pattern of point C12, neighboring in the horizontal direction, is seen using C11 as a reference. Since such an intersection pattern is a pattern having an intersection, adjacent point C22 in the vertical direction is seen subsequently from that point. Since such an intersection pattern can be the intersection pattern of initial point C11, the area enclosed by C11, C12, and C22 is set to one cell area (412). Adjacent point C22 in the horizontal direction is seen using C21 as a reference. Since the point includes the intersection, the process advances to the next point C32 in the vertical direction from point C22. However, since the point C32 cannot be the intersection pattern on the diagonal line of the intersection pattern at initial point C21, point C32 is ignored and the process advances to the next point C42 (411). Since C42 can be the intersection pattern for C21, the area enclosed by C21, C22, and C42 is set to one cell area.

Processes have been performed up to the final fourth line in this manner. Therefore, C12 of the second column is used as a reference. No intersection is included in the intersection pattern of adjacent point C13 in the horizontal direction for C12. Therefore, C13 is ignored and the process advances to further adjacent point C14 (409). Since an intersection is included in point C14, adjacent point C24 in the vertical direction is seen from point C14 (409). Since point C24 can be the intersection pattern on the diagonal line of C12, the area enclosed by C12, C14, and C24 is set to a cell area. In a manner similar to the above, the area enclosed by C22, C23, and C33, the area enclosed by C32, C33, and C43, etc. are sequentially designated as cell areas.