JPH0877294A - Image processor for document - Google Patents

Abstract

PURPOSE: To provide the document image processor which can accurately specify the document format of a document, etc., and efficiently extract and read a character string. CONSTITUTION: Figure feature quantities extracted by a feature extraction part 12 from an input image of the document generated by an image input part 11 are grouped by a feature structuring part 13, and the relation of the respective features is extracted and managed. The kind of the format structure of the input document is estimated by using the structured features and information (format structure model) regarding the format structure of a document to be processed which is previously registered in a format structure kind identification part 15. A format structure information collation part 16 extracts detailed correspondence relation between the format structure model corresponding to the estimated kind of the format structure and the structured features of the input document. After noncorrespondence and contradict correspondence finding and correction part 18 obtains the matching of the correspondence relation, a document structure acquisition part 19 copies information regarding the previously registered document structure model to the input document on the basis of the correspondence relation to acquire the structure and relative knowledge of the input document.

Description

Detailed Description of the Invention

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to a document image processing apparatus used for reading characters written on a document such as a form, automatically inputting into a database, and automatic filing of form images.

[0002]

2. Description of the Related Art In recent years, documents that have been managed and used in the form of documents are digitized and input to a computer, and are used for various purposes. Many documents used in various business processes are in tabular form, and I want to efficiently input and manage the desired character string written in a specific position in the document in the desired format on the computer. The demand is increasing. In order to meet these expectations, optical character reading devices have been developed and put into practical use.

When reading a character string written in a specific position on such a form, it is necessary to know the format structure of the form in advance. In the process of reading a character string for a document having a standard format structure such as a form, the format structure is memorized in advance, and the character string area is efficiently specified and read based on the stored structure structure.

According to such an approach, the expandability to the versatility of the format structure is enhanced by separating the knowledge about the format structure of the target document and the process using it. These items use physical information of the document structure as knowledge about the format structure, for example, information such as position, size, and geometrical relationship. As a typical research, reference is made to the literature “Shingaku theory (D), J71-D, 10, pp.2050-2058 (1988-1).
0) ”and the literature“ Shingaku Theory (D-II), J72-D-II, 7, p.
p.1029-1039 (1989-07) ”.

On the other hand, recently, it has been considered to make it possible to specify a character string area even for a form that cannot be handled only by using physical information regarding the document structure. In this case, the character area can be expressed and identified by logical information based on the spatial adjacency / connection relationship.

In order to take such an approach, the format rule of the target document image is recognized by using the one expressed as meta-knowledge by generalizing the configuration rules regarding the format structure of various form documents. As a typical research, the literature “Biological theory (D-II), J76-D-II, 3, pp.534-545 (1)
993-03) ”.

[0007]

[Problems to be Solved by the Invention] The literature "Dieology (D),
J71-D, 10, pp. 2050-2058 (1988-10) "and the literature," Theoretical theory (D-II), J72-D-II, 7, pp.1029-1039 (1989-).
The method such as "07)" cannot be applied when the document is input with a large deviation or undergoes scale conversion due to enlargement / reduction because it relies on physical information. In addition, the literature, “Sociology (D-II), J76-D-
II, 3, pp.534-545 (1993-03) ”, it is assumed that the input document is of high quality and there is no deterioration of the image. If the information is insufficient, there is a problem that the desired processing result cannot be obtained.

Further, any of the methods has the following problems (1) to (6).

(1) It is not possible to deal with the case where a plurality of tables are mixed.

(2) If the table is divided, it cannot be dealt with.

(3) If the ruled line is faint or missing, it cannot be dealt with.

(4) It is not possible to deal with the case where the ruled line distribution locally changes.

(5) The processing method of the input document is limited (it cannot support documents rotated 90 degrees and 180 degrees to the left and right).

(6) When documents of various format structures are read collectively, the format structure model to be applied cannot be automatically identified.

The present invention has been made in view of the above circumstances, and provides a document image processing apparatus capable of accurately recognizing a format structure of a tabular form or the like and efficiently specifying a character string area. The purpose is to

[0016]

SUMMARY OF THE INVENTION According to the present invention, an image input means for generating an input image from a document and an information regarding the format structure of a processing target document used for recognizing the format structure of the input document are registered. , Generates information about the format structure of an upright document to be processed at multiple predetermined angles, gives information about how many times it is rotated from the upright document, and processes all of them. Form structure information registration means for registering as information about the format structure of the document, and graphic features regarding line segments and character components are extracted from the input image generated by the image input means, and further extracted from areas other than the character components in the input image. Feature extraction means for extracting the features related to the line segment as the graphic features forming the ruled lines, and the graphic feature related to the ruled lines extracted by the feature extraction means. Feature structuring means for extracting features related to a table by grouping, extracting information about a joint portion at a portion where ruled lines intersect / connect in the features related to each table, and extracting / managing a relationship between the features. And calculating the similarity using the structured image features of the input image obtained by the feature structuring means and the information about the format structure of the processing target document registered in advance by the format structure information registration means. Then, a plurality of format structure models or a format structure model having a similarity of a certain value or more are selected in order from the format structure model having the highest similarity or the one having the highest similarity, and the type of the format structure of the input document is set to one. Format structure type identifying means for narrowing down to one or a plurality of candidates, features relating to the table of the input document obtained by the feature structuring means, and the format structure Correspondence between the table obtained by the table collating means and the table collating means for performing the collating process with the features relating to the tables constituting the format structure model registered by the information registering means to obtain the inter-table correspondence relationship. In the relation, ruled line collating means for acquiring the correspondence between the ruled lines forming the table of the input document and the ruled lines forming the table of the format structure model corresponding to the ruled line, and the correspondence between the features based on the result of the collation processing. Of the structured structure document selected by the model matching means, and a model matching means configured by a matching result determining means for calculating a matching degree indicating the degree of matching and determining whether or not correct matching is performed. In the correspondence between the structured features in the input document and the input document, the formal structure model and the input document are matched by eliminating incomplete correspondence and inconsistent correspondence. Uncorrespondence that acquires the correspondence between the structured features of
When the format structure model associated with the input image by the contradiction correspondence finding and correction means and the model matching means is rotated by a predetermined angle, the input image is rotated in a direction in which the rotation angle is erect, Based on the correspondence between the image rotation means associated with the upright format model and the structured features of the format structure model and the input document, information on the previously registered format structure model is copied to the input document. The document structure acquisition means for acquiring the format structure and the related information of the input document is provided, and the format structure of the input image is recognized based on the result obtained by the document structure acquisition means.

[0017]

As a result, according to the present invention, the feature amount of the ruled line and the feature amount of the character component related to the ruled line are extracted from the input document image, and the feature amount of the ruled line can be accurately extracted in the area other than the character component based on the relation between them. Also, by grouping these ruled line features, the feature amount related to the table can be obtained,
Furthermore, in each table, the features related to ruled lines and their intersections
It is possible to add more abundant information to the graphic feature amount by extracting the joint portion generated by the joint and describing and managing the joint portion by the whole-part relation. You can search them efficiently. As a result, even if a plurality of tables are mixed in the document, the respective information can be extracted, and the characteristics regarding ruled lines can be distinguished for each table.

According to the present invention, the input document is interpreted by performing the matching process between the structured feature obtained from the input image and the structured feature of the format structure model registered in advance. By identifying the type of the format structure model before, it is possible to avoid performing the matching process with all the registered format structure models. In this process, since the number of joints and the number of ruled lines included in the document are used, scale conversion is performed between the input document and the format structure model due to scaling, or the components of tables and ruled lines are used. It is possible to obtain a stable result even if the size of is partially varied. The identification error is prevented by outputting a plurality of candidates instead of outputting a single result when identifying the type of the format structure model. In the matching process performed between the structured features of the candidate format structure model and the structured features of the input document, the format structure model with the best correspondence can be selected, and the obtained correspondence relationship can be acquired correctly. The reliability of the processing result is improved by determining whether or not the processing result is obtained. At this time, the collating process is first performed for each table and then for each ruled line. As a result, even if a ruled line having exactly the same local feature amount locally belongs to a different ruled line, incorrect association is not performed.

Further, in the present invention, the presence or absence of incomplete correspondence or inconsistent correspondence due to the lack of one of the structured features in the correspondence relation and this portion are found and solved. As a result, a matching correspondence can be obtained, and a stable processing result can be obtained. The document structure of the input document can be acquired by copying the information related to the pre-registered format structure model based on this correspondence to the input document, and the position where the character string to be read can be accurately specified. .

[0020]

An embodiment of the present invention will be described below with reference to the drawings. FIG. 1 is a block diagram showing the schematic arrangement of an image processing apparatus according to this embodiment.

The present invention includes an image input unit 11 and a feature extraction unit 1.
2, feature structuring unit 13, form structure information registration unit 14, form structure type identifying unit 15, form structure information collating unit 16, uncorrespondence / contradiction correspondence finding and correcting unit 17, collation result judging unit 18, and document structure acquiring unit. It is composed of 19 functional units.

Further, it is assumed that the form to be processed has a character string area defined by ruled lines as shown in FIG.

The image input unit 11 is composed of a scanner device, a TV camera, a FAX data input unit, and the like. The image input unit 11 detects an image of a document such as a form to be processed and takes it into the system. The image (input image) input by the image input unit 11 is sent to the feature extraction unit 12.

The feature extraction unit 12 extracts, from the input image obtained from the image input unit 11, geometrical figure feature amounts regarding ruled lines and character components as basic features. The set of basic features extracted by the feature extraction unit 12 is sent to the feature structuring unit 13.

The feature structuring unit 13 is a table obtained by, for example, grouping features related to ruled lines in the set of basic features extracted by the feature extraction unit 12, and a joint portion generated at a portion where ruled lines intersect / connect. Information related to etc. is extracted as a structured feature, and the relationship between each feature is described and managed.

The format structure information registration unit 14 registers knowledge about the document to be processed by interactive input work between the system and the operator. In the present embodiment, the total of various knowledge prepared for each type of document to be processed is called a model, and the document used when the model is defined is called a model document. The model has, for example, information about the structured features of the model document.

At this time, the format structure information registration unit 14 rotates the structure feature standing upright by 90 degrees to the right,
Generates three types of structured features, one rotated 90 degrees to the left and one rotated 180 degrees, and added as information about how many times each of them has been rotated from an upright one and stored as a knowledge base. You may.

In addition to this, for example, when a character string included in an area defined by a ruled line is to be recognized and coded by a character recognition device, various kinds of information are registered as a knowledge base in association with structured features.・ It may be managed.

The various information includes, for example, information relating to designation of the character recognition target area, information on the character string direction of the character recognition target area, character type information and writing form information which acts as a constraint condition at the time of character reading processing, and post-character recognition processing. There is information such as item attribute information and a correspondence relationship between character recognition results.

The format structure type identifying unit 15 includes a structured feature for the input image extracted by the feature structuring unit 13 and each structured feature of the model document registered in advance by the format structure information registration unit 14. In between, the type of format of the input document is identified by performing similarity calculation. That is, it is determined that the model format having a high similarity value is highly likely to be the input document format. The format structure type identifying unit 15 outputs the corresponding structured feature to the format structure information matching unit 16 in the next stage.

It should be noted that the format structure type identifying unit 15 does not focus only on the model having the highest similarity value, for example, for all model documents showing a similarity value equal to or higher than a certain predetermined threshold value. The structured feature may be sent to the format structure information matching unit 16 together with the input structured feature as a candidate.

The format structure information collating unit 16 acquires the correspondence relation between the structured features between all the model documents and the input documents which are candidates by the format structure type identifying unit 15. Further, the format structure information matching unit 16 calculates a scale (hereinafter, referred to as a matching degree) indicating the degree of correspondence with the correspondence result between the structured feature of the input document and the structured feature of each model document. . The format structure information matching unit 16 outputs the information indicating the correspondence between the structured features and the information indicating the matching degree to the matching result determination unit 17.

When the structured features of a plurality of model documents are sent from the format structure type identifying unit 15, the format structure information matching unit 16 further selects and outputs the model document showing the maximum matching degree. It may be like this.

Based on the information obtained by the format structure information matching unit 16, the matching result judging unit 17 judges whether or not there is a correspondence between the document model showing the maximum matching degree and the input document. . If it is determined that the correspondence is established, the information about the correspondence between the input document of interest and the model document is sent to the uncorresponding / contradiction correspondence finding / correcting unit 18 in the subsequent stage. When it is considered that the correspondence is not established, the input document is rejected and the operator is urged to input the next document.

The non-correspondence / contradiction correspondence finding / correction unit 18 extracts an erroneous feature in the correspondence relation between the structured feature of the input document and the structured feature of the model document acquired by the format structure information collation unit 16 and extracts a necessary feature. Discover whether incomplete or inconsistent correspondences occur due to missing features. Not compatible·
When the inconsistent correspondence finding / correcting unit 18 finds an incomplete correspondence or an inconsistent correspondence, the inconsistent correspondence finding / correcting unit 18 eliminates them to obtain a matching correspondence between the input and the model, and
It is output to the document structure acquisition unit 19.

The document structure acquisition unit 19 preliminarily uses the format structure information registration unit based on the correspondence between the structured features of the matched input document and the model document obtained by the uncorrespondence / contradiction correspondence finding / correction unit 18. The document structure of the input document and the related knowledge are acquired by copying the knowledge about the model document registered in 14 to the input document.

Next, a specific document image processing system including the above-mentioned essential components will be described. here,
As shown in FIG. 3, a document image processing system combined with a character recognition device will be described. This system automatically extracts the character string area described at a specific position in the input image obtained from the input document, recognizes and codes the character string image, and outputs it in the desired output format. It is the action of doing. Hereinafter, description will be made using the document shown in FIG. 2 (hereinafter, the document of FIG. 2 is referred to as an input document unless otherwise specified).

As shown in FIG. 3, the document image processing system includes an image input section 21, a binarization processing section 23, and a preprocessing section 2.
5, feature extraction unit 27, feature structuring unit 29, model registration unit 31, font type identification unit 33, model collation unit 35, collation result determination unit 37, uncorresponding contradiction correspondence finding and correction unit 39, document structure acquisition unit 41, The character string area extraction unit 43, the character recognition unit 45, and the character recognition result output unit 47 are included.

The image input section 21 is the same as the image input section 11 described with reference to FIG.

The binarization processing unit 23 converts the document image fetched from the image input unit 23 into binary image data of white and black by a known binarization process, and outputs it to the preprocessing unit 25. To do.

The pre-processing unit 25 processes the binary image output from the binarization processing unit 23, for example, in the literature “Science Technical Report, P.
RU92-32, 1992 ”, the image is converted into a binary image having no inclination by the inclination detection / correction processing. Further, the preprocessing unit 25 generates a circumscribing rectangular frame surrounding a group of black pixels to be connected to the binary image whose inclination has been corrected by a known black connected component extraction process, and determines its size (vertical length). (Width and width) and position coordinate values are extracted and managed,
The result is output to the feature extraction unit 27.

The position coordinates of the input document are defined such that the upper left corner is the origin, the x coordinate value gradually increases in the right direction, and the y coordinate value gradually increases in the downward direction. All the document images touched in this embodiment are defined in this coordinate system. Of these, the width and height are smaller than the dynamically detected thresholds th1 and th2, respectively.
In addition, it is also possible to remove those that are separated from the other nearest black connected component rectangle by a distance th3 or more as noise or halftone dots.

After that, the document image input from the image input unit 21 is binarized by the binarization processing unit 23.
An image obtained by performing the preprocessing in the preprocessing unit 25 is called an input document image or simply an input image. The input image is sent to the feature extraction unit 27. The feature extraction unit 27 extracts geometrical graphic features from the input image obtained from the preprocessing unit 25. As shown in FIG. The extraction unit 27a, the character candidate rectangle extraction unit 27b, and the ruled line feature extraction unit 27c are configured. The feature extraction unit 27 extracts geometrical graphic features by the following procedure.

First, the line segment extraction unit 27a extracts a line segment from the input image based on the procedure described below, for example.
At this time, the line segment extraction process may be performed only in two directions, that is, the vertical direction and the horizontal direction. As a specific example, a case of extracting a line segment in the vertical direction will be described. Note that line segments in the horizontal direction can also be extracted by the same procedure.

Step 1: A document image is sequentially scanned in the vertical direction, and a series of consecutive black pixels (BL ==) having a predetermined length of, for example, 3 dots or more is scanned in each scanning line.
{Bli | i = 1, 2, ..., N}) is extracted.

Step 2: Of the elements of BL, those that are adjacent in the horizontal direction are integrated and put together, and the set (BLG = {blgj | j = 1, 2, ...
M}) is extracted.

Step3: B included in each element of BLG
In L, a series of black pixels that are longest in the vertical direction blma
x is extracted, and its length blmax is α (for example, α = 0.
3) Delete bli with length less than double.

Step 4: A rectangle inscribed in the remaining bli is extracted and its set (RL = {rlk | k = 1, 2,
, P}) (at this time, rlk and bli that compose it are correlated with each other). The y coordinate values of the upper left corner and the lower right corner of rlk are detected, and rlk y1, respectively.
Let rlk y2.

Step 5: Each element of RL is sequentially scanned in the horizontal direction (from left to right), and the x coordinate (xis) of bli that first appears in each scanning line and the b that appears last in bli.
Hold the x coordinate (xie) of li.

Step 6: The average value r of the collection of xis and the collection of eie obtained in each horizontal scanning line of each rlk.
lk x1 and rlk x2 are calculated respectively.

Step 7: The coordinates of the upper left corner and the lower right corner of each rlk are (rlk x1, rlk y1) and (r
lk x2, rlk y2) and extract it as a line segment.

FIG. 5 shows an example of the line segment extracted from the input image by the line segment extraction unit 27a. As shown in FIG. 5, at this stage, short line segments forming a character are detected in the character portion. The following processing may be performed to remove these. That is, the line segment extraction unit 27a
Before or after the line segment extraction processing by, the character candidate rectangle extraction unit 27b uses the procedure described below to determine a black connected component that can be regarded as a character (hereinafter referred to as a character candidate rectangle). Call).

Step 1: A rectangle inscribed in each black connected component is extracted, and its vertical width ch and horizontal width cw are obtained.

Step 2: The appearance frequency is calculated for each value of ch and cw, and the mode value is extracted. The ch indicating the mode value is the average character height (CH) of the characters in the input document, and the cw indicating the mode value is the average character width (C) of the character in the input document.
W).

Step 3: (CW-th) ≤cw≤ (C
W + th) and (CH-th) ≦ ch ≦ (CH + th)
Black connected components that satisfy the above are extracted as character candidate rectangles.

An example of the extraction result of the character candidate rectangles extracted by the character candidate rectangle extraction unit 27b is shown in FIG. 6 (an example in which the character portion is surrounded by an outer frame rectangle).

The character candidate rectangle extraction process is performed before the line segment extraction process, and the filtering process described below is performed in both the vertical direction and the horizontal direction with respect to the portion other than the obtained character candidate rectangle on the input image. May be applied to stabilize the line segment extraction processing result even when the ruled line is faint or broken.

In this case, the feature extraction unit 27 is constructed as shown in FIG. That is, the character candidate rectangle extraction unit 27
The processing result of b is output to the filtering processing unit 27d and subjected to filtering processing. Then, after the filtering process, the line segment extracting process is executed by the line segment extracting unit 27a.

The filtering process by the filtering process unit 27d is realized by, for example, a process of replacing all continuous white pixels within a predetermined length on a horizontal (vertical) scanning line in a binary image with black pixels. . As a result, the ruled line portion having faintness or discontinuity is corrected, so that the line segment extraction processing result is stabilized.

The ruled line feature extraction unit 27c is a line segment extraction unit 27.
In the line segment group extracted by a, line segments that intersect or are included in the character candidate rectangle as shown in FIG. 8 are removed, and the remaining line segments are extracted as ruled line features.

At this point, each ruled line feature is represented by various information such as the position coordinates of the upper left and lower right edges of the circumscribing rectangle surrounding the image in the input image, and the vertical and horizontal widths of the circumscribing rectangle. Good. In addition, a ruled line feature “corresponding ruled line feature identification number” may be prepared, and the corresponding partner identification number may be stored in the matching process performed by the model matching unit 35 in the subsequent stage. Good.

The obtained set of ruled line features is further classified into two types of horizontal ruled lines and vertical ruled lines, and the set of horizontal ruled line features and the number of elements thereof, and the set of vertical ruled line features and the number of elements thereof are extracted.

FIG. 9 shows an example of ruled line feature extraction results for the input image. Here, IHL = (ihl ₁ , ihl ₂ , ihl ₃ , ihl ₄ , ihl ₄ , ihl ₄ , ihl ₄ , ihl ₄ , ihl ₄ , ihl ₄ , ihl ₄ , ihl ₄ , ihl ₄ , ihl ₄ , ihl ₄ , ihl ₄ , ihl ₄ , ihl ₄ , ihl ₄ ,
ihl ₅ , ihl ₆ , ihl ₇ ), IVL = (ivl ₁ , ivl ₂ , ivl ₃ , ivl ₄ ,
(ivl ₅ , ivl ₆ , ivl ₇ , ivl ₈ , ivl ₉ ) are assigned identification numbers.

The number of elements of the horizontal ruled line feature set is ih-n.
um and the number of elements of the vertical ruled line feature set are iv-num, and the horizontal ruled line feature set and the vertical ruled line feature set are collectively referred to as an input ruled line feature set. The input ruled line feature set is sent to the subsequent feature structuring unit 29. In the following description, the above symbols will be used.

The feature structuring unit 29 extracts structured features relating to ruled lines from the input ruled line feature set obtained from the feature extracting unit 27 by the procedure described below. As shown in FIG. 10, ruled line grouping processing is performed. Unit 29a, table feature extraction unit 29
b, the ruled line joint detection unit 29c, and the inter-feature relationship description unit 2
It is composed of 9d.

First, the ruled line grouping processing unit 29a groups the ruled line features intersecting / connecting into one group. The ruled line grouping processing algorithm is as follows, for example. This algorithm groups ruled lines by giving the same label to the ruled lines that intersect and connect.

Step 1: Initialize the label number.

Step 2: Select one vertical ruled line.

Step 3: All horizontal ruled lines orthogonal to the vertical ruled line selected in step 2 are extracted.

Step 4: If a label is already attached to either the vertical ruled line or the horizontal ruled line, the minimum value label is given to all of the ruled lines.

Step 5: If no label is given to either the vertical ruled line or the horizontal ruled line, new label numbers are given to all of them and the label numbers are updated.

Step 6: Steps 2 to 5 are applied to all vertical ruled lines. (Step 2 to Step
6 is the procedure A) Step 7: Select one horizontal ruled line.

Step 8: Extract all vertical ruled lines orthogonal to the horizontal ruled line.

Step 9: When a label is already attached to either the horizontal ruled line or the vertical ruled line, the minimum value label is given to all the ruled lines.

Step 10: If no label is given to either the vertical ruled line or the horizontal ruled line, new label numbers are given to all of them and the label numbers are updated.

Step11: Apply Step7 to Step10 to all vertical ruled lines (Step7 to St)
(Procedure B is up to ep11).

Step 12: Procedures A and B are repeated until the label number is no longer updated.

Step 13: The ruled line features having the same label are grouped.

For example, when the above-described grouping process is applied to the input ruled line feature set shown in FIG. 9, the following two groups are obtained.

Group1: (ihl ₁ , ihl ₂ , ihl
₃ , ihl ₄ , ihl ₅ , ivl ₁ , ivl ₂ , ivl
₃ , ivl ₄ , ivl ₅ , ivl ₆ ), Group2: (ihl6, ihl7, ivl7, ivl8)
, Ivl9) The table feature extraction unit 29b extracts, for each group obtained by the ruled line grouping processing unit 29a, a rectangle (hereinafter referred to as a table frame) inscribed with the ruled lines included in the group. Further, the table feature extraction unit 29b, as the table feature, for example, the position coordinates of the upper left corner, the position coordinates of the lower right corner, the vertical width of the table, the horizontal width of the table, the positional coordinates of the center of gravity, the number of horizontal ruled lines, the horizontal included in the table. A set of ruled lines, the number of vertical ruled lines, a set of vertical ruled lines included in the table, the number of joints included in the table, and information about whether or not the table is inscribed in another table are extracted. At this time, the horizontal (vertical) ruled line features may be sorted in ascending order of the y (x) coordinate values at the upper left end thereof.

Here, the number of joints is extracted by the ruled line joint detector 29c in the subsequent stage and stored as a table feature. For example, the following table feature it ₁ is obtained from Group1 as shown in FIG. Also, the table feature obtained from Group2 is set to it2.

Table features: it ₁ top left position coordinates (it ₁ x1, it ₁ y1) bottom right position coordinates (it ₁ x2, it ₁ y2) table vertical width it ₁ height table width it ₁ width centroid Position coordinates (it ₁ cx, it ₁ cy) Number of horizontal ruled lines ihl ₁ num Set of horizontal ruled lines included in the table IHL ₁ Number of vertical ruled lines ivl ₁ num Set of vertical ruled lines included in the table IVL ₁ Included in the table Number of joints i ₁ junc-num Information on whether or not it is inscribed in another table nest flag it ₁ height = it ₁ y2 −it ₁ y1 +1, it ₁ width = it ₁ x2 −it ₁ x1 +1, it ₁ cx = (it ₁ x1 + it ₁ x2) / 2, it ₁ cy = (it ₁ y1 + it ₁ y2) / 2, ihl ₁ num = 5, IHL ₁ = (ihl ₁ , ihl ₂ , ihl ₃ , ih
l ₄ , ihl ₅ ), ivl ₁ num = 6, IVL ₁ = (ivl ₁ , ivl ₂ , ivl ₃ , iv
l ₄ , ivl ₅ , ivl ₆ ), nest flag = 0 (that is, not included in other tables) Considering that one input form contains multiple tables, page features are further extracted. ,to manage. The page feature is defined by, for example, the number of tables, the set of table features, the number of horizontal ruled lines, the number of vertical ruled lines, and the number of joints.

For example, from the set of input ruled lines in FIG. 9, as the page feature: IP, the number of tables = 2, the set of table features IT = (it ₁ , it ₂ ), the number of horizontal ruled lines ihl-num = 7, the vertical ruled lines Number ivl-num =
9, the number of junctions ijunc-num = 28 is obtained.

Next, the ruled line joining portion detecting unit 29c finds the intersections / connections (hereinafter referred to as joining portions) of the horizontal ruled lines and vertical ruled lines contained therein in each table, and joins them according to the characteristics of each table. Manage the number of copies. Ruled line joint detection unit 29
The operation procedure of c is as follows, for example.

Step 1: Select one horizontal ruled line.

Step 2: Extract all vertical ruled lines that intersect / connect to the focused horizontal ruled line.

Step 3: The intersection between the horizontal ruled line and the vertical ruled line is obtained, and the coordinate value is managed for each horizontal ruled line.
In each horizontal ruled line, the joint features are sorted in ascending order of the x coordinate value.

Step 4: Steps 1 to 3 are executed for all horizontal ruled lines.

Step 5: Select one vertical ruled line.

Step 6: Extract all horizontal ruled lines that intersect and connect with the vertical ruled line of interest.

Step 7: The intersection of the vertical ruled line and the horizontal ruled line is obtained, and the coordinate value is managed for each vertical ruled line.
In each vertical ruled line, the joint features are sorted in ascending order of the y coordinate value.

Step 8: Steps 5 to 7 are executed for all vertical ruled lines.

For example, in the table feature it ₁ , the joint shown in FIG. 12 is obtained from the horizontal ruled line set IHL ₁ and the vertical ruled line set IVL ₂ , and the number of joints “22” is added to the table feature (i ₁ junc -num = 22).

The inter-feature relation description part 29d manages the information obtained from the above processing results in relation to each other as shown in FIG. As a result, the page features are managed by being hierarchically associated with the table features, the ruled line features, and the joining features, and the information about the features can be efficiently searched.

Hereinafter, these features will be collectively referred to as structured features. In addition, the structured features extracted from the input document are called input structured features, and the structured features extracted from the model document are called model structured features.

On the other hand, in addition to the processing on the processing target document, the model registration unit 31 interactively inputs the operator based on the sample document presented by the operator, which is an example for each type of the processing target document. The model is registered by work. Here, an example of the operation of the model registration unit 31 during the model registration work will be described.

First, the sample document to be registered is input via the image input unit 21, and the binarization processing unit 23 and the preprocessing unit 2 are input.
A document image (hereinafter referred to as a model image) is acquired via step 5. Next, the feature extraction unit 27 extracts ruled line features from the model image.

The model registration unit 31 estimates the error of the feature extraction processing with respect to the extraction result of the feature extraction unit 27 and displays a message to the effect that the error is corrected on the screen of the display of the display unit 31a. Instruct the operator to make corrections.

The error estimation method of the feature extraction processing can be realized by, for example, finding a ruled line whose end point is not a joint portion and assuming that the ruled line is not correctly extracted. The model registration unit 31 inputs, through the input unit 31b, the ruled line feature corrected on the screen by the operator according to the instruction displayed on the display unit 31a.

When the modification work is completed, the modified ruled line feature is sent to the feature structuring unit 29, and the structured feature is extracted. This structured feature is useful when processing unknown input documents.
It is used by the format type identifying unit 33, the model matching unit 35, the unsupported / contradiction correspondence finding / correction unit 39, the matching result determination unit 37, and the like.

The extracted / corrected ruled line features are displayed on the screen so as to be superimposed on the model image. The operator builds the knowledge necessary for processing the input document image to be associated with the model document while following the message output by the format structure information registration unit 31 on the screen.

As a result, the structured feature information as the model, the information regarding the designation of the character recognition target area, the information about the character string direction of the character recognition target area, the character type information serving as a constraint condition during the character reading process, the writing form information, and the character Information such as item attribute information for post-recognition processing and correspondence between character recognition results is stored in the knowledge base 31c.

Of these, structured features are created for upright images. Therefore, the model registration unit 31 generates one rotated 90 degrees to the left, one rotated 90 degrees to the right, and one rotated 180 degrees at the time of registration in the knowledge base 31c. You may make it add the information shown.

In the model collating unit 35 in the subsequent stage, the structured feature in the four directions and the input structured feature are collated with the feature in each direction and the input image, and the document direction of the input document is unknown. Also, it is possible to know the rotation angle given to the structured feature best matched by the model matching. Therefore, if the input image is rotated in the direction in which the angle is set to 0 degree, an upright input image can be obtained without fail.

The model registration unit 31 performs the above processing on all model documents. Here, as an example, FIG.
It is assumed that two types of structured features shown in FIG. 4 and FIG. 15 are registered as models (hereinafter, FIG. 14 is model 1, FIG.
Is called model 2).

The format type identifying unit 33 selects a model corresponding to (or possibly corresponding to) the input document from the models registered in advance by the model registering unit 31.

Here, the similarity is calculated between the structured features of the input document and the structured features of all the registered models, and the model with the highest similarity or the similarity of a certain value or more is calculated. The structured features of the model having the above are sent to the model matching unit 35 in the subsequent stage.

As the feature used for the similarity calculation, for example, the number of joints extracted by the feature structuring 29 included in the document is used. The number of joints is a feature that is not affected even when the unknown input document is scaled up or down, and when each table is scale-converted independently. Suitable for calculation.

Besides this, the number of horizontal ruled line features, the number of vertical ruled line features, the number of table features, etc. included in the document are also effective as features for similarity calculation. Here, it is assumed that the model documents are appropriately ordered.

The degree of similarity can be obtained as follows.
Here, the total number of models: model-num, the number of joints in the input document: ijn, the number of joints in the kth model document: mj
n _k (where 1 ≦ k ≦ model-num), the similarity between the input document and the kth model document: sim _k (where −100 ≦ s
Im _k ≦ 100), the similarity is, for example, when ijn> 0 or mjn _k > 0 sim _k = 100−200 × | ijn−mjn _k | / (ij
n + mjn _k ) ijn = 0 and mjn _k = 0, it is obtained by sim _k = −100.

Among the obtained similarities, the one having the maximum similarity or one having a preset threshold value th5 or more is sent to the model matching unit 35 as a candidate model together with the structured feature of the input document. At this time, if the similarity is less than the threshold value th5 in all models, the subsequent processing may be interrupted and the input document may be rejected. You may send it to.

For example, the registered model document is shown in FIG.
4 and FIG. 15, the similarity calculation between the input document and these two model documents is as follows. Here, the number of joints in the input document: ijn = 28, the number of joints in the model 1: mjn ₁ = 31, the number of joints in the model 2: mjn ₂ = 26
, The similarity between the input document and the model 1 is sim ₁ , the similarity between the input document and the model 2 is sim ₂ , and the threshold value is th5.
= 80.

Sim ₁ = 100−200 × | 28−31 | / (28 + 31) = 89.83 sim ₂ = 100−200 × | 28−26 | / (28 + 26) = 92.59 From the above calculation results, sim1 and sim2 are combined. Threshold
Since th5 is exceeded, both of them send their structured features to the model matching unit 35 in the subsequent stage as models that may correspond to the input document.

The model matching unit 35 structures the structured features extracted from the input document (hereinafter referred to as input structured features) and one or more model documents selected by the format structure type identifying unit. The features (hereinafter referred to as model structured features) are received, and the matching process described below is performed between them to calculate the matching degree.

The matching process is a matching process between the input structured feature and the model structured feature, and the matching degree is a scale indicating the degree of correspondence. Here, it is assumed that the model document having the highest matching degree corresponds to the input document, and information regarding the correspondence between the input structured feature and the model structured feature is sent to the matching result determination unit in the subsequent stage. . The collation result judging unit makes a final judgment as to whether or not the correspondence between the model document showing the maximum matching degree and the input document is acquired.

As shown in FIG. 13, the structured features obtained by the feature structuring unit 29 have a hierarchical relationship of whole-part extracted from page features to table features, and from table features to ruled line features. Is structured. When using this feature, the matching process is performed hierarchically. In response to this, the model matching unit 35 further, as shown in FIG.
The selection unit 35a, the table matching unit 35b, the ruled line matching unit 35c, the matching degree calculation unit 35d, and the matching result output unit 35e.

First, the selecting unit 35a selects the structured feature of one model from the structured features of a plurality of models and sends it to the table collating unit 35b together with the structured feature of the input document.

Next, the table collating unit 35b performs processing between the set of table features of the input document (hereinafter referred to as the input table feature set) and the set of table features of the model document (hereinafter referred to as the model table feature set). Correspond.

When the correspondence between the tables is established, the ruled line collating unit 35c further determines whether the ruled line features included in the table of the input document (hereinafter referred to as the input ruled line feature) and the table of the model document are included. Correspondence is performed between the included ruled line features (hereinafter referred to as model ruled line features).

When the ruled lines are matched with each other, the matching degree calculation unit 35d determines (between the input document and the model document).
Calculate the degree of matching. If neither table correspondence nor ruled line correspondence is obtained, the minimum matching degree (-10
0) is substituted.

The collation result output unit 35e selects a set of the model document and the input document showing the highest collation degree calculated up to that time, and provides information on the correspondence between the structured features in the collation result determination unit in the subsequent stage. Output to 37.

In the following, an example of the processing operation of the model collating unit 35 when the two types of models of FIGS. 14 and 15 and the structured feature of the input document are respectively sent from the format type identifying unit 33 will be described.

It is assumed that, out of the two types of models, Model 1 is selected by the selection unit 35a and the structured features thereof are sent to the table matching unit 35b together with the input document. Here, if the number of table features of the input document is it-num = 2 and the table feature set is IT, IT = (it ₁ , it ₂ ) (see FIG. 9) mt 1-num = 2 and the table feature set is MT1, MT1 = (mt1 ₁ , mt
1 ₂ ) (see FIG. 14).

As shown in FIG. 17, the table collating unit 35b further includes a compatible pair detecting unit 35b-1, a heterogeneous compatible inter-pair compatibility determining unit 35b-2, and a best matching extracting unit 35b-3. And operates as follows.

First, the available pair detection unit 35b-1
For each element of the table feature set of the model selected by the selection unit 35a, all the input table features that may be associated with it are detected and managed as a pair that can be associated. That is, Step 1: any MT to any one table feature mt _k
(Kth table feature of the table feature set of the model of interest) is selected.

Step 2: The number of joints of the table feature mt _k and I
Similarity is calculated between the number of joints of each table feature of T.

Step 3: For example, if the similarity sim _kj between mt _k and it _j (the j-th table feature of the input table feature set) is equal to or greater than a preset threshold th6, it is possible to handle it. The set (mt _k , it _j ) is held as a compatible pair.

Step4: Step3 is a table feature set IT
Applies to all elements of.

Step 5: Steps 1 to 4 are applied to all the elements of the MT of interest.

Here, the number of junctions of itj is ijn _j , m
Assuming that the number of joints of t _k is mjn _k , it is assumed that the degree of similarity is obtained by the following equation, for example.

When ijn _j > 0 or mjn _j > 0, sim _kj = 100-200 × | ijn _j −mjn _k | / (i
jn _j + mjn _k ) ijn _j = 0 and mjn _k = 0, sim _kj = −100 The above operation will be described in detail using IT and MT1 as examples. th6 = 75, number of junctions of it ₁ = 22,
Number of joints of it ₂ = 6, number of joints of mt1 ₁ = 25, mt
If the number of joints of 1 ₂ = 6, from the formula, the similarity between mt1 ₁ and it ₁ is sim1 ₁₁ = 86.67, and sim1 ₁₁ > th6. Therefore, it is considered that the pair (mt1 ₁ , it) ₁ ) is held as a compatible pair.

Similarity between mt1 ₁ and it ₂ : sim1
_{Since 12} = −22.58, and sim1 ₁₂ <th6, it cannot be handled.

Similarity between mt1 ₂ and it ₁ : sim1
_{Since 21} = -14.28, and sim1 ₂₁ <th6, it is possible to deal with it.

Similarity between mt1 ₂ and it ₂ : sim1
_{Since 22} = 100 and sim1 ₂₂ > th6, the set (mt1 ₂ , it ₂ ) is held as a compatible pair.

As a result, as a compatible pair, p1 = (mt1 ₁ , it ₁ ) and p2 = between IT and MT1.
(Mt1 ₂ , it ₂ ) was detected.

Next, the heterogeneous compatible pair compatibility relationship determining unit 35b-2 is compatible with the two different compatible pairs detected by the compatible pair detecting unit 35b-1 between the model document and the input document. It is determined whether or not to do.

"Compatible" here means 2
It means that there is no contradiction that two corresponding pairs exist at the same time. The determination conditions here include the following. Corresponding pairs to be judged are (mt _k , it _j ) and (mt ′ _k , it ′ _j ), respectively.
Here, the position coordinates of the upper left point of the mt _k (mt _k x1, m
t _k y1), and the position coordinates of the lower right corner are (mt _k x2, mt _k
y2), 'the position coordinates of the upper left point of the _k (mt' mt _k x1
, Mt ′ _k y1) and the position coordinates of the lower right corner are (mt ′ _k x2
, Mt ′ _k y2), and the position coordinate of the upper left end of it _j is (i
t _j x1, it _j y1), and the position coordinates of the lower right corner are (it _{j
x2, it j y2), it} 'j of the coordinates of the upper left end (it' _j x1, it is' _j y1), the position coordinates of the lower right (it 'and _{j x2, it' j y2)} .

The coordinate system (x, y) of the document image: 0 <
In the case of x ≦ WIDTH and 0 <y ≦ HEIGHT, FIG.
A coordinate system as shown in 8 is defined. That is, in FIG.
Rectangular area T shown in (a): (The position coordinate of the upper left corner is (t
x1, ty1) and the position coordinates of the lower right corner are (tx2, ty2)
) And 0 <x <t shown in FIG.
The region where x1 and 0 <y≤HEIGHT is satisfied is region 1,
18 (c), tx2 <x ≦ WIDTH and 0 <y
The region satisfying ≤HEIGHT is region 2, the region satisfying 0 <x≤WIDTH and 0 <y <ty1 shown in FIG. 18D is region 3, and the region satisfying 0 <x≤WIDTH and ty2 <y shown in FIG. 18E. A region that satisfies ≦ HEIGHT is defined as a region 4.

Also, it is considered that two compatible pairs are compatible only when all the following conditions 1 to 3 are not satisfied as the determination conditions.

Condition 1: mt _k = mt ' _k , Condition 2: it _j = it' _j , Condition 3: There is an inversion in the arrangement relationship. Condition 3 is a case where the following conditions 3-1 to 3-4 are satisfied. That is, condition 3-1: it ′ for it _j (it ′ _j )
_j (it _j ) is in region 1 and mt ' _k (mt _k ) is in region 2 for mt _k (mt' _k ).

Condition 3-2: For it _j (it ' _j ), it' _j (it _j ) is in the region 2 and mt _k (m
For t ′ _k ), mt ′ _k (mt _k ) is in region 1.

Condition 3-3: For it _j (it ' _j ), it' _j (it _j ) is in the region 3, and mt _k (m
'to _{k), mt' t k (} mt k) is in the region 4.

Condition 3-4: For it _j (it ' _j ), it' _j (it _j ) is in the region 4, and mt _k (m
'to _{k), mt' t k (} mt k) is in the region 3.

Different type compatible compatibility determination unit 35b
The operation -2 will be specifically described by using the compatible pairs p1 and p2 described above. There is (p1, p2) as a set of two different compatible pairs between IT and MT1. Since this pair does not satisfy all of the conditions 1 to 3, it is judged that they are compatible with each other. The heterogeneous compatible pair compatibility relationship determination unit 35b-2 outputs the compatible pair determined to be compatible to the best matching extraction unit 35b-3.

The best matching extraction unit 35b-3 selects the maximum set of compatible pairs that are compatible with each other among the compatible pairs determined to be compatible by the heterogeneous compatible pair compatibility relationship determination unit 35b-2. By finding, the best matching between the input table feature set and the model table feature set is extracted.

The best matching extraction unit 35b-3, as shown in FIG. 19, further includes an association graph creation unit 35b-3a.
And the maximum clique extraction unit 35b-3b. The association graph creation unit 35b-3a receives the determination result of the inter-pair compatible compatibility determination unit 35b-2,
An association graph is created based on the information. The nodes of this union graph indicate compatible pairs, and the arc connecting the nodes indicates that two compatible pairs are compatible, and the determination result of the compatibility compatible pair determining unit 35b-2 for different types is possible. Is an auxiliary data structure that represents.

Specifically, the available pairs p1 and p2 are sent to the association graph creating section 35b-3a, and as a result, the association graph shown in FIG. 20 is obtained. The above-mentioned “maximum set of compatible pairs that are all compatible with each other” can be regarded as the maximum connected node set (completely compatible with each other) in this association graph. It is a clique, with larger cliques representing better matching in this example.

The maximum clique detection unit 35b-3b extracts a fully connected subgraph (maximum clique) having the maximum number of nodes from the association graph created by the association graph creation unit 35b-3a. The maximum clique detection unit 35
The operation of b-3b is described in, for example, the literature “Science theory (D), J68-
D, 3, pp 221-228, 1985 ”can be applied.

The cliques extracted by the maximum clique detectors 35b-3b, that is, the corresponding pairs of elements that make up the "maximum set of compatible pairs that are all compatible with each other" are the table feature set IT of the input document. And a table feature set MT1 of the model document are associated with each other. Specifically, the maximum cliques: mclique = p1, p2 are obtained, and the correspondences of mt1 ₁ and it ₁ and mt1 ₂ and it ₂ are obtained. This correspondence result is sent to the ruled line collating unit 35c in the subsequent stage.

At this time, in each table of the table feature set of the input document and the model document, the coordinate value of the ruled line feature contained therein is normalized by the coordinate value of the upper left end of the table. Further, the coordinate values of the ruled line feature of each table of the input document are scale-converted so as to be superimposed on the corresponding model document table.

That is, the vertical width of the input table is it-height,
The width is it-width, and the corresponding model table height is mt-h.
When the width is eight and the width is mt-width, the coordinate value of the normalized ruled line feature in the input table is further multiplied by (mt-width / it-width) for the x coordinate value and (mt-width for the y coordinate value. h
Eight / it-height) Scale conversion by multiplication. As a result, the ruled line collating unit 35c in the subsequent stage can perform the matching process between the ruled line sets included in the input table and the model table under the same scale and the same coordinate system.

In Step 3 showing the operation of the above-mentioned compatible pair detection unit 35b-1, if sim _kj <th6, the structures of mt _k and it _j are different, and
For example, as shown in FIG. 21A, when the input document has poor print quality and the table is separated ((a-1) in the figure)
Alternatively, there may be a case where the adjacent tables come into contact with each other at the time of image input because of a narrow interval ((b-1) in the figure).

In order to deal with such a problem, the available pair detection unit 35b-1 may further execute the following processing.

Step 3-1: mjn _k > ijn _j (m
If it is jn _k <ijn _j) is a table wherein it _l (mt _l) detecting one adjacent to the following conditions are met it _j (mt _k) from the IT (MT1), integrate them Then, a new virtual table feature it ′ _j is newly generated, and the number of joints ijn ′ _j (mjn ′ _k ) and mjn _k (i
jn _j ) and the similarity degree siml ′ _kj .

Similarity: If siml ' _kj is greater than or equal to the threshold value th6, it is considered that it is possible to cope with (mt _k , i
t ′ _j ) ((mt ′ _k , it _j )) is held as a compatible pair.

Condition: it _j (mt _k ) and it _l (m
No other table exists during t _l ).

Step 3-2: If the siml ' _kj obtained in Step 3-1 is less than the threshold value th6, the similarity:
St is continued until siml ' _kj becomes equal to or greater than the threshold value th6, or until a table that satisfies the conditions cannot be found.
Repeat ep3-1.

In this case, the best matching unit 35b-3 of the table matching unit 35b outputs all the combinations of "corresponding" that make up the maximum clique, and then applies the following conditions to the candidates. Narrow down. If a plurality of combinations still occur, all of them are sent to the ruled line matching unit 35c in the subsequent stage, and finally based on the result (by selecting the combination with the highest matching degree). The correspondence between tables may be uniquely determined.

Condition: All the elements of the model table feature set correspond to any of the elements of the input table feature set.

Next, in the ruled line collating unit 35c, the table collating unit 3
Correspondence processing is performed between the ruled line sets included in the input table and the model table associated with each other in 5b. At this time, the association between the horizontal ruled line sets and the association between the vertical ruled line sets may be performed independently. Then, the matching between the two may be obtained after the corresponding processing is completed. The ruled line matching unit 35c in this case is further configured as shown in FIG. That is, the table correspondence selection unit 35c-1, the vertical ruled line matching unit 35c-2, the horizontal ruled line matching unit 35c-3,
And an inter-direction matching acquisition unit 35c-4.

First, the table correspondence selecting unit 35c-1 selects an arbitrary correspondence from the correspondences between tables extracted by the table collating unit 35b. The vertical ruled line collating unit 35c-2 associates the vertical ruled line set of the input table selected by the table correspondence selecting unit 35c-1 with the vertical ruled line set of the model table. If this matching is successful, the horizontal ruled line matching unit 35c-3 further matches the horizontal ruled line sets. Direction matching acquisition unit 35c-
3 obtains the matching between the matching by the vertical ruled line matching unit 35c-2 and the matching by the horizontal ruled line matching unit 35c-3.

The vertical ruled line matching unit 35c-2 and the horizontal ruled line matching unit 35c-2 are further configured as shown in FIG. These processing operations are basically the same except that the difference in ruled line direction is taken into consideration.

As a concrete description, the vertical ruled line set M _{1 of} mt1 _{1 in} the vertical ruled line matching unit 35c-2 will be described below.
The operation of the associating process between the vertical ruled line set IVL ₁ of VL ₁ and it ₁ will be described. However, from FIG. 14, M ₁ VL ₁ = (m ₁ vl ₁ , m ₁ vl ₂ , m ₁ vl ₃ ,
m ₁ vl ₄ , m ₁ vl ₅ , m ₁ vl ₆ , m ₁ vl ₇ , m
₁ vl ₈ ). Hereinafter, the vertical ruled line will be simply described as a ruled line.

The applicable ruled line feature pair detection unit 35c-2a shown in FIG. 23 detects, for each element of the ruled line set of the model, all of the input ruled line features that may be associated with the element, and can handle them. Manage as a pair of different ruled line features.
That is, the procedure described below is executed.

Step 1: Select any one ruled line feature m ₁ vl _k (meaning the kth ruled line feature) from any M ₁ VL ₁ .

Step 2: A search range (area _mvl ) for detecting the input ruled line feature corresponding to m ₁ vl _k is set.

Here, the position coordinates of the upper left end and the lower right end of the ruled line feature of m ₁ vl _k are (mlx1, mly1), (mlx
2, mly2), the search range is, for example, (mlx1
-Th9, mly1) and (mlx2 + th9, mly2) may be used as the inside of a rectangle constituted by coordinate values. here,
It is assumed that the threshold th9 is given in advance.

Step 3: The input ruled line feature that is included / intersects in the search range obtained in Step 2 is extracted.

This processing is performed, for example, as follows. That is, the position coordinate values of the upper left corner and the lower right corner of the input ruled line to be searched are (ix1, iy1), (ix2, i
If y2), the input ruled line satisfying the following conditions is extracted.

Condition: min (mlx2 + th9, ix2)
-Max (mlx1 + th9, ix1) +1> 0 and m
in (mly2, iy2) -max (mly1, iy1
) +1> 0.

Step 4: Select one of the extracted input ruled line features (for example, ivl _j ( _jth ruled line feature of the input ruled line feature set) is selected).

Vertical width of Step 5: m ₁ vl _k : ml-hei
Vertical width of ght and ivl _j : il-height similarity: si
Calculate ml _kj .

Here, it is assumed that the degree of similarity: siml _kj is obtained by the following equation, for example.

When ml-height> 0 or il-height> 0 siml _kj = 100−200 × | ml-height−il-heigh
t | / (ml-height + il-height) ml-height = 0 and il-height = 0 siml _kj = -100 Step 6: Similarity: If siml _kj is equal to or greater than a preset threshold th10, Assuming that the correspondence is possible, the pair (m ₁ vl _k , ivl _j ) is held as a correspondence pair.

Step 7: Similarity: When siml _kj is less than the threshold value th10, the following processing is further performed.

Step 7-1: As shown in FIG.
The following processing is performed in order to deal with the case where a line that should be a book is faint or is broken and is separated.

Step 7-1-1: Among the input ruled line features extracted in Step 3, one of the ruled line features that satisfies the following conditions is extracted, and the closest one is extracted.
As shown in (1), the similarity between the vertical width: il-height 'and ml-height: siml' _kj is calculated. However, the position coordinate values of the upper left corner and the lower right corner of ivl _j are (i
vl _j x1, ivl _j y1), (ivl _j x2, ivl
_j y2), and the position coordinate values of the upper left corner and the lower right corner of the input ruled line to be extracted are (ix1, iy1), (ix2, iy2)
And

Condition: min (ivl _j x2, ix2)-
max (ivl _j x1, ix1) +1> 0, similarity: s
If iml ' _kj is greater than or equal to the threshold value th10, it is determined that they can be supported, and the set (m ₁ vl _k , ivl' _j ) is held as a compatible pair.

Step 7-1-2: Step 7-1-1
When siml ′ _kj <th10 obtained in step S1, the similarity: si
Step until ml ′ _kj becomes equal to or greater than the threshold value th10, or until no ruled line that meets the conditions is found.
Repeat p7-1-1.

Step 7-2: As shown in FIG. 26, the following processing is performed in order to cope with a case where a plurality of ruled line features of the model correspond to a plurality of input ruled line features.

Step 7-2-1: ml-height> il
-height (ml-height <il-height), the ruled line feature iv that is closest to ivl _j (m ₁ vl _k ) satisfying the following condition out of IVL ₁ (M ₁ VL ₁ ).
Similarity between the vertical widths il-height ′ (ml-height ′) and ml-height (il-height) generated by detecting _one l ′ _j (m ₁ vl ′ _k ) and integrating them: siml Calculate ′ _kj .

[0182] However, the position coordinates of the left upper and right lower ends of _{ivl j, (ivl j x1 '} , ivl j y1'), (i
vl _j x2 ', ivl _j y2'), and a preset threshold value is th11.

Condition: min (ivl _j x2 + th11, iv
l _j x2 ′)-max (ivl _j x1-th11, ivl _j
x1 ′) + 1> 0 Similarity: When siml ′ _kj is greater than or equal to the threshold value th10, it is possible to support (m ₁ vl _k , ivl _j ).
And _{(m 1 vl k, ivl '} j) ((m 1 vl k, ivl
_j ) and (m ₁ vl ′ _k , ivl _j )) are held as a pair capable of correspondence.

Step 7-2-2: Step 7-2-1
When siml ′ _kj <th10 obtained in step S1, the similarity: si
Step until ml ′ _kj becomes equal to or greater than the threshold value th10, or until no ruled line that meets the conditions is found.
Repeat p7-2-1.

Step 8: Steps 4 to 7 are applied to all the input ruled line features extracted in Step 3.

Step 9: Steps ₁ to 8 are applied to all the elements of the attention M ₁ VL ₁ .

Here, min () is a function that outputs the smaller one of the two variables in (), and max () is ().
This is a function that outputs the larger of the two variables.

Correspondence Ruled Line Feature Pair Detection Unit 35c-2a
The above-mentioned processing operation will be specifically described by using M ₁ VL ₁ and IVL ₁ . Available ruled line feature pair detection unit 35c
-2a, it is assumed that the following ruled line feature pairs are obtained as a result of extracting the elements of IVL ₁ that have a possibility of being associated with each other by providing a search range for each element of M ₁ VL ₁ .

Pl ₁ = (m ₁ vl ₁ , ivl ₁ ), pl ₂ = (m ₁ vl ₂ , ivl ₂ ), pl ₃ = (m ₁ vl ₃ , ivl ₃ ), pl ₄ = (m ₁ vl _4). , Ivl ₂ ), pl ₅ = (m ₁ vl ₄ , ivl ₄ ), pl ₆ = (m ₁ vl ₅ , ivl ₄ ), pl ₇ = (m ₁ vl ₆ , ivl ₄ ), pl ₈ = (m ₁ vl ₇ , ivl ₅ ), pl ₉ = (m ₁ vl ₈ , ivl ₆ ).

Of these, pl ₁ , pl ₂ , pl ₃ , pl
₄ , pl ₈ and pl ₉ are obtained by the processing from Step 2 to Step 6 (hereinafter, only the corresponding feature pairs obtained by the processing from Step 2 to Step 6 are referred to as one-to-one correspondence pair).

[0191] pl5 is similarity in the process from Step2 to Step6: To Siml ₄₄ is less than the threshold value TH10, and IVL ₄ by Step7-2-1 "m ₁
v1 ₄ and m1 vl5 integrated "pair was detected. Then, the pair is managed by dividing it into a compatible pair of pl ₅ and pl ₆ . Similarly for pl ₇ , St
In ep7-2-1, ivl ₄ and “m ₁ vl ₄ and m ₁ vl ₆
Is detected as a pair that is integrated, and is extracted as a compatible pair.

Correspondence Ruled Line Feature Pair Detection Unit 35c-2a
The setting of the search range in Step 2 of the processing operation may be performed by the procedure described below, for example. For example, the search range of the model vertical ruled line VL ₁ shown in FIG.
It may be set according to the distance between the model vertical ruled line VL ₂ adjacent to the model vertical ruled line VL ₁ on the left side and the model vertical ruled line VL ₃ adjacent to the right side.

[0193] That is, the position coordinates of the upper left point of the _{VL 1 (VL 1 x1, VL} 1 y1), the position coordinates of the lower right end _{(VL 1 x2, VL 1 y2} ), the position coordinates of the upper left point of the VL ₂ value _{(VL 2 x1, VL 2 y1} ), the position coordinates of the lower right end _{(VL 2 x2, VL 2 y2} ), the position coordinates of the upper left point of the _{VL 3 (VL 3 x1, VL} 3 y1), right If the position coordinate value of the lower end is (VL ₃ x2, VL ₃ y2), VL ₁
The distance between the VL _2: a Dist12, the distance between the VL ₁ and VL _3: dist13 _{respectively, dist12 = VL 1 x1 -VL 2} x2 +1, dist13 = VL 3 x1 -VL 1 x2 +1, more determined that And

Then, the search range is set to ((VL ₁ x1 -dis
t12 / 2), (VL ₁ y1 + th9)) and ((VL ₁ x2 +
_{dist13 / 2), (VL 1} y2 + th9)), it may be a rectangular region composed of position coordinates of the.

Here, the model vertical ruled line VL ₂ adjacent to VL ₁ on its left side is min (VL ₁ y2, VL ₂ y2) −
The model vertical ruled line VL3 adjacent to the right side can be obtained by detecting the model vertical ruled line having the minimum distance dist12, which satisfies max (VL ₁ y1, VL ₂ y1) +1> th13, and min (VL ₁ y2 , VL ₃ y2) -max (V
L ₁ y1, VL ₃ y1) +1> th13, distance di
This can be obtained by detecting the model vertical ruled line for which st13 is the minimum. Here, th13 is the threshold.
The search range of each model horizontal ruled line can be similarly obtained.

In addition to this, the search range in Step 2 may be set as follows. For example, when the k-th model ruled line is focused, the input ruled line that is the search target and has a number within k ± α may be set as the search range of the focused model ruled line. Further, all the input ruled lines having the same length as the target model ruled line may be set as the search range in the state where the scale conversion is performed with the parameter of a certain size.

Next, the compatible ruled line feature pair compatibility determination unit 35c-2b determines the applicable ruled line feature pair detection unit 35c.
-2a, it is determined whether or not they are compatible with each other in the combination of all the two different compatible pairs detected.

The following are given as the judgment conditions here. Each available pair to be judged is p =
Let (ml _k , il _j ) and p ′ = (ml ′ _k , il ′ _j ).

Here, the position coordinate of the upper left corner of ml _k is (m
l _k x1, ml _k y1), and the position coordinates of the lower right corner are (ml _k
x2, ml _k y2), 'the position coordinates of the upper left point of the _{k (ml' ml k x1,} ml 'k y1), the position coordinates (ml lower right _{end' k x2, ml 'k y2} ), the il _j the position coordinates of the upper left corner _{(il j x1, il j y1} ), the position coordinates of the lower right end _{(il j x2, il j y2} ), il ' the position coordinates of the upper left point of the _{j (il' j x1, il} ' _j y1) and the position coordinates of the lower right corner are (il ′ _j x2, il ′ _j y2).

It is considered that the two compatible pairs are compatible only when all the conditions 1 to 4 are not satisfied as the determination conditions.

Condition 1: Either p or p'can be a one-to-one correspondence pair, and ml _k = ml ' _k .

Condition 2: Either p or p'is a one-to-one correspondence pair, and il _j = il ' _j .

Condition 3: Both p and p'are one-to-one correspondence pairs, and satisfy either of the following conditions 3-1 and 3-2.

Condition 3-1: (min (ml _k x2, ml ' _k
x2) -max (ml _k x1, ml ′ _k x1) +1)> 0 and (min (ml _k y2, ml ′ _k y2) −max (ml _k y1
, Ml ′ _k y1) +1)> 0.

Condition 3-2: (min (il _k x2, il ' _{k
x2) -max (il k x1,} il 'k x1) +1)> 0 and _{(min (il k y2, il} ' k y2) -max (il k y1
, Il ′ _k y1) +1)> 0.

Condition 4: The arrangement relationship is reversed. That is, it is in the following states 4-1 to 4-4.

4-1: For il _j (il ' _j ), i
l ′ _j (il _j ) is in the region 1 and ml _k (ml ′ _k )
, There is ml ′ _k (ml _k ) in region 2.

4-2: For il _j (il ′ _j ), i
l ′ _j (il _j ) is in the region 2, and ml _k (ml ′ _k )
, There is ml ' _k (ml _k ) in region 1.

4-3: For il _j (il ′ _j ), i
l ′ _j (il _j ) is in the region 3, and ml _k (ml ′ _k )
, There is ml ′ _k (ml _k ) in region 4.

4-4: For il _j (il ' _j ), i
l ′ _j (il _j ) is in the region 4, and ml _k (ml ′ _k )
, There is ml ′ _k (ml _k ) in region 3.

Compatible ruled line feature pair compatibility determination unit 35
The operation of c-2b can be performed by the corresponding ruled line feature pair pl described above.
_A specific description will be given using _{1 to} pl ₉ . pl ₁ to pl
_There are 36 combinations of all 9 possible ruled line feature pairs up to 9.

Among the combinations which do not satisfy all of the above conditions 1 to 4, (pl ₁ , pl ₂ ), (pl ₁ , pl)
₃ ), (pl ₁ , pl ₄ ), (pl ₁ , pl ₅ ), (p
l ₁ , pl ₆ ), (pl ₁ , pl ₇ ), (pl ₁ , pl
₈ ), (pl ₁ , pl ₉ ), (pl ₂ , pl ₃ ), (p
l ₂ , pl ₅ ), (pl ₂ , pl ₆ ), (pl ₂ , pl
₇ ), (pl ₂ , pl ₈ ), (pl ₂ , pl ₉ ), (p
l ₃ , pl ₅ ), (pl ₃ , pl ₆ ), (pl ₃ , pl
₇ ), (pl ₃ , pl ₈ ), (pl ₃ , pl ₉ ), (p
l ₄ , pl ₆ ), (pl ₄ , pl ₇ ), (pl ₄ , pl
₈ ), (pl ₄ , pl ₉ ), (pl ₅ , pl ₆ ), (p
l ₅ , pl ₇ ), (pl ₅ , pl ₈ ), (pl ₅ , pl
₉ ), (pl ₆ , pl ₇ ), (pl ₆ , pl ₈ ), (p
l ₆ , pl ₉ ), (pl ₇ , pl ₈ ), (pl ₇ , pl
₉ ) and (pl ₈ , pl ₉ ) in 32 ways. In each of these combinations, the corresponding ruled line feature pairs that make up the combination are determined to be compatible.

Next, the best matching extraction unit 35c-2c
Is a compatible ruled line feature pair compatibility determination unit 35c-2b.
The best matching between the input table feature set and the model table feature set is extracted by finding the maximum set of compatible pairs that are all compatible with each other.

The best matching extraction units 35c-2c
Has the same function as the best matching extraction unit 35b-3 shown in FIG. 17 (details are shown in FIG. 19).
In the association graph creation unit that constitutes the best matching extraction unit 35c-2c, an association graph is created from the results obtained by the compatible ruled line feature pair compatibility determination unit 35c-2b, or from the pl ₁ to pl ₉ For 9 possible ruled line feature pairs, the one shown in FIG. 28 is created.

Regarding the matching process between M ₁ VL ₁ and IVL ₁ , in the best matching extraction units 35c-2c, (m ₁ vl ₁ , ivl ₁ ), (m ₁ vl ₂ , ivl)
₂ ), (m ₁ vl ₃ , ivl ₃ ), (m ₁ vl ₅ , iv
l ₄ ), (m ₁ vl ₆ , ivl ₄ ), (m ₁ vl ₇ , i
It is assumed that the correspondence of vl ₅ ) and (m ₁ vl ₈ , ivl ₆ ) is extracted.

Set of horizontal ruled lines of mt1 ₁ : M ₁ HL ₁ =
(M ₁ hl ₁ , m ₁ hl ₂ , m ₁ hl ₃ , m ₁ hl ₄ ,
horizontal ruled line set of m ₁ hl ₅ ) and it ₁ : IHL ₁ = (i
Similarly, in the matching process among the hl ₁ , ihl ₂ , ihl ₃ , ihl ₄ , ihl ₅ ), the horizontal ruled line matching unit 35c-3 similarly (m1 hl ₁ , ihl ₁ ), (m ₁ h
l ₂ , ihl ₂ ), (m ₁ hl ₃ , ihl ₃ ), (m ₁
It is assumed that the correspondence of hl ₄ , ihl ₄ ) and (m ₁ hl ₅ , ihl ₅ ) is extracted.

Mt1 ₂ and i extracted by the table collating unit 35b
Correspondence processing between ruled line sets in correspondence of t ₂ is similarly performed by the ruled line collating unit 35c, and a vertical ruled line set of mt1 ₂ is: M ₁ VL ₂ = (m ₁ vl ₉ , m ₁ vl ₁₀ , m ₁ vl
₁₁ ) and it ₂ vertical ruled line set: IVL ₂ = (ivl ₇ ,
Between ivl ₈ and ivl ₉ ), (m ₁ vl ₉ and ivl
₇ ), (m ₁ vl ₁₀ , ivl ₈ ), (m ₁ vl ₁₁ , iv)
l ₉ ), mt1 ₂ horizontal ruled line set: M ₁ HL ₁ = (m ₁
hl ₆ , m ₁ hl ₇ ) and it ₂ horizontal ruled line set: IHL
_{Between 2} = (ihl ₇ , ihl ₈ ), (m ₁ vl ₆ ,
It is assumed that the correspondence between the ruled line features of ivl ₆ ) and (m ₁ vl ₇ , ivl ₇ ) is obtained.

The collation degree calculation unit 35d includes a ruled line collation unit 35c.
The degree (matching degree) is calculated by quantifying the correspondence between the structured features between the model document and the input document from which the correspondence relationship is extracted by.

The matching degree is calculated between all the model documents sent to the model matching unit 35 and the input document, and is output to the matching result output unit 35e. Matching degree: matching-m
etric is the number of model horizontal ruled lines smhl-num, the number of model vertical ruled lines smvl-num, the total number of input horizontal ruled lines that are associated with the model horizontal ruled line is smch-num, and the corresponding input vertical ruled line is the model vertical ruled line When the total number of attached items is smcv-num, it is defined by the following formula, for example.

Matching-metric = 100-200 × (| smhl
-num-smch-num | + | smvl-num-smcv-num |) / ((sm
hl-num-smch-num) + (smvl-num-smcv-num)) For example, the matching degree between the input document of FIG. 9 and the model document of FIG. 14: matching-metric1 is smhl-num = 7, smvl-n
From um = 11, smch-num = 7, smcv-num = 10, matching-metric ₁ = 100-200 x (| 7-7 | + | 11
−10 | / (7 + 7) + (11 + 11)) = 94.44.

The matching degree: matching-metric ₂ between the input document in FIG. 9 and the model document in FIG. 15 is set to (-100) because the corresponding relationship between the structured features can be extracted. To do.

The matching result output unit 35e is the model matching unit 3
Among the matching degrees between all the model structured features and the input structured features sent to S5, the combination of the model document and the input document showing the maximum value is selected, and the correspondence between these structured features is selected. The result is output to the collation result determination unit 37.

The collation result judging unit 37 is the model collating unit 35.
Correspondence between the structured features of the model document and the input document showing the maximum matching degree in (hereinafter referred to as the correspondence between structured features)
It is determined whether or not was acquired.

That is, when the maximum matching degree calculated by the model matching unit 35 is equal to or greater than the threshold value: th7 which is given in advance, it is determined that the structured feature correspondence can be acquired. When the maximum matching degree is less than th7,
Assuming that the structured feature correspondence cannot be acquired, the input document is rejected and the next document is input.

In this case, the model collation unit 35 performs collation processing on all the models not selected by the format type identification unit 33, and the result is discriminated by the collation result determination unit 37. Good. By doing so, the processing error in the format type identifying unit 33 can be relieved, and the accuracy of the processing result can be improved.

More specifically, for example, when the model matching unit 35 calculates the maximum matching degree between the input structured feature of FIG. 9 and the model structured feature of FIG. 14, its value: max-sim. Is from matching-metric ₁ , max-sim = 9
It is 4.44, and if th7 = 60, then th7 <max-sim, and it is considered that the corresponding relationship between the structured features has been acquired.

The correspondence between the structured features is held in the following format, for example. That is, in each input ruled line feature model ruled line feature correspondence, the input ruled line feature im
The age of the model ruled line feature corresponding thereto is stored in age, and the identifier of the model ruled line corresponding thereto is stored in image of the model ruled line feature. If -1 is set in advance to the image of each ruled line feature of each ruled line set, -1 is always set to the image of the ruled line feature that is not associated.

The most important structured feature correspondence obtained through the model matching unit 35 and the matching result judging unit 37 is the correspondence between the ruled line set of the input document and the ruled line set of the model document (hereinafter , Which is referred to as a ruled line feature correspondence). The character string region extraction unit 43 in the subsequent stage cuts out the character string region from the input image based on this correspondence.

At this time, if the correspondence between ruled lines is incomplete due to the lack of one of the structured features or contains a contradiction, it becomes impossible to process. In order to solve such a problem, the unfixed / contradictory correspondence discovery / correction unit 4
1 corrects the non-correspondence / contradiction correspondence with respect to the correspondence between ruled lines before the processing by the character string area extraction unit 43.

The non-correspondence / contradiction correspondence finding / correcting unit 41 carries out the following processes (1) and (2).

(1) Among the ruled line features that make up the model ruled line set, those that are not associated with the input ruled line are detected, and the other features that are already associated are used to identify those that are associated with the input ruled line set. A virtual input ruled line to be discovered or associated is automatically generated and newly added to the input ruled line set.

(2) When the processing of (1) above is performed, FIG.
If a contradiction such as the one shown in Figure 6 occurs, it is resolved and a consistent relationship is created.

Such unsupported / contradictory correspondence discovery / correction unit 3
The operation of 9 follows the flowchart shown in FIG. 30, for example. The processing operation of each step of the flowchart shown in FIG. 30 is as follows. However, it is assumed that each element of the input ruled line set is still converted to the coordinate system of the associated model ruled line set at this point.

F1: Of the elements of the model ruled line set,
The feature image with -1 is detected.

F2: Coordinate values (mx1, my1) at the upper left end and coordinate values (mx2, my) at the lower right end of the target model ruled line feature
For 2), the search ranges are set as follows. Here, it is assumed that the threshold value th8 is preset.

Lim-x1 = mx1−th8 lim-y1 = my1−th8 lim-x2 = mx2 + th8 lim-y2 = my2 + th8 Among the input ruled line features included in this search range, the one closest to the target model ruled line is detected. To do. At this time, the distance value representing the measure of the closeness may be defined by, for example, the Euclidean distance between the centers of gravity of the ruled line features.

F3: A virtual input ruled line having the following features (ruled line feature) is generated. The ruled line features are position coordinates (kx1, ky1) at the upper left end, position coordinates (kx2, ky2) at the lower right end, vertical width (k-height), and horizontal width (k-
width) and the position coordinates (kcx, kcy) of the center of gravity.

F4: The target model ruled line is 1. In the case of horizontal ruled lines, vertical model ruled lines connected to both ends of the model ruled line of interest are detected. If these vertical model ruled lines exist (a) and the input ruled lines corresponding to them exist, only the x coordinate value of the position coordinates of the upper left end and the lower right end of the vertical input ruled line feature is respectively kx1.
And kx2.

(B) If it does not exist, or if there is a vertical model ruled line but no corresponding input ruled line, the position coordinate value mx of the horizontal model ruled line of interest.
Store 1 and mx2 in kx1 and kx2, respectively.

2. In the case of a vertical ruled line, the position coordinate values mx1 and mx2 of the model ruled line of interest are set to kx1 and kx, respectively.
Store in 2.

F5: The target model ruled line is 1. In the case of vertical ruled lines, the horizontal model ruled lines connected to both ends of the model ruled line of interest are detected. If these horizontal model ruled lines (a) exist and the corresponding input ruled lines also exist, only the y coordinate value of the position coordinates of the upper left end and the lower right end of the vertical input ruled line feature is determined by ky1
And ky2.

(B) If it does not exist, or if there is a horizontal model ruled line but no corresponding input ruled line, the position coordinate value my of the vertical model ruled line of interest is my.
Store 1 and my2 in ky1 and ky2, respectively.

2. In the case of a horizontal ruled line, the position coordinate values my1 and my2 of the target model ruled line are set to ky1 and ky, respectively.
Store in 2.

F6: An image of the feature of the detected model ruled line at f2
Find out. If image is set to -1,
If a value other than -1 is set in the direction of NO in the flowchart of FIG. 30, the process proceeds in the direction of YES.

F7: When the target model ruled line is a horizontal ruled line,
The vertical model ruled lines connected to both ends of the model ruled line of interest are detected. These vertical model lines are: If they exist and there is an input ruled line corresponding to them, only the x-coordinate value of the position coordinates of the upper left corner and the lower right corner of the vertical input ruled line feature is respectively considered as the x at the upper left corner and the lower right corner of the horizontal input ruled line. Store in coordinate values.

2. If it does not exist, or if there is a vertical model ruled line but no corresponding input ruled line, the position coordinate value mx of the horizontal model ruled line of interest.
1 and mx2 are stored in the x coordinate values of the upper left corner and the lower right corner of the horizontal input ruled line of interest, respectively.

F8: When the target model ruled line is a vertical ruled line,
The horizontal model ruled lines connected to both ends of the target model ruled line are respectively detected. These horizontal model lines are: If it exists and there is an input ruled line corresponding to it, only the y coordinate value of the position coordinates of the upper left corner and the lower right corner of the horizontal input ruled line feature is only the y coordinates of the upper left corner and the lower right corner of the horizontal input ruled line of interest, respectively. Store in coordinate values.

2. If it does not exist, or if there is a horizontal model ruled line but no corresponding input ruled line, the position coordinate value my of the vertical model ruled line of interest is my.
1 and my2 are stored in the y coordinate values of the upper left corner and the lower right corner of the vertical input ruled line of interest, respectively.

The specific operation of the flow chart shown in FIG. 30 will be described with reference to the input structured feature shown in FIG. 9 and the model structured feature shown in FIG. Of the model ruled line feature set, only m ₁ vl ₄ has no associated input ruled line.
Thus, m ₁ in step f1 of the flow chart of FIG. 30
vl ₄ is detected. Then, in step f2,
ivl ₄ included in the search range of m ₁ vl ₄ is detected, and m ₁ vl ₅ and m ₁ vl ₆ are detected as model ruled lines corresponding to ivl ₄ in step f6. Of these, m ₁
vl ₆ and m ₁ vl ₄ can coexist (can exist at the same time)
However, the compatibility of m ₁ vl ₄ and m ₁ vl ₅ is contradictory. Therefore, in step f9, it is determined which of m ₁ vl ₄ and m ₁ vl ₅ is closer to the input ruled line, and as a result, m ₁ vl 4 is determined.
You can see that ₄ is closer. As a result, step f10
Then, the correspondence between ivl ₄ and m ₁ vl ₅ is invalidated, a correspondence between m ₁ vl ₄ and ivl ₄ is newly generated in steps f11 and f12, and the resulting change in the coordinate values is performed in steps f7 and f8. Done.

Since the correspondence is invalidated in step f10, there is no input ruled line associated with m ₁ vl ₅ . After detecting this in step f14, m ₁
The input ruled line corresponding to vl ₅ is found and set. First, in step f2, iv is set in the search range of m ₁ vl _5.
l ₄ is found, and m ₁ vl ₄ and m ₁ vl ₆ are detected as model ruled lines corresponding to ivl ₄ in step f6. Of these, m ₁ vl ₆ and m ₁ vl ₅ can coexist (can exist at the same time), but it is known that the compatibility of m ₁ vl ₄ and m ₁ vl ₅ is inconsistent, and m ₁ vl ₄ is more compatible. Is m ₁
Since it is known that the input ruled line corresponding to m ₁ vl ₅ is not found in the input ruled line set since it is closer than vl ₅ , a virtual input ruled line is generated in step f3,
The position coordinates are set in steps f4 and f5, and added to the ruled line set in step f13. As a result, there is no uncorresponding model ruled line in the model ruled line set, and the process in the uncorresponding / contradictory correspondence finding / correcting means 39 ends.

By applying the post-matching processing shown in the following procedure to the ruled line matching obtained by the above processing result, the accuracy of the matching result can be further improved. When there is a line segment (for example, a strike-through line) having a high degree of similarity with the model ruled line near the input ruled line that should be associated with a certain model ruled line, it may be erroneously associated with it. The following process
Such an error is eliminated.

Step 1: One model ruled line (ml) is extracted.

Step 2: its search range (ar described above
The input ruled line (il) existing in (ea _ml ) is extracted, and the similarity (lsim _ml ) with the model is calculated. Where ml
If h: ml vertical width, mlw: ml horizontal width, ilh: il vertical width, and ilw: il horizontal width, then if ml is a horizontal ruled line, lsim _ml = 100−200 × | mlw−ilw | / (Ml
w + ilw), and in the case of a vertical ruled line, lsim _ml = 100−200 × | mlh−ilh | / (ml
h + ilh).

Step 3: All input ruled lines (il ′) for which lsim _ml ≧ th10 are extracted.

Step 4: Select the ruled line having the shortest distance dd _ml among the input ruled lines that have been associated with the model ruled line and il ′, and associate it with the model again. Here, the coordinates of the upper left corner and the lower right corner of ml are (mlx
1, mly1), (mlx2, mly2), and the upper left and lower right ends of il 'are (il'x1, il'y1),
(Il'x2, il'y2), if ml is a horizontal ruled line, dd _ml = min (mly1, il'y1) -max (mly
2, il'y2) +1, and in the case of a vertical ruled line, dd _ml = min (mlx1, il'x1) -max (mlx
2, il'x2) +1.

As a result of the above, the association processing between the input structuring and the model structuring features is completed, and the coordinate systems of all ruled line features of the input document are restored.

The ruled line forming process described below is performed on the ruled line feature set of the input document by using the correspondence relationship between the input structured feature and the model structured feature that are matched by the unsupported / contradictory correspondence finding / correcting means 39. The subsequent processing may be performed stably by applying the above.

For example, as shown in FIG. 31, when the end point (E in the figure) of the ruled line feature (L1 in the figure) is not in contact with another ruled line feature (L2 in the figure) orthogonal thereto, the end point of L1 The ruled line feature is formed by changing the position coordinates of the so as to be in contact with L2. This shaping process is applied to both the horizontal ruled line set and the vertical ruled line set of the input image.

The operation of the ruled line forming processing section for a set of horizontal ruled lines is as follows, for example. Here, the coordinate value of the upper left corner of L1 is (L ₁ x1, L ₁ y1) and the coordinate value of the lower right corner is (L _1
1 x2, L ₁ y2), the coordinate value of the upper left corner of L2 is (L ₂ x
1, L ₂ y 1) and the coordinate value of the lower right corner is (L ₂ x 2, L ₂ y
2)

Step 1: Select an arbitrary ruled line feature of the horizontal ruled line feature set of the model document corresponding to the input image.

Step 2: Detect model vertical ruled lines in contact with both ends of the target horizontal ruled line.

For example, the vertical ruled line L2 that should contact the left end (point E) of L1 in FIG. 31 is detected as follows.
First, the search area is set. Assuming that the threshold value set in advance is th12, the search area is, for example, (L ₁ x1 −th1
2, (L ₁ y1 + L ₁ y2) / 2-th12), (L ₁ x1
+ Th12, (L ₁ y1 + L ₁ y2) / 2 + th12) is the inside of the rectangle (the rectangle shown by the broken line in FIG. 31).

Next, of the vertical ruled lines intersecting the search area, the one having the smallest distance: dist defined below is extracted.

Dist = | L ₁ x1 − (L ₂ x1 + L ₂ x2) / 2 | Step 3: Extract the input vertical ruled line associated with the target model horizontal ruled line. Here, the position coordinate value of the upper left end of the focused input horizontal ruled line is (ix1, iy1), and the position coordinate value of the lower right end is (ix2, iy2).

Step 4: The input vertical ruled line corresponding to the model vertical ruled line in contact with the left end of the model horizontal ruled line of interest is extracted. Here, the position coordinate value of the upper left corner is (lx1
, Ly1), and the position coordinate value of the lower right corner is (lx2, ly2
).

Step 5: The input vertical ruled line associated with the model vertical ruled line in contact with the right end of the target model horizontal ruled line is extracted. Here, the position coordinate value of the upper left end is (rx1
, Ry1) and the position coordinate value of the lower right corner is (rx2, ry2
).

Step 6: The position coordinate of the upper left end of the input horizontal ruled line of interest is changed to ((lx1 + lx2) / 2, iy1).

Step 7: Change the position coordinates of the lower right corner of the input horizontal ruled line of interest to ((rx1 + rx2) / 2, iy2).

Step 8: The processing from Step 2 to Step 7 is performed on all the model horizontal ruled line features.

The document structure acquisition unit 41 acquires the structure of the input document by performing the following processing when a consistent structured feature correspondence relationship is obtained between the input document and the model document. To do. That is, it is considered that the structure of the input document is acquired by copying the knowledge of the model document registered in advance in the model registration unit 31 into the input document based on the correspondence between the structured features.

More specifically, first, the identification number (hereinafter referred to as id) given to each ruled line feature of the model document is determined based on the ruled line correspondence to the ruled line feature of the input document associated therewith. Give.

Next, the various kinds of knowledge defined for the model document are copied to predetermined areas of the memory 43b for storing the knowledge prepared for the input document. The character string area extraction unit 43, the character recognition unit 45, and the character recognition result output unit 47 in the subsequent stage operate based on the knowledge copied to a predetermined area of the memory 43b.

The character string area extracting unit 43 cuts out only the area defined as the character string area to be recognized from the input image by using the knowledge about the document obtained by the document structure acquiring unit 41. The recognition target character string area may be defined by, for example, respective identification numbers of upper, lower, left, and right ruled lines surrounding the area. In this case, the character string area extracting unit 43 extracts the character string area by cutting out the portions inside the ruled lines located in the input document image from the input image.

The character recognizing unit 45 has a character string area extracting unit 43.
Using the knowledge defined for the character string area as a constraint condition, the character string image extracted in 1) is processed based on the method described in, for example, the literature “Science Technical Report, PRU93-47, 1993”. By this, character cutting / recognition processing is performed and converted into code data.

At this time, the character recognition results are sorted in descending order of similarity, and the upper N ranks may be held. Further, the recognition result may be corrected by interactive correction work between the operator and the system.

The character recognition result output unit 47 is the character recognition unit 4
The character recognition result of 5 is output to a display or a file based on an output form designated in advance for a model associated with an input document according to the character code data corrected in character units.

As described above, according to the present invention, the ruled line feature extracted from the input image is structured by the feature structuring unit 29, and the table feature and the feature relating to the joint are extracted, and the relation between them is extracted. to manage. Using these pieces of information, the associating process is performed between the structured features related to the format of the model document registered in advance by the model registration unit 31. At this time, the model matching unit 35 performs the matching process between the table feature sets between the input document and the model document, and further performs the matching process between the ruled line feature sets included therein, whereby the following effects are obtained. Is obtained.

1. Since a hierarchical matching process is performed, the amount of calculation can be reduced.

2. It is possible to handle the case where multiple tables are mixed.

3. By performing the table-by-table matching process, the overall layout relationship can be taken into consideration, and even if the same feature amount is seen locally, a matching error does not occur.

4. It is possible to obtain a parameter related to the size magnification for each correspondence between tables, and it is possible to handle a document in which the parameters related to the size of the input table corresponding to the model table have independent values.

5. Even if the table is divided due to deterioration of print quality, it can be handled.

6. Since the correspondence between the ruled lines is obtained between the input document and the model document, it is possible to deal with the case where the ruled lines are faint, broken or missing, or when there is an extra feature extraction result.

7. When the matching process is performed in ruled line units, plural-to-plural correspondence is permitted, so that it is possible to cope with a case where the ruled line distribution locally changes.

With respect to the collation processing result, the collation result determination section 37 evaluates the validity of the collation degree using the degree of collation, so that only the correct association result can be adopted.

Furthermore, the collation processing result is not supported.
Since the inconsistent correspondence finding / correcting unit 39 finds and corrects the incomplete correspondence result, the following effects can be obtained.

1. It can handle documents with poor print quality.

2. It is possible to deal with incomplete feature extraction results.

3. There is no case where processing cannot be performed in the subsequent processing based on the correspondence relationship.

4. It is possible to extract undetected image features by adjusting the parameters at the time of feature extraction for uncorresponding parts.

In the present invention, before the model matching process,
Since the format type identification unit 33 performs the identification process of the format structure type of the input document to narrow down the types of models to be applied in the collation process, wasteful collation process is not performed, and the following effects are obtained. is there.

1. The calculation amount is small.

2. Highly accurate processing results can be obtained because there is no need to unreasonably associate objects with dissimilar structures.

3. Since the operator does not have to manually give a model for each target document, the system can be automatically operated.

4. From the model format that was upright when the model was registered, rotated 90 degrees to the left and right, 18
It is not necessary to limit the input direction of the document by registering the four types that have been rotated by 0 ° and performing the matching process with these at the time of model matching.

[0296]

As described in detail above, according to the present invention, the format structure of a tabular form or the like can be accurately recognized, and the area of a character string can be efficiently specified.

[Brief description of drawings]

FIG. 1 is a block diagram showing a schematic configuration of an image processing apparatus according to an embodiment of the present invention.

FIG. 2 is a diagram showing an example of a document to be processed in this embodiment.

FIG. 3 is a block diagram showing a schematic configuration of a document image processing system combined with a character recognition device which is an embodiment of the present invention.

FIG. 4 is a block diagram showing the configuration of a feature extraction unit 27 in this embodiment.

FIG. 5 is a diagram showing an example of line segment elements extracted from an input image.

FIG. 6 is a diagram showing an example of character candidate rectangles extracted from an input image.

FIG. 7 is a block diagram showing another configuration of a feature extraction unit 27 in this embodiment.

FIG. 8 is a diagram showing an example of line segment elements that intersect / include a character candidate rectangle.

FIG. 9 is a diagram showing an example of ruled line features extracted from an input image.

FIG. 10 is a block diagram showing the configuration of a characteristic structuring unit 29 in this embodiment.

FIG. 11 is a diagram showing an example of table features extracted from an input image.

FIG. 12 is a diagram showing an example of a joint feature extracted from an input image.

FIG. 13 is a diagram showing an example of information about features that are hierarchically associated and managed.

FIG. 14 is a diagram showing an example of a model document.

FIG. 15 is a diagram showing an example of a model document.

FIG. 16 is a block diagram showing the configuration of a model matching unit 35 in this embodiment.

FIG. 17 is a block diagram showing the configuration of a table matching unit 35b in this embodiment.

FIG. 18 is a diagram used for description to define a region related to the periphery of an arbitrary rectangular region.

FIG. 19 is the best matching extraction unit 35 in this embodiment.
The block diagram which shows the structure of b-3.

FIG. 20 is a diagram showing an example of a association graph.

FIG. 21 shows an example of splitting and contacting table features.

FIG. 22 is a block diagram showing the configuration of a ruled line matching unit 35c in this embodiment.

FIG. 23 is a vertical ruled line matching unit 35c-2 according to the present embodiment.
3 is a block diagram showing the configuration of a horizontal ruled line matching unit 35c-3. FIG.

FIG. 24 is a diagram showing an example in which one ruled line is separated.

FIG. 25 is a view showing an example in which separated ruled lines are integrated.

FIG. 26 is a diagram showing an example in which a plurality of model ruled lines are associated with a plurality of input ruled lines.

FIG. 27 is a diagram showing an example of a search range for extracting an input ruled line feature that may be associated with any one model ruled line feature.

FIG. 28 is a diagram showing an example of the association graph.

FIG. 29 is a diagram showing an example in which inconsistent correspondence occurs due to an unsupported / contradictory correspondence discovery / extraction process.

FIG. 30 is a diagram showing an example of a flowchart showing a flow of uncorrespondence / contradiction correspondence discovery / extraction processing.

FIG. 31 is a diagram showing an example in which an end point of a ruled line feature is not in contact with another ruled line feature orthogonal to it.

[Explanation of symbols]

11, 21 ... Image input section, 12 ... Feature extraction section, 13 ... Feature structuring section, 14 ... Format structure information registration section, 15 ... Format structure type identifying section, 16 ... Format structure information collating section, 17 ... Not supported Conflict correspondence finding / correction unit, 18 ... Collation result determination unit, 19
... Document structure acquisition unit, 23 ... Binarization processing unit, 25 ... Pre-processing unit, 27 ... Feature extraction unit, 27a ... Line segment extraction unit, 27b ...
Character candidate rectangle extraction unit, 27c ... Ruled line feature extraction unit, 27d
... Filtering processing unit, 29 ... Feature structuring unit, 29a
... Ruled line grouping processing unit, 29b ... Table feature extraction unit, 29
c ... Ruled line joint detecting section, 29d ... Inter-feature relation describing section, 3
1 ... Model registration unit, 33 ... Font type identification unit, 35 ...
Model collating unit, 35a ... Selecting unit, 35b ... Table collating unit, 3
5b-1 ... Corresponding pair detection unit, 35b-2 ... Heterogeneous correspondence inter-pair compatibility relationship determination unit, 35b-3 ... Best matching extraction unit, 35b-3a ... Union graph creation unit, 35b-
3b ... Maximum clique extraction unit, 35c ... Ruled line collation unit, 35
c-1 ... Table correspondence selection unit, 35c-2 ... Vertical ruled line collation unit,
35c-2a ... Compatible ruled line feature pair detection unit, 35c-
2b ... Compatible ruled line feature pair compatibility determination unit, 35c-
2c ... best matching extraction unit, 35c-3 ... horizontal ruled line collation unit, 35c-4 ... direction matching acquisition unit, 35d ... collation degree calculation unit, 35e ... collation result output unit, 37 ... collation result determination unit, 39 ... not yet Correspondence contradiction correspondence finding / correction unit, 41 ... Document structure acquisition unit, 43 ... Character string region extraction unit, 45 ... Character recognition unit,
47 ... Character recognition result output unit.

Claims (10)

[Claims] 1. An image input means for generating an input image from a document, and a format structure information registration for previously registering information (format structure model) on the format structure of a processing target document used for recognizing the format structure of the input image. Means, a feature extraction means for extracting a geometric figure feature quantity from the input image generated by the image input means, and a graphic feature quantity extracted by the feature extraction means are grouped to generate an image feature, Feature structuring means for extracting and managing the relationship between the respective image features, and image features of the input image obtained by the feature structuring means,
A format structure type identifying unit that narrows down candidates for the format structure type of the input document by using information about the format structure of the processing target document registered in advance by the format structure information registering unit, and a candidate by the format structure identifying unit. All the format structure models that have become and the features of the input document structured by the feature structuring means are associated with each other, and the set of the format structure model and the input document that best correspond to each other is selected. In the format structure information matching unit that obtains the correspondence relationship and in the correspondence between the format structure document selected by the format structure information matching unit and the structured feature in the input document, incomplete correspondence and inconsistent correspondence are eliminated. An uncorrespondence / contradiction correspondence finding / correcting means for acquiring the correspondence between the format structure model and the structured features of the input document which are matched by Copying, in the input document, information about the pre-registered format structure model based on the correspondence between the structure structure model and the structured features of the input document obtained by the response / contradiction correspondence finding / correcting means. A document image processing apparatus, comprising: a document structure acquisition means for acquiring the format structure of an input document and related information. 2. An image input unit for generating an input image from a document, a line segment and a graphic feature relating to a character component are extracted from the input image generated by the image input unit, and the region other than the character component in the input image is further extracted. From the feature extraction means for extracting the features related to the line segment as the graphic features forming the ruled lines, and the feature related to the table by grouping the graphic features related to the ruled lines extracted by the feature extraction means,
Document image processing characterized by comprising: feature structuring means for extracting information about a joint portion generated at a portion where ruled lines intersect / connect in the feature relating to each table, and extracting / managing a relation between the features. apparatus. 3. An image input unit for generating an input image from a document, a line segment and a graphic feature relating to a character component are extracted from the input image generated by the image input unit, and the region other than the character component in the input image is further extracted. The ruled line feature extracting means for extracting the feature relating to the line segment as a graphic feature forming the ruled line and the set of the graphic feature relating to the ruled line extracted by the ruled line feature extracting means are the same group of ruled lines intersecting / connecting A document image processing apparatus comprising: a table feature extracting unit that extracts a feature related to a table by combining the above. 4. An image input means for generating an input image from a document, and format structure information registration for previously registering information (format structure model) relating to the format structure of a processing target document used for recognizing the format structure of the input image. Means and the graphic feature relating to the line segment and the character component from the input image generated by the image input means, and further extracting the feature relating to the line segment from the area other than the character component in the input image by regarding it as the graphic feature relating to the ruled line. A feature extraction unit and a feature related to a table are extracted by grouping graphic features related to ruled lines extracted by the feature extraction unit,
Feature structuring means for extracting information on a joint portion generated at a portion where ruled lines intersect / connect in the feature relating to each table, and extracting / managing a relation between the respective features, and the input obtained by the feature structuring means. Table collating means for performing collation processing between the characteristic relating to the table of the document and the characteristic relating to the table forming the format structure model registered in advance by the format structure information registering means, A ruled line collating unit that obtains a correspondence relationship between the ruled lines that form the table of the input document in the table correspondence obtained by the table matching unit and the ruled lines that form the table of the format structure model that corresponds to the ruled line, Collation result determining means for calculating the degree of collation indicating the degree of correspondence between the features based on the result of the collation processing, and determining whether or not the correct correspondence is performed. A document image processing device characterized by the above. 5. An image input means for generating an input image from a document, and format structure information registration for previously registering information (format structure model) on the format structure of a processing target document used for recognizing the format structure of the input image. Means, a feature extraction means for extracting a geometric figure feature amount from the input image generated by the image input means, and a group of graphic feature amounts extracted by the feature extraction means to generate image features, Feature structuring means for extracting and managing the relationship between the respective features, structured image features of the input image obtained by the feature structuring means, and processing registered in advance by the format structure information registering means The similarity is calculated using the information about the format structure of the target document, and the format structure model with the highest similarity or a plurality of format structure models in order from the highest similarity is calculated. Or a format structure model having a similarity of a certain value or more, and a format structure type identifying means for narrowing down the type of the format structure of the input document to one or a plurality of candidates. Document image processing device. 6. An image input means for generating an input image from a document, and format structure information registration for previously registering information (format structure model) relating to the format structure of a processing target document used for recognizing the format structure of the input image. Means and the graphic feature relating to the line segment and the character component from the input image obtained by the image input means, and further extracting the feature relating to the line segment from the region other than the character component in the input image as the graphic feature relating to the ruled line. A feature extraction unit and a feature related to a table are extracted by grouping graphic features related to ruled lines extracted by the feature extraction unit,
Feature structuring means for extracting information about a joint portion generated at a portion where ruled lines intersect / connect in the feature relating to each table, and extracting / managing a relation between the features, and an input image obtained by the feature structuring means. Of the structured feature of the document and the information about the format structure of the document to be processed registered in advance by the format structure information registration means, the similarity is calculated, and the format structure model or the similarity of the highest similarity is calculated. A format structure type identifying means for selecting a plurality of format structure models in order from the highest one or a format structure model having a similarity of a certain value or more and narrowing down the format structure type of the input document to one or more candidates. , For each of the format structure models selected by the format structure type identifying means, with respect to the table of the input document obtained by the feature structuring means. And a table collating unit that performs a collation process between the features related to the table that constitutes the format structure model registered by the format structure information registering unit and obtains an inter-table correspondence relationship; The ruled line collating means for acquiring the correspondence between the ruled lines forming the table of the input document and the ruled lines forming the table of the format structure model corresponding to the ruled lines in the correspondence relation of the created table, and the ruled line collating means. The matching degree calculation means for calculating the matching degree representing the degree of correspondence between the features with respect to the obtained correspondence relationship, and the maximum matching among the matching degrees of the respective format structure models calculated by the matching degree calculation means. Of the input document and the format structure model using the matching result output means for extracting the format structure model indicating the degree, and the maximum matching degree of the format structure model extracted by the matching result output means. Document image processing apparatus characterized by comprising a comparison result determining means for determining whether or not the correct correspondence between Zoka feature is being performed, the. 7. The format structure information registration means registers information about the format structure of an upright processing target document when registering information about the format structure of a processing target document used for recognizing the format structure of an input document. Characters that are generated by rotating at a plurality of predetermined angles, give information about how many times it is rotated from the upright one, and register all of them as information about the format structure of the processing target document The document image processing apparatus according to claim 1, claim 4, claim 5, or claim 6. 8. An image input means for generating an input image from a document and an upright processing target document when registering information on the format structure of the processing target document used for recognizing the format structure of the input document. Generates information about the format structure rotated at multiple predetermined angles, gives information about how many times it has rotated from the upright one, and registers all of them as information about the format structure of the processing target document. Format structure information registering means, feature extracting means for extracting geometrical graphic feature quantities from the input image generated by the image input means, and grouping graphic feature quantities extracted by the feature extracting means. The feature structuring means for generating image features by using the feature structuring means for extracting and managing the relationship between the features, and the structuring of the input image obtained by the feature structuring means. Format structure type identification for narrowing down the type structure of the input document to one or a plurality of candidates using the image feature and the information on the format structure of the processing target document registered in advance by the format structure information registration means. Means, and all the format structure models that are candidates in the format structure type identifying means and the features structured by the feature structuring means of the input document are associated with each other, and the format structure with the best correspondence is obtained. Model matching means for selecting a pair of a model and an input document and acquiring the corresponding relationship, and incomplete matching in the correspondence between the structured structure document and the structured feature in the input document selected by the model matching means. Between the structured structure model of the input document and the structured features of the input document, which are matched by discovering whether or not there is an inconsistent correspondence and eliminating them. When the unstructured and inconsistent correspondence finding / correcting means for acquiring the correspondence and the format structure model associated with the input image by the model matching means are rotated by a predetermined angle, the rotation angle is set upright. The image rotation means for rotating the input image in the direction to correspond to the erect format model, and the format registered in advance based on the correspondence between the format structure model and the structured features of the input document. A document image processing apparatus, comprising: a document structure acquisition unit that acquires the format structure of an input document and related information by copying information about a structure model into the input document. 9. An image input means for generating an input image from a document, and format structure information registration for previously registering information (format structure model) on the format structure of a processing target document used for recognizing the format structure of the input image. Means for extracting graphic features relating to line segments and character components from the input image generated by the image input means, and determining features relating to line segments from regions other than character components in the input image as graphic features relating to ruled lines (ruled line features). A feature extraction unit that considers and extracts a feature (table feature) related to a table by grouping the ruled line features extracted by the feature extraction unit, and joins that occur in the portions where the ruled lines intersect / connect in each table feature. Feature structuring means for extracting information about parts and extracting / managing relations between the respective features; and Table collating means for collating processing between the table features of the input document and table features forming the format structure model registered in advance by the format structure information registering means, and acquiring table correspondence relation; A ruled line collating unit that obtains a correspondence between the ruled line features that form the table of the input document and the corresponding ruled lines that form the table of the format structure model corresponding to the table correspondence obtained by the matching unit; Collation result judging means for calculating a collation degree indicating a degree of correspondence between the features with respect to the correspondence relation acquired by the means, and judging whether or not correct correspondence is made; In the correspondence relationship between the input document and the ruled line feature of the format structure model, which is determined to be correct by the above, the ruled line feature of the input document (input ruled line feature) is not associated. A means for extracting ruled line features (unsupported model ruled line features) of the format structure model, and a correspondence relationship when an input ruled line feature to be associated with the unsupported model ruled line feature is associated with another model ruled line feature Means for associating an unsupported model ruled line feature with its input ruled line feature, and if there is a missing unsupported input ruled line feature to be associated with the unsupported model ruled line feature, A means for associating input ruled line features, and when an input ruled line feature to be associated with the unsupported model ruled line feature is not found, a new input ruled line feature to be associated is newly generated and an unsupported model ruled line feature is newly generated. A document image processing apparatus, comprising: means for correcting non-correspondence and inconsistency correspondence by means for associating the input ruled line features. 10. An image input means for generating an input image from a document, and format structure information registration for previously registering information (format structure model) on the format structure of a processing target document used for recognizing the format structure of the input image. Means for extracting graphic features relating to line segments and character components from the input image generated by the image inputting means, and determining features relating to line segments from regions other than character components in the input image as graphic features relating to ruled lines (ruled line features). A feature extraction unit that considers and extracts a feature (table feature) related to a table by grouping the ruled line features extracted by the feature extraction unit, and joins that occur in the portions where the ruled lines intersect / connect in each table feature. Feature structuring means for extracting information about parts and extracting / managing relations between the respective features; and Table collating means for performing collation processing between the table features of the input document and the table features constituting the format structure model registered in advance by the format structure information registering means, and table collating means for obtaining the correspondence relation between tables; Ruled line matching means for acquiring a correspondence relationship between the ruled line feature forming the table of the input document and the ruled line feature forming the table of the format structure model corresponding thereto in the correspondence relationship of the table obtained by the means; In the correspondence relationship between the ruled line features acquired by the means, the ruled line matching that corrects the connection relationship between the ruled lines in the ruled line feature set of the corresponding input document based on the connection relationship between the ruled line features in the ruled line feature set of the format structure model. A document image processing apparatus comprising: a post-processing unit.