JP4853891B2 - How to create document structure information - Google Patents

Description

  The present invention relates to a method for creating document structure information, and more particularly, to a method for creating document structure information for a document composed of boxes separated by ruled lines.

  In recent years, enterprises and local governments have promoted the digitization of office documents, and development has been progressing at the national level, including the provision of general electronic government contact points. In order to improve the efficiency of paperwork, the processing of forms and the like is rapidly computerized. A lot of ruled lines are drawn vertically and horizontally in the form, and an area surrounded by these ruled lines is called a box or a cell. The box may be a self-instruction box pre-printed on the form itself, such as “name”, or an insertion box that specifically fills in the name, address, etc. of the writer. These boxes are laid out on the form based on a predetermined rule.

Generally, a system for processing a form has the following configuration. In order for the form processing system to extract necessary information from the form, first, an image image (bitmap) of the form is obtained by a reading device (OCR or the like). By analyzing the image based on the format stored in advance in the system memory, the layout of the form is grasped. This analysis specifies what information (for example, address or name) exists in which position in the form, and then, as an image that actually exists at that position, letters, numbers, symbols, etc. It is recognized as text by using well-known character recognition technology. Thereby, the information entered at the position is recognized as text. Here, the format is a model for analyzing the layout of the form, and the layout of the form is analyzed by comparing and referring to the template (see Patent Document 1).
JP 2001-266066 A

  However, the above-described method described in Patent Document 1 has a problem that it lacks expandability and flexibility when considering the correspondence to ruled line documents of various formats.

  Furthermore, although the above analysis method is effective for a document in which information has been previously entered, it has not been possible to analyze a document in which no information has been entered.

  The present invention has been made in view of the above problems. One of the objects of the present invention is to provide a method for creating document structure information that can analyze the structure of a ruled line document that is composed of boxes separated by ruled lines and in which no information is written.

The document structure information creation method of the present invention is a method for creating document structure information from a document in which a general structure document and a table structure document are mixed, and a plurality of boxes delimited by ruled lines are manually created by a computer or manually. A first step of classifying the boxes of the document based on the type of the box; and a second list for creating a box list indicating a vertical or / and horizontal adjacency relationship of the boxes by the computer And a third step of applying, to the box list , a format structure grammar constituted by a plurality of grammatical rules having a priority order and clarifying an instruction relationship between boxes by each grammar rule. , comprising a, in the third step, with respect to the box list, one of the vertical or horizontal instructions relationships between the box Only to the application of the general structure grammar is the format structure grammar for box group after conflict box, is the format structure grammar both directions between the vertical and horizontal instructions relationships between the box A table structure grammar is applied.

  According to the document structure information creation method of the present invention, a format structure grammar is applied to a box list indicating a vertical and / or horizontal adjacency relationship for a document having a plurality of boxes separated by ruled lines. is doing. Therefore, it is possible to analyze the relationship between the indications of the ruled line document and support the management of entry information, the summation of entry information, and the like, and the processing of the digitized document can be easily and universally handled. In addition, by applying the document structure information creation method of the present invention to an interactive document creation word processor, an interactive document entry word processor, a local electronic application system, an in-house document processing system, etc., an interactive document can be easily created. And managing the completed interactive document efficiently.

  Also, according to the document structure information creation method of the present invention, it is possible to analyze a ruled line document in which both vertical and horizontal instruction directions are mixed, and therefore various types of ruled line documents are analyzed. It becomes possible.

  Furthermore, according to the document structure information creation method of the present invention, each box constituting a ruled line document is classified into an instruction box, a blank box, an explanation box, and an insertion box. It is possible to analyze the indication relationship between each box.

<First embodiment>
First, a document format to which the document structure information creation method of this embodiment can be applied will be described. Documents that are generally widely used can be classified into two types: a complete document model and an interactive document model.

  The complete document model is used for applications such as newspapers, books, or advertisements, and is completed as a document when the author creates the document. Then, the reader reads the creator's transmission items from the completed document and acquires information.

  The interactive document model is a document model that is used for applications such as application forms, questionnaires, and resumes, and there are three types of people: creators, writers, and processors. The creator creates an incomplete document composed of an instruction regarding the contents of input information and an area for inputting the input information. The writer reads the instruction of the unfinished document, fills in necessary information in an appropriate area, and completes the document. The processor extracts and manages necessary information from the document completed by the entry of information by the writer. The processor may be the same as the creator.

  Furthermore, as shown in FIG. 1, there are a plurality of types of interactive document models. For example, FIG. 1A shows an interactive ruled line document 1 in which areas are divided by ruled lines, and FIG. 1B shows an interactive free format document 2 that is not divided into clear areas. The document structure information creation method of the present embodiment targets an interactive ruled line document 1 as shown in FIG. In the interactive ruled line document, instructions for all entry contents and areas for entry exist within the area delimited by ruled lines. Therefore, the document 3 as shown in FIG. 2 does not apply to the interactive ruled line document. However, the indication relationship can be analyzed by applying the present invention to the ruled line region of FIG.

  In an interactive ruled line document, a minimum rectangular area divided by ruled lines is defined as a box. Each box has its own meaning based on its location and internal string. Further, by combining a plurality of boxes, the document as a whole has a single purpose. The interactive ruled line document is composed of three elements (the relationship between an instruction and an instruction that form an interactive element, a character string related to entry information, and layout information indicating how to draw a ruled line).

  The ruled line document that is the target of the document structure information creation method is a ruled line document in which no useless box exists (no useless box that does not make sense exists in the document).

Boxes are roughly classified into non-entry boxes and entry boxes. The non-entry box includes an instruction box (IND) and an explanation box (EXP), and the entry box includes an insertion box (INS) and a blank box (BLK). The characteristics of each box are specified below.
・ Instruction box (IND) gives some entry instructions to other boxes ・ Insert box (INS) has a character string inside ・ Blank box (BLK) is a blank box with nothing written inside ・The explanation box (EXP) is described as IND, INS, BLK, EXP below the box where the explanation is written.

  With reference to FIG. 3 (A) and FIG. 3 (B), a box is demonstrated concretely. Referring to the ruled line document 4 shown in FIG. 3A, a box in which “name” and “birth date” are entered corresponds to IND. In addition, the box in which “Date” is entered is INS, the blank box is BLK, and the box in which “* Please enter your date of birth” is EXP. The classification result is shown in FIG.

  Referring to FIG. 3B, as indicated by an arrow, IND1 gives an instruction to the BLK adjacent to the right, and IND2 gives an instruction to the INS adjacent to the right.

  Next, the box indication relationship will be described with reference to FIGS. In an interactive ruled line document, there is an instruction relationship regarding the contents to be entered between boxes. This indication relationship has two directions, the vertical direction and the horizontal direction. There are various types of instruction relationships themselves. In this embodiment, four kinds of instruction relations acting between adjacent boxes as shown in FIG. 4 are assumed as instruction relations in the interactive ruled line document.

  FIG. 4A shows a single instruction box group 5 and shows a one-to-one instruction relationship in which one instruction box functions as one entry box. There are two types of adjoining directions between boxes: vertical and horizontal directions. Specifically, the arrows in the figure indicate an instruction relationship, and IND gives an instruction to an adjacent BLK. Such an instruction form is called a single instruction. Further, here, BLK (blank box) is adopted as the instruction box, but INS (insertion box) can also be an instruction box. The same applies to the instruction relationship described later.

  FIG. 4B shows a self-instruction box and an entry box that does not receive an instruction from the instruction box. The entry contents of this entry box can be fully assumed by the internal character string. Such a box is considered to point to the box itself. In other words, the self-instruction indication relationship occurs only in the insertion box.

  5 and 6, a one-to-n instruction relationship in which an instruction in one instruction box works on a plurality of boxes will be described. The indication direction is vertical or horizontal, and the indication is given linearly in either direction.

  The box group shown in FIG. 5 is a single layer repetition instruction box group 6, and the instruction relationship between the boxes is a single layer repetition instruction. The single-layer repetition instruction is a form in which the instruction box repeatedly instructs a structure in which only BLK is continuous or a structure in which only an insertion box having the same internal character string is continuous.

  Specifically, referring to FIGS. 5A and 5B, IND gives an instruction to adjacent BLK1, and further gives an instruction to BLK2 adjacent to BLK1.

  Referring to FIGS. 5C and 5D, IND is adjacent to BLK1 and BLK2, and gives the same instruction to BLK1 and BLK2, respectively.

  The box group shown in FIG. 6 is a multilayer repeat instruction box group 7, and the instruction relationship between boxes indicates a multilayer repeat instruction. The multi-layer repeated instruction is a form in which a plurality of box groups including instruction boxes are combined into one instruction box. That is, it is used to bundle overlapping information. In the multi-layer repeated instruction, a parent-child relationship is generated in the instruction box, so that a hierarchical instruction relationship is obtained in the entry box. Hierarchical instructions are called parent instructions.

  Referring to FIGS. 6A and 6B, IND1 gives the same instruction to IND2 and IND3. IND2 gives an instruction to the adjacent BLK1, and IND3 gives an instruction to the adjacent BLK2. These pointing directions are the same direction, and IND1 and IND2 are adjacent to each other, but IND1 and IND3 are not adjacent to each other. Such an instruction relationship is the parent-child relationship described above, IND1 is a parent instruction, and IND2 and IND3 are child instructions.

  Referring to FIG. 6C, IND1 is adjacent to IND2, and IND2 is adjacent to IND3. Both adjacent directions are longitudinal directions. Here, IND1 gives instructions to IND2 and IND3. Then, IND2 gives an instruction to BLK1 adjacent in the horizontal direction, and similarly IND3 gives an instruction to BLK2 adjacent in the horizontal direction. That is, for BLK1, IND1 is a parent instruction, and IND2 is a child instruction.

  With reference to FIG. 6D and FIG. 6E, such an instruction relationship also occurs in the multilayer repeat instruction box groups 7D and 7E.

  The ruled line document to which the document structure information creation method of the present embodiment is applied is configured by the above-described instruction relationship, and the instruction relationship across the pages, the instruction relationship by the arrow, and the instruction relationship working at a remote place are Do not handle.

The indication relationship as described above can be expressed by a context-free grammar using the extended Bacchus notation. In this embodiment, the grammar expression method is defined as a format structure grammar and expressed using the following symbols.
“·” Represents an adjacent relationship between boxes.
“:: =” represents derivation (reduction) from the right side to the left side.
“+” Represents one or more repetitions of the immediately preceding element.
“|” Represents selection of an element.

  Here, “adjacent” means that two boxes share sides of the same height or width.

  The format structure grammar is composed of grammatical rules having priorities. In addition to the four types of terminal symbols IND, EXP, BLK, and INS corresponding to the box type, <gcb> and <icb> which are non-terminal symbols are included. Used.

  <Gcb> (general compound box) represents a compound box that does not designate another box. Here, the composite box represents a group of boxes having an instruction / instructed relationship.

  <Icb> (indication compound box) represents a composite box that may indicate another composite box.

  With reference to FIG. 7, specific grammar rules of format structure grammar and their priorities will be described. The format structure grammar 50 is composed of eight types of grammar rules, and each grammar rule is assigned the same number as the priority order. That is, rule 1 is considered to have a higher priority in grammar rule 1 and grammar rule 2. This priority is given empirically and will be described below.

  Each grammar rule represents an instruction relationship, rule 1 represents a multi-layer repetition instruction, and rule 2 represents a single-layer repetition instruction. Rule 3 expresses a self-instruction insertion box, and rule 4 expresses an explanation box. Furthermore, rule 5 is a rule for receiving a single layer repetition instruction as shown in FIGS. 5C and 5D and a multilayer repetition instruction as shown in FIGS. 6D and 6E. This means reduction in a direction orthogonal to the application direction of Rule 1 performed as a process. Rule 6 is a rule for reducing composite boxes.

  In addition to each of these indication relationships, rule 7 considers the possibility of indicating other <gcb>, and if it is reduced to <icb> but there is no finally indicated <gcb>, it is analyzed This is a rule for making an element of a set of <gcb> meaning termination by success.

  Rule 8 exists to reduce the instruction linking part that is a feature of the tabular instruction in order to obtain the tabular instruction as a combination of structural analyzes in the horizontal and vertical directions.

  Specifically, rule 2 is given priority over rule 3 because the self-instruction is given only when there is no instruction box for the insertion box.

  Further, when rule 5 and rule 6 are not reduced by a higher-order rule, in order to detect a repetitive instruction as shown in FIGS. 5C, 5D, 6D, and 6E. Multi-layer, single-layer (including single instruction) and self-instruction are given priority.

  Furthermore, rule 7 is used when there is no <gcb> adjacent to <icb> in the end, and rule 8 is for formal handling of the table structure. Must not be.

  The document structure is analyzed using the format structure grammar as described above. The structure analysis of a document is composed of two stages: a syntax analysis stage for creating a structure analysis tree and an instruction relation analysis stage for analyzing an instruction relation working between boxes from the obtained structure analysis tree. Here, the structural analysis tree has a data structure that starts from a node indicating one component and repeats branching so that the tree expands to extend the branch. This structural analysis tree is generated directly from the grammar. In other words, the structural analysis tree can start reduction based on the grammatical rule from the state in which the classification result of the box type is a leaf node, and can place the symbol after reduction as the parent node of the symbol set before reduction. It can be generated by applying as many times as possible.

  The instruction relation analysis can be obtained from the result of the syntax analysis. That is, when attention is paid to a node in which the left node is an instruction box, an instruction relationship is established in which the instruction of the left node is directed to the entire right node.

  FIG. 8 shows a unique tree structure formed by three types of instruction relationships: single instruction, self instruction, and repetitive instruction. In the single instruction shown in FIG. 8A, the instruction box gives an instruction only to the entry box. Also, the entry box has not received instructions from other than this instruction box. In the self-instruction shown in FIG. 8B, the instruction box gives instructions to its own box and does not give instructions to other boxes. In the single-layer repetition instruction shown in FIG. 8C, the instructions for the entry box groups (a) to (c) for receiving the instructions are given from (1). In the multi-layer repetition instruction shown in FIG. 8D, the instructions for the box (d) for receiving the instructions are (2) to (4).

  As described above, the document structure information can be obtained by clarifying the indication relation of each box of the interactive ruled line document by the format structure grammar.

  Referring to FIG. 9, a flowchart 28 shows a method for analyzing an interactive ruled line document, and each step will be described below.

  In step S1, a vertical or horizontal box list is created from the target interactive ruled line document. The box list is a list indicating the adjacent relationship between boxes.

  The interactive ruled line document that is a target in this embodiment is limited to a document in which the pointing direction is only in the horizontal direction or a document in which only the vertical direction is set. That is, a document in which the pointing direction exists in both the vertical direction and the horizontal direction is not a target. Therefore, an H_list indicating the left and right connection is created for a document whose pointing direction is horizontal, and a V_list is created for a document whose pointing direction is vertical. A method for creating the box list will be described later.

  In step S2, the grammar rule having the highest priority in the format structure grammar is set as the current grammar rule.

  In step S3, it is determined whether or not there is a place where the current rule is applicable in the box list. If there is an applicable part, the process proceeds to step S4, and if not, the process proceeds to step S6.

  In step S4, a reduction process based on the grammatical rule is performed on the application location. However, when there are a plurality of applicable places, the reduction process is performed only on the first appearing place.

  In step S5, it is determined whether or not all boxes in the box list are described by <gcb> (a composite box that does not designate another box). If all the boxes are described by <gcb>, the box list is successfully analyzed, and the document structure information can be obtained. If some boxes are not described by <gcb>, the process moves to step S2.

  In step S6, a grammar rule having a lower priority than the current rule is set as the current rule, and the process moves to step S3 again.

  The structural analysis of the interactive ruled line document is performed by performing the above steps on the box list in the vertical direction or the horizontal direction.

  With reference to FIGS. 10 to 18, the structure analysis method of the interactive ruled line document according to the present embodiment will be specifically described.

  First, step S1 will be described in detail with reference to FIG. 10 and FIG. Here, an interactive ruled line document 30A having an instruction direction only in the horizontal direction as shown in FIG. 10A will be described as an example.

  Referring to FIG. 10B, an interactive ruled line document 30B shows a document in which each box of the interactive ruled line document 30A is classified into four types of IND, INS, EXP, and BLK. A unique number is assigned to each box type so that each classified box can be identified.

  As a method for classifying boxes, it is possible to automatically determine a box without a character string as BLK by using an image reading means such as OCR, but basically the boxes are classified manually. . Then, a box list (H_list) indicating the adjacent relationship in the horizontal direction is created.

  A method of creating the horizontal box list (H_list) 31 will be described with reference to FIG.

  In order to create the horizontal box list 31, first, a coordinate system is assumed in which the right direction of the page is the positive direction of the x axis and the downward direction is the positive direction of the y axis with reference to the upper left coordinates of the box. Then, after sorting in ascending order by y coordinate, boxes having the same y coordinate are sorted in ascending order by x coordinate. After sorting, if two consecutive boxes have the same height and completely share one side of each other, it is determined that the two boxes are adjacent in the left-right direction, and the adjacent symbol “·” Is inserted between the boxes. The resulting list is the horizontal box list 31. Here, with reference to FIG. 11 (A), it sorts in the order of arrow A1 to arrow A4. The arrow A passes over the box to be sorted and connects the sorting start point box and the end point box. The horizontal box list 31 formed in this way is shown in FIG. Here, the boxes sorted according to each arrow A are described on the same line.

  The above processing is performed in step S1, and the process proceeds to step S2.

  Although not required in this embodiment, a method of creating a vertical box list (V_list) will also be described here. In order to create a vertical box list, assuming the coordinate system described above, after sorting in ascending order by x coordinate, boxes having the same x coordinate are sorted in ascending order by y coordinate. After sorting, if two consecutive boxes have the same width and completely share one side of each other, it is determined that the two boxes are adjacent vertically, and the adjacent symbol “ Insert between boxes. The resulting list is a vertical box list.

  Next, the processing from step S2 to step S6 will be described in detail with reference to FIGS.

  In step S2, the grammar rule having the highest priority in the format structure grammar 50 shown in FIG. 7 is set as the current rule. Therefore, grammar rule 1 is set to the current rule.

  In step S 3, a part where the grammatical rule 1 can be applied to the horizontal box list 31 is checked. However, since there is no applicable part, the process proceeds to step S6, and after the grammatical rule 2 is set in the current rule, the process proceeds to step S3. In step S 3, it is determined whether grammar rule 2 is applicable to the box list 31. Here, referring to FIG. 12, grammatical rule 2 can be applied to the box group S1 surrounded by a broken line, so that the process proceeds to step S4 and reduction processing is performed. In the box list 31 after the reduction process is performed, the box group S1 is reduced to <gcb1>. By this reduction process, the single instruction relationship in which IND1 gives an instruction to BLK1 is analyzed.

  After the reduction process, it is determined in step S5 whether or not the box list 31 is described only by <gcb>. However, since there is an unreduced part at this stage, the process moves to step S2. In step S2, grammar rule 1 is set again as the current rule.

  As described above, it is determined whether or not the box structure can be applied to the box list in order from the grammar rule having the highest priority of the format structure grammar 50, the reduction process is performed on the applicable part, and the determination is made from the grammar rule 1. repeat. This is repeated until all box lists are described only with <gcb>.

  From here, the series of processes from the setting of grammar rule 1 to the current rule until the first reduction process is counted as one process, and the grammar rules applied at that time are mainly described. I will do it. Therefore, as shown in FIG. 12, the grammatical rule 2 is applied at the number of times of processing 1, and the box group S1 composed of IND1 and BLK1 is reduced to <gcb1>.

  With reference to FIG. 13, the processing from the processing count 2 to the processing count 7 will be described. A box group number corresponding to the number of times of processing is processed at the time of the number of times of processing. That is, the reduction process of the box group 2 is performed at the process count 2. Here, the reduction process based on the grammatical rule 2 is performed from the process number 2 to the process number 7. Therefore, in the number of processing times 2, the box group S2 composed of IND2 and BLK2 is reduced to <gcb2>. Similarly, the box group 3 to the box group 7 are also subjected to such a reduction process, and the box group S3 composed of IND3 and BLK3 is reduced to <gcb3> at the number of processing times 3. The other box groups S4 to S7 are also reduced from <gcb4> to <gcb7>, and the box group number corresponds to the number of the non-terminal symbol <gcb> after reduction.

  With reference to FIG. 14, the process in the process frequency 8 to the process frequency 10 is demonstrated. Here, reduction processing based on grammatical rule 3 is performed. That is, the box group 8 to the box group 10 are insertion boxes, and it is analyzed that there is no instruction relationship with other instruction boxes adjacent in the horizontal direction. Therefore, at the number of processing times 8, the box group S8 that is INS1 is reduced to <gcb8>. Similarly, in the processing times 9 and 10, the box group S9 is reduced to <gcb9> and the box group S10 is reduced to <gcb10>.

  With reference to FIG. 15, processing of the processing count 11 will be described. Here, a reduction process based on the grammatical rule 4 is performed, and the box group S11 indicating EXP1 which is the explanation box is reduced to <gcb11>.

  With reference to FIG. 16, processing from the processing count 12 to the processing count 15 will be described. Here, reduction processing based on the grammatical rule 6 is performed. That is, a process of reducing box groups that do not designate other adjacent boxes into one box group is performed. Accordingly, at the number of processing times 12, the box group S12 is reduced to <gcb12>. Similarly, the box group S13 is reduced to <gcb13> at the processing count 13, the box group S14 is reduced to <gcb14> at the processing count 14, and the box group S15 is reduced to <gcb15> at the processing count 15. If the processing count 15 is completed, it is determined that the analysis of the box list 31 in the horizontal direction is successful through step S5.

  With reference to FIG. 17, the horizontal indicating relationship between the analyzed boxes will be described. FIG. 17A shows the laterally adjacent structure analysis tree 35 created based on the analysis result, and FIG. 17B shows the analysis result.

  Referring to FIG. 17A, it can be seen that the entire document <document> is composed of box groups <gcb8>, <gcb11>, <gcb12>, <gcb13>, <gcb14>, and <gcb15>. These box groups are not in an instruction relationship. However, an instruction relation is established in the box group corresponding to the lower order of each box group. For example, <gcb1> and <gcb2>, which are positioned below <gcb12>, are in a pointing relationship. An arrow indicated by a solid line indicates the indicated direction. For example, <gcb1> is composed of IND1 and BLK1, and a single-instruction relationship is established in which IND1 gives an instruction to BLK1. Similarly, <gcb2> is composed of IND2 and BLK2, which are also in a single indication relationship.

  Referring to FIG. 17B, in the interactive ruled line document 30B, the analysis result obtained from the horizontal adjacent structure analysis tree 35 is indicated by an arrow 38, and the indication relation of each box is clarified. Yes. In this way, document structure information can be created. Here, a document in which only a box group having a single instruction relationship exists is handled, but a document having a box group having another instruction relationship can also be analyzed using the above-described method.

  Further, in the case of a document having a pointing relationship only in the vertical direction, document structure information can be created from the vertical structure analysis tree in the same manner as for V_list.

  By analyzing the instruction relations of ruled line documents and dividing and managing layout information, entry information and instruction information of interactive documents, it is possible to support entry information management, entry information aggregation, etc. It is possible to handle the processed document easily and universally. Further, only necessary information can be extracted, and management of document information can be made more efficient. Further, by separately managing document structure information and ruled line layout information, it is possible to improve the efficiency of office processing. Furthermore, by displaying an arrow or the like indicating the instruction relationship on the ruled line document, it becomes possible to prevent the writer from writing errors or omissions.

  In addition, by applying the document structure information creation method of this form to an interactive document creation word processor, an interactive document entry word processor, a local electronic application system, an in-house document processing system, etc., an interactive document can be created easily. And managing the completed interactive document efficiently. Furthermore, a structured description based on the format structure grammar can be generated semi-automatically.

<Second Embodiment>
Since this embodiment is basically the same as the first embodiment, the differences will be mainly described.

  First, the document to be analyzed in the present embodiment is a ruled line document in which vertical direction instructions and horizontal direction instructions are mixed. In order to analyze the structure of such a ruled line document, a single structural analysis is not sufficient. Therefore, horizontal priority structure analysis and vertical priority structure analysis are performed in order to analyze the indication relationship of the ruled line document.

  The horizontal priority structure analysis method is an analysis method in which grammatical rule application location search when creating a structural analysis tree is performed in the order of H_list and V_list. The procedure for creating the structural analysis tree will be described in the order of process number 1 to process number 6 shown below.

  1. Classify the box type of the target document, and create H_list and V_list.

  2. The rule with the highest priority in the grammar rule is the current rule.

  3. Scans H_list for places where the current rule can be applied. If there is an applicable part, a reduction process is performed, and the process proceeds to process number 6. In addition, when there are a plurality of applicable places, the reduction process is performed only on the first appearing place.

  4). Scans V_list for places where the current rule can be applied. If there is an applicable part, a reduction process is performed, and the process proceeds to process number 6. In addition, when there are a plurality of applicable places, the reduction process is performed only on the first appearing place.

  5. The grammar rule having one lower priority is newly set as the current rule, and the process proceeds to process number 3 again. If all grammar rules cannot be applied at this point, the analysis is terminated.

  6). Since there is a possibility that the arrangement of boxes and the connection relationship have changed due to the reduction process, H_list and V_list are created again. After creating the list, the process proceeds to process number 2. However, if H_list or V_list is reduced to only <gcb>, the analysis is successful and the process ends.

  As described above, the horizontal priority structure is analyzed. The vertical priority structure analysis method is an analysis method in which process number 3 and process number 4 are interchanged.

  In this way, by searching in a certain direction for grammatical rule application locations, it is possible to preferentially analyze the instruction relation that works in the horizontal direction in the horizontal priority structure analysis, and the instruction relation that works in the vertical direction in the vertical priority structure analysis. Can be preferentially analyzed. As a result, it is possible to create document structure information of a ruled line document in which instruction directions are mixed.

  With reference to FIG. 18A, a ruled line document analyzing method in which a vertical instruction direction and a horizontal instruction direction are mixed will be described by taking a ruled line document 70A as an example.

  First, the ruled line document 70B in which the box type of the ruled line document 70A is classified will be described with reference to FIG. Here, IND1 gives instructions to BLK1, and IND2 gives instructions to BLK2. These indication directions are horizontal directions. Further, IND3 gives an instruction to INS2, and this instruction direction is vertical. The format structure grammar 50 shown in FIG. 7 is applied to such a ruled line document 70.

  FIG. 18C shows a box list related to the ruled line document 70. Here, in order to explain horizontal priority structure analysis, a format structure grammar is first applied to the horizontal box list 71. If there is no applicable location of the current grammar rule in the horizontal box list 71, the current grammar rule is applied to the vertical box list 72.

  Referring to FIG. 19A, grammar rule 2 is applied to box group S30 consisting of IND1 and BLK1 in horizontal box list 71 and reduced to <gcb1>. The ruled line document 70C after the reduction process is shown in FIG. Then, with reference to FIG. 19C, a box list relating to the ruled line document 70C on which the reduction process has been performed is newly created.

  Referring to FIG. 20A, grammar rule 2 is applied to box group S31 consisting of IND2 and BLK2 in horizontal box list 71 and reduced to <gcb2>. Then, with reference to FIG. 20B, a box list relating to the ruled line document 70 on which the reduction process has been performed is newly created.

  Referring to FIG. 21A, grammar rule 2 is applied to box group S32 consisting of IND3 and INS2 in vertical box list 72 and reduced to <gcb3>. Then, with reference to FIG. 21B, a box list relating to the ruled line document that has undergone the reduction process is newly created.

  Referring to FIG. 22A, grammar rule 4 is applied to box group S33, which is EXP1 in horizontal box list 71, and reduced to <gcb4>. Then, referring to FIG. 22B, as a result of creating a new box list, the horizontal box list 71 and the vertical box list 72 are expressed only by <gcb>, and therefore the analysis is completed. Become.

  Referring to FIG. 23A, a horizontal priority structure analysis tree 73 is created from the analysis result. As a result, the horizontal instruction relationship is clarified, and the box gives an instruction in the direction indicated by the arrow. Therefore, IND1 becomes BLK1. It can be seen that IND2 gives instructions to BLK2.

  Here, the vertical priority structure analysis is omitted, but the result of analysis by the above-described method is shown in FIG. The vertical priority structure analysis tree 74 will be described with reference to FIG. IND3 and INS2 are in an instruction relationship in the vertical direction, and IND3 gives an instruction to INS2.

  With reference to FIG. 23C, the indication relationship obtained from the horizontal priority structure analysis tree 73 and the vertical priority structure analysis tree 74 is indicated by an arrow in the ruled line document 70. In this way, it is possible to create document structure information of a ruled line document in which designated directions are mixed vertically and horizontally.

<Third Embodiment>
Since the basic part of this embodiment is the same as that of the first embodiment and the second embodiment, the description will focus on the differences.

  With reference to FIG. 24, a ruled line document to which the document structure information creation method of the present embodiment is applicable will be described. Documents handled in this form are formed in a table structure. Specifically, the table structure is a document having a structure in which the shape of the entire box group is a rectangle, and all other boxes except the instruction box are entry boxes such as a blank box or an insertion box. However, the box at the top left of the table structure is considered an explanation box.

  The table structure is characterized by the fact that the entry boxes are arranged in a matrix, so that the entry box group is rectangular, and the instruction box continuous portion 41 exists in the horizontal and vertical directions of the upper and left sides of the box group. It is.

  The document structure expressed using the table structure is a structure used for effectively laying out the multilayer repeat instruction. That is, when there are two layers having a plurality of attribute information bundled with the parent instruction in the multilayer repeat instruction, the attribute information of each layer is laid out in the horizontal or vertical direction.

  Hereinafter, a specific example of the table structure targeted in this embodiment will be described.

  Referring to FIG. 24A, the table structure 40A is the simplest table structure. Here, three instruction boxes are provided continuously in the vertical direction and the horizontal direction, but the number of both instruction boxes is not limited. Referring to FIGS. 24B to 24E, these table structures 40B to 40E are table structures having an instruction box group of a parent-child relationship. Specifically, the table structure 40B and the table structure 40C have a parent-child relationship in a part of an instruction box that gives instructions in the horizontal direction. Although not shown here, a table structure in which an instruction box for giving an instruction in the vertical direction partially has a parent-child relationship is also an object of this embodiment. In the table structure 40D, a parent-child relationship is established in all instruction boxes that give instructions in the horizontal direction, and in the table structure 40E, a parent-child relationship is established in all instruction boxes that give instructions in the vertical direction.

  In this embodiment, document structure information is created by applying a table structure grammar, which is a format structure grammar corresponding to the table structure, to a document formed with the table structure as described above.

  The table structure grammar is a grammar characterized by combining a blank box and an insertion box at a time without distinction. As a result, it is possible to solve the case where an insertion box in which a unit or the like is embedded in the table and a blank box in which the unit is unnecessary or omitted are mixed. In addition, since there are portions where instruction boxes are continuous in a line in the table, grammar rules for reducing them in a meaningful manner are included.

  Since the entry boxes inside the table receive instructions from the left and upper two directions, if the consecutive entry boxes are combined with the instruction boxes and returned to a composite box, the composite box will have a different direction from the original reduction direction. Need to be combined. Therefore, new non-terminal symbols igt (indication group in table) and tbl (table) have been added to the portions representing the characteristics of these tables.

  <Igt> (indication group in table) is a group of boxes that indicate an instruction box concatenation unit in the table but do not give an instruction.

  <Tbl> (table) is a group of boxes having a table format instruction.

  The tabular instruction is an instruction relationship in which one entry box receives instructions independently from two different directions boxes in the vertical and horizontal directions, and one instruction box repeatedly issues instructions in one direction. The vertical and horizontal sides of the entry box are adjacent to the same width (height) box. In the tabular instructions, there is no parent-child relationship or semantic connection between the instruction boxes in two directions.

  With reference to FIG. 25, the grammar rules of the table structure grammar 60 and their priorities will be described. The table structure grammar 60 is composed of nine kinds of grammar rules, and each grammar rule is assigned the same number as the priority order. The priority of the table rules is set so that the most reliable analysis results appear first when analyzing the table structure.

  The nature of each grammar rule is explained below. Hereinafter, in order to distinguish from the grammatical rule 1 of the format structure grammar, it is described as a table rule 1, a table rule 2,.

  In the table rule 1, the continuous part of the entry box, which is a feature of the table structure, is reduced.

  In Table Rule 2, the multilayer repeat instruction is reduced.

  In the table rule 3, as a pre-processing for receiving the multilayer repetition instruction of the table rule 2, reduction is performed in a direction orthogonal to the application direction of the table rule 2.

  In the table rules 4, 5, and 6, the instruction connecting part, which is a feature of the table structure, is reduced.

  In Table Rule 4, the upper left of the table is reduced to igt.

  According to Table Rule 5, the instruction box link side portion of the IND array is sequentially reduced to “itt”.

  In the table rule 6, an instruction box continuous part having a parent instruction or a plurality of igt reduced by this table rule is sequentially reduced to igt.

  Table rules 7, 8, and 9 perform reduction to a table structure.

  In the table rule 7, the instruction box side part having the parent instruction or a plurality of igt reduced by this table rule is sequentially reduced to igt.

  In Table Rule 8, in order to allow the parent instruction to be applied to the entire table, the repetition of the parent instruction and tbl related to the entire table is reduced to tbl.

  According to the table rule 9, the table structure document is finally reduced to a composite box (gcb) and becomes a component of the document.

  In order to analyze the table structure, a single structural analysis is not sufficient. This is because the entry box in the table receives instructions from both the vertical and horizontal directions. Therefore, horizontal priority structure analysis and vertical priority structure analysis are performed in order to analyze the table structure indication relationship. Since the specific methods of the horizontal priority structure analysis and the vertical priority structure analysis have been described in the second embodiment, they are omitted here.

  A method for creating the document structure information of the table structure document 61 will be specifically described with reference to FIGS.

  Referring to FIG. 26A, the table structure document 61 has boxes for receiving instructions from both the vertical direction and the horizontal direction. FIG. 26B shows the result of classifying the box types. BLK1 receives instructions from IND1 and IND3, and BLK2 receives instructions from IND2 and IND3. The indication direction of IND3 is the horizontal direction, but the indication directions of IND1 and IND2 are the vertical direction.

  Referring to FIG. 27A, a box list is created after classification of box types. The horizontal box list 62 indicates H_list, and the vertical box list indicates V_list. Here, in order to perform the horizontal priority structure analysis, the table structure grammar rule is first applied to the horizontal box list 62. Table rule 1 is applied to the box group S20. As a result of applying Table Rule 1, IND3, BLK1, and BLK2 are reduced to <gcb1>. FIG. 27B shows the result of creating a new box list after the reduction. At this time, the box list is created again for the vertical box list 63 as well.

  Referring to FIG. 28A, table rule 4 is applied to box group S21 made up of EXP1 and IND1. As a result, the box group S21 is reduced to <igt1>. Then, as shown in FIG. 28B, a box list is created again.

  Referring to FIG. 29A, table rule 4 is applied to box group S22 made up of <igt1> and IND2. As a result, the box group S22 is reduced to <igt2>. Then, as shown in FIG. 29B, a box list is created again.

  Referring to FIG. 30A, table rule 7 is applied to box group S23 made up of <igt1> and <gcb1>. As a result, the box group S23 is reduced to <tbl1>. Here, since there is no applicable table rule for the horizontal box list 62, the applicable table rule for the vertical box list 63 is applied. Then, as shown in FIG. 30B, a box list is created again.

  Referring to FIG. 31A, table rule 9 is applied to box group 25 that is <tbl1>. As a result, <tbl1> is converted to <gcb2>, and all the boxes are converted to <gcb>, and thus the analysis ends. As described above, the horizontal priority structure is analyzed.

  With reference to FIG. 32, the indication relationship between the analyzed boxes will be described.

  First, the horizontal priority structure analysis tree 64 created based on the analysis result will be described with reference to FIG. An arrow indicated by a bold line represents an instruction relationship, and it can be seen that IND1 gives an instruction to BLK1, and IND2 gives an instruction to BLK2.

  Next, the vertical priority structure analysis tree 65 will be described with reference to FIG. The analysis method of the vertical priority structure is omitted because it only changes the order of the box list to which the table rule is applied as described above. Here, only the analysis result is shown. Thick line arrows indicate an instruction relationship, and it is understood that IND3 gives instructions to BLK1 and BLK2.

  Referring to FIG. 32C, the arrows in the table structure document 61 indicate the indication relationship obtained from these parse trees. In this way, the structure information of the table structure document can be created.

<Fourth embodiment>
Since this embodiment is the same as the first embodiment to the third embodiment in the same basic points, differences will be mainly described. Here, the document targeted in the first embodiment and the second embodiment is described as a general structure document, and the used format structure grammar is described as a general structure grammar. Also, the document targeted in the third embodiment is described as a table structure document, and the used format structure grammar is described as a table structure grammar.

  In this embodiment, the target document is both a general structure document and a table structure document, and the combined document is also a target. Furthermore, by specifying only the insertion box, it is possible to classify the box type.

  The analysis method for the general structure document employs the method of performing the horizontal priority structure analysis and the vertical priority structure analysis described in the second embodiment.

  Specifically, when classifying the types of boxes, first, the blank box is automatically determined as a box having no character string by using an image reading means, and is automatically set to BLK. Next, all boxes with character strings inside are set as instruction boxes except blank boxes. Then set the insertion box manually. At this point, the explanation box and the instruction box are allocated to the instruction box. However, when the format structure grammar is applied, an instruction box and an explanation box are classified by setting an explanation box as an instruction box that does not give an instruction to any box.

  Here, the grammar rule 8 of the format structure grammar 50 shown in FIG. 7 is unnecessary because it is a rule included to handle the table structure formally. In the second embodiment, the upper left box of the table structure is assumed to be an explanation box. However, since the writer specifies only the insertion box, the explanation box at the upper left of the table structure and the explanation box in the other ruled line document are classified as instruction boxes. Originally, the explanation box is a box that does not designate another box and is not designated by another box. Therefore, when the general structure grammar is used, it is inconsistent that no other box is indicated even though it is an instruction box in the analysis of both the horizontal priority and the vertical priority structure analysis. It will be. At this point, it is not possible to determine whether the instruction box in which the contradiction occurs is the upper left explanation box of the table structure or the explanation box in the general structure, but it can be judged to be either.

  Therefore, the analysis using the table structure grammar is performed for the boxes after the box in which the contradiction occurs. As a result, if the contradicted box is the upper left box of the table structure, it is reduced to <tbl>. Therefore, the box in which the contradiction has occurred is used as an explanation box. On the other hand, if it is not reduced to <tbl>, it can be determined that it is an explanation box in the general structure, so the box in which the contradiction occurs is replaced with the explanation box, and the general structure grammar is applied again.

  With reference to FIG. 33, a specific method for creating document structure information according to this embodiment will be described.

  In step S10 shown in the flowchart 70, as described above, a box list corresponding to the document in which the box type is classified is created.

  Next, in step S11, the format structure is applied to the box list. Here, the grammar excluding the grammar rule 8 of the format structure grammar 50 shown in FIG. 7 is applied.

  In step S12, after applying the grammar, it is determined whether or not an undirected relation error has occurred. If no unindicated error occurs, the analysis is successful. A box that causes an unindicated relation error is a box with an incorrect box type or a top box of a table structure. Therefore, if this unindicated error occurs, the process proceeds to step S13 in order to determine whether the cause of the error is the top box of the table structure or the box type is incorrect.

  In step S13, in order to determine the cause of the occurrence of an unindicated relation error, an instruction relation analysis of a structural analysis tree using table structure grammar is performed. At this time, the table structure grammar is applied to all boxes after the undirected relation error occurrence box.

  In step S14, after applying the table structure grammar, if a table structure starting from a box in which an unindicated relation error has occurred is not found, it is determined that the box type is the wrong box. This box is converted into an explanation box.

  After the box in which the error has occurred is converted into an explanation box, the format structure grammar is applied again in step S11. As a result, if no error occurs, the analysis is successful. That is, it is found that the box in which the error occurred is not an insertion box but an explanation box.

  If a tabular indication is detected, a table structure exists. Therefore, the range of the table structure is specified, the process returns to step S11, and the format structure grammar is again applied to the boxes after the table structure. The range of the table structure is up to the maximum number of entry boxes that receive instructions.

  With the above method, it is possible to analyze a document in which a general structure document and a table structure document are mixed, and document structure information can be created. Also, using this technique, it is possible to create document structure information for a document in which general structure documents and table structure documents exist alternately.

  A document 80 as shown in FIG. 34 will be described as an example of a document in which a general structure document and a table structure document are mixed. The result of classifying the box type of the document 80 is shown in FIG. Here, as described above, all the explanation boxes are classified as instruction boxes. First, when the general structure grammar is applied to this document, the box 85 indicated by diagonal lines causes an unindicated relation error. Therefore, the table structure grammar is applied to all the boxes after the box 85. When the instruction relation analysis is performed after the table structure grammar is applied, the table format instruction is seen from the box 86A and the box 87A to the box receiving the repeated instruction from the box 86B and the box 87B, and an unindicated relation error does not occur. It was. Therefore, this range is determined as a table, and up to box 85 is reanalyzed with the general structure grammar. When the general structural grammar is applied again after the box 90, a structural analysis tree is created, and an undirected relationship error does not occur even if the directed relationship analysis is performed. FIG. 36 shows the result of analyzing the instruction relationship in this way. In FIG. 36, the start point of the arrow is a box giving an instruction, and an instruction is given to the box located at the end point of the arrow. Then, it can be understood that the document 80 is a document in which the table structure document 89 exists between the general structure document 88A and the general structure document 88B.

As described above, document structure information of a document in which a general structure document and a table structure document are mixed is created.

(A) (B) is a figure explaining the document used as the object of the preparation method of the document structure information of this invention. It is a figure explaining the document used as the object of the preparation method of the document structure information of this invention. (A) (B) is a figure explaining the kind of box of the creation method of the document structure information of this invention. (A)-(B) is a figure explaining the instruction | indication relationship between boxes in the preparation method of the document structure information of this invention. (A)-(D) is a figure explaining the instruction | indication relationship between the boxes in the preparation method of the document structure information of this invention. (A)-(E) is a figure explaining the instruction | indication relationship between the boxes in the preparation method of the document structure information of this invention. It is a figure explaining the format structure grammar in the preparation method of the document structure information of this invention. (A)-(D) is a figure explaining the structure analysis tree of the preparation method of the document structure information of this invention. It is a figure explaining the flowchart of the preparation method of the document structure information of this invention. (A) (B) is a figure explaining the document used as the object of the preparation method of the document structure information of this invention. (A) (B) It is a figure explaining the box list | wrist of the preparation method of the document structure information of this invention. It is a figure explaining the preparation method of the document structure information of this invention. It is a figure explaining the preparation method of the document structure information of this invention. It is a figure explaining the preparation method of the document structure information of this invention. It is a figure explaining the preparation method of the document structure information of this invention. It is a figure explaining the preparation method of the document structure information of this invention. (A) (B) is a figure explaining the creation method of the document structure information of this invention. (A)-(C) is a figure explaining the preparation method of the document structure information of this invention. (A)-(C) is a figure explaining the preparation method of the document structure information of this invention. (A) (B) is a figure explaining the creation method of the document structure information of this invention. (A) (B) is a figure explaining the creation method of the document structure information of this invention. (A) (B) is a figure explaining the creation method of the document structure information of this invention. (A)-(C) is a figure explaining the preparation method of the document structure information of this invention. (A)-(E) is a figure explaining the table | surface structure used as the object of the preparation method of the document structure information of this invention. It is a figure explaining the table structure grammar in the preparation method of the document structure information of this invention. (A) (B) is a figure explaining the creation method of the document structure information of this invention. (A) (B) is a figure explaining the creation method of the document structure information of this invention. (A) (B) is a figure explaining the creation method of the document structure information of this invention. (A) (B) is a figure explaining the creation method of the document structure information of this invention. (A) (B) is a figure explaining the creation method of the document structure information of this invention. (A) (B) is a figure explaining the creation method of the document structure information of this invention. (A)-(C) is a figure explaining the preparation method of the document structure information of this invention. It is a figure explaining the preparation method of the document structure information of this invention. It is a figure explaining the preparation method of the document structure information of this invention. It is a figure explaining the preparation method of the document structure information of this invention. It is a figure explaining the preparation method of the document structure information of this invention.

Claims (8)

A method for creating document structure information from a document in which general structure documents and table structure documents are mixed.
A first step of classifying the box of the document having a plurality of boxes separated by ruled lines based on a type of the box, manually or manually;
A second step of creating a box list indicating a vertical or / and horizontal adjacency relationship of the box in a computer;
And a third step of applying to the box list a format structure grammar constituted by a plurality of grammatical rules having a priority order and clarifying the instruction relationship between boxes by each grammar rule. And
In the third step,
Applying a general structure grammar, which is the format structure grammar , in which the instruction relation between the boxes is only in one direction vertically or horizontally, to the box list,
Respect box group after conflict box, creating the document structure information, which comprises applying a table structure grammar is the format structure grammar both directions between the vertical and horizontal instructions relationships between the box Method. The box is
An instruction box that gives instructions to other boxes;
An explanation box that does not receive instructions from other boxes and does not give instructions.
A blank box where nothing is written in the box and information is entered,
2. The method for creating document structure information according to claim 1, wherein the box is one of insertion boxes in which characters are written and information is entered. In the first step,
The blank boxes are automatically classified using image reading means,
3. The method for creating document structure information according to claim 2, wherein the instruction box, the explanation box, and the insertion box are manually classified. In the third step,
2. The document structure information creation method according to claim 1, wherein a structure analysis tree indicating a vertical or horizontal pointing relationship between the boxes is formed. In the third step,
After applying the format structure grammar to the box list indicating the horizontal adjacency relationship, the format structure grammar is applied to the box list indicating the vertical adjacency relationship. Create
After applying the format structure grammar to the box list indicating vertical adjacency, the vertical structure analysis tree is obtained by applying the format structure grammar to the box list indicating horizontal adjacency. make,
2. The document structure information creation method according to claim 1, wherein a document structure is analyzed from the horizontal priority structure analysis tree and the vertical priority structure analysis tree. In the first step,
The blank boxes are classified using image reading means,
The insertion box is manually classified, and the boxes other than the blank box and the insertion box are classified as the instruction box,
3. The document structure information according to claim 2, wherein in the third step, the instruction relationship between adjacent boxes is analyzed, and the instruction boxes having no instruction relationship with other boxes are classified into explanation boxes. How to create   The document structure information creation method according to claim 1, wherein the grammar rules are described in an extended Bacchus notation. In the third step,
Scan sequentially applicable places from the grammar rules with high priority to the box list,
2. The method for creating document structure information according to claim 1, wherein after applying the grammar rule to the applicable part, the applicable part is sequentially scanned again from a grammatical rule having a higher priority.

Images