JPH0743718B2 - Multimedia document structuring method - Google Patents

Description

The present invention relates to a document processing method, and is suitable for extracting a logical structure (chapter / section, etc.) of a document from a multimedia document image and storing it in a file. The present invention relates to a multimedia document structuring method.

[Conventional technology]

Conventionally, a system for performing a keyword search using a document image has been proposed.

・ Joh Tanaka, Hideyuki Horii: “Transmedia Machine and It's Keyword Search Over Image Texts”, Rio 1988, 1988, “Transmedia Ma
chine and Its Keyword Search over Image Texts ", RIA
O'88,1988 The keyword search method in this system is realized by the matching process of the standard image pattern of the keyword and the character pattern in the document image. For this reason, it is impossible to use the information that the document image has in other systems such as a word processor that expresses the information in the existing character code.

Further, in recent document processing, it is required that not only character and text information but also non-text information such as figures and tables be uniformly handled as document content. A document in which character text information and non-text information are mixed is called a multimedia document. A multimedia document has a plurality of media, and a structure exists between the media (character area, photo area, figure area, etc.). This structure includes a layout structure that determines the spatial layout of pages, character spacing, line spacing, etc., and a logical structure that determines the semantic structure of chapters and sections.

Currently, there are the following formats for expressing the logical structure of a document in the computer world.

・ Formatter (Dee Knus, "The Tefbook", Addison Wesley, 1984, "The TEXbo
ok ", ADDISON WESLEY, 1984) Well-known formatters such as TEX provide commands for expressing the logical structure of a document such as chapters and sections. By using this command, the chapter title can be highlighted. , It is possible to generate a table of contents.

-ODA / ODIF, T.73 These are data formats for exchanging document information, and are mainly present as standards. The former ODA / ODIF (“Office Document Architecture (OD
A) and Interchange Format ", IS Oh 8613, 1988," Office Document Architect
ure (ODA) and Interchange Format ", ISO8613,1988)
Is the OSI standard of ISO, and the latter T.73 ("Recommendation T. Dot 73 Document Interface Pro Turkey for the Telematic Service", CIT Tea , 1984
Year, “Recomendation T.73 Document Interface Protoco
l for the Telematic Services ", CCITT, 1984) is CCITT
Is the standard. ODA / ODIF is being developed in a form that includes compatibility with T.73. The feature of these formats is that the document can be expressed by both the logical structure and the layout structure.

All of the above mentioned uses a logical structure to get the formatted output of the document. That is, if the contents of the document and the logical structure of the document are input, a formatted document is automatically obtained.

The document layout structure expresses a print layout on paper and is sometimes called a "format" or a "layout structure". In the following, "layout information structure" is regarded as a term having the same meaning as "layout structure", and is unified by using "layout structure". The "format" shall be regarded as indicating the common "allocation structure" for a certain document class.

When a person reads a document, the content of the document can be grasped more accurately by inferring the logical structure while looking at the layout structure of the document. Conversely, the layout structure of the document is to make the logic of the document easier to understand. Further, as described in the previous section, the representation of the logical structure of the document in the computer is used for shaping the document. Formatting a document is nothing more than adding a layout structure to the document.

From the above, it is considered that the logical structure and the layout structure are closely related in the document. Therefore, it is considered useful to use the layout structure of the document as a means for understanding the logical structure of the document.

In the above-mentioned image filing system, some methods have been proposed for obtaining the structure of a document from a stored document image.

・ Tsujimoto et al .: "Understanding layout of English documents", 1988 IEICE Spring National Conference, D-477, 1988. ・ Nishimura et al .: "Study on paper identification by layout structure", IEICE technology. Report PRU87-120, 1987 The above two methods generate bottom-up layout structure from multiple rectangular areas extracted in character units. By using the generated structure, it is possible to judge the similarity of the structures. However, since he does not have knowledge about the semantic structure, the elements of the document to be extracted are judged,
Bibliographic items cannot be extracted.

Higashino et al .: "Knowledge Representation Language Based on Set Representation of Rectangular Area
FDL and its application to document image understanding ”, IEICE Technical Report P
RU86-31, 1986 This is a method of extracting bibliographic items such as the author name of the title from the top down using the format definition language, but the structure of the data such as chapters and sections in the text is extracted. Cannot be converted to. Further, if the input document image does not satisfy the defined format, it can be rejected. This is effective when semantic information such as the title on the title page of a paper is always assigned to the same place in a document, but it cannot handle extraction of chapters or sections whose assigned position and number differ depending on the document. In this method, since the document is only divided, the elements of the document can be extracted, but the relation between the elements cannot be extracted as a data structure.

In the semantic structure of a document, it is possible to extract elements having only one layer corresponding to each element of the layout structure, such as bibliographic items and charts.
It was not possible to extract the elements that make up the hierarchical structure such as clauses and terms.

[Problems to be solved by the invention]

 The problems of the prior art are summarized as follows.

In the conventional technique, the processing target is only one page of the document image, and it is possible to extract the relationship between the areas in the page, but it is not possible to extract the relationship between the areas over a plurality of pages.

In the conventional technique, the structural elements of the document such as character strings, photographs and figures are separated and extracted as rectangular areas from the document image. From the absolute coordinates and relative coordinates of the rectangular area extracted here,
The layout structure of a document is analyzed bottom-up or top-down by examining the positional relationship of each rectangular area. As a result, it becomes possible to extract bibliographic items and make a similarity determination on the paper surface using the document layout structure.
However, in the conventional technique, since there is no means for outputting the relation information obtained as a result of the analysis to the secondary storage device such as a file, the analysis must be performed each time the retrieval is performed.

[Means for Solving the Problems]

In order to solve the above-mentioned problems in the prior art, the present invention has the following means.

First, we define the logical structure of the document and the procedure that can be expressed hierarchically. A means for estimating the logical structure of a document from the document allocation structure is provided. By providing this means, it becomes possible to extract the logical structure of the document from the document image.

Next, a means for expressing the logical structure of the document class and a specific logical structure of one document belonging to the document class are provided. Here, the document class means a set of documents having a common layout structure / logical structure. Further, means for hierarchically expressing the logical structure of the document class is provided, and means for associating the element of the logical structure estimated by the means for estimating the logical structure with the element of the logical structure of the document class is provided. By using the above means, it becomes possible to generate a logical structure unique to the input document.

[Action]

By using the method of the present invention, the common document allocation structure / logical structure and the relationship between them are described, so that a unique allocation structure and logical structure can be determined from a multimedia document input by a scanner or the like. Can be extracted. For example, there is a common format for the layout structure, the logical structure, and the relationship between the documents related to academic papers. In the present invention, by describing this common part in advance, it is possible to extract the layout structure and logical structure for each paper.

As for the extracted logical structure, the extracted logical structure and an image, or the character text resulting from character recognition of this image are combined and structured and stored in a file. By using the stored structured multimedia document data, it becomes possible to search the document including the logical structure information. For example, it is possible to search only the chapter title or refer to the table of contents.

〔Example〕

FIG. 1 is a block diagram showing an embodiment of a multimedia document structuring system of the present invention. The method of the present invention will be briefly described with reference to FIG.

A color multimedia document indicated by 100 in the figure means a document in which text, color photographs, and figures / tables are mixed. When this color multimedia document is stored in the storage device in the computer by means such as a color scanner, a large capacity is required. For example, A4 size document is 8dot / m
If you read in a color representation of m resolution and 256 gradations of RGB (red, green, blue), 12 MB per page is required.

In the multimedia structuring method of the present invention, first, the color area extracting unit 110 separates the input multimedia color document image into a portion that can be expressed by a single color and a portion that cannot be expressed. The part that can be expressed in a single color is a text part or the figure / table part expressed in a single color, and the part that cannot be expressed in a single color is a color photograph. Hereinafter, a portion that cannot be represented by a single color is called a full-color area. The color area extraction unit 110 extracts the circumscribed rectangular area of the area in the input multimedia document image 100 where the full-color area exists. Similarly, a single color area is also extracted as a circumscribed rectangular area. The full-color area extracted by the color area extraction unit 110 passes through the color correction unit 111, and then the color image compression unit 112 compresses the color image.

Next, binarization processing 120 is performed using the single color image data extracted by the color area extraction unit 110. By this processing, the data to be processed thereafter is narrowed down to single color data, and the data amount is reduced to 1/3.

The image data obtained through the binarization processing unit 120 is sent to the bibliographic item extraction processing unit 130. Bibliographic information includes titles, author names, UDC classification numbers, purge numbers, pillars, etc. in title pages of articles. The bibliographic items are described in a certain format for each type of paper. Information in this format is described in advance for each type of paper, and Higashino et al .: "Knowledge Representation Language FDL Based on Set Operations of Rectangular Areas and Its Application to Document Image Understanding," IEICE Tech. PRU86-31, 1986 It is possible to extract bibliographic items by using the method described in.

In addition, the chart area extraction processing unit 140 extracts the chart area. The index information extraction unit 141 extracts information that should be a keyword from the graphic region extracted by the graphic region extraction unit 140, and the information represented as an image by the line drawing recognition unit 142 is represented by vector data.

The area excluding the color photographic area, the bibliographical area, and the figure / table area obtained by the above-described processing 110, 130, 140 is the text area.
In process 150, the body region is extracted and divided into lines.

In process 151, the bibliographic item area obtained in processes 130, 141, 150,
Character recognition processing is performed for character patterns in the index information area and body area. In this processing, a character code and font information for expressing a character are obtained from the character pattern. In process 152, the dictionary is collated to determine whether or not the character extracted by the character recognition processing unit 150 is correctly recognized.

In process 160, the coordinates of the line area obtained in process 150 and process 15 are processed.
The elements of the logical structure are extracted using the character code and font information obtained in 1.

The logical structure generation unit 170 generates data for expressing the logical structure extracted in the process 160 in the computer. Processing 11
2, processing 142, processing 152, color image, line drawing,
Characters are separated and extracted, and converted into an expression suitable for each media. The separated document contents are related by the structure generated by the logical structure generation unit.

Through the above processing, the multimedia structured file 180 is obtained from the multimedia color document 101.

Before describing the embodiment of the logical structure extraction unit 160, the principle for extracting the logical structure will be described.

The document structure has a logical structure and a layout structure. The logical structure is a semantic structure of a document such as a chapter or a section, and the layout structure is a representation of a print layout on a paper surface. This section describes a method for extracting the logical structure of a document from the document image using the layout structure of the document.

Literature (Ministry of Education, Academic Affairs Bureau, "Documentation Handbook", Tokyo Denki University Press, pages 22 to 25)
Page, 1965), the logical structure of documents (especially papers) is
(I) title, (ii) author's name, (iii) abstract, (iv) table of contents, (v) symbols used, list of special symbols, (Vi) preface, (vii) main subject, (Viii) conclusion, (ix) Thanks,
It is stated that it should consist of (x) cited documents, (xi) discussion, and answers.

The subject of (vii) is subdivided into chapters, sections, and paragraphs. Further, a multimedia document will include media different from text such as figures and tables. In the literature, these logical structures are necessary for smooth communication through documents.

In the above-mentioned standard ODA / ODIF, two common logical structures and specific logical structures are used when describing the logical structure of a document.
The common logical structure expresses a common logical structure in a certain document class. The document class here is
It corresponds to a superordinate concept of an existing document, and is, for example, "a set of papers published in a journal of the Information Processing Society of Japan".
And so on. In addition, the specific document logical structure represents the logical structure of a specific document.

Figure 2 shows the journal “HITACHI REVIEW” as a document class, and the common logical structure of the articles published in it is expressed in ODA / ODIF. In the figure, 210 represents an order relation, which means that the set of lower components has an order relation. "paper"
200 is composed of "UDC" 210, "title" 220, "author name" 230, "summary" 240, "text" 250, and "reference list" 260 in this order. REP indicated by reference numeral 211 in the figure represents a repeating structure, which means that there are a plurality of sets of constituent elements at the bottom. “Body” 250 is composed of a plurality of “chapter”. Further, SEL indicated by 212 in the figure has the meaning of arbitrarily selecting one of the lower components. The “figure / table” 2513 is optional.

Using "HITACHI REVIEW" above as an example of a document class, the format required to extract its logical structure is explained.

(1) Extraction of chapter and section The line spacing of chapters and sections is wider than the line spacing in the text. Also,
The character fonts used in chapters and sections are different from those used in the text.

(2) Extraction of chapters and sections Following chapters and sections.

(3) Extraction of paragraphs Indentation exists at the beginning of paragraphs.

(4) Extraction of reference list This can be extracted in the same way as the extraction of chapters and sections in (2) above. However, the header "REFERENCE" showing the reference list
S "is centered. Chapters and sections are left-justified.

(5) Extracting each reference The reference list can be viewed as a type of chapter or section. Each reference then corresponds to a paragraph. Ordinary chapter,
The difference with paragraphs in sections is that each reference is a hanging paragraph. That is, in each reference, the first line is left-justified and the remaining lines are indented. Chapters and sections are extracted from multimedia documents based on the knowledge of the logical structure of documents described above. The method used to extract chapters / sections from a multimedia document is shown below.

(1) Separate a multimedia document into a text area and a non-text area. In the non-text area, there are figures, tables, photographs, etc. This process corresponds to the preprocessing part for extracting the logical structure in the multimedia document.

(2) First, pay attention to the layout structure and separate it into the components of the logical structure. For example, if the body part of a page is cut out and the body part is multi-column, it is separated into column units.

(3) Once separated into columns, the logical structure is extracted using the lines and words in the columns as elements. This is because the logical structure related to chapters / sections can be obtained from the line / word level format as described in the previous section.

In this embodiment, as a means for extracting the logical structure of a document, the FDL (Form Definition Language) is used.
age) was used. The format definition language FDL has a function of defining a format of a document and decomposing a given document into each component of the format.

FIG. 3 is a diagram showing a format related to a chapter / section of a document. In FIG. 3, the lines of the document are shown as rectangles.
Each 301 is a line showing the text. 302 is a line indicating a chapter / section. Reference numerals 303, 304, 305, and 306 respectively indicate the Y coordinates of the rectangular area. As mentioned above, chapter and section areas
302 has a wider line space than the text area 301. This is 303,
It expresses that the distance of 304 and the distances of 305 and 306 are wider than other rectangular areas.

Fig. 4 is an example of expressing the formats for chapters and sections in the format definition language FDL. First, in the first three lines, the space between the rectangular areas is described. SPACE of 401 is a predicate for describing a space between rectangular areas. Also,
? YO and? Y1 are variables for storing the coordinates indicating the position of the blank obtained under the following conditions. In 402, when checking a blank, it is specified to check from the side with the smallest Y coordinate direction. In 403, the size of the blank is specified to be 2.5 mm or more. This value is a value calculated based on the knowledge that the line spacing is three times the line height. With the above procedure, the blank coordinates at the top of the rectangular area representing the chapter / section
The coordinates of? Y0 and? Y1 are obtained. In the next four lines, the blank space at the bottom of the rectangular area of the chapter / section is extracted. First 3
The row has the same meaning as described in 401, 402, 403. Four
In the area indicated by 04, the area to search for blanks is narrowed. This is because the same part as the blank extracted in the previous three lines is not extracted again.

FIG. 5 is a functional block diagram of a filing apparatus adopting a multimedia document structuring system which is an embodiment of the system of the present invention. The configuration and operation of the entire device will be described.

This apparatus includes an image scanning unit 501 for reading a document to be structured as a digital image, and a display 50 for displaying an original image and text / partial images of a structured document.
3. A page image storage unit 502 for storing the read document image in page units, a format data storage unit 504 for storing the format information necessary for structuring the document, and a document storage for accumulating the structured document. Unit 505, a document structure analysis unit 506 for performing a structure analysis of the read document image,
It is composed of a character recognition unit 507 for recognizing characters from a digital image formed into a character pattern, and an image processing unit 508 for performing image processing such as expansion / contraction / blinking.

The outline of the processing flow will be described below. Documents to be entered 510
Is set in the image scanning unit 501. Document 51 in the image scanning unit 501
0 is optically scanned, input as image data, and stored in the page image storage unit 502. The image data 110 is composed of binary image data or binarized by setting a certain threshold for the grayscale data of the image. Next, the page image storage unit 50
In order to structure the input image data stored in 3, the data describing the format of the input document is read from the format data storage unit 504. The document structure analysis unit 506 includes a format data storage unit 5
Based on the format data read from 04, the structure analysis of the document image data stored in the page image storage unit 502 is performed. The document structure analysis unit 506 appropriately calls the character recognition unit 507 and the image processing unit 508 according to the format data stored in the format data storage unit 504.

Next, a logical structure extraction method which is a part of the method of the present invention will be described. FIG. 6 is a PAD when the method of the present invention is used.
It is a figure (Program Analysis Diaglam). In the structure analysis of the multimedia document image in this method, first, a character string area is extracted 600.

Next, extraction 601 of the character string area excluding the page number and the pillar portion is performed. In the extraction of the character string area, the area excluding the non-character string area of the figure / table and the page number / column portion is defined as the body character string body area. For this character string body area, column-based area separation 602, line-based area separation 603, and word-based area separation 604 are performed. These areas are separated based on the format information defined in advance. The format information used at this time is the value of the blank area between columns, the space between lines, and the space between words.

The processing of the algorithm for separating text / non-text will be described. In the separation of text and non-text, the knowledge that the character area tends to expand in the row direction when compared to the figure or table area is used. For example, in a horizontally written document, black pixels are blocked in the horizontal direction,
In the vertical direction, a white pixel area appears for each line interval. However, in the figures and tables, pixels are distributed almost in front of the region. Using this knowledge, we apply image processing techniques to preprocessing.

FIG. 7 is a PAD diagram illustrating in detail the extraction of the logical structure. The logical structure extraction processing is performed for each row in the column area. First, a process 701 of selecting the top line as a process target line is performed. Next, a process 702 for finding the line spacing on both sides of the line to be processed in the logical structure is performed. If the coordinate value of the circumscribing rectangular area for each line is obtained before the extraction process of the logical structure, the space between lines can be efficiently checked without performing complicated processing such as image processing. next,
In step 703, when the line spacing on both sides is wider than the line spacing in the text, this line is considered to be a chapter / section.

Next, the chapter / section structuring process is performed. The chapter / section structuring process is a process of separating the text into chapter units or section units.

FIG. 8 is an explanatory diagram of the structuring process of chapters / sections. In the chapter / section structuring process, a process 801 for adding an indesk indicating a chapter / section to the processing target line determined to be the chapter / section in the above-described process 703 is performed. Also, next,
A process 80 for adding an index indicating that the index is the end of a chapter / section to the line before the section title is performed. By using the above processing, it is possible to separate each chapter / section. The chapter / section area can be extracted by the index added in the above-described two processes 801 and 802.
Paragraph separation processing is performed for this area.

Indentation (indentation) information is used in the paragraph separation process. Indentation is general formatting information for paragraphs.

FIG. 9 details the paragraph separation process. In the paragraph separation process, first, step 901.
Then, the line to be processed is the first line of the area separated into chapters and sections. The line to be processed is
Switch to the next line.

In step 902, the space on the left side of the row to be processed is checked for the area extracted as the chapter. The space on the left side is the indentation information. In the determination processing 903, it is determined whether the left space is lower than the area extracted as the chapter. If it is confirmed here that the indentation is being performed, the determination processing 904 is performed. In the determination processing 904,
If this line to be processed is the first line in the chapter / section, the line to be processed is the first line of the first paragraph, and otherwise,
An index is added to the line before the line to be processed as the first paragraph. This processing needs to be performed on the first line of the first paragraph because indentation may not be performed in some cases.

The above-described processing is performed in order from the top, and after processing one column, the same processing is performed for the next column (right column). At this time, the indexes and flags for indicating the chapters / sections are retained in the state of the previous column.

In this way, since processing is performed in column units, it is possible to extract the logical structure even if one document such as a paper or a journal spans multiple pages.

Further, when the line-by-line extraction is performed, the character recognition process is also performed on the process target line. This is because it may not be possible to extract chapter / section titles only with global format information such as line spacing. A method for coping with such a case will be described with reference to FIG. FIG. 10 is an example of a document in which the logical structure cannot be separated and extracted only by general format information such as line spacing and character spacing. Rectangular area 10 shown in FIG. 10 (a)
01 indicates the last line of the paragraph, rectangular region 1002 indicates the title line, rectangular region 1003 indicates the first line of the first paragraph of the next chapter, and rectangular region 1004 indicates the rectangular region.
This is an area indicating a line following the line indicated by 1003. A rectangular area 1012 shown in FIG. 10 (b) is an area showing the last line of the paragraph, a rectangular area 1011 is an area showing a row before the row shown by the rectangular area 1012, and a rectangular area 1013 is shown by rectangular areas 1011 and 1012. The rectangular area 1014 is an area indicating the first row of the next paragraph included in the same chapter as the line, and the rectangular area 1014 is an area indicating the row following the line indicating the rectangular area 1013. The character string in the rectangular area 1001 in FIG. 10 (a) indicates a chapter, and the rectangular area 1002 in FIG. 10 (b) indicates the end of the paragraph. However, the geometrical positional relationship of each rectangular area is the same in both FIG. 10 (a) and FIG. 10 (b). For this reason, it is difficult to extract chapter and section titles using geometric information such as line spacing and character spacing. On the other hand, the character fonts used for chapter and section titles are larger or different in type than the character fonts in the text. If the above structural analysis processing is performed using the font information of characters, it becomes possible to have a stronger extraction capability.

By performing the above processing, it is possible to extract the areas such as chapters and sections that are elements of the logical structure. In order to store this in a file, it is necessary to extract the hierarchical relation of the extracted area. Take out this relationship,
The process of storing the tree structure data in the file is performed by the logical structure generation unit.

Next, details of the logical structure generation unit will be described.

Figure 11 shows a typical document format, usually
It spans two pages as shown in FIGS.
Here, 1101 indicates a chapter, 1102 indicates a title included in the chapter, and 1103 indicates a paragraph included in the chapter 1101.
Also, 1104 indicates a chapter, 1105, 1107, 1108 indicate paragraphs, and 1106, 1109 indicate figures. In the prior art, in order to divide these areas, for example, known FD
Using the grammar means of L, (defform chapter block ..... (form chapter block (...)) ..... (form chapter block (...)) ...・ ・) If the chapter describes the inclusion relations of the chapter title and paragraphs, it means that the relation between both the allocation structure and the logical structure is described. However, chapter 1104 and paragraphs 1105,1107,1108
Cannot span chapters in FDL because it spans pages. This is because FDL can describe only the physical layout of the document. Therefore, it is necessary to connect the elements of the logical structure extending over physically separated areas such as pages and columns.

In the logical structure extraction unit, a page image is input, and the area is divided in the order of text body part, column, chapter title, chapter, section. Here, necessary parts as a logical structure are chapters and sections, and purge and columns are elements of an allocation structure. The area extracted at this time is shown in FIG.

FIG. 12 shows an example of the logical structure of a document class. In this figure, the text 1201 is chapter 1202, reference 1206.
”,“ Chapter 1202 consists of chapter title 1203, section 1204, explanatory notes 1206 ”, and“ Explanatory notes 1206
Is composed of FIG. 1207 and description 1208 ”. Each element of this structure indicates a concept common to a plurality of documents such as “chapter” and “section”, not a concept unique to the document. In this embodiment, a language for expressing this common logical structure is set, and this language is used to facilitate registration in the common logical structure relation table. For example, the common logical structure of FIG. 12 can be expressed as follows.

(Deflogic main text (consist-of (chapter reference))) (deflogic chapter (consist-of (chapter description with explanatory text))) (deflogic explanatory text (consist-of (figure description))) (defform chapter Block (logical chapter) ・ ・ ・ ・ ・ ・) (Continued block of the deffom chapter (logical chapter continued)) ・ ・ ・ ・ ・ ・) When the document spans multiple pages, the relationship between the elements of the separated logical structure is extracted. I couldn't.

By doing so, it is possible to describe more easily than the case of describing the procedure for extracting the logical structure using only the area division procedure.

FIG. 13 shows the relationship registered in the common logical structure table. This common logical structure table is a table showing the parent-child relationship of the common logical structure, and links 1212 to 1217 in FIG. 12 correspond to the parts 1212 to 1217 in the table in FIG. 13, respectively. For example, the link 1211 indicating the relationship between the text and the chapter in FIG. 12 indicates that “the text is a parent and the chapter is a child” in FIG.

The results obtained by the logical structure area extraction unit are the specific logical structure relation table 1401 and the specific logical structure number count table 140 shown in FIG.
2. Registered in each of the common / specific logical structure relation table 1403 and the object management table 1404. Specific logical structure relationship table 1401
Stores a specific document structure in the input document in a parent-child relationship. The specific logical structure number count table 1402 stores the common logical structure and the number of specific logical structures corresponding to the common logical structure. Count table of this specific logical structure number 1402
The count number is used when creating the name of a specific logical structure. The common / specific logical structure relation table 1403 is a stack, and the element names of the extracted specific logical structure are stored in the corresponding common logical structure. The object management table 1404 shows the element name of the specific logical structure, the name for identifying the extracted image, and the coordinates of two points necessary for expressing the rectangular area.

The logical structure generation unit fills the above tables 1401, 1402, 1403, 1404 according to the following steps.

(1) First, an instance generation process of the highest element name of the common logical structure is performed. The instance generation processing is to number the element names of the common logical structure, generate a new name, and register the name in the common / specific logical structure relation table. For example, in the example of FIG. 13, it can be seen that the highest level of the common logical structure element name is "body", so "body # 1" is added as the specific logical structure element name. Next, common
In the parent column of the specific logical structure relation table, "body" is registered in the child column, and the generated name "body # 1" is registered.

Each form of FDL is called from the beginning, and the following process is performed for the form for which the logical structure is specified.

The logical structure is specified, for example, as follows.

(Defform chapter block (logical chapter) ・ ・ ・ ・ ・ ・) (Continued block of defform chapter (logical chapter continued) ・ ・ ・ ・ ・ ・) (2) When the logical structure is specified in each FDL form , A new instance corresponding to the specified common logical structure element name is newly generated. Next, the designated common logical structure element name is looked up from the common logical structure table to the parent name of this common logical structure element name. The latest child of this parent is common
The specific logical structure relation table is searched, and the corresponding specific logical structure element and the newly created instance are registered in the specific logical structure element relation table in the parent-child relationship. For example,
If the specified logical structure element name is "section",
It can be seen from the common logical structure relation table that the parent is a “chapter”. It can be seen from the common / specific logical structure relation table 1301 in FIG. 13 that the latest instance of this chapter is “chapter # 1”, and the specific logical structure relation table 1401 shows “chapter # 1” and “section # 1”.
2 ”is registered as a parent-child relationship.

(3) If the logical structure is specified to be a continuation of the logical structure, a new instance is not generated,
A logical structure element that specifies the extracted area is newly registered in the object management table as the latest instance area.

As a result of the above processing, the element of the specific logical structure corresponding to the common logical structure is registered in the common / specific logical structure relationship table 1401, and the inclusion relation of each document is registered in the specific logical structure relationship table. Further, in the object management table 1403, the divided areas and the specific logical structure element names 1403 corresponding thereto are registered respectively.

[Brief description of drawings]

FIG. 1 is a functional block diagram showing an embodiment of the system of the present invention, FIG. 2 is a diagram expressing the logical structure of an input document targeted by the system of the present invention in ODA / ODIF, and FIG. 3 is a document. Figure showing the format related to chapters and sections, Figure 4 is the format definition language FDL
FIG. 5 is a diagram showing a format for a chapter / section, and FIG. 5 is a functional block diagram showing a system using the method of the present invention.
FIG. 7 is a PAD diagram for explaining the method of the present invention, FIG. 7 is a PAD diagram for explaining extraction of a logical structure, FIG. 8 is a PAD diagram for explaining structuring processing of chapters / sections, and FIG. 9 is a PAD diagram for explaining the paragraph separation process, FIG. 10 is a diagram showing a document in which the logical structure cannot be extracted only by using geometric information, and FIG. 11 is a diagram showing the logical structure in the logical structure generator. An example of a generated document, FIG. 12 is a diagram showing an example of a common logical structure, FIG. 13 is a diagram showing a parent-child relationship of the common logical structure in a table format, and FIG. 14 is a specific logical structure and a common / specific logical structure. The figure which shows the tabular form required in order to generate a relationship. 110 ... Color area extraction section, 111 ... Color correction section, 112 ... Color image compression section, 120 ... Binarization processing section, 130 ... Bibliographic matter extraction section, 140 ... Chart area extraction section, 141 ... Index information extraction section, 142 ... Line drawing recognition section, 150 ... Body area extraction section, 151 ...
Character recognition unit, 152 ... Word matching unit, 160 ... Logical structure extraction unit,
170 ... Logical structure generation unit.

 ─────────────────────────────────────────────────── ─── Continuation of front page (72) Hiromichi Fujisawa Inventor Hiromichi 1-280, Higashi Koigokubo, Kokubunji, Tokyo Inside Central Research Laboratory, Hitachi, Ltd. (56) Reference JP-A-63-201867 (JP, A)

Claims (7)

[Claims] 1. A multimedia document structuring method for extracting a layout structure and a logical structure peculiar to a document from a multimedia document, the input device inputting the multimedia document as a digital image, which is common to the input document. A first grammar expression storing means for storing an expression written in a first grammar that describes a logical structure hierarchically, and a logical structure such as an extracted chapter / section is extracted as a parent-child relationship,
A means for storing the extracted information in a file in a table format; a second means for storing an expression written in a second grammar that describes the input document as a set of a plurality of rectangular areas;
Grammar expression storage means for storing, in the second grammar, variables that represent absolute or relative sizes of rectangular areas and absolute or relative relationships between the rectangular areas, and The second area is selected from the rectangular area including a description of a search method.
Means for searching a rectangular area specified by an expression written according to the grammar of, and assigning a value determined from the search result to a variable in the expression,
A multimedia document structuring method having means for dividing an area based on an unsolved result of analysis of the same variable. 2. The multimedia document structuring system according to claim 1, wherein one of the elements in the logical structure expressed by the first grammar expression means in the second grammar and the element A multimedia document structuring system characterized in that it has means for associating the divided areas in the second grammar expressing means with one another and combining them into one logical structure. 3. The multimedia document structuring system according to claim 1, wherein the means for storing in the file further includes: for homogeneous data such as texts, images and charts in the document, Having feature extraction means suitable for data,
The multimedia document structuring method, wherein the result of the extracting means is extracted as a rectangular area and attribute information. 4. The multimedia document structuring system according to claim 1, wherein rectangular area extracting means for extracting a rectangular area from the input digital image, layout information such as line spacing, time, and column of the input document. Is represented by relative coordinate values of the rectangular area obtained by the rectangular area extracting means, and means for estimating a logical structure such as a chapter / section from the input document using the layout information. Multimedia document structuring method. 5. The multimedia document structuring method according to claim 1, wherein an area expressing a logical structure obtained by using the logical structure estimating means is extracted as a rectangular area from the input digital image. A multimedia document structuring method characterized by comprising rectangular area extracting means. 6. The multimedia document structuring method according to claim 5, wherein the rectangular area extracting unit further includes inputting the input digital image when the input digital image is expressed in color. A multimedia document structuring system characterized by having a means for separating an area of a single color and an area of mixed colors. 7. The multimedia document structuring system according to claim 5, wherein the rectangular area extracting means further comprises: when the input digital image is represented by a gray image of a single color. A method for structuring a multimedia document, comprising means for extracting, as a rectangular area, an area in which the degree of shading is not clear from an input digital image.