JPH083828B2 - Document image understanding device - Google Patents

Description

Description: BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to a document image processing system, and more particularly to a document understanding system suitable as an input unit of an electronic document file device.

[Background of the Invention]

A conventional electronic document file device merely stores each page of a document as an image, and secondary information for retrieval needs to be externally provided from a code input means such as a keyboard. However, in order to save labor in file input work, it is desirable to automatically read the title, author, etc. described in the document to generate the secondary information. In order to further improve the search, it is necessary to use captions for figures and tables, automatic input of chapter / section titles, or automatic keyword extraction by recognizing the text itself. In addition, dividing the image of the target document into parts such as titles, authors, summaries, text, figures, and photos, and recognizing and encoding the character parts reduces storage space and diversifies search units. It was also requested for.

In order to deal with such a problem in the conventional technology, a method of externally designating a search target area in a document and automatically converting it into search character data by a character recognition device has been proposed. An example of such a method is disclosed in Japanese Patent Laid-Open Publication No. Sho 60-17565, "Image storage and retrieval apparatus" (published on January 29, 1985). However, this method has a problem that it takes a lot of labor to specify the search target area.

In order to deal with the problem of the manual designation method, a method of understanding the content of a document and processing the document based on the understanding result is being researched. For example, the 23rd national conference of the Information Processing Society of Japan Basic research on clipping system "(Proceedings 6C-1, 1981). However, since this document understanding technology is aimed at newspapers, it is possible to efficiently use secondary information such as titles and authors necessary for searching for documents that are standardized to some extent, such as journals and patent gazettes. It is not always suitable for the purpose of extraction. Further, there is no suitable means for improving the extraction method when the secondary information extraction fails.

[Object of the Invention]

An object of the present invention is to provide a document comprehension method for a standardized general document, which can be divided according to its structure and can recognize a character portion when necessary. It is in.

[Outline of Invention]

In order to achieve such an object, the present invention uses a grammar that expresses the structure of an image, and parses the description expressed by this grammar to grasp the structure of an unknown input image. In the above grammar, an image is expressed as a set of rectangular areas, and the absolute or relative size of the rectangular areas and the quantity representing the absolute or relative relationship between the rectangular areas are included as variables. Also, a search method for a rectangular area can be specified. Further, the rectangular area is also expressed as a set of rectangular areas, and by such a hierarchical expression, the syntax of the image can be expressed in detail.

For each type of document, the document formats expressed according to the above grammar are stored in advance in the memory. When an unknown image is input in the syntactic analysis unit, a rectangular area is searched according to the search method specified in the image format, information indicating whether the search is successful, and a parameter determined at the time of search (absolute or absolute value of the rectangular area). Numerical value indicating relative size and absolute or relative relationship between rectangular areas is extracted. The syntax comprehension unit substitutes the numerical values of the above parameters into variables in the image format, and performs the next analysis to sequentially perform the syntax analysis of the image.

Example of Invention

Before describing the embodiments of the present invention, the principle of the present invention will be described. FIG. 1 shows an example of one page of a technical paper having a certain format as an input image. In the following description, a technical paper is taken as an example as a target, but even in other documents, the format of the grammar is slightly different, and the present invention can be applied if a part of the grammar is changed. However, the present invention is not limited to this.

Next, an example of a grammar expressing the structure of a document (hereinafter abbreviated as document grammar) is shown.

(Defform F (form F1 (10 90 10 40)) (form F2 ......) (form F3 ......)) (defform F1 (form F11 (10 90 10 50)) (form F12 (10 90 60 90))) (Defmac LINE-1 (% 1) (point? Y1 (mode IN Y LESS) (point? Y2 (mode OUT Y LESS) (form% 1 (0? W? Y1? Y2)))) This will be described with reference to the example of the figure.

The first defform F ... indicates that the form F is formed by additionally forming the forms F2 and F3 laterally below the form F1 as shown in FIG. In FIG. 1, the portions F, F1, F2, and F3 corresponding to FIG. 2 are shown surrounded by broken lines. Format Four numbers 10 90 10 40 sandwiched by () next to each F1 are the format when the total area corresponding to format F is 100 × 100.
The position of the area of F1 is shown. Here, the coordinate system has the upper left as the origin. The numerical values indicating the region are the minimum value of the X coordinate, the maximum value of the X coordinate, the minimum value of the Y coordinate, and the maximum value of the Y coordinate. When the parameter value is known as in this example, the value may be directly described. Similarly, format F2 and format F3 are also described in rectangular areas.

In the next defform F1 ..., the format F1 is
Indicates that the F12s are arranged vertically. That is, the Y-direction area of the format F11 is 10 to 50, and the Y-direction area of the format F12 is 60 to 90. The positions of the areas of format F11 and format F12 are described in the coordinate system with the upper left of format F1 as the origin. Therefore, the format F has a relative coordinate system.

In this way, the image can be generalized by expressing the format in the rectangular area and hierarchically expressing the area as a set of the areas. Of course, it is not hierarchical and may be described in the absolute coordinate system with the format F as a reference as shown in FIG. In this case, in order to specify the same rectangular area as in FIG. 2, the following may be done.

(Defform F (form F11 (18 82 13 25)) (form F12 (18 82 28 38)) (form F2 ......) (form F3 ......)) After the next defmac LINE-1 (% 1), macro It is a definition. The following three-line description, which is the main body of this macro definition, expresses that the first line from the top of the rectangular area has the format% 1.

(Point? Y1 (mode IN Y LESS)) (point? Y2 (mode OUT Y LESS)) (form% 1 (0? W? Y1? Y2))) where? W is the horizontal size of the format. ,? H represents the vertical size of the format. ? Y1 and? Y2 are variables specified by the search as described below.

point means to search for a point that satisfies a certain condition and substitute it into a variable. The search condition is specified by mode. IN
・ OUT indicates whether the search point is the change point from white to black or the change point from black to white, Y indicates the search axis (X or Y), and LESS
Indicates the search direction. area indicates the area of the search range.

The search method will be described with reference to FIG. 4 by taking the description of the macro definition as an example. (A) shows that lines such as Title ..., Author ... Are present in the format. The coordinate values of these lines in the Y direction, that is, the first and second lines are described in (B) and (C).
And the first line exists from? Y1 to? Y2, and the second line is? Y3.
To? Y4. As described above, (B) is a macro that defines that the format of the first line is% 1, and similarly (C) is a macro that defines that the format of the second line is% 1. You can call these macros as follows.

(LINE-1 F1) (LINE-2 F2) That is, the format of the first line is F1, and the format of the second line is F2. The search condition for the coordinate value? Y1 designated by point in the second line in (B) is IN Y LESS. Therefore, the condition is that the change point from white to black, the search axis is Y, and the direction is LESS, that is, the search is performed from the one having a smaller Y coordinate value. When searching from the one with the largest Y coordinate value, GREATER may be used. The one satisfying these conditions is the upper limit coordinate value? Y1 on the first line. The lower limit coordinate value? Y2 on the first line designated by point on the third line in (B) may be described as a change point from black to white under the above search conditions. That is, the search condition of? Y2 is OUT Y LESS.

Next, (C) which defines the second line in the format will be described. Since the second line is a line next to the first line, the lower limit? Y2 of the first line is searched, and? Y3 indicates the area of the search range by area. That is, by setting the rectangular area to be searched as 0? W? Y2? H, the same search as in (B) can be performed from the lower limit of the first line.

In understanding a document, an expression written in accordance with a grammar is referred to, and it is sequentially checked whether or not the rectangular area described therein exists in the document. When a rectangular area including a variable is searched for, a numerical value of the variable is obtained, and thereafter, the numerical value is substituted for the variable and used.

Next, the calculation between the rectangular areas will be described. In an actual document, an area having a shape other than a rectangle also appears. FIGS. 5A and 5B are examples of regions having shapes other than rectangles. Further, (C) shows an example in which one rectangular area is separated into two rectangular areas. 5 (A) and 5 (B) can be considered as the sum or difference of two rectangular areas, as indicated by broken lines. Further, in (C), if it is considered that two rectangular areas are connected and virtually combined into one rectangular area, the expression becomes simple. In order to enable calculation between such rectangular areas, virtual transfer of areas is defined as follows.

(Map & form F (space? W? H) (position ((? X0? Y0) (? Xmin? Xmax? Ymin? Ymax)) (...))) Figure 6 shows the meaning of this definition. space
Indicates that a new format F is set, and a rectangular area of width? W and height? H is set, and transfer is performed in this area. position
Represents the upper left coordinates of the rectangular area of the transfer destination. The transfer destination rectangular area indicated by four values (? Xmin? Xmax? Ymin? Ymax) is copied to the above transfer destination.

This virtual transfer will be specifically described with reference to FIG. It is assumed that the actual format to be analyzed is arranged as shown in (A). This is called a multi-column or double column. The formats F1 and F2 are spatially arranged side by side, but semantically they are vertically aligned as shown in (B). The operation between such rectangular areas can be expressed by (map & form F (space 50 60) (position ((10 10) (10 40 10 40)) ((10 40) (40 70 10 30)))) . The virtual format shown in (B) is spac
A rectangular area having a width of 50 and a height of 60 is set by e. Then, the relationship between (A) and (B) is expressed as (position ((10 10) (10 40 10 40)) ((10 40) (40 70 10 30))). Rectangular area in (A) (10 40
10 40) is transferred to the area having the origin of (10 10) in (B).

By combining the virtual transfer described above, a region having a complicated shape as shown in FIG. 5 can be expressed by an operation between two or more rectangular regions. For example, FIG. 5 (A) can be expressed as a case where two rectangular areas having different sizes are adjacently transferred.

As can be seen from the above description, in the document grammar proposed by the present invention, the structure of a document is grasped as a combination of rectangular areas and the relationship between the rectangular areas is expressed by the grammar, so that the expressive power of the document is increased and It is possible to describe a target that has been difficult to handle in the past, such as when the number of lines in is indeterminate or when a rectangular area appears or not. Therefore, a wide variety of documents can be analyzed.

Hereinafter, embodiments of the present invention will be described in detail with reference to the drawings.

FIG. 8 is a block diagram showing the configuration of an apparatus that employs the image understanding method according to the embodiment of the present invention. In the present embodiment, an image to be understood will be described for a document, but the present invention can be applied even when a general image, that is, a grayscale image such as a figure or a photograph is included. Each unit of the device is connected to the bus 1, and the entire operation is controlled by the control unit 2. Document 3
The above information (document image information) is photoelectrically converted and digitalized by the scanner 4 to form a digital image, which is stored in the memory 51 via the bus 1. Memory 51 will be described later 52,5
It forms a part of the memory 5 together with 3,54,55. Instead of obtaining the digital image 51 from the scanner 4, the digital image 51 may be read from a digital image file device such as an optical disk. Further, in the following description, it is assumed that one pixel is binarized into one bit, but one pixel may be represented by multiple values, or color information may be provided by photoelectric conversion by a color scanner. The document image is stored in a normalized image memory 52 obtained by performing known position correction processing, inclination correction processing, and the like by the control unit 2.

It is assumed that the format data of the target document written according to the grammar described above is stored in the memory 53 in advance.
The control unit 2 uses the format data to perform the document understanding process of the normalized image. Here, the document comprehension process is to decompose into a plurality of rectangular areas and classify each of the areas. Among the areas obtained as the result of document understanding, the area of a predetermined area as a search target area is sent to the character recognition unit 6 to recognize the internal character pattern. Generally, the original document image has a complicated shape, but since the area obtained as a result of the document understanding has a rectangular shape, it is possible to easily cut out and recognize the characters by a known method. A character code string obtained as a character recognition result or a character code string edited from the character code string is search information of an input document. The search information of the input document obtained as described above is output to the file 7, and the digital image of the document is output to the file 8. When outputting the digital image of the document to the file 8, it may be separately output in units of a plurality of decomposed rectangular areas. Further, the file 7 and the file 8 may be the same.

The details of the document understanding process are described below. 9 and 10
The figure is a diagram for explaining the flow of document understanding processing. The process flow is written in PAD (program Analysis Diagram) format. The document image outline is extracted with 100, and the memory 5
Store in 4. A known method may be used for the contour extraction. Instead of the contour extraction, a so-called connected region extraction method may be used. The maximum value and the minimum value Xmin (i) Xmax (i) Ymin (i) Ymax (i) of the X coordinate and the Y coordinate are extracted from each contour i extracted in 200. The circumscribed rectangle of the contour i is obtained from these four numerical values. 300, 400, and 500 are initialization, main body, and end determination of the syntax analysis process, respectively.

At 300, the format data stored in the memory 53 is copied to the work memory 55, and various tables and program internal variables are initialized.

The main body 400 of the parsing process is composed of 410 to 460. 410 controls to repeat the processes of 420 to 450 until the end determination is made in 460. At 420, the statement in the format data is retrieved. An unprocessed statement is a line in which some of the variables contained therein have undetermined values, or the corresponding document area has not yet been determined. 430 is a judgment to skip the processing of 440 when there are no unprocessed statements left. In this case, the end determination is made. 42
If the statement fetched at 0 is an unprocessed statement, 440 processing is performed. Reference numeral 440 is a part for determining the type of statement and branching, and the content of processing changes according to the type of statement. In Figures 9 and 10 and the description below, only the case of the form statement, that is, (form F0 (? Xmin? Xmax? Ymin? Ymax) (shrink? X? Y)) is described. Statement-specific processing is performed.

Here, the term (? Xmin? Xmax? Ymin? Ymax) of this expression represents the area of the statement to be fetched. That is,
It represents the minimum and maximum values of the X and Y coordinates of the region. Also, the term (shrink? X? Y) indicates that the size of the area is normalized by ignoring the character components whose size in the X direction is? X or less and whose size in the Y direction is? Y or less. Represent This will be described with reference to FIG. 11 (C). Originally, in (C), the statement enclosed by the broken line is taken out, but since there is (shrink 5 5), the character component in the upper left is Is ignored and the area enclosed by the solid line is extracted. Here, the ignored character component corresponds to i = 5 in FIG. 12 (B). Therefore, its size is 26-22 =
4 and the Y direction is 16-12 = 4.

441 to 448 of FIG. 10 are parts for processing the predicate form. 44
In 1 it is checked whether or not the format name F0 is registered. If it is not registered, then in 442 F0 is registered in the format table. In 442, the character string written at the position of variable name? Xmin,? Xmax,? Ymin,? Ymax,? X,? Y is checked whether it is a variable or a numeric value, and if it is a variable, it is registered. Is registered in the variable table. If the variable is already registered, the value is checked to see if it is fixed. If not, the form process ends (in this case, this statement is unfinished). If confirmed, rewrite the variable name in the statement with the above numerical value.

As a specific example, when? Xmin = 0,? Xmax = 90,? Ymin,? Ymax: unregistered? X = 5,? Y = 5, the above statement is (form F0 (0 90? Ymin? Ymax) (Shrink 55)) is rewritten and the variables? Ymin and? Ymax are registered in the variable table, and the values are undetermined.

At 443, it branches depending on whether all the variable names in the statement have been rewritten to numerical values, and when all have been rewritten to numerical values, the form execution processing of 444 is performed. Details of form execution processing are represented by 445 to 448. Reference numeral 445 indicates that the following processing is repeated for the contour i extracted in 200. In 446, the minimum value and the maximum value Xmin (i) Xmax (i) Ymin (i) Ymax (i) of the X coordinate and the Y coordinate of the contour i are set in the variable? Xmin? Xmax? Ymin? Ymax? X? Y in the statement. ? Xmin <Xmin (i) <Xmax (i) <? Xmax? Ymin <Ymin (i) <Ymax (i) <? Ymax? X <Ymax (i) -Xmin (i)? It is determined whether or not the contour satisfies Y <Ymax (i) -Ymin (i). In 447, when the above condition is satisfied, the contour i is registered in the F0 component table. In 448, when there is no contour satisfying the above conditions, an analysis failure flag is set.

As described above, by the processing of 441 to 448, it can be detected that the structure corresponding to the statement form in the format data exists in the input image. The same applies to statements other than from. In the case of from, there is no output data, but depending on the statement, there are cases in which the parameters found during analysis are assigned to the variables in the statement, and the result is used in other statements.

At 450, the parsing failure flag is checked and if the parsing fails, it goes back and tries again. In this case, the variable in which the parameter is substituted in the parsed statement is rewritten to the previous state, and control is performed to search another possibility.

The 460 detects if the parsing failure flag is not set, or if there is a parsing failure flag after a backtracking retry,
Determine the end.

Reference numeral 500 is a part for passing the data obtained as a result of the analysis to the outside. The data to be transferred to the outside includes the coordinates on the document of the rectangular area detected corresponding to the format name.

If parsing fails for a statement with the parsing-failed flag set, this document is incomprehensible and will be rejected. For example, the final result or the intermediate result of the document understanding is displayed on the console 9 and is corrected man-machinely.

Next, the contents of the form execution process will be specifically described with reference to FIG. Fig. 11 (A) shows the noise component in the image. And the case where the characters 1, A, 2, B components are present.

In (B), the parameter when executing the from statement is (form F (20 80 10 50) (shrink 0
0)) In (C), the parameters at the time of execution of the form statement are (form F (20 80 10 50) (shrink 5
This is the case of 5)). As shown in the figure, in the component table of format F, in the case of (B), the noise component and the character 1 and A components are registered, and in the case of (C), the character 1 and A components are registered, but the noise component The component is not registered by the shrink specification and is removed. In addition, after executing the form for the rectangular area of the format F, the area can be normalized by the character components included in the area as shown in the figure, and the area size can be flexibly changed according to the content of the image. Can be specified.

Fig. 12 shows how to select contour components when executing from from above.
This will be specifically described. FIG. 12 (A) shows a circumscribed rectangle as a result of processing the contour image shown in FIG. 11 (A) by using FIG. That is, 5 is a noise component, 1-8 is a character component, and 6-8 is a so-called inner contour. Xmin, Xmax, Ymin and Ymax of these components are shown in (B). And form F
Is included in the following formula 20 <Xmin (i) <Xmax (i) <80 10 <Ymin (i) <Ymax (i) <50 5 <Xmax (i) -Xmin (i) 5 <Ymax ( i) -Ymin (i) Judge by whether or not it holds. In this example, the contours i = 1 and 3 hold.

〔The invention's effect〕

As described above, according to the present invention, it is possible to automatically analyze the target document to be stored, and it becomes unnecessary to input the secondary information from the keyboard, or it is significantly reduced. Input is greatly simplified.
Further, even if the structure of the target document changes, there is an advantage that it can be dealt with immediately by changing the format data.

[Brief description of drawings]

FIG. 1 is a reference diagram showing an example of a document, FIGS. 2, 3, 4, 5, 6 and 7 are explanatory diagrams for explaining the principle of the present invention, and FIG. 8 is a document processing method of the present invention. FIG. 9 and FIG. 10 are block diagrams showing the configuration of the apparatus for performing the processing, and FIG. 11 and FIG. 12 are flowcharts for explaining the processing in the control unit 2 in FIG. It is explanatory drawing for doing. 1 ... bus, 2 ... control unit, 3 ... document, 4 ... scanner, 5 ...
Memory, 6 ... Character recognition unit, 7,8 ... File, 9 ... Console.

 ─────────────────────────────────────────────────── ─── Continuation of the front page (72) Inventor Masaji Ejiri 1-280, Higashi Koigakubo, Kokubunji City, Tokyo Metropolitan Research Laboratory, Hitachi, Ltd. (56) Reference JP-A-60-183688 (JP, A)

Claims (7)

[Claims] 1. Storage means for storing in advance a format of a document, which is almost stylized using a grammar for expressing a document image as a set of rectangular areas, and means for photoelectrically converting an input document image into a digital image. , A rectangular area is extracted from the digital image, and each rectangular area in the document format stored in the storage means is
Rectangle area searching means for searching whether or not it corresponds to any of the extracted rectangular areas, and image syntax understanding means for understanding the syntax of the input document image based on the search result, Document image understanding device. 2. The document image understanding apparatus according to claim 1, wherein the grammar uses a variable that represents a quantity representing an absolute or relative size of a rectangular area and an absolute value between rectangular areas. An apparatus for understanding a document image, characterized in that a variable is used as a variable that expresses a relative relationship. 3. The document image understanding apparatus according to claim 2, wherein the rectangular area searching means searches the rectangular area with a variable representing an absolute or relative size of the rectangular area. A document image understanding device characterized by. 4. A document image understanding apparatus according to claim 3, wherein the rectangular area searching means is a rectangular area until a variable representing an absolute or relative size of the rectangular area does not exist. A document image understanding device characterized by searching for. 5. The document image understanding apparatus according to claim 1, wherein the rectangular area of the grammar is a virtual rectangular area generated by performing an operation from a plurality of spatially separated rectangular areas. An apparatus for understanding a document image, including: 6. The document image understanding apparatus according to claim 1, wherein the storage means stores attributes for the plurality of rectangular areas. 7. The document image understanding device according to claim 1, wherein the image syntax understanding means recognizes an image pattern in a rectangular area obtained by a search result of the rectangular area searching means. Document image understanding device.