JPH0821057B2 - Document image analysis method - Google Patents

Description

The present invention relates to a document image analysis method for dividing a document image of a book or the like into a predetermined paper surface configuration and automatically extracting a desired area, and in particular, The present invention relates to a structure analysis method of a document image, which is generated after dividing a basic element such as a character line / character or a chart and the like and an arrangement relationship between the elements forming the document image.

(Prior art) In order to efficiently store / search a large amount of existing document images, transmit images, and to automatically read general books, in order to automatically read general books, a specific character set in advance on a form with a fixed format is specified. Not only is it necessary to read characters from only an image string, but it is also necessary to analyze various document images, separate character areas and chart areas, and automatically extract desired areas. Conventionally, such a structure analysis method of a document image, in particular, as a region division method of a document image, for example, a method of tracking a peripheral distribution of a paper surface composed of character regions and a connected component of black pixels (IEICE Transactions D Vol.J66 NO.1,1983-1,111 pages ~
Page 118). Also, raster scan the document image,
There is a method of structuring from a white / black run length information into a well-coordinated rectangular area (21st National Convention for Information Processing,
7H-1).

(Problems to be Solved by the Invention) In the document image area dividing method as described above, character lines,
Although it is possible to decompose a document image such as a chart into basic elements, it is difficult to obtain the positional relationship of each basic element and the flow of character string information expressed in text. Also,
In the method of structuring white / black run length information into a well-coordinated rectangular area, it is difficult to grasp the overall structure of the document image, so format information and physical parameters of the character lines that make up the document image are used in advance when dividing the area. There is a need to. Therefore, it is difficult to automatically analyze the above-mentioned arrangement relationship of the document constituent elements and the document structure with respect to various document images.

In addition, as a structure analysis method for document images, "Structural analysis of page image based on split detection method" (Technical Research Report of IEICE, Pattern Recognition and Learning PRL85-17, 1985-6, 63)
As described on pages 70 to 70), the constituent elements of the document are determined after segmenting the global region into the local region while alternately extracting vertical or horizontal projection information. However, the above method is performed on the premise of reading characters such as the body of a book. Therefore, if the existence of the column structure found in general documents and the reading of characters in a specific area are presupposed, the layout relationship that forms the document image, etc. is not obtained. It is important to find the elements of the document image and the positional relationship between the elements.

In order to solve the above-mentioned conventional problems, the object of the present invention is to use the attribute values of basic elements constituting a document such as area information and character lines that hierarchically hold the upper and lower or left and right layout relationships as a guideline, and document An object of the present invention is to provide a method of automatically determining an element that constitutes an image and a vertical and horizontal arrangement relationship between the elements as a hierarchical structure.

Another object of the present invention is to provide a structure description method for a document image that can easily detect the flow of information in the text area and the structure of the document by automatically generating the constituent elements of various document images and the positional relationship between the elements. To provide.

Another object of the present invention is to provide a structure description method of a document image for easily extracting a specific area determined according to the purpose.

(Structure of the Invention) The structure of the present invention is an area dividing means for dividing an area to be divided into a small area from a large area while alternately defining a vertically or horizontally dividing direction that is uniquely determined. , According to the attribute information of the basic elements such as the area information and the character line that hierarchically holds the vertical or horizontal layout relationship determined by the division direction, sequentially structuring from a plurality of basic elements,
And a document structure generating means for generating and determining the elements constituting the document image and the arrangement relationship between the elements as a hierarchical structure.

(Examples) Examples of the present invention will be described below with reference to the drawings.

FIG. 1 and FIG. 2 are examples used to explain the structures of document images written vertically and horizontally, respectively.

In the figure, black circles indicate characters, and a rectangular area indicated by diagonal lines is an element such as a figure, a table, or a photograph. If a conventional document image area division method or line extraction method is used, the symbol Si in FIGS. 1 and 2 (i = 1, ..., 7 in FIG. 1, i = 1 ,. The character line area shown in 15) or the area such as the figure / table / photo shown by the symbol F ₁ in FIG. ₁ (hereinafter referred to as pixel description area) can be extracted.

Next, focusing on the flow of sentence information, in the case of vertical writing shown in FIG. 1, normally, in a vertical character line, the sentence information flows from left to right, and each character in the character line is written from top to bottom. Text information flows to. That is, the arrangement relationship of each character line in FIG. 1 has a left-right relationship. Also, the pixel description area F ₁ is a character line.
There is an arrangement relationship such as being above S ₅ , S ₆ , and S ₇ . Therefore, when the text area indicated by Ti (i = 1, 2) in the figure of FIG. 1 is detected, two text areas T ₁ and T ₂ composed of character lines having a left-right relationship have a left-right relationship, and a pixel description is made. It is easy to see that the area F ₁ and the text area T ₂ have a vertical relationship. Therefore,
By extracting the layout relationship described above, for example, from the text area T ₁ to T ₂ in sequence, the characters in the character line are extracted and converted into a character code, or the text under the pixel description area F ₁ It is possible to easily extract only the region.

Similarly, in the case of horizontal writing as shown in FIG. 2, information normally flows from right to left for each character in a horizontal writing line, and the text area consisting of each horizontal writing line moves from top to bottom. Information flows. For example, each character line Si (i = 1, ...
15), character line S ₁ to character line S ₅ and character line S ₆ to character line S ₁₀ and character line S ₁₁ to character line S ₁₅ are respectively from the character lines having a hierarchical relationship to the text areas T ₁ and T ₅ It is formed from T _6. In addition, as a structure similar to two columns, the text area
Since T ₅ and T ₆ exist and there is a left-right relationship as the flow of information, the text area T ₄ has a horizontal relationship with the text areas T ₅ and T _6.
Can be seen as being formed.

Further, as shown in FIG. ₁ , when there are character lines having different character pitches in the text region T ₁ , the text region T ₁ composed of the character lines having the upper and lower relation is further added to the text region T _1. Even if it is decomposed into T ₂ and T ₃ , the upper and lower relations are established.

As described above, when expressing the layout relationship of the constituent elements of the document image and the flow of the sentence information, the relationship between each element is defined as a vertical relationship and a left-right relationship (in the case of vertical writing) or a left-right relationship (in the case of horizontal writing). It can be seen that this is possible by hierarchically detecting and generating.

FIGS. 3 (a), (b), and (c) are examples of a method of hierarchically dividing an area while alternately defining vertical and horizontal division directions used in the present invention.

One method of dividing the area is described in "Structural analysis of page image based on split detection method" described above. Therefore, in this description, details are omitted, and FIG.
With reference to (b) and (c), description will be made centering on the point that the area division method is hierarchically divided while maintaining the vertical and horizontal relationships. Although the above method uses the feature amount obtained from the projection information, the area division method used in the present invention is not limited to this, and run length information or the like or a combination thereof may be used.

In FIG. 3A, the area P of the document image to be divided into areas includes the characters indicated by black circles and the pixel description areas such as rectangles and diagonal lines, and the vertical writing document shown in FIG. It has a similar structure to the image.

Symbol used in FIG. 2 R _i (Lev) (Lev = 1,2,3, ..., i
= 1,2,3, ...) indicates a region obtained by the hierarchical region segmentation process using the projection distribution (the shaded figure in the figure), and the symbol Lev indicates the segmentation level. To do. The division level Lev represents not only the hierarchical depth but also the direction in which the projection information is obtained. That is, the division level of a plurality of areas divided by the projection information in the horizontal direction.
Lev has an odd value, and the division level Lev of a plurality of regions divided by the projection information in the vertical direction has an even value. Further, it is apparent that the vertical relationship (horizontal relationship) is preserved in each of the plurality of regions divided by the horizontal (vertical) projection distribution.

First, the horizontal projection distribution H ₁ is applied to the analysis target region P, and the region R ₁ (1) is obtained. Next area R ₁ (1)
The vertical projection distribution V ₂ is applied to the region R ₁ (2),… R
₅ (2) is obtained. Here, it is clear that the five areas having the division level 2 sequentially satisfy the left-right relationship. Here, how to divide the five regions is to determine the feature of each region and the feature amount (blank value or correlation ratio) between the regions as the feature (for example, identifier) of the parent region R ₁ (1). 5
, R ₅ (2) are classified according to the characteristics of the individual regions R ₁ (2), ...

In the case of FIG. 3 (a), the region is divided into five regions, and the region R ₁ (2) has not been determined as an identifier, and R ₂ (2) to R ₅
An identifier called a character line candidate is added to (2) and stored.

Region segmentation uses the vertical search technique,
The region R ₅ (2) is taken out as the region to be divided next,
Similar processing is repeated. When the horizontal projection distribution is applied to the region R ₅ (2), a plurality of character candidate regions are obtained, so at this point the division of the region R ₅ (2) is stopped,
A plurality of character candidate areas are also stored. Similarly, the regions R ₄ (2), R ₃ (2), and R ₂ (2) are sequentially applied with the horizontal projection distribution, and the same processing as in the case of the region R ₅ (2) is performed.

Next, the horizontal projection distribution H ₂ is applied to the region R ₁ (2) as shown in FIG.
₁ (3) and R ₂ (3) are obtained, and the same processing as described above is performed.

In the case of FIG. 3B, the region R ₁ (3) and the region R
₂ (3) is added with an undetermined identifier and stored. At this time, the region R ₁ (3) and the region R ₂ (3) have a vertical relationship, and their parent region is R ₁ (2). Then region R
₂ (3), the vertical projection distribution V ₄ is applied to the three character line candidate regions R ₁ (4), as shown in FIG.
R ₂ (4) and R ₃ (4) are obtained.

Also, if the same vertical projection distribution as that of the region R ₂ (3) is applied to the region R ₁ (3), there is only one distribution, so it cannot be further divided, and the region size and other factors can・
An identifier called a pixel expression area such as a table or a photograph is given.
When the vertical search is completed by repeating the above operation, the tree structure of the area information shown in FIG. 4 is generated.

The area division result shown in FIG. 4 is generated corresponding to the document image shown in FIG. 3 (a), but FIG. 3 (a) has a structure similar to that of FIG. Because I have
The following description of FIG. 4 will be given corresponding to FIG.

In FIG. 4, the area information is represented by a circle in the figure,
The symbol S _i represents a character line, and the symbol F _i represents a pixel representation area,
Black circles indicate character area information. Further, a circle to which no symbol is added represents undetermined area information.

Further, in the figure, Lev represents a division level, and when the division level is an odd number, a vertical relationship is established between the areas, and when the division level is an even number, a horizontal relationship is established between the areas.

Here, in the hierarchical representation with the tree structure in FIG. 4, the relation between the division level i and the division level i + 1 (i = 1, 2, ...) Is an inclusive relation, and the regions within the same division level have a left-right relation ( (Indicated by → in the figure) or a vertical relationship (indicated by ↓ in the figure) is established.

Next, an example of the attribute value of the area information described in FIG. 4 will be described with reference to FIG.

The classification name shown in FIG. 5 indicates the analysis target area character line, pixel expression area, line segment, and the like. The position / size represents the position / size of the area. The logical classification name is, for example, as described in “Structural analysis of page image based on split detection method” by the same applicant as described above, in the text, chapter title, and “adaptation based on minimum variance criterion” by the same applicant. Type character separation method ”(The Institute of Electronics and Communication Engineers, D'85/8 VOL.J68-D.No.8, page 1497 to page 1504). It is used when classifying including the properties of. The inter-region distance indicates a blank size between adjacent regions at the same division level.

Here, as described with reference to FIG. 1, it is necessary to generate a description of the document structure including the flow of text information from the region division result shown in FIG.

That is, attribute values such as classification symbols are determined for the undetermined area shown in FIG. 4, or, for example, the text area T ₁ shown in FIG. ₁ is the area shown as the fourth area as new area information. It is necessary to generate from the division result.

FIG. 6 shows an example in which a document structure is automatically generated from the area division result shown in FIG.

The description generation of the document structure shown in FIG. 6 is an example in which a classification name is used as an attribute value of a basic element such as a character line, and the classification name T _i (where i = 1, 2, ...) Is a sentence. It is a classification name indicating the area.

Here, the structuring condition is vertical writing in the case of FIG. Further, it is assumed that only a plurality of regions having the classification name S _i (character line) continuously are generated as a new text region.

The vertical writing / horizontal writing determination may be given in advance,
It may be automatically determined using a conventional technique. Also, the classification name S _i
It is not necessary to create a new area when the plurality of areas with is the only parent area.

First, as a search for area information, the basic element with the largest division level (area R ₁ (4), R in the diagram of FIG. 4) is used.
₂ (4), R ₃ (4)) and their parent regions (R in the diagram of FIG. 4)
₂ (3) only) is taken out.

Next, the vertical writing / horizontal writing information and the division level Lev in the structured condition are checked. When the division level Lev is an odd number, a plurality of areas having the same parent area are arranged by connecting them in the order in which the vertical relationship is established by using the vertical relationship pointers shown in FIG. On the other hand, the split level Lev
When is even, the left-right relationship is established in vertical writing (shown by ← in FIG. 6) when viewed from the flow of text, and the left-right relationship is established in horizontal writing. Therefore, the same parent area described above
A plurality of regions having R ₂ (3) (R ₁ (4) in the diagram of FIG. 4,
R ₂ (4) and R ₃ (4)) are arranged by connecting them in the order in which the left-right relationship is established by using the left-right relationship pointer shown in FIG. (R ₃ (4) → R in the diagram of FIG. 6)
₂ (4) → R ₃ (4)) The above vertical writing / horizontal writing information and division level Le
It goes without saying that the processing equivalent to the rearrangement by v can be easily performed by using the left-right relation pointer and the up-down relation pointer of each area information shown in FIG.

Next, a text area, which is a structuring condition, is generated.
In the example of FIG. 4, all three areas are classified names S _i (i = 5,
6,7), the parent area R ₂ (3) is directly added to the classification name T ₂ as a text area, and the division level Lev
And the number of child areas (which does not change in this case) are updated.

Here, in the case of FIG. 4, the structuring of the division level 4 is completed.

Next, the area of division level 3 (area R in FIG. 6)
₁ (3), R ₂ (3)) and its parent area R ₁ (2) are taken out. In the area of the division level 3, there are character areas indicated by black circles in the drawing of FIG. 6, but since their parent areas are the character lines that are the basic elements, they are not extracted.

Similarly, there are two regions R ₁ (3) and R of division level 3.
_{2 The} structuring conditions described above in (3) are checked. In this case, the regions R ₁ (3) and R ₂ (3) (with the classification symbol T ₂ already added) are attached with the hierarchical relation pointers, and the classification names F ₁ and T ₂ are new regions. Is not generated,
A classification name F * T (where F * T indicates a mixture of a pixel description expression area and a text area) is added to the parent area R ₁ (2). Here, the structuring of the division level 3 ends.

Next, the area of division level 2 (area R in FIG. 6)
₁ (2), R ₂ (2), R ₃ (2), R ₄ (2), R ₅ (2))
And its parent region R ₁ (1) are retrieved.

Similarly, the structuring conditions described above are examined and left-right relationship pointers are attached in the order R ₅ (2) through R ₁ (2) (right-left relationship). Then their classification names S ₁ , S ₂ , S ₃ , S ₄ , F ₁ * T ₂
Are examined in sequence. In this case, the classification names S ₁ , S ₂ , S ₃ , and S ₄ satisfy the structuring condition of the text area, and
Since R ₁ (1) includes an area having the classification name F * T, an area having the classification name T ₁ shown by a rectangle in FIG. 6 is generated as a new area. Then the region R with the classification symbol S _4
2 The left-right relation pointer between (2) and the area R ₁ (2) having the classification name F * T is separated, and the left-right relation pointer of the area R ₂ (2) is set to NULL.) Classification symbol T ₁ The address indicating the area R ₁ (2) is put in the left-right relation pointer of the area having. Furthermore, classification symbols S _1, S _2, S _3, with S address indicating a region having a distinguished name T ₁ parent region pointer indicated ₄ in FIG. 5 for each region showing is stored, classified name T ₁ 5 of the area showing
The child area pointer shown in the figure stores an address indicating the area of the classification symbol S ₁ as the leading child area. Next, the division level of the area having the classification symbol T ₁ is set to the same division level 2 as the child area classification names S ₁ ... S _4, and other attribute values are set. Then, the newly generated classification symbol T ₁
From the region having the left-right relationship (in this case, the region R ₁ (2) having the classification symbol F * T is taken out, and the structuring conditions described above are similarly examined. In this case, the parent region R _{1 in} FIG.
The classification name F * T is given to (1).
Hereinafter, by performing the same operation, the document structure shown in FIG. 6 can be described.

By using the tree structure showing the description generation result of the document structure as shown in FIG. 6, vertical writing sentences are read in a predetermined order, and a specific area, for example, below a pixel expression area near a predetermined size is displayed. It can be seen that certain sentences can be easily extracted and read.

FIG. 7 is an example showing a result of performing area division on the horizontally written document image shown in FIG.

The area division result shown in FIG. 7 can be realized by using the conventional technique as described in “Analysis of page image structure based on split detection method” by the same applicant. Further, in the figure, the character area is omitted.

FIG. 8 shows an example in which the description of the document structure is generated for the area division result of FIG.

The description generation of the document structure shown in FIG. 8 is an example in which the classification name (S _i , T _i, etc.) and the value of the character pitch P are used as basic elements such as character lines.

The structured condition is horizontal writing. Furthermore, the classification names are consecutive
Has S _i and the character pitches are almost equal (threshold processing)
When the condition is satisfied, a new text area is generated.

The process is the same as in the case of FIG. 6, but when the division level is an even number, the left / right relation pointer is set based on the left / right relation, for example, the region having the classification name T ₅ and the region having the classification name T ₆ in the figure. The child area pointer in the point and area information stores the address of the first area that satisfies the left-right relationship (for example, the child area pointer of the area having the classification name T ₄ is the classification name T ₅
Area) is different.

In FIG. 8, when the character pitch P is not used,
The classification names S ₁ , S ₂ , S ₃ , S ₄ , S ₅ in the figure are the same text area (in the figure
T ₁₎ and is represented, so that the area having a distinguished name T _2, T ₃ is not generated.

Also, it is easy to see that the text areas having the classification names T ₁ and T ₄ have different internal structures.

That is, all the elements of the text area having the classification name T ₁ have a vertical relationship, whereas the text area having the classification name T ₄ is composed of two text areas having a left-right relationship. The elements of the text area have a hierarchical relationship.

In this way, as shown in FIG. 8, by using the description generation result of the document structure according to the present invention, the flow of the text information can be easily detected at each basic element level, and in addition, it is possible to detect the flow at a specific portion. It is easy to see that there are sets of configurations.

Although an example of using the classification name and the character pitch is shown as the structuring condition shown in FIGS. 6 and 7, the present invention is not limited to this.

FIG. 9 is a block diagram showing a specific embodiment of the present invention. In the figure, 1 is a document image memory for storing a document image as quantized image information. Reference numeral 2 is a region dividing unit. The area dividing unit 2 divides the document image memory 1 into a small area from a large area while maintaining the layout relationship of the vertical relationship and the left-right relationship in the document image memory 1 as described in FIG. It has a function, and area information obtained in the area dividing process as shown in FIG. 4 or 5 is sequentially stored in the structured data storage unit 4.

Further, the area dividing unit 2 determines whether the text image is written vertically or horizontally based on the area division result, and stores the result in the vertical / horizontal information storage unit 2.

Note that the pointer-related values (parent area pointer, child area pointer, vertical relation pointer, left-right relation pointer, etc.) of each area information stored in the structured data storage section 4 are stored in the structured data storage section of each area. Suppose it is represented by a relative position. Further, each area has a structured data storage unit 4
It is also assumed that the relative position of itself in the inside is also stored in the relative position pointer as the attribute value of the area at the same time. Further, the relative position counter 11 stores the relative position next to the last region stored in the structured data storage unit 4 from the region division unit 2 as an initial value, and the relative position counter 11 reads the value. When issued, it shall be counted up in units of attribute value of each area.

Next, the area information control unit 4, as shown in FIG.
An area to be structured having the largest division level (hereinafter referred to as a child area corresponding to a parent area, which will be described later, first becomes a basic element area) and structured data in which the parent areas are paired. At the same time as it is retrieved from the storage unit 4, the relative position of the area connected to the vertical relation pointer or the horizontal relation pointer of each area is stored using the division level and the vertical writing / horizontal writing information of the vertical / horizontal information storage unit 3 described above. . Further, the relative position of the child area first searched from the parent area is stored in the child area pointers of those parent areas, and is stored in the target data storage unit 6.

Next, the area information control unit 5 reads the parent area and the plurality of child areas from the target data storage unit 6 and transfers them to the area determination unit 8.

As described with reference to FIGS. 6 and 8, the structured inspection unit 8 uses the condition storage unit 7 in which the structured conditions for the attribute values of the plurality of child regions are stored according to the attribute values of the plurality of child regions. Will be inspected sequentially. When it is necessary to generate a new area when the above inspections are sequentially performed, the parent area and the child area described above are transferred to the area generation unit 9. The area generation unit 9 generates a new child area using the attribute values of a plurality of child areas to be structured among the plurality of child areas, and the new child areas are generated as shown in FIGS.
As described with reference to the figure, the relative position of the predetermined child area to be structured is set to the child area pointer of the new child area, and the new child is set to the parent area pointer of the plurality of child areas to be structured. The relative position of the area is separated from the vertical or horizontal relationship between the plurality of child areas to be structured and the uninspected child area. It is assumed that the value of the relative position counter 11 is read and set to the relative position pointer of the new child area.

The relative position of the parent area is stored in the parent area pointer of the new child area.

Upon completion of the above-mentioned processing, the area generation unit 9 writes a plurality of areas structured as described above among the plurality of child areas at predetermined relative positions in the structured data storage unit 4, The newly generated child area, a plurality of uninspected child areas, and their parent areas are sent to the structured inspection unit 8 again, and the same processing as described above is performed. Next, the structured inspection unit 8 sequentially inspects → If it is not necessary to generate a new region for a plurality of child regions, the plurality of child regions and their parent regions are transferred to the attribute determination unit 10. .

The attribute determining unit 10 determines the attribute value of the parent area as described with reference to FIG. 6, and writes the parent area and the plurality of child areas at predetermined relative positions in the structured data storage unit 4.

Next, the area information control unit 5, as described above, if a pair of the parent area having the structured division level and the plurality of child areas remains in the target data storage unit 6, then those pairs are paired. Are sequentially transferred to the structured inspection unit 8.

On the other hand, if the target data storage unit 6 is empty, the division level is reduced by one, the pair of the area to be structured and its parent area is taken out from the structured data storage unit 4, and The same operation is performed until the area is taken out as a structured object, and as a result, the structural description of the document stored in the document image memory 1 is automatically generated in the structured data storage unit 4.

(Effect of the Invention) As described above, according to the document image analysis method of the present invention, the area information in which the vertical or horizontal layout relationship is hierarchically held and the attribute value of the basic element forming the document are used as guides. The structure of the document including the flow of text information is extracted by automatically determining the constituent elements of the document image and the positional relationship between the elements as a hierarchical structure. Therefore, it is possible to easily extract the specific area determined according to various purposes.

[Brief description of drawings]

FIG. 1 and FIG. 2 are diagrams for explaining the structures of document images written vertically and horizontally, respectively. FIG. 3 is an example of a document area division method in which area division is hierarchically performed while alternately defining vertical and horizontal division directions. FIG. 4 and FIG. 7 show an example of the result of area division of the document image of FIG. 1 and FIG. 2, respectively. FIG. 5 shows an example of area information. FIGS. 6 and 8 are examples of automatically generating the document structure from the area division results shown in FIGS. 4 and 7. FIG. 9 is a logical block diagram showing a concrete example of the present invention. In the figure, 1 is a document image memory, 2 is a region dividing unit, 3
Is a vertical / horizontal information storage unit, 4 is a structured data storage unit, 5 is a region information control unit, 6 is a target data storage unit, 7 is a condition storage unit, 8 is a structured inspection unit, 9 is a region generation unit, 10 Is an attribute determining unit, and 11 is a relative position counter.

Claims (1)

[Claims] 1. When a document image is divided into a plurality of basic element regions such as character lines, the region to be divided is defined from the large local region while alternately defining the vertically or horizontally divided direction that is uniquely determined. Area dividing means for dividing into small areas, and a plurality of basic elements according to the attribute value of the basic element and a plurality of area information that hierarchically holds the vertical or horizontal arrangement relationship determined by the dividing direction And a document structure generating means for generating and deciding the elements constituting the document image and the arrangement relationship between the elements as a hierarchical structure.