JPH05314309A - Character string direction discriminating method - Google Patents

Abstract

(57) [Summary] [Purpose] Character string direction of a document (vertical writing
Horizontal writing) is automatically determined. [Structure] A reduced image of a document is generated (203), and connected components of character string candidates on the reduced image are extracted (203 to 20).
4). The numbers of the slender vertically connected components and the horizontally connected components are totaled (205), and if the numbers are sufficient, the character string direction is determined by comparing the numbers (20).
6). If the number is insufficient, the connected components are combined into character strings in the vertical and horizontal directions, and a non-histogram of the distance between adjacent connected components is created for each direction (2
07). The distance of the maximum frequency in each direction is compared to determine the character string direction. If it is uncertain, the character string direction is determined by comparing the maximum frequency with the total frequency around it (208). ..

Description

Detailed Description of the Invention

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to a method for automatically discriminating a direction of a character string or vertical writing / horizontal writing of a document from a binary image of the document in an apparatus or system for handling a document image.

[0002]

2. Description of the Related Art In a system such as an OCR which processes a vertically or horizontally written document, when a character string and a text area are extracted from a document image, first, a small candidate area that constitutes the character string is first formed from the document image. The method of extracting the text area by extracting and integrating it is generally adopted, but it is necessary to know the direction of the character string, that is, the vertical writing / horizontal writing of the document, in order to integrate the candidate areas. ..

The following method is known for automatic determination of this direction.

(A) As described in Japanese Patent Laid-Open No. 3-44788, a document image is divided into several blocks, a black pixel peripheral distribution is taken in each block, and the character string direction is determined from its periodicity. How to judge.

(B) Report of the PSU Research Group of the Communication Society of Japan 89-1
14 As described in “Division of Documents with Various Layout Structures and Components”, the distance between the closest components of each connected component is checked in the vertical and horizontal directions, and the sum of the distances is checked. A method in which the direction with the smaller is the string direction.

[0006]

The method (a) uses the marginal distribution and thus is weak against the inclination of the document, and has a layout different from the text even in a portion other than the text area such as a photograph area or in the text area. Processing may not be possible due to the influence of the part (title, etc.).

The method (b) requires an extremely large amount of processing because it is necessary to search for adjacent connected components in the vertical and horizontal directions for all the connected components on the document image. Also,
The effect of non-character parts on the document can be eliminated by separating the characters and other objects from the attributes such as the size of the connected components in advance, but the total distance between adjacent connected components is used. , If there is a title, page number, etc. close to the text, that effect will occur.

In view of the weak points of the conventional method, the present invention aims to provide a new method for surely determining the character string direction of a document with a small processing amount.

[0009]

According to the method of the present invention, a reduced image of a binary image of a document is generated, and a connected component of black pixels as a character string candidate is extracted from the reduced image. Then, by comparing the number of vertically connected components whose aspect ratio or aspect ratio exceeds a certain threshold among the connected components and the number of horizontally connected components, the character string direction or vertical writing / writing
It is to judge whether to write horizontally.

According to a second aspect of the present invention, a reduced image of a binary image of a document is generated, a connected component of black pixels as a character string candidate is extracted from the reduced image, and an aspect ratio among the connected components is extracted. Alternatively, the number of each of vertically long connected components and horizontally long connected components having an aspect ratio equal to or larger than a first threshold is checked. When the number of the vertically long connected components or the number of the horizontally long connected components exceeds the second threshold value, the character string direction is determined by comparing the respective numbers. However, when the number of the vertically long connected components and the number of the horizontally long connected components are each less than or equal to the second threshold value, a process of integrating the connected components as the character string candidates into the vertical and horizontal character strings, respectively. And generating a histogram of distances between adjacent ones of connected components integrated in a character string having a height to length ratio less than or equal to a third threshold value separately in the vertical direction and the horizontal direction, and The character string direction is determined by comparing the distances corresponding to the modal values of.

According to the method of the third aspect of the present invention, in the same manner as the method of the second aspect of the present invention, when the histogram of each direction is generated, the maximum frequency in the histogram of each direction and the vicinity of the distance corresponding to the maximum frequency are generated. Find the total with the distance frequency of. Then, when the ratio of the total in each direction is less than or equal to a fourth threshold value, the character string direction is determined by comparing the distances corresponding to the maximum frequency as in the method of the invention of claim 2.
If not, the direction of the character string is determined by comparing the totals.

[0012]

According to the first aspect of the invention, the binary image of the document is reduced, and the connected components as the character string candidates on the reduced image are extracted. In the case of a document with a general character spacing, characters are fused on a reduced image with an appropriate reduction ratio, but line spacing is not fused, so in a horizontal writing document, there are many horizontally-oriented connected components with a large aspect ratio. In contrast, in the case of a vertically written document, many vertically long connected components with a large aspect ratio appear. Therefore, according to the invention of claim 1, it is possible to determine the direction in which the number is large as the character string direction by comparing the numbers of such horizontally-long and vertically-long connected components.

Since the method using the marginal distribution is not used, the connected component which is inherently strong in the inclination of the document and which is unsuitable as a character string candidate can be easily excluded due to its size and the like. Even if there is an area or an area such as a title whose layout is largely different from that of the body, the influence of the area can be eliminated and the direction of the character string of the body can be determined.

If the character string direction discrimination similar to that of the first aspect of the present invention is to be performed directly on the character image before compression, a far larger number of connected components are extracted, and these are extracted in the vertical and horizontal directions. It will be necessary to perform processing that integrates or fuses with. According to the invention of claim 1, the number of connected components to be subjected to the direction discrimination processing is significantly reduced by performing the reduction processing only once, and the integration processing without the integration becomes unnecessary. Can be achieved by a simple logical sum operation or the like, so that the character string direction can be determined in a single time with a small amount of processing.

In the case of a document with a long character distance such as a word processing document, the characters are not fused and remain isolated even on a reduced image, so that the aspect ratio or the connected component whose aspect ratio is greater than or equal to the threshold value. As a result, the number of
If the number of vertically connected components and the number of horizontally connected components are compared, the determination result in the character string direction may be incorrect.

According to the invention of claim 2, in the case of such a document, the connected components are integrated into the character strings in the vertical direction and the horizontal direction, and at that time, a histogram of the distance between adjacent connected components is generated. .. Normally, the character spacing is smaller than the line spacing (character string spacing), so if the document is a horizontal writing document, the maximum frequency distance on the horizontal histogram is smaller than the maximum frequency distance on the vertical histogram. The usual case is the opposite. Therefore, according to the second aspect of the present invention, by comparing the distance having the maximum frequency on the histogram in each direction, even in the case of a document having a relatively large character spacing such as a word processing document, the character string direction Can be accurately determined.

According to the invention of claim 3, in the invention of claim 2, the total of the maximum frequency of the histogram and the frequency around it is obtained for each direction, and when the ratio is large, the direction in which the total frequency is large is set to the character. Judge in the column direction. By doing this, even if the maximum frequency of the histogram becomes unreliable, that is, even for a document with a large distance distribution or a document with a low overall frequency,
The character string direction can be reliably determined.

Further, according to the invention of claim 2 or 3, even when the character strings are integrated to determine the direction of the character string, the character string data can be directly used for the text area integration.
The processing amount as a whole does not increase, and the consistency with the area identification processing is excellent. Also, in the invention of claim 2 or 3, as in the invention of claim 1, the influence is eliminated even if there is an area such as a photo area or a title whose layout is different from the text area, such as a title area. It is clear that you can do it.

[0019]

1 is a block diagram of a processing system according to an embodiment of the present invention, and FIG. 2 is a flow chart showing the processing flow thereof.

In FIG. 1, 101 is an image input unit such as a scanner for inputting a binary image of a document, 102 is an image reducing unit for reducing the input image to generate a reduced image, and 103 is the reduced image. A connected component extraction unit that extracts a connected component of black pixels, 104 is a vertical / horizontal determination unit that performs a process of determining a character string direction (document vertical writing / horizontal writing) based on the extracted connected component information, and 105 is a connected component Is integrated into a character string and the character area is integrated into a coherent text area such as a column.
Is a data storage unit for storing various data such as an input image, a reduced image thereof, information of extracted connected components, 107 is a control unit for controlling each unit, and 108 is a data communication path.

The processing contents will be described below along the processing flow shown in FIG.

First, the image input unit 101 inputs a binary image of a document to be processed, and the data storage unit 106
(Step 201). Next, the image reduction unit 10
An image obtained by reducing the input image in the vertical direction and the horizontal direction at the same reduction rate by 2 is generated in the data storage unit 106 (step 202).

The reduction ratio is selected so that characters on the same line may be merged by the reduction, but characters on different lines may not be merged. For example, when a document image is input at 400 dpi, 8 × 8 pixels are reduced to 1 pixel. The reduction method is OR reduction, and in the case of reducing 8 × 8 pixels to 1 pixel, if even one pixel in 8 × 8 pixels is black, the reduced pixel is black. However, other reduction methods can be used.

Next, the connected component extraction unit 103 extracts the connected components of the black pixels on the reduced image, and stores information such as the vertex coordinates of the circumscribed rectangle in the data storage unit 106 (step 203). However, some of the connected components extracted at this stage may not be character string candidates.
Next, the processing by the vertical / horizontal discriminating unit 104 (step 204 to
209) is performed. However, the process of integrating the connected component into the character string in step 207 and the process of step 209 are performed by the character area integrating unit 105. First, referring to the information on the connected components extracted in step 203, the connected components are classified into character string candidates and candidates other than characters (drawings or photographs) (step 204). As the characteristics for this classification, for example, the size, size, and aspect ratio or aspect ratio of the connected component can be used. Subsequent processing targets the connected component as a character string candidate. It is also possible to combine the processes of steps 203 and 204 and perform the condition check while extracting only the connected components that can be character string candidates from the beginning.

Next, the aspect ratios and aspect ratios of the connected components as character string candidates are compared with the threshold value th1 (for example, 3), and the number of vertically connected components whose aspect ratio is equal to or greater than the threshold value th1 and The number of horizontally long connected components whose aspect ratio is greater than or equal to the threshold value th1 is counted (step 205).

For example, in the case of 400 dpi, when 8 × 8 pixels are logically reduced to 1 pixel, on the reduced image of a general document, the characters in the same character string are fused (the punctuation marks are not fused), but Lines do not merge. Therefore, each connected component has an elongated shape in the row (character string) direction, so by summing up only the elongated connected components and comparing the number of vertically long ones and the number of horizontally long ones, the character string (row)
The direction can be determined.

Step 206 is a processing step for making this determination. That is, the number of connected components in each direction obtained in step 205 is compared, and if the number of vertically connected components is greater than the number of horizontally connected components, the character string direction is determined to be the vertical direction, and vice versa. If there is a relationship, the character string direction is determined to be the horizontal direction.

However, when the document to be processed has a long character-to-character distance, such as a word-processor-created document, the characters are not merged and remain isolated even in the reduced image. Therefore, the aspect ratio or the aspect ratio is equal to or greater than the threshold value. The number of connected components of is very small. In such a case, it is impossible to determine the character string direction by comparing the numbers of the vertically long connected components and the horizontally long connected components as described above.

Therefore, in step 206, first, the number of connected components in each direction obtained in step 205 is compared with a certain threshold value th2, and if both the number of vertically long connected components and horizontally long connected components are less than or equal to the threshold value th2, The character string direction determination based on the above number comparison is not performed. In this case, the character string direction is determined in step 207 and the subsequent steps. However, even if one of the vertically or horizontally long connected components has the threshold value th2.
When it exceeds, the character string direction is determined by the above number comparison in step 206. In this case, the character string direction determination ends, and the process proceeds to step 209.

If the character string direction cannot be determined in step 206, the connected components as character string candidates are integrated into the vertical character string (row) and the horizontal character string (row) in step 207. Perform processing. This integration into a character string is performed in the character string direction (as the character string direction is fixed at this stage, as described in "Division of Documents Having Various Layout Structures and Components"). This is a process in which connected components that are close to each other belong to the same character string. At the time of this integration, the distances between adjacent connected components are aggregated and a distance histogram is created for each direction.

FIG. 3 is a diagram for explaining this processing. FIG. 3 (A) shows a state before the integration.
˜315 are circumscribed rectangles of the character string candidate connected components. Figure 3
(B) shows the state after integration into the vertical character string.
1 to 323 are character strings (rows) obtained by the integration.
(C) shows a state after integration into a horizontal character string.
˜333 are character strings (rows).

At the time of vertical integration, a histogram of distances as shown by reference numeral 324 is created in (B), and at the time of horizontal integration, a histogram of distances as shown by reference numeral 334 is created in (C). To do. However, when creating a histogram, the height (horizontal length in the case of a vertical character string) of the character string (row) obtained as a result of the integration is the vertical length in the case of a vertical character string. Is too large (when the ratio of the former to the latter exceeds a certain threshold th3), it is determined that the character strings are not correctly integrated, and the distance between the connected components is not used for histogram creation. .. For example, the character string 321 shown in FIG. 3B is excluded from the histogram creation target.

In the next step 208, the distances having the maximum frequencies of the histograms in the vertical and horizontal directions created in step 207 are compared, and the direction with the smaller distance is determined to be the character string direction. This is because the distance between characters is generally smaller than the distance between lines.

However, since the integration in step 207 is integration in the direction of the tentative character string, the dispersion of the distance becomes large due to the change between the lines, or the totalization is performed as the character string 321 shown in FIG. 3B. In some cases, the maximum frequency of the histogram is not reliable because the number of connected components that are excluded from the target increases and the total frequency decreases. For example, in a document whose character string direction is the horizontal direction, FIG.
When the histogram shown in FIG. 4A is obtained and the histogram shown in FIG. 4B is obtained in the horizontal direction, the distance corresponding to the maximum frequency 401 in the vertical direction is
It is smaller than the distance corresponding to the maximum frequency 402 in the lateral direction.
In this case, the character string direction is erroneously determined to be the vertical direction by comparing the distances with the maximum frequency.

In order to avoid such an erroneous determination, in step 208, the total of the maximum frequency and the frequencies on both sides of the maximum frequency (generally, the total frequency around the maximum frequency) is obtained for each direction, and there is a ratio thereof. When the threshold value th4 is exceeded,
The direction in which the total frequency is large is determined to be the direction of the character string. When the ratio is less than or equal to the threshold value th4, the one having the smaller maximum frequency distance is set to the character string direction. For example, reference numeral 40 in FIG.
When the ratio of the total frequency indicated by 3 and the total frequency indicated by reference numeral 404 in FIG. 4B exceeds the threshold th4, the larger horizontal direction of the total frequency is set to the character string direction.

When the character string direction is determined in step 206, the character string candidate connected component is integrated into the character string in the determined direction in step 209 and the process proceeds to step 210. If the character string direction is determined in step 208,
Since the string integration has already been completed, immediately proceed to step 2
Go to 10. Step 210 is processing of the character area integration unit 105, which integrates a character string into a cohesive text area such as a column. Such integration is disclosed in Japanese Patent Laid-Open No. 3-1
The method described in Japanese Patent No. 28340 may be used.

[0037]

As is apparent from the above description, according to the invention of claim 1, the character string direction of a document can be determined with a small processing amount, and the inclination of the document, the text area of the photograph area, the title, etc. can be determined. It becomes difficult to be affected by the area where the layout greatly differs.

According to the second or third aspect of the present invention, it is possible to accurately determine the character string direction even for a document having a large character spacing such as a document created by a word processor, and to determine the character string direction. Since the result of the character string integration for can be used as the character string data for the text area integration, the consistency with the area identification processing is excellent, and the processing amount as a whole can be reduced.

[Brief description of drawings]

FIG. 1 shows a block configuration of a processing system according to an embodiment of the present invention.

FIG. 2 shows a schematic flow of processing.

FIG. 3A shows an example of extraction of connected components. (B) shows the extraction result to the character string in the vertical direction. (C) shows the result of extraction into a character string in the horizontal direction.

FIG. 4A shows an example of a histogram of distance in the vertical direction. (B) An example of a histogram of the distance in the horizontal direction is shown.

[Explanation of symbols]

 Reference Signs List 101 image input unit 102 image reduction unit 103 connected component extraction unit 104 vertical / horizontal discrimination unit 105 character region integration unit 106 data storage unit 107 control unit 108 data communication path 301 to 315 circumscribed rectangle of connected components 321 to 323 vertical integrated character string 331 ~ 333 Horizontal integrated character string

Claims (3)

[Claims] 1. A threshold value having an aspect ratio or an aspect ratio among the connected components, which generates a reduced image of a binary image of a document, extracts a connected component of black pixels as a character string candidate from the reduced image. A character string direction discriminating method for discriminating the character string direction of the document by comparing the number of vertically long connected components exceeding the number of horizontally long connected components. 2. A reduced image of a binary image of a document is generated, a connected component of black pixels as a character string candidate is extracted from the reduced image, and the connected component has an aspect ratio or an aspect ratio. The number of each of the vertically long connected components and the horizontally long connected components equal to or larger than the first threshold is checked, and if the number of the vertically connected components or the horizontally connected components exceeds the second threshold, the number of each The character string direction of the document is determined by comparing, and if the number of the vertically long connected components and the number of the horizontally long connected components are respectively less than or equal to the second threshold value, the connected components as the character string candidates are vertically A process of integrating the character strings in the horizontal direction and the horizontal direction is performed, and a histogram of distances between adjacent ones of the connected components integrated in the character string having a ratio of height to length less than or equal to a third threshold is displayed in the vertical direction and the horizontal direction. Generated separately for each direction Character string direction determining method determines the character string direction of the document by comparing the distance corresponding to the maximum frequency of the histogram of direction. 3. A reduced image of a binary image of a document is generated, a connected component of black pixels as a character string candidate is extracted from the reduced image, and the connected component has an aspect ratio or an aspect ratio. The number of each of the vertically long connected components and the horizontally long connected components equal to or larger than the first threshold is checked, and if the number of the vertically connected components or the horizontally connected components exceeds the second threshold, the number of each The character string direction of the document is determined by comparing, and if the number of the vertically long connected components and the number of the horizontally long connected components are respectively less than or equal to the second threshold value, the connected components as the character string candidates are vertically A process of integrating the character strings in the horizontal direction and the horizontal direction is performed, and a histogram of distances between adjacent ones of the connected components integrated in the character string having a ratio of height to length less than or equal to a third threshold is displayed in the vertical direction and the horizontal direction. Generated separately for each direction In the histogram of the directions, the sum of the maximum frequency and the frequency of distances around the distance corresponding to the maximum frequency is calculated, and when the ratio of the total in each direction is less than or equal to a fourth threshold value, the distances corresponding to the maximum frequency are compared. If not, the character string direction determining method is characterized by determining the character string of the document by comparing the total amount.