CN105574530B - Method and device for extracting text lines in a document - Google Patents

Abstract

The present invention relates to the method and apparatus for extracting the line of text in document.According to an aspect of the invention, there is provided a kind of method for extracting the line of text in document, comprising: slightly clustered to multiple text blocks in document, to form multiple classes；Calculate the feature of each class；According to the feature of each class, the direction of the document is determined；And the multiple text block is finely clustered according to the direction of the document, to extract line of text.

Description

Method and device for extracting text lines in a document

technical field

The invention relates to the field of document processing, in particular to a method and a device for extracting text lines in a document.

Background technique

With the development of computer technology and communication technology, the amount of information and data has increased dramatically. In the face of huge data, users have more and more requirements for automatic information processing technology, especially document processing technology. In document processing technology, it is necessary to extract and recognize text in document images. When extracting the text in the document image, it is necessary to extract the text line first, and then segment and recognize the text line according to the text features shown in the text line.

The usual text line extraction algorithm is to extract the text line by using the feature that there is a large gap between the text lines through projection in the horizontal direction and in the vertical direction. However, when the document image has a relatively complex layout or the document image contains a lot of noise, it becomes very difficult to extract text lines.

For the above problems, different solutions have been proposed in the prior art, including methods based on graph theory, methods based on Gaussian convolution, methods based on K-means clustering, methods based on morphology, and so on. However, some of these methods have a high error rate, and some require human supervision or intervention during the operation, which brings inconvenience to the operation.

Contents of the invention

In view of this, the present invention proposes a method and device for extracting text lines in documents, so as to accurately and efficiently extract text lines in documents.

According to one aspect of the present invention, a method for extracting text lines in a document is provided, including: performing rough clustering on multiple text blocks in the document to form multiple classes; calculating features of each class; The features of each class determine the orientation of the document; and perform fine clustering on the plurality of text blocks according to the orientation of the document to extract text lines.

According to another aspect of the present invention, there is provided a device for extracting text lines in a document, including: a rough clustering unit, which performs rough clustering on multiple text blocks in the document to form multiple classes; class feature calculation A unit for calculating the characteristics of the class; a document direction determination unit for determining the direction of the document according to the class characteristics calculated by the class feature calculation unit; and a fine clustering unit for determining the direction of the document according to the document direction determination unit The orientation of the document is finely clustered on the multiple text blocks to extract text lines.

According to the technical solution provided by the invention, the text lines in the document can be extracted with high accuracy.

Description of drawings

Other features and advantages of the present invention will be more easily understood by reading the various embodiments of the present invention with reference to the accompanying drawings. The accompanying drawings described here are only for the purpose of schematically illustrating the embodiments of the present invention, not all possible implementations , and are not intended to limit the scope of the invention. In the attached picture:

Fig. 1 shows a flowchart of a method for extracting text lines in a document according to an embodiment of the present invention.

Fig. 2 shows a flow chart of determining the direction of a document according to an embodiment of the present invention.

Fig. 3 shows a flowchart of fine clustering according to one embodiment of the present invention.

Fig. 4 shows a flow chart of updating the class of each text block according to an embodiment of the present invention.

Fig. 5 shows a flowchart of coarse clustering according to one embodiment of the present invention.

Fig. 6 shows a flow chart of merging each text block and the closest text block to the same class according to an embodiment of the present invention.

Fig. 7 shows a block diagram of an apparatus for extracting text lines in a document according to an embodiment of the present invention.

Fig. 8 shows a block diagram of a document orientation determining unit according to an embodiment of the present invention.

Fig. 9 shows a block diagram of a fine clustering unit according to an embodiment of the present invention.

Fig. 10 shows a block diagram of a clustering subunit according to an embodiment of the present invention.

Fig. 11 shows a block diagram of a coarse clustering unit according to an embodiment of the present invention.

Fig. 12 shows a block diagram of the clustering subunit of the coarse clustering unit according to an embodiment of the present invention.

Fig. 13 shows a schematic block diagram of a computer that can be used to implement the method and apparatus according to the embodiments of the present invention.

Detailed ways

Embodiments of the present invention will now be described in detail with reference to the accompanying drawings. It should be noted that the following description is exemplary only and is not intended to limit the present invention. Also, in the following description, the same reference numerals will be used to designate the same or similar components in different drawings. Different features in different embodiments described below can be combined with each other to form other embodiments within the scope of the present invention.

In the description of this application, "text line" refers to a line composed of text characters in a document. The "line" mentioned here does not involve the direction. It can mean either a horizontal "line" or a vertical "OK".

In the description of the present application, "direction of the document" refers to the general reading direction of the document, that is, the arrangement direction between text lines. For example, the "direction of the document" herein is vertical because text lines are arranged vertically. If the text in each text line is arranged vertically, that is, the text lines are arranged horizontally, the orientation of the document is horizontal.

In the description of this application, "text block" refers to a plurality of blocks into which the entire document is divided during the preprocessing process of the document, which are used for subsequent processing. This segmentation can be performed based on various methods in the prior art, such as performing continuous component analysis on the document or segmentation based on histograms to obtain multiple text blocks. Depending on the selected segmentation method, each obtained text block may contain a part of a character or one or more characters, or a combination thereof. It can be understood that those skilled in the art can divide the document into text blocks in an appropriate manner according to the actual needs and the actual situation of the document (such as the size of the text, the spacing between characters and the spacing between lines).

Fig. 1 shows a flowchart of a method for extracting text lines in a document according to an embodiment of the present invention. As shown in FIG. 1 , the method 100 for extracting text lines in a document includes steps S110 to S140. In step S110, rough clustering, ie preliminary clustering, is performed on multiple text blocks in the document to form multiple clusters. Each class formed is a collection of text blocks and can contain one or more text blocks. In step S120, features of each class formed by step S110 are calculated. In this application, the feature of a class is a feature that characterizes the location information of the class, which will be described in detail below. In step S130, the orientation of the document is determined according to the features of each class calculated in step S120. After the direction of the document is determined, in step S140, according to the direction of the document determined in step S130, a plurality of text blocks in the document are finely clustered, so that each class obtained by the fine clustering is regarded as a The text line is output, that is, the text line is extracted.

According to this embodiment of the present invention, through coarse clustering and fine clustering, text lines are extracted from documents for subsequent operations such as text extraction and/or recognition. The method can correctly extract text lines from the document, has a low error rate, and the whole operation process does not require human supervision or intervention, thereby facilitating operation.

According to another embodiment of the present invention, each text block in the document has position information, and in step S120, the features of each class can be calculated respectively according to the position information of the text blocks included in each class. According to one embodiment, the position information of each text block in the document may include horizontal position information and vertical position information. Correspondingly, the features of each class may include horizontal features and vertical features, which are respectively used to characterize the horizontal position information and vertical position information of each class. In step S120, the horizontal feature and vertical feature of each class are respectively calculated according to the horizontal position information and vertical position information of each text block included in each class.

The horizontal features of each class can include the mean and standard deviation of the horizontal position information of all text blocks included in the class, and the vertical features of each class can include the vertical position information of all text blocks included in the class mean and standard deviation. According to one embodiment, the horizontal position information of each text block may include the uppermost position, the lowermost position and/or the central horizontal position of the text block, which are used to indicate the position of the text block in the document in the horizontal direction. s position. For example, when the horizontal position information of each text block includes the uppermost position and the lowermost position of the text block, the horizontal feature of each class may include the average value of the uppermost positions of all text blocks included in the class and standard deviation, and the mean and standard deviation of the bottommost positions. Similarly, the vertical position information of each text block may include the leftmost position, the rightmost position and/or the central vertical position of the text block, which are used to indicate that the text block is in the document in the vertical direction. where you are.

Fig. 2 shows a flow chart of determining the direction of a document according to an embodiment of the present invention. As shown in FIG. 2, the above step S130 includes sub-steps S210-S230.

In sub-step S210, the average value of the standard deviations in the horizontal features and the average value of the standard deviations in the vertical features of all classes are compared. It can be understood that if the standard deviation of the horizontal features of each class is larger than the standard deviation of the vertical features, it indicates that the vertical positions of the text blocks in each class are relatively close to each other. Conversely, if the standard deviation of the horizontal features of each class is smaller than that of the vertical features, it indicates that the horizontal positions of the text blocks in each class are relatively close to each other.

For example, when the horizontal position information of each text block includes the uppermost position and the lowermost position of the text block and the vertical position information includes the leftmost position and the rightmost position of the text block, then each class The horizontal feature includes the mean and standard deviation of the topmost position and the mean and standard deviation of the bottommost position of all text blocks contained in the class and the vertical feature contains the leftmost position of all text blocks contained in the class The mean and standard deviation of , and the mean and standard deviation of the rightmost position. In sub-step S210, the standard deviation in the horizontal features of each class not only considers the standard deviation of the uppermost position of each text block, but also considers the standard deviation of the lowermost position of each text block, for example, in the horizontal feature of each class The standard deviation of can be the sum or average of the standard deviation of the uppermost position of each text block and the standard deviation of the lowermost position of each text block. Similarly, the standard deviation in the vertical features of each class may be the sum or average of the standard deviation of the leftmost position of each text block and the standard deviation of the rightmost position of each text block.

Therefore, when the average value of the standard deviations in the horizontal features of all classes is greater than the average value of the standard deviations in the vertical features, in step S220, it is determined that the direction of the document is the horizontal direction; when the standard deviation in the horizontal features of all classes When the average value of the difference is smaller than the average value of the standard deviation in the vertical feature, in step S230, it is determined that the orientation of the document is the vertical orientation.

Fig. 3 shows a flowchart of fine clustering according to one embodiment of the present invention. As shown in FIG. 3, the above step S140 includes sub-steps S310-S350.

In sub-step S310, according to the direction of the document determined in step S130, the association value between each text block and each class is calculated. In this application, the association value between a text block and a class represents the closeness of the text block to the class.

According to one embodiment, the association value between each text block and each class is calculated according to the position information of the text block and the characteristics of the class. For example, when the orientation of the document is horizontal, the difference between the vertical position information of a text block and the average value of the vertical feature of a class is calculated as the association value of the text block and the class. Conversely, when the orientation of the document is vertical, the difference between the horizontal position information of a text block and the average value of the horizontal feature of a class is calculated as the association value between the text block and the class.

For example, as described above, when the horizontal position information of each text block includes the uppermost position and the lowermost position of the text block and the vertical position information includes the leftmost position and the rightmost position of the text block, then The horizontal features of each class include the mean and standard deviation of the uppermost position and the mean and standard deviation of the lowermost position of all text blocks contained in the class and the vertical features include the mean and standard deviation of all text blocks contained in the class The mean and standard deviation for the leftmost position and the mean and standard deviation for the rightmost position. In sub-step S310, when the orientation of the document is horizontal, the association value between a text block and a class is the difference between the leftmost position of the text block and the average value of the leftmost positions of all text blocks included in the class difference, and the difference between the rightmost position of this text block and the average of the rightmost positions of all text blocks contained in this class, the sum, the average value, or whichever is greater. Similarly, when the document orientation is vertical, the associated value of a text block and a class is the difference between the uppermost position of the text block and the average of the uppermost positions of all text blocks contained in the class and the text The sum, the average, or the greater of the difference between the bottommost position of the block and the average of the bottommost positions of all text blocks contained in this class.

Subsequently, in sub-step S320, the class of each text block is updated according to the calculated association value between each text block and each class. Through the coarse clustering in step S110 above, the clustering result is often not accurate enough, for example, the text blocks that should be in two text lines are clustered into one class. Here, by using the associated value between each text block and each class, the proximity of the text block to each class can be determined, so as to update the class where the text block should be located.

In sub-step S330, the features of each class are updated, and the classes that do not contain any text blocks are deleted. After the class of each text block is updated by substep S320, the class of the text block may change, that is to say, the text blocks contained in a certain class or some classes will change, and some It is possible that a class no longer contains any text blocks. Here, the features of each class can be recalculated and classes that no longer contain any text blocks can be deleted. It can be seen that in the process of fine clustering, the number of the multiple classes is dynamically changed, which is beneficial to obtain the final clustering result accurately and quickly.

In sub-step S340, it is judged whether the category of each text block has not changed. If yes, extract each generated class as a text line (S350); if no, return to sub-step S310 to continue the fine clustering process.

Fig. 4 shows a flow chart of updating the class of each text block according to an embodiment of the present invention. As shown in FIG. 4, the above sub-step S320 includes sub-steps S410-S450.

In sub-step S410, a threshold is calculated according to the determined orientation of the document and the features of all classes. According to one embodiment, when the orientation of the document is horizontal, the average value of the standard deviations in the vertical features of all classes is calculated and multiplied by a preset coefficient, and the product is used as a threshold. When the orientation of the document is the vertical orientation, calculate the average value of the standard deviations in the horizontal features of all classes multiplied by a preset coefficient, and use the product as a threshold.

For example, as described above, when the horizontal position information of each text block includes the uppermost position and the lowermost position of the text block and the vertical position information includes the leftmost position and the rightmost position of the text block, then The horizontal features of each class include the mean and standard deviation of the uppermost position and the mean and standard deviation of the lowermost position of all text blocks contained in the class and the vertical features include the mean and standard deviation of all text blocks contained in the class The mean and standard deviation for the leftmost position and the mean and standard deviation for the rightmost position. In sub-step S410, when the document orientation is horizontal, the average value of the standard deviations of the leftmost positions and the average value of the standard deviations of the rightmost positions of all text blocks contained in all classes, the average value Or the larger one is multiplied by a preset coefficient, and the obtained product is used as a threshold. Similarly, when the document orientation is the vertical direction, the average value of the standard deviations of the uppermost positions and the average value of the standard deviations of the lowermost positions of all text blocks contained in all classes, the average value or the lower The larger one is multiplied by a preset coefficient, and the resulting product is used as a threshold.

For a text block that has an associated value with each class, in substep S420, determine the minimum associated value of the text block and the class that has the minimum associated value with the text block.

In sub-step S430, the minimum correlation value determined in sub-step S420 is compared with the threshold value calculated in sub-step S410. When the minimum correlation value is less than the threshold, in sub-step S440, the text block is clustered into a class having the minimum correlation value with the text block. When the minimum correlation value is greater than or equal to the threshold, in substep S450, a class is created, and the text block is clustered into the created class. It can be seen that which class a text block belongs to will be affected by the threshold, and the numerical value of the threshold depends on the belonging situation of the current text block. Therefore, the method according to the present invention is an iterative process of dynamic adjustment, and when updating each text block During the course of the class, the number of the plurality of classes is also dynamically changed. It can be understood that those skilled in the art can select appropriate preset coefficients according to actual needs and actual conditions of the processed documents. According to an embodiment, the preset coefficient is a real number in the range of 1-3, such as 2.

Fig. 5 shows a flowchart of coarse clustering according to one embodiment of the present invention. As shown in FIG. 5, the above step S110 includes sub-steps S510-S520. In sub-step S510, the distance between every two text blocks is calculated. Those skilled in the art can understand that the distance between two text blocks can be calculated by any applicable method in the prior art, for example, calculate the distance between the two closest points between two text blocks, and calculate the distance between two text blocks. distance between points, etc. Subsequently, in sub-step S520, according to the distance calculated in sub-step S510, each text block and the text block closest to the text block are merged into the same class.

Fig. 6 shows a flow chart of merging each text block and the closest text block to the same class according to an embodiment of the present invention. As shown in FIG. 6, the above sub-step S520 includes sub-steps S610-S630. In sub-step S610, it is judged whether the text block closest to the text block not clustered in any class has been clustered in a certain class. If yes, then in sub-step S620, the text block is also clustered in the same class as its closest text block. If not, in substep S630, a class is created, and the text block and its closest text blocks are clustered into the created class. It can be seen that in the process of rough clustering, the number of the multiple classes also changes dynamically.

Fig. 7 shows a block diagram of an apparatus for extracting text lines in a document according to an embodiment of the present invention. As shown in FIG. 7 , the device 700 includes a rough clustering unit 710 , a class feature calculation unit 720 , a document direction determination unit 730 and a fine clustering unit 740 . The rough clustering unit 710 can perform rough clustering on multiple text blocks in the document to form multiple clusters. The class feature calculation unit 720 may calculate features of a class. The document orientation determination unit 730 can determine the orientation of the document according to the class features calculated by the class feature calculation unit 720 . The fine clustering unit 740 may perform fine clustering on multiple text blocks according to the direction of the document determined by the document direction determining unit 730 to extract text lines.

According to another embodiment of the present invention, each text block in the document has position information, and the class feature calculation unit 720 can calculate the feature of the class according to the position information of the text blocks included in the class.

According to one embodiment, the position information of the text block includes horizontal position information and vertical position information, the horizontal position information of the text block includes the uppermost position, the lowermost position and/or the central horizontal position of the text block, and the vertical position of the text block. The vertical position information includes the leftmost position, rightmost position and/or center vertical position of the text block. Correspondingly, the features of a class include horizontal features and vertical features. The horizontal features of a class include the average and standard deviation of the horizontal position information of all text blocks contained in the class. The vertical features of a class include all text blocks contained in the class. The mean and standard deviation of the vertical position information of the text block.

Fig. 8 shows a block diagram of a document orientation determining unit according to an embodiment of the present invention. As shown in FIG. 8 , the document direction determination unit 730 includes a comparison subunit 810 and a determination subunit 820 . The comparison subunit 810 can compare the average value of the standard deviations in the horizontal features and the average value of the standard deviations in the vertical features of all classes. The determination subunit 820 may determine whether the orientation of the document is horizontal or vertical according to the comparison result of the comparison subunit 810 . Specifically, when the average value of the standard deviations in the horizontal features of all classes is greater than the average value of the standard deviations in the vertical features, the determining subunit 820 determines that the orientation of the document is a horizontal direction; when the standard deviation in the horizontal features of all classes When the average value of the difference is smaller than the average value of the standard deviation in the vertical feature, the determination subunit 820 determines that the orientation of the document is the vertical orientation.

Fig. 9 shows a block diagram of a fine clustering unit according to an embodiment of the present invention. As shown in FIG. 9 , the fine clustering unit 740 includes an association value calculation subunit 910 , a clustering subunit 920 and a class updating subunit 930 . The correlation value calculation subunit 910 can calculate the correlation value between the text block and each class according to the orientation of the document determined by the document orientation determination unit 730 . The clustering subunit 920 may update the class of the text block according to the association value calculated by the association value calculation subunit 910 . Since the class of the text block may change, among multiple classes, the characteristics of at least one class may change. The class update subunit 930 may update the characteristics of each class and delete classes that no longer contain any text blocks.

According to one embodiment, the association value calculation subunit 910 may calculate the association value between the text block and the class according to the position information of the text block and the characteristics of the class.

Optionally, when the document orientation determination unit 730 determines that the orientation of the document is the horizontal orientation, the associated value calculation subunit 910 calculates the difference between the vertical position information of the text block and the average value of the vertical feature of the class as the text block and The associated value for this class. Conversely, when the document direction determination unit 730 determines that the direction of the document is the vertical direction, the correlation value calculation subunit 910 calculates the difference between the horizontal position information of the text block and the average value of the horizontal feature of the class as the difference between the text block and the class. associated value.

Fig. 10 shows a block diagram of a clustering subunit according to an embodiment of the present invention. As shown in FIG. 10 , the clustering subunit 920 includes a threshold calculation module 1010 , a minimum correlation value determination module 1020 , a class creation module 1030 and a clustering module 1040 . The threshold calculation module 1010 can calculate the threshold according to the direction of the document and the features of all classes. The class creation module 1030 can be used to create classes. For a text block, the minimum association value determination module 1020 can determine the minimum association value of the text block and the class that has the minimum association value with the text block, and if its minimum association value is less than a threshold, the clustering module 1040 can use the The text block is clustered into the class determined by the minimum association value determination module 1020 , and if the minimum association value is greater than or equal to the threshold, the clustering module 1040 may cluster the text block into the class created by the class creation module 1030 .

According to one embodiment, when the document orientation determination unit 730 determines that the orientation of the document is horizontal, the threshold calculation module 1010 calculates the average value of the standard deviations in the vertical features of all classes multiplied by a preset coefficient as the result threshold. Conversely, when the document orientation determination unit 730 determines that the orientation of the document is vertical, the threshold calculation module 1010 calculates the result obtained by multiplying the average value of the standard deviations in the horizontal features of all classes by a preset coefficient as the threshold.

Fig. 11 shows a block diagram of a coarse clustering unit according to an embodiment of the present invention. As shown in FIG. 11 , the rough clustering unit 710 includes a distance calculation subunit 1110 and a clustering subunit 1120 . The distance calculation subunit 1110 can calculate the distance between every two text blocks. The clustering subunit 1120 can combine each text block and the text block closest to the text block into the same class according to the distance calculated by the distance calculation subunit 1110 .

Fig. 12 shows a block diagram of the clustering subunit of the coarse clustering unit according to an embodiment of the present invention. As shown in FIG. 12 , the clustering subunit 1120 includes a class creation module 1210 and a clustering module 1220 . Class creation module 1210 may be used to create classes. For a text block that is not clustered in any class, if the text block closest to the text block has been clustered in a class, the clustering module 1220 will also cluster the text block in the class. When the text block closest to the text block is not clustered in any class, the clustering module 1220 clusters the text block and its closest text block into the class created by the class creation module 1210 .

In addition, it should be pointed out here that each component in the above device may be configured by software, firmware, hardware or a combination thereof. Specific means or manners that can be used for configuration are well known to those skilled in the art, and will not be repeated here. In the case of realizing by software or firmware, the program constituting the software is installed from a storage medium or a network to a computer (for example, a general-purpose computer 1300 shown in FIG. 13 ) having a dedicated hardware configuration. Capable of performing various functions, etc.

Fig. 13 shows a schematic block diagram of a computer that can be used to implement the method and apparatus according to the embodiments of the present invention.

In FIG. 13 , a central processing unit (CPU) 1301 executes various processes according to programs stored in a read only memory (ROM) 1302 or loaded from a storage section 1308 to a random access memory (RAM) 1303 . In the RAM 1303, data required when the CPU 1301 executes various processes and the like is also stored as necessary. The CPU 1301 , ROM 1302 , and RAM 1303 are connected to each other via a bus 1304 . The input/output interface 1305 is also connected to the bus 1304 .

The following components are connected to the input/output interface 1305: an input section 1306 (including a keyboard, a mouse, etc.), an output section 1307 (including a display such as a cathode ray tube (CRT), a liquid crystal display (LCD), etc., and a speaker, etc.), A storage section 1308 (including a hard disk, etc.), a communication section 1309 (including a network interface card such as a LAN card, a modem, etc.). The communication section 1309 performs communication processing via a network such as the Internet. A driver 1310 may also be connected to the input/output interface 1305 as needed. A removable medium 1311 such as a magnetic disk, an optical disk, a magneto-optical disk, a semiconductor memory, or the like can be mounted on the drive 1310 as needed, so that a computer program read therefrom can be installed into the storage section 1308 as needed.

In the case of realizing the above-described series of processes by software, the programs constituting the software are installed from a network such as the Internet or a storage medium such as the removable medium 1311 .

Those skilled in the art should understand that such a storage medium is not limited to the removable medium 1311 shown in FIG. 13 in which the program is stored and distributed separately from the device to provide the program to the user. Examples of the removable media 1311 include magnetic disks (including floppy disks (registered trademark)), optical disks (including compact disk read only memory (CD-ROM) and digital versatile disks (DVD)), magneto-optical disks (including )) and semiconductor memory. Alternatively, the storage medium may be the ROM 1302, a hard disk contained in the storage section 1308, or the like, in which programs are stored and distributed to users together with devices containing them.

The invention also proposes a program product storing machine-readable instruction codes. When the instruction code is read and executed by a machine, the above method according to the embodiments of the present invention can be executed.

Correspondingly, a storage medium for carrying the program product storing the above-mentioned machine-readable instruction codes is also included in the scope of the present invention. The storage medium includes, but is not limited to, a floppy disk, an optical disk, a magneto-optical disk, a memory card, a memory stick, and the like.

It should be noted that the method of the present invention is not limited to being executed in the chronological order described in the specification, and may also be executed in other chronological order, in parallel or independently. Therefore, the execution order of the methods described in this specification does not limit the technical scope of the present invention.

The above descriptions of various embodiments of the present invention are for a better understanding of the present invention, which are only exemplary rather than intended to implement the present invention. It should be noted that in the above description, features described and/or illustrated for one embodiment can be used in the same or similar manner in one or more other embodiments, in combination with features in other embodiments, Or replace the features in other embodiments. Those skilled in the art can understand that without departing from the inventive concept of the present invention, various changes and modifications made to the above-described implementations fall within the scope of the present invention.

To sum up, in the embodiments according to the present invention, the present invention provides the following technical solutions.

Scheme 1. A method for extracting text lines in a document, comprising:

Roughly cluster multiple text blocks in a document to form multiple classes;

Calculate the features of each class;

determining the orientation of the document based on the characteristics of each class; and

Perform fine clustering on the plurality of text blocks according to the orientation of the document to extract text lines.

Solution 2. The method according to solution 1, wherein calculating the features of each class includes: calculating the features of each class respectively according to the position information of the text blocks contained in each class.

Scheme 3, the method as described in scheme 2, wherein

The position information of each text block includes horizontal position information and vertical position information, and the horizontal position information of each text block includes the uppermost side position, the lowermost side position and/or the central horizontal position of the described text block, each text block The vertical position information includes the leftmost position, rightmost position and/or center vertical position of the text block; and

The features of each class include horizontal features and vertical features, the horizontal features of each class include the mean and standard deviation of the horizontal position information of all text blocks contained in the class, the vertical features of each class include the The mean and standard deviation of the vertical position information of all text blocks contained in the class.

Scheme 4. The method as described in scheme 3, wherein determining the direction of the document comprises:

comparing the mean of the standard deviations in the horizontal features to the mean of the standard deviations in the vertical features for all classes in the plurality of classes;

determining that the orientation of the document is a horizontal orientation when the average of the standard deviations in the horizontal features of all of the plurality of classes is greater than the average of the standard deviations in the vertical features; and

The orientation of the document is determined to be a vertical orientation when an average of standard deviations in horizontal features of all of the plurality of classes is smaller than an average of standard deviations in vertical features.

Scheme 5. The method according to any one of schemes 1 to 4, wherein fine clustering comprises:

a) For each text block, according to the direction of the document, calculate the associated value of each text block and each class;

b) updating the class of each text block in the plurality of classes according to the calculated association value;

c) update the features of each class and remove classes that do not contain any text blocks; and

d) Repeat a) to c) until the class of each text block does not change.

Solution 6. The method according to solution 5, wherein the association value between each text block and each class is calculated according to the position information of the text block and the characteristics of the class.

Scheme 7, the method as described in scheme 6, wherein

The position information of each text block includes horizontal position information and vertical position information, and the horizontal position information of each text block includes the uppermost side position, the lowermost side position and/or the central horizontal position of the described text block, each text block The vertical position information includes the leftmost position, the rightmost position and/or the center vertical position of the text block;

The features of each class include horizontal features and vertical features, the horizontal features of each class include the mean and standard deviation of the horizontal position information of all text blocks contained in the class, the vertical features of each class include the The average value and standard deviation of the vertical position information of all text blocks contained in the class;

When it is determined that the orientation of the document is horizontal, the value associated with each text block and each class is the difference between the vertical position information of the text block and the average value of the vertical features of the class; and

When it is determined that the orientation of the document is the vertical orientation, the value associated with each text block and each class is the difference between the horizontal position information of the text block and the average value of the horizontal feature of the class.

Scheme 8. The method of scheme 7, wherein updating the class of each text block in the plurality of classes comprises:

calculating a threshold according to the direction of the document and the features of the plurality of classes;

determining a minimum associated value of the text block and a class having the minimum associated value with the text block;

When the minimum correlation value is less than the threshold value, clustering the text block into a class with the minimum correlation value with the text block; and

When the minimum association value is greater than or equal to the threshold, a class is created, and the text block is clustered into the created class.

Scheme 9, the method as described in scheme 8, wherein

When it is determined that the orientation of the document is a horizontal orientation, the threshold is the result obtained by multiplying the average value of the standard deviations in the vertical features of all classes by a preset coefficient,

When it is determined that the orientation of the document is a vertical orientation, the threshold value is a result obtained by multiplying an average value of standard deviations in horizontal features of all classes by a preset coefficient.

Scheme 10. The method of any one of schemes 1 to 9, wherein the coarse clustering comprises:

calculating the distance between each two text blocks in the plurality of text blocks; and

Merge each text block with the closest text block to the same class according to the calculated distance.

Scheme 11. The method as described in scheme 10, wherein merging each text block and the nearest text block to the same class includes:

For text blocks that are not clustered in any class,

When the text block closest to the text block has been clustered in one of the plurality of classes, the text block is also clustered in the one class; and

When the closest text block of the text block is not clustered in any class, a class is created, and the text block and its closest text block are clustered in the created class.

Solution 12. A device for extracting text lines in a document, comprising:

A rough clustering unit, which roughly clusters multiple text blocks in the document to form multiple classes;

A class feature calculation unit, which calculates the feature of the class;

a document orientation determination unit, for determining the orientation of the document according to the class features calculated by the class feature calculation unit; and

The fine clustering unit performs fine clustering on the plurality of text blocks according to the direction of the document determined by the document direction determining unit, so as to extract text lines.

Solution 13. The device according to solution 12, wherein the class feature calculation unit calculates the feature of the class according to the position information of the text blocks included in the class.

Item 14. The device of item 13, wherein

The position information of the text block includes horizontal position information and vertical position information, the horizontal position information of the text block includes the uppermost position, the lowermost position and/or the central horizontal position of the text block, and the vertical position information of the text block includes the the leftmost position, rightmost position and/or center vertical position of the text block; and

The features of a class include horizontal features and vertical features. The horizontal features of a class include the average and standard deviation of the horizontal position information of all text blocks contained in the class. The vertical features of a class include the values of all text blocks contained in the class. The mean and standard deviation of the vertical position information.

Scheme 15. The device according to scheme 14, wherein the document direction determining unit comprises:

Comparing subunits, comparing the average of the standard deviations in the horizontal features to the average of the standard deviations in the vertical features for all classes in the plurality of classes; and

The determination subunit determines whether the orientation of the document is horizontal or vertical according to the comparison result of the comparison subunit.

Scheme 16. The device according to any one of schemes 12 to 15, wherein the fine clustering unit comprises:

an association value calculation subunit, calculating an association value between a text block and each class according to the orientation of the document determined by the document orientation determination unit;

The clustering subunit updates the class of the text block in the plurality of classes according to the association value calculated by the association value calculation subunit; and

Classes update subunits, updating the characteristics of each class, and removing classes that no longer contain any text blocks.

Solution 17. The device according to solution 16, wherein the association value calculation subunit calculates the association value between the text block and the class according to the position information of the text block and the characteristics of the class.

Item 18. The device of item 17, wherein

The position information of the text block includes horizontal position information and vertical position information, the horizontal position information of the text block includes the uppermost position, the lowermost position and/or the central horizontal position of the text block, and the vertical position information of the text block includes the the leftmost position, rightmost position and/or center vertical position of the text block;

The features of a class include horizontal features and vertical features. The horizontal features of a class include the average and standard deviation of the horizontal position information of all text blocks contained in the class. The vertical features of a class include the values of all text blocks contained in the class. The mean and standard deviation of the vertical position information;

When the document orientation determination unit determines that the orientation of the document is the horizontal orientation, the correlation value calculation subunit calculates the difference between the vertical position information of the text block and the average value of the vertical feature of the class as the text block and the associated value of the class; and

When the document orientation determination unit determines that the orientation of the document is a vertical orientation, the correlation value calculation subunit calculates the difference between the horizontal position information of the text block and the average value of the horizontal feature of the class as the difference between the text block and the The associated value of the class.

Scheme 19. The device of scheme 18, wherein the clustering subunit comprises:

A threshold calculation module calculates a threshold according to the direction of the document and the characteristics of the plurality of classes;

The minimum correlation value determination module determines the minimum correlation value of the text block and the class that has the minimum correlation value with the text block;

a class creation module for creating classes; and

A clustering module, clustering the text blocks with the minimum association value less than the threshold into the class determined by the minimum association value determination module, and clustering the text blocks with the minimum association value greater than or equal to the threshold class into the class created by the class creation module.

Item 20. The device of item 19, wherein

When the document orientation determination unit determines that the orientation of the document is a horizontal orientation, the threshold calculation module calculates the average value of the standard deviations in the vertical features of all classes multiplied by a preset coefficient as the result obtained threshold,

When the document orientation determination unit determines that the orientation of the document is a vertical orientation, the threshold calculation module calculates the average value of the standard deviations in the horizontal features of all classes multiplied by a preset coefficient as the result obtained threshold.

Claims (6)

1. A method of extracting text lines in a document, comprising: Roughly cluster multiple text blocks in a document to form multiple classes; Calculate the features of each class; determining the orientation of the document based on the characteristics of each class; and Carrying out fine clustering on the plurality of text blocks according to the direction of the document to extract text lines, wherein the fine clustering includes: a) For each text block, according to the direction of the document, calculate the associated value of each text block and each class; b) updating the class of each text block in the plurality of classes according to the calculated association value; c) update the features of each class and remove classes that do not contain any text blocks; and d) Repeat a) to c) until the class of each text block does not change, Among them, the associated value of each text block and each class is calculated according to the position information of the text block and the characteristics of the class, where: The position information of each text block includes horizontal position information and vertical position information, and the horizontal position information of each text block includes the uppermost side position, the lowermost side position and/or the central horizontal position of the described text block, each text block The vertical position information includes the leftmost position, the rightmost position and/or the center vertical position of the text block; The features of each class include horizontal features and vertical features, the horizontal features of each class include the mean and standard deviation of the horizontal position information of all text blocks contained in the class, the vertical features of each class include the The average value and standard deviation of the vertical position information of all text blocks contained in the class; When it is determined that the orientation of the document is horizontal, the value associated with each text block and each class is the difference between the vertical position information of the text block and the average value of the vertical features of the class; and When it is determined that the orientation of the document is the vertical orientation, the value associated with each text block and each class is the difference between the horizontal position information of the text block and the average value in the horizontal feature of the class. 2. The method according to claim 1, wherein calculating the features of each class comprises: calculating the features of each class respectively according to the position information of the text blocks contained in each class. 3. The method of claim 1 or 2, wherein determining the orientation of the document comprises: comparing the mean of the standard deviations in the horizontal features to the mean of the standard deviations in the vertical features for all classes in the plurality of classes; determining that the orientation of the document is a horizontal orientation when the average of the standard deviations in the horizontal features of all of the plurality of classes is greater than the average of the standard deviations in the vertical features; and The orientation of the document is determined to be a vertical orientation when an average of standard deviations in horizontal features of all of the plurality of classes is smaller than an average of standard deviations in vertical features. 4. The method of claim 1 , wherein updating the class in which each text block resides in the plurality of classes comprises: calculating a threshold according to the direction of the document and the features of the plurality of classes; determining a minimum associated value of the text block and a class having the minimum associated value with the text block; When the minimum correlation value is less than the threshold value, clustering the text block into a class with the minimum correlation value with the text block; and When the minimum association value is greater than or equal to the threshold, a class is created, and the text block is clustered into the created class. 5. The method of claim 4, wherein When it is determined that the orientation of the document is a horizontal orientation, the threshold is the result obtained by multiplying the average value of the standard deviations in the vertical features of all classes by a preset coefficient, When it is determined that the orientation of the document is a vertical orientation, the threshold value is a result obtained by multiplying an average value of standard deviations in horizontal features of all classes by a preset coefficient. 6. An apparatus for extracting lines of text in a document, comprising: A rough clustering unit, which roughly clusters multiple text blocks in the document to form multiple classes; A class feature calculation unit, which calculates the feature of the class; a document orientation determination unit, configured to determine the orientation of the document according to the class features calculated by the class feature calculation unit; and The fine clustering unit performs fine clustering on the plurality of text blocks according to the direction of the document determined by the document direction determining unit to extract text lines, wherein the fine clustering includes: a) For each text block, according to the direction of the document, calculate the associated value of each text block and each class; b) updating the class of each text block in the plurality of classes according to the calculated association value; c) update the features of each class and remove classes that do not contain any text blocks; and d) Repeat a) to c) until the class of each text block does not change, Among them, the associated value of each text block and each class is calculated according to the position information of the text block and the characteristics of the class, where: The position information of each text block includes horizontal position information and vertical position information, and the horizontal position information of each text block includes the uppermost side position, the lowermost side position and/or the central horizontal position of the described text block, each text block The vertical position information includes the leftmost position, the rightmost position and/or the center vertical position of the text block; The features of each class include horizontal features and vertical features, the horizontal features of each class include the mean and standard deviation of the horizontal position information of all text blocks contained in the class, the vertical features of each class include the The average value and standard deviation of the vertical position information of all text blocks contained in the class; When it is determined that the orientation of the document is horizontal, the value associated with each text block and each class is the difference between the vertical position information of the text block and the average value of the vertical features of the class; and When it is determined that the orientation of the document is the vertical orientation, the value associated with each text block and each class is the difference between the horizontal position information of the text block and the average value of the horizontal feature of the class.