Robust table recognition for printed document images

1.   Introduction

Tables in documents such as product catalogues, balance sheets, and financial reports are important expressive objects that present statistical and relational information. In the past several decades, Optical Character Recognition (OCR) is widely implemented in various applications by converting printed text into editable text, such as archival literature, office automation and license plate recognition ^[1]. This advanced technology integrates the digital image processing, computer vision and other disciplines. The rapid development of OCR has promoted the transformation of many industries, since it can significantly save the working hours, as well as the labor costs. However, the printed document recognition remains challenging. For example, images obtained by photographing or scanning contain a lot of complicated information, i.e., tables, formulas, images, and a large number of Chinese characters.

The general document image character recognition is mainly accomplished by the following steps ^[2]. First, we obtain the information of documents in a real scene by photographing or scanning the original paper documents stored in the form of image. Secondly, we apply the knowledge of the image to analyze the layout of the image, then separate the corresponding modules and send each module to the corresponding processor for processing. Thirdly, employ different functions of different modules in the related technology of document character recognition to distinguish and identify the characters in each section. The last two steps play a vital role in the document image recognition. Unlike other document recognition technologies, the table recognition requires not only extracting the frame and lines of the table, but also obtaining useful information contained in the table, such as numbers, characters, and formulas.

In the printed documents, the form of tables can be mainly divided into two categories. One is the mixed type document including pictures, characters, tables, etc. The other one is only composed of tables, e.g. financial statement, transcripts, and other single structured tables. The latter one is less challenging since the structure and information of the table can be directly extracted and identified after analyzing the table. For the former, it is more complicated because it has to preprocess the document image to minimize its own noise interference, extract the table parts, and use algorithms for identification and analysis. This paper focuses on the recognition of the commonly used tables of the former type formed by rectangular elements.

There are a large number of recognition approaches in the field of image processing for various recognition tasks. Ranka et al. ^[3] tackled the problem of table detection and retention by proposing a bi-modular approach based on structural information of tables includes bounding lines, row/column separators, spaces between columns. Experiments on a dataset of above 600 images consisting of more than 829 tables have detected 90% of the table correctly. Kasar et al. ^[4] presented a query-based approach to selectively extract tabular information and recognize the table structure from scanned documents. The query pattern is first transformed into an attributed relational graph and a fast graph matching technique was then used to retrieve other similar graphs from the document images. Cuevas ^[5] presented the Block-matching algorithm based on harmony search optimization for motion estimation which could be viewed as an optimization problem whose goal was to find the best-matching block within a search space. The average number of search points visited by the HS-BM algorithm ranges from 9.2 to 17.3, representing 4 and 7.4% respectively in comparison to the FSA method. Sage et al. ^[6] proposed a generic method for end-to-end table field extraction that started with the sequence of document tokens segmented by an OCR engine. The proposed method outperformed the feedforward network with a token level recurrent neural network combining spatial and textual features.

As the initial approach in table recognition, the commonly used preprocessing algorithms generally include denoise, image binarization, tilt correction and perspective correction. In the first step, denoise can make the tables and character information in the images more prominent. The binarization algorithm used in the second step is crucial to the recognition result since it can enhance the foreground components and weaken the background components. Based on the focused level of information, binarization algorithms can be generally categorized into the global algorithms and the local algorithms ^[7]. The global binarization algorithms select a single intensity threshold that separate pixels into two classes, the foreground and the background, by maximizing intra-class intensity variance for the entire grayscale image. The typical global binarization algorithms are Otsu algorithm ^[8] and iterative method ^[9]. By contrast, local binarization algorithms divide the image into small block units, and estimate different thresholds for every pixel according to the grayscale information of its neighboring pixels. Several local binarization methods have been proposed such as Niblack ^[10], Sauvola ^[11,12], and Bernsen ^[13] algorithms. Generally, global binarization algorithms perform well with high efficiency for typical scanned table images, while local binarization methods can deal with table images with high computational complexity. It should be mentioned that binarization algorithms have been constantly optimized to adapt to various light conditions ^[14]. In the third step, to address the issues caused by the tilted or deformed table images, the tilt correction algorithms or the perspective correction algorithms have been utilized respectively, such as the projection-based and Hough transform-based methods ^[15]. Besides, layout analysis of document images is also implemented in certain scenarios by using the top-down method and the bottom-up method ^[16,17].

Significant efforts also have been made to develop methods and algorithms for table recognition after the preprocessing of the table images. The extraction methods are proposed to identify the geometric structures of the tables based on the different logical relations ^[18]. One of the most extensively used extraction method is the projection method, which projects the table in the horizontal and vertical directions respectively and obtains the horizontal and vertical line segments. In addition, a model-based approach is formed to obtain the characteristics of the tables with the topological relationship between table cells ^[19], which makes the result of this approach more accurate and flexible than that of the extraction method. Methods based on formal description languages have been developed. For example, some methods utilize the Latex typesetting system as a language description module to represent the table. The Latex typesetting system describes tables by means of table description language, and the structure of the table is parsed and saved.

The early classification networks for character recognition are mainly built based on the AlexNet and ResNet networks designed by Microsoft ^[20,21]. With the rapid development of deep learning, especially the deep learning frameworks such as convolutional neural network (CNN) ^[22], it becomes possible to develop the end-to-end character recognition systems. Compared with the early classification networks, the recognition algorithms based on deep convolutional networks have strong fault tolerance and classification ability, and do not require complicated pre-processing and feature extracting, which significantly reduces the recognition complexity and obtains a higher recognition accuracy. Table recognition workflow comprises table image pre-processing, table detection, and text character recognition.

It is, therefore, the objective of this paper is to develop an efficient recognition system for table images by integrating the advanced algorithms, especially the deep learning framework. The main processing procedures of the proposed table image recognition have been outlined in Figure 1 and the remainder of the paper is organized as follows. Section 2 illustrates the algorithms implemented in the proposed system to preprocess the table images. In Section 3, the approaches utilized to extract the table lines and locate the table cells have been demonstrated. After that, the deep learning framework is proposed in Section 4 to recognize the printed characters. By integrating the proposed algorithms and approaches, an android-based application for table image recognition has been developed in Section 5 and its effectiveness has been verified with practical tests. Finally, the main conclusions are summarized in Section 6.

2.   Image preprocessing

To enhance the features of table images for further processing, a preprocessing algorithm has been proposed for table recognition with its overall procedures illustrated in Figure 2. As shown in Figure 2, the table image is firstly denoised ^[23], and then the grayscale image is obtained to make the table outline and content clearer. Image binarization method is optimized and its robustness is enhanced, leading to significant decrease in the amount of information that is subjected to further processing. Subsequently, edge detection on the binary image is performed to obtain peripheral contour information. Then, tilt correction and perspective correction are applied for regular and unregular rectangles, respectively.

2.1.   Denoise

There are many noise reduction algorithms developed for table image preprocessing, such as mean filtering, mask smooth filtering, and median filtering. Experiments have been conducted to show their efficiencies of reducing noise in the images with the original image shown in Figure 3(a). Among these existing noise reduction algorithms, the mean filtering can be defined as

where B(i, j) represents the gray value of a point in the image before processing, A(i, j) represents the gray value of the point after mean filtering, N denotes the sum of pixels in the neighborhood of the point, and P stands for the set of coordinates of these points in the neighborhood. The mean filtering algorithm is easier to operate with higher processing speed. The experimental result of the mean filtering has been shown in Figure 3(b), where the gray distribution of the local pixels in the image is relatively average and the overall image looks smoother.

The mask smoothing, referring to the common local smoothing algorithm, is frequently utilized to improve the overall quality of the image, which makes the brightness of the image more even. This algorithm can detect the edge in the image by solving the variance and the average value, according to the difference between the foreground and background characteristics. Then, the template is implemented to calculate the smoothing effect. The experimental result of the mask smooth filtering is shown in Figure 3(c).

The median filtering algorithm, as an effective method widely utilized in image preprocessing, processes the image with a sliding window. Its general process consists of two steps, setting the sliding window with the target pixel as the center, and replacing the target pixel value with the median of all the pixels in the window. The image after pre-processing with median filtering algorithm is illustrated in Figure 3(d) for comparison.

It can be observed from Figure 3 that the mean filtered image is smoother, but it is easy to lose information and the filtering effect on salt and pepper noise is limited. Compared with mean filtering algorithm, the smooth and median filtering algorithms can better reduce the noise in the image. However, the calculation time of smooth filtering is much higher than that of median filtering. Based on the comparison involving the above characteristics, the median filtering with the 5 × 5 template will be utilized to process the table image.

2.2.   Binarization

Binarization algorithms, which can enhance the foreground component and weaken the background component, also play a vital role in table image preprocessing. The detection accuracy of edge information and characters in table recognition depends on the effect of binarization. After binarization, the table images retain only the main information such as table lines and text characters. Many global and local binarization algorithms have been proposed, such as the Otsu algorithm and the Bernsen algorithm. Among these binarization algorithms, the Sauvola algorithm is a classical local binarization algorithm proposed for images suffering from poor or uneven illumination. Specifically, this algorithm takes the local mean as the benchmark, makes a fine-tuning according to the standard deviation, and then uses the integral graph method. It takes a sliding window with the size is $w*w$ and solves the threshold T(x, y) in the window. Accordingly, this algorithm can be described as

with R, m(x, y) and s(x, y) being the maximum standard deviation of gray scale, the average gray value, the standard deviation in the sliding window, respectively. Here, k is a correction factor ranging from 0 to 1. It should be mentioned that the value 128 is usually assigned to R during the calculation.

The Sauvola algorithm can deal with the images suffering from uneven illumination, but it is not robust enough for low-contrast areas and often results in loss of detail. In this paper, an improved robust binarization algorithm based on the Sauvola algorithm is proposed for degraded table images with low contrast, uniform background, and uneven illumination. To enhance the robustness of the contrast region and reduce the loss of detail in the low contrast region, m(x, y) representing the mean of the pixel values within the window in the Sauvola algorithm, is replaced by the geometric mean of m(x, y) and maximum value max(x, y) in the window, which can be illustrated as

For the table image under uneven illumination in Figure 4(a), the Otsu algorithm has poor performance, and many black blocks appear in the uneven portion, which causes a greater impact on the subsequent recognition, which could be seen in Figure 4(b). The Sauvola algorithm and the proposed algorithm have better performance in areas under uneven illumination. However, as illustrated in Figure 4(c), the Sauvola algorithm is prone to losing details in processing areas with low contrast. It can be clearly observed from Figure 4(d) that the proposed algorithm performs better under uneven illumination with stronger robustness and less information loss in low contrast regions.

2.3.   Correction

The table images obtained could be tilted and deformed due to the placement of the target or the angle of the camera. In what follows, it is crucial to implement image correction in table image pre-processing. Before correcting the table image, whether the table image constitutes a regular rectangle should be firstly determined. After that, the distances between the center and the four endpoints in the table image are calculated and then used as a criterion for correction. Common correction methods include tilt correction ^[24], correction method based on projection ^[25], and correction method based on contour extraction ^[26].

In this paper, a tilt correction method based on the modified Hough transform is adopted when the table in the image is regular rectangle. Table characteristics such as horizontal and vertical lines are obtained by the modified Hough transform. Then, the detected longest line segment is used to calculate tilt angle, which can be obtained according to the following relation,

where α represents the tilt angle of the image and β refers to the tilt angle of the line segment. The original image and the image processed by tilt correction have been shown in Figure 5(a) and (b) respectively, which show the effectiveness of the proposed method.

If the table in the image is not a regular rectangle, perspective correction technology could be implemented to process this image ^[27]. Perspective correction projects the original image onto a new visual plane with the perspective transformation ^[28]. Specifically, the coordinate system (u, v) in the original image is converted to a new coordinate system (x, y). The common transformation formula for the perspective transformation can be generally expressed as

where $x = x'/w', \text{ }y = y'/w'$. Also, the transformed matrix can be described as

where T₁ indicates that the image is linearly transformed, T₂ is used to produce a perspective transformation, and T₃ represents the translation of the image. The four endpoints of the quadrilateral in the table image are selected as reference points, which are used to obtain the transformation matrix of perspective transformation. In order to show the effectiveness of perspective correction, experiments have been performed on the original image and the perspective-corrected image respectively, as shown in Figure 6.

3.   Table lines extraction and cells location

3.1.   Table lines extraction

Common methods for detecting table lines include projection-based detection algorithms, detection algorithms based on directed single-link chains, and morphological-based detection algorithms. Among these existing methods, the morphological method ^[29] is one of the most widely used techniques to extract image components that contain useful information for expressing and depicting the shape of the region in the image. The subsequent recognition work can obtain the most essential shape features of the table such as boundaries and connected areas, where erosion and dilation are the most basic operations.

The erosion operation with a structure element S shrinks the subset S[w] of the image W that is congruent with the structure element to point w. The shrinking process is called erosion, which is defined as

Erosion eliminates small-scale details such as burrs from a table image with the targets and non-targets separated by selecting structural elements with different specifications for specific situations.

Different from the erosion operation, the dilation operation is utilized to expand the subset S[w] of the image W that is congruent with the structure element S to point w. This expanding process is called dilation and can be described as

It should be mentioned that the dilation of an image can expand both the inner and outer boundaries of regions, supplement the cavity and connect similar objects.

In this paper, the horizontal and vertical structure elements have been selected to detect the horizontal and vertical lines of the table. The extraction algorithm uses an open operation on the binarized table image, i.e., the table image is eroded and then expanded, which can effectively eliminate edge burrs. As shown in Figure 7, it can be observed that the outlines of the tables have been extracted.

Due to the complexity of the natural scene, the table lines detected by the morphological operation are particularly prone to uneven thickness. The thinning algorithm should be further applied to delete meaningless contour points in the image and keep only the bone points, which makes the table contours evenly distributed ^[30]. Refinement algorithms, such as Hilditch algorithm ^[31], OPTA algorithm ^[32], Zhang fast parallel algorithm ^[34], and morphological methods, have been widely utilized in image processing. This paper adopts the morphological method to refine the table image and obtains a satisfactory skeleton diagram. As shown in Figure 8, the outlines of the table lines are clear and evenly distributed.

3.2.   Table cells location

A method to estimate the line height of characters based on the connected domain has been proposed to solve the connected domain on the separated table illustrated in Figure 9 ^[34], which makes it easy to get the height and width histograms in the connected domain. Projection of the table image along the y direction is utilized to calculate the height of table cells, as shown in Figure 10.

Each table cell can be obtained based on the mutually exclusive relationship between the contours. The table image is composed of rectangular boxes, and each rectangular box is a relatively independent contour. Specifically, estimate the average line height of the characters. According to the filling characteristic of the table characters, the average line height of the characters is labelled as hchar, the height of a contour is h, and the width is w. The following restrictions are imposed

Then, add the filter conditions to the contours obtained in the previous step to filter out all the rectangular contours. Iterate through all the rectangular contours and compare each contour with the rest of the contours with the method based on mutual exclusion. The main code is listed as following

Therefore, the rectangular contours filtered by the algorithm based on mutual exclusion can be obtained as the target cells, as shown in Figure 11.

Locating the cells of the table image, labeling and sorting them, and then entering them into the character recognition module for identification are crucial steps in the whole system. We found through experiments that the previous image preprocessing are actually indispensable due to the fact that these tasks could affect the final accuracy of the table recognition and the robustness of the system. First, a large amount of obvious noise in the image can be filtered by denoising, which is the most basic operation and is beneficial to subsequent operations. The image binarization algorithm ensure clearer outlines and more prominent characters of table images. Different correction algorithms are utilized to obtain a relatively clear and flat table images. It is considerably conducive to applying morphological operations to position the table outline and accurately locate the table cells to improve the recognition accuracy of cell texts. In summary, image preprocessing is the basis of the table recognition system. Better preprocessing algorithms could improve the positioning rate of the table and the recognition accuracy of cell texts.

4.   Recognition of printed characters

Recognition of printed characters is a very important step in the table recognition. Traditional methods of character recognition include the methods based on statistical pattern ^[35] and structural pattern ^[36]. In the past several decades, deep learning has achieved great success in the field of image processing. Since the birth of the AlexNet network ^[20], various deep convolutional networks have continually updated the accuracy of various classification tasks. From AlexNet to ZF Net ^[37], VGGNet ^[38], GoogLeNet ^[39], ResNet ^[21] and DenseNet ^[40], CNNs are growing faster and faster. In addition, Long Short-Term Memory (LSTM) ^[41], GRU ^[42], hierarchical multiscale recurrent neural network (RNN) ^[43] and bidirectional LSTM ^[44], which focus on processing time series data, also have been employed in the field of speech processing and natural language processing. RNN has a memory function for the information of the past moment ^[41], that is, the input of the current hidden layer of RNN not only comes from the output of the input layer, but also from the output of the previous hidden layer. In this paper, the CNN+LSTM network is employed to identify characters.

The architecture of a convolutional neural network for identifying printed characters has been illustrated in Figure 12, where CNN adopts the classic VGG16 network. The 3rd and 4th max pooling layers of VGG16 take a 1 × 2 rectangular pooling window due to the fact that the text images are mostly shorter and wider. The feature sequence of the input image obtained through the deep convolutional network is further processed by the LSTM algorithm, which is a special form of RNN and often used as a solution to sequence data. The LSTM network subtly adds the input, output and forget gates, and the self-looping weight of the network is constantly changing. According to the network structure of LSTM, the output can be obtained as following

where ${{i}_{t}}$ represents the input threshold, ${{f}_{t}}$ represents the forgotten threshold, ${{\tilde{C}}_{t}}$ refers to the state of the cell at the previous moment, C_t refers to the state of the cell at this time, O_t represents the output threshold, h_t stands for the output at this time and h_t-1 stands for the output at the previous moment. The symbols b_f, b_i, b_c, and b_o indicate the activation result of the corresponding value in the current state, respectively.

The large-scale dataset used in this paper was generated by the large database and image processing technology published on GitHub, which covers multiple fonts and various printed characters such as Chinese characters, English letters, numbers, and punctuation marks. A large multi-character image data is generated for training duo to the consideration that the cell size of the table and the length of the characters in the table cell are not fixed. Specifically, there are 30000 × 100 images for training and 30000 images for testing. Data augmentation was performed with OpenCV ^[29] in order to further enhance the generalization of the training model. Specifically, data enhancement methods include text blurring, text tilting, text rotating, font stretching, adding different backgrounds and noises, stroke adhesion, and stroke break were applied. Figure 14 shows some pictures for training and testing from the augmented dataset containing the images with different character types and lengths.

In the training phase, the algorithm has been developed on ubuntu 16.04 with a single RTX 2080TI graphics card by using Python and Pytorch ^[46]. Also, the root mean square prop (RMSprop) algorithm ^[47] is utilized to optimize the network parameters, where the batch size is 64 and the initial learning rate is 0.0001. In the development environment of Ubuntu16.04 + Anaconda, the network model is implemented by using the development framework of pytorch and the training of the model is completed on the server of the laboratory. Figure 13(a, b) show the curve of loss reduction and accuracy curve during training respectively, which indicates that the loss of the train dataset goes to 0.4 and the loss of the test dataset approaches 0.45 after the model iterates 50 epochs. At this time, the corresponding train accuracy becomes stable at 96.7% and the test accuracy is stable at 96.3%. The experiment finally obtained a depth network model with a recognition accuracy of 96.7% to identify the character data in the table.

In order to verify the validity of the proposed recognition algorithm, 200 cell text images have been selected as experimental data for the comparison with the Resnet network. As listed in Table 1, the experimental results clearly show that the recognition accuracy and speed of the CNN + LSTM algorithm used in this paper are better than those of the Resnet network.

5.   Design of recognition system

In this paper, an android-based app has been developed by integrating the proposed recognition algorithm with its interfaces shown in Figure 15. In order to verify the recognition performance of the proposed recognition algorithm, 105 table document images obtained in the natural scene with different shapes and backgrounds have been collected. Performance comparison was carried out with the common software system on the market and some existing table detection methods, as shown in Table 2. It can be observed that the proposed recognition system and the existing recognition systems in the market both have a high recognition rate for the normal printed tables, while the former outperforms other methods on recognition rate for table images in the natural scene with the noise, blur, distortion and other conditions.

6.   Conclusion

In conclusion, a novel recognition system for table images in natural backgrounds has been proposed. In the process of table image recognition, image pre-processing methods including denoise, binarization, tilt correction, and perspective correction are first performed. Morphological operations, refinement, and a contour mutual exclusion algorithm are then utilized to locate the table. The CNN + LSTM network is employed to identify characters in cells with an accuracy of 96.5%. A table recognition APP is developed based on the proposed system with effective frames and optimal algorithms, which is more effective than other table recognition methods. Furthermore, the results of comparative experiments have demonstrated that the proposed method show higher accuracy than the existing commercial recognition system and methods. It is hoped that the proposed solution could be of significance for the table recognition. Further research will focus on improving light-weight architecture and recognition accuracy, and further applying it to more complex recognition tasks, such as the variety of tables with severe distortions, etc.

Acknowledgement

This work is supported in part by the National Natural Science Foundation of China (NSFC 61673163), Chang-Zhu-Tan National Indigenous Innovation Demonstration Zone Project (2017XK2102).

Conflict of Interests

The authors declare that there is no conflict of interest regarding the publication of this paper.