ARTICLE

J. Cent. South Univ. (2019) 26: 1661-1671

DOI: https://doi.org/10.1007/s11771-019-4120-9

An enhanced image binarization method incorporating with Monte-Carlo simulation

HAN Zheng(韩征)^{1, 2}, SU Bin(粟滨)¹, LI Yan-ge(李艳鸽)^{1, 2}, MA Yang-fan(马杨帆)¹,WANG Wei-dong(王卫东)^{1, 3}, CHEN Guang-qi(陈光齐)⁴

1. School of Civil Engineering, Central South University, Changsha 410075, China;

2. State Key Laboratory of Geohazard Prevention and Geo-environment Protection, Chengdu 610000, China;

3. The Key Laboratory of Engineering Structures of Heavy Haul Railway, Ministry of Education,Changsha 410075, China;

4. Department of Civil and Structural Engineering, Kyushu University, Fukuoka 819-0395, Japan

Central South University Press and Springer-Verlag GmbH Germany, part of Springer Nature 2019

Abstract: We proposed an enhanced image binarization method. The proposed solution incorporates Monte-Carlo simulation into the local thresholding method to address the essential issues with respect to complex background, spatially-changed illumination, and uncertainties of block size in traditional method. The proposed method first partitions the image into square blocks that reflect local characteristics of the image. After image partitioning, each block is binarized using Otsu’s thresholding method. To minimize the influence of the block size and the boundary effect, we incorporate Monte-Carlo simulation into the binarization algorithm. Iterative calculation with varying block sizes during Monte-Carlo simulation generates a probability map, which illustrates the probability of each pixel classified as foreground. By setting a probability threshold, and separating foreground and background of the source image, the final binary image can be obtained. The described method has been tested by benchmark tests. Results demonstrate that the proposed method performs well in dealing with the complex background and illumination condition.

Key words: binarization method; local thresholding; Monte-Carlo simulation; benchmark tests

Cite this article as: HAN Zheng, SU Bin, LI Yan-ge, MA Yang-fan, WANG Wei-dong, CHEN Guang-qi. An enhanced image binarization method incorporating with Monte-Carlo simulation [J]. Journal of Central South University, 2019, 26(6): 1661-1671. DOI: https://doi.org/10.1007/s11771-019-4120-9.

1 Introduction

Binary image representation in textual image techniques is one of the preferred formats for image analysis [1]. It aims at distinguishing the foreground from the background. This technique converts all pixels of the image into two categories with separated colors such as light or dark [2], decreasing the presence of unwanted data and preserving only the desired data in the image [3]. A robust, automatic, and efficiency binarization algorithm is required to attain a satisfactory binary result. The threshold-based methods are an indispensable component of binarization algorithms. They permit to rapidly binarize the images with one or more thresholds, and thus become an efficient solution. Previous studies [4-6] classified the up-to-date threshold-based methods into two major categories, i.e., global thresholding methods and local thresholding methods.

Logically, simple thresholding methods benefit pre-processing and post-processing on the image [5]. The most basic ones are global thresholding methods, which choose a fixed threshold and compare each pixel to that. As a remarkable work, Otsu’s algorithm derives an overall threshold based on the maximum of the between-class variances, and binarizes the image according to this threshold [7, 8]. Global thresholding methods are advanced in the simple implementation and high computation efficiency [9]. Our previous study [10] demonstrated that global thresholding methods perform well in the case of the grey-level histogram of the image approximating a balanced bimodal type. However, the grey-level histogram often approximates a mixed unimodal type when the image contains various background patterns, multiple noises, illumination levels, and shadows. In this case, global thresholding methods are often limited to interpret foreground from the image [11].

By contrast, local thresholding methods compute different thresholds based on the information contained in the neighborhood for each pixel, or a small region of the image independently [6, 12-21]. Hence, they are also referred as the local adaptive thresholding methods. Some current studies support that Niblack’s method, Sauvola’s method, and NICK’s method perform better [8, 22]. However, these sophisticated compound methods are often costly and complex to design [23]. Commonly, these local thresholding methods are based on adaptive thresholding algorithm in fixed square blocks, implying that they are scale- dependent and require empirical tuning on the block size [5]. Nevertheless, uncertainties of block size challenge the application of local threshold methods. Firstly, block size has long been substantiated having a significant influence on the binarization results [24]; however, it lacks a widely-accepted criterion, and requires empirical adjusting before executing the binarization algorithm. Secondly, local binarization in the fixed block is likely to generate interference left between two neighbored blocks [6], because the binarization results in the neighbored block may be opposite. We call this kind of interference “the boundary effect” and find that it is difficult to eliminate in post-processing.

In this paper, we report an enhanced image binarization method. The proposed method first partitions the image into a number of square blocks that reflect local characteristics in the entire image. After image partitioning, the binary image of each block can be obtained by using Otsu’s thresholding method. To reduce the influence of the block size and the boundary effect, we incorporate Monte- Carlo simulation into the binarization algorithm. Varying block sizes during the Monte-Carlo simulation generates a probability map. By setting a probability threshold, the final binary image that delineates the foreground can be obtained. The proposed method addresses two essential issues with respect to complex background and illumination condition, and uncertainties of determining block size in local thresholding method.

2 Methods

In line with the inspirations of previous local thresholding methods, we propose an enhanced local thresholding method integrating with Monte- Carlo simulation. It is an extension of previous methods. The proposed method is composed of four major steps as described below.

2.1 Configuration of Monte-Carlo simulation

The first step of the proposed method is to configure Monte-Carlo simulation. Monte-Carlo method uses repeated random sampling to simulate data for a given mathematical model and evaluate the outcome. In this sense, the core of the Monte- Carlo simulation is to create a large, random data set so the uncertainties of inputs can be covered by this data set [25]. The total number of this data set is named of the Monte-Carlo steps (MCS, S_MC). Such as, S_MC=20 refers to that the procedure will repeat 20 times. Ideally, the larger MCS generates better data set for the following analysis. However, it linearly increases the amount of computation.

2.2 Image partitioning with random block size

In each step of Monte-Carlo simulation, the original grey-level image is imported. f(x, y) refers to the grey-level image with size M×N, where (x, y) represents the coordinate of each pixel in the image. We use square blocks with uniform size to partition the majority of the image. As mentioned above, the block size has a significant influence on the binarization results, but it is scale-dependent and requires empirical tuning. In our study, the block size, notated as D, is regarded as the only random variable in the Monte-Carlo simulation. It obeys the uniform distribution ranging between D_min and D_max, which are the manipulated parameters. Theoretically, D_min could be as small as one pixel, and D_max extends up to min(M, N). However, to obtain a better binarized result, we suggest empirical values that D_min=10 pixels, and D_max= min(M, N)/2, ensuring that the block size D would not exceed the image size M×N. Discussion on the optimized values of the parameters D_min and D_max is ongoing.

As shown in Figure 1, for most of images, the number of rows M does not strictly equate the number of columns N, which means the square blocks could not completely cover the entire image. In the case of it, we use rectangular blocks of different sizes to fill the remaining fragmented part. The sizes of the remaining blocks are calculated by

D′=M mod D                            (1)

D″=N mod D                            (2)

where D' and D'' are the remainders of the term (M/D) and (N/D), respectively. In this sense, four types of blocks, with sizes of (D, D), (D', D), (D, D'') and (D', D'') are used to partition the image in a Monte-Carlo step.

Figure 1 Schematic illustration for image partitioning using blocks in a Monte-Carlo step (Blue region represents area partitioned by square blocks, while red region denotes remaining fragmented area partitioned by rectangular blocks)

2.3 Image binarization

In each Monte-Carlo step k, the sub-images of the blocks are independently binarized. The whole binary image is subsequently obtained by integrating the amount of the binary images of blocks. We use Otsu’s thresholding method [7] to calculate optimal local thresholds T_o for each block. In each block, the pixel with a lower grey level than the local threshold is labelled as foreground; otherwise, it is labelled as background. Assuming that f ′_k(x, y) refers to the binary image at the step k, we assign the foreground pixel a value of f ′_k(x, y)=1, while the background pixel f ′_k(x, y)=0. The detailed equation can be expressed as

                   (3)

Notice that the representation of the foreground and background differs by purposes. For most of cases in character recognition, the foreground (i.e., characters) often has low grey-level value, and is highlighted in black.

2.4 Monte-Carlo iteration

In each Monte-Carlo step k, the original image f(x,y) is transited to the binary image f ′_k(x, y) using square blocks with size D. However, as illustrated by the previous studies, the binary result is quite sensitive to the block size, as well as the line- approximating interferences left between blocks that observed by the previous study [6]. Owing to the fact the block size is changed during Monte-Carlo iteration, a better solution is to comprehensively consider the binary images of all Monte-Carlo steps. An indicator P(x, y) is introduced, which is represented by

                  (4)

where P(x, y) denotes the probability of the pixel (x, y) classified as foreground. The value of P(x, y) theoretically ranges from 0.0 to 1.0. The higher value demonstrates that the pixel is more likely to be a component of foreground. The probability image is comprehensively evaluated by the following criterion.

           (5)

where P'(x, y) refers to the final binary image after Monte-Carlo iteration; T_P denotes probability threshold to evaluate the result in Monte-Carlo iteration. In order to find an appropriate probability threshold, trial-and-error adjusting can be considered, because it does not increase computational complexity. In most of cases, a better-fitting probability threshold T_P=0.8 is suggested. In order to better illustrate the improved local thresholding method, the procedure described above is represented in Figure 2.

3 Results

The quality of the binary results must be of priority concern. In this study, we compare the binarization performance of the proposed method with that of previous methods. Here, Otsu’s method [7] and Niblack’s method [15] (source code from Mathworks.com [26]) are considered owing to their lower computation in global and local thresholding methods. Some typical images in previous studies are selected as benchmarks.

3.1 Examples of optical character recognition

Examples in Figures 3-5 are the applications of the proposed method in optical character recognition. Binarization is an important step in reading text documents automatically through an image. Three source images from different databases and literature are selected. Figure 3(a) displays an original document image from PAI et al [8]. The image was taken from a paper that involves gradations of shadows. Figure 4(a) shows a similar scene with Figure 3(a). It illustrates an augmented reality example with several planar markers that are tracked in a video stream (BRADLEY and ROTH [2]). Figure 5(a) is the image P04 from the DIBCO’09 dataset. It illustrates a degraded document image that includes image contrast variation and smear (HADJADJ et al [27]).

Figure 2 Procedure of proposed Monte-Carlo iteration algorithm

Figure 3 Benchmark test 1:

Due to severe illumination gradient across the scenes, the peaks of the grey histogram corresponding to foreground and background have run together, such that simple thresholding methods like Otsu’s method could not give good results. Such limitation is obvious in Figure 3(b). Owing to the shadow in the upper part, the characters in the shadow merged with background, and could not be recognized. Although Niblack’s method performs better, the resulting binary image is rather sensitive to the block size. We test two different block sizes in each example, and the binary results demonstrate that the best-fitting block size requires empirical adjusting and varies case by case. For example, the best-fitting block size of Niblack’s method varies from 15 pixels in Examples 1 and 3 (Figures 3(c) and 5(c)) to 50 pixels in Example 2 (Figure 4(d)). Such method also has limitation regarding that some fine details are lost in the binary image. As shown in Figure 4(d), Niblack’s method with 50-pixels block size generates better results, but the patterns of the planar markers in the shadow, in particular those at the top right corner, merge with the background and are difficult to distinguish. In contrast, the proposed method yields a better outcome resembling that of Niblack’s, providing near perfect segmentation despite the strong illumination changes in the image.

Figure 4 Benchmark test 2:

3.2 Example of T-shape block recognition

Figure 6(a) shows an image of T-shape block as presented in Mathworks.com [28]. The image has significant illumination changes across the scene, so the Otsu’s method could not give good results. As shown in Figure 6(b), most of the block merges with the background. Niblack’s method generates better binary results. Figure 6(d) represents the binary image using Niblack’s method when the local block size is 400 pixels. The foreground and the background are well separated. However, the binary results degrade significantly when a smaller local block size is applied.Figure 6(c) shows that Niblack’s method fails to attain a satisfactory result using 50-pixels block size. We use a 50-steps Monte-Carlo simulation to compute the probability image (Figure 6(e)), and T_P=0.8 is selected to export the final binary image as shown in Figure 6(f). Although some interferences remain at the edge of the image,the proposed method generates acceptable binary image resembling with the best-fitting result of Niblack’s.

Figure 5 Benchmark test 3:

Figure 6 Benchmark test 4:

3.3 Example of car license plate recognition

Figure 7(a) presents a little more complicated scene. It is a captured photo of car license plate at night (as shown in Ref. [29]). High brightness of the two car bulbs significantly increases the grey level of the image, so the license plate in the middle of the car could not be well separated by Otsu’s method (Figure 7(b)). Figures 7(c) and (d) show the binary results by Niblack’s method. Although the segmentation quality is improved, the results depend upon the block size, implying that the larger block generates better results despite increasing the computational complexity. In the proposed method, a 20-steps Monte-Carlo simulation is used to produce the probability map (Figure 7(e)), and a probability threshold T_P=0.3 is selected to obtain the final binary image (Figure 7(f)). It is obvious that the license plate can be well recognized.

Figure 7 Benchmark test 5:

The above benchmark tests demonstrate that Otsu’s global thresholding method is limited to deal with complex illumination condition in the image. Niblack’s local thresholding method performs better; however, the binary result is very sensitive to the block size, which is currently empirically determined. In this sense, the proposed method yields the best results among of the methods.

4 Discussion

Our previous work [10] in image segmentation demonstrated a need for robust thresholding method of images that have mixed unimodal grey-level histograms. The proposed method in this paper is proved well-suitable for scenes with strong spatial changes in illumination, which is not the case for global thresholding methods. The major advantage of the method is that the essential parameter in local thresholding methods, i.e., the block size, is handled automatically, and requires no empirical adjusting when processing the image.

Some drawbacks of the proposed method remain. One of these drawbacks is the computational efficiency. Because images must be processed repeatedly in Monte-Carlo iteration, the computational complexity of the proposed method is an order of magnitude greater than that of Otsu’s method. However, considering the current speed of processors, the differences in time consumption could be negligible.

The main drawback is that the proposed method introduces a new parameter, the probability threshold T_P, to get the final binary image. This parameter is not relevant to computing the probability map during Monte-Carlo simulation, but it dominates the output effect of the binary image. As shown in Figure 8, a greater probability threshold T_P is beneficial to decrease the presence of unwanted data, but on the contrary, some fine details were lost. Unfortunately, the probability threshold T_P currently needs empirically manipulation and adjusting for a better output binary image. However, this is not a significant drawback because major computation finishes at the end of Monte-Carlo iteration. No computational complexity increases when adjusting T_P for the output. Efforts to address this drawback will be the next step toward making the proposed method a robust and automatic solution for image binarization work.

Figure 8 Image binarization results against different probability thresholds T_P:

5 Conclusion

An enhanced image binarization method has been presented. The proposed method partitions the image into a number of square blocks and uses local thresholds to segment the sub-image in each block. Additionally, the proposed method incorporates Monte-Carlo simulation in the local thresholding method, and addresses several essential issues that trouble previous methods, i.e., complex background and illumination condition, and uncertainties of determining block size. Some benchmark tests have been introduced to illustrate the performance of the proposed method. The method provides a new way to separate foreground and background of an image with complex background. Future work would include improving the computational efficiency, and addressing the empirical tuning problem on the probability threshold T_P.

References

[1] STATHIS P, KAVALLIERATOU E, PAPAMARKOS N. An evaluation technique for binarization algorithms [J]. J Univ Comput Sci, 2008, 14(8): 3011–3030.

[2] BRADELY D, ROTH G. Adaptive thresholding using the integral image [J]. Journal of Graphics Tools, 2011, 12(2): 13–21.

[3] KEFALI A, SARI T, SELLAMI M. Evaluation of several binarization techniques for old Arabic documents images [C]// The First Internat Symp on Modeling and Implementing Complex Systems (MISC 2010). Constantine, Algeria: Springer, 2010: 88-99.

[4] SEZGIN M, SANKUR B. Survey over image thresholding techniques and quantitative performance evaluation [J]. J Electron Imaging, 2004, 13(1): 146–168.

[5] BATAINEH B, ABDULLAH S N H S, OMAR K. An adaptive local binarization method for document images based on a novel thresholding method and dynamic windows [J]. Pattern Recognition Letters, 2011, 32: 1805–1813.

[6] WEN J T, LI S M, SUN J D. A new binarization method for non-uniform illuminated document images [J]. Pattern Recognition, 2013, 46: 1670–1690.

[7] OTSU N. A Threshold selection method from gray-level histograms [J]. IEEE Transactions on Systems, Man and Cybernetics, 1979, 9(1): 62–66.

[8] PAI Y T, CHANG Y F, RUAN S J. Adaptive thresholding algorithm: Efficient computation technique based on intelligent block detection for degraded document images [J]. Pattern Recognition, 2010, 43: 3177–3187.

[9] POLETTI E, ZAPPELLI F, RUGGERI A, GRISAN E. A review of thresholding strategies applied to human chromosome segmentation [J]. Computer Methods and Programs in Biomedicine, 2012, 108(2): 679–688.

[10] LI Y G, CHEN G Q, HAN Z, ZHANG F L. A hybrid automatic thresholding approach using panchromatic image for rapid mapping of landslides [J]. GIScience and Remote Sensing, 2014, 51: 710–730.

[11] GATOS B, PRATIKAKIS I, PERANTONIS S J. Adaptive degraded document image binarization [J]. Pattern Recognition, 2006, 39: 317–327.

[12] BERNSEN J. Dynamic thresholding of gray-level images [C]// Proceedings of the Eighth International Conference on Pattern Recognition. Paris, France: IEEE Computer Society Press, 1986: 1251-1255.

[13] YANOWITZ S D, BRUCKSTEIN A M. A new method for image segmentation [J]. Computer Vision Graphical and Image Processing, 1989, 46(1): 82–95.

[14] TAXT T, FLYNN P J, JAIN A K. Segmentation of document images [J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 1989, 11(12): 1322-1329.

[15] NIBLACK W. An introduction to digital image processing [M]. New Jersey: Prentice Hall, 1986.

[16] EIKVIL L, TAXT T, MOEN K. A fast adaptive method for binarization of document images [C]// Proceedings of the ICDAR-91, Saint Malo, France: AFCET, 1991: 435-443.

[17] SAUVOLA J, PIETIKAINEN M, Adaptive document image binarization [J]. Pattern Recognition, 2000, 33(2): 225–236.

[18] CHOU C, LIN A W, CHANG A F. A binarization method with learning-built rules for document images produced by cameras [J]. Pattern Recognition, 2010, 43: 1518–1530.

[19] TONG L, CHEN K, ZHANG Y, FU X, DUAN J. Document image binarization based on NFCM [C]// Proceedings of the 2nd Internat Congress on Image and Signal Processing. New York: IEEE eXpress, 2009: 5305330.

[20] ZHANG C, YANG J. Binarization of document images with complex background [C]// Proceedings of the 6th Internat Conf in Wireless Communications Networking and Mobile Computing. New York: IEEE eXpress, 2010: 5601007.

[21] GATOS B, NTIROGIANNIS K, PRATIKAKIS I. DIBCO 2009: Document image binarization contest [J]. Int J Doc Anal Recognit, 2011, 14: 35–44.

[22] KHURSHID K, SIDDIQI I, FAURE C, VINCENT N. Comparison of Niblack inspired binarization methods for ancient documents [C]// Proceeding of 16th International Conference on Document Recognition and Retrieval. California: SPIE, 2009: 72470U.

[23] TRIER O D, JAIN A K. Goal-directed evaluation of binarization methods [J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 1995, 17(12): 1191–1201.

[24] HAN Z, LI Y G, DU Y F, WANG W D, CHEN G Q. Noncontact detection of earthquake-induced landslides by an enhanced image binarization method incorporating with Monte-Carlo simulation [J]. Geomatics, Natural Hazards and Risks, 2019, 10(1): 219-241.

[25] HAN Z, WANG W D, LI Y G, HUANG J L, SU B, TANG C, CHEN G Q, QU X. An integrated method for rapid estimation of the valley incision by debris flows [J]. Engineering Geology, 2018, 232: 34-45.

[26] MOTL J. Niblack local thresholding [EB/OL]. [2013-5-10]. https://cn.mathworks.com/matlabcentral/fileexchange/40849-niblack-local-thresholding.

[27] HADJAJD Z, CHERIET M, MEZIANE A, CHERFA Y. A new efficient binarization method: application to degraded historical document images [J]. SIViP, 2017, 11: 1155–1162.

[28] XIONG G L. Local adaptive thresholding [EB/OL]. [2016- 3-31]. https://cn.mathworks.com/matlabcentral/fileexchange/ 8647-local-adaptive-thresholding.

[29] MARTN-RODRGUEZ F. New tools for gray level histogram analysis, applications in segmentation [C]// Proceeding of the 10th International Conference of Image Analysis and Recognition. Portugal: Springer, 2013: 326-335.

(Edited by ZHENG Yu-tong)

中文导读

基于蒙特卡洛模拟的图像二值化增强算法

摘要：本文基于蒙特卡洛模拟与局部阈值思想，提出了一种能够适应图像复杂背景、亮度不均条件的灰阶图像二值化分割方法。该方法将灰阶图像划分为多个正方形子图像，每个子图像均反映了灰阶图像的局部信息。先利用大津法对每个子图像进行二值化分割，再将所有二值化后的子图像重新合并后形成灰阶图像的二值化结果。针对局部阈值分割过程中子图像的尺寸选取问题及二值化后子图像合并时的边界效应问题，本文结合蒙特卡洛模拟思想提出了改进算法。将子图像尺寸作为蒙特卡洛计算步中的随机变量，通过大量迭代计算获取灰阶图像中每个像素被分割为目标和背景的概率，并按照指定概率阈值对其进行划分。为验证所述方法的可行性与准确性，本文依托多个灰阶图像案例对方法的二值化结果进行了测试，结果表明，本文提出的方法能够较好地处理复杂背景及亮度不均条件下的灰阶图像。本方法可为区域性遥感影像的解译和地物识别提供支撑。

关键词：二值化方法；局部阈值；蒙特卡洛模拟；基准测试

Foundation item: Project(2018YFC1505401) supported by the National Key R&D Program of China; Project(41702310) supported by the National Natural Science Foundation of China; Project(SKLGP2017K014) supported by the Foundation of State Key Laboratory of Geohazard Prevention and Geo-environment Protection, China; Project(2018JJ3644) supported by the Natural Science Foundation of Hunan Province, China

Received date: 2018-07-19; Accepted date: 2018-11-07

Corresponding author: LI Yan-ge, PhD, Associate Professor; Tel: +86-18684982076; E-mail: liyange@csu.edu.cn; ORCID: 0000-0002- 8558-0598