{'fraction_non_alphanumeric': 0.03968500673505336, 'fraction_numerical': 0.015335198425033674, 'mean_word_length': 4.649107404155692, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Otsu’s Thresholding Method Based on Plane Intercept Histogram and Geometric Analysis

The Three-Dimensional (3-D) Otsu’s method is an effective improvement on the traditional Otsu’s method. However, it not only has high computational complexity, but also needs to improve its anti-noise ability. This paper presents a new Otsu’s method based on 3-D histogram. This method transforms 3-D histogram into a 1-D histogram by a plane that is perpendicular to the main diagonal of the 3-D histogram, and designs a new maximum variance criterion for threshold selection. In order to enhance its anti-noise ability, a method based on geometric analysis, which can correct noise, is used for image segmentation. Simulation experiments show that this method has stronger anti-noise ability and less time consumption, comparing with the conventional 3-D Otsu’s method, the recursive 3-D Otsu’s method, the 3-D Otsu’s method with SFLA, the equivalent 3-D Otsu’s method and the improved 3-D Otsu’s method.


Introduction
Image segmentation is one of the most important branches in digital image processing [8]. It is useful in distincting objects from background in digital images. So far, there are a variety of image segmentation methods [1,9]. Automatic threshold selection is widely prevalent in all existing segmentation techniques due to its simplicity, accuracy and robustness. Threshold segmentation methods can be divided into two categories: 1. The global threshold which selects a single threshold from the image histogram. 2. The local threshold, computing an independent threshold for each pixel on a local window that is locally binarized. Although the global threshold is simple and effective, there is a drawback that relies on uniform illumination. The local threshold method is effective for non-uniform illumination image, but it is computationally complex and slow to run [15].
In global threshold techniques, Otsu's method is one of the best methods for image segmentation. Its global threshold is chosen according to the maximum between-class variance of histogram [7]. However, Otsu's method uses only one-dimensional histograms of images, ignoring the spatial correlation of pixels in the image. So, when the image contains noise, it is not easy to get effective segmentation. For this reason, Liu et al. [9] extended the 1-D histogram to a 2-D histogram [5], the gray information of each pixel is combined with the spatial related information in its neighborhood to propose a 2-D Otsu's method. 2-D Otsu's method obtains more satisfactory results, because the 2-D histogram not only utilizes the gray value distribution of the image, but also the spatial correlation of pixels in the neighborhood. The traditional 2-D Otsu's method assumes that the sum of the probabilities of the diagonal quadrants is approximately one and ignores the points in the second and third quadrants close to the diagonal, resulting in inaccurate segmentation. As the noise increases, the performance of 2-D Otsu's method unceasingly decreases. Therefore, based on the median gray value, Jing created Three-Dimensional (3-D) histogram and proposed 3-D Otsu's method [6]. As we all know, mean filter and median filter can effectively eliminate noise. Therefore, 3-D Otsu's method performs better than 2-D Otsu's method for low contrast and Peak Signal-To-Noise Ratio (PSNR) images. However, due to the introduction of median information, its computational complexity is sharply increased. In response to this shortcoming, several improved methods have been proposed. Jing proposed a recursive algorithm to reduce the computational complexity from O (L 6 ) to O (L 3 ) [6]. Based on this result, Fan revised the recursive formula and derived a fast iterative algorithm, which remains complexity of computation in O (L 3 ) and reduces the operation time dramatically [4]. Wang proposed a threshold selection method based on Shuffled Frog Leaping Algorithm (SFLA) to accelerate the original 3-D Otsu's method [16]. Sthitpattanapongs a proposed a method that independently selects each threshold component in the threshold vector instead of a threshold vector as a whole to reduce the computational complexity from O (L 6 ) to O (L) [13]. In addition, like 2-D Otsu's method, 3-D Otsu's method only considers two cuboid regions diagonally in the threshold calculation and ignores the target points and background points in other areas around the diagonal. Therefore, the segmentation results are not accurate enough.
A lot of methods have been presented to improve the segmentation accuracy of 2-D Otsu's method. Fan proposed a curve threshold segmentation method and divided 2-D histogram into two regions by a curve [3]. Wu proposed 2-D histogram oblique segmentation method, that used four paralleled oblique lines to divide the histogram into noise, edge and inner parts, and select threshold based on the oblique lines perpendicular to the main diagonal [17]. By establishing a line intercept histogram and finding the optimal intercept threshold based on this histogram, Zhi-yong et al. [19] proposed line intercept histogram based Otsu's method [11,19]. All these methods spent less time and performed much better than 2-D Otsu's method. Similar methods applied to 3-D Otsu's method are expected to obtain better segmentation performance. Inspired by Otsu's method based on line intercept histogram [19], in this paper, we proposed a Otsu's method which uses a plane intercept histogram to select the threshold, reducing the computational complexity from O(L 6 ) to O(L). And then segmented images according to geometric analysis, in order to obtain more accurate results and improve segmentation effect. We call our method "Otsu's method based on Plane Intercept Histogram and Geometric Analysis (PIHGA based Otsu's method)". Compared with the conventional 3-D Otsu's method [6], the fast recursive 3-D Otsu's method [4], the fast 3-D Otsu's method with shuffled frog-leaping algorithm [16], the equivalent 3-D Otsu's method [13] and improved 3-D Otsu's method [2], the proposed method can segment images with less computational cost and provide more satisfactory results for images with different noises.
The structure of this article is as follows: Section 2 introduces 3-D Otsu's method. Section 3 describes in detail the PIHGA based Otsu's method. Section 4 shows the simulation results. And section 5 gives the conclusion.

3-D Otsu's Method
The gray level of M×N image is L, f (x, y) represents the gray value of the pixel (x, y). And g(x, y) is defined as its gray mean in the neighborhood of k×k centered on the pixel (x, y)      (1) and (2), L also represents the levels of g (x, y) and h(x, y). For each pixel, we construct a triplet (i, j, k) with its gray value, neighborhood mean, and neighborhood median. As shown in Figure 1 We select (s, t, q) as a set of segmentation thresholds shown in Figure 1 (b), (c) and (d), the 3-D histogram is divided into eight cuboid regions. Due to the strong correlation between pixels in the regions of object and background, the values of these three elements are very close. However, the three values of noise (or edge pixels) are obviously different. Based on the above analysis, the cuboid areas 0 and 1 can represent the object and the background area. Noise and edge areas can be represented by regions 2-7. In most cases, the edge pixel is a small part of the entire image. Therefore, the traditional 3-D Otsu's method assumes that the probability of pixels appearing in the rectangular region 2-7 is approximately equal 0. The threshold vector is (s, t, q), and the probabilities of object and background can be expressed as h(x,y)  (1) And the corresponding mean vectors are shown as The total mean vector of the 3-D histogram is: According to the assumption that the probabilities of pixels appear in the cuboid regions 2-7 are negligible, then The between-class discrete matrix is: The trace of sB can be expressed as The optimal threshold vector (s0, t0, q0) is

Proposed Method
3-D Otsu's method provides better segmentation results than 2-D Otsu's method, but it still has the following shortcomings: 1. 3-D Otsu's method is also based on just two cuboid regions along the diagonal in the threshold calculation, so that the segmentation result is not accurate enough. 2. The introduction of the median of the neighborhood pixels sharply increases the computation complexity. In view of the above problems, some improvements are proposed to improve the performance of 3-DOtsu's method.

Plane Intercept Histogram Based Otsu Criterion
As shown in Figure 2, 2-D Otsu's method only considers the diagonal regions A and B, and ignores the off-diagonal regions C and D, which will lead to the loss of important information in the segmentation process. To overcome this shortcoming, Sahoo proposed used a threshold line (denoted by l in Figure  2(a)) to partition 2-D histogram into two parts, which provided better segmentation [12]. However, this method may be very time-consuming, the 256×256 histogram may be bisected by one of the 4×105 lines [11]. Based on these threshold lines, He et al. proposed a new Otsu's method [19]. As shown in Figure 2(b), the new Otsu's method considered the intercepts of line l perpendicular to principal diagonal as a new variable T, constructed its histogram and then selected the optimal threshold based on maximum variance criterion. Inspired by the principle of Otsu's method based on line intercept histogram, this paper uses a faster and more efficient method to partition 3-D histogram. From Figure 3, plane α that perpendicular to main diagonal partitions the 3-D histogram into two regions, and its intercept is T. According to Otsu's method based on line intercept histogram, we consider T=i+j+k as a new variable. cT denotes the number of occurrence of T, and the corresponding occurrence frequency is denoted by pT which can be expressed as histogram'. Therefore, each bin in a plan intercept histogram comes only from one of the intercept planes in the 3-D histogram. In this way, the 3-D histogram was reduced to a 1-D histogram with variable T. Figure  4 illustrates an example of plane intercept histogram. In Figure 4, the size of the noise-damaged Lena image is 512×512. And the size of the neighborhood is 3×3.
In image segmentation, we adopt the threshold criterion similar to 1-D Otsu's method to obtain threshold T, i.e.,  From Figure 3, we know that the plane intercept histogram considers all the pixels in the image, and can avoid ignoring important information. The plane intercept histogram is a 1-D histogram, and its computational complexity is only O(L). Although the computational complexity of equivalent 3-D Otsu's method is also O(L) [14], it needs to establish three 1-D histograms and selects three thresholds from these histograms, respectively. So the operation time of the Otsu's method based on plane intercept histogram is dramatically reduced. In addition, Otsu's method based on plane intercept histogram does not need additional space, which is essential for recursive algorithms such as recursive algorithm [6] and its revision [4].

Geometric Analysis Based Method for Image Segmentation
As shown in Figure 1 The conventional 3-D Otsu's method ignores the regions 2-7, which may contain important information, resulting in the dissatisfaction of the segmentation. For example in Figure 5, the point P located in region 2, whose gray value, neighborhood mean and neighborhood median are denoted by fP, gP and hP, respectively. Obviously, both gP and hP are much smaller than fP, so P may be a noise point in the object region. According to Equation (16), point P will be classified into the background region, it will still be a noise point in the segmented image.
h(x,y) In order to overcome this problem and make the segmentation results more accurate, we analyzed the geometric histogram that shown in Figure 5 and proposed a new method for image segmentation, which we named it "Geometric analysis based method for image segmentation". Therefore, we need to analyze the shadow regions 2-7. We use Disij, Disik, Disjk and Rm to denote ij  , ik  , jk  and region m (m=2,...,7), respectively. For a point (i, j, k) in Rm, we classify it according to the following algorithm: The gray value, neighborhood mean and neighborhood median of these points located in other regions (such as regions 0 and 1 in Figure 1) are very close to each other. So the effect of the replacement as the above algorithm is negligible. Based on the analysis above, a new method for image segmentation can be proposed as follows: Obviously, the points located in those regions may apply to one of the circumstances above.

Experiments and Discussion
In order to demonstrate the performances of our method, compare it with the conventional 3-D Otsu method [6], the recursive 3-D Otsu's method [4], the 3-D Otsu's method with SFLA [16], the Equivalent 3-D Otsu's method [13] and the improved 3-D Otsu's method [2]. This section contains four parts: in the first subsection, two widely used evaluation measures were introduced to estimate the performances of the methods above; in the second subsection, we used these methods to segment images corrupted with different noises, and compared their performances; in the third subsection, stability of these methods was analyzed; in the fourth subsection, the efficiency of these methods was compared. All the relevant experiments were implemented in Matlab R2009b on a PC with 2.7 GHz Pentium(R) CPU and 2.0 GB RAM, under Windows XP Operating system.

Performance Evaluation
Researchers believe that efficient segmentation should yield high intra-region uniformity and accurately classified images. Therefore, two widely used objective measures, Intra-Region Uniformity (IRU) [10,18] and Misclassification Error (ME) [13,14], are used to evaluate the quality of segmentation. The first measure, IRU, is based on the sum of the variances of the regions in the segmented image. Its normalized value can be computed by Where μi is the average gray level of the ith region Ri, H is the number of regions. The total number of pixels in the image is M×N. fmax and fmin represent the maximum and minimum gray levels of the image, respectively. The closer to 1 IRU is, the more uniformity of segmentation is. The second measure, ME, reflects the number of wrongly assinged both foreground pixels in background and background pixeels in foreground. ME can be simply expressed as Where FO and BO represent the foreground and background of the original image, and FT and BT denote the foreground and background of the segmented image. * is the cardinality of '*'. Obviously, the closer to 0 ME is, the more accuracy of segmentation is.

Comparison with Other 3-D Otsu's Methods
To testify the effect of our method, we test its segmentation effect under the conditions of different noises. Lena and Peppers are damaged with different kinds of noise, used as test images shown in Figure 6. The results of these methods were shown in Figures 7,8,9,and10. From Figures 7, 8, 9, and 10, we know that the results obtained from the equivalent 3-D Otsu's method, the improved 3-D Otsu's method and the proposed method are better than those obtained from the conventional 3-D Otsu's method. The results obtained from the equivalent 3-D Otsu's method and the improved 3-D Otsu's method are relatively close, and PIHGA based Otsu's method obtains the best results.
In Table 1, the IRU value of PIHGA based Otsu's method is higher than other methods, and its ME value is lower than others' values. According to Table 1 and the segmented images in Figures 7, 8, 9, and 10, we can conclude that PIHGA based Otsu's method has the best segmentation results.

Stability of Various Methods
In this subsection, we test robustness of those methods under noisy conditions. We selected House and Cameraman as our test images. We added Salt-andpepper noise to House to generate 10 images with intensity δ varies from 0.01 to 0.1, and added Gaussian noise to Cameraman to generate the other 10 images with variance σ 2 varies from 0.01 to 0.1. The test images are shown in Figures 11, and 12. Figures 13  and 14 show the graphs of different segmentation methods. According to the graphs, IRU values of each method decreased with the increase of δ, while ME values of each method increased with the increase of σ 2 . The higher the IRU values and the lower the ME values, the better the threshold image is. Both IRU and ME values of PIHGA based Otsu's method are better than others' values. Compared with other methods, the IRU and ME values of PIHGA based Otsu's method changed much slower, which means that it is more robust.

Computational Complexity Analysis
In many tasks of image processing, the time cost must be considered as an important performance index. The computing time also becomes an important influence factor for thresholding method that used widely. We use Lena, Peppers, House and Cameraman images of various sizes, and the sizes of these images vary from 100×100 to 1000×1000. Table 2 Figure 11. House images corrupted with salt-and-pepper noise, from δ = 0.01 to δ = 0.1.    From Table 2, we can see that the time required by the recursive 3-D Otsu's method and the improved 3-D Otsu's method is less than it required by the conventional 3-D Otsu's method. Due to the avoidance of exhaustive search, the time required by the 3-D Otsu's method with SFLA is also less than it required by the conventional 3-D Otsu's method. In addition, the time required by the equivalent 3-D Otsu's method and the PIHGA based Otsu's method are less than that required by the others. The Equivalent 3-D Otsu's method and the PIHGA based Otsu's method use Equations (16) and (17) respectively to segment the image. Compared with Equations (16), and (17) needs to correct the pixels. And with the increase of the image size, the number of pixels to be corrected is also more. So the time consumption increases as the image size increases. Hence, the time required by PIHGA based Otsu's method is slightly more than it required by the equivalent 3-D Otsu's method when the sizes of the images are greater than 200×200.

Conclusions
In this paper, we proposed a PIHGA based Otsu's method that aiming to alleviate the drawbacks of the traditional 3-D Otsu's methods. In the proposed method, we first transform the 3-D histogram into 1-D histogram by using plane intercept; and then segment the image according to the variance-based thresholds. In addition, a geometric analysis based method was proposed to enhance the performance of segmentation against noises. Images with various noises are used to evaluate the performances of the proposed method.
Experimental results show that the proposed method significantly outperforms other 3-D Otsu's methods, and remains robust against noise. The computational complexity of the proposed method is lower than most of the other 3-D Otsu's methods while providing similar or better results. However, it can be seen from the segmentation results that its anti-noise ability still needs to be improved. In addition, an image often contains several objects, so the multi-level threshold extension of this method is worthy of further study.