# FADIT: Fast Document Image Thresholding
## 2 Fadit
### Speed-up Algorithms  
Suppose that an image is denoted by \(I\), and its grayscale variable is \(n\). \(\tau\) is the optimization variable and the optimal value \(\tau_{opt}\) is obtained by a criterion function. The image histogram \(H(n)\) and the total pixel number \(N\) are computed by using the image to obtain the probability \(P(n)\) of occurrence of each grayscale \(n\),  
\[P(n)=\frac{H(n)}{N}. \tag{15}\]  
The global mean of the image is calculated by,  
\[\mu=\sum_{n=0}^{L-1}nP(n). \tag{16}\]  
Using the threshold \(\tau\), \(P_{i}(\tau)\), that the text assigned to class \(i\) is given by Equation (7). The background assigned to class \(j\) is given by,  
\[P_{j}(\tau)=1-P_{i}(\tau). \tag{17}\]  
The criterion function \(C(\tau)\) is computed easily and finding its maximum is a simple algorithm as shown in Algorithm 1. ```
1:Compute the criterion function, \(C(\tau)\),
2:for\(\tau=0\) to \(L-1\)do
3:\(P_{i}(\tau)=\sum_{n=0}^{\tau}P(n)\),
4:\(f_{-}(\tau)=\frac{\mu}{\mu+\frac{\tau(\tau+1)}{2}(1-\frac{\mu}{L-1})}\),
5:\(C(\tau)=2P_{i}(\tau)f_{-}(\tau)-P_{i}(\tau)-f_{-}(\tau)+1\),
6:endfor
7:Obtain the FADIT threshold, \(\tau_{opt}=\arg\max C(\tau)\). ```  
**Algorithm 1** The FADIT algorithm. [PERSON]'s method [6] selects the threshold \(\tau\) that maximizes the between-class variance \(\sigma_{b}^{2}\) defined as  
\[\sigma_{b}^{2}=P_{i}(\tau)[\mu_{i}(\tau)-\mu]^{2}+P_{j}(\tau)[\mu_{j}(\tau)- \mu]^{2} \tag{18}\]  
where \(\mu_{i}\) and \(\mu_{j}\) are the means of grayscale of the pixels assigned to class \(i\) and class \(j\), respectively. The between-class variance \(\sigma_{b}^{2}\) has been rewritten to obtain fast algorithm [21] as,  
\[\sigma_{b}^{2}(\tau)=\frac{[\mu P_{i}(\tau)-\mu_{i}^{c}(\tau)]^{2}}{P_{i}(\tau )[1-P_{i}(\tau)]} \tag{19}\]  
where \(\mu_{i}^{c}\) is the cumulative mean grayscale up to threshold \(\tau\) and it is given by,  
\[\mu_{i}^{c}(\tau)=\sum_{n=0}^{\tau}nP(n). \tag{20}\]  
Thus, the fast [PERSON]'s algorithm is given by Algorithm 2. The criterion function of [PERSON] et al. 's method is given by [7],  
\[ \begin{split} J(\tau)=& 1+P_{i}(\tau)\log\sigma_{i}^{2}( \tau)+P_{j}(\tau)\log\sigma_{j}^{2}(\tau)]\\ &-2[P_{i}(\tau)\log P_{i}(\tau)+P_{j}(\tau)\log P_{j}(\tau)]\end{split}  \tag{21}\]  
where \(\sigma_{i}^{2}(\tau)\) and \(\sigma_{j}^{2}(\tau)\) are the variances of grayscale of the pixels assigned to class \(i\) and class \(j\), respectively. The variances \(\sigma_{i}^{2}(\tau)\) and \(\sigma_{j}^{2}(\tau)\) are calculated by,  
\[\sigma_{i}^{2}(\tau)=\frac{\sum_{n=0}^{\tau}\big{\{}[n-\mu_{i}(\tau)]^{2}P(n) \big{\}}}{P_{i}(\tau)}, \tag{22}\]  
\[\sigma_{j}^{2}(\tau)=\frac{\sum_{n=\tau+1}^{L-1}\big{\{}[n-\mu_{j}(\tau)]^{2}P( n)\big{\}}}{P_{j}(\tau)}. \tag{23}\]  
Before using Equations (22) and (23) to obtain the criterion function, \(\mu_{i}\) and \(\mu_{j}\) are calculated by,  
\[\mu_{i}(\tau)=\frac{\sum_{n=0}^{\tau}nP(n)}{P_{i}(\tau)}=\frac{\mu_{i}^{c}( \tau)}{P_{i}(\tau)}, \tag{24}\]  
\[\mu_{j}(\tau)=\frac{\sum_{n=\tau+1}^{L-1}nP(n)}{P_{j}(\tau)}=\frac{\mu_{j}^{c} (\tau)}{P_{j}(\tau)}. \tag{25}\]  
where \(\mu_{j}^{c}(\tau)\) is similar to Equation (20) and is calculated by,  
\[\mu_{j}^{c}(\tau)=\mu-\mu_{i}^{c}(\tau). \tag{26}\]  
Thus, the [PERSON] et al. 's algorithm is given by Algorithm 3. ```
1:Compute the between-class variance, \(\sigma_{b}^{2}(\tau)\),
2:for\(\tau=0\) to \(L-1\)do
3:\(P_{i}(\tau)=\sum_{n=0}^{\tau}P(n)\),
4:\(\mu_{i}^{c}(\tau)=\sum_{n=0}^{\tau}nP(n)\),
5:\(\sigma_{b}^{2}(\tau)=\frac{[\mu_{i}(\tau)-\mu_{c}(\tau)]^{2}}{P_{i}(\tau)[1-P_ {i}(\tau)]}\),
6:endfor
7:Obtain the [PERSON]'s threshold, \(\tau_{opt}=\arg\max\sigma_{b}^{2}(\tau)\). ```  
**Algorithm 2** The fast [PERSON]'s algorithm. The effectiveness of a thresholding algorithm depends strongly on the statistical characteristics of the image, and FADIT only use the probability rather than the mean and variance as shown in Table 1.