# Application of Image Segmentation in Surface Water Extraction of Freshwater Lakes using Radar Data
## Materials and Methods
### Otsu Method
\[V=\sum_{j=0,1}V_{j}+V_{0,1} \tag{2}\]  
Therefore, the previous objective function Equation (1) is equivalent to maximizing the interclass variance \(V_{0,1}\):  
\[\max_{C_{0},C_{1}}\sum_{j=0,1}((\sum_{i\in C_{j}}p_{i})\cdot(\mu_{j}-\mu)^{2}) \tag{3}\]  
Now, in applying the Otsu Method on the density histogram, we can have:  
* The set of all possible bin's values on the density histogram as \(\Theta\), which is also the hypothesis space for the estimation of the threshold. * The density corresponding to the bin with value \(\theta\) is denoted as \(p_{\theta}\) and we should have \(1=\sum\limits_{\theta\in\Theta}p_{\theta}\). * For each bin value \(\theta\in\Theta\), we can put a corresponding index \(i_{\theta}\) into the indexed set \(C\), where \(i_{\theta}\)-th bin on the density histogram has a bin value of \(\theta\). Therefore, \(x_{i_{\theta}}=\theta\) and \(p_{i_{\theta}}\) is equal to the density \(p_{\theta}\) of the bin with value \(\theta\) from the density histogram. * The final prediction of the threshold is denoted as \(\hat{\theta}\in\Theta\), which corresponds to the index \(i_{\hat{\theta}}\in C\). * the two separate clusters formed by a threshold \(\theta\) is \(C_{0}=\{i:i<i_{\theta},i\in C\}\) and \(C_{1}=\{i:i\geq i_{\theta},i\in C\}\). The final estimation of the threshold \(\hat{\theta}\) should be the one based on which the subcluster \(C_{0}^{*}\) and \(C_{1}^{*}\) can reach the optimal value of the objective function in Equation (3). Then, we can have:  
\[i_{\hat{\theta}}=\min_{i\in C_{1}^{*}}i \tag{4}\]  
\[\hat{\theta}=x_{i_{\hat{\theta}}} \tag{5}\]  
This optimization problem can be solved in at most quadratic polynomial time of the size of the finite set \(\Theta\), i.e., the time complexity will be \(O(|\Theta|^{2})\). One possible implementation as shown in Algorithm 1 is to iterate through the finite set and record the element in the set that provides the highest value for the objective function. Each inner iteration takes linear time to calculate the objective function. ```
Input:\(\{(\theta_{i},p_{\theta_{i}})\}_{i=1}^{|\Theta|}\) is the set of bins for the density histogram. Output:\(\hat{\theta}\) is the final prediction of the optimal threshold between the two classes. Procedure: \(\hat{\theta}\leftarrow\infty\) objective_value\(\gets 0\) for each bin \(i\) in the input density histogramdo \(C_{0}\leftarrow\emptyset\) \(C_{1}\leftarrow\emptyset\) for each bin \(j\) in the input density histogramdo if\(\theta_{j}<\theta_{i}\)then \(C_{0}\) adds \(j\) else \(C_{1}\) adds \(j\)  end if  end for curr \(\leftarrow\) Compute objective function value based on Equation (3) with using \(C_{0}\), \(C_{1}\) if\(curr>objective\_value\)then \(\hat{\theta}\leftarrow\theta_{i}\) else  end for return\(\hat{\theta}\)
```  
**Algorithm 1**OtsuMethodFindOptimalThresholding (Time: \(O(|\Theta|^{2})\))  
We can further improve the time complexity of the Otsu Method into linear time complexity of \(O(|\Theta|)\). If we store the value of \(\mu_{0}\) and \(\mu_{1}\) from previous outer loop iteration, then it will take constant time \(O(1)\) for recomputing the objective function value based on the Equation (3) for the newly updated \(C_{0}\) and \(C_{1}\) in this current round. Because the Otsu Method iterates through all the possible values for the threshold and compares the objective values with all these possible thresholds, the implementation of Otsu Method in Algorithm 1 provides a global optimal solution for the objective function in Equation (3).