# Spatially Adaptive Regularization in Image Segmentation
## 3 Solution by Split Bregman Iterations  
As mentioned in Section 1, we use an alternating minimization method to solve problem (5). Given \(u_{i,j}^{k-1}\), by imposing the first-order optimality conditions with respect to \(c_{1}\) and \(c_{2}\), we get  
\[c_{1}^{k}=\frac{\sum_{i,j}\lambda_{i,j}\bar{u}_{i,j}u_{i,j}^{k-1}}{\sum_{i,j} \lambda_{i,j}u_{i,j}^{k-1}},\quad c_{2}^{k}=\frac{\sum_{i,j}\lambda_{i,j}\bar {u}_{i,j}(1-u_{i,j}^{k-1})}{\sum_{i,j}\lambda_{i,j}(1-u_{i,j}^{k-1})}. \tag{13}\]  
For the solution of (5) with respect to \(u\), we use the split Bregman (SB) method [24]. Let  
\[G_{loc}(u,c_{1},c_{2})=\sum_{i,j}\lambda_{i,j}\left(\left(c_{1}-\bar{u}_{i,j} \right)^{2}-\left(c_{2}-\bar{u}_{i,j}\right)^{2}\right)u_{i,j}=\sum_{i,j}r_{i,j}u_{i,j}, \tag{14}\]  
where  
\[r_{i,j}=\lambda_{i,j}\left(\left(c_{1}-\bar{u}_{i,j}\right)^{2}-\left(c_{2}- \bar{u}_{i,j}\right)^{2}\right).\]  
Following [33], we reformulate the minimization problem, as follows:  
\[\begin{array}{ll}\underset{u,d_{x},d_{y}}{\text{minimize}}&\|d_{x}\|_{1}+\| d_{y}\|_{1}+G_{loc}(u,c_{1},c_{2}),\\ \text{s.t.}&0\leq u_{i,j}\leq 1,\\ &d_{x}=\
abla_{x}u,\\ &d_{y}=\
abla_{y}u.\end{array} \tag{15}\]  
Given \(c_{1}^{k}\) and \(c_{2}^{k}\), the SB method applied to (15) reads:  
\[\begin{array}{l}u^{k}=\underset{0\leq u_{i,j}\leq 1}{\text{argmin}}G_{loc}(u, c_{1}^{k},c_{2}^{k})+\frac{\mu}{2}\|d_{x}^{k-1}-\
abla_{x}u-b_{x}^{k-1}\|_{2}^{ 2}+\frac{\mu}{2}\|d_{y}^{k-1}-\
abla_{y}u-b_{y}^{k-1}\|_{2}^{2},\\ d_{x}^{k}=\underset{d_{y}}{\text{argmin}}\|d_{x}\|_{1}+\frac{\mu}{2}\|d_{x}- \
abla_{x}u^{k}-b_{x}^{k-1}\|_{2}^{2},\\ d_{x}^{k}=\underset{d_{y}}{\text{argmin}}\|d_{y}\|_{1}+\frac{\mu}{2}\|d_{y}- \
abla_{y}u^{k}-b_{y}^{k-1}\|_{2}^{2},\\ b_{x}^{k}=b_{x}^{k-1}+\mu(\
abla_{x}u^{k}-d_{x}^{k}),\\ b_{y}^{k}=b_{y}^{k-1}+\mu(\
abla_{x}u^{k}-d_{y}^{k}),\end{array} \tag{16}\]  
where \(\mu>0\).  
Closed-form solutions of the minimization problems with respect to \(d_{x}\) and \(d_{y}\) can be computed using the soft-thresholding operator:  
\[d_{x}^{k}=\mathcal{S}\left(\
abla_{x}u^{k}+b_{x}^{k},\frac{1}{\mu}\right),\quad d _{y}^{k}=\mathcal{S}\left(\
abla_{y}u^{k}+b_{y}^{k},\frac{1}{\mu}\right),\]  
where, for any \(v=(v_{i,j})\) and any scalar \(\gamma>0\),  
\[\mathcal{S}(v,\gamma)=z=(z_{i,j}),\quad z_{i,j}=\frac{z_{i,j}}{|z_{i,j}|}\max \left\{|z_{i,j}|-\gamma,\,0\right\}.\]  
Finally, an approximate solution to the minimization problem with respect to \(u\) can be obtained by applying Gauss-Seidel (GS) iterations to the following system, as explained in [33]:  
\[-\Delta u_{i,j}=\frac{r_{i,j}}{\mu}+(\
abla_{x}(b_{x}^{k}-d_{x}^{k})_{i,j})+( \
abla_{y}(b_{y}^{k}-d_{y}^{k})_{i,j}), \tag{17}\]  
where \(\Delta\) is the classical finite-difference discretization of the Laplacian. If the solution to (17) lies outside \([0,1]^{m\times n}\), then it is projected onto that set. We denote \(\mathcal{P}_{[0,1]}\) the corresponding projection operator.  
The overall solution method is outlined in Algorithm 1. Note that, when the approach in Section 2.3 is used, the values \(\lambda_{i,j}\) must be updated at each iteration \(k\), using (12) with \(u=u^{k}\).  
```
Input:\(\bar{u}\), \(\lambda_{min}\), \(\lambda_{max}\), \(f\), \(\mu\), \(\alpha\) (with \(f\) defined in (9) or (11) or (12)) Output:\(u\), \(c_{1}\), \(c_{2}\)  Set \(u^{0}=\bar{u}\), \(d_{x}^{0}=0\), \(d_{y}^{0}=0\), \(b_{x}^{0}=0\), \(b_{y}^{0}=0\)  Compute \(\Lambda=f(u^{0})\) for\(k=1,2,\ldots\)do  Compute \(c_{1}^{k}\) and \(c_{2}^{k}\) by (13)  Compute \(u^{k}\) by applying GS iterations to system (17) \(u^{k}=\mathcal{P}_{[0,1]}(u^{k})\) \(d_{x}^{k}=\mathcal{S}(\
abla_{x}u^{k}+b_{x}^{k},1/\mu)\) \(d_{y}^{k}=\mathcal{S}(\
abla_{y}u^{k}+b_{y}^{k},1/\mu)\)  Update \(b_{x}^{k}\) and \(b_{y}^{k}\) according to (16)  end for Set \(\Sigma=\left\{(i,j)\in\Theta:u_{i,j}^{k}>\alpha\right\}\)
```  
**Algorithm 1** Split Bregman (SB)-based method for spatially adaptive segmentation