Segmentation Algorithm

To obtain an initial segmentation $\{R_k^0\}_{k=1}^K$ given no a priori information about the locations of the textures in the images, the proposed method uses randomly generated regions, as shown in Section 7.6, based on the following algorithm.

1. 
   Generate $K$ images of i.i.d. uniform random noise, one for each $R_k^0$.
   
2. 
   Convolve each $R_k^0$ with a chosen Gaussian kernel.
   
3. 
   Construct the initial segmentation. $\forall k = 1, \ldots, K, \forall t \in \mathcal{T}$ do: if
   

   $$R_k^0(t) = \mathop{\mbox{max }}_{j = 1, \ldots, K} R_j^0(t),$$ (158)

   
   
   then set $R^0_k(t) = 1$, otherwise set $R^0_k(t) = 0$. In case of multiple maxima, assign the pixel to an arbitrary region among them.

The key idea behind this procedure is to try to generate an initial segmentation where each segment is spread out over the image such can we can recover the correct segments irrespective of their position in the image. The variance of the Gaussian-smoothing kernel is related to the size of the correct segments. Excessively high or low smoothing produces segments with almost-identical nonparametric Markov PDFs and, thereby, have higher chances of getting stuck in local minima during the level-set optimization. Effective smoothing produces segments with sufficiently different PDFs that drive the optimization procedure to the global minimum, i.e., the correct segmentation.

Given a segmentation $\{R_k^m\}_{k=1}^K$ at iteration $m$, the iterations in Esedoglu and Tsai's fast level-set evolution scheme [54,53] proceed as follows.

1. 
   Compute the level-set forces for all pixels in all classes:
   
   1. 
      Estimate
      

      $$P_k^m ({\bf z}_t), \forall k = 1, \ldots, K, \forall t \in \mathcal{T}$$ (159)

      
      
      via nonparametric Parzen-window density estimation as in (6.10).
      
   2. 
      Update the level-sets:
      

      $$R'_k(t) = R_k^m(t) + \beta \Bigg( \log {P_k^m ({\bf z}_t)} + \fra... ...}_k} \frac { G_d ({\bf z}_s - {\bf z}_t, \Psi_d) } { P_k^m ({\bf z}_s) } \Bigg)$$ (160)

      
      

   
   
2. 
   Regularize the level-sets:
   

   $$R''_k = R'_k \otimes G (0,\gamma^2),$$ (161)

   
   
   where $\otimes$ denotes convolution and $G (0,\gamma^2)$ is a Gaussian kernel with zero mean and standard deviation $\gamma$.
   
3. 
   Update the classification: $\forall k = 1, \ldots, K, \forall t \in \mathcal{T}$ do: if
   

   $$R''_k(t) = \mathop{\mbox{max }}_{j = 1, \ldots, K} R''_j(t),$$ (162)

   
   
   then set $R^{m+1}_k(t) = 1$, otherwise set $R^{m+1}_k(t) = 0$. In case of multiple maxima, assign the pixel to an arbitrary region among them.
   
4. 
   Stop upon convergence, i.e., when $\parallel R_k^{m+1} - R_k^m \parallel_2^2 < \epsilon$, where $\epsilon$ is a small threshold.

For a detailed discussion on the relationship between the parameters $\{ \beta,\gamma \}$ in the threshold-dynamics framework, and the parameter $\alpha$ in the traditional level-set framework, please refer to [54,53]. In short, increasing $\beta$ corresponds to increasing the PDE-driven force on the level-set evolution and increasing $\gamma$ results in smoother region boundaries.