# Autonomous Prostate Segmentation in 2D B-Mode Ultrasound Images
## 4 Superpixel Algorithm Incorporating Image Statistics
### Superpixel Algorithm Outline
#### 4.3.2 Region Update  
With the cluster update sub-step completed, the region update sub-step is then performed. Region updating incorporates pixel cluster information and the calculation of image statistics to modify the individual regions \(R_{k}\) and the region adjacency graph \(\mathcal{G}\). The goal of the region update sub-step is to join neighbouring regions together so that, at the termination of the superpixel algorithm, large, statistically similar regions in the input image will be delineated. In a similar manner to the pixel cluster update, a distance metric, \(D_{KS}(k_{1},k_{2})\), will be used to inform the region update process. The distance metric used is the Kolmogorov-Smirnov (KS) test, which gives a distance between two empirical CDFs [33]. The KS test is the mechanism through which changes in image statistics in the input image will be incorporated into the region update process. Using the KS test, regions with similar statistical properties (or equivalently similar empirical CDFs) will be joined together and, conversely, dissimilar regions will remain separated, thus creating regions with distinct image statistics. The region update step consists of two separate optimizations, a region-statistic optimization through performing a region union operation, and a subsequent optimization of the pixel cluster through cluster merging. Conceptually, measuring the statistical dissimilarity between superpixel regions is a form of texture discrimination and edge feature extraction. In [34], a model incorporating pixel cluster covariance was used to create a line and edge feature extractor for generic images. This concept was incorporated in the work of [32], where a line/edge detector was formulated based only on the gradient of the pixel region covariance (change between covariance in neighbouring pixel regions). Expanding on the use of covariance for edge extraction, ref. [35] showed that a statistical distance measurement, the Bhattacharyya space, allowed for the discrimination of various textures within an image. The Bhattacharyya space was applied to large-scale region of interest (ROI) finding and feature segmentation in [36]. Refs. [37; 38] demonstrate that comparable ROI and feature segmentation can be performed on ultrasound images using speckle and image statistics. _Region Union:_  
The first operation, the region union, will incorporate the adjacency information stored in the graph \(\mathcal{G}\) to evaluate the KS distance between neighbouring regions and to choose which regions a union operation should be performed on. As each region consists of a pixel cluster (or pixel clusters after the first iteration of the algorithm), the values in the region list \(\mathbf{R}\) must be updated to incorporate the changes to the pixel clusters during their update step. Values of the centroid of each region, given in (29), and the empirical CDF of each region, given in (30), need to be calculated. Using these new region list values, the distance metric is computed for each edge \(E_{v}=(k_{v1},k_{v2})\) in the graph \((E_{v}\in\mathcal{E})\). The edges describe the interconnection between the region elements, a region's neighbours, and the score measures how statistically similar neighbouring regions are. The score is stored in an array,  
\[\mathbf{S}=[s_{0},s_{1},...,s_{\ell}]^{\top}, \tag{38}\]which contains the same number of entries as the edge structure, \(\ell=v_{max}\) where \(v_{max}\) is the largest index of edges \(E_{v}\in\mathcal{E}\). The distance score is then calculated along each edge via the function  
\[ \begin{split} D_{KS}(k_{i},k_{j})&=\sup_{x}\big{|} \hat{F}_{i}(x)-\hat{F}_{j}(x)\big{|}\\ s_{v}&=D_{KS}(k_{v1},k_{v2})\end{split}  \tag{39}\]  
which returns the largest mismatch between the values of the empirical CDFs, \(\hat{F}_{k}(x)\) (stored in \(\hat{\mathbf{F}}_{\mathbf{k}}\)), across all of the input pixel intensities, \(x=\{0,1,...,255\}\), seen in the input image \(\mathcal{I}(i)\).