# Autonomous Prostate Segmentation in 2D B-Mode Ultrasound Images
## 5 Graph-Cut Segmentation  
The last step in the prostate segmentation algorithm, as shown in Figure 1, combines the output of the superpixel processing with the statistical prostate shape model. The prostate shape model, described in Section 3.2, can be used to find the likelihood that a particular pixel will be on the edge of the prostate. The superpixel image processing algorithm returns an image which has been divided into a large number of superpixel regions, with each superpixel region being a large area of pixels which have particular pixel intensity distributions. The superpixel algorithm also returns an associated graph describing the adjacency between the superpixel regions. A graph-cut algorithm will be used to merge the contour position information with statistical properties of the superpixel regions in order to segment the prostate. Given an input set of TRUS ultrasound images slices, \({}^{U}\mathbf{I}\), containing \(nImg\) images, the first step in segmentation is to preprocess each image, as covered in A, to obtain the ROI for segmentation. After preprocessing, each of the ROI images in the set, \({}^{R}\mathbf{I}\), will be input into the superpixel processing algorithm. Each image \(i\) in the set will then have a corresponding superpixel region image \({}^{R}\mathcal{L}_{Ri}\) and graphs describing the neighbours of each region \(\mathcal{G}_{i}=\{\mathcal{V}_{i},\mathcal{E}_{i}\}\). For final segmentation, the superpixel region image is warped back into the ultrasound image frame \(\{U\}\) by inverting the transform given in (A1). To do this, the location of each pixel inside of the ROI in \({}^{U}\mathcal{I}({}^{U}px,\;^{U}py)_{i}\) will be used to find the corresponding pixel in \({}^{R}\mathcal{I}({}^{R}px,\;^{R}py)_{i}\), and the region label for that pixel, at \({}^{R}\mathcal{L}_{Ri}({}^{R}px,\;^{R}py)\), will be transferred to a new region image \({}^{U}\mathcal{L}_{Ri}({}^{U}px,\;^{U}py)\), and any pixels outside of the ROI are given a label of 0. For a region \(R_{k}\), the pixels inside of that region are defined to be \(\{{}^{U}\mathcal{L}_{Ri}({}^{U}px,\;^{U}py)=k:\forall({}^{R}px,\;^{R}py)\in R _{k}\}\); the result of this warping procedure is shown in Figure 9. Warping the region images back in the \(\{U\}\) frame is required in order to use the prostate shape model, as it was derived based on the prostate contour segmented by clinicians in standard TRUS images. The probabilistic prostate shape model is generated offline before segmentation and so the prostate can be segmented in all of the input images. For segmentation, an energy-based cost function [40] will be minimized to perform the final segmentation (contouring) of the prostate in the TRUS images. The segmentation and contouring will be performed by labelling pixel regions \(R_{k}\) as being inside of the prostate, \(\mathbf{L}_{In}\), or outside of the prostate, \(\mathbf{L}_{Out}\). For a single image \(i\), the cost function is given by  
\[E(\mathbf{L})_{i}=\lambda_{D}\sum_{k\in\mathcal{V}_{i}}\psi_{k}(\mathbf{L}_{k })+\lambda_{S}\sum_{k,m\in\mathcal{E}_{i}}\psi_{km}(\mathbf{L}_{k},\mathbf{L} _{m}) \tag{47}\]where \(\mathbf{L}\) is a labelling for the images. The cost function contains a data term  
\[\sum_{k\in\mathcal{V}_{i}}\psi_{k}(\mathbf{L}_{k}) \tag{48}\]  
for each region \(R_{k}\) in the image corresponding to the vertices in \(\mathcal{V}_{i}\), and a smoothness term  
\[\sum_{k,m\in\mathcal{E}_{i}}\psi_{km}(\mathbf{L}_{k},\mathbf{L}_{m})\,, \tag{49}\]  
which incorporates a score based on the neighbours connected by an edge \(\mathcal{E}_{i}\), of the region \(R_{k}\). The values \(\lambda_{D}\) and \(\lambda_{S}\) weight the data terms and smoothing terms, respectively, and this cost function will be minimized through the graph-cut procedure. The data term will incorporate the contour location probabilities from the prostate shape model and a prostate appearance term into the graph-cut score.