# Graph-Cuts with CA

A recent noteworthy development in image segmentation is the graph- cuts approach [160-164], in which the global minimum for a sub-modular function of a binary label problem is guaranteed. This section introduces techniques that incorporate a shape prior into a graph-cuts approach in order to achieve accurate segmentation. So far, general shape constraints, such an ellipse and a star shape, were combined with graph-cuts [165, 166]. In addition, the paper [167] presented a new boundary term that can take into account more general shape constraints or a compact shape constraint in a graph-cuts segmentation. Although the above priors are general and can be used in segmentation of a variety of objects, it might not be applicable to more complicated shape objects. To give a specific shape constraint on graph-cuts, a user-defined rigid template was incorporated into a graph-cuts-based segmentation [168]. To deal with statistical variations in the shape of an organ, the papers [169, 170] derived a shape prior from an SSM.

A limitation of the above approaches is that a single shape might not account for a shape in a given test image. A shape-based energy computed by the Parzen window method was presented in [153], which is a population statistic-based method, but the combinatorial problem of multiple shape information remains unsolved. The paper [171] extended the algorithm of [169] to multi-shape graph-cuts that can take into account multiplicity of shapes prior in the segmentation framework by using fusion move with the quadratic pseudo-Boolean optimization (QPBO) algorithm. In the remainder of this section, a multi-shape graph-cuts algorithm [163] is presented. A new pairwise energy, S_{pq}, for multiple shape priors was proposed and linearly combined with the conventional graph-cuts energy:

where * 9_{Ap}* is the angle between a vector connecting voxels

*and*

**p***and a gradient vector of a signed distance*

**q***from the boundary of a shape prior A*

**ф**_{Ар}_{p}. The method selects five shapes from an eigenshape space of an SSM which are similar to a region by MAP-based segmentation. The selected shapes are forwarded to multishape graph-cuts to perform segmentation with multiple shape priors. Unlike a conventional single-shape graph-cuts, multi-shape graph- cuts use multiple labels, each of which corresponds to a shape prior in graph-cuts-based fine segmentation. In addition, negative labels are used for background to differentiate between background labels and object labels. The fusion move with the QPBO algorithm finds a combinatorial optimal solution of labels or shapes.

Figure 2.26 shows lung segmentation results from a CT volume and shape priors. Although a single shape graph-cuts with shape 1 of part (e) led to inaccurate lung segmentation (red arrow in part (c)), the remaining shape priors of parts (f) to (i) corrected the segmentation as presented in part (d). Details of the algorithm as well as the experimental results using 97 CT volumes can be found in [171].

Fig. 2.26 **Influence of shape priors on segmentation results. (a) original CT, (b) true boundary, (c) segmentation result by a single- shape graph-cuts with single-shape prior of part (e), and (d) segmentation result by the multi-shape graph-cuts with five shape priors of figures (e) to (i)**