Medical image segmentation via min s-t cuts with sides constraints

Graph cut algorithms (i.e., min s-t cuts) [3][10][15] are useful in many computer vision applications. In this paper we develop a formulation that allows the addition of side constraints to the min s-t cuts algorithm in order to improve its performance. We apply this formulation to foreground/background segmentation and provide empirical evidence to support its usefulness. From our experiments on medical image segmentation, the graph cut with constraints achieve significantly better performance than that without any constraint. Although the constrained min s-t cut problem is generally NP-hard, our approximation algorithm that uses linear programming relaxation and a simple rounding technique as a heuristic produces good results in a few seconds with our unoptimized code.