Volume constrained 2-phase segmentation method utilizing a linear system solver based on the best uniform polynomial approximation of x−1/2

Volume constrained image segmentation aims at improving the quality of image reconstruction via incorporating physical information for the underline object of interest into the mathematical modeling of the segmentation problem. In this paper, we develop a general framework for 3D 2-phase image segmentation, based on constrained ℓ2 minimization of a non-local regularizer, the Euler-Lagrange derivative of which is the discrete graph-Laplacian of a weighted graph, associated with the image voxels. It involves a convenient change of basis in the image domain, for which the optimization function is decomposed element-wise. Using univariate polynomial approximation techniques, we show that the transformation matrix does not need to be explicitly computed and its action is well approximated by a suitable matrix polynomial. The error is independent of the domain size, thus our approach is applicable to high resolution data. The model allows for adding arbitrary linear terms into the optimization function in order to increase the control on the output, in particular to add its scalar product with another, already known, segmentation vector. Such a “hybrid” process may significantly improve on the individual quality of each of the involved segmentations.