In this letter, we present a novel watershed-based method for segmentation of cervical and breast cell images. We formulate the segmentation of clustered nuclei as an optimization problem. A hypothesis concerning the nuclei, which involves a priori knowledge with respect to the shape of nuclei, is tested to solve the optimization problem. We first apply the distance transform to the clustered nuclei. A marker extraction scheme based on the H-minima transform is introduced to obtain the optimal segmentation result from the distance map. In order to estimate the optimal h-value, a size-invariant segmentation distortion evaluation function is defined based on the fitting residuals between the segmented region boundaries and fitted models. Ellipsoidal modeling of contours is introduced to adjust nuclei contours for more effective analysis. Experiments on a variety of real microscopic cell images show that the proposed method yields more accurate segmentation results than the state-of-the-art watershed-based methods.