The key step of a computer-assisted screening system that aims early diagnosis of cervical cancer is the accurate segmentation of cells. In this paper, we propose a two-phase approach to cell segmentation in Pap smear test images with the challenges of inconsistent staining, poor contrast, and overlapping cells. The first phase consists of segmenting an image by a non-parametric hierarchical segmentation algorithm that uses spectral and shape information as well as the gradient information. The second phase aims to obtain nucleus regions and cytoplasm areas by classifying the segments resulting from the first phase based on their spectral and shape features. Experiments using two data sets show that our method performs well for images containing both a single cell and many overlapping cells. © 2010 IEEE.