## 1 Introduction  
Lung cancer is considered the leading cause of cancer death throughout the world. More people die because of lung cancer than any other type of cancer such as breast, colon, and prostate cancers. Optimistically, there is significant evidence indicating that the early detection of lung cancer will decrease the mortality rate, by using asymptomatic screening methods, followed by effective treatment. Lung cancer symptoms consist of shortness of breath, wheezing, chest pain that does not get better, coughing accompanied with blood, difficulty in swallowing, and loss of weight and appetite [1]. The most recent estimate statistics according to the American Cancer Society indicate that 226,160 new cases will be diagnosed (116,470 in men and 109,690 in women) in US, and there will be estimated 160,340 mortalities from lung cancer (87,750 in men and 72,590 among women) [2]. Furthermore, based on statistics from the World Health Organization (WHO), deaths caused by cancer will reach about 12 million people in 2030. Lung cancer is projected to continue killing more people than any other type, unless the efforts to control the main cause of cancer death are largely intensified. There are many techniques to diagnose lung cancer, such as Chest Radiograph (\(x\)-ray), Computed Tomography (CT) [3], Magnetic Resonance Imaging (MRI scans) and Sputum Cytology [4]. However, most of these techniques are expensive and time consuming. In most cases, these techniques detect lung cancer in its advanced stages, where the patient's chance of survival is very low. Thus, there is a substantial demand for a new technology to diagnose lung cancer in its early stages. Image processing techniques provide a superior quality tool for improving the manual analysis. Among all the previous techniques, only the manual sputum cytological examination has been utilized for the diagnosis of early lung cancer detection since 1930s [5]. The goal of this research is to design a Computer Aided Diagnosis (CAD) system for early detection of malignant lung cancer cells using digital images of stained sputum smears. Such an automated system would allow objective and unbiased assessment, as compared to human evaluation which might be corrupted by errors originating from inter-and intra-observer variability that characterizes human observation. Eventually, this system will be useful for handling large sputum image databases and relieving the pathologist from tedious and routine task. In this paper, we focus on the extraction and segmentation of sputum cells from background regions. The sputum images are stained according to the Papanicolaou standard staining method [6] provided by the Tokyo Center for lung cancer in Japan. These images are stained with two types. Type1, blue dye images resulting in the dark-blue nucleus of all the cells present in the image and clear-blue cytoplasm. Type 2, red dye images resulting in the dark-blue nucleus of the small debris cells with their corresponding small clear-blue cytoplasm regions, and red sputum cell with dark-red nucleus and clear-red cytoplasm. Some of the sputum nuclei cells overlap due to the dispersion of the cytoplasm in the staining process. The automatic assessment of the sputum cell state, using the sputum image, is based on the analysis of both the chromatic and geometric attribute of its nucleus and cytoplasm, therefore this process involves the extraction of their related regions in the image. This problem is viewed as a segmentation problem whereby we want to partition the image into sputum cell regions including the nuclei and cytoplasm, plus the background that includes all the rest. Nevertheless, the sputum images arecharacterized by noisy and cluttered background patterns that cause the segmentation and automatic detection of the cancerous cells highly problematic. There have already been attempts to solve this problem using heuristic rules [7]. In this paper, we propose two methods for addressing this problem the first employed a threshold-based technique.