Identification of Lung Nodule Using Hierarchical Graph-Based Clustering and Multi-Level Thresholding

Date of Award


Publication Type


Degree Name



Computer Science

First Advisor


Second Advisor


Third Advisor



Clustering, Detection, Lung cancer, Nodules, Segmentation, Superpixels



Creative Commons License

Creative Commons Attribution 4.0 International License
This work is licensed under a Creative Commons Attribution 4.0 International License.


Lung cancer is the second most commonly diagnosed cancer and the leading cause of cancer deaths worldwide. Compared to standard chest radiography, clinical trials have demonstrated that low-dose CT significantly reduces mortality from lung cancer by 20%. However, segmenting pulmonary nodules remains challenging due to intrinsic noise, low contrast, variable sizes and different shapes of the nodules. Radiologists manually drawing the nodule boundary is a common approach for delineating nodules which is time-consuming, expensive and prone to intra (the difference in repeated measurements by the same observer) and inter (the difference in the measurements between observers) observer variability. Also, most lung nodule analysis techniques use supervised learning that requires manually labelled regions of interest. Therefore, an automatic unsupervised lung nodule detection algorithm is needed to assist radiologists in deciding the malignancy of nodules. This thesis proposes a method that uses a set of morphological operations and median filtering in the preprocessing stage, followed by a superpixel segmentation method called Linear Spectral Clustering (LSC). After the superpixel segmentation, an eight nearest-neighbour Region Adjacency Graph (RAG) is constructed, and hierarchical agglomerative clustering is applied on the RAG in which similar superpixels are iteratively merged to form more significant regions with similar pixels. Different objects in the CT scan images are clustered into unique classes. In the final step, a post-processing step of multilevel thresholding based on the colour and shape features is applied to these classes for nodule detection. The proposed method is evaluated on the Lung Image Database Consortium dataset. Comparative analysis shows that the proposed method outperforms the state-of-the-art superpixel methods for unsupervised lung nodule detection, with an average Dice Similarity Coefficient of 95.10 % and an average Intersection over Union (IoU) of 90.57 %.