We propose a super-pixel segmentation algorithm based on normalized Euclidean distance for handling the uncertainty and complexity in medical image. Benefited from the statistic characteristics, compactness within super-pixels is described by normalized Euclidean distance. Our algorithm banishes the balance factor of the Simple Linear Iterative Clustering framework. In this way, our algorithm properly responses to the lesion tissues, such as tiny lung nodules, which have a little difference in luminance with their neighbors. The effectiveness of proposed algorithm is verified in The Cancer Imaging Archive (TCIA) database. Compared with Simple Linear Iterative Clustering (SLIC) and Linear Spectral Clustering (LSC), the experiment results show that, the proposed algorithm achieves competitive performance over super-pixel segmentation in the state of art. © Springer International Publishing AG 2017.