Image segmentation algorithm based on ESFCM (Edge-based Semi-Fuzzy C-means Clustering Method) is a hotspot in the domain of image processing. But the original image segmentation algorithm based on ESFCM cannot meet the requirements in real time image detention, due to its heavy computational effort to work out the spatial distance between an edge pixel with every clustering center. In order to reduce the computation complexity, an improved algorithm is put forward based on a new spatial distance, in which fuzzy distance is used to replace the physical distance. The experiment results show that not only the calculation amount but also the parameters convergence rate of the improved ESFCM have been drastically decreased after the redefinition of spatial distance. In other words, the computation complexity of the improved algorithm has been reduced much more significantly than that of the original one