In digital image processing, image segmentation is an essential step in which animage is partitioned into groups of pixels. k-means clustering algorithm, which isoften considered as fast and efficient, is one of the most widely used clusteringalgorithms to segment an image. However, as the problem size gets larger, the kmeans starts to spend a significant amount of time to process. At this point,parallelization techniques should be applied to reduce the required time. Designingan efficient parallel and distributed model is not a trivial job since it shouldcorrespond to the parallel computer architecture and take communication and loadbalancing among processors into account. In this study, we propose a parallel anddistributed k-means clustering algorithm with naïve sharding centroid initializationfor image segmentation. The proposed algorithm adopts the Message PassingInterface (MPI) standard to take advantage of the computational power ofdistributed computing nodes in a High-Performance Computing Cluster. Wedemonstrate the parallel scalability of the proposed algorithm using up to 128 coresand it achieves 104.23 times faster clustering time.