In Indonesia, cancer is very burdensome financially for sufferers as well as for the country. Increasing the access to early detection of cancer can be a solution to prevent the situation from worsening. Regarding the problem of cancer lesion detection, a whole-body bone scan image is the primary modality of nuclear medicine for the detection of cancer lesions on a bone. Therefore, high segmentation accuracy of the whole-body bone scan image is a crucial step in building the shape model of some predefined regions in the bone scan image where metastasis was predicted to appear frequently. In this article, we proposed an automatic whole-body bone scan image segmentation based on constrained local model (CLM). We determine 111 landmark points on the bone scan image as the input for the model building step. The resulting shape and texture model are further used in the fitting step to estimate the landmark points of predefined regions. We use the CLM-based approach using regularized landmark mean-shift (RLMS) to lessen the effect of ambiguity, which was struggled by the CLM-based approach. From the experimental result, we successfully show that our proposed image segmentation system achieves higher performance than the general CLM-based approach.