Delineation and noise removal play a significant role in clinical quantification of PET images. Conventionally, these two tasks are considered independent, however, denoising can improve the performance of boundary delineation by enhancing SNR while preserving the structural continuity of local regions. On the other hand, we postulate that segmentation can help denoising process by constraining the smoothing criteria locally. Herein, we present a novel iterative approach for simultaneous PET image denoising and segmentation. The proposed algorithm uses generalized Anscombe transformation priori to non-local means based noise removal scheme and affinity propagation based delineation. For non-local means denoising, we propose a new regional means approach where we automatically and efficiently extract the appropriate subset of the image voxels by incorporating the class information from affinity propagation based segmentation. PET images after denoising are further utilized for refinement of the segmentation in an iterative manner. Qualitative and quantitative results demonstrate that the proposed framework successfully removes the noise from PET images while preserving the structures, and improves the segmentation accuracy.