A complete and detailed cerebrovascular image segmented from time-of-flight magnetic resonance angiography (TOF-MRA) data is essential for the diagnosis and therapy of the cerebrovascular diseases. In recent years, three-dimensional cerebrovascular segmentation algorithms based on statistical models have been widely used, but the existed methods always perform poorly on stenotic vessels and are not robust enough. In this paper, we propose a parallel cerebrovascular segmentation algorithm based on focused multi-Gaussians model and heterogeneous Markov random field. Specifically, we present a focused multi-Gaussians (FMG) model with local fitting region to model the vascular tissue more accurately and introduce the chaotic oscillation particle swarm optimization (CO-PSO) algorithm to improve the global optimization capability in the parameter estimation. Furthermore, we design a heterogeneous Markov Random Field (MRF) in the three-dimensional neighborhood system to incorporate precise local character of image. Finally, the algorithm has been performed parallel optimization based on GPUs and obtain about 60 times speedup compared to serial execution. The experiments show that the proposed algorithm can produce more detailed segmentation result in shorter time and performs well on the stenotic vessels robustly.