- Superpixel segmentation is a key step in many image processing and vision tasks. Our recently-proposed connectivity-constrained probabilistic model  yields high-quality super- pixels. Seemingly, however, connectivity constraints preclude parallelized inference. As such, the implementation from  is serial. The contributions of this work are as follows. First, we demonstrate that effective parallelization is possible via a fast GPU implementation that scales gracefully with both the number of pixels and number of superpixels. Second, we show that the superpixels are improved by replacing the fixed and restricted spatial covariances from  with a flexible Bayesian prior. Quantitative evaluation on public benchmarks shows the proposed method outperforms the state-of-the-art. We make our implementation publicly available.