Fully connected pairwise Conditional Random Fields (Full-CRF) with Gaussianedge weights can achieve superior results compared to sparsely connected CRFs.However, traditional methods for Full-CRFs are too expensive. Previous workdevelops efficient approximate optimization based on mean field inference,which is a local optimization method and can be far from the optimum. Wepropose efficient and effective optimization based on graph cuts for Full-CRFswith quantized edge weights. To quantize edge weights, we partition the imageinto superpixels and assume that the weight of an edge between any two pixelsdepends only on the superpixels these pixels belong to. Our quantized edge CRFis an approximation to the Gaussian edge CRF, and gets closer to it assuperpixel size decreases. Being an approximation, our model offers anintuition about the regularization properties of the Guassian edge Full-CRF.For efficient inference, we first consider the two-label case and develop anapproximate method based on transforming the original problem into a smallerdomain. Then we handle multi-label CRF by showing how to implement expansionmoves. In both binary and multi-label cases, our solutions have significantlylower energy compared to that of mean field inference. We also show theeffectiveness of our approach on semantic segmentation task.