Grouping algorithms based on histograms over measured image features have very successfully been applied to textured image segmentation [2, 11, 6]. However, the competing goals of statistical estimation significance demanding few quantization levels versus the necessary richness in representation often prevent a successful application for the color cue, since quantization may result in contouring. In this paper, we combine a novel halftoning technique called spatial quantization with distribution-based grouping algorithms to synthesize a powerful color image segmentation technique. The spatial quantization simultaneously determines color palette and halftoning by optimizing a joint cost function. It therefore allows for a highly adapted image representation with a smooth transition of color distributions for non-constant image surfaces.