N-Candidate methods for location invariant dithering of color images

We introduce a new class of dithering methods called N-candidate methods. The main idea is that the output color is randomly chosen among several candidate colors so that the estimated color average would be preserved. The dithering process is pixelwise without any interaction with the neighboring pixels. The N-candidate methods are thus location invariant, which has two benefits: (1) the algorithm can be fully parallelized; and (2) the image can be partially processed without effecting the pixels outside the processed part. The proposed approach allows more efficient dithering than error diffusion but at the cost of a slightly lower image quality.