Dithering

Recently, I started researching on dithering algorithms and here are my findings. I was pretty sure that I might not find any new blog posts on this topic as it is a very old technology. But to my suprise I came across this excellent blog post which was published this year (2021.01.04). Not only is it extremely well written, it thoroughly covers everything about about dithering. An obvious question is then what is the point of having another blog post about the same topic. I am of the opinion that when we explain a concept to someone or to write about it or may be implement it (if that can be done) it helps one to understand the concept better. As there is already very nice explanation in the earlier mentioned post and because I possibly couldn’t have written any better, I will only attempt to implement one of the popular dithering algorithms in Python. There are a few more resources, that I found really helpful and you can find it at the bottom of this post.

The algorithm that I implemented is called the Floyd Steinberg algorithm. It uses the technique of error diffusion, which in simple terms means that the quantization error is distributed among the neighboring pixels. Thus output pixel value not only depends on the corresponding pixel value in the input, but also on the neighboring pixels. There is an excellent animation of error diffusion in this blog. One thing to be noted here is that it is what one would call an inherently sequential algorithm (as opposed to an embarassingly parallel algorithm). So what that means is that if dithering is part of an image processing pipeline, it might be a bottleneck to execute the pipeline on GPU. Show below is an implementation of the alogithm in Python and is self explanatory. Also shown are a grayscale image and the corresponding dithered image.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
def dither(img):
"""
@img: Input image in the form of numpy array
"""
r, c = img.shape
for row_idx in np.arange(r):
for col_idx in np.arange(c):
old_pixel = img[row_idx][col_idx]
new_pixel = 255 if old_pixel > 127 else 0
err = old_pixel - new_pixel
img[row_idx][col_idx] = new_pixel
if col_idx + 1 < c:
img[row_idx][col_idx + 1] += err * 7 // 16
if row_idx + 1 < r:
img[row_idx + 1][col_idx] += err * 5 // 16
img[row_idx + 1][col_idx + 1] += err * 1 // 16
if col_idx - 1 >= 0:
img[row_idx + 1][col_idx - 1] += err * 3 // 16

return img

Input Image

source(https://homepages.cae.wisc.edu/~ece533/images/)
png

Output Image

png