1

Error Diffusion Dithering - Sierra3

Unsolved
Computer Vision

Difficulty: 6 | Problem written by mesakarghm
Problem reported in interviews at

Apple
Facebook
Google
Netflix

Error diffusion dithering using the Sierra3 approach is a process for image dithering using error diffusion. In error diffusion, the quantization error of current pixel is added to the pixel on the right and below according to the procedure below:

a: For each point in image, find the closest color available (for grayscale images, this is just a thresholding operation fixed at 127 for this problem set)

b: Calculate the difference between the value in the image and the color you have.

c: Now divide up these error values and distribute them over the neighboring pixels which you have not visited yet. 

d: When you get to these later pixels, just add the errors distributed from the earlier ones, clip the values to the allowed range if needed, then continue as above.

The set below shows the index of the neighboring pixels along with their diffusal coefficient according to the Sierra3 Method. 

(
        (1, 0, 5 / 32),
        (2, 0, 3 / 32),
        (-2, 1, 2 / 32),
        (-1, 1, 4 / 32),
        (0, 1, 5 / 32),
        (1, 1, 4 / 32),
        (2, 1, 2 / 32),
        (-1, 2, 2 / 32),
        (0, 2, 3 / 32),
        (1, 2, 2 / 32),
    )

Write a program to implement the Sierra3 dithering in a given 2D matrix (grayscale image). Use the diffusion filter given in the problem set for dividing up the error. 

Sample Input:
<class 'list'>
image: [[ 1 7 119 13 12] [ 11 21 61 81 91] [ 5 66 6 5 5] [ 5 66 166 145 155] [ 5 66 136 145 155]]

Expected Output:
<class 'numpy.ndarray'>
[[ 0 0 0 0 0] [ 0 0 0 0 0] [ 0 0 0 0 0] [ 0 0 255 255 255] [ 0 0 255 255 255]]

Lorem ipsum dolor sit amet, consectetur adipisicing elit, sed do eiusmod tempor incididunt ut labore et dolore magna aliqua. Ut enim ad minim veniam, quis nostrud exercitation ullamco laboris nisi ut aliquip ex ea commodo consequat. Duis aute irure dolor in reprehenderit in voluptate velit esse cillum dolore eu fugiat nulla pariatur. Excepteur sint occaecat cupidatat non proident, sunt in culpa qui officia deserunt mollit anim id est laborum.

Delectus fugit fuga aliquam id, placeat quas voluptas nobis atque minima excepturi, dolore consequuntur placeat eveniet cumque corporis nulla quas, dolor officia quo autem eligendi. Dolorem amet error, amet quis sapiente adipisci enim fugiat aperiam dolore ex architecto, asperiores laborum a ab saepe nobis ducimus quos officiis tempore culpa inventore, magnam fuga illo vitae in non quisquam nam, iste facilis voluptate adipisci distinctio dicta maxime a assumenda unde hic recusandae? Odit sed provident perferendis corporis tenetur minus consectetur, perferendis eveniet suscipit fugit sit cumque, tempore magni esse expedita illo possimus et dignissimos eos, veritatis placeat iusto provident laborum aperiam error quia maxime ullam optio? Ipsam eveniet aliquid iure dolore magni provident.

Id molestias excepturi voluptates aspernatur maiores doloribus, atque saepe facere architecto odit, veniam cum ea harum aspernatur culpa. Dolorem illo maiores consequatur vero voluptatibus, illum doloremque eum eos praesentium nesciunt odit quam dolor doloribus illo ex, eligendi vel quod eveniet accusantium velit eius provident excepturi obcaecati? Labore accusamus nisi laudantium delectus optio minima soluta voluptas?

Reprehenderit facilis voluptate est iusto ad dolores voluptatum repellendus, perferendis quod voluptatem modi fuga vero est commodi provident unde ab, explicabo ab libero corporis quibusdam neque dolorem sit corrupti illum, laborum dolorum repellendus fugiat, accusantium tempore quis harum est dolorem pariatur laudantium vitae cum? Illo facere dolore culpa quas possimus enim nihil, perferendis quo necessitatibus dolorem blanditiis rerum odio debitis ratione dicta quam expedita, voluptate quas maiores ipsa vel doloremque quidem officiis incidunt, minus et magni illo dignissimos nihil molestiae assumenda enim dolores, iste reiciendis consectetur aspernatur harum? Quaerat quisquam numquam assumenda?

This is a premium feature.
To access this and other such features, click on upgrade below.

Ready.

Input Test Case

Please enter only one test case at a time
numpy has been already imported as np (import numpy as np)