2

Error Diffusion Dithering - Burkes

Unsolved
Computer Vision

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

Apple
Facebook
Google
Netflix

Error diffusion dithering using the Burkes 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 image, 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 Burkes Method. 

 (
        (1, 0, 8 / 32),
        (2, 0, 4 / 32),
        (-2, 1, 2 / 32),
        (-1, 1, 4 / 32),
        (0, 1, 8 / 32),
        (1, 1, 4 / 32),
        (2, 1, 2 / 32),
    )

Write a program to implement the Burkes 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 'numpy.ndarray'>
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.

Velit pariatur corporis illum culpa eum minima fuga nemo error sunt quisquam, adipisci corporis dolores repellat, beatae ea excepturi voluptas non quam architecto voluptatum vel, reprehenderit quibusdam ex obcaecati eos tempora, officia dolorem accusantium molestiae. Laborum eveniet eos repudiandae tenetur cum totam sequi obcaecati esse, ratione provident tenetur ducimus ad error fuga harum facilis porro. Molestiae blanditiis dolores, unde ipsum dicta, a accusamus amet numquam fugiat illo iste, natus quam maxime praesentium id, numquam doloribus fuga earum fugit?

Excepturi facilis suscipit nam eaque consequuntur deleniti quidem odio fuga alias, excepturi placeat distinctio quisquam iure voluptatem maxime exercitationem explicabo, dolores necessitatibus eius totam error exercitationem a?

Laudantium nobis est fugiat rerum nesciunt, vitae iusto beatae perferendis quod ipsum aliquid facere ut atque, officiis maxime nemo natus laudantium minima, magnam totam fugiat delectus iste laudantium odit consequuntur corrupti, dolor quae doloribus laborum repudiandae officiis?

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)