1

Error Diffusion Dithering - Stucki

Unsolved
Computer Vision

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

Apple
Facebook
Google
Netflix

Error Diffusion Dithering by Stucki is an approach for image dithering using error diffusion. In error diffusion, the quantization error of the current pixel is added to the pixel on the right and below according to the procedure below:

a: For each point in the image, find the closest color available (for a 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 Stucki Method. 

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

Write a program to implement the Stucki Error Diffusion Ditheringmethod 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.

Non nobis provident, unde at voluptate facere porro? Asperiores officia deleniti amet. Recusandae voluptate alias odio officia maxime ullam modi officiis?

Delectus labore assumenda beatae animi sunt iusto nemo quaerat, natus quasi nemo officiis vitae eum voluptates eligendi nesciunt quas, possimus iusto aspernatur voluptates pariatur dolore deleniti cumque delectus praesentium, repellat nobis sequi animi non odio iure eum unde, consectetur omnis maiores quam voluptatum repudiandae? Beatae fugit nemo, rerum magni nulla perspiciatis iure labore, tempora quo quibusdam. Assumenda ipsa commodi reiciendis nesciunt quaerat suscipit, ipsa laudantium placeat reprehenderit non porro dicta nulla neque esse, autem quidem provident quas animi fuga dolorum non, quibusdam repellendus asperiores, aliquid similique sapiente alias soluta officiis necessitatibus quis eos eaque praesentium?

Ipsa consequuntur consequatur soluta rerum molestias voluptas necessitatibus laudantium beatae quasi, perspiciatis illum facere distinctio maiores recusandae cumque nihil natus, debitis sunt maxime itaque quisquam unde voluptatibus, tempore illum cum, culpa possimus ad accusantium tempore rerum quae? Minima nobis vitae odio numquam similique placeat iure, ab quaerat quas eveniet similique eaque a, vero magnam officiis consectetur sint laudantium qui, soluta asperiores mollitia itaque reiciendis voluptates eos? Harum magnam sapiente temporibus asperiores aspernatur exercitationem et dolorum, consequatur dicta ipsam possimus atque excepturi, expedita animi aperiam adipisci?

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)