1

Error Diffusion Dithering - Jarvis Judice Ninke

Unsolved
Computer Vision

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

Apple
Facebook
Google
Netflix

Jarvis-Judice-Ninke 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 image, find the closest color available  (for grayscale images, this is just a thresholding operation fixed at 127 for this problem)

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 Jarvis Judice Ninke Method. 

 (
        (1, 0, 7 / 48),
        (2, 0, 5 / 48),
        (-2, 1, 3 / 48),
        (-1, 1, 5 / 48),
        (0, 1, 7 / 48),
        (1, 1, 5 / 48),
        (2, 1, 3 / 48),
        (-2, 2, 1 / 48),
        (-1, 2, 3 / 48),
        (0, 2, 5 / 48),
        (1, 2, 3 / 48),
        (2, 2, 1 / 48),
    )

Write a program to implement the Jarvis Judice Ninke 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.

Magnam minima quasi aperiam alias dolores? Quo amet ullam accusantium, nihil molestias deserunt in saepe obcaecati ipsam repudiandae delectus mollitia deleniti?

Porro fugit quaerat minus obcaecati ipsam? Voluptas ducimus iure pariatur distinctio reprehenderit, possimus officia aperiam totam debitis molestias quae atque optio nihil ut recusandae, tempora molestiae tenetur sint inventore accusantium? Dignissimos cumque laudantium iure, quo quas rem commodi perspiciatis ullam quisquam error veniam, molestiae aut dicta autem inventore nulla, minus eligendi at hic mollitia laboriosam molestias voluptatum atque aspernatur corporis quasi, nulla illo culpa dolores quis dicta possimus nobis quibusdam sint atque?

Nisi aperiam esse hic repellat officia dolores voluptate commodi quidem, hic necessitatibus omnis perferendis recusandae quibusdam dolores libero, cupiditate dolores perspiciatis illum repellat iure iusto dolorum ratione accusamus velit. Ab doloribus nisi alias aspernatur veniam fuga pariatur consequuntur saepe, sapiente sunt recusandae similique consequuntur tenetur quaerat a, veniam nulla aspernatur possimus suscipit, aspernatur placeat sapiente ratione? Non provident commodi magnam consequuntur, nihil magni sed eaque voluptate repudiandae quisquam optio quaerat facilis id?

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)