Talk:Ordered dithering

The current version of the matrices is incorrect.

If you look at the 4x4 matrix here https://wikimedia.org/api/rest_v1/media/math/render/svg/3c62838dbbd378c058444a60b9c803b9bb4ee09c you will see that it it results in thresholds at 0/16, 1/16, etc up to 15/16. A threshold makes a decision if something is in a range below it, or greater-than or equal to it. The thing is there's no way for anything to be below 0, so the threshold 0/16 is useless. The problem also exists for the other matricies shown in this article. Also, regarding the 4x4 matrix, there are only 16 ranges of values using this incorrect matrix, while the picture at https://upload.wikimedia.org/wikipedia/commons/e/e5/Ordered_4x4_Bayer_matrix_dithering.png clearly indicates that the 4x4 threshold matrix should produce 17 ranges of values. This is how I know that the matrix used here is incorrect. Fortunately, an earlier version of the ordered dithering article has the correct matricies. The last version of this article to have the correct matricies is https://en.wikipedia.org/w/index.php?title=Ordered_dithering&oldid=665270162

As you can see. The correct 4x4 matrix has thresholds at 1/17, 2/17, etc up to 16/17. I recommend that the original matricies be put back in the article, as these were correct.

Benhut1 (talk) 21:02, 6 November 2020 (UTC)[reply]

I think it's equivalent whether you use < on the old matrices or <= on the new ones. Vegard (talk) 22:04, 20 December 2020 (UTC)[reply]

No, I don't think it has to do with < vs <=. A 2x2 grid provides 5 distinct shading patterns: All white, quarter white/ 3-quarter black, half white/ half black, and all black. Hence, the divisor on the matrix is 5. Similarly, a 4x4 grid creates 17 shadings. — Preceding unsigned comment added by 147.219.138.129 (talk) 23:23, 30 January 2021 (UTC)[reply]

After having tried to implement this I too believe it to be wrong. The next section says "Additionally, normalizing the values to average out their sum to 0" but shows a matrix where the sum isn't 0. Using this formulan instead produces a matrix that sums to 0

Mpre(i,j) = (Mint(i,j)+1) / (n^2+1) - 0.5

Testing it also produces the correct pattern for a gradient.

81.0.172.250 (talk) 13:49, 11 May 2022 (UTC)[reply]

Third matrix (8x8) is transposed

The algorithm given for computing the matrix recursively gives the transpose of the matrix given in the article. I used the following Python code:

M_prev = [0]

for i in range(3):
    n = 1 << i
    nn = 2 * n

    M = [0 for j in range(nn * nn)]

    for y in range(n):
        for x in range(n):
            M[nn * (y + 0) + (x + 0)] = 4 * M_prev[n * y + x] + 0
            M[nn * (y + 0) + (x + n)] = 4 * M_prev[n * y + x] + 2
            M[nn * (y + n) + (x + 0)] = 4 * M_prev[n * y + x] + 3
            M[nn * (y + n) + (x + n)] = 4 * M_prev[n * y + x] + 1

    print M
    M_prev = M

and this prints (with additional line breaks inserted):

[0, 2, 3, 1]

[0, 8, 2, 10,
12, 4, 14, 6,
3, 11, 1, 9,
15, 7, 13, 5]

[0, 32, 8, 40, 2, 34, 10, 42,
48, 16, 56, 24, 50, 18, 58, 26,
12, 44, 4, 36, 14, 46, 6, 38,
60, 28, 52, 20, 62, 30, 54, 22,
3, 35, 11, 43, 1, 33, 9, 41,
51, 19, 59, 27, 49, 17, 57, 25,
15, 47, 7, 39, 13, 45, 5, 37,
63, 31, 55, 23, 61, 29, 53, 21]

which is clearly transposed with respect to the matrix currently in the article.

Please double check and edit the article if this seems correct. The code can obviously also be used, although maybe the description that is already there is enough.

Vegard (talk) 22:12, 20 December 2020 (UTC)[reply]

You're correct that the recursive method yields the transpose of the matrix displayed. However, as the text says, the matrix can be rotated or reflected without changing the effectiveness, and the transpose is simply a 90-degree rotation followed by a horizontal reflection (or simply, a reflection in the diagonal). So either matrix works fine. If you want to edit the matrix to transpose it, feel free. -- Elphion (talk) 23:15, 20 December 2020 (UTC)[reply]

I have edited the matrix so it is transposed and matches the others. I was going mad trying to figure out why my code wouldn't work until I saw this discussion. Makeworldpedia (talk) 00:30, 13 January 2021 (UTC)[reply]

Sources

What is the source for the idea of subtracting 0.5? And what is the source for calculating the r value? I can't find this anywhere else on the Internet.

Makeworldpedia (talk) 01:40, 13 January 2021 (UTC)[reply]

Ok, I can confirm that doing

Mpre(i,j) = (Mint(i,j)+1) / n^2 - 0.5

and using an r value of 255 when modifying the pixel, is equivalent to thresholding the matrix without the +1 and -0.5. This was tested with a grayscale image being dithered to a black and white palette, using linear RGB for all mathematical operations as one should. So basically, while there is not a source for the +1 and -0.5, I can confirm that it is correct.

However the part about calculating the r value appears to be incorrect, as it would have me use a value of 765 in this case (I calculated that based on a value of n=0.333 because there are only two palette colors), but it was only a value of 255 that created the same image as thresholding. Additionally, some sources like this one appear to suggest a general r value of 256/4. According to the article, this woulds suggest they using a palette of 4096 colors, which isn't true.

Makeworldpedia (talk) 17:02, 13 January 2021 (UTC)[reply]

After testing with different r values, for both grayscale and color images, I've discovered that an r value of 1 or whatever the equivalent maximum color value is (often 255) works best. I will post more details about this once I put some code up.

Makeworldpedia (talk) 18:48, 20 January 2021 (UTC)[reply]

Errors abound

Never mind specific errors: the entire "mathematical development" is for naught. It seems as if the author felt obligated to stuff the article full of spiffy mathematical notation without sensing the need to integrate it with the text. It's useless: "here, look at these matrices." — Preceding unsigned comment added by 2601:589:4B00:C200:0:0:0:1BF6 (talk) 22:50, 14 June 2021 (UTC)[reply]

The 4x4 example gradient is wrong.

If you look closely at the image, you'll see that the last 4x4 matrix is incorrectly displaced as follows.

[0, 0, 0, 0]
[0, 0, 1, 0]
[0, 0, 0, 0]
[0, 0, 0, 0]

It should be displayed like this instead.

[0, 0, 0, 0]
[0, 0, 0, 0]
[0, 0, 0, 0]
[1, 0, 0, 0] 147.206.1.25 (talk) 04:04, 1 October 2023 (UTC)[reply]