4
\$\begingroup\$

In ordered dithering Bayer matrix is used.

How is that matrix generated? What algorithm can be used to generate matrix of arbitrary size?

\$\endgroup\$
  • 1
    \$\begingroup\$ Have you actually read the wikipedia page you linked? Let me try to summarize it in an answer \$\endgroup\$ – Bálint Sep 29 '16 at 11:56
1
\$\begingroup\$

(As @Bálint seems not to have gotten around to it… :)

To quote the article as it (likely) was when you initially asked:

Arbitrary size threshold maps can be devised with a simple rule: First fill each slot with a successive integer starting from 1. Then reorder them such that the average distance between two successive numbers in the map is as large as possible, ensuring that the table "wraps" around at edges.

A more detailed explanation has since been added to the article:

For threshold maps whose dimensions are a power of two, the map can be generated recursively via:

The recursive expression can be calculated explicitly using only bit arithmetic:
M(i, j) = bit_reverse(bit_interleave(bitwise_xor(x, y), x)) / n ^ 2

That last bit can be implemented with little trouble in e.g. Python:

def bit_reverse(x, n):
    return int(bin(x)[2:].zfill(n)[::-1], 2)

def bit_interleave(x, y, n):
    x = bin(x)[2:].zfill(n)
    y = bin(y)[2:].zfill(n)
    return int(''.join(''.join(i) for i in zip(x, y)), 2)

def bayer_entry(x, y, n):
    return bit_reverse(bit_interleave(x ^ y, y, n), 2*n)

def bayer_matrix(n):
    r = range(2**n)
    return [[bayer_entry(x, y, n) for x in r] for y in r]

print(bayer_matrix(2))

This doesn't produce quite the same matrix as listed in the Wikipedia article, but as the author of the original source writes, "it is good enough in practice".

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.