Find coordinate in ordered-dithering matrix

Question

The Bayer index matrix for ordered dithering can be computed as follows:

import numpy as np
base = np.array([[0, 2],
 [3, 1]])
matrix = base.copy()
for _ in range(n_iterations):
 # current matrix upscaled + base matrix tiled * number of entries
 matrix = np.kron(matrix, np.ones_like(base)) + np.tile(base, matrix.shape) * matrix.size

Given an integer, how can I compute the coordinate in the matrix where that integer is? I'm asking for an efficient solution instead of computing and searching the entire matrix.

Answer 1

That matrix consists of consecutive integers ordered in a fractal criss-cross manner. In the following illustration modified from this article, the submatrix of each color consists of consecutive integers ordered in a criss-cross manner, and the submatrices themselves are ordered in the same criss-cross manner.

illustration of the matrix as described in the text

To compute the coordinate, you can compute in which submatrix the queried integer is. Then recursively compute the coordinate of the first entry of that submatrix. Then add to that coordinate depending on which index the queried integer has in that submatrix (for example, the largest value of the submatrix is located under the smallest one).

function bayerCoordinate(index, size) {
 if (size === 1) {
 return [0, 0];
 }
 
 const half = size / 2;
 const whichSubmatrix = Math.floor(index / 4);
 const indexInSubmatrix = index % 4;
 
 const [x, y] = bayerCoordinate(whichSubmatrix, half);
 
 switch (indexInSubmatrix) {
 case 0:
 return [x, y];
 case 1:
 return [x + half, y + half];
 case 2:
 return [x + half, y];
 case 3:
 return [x, y + half];
 default:
 throw new Error("Invalid value, probably not a nonnegative integer: "+index);
 }
}

Complexity: Looks like n_iterations searches through the ×ばつ2 base matrix instead of computing and searching the entire large 2^n_iterations ×ばつ 2^n_iterations matrix.

• root: cs.stackexchange.com/help/self-answer