I'm surprised the algorithm for producing blue noise is so complicated.
Could you not generate white noise, then apply a high-pass filter? Say, by blurring it and then subtracting the blurred version from the original?
Could you split the map into blocks, fill each block with a greyscale ramp, then shuffle the pixels inside the block?
Could you take a random sudoku approach, where you start with a blank map, then randomly select pixels, look at the distribution of pixels in their neighbourhood, randomly pick one of the greyscale values not present (or least present) for that pixel, then repeat?
The first technique is challenging because the filter needs to have a specific frequency response, without shortcuts. Such high quality filtering can be done more simply and more exactly with an inverse Fourier transform.
The second technique doesn't seem promising because shuffling is very crude: differently shuffled small blocks are going to have border artifacts, repeating small blocks are going to have worse periodic artifacts, large blocks are going to approximate white noise rather than blue noise. Higher quality would require precomputing blue noise images, losing the advantage of on-the-fly computation.
The third technique, being sequential, is unlikely to be practically cheaper than an inverse Fourier transform.
I only went as far as generating threshold maps, not actually using them. Couldn't see how to do that using ImageMagick, and didn't want to write it manually!
The high-pass filter maps "look okay", but i haven't looked at their spectrum. How important is it that they have a specific frequency response? What is the failure mode if they don't?
The shuffling maps don't "look" so hot. There aren't border artifacts or repeating blocks (and you wouldn't expect these a priori - not sure why you think that), but indeed, it's not very different to white noise.
Could you not generate white noise, then apply a high-pass filter? Say, by blurring it and then subtracting the blurred version from the original?
Could you split the map into blocks, fill each block with a greyscale ramp, then shuffle the pixels inside the block?
Could you take a random sudoku approach, where you start with a blank map, then randomly select pixels, look at the distribution of pixels in their neighbourhood, randomly pick one of the greyscale values not present (or least present) for that pixel, then repeat?