Unfortunately entirely deterministic version of this algorithm fails on Test #10. So I'm very curious about this Test #10. Because I've done a lot of testing in MATLAB of varoius modification of Floyd-Steinberg dithering algo, including zig-zag proseccing and edge attending. In all cases constraint in statement can be hardened from 20 to 10 and even less. On normal images error is about 6-8.

I guess Test #10 some kind of periodic image, that has bad compatibility with that unnatural restriction put in the problem. I mean it square form and discontinuous nature. I think dithering yield much more better image than that which can be produced by uniform minimization of constrain function.

I solve this issue whit Test #10 by adding a little bit of randomness in my dithering algo. I mean in place of this threashold function:

int quantize(int value) {
    if (127 < value) {
        return 255;
    }
    return 0;
}

I'm using this function:

int quantize(int value, int randomness) {
    if (127 - randomness + rng.nextInt(2 * randomness + 1) < value) {
        return 255;
    }
    return 0;
}

This provides me with magical parameter "randomness" varying which and playing tambourine I got my AC. 8-] I think I should add constraints checking and reprocessing in case the check was a fail, but I'm too lazy, I guess in case of possible future rejudging everything will be fine. :)

I express my sincerest thanks to authors of this beautiful problem. It has bugged me a lot in era of matrix printers how can they do this funny dotted images. Finally I have my answer and I can even do it myself!!!

Edited by author 17.01.2018 02:43

There is very good article about others dithering algorithms: http://www.tannerhelland.com/4660/dithering-eleven-algorithms-source-code/ It even mention static dithering.

But I want to disagree over the way they implemented error partitioning to distribute it among neighbouring pixels: they are dividing the error, then multiplying it and then adding to neighbours. Using integer arithmetics this leads to relatively big errors producing that can be reduced by first multiplying and only then dividing. But this approach has the same error source, namely discading remainder after division, it's just not multiplied further. Taking into account constrants put in the problem it will be much better to calculate all the remainders and put them in one or more pixels. Just compare the following:

{
  error1 = 1 * (error / 16);
  error3 = 3 * (error / 16);
  error5 = 5 * (error / 16);
  error7 = 7 * (error / 16);
}
{
  error1 = (1 * error) / 16;
  error3 = (3 * error) / 16;
  error5 = (5 * error) / 16;
  error7 = (7 * error) / 16;
}
{
  error1 = (1 * error) / 16;
  error -= error1;
  error3 = (3 * error) / 15;
  error -= error3;
  error5 = (5 * error) / 12;
  error -= error5;
  error7 = (7 * error) / 7;
}

Edited by author 17.01.2018 15:59