How to search for an optimal dithering pattern?

I'm trying to find an optimal dithering pattern which can be used as a threshold on a greyscale image to generate a 1 bit black and white image. Ideally it would be optimal in the sense that a human would judge it perceptually most close to the source image.

For instance, dithering with white noise looks pretty bad:

While dithering with blue noise looks a lot better, despite having the same amount of error:

(images from https://blog.demofox.org/2017/10/31/animating-noise-for-integration-over-time/)

While white noise doesn't look good, it can be easily generated in real time, whereas blue noise cannot.

Because of this, I'm trying to find a dithering pattern which is:

  • NxN in size
  • Has an even distribution of values: 0/N, 1/N ... (N-1)/N
  • Perceptually the best bang for the buck

After I have the best pattern for a given N (or a reasonably good pattern), step 2 would be to try and figure out how to calculate it mathematically, but the first step is to find the pattern.

Does anyone have any recommendations on a good way to do this?

What I'm currently trying is using simulated annealing to find an optimal solution. I'm using SSIM to calculate the score of how good a solution is, for use in in the simulated annealing logic.

For the simulated annealing, I initialize the pattern by doing this:

  1. Initialize the NxN pattern such that row M is set to M/N.
  2. Shuffle the pattern

When calculating a possible move to make for the simulated annealing, I pick two values at random in the NxN pattern and swap them.

This isn't working very well for me, but I am unsure if this is not a good way to go about it, or if maybe I'm choosing bad parameters for the simulating annealing and/or the SSIM.

The simulated annealing has a starting temperature, and a specified number of iterations to take it from there down to temperature 0.

SSIM on the other hand has c1, c2, and c3 which I'm setting to zero. I am also doing SSIM of every 8x8 block in the dithered image (ALL of them, even though they overlap) and averaging them together to get the SSIM score.

Here is an example of a 5x5 dither pattern this algorithm came up with, which really doesn't look good at all.

I manually derived a 5x5 by hand which looks much better in fact:

Does anyone have any recommendations on how I might search / solve this problem better?

Topic meta-learning gradient-descent

Category Data Science

1
answered at

I think you're on the right track. If you can produce an objective scoring algorithm for the output which more closely resembles your subjective perception than 1:1 error you could definitely use simulated annealing to derive from that an optimal matrix at a given size N.

Your current scoring calculation for error seems to focus too much on high-frequency information (details), and not enough on low frequency information (larger areas) - notice the results you deem subjectively superior, if blurred (low-pass-filter) more closely resemble the input image (if also blurred) compared to the results you have deemed inferior.

If it were me, my next step might be to try something hierarchical in order to avoid bias toward any given frequencies, maybe a quadtree where at each level 1x1, 2x2, 4x4, etc. I average the values of the node's children, then scoring uses the error between trees.

About

Geeks Mental is a community that publishes articles and tutorials about Web, Android, Data Science, new techniques and Linux security.