6
$\begingroup$

The context of this question is correct dithering of color with gamma correction. In dithering we add (shaped) noise $n$ to a signal $s \in [0, 1]$ based on a random variable $r \in [0, 1]$

$$s' = s + n(s, r)$$

such that when we quantize the signal to $m$ steps the rounding will end up distorting the signal less.

I already have a function that works in a linear world from here, where $n$ is a symmetric triangular distribution on $[-1, 1]$ (with the caveat that for $s$ close to $0$ or $1$ we switch to a uniform distribution on $[-\frac{1}{2}, \frac{1}{2}]$), as it has mean $0$ and appropriately smoothes out the rounding (demo that incorrectly ignores gamma: https://www.shadertoy.com/view/Wts3zH). This function written out is (matching top to bottom in priority for the cases):

$$n(s, r) \cdot (m - 1) = \begin{cases} r - \frac{1}{2}&s \leq \frac{1}{2(m-1)} \vee s \geq 1-\frac{1}{2(m-1)}\\ \sqrt{2r} - 1&r < \frac{1}{2}\\ 1 - \sqrt{2 - 2r}&r \geq \frac{1}{2}\\ \end{cases}$$

However in sRGB files we have to deal with gamma. Essentially we have an invertable transform $t$ (often $t(x) = x^{2.4}$) that is applied before/after quantization to allocate more steps to lower intensities.

This means that the average color when viewing is no longer (ignoring quantization for now):

$$\int_0^1\left(s + n(s, r)\right)\text{d}r = s$$

But is instead:

$$\int_0^1 t^{-1}\left(s + n(s, r)\right)\text{d}r > s$$

How can we change our noise function $n$ so that the average color is again $s$ after dithering, while maintaining our properties from the triangular distribution as much as possible?

For the record, the main property the triangular distribution gives is that the variance after rounding becomes constant:

$$\int_0^1\left(\left[(s + n(s, r))(m-1)\right]/(m-1) - s\right)^2\text{d}r = c$$

Where $[x]$ denotes $x$ rounded to the closest integer. Note that this only holds in the triangular part of the domain of $n$, so when $\frac{1}{2(m-1)} \leq s \leq 1-\frac{1}{2(m-1)}$.

If you want to give a shot, here is a demo that can show you the error from dithering, which has gamma correction: https://www.shadertoy.com/view/3tf3Dn.

Improve this question
$\endgroup$
4
  • $\begingroup$ I think now I understand your question. I'm not familiar with the language you implemented the function you mentioned, could you maybe write down $n(s,r)$ explicitly in "math notation"? :) (btw: I assume $r$ is uniform on $[0,1]$, right?) $\endgroup$
    – flawr
    May 1 '19 at 9:13
  • $\begingroup$ @flawr It's only dither_quantize you need to look at. There c is $s$, rng is $r$, depth is $m$, ci is $s\cdot (m-1)$ and d is $n(s, r)\cdot (m-1)$. a ? b : c means b if a else c, and clamp(x, lo, hi) is min(max(x, lo), hi). Finally uint(x) is basically $\lfloor x \rfloor$. $\endgroup$
    – orlp
    May 1 '19 at 9:49
  • $\begingroup$ @flawr One thing that isn't particularly clean here is that we must not forget $n(s, r)$ also depends on $m$, as fewer quantization steps means the noise must increase in size. It is $n(s, r) \cdot (m-1)$ that doesn't change as $m$ does. $\endgroup$
    – orlp
    May 1 '19 at 9:54
  • $\begingroup$ @flawr There is another way you can view it, which I posted here: math.stackexchange.com/questions/3200249/…. I convolved the above noise function with a unit square to find the probability that a signal $s$ gets quantized to $[s]$ after adding noise. Then you can view the whole quantizing operation as summing a couple random variables (e.g. one for the chance at $[s] -1$, one for $[s]$ and one for $[s] + 1$). $\endgroup$
    – orlp
    May 1 '19 at 10:26

Your Answer

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

Browse other questions tagged or ask your own question.