Maintaining probability distribution under transform

216 Views Asked by At

The context of this question is correct dithering of color $c$ with gamma correction.

We can only ever output integers $\lfloor c \rfloor - 1,\lfloor c \rfloor,\lfloor c \rfloor + 1, \dots$, but wish to do this probabilistically such that our mean output is $c$. We do this by a triangular distribution, in which each integer $k$ surrounding $c$ has a probability of being chosen to be output, based on the distance $d = |k - c|$:

$$p(c, k) = \begin{cases} \frac{3}{4} - d^2 & d < \frac{1}{2} \\ \frac{1}{2}(d - \frac{3}{2})^2 & \frac{1}{2} \leq d < \frac{3}{2} \\ 0 & d \geq \frac{3}{2} \end{cases}$$

This works nicely, as you can see that $p(c, 2)\cdot2 + p(c, 3)\cdot 3+ p(c, 4) \cdot 4 = c$ in the neighbourhood of $c = 3$:

enter image description here

The issue is that our image file format applies gamma correction. A domain-preserving reversible transform $t$ is applied on the domain, and it is in this transformed space that our intensities are averaged. So instead of

$$p(c, 2)\cdot2 + p(c, 3)\cdot 3+ p(c, 4) \cdot 4 = c$$

What actually happens is:

$$t^{-1}\big(p(c, 2)\cdot t(2) + p(c, 3)\cdot t(3)+ p(c, 4) \cdot t(4)\big) \neq c$$

Knowing $t$ (here I'll be using $t(x) = 6\cdot (x / 6)^{2.4}$, but I'm interested in generic strictly increasing domain-preserving $t$), how can we change $p(c, k)$ such that we restore our wanted properties

$$t^{-1}\big(p(c, [c] - 1)\cdot t([c]-1) + p(c, [c])\cdot t([c])+ p(c, [c]+1) \cdot t([c]+1)\big) = c$$ $$p(c, [c] - 1) + p(c, [c]) + p(c, [c]+1) = 1$$

where $[c] = \lfloor c + \frac{1}{2} \rfloor$.

I tried correcting using the gradient of the inverse transform at $k$, which almost worked but not quite:

$$g = (t^{-1})'(k)$$ $$p'(c, k) = p(t^{-1}(c)/g, t^{-1}(k)/g)$$

attempt