# Inverse of any strictly monotonic increasing function defined over a fixed domain and range.

I am working on a problem in image processing, one part of which involves inverting a transformation which is applied to the value of every pixel in a (greyscale) image.

I've included a figure illustrating quite nicely what a given transformation and its inverse might look like.

In the domain of this problem, I can assume that any transformation I need to invert will be defined by a strictly monotonic increasing function, and that I only need concern myself with the portion of the function that falls within a domain and range defined by the set of possible values of a pixel (0 to 255).

I cannot for the life of me figure out how to approach this. I've had some ideas but they've all been quite incorrect after checking how they might behave on some simple test cases.

• If I was dealing with a transformation defined in a discrete way (such as a lookup table) this would be as trivial as swapping the x and T(x) entries. – ophilbinbriscoe Sep 25 '16 at 2:19

You have your graph of $f$ as set of points $$G_f = \{ (x_i, y_i) \mid y_i = f(x_i)\} \subseteq \{ 0, \dotsc, 255 \}^2$$ then the inverse relation is $$(G_f)^{-1} = \{ (y_i, x_i) \}$$ If $f$ is injective, which is the case if it is strictly monotonic increasing, then $$(G_f)^{-1} = G_{f^{-1}}$$

If I would address my friend Ruby with such a task, it would look like this.

She gave me this random strictly monotonous graph:

[[0, 0], [1, 1], [2, 2], [3, 5], [4, 9], [5, 13], [6, 15], [7, 19],[8, 22], [9, 24]]


and the inverse graph:

[[0, 0], [1, 1], [2, 2], [5, 3], [9, 4], [13, 5], [15, 6], [19, 7], [22, 8], [24, 9]]


I also asked for plots, which gave:

size 25 x 25
+--------------------------------------------------+
|                                                  |
|                                                  |
|                    ()                            |
|                                                  |
|                                                  |
|                  ()                              |
|                                                  |
|                ()                                |
|                                                  |
|                                                  |
|                                                  |
|              ()                                  |
|                                                  |
|            ()                                    |
|                                                  |
|          ()                                      |
|        ()                                        |
|                                                  |
|                                                  |
|      ()                                          |
|                                                  |
|                                                  |
|    ()                                            |
|  ()                                              |
|()                                                |
+--------------------------------------------------+


and

size 25 x 25
+--------------------------------------------------+
|                                                  |
|                                                  |
|                                                  |
|                                                  |
|                                                  |
|                                                  |
|                                                  |
|                                                  |
|                                                  |
|                                                  |
|                                                  |
|                                                  |
|                                                  |
|                                                  |
|                                                  |
|                                                ()|
|                                            ()    |
|                                      ()          |
|                              ()                  |
|                          ()                      |
|                  ()                              |
|          ()                                      |
|    ()                                            |
|  ()                                              |
|()                                                |
+--------------------------------------------------+


We see that the inverse graph is not defined for all $x$ values, so we would need to fill the gaps by some interpolation scheme, e.g. $$y = (1-\lambda) y_i + \lambda y_{i+1} \quad (\lambda \in [0, 1])$$

Here is an example, where we interpolated between points:

size 25 x 25
+--------------------------------------------------+
|                                                  |
|                                                  |
|                                                  |
|                                                  |
|                                                  |
|                                                  |
|                                                  |
|                                                  |
|                                                  |
|                                                  |
|                                                  |
|                                                  |
|                                                  |
|                                                  |
|                                                  |
|                                              ()  |
|                                          ()()    |
|                                  ()()()()        |
|                            ()()()                |
|                      ()()()                      |
|              ()()()()                            |
|        ()()()                                    |
|    ()()                                          |
|  ()                                              |
|()                                                |
+--------------------------------------------------+

• Thank you for your detailed reply.I can definitely see how this works for a discrete mapping, do you have any intuition towards what this might look like for a continuous approach? – ophilbinbriscoe Sep 25 '16 at 4:21
• I will mark this as the answer since most people looking to tackle with this problem will be concerned with finding a working implementation, vs the theory. – ophilbinbriscoe Sep 25 '16 at 4:22
• If your function is continuous $f = f(x)$, you still evaluate it at a discrete set of arguments $x_i$ resulting in a sampled set $y_i = f(x_i)$. These points you invert $(x_i, y_i) \to (y_i, x_i)$ and apply some interpolation. Better drive the sampling of $f$ from the inverse side. – mvw Sep 25 '16 at 4:31