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

Question

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.

Answer 1

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
+--------------------------------------------------+
|                                                  |
|                                                  |
|                                                  |
|                                                  |
|                                                  |
|                                                  |
|                                                  |
|                                                  |
|                                                  |
|                                                  |
|                                                  |
|                                                  |
|                                                  |
|                                                  |
|                                                  |
|                                              ()  |
|                                          ()()    |
|                                  ()()()()        |
|                            ()()()                |
|                      ()()()                      |
|              ()()()()                            |
|        ()()()                                    |
|    ()()                                          |
|  ()                                              |
|()                                                |
+--------------------------------------------------+