Interpolation – Tri(cubic?)-Interpolation on Finite Sets

3dinterpolation

I have two sets of data of same size, representing binded triplets, we can represent these two sets like this:

$\mathbb{N}_A=\{i \in\mathbb{N}\mid i\in [0;256[\; \mid i \equiv 0\, [8]\}$

$\mathbb{N}_B=\{i \in\mathbb{N}\mid i\in [0;256[\, \}$

$f(\mathbb{N}{_{A}}^{3})=\mathbb{N}{_{B}}^{3}$

For example:

(8;8;32) -> (5;7;43)

(8;0;40) -> (5;41;58)

(16;8;48) -> (5;41;58)

(8;24;48) -> (16;48;255)

I need to interpolate these two sets of values of mine in order to be able to say, for any triplet in $\mathbb{N}{_{A}}^{3}$, what is the corresponding triplet in $\mathbb{N}{_{B}}^{3}$.

Usually in IT (I ain't not mathematician) it's cool because nearly all 1-2-3dimensional problem can easily be generalized to any higher dimension and help us solve really abstract (and hardly understandable for humans) problems. But as a human not so familiar with math, it's hard for me to entirely visualize my problem. I'd tend to say $f(\mathbb{R^n})=\mathbb{R^n}$ needs $n+1$ dimensions to be drawn, so in my case it's an hypercube, to a bunch of points in cube we bind another bunch of points in the (same?) cube, but I'm pretty sure I'm wrong assuming this. Maybe the restrictions on $\mathbb{N}$ are useless but if I have to build my own algorithm later I prefered to write them there too, just in case you find them useful. Because even if I manage to find a tool for tri-interpolation, chances to find one accepting restrictions are really slim, I think, even though I'm pretty sure it changes a lot of things to have a finite set for interpolation, and maybe there's even a better way than interpolation for finite sets?

If you are interested in why I'm trying to achieve this (and maybe this could help you helping me), it's because I have two versions of a game, an old one where images were encoded in 5 bits (so 15 bits) and a newer one were images were encoded in 8 bits (so 24 bits), and I'm trying to guess the rule (even though there was no "rule") guys used to "restore" the old game, so I can apply this "rule" (my function $f$) to any 5-bits-colors game to restore it keeping the style used from old game to recent game (and yes I know if this was used in some game it may not fit in another and that's right, but my goal is to apply the rule to parts of the old game that haven't got a restored version, so I can know what they would look like if people working on the newer game would have restored them as well).

Hope I was clear, I'm still looking around tri-cubic interpolation, but all I'm kind of sure is the tri part but for the cubic I'm not sure, how can I know? In 1-dimensional functions it's more trivial to guess the "form" of the function, but in 3D I have no clue…

Best Answer

For three-variate degree $D$ polynomial interpolation of three-component (color) vectors, you need $$f(r, g, b) = \sum_{i=0}^D \sum_{j=0}^D \sum_{k=0}^D \, r^i \, g^j \, b^k \, \vec{C}_{ijk}$$ where $\vec{C}_{ijk}$ are three-component (color) vectors to be fitted to the known data. There are $(D + 1)^3$ of those. Note that usually the components are real, between 0 and 1, so that the actual valid range of inputs and outputs is just a matter of scaling, and the constant color vector components are within a sensible range (not huge in magnitude).

For cubic interpolation, $(3+1)^3 = 4^3 = 64$: $$\begin{aligned} f(r, g, b) = &\; \vec{C}_{000} + \vec{C}_{001} \, b + \vec{C}_{002} \, b^2 + \vec{C}_{003} \, b^3 \\ \; + &\; \vec{C}_{010} \, g + \vec{C}_{011} \, g \, b + \vec{C}_{012} \, g \, b^2 + \vec{C}_{013} \, g \, b^3 \\ \; + &\; \vec{C}_{020} \, g^2 + \vec{C}_{021} \, g^2 \, b + \vec{C}_{022} \, g^2 \, b^2 + \vec{C}_{023} \, g^2 \, b^3 \\ \; + &\; \vec{C}_{030} \, g^3 + \vec{C}_{031} \, g^3 \, b + \vec{C}_{032} \, g^3 \, b^2 + \vec{C}_{033} \, g^3 \, b^3 \\ \; + &\; \vec{C}_{100} \, r + \vec{C}_{101} \, r \, b + \vec{C}_{102} \, r \, b^2 + \vec{C}_{103} \, r \, b^3 \\ \; + &\; \vec{C}_{110} \, r \, g + \vec{C}_{111} \, r \, g \, b + \vec{C}_{112} \, r \, g \, b^2 + \vec{C}_{113} \, r \, g \, b^3 \\ \; \vdots \; &\; \\ \; + &\; \vec{C}_{330} \, r^3 \, g^3 + \vec{C}_{331} \, r^3 \, g^3 \, b + \vec{C}_{332} \, r^3 \, g^3 \, b^2 + \vec{C}_{333} \, r^3 \, g^3 \, b^3 \\ \end{aligned}$$ Note that this is capable of mapping blues to reds, and so on. If you have 64 color-to-color samples, you can use e.g SageMath to solve the huge mess of equations:

r, g, b = var('r', 'g', 'b')
R_000, R_001, ..., R_333 = var('R_000', 'R_001', ..., 'R_333')
G_000, G_001, ..., G_333 = var('G_000', 'G_001', ..., 'G_333')
B_000, B_001, ..., B_333 = var('B_000', 'B_001', ..., 'B_333')
R(r, g, b) = R_000 + R_001*b + R_002*b^2 + R_003*b^3 + ...
G(r, g, b) = G_000 + G_001*b + G_002*b^2 + G_003*b^3 + ...
B(r, g, b) = G_000 + G_001*b + G_002*b^2 + G_003*b^3 + ...
solve([ R(?,?,?) == ?, G(?,?,?) == ?, B(?,?,?) == ?,
        ..
        R(?,?,?) == ?, G(?,?,?) == ?, B(?,?,?) == ? ],
        R_000, R_001, R_002, R_010, ..., R_333,
        G_000, G_001, G_002, G_010, ..., G_333,
        B_000, B_001, B_002, B_010, ..., B_333)

where you need to fill in both the ... and the known color mapping samples ?. I don't know if SageMath can handle it, though.

Unfortunately, your initial premise is incorrect. Those colors are not mapped by any algorithm, but actual human artists. The mapping is not contiguous, so interpolation just won't work!

Mapping r5g5b5 to r8g8b8 is best done using a 215-entry color array. (For 24-bit color words, you'll need 98,304 bytes; for 32-bit, 131,072 bytes).

Instead of mapping colors directly, convert the source RGB to e.g. HSL (hue, saturation, and lightness), and apply any filtering in this space. (Say, increase saturation, maybe tint some hues, and so on.) Then, convert to the final color words. You do this for each possible input color once, precalculating the color map.

Color filtering in HSL colorspace is simpler, because it is closer to human perception.

Related Question