I have had to manipulate a lot of images in my life to look nice with brands where no designer was available to do the job. I wanted an algorithm to make this easier for a long time, and recently I developed one. The basic idea is to make, say, the reds or blues in an image specific reds and blues, while maintaining the image as much as possible and still keep the relationships between colors intact. In the example, we want a color between the old red and blue (some purplish color) to be between the new red and blue in the transformed image (a transformed purple).
Basic Description
The make the explanation easier to visualize, I’ll first explain it using only two colors channels (red and cyan), so that the color space is 2D and we can easily make images of everything.
This is the two-channel color space we will use for the explanation. In this space, colors have two coordinates, which represents the red and cyan amounts respectively. (0, 0) correspond to black, (1, 1) to white, (1, 0) to red and (0, 1) to cyan.
The principle that we will exploit is that there is a straightforward way to map one triangle to another, and that this mapping preserves lines. This second part simply means that if P maps to P’ and Q maps to Q’, and R is a point between P and Q, then the map of R is a point R’ between P’ and Q’.
The mapping is called an affine map, and it works as follows:
- Suppose the triangles are ABC and A’B’C’, where A, B, C and so on are the vertices of the triangles represented as vectors.
- Any point p can be expressed as a weighted sum of A, B, and C (using coordinates), so p = aA + bB + cC. The triplet (a, b, c) is called the barycentric coordinates of p.
- We can now use these weights, and apply them to the new triangle to form a new point p’ = aA’ + bB’ + cC’, and this is how we calculate the resulting point for each point.
Below are the barycentric coordinates of important points, and what they map to:
| Point | Coordinate | Mapped point |
|---|---|---|
| A | (1, 0, 0) | A’ |
| B | (0, 1, 0) | B’ |
| C | (0, 0, 1) | C’ |
| (A + B) / 2 | (0.5, 0.5, 0) | (A’ + B’) / 2 |
| (A + B + C) / 3 | (0.333, 0.333, 0.333) | (A’ + B’ + C’) / 3 |
Here are a few things about these coordinates:
- They add to one.
- If they are all positive, p lies inside the triangle. (And so then, will p’)
- If the coordinate that corresponds to a vertex is 0, p lies on the line formed by the other two vertices (and so p’ will lie on the line formed by the mapped vertices).
So how do we use this transformation to map colors of an image?
Let’s start with one color:
- Pick a color in the input image.
- This point, together with the vertices of a color space, forms a point set. Find a triangulation of this set. The Delayney triangulation is a good candidate, as it avoids sliver triangles, which leads to better results.
- Pick a color in the available color space that we want to map it to.
- Now move all the vertices of the triangles that correspond to the input color to the output color, giving a new set of triangles. This gives us a mapping from each triangle T_i in the input set, a triangle T’_i in the output set.
- Now, for each pixel in the input image:
- Find the triangle T it is in, and the corresponding mapped triangle T’.
- Calculate the affine mapping of that point.
- This is the new color of the pixel.
Let’s start with a simple example where we map a greyish red to a brighter red.
Here is how it transforms the image:
The original image and the mapped image. The yellow and blue markers correspond to colors marked in the color space above.
Here is the same idea, but with two input colors. The main difference is that we now have more triangles; everything else stays the same.
And here is the result.
The original and mapped image. The yellow and blue markers correspond to colors marked in the color space above as before, but now the color below the blue marker is mapped to a target color we specified.
The same idea applies to 3 channel color spaces, but here we rely on the affine mapping between tetrahedra as the basis: Given two tetrahedra ABCD and A’B’C’D’, calculate the barycentric coordinates of a point p (a, b, c, d) such that p = aA + bB + cC + dD, then use these to calculate a new point p’ = aA’ + bB’ + cC’ + dD’.
The processing algorithm then becomes the following:
- Select a set of input colors to map.
- These points, together with the vertices of the cube that represents the color space, form a set. Find a triangulation for this set. As in the 2D case, the Delaunay triangulation gives good results.
- For each of the input colors, select a color you want to map it to.
- Now move all the vertices of the tetrahedra that correspond to the input color to the output color, giving a new set of tetrahedra. This gives us a mapping from each tetrahedron T_i in the input set, a tetrahedron T’_i in the output set.
- Now, for each pixel in the input image:
- Find the tetrahedron T it is in, and the corresponding mapped tetrahedron T’. Calculate the affine mapping of the pixel color.
- This is the new color of the pixel.
Implementation Notes
Most of the processing can be done in advance, so that each pixel requires two computations:
- Determining which tetrahedron it falls into.
- Multiplying the color with a matrix associated with the tetrahedron.
The matrices are all computed in advance, so the main bottleneck is determining which tetrahedron the color falls into.
Since the algorithm is a pixel-wise operation, the algorithm is easy to parallelize.
Limitations
There are two things to watch out for:
- Avoid using input color points that are very close to each other. Choose only one from any closely spaced group. This is especially important near the vertices of the color space cube—directly map these vertices to the target color.
- Keep the output color within a close range of the input color to prevent visual artifacts. For more drastic color changes, consider using a different algorithm better suited for significant transformations.
