20130615

Optimizing a hue rotation operator

This post covers hue-rotation as a rotation in 3D color space, and optimizes this rotation to minimize floating point multiplications using a trick borrowed from Gauss' algorithm for multiplying complex numbers.

Hue rotation is a shift of the hue in a HSV or HSL color model, example: 


I am interested in implementing a hue rotation for Java. The colors are input in RGB format, with each component ranging from 0 to 255.

The first implementation I tested uses HSV color space. It combines an RGB to HSV conversion, hue shifting, and HSV to RGB conversion, into a single series of operations:
float min    = r&ltb?g&ltr?g:r:g&ltb?g:b; 
float value  = r&gtb?g&gtr?g:r:g&gtb?g:b; 
float C= value - min;
if (C!=0.f) { //with no saturation, hue is undefined
        float hue;
        // CONVERT FROM RGB TO HSV
        if      (value==r) hue = 6+(g-b)/C;
        else if (value==g) hue = 2+(b-r)/C;
        else               hue = 4+(r-g)/C;
        // ROTATE THE HUE
        hue += fhuerotate; 
        hue %= 6.f;
        // CONVERT FROM HSV TO RGB
        r=g=b=min;
        switch((int)hue) {
                case 0: r+=C; g+=C*hue; break;
                case 1: r+=C*(2-hue); g+=C; break;
                case 2: g+=C; b+=C*(hue-2); break;
                case 3: g+=C*(4-hue); b+=C; break;
                case 4: r+=C*(hue-4); b+=C; break;
                case 5: r+=C; b+=C*(6-hue); break;
        }
}
This approach is decent. The branching associated with the different hues is cheap on the CPU, and there aren't that many floating point multiplications or divisions. The hue space is mapped to [0,6) rather than [0,2π), which simplifies the computation.

It is also possible to implement HSV rotation as a linear transformation of the RGB color components. To start, it is possible to derive a notion of hue and chroma that relates to the RGB components without casing on hue. This is taken directly from Wikipedia and more information can be found there.

\[\alpha=\frac{1}{2}(2R - G - B)\] \[\beta =\frac{\sqrt{3}}{2}(G - B)\] \[H_2 =\operatorname{atan2}(\beta, \alpha)\] \[C_2 =\sqrt{\alpha^2 + \beta^2}\]

This gives us a Cartesian representation of hue and chroma. To complete this color space, we need a notion of "brightness". The "value" and "lightness" of HSV and HSL color spaces are defined in terms of the brightest and dimmest color component. Another notion of brightness is simply the average of the three RGB color components, termed "intensity". Intensity facilitates representing hue rotation as a linear transform in RGB space. The intensity value, combined with the cartesian hue and chroma ( or $\alpha$ and $\beta$ ), form a complete colorspace. We can do hue rotation by rotating the Cartesian ($\alpha$,$\beta$) plane, without ever explicitly converting to hue and chroma.

Once you write hue rotation as a transform in the ($\alpha$,$\beta$) plane, and combine that with converting from RGB to our HCI color-space and back, you are left with a linear transformation on the RGB color components. This transformation can be simplified to reduce the number of floating point multiplications. Expensive constants (Q1 and Q2 below) related to the rotation can be computed before iterating over the image.

Compute these as a function of the hue rotation "th" ahead of time, before iterating over the image:
Q1 = sin(th)/sqrt(3)
Q2 = (1-cos(th))/3
Then, for each RGB pixel, the hue rotation is:
rb = r-b;
gr = g-r;
bg = b-g;
r1 = Q2*(gr-rb)-Q1*bg+r;
Z  = Q2*(bg-rb)+Q1*gr;
g += Z + (r-r1);
b -= Z;
r = r1;

Using intermediate constants r1 and Z reduces the number of multiplications, at the expense of adding more additions/subtractions (and possibly reducing numerical stability). It is inspired by Gauss' trick for multiplying complex numbers.

One major difference between the HSV hue rotation and this one is how it treats the chroma component. Subjectively, the brightness of yellow, magenta, and cyan, are kept more equal to red, green, and blue, using this operator. In cases where you want to preserve subjective brightness, this is a good thing. However, this also makes yellows seem less colorful than one might expect for a hue rotation operator. This is related to how chroma is represented in the HCI color space. To paraphrase Wikipedia

The two definitions of chroma ($C$ and $C_2$) differ substantially: they are equal at the corners of our hexagon, but at points halfway between two corners, such as $H=H_2=30^o$, we have $C=1$, but $C_2\approx 0.866$, a difference of about 13.4%.

One patch is to restore the maximum color value after hue rotation. This preserves the "value" of the HSV color model and makes yellows brighter:

max = r&gtb?g&gtr?g:r:g&gtb?g:b;
rb = r-b;
gr = g-r;
bg = b-g;
r1 = Q2*(gr-rb)-Q1*bg+r;
Z  = Q2*(bg-rb)+Q1*gr;
g += Z + (r-r1);
b -= Z;
r = r1;
adjust = max / ( r&gtb?g&gtr?g:r:g&gtb?g:b );
r *= adjust;
g *= adjust;
b *= adjust;

Representing hue rotation as a linear transform is slightly faster on my system, and could be substantially faster in other environments ( e.g. where division is very costly). The subjective performance of these algorithms are comparable. The image at the start of this post was generated using the ($\alpha$,$\beta$) rotation approach without correcting for value.