A fast RGB to HSV floating point conversion

The operations typically performed to convert from RGB to HSV are the following:

  • find the largest RGB component
  • find the smallest RGB component
  • compute V and S
  • select the main circular sector for H
  • compute H

Here is, to my knowledge, the most commonly used RGB to HSV routine for floating point, with an extra minor optimisation (adding 1e-20f to divisors to avoid the need to care about divisions by zero):

static void RGB2HSV(float r, float g, float b,
                    float &h, float &s, float &v)
{
    float rgb_max = std::max(r, std::max(g, b));
    float rgb_min = std::min(r, std::min(g, b));
    float delta = rgb_max - rgb_min;
    s = delta / (rgb_max + 1e-20f);
    v = rgb_max;

    float hue;
    if (r == rgb_max)
        hue = (g - b) / (delta + 1e-20f);
    else if (g == rgb_max)
        hue = 2 + (b - r) / (delta + 1e-20f);
    else
        hue = 4 + (r - g) / (delta + 1e-20f);
    if (hue < 0)
        hue += 6.f;
    h = hue * (1.f / 6.f);
}

Several things seem worth noticing already:

  • Most of the complexity comes from the hue calculation.
  • Four min/max operations are performed to find rgb_max and rgb_min; however, sorting three values can be done with only 3 comparisons. This is not necessarily problematic because min/max could be wired in an efficient way depending on the CPU.
  • Two additional tests are performed to compare r and g to rgb_max; if rgb_max and rgb_min were computed using tests, this is a waste of time to compare them again.
  • Adding 6.f to the final hue value only has a 16.6% chance of happening.

The actual hue calculation depends on how r, g, and b are ordered:

$\operatorname{Hue_{0\dots 6}}(r,g,b)=\begin{cases}
    (g - b) / (r - b), & \text{if $r \ge g \ge b$}.\\
    6 + (g - b) / (r - g), & \text{if $r \ge b \ge g$}.\\
    2 + (b - r) / (g - r), & \text{if $g \ge b \ge r$}.\\
    2 + (b - r) / (g - b), & \text{if $g \ge r \ge b$}.\\
    4 + (r - g) / (b - g), & \text{if $b \ge r \ge g$}.\\
    4 + (r - g) / (b - r), & \text{if $b \ge g \ge r$}.\\
  \end{cases}$

But let’s rewrite this in terms of x, y and z, where x is the largest of (r,g,b), z is the smallest of the three, and y is inbetween:

$\operatorname{Hue_{0\dots 6}}(R,G,B)=\begin{cases}
    (y - z) / (x - z), & \text{if $r \ge g \ge b$}.\\
    6 + (z - y) / (x - z), & \text{if $r \ge b \ge g$}.\\
    2 + (y - z) / (x - z), & \text{if $g \ge b \ge r$}.\\
    2 + (z - y) / (x - z), & \text{if $g \ge r \ge b$}.\\
    4 + (y - z) / (x - z), & \text{if $b \ge r \ge g$}.\\
    4 + (z - y) / (x - z), & \text{if $b \ge b \ge r$}.\\
  \end{cases}$

There are a lot of similarities here. We can push it even further, using the fact that x ≥ z and y ≥ z by definition:

$\operatorname{Hue_{0\dots 6}}(R,G,B)=\left|K + \dfrac{y - z}{x - z}\right|,
 \text{with $K =\begin{cases}
    0, & \text{if $r \ge g \ge b$}.\\
    -6, & \text{if $r \ge b \ge g$}.\\
    2, & \text{if $g \ge b \ge r$}.\\
    -2, & \text{if $g \ge r \ge b$}.\\
    4, & \text{if $b \ge r \ge g$}.\\
    -4, & \text{if $b \ge b \ge r$}.\\
  \end{cases}$}$

That’s actually the same calculation! Only the hue offset K changes. The idea now is the following:

  • Sort the triplet (r,g,b) using comparisons
  • Build K while sorting the triplet
  • Perform the final calculation

Putting the idea into practice gives us the following code:

static void RGB2HSV(float r, float g, float b,
                    float &h, float &s, float &v)
{
    float K = 0.f;

    if (g < b)
    {
        float tmp = g; g = b; b = tmp;
        K = -1.f;
    }

    if (r < g)
    {
        float tmp = r; r = g; g = tmp;
        K = -2.f / 6.f - K;
    }

    if (g < b)
    {
        float tmp = g; g = b; b = tmp;
        K = -K;
    }

    float chroma = r - b;
    h = fabs(K + (g - b) / (6.f * chroma + 1e-20f));
    s = chroma / (r + 1e-20f);
    v = r;
}

You can check for yourself that the values for K explicited above are properly generated by that function. There were many other ways to sort (r,g,b) but this specific one lets us do one final optimisation.

We notice that the last swap effectively changes the sign of K and the sign of g - b. Since both are then added and passed to fabs(), the sign reversal can actually be omitted.

That additional trickery gives us this final code:

static void RGB2HSV(float r, float g, float b,
                    float &h, float &s, float &v)
{
    float K = 0.f;

    if (g < b)
    {
        std::swap(g, b);
        K = -1.f;
    }

    if (r < g)
    {
        std::swap(r, g);
        K = -2.f / 6.f - K;
    }

    float chroma = r - std::min(g, b);
    h = fabs(K + (g - b) / (6.f * chroma + 1e-20f));
    s = chroma / (r + 1e-20f);
    v = r;
}

That’s 2 tests and 1 std::min call instead of the previous 3 tests and 4 std::min/max calls. We really should see some kind of performance gain here.

And as expected, benchmarks indicate a performance increase of 25 to 40 % with a great variety of CPUs, compilers and compiler flags. The following graph (average nanoseconds per conversion) is on a Core i7-2600K CPU, using g++ 4.7.2 with -O3 -ffast-math:

  • Posted: 2013-01-13 06:19 (Updated: 2013-02-11 13:48)
  • Author: sam
  • Categories: optim c++

Attachments (1)

Download all attachments as: .zip

Comments

1. Andrea.doimo@gmail.com -- 2013-01-13 10:56

Great! I'm doing color conversions in javascript, so any speed gain is welcome!

2. B.stolk@gmail.com -- 2013-01-13 19:06

If source data is in 8/8/8 integer bits, One option is to spend 16Mbyte for a lookup table, which could be the fastest way.

3. sam -- 2013-01-13 20:53

@B.stolk: unfortunately this can only be true in the magical world of zero-latency memory accesses :-)

4. sam@rfc1149.net -- 2013-01-22 12:11

Any reason not to use std::swap?

5. sam -- 2013-01-22 14:44

@sam: no, no specific reason, except maybe that it would make the code slightly less obvious to the non-C++ literate.

6. str82no1 -- 2013-07-06 19:43

Hello,

What are the ranges for the input and output values?

Thank you!

7. sam -- 2013-07-06 19:48

@str82no1 all values are floating point between 0.f and 1.f.

8. anonymous -- 2013-07-06 20:02

@sam Thanks!

9. anonymous -- 2013-07-14 22:40
float chroma = r - std::min(g, b);

Won't std::min(g, b) at this point always return b, considering the if(g < b) block earlier?

10. sam -- 2013-07-14 23:14

@anonymous No, because g may still change in the if (r < g) block.

11. anonymous -- 2013-07-15 04:53

@sam ok... seems like there's another optimization in there somewhere. The result is only g in 4/13ths of cases. For 100% of those cases the r < g line evaluates as true, which is only 7/13ths of cases. Also for 100% of cases where the min is g, r starts less than g. Hmmmm....

12. anonymous -- 2013-07-15 05:29

Figured it out...small performance increase at the expense of an extra register and two assigns.

static void RGB2HSV(float r, float g, float b,
                    float &h, float &s, float &v)
{
    float K = 0.f;
    if (g < b)
    {
        std::swap(g, b);
        K = -1.f;
    }
    float min_gb = b;
    if (r < g)
    {
        std::swap(r, g);
        K = -2.f / 6.f - K;
        min_gb = std::min(g, b);
    }
    float chroma = r - min_gb;
    h = fabs(K + (g - b) / (6.f * chroma + 1e-20f));
    s = chroma / (r + 1e-20f);
    v = r;
}

The std::min(g,b) will only execute in 7/13ths of cases (rather than 13/13ths) Though the performance increase depends on how std::min is optimized, like you mentioned in your article. It could be as simple as a switch statement on MIPS CPUs which would make it more efficient, but the assembly output on my gcc 4.7.2 x86_64 std::min wasn't so optimal.

But regardless, your optimization is really cool. Definitely sped up my code. Thanks! :)

13. phoebus1966 -- 2014-01-14 01:36

What about the trigonometric approach. Anyone?

14. phoebus1966 -- 2014-01-14 01:48

So here it is. A tad slow but what's in the way to 'linearize' the cosine function. I get itches from switches, it breaks the colour circle, not?

void HSV2RGB(byte &R, byte &G, byte &B, int H, byte S, byte V)

{

float saturation = 255 - S;

byte r = V * constrain(0.5+cos(radians(H)),0,1);

byte g = V * constrain(0.5+cos(radians(H-120)),0,1);

byte b = V * constrain(0.5+cos(radians(H+120)),0,1);

byte white = 0.3*r + 0.59*g + 0.11*b;

R = r + saturation/255 * (white - r);

G = g + saturation/255 * (white - g);

B = b + saturation/255 * (white - b);

}

H is from 0 to 360 S and V are from 0 to 255

Changing S to zero will translate H into the equivalent greyscale of the colour and dim it according to V.

We're dealing with RGB LED's.

15. Petr -- 2014-03-10 00:12

I published yet another RGB to HSV and HSV to RGB conversion by using SSE/SSE2, check it out:

https://github.com/kobalicekp/rgbhsv

16. steph -- 2016-05-01 13:51

Thanks for your article. Here is a RGB to HSL implementation:

struct COLOR_HSL
{
	float h;
	float s;
	float l;
};
COLOR_HSL CORE_API RGBtoHSL(COLORREF color)
{
	COLOR_HSL result;
	int x = GetRValue(color);
	int y = GetGValue(color);
	int z = GetBValue(color);
	float k = 0.0f;
	if (y < z)
	{
		swap(y, z);
		k = 6.0f;
	}
	if (x < y)
	{
		swap(x, y);
		k = 2.0f - k;
	}
	int lightness = x + min(y, z);
	if (int chroma = x - min(y, z))
	{
		result.h = fabsf(float(y - z) / float(chroma) - k) * 1.0f / 6.0f;
		result.s = float(chroma) / float(255 - abs(lightness - 255));
	}
	else
	{
		result.h = 0.0f;
		result.s = 0.0f;
	}
	result.l = lightness * 1.0f / 510.0f;
	return result;
}
17. BrianP -- 2016-06-04 01:00

Sam, The horribly inefficient and redundant standard rgb->hsv calc has always bugged me. As I was attempting to hack a vastly superior method, I stumbled upon yours. It probably saved me days of hair pulling. Very Slick!

What is even cooler than the Cone of HSV based on some funky, computer-centric RGB cube? The Sphere of LAB space based on primate perception!

It involves much more intricate calculations which requires an XYZ intermediate space as well as matrix transforms for illuminant. If you could similarly fix RGB->LAB, what would an even more momentous leap forward!

My hat's off to you,

Brian

http://www.brucelindbloom.com/index.html?Equations.html

18. anonymous -- 2016-09-29 10:32

Hello,

Tested the final code and found it actually slower than the original without any optimization. And the reason is fabs(). If you really want to get speed increase, then better change it to "if (a < 0) a = -a;

Regards, Andrew

156. Loraine -- 2016-10-15 08:12

Hi my name is Loraine and I just wanted to send you a quick note here instead of calling you. I came to your Blog: A fast RGB to HSV floating point conversion – Lol Engine website and noticed you could have a lot more traffic. I have found that the key to running a successful website is making sure the visitors you are getting are interested in your website topic. There is a company that you can get keyword targeted visitors from and they let you try the service for free for 7 days. I managed to get over 300 targeted visitors to day to my site. http://korturl.no/sy6t - Unsubscribe here: http://hothor.se/1u2ei

Add New Comment