CODEWITHSUNDEEP
algorithmmathcolors
Tomáš Zato
Tomáš Zato

Reputation: 53119

Calculate difference between 24 bit colors without splitting into seperate RGB bytes?

Normal approach to calculate distance between colors is probably this:

//             R G B
var color1 = 0xFF0000;
var color2 = 0x00FF00;
// Calculate points      R                    G                  B
var color1_p = [(color1&0xFF0000)>>16, (color1&0xFF00)>>8, color1&0xFF];
var color2_p = [(color2&0xFF0000)>>16, (color2&0xFF00)>>8, color2&0xFF];

var distance = Math.sqrt((color1_p[0]-color2_p[0])*(color1_p[0]-color2_p[0]) + 
                         (color1_p[1]-color2_p[1])*(color1_p[1]-color2_p[1]) +
                         (color1_p[2]-color2_p[2])*(color1_p[2]-color2_p[2]))

This is just normal Pythagorean distance. But I have to create an array or otherwise save the RGB values. I could workaround this in C++ I guess:

uint32_t color = 0xFF0000;
uint8_t* color_p = (uint8_t*)&color; // [G, B, R, alpha, segmentation fault ...]

You can try it here. Never do this with int, it can range from 16 to 64 bits on some weird platforms.

Now my question is, if there's some smart math that can be done directly on the numbers like 0xFF0000 (red, 16711680 dec) and 0xFFCC00 (orange, 16763904 dec) to calculate distance or other kind of difference. I'm looking for linear difference. By linear difference I mean that if distance between A and B is the same, the difference must also be the same, but I don't care what number exactly it is.

Upvotes: 1

Views: 1441

Answers (2)

Salix alba
Salix alba

Reputation: 7824

As @harold mentioned there are other distance metrics. The simplest being the Manhattan distance or taxicab metric. This basically calculates the sum of the absolute values. If you points were (r1,g1,b1) and (r2,g2,b2) find |r1-r2| + |g1-g2| + |b1-b2|. Its called the Manhattan distance as it measures the distance you would travel between two points if you can only move along the edges of a rectangular grid, like the road pattern in Manhattan.

Let c1=0xrrggbb be single byte representation of (r1,g1,b1) and similar for c2. If we knew r2>=r1, g2>=g1, b2>=b1 we could just find x=c2-c1, y=((x & 0xFF0000)>>16)+((x & 0x00FF00)>>8)+(x & 0x0000FF). If the points can be in any order then we have to worry about each byte overflowing.

Hackers delight has a nice way of finding the absolute value. If have a signed 32 bit integer x then we can calculate y = x >> 32; z=(x+y)^x. Gives the absolute value. We could do something like

int32_t r = ((c1 & 0xFF0000) - (c2 & 0xFF0000)) >> 16;
int32_t rsign = r >> 32; // fill with sign bit
int32_t result = (r+rsign)^r;
int32_t g = ((c1 & 0x00FF00) - (c2 & 0x00FF00)) >> 8;
int32_t gsign = g >> 32; // fill with sign bit
result += (g+gsign)^g;
int32_t b = ((c1 & 0x0000FF) - (c2 & 0x0000FF));
int32_t bsign = b >> 32; // fill with sign bit
result += (b+bsign)^b;

I think this takes 23 operations. It does not really offer an advantage over @m69's answer and integer multiplication is fast on modern hardware.

Upvotes: 1

m69 ''snarky and unwelcoming''
m69 ''snarky and unwelcoming''

Reputation: 12324

There's no avoiding the 3-dimensional nature of the calculation. A calculation using the 3-byte integer value would not respect the independence of the dimensions. The only thing you can safely do with the integer values is check for equality, which would indeed be more efficient than comparing the 3 bytes seperately (if you have a lot of identical RGB values).
You can optimize the calculation in a number of ways, but splitting the colours into seperate R, G and B values will always be part of it. Something like this will be the most efficient you can make this: 

function rgbDistanceSquared(x, y) {
    if (x == y) return 0;    // if you expect a lot of identical RGB values
    var r = ((x & 0xFF0000) - (y & 0xFF0000)) >> 16;
    var g = ((x & 0x00FF00) - (y & 0x00FF00)) >> 8;
    var b =  (x & 0x0000FF) - (y & 0x0000FF);
    return r * r + g * g + b * b;
}

document.write(rgbDistanceSquared(0xFF0000, 0xFFCC00) + "<BR>");
document.write(rgbDistanceSquared(0x00CCFF, 0x0000FF) + "<BR>");
document.write(rgbDistanceSquared(0x00CCFF, 0xFFCC00) + "<BR>");

The above code returns the distance squared, to avoid having to calculate the square root. When checking equality or comparing distances this makes no difference, because:
A < B → A2 < B2
A = B → A2 = B2
A > B → A2 > B2

Upvotes: 3

Related Questions