Color Distance Function

[dedndave]

a while back, i was using a modified version of an equation by
Thiadmer Riemersma to calculate the "distance" between 2 colors

http://masm32.com/board/index.php?topic=1123.msg11032#msg11032

the function i had written used the FPU, and followed that equation

well - i needed such a function, and couldn't find my previous code
so, i thought i'd just do a re-write

i examined the equation a little deeper, this time
for one thing, i don't need the "lineal distance"
i just need to compare to see which is closest
in fact, i don't really care about the scale of the result, so long as it fits in 32 bits

as it happens, there are other cases where you would want the distance squared, not lineal distance
so, it makes sense to return the squared value - take the squareroot if you need to

at the end of the day, i did it with integer math - no FPU
i also added a feature where the values may either be COLORREF or RGB format

Code Select Expand

;###############################################################################################

        .XCREF
        .NoList
        INCLUDE    \Masm32\Include\Masm32rt.inc
        .List

;###############################################################################################

ColorDist PROTO :DWORD,:DWORD

;###############################################################################################

CLRDST_CREF EQU 00FFFFFFh
CLRDST_RGB  EQU 80000000h

;###############################################################################################

        .CODE

;***********************************************************************************************

main    PROC

        INVOKE  ColorDist,563412h or CLRDST_RGB,123456h and CLRDST_CREF
        print   ustr$(eax),32

        INVOKE  ColorDist,0,0FFFFFFh
        print   ustr$(eax),13,10

        print   chr$(13,10)
        inkey
        INVOKE  ExitProcess,0

main    ENDP

;***********************************************************************************************

        OPTION  PROLOGUE:None
        OPTION  EPILOGUE:None

ColorDist PROC dwColor1:DWORD,dwColor2:DWORD

;returns a value that is proportional to an approximation of the square of the distance between 2 colors
;version 2.0, David R. Sheldon, 3-2015
;
;(1020 + Ra + Rb) * Dr^2  +  2040 * Dg^2  +  (1530 - Ra - Rb) * Db^2
;Ra = red1
;Rb = red2
;Dr = red1 - red2
;Dg = green1 - green2
;Db = blue1 - blue2
;(1530 - Ra - Rb) = 2550 - (1020 + Ra + Rb)
;
;if one color is black and the other is white, the returned value is 298464750
;
;the equation is a modified version of one developed by Thiadmer Riemersma
;
;dwColor1 and/or dwColor2 may be either RGB or COLORREF format
;if the high byte of the DWORD is zero, it is treated as a COLORREF value (BBGGRRh)
;if the high byte of the DWORD is non-zero, it is treated as an RGB value (RRGGBBh)
;
;CLRDST_CREF EQU 00FFFFFFh
;CLRDST_RGB  EQU 80000000h
;
;in the following example, color1 is treated as an RGB and color2 is treated as a COLORREF:
;
;        INVOKE  ColorDist,123456h or CLRDST_RGB,123456h and CLRDST_CREF

;-------------------------------------------------

    push    ebx
    push    esi
    push    edi
    mov     ecx,[esp+20]                  ;dwColor2
    mov     ebx,[esp+16]                  ;dwColor1
    .if ecx & 0FF000000h
        mov     eax,ecx
        shr     eax,16
        mov     ah,0
    .else
        movzx    eax,cl
        bswap    ecx
        shr      ecx,8
    .endif
    .if ebx & 0FF000000h
        mov     edx,ebx
        shr     edx,16
        mov     dh,0
    .else
        movzx    edx,bl
        bswap    ebx
        shr      ebx,8
    .endif
    lea     esi,[eax+edx+1020]            ;ESI = 1020 + Red1 + Red2
    sub     eax,edx
    mul     eax
    mov     edi,eax                       ;EAX = EDI = (Red1 - Red2)^2
    mul     esi
    xchg    eax,edi                       ;EDI = (1020 + Red1 + Red2) * (Red1 - Red2)^2
    movzx   edx,cl
    movzx   eax,bl
    sub     eax,edx
    mul     eax
    mov     edx,2550
    sub     edx,esi
    mul     edx                           ;EAX = (1530 - Red1 - Red2) * (Blue1 - Blue2)^2
    add     edi,eax
    movzx   eax,bh
    movzx   edx,ch
    sub     eax,edx
    mul     eax
    imul    eax,2040
    add     eax,edi
    pop     edi
    pop     esi
    pop     ebx
    ret     8

ColorDist ENDP

        OPTION  PROLOGUE:PrologueDef
        OPTION  EPILOGUE:EpilogueDef

;###############################################################################################

        END     main

[FORTRANS]

Hi Dave,

   Have you looked at "Manhattan distance" (sometimes street
distance) as a metric?  For the palette reduction program I use
it as a screening step before calculating the rms distance for
candidate colors.  On a slower machine it sped things up quite
a bit when processing a large number of possible colors.

Regards,

Steve N.

[dedndave]

haven't heard of it, Steve
in this case, i wanted something simple, but meaningful
color space isn't a linear cube, so the squareroot of the sum of squares isn't quite right   :P

i played with a few values this morning and it seems to work pretty well

[dedndave]

ok - i see what it is
i have used something like that for a game map
in the game, you can move 8 different directions, instead of 4
so, to calculate paths, it's Manhattan with 45's   :P

the city of Detroit would throw a wrench in that   :lol:
they started out downtown with a sort of wagonwheel pattern, then went to a normal grid
some blocks are pie-shaped (really confusing with all the one-way streets)
in Detroit, you can go around the block and get lost

[Tedd]

It is essentially a Manhattan Euclidean distance (minus the square-root), modified to scale the components to try to account for the colour sensitivity of our eyes (most sensitive to green, least to blue.)

[rrr314159]

While I was typing this 2 new posts showed up, guess it's still relevant

"Manhattan" distance is just the sum of absolute vals. Using notation from Thiadmer's equation, where delR = C(1,R) - C(2,R) it's

delC = abs(delR) + abs(delG) + abs(delB)

In math we call the normal euclidean distance "L2", because of the two's in the eqn (x^2 + y^2 +z^2)^1/2, while this "manhattan" dist is L1 - just replace all the 2's with 1's! (I wonder if L3 or others would be worth considering.)

In Thiadmer's empirical eqn the coefficients are (2+r, 4, 3-r), where r = average of the two R vals,

r = (C(1,R) + C(2,R))/2 (normalize out the 255, and assume 0<=color<=1)

Thiadmer's eqn can be considered the sqrt of the dot product (aka "norm") of those 3 coeff's and delRGB = (delR^2, delG^2, delB^2) so to "manhattanize" her eqn you'd get: (could take sqrt of coeff's, or not)

delC = (2+r)*delR + 4*delG + (3-r)*delB

where del's are of course absolute value.

But the funny thing is, Farabi started with this approach in that thread; he was just taking abs dif of RGB vals. Remember, his question was essentially how to compute abs val of the numbers with SSE - thought there shld be one instruction to do it ...

Common wisdom seems to indicate L1 norm is not good in color space, but I guess as a first cut it's useful - computationally very cheap.

I have a question. Looking around on the net the "color distance" function is always used with reduced palette's of 16 or 256 colors, and it seems that's what you're doing with it. The idea, take from greater bit-depth colors and map to the nearest color from the reduced palette. Now, why is this still a big deal? Monitors today don't use palettes, they all have full 255-bit depth. Where do you still use 256-color palettes? Is it, perhaps, for printers?

I'm interested in color distance for a different purpose, viz. pattern recognition. A picture can have an artifact such as a line on it, which human eye can clearly see, but its pixels have slightly different values. I want the computer to be able to recognize them all as the "same" value, in order to integrate them into a line. Does anyone use color distance in such context? Know any references?

Finally, something peculiar. Do u realize that the picture of Thiadmer's eqn's that you linked to above (which u posted a while ago, in farabi's thread) has writing in its background? Looks written by a blue marker (altho, depending how your monitor color vals are set, could be brownish instead), very faded, and says something like "You please ...". It happens to be a great example of the type of thing I'd like a computer to be able to pick out. U might not have noticed it, I didn't until I viewed in the right light - sounds like a secret message for help, from someone ... you're not holding her prisoner in your basement, by any chance ...?

[FORTRANS]

Hi,

[Snip of some good comments]

I have a question. Looking around on the net the "color distance" function is always used with reduced palette's of 16 or 256 colors, and it seems that's what you're doing with it. The idea, take from greater bit-depth colors and map to the nearest color from the reduced palette. Now, why is this still a big deal? Monitors today don't use palettes, they all have full 255-bit depth. Where do you still use 256-color palettes? Is it, perhaps, for printers?

   In my case it started out as an effort to shrink the size of some
image files.  That was a lousy idea.  It evolved into an algorithm
investigation to see how good a 16 or 256 paletted image could be.
And I got to write a few dithering routines to see how they varied.
255-bit?  Hopefully 24-bit in most cases.  And a reduced palette, with
error diffusion, can help with printing.  But printer hardware is evolving
along with monitors, so not really needed I guess.  And most of the
effort on my part was a while ago.

Regards,

Steve N.

[dedndave]

Thiadmer's equation also "bends" the map at certain red levels

yah - that is just a watermark from the original website where i found it   :P

anyways....

today, i am blending colors
but - it's always nice to reduce an image to 256 colors for GIF's
better compression means lower bandwidth

here's a sample of what i'm doing at the moment   

[dedndave]

another sample...

the primary colors are initialized
but, the secondaries and combines are generated in code

[rrr314159]

@Steve N, thanks! The topic is interesting, of course, no matter what you do with it ...

Now that u mention it, compression is obviously a good idea. On the net, lots of utilities available (peazip, hyperspin, zamzar etc) but I hate to download such things. Your picture is only 30k, and looks pretty good. That's done with your own custom compressor, I suppose? Can u recommend any free prog that does a halfway decent job? What's the largest size hutch wants on this site - under 100K or so? I have some bmp's (repesenting diff eq's, very cool looking) I could show but they're multi megs, even as jpg's.

Yes, red is key in Thiadmer eqn. G coefficient is constant, but more red increases the red coeff and reduces the blue. With no red (average r = 0) red coeff is 2 and blue is 3; at max red, the opposite. Thus the more red in the picture, the more the color distance depends on red; nonlinearly of course. Intuitively I would have expected the opposite. I would expect the difference between no red, and a little red, is more noticeable than diff between a lot of red and a bit less (and same for blue), but that's not the eqn. I suppose the whole thing is extremely subjective. Meanwhile green dominates the distance regardless, with a constant coeff of 4; the other two fight it out between 2 and 3 ... no doubt it all makes sense.

The retina / brain, of course, uses two color axes (essentially): red-green and blue-yellow. Genes for red and green receptors are found close together on X chromosome (therefore men are color blind much more than women) while blue is elsewhere. Evidently originally red/green was just one receptor, the gene got copied onto the same chromosome nearby (very common, various mechanisms for this, including retroviri) and evolved to slightly differentiate (blue wavelength is much farther away from red-green). Putting the evidence together red and green are one "color pair", to be contrasted with blue at the other end. So, I'd expect the best approach would be use those 2 axes, red vs green and (red,green = yellow) vs blue. The third axis being intensity, saturation, luminosity or whatever. No doubt somebody's pet color space does exactly that, but looking around on net I don't "see" it (no pun intended :). YUV, CMYK, on and on, none of them appear to do this? Do u know of any such color space?

... this is a very interesting topic, now that u mention it!

[dedndave]

it is very interesting
and - there is a lot of very intense study in the area
facial/pattern recognition and astronomy have generated a lot of scientific interest
i got into it because of bio-med imaging applications (ultrasound scanners) back in the 80's

google for "just noticeable difference" to get some of the underlying math

there are seemingly as many color maps as there are people that study color   :lol:
some day, i may write a 3D rotatable color map

the above images were generated as 256-color BMP's
loaded into Paint, and saved as JPG - probably not the best compression

if i want presice control over a jpeg image, i use a very old version of PicView
it used to be freeware and if you look around, it can still be found
i think it uses the IImage interface to compress jpeg's
it allows you to control the hoffman quality and smoothing constants

[anunitu]

I am trying to understand what is meant by color distance. Have never heard the term,and wonder what that means.

[dedndave]

well, if you imagine a box with 3 dimensions, red, green, blue
you get an idea of "color space"

but, color (chroma) and luminance are not perceived by the human eye in a linear way
so, the box is oddly shaped, not a cube

in the digital world, we normally get 256 levels of each color
so, fitting the linear values into a non-linear space becomes a bit of a problem   :P

the routine attempts to say "these two colors are this far apart"
strictly for comparison of the distance of 2 other colors, for example

[dedndave]

here's a hypothetical example

we have a 256-color image with a palette
in the palette are these 2 colors:
R = 124, G = 190, B = 24
R = 130, G = 185, B = 30

now, we have a pixel that wants to be
R = 128, G = 188, B = 28

which palette index do we use?

well, you can see which is closest in color space and use that one

[FORTRANS]

Hi,

@Steve N, thanks! The topic is interesting, of course, no matter what you do with it ...

   You're welcome.  I should have remembered 256 color animations,
both GIF and FLI as well.  I made one FLI from ray-traced images,
and their selection of colors was rather bad.  So I did my own.  Of
course, if I had RTFM I would have seen an option to improve quality.

Now that u mention it, compression is obviously a good idea. On the net, lots of utilities available (peazip, hyperspin, zamzar etc) but I hate to download such things. Your picture is only 30k, and looks pretty good. That's done with your own custom compressor, I suppose?

   Yes, it's been a while, It is a 256 color GIF.  I most probably
reduced the colors with my own code.  The original picture was a
JPEG.  And while I have since written a GIF writer, I probably used
a paint program to resize and create the GIF file.

Can u recommend any free prog that does a halfway decent job? What's the largest size hutch wants on this site - under 100K or so? I have some bmp's (repesenting diff eq's, very cool looking) I could show but they're multi megs, even as jpg's.

   No, not really.  That was one of the ideas behind writing my own.
If you look for one, you should find a median-cut or octree program.
Those perform fairly well in terms of speed and quality.  The one
Dave pointed out in another thread seems do a good job based on
their web site.

Regards,

Steve N.