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 (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
;###############################################################################################
.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
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.
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
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
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.)
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 ...?
Hi,
Quote from: rrr314159 on March 10, 2015, 02:53:09 AM
[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.
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 :biggrin:
another sample...
the primary colors are initialized
but, the secondaries and combines are generated in code
@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!
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
I am trying to understand what is meant by color distance. Have never heard the term,and wonder what that means.
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
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
Hi,
Quote from: rrr314159 on March 10, 2015, 04:17:28 AM
@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.
Quote
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.
QuoteCan 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.
Hi Dave,
Don't know if these methods are usefull for you to find the nearest color in your color palette but, you could try it out.
Make 4 look-up tables from your color palette ( one for each method ) then encode your new pixel color according the 4 methods and find the best ( nearest ) match in your color palette.
1) The lightness method:
Averages the most prominent and least prominent colors: (max(R, G, B) + min(R, G, B)) / 2
2) The average method:
Averages the values: (R + G + B) / 3
3) Colorimetric method:
It forms a weighted average to account for human perception.
Luminosity is: (R * 0.2126) + (G * 0.7152) + (B * 0.0722)
4) Luma coding method:
This is how we perceive colors from TV's monitors etc.
Luma is: (R * 0.299) + (G * 0.587) + (B * 0.114)
thanks for the hint, Marinus
as it turns out, my little routine is plenty fast for what i'm doing
tables might be better if you were processing an image :t
although, my routine uses 4 MUL's and an IMUL - i would guess maybe 70-80 clock cycles
This may be ignorant - is that 70 or 80 clock cycles per pixel you're talking about? Do u apply it to each pixel, to match to the palette? If it's something like that, shouldn't you be using SSE?
I found this free image manipulation prog "IrfanView" which seems best of the bunch, does anyone know anything about it? Recommended?
if i were using it to match pixels to a palette, i might want a faster solution
in this case, i am using it to find a few colors, only - so the function serves my purposes quite nicely
i was only giving that as an example of "color distance"
IrfanView looks quite interesting, although i have no experience with it
if you want to find others, you might look at
http://filehippo.com/software/photos_images/ (http://filehippo.com/software/photos_images/)
Quote from: dedndave on March 10, 2015, 03:44:51 PM
if i were using it to match pixels to a palette, i might want a faster solution
in this case, i am using it to find a few colors, only - so the function serves my purposes quite nicely
i was only giving that as an example of "color distance"
http://filehippo.com/software/photos_images/ (http://filehippo.com/software/photos_images/)
Hi Dave, now I understand your routine. :t
You gave me some inspiration to do a rotatable 3D color map. ( see attachment )
When I saw it on screen it gave me ideas to make use of it as for example creating 3D plasma effects etc.
2th color map cube with the colors diagonally connected. ( see attachment )
those are cool, Marinus :t
The source code.
lol
you make it look so easy :P
Nice rotating cube, Marinus :t
and thanks for the source code . BTW do you plan to release your complete MASM32 DirectX SDK ?
@Dave:
Quote from: dedndave on March 10, 2015, 05:55:40 AM
...
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
...
Didn't know it and don't understand now . Could you post a link for reading on this subject ?
Quote from: dedndave on March 11, 2015, 03:24:29 AM
lol
you make it look so easy :P
Now let's wait for a transparent color map cube with 256x256x256 selectable cells :biggrin:
Quote from: vertograd on March 11, 2015, 04:21:09 AM
Nice rotating cube, Marinus :t
and thanks for the source code . BTW do you plan to release your complete MASM32 DirectX SDK ?
Do you mean the include files for the d3dx9.lib ?
Quote from: Siekmanski on March 11, 2015, 05:11:57 AM
Do you mean the include files for the d3dx9.lib ?
I mean your all DX examples + framework
the color box Marinus shows you is a nice linear cube
but, the human eye sees different colors in different ways - it's not linear
for example, the eye is much more sensitive to greens than reds or blues
and - a graph of green levels vs how we perceive them would not be a straight line
the fact is, color space is probably not a cube at all
however, our digital input to the video adapter (3 colors, 256 levels each) seems cubical
i imagine something like a diamond shape
but none of the sides are straight or flat, nor are they the same size :P
the top point could be white and the bottom point could be black
points around the outside would be green, cyan, blue, magenta, red, yellow
the points would be at different heights, too
but, this would be a starting place to describe it
a guy named MacAdams made a 2 dimensional representation that is used in the industry
it's a flat graph, but it gives you some idea how oddly shaped things are
it shows chroma, but not luminance
there are thousands of papers to read
just google "color space" or "color map"
Hi vertograd,
Haven't done much d3d9 coding the last 10 years.
Most of my sources from that era are lost or incomplete.... :(
I don't use the d3dx9.lib anymore ( although it's a great wrapper lib). I just hated the fact you need the right version of redistributables installed before it works.
Now I only use the d3d9.lib wich has all the interfaces we need and is available on all latest windows versions as far as I know.
But you need to write your own math.lib and texture and model loaders etc.
From time to time i worked at it just for the fun, nothing really fancy.
I can put something together. What are you interested in ?
Maybe starting with some old school intro - demo coding for example to start the easy way ?
Dave, thank you for your explanations
The subject is very interesting, I'll google on it
Quote from: Siekmanski on March 11, 2015, 06:02:12 AM
...
I can put something together. What are you interested in ?
...
Hi Marinus,
I'm afraid my winter coding season comes to its end . Now I'm going to be out of active forum participation till late autumn . I want to say that your DX stuff ( esp. if put together) can be very interesting and helpful for many other forum members and guests . I've already told you that my first acquaintance with MASM began with your and Scrontie's DX SDK examples. I still keep those archives somewhere on my old machine.
Graphics is fun ! Now I'm looking forward to see what's new in upcoming DX12 and new version of OpenGL
This is what exactly Im looking for :t
Dave function seems promising, I tried to reduce the image bit depth to a lower bit depth, and here is I get
(https://scontent-sin.xx.fbcdn.net/hphotos-xtf1/v/l/t1.0-9/11156221_10204702493622309_1640120983176992349_n.jpg?oh=885cc0e2caeed206d88a935be007e498&oe=55E1EF20)
It looks better than my last line detect algo, but the line is still crude. I saw dave algo is a lot better, but I havent tried it. I used PHP for now, it slow, but it fast for coding the prototype.