0

My current color distance formula is a modified version of Euclidian distance (eDist) because with eDist I was noticing weird issues where blue could be used instead of green in some situations when green would have made more sense. So my formula is:

dR^2 + dG^2 + dB^2 + dHue^1.5

*d means "delta" or "difference"

*dHue is calculated as:

        public static float GetDegreeDistance(float alpha, float beta)
        {
            float phi = Math.Abs(beta - alpha) % 360;       // This is either the distance or 360 - distance
            float distance = phi > 180 ? 360 - phi : phi;
            return distance;
        }

I can use a KDTree for RGB values, but Hue is a bit tricky because it has values that loop around in a circle. That is- 359 is closer to 2 than 10 is. With that in mind, can anyone recommend an ideal data structure that would work for this situation? Should I just use a KDTree, find nearest 10 matches, and do o(10) search on those 10 results to see which item is the best match? Or is there a better way of doing this?

Details about usage: Once the color map is created, it will be called about 4,194,304 times to find best matches. I WILL be making a best match cache, but... the initial match finding can still be optimized.

1
  • You could consider just storing two copies in the tree, one with looped-around hue.
    – user253751
    Mar 15 at 11:59
0

A fairly simple approach would be to do two searches. Do a regular search. If the distance to the found hue is less than hue or 360 - hue, do another search with the hue set to hue + 360 or hue - 360 respectively. Make sure to input the max-distance to the second search to limit the number of nodes searched.

This would be equivalent to how KD trees are searched for closest values. First go down the branch the search target is in, than go down the other branch if the distance to the pivot-plane is smaller than the current best distance.

Another approach could be to store each color twice in the tree, so your tree spans for example [-360, 360] and normalize the input hue to [-180, 180].

1
  • ngl- your first paragraph didn't make much sense. But In your second and third paragraphs I understand your concept. Basically just have two sets of data so that you can perform binary searching as you would normally, just adjusted depending on where the boundaries are.
    – Taylor
    Apr 30 at 20:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.