Click here to Skip to main content
15,665,663 members
Please Sign up or sign in to vote.
4.00/5 (1 vote)
See more:
These days, I'm doing something with image.

Now the problem I faced is that is there any fast way to find the nearest pallette color index of one given color?

Such as give you a color A, and one color pallete B, the pallette contains many colors, you should find one color in B that is cloest to color A, and then use this color instead.

So the most basic way is like bellow
For each color D in the pallette, we get it and calc the distance of D and A using formula

d = (Ra-Rd)^2 + (Ga-Gd)^2 + (Ba-Bd)^2 (Ra,Rd,Ga,Gd,Ba,Bd means Red,Green,Red of color A and color D)

And find the smallest d, then we can find the nearest color. But if the pallette has many colors, the speed is very slow.

Is there any faster way?

1 solution

Using palettes or Indexed color scheme is pretty exotic these days where most of graphic cards, printers and other devices nicely render full pixel formats of 24 bits per pixel or more. So, I'm curious why you may need it. Are you sure you really need it?

If you really need to improve performance of the process you describe, the remedy could be very typical for performance problem of the search. This is using some redundancy ([^]) and some caching algorithm ([^]).

You can create some intermediate lookup table used to narrow down the search in one or two steps. Here is a simple example: you can divide all the RGB color space in smaller cubes. The cube can be positioned using the record RStart, GStart, BStart, Size; you can make all cubes of the same size, so Size will be a constant, and the structure will be just index IndexR, IndexG, IndexB. Each input color can be calculated as belonging to some cube in one step. To find a point in a palette, create a lookup structure in the form of dictionary System.Collections.Generic.Dictionary<CubeIndex, PalettPointList>, where CubeIndex is the index if the cube described above; and PalettPointList = System.Collections.Generic.Dictionary<Color> should list all the palette points getting into the list. You should select the size of the cube the way each cube contained at least one palette point, but not too many palette points in each cube. If the palette is very non-uniform, you can possibly optimize the lookup structure by using non-constant cube size and/or using parallelepipeds instead of cubes or possibly by introducing more them one level of hierarchy.

You need to play with the set of your palettes and the algorithm to figure our the way to get caching mechanism close to the optimum and meed your performance requirements.

Share this answer
tank0 19-Sep-11 9:15am    
Sergey Alexandrovich Kryukov 19-Sep-11 11:04am    
You're welcome.
Good luck, call again.

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

CodeProject, 20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8 +1 (416) 849-8900