15,665,663 members
4.00/5 (1 vote)
See more:
Hello,
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?
Posted

## Solution 1

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 (http://en.wikipedia.org/wiki/Redundancy_%28engineering%29[^]) and some caching algorithm (http://en.wikipedia.org/wiki/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.

—SA

v3
tank0 19-Sep-11 9:15am
Thanks
Sergey Alexandrovich Kryukov 19-Sep-11 11:04am
You're welcome.
Good luck, call again.
--SA