11
$\begingroup$

I'm trying to use a color camera to track multiple objects in space. Each object will have a different color and in order to be able to distinguish well between each objects I'm trying to make sure that each color assigned to an object is as different from any color on any other object as possible.

In RGB space, we have three planes, all with values between 0 and 255. In this cube $(0,0,0) / (255,255,255)$, I would like to distribute the $n$ colors so that there is as much distance between themselves and others as possible. An additional restriction is that $(0, 0, 0)$ and $(255, 255, 255)$ (or as close to them as possible) should be included in the $n$ colors, because I want to make sure that none of my $(n-2)$ objects takes either color because the background will probably be one of these colors.

Probably, $n$ (including black and while) will not be more than around 14.

Thanks in advance for any pointers on how to get these colors.

Improve this question
$\endgroup$
7
  • 2
    $\begingroup$ I think you should only consider a two dimensional space, because your camera will probably not be able to distinguish objects that have the same color but different intensities. The problem is interesting though. $\endgroup$
    – Stéphane Gimenez
    Apr 20, 2012 at 21:22
  • $\begingroup$ The three dimensions come from the three color planes: red, green, and blue where they can each independently take values from 0-255. In the RGB space, I don't think there's intensity. There are other color spaces which might be more suited for this since they might only be 2D, although I don't know much about them. $\endgroup$
    – Matt
    Apr 20, 2012 at 21:28
  • $\begingroup$ If you can precisely control the amount of light casted on objects then OK. In the RGB space (100, 100, 100) and (200, 200, 200) are what I called the same color (grey) with different intensities. $\endgroup$
    – Stéphane Gimenez
    Apr 20, 2012 at 21:30
  • $\begingroup$ @Matt, Stephane seems to be suggesting that you use an HSL or HSV cube rather than an RGB cube. The colors are mapped, more or less, but then you can ignore the S component for a 2D map. I would go further to suggest a 1D scale on H alone at a chosen SV or SL which would keep your colors in a similar aesthetic "tone". The equal distribution algorithm over 1D is simpler too! $\endgroup$
    – Jason Kleban
    Apr 21, 2012 at 15:08
  • 1
    $\begingroup$ Yes, the maximum pairwise distance. @uosɐſ HSV did actually seem to return better results, than RGB. Even using all three HSV planes I could better select individual colors based on distance to each ideal color. $\endgroup$
    – Matt
    Apr 25, 2012 at 1:54

1 Answer 1

Reset to default
4
$\begingroup$

All colors will be on the surface of the RGB cube, unless I'm mistaken, for the same reason that all electrical charge appears on the surface of electrical conductors. This suggests the following method to determine colors:

  • interpret the RGB color space as an XYZ Cartesian space;
  • interpret candidate colors as charged particles, e.g., electrons;
  • find the low-energy state of the system through e.g. simulated annealing;

For $n \sim 15$, a highly accurate simulation should be fairly quick; you could use a Runge Kutta technique, or even Euler's method with a small time step could probably do it (much easier to implement/understand). I might suggest the series "Numerical Recipes" for numerical integration/quadrature techniques of interest.

Once particles converge, you have the arrangement of colors by interpreting points as colors. Initially, particles can be arranged randomly on the cube's surface, with a little spacing (helps convergence and stability issues). Putting small groups on faces of the cube should work.

To avoid getting stuck in a local (rather than global) minimum, you can "pulse" some small random electric field after convergence and see whether the system goes back to the same configuration, or a different one. It's somewhat unlikely that randomly placed particles will do that in this scenario, but possible.

EDIT:

As pointed out in the comments, the assumption that optimal solutions should lie only on the surface probably doesn't hold for all geometries in the discrete case.

Fortunately, this has little bearing on the rest of the technique described above. Particles can be initially placed anywhere; just leave some room between pairs of particles for stability and covergence, and then iterate the system to convergence, then pulse a few times (possibly with increasing intensity) to see if you can get the system to converge to some different (possibly better) configuration.

Also note that I believe this method will maximize something like "(harmonic?) average distance between pairs of particles". If you want to maximize the minimum distance between pairs of particles, or some other average (geometric?) between pairs of particles, this may not give you the best solution.

In any event, I feel like this technique will give you an easy way to come up with good approximately-optimal sets of colors... getting actual "optimal" solutions is probably not required for your use-case. Naturally, if an exact and provably optimal solution is desired, numerical simulation is probably not the best way to go.

Improve this answer
$\endgroup$
5
  • 3
    $\begingroup$ For $n=9$ best solution is putting one of the nodes in center of cube and putting others in corners of cube, so your assumptions are not true. $\endgroup$
    – user742
    Apr 21, 2012 at 14:42
  • $\begingroup$ @SaeedAmiri Interesting observation... the issue may very well be with the discrete nature of this problem, compared to the usual physical discussion of charge densities. It's worth noting, however, that there's no reason that the numerical simulation with physical annealing wouldn't still find the solution you describe; editing answer to refelect your comment and this insight. $\endgroup$
    – Patrick87
    Apr 21, 2012 at 16:38
  • $\begingroup$ I'll see if I can figure out how to do this in matlab (with simulannealbnd). The difficulty I imagine will be in translating the problem into a mathematical function that matlab can try to minimize. $\endgroup$
    – Matt
    Apr 21, 2012 at 17:47
  • $\begingroup$ p.s. my initial thought was to use the vertices of a polyhedron (icosahedron), since I also thought that the solution would probably have them on the surface, but then I wasn't sure if that would be true. $\endgroup$
    – Matt
    Apr 21, 2012 at 17:52
  • $\begingroup$ In matlab I wrote a function, which given a set of (x,y,z) points, it calculates the sum of the pairwise euclidean distances between each pair of points in the set. Then I divide one by the result and matlab is supposed to find the minimum of this function. But matlab doesn't get it right, for instance, for 4 3D points it returns the following x1,x2,x3,x4;y1,y2.... points (0-1 range): 0.0001, 0.0031, 0.9993, 0.9920; 0.9970 0.0004 0.9919 0.0030; 0.0030 0.0003 0.9973 0.5756. Nonetheless, I think it's a matlab issue so I'll accept this. $\endgroup$
    – Matt
    Apr 25, 2012 at 1:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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