I have thought about this for years, in a very low-priority thread in my head.
There are many situations where it could be useful. In this particular instance, we are making a rotoscoping application with Nuclear, where we draw polygons over a video, to create animations for a game we’re making.
The polygons have uniform fill, so it would be very useful to get a representative color automatically, based on the video pixels that lie underneath each polygon.
The first thing that comes to mind is to just get the average color. This is a simple method, but it can lead to weird results.
For instance, if we have an image that contains mostly blue, but a significant portion of the pixels is red, we’ll end up with a purple average, which is not at all representative of the picture.
The next thing I tried was to select the pixel that is closest to average. This works better, but still, in most images you’ll find edge pixels that vary smoothly between the colors the edge separates. So, in the blue-red example above, it is possible that a purple pixel is found in the boundary between blue and red. In which case we’ll end up with purple, again.
So, here is what I came up with:
- Get the average of all pixels.
- Sort all pixels; from closest to more distant from average.
- Discard the second half (the most distant pixels from average).
- Repeat, until you end up with just 1 pixel.
This works because it progressively gets rid of “impurities”.
So, for our blue-red example, in the first iteration, a purplish average will be calculated. This average will be more similar to blue though. So, we’ll discard all the red pixels in the first iteration.
The next iterations will progressively refine the blue average, until we end up with the most representative blue that can be found in the image.
Because this can be a bit slow, here is an optimization: calculate the representative color of each scanline first, then find the representative of the representatives.
Doesn’t it seem like a person picked those colors? 🙂