How is downscaling image affecting dominant color in it?

Question

I am looking to efficiently and quickly compute the most dominant color in an image. By dominant I mean the color present in the most amount of pixels. When attempting to implement this I quickly noticed the biggest bottleneck was in looping through the sheer amount of pixels in images. To optimize this I experimented with rescaling the image, I noticed as I rescaled the image the dominant colors became more and more prominent. It also greatly improved my algos performance because the number of pixels I analyzed greatly dropped. Rescaling is somewhat expensive but if done once and cached I can live with it.

My question to the stack overflow community is how safe is it to rescale like this? I am concerned I am significantly trading accuracy for performance. It seems to work fine, but I would love an experts feedback. Not looking to write a paper or create the next lighting fast image processing algo, just need it to work and be reasonably efficient.

Answer 1

In terms of performance cost, your downscaling algorithm is going to be the most expensive operation. Assuming your input image is a square image, for the sake of simplicity, with dimensions of AxA, and the output image is of dimensions BxB, you'll typically do something like so:

• Apply pre-filtering
• Up-sample the image by a factor of B
• Convert to frequency domain
• Anti-aliasing filter
• Down-sample by a factor of A
• Apply post-processing filters

Assuming you are using a trivial down-sampling mechanism (ie: decimation or discarding every n'th row/column, etc), this cost is greatly reduced. By using a simpler down-sampling method, you trade off quality for performance (less memory, fewer CPU cycles used, etc).

To your question: down-sampling is affecting the dominant color:

• By discarding data permanently, in the case of decimation.
• Changing the measured data, in the case of more advanced interpolation/re-sampling methods.

The metrics you generate from the down-sampled image will be less accurate, but not necessarily less precise. That's it.

Computing the dominant color in an image is fairly cheap compared to resampling it with any method other than possibly simply decimation. Assuming even something like images with 24-bit color depth, a modern 64-bit PC will, at most, use 2^24 * (64bits / 8bits-per-byte) = 134217728 bytes of memory. You could just allocate a large chunk of memory and implement a simple histogram. You'd simply execute A*B addition operations, and another A*B comparisons, so it'd be of linear execution complexity and constant memory complexity.

Answer 2

I dont know what scaling your doing but usually there is a low pass filter passed over an image before decimating or removing pixels to resize it. Its not necessary to filter first and an effective re-sizing can be done by selectively and evenly picking out pixels directly from an unprocessed image. The filter stops information from being lost so resizing it smaller and smaller will simply result in an average of the entire image when you get down to one pixel.

Generally, to get the dominate color I would take out the gray in the image (leaving two of three dimensions) then using only pixels that are saturated above a certain percentage or threshold (like max(R,G,B) - min(R,G,B) > 20 pixels in a 256 bit color image) create a histogram of the hues. The largest count in a bin is the dominant color assuming the bins are not too small.

Maybe just histogram the hues without doing anything else, but this assumes there is no gray which would be simply color noise.

Maybe just histogram both hues and saturation dimensions, but this usually results in bins that are too small.

Maybe just histogram (max(R,G,B) - min(R,G,B)) and though the resulting histogram peaks may be blurred alittle (or spread out some) this usually works. ...but it ignores the hue and requires sampling to determine it