Problem: How to find gray-scale image histogram without iterating all pixels and binning them.
Description: Suppose that I have large set of images with no common scene and of different resolutions. For each image I would like to compute histogram but to save processing time, I want just an estimate rather than finding the full histogram.
One way which is more or less obvious is to take just sub-set of pixels in a clever way and use these to determine the estimate. The problem is then how to sample the image (which pixels to take) so that the estimate is really representative (similar to full histogram). What would be a good sampling technique to use? E.g. the simplest may be to take N samples at random positions. I have thought of some approaches but I'd be interested if there are any that were proven to give good estimate or, if there are none, in your ideas what could work.
There may be also different approaches to histogram estimation that I didn't think of other than (or complementing) taking sub-set of pixels. I'd be glad for pointing out anything that may improve estimate or processing speed.
I was searching for some time but there seems to be no scientific papers or other resources that would discuss this issue.