Histogram estimation (from sub-set of image pixels)

Question

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.

Answer 1

I think random sampling approach seems to be not effective, since the statistical population (pixel intensities) distribution in images is heavily localized. There might be more scientific approaches, but if you need only a rough near estimation I'd like to suggest a method. Here is how:

1. Blur the image with a low-pass mask (average out neighboring pixels) [Optional, if you are O.K with blurring computations]
2. Down sample (make it smaller like by a factor of 2) the blurred image
3. Compute histogram of the down-samples blurred version of the image.

Here is a code experiment:

I=imread('coins.png');
Mask=ones(5,5);
tic
H1=imhist(I);
toc
I_Averaged=imfilter(I,Mask); %OPTIONAL STEP
I_DownSampled=I(1:3:end,1:3:end);
tic 
H2=imhist(I_DownSampled);
toc

The results:

• Elapsed time is 0.003042 seconds. %For Original Hist
• Elapsed time is 0.000365 seconds. %For DownSampled Hist

and the rough histogram and original image histogram are shown in below images:

1.Rough

  2.Original

Almost no difference, for 8 times faster computations.