# Histogram estimation (from sub-set of image pixels)

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.

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');
tic
H1=imhist(I);
toc
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.

• Thanks for also implementing this and showing results. There is one problem with this solution - the optional averaging step. I think it would be even more computationally expensive than finding full histogram. I'll try to use the down-sampling on its own though. – Raven Mar 21 '17 at 15:01
• You are right, of course, it is not necessary at all. The results are taken without blurring the image. note the code, the first step is carried out but its result is not used. – MimSaad Mar 21 '17 at 15:11
• Sorry, I indeed missed that. Thanks for pointing out. If nothing else pops up in near time I'd consider this to be the answer. – Raven Mar 21 '17 at 19:09