Histogram Intersection with two different bin sizes?

I have two images: A and B. Image A is a screenshot of image B, the original image. While there is noise in image A, the original features are still distinguishable.

Histogram intersection tells us that:

$$K(a,b) = \sum_{i=1}^{n}\min(a_i,b_i)$$

where if $K$ is large, $a$ and $b$ are similar.

If we process image A to create a histogram with an optimal amount of ($n \pm x$) bins, how do we apply histogram intersection in this case where image A and B don't have the same amount of histogram bins?

• If you're dealing with screen shots, the number of bins should always be 256, and as such, I don't see why you need to worry about complications. Is there a reason you can't use 256 bins for A & B? – John Sep 5 '14 at 17:07
• I'm quite inexperienced but I guess it would be due to efficiency. If I have a database of 500 reference images and each image has 256 bins (x3 for each channel), I imagine that it would take a long time to compare one image with all 500 reference images. – Dennis Sep 5 '14 at 22:30
• that should be relatively snappy. Code it up first, time it. If it's too slow, use Matlab's profiler to make sure you weren't doing anything stupid (I do all the time). THEN if it's too slow, decimate the images, but use the same decimation for all your images. – John Sep 7 '14 at 2:13
• So, if one of your images is all black, it will have the same score against all other images? Is the intersection the right measure of image similarity? – rickhg12hs Sep 7 '14 at 12:32

I don't see any other way than to adapt one of the histograms such that both histograms have the same number of bins before performing histogram intersection. This will always involve some guesswork since the histograms themselves don't give you enough information to do this accurately. I would adapt the histogram with the larger number of bins to the number of bins of the other histogram. This is a simple example:

h1 = [12 17]
h2 = [9 10 11]


So in this case you want to change h2 such that it has two bins like h1. Since the interval boundary between the two intervals of h1 is right in the middle of bin 2 of h2, it is reasonable to divide bin 2 of h2 evenly between the two other bins. So you get

h2_new = [14 16]


If the new boundary falls somewhere else inside a bin interval just divide the interval by the respective percentage. This step of course involves guesswork and it would be much better if you could avoid it by making sure that both histograms are computed using the same number of bins.

As a final note, usually histogram intersection is normalized such that its maximum value is $1$:

$$K(a,b)=\frac{\sum_{i=1}^n\min (a_i,b_i)}{\min\left(\sum_i a_i,\sum_i b_i\right)}$$

• Thanks for your input Matt. I was discussing the idea with one of my supervisors and he mentioned something about calculating the optimal number of bins which led me to this question. What I am actually trying to do is image matching using color histograms. The idea is to store the histogram bins in a SQL database entry but using 256 bins would be costly when the number of images increases. What are your thoughts on this? – Dennis Sep 5 '14 at 22:36
• @Dennis I think it would be best to use the same number of bins for all images. Then you just have to reach an acceptable trade-off between performance and computational complexity. You might also try to come up with some heuristics to reduce the number of possible candidates for comparison. But first I'd try the full-blown algorithm and see how bad complexity actually gets (after having optimized your code!). – Matt L. Sep 7 '14 at 16:45