Histogram Comparison

mediumFREEBrief HistoryImage AnalysisCV: Introduction to Computer Vision

Implement a function to compare the similarity between two grayscale images using histogram intersection. This technique is based on the idea of representing images as histograms, which are graphical representations of the distribution of pixel intensities.

The comparison of two histograms, $A$ and $B$ , is done by calculating the intersection between them, which is a measure of the amount of overlap between the two distributions.

Represent each image as a histogram with 256 bins, where each bin corresponds to a possible pixel intensity value.
Calculate the minimum value between corresponding bins in the two histograms.
Sum up these minimum values to obtain the histogram intersection.
Normalise by dividing by the number of pixels in the smaller image, and round the result to 4 decimal places.

H(A,B) = \sum_{i=0}^{255} \min(A_i, B_i)

This technique is widely used in image retrieval and object recognition systems.

Example

Input

histogram_intersection([[0,1,2]], [[0,1,2]])

Output

1.0

Reasoning

Inputs: img1 and img2 are both $1 \times 3$ grayscale images holding the intensities 0, 1 and 2. Each is summarised as a 256-bin histogram: $A_v$ is the number of pixels in the first image with intensity exactly $v$ .
Histograms: both images give $A_0 = A_1 = A_2 = 1$ and $B_0 = B_1 = B_2 = 1$ , with every other bin (3 through 255) equal to 0.
Intersection: $H(A,B) = \min(1,1) + \min(1,1) + \min(1,1) + 253 \cdot \min(0,0) = 3$ . Empty bins add nothing.
Normalisation: the smaller image has 3 pixels, so the score is $3 / 3 = 1$ , reported as 1.0.
Notice: the histogram ignores where pixels sit. Reversing one image to $[2, 1, 0]$ still scores 1.0. With $[0,0,128,128]$ vs $[0,128,128,255]$ , bin 0 gives $\min(2,1)=1$ , bin 128 gives $\min(2,2)=2$ , bin 255 gives $\min(0,1)=0$ , so $H = 3$ and the score is $3/4 = 0.75$ .

Constraints

Input images are 2D grayscale arrays with values in [0, 255]
Return the intersection value normalized by total pixels in smaller image

More from CV: Introduction to Computer Vision

Sparse Matrix Operations for Imagesmedium Multi-Scale Feature Pyramidhard Implement Prewitt Edge Detectorhard Connected Components Labelinghard K-Means Color Quantizationmedium

Concept primer

To solve this problem, you only need to understand what a histogram is and how the histogram intersection similarity works; the implementation is a direct, linear pass over the bins.

1. Background Knowledge (Key Concepts)

A grayscale image histogram is a 256-dimensional vector where each entry $A_i$ counts how many pixels in the image have intensity $i$ , with $i \in [0, 255]$ . Intensity 0 is black, 255 is white, and values in between represent shades of gray. The histogram is therefore a compact summary of how brightness values are distributed in the image.

To compare two images using their histograms, we use a similarity measure between these two vectors. One such measure is the histogram intersection:

H(A,B) = \sum_{i=0}^{255} \min(A_i, B_i)

For each bin $i$ , you take the smaller of the two counts and sum those minima across all bins. Intuitively, this measures the amount of “overlap” between the two distributions: if both histograms have similar counts across intensities, the intersection is large; if they differ a lot, the intersection is smaller.

Because this is a similarity (higher = more similar), it is often used in tasks like image retrieval and basic object recognition where you want to rank candidate images by how similar their appearance (in terms of intensity distribution) is to a query image.

2. Algorithm / General Approach

The algorithm pattern here is a simple element-wise aggregation over arrays:

You are given two arrays (the histograms) of equal length (256).
For each index:
Compute the minimum of the two values.
Add that minimum to an accumulating sum.
Return the final sum.

This is a straightforward single pass (linear-time) algorithm with a simple reduction (sum) over an element-wise operation (min).

3. Step-by-Step Strategy

Understand input format

Confirm you receive two arrays/lists, A and B, each of length 256, where A[i] and B[i] are non-negative integers (or possibly floats) representing counts or normalized frequencies.

Initialize an accumulator

Set intersection = 0 (or 0.0 if using floats).

Iterate over all bins

For i from 0 to 255:
Compute bin_min = min(A[i], B[i]).
Update intersection += bin_min.

Return the result

After the loop, return intersection.

(Optional, conceptual) If you want a normalized similarity (between 0 and 1), you can divide by a reference sum, e.g. $\sum_i A_i$ , $\sum_i B_i$ , or $\min($ \sum $_i A_i,$ \sum $_i B_i)$ , but this is not required unless the problem explicitly asks.

Pseudocode example:

def histogram_intersection(A, B):
 intersection = 0
 for i in range(256):
 intersection += min(A[i], B[i])
 return intersection

4. Common Pitfalls

Mismatched lengths: Assuming the histograms always have 256 bins; in a more general setting, you should either:
Assert they have equal length, or
Loop up to len(A) and assume len(A) == len(B).
Integer overflow: In languages with limited integer size, if counts are very large, intersection could overflow. In typical coding challenge constraints this is usually safe, but be aware in lower-level languages.
Using the wrong operation:
Do not use max or absolute difference; the formula specifically uses min(A_i, B_i) and sums those values.
Off-by-one errors:
Correct loop range is inclusive of 0 and 255, i.e., 256 iterations. In zero-based indexing languages, that is for i in range(256).

5. Time & Space Complexity

Time Complexity:
You perform a constant amount of work for each of the 256 bins, so the runtime is $O(256)$ , which simplifies to $O(n)$ where $n$ is the number of bins in the histogram.
Space Complexity:
You only use a few scalar variables in addition to the given histograms, so the extra space is $O(1)$ (constant auxiliary space).

solution.py

Python 3.13

Test results