Skip to content
Tutorials Center
My learning

Topics

Lesson 41 of 46 ยท Projects

Project: Image Search by Similarity

Build image search from scratch: color histogram and HOG features, distance ranking, nearest neighbours and honest evaluation with precision@k and MAP.

"Find me more pictures like this one." Reverse image search, photo-library suggestions and visual product search all work the same way. Every image becomes a feature vector (a list of numbers), the vectors of similar images land close together, and a search is a nearest-neighbour lookup: measure the distance from the query's vector to every vector in the database and return the closest ones.

In this project you will build that engine with two kinds of features, a color histogram for scenes and a gradient-orientation descriptor (HOG, see the HOG lesson) for handwritten digits, and then you will measure how good the results are. Along the way you will discover the key lesson of image retrieval: the quality of the search depends almost entirely on whether the features keep the information that makes two images "similar" for your purpose.

flowchart LR
    A["database images"] --> B["feature extraction"]
    B --> C["feature matrix<br/>one row per image"]
    D["query image"] --> E["same feature extraction"]
    C --> F["distance to every row"]
    E --> F
    F --> G["sort: nearest first"]
    G --> H["top-k results"]

Image search is feature extraction plus a sorted distance list. The query must go through exactly the same extraction as the database.

Part 1: Searching scenes by color

The database is 150 tiny 24 by 24 color scenes in five categories (30 each): sunsets, forests, oceans, fields (blue sky above green grass) and lakes (green trees above blue water). Within a category the images differ by a random color cast, noise and texture.

A color histogram counts how many pixels fall into each color bin. We divide each of the R, G and B channels into 4 ranges, which gives 4 x 4 x 4 = 64 bins, and divide by the pixel count so that the histogram sums to 1 and image size does not matter. Distance between histograms is the L1 distance (sum of absolute differences). The helper precision_at_k uses every image as a query once, retrieves the k nearest others, and reports the fraction that have the same category as the query. That fraction is precision@k.

Python A color histogram search engine

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Precision@10 is 1.00 for sunsets, forests and oceans, but only about 0.5 for fields and lakes. The two weak classes contain exactly the same colors (sky blue and grass green); one just has them upside down. A color histogram counts colors and throws away where they are, so a field and a lake are the same image to it. The results prove it: the field query mixes in lakes.

Keeping a little layout

A cheap fix is to build one histogram for the top half of the picture and one for the bottom half, then concatenate them into a single 128-number vector. Now "blue on top" and "blue below" are different features. Finer grids (3 by 3, 4 by 4) keep even more layout, at the price of longer vectors and more sensitivity to small shifts.

The same experiment also compares three distance functions: L1, L2 (Euclidean) and chi-square, which divides each squared difference by the sum of the two bins so that differences in rare colors count as much as differences in common ones.

Python Global versus spatial histograms

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The grid features reach a perfect 1.000 for all three metrics, while the global histogram stays at about 0.80. The choice of distance function barely matters on this simple data; the choice of features matters enormously. This is typical: spend your effort on the features first.

Note: A color histogram is not invariant to lighting. A sunset photographed an hour later has different colors and a different histogram. Converting to a color space that separates brightness from color (such as the HSV or Lab spaces in Color Channels and Color Spaces) and dropping the brightness channel makes the search more robust to this.

Part 2: Searching handwritten digits by shape

Color is useless for finding digits, which are gray strokes on a dark background; the information is in the shape. We use scikit-learn's 8 by 8 digits (1,797 images, values scaled to 0 to 1), which also have labels, so we can score retrieval honestly.

Three feature sets compete:

  • Raw pixels: the 64 intensities, compared directly.
  • HOG: for each 2 by 2 cell, a histogram of 8 gradient orientations weighted by gradient strength, normalized to unit length (128 numbers). It describes which way the strokes point and where.
  • Gray-level histogram: how many pixels have each brightness, the digit-world analogue of the color histogram. It throws away position.

200 randomly chosen images are the queries and the other 1,597 form the database, so a query never finds itself. Besides precision@k we report mean average precision (MAP). For one query, rank the entire database and average the precision measured at the rank of every correct image; the score is 1.0 only if all images of the right digit come before any other. MAP is the mean over all queries and punishes engines that bury correct results deep in the list.

Python Raw pixels, HOG and a gray histogram

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Raw pixels do very well here, with a precision@1 of 0.995, and HOG trails slightly. The gray histogram sits near chance (0.10), as predicted: it cannot tell a 1 from an 8 if they have the same amount of ink. Raw pixels win on this tiny, perfectly centered dataset because every digit is aligned with every other, so pixelwise comparison is exactly right. An 8 by 8 image is also too small to give HOG much to work with (a 2 by 2 cell sees only four pixels). What matters is the next experiment.

Robustness: when the query is shifted

Real queries are never perfectly aligned. We repeat the evaluation with every query image moved one pixel to the right (the database stays unchanged). A good descriptor should shrug this off, because a one-pixel move does not change what the digit is.

Python Searching with shifted queries

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

A one-pixel move is enough to drop raw-pixel precision@10 from 0.963 to 0.551, because the pixelwise distance suddenly compares each stroke with the empty spot next to it. HOG falls less (to 0.612), since its cells summarize orientation over small neighbourhoods rather than exact positions. Larger cells would be more tolerant still, at the cost of discrimination; this is the basic trade-off of hand-made descriptors, and why the field moved on to features learned by neural networks (see Transfer Learning and Modern Vision Models) whose vectors stay stable under shifts, lighting changes and small rotations.

Practical notes

  • Normalize features. Histograms sum to 1 and HOG has unit length, so no image dominates the distances because it is bigger or brighter. With mixed features, scale each part before concatenating.
  • Report several numbers. P@1 says whether the very first result is right, P@10 matches a screen of results, and MAP reflects the whole ranking. Look at the failures too: the field versus lake confusion above would not have been found by a single average.
  • Evaluate fairly. Queries must not be in the database (otherwise each finds itself at distance zero), and the database should not contain near-duplicates of the queries, the leakage trap from Evaluating Vision Models.
  • Scale. Brute-force search over millions of vectors is slow. Production systems use approximate nearest-neighbour indexes (libraries such as FAISS, or vector databases) that trade a little accuracy for large speedups.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. Why does a global color histogram confuse a 'field' (blue sky above green grass) with a 'lake' (green trees above blue water)?

    A histogram only records how many pixels fall in each color bin. Swapping top and bottom does not change those counts at all. A spatial grid of histograms keeps that layout.
  2. 2. What does precision@10 measure for a query?

    Retrieve the 10 closest items, count how many share the query's category and divide by 10.
  3. 3. Why must the query image be processed with exactly the same feature extraction as the database images?

    Distances only make sense between vectors computed in the same way: the same bins, cells, normalization and image size.
  4. 4. Raw pixels beat HOG on aligned digits but lose after a one-pixel shift. What does this show?

    A one-pixel move shifts every stroke onto previously empty pixels, which wrecks the pixelwise distance. HOG cells pool gradients locally, so the descriptor changes less.
  5. 5. For one query, what does average precision (AP) average?

    AP walks through the ranked list and, at every relevant item, records the precision so far; correct results ranked early raise the average. MAP is the mean of AP over all queries.

Summary

  • Image search is feature extraction plus nearest-neighbour ranking. The query must use the same extraction as the database.
  • A color histogram finds images of similar color but ignores layout. Histograms of image regions (a grid) bring layout back at the price of longer vectors.
  • For shapes, gradient-orientation features such as HOG describe strokes; a gray-level histogram carries almost no shape information and performs at chance.
  • Evaluate with held-out queries and several measures: precision@k for the top of the list and MAP for the whole ranking.
  • Always test robustness (shifts, lighting). Hand-made features are fragile, and learned embeddings are the modern answer.

Next project: A Small Photo Filter Toolkit.