Using Vocabulary Trees for Large Dataset Matching

Spatial pairing handles most of a survey and misses the pairs that matter most structurally: the loop closure where a corridor flight returns near its start, the cross-line tie on a survey whose positions are slightly wrong, and every pair on a dataset with no positions at all.

Those need a way to ask “which images look like this one” without comparing it against every other, and a vocabulary tree is the standard answer. It reduces each image to a compact signature and retrieves similar ones in logarithmic time, turning an intractable comparison into an index lookup. This page covers building one, using it well, and the cases where appearance similarity actively misleads. It complements the position-based approach in building an image pair graph from GPS positions.

How the retrieval works

Every image produces thousands of feature descriptors. A vocabulary tree clusters a large sample of descriptors — from a representative dataset, not necessarily the one being processed — into a hierarchy of visual words, so any descriptor can be assigned to a leaf by a few comparisons rather than by searching everything.

An image is then a histogram over those words: a compact vector saying which visual patterns it contains and how often. Two images of the same ground share many words; two images of different ground share few. Retrieval is a similarity search over those vectors, which is fast.

The weighting matters. Words that appear in almost every image — the texture of grass, the edges of a field — carry no information about identity, and words that appear rarely carry a great deal. Weighting each word by the inverse of how often it appears is what makes the scores discriminate rather than simply rank by texture density.

From descriptors to a retrievable image signature A four-stage pipeline. An image produces thousands of feature descriptors. Each descriptor is assigned to a leaf of a vocabulary tree by a handful of comparisons rather than an exhaustive search. The counts per leaf form a histogram over visual words. The histogram is weighted by inverse document frequency so that common words contribute little and rare ones contribute much, producing a signature that can be compared against every other image in logarithmic time. A note records that the weighting is what makes the scores discriminate rather than rank by texture density. descriptors a few thousand per image tree assignment a few comparisons each word histogram counts per visual word weighted signature rare words weighted up why the weighting matters grass texture appears in every frame and identifies nothing a particular roof pattern appears in six and identifies them Without it, the top-ranked matches are simply the most textured images in the survey.

Figure 1 — The pipeline, and the weighting step that makes it useful.

Minimal reproducible solution

import numpy as np
from sklearn.cluster import MiniBatchKMeans


class VocabularyIndex:
    """A flat visual vocabulary with inverse-document-frequency weighting.

    A flat vocabulary is simpler than a tree and adequate to tens of
    thousands of images; the tree's advantage appears at a scale a single
    drone survey does not reach.
    """

    def __init__(self, n_words: int = 4096, seed: int = 0):
        self.n_words = n_words
        self._kmeans = MiniBatchKMeans(n_clusters=n_words, random_state=seed,
                                       batch_size=4096, n_init=3)
        self._idf: np.ndarray | None = None
        self._signatures: np.ndarray | None = None

    def fit(self, descriptor_sample: np.ndarray) -> "VocabularyIndex":
        """Learn the vocabulary from a sample of descriptors."""
        self._kmeans.fit(descriptor_sample.astype(np.float32))
        return self

    def index(self, per_image_descriptors: list[np.ndarray]) -> "VocabularyIndex":
        """Build weighted signatures for every image in the survey."""
        counts = np.zeros((len(per_image_descriptors), self.n_words), dtype=np.float32)
        for i, desc in enumerate(per_image_descriptors):
            if desc is None or len(desc) == 0:
                continue
            words = self._kmeans.predict(desc.astype(np.float32))
            np.add.at(counts[i], words, 1.0)

        document_freq = (counts > 0).sum(axis=0)
        self._idf = np.log(len(counts) / np.maximum(document_freq, 1)).astype(np.float32)

        weighted = counts * self._idf
        norms = np.linalg.norm(weighted, axis=1, keepdims=True)
        self._signatures = weighted / np.maximum(norms, 1e-9)
        return self

    def query(self, image_index: int, *, top_k: int = 30) -> list[tuple[int, float]]:
        """Most similar images to the given one, by cosine similarity."""
        scores = self._signatures @ self._signatures[image_index]
        scores[image_index] = -1.0
        order = np.argsort(-scores)[:top_k]
        return [(int(i), float(scores[i])) for i in order]

Normalising the weighted histograms to unit length before comparison is what makes the similarity a cosine rather than a dot product, and it removes the bias toward images with many features. Without it, a frame over a rocky outcrop ranks highly against everything.

Where appearance similarity misleads

Two situations produce high similarity between images that share no ground, and both are common in survey work.

Repetitive structure. A solar farm, an orchard, a car park of identical bays. Every frame looks like every other frame, so the retrieval returns high scores across the whole site and the candidate list is noise.

Uniform texture. Bare soil, water, mown grass. The signatures are nearly identical because there is nothing to distinguish them, and the top-ranked candidates are effectively random.

Both are detectable from the score distribution rather than from the images. A healthy retrieval has a small number of high scores and a long tail of low ones; a degenerate one has a flat distribution.

import numpy as np


def retrieval_quality(scores: list[float], *, top_k: int = 30) -> dict:
    """Is this retrieval discriminating, or returning noise?

    A discriminating retrieval has a sharp drop between the best candidates
    and the rest. A flat distribution means the imagery is repetitive or
    textureless and the candidates should not be trusted.
    """
    s = np.sort(np.asarray(scores, dtype=float))[::-1][:top_k]
    if s.size < 5:
        return {"note": "too few candidates to judge"}
    contrast = float(s[0] - s[4]) / max(float(s[0]), 1e-9)
    return {"best": float(s[0]), "fifth": float(s[4]),
            "contrast": contrast,
            "discriminating": contrast > 0.15,
            "note": ("candidates are well separated" if contrast > 0.15 else
                     "scores are flat — repetitive or textureless imagery; rely on "
                     "position and sequence instead")}
What a vocabulary tree does, in three steps Three rows. Building the tree clusters a sample of descriptors from the dataset into a hierarchy, so that any descriptor can be assigned to a leaf by a handful of comparisons rather than by searching every other descriptor. Describing each image as a weighted histogram over those leaves reduces an image to a compact vector, with rare leaves weighted more heavily because they are more distinctive. Querying then ranks all images by histogram similarity, which is a cheap operation, and only the top-ranked candidates are matched properly. build the tree cluster sampled descriptors into a hierarchy — a leaf in a few comparisons describe each image a weighted histogram over leaves; rare leaves weigh more query and rank cheap similarity over histograms; only top candidates are matched properly The tree never decides a match. It decides which pairs are worth the cost of deciding.

Figure 3 — Three steps, and the expensive matcher still makes every actual decision.

Edge-case matrix

Situation Effect Handling
No positions at all Appearance is the only strategy Use it, with more candidates per image
Repetitive structure Flat score distribution Fall back to position and sequence
Uniform texture Random candidates Same; detect from the contrast
Vocabulary from a different scene Poor discrimination Train on representative imagery
Too few words Everything matches everything 4 000–10 000 for a survey
Too many words Nothing matches anything Descriptors of the same point land in different words
Loop closure present High score across a long time gap Exactly what this is for
Very large survey Signature comparison itself is quadratic Use an approximate index

The vocabulary-source row is worth a note. A vocabulary trained on the survey being processed is convenient and slightly circular; one trained on a representative but different dataset generalises better and can be reused across jobs. For a fleet flying similar terrain, training once and reusing is both faster and more stable.

Verification snippet

import numpy as np


def verify_candidates(candidates: dict[int, list[tuple[int, float]]],
                      positions_enu: np.ndarray, radius_m: float) -> dict:
    """What do the appearance candidates add beyond what position already found?

    The valuable ones are the distant pairs: near pairs were already covered
    by spatial matching, so a retrieval that returns only near neighbours has
    contributed nothing.
    """
    added_far = 0
    total = 0
    distances = []
    for i, ranked in candidates.items():
        for j, _score in ranked:
            total += 1
            d = float(np.linalg.norm(positions_enu[i, :2] - positions_enu[j, :2]))
            distances.append(d)
            if d > radius_m:
                added_far += 1

    return {"candidates": total,
            "beyond_spatial_radius": added_far,
            "fraction_new": added_far / max(total, 1),
            "median_distance_m": float(np.median(distances)) if distances else 0.0,
            "useful": added_far > 0.1 * max(total, 1),
            "note": ("the retrieval is finding pairs position missed" if added_far else
                     "all candidates were already within the spatial radius")}
Score distribution for a discriminating and a degenerate retrieval Two curves of similarity score against candidate rank for a single query image. The discriminating case starts at zero point seven eight for the best candidate and falls steeply to zero point two by the tenth, giving clear separation. The degenerate case, over a solar farm, starts at zero point four one and is still at zero point three eight by the thirtieth candidate, a nearly flat line. A note states that the flatness is detectable without looking at any imagery and is the signal to fall back on position and sequence. 15 102030 candidate rank similarity discriminating — steep drop solar farm — flat Detectable from the scores alone, without looking at a single image.

Figure 2 — The shape that decides whether to trust the candidates.

Combining with position sensibly

The two strategies are complementary and the combination should reflect that: position provides the bulk coverage cheaply, and appearance adds the pairs position cannot know about.

A practical arrangement takes all spatial pairs, all sequential pairs, and the top-ranked appearance candidates that lie beyond the spatial radius. Filtering the appearance candidates that way avoids paying twice for pairs already covered and concentrates the extra matching effort where it adds structure.

def combine_with_position(spatial: set, sequential: set,
                          candidates: dict, positions_enu, radius_m: float,
                          *, per_image: int = 12) -> set:
    """Add only the appearance candidates that position could not have found."""
    import numpy as np
    extra = set()
    for i, ranked in candidates.items():
        added = 0
        for j, _ in ranked:
            if added >= per_image:
                break
            d = float(np.linalg.norm(positions_enu[i, :2] - positions_enu[j, :2]))
            if d > radius_m:
                extra.add((min(i, j), max(i, j)))
                added += 1
    return spatial | sequential | extra

When to escalate

  • The retrieval is degenerate across the whole survey. The imagery is repetitive or textureless. Position and sequence are the only viable strategies, and the reconstruction will depend heavily on them.
  • Loop closures are known to exist and are not retrieved. The vocabulary may be poorly suited. Try one trained on similar terrain before adjusting parameters.
  • The signature comparison itself is the bottleneck. At tens of thousands of images, replace the exhaustive cosine comparison with an approximate nearest-neighbour index.

← Matching Strategies for Large and Linear Surveys