wikillm

Paper · 2025-08-25 · cs.CV

HotSpotter - Patterned Species Instance Recognition

Identifies individual animals with patterned coats by matching affine keypoints ("hotspots") and SIFT-style descriptors against a labelled database. One-vs-one scores each database image with a ratio test and spatial check; one-vs-many searches all database descriptors with k-d trees and LNBNN-style scores. Author-reported: 95% top-1 on Grevy's zebras, over 99% on plains zebras.

Local feature matchingNearest-neighbor searchanimal-identificationinstance-recognitionlocal-featuresnearest-neighbour-search

arXivPDFCodeMarkdown16 min read

AI-compiled by claude-haiku-5-5 on 2026-11-12, not yet reviewed by a human. Every claim cites its source; check it when a detail matters.

In plain words

Researchers who study animal populations need to know which individual animal appears in each photo. Zebras, giraffes and similar animals carry markings that differ from one individual to the next. This method looks for small, distinctive points in the photo, which the paper calls hotspots, and describes each one by a short list of numbers. A new photo is then compared against a labelled set of photos, and the animals whose spots match best are ranked first.

The paper offers two ways to do the comparison. The first takes the new photo and checks it against each labelled photo in turn, then keeps only spots that line up in a consistent geometric way. The second puts the spots from every labelled photo into one searchable index and asks, for each spot in the new photo, which stored spots are closest. Both then add up the evidence per animal. The second approach is much faster, and the authors report it is about as accurate. A person still draws a box around the animal and checks the final answer.

TL;DR

Patterned-animal re-identification by local keypoint matching. Each query is a user-drawn box around one animal, matched against a static labelled database. The one-vs-many variant trades per-image comparison for one nearest-neighbour index and a LNBNN-derived score, which the authors report as faster at similar accuracy on zebras tab. 2 tab. 3. Results are author-reported on five species, mostly zebras.

Problem

Photo-based identification of individual animals has to compare a new image with a database of previously identified individuals, and manual comparison does not scale §1. The task is to rank labelled animals for a query image and a user-drawn region of interest, not to make a final decision §1. The method assumes the database is static for the experiments, that all images show the same flank of each animal, and that a human confirms the result §1. Earlier species-specific or Wild-ID-style approaches are the comparison points §2.

Method

Overview. Both variants share five steps: preprocessing, matching, image scoring, spatial reranking and label scoring §3. The one-vs-many variant changes only the index and the matching step §4.

  1. Preprocessing §3.1. Crop each image to the user-drawn region of interest and resize it, keeping the aspect ratio. Detect Hessian-type spatial and scale extrema, fit an elliptical affine region to each, and set the orientation to zero by assuming the gravity direction points down in every image. Compute a 128-dimensional RootSIFT descriptor (the element-wise square root of a SIFT vector) for each region §3.1.
  2. Index §3.1 §4.1. One-vs-one builds a k-d tree forest over the query descriptors only. One-vs-many builds one forest over all database descriptors and none for the query.
  3. Matching, one-vs-one §3.2. For each database descriptor, find its two nearest query descriptors with an approximate, prioritised search. Keep the correspondence only when the ratio of the squared distances to the second and first neighbour exceeds a threshold eq. 1.
  4. Initial image score §3.3. Sum the ratios of all kept matches for that image eq. 2.
  5. Spatial reranking §3.4. For the 50 images with the highest initial score, keep matches that agree with a single geometric transform. Each match defines an affine map from its two region shapes. A correspondence is an inlier when the projected query point lies within a threshold of its database partner. The largest inlier set gives a final homography, and the image is rescored with the matches that agree with it.
  6. Label scoring §3.5. Score each name in one of two ways. Image scoring takes the best reranked image of that name. Label scoring pools the matches of all reranked images with that name, keeps one best match per query descriptor, and applies the same sum as in step 4.
  7. One-vs-many matching §4.2. For each query descriptor, retrieve its k+1 approximate nearest database descriptors, ordered by distance. Score the first k of them against a normalising distance, taken from the k+1 st neighbour, with both distances squared. Matches beyond the first k get no score. Each score is credited to the database image that owns the descriptor. The four scoring rules are listed below.
  8. Large databases §4.3. The paper also tests product quantisation in place of the k-d forest, with 16 sub-vectors of length 8 and 128 codewords each.

Key equations:

r_{i,j} = \frac{\lVert d_i - q_{j_2} \rVert^2}{\lVert d_i - q_j \rVert^2} eq. 1

\mathrm{Sim}(\mathcal{M}_D) = \sum_{(i,j,r_{i,j}) \in \mathcal{M}_D} r_{i,j} eq. 2

\delta_{\mathrm{LNBNN}} = \lVert d_{k+1} - q \rVert^2 - \lVert d_p - q \rVert^2 eq. 3

\delta_{\mathrm{ratio}} = \frac{\lVert d_{k+1} - q \rVert^2}{\lVert d_p - q \rVert^2} eq. 4

\delta_{\mathrm{lnrat}} = \ln\!\left(\frac{\lVert d_{k+1} - q \rVert^2}{\lVert d_p - q \rVert^2}\right) eq. 5

\delta_{\mathrm{count}} = 1 eq. 6

Pseudocode for the one-vs-one path §3.1 §3.2 §3.3 §3.4 §3.5:

Pseudocode
# Query side only: k-d forest over the query descriptors  [§3.1]
query_forest = build_kdtree_forest(query_descriptors)

# For each database descriptor, find its two nearest query descriptors
# with an approximate, prioritised search  [§3.2]
def one_vs_one_matches(db_descriptors, query_forest, query_descriptors):
    matches = []
    for i, d in enumerate(db_descriptors):
        j, j2 = two_nearest(query_forest, d)
        # Ratio of squared distances to second and first neighbour  [eq. 1]
        r = (squared_dist(d, query_descriptors[j2])
             / squared_dist(d, query_descriptors[j]))
        # Keep the correspondence only above the ratio threshold  [§3.2]
        if r > T_RATIO:
            matches.append((i, j, r))
    return matches

# Initial image score: sum of kept ratios  [§3.3] [eq. 2]
def initial_score(matches):
    return sum(r for (_, _, r) in matches)

# Spatial reranking of the 50 best images by initial score  [§3.4]
def spatial_rerank(matches, db_shapes, query_shapes, t_sp):
    # Each match defines an affine map from its two region shapes  [§3.4]
    hyps = [affine_from_match(m, db_shapes, query_shapes) for m in matches]
    # Largest set of matches whose projected points land within t_sp  [§3.4]
    inliers = largest_inlier_set(matches, hyps, t_sp)
    # Final homography from the inliers; keep matches that agree with it  [§3.4]
    final = fit_homography(inliers)
    kept = [m for m in matches if reprojection_error(final, m) < t_sp]
    return initial_score(kept)

# Label scoring: pool reranked matches of all images with one name  [§3.5]
def label_score(label, reranked_by_label):
    pooled = []
    for image_matches in reranked_by_label[label]:
        pooled.extend(image_matches)
    # Keep one best match per query descriptor before summing  [§3.5]
    best = best_per_query_descriptor(pooled)
    return initial_score(best)

Pseudocode for the one-vs-many path §4.1 §4.2:

Pseudocode
# One forest over ALL database descriptors; no query index  [§4.1]
db_forest = build_kdtree_forest(all_db_descriptors)

# Each query descriptor gets k+1 approximate neighbours  [§4.2]
def one_vs_many_matches(q_desc, db_forest, k, delta):
    scores = []
    for j, q in enumerate(q_desc):
        nbrs = approx_knn(db_forest, q, k + 1)  # sorted by distance
        # The (k+1)-th neighbour is the normaliser  [§4.2]
        d_norm = squared_dist(q, nbrs[k])
        for p in range(k):
            d_p = squared_dist(q, nbrs[p])
            # Credit the image that owns this database descriptor  [§4.2]
            owner = image_of(nbrs[p])
            scores.append((owner, nbrs[p], j, delta(d_norm, d_p)))
    return scores

# LNBNN, maximised: difference of squared distances  [§4.2] [eq. 3]
def delta_lnbnn(d_norm, d_p):
    return d_norm - d_p

# Ratio of the same two squared distances  [§4.2] [eq. 4]
def delta_ratio(d_norm, d_p):
    return d_norm / d_p

# Logarithm of that ratio  [§4.2] [eq. 5]
def delta_lnrat(d_norm, d_p):
    return log(d_norm / d_p)

# Match counting: each match scores 1  [§4.2] [eq. 6]
def delta_count(d_norm, d_p):
    return 1

Implementation notes that the paper states:

  • Scores from one-vs-many are then passed through the same image scoring, spatial reranking and label scoring as one-vs-one §4.2.
  • The product-quantised variant stores database vectors as codes, not raw descriptors, and the paper says the codes are 16 times smaller than the forest §4.3. The paper does not say how that size was counted.

Hyperparameters

Values marked "not stated" are absent from the paper. The code column is what the public repository uses by default, which is a later Python port and not the MATLAB code the paper reports §5.

NameValueWhereNotes
Keypoint detectorHessian-type extrema with elliptical affine region§3.1Code uses an affine-shape detector called hesaff with a parameter set pyhesaff.py
DescriptorRootSIFT, 128-dim§3.1Not visible in the Python code; the hesaff C source is not in the repo, so unverified
Orientation θ0 for all regions§3.1Gravity assumption; the importer writes θ = 0 convert_db.py
ROI resize targetnot stated§3.1Code default: square-root area 450, aspect kept Config.py
k-d forest treesnot stated§3.1 §4.1Code: 4 trees DataStructures.py
Search checksnot stated§3.2 §4.2Code: 1024 default Config.py; 256 for one-vs-one Config.py; 128 in a params file params.py
Ratio threshold t_ratio1.6² on squared distances§3.2 eq. 1Code default 1.5, applied to the ratio directly Config.py; a test script uses 1.6 vsone_test.py
Neighbours k1, 5, 10, 20 tested; default not statedtab. 2 tab. 3Code default K = 4 Config.py; one-vs-one K = 1 Config.py
Normaliser(k+1)-th neighbour§4.2Code: Knorm = 1 Config.py
Spatial threshold t_sp10% of the diagonal of the database image§3.4Code: 0.1 times the diagonal of the matched keypoints, not the image, unless a flag is set Config.py matching_functions.py; see Pitfalls
Reranked images K_SR50§3.4Code: nShortlist = 50 Config.py
Minimum inliersnot stated§3.4Code: 4 Config.py
RANSAC iterations and sample sizenot stated§3.4Code uses no RANSAC; see Paper vs code
Scale gate on inliersnot in paper—Code keeps determinant ratio between 0.5 and 2 Config.py spatial_verification2.py
Product quantisation16 sub-vectors of length 8, 128 codewords each§4.3Not in the released code
Hardware and timingMATLAB on i7-2600K, 3.4 GHz§5Times in tab. 2 to tab. 4 are seconds per query on that setup
Ground truthcorrected during the study§5.2Exact accuracy depends on the corrected labels; release of the data is not stated

Results

Author-reported. Setup: five datasets from field teams in Kenya and elsewhere §5; baselines are Wild-ID for the small sets and the one-vs-one variant for the large zebra sets §5.3 tab. 4. Every database image with a known match is used as a query, with self-matches ignored §5.2.

Dataset statistics tab. 1:

SpeciesImagesLabelsMean descriptors per image
Grevy's zebra1047592837.6
Plains zebra82486403.6
Jaguar45212660.5
Giraffe45151418.3
Lionfish1351183.3

Grevy's zebra, 657 queries tab. 2. Columns: "not first" means the correct name is not ranked first, "not in top 5" means it is not in the top five. The label columns use label scoring, the image columns use image scoring §3.5. Time is seconds per query.

ConfigkδLabel not firstImage not firstLabel not in top 5Image not in top 5Sec/query
1v1+R01ratio332511878.8
1v11ratio26246772.2
1vM1ratio3336854.0
1vM1lnrat3234654.0
1vM1count2728793.9
1vM1LNBNN4047894.0
1vM+PQ1LNBNN15217392925.6
1vM5ratio3734563.4
1vM5lnrat3433553.8
1vM5count3236773.6
1vM5LNBNN3941453.7
1vM+PQ5LNBNN414913134.5
1vM10ratio3835663.5
1vM10lnrat3333453.8
1vM10count3236873.7
1vM10LNBNN3941454.0
1vM+PQ10LNBNN435114164.5
1vM20ratio3836663.4
1vM20lnrat3231553.7
1vM20count3236873.6
1vM20LNBNN3841663.8
1vM+PQ20LNBNN435115164.6
1vM+S1lnrat3335673.8
1vM+S1LNBNN4045773.7
1vM+R01lnrat3436751.5
1vM+RA1lnrat32346544.6

Plains zebra, 819 queries tab. 3, same columns:

ConfigkδLabel not firstImage not firstLabel not in top 5Image not in top 5Sec/query
1v1+R01ratio955341.0
1v11ratio743338.2
1vM1ratio62322.6
1vM1lnrat74212.6
1vM1count63222.6
1vM1LNBNN65112.5
1vM+PQ1LNBNN252915152.7
1vM5ratio73322.2
1vM5lnrat53222.3
1vM5count84322.4
1vM5LNBNN63222.6
1vM+PQ5LNBNN77343.1
1vM10ratio73322.3
1vM10lnrat73322.2
1vM10count84322.5
1vM10LNBNN73222.4
1vM+PQ10LNBNN77233.3
1vM20ratio73322.3
1vM20lnrat73322.2
1vM20count84322.5
1vM20LNBNN75322.6
1vM+PQ20LNBNN76233.3
1vM+S1lnrat74322.4
1vM+S1LNBNN66222.5
1vM+R01lnrat75430.7
1vM+RA1lnrat643230.4

Giraffe (38 queries), jaguar (35) and lionfish (13) tab. 4. Wild-ID has no label-scoring column in the source.

DatasetConfigkδLabel not firstImage not firstLabel not in top 5Image not in top 5Sec/query
Giraffe1v1+RA1ratio10103.3
Giraffe1vM+RA1ratio10001.1
GiraffeWild-ID———4—10.5
Jaguar1v1+RA1ratio10006.2
Jaguar1vM+RA1ratio10002.0
JaguarWild-ID———3—22.6
Lionfish1v1+RA1ratio00000.7
Lionfish1vM+RA1ratio00000.7
LionfishWild-ID———1—01.5

Headline numbers, as reported by the authors §5.3: about 95% of Grevy's queries correct at top-1 and 98% in the top five; over 99% for plains zebras; perfect results on giraffes, jaguars and lionfish. The table counts agree with the first two figures for the one-vs-many, k = 5, count row: 32 of 657 not first (95.1% correct) and 7 not in the top five (98.9%). The plains figure holds only for the better rows; the product-quantised k = 1 row has 25 top-1 misses of 819. The "perfect" claim does not match tab. 4 for giraffes and jaguars, which each have one label-scoring top-1 miss (see Pitfalls).

Failure analysis §5.4 fig. 3: of the 34 Grevy's queries that the one-vs-many, k = 5, lnrat configuration ranks below first, 2 come from mislabelled database images, 5 from a query box covering two animals, 13 from matches on background scenery, 8 from large pose differences, and 6 from image quality (focus, resolution, contrast). The 6 is the remainder of the paper's counts. Figures: fig. 1 shows a query and ranked results with matching regions; fig. 2 shows correct matches for five species, with Wild-ID failing on two of them §5.1.

Table numbering follows the pdfLaTeX build. In the source, the plains and giraffe/jaguar/lionfish tables sit in an \ifxetex conditional.

Paper vs code

Repository: https://github.com/Erotemic/hotspotter at code_commit 926c0a143a89fc9cea1dcdb485ec3adf3e600017, Apache-2.0 LICENSE.txt. The owner's profile shows the name Jon Crall and Kitware [GitHub profile], and the repository ships a copy of the WACV 2013 paper as crall-hotspotter-wacv-2013.pdf, so it is treated as the authors' code. The paper's MATLAB code is not in the repository; this is a later Python port with a C extension whose source is absent. Discrepancies, each with both citations:

  • Spatial verification is not RANSAC. The paper describes a standard RANSAC solution §3.4. The code tries every match as an affine hypothesis, keeps the one with the most inliers, then fits a homography to those inliers by linear least squares with coordinate normalisation spatial_verification2.py spatial_verification2.py. It samples nothing at random.
  • Scale gate. The code also rejects affine hypotheses whose determinant ratio falls outside 0.5 to 2 spatial_verification2.py Config.py. The paper does not mention this gate §3.4.
  • Spatial threshold size. The paper uses 10% of the database image diagonal §3.4. The code uses the bounding box of the matched database keypoints, unless use_chip_extent is set, which it is not by default matching_functions.py Config.py. The 0.1 factor matches Config.py.
  • Log-ratio score. The paper defines the score as the natural log of the distance ratio §4.2 eq. 5. The code computes the log of the ratio plus one, with a small constant added to the denominator nn_filters.py. At a ratio of 1 the paper's score is 0 (the stated purpose), while the code's is about 0.69.
  • Ratio score epsilon. The code's ratio adds 1e-8 to the denominator nn_filters.py, which the paper does not.
  • Count score. The paper's count score (eq. 6) has no counterpart in the code's filter list, which has ratio, LNBNN, log-ratio, round-trip reciprocal, bursty and region-distance filters Config.py.
  • Ratio threshold. The paper uses 1.6² on squared distances §3.2. The default one-vs-one setting is 1.5 Config.py, and the test script uses 1.6 vsone_test.py. The code applies the threshold to FLANN's returned distances without squaring; the repository does not show whether those are squared, so the equivalence is unverified.
  • Normaliser rule. The code has a second normaliser rule that picks the first neighbour whose name differs from the top names nn_filters.py. The paper does not describe it. The default is the (k+1)-th neighbour Config.py Config.py.
  • Forest size and search budget. The paper gives no tree count. The code builds 4 trees DataStructures.py and uses three different search-check defaults in different places (Pitfalls).
  • Chip size. Target size is not stated in the paper. The code uses square-root area 450 Config.py.
  • Product quantisation. The paper tests PQ §4.3. The repository has no quantisation code, so the PQ rows cannot be reproduced from it.
  • RootSIFT. Not checkable in the Python code; the descriptor is computed inside the hesaff binary pyhesaff.py.
  • Matching and scoring, one-vs-many. The k+1 search and per-image credit match the paper matching_functions.py nn_filters.py.
  • Prescore. The shortlist is ranked by summed match weights, as in eq. 2 voting_rules2.py matching_functions.py. Reranking the top 50 matches the paper Config.py.
  • Orientation. The paper's zero-orientation assumption matches the importer, which writes θ = 0 convert_db.py.

Pitfalls

  • "Perfect" on giraffes and jaguars is not what the table shows. tab. 4 gives one label-scoring top-1 miss for giraffes and one for jaguars, in both one-vs-one and one-vs-many. Image scoring has none. Only lionfish is perfect on all columns.
  • Speed claim against Wild-ID. The text claims Wild-ID runs more quickly than the one-vs-one variant §5.3. On lionfish, tab. 4 shows 1.5 s for Wild-ID against 0.7 s for one-vs-one. The authors attribute Wild-ID's speed to multithreading and a Java implementation §5.3.
  • Spatial threshold reference. "Database image diagonal" is ambiguous (before or after the ROI crop and resize), and the code uses matched keypoints (see Paper vs code). Set t_sp from the matched keypoints if you want the code's behaviour.
  • Unstated RANSAC parameters. Iterations, minimal sample size and the inlier stopping rule are not stated. The LaTeX source has two commented-out drafts of the inlier test, one in relative displacements with an unsquared norm and one with a squared norm [raw source: zebra_3_one_against_one.tex lines 104-106, 118-122]. The published text does not say which applies. The code's approach is in Paper vs code.
  • Ratio direction. The paper's ratio is the second-nearest squared distance over the nearest one, and a match is kept when it exceeds the threshold §3.2 eq. 1. That is the inverse of the usual nearest-over-second test, so a threshold copied from that test will keep the wrong matches.
  • Initial score is not normalised. The score sums ratios with no division by the number of features eq. 2. A commented-out note in the LaTeX source asks whether it should be normalised [raw source: zebra_3_one_against_one.tex lines 70-74]. The published text does not answer it, so the score may favour images with many features.
  • "Best match" in label scoring is undefined. The text says to keep the best match per query descriptor §3.5. The direction depends on the scoring rule. A commented-out draft says "highest score" [raw source: zebra_3_one_against_one.tex lines 150-151]. Treat "best" as the highest value of the scoring function used.
  • Division by zero. Eqs. 4 and 5 divide by the nearest-neighbour distance without a guard. The code adds 1e-8 to the denominator in the ratio and log-ratio, which changes values very close to zero nn_filters.py.
  • Affine shape convention. The paper writes the shape as a lower-triangular matrix §3.1. The code stores the inverse shape, with a note in the code spatial_verification2.py. Mixing the two conventions will give wrong transforms.
  • One-vs-many gives no ratio cut-off. Matches beyond the first k get zero score and no threshold is applied §4.2. A one-vs-one threshold does not carry over.
  • Three different search-check defaults. The code uses 1024 for the general neighbour search Config.py, 256 for one-vs-one Config.py and 128 in a params file params.py. The paper does not state a value. Results depend on it, so fix one and record it.
  • Memory cost. One-vs-many keeps every database descriptor in memory, which the paper names as the drawback that PQ addresses §4.3. The 16-times reduction is not explained.
  • Timings are not portable. Times come from MATLAB on one i7-2600K at 3.4 GHz and are seconds per query §5 tab. 2. The Python port is a different implementation.
  • Ground truth changed during the study. The authors fixed several labelling errors while running the experiments §5.2. The paper does not say whether the corrected labels are released, so the exact accuracy cannot be reproduced without them.
  • Failure categories are the authors' own count. The 6 image-quality cases are the remainder after the other counts §5.4. The paper gives no separate method for assigning each failure to a category.
  • Plains claim depends on the row. "Well over 99%" holds for the better rows, not for the product-quantised k = 1 row tab. 3.

Lineage

  • Builds on: Wild-ID, which uses SIFT keypoints with per-image matching and triple-based consistency §2; the ratio test and SIFT §3.2; RootSIFT §3.1; Hessian-affine regions §3.1; LNBNN for the one-vs-many scoring §4.2; product quantisation §4.3. None of these has a card in this wiki.
  • Compared against: Wild-ID on the small datasets tab. 4; one-vs-one matching within the paper tab. 2 tab. 3.
  • Superseded by: not stated.
  • Publication note: the first page footer says the paper was originally published at WACV 2013 (DOI 10.1109/WACV.2013.6475023) [raw source: main.tex lines 43-44]. The arXiv v1 record is dated 2025-08-25.

Source and license

Adapted from “HotSpotter - Patterned Species Instance Recognition” by Jonathan P. Crall, Charles V. Stewart, Tanya Y. Berger-Wolf, Daniel I. Rubenstein, Siva R. Sundaresan (arXiv:2508.17605), used under CC BY 4.0. Changes: condensed and restructured for implementation, with tables, equations and algorithms taken from the paper and its code, each cited to its source. Not affiliated with or endorsed by the authors. Code citations refer to https://github.com/Erotemic/hotspotter at commit 926c0a143a89 (Apache-2.0). Any quoted code is shown under that license.