K-Reciprocal Reranking

KReciprocalReranker re-orders the candidates a store retrieved for a query with the k-reciprocal encoding of Zhong et al. [1]. Two images are k-reciprocal neighbors when each is among the k1 nearest neighbors of the other, a far stricter relation than merely being close to the query: a false match may lie close to the query, but the query rarely lies close to the false match’s own neighbors. The query and every candidate are encoded into a k-reciprocal feature, a vector over the candidate set that holds a Gaussian weight for each of their k-reciprocal neighbors and zero elsewhere, and the Jaccard distance between the query’s feature and a candidate’s says how much their neighborhoods agree. The candidates are finally re-ranked by (1 - lambda_value) * jaccard + lambda_value * original, where original is the distance the store ranked them by.

The candidates must come from the store that is passed to the reranker, and a store on an ExternalSearchIndex is rejected. For more technical information, visit https://github.com/MechaCritter/Python-Visual-Similarity/blob/main/docs/image_similarity_retrieval/arc42.md.

Example

Tip

See this tutorial for a more detailed walkthrough.

from pyvisim.neural_networks import ClipEmbedder
from pyvisim.retrieval.image_store import InMemoryImageEmbeddingStore
from pyvisim.retrieval.reranking import KReciprocalReranker

store = InMemoryImageEmbeddingStore(gallery_paths, ClipEmbedder(), "hnsw")
store.build_store()
reranker = KReciprocalReranker(store, k1=20, k2=6, lambda_value=0.3)

# Retrieve a pool of candidates, then keep the best five after re-ranking
# Retrieve more candidates than you finally want with the `InMemoryImageEmbeddingStore`,
# at least `k1` and better a few dozen more than `top_k`.
candidates = store.retrieve_top_k_similar(query_image, k=100)[0]
best = reranker.rerank(candidates, top_k=5)

Reranking algorithm

Let the probe \(p\) be the query and \(\mathcal{G} = \{g_i \mid i = 1, 2, \dots, N\}\) are the candidates, so the set the neighborhoods are built over holds \(N + 1\) images.

• Original distance. \(d(p, g_i)\) is the score the store ranked the candidate by, and \(d(g_i, g_j)\) is computed from the candidates’ embeddings in the store’s space. Every row of it is divided by its largest entry (reference implementation), and hence lies in range \([0, 1]\).

• k-nearest neighbors, Eq. (2). The ranking list \(\mathcal{L}(p, \mathcal{G})\) sorts the set by \(d\), and \(N(p, k)\) is its top-\(k\):

  \[N(p, k) = \{g_1^0, g_2^0, \dots, g_k^0\}, \quad |N(p, k)| = k\]

  The ranking list runs over the probe and the candidates together, the image itself at rank zero (reference implementation), and the same definition serves every candidate \(g_i\) in place of \(p\).

• k-reciprocal neighbors, Eq. (3). Only the neighbors that hold \(p\) among their own \(k\) nearest neighbors are kept:

  \[\mathcal{R}(p, k) = \{g_i \mid (g_i \in N(p, k)) \wedge (p \in N(g_i, k))\}\]

• Expansion, Eq. (4). With \(k = k_1\), every member \(q\) of \(\mathcal{R}(p, k)\) brings its own \(\tfrac{1}{2}k\)-reciprocal neighbors in, provided at least two thirds of them already lie in \(\mathcal{R}(p, k)\):

  \[\mathcal{R}^*(p, k) \leftarrow \mathcal{R}(p, k) \cup \mathcal{R}(q, \tfrac{1}{2}k) \quad \text{s.t.} \quad |\mathcal{R}(p, k) \cap \mathcal{R}(q, \tfrac{1}{2}k)| \geq \tfrac{2}{3} |\mathcal{R}(q, \tfrac{1}{2}k)|, \quad \forall q \in \mathcal{R}(p, k)\]

• k-reciprocal feature, Eq. (7). Each image is encoded into a vector over the set, a Gaussian kernel of the original distance on its expanded neighborhood and zero elsewhere:

  \[\begin{split}\mathcal{V}_{p, g_i} = \begin{cases} e^{-d(p, g_i)} & \text{if } g_i \in \mathcal{R}^*(p, k_1) \\ 0 & \text{otherwise} \end{cases}\end{split}\]

  Each vector is scaled to unit \(L_1\) norm (reference implementation), so the Jaccard distance below compares the shape of two neighborhoods rather than their size.

• Local query expansion, Eq. (11). The feature of every image is replaced by the mean feature of its \(k_2\) nearest neighbors, the image itself included (reference implementation). k2=1 skips this step.

  \[\mathcal{V}_p = \frac{1}{|N(p, k_2)|} \sum_{g_i \in N(p, k_2)} \mathcal{V}_{g_i}\]

• Jaccard distance, Eq. (10). The overlap of two neighborhoods is read off their features with the element-wise minimum and maximum:

  \[d_J(p, g_i) = 1 - \frac{\sum_{j=1}^{N} \min(\mathcal{V}_{p, g_j}, \mathcal{V}_{g_i, g_j})} {\sum_{j=1}^{N} \max(\mathcal{V}_{p, g_j}, \mathcal{V}_{g_i, g_j})}\]

• Final distance, Eq. (12). The Jaccard distance is mixed with the original one, and the candidates are sorted by it in ascending order. rerank returns the first top_k of them, each scored by its \(d^*\):

  \[d^*(p, g_i) = (1 - \lambda) \, d_J(p, g_i) + \lambda \, d(p, g_i)\]

Benchmark: Use the ClipEmbedder for retrieval on the Oxford Flower dataset

Important

The numbers in this section were produced by scripts/benchmark_reranking.py. Do not edit this section manually.

All 6149 images of the Oxford Flower dataset (train split) are embedded by ClipEmbedder("ViT-B-32", "openai") into an InMemoryImageEmbeddingStore on the hnsw index, and the 1020 images of the test split are the queries. A result is relevant when it shows the query’s flower category. Every configuration returns the top 100 results of a query: recall@k is the share of queries with a relevant image among the first k results, mAP@100 the mean average precision over the top 100 (normalised by the relevant images a query can reach within them), and MRR the mean reciprocal rank of the first relevant result. The hyperparameters were picked on the validation split, and the re-ranking works on a pool of the top 200 candidates of the expanded query. The time per query includes the embedding of the query image on the GPU.

Configuration	Recall@1	Recall@5	mAP@100	MRR	Time per query
Plain retrieval	90.3%	97.1%	55.6%	93.5%	4.3 ms
Alpha query expansion (expansion_alpha=0, expansion_neighbors=5)	87.8%	94.7%	62.4%	90.6%	4.3 ms
Alpha query expansion and k-reciprocal re-ranking (k1=40, k2=6, lambda_value=0.1)	88.8%	91.8%	73.1%	90.5%	18.7 ms

The precision-recall curves interpolate the precision of every query at fixed recall levels (the best precision at that recall or beyond) and average it over the queries. The recall is relative to the relevant images a query can reach within the top 100.

Benchmark precision-recall curves

References

[1] Z. Zhong, L. Zheng, D. Cao, and S. Li, “Re-ranking Person Re-identification with k-reciprocal Encoding,” in Proc. CVPR, pp. 1318-1327, 2017.

API reference

class pyvisim.retrieval.reranking.KReciprocalReranker(store, *, k1=20, k2=6, lambda_value=0.3)

Bases: object

Re-rank retrieval candidates with k-reciprocal encoding.

For more information, see the documentation: https://mechacritter.github.io/Python-Visual-Similarity/image_similarity_retrieval/reranking/k_reciprocal_reranker/k_reciprocal_reranker.html.

Parameters:

• store (InMemoryImageEmbeddingStore) – The store the candidates were retrieved from.

• k1 (int) – Size of the neighborhoods the k-reciprocal sets are built from. [1] uses 20.

• k2 (int) – Size of the neighborhood the local query expansion averages the k-reciprocal features over. 1 turns the expansion off. [1] uses 6.

• lambda_value (float) – Weight of the original distance in the final distance, from 0 (Jaccard distance only) to 1 (original ranking kept). [1] uses 0.3.

Raises:

• TypeError – If store is not an InMemoryImageEmbeddingStore.

• ValueError – If the store searches through an external index, k1 or k2 is not a positive integer, k2 exceeds k1, or lambda_value lies outside [0, 1].

References:

[1] Z. Zhong, L. Zheng, D. Cao, and S. Li, “Re-ranking Person

Re-identification with k-reciprocal Encoding,” in Proc. CVPR, pp. 1318-1327, 2017.

rerank(candidates, top_k)

Re-rank the candidates of one query and return the best top_k.

The candidates are the ranked matches of a single query, as one row of retrieve_top_k_similar() returns them, and their scores are the query’s distances to them. The neighborhoods are built among the candidates themselves, so a pool no larger than the answer leaves them nothing to say: retrieve at least k1 candidates and a few dozen more than top_k. Neighborhood sizes beyond the number of candidates are capped at it.

Parameters:

• candidates (Sequence[Candidate]) – The ranked matches of one query, at least one, no path twice.

• top_k (int) – Number of best re-ranked candidates to return. More than there are candidates returns them all.

Returns:

The top_k best candidates, best first, each scored by the final distance of Eq. (12) of [1], which lies in [0, 1] and is lower for a better match.

Raises:

• TypeError – If an element of candidates is not a Candidate.

• ValueError – If candidates is empty, names a path twice or one the store does not hold, a score is not finite, or top_k is not a positive integer.

Return type:

list[Candidate]

property k1: int

Size of the neighborhoods the k-reciprocal sets are built from.

property k2: int

Size of the neighborhood of the local query expansion.

property lambda_value: float

Weight of the original distance in the final distance.

property store: InMemoryImageEmbeddingStore

The store the candidates are read back from.