Search a gallery. More...

Data Structures
struct	roc_candidate
	Reference to a gallery template associated with a similarity to a probe. More...

Typedefs
typedef struct roc_candidate	roc_candidate
	Reference to a gallery template associated with a similarity to a probe. More...

Functions
roc_error	roc_search (roc_const_gallery gallery, const roc_template probe, size_t k, roc_similarity min_similarity, roc_candidate *candidates)
	Ranked search for a probe template against a gallery of templates. More...

roc_error	roc_knn (roc_const_gallery gallery, roc_const_gallery probes, size_t k, roc_similarity min_similarity, roc_candidate *neighbors, roc_progress progress)
	Construct the k-nearest neighbors graph of a gallery. More...

roc_error	roc_knn_and_cluster (roc_gallery gallery, size_t k, roc_similarity min_similarity, bool incremental, roc_progress progress)
	Convenience functon to call both roc_knn and roc_cluster. More...

roc_error	roc_search_persons (roc_const_gallery gallery, roc_const_gallery probes, size_t k, roc_similarity min_similarity, bool one_candidate_per_person_id, bool ignore_identical, roc_candidate *candidates)
	Search with multiple probe templates for the same person. More...

roc_error	roc_rerank (roc_const_gallery gallery, size_t k, roc_candidate *candidates)
	Re-rank roc_search or roc_knn results based on commonly occuring roc_person_id and roc_template_index. More...

roc_error	roc_rank_persons (roc_const_gallery gallery, const roc_template probe, size_t k, roc_person_id person_ids, roc_similarity similarities)
	Order persons by similarity to probe. More...

roc_error	roc_consolidate_candidates (roc_gallery gallery, roc_similarity max_similarity, size_t k, roc_candidate *candidates)
	Downsample a candidate list by removing redundant templates. More...

Detailed Description

Search a gallery.

Retrieve a sorted list of the top candidate templates for a single probe with roc_search or multiple independent probes with roc_knn. Re-order search results based on commonly occuring roc_person_id with roc_rerank.

Data Structure Documentation

◆ roc_candidate

struct roc_candidate

Reference to a gallery template associated with a similarity to a probe.

Retrieve the gallery template using roc_at with roc_candidate::index. Note that roc_candidate::similarity is equal to the similarity returned by roc_compare_templates.

Public Member Functions
	roc_candidate ()
	Default initialize a candidate.

	roc_candidate (const roc_person_id &person_id, const roc_template_id &template_id, roc_template_index index, roc_similarity similarity)
	Initialize a candidate.

bool	operator< (const roc_candidate &other) const
	Sort higher scoring candidates first.

Data Fields
roc_person_id	person_id
	roc_template::person_id of the candidate template in the gallery.

roc_template_id	template_id
	roc_template::template_id of the candidate template in the gallery.

roc_template_index	index
	Index of the candidate template in the gallery.

roc_similarity	similarity
	Similarity of the candidate template to the probe.

Typedef Documentation

◆ roc_candidate

typedef struct roc_candidate roc_candidate

Reference to a gallery template associated with a similarity to a probe.

Retrieve the gallery template using roc_at with roc_candidate::index. Note that roc_candidate::similarity is equal to the similarity returned by roc_compare_templates.

Function Documentation

◆ roc_search()

roc_error roc_search	(	roc_const_gallery	gallery,
		const roc_template	probe,
		size_t	k,
		roc_similarity	min_similarity,
		roc_candidate *	candidates
	)

Ranked search for a probe template against a gallery of templates.

The pre-allocated buffer candidates should be large enough to contain k elements. The candidates will be ordered by decreasing roc_candidate::similarity. In the event that there are fewer than k candidates to return, the trailing elements of candidates will be populated with roc_candidate::index of ROC_INVALID_TEMPLATE_INDEX and roc_candidate::similarity of ROC_INVALID_SIMILARITY.

Note that this function is a special case of roc_knn with a single probe template and is exposed in the Command Line Interface as roc-search.

If you have multiple probes, it is more efficient to call roc_knn once than make repeated calls to roc_search. This is particularly true when gallery is large as the probes will be batched together to minimize reads to main memory.

If the probe roc_template::algorithm_id includes ROC_SERIAL then only one thread will be used to execute the search.

Number of Candidates

The k most similar templates in gallery to probe, ordered by decreasing similarity. The suggested default value for k is 10.

Minimum Similarity

The minimum similarity score required to add a candidate to the candidate list. The suggested default value for min_similarity is 0.

Example: roc_const_gallery gallery = ...;
roc_template probe = ...;
roc_candidate candidates[10];
roc_search(gallery, probe, 10, 0.f, &candidates[0]);

Parameters

[in]	gallery	Gallery to search against.
[in]	probe	Template to search for.
[in]	k	The desired number of candidates, see Number of Candidates.
[in]	min_similarity	The desired minimum similarity of candidates, see Minimum Similarity.
[out]	candidates	Pre-allocated buffer to contain the top matching templates in `gallery`.

Remarks: This function is thread-safe and parallel.

See also: roc_search_persons roc_compare_galleries roc_rerank

◆ roc_knn()

roc_error roc_knn	(	roc_const_gallery	gallery,
		roc_const_gallery	probes,
		size_t	k,
		roc_similarity	min_similarity,
		roc_candidate *	neighbors,
		roc_progress	progress
	)

Construct the k-nearest neighbors graph of a gallery.

The pre-allocated buffer neighbors should be large enough to hold n = k*roc_size (probes) elements. For a roc_template_index p in probes, its i-th nearest neighbor in gallery is g = neighbors[p*k+i].index.

In the common case where gallery == probe, neighbors can be used as the input to roc_cluster.

Search Generalization

This function is a generalized version of roc_search with multiple independent probe templates, as illustrated in the following code snippet.

KNN Speed

Maximum comparison throughput is obtained when gallery size is large and probes size is large and divisible by 4.

roc_const_gallery gallery = ...;
roc_const_gallery probes = ...;
size_t k = ...;
roc_similarity min_similarity = ...;
size_t gallery_size, probes_size;
roc_size(gallery, &gallery_size);
roc_size(probes, &probes_size);
roc_candidate *neighbors = (roc_candidate*) malloc(k * probes_size *
                                                   sizeof(roc_candidate));
// This is identical ...
for (size_t i=0; i<probe_sizes; i++) {
    roc_template t;
    roc_at(probes, i, &t);
    roc_search(gallery, t, k, min_similarity, neighbors + i * k);
    roc_free_template(&t);
}
// ... to this
roc_knn(gallery, probes, k, min_similarity, neighbors);

Nearest Neighbors

The k nearest neighbors to a template are the k most similar templates in gallery to it, ordered by decreasing similarity. The suggested default value for k is 10.

Minimum Similarity

The minimum similarity score required to add a candidate to the nearest neighbors graph. The suggested default value for min_similarity is 0, particularly when neighbors is to be used in a subsequent call to roc_cluster.

Example: roc_const_gallery gallery = ...;
size_t k = ...;
roc_similarity min_similarity = ...;
size_t size;
roc_size(gallery, &size);
roc_candidate *neighbors = (roc_candidate*) malloc(k * size *
sizeof(roc_candidate));
roc_knn(gallery, gallery, k, min_similarity, neighbors);

Parameters

[in]	gallery	The templates from which to find nearest neighbors.
[in]	probes	The templates for which to find nearest neighbors.
[in]	k	The number of nearest neighbors in `gallery` to retain, see Nearest Neighbors.
[in]	min_similarity	The desired minimum similarity of candidates, see Minimum Similarity.
[out]	neighbors	Pre-allocated buffer to store the nearest neighbors of each template in `probes`.
[in]	progress	Optional progress callback or `NULL`.

Remarks: This function is thread-safe and parallel.

See also: roc_search roc_rerank roc_adjudicate_knn

◆ roc_knn_and_cluster()

roc_error roc_knn_and_cluster	(	roc_gallery	gallery,
		size_t	k,
		roc_similarity	min_similarity,
		bool	incremental,
		roc_progress	progress
	)

Convenience functon to call both roc_knn and roc_cluster.

This function will cluster all templates in a given gallery and group similar templates by assigning each group a unique person_id.

Please refer to roc_knn and roc_cluster for more information about their function and detailed definitions of their parameters.

Parameters

[in]	gallery	The templates from which to find nearest neighbors.
[in]	k	The number of nearest neighbors in `gallery` to retain.
[in]	min_similarity	The desired minimum similarity of candidates, see Minimum Similarity.
[in]	incremental	See incremental_clustering.
[in]	progress	Optional progress callback or `NULL`.

Remarks: This function is thread-safe and parallel.

See also: roc_knn roc_cluster

◆ roc_search_persons()

roc_error roc_search_persons	(	roc_const_gallery	gallery,
		roc_const_gallery	probes,
		size_t	k,
		roc_similarity	min_similarity,
		bool	one_candidate_per_person_id,
		bool	ignore_identical,
		roc_candidate *	candidates
	)

Search with multiple probe templates for the same person.

This function is a generalization of roc_search with multiple probe templates all corresponding to the same person. A single candidate list is generated where each roc_candidate::similarity reflects the maximum similarity across all probe templates.

If one_candidate_per_person_id is true, all entries in candidates will correspond to gallery templates with different roc_person_id. Otherwise entries in candidates may correspond to gallery templates with the same roc_person_id, as it would in roc_search. Gallery templates with roc_template::person_id of roc_uuid_get_null() will be considered unique persons.

If ignore_identical is true, similarity scores of ROC_MAX_SIMILARITY (indicating an identical match), or gallery templates with roc_template::person_id matching the probe, will be ignored when constructing candidates. This is useful when probes are in gallery and you want to exclude them from the search results.

Example: roc_const_gallery gallery = ...;
roc_const_gallery probes = ...;
roc_candidate candidates[10];
roc_search(gallery, probes, 10, 0.f, true, true, &candidates[0]);

Parameters

[in]	gallery	Gallery to search against.
[in]	probes	Probe templates belonging to the same person to search for.
[in]	k	The desired number of candidates, see Number of Candidates.
[in]	min_similarity	The desired minimum similarity of candidates, see Minimum Similarity.
[in]	one_candidate_per_person_id	If `true`, all entries in `candidates` will correspond to gallery templates with different roc_person_id.
[in]	ignore_identical	If `true`, similarity scores of ROC_MAX_SIMILARITY (indicating an identical match) will be ignored when constructing `candidates`.
[out]	candidates	Pre-allocated buffer to contain the top matching templates in `gallery`.

Remarks: This function is thread-safe and parallel.

◆ roc_rerank()

roc_error roc_rerank	(	roc_const_gallery	gallery,
		size_t	k,
		roc_candidate *	candidates
	)

Re-rank roc_search or roc_knn results based on commonly occuring roc_person_id and roc_template_index.

roc_search and roc_knn order each roc_candidate independently based soley on its roc_similarity score to the probe roc_template. This function re-orders candidates by considering commonly occuring roc_person_id and roc_template_index in candidates. After calling this function, the ordering is now based on the max of the similarities for all candidates with the same roc_person_id (or roc_template_index when roc_person_id is roc_uuid_is_null). In the resulting candidates, two roc_candidate with the same roc_person_id (or roc_template_index) will occur at adjacent indicies, ordered by roc_candidate::similarity. Note that the use of roc_template_index only comes into play when candidates is the ouput from roc_knn with multiple probes (from the same person) and the candidates have roc_uuid_is_null for roc_person_id.

Example: roc_const_gallery gallery = ...;
roc_template probe = ...;
roc_candidate candidates[10];
roc_search(gallery, probe, 10, 0, &candidates[0]);
roc_rerank(gallery, 10, &candidates[0]);

Parameters

[in]	gallery	The gallery used in the prior call to roc_search or roc_knn.
[in]	k	The length of `candidates` used in the prior call to roc_search or roc_knn.
[in,out]	candidates	Candidates list to re-order based on commonly occuring roc_template::person_id.

Remarks: This function is thread-safe.

See also: roc_search roc_knn roc_fuse

◆ roc_rank_persons()

roc_error roc_rank_persons	(	roc_const_gallery	gallery,
		const roc_template	probe,
		size_t	k,
		roc_person_id *	person_ids,
		roc_similarity *	similarities
	)

Order persons by similarity to probe.

The provided person_ids will be re-ordered by roc_similarity to probe, with the most similar roc_person_id first.

Parameters

[in]	gallery	Gallery of templates including those for `person_ids`.
[in]	probe	Probe template used to rank `person_ids`.
[in]	k	Length of `person_ids`.
[in,out]	person_ids	Persons to sort by similarity to `probe`.
[out]	similarities	Pre-allocated array of length `k` to contain the corresponding roc_similarity score for each element in `person_ids` to `probe`.

Remarks: This function is thread-safe.

◆ roc_consolidate_candidates()

roc_error roc_consolidate_candidates	(	roc_gallery	gallery,
		roc_similarity	max_similarity,
		size_t	k,
		roc_candidate *	candidates
	)

Downsample a candidate list by removing redundant templates.

This function greedily removes candidates toward the end of the list that match entries earlier in the list.

Parameters

[in]	gallery	The gallery containing the persons to consolidate.
[in]	max_similarity	The maximum pairwise similarity between candidates.
[in]	k	Length of `candidates`.
[in,out]	candidates	Top matching templates to consolidate.

Remarks: This function is thread-safe.

See also: roc_consolidate_persons

Data Structures

Typedefs

Functions

Detailed Description

Data Structure Documentation

◆ roc_candidate

Public Member Functions

Data Fields

Typedef Documentation

◆ roc_candidate

Function Documentation

◆ roc_search()

Number of Candidates

Minimum Similarity

◆ roc_knn()

Search Generalization

KNN Speed

Nearest Neighbors

Minimum Similarity

◆ roc_knn_and_cluster()

◆ roc_search_persons()

◆ roc_rerank()

◆ roc_rank_persons()

◆ roc_consolidate_candidates()