cv.BinaryDescriptorMatcher

BinaryDescriptor matcher class

Furnishes all functionalities for querying a dataset provided by user or internal to class (that user must, anyway, populate) on the model of Descriptor Matchers.

Once descriptors have been extracted from an image (both they represent lines and points), it becomes interesting to be able to match a descriptor with another one extracted from a different image and representing the same line or point, seen from a differente perspective or on a different scale. In reaching such goal, the main headache is designing an efficient search algorithm to associate a query descriptor to one extracted from a dataset. In the following, a matching modality based on Multi-Index Hashing (MiHashing) will be described.

Multi-Index Hashing

The theory described in this section is based on [MIH]. Given a dataset populated with binary codes, each code is indexed m times into m different hash tables, according to m substrings it has been divided into. Thus, given a query code, all the entries close to it at least in one substring are returned by search as neighbor candidates. Returned entries are then checked for validity by verifying that their full codes are not distant (in Hamming space) more than r bits from query code. In details, each binary code h composed of b bits is divided into m disjoint substrings h^(1), ..., h^(m), each with length floor(b/m) or ceil(b/m) bits. Formally, when two codes h and g differ by at the most r bits, in at the least one of their m substrings they differ by at the most floor(r/m) bits. In particular, when ||h-g||_H <= r (where ||.||_H is the Hamming norm), there must exist a substring k (with 1 <= k <= m) such that:

|| h^(k) - g^(k) ||_H <= floor(r/m)

That means that if Hamming distance between each of the m substring is strictly greater than floor(r/m), then ||h-g||_H must be larger that r and that is a contradiction. If the codes in dataset are divided into m substrings, then m tables will be built. Given a query q with substrings {q^(i)}_[i=1..m], i-th hash table is searched for entries distant at the most floor(r/m) from q^(i) and a set of candidates N_i(q) is obtained. The union of sets N(q) = U_i {N_i(q)} is a superset of the r-neighbors of q. Then, last step of algorithm is computing the Hamming distance between q and each element in N(q), deleting the codes that are distant more that r from q.

References

[MIH]:

Mohammad Norouzi, Ali Punjani, and David J Fleet. "Fast search in hamming space with Multi-Index Hashing". In Computer Vision and Pattern Recognition (CVPR), 2012 IEEE Conference on, pages 3108-3115. IEEE, 2012.

Superclasses	handle
Sealed	false
Construct on load	false

	add	Store locally new descriptors to be inserted in dataset, without updating dataset
	addlistener	Add listener for event.
	clear	Clear dataset and internal data
	delete	Destructor
	empty	Returns true if there are no train descriptors in the collection
	eq	== (EQ) Test handle equality.
	findobj	Find objects matching specified conditions.
	findprop	Find property of MATLAB handle object.
	ge	>= (GE) Greater than or equal relation for handles.
	getDefaultName	Returns the algorithm string identifier
	gt	> (GT) Greater than relation for handles.
Sealed	isvalid	Test handle validity.
	knnMatch	For every input query descriptor, retrieve the best k matching ones from a dataset provided from user or from the one internal to class
	le	<= (LE) Less than or equal relation for handles.
	listener	Add listener for event without binding the listener to the source object.
	load	Loads algorithm from a file or a string
	lt	< (LT) Less than relation for handles.
	match	For every input query descriptor, retrieve the best matching one from a dataset provided from user or from the one internal to class
	ne	~= (NE) Not equal relation for handles.
	notify	Notify listeners of event.
	radiusMatch	For every input query descriptor, retrieve, from a dataset provided from user or from the one internal to class, all the descriptors that are not further than maxDist from input query
	save	Saves the algorithm parameters to a file
	train	Update dataset by inserting into it all descriptors that were stored locally by add function