Itseez/opencv — pull request #2071 by pemmanuelviel (2013-12-26 23:23:44+00:00)
Title: Avoid obtaining several identical dimensions between two LSH sub-vectors by choosing orthogonal sub-vectors.

LSH algorithm consists in accelerating the vectors retrieval in a database by using several vectors of smaller dimension (e.g. 22 dimensions by default instead of usual 512 ones). These sub-vectors are created by picking randomly dimensions among the 512 ones.
But the more sub-vectors we have and the higher are their dimensions, the more dimensions will be common between two vectors. Thus the gain in quality for retrieving the closest vector in the database will not increase regularly with the number of sub-vectors (e.g. increase the sub-vectors number from 16 to 24 with a multi_probe_level set to 1)

To ensure a better repartition among dimensions, the best is to avoid having two vectors with dimensions in common. Thus we select orthogonal vectors.