Interesting how you arrived at a totally different local descriptors solution than me. I used ORB descriptors for the small size, with LSH. Then to improve recall speed, first build a list of candidates using a subset of the features, before checking all the features of the candidates. Dividing the image into quadrants is a good idea, I should have done that.