How does BRIEF produce consistent keypoints with random sampling?
It looks to me as if they came up with a random pixel patch vs pixel patch set of points and they used this to train their system.  The system then recognizes different transformations by looking at the database of transformations and seeing how the transformations would affect the match.  It then picks the transformation with the best score (lowest Hamming distance).  The random pixel locations are only random once during the system design.