Chapter 9 Keypoint Recognition using Random Forests and Random Ferns ⇤

Abstract In many 3-D object-detection and pose-estimation problems, run-time performance is of critical importance. However, there usually is time to train the system. We introduce an approach that takes advantage of this fact by formulating wide-baseline matching of keypoints extracted from the input images to those found in the model images as a classification problem. This shifts much of the computa-tional burden to a training phase and eliminates the need for expensive patch pre-processing, without sacrificing recognition performance. This makes our approach highly suitable for real-time operations on low-powered devices. To this end, we developed two related methods. The first uses Random Forests that rely on simple binary tests on image intensities surrounding the keypoints. In the second, we flatten the trees to turn them into simple bit strings, which we will re-fer to as Ferns, and combine their output in a Naive Bayesian manner. Surprisingly, the Ferns, while simpler, actually perform better than the trees. This is because the Naive Bayesian approach benefits more from the thousands of synthetic training examples we can generate than output averaging as usually performed by Rando