Sunday, March 6, 2011

Random Ferns Classifier - Semi-Naive-Bayes

The team that proposes training Randomized Trees on Binary Descriptors for fast key-point matching is trying another approach to speed up training and matching. This time they use Semi-Naive-Bayes classification instead of Randomized Trees. The word 'semi' here means that not all the input elements are independent. The input vector would be divided into groups. Only the probability densities among groups are assumed to be independent. The grouping is selected by randomized permutation. Input vector is extracted from a key-point region using binary-intensity-differences. 300 of them will be extracted from a 32x32 patch region. A typical group-size is 11, so there will be about 28 groups. Each group is a 'Fern', so it's called a Fern Classifier / Matcher. An input patch will be characterized by the SNB classifier to one of the classes - set of stable key-points. A product of posterior probabilities is calculated given a class label is true. The input patch would be classified to the one of highest value.

Training Phase: Very similar to Randomized Tree. Only a few training images is required. A set of stable key-points will be chosen by transforming the input images in many ways(300). These stable key-points becomes the class labels. Each image is then transformed again many more times (1000) to obtain the view-set. The classifier will keep count of each Fern pattern (vector of binary-intensity-differences of a group of pixel-pairs) for each associated class label. The counts are used to set the prior probabilities.

The training and testing for 2D matching is done on a video frame sequence. The frame with upright front facing object is chosen for training.

Implementation decision has to be made on how to divide up the input vector into groups - Fern-Size. Increasing fern-size yields better 'variations' handling. (Is this referring to perspective, lighting variants?) Care must be taken with respect to memory usage. The amount required to store the distributions increases quickly with Fern size. And it would need more training samples (to build distributions of a bigger set of possible values?). On the other hand, increasing number of Ferns while keeping the same Fern size (small?) (increased vector size?) gives better recognition rate. The comes with only linear memory increase. But the run-time costs increases (relevant?!).

There is a paper on mobile AR application using Ferns - Citation 34 "Pose Tracking from Natural Features on Mobile Phones", Wagner et al.

Demo (find_fern_obj)

This demo uses the LDetector class to detect object keypoints. And it uses PlanarObjectDetector class to do matching. FernsClassifier is one of PlanarObjectDetector members.
  1. Determine the most stable key-points from the object image (by recovering the key-points from affine-transformed object images).
  2. Build 3-level Image Pyramid for object image.
  3. Train the stable key-points with FernsClassifier and save the result to a file. The image pyramid is also supplied for training. Parameters include Ferns size, number of Ferns, Patch size, and Patch Generator.
  4. Load the PlanarObjectDetector from the file obtained from the last step.
  5. Use the LDetector to find keypoints from the scene image pyramid. Match them against the object key-points using the PlanarObjectDetector. The results are represented as index-pairs between the model-keypoints and the scene-keypoints. The model-keypoints are the stable keypoints of object-image. The list is available from the loaded PlanarObjectDetector instance.
  6. Draw the correspondences on screen.
More notes: Object and Scene Images are loaded as grayscale. And they are smoothed with a Gaussian Filter.

Demo (generic_descriptor_matcher)

The simplest way to exercise Ferns matching is to use the FernDescriptorMatcher class. The demo program is very straightforward. The find_obj_ferns demo app is more informative.

Results and Observations

Using ball.pgm (book is pictured sideways) from Dundee test set as training image.

In most cases, it is able to find and locate correctly from the scene images it appears on. The worst result is TestImg010.jpg. It cannot locate the whole upside down book. I suppose that is because the lack of keypoints detected. The book title "Rivera" is obscured.

Test for false-positive using TestImg02.pgm. The detector return status of 'found' but it was obviously wrong. Half of it is 'out-of-the-picture'.

Fast Keypoint Recognition using Random Ferns, Ozuyal et al.


  1. Nice article ! :) Just one question ... and sorry for such a silly question .It is about the files you are mentioning here.Is there a link to those files? I am actually reading about the Random Ferns Classifier.And i found it may help me. Thanks in advance.

  2. Hi, here is the url of the imageset from Dundee university:
    Good luck!

  3. Hi, currently I have 1200 trainig images(labelled) and I want to train them using fern classifier in order to classify them into 8 classes.

    However, I looked trough the opencv fernClassifier class-->
    virtual void cv::FernClassifier::train ( const vector< vector< Point2f > > & points,
    const vector< Mat > & refimgs,
    const vector< vector< int > > & labels = vector< vector< int > >(),
    int _nclasses = 0,
    int _patchSize = PATCH_SIZE,
    int _signatureSize = DEFAULT_SIGNATURE_SIZE,
    int _nstructs = DEFAULT_STRUCTS,
    int _structSize = DEFAULT_STRUCT_SIZE,
    int _nviews = DEFAULT_VIEWS,
    int _compressionMethod = COMPRESSION_NONE,
    const PatchGenerator & patchGenerator = PatchGenerator()

    I am not sure about the meaning of points, refimgs and labels. For what I think is points is key points/ feature of 1200 labelled image. And, the refimgs is the 1200 labelled training images. While, labels is the label classes of each 1200 images.

    Please correct me if I wrong. Thank you.

    1. Hi adeline,

      I think the idea is right. I have not get back to this topic in a while. So I am a bit blurry at the details. You might find better help at the OpenCV forums at Yahoo /

  4. Hi, i try to run the generic_descriptor_matcher file with Ferns but it always says that is not able to create the descriptor. My Question is how do i use the FernDescriptorMatcher class correctly?

    1. Hello, there are 4 command-line arguments required by the generic_descriptor_match sample app. (See 'help()' function). Please make sure you specify FERN. I was using OpenCV 2.2 when I wrote the post, you might want to check to see if it still the same in your OpenCV version.

  5. Hi all, how can i find source code of this paper?